1 
2 /* Author : Stephen Smalley, <sds@tycho.nsa.gov> */
3 
4 /* FLASK */
5 
6 /*
7  * Implementation of the extensible bitmap type.
8  */
9 
10 #include <stdlib.h>
11 
12 #include <sepol/policydb/ebitmap.h>
13 #include <sepol/policydb/policydb.h>
14 
15 #include "debug.h"
16 #include "private.h"
17 
ebitmap_or(ebitmap_t * dst,const ebitmap_t * e1,const ebitmap_t * e2)18 int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2)
19 {
20 	ebitmap_node_t *n1, *n2, *new, *prev;
21 
22 	ebitmap_init(dst);
23 
24 	n1 = e1->node;
25 	n2 = e2->node;
26 	prev = 0;
27 	while (n1 || n2) {
28 		new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
29 		if (!new) {
30 			ebitmap_destroy(dst);
31 			return -ENOMEM;
32 		}
33 		memset(new, 0, sizeof(ebitmap_node_t));
34 		if (n1 && n2 && n1->startbit == n2->startbit) {
35 			new->startbit = n1->startbit;
36 			new->map = n1->map | n2->map;
37 			n1 = n1->next;
38 			n2 = n2->next;
39 		} else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
40 			new->startbit = n1->startbit;
41 			new->map = n1->map;
42 			n1 = n1->next;
43 		} else {
44 			new->startbit = n2->startbit;
45 			new->map = n2->map;
46 			n2 = n2->next;
47 		}
48 
49 		new->next = 0;
50 		if (prev)
51 			prev->next = new;
52 		else
53 			dst->node = new;
54 		prev = new;
55 	}
56 
57 	dst->highbit = (e1->highbit > e2->highbit) ? e1->highbit : e2->highbit;
58 	return 0;
59 }
60 
ebitmap_union(ebitmap_t * dst,const ebitmap_t * e1)61 int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
62 {
63 	ebitmap_t tmp;
64 
65 	if (ebitmap_or(&tmp, dst, e1))
66 		return -1;
67 	ebitmap_destroy(dst);
68 	dst->node = tmp.node;
69 	dst->highbit = tmp.highbit;
70 
71 	return 0;
72 }
73 
ebitmap_and(ebitmap_t * dst,ebitmap_t * e1,ebitmap_t * e2)74 int ebitmap_and(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2)
75 {
76 	unsigned int i, length = min(ebitmap_length(e1), ebitmap_length(e2));
77 	ebitmap_init(dst);
78 	for (i=0; i < length; i++) {
79 		if (ebitmap_get_bit(e1, i) && ebitmap_get_bit(e2, i)) {
80 			int rc = ebitmap_set_bit(dst, i, 1);
81 			if (rc < 0)
82 				return rc;
83 		}
84 	}
85 	return 0;
86 }
87 
ebitmap_xor(ebitmap_t * dst,ebitmap_t * e1,ebitmap_t * e2)88 int ebitmap_xor(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2)
89 {
90 	unsigned int i, length = max(ebitmap_length(e1), ebitmap_length(e2));
91 	ebitmap_init(dst);
92 	for (i=0; i < length; i++) {
93 		int val = ebitmap_get_bit(e1, i) ^ ebitmap_get_bit(e2, i);
94 		int rc = ebitmap_set_bit(dst, i, val);
95 		if (rc < 0)
96 			return rc;
97 	}
98 	return 0;
99 }
100 
ebitmap_not(ebitmap_t * dst,ebitmap_t * e1,unsigned int maxbit)101 int ebitmap_not(ebitmap_t *dst, ebitmap_t *e1, unsigned int maxbit)
102 {
103 	unsigned int i;
104 	ebitmap_init(dst);
105 	for (i=0; i < maxbit; i++) {
106 		int val = ebitmap_get_bit(e1, i);
107 		int rc = ebitmap_set_bit(dst, i, !val);
108 		if (rc < 0)
109 			return rc;
110 	}
111 	return 0;
112 }
113 
ebitmap_andnot(ebitmap_t * dst,ebitmap_t * e1,ebitmap_t * e2,unsigned int maxbit)114 int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int maxbit)
115 {
116 	ebitmap_t e3;
117 	ebitmap_init(dst);
118 	int rc = ebitmap_not(&e3, e2, maxbit);
119 	if (rc < 0)
120 		return rc;
121 	rc = ebitmap_and(dst, e1, &e3);
122 	ebitmap_destroy(&e3);
123 	if (rc < 0)
124 		return rc;
125 	return 0;
126 }
127 
ebitmap_cardinality(ebitmap_t * e1)128 unsigned int ebitmap_cardinality(ebitmap_t *e1)
129 {
130 	unsigned int i, count = 0;
131 	for (i=ebitmap_startbit(e1); i < ebitmap_length(e1); i++)
132 		if (ebitmap_get_bit(e1, i))
133 			count++;
134 	return count;
135 }
136 
ebitmap_hamming_distance(ebitmap_t * e1,ebitmap_t * e2)137 int ebitmap_hamming_distance(ebitmap_t * e1, ebitmap_t * e2)
138 {
139 	if (ebitmap_cmp(e1, e2))
140 		return 0;
141 	ebitmap_t tmp;
142 	int rc = ebitmap_xor(&tmp, e1, e2);
143 	if (rc < 0)
144 		return -1;
145 	int distance = ebitmap_cardinality(&tmp);
146 	ebitmap_destroy(&tmp);
147 	return distance;
148 }
149 
ebitmap_cmp(const ebitmap_t * e1,const ebitmap_t * e2)150 int ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2)
151 {
152 	ebitmap_node_t *n1, *n2;
153 
154 	if (e1->highbit != e2->highbit)
155 		return 0;
156 
157 	n1 = e1->node;
158 	n2 = e2->node;
159 	while (n1 && n2 &&
160 	       (n1->startbit == n2->startbit) && (n1->map == n2->map)) {
161 		n1 = n1->next;
162 		n2 = n2->next;
163 	}
164 
165 	if (n1 || n2)
166 		return 0;
167 
168 	return 1;
169 }
170 
ebitmap_cpy(ebitmap_t * dst,const ebitmap_t * src)171 int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
172 {
173 	ebitmap_node_t *n, *new, *prev;
174 
175 	ebitmap_init(dst);
176 	n = src->node;
177 	prev = 0;
178 	while (n) {
179 		new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
180 		if (!new) {
181 			ebitmap_destroy(dst);
182 			return -ENOMEM;
183 		}
184 		memset(new, 0, sizeof(ebitmap_node_t));
185 		new->startbit = n->startbit;
186 		new->map = n->map;
187 		new->next = 0;
188 		if (prev)
189 			prev->next = new;
190 		else
191 			dst->node = new;
192 		prev = new;
193 		n = n->next;
194 	}
195 
196 	dst->highbit = src->highbit;
197 	return 0;
198 }
199 
ebitmap_contains(const ebitmap_t * e1,const ebitmap_t * e2)200 int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2)
201 {
202 	ebitmap_node_t *n1, *n2;
203 
204 	if (e1->highbit < e2->highbit)
205 		return 0;
206 
207 	n1 = e1->node;
208 	n2 = e2->node;
209 	while (n1 && n2 && (n1->startbit <= n2->startbit)) {
210 		if (n1->startbit < n2->startbit) {
211 			n1 = n1->next;
212 			continue;
213 		}
214 		if ((n1->map & n2->map) != n2->map)
215 			return 0;
216 
217 		n1 = n1->next;
218 		n2 = n2->next;
219 	}
220 
221 	if (n2)
222 		return 0;
223 
224 	return 1;
225 }
226 
ebitmap_match_any(const ebitmap_t * e1,const ebitmap_t * e2)227 int ebitmap_match_any(const ebitmap_t *e1, const ebitmap_t *e2)
228 {
229 	ebitmap_node_t *n1 = e1->node;
230 	ebitmap_node_t *n2 = e2->node;
231 
232 	while (n1 && n2) {
233 		if (n1->startbit < n2->startbit) {
234 			n1 = n1->next;
235 		} else if (n2->startbit < n1->startbit) {
236 			n2 = n2->next;
237 		} else {
238 			if (n1->map & n2->map) {
239 				return 1;
240 			}
241 			n1 = n1->next;
242 			n2 = n2->next;
243 		}
244 	}
245 
246 	return 0;
247 }
248 
ebitmap_get_bit(const ebitmap_t * e,unsigned int bit)249 int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit)
250 {
251 	ebitmap_node_t *n;
252 
253 	if (e->highbit < bit)
254 		return 0;
255 
256 	n = e->node;
257 	while (n && (n->startbit <= bit)) {
258 		if ((n->startbit + MAPSIZE) > bit) {
259 			if (n->map & (MAPBIT << (bit - n->startbit)))
260 				return 1;
261 			else
262 				return 0;
263 		}
264 		n = n->next;
265 	}
266 
267 	return 0;
268 }
269 
ebitmap_set_bit(ebitmap_t * e,unsigned int bit,int value)270 int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
271 {
272 	ebitmap_node_t *n, *prev, *new;
273 	uint32_t startbit = bit & ~(MAPSIZE - 1);
274 	uint32_t highbit = startbit + MAPSIZE;
275 
276 	if (highbit == 0) {
277 		ERR(NULL, "bitmap overflow, bit 0x%x", bit);
278 		return -EINVAL;
279 	}
280 
281 	prev = 0;
282 	n = e->node;
283 	while (n && n->startbit <= bit) {
284 		if ((n->startbit + MAPSIZE) > bit) {
285 			if (value) {
286 				n->map |= (MAPBIT << (bit - n->startbit));
287 			} else {
288 				n->map &= ~(MAPBIT << (bit - n->startbit));
289 				if (!n->map) {
290 					/* drop this node from the bitmap */
291 
292 					if (!n->next) {
293 						/*
294 						 * this was the highest map
295 						 * within the bitmap
296 						 */
297 						if (prev)
298 							e->highbit =
299 							    prev->startbit +
300 							    MAPSIZE;
301 						else
302 							e->highbit = 0;
303 					}
304 					if (prev)
305 						prev->next = n->next;
306 					else
307 						e->node = n->next;
308 
309 					free(n);
310 				}
311 			}
312 			return 0;
313 		}
314 		prev = n;
315 		n = n->next;
316 	}
317 
318 	if (!value)
319 		return 0;
320 
321 	new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
322 	if (!new)
323 		return -ENOMEM;
324 	memset(new, 0, sizeof(ebitmap_node_t));
325 
326 	new->startbit = startbit;
327 	new->map = (MAPBIT << (bit - new->startbit));
328 
329 	if (!n) {
330 		/* this node will be the highest map within the bitmap */
331 		e->highbit = highbit;
332 	}
333 
334 	if (prev) {
335 		new->next = prev->next;
336 		prev->next = new;
337 	} else {
338 		new->next = e->node;
339 		e->node = new;
340 	}
341 
342 	return 0;
343 }
344 
ebitmap_destroy(ebitmap_t * e)345 void ebitmap_destroy(ebitmap_t * e)
346 {
347 	ebitmap_node_t *n, *temp;
348 
349 	if (!e)
350 		return;
351 
352 	n = e->node;
353 	while (n) {
354 		temp = n;
355 		n = n->next;
356 		free(temp);
357 	}
358 
359 	e->highbit = 0;
360 	e->node = 0;
361 	return;
362 }
363 
ebitmap_read(ebitmap_t * e,void * fp)364 int ebitmap_read(ebitmap_t * e, void *fp)
365 {
366 	int rc;
367 	ebitmap_node_t *n, *l;
368 	uint32_t buf[3], mapsize, count, i;
369 	uint64_t map;
370 
371 	ebitmap_init(e);
372 
373 	rc = next_entry(buf, fp, sizeof(uint32_t) * 3);
374 	if (rc < 0)
375 		goto bad;
376 
377 	mapsize = le32_to_cpu(buf[0]);
378 	e->highbit = le32_to_cpu(buf[1]);
379 	count = le32_to_cpu(buf[2]);
380 
381 	if (mapsize != MAPSIZE) {
382 		printf
383 		    ("security: ebitmap: map size %d does not match my size %zu (high bit was %d)\n",
384 		     mapsize, MAPSIZE, e->highbit);
385 		goto bad;
386 	}
387 	if (!e->highbit) {
388 		e->node = NULL;
389 		goto ok;
390 	}
391 	if (e->highbit & (MAPSIZE - 1)) {
392 		printf
393 		    ("security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)\n",
394 		     e->highbit, MAPSIZE);
395 		goto bad;
396 	}
397 
398 	if (e->highbit && !count)
399 		goto bad;
400 
401 	l = NULL;
402 	for (i = 0; i < count; i++) {
403 		rc = next_entry(buf, fp, sizeof(uint32_t));
404 		if (rc < 0) {
405 			printf("security: ebitmap: truncated map\n");
406 			goto bad;
407 		}
408 		n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
409 		if (!n) {
410 			printf("security: ebitmap: out of memory\n");
411 			rc = -ENOMEM;
412 			goto bad;
413 		}
414 		memset(n, 0, sizeof(ebitmap_node_t));
415 
416 		n->startbit = le32_to_cpu(buf[0]);
417 
418 		if (n->startbit & (MAPSIZE - 1)) {
419 			printf
420 			    ("security: ebitmap start bit (%d) is not a multiple of the map size (%zu)\n",
421 			     n->startbit, MAPSIZE);
422 			goto bad_free;
423 		}
424 		if (n->startbit > (e->highbit - MAPSIZE)) {
425 			printf
426 			    ("security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)\n",
427 			     n->startbit, (e->highbit - MAPSIZE));
428 			goto bad_free;
429 		}
430 		rc = next_entry(&map, fp, sizeof(uint64_t));
431 		if (rc < 0) {
432 			printf("security: ebitmap: truncated map\n");
433 			goto bad_free;
434 		}
435 		n->map = le64_to_cpu(map);
436 
437 		if (!n->map) {
438 			printf
439 			    ("security: ebitmap: null map in ebitmap (startbit %d)\n",
440 			     n->startbit);
441 			goto bad_free;
442 		}
443 		if (l) {
444 			if (n->startbit <= l->startbit) {
445 				printf
446 				    ("security: ebitmap: start bit %d comes after start bit %d\n",
447 				     n->startbit, l->startbit);
448 				goto bad_free;
449 			}
450 			l->next = n;
451 		} else
452 			e->node = n;
453 
454 		l = n;
455 	}
456 	if (count && l->startbit + MAPSIZE != e->highbit) {
457 		printf
458 		    ("security: ebitmap: hight bit %u has not the expected value %zu\n",
459 		     e->highbit, l->startbit + MAPSIZE);
460 		goto bad;
461 	}
462 
463       ok:
464 	rc = 0;
465       out:
466 	return rc;
467       bad_free:
468 	free(n);
469       bad:
470 	if (!rc)
471 		rc = -EINVAL;
472 	ebitmap_destroy(e);
473 	goto out;
474 }
475 
476 /* FLASK */
477