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 const ebitmap_node_t *n1, *n2;
21 ebitmap_node_t *new, *prev;
22
23 ebitmap_init(dst);
24
25 n1 = e1->node;
26 n2 = e2->node;
27 prev = 0;
28 while (n1 || n2) {
29 new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
30 if (!new) {
31 ebitmap_destroy(dst);
32 return -ENOMEM;
33 }
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,const ebitmap_t * e1,const ebitmap_t * e2)74 int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
75 {
76 const ebitmap_node_t *n1, *n2;
77 ebitmap_node_t *new, *prev = NULL;
78
79 ebitmap_init(dst);
80
81 n1 = e1->node;
82 n2 = e2->node;
83 while (n1 && n2) {
84 if (n1->startbit == n2->startbit) {
85 if (n1->map & n2->map) {
86 new = malloc(sizeof(ebitmap_node_t));
87 if (!new) {
88 ebitmap_destroy(dst);
89 return -ENOMEM;
90 }
91 new->startbit = n1->startbit;
92 new->map = n1->map & n2->map;
93 new->next = NULL;
94
95 if (prev)
96 prev->next = new;
97 else
98 dst->node = new;
99 prev = new;
100 }
101
102 n1 = n1->next;
103 n2 = n2->next;
104 } else if (n1->startbit > n2->startbit) {
105 n2 = n2->next;
106 } else {
107 n1 = n1->next;
108 }
109 }
110
111 if (prev)
112 dst->highbit = prev->startbit + MAPSIZE;
113
114 return 0;
115 }
116
ebitmap_xor(ebitmap_t * dst,const ebitmap_t * e1,const ebitmap_t * e2)117 int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
118 {
119 const ebitmap_node_t *n1, *n2;
120 ebitmap_node_t *new, *prev = NULL;
121 uint32_t startbit;
122 MAPTYPE map;
123
124 ebitmap_init(dst);
125
126 n1 = e1->node;
127 n2 = e2->node;
128 while (n1 || n2) {
129 if (n1 && n2 && n1->startbit == n2->startbit) {
130 startbit = n1->startbit;
131 map = n1->map ^ n2->map;
132 n1 = n1->next;
133 n2 = n2->next;
134 } else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
135 startbit = n1->startbit;
136 map = n1->map;
137 n1 = n1->next;
138 } else {
139 startbit = n2->startbit;
140 map = n2->map;
141 n2 = n2->next;
142 }
143
144 if (map != 0) {
145 new = malloc(sizeof(ebitmap_node_t));
146 if (!new) {
147 ebitmap_destroy(dst);
148 return -ENOMEM;
149 }
150 new->startbit = startbit;
151 new->map = map;
152 new->next = NULL;
153 if (prev)
154 prev->next = new;
155 else
156 dst->node = new;
157 prev = new;
158 }
159 }
160
161 if (prev)
162 dst->highbit = prev->startbit + MAPSIZE;
163
164 return 0;
165 }
166
ebitmap_not(ebitmap_t * dst,const ebitmap_t * e1,unsigned int maxbit)167 int ebitmap_not(ebitmap_t *dst, const ebitmap_t *e1, unsigned int maxbit)
168 {
169 const ebitmap_node_t *n;
170 ebitmap_node_t *new, *prev = NULL;
171 uint32_t startbit, cur_startbit;
172 MAPTYPE map;
173
174 ebitmap_init(dst);
175
176 n = e1->node;
177 for (cur_startbit = 0; cur_startbit < maxbit; cur_startbit += MAPSIZE) {
178 if (n && n->startbit == cur_startbit) {
179 startbit = n->startbit;
180 map = ~n->map;
181
182 n = n->next;
183 } else {
184 startbit = cur_startbit;
185 map = ~((MAPTYPE) 0);
186 }
187
188 if (maxbit - cur_startbit < MAPSIZE)
189 map &= (((MAPTYPE)1) << (maxbit - cur_startbit)) - 1;
190
191 if (map != 0) {
192 new = malloc(sizeof(ebitmap_node_t));
193 if (!new) {
194 ebitmap_destroy(dst);
195 return -ENOMEM;
196 }
197
198 new->startbit = startbit;
199 new->map = map;
200 new->next = NULL;
201
202 if (prev)
203 prev->next = new;
204 else
205 dst->node = new;
206 prev = new;
207 }
208 }
209
210 if (prev)
211 dst->highbit = prev->startbit + MAPSIZE;
212
213 return 0;
214 }
215
ebitmap_andnot(ebitmap_t * dst,const ebitmap_t * e1,const ebitmap_t * e2,unsigned int maxbit)216 int ebitmap_andnot(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2, unsigned int maxbit)
217 {
218 int rc;
219 ebitmap_t e3;
220 ebitmap_init(dst);
221 rc = ebitmap_not(&e3, e2, maxbit);
222 if (rc < 0)
223 return rc;
224 rc = ebitmap_and(dst, e1, &e3);
225 ebitmap_destroy(&e3);
226 if (rc < 0)
227 return rc;
228 return 0;
229 }
230
ebitmap_cardinality(const ebitmap_t * e1)231 unsigned int ebitmap_cardinality(const ebitmap_t *e1)
232 {
233 unsigned int count = 0;
234 const ebitmap_node_t *n;
235
236 for (n = e1->node; n; n = n->next) {
237 count += __builtin_popcountll(n->map);
238 }
239 return count;
240 }
241
ebitmap_hamming_distance(const ebitmap_t * e1,const ebitmap_t * e2)242 int ebitmap_hamming_distance(const ebitmap_t * e1, const ebitmap_t * e2)
243 {
244 int rc;
245 ebitmap_t tmp;
246 int distance;
247 if (ebitmap_cmp(e1, e2))
248 return 0;
249 rc = ebitmap_xor(&tmp, e1, e2);
250 if (rc < 0)
251 return -1;
252 distance = ebitmap_cardinality(&tmp);
253 ebitmap_destroy(&tmp);
254 return distance;
255 }
256
ebitmap_cmp(const ebitmap_t * e1,const ebitmap_t * e2)257 int ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2)
258 {
259 const ebitmap_node_t *n1, *n2;
260
261 if (e1->highbit != e2->highbit)
262 return 0;
263
264 n1 = e1->node;
265 n2 = e2->node;
266 while (n1 && n2 &&
267 (n1->startbit == n2->startbit) && (n1->map == n2->map)) {
268 n1 = n1->next;
269 n2 = n2->next;
270 }
271
272 if (n1 || n2)
273 return 0;
274
275 return 1;
276 }
277
ebitmap_cpy(ebitmap_t * dst,const ebitmap_t * src)278 int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
279 {
280 const ebitmap_node_t *n;
281 ebitmap_node_t *new, *prev;
282
283 ebitmap_init(dst);
284 n = src->node;
285 prev = 0;
286 while (n) {
287 new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
288 if (!new) {
289 ebitmap_destroy(dst);
290 return -ENOMEM;
291 }
292 new->startbit = n->startbit;
293 new->map = n->map;
294 new->next = 0;
295 if (prev)
296 prev->next = new;
297 else
298 dst->node = new;
299 prev = new;
300 n = n->next;
301 }
302
303 dst->highbit = src->highbit;
304 return 0;
305 }
306
ebitmap_contains(const ebitmap_t * e1,const ebitmap_t * e2)307 int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2)
308 {
309 const ebitmap_node_t *n1, *n2;
310
311 if (e1->highbit < e2->highbit)
312 return 0;
313
314 n1 = e1->node;
315 n2 = e2->node;
316 while (n1 && n2 && (n1->startbit <= n2->startbit)) {
317 if (n1->startbit < n2->startbit) {
318 n1 = n1->next;
319 continue;
320 }
321 if ((n1->map & n2->map) != n2->map)
322 return 0;
323
324 n1 = n1->next;
325 n2 = n2->next;
326 }
327
328 if (n2)
329 return 0;
330
331 return 1;
332 }
333
ebitmap_match_any(const ebitmap_t * e1,const ebitmap_t * e2)334 int ebitmap_match_any(const ebitmap_t *e1, const ebitmap_t *e2)
335 {
336 const ebitmap_node_t *n1 = e1->node;
337 const ebitmap_node_t *n2 = e2->node;
338
339 while (n1 && n2) {
340 if (n1->startbit < n2->startbit) {
341 n1 = n1->next;
342 } else if (n2->startbit < n1->startbit) {
343 n2 = n2->next;
344 } else {
345 if (n1->map & n2->map) {
346 return 1;
347 }
348 n1 = n1->next;
349 n2 = n2->next;
350 }
351 }
352
353 return 0;
354 }
355
ebitmap_get_bit(const ebitmap_t * e,unsigned int bit)356 int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit)
357 {
358 const ebitmap_node_t *n;
359
360 if (e->highbit < bit)
361 return 0;
362
363 n = e->node;
364 while (n && (n->startbit <= bit)) {
365 if ((n->startbit + MAPSIZE) > bit) {
366 if (n->map & (MAPBIT << (bit - n->startbit)))
367 return 1;
368 else
369 return 0;
370 }
371 n = n->next;
372 }
373
374 return 0;
375 }
376
ebitmap_set_bit(ebitmap_t * e,unsigned int bit,int value)377 int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
378 {
379 ebitmap_node_t *n, *prev, *new;
380 uint32_t startbit = bit & ~(MAPSIZE - 1);
381 uint32_t highbit = startbit + MAPSIZE;
382
383 if (highbit == 0) {
384 ERR(NULL, "bitmap overflow, bit 0x%x", bit);
385 return -EINVAL;
386 }
387
388 prev = 0;
389 n = e->node;
390 while (n && n->startbit <= bit) {
391 if ((n->startbit + MAPSIZE) > bit) {
392 if (value) {
393 n->map |= (MAPBIT << (bit - n->startbit));
394 } else {
395 n->map &= ~(MAPBIT << (bit - n->startbit));
396 if (!n->map) {
397 /* drop this node from the bitmap */
398
399 if (!n->next) {
400 /*
401 * this was the highest map
402 * within the bitmap
403 */
404 if (prev)
405 e->highbit =
406 prev->startbit +
407 MAPSIZE;
408 else
409 e->highbit = 0;
410 }
411 if (prev)
412 prev->next = n->next;
413 else
414 e->node = n->next;
415
416 free(n);
417 }
418 }
419 return 0;
420 }
421 prev = n;
422 n = n->next;
423 }
424
425 if (!value)
426 return 0;
427
428 new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
429 if (!new)
430 return -ENOMEM;
431
432 new->startbit = startbit;
433 new->map = (MAPBIT << (bit - new->startbit));
434
435 if (!n) {
436 /* this node will be the highest map within the bitmap */
437 e->highbit = highbit;
438 }
439
440 if (prev) {
441 new->next = prev->next;
442 prev->next = new;
443 } else {
444 new->next = e->node;
445 e->node = new;
446 }
447
448 return 0;
449 }
450
ebitmap_init_range(ebitmap_t * e,unsigned int minbit,unsigned int maxbit)451 int ebitmap_init_range(ebitmap_t * e, unsigned int minbit, unsigned int maxbit)
452 {
453 ebitmap_node_t *new, *prev = NULL;
454 uint32_t minstartbit = minbit & ~(MAPSIZE - 1);
455 uint32_t maxstartbit = maxbit & ~(MAPSIZE - 1);
456 uint32_t minhighbit = minstartbit + MAPSIZE;
457 uint32_t maxhighbit = maxstartbit + MAPSIZE;
458 uint32_t startbit;
459 MAPTYPE mask;
460
461 ebitmap_init(e);
462
463 if (minbit > maxbit)
464 return -EINVAL;
465
466 if (minhighbit == 0 || maxhighbit == 0)
467 return -EOVERFLOW;
468
469 for (startbit = minstartbit; startbit <= maxstartbit; startbit += MAPSIZE) {
470 new = malloc(sizeof(ebitmap_node_t));
471 if (!new)
472 return -ENOMEM;
473
474 new->next = NULL;
475 new->startbit = startbit;
476
477 if (startbit != minstartbit && startbit != maxstartbit) {
478 new->map = ~((MAPTYPE)0);
479 } else if (startbit != maxstartbit) {
480 new->map = ~((MAPTYPE)0) << (minbit - startbit);
481 } else if (startbit != minstartbit) {
482 new->map = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - startbit + 1));
483 } else {
484 mask = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - minbit + 1));
485 new->map = (mask << (minbit - startbit));
486 }
487
488 if (prev)
489 prev->next = new;
490 else
491 e->node = new;
492 prev = new;
493 }
494
495 e->highbit = maxhighbit;
496
497 return 0;
498 }
499
ebitmap_highest_set_bit(const ebitmap_t * e)500 unsigned int ebitmap_highest_set_bit(const ebitmap_t * e)
501 {
502 const ebitmap_node_t *n;
503 MAPTYPE map;
504 unsigned int pos = 0;
505
506 n = e->node;
507 if (!n)
508 return 0;
509
510 while (n->next)
511 n = n->next;
512
513 map = n->map;
514 while (map >>= 1)
515 pos++;
516
517 return n->startbit + pos;
518 }
519
ebitmap_destroy(ebitmap_t * e)520 void ebitmap_destroy(ebitmap_t * e)
521 {
522 ebitmap_node_t *n, *temp;
523
524 if (!e)
525 return;
526
527 n = e->node;
528 while (n) {
529 temp = n;
530 n = n->next;
531 free(temp);
532 }
533
534 e->highbit = 0;
535 e->node = 0;
536 return;
537 }
538
ebitmap_read(ebitmap_t * e,void * fp)539 int ebitmap_read(ebitmap_t * e, void *fp)
540 {
541 int rc;
542 ebitmap_node_t *n, *l;
543 uint32_t buf[3], mapsize, count, i;
544 uint64_t map;
545
546 ebitmap_init(e);
547
548 rc = next_entry(buf, fp, sizeof(uint32_t) * 3);
549 if (rc < 0)
550 goto bad;
551
552 mapsize = le32_to_cpu(buf[0]);
553 e->highbit = le32_to_cpu(buf[1]);
554 count = le32_to_cpu(buf[2]);
555
556 if (mapsize != MAPSIZE) {
557 ERR(NULL, "security: ebitmap: map size %d does not match my size %zu (high bit was %d)",
558 mapsize, MAPSIZE, e->highbit);
559 goto bad;
560 }
561 if (!e->highbit) {
562 e->node = NULL;
563 goto ok;
564 }
565 if (e->highbit & (MAPSIZE - 1)) {
566 ERR(NULL, "security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)",
567 e->highbit, MAPSIZE);
568 goto bad;
569 }
570
571 if (e->highbit && !count)
572 goto bad;
573
574 l = NULL;
575 for (i = 0; i < count; i++) {
576 rc = next_entry(buf, fp, sizeof(uint32_t));
577 if (rc < 0) {
578 ERR(NULL, "security: ebitmap: truncated map");
579 goto bad;
580 }
581 n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
582 if (!n) {
583 ERR(NULL, "security: ebitmap: out of memory");
584 rc = -ENOMEM;
585 goto bad;
586 }
587 memset(n, 0, sizeof(ebitmap_node_t));
588
589 n->startbit = le32_to_cpu(buf[0]);
590
591 if (n->startbit & (MAPSIZE - 1)) {
592 ERR(NULL, "security: ebitmap start bit (%d) is not a multiple of the map size (%zu)",
593 n->startbit, MAPSIZE);
594 goto bad_free;
595 }
596 if (n->startbit > (e->highbit - MAPSIZE)) {
597 ERR(NULL, "security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)",
598 n->startbit, (e->highbit - MAPSIZE));
599 goto bad_free;
600 }
601 rc = next_entry(&map, fp, sizeof(uint64_t));
602 if (rc < 0) {
603 ERR(NULL, "security: ebitmap: truncated map");
604 goto bad_free;
605 }
606 n->map = le64_to_cpu(map);
607
608 if (!n->map) {
609 ERR(NULL, "security: ebitmap: null map in ebitmap (startbit %d)",
610 n->startbit);
611 goto bad_free;
612 }
613 if (l) {
614 if (n->startbit <= l->startbit) {
615 ERR(NULL, "security: ebitmap: start bit %d comes after start bit %d",
616 n->startbit, l->startbit);
617 goto bad_free;
618 }
619 l->next = n;
620 } else
621 e->node = n;
622
623 l = n;
624 }
625 if (count && l->startbit + MAPSIZE != e->highbit) {
626 ERR(NULL, "security: ebitmap: high bit %u has not the expected value %zu",
627 e->highbit, l->startbit + MAPSIZE);
628 goto bad;
629 }
630
631 ok:
632 rc = 0;
633 out:
634 return rc;
635 bad_free:
636 free(n);
637 bad:
638 if (!rc)
639 rc = -EINVAL;
640 ebitmap_destroy(e);
641 goto out;
642 }
643
644 /* FLASK */
645