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