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