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