1
2 /* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
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_get_bit(const ebitmap_t * e,unsigned int bit)227 int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit)
228 {
229 ebitmap_node_t *n;
230
231 if (e->highbit < bit)
232 return 0;
233
234 n = e->node;
235 while (n && (n->startbit <= bit)) {
236 if ((n->startbit + MAPSIZE) > bit) {
237 if (n->map & (MAPBIT << (bit - n->startbit)))
238 return 1;
239 else
240 return 0;
241 }
242 n = n->next;
243 }
244
245 return 0;
246 }
247
ebitmap_set_bit(ebitmap_t * e,unsigned int bit,int value)248 int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
249 {
250 ebitmap_node_t *n, *prev, *new;
251 uint32_t startbit = bit & ~(MAPSIZE - 1);
252 uint32_t highbit = startbit + MAPSIZE;
253
254 if (highbit == 0) {
255 ERR(NULL, "bitmap overflow, bit 0x%x", bit);
256 return -EINVAL;
257 }
258
259 prev = 0;
260 n = e->node;
261 while (n && n->startbit <= bit) {
262 if ((n->startbit + MAPSIZE) > bit) {
263 if (value) {
264 n->map |= (MAPBIT << (bit - n->startbit));
265 } else {
266 n->map &= ~(MAPBIT << (bit - n->startbit));
267 if (!n->map) {
268 /* drop this node from the bitmap */
269
270 if (!n->next) {
271 /*
272 * this was the highest map
273 * within the bitmap
274 */
275 if (prev)
276 e->highbit =
277 prev->startbit +
278 MAPSIZE;
279 else
280 e->highbit = 0;
281 }
282 if (prev)
283 prev->next = n->next;
284 else
285 e->node = n->next;
286
287 free(n);
288 }
289 }
290 return 0;
291 }
292 prev = n;
293 n = n->next;
294 }
295
296 if (!value)
297 return 0;
298
299 new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
300 if (!new)
301 return -ENOMEM;
302 memset(new, 0, sizeof(ebitmap_node_t));
303
304 new->startbit = startbit;
305 new->map = (MAPBIT << (bit - new->startbit));
306
307 if (!n) {
308 /* this node will be the highest map within the bitmap */
309 e->highbit = highbit;
310 }
311
312 if (prev) {
313 new->next = prev->next;
314 prev->next = new;
315 } else {
316 new->next = e->node;
317 e->node = new;
318 }
319
320 return 0;
321 }
322
ebitmap_destroy(ebitmap_t * e)323 void ebitmap_destroy(ebitmap_t * e)
324 {
325 ebitmap_node_t *n, *temp;
326
327 if (!e)
328 return;
329
330 n = e->node;
331 while (n) {
332 temp = n;
333 n = n->next;
334 free(temp);
335 }
336
337 e->highbit = 0;
338 e->node = 0;
339 return;
340 }
341
ebitmap_read(ebitmap_t * e,void * fp)342 int ebitmap_read(ebitmap_t * e, void *fp)
343 {
344 int rc;
345 ebitmap_node_t *n, *l;
346 uint32_t buf[3], mapsize, count, i;
347 uint64_t map;
348
349 ebitmap_init(e);
350
351 rc = next_entry(buf, fp, sizeof(uint32_t) * 3);
352 if (rc < 0)
353 goto bad;
354
355 mapsize = le32_to_cpu(buf[0]);
356 e->highbit = le32_to_cpu(buf[1]);
357 count = le32_to_cpu(buf[2]);
358
359 if (mapsize != MAPSIZE) {
360 printf
361 ("security: ebitmap: map size %d does not match my size %zu (high bit was %d)\n",
362 mapsize, MAPSIZE, e->highbit);
363 goto bad;
364 }
365 if (!e->highbit) {
366 e->node = NULL;
367 goto ok;
368 }
369 if (e->highbit & (MAPSIZE - 1)) {
370 printf
371 ("security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)\n",
372 e->highbit, MAPSIZE);
373 goto bad;
374 }
375 l = NULL;
376 for (i = 0; i < count; i++) {
377 rc = next_entry(buf, fp, sizeof(uint32_t));
378 if (rc < 0) {
379 printf("security: ebitmap: truncated map\n");
380 goto bad;
381 }
382 n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
383 if (!n) {
384 printf("security: ebitmap: out of memory\n");
385 rc = -ENOMEM;
386 goto bad;
387 }
388 memset(n, 0, sizeof(ebitmap_node_t));
389
390 n->startbit = le32_to_cpu(buf[0]);
391
392 if (n->startbit & (MAPSIZE - 1)) {
393 printf
394 ("security: ebitmap start bit (%d) is not a multiple of the map size (%zu)\n",
395 n->startbit, MAPSIZE);
396 goto bad_free;
397 }
398 if (n->startbit > (e->highbit - MAPSIZE)) {
399 printf
400 ("security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)\n",
401 n->startbit, (e->highbit - MAPSIZE));
402 goto bad_free;
403 }
404 rc = next_entry(&map, fp, sizeof(uint64_t));
405 if (rc < 0) {
406 printf("security: ebitmap: truncated map\n");
407 goto bad_free;
408 }
409 n->map = le64_to_cpu(map);
410
411 if (!n->map) {
412 printf
413 ("security: ebitmap: null map in ebitmap (startbit %d)\n",
414 n->startbit);
415 goto bad_free;
416 }
417 if (l) {
418 if (n->startbit <= l->startbit) {
419 printf
420 ("security: ebitmap: start bit %d comes after start bit %d\n",
421 n->startbit, l->startbit);
422 goto bad_free;
423 }
424 l->next = n;
425 } else
426 e->node = n;
427
428 l = n;
429 }
430
431 ok:
432 rc = 0;
433 out:
434 return rc;
435 bad_free:
436 free(n);
437 bad:
438 if (!rc)
439 rc = -EINVAL;
440 ebitmap_destroy(e);
441 goto out;
442 }
443
444 /* FLASK */
445