Home | History | Annotate | Download | only in src
      1 
      2 /* Author : Stephen Smalley, <sds (at) 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 
     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 
     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 
     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 
     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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 	l = NULL;
    398 	for (i = 0; i < count; i++) {
    399 		rc = next_entry(buf, fp, sizeof(uint32_t));
    400 		if (rc < 0) {
    401 			printf("security: ebitmap: truncated map\n");
    402 			goto bad;
    403 		}
    404 		n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
    405 		if (!n) {
    406 			printf("security: ebitmap: out of memory\n");
    407 			rc = -ENOMEM;
    408 			goto bad;
    409 		}
    410 		memset(n, 0, sizeof(ebitmap_node_t));
    411 
    412 		n->startbit = le32_to_cpu(buf[0]);
    413 
    414 		if (n->startbit & (MAPSIZE - 1)) {
    415 			printf
    416 			    ("security: ebitmap start bit (%d) is not a multiple of the map size (%zu)\n",
    417 			     n->startbit, MAPSIZE);
    418 			goto bad_free;
    419 		}
    420 		if (n->startbit > (e->highbit - MAPSIZE)) {
    421 			printf
    422 			    ("security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)\n",
    423 			     n->startbit, (e->highbit - MAPSIZE));
    424 			goto bad_free;
    425 		}
    426 		rc = next_entry(&map, fp, sizeof(uint64_t));
    427 		if (rc < 0) {
    428 			printf("security: ebitmap: truncated map\n");
    429 			goto bad_free;
    430 		}
    431 		n->map = le64_to_cpu(map);
    432 
    433 		if (!n->map) {
    434 			printf
    435 			    ("security: ebitmap: null map in ebitmap (startbit %d)\n",
    436 			     n->startbit);
    437 			goto bad_free;
    438 		}
    439 		if (l) {
    440 			if (n->startbit <= l->startbit) {
    441 				printf
    442 				    ("security: ebitmap: start bit %d comes after start bit %d\n",
    443 				     n->startbit, l->startbit);
    444 				goto bad_free;
    445 			}
    446 			l->next = n;
    447 		} else
    448 			e->node = n;
    449 
    450 		l = n;
    451 	}
    452 
    453       ok:
    454 	rc = 0;
    455       out:
    456 	return rc;
    457       bad_free:
    458 	free(n);
    459       bad:
    460 	if (!rc)
    461 		rc = -EINVAL;
    462 	ebitmap_destroy(e);
    463 	goto out;
    464 }
    465 
    466 /* FLASK */
    467