1 2 /* Author : Stephen Smalley, <sds (at) 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 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 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
