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_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 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 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 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
