Joshua Brindle | 13cd4c8 | 2008-08-19 15:30:36 -0400 | [diff] [blame] | 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 | |
| 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 | |
Steve Lawrence | 2f68def | 2011-10-18 08:34:41 -0400 | [diff] [blame] | 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 | |
Joshua Brindle | 13cd4c8 | 2008-08-19 15:30:36 -0400 | [diff] [blame] | 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 | |
James Carter | 49f7ebb | 2015-06-09 10:09:15 -0400 | [diff] [blame] | 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 | |
Joshua Brindle | 13cd4c8 | 2008-08-19 15:30:36 -0400 | [diff] [blame] | 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 */ |