1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * Implementation of the extensible bitmap type. 4 * 5 * Author : Stephen Smalley, <stephen.smalley.work@gmail.com> 6 */ 7 /* 8 * Updated: Hewlett-Packard <paul@paul-moore.com> 9 * Added support to import/export the NetLabel category bitmap 10 * (c) Copyright Hewlett-Packard Development Company, L.P., 2006 11 * 12 * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com> 13 * Applied standard bit operations to improve bitmap scanning. 14 */ 15 16 #include <linux/kernel.h> 17 #include <linux/slab.h> 18 #include <linux/errno.h> 19 #include <linux/jhash.h> 20 #include <net/netlabel.h> 21 #include "ebitmap.h" 22 #include "policydb.h" 23 24 #define BITS_PER_U64 ((u32)(sizeof(u64) * 8)) 25 26 static struct kmem_cache *ebitmap_node_cachep __ro_after_init; 27 28 bool ebitmap_equal(const struct ebitmap *e1, const struct ebitmap *e2) 29 { 30 const struct ebitmap_node *n1, *n2; 31 32 if (e1->highbit != e2->highbit) 33 return false; 34 35 n1 = e1->node; 36 n2 = e2->node; 37 while (n1 && n2 && (n1->startbit == n2->startbit) && 38 !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) { 39 n1 = n1->next; 40 n2 = n2->next; 41 } 42 43 if (n1 || n2) 44 return false; 45 46 return true; 47 } 48 49 int ebitmap_cpy(struct ebitmap *dst, const struct ebitmap *src) 50 { 51 struct ebitmap_node *new, *prev; 52 const struct ebitmap_node *n; 53 54 ebitmap_init(dst); 55 n = src->node; 56 prev = NULL; 57 while (n) { 58 new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC); 59 if (!new) { 60 ebitmap_destroy(dst); 61 return -ENOMEM; 62 } 63 new->startbit = n->startbit; 64 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8); 65 new->next = NULL; 66 if (prev) 67 prev->next = new; 68 else 69 dst->node = new; 70 prev = new; 71 n = n->next; 72 } 73 74 dst->highbit = src->highbit; 75 return 0; 76 } 77 78 int ebitmap_and(struct ebitmap *dst, const struct ebitmap *e1, 79 const struct ebitmap *e2) 80 { 81 struct ebitmap_node *n; 82 u32 bit; 83 int rc; 84 85 ebitmap_init(dst); 86 87 ebitmap_for_each_positive_bit(e1, n, bit) 88 { 89 if (ebitmap_get_bit(e2, bit)) { 90 rc = ebitmap_set_bit(dst, bit, 1); 91 if (rc < 0) 92 return rc; 93 } 94 } 95 return 0; 96 } 97 98 #ifdef CONFIG_NETLABEL 99 /** 100 * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap 101 * @ebmap: the ebitmap to export 102 * @catmap: the NetLabel category bitmap 103 * 104 * Description: 105 * Export a SELinux extensibile bitmap into a NetLabel category bitmap. 106 * Returns zero on success, negative values on error. 107 * 108 */ 109 int ebitmap_netlbl_export(struct ebitmap *ebmap, 110 struct netlbl_lsm_catmap **catmap) 111 { 112 struct ebitmap_node *e_iter = ebmap->node; 113 unsigned long e_map; 114 u32 offset; 115 unsigned int iter; 116 int rc; 117 118 if (e_iter == NULL) { 119 *catmap = NULL; 120 return 0; 121 } 122 123 if (*catmap != NULL) 124 netlbl_catmap_free(*catmap); 125 *catmap = NULL; 126 127 while (e_iter) { 128 offset = e_iter->startbit; 129 for (iter = 0; iter < EBITMAP_UNIT_NUMS; iter++) { 130 e_map = e_iter->maps[iter]; 131 if (e_map != 0) { 132 rc = netlbl_catmap_setlong(catmap, offset, 133 e_map, GFP_ATOMIC); 134 if (rc != 0) 135 goto netlbl_export_failure; 136 } 137 offset += EBITMAP_UNIT_SIZE; 138 } 139 e_iter = e_iter->next; 140 } 141 142 return 0; 143 144 netlbl_export_failure: 145 netlbl_catmap_free(*catmap); 146 return -ENOMEM; 147 } 148 149 /** 150 * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap 151 * @ebmap: the ebitmap to import 152 * @catmap: the NetLabel category bitmap 153 * 154 * Description: 155 * Import a NetLabel category bitmap into a SELinux extensibile bitmap. 156 * Returns zero on success, negative values on error. 157 * 158 */ 159 int ebitmap_netlbl_import(struct ebitmap *ebmap, 160 struct netlbl_lsm_catmap *catmap) 161 { 162 int rc; 163 struct ebitmap_node *e_iter = NULL; 164 struct ebitmap_node *e_prev = NULL; 165 u32 offset = 0, idx; 166 unsigned long bitmap; 167 168 for (;;) { 169 rc = netlbl_catmap_getlong(catmap, &offset, &bitmap); 170 if (rc < 0) 171 goto netlbl_import_failure; 172 if (offset == (u32)-1) 173 return 0; 174 175 /* don't waste ebitmap space if the netlabel bitmap is empty */ 176 if (bitmap == 0) { 177 offset += EBITMAP_UNIT_SIZE; 178 continue; 179 } 180 181 if (e_iter == NULL || 182 offset >= e_iter->startbit + EBITMAP_SIZE) { 183 e_prev = e_iter; 184 e_iter = kmem_cache_zalloc(ebitmap_node_cachep, 185 GFP_ATOMIC); 186 if (e_iter == NULL) 187 goto netlbl_import_failure; 188 e_iter->startbit = offset - (offset % EBITMAP_SIZE); 189 if (e_prev == NULL) 190 ebmap->node = e_iter; 191 else 192 e_prev->next = e_iter; 193 ebmap->highbit = e_iter->startbit + EBITMAP_SIZE; 194 } 195 196 /* offset will always be aligned to an unsigned long */ 197 idx = EBITMAP_NODE_INDEX(e_iter, offset); 198 e_iter->maps[idx] = bitmap; 199 200 /* next */ 201 offset += EBITMAP_UNIT_SIZE; 202 } 203 204 /* NOTE: we should never reach this return */ 205 return 0; 206 207 netlbl_import_failure: 208 ebitmap_destroy(ebmap); 209 return -ENOMEM; 210 } 211 #endif /* CONFIG_NETLABEL */ 212 213 /* 214 * Check to see if all the bits set in e2 are also set in e1. Optionally, 215 * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed 216 * last_e2bit. 217 */ 218 int ebitmap_contains(const struct ebitmap *e1, const struct ebitmap *e2, 219 u32 last_e2bit) 220 { 221 const struct ebitmap_node *n1, *n2; 222 int i; 223 224 if (e1->highbit < e2->highbit) 225 return 0; 226 227 n1 = e1->node; 228 n2 = e2->node; 229 230 while (n1 && n2 && (n1->startbit <= n2->startbit)) { 231 if (n1->startbit < n2->startbit) { 232 n1 = n1->next; 233 continue; 234 } 235 for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i];) 236 i--; /* Skip trailing NULL map entries */ 237 if (last_e2bit && (i >= 0)) { 238 u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE + 239 __fls(n2->maps[i]); 240 if (lastsetbit > last_e2bit) 241 return 0; 242 } 243 244 while (i >= 0) { 245 if ((n1->maps[i] & n2->maps[i]) != n2->maps[i]) 246 return 0; 247 i--; 248 } 249 250 n1 = n1->next; 251 n2 = n2->next; 252 } 253 254 if (n2) 255 return 0; 256 257 return 1; 258 } 259 260 u32 ebitmap_get_highest_set_bit(const struct ebitmap *e) 261 { 262 const struct ebitmap_node *n; 263 unsigned long unit; 264 u32 pos = 0; 265 266 n = e->node; 267 if (!n) 268 return 0; 269 270 while (n->next) 271 n = n->next; 272 273 for (unsigned int i = EBITMAP_UNIT_NUMS; i > 0; i--) { 274 unit = n->maps[i - 1]; 275 if (unit == 0) 276 continue; 277 278 pos = (i - 1) * EBITMAP_UNIT_SIZE; 279 while (unit >>= 1) 280 pos++; 281 break; 282 } 283 284 return n->startbit + pos; 285 } 286 287 int ebitmap_get_bit(const struct ebitmap *e, u32 bit) 288 { 289 const struct ebitmap_node *n; 290 291 if (e->highbit < bit) 292 return 0; 293 294 n = e->node; 295 while (n && (n->startbit <= bit)) { 296 if ((n->startbit + EBITMAP_SIZE) > bit) 297 return ebitmap_node_get_bit(n, bit); 298 n = n->next; 299 } 300 301 return 0; 302 } 303 304 int ebitmap_set_bit(struct ebitmap *e, u32 bit, int value) 305 { 306 struct ebitmap_node *n, *prev, *new; 307 308 prev = NULL; 309 n = e->node; 310 while (n && n->startbit <= bit) { 311 if ((n->startbit + EBITMAP_SIZE) > bit) { 312 if (value) { 313 ebitmap_node_set_bit(n, bit); 314 } else { 315 u32 s; 316 317 ebitmap_node_clr_bit(n, bit); 318 319 s = find_first_bit(n->maps, EBITMAP_SIZE); 320 if (s < EBITMAP_SIZE) 321 return 0; 322 323 /* drop this node from the bitmap */ 324 if (!n->next) { 325 /* 326 * this was the highest map 327 * within the bitmap 328 */ 329 if (prev) 330 e->highbit = prev->startbit + 331 EBITMAP_SIZE; 332 else 333 e->highbit = 0; 334 } 335 if (prev) 336 prev->next = n->next; 337 else 338 e->node = n->next; 339 kmem_cache_free(ebitmap_node_cachep, n); 340 } 341 return 0; 342 } 343 prev = n; 344 n = n->next; 345 } 346 347 if (!value) 348 return 0; 349 350 new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC); 351 if (!new) 352 return -ENOMEM; 353 354 new->startbit = bit - (bit % EBITMAP_SIZE); 355 ebitmap_node_set_bit(new, bit); 356 357 if (!n) 358 /* this node will be the highest map within the bitmap */ 359 e->highbit = new->startbit + EBITMAP_SIZE; 360 361 if (prev) { 362 new->next = prev->next; 363 prev->next = new; 364 } else { 365 new->next = e->node; 366 e->node = new; 367 } 368 369 return 0; 370 } 371 372 void ebitmap_destroy(struct ebitmap *e) 373 { 374 struct ebitmap_node *n, *temp; 375 376 if (!e) 377 return; 378 379 n = e->node; 380 while (n) { 381 temp = n; 382 n = n->next; 383 kmem_cache_free(ebitmap_node_cachep, temp); 384 } 385 386 e->highbit = 0; 387 e->node = NULL; 388 } 389 390 int ebitmap_read(struct ebitmap *e, struct policy_file *fp) 391 { 392 struct ebitmap_node *n = NULL; 393 u32 mapunit, count, startbit, index, i; 394 __le32 ebitmap_start; 395 u64 map; 396 __le64 mapbits; 397 __le32 buf[3]; 398 int rc; 399 400 ebitmap_init(e); 401 402 rc = next_entry(buf, fp, sizeof buf); 403 if (rc < 0) 404 goto out; 405 406 mapunit = le32_to_cpu(buf[0]); 407 e->highbit = le32_to_cpu(buf[1]); 408 count = le32_to_cpu(buf[2]); 409 410 if (mapunit != BITS_PER_U64) { 411 pr_err("SELinux: ebitmap: map size %u does not " 412 "match my size %u (high bit was %u)\n", 413 mapunit, BITS_PER_U64, e->highbit); 414 goto bad; 415 } 416 417 /* round up e->highbit */ 418 e->highbit += EBITMAP_SIZE - 1; 419 e->highbit -= (e->highbit % EBITMAP_SIZE); 420 421 if (!e->highbit) { 422 e->node = NULL; 423 goto ok; 424 } 425 426 if (e->highbit && !count) 427 goto bad; 428 429 for (i = 0; i < count; i++) { 430 rc = next_entry(&ebitmap_start, fp, sizeof(u32)); 431 if (rc < 0) { 432 pr_err("SELinux: ebitmap: truncated map\n"); 433 goto bad; 434 } 435 startbit = le32_to_cpu(ebitmap_start); 436 437 if (startbit & (mapunit - 1)) { 438 pr_err("SELinux: ebitmap start bit (%u) is " 439 "not a multiple of the map unit size (%u)\n", 440 startbit, mapunit); 441 goto bad; 442 } 443 if (startbit > e->highbit - mapunit) { 444 pr_err("SELinux: ebitmap start bit (%u) is " 445 "beyond the end of the bitmap (%u)\n", 446 startbit, (e->highbit - mapunit)); 447 goto bad; 448 } 449 450 if (!n || startbit >= n->startbit + EBITMAP_SIZE) { 451 struct ebitmap_node *tmp; 452 tmp = kmem_cache_zalloc(ebitmap_node_cachep, 453 GFP_KERNEL); 454 if (!tmp) { 455 pr_err("SELinux: ebitmap: out of memory\n"); 456 rc = -ENOMEM; 457 goto bad; 458 } 459 /* round down */ 460 tmp->startbit = startbit - (startbit % EBITMAP_SIZE); 461 if (n) 462 n->next = tmp; 463 else 464 e->node = tmp; 465 n = tmp; 466 } else if (startbit <= n->startbit) { 467 pr_err("SELinux: ebitmap: start bit %u" 468 " comes after start bit %u\n", 469 startbit, n->startbit); 470 goto bad; 471 } 472 473 rc = next_entry(&mapbits, fp, sizeof(u64)); 474 if (rc < 0) { 475 pr_err("SELinux: ebitmap: truncated map\n"); 476 goto bad; 477 } 478 map = le64_to_cpu(mapbits); 479 if (!map) { 480 pr_err("SELinux: ebitmap: empty map\n"); 481 goto bad; 482 } 483 484 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; 485 while (map) { 486 n->maps[index++] = map & (-1UL); 487 map = EBITMAP_SHIFT_UNIT_SIZE(map); 488 } 489 } 490 491 if (n && n->startbit + EBITMAP_SIZE != e->highbit) { 492 pr_err("SELinux: ebitmap: high bit %u is not equal to the expected value %zu\n", 493 e->highbit, n->startbit + EBITMAP_SIZE); 494 goto bad; 495 } 496 497 ok: 498 rc = 0; 499 out: 500 return rc; 501 bad: 502 if (!rc) 503 rc = -EINVAL; 504 ebitmap_destroy(e); 505 goto out; 506 } 507 508 int ebitmap_write(const struct ebitmap *e, struct policy_file *fp) 509 { 510 struct ebitmap_node *n; 511 u32 bit, count, last_bit, last_startbit; 512 __le32 buf[3]; 513 u64 map; 514 int rc; 515 516 buf[0] = cpu_to_le32(BITS_PER_U64); 517 518 count = 0; 519 last_bit = 0; 520 last_startbit = U32_MAX; 521 ebitmap_for_each_positive_bit(e, n, bit) 522 { 523 if (last_startbit == U32_MAX || 524 rounddown(bit, BITS_PER_U64) > last_startbit) { 525 count++; 526 last_startbit = rounddown(bit, BITS_PER_U64); 527 } 528 last_bit = roundup(bit + 1, BITS_PER_U64); 529 } 530 buf[1] = cpu_to_le32(last_bit); 531 buf[2] = cpu_to_le32(count); 532 533 rc = put_entry(buf, sizeof(u32), 3, fp); 534 if (rc) 535 return rc; 536 537 map = 0; 538 last_startbit = U32_MAX; 539 ebitmap_for_each_positive_bit(e, n, bit) 540 { 541 if (last_startbit == U32_MAX || 542 rounddown(bit, BITS_PER_U64) > last_startbit) { 543 __le64 buf64[1]; 544 545 /* this is the very first bit */ 546 if (!map) { 547 last_startbit = rounddown(bit, BITS_PER_U64); 548 map = (u64)1 << (bit - last_startbit); 549 continue; 550 } 551 552 /* write the last node */ 553 buf[0] = cpu_to_le32(last_startbit); 554 rc = put_entry(buf, sizeof(u32), 1, fp); 555 if (rc) 556 return rc; 557 558 buf64[0] = cpu_to_le64(map); 559 rc = put_entry(buf64, sizeof(u64), 1, fp); 560 if (rc) 561 return rc; 562 563 /* set up for the next node */ 564 map = 0; 565 last_startbit = rounddown(bit, BITS_PER_U64); 566 } 567 map |= (u64)1 << (bit - last_startbit); 568 } 569 /* write the last node */ 570 if (map) { 571 __le64 buf64[1]; 572 573 /* write the last node */ 574 buf[0] = cpu_to_le32(last_startbit); 575 rc = put_entry(buf, sizeof(u32), 1, fp); 576 if (rc) 577 return rc; 578 579 buf64[0] = cpu_to_le64(map); 580 rc = put_entry(buf64, sizeof(u64), 1, fp); 581 if (rc) 582 return rc; 583 } 584 return 0; 585 } 586 587 u32 ebitmap_hash(const struct ebitmap *e, u32 hash) 588 { 589 struct ebitmap_node *node; 590 591 /* need to change hash even if ebitmap is empty */ 592 hash = jhash_1word(e->highbit, hash); 593 for (node = e->node; node; node = node->next) { 594 hash = jhash_1word(node->startbit, hash); 595 hash = jhash(node->maps, sizeof(node->maps), hash); 596 } 597 return hash; 598 } 599 600 void __init ebitmap_cache_init(void) 601 { 602 ebitmap_node_cachep = KMEM_CACHE(ebitmap_node, SLAB_PANIC); 603 } 604