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 int ebitmap_cmp(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 0; 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 0; 45 46 return 1; 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 int ebitmap_get_bit(const struct ebitmap *e, u32 bit) 261 { 262 const struct ebitmap_node *n; 263 264 if (e->highbit < bit) 265 return 0; 266 267 n = e->node; 268 while (n && (n->startbit <= bit)) { 269 if ((n->startbit + EBITMAP_SIZE) > bit) 270 return ebitmap_node_get_bit(n, bit); 271 n = n->next; 272 } 273 274 return 0; 275 } 276 277 int ebitmap_set_bit(struct ebitmap *e, u32 bit, int value) 278 { 279 struct ebitmap_node *n, *prev, *new; 280 281 prev = NULL; 282 n = e->node; 283 while (n && n->startbit <= bit) { 284 if ((n->startbit + EBITMAP_SIZE) > bit) { 285 if (value) { 286 ebitmap_node_set_bit(n, bit); 287 } else { 288 u32 s; 289 290 ebitmap_node_clr_bit(n, bit); 291 292 s = find_first_bit(n->maps, EBITMAP_SIZE); 293 if (s < EBITMAP_SIZE) 294 return 0; 295 296 /* drop this node from the bitmap */ 297 if (!n->next) { 298 /* 299 * this was the highest map 300 * within the bitmap 301 */ 302 if (prev) 303 e->highbit = prev->startbit + 304 EBITMAP_SIZE; 305 else 306 e->highbit = 0; 307 } 308 if (prev) 309 prev->next = n->next; 310 else 311 e->node = n->next; 312 kmem_cache_free(ebitmap_node_cachep, n); 313 } 314 return 0; 315 } 316 prev = n; 317 n = n->next; 318 } 319 320 if (!value) 321 return 0; 322 323 new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC); 324 if (!new) 325 return -ENOMEM; 326 327 new->startbit = bit - (bit % EBITMAP_SIZE); 328 ebitmap_node_set_bit(new, bit); 329 330 if (!n) 331 /* this node will be the highest map within the bitmap */ 332 e->highbit = new->startbit + EBITMAP_SIZE; 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(struct ebitmap *e) 346 { 347 struct ebitmap_node *n, *temp; 348 349 if (!e) 350 return; 351 352 n = e->node; 353 while (n) { 354 temp = n; 355 n = n->next; 356 kmem_cache_free(ebitmap_node_cachep, temp); 357 } 358 359 e->highbit = 0; 360 e->node = NULL; 361 } 362 363 int ebitmap_read(struct ebitmap *e, void *fp) 364 { 365 struct ebitmap_node *n = NULL; 366 u32 mapunit, count, startbit, index, i; 367 __le32 ebitmap_start; 368 u64 map; 369 __le64 mapbits; 370 __le32 buf[3]; 371 int rc; 372 373 ebitmap_init(e); 374 375 rc = next_entry(buf, fp, sizeof buf); 376 if (rc < 0) 377 goto out; 378 379 mapunit = le32_to_cpu(buf[0]); 380 e->highbit = le32_to_cpu(buf[1]); 381 count = le32_to_cpu(buf[2]); 382 383 if (mapunit != BITS_PER_U64) { 384 pr_err("SELinux: ebitmap: map size %u does not " 385 "match my size %u (high bit was %u)\n", 386 mapunit, BITS_PER_U64, e->highbit); 387 goto bad; 388 } 389 390 /* round up e->highbit */ 391 e->highbit += EBITMAP_SIZE - 1; 392 e->highbit -= (e->highbit % EBITMAP_SIZE); 393 394 if (!e->highbit) { 395 e->node = NULL; 396 goto ok; 397 } 398 399 if (e->highbit && !count) 400 goto bad; 401 402 for (i = 0; i < count; i++) { 403 rc = next_entry(&ebitmap_start, fp, sizeof(u32)); 404 if (rc < 0) { 405 pr_err("SELinux: ebitmap: truncated map\n"); 406 goto bad; 407 } 408 startbit = le32_to_cpu(ebitmap_start); 409 410 if (startbit & (mapunit - 1)) { 411 pr_err("SELinux: ebitmap start bit (%u) is " 412 "not a multiple of the map unit size (%u)\n", 413 startbit, mapunit); 414 goto bad; 415 } 416 if (startbit > e->highbit - mapunit) { 417 pr_err("SELinux: ebitmap start bit (%u) is " 418 "beyond the end of the bitmap (%u)\n", 419 startbit, (e->highbit - mapunit)); 420 goto bad; 421 } 422 423 if (!n || startbit >= n->startbit + EBITMAP_SIZE) { 424 struct ebitmap_node *tmp; 425 tmp = kmem_cache_zalloc(ebitmap_node_cachep, 426 GFP_KERNEL); 427 if (!tmp) { 428 pr_err("SELinux: ebitmap: out of memory\n"); 429 rc = -ENOMEM; 430 goto bad; 431 } 432 /* round down */ 433 tmp->startbit = startbit - (startbit % EBITMAP_SIZE); 434 if (n) 435 n->next = tmp; 436 else 437 e->node = tmp; 438 n = tmp; 439 } else if (startbit <= n->startbit) { 440 pr_err("SELinux: ebitmap: start bit %u" 441 " comes after start bit %u\n", 442 startbit, n->startbit); 443 goto bad; 444 } 445 446 rc = next_entry(&mapbits, fp, sizeof(u64)); 447 if (rc < 0) { 448 pr_err("SELinux: ebitmap: truncated map\n"); 449 goto bad; 450 } 451 map = le64_to_cpu(mapbits); 452 if (!map) { 453 pr_err("SELinux: ebitmap: empty map\n"); 454 goto bad; 455 } 456 457 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; 458 while (map) { 459 n->maps[index++] = map & (-1UL); 460 map = EBITMAP_SHIFT_UNIT_SIZE(map); 461 } 462 } 463 464 if (n && n->startbit + EBITMAP_SIZE != e->highbit) { 465 pr_err("SELinux: ebitmap: high bit %u is not equal to the expected value %zu\n", 466 e->highbit, n->startbit + EBITMAP_SIZE); 467 goto bad; 468 } 469 470 ok: 471 rc = 0; 472 out: 473 return rc; 474 bad: 475 if (!rc) 476 rc = -EINVAL; 477 ebitmap_destroy(e); 478 goto out; 479 } 480 481 int ebitmap_write(const struct ebitmap *e, void *fp) 482 { 483 struct ebitmap_node *n; 484 u32 bit, count, last_bit, last_startbit; 485 __le32 buf[3]; 486 u64 map; 487 int rc; 488 489 buf[0] = cpu_to_le32(BITS_PER_U64); 490 491 count = 0; 492 last_bit = 0; 493 last_startbit = U32_MAX; 494 ebitmap_for_each_positive_bit(e, n, bit) 495 { 496 if (last_startbit == U32_MAX || 497 rounddown(bit, BITS_PER_U64) > last_startbit) { 498 count++; 499 last_startbit = rounddown(bit, BITS_PER_U64); 500 } 501 last_bit = roundup(bit + 1, BITS_PER_U64); 502 } 503 buf[1] = cpu_to_le32(last_bit); 504 buf[2] = cpu_to_le32(count); 505 506 rc = put_entry(buf, sizeof(u32), 3, fp); 507 if (rc) 508 return rc; 509 510 map = 0; 511 last_startbit = U32_MAX; 512 ebitmap_for_each_positive_bit(e, n, bit) 513 { 514 if (last_startbit == U32_MAX || 515 rounddown(bit, BITS_PER_U64) > last_startbit) { 516 __le64 buf64[1]; 517 518 /* this is the very first bit */ 519 if (!map) { 520 last_startbit = rounddown(bit, BITS_PER_U64); 521 map = (u64)1 << (bit - last_startbit); 522 continue; 523 } 524 525 /* write the last node */ 526 buf[0] = cpu_to_le32(last_startbit); 527 rc = put_entry(buf, sizeof(u32), 1, fp); 528 if (rc) 529 return rc; 530 531 buf64[0] = cpu_to_le64(map); 532 rc = put_entry(buf64, sizeof(u64), 1, fp); 533 if (rc) 534 return rc; 535 536 /* set up for the next node */ 537 map = 0; 538 last_startbit = rounddown(bit, BITS_PER_U64); 539 } 540 map |= (u64)1 << (bit - last_startbit); 541 } 542 /* write the last node */ 543 if (map) { 544 __le64 buf64[1]; 545 546 /* write the last node */ 547 buf[0] = cpu_to_le32(last_startbit); 548 rc = put_entry(buf, sizeof(u32), 1, fp); 549 if (rc) 550 return rc; 551 552 buf64[0] = cpu_to_le64(map); 553 rc = put_entry(buf64, sizeof(u64), 1, fp); 554 if (rc) 555 return rc; 556 } 557 return 0; 558 } 559 560 u32 ebitmap_hash(const struct ebitmap *e, u32 hash) 561 { 562 struct ebitmap_node *node; 563 564 /* need to change hash even if ebitmap is empty */ 565 hash = jhash_1word(e->highbit, hash); 566 for (node = e->node; node; node = node->next) { 567 hash = jhash_1word(node->startbit, hash); 568 hash = jhash(node->maps, sizeof(node->maps), hash); 569 } 570 return hash; 571 } 572 573 void __init ebitmap_cache_init(void) 574 { 575 ebitmap_node_cachep = kmem_cache_create("ebitmap_node", 576 sizeof(struct ebitmap_node), 0, 577 SLAB_PANIC, NULL); 578 } 579