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