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 } 363 364 int ebitmap_read(struct ebitmap *e, void *fp) 365 { 366 struct ebitmap_node *n = NULL; 367 u32 mapunit, count, startbit, index; 368 __le32 ebitmap_start; 369 u64 map; 370 __le64 mapbits; 371 __le32 buf[3]; 372 int rc, i; 373 374 ebitmap_init(e); 375 376 rc = next_entry(buf, fp, sizeof buf); 377 if (rc < 0) 378 goto out; 379 380 mapunit = le32_to_cpu(buf[0]); 381 e->highbit = le32_to_cpu(buf[1]); 382 count = le32_to_cpu(buf[2]); 383 384 if (mapunit != BITS_PER_U64) { 385 pr_err("SELinux: ebitmap: map size %u does not " 386 "match my size %zd (high bit was %d)\n", 387 mapunit, BITS_PER_U64, e->highbit); 388 goto bad; 389 } 390 391 /* round up e->highbit */ 392 e->highbit += EBITMAP_SIZE - 1; 393 e->highbit -= (e->highbit % EBITMAP_SIZE); 394 395 if (!e->highbit) { 396 e->node = NULL; 397 goto ok; 398 } 399 400 if (e->highbit && !count) 401 goto bad; 402 403 for (i = 0; i < count; i++) { 404 rc = next_entry(&ebitmap_start, fp, sizeof(u32)); 405 if (rc < 0) { 406 pr_err("SELinux: ebitmap: truncated map\n"); 407 goto bad; 408 } 409 startbit = le32_to_cpu(ebitmap_start); 410 411 if (startbit & (mapunit - 1)) { 412 pr_err("SELinux: ebitmap start bit (%d) is " 413 "not a multiple of the map unit size (%u)\n", 414 startbit, mapunit); 415 goto bad; 416 } 417 if (startbit > e->highbit - mapunit) { 418 pr_err("SELinux: ebitmap start bit (%d) is " 419 "beyond the end of the bitmap (%u)\n", 420 startbit, (e->highbit - mapunit)); 421 goto bad; 422 } 423 424 if (!n || startbit >= n->startbit + EBITMAP_SIZE) { 425 struct ebitmap_node *tmp; 426 tmp = kmem_cache_zalloc(ebitmap_node_cachep, 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 %d" 441 " comes after start bit %d\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 453 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; 454 while (map) { 455 n->maps[index++] = map & (-1UL); 456 map = EBITMAP_SHIFT_UNIT_SIZE(map); 457 } 458 } 459 ok: 460 rc = 0; 461 out: 462 return rc; 463 bad: 464 if (!rc) 465 rc = -EINVAL; 466 ebitmap_destroy(e); 467 goto out; 468 } 469 470 int ebitmap_write(struct ebitmap *e, void *fp) 471 { 472 struct ebitmap_node *n; 473 u32 count; 474 __le32 buf[3]; 475 u64 map; 476 int bit, last_bit, last_startbit, rc; 477 478 buf[0] = cpu_to_le32(BITS_PER_U64); 479 480 count = 0; 481 last_bit = 0; 482 last_startbit = -1; 483 ebitmap_for_each_positive_bit(e, n, bit) { 484 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { 485 count++; 486 last_startbit = rounddown(bit, BITS_PER_U64); 487 } 488 last_bit = roundup(bit + 1, BITS_PER_U64); 489 } 490 buf[1] = cpu_to_le32(last_bit); 491 buf[2] = cpu_to_le32(count); 492 493 rc = put_entry(buf, sizeof(u32), 3, fp); 494 if (rc) 495 return rc; 496 497 map = 0; 498 last_startbit = INT_MIN; 499 ebitmap_for_each_positive_bit(e, n, bit) { 500 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { 501 __le64 buf64[1]; 502 503 /* this is the very first bit */ 504 if (!map) { 505 last_startbit = rounddown(bit, BITS_PER_U64); 506 map = (u64)1 << (bit - last_startbit); 507 continue; 508 } 509 510 /* write the last node */ 511 buf[0] = cpu_to_le32(last_startbit); 512 rc = put_entry(buf, sizeof(u32), 1, fp); 513 if (rc) 514 return rc; 515 516 buf64[0] = cpu_to_le64(map); 517 rc = put_entry(buf64, sizeof(u64), 1, fp); 518 if (rc) 519 return rc; 520 521 /* set up for the next node */ 522 map = 0; 523 last_startbit = rounddown(bit, BITS_PER_U64); 524 } 525 map |= (u64)1 << (bit - last_startbit); 526 } 527 /* write the last node */ 528 if (map) { 529 __le64 buf64[1]; 530 531 /* write the last node */ 532 buf[0] = cpu_to_le32(last_startbit); 533 rc = put_entry(buf, sizeof(u32), 1, fp); 534 if (rc) 535 return rc; 536 537 buf64[0] = cpu_to_le64(map); 538 rc = put_entry(buf64, sizeof(u64), 1, fp); 539 if (rc) 540 return rc; 541 } 542 return 0; 543 } 544 545 u32 ebitmap_hash(const struct ebitmap *e, u32 hash) 546 { 547 struct ebitmap_node *node; 548 549 /* need to change hash even if ebitmap is empty */ 550 hash = jhash_1word(e->highbit, hash); 551 for (node = e->node; node; node = node->next) { 552 hash = jhash_1word(node->startbit, hash); 553 hash = jhash(node->maps, sizeof(node->maps), hash); 554 } 555 return hash; 556 } 557 558 void __init ebitmap_cache_init(void) 559 { 560 ebitmap_node_cachep = kmem_cache_create("ebitmap_node", 561 sizeof(struct ebitmap_node), 562 0, SLAB_PANIC, NULL); 563 } 564