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 <net/netlabel.h> 23 #include "ebitmap.h" 24 #include "policydb.h" 25 26 #define BITS_PER_U64 (sizeof(u64) * 8) 27 28 static struct kmem_cache *ebitmap_node_cachep; 29 30 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2) 31 { 32 struct ebitmap_node *n1, *n2; 33 34 if (e1->highbit != e2->highbit) 35 return 0; 36 37 n1 = e1->node; 38 n2 = e2->node; 39 while (n1 && n2 && 40 (n1->startbit == n2->startbit) && 41 !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) { 42 n1 = n1->next; 43 n2 = n2->next; 44 } 45 46 if (n1 || n2) 47 return 0; 48 49 return 1; 50 } 51 52 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src) 53 { 54 struct ebitmap_node *n, *new, *prev; 55 56 ebitmap_init(dst); 57 n = src->node; 58 prev = NULL; 59 while (n) { 60 new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC); 61 if (!new) { 62 ebitmap_destroy(dst); 63 return -ENOMEM; 64 } 65 new->startbit = n->startbit; 66 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8); 67 new->next = NULL; 68 if (prev) 69 prev->next = new; 70 else 71 dst->node = new; 72 prev = new; 73 n = n->next; 74 } 75 76 dst->highbit = src->highbit; 77 return 0; 78 } 79 80 int ebitmap_and(struct ebitmap *dst, struct ebitmap *e1, struct ebitmap *e2) 81 { 82 struct ebitmap_node *n; 83 int bit, rc; 84 85 ebitmap_init(dst); 86 87 ebitmap_for_each_positive_bit(e1, n, bit) { 88 if (ebitmap_get_bit(e2, bit)) { 89 rc = ebitmap_set_bit(dst, bit, 1); 90 if (rc < 0) 91 return rc; 92 } 93 } 94 return 0; 95 } 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, 133 offset, 134 e_map, 135 GFP_ATOMIC); 136 if (rc != 0) 137 goto netlbl_export_failure; 138 } 139 offset += EBITMAP_UNIT_SIZE; 140 } 141 e_iter = e_iter->next; 142 } 143 144 return 0; 145 146 netlbl_export_failure: 147 netlbl_catmap_free(*catmap); 148 return -ENOMEM; 149 } 150 151 /** 152 * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap 153 * @ebmap: the ebitmap to import 154 * @catmap: the NetLabel category bitmap 155 * 156 * Description: 157 * Import a NetLabel category bitmap into a SELinux extensibile bitmap. 158 * Returns zero on success, negative values on error. 159 * 160 */ 161 int ebitmap_netlbl_import(struct ebitmap *ebmap, 162 struct netlbl_lsm_catmap *catmap) 163 { 164 int rc; 165 struct ebitmap_node *e_iter = NULL; 166 struct ebitmap_node *e_prev = NULL; 167 u32 offset = 0, idx; 168 unsigned long bitmap; 169 170 for (;;) { 171 rc = netlbl_catmap_getlong(catmap, &offset, &bitmap); 172 if (rc < 0) 173 goto netlbl_import_failure; 174 if (offset == (u32)-1) 175 return 0; 176 177 /* don't waste ebitmap space if the netlabel bitmap is empty */ 178 if (bitmap == 0) { 179 offset += EBITMAP_UNIT_SIZE; 180 continue; 181 } 182 183 if (e_iter == NULL || 184 offset >= e_iter->startbit + EBITMAP_SIZE) { 185 e_prev = e_iter; 186 e_iter = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC); 187 if (e_iter == NULL) 188 goto netlbl_import_failure; 189 e_iter->startbit = offset - (offset % EBITMAP_SIZE); 190 if (e_prev == NULL) 191 ebmap->node = e_iter; 192 else 193 e_prev->next = e_iter; 194 ebmap->highbit = e_iter->startbit + EBITMAP_SIZE; 195 } 196 197 /* offset will always be aligned to an unsigned long */ 198 idx = EBITMAP_NODE_INDEX(e_iter, offset); 199 e_iter->maps[idx] = bitmap; 200 201 /* next */ 202 offset += EBITMAP_UNIT_SIZE; 203 } 204 205 /* NOTE: we should never reach this return */ 206 return 0; 207 208 netlbl_import_failure: 209 ebitmap_destroy(ebmap); 210 return -ENOMEM; 211 } 212 #endif /* CONFIG_NETLABEL */ 213 214 /* 215 * Check to see if all the bits set in e2 are also set in e1. Optionally, 216 * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed 217 * last_e2bit. 218 */ 219 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit) 220 { 221 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(struct ebitmap *e, unsigned long bit) 261 { 262 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, unsigned long 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 unsigned int 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 return; 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 void __init ebitmap_cache_init(void) 546 { 547 ebitmap_node_cachep = kmem_cache_create("ebitmap_node", 548 sizeof(struct ebitmap_node), 549 0, SLAB_PANIC, NULL); 550 } 551