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 #ifdef CONFIG_NETLABEL 81 /** 82 * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap 83 * @ebmap: the ebitmap to export 84 * @catmap: the NetLabel category bitmap 85 * 86 * Description: 87 * Export a SELinux extensibile bitmap into a NetLabel category bitmap. 88 * Returns zero on success, negative values on error. 89 * 90 */ 91 int ebitmap_netlbl_export(struct ebitmap *ebmap, 92 struct netlbl_lsm_catmap **catmap) 93 { 94 struct ebitmap_node *e_iter = ebmap->node; 95 unsigned long e_map; 96 u32 offset; 97 unsigned int iter; 98 int rc; 99 100 if (e_iter == NULL) { 101 *catmap = NULL; 102 return 0; 103 } 104 105 if (*catmap != NULL) 106 netlbl_catmap_free(*catmap); 107 *catmap = NULL; 108 109 while (e_iter) { 110 offset = e_iter->startbit; 111 for (iter = 0; iter < EBITMAP_UNIT_NUMS; iter++) { 112 e_map = e_iter->maps[iter]; 113 if (e_map != 0) { 114 rc = netlbl_catmap_setlong(catmap, 115 offset, 116 e_map, 117 GFP_ATOMIC); 118 if (rc != 0) 119 goto netlbl_export_failure; 120 } 121 offset += EBITMAP_UNIT_SIZE; 122 } 123 e_iter = e_iter->next; 124 } 125 126 return 0; 127 128 netlbl_export_failure: 129 netlbl_catmap_free(*catmap); 130 return -ENOMEM; 131 } 132 133 /** 134 * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap 135 * @ebmap: the ebitmap to import 136 * @catmap: the NetLabel category bitmap 137 * 138 * Description: 139 * Import a NetLabel category bitmap into a SELinux extensibile bitmap. 140 * Returns zero on success, negative values on error. 141 * 142 */ 143 int ebitmap_netlbl_import(struct ebitmap *ebmap, 144 struct netlbl_lsm_catmap *catmap) 145 { 146 int rc; 147 struct ebitmap_node *e_iter = NULL; 148 struct ebitmap_node *e_prev = NULL; 149 u32 offset = 0, idx; 150 unsigned long bitmap; 151 152 for (;;) { 153 rc = netlbl_catmap_getlong(catmap, &offset, &bitmap); 154 if (rc < 0) 155 goto netlbl_import_failure; 156 if (offset == (u32)-1) 157 return 0; 158 159 /* don't waste ebitmap space if the netlabel bitmap is empty */ 160 if (bitmap == 0) { 161 offset += EBITMAP_UNIT_SIZE; 162 continue; 163 } 164 165 if (e_iter == NULL || 166 offset >= e_iter->startbit + EBITMAP_SIZE) { 167 e_prev = e_iter; 168 e_iter = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC); 169 if (e_iter == NULL) 170 goto netlbl_import_failure; 171 e_iter->startbit = offset - (offset % EBITMAP_SIZE); 172 if (e_prev == NULL) 173 ebmap->node = e_iter; 174 else 175 e_prev->next = e_iter; 176 ebmap->highbit = e_iter->startbit + EBITMAP_SIZE; 177 } 178 179 /* offset will always be aligned to an unsigned long */ 180 idx = EBITMAP_NODE_INDEX(e_iter, offset); 181 e_iter->maps[idx] = bitmap; 182 183 /* next */ 184 offset += EBITMAP_UNIT_SIZE; 185 } 186 187 /* NOTE: we should never reach this return */ 188 return 0; 189 190 netlbl_import_failure: 191 ebitmap_destroy(ebmap); 192 return -ENOMEM; 193 } 194 #endif /* CONFIG_NETLABEL */ 195 196 /* 197 * Check to see if all the bits set in e2 are also set in e1. Optionally, 198 * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed 199 * last_e2bit. 200 */ 201 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit) 202 { 203 struct ebitmap_node *n1, *n2; 204 int i; 205 206 if (e1->highbit < e2->highbit) 207 return 0; 208 209 n1 = e1->node; 210 n2 = e2->node; 211 212 while (n1 && n2 && (n1->startbit <= n2->startbit)) { 213 if (n1->startbit < n2->startbit) { 214 n1 = n1->next; 215 continue; 216 } 217 for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; ) 218 i--; /* Skip trailing NULL map entries */ 219 if (last_e2bit && (i >= 0)) { 220 u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE + 221 __fls(n2->maps[i]); 222 if (lastsetbit > last_e2bit) 223 return 0; 224 } 225 226 while (i >= 0) { 227 if ((n1->maps[i] & n2->maps[i]) != n2->maps[i]) 228 return 0; 229 i--; 230 } 231 232 n1 = n1->next; 233 n2 = n2->next; 234 } 235 236 if (n2) 237 return 0; 238 239 return 1; 240 } 241 242 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit) 243 { 244 struct ebitmap_node *n; 245 246 if (e->highbit < bit) 247 return 0; 248 249 n = e->node; 250 while (n && (n->startbit <= bit)) { 251 if ((n->startbit + EBITMAP_SIZE) > bit) 252 return ebitmap_node_get_bit(n, bit); 253 n = n->next; 254 } 255 256 return 0; 257 } 258 259 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) 260 { 261 struct ebitmap_node *n, *prev, *new; 262 263 prev = NULL; 264 n = e->node; 265 while (n && n->startbit <= bit) { 266 if ((n->startbit + EBITMAP_SIZE) > bit) { 267 if (value) { 268 ebitmap_node_set_bit(n, bit); 269 } else { 270 unsigned int s; 271 272 ebitmap_node_clr_bit(n, bit); 273 274 s = find_first_bit(n->maps, EBITMAP_SIZE); 275 if (s < EBITMAP_SIZE) 276 return 0; 277 278 /* drop this node from the bitmap */ 279 if (!n->next) { 280 /* 281 * this was the highest map 282 * within the bitmap 283 */ 284 if (prev) 285 e->highbit = prev->startbit 286 + EBITMAP_SIZE; 287 else 288 e->highbit = 0; 289 } 290 if (prev) 291 prev->next = n->next; 292 else 293 e->node = n->next; 294 kmem_cache_free(ebitmap_node_cachep, n); 295 } 296 return 0; 297 } 298 prev = n; 299 n = n->next; 300 } 301 302 if (!value) 303 return 0; 304 305 new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC); 306 if (!new) 307 return -ENOMEM; 308 309 new->startbit = bit - (bit % EBITMAP_SIZE); 310 ebitmap_node_set_bit(new, bit); 311 312 if (!n) 313 /* this node will be the highest map within the bitmap */ 314 e->highbit = new->startbit + EBITMAP_SIZE; 315 316 if (prev) { 317 new->next = prev->next; 318 prev->next = new; 319 } else { 320 new->next = e->node; 321 e->node = new; 322 } 323 324 return 0; 325 } 326 327 void ebitmap_destroy(struct ebitmap *e) 328 { 329 struct ebitmap_node *n, *temp; 330 331 if (!e) 332 return; 333 334 n = e->node; 335 while (n) { 336 temp = n; 337 n = n->next; 338 kmem_cache_free(ebitmap_node_cachep, temp); 339 } 340 341 e->highbit = 0; 342 e->node = NULL; 343 return; 344 } 345 346 int ebitmap_read(struct ebitmap *e, void *fp) 347 { 348 struct ebitmap_node *n = NULL; 349 u32 mapunit, count, startbit, index; 350 __le32 ebitmap_start; 351 u64 map; 352 __le64 mapbits; 353 __le32 buf[3]; 354 int rc, i; 355 356 ebitmap_init(e); 357 358 rc = next_entry(buf, fp, sizeof buf); 359 if (rc < 0) 360 goto out; 361 362 mapunit = le32_to_cpu(buf[0]); 363 e->highbit = le32_to_cpu(buf[1]); 364 count = le32_to_cpu(buf[2]); 365 366 if (mapunit != BITS_PER_U64) { 367 pr_err("SELinux: ebitmap: map size %u does not " 368 "match my size %zd (high bit was %d)\n", 369 mapunit, BITS_PER_U64, e->highbit); 370 goto bad; 371 } 372 373 /* round up e->highbit */ 374 e->highbit += EBITMAP_SIZE - 1; 375 e->highbit -= (e->highbit % EBITMAP_SIZE); 376 377 if (!e->highbit) { 378 e->node = NULL; 379 goto ok; 380 } 381 382 if (e->highbit && !count) 383 goto bad; 384 385 for (i = 0; i < count; i++) { 386 rc = next_entry(&ebitmap_start, fp, sizeof(u32)); 387 if (rc < 0) { 388 pr_err("SELinux: ebitmap: truncated map\n"); 389 goto bad; 390 } 391 startbit = le32_to_cpu(ebitmap_start); 392 393 if (startbit & (mapunit - 1)) { 394 pr_err("SELinux: ebitmap start bit (%d) is " 395 "not a multiple of the map unit size (%u)\n", 396 startbit, mapunit); 397 goto bad; 398 } 399 if (startbit > e->highbit - mapunit) { 400 pr_err("SELinux: ebitmap start bit (%d) is " 401 "beyond the end of the bitmap (%u)\n", 402 startbit, (e->highbit - mapunit)); 403 goto bad; 404 } 405 406 if (!n || startbit >= n->startbit + EBITMAP_SIZE) { 407 struct ebitmap_node *tmp; 408 tmp = kmem_cache_zalloc(ebitmap_node_cachep, GFP_KERNEL); 409 if (!tmp) { 410 pr_err("SELinux: ebitmap: out of memory\n"); 411 rc = -ENOMEM; 412 goto bad; 413 } 414 /* round down */ 415 tmp->startbit = startbit - (startbit % EBITMAP_SIZE); 416 if (n) 417 n->next = tmp; 418 else 419 e->node = tmp; 420 n = tmp; 421 } else if (startbit <= n->startbit) { 422 pr_err("SELinux: ebitmap: start bit %d" 423 " comes after start bit %d\n", 424 startbit, n->startbit); 425 goto bad; 426 } 427 428 rc = next_entry(&mapbits, fp, sizeof(u64)); 429 if (rc < 0) { 430 pr_err("SELinux: ebitmap: truncated map\n"); 431 goto bad; 432 } 433 map = le64_to_cpu(mapbits); 434 435 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; 436 while (map) { 437 n->maps[index++] = map & (-1UL); 438 map = EBITMAP_SHIFT_UNIT_SIZE(map); 439 } 440 } 441 ok: 442 rc = 0; 443 out: 444 return rc; 445 bad: 446 if (!rc) 447 rc = -EINVAL; 448 ebitmap_destroy(e); 449 goto out; 450 } 451 452 int ebitmap_write(struct ebitmap *e, void *fp) 453 { 454 struct ebitmap_node *n; 455 u32 count; 456 __le32 buf[3]; 457 u64 map; 458 int bit, last_bit, last_startbit, rc; 459 460 buf[0] = cpu_to_le32(BITS_PER_U64); 461 462 count = 0; 463 last_bit = 0; 464 last_startbit = -1; 465 ebitmap_for_each_positive_bit(e, n, bit) { 466 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { 467 count++; 468 last_startbit = rounddown(bit, BITS_PER_U64); 469 } 470 last_bit = roundup(bit + 1, BITS_PER_U64); 471 } 472 buf[1] = cpu_to_le32(last_bit); 473 buf[2] = cpu_to_le32(count); 474 475 rc = put_entry(buf, sizeof(u32), 3, fp); 476 if (rc) 477 return rc; 478 479 map = 0; 480 last_startbit = INT_MIN; 481 ebitmap_for_each_positive_bit(e, n, bit) { 482 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { 483 __le64 buf64[1]; 484 485 /* this is the very first bit */ 486 if (!map) { 487 last_startbit = rounddown(bit, BITS_PER_U64); 488 map = (u64)1 << (bit - last_startbit); 489 continue; 490 } 491 492 /* write the last node */ 493 buf[0] = cpu_to_le32(last_startbit); 494 rc = put_entry(buf, sizeof(u32), 1, fp); 495 if (rc) 496 return rc; 497 498 buf64[0] = cpu_to_le64(map); 499 rc = put_entry(buf64, sizeof(u64), 1, fp); 500 if (rc) 501 return rc; 502 503 /* set up for the next node */ 504 map = 0; 505 last_startbit = rounddown(bit, BITS_PER_U64); 506 } 507 map |= (u64)1 << (bit - last_startbit); 508 } 509 /* write the last node */ 510 if (map) { 511 __le64 buf64[1]; 512 513 /* write the last node */ 514 buf[0] = cpu_to_le32(last_startbit); 515 rc = put_entry(buf, sizeof(u32), 1, fp); 516 if (rc) 517 return rc; 518 519 buf64[0] = cpu_to_le64(map); 520 rc = put_entry(buf64, sizeof(u64), 1, fp); 521 if (rc) 522 return rc; 523 } 524 return 0; 525 } 526 527 void __init ebitmap_cache_init(void) 528 { 529 ebitmap_node_cachep = kmem_cache_create("ebitmap_node", 530 sizeof(struct ebitmap_node), 531 0, SLAB_PANIC, NULL); 532 } 533