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