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