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 & ~(EBITMAP_SIZE - 1); 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 for (i = 0; i < count; i++) { 378 rc = next_entry(&startbit, fp, sizeof(u32)); 379 if (rc < 0) { 380 printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); 381 goto bad; 382 } 383 startbit = le32_to_cpu(startbit); 384 385 if (startbit & (mapunit - 1)) { 386 printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " 387 "not a multiple of the map unit size (%u)\n", 388 startbit, mapunit); 389 goto bad; 390 } 391 if (startbit > e->highbit - mapunit) { 392 printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " 393 "beyond the end of the bitmap (%u)\n", 394 startbit, (e->highbit - mapunit)); 395 goto bad; 396 } 397 398 if (!n || startbit >= n->startbit + EBITMAP_SIZE) { 399 struct ebitmap_node *tmp; 400 tmp = kzalloc(sizeof(*tmp), GFP_KERNEL); 401 if (!tmp) { 402 printk(KERN_ERR 403 "SELinux: ebitmap: out of memory\n"); 404 rc = -ENOMEM; 405 goto bad; 406 } 407 /* round down */ 408 tmp->startbit = startbit - (startbit % EBITMAP_SIZE); 409 if (n) 410 n->next = tmp; 411 else 412 e->node = tmp; 413 n = tmp; 414 } else if (startbit <= n->startbit) { 415 printk(KERN_ERR "SELinux: ebitmap: start bit %d" 416 " comes after start bit %d\n", 417 startbit, n->startbit); 418 goto bad; 419 } 420 421 rc = next_entry(&map, fp, sizeof(u64)); 422 if (rc < 0) { 423 printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); 424 goto bad; 425 } 426 map = le64_to_cpu(map); 427 428 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; 429 while (map) { 430 n->maps[index++] = map & (-1UL); 431 map = EBITMAP_SHIFT_UNIT_SIZE(map); 432 } 433 } 434 ok: 435 rc = 0; 436 out: 437 return rc; 438 bad: 439 if (!rc) 440 rc = -EINVAL; 441 ebitmap_destroy(e); 442 goto out; 443 } 444 445 int ebitmap_write(struct ebitmap *e, void *fp) 446 { 447 struct ebitmap_node *n; 448 u32 count; 449 __le32 buf[3]; 450 u64 map; 451 int bit, last_bit, last_startbit, rc; 452 453 buf[0] = cpu_to_le32(BITS_PER_U64); 454 455 count = 0; 456 last_bit = 0; 457 last_startbit = -1; 458 ebitmap_for_each_positive_bit(e, n, bit) { 459 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { 460 count++; 461 last_startbit = rounddown(bit, BITS_PER_U64); 462 } 463 last_bit = roundup(bit + 1, BITS_PER_U64); 464 } 465 buf[1] = cpu_to_le32(last_bit); 466 buf[2] = cpu_to_le32(count); 467 468 rc = put_entry(buf, sizeof(u32), 3, fp); 469 if (rc) 470 return rc; 471 472 map = 0; 473 last_startbit = INT_MIN; 474 ebitmap_for_each_positive_bit(e, n, bit) { 475 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { 476 __le64 buf64[1]; 477 478 /* this is the very first bit */ 479 if (!map) { 480 last_startbit = rounddown(bit, BITS_PER_U64); 481 map = (u64)1 << (bit - last_startbit); 482 continue; 483 } 484 485 /* write the last node */ 486 buf[0] = cpu_to_le32(last_startbit); 487 rc = put_entry(buf, sizeof(u32), 1, fp); 488 if (rc) 489 return rc; 490 491 buf64[0] = cpu_to_le64(map); 492 rc = put_entry(buf64, sizeof(u64), 1, fp); 493 if (rc) 494 return rc; 495 496 /* set up for the next node */ 497 map = 0; 498 last_startbit = rounddown(bit, BITS_PER_U64); 499 } 500 map |= (u64)1 << (bit - last_startbit); 501 } 502 /* write the last node */ 503 if (map) { 504 __le64 buf64[1]; 505 506 /* write the last node */ 507 buf[0] = cpu_to_le32(last_startbit); 508 rc = put_entry(buf, sizeof(u32), 1, fp); 509 if (rc) 510 return rc; 511 512 buf64[0] = cpu_to_le64(map); 513 rc = put_entry(buf64, sizeof(u64), 1, fp); 514 if (rc) 515 return rc; 516 } 517 return 0; 518 } 519