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