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 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2) 217 { 218 struct ebitmap_node *n1, *n2; 219 int i; 220 221 if (e1->highbit < e2->highbit) 222 return 0; 223 224 n1 = e1->node; 225 n2 = e2->node; 226 while (n1 && n2 && (n1->startbit <= n2->startbit)) { 227 if (n1->startbit < n2->startbit) { 228 n1 = n1->next; 229 continue; 230 } 231 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) { 232 if ((n1->maps[i] & n2->maps[i]) != n2->maps[i]) 233 return 0; 234 } 235 236 n1 = n1->next; 237 n2 = n2->next; 238 } 239 240 if (n2) 241 return 0; 242 243 return 1; 244 } 245 246 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit) 247 { 248 struct ebitmap_node *n; 249 250 if (e->highbit < bit) 251 return 0; 252 253 n = e->node; 254 while (n && (n->startbit <= bit)) { 255 if ((n->startbit + EBITMAP_SIZE) > bit) 256 return ebitmap_node_get_bit(n, bit); 257 n = n->next; 258 } 259 260 return 0; 261 } 262 263 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) 264 { 265 struct ebitmap_node *n, *prev, *new; 266 267 prev = NULL; 268 n = e->node; 269 while (n && n->startbit <= bit) { 270 if ((n->startbit + EBITMAP_SIZE) > bit) { 271 if (value) { 272 ebitmap_node_set_bit(n, bit); 273 } else { 274 unsigned int s; 275 276 ebitmap_node_clr_bit(n, bit); 277 278 s = find_first_bit(n->maps, EBITMAP_SIZE); 279 if (s < EBITMAP_SIZE) 280 return 0; 281 282 /* drop this node from the bitmap */ 283 if (!n->next) { 284 /* 285 * this was the highest map 286 * within the bitmap 287 */ 288 if (prev) 289 e->highbit = prev->startbit 290 + EBITMAP_SIZE; 291 else 292 e->highbit = 0; 293 } 294 if (prev) 295 prev->next = n->next; 296 else 297 e->node = n->next; 298 kfree(n); 299 } 300 return 0; 301 } 302 prev = n; 303 n = n->next; 304 } 305 306 if (!value) 307 return 0; 308 309 new = kzalloc(sizeof(*new), GFP_ATOMIC); 310 if (!new) 311 return -ENOMEM; 312 313 new->startbit = bit - (bit % EBITMAP_SIZE); 314 ebitmap_node_set_bit(new, bit); 315 316 if (!n) 317 /* this node will be the highest map within the bitmap */ 318 e->highbit = new->startbit + EBITMAP_SIZE; 319 320 if (prev) { 321 new->next = prev->next; 322 prev->next = new; 323 } else { 324 new->next = e->node; 325 e->node = new; 326 } 327 328 return 0; 329 } 330 331 void ebitmap_destroy(struct ebitmap *e) 332 { 333 struct ebitmap_node *n, *temp; 334 335 if (!e) 336 return; 337 338 n = e->node; 339 while (n) { 340 temp = n; 341 n = n->next; 342 kfree(temp); 343 } 344 345 e->highbit = 0; 346 e->node = NULL; 347 return; 348 } 349 350 int ebitmap_read(struct ebitmap *e, void *fp) 351 { 352 struct ebitmap_node *n = NULL; 353 u32 mapunit, count, startbit, index; 354 u64 map; 355 __le32 buf[3]; 356 int rc, i; 357 358 ebitmap_init(e); 359 360 rc = next_entry(buf, fp, sizeof buf); 361 if (rc < 0) 362 goto out; 363 364 mapunit = le32_to_cpu(buf[0]); 365 e->highbit = le32_to_cpu(buf[1]); 366 count = le32_to_cpu(buf[2]); 367 368 if (mapunit != BITS_PER_U64) { 369 printk(KERN_ERR "SELinux: ebitmap: map size %u does not " 370 "match my size %Zd (high bit was %d)\n", 371 mapunit, BITS_PER_U64, e->highbit); 372 goto bad; 373 } 374 375 /* round up e->highbit */ 376 e->highbit += EBITMAP_SIZE - 1; 377 e->highbit -= (e->highbit % EBITMAP_SIZE); 378 379 if (!e->highbit) { 380 e->node = NULL; 381 goto ok; 382 } 383 384 for (i = 0; i < count; i++) { 385 rc = next_entry(&startbit, fp, sizeof(u32)); 386 if (rc < 0) { 387 printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); 388 goto bad; 389 } 390 startbit = le32_to_cpu(startbit); 391 392 if (startbit & (mapunit - 1)) { 393 printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " 394 "not a multiple of the map unit size (%u)\n", 395 startbit, mapunit); 396 goto bad; 397 } 398 if (startbit > e->highbit - mapunit) { 399 printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " 400 "beyond the end of the bitmap (%u)\n", 401 startbit, (e->highbit - mapunit)); 402 goto bad; 403 } 404 405 if (!n || startbit >= n->startbit + EBITMAP_SIZE) { 406 struct ebitmap_node *tmp; 407 tmp = kzalloc(sizeof(*tmp), GFP_KERNEL); 408 if (!tmp) { 409 printk(KERN_ERR 410 "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 printk(KERN_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(&map, fp, sizeof(u64)); 429 if (rc < 0) { 430 printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); 431 goto bad; 432 } 433 map = le64_to_cpu(map); 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