1 /* 2 * Implementation of the access vector table type. 3 * 4 * Author : Stephen Smalley, <sds@tycho.nsa.gov> 5 */ 6 7 /* Updated: Frank Mayer <mayerf@tresys.com> and Karl MacMillan <kmacmillan@tresys.com> 8 * 9 * Added conditional policy language extensions 10 * 11 * Copyright (C) 2003 Tresys Technology, LLC 12 * This program is free software; you can redistribute it and/or modify 13 * it under the terms of the GNU General Public License as published by 14 * the Free Software Foundation, version 2. 15 * 16 * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp> 17 * Tuned number of hash slots for avtab to reduce memory usage 18 */ 19 20 #include <linux/kernel.h> 21 #include <linux/slab.h> 22 #include <linux/errno.h> 23 #include "avtab.h" 24 #include "policydb.h" 25 26 static struct kmem_cache *avtab_node_cachep; 27 static struct kmem_cache *avtab_xperms_cachep; 28 29 /* Based on MurmurHash3, written by Austin Appleby and placed in the 30 * public domain. 31 */ 32 static inline int avtab_hash(struct avtab_key *keyp, u32 mask) 33 { 34 static const u32 c1 = 0xcc9e2d51; 35 static const u32 c2 = 0x1b873593; 36 static const u32 r1 = 15; 37 static const u32 r2 = 13; 38 static const u32 m = 5; 39 static const u32 n = 0xe6546b64; 40 41 u32 hash = 0; 42 43 #define mix(input) { \ 44 u32 v = input; \ 45 v *= c1; \ 46 v = (v << r1) | (v >> (32 - r1)); \ 47 v *= c2; \ 48 hash ^= v; \ 49 hash = (hash << r2) | (hash >> (32 - r2)); \ 50 hash = hash * m + n; \ 51 } 52 53 mix(keyp->target_class); 54 mix(keyp->target_type); 55 mix(keyp->source_type); 56 57 #undef mix 58 59 hash ^= hash >> 16; 60 hash *= 0x85ebca6b; 61 hash ^= hash >> 13; 62 hash *= 0xc2b2ae35; 63 hash ^= hash >> 16; 64 65 return hash & mask; 66 } 67 68 static struct avtab_node* 69 avtab_insert_node(struct avtab *h, int hvalue, 70 struct avtab_node *prev, struct avtab_node *cur, 71 struct avtab_key *key, struct avtab_datum *datum) 72 { 73 struct avtab_node *newnode; 74 struct avtab_extended_perms *xperms; 75 newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL); 76 if (newnode == NULL) 77 return NULL; 78 newnode->key = *key; 79 80 if (key->specified & AVTAB_XPERMS) { 81 xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL); 82 if (xperms == NULL) { 83 kmem_cache_free(avtab_node_cachep, newnode); 84 return NULL; 85 } 86 *xperms = *(datum->u.xperms); 87 newnode->datum.u.xperms = xperms; 88 } else { 89 newnode->datum.u.data = datum->u.data; 90 } 91 92 if (prev) { 93 newnode->next = prev->next; 94 prev->next = newnode; 95 } else { 96 struct avtab_node **n = &h->htable[hvalue]; 97 98 newnode->next = *n; 99 *n = newnode; 100 } 101 102 h->nel++; 103 return newnode; 104 } 105 106 static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum) 107 { 108 int hvalue; 109 struct avtab_node *prev, *cur, *newnode; 110 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 111 112 if (!h) 113 return -EINVAL; 114 115 hvalue = avtab_hash(key, h->mask); 116 for (prev = NULL, cur = h->htable[hvalue]; 117 cur; 118 prev = cur, cur = cur->next) { 119 if (key->source_type == cur->key.source_type && 120 key->target_type == cur->key.target_type && 121 key->target_class == cur->key.target_class && 122 (specified & cur->key.specified)) { 123 /* extended perms may not be unique */ 124 if (specified & AVTAB_XPERMS) 125 break; 126 return -EEXIST; 127 } 128 if (key->source_type < cur->key.source_type) 129 break; 130 if (key->source_type == cur->key.source_type && 131 key->target_type < cur->key.target_type) 132 break; 133 if (key->source_type == cur->key.source_type && 134 key->target_type == cur->key.target_type && 135 key->target_class < cur->key.target_class) 136 break; 137 } 138 139 newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum); 140 if (!newnode) 141 return -ENOMEM; 142 143 return 0; 144 } 145 146 /* Unlike avtab_insert(), this function allow multiple insertions of the same 147 * key/specified mask into the table, as needed by the conditional avtab. 148 * It also returns a pointer to the node inserted. 149 */ 150 struct avtab_node * 151 avtab_insert_nonunique(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum) 152 { 153 int hvalue; 154 struct avtab_node *prev, *cur; 155 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 156 157 if (!h) 158 return NULL; 159 hvalue = avtab_hash(key, h->mask); 160 for (prev = NULL, cur = h->htable[hvalue]; 161 cur; 162 prev = cur, cur = cur->next) { 163 if (key->source_type == cur->key.source_type && 164 key->target_type == cur->key.target_type && 165 key->target_class == cur->key.target_class && 166 (specified & cur->key.specified)) 167 break; 168 if (key->source_type < cur->key.source_type) 169 break; 170 if (key->source_type == cur->key.source_type && 171 key->target_type < cur->key.target_type) 172 break; 173 if (key->source_type == cur->key.source_type && 174 key->target_type == cur->key.target_type && 175 key->target_class < cur->key.target_class) 176 break; 177 } 178 return avtab_insert_node(h, hvalue, prev, cur, key, datum); 179 } 180 181 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key) 182 { 183 int hvalue; 184 struct avtab_node *cur; 185 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 186 187 if (!h) 188 return NULL; 189 190 hvalue = avtab_hash(key, h->mask); 191 for (cur = h->htable[hvalue]; cur; 192 cur = cur->next) { 193 if (key->source_type == cur->key.source_type && 194 key->target_type == cur->key.target_type && 195 key->target_class == cur->key.target_class && 196 (specified & cur->key.specified)) 197 return &cur->datum; 198 199 if (key->source_type < cur->key.source_type) 200 break; 201 if (key->source_type == cur->key.source_type && 202 key->target_type < cur->key.target_type) 203 break; 204 if (key->source_type == cur->key.source_type && 205 key->target_type == cur->key.target_type && 206 key->target_class < cur->key.target_class) 207 break; 208 } 209 210 return NULL; 211 } 212 213 /* This search function returns a node pointer, and can be used in 214 * conjunction with avtab_search_next_node() 215 */ 216 struct avtab_node* 217 avtab_search_node(struct avtab *h, struct avtab_key *key) 218 { 219 int hvalue; 220 struct avtab_node *cur; 221 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 222 223 if (!h) 224 return NULL; 225 226 hvalue = avtab_hash(key, h->mask); 227 for (cur = h->htable[hvalue]; cur; 228 cur = cur->next) { 229 if (key->source_type == cur->key.source_type && 230 key->target_type == cur->key.target_type && 231 key->target_class == cur->key.target_class && 232 (specified & cur->key.specified)) 233 return cur; 234 235 if (key->source_type < cur->key.source_type) 236 break; 237 if (key->source_type == cur->key.source_type && 238 key->target_type < cur->key.target_type) 239 break; 240 if (key->source_type == cur->key.source_type && 241 key->target_type == cur->key.target_type && 242 key->target_class < cur->key.target_class) 243 break; 244 } 245 return NULL; 246 } 247 248 struct avtab_node* 249 avtab_search_node_next(struct avtab_node *node, int specified) 250 { 251 struct avtab_node *cur; 252 253 if (!node) 254 return NULL; 255 256 specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 257 for (cur = node->next; cur; cur = cur->next) { 258 if (node->key.source_type == cur->key.source_type && 259 node->key.target_type == cur->key.target_type && 260 node->key.target_class == cur->key.target_class && 261 (specified & cur->key.specified)) 262 return cur; 263 264 if (node->key.source_type < cur->key.source_type) 265 break; 266 if (node->key.source_type == cur->key.source_type && 267 node->key.target_type < cur->key.target_type) 268 break; 269 if (node->key.source_type == cur->key.source_type && 270 node->key.target_type == cur->key.target_type && 271 node->key.target_class < cur->key.target_class) 272 break; 273 } 274 return NULL; 275 } 276 277 void avtab_destroy(struct avtab *h) 278 { 279 int i; 280 struct avtab_node *cur, *temp; 281 282 if (!h) 283 return; 284 285 for (i = 0; i < h->nslot; i++) { 286 cur = h->htable[i]; 287 while (cur) { 288 temp = cur; 289 cur = cur->next; 290 if (temp->key.specified & AVTAB_XPERMS) 291 kmem_cache_free(avtab_xperms_cachep, 292 temp->datum.u.xperms); 293 kmem_cache_free(avtab_node_cachep, temp); 294 } 295 } 296 kvfree(h->htable); 297 h->htable = NULL; 298 h->nslot = 0; 299 h->mask = 0; 300 } 301 302 void avtab_init(struct avtab *h) 303 { 304 h->htable = NULL; 305 h->nel = 0; 306 } 307 308 int avtab_alloc(struct avtab *h, u32 nrules) 309 { 310 u32 mask = 0; 311 u32 shift = 0; 312 u32 work = nrules; 313 u32 nslot = 0; 314 315 if (nrules == 0) 316 goto avtab_alloc_out; 317 318 while (work) { 319 work = work >> 1; 320 shift++; 321 } 322 if (shift > 2) 323 shift = shift - 2; 324 nslot = 1 << shift; 325 if (nslot > MAX_AVTAB_HASH_BUCKETS) 326 nslot = MAX_AVTAB_HASH_BUCKETS; 327 mask = nslot - 1; 328 329 h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL); 330 if (!h->htable) 331 return -ENOMEM; 332 333 avtab_alloc_out: 334 h->nel = 0; 335 h->nslot = nslot; 336 h->mask = mask; 337 pr_debug("SELinux: %d avtab hash slots, %d rules.\n", 338 h->nslot, nrules); 339 return 0; 340 } 341 342 int avtab_duplicate(struct avtab *new, struct avtab *orig) 343 { 344 int i; 345 struct avtab_node *node, *tmp, *tail; 346 347 memset(new, 0, sizeof(*new)); 348 349 new->htable = kvcalloc(orig->nslot, sizeof(void *), GFP_KERNEL); 350 if (!new->htable) 351 return -ENOMEM; 352 new->nslot = orig->nslot; 353 new->mask = orig->mask; 354 355 for (i = 0; i < orig->nslot; i++) { 356 tail = NULL; 357 for (node = orig->htable[i]; node; node = node->next) { 358 tmp = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL); 359 if (!tmp) 360 goto error; 361 tmp->key = node->key; 362 if (tmp->key.specified & AVTAB_XPERMS) { 363 tmp->datum.u.xperms = 364 kmem_cache_zalloc(avtab_xperms_cachep, 365 GFP_KERNEL); 366 if (!tmp->datum.u.xperms) { 367 kmem_cache_free(avtab_node_cachep, tmp); 368 goto error; 369 } 370 tmp->datum.u.xperms = node->datum.u.xperms; 371 } else 372 tmp->datum.u.data = node->datum.u.data; 373 374 if (tail) 375 tail->next = tmp; 376 else 377 new->htable[i] = tmp; 378 379 tail = tmp; 380 new->nel++; 381 } 382 } 383 384 return 0; 385 error: 386 avtab_destroy(new); 387 return -ENOMEM; 388 } 389 390 void avtab_hash_eval(struct avtab *h, char *tag) 391 { 392 int i, chain_len, slots_used, max_chain_len; 393 unsigned long long chain2_len_sum; 394 struct avtab_node *cur; 395 396 slots_used = 0; 397 max_chain_len = 0; 398 chain2_len_sum = 0; 399 for (i = 0; i < h->nslot; i++) { 400 cur = h->htable[i]; 401 if (cur) { 402 slots_used++; 403 chain_len = 0; 404 while (cur) { 405 chain_len++; 406 cur = cur->next; 407 } 408 409 if (chain_len > max_chain_len) 410 max_chain_len = chain_len; 411 chain2_len_sum += chain_len * chain_len; 412 } 413 } 414 415 pr_debug("SELinux: %s: %d entries and %d/%d buckets used, " 416 "longest chain length %d sum of chain length^2 %llu\n", 417 tag, h->nel, slots_used, h->nslot, max_chain_len, 418 chain2_len_sum); 419 } 420 421 static uint16_t spec_order[] = { 422 AVTAB_ALLOWED, 423 AVTAB_AUDITDENY, 424 AVTAB_AUDITALLOW, 425 AVTAB_TRANSITION, 426 AVTAB_CHANGE, 427 AVTAB_MEMBER, 428 AVTAB_XPERMS_ALLOWED, 429 AVTAB_XPERMS_AUDITALLOW, 430 AVTAB_XPERMS_DONTAUDIT 431 }; 432 433 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, 434 int (*insertf)(struct avtab *a, struct avtab_key *k, 435 struct avtab_datum *d, void *p), 436 void *p) 437 { 438 __le16 buf16[4]; 439 u16 enabled; 440 u32 items, items2, val, vers = pol->policyvers; 441 struct avtab_key key; 442 struct avtab_datum datum; 443 struct avtab_extended_perms xperms; 444 __le32 buf32[ARRAY_SIZE(xperms.perms.p)]; 445 int i, rc; 446 unsigned set; 447 448 memset(&key, 0, sizeof(struct avtab_key)); 449 memset(&datum, 0, sizeof(struct avtab_datum)); 450 451 if (vers < POLICYDB_VERSION_AVTAB) { 452 rc = next_entry(buf32, fp, sizeof(u32)); 453 if (rc) { 454 pr_err("SELinux: avtab: truncated entry\n"); 455 return rc; 456 } 457 items2 = le32_to_cpu(buf32[0]); 458 if (items2 > ARRAY_SIZE(buf32)) { 459 pr_err("SELinux: avtab: entry overflow\n"); 460 return -EINVAL; 461 462 } 463 rc = next_entry(buf32, fp, sizeof(u32)*items2); 464 if (rc) { 465 pr_err("SELinux: avtab: truncated entry\n"); 466 return rc; 467 } 468 items = 0; 469 470 val = le32_to_cpu(buf32[items++]); 471 key.source_type = (u16)val; 472 if (key.source_type != val) { 473 pr_err("SELinux: avtab: truncated source type\n"); 474 return -EINVAL; 475 } 476 val = le32_to_cpu(buf32[items++]); 477 key.target_type = (u16)val; 478 if (key.target_type != val) { 479 pr_err("SELinux: avtab: truncated target type\n"); 480 return -EINVAL; 481 } 482 val = le32_to_cpu(buf32[items++]); 483 key.target_class = (u16)val; 484 if (key.target_class != val) { 485 pr_err("SELinux: avtab: truncated target class\n"); 486 return -EINVAL; 487 } 488 489 val = le32_to_cpu(buf32[items++]); 490 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0; 491 492 if (!(val & (AVTAB_AV | AVTAB_TYPE))) { 493 pr_err("SELinux: avtab: null entry\n"); 494 return -EINVAL; 495 } 496 if ((val & AVTAB_AV) && 497 (val & AVTAB_TYPE)) { 498 pr_err("SELinux: avtab: entry has both access vectors and types\n"); 499 return -EINVAL; 500 } 501 if (val & AVTAB_XPERMS) { 502 pr_err("SELinux: avtab: entry has extended permissions\n"); 503 return -EINVAL; 504 } 505 506 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 507 if (val & spec_order[i]) { 508 key.specified = spec_order[i] | enabled; 509 datum.u.data = le32_to_cpu(buf32[items++]); 510 rc = insertf(a, &key, &datum, p); 511 if (rc) 512 return rc; 513 } 514 } 515 516 if (items != items2) { 517 pr_err("SELinux: avtab: entry only had %d items, expected %d\n", 518 items2, items); 519 return -EINVAL; 520 } 521 return 0; 522 } 523 524 rc = next_entry(buf16, fp, sizeof(u16)*4); 525 if (rc) { 526 pr_err("SELinux: avtab: truncated entry\n"); 527 return rc; 528 } 529 530 items = 0; 531 key.source_type = le16_to_cpu(buf16[items++]); 532 key.target_type = le16_to_cpu(buf16[items++]); 533 key.target_class = le16_to_cpu(buf16[items++]); 534 key.specified = le16_to_cpu(buf16[items++]); 535 536 if (!policydb_type_isvalid(pol, key.source_type) || 537 !policydb_type_isvalid(pol, key.target_type) || 538 !policydb_class_isvalid(pol, key.target_class)) { 539 pr_err("SELinux: avtab: invalid type or class\n"); 540 return -EINVAL; 541 } 542 543 set = 0; 544 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 545 if (key.specified & spec_order[i]) 546 set++; 547 } 548 if (!set || set > 1) { 549 pr_err("SELinux: avtab: more than one specifier\n"); 550 return -EINVAL; 551 } 552 553 if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) && 554 (key.specified & AVTAB_XPERMS)) { 555 pr_err("SELinux: avtab: policy version %u does not " 556 "support extended permissions rules and one " 557 "was specified\n", vers); 558 return -EINVAL; 559 } else if (key.specified & AVTAB_XPERMS) { 560 memset(&xperms, 0, sizeof(struct avtab_extended_perms)); 561 rc = next_entry(&xperms.specified, fp, sizeof(u8)); 562 if (rc) { 563 pr_err("SELinux: avtab: truncated entry\n"); 564 return rc; 565 } 566 rc = next_entry(&xperms.driver, fp, sizeof(u8)); 567 if (rc) { 568 pr_err("SELinux: avtab: truncated entry\n"); 569 return rc; 570 } 571 rc = next_entry(buf32, fp, sizeof(u32)*ARRAY_SIZE(xperms.perms.p)); 572 if (rc) { 573 pr_err("SELinux: avtab: truncated entry\n"); 574 return rc; 575 } 576 for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++) 577 xperms.perms.p[i] = le32_to_cpu(buf32[i]); 578 datum.u.xperms = &xperms; 579 } else { 580 rc = next_entry(buf32, fp, sizeof(u32)); 581 if (rc) { 582 pr_err("SELinux: avtab: truncated entry\n"); 583 return rc; 584 } 585 datum.u.data = le32_to_cpu(*buf32); 586 } 587 if ((key.specified & AVTAB_TYPE) && 588 !policydb_type_isvalid(pol, datum.u.data)) { 589 pr_err("SELinux: avtab: invalid type\n"); 590 return -EINVAL; 591 } 592 return insertf(a, &key, &datum, p); 593 } 594 595 static int avtab_insertf(struct avtab *a, struct avtab_key *k, 596 struct avtab_datum *d, void *p) 597 { 598 return avtab_insert(a, k, d); 599 } 600 601 int avtab_read(struct avtab *a, void *fp, struct policydb *pol) 602 { 603 int rc; 604 __le32 buf[1]; 605 u32 nel, i; 606 607 608 rc = next_entry(buf, fp, sizeof(u32)); 609 if (rc < 0) { 610 pr_err("SELinux: avtab: truncated table\n"); 611 goto bad; 612 } 613 nel = le32_to_cpu(buf[0]); 614 if (!nel) { 615 pr_err("SELinux: avtab: table is empty\n"); 616 rc = -EINVAL; 617 goto bad; 618 } 619 620 rc = avtab_alloc(a, nel); 621 if (rc) 622 goto bad; 623 624 for (i = 0; i < nel; i++) { 625 rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL); 626 if (rc) { 627 if (rc == -ENOMEM) 628 pr_err("SELinux: avtab: out of memory\n"); 629 else if (rc == -EEXIST) 630 pr_err("SELinux: avtab: duplicate entry\n"); 631 632 goto bad; 633 } 634 } 635 636 rc = 0; 637 out: 638 return rc; 639 640 bad: 641 avtab_destroy(a); 642 goto out; 643 } 644 645 int avtab_write_item(struct policydb *p, struct avtab_node *cur, void *fp) 646 { 647 __le16 buf16[4]; 648 __le32 buf32[ARRAY_SIZE(cur->datum.u.xperms->perms.p)]; 649 int rc; 650 unsigned int i; 651 652 buf16[0] = cpu_to_le16(cur->key.source_type); 653 buf16[1] = cpu_to_le16(cur->key.target_type); 654 buf16[2] = cpu_to_le16(cur->key.target_class); 655 buf16[3] = cpu_to_le16(cur->key.specified); 656 rc = put_entry(buf16, sizeof(u16), 4, fp); 657 if (rc) 658 return rc; 659 660 if (cur->key.specified & AVTAB_XPERMS) { 661 rc = put_entry(&cur->datum.u.xperms->specified, sizeof(u8), 1, fp); 662 if (rc) 663 return rc; 664 rc = put_entry(&cur->datum.u.xperms->driver, sizeof(u8), 1, fp); 665 if (rc) 666 return rc; 667 for (i = 0; i < ARRAY_SIZE(cur->datum.u.xperms->perms.p); i++) 668 buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]); 669 rc = put_entry(buf32, sizeof(u32), 670 ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp); 671 } else { 672 buf32[0] = cpu_to_le32(cur->datum.u.data); 673 rc = put_entry(buf32, sizeof(u32), 1, fp); 674 } 675 if (rc) 676 return rc; 677 return 0; 678 } 679 680 int avtab_write(struct policydb *p, struct avtab *a, void *fp) 681 { 682 unsigned int i; 683 int rc = 0; 684 struct avtab_node *cur; 685 __le32 buf[1]; 686 687 buf[0] = cpu_to_le32(a->nel); 688 rc = put_entry(buf, sizeof(u32), 1, fp); 689 if (rc) 690 return rc; 691 692 for (i = 0; i < a->nslot; i++) { 693 for (cur = a->htable[i]; cur; 694 cur = cur->next) { 695 rc = avtab_write_item(p, cur, fp); 696 if (rc) 697 return rc; 698 } 699 } 700 701 return rc; 702 } 703 704 void __init avtab_cache_init(void) 705 { 706 avtab_node_cachep = kmem_cache_create("avtab_node", 707 sizeof(struct avtab_node), 708 0, SLAB_PANIC, NULL); 709 avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms", 710 sizeof(struct avtab_extended_perms), 711 0, SLAB_PANIC, NULL); 712 } 713