1 /* 2 * Implementation of the access vector table type. 3 * 4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil> 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 newnode->next = flex_array_get_ptr(h->htable, hvalue); 97 if (flex_array_put_ptr(h->htable, hvalue, newnode, 98 GFP_KERNEL|__GFP_ZERO)) { 99 kmem_cache_free(avtab_node_cachep, newnode); 100 return NULL; 101 } 102 } 103 104 h->nel++; 105 return newnode; 106 } 107 108 static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum) 109 { 110 int hvalue; 111 struct avtab_node *prev, *cur, *newnode; 112 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 113 114 if (!h || !h->htable) 115 return -EINVAL; 116 117 hvalue = avtab_hash(key, h->mask); 118 for (prev = NULL, cur = flex_array_get_ptr(h->htable, hvalue); 119 cur; 120 prev = cur, cur = cur->next) { 121 if (key->source_type == cur->key.source_type && 122 key->target_type == cur->key.target_type && 123 key->target_class == cur->key.target_class && 124 (specified & cur->key.specified)) { 125 /* extended perms may not be unique */ 126 if (specified & AVTAB_XPERMS) 127 break; 128 return -EEXIST; 129 } 130 if (key->source_type < cur->key.source_type) 131 break; 132 if (key->source_type == cur->key.source_type && 133 key->target_type < cur->key.target_type) 134 break; 135 if (key->source_type == cur->key.source_type && 136 key->target_type == cur->key.target_type && 137 key->target_class < cur->key.target_class) 138 break; 139 } 140 141 newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum); 142 if (!newnode) 143 return -ENOMEM; 144 145 return 0; 146 } 147 148 /* Unlike avtab_insert(), this function allow multiple insertions of the same 149 * key/specified mask into the table, as needed by the conditional avtab. 150 * It also returns a pointer to the node inserted. 151 */ 152 struct avtab_node * 153 avtab_insert_nonunique(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum) 154 { 155 int hvalue; 156 struct avtab_node *prev, *cur; 157 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 158 159 if (!h || !h->htable) 160 return NULL; 161 hvalue = avtab_hash(key, h->mask); 162 for (prev = NULL, cur = flex_array_get_ptr(h->htable, hvalue); 163 cur; 164 prev = cur, cur = cur->next) { 165 if (key->source_type == cur->key.source_type && 166 key->target_type == cur->key.target_type && 167 key->target_class == cur->key.target_class && 168 (specified & cur->key.specified)) 169 break; 170 if (key->source_type < cur->key.source_type) 171 break; 172 if (key->source_type == cur->key.source_type && 173 key->target_type < cur->key.target_type) 174 break; 175 if (key->source_type == cur->key.source_type && 176 key->target_type == cur->key.target_type && 177 key->target_class < cur->key.target_class) 178 break; 179 } 180 return avtab_insert_node(h, hvalue, prev, cur, key, datum); 181 } 182 183 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key) 184 { 185 int hvalue; 186 struct avtab_node *cur; 187 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 188 189 if (!h || !h->htable) 190 return NULL; 191 192 hvalue = avtab_hash(key, h->mask); 193 for (cur = flex_array_get_ptr(h->htable, hvalue); cur; 194 cur = cur->next) { 195 if (key->source_type == cur->key.source_type && 196 key->target_type == cur->key.target_type && 197 key->target_class == cur->key.target_class && 198 (specified & cur->key.specified)) 199 return &cur->datum; 200 201 if (key->source_type < cur->key.source_type) 202 break; 203 if (key->source_type == cur->key.source_type && 204 key->target_type < cur->key.target_type) 205 break; 206 if (key->source_type == cur->key.source_type && 207 key->target_type == cur->key.target_type && 208 key->target_class < cur->key.target_class) 209 break; 210 } 211 212 return NULL; 213 } 214 215 /* This search function returns a node pointer, and can be used in 216 * conjunction with avtab_search_next_node() 217 */ 218 struct avtab_node* 219 avtab_search_node(struct avtab *h, struct avtab_key *key) 220 { 221 int hvalue; 222 struct avtab_node *cur; 223 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 224 225 if (!h || !h->htable) 226 return NULL; 227 228 hvalue = avtab_hash(key, h->mask); 229 for (cur = flex_array_get_ptr(h->htable, hvalue); cur; 230 cur = cur->next) { 231 if (key->source_type == cur->key.source_type && 232 key->target_type == cur->key.target_type && 233 key->target_class == cur->key.target_class && 234 (specified & cur->key.specified)) 235 return cur; 236 237 if (key->source_type < cur->key.source_type) 238 break; 239 if (key->source_type == cur->key.source_type && 240 key->target_type < cur->key.target_type) 241 break; 242 if (key->source_type == cur->key.source_type && 243 key->target_type == cur->key.target_type && 244 key->target_class < cur->key.target_class) 245 break; 246 } 247 return NULL; 248 } 249 250 struct avtab_node* 251 avtab_search_node_next(struct avtab_node *node, int specified) 252 { 253 struct avtab_node *cur; 254 255 if (!node) 256 return NULL; 257 258 specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 259 for (cur = node->next; cur; cur = cur->next) { 260 if (node->key.source_type == cur->key.source_type && 261 node->key.target_type == cur->key.target_type && 262 node->key.target_class == cur->key.target_class && 263 (specified & cur->key.specified)) 264 return cur; 265 266 if (node->key.source_type < cur->key.source_type) 267 break; 268 if (node->key.source_type == cur->key.source_type && 269 node->key.target_type < cur->key.target_type) 270 break; 271 if (node->key.source_type == cur->key.source_type && 272 node->key.target_type == cur->key.target_type && 273 node->key.target_class < cur->key.target_class) 274 break; 275 } 276 return NULL; 277 } 278 279 void avtab_destroy(struct avtab *h) 280 { 281 int i; 282 struct avtab_node *cur, *temp; 283 284 if (!h || !h->htable) 285 return; 286 287 for (i = 0; i < h->nslot; i++) { 288 cur = flex_array_get_ptr(h->htable, i); 289 while (cur) { 290 temp = cur; 291 cur = cur->next; 292 if (temp->key.specified & AVTAB_XPERMS) 293 kmem_cache_free(avtab_xperms_cachep, 294 temp->datum.u.xperms); 295 kmem_cache_free(avtab_node_cachep, temp); 296 } 297 } 298 flex_array_free(h->htable); 299 h->htable = NULL; 300 h->nslot = 0; 301 h->mask = 0; 302 } 303 304 int avtab_init(struct avtab *h) 305 { 306 h->htable = NULL; 307 h->nel = 0; 308 return 0; 309 } 310 311 int avtab_alloc(struct avtab *h, u32 nrules) 312 { 313 u32 mask = 0; 314 u32 shift = 0; 315 u32 work = nrules; 316 u32 nslot = 0; 317 318 if (nrules == 0) 319 goto avtab_alloc_out; 320 321 while (work) { 322 work = work >> 1; 323 shift++; 324 } 325 if (shift > 2) 326 shift = shift - 2; 327 nslot = 1 << shift; 328 if (nslot > MAX_AVTAB_HASH_BUCKETS) 329 nslot = MAX_AVTAB_HASH_BUCKETS; 330 mask = nslot - 1; 331 332 h->htable = flex_array_alloc(sizeof(struct avtab_node *), nslot, 333 GFP_KERNEL | __GFP_ZERO); 334 if (!h->htable) 335 return -ENOMEM; 336 337 avtab_alloc_out: 338 h->nel = 0; 339 h->nslot = nslot; 340 h->mask = mask; 341 printk(KERN_DEBUG "SELinux: %d avtab hash slots, %d rules.\n", 342 h->nslot, nrules); 343 return 0; 344 } 345 346 void avtab_hash_eval(struct avtab *h, char *tag) 347 { 348 int i, chain_len, slots_used, max_chain_len; 349 unsigned long long chain2_len_sum; 350 struct avtab_node *cur; 351 352 slots_used = 0; 353 max_chain_len = 0; 354 chain2_len_sum = 0; 355 for (i = 0; i < h->nslot; i++) { 356 cur = flex_array_get_ptr(h->htable, i); 357 if (cur) { 358 slots_used++; 359 chain_len = 0; 360 while (cur) { 361 chain_len++; 362 cur = cur->next; 363 } 364 365 if (chain_len > max_chain_len) 366 max_chain_len = chain_len; 367 chain2_len_sum += chain_len * chain_len; 368 } 369 } 370 371 printk(KERN_DEBUG "SELinux: %s: %d entries and %d/%d buckets used, " 372 "longest chain length %d sum of chain length^2 %llu\n", 373 tag, h->nel, slots_used, h->nslot, max_chain_len, 374 chain2_len_sum); 375 } 376 377 static uint16_t spec_order[] = { 378 AVTAB_ALLOWED, 379 AVTAB_AUDITDENY, 380 AVTAB_AUDITALLOW, 381 AVTAB_TRANSITION, 382 AVTAB_CHANGE, 383 AVTAB_MEMBER, 384 AVTAB_XPERMS_ALLOWED, 385 AVTAB_XPERMS_AUDITALLOW, 386 AVTAB_XPERMS_DONTAUDIT 387 }; 388 389 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, 390 int (*insertf)(struct avtab *a, struct avtab_key *k, 391 struct avtab_datum *d, void *p), 392 void *p) 393 { 394 __le16 buf16[4]; 395 u16 enabled; 396 u32 items, items2, val, vers = pol->policyvers; 397 struct avtab_key key; 398 struct avtab_datum datum; 399 struct avtab_extended_perms xperms; 400 __le32 buf32[ARRAY_SIZE(xperms.perms.p)]; 401 int i, rc; 402 unsigned set; 403 404 memset(&key, 0, sizeof(struct avtab_key)); 405 memset(&datum, 0, sizeof(struct avtab_datum)); 406 407 if (vers < POLICYDB_VERSION_AVTAB) { 408 rc = next_entry(buf32, fp, sizeof(u32)); 409 if (rc) { 410 printk(KERN_ERR "SELinux: avtab: truncated entry\n"); 411 return rc; 412 } 413 items2 = le32_to_cpu(buf32[0]); 414 if (items2 > ARRAY_SIZE(buf32)) { 415 printk(KERN_ERR "SELinux: avtab: entry overflow\n"); 416 return -EINVAL; 417 418 } 419 rc = next_entry(buf32, fp, sizeof(u32)*items2); 420 if (rc) { 421 printk(KERN_ERR "SELinux: avtab: truncated entry\n"); 422 return rc; 423 } 424 items = 0; 425 426 val = le32_to_cpu(buf32[items++]); 427 key.source_type = (u16)val; 428 if (key.source_type != val) { 429 printk(KERN_ERR "SELinux: avtab: truncated source type\n"); 430 return -EINVAL; 431 } 432 val = le32_to_cpu(buf32[items++]); 433 key.target_type = (u16)val; 434 if (key.target_type != val) { 435 printk(KERN_ERR "SELinux: avtab: truncated target type\n"); 436 return -EINVAL; 437 } 438 val = le32_to_cpu(buf32[items++]); 439 key.target_class = (u16)val; 440 if (key.target_class != val) { 441 printk(KERN_ERR "SELinux: avtab: truncated target class\n"); 442 return -EINVAL; 443 } 444 445 val = le32_to_cpu(buf32[items++]); 446 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0; 447 448 if (!(val & (AVTAB_AV | AVTAB_TYPE))) { 449 printk(KERN_ERR "SELinux: avtab: null entry\n"); 450 return -EINVAL; 451 } 452 if ((val & AVTAB_AV) && 453 (val & AVTAB_TYPE)) { 454 printk(KERN_ERR "SELinux: avtab: entry has both access vectors and types\n"); 455 return -EINVAL; 456 } 457 if (val & AVTAB_XPERMS) { 458 printk(KERN_ERR "SELinux: avtab: entry has extended permissions\n"); 459 return -EINVAL; 460 } 461 462 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 463 if (val & spec_order[i]) { 464 key.specified = spec_order[i] | enabled; 465 datum.u.data = le32_to_cpu(buf32[items++]); 466 rc = insertf(a, &key, &datum, p); 467 if (rc) 468 return rc; 469 } 470 } 471 472 if (items != items2) { 473 printk(KERN_ERR "SELinux: avtab: entry only had %d items, expected %d\n", items2, items); 474 return -EINVAL; 475 } 476 return 0; 477 } 478 479 rc = next_entry(buf16, fp, sizeof(u16)*4); 480 if (rc) { 481 printk(KERN_ERR "SELinux: avtab: truncated entry\n"); 482 return rc; 483 } 484 485 items = 0; 486 key.source_type = le16_to_cpu(buf16[items++]); 487 key.target_type = le16_to_cpu(buf16[items++]); 488 key.target_class = le16_to_cpu(buf16[items++]); 489 key.specified = le16_to_cpu(buf16[items++]); 490 491 if (!policydb_type_isvalid(pol, key.source_type) || 492 !policydb_type_isvalid(pol, key.target_type) || 493 !policydb_class_isvalid(pol, key.target_class)) { 494 printk(KERN_ERR "SELinux: avtab: invalid type or class\n"); 495 return -EINVAL; 496 } 497 498 set = 0; 499 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 500 if (key.specified & spec_order[i]) 501 set++; 502 } 503 if (!set || set > 1) { 504 printk(KERN_ERR "SELinux: avtab: more than one specifier\n"); 505 return -EINVAL; 506 } 507 508 if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) && 509 (key.specified & AVTAB_XPERMS)) { 510 printk(KERN_ERR "SELinux: avtab: policy version %u does not " 511 "support extended permissions rules and one " 512 "was specified\n", vers); 513 return -EINVAL; 514 } else if (key.specified & AVTAB_XPERMS) { 515 memset(&xperms, 0, sizeof(struct avtab_extended_perms)); 516 rc = next_entry(&xperms.specified, fp, sizeof(u8)); 517 if (rc) { 518 printk(KERN_ERR "SELinux: avtab: truncated entry\n"); 519 return rc; 520 } 521 rc = next_entry(&xperms.driver, fp, sizeof(u8)); 522 if (rc) { 523 printk(KERN_ERR "SELinux: avtab: truncated entry\n"); 524 return rc; 525 } 526 rc = next_entry(buf32, fp, sizeof(u32)*ARRAY_SIZE(xperms.perms.p)); 527 if (rc) { 528 printk(KERN_ERR "SELinux: avtab: truncated entry\n"); 529 return rc; 530 } 531 for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++) 532 xperms.perms.p[i] = le32_to_cpu(buf32[i]); 533 datum.u.xperms = &xperms; 534 } else { 535 rc = next_entry(buf32, fp, sizeof(u32)); 536 if (rc) { 537 printk(KERN_ERR "SELinux: avtab: truncated entry\n"); 538 return rc; 539 } 540 datum.u.data = le32_to_cpu(*buf32); 541 } 542 if ((key.specified & AVTAB_TYPE) && 543 !policydb_type_isvalid(pol, datum.u.data)) { 544 printk(KERN_ERR "SELinux: avtab: invalid type\n"); 545 return -EINVAL; 546 } 547 return insertf(a, &key, &datum, p); 548 } 549 550 static int avtab_insertf(struct avtab *a, struct avtab_key *k, 551 struct avtab_datum *d, void *p) 552 { 553 return avtab_insert(a, k, d); 554 } 555 556 int avtab_read(struct avtab *a, void *fp, struct policydb *pol) 557 { 558 int rc; 559 __le32 buf[1]; 560 u32 nel, i; 561 562 563 rc = next_entry(buf, fp, sizeof(u32)); 564 if (rc < 0) { 565 printk(KERN_ERR "SELinux: avtab: truncated table\n"); 566 goto bad; 567 } 568 nel = le32_to_cpu(buf[0]); 569 if (!nel) { 570 printk(KERN_ERR "SELinux: avtab: table is empty\n"); 571 rc = -EINVAL; 572 goto bad; 573 } 574 575 rc = avtab_alloc(a, nel); 576 if (rc) 577 goto bad; 578 579 for (i = 0; i < nel; i++) { 580 rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL); 581 if (rc) { 582 if (rc == -ENOMEM) 583 printk(KERN_ERR "SELinux: avtab: out of memory\n"); 584 else if (rc == -EEXIST) 585 printk(KERN_ERR "SELinux: avtab: duplicate entry\n"); 586 587 goto bad; 588 } 589 } 590 591 rc = 0; 592 out: 593 return rc; 594 595 bad: 596 avtab_destroy(a); 597 goto out; 598 } 599 600 int avtab_write_item(struct policydb *p, struct avtab_node *cur, void *fp) 601 { 602 __le16 buf16[4]; 603 __le32 buf32[ARRAY_SIZE(cur->datum.u.xperms->perms.p)]; 604 int rc; 605 unsigned int i; 606 607 buf16[0] = cpu_to_le16(cur->key.source_type); 608 buf16[1] = cpu_to_le16(cur->key.target_type); 609 buf16[2] = cpu_to_le16(cur->key.target_class); 610 buf16[3] = cpu_to_le16(cur->key.specified); 611 rc = put_entry(buf16, sizeof(u16), 4, fp); 612 if (rc) 613 return rc; 614 615 if (cur->key.specified & AVTAB_XPERMS) { 616 rc = put_entry(&cur->datum.u.xperms->specified, sizeof(u8), 1, fp); 617 if (rc) 618 return rc; 619 rc = put_entry(&cur->datum.u.xperms->driver, sizeof(u8), 1, fp); 620 if (rc) 621 return rc; 622 for (i = 0; i < ARRAY_SIZE(cur->datum.u.xperms->perms.p); i++) 623 buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]); 624 rc = put_entry(buf32, sizeof(u32), 625 ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp); 626 } else { 627 buf32[0] = cpu_to_le32(cur->datum.u.data); 628 rc = put_entry(buf32, sizeof(u32), 1, fp); 629 } 630 if (rc) 631 return rc; 632 return 0; 633 } 634 635 int avtab_write(struct policydb *p, struct avtab *a, void *fp) 636 { 637 unsigned int i; 638 int rc = 0; 639 struct avtab_node *cur; 640 __le32 buf[1]; 641 642 buf[0] = cpu_to_le32(a->nel); 643 rc = put_entry(buf, sizeof(u32), 1, fp); 644 if (rc) 645 return rc; 646 647 for (i = 0; i < a->nslot; i++) { 648 for (cur = flex_array_get_ptr(a->htable, i); cur; 649 cur = cur->next) { 650 rc = avtab_write_item(p, cur, fp); 651 if (rc) 652 return rc; 653 } 654 } 655 656 return rc; 657 } 658 void avtab_cache_init(void) 659 { 660 avtab_node_cachep = kmem_cache_create("avtab_node", 661 sizeof(struct avtab_node), 662 0, SLAB_PANIC, NULL); 663 avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms", 664 sizeof(struct avtab_extended_perms), 665 0, SLAB_PANIC, NULL); 666 } 667 668 void avtab_cache_destroy(void) 669 { 670 kmem_cache_destroy(avtab_node_cachep); 671 kmem_cache_destroy(avtab_xperms_cachep); 672 } 673