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