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