1 2 /* Author : Stephen Smalley, <sds (at) epoch.ncsc.mil> */ 3 4 /* 5 * Updated: Yuichi Nakamura <ynakam (at) hitachisoft.jp> 6 * Tuned number of hash slots for avtab to reduce memory usage 7 */ 8 9 /* Updated: Frank Mayer <mayerf (at) tresys.com> 10 * and Karl MacMillan <kmacmillan (at) mentalrootkit.com> 11 * 12 * Added conditional policy language extensions 13 * 14 * Updated: Red Hat, Inc. James Morris <jmorris (at) redhat.com> 15 * 16 * Code cleanup 17 * 18 * Updated: Karl MacMillan <kmacmillan (at) mentalrootkit.com> 19 * 20 * Copyright (C) 2003 Tresys Technology, LLC 21 * Copyright (C) 2003,2007 Red Hat, Inc. 22 * 23 * This library is free software; you can redistribute it and/or 24 * modify it under the terms of the GNU Lesser General Public 25 * License as published by the Free Software Foundation; either 26 * version 2.1 of the License, or (at your option) any later version. 27 * 28 * This library is distributed in the hope that it will be useful, 29 * but WITHOUT ANY WARRANTY; without even the implied warranty of 30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 31 * Lesser General Public License for more details. 32 * 33 * You should have received a copy of the GNU Lesser General Public 34 * License along with this library; if not, write to the Free Software 35 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 36 */ 37 38 /* FLASK */ 39 40 /* 41 * Implementation of the access vector table type. 42 */ 43 44 #include <stdlib.h> 45 #include <sepol/policydb/avtab.h> 46 #include <sepol/policydb/policydb.h> 47 #include <sepol/errcodes.h> 48 49 #include "debug.h" 50 #include "private.h" 51 52 /* Based on MurmurHash3, written by Austin Appleby and placed in the 53 * public domain. 54 */ 55 static inline int avtab_hash(struct avtab_key *keyp, uint32_t mask) 56 { 57 static const uint32_t c1 = 0xcc9e2d51; 58 static const uint32_t c2 = 0x1b873593; 59 static const uint32_t r1 = 15; 60 static const uint32_t r2 = 13; 61 static const uint32_t m = 5; 62 static const uint32_t n = 0xe6546b64; 63 64 uint32_t hash = 0; 65 66 #define mix(input) { \ 67 uint32_t v = input; \ 68 v *= c1; \ 69 v = (v << r1) | (v >> (32 - r1)); \ 70 v *= c2; \ 71 hash ^= v; \ 72 hash = (hash << r2) | (hash >> (32 - r2)); \ 73 hash = hash * m + n; \ 74 } 75 76 mix(keyp->target_class); 77 mix(keyp->target_type); 78 mix(keyp->source_type); 79 80 #undef mix 81 82 hash ^= hash >> 16; 83 hash *= 0x85ebca6b; 84 hash ^= hash >> 13; 85 hash *= 0xc2b2ae35; 86 hash ^= hash >> 16; 87 88 return hash & mask; 89 } 90 91 static avtab_ptr_t 92 avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key, 93 avtab_datum_t * datum) 94 { 95 avtab_ptr_t newnode; 96 avtab_extended_perms_t *xperms; 97 98 newnode = (avtab_ptr_t) malloc(sizeof(struct avtab_node)); 99 if (newnode == NULL) 100 return NULL; 101 memset(newnode, 0, sizeof(struct avtab_node)); 102 newnode->key = *key; 103 104 if (key->specified & AVTAB_XPERMS) { 105 xperms = calloc(1, sizeof(avtab_extended_perms_t)); 106 if (xperms == NULL) { 107 free(newnode); 108 return NULL; 109 } 110 if (datum->xperms) /* else caller populates xperms */ 111 *xperms = *(datum->xperms); 112 113 newnode->datum.xperms = xperms; 114 /* data is usually ignored with xperms, except in the case of 115 * neverallow checking, which requires permission bits to be set. 116 * So copy data so it is set in the avtab 117 */ 118 newnode->datum.data = datum->data; 119 } else { 120 newnode->datum = *datum; 121 } 122 123 if (prev) { 124 newnode->next = prev->next; 125 prev->next = newnode; 126 } else { 127 newnode->next = h->htable[hvalue]; 128 h->htable[hvalue] = newnode; 129 } 130 131 h->nel++; 132 return newnode; 133 } 134 135 int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum) 136 { 137 int hvalue; 138 avtab_ptr_t prev, cur, newnode; 139 uint16_t specified = 140 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 141 142 if (!h || !h->htable) 143 return SEPOL_ENOMEM; 144 145 hvalue = avtab_hash(key, h->mask); 146 for (prev = NULL, cur = h->htable[hvalue]; 147 cur; prev = cur, cur = cur->next) { 148 if (key->source_type == cur->key.source_type && 149 key->target_type == cur->key.target_type && 150 key->target_class == cur->key.target_class && 151 (specified & cur->key.specified)) { 152 /* Extended permissions are not necessarily unique */ 153 if (specified & AVTAB_XPERMS) 154 break; 155 return SEPOL_EEXIST; 156 } 157 if (key->source_type < cur->key.source_type) 158 break; 159 if (key->source_type == cur->key.source_type && 160 key->target_type < cur->key.target_type) 161 break; 162 if (key->source_type == cur->key.source_type && 163 key->target_type == cur->key.target_type && 164 key->target_class < cur->key.target_class) 165 break; 166 } 167 168 newnode = avtab_insert_node(h, hvalue, prev, key, datum); 169 if (!newnode) 170 return SEPOL_ENOMEM; 171 172 return 0; 173 } 174 175 /* Unlike avtab_insert(), this function allow multiple insertions of the same 176 * key/specified mask into the table, as needed by the conditional avtab. 177 * It also returns a pointer to the node inserted. 178 */ 179 avtab_ptr_t 180 avtab_insert_nonunique(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum) 181 { 182 int hvalue; 183 avtab_ptr_t prev, cur, newnode; 184 uint16_t specified = 185 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 186 187 if (!h || !h->htable) 188 return NULL; 189 hvalue = avtab_hash(key, h->mask); 190 for (prev = NULL, cur = h->htable[hvalue]; 191 cur; prev = cur, cur = cur->next) { 192 if (key->source_type == cur->key.source_type && 193 key->target_type == cur->key.target_type && 194 key->target_class == cur->key.target_class && 195 (specified & cur->key.specified)) 196 break; 197 if (key->source_type < cur->key.source_type) 198 break; 199 if (key->source_type == cur->key.source_type && 200 key->target_type < cur->key.target_type) 201 break; 202 if (key->source_type == cur->key.source_type && 203 key->target_type == cur->key.target_type && 204 key->target_class < cur->key.target_class) 205 break; 206 } 207 newnode = avtab_insert_node(h, hvalue, prev, key, datum); 208 209 return newnode; 210 } 211 212 avtab_datum_t *avtab_search(avtab_t * h, avtab_key_t * key) 213 { 214 int hvalue; 215 avtab_ptr_t cur; 216 uint16_t specified = 217 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 218 219 if (!h || !h->htable) 220 return NULL; 221 222 hvalue = avtab_hash(key, h->mask); 223 for (cur = h->htable[hvalue]; cur; cur = cur->next) { 224 if (key->source_type == cur->key.source_type && 225 key->target_type == cur->key.target_type && 226 key->target_class == cur->key.target_class && 227 (specified & cur->key.specified)) 228 return &cur->datum; 229 230 if (key->source_type < cur->key.source_type) 231 break; 232 if (key->source_type == cur->key.source_type && 233 key->target_type < cur->key.target_type) 234 break; 235 if (key->source_type == cur->key.source_type && 236 key->target_type == cur->key.target_type && 237 key->target_class < cur->key.target_class) 238 break; 239 } 240 241 return NULL; 242 } 243 244 /* This search function returns a node pointer, and can be used in 245 * conjunction with avtab_search_next_node() 246 */ 247 avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key) 248 { 249 int hvalue; 250 avtab_ptr_t cur; 251 uint16_t specified = 252 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 253 254 if (!h || !h->htable) 255 return NULL; 256 257 hvalue = avtab_hash(key, h->mask); 258 for (cur = h->htable[hvalue]; cur; cur = cur->next) { 259 if (key->source_type == cur->key.source_type && 260 key->target_type == cur->key.target_type && 261 key->target_class == cur->key.target_class && 262 (specified & cur->key.specified)) 263 return cur; 264 265 if (key->source_type < cur->key.source_type) 266 break; 267 if (key->source_type == cur->key.source_type && 268 key->target_type < cur->key.target_type) 269 break; 270 if (key->source_type == cur->key.source_type && 271 key->target_type == cur->key.target_type && 272 key->target_class < cur->key.target_class) 273 break; 274 } 275 return NULL; 276 } 277 278 avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified) 279 { 280 avtab_ptr_t cur; 281 282 if (!node) 283 return NULL; 284 285 specified &= ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 286 for (cur = node->next; cur; cur = cur->next) { 287 if (node->key.source_type == cur->key.source_type && 288 node->key.target_type == cur->key.target_type && 289 node->key.target_class == cur->key.target_class && 290 (specified & cur->key.specified)) 291 return cur; 292 293 if (node->key.source_type < cur->key.source_type) 294 break; 295 if (node->key.source_type == cur->key.source_type && 296 node->key.target_type < cur->key.target_type) 297 break; 298 if (node->key.source_type == cur->key.source_type && 299 node->key.target_type == cur->key.target_type && 300 node->key.target_class < cur->key.target_class) 301 break; 302 } 303 return NULL; 304 } 305 306 void avtab_destroy(avtab_t * h) 307 { 308 unsigned int i; 309 avtab_ptr_t cur, temp; 310 311 if (!h || !h->htable) 312 return; 313 314 for (i = 0; i < h->nslot; i++) { 315 cur = h->htable[i]; 316 while (cur != NULL) { 317 if (cur->key.specified & AVTAB_XPERMS) { 318 free(cur->datum.xperms); 319 } 320 temp = cur; 321 cur = cur->next; 322 free(temp); 323 } 324 h->htable[i] = NULL; 325 } 326 free(h->htable); 327 h->htable = NULL; 328 h->nslot = 0; 329 h->mask = 0; 330 } 331 332 int avtab_map(avtab_t * h, 333 int (*apply) (avtab_key_t * k, 334 avtab_datum_t * d, void *args), void *args) 335 { 336 unsigned int i; 337 int ret; 338 avtab_ptr_t cur; 339 340 if (!h) 341 return 0; 342 343 for (i = 0; i < h->nslot; i++) { 344 cur = h->htable[i]; 345 while (cur != NULL) { 346 ret = apply(&cur->key, &cur->datum, args); 347 if (ret) 348 return ret; 349 cur = cur->next; 350 } 351 } 352 return 0; 353 } 354 355 int avtab_init(avtab_t * h) 356 { 357 h->htable = NULL; 358 h->nel = 0; 359 return 0; 360 } 361 362 int avtab_alloc(avtab_t *h, uint32_t nrules) 363 { 364 uint32_t mask = 0; 365 uint32_t shift = 0; 366 uint32_t work = nrules; 367 uint32_t nslot = 0; 368 369 if (nrules == 0) 370 goto out; 371 372 while (work) { 373 work = work >> 1; 374 shift++; 375 } 376 if (shift > 2) 377 shift = shift - 2; 378 nslot = 1 << shift; 379 if (nslot > MAX_AVTAB_HASH_BUCKETS) 380 nslot = MAX_AVTAB_HASH_BUCKETS; 381 mask = nslot - 1; 382 383 h->htable = calloc(nslot, sizeof(avtab_ptr_t)); 384 if (!h->htable) 385 return -1; 386 out: 387 h->nel = 0; 388 h->nslot = nslot; 389 h->mask = mask; 390 return 0; 391 } 392 393 void avtab_hash_eval(avtab_t * h, char *tag) 394 { 395 unsigned int i, chain_len, slots_used, max_chain_len; 396 avtab_ptr_t cur; 397 398 slots_used = 0; 399 max_chain_len = 0; 400 for (i = 0; i < h->nslot; i++) { 401 cur = h->htable[i]; 402 if (cur) { 403 slots_used++; 404 chain_len = 0; 405 while (cur) { 406 chain_len++; 407 cur = cur->next; 408 } 409 410 if (chain_len > max_chain_len) 411 max_chain_len = chain_len; 412 } 413 } 414 415 printf 416 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n", 417 tag, h->nel, slots_used, h->nslot, max_chain_len); 418 } 419 420 /* Ordering of datums in the original avtab format in the policy file. */ 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 policy_file *fp, uint32_t vers, avtab_t * a, 434 int (*insertf) (avtab_t * a, avtab_key_t * k, 435 avtab_datum_t * d, void *p), void *p) 436 { 437 uint8_t buf8; 438 uint16_t buf16[4], enabled; 439 uint32_t buf32[8], items, items2, val; 440 avtab_key_t key; 441 avtab_datum_t datum; 442 avtab_extended_perms_t xperms; 443 unsigned set; 444 unsigned int i; 445 int rc; 446 447 memset(&key, 0, sizeof(avtab_key_t)); 448 memset(&datum, 0, sizeof(avtab_datum_t)); 449 memset(&xperms, 0, sizeof(avtab_extended_perms_t)); 450 451 if (vers < POLICYDB_VERSION_AVTAB) { 452 rc = next_entry(buf32, fp, sizeof(uint32_t)); 453 if (rc < 0) { 454 ERR(fp->handle, "truncated entry"); 455 return -1; 456 } 457 items2 = le32_to_cpu(buf32[0]); 458 459 if (items2 < 5 || items2 > ARRAY_SIZE(buf32)) { 460 ERR(fp->handle, "invalid item count"); 461 return -1; 462 } 463 464 rc = next_entry(buf32, fp, sizeof(uint32_t) * items2); 465 if (rc < 0) { 466 ERR(fp->handle, "truncated entry"); 467 return -1; 468 } 469 470 items = 0; 471 val = le32_to_cpu(buf32[items++]); 472 key.source_type = (uint16_t) val; 473 if (key.source_type != val) { 474 ERR(fp->handle, "truncated source type"); 475 return -1; 476 } 477 val = le32_to_cpu(buf32[items++]); 478 key.target_type = (uint16_t) val; 479 if (key.target_type != val) { 480 ERR(fp->handle, "truncated target type"); 481 return -1; 482 } 483 val = le32_to_cpu(buf32[items++]); 484 key.target_class = (uint16_t) val; 485 if (key.target_class != val) { 486 ERR(fp->handle, "truncated target class"); 487 return -1; 488 } 489 490 val = le32_to_cpu(buf32[items++]); 491 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0; 492 493 if (!(val & (AVTAB_AV | AVTAB_TYPE))) { 494 ERR(fp->handle, "null entry"); 495 return -1; 496 } 497 if ((val & AVTAB_AV) && (val & AVTAB_TYPE)) { 498 ERR(fp->handle, "entry has both access " 499 "vectors and types"); 500 return -1; 501 } 502 503 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 504 if (val & spec_order[i]) { 505 key.specified = spec_order[i] | enabled; 506 datum.data = le32_to_cpu(buf32[items++]); 507 rc = insertf(a, &key, &datum, p); 508 if (rc) 509 return rc; 510 } 511 } 512 513 if (items != items2) { 514 ERR(fp->handle, "entry only had %d items, " 515 "expected %d", items2, items); 516 return -1; 517 } 518 return 0; 519 } 520 521 rc = next_entry(buf16, fp, sizeof(uint16_t) * 4); 522 if (rc < 0) { 523 ERR(fp->handle, "truncated entry"); 524 return -1; 525 } 526 items = 0; 527 key.source_type = le16_to_cpu(buf16[items++]); 528 key.target_type = le16_to_cpu(buf16[items++]); 529 key.target_class = le16_to_cpu(buf16[items++]); 530 key.specified = le16_to_cpu(buf16[items++]); 531 532 set = 0; 533 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 534 if (key.specified & spec_order[i]) 535 set++; 536 } 537 if (!set || set > 1) { 538 ERR(fp->handle, "more than one specifier"); 539 return -1; 540 } 541 542 if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) && 543 (key.specified & AVTAB_XPERMS)) { 544 ERR(fp->handle, "policy version %u does not support extended " 545 "permissions rules and one was specified\n", vers); 546 return -1; 547 } else if (key.specified & AVTAB_XPERMS) { 548 rc = next_entry(&buf8, fp, sizeof(uint8_t)); 549 if (rc < 0) { 550 ERR(fp->handle, "truncated entry"); 551 return -1; 552 } 553 xperms.specified = buf8; 554 rc = next_entry(&buf8, fp, sizeof(uint8_t)); 555 if (rc < 0) { 556 ERR(fp->handle, "truncated entry"); 557 return -1; 558 } 559 xperms.driver = buf8; 560 rc = next_entry(buf32, fp, sizeof(uint32_t)*8); 561 if (rc < 0) { 562 ERR(fp->handle, "truncated entry"); 563 return -1; 564 } 565 for (i = 0; i < ARRAY_SIZE(xperms.perms); i++) 566 xperms.perms[i] = le32_to_cpu(buf32[i]); 567 datum.xperms = &xperms; 568 } else { 569 rc = next_entry(buf32, fp, sizeof(uint32_t)); 570 if (rc < 0) { 571 ERR(fp->handle, "truncated entry"); 572 return -1; 573 } 574 datum.data = le32_to_cpu(*buf32); 575 } 576 return insertf(a, &key, &datum, p); 577 } 578 579 static int avtab_insertf(avtab_t * a, avtab_key_t * k, avtab_datum_t * d, 580 void *p __attribute__ ((unused))) 581 { 582 return avtab_insert(a, k, d); 583 } 584 585 int avtab_read(avtab_t * a, struct policy_file *fp, uint32_t vers) 586 { 587 unsigned int i; 588 int rc; 589 uint32_t buf[1]; 590 uint32_t nel; 591 592 rc = next_entry(buf, fp, sizeof(uint32_t)); 593 if (rc < 0) { 594 ERR(fp->handle, "truncated table"); 595 goto bad; 596 } 597 nel = le32_to_cpu(buf[0]); 598 if (!nel) { 599 ERR(fp->handle, "table is empty"); 600 goto bad; 601 } 602 603 rc = avtab_alloc(a, nel); 604 if (rc) { 605 ERR(fp->handle, "out of memory"); 606 goto bad; 607 } 608 609 for (i = 0; i < nel; i++) { 610 rc = avtab_read_item(fp, vers, a, avtab_insertf, NULL); 611 if (rc) { 612 if (rc == SEPOL_ENOMEM) 613 ERR(fp->handle, "out of memory"); 614 if (rc == SEPOL_EEXIST) 615 ERR(fp->handle, "duplicate entry"); 616 ERR(fp->handle, "failed on entry %d of %u", i, nel); 617 goto bad; 618 } 619 } 620 621 return 0; 622 623 bad: 624 avtab_destroy(a); 625 return -1; 626 } 627
