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