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 static inline int avtab_hash(struct avtab_key *keyp, uint16_t mask) 53 { 54 return ((keyp->target_class + (keyp->target_type << 2) + 55 (keyp->source_type << 9)) & mask); 56 } 57 58 static avtab_ptr_t 59 avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key, 60 avtab_datum_t * datum) 61 { 62 avtab_ptr_t newnode; 63 newnode = (avtab_ptr_t) malloc(sizeof(struct avtab_node)); 64 if (newnode == NULL) 65 return NULL; 66 memset(newnode, 0, sizeof(struct avtab_node)); 67 newnode->key = *key; 68 newnode->datum = *datum; 69 if (prev) { 70 newnode->next = prev->next; 71 prev->next = newnode; 72 } else { 73 newnode->next = h->htable[hvalue]; 74 h->htable[hvalue] = newnode; 75 } 76 77 h->nel++; 78 return newnode; 79 } 80 81 int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum) 82 { 83 int hvalue; 84 avtab_ptr_t prev, cur, newnode; 85 uint16_t specified = 86 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 87 88 if (!h || !h->htable) 89 return SEPOL_ENOMEM; 90 91 hvalue = avtab_hash(key, h->mask); 92 for (prev = NULL, cur = h->htable[hvalue]; 93 cur; prev = cur, cur = cur->next) { 94 if (key->source_type == cur->key.source_type && 95 key->target_type == cur->key.target_type && 96 key->target_class == cur->key.target_class && 97 (specified & cur->key.specified)) 98 return SEPOL_EEXIST; 99 if (key->source_type < cur->key.source_type) 100 break; 101 if (key->source_type == cur->key.source_type && 102 key->target_type < cur->key.target_type) 103 break; 104 if (key->source_type == cur->key.source_type && 105 key->target_type == cur->key.target_type && 106 key->target_class < cur->key.target_class) 107 break; 108 } 109 110 newnode = avtab_insert_node(h, hvalue, prev, key, datum); 111 if (!newnode) 112 return SEPOL_ENOMEM; 113 114 return 0; 115 } 116 117 /* Unlike avtab_insert(), this function allow multiple insertions of the same 118 * key/specified mask into the table, as needed by the conditional avtab. 119 * It also returns a pointer to the node inserted. 120 */ 121 avtab_ptr_t 122 avtab_insert_nonunique(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum) 123 { 124 int hvalue; 125 avtab_ptr_t prev, cur, newnode; 126 uint16_t specified = 127 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 128 129 if (!h || !h->htable) 130 return NULL; 131 hvalue = avtab_hash(key, h->mask); 132 for (prev = NULL, cur = h->htable[hvalue]; 133 cur; prev = cur, cur = cur->next) { 134 if (key->source_type == cur->key.source_type && 135 key->target_type == cur->key.target_type && 136 key->target_class == cur->key.target_class && 137 (specified & cur->key.specified)) 138 break; 139 if (key->source_type < cur->key.source_type) 140 break; 141 if (key->source_type == cur->key.source_type && 142 key->target_type < cur->key.target_type) 143 break; 144 if (key->source_type == cur->key.source_type && 145 key->target_type == cur->key.target_type && 146 key->target_class < cur->key.target_class) 147 break; 148 } 149 newnode = avtab_insert_node(h, hvalue, prev, key, datum); 150 151 return newnode; 152 } 153 154 avtab_datum_t *avtab_search(avtab_t * h, avtab_key_t * key) 155 { 156 int hvalue; 157 avtab_ptr_t cur; 158 uint16_t specified = 159 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 160 161 if (!h || !h->htable) 162 return NULL; 163 164 hvalue = avtab_hash(key, h->mask); 165 for (cur = h->htable[hvalue]; cur; cur = cur->next) { 166 if (key->source_type == cur->key.source_type && 167 key->target_type == cur->key.target_type && 168 key->target_class == cur->key.target_class && 169 (specified & cur->key.specified)) 170 return &cur->datum; 171 172 if (key->source_type < cur->key.source_type) 173 break; 174 if (key->source_type == cur->key.source_type && 175 key->target_type < cur->key.target_type) 176 break; 177 if (key->source_type == cur->key.source_type && 178 key->target_type == cur->key.target_type && 179 key->target_class < cur->key.target_class) 180 break; 181 } 182 183 return NULL; 184 } 185 186 /* This search function returns a node pointer, and can be used in 187 * conjunction with avtab_search_next_node() 188 */ 189 avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key) 190 { 191 int hvalue; 192 avtab_ptr_t cur; 193 uint16_t specified = 194 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 195 196 if (!h || !h->htable) 197 return NULL; 198 199 hvalue = avtab_hash(key, h->mask); 200 for (cur = h->htable[hvalue]; cur; cur = cur->next) { 201 if (key->source_type == cur->key.source_type && 202 key->target_type == cur->key.target_type && 203 key->target_class == cur->key.target_class && 204 (specified & cur->key.specified)) 205 return cur; 206 207 if (key->source_type < cur->key.source_type) 208 break; 209 if (key->source_type == cur->key.source_type && 210 key->target_type < cur->key.target_type) 211 break; 212 if (key->source_type == cur->key.source_type && 213 key->target_type == cur->key.target_type && 214 key->target_class < cur->key.target_class) 215 break; 216 } 217 return NULL; 218 } 219 220 avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified) 221 { 222 avtab_ptr_t cur; 223 224 if (!node) 225 return NULL; 226 227 specified &= ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD); 228 for (cur = node->next; cur; cur = cur->next) { 229 if (node->key.source_type == cur->key.source_type && 230 node->key.target_type == cur->key.target_type && 231 node->key.target_class == cur->key.target_class && 232 (specified & cur->key.specified)) 233 return cur; 234 235 if (node->key.source_type < cur->key.source_type) 236 break; 237 if (node->key.source_type == cur->key.source_type && 238 node->key.target_type < cur->key.target_type) 239 break; 240 if (node->key.source_type == cur->key.source_type && 241 node->key.target_type == cur->key.target_type && 242 node->key.target_class < cur->key.target_class) 243 break; 244 } 245 return NULL; 246 } 247 248 void avtab_destroy(avtab_t * h) 249 { 250 unsigned int i; 251 avtab_ptr_t cur, temp; 252 253 if (!h || !h->htable) 254 return; 255 256 for (i = 0; i < h->nslot; i++) { 257 cur = h->htable[i]; 258 while (cur != NULL) { 259 temp = cur; 260 cur = cur->next; 261 free(temp); 262 } 263 h->htable[i] = NULL; 264 } 265 free(h->htable); 266 h->htable = NULL; 267 h->nslot = 0; 268 h->mask = 0; 269 } 270 271 int avtab_map(avtab_t * h, 272 int (*apply) (avtab_key_t * k, 273 avtab_datum_t * d, void *args), void *args) 274 { 275 unsigned int i; 276 int ret; 277 avtab_ptr_t cur; 278 279 if (!h) 280 return 0; 281 282 for (i = 0; i < h->nslot; i++) { 283 cur = h->htable[i]; 284 while (cur != NULL) { 285 ret = apply(&cur->key, &cur->datum, args); 286 if (ret) 287 return ret; 288 cur = cur->next; 289 } 290 } 291 return 0; 292 } 293 294 int avtab_init(avtab_t * h) 295 { 296 h->htable = NULL; 297 h->nel = 0; 298 return 0; 299 } 300 301 int avtab_alloc(avtab_t *h, uint32_t nrules) 302 { 303 uint16_t mask = 0; 304 uint32_t shift = 0; 305 uint32_t work = nrules; 306 uint32_t nslot = 0; 307 308 if (nrules == 0) 309 goto out; 310 311 while (work) { 312 work = work >> 1; 313 shift++; 314 } 315 if (shift > 2) 316 shift = shift - 2; 317 nslot = 1 << shift; 318 if (nslot > MAX_AVTAB_SIZE) 319 nslot = MAX_AVTAB_SIZE; 320 mask = nslot - 1; 321 322 h->htable = calloc(nslot, sizeof(avtab_ptr_t)); 323 if (!h->htable) 324 return -1; 325 out: 326 h->nel = 0; 327 h->nslot = nslot; 328 h->mask = mask; 329 return 0; 330 } 331 332 void avtab_hash_eval(avtab_t * h, char *tag) 333 { 334 unsigned int i, chain_len, slots_used, max_chain_len; 335 avtab_ptr_t cur; 336 337 slots_used = 0; 338 max_chain_len = 0; 339 for (i = 0; i < h->nslot; i++) { 340 cur = h->htable[i]; 341 if (cur) { 342 slots_used++; 343 chain_len = 0; 344 while (cur) { 345 chain_len++; 346 cur = cur->next; 347 } 348 349 if (chain_len > max_chain_len) 350 max_chain_len = chain_len; 351 } 352 } 353 354 printf 355 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n", 356 tag, h->nel, slots_used, h->nslot, max_chain_len); 357 } 358 359 /* Ordering of datums in the original avtab format in the policy file. */ 360 static uint16_t spec_order[] = { 361 AVTAB_ALLOWED, 362 AVTAB_AUDITDENY, 363 AVTAB_AUDITALLOW, 364 AVTAB_TRANSITION, 365 AVTAB_CHANGE, 366 AVTAB_MEMBER 367 }; 368 369 int avtab_read_item(struct policy_file *fp, uint32_t vers, avtab_t * a, 370 int (*insertf) (avtab_t * a, avtab_key_t * k, 371 avtab_datum_t * d, void *p), void *p) 372 { 373 uint16_t buf16[4], enabled; 374 uint32_t buf32[7], items, items2, val; 375 avtab_key_t key; 376 avtab_datum_t datum; 377 unsigned set; 378 unsigned int i; 379 int rc; 380 381 memset(&key, 0, sizeof(avtab_key_t)); 382 memset(&datum, 0, sizeof(avtab_datum_t)); 383 384 if (vers < POLICYDB_VERSION_AVTAB) { 385 rc = next_entry(buf32, fp, sizeof(uint32_t)); 386 if (rc < 0) { 387 ERR(fp->handle, "truncated entry"); 388 return -1; 389 } 390 items2 = le32_to_cpu(buf32[0]); 391 392 if (items2 < 5 || items2 > ARRAY_SIZE(buf32)) { 393 ERR(fp->handle, "invalid item count"); 394 return -1; 395 } 396 397 rc = next_entry(buf32, fp, sizeof(uint32_t) * items2); 398 if (rc < 0) { 399 ERR(fp->handle, "truncated entry"); 400 return -1; 401 } 402 403 items = 0; 404 val = le32_to_cpu(buf32[items++]); 405 key.source_type = (uint16_t) val; 406 if (key.source_type != val) { 407 ERR(fp->handle, "truncated source type"); 408 return -1; 409 } 410 val = le32_to_cpu(buf32[items++]); 411 key.target_type = (uint16_t) val; 412 if (key.target_type != val) { 413 ERR(fp->handle, "truncated target type"); 414 return -1; 415 } 416 val = le32_to_cpu(buf32[items++]); 417 key.target_class = (uint16_t) val; 418 if (key.target_class != val) { 419 ERR(fp->handle, "truncated target class"); 420 return -1; 421 } 422 423 val = le32_to_cpu(buf32[items++]); 424 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0; 425 426 if (!(val & (AVTAB_AV | AVTAB_TYPE))) { 427 ERR(fp->handle, "null entry"); 428 return -1; 429 } 430 if ((val & AVTAB_AV) && (val & AVTAB_TYPE)) { 431 ERR(fp->handle, "entry has both access " 432 "vectors and types"); 433 return -1; 434 } 435 436 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 437 if (val & spec_order[i]) { 438 key.specified = spec_order[i] | enabled; 439 datum.data = le32_to_cpu(buf32[items++]); 440 rc = insertf(a, &key, &datum, p); 441 if (rc) 442 return rc; 443 } 444 } 445 446 if (items != items2) { 447 ERR(fp->handle, "entry only had %d items, " 448 "expected %d", items2, items); 449 return -1; 450 } 451 return 0; 452 } 453 454 rc = next_entry(buf16, fp, sizeof(uint16_t) * 4); 455 if (rc < 0) { 456 ERR(fp->handle, "truncated entry"); 457 return -1; 458 } 459 items = 0; 460 key.source_type = le16_to_cpu(buf16[items++]); 461 key.target_type = le16_to_cpu(buf16[items++]); 462 key.target_class = le16_to_cpu(buf16[items++]); 463 key.specified = le16_to_cpu(buf16[items++]); 464 465 set = 0; 466 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 467 if (key.specified & spec_order[i]) 468 set++; 469 } 470 if (!set || set > 1) { 471 ERR(fp->handle, "more than one specifier"); 472 return -1; 473 } 474 475 rc = next_entry(buf32, fp, sizeof(uint32_t)); 476 if (rc < 0) { 477 ERR(fp->handle, "truncated entry"); 478 return -1; 479 } 480 datum.data = le32_to_cpu(*buf32); 481 return insertf(a, &key, &datum, p); 482 } 483 484 static int avtab_insertf(avtab_t * a, avtab_key_t * k, avtab_datum_t * d, 485 void *p __attribute__ ((unused))) 486 { 487 return avtab_insert(a, k, d); 488 } 489 490 int avtab_read(avtab_t * a, struct policy_file *fp, uint32_t vers) 491 { 492 unsigned int i; 493 int rc; 494 uint32_t buf[1]; 495 uint32_t nel; 496 497 rc = next_entry(buf, fp, sizeof(uint32_t)); 498 if (rc < 0) { 499 ERR(fp->handle, "truncated table"); 500 goto bad; 501 } 502 nel = le32_to_cpu(buf[0]); 503 if (!nel) { 504 ERR(fp->handle, "table is empty"); 505 goto bad; 506 } 507 508 rc = avtab_alloc(a, nel); 509 if (rc) { 510 ERR(fp->handle, "out of memory"); 511 goto bad; 512 } 513 514 for (i = 0; i < nel; i++) { 515 rc = avtab_read_item(fp, vers, a, avtab_insertf, NULL); 516 if (rc) { 517 if (rc == SEPOL_ENOMEM) 518 ERR(fp->handle, "out of memory"); 519 if (rc == SEPOL_EEXIST) 520 ERR(fp->handle, "duplicate entry"); 521 ERR(fp->handle, "failed on entry %d of %u", i, nel); 522 goto bad; 523 } 524 } 525 526 return 0; 527 528 bad: 529 avtab_destroy(a); 530 return -1; 531 } 532
