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