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 17 #include <linux/kernel.h> 18 #include <linux/slab.h> 19 #include <linux/vmalloc.h> 20 #include <linux/errno.h> 21 22 #include "avtab.h" 23 #include "policydb.h" 24 25 #define AVTAB_HASH(keyp) \ 26 ((keyp->target_class + \ 27 (keyp->target_type << 2) + \ 28 (keyp->source_type << 9)) & \ 29 AVTAB_HASH_MASK) 30 31 static kmem_cache_t *avtab_node_cachep; 32 33 static struct avtab_node* 34 avtab_insert_node(struct avtab *h, int hvalue, 35 struct avtab_node * prev, struct avtab_node * cur, 36 struct avtab_key *key, struct avtab_datum *datum) 37 { 38 struct avtab_node * newnode; 39 newnode = kmem_cache_alloc(avtab_node_cachep, SLAB_KERNEL); 40 if (newnode == NULL) 41 return NULL; 42 memset(newnode, 0, sizeof(struct avtab_node)); 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 57 static 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) 64 return -EINVAL; 65 66 hvalue = AVTAB_HASH(key); 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 */ 97 struct avtab_node * 98 avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_datum * datum) 99 { 100 int hvalue; 101 struct avtab_node *prev, *cur, *newnode; 102 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 103 104 if (!h) 105 return NULL; 106 hvalue = AVTAB_HASH(key); 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 newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum); 126 127 return newnode; 128 } 129 130 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key) 131 { 132 int hvalue; 133 struct avtab_node *cur; 134 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 135 136 if (!h) 137 return NULL; 138 139 hvalue = AVTAB_HASH(key); 140 for (cur = h->htable[hvalue]; cur; cur = cur->next) { 141 if (key->source_type == cur->key.source_type && 142 key->target_type == cur->key.target_type && 143 key->target_class == cur->key.target_class && 144 (specified & cur->key.specified)) 145 return &cur->datum; 146 147 if (key->source_type < cur->key.source_type) 148 break; 149 if (key->source_type == cur->key.source_type && 150 key->target_type < cur->key.target_type) 151 break; 152 if (key->source_type == cur->key.source_type && 153 key->target_type == cur->key.target_type && 154 key->target_class < cur->key.target_class) 155 break; 156 } 157 158 return NULL; 159 } 160 161 /* This search function returns a node pointer, and can be used in 162 * conjunction with avtab_search_next_node() 163 */ 164 struct avtab_node* 165 avtab_search_node(struct avtab *h, struct avtab_key *key) 166 { 167 int hvalue; 168 struct avtab_node *cur; 169 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 170 171 if (!h) 172 return NULL; 173 174 hvalue = AVTAB_HASH(key); 175 for (cur = h->htable[hvalue]; cur; cur = cur->next) { 176 if (key->source_type == cur->key.source_type && 177 key->target_type == cur->key.target_type && 178 key->target_class == cur->key.target_class && 179 (specified & cur->key.specified)) 180 return cur; 181 182 if (key->source_type < cur->key.source_type) 183 break; 184 if (key->source_type == cur->key.source_type && 185 key->target_type < cur->key.target_type) 186 break; 187 if (key->source_type == cur->key.source_type && 188 key->target_type == cur->key.target_type && 189 key->target_class < cur->key.target_class) 190 break; 191 } 192 return NULL; 193 } 194 195 struct avtab_node* 196 avtab_search_node_next(struct avtab_node *node, int specified) 197 { 198 struct avtab_node *cur; 199 200 if (!node) 201 return NULL; 202 203 specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 204 for (cur = node->next; cur; cur = cur->next) { 205 if (node->key.source_type == cur->key.source_type && 206 node->key.target_type == cur->key.target_type && 207 node->key.target_class == cur->key.target_class && 208 (specified & cur->key.specified)) 209 return cur; 210 211 if (node->key.source_type < cur->key.source_type) 212 break; 213 if (node->key.source_type == cur->key.source_type && 214 node->key.target_type < cur->key.target_type) 215 break; 216 if (node->key.source_type == cur->key.source_type && 217 node->key.target_type == cur->key.target_type && 218 node->key.target_class < cur->key.target_class) 219 break; 220 } 221 return NULL; 222 } 223 224 void avtab_destroy(struct avtab *h) 225 { 226 int i; 227 struct avtab_node *cur, *temp; 228 229 if (!h || !h->htable) 230 return; 231 232 for (i = 0; i < AVTAB_SIZE; i++) { 233 cur = h->htable[i]; 234 while (cur != NULL) { 235 temp = cur; 236 cur = cur->next; 237 kmem_cache_free(avtab_node_cachep, temp); 238 } 239 h->htable[i] = NULL; 240 } 241 vfree(h->htable); 242 h->htable = NULL; 243 } 244 245 246 int avtab_init(struct avtab *h) 247 { 248 int i; 249 250 h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE); 251 if (!h->htable) 252 return -ENOMEM; 253 for (i = 0; i < AVTAB_SIZE; i++) 254 h->htable[i] = NULL; 255 h->nel = 0; 256 return 0; 257 } 258 259 void avtab_hash_eval(struct avtab *h, char *tag) 260 { 261 int i, chain_len, slots_used, max_chain_len; 262 struct avtab_node *cur; 263 264 slots_used = 0; 265 max_chain_len = 0; 266 for (i = 0; i < AVTAB_SIZE; i++) { 267 cur = h->htable[i]; 268 if (cur) { 269 slots_used++; 270 chain_len = 0; 271 while (cur) { 272 chain_len++; 273 cur = cur->next; 274 } 275 276 if (chain_len > max_chain_len) 277 max_chain_len = chain_len; 278 } 279 } 280 281 printk(KERN_INFO "%s: %d entries and %d/%d buckets used, longest " 282 "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE, 283 max_chain_len); 284 } 285 286 static uint16_t spec_order[] = { 287 AVTAB_ALLOWED, 288 AVTAB_AUDITDENY, 289 AVTAB_AUDITALLOW, 290 AVTAB_TRANSITION, 291 AVTAB_CHANGE, 292 AVTAB_MEMBER 293 }; 294 295 int avtab_read_item(void *fp, u32 vers, struct avtab *a, 296 int (*insertf)(struct avtab *a, struct avtab_key *k, 297 struct avtab_datum *d, void *p), 298 void *p) 299 { 300 __le16 buf16[4]; 301 u16 enabled; 302 __le32 buf32[7]; 303 u32 items, items2, val; 304 struct avtab_key key; 305 struct avtab_datum datum; 306 int i, rc; 307 308 memset(&key, 0, sizeof(struct avtab_key)); 309 memset(&datum, 0, sizeof(struct avtab_datum)); 310 311 if (vers < POLICYDB_VERSION_AVTAB) { 312 rc = next_entry(buf32, fp, sizeof(u32)); 313 if (rc < 0) { 314 printk(KERN_ERR "security: avtab: truncated entry\n"); 315 return -1; 316 } 317 items2 = le32_to_cpu(buf32[0]); 318 if (items2 > ARRAY_SIZE(buf32)) { 319 printk(KERN_ERR "security: avtab: entry overflow\n"); 320 return -1; 321 322 } 323 rc = next_entry(buf32, fp, sizeof(u32)*items2); 324 if (rc < 0) { 325 printk(KERN_ERR "security: avtab: truncated entry\n"); 326 return -1; 327 } 328 items = 0; 329 330 val = le32_to_cpu(buf32[items++]); 331 key.source_type = (u16)val; 332 if (key.source_type != val) { 333 printk("security: avtab: truncated source type\n"); 334 return -1; 335 } 336 val = le32_to_cpu(buf32[items++]); 337 key.target_type = (u16)val; 338 if (key.target_type != val) { 339 printk("security: avtab: truncated target type\n"); 340 return -1; 341 } 342 val = le32_to_cpu(buf32[items++]); 343 key.target_class = (u16)val; 344 if (key.target_class != val) { 345 printk("security: avtab: truncated target class\n"); 346 return -1; 347 } 348 349 val = le32_to_cpu(buf32[items++]); 350 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0; 351 352 if (!(val & (AVTAB_AV | AVTAB_TYPE))) { 353 printk("security: avtab: null entry\n"); 354 return -1; 355 } 356 if ((val & AVTAB_AV) && 357 (val & AVTAB_TYPE)) { 358 printk("security: avtab: entry has both access vectors and types\n"); 359 return -1; 360 } 361 362 for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 363 if (val & spec_order[i]) { 364 key.specified = spec_order[i] | enabled; 365 datum.data = le32_to_cpu(buf32[items++]); 366 rc = insertf(a, &key, &datum, p); 367 if (rc) return rc; 368 } 369 } 370 371 if (items != items2) { 372 printk("security: avtab: entry only had %d items, expected %d\n", items2, items); 373 return -1; 374 } 375 return 0; 376 } 377 378 rc = next_entry(buf16, fp, sizeof(u16)*4); 379 if (rc < 0) { 380 printk("security: avtab: truncated entry\n"); 381 return -1; 382 } 383 384 items = 0; 385 key.source_type = le16_to_cpu(buf16[items++]); 386 key.target_type = le16_to_cpu(buf16[items++]); 387 key.target_class = le16_to_cpu(buf16[items++]); 388 key.specified = le16_to_cpu(buf16[items++]); 389 390 rc = next_entry(buf32, fp, sizeof(u32)); 391 if (rc < 0) { 392 printk("security: avtab: truncated entry\n"); 393 return -1; 394 } 395 datum.data = le32_to_cpu(*buf32); 396 return insertf(a, &key, &datum, p); 397 } 398 399 static int avtab_insertf(struct avtab *a, struct avtab_key *k, 400 struct avtab_datum *d, void *p) 401 { 402 return avtab_insert(a, k, d); 403 } 404 405 int avtab_read(struct avtab *a, void *fp, u32 vers) 406 { 407 int rc; 408 __le32 buf[1]; 409 u32 nel, i; 410 411 412 rc = next_entry(buf, fp, sizeof(u32)); 413 if (rc < 0) { 414 printk(KERN_ERR "security: avtab: truncated table\n"); 415 goto bad; 416 } 417 nel = le32_to_cpu(buf[0]); 418 if (!nel) { 419 printk(KERN_ERR "security: avtab: table is empty\n"); 420 rc = -EINVAL; 421 goto bad; 422 } 423 for (i = 0; i < nel; i++) { 424 rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL); 425 if (rc) { 426 if (rc == -ENOMEM) 427 printk(KERN_ERR "security: avtab: out of memory\n"); 428 else if (rc == -EEXIST) 429 printk(KERN_ERR "security: avtab: duplicate entry\n"); 430 else 431 rc = -EINVAL; 432 goto bad; 433 } 434 } 435 436 rc = 0; 437 out: 438 return rc; 439 440 bad: 441 avtab_destroy(a); 442 goto out; 443 } 444 445 void avtab_cache_init(void) 446 { 447 avtab_node_cachep = kmem_cache_create("avtab_node", 448 sizeof(struct avtab_node), 449 0, SLAB_PANIC, NULL, NULL); 450 } 451 452 void avtab_cache_destroy(void) 453 { 454 kmem_cache_destroy (avtab_node_cachep); 455 } 456