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