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 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 (datum->specified & cur->datum.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 102 if (!h) 103 return NULL; 104 hvalue = AVTAB_HASH(key); 105 for (prev = NULL, cur = h->htable[hvalue]; 106 cur; 107 prev = cur, cur = cur->next) { 108 if (key->source_type == cur->key.source_type && 109 key->target_type == cur->key.target_type && 110 key->target_class == cur->key.target_class && 111 (datum->specified & cur->datum.specified)) 112 break; 113 if (key->source_type < cur->key.source_type) 114 break; 115 if (key->source_type == cur->key.source_type && 116 key->target_type < cur->key.target_type) 117 break; 118 if (key->source_type == cur->key.source_type && 119 key->target_type == cur->key.target_type && 120 key->target_class < cur->key.target_class) 121 break; 122 } 123 newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum); 124 125 return newnode; 126 } 127 128 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key, int specified) 129 { 130 int hvalue; 131 struct avtab_node *cur; 132 133 if (!h) 134 return NULL; 135 136 hvalue = AVTAB_HASH(key); 137 for (cur = h->htable[hvalue]; cur; cur = cur->next) { 138 if (key->source_type == cur->key.source_type && 139 key->target_type == cur->key.target_type && 140 key->target_class == cur->key.target_class && 141 (specified & cur->datum.specified)) 142 return &cur->datum; 143 144 if (key->source_type < cur->key.source_type) 145 break; 146 if (key->source_type == cur->key.source_type && 147 key->target_type < cur->key.target_type) 148 break; 149 if (key->source_type == cur->key.source_type && 150 key->target_type == cur->key.target_type && 151 key->target_class < cur->key.target_class) 152 break; 153 } 154 155 return NULL; 156 } 157 158 /* This search function returns a node pointer, and can be used in 159 * conjunction with avtab_search_next_node() 160 */ 161 struct avtab_node* 162 avtab_search_node(struct avtab *h, struct avtab_key *key, int specified) 163 { 164 int hvalue; 165 struct avtab_node *cur; 166 167 if (!h) 168 return NULL; 169 170 hvalue = AVTAB_HASH(key); 171 for (cur = h->htable[hvalue]; cur; cur = cur->next) { 172 if (key->source_type == cur->key.source_type && 173 key->target_type == cur->key.target_type && 174 key->target_class == cur->key.target_class && 175 (specified & cur->datum.specified)) 176 return cur; 177 178 if (key->source_type < cur->key.source_type) 179 break; 180 if (key->source_type == cur->key.source_type && 181 key->target_type < cur->key.target_type) 182 break; 183 if (key->source_type == cur->key.source_type && 184 key->target_type == cur->key.target_type && 185 key->target_class < cur->key.target_class) 186 break; 187 } 188 return NULL; 189 } 190 191 struct avtab_node* 192 avtab_search_node_next(struct avtab_node *node, int specified) 193 { 194 struct avtab_node *cur; 195 196 if (!node) 197 return NULL; 198 199 for (cur = node->next; cur; cur = cur->next) { 200 if (node->key.source_type == cur->key.source_type && 201 node->key.target_type == cur->key.target_type && 202 node->key.target_class == cur->key.target_class && 203 (specified & cur->datum.specified)) 204 return cur; 205 206 if (node->key.source_type < cur->key.source_type) 207 break; 208 if (node->key.source_type == cur->key.source_type && 209 node->key.target_type < cur->key.target_type) 210 break; 211 if (node->key.source_type == cur->key.source_type && 212 node->key.target_type == cur->key.target_type && 213 node->key.target_class < cur->key.target_class) 214 break; 215 } 216 return NULL; 217 } 218 219 void avtab_destroy(struct avtab *h) 220 { 221 int i; 222 struct avtab_node *cur, *temp; 223 224 if (!h || !h->htable) 225 return; 226 227 for (i = 0; i < AVTAB_SIZE; i++) { 228 cur = h->htable[i]; 229 while (cur != NULL) { 230 temp = cur; 231 cur = cur->next; 232 kmem_cache_free(avtab_node_cachep, temp); 233 } 234 h->htable[i] = NULL; 235 } 236 vfree(h->htable); 237 h->htable = NULL; 238 } 239 240 241 int avtab_init(struct avtab *h) 242 { 243 int i; 244 245 h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE); 246 if (!h->htable) 247 return -ENOMEM; 248 for (i = 0; i < AVTAB_SIZE; i++) 249 h->htable[i] = NULL; 250 h->nel = 0; 251 return 0; 252 } 253 254 void avtab_hash_eval(struct avtab *h, char *tag) 255 { 256 int i, chain_len, slots_used, max_chain_len; 257 struct avtab_node *cur; 258 259 slots_used = 0; 260 max_chain_len = 0; 261 for (i = 0; i < AVTAB_SIZE; i++) { 262 cur = h->htable[i]; 263 if (cur) { 264 slots_used++; 265 chain_len = 0; 266 while (cur) { 267 chain_len++; 268 cur = cur->next; 269 } 270 271 if (chain_len > max_chain_len) 272 max_chain_len = chain_len; 273 } 274 } 275 276 printk(KERN_INFO "%s: %d entries and %d/%d buckets used, longest " 277 "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE, 278 max_chain_len); 279 } 280 281 int avtab_read_item(void *fp, struct avtab_datum *avdatum, struct avtab_key *avkey) 282 { 283 u32 buf[7]; 284 u32 items, items2; 285 int rc; 286 287 memset(avkey, 0, sizeof(struct avtab_key)); 288 memset(avdatum, 0, sizeof(struct avtab_datum)); 289 290 rc = next_entry(buf, fp, sizeof(u32)); 291 if (rc < 0) { 292 printk(KERN_ERR "security: avtab: truncated entry\n"); 293 goto bad; 294 } 295 items2 = le32_to_cpu(buf[0]); 296 if (items2 > ARRAY_SIZE(buf)) { 297 printk(KERN_ERR "security: avtab: entry overflow\n"); 298 goto bad; 299 } 300 rc = next_entry(buf, fp, sizeof(u32)*items2); 301 if (rc < 0) { 302 printk(KERN_ERR "security: avtab: truncated entry\n"); 303 goto bad; 304 } 305 items = 0; 306 avkey->source_type = le32_to_cpu(buf[items++]); 307 avkey->target_type = le32_to_cpu(buf[items++]); 308 avkey->target_class = le32_to_cpu(buf[items++]); 309 avdatum->specified = le32_to_cpu(buf[items++]); 310 if (!(avdatum->specified & (AVTAB_AV | AVTAB_TYPE))) { 311 printk(KERN_ERR "security: avtab: null entry\n"); 312 goto bad; 313 } 314 if ((avdatum->specified & AVTAB_AV) && 315 (avdatum->specified & AVTAB_TYPE)) { 316 printk(KERN_ERR "security: avtab: entry has both access vectors and types\n"); 317 goto bad; 318 } 319 if (avdatum->specified & AVTAB_AV) { 320 if (avdatum->specified & AVTAB_ALLOWED) 321 avtab_allowed(avdatum) = le32_to_cpu(buf[items++]); 322 if (avdatum->specified & AVTAB_AUDITDENY) 323 avtab_auditdeny(avdatum) = le32_to_cpu(buf[items++]); 324 if (avdatum->specified & AVTAB_AUDITALLOW) 325 avtab_auditallow(avdatum) = le32_to_cpu(buf[items++]); 326 } else { 327 if (avdatum->specified & AVTAB_TRANSITION) 328 avtab_transition(avdatum) = le32_to_cpu(buf[items++]); 329 if (avdatum->specified & AVTAB_CHANGE) 330 avtab_change(avdatum) = le32_to_cpu(buf[items++]); 331 if (avdatum->specified & AVTAB_MEMBER) 332 avtab_member(avdatum) = le32_to_cpu(buf[items++]); 333 } 334 if (items != items2) { 335 printk(KERN_ERR "security: avtab: entry only had %d items, expected %d\n", 336 items2, items); 337 goto bad; 338 } 339 340 return 0; 341 bad: 342 return -1; 343 } 344 345 int avtab_read(struct avtab *a, void *fp, u32 config) 346 { 347 int rc; 348 struct avtab_key avkey; 349 struct avtab_datum avdatum; 350 u32 buf[1]; 351 u32 nel, i; 352 353 354 rc = next_entry(buf, fp, sizeof(u32)); 355 if (rc < 0) { 356 printk(KERN_ERR "security: avtab: truncated table\n"); 357 goto bad; 358 } 359 nel = le32_to_cpu(buf[0]); 360 if (!nel) { 361 printk(KERN_ERR "security: avtab: table is empty\n"); 362 rc = -EINVAL; 363 goto bad; 364 } 365 for (i = 0; i < nel; i++) { 366 if (avtab_read_item(fp, &avdatum, &avkey)) { 367 rc = -EINVAL; 368 goto bad; 369 } 370 rc = avtab_insert(a, &avkey, &avdatum); 371 if (rc) { 372 if (rc == -ENOMEM) 373 printk(KERN_ERR "security: avtab: out of memory\n"); 374 if (rc == -EEXIST) 375 printk(KERN_ERR "security: avtab: duplicate entry\n"); 376 goto bad; 377 } 378 } 379 380 rc = 0; 381 out: 382 return rc; 383 384 bad: 385 avtab_destroy(a); 386 goto out; 387 } 388 389 void avtab_cache_init(void) 390 { 391 avtab_node_cachep = kmem_cache_create("avtab_node", 392 sizeof(struct avtab_node), 393 0, SLAB_PANIC, NULL, NULL); 394 } 395 396 void avtab_cache_destroy(void) 397 { 398 kmem_cache_destroy (avtab_node_cachep); 399 } 400