Commit | Line | Data |
---|---|---|
1da177e4 LT |
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. | |
3232c110 YN |
15 | * |
16 | * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp> | |
17 | * Tuned number of hash slots for avtab to reduce memory usage | |
1da177e4 LT |
18 | */ |
19 | ||
20 | #include <linux/kernel.h> | |
21 | #include <linux/slab.h> | |
1da177e4 | 22 | #include <linux/errno.h> |
1da177e4 LT |
23 | #include "avtab.h" |
24 | #include "policydb.h" | |
25 | ||
e18b890b | 26 | static struct kmem_cache *avtab_node_cachep; |
1da177e4 | 27 | |
3232c110 YN |
28 | static 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 | ||
1da177e4 LT |
34 | static struct avtab_node* |
35 | avtab_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; | |
c3762229 | 40 | newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL); |
1da177e4 LT |
41 | if (newnode == NULL) |
42 | return NULL; | |
1da177e4 LT |
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; | |
782ebb99 | 61 | u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); |
1da177e4 | 62 | |
3232c110 | 63 | if (!h || !h->htable) |
1da177e4 LT |
64 | return -EINVAL; |
65 | ||
3232c110 | 66 | hvalue = avtab_hash(key, h->mask); |
1da177e4 LT |
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 && | |
782ebb99 | 73 | (specified & cur->key.specified)) |
1da177e4 LT |
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; | |
782ebb99 | 102 | u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); |
1da177e4 | 103 | |
3232c110 | 104 | if (!h || !h->htable) |
1da177e4 | 105 | return NULL; |
3232c110 | 106 | hvalue = avtab_hash(key, h->mask); |
1da177e4 LT |
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 && | |
782ebb99 | 113 | (specified & cur->key.specified)) |
1da177e4 LT |
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 | ||
782ebb99 | 130 | struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key) |
1da177e4 LT |
131 | { |
132 | int hvalue; | |
133 | struct avtab_node *cur; | |
782ebb99 | 134 | u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); |
1da177e4 | 135 | |
3232c110 | 136 | if (!h || !h->htable) |
1da177e4 LT |
137 | return NULL; |
138 | ||
3232c110 | 139 | hvalue = avtab_hash(key, h->mask); |
1da177e4 LT |
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 && | |
782ebb99 | 144 | (specified & cur->key.specified)) |
1da177e4 LT |
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* | |
782ebb99 | 165 | avtab_search_node(struct avtab *h, struct avtab_key *key) |
1da177e4 LT |
166 | { |
167 | int hvalue; | |
168 | struct avtab_node *cur; | |
782ebb99 | 169 | u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); |
1da177e4 | 170 | |
3232c110 | 171 | if (!h || !h->htable) |
1da177e4 LT |
172 | return NULL; |
173 | ||
3232c110 | 174 | hvalue = avtab_hash(key, h->mask); |
1da177e4 LT |
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 && | |
782ebb99 | 179 | (specified & cur->key.specified)) |
1da177e4 LT |
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 | ||
782ebb99 | 203 | specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); |
1da177e4 LT |
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 && | |
782ebb99 | 208 | (specified & cur->key.specified)) |
1da177e4 LT |
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 | ||
3232c110 | 232 | for (i = 0; i < h->nslot; i++) { |
1da177e4 LT |
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 | } | |
3232c110 | 241 | kfree(h->htable); |
1da177e4 | 242 | h->htable = NULL; |
3232c110 YN |
243 | h->nslot = 0; |
244 | h->mask = 0; | |
1da177e4 LT |
245 | } |
246 | ||
1da177e4 LT |
247 | int avtab_init(struct avtab *h) |
248 | { | |
3232c110 YN |
249 | h->htable = NULL; |
250 | h->nel = 0; | |
251 | return 0; | |
252 | } | |
253 | ||
254 | int avtab_alloc(struct avtab *h, u32 nrules) | |
255 | { | |
256 | u16 mask = 0; | |
257 | u32 shift = 0; | |
258 | u32 work = nrules; | |
259 | u32 nslot = 0; | |
260 | ||
261 | if (nrules == 0) | |
262 | goto avtab_alloc_out; | |
1da177e4 | 263 | |
3232c110 YN |
264 | while (work) { |
265 | work = work >> 1; | |
266 | shift++; | |
267 | } | |
268 | if (shift > 2) | |
269 | shift = shift - 2; | |
270 | nslot = 1 << shift; | |
271 | if (nslot > MAX_AVTAB_SIZE) | |
272 | nslot = MAX_AVTAB_SIZE; | |
273 | mask = nslot - 1; | |
274 | ||
275 | h->htable = kcalloc(nslot, sizeof(*(h->htable)), GFP_KERNEL); | |
1da177e4 LT |
276 | if (!h->htable) |
277 | return -ENOMEM; | |
3232c110 YN |
278 | |
279 | avtab_alloc_out: | |
1da177e4 | 280 | h->nel = 0; |
3232c110 YN |
281 | h->nslot = nslot; |
282 | h->mask = mask; | |
19c5fc19 | 283 | printk(KERN_DEBUG "SELinux:%d avtab hash slots allocated. " |
3232c110 | 284 | "Num of rules:%d\n", h->nslot, nrules); |
1da177e4 LT |
285 | return 0; |
286 | } | |
287 | ||
288 | void avtab_hash_eval(struct avtab *h, char *tag) | |
289 | { | |
290 | int i, chain_len, slots_used, max_chain_len; | |
3232c110 | 291 | unsigned long long chain2_len_sum; |
1da177e4 LT |
292 | struct avtab_node *cur; |
293 | ||
294 | slots_used = 0; | |
295 | max_chain_len = 0; | |
3232c110 YN |
296 | chain2_len_sum = 0; |
297 | for (i = 0; i < h->nslot; i++) { | |
1da177e4 LT |
298 | cur = h->htable[i]; |
299 | if (cur) { | |
300 | slots_used++; | |
301 | chain_len = 0; | |
302 | while (cur) { | |
303 | chain_len++; | |
304 | cur = cur->next; | |
305 | } | |
306 | ||
307 | if (chain_len > max_chain_len) | |
308 | max_chain_len = chain_len; | |
3232c110 | 309 | chain2_len_sum += chain_len * chain_len; |
1da177e4 LT |
310 | } |
311 | } | |
312 | ||
fadcdb45 | 313 | printk(KERN_DEBUG "%s: %d entries and %d/%d buckets used, longest " |
3232c110 YN |
314 | "chain length %d sum of chain length^2 %Lu\n", |
315 | tag, h->nel, slots_used, h->nslot, max_chain_len, | |
316 | chain2_len_sum); | |
1da177e4 LT |
317 | } |
318 | ||
782ebb99 SS |
319 | static uint16_t spec_order[] = { |
320 | AVTAB_ALLOWED, | |
321 | AVTAB_AUDITDENY, | |
322 | AVTAB_AUDITALLOW, | |
323 | AVTAB_TRANSITION, | |
324 | AVTAB_CHANGE, | |
325 | AVTAB_MEMBER | |
326 | }; | |
327 | ||
45e5421e | 328 | int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, |
782ebb99 SS |
329 | int (*insertf)(struct avtab *a, struct avtab_key *k, |
330 | struct avtab_datum *d, void *p), | |
331 | void *p) | |
1da177e4 | 332 | { |
b5bf6c55 AD |
333 | __le16 buf16[4]; |
334 | u16 enabled; | |
335 | __le32 buf32[7]; | |
45e5421e | 336 | u32 items, items2, val, vers = pol->policyvers; |
782ebb99 SS |
337 | struct avtab_key key; |
338 | struct avtab_datum datum; | |
339 | int i, rc; | |
45e5421e | 340 | unsigned set; |
782ebb99 SS |
341 | |
342 | memset(&key, 0, sizeof(struct avtab_key)); | |
343 | memset(&datum, 0, sizeof(struct avtab_datum)); | |
344 | ||
345 | if (vers < POLICYDB_VERSION_AVTAB) { | |
346 | rc = next_entry(buf32, fp, sizeof(u32)); | |
347 | if (rc < 0) { | |
348 | printk(KERN_ERR "security: avtab: truncated entry\n"); | |
349 | return -1; | |
350 | } | |
351 | items2 = le32_to_cpu(buf32[0]); | |
352 | if (items2 > ARRAY_SIZE(buf32)) { | |
353 | printk(KERN_ERR "security: avtab: entry overflow\n"); | |
354 | return -1; | |
1da177e4 | 355 | |
782ebb99 SS |
356 | } |
357 | rc = next_entry(buf32, fp, sizeof(u32)*items2); | |
358 | if (rc < 0) { | |
359 | printk(KERN_ERR "security: avtab: truncated entry\n"); | |
360 | return -1; | |
361 | } | |
362 | items = 0; | |
1da177e4 | 363 | |
782ebb99 SS |
364 | val = le32_to_cpu(buf32[items++]); |
365 | key.source_type = (u16)val; | |
366 | if (key.source_type != val) { | |
367 | printk("security: avtab: truncated source type\n"); | |
368 | return -1; | |
369 | } | |
370 | val = le32_to_cpu(buf32[items++]); | |
371 | key.target_type = (u16)val; | |
372 | if (key.target_type != val) { | |
373 | printk("security: avtab: truncated target type\n"); | |
374 | return -1; | |
375 | } | |
376 | val = le32_to_cpu(buf32[items++]); | |
377 | key.target_class = (u16)val; | |
378 | if (key.target_class != val) { | |
379 | printk("security: avtab: truncated target class\n"); | |
380 | return -1; | |
381 | } | |
382 | ||
383 | val = le32_to_cpu(buf32[items++]); | |
384 | enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0; | |
385 | ||
386 | if (!(val & (AVTAB_AV | AVTAB_TYPE))) { | |
387 | printk("security: avtab: null entry\n"); | |
388 | return -1; | |
389 | } | |
390 | if ((val & AVTAB_AV) && | |
391 | (val & AVTAB_TYPE)) { | |
392 | printk("security: avtab: entry has both access vectors and types\n"); | |
393 | return -1; | |
394 | } | |
395 | ||
32725ad8 | 396 | for (i = 0; i < ARRAY_SIZE(spec_order); i++) { |
782ebb99 SS |
397 | if (val & spec_order[i]) { |
398 | key.specified = spec_order[i] | enabled; | |
399 | datum.data = le32_to_cpu(buf32[items++]); | |
400 | rc = insertf(a, &key, &datum, p); | |
401 | if (rc) return rc; | |
402 | } | |
403 | } | |
404 | ||
405 | if (items != items2) { | |
406 | printk("security: avtab: entry only had %d items, expected %d\n", items2, items); | |
407 | return -1; | |
408 | } | |
409 | return 0; | |
1da177e4 | 410 | } |
782ebb99 SS |
411 | |
412 | rc = next_entry(buf16, fp, sizeof(u16)*4); | |
1da177e4 | 413 | if (rc < 0) { |
782ebb99 SS |
414 | printk("security: avtab: truncated entry\n"); |
415 | return -1; | |
1da177e4 | 416 | } |
782ebb99 | 417 | |
1da177e4 | 418 | items = 0; |
782ebb99 SS |
419 | key.source_type = le16_to_cpu(buf16[items++]); |
420 | key.target_type = le16_to_cpu(buf16[items++]); | |
421 | key.target_class = le16_to_cpu(buf16[items++]); | |
422 | key.specified = le16_to_cpu(buf16[items++]); | |
423 | ||
45e5421e SS |
424 | if (!policydb_type_isvalid(pol, key.source_type) || |
425 | !policydb_type_isvalid(pol, key.target_type) || | |
426 | !policydb_class_isvalid(pol, key.target_class)) { | |
427 | printk(KERN_WARNING "security: avtab: invalid type or class\n"); | |
428 | return -1; | |
429 | } | |
430 | ||
431 | set = 0; | |
432 | for (i = 0; i < ARRAY_SIZE(spec_order); i++) { | |
433 | if (key.specified & spec_order[i]) | |
434 | set++; | |
435 | } | |
436 | if (!set || set > 1) { | |
437 | printk(KERN_WARNING | |
438 | "security: avtab: more than one specifier\n"); | |
439 | return -1; | |
440 | } | |
441 | ||
782ebb99 SS |
442 | rc = next_entry(buf32, fp, sizeof(u32)); |
443 | if (rc < 0) { | |
444 | printk("security: avtab: truncated entry\n"); | |
445 | return -1; | |
1da177e4 | 446 | } |
782ebb99 | 447 | datum.data = le32_to_cpu(*buf32); |
45e5421e SS |
448 | if ((key.specified & AVTAB_TYPE) && |
449 | !policydb_type_isvalid(pol, datum.data)) { | |
450 | printk(KERN_WARNING "security: avtab: invalid type\n"); | |
451 | return -1; | |
452 | } | |
782ebb99 SS |
453 | return insertf(a, &key, &datum, p); |
454 | } | |
1da177e4 | 455 | |
782ebb99 SS |
456 | static int avtab_insertf(struct avtab *a, struct avtab_key *k, |
457 | struct avtab_datum *d, void *p) | |
458 | { | |
459 | return avtab_insert(a, k, d); | |
1da177e4 LT |
460 | } |
461 | ||
45e5421e | 462 | int avtab_read(struct avtab *a, void *fp, struct policydb *pol) |
1da177e4 LT |
463 | { |
464 | int rc; | |
b5bf6c55 | 465 | __le32 buf[1]; |
1da177e4 LT |
466 | u32 nel, i; |
467 | ||
468 | ||
469 | rc = next_entry(buf, fp, sizeof(u32)); | |
470 | if (rc < 0) { | |
471 | printk(KERN_ERR "security: avtab: truncated table\n"); | |
472 | goto bad; | |
473 | } | |
474 | nel = le32_to_cpu(buf[0]); | |
475 | if (!nel) { | |
476 | printk(KERN_ERR "security: avtab: table is empty\n"); | |
477 | rc = -EINVAL; | |
478 | goto bad; | |
479 | } | |
3232c110 YN |
480 | |
481 | rc = avtab_alloc(a, nel); | |
482 | if (rc) | |
483 | goto bad; | |
484 | ||
1da177e4 | 485 | for (i = 0; i < nel; i++) { |
45e5421e | 486 | rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL); |
1da177e4 LT |
487 | if (rc) { |
488 | if (rc == -ENOMEM) | |
489 | printk(KERN_ERR "security: avtab: out of memory\n"); | |
782ebb99 | 490 | else if (rc == -EEXIST) |
1da177e4 | 491 | printk(KERN_ERR "security: avtab: duplicate entry\n"); |
782ebb99 SS |
492 | else |
493 | rc = -EINVAL; | |
1da177e4 LT |
494 | goto bad; |
495 | } | |
496 | } | |
497 | ||
498 | rc = 0; | |
499 | out: | |
500 | return rc; | |
501 | ||
502 | bad: | |
503 | avtab_destroy(a); | |
504 | goto out; | |
505 | } | |
506 | ||
507 | void avtab_cache_init(void) | |
508 | { | |
509 | avtab_node_cachep = kmem_cache_create("avtab_node", | |
510 | sizeof(struct avtab_node), | |
20c2df83 | 511 | 0, SLAB_PANIC, NULL); |
1da177e4 LT |
512 | } |
513 | ||
514 | void avtab_cache_destroy(void) | |
515 | { | |
516 | kmem_cache_destroy (avtab_node_cachep); | |
517 | } |