1
2 /* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
3
4 /*
5 * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
6 * Tuned number of hash slots for avtab to reduce memory usage
7 */
8
9 /* Updated: Frank Mayer <mayerf@tresys.com>
10 * and Karl MacMillan <kmacmillan@mentalrootkit.com>
11 *
12 * Added conditional policy language extensions
13 *
14 * Updated: Red Hat, Inc. James Morris <jmorris@redhat.com>
15 *
16 * Code cleanup
17 *
18 * Updated: Karl MacMillan <kmacmillan@mentalrootkit.com>
19 *
20 * Copyright (C) 2003 Tresys Technology, LLC
21 * Copyright (C) 2003,2007 Red Hat, Inc.
22 *
23 * This library is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU Lesser General Public
25 * License as published by the Free Software Foundation; either
26 * version 2.1 of the License, or (at your option) any later version.
27 *
28 * This library is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
31 * Lesser General Public License for more details.
32 *
33 * You should have received a copy of the GNU Lesser General Public
34 * License along with this library; if not, write to the Free Software
35 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
36 */
37
38 /* FLASK */
39
40 /*
41 * Implementation of the access vector table type.
42 */
43
44 #include <stdlib.h>
45 #include <sepol/policydb/avtab.h>
46 #include <sepol/policydb/policydb.h>
47 #include <sepol/errcodes.h>
48
49 #include "debug.h"
50 #include "private.h"
51
52 /* Based on MurmurHash3, written by Austin Appleby and placed in the
53 * public domain.
54 */
avtab_hash(struct avtab_key * keyp,uint32_t mask)55 static inline int avtab_hash(struct avtab_key *keyp, uint32_t mask)
56 {
57 static const uint32_t c1 = 0xcc9e2d51;
58 static const uint32_t c2 = 0x1b873593;
59 static const uint32_t r1 = 15;
60 static const uint32_t r2 = 13;
61 static const uint32_t m = 5;
62 static const uint32_t n = 0xe6546b64;
63
64 uint32_t hash = 0;
65
66 #define mix(input) { \
67 uint32_t v = input; \
68 v *= c1; \
69 v = (v << r1) | (v >> (32 - r1)); \
70 v *= c2; \
71 hash ^= v; \
72 hash = (hash << r2) | (hash >> (32 - r2)); \
73 hash = hash * m + n; \
74 }
75
76 mix(keyp->target_class);
77 mix(keyp->target_type);
78 mix(keyp->source_type);
79
80 #undef mix
81
82 hash ^= hash >> 16;
83 hash *= 0x85ebca6b;
84 hash ^= hash >> 13;
85 hash *= 0xc2b2ae35;
86 hash ^= hash >> 16;
87
88 return hash & mask;
89 }
90
91 static avtab_ptr_t
avtab_insert_node(avtab_t * h,int hvalue,avtab_ptr_t prev,avtab_key_t * key,avtab_datum_t * datum)92 avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key,
93 avtab_datum_t * datum)
94 {
95 avtab_ptr_t newnode;
96 avtab_operations_t *ops;
97
98 newnode = (avtab_ptr_t) malloc(sizeof(struct avtab_node));
99 if (newnode == NULL)
100 return NULL;
101 memset(newnode, 0, sizeof(struct avtab_node));
102 newnode->key = *key;
103
104 if (key->specified & AVTAB_OP) {
105 ops = calloc(1, sizeof(avtab_operations_t));
106 if (ops == NULL) {
107 free(newnode);
108 return NULL;
109 }
110 if (datum->ops) /* else caller populates ops*/
111 *ops = *(datum->ops);
112
113 newnode->datum.ops = ops;
114 } else {
115 newnode->datum = *datum;
116 }
117
118 if (prev) {
119 newnode->next = prev->next;
120 prev->next = newnode;
121 } else {
122 newnode->next = h->htable[hvalue];
123 h->htable[hvalue] = newnode;
124 }
125
126 h->nel++;
127 return newnode;
128 }
129
avtab_insert(avtab_t * h,avtab_key_t * key,avtab_datum_t * datum)130 int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
131 {
132 int hvalue;
133 avtab_ptr_t prev, cur, newnode;
134 uint16_t specified =
135 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
136
137 if (!h || !h->htable)
138 return SEPOL_ENOMEM;
139
140 hvalue = avtab_hash(key, h->mask);
141 for (prev = NULL, cur = h->htable[hvalue];
142 cur; prev = cur, cur = cur->next) {
143 if (key->source_type == cur->key.source_type &&
144 key->target_type == cur->key.target_type &&
145 key->target_class == cur->key.target_class &&
146 (specified & cur->key.specified)) {
147 if (specified & AVTAB_OPNUM)
148 break;
149 return SEPOL_EEXIST;
150 }
151 if (key->source_type < cur->key.source_type)
152 break;
153 if (key->source_type == cur->key.source_type &&
154 key->target_type < cur->key.target_type)
155 break;
156 if (key->source_type == cur->key.source_type &&
157 key->target_type == cur->key.target_type &&
158 key->target_class < cur->key.target_class)
159 break;
160 }
161
162 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
163 if (!newnode)
164 return SEPOL_ENOMEM;
165
166 return 0;
167 }
168
169 /* Unlike avtab_insert(), this function allow multiple insertions of the same
170 * key/specified mask into the table, as needed by the conditional avtab.
171 * It also returns a pointer to the node inserted.
172 */
173 avtab_ptr_t
avtab_insert_nonunique(avtab_t * h,avtab_key_t * key,avtab_datum_t * datum)174 avtab_insert_nonunique(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
175 {
176 int hvalue;
177 avtab_ptr_t prev, cur, newnode;
178 uint16_t specified =
179 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
180
181 if (!h || !h->htable)
182 return NULL;
183 hvalue = avtab_hash(key, h->mask);
184 for (prev = NULL, cur = h->htable[hvalue];
185 cur; prev = cur, cur = cur->next) {
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 (specified & cur->key.specified))
190 break;
191 if (key->source_type < cur->key.source_type)
192 break;
193 if (key->source_type == cur->key.source_type &&
194 key->target_type < cur->key.target_type)
195 break;
196 if (key->source_type == cur->key.source_type &&
197 key->target_type == cur->key.target_type &&
198 key->target_class < cur->key.target_class)
199 break;
200 }
201 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
202
203 return newnode;
204 }
205
avtab_search(avtab_t * h,avtab_key_t * key)206 avtab_datum_t *avtab_search(avtab_t * h, avtab_key_t * key)
207 {
208 int hvalue;
209 avtab_ptr_t cur;
210 uint16_t specified =
211 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
212
213 if (!h || !h->htable)
214 return NULL;
215
216 hvalue = avtab_hash(key, h->mask);
217 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
218 if (key->source_type == cur->key.source_type &&
219 key->target_type == cur->key.target_type &&
220 key->target_class == cur->key.target_class &&
221 (specified & cur->key.specified))
222 return &cur->datum;
223
224 if (key->source_type < cur->key.source_type)
225 break;
226 if (key->source_type == cur->key.source_type &&
227 key->target_type < cur->key.target_type)
228 break;
229 if (key->source_type == cur->key.source_type &&
230 key->target_type == cur->key.target_type &&
231 key->target_class < cur->key.target_class)
232 break;
233 }
234
235 return NULL;
236 }
237
238 /* This search function returns a node pointer, and can be used in
239 * conjunction with avtab_search_next_node()
240 */
avtab_search_node(avtab_t * h,avtab_key_t * key)241 avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key)
242 {
243 int hvalue;
244 avtab_ptr_t cur;
245 uint16_t specified =
246 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
247
248 if (!h || !h->htable)
249 return NULL;
250
251 hvalue = avtab_hash(key, h->mask);
252 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
253 if (key->source_type == cur->key.source_type &&
254 key->target_type == cur->key.target_type &&
255 key->target_class == cur->key.target_class &&
256 (specified & cur->key.specified))
257 return cur;
258
259 if (key->source_type < cur->key.source_type)
260 break;
261 if (key->source_type == cur->key.source_type &&
262 key->target_type < cur->key.target_type)
263 break;
264 if (key->source_type == cur->key.source_type &&
265 key->target_type == cur->key.target_type &&
266 key->target_class < cur->key.target_class)
267 break;
268 }
269 return NULL;
270 }
271
avtab_search_node_next(avtab_ptr_t node,int specified)272 avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified)
273 {
274 avtab_ptr_t cur;
275
276 if (!node)
277 return NULL;
278
279 specified &= ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
280 for (cur = node->next; cur; cur = cur->next) {
281 if (node->key.source_type == cur->key.source_type &&
282 node->key.target_type == cur->key.target_type &&
283 node->key.target_class == cur->key.target_class &&
284 (specified & cur->key.specified))
285 return cur;
286
287 if (node->key.source_type < cur->key.source_type)
288 break;
289 if (node->key.source_type == cur->key.source_type &&
290 node->key.target_type < cur->key.target_type)
291 break;
292 if (node->key.source_type == cur->key.source_type &&
293 node->key.target_type == cur->key.target_type &&
294 node->key.target_class < cur->key.target_class)
295 break;
296 }
297 return NULL;
298 }
299
avtab_destroy(avtab_t * h)300 void avtab_destroy(avtab_t * h)
301 {
302 unsigned int i;
303 avtab_ptr_t cur, temp;
304
305 if (!h || !h->htable)
306 return;
307
308 for (i = 0; i < h->nslot; i++) {
309 cur = h->htable[i];
310 while (cur != NULL) {
311 temp = cur;
312 cur = cur->next;
313 free(temp);
314 }
315 h->htable[i] = NULL;
316 }
317 free(h->htable);
318 h->htable = NULL;
319 h->nslot = 0;
320 h->mask = 0;
321 }
322
avtab_map(avtab_t * h,int (* apply)(avtab_key_t * k,avtab_datum_t * d,void * args),void * args)323 int avtab_map(avtab_t * h,
324 int (*apply) (avtab_key_t * k,
325 avtab_datum_t * d, void *args), void *args)
326 {
327 unsigned int i;
328 int ret;
329 avtab_ptr_t cur;
330
331 if (!h)
332 return 0;
333
334 for (i = 0; i < h->nslot; i++) {
335 cur = h->htable[i];
336 while (cur != NULL) {
337 ret = apply(&cur->key, &cur->datum, args);
338 if (ret)
339 return ret;
340 cur = cur->next;
341 }
342 }
343 return 0;
344 }
345
avtab_init(avtab_t * h)346 int avtab_init(avtab_t * h)
347 {
348 h->htable = NULL;
349 h->nel = 0;
350 return 0;
351 }
352
avtab_alloc(avtab_t * h,uint32_t nrules)353 int avtab_alloc(avtab_t *h, uint32_t nrules)
354 {
355 uint32_t mask = 0;
356 uint32_t shift = 0;
357 uint32_t work = nrules;
358 uint32_t nslot = 0;
359
360 if (nrules == 0)
361 goto out;
362
363 while (work) {
364 work = work >> 1;
365 shift++;
366 }
367 if (shift > 2)
368 shift = shift - 2;
369 nslot = 1 << shift;
370 if (nslot > MAX_AVTAB_HASH_BUCKETS)
371 nslot = MAX_AVTAB_HASH_BUCKETS;
372 mask = nslot - 1;
373
374 h->htable = calloc(nslot, sizeof(avtab_ptr_t));
375 if (!h->htable)
376 return -1;
377 out:
378 h->nel = 0;
379 h->nslot = nslot;
380 h->mask = mask;
381 return 0;
382 }
383
avtab_hash_eval(avtab_t * h,char * tag)384 void avtab_hash_eval(avtab_t * h, char *tag)
385 {
386 unsigned int i, chain_len, slots_used, max_chain_len;
387 avtab_ptr_t cur;
388
389 slots_used = 0;
390 max_chain_len = 0;
391 for (i = 0; i < h->nslot; i++) {
392 cur = h->htable[i];
393 if (cur) {
394 slots_used++;
395 chain_len = 0;
396 while (cur) {
397 chain_len++;
398 cur = cur->next;
399 }
400
401 if (chain_len > max_chain_len)
402 max_chain_len = chain_len;
403 }
404 }
405
406 printf
407 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
408 tag, h->nel, slots_used, h->nslot, max_chain_len);
409 }
410
411 /* Ordering of datums in the original avtab format in the policy file. */
412 static uint16_t spec_order[] = {
413 AVTAB_ALLOWED,
414 AVTAB_AUDITDENY,
415 AVTAB_AUDITALLOW,
416 AVTAB_TRANSITION,
417 AVTAB_CHANGE,
418 AVTAB_MEMBER,
419 AVTAB_OPNUM_ALLOWED,
420 AVTAB_OPNUM_AUDITALLOW,
421 AVTAB_OPNUM_DONTAUDIT,
422 AVTAB_OPTYPE_ALLOWED,
423 AVTAB_OPTYPE_AUDITALLOW,
424 AVTAB_OPTYPE_DONTAUDIT
425 };
426
avtab_read_item(struct policy_file * fp,uint32_t vers,avtab_t * a,int (* insertf)(avtab_t * a,avtab_key_t * k,avtab_datum_t * d,void * p),void * p)427 int avtab_read_item(struct policy_file *fp, uint32_t vers, avtab_t * a,
428 int (*insertf) (avtab_t * a, avtab_key_t * k,
429 avtab_datum_t * d, void *p), void *p)
430 {
431 uint8_t buf8;
432 uint16_t buf16[4], enabled;
433 uint32_t buf32[8], items, items2, val;
434 avtab_key_t key;
435 avtab_datum_t datum;
436 avtab_operations_t ops;
437 unsigned set;
438 unsigned int i;
439 int rc;
440
441 memset(&key, 0, sizeof(avtab_key_t));
442 memset(&datum, 0, sizeof(avtab_datum_t));
443 memset(&ops, 0, sizeof(avtab_operations_t));
444
445 if (vers < POLICYDB_VERSION_AVTAB) {
446 rc = next_entry(buf32, fp, sizeof(uint32_t));
447 if (rc < 0) {
448 ERR(fp->handle, "truncated entry");
449 return -1;
450 }
451 items2 = le32_to_cpu(buf32[0]);
452
453 if (items2 < 5 || items2 > ARRAY_SIZE(buf32)) {
454 ERR(fp->handle, "invalid item count");
455 return -1;
456 }
457
458 rc = next_entry(buf32, fp, sizeof(uint32_t) * items2);
459 if (rc < 0) {
460 ERR(fp->handle, "truncated entry");
461 return -1;
462 }
463
464 items = 0;
465 val = le32_to_cpu(buf32[items++]);
466 key.source_type = (uint16_t) val;
467 if (key.source_type != val) {
468 ERR(fp->handle, "truncated source type");
469 return -1;
470 }
471 val = le32_to_cpu(buf32[items++]);
472 key.target_type = (uint16_t) val;
473 if (key.target_type != val) {
474 ERR(fp->handle, "truncated target type");
475 return -1;
476 }
477 val = le32_to_cpu(buf32[items++]);
478 key.target_class = (uint16_t) val;
479 if (key.target_class != val) {
480 ERR(fp->handle, "truncated target class");
481 return -1;
482 }
483
484 val = le32_to_cpu(buf32[items++]);
485 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
486
487 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
488 ERR(fp->handle, "null entry");
489 return -1;
490 }
491 if ((val & AVTAB_AV) && (val & AVTAB_TYPE)) {
492 ERR(fp->handle, "entry has both access "
493 "vectors and types");
494 return -1;
495 }
496
497 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
498 if (val & spec_order[i]) {
499 key.specified = spec_order[i] | enabled;
500 datum.data = le32_to_cpu(buf32[items++]);
501 rc = insertf(a, &key, &datum, p);
502 if (rc)
503 return rc;
504 }
505 }
506
507 if (items != items2) {
508 ERR(fp->handle, "entry only had %d items, "
509 "expected %d", items2, items);
510 return -1;
511 }
512 return 0;
513 }
514
515 rc = next_entry(buf16, fp, sizeof(uint16_t) * 4);
516 if (rc < 0) {
517 ERR(fp->handle, "truncated entry");
518 return -1;
519 }
520 items = 0;
521 key.source_type = le16_to_cpu(buf16[items++]);
522 key.target_type = le16_to_cpu(buf16[items++]);
523 key.target_class = le16_to_cpu(buf16[items++]);
524 key.specified = le16_to_cpu(buf16[items++]);
525
526 set = 0;
527 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
528 if (key.specified & spec_order[i])
529 set++;
530 }
531 if (!set || set > 1) {
532 ERR(fp->handle, "more than one specifier");
533 return -1;
534 }
535
536 if ((vers < POLICYDB_VERSION_IOCTL_OPERATIONS) &&
537 (key.specified & AVTAB_OP)) {
538 ERR(fp->handle, "policy version %u does not support ioctl "
539 "operation rules and one was specified\n", vers);
540 return -1;
541 } else if (key.specified & AVTAB_OP) {
542 rc = next_entry(&buf8, fp, sizeof(uint8_t));
543 if (rc < 0) {
544 ERR(fp->handle, "truncated entry");
545 return -1;
546 }
547 ops.type = buf8;
548 rc = next_entry(buf32, fp, sizeof(uint32_t)*8);
549 if (rc < 0) {
550 ERR(fp->handle, "truncated entry");
551 return -1;
552 }
553 for (i = 0; i < ARRAY_SIZE(ops.perms); i++)
554 ops.perms[i] = le32_to_cpu(buf32[i]);
555 datum.ops = &ops;
556 } else {
557 rc = next_entry(buf32, fp, sizeof(uint32_t));
558 if (rc < 0) {
559 ERR(fp->handle, "truncated entry");
560 return -1;
561 }
562 datum.data = le32_to_cpu(*buf32);
563 }
564 return insertf(a, &key, &datum, p);
565 }
566
avtab_insertf(avtab_t * a,avtab_key_t * k,avtab_datum_t * d,void * p)567 static int avtab_insertf(avtab_t * a, avtab_key_t * k, avtab_datum_t * d,
568 void *p __attribute__ ((unused)))
569 {
570 return avtab_insert(a, k, d);
571 }
572
avtab_read(avtab_t * a,struct policy_file * fp,uint32_t vers)573 int avtab_read(avtab_t * a, struct policy_file *fp, uint32_t vers)
574 {
575 unsigned int i;
576 int rc;
577 uint32_t buf[1];
578 uint32_t nel;
579
580 rc = next_entry(buf, fp, sizeof(uint32_t));
581 if (rc < 0) {
582 ERR(fp->handle, "truncated table");
583 goto bad;
584 }
585 nel = le32_to_cpu(buf[0]);
586 if (!nel) {
587 ERR(fp->handle, "table is empty");
588 goto bad;
589 }
590
591 rc = avtab_alloc(a, nel);
592 if (rc) {
593 ERR(fp->handle, "out of memory");
594 goto bad;
595 }
596
597 for (i = 0; i < nel; i++) {
598 rc = avtab_read_item(fp, vers, a, avtab_insertf, NULL);
599 if (rc) {
600 if (rc == SEPOL_ENOMEM)
601 ERR(fp->handle, "out of memory");
602 if (rc == SEPOL_EEXIST)
603 ERR(fp->handle, "duplicate entry");
604 ERR(fp->handle, "failed on entry %d of %u", i, nel);
605 goto bad;
606 }
607 }
608
609 return 0;
610
611 bad:
612 avtab_destroy(a);
613 return -1;
614 }
615