1
2 /* Author : Stephen Smalley, <[email protected]> */
3
4 /*
5 * Updated: Yuichi Nakamura <[email protected]>
6 * Tuned number of hash slots for avtab to reduce memory usage
7 */
8
9 /* Updated: Frank Mayer <[email protected]>
10 * and Karl MacMillan <[email protected]>
11 *
12 * Added conditional policy language extensions
13 *
14 * Updated: Red Hat, Inc. James Morris <[email protected]>
15 *
16 * Code cleanup
17 *
18 * Updated: Karl MacMillan <[email protected]>
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 */
55 ignore_unsigned_overflow_
avtab_hash(struct avtab_key * keyp,uint32_t mask)56 static inline int avtab_hash(struct avtab_key *keyp, uint32_t mask)
57 {
58 static const uint32_t c1 = 0xcc9e2d51;
59 static const uint32_t c2 = 0x1b873593;
60 static const uint32_t r1 = 15;
61 static const uint32_t r2 = 13;
62 static const uint32_t m = 5;
63 static const uint32_t n = 0xe6546b64;
64
65 uint32_t hash = 0;
66
67 #define mix(input) do { \
68 uint32_t v = input; \
69 v *= c1; \
70 v = (v << r1) | (v >> (32 - r1)); \
71 v *= c2; \
72 hash ^= v; \
73 hash = (hash << r2) | (hash >> (32 - r2)); \
74 hash = hash * m + n; \
75 } while (0)
76
77 mix(keyp->target_class);
78 mix(keyp->target_type);
79 mix(keyp->source_type);
80
81 #undef mix
82
83 hash ^= hash >> 16;
84 hash *= 0x85ebca6b;
85 hash ^= hash >> 13;
86 hash *= 0xc2b2ae35;
87 hash ^= hash >> 16;
88
89 return hash & mask;
90 }
91
92 static avtab_ptr_t
avtab_insert_node(avtab_t * h,int hvalue,avtab_ptr_t prev,avtab_key_t * key,avtab_datum_t * datum)93 avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key,
94 avtab_datum_t * datum)
95 {
96 avtab_ptr_t newnode;
97 avtab_extended_perms_t *xperms;
98
99 newnode = (avtab_ptr_t) malloc(sizeof(struct avtab_node));
100 if (newnode == NULL)
101 return NULL;
102 memset(newnode, 0, sizeof(struct avtab_node));
103 newnode->key = *key;
104
105 if (key->specified & AVTAB_XPERMS) {
106 xperms = calloc(1, sizeof(avtab_extended_perms_t));
107 if (xperms == NULL) {
108 free(newnode);
109 return NULL;
110 }
111 if (datum->xperms) /* else caller populates xperms */
112 *xperms = *(datum->xperms);
113
114 newnode->datum.xperms = xperms;
115 /* data is usually ignored with xperms, except in the case of
116 * neverallow checking, which requires permission bits to be set.
117 * So copy data so it is set in the avtab
118 */
119 newnode->datum.data = datum->data;
120 } else {
121 newnode->datum = *datum;
122 }
123
124 if (prev) {
125 newnode->next = prev->next;
126 prev->next = newnode;
127 } else {
128 newnode->next = h->htable[hvalue];
129 h->htable[hvalue] = newnode;
130 }
131
132 h->nel++;
133 return newnode;
134 }
135
avtab_insert(avtab_t * h,avtab_key_t * key,avtab_datum_t * datum)136 int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
137 {
138 int hvalue;
139 avtab_ptr_t prev, cur, newnode;
140 uint16_t specified =
141 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
142
143 if (!h || !h->htable)
144 return SEPOL_ENOMEM;
145
146 hvalue = avtab_hash(key, h->mask);
147 for (prev = NULL, cur = h->htable[hvalue];
148 cur; prev = cur, cur = cur->next) {
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 (specified & cur->key.specified)) {
153 /* Extended permissions are not necessarily unique */
154 if (specified & AVTAB_XPERMS)
155 break;
156 return SEPOL_EEXIST;
157 }
158 if (key->source_type < cur->key.source_type)
159 break;
160 if (key->source_type == cur->key.source_type &&
161 key->target_type < cur->key.target_type)
162 break;
163 if (key->source_type == cur->key.source_type &&
164 key->target_type == cur->key.target_type &&
165 key->target_class < cur->key.target_class)
166 break;
167 }
168
169 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
170 if (!newnode)
171 return SEPOL_ENOMEM;
172
173 return 0;
174 }
175
176 /* Unlike avtab_insert(), this function allow multiple insertions of the same
177 * key/specified mask into the table, as needed by the conditional avtab.
178 * It also returns a pointer to the node inserted.
179 */
180 avtab_ptr_t
avtab_insert_nonunique(avtab_t * h,avtab_key_t * key,avtab_datum_t * datum)181 avtab_insert_nonunique(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
182 {
183 int hvalue;
184 avtab_ptr_t prev, cur, newnode;
185 uint16_t specified =
186 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
187
188 if (!h || !h->htable)
189 return NULL;
190 hvalue = avtab_hash(key, h->mask);
191 for (prev = NULL, cur = h->htable[hvalue];
192 cur; prev = cur, cur = cur->next) {
193 if (key->source_type == cur->key.source_type &&
194 key->target_type == cur->key.target_type &&
195 key->target_class == cur->key.target_class &&
196 (specified & cur->key.specified))
197 break;
198 if (key->source_type < cur->key.source_type)
199 break;
200 if (key->source_type == cur->key.source_type &&
201 key->target_type < cur->key.target_type)
202 break;
203 if (key->source_type == cur->key.source_type &&
204 key->target_type == cur->key.target_type &&
205 key->target_class < cur->key.target_class)
206 break;
207 }
208 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
209
210 return newnode;
211 }
212
avtab_search(avtab_t * h,avtab_key_t * key)213 avtab_datum_t *avtab_search(avtab_t * h, avtab_key_t * key)
214 {
215 int hvalue;
216 avtab_ptr_t cur;
217 uint16_t specified =
218 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
219
220 if (!h || !h->htable)
221 return NULL;
222
223 hvalue = avtab_hash(key, h->mask);
224 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
225 if (key->source_type == cur->key.source_type &&
226 key->target_type == cur->key.target_type &&
227 key->target_class == cur->key.target_class &&
228 (specified & cur->key.specified))
229 return &cur->datum;
230
231 if (key->source_type < cur->key.source_type)
232 break;
233 if (key->source_type == cur->key.source_type &&
234 key->target_type < cur->key.target_type)
235 break;
236 if (key->source_type == cur->key.source_type &&
237 key->target_type == cur->key.target_type &&
238 key->target_class < cur->key.target_class)
239 break;
240 }
241
242 return NULL;
243 }
244
245 /* This search function returns a node pointer, and can be used in
246 * conjunction with avtab_search_next_node()
247 */
avtab_search_node(avtab_t * h,avtab_key_t * key)248 avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key)
249 {
250 int hvalue;
251 avtab_ptr_t cur;
252 uint16_t specified =
253 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
254
255 if (!h || !h->htable)
256 return NULL;
257
258 hvalue = avtab_hash(key, h->mask);
259 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
260 if (key->source_type == cur->key.source_type &&
261 key->target_type == cur->key.target_type &&
262 key->target_class == cur->key.target_class &&
263 (specified & cur->key.specified))
264 return cur;
265
266 if (key->source_type < cur->key.source_type)
267 break;
268 if (key->source_type == cur->key.source_type &&
269 key->target_type < cur->key.target_type)
270 break;
271 if (key->source_type == cur->key.source_type &&
272 key->target_type == cur->key.target_type &&
273 key->target_class < cur->key.target_class)
274 break;
275 }
276 return NULL;
277 }
278
avtab_search_node_next(avtab_ptr_t node,int specified)279 avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified)
280 {
281 avtab_ptr_t cur;
282
283 if (!node)
284 return NULL;
285
286 specified &= ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
287 for (cur = node->next; cur; cur = cur->next) {
288 if (node->key.source_type == cur->key.source_type &&
289 node->key.target_type == cur->key.target_type &&
290 node->key.target_class == cur->key.target_class &&
291 (specified & cur->key.specified))
292 return cur;
293
294 if (node->key.source_type < cur->key.source_type)
295 break;
296 if (node->key.source_type == cur->key.source_type &&
297 node->key.target_type < cur->key.target_type)
298 break;
299 if (node->key.source_type == cur->key.source_type &&
300 node->key.target_type == cur->key.target_type &&
301 node->key.target_class < cur->key.target_class)
302 break;
303 }
304 return NULL;
305 }
306
avtab_destroy(avtab_t * h)307 void avtab_destroy(avtab_t * h)
308 {
309 unsigned int i;
310 avtab_ptr_t cur, temp;
311
312 if (!h || !h->htable)
313 return;
314
315 for (i = 0; i < h->nslot; i++) {
316 cur = h->htable[i];
317 while (cur != NULL) {
318 if (cur->key.specified & AVTAB_XPERMS) {
319 free(cur->datum.xperms);
320 }
321 temp = cur;
322 cur = cur->next;
323 free(temp);
324 }
325 h->htable[i] = NULL;
326 }
327 free(h->htable);
328 h->htable = NULL;
329 h->nslot = 0;
330 h->mask = 0;
331 }
332
avtab_map(const avtab_t * h,int (* apply)(avtab_key_t * k,avtab_datum_t * d,void * args),void * args)333 int avtab_map(const avtab_t * h,
334 int (*apply) (avtab_key_t * k,
335 avtab_datum_t * d, void *args), void *args)
336 {
337 unsigned int i;
338 int ret;
339 avtab_ptr_t cur;
340
341 if (!h)
342 return 0;
343
344 for (i = 0; i < h->nslot; i++) {
345 cur = h->htable[i];
346 while (cur != NULL) {
347 ret = apply(&cur->key, &cur->datum, args);
348 if (ret)
349 return ret;
350 cur = cur->next;
351 }
352 }
353 return 0;
354 }
355
avtab_init(avtab_t * h)356 int avtab_init(avtab_t * h)
357 {
358 h->htable = NULL;
359 h->nel = 0;
360 return 0;
361 }
362
avtab_alloc(avtab_t * h,uint32_t nrules)363 int avtab_alloc(avtab_t *h, uint32_t nrules)
364 {
365 uint32_t mask = 0;
366 uint32_t shift = 0;
367 uint32_t work = nrules;
368 uint32_t nslot = 0;
369
370 if (nrules == 0)
371 goto out;
372
373 while (work) {
374 work = work >> 1;
375 shift++;
376 }
377 if (shift > 2)
378 shift = shift - 2;
379 nslot = UINT32_C(1) << shift;
380 if (nslot > MAX_AVTAB_HASH_BUCKETS)
381 nslot = MAX_AVTAB_HASH_BUCKETS;
382 mask = nslot - 1;
383
384 h->htable = calloc(nslot, sizeof(avtab_ptr_t));
385 if (!h->htable)
386 return -1;
387 out:
388 h->nel = 0;
389 h->nslot = nslot;
390 h->mask = mask;
391 return 0;
392 }
393
avtab_hash_eval(avtab_t * h,char * tag)394 void avtab_hash_eval(avtab_t * h, char *tag)
395 {
396 unsigned int i, chain_len, slots_used, max_chain_len;
397 avtab_ptr_t cur;
398
399 slots_used = 0;
400 max_chain_len = 0;
401 for (i = 0; i < h->nslot; i++) {
402 cur = h->htable[i];
403 if (cur) {
404 slots_used++;
405 chain_len = 0;
406 while (cur) {
407 chain_len++;
408 cur = cur->next;
409 }
410
411 if (chain_len > max_chain_len)
412 max_chain_len = chain_len;
413 }
414 }
415
416 printf
417 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
418 tag, h->nel, slots_used, h->nslot, max_chain_len);
419 }
420
421 /* Ordering of datums in the original avtab format in the policy file. */
422 static const uint16_t spec_order[] = {
423 AVTAB_ALLOWED,
424 AVTAB_AUDITDENY,
425 AVTAB_AUDITALLOW,
426 AVTAB_TRANSITION,
427 AVTAB_CHANGE,
428 AVTAB_MEMBER,
429 AVTAB_XPERMS_ALLOWED,
430 AVTAB_XPERMS_AUDITALLOW,
431 AVTAB_XPERMS_DONTAUDIT
432 };
433
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)434 int avtab_read_item(struct policy_file *fp, uint32_t vers, avtab_t * a,
435 int (*insertf) (avtab_t * a, avtab_key_t * k,
436 avtab_datum_t * d, void *p), void *p)
437 {
438 uint8_t buf8;
439 uint16_t buf16[4], enabled;
440 uint32_t buf32[8], items, items2, val;
441 avtab_key_t key;
442 avtab_datum_t datum;
443 avtab_extended_perms_t xperms;
444 unsigned int i;
445 int rc;
446
447 memset(&key, 0, sizeof(avtab_key_t));
448 memset(&datum, 0, sizeof(avtab_datum_t));
449 memset(&xperms, 0, sizeof(avtab_extended_perms_t));
450
451 if (vers < POLICYDB_VERSION_AVTAB) {
452 rc = next_entry(buf32, fp, sizeof(uint32_t));
453 if (rc < 0) {
454 ERR(fp->handle, "truncated entry");
455 return -1;
456 }
457 items2 = le32_to_cpu(buf32[0]);
458
459 if (items2 < 5 || items2 > ARRAY_SIZE(buf32)) {
460 ERR(fp->handle, "invalid item count");
461 return -1;
462 }
463
464 rc = next_entry(buf32, fp, sizeof(uint32_t) * items2);
465 if (rc < 0) {
466 ERR(fp->handle, "truncated entry");
467 return -1;
468 }
469
470 items = 0;
471 val = le32_to_cpu(buf32[items++]);
472 key.source_type = (uint16_t) val;
473 if (key.source_type != val) {
474 ERR(fp->handle, "truncated source type");
475 return -1;
476 }
477 val = le32_to_cpu(buf32[items++]);
478 key.target_type = (uint16_t) val;
479 if (key.target_type != val) {
480 ERR(fp->handle, "truncated target type");
481 return -1;
482 }
483 val = le32_to_cpu(buf32[items++]);
484 key.target_class = (uint16_t) val;
485 if (key.target_class != val) {
486 ERR(fp->handle, "truncated target class");
487 return -1;
488 }
489
490 val = le32_to_cpu(buf32[items++]);
491 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
492
493 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
494 ERR(fp->handle, "null entry");
495 return -1;
496 }
497 if ((val & AVTAB_AV) && (val & AVTAB_TYPE)) {
498 ERR(fp->handle, "entry has both access "
499 "vectors and types");
500 return -1;
501 }
502
503 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
504 if (val & spec_order[i]) {
505 if (items >= items2) { /* items is index, items2 is total number */
506 ERR(fp->handle, "entry has too many items (%d/%d)",
507 items + 1, items2);
508 return -1;
509 }
510 key.specified = spec_order[i] | enabled;
511 datum.data = le32_to_cpu(buf32[items++]);
512 rc = insertf(a, &key, &datum, p);
513 if (rc)
514 return rc;
515 }
516 }
517
518 if (items != items2) {
519 ERR(fp->handle, "entry only had %d items, "
520 "expected %d", items2, items);
521 return -1;
522 }
523 return 0;
524 }
525
526 rc = next_entry(buf16, fp, sizeof(uint16_t) * 4);
527 if (rc < 0) {
528 ERR(fp->handle, "truncated entry");
529 return -1;
530 }
531 items = 0;
532 key.source_type = le16_to_cpu(buf16[items++]);
533 key.target_type = le16_to_cpu(buf16[items++]);
534 key.target_class = le16_to_cpu(buf16[items++]);
535 key.specified = le16_to_cpu(buf16[items++]);
536
537 if (key.specified & ~(AVTAB_AV | AVTAB_TYPE | AVTAB_XPERMS | AVTAB_ENABLED)) {
538 ERR(fp->handle, "invalid specifier");
539 return -1;
540 }
541
542 if (__builtin_popcount(key.specified & ~AVTAB_ENABLED) != 1) {
543 ERR(fp->handle, "not exactly one specifier");
544 return -1;
545 }
546
547 if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) &&
548 (key.specified & AVTAB_XPERMS)) {
549 ERR(fp->handle, "policy version %u does not support extended "
550 "permissions rules and one was specified", vers);
551 return -1;
552 } else if (key.specified & AVTAB_XPERMS) {
553 rc = next_entry(&buf8, fp, sizeof(uint8_t));
554 if (rc < 0) {
555 ERR(fp->handle, "truncated entry");
556 return -1;
557 }
558 xperms.specified = buf8;
559 rc = next_entry(&buf8, fp, sizeof(uint8_t));
560 if (rc < 0) {
561 ERR(fp->handle, "truncated entry");
562 return -1;
563 }
564 xperms.driver = buf8;
565 rc = next_entry(buf32, fp, sizeof(uint32_t)*8);
566 if (rc < 0) {
567 ERR(fp->handle, "truncated entry");
568 return -1;
569 }
570 for (i = 0; i < ARRAY_SIZE(xperms.perms); i++)
571 xperms.perms[i] = le32_to_cpu(buf32[i]);
572 datum.xperms = &xperms;
573 } else {
574 rc = next_entry(buf32, fp, sizeof(uint32_t));
575 if (rc < 0) {
576 ERR(fp->handle, "truncated entry");
577 return -1;
578 }
579 datum.data = le32_to_cpu(*buf32);
580 }
581 return insertf(a, &key, &datum, p);
582 }
583
avtab_insertf(avtab_t * a,avtab_key_t * k,avtab_datum_t * d,void * p)584 static int avtab_insertf(avtab_t * a, avtab_key_t * k, avtab_datum_t * d,
585 void *p __attribute__ ((unused)))
586 {
587 return avtab_insert(a, k, d);
588 }
589
avtab_read(avtab_t * a,struct policy_file * fp,uint32_t vers)590 int avtab_read(avtab_t * a, struct policy_file *fp, uint32_t vers)
591 {
592 unsigned int i;
593 int rc;
594 uint32_t buf[1];
595 uint32_t nel;
596
597 rc = next_entry(buf, fp, sizeof(uint32_t));
598 if (rc < 0) {
599 ERR(fp->handle, "truncated table");
600 goto bad;
601 }
602 nel = le32_to_cpu(buf[0]);
603 if (zero_or_saturated(nel) || exceeds_available_bytes(fp, nel, sizeof(uint32_t) * 3)) {
604 ERR(fp->handle, "table is empty");
605 goto bad;
606 }
607
608 rc = avtab_alloc(a, nel);
609 if (rc) {
610 ERR(fp->handle, "out of memory");
611 goto bad;
612 }
613
614 for (i = 0; i < nel; i++) {
615 rc = avtab_read_item(fp, vers, a, avtab_insertf, NULL);
616 if (rc) {
617 if (rc == SEPOL_ENOMEM)
618 ERR(fp->handle, "out of memory");
619 if (rc == SEPOL_EEXIST)
620 ERR(fp->handle, "duplicate entry");
621 ERR(fp->handle, "failed on entry %d of %u", i, nel);
622 goto bad;
623 }
624 }
625
626 return 0;
627
628 bad:
629 avtab_destroy(a);
630 return -1;
631 }
632