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
avtab_hash(struct avtab_key * keyp,uint16_t mask)52 static inline int avtab_hash(struct avtab_key *keyp, uint16_t mask)
53 {
54 return ((keyp->target_class + (keyp->target_type << 2) +
55 (keyp->source_type << 9)) & mask);
56 }
57
58 static avtab_ptr_t
avtab_insert_node(avtab_t * h,int hvalue,avtab_ptr_t prev,avtab_key_t * key,avtab_datum_t * datum)59 avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key,
60 avtab_datum_t * datum)
61 {
62 avtab_ptr_t newnode;
63 newnode = (avtab_ptr_t) malloc(sizeof(struct avtab_node));
64 if (newnode == NULL)
65 return NULL;
66 memset(newnode, 0, sizeof(struct avtab_node));
67 newnode->key = *key;
68 newnode->datum = *datum;
69 if (prev) {
70 newnode->next = prev->next;
71 prev->next = newnode;
72 } else {
73 newnode->next = h->htable[hvalue];
74 h->htable[hvalue] = newnode;
75 }
76
77 h->nel++;
78 return newnode;
79 }
80
avtab_insert(avtab_t * h,avtab_key_t * key,avtab_datum_t * datum)81 int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
82 {
83 int hvalue;
84 avtab_ptr_t prev, cur, newnode;
85 uint16_t specified =
86 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
87
88 if (!h || !h->htable)
89 return SEPOL_ENOMEM;
90
91 hvalue = avtab_hash(key, h->mask);
92 for (prev = NULL, cur = h->htable[hvalue];
93 cur; prev = cur, cur = cur->next) {
94 if (key->source_type == cur->key.source_type &&
95 key->target_type == cur->key.target_type &&
96 key->target_class == cur->key.target_class &&
97 (specified & cur->key.specified))
98 return SEPOL_EEXIST;
99 if (key->source_type < cur->key.source_type)
100 break;
101 if (key->source_type == cur->key.source_type &&
102 key->target_type < cur->key.target_type)
103 break;
104 if (key->source_type == cur->key.source_type &&
105 key->target_type == cur->key.target_type &&
106 key->target_class < cur->key.target_class)
107 break;
108 }
109
110 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
111 if (!newnode)
112 return SEPOL_ENOMEM;
113
114 return 0;
115 }
116
117 /* Unlike avtab_insert(), this function allow multiple insertions of the same
118 * key/specified mask into the table, as needed by the conditional avtab.
119 * It also returns a pointer to the node inserted.
120 */
121 avtab_ptr_t
avtab_insert_nonunique(avtab_t * h,avtab_key_t * key,avtab_datum_t * datum)122 avtab_insert_nonunique(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
123 {
124 int hvalue;
125 avtab_ptr_t prev, cur, newnode;
126 uint16_t specified =
127 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
128
129 if (!h || !h->htable)
130 return NULL;
131 hvalue = avtab_hash(key, h->mask);
132 for (prev = NULL, cur = h->htable[hvalue];
133 cur; prev = cur, cur = cur->next) {
134 if (key->source_type == cur->key.source_type &&
135 key->target_type == cur->key.target_type &&
136 key->target_class == cur->key.target_class &&
137 (specified & cur->key.specified))
138 break;
139 if (key->source_type < cur->key.source_type)
140 break;
141 if (key->source_type == cur->key.source_type &&
142 key->target_type < cur->key.target_type)
143 break;
144 if (key->source_type == cur->key.source_type &&
145 key->target_type == cur->key.target_type &&
146 key->target_class < cur->key.target_class)
147 break;
148 }
149 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
150
151 return newnode;
152 }
153
avtab_search(avtab_t * h,avtab_key_t * key)154 avtab_datum_t *avtab_search(avtab_t * h, avtab_key_t * key)
155 {
156 int hvalue;
157 avtab_ptr_t cur;
158 uint16_t specified =
159 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
160
161 if (!h || !h->htable)
162 return NULL;
163
164 hvalue = avtab_hash(key, h->mask);
165 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
166 if (key->source_type == cur->key.source_type &&
167 key->target_type == cur->key.target_type &&
168 key->target_class == cur->key.target_class &&
169 (specified & cur->key.specified))
170 return &cur->datum;
171
172 if (key->source_type < cur->key.source_type)
173 break;
174 if (key->source_type == cur->key.source_type &&
175 key->target_type < cur->key.target_type)
176 break;
177 if (key->source_type == cur->key.source_type &&
178 key->target_type == cur->key.target_type &&
179 key->target_class < cur->key.target_class)
180 break;
181 }
182
183 return NULL;
184 }
185
186 /* This search function returns a node pointer, and can be used in
187 * conjunction with avtab_search_next_node()
188 */
avtab_search_node(avtab_t * h,avtab_key_t * key)189 avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key)
190 {
191 int hvalue;
192 avtab_ptr_t cur;
193 uint16_t specified =
194 key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
195
196 if (!h || !h->htable)
197 return NULL;
198
199 hvalue = avtab_hash(key, h->mask);
200 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
201 if (key->source_type == cur->key.source_type &&
202 key->target_type == cur->key.target_type &&
203 key->target_class == cur->key.target_class &&
204 (specified & cur->key.specified))
205 return cur;
206
207 if (key->source_type < cur->key.source_type)
208 break;
209 if (key->source_type == cur->key.source_type &&
210 key->target_type < cur->key.target_type)
211 break;
212 if (key->source_type == cur->key.source_type &&
213 key->target_type == cur->key.target_type &&
214 key->target_class < cur->key.target_class)
215 break;
216 }
217 return NULL;
218 }
219
avtab_search_node_next(avtab_ptr_t node,int specified)220 avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified)
221 {
222 avtab_ptr_t cur;
223
224 if (!node)
225 return NULL;
226
227 specified &= ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
228 for (cur = node->next; cur; cur = cur->next) {
229 if (node->key.source_type == cur->key.source_type &&
230 node->key.target_type == cur->key.target_type &&
231 node->key.target_class == cur->key.target_class &&
232 (specified & cur->key.specified))
233 return cur;
234
235 if (node->key.source_type < cur->key.source_type)
236 break;
237 if (node->key.source_type == cur->key.source_type &&
238 node->key.target_type < cur->key.target_type)
239 break;
240 if (node->key.source_type == cur->key.source_type &&
241 node->key.target_type == cur->key.target_type &&
242 node->key.target_class < cur->key.target_class)
243 break;
244 }
245 return NULL;
246 }
247
avtab_destroy(avtab_t * h)248 void avtab_destroy(avtab_t * h)
249 {
250 unsigned int i;
251 avtab_ptr_t cur, temp;
252
253 if (!h || !h->htable)
254 return;
255
256 for (i = 0; i < h->nslot; i++) {
257 cur = h->htable[i];
258 while (cur != NULL) {
259 temp = cur;
260 cur = cur->next;
261 free(temp);
262 }
263 h->htable[i] = NULL;
264 }
265 free(h->htable);
266 h->htable = NULL;
267 h->nslot = 0;
268 h->mask = 0;
269 }
270
avtab_map(avtab_t * h,int (* apply)(avtab_key_t * k,avtab_datum_t * d,void * args),void * args)271 int avtab_map(avtab_t * h,
272 int (*apply) (avtab_key_t * k,
273 avtab_datum_t * d, void *args), void *args)
274 {
275 unsigned int i;
276 int ret;
277 avtab_ptr_t cur;
278
279 if (!h)
280 return 0;
281
282 for (i = 0; i < h->nslot; i++) {
283 cur = h->htable[i];
284 while (cur != NULL) {
285 ret = apply(&cur->key, &cur->datum, args);
286 if (ret)
287 return ret;
288 cur = cur->next;
289 }
290 }
291 return 0;
292 }
293
avtab_init(avtab_t * h)294 int avtab_init(avtab_t * h)
295 {
296 h->htable = NULL;
297 h->nel = 0;
298 return 0;
299 }
300
avtab_alloc(avtab_t * h,uint32_t nrules)301 int avtab_alloc(avtab_t *h, uint32_t nrules)
302 {
303 uint16_t mask = 0;
304 uint32_t shift = 0;
305 uint32_t work = nrules;
306 uint32_t nslot = 0;
307
308 if (nrules == 0)
309 goto out;
310
311 while (work) {
312 work = work >> 1;
313 shift++;
314 }
315 if (shift > 2)
316 shift = shift - 2;
317 nslot = 1 << shift;
318 if (nslot > MAX_AVTAB_SIZE)
319 nslot = MAX_AVTAB_SIZE;
320 mask = nslot - 1;
321
322 h->htable = calloc(nslot, sizeof(avtab_ptr_t));
323 if (!h->htable)
324 return -1;
325 out:
326 h->nel = 0;
327 h->nslot = nslot;
328 h->mask = mask;
329 return 0;
330 }
331
avtab_hash_eval(avtab_t * h,char * tag)332 void avtab_hash_eval(avtab_t * h, char *tag)
333 {
334 unsigned int i, chain_len, slots_used, max_chain_len;
335 avtab_ptr_t cur;
336
337 slots_used = 0;
338 max_chain_len = 0;
339 for (i = 0; i < h->nslot; i++) {
340 cur = h->htable[i];
341 if (cur) {
342 slots_used++;
343 chain_len = 0;
344 while (cur) {
345 chain_len++;
346 cur = cur->next;
347 }
348
349 if (chain_len > max_chain_len)
350 max_chain_len = chain_len;
351 }
352 }
353
354 printf
355 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
356 tag, h->nel, slots_used, h->nslot, max_chain_len);
357 }
358
359 /* Ordering of datums in the original avtab format in the policy file. */
360 static uint16_t spec_order[] = {
361 AVTAB_ALLOWED,
362 AVTAB_AUDITDENY,
363 AVTAB_AUDITALLOW,
364 AVTAB_TRANSITION,
365 AVTAB_CHANGE,
366 AVTAB_MEMBER
367 };
368
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)369 int avtab_read_item(struct policy_file *fp, uint32_t vers, avtab_t * a,
370 int (*insertf) (avtab_t * a, avtab_key_t * k,
371 avtab_datum_t * d, void *p), void *p)
372 {
373 uint16_t buf16[4], enabled;
374 uint32_t buf32[7], items, items2, val;
375 avtab_key_t key;
376 avtab_datum_t datum;
377 unsigned set;
378 unsigned int i;
379 int rc;
380
381 memset(&key, 0, sizeof(avtab_key_t));
382 memset(&datum, 0, sizeof(avtab_datum_t));
383
384 if (vers < POLICYDB_VERSION_AVTAB) {
385 rc = next_entry(buf32, fp, sizeof(uint32_t));
386 if (rc < 0) {
387 ERR(fp->handle, "truncated entry");
388 return -1;
389 }
390 items2 = le32_to_cpu(buf32[0]);
391
392 if (items2 < 5 || items2 > ARRAY_SIZE(buf32)) {
393 ERR(fp->handle, "invalid item count");
394 return -1;
395 }
396
397 rc = next_entry(buf32, fp, sizeof(uint32_t) * items2);
398 if (rc < 0) {
399 ERR(fp->handle, "truncated entry");
400 return -1;
401 }
402
403 items = 0;
404 val = le32_to_cpu(buf32[items++]);
405 key.source_type = (uint16_t) val;
406 if (key.source_type != val) {
407 ERR(fp->handle, "truncated source type");
408 return -1;
409 }
410 val = le32_to_cpu(buf32[items++]);
411 key.target_type = (uint16_t) val;
412 if (key.target_type != val) {
413 ERR(fp->handle, "truncated target type");
414 return -1;
415 }
416 val = le32_to_cpu(buf32[items++]);
417 key.target_class = (uint16_t) val;
418 if (key.target_class != val) {
419 ERR(fp->handle, "truncated target class");
420 return -1;
421 }
422
423 val = le32_to_cpu(buf32[items++]);
424 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
425
426 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
427 ERR(fp->handle, "null entry");
428 return -1;
429 }
430 if ((val & AVTAB_AV) && (val & AVTAB_TYPE)) {
431 ERR(fp->handle, "entry has both access "
432 "vectors and types");
433 return -1;
434 }
435
436 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
437 if (val & spec_order[i]) {
438 key.specified = spec_order[i] | enabled;
439 datum.data = le32_to_cpu(buf32[items++]);
440 rc = insertf(a, &key, &datum, p);
441 if (rc)
442 return rc;
443 }
444 }
445
446 if (items != items2) {
447 ERR(fp->handle, "entry only had %d items, "
448 "expected %d", items2, items);
449 return -1;
450 }
451 return 0;
452 }
453
454 rc = next_entry(buf16, fp, sizeof(uint16_t) * 4);
455 if (rc < 0) {
456 ERR(fp->handle, "truncated entry");
457 return -1;
458 }
459 items = 0;
460 key.source_type = le16_to_cpu(buf16[items++]);
461 key.target_type = le16_to_cpu(buf16[items++]);
462 key.target_class = le16_to_cpu(buf16[items++]);
463 key.specified = le16_to_cpu(buf16[items++]);
464
465 set = 0;
466 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
467 if (key.specified & spec_order[i])
468 set++;
469 }
470 if (!set || set > 1) {
471 ERR(fp->handle, "more than one specifier");
472 return -1;
473 }
474
475 rc = next_entry(buf32, fp, sizeof(uint32_t));
476 if (rc < 0) {
477 ERR(fp->handle, "truncated entry");
478 return -1;
479 }
480 datum.data = le32_to_cpu(*buf32);
481 return insertf(a, &key, &datum, p);
482 }
483
avtab_insertf(avtab_t * a,avtab_key_t * k,avtab_datum_t * d,void * p)484 static int avtab_insertf(avtab_t * a, avtab_key_t * k, avtab_datum_t * d,
485 void *p __attribute__ ((unused)))
486 {
487 return avtab_insert(a, k, d);
488 }
489
avtab_read(avtab_t * a,struct policy_file * fp,uint32_t vers)490 int avtab_read(avtab_t * a, struct policy_file *fp, uint32_t vers)
491 {
492 unsigned int i;
493 int rc;
494 uint32_t buf[1];
495 uint32_t nel;
496
497 rc = next_entry(buf, fp, sizeof(uint32_t));
498 if (rc < 0) {
499 ERR(fp->handle, "truncated table");
500 goto bad;
501 }
502 nel = le32_to_cpu(buf[0]);
503 if (!nel) {
504 ERR(fp->handle, "table is empty");
505 goto bad;
506 }
507
508 rc = avtab_alloc(a, nel);
509 if (rc) {
510 ERR(fp->handle, "out of memory");
511 goto bad;
512 }
513
514 for (i = 0; i < nel; i++) {
515 rc = avtab_read_item(fp, vers, a, avtab_insertf, NULL);
516 if (rc) {
517 if (rc == SEPOL_ENOMEM)
518 ERR(fp->handle, "out of memory");
519 if (rc == SEPOL_EEXIST)
520 ERR(fp->handle, "duplicate entry");
521 ERR(fp->handle, "failed on entry %d of %u", i, nel);
522 goto bad;
523 }
524 }
525
526 return 0;
527
528 bad:
529 avtab_destroy(a);
530 return -1;
531 }
532