2 * Implementation of the access vector table type.
4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
7 /* Updated: Frank Mayer <mayerf@tresys.com> and Karl MacMillan <kmacmillan@tresys.com>
9 * Added conditional policy language extensions
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.
17 #include <linux/kernel.h>
18 #include <linux/slab.h>
19 #include <linux/vmalloc.h>
20 #include <linux/errno.h>
25 #define AVTAB_HASH(keyp) \
26 ((keyp->target_class + \
27 (keyp->target_type << 2) + \
28 (keyp->source_type << 9)) & \
31 static struct kmem_cache *avtab_node_cachep;
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)
38 struct avtab_node * newnode;
39 newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
43 newnode->datum = *datum;
45 newnode->next = prev->next;
48 newnode->next = h->htable[hvalue];
49 h->htable[hvalue] = newnode;
56 static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum)
59 struct avtab_node *prev, *cur, *newnode;
60 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
65 hvalue = AVTAB_HASH(key);
66 for (prev = NULL, cur = h->htable[hvalue];
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 (specified & cur->key.specified))
74 if (key->source_type < cur->key.source_type)
76 if (key->source_type == cur->key.source_type &&
77 key->target_type < cur->key.target_type)
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)
85 newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
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.
97 avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_datum * datum)
100 struct avtab_node *prev, *cur, *newnode;
101 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
105 hvalue = AVTAB_HASH(key);
106 for (prev = NULL, cur = h->htable[hvalue];
108 prev = cur, cur = cur->next) {
109 if (key->source_type == cur->key.source_type &&
110 key->target_type == cur->key.target_type &&
111 key->target_class == cur->key.target_class &&
112 (specified & cur->key.specified))
114 if (key->source_type < cur->key.source_type)
116 if (key->source_type == cur->key.source_type &&
117 key->target_type < cur->key.target_type)
119 if (key->source_type == cur->key.source_type &&
120 key->target_type == cur->key.target_type &&
121 key->target_class < cur->key.target_class)
124 newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
129 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
132 struct avtab_node *cur;
133 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
138 hvalue = AVTAB_HASH(key);
139 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
140 if (key->source_type == cur->key.source_type &&
141 key->target_type == cur->key.target_type &&
142 key->target_class == cur->key.target_class &&
143 (specified & cur->key.specified))
146 if (key->source_type < cur->key.source_type)
148 if (key->source_type == cur->key.source_type &&
149 key->target_type < cur->key.target_type)
151 if (key->source_type == cur->key.source_type &&
152 key->target_type == cur->key.target_type &&
153 key->target_class < cur->key.target_class)
160 /* This search function returns a node pointer, and can be used in
161 * conjunction with avtab_search_next_node()
164 avtab_search_node(struct avtab *h, struct avtab_key *key)
167 struct avtab_node *cur;
168 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
173 hvalue = AVTAB_HASH(key);
174 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
175 if (key->source_type == cur->key.source_type &&
176 key->target_type == cur->key.target_type &&
177 key->target_class == cur->key.target_class &&
178 (specified & cur->key.specified))
181 if (key->source_type < cur->key.source_type)
183 if (key->source_type == cur->key.source_type &&
184 key->target_type < cur->key.target_type)
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)
195 avtab_search_node_next(struct avtab_node *node, int specified)
197 struct avtab_node *cur;
202 specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
203 for (cur = node->next; cur; cur = cur->next) {
204 if (node->key.source_type == cur->key.source_type &&
205 node->key.target_type == cur->key.target_type &&
206 node->key.target_class == cur->key.target_class &&
207 (specified & cur->key.specified))
210 if (node->key.source_type < cur->key.source_type)
212 if (node->key.source_type == cur->key.source_type &&
213 node->key.target_type < cur->key.target_type)
215 if (node->key.source_type == cur->key.source_type &&
216 node->key.target_type == cur->key.target_type &&
217 node->key.target_class < cur->key.target_class)
223 void avtab_destroy(struct avtab *h)
226 struct avtab_node *cur, *temp;
228 if (!h || !h->htable)
231 for (i = 0; i < AVTAB_SIZE; i++) {
233 while (cur != NULL) {
236 kmem_cache_free(avtab_node_cachep, temp);
245 int avtab_init(struct avtab *h)
249 h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
252 for (i = 0; i < AVTAB_SIZE; i++)
258 void avtab_hash_eval(struct avtab *h, char *tag)
260 int i, chain_len, slots_used, max_chain_len;
261 struct avtab_node *cur;
265 for (i = 0; i < AVTAB_SIZE; i++) {
275 if (chain_len > max_chain_len)
276 max_chain_len = chain_len;
280 printk(KERN_DEBUG "%s: %d entries and %d/%d buckets used, longest "
281 "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
285 static uint16_t spec_order[] = {
294 int avtab_read_item(void *fp, u32 vers, struct avtab *a,
295 int (*insertf)(struct avtab *a, struct avtab_key *k,
296 struct avtab_datum *d, void *p),
302 u32 items, items2, val;
303 struct avtab_key key;
304 struct avtab_datum datum;
307 memset(&key, 0, sizeof(struct avtab_key));
308 memset(&datum, 0, sizeof(struct avtab_datum));
310 if (vers < POLICYDB_VERSION_AVTAB) {
311 rc = next_entry(buf32, fp, sizeof(u32));
313 printk(KERN_ERR "security: avtab: truncated entry\n");
316 items2 = le32_to_cpu(buf32[0]);
317 if (items2 > ARRAY_SIZE(buf32)) {
318 printk(KERN_ERR "security: avtab: entry overflow\n");
322 rc = next_entry(buf32, fp, sizeof(u32)*items2);
324 printk(KERN_ERR "security: avtab: truncated entry\n");
329 val = le32_to_cpu(buf32[items++]);
330 key.source_type = (u16)val;
331 if (key.source_type != val) {
332 printk("security: avtab: truncated source type\n");
335 val = le32_to_cpu(buf32[items++]);
336 key.target_type = (u16)val;
337 if (key.target_type != val) {
338 printk("security: avtab: truncated target type\n");
341 val = le32_to_cpu(buf32[items++]);
342 key.target_class = (u16)val;
343 if (key.target_class != val) {
344 printk("security: avtab: truncated target class\n");
348 val = le32_to_cpu(buf32[items++]);
349 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
351 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
352 printk("security: avtab: null entry\n");
355 if ((val & AVTAB_AV) &&
356 (val & AVTAB_TYPE)) {
357 printk("security: avtab: entry has both access vectors and types\n");
361 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
362 if (val & spec_order[i]) {
363 key.specified = spec_order[i] | enabled;
364 datum.data = le32_to_cpu(buf32[items++]);
365 rc = insertf(a, &key, &datum, p);
370 if (items != items2) {
371 printk("security: avtab: entry only had %d items, expected %d\n", items2, items);
377 rc = next_entry(buf16, fp, sizeof(u16)*4);
379 printk("security: avtab: truncated entry\n");
384 key.source_type = le16_to_cpu(buf16[items++]);
385 key.target_type = le16_to_cpu(buf16[items++]);
386 key.target_class = le16_to_cpu(buf16[items++]);
387 key.specified = le16_to_cpu(buf16[items++]);
389 rc = next_entry(buf32, fp, sizeof(u32));
391 printk("security: avtab: truncated entry\n");
394 datum.data = le32_to_cpu(*buf32);
395 return insertf(a, &key, &datum, p);
398 static int avtab_insertf(struct avtab *a, struct avtab_key *k,
399 struct avtab_datum *d, void *p)
401 return avtab_insert(a, k, d);
404 int avtab_read(struct avtab *a, void *fp, u32 vers)
411 rc = next_entry(buf, fp, sizeof(u32));
413 printk(KERN_ERR "security: avtab: truncated table\n");
416 nel = le32_to_cpu(buf[0]);
418 printk(KERN_ERR "security: avtab: table is empty\n");
422 for (i = 0; i < nel; i++) {
423 rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
426 printk(KERN_ERR "security: avtab: out of memory\n");
427 else if (rc == -EEXIST)
428 printk(KERN_ERR "security: avtab: duplicate entry\n");
444 void avtab_cache_init(void)
446 avtab_node_cachep = kmem_cache_create("avtab_node",
447 sizeof(struct avtab_node),
448 0, SLAB_PANIC, NULL);
451 void avtab_cache_destroy(void)
453 kmem_cache_destroy (avtab_node_cachep);