URL https://opencores.org/ocsvn/test_project/test_project/trunk

Subversion Repositories test_project

[/] [test_project/] [trunk/] [linux_sd_driver/] [security/] [selinux/] [ss/] [avtab.c] - Blame information for rev 62

Details | Compare with Previous | View Log


/*
 * Implementation of the access vector table type.
 *
 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
 */
 
/* Updated: Frank Mayer <mayerf@tresys.com> and Karl MacMillan <kmacmillan@tresys.com>
 *
 *      Added conditional policy language extensions
 *
 * Copyright (C) 2003 Tresys Technology, LLC
 *      This program is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation, version 2.
 *
 * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
 *      Tuned number of hash slots for avtab to reduce memory usage
 */
 
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/errno.h>
#include "avtab.h"
#include "policydb.h"
 
static struct kmem_cache *avtab_node_cachep;
 
static inline int avtab_hash(struct avtab_key *keyp, u16 mask)
{
        return ((keyp->target_class + (keyp->target_type << 2) +
                 (keyp->source_type << 9)) & mask);
}
 
static struct avtab_node*
avtab_insert_node(struct avtab *h, int hvalue,
                  struct avtab_node * prev, struct avtab_node * cur,
                  struct avtab_key *key, struct avtab_datum *datum)
{
        struct avtab_node * newnode;
        newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
        if (newnode == NULL)
                return NULL;
        newnode->key = *key;
        newnode->datum = *datum;
        if (prev) {
                newnode->next = prev->next;
                prev->next = newnode;
        } else {
                newnode->next = h->htable[hvalue];
                h->htable[hvalue] = newnode;
        }
 
        h->nel++;
        return newnode;
}
 
static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum)
{
        int hvalue;
        struct avtab_node *prev, *cur, *newnode;
        u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
        if (!h || !h->htable)
                return -EINVAL;
 
        hvalue = avtab_hash(key, h->mask);
        for (prev = NULL, cur = h->htable[hvalue];
             cur;
             prev = cur, cur = cur->next) {
                if (key->source_type == cur->key.source_type &&
                    key->target_type == cur->key.target_type &&
                    key->target_class == cur->key.target_class &&
                    (specified & cur->key.specified))
                        return -EEXIST;
                if (key->source_type < cur->key.source_type)
                        break;
                if (key->source_type == cur->key.source_type &&
                    key->target_type < cur->key.target_type)
                        break;
                if (key->source_type == cur->key.source_type &&
                    key->target_type == cur->key.target_type &&
                    key->target_class < cur->key.target_class)
                        break;
        }
 
        newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
        if(!newnode)
                return -ENOMEM;
 
        return 0;
}
 
/* Unlike avtab_insert(), this function allow multiple insertions of the same
 * key/specified mask into the table, as needed by the conditional avtab.
 * It also returns a pointer to the node inserted.
 */
struct avtab_node *
avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_datum * datum)
{
        int hvalue;
        struct avtab_node *prev, *cur, *newnode;
        u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
        if (!h || !h->htable)
                return NULL;
        hvalue = avtab_hash(key, h->mask);
        for (prev = NULL, cur = h->htable[hvalue];
             cur;
             prev = cur, cur = cur->next) {
                if (key->source_type == cur->key.source_type &&
                    key->target_type == cur->key.target_type &&
                    key->target_class == cur->key.target_class &&
                    (specified & cur->key.specified))
                        break;
                if (key->source_type < cur->key.source_type)
                        break;
                if (key->source_type == cur->key.source_type &&
                    key->target_type < cur->key.target_type)
                        break;
                if (key->source_type == cur->key.source_type &&
                    key->target_type == cur->key.target_type &&
                    key->target_class < cur->key.target_class)
                        break;
        }
        newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
 
        return newnode;
}
 
struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
{
        int hvalue;
        struct avtab_node *cur;
        u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
        if (!h || !h->htable)
                return NULL;
 
        hvalue = avtab_hash(key, h->mask);
        for (cur = h->htable[hvalue]; cur; cur = cur->next) {
                if (key->source_type == cur->key.source_type &&
                    key->target_type == cur->key.target_type &&
                    key->target_class == cur->key.target_class &&
                    (specified & cur->key.specified))
                        return &cur->datum;
 
                if (key->source_type < cur->key.source_type)
                        break;
                if (key->source_type == cur->key.source_type &&
                    key->target_type < cur->key.target_type)
                        break;
                if (key->source_type == cur->key.source_type &&
                    key->target_type == cur->key.target_type &&
                    key->target_class < cur->key.target_class)
                        break;
        }
 
        return NULL;
}
 
/* This search function returns a node pointer, and can be used in
 * conjunction with avtab_search_next_node()
 */
struct avtab_node*
avtab_search_node(struct avtab *h, struct avtab_key *key)
{
        int hvalue;
        struct avtab_node *cur;
        u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
        if (!h || !h->htable)
                return NULL;
 
        hvalue = avtab_hash(key, h->mask);
        for (cur = h->htable[hvalue]; cur; cur = cur->next) {
                if (key->source_type == cur->key.source_type &&
                    key->target_type == cur->key.target_type &&
                    key->target_class == cur->key.target_class &&
                    (specified & cur->key.specified))
                        return cur;
 
                if (key->source_type < cur->key.source_type)
                        break;
                if (key->source_type == cur->key.source_type &&
                    key->target_type < cur->key.target_type)
                        break;
                if (key->source_type == cur->key.source_type &&
                    key->target_type == cur->key.target_type &&
                    key->target_class < cur->key.target_class)
                        break;
        }
        return NULL;
}
 
struct avtab_node*
avtab_search_node_next(struct avtab_node *node, int specified)
{
        struct avtab_node *cur;
 
        if (!node)
                return NULL;
 
        specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
        for (cur = node->next; cur; cur = cur->next) {
                if (node->key.source_type == cur->key.source_type &&
                    node->key.target_type == cur->key.target_type &&
                    node->key.target_class == cur->key.target_class &&
                    (specified & cur->key.specified))
                        return cur;
 
                if (node->key.source_type < cur->key.source_type)
                        break;
                if (node->key.source_type == cur->key.source_type &&
                    node->key.target_type < cur->key.target_type)
                        break;
                if (node->key.source_type == cur->key.source_type &&
                    node->key.target_type == cur->key.target_type &&
                    node->key.target_class < cur->key.target_class)
                        break;
        }
        return NULL;
}
 
void avtab_destroy(struct avtab *h)
{
        int i;
        struct avtab_node *cur, *temp;
 
        if (!h || !h->htable)
                return;
 
        for (i = 0; i < h->nslot; i++) {
                cur = h->htable[i];
                while (cur != NULL) {
                        temp = cur;
                        cur = cur->next;
                        kmem_cache_free(avtab_node_cachep, temp);
                }
                h->htable[i] = NULL;
        }
        kfree(h->htable);
        h->htable = NULL;
        h->nslot = 0;
        h->mask = 0;
}
 
int avtab_init(struct avtab *h)
{
        h->htable = NULL;
        h->nel = 0;
        return 0;
}
 
int avtab_alloc(struct avtab *h, u32 nrules)
{
        u16 mask = 0;
        u32 shift = 0;
        u32 work = nrules;
        u32 nslot = 0;
 
        if (nrules == 0)
                goto avtab_alloc_out;
 
        while (work) {
                work  = work >> 1;
                shift++;
        }
        if (shift > 2)
                shift = shift - 2;
        nslot = 1 << shift;
        if (nslot > MAX_AVTAB_SIZE)
                nslot = MAX_AVTAB_SIZE;
        mask = nslot - 1;
 
        h->htable = kcalloc(nslot, sizeof(*(h->htable)), GFP_KERNEL);
        if (!h->htable)
                return -ENOMEM;
 
 avtab_alloc_out:
        h->nel = 0;
        h->nslot = nslot;
        h->mask = mask;
        printk(KERN_DEBUG "SELinux:%d avtab hash slots allocated."
               "Num of rules:%d\n", h->nslot, nrules);
        return 0;
}
 
void avtab_hash_eval(struct avtab *h, char *tag)
{
        int i, chain_len, slots_used, max_chain_len;
        unsigned long long chain2_len_sum;
        struct avtab_node *cur;
 
        slots_used = 0;
        max_chain_len = 0;
        chain2_len_sum = 0;
        for (i = 0; i < h->nslot; i++) {
                cur = h->htable[i];
                if (cur) {
                        slots_used++;
                        chain_len = 0;
                        while (cur) {
                                chain_len++;
                                cur = cur->next;
                        }
 
                        if (chain_len > max_chain_len)
                                max_chain_len = chain_len;
                        chain2_len_sum += chain_len * chain_len;
                }
        }
 
        printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
               "chain length %d sum of chain length^2 %Lu\n",
               tag, h->nel, slots_used, h->nslot, max_chain_len,
               chain2_len_sum);
}
 
static uint16_t spec_order[] = {
        AVTAB_ALLOWED,
        AVTAB_AUDITDENY,
        AVTAB_AUDITALLOW,
        AVTAB_TRANSITION,
        AVTAB_CHANGE,
        AVTAB_MEMBER
};
 
int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
                    int (*insertf)(struct avtab *a, struct avtab_key *k,
                                   struct avtab_datum *d, void *p),
                    void *p)
{
        __le16 buf16[4];
        u16 enabled;
        __le32 buf32[7];
        u32 items, items2, val, vers = pol->policyvers;
        struct avtab_key key;
        struct avtab_datum datum;
        int i, rc;
        unsigned set;
 
        memset(&key, 0, sizeof(struct avtab_key));
        memset(&datum, 0, sizeof(struct avtab_datum));
 
        if (vers < POLICYDB_VERSION_AVTAB) {
                rc = next_entry(buf32, fp, sizeof(u32));
                if (rc < 0) {
                        printk(KERN_ERR "security: avtab: truncated entry\n");
                        return -1;
                }
                items2 = le32_to_cpu(buf32[0]);
                if (items2 > ARRAY_SIZE(buf32)) {
                        printk(KERN_ERR "security: avtab: entry overflow\n");
                        return -1;
 
                }
                rc = next_entry(buf32, fp, sizeof(u32)*items2);
                if (rc < 0) {
                        printk(KERN_ERR "security: avtab: truncated entry\n");
                        return -1;
                }
                items = 0;
 
                val = le32_to_cpu(buf32[items++]);
                key.source_type = (u16)val;
                if (key.source_type != val) {
                        printk("security: avtab: truncated source type\n");
                        return -1;
                }
                val = le32_to_cpu(buf32[items++]);
                key.target_type = (u16)val;
                if (key.target_type != val) {
                        printk("security: avtab: truncated target type\n");
                        return -1;
                }
                val = le32_to_cpu(buf32[items++]);
                key.target_class = (u16)val;
                if (key.target_class != val) {
                        printk("security: avtab: truncated target class\n");
                        return -1;
                }
 
                val = le32_to_cpu(buf32[items++]);
                enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
 
                if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
                        printk("security: avtab: null entry\n");
                        return -1;
                }
                if ((val & AVTAB_AV) &&
                    (val & AVTAB_TYPE)) {
                        printk("security: avtab: entry has both access vectors and types\n");
                        return -1;
                }
 
                for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
                        if (val & spec_order[i]) {
                                key.specified = spec_order[i] | enabled;
                                datum.data = le32_to_cpu(buf32[items++]);
                                rc = insertf(a, &key, &datum, p);
                                if (rc) return rc;
                        }
                }
 
                if (items != items2) {
                        printk("security: avtab: entry only had %d items, expected %d\n", items2, items);
                        return -1;
                }
                return 0;
        }
 
        rc = next_entry(buf16, fp, sizeof(u16)*4);
        if (rc < 0) {
                printk("security: avtab: truncated entry\n");
                return -1;
        }
 
        items = 0;
        key.source_type = le16_to_cpu(buf16[items++]);
        key.target_type = le16_to_cpu(buf16[items++]);
        key.target_class = le16_to_cpu(buf16[items++]);
        key.specified = le16_to_cpu(buf16[items++]);
 
        if (!policydb_type_isvalid(pol, key.source_type) ||
            !policydb_type_isvalid(pol, key.target_type) ||
            !policydb_class_isvalid(pol, key.target_class)) {
                printk(KERN_WARNING "security: avtab: invalid type or class\n");
                return -1;
        }
 
        set = 0;
        for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
                if (key.specified & spec_order[i])
                        set++;
        }
        if (!set || set > 1) {
                printk(KERN_WARNING
                        "security:  avtab:  more than one specifier\n");
                return -1;
        }
 
        rc = next_entry(buf32, fp, sizeof(u32));
        if (rc < 0) {
                printk("security: avtab: truncated entry\n");
                return -1;
        }
        datum.data = le32_to_cpu(*buf32);
        if ((key.specified & AVTAB_TYPE) &&
            !policydb_type_isvalid(pol, datum.data)) {
                printk(KERN_WARNING "security: avtab: invalid type\n");
                return -1;
        }
        return insertf(a, &key, &datum, p);
}
 
static int avtab_insertf(struct avtab *a, struct avtab_key *k,
                         struct avtab_datum *d, void *p)
{
        return avtab_insert(a, k, d);
}
 
int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
{
        int rc;
        __le32 buf[1];
        u32 nel, i;
 
 
        rc = next_entry(buf, fp, sizeof(u32));
        if (rc < 0) {
                printk(KERN_ERR "security: avtab: truncated table\n");
                goto bad;
        }
        nel = le32_to_cpu(buf[0]);
        if (!nel) {
                printk(KERN_ERR "security: avtab: table is empty\n");
                rc = -EINVAL;
                goto bad;
        }
 
        rc = avtab_alloc(a, nel);
        if (rc)
                goto bad;
 
        for (i = 0; i < nel; i++) {
                rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
                if (rc) {
                        if (rc == -ENOMEM)
                                printk(KERN_ERR "security: avtab: out of memory\n");
                        else if (rc == -EEXIST)
                                printk(KERN_ERR "security: avtab: duplicate entry\n");
                        else
                                rc = -EINVAL;
                        goto bad;
                }
        }
 
        rc = 0;
out:
        return rc;
 
bad:
        avtab_destroy(a);
        goto out;
}
 
void avtab_cache_init(void)
{
        avtab_node_cachep = kmem_cache_create("avtab_node",
                                              sizeof(struct avtab_node),
                                              0, SLAB_PANIC, NULL);
}
 
void avtab_cache_destroy(void)
{
        kmem_cache_destroy (avtab_node_cachep);
}

Browse

Tools

Subversion Repositories test_project

[/] [test_project/] [trunk/] [linux_sd_driver/] [security/] [selinux/] [ss/] [avtab.c] - Blame information for rev 62

Line No.	Rev	Author	Line
1	62	marcus.erl	`/*`
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.`
15			`*`
16			`* Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>`
17			`* Tuned number of hash slots for avtab to reduce memory usage`
18			`*/`
19
20			`#include <linux/kernel.h>`
21			`#include <linux/slab.h>`
22			`#include <linux/errno.h>`
23			`#include "avtab.h"`
24			`#include "policydb.h"`
25
26			`static struct kmem_cache *avtab_node_cachep;`
27
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
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;`
40			`newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);`
41			`if (newnode == NULL)`
42			`return NULL;`
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;`
61			`u16 specified = key->specified & ~(AVTAB_ENABLED\|AVTAB_ENABLED_OLD);`
62
63			`if (!h \|\| !h->htable)`
64			`return -EINVAL;`
65
66			`hvalue = avtab_hash(key, h->mask);`
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 &&`
73			`(specified & cur->key.specified))`
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;`
102			`u16 specified = key->specified & ~(AVTAB_ENABLED\|AVTAB_ENABLED_OLD);`
103
104			`if (!h \|\| !h->htable)`
105			`return NULL;`
106			`hvalue = avtab_hash(key, h->mask);`
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 &&`
113			`(specified & cur->key.specified))`
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
130			`struct avtab_datum avtab_search(struct avtab h, struct avtab_key *key)`
131			`{`
132			`int hvalue;`
133			`struct avtab_node *cur;`
134			`u16 specified = key->specified & ~(AVTAB_ENABLED\|AVTAB_ENABLED_OLD);`
135
136			`if (!h \|\| !h->htable)`
137			`return NULL;`
138
139			`hvalue = avtab_hash(key, h->mask);`
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 &&`
144			`(specified & cur->key.specified))`
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*`
165			`avtab_search_node(struct avtab h, struct avtab_key key)`
166			`{`
167			`int hvalue;`
168			`struct avtab_node *cur;`
169			`u16 specified = key->specified & ~(AVTAB_ENABLED\|AVTAB_ENABLED_OLD);`
170
171			`if (!h \|\| !h->htable)`
172			`return NULL;`
173
174			`hvalue = avtab_hash(key, h->mask);`
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 &&`
179			`(specified & cur->key.specified))`
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
203			`specified &= ~(AVTAB_ENABLED\|AVTAB_ENABLED_OLD);`
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 &&`
208			`(specified & cur->key.specified))`
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
232			`for (i = 0; i < h->nslot; i++) {`
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			`}`
241			`kfree(h->htable);`
242			`h->htable = NULL;`
243			`h->nslot = 0;`
244			`h->mask = 0;`
245			`}`
246
247			`int avtab_init(struct avtab *h)`
248			`{`
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;`
263
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);`
276			`if (!h->htable)`
277			`return -ENOMEM;`
278
279			`avtab_alloc_out:`
280			`h->nel = 0;`
281			`h->nslot = nslot;`
282			`h->mask = mask;`
283			`printk(KERN_DEBUG "SELinux:%d avtab hash slots allocated."`
284			`"Num of rules:%d\n", h->nslot, nrules);`
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;`
291			`unsigned long long chain2_len_sum;`
292			`struct avtab_node *cur;`
293
294			`slots_used = 0;`
295			`max_chain_len = 0;`
296			`chain2_len_sum = 0;`
297			`for (i = 0; i < h->nslot; i++) {`
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;`
309			`chain2_len_sum += chain_len * chain_len;`
310			`}`
311			`}`
312
313			`printk(KERN_DEBUG "%s: %d entries and %d/%d buckets used, longest "`
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);`
317			`}`
318
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
328			`int avtab_read_item(struct avtab a, void fp, struct policydb *pol,`
329			`int (insertf)(struct avtab a, struct avtab_key *k,`
330			`struct avtab_datum d, void p),`
331			`void *p)`
332			`{`
333			`__le16 buf16[4];`
334			`u16 enabled;`
335			`__le32 buf32[7];`
336			`u32 items, items2, val, vers = pol->policyvers;`
337			`struct avtab_key key;`
338			`struct avtab_datum datum;`
339			`int i, rc;`
340			`unsigned set;`
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;`
355
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;`
363
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
396			`for (i = 0; i < ARRAY_SIZE(spec_order); i++) {`
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;`
410			`}`
411
412			`rc = next_entry(buf16, fp, sizeof(u16)*4);`
413			`if (rc < 0) {`
414			`printk("security: avtab: truncated entry\n");`
415			`return -1;`
416			`}`
417
418			`items = 0;`
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
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
442			`rc = next_entry(buf32, fp, sizeof(u32));`
443			`if (rc < 0) {`
444			`printk("security: avtab: truncated entry\n");`
445			`return -1;`
446			`}`
447			`datum.data = le32_to_cpu(*buf32);`
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			`}`
453			`return insertf(a, &key, &datum, p);`
454			`}`
455
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);`
460			`}`
461
462			`int avtab_read(struct avtab a, void fp, struct policydb *pol)`
463			`{`
464			`int rc;`
465			`__le32 buf[1];`
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			`}`
480
481			`rc = avtab_alloc(a, nel);`
482			`if (rc)`
483			`goto bad;`
484
485			`for (i = 0; i < nel; i++) {`
486			`rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);`
487			`if (rc) {`
488			`if (rc == -ENOMEM)`
489			`printk(KERN_ERR "security: avtab: out of memory\n");`
490			`else if (rc == -EEXIST)`
491			`printk(KERN_ERR "security: avtab: duplicate entry\n");`
492			`else`
493			`rc = -EINVAL;`
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),`
511			`0, SLAB_PANIC, NULL);`
512			`}`
513
514			`void avtab_cache_destroy(void)`
515			`{`
516			`kmem_cache_destroy (avtab_node_cachep);`
517			`}`