diff options
Diffstat (limited to 'security/selinux/ss/avtab.c')
-rw-r--r-- | security/selinux/ss/avtab.c | 72 |
1 files changed, 56 insertions, 16 deletions
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index a3dd9faa19c0..b64f2772b030 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -25,10 +25,43 @@ static struct kmem_cache *avtab_node_cachep; -static inline int avtab_hash(struct avtab_key *keyp, u16 mask) +/* Based on MurmurHash3, written by Austin Appleby and placed in the + * public domain. + */ +static inline int avtab_hash(struct avtab_key *keyp, u32 mask) { - return ((keyp->target_class + (keyp->target_type << 2) + - (keyp->source_type << 9)) & mask); + static const u32 c1 = 0xcc9e2d51; + static const u32 c2 = 0x1b873593; + static const u32 r1 = 15; + static const u32 r2 = 13; + static const u32 m = 5; + static const u32 n = 0xe6546b64; + + u32 hash = 0; + +#define mix(input) { \ + u32 v = input; \ + v *= c1; \ + v = (v << r1) | (v >> (32 - r1)); \ + v *= c2; \ + hash ^= v; \ + hash = (hash << r2) | (hash >> (32 - r2)); \ + hash = hash * m + n; \ +} + + mix(keyp->target_class); + mix(keyp->target_type); + mix(keyp->source_type); + +#undef mix + + hash ^= hash >> 16; + hash *= 0x85ebca6b; + hash ^= hash >> 13; + hash *= 0xc2b2ae35; + hash ^= hash >> 16; + + return hash & mask; } static struct avtab_node* @@ -46,8 +79,12 @@ avtab_insert_node(struct avtab *h, int hvalue, newnode->next = prev->next; prev->next = newnode; } else { - newnode->next = h->htable[hvalue]; - h->htable[hvalue] = newnode; + newnode->next = flex_array_get_ptr(h->htable, hvalue); + if (flex_array_put_ptr(h->htable, hvalue, newnode, + GFP_KERNEL|__GFP_ZERO)) { + kmem_cache_free(avtab_node_cachep, newnode); + return NULL; + } } h->nel++; @@ -64,7 +101,7 @@ static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_dat return -EINVAL; hvalue = avtab_hash(key, h->mask); - for (prev = NULL, cur = h->htable[hvalue]; + for (prev = NULL, cur = flex_array_get_ptr(h->htable, hvalue); cur; prev = cur, cur = cur->next) { if (key->source_type == cur->key.source_type && @@ -104,7 +141,7 @@ avtab_insert_nonunique(struct avtab *h, struct avtab_key *key, struct avtab_datu if (!h || !h->htable) return NULL; hvalue = avtab_hash(key, h->mask); - for (prev = NULL, cur = h->htable[hvalue]; + for (prev = NULL, cur = flex_array_get_ptr(h->htable, hvalue); cur; prev = cur, cur = cur->next) { if (key->source_type == cur->key.source_type && @@ -135,7 +172,8 @@ struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key) return NULL; hvalue = avtab_hash(key, h->mask); - for (cur = h->htable[hvalue]; cur; cur = cur->next) { + for (cur = flex_array_get_ptr(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 && @@ -170,7 +208,8 @@ avtab_search_node(struct avtab *h, struct avtab_key *key) return NULL; hvalue = avtab_hash(key, h->mask); - for (cur = h->htable[hvalue]; cur; cur = cur->next) { + for (cur = flex_array_get_ptr(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 && @@ -228,15 +267,14 @@ void avtab_destroy(struct avtab *h) return; for (i = 0; i < h->nslot; i++) { - cur = h->htable[i]; + cur = flex_array_get_ptr(h->htable, i); while (cur) { temp = cur; cur = cur->next; kmem_cache_free(avtab_node_cachep, temp); } - h->htable[i] = NULL; } - kfree(h->htable); + flex_array_free(h->htable); h->htable = NULL; h->nslot = 0; h->mask = 0; @@ -251,7 +289,7 @@ int avtab_init(struct avtab *h) int avtab_alloc(struct avtab *h, u32 nrules) { - u16 mask = 0; + u32 mask = 0; u32 shift = 0; u32 work = nrules; u32 nslot = 0; @@ -270,7 +308,8 @@ int avtab_alloc(struct avtab *h, u32 nrules) nslot = MAX_AVTAB_HASH_BUCKETS; mask = nslot - 1; - h->htable = kcalloc(nslot, sizeof(*(h->htable)), GFP_KERNEL); + h->htable = flex_array_alloc(sizeof(struct avtab_node *), nslot, + GFP_KERNEL | __GFP_ZERO); if (!h->htable) return -ENOMEM; @@ -293,7 +332,7 @@ void avtab_hash_eval(struct avtab *h, char *tag) max_chain_len = 0; chain2_len_sum = 0; for (i = 0; i < h->nslot; i++) { - cur = h->htable[i]; + cur = flex_array_get_ptr(h->htable, i); if (cur) { slots_used++; chain_len = 0; @@ -534,7 +573,8 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp) return rc; for (i = 0; i < a->nslot; i++) { - for (cur = a->htable[i]; cur; cur = cur->next) { + for (cur = flex_array_get_ptr(a->htable, i); cur; + cur = cur->next) { rc = avtab_write_item(p, cur, fp); if (rc) return rc; |