From 83d4a806ae46397f606de7376b831524bd3a21e5 Mon Sep 17 00:00:00 2001 From: Jeff Vander Stoep Date: Thu, 26 Feb 2015 13:54:17 -0800 Subject: selinux: remove unnecessary pointer reassignment Commit f01e1af445fa ("selinux: don't pass in NULL avd to avc_has_perm_noaudit") made this pointer reassignment unnecessary. Avd should continue to reference the stack-based copy. Signed-off-by: Jeff Vander Stoep Acked-by: Stephen Smalley [PM: tweaked subject line] Signed-off-by: Paul Moore --- security/selinux/avc.c | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'security/selinux') diff --git a/security/selinux/avc.c b/security/selinux/avc.c index afcc0aed9393..3c17dda9571d 100644 --- a/security/selinux/avc.c +++ b/security/selinux/avc.c @@ -724,12 +724,10 @@ inline int avc_has_perm_noaudit(u32 ssid, u32 tsid, rcu_read_lock(); node = avc_lookup(ssid, tsid, tclass); - if (unlikely(!node)) { + if (unlikely(!node)) node = avc_compute_av(ssid, tsid, tclass, avd); - } else { + else memcpy(avd, &node->ae.avd, sizeof(*avd)); - avd = &node->ae.avd; - } denied = requested & ~(avd->allowed); if (unlikely(denied)) -- cgit v1.2.3 From da8026fa0f9154b1c571c4d160dd51a7b8c34495 Mon Sep 17 00:00:00 2001 From: Paul Moore Date: Tue, 17 Feb 2015 15:30:23 -0500 Subject: selinux: reconcile security_netlbl_secattr_to_sid() and mls_import_netlbl_cat() Move the NetLabel secattr MLS category import logic into mls_import_netlbl_cat() where it belongs, and use the mls_import_netlbl_cat() function in security_netlbl_secattr_to_sid(). Reported-by: Rickard Strandqvist Signed-off-by: Paul Moore --- security/selinux/ss/mls.c | 10 +++------- security/selinux/ss/services.c | 6 +----- 2 files changed, 4 insertions(+), 12 deletions(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/mls.c b/security/selinux/ss/mls.c index d307b37ddc2b..e1088842232c 100644 --- a/security/selinux/ss/mls.c +++ b/security/selinux/ss/mls.c @@ -654,19 +654,15 @@ int mls_import_netlbl_cat(struct context *context, rc = ebitmap_netlbl_import(&context->range.level[0].cat, secattr->attr.mls.cat); - if (rc != 0) - goto import_netlbl_cat_failure; - - rc = ebitmap_cpy(&context->range.level[1].cat, - &context->range.level[0].cat); - if (rc != 0) + if (rc) goto import_netlbl_cat_failure; + memcpy(&context->range.level[1].cat, &context->range.level[0].cat, + sizeof(context->range.level[0].cat)); return 0; import_netlbl_cat_failure: ebitmap_destroy(&context->range.level[0].cat); - ebitmap_destroy(&context->range.level[1].cat); return rc; } #endif /* CONFIG_NETLABEL */ diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c index a1d3944751b9..9e2d82070915 100644 --- a/security/selinux/ss/services.c +++ b/security/selinux/ss/services.c @@ -3179,13 +3179,9 @@ int security_netlbl_secattr_to_sid(struct netlbl_lsm_secattr *secattr, ctx_new.type = ctx->type; mls_import_netlbl_lvl(&ctx_new, secattr); if (secattr->flags & NETLBL_SECATTR_MLS_CAT) { - rc = ebitmap_netlbl_import(&ctx_new.range.level[0].cat, - secattr->attr.mls.cat); + rc = mls_import_netlbl_cat(&ctx_new, secattr); if (rc) goto out; - memcpy(&ctx_new.range.level[1].cat, - &ctx_new.range.level[0].cat, - sizeof(ctx_new.range.level[0].cat)); } rc = -EIDRM; if (!mls_context_isvalid(&policydb, &ctx_new)) -- cgit v1.2.3 From ba39db6e0519aa8362dbda6523ceb69349a18dc3 Mon Sep 17 00:00:00 2001 From: Stephen Smalley Date: Tue, 24 Mar 2015 16:54:16 -0400 Subject: selinux: convert avtab hash table to flex_array Previously we shrank the avtab max hash buckets to avoid high order memory allocations, but this causes avtab lookups to degenerate to very long linear searches for the Fedora policy. Convert to using a flex_array instead so that we can increase the buckets without such limitations. This change does not alter the max hash buckets; that is left to a separate follow-on change. Signed-off-by: Stephen Smalley Signed-off-by: Paul Moore --- security/selinux/ss/avtab.c | 31 +++++++++++++++++++------------ security/selinux/ss/avtab.h | 4 +++- 2 files changed, 22 insertions(+), 13 deletions(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index a3dd9faa19c0..3ea0198fc964 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -46,8 +46,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 +68,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 +108,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 +139,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 +175,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 +234,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; @@ -270,7 +275,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 +299,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 +540,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; diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h index 63ce2f9e441d..9318b2b8f6c9 100644 --- a/security/selinux/ss/avtab.h +++ b/security/selinux/ss/avtab.h @@ -23,6 +23,8 @@ #ifndef _SS_AVTAB_H_ #define _SS_AVTAB_H_ +#include + struct avtab_key { u16 source_type; /* source type */ u16 target_type; /* target type */ @@ -51,7 +53,7 @@ struct avtab_node { }; struct avtab { - struct avtab_node **htable; + struct flex_array *htable; u32 nel; /* number of elements */ u32 nslot; /* number of hash slots */ u16 mask; /* mask to compute hash func */ -- cgit v1.2.3 From 33ebc1932a07efd8728975750409741940334489 Mon Sep 17 00:00:00 2001 From: John Brooks Date: Tue, 24 Mar 2015 16:54:17 -0400 Subject: selinux: Use a better hash function for avtab This function, based on murmurhash3, has much better distribution than the original. Using the current default of 2048 buckets, there are many fewer collisions: Before: 101421 entries and 2048/2048 buckets used, longest chain length 374 After: 101421 entries and 2048/2048 buckets used, longest chain length 81 The difference becomes much more significant when buckets are increased. A naive attempt to expand the current function to larger outputs doesn't yield any significant improvement; so this function is a prerequisite for increasing the bucket size. sds: Adapted from the original patches for libsepol to the kernel. Signed-off-by: John Brooks Signed-off-by: Stephen Smalley Signed-off-by: Paul Moore --- security/selinux/ss/avtab.c | 41 +++++++++++++++++++++++++++++++++++++---- security/selinux/ss/avtab.h | 2 +- 2 files changed, 38 insertions(+), 5 deletions(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 3ea0198fc964..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* @@ -256,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; diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h index 9318b2b8f6c9..6d794a2eee57 100644 --- a/security/selinux/ss/avtab.h +++ b/security/selinux/ss/avtab.h @@ -56,7 +56,7 @@ struct avtab { struct flex_array *htable; u32 nel; /* number of elements */ u32 nslot; /* number of hash slots */ - u16 mask; /* mask to compute hash func */ + u32 mask; /* mask to compute hash func */ }; -- cgit v1.2.3 From cf7b6c0205f11cdb015384244c0b423b00e35c69 Mon Sep 17 00:00:00 2001 From: Stephen Smalley Date: Tue, 24 Mar 2015 16:54:18 -0400 Subject: selinux: increase avtab max buckets Now that we can safely increase the avtab max buckets without triggering high order allocations and have a hash function that will make better use of the larger number of buckets, increase the max buckets to 2^16. Original: 101421 entries and 2048/2048 buckets used, longest chain length 374 With new hash function: 101421 entries and 2048/2048 buckets used, longest chain length 81 With increased max buckets: 101421 entries and 31078/32768 buckets used, longest chain length 12 Signed-off-by: Stephen Smalley Signed-off-by: Paul Moore --- security/selinux/ss/avtab.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h index 6d794a2eee57..adb451cd44f9 100644 --- a/security/selinux/ss/avtab.h +++ b/security/selinux/ss/avtab.h @@ -86,7 +86,7 @@ struct avtab_node *avtab_search_node_next(struct avtab_node *node, int specified void avtab_cache_init(void); void avtab_cache_destroy(void); -#define MAX_AVTAB_HASH_BITS 11 +#define MAX_AVTAB_HASH_BITS 16 #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS) #endif /* _SS_AVTAB_H_ */ -- cgit v1.2.3