From 34df25517a9bbec3436ab6f53074bcce9dc3eafc Mon Sep 17 00:00:00 2001 From: Kees Cook Date: Thu, 17 Aug 2023 13:22:17 -0700 Subject: selinux: Annotate struct sidtab_str_cache with __counted_by Prepare for the coming implementation by GCC and Clang of the __counted_by attribute. Flexible array members annotated with __counted_by can have their accesses bounds-checked at run-time checking via CONFIG_UBSAN_BOUNDS (for array indexing) and CONFIG_FORTIFY_SOURCE (for strcpy/memcpy-family functions). As found with Coccinelle[1], add __counted_by for struct sidtab_str_cache. [1] https://github.com/kees/kernel-tools/blob/trunk/coccinelle/examples/counted_by.cocci Cc: Paul Moore Cc: Stephen Smalley Cc: Eric Paris Cc: Ondrej Mosnacek Cc: selinux@vger.kernel.org Signed-off-by: Kees Cook Reviewed-by: "Gustavo A. R. Silva" Signed-off-by: Paul Moore --- security/selinux/ss/sidtab.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/sidtab.c b/security/selinux/ss/sidtab.c index d8ead463b8df..732fd8e22a12 100644 --- a/security/selinux/ss/sidtab.c +++ b/security/selinux/ss/sidtab.c @@ -25,7 +25,7 @@ struct sidtab_str_cache { struct list_head lru_member; struct sidtab_entry *parent; u32 len; - char str[]; + char str[] __counted_by(len); }; #define index_to_sid(index) ((index) + SECINITSID_NUM + 1) -- cgit v1.2.3 From fb8142ff4a642f14c4805980efb7531854c5dbdf Mon Sep 17 00:00:00 2001 From: Christian Göttsche Date: Fri, 18 Aug 2023 17:12:18 +0200 Subject: selinux: print sum of chain lengths^2 for hash tables MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Print the sum of chain lengths squared as a metric for hash tables to provide more insights, similar to avtabs. While on it add a comma in the avtab message to improve readability of the output. Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley Signed-off-by: Paul Moore --- security/selinux/ss/avtab.c | 2 +- security/selinux/ss/hashtab.c | 5 +++++ security/selinux/ss/hashtab.h | 1 + security/selinux/ss/policydb.c | 4 ++-- 4 files changed, 9 insertions(+), 3 deletions(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 86d98a8e291b..955cfe495606 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -349,7 +349,7 @@ void avtab_hash_eval(struct avtab *h, const char *tag) } pr_debug("SELinux: %s: %d entries and %d/%d buckets used, " - "longest chain length %d sum of chain length^2 %llu\n", + "longest chain length %d, sum of chain length^2 %llu\n", tag, h->nel, slots_used, h->nslot, max_chain_len, chain2_len_sum); } diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c index ac5cdddfbf78..c05d8346a94a 100644 --- a/security/selinux/ss/hashtab.c +++ b/security/selinux/ss/hashtab.c @@ -107,10 +107,12 @@ int hashtab_map(struct hashtab *h, void hashtab_stat(struct hashtab *h, struct hashtab_info *info) { u32 i, chain_len, slots_used, max_chain_len; + u64 chain2_len_sum; struct hashtab_node *cur; slots_used = 0; max_chain_len = 0; + chain2_len_sum = 0; for (i = 0; i < h->size; i++) { cur = h->htable[i]; if (cur) { @@ -123,11 +125,14 @@ void hashtab_stat(struct hashtab *h, struct hashtab_info *info) if (chain_len > max_chain_len) max_chain_len = chain_len; + + chain2_len_sum += (u64)chain_len * chain_len; } } info->slots_used = slots_used; info->max_chain_len = max_chain_len; + info->chain2_len_sum = chain2_len_sum; } #endif /* CONFIG_SECURITY_SELINUX_DEBUG */ diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h index f9713b56d3d0..09b0a3744937 100644 --- a/security/selinux/ss/hashtab.h +++ b/security/selinux/ss/hashtab.h @@ -38,6 +38,7 @@ struct hashtab { struct hashtab_info { u32 slots_used; u32 max_chain_len; + u64 chain2_len_sum; }; /* diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c index 2d528f699a22..d420c6c12f54 100644 --- a/security/selinux/ss/policydb.c +++ b/security/selinux/ss/policydb.c @@ -684,9 +684,9 @@ static void hash_eval(struct hashtab *h, const char *hash_name) struct hashtab_info info; hashtab_stat(h, &info); - pr_debug("SELinux: %s: %d entries and %d/%d buckets used, longest chain length %d\n", + pr_debug("SELinux: %s: %d entries and %d/%d buckets used, longest chain length %d, sum of chain length^2 %llu\n", hash_name, h->nel, info.slots_used, h->size, - info.max_chain_len); + info.max_chain_len, info.chain2_len_sum); } static void symtab_hash_eval(struct symtab *s) -- cgit v1.2.3 From 6f594f5a3dc4917be1556e524673420197ca471d Mon Sep 17 00:00:00 2001 From: Christian Göttsche Date: Fri, 18 Aug 2023 17:12:14 +0200 Subject: selinux: improve debug configuration MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit If the SELinux debug configuration is enabled define the macro DEBUG such that pr_debug() calls are always enabled, regardless of CONFIG_DYNAMIC_DEBUG, since those message are the main reason for this configuration in the first place. Mention example usage in case CONFIG_DYNAMIC_DEBUG is enabled in the help section of the configuration. Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley Signed-off-by: Paul Moore --- security/selinux/Kconfig | 10 ++++++++++ security/selinux/Makefile | 2 ++ 2 files changed, 12 insertions(+) (limited to 'security/selinux') diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig index d30348fbe0df..61abc1e094a8 100644 --- a/security/selinux/Kconfig +++ b/security/selinux/Kconfig @@ -77,3 +77,13 @@ config SECURITY_SELINUX_DEBUG This enables debugging code designed to help SELinux kernel developers, unless you know what this does in the kernel code you should leave this disabled. + + To fine control the messages to be printed enable + CONFIG_DYNAMIC_DEBUG and see + Documentation/admin-guide/dynamic-debug-howto.rst for additional + information. + + Example usage: + + echo -n 'file "security/selinux/*" +p' > \ + /proc/dynamic_debug/control diff --git a/security/selinux/Makefile b/security/selinux/Makefile index 836379639058..c47519ed8156 100644 --- a/security/selinux/Makefile +++ b/security/selinux/Makefile @@ -12,6 +12,8 @@ obj-$(CONFIG_SECURITY_SELINUX) := selinux.o ccflags-y := -I$(srctree)/security/selinux -I$(srctree)/security/selinux/include +ccflags-$(CONFIG_SECURITY_SELINUX_DEBUG) += -DDEBUG + selinux-y := avc.o hooks.o selinuxfs.o netlink.o nlmsgtab.o netif.o \ netnode.o netport.o status.o \ ss/ebitmap.o ss/hashtab.o ss/symtab.o ss/sidtab.o ss/avtab.o \ -- cgit v1.2.3 From 7969ba577636a83553baf95882eb310b39e1c742 Mon Sep 17 00:00:00 2001 From: Christian Göttsche Date: Fri, 18 Aug 2023 17:12:15 +0200 Subject: selinux: simplify avtab slot calculation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Instead of dividing by 8 and then performing log2 by hand, use a more readable calculation. The behavior of rounddown_pow_of_two() for an input of 0 is undefined, so handle that case and small values manually to achieve the same results. Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley Signed-off-by: Paul Moore --- security/selinux/ss/avtab.c | 8 +------- 1 file changed, 1 insertion(+), 7 deletions(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 955cfe495606..1d1ffe085b35 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -298,13 +298,7 @@ int avtab_alloc(struct avtab *h, u32 nrules) u32 nslot = 0; if (nrules != 0) { - u32 shift = 1; - u32 work = nrules >> 3; - while (work) { - work >>= 1; - shift++; - } - nslot = 1 << shift; + nslot = nrules > 3 ? rounddown_pow_of_two(nrules / 2) : 2; if (nslot > MAX_AVTAB_HASH_BUCKETS) nslot = MAX_AVTAB_HASH_BUCKETS; -- cgit v1.2.3 From 37b7ea3ca3062f5b7f02c2b335f203e4d411793d Mon Sep 17 00:00:00 2001 From: Christian Göttsche Date: Fri, 18 Aug 2023 17:12:16 +0200 Subject: selinux: improve role transition hashing MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The number of buckets is calculated by performing a binary AND against the mask of the hash table, which is one less than its size (which is a power of two). This leads to all top bits being discarded, e.g. with the Reference Policy on Debian there exists 376 entries, leading to a size of 512, discarding the top 23 bits. Use jhash to improve the hash table utilization: # current roletr: 376 entries and 124/512 buckets used, longest chain length 8, sum of chain length^2 1496 # patch roletr: 376 entries and 266/512 buckets used, longest chain length 4, sum of chain length^2 646 Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley [PM: line wrap in the commit description] Signed-off-by: Paul Moore --- security/selinux/ss/policydb.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c index d420c6c12f54..595a435ea9c8 100644 --- a/security/selinux/ss/policydb.c +++ b/security/selinux/ss/policydb.c @@ -491,7 +491,7 @@ static u32 role_trans_hash(const void *k) { const struct role_trans_key *key = k; - return key->role + (key->type << 3) + (key->tclass << 5); + return jhash_3words(key->role, key->type, (u32)key->tclass << 16 | key->tclass, 0); } static int role_trans_cmp(const void *k1, const void *k2) -- cgit v1.2.3 From 9d140885e35dac6dff2c56eccacc13f4fc96188a Mon Sep 17 00:00:00 2001 From: Jacob Satterfield Date: Wed, 6 Sep 2023 15:46:06 +0000 Subject: selinux: hweight optimization in avtab_read_item avtab_read_item() is a hot function called when reading each rule in a binary policydb. With the current Fedora policy and refpolicy, this function is called nearly 100,000 times per policy load. A single avtab node is only permitted to have a single specifier to describe the data it holds. As such, a check is performed to make sure only one specifier is set. Previously this was done via a for-loop. However, there is already an optimal function for finding the number of bits set (hamming weight) and on some architectures, dedicated instructions (popcount) which can be executed much more efficiently. Even when using -mcpu=generic on a x86-64 Fedora 38 VM, this commit results in a modest 2-4% speedup for policy loading due to a substantial reduction in the number of instructions executed. Signed-off-by: Jacob Satterfield Reviewed-by: Stephen Smalley Signed-off-by: Paul Moore --- security/selinux/ss/avtab.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 1d1ffe085b35..095b8cd24806 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -17,6 +17,7 @@ * Tuned number of hash slots for avtab to reduce memory usage */ +#include #include #include #include @@ -471,11 +472,7 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, return -EINVAL; } - set = 0; - for (i = 0; i < ARRAY_SIZE(spec_order); i++) { - if (key.specified & spec_order[i]) - set++; - } + set = hweight16(key.specified & (AVTAB_XPERMS | AVTAB_TYPE | AVTAB_AV)); if (!set || set > 1) { pr_err("SELinux: avtab: more than one specifier\n"); return -EINVAL; -- cgit v1.2.3 From 19c1c9916dbf9b05157a0c4970f61f952c0cb86a Mon Sep 17 00:00:00 2001 From: Jacob Satterfield Date: Fri, 29 Sep 2023 19:56:12 +0000 Subject: selinux: simplify avtab_insert_node() prototype __hashtab_insert() in hashtab.h has a cleaner interface that allows the caller to specify the chain node location that the new node is being inserted into so that it can update the node that currently occupies it. Signed-off-by: Jacob Satterfield Reviewed-by: Stephen Smalley Signed-off-by: Paul Moore --- security/selinux/ss/avtab.c | 20 +++++++------------- 1 file changed, 7 insertions(+), 13 deletions(-) (limited to 'security/selinux') diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 095b8cd24806..8751a602ead2 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -67,8 +67,7 @@ static inline u32 avtab_hash(const struct avtab_key *keyp, u32 mask) } static struct avtab_node* -avtab_insert_node(struct avtab *h, u32 hvalue, - struct avtab_node *prev, +avtab_insert_node(struct avtab *h, struct avtab_node **dst, const struct avtab_key *key, const struct avtab_datum *datum) { struct avtab_node *newnode; @@ -90,15 +89,8 @@ avtab_insert_node(struct avtab *h, u32 hvalue, newnode->datum.u.data = datum->u.data; } - if (prev) { - newnode->next = prev->next; - prev->next = newnode; - } else { - struct avtab_node **n = &h->htable[hvalue]; - - newnode->next = *n; - *n = newnode; - } + newnode->next = *dst; + *dst = newnode; h->nel++; return newnode; @@ -138,7 +130,8 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key, break; } - newnode = avtab_insert_node(h, hvalue, prev, key, datum); + newnode = avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue], + key, datum); if (!newnode) return -ENOMEM; @@ -178,7 +171,8 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h, key->target_class < cur->key.target_class) break; } - return avtab_insert_node(h, hvalue, prev, key, datum); + return avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue], + key, datum); } /* This search function returns a node pointer, and can be used in -- cgit v1.2.3