[RFC PATCH] selinux: assorted hash table improvements

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



From: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>

This is an inline patch version of a patch submitted by Linus in the
thread below.  Do not merge this patch anywhere without additional
testing or a proper commit message.

* https://lore.kernel.org/selinux/20231111160954.45911-2-paul@xxxxxxxxxxxxxx
---
 security/selinux/ss/hashtab.c  | 78 +++++++++++++++++-----------------
 security/selinux/ss/hashtab.h  | 41 ++++++++++--------
 security/selinux/ss/policydb.c |  2 +-
 3 files changed, 64 insertions(+), 57 deletions(-)

diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
index c05d8346a94a..b4bc1aebebe6 100644
--- a/security/selinux/ss/hashtab.c
+++ b/security/selinux/ss/hashtab.c
@@ -24,25 +24,27 @@ static struct kmem_cache *hashtab_node_cachep __ro_after_init;
  * The total memory used by the htable arrays (only) with Fedora policy loaded
  * is approximately 163 KB at the time of writing.
  */
-static u32 hashtab_compute_size(u32 nel)
+static u32 hashtab_compute_hbits(u32 nel)
 {
-	return nel == 0 ? 0 : roundup_pow_of_two(nel);
+	if (nel <= 1)
+		return nel;
+	return ilog2(nel - 1) + 1;
 }
 
 int hashtab_init(struct hashtab *h, u32 nel_hint)
 {
-	u32 size = hashtab_compute_size(nel_hint);
+	u32 hbits = hashtab_compute_hbits(nel_hint);
 
 	/* should already be zeroed, but better be safe */
 	h->nel = 0;
-	h->size = 0;
+	h->hbits = 0;
 	h->htable = NULL;
 
-	if (size) {
-		h->htable = kcalloc(size, sizeof(*h->htable), GFP_KERNEL);
+	if (hbits) {
+		h->htable = kcalloc(1 << hbits, sizeof(*h->htable), GFP_KERNEL);
 		if (!h->htable)
 			return -ENOMEM;
-		h->size = size;
+		h->hbits = hbits;
 	}
 	return 0;
 }
@@ -66,10 +68,11 @@ int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
 
 void hashtab_destroy(struct hashtab *h)
 {
-	u32 i;
-	struct hashtab_node *cur, *temp;
+	u32 size = hashtab_size(h);
+
+	for (u32 i = 0; i < size; i++) {
+		struct hashtab_node *cur, *temp;
 
-	for (i = 0; i < h->size; i++) {
 		cur = h->htable[i];
 		while (cur) {
 			temp = cur;
@@ -81,20 +84,19 @@ void hashtab_destroy(struct hashtab *h)
 
 	kfree(h->htable);
 	h->htable = NULL;
+	h->hbits = 0;
 }
 
 int hashtab_map(struct hashtab *h,
 		int (*apply)(void *k, void *d, void *args),
 		void *args)
 {
-	u32 i;
-	int ret;
-	struct hashtab_node *cur;
+	u32 size = hashtab_size(h);
 
-	for (i = 0; i < h->size; i++) {
-		cur = h->htable[i];
+	for (u32 i = 0; i < size; i++) {
+		struct hashtab_node *cur = cur = h->htable[i];
 		while (cur) {
-			ret = apply(cur->key, cur->datum, args);
+			int ret = apply(cur->key, cur->datum, args);
 			if (ret)
 				return ret;
 			cur = cur->next;
@@ -106,18 +108,18 @@ int hashtab_map(struct hashtab *h,
 #ifdef CONFIG_SECURITY_SELINUX_DEBUG
 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 {
-	u32 i, chain_len, slots_used, max_chain_len;
+	u32 size = hashtab_size(h);
+	u32 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];
+	for (u32 i = 0; i < size; i++) {
+		struct hashtab_node *cur = h->htable[i];
 		if (cur) {
+			u32 chain_len = 0;
 			slots_used++;
-			chain_len = 0;
 			while (cur) {
 				chain_len++;
 				cur = cur->next;
@@ -142,36 +144,35 @@ int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
 		int (*destroy)(void *k, void *d, void *args),
 		void *args)
 {
-	struct hashtab_node *cur, *tmp, *tail;
-	u32 i;
-	int rc;
+	u32 size = hashtab_size(orig);
 
 	memset(new, 0, sizeof(*new));
 
-	new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL);
-	if (!new->htable)
-		return -ENOMEM;
+	if (size) {
+		new->htable = kcalloc(size, sizeof(*new->htable), GFP_KERNEL);
+		if (!new->htable)
+			return -ENOMEM;
+		new->hbits = orig->hbits;
+	}
 
-	new->size = orig->size;
+	for (u32 i = 0; i < size; i++) {
+		struct hashtab_node *cur, **tailp;
+		tailp = new->htable + i;
 
-	for (i = 0; i < orig->size; i++) {
-		tail = NULL;
 		for (cur = orig->htable[i]; cur; cur = cur->next) {
+			struct hashtab_node *tmp;
+
 			tmp = kmem_cache_zalloc(hashtab_node_cachep,
 						GFP_KERNEL);
 			if (!tmp)
 				goto error;
-			rc = copy(tmp, cur, args);
-			if (rc) {
+			if (copy(tmp, cur, args)) {
 				kmem_cache_free(hashtab_node_cachep, tmp);
 				goto error;
 			}
 			tmp->next = NULL;
-			if (!tail)
-				new->htable[i] = tmp;
-			else
-				tail->next = tmp;
-			tail = tmp;
+			*tailp = tmp;
+			tailp = &tmp->next;
 			new->nel++;
 		}
 	}
@@ -179,7 +180,8 @@ int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
 	return 0;
 
  error:
-	for (i = 0; i < new->size; i++) {
+	for (u32 i = 0; i < size; i++) {
+		struct hashtab_node *cur, *tmp;
 		for (cur = new->htable[i]; cur; cur = tmp) {
 			tmp = cur->next;
 			destroy(cur->key, cur->datum, args);
diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h
index 09b0a3744937..6b65c9a52559 100644
--- a/security/selinux/ss/hashtab.h
+++ b/security/selinux/ss/hashtab.h
@@ -14,6 +14,7 @@
 #include <linux/types.h>
 #include <linux/errno.h>
 #include <linux/sched.h>
+#include <linux/hash.h>
 
 #define HASHTAB_MAX_NODES	U32_MAX
 
@@ -31,7 +32,7 @@ struct hashtab_node {
 
 struct hashtab {
 	struct hashtab_node **htable;	/* hash table */
-	u32 size;			/* number of slots in hash table */
+	u32 hbits;			/* number of slots in hash table */
 	u32 nel;			/* number of elements in hash table */
 };
 
@@ -41,6 +42,11 @@ struct hashtab_info {
 	u64 chain2_len_sum;
 };
 
+static inline u32 hashtab_size(const struct hashtab *h)
+{
+	return h->hbits ? 1 << h->hbits : 0;
+}
+
 /*
  * Initializes a new hash table with the specified characteristics.
  *
@@ -51,6 +57,12 @@ int hashtab_init(struct hashtab *h, u32 nel_hint);
 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
 		     void *key, void *datum);
 
+static inline struct hashtab_node **hashtab_entry(struct hashtab *h,
+	const void *key, const struct hashtab_key_params key_params)
+{
+	return h->htable + hash_32(key_params.hash(key), h->hbits);
+}
+
 /*
  * Inserts the specified (key, datum) pair into the specified hash table.
  *
@@ -60,32 +72,27 @@ int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
   0 otherwise.
  */
 static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
-				 struct hashtab_key_params key_params)
+				 const struct hashtab_key_params key_params)
 {
-	u32 hvalue;
-	struct hashtab_node *prev, *cur;
+	struct hashtab_node **pprev;
 
 	cond_resched();
 
-	if (!h->size || h->nel == HASHTAB_MAX_NODES)
+	if (!h->hbits || h->nel == HASHTAB_MAX_NODES)
 		return -EINVAL;
 
-	hvalue = key_params.hash(key) & (h->size - 1);
-	prev = NULL;
-	cur = h->htable[hvalue];
-	while (cur) {
+	pprev = hashtab_entry(h, key, key_params);
+	for (struct hashtab_node *cur; (cur = *pprev) != NULL; ) {
 		int cmp = key_params.cmp(key, cur->key);
 
 		if (cmp == 0)
 			return -EEXIST;
 		if (cmp < 0)
 			break;
-		prev = cur;
-		cur = cur->next;
+		pprev = &cur->next;
 	}
 
-	return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue],
-				key, datum);
+	return __hashtab_insert(h, pprev, key, datum);
 }
 
 /*
@@ -95,16 +102,14 @@ static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
  * the datum of the entry otherwise.
  */
 static inline void *hashtab_search(struct hashtab *h, const void *key,
-				   struct hashtab_key_params key_params)
+				   const struct hashtab_key_params key_params)
 {
-	u32 hvalue;
 	struct hashtab_node *cur;
 
-	if (!h->size)
+	if (!h->hbits)
 		return NULL;
 
-	hvalue = key_params.hash(key) & (h->size - 1);
-	cur = h->htable[hvalue];
+	cur = *hashtab_entry(h, key, key_params);
 	while (cur) {
 		int cmp = key_params.cmp(key, cur->key);
 
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 595a435ea9c8..61bc82b2cea6 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -685,7 +685,7 @@ static void hash_eval(struct hashtab *h, const char *hash_name)
 
 	hashtab_stat(h, &info);
 	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,
+		 hash_name, h->nel, info.slots_used, hashtab_size(h),
 		 info.max_chain_len, info.chain2_len_sum);
 }
 
-- 
2.42.1




[Index of Archives]     [Selinux Refpolicy]     [Linux SGX]     [Fedora Users]     [Fedora Desktop]     [Yosemite Photos]     [Yosemite Camping]     [Yosemite Campsites]     [KDE Users]     [Gnome Users]

  Powered by Linux