add new system file

hc

2024-02-20 102a0743326a03cd1a1202ceda21e175b7d3575c

 kernel/security/selinux/ss/hashtab.c
..
..
@@ -7,102 +7,66 @@
7
7
 #include <linux/kernel.h>
8
8
 #include <linux/slab.h>
9
9
 #include <linux/errno.h>
10
-#include <linux/sched.h>
11
10
 #include "hashtab.h"
12
11
 
13
12
 static struct kmem_cache *hashtab_node_cachep;
14
13
 
15
-struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
16
-			       int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
17
-			       u32 size)
14
+/*
15
+ * Here we simply round the number of elements up to the nearest power of two.
16
+ * I tried also other options like rouding down or rounding to the closest
17
+ * power of two (up or down based on which is closer), but I was unable to
18
+ * find any significant difference in lookup/insert performance that would
19
+ * justify switching to a different (less intuitive) formula. It could be that
20
+ * a different formula is actually more optimal, but any future changes here
21
+ * should be supported with performance/memory usage data.
22
+ *
23
+ * The total memory used by the htable arrays (only) with Fedora policy loaded
24
+ * is approximately 163 KB at the time of writing.
25
+ */
26
+static u32 hashtab_compute_size(u32 nel)
18
27
 {
19
-	struct hashtab *p;
20
-	u32 i;
21
-
22
-	p = kzalloc(sizeof(*p), GFP_KERNEL);
23
-	if (!p)
24
-		return p;
25
-
26
-	p->size = size;
27
-	p->nel = 0;
28
-	p->hash_value = hash_value;
29
-	p->keycmp = keycmp;
30
-	p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL);
31
-	if (!p->htable) {
32
-		kfree(p);
33
-		return NULL;
34
-	}
35
-
36
-	for (i = 0; i < size; i++)
37
-		p->htable[i] = NULL;
38
-
39
-	return p;
28
+	return nel == 0 ? 0 : roundup_pow_of_two(nel);
40
29
 }
41
30
 
42
-int hashtab_insert(struct hashtab *h, void *key, void *datum)
31
+int hashtab_init(struct hashtab *h, u32 nel_hint)
43
32
 {
44
-	u32 hvalue;
45
-	struct hashtab_node *prev, *cur, *newnode;
33
+	u32 size = hashtab_compute_size(nel_hint);
46
34
 
47
-	cond_resched();
35
+	/* should already be zeroed, but better be safe */
36
+	h->nel = 0;
37
+	h->size = 0;
38
+	h->htable = NULL;
48
39
 
49
-	if (!h || h->nel == HASHTAB_MAX_NODES)
50
-		return -EINVAL;
51
-
52
-	hvalue = h->hash_value(h, key);
53
-	prev = NULL;
54
-	cur = h->htable[hvalue];
55
-	while (cur && h->keycmp(h, key, cur->key) > 0) {
56
-		prev = cur;
57
-		cur = cur->next;
40
+	if (size) {
41
+		h->htable = kcalloc(size, sizeof(*h->htable), GFP_KERNEL);
42
+		if (!h->htable)
43
+			return -ENOMEM;
44
+		h->size = size;
58
45
 	}
46
+	return 0;
47
+}
59
48
 
60
-	if (cur && (h->keycmp(h, key, cur->key) == 0))
61
-		return -EEXIST;
49
+int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
50
+		     void *key, void *datum)
51
+{
52
+	struct hashtab_node *newnode;
62
53
 
63
54
 	newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
64
55
 	if (!newnode)
65
56
 		return -ENOMEM;
66
57
 	newnode->key = key;
67
58
 	newnode->datum = datum;
68
-	if (prev) {
69
-		newnode->next = prev->next;
70
-		prev->next = newnode;
71
-	} else {
72
-		newnode->next = h->htable[hvalue];
73
-		h->htable[hvalue] = newnode;
74
-	}
59
+	newnode->next = *dst;
60
+	*dst = newnode;
75
61
 
76
62
 	h->nel++;
77
63
 	return 0;
78
-}
79
-
80
-void *hashtab_search(struct hashtab *h, const void *key)
81
-{
82
-	u32 hvalue;
83
-	struct hashtab_node *cur;
84
-
85
-	if (!h)
86
-		return NULL;
87
-
88
-	hvalue = h->hash_value(h, key);
89
-	cur = h->htable[hvalue];
90
-	while (cur && h->keycmp(h, key, cur->key) > 0)
91
-		cur = cur->next;
92
-
93
-	if (!cur || (h->keycmp(h, key, cur->key) != 0))
94
-		return NULL;
95
-
96
-	return cur->datum;
97
64
 }
98
65
 
99
66
 void hashtab_destroy(struct hashtab *h)
100
67
 {
101
68
 	u32 i;
102
69
 	struct hashtab_node *cur, *temp;
103
-
104
-	if (!h)
105
-		return;
106
70
 
107
71
 	for (i = 0; i < h->size; i++) {
108
72
 		cur = h->htable[i];
..
..
@@ -116,8 +80,6 @@
116
80
 
117
81
 	kfree(h->htable);
118
82
 	h->htable = NULL;
119
-
120
-	kfree(h);
121
83
 }
122
84
 
123
85
 int hashtab_map(struct hashtab *h,
..
..
@@ -127,9 +89,6 @@
127
89
 	u32 i;
128
90
 	int ret;
129
91
 	struct hashtab_node *cur;
130
-
131
-	if (!h)
132
-		return 0;
133
92
 
134
93
 	for (i = 0; i < h->size; i++) {
135
94
 		cur = h->htable[i];
..
..
@@ -170,6 +129,60 @@
170
129
 	info->max_chain_len = max_chain_len;
171
130
 }
172
131
 
132
+int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
133
+		int (*copy)(struct hashtab_node *new,
134
+			struct hashtab_node *orig, void *args),
135
+		int (*destroy)(void *k, void *d, void *args),
136
+		void *args)
137
+{
138
+	struct hashtab_node *cur, *tmp, *tail;
139
+	int i, rc;
140
+
141
+	memset(new, 0, sizeof(*new));
142
+
143
+	new->htable = kcalloc(orig->size, sizeof(*new->htable), GFP_KERNEL);
144
+	if (!new->htable)
145
+		return -ENOMEM;
146
+
147
+	new->size = orig->size;
148
+
149
+	for (i = 0; i < orig->size; i++) {
150
+		tail = NULL;
151
+		for (cur = orig->htable[i]; cur; cur = cur->next) {
152
+			tmp = kmem_cache_zalloc(hashtab_node_cachep,
153
+						GFP_KERNEL);
154
+			if (!tmp)
155
+				goto error;
156
+			rc = copy(tmp, cur, args);
157
+			if (rc) {
158
+				kmem_cache_free(hashtab_node_cachep, tmp);
159
+				goto error;
160
+			}
161
+			tmp->next = NULL;
162
+			if (!tail)
163
+				new->htable[i] = tmp;
164
+			else
165
+				tail->next = tmp;
166
+			tail = tmp;
167
+			new->nel++;
168
+		}
169
+	}
170
+
171
+	return 0;
172
+
173
+ error:
174
+	for (i = 0; i < new->size; i++) {
175
+		for (cur = new->htable[i]; cur; cur = tmp) {
176
+			tmp = cur->next;
177
+			destroy(cur->key, cur->datum, args);
178
+			kmem_cache_free(hashtab_node_cachep, cur);
179
+		}
180
+	}
181
+	kfree(new->htable);
182
+	memset(new, 0, sizeof(*new));
183
+	return -ENOMEM;
184
+}
185
+
173
186
 void __init hashtab_cache_init(void)
174
187
 {
175
188
 		hashtab_node_cachep = kmem_cache_create("hashtab_node",