diff options
author | Geert Uytterhoeven <geert@linux-m68k.org> | 2015-01-29 09:40:25 -0500 |
---|---|---|
committer | David S. Miller <davem@davemloft.net> | 2015-01-30 21:06:33 -0500 |
commit | 9d6dbe1bbaf8bf03804c164fb67a98646bf2f622 (patch) | |
tree | 8d9dfb332d0cfea4f35d18e4cec4e0b7bbd3d86e /lib | |
parent | 207895fd388c7c4c48bc33055cd726d9e750298c (diff) |
rhashtable: Make selftest modular
Allow the selftest on the resizable hash table to be built modular, just
like all other tests that do not depend on DEBUG_KERNEL.
Signed-off-by: Geert Uytterhoeven <geert@linux-m68k.org>
Acked-by: Thomas Graf <tgraf@suug.ch>
Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Kconfig.debug | 2 | ||||
-rw-r--r-- | lib/Makefile | 1 | ||||
-rw-r--r-- | lib/rhashtable.c | 205 | ||||
-rw-r--r-- | lib/test_rhashtable.c | 227 |
4 files changed, 229 insertions, 206 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 5f2ce616c046..a8f3c9993229 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug | |||
@@ -1586,7 +1586,7 @@ config TEST_KSTRTOX | |||
1586 | tristate "Test kstrto*() family of functions at runtime" | 1586 | tristate "Test kstrto*() family of functions at runtime" |
1587 | 1587 | ||
1588 | config TEST_RHASHTABLE | 1588 | config TEST_RHASHTABLE |
1589 | bool "Perform selftest on resizable hash table" | 1589 | tristate "Perform selftest on resizable hash table" |
1590 | default n | 1590 | default n |
1591 | help | 1591 | help |
1592 | Enable this option to test the rhashtable functions at boot. | 1592 | Enable this option to test the rhashtable functions at boot. |
diff --git a/lib/Makefile b/lib/Makefile index 3c3b30b9e020..a8cf98d14199 100644 --- a/lib/Makefile +++ b/lib/Makefile | |||
@@ -35,6 +35,7 @@ obj-$(CONFIG_TEST_LKM) += test_module.o | |||
35 | obj-$(CONFIG_TEST_USER_COPY) += test_user_copy.o | 35 | obj-$(CONFIG_TEST_USER_COPY) += test_user_copy.o |
36 | obj-$(CONFIG_TEST_BPF) += test_bpf.o | 36 | obj-$(CONFIG_TEST_BPF) += test_bpf.o |
37 | obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o | 37 | obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o |
38 | obj-$(CONFIG_TEST_RHASHTABLE) += test_rhashtable.o | ||
38 | 39 | ||
39 | ifeq ($(CONFIG_DEBUG_KOBJECT),y) | 40 | ifeq ($(CONFIG_DEBUG_KOBJECT),y) |
40 | CFLAGS_kobject.o += -DDEBUG | 41 | CFLAGS_kobject.o += -DDEBUG |
diff --git a/lib/rhashtable.c b/lib/rhashtable.c index bc2d0d80d1f9..c41e21096373 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c | |||
@@ -935,208 +935,3 @@ void rhashtable_destroy(struct rhashtable *ht) | |||
935 | mutex_unlock(&ht->mutex); | 935 | mutex_unlock(&ht->mutex); |
936 | } | 936 | } |
937 | EXPORT_SYMBOL_GPL(rhashtable_destroy); | 937 | EXPORT_SYMBOL_GPL(rhashtable_destroy); |
938 | |||
939 | /************************************************************************** | ||
940 | * Self Test | ||
941 | **************************************************************************/ | ||
942 | |||
943 | #ifdef CONFIG_TEST_RHASHTABLE | ||
944 | |||
945 | #define TEST_HT_SIZE 8 | ||
946 | #define TEST_ENTRIES 2048 | ||
947 | #define TEST_PTR ((void *) 0xdeadbeef) | ||
948 | #define TEST_NEXPANDS 4 | ||
949 | |||
950 | struct test_obj { | ||
951 | void *ptr; | ||
952 | int value; | ||
953 | struct rhash_head node; | ||
954 | }; | ||
955 | |||
956 | static int __init test_rht_lookup(struct rhashtable *ht) | ||
957 | { | ||
958 | unsigned int i; | ||
959 | |||
960 | for (i = 0; i < TEST_ENTRIES * 2; i++) { | ||
961 | struct test_obj *obj; | ||
962 | bool expected = !(i % 2); | ||
963 | u32 key = i; | ||
964 | |||
965 | obj = rhashtable_lookup(ht, &key); | ||
966 | |||
967 | if (expected && !obj) { | ||
968 | pr_warn("Test failed: Could not find key %u\n", key); | ||
969 | return -ENOENT; | ||
970 | } else if (!expected && obj) { | ||
971 | pr_warn("Test failed: Unexpected entry found for key %u\n", | ||
972 | key); | ||
973 | return -EEXIST; | ||
974 | } else if (expected && obj) { | ||
975 | if (obj->ptr != TEST_PTR || obj->value != i) { | ||
976 | pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n", | ||
977 | obj->ptr, TEST_PTR, obj->value, i); | ||
978 | return -EINVAL; | ||
979 | } | ||
980 | } | ||
981 | } | ||
982 | |||
983 | return 0; | ||
984 | } | ||
985 | |||
986 | static void test_bucket_stats(struct rhashtable *ht, bool quiet) | ||
987 | { | ||
988 | unsigned int cnt, rcu_cnt, i, total = 0; | ||
989 | struct rhash_head *pos; | ||
990 | struct test_obj *obj; | ||
991 | struct bucket_table *tbl; | ||
992 | |||
993 | tbl = rht_dereference_rcu(ht->tbl, ht); | ||
994 | for (i = 0; i < tbl->size; i++) { | ||
995 | rcu_cnt = cnt = 0; | ||
996 | |||
997 | if (!quiet) | ||
998 | pr_info(" [%#4x/%zu]", i, tbl->size); | ||
999 | |||
1000 | rht_for_each_entry_rcu(obj, pos, tbl, i, node) { | ||
1001 | cnt++; | ||
1002 | total++; | ||
1003 | if (!quiet) | ||
1004 | pr_cont(" [%p],", obj); | ||
1005 | } | ||
1006 | |||
1007 | rht_for_each_entry_rcu(obj, pos, tbl, i, node) | ||
1008 | rcu_cnt++; | ||
1009 | |||
1010 | if (rcu_cnt != cnt) | ||
1011 | pr_warn("Test failed: Chain count mismach %d != %d", | ||
1012 | cnt, rcu_cnt); | ||
1013 | |||
1014 | if (!quiet) | ||
1015 | pr_cont("\n [%#x] first element: %p, chain length: %u\n", | ||
1016 | i, tbl->buckets[i], cnt); | ||
1017 | } | ||
1018 | |||
1019 | pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d\n", | ||
1020 | total, atomic_read(&ht->nelems), TEST_ENTRIES); | ||
1021 | |||
1022 | if (total != atomic_read(&ht->nelems) || total != TEST_ENTRIES) | ||
1023 | pr_warn("Test failed: Total count mismatch ^^^"); | ||
1024 | } | ||
1025 | |||
1026 | static int __init test_rhashtable(struct rhashtable *ht) | ||
1027 | { | ||
1028 | struct bucket_table *tbl; | ||
1029 | struct test_obj *obj; | ||
1030 | struct rhash_head *pos, *next; | ||
1031 | int err; | ||
1032 | unsigned int i; | ||
1033 | |||
1034 | /* | ||
1035 | * Insertion Test: | ||
1036 | * Insert TEST_ENTRIES into table with all keys even numbers | ||
1037 | */ | ||
1038 | pr_info(" Adding %d keys\n", TEST_ENTRIES); | ||
1039 | for (i = 0; i < TEST_ENTRIES; i++) { | ||
1040 | struct test_obj *obj; | ||
1041 | |||
1042 | obj = kzalloc(sizeof(*obj), GFP_KERNEL); | ||
1043 | if (!obj) { | ||
1044 | err = -ENOMEM; | ||
1045 | goto error; | ||
1046 | } | ||
1047 | |||
1048 | obj->ptr = TEST_PTR; | ||
1049 | obj->value = i * 2; | ||
1050 | |||
1051 | rhashtable_insert(ht, &obj->node); | ||
1052 | } | ||
1053 | |||
1054 | rcu_read_lock(); | ||
1055 | test_bucket_stats(ht, true); | ||
1056 | test_rht_lookup(ht); | ||
1057 | rcu_read_unlock(); | ||
1058 | |||
1059 | for (i = 0; i < TEST_NEXPANDS; i++) { | ||
1060 | pr_info(" Table expansion iteration %u...\n", i); | ||
1061 | mutex_lock(&ht->mutex); | ||
1062 | rhashtable_expand(ht); | ||
1063 | mutex_unlock(&ht->mutex); | ||
1064 | |||
1065 | rcu_read_lock(); | ||
1066 | pr_info(" Verifying lookups...\n"); | ||
1067 | test_rht_lookup(ht); | ||
1068 | rcu_read_unlock(); | ||
1069 | } | ||
1070 | |||
1071 | for (i = 0; i < TEST_NEXPANDS; i++) { | ||
1072 | pr_info(" Table shrinkage iteration %u...\n", i); | ||
1073 | mutex_lock(&ht->mutex); | ||
1074 | rhashtable_shrink(ht); | ||
1075 | mutex_unlock(&ht->mutex); | ||
1076 | |||
1077 | rcu_read_lock(); | ||
1078 | pr_info(" Verifying lookups...\n"); | ||
1079 | test_rht_lookup(ht); | ||
1080 | rcu_read_unlock(); | ||
1081 | } | ||
1082 | |||
1083 | rcu_read_lock(); | ||
1084 | test_bucket_stats(ht, true); | ||
1085 | rcu_read_unlock(); | ||
1086 | |||
1087 | pr_info(" Deleting %d keys\n", TEST_ENTRIES); | ||
1088 | for (i = 0; i < TEST_ENTRIES; i++) { | ||
1089 | u32 key = i * 2; | ||
1090 | |||
1091 | obj = rhashtable_lookup(ht, &key); | ||
1092 | BUG_ON(!obj); | ||
1093 | |||
1094 | rhashtable_remove(ht, &obj->node); | ||
1095 | kfree(obj); | ||
1096 | } | ||
1097 | |||
1098 | return 0; | ||
1099 | |||
1100 | error: | ||
1101 | tbl = rht_dereference_rcu(ht->tbl, ht); | ||
1102 | for (i = 0; i < tbl->size; i++) | ||
1103 | rht_for_each_entry_safe(obj, pos, next, tbl, i, node) | ||
1104 | kfree(obj); | ||
1105 | |||
1106 | return err; | ||
1107 | } | ||
1108 | |||
1109 | static int __init test_rht_init(void) | ||
1110 | { | ||
1111 | struct rhashtable ht; | ||
1112 | struct rhashtable_params params = { | ||
1113 | .nelem_hint = TEST_HT_SIZE, | ||
1114 | .head_offset = offsetof(struct test_obj, node), | ||
1115 | .key_offset = offsetof(struct test_obj, value), | ||
1116 | .key_len = sizeof(int), | ||
1117 | .hashfn = jhash, | ||
1118 | .nulls_base = (3U << RHT_BASE_SHIFT), | ||
1119 | .grow_decision = rht_grow_above_75, | ||
1120 | .shrink_decision = rht_shrink_below_30, | ||
1121 | }; | ||
1122 | int err; | ||
1123 | |||
1124 | pr_info("Running resizable hashtable tests...\n"); | ||
1125 | |||
1126 | err = rhashtable_init(&ht, ¶ms); | ||
1127 | if (err < 0) { | ||
1128 | pr_warn("Test failed: Unable to initialize hashtable: %d\n", | ||
1129 | err); | ||
1130 | return err; | ||
1131 | } | ||
1132 | |||
1133 | err = test_rhashtable(&ht); | ||
1134 | |||
1135 | rhashtable_destroy(&ht); | ||
1136 | |||
1137 | return err; | ||
1138 | } | ||
1139 | |||
1140 | subsys_initcall(test_rht_init); | ||
1141 | |||
1142 | #endif /* CONFIG_TEST_RHASHTABLE */ | ||
diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c new file mode 100644 index 000000000000..1dfeba73fc74 --- /dev/null +++ b/lib/test_rhashtable.c | |||
@@ -0,0 +1,227 @@ | |||
1 | /* | ||
2 | * Resizable, Scalable, Concurrent Hash Table | ||
3 | * | ||
4 | * Copyright (c) 2014 Thomas Graf <tgraf@suug.ch> | ||
5 | * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net> | ||
6 | * | ||
7 | * Based on the following paper: | ||
8 | * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf | ||
9 | * | ||
10 | * Code partially derived from nft_hash | ||
11 | * | ||
12 | * This program is free software; you can redistribute it and/or modify | ||
13 | * it under the terms of the GNU General Public License version 2 as | ||
14 | * published by the Free Software Foundation. | ||
15 | */ | ||
16 | |||
17 | /************************************************************************** | ||
18 | * Self Test | ||
19 | **************************************************************************/ | ||
20 | |||
21 | #include <linux/init.h> | ||
22 | #include <linux/jhash.h> | ||
23 | #include <linux/kernel.h> | ||
24 | #include <linux/module.h> | ||
25 | #include <linux/rcupdate.h> | ||
26 | #include <linux/rhashtable.h> | ||
27 | #include <linux/slab.h> | ||
28 | |||
29 | |||
30 | #define TEST_HT_SIZE 8 | ||
31 | #define TEST_ENTRIES 2048 | ||
32 | #define TEST_PTR ((void *) 0xdeadbeef) | ||
33 | #define TEST_NEXPANDS 4 | ||
34 | |||
35 | struct test_obj { | ||
36 | void *ptr; | ||
37 | int value; | ||
38 | struct rhash_head node; | ||
39 | }; | ||
40 | |||
41 | static int __init test_rht_lookup(struct rhashtable *ht) | ||
42 | { | ||
43 | unsigned int i; | ||
44 | |||
45 | for (i = 0; i < TEST_ENTRIES * 2; i++) { | ||
46 | struct test_obj *obj; | ||
47 | bool expected = !(i % 2); | ||
48 | u32 key = i; | ||
49 | |||
50 | obj = rhashtable_lookup(ht, &key); | ||
51 | |||
52 | if (expected && !obj) { | ||
53 | pr_warn("Test failed: Could not find key %u\n", key); | ||
54 | return -ENOENT; | ||
55 | } else if (!expected && obj) { | ||
56 | pr_warn("Test failed: Unexpected entry found for key %u\n", | ||
57 | key); | ||
58 | return -EEXIST; | ||
59 | } else if (expected && obj) { | ||
60 | if (obj->ptr != TEST_PTR || obj->value != i) { | ||
61 | pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n", | ||
62 | obj->ptr, TEST_PTR, obj->value, i); | ||
63 | return -EINVAL; | ||
64 | } | ||
65 | } | ||
66 | } | ||
67 | |||
68 | return 0; | ||
69 | } | ||
70 | |||
71 | static void test_bucket_stats(struct rhashtable *ht, bool quiet) | ||
72 | { | ||
73 | unsigned int cnt, rcu_cnt, i, total = 0; | ||
74 | struct rhash_head *pos; | ||
75 | struct test_obj *obj; | ||
76 | struct bucket_table *tbl; | ||
77 | |||
78 | tbl = rht_dereference_rcu(ht->tbl, ht); | ||
79 | for (i = 0; i < tbl->size; i++) { | ||
80 | rcu_cnt = cnt = 0; | ||
81 | |||
82 | if (!quiet) | ||
83 | pr_info(" [%#4x/%zu]", i, tbl->size); | ||
84 | |||
85 | rht_for_each_entry_rcu(obj, pos, tbl, i, node) { | ||
86 | cnt++; | ||
87 | total++; | ||
88 | if (!quiet) | ||
89 | pr_cont(" [%p],", obj); | ||
90 | } | ||
91 | |||
92 | rht_for_each_entry_rcu(obj, pos, tbl, i, node) | ||
93 | rcu_cnt++; | ||
94 | |||
95 | if (rcu_cnt != cnt) | ||
96 | pr_warn("Test failed: Chain count mismach %d != %d", | ||
97 | cnt, rcu_cnt); | ||
98 | |||
99 | if (!quiet) | ||
100 | pr_cont("\n [%#x] first element: %p, chain length: %u\n", | ||
101 | i, tbl->buckets[i], cnt); | ||
102 | } | ||
103 | |||
104 | pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d\n", | ||
105 | total, atomic_read(&ht->nelems), TEST_ENTRIES); | ||
106 | |||
107 | if (total != atomic_read(&ht->nelems) || total != TEST_ENTRIES) | ||
108 | pr_warn("Test failed: Total count mismatch ^^^"); | ||
109 | } | ||
110 | |||
111 | static int __init test_rhashtable(struct rhashtable *ht) | ||
112 | { | ||
113 | struct bucket_table *tbl; | ||
114 | struct test_obj *obj; | ||
115 | struct rhash_head *pos, *next; | ||
116 | int err; | ||
117 | unsigned int i; | ||
118 | |||
119 | /* | ||
120 | * Insertion Test: | ||
121 | * Insert TEST_ENTRIES into table with all keys even numbers | ||
122 | */ | ||
123 | pr_info(" Adding %d keys\n", TEST_ENTRIES); | ||
124 | for (i = 0; i < TEST_ENTRIES; i++) { | ||
125 | struct test_obj *obj; | ||
126 | |||
127 | obj = kzalloc(sizeof(*obj), GFP_KERNEL); | ||
128 | if (!obj) { | ||
129 | err = -ENOMEM; | ||
130 | goto error; | ||
131 | } | ||
132 | |||
133 | obj->ptr = TEST_PTR; | ||
134 | obj->value = i * 2; | ||
135 | |||
136 | rhashtable_insert(ht, &obj->node); | ||
137 | } | ||
138 | |||
139 | rcu_read_lock(); | ||
140 | test_bucket_stats(ht, true); | ||
141 | test_rht_lookup(ht); | ||
142 | rcu_read_unlock(); | ||
143 | |||
144 | for (i = 0; i < TEST_NEXPANDS; i++) { | ||
145 | pr_info(" Table expansion iteration %u...\n", i); | ||
146 | mutex_lock(&ht->mutex); | ||
147 | rhashtable_expand(ht); | ||
148 | mutex_unlock(&ht->mutex); | ||
149 | |||
150 | rcu_read_lock(); | ||
151 | pr_info(" Verifying lookups...\n"); | ||
152 | test_rht_lookup(ht); | ||
153 | rcu_read_unlock(); | ||
154 | } | ||
155 | |||
156 | for (i = 0; i < TEST_NEXPANDS; i++) { | ||
157 | pr_info(" Table shrinkage iteration %u...\n", i); | ||
158 | mutex_lock(&ht->mutex); | ||
159 | rhashtable_shrink(ht); | ||
160 | mutex_unlock(&ht->mutex); | ||
161 | |||
162 | rcu_read_lock(); | ||
163 | pr_info(" Verifying lookups...\n"); | ||
164 | test_rht_lookup(ht); | ||
165 | rcu_read_unlock(); | ||
166 | } | ||
167 | |||
168 | rcu_read_lock(); | ||
169 | test_bucket_stats(ht, true); | ||
170 | rcu_read_unlock(); | ||
171 | |||
172 | pr_info(" Deleting %d keys\n", TEST_ENTRIES); | ||
173 | for (i = 0; i < TEST_ENTRIES; i++) { | ||
174 | u32 key = i * 2; | ||
175 | |||
176 | obj = rhashtable_lookup(ht, &key); | ||
177 | BUG_ON(!obj); | ||
178 | |||
179 | rhashtable_remove(ht, &obj->node); | ||
180 | kfree(obj); | ||
181 | } | ||
182 | |||
183 | return 0; | ||
184 | |||
185 | error: | ||
186 | tbl = rht_dereference_rcu(ht->tbl, ht); | ||
187 | for (i = 0; i < tbl->size; i++) | ||
188 | rht_for_each_entry_safe(obj, pos, next, tbl, i, node) | ||
189 | kfree(obj); | ||
190 | |||
191 | return err; | ||
192 | } | ||
193 | |||
194 | static int __init test_rht_init(void) | ||
195 | { | ||
196 | struct rhashtable ht; | ||
197 | struct rhashtable_params params = { | ||
198 | .nelem_hint = TEST_HT_SIZE, | ||
199 | .head_offset = offsetof(struct test_obj, node), | ||
200 | .key_offset = offsetof(struct test_obj, value), | ||
201 | .key_len = sizeof(int), | ||
202 | .hashfn = jhash, | ||
203 | .nulls_base = (3U << RHT_BASE_SHIFT), | ||
204 | .grow_decision = rht_grow_above_75, | ||
205 | .shrink_decision = rht_shrink_below_30, | ||
206 | }; | ||
207 | int err; | ||
208 | |||
209 | pr_info("Running resizable hashtable tests...\n"); | ||
210 | |||
211 | err = rhashtable_init(&ht, ¶ms); | ||
212 | if (err < 0) { | ||
213 | pr_warn("Test failed: Unable to initialize hashtable: %d\n", | ||
214 | err); | ||
215 | return err; | ||
216 | } | ||
217 | |||
218 | err = test_rhashtable(&ht); | ||
219 | |||
220 | rhashtable_destroy(&ht); | ||
221 | |||
222 | return err; | ||
223 | } | ||
224 | |||
225 | module_init(test_rht_init); | ||
226 | |||
227 | MODULE_LICENSE("GPL v2"); | ||