1 /*
2 * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
3 *
4 * License: GNU GPL, version 2 or later.
5 * See the COPYING file in the top-level directory.
6 */
7 #include "qemu/osdep.h"
8 #include "qemu/qht.h"
9 #include "qemu/rcu.h"
10
11 #define N 5000
12
13 static struct qht ht;
14 static int32_t arr[N * 2];
15
is_equal(const void * ap,const void * bp)16 static bool is_equal(const void *ap, const void *bp)
17 {
18 const int32_t *a = ap;
19 const int32_t *b = bp;
20
21 return *a == *b;
22 }
23
insert(int a,int b)24 static void insert(int a, int b)
25 {
26 int i;
27
28 for (i = a; i < b; i++) {
29 uint32_t hash;
30 void *existing;
31 bool inserted;
32
33 arr[i] = i;
34 hash = i;
35
36 inserted = qht_insert(&ht, &arr[i], hash, NULL);
37 g_assert_true(inserted);
38 inserted = qht_insert(&ht, &arr[i], hash, &existing);
39 g_assert_false(inserted);
40 g_assert_true(existing == &arr[i]);
41 }
42 }
43
do_rm(int init,int end,bool exist)44 static void do_rm(int init, int end, bool exist)
45 {
46 int i;
47
48 for (i = init; i < end; i++) {
49 uint32_t hash;
50
51 hash = arr[i];
52 if (exist) {
53 g_assert_true(qht_remove(&ht, &arr[i], hash));
54 } else {
55 g_assert_false(qht_remove(&ht, &arr[i], hash));
56 }
57 }
58 }
59
rm(int init,int end)60 static void rm(int init, int end)
61 {
62 do_rm(init, end, true);
63 }
64
rm_nonexist(int init,int end)65 static void rm_nonexist(int init, int end)
66 {
67 do_rm(init, end, false);
68 }
69
check(int a,int b,bool expected)70 static void check(int a, int b, bool expected)
71 {
72 struct qht_stats stats;
73 int i;
74
75 rcu_read_lock();
76 for (i = a; i < b; i++) {
77 void *p;
78 uint32_t hash;
79 int32_t val;
80
81 val = i;
82 hash = i;
83 /* test both lookup variants; results should be the same */
84 if (i % 2) {
85 p = qht_lookup(&ht, &val, hash);
86 } else {
87 p = qht_lookup_custom(&ht, &val, hash, is_equal);
88 }
89 g_assert_true(!!p == expected);
90 }
91 rcu_read_unlock();
92
93 qht_statistics_init(&ht, &stats);
94 if (stats.used_head_buckets) {
95 g_assert_cmpfloat(qdist_avg(&stats.chain), >=, 1.0);
96 }
97 g_assert_cmpuint(stats.head_buckets, >, 0);
98 qht_statistics_destroy(&stats);
99 }
100
count_func(void * p,uint32_t hash,void * userp)101 static void count_func(void *p, uint32_t hash, void *userp)
102 {
103 unsigned int *curr = userp;
104
105 (*curr)++;
106 }
107
check_n(size_t expected)108 static void check_n(size_t expected)
109 {
110 struct qht_stats stats;
111
112 qht_statistics_init(&ht, &stats);
113 g_assert_cmpuint(stats.entries, ==, expected);
114 qht_statistics_destroy(&stats);
115 }
116
iter_check(unsigned int count)117 static void iter_check(unsigned int count)
118 {
119 unsigned int curr = 0;
120
121 qht_iter(&ht, count_func, &curr);
122 g_assert_cmpuint(curr, ==, count);
123 }
124
sum_func(void * p,uint32_t hash,void * userp)125 static void sum_func(void *p, uint32_t hash, void *userp)
126 {
127 uint32_t *sum = userp;
128 uint32_t a = *(uint32_t *)p;
129
130 *sum += a;
131 }
132
iter_sum_check(unsigned int expected)133 static void iter_sum_check(unsigned int expected)
134 {
135 unsigned int sum = 0;
136
137 qht_iter(&ht, sum_func, &sum);
138 g_assert_cmpuint(sum, ==, expected);
139 }
140
rm_mod_func(void * p,uint32_t hash,void * userp)141 static bool rm_mod_func(void *p, uint32_t hash, void *userp)
142 {
143 uint32_t a = *(uint32_t *)p;
144 unsigned int mod = *(unsigned int *)userp;
145
146 return a % mod == 0;
147 }
148
iter_rm_mod(unsigned int mod)149 static void iter_rm_mod(unsigned int mod)
150 {
151 qht_iter_remove(&ht, rm_mod_func, &mod);
152 }
153
iter_rm_mod_check(unsigned int mod)154 static void iter_rm_mod_check(unsigned int mod)
155 {
156 unsigned int expected = 0;
157 unsigned int i;
158
159 for (i = 0; i < N; i++) {
160 if (i % mod == 0) {
161 continue;
162 }
163 expected += i;
164 }
165 iter_sum_check(expected);
166 }
167
qht_do_test(unsigned int mode,size_t init_entries)168 static void qht_do_test(unsigned int mode, size_t init_entries)
169 {
170 /* under KVM we might fetch stats from an uninitialized qht */
171 check_n(0);
172
173 qht_init(&ht, is_equal, 0, mode);
174 rm_nonexist(0, 4);
175 /*
176 * Test that we successfully delete the last element in a bucket.
177 * This is a hard-to-reach code path when resizing is on, but without
178 * resizing we can easily hit it if init_entries <= 1.
179 * Given that the number of elements per bucket can be 4 or 6 depending on
180 * the host's pointer size, test the removal of the 4th and 6th elements.
181 */
182 insert(0, 4);
183 rm_nonexist(5, 6);
184 rm(3, 4);
185 check_n(3);
186 insert(3, 6);
187 rm(5, 6);
188 check_n(5);
189 rm_nonexist(7, 8);
190 iter_rm_mod(1);
191
192 if (!(mode & QHT_MODE_AUTO_RESIZE)) {
193 qht_resize(&ht, init_entries * 4 + 4);
194 }
195
196 check_n(0);
197 rm_nonexist(0, 10);
198 insert(0, N);
199 check(0, N, true);
200 check_n(N);
201 check(-N, -1, false);
202 iter_check(N);
203
204 rm(101, 102);
205 check_n(N - 1);
206 insert(N, N * 2);
207 check_n(N + N - 1);
208 rm(N, N * 2);
209 check_n(N - 1);
210 insert(101, 102);
211 check_n(N);
212
213 rm(10, 200);
214 check_n(N - 190);
215 insert(150, 200);
216 check_n(N - 190 + 50);
217 insert(10, 150);
218 check_n(N);
219
220 qht_reset(&ht);
221 insert(0, N);
222 rm_nonexist(N, N + 32);
223 iter_rm_mod(10);
224 iter_rm_mod_check(10);
225 check_n(N * 9 / 10);
226 qht_reset_size(&ht, 0);
227 check_n(0);
228 check(0, N, false);
229
230 qht_destroy(&ht);
231 }
232
qht_test(unsigned int mode)233 static void qht_test(unsigned int mode)
234 {
235 qht_do_test(mode, 0);
236 qht_do_test(mode, 1);
237 qht_do_test(mode, 2);
238 qht_do_test(mode, 8);
239 qht_do_test(mode, 16);
240 qht_do_test(mode, 8192);
241 qht_do_test(mode, 16384);
242 }
243
test_default(void)244 static void test_default(void)
245 {
246 qht_test(0);
247 }
248
test_resize(void)249 static void test_resize(void)
250 {
251 qht_test(QHT_MODE_AUTO_RESIZE);
252 }
253
main(int argc,char * argv[])254 int main(int argc, char *argv[])
255 {
256 g_test_init(&argc, &argv, NULL);
257 g_test_add_func("/qht/mode/default", test_default);
258 g_test_add_func("/qht/mode/resize", test_resize);
259 return g_test_run();
260 }
261