1 | /* |
2 | * Copyright (c) 2018-2021 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | |
29 | #if (DEVELOPMENT || DEBUG) |
30 | |
31 | #pragma clang optimize off |
32 | |
33 | #include <libkern/OSAtomic.h> |
34 | #include <os/refcnt.h> |
35 | #include <skywalk/os_skywalk_private.h> |
36 | #include <skywalk/lib/cuckoo_hashtable.h> |
37 | |
38 | #define CUCKOO_TEST_TAG "com.apple.skywalk.libcuckoo.test" |
39 | SKMEM_TAG_DEFINE(cuckoo_test_tag, CUCKOO_TEST_TAG); |
40 | |
41 | os_refgrp_decl(static, cht_obj_refgrp, "CuckooTestRefGroup" , NULL); |
42 | |
43 | static void cuckoo_test_start(void *, wait_result_t); |
44 | static void cuckoo_test_stop(void *, wait_result_t); |
45 | |
46 | extern unsigned int ml_wait_max_cpus(void); |
47 | |
48 | // threading related |
49 | static int cht_inited = 0; |
50 | static int cht_enabled; |
51 | static int cht_busy; |
52 | |
53 | decl_lck_mtx_data(static, cht_lock); |
54 | |
55 | static struct cuckoo_hashtable *h = NULL; |
56 | |
57 | struct cht_thread_conf { |
58 | thread_t ctc_thread; /* thread instance */ |
59 | uint32_t ctc_nthreads; /* number of threads */ |
60 | uint32_t ctc_id; /* thread id */ |
61 | } __attribute__((aligned(CHANNEL_CACHE_ALIGN_MAX))); |
62 | |
63 | static struct cht_thread_conf *chth_confs; |
64 | static uint32_t chth_nthreads; |
65 | static uint32_t chth_cnt; |
66 | static boolean_t chth_run; |
67 | |
68 | enum { |
69 | COS_NOT_ADDED = 0, /* no inserted, available for insertion */ |
70 | COS_BUSY = -1, /* being inserted/deleted */ |
71 | COS_ADDED = 1, /* inserted, available for deletion */ |
72 | } co_state_t; |
73 | |
74 | // Cuckoo hashtable key object |
75 | |
76 | struct cht_obj { |
77 | struct cuckoo_node co_cnode; // cuckoo node |
78 | int64_t co_key; // unique key |
79 | uint32_t co_hash; // dummy hash value (not collision-free) |
80 | os_refcnt_t co_refcnt; // reference count |
81 | volatile int32_t co_state; // co_state_t |
82 | uint32_t co_seen; // number of times seen |
83 | }; |
84 | |
85 | #if XNU_PLATFORM_WatchOS |
86 | static const uint32_t CHT_OBJ_MAX = 16 * 1024; |
87 | #else /* XNU_PLATFORM_WatchOS */ |
88 | static const uint32_t CHT_OBJ_MAX = 512 * 1024; |
89 | #endif /* !XNU_PLATFORM_WatchOS */ |
90 | static struct cht_obj *cht_objs; |
91 | |
92 | static int |
93 | cht_obj_cmp__(struct cuckoo_node *node, void *key) |
94 | { |
95 | struct cht_obj *co = container_of(node, struct cht_obj, co_cnode); |
96 | int64_t key1 = *(int64_t *)key; |
97 | |
98 | if (co->co_key < key1) { |
99 | return -1; |
100 | } else if (co->co_key > key1) { |
101 | return 1; |
102 | } |
103 | |
104 | return 0; |
105 | } |
106 | |
107 | static void |
108 | cht_obj_retain(struct cht_obj *co) |
109 | { |
110 | (void)os_ref_retain(&co->co_refcnt); |
111 | } |
112 | |
113 | static void |
114 | cht_obj_retain__(struct cuckoo_node *node) |
115 | { |
116 | struct cht_obj *co = container_of(node, struct cht_obj, co_cnode); |
117 | return cht_obj_retain(co); |
118 | } |
119 | |
120 | static void |
121 | cht_obj_release(struct cht_obj *co) |
122 | { |
123 | (void)os_ref_release(&co->co_refcnt); |
124 | } |
125 | |
126 | static void |
127 | cht_obj_release__(struct cuckoo_node *node) |
128 | { |
129 | struct cht_obj *co = container_of(node, struct cht_obj, co_cnode); |
130 | cht_obj_release(co); |
131 | } |
132 | |
133 | static int |
134 | cht_obj_refcnt(struct cht_obj *co) |
135 | { |
136 | return os_ref_get_count(&co->co_refcnt); |
137 | } |
138 | |
139 | static struct cuckoo_hashtable_params params_template = { |
140 | .cht_capacity = 1024, |
141 | .cht_obj_cmp = cht_obj_cmp__, |
142 | .cht_obj_retain = cht_obj_retain__, |
143 | .cht_obj_release = cht_obj_release__, |
144 | }; |
145 | |
146 | void |
147 | cht_test_init(void) |
148 | { |
149 | if (OSCompareAndSwap(0, 1, &cht_inited)) { |
150 | lck_mtx_init(&cht_lock, &sk_lock_group, &sk_lock_attr); |
151 | } |
152 | } |
153 | |
154 | void |
155 | cht_test_fini(void) |
156 | { |
157 | lck_mtx_destroy(&cht_lock, &sk_lock_group); |
158 | } |
159 | |
160 | static void |
161 | cht_obj_init() |
162 | { |
163 | // init testing objects |
164 | cht_objs = sk_alloc_type_array(struct cht_obj, CHT_OBJ_MAX, |
165 | Z_WAITOK, cuckoo_test_tag); |
166 | VERIFY(cht_objs != NULL); |
167 | |
168 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
169 | cht_objs[i].co_key = i; |
170 | do { |
171 | read_random(&cht_objs[i].co_hash, sizeof(cht_objs[i].co_hash)); |
172 | } while (cht_objs[i].co_hash == 0); |
173 | os_ref_init(&cht_objs[i].co_refcnt, &cht_obj_refgrp); |
174 | cht_objs[i].co_state = COS_NOT_ADDED; |
175 | } |
176 | } |
177 | |
178 | static void |
179 | cht_obj_fini() |
180 | { |
181 | VERIFY(cht_objs != NULL); |
182 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
183 | ASSERT(os_ref_release(&cht_objs[i].co_refcnt) == 0); |
184 | cht_objs[i].co_state = COS_NOT_ADDED; |
185 | cht_objs[i].co_seen = 0; |
186 | } |
187 | // init testing objects |
188 | sk_free_type_array(struct cht_obj, CHT_OBJ_MAX, cht_objs); |
189 | } |
190 | |
191 | static void |
192 | cht_basic_tests(void) |
193 | { |
194 | SK_ERR("start" ); |
195 | |
196 | // Cuckoo hashtable creation |
197 | h = cuckoo_hashtable_create(¶ms_template); |
198 | |
199 | // basic add/del |
200 | struct cht_obj co1 = { |
201 | .co_cnode = {NULL}, |
202 | .co_key = -1, |
203 | .co_hash = 1, |
204 | .co_state = COS_NOT_ADDED, |
205 | .co_seen = 0 |
206 | }; |
207 | struct cht_obj co2 = { |
208 | .co_cnode = {NULL}, |
209 | .co_key = -2, |
210 | .co_hash = 1, |
211 | .co_state = COS_NOT_ADDED, |
212 | .co_seen = 0 |
213 | }; |
214 | os_ref_init(&co1.co_refcnt, &cht_obj_refgrp); |
215 | os_ref_init(&co2.co_refcnt, &cht_obj_refgrp); |
216 | |
217 | struct cuckoo_node *node = NULL; |
218 | __block struct cht_obj *co = NULL; |
219 | int error = 0; |
220 | |
221 | // add objs with duplicate hash |
222 | error = cuckoo_hashtable_add_with_hash(h, &co1.co_cnode, co1.co_hash); |
223 | ASSERT(error == 0); |
224 | |
225 | error = cuckoo_hashtable_add_with_hash(h, &co2.co_cnode, co2.co_hash); |
226 | ASSERT(error == 0); |
227 | |
228 | ASSERT(cuckoo_hashtable_entries(h) == 2); |
229 | |
230 | node = cuckoo_hashtable_find_with_hash(h, &co1.co_key, co1.co_hash); |
231 | ASSERT(node != NULL); |
232 | ASSERT(node == &co1.co_cnode); |
233 | |
234 | node = cuckoo_hashtable_find_with_hash(h, &co2.co_key, co2.co_hash); |
235 | ASSERT(node != NULL); |
236 | ASSERT(node == &co2.co_cnode); |
237 | |
238 | cuckoo_hashtable_del(h, &co1.co_cnode, co1.co_hash); |
239 | |
240 | node = cuckoo_hashtable_find_with_hash(h, &co1.co_key, co1.co_hash); |
241 | ASSERT(node == NULL); |
242 | |
243 | node = cuckoo_hashtable_find_with_hash(h, &co2.co_key, co2.co_hash); |
244 | ASSERT(node != NULL); |
245 | ASSERT(node == &co2.co_cnode); |
246 | |
247 | cuckoo_hashtable_del(h, &co2.co_cnode, co2.co_hash); |
248 | node = cuckoo_hashtable_find_with_hash(h, &co2.co_key, co2.co_hash); |
249 | ASSERT(node == NULL); |
250 | |
251 | ASSERT(cuckoo_hashtable_entries(h) == 0); |
252 | |
253 | // add all objs |
254 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
255 | co = &cht_objs[i]; |
256 | error = cuckoo_hashtable_add_with_hash(h, &co->co_cnode, co->co_hash); |
257 | ASSERT(error == 0); |
258 | ASSERT(cuckoo_hashtable_entries(h) == i + 1); |
259 | co->co_state = COS_ADDED; |
260 | } |
261 | |
262 | // find all objs |
263 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
264 | co = &cht_objs[i]; |
265 | ASSERT(co->co_state = COS_ADDED); |
266 | node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
267 | ASSERT(node != NULL); |
268 | ASSERT(node == &co->co_cnode); |
269 | ASSERT(cht_obj_refcnt(co) == 3); |
270 | cht_obj_release(co); |
271 | } |
272 | |
273 | // walk all objs |
274 | cuckoo_hashtable_foreach(h, ^(struct cuckoo_node *curr_node, uint32_t curr_hash) { |
275 | co = container_of(curr_node, struct cht_obj, co_cnode); |
276 | ASSERT(co->co_hash == curr_hash); |
277 | ASSERT(cht_obj_refcnt(co) == 2); |
278 | co->co_seen++; |
279 | }); |
280 | |
281 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
282 | co = &cht_objs[i]; |
283 | ASSERT(co->co_seen == 1); |
284 | } |
285 | |
286 | size_t memory_use_before_shrink = cuckoo_hashtable_memory_footprint(h); |
287 | |
288 | // del all objs |
289 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
290 | co = &cht_objs[i]; |
291 | ASSERT(co->co_state = COS_ADDED); |
292 | node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
293 | ASSERT(cht_obj_refcnt(co) == 3); |
294 | cuckoo_hashtable_del(h, &co->co_cnode, co->co_hash); |
295 | cht_obj_release(co); |
296 | ASSERT(cht_obj_refcnt(co) == 1); |
297 | ASSERT(cuckoo_hashtable_entries(h) == CHT_OBJ_MAX - i - 1); |
298 | co->co_seen = 0; |
299 | } |
300 | |
301 | // shrink |
302 | cuckoo_hashtable_try_shrink(h); |
303 | |
304 | ASSERT(cuckoo_hashtable_memory_footprint(h) < memory_use_before_shrink); |
305 | |
306 | // self healthy check |
307 | cuckoo_hashtable_health_check(h); |
308 | |
309 | cuckoo_hashtable_free(h); |
310 | |
311 | SK_ERR("done" ); |
312 | } |
313 | |
314 | static void |
315 | cht_concurrent_ops_begin() |
316 | { |
317 | /* let skmem_test_start() know we're ready */ |
318 | lck_mtx_lock(&cht_lock); |
319 | os_atomic_inc(&chth_cnt, relaxed); |
320 | wakeup((caddr_t)&chth_cnt); |
321 | |
322 | do { |
323 | (void) msleep(&chth_run, &cht_lock, (PZERO - 1), |
324 | "chthfuncw" , NULL); |
325 | } while (!chth_run); |
326 | lck_mtx_unlock(&cht_lock); |
327 | } |
328 | |
329 | static void |
330 | cht_concurrent_ops_done() |
331 | { |
332 | /* let skmem_test_start() know we're finished */ |
333 | lck_mtx_lock(&cht_lock); |
334 | VERIFY(os_atomic_dec_orig(&chth_cnt, relaxed) != 0); |
335 | wakeup((caddr_t)&chth_cnt); |
336 | lck_mtx_unlock(&cht_lock); |
337 | } |
338 | |
339 | static void |
340 | cht_concurrent_add_init(void) |
341 | { |
342 | h = cuckoo_hashtable_create(¶ms_template); |
343 | } |
344 | |
345 | static void |
346 | cht_concurrent_add(void *v, wait_result_t w) |
347 | { |
348 | #pragma unused(v, w) |
349 | cht_concurrent_ops_begin(); |
350 | |
351 | struct cht_thread_conf *conf = v; |
352 | uint32_t objs_per_cpu = CHT_OBJ_MAX / conf->ctc_nthreads; |
353 | uint32_t objs_start_idx = objs_per_cpu * conf->ctc_id; |
354 | uint32_t objs_to_add = objs_per_cpu; |
355 | |
356 | // last thread id add any tailing objs |
357 | if (conf->ctc_id == conf->ctc_nthreads - 1) { |
358 | objs_to_add += (CHT_OBJ_MAX % conf->ctc_nthreads); |
359 | } |
360 | |
361 | for (uint32_t i = 0; i < objs_to_add; i++) { |
362 | struct cht_obj *co = &cht_objs[objs_start_idx + i]; |
363 | int error = cuckoo_hashtable_add_with_hash(h, &co->co_cnode, co->co_hash); |
364 | ASSERT(error == 0); |
365 | co->co_state = COS_ADDED; |
366 | |
367 | struct cuckoo_node *node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
368 | ASSERT(node != NULL); |
369 | ASSERT(node == &co->co_cnode); |
370 | cht_obj_release(co); |
371 | } |
372 | |
373 | cht_concurrent_ops_done(); |
374 | } |
375 | |
376 | static void |
377 | cht_concurrent_add_check(void) |
378 | { |
379 | __block struct cht_obj *co = NULL; |
380 | struct cuckoo_node *node = NULL; |
381 | |
382 | // find all objs |
383 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
384 | co = &cht_objs[i]; |
385 | ASSERT(co->co_state = COS_ADDED); |
386 | node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
387 | ASSERT(node != NULL); |
388 | ASSERT(node == &co->co_cnode); |
389 | ASSERT(cht_obj_refcnt(co) == 3); |
390 | cht_obj_release(co); |
391 | } |
392 | |
393 | // walk all objs |
394 | cuckoo_hashtable_foreach(h, ^(struct cuckoo_node *curr_node, uint32_t curr_hash) { |
395 | co = container_of(curr_node, struct cht_obj, co_cnode); |
396 | ASSERT(co->co_hash == curr_hash); |
397 | ASSERT(cht_obj_refcnt(co) == 2); |
398 | co->co_seen++; |
399 | }); |
400 | |
401 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
402 | co = &cht_objs[i]; |
403 | //ASSERT(co->co_seen == 1); |
404 | } |
405 | } |
406 | |
407 | static void |
408 | cht_concurrent_add_fini(void) |
409 | { |
410 | struct cht_obj *co = NULL; |
411 | struct cuckoo_node *node = NULL; |
412 | |
413 | // del all objs |
414 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
415 | co = &cht_objs[i]; |
416 | ASSERT(co->co_state = COS_ADDED); |
417 | node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
418 | ASSERT(cht_obj_refcnt(co) == 3); |
419 | cuckoo_hashtable_del(h, &co->co_cnode, co->co_hash); |
420 | cht_obj_release(co); |
421 | ASSERT(cht_obj_refcnt(co) == 1); |
422 | ASSERT(cuckoo_hashtable_entries(h) == CHT_OBJ_MAX - i - 1); |
423 | } |
424 | |
425 | cuckoo_hashtable_free(h); |
426 | } |
427 | |
428 | |
429 | static void |
430 | cht_concurrent_del_init(void) |
431 | { |
432 | h = cuckoo_hashtable_create(¶ms_template); |
433 | |
434 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
435 | struct cht_obj *co = &cht_objs[i]; |
436 | int error = cuckoo_hashtable_add_with_hash(h, &co->co_cnode, co->co_hash); |
437 | ASSERT(error == 0); |
438 | ASSERT(cuckoo_hashtable_entries(h) == i + 1); |
439 | co->co_state = COS_ADDED; |
440 | } |
441 | } |
442 | |
443 | static void |
444 | cht_concurrent_del(void *v, wait_result_t w) |
445 | { |
446 | #pragma unused(v, w) |
447 | cht_concurrent_ops_begin(); |
448 | |
449 | struct cht_thread_conf *conf = v; |
450 | uint32_t objs_per_cpu = CHT_OBJ_MAX / conf->ctc_nthreads; |
451 | uint32_t objs_start_idx = objs_per_cpu * conf->ctc_id; |
452 | uint32_t objs_to_del = objs_per_cpu; |
453 | |
454 | // last thread id add any tailing objs |
455 | if (conf->ctc_id == conf->ctc_nthreads - 1) { |
456 | objs_to_del += (CHT_OBJ_MAX % conf->ctc_nthreads); |
457 | } |
458 | |
459 | for (uint32_t i = 0; i < objs_to_del; i++) { |
460 | struct cht_obj *co = &cht_objs[objs_start_idx + i]; |
461 | int error = cuckoo_hashtable_del(h, &co->co_cnode, co->co_hash); |
462 | ASSERT(error == 0); |
463 | co->co_state = COS_NOT_ADDED; |
464 | |
465 | struct cuckoo_node *node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
466 | ASSERT(node == NULL); |
467 | ASSERT(cht_obj_refcnt(co) == 1); |
468 | } |
469 | |
470 | cht_concurrent_ops_done(); |
471 | } |
472 | |
473 | static void |
474 | cht_concurrent_del_check(void) |
475 | { |
476 | ASSERT(cuckoo_hashtable_entries(h) == 0); |
477 | |
478 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
479 | struct cht_obj *co = &cht_objs[i]; |
480 | struct cuckoo_node *node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
481 | ASSERT(node == NULL); |
482 | ASSERT(cht_obj_refcnt(co) == 1); |
483 | } |
484 | } |
485 | |
486 | static void |
487 | cht_concurrent_del_fini(void) |
488 | { |
489 | cuckoo_hashtable_free(h); |
490 | } |
491 | |
492 | static void |
493 | cht_concurrent_duo_init(void) |
494 | { |
495 | struct cuckoo_hashtable_params p = params_template; |
496 | p.cht_capacity = CHT_OBJ_MAX / 2; |
497 | h = cuckoo_hashtable_create(&p); |
498 | |
499 | // populate 1/3 of the objects |
500 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i += 3) { |
501 | struct cht_obj *co = &cht_objs[i]; |
502 | int error = cuckoo_hashtable_add_with_hash(h, &co->co_cnode, co->co_hash); |
503 | ASSERT(error == 0); |
504 | co->co_state = COS_ADDED; |
505 | } |
506 | } |
507 | |
508 | static void |
509 | cht_concurrent_duo(void *v, wait_result_t w) |
510 | { |
511 | #pragma unused(v, w) |
512 | #define DUO_ITERATIONS (2 * CHT_OBJ_MAX) |
513 | |
514 | #define DUO_OPS_MASK 0x0000000f |
515 | #define DUO_OPS_ADD 0x9 |
516 | |
517 | #define DUO_IDX_MASK 0xfffffff0 |
518 | #define DUO_IDX_SHIFT 0x8 |
519 | |
520 | cht_concurrent_ops_begin(); |
521 | |
522 | uint32_t *rands; |
523 | rands = sk_alloc_data(sizeof(uint32_t) * DUO_ITERATIONS, Z_WAITOK, cuckoo_test_tag); |
524 | VERIFY(rands != NULL); |
525 | read_random(rands, sizeof(uint32_t) * DUO_ITERATIONS); |
526 | |
527 | for (uint32_t i = 0; i < DUO_ITERATIONS; i++) { |
528 | uint32_t rand, ops, idx; |
529 | rand = rands[i]; |
530 | ops = rand & DUO_OPS_MASK; |
531 | idx = (rand >> DUO_IDX_SHIFT) % CHT_OBJ_MAX; |
532 | |
533 | // choose an ops (add, del, shrink) |
534 | if (ops < DUO_OPS_ADD) { |
535 | struct cht_obj *co = &cht_objs[idx]; |
536 | if (os_atomic_cmpxchg(&co->co_state, COS_NOT_ADDED, COS_BUSY, acq_rel)) { |
537 | struct cuckoo_node *node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
538 | ASSERT(node == NULL); |
539 | int error = cuckoo_hashtable_add_with_hash(h, &co->co_cnode, co->co_hash); |
540 | ASSERT(error == 0); |
541 | ASSERT(cht_obj_refcnt(co) == 2); |
542 | |
543 | co->co_state = COS_ADDED; |
544 | } |
545 | } else { |
546 | struct cht_obj *co = &cht_objs[idx]; |
547 | if (os_atomic_cmpxchg(&co->co_state, COS_ADDED, COS_BUSY, acq_rel)) { |
548 | struct cuckoo_node *node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
549 | ASSERT(node != NULL); |
550 | ASSERT(node == &co->co_cnode); |
551 | int error = cuckoo_hashtable_del(h, &co->co_cnode, co->co_hash); |
552 | ASSERT(error == 0); |
553 | ASSERT(cht_obj_refcnt(co) == 2); |
554 | cht_obj_release(co); |
555 | |
556 | co->co_state = COS_NOT_ADDED; |
557 | } |
558 | } |
559 | } |
560 | |
561 | sk_free_data(rands, sizeof(uint32_t) * DUO_ITERATIONS); |
562 | cht_concurrent_ops_done(); |
563 | } |
564 | |
565 | static void |
566 | cht_concurrent_duo_check(void) |
567 | { |
568 | size_t added = 0; |
569 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
570 | struct cht_obj *co = &cht_objs[i]; |
571 | if (co->co_state == COS_ADDED) { |
572 | struct cuckoo_node *node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
573 | ASSERT(node != NULL); |
574 | ASSERT(node == &co->co_cnode); |
575 | added++; |
576 | cht_obj_release(co); |
577 | } else { |
578 | struct cuckoo_node *node = cuckoo_hashtable_find_with_hash(h, &co->co_key, co->co_hash); |
579 | ASSERT(node == NULL); |
580 | } |
581 | } |
582 | |
583 | ASSERT(added == cuckoo_hashtable_entries(h)); |
584 | } |
585 | |
586 | static void |
587 | cht_concurrent_duo_fini(void) |
588 | { |
589 | for (uint32_t i = 0; i < CHT_OBJ_MAX; i++) { |
590 | struct cht_obj *co = &cht_objs[i]; |
591 | if (co->co_state == COS_ADDED) { |
592 | int error = cuckoo_hashtable_del(h, &co->co_cnode, co->co_hash); |
593 | ASSERT(error == 0); |
594 | } |
595 | } |
596 | |
597 | ASSERT(cuckoo_hashtable_entries(h) == 0); |
598 | |
599 | cuckoo_hashtable_free(h); |
600 | } |
601 | |
602 | static void |
603 | cht_concurrent_tests( |
604 | void (*cht_concurrent_init)(void), |
605 | void (*cht_concurrent_ops)(void *v, wait_result_t w), |
606 | void (*cht_concurrent_check)(void), |
607 | void (*cht_concurrent_fini)(void)) |
608 | { |
609 | uint32_t nthreads = MAX(2, ml_wait_max_cpus() * 3 / 4); |
610 | |
611 | SK_ERR("start, nthreads %d" , nthreads); |
612 | |
613 | cht_concurrent_init(); |
614 | |
615 | // init multithread test config |
616 | if (chth_confs == NULL) { |
617 | chth_nthreads = nthreads; |
618 | chth_confs = sk_alloc_type_array(struct cht_thread_conf, nthreads, |
619 | Z_WAITOK | Z_NOFAIL, cuckoo_test_tag); |
620 | } |
621 | |
622 | for (uint32_t i = 0; i < nthreads; i++) { |
623 | chth_confs[i].ctc_nthreads = nthreads; |
624 | chth_confs[i].ctc_id = i; |
625 | if (kernel_thread_start(cht_concurrent_ops, (void *)&chth_confs[i], |
626 | &chth_confs[i].ctc_thread) != KERN_SUCCESS) { |
627 | panic("failed to create cuckoo test thread" ); |
628 | __builtin_unreachable(); |
629 | } |
630 | } |
631 | |
632 | // wait for threads to spwan |
633 | lck_mtx_lock(&cht_lock); |
634 | do { |
635 | struct timespec ts = { 0, 100 * USEC_PER_SEC }; |
636 | (void) msleep(&chth_cnt, &cht_lock, (PZERO - 1), |
637 | "skmtstartw" , &ts); |
638 | } while (chth_cnt < nthreads); |
639 | VERIFY(chth_cnt == nthreads); |
640 | lck_mtx_unlock(&cht_lock); |
641 | |
642 | // signal threads to run |
643 | lck_mtx_lock(&cht_lock); |
644 | VERIFY(!chth_run); |
645 | chth_run = TRUE; |
646 | wakeup((caddr_t)&chth_run); |
647 | lck_mtx_unlock(&cht_lock); |
648 | |
649 | // wait until all threads are done |
650 | lck_mtx_lock(&cht_lock); |
651 | do { |
652 | struct timespec ts = { 0, 100 * USEC_PER_SEC }; |
653 | (void) msleep(&chth_cnt, &cht_lock, (PZERO - 1), |
654 | "skmtstopw" , &ts); |
655 | } while (chth_cnt != 0); |
656 | chth_run = FALSE; |
657 | lck_mtx_unlock(&cht_lock); |
658 | |
659 | // check results |
660 | cht_concurrent_check(); |
661 | |
662 | cht_concurrent_fini(); |
663 | |
664 | SK_ERR("done" ); |
665 | } |
666 | |
667 | static void |
668 | cuckoo_test_start(void *v, wait_result_t w) |
669 | { |
670 | #pragma unused(v, w) |
671 | lck_mtx_lock(&cht_lock); |
672 | VERIFY(!cht_busy); |
673 | cht_busy = 1; |
674 | lck_mtx_unlock(&cht_lock); |
675 | |
676 | cht_obj_init(); |
677 | |
678 | cht_basic_tests(); |
679 | |
680 | cht_concurrent_tests(cht_concurrent_add_init, cht_concurrent_add, cht_concurrent_add_check, cht_concurrent_add_fini); |
681 | cht_concurrent_tests(cht_concurrent_del_init, cht_concurrent_del, cht_concurrent_del_check, cht_concurrent_del_fini); |
682 | cht_concurrent_tests(cht_concurrent_duo_init, cht_concurrent_duo, cht_concurrent_duo_check, cht_concurrent_duo_fini); |
683 | |
684 | lck_mtx_lock(&cht_lock); |
685 | cht_enabled = 1; |
686 | wakeup((caddr_t)&cht_enabled); |
687 | lck_mtx_unlock(&cht_lock); |
688 | } |
689 | |
690 | static void |
691 | cuckoo_test_stop(void *v, wait_result_t w) |
692 | { |
693 | #pragma unused(v, w) |
694 | |
695 | if (chth_confs != NULL) { |
696 | sk_free_type_array(struct cht_thread_conf, chth_nthreads, chth_confs); |
697 | chth_confs = NULL; |
698 | chth_nthreads = 0; |
699 | } |
700 | |
701 | cht_obj_fini(); |
702 | |
703 | lck_mtx_lock(&cht_lock); |
704 | VERIFY(cht_busy); |
705 | cht_busy = 0; |
706 | cht_enabled = 0; |
707 | wakeup((caddr_t)&cht_enabled); |
708 | lck_mtx_unlock(&cht_lock); |
709 | } |
710 | |
711 | static int |
712 | sysctl_cuckoo_test(__unused struct sysctl_oid *oidp, |
713 | __unused void *arg1, __unused int arg2, struct sysctl_req *req) |
714 | { |
715 | int error, newvalue, changed; |
716 | thread_t th; |
717 | thread_continue_t func; |
718 | |
719 | lck_mtx_lock(&cht_lock); |
720 | if ((error = sysctl_io_number(req, cht_enabled, sizeof(int), |
721 | &newvalue, &changed)) != 0) { |
722 | SK_ERR("failed to get new sysctl value" ); |
723 | goto done; |
724 | } |
725 | |
726 | if (changed && cht_enabled != newvalue) { |
727 | if (newvalue && cht_busy) { |
728 | SK_ERR("previous cuckoo test instance is still active" ); |
729 | error = EBUSY; |
730 | goto done; |
731 | } |
732 | |
733 | if (newvalue) { |
734 | func = cuckoo_test_start; |
735 | } else { |
736 | func = cuckoo_test_stop; |
737 | } |
738 | |
739 | if (kernel_thread_start(func, NULL, &th) != KERN_SUCCESS) { |
740 | SK_ERR("failed to create cuckoo test action thread" ); |
741 | error = EBUSY; |
742 | goto done; |
743 | } |
744 | do { |
745 | SK_ERR("waiting for %s to complete" , |
746 | newvalue ? "startup" : "shutdown" ); |
747 | error = msleep(&cht_enabled, &cht_lock, |
748 | PWAIT | PCATCH, "skmtw" , NULL); |
749 | /* BEGIN CSTYLED */ |
750 | /* |
751 | * Loop exit conditions: |
752 | * - we were interrupted |
753 | * OR |
754 | * - we are starting up and are enabled |
755 | * (Startup complete) |
756 | * OR |
757 | * - we are starting up and are not busy |
758 | * (Failed startup) |
759 | * OR |
760 | * - we are shutting down and are not busy |
761 | * (Shutdown complete) |
762 | */ |
763 | /* END CSTYLED */ |
764 | } while (!((error == EINTR) || (newvalue && cht_enabled) || |
765 | (newvalue && !cht_busy) || (!newvalue && !cht_busy))); |
766 | |
767 | SK_ERR("exited from msleep" ); |
768 | thread_deallocate(th); |
769 | } |
770 | |
771 | done: |
772 | lck_mtx_unlock(&cht_lock); |
773 | return error; |
774 | } |
775 | |
776 | SYSCTL_PROC(_kern_skywalk_libcuckoo, OID_AUTO, test, |
777 | CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_LOCKED, NULL, 0, |
778 | sysctl_cuckoo_test, "I" , "Start Cuckoo hashtable test" ); |
779 | |
780 | #endif /* DEVELOPMENT || DEBUG */ |
781 | |