1
2 #pragma GCC push_options
3 #pragma GCC optimize("O1")
4 #include "ktest.h"
5 #include "ktest_utils.h"
6 #include <common/idr.h>
7
8 /**
9 * @brief 测试idr的构建,预获取空间是否成功
10 *
11 * 以下函数将被测试:
12 * 1. idr_preload
13 * 2. DECLARE_IDR
14 * 3. idr_init
15 * 4. idr_destroy
16 *
17 * 同时还会(间接)测试一些内部函数:
18 * 1. move_to_free_list
19 *
20 * @param arg0
21 * @param arg1
22 */
ktest_idr_case0(uint64_t arg0,uint64_t arg1)23 static long ktest_idr_case0(uint64_t arg0, uint64_t arg1)
24 {
25 unsigned long bitmap = -1;
26 assert((int)(bitmap == IDR_FULL));
27
28 DECLARE_IDR(k_idr);
29 assert(k_idr.top == NULL); // 刚被创建,必须是NULL
30 assert(k_idr.id_free_cnt == 0); // 必须是0
31 assert(k_idr.free_list == NULL);
32
33 k_idr.id_free_cnt = arg1;
34 idr_init(&k_idr);
35 assert(k_idr.id_free_cnt == 0);
36
37 assert(idr_preload(&k_idr, 0) == 0);
38 assert(k_idr.id_free_cnt == IDR_FREE_MAX);
39
40 for (uint64_t i = 1; i < 64; i++)
41 {
42 int id = __lowbit_id(i), chk_id = -1;
43 for (int j = 0; j < 64; j++)
44 if ((i >> j) & 1)
45 {
46 chk_id = j;
47 break;
48 }
49 assert(id == chk_id);
50 }
51
52 // 销毁
53 idr_destroy(&k_idr);
54 assert(k_idr.id_free_cnt == 0);
55 assert(k_idr.free_list == NULL);
56 assert(k_idr.top == NULL);
57
58 return 0;
59 }
60
61 /**
62 * @brief 测试id的获取，id的删除，id的全体删除, idr的find函数
63 *
64 * @param arg0
65 * @param arg1
66 */
ktest_idr_case1(uint64_t arg0,uint64_t arg1)67 static long ktest_idr_case1(uint64_t arg0, uint64_t arg1)
68 {
69 DECLARE_IDR(k_idr);
70 int a[128];
71
72 // 获取128个id
73 for (int i = 0; i < 128; i++)
74 {
75 assert(idr_alloc(&k_idr, &a[i], &a[i]) == 0);
76 assert(a[i] == i);
77 }
78
79 // 查询128个ptr
80 for (int i = 0; i < 128; i++)
81 {
82 int *ptr = idr_find(&k_idr, a[i]);
83 assert(ptr == &a[i]);
84 assert(ptr != NULL);
85 assert(*ptr == a[i]);
86 }
87
88 // 倒序：删除64个id
89 for (int i = 127; i >= 64; i--)
90 {
91 int *id = idr_remove(&k_idr, a[i]);
92 assert(id != NULL);
93 assert(*id == i);
94 assert(idr_find(&k_idr, a[i]) == NULL);
95 }
96
97 // 正序：删除64个id
98 for (int i = 0; i <= 63; i++)
99 {
100 int *id = idr_remove(&k_idr, a[i]);
101 assert(id != NULL);
102 assert(*id == i);
103 assert(idr_find(&k_idr, a[i]) == NULL);
104 }
105
106 for (int i = 0; i < 128; i++)
107 {
108 assert(idr_count(&k_idr, i) == 0);
109 }
110
111 // 重新申请128个id, 值域范围应该仍然是[0,127]
112 for (int i = 0; i < 128; i++)
113 {
114 assert(idr_alloc(&k_idr, &a[i], &a[i]) == 0);
115 assert(a[i] == i);
116 }
117
118 for (int i = 0; i < 128; i++)
119 {
120 assert(idr_count(&k_idr, i));
121 }
122
123 // 正序：删除32个id
124 for (int i = 0; i <= 31; i++)
125 {
126 int *id = idr_remove(&k_idr, a[i]);
127 assert(id != NULL);
128 assert(*id == i);
129 assert(idr_find(&k_idr, a[i]) == NULL);
130 }
131
132 // 倒序：删除32个id
133 for (int i = 127; i >= 96; i--)
134 {
135 int *id = idr_remove(&k_idr, a[i]);
136 assert(id != NULL);
137 assert(*id == i);
138 assert(idr_find(&k_idr, a[i]) == NULL);
139 }
140
141 // 整体删除
142 idr_remove_all(&k_idr);
143 assert(k_idr.top == NULL);
144
145 // 获取128个id
146 for (int i = 0; i < 128; i++)
147 {
148 assert(idr_alloc(&k_idr, &a[i], &a[i]) == 0);
149 assert(a[i] == i);
150 }
151
152 // 查询128个ptr
153 for (int i = 0; i < 128; i++)
154 {
155 int *ptr = idr_find(&k_idr, a[i]);
156 assert(ptr == &a[i]);
157 assert(*ptr == a[i]);
158 }
159
160 // 正序：删除64个id
161 for (int i = 0; i <= 63; i++)
162 {
163 idr_remove(&k_idr, a[i]);
164 assert(idr_find(&k_idr, a[i]) == NULL);
165 }
166
167 // 倒序：删除64个id
168 for (int i = 127; i >= 64; i--)
169 {
170 idr_remove(&k_idr, a[i]);
171 assert(idr_find(&k_idr, a[i]) == NULL);
172 }
173
174 // 销毁
175 idr_destroy(&k_idr);
176 assert(k_idr.id_free_cnt == 0);
177 assert(k_idr.free_list == NULL);
178
179 return 0;
180 }
181
182 /**
183 * @brief case1 的大数据测试
184 *
185 * @param arg0
186 * @param arg1
187 */
ktest_idr_case2(uint64_t arg0,uint64_t arg1)188 static long ktest_idr_case2(uint64_t arg0, uint64_t arg1)
189 {
190 DECLARE_IDR(k_idr);
191
192 // 获取 1000‘000 个ID
193 const int N = 1e6;
194 // const int N = 1048576;
195 const int M = 2e5;
196
197 int tmp = 0;
198 for (int i = 0; i < N; i++)
199 {
200 barrier();
201 assert(idr_alloc(&k_idr, &tmp, &tmp) == 0);
202 barrier();
203 assert(tmp == i);
204
205 barrier();
206 int *ptr = idr_find(&k_idr, i);
207 barrier();
208 assert(ptr != NULL);
209 assert(*ptr == i);
210
211 barrier();
212 // if (i >= 7255) kdebug("1e6 !!!!!!! : %d", i);
213 assert(idr_count(&k_idr, i));
214 barrier();
215 }
216 // kdebug("111111");
217 // 正向: M 个ID
218 for (int i = 0; i < M; i++)
219 {
220 int *ptr = idr_find(&k_idr, i);
221 assert(ptr != NULL);
222 assert(*ptr == N - 1);
223 idr_remove(&k_idr, i);
224 assert(idr_find(&k_idr, i) == NULL);
225 }
226 // kdebug("22222");
227
228 // 倒序: N-M 个ID
229 for (int i = (N)-1; i >= M; i--)
230 {
231 int *ptr = idr_find(&k_idr, i);
232 assert(*ptr == N - 1);
233 idr_remove(&k_idr, i);
234 assert(idr_find(&k_idr, i) == NULL);
235 }
236 // kdebug("3333333");
237 // 重新插入数据
238 for (int i = 0; i < N; i++)
239 {
240 assert(idr_alloc(&k_idr, &tmp, &tmp) == 0);
241 assert(tmp == i);
242 assert(k_idr.top != NULL);
243
244 int *ptr = idr_find(&k_idr, i);
245 assert(ptr != NULL);
246 assert(*ptr == i);
247 }
248 // kdebug("4444444444");
249 assert(k_idr.top != NULL);
250
251 for (int i = 0; i < M; i++)
252 {
253 assert(idr_replace(&k_idr, NULL, i) == 0);
254 }
255 // kdebug("555555555555555555");
256 // 销毁
257 idr_destroy(&k_idr);
258 assert(k_idr.id_free_cnt == 0);
259 assert(k_idr.free_list == NULL);
260 // kdebug("666666666666");
261 return 0;
262 }
263
264 /**
265 * @brief case1 的大数据测试
266 *
267 * @param arg0
268 * @param arg1
269 */
ktest_idr_case3(uint64_t arg0,uint64_t arg1)270 static long ktest_idr_case3(uint64_t arg0, uint64_t arg1)
271 {
272 DECLARE_IDR(k_idr);
273
274 const int N = 1949;
275 int tmp;
276
277 // 获取ID
278 for (int i = 0; i < N; i++)
279 {
280 assert(idr_alloc(&k_idr, &tmp, &tmp) == 0);
281 assert(tmp == i);
282
283 int *ptr = idr_find(&k_idr, i);
284 assert(ptr != NULL);
285 assert(*ptr == i);
286 }
287
288 // 查询 nextid
289 for (int i = 1; i <= N; i++)
290 {
291 int nextid;
292 int *ptr = idr_find_next_getid(&k_idr, i - 1, &nextid);
293 if (likely(i < N))
294 {
295 assert(ptr != NULL);
296 assert(*ptr == N - 1);
297 assert(nextid == i);
298 }
299 else
300 {
301 assert(ptr == NULL);
302 assert(nextid == -1);
303 }
304 }
305
306 int sz = N;
307 // 删掉某一段
308 for (int i = N / 3, j = 2 * (N / 3), k = 0; i <= j; k++, i++)
309 {
310 int *ptr = idr_find(&k_idr, i);
311 assert(ptr != NULL);
312 assert(*ptr == N - 1);
313 idr_remove(&k_idr, i);
314
315 assert(idr_find(&k_idr, i) == NULL);
316 sz--;
317 assert(k_idr.top != NULL);
318 }
319
320 // 查询 nextid
321 for (int i = 1; i <= N; i++)
322 {
323 int nextid;
324 int *ptr = idr_find_next_getid(&k_idr, i - 1, &nextid);
325 if (likely(i < N))
326 {
327 int target = i < N / 3 ? i : max(i, 2 * (N / 3) + 1);
328 assert(ptr != NULL);
329 assert(*ptr == N - 1);
330 assert(nextid == target);
331 }
332 else
333 {
334 assert(ptr == NULL);
335 assert(nextid == -1);
336 }
337 }
338
339 // 销毁
340 idr_destroy(&k_idr);
341 assert(k_idr.id_free_cnt == 0);
342 assert(k_idr.free_list == NULL);
343
344 return 0;
345 }
346
347 /**
348 * @brief 更加全面覆盖所有函数 - 小数据测试
349 *
350 * @param arg0
351 * @param arg1
352 */
ktest_idr_case4(uint64_t arg0,uint64_t arg1)353 static long ktest_idr_case4(uint64_t arg0, uint64_t arg1)
354 {
355 DECLARE_IDR(k_idr);
356 idr_init(&k_idr);
357
358 const int N = 91173;
359 static uint32_t tmp;
360
361 for (int i = 1; i <= 20; i++)
362 {
363 int M = N / i, T = M / 3, b = 2 * T;
364 for (int j = 0; j < M; j++)
365 {
366 assert(idr_alloc(&k_idr, &tmp, &tmp) == 0);
367 assert(tmp == j);
368 }
369
370 for (int j = b; j >= T; j--)
371 {
372 int *ptr = idr_find(&k_idr, j);
373 assert(ptr != NULL);
374 assert(*ptr == M - 1);
375 idr_remove(&k_idr, j);
376 }
377
378 for (int j = b + 1; j < M; j++)
379 {
380 int *ptr = idr_find(&k_idr, j);
381 assert(ptr != NULL);
382 assert(*ptr == M - 1);
383 idr_remove(&k_idr, j);
384 }
385
386 for (int j = T - 1; j >= 0; j--)
387 {
388 int *ptr = idr_find(&k_idr, j);
389 assert(ptr != NULL);
390 assert(*ptr == M - 1);
391 idr_remove(&k_idr, j);
392 }
393
394 assert(k_idr.top == NULL);
395 assert(idr_empty(&k_idr));
396 }
397
398 // 销毁
399 idr_destroy(&k_idr);
400 assert(k_idr.id_free_cnt == 0);
401 assert(k_idr.free_list == NULL);
402 assert(idr_empty(&k_idr));
403
404 return 0;
405 }
406
407 /**
408 * @brief 测试id的获取，id的删除，id的全体删除, idr的find函数
409 *
410 * @param arg0
411 * @param arg1
412 */
ktest_idr_case5(uint64_t arg0,uint64_t arg1)413 static long ktest_idr_case5(uint64_t arg0, uint64_t arg1)
414 {
415 DECLARE_IDR(k_idr);
416 const int N = 128;
417 int a[N];
418
419 // 获取128个id
420 for (int i = 0; i < N; i++)
421 {
422 assert(idr_alloc(&k_idr, &a[i], &a[i]) == 0);
423 assert(a[i] == i);
424 }
425
426 // 把id指向的指针向后移动一个单位
427 for (int i = 0; i < N; i++)
428 {
429 int *ptr;
430 int flags = idr_replace_get_old(&k_idr, &a[(i + 1) % N], i, (void *)&ptr);
431 assert(flags == 0); // 0 是成功
432 assert(ptr != NULL);
433 assert(*ptr == i);
434
435 // 测试是否替换成功
436 ptr = idr_find(&k_idr, i);
437 assert(ptr != NULL);
438 assert(*ptr == (i + 1) % N);
439 }
440
441 // 销毁
442 idr_destroy(&k_idr);
443 assert(k_idr.id_free_cnt == 0);
444 assert(k_idr.free_list == NULL);
445
446 // destroy之后，再获取128个id
447 for (int i = 0; i < N; i++)
448 {
449 assert(idr_alloc(&k_idr, &a[i], &a[i]) == 0);
450 assert(a[i] == i);
451 }
452
453 // 销毁
454 idr_destroy(&k_idr);
455 assert(idr_empty(&k_idr));
456 assert(k_idr.id_free_cnt == 0);
457 assert(k_idr.free_list == NULL);
458
459 return 0;
460 }
461
462 /**
463 * @brief 测试ida的插入/删除
464 *
465 * @param arg0
466 * @param arg1
467 * @return long
468 */
ktest_idr_case6(uint64_t arg0,uint64_t arg1)469 static long ktest_idr_case6(uint64_t arg0, uint64_t arg1)
470 {
471 assert(IDA_BITMAP_LONGS != 0);
472 assert(IDA_BMP_SIZE != 0);
473 assert(IDA_FULL != 0);
474 assert(IDA_BITMAP_BITS != 0);
475
476 DECLARE_IDA(k_ida);
477 ida_init(&k_ida);
478 io_sfence();
479
480 const int N = IDA_FULL * IDR_SIZE + 1;
481
482 for (int i = 0; i < N; i++)
483 {
484 int p_id;
485 io_sfence();
486 assert(ida_alloc(&k_ida, &p_id) == 0);
487 io_sfence();
488 assert(p_id == i);
489 io_sfence();
490 }
491
492 for (int i = 0; i < N; i++)
493 {
494 assert(ida_count(&k_ida, i) == 1);
495 io_sfence();
496 }
497
498 for (int i = N - 1; i >= 0; i--)
499 {
500 ida_remove(&k_ida, i);
501 io_sfence();
502 assert(ida_count(&k_ida, i) == 0);
503 io_sfence();
504 }
505
506 assert(k_ida.idr.top == NULL);
507
508 for (int i = 0; i < N; i++)
509 {
510 int p_id;
511 io_sfence();
512 assert(ida_alloc(&k_ida, &p_id) == 0);
513 io_sfence();
514 assert(p_id == i);
515 io_sfence();
516 }
517
518 assert(k_ida.idr.top != NULL);
519 io_sfence();
520 ida_destroy(&k_ida);
521 io_sfence();
522 assert(k_ida.idr.top == NULL);
523 io_sfence();
524 assert(k_ida.free_list == NULL);
525 io_sfence();
526 assert(ida_empty(&k_ida));
527 io_sfence();
528
529 // 测试destroy之后能否重新获取ID
530 for (int i = 0; i < N; i++)
531 {
532 int p_id;
533 io_sfence();
534 assert(ida_alloc(&k_ida, &p_id) == 0);
535 io_sfence();
536 assert(p_id == i);
537 io_sfence();
538 }
539
540 for (int i = 0; i < N / 3; i++)
541 {
542 ida_remove(&k_ida, i);
543 io_sfence();
544 assert(ida_count(&k_ida, i) == 0);
545 io_sfence();
546 }
547
548 for (int i = 2 * N / 3; i < N; i++)
549 {
550 ida_remove(&k_ida, i);
551 io_sfence();
552 assert(ida_count(&k_ida, i) == 0);
553 io_sfence();
554 }
555
556 assert(k_ida.idr.top != NULL);
557 io_sfence();
558 ida_destroy(&k_ida);
559 io_sfence();
560 assert(k_ida.idr.top == NULL);
561 io_sfence();
562 assert(k_ida.free_list == NULL);
563 io_sfence();
564 assert(ida_empty(&k_ida));
565 io_sfence();
566
567 return 0;
568 }
569
570 static ktest_case_table kt_idr_func_table[] = {
571 ktest_idr_case0,
572 ktest_idr_case1,
573 // ktest_idr_case2, // 为了加快启动速度, 暂时注释掉这个测试
574 ktest_idr_case3,
575 ktest_idr_case4,
576 ktest_idr_case5,
577 ktest_idr_case6,
578 };
579
ktest_test_idr(void * arg)580 int ktest_test_idr(void *arg)
581 {
582 kTEST("Testing idr...");
583 unsigned int sz = sizeof(kt_idr_func_table) / sizeof(ktest_case_table);
584 for (int i = 0; i < sz; ++i)
585 {
586 kTEST("Testing case %d", i);
587 kt_idr_func_table[i](i, i + 1);
588 }
589 kTEST("idr Test done.");
590 return 0;
591 }
592
593 #pragma GCC pop_options