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 = 1048576;
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