xref: /unit/src/test/nxt_lvlhsh_test.c (revision 840)
1384Szelenkov@nginx.com 
2384Szelenkov@nginx.com /*
3384Szelenkov@nginx.com  * Copyright (C) Igor Sysoev
4384Szelenkov@nginx.com  * Copyright (C) NGINX, Inc.
5384Szelenkov@nginx.com  */
6384Szelenkov@nginx.com 
7384Szelenkov@nginx.com #include <nxt_main.h>
8384Szelenkov@nginx.com #include "nxt_tests.h"
9384Szelenkov@nginx.com 
10384Szelenkov@nginx.com 
11384Szelenkov@nginx.com static nxt_int_t
12384Szelenkov@nginx.com nxt_lvlhsh_test_key_test(nxt_lvlhsh_query_t *lhq, void *data)
13384Szelenkov@nginx.com {
14384Szelenkov@nginx.com     if (*(uintptr_t *) lhq->key.start == (uintptr_t) data) {
15384Szelenkov@nginx.com         return NXT_OK;
16384Szelenkov@nginx.com     }
17384Szelenkov@nginx.com 
18384Szelenkov@nginx.com     return NXT_DECLINED;
19384Szelenkov@nginx.com }
20384Szelenkov@nginx.com 
21384Szelenkov@nginx.com 
22384Szelenkov@nginx.com static void *
23384Szelenkov@nginx.com nxt_lvlhsh_test_pool_alloc(void *pool, size_t size)
24384Szelenkov@nginx.com {
25384Szelenkov@nginx.com     return nxt_mp_align(pool, size, size);
26384Szelenkov@nginx.com }
27384Szelenkov@nginx.com 
28384Szelenkov@nginx.com 
29384Szelenkov@nginx.com static void
30384Szelenkov@nginx.com nxt_lvlhsh_test_pool_free(void *pool, void *p)
31384Szelenkov@nginx.com {
32384Szelenkov@nginx.com     nxt_mp_free(pool, p);
33384Szelenkov@nginx.com }
34384Szelenkov@nginx.com 
35384Szelenkov@nginx.com 
36384Szelenkov@nginx.com static const nxt_lvlhsh_proto_t  malloc_proto  nxt_aligned(64) = {
37384Szelenkov@nginx.com     //NXT_LVLHSH_LARGE_MEMALIGN,
38384Szelenkov@nginx.com     NXT_LVLHSH_DEFAULT,
39384Szelenkov@nginx.com     nxt_lvlhsh_test_key_test,
40384Szelenkov@nginx.com     nxt_lvlhsh_alloc,
41384Szelenkov@nginx.com     nxt_lvlhsh_free,
42384Szelenkov@nginx.com };
43384Szelenkov@nginx.com 
44384Szelenkov@nginx.com static const nxt_lvlhsh_proto_t  pool_proto  nxt_aligned(64) = {
45384Szelenkov@nginx.com     NXT_LVLHSH_LARGE_SLAB,
46384Szelenkov@nginx.com     nxt_lvlhsh_test_key_test,
47384Szelenkov@nginx.com     nxt_lvlhsh_test_pool_alloc,
48384Szelenkov@nginx.com     nxt_lvlhsh_test_pool_free,
49384Szelenkov@nginx.com };
50384Szelenkov@nginx.com 
51384Szelenkov@nginx.com 
52384Szelenkov@nginx.com static nxt_int_t
53384Szelenkov@nginx.com nxt_lvlhsh_test_add(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
54384Szelenkov@nginx.com     void *pool, uintptr_t key)
55384Szelenkov@nginx.com {
56384Szelenkov@nginx.com     nxt_lvlhsh_query_t  lhq;
57384Szelenkov@nginx.com 
58384Szelenkov@nginx.com     lhq.key_hash = key;
59384Szelenkov@nginx.com     lhq.replace = 0;
60384Szelenkov@nginx.com     lhq.key.length = sizeof(uintptr_t);
61384Szelenkov@nginx.com     lhq.key.start = (u_char *) &key;
62384Szelenkov@nginx.com     lhq.value = (void *) key;
63384Szelenkov@nginx.com     lhq.proto = proto;
64384Szelenkov@nginx.com     lhq.pool = pool;
65384Szelenkov@nginx.com 
66384Szelenkov@nginx.com     switch (nxt_lvlhsh_insert(lh, &lhq)) {
67384Szelenkov@nginx.com 
68384Szelenkov@nginx.com     case NXT_OK:
69384Szelenkov@nginx.com         return NXT_OK;
70384Szelenkov@nginx.com 
71384Szelenkov@nginx.com     case NXT_DECLINED:
72384Szelenkov@nginx.com         nxt_thread_log_alert("lvlhsh test failed: "
73384Szelenkov@nginx.com                              "key %p is already in hash", key);
74384Szelenkov@nginx.com         /* Fall through. */
75384Szelenkov@nginx.com     default:
76384Szelenkov@nginx.com         return NXT_ERROR;
77384Szelenkov@nginx.com     }
78384Szelenkov@nginx.com }
79384Szelenkov@nginx.com 
80384Szelenkov@nginx.com 
81384Szelenkov@nginx.com static nxt_int_t
82384Szelenkov@nginx.com nxt_lvlhsh_test_get(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
83384Szelenkov@nginx.com     uintptr_t key)
84384Szelenkov@nginx.com {
85384Szelenkov@nginx.com     nxt_lvlhsh_query_t  lhq;
86384Szelenkov@nginx.com 
87384Szelenkov@nginx.com     lhq.key_hash = key;
88384Szelenkov@nginx.com     lhq.key.length = sizeof(uintptr_t);
89384Szelenkov@nginx.com     lhq.key.start = (u_char *) &key;
90384Szelenkov@nginx.com     lhq.proto = proto;
91384Szelenkov@nginx.com 
92384Szelenkov@nginx.com     if (nxt_lvlhsh_find(lh, &lhq) == NXT_OK) {
93384Szelenkov@nginx.com 
94384Szelenkov@nginx.com         if (key == (uintptr_t) lhq.value) {
95384Szelenkov@nginx.com             return NXT_OK;
96384Szelenkov@nginx.com         }
97384Szelenkov@nginx.com     }
98384Szelenkov@nginx.com 
99384Szelenkov@nginx.com     nxt_thread_log_alert("lvlhsh test failed: "
100384Szelenkov@nginx.com                          "key %p not found in hash", key);
101384Szelenkov@nginx.com 
102384Szelenkov@nginx.com     return NXT_ERROR;
103384Szelenkov@nginx.com }
104384Szelenkov@nginx.com 
105384Szelenkov@nginx.com 
106384Szelenkov@nginx.com static nxt_int_t
107384Szelenkov@nginx.com nxt_lvlhsh_test_delete(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
108384Szelenkov@nginx.com     void *pool, uintptr_t key)
109384Szelenkov@nginx.com {
110384Szelenkov@nginx.com     nxt_int_t           ret;
111384Szelenkov@nginx.com     nxt_lvlhsh_query_t  lhq;
112384Szelenkov@nginx.com 
113384Szelenkov@nginx.com     lhq.key_hash = key;
114384Szelenkov@nginx.com     lhq.key.length = sizeof(uintptr_t);
115384Szelenkov@nginx.com     lhq.key.start = (u_char *) &key;
116384Szelenkov@nginx.com     lhq.proto = proto;
117384Szelenkov@nginx.com     lhq.pool = pool;
118384Szelenkov@nginx.com 
119384Szelenkov@nginx.com     ret = nxt_lvlhsh_delete(lh, &lhq);
120384Szelenkov@nginx.com 
121384Szelenkov@nginx.com     if (ret != NXT_OK) {
122384Szelenkov@nginx.com         nxt_thread_log_alert("lvlhsh test failed: "
123384Szelenkov@nginx.com                              "key %p not found in hash", key);
124384Szelenkov@nginx.com     }
125384Szelenkov@nginx.com 
126384Szelenkov@nginx.com     return ret;
127384Szelenkov@nginx.com }
128384Szelenkov@nginx.com 
129384Szelenkov@nginx.com 
130384Szelenkov@nginx.com nxt_int_t
131384Szelenkov@nginx.com nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool)
132384Szelenkov@nginx.com {
133594Sigor@sysoev.ru     void                      *value;
134*840Svbart@nginx.com     uint32_t                  key;
135384Szelenkov@nginx.com     nxt_mp_t                  *mp;
136384Szelenkov@nginx.com     nxt_nsec_t                start, end;
137384Szelenkov@nginx.com     nxt_uint_t                i;
138384Szelenkov@nginx.com     nxt_lvlhsh_t              lh;
139384Szelenkov@nginx.com     nxt_lvlhsh_each_t         lhe;
140384Szelenkov@nginx.com     const nxt_lvlhsh_proto_t  *proto;
141384Szelenkov@nginx.com 
142384Szelenkov@nginx.com     const size_t              min_chunk_size = 32;
143384Szelenkov@nginx.com     const size_t              page_size = 1024;
144384Szelenkov@nginx.com     const size_t              page_alignment = 128;
145384Szelenkov@nginx.com     const size_t              cluster_size = 4096;
146384Szelenkov@nginx.com 
147384Szelenkov@nginx.com     nxt_thread_time_update(thr);
148384Szelenkov@nginx.com     start = nxt_thread_monotonic_time(thr);
149384Szelenkov@nginx.com 
150384Szelenkov@nginx.com     if (use_pool) {
151384Szelenkov@nginx.com         mp = nxt_mp_create(cluster_size, page_alignment, page_size,
152384Szelenkov@nginx.com                            min_chunk_size);
153384Szelenkov@nginx.com         if (mp == NULL) {
154384Szelenkov@nginx.com             return NXT_ERROR;
155384Szelenkov@nginx.com         }
156384Szelenkov@nginx.com 
157384Szelenkov@nginx.com         nxt_log_error(NXT_LOG_NOTICE, thr->log,
158384Szelenkov@nginx.com                       "lvlhsh test started: %uD pool", n);
159384Szelenkov@nginx.com         proto = &pool_proto;
160384Szelenkov@nginx.com 
161384Szelenkov@nginx.com     } else {
162384Szelenkov@nginx.com         nxt_log_error(NXT_LOG_NOTICE, thr->log,
163384Szelenkov@nginx.com                       "lvlhsh test started: %uD malloc", n);
164384Szelenkov@nginx.com         proto = &malloc_proto;
165384Szelenkov@nginx.com         mp = NULL;
166384Szelenkov@nginx.com     }
167384Szelenkov@nginx.com 
168384Szelenkov@nginx.com     nxt_memzero(&lh, sizeof(nxt_lvlhsh_t));
169384Szelenkov@nginx.com 
170384Szelenkov@nginx.com     key = 0;
171384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
172384Szelenkov@nginx.com         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
173384Szelenkov@nginx.com 
174384Szelenkov@nginx.com         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
175384Szelenkov@nginx.com             nxt_log_error(NXT_LOG_NOTICE, thr->log,
176384Szelenkov@nginx.com                           "lvlhsh add test failed at %ui", i);
177384Szelenkov@nginx.com             return NXT_ERROR;
178384Szelenkov@nginx.com         }
179384Szelenkov@nginx.com     }
180384Szelenkov@nginx.com 
181384Szelenkov@nginx.com     key = 0;
182384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
183384Szelenkov@nginx.com         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
184384Szelenkov@nginx.com 
185384Szelenkov@nginx.com         if (nxt_lvlhsh_test_get(&lh, proto, key) != NXT_OK) {
186384Szelenkov@nginx.com             return NXT_ERROR;
187384Szelenkov@nginx.com         }
188384Szelenkov@nginx.com     }
189384Szelenkov@nginx.com 
190598Sigor@sysoev.ru     nxt_lvlhsh_each_init(&lhe, proto);
191384Szelenkov@nginx.com 
192384Szelenkov@nginx.com     for (i = 0; i < n + 1; i++) {
193384Szelenkov@nginx.com         if (nxt_lvlhsh_each(&lh, &lhe) == NULL) {
194384Szelenkov@nginx.com             break;
195384Szelenkov@nginx.com         }
196384Szelenkov@nginx.com     }
197384Szelenkov@nginx.com 
198384Szelenkov@nginx.com     if (i != n) {
199384Szelenkov@nginx.com         nxt_log_error(NXT_LOG_NOTICE, thr->log,
200384Szelenkov@nginx.com                       "lvlhsh each test failed at %ui of %ui", i, n);
201384Szelenkov@nginx.com         return NXT_ERROR;
202384Szelenkov@nginx.com     }
203384Szelenkov@nginx.com 
204384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
205594Sigor@sysoev.ru         value = nxt_lvlhsh_peek(&lh, proto);
206594Sigor@sysoev.ru 
207594Sigor@sysoev.ru         if (value == NULL) {
208594Sigor@sysoev.ru             break;
209594Sigor@sysoev.ru         }
210594Sigor@sysoev.ru 
211594Sigor@sysoev.ru         key = (uintptr_t) value;
212384Szelenkov@nginx.com 
213384Szelenkov@nginx.com         if (nxt_lvlhsh_test_delete(&lh, proto, mp, key) != NXT_OK) {
214384Szelenkov@nginx.com             return NXT_ERROR;
215384Szelenkov@nginx.com         }
216384Szelenkov@nginx.com     }
217384Szelenkov@nginx.com 
218594Sigor@sysoev.ru     if (i != n) {
219594Sigor@sysoev.ru         nxt_log_error(NXT_LOG_NOTICE, thr->log,
220594Sigor@sysoev.ru                       "lvlhsh peek test failed at %ui of %ui", i, n);
221594Sigor@sysoev.ru         return NXT_ERROR;
222594Sigor@sysoev.ru     }
223594Sigor@sysoev.ru 
224595Sigor@sysoev.ru     if (!nxt_lvlhsh_is_empty(&lh)) {
225595Sigor@sysoev.ru         nxt_log_error(NXT_LOG_NOTICE, thr->log,
226595Sigor@sysoev.ru                       "lvlhsh is not empty after deletion");
227595Sigor@sysoev.ru         return NXT_ERROR;
228595Sigor@sysoev.ru     }
229595Sigor@sysoev.ru 
230595Sigor@sysoev.ru     key = 0;
231595Sigor@sysoev.ru     for (i = 0; i < n; i++) {
232595Sigor@sysoev.ru         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
233595Sigor@sysoev.ru 
234595Sigor@sysoev.ru         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
235595Sigor@sysoev.ru             nxt_log_error(NXT_LOG_NOTICE, thr->log,
236595Sigor@sysoev.ru                           "lvlhsh add test failed at %ui", i);
237595Sigor@sysoev.ru             return NXT_ERROR;
238595Sigor@sysoev.ru         }
239595Sigor@sysoev.ru     }
240595Sigor@sysoev.ru 
241595Sigor@sysoev.ru     for (i = 0; i < n; i++) {
242595Sigor@sysoev.ru         value = nxt_lvlhsh_retrieve(&lh, proto, mp);
243595Sigor@sysoev.ru 
244595Sigor@sysoev.ru         if (value == NULL) {
245595Sigor@sysoev.ru             break;
246595Sigor@sysoev.ru         }
247595Sigor@sysoev.ru     }
248595Sigor@sysoev.ru 
249595Sigor@sysoev.ru     if (i != n) {
250595Sigor@sysoev.ru         nxt_log_error(NXT_LOG_NOTICE, thr->log,
251595Sigor@sysoev.ru                       "lvlhsh retrieve test failed at %ui of %ui", i, n);
252595Sigor@sysoev.ru         return NXT_ERROR;
253595Sigor@sysoev.ru     }
254595Sigor@sysoev.ru 
255595Sigor@sysoev.ru     if (!nxt_lvlhsh_is_empty(&lh)) {
256595Sigor@sysoev.ru         nxt_log_error(NXT_LOG_NOTICE, thr->log,
257595Sigor@sysoev.ru                       "lvlhsh is not empty after retrieving");
258595Sigor@sysoev.ru         return NXT_ERROR;
259595Sigor@sysoev.ru     }
260595Sigor@sysoev.ru 
261384Szelenkov@nginx.com     if (mp != NULL) {
262384Szelenkov@nginx.com         if (!nxt_mp_is_empty(mp)) {
263384Szelenkov@nginx.com             nxt_log_error(NXT_LOG_NOTICE, thr->log, "mem pool is not empty");
264384Szelenkov@nginx.com             return NXT_ERROR;
265384Szelenkov@nginx.com         }
266384Szelenkov@nginx.com 
267384Szelenkov@nginx.com         nxt_mp_destroy(mp);
268384Szelenkov@nginx.com     }
269384Szelenkov@nginx.com 
270384Szelenkov@nginx.com     nxt_thread_time_update(thr);
271384Szelenkov@nginx.com     end = nxt_thread_monotonic_time(thr);
272384Szelenkov@nginx.com 
273384Szelenkov@nginx.com     nxt_log_error(NXT_LOG_NOTICE, thr->log, "lvlhsh test passed: %0.3fs",
274384Szelenkov@nginx.com                   (end - start) / 1000000000.0);
275384Szelenkov@nginx.com 
276384Szelenkov@nginx.com     return NXT_OK;
277384Szelenkov@nginx.com }
278