xref: /unit/src/test/nxt_lvlhsh_test.c (revision 1563:d32bc428f46b)
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
nxt_lvlhsh_test_key_test(nxt_lvlhsh_query_t * lhq,void * data)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 const nxt_lvlhsh_proto_t  malloc_proto  nxt_aligned(64) = {
23384Szelenkov@nginx.com     //NXT_LVLHSH_LARGE_MEMALIGN,
24384Szelenkov@nginx.com     NXT_LVLHSH_DEFAULT,
25384Szelenkov@nginx.com     nxt_lvlhsh_test_key_test,
26384Szelenkov@nginx.com     nxt_lvlhsh_alloc,
27384Szelenkov@nginx.com     nxt_lvlhsh_free,
28384Szelenkov@nginx.com };
29384Szelenkov@nginx.com 
30384Szelenkov@nginx.com static const nxt_lvlhsh_proto_t  pool_proto  nxt_aligned(64) = {
31384Szelenkov@nginx.com     NXT_LVLHSH_LARGE_SLAB,
32384Szelenkov@nginx.com     nxt_lvlhsh_test_key_test,
33*1563Svbart@nginx.com     nxt_mp_lvlhsh_alloc,
34*1563Svbart@nginx.com     nxt_mp_lvlhsh_free,
35384Szelenkov@nginx.com };
36384Szelenkov@nginx.com 
37384Szelenkov@nginx.com 
38384Szelenkov@nginx.com static nxt_int_t
nxt_lvlhsh_test_add(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto,void * pool,uintptr_t key)39384Szelenkov@nginx.com nxt_lvlhsh_test_add(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
40384Szelenkov@nginx.com     void *pool, uintptr_t key)
41384Szelenkov@nginx.com {
42384Szelenkov@nginx.com     nxt_lvlhsh_query_t  lhq;
43384Szelenkov@nginx.com 
44384Szelenkov@nginx.com     lhq.key_hash = key;
45384Szelenkov@nginx.com     lhq.replace = 0;
46384Szelenkov@nginx.com     lhq.key.length = sizeof(uintptr_t);
47384Szelenkov@nginx.com     lhq.key.start = (u_char *) &key;
48384Szelenkov@nginx.com     lhq.value = (void *) key;
49384Szelenkov@nginx.com     lhq.proto = proto;
50384Szelenkov@nginx.com     lhq.pool = pool;
51384Szelenkov@nginx.com 
52384Szelenkov@nginx.com     switch (nxt_lvlhsh_insert(lh, &lhq)) {
53384Szelenkov@nginx.com 
54384Szelenkov@nginx.com     case NXT_OK:
55384Szelenkov@nginx.com         return NXT_OK;
56384Szelenkov@nginx.com 
57384Szelenkov@nginx.com     case NXT_DECLINED:
58384Szelenkov@nginx.com         nxt_thread_log_alert("lvlhsh test failed: "
59384Szelenkov@nginx.com                              "key %p is already in hash", key);
60384Szelenkov@nginx.com         /* Fall through. */
61384Szelenkov@nginx.com     default:
62384Szelenkov@nginx.com         return NXT_ERROR;
63384Szelenkov@nginx.com     }
64384Szelenkov@nginx.com }
65384Szelenkov@nginx.com 
66384Szelenkov@nginx.com 
67384Szelenkov@nginx.com static nxt_int_t
nxt_lvlhsh_test_get(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto,uintptr_t key)68384Szelenkov@nginx.com nxt_lvlhsh_test_get(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
69384Szelenkov@nginx.com     uintptr_t key)
70384Szelenkov@nginx.com {
71384Szelenkov@nginx.com     nxt_lvlhsh_query_t  lhq;
72384Szelenkov@nginx.com 
73384Szelenkov@nginx.com     lhq.key_hash = key;
74384Szelenkov@nginx.com     lhq.key.length = sizeof(uintptr_t);
75384Szelenkov@nginx.com     lhq.key.start = (u_char *) &key;
76384Szelenkov@nginx.com     lhq.proto = proto;
77384Szelenkov@nginx.com 
78384Szelenkov@nginx.com     if (nxt_lvlhsh_find(lh, &lhq) == NXT_OK) {
79384Szelenkov@nginx.com 
80384Szelenkov@nginx.com         if (key == (uintptr_t) lhq.value) {
81384Szelenkov@nginx.com             return NXT_OK;
82384Szelenkov@nginx.com         }
83384Szelenkov@nginx.com     }
84384Szelenkov@nginx.com 
85384Szelenkov@nginx.com     nxt_thread_log_alert("lvlhsh test failed: "
86384Szelenkov@nginx.com                          "key %p not found in hash", key);
87384Szelenkov@nginx.com 
88384Szelenkov@nginx.com     return NXT_ERROR;
89384Szelenkov@nginx.com }
90384Szelenkov@nginx.com 
91384Szelenkov@nginx.com 
92384Szelenkov@nginx.com static nxt_int_t
nxt_lvlhsh_test_delete(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto,void * pool,uintptr_t key)93384Szelenkov@nginx.com nxt_lvlhsh_test_delete(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
94384Szelenkov@nginx.com     void *pool, uintptr_t key)
95384Szelenkov@nginx.com {
96384Szelenkov@nginx.com     nxt_int_t           ret;
97384Szelenkov@nginx.com     nxt_lvlhsh_query_t  lhq;
98384Szelenkov@nginx.com 
99384Szelenkov@nginx.com     lhq.key_hash = key;
100384Szelenkov@nginx.com     lhq.key.length = sizeof(uintptr_t);
101384Szelenkov@nginx.com     lhq.key.start = (u_char *) &key;
102384Szelenkov@nginx.com     lhq.proto = proto;
103384Szelenkov@nginx.com     lhq.pool = pool;
104384Szelenkov@nginx.com 
105384Szelenkov@nginx.com     ret = nxt_lvlhsh_delete(lh, &lhq);
106384Szelenkov@nginx.com 
107384Szelenkov@nginx.com     if (ret != NXT_OK) {
108384Szelenkov@nginx.com         nxt_thread_log_alert("lvlhsh test failed: "
109384Szelenkov@nginx.com                              "key %p not found in hash", key);
110384Szelenkov@nginx.com     }
111384Szelenkov@nginx.com 
112384Szelenkov@nginx.com     return ret;
113384Szelenkov@nginx.com }
114384Szelenkov@nginx.com 
115384Szelenkov@nginx.com 
116384Szelenkov@nginx.com nxt_int_t
nxt_lvlhsh_test(nxt_thread_t * thr,nxt_uint_t n,nxt_bool_t use_pool)117384Szelenkov@nginx.com nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool)
118384Szelenkov@nginx.com {
119594Sigor@sysoev.ru     void                      *value;
120840Svbart@nginx.com     uint32_t                  key;
121384Szelenkov@nginx.com     nxt_mp_t                  *mp;
122384Szelenkov@nginx.com     nxt_nsec_t                start, end;
123384Szelenkov@nginx.com     nxt_uint_t                i;
124384Szelenkov@nginx.com     nxt_lvlhsh_t              lh;
125384Szelenkov@nginx.com     nxt_lvlhsh_each_t         lhe;
126384Szelenkov@nginx.com     const nxt_lvlhsh_proto_t  *proto;
127384Szelenkov@nginx.com 
128384Szelenkov@nginx.com     const size_t              min_chunk_size = 32;
129384Szelenkov@nginx.com     const size_t              page_size = 1024;
130384Szelenkov@nginx.com     const size_t              page_alignment = 128;
131384Szelenkov@nginx.com     const size_t              cluster_size = 4096;
132384Szelenkov@nginx.com 
133384Szelenkov@nginx.com     nxt_thread_time_update(thr);
134384Szelenkov@nginx.com     start = nxt_thread_monotonic_time(thr);
135384Szelenkov@nginx.com 
136384Szelenkov@nginx.com     if (use_pool) {
137384Szelenkov@nginx.com         mp = nxt_mp_create(cluster_size, page_alignment, page_size,
138384Szelenkov@nginx.com                            min_chunk_size);
139384Szelenkov@nginx.com         if (mp == NULL) {
140384Szelenkov@nginx.com             return NXT_ERROR;
141384Szelenkov@nginx.com         }
142384Szelenkov@nginx.com 
143384Szelenkov@nginx.com         nxt_log_error(NXT_LOG_NOTICE, thr->log,
144384Szelenkov@nginx.com                       "lvlhsh test started: %uD pool", n);
145384Szelenkov@nginx.com         proto = &pool_proto;
146384Szelenkov@nginx.com 
147384Szelenkov@nginx.com     } else {
148384Szelenkov@nginx.com         nxt_log_error(NXT_LOG_NOTICE, thr->log,
149384Szelenkov@nginx.com                       "lvlhsh test started: %uD malloc", n);
150384Szelenkov@nginx.com         proto = &malloc_proto;
151384Szelenkov@nginx.com         mp = NULL;
152384Szelenkov@nginx.com     }
153384Szelenkov@nginx.com 
154384Szelenkov@nginx.com     nxt_memzero(&lh, sizeof(nxt_lvlhsh_t));
155384Szelenkov@nginx.com 
156384Szelenkov@nginx.com     key = 0;
157384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
158384Szelenkov@nginx.com         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
159384Szelenkov@nginx.com 
160384Szelenkov@nginx.com         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
161384Szelenkov@nginx.com             nxt_log_error(NXT_LOG_NOTICE, thr->log,
162384Szelenkov@nginx.com                           "lvlhsh add test failed at %ui", i);
163384Szelenkov@nginx.com             return NXT_ERROR;
164384Szelenkov@nginx.com         }
165384Szelenkov@nginx.com     }
166384Szelenkov@nginx.com 
167384Szelenkov@nginx.com     key = 0;
168384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
169384Szelenkov@nginx.com         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
170384Szelenkov@nginx.com 
171384Szelenkov@nginx.com         if (nxt_lvlhsh_test_get(&lh, proto, key) != NXT_OK) {
172384Szelenkov@nginx.com             return NXT_ERROR;
173384Szelenkov@nginx.com         }
174384Szelenkov@nginx.com     }
175384Szelenkov@nginx.com 
176598Sigor@sysoev.ru     nxt_lvlhsh_each_init(&lhe, proto);
177384Szelenkov@nginx.com 
178384Szelenkov@nginx.com     for (i = 0; i < n + 1; i++) {
179384Szelenkov@nginx.com         if (nxt_lvlhsh_each(&lh, &lhe) == NULL) {
180384Szelenkov@nginx.com             break;
181384Szelenkov@nginx.com         }
182384Szelenkov@nginx.com     }
183384Szelenkov@nginx.com 
184384Szelenkov@nginx.com     if (i != n) {
185384Szelenkov@nginx.com         nxt_log_error(NXT_LOG_NOTICE, thr->log,
186384Szelenkov@nginx.com                       "lvlhsh each test failed at %ui of %ui", i, n);
187384Szelenkov@nginx.com         return NXT_ERROR;
188384Szelenkov@nginx.com     }
189384Szelenkov@nginx.com 
190384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
191594Sigor@sysoev.ru         value = nxt_lvlhsh_peek(&lh, proto);
192594Sigor@sysoev.ru 
193594Sigor@sysoev.ru         if (value == NULL) {
194594Sigor@sysoev.ru             break;
195594Sigor@sysoev.ru         }
196594Sigor@sysoev.ru 
197594Sigor@sysoev.ru         key = (uintptr_t) value;
198384Szelenkov@nginx.com 
199384Szelenkov@nginx.com         if (nxt_lvlhsh_test_delete(&lh, proto, mp, key) != NXT_OK) {
200384Szelenkov@nginx.com             return NXT_ERROR;
201384Szelenkov@nginx.com         }
202384Szelenkov@nginx.com     }
203384Szelenkov@nginx.com 
204594Sigor@sysoev.ru     if (i != n) {
205594Sigor@sysoev.ru         nxt_log_error(NXT_LOG_NOTICE, thr->log,
206594Sigor@sysoev.ru                       "lvlhsh peek test failed at %ui of %ui", i, n);
207594Sigor@sysoev.ru         return NXT_ERROR;
208594Sigor@sysoev.ru     }
209594Sigor@sysoev.ru 
210595Sigor@sysoev.ru     if (!nxt_lvlhsh_is_empty(&lh)) {
211595Sigor@sysoev.ru         nxt_log_error(NXT_LOG_NOTICE, thr->log,
212595Sigor@sysoev.ru                       "lvlhsh is not empty after deletion");
213595Sigor@sysoev.ru         return NXT_ERROR;
214595Sigor@sysoev.ru     }
215595Sigor@sysoev.ru 
216595Sigor@sysoev.ru     key = 0;
217595Sigor@sysoev.ru     for (i = 0; i < n; i++) {
218595Sigor@sysoev.ru         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
219595Sigor@sysoev.ru 
220595Sigor@sysoev.ru         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
221595Sigor@sysoev.ru             nxt_log_error(NXT_LOG_NOTICE, thr->log,
222595Sigor@sysoev.ru                           "lvlhsh add test failed at %ui", i);
223595Sigor@sysoev.ru             return NXT_ERROR;
224595Sigor@sysoev.ru         }
225595Sigor@sysoev.ru     }
226595Sigor@sysoev.ru 
227595Sigor@sysoev.ru     for (i = 0; i < n; i++) {
228595Sigor@sysoev.ru         value = nxt_lvlhsh_retrieve(&lh, proto, mp);
229595Sigor@sysoev.ru 
230595Sigor@sysoev.ru         if (value == NULL) {
231595Sigor@sysoev.ru             break;
232595Sigor@sysoev.ru         }
233595Sigor@sysoev.ru     }
234595Sigor@sysoev.ru 
235595Sigor@sysoev.ru     if (i != n) {
236595Sigor@sysoev.ru         nxt_log_error(NXT_LOG_NOTICE, thr->log,
237595Sigor@sysoev.ru                       "lvlhsh retrieve test failed at %ui of %ui", i, n);
238595Sigor@sysoev.ru         return NXT_ERROR;
239595Sigor@sysoev.ru     }
240595Sigor@sysoev.ru 
241595Sigor@sysoev.ru     if (!nxt_lvlhsh_is_empty(&lh)) {
242595Sigor@sysoev.ru         nxt_log_error(NXT_LOG_NOTICE, thr->log,
243595Sigor@sysoev.ru                       "lvlhsh is not empty after retrieving");
244595Sigor@sysoev.ru         return NXT_ERROR;
245595Sigor@sysoev.ru     }
246595Sigor@sysoev.ru 
247384Szelenkov@nginx.com     if (mp != NULL) {
248384Szelenkov@nginx.com         if (!nxt_mp_is_empty(mp)) {
249384Szelenkov@nginx.com             nxt_log_error(NXT_LOG_NOTICE, thr->log, "mem pool is not empty");
250384Szelenkov@nginx.com             return NXT_ERROR;
251384Szelenkov@nginx.com         }
252384Szelenkov@nginx.com 
253384Szelenkov@nginx.com         nxt_mp_destroy(mp);
254384Szelenkov@nginx.com     }
255384Szelenkov@nginx.com 
256384Szelenkov@nginx.com     nxt_thread_time_update(thr);
257384Szelenkov@nginx.com     end = nxt_thread_monotonic_time(thr);
258384Szelenkov@nginx.com 
259384Szelenkov@nginx.com     nxt_log_error(NXT_LOG_NOTICE, thr->log, "lvlhsh test passed: %0.3fs",
260384Szelenkov@nginx.com                   (end - start) / 1000000000.0);
261384Szelenkov@nginx.com 
262384Szelenkov@nginx.com     return NXT_OK;
263384Szelenkov@nginx.com }
264