1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 #include <nxt_main.h>
8 #include "nxt_tests.h"
9 
10 
11 static nxt_int_t
nxt_lvlhsh_test_key_test(nxt_lvlhsh_query_t * lhq,void * data)12 nxt_lvlhsh_test_key_test(nxt_lvlhsh_query_t *lhq, void *data)
13 {
14     if (*(uintptr_t *) lhq->key.start == (uintptr_t) data) {
15         return NXT_OK;
16     }
17 
18     return NXT_DECLINED;
19 }
20 
21 
22 static const nxt_lvlhsh_proto_t  malloc_proto  nxt_aligned(64) = {
23     //NXT_LVLHSH_LARGE_MEMALIGN,
24     NXT_LVLHSH_DEFAULT,
25     nxt_lvlhsh_test_key_test,
26     nxt_lvlhsh_alloc,
27     nxt_lvlhsh_free,
28 };
29 
30 static const nxt_lvlhsh_proto_t  pool_proto  nxt_aligned(64) = {
31     NXT_LVLHSH_LARGE_SLAB,
32     nxt_lvlhsh_test_key_test,
33     nxt_mp_lvlhsh_alloc,
34     nxt_mp_lvlhsh_free,
35 };
36 
37 
38 static nxt_int_t
nxt_lvlhsh_test_add(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto,void * pool,uintptr_t key)39 nxt_lvlhsh_test_add(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
40     void *pool, uintptr_t key)
41 {
42     nxt_lvlhsh_query_t  lhq;
43 
44     lhq.key_hash = key;
45     lhq.replace = 0;
46     lhq.key.length = sizeof(uintptr_t);
47     lhq.key.start = (u_char *) &key;
48     lhq.value = (void *) key;
49     lhq.proto = proto;
50     lhq.pool = pool;
51 
52     switch (nxt_lvlhsh_insert(lh, &lhq)) {
53 
54     case NXT_OK:
55         return NXT_OK;
56 
57     case NXT_DECLINED:
58         nxt_thread_log_alert("lvlhsh test failed: "
59                              "key %p is already in hash", key);
60         /* Fall through. */
61     default:
62         return NXT_ERROR;
63     }
64 }
65 
66 
67 static nxt_int_t
nxt_lvlhsh_test_get(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto,uintptr_t key)68 nxt_lvlhsh_test_get(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
69     uintptr_t key)
70 {
71     nxt_lvlhsh_query_t  lhq;
72 
73     lhq.key_hash = key;
74     lhq.key.length = sizeof(uintptr_t);
75     lhq.key.start = (u_char *) &key;
76     lhq.proto = proto;
77 
78     if (nxt_lvlhsh_find(lh, &lhq) == NXT_OK) {
79 
80         if (key == (uintptr_t) lhq.value) {
81             return NXT_OK;
82         }
83     }
84 
85     nxt_thread_log_alert("lvlhsh test failed: "
86                          "key %p not found in hash", key);
87 
88     return NXT_ERROR;
89 }
90 
91 
92 static nxt_int_t
nxt_lvlhsh_test_delete(nxt_lvlhsh_t * lh,const nxt_lvlhsh_proto_t * proto,void * pool,uintptr_t key)93 nxt_lvlhsh_test_delete(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
94     void *pool, uintptr_t key)
95 {
96     nxt_int_t           ret;
97     nxt_lvlhsh_query_t  lhq;
98 
99     lhq.key_hash = key;
100     lhq.key.length = sizeof(uintptr_t);
101     lhq.key.start = (u_char *) &key;
102     lhq.proto = proto;
103     lhq.pool = pool;
104 
105     ret = nxt_lvlhsh_delete(lh, &lhq);
106 
107     if (ret != NXT_OK) {
108         nxt_thread_log_alert("lvlhsh test failed: "
109                              "key %p not found in hash", key);
110     }
111 
112     return ret;
113 }
114 
115 
116 nxt_int_t
nxt_lvlhsh_test(nxt_thread_t * thr,nxt_uint_t n,nxt_bool_t use_pool)117 nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool)
118 {
119     void                      *value;
120     uint32_t                  key;
121     nxt_mp_t                  *mp;
122     nxt_nsec_t                start, end;
123     nxt_uint_t                i;
124     nxt_lvlhsh_t              lh;
125     nxt_lvlhsh_each_t         lhe;
126     const nxt_lvlhsh_proto_t  *proto;
127 
128     const size_t              min_chunk_size = 32;
129     const size_t              page_size = 1024;
130     const size_t              page_alignment = 128;
131     const size_t              cluster_size = 4096;
132 
133     nxt_thread_time_update(thr);
134     start = nxt_thread_monotonic_time(thr);
135 
136     if (use_pool) {
137         mp = nxt_mp_create(cluster_size, page_alignment, page_size,
138                            min_chunk_size);
139         if (mp == NULL) {
140             return NXT_ERROR;
141         }
142 
143         nxt_log_error(NXT_LOG_NOTICE, thr->log,
144                       "lvlhsh test started: %uD pool", n);
145         proto = &pool_proto;
146 
147     } else {
148         nxt_log_error(NXT_LOG_NOTICE, thr->log,
149                       "lvlhsh test started: %uD malloc", n);
150         proto = &malloc_proto;
151         mp = NULL;
152     }
153 
154     nxt_memzero(&lh, sizeof(nxt_lvlhsh_t));
155 
156     key = 0;
157     for (i = 0; i < n; i++) {
158         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
159 
160         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
161             nxt_log_error(NXT_LOG_NOTICE, thr->log,
162                           "lvlhsh add test failed at %ui", i);
163             return NXT_ERROR;
164         }
165     }
166 
167     key = 0;
168     for (i = 0; i < n; i++) {
169         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
170 
171         if (nxt_lvlhsh_test_get(&lh, proto, key) != NXT_OK) {
172             return NXT_ERROR;
173         }
174     }
175 
176     nxt_lvlhsh_each_init(&lhe, proto);
177 
178     for (i = 0; i < n + 1; i++) {
179         if (nxt_lvlhsh_each(&lh, &lhe) == NULL) {
180             break;
181         }
182     }
183 
184     if (i != n) {
185         nxt_log_error(NXT_LOG_NOTICE, thr->log,
186                       "lvlhsh each test failed at %ui of %ui", i, n);
187         return NXT_ERROR;
188     }
189 
190     for (i = 0; i < n; i++) {
191         value = nxt_lvlhsh_peek(&lh, proto);
192 
193         if (value == NULL) {
194             break;
195         }
196 
197         key = (uintptr_t) value;
198 
199         if (nxt_lvlhsh_test_delete(&lh, proto, mp, key) != NXT_OK) {
200             return NXT_ERROR;
201         }
202     }
203 
204     if (i != n) {
205         nxt_log_error(NXT_LOG_NOTICE, thr->log,
206                       "lvlhsh peek test failed at %ui of %ui", i, n);
207         return NXT_ERROR;
208     }
209 
210     if (!nxt_lvlhsh_is_empty(&lh)) {
211         nxt_log_error(NXT_LOG_NOTICE, thr->log,
212                       "lvlhsh is not empty after deletion");
213         return NXT_ERROR;
214     }
215 
216     key = 0;
217     for (i = 0; i < n; i++) {
218         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
219 
220         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
221             nxt_log_error(NXT_LOG_NOTICE, thr->log,
222                           "lvlhsh add test failed at %ui", i);
223             return NXT_ERROR;
224         }
225     }
226 
227     for (i = 0; i < n; i++) {
228         value = nxt_lvlhsh_retrieve(&lh, proto, mp);
229 
230         if (value == NULL) {
231             break;
232         }
233     }
234 
235     if (i != n) {
236         nxt_log_error(NXT_LOG_NOTICE, thr->log,
237                       "lvlhsh retrieve test failed at %ui of %ui", i, n);
238         return NXT_ERROR;
239     }
240 
241     if (!nxt_lvlhsh_is_empty(&lh)) {
242         nxt_log_error(NXT_LOG_NOTICE, thr->log,
243                       "lvlhsh is not empty after retrieving");
244         return NXT_ERROR;
245     }
246 
247     if (mp != NULL) {
248         if (!nxt_mp_is_empty(mp)) {
249             nxt_log_error(NXT_LOG_NOTICE, thr->log, "mem pool is not empty");
250             return NXT_ERROR;
251         }
252 
253         nxt_mp_destroy(mp);
254     }
255 
256     nxt_thread_time_update(thr);
257     end = nxt_thread_monotonic_time(thr);
258 
259     nxt_log_error(NXT_LOG_NOTICE, thr->log, "lvlhsh test passed: %0.3fs",
260                   (end - start) / 1000000000.0);
261 
262     return NXT_OK;
263 }
264