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