xref: /unit/src/test/nxt_lvlhsh_test.c (revision 384:8f86d3ff3e29)
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
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 void *
23 nxt_lvlhsh_test_pool_alloc(void *pool, size_t size)
24 {
25     return nxt_mp_align(pool, size, size);
26 }
27 
28 
29 static void
30 nxt_lvlhsh_test_pool_free(void *pool, void *p)
31 {
32     nxt_mp_free(pool, p);
33 }
34 
35 
36 static const nxt_lvlhsh_proto_t  malloc_proto  nxt_aligned(64) = {
37     //NXT_LVLHSH_LARGE_MEMALIGN,
38     NXT_LVLHSH_DEFAULT,
39     nxt_lvlhsh_test_key_test,
40     nxt_lvlhsh_alloc,
41     nxt_lvlhsh_free,
42 };
43 
44 static const nxt_lvlhsh_proto_t  pool_proto  nxt_aligned(64) = {
45     NXT_LVLHSH_LARGE_SLAB,
46     nxt_lvlhsh_test_key_test,
47     nxt_lvlhsh_test_pool_alloc,
48     nxt_lvlhsh_test_pool_free,
49 };
50 
51 
52 static nxt_int_t
53 nxt_lvlhsh_test_add(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
54     void *pool, uintptr_t key)
55 {
56     nxt_lvlhsh_query_t  lhq;
57 
58     lhq.key_hash = key;
59     lhq.replace = 0;
60     lhq.key.length = sizeof(uintptr_t);
61     lhq.key.start = (u_char *) &key;
62     lhq.value = (void *) key;
63     lhq.proto = proto;
64     lhq.pool = pool;
65 
66     switch (nxt_lvlhsh_insert(lh, &lhq)) {
67 
68     case NXT_OK:
69         return NXT_OK;
70 
71     case NXT_DECLINED:
72         nxt_thread_log_alert("lvlhsh test failed: "
73                              "key %p is already in hash", key);
74         /* Fall through. */
75     default:
76         return NXT_ERROR;
77     }
78 }
79 
80 
81 static nxt_int_t
82 nxt_lvlhsh_test_get(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
83     uintptr_t key)
84 {
85     nxt_lvlhsh_query_t  lhq;
86 
87     lhq.key_hash = key;
88     lhq.key.length = sizeof(uintptr_t);
89     lhq.key.start = (u_char *) &key;
90     lhq.proto = proto;
91 
92     if (nxt_lvlhsh_find(lh, &lhq) == NXT_OK) {
93 
94         if (key == (uintptr_t) lhq.value) {
95             return NXT_OK;
96         }
97     }
98 
99     nxt_thread_log_alert("lvlhsh test failed: "
100                          "key %p not found in hash", key);
101 
102     return NXT_ERROR;
103 }
104 
105 
106 static nxt_int_t
107 nxt_lvlhsh_test_delete(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto,
108     void *pool, uintptr_t key)
109 {
110     nxt_int_t           ret;
111     nxt_lvlhsh_query_t  lhq;
112 
113     lhq.key_hash = key;
114     lhq.key.length = sizeof(uintptr_t);
115     lhq.key.start = (u_char *) &key;
116     lhq.proto = proto;
117     lhq.pool = pool;
118 
119     ret = nxt_lvlhsh_delete(lh, &lhq);
120 
121     if (ret != NXT_OK) {
122         nxt_thread_log_alert("lvlhsh test failed: "
123                              "key %p not found in hash", key);
124     }
125 
126     return ret;
127 }
128 
129 
130 nxt_int_t
131 nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool)
132 {
133     uintptr_t                 key;
134     nxt_mp_t                  *mp;
135     nxt_nsec_t                start, end;
136     nxt_uint_t                i;
137     nxt_lvlhsh_t              lh;
138     nxt_lvlhsh_each_t         lhe;
139     const nxt_lvlhsh_proto_t  *proto;
140 
141     const size_t              min_chunk_size = 32;
142     const size_t              page_size = 1024;
143     const size_t              page_alignment = 128;
144     const size_t              cluster_size = 4096;
145 
146     nxt_thread_time_update(thr);
147     start = nxt_thread_monotonic_time(thr);
148 
149     if (use_pool) {
150         mp = nxt_mp_create(cluster_size, page_alignment, page_size,
151                            min_chunk_size);
152         if (mp == NULL) {
153             return NXT_ERROR;
154         }
155 
156         nxt_log_error(NXT_LOG_NOTICE, thr->log,
157                       "lvlhsh test started: %uD pool", n);
158         proto = &pool_proto;
159 
160     } else {
161         nxt_log_error(NXT_LOG_NOTICE, thr->log,
162                       "lvlhsh test started: %uD malloc", n);
163         proto = &malloc_proto;
164         mp = NULL;
165     }
166 
167     nxt_memzero(&lh, sizeof(nxt_lvlhsh_t));
168 
169     key = 0;
170     for (i = 0; i < n; i++) {
171         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
172 
173         if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) {
174             nxt_log_error(NXT_LOG_NOTICE, thr->log,
175                           "lvlhsh add test failed at %ui", i);
176             return NXT_ERROR;
177         }
178     }
179 
180     key = 0;
181     for (i = 0; i < n; i++) {
182         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
183 
184         if (nxt_lvlhsh_test_get(&lh, proto, key) != NXT_OK) {
185             return NXT_ERROR;
186         }
187     }
188 
189     nxt_memzero(&lhe, sizeof(nxt_lvlhsh_each_t));
190     lhe.proto = proto;
191 
192     for (i = 0; i < n + 1; i++) {
193         if (nxt_lvlhsh_each(&lh, &lhe) == NULL) {
194             break;
195         }
196     }
197 
198     if (i != n) {
199         nxt_log_error(NXT_LOG_NOTICE, thr->log,
200                       "lvlhsh each test failed at %ui of %ui", i, n);
201         return NXT_ERROR;
202     }
203 
204     key = 0;
205     for (i = 0; i < n; i++) {
206         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
207 
208         if (nxt_lvlhsh_test_delete(&lh, proto, mp, key) != NXT_OK) {
209             return NXT_ERROR;
210         }
211     }
212 
213     if (mp != NULL) {
214         if (!nxt_mp_is_empty(mp)) {
215             nxt_log_error(NXT_LOG_NOTICE, thr->log, "mem pool is not empty");
216             return NXT_ERROR;
217         }
218 
219         nxt_mp_destroy(mp);
220     }
221 
222     nxt_thread_time_update(thr);
223     end = nxt_thread_monotonic_time(thr);
224 
225     nxt_log_error(NXT_LOG_NOTICE, thr->log, "lvlhsh test passed: %0.3fs",
226                   (end - start) / 1000000000.0);
227 
228     return NXT_OK;
229 }
230