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