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 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 void * 23384Szelenkov@nginx.com nxt_lvlhsh_test_pool_alloc(void *pool, size_t size) 24384Szelenkov@nginx.com { 25384Szelenkov@nginx.com return nxt_mp_align(pool, size, size); 26384Szelenkov@nginx.com } 27384Szelenkov@nginx.com 28384Szelenkov@nginx.com 29384Szelenkov@nginx.com static void 30384Szelenkov@nginx.com nxt_lvlhsh_test_pool_free(void *pool, void *p) 31384Szelenkov@nginx.com { 32384Szelenkov@nginx.com nxt_mp_free(pool, p); 33384Szelenkov@nginx.com } 34384Szelenkov@nginx.com 35384Szelenkov@nginx.com 36384Szelenkov@nginx.com static const nxt_lvlhsh_proto_t malloc_proto nxt_aligned(64) = { 37384Szelenkov@nginx.com //NXT_LVLHSH_LARGE_MEMALIGN, 38384Szelenkov@nginx.com NXT_LVLHSH_DEFAULT, 39384Szelenkov@nginx.com nxt_lvlhsh_test_key_test, 40384Szelenkov@nginx.com nxt_lvlhsh_alloc, 41384Szelenkov@nginx.com nxt_lvlhsh_free, 42384Szelenkov@nginx.com }; 43384Szelenkov@nginx.com 44384Szelenkov@nginx.com static const nxt_lvlhsh_proto_t pool_proto nxt_aligned(64) = { 45384Szelenkov@nginx.com NXT_LVLHSH_LARGE_SLAB, 46384Szelenkov@nginx.com nxt_lvlhsh_test_key_test, 47384Szelenkov@nginx.com nxt_lvlhsh_test_pool_alloc, 48384Szelenkov@nginx.com nxt_lvlhsh_test_pool_free, 49384Szelenkov@nginx.com }; 50384Szelenkov@nginx.com 51384Szelenkov@nginx.com 52384Szelenkov@nginx.com static nxt_int_t 53384Szelenkov@nginx.com nxt_lvlhsh_test_add(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto, 54384Szelenkov@nginx.com void *pool, uintptr_t key) 55384Szelenkov@nginx.com { 56384Szelenkov@nginx.com nxt_lvlhsh_query_t lhq; 57384Szelenkov@nginx.com 58384Szelenkov@nginx.com lhq.key_hash = key; 59384Szelenkov@nginx.com lhq.replace = 0; 60384Szelenkov@nginx.com lhq.key.length = sizeof(uintptr_t); 61384Szelenkov@nginx.com lhq.key.start = (u_char *) &key; 62384Szelenkov@nginx.com lhq.value = (void *) key; 63384Szelenkov@nginx.com lhq.proto = proto; 64384Szelenkov@nginx.com lhq.pool = pool; 65384Szelenkov@nginx.com 66384Szelenkov@nginx.com switch (nxt_lvlhsh_insert(lh, &lhq)) { 67384Szelenkov@nginx.com 68384Szelenkov@nginx.com case NXT_OK: 69384Szelenkov@nginx.com return NXT_OK; 70384Szelenkov@nginx.com 71384Szelenkov@nginx.com case NXT_DECLINED: 72384Szelenkov@nginx.com nxt_thread_log_alert("lvlhsh test failed: " 73384Szelenkov@nginx.com "key %p is already in hash", key); 74384Szelenkov@nginx.com /* Fall through. */ 75384Szelenkov@nginx.com default: 76384Szelenkov@nginx.com return NXT_ERROR; 77384Szelenkov@nginx.com } 78384Szelenkov@nginx.com } 79384Szelenkov@nginx.com 80384Szelenkov@nginx.com 81384Szelenkov@nginx.com static nxt_int_t 82384Szelenkov@nginx.com nxt_lvlhsh_test_get(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto, 83384Szelenkov@nginx.com uintptr_t key) 84384Szelenkov@nginx.com { 85384Szelenkov@nginx.com nxt_lvlhsh_query_t lhq; 86384Szelenkov@nginx.com 87384Szelenkov@nginx.com lhq.key_hash = key; 88384Szelenkov@nginx.com lhq.key.length = sizeof(uintptr_t); 89384Szelenkov@nginx.com lhq.key.start = (u_char *) &key; 90384Szelenkov@nginx.com lhq.proto = proto; 91384Szelenkov@nginx.com 92384Szelenkov@nginx.com if (nxt_lvlhsh_find(lh, &lhq) == NXT_OK) { 93384Szelenkov@nginx.com 94384Szelenkov@nginx.com if (key == (uintptr_t) lhq.value) { 95384Szelenkov@nginx.com return NXT_OK; 96384Szelenkov@nginx.com } 97384Szelenkov@nginx.com } 98384Szelenkov@nginx.com 99384Szelenkov@nginx.com nxt_thread_log_alert("lvlhsh test failed: " 100384Szelenkov@nginx.com "key %p not found in hash", key); 101384Szelenkov@nginx.com 102384Szelenkov@nginx.com return NXT_ERROR; 103384Szelenkov@nginx.com } 104384Szelenkov@nginx.com 105384Szelenkov@nginx.com 106384Szelenkov@nginx.com static nxt_int_t 107384Szelenkov@nginx.com nxt_lvlhsh_test_delete(nxt_lvlhsh_t *lh, const nxt_lvlhsh_proto_t *proto, 108384Szelenkov@nginx.com void *pool, uintptr_t key) 109384Szelenkov@nginx.com { 110384Szelenkov@nginx.com nxt_int_t ret; 111384Szelenkov@nginx.com nxt_lvlhsh_query_t lhq; 112384Szelenkov@nginx.com 113384Szelenkov@nginx.com lhq.key_hash = key; 114384Szelenkov@nginx.com lhq.key.length = sizeof(uintptr_t); 115384Szelenkov@nginx.com lhq.key.start = (u_char *) &key; 116384Szelenkov@nginx.com lhq.proto = proto; 117384Szelenkov@nginx.com lhq.pool = pool; 118384Szelenkov@nginx.com 119384Szelenkov@nginx.com ret = nxt_lvlhsh_delete(lh, &lhq); 120384Szelenkov@nginx.com 121384Szelenkov@nginx.com if (ret != NXT_OK) { 122384Szelenkov@nginx.com nxt_thread_log_alert("lvlhsh test failed: " 123384Szelenkov@nginx.com "key %p not found in hash", key); 124384Szelenkov@nginx.com } 125384Szelenkov@nginx.com 126384Szelenkov@nginx.com return ret; 127384Szelenkov@nginx.com } 128384Szelenkov@nginx.com 129384Szelenkov@nginx.com 130384Szelenkov@nginx.com nxt_int_t 131384Szelenkov@nginx.com nxt_lvlhsh_test(nxt_thread_t *thr, nxt_uint_t n, nxt_bool_t use_pool) 132384Szelenkov@nginx.com { 133594Sigor@sysoev.ru void *value; 134*840Svbart@nginx.com uint32_t key; 135384Szelenkov@nginx.com nxt_mp_t *mp; 136384Szelenkov@nginx.com nxt_nsec_t start, end; 137384Szelenkov@nginx.com nxt_uint_t i; 138384Szelenkov@nginx.com nxt_lvlhsh_t lh; 139384Szelenkov@nginx.com nxt_lvlhsh_each_t lhe; 140384Szelenkov@nginx.com const nxt_lvlhsh_proto_t *proto; 141384Szelenkov@nginx.com 142384Szelenkov@nginx.com const size_t min_chunk_size = 32; 143384Szelenkov@nginx.com const size_t page_size = 1024; 144384Szelenkov@nginx.com const size_t page_alignment = 128; 145384Szelenkov@nginx.com const size_t cluster_size = 4096; 146384Szelenkov@nginx.com 147384Szelenkov@nginx.com nxt_thread_time_update(thr); 148384Szelenkov@nginx.com start = nxt_thread_monotonic_time(thr); 149384Szelenkov@nginx.com 150384Szelenkov@nginx.com if (use_pool) { 151384Szelenkov@nginx.com mp = nxt_mp_create(cluster_size, page_alignment, page_size, 152384Szelenkov@nginx.com min_chunk_size); 153384Szelenkov@nginx.com if (mp == NULL) { 154384Szelenkov@nginx.com return NXT_ERROR; 155384Szelenkov@nginx.com } 156384Szelenkov@nginx.com 157384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, 158384Szelenkov@nginx.com "lvlhsh test started: %uD pool", n); 159384Szelenkov@nginx.com proto = &pool_proto; 160384Szelenkov@nginx.com 161384Szelenkov@nginx.com } else { 162384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, 163384Szelenkov@nginx.com "lvlhsh test started: %uD malloc", n); 164384Szelenkov@nginx.com proto = &malloc_proto; 165384Szelenkov@nginx.com mp = NULL; 166384Szelenkov@nginx.com } 167384Szelenkov@nginx.com 168384Szelenkov@nginx.com nxt_memzero(&lh, sizeof(nxt_lvlhsh_t)); 169384Szelenkov@nginx.com 170384Szelenkov@nginx.com key = 0; 171384Szelenkov@nginx.com for (i = 0; i < n; i++) { 172384Szelenkov@nginx.com key = nxt_murmur_hash2(&key, sizeof(uint32_t)); 173384Szelenkov@nginx.com 174384Szelenkov@nginx.com if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) { 175384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, 176384Szelenkov@nginx.com "lvlhsh add test failed at %ui", i); 177384Szelenkov@nginx.com return NXT_ERROR; 178384Szelenkov@nginx.com } 179384Szelenkov@nginx.com } 180384Szelenkov@nginx.com 181384Szelenkov@nginx.com key = 0; 182384Szelenkov@nginx.com for (i = 0; i < n; i++) { 183384Szelenkov@nginx.com key = nxt_murmur_hash2(&key, sizeof(uint32_t)); 184384Szelenkov@nginx.com 185384Szelenkov@nginx.com if (nxt_lvlhsh_test_get(&lh, proto, key) != NXT_OK) { 186384Szelenkov@nginx.com return NXT_ERROR; 187384Szelenkov@nginx.com } 188384Szelenkov@nginx.com } 189384Szelenkov@nginx.com 190598Sigor@sysoev.ru nxt_lvlhsh_each_init(&lhe, proto); 191384Szelenkov@nginx.com 192384Szelenkov@nginx.com for (i = 0; i < n + 1; i++) { 193384Szelenkov@nginx.com if (nxt_lvlhsh_each(&lh, &lhe) == NULL) { 194384Szelenkov@nginx.com break; 195384Szelenkov@nginx.com } 196384Szelenkov@nginx.com } 197384Szelenkov@nginx.com 198384Szelenkov@nginx.com if (i != n) { 199384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, 200384Szelenkov@nginx.com "lvlhsh each test failed at %ui of %ui", i, n); 201384Szelenkov@nginx.com return NXT_ERROR; 202384Szelenkov@nginx.com } 203384Szelenkov@nginx.com 204384Szelenkov@nginx.com for (i = 0; i < n; i++) { 205594Sigor@sysoev.ru value = nxt_lvlhsh_peek(&lh, proto); 206594Sigor@sysoev.ru 207594Sigor@sysoev.ru if (value == NULL) { 208594Sigor@sysoev.ru break; 209594Sigor@sysoev.ru } 210594Sigor@sysoev.ru 211594Sigor@sysoev.ru key = (uintptr_t) value; 212384Szelenkov@nginx.com 213384Szelenkov@nginx.com if (nxt_lvlhsh_test_delete(&lh, proto, mp, key) != NXT_OK) { 214384Szelenkov@nginx.com return NXT_ERROR; 215384Szelenkov@nginx.com } 216384Szelenkov@nginx.com } 217384Szelenkov@nginx.com 218594Sigor@sysoev.ru if (i != n) { 219594Sigor@sysoev.ru nxt_log_error(NXT_LOG_NOTICE, thr->log, 220594Sigor@sysoev.ru "lvlhsh peek test failed at %ui of %ui", i, n); 221594Sigor@sysoev.ru return NXT_ERROR; 222594Sigor@sysoev.ru } 223594Sigor@sysoev.ru 224595Sigor@sysoev.ru if (!nxt_lvlhsh_is_empty(&lh)) { 225595Sigor@sysoev.ru nxt_log_error(NXT_LOG_NOTICE, thr->log, 226595Sigor@sysoev.ru "lvlhsh is not empty after deletion"); 227595Sigor@sysoev.ru return NXT_ERROR; 228595Sigor@sysoev.ru } 229595Sigor@sysoev.ru 230595Sigor@sysoev.ru key = 0; 231595Sigor@sysoev.ru for (i = 0; i < n; i++) { 232595Sigor@sysoev.ru key = nxt_murmur_hash2(&key, sizeof(uint32_t)); 233595Sigor@sysoev.ru 234595Sigor@sysoev.ru if (nxt_lvlhsh_test_add(&lh, proto, mp, key) != NXT_OK) { 235595Sigor@sysoev.ru nxt_log_error(NXT_LOG_NOTICE, thr->log, 236595Sigor@sysoev.ru "lvlhsh add test failed at %ui", i); 237595Sigor@sysoev.ru return NXT_ERROR; 238595Sigor@sysoev.ru } 239595Sigor@sysoev.ru } 240595Sigor@sysoev.ru 241595Sigor@sysoev.ru for (i = 0; i < n; i++) { 242595Sigor@sysoev.ru value = nxt_lvlhsh_retrieve(&lh, proto, mp); 243595Sigor@sysoev.ru 244595Sigor@sysoev.ru if (value == NULL) { 245595Sigor@sysoev.ru break; 246595Sigor@sysoev.ru } 247595Sigor@sysoev.ru } 248595Sigor@sysoev.ru 249595Sigor@sysoev.ru if (i != n) { 250595Sigor@sysoev.ru nxt_log_error(NXT_LOG_NOTICE, thr->log, 251595Sigor@sysoev.ru "lvlhsh retrieve test failed at %ui of %ui", i, n); 252595Sigor@sysoev.ru return NXT_ERROR; 253595Sigor@sysoev.ru } 254595Sigor@sysoev.ru 255595Sigor@sysoev.ru if (!nxt_lvlhsh_is_empty(&lh)) { 256595Sigor@sysoev.ru nxt_log_error(NXT_LOG_NOTICE, thr->log, 257595Sigor@sysoev.ru "lvlhsh is not empty after retrieving"); 258595Sigor@sysoev.ru return NXT_ERROR; 259595Sigor@sysoev.ru } 260595Sigor@sysoev.ru 261384Szelenkov@nginx.com if (mp != NULL) { 262384Szelenkov@nginx.com if (!nxt_mp_is_empty(mp)) { 263384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, "mem pool is not empty"); 264384Szelenkov@nginx.com return NXT_ERROR; 265384Szelenkov@nginx.com } 266384Szelenkov@nginx.com 267384Szelenkov@nginx.com nxt_mp_destroy(mp); 268384Szelenkov@nginx.com } 269384Szelenkov@nginx.com 270384Szelenkov@nginx.com nxt_thread_time_update(thr); 271384Szelenkov@nginx.com end = nxt_thread_monotonic_time(thr); 272384Szelenkov@nginx.com 273384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, "lvlhsh test passed: %0.3fs", 274384Szelenkov@nginx.com (end - start) / 1000000000.0); 275384Szelenkov@nginx.com 276384Szelenkov@nginx.com return NXT_OK; 277384Szelenkov@nginx.com } 278