1*384Szelenkov@nginx.com
2*384Szelenkov@nginx.com /*
3*384Szelenkov@nginx.com * Copyright (C) Igor Sysoev
4*384Szelenkov@nginx.com * Copyright (C) NGINX, Inc.
5*384Szelenkov@nginx.com */
6*384Szelenkov@nginx.com
7*384Szelenkov@nginx.com #include <nxt_main.h>
8*384Szelenkov@nginx.com #include "nxt_tests.h"
9*384Szelenkov@nginx.com
10*384Szelenkov@nginx.com
11*384Szelenkov@nginx.com typedef struct {
12*384Szelenkov@nginx.com NXT_RBTREE_NODE (node);
13*384Szelenkov@nginx.com uint32_t key;
14*384Szelenkov@nginx.com } nxt_rbtree_test_t;
15*384Szelenkov@nginx.com
16*384Szelenkov@nginx.com
17*384Szelenkov@nginx.com static intptr_t nxt_rbtree_test_comparison(nxt_rbtree_node_t *node1,
18*384Szelenkov@nginx.com nxt_rbtree_node_t *node2);
19*384Szelenkov@nginx.com static nxt_int_t nxt_rbtree_test_compare(uint32_t key1, uint32_t key2);
20*384Szelenkov@nginx.com static int nxt_cdecl nxt_rbtree_test_sort_cmp(const void *one, const void *two);
21*384Szelenkov@nginx.com
22*384Szelenkov@nginx.com
23*384Szelenkov@nginx.com nxt_int_t
nxt_rbtree_test(nxt_thread_t * thr,nxt_uint_t n)24*384Szelenkov@nginx.com nxt_rbtree_test(nxt_thread_t *thr, nxt_uint_t n)
25*384Szelenkov@nginx.com {
26*384Szelenkov@nginx.com void *mark;
27*384Szelenkov@nginx.com uint32_t key, *keys;
28*384Szelenkov@nginx.com nxt_uint_t i;
29*384Szelenkov@nginx.com nxt_nsec_t start, end;
30*384Szelenkov@nginx.com nxt_rbtree_t tree;
31*384Szelenkov@nginx.com nxt_rbtree_node_t *node;
32*384Szelenkov@nginx.com nxt_rbtree_test_t *items, *item;
33*384Szelenkov@nginx.com
34*384Szelenkov@nginx.com nxt_thread_time_update(thr);
35*384Szelenkov@nginx.com
36*384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree test started: %ui", n);
37*384Szelenkov@nginx.com
38*384Szelenkov@nginx.com nxt_rbtree_init(&tree, nxt_rbtree_test_comparison);
39*384Szelenkov@nginx.com
40*384Szelenkov@nginx.com mark = tree.sentinel.right;
41*384Szelenkov@nginx.com
42*384Szelenkov@nginx.com items = nxt_malloc(n * sizeof(nxt_rbtree_test_t));
43*384Szelenkov@nginx.com if (items == NULL) {
44*384Szelenkov@nginx.com return NXT_ERROR;
45*384Szelenkov@nginx.com }
46*384Szelenkov@nginx.com
47*384Szelenkov@nginx.com keys = nxt_malloc(n * sizeof(uint32_t));
48*384Szelenkov@nginx.com if (keys == NULL) {
49*384Szelenkov@nginx.com nxt_free(keys);
50*384Szelenkov@nginx.com return NXT_ERROR;
51*384Szelenkov@nginx.com }
52*384Szelenkov@nginx.com
53*384Szelenkov@nginx.com key = 0;
54*384Szelenkov@nginx.com
55*384Szelenkov@nginx.com for (i = 0; i < n; i++) {
56*384Szelenkov@nginx.com key = nxt_murmur_hash2(&key, sizeof(uint32_t));
57*384Szelenkov@nginx.com
58*384Szelenkov@nginx.com keys[i] = key;
59*384Szelenkov@nginx.com items[i].key = key;
60*384Szelenkov@nginx.com }
61*384Szelenkov@nginx.com
62*384Szelenkov@nginx.com nxt_qsort(keys, n, sizeof(uint32_t), nxt_rbtree_test_sort_cmp);
63*384Szelenkov@nginx.com
64*384Szelenkov@nginx.com nxt_thread_time_update(thr);
65*384Szelenkov@nginx.com start = nxt_thread_monotonic_time(thr);
66*384Szelenkov@nginx.com
67*384Szelenkov@nginx.com for (i = 0; i < n; i++) {
68*384Szelenkov@nginx.com nxt_rbtree_insert(&tree, &items[i].node);
69*384Szelenkov@nginx.com }
70*384Szelenkov@nginx.com
71*384Szelenkov@nginx.com for (i = 0; i < n; i++) {
72*384Szelenkov@nginx.com node = nxt_rbtree_find(&tree, &items[i].node);
73*384Szelenkov@nginx.com
74*384Szelenkov@nginx.com if (node != (nxt_rbtree_node_t *) &items[i].node) {
75*384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree test failed: %08XD not found",
76*384Szelenkov@nginx.com items[i].key);
77*384Szelenkov@nginx.com goto fail;
78*384Szelenkov@nginx.com }
79*384Szelenkov@nginx.com }
80*384Szelenkov@nginx.com
81*384Szelenkov@nginx.com i = 0;
82*384Szelenkov@nginx.com node = nxt_rbtree_min(&tree);
83*384Szelenkov@nginx.com
84*384Szelenkov@nginx.com while (nxt_rbtree_is_there_successor(&tree, node)) {
85*384Szelenkov@nginx.com
86*384Szelenkov@nginx.com item = (nxt_rbtree_test_t *) node;
87*384Szelenkov@nginx.com
88*384Szelenkov@nginx.com if (keys[i] != item->key) {
89*384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree test failed: %i: %08XD %08XD",
90*384Szelenkov@nginx.com i, keys[i], item->key);
91*384Szelenkov@nginx.com goto fail;
92*384Szelenkov@nginx.com }
93*384Szelenkov@nginx.com
94*384Szelenkov@nginx.com i++;
95*384Szelenkov@nginx.com node = nxt_rbtree_node_successor(&tree, node);
96*384Szelenkov@nginx.com }
97*384Szelenkov@nginx.com
98*384Szelenkov@nginx.com if (i != n) {
99*384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree test failed: %ui", i);
100*384Szelenkov@nginx.com goto fail;
101*384Szelenkov@nginx.com }
102*384Szelenkov@nginx.com
103*384Szelenkov@nginx.com for (i = 0; i < n; i++) {
104*384Szelenkov@nginx.com nxt_rbtree_delete(&tree, &items[i].node);
105*384Szelenkov@nginx.com nxt_memset(&items[i], 0xA5, sizeof(nxt_rbtree_test_t));
106*384Szelenkov@nginx.com }
107*384Szelenkov@nginx.com
108*384Szelenkov@nginx.com nxt_thread_time_update(thr);
109*384Szelenkov@nginx.com end = nxt_thread_monotonic_time(thr);
110*384Szelenkov@nginx.com
111*384Szelenkov@nginx.com if (!nxt_rbtree_is_empty(&tree)) {
112*384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree test failed: tree is not empty");
113*384Szelenkov@nginx.com goto fail;
114*384Szelenkov@nginx.com }
115*384Szelenkov@nginx.com
116*384Szelenkov@nginx.com /* Check that the sentinel callback was not modified. */
117*384Szelenkov@nginx.com
118*384Szelenkov@nginx.com if (mark != tree.sentinel.right) {
119*384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree sentinel test failed");
120*384Szelenkov@nginx.com goto fail;
121*384Szelenkov@nginx.com }
122*384Szelenkov@nginx.com
123*384Szelenkov@nginx.com nxt_free(keys);
124*384Szelenkov@nginx.com nxt_free(items);
125*384Szelenkov@nginx.com
126*384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree test passed %0.3fs",
127*384Szelenkov@nginx.com (end - start) / 1000000000.0);
128*384Szelenkov@nginx.com
129*384Szelenkov@nginx.com return NXT_OK;
130*384Szelenkov@nginx.com
131*384Szelenkov@nginx.com fail:
132*384Szelenkov@nginx.com
133*384Szelenkov@nginx.com nxt_free(keys);
134*384Szelenkov@nginx.com nxt_free(items);
135*384Szelenkov@nginx.com
136*384Szelenkov@nginx.com return NXT_ERROR;
137*384Szelenkov@nginx.com }
138*384Szelenkov@nginx.com
139*384Szelenkov@nginx.com
140*384Szelenkov@nginx.com static intptr_t
nxt_rbtree_test_comparison(nxt_rbtree_node_t * node1,nxt_rbtree_node_t * node2)141*384Szelenkov@nginx.com nxt_rbtree_test_comparison(nxt_rbtree_node_t *node1,
142*384Szelenkov@nginx.com nxt_rbtree_node_t *node2)
143*384Szelenkov@nginx.com {
144*384Szelenkov@nginx.com nxt_rbtree_test_t *item1, *item2;
145*384Szelenkov@nginx.com
146*384Szelenkov@nginx.com item1 = (nxt_rbtree_test_t *) node1;
147*384Szelenkov@nginx.com item2 = (nxt_rbtree_test_t *) node2;
148*384Szelenkov@nginx.com
149*384Szelenkov@nginx.com return nxt_rbtree_test_compare(item1->key, item2->key);
150*384Szelenkov@nginx.com }
151*384Szelenkov@nginx.com
152*384Szelenkov@nginx.com
153*384Szelenkov@nginx.com /*
154*384Szelenkov@nginx.com * Subtraction cannot be used in these comparison functions because
155*384Szelenkov@nginx.com * the key values are spread uniform in whole 0 .. 2^32 range but are
156*384Szelenkov@nginx.com * not grouped around some value as timeout values are.
157*384Szelenkov@nginx.com */
158*384Szelenkov@nginx.com
159*384Szelenkov@nginx.com static nxt_int_t
nxt_rbtree_test_compare(uint32_t key1,uint32_t key2)160*384Szelenkov@nginx.com nxt_rbtree_test_compare(uint32_t key1, uint32_t key2)
161*384Szelenkov@nginx.com {
162*384Szelenkov@nginx.com if (key1 < key2) {
163*384Szelenkov@nginx.com return -1;
164*384Szelenkov@nginx.com }
165*384Szelenkov@nginx.com
166*384Szelenkov@nginx.com if (key1 == key2) {
167*384Szelenkov@nginx.com return 0;
168*384Szelenkov@nginx.com }
169*384Szelenkov@nginx.com
170*384Szelenkov@nginx.com return 1;
171*384Szelenkov@nginx.com }
172*384Szelenkov@nginx.com
173*384Szelenkov@nginx.com
174*384Szelenkov@nginx.com static int nxt_cdecl
nxt_rbtree_test_sort_cmp(const void * one,const void * two)175*384Szelenkov@nginx.com nxt_rbtree_test_sort_cmp(const void *one, const void *two)
176*384Szelenkov@nginx.com {
177*384Szelenkov@nginx.com const uint32_t *first, *second;
178*384Szelenkov@nginx.com
179*384Szelenkov@nginx.com first = one;
180*384Szelenkov@nginx.com second = two;
181*384Szelenkov@nginx.com
182*384Szelenkov@nginx.com if (*first < *second) {
183*384Szelenkov@nginx.com return -1;
184*384Szelenkov@nginx.com }
185*384Szelenkov@nginx.com
186*384Szelenkov@nginx.com if (*first == *second) {
187*384Szelenkov@nginx.com return 0;
188*384Szelenkov@nginx.com }
189*384Szelenkov@nginx.com
190*384Szelenkov@nginx.com return 1;
191*384Szelenkov@nginx.com }
192*384Szelenkov@nginx.com
193*384Szelenkov@nginx.com
194*384Szelenkov@nginx.com #if (NXT_TEST_RTDTSC)
195*384Szelenkov@nginx.com
196*384Szelenkov@nginx.com #define NXT_RBT_STEP (21 * nxt_pagesize / 10 / sizeof(nxt_rbtree_test_t))
197*384Szelenkov@nginx.com
198*384Szelenkov@nginx.com static nxt_rbtree_t mb_tree;
199*384Szelenkov@nginx.com static nxt_rbtree_test_t *mb_nodes;
200*384Szelenkov@nginx.com
201*384Szelenkov@nginx.com
202*384Szelenkov@nginx.com nxt_int_t
nxt_rbtree_mb_start(nxt_thread_t * thr)203*384Szelenkov@nginx.com nxt_rbtree_mb_start(nxt_thread_t *thr)
204*384Szelenkov@nginx.com {
205*384Szelenkov@nginx.com uint32_t key;
206*384Szelenkov@nginx.com uint64_t start, end;
207*384Szelenkov@nginx.com nxt_uint_t i, n;
208*384Szelenkov@nginx.com
209*384Szelenkov@nginx.com n = NXT_RBT_STEP;
210*384Szelenkov@nginx.com
211*384Szelenkov@nginx.com mb_nodes = nxt_malloc(NXT_RBT_NODES * n * sizeof(nxt_rbtree_test_t));
212*384Szelenkov@nginx.com if (mb_nodes == NULL) {
213*384Szelenkov@nginx.com return NXT_ERROR;
214*384Szelenkov@nginx.com }
215*384Szelenkov@nginx.com
216*384Szelenkov@nginx.com nxt_rbtree_init(&mb_tree, nxt_rbtree_test_comparison);
217*384Szelenkov@nginx.com
218*384Szelenkov@nginx.com key = 0;
219*384Szelenkov@nginx.com
220*384Szelenkov@nginx.com for (i = 0; i < NXT_RBT_NODES; i++) {
221*384Szelenkov@nginx.com key = nxt_murmur_hash2(&key, sizeof(uint32_t));
222*384Szelenkov@nginx.com mb_nodes[n * i].key = key;
223*384Szelenkov@nginx.com }
224*384Szelenkov@nginx.com
225*384Szelenkov@nginx.com for (i = 0; i < NXT_RBT_NODES - 2; i++) {
226*384Szelenkov@nginx.com nxt_rbtree_insert(&mb_tree, &mb_nodes[n * i].node);
227*384Szelenkov@nginx.com }
228*384Szelenkov@nginx.com
229*384Szelenkov@nginx.com n *= (NXT_RBT_NODES - 2);
230*384Szelenkov@nginx.com
231*384Szelenkov@nginx.com start = nxt_rdtsc();
232*384Szelenkov@nginx.com nxt_rbtree_insert(&mb_tree, &mb_nodes[n].node);
233*384Szelenkov@nginx.com end = nxt_rdtsc();
234*384Szelenkov@nginx.com
235*384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log,
236*384Szelenkov@nginx.com "rbtree mb cached insert: %L cycles", end - start);
237*384Szelenkov@nginx.com
238*384Szelenkov@nginx.com return NXT_OK;
239*384Szelenkov@nginx.com }
240*384Szelenkov@nginx.com
241*384Szelenkov@nginx.com
242*384Szelenkov@nginx.com void
nxt_rbtree_mb_insert(nxt_thread_t * thr)243*384Szelenkov@nginx.com nxt_rbtree_mb_insert(nxt_thread_t *thr)
244*384Szelenkov@nginx.com {
245*384Szelenkov@nginx.com uint64_t start, end;
246*384Szelenkov@nginx.com nxt_uint_t n;
247*384Szelenkov@nginx.com
248*384Szelenkov@nginx.com n = NXT_RBT_STEP;
249*384Szelenkov@nginx.com n *= (NXT_RBT_NODES - 1);
250*384Szelenkov@nginx.com
251*384Szelenkov@nginx.com start = nxt_rdtsc();
252*384Szelenkov@nginx.com nxt_rbtree_insert(&mb_tree, &mb_nodes[n].node);
253*384Szelenkov@nginx.com end = nxt_rdtsc();
254*384Szelenkov@nginx.com
255*384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log,
256*384Szelenkov@nginx.com "rbtree mb insert: %L cycles", end - start);
257*384Szelenkov@nginx.com }
258*384Szelenkov@nginx.com
259*384Szelenkov@nginx.com
260*384Szelenkov@nginx.com void
nxt_rbtree_mb_delete(nxt_thread_t * thr)261*384Szelenkov@nginx.com nxt_rbtree_mb_delete(nxt_thread_t *thr)
262*384Szelenkov@nginx.com {
263*384Szelenkov@nginx.com uint64_t start, end;
264*384Szelenkov@nginx.com nxt_uint_t n;
265*384Szelenkov@nginx.com
266*384Szelenkov@nginx.com n = NXT_RBT_STEP;
267*384Szelenkov@nginx.com n *= (NXT_RBT_NODES / 4 + 1);
268*384Szelenkov@nginx.com
269*384Szelenkov@nginx.com start = nxt_rdtsc();
270*384Szelenkov@nginx.com nxt_rbtree_delete(&mb_tree, &mb_nodes[n].node);
271*384Szelenkov@nginx.com end = nxt_rdtsc();
272*384Szelenkov@nginx.com
273*384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log,
274*384Szelenkov@nginx.com "rbtree mb delete: %L cycles", end - start);
275*384Szelenkov@nginx.com
276*384Szelenkov@nginx.com nxt_free(mb_nodes);
277*384Szelenkov@nginx.com }
278*384Szelenkov@nginx.com
279*384Szelenkov@nginx.com #endif
280