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