@cryptotaxi247 / netdata-1
Code Commits Issues Pulls Sessions CI/CD
master
master
c 1,919 lines 77 KB
Raw
1 // SPDX-License-Identifier: GPL-3.0-or-later
2
3 #include "dictionary-internals.h"
4
5 // ----------------------------------------------------------------------------
6 // unit test
7
8 static void dictionary_unittest_free_char_pp(char **pp, size_t entries) {
9 for(size_t i = 0; i < entries ;i++)
10 freez(pp[i]);
11
12 freez(pp);
13 }
14
15 static char **dictionary_unittest_generate_names(size_t entries) {
16 char **names = mallocz(sizeof(char *) * entries);
17 for(size_t i = 0; i < entries ;i++) {
18 char buf[25 + 1] = "";
19 snprintfz(buf, sizeof(buf), "name.%zu.0123456789.%zu!@#$%%^&*(),./[]{}\\|~`", i, entries / 2 + i);
20 names[i] = strdupz(buf);
21 }
22 return names;
23 }
24
25 static char **dictionary_unittest_generate_values(size_t entries) {
26 char **values = mallocz(sizeof(char *) * entries);
27 for(size_t i = 0; i < entries ;i++) {
28 char buf[25 + 1] = "";
29 snprintfz(buf, sizeof(buf), "value-%zu-0987654321.%zu%%^&*(),. \t !@#$/[]{}\\|~`", i, entries / 2 + i);
30 values[i] = strdupz(buf);
31 }
32 return values;
33 }
34
35 static size_t dictionary_unittest_set_clone(DICTIONARY *dict, char **names, char **values, size_t entries) {
36 size_t errors = 0;
37 for(size_t i = 0; i < entries ;i++) {
38 size_t vallen = strlen(values[i]);
39 char *val = (char *)dictionary_set(dict, names[i], values[i], vallen);
40 if(val == values[i]) { fprintf(stderr, ">>> %s() returns reference to value\n", __FUNCTION__); errors++; }
41 if(!val || memcmp(val, values[i], vallen) != 0) { fprintf(stderr, ">>> %s() returns invalid value\n", __FUNCTION__); errors++; }
42 }
43 return errors;
44 }
45
46 static size_t dictionary_unittest_set_null(DICTIONARY *dict, char **names, char **values, size_t entries) {
47 (void)values;
48 size_t errors = 0;
49 size_t i = 0;
50 for(; i < entries ;i++) {
51 void *val = dictionary_set(dict, names[i], NULL, 0);
52 if(val != NULL) { fprintf(stderr, ">>> %s() returns a non NULL value\n", __FUNCTION__); errors++; }
53 }
54 if(dictionary_entries(dict) != i) {
55 fprintf(stderr, ">>> %s() dictionary items do not match\n", __FUNCTION__);
56 errors++;
57 }
58 return errors;
59 }
60
61
62 static size_t dictionary_unittest_set_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) {
63 size_t errors = 0;
64 for(size_t i = 0; i < entries ;i++) {
65 size_t vallen = strlen(values[i]);
66 char *val = (char *)dictionary_set(dict, names[i], values[i], vallen);
67 if(val != values[i]) { fprintf(stderr, ">>> %s() returns invalid pointer to value\n", __FUNCTION__); errors++; }
68 }
69 return errors;
70 }
71
72 static size_t dictionary_unittest_get_clone(DICTIONARY *dict, char **names, char **values, size_t entries) {
73 size_t errors = 0;
74 for(size_t i = 0; i < entries ;i++) {
75 size_t vallen = strlen(values[i]);
76 char *val = (char *)dictionary_get(dict, names[i]);
77 if(val == values[i]) { fprintf(stderr, ">>> %s() returns reference to value\n", __FUNCTION__); errors++; }
78 if(!val || memcmp(val, values[i], vallen) != 0) { fprintf(stderr, ">>> %s() returns invalid value\n", __FUNCTION__); errors++; }
79 }
80 return errors;
81 }
82
83 static size_t dictionary_unittest_get_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) {
84 size_t errors = 0;
85 for(size_t i = 0; i < entries ;i++) {
86 char *val = (char *)dictionary_get(dict, names[i]);
87 if(val != values[i]) { fprintf(stderr, ">>> %s() returns invalid pointer to value\n", __FUNCTION__); errors++; }
88 }
89 return errors;
90 }
91
92 static size_t dictionary_unittest_get_nonexisting(DICTIONARY *dict, char **names, char **values, size_t entries) {
93 (void)names;
94 size_t errors = 0;
95 for(size_t i = 0; i < entries ;i++) {
96 char *val = (char *)dictionary_get(dict, values[i]);
97 if(val) { fprintf(stderr, ">>> %s() returns non-existing item\n", __FUNCTION__); errors++; }
98 }
99 return errors;
100 }
101
102 static size_t dictionary_unittest_del_nonexisting(DICTIONARY *dict, char **names, char **values, size_t entries) {
103 (void)names;
104 size_t errors = 0;
105 for(size_t i = 0; i < entries ;i++) {
106 bool ret = dictionary_del(dict, values[i]);
107 if(ret) { fprintf(stderr, ">>> %s() deleted non-existing item\n", __FUNCTION__); errors++; }
108 }
109 return errors;
110 }
111
112 static size_t dictionary_unittest_del_existing(DICTIONARY *dict, char **names, char **values, size_t entries) {
113 (void)values;
114 size_t errors = 0;
115
116 size_t forward_from = 0, forward_to = entries / 3;
117 size_t middle_from = forward_to, middle_to = entries * 2 / 3;
118 size_t backward_from = middle_to, backward_to = entries;
119
120 for(size_t i = forward_from; i < forward_to ;i++) {
121 bool ret = dictionary_del(dict, names[i]);
122 if(!ret) { fprintf(stderr, ">>> %s() didn't delete (forward) existing item\n", __FUNCTION__); errors++; }
123 }
124
125 for(size_t i = middle_to - 1; i >= middle_from ;i--) {
126 bool ret = dictionary_del(dict, names[i]);
127 if(!ret) { fprintf(stderr, ">>> %s() didn't delete (middle) existing item\n", __FUNCTION__); errors++; }
128 }
129
130 for(size_t i = backward_to - 1; i >= backward_from ;i--) {
131 bool ret = dictionary_del(dict, names[i]);
132 if(!ret) { fprintf(stderr, ">>> %s() didn't delete (backward) existing item\n", __FUNCTION__); errors++; }
133 }
134
135 return errors;
136 }
137
138 static size_t dictionary_unittest_reset_clone(DICTIONARY *dict, char **names, char **values, size_t entries) {
139 (void)values;
140 // set the name as value too
141 size_t errors = 0;
142 for(size_t i = 0; i < entries ;i++) {
143 size_t vallen = strlen(names[i]);
144 char *val = (char *)dictionary_set(dict, names[i], names[i], vallen);
145 if(val == names[i]) { fprintf(stderr, ">>> %s() returns reference to value\n", __FUNCTION__); errors++; }
146 if(!val || memcmp(val, names[i], vallen) != 0) { fprintf(stderr, ">>> %s() returns invalid value\n", __FUNCTION__); errors++; }
147 }
148 return errors;
149 }
150
151 static size_t dictionary_unittest_reset_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) {
152 (void)values;
153 // set the name as value too
154 size_t errors = 0;
155 for(size_t i = 0; i < entries ;i++) {
156 size_t vallen = strlen(names[i]);
157 char *val = (char *)dictionary_set(dict, names[i], names[i], vallen);
158 if(val != names[i]) { fprintf(stderr, ">>> %s() returns invalid pointer to value\n", __FUNCTION__); errors++; }
159 if(!val) { fprintf(stderr, ">>> %s() returns invalid value\n", __FUNCTION__); errors++; }
160 }
161 return errors;
162 }
163
164 static size_t dictionary_unittest_reset_dont_overwrite_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) {
165 // set the name as value too
166 size_t errors = 0;
167 for(size_t i = 0; i < entries ;i++) {
168 size_t vallen = strlen(names[i]);
169 char *val = (char *)dictionary_set(dict, names[i], names[i], vallen);
170 if(val != values[i]) { fprintf(stderr, ">>> %s() returns invalid pointer to value\n", __FUNCTION__); errors++; }
171 }
172 return errors;
173 }
174
175 static int dictionary_unittest_walkthrough_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) {
176 return 1;
177 }
178
179 static size_t dictionary_unittest_walkthrough(DICTIONARY *dict, char **names, char **values, size_t entries) {
180 (void)names;
181 (void)values;
182 int sum = dictionary_walkthrough_read(dict, dictionary_unittest_walkthrough_callback, NULL);
183 if(sum < (int)entries) return entries - sum;
184 else return sum - entries;
185 }
186
187 static int dictionary_unittest_walkthrough_delete_this_callback(const DICTIONARY_ITEM *item, void *value __maybe_unused, void *data) {
188 const char *name = dictionary_acquired_item_name((DICTIONARY_ITEM *)item);
189
190 if(!dictionary_del((DICTIONARY *)data, name))
191 return 0;
192
193 return 1;
194 }
195
196 static size_t dictionary_unittest_walkthrough_delete_this(DICTIONARY *dict, char **names, char **values, size_t entries) {
197 (void)names;
198 (void)values;
199 int sum = dictionary_walkthrough_write(dict, dictionary_unittest_walkthrough_delete_this_callback, dict);
200 if(sum < (int)entries) return entries - sum;
201 else return sum - entries;
202 }
203
204 static int dictionary_unittest_walkthrough_stop_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) {
205 return -1;
206 }
207
208 static size_t dictionary_unittest_walkthrough_stop(DICTIONARY *dict, char **names, char **values, size_t entries) {
209 (void)names;
210 (void)values;
211 (void)entries;
212 int sum = dictionary_walkthrough_read(dict, dictionary_unittest_walkthrough_stop_callback, NULL);
213 if(sum != -1) return 1;
214 return 0;
215 }
216
217 static size_t dictionary_unittest_foreach(DICTIONARY *dict, char **names, char **values, size_t entries) {
218 (void)names;
219 (void)values;
220 (void)entries;
221 size_t count = 0;
222 char *item;
223 dfe_start_read(dict, item)
224 count++;
225 dfe_done(item);
226
227 if(count > entries) return count - entries;
228 return entries - count;
229 }
230
231 static size_t dictionary_unittest_foreach_delete_this(DICTIONARY *dict, char **names, char **values, size_t entries) {
232 (void)names;
233 (void)values;
234 (void)entries;
235 size_t count = 0;
236 char *item;
237 dfe_start_write(dict, item)
238 if(dictionary_del(dict, item_dfe.name)) count++;
239 dfe_done(item);
240
241 if(count > entries) return count - entries;
242 return entries - count;
243 }
244
245 static size_t dictionary_unittest_destroy(DICTIONARY *dict, char **names, char **values, size_t entries) {
246 (void)names;
247 (void)values;
248 (void)entries;
249 size_t bytes = dictionary_destroy(dict);
250 fprintf(stderr, " %s() freed %zu bytes,", __FUNCTION__, bytes);
251 return 0;
252 }
253
254 static usec_t dictionary_unittest_run_and_measure_time(DICTIONARY *dict, char *message, char **names, char **values, size_t entries, size_t *errors, size_t (*callback)(DICTIONARY *dict, char **names, char **values, size_t entries)) {
255 fprintf(stderr, "%40s ... ", message);
256
257 usec_t started = now_realtime_usec();
258 size_t errs = callback(dict, names, values, entries);
259 usec_t ended = now_realtime_usec();
260 usec_t dt = ended - started;
261
262 if(callback == dictionary_unittest_destroy) dict = NULL;
263
264 long int found_ok = 0, found_deleted = 0, found_referenced = 0;
265 if(dict) {
266 DICTIONARY_ITEM *item;
267 DOUBLE_LINKED_LIST_FOREACH_FORWARD(dict->items.list, item, prev, next) {
268 if(item->refcount >= 0 && !(item ->flags & ITEM_FLAG_DELETED))
269 found_ok++;
270 else
271 found_deleted++;
272
273 if(item->refcount > 0)
274 found_referenced++;
275 }
276 }
277
278 fprintf(stderr, " %zu errors, %d (found %ld) items in dictionary, %d (found %ld) referenced, %d (found %ld) deleted, %"PRIu64" usec \n",
279 errs, dict?dict->entries:0, found_ok, dict?dict->referenced_items:0, found_referenced, dict?dict->pending_deletion_items:0, found_deleted, dt);
280 *errors += errs;
281 return dt;
282 }
283
284 static void dictionary_unittest_clone(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) {
285 dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, errors, dictionary_unittest_set_clone);
286 dictionary_unittest_run_and_measure_time(dict, "getting entries", names, values, entries, errors, dictionary_unittest_get_clone);
287 dictionary_unittest_run_and_measure_time(dict, "getting non-existing entries", names, values, entries, errors, dictionary_unittest_get_nonexisting);
288 dictionary_unittest_run_and_measure_time(dict, "resetting entries", names, values, entries, errors, dictionary_unittest_reset_clone);
289 dictionary_unittest_run_and_measure_time(dict, "deleting non-existing entries", names, values, entries, errors, dictionary_unittest_del_nonexisting);
290 dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, errors, dictionary_unittest_foreach);
291 dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback", names, values, entries, errors, dictionary_unittest_walkthrough);
292 dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback stop", names, values, entries, errors, dictionary_unittest_walkthrough_stop);
293 dictionary_unittest_run_and_measure_time(dict, "deleting existing entries", names, values, entries, errors, dictionary_unittest_del_existing);
294 dictionary_unittest_run_and_measure_time(dict, "walking through empty", names, values, 0, errors, dictionary_unittest_walkthrough);
295 dictionary_unittest_run_and_measure_time(dict, "traverse foreach empty", names, values, 0, errors, dictionary_unittest_foreach);
296 dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, errors, dictionary_unittest_destroy);
297 }
298
299 static void dictionary_unittest_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) {
300 dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, errors, dictionary_unittest_set_nonclone);
301 dictionary_unittest_run_and_measure_time(dict, "getting entries", names, values, entries, errors, dictionary_unittest_get_nonclone);
302 dictionary_unittest_run_and_measure_time(dict, "getting non-existing entries", names, values, entries, errors, dictionary_unittest_get_nonexisting);
303 dictionary_unittest_run_and_measure_time(dict, "resetting entries", names, values, entries, errors, dictionary_unittest_reset_nonclone);
304 dictionary_unittest_run_and_measure_time(dict, "deleting non-existing entries", names, values, entries, errors, dictionary_unittest_del_nonexisting);
305 dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, errors, dictionary_unittest_foreach);
306 dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback", names, values, entries, errors, dictionary_unittest_walkthrough);
307 dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback stop", names, values, entries, errors, dictionary_unittest_walkthrough_stop);
308 dictionary_unittest_run_and_measure_time(dict, "deleting existing entries", names, values, entries, errors, dictionary_unittest_del_existing);
309 dictionary_unittest_run_and_measure_time(dict, "walking through empty", names, values, 0, errors, dictionary_unittest_walkthrough);
310 dictionary_unittest_run_and_measure_time(dict, "traverse foreach empty", names, values, 0, errors, dictionary_unittest_foreach);
311 dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, errors, dictionary_unittest_destroy);
312 }
313
314 struct dictionary_unittest_sorting {
315 const char *old_name;
316 const char *old_value;
317 size_t count;
318 };
319
320 static int dictionary_unittest_sorting_callback(const DICTIONARY_ITEM *item, void *value, void *data) {
321 const char *name = dictionary_acquired_item_name((DICTIONARY_ITEM *)item);
322 struct dictionary_unittest_sorting *t = (struct dictionary_unittest_sorting *)data;
323 const char *v = (const char *)value;
324
325 int ret = 0;
326 if(t->old_name && strcmp(t->old_name, name) > 0) {
327 fprintf(stderr, "name '%s' should be after '%s'\n", t->old_name, name);
328 ret = 1;
329 }
330 t->count++;
331 t->old_name = name;
332 t->old_value = v;
333
334 return ret;
335 }
336
337 static size_t dictionary_unittest_sorted_walkthrough(DICTIONARY *dict, char **names, char **values, size_t entries) {
338 (void)names;
339 (void)values;
340 struct dictionary_unittest_sorting tmp = { .old_name = NULL, .old_value = NULL, .count = 0 };
341 size_t errors;
342 errors = dictionary_sorted_walkthrough_read(dict, dictionary_unittest_sorting_callback, &tmp);
343
344 if(tmp.count != entries) {
345 fprintf(stderr, "Expected %zu entries, counted %zu\n", entries, tmp.count);
346 errors++;
347 }
348 return errors;
349 }
350
351 static void dictionary_unittest_sorting(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) {
352 dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, errors, dictionary_unittest_set_clone);
353 dictionary_unittest_run_and_measure_time(dict, "sorted walkthrough", names, values, entries, errors, dictionary_unittest_sorted_walkthrough);
354 }
355
356 static void dictionary_unittest_null_dfe(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) {
357 dictionary_unittest_run_and_measure_time(dict, "adding null value entries", names, values, entries, errors, dictionary_unittest_set_null);
358 dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, errors, dictionary_unittest_foreach);
359 }
360
361
362 static int unittest_check_dictionary_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) {
363 return 1;
364 }
365
366 static size_t unittest_check_dictionary(const char *label, DICTIONARY *dict, size_t traversable, size_t active_items, size_t deleted_items, size_t referenced_items, size_t pending_deletion) {
367 size_t errors = 0;
368
369 size_t ll = 0;
370 void *t;
371 dfe_start_read(dict, t)
372 ll++;
373 dfe_done(t);
374
375 fprintf(stderr, "DICT %-20s: dictionary foreach entries %zu, expected %zu...\t\t\t\t\t",
376 label, ll, traversable);
377 if(ll != traversable) {
378 fprintf(stderr, "FAILED\n");
379 errors++;
380 }
381 else
382 fprintf(stderr, "OK\n");
383
384 ll = dictionary_walkthrough_read(dict, unittest_check_dictionary_callback, NULL);
385 fprintf(stderr, "DICT %-20s: dictionary walkthrough entries %zu, expected %zu...\t\t\t\t",
386 label, ll, traversable);
387 if(ll != traversable) {
388 fprintf(stderr, "FAILED\n");
389 errors++;
390 }
391 else
392 fprintf(stderr, "OK\n");
393
394 ll = dictionary_sorted_walkthrough_read(dict, unittest_check_dictionary_callback, NULL);
395 fprintf(stderr, "DICT %-20s: dictionary sorted walkthrough entries %zu, expected %zu...\t\t\t",
396 label, ll, traversable);
397 if(ll != traversable) {
398 fprintf(stderr, "FAILED\n");
399 errors++;
400 }
401 else
402 fprintf(stderr, "OK\n");
403
404 DICTIONARY_ITEM *item;
405 size_t active = 0, deleted = 0, referenced = 0, pending = 0;
406 for(item = dict->items.list; item; item = item->next) {
407 if(!(item->flags & ITEM_FLAG_DELETED) && !(item->shared->flags & ITEM_FLAG_DELETED))
408 active++;
409 else {
410 deleted++;
411
412 if(item->refcount == 0)
413 pending++;
414 }
415
416 if(item->refcount > 0)
417 referenced++;
418 }
419
420 fprintf(stderr, "DICT %-20s: dictionary active items reported %d, counted %zu, expected %zu...\t\t\t",
421 label, dict->entries, active, active_items);
422 if(active != active_items || active != (size_t)dict->entries) {
423 fprintf(stderr, "FAILED\n");
424 errors++;
425 }
426 else
427 fprintf(stderr, "OK\n");
428
429 fprintf(stderr, "DICT %-20s: dictionary deleted items counted %zu, expected %zu...\t\t\t\t",
430 label, deleted, deleted_items);
431 if(deleted != deleted_items) {
432 fprintf(stderr, "FAILED\n");
433 errors++;
434 }
435 else
436 fprintf(stderr, "OK\n");
437
438 fprintf(stderr, "DICT %-20s: dictionary referenced items reported %d, counted %zu, expected %zu...\t\t",
439 label, dict->referenced_items, referenced, referenced_items);
440 if(referenced != referenced_items || dict->referenced_items != (long int)referenced) {
441 fprintf(stderr, "FAILED\n");
442 errors++;
443 }
444 else
445 fprintf(stderr, "OK\n");
446
447 fprintf(stderr, "DICT %-20s: dictionary pending deletion items reported %d, counted %zu, expected %zu...\t",
448 label, dict->pending_deletion_items, pending, pending_deletion);
449 if(pending != pending_deletion || pending != (size_t)dict->pending_deletion_items) {
450 fprintf(stderr, "FAILED\n");
451 errors++;
452 }
453 else
454 fprintf(stderr, "OK\n");
455
456 return errors;
457 }
458
459 static int check_item_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value, void *data) {
460 return value == data;
461 }
462
463 static size_t unittest_check_item(const char *label, DICTIONARY *dict,
464 DICTIONARY_ITEM *item, const char *name, const char *value, int refcount,
465 ITEM_FLAGS deleted_flags, bool searchable, bool browsable, bool linked) {
466 size_t errors = 0;
467
468 fprintf(stderr, "ITEM %-20s: name is '%s', expected '%s'...\t\t\t\t\t\t", label, item_get_name(item), name);
469 if(strcmp(item_get_name(item), name) != 0) {
470 fprintf(stderr, "FAILED\n");
471 errors++;
472 }
473 else
474 fprintf(stderr, "OK\n");
475
476 fprintf(stderr, "ITEM %-20s: value is '%s', expected '%s'...\t\t\t\t\t", label, (const char *)item->shared->value, value);
477 if(strcmp((const char *)item->shared->value, value) != 0) {
478 fprintf(stderr, "FAILED\n");
479 errors++;
480 }
481 else
482 fprintf(stderr, "OK\n");
483
484 fprintf(stderr, "ITEM %-20s: refcount is %d, expected %d...\t\t\t\t\t\t\t", label, item->refcount, refcount);
485 if (item->refcount != refcount) {
486 fprintf(stderr, "FAILED\n");
487 errors++;
488 }
489 else
490 fprintf(stderr, "OK\n");
491
492 fprintf(stderr, "ITEM %-20s: deleted flag is %s, expected %s...\t\t\t\t\t", label,
493 (item->flags & ITEM_FLAG_DELETED || item->shared->flags & ITEM_FLAG_DELETED)?"true":"false",
494 (deleted_flags & ITEM_FLAG_DELETED)?"true":"false");
495
496 if ((item->flags & ITEM_FLAG_DELETED || item->shared->flags & ITEM_FLAG_DELETED) != (deleted_flags & ITEM_FLAG_DELETED)) {
497 fprintf(stderr, "FAILED\n");
498 errors++;
499 }
500 else
501 fprintf(stderr, "OK\n");
502
503 void *v = dictionary_get(dict, name);
504 bool found = v == item->shared->value;
505 fprintf(stderr, "ITEM %-20s: searchable %5s, expected %5s...\t\t\t\t\t\t", label,
506 found?"true":"false", searchable?"true":"false");
507 if(found != searchable) {
508 fprintf(stderr, "FAILED\n");
509 errors++;
510 }
511 else
512 fprintf(stderr, "OK\n");
513
514 found = false;
515 void *t;
516 dfe_start_read(dict, t) {
517 if(t == item->shared->value) found = true;
518 }
519 dfe_done(t);
520
521 fprintf(stderr, "ITEM %-20s: dfe browsable %5s, expected %5s...\t\t\t\t\t", label,
522 found?"true":"false", browsable?"true":"false");
523 if(found != browsable) {
524 fprintf(stderr, "FAILED\n");
525 errors++;
526 }
527 else
528 fprintf(stderr, "OK\n");
529
530 found = dictionary_walkthrough_read(dict, check_item_callback, item->shared->value);
531 fprintf(stderr, "ITEM %-20s: walkthrough browsable %5s, expected %5s...\t\t\t\t", label,
532 found?"true":"false", browsable?"true":"false");
533 if(found != browsable) {
534 fprintf(stderr, "FAILED\n");
535 errors++;
536 }
537 else
538 fprintf(stderr, "OK\n");
539
540 found = dictionary_sorted_walkthrough_read(dict, check_item_callback, item->shared->value);
541 fprintf(stderr, "ITEM %-20s: sorted walkthrough browsable %5s, expected %5s...\t\t\t", label,
542 found?"true":"false", browsable?"true":"false");
543 if(found != browsable) {
544 fprintf(stderr, "FAILED\n");
545 errors++;
546 }
547 else
548 fprintf(stderr, "OK\n");
549
550 found = false;
551 DICTIONARY_ITEM *n;
552 for(n = dict->items.list; n ;n = n->next)
553 if(n == item) found = true;
554
555 fprintf(stderr, "ITEM %-20s: linked %5s, expected %5s...\t\t\t\t\t\t", label,
556 found?"true":"false", linked?"true":"false");
557 if(found != linked) {
558 fprintf(stderr, "FAILED\n");
559 errors++;
560 }
561 else
562 fprintf(stderr, "OK\n");
563
564 return errors;
565 }
566
567 struct thread_unittest {
568 int join;
569 DICTIONARY *dict;
570 int dups;
571
572 ND_THREAD *thread;
573 struct dictionary_stats stats;
574 };
575
576 static void unittest_dict_thread(void *arg) {
577 struct thread_unittest *tu = arg;
578 for(; 1 ;) {
579 if(__atomic_load_n(&tu->join, __ATOMIC_RELAXED))
580 break;
581
582 DICT_ITEM_CONST DICTIONARY_ITEM *item =
583 dictionary_set_and_acquire_item_advanced(tu->dict, "dict thread checking 1234567890",
584 -1, NULL, 0, NULL);
585 tu->stats.ops.inserts++;
586
587 dictionary_get(tu->dict, dictionary_acquired_item_name(item));
588 tu->stats.ops.searches++;
589
590 void *t1;
591 dfe_start_write(tu->dict, t1) {
592
593 // this should delete the referenced item
594 dictionary_del(tu->dict, t1_dfe.name);
595 tu->stats.ops.deletes++;
596
597 void *t2;
598 dfe_start_write(tu->dict, t2) {
599 // this should add another
600 dictionary_set(tu->dict, t2_dfe.name, NULL, 0);
601 tu->stats.ops.inserts++;
602
603 dictionary_get(tu->dict, dictionary_acquired_item_name(item));
604 tu->stats.ops.searches++;
605
606 // and this should delete it again
607 dictionary_del(tu->dict, t2_dfe.name);
608 tu->stats.ops.deletes++;
609 }
610 dfe_done(t2);
611 tu->stats.ops.traversals++;
612
613 // this should fail to add it
614 dictionary_set(tu->dict, t1_dfe.name, NULL, 0);
615 tu->stats.ops.inserts++;
616
617 dictionary_del(tu->dict, t1_dfe.name);
618 tu->stats.ops.deletes++;
619 }
620 dfe_done(t1);
621 tu->stats.ops.traversals++;
622
623 for(int i = 0; i < tu->dups ; i++) {
624 dictionary_acquired_item_dup(tu->dict, item);
625 dictionary_get(tu->dict, dictionary_acquired_item_name(item));
626 tu->stats.ops.searches++;
627 }
628
629 for(int i = 0; i < tu->dups ; i++) {
630 dictionary_acquired_item_release(tu->dict, item);
631 dictionary_del(tu->dict, dictionary_acquired_item_name(item));
632 tu->stats.ops.deletes++;
633 }
634
635 dictionary_acquired_item_release(tu->dict, item);
636 dictionary_del(tu->dict, "dict thread checking 1234567890");
637 tu->stats.ops.deletes++;
638
639 // test concurrent deletions and flushes
640 {
641 if(gettid_cached() % 2) {
642 char buf [256 + 1];
643
644 for (int i = 0; i < 1000; i++) {
645 snprintfz(buf, sizeof(buf), "del/flush test %d", i);
646 dictionary_set(tu->dict, buf, NULL, 0);
647 tu->stats.ops.inserts++;
648 }
649
650 for (int i = 0; i < 1000; i++) {
651 snprintfz(buf, sizeof(buf), "del/flush test %d", i);
652 dictionary_del(tu->dict, buf);
653 tu->stats.ops.deletes++;
654 }
655 }
656 else {
657 for (int i = 0; i < 10; i++) {
658 dictionary_flush(tu->dict);
659 tu->stats.ops.flushes++;
660 }
661 }
662 }
663 }
664 }
665
666 static int dictionary_unittest_threads() {
667 time_t seconds_to_run = 5;
668 enum { DICTIONARY_UNITTEST_THREADS = 2 };
669
670 struct thread_unittest tu[DICTIONARY_UNITTEST_THREADS];
671 memset(tu, 0, sizeof(struct thread_unittest) * DICTIONARY_UNITTEST_THREADS);
672
673 fprintf(
674 stderr,
675 "\nChecking dictionary concurrency with %d threads for %lld seconds...\n",
676 DICTIONARY_UNITTEST_THREADS,
677 (long long)seconds_to_run);
678
679 // threads testing of dictionary
680 struct dictionary_stats stats = {};
681 tu[0].join = 0;
682 tu[0].dups = 1;
683 tu[0].dict = dictionary_create_advanced(DICT_OPTION_DONT_OVERWRITE_VALUE, &stats, 0);
684
685 for (int i = 0; i < DICTIONARY_UNITTEST_THREADS; i++) {
686 if(i)
687 tu[i] = tu[0];
688
689 char buf[100 + 1];
690 snprintf(buf, 100, "dict%d", i);
691 tu[i].thread = nd_thread_create(buf, NETDATA_THREAD_OPTION_DONT_LOG, unittest_dict_thread, &tu[i]);
692 }
693
694 sleep_usec(seconds_to_run * USEC_PER_SEC);
695
696 for (int i = 0; i < DICTIONARY_UNITTEST_THREADS; i++) {
697 __atomic_store_n(&tu[i].join, 1, __ATOMIC_RELAXED);
698
699 nd_thread_join(tu[i].thread);
700
701 if(i) {
702 tu[0].stats.ops.inserts += tu[i].stats.ops.inserts;
703 tu[0].stats.ops.deletes += tu[i].stats.ops.deletes;
704 tu[0].stats.ops.searches += tu[i].stats.ops.searches;
705 tu[0].stats.ops.flushes += tu[i].stats.ops.flushes;
706 tu[0].stats.ops.traversals += tu[i].stats.ops.traversals;
707 }
708 }
709
710 fprintf(stderr,
711 "CALLS : inserts %zu"
712 ", deletes %zu"
713 ", searches %zu"
714 ", traversals %zu"
715 ", flushes %zu"
716 "\n",
717 tu[0].stats.ops.inserts,
718 tu[0].stats.ops.deletes,
719 tu[0].stats.ops.searches,
720 tu[0].stats.ops.traversals,
721 tu[0].stats.ops.flushes
722 );
723
724 #ifdef DICT_WITH_STATS
725 fprintf(stderr,
726 "ACTUAL: inserts %zu"
727 ", deletes %zu"
728 ", searches %zu"
729 ", traversals %zu"
730 ", resets %zu"
731 ", flushes %zu"
732 ", entries %d"
733 ", referenced_items %d"
734 ", pending deletions %d"
735 ", check spins %zu"
736 ", insert spins %zu"
737 ", delete spins %zu"
738 ", search ignores %zu"
739 "\n",
740 stats.ops.inserts,
741 stats.ops.deletes,
742 stats.ops.searches,
743 stats.ops.traversals,
744 stats.ops.resets,
745 stats.ops.flushes,
746 tu[0].dict->entries,
747 tu[0].dict->referenced_items,
748 tu[0].dict->pending_deletion_items,
749 stats.spin_locks.use_spins,
750 stats.spin_locks.insert_spins,
751 stats.spin_locks.delete_spins,
752 stats.spin_locks.search_spins
753 );
754 #endif
755
756 dictionary_destroy(tu[0].dict);
757 return 0;
758 }
759
760 struct thread_view_unittest {
761 int join;
762 DICTIONARY *master;
763 DICTIONARY *view;
764 DICTIONARY_ITEM *item_master;
765 int dups;
766 };
767
768 static void unittest_dict_master_thread(void *arg) {
769 struct thread_view_unittest *tv = arg;
770
771 DICTIONARY_ITEM *item = NULL;
772 int loops = 0;
773 while(!__atomic_load_n(&tv->join, __ATOMIC_RELAXED)) {
774
775 if(!item)
776 item = dictionary_set_and_acquire_item(tv->master, "ITEM1", "123", strlen("123"));
777
778 if(__atomic_load_n(&tv->item_master, __ATOMIC_RELAXED) != NULL) {
779 dictionary_acquired_item_release(tv->master, item);
780 dictionary_del(tv->master, "ITEM1");
781 item = NULL;
782 loops++;
783 continue;
784 }
785
786 dictionary_acquired_item_dup(tv->master, item); // for the view thread
787 __atomic_store_n(&tv->item_master, item, __ATOMIC_RELAXED);
788 dictionary_del(tv->master, "ITEM1");
789
790
791 for(int i = 0; i < tv->dups + loops ; i++) {
792 dictionary_acquired_item_dup(tv->master, item);
793 }
794
795 for(int i = 0; i < tv->dups + loops ; i++) {
796 dictionary_acquired_item_release(tv->master, item);
797 }
798
799 dictionary_acquired_item_release(tv->master, item);
800
801 item = NULL;
802 loops = 0;
803 }
804 }
805
806 static void unittest_dict_view_thread(void *arg) {
807 struct thread_view_unittest *tv = arg;
808
809 DICTIONARY_ITEM *m_item = NULL;
810
811 while(!__atomic_load_n(&tv->join, __ATOMIC_RELAXED)) {
812 if(!(m_item = __atomic_load_n(&tv->item_master, __ATOMIC_RELAXED)))
813 continue;
814
815 DICTIONARY_ITEM *v_item = dictionary_view_set_and_acquire_item(tv->view, "ITEM2", m_item);
816 dictionary_acquired_item_release(tv->master, m_item);
817 __atomic_store_n(&tv->item_master, NULL, __ATOMIC_RELAXED);
818
819 for(int i = 0; i < tv->dups ; i++) {
820 dictionary_acquired_item_dup(tv->view, v_item);
821 }
822
823 for(int i = 0; i < tv->dups ; i++) {
824 dictionary_acquired_item_release(tv->view, v_item);
825 }
826
827 dictionary_del(tv->view, "ITEM2");
828
829 while(!__atomic_load_n(&tv->join, __ATOMIC_RELAXED) && !(m_item = __atomic_load_n(&tv->item_master, __ATOMIC_RELAXED))) {
830 dictionary_acquired_item_dup(tv->view, v_item);
831 dictionary_acquired_item_release(tv->view, v_item);
832 }
833
834 dictionary_acquired_item_release(tv->view, v_item);
835 }
836 }
837
838 static struct dictionary_stats stats_master = { 0 };
839 static struct dictionary_stats stats_view = { 0 };
840
841 static int dictionary_unittest_view_threads() {
842 struct thread_view_unittest tv = {
843 .join = 0,
844 .master = NULL,
845 .view = NULL,
846 .item_master = NULL,
847 .dups = 1,
848 };
849
850 // threads testing of dictionary
851 tv.master = dictionary_create_advanced(DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE, &stats_master, 0);
852 tv.view = dictionary_create_view(tv.master);
853 tv.view->stats = &stats_view;
854
855 time_t seconds_to_run = 5;
856 fprintf(
857 stderr,
858 "\nChecking dictionary concurrency with 1 master and 1 view threads for %lld seconds...\n",
859 (long long)seconds_to_run);
860
861 ND_THREAD *master_thread, *view_thread;
862 tv.join = 0;
863
864 master_thread = nd_thread_create("master", NETDATA_THREAD_OPTION_DONT_LOG, unittest_dict_master_thread, &tv);
865
866 view_thread = nd_thread_create("view", NETDATA_THREAD_OPTION_DONT_LOG, unittest_dict_view_thread, &tv);
867
868 sleep_usec(seconds_to_run * USEC_PER_SEC);
869
870 __atomic_store_n(&tv.join, 1, __ATOMIC_RELAXED);
871 nd_thread_join(view_thread);
872 nd_thread_join(master_thread);
873
874 #ifdef DICT_WITH_STATS
875 fprintf(stderr,
876 "MASTER: inserts %zu"
877 ", deletes %zu"
878 ", searches %zu"
879 ", resets %zu"
880 ", entries %d"
881 ", referenced_items %d"
882 ", pending deletions %d"
883 ", check spins %zu"
884 ", insert spins %zu"
885 ", delete spins %zu"
886 ", search ignores %zu"
887 "\n",
888 stats_master.ops.inserts,
889 stats_master.ops.deletes,
890 stats_master.ops.searches,
891 stats_master.ops.resets,
892 tv.master->entries,
893 tv.master->referenced_items,
894 tv.master->pending_deletion_items,
895 stats_master.spin_locks.use_spins,
896 stats_master.spin_locks.insert_spins,
897 stats_master.spin_locks.delete_spins,
898 stats_master.spin_locks.search_spins
899 );
900 fprintf(stderr,
901 "VIEW : inserts %zu"
902 ", deletes %zu"
903 ", searches %zu"
904 ", resets %zu"
905 ", entries %d"
906 ", referenced_items %d"
907 ", pending deletions %d"
908 ", check spins %zu"
909 ", insert spins %zu"
910 ", delete spins %zu"
911 ", search ignores %zu"
912 "\n",
913 stats_view.ops.inserts,
914 stats_view.ops.deletes,
915 stats_view.ops.searches,
916 stats_view.ops.resets,
917 tv.view->entries,
918 tv.view->referenced_items,
919 tv.view->pending_deletion_items,
920 stats_view.spin_locks.use_spins,
921 stats_view.spin_locks.insert_spins,
922 stats_view.spin_locks.delete_spins,
923 stats_view.spin_locks.search_spins
924 );
925 #endif
926
927 dictionary_destroy(tv.master);
928 dictionary_destroy(tv.view);
929
930 return 0;
931 }
932
933 size_t dictionary_unittest_views(void) {
934 size_t errors = 0;
935 struct dictionary_stats stats = {};
936 DICTIONARY *master = dictionary_create_advanced(DICT_OPTION_NONE, &stats, 0);
937 DICTIONARY *view = dictionary_create_view(master);
938 DICTIONARY_ITEM *master_item2 = NULL;
939 DICTIONARY_ITEM *view_item2 = NULL;
940 DICTIONARY_ITEM *lookup = NULL;
941
942 fprintf(stderr, "\n\nChecking dictionary views...\n");
943
944 // Add an item to both master and view, then remove the view first and the master second
945 fprintf(stderr, "\nPASS 1: Adding 1 item to master:\n");
946 DICTIONARY_ITEM *item1_on_master = dictionary_set_and_acquire_item(master, "KEY 1", "VALUE1", strlen("VALUE1") + 1);
947 errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0);
948 errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true);
949
950 fprintf(stderr, "\nPASS 1: Adding master item to view:\n");
951 DICTIONARY_ITEM *item1_on_view = dictionary_view_set_and_acquire_item(view, "KEY 1 ON VIEW", item1_on_master);
952 errors += unittest_check_dictionary("view", view, 1, 1, 0, 1, 0);
953 errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true);
954
955 fprintf(stderr, "\nPASS 1: Deleting view item:\n");
956 dictionary_del(view, "KEY 1 ON VIEW");
957 errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0);
958 errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0);
959 errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true);
960 errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true);
961
962 fprintf(stderr, "\nPASS 1: Releasing the deleted view item:\n");
963 dictionary_acquired_item_release(view, item1_on_view);
964 errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0);
965 errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1);
966 errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true);
967
968 fprintf(stderr, "\nPASS 1: Releasing the acquired master item:\n");
969 dictionary_acquired_item_release(master, item1_on_master);
970 errors += unittest_check_dictionary("master", master, 1, 1, 0, 0, 0);
971 errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1);
972 errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 0, ITEM_FLAG_NONE, true, true, true);
973
974 fprintf(stderr, "\nPASS 1: Deleting the released master item:\n");
975 dictionary_del(master, "KEY 1");
976 errors += unittest_check_dictionary("master", master, 0, 0, 0, 0, 0);
977 errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1);
978
979 // The other way now:
980 // Add an item to both master and view, then remove the master first and verify it is deleted on the view also
981 fprintf(stderr, "\nPASS 2: Adding 1 item to master:\n");
982 item1_on_master = dictionary_set_and_acquire_item(master, "KEY 1", "VALUE1", strlen("VALUE1") + 1);
983 errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0);
984 errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true);
985
986 fprintf(stderr, "\nPASS 2: Adding master item to view:\n");
987 item1_on_view = dictionary_view_set_and_acquire_item(view, "KEY 1 ON VIEW", item1_on_master);
988 errors += unittest_check_dictionary("view", view, 1, 1, 0, 1, 0);
989 errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true);
990
991 fprintf(stderr, "\nPASS 2: Deleting master item:\n");
992 dictionary_del(master, "KEY 1");
993 garbage_collect_pending_deletes(view);
994 errors += unittest_check_dictionary("master", master, 0, 0, 1, 1, 0);
995 errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0);
996 errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true);
997 errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true);
998
999 fprintf(stderr, "\nPASS 2: Releasing the acquired master item:\n");
1000 dictionary_acquired_item_release(master, item1_on_master);
1001 errors += unittest_check_dictionary("master", master, 0, 0, 1, 0, 1);
1002 errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0);
1003 errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true);
1004
1005 fprintf(stderr, "\nPASS 2: Releasing the deleted view item:\n");
1006 dictionary_acquired_item_release(view, item1_on_view);
1007 errors += unittest_check_dictionary("master", master, 0, 0, 1, 0, 1);
1008 errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1);
1009
1010 fprintf(stderr, "\nPASS 3: Replacing a stale view item after master deletion:\n");
1011 item1_on_master = dictionary_set_and_acquire_item(master, "KEY 1", "VALUE1", strlen("VALUE1") + 1);
1012 item1_on_view = dictionary_view_set_and_acquire_item(view, "KEY 1 ON VIEW", item1_on_master);
1013 dictionary_acquired_item_release(view, item1_on_view);
1014 dictionary_del(master, "KEY 1");
1015
1016 // Suppress the preflight garbage collection once so view_set() exercises
1017 // the stale-entry cleanup path inside dict_item_add_or_reset_value_and_acquire().
1018 __atomic_store_n(&view->last_gc_run_us, now_realtime_usec(), __ATOMIC_RELAXED);
1019
1020 master_item2 = dictionary_set_and_acquire_item(master, "KEY 1", "VALUE2", strlen("VALUE2") + 1);
1021 view_item2 = dictionary_view_set_and_acquire_item(view, "KEY 1 ON VIEW", master_item2);
1022
1023 if(!view_item2) {
1024 fprintf(stderr, "View replacement returned NULL\n");
1025 errors++;
1026 }
1027 else if(item_flag_check(view_item2, ITEM_FLAG_DELETED) || view_item2->shared != master_item2->shared) {
1028 fprintf(stderr, "View replacement returned stale/deleted item\n");
1029 dictionary_acquired_item_release(view, view_item2);
1030 errors++;
1031 }
1032 else
1033 dictionary_acquired_item_release(view, view_item2);
1034
1035 lookup = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(view, "KEY 1 ON VIEW");
1036 if(!lookup || item_flag_check(lookup, ITEM_FLAG_DELETED) || lookup->shared != master_item2->shared) {
1037 fprintf(stderr, "View lookup did not resolve to the replacement item\n");
1038 errors++;
1039 }
1040 if(lookup)
1041 dictionary_acquired_item_release(view, lookup);
1042
1043 dictionary_acquired_item_release(master, master_item2);
1044 dictionary_acquired_item_release(master, item1_on_master);
1045
1046 dictionary_destroy(master);
1047 dictionary_destroy(view);
1048 return errors;
1049 }
1050
1051 // ----------------------------------------------------------------------------
1052 // Test: dictionary_destroy() TOCTOU race
1053 //
1054 // Stress test for the race where dictionary_destroy() could start force-freeing
1055 // a dictionary while concurrent get/set/traversal operations were still able
1056 // to enter through stale pre-lock destroyed-state checks.
1057 //
1058 // The test runs the racy workload in a forked child process so that a crash
1059 // is detected as a child signal instead of bringing down the test harness.
1060
1061 #ifndef OS_WINDOWS
1062 #include <sys/wait.h>
1063 #endif
1064
1065 #ifndef OS_WINDOWS
1066
1067 struct dict_destroy_race_data {
1068 DICTIONARY *dict;
1069 int ready; // atomic: worker signals it is looping
1070 int stop; // atomic: main tells worker to stop
1071 };
1072
1073 // Worker that continuously acquires and releases an item.
1074 // Keep the reference briefly so destroy() can observe an in-flight access in
1075 // the post-index-teardown recheck without forcing the old "already referenced"
1076 // path up front.
1077 static void dict_destroy_race_getter_thread(void *arg) {
1078 struct dict_destroy_race_data *d = arg;
1079
1080 __atomic_store_n(&d->ready, 1, __ATOMIC_RELEASE);
1081
1082 while(!__atomic_load_n(&d->stop, __ATOMIC_RELAXED)) {
1083 DICTIONARY_ITEM *item = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(d->dict, "key");
1084 if(item) {
1085 const char *val = dictionary_acquired_item_value(item);
1086 if(val) {
1087 volatile char c __attribute__((unused)) = val[0];
1088 }
1089 tinysleep();
1090 dictionary_acquired_item_release(d->dict, item);
1091 }
1092 }
1093 }
1094
1095 // Worker that continuously sets (inserts/updates) items.
1096 static void dict_destroy_race_setter_thread(void *arg) {
1097 struct dict_destroy_race_data *d = arg;
1098
1099 __atomic_store_n(&d->ready, 1, __ATOMIC_RELEASE);
1100
1101 int counter = 0;
1102 while(!__atomic_load_n(&d->stop, __ATOMIC_RELAXED)) {
1103 char key[32], val[32];
1104 // Use unique keys so the test exercises concurrent inserts during
1105 // destruction without racing on value replacement semantics.
1106 snprintfz(key, sizeof(key), "key-%d", counter);
1107 snprintfz(val, sizeof(val), "val-%d", counter);
1108 dictionary_set(d->dict, key, val, strlen(val) + 1);
1109 counter++;
1110 }
1111 }
1112
1113 // Worker that continuously traverses (dfe_start_read / dfe_done).
1114 static void dict_destroy_race_traverser_thread(void *arg) {
1115 struct dict_destroy_race_data *d = arg;
1116
1117 __atomic_store_n(&d->ready, 1, __ATOMIC_RELEASE);
1118
1119 while(!__atomic_load_n(&d->stop, __ATOMIC_RELAXED)) {
1120 void *val;
1121 dfe_start_read(d->dict, val) {
1122 if(val) {
1123 volatile char c __attribute__((unused)) = ((const char *)val)[0];
1124 }
1125 }
1126 dfe_done(val);
1127 }
1128 }
1129
1130 // Run the racy workload in a child process: concurrent get/set/traverse
1131 // while the main thread destroys the dictionary. Without the fix this may
1132 // crash or trip internal consistency checks, depending on timing.
1133 static void dict_destroy_race_child(int iterations) {
1134 for(int i = 0; i < iterations; i++) {
1135 DICTIONARY *dict = dictionary_create(DICT_OPTION_NONE);
1136 dictionary_set(dict, "key", "value", 6);
1137
1138 struct dict_destroy_race_data getter_data = { .dict = dict, .ready = 0, .stop = 0 };
1139 struct dict_destroy_race_data setter_data = { .dict = dict, .ready = 0, .stop = 0 };
1140 struct dict_destroy_race_data traverser_data = { .dict = dict, .ready = 0, .stop = 0 };
1141
1142 ND_THREAD *getter = nd_thread_create(
1143 "race-getter", NETDATA_THREAD_OPTION_DONT_LOG,
1144 dict_destroy_race_getter_thread, &getter_data);
1145
1146 ND_THREAD *setter = nd_thread_create(
1147 "race-setter", NETDATA_THREAD_OPTION_DONT_LOG,
1148 dict_destroy_race_setter_thread, &setter_data);
1149
1150 ND_THREAD *traverser = nd_thread_create(
1151 "race-trav", NETDATA_THREAD_OPTION_DONT_LOG,
1152 dict_destroy_race_traverser_thread, &traverser_data);
1153
1154 if(!getter || !setter || !traverser) {
1155 // Thread creation failed — stop any that did start and clean up.
1156 __atomic_store_n(&getter_data.stop, 1, __ATOMIC_RELEASE);
1157 __atomic_store_n(&setter_data.stop, 1, __ATOMIC_RELEASE);
1158 __atomic_store_n(&traverser_data.stop, 1, __ATOMIC_RELEASE);
1159 if(getter) nd_thread_join(getter);
1160 if(setter) nd_thread_join(setter);
1161 if(traverser) nd_thread_join(traverser);
1162 dictionary_destroy(dict);
1163 cleanup_destroyed_dictionaries(false);
1164 _exit(2);
1165 }
1166
1167 // wait for all workers to be running
1168 while(!__atomic_load_n(&getter_data.ready, __ATOMIC_ACQUIRE) ||
1169 !__atomic_load_n(&setter_data.ready, __ATOMIC_ACQUIRE) ||
1170 !__atomic_load_n(&traverser_data.ready, __ATOMIC_ACQUIRE))
1171 tinysleep();
1172
1173 tinysleep();
1174
1175 // Do not hold a permanent acquired item here: that would force the old
1176 // "already referenced" delayed-destroy path before destroy() reaches
1177 // the new destroyed-flag + index-teardown synchronization. Instead,
1178 // rely on the active workers to create transient in-flight accesses
1179 // while destroy() races with get/set/traversal.
1180 dictionary_destroy(dict);
1181
1182 __atomic_store_n(&getter_data.stop, 1, __ATOMIC_RELEASE);
1183 __atomic_store_n(&setter_data.stop, 1, __ATOMIC_RELEASE);
1184 __atomic_store_n(&traverser_data.stop, 1, __ATOMIC_RELEASE);
1185 nd_thread_join(getter);
1186 nd_thread_join(setter);
1187 nd_thread_join(traverser);
1188
1189 cleanup_destroyed_dictionaries(false);
1190 }
1191 }
1192
1193 static int dictionary_destroy_race_unittest(void) {
1194 const int iterations = nd_is_running_under_ci() ? 10 : 100;
1195
1196 fprintf(stderr,
1197 "\nTesting dictionary_destroy() TOCTOU race (%d iterations in child process)...\n",
1198 iterations);
1199
1200 fflush(stderr);
1201 fflush(stdout);
1202
1203 pid_t pid = fork();
1204 if(pid == 0) {
1205 // child — run the racy workload
1206 dict_destroy_race_child(iterations);
1207 _exit(0);
1208 }
1209
1210 if(pid < 0) {
1211 fprintf(stderr, "dictionary_destroy() TOCTOU race test: fork() failed: %s\n",
1212 strerror(errno));
1213 return 1;
1214 }
1215
1216 // Give the child a generous timeout so a hang doesn't stall the suite.
1217 int timeout_sec = 120;
1218 int status = 0;
1219 bool reaped = false;
1220 for(int elapsed = 0; elapsed < timeout_sec; elapsed++) {
1221 pid_t rc = waitpid(pid, &status, WNOHANG);
1222 if(rc > 0) { reaped = true; break; }
1223 if(rc < 0) {
1224 if(errno == EINTR)
1225 continue;
1226 fprintf(stderr, "dictionary_destroy() TOCTOU race test: waitpid() failed: %s\n",
1227 strerror(errno));
1228 return 1;
1229 }
1230 sleep_usec(USEC_PER_SEC);
1231 }
1232 if(!reaped) {
1233 kill(pid, SIGKILL);
1234 while(waitpid(pid, &status, 0) < 0) {
1235 if(errno != EINTR) {
1236 fprintf(stderr, "dictionary_destroy() TOCTOU race test: waitpid() failed after SIGKILL: %s\n",
1237 strerror(errno));
1238 return 1;
1239 }
1240 }
1241 fprintf(stderr, "dictionary_destroy() TOCTOU race test: FAILED — "
1242 "child hung (killed after %d seconds)\n", timeout_sec);
1243 return 1;
1244 }
1245
1246 if(WIFSIGNALED(status)) {
1247 int sig = WTERMSIG(status);
1248 fprintf(stderr,
1249 "dictionary_destroy() TOCTOU race test: FAILED — "
1250 "child killed by signal %d (%s) — "
1251 "dictionary_destroy() still has a TOCTOU in its destroy/access "
1252 "synchronization path\n",
1253 sig, strsignal(sig));
1254 return 1;
1255 }
1256
1257 if(WIFEXITED(status) && WEXITSTATUS(status) != 0) {
1258 fprintf(stderr,
1259 "dictionary_destroy() TOCTOU race test: FAILED — "
1260 "child exited with status %d\n",
1261 WEXITSTATUS(status));
1262 return 1;
1263 }
1264
1265 fprintf(stderr, "dictionary_destroy() TOCTOU race test: OK\n");
1266 return 0;
1267 }
1268
1269 #else
1270
1271 static int dictionary_destroy_race_unittest(void) {
1272 fprintf(stderr,
1273 "\nTesting dictionary_destroy() TOCTOU race: SKIPPED "
1274 "(fork-based test is unsupported on this platform)\n");
1275 return 0;
1276 }
1277
1278 #endif
1279
1280 bool dictionary_traverse_or_destroy_unittest(void) {
1281 DICTIONARY *dict = dictionary_create(DICT_OPTION_SINGLE_THREADED);
1282 dictionary_set(dict, "KEY 1", "VALUE1", strlen("VALUE1") + 1);
1283 dictionary_set(dict, "KEY 2", "VALUE2", strlen("VALUE2") + 1);
1284 dictionary_set(dict, "KEY 3", "VALUE3", strlen("VALUE3") + 1);
1285
1286 size_t counted = 0;
1287 const char *s;
1288 dfe_start_read(dict, s) {
1289 if(!counted)
1290 dictionary_destroy(dict);
1291
1292 counted++;
1293 }
1294 dfe_done(s);
1295
1296 return counted == 1;
1297 }
1298
1299 /*
1300 * FIXME: a dictionary-related leak is reported when running the address
1301 * sanitizer. Need to investigate if it's introduced by the unit-test itself,
1302 * or the dictionary implementation.
1303 */
1304 // ============================================================================
1305 // Dictionary benchmark harness for before/after concurrency work (for example
1306 // RCU internals). Keep the workloads stable and the output compact.
1307 // ============================================================================
1308
1309 #define DICT_BENCH_MAX_SAMPLES 4096
1310 #define DICT_BENCH_SAMPLE_EVERY 64
1311
1312 typedef enum {
1313 DICT_BENCH_READ_NONE = 0,
1314 DICT_BENCH_READ_TRAVERSAL,
1315 DICT_BENCH_READ_LOOKUP_HOT,
1316 DICT_BENCH_READ_LOOKUP_RANDOM,
1317 } dict_bench_read_mode_t;
1318
1319 typedef enum {
1320 DICT_BENCH_WRITE_NONE = 0,
1321 DICT_BENCH_WRITE_CHURN,
1322 DICT_BENCH_WRITE_UPDATE,
1323 } dict_bench_write_mode_t;
1324
1325 struct dict_bench_config {
1326 const char *workload;
1327 size_t entries;
1328 int readers;
1329 int writers;
1330 time_t seconds_to_run;
1331 dict_bench_read_mode_t read_mode;
1332 dict_bench_write_mode_t write_mode;
1333 };
1334
1335 struct dict_bench_stats {
1336 uint64_t ops;
1337 uint64_t items_seen;
1338 uint64_t latency_total_ut;
1339 size_t latency_samples_used;
1340 uint64_t latency_samples_seen;
1341 usec_t latency_samples[DICT_BENCH_MAX_SAMPLES];
1342 };
1343
1344 struct dict_bench_thread {
1345 int id;
1346 int *join;
1347 DICTIONARY *dict;
1348 const struct dict_bench_config *cfg;
1349 struct dict_bench_stats stats;
1350 bool is_writer;
1351 uint32_t rng_state;
1352 ND_THREAD *thread;
1353 };
1354
1355 struct dict_bench_summary {
1356 uint64_t read_ops;
1357 uint64_t read_items_seen;
1358 uint64_t write_ops;
1359 double read_avg_ut;
1360 double read_p99_ut;
1361 double write_avg_ut;
1362 double write_p99_ut;
1363 };
1364
1365 static int dict_bench_usec_cmp(const void *a, const void *b) {
1366 const usec_t ua = *(const usec_t *)a;
1367 const usec_t ub = *(const usec_t *)b;
1368 return (ua > ub) - (ua < ub);
1369 }
1370
1371 static inline uint32_t dict_bench_rand(uint32_t *state) {
1372 if(!*state) *state = 1;
1373 *state ^= *state << 13;
1374 *state ^= *state >> 17;
1375 *state ^= *state << 5;
1376 return *state;
1377 }
1378
1379 static inline void dict_bench_record_latency(struct dict_bench_stats *stats, usec_t latency_ut, uint32_t *rng) {
1380 stats->latency_total_ut += latency_ut;
1381 stats->latency_samples_seen++;
1382
1383 if(stats->latency_samples_used < DICT_BENCH_MAX_SAMPLES)
1384 stats->latency_samples[stats->latency_samples_used++] = latency_ut;
1385 else {
1386 // reservoir sampling: replace a random slot with probability N/total_seen
1387 uint32_t idx = dict_bench_rand(rng) % stats->latency_samples_seen;
1388 if(idx < DICT_BENCH_MAX_SAMPLES)
1389 stats->latency_samples[idx] = latency_ut;
1390 }
1391 }
1392
1393 static void dict_bench_lookup_key(char *buf, size_t len, size_t key_idx) {
1394 snprintfz(buf, len, "bench-item-%zu", key_idx);
1395 }
1396
1397 static void dict_bench_reader_thread(void *arg) {
1398 struct dict_bench_thread *ctx = arg;
1399 const size_t hot_keys = MIN(ctx->cfg->entries, (size_t)64);
1400
1401 while(!__atomic_load_n(ctx->join, __ATOMIC_RELAXED)) {
1402 usec_t started_ut = 0;
1403 bool sample_latency = ((ctx->stats.ops & (DICT_BENCH_SAMPLE_EVERY - 1)) == 0);
1404
1405 if(sample_latency)
1406 started_ut = now_monotonic_usec();
1407
1408 if(ctx->cfg->read_mode == DICT_BENCH_READ_TRAVERSAL) {
1409 void *v;
1410 dfe_start_read(ctx->dict, v) {
1411 (void)v;
1412 ctx->stats.items_seen++;
1413 }
1414 dfe_done(v);
1415 }
1416 else {
1417 char name[64];
1418 size_t key_idx;
1419
1420 if(ctx->cfg->read_mode == DICT_BENCH_READ_LOOKUP_HOT)
1421 key_idx = dict_bench_rand(&ctx->rng_state) % hot_keys;
1422 else
1423 key_idx = dict_bench_rand(&ctx->rng_state) % ctx->cfg->entries;
1424
1425 dict_bench_lookup_key(name, sizeof(name), key_idx);
1426 (void)dictionary_get(ctx->dict, name);
1427 }
1428
1429 ctx->stats.ops++;
1430
1431 if(sample_latency)
1432 dict_bench_record_latency(&ctx->stats, now_monotonic_usec() - started_ut, &ctx->rng_state);
1433 }
1434 }
1435
1436 static void dict_bench_writer_thread(void *arg) {
1437 struct dict_bench_thread *ctx = arg;
1438 uint64_t counter = 0;
1439
1440 while(!__atomic_load_n(ctx->join, __ATOMIC_RELAXED)) {
1441 usec_t started_ut = 0;
1442 bool sample_latency = ((ctx->stats.ops & (DICT_BENCH_SAMPLE_EVERY - 1)) == 0);
1443
1444 if(sample_latency)
1445 started_ut = now_monotonic_usec();
1446
1447 if(ctx->cfg->write_mode == DICT_BENCH_WRITE_CHURN) {
1448 char buf[64];
1449 snprintfz(buf, sizeof(buf), "writer-key-%d-%"PRIu64, ctx->id, counter);
1450 dictionary_set(ctx->dict, buf, NULL, 0);
1451 dictionary_del(ctx->dict, buf);
1452 }
1453 else {
1454 char buf[64];
1455 size_t key_idx = dict_bench_rand(&ctx->rng_state) % ctx->cfg->entries;
1456 uint64_t value = counter;
1457
1458 dict_bench_lookup_key(buf, sizeof(buf), key_idx);
1459 dictionary_set(ctx->dict, buf, &value, sizeof(value));
1460 }
1461
1462 counter++;
1463 ctx->stats.ops++;
1464
1465 if(sample_latency)
1466 dict_bench_record_latency(&ctx->stats, now_monotonic_usec() - started_ut, &ctx->rng_state);
1467 }
1468 }
1469
1470 static void dict_bench_prepopulate(DICTIONARY *dict, size_t entries) {
1471 char name[64];
1472
1473 for(size_t i = 0; i < entries; i++) {
1474 uint64_t value = i;
1475 dict_bench_lookup_key(name, sizeof(name), i);
1476 dictionary_set(dict, name, &value, sizeof(value));
1477 }
1478 }
1479
1480 static double dict_bench_percentile_ut(usec_t *samples, size_t samples_used, size_t percentile) {
1481 if(!samples_used)
1482 return 0.0;
1483
1484 qsort(samples, samples_used, sizeof(*samples), dict_bench_usec_cmp);
1485
1486 size_t idx = ((samples_used - 1) * percentile) / 100;
1487 return (double)samples[idx];
1488 }
1489
1490 static void dict_bench_aggregate_latency(
1491 struct dict_bench_thread *threads,
1492 int count,
1493 bool writers,
1494 double *avg_ut,
1495 double *p99_ut
1496 ) {
1497 size_t max_samples = (size_t)DICT_BENCH_MAX_SAMPLES * count;
1498 usec_t *samples = callocz(max_samples, sizeof(usec_t));
1499 size_t samples_used = 0;
1500 uint64_t total_latency_ut = 0;
1501 uint64_t total_ops = 0;
1502
1503 for(int i = 0; i < count; i++) {
1504 if(threads[i].is_writer != writers)
1505 continue;
1506
1507 total_latency_ut += threads[i].stats.latency_total_ut;
1508 total_ops += threads[i].stats.latency_samples_seen;
1509
1510 size_t available = max_samples - samples_used;
1511 size_t copy = MIN(available, threads[i].stats.latency_samples_used);
1512 if(copy) {
1513 memcpy(&samples[samples_used], threads[i].stats.latency_samples, copy * sizeof(usec_t));
1514 samples_used += copy;
1515 }
1516 }
1517
1518 *avg_ut = total_ops ? (double)total_latency_ut / (double)total_ops : 0.0;
1519 *p99_ut = dict_bench_percentile_ut(samples, samples_used, 99);
1520 freez(samples);
1521 }
1522
1523 static void dict_bench_run_case(const struct dict_bench_config *cfg) {
1524 int total_threads = cfg->readers + cfg->writers;
1525 int join = 0;
1526 struct dict_bench_thread *threads = callocz(total_threads, sizeof(*threads));
1527 struct dict_bench_summary summary = {0};
1528 DICTIONARY *dict = dictionary_create(DICT_OPTION_NONE);
1529 dict_bench_prepopulate(dict, cfg->entries);
1530
1531 for(int i = 0; i < cfg->readers; i++) {
1532 char tname[32];
1533 threads[i] = (struct dict_bench_thread){
1534 .id = i,
1535 .join = &join,
1536 .dict = dict,
1537 .cfg = cfg,
1538 .is_writer = false,
1539 .rng_state = (uint32_t)(i + 1) * 2654435761U,
1540 };
1541 snprintfz(tname, sizeof(tname), "dbread%d", i);
1542 threads[i].thread = nd_thread_create(tname, NETDATA_THREAD_OPTION_DONT_LOG,
1543 dict_bench_reader_thread, &threads[i]);
1544 }
1545
1546 for(int i = 0; i < cfg->writers; i++) {
1547 int idx = cfg->readers + i;
1548 char tname[32];
1549 threads[idx] = (struct dict_bench_thread){
1550 .id = idx,
1551 .join = &join,
1552 .dict = dict,
1553 .cfg = cfg,
1554 .is_writer = true,
1555 .rng_state = (uint32_t)(idx + 1) * 2246822519U,
1556 };
1557 snprintfz(tname, sizeof(tname), "dbwrite%d", i);
1558 threads[idx].thread = nd_thread_create(tname, NETDATA_THREAD_OPTION_DONT_LOG,
1559 dict_bench_writer_thread, &threads[idx]);
1560 }
1561
1562 sleep_usec(cfg->seconds_to_run * USEC_PER_SEC);
1563 __atomic_store_n(&join, 1, __ATOMIC_RELAXED);
1564
1565 for(int i = 0; i < total_threads; i++) {
1566 nd_thread_join(threads[i].thread);
1567 if(threads[i].is_writer)
1568 summary.write_ops += threads[i].stats.ops;
1569 else {
1570 summary.read_ops += threads[i].stats.ops;
1571 summary.read_items_seen += threads[i].stats.items_seen;
1572 }
1573 }
1574
1575 dict_bench_aggregate_latency(threads, total_threads, false, &summary.read_avg_ut, &summary.read_p99_ut);
1576 dict_bench_aggregate_latency(threads, total_threads, true, &summary.write_avg_ut, &summary.write_p99_ut);
1577 dictionary_destroy(dict);
1578 cleanup_destroyed_dictionaries(false);
1579 freez(threads);
1580
1581 if(cfg->read_mode == DICT_BENCH_READ_TRAVERSAL) {
1582 fprintf(stderr, "%-14s %8zu %8d %8d %14.0f %14.0f %14.0f %14.2f %14.2f %14.2f %14.2f\n",
1583 cfg->workload,
1584 cfg->entries,
1585 cfg->readers,
1586 cfg->writers,
1587 cfg->seconds_to_run ? (double)summary.read_ops / cfg->seconds_to_run : 0.0,
1588 cfg->seconds_to_run ? (double)summary.read_items_seen / cfg->seconds_to_run : 0.0,
1589 cfg->seconds_to_run ? (double)summary.write_ops / cfg->seconds_to_run : 0.0,
1590 summary.read_avg_ut,
1591 summary.read_p99_ut,
1592 summary.write_avg_ut,
1593 summary.write_p99_ut);
1594 }
1595 else {
1596 fprintf(stderr, "%-14s %8zu %8d %8d %14.0f %14.0f %14.2f %14.2f %14.2f %14.2f\n",
1597 cfg->workload,
1598 cfg->entries,
1599 cfg->readers,
1600 cfg->writers,
1601 cfg->seconds_to_run ? (double)summary.read_ops / cfg->seconds_to_run : 0.0,
1602 cfg->seconds_to_run ? (double)summary.write_ops / cfg->seconds_to_run : 0.0,
1603 summary.read_avg_ut,
1604 summary.read_p99_ut,
1605 summary.write_avg_ut,
1606 summary.write_p99_ut);
1607 }
1608 }
1609
1610 static void dict_bench_print_separator(size_t width) {
1611 for(size_t i = 0; i < width; i++)
1612 fputc('-', stderr);
1613 fputc('\n', stderr);
1614 }
1615
1616 static void dict_bench_print_header_line(const char *line) {
1617 fprintf(stderr, "%s\n", line);
1618 dict_bench_print_separator(strlen(line));
1619 }
1620
1621 static void dict_bench_print_suite_header(
1622 const char *suite,
1623 const char *read_ops_label,
1624 const char *read_avg_label,
1625 const char *read_slow_label,
1626 const char *writer_desc
1627 ) {
1628 char header[512];
1629
1630 fprintf(stderr, "\n=== %s ===\n", suite);
1631 fprintf(stderr, "%s\n", writer_desc);
1632 snprintfz(header, sizeof(header),
1633 "%-14s %8s %8s %8s %14s %14s %14s %14s %14s %14s",
1634 "workload", "entries", "readers", "writers",
1635 read_ops_label, "write ops/s",
1636 read_avg_label, read_slow_label, "w avg us", "w slow us");
1637 dict_bench_print_header_line(header);
1638 }
1639
1640 static void dict_bench_print_traversal_header(void) {
1641 char header[512];
1642
1643 fprintf(stderr, "\n=== Dictionary Traversal Benchmark ===\n");
1644 fprintf(stderr, "Reader workload: full dictionary scan. Writer workload: temporary-key insert followed by delete.\n");
1645 snprintfz(header, sizeof(header),
1646 "%-14s %8s %8s %8s %14s %14s %14s %14s %14s %14s %14s",
1647 "workload", "entries", "readers", "writers",
1648 "full scans/s", "items visited/s", "write ops/s",
1649 "avg scan us", "slow scan us", "w avg us", "w slow us");
1650 dict_bench_print_header_line(header);
1651 }
1652
1653 int dictionary_unittest_benchmark(void) {
1654 const time_t seconds_to_run = 2;
1655 const size_t sizes[] = {100, 10000};
1656 const int readers[] = {1, 4, 8};
1657 const int writers[] = {0, 1, 2};
1658
1659 dict_bench_print_traversal_header();
1660 for(size_t i = 0; i < sizeof(readers) / sizeof(readers[0]); i++) {
1661 for(size_t j = 0; j < sizeof(writers) / sizeof(writers[0]); j++) {
1662 struct dict_bench_config cfg = {
1663 .workload = "traversal",
1664 .entries = 10000,
1665 .readers = readers[i],
1666 .writers = writers[j],
1667 .seconds_to_run = seconds_to_run,
1668 .read_mode = DICT_BENCH_READ_TRAVERSAL,
1669 .write_mode = DICT_BENCH_WRITE_CHURN,
1670 };
1671 dict_bench_run_case(&cfg);
1672 }
1673 }
1674
1675 dict_bench_print_suite_header(
1676 "Dictionary Lookup Benchmark",
1677 "lookups/s",
1678 "avg lookup us",
1679 "slow lookup us",
1680 "Reader workload: dictionary_get(). Writer workload: overwrite an existing dictionary entry."
1681 );
1682 for(size_t s = 0; s < sizeof(sizes) / sizeof(sizes[0]); s++) {
1683 for(size_t i = 0; i < sizeof(readers) / sizeof(readers[0]); i++) {
1684 for(size_t j = 0; j < sizeof(writers) / sizeof(writers[0]); j++) {
1685 struct dict_bench_config hot_cfg = {
1686 .workload = "lookup-hot",
1687 .entries = sizes[s],
1688 .readers = readers[i],
1689 .writers = writers[j],
1690 .seconds_to_run = seconds_to_run,
1691 .read_mode = DICT_BENCH_READ_LOOKUP_HOT,
1692 .write_mode = DICT_BENCH_WRITE_UPDATE,
1693 };
1694 struct dict_bench_config random_cfg = hot_cfg;
1695 random_cfg.workload = "lookup-random";
1696 random_cfg.read_mode = DICT_BENCH_READ_LOOKUP_RANDOM;
1697
1698 dict_bench_run_case(&hot_cfg);
1699 dict_bench_run_case(&random_cfg);
1700 }
1701 }
1702 }
1703
1704 dict_bench_print_suite_header(
1705 "Dictionary Mixed RW Benchmark",
1706 "read ops/s",
1707 "read avg us",
1708 "slow read us",
1709 "Reader workload: random lookups. Writer workload depends on the row: update rewrites existing keys, churn inserts then deletes temporary keys."
1710 );
1711 {
1712 const struct dict_bench_config configs[] = {
1713 {.workload = "mixed-8r1w", .entries = 10000, .readers = 8, .writers = 1, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_LOOKUP_RANDOM, .write_mode = DICT_BENCH_WRITE_UPDATE},
1714 {.workload = "mixed-8r2w", .entries = 10000, .readers = 8, .writers = 2, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_LOOKUP_RANDOM, .write_mode = DICT_BENCH_WRITE_UPDATE},
1715 {.workload = "mixed-4r1w", .entries = 10000, .readers = 4, .writers = 1, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_LOOKUP_RANDOM, .write_mode = DICT_BENCH_WRITE_CHURN},
1716 {.workload = "mixed-4r2w", .entries = 10000, .readers = 4, .writers = 2, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_LOOKUP_RANDOM, .write_mode = DICT_BENCH_WRITE_CHURN},
1717 };
1718
1719 for(size_t i = 0; i < sizeof(configs) / sizeof(configs[0]); i++)
1720 dict_bench_run_case(&configs[i]);
1721 }
1722
1723 dict_bench_print_suite_header(
1724 "Dictionary Writer Cost Benchmark",
1725 "read ops/s",
1726 "read avg us",
1727 "slow read us",
1728 "Writer workload: 'update' overwrites existing keys, 'churn' inserts then deletes temporary keys; '+r' rows include background readers."
1729 );
1730 {
1731 const struct dict_bench_config configs[] = {
1732 {.workload = "update-1w", .entries = 10000, .readers = 0, .writers = 1, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_NONE, .write_mode = DICT_BENCH_WRITE_UPDATE},
1733 {.workload = "update-2w", .entries = 10000, .readers = 0, .writers = 2, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_NONE, .write_mode = DICT_BENCH_WRITE_UPDATE},
1734 {.workload = "churn-1w", .entries = 10000, .readers = 0, .writers = 1, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_NONE, .write_mode = DICT_BENCH_WRITE_CHURN},
1735 {.workload = "churn-2w", .entries = 10000, .readers = 0, .writers = 2, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_NONE, .write_mode = DICT_BENCH_WRITE_CHURN},
1736 {.workload = "update+r", .entries = 10000, .readers = 8, .writers = 1, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_LOOKUP_RANDOM, .write_mode = DICT_BENCH_WRITE_UPDATE},
1737 {.workload = "churn+r", .entries = 10000, .readers = 8, .writers = 2, .seconds_to_run = seconds_to_run, .read_mode = DICT_BENCH_READ_LOOKUP_RANDOM, .write_mode = DICT_BENCH_WRITE_CHURN},
1738 };
1739
1740 for(size_t i = 0; i < sizeof(configs) / sizeof(configs[0]); i++)
1741 dict_bench_run_case(&configs[i]);
1742 }
1743
1744 fprintf(stderr, "\n");
1745 return 0;
1746 }
1747
1748 int dictionary_unittest(size_t entries) {
1749 if(entries < 10) entries = 10;
1750
1751 DICTIONARY *dict;
1752 size_t errors = 0;
1753
1754 fprintf(stderr, "Generating %zu names and values...\n", entries);
1755 char **names = dictionary_unittest_generate_names(entries);
1756 char **values = dictionary_unittest_generate_values(entries);
1757
1758 fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries);
1759 dict = dictionary_create(DICT_OPTION_SINGLE_THREADED);
1760 dictionary_unittest_clone(dict, names, values, entries, &errors);
1761
1762 fprintf(stderr, "\nCreating dictionary multi threaded, clone, %zu items\n", entries);
1763 dict = dictionary_create(DICT_OPTION_NONE);
1764 dictionary_unittest_clone(dict, names, values, entries, &errors);
1765
1766 fprintf(stderr, "\nCreating dictionary single threaded, non-clone, add-in-front options, %zu items\n", entries);
1767 dict = dictionary_create(
1768 DICT_OPTION_SINGLE_THREADED | DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE |
1769 DICT_OPTION_ADD_IN_FRONT);
1770 dictionary_unittest_nonclone(dict, names, values, entries, &errors);
1771
1772 fprintf(stderr, "\nCreating dictionary multi threaded, non-clone, add-in-front options, %zu items\n", entries);
1773 dict = dictionary_create(
1774 DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_ADD_IN_FRONT);
1775 dictionary_unittest_nonclone(dict, names, values, entries, &errors);
1776
1777 fprintf(stderr, "\nCreating dictionary single-threaded, non-clone, don't overwrite options, %zu items\n", entries);
1778 dict = dictionary_create(
1779 DICT_OPTION_SINGLE_THREADED | DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE |
1780 DICT_OPTION_DONT_OVERWRITE_VALUE);
1781 dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone);
1782 dictionary_unittest_run_and_measure_time(dict, "resetting non-overwrite entries", names, values, entries, &errors, dictionary_unittest_reset_dont_overwrite_nonclone);
1783 dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, &errors, dictionary_unittest_foreach);
1784 dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback", names, values, entries, &errors, dictionary_unittest_walkthrough);
1785 dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback stop", names, values, entries, &errors, dictionary_unittest_walkthrough_stop);
1786 dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy);
1787
1788 fprintf(stderr, "\nCreating dictionary multi-threaded, non-clone, don't overwrite options, %zu items\n", entries);
1789 dict = dictionary_create(
1790 DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE);
1791 dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone);
1792 dictionary_unittest_run_and_measure_time(dict, "walkthrough write delete this", names, values, entries, &errors, dictionary_unittest_walkthrough_delete_this);
1793 dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, &errors, dictionary_unittest_destroy);
1794
1795 fprintf(stderr, "\nCreating dictionary multi-threaded, non-clone, don't overwrite options, %zu items\n", entries);
1796 dict = dictionary_create(
1797 DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE);
1798 dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone);
1799 dictionary_unittest_run_and_measure_time(dict, "foreach write delete this", names, values, entries, &errors, dictionary_unittest_foreach_delete_this);
1800 dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop empty", names, values, 0, &errors, dictionary_unittest_foreach);
1801 dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback empty", names, values, 0, &errors, dictionary_unittest_walkthrough);
1802 dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, &errors, dictionary_unittest_destroy);
1803
1804 fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries);
1805 dict = dictionary_create(DICT_OPTION_SINGLE_THREADED);
1806 dictionary_unittest_sorting(dict, names, values, entries, &errors);
1807 dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy);
1808
1809 fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries);
1810 dict = dictionary_create(DICT_OPTION_SINGLE_THREADED);
1811 dictionary_unittest_null_dfe(dict, names, values, entries, &errors);
1812 dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy);
1813
1814 fprintf(stderr, "\nCreating dictionary single threaded, noclone, %zu items\n", entries);
1815 dict = dictionary_create(DICT_OPTION_SINGLE_THREADED | DICT_OPTION_VALUE_LINK_DONT_CLONE);
1816 dictionary_unittest_null_dfe(dict, names, values, entries, &errors);
1817 dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy);
1818
1819 // check reference counters
1820 {
1821 fprintf(stderr, "\nTesting reference counters:\n");
1822 dict = dictionary_create(DICT_OPTION_NONE | DICT_OPTION_NAME_LINK_DONT_CLONE);
1823 errors += unittest_check_dictionary("", dict, 0, 0, 0, 0, 0);
1824
1825 fprintf(stderr, "\nAdding test item to dictionary and acquiring it\n");
1826 dictionary_set(dict, "test", "ITEM1", 6);
1827 DICTIONARY_ITEM *item = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test");
1828
1829 errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0);
1830 errors += unittest_check_item("ACQUIRED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true);
1831
1832 fprintf(stderr, "\nChecking that reference counters are increased:\n");
1833 void *t;
1834 dfe_start_read(dict, t) {
1835 errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0);
1836 errors += unittest_check_item("ACQUIRED TRAVERSAL", dict, item, "test", "ITEM1", 2, ITEM_FLAG_NONE, true, true, true);
1837 }
1838 dfe_done(t);
1839
1840 fprintf(stderr, "\nChecking that reference counters are decreased:\n");
1841 errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0);
1842 errors += unittest_check_item("ACQUIRED TRAVERSAL 2", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true);
1843
1844 fprintf(stderr, "\nDeleting the item we have acquired:\n");
1845 dictionary_del(dict, "test");
1846
1847 errors += unittest_check_dictionary("", dict, 0, 0, 1, 1, 0);
1848 errors += unittest_check_item("DELETED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true);
1849
1850 fprintf(stderr, "\nAdding another item with the same name of the item we deleted, while being acquired:\n");
1851 dictionary_set(dict, "test", "ITEM2", 6);
1852 errors += unittest_check_dictionary("", dict, 1, 1, 1, 1, 0);
1853
1854 fprintf(stderr, "\nAcquiring the second item:\n");
1855 DICTIONARY_ITEM *item2 = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test");
1856 errors += unittest_check_item("FIRST", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true);
1857 errors += unittest_check_item("SECOND", dict, item2, "test", "ITEM2", 1, ITEM_FLAG_NONE, true, true, true);
1858 errors += unittest_check_dictionary("", dict, 1, 1, 1, 2, 0);
1859
1860 fprintf(stderr, "\nReleasing the second item (the first is still acquired):\n");
1861 dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item2);
1862 errors += unittest_check_dictionary("", dict, 1, 1, 1, 1, 0);
1863 errors += unittest_check_item("FIRST", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true);
1864 errors += unittest_check_item("SECOND RELEASED", dict, item2, "test", "ITEM2", 0, ITEM_FLAG_NONE, true, true, true);
1865
1866 fprintf(stderr, "\nDeleting the second item (the first is still acquired):\n");
1867 dictionary_del(dict, "test");
1868 errors += unittest_check_dictionary("", dict, 0, 0, 1, 1, 0);
1869 errors += unittest_check_item("ACQUIRED DELETED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true);
1870
1871 fprintf(stderr, "\nReleasing the first item (which we have already deleted):\n");
1872 dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item);
1873 dfe_start_write(dict, item) ; dfe_done(item);
1874 errors += unittest_check_dictionary("", dict, 0, 0, 1, 0, 1);
1875
1876 fprintf(stderr, "\nAdding again the test item to dictionary and acquiring it\n");
1877 dictionary_set(dict, "test", "ITEM1", 6);
1878 item = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test");
1879
1880 errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0);
1881 errors += unittest_check_item("RE-ADDITION", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true);
1882
1883 fprintf(stderr, "\nDestroying the dictionary while we have acquired an item\n");
1884 dictionary_destroy(dict);
1885
1886 fprintf(stderr, "Releasing the item (on a destroyed dictionary)\n");
1887 dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item);
1888 item = NULL;
1889 dict = NULL;
1890 }
1891
1892 dictionary_unittest_free_char_pp(names, entries);
1893 dictionary_unittest_free_char_pp(values, entries);
1894
1895 errors += dictionary_unittest_views();
1896 errors += dictionary_unittest_threads();
1897 errors += dictionary_unittest_view_threads();
1898
1899 if(!dictionary_traverse_or_destroy_unittest()) {
1900 fprintf(stderr, "Destroy on traversal test failed\n");
1901 errors++;
1902 }
1903 else
1904 fprintf(stderr, "Destroy on traversal test OK\n");
1905
1906 errors += dictionary_destroy_race_unittest();
1907
1908 cleanup_destroyed_dictionaries(false);
1909
1910 size_t delayed = dictionary_destroy_delayed_count();
1911 if(delayed != 0) {
1912 fprintf(stderr, "WARNING: There are %zu dictionaries that cannot be destroyed\n", delayed);
1913 }
1914 else
1915 fprintf(stderr, "All dictionaries have been freed: OK\n");
1916
1917 fprintf(stderr, "\n%zu errors found\n", errors);
1918 return errors ? 1 : 0;
1919 }