| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | #ifndef NETDATA_DICTIONARY_H |
| 4 | #define NETDATA_DICTIONARY_H 1 |
| 5 | |
| 6 | #include "../libnetdata.h" |
| 7 | |
| 8 | |
| 9 | /* |
| 10 | * Netdata DICTIONARY features: |
| 11 | * |
| 12 | * CLONE or LINK |
| 13 | * Names and Values in the dictionary can be cloned or linked. |
| 14 | * In clone mode, the dictionary does all the memory management. |
| 15 | * The default is clone for both names and values. |
| 16 | * Set DICT_OPTION_NAME_LINK_DONT_CLONE to link names. |
| 17 | * Set DICT_OPTION_VALUE_LINK_DONT_CLONE to link names. |
| 18 | * |
| 19 | * ORDERED |
| 20 | * Items are ordered in the order they are added (new items are appended at the end). |
| 21 | * You may reverse the order by setting the flag DICT_OPTION_ADD_IN_FRONT. |
| 22 | * |
| 23 | * LOOKUP |
| 24 | * The dictionary uses JudyHS to maintain a very fast randomly accessible hash table. |
| 25 | * |
| 26 | * MULTI-THREADED and SINGLE-THREADED |
| 27 | * Each dictionary may be single threaded (no locks), or multi-threaded (multiple readers or one writer). |
| 28 | * The default is multi-threaded. Add the flag DICT_OPTION_SINGLE_THREADED for single-threaded. |
| 29 | * |
| 30 | * WALK-THROUGH and FOREACH traversal |
| 31 | * The dictionary can be traversed on read or write mode, either with a callback (walkthrough) or with |
| 32 | * a loop (foreach). |
| 33 | * |
| 34 | * In write mode traversal, the caller may delete only the current item, but may add as many items as needed. |
| 35 | * |
| 36 | */ |
| 37 | |
| 38 | #ifdef NETDATA_INTERNAL_CHECKS |
| 39 | #define DICT_WITH_STATS 1 |
| 40 | #endif |
| 41 | |
| 42 | #ifdef DICTIONARY_INTERNALS |
| 43 | #define DICTFE_CONST |
| 44 | #define DICT_ITEM_CONST |
| 45 | #else |
| 46 | #define DICTFE_CONST const |
| 47 | #define DICT_ITEM_CONST const |
| 48 | #endif |
| 49 | |
| 50 | typedef struct dictionary DICTIONARY; |
| 51 | typedef struct dictionary_item DICTIONARY_ITEM; |
| 52 | |
| 53 | typedef enum __attribute__((packed)) dictionary_options { |
| 54 | DICT_OPTION_NONE = 0, // the default is the opposite of all below |
| 55 | DICT_OPTION_SINGLE_THREADED = (1 << 0), // don't use any locks (default: use locks) |
| 56 | DICT_OPTION_VALUE_LINK_DONT_CLONE = (1 << 1), // don't copy the value, just point to the one provided (default: copy) |
| 57 | DICT_OPTION_NAME_LINK_DONT_CLONE = (1 << 2), // don't copy the name, just point to the one provided (default: copy) |
| 58 | DICT_OPTION_DONT_OVERWRITE_VALUE = (1 << 3), // don't overwrite values of dictionary items (default: overwrite) |
| 59 | DICT_OPTION_ADD_IN_FRONT = (1 << 4), // add dictionary items at the front of the linked list (default: at the end) |
| 60 | DICT_OPTION_FIXED_SIZE = (1 << 5), // the items of the dictionary have a fixed size |
| 61 | DICT_OPTION_INDEX_JUDY = (1 << 6), // the default, if no other indexing is set |
| 62 | // DICT_OPTION_INDEX_HASHTABLE = (1 << 7), // use SIMPLE_HASHTABLE for indexing |
| 63 | } DICT_OPTIONS; |
| 64 | |
| 65 | struct dictionary_stats { |
| 66 | const char *name; // the name of the category |
| 67 | |
| 68 | struct { |
| 69 | PAD64(size_t) active; // the number of active dictionaries |
| 70 | PAD64(size_t) deleted; // the number of dictionaries queued for destruction |
| 71 | } dictionaries; |
| 72 | |
| 73 | struct { |
| 74 | PAD64(long) entries; // active items in the dictionary |
| 75 | PAD64(long) pending_deletion; // pending deletion items in the dictionary |
| 76 | PAD64(long) referenced; // referenced items in the dictionary |
| 77 | } items; |
| 78 | |
| 79 | struct { |
| 80 | PAD64(size_t) creations; // dictionary creations |
| 81 | PAD64(size_t) destructions; // dictionary destructions |
| 82 | PAD64(size_t) flushes; // dictionary flushes |
| 83 | PAD64(size_t) traversals; // dictionary foreach |
| 84 | PAD64(size_t) walkthroughs; // dictionary walkthrough |
| 85 | PAD64(size_t) garbage_collections; // dictionary garbage collections |
| 86 | PAD64(size_t) searches; // item searches |
| 87 | PAD64(size_t) inserts; // item inserts |
| 88 | PAD64(size_t) resets; // item resets |
| 89 | PAD64(size_t) deletes; // item deletes |
| 90 | } ops; |
| 91 | |
| 92 | struct { |
| 93 | PAD64(size_t) inserts; // number of times the insert callback is called |
| 94 | PAD64(size_t) conflicts; // number of times the conflict callback is called |
| 95 | PAD64(size_t) reacts; // number of times the react callback is called |
| 96 | PAD64(size_t) deletes; // number of times the delete callback is called |
| 97 | } callbacks; |
| 98 | |
| 99 | // memory |
| 100 | struct { |
| 101 | PAD64(ssize_t) index; // bytes of keys indexed (indication of the index size) |
| 102 | PAD64(ssize_t) values; // bytes of caller structures |
| 103 | PAD64(ssize_t) dict; // bytes of the structures dictionary needs |
| 104 | } memory; |
| 105 | |
| 106 | // spin locks |
| 107 | struct { |
| 108 | PAD64(size_t) use_spins; // number of times a reference to item had to spin to acquire it or ignore it |
| 109 | PAD64(size_t) search_spins; // number of times a successful search result had to be thrown away |
| 110 | PAD64(size_t) insert_spins; // number of times an insertion to the hash table had to be repeated |
| 111 | PAD64(size_t) delete_spins; // number of times a deletion had to spin to get a decision |
| 112 | } spin_locks; |
| 113 | }; |
| 114 | |
| 115 | // Create a dictionary |
| 116 | #define dictionary_create(options) dictionary_create_advanced(options, NULL, 0) |
| 117 | DICTIONARY *dictionary_create_advanced(DICT_OPTIONS options, struct dictionary_stats *stats, size_t fixed_size); |
| 118 | |
| 119 | // Create a view on a dictionary |
| 120 | DICTIONARY *dictionary_create_view(DICTIONARY *master); |
| 121 | |
| 122 | // an insert callback to be called just after an item is added to the dictionary |
| 123 | // this callback is called while the dictionary is write locked! |
| 124 | typedef void (*dict_cb_insert_t)(const DICTIONARY_ITEM *item, void *value, void *data); |
| 125 | void dictionary_register_insert_callback(DICTIONARY *dict, dict_cb_insert_t insert_callback, void *data); |
| 126 | |
| 127 | // a delete callback to be called just before an item is deleted forever |
| 128 | // this callback is called while the dictionary is write locked! |
| 129 | typedef void (*dict_cb_delete_t)(const DICTIONARY_ITEM *item, void *value, void *data); |
| 130 | void dictionary_register_delete_callback(DICTIONARY *dict, dict_cb_delete_t delete_callback, void *data); |
| 131 | |
| 132 | // a merge callback to be called when DICT_OPTION_DONT_OVERWRITE_VALUE |
| 133 | // and an item is already found in the dictionary - the dictionary does nothing else in this case |
| 134 | // the old_value will remain in the dictionary - the new_value is ignored |
| 135 | // The callback should return true if the value has been updated (it increases the dictionary version). |
| 136 | typedef bool (*dict_cb_conflict_t)(const DICTIONARY_ITEM *item, void *old_value, void *new_value, void *data); |
| 137 | void dictionary_register_conflict_callback(DICTIONARY *dict, dict_cb_conflict_t conflict_callback, void *data); |
| 138 | |
| 139 | // a reaction callback to be called after every item insertion or conflict |
| 140 | // after the constructors have finished and the items are fully available for use |
| 141 | // and the dictionary is not write locked anymore |
| 142 | typedef void (*dict_cb_react_t)(const DICTIONARY_ITEM *item, void *value, void *data); |
| 143 | void dictionary_register_react_callback(DICTIONARY *dict, dict_cb_react_t react_callback, void *data); |
| 144 | |
| 145 | // Destroy a dictionary |
| 146 | // Returns the number of bytes freed |
| 147 | // The returned value will not include name/key sizes |
| 148 | // Registered delete callbacks will be run for each item in the dictionary. |
| 149 | size_t dictionary_destroy(DICTIONARY *dict); |
| 150 | |
| 151 | // Empties a dictionary |
| 152 | // Referenced items will survive, but are not offered anymore. |
| 153 | // Registered delete callbacks will be run for each item in the dictionary. |
| 154 | void dictionary_flush(DICTIONARY *dict); |
| 155 | |
| 156 | void dictionary_version_increment(DICTIONARY *dict); |
| 157 | |
| 158 | void dictionary_garbage_collect(DICTIONARY *dict); |
| 159 | |
| 160 | size_t cleanup_destroyed_dictionaries(bool shutdown); |
| 161 | |
| 162 | // Report on allocated dictionaries - used during Address Sanitizer builds |
| 163 | void dictionary_print_still_allocated_stacktraces(void); |
| 164 | |
| 165 | // ---------------------------------------------------------------------------- |
| 166 | // Set an item in the dictionary |
| 167 | // |
| 168 | // - if an item with the same name does not exist, create one |
| 169 | // - if an item with the same name exists, then: |
| 170 | // a) if DICT_OPTION_DONT_OVERWRITE_VALUE is set, just return the existing value (ignore the new value) |
| 171 | // else b) reset the value to the new value passed at the call |
| 172 | // |
| 173 | // When DICT_OPTION_VALUE_LINK_DONT_CLONE is set, the value is linked, otherwise it is copied |
| 174 | // When DICT_OPTION_NAME_LINK_DONT_CLONE is set, the name is linked, otherwise it is copied |
| 175 | // |
| 176 | // When neither DICT_OPTION_VALUE_LINK_DONT_CLONE nor DICT_OPTION_NAME_LINK_DONT_CLONE are set, all the |
| 177 | // memory management for names and values is done by the dictionary. |
| 178 | // |
| 179 | // Passing NULL as value, the dictionary will callocz() the newly allocated value, otherwise it will copy it. |
| 180 | // Passing 0 as value_len, the dictionary will set the value to NULL (no allocations for value will be made). |
| 181 | #define dictionary_set(dict, name, value, value_len) dictionary_set_advanced(dict, name, -1, value, value_len, NULL) |
| 182 | void *dictionary_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data); |
| 183 | |
| 184 | #define dictionary_set_and_acquire_item(dict, name, value, value_len) dictionary_set_and_acquire_item_advanced(dict, name, -1, value, value_len, NULL) |
| 185 | DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_set_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data); |
| 186 | |
| 187 | // set an item in a dictionary view |
| 188 | #define dictionary_view_set_and_acquire_item(dict, name, master_item) dictionary_view_set_and_acquire_item_advanced(dict, name, -1, master_item) |
| 189 | DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_view_set_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICT_ITEM_CONST DICTIONARY_ITEM *master_item); |
| 190 | #define dictionary_view_set(dict, name, master_item) dictionary_view_set_advanced(dict, name, -1, master_item) |
| 191 | void *dictionary_view_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICT_ITEM_CONST DICTIONARY_ITEM *master_item); |
| 192 | |
| 193 | // ---------------------------------------------------------------------------- |
| 194 | // Get an item from the dictionary |
| 195 | // If it returns NULL, the item is not found |
| 196 | |
| 197 | #define dictionary_get(dict, name) dictionary_get_advanced(dict, name, -1) |
| 198 | void *dictionary_get_advanced(DICTIONARY *dict, const char *name, ssize_t name_len); |
| 199 | |
| 200 | #define dictionary_get_and_acquire_item(dict, name) dictionary_get_and_acquire_item_advanced(dict, name, -1) |
| 201 | DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_get_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len); |
| 202 | |
| 203 | |
| 204 | // ---------------------------------------------------------------------------- |
| 205 | // Delete an item from the dictionary |
| 206 | // returns true if the item was found and has been deleted |
| 207 | // returns false if the item was not found in the index |
| 208 | |
| 209 | #define dictionary_del(dict, name) dictionary_del_advanced(dict, name, -1) |
| 210 | bool dictionary_del_advanced(DICTIONARY *dict, const char *name, ssize_t name_len); |
| 211 | |
| 212 | // ---------------------------------------------------------------------------- |
| 213 | // reference counters management |
| 214 | |
| 215 | void dictionary_acquired_item_release(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item); |
| 216 | |
| 217 | DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item); |
| 218 | |
| 219 | const char *dictionary_acquired_item_name(DICT_ITEM_CONST DICTIONARY_ITEM *item); |
| 220 | void *dictionary_acquired_item_value(DICT_ITEM_CONST DICTIONARY_ITEM *item); |
| 221 | |
| 222 | size_t dictionary_acquired_item_references(DICT_ITEM_CONST DICTIONARY_ITEM *item); |
| 223 | |
| 224 | // ---------------------------------------------------------------------------- |
| 225 | // Traverse (walk through) the items of the dictionary. |
| 226 | // The order of traversal is currently the order of insertion. |
| 227 | // |
| 228 | // The callback function may return a negative number to stop the traversal, |
| 229 | // in which case that negative value is returned to the caller. |
| 230 | // |
| 231 | // If all callback calls return zero or positive numbers, the sum of all of |
| 232 | // them is returned to the caller. |
| 233 | // |
| 234 | // You cannot alter the dictionary from inside a dictionary_walkthrough_read() - deadlock! |
| 235 | // You can only delete the current item from inside a dictionary_walkthrough_write() - you can add as many as you want. |
| 236 | // |
| 237 | typedef int (*dict_walkthrough_callback_t)(const DICTIONARY_ITEM *item, void *value, void *data); |
| 238 | |
| 239 | #define dictionary_walkthrough_read(dict, callback, data) dictionary_walkthrough_rw(dict, 'r', callback, data) |
| 240 | #define dictionary_walkthrough_write(dict, callback, data) dictionary_walkthrough_rw(dict, 'w', callback, data) |
| 241 | int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, dict_walkthrough_callback_t walkthrough_callback, void *data); |
| 242 | |
| 243 | typedef int (*dict_item_comparator_t)(const DICTIONARY_ITEM **item1, const DICTIONARY_ITEM **item2); |
| 244 | |
| 245 | #define dictionary_sorted_walkthrough_read(dict, callback, data) dictionary_sorted_walkthrough_rw(dict, 'r', callback, data, NULL) |
| 246 | #define dictionary_sorted_walkthrough_write(dict, callback, data) dictionary_sorted_walkthrough_rw(dict, 'w', callback, data, NULL) |
| 247 | int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, dict_walkthrough_callback_t walkthrough_callback, void *data, dict_item_comparator_t item_comparator_callback); |
| 248 | |
| 249 | // ---------------------------------------------------------------------------- |
| 250 | // Traverse with foreach |
| 251 | // |
| 252 | // Use like this: |
| 253 | // |
| 254 | // DICTFE dfe = {}; |
| 255 | // for(MY_ITEM *item = dfe_start_read(&dfe, dict); item ; item = dfe_next(&dfe)) { |
| 256 | // // do things with the item and its dfe.name |
| 257 | // } |
| 258 | // dfe_done(&dfe); |
| 259 | // |
| 260 | // You cannot alter the dictionary from within a dfe_read_start() - deadlock! |
| 261 | // You can only delete the current item from inside a dfe_start_write() - you can add as many as you want. |
| 262 | // |
| 263 | |
| 264 | #define DICTIONARY_LOCK_READ 'r' |
| 265 | #define DICTIONARY_LOCK_WRITE 'w' |
| 266 | #define DICTIONARY_LOCK_REENTRANT 'z' |
| 267 | |
| 268 | void dictionary_write_lock(DICTIONARY *dict); |
| 269 | void dictionary_write_unlock(DICTIONARY *dict); |
| 270 | |
| 271 | typedef DICTFE_CONST struct dictionary_foreach { |
| 272 | DICTIONARY *dict; // the dictionary upon we work |
| 273 | |
| 274 | DICTIONARY_ITEM *item; // the item we work on, to remember the position we are at |
| 275 | // this can be used with dictionary_acquired_item_dup() to |
| 276 | // acquire the currently working item. |
| 277 | |
| 278 | const char *name; // the dictionary name of the last item used |
| 279 | void *value; // the dictionary value of the last item used |
| 280 | // same as the return value of dictfe_start() and dictfe_next() |
| 281 | |
| 282 | size_t counter; // counts the number of iterations made, starting from zero |
| 283 | |
| 284 | char rw; // the lock mode 'r' or 'w' |
| 285 | bool locked; // true when the dictionary is locked |
| 286 | } DICTFE; |
| 287 | |
| 288 | #define dfe_start_read(dict, value) dfe_start_rw(dict, value, DICTIONARY_LOCK_READ) |
| 289 | #define dfe_start_write(dict, value) dfe_start_rw(dict, value, DICTIONARY_LOCK_WRITE) |
| 290 | #define dfe_start_reentrant(dict, value) dfe_start_rw(dict, value, DICTIONARY_LOCK_REENTRANT) |
| 291 | |
| 292 | #define dfe_start_rw(dictionary, ptr, mode) \ |
| 293 | do { \ |
| 294 | /* automatically cleanup DFE, to allow using return from within the loop */ \ |
| 295 | DICTFE _cleanup_(dictionary_foreach_done) ptr ## _dfe = (DICTFE){ \ |
| 296 | .dict = (dictionary), \ |
| 297 | .item = NULL, \ |
| 298 | .name = NULL, \ |
| 299 | .value = NULL, \ |
| 300 | .counter = 0, \ |
| 301 | .rw = (mode), \ |
| 302 | .locked = false, \ |
| 303 | }; \ |
| 304 | (void)(ptr); /* needed to avoid warning when looping without using this */ \ |
| 305 | for((ptr) = dictionary_foreach_start_rw(&ptr ## _dfe); \ |
| 306 | (ptr ## _dfe.item) || (ptr) ; \ |
| 307 | (ptr) = dictionary_foreach_next(&ptr ## _dfe)) \ |
| 308 | { |
| 309 | |
| 310 | #define dfe_done(value) \ |
| 311 | } \ |
| 312 | } while(0) |
| 313 | |
| 314 | #define dfe_unlock(value) dictionary_foreach_unlock(&value ## _dfe) |
| 315 | |
| 316 | void *dictionary_foreach_start_rw(DICTFE *dfe); |
| 317 | void *dictionary_foreach_next(DICTFE *dfe); |
| 318 | void dictionary_foreach_done(DICTFE *dfe); |
| 319 | void dictionary_foreach_unlock(DICTFE *dfe); |
| 320 | |
| 321 | // ---------------------------------------------------------------------------- |
| 322 | // Get statistics about the dictionary |
| 323 | |
| 324 | size_t dictionary_version(DICTIONARY *dict); |
| 325 | size_t dictionary_entries(DICTIONARY *dict); |
| 326 | size_t dictionary_referenced_items(DICTIONARY *dict); |
| 327 | |
| 328 | // for all cases that the caller does not provide a stats structure, this is where they are accumulated. |
| 329 | extern struct dictionary_stats dictionary_stats_category_other; |
| 330 | |
| 331 | int dictionary_unittest(size_t entries); |
| 332 | int dictionary_unittest_benchmark(void); |
| 333 | |
| 334 | #endif /* NETDATA_DICTIONARY_H */ |