diff options
Diffstat (limited to 'libnetdata/dictionary')
| -rw-r--r-- | libnetdata/dictionary/README.md | 116 | ||||
| -rw-r--r-- | libnetdata/dictionary/dictionary.c | 3686 | ||||
| -rw-r--r-- | libnetdata/dictionary/dictionary.h | 305 |
3 files changed, 2689 insertions, 1418 deletions
diff --git a/libnetdata/dictionary/README.md b/libnetdata/dictionary/README.md index 879c1bcc1..6d7e55392 100644 --- a/libnetdata/dictionary/README.md +++ b/libnetdata/dictionary/README.md @@ -18,52 +18,61 @@ Dictionaries provide an interface to: - **Delete** an item from the dictionary (provided its `name`) - **Traverse** the list of items in the dictionary -Dictionaries are **ordered**, meaning that the order they have been added is preserved while traversing them. The caller may reverse this order by passing the flag `DICTIONARY_FLAG_ADD_IN_FRONT` when creating the dictionary. +Dictionaries are **ordered**, meaning that the order they have been added, is preserved while traversing them. The caller may reverse this order by passing the flag `DICT_OPTION_ADD_IN_FRONT` when creating the dictionary. -Dictionaries guarantee **uniqueness** of all items added to them, meaning that only one item with a given name can exist in the dictionary at any given time. +Dictionaries guarantee **uniqueness** of all items added to them, meaning that only one item with a given `name` can exist in the dictionary at any given time. -Dictionaries are extremely fast in all operations. They are indexing the keys with `JudyHS` (or `AVL` when `libJudy` is not available) and they utilize a double-linked-list for the traversal operations. Deletion is the most expensive operation, usually somewhat slower than insertion. +Dictionaries are extremely fast in all operations. They are indexing the keys with `JudyHS` and they utilize a double-linked-list for the traversal operations. Deletion is the most expensive operation, usually somewhat slower than insertion. ## Memory management Dictionaries come with 2 memory management options: -- **Clone** (copy) the name and/or the value to memory allocated by the dictionary. -- **Link** the name and/or the value, without allocating any memory about them. +- **Clone** (copy) the `name` and/or the `value` to memory allocated by the dictionary. +- **Link** the `name` and/or the `value`, without allocating any memory about them. -In **clone** mode, the dictionary guarantees that all operations on the dictionary items will automatically take care of the memory used by the name and/or the value. In case the value is an object that needs to have user allocated memory, the following callback functions can be registered: +In **clone** mode, the dictionary guarantees that all operations on the dictionary items, will automatically take care of the memory used by the `name` and/or the `value`. In case the `value` is an object that needs to have user allocated memory, the following callback functions can be registered: - 1.`dictionary_register_insert_callback()` that will be called just after the insertion of an item to the dictionary, or after the replacement of the value of a dictionary item (but while the dictionary is write-locked - if locking is enabled). - 2. `dictionary_register_delete_callback()` that will be called just prior to the deletion of an item from the dictionary, or prior to the replacement of the value of a dictionary item (but while the dictionary is write-locked - if locking is enabled). - 3. `dictionary_register_conflict_callback()` that will be called when `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` is set and another value is attempted to be inserted for the same key. +1. `dictionary_register_insert_callback()` that can be called just after the insertion of an item to the dictionary, or after the replacement of the value of a dictionary item. +2. `dictionary_register_delete_callback()` that will be called just prior to the deletion of an item from the dictionary, or prior to the replacement of the value of a dictionary item. +3. `dictionary_register_conflict_callback()` that will be called when `DICT_OPTION_DONT_OVERWRITE_VALUE` is set, and another `value` is attempted to be inserted for the same key. +4. `dictionary_register_react_callback()` that will be called after the the `insert` and the `conflict` callbacks. The `conflict` callback is called while the dictionary hash table is available for other threads. -In **link** mode, the name and/or the value are just linked to the dictionary item, and it is the user's responsibility to free the memory they use after an item is deleted from the dictionary or when the dictionary is destroyed. +In **link** mode, the `name` and/or the `value` are just linked to the dictionary item, and it is the user's responsibility to free the memory they use after an item is deleted from the dictionary or when the dictionary is destroyed. By default, **clone** mode is used for both the name and the value. -To use **link** mode for names, add `DICTIONARY_FLAG_NAME_LINK_DONT_CLONE` to the flags when creating the dictionary. +To use **link** mode for names, add `DICT_OPTION_NAME_LINK_DONT_CLONE` to the flags when creating the dictionary. -To use **link** mode for values, add `DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE` to the flags when creating the dictionary. +To use **link** mode for values, add `DICT_OPTION_VALUE_LINK_DONT_CLONE` to the flags when creating the dictionary. ## Locks The dictionary allows both **single-threaded** operation (no locks - faster) and **multi-threaded** operation utilizing a read-write lock. -The default is **multi-threaded**. To enable **single-threaded** add `DICTIONARY_FLAG_SINGLE_THREADED` to the flags when creating the dictionary. +The default is **multi-threaded**. To enable **single-threaded** add `DICT_OPTION_SINGLE_THREADED` to the flags when creating the dictionary. + +When in **multi-threaded** mode, the dictionaries have 2 independent R/W locks. One for the linked list and one for the hash table (index). An insertion and a deletion will acquire both independently (one after another) for as long as they are needed, but a traversal may hold the the linked list for longer durations. The hash table (index) lock may be acquired while the linked list is acquired, but not the other way around (and the way the code is structured, it is not technically possible to hold and index lock and then lock the linked list one). + +These locks are R/W locks. They allow multiple readers, but only one writer. + +Unlike POSIX standards, the linked-list lock, allows one writer to lock it multiple times. This has been implemented in such a way, so that a traversal to the items of the dictionary in write-lock mode, allows the writing thread to call `dictionary_set()` or `dictionary_del()`, which alter the dictionary index and the linked list. Especially for the deletion of the currently working item, the dictionary support delayed removal, so it will remove it from the index immediately and mark it as deleted, so that it can be added to the dictionary again with a different value and the traversal will still proceed from the point it was. ## Hash table operations The dictionary supports the following operations supported by the hash table: - `dictionary_set()` to add an item to the dictionary, or change its value. -- `dictionary_get()` to get an item from the dictionary. +- `dictionary_get()` and `dictionary_get_and_acquire_item()` to get an item from the dictionary. - `dictionary_del()` to delete an item from the dictionary. +For all the calls, there are also `*_advanced()` versions of them, that support more parameters. Check the header file for more information about them. + ## Creation and destruction Use `dictionary_create()` to create a dictionary. -Use `dictionary_destroy()` to destroy a dictionary. When destroyed, a dictionary frees all the memory it has allocated on its own. This can be complemented by the registration of a deletion callback function that can be called upon deletion of each item in the dictionary, which may free additional resources. +Use `dictionary_destroy()` to destroy a dictionary. When destroyed, a dictionary frees all the memory it has allocated on its own. This can be complemented by the registration of a deletion callback function that can be called upon deletion of each item in the dictionary, which may free additional resources linked to it. ### dictionary_set() @@ -72,9 +81,7 @@ This call is used to: - **add** an item to the dictionary. - **reset** the value of an existing item in the dictionary. -If **resetting** is not desired, add `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` to the flags when creating the dictionary. In this case, `dictionary_set()` will return the value of the original item found in the dictionary instead of resetting it and the value passed to the call will be ignored. Optionally a conflict callback function can be registered, to manipulate (probably merge or extend) the original value, based on the new value attempted to be added to the dictionary. - -For **multi-threaded** operation, the `dictionary_set()` calls get an exclusive write lock on the dictionary. +If **resetting** is not desired, add `DICT_OPTION_DONT_OVERWRITE_VALUE` to the flags when creating the dictionary. In this case, `dictionary_set()` will return the value of the original item found in the dictionary instead of resetting it and the value passed to the call will be ignored. Optionally a conflict callback function can be registered, to manipulate (probably merge or extend) the original value, based on the new value attempted to be added to the dictionary. The format is: @@ -87,17 +94,15 @@ Where: * `dict` is a pointer to the dictionary previously created. * `name` is a pointer to a string to be used as the key of this item. The name must not be `NULL` and must not be an empty string `""`. * `value` is a pointer to the value associated with this item. In **clone** mode, if `value` is `NULL`, a new memory allocation will be made of `value_len` size and will be initialized to zero. -* `value_len` is the size of the `value` data. If `value_len` is zero, no allocation will be done and the dictionary item will permanently have the `NULL` value. - -> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary in write mode. It should never be called without an active lock on the dictionary, which can only be acquired while traversing. +* `value_len` is the size of the `value` data in bytes. If `value_len` is zero, no allocation will be done and the dictionary item will permanently have the `NULL` value. ### dictionary_get() -This call is used to get the value of an item, given its name. It utilizes the `JudyHS` hash table for making the lookup. +This call is used to get the `value` of an item, given its `name`. It utilizes the hash table (index) for making the lookup. -For **multi-threaded** operation, the `dictionary_get()` call gets a shared read lock on the dictionary. +For **multi-threaded** operation, the `dictionary_get()` call gets a shared read lock on the index lock (multiple readers are allowed). The linked-list lock is not used. -In clone mode, the value returned is not guaranteed to be valid, as any other thread may delete the item from the dictionary at any time. To ensure the value will be available, use `dictionary_get_and_acquire_item()`, which uses a reference counter to defer deletes until the item is released. +In clone mode, the value returned is not guaranteed to be valid, as any other thread may delete the item from the dictionary at any time. To ensure the value will be available, use `dictionary_get_and_acquire_item()`, which uses a reference counter to defer deletes until the item is released with `dictionary_acquired_item_release()`. The format is: @@ -110,16 +115,12 @@ Where: * `dict` is a pointer to the dictionary previously created. * `name` is a pointer to a string to be used as the key of this item. The name must not be `NULL` and must not be an empty string `""`. -> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary. It should never be called without an active lock on the dictionary, which can only be acquired while traversing. - ### dictionary_del() This call is used to delete an item from the dictionary, given its name. If there is a deletion callback registered to the dictionary (`dictionary_register_delete_callback()`), it is called prior to the actual deletion of the item. -For **multi-threaded** operation, the `dictionary_del()` calls get an exclusive write lock on the dictionary. - The format is: ```c @@ -131,11 +132,9 @@ Where: * `dict` is a pointer to the dictionary previously created. * `name` is a pointer to a string to be used as the key of this item. The name must not be `NULL` and must not be an empty string `""`. -> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary, to delete the current item. It should never be called without an active lock on the dictionary, which can only be acquired while traversing. - ### dictionary_get_and_acquire_item() -This call can be used the search and get a dictionary item, while ensuring that it will be available for use, until `dictionary_acquired_item_release()` is called. +This call can be used to search and acquire a dictionary item, while ensuring that it will be available for use, until `dictionary_acquired_item_release()` is called. This call **does not return the value** of the dictionary item. It returns an internal pointer to a structure that maintains the reference counter used to protect the actual value. To get the value of the item (the same value as returned by `dictionary_get()`), the function `dictionary_acquired_item_value()` has to be called. @@ -143,13 +142,13 @@ Example: ```c // create the dictionary -DICTIONARY *dict = dictionary_create(DICTIONARY_FLAGS_NONE); +DICTIONARY *dict = dictionary_create(DICT_OPTION_NONE); // add an item to it dictionary_set(dict, "name", "value", 6); // find the item we added and acquire it -void *item = dictionary_get_and_acquire_item(dict, "name"); +const DICTIONARY_ITEM *item = dictionary_get_and_acquire_item(dict, "name"); // extract its value char *value = (char *)dictionary_acquired_item_value(dict, item); @@ -164,7 +163,7 @@ dictionary_acquired_item_release(dict, item); dictionary_destroy(dict); ``` -When items are acquired, a reference counter is maintained to keep track of how many users exist for it. If an item with a non-zero number of users is deleted, it is removed from the index, it can be added again to the index (without conflict), and although it exists in the linked-list, it is not offered during traversal. Garbage collection to actually delete the item happens every time a write-locked dictionary is unlocked (just before the unlock) and items are deleted only if no users are using them. +When items are acquired, a reference counter is maintained to keep track of how many users exist for it. If an item with a non-zero number of users is deleted, it is removed from the index, it can be added again to the index (without conflict), and although it exists in the linked-list, it is not offered during traversal. Garbage collection to actually delete the item happens every time another item is added or removed from the linked-list and items are deleted only if no users are using them. If any item is still acquired when the dictionary is destroyed, the destruction of the dictionary is also deferred until all the acquired items are released. When the dictionary is destroyed like that, all operations on the dictionary fail (traversals do not traverse, insertions do not insert, deletions do not delete, searches do not find any items, etc). Once the last item in the dictionary is released, the dictionary is automatically destroyed too. @@ -176,20 +175,16 @@ Dictionaries offer 3 ways to traverse the entire dictionary: - **sorted walkthrough**, which first sorts the dictionary and then call a callback function for every item. - **foreach**, a way to traverse the dictionary with a for-next loop. -All these methods are available in **read** or **write** mode. In **read** mode only lookups are allowed to the dictionary. In **write** lookups but also insertions and deletions are allowed. - -While traversing the dictionary with any of these methods, all calls to the dictionary have to use the `_unsafe` versions of the function calls, otherwise deadlocks may arise. - -> **IMPORTANT**<br/>The dictionary itself does not check to ensure that a user is actually using the right lock mode (read or write) while traversing the dictionary for each of the unsafe calls. +All these methods are available in **read**, **write**, or **reentrant** mode. In **read** mode only lookups are allowed to the dictionary. In **write** lookups but also insertions and deletions are allowed, and in **reentrant** mode the dictionary is unlocked outside dictionary code. ### walkthrough (callback) There are 4 calls: -- `dictionary_walkthrough_read()` and `dictionary_sorted_walkthrough_read()` that acquire a shared read lock, and they call a callback function for every item of the dictionary. The callback function may use the unsafe versions of the `dictionary_get()` calls to lookup other items in the dictionary, but it should not attempt to add or remove items to/from the dictionary. -- `dictionary_walkthrough_write()` and `dictionary_sorted_walkthrough_write()` that acquire an exclusive write lock, and they call a callback function for every item of the dictionary. This is to be used when items need to be added to or removed from the dictionary. The `write` versions can be used to delete any or all the items from the dictionary, including the currently working one. For the `sorted` version, all items in the dictionary maintain a reference counter, so all deletions are deferred until the sorted walkthrough finishes.** +- `dictionary_walkthrough_read()` and `dictionary_sorted_walkthrough_read()` acquire a shared read lock on the linked-list, and they call a callback function for every item of the dictionary. +- `dictionary_walkthrough_write()` and `dictionary_sorted_walkthrough_write()` acquire a write lock on the linked-list, and they call a callback function for every item of the dictionary. This is to be used when items need to be added to or removed from the dictionary. The `write` versions can be used to delete any or all the items from the dictionary, including the currently working one. For the `sorted` version, all items in the dictionary maintain a reference counter, so all deletions are deferred until the sorted walkthrough finishes. -The non sorted versions traverse the items in the same order they have been added to the dictionary (or the reverse order if the flag `DICTIONARY_FLAG_ADD_IN_FRONT` is set during dictionary creation). The sorted versions sort alphabetically the items based on their name, and then they traverse them in the sorted order. +The non sorted versions traverse the items in the same order they have been added to the dictionary (or the reverse order if the flag `DICT_OPTION_ADD_IN_FRONT` is set during dictionary creation). The sorted versions sort alphabetically the items based on their name, and then they traverse them in the sorted order. The callback function returns an `int`. If this value is negative, traversal of the dictionary is stopped immediately and the negative value is returned to the caller. If the returned value of all callback calls is zero or positive, the walkthrough functions return the sum of the return values of all callbacks. So, if you are just interested to know how many items fall into some condition, write a callback function that returns 1 when the item satisfies that condition and 0 when it does not and the walkthrough function will return how many tested positive. @@ -198,48 +193,39 @@ The callback function returns an `int`. If this value is negative, traversal of The following is a snippet of such a loop: ```c -MY_ITEM *item; -dfe_start_read(dict, item) { - printf("hey, I got an item named '%s' with value ptr %08X", item_name, item); +MY_STRUCTURE *x; +dfe_start_read(dict, x) { + printf("hey, I got an item named '%s' with value ptr %08X", x_dfe.name, x); } -dfe_done(item); +dfe_done(x); ``` -The `item` parameter gives the name of the pointer to be used while iterating the items. Any name is accepted. +The `x` parameter gives the name of the pointer to be used while iterating the items. Any name is accepted. `x` points to the `value` of the item in the dictionary. -The `item_name` is a variable that is automatically created, by concatenating whatever is given as `item` and `_name`. So, if you call `dfe_start_read(dict, myvar)`, the name will be `myvar_name`. +The `x_dfe.name` is a variable that is automatically created, by concatenating whatever is given as `x` and `_dfe`. It is an object and it has a few members, including `x_dfe.counter` that counts the iterations made so far, `x_dfe.item` that provides the acquired item from the dictionary and which can be used to pass it over for further processing, etc. Check the header file for more info. So, if you call `dfe_start_read(dict, myvar)`, the name will be `myvar_dfe`. Both `dfe_start_read(dict, item)` and `dfe_done(item)` are together inside a `do { ... } while(0)` loop, so that the following will work: ```c MY_ITEM *item; -if(x = 1) +if(a = 1) // do { - dfe_start_read(dict, item) - printf("hey, I got an item named '%s' with value ptr %08X", item_name, item); - dfe_done(item); + dfe_start_read(dict, x) + printf("hey, I got an item named '%s' with value ptr %08X", x_dfe.name, x); + dfe_done(x); // } while(0); else something else; ``` -In the above, the `if(x == 1)` condition will work as expected. It will do the foreach loop when x is 1, otherwise it will run `something else`. +In the above, the `if(a == 1)` condition will work as expected. It will do the foreach loop when a is 1, otherwise it will run `something else`. There are 2 versions of `dfe_start`: -- `dfe_start_read()` that acquires a shared read lock to the dictionary. -- `dfe_start_write()` that acquires an exclusive write lock to the dictionary. +- `dfe_start_read()` that acquires a shared read linked-list lock to the dictionary. +- `dfe_start_write()` that acquires an exclusive write linked-list lock to the dictionary. -While in the loop, depending on the read or write versions of `dfe_start`, the caller may lookup or manipulate the dictionary using the unsafe functions. The rules are the same with the unsorted walkthrough callback functions. +While in the loop, depending on the read or write versions of `dfe_start`, the caller may lookup or manipulate the dictionary. The rules are the same with the unsorted walkthrough callback functions. PS: DFE is Dictionary For Each. - -## special multi-threaded lockless case - -Since the dictionary uses a hash table and a double linked list, if the contract between 2 threads is for one to use the hash table functions only (`set`, `get` - but no `del`) and the other to use the traversal ones only, the dictionary allows concurrent use without locks. - -This is currently used in statsd: - -- the data collection thread uses only `get` and `set`. It never uses `del`. New items are added at the front of the linked list (`DICTIONARY_FLAG_ADD_IN_FRONT`). -- the flushing thread is only traversing the dictionary up to the point it last traversed it (it uses a flag for that to know where it stopped last time). It never uses `get`, `set` or `del`. diff --git a/libnetdata/dictionary/dictionary.c b/libnetdata/dictionary/dictionary.c index c1325ecb5..f03da25ab 100644 --- a/libnetdata/dictionary/dictionary.c +++ b/libnetdata/dictionary/dictionary.c @@ -1,64 +1,137 @@ // SPDX-License-Identifier: GPL-3.0-or-later -// NOT TO BE USED BY USERS -#define DICTIONARY_FLAG_EXCLUSIVE_ACCESS (1 << 29) // there is only one thread accessing the dictionary -#define DICTIONARY_FLAG_DESTROYED (1 << 30) // this dictionary has been destroyed -#define DICTIONARY_FLAG_DEFER_ALL_DELETIONS (1 << 31) // defer all deletions of items in the dictionary - -// our reserved flags that cannot be set by users -#define DICTIONARY_FLAGS_RESERVED (DICTIONARY_FLAG_EXCLUSIVE_ACCESS|DICTIONARY_FLAG_DESTROYED|DICTIONARY_FLAG_DEFER_ALL_DELETIONS) - -typedef struct dictionary DICTIONARY; #define DICTIONARY_INTERNALS #include "../libnetdata.h" +#include <Judy.h> -#ifndef ENABLE_DBENGINE -#define DICTIONARY_WITH_AVL -#warning Compiling DICTIONARY with an AVL index -#else -#define DICTIONARY_WITH_JUDYHS -#endif +// runtime flags of the dictionary - must be checked with atomics +typedef enum { + DICT_FLAG_NONE = 0, + DICT_FLAG_DESTROYED = (1 << 0), // this dictionary has been destroyed +} DICT_FLAGS; -#ifdef DICTIONARY_WITH_JUDYHS -#include <Judy.h> -#endif +#define dict_flag_check(dict, flag) (__atomic_load_n(&((dict)->flags), __ATOMIC_SEQ_CST) & (flag)) +#define dict_flag_set(dict, flag) __atomic_or_fetch(&((dict)->flags), flag, __ATOMIC_SEQ_CST) +#define dict_flag_clear(dict, flag) __atomic_and_fetch(&((dict)->flags), ~(flag), __ATOMIC_SEQ_CST) + +// flags macros +#define is_dictionary_destroyed(dict) dict_flag_check(dict, DICT_FLAG_DESTROYED) + +// configuration options macros +#define is_dictionary_single_threaded(dict) ((dict)->options & DICT_OPTION_SINGLE_THREADED) +#define is_view_dictionary(dict) ((dict)->master) +#define is_master_dictionary(dict) (!is_view_dictionary(dict)) + +typedef enum item_options { + ITEM_OPTION_NONE = 0, + ITEM_OPTION_ALLOCATED_NAME = (1 << 0), // the name pointer is a STRING + + // IMPORTANT: This is 1-bit - to add more change ITEM_OPTIONS_BITS +} ITEM_OPTIONS; + +typedef enum item_flags { + ITEM_FLAG_NONE = 0, + ITEM_FLAG_DELETED = (1 << 0), // this item is marked deleted, so it is not available for traversal (deleted from the index too) + ITEM_FLAG_BEING_CREATED = (1 << 1), // this item is currently being created - this flag is removed when construction finishes + + // IMPORTANT: This is 8-bit +} ITEM_FLAGS; + +#define item_flag_check(item, flag) (__atomic_load_n(&((item)->flags), __ATOMIC_SEQ_CST) & (flag)) +#define item_flag_set(item, flag) __atomic_or_fetch(&((item)->flags), flag, __ATOMIC_SEQ_CST) +#define item_flag_clear(item, flag) __atomic_and_fetch(&((item)->flags), ~(flag), __ATOMIC_SEQ_CST) + +#define item_shared_flag_check(item, flag) (__atomic_load_n(&((item)->shared->flags), __ATOMIC_SEQ_CST) & (flag)) +#define item_shared_flag_set(item, flag) __atomic_or_fetch(&((item)->shared->flags), flag, __ATOMIC_SEQ_CST) +#define item_shared_flag_clear(item, flag) __atomic_and_fetch(&((item)->shared->flags), ~(flag), __ATOMIC_SEQ_CST) -typedef enum name_value_flags { - NAME_VALUE_FLAG_NONE = 0, - NAME_VALUE_FLAG_NAME_IS_ALLOCATED = (1 << 0), // the name pointer is a STRING - NAME_VALUE_FLAG_DELETED = (1 << 1), // this item is deleted, so it is not available for traversal - NAME_VALUE_FLAG_NEW_OR_UPDATED = (1 << 2), // this item is new or just updated (used by the react callback) +#define REFCOUNT_DELETING (-100) + +#define ITEM_FLAGS_TYPE uint8_t +#define KEY_LEN_TYPE uint32_t +#define VALUE_LEN_TYPE uint32_t + +#define ITEM_OPTIONS_BITS 1 +#define KEY_LEN_BITS ((sizeof(KEY_LEN_TYPE) * 8) - (sizeof(ITEM_FLAGS_TYPE) * 8) - ITEM_OPTIONS_BITS) +#define KEY_LEN_MAX ((1 << KEY_LEN_BITS) - 1) + +#define VALUE_LEN_BITS ((sizeof(VALUE_LEN_TYPE) * 8) - (sizeof(ITEM_FLAGS_TYPE) * 8)) +#define VALUE_LEN_MAX ((1 << VALUE_LEN_BITS) - 1) - // IMPORTANT: IF YOU ADD ANOTHER FLAG, YOU NEED TO ALLOCATE ANOTHER BIT TO FLAGS IN NAME_VALUE !!! -} NAME_VALUE_FLAGS; /* * Every item in the dictionary has the following structure. */ -typedef struct name_value { -#ifdef DICTIONARY_WITH_AVL - avl_t avl_node; -#endif +typedef int32_t REFCOUNT; + +typedef struct dictionary_item_shared { + void *value; // the value of the dictionary item + + // the order of the following items is important! + // The total of their storage should be 64-bits + + REFCOUNT links; // how many links this item has + VALUE_LEN_TYPE value_len:VALUE_LEN_BITS; // the size of the value + ITEM_FLAGS_TYPE flags; // shared flags +} DICTIONARY_ITEM_SHARED; +struct dictionary_item { #ifdef NETDATA_INTERNAL_CHECKS DICTIONARY *dict; + pid_t creator_pid; + pid_t deleter_pid; + pid_t ll_adder_pid; + pid_t ll_remover_pid; #endif - struct name_value *next; // a double linked list to allow fast insertions and deletions - struct name_value *prev; + DICTIONARY_ITEM_SHARED *shared; - uint32_t refcount; // the reference counter - uint32_t value_len:29; // the size of the value (assumed binary) - uint8_t flags:3; // the flags for this item + struct dictionary_item *next; // a double linked list to allow fast insertions and deletions + struct dictionary_item *prev; - void *value; // the value of the dictionary item union { - STRING *string_name; // the name of the dictionary item - char *caller_name; // the user supplied string pointer + STRING *string_name; // the name of the dictionary item + char *caller_name; // the user supplied string pointer +// void *key_ptr; // binary key pointer }; -} NAME_VALUE; + + // the order of the following items is important! + // The total of their storage should be 64-bits + + REFCOUNT refcount; // the private reference counter + + KEY_LEN_TYPE key_len:KEY_LEN_BITS; // the size of key indexed (for strings, including the null terminator) + // this is (2^23 - 1) = 8.388.607 bytes max key length. + + ITEM_OPTIONS options:ITEM_OPTIONS_BITS; // permanent configuration options + // (no atomic operations on this - they never change) + + ITEM_FLAGS_TYPE flags; // runtime changing flags for this item (atomic operations on this) + // cannot be a bit field because of atomics. +}; + +struct dictionary_hooks { + REFCOUNT links; + usec_t last_master_deletion_us; + + void (*ins_callback)(const DICTIONARY_ITEM *item, void *value, void *data); + void *ins_callback_data; + + bool (*conflict_callback)(const DICTIONARY_ITEM *item, void *old_value, void *new_value, void *data); + void *conflict_callback_data; + + void (*react_callback)(const DICTIONARY_ITEM *item, void *value, void *data); + void *react_callback_data; + + void (*del_callback)(const DICTIONARY_ITEM *item, void *value, void *data); + void *del_callback_data; +}; + +struct dictionary_stats dictionary_stats_category_other = { + .name = "other", +}; struct dictionary { #ifdef NETDATA_INTERNAL_CHECKS @@ -67,331 +140,685 @@ struct dictionary { size_t creation_line; #endif - DICTIONARY_FLAGS flags; // the flags of the dictionary + usec_t last_gc_run_us; + DICT_OPTIONS options; // the configuration flags of the dictionary (they never change - no atomics) + DICT_FLAGS flags; // run time flags for the dictionary (they change all the time - atomics needed) + + struct { // support for multiple indexing engines + Pvoid_t JudyHSArray; // the hash table + netdata_rwlock_t rwlock; // protect the index + } index; + + struct { + DICTIONARY_ITEM *list; // the double linked list of all items in the dictionary + netdata_rwlock_t rwlock; // protect the linked-list + pid_t writer_pid; // the gettid() of the writer + size_t writer_depth; // nesting of write locks + } items; + + struct dictionary_hooks *hooks; // pointer to external function callbacks to be called at certain points + struct dictionary_stats *stats; // statistics data, when DICT_OPTION_STATS is set - NAME_VALUE *first_item; // the double linked list base pointers - NAME_VALUE *last_item; + DICTIONARY *master; // the master dictionary + DICTIONARY *next; // linked list for delayed destruction (garbage collection of whole dictionaries) -#ifdef DICTIONARY_WITH_AVL - avl_tree_type values_index; - NAME_VALUE *hash_base; - void *(*get_thread_static_name_value)(const char *name); + size_t version; // the current version of the dictionary + // it is incremented when: + // - item added + // - item removed + // - item value reset + // - conflict callback returns true + // - function dictionary_version_increment() is called + + long int entries; // how many items are currently in the index (the linked list may have more) + long int referenced_items; // how many items of the dictionary are currently being used by 3rd parties + long int pending_deletion_items; // how many items of the dictionary have been deleted, but have not been removed yet + +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_t global_pointer_registry_mutex; + Pvoid_t global_pointer_registry; #endif +}; + +// forward definitions of functions used in reverse order in the code +static void garbage_collect_pending_deletes(DICTIONARY *dict); +static inline void item_linked_list_remove(DICTIONARY *dict, DICTIONARY_ITEM *item); +static size_t dict_item_free_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item); +static inline const char *item_get_name(const DICTIONARY_ITEM *item); +static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *item); +static void item_release(DICTIONARY *dict, DICTIONARY_ITEM *item); +static bool dict_item_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item); + +#define RC_ITEM_OK ( 0) +#define RC_ITEM_MARKED_FOR_DELETION (-1) // the item is marked for deletion +#define RC_ITEM_IS_CURRENTLY_BEING_DELETED (-2) // the item is currently being deleted +#define RC_ITEM_IS_CURRENTLY_BEING_CREATED (-3) // the item is currently being deleted +#define RC_ITEM_IS_REFERENCED (-4) // the item is currently referenced +#define item_check_and_acquire(dict, item) (item_check_and_acquire_advanced(dict, item, false) == RC_ITEM_OK) +static int item_check_and_acquire_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item, bool having_index_lock); +#define item_is_not_referenced_and_can_be_removed(dict, item) (item_is_not_referenced_and_can_be_removed_advanced(dict, item) == RC_ITEM_OK) +static inline int item_is_not_referenced_and_can_be_removed_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item); + +// ---------------------------------------------------------------------------- +// validate each pointer is indexed once - internal checks only -#ifdef DICTIONARY_WITH_JUDYHS - Pvoid_t JudyHSArray; // the hash table +static inline void pointer_index_init(DICTIONARY *dict __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_init(&dict->global_pointer_registry_mutex); +#else + ; #endif +} - netdata_rwlock_t rwlock; // the r/w lock when DICTIONARY_FLAG_SINGLE_THREADED is not set +static inline void pointer_destroy_index(DICTIONARY *dict __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_lock(&dict->global_pointer_registry_mutex); + JudyHSFreeArray(&dict->global_pointer_registry, PJE0); + netdata_mutex_unlock(&dict->global_pointer_registry_mutex); +#else + ; +#endif +} +static inline void pointer_add(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_lock(&dict->global_pointer_registry_mutex); + Pvoid_t *PValue = JudyHSIns(&dict->global_pointer_registry, &item, sizeof(void *), PJE0); + if(*PValue != NULL) + fatal("pointer already exists in registry"); + *PValue = item; + netdata_mutex_unlock(&dict->global_pointer_registry_mutex); +#else + ; +#endif +} - void (*ins_callback)(const char *name, void *value, void *data); - void *ins_callback_data; +static inline void pointer_check(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_lock(&dict->global_pointer_registry_mutex); + Pvoid_t *PValue = JudyHSGet(dict->global_pointer_registry, &item, sizeof(void *)); + if(PValue == NULL) + fatal("pointer is not found in registry"); + netdata_mutex_unlock(&dict->global_pointer_registry_mutex); +#else + ; +#endif +} - void (*react_callback)(const char *name, void *value, void *data); - void *react_callback_data; +static inline void pointer_del(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_lock(&dict->global_pointer_registry_mutex); + int ret = JudyHSDel(&dict->global_pointer_registry, &item, sizeof(void *), PJE0); + if(!ret) + fatal("pointer to be deleted does not exist in registry"); + netdata_mutex_unlock(&dict->global_pointer_registry_mutex); +#else + ; +#endif +} - void (*del_callback)(const char *name, void *value, void *data); - void *del_callback_data; +// ---------------------------------------------------------------------------- +// memory statistics - void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data); - void *conflict_callback_data; +static inline void DICTIONARY_STATS_PLUS_MEMORY(DICTIONARY *dict, size_t key_size, size_t item_size, size_t value_size) { + if(key_size) + __atomic_fetch_add(&dict->stats->memory.indexed, (long)key_size, __ATOMIC_RELAXED); - size_t version; // the current version of the dictionary - size_t inserts; // how many index insertions have been performed - size_t deletes; // how many index deletions have been performed - size_t searches; // how many index searches have been performed - size_t resets; // how many times items have reset their values - size_t walkthroughs; // how many walkthroughs have been done - long int memory; // how much memory the dictionary has currently allocated - long int entries; // how many items are currently in the index (the linked list may have more) - long int referenced_items; // how many items of the dictionary are currently being used by 3rd parties - long int pending_deletion_items; // how many items of the dictionary have been deleted, but have not been removed yet - int readers; // how many readers are currently using the dictionary - int writers; // how many writers are currently using the dictionary - - size_t scratchpad_size; // the size of the scratchpad in bytes - uint8_t scratchpad[]; // variable size scratchpad requested by the caller -}; + if(item_size) + __atomic_fetch_add(&dict->stats->memory.dict, (long)item_size, __ATOMIC_RELAXED); + + if(value_size) + __atomic_fetch_add(&dict->stats->memory.values, (long)value_size, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_MINUS_MEMORY(DICTIONARY *dict, size_t key_size, size_t item_size, size_t value_size) { + if(key_size) + __atomic_fetch_sub(&dict->stats->memory.indexed, (long)key_size, __ATOMIC_RELAXED); -static inline void linkedlist_namevalue_unlink_unsafe(DICTIONARY *dict, NAME_VALUE *nv); -static size_t namevalue_destroy_unsafe(DICTIONARY *dict, NAME_VALUE *nv); -static inline const char *namevalue_get_name(NAME_VALUE *nv); + if(item_size) + __atomic_fetch_sub(&dict->stats->memory.dict, (long)item_size, __ATOMIC_RELAXED); + + if(value_size) + __atomic_fetch_sub(&dict->stats->memory.values, (long)value_size, __ATOMIC_RELAXED); +} // ---------------------------------------------------------------------------- // callbacks registration -void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const char *name, void *value, void *data), void *data) { - dict->ins_callback = ins_callback; - dict->ins_callback_data = data; -} +static inline void dictionary_hooks_allocate(DICTIONARY *dict) { + if(dict->hooks) return; -void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const char *name, void *value, void *data), void *data) { - dict->del_callback = del_callback; - dict->del_callback_data = data; -} + dict->hooks = callocz(1, sizeof(struct dictionary_hooks)); + dict->hooks->links = 1; -void dictionary_register_conflict_callback(DICTIONARY *dict, void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data), void *data) { - dict->conflict_callback = conflict_callback; - dict->conflict_callback_data = data; + DICTIONARY_STATS_PLUS_MEMORY(dict, 0, sizeof(struct dictionary_hooks), 0); } -void dictionary_register_react_callback(DICTIONARY *dict, void (*react_callback)(const char *name, void *value, void *data), void *data) { - dict->react_callback = react_callback; - dict->react_callback_data = data; +static inline size_t dictionary_hooks_free(DICTIONARY *dict) { + if(!dict->hooks) return 0; + + REFCOUNT links = __atomic_sub_fetch(&dict->hooks->links, 1, __ATOMIC_SEQ_CST); + if(links == 0) { + freez(dict->hooks); + dict->hooks = NULL; + + DICTIONARY_STATS_MINUS_MEMORY(dict, 0, sizeof(struct dictionary_hooks), 0); + return sizeof(struct dictionary_hooks); + } + + return 0; } -// ---------------------------------------------------------------------------- -// dictionary statistics maintenance +void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); -long int dictionary_stats_allocated_memory(DICTIONARY *dict) { - return dict->memory; + dictionary_hooks_allocate(dict); + dict->hooks->ins_callback = ins_callback; + dict->hooks->ins_callback_data = data; } -long int dictionary_stats_entries(DICTIONARY *dict) { - return dict->entries; + +void dictionary_register_conflict_callback(DICTIONARY *dict, bool (*conflict_callback)(const DICTIONARY_ITEM *item, void *old_value, void *new_value, void *data), void *data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + internal_error(!(dict->options & DICT_OPTION_DONT_OVERWRITE_VALUE), "DICTIONARY: registering conflict callback without DICT_OPTION_DONT_OVERWRITE_VALUE"); + dict->options |= DICT_OPTION_DONT_OVERWRITE_VALUE; + + dictionary_hooks_allocate(dict); + dict->hooks->conflict_callback = conflict_callback; + dict->hooks->conflict_callback_data = data; } -size_t dictionary_stats_version(DICTIONARY *dict) { - return dict->version; + +void dictionary_register_react_callback(DICTIONARY *dict, void (*react_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + dictionary_hooks_allocate(dict); + dict->hooks->react_callback = react_callback; + dict->hooks->react_callback_data = data; } -size_t dictionary_stats_searches(DICTIONARY *dict) { - return dict->searches; + +void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + dictionary_hooks_allocate(dict); + dict->hooks->del_callback = del_callback; + dict->hooks->del_callback_data = data; } -size_t dictionary_stats_inserts(DICTIONARY *dict) { - return dict->inserts; + +// ---------------------------------------------------------------------------- +// dictionary statistics API + +size_t dictionary_version(DICTIONARY *dict) { + if(unlikely(!dict)) return 0; + + // this is required for views to return the right number + garbage_collect_pending_deletes(dict); + + return __atomic_load_n(&dict->version, __ATOMIC_SEQ_CST); } -size_t dictionary_stats_deletes(DICTIONARY *dict) { - return dict->deletes; +size_t dictionary_entries(DICTIONARY *dict) { + if(unlikely(!dict)) return 0; + + // this is required for views to return the right number + garbage_collect_pending_deletes(dict); + + long int entries = __atomic_load_n(&dict->entries, __ATOMIC_SEQ_CST); + if(entries < 0) + fatal("DICTIONARY: entries is negative: %ld", entries); + + return entries; } -size_t dictionary_stats_resets(DICTIONARY *dict) { - return dict->resets; +size_t dictionary_referenced_items(DICTIONARY *dict) { + if(unlikely(!dict)) return 0; + + long int referenced_items = __atomic_load_n(&dict->referenced_items, __ATOMIC_SEQ_CST); + if(referenced_items < 0) + fatal("DICTIONARY: referenced items is negative: %ld", referenced_items); + + return referenced_items; } -size_t dictionary_stats_walkthroughs(DICTIONARY *dict) { - return dict->walkthroughs; + +long int dictionary_stats_for_registry(DICTIONARY *dict) { + if(unlikely(!dict)) return 0; + return (dict->stats->memory.indexed + dict->stats->memory.dict); } -size_t dictionary_stats_referenced_items(DICTIONARY *dict) { - return __atomic_load_n(&dict->referenced_items, __ATOMIC_SEQ_CST); +void dictionary_version_increment(DICTIONARY *dict) { + __atomic_fetch_add(&dict->version, 1, __ATOMIC_SEQ_CST); } +// ---------------------------------------------------------------------------- +// internal statistics API + static inline void DICTIONARY_STATS_SEARCHES_PLUS1(DICTIONARY *dict) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - dict->searches++; - } - else { - __atomic_fetch_add(&dict->searches, 1, __ATOMIC_RELAXED); - } + __atomic_fetch_add(&dict->stats->ops.searches, 1, __ATOMIC_RELAXED); } -static inline void DICTIONARY_STATS_ENTRIES_PLUS1(DICTIONARY *dict, size_t size) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { +static inline void DICTIONARY_ENTRIES_PLUS1(DICTIONARY *dict) { + // statistics + __atomic_fetch_add(&dict->stats->items.entries, 1, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->stats->items.referenced, 1, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->stats->ops.inserts, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) { dict->version++; - dict->inserts++; dict->entries++; - dict->memory += (long)size; + dict->referenced_items++; + } else { __atomic_fetch_add(&dict->version, 1, __ATOMIC_SEQ_CST); - __atomic_fetch_add(&dict->inserts, 1, __ATOMIC_RELAXED); - __atomic_fetch_add(&dict->entries, 1, __ATOMIC_RELAXED); - __atomic_fetch_add(&dict->memory, (long)size, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->entries, 1, __ATOMIC_SEQ_CST); + __atomic_fetch_add(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); } } -static inline void DICTIONARY_STATS_ENTRIES_MINUS1(DICTIONARY *dict) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { +static inline void DICTIONARY_ENTRIES_MINUS1(DICTIONARY *dict) { + // statistics + __atomic_fetch_add(&dict->stats->ops.deletes, 1, __ATOMIC_RELAXED); + __atomic_fetch_sub(&dict->stats->items.entries, 1, __ATOMIC_RELAXED); + + size_t entries; (void)entries; + if(unlikely(is_dictionary_single_threaded(dict))) { dict->version++; - dict->deletes++; - dict->entries--; + entries = dict->entries++; } else { __atomic_fetch_add(&dict->version, 1, __ATOMIC_SEQ_CST); - __atomic_fetch_add(&dict->deletes, 1, __ATOMIC_RELAXED); - __atomic_fetch_sub(&dict->entries, 1, __ATOMIC_RELAXED); - } -} -static inline void DICTIONARY_STATS_ENTRIES_MINUS_MEMORY(DICTIONARY *dict, size_t size) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - dict->memory -= (long)size; - } - else { - __atomic_fetch_sub(&dict->memory, (long)size, __ATOMIC_RELAXED); + entries = __atomic_fetch_sub(&dict->entries, 1, __ATOMIC_SEQ_CST); } + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(entries == 0)) + fatal("DICT: negative number of entries in dictionary created from %s() (%zu@%s)", + dict->creation_function, + dict->creation_line, + dict->creation_file); +#endif } -static inline void DICTIONARY_STATS_VALUE_RESETS_PLUS1(DICTIONARY *dict, size_t oldsize, size_t newsize) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { +static inline void DICTIONARY_VALUE_RESETS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->ops.resets, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) dict->version++; - dict->resets++; - dict->memory += (long)newsize; - dict->memory -= (long)oldsize; - } - else { + else __atomic_fetch_add(&dict->version, 1, __ATOMIC_SEQ_CST); - __atomic_fetch_add(&dict->resets, 1, __ATOMIC_RELAXED); - __atomic_fetch_add(&dict->memory, (long)newsize, __ATOMIC_RELAXED); - __atomic_fetch_sub(&dict->memory, (long)oldsize, __ATOMIC_RELAXED); - } } - +static inline void DICTIONARY_STATS_TRAVERSALS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->ops.traversals, 1, __ATOMIC_RELAXED); +} static inline void DICTIONARY_STATS_WALKTHROUGHS_PLUS1(DICTIONARY *dict) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - dict->walkthroughs++; - } - else { - __atomic_fetch_add(&dict->walkthroughs, 1, __ATOMIC_RELAXED); - } + __atomic_fetch_add(&dict->stats->ops.walkthroughs, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CHECK_SPINS_PLUS(DICTIONARY *dict, size_t count) { + __atomic_fetch_add(&dict->stats->spin_locks.use_spins, count, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_INSERT_SPINS_PLUS(DICTIONARY *dict, size_t count) { + __atomic_fetch_add(&dict->stats->spin_locks.insert_spins, count, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DELETE_SPINS_PLUS(DICTIONARY *dict, size_t count) { + __atomic_fetch_add(&dict->stats->spin_locks.delete_spins, count, __ATOMIC_RELAXED); } +static inline void DICTIONARY_STATS_SEARCH_IGNORES_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->spin_locks.search_spins, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CALLBACK_INSERTS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->callbacks.inserts, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CALLBACK_CONFLICTS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->callbacks.conflicts, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CALLBACK_REACTS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->callbacks.reacts, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CALLBACK_DELETES_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->callbacks.deletes, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_GARBAGE_COLLECTIONS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->ops.garbage_collections, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_CREATIONS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->dictionaries.active, 1, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->stats->ops.creations, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_DESTRUCTIONS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_sub(&dict->stats->dictionaries.active, 1, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->stats->ops.destructions, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_DESTROY_QUEUED_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->dictionaries.deleted, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_DESTROY_QUEUED_MINUS1(DICTIONARY *dict) { + __atomic_fetch_sub(&dict->stats->dictionaries.deleted, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_FLUSHES_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->ops.flushes, 1, __ATOMIC_RELAXED); +} + +static inline long int DICTIONARY_REFERENCED_ITEMS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->items.referenced, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) + return ++dict->referenced_items; + else + return __atomic_add_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); +} + +static inline long int DICTIONARY_REFERENCED_ITEMS_MINUS1(DICTIONARY *dict) { + __atomic_fetch_sub(&dict->stats->items.referenced, 1, __ATOMIC_RELAXED); + + long int referenced_items; + if(unlikely(is_dictionary_single_threaded(dict))) + referenced_items = --dict->referenced_items; + else + referenced_items = __atomic_sub_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(referenced_items < 0)) + fatal("DICT: negative number of referenced items (%ld) in dictionary created from %s() (%zu@%s)", + referenced_items, + dict->creation_function, + dict->creation_line, + dict->creation_file); +#endif -static inline size_t DICTIONARY_STATS_REFERENCED_ITEMS_PLUS1(DICTIONARY *dict) { - return __atomic_add_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); + return referenced_items; } -static inline size_t DICTIONARY_STATS_REFERENCED_ITEMS_MINUS1(DICTIONARY *dict) { - return __atomic_sub_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); +static inline long int DICTIONARY_PENDING_DELETES_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->items.pending_deletion, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) + return ++dict->pending_deletion_items; + else + return __atomic_add_fetch(&dict->pending_deletion_items, 1, __ATOMIC_SEQ_CST); } -static inline size_t DICTIONARY_STATS_PENDING_DELETES_PLUS1(DICTIONARY *dict) { - return __atomic_add_fetch(&dict->pending_deletion_items, 1, __ATOMIC_SEQ_CST); +static inline long int DICTIONARY_PENDING_DELETES_MINUS1(DICTIONARY *dict) { + __atomic_fetch_sub(&dict->stats->items.pending_deletion, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) + return --dict->pending_deletion_items; + else + return __atomic_sub_fetch(&dict->pending_deletion_items, 1, __ATOMIC_SEQ_CST); } -static inline size_t DICTIONARY_STATS_PENDING_DELETES_MINUS1(DICTIONARY *dict) { - return __atomic_sub_fetch(&dict->pending_deletion_items, 1, __ATOMIC_SEQ_CST); +static inline long int DICTIONARY_PENDING_DELETES_GET(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) + return dict->pending_deletion_items; + else + return __atomic_load_n(&dict->pending_deletion_items, __ATOMIC_SEQ_CST); } -static inline size_t DICTIONARY_STATS_PENDING_DELETES_GET(DICTIONARY *dict) { - return __atomic_load_n(&dict->pending_deletion_items, __ATOMIC_SEQ_CST); +static inline REFCOUNT DICTIONARY_ITEM_REFCOUNT_GET(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(unlikely(dict && is_dictionary_single_threaded(dict))) // this is an exception, dict can be null + return item->refcount; + else + return (REFCOUNT)__atomic_load_n(&item->refcount, __ATOMIC_SEQ_CST); } -static inline int DICTIONARY_NAME_VALUE_REFCOUNT_GET(NAME_VALUE *nv) { - return __atomic_load_n(&nv->refcount, __ATOMIC_SEQ_CST); +static inline REFCOUNT DICTIONARY_ITEM_REFCOUNT_GET_SOLE(DICTIONARY_ITEM *item) { + return (REFCOUNT)__atomic_load_n(&item->refcount, __ATOMIC_SEQ_CST); } // ---------------------------------------------------------------------------- -// garbage collector -// it is called every time someone gets a write lock to the dictionary +// callbacks execution -static void garbage_collect_pending_deletes_unsafe(DICTIONARY *dict) { - if(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS)) return; +static void dictionary_execute_insert_callback(DICTIONARY *dict, DICTIONARY_ITEM *item, void *constructor_data) { + if(likely(!dict->hooks || !dict->hooks->ins_callback)) + return; - if(likely(!DICTIONARY_STATS_PENDING_DELETES_GET(dict))) return; + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); - NAME_VALUE *nv = dict->first_item; - while(nv) { - if((nv->flags & NAME_VALUE_FLAG_DELETED) && DICTIONARY_NAME_VALUE_REFCOUNT_GET(nv) == 0) { - NAME_VALUE *nv_next = nv->next; + internal_error(false, + "DICTIONARY: Running insert callback on item '%s' of dictionary created from %s() %zu@%s.", + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); - linkedlist_namevalue_unlink_unsafe(dict, nv); - namevalue_destroy_unsafe(dict, nv); + DICTIONARY_STATS_CALLBACK_INSERTS_PLUS1(dict); + dict->hooks->ins_callback(item, item->shared->value, constructor_data?constructor_data:dict->hooks->ins_callback_data); +} - size_t pending = DICTIONARY_STATS_PENDING_DELETES_MINUS1(dict); - if(!pending) break; +static bool dictionary_execute_conflict_callback(DICTIONARY *dict, DICTIONARY_ITEM *item, void *new_value, void *constructor_data) { + if(likely(!dict->hooks || !dict->hooks->conflict_callback)) + return false; - nv = nv_next; - } - else - nv = nv->next; - } + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + internal_error(false, + "DICTIONARY: Running conflict callback on item '%s' of dictionary created from %s() %zu@%s.", + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + DICTIONARY_STATS_CALLBACK_CONFLICTS_PLUS1(dict); + return dict->hooks->conflict_callback( + item, item->shared->value, new_value, + constructor_data ? constructor_data : dict->hooks->conflict_callback_data); } -// ---------------------------------------------------------------------------- -// dictionary locks +static void dictionary_execute_react_callback(DICTIONARY *dict, DICTIONARY_ITEM *item, void *constructor_data) { + if(likely(!dict->hooks || !dict->hooks->react_callback)) + return; + + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + internal_error(false, + "DICTIONARY: Running react callback on item '%s' of dictionary created from %s() %zu@%s.", + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + DICTIONARY_STATS_CALLBACK_REACTS_PLUS1(dict); + dict->hooks->react_callback(item, item->shared->value, + constructor_data?constructor_data:dict->hooks->react_callback_data); +} -static inline size_t dictionary_lock_init(DICTIONARY *dict) { - if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { - netdata_rwlock_init(&dict->rwlock); +static void dictionary_execute_delete_callback(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(likely(!dict->hooks || !dict->hooks->del_callback)) + return; + + // We may execute the delete callback on items deleted from a view, + // because we may have references to it, after the master is gone + // so, the shared structure will remain until the last reference is released. - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) - dict->flags &= ~DICTIONARY_FLAG_EXCLUSIVE_ACCESS; + internal_error(false, + "DICTIONARY: Running delete callback on item '%s' of dictionary created from %s() %zu@%s.", + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + DICTIONARY_STATS_CALLBACK_DELETES_PLUS1(dict); + dict->hooks->del_callback(item, item->shared->value, dict->hooks->del_callback_data); +} + +// ---------------------------------------------------------------------------- +// dictionary locks +static inline size_t dictionary_locks_init(DICTIONARY *dict) { + if(likely(!is_dictionary_single_threaded(dict))) { + netdata_rwlock_init(&dict->index.rwlock); + netdata_rwlock_init(&dict->items.rwlock); return 0; } - - // we are single threaded - dict->flags |= DICTIONARY_FLAG_EXCLUSIVE_ACCESS; return 0; } -static inline size_t dictionary_lock_free(DICTIONARY *dict) { - if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { - netdata_rwlock_destroy(&dict->rwlock); +static inline size_t dictionary_locks_destroy(DICTIONARY *dict) { + if(likely(!is_dictionary_single_threaded(dict))) { + netdata_rwlock_destroy(&dict->index.rwlock); + netdata_rwlock_destroy(&dict->items.rwlock); return 0; } return 0; } -static void dictionary_lock(DICTIONARY *dict, char rw) { - if(rw == 'u' || rw == 'U') return; +static inline void ll_recursive_lock_set_thread_as_writer(DICTIONARY *dict) { + pid_t expected = 0, desired = gettid(); + if(!__atomic_compare_exchange_n(&dict->items.writer_pid, &expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) + fatal("DICTIONARY: Cannot set thread %d as exclusive writer, expected %d, desired %d, found %d.", gettid(), expected, desired, __atomic_load_n(&dict->items.writer_pid, __ATOMIC_SEQ_CST)); +} - if(rw == 'r' || rw == 'R') { - // read lock - __atomic_add_fetch(&dict->readers, 1, __ATOMIC_RELAXED); - } - else { - // write lock - __atomic_add_fetch(&dict->writers, 1, __ATOMIC_RELAXED); - } +static inline void ll_recursive_unlock_unset_thread_writer(DICTIONARY *dict) { + pid_t expected = gettid(), desired = 0; + if(!__atomic_compare_exchange_n(&dict->items.writer_pid, &expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) + fatal("DICTIONARY: Cannot unset thread %d as exclusive writer, expected %d, desired %d, found %d.", gettid(), expected, desired, __atomic_load_n(&dict->items.writer_pid, __ATOMIC_SEQ_CST)); +} + +static inline bool ll_recursive_lock_is_thread_the_writer(DICTIONARY *dict) { + pid_t tid = gettid(); + return tid > 0 && tid == __atomic_load_n(&dict->items.writer_pid, __ATOMIC_SEQ_CST); +} - if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) +static void ll_recursive_lock(DICTIONARY *dict, char rw) { + if(unlikely(is_dictionary_single_threaded(dict))) return; - if(rw == 'r' || rw == 'R') { - // read lock - netdata_rwlock_rdlock(&dict->rwlock); + if(ll_recursive_lock_is_thread_the_writer(dict)) { + dict->items.writer_depth++; + return; + } - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - internal_error(true, "DICTIONARY: left-over exclusive access to dictionary created by %s (%zu@%s) found", dict->creation_function, dict->creation_line, dict->creation_file); - dict->flags &= ~DICTIONARY_FLAG_EXCLUSIVE_ACCESS; - } + if(rw == DICTIONARY_LOCK_READ || rw == DICTIONARY_LOCK_REENTRANT || rw == 'R') { + // read lock + netdata_rwlock_rdlock(&dict->items.rwlock); } else { // write lock - netdata_rwlock_wrlock(&dict->rwlock); - - dict->flags |= DICTIONARY_FLAG_EXCLUSIVE_ACCESS; + netdata_rwlock_wrlock(&dict->items.rwlock); + ll_recursive_lock_set_thread_as_writer(dict); } } -static void dictionary_unlock(DICTIONARY *dict, char rw) { - if(rw == 'u' || rw == 'U') return; +static void ll_recursive_unlock(DICTIONARY *dict, char rw) { + if(unlikely(is_dictionary_single_threaded(dict))) + return; - if(rw == 'r' || rw == 'R') { + if(ll_recursive_lock_is_thread_the_writer(dict) && dict->items.writer_depth > 0) { + dict->items.writer_depth--; + return; + } + + if(rw == DICTIONARY_LOCK_READ || rw == DICTIONARY_LOCK_REENTRANT || rw == 'R') { // read unlock - __atomic_sub_fetch(&dict->readers, 1, __ATOMIC_RELAXED); + + netdata_rwlock_unlock(&dict->items.rwlock); } else { // write unlock - garbage_collect_pending_deletes_unsafe(dict); - __atomic_sub_fetch(&dict->writers, 1, __ATOMIC_RELAXED); + + ll_recursive_unlock_unset_thread_writer(dict); + + netdata_rwlock_unlock(&dict->items.rwlock); } +} - if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) +void dictionary_write_lock(DICTIONARY *dict) { + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); +} +void dictionary_write_unlock(DICTIONARY *dict) { + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); +} + +static inline void dictionary_index_lock_rdlock(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) return; - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) - dict->flags &= ~DICTIONARY_FLAG_EXCLUSIVE_ACCESS; + netdata_rwlock_rdlock(&dict->index.rwlock); +} + +static inline void dictionary_index_rdlock_unlock(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) + return; - netdata_rwlock_unlock(&dict->rwlock); + netdata_rwlock_unlock(&dict->index.rwlock); } -// ---------------------------------------------------------------------------- -// deferred deletions +static inline void dictionary_index_lock_wrlock(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) + return; -void dictionary_defer_all_deletions_unsafe(DICTIONARY *dict, char rw) { - if(rw == 'r' || rw == 'R') { - // read locked - no need to defer deletions - ; - } - else { - // write locked - defer deletions - dict->flags |= DICTIONARY_FLAG_DEFER_ALL_DELETIONS; - } + netdata_rwlock_wrlock(&dict->index.rwlock); } +static inline void dictionary_index_wrlock_unlock(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) + return; -void dictionary_restore_all_deletions_unsafe(DICTIONARY *dict, char rw) { - if(rw == 'r' || rw == 'R') { - // read locked - no need to defer deletions - internal_error(dict->flags & DICTIONARY_FLAG_DEFER_ALL_DELETIONS, "DICTIONARY: deletions are deferred on a read lock"); - } - else { - // write locked - defer deletions - if(dict->flags & DICTIONARY_FLAG_DEFER_ALL_DELETIONS) - dict->flags &= ~DICTIONARY_FLAG_DEFER_ALL_DELETIONS; + netdata_rwlock_unlock(&dict->index.rwlock); +} + +// ---------------------------------------------------------------------------- +// items garbage collector + +static void garbage_collect_pending_deletes(DICTIONARY *dict) { + usec_t last_master_deletion_us = dict->hooks?__atomic_load_n(&dict->hooks->last_master_deletion_us, __ATOMIC_SEQ_CST):0; + usec_t last_gc_run_us = __atomic_load_n(&dict->last_gc_run_us, __ATOMIC_SEQ_CST); + + bool is_view = is_view_dictionary(dict); + + if(likely(!( + DICTIONARY_PENDING_DELETES_GET(dict) > 0 || + (is_view && last_master_deletion_us > last_gc_run_us) + ))) + return; + + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + + __atomic_store_n(&dict->last_gc_run_us, now_realtime_usec(), __ATOMIC_SEQ_CST); + + if(is_view) + dictionary_index_lock_wrlock(dict); + + DICTIONARY_STATS_GARBAGE_COLLECTIONS_PLUS1(dict); + + size_t deleted = 0, pending = 0, examined = 0; + DICTIONARY_ITEM *item = dict->items.list, *item_next; + while(item) { + examined++; + + // this will cleanup + item_next = item->next; + int rc = item_check_and_acquire_advanced(dict, item, is_view); + + if(rc == RC_ITEM_MARKED_FOR_DELETION) { + // we didn't get a reference + + if(item_is_not_referenced_and_can_be_removed(dict, item)) { + DOUBLE_LINKED_LIST_REMOVE_UNSAFE(dict->items.list, item, prev, next); + dict_item_free_with_hooks(dict, item); + deleted++; + + pending = DICTIONARY_PENDING_DELETES_MINUS1(dict); + if (!pending) + break; + } + } + else if(rc == RC_ITEM_IS_CURRENTLY_BEING_DELETED) + ; // do not touch this item (we didn't get a reference) + + else if(rc == RC_ITEM_OK) + item_release(dict, item); + + item = item_next; } + + if(is_view) + dictionary_index_wrlock_unlock(dict); + + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); + + (void)deleted; + (void)examined; + + internal_error(false, "DICTIONARY: garbage collected dictionary created by %s (%zu@%s), examined %zu items, deleted %zu items, still pending %zu items", + dict->creation_function, dict->creation_line, dict->creation_file, examined, deleted, pending); + } // ---------------------------------------------------------------------------- @@ -413,144 +840,248 @@ static inline size_t reference_counter_free(DICTIONARY *dict) { return 0; } -static int reference_counter_increase(NAME_VALUE *nv) { - int refcount = __atomic_add_fetch(&nv->refcount, 1, __ATOMIC_SEQ_CST); - if(refcount == 1) - fatal("DICTIONARY: request to dup item '%s' but its reference counter was zero", namevalue_get_name(nv)); - return refcount; -} +static void item_acquire(DICTIONARY *dict, DICTIONARY_ITEM *item) { + REFCOUNT refcount; -static int reference_counter_acquire(DICTIONARY *dict, NAME_VALUE *nv) { - int refcount; - if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) - refcount = ++nv->refcount; - else - refcount = __atomic_add_fetch(&nv->refcount, 1, __ATOMIC_SEQ_CST); + if(unlikely(is_dictionary_single_threaded(dict))) { + refcount = ++item->refcount; + } + else { + // increment the refcount + refcount = __atomic_add_fetch(&item->refcount, 1, __ATOMIC_SEQ_CST); + } + + if(refcount <= 0) { + internal_error( + true, + "DICTIONARY: attempted to acquire item which is deleted (refcount = %d): " + "'%s' on dictionary created by %s() (%zu@%s)", + refcount - 1, + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + fatal( + "DICTIONARY: request to acquire item '%s', which is deleted (refcount = %d)!", + item_get_name(item), + refcount - 1); + } if(refcount == 1) { // referenced items counts number of unique items referenced // so, we increase it only when refcount == 1 - DICTIONARY_STATS_REFERENCED_ITEMS_PLUS1(dict); + DICTIONARY_REFERENCED_ITEMS_PLUS1(dict); // if this is a deleted item, but the counter increased to 1 // we need to remove it from the pending items to delete - if (nv->flags & NAME_VALUE_FLAG_DELETED) - DICTIONARY_STATS_PENDING_DELETES_MINUS1(dict); + if(item_flag_check(item, ITEM_FLAG_DELETED)) + DICTIONARY_PENDING_DELETES_MINUS1(dict); } - - return refcount; } -static uint32_t reference_counter_release(DICTIONARY *dict, NAME_VALUE *nv, bool can_get_write_lock) { +static void item_release(DICTIONARY *dict, DICTIONARY_ITEM *item) { // this function may be called without any lock on the dictionary - // or even when someone else has a write lock on the dictionary - // so, we cannot check for EXCLUSIVE ACCESS + // or even when someone else has write lock on the dictionary - uint32_t refcount; - if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) - refcount = nv->refcount--; - else - refcount = __atomic_fetch_sub(&nv->refcount, 1, __ATOMIC_SEQ_CST); + bool is_deleted; + REFCOUNT refcount; - if(refcount == 0) { - internal_error(true, "DICTIONARY: attempted to release item without references: '%s' on dictionary created by %s() (%zu@%s)", namevalue_get_name(nv), dict->creation_function, dict->creation_line, dict->creation_file); - fatal("DICTIONARY: attempted to release item without references: '%s'", namevalue_get_name(nv)); + if(unlikely(is_dictionary_single_threaded(dict))) { + is_deleted = item->flags & ITEM_FLAG_DELETED; + refcount = --item->refcount; } + else { + // get the flags before decrementing any reference counters + // (the other way around may lead to use-after-free) + is_deleted = item_flag_check(item, ITEM_FLAG_DELETED); - if(refcount == 1) { - if((nv->flags & NAME_VALUE_FLAG_DELETED)) - DICTIONARY_STATS_PENDING_DELETES_PLUS1(dict); + // decrement the refcount + refcount = __atomic_sub_fetch(&item->refcount, 1, __ATOMIC_SEQ_CST); + } + + if(refcount < 0) { + internal_error( + true, + "DICTIONARY: attempted to release item without references (refcount = %d): " + "'%s' on dictionary created by %s() (%zu@%s)", + refcount + 1, + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + fatal( + "DICTIONARY: attempted to release item '%s' without references (refcount = %d)", + item_get_name(item), + refcount + 1); + } + + if(refcount == 0) { + + if(is_deleted) + DICTIONARY_PENDING_DELETES_PLUS1(dict); // referenced items counts number of unique items referenced // so, we decrease it only when refcount == 0 - DICTIONARY_STATS_REFERENCED_ITEMS_MINUS1(dict); + DICTIONARY_REFERENCED_ITEMS_MINUS1(dict); } +} + +static int item_check_and_acquire_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item, bool having_index_lock) { + size_t spins = 0; + REFCOUNT refcount, desired; + + int ret = RC_ITEM_OK; + + do { + spins++; + + refcount = DICTIONARY_ITEM_REFCOUNT_GET(dict, item); + + if(refcount < 0) { + // we can't use this item + ret = RC_ITEM_IS_CURRENTLY_BEING_DELETED; + break; + } + + if(item_flag_check(item, ITEM_FLAG_DELETED)) { + // we can't use this item + ret = RC_ITEM_MARKED_FOR_DELETION; + break; + } + + desired = refcount + 1; + + } while(!__atomic_compare_exchange_n(&item->refcount, &refcount, desired, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)); + + // if ret == ITEM_OK, we acquired the item + + if(ret == RC_ITEM_OK) { + if (is_view_dictionary(dict) && + item_shared_flag_check(item, ITEM_FLAG_DELETED) && + !item_flag_check(item, ITEM_FLAG_DELETED)) { + // but, we can't use this item + + if (having_index_lock) { + // delete it from the hashtable + if(hashtable_delete_unsafe(dict, item_get_name(item), item->key_len, item) == 0) + error("DICTIONARY: INTERNAL ERROR VIEW: tried to delete item with name '%s', name_len %u that is not in the index", item_get_name(item), (KEY_LEN_TYPE)(item->key_len - 1)); + else + pointer_del(dict, item); + + // mark it in our dictionary as deleted too + // this is safe to be done here, because we have got + // a reference counter on item + dict_item_set_deleted(dict, item); + + // decrement the refcount we incremented above + if (__atomic_sub_fetch(&item->refcount, 1, __ATOMIC_SEQ_CST) == 0) { + // this is a deleted item, and we are the last one + DICTIONARY_PENDING_DELETES_PLUS1(dict); + } + + // do not touch the item below this point + } else { + // this is traversal / walkthrough + // decrement the refcount we incremented above + __atomic_sub_fetch(&item->refcount, 1, __ATOMIC_SEQ_CST); + } - if(can_get_write_lock && DICTIONARY_STATS_PENDING_DELETES_GET(dict)) { - // we can garbage collect now + return RC_ITEM_MARKED_FOR_DELETION; + } - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - garbage_collect_pending_deletes_unsafe(dict); - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + if(desired == 1) + DICTIONARY_REFERENCED_ITEMS_PLUS1(dict); } - return refcount; + + if(unlikely(spins > 1 && dict->stats)) + DICTIONARY_STATS_CHECK_SPINS_PLUS(dict, spins - 1); + + return ret; } -// ---------------------------------------------------------------------------- -// hash table +// if a dictionary item can be deleted, return true, otherwise return false +// we use the private reference counter +static inline int item_is_not_referenced_and_can_be_removed_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item) { + // if we can set refcount to REFCOUNT_DELETING, we can delete this item -#ifdef DICTIONARY_WITH_AVL -static inline const char *namevalue_get_name(NAME_VALUE *nv); + size_t spins = 0; + REFCOUNT refcount, desired = REFCOUNT_DELETING; -static int name_value_compare(void* a, void* b) { - return strcmp(namevalue_get_name((NAME_VALUE *)a), namevalue_get_name((NAME_VALUE *)b)); -} + int ret = RC_ITEM_OK; -static void *get_thread_static_name_value(const char *name) { - static __thread NAME_VALUE tmp = { 0 }; - tmp.flags = NAME_VALUE_FLAG_NONE; - tmp.caller_name = (char *)name; - return &tmp; -} + do { + spins++; -static void hashtable_init_unsafe(DICTIONARY *dict) { - avl_init(&dict->values_index, name_value_compare); - dict->get_thread_static_name_value = get_thread_static_name_value; -} + refcount = DICTIONARY_ITEM_REFCOUNT_GET(dict, item); -static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { - (void)dict; - return 0; -} + if(refcount < 0) { + // we can't use this item + ret = RC_ITEM_IS_CURRENTLY_BEING_DELETED; + break; + } -static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *nv) { - (void)name; - (void)name_len; + if(refcount > 0) { + // we can't delete this + ret = RC_ITEM_IS_REFERENCED; + break; + } - if(unlikely(avl_remove(&(dict->values_index), (avl_t *)(nv)) != (avl_t *)nv)) - return 0; + if(item_flag_check(item, ITEM_FLAG_BEING_CREATED)) { + // we can't use this item + ret = RC_ITEM_IS_CURRENTLY_BEING_CREATED; + break; + } + } while(!__atomic_compare_exchange_n(&item->refcount, &refcount, desired, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)); - return 1; -} +#ifdef NETDATA_INTERNAL_CHECKS + if(ret == RC_ITEM_OK) + item->deleter_pid = gettid(); +#endif -static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { - (void)name_len; + if(unlikely(spins > 1 && dict->stats)) + DICTIONARY_STATS_DELETE_SPINS_PLUS(dict, spins - 1); - void *tmp = dict->get_thread_static_name_value(name); - return (NAME_VALUE *)avl_search(&(dict->values_index), (avl_t *)tmp); + return ret; } -static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { - // AVL needs a NAME_VALUE to insert into the dictionary but we don't have it yet. - // So, the only thing we can do, is return an existing one if it is already there. - // Returning NULL will make the caller thing we added it, will allocate one - // and will call hashtable_inserted_name_value_unsafe(), at which we will do - // the actual indexing. +// if a dictionary item can be freed, return true, otherwise return false +// we use the shared reference counter +static inline bool item_shared_release_and_check_if_it_can_be_freed(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item) { + // if we can set refcount to REFCOUNT_DELETING, we can delete this item - dict->hash_base = hashtable_get_unsafe(dict, name, name_len); - return &dict->hash_base; -} + REFCOUNT links = __atomic_sub_fetch(&item->shared->links, 1, __ATOMIC_SEQ_CST); + if(links == 0 && __atomic_compare_exchange_n(&item->shared->links, &links, REFCOUNT_DELETING, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { -static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, void *nv) { - // we have our new NAME_VALUE object. - // Let's index it. + // we can delete it + return true; + } - if(unlikely(avl_insert(&((dict)->values_index), (avl_t *)(nv)) != (avl_t *)nv)) - error("dictionary: INTERNAL ERROR: duplicate insertion to dictionary."); + // we can't delete it + return false; } -#endif -#ifdef DICTIONARY_WITH_JUDYHS -static void hashtable_init_unsafe(DICTIONARY *dict) { - dict->JudyHSArray = NULL; + +// ---------------------------------------------------------------------------- +// hash table operations + +static size_t hashtable_init_unsafe(DICTIONARY *dict) { + dict->index.JudyHSArray = NULL; + return 0; } static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { - if(unlikely(!dict->JudyHSArray)) return 0; + if(unlikely(!dict->index.JudyHSArray)) return 0; + + pointer_destroy_index(dict); JError_t J_Error; - Word_t ret = JudyHSFreeArray(&dict->JudyHSArray, &J_Error); + Word_t ret = JudyHSFreeArray(&dict->index.JudyHSArray, &J_Error); if(unlikely(ret == (Word_t) JERR)) { error("DICTIONARY: Cannot destroy JudyHS, JU_ERRNO_* == %u, ID == %d", JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); @@ -558,17 +1089,15 @@ static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { debug(D_DICTIONARY, "Dictionary: hash table freed %lu bytes", ret); - dict->JudyHSArray = NULL; + dict->index.JudyHSArray = NULL; return (size_t)ret; } -static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: inserting item from the index without exclusive access to the dictionary created by %s() (%zu@%s)", dict->creation_function, dict->creation_line, dict->creation_file); - +static inline void **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { JError_t J_Error; - Pvoid_t *Rc = JudyHSIns(&dict->JudyHSArray, (void *)name, name_len, &J_Error); + Pvoid_t *Rc = JudyHSIns(&dict->index.JudyHSArray, (void *)name, name_len, &J_Error); if (unlikely(Rc == PJERR)) { - fatal("DICTIONARY: Cannot insert entry with name '%s' to JudyHS, JU_ERRNO_* == %u, ID == %d", + error("DICTIONARY: Cannot insert entry with name '%s' to JudyHS, JU_ERRNO_* == %u, ID == %d", name, JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); } @@ -579,17 +1108,15 @@ static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char // put anything needed at the value of the index. // The pointer to pointer we return has to be used before // any other operation that may change the index (insert/delete). - return (NAME_VALUE **)Rc; + return Rc; } -static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *nv) { - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: deleting item from the index without exclusive access to the dictionary created by %s() (%zu@%s)", dict->creation_function, dict->creation_line, dict->creation_file); - - (void)nv; - if(unlikely(!dict->JudyHSArray)) return 0; +static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *item) { + (void)item; + if(unlikely(!dict->index.JudyHSArray)) return 0; JError_t J_Error; - int ret = JudyHSDel(&dict->JudyHSArray, (void *)name, name_len, &J_Error); + int ret = JudyHSDel(&dict->index.JudyHSArray, (void *)name, name_len, &J_Error); if(unlikely(ret == JERR)) { error("DICTIONARY: Cannot delete entry with name '%s' from JudyHS, JU_ERRNO_* == %u, ID == %d", name, JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); @@ -609,16 +1136,17 @@ static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, si } } -static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { - if(unlikely(!dict->JudyHSArray)) return NULL; +static inline DICTIONARY_ITEM *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { + if(unlikely(!dict->index.JudyHSArray)) return NULL; DICTIONARY_STATS_SEARCHES_PLUS1(dict); Pvoid_t *Rc; - Rc = JudyHSGet(dict->JudyHSArray, (void *)name, name_len); + Rc = JudyHSGet(dict->index.JudyHSArray, (void *)name, name_len); if(likely(Rc)) { // found in the hash table - return (NAME_VALUE *)*Rc; + pointer_check(dict, (DICTIONARY_ITEM *)*Rc); + return (DICTIONARY_ITEM *)*Rc; } else { // not found in the hash table @@ -626,345 +1154,419 @@ static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *nam } } -static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, void *nv) { +static inline void hashtable_inserted_item_unsafe(DICTIONARY *dict, void *item) { (void)dict; - (void)nv; + (void)item; + + // this is called just after an item is successfully inserted to the hashtable + // we don't need this for judy, but we may need it if we integrate more hash tables + ; } -#endif // DICTIONARY_WITH_JUDYHS - // ---------------------------------------------------------------------------- // linked list management -static inline void linkedlist_namevalue_link_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: adding item to the linked-list without exclusive access to the dictionary created by %s() (%zu@%s)", dict->creation_function, dict->creation_line, dict->creation_file); +static inline void item_linked_list_add(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); - if (unlikely(!dict->first_item)) { - // we are the only ones here - nv->next = NULL; - nv->prev = NULL; - dict->first_item = dict->last_item = nv; - return; - } + if(dict->options & DICT_OPTION_ADD_IN_FRONT) + DOUBLE_LINKED_LIST_PREPEND_UNSAFE(dict->items.list, item, prev, next); + else + DOUBLE_LINKED_LIST_APPEND_UNSAFE(dict->items.list, item, prev, next); - if(dict->flags & DICTIONARY_FLAG_ADD_IN_FRONT) { - // add it at the beginning - nv->prev = NULL; - nv->next = dict->first_item; +#ifdef NETDATA_INTERNAL_CHECKS + item->ll_adder_pid = gettid(); +#endif - if (likely(nv->next)) nv->next->prev = nv; - dict->first_item = nv; - } - else { - // add it at the end - nv->next = NULL; - nv->prev = dict->last_item; + // clear the BEING created flag, + // after it has been inserted into the linked list + item_flag_clear(item, ITEM_FLAG_BEING_CREATED); - if (likely(nv->prev)) nv->prev->next = nv; - dict->last_item = nv; - } + garbage_collect_pending_deletes(dict); + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); } -static inline void linkedlist_namevalue_unlink_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: removing item from the linked-list without exclusive access to the dictionary created by %s() (%zu@%s)", dict->creation_function, dict->creation_line, dict->creation_file); +static inline void item_linked_list_remove(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + + DOUBLE_LINKED_LIST_REMOVE_UNSAFE(dict->items.list, item, prev, next); - if(nv->next) nv->next->prev = nv->prev; - if(nv->prev) nv->prev->next = nv->next; - if(dict->first_item == nv) dict->first_item = nv->next; - if(dict->last_item == nv) dict->last_item = nv->prev; +#ifdef NETDATA_INTERNAL_CHECKS + item->ll_remover_pid = gettid(); +#endif + + garbage_collect_pending_deletes(dict); + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); } // ---------------------------------------------------------------------------- -// NAME_VALUE methods +// ITEM initialization and updates -static inline size_t namevalue_set_name(DICTIONARY *dict, NAME_VALUE *nv, const char *name, size_t name_len) { - if(likely(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE)) { - nv->caller_name = (char *)name; - return 0; +static inline size_t item_set_name(DICTIONARY *dict, DICTIONARY_ITEM *item, const char *name, size_t name_len) { + if(likely(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE)) { + item->caller_name = (char *)name; + item->key_len = name_len; + } + else { + item->string_name = string_strdupz(name); + item->key_len = string_strlen(item->string_name) + 1; + item->options |= ITEM_OPTION_ALLOCATED_NAME; } - nv->string_name = string_strdupz(name); - nv->flags |= NAME_VALUE_FLAG_NAME_IS_ALLOCATED; - return name_len; + return item->key_len; } -static inline size_t namevalue_free_name(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(!(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE))) - string_freez(nv->string_name); +static inline size_t item_free_name(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(likely(!(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE))) + string_freez(item->string_name); - return 0; + return item->key_len; } -static inline const char *namevalue_get_name(NAME_VALUE *nv) { - if(nv->flags & NAME_VALUE_FLAG_NAME_IS_ALLOCATED) - return string2str(nv->string_name); +static inline const char *item_get_name(const DICTIONARY_ITEM *item) { + if(item->options & ITEM_OPTION_ALLOCATED_NAME) + return string2str(item->string_name); else - return nv->caller_name; + return item->caller_name; } -static NAME_VALUE *namevalue_create_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *value, size_t value_len) { - debug(D_DICTIONARY, "Creating name value entry for name '%s'.", name); +static inline size_t item_get_name_len(const DICTIONARY_ITEM *item) { + if(item->options & ITEM_OPTION_ALLOCATED_NAME) + return string_strlen(item->string_name); + else + return strlen(item->caller_name); +} - size_t size = sizeof(NAME_VALUE); - NAME_VALUE *nv = mallocz(size); - size_t allocated = size; +static DICTIONARY_ITEM *dict_item_create(DICTIONARY *dict __maybe_unused, size_t *allocated_bytes, DICTIONARY_ITEM *master_item) { + DICTIONARY_ITEM *item; + + size_t size = sizeof(DICTIONARY_ITEM); + item = callocz(1, size); #ifdef NETDATA_INTERNAL_CHECKS - nv->dict = dict; + item->creator_pid = gettid(); #endif - nv->refcount = 0; - nv->flags = NAME_VALUE_FLAG_NONE; - nv->value_len = value_len; + item->refcount = 1; + item->flags = ITEM_FLAG_BEING_CREATED; + + *allocated_bytes += size; - allocated += namevalue_set_name(dict, nv, name, name_len); + if(master_item) { + item->shared = master_item->shared; - if(likely(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) - nv->value = value; + if(unlikely(__atomic_add_fetch(&item->shared->links, 1, __ATOMIC_SEQ_CST) <= 1)) + fatal("DICTIONARY: attempted to link to a shared item structure that had zero references"); + } else { - if(likely(value_len)) { - if (value) { - // a value has been supplied - // copy it - nv->value = mallocz(value_len); - memcpy(nv->value, value, value_len); - } - else { - // no value has been supplied - // allocate a clear memory block - nv->value = callocz(1, value_len); - } + size = sizeof(DICTIONARY_ITEM_SHARED); + item->shared = callocz(1, size); + item->shared->links = 1; + *allocated_bytes += size; + } + +#ifdef NETDATA_INTERNAL_CHECKS + item->dict = dict; +#endif + return item; +} + +static void *dict_item_value_create(void *value, size_t value_len) { + void *ptr = NULL; + + if(likely(value_len)) { + if (likely(value)) { + // a value has been supplied + // copy it + ptr = mallocz(value_len); + memcpy(ptr, value, value_len); } else { - // the caller wants an item without any value - nv->value = NULL; + // no value has been supplied + // allocate a clear memory block + ptr = callocz(1, value_len); } + } + // else + // the caller wants an item without any value + + return ptr; +} + +static DICTIONARY_ITEM *dict_item_create_with_hooks(DICTIONARY *dict, const char *name, size_t name_len, void *value, size_t value_len, void *constructor_data, DICTIONARY_ITEM *master_item) { +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(name_len > KEY_LEN_MAX)) + fatal("DICTIONARY: tried to index a key of size %zu, but the maximum acceptable is %zu", name_len, (size_t)KEY_LEN_MAX); + + if(unlikely(value_len > VALUE_LEN_MAX)) + fatal("DICTIONARY: tried to add an item of size %zu, but the maximum acceptable is %zu", value_len, (size_t)VALUE_LEN_MAX); +#endif - allocated += value_len; + size_t item_size = 0, key_size = 0, value_size = 0; + + DICTIONARY_ITEM *item = dict_item_create(dict, &item_size, master_item); + key_size += item_set_name(dict, item, name, name_len); + + if(unlikely(is_view_dictionary(dict))) { + // we are on a view dictionary + // do not touch the value + ; + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(!master_item)) + fatal("DICTIONARY: cannot add an item to a view without a master item."); +#endif } + else { + // we are on the master dictionary - DICTIONARY_STATS_ENTRIES_PLUS1(dict, allocated); + if(unlikely(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE)) + item->shared->value = value; + else + item->shared->value = dict_item_value_create(value, value_len); + + item->shared->value_len = value_len; + value_size += value_len; + + dictionary_execute_insert_callback(dict, item, constructor_data); + } - if(dict->ins_callback) - dict->ins_callback(namevalue_get_name(nv), nv->value, dict->ins_callback_data); + DICTIONARY_ENTRIES_PLUS1(dict); + DICTIONARY_STATS_PLUS_MEMORY(dict, key_size, item_size, value_size); - return nv; + return item; } -static void namevalue_reset_unsafe(DICTIONARY *dict, NAME_VALUE *nv, void *value, size_t value_len) { - debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", namevalue_get_name(nv)); +static void dict_item_reset_value_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item, void *value, size_t value_len, void *constructor_data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: %s() should never be called on views.", __FUNCTION__ ); + + debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", item_get_name(item)); + + DICTIONARY_VALUE_RESETS_PLUS1(dict); - DICTIONARY_STATS_VALUE_RESETS_PLUS1(dict, nv->value_len, value_len); + if(item->shared->value_len != value_len) { + DICTIONARY_STATS_PLUS_MEMORY(dict, 0, 0, value_len); + DICTIONARY_STATS_MINUS_MEMORY(dict, 0, 0, item->shared->value_len); + } - if(dict->del_callback) - dict->del_callback(namevalue_get_name(nv), nv->value, dict->del_callback_data); + dictionary_execute_delete_callback(dict, item); - if(likely(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) { - debug(D_DICTIONARY, "Dictionary: linking value to '%s'", namevalue_get_name(nv)); - nv->value = value; - nv->value_len = value_len; + if(likely(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE)) { + debug(D_DICTIONARY, "Dictionary: linking value to '%s'", item_get_name(item)); + item->shared->value = value; + item->shared->value_len = value_len; } else { - debug(D_DICTIONARY, "Dictionary: cloning value to '%s'", namevalue_get_name(nv)); + debug(D_DICTIONARY, "Dictionary: cloning value to '%s'", item_get_name(item)); - void *oldvalue = nv->value; - void *newvalue = NULL; + void *old_value = item->shared->value; + void *new_value = NULL; if(value_len) { - newvalue = mallocz(value_len); - if(value) memcpy(newvalue, value, value_len); - else memset(newvalue, 0, value_len); + new_value = mallocz(value_len); + if(value) memcpy(new_value, value, value_len); + else memset(new_value, 0, value_len); } - nv->value = newvalue; - nv->value_len = value_len; + item->shared->value = new_value; + item->shared->value_len = value_len; - debug(D_DICTIONARY, "Dictionary: freeing old value of '%s'", namevalue_get_name(nv)); - freez(oldvalue); + debug(D_DICTIONARY, "Dictionary: freeing old value of '%s'", item_get_name(item)); + freez(old_value); } - if(dict->ins_callback) - dict->ins_callback(namevalue_get_name(nv), nv->value, dict->ins_callback_data); + dictionary_execute_insert_callback(dict, item, constructor_data); } -static size_t namevalue_destroy_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { - debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", namevalue_get_name(nv)); +static size_t dict_item_free_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item) { + debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", item_get_name(item)); - if(dict->del_callback) - dict->del_callback(namevalue_get_name(nv), nv->value, dict->del_callback_data); + if(!item_flag_check(item, ITEM_FLAG_DELETED)) + DICTIONARY_ENTRIES_MINUS1(dict); - size_t freed = 0; + size_t item_size = 0, key_size = 0, value_size = 0; - if(unlikely(!(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE))) { - debug(D_DICTIONARY, "Dictionary freeing value of '%s'", namevalue_get_name(nv)); - freez(nv->value); - freed += nv->value_len; - } + key_size += item->key_len; + if(unlikely(!(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE))) + item_free_name(dict, item); - if(unlikely(!(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE))) { - debug(D_DICTIONARY, "Dictionary freeing name '%s'", namevalue_get_name(nv)); - freed += namevalue_free_name(dict, nv); + if(item_shared_release_and_check_if_it_can_be_freed(dict, item)) { + dictionary_execute_delete_callback(dict, item); + + if(unlikely(!(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE))) { + debug(D_DICTIONARY, "Dictionary freeing value of '%s'", item_get_name(item)); + freez(item->shared->value); + item->shared->value = NULL; + } + value_size += item->shared->value_len; + + freez(item->shared); + item->shared = NULL; + item_size += sizeof(DICTIONARY_ITEM_SHARED); } - freez(nv); - freed += sizeof(NAME_VALUE); + freez(item); + item_size += sizeof(DICTIONARY_ITEM); - DICTIONARY_STATS_ENTRIES_MINUS_MEMORY(dict, freed); + DICTIONARY_STATS_MINUS_MEMORY(dict, key_size, item_size, value_size); - return freed; + // we return the memory we actually freed + return item_size + ((dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE) ? 0 : value_size); } -// if a dictionary item can be deleted, return true, otherwise return false -static bool name_value_can_be_deleted(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(dict->flags & DICTIONARY_FLAG_DEFER_ALL_DELETIONS)) - return false; +// ---------------------------------------------------------------------------- +// item operations - if(unlikely(DICTIONARY_NAME_VALUE_REFCOUNT_GET(nv) > 0)) - return false; +static void dict_item_shared_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(is_master_dictionary(dict)) { + item_shared_flag_set(item, ITEM_FLAG_DELETED); - return true; + if(dict->hooks) + __atomic_store_n(&dict->hooks->last_master_deletion_us, now_realtime_usec(), __ATOMIC_SEQ_CST); + } } -// ---------------------------------------------------------------------------- -// API - dictionary management -#ifdef NETDATA_INTERNAL_CHECKS -DICTIONARY *dictionary_create_advanced_with_trace(DICTIONARY_FLAGS flags, size_t scratchpad_size, const char *function, size_t line, const char *file) { -#else -DICTIONARY *dictionary_create_advanced(DICTIONARY_FLAGS flags, size_t scratchpad_size) { -#endif - debug(D_DICTIONARY, "Creating dictionary."); +// returns true if we set the deleted flag on this item +static bool dict_item_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ITEM_FLAGS expected, desired; - if(unlikely(flags & DICTIONARY_FLAGS_RESERVED)) - flags &= ~DICTIONARY_FLAGS_RESERVED; + do { + expected = __atomic_load_n(&item->flags, __ATOMIC_SEQ_CST); - DICTIONARY *dict = callocz(1, sizeof(DICTIONARY) + scratchpad_size); - size_t allocated = sizeof(DICTIONARY) + scratchpad_size; + if (expected & ITEM_FLAG_DELETED) + return false; - dict->scratchpad_size = scratchpad_size; - dict->flags = flags; - dict->first_item = dict->last_item = NULL; + desired = expected | ITEM_FLAG_DELETED; - allocated += dictionary_lock_init(dict); - allocated += reference_counter_init(dict); - dict->memory = (long)allocated; + } while(!__atomic_compare_exchange_n(&item->flags, &expected, desired, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)); - hashtable_init_unsafe(dict); + DICTIONARY_ENTRIES_MINUS1(dict); + return true; +} -#ifdef NETDATA_INTERNAL_CHECKS - dict->creation_function = function; - dict->creation_file = file; - dict->creation_line = line; -#endif +static inline void dict_item_free_or_mark_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item) { + int rc = item_is_not_referenced_and_can_be_removed_advanced(dict, item); + switch(rc) { + case RC_ITEM_OK: + // the item is ours, refcount set to -100 + dict_item_shared_set_deleted(dict, item); + item_linked_list_remove(dict, item); + dict_item_free_with_hooks(dict, item); + break; - return (DICTIONARY *)dict; -} + case RC_ITEM_IS_REFERENCED: + case RC_ITEM_IS_CURRENTLY_BEING_CREATED: + // the item is currently referenced by others + dict_item_shared_set_deleted(dict, item); + dict_item_set_deleted(dict, item); + // after this point do not touch the item + break; -void *dictionary_scratchpad(DICTIONARY *dict) { - return &dict->scratchpad; -} + case RC_ITEM_IS_CURRENTLY_BEING_DELETED: + // an item that is currently being deleted by someone else - don't touch it + break; -size_t dictionary_destroy(DICTIONARY *dict) { - if(!dict) return 0; + default: + internal_error(true, "Hey dev! You forgot to add the new condition here!"); + break; + } +} - NAME_VALUE *nv; +// this is used by traversal functions to remove the current item +// if it is deleted and it has zero references. This will eliminate +// the need for the garbage collector to kick-in later. +// Most deletions happen during traversal, so this is a nice hack +// to speed up everything! +static inline void dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(DICTIONARY *dict, DICTIONARY_ITEM *item, char rw) { + if(rw == DICTIONARY_LOCK_WRITE) { + bool should_be_deleted = item_flag_check(item, ITEM_FLAG_DELETED); - debug(D_DICTIONARY, "Destroying dictionary."); + item_release(dict, item); - long referenced_items = 0; - size_t retries = 0; - do { - referenced_items = __atomic_load_n(&dict->referenced_items, __ATOMIC_SEQ_CST); - if (referenced_items) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - - // there are referenced items - // delete all items individually, so that only the referenced will remain - NAME_VALUE *nv_next; - for (nv = dict->first_item; nv; nv = nv_next) { - nv_next = nv->next; - size_t refcount = DICTIONARY_NAME_VALUE_REFCOUNT_GET(nv); - if (!refcount && !(nv->flags & NAME_VALUE_FLAG_DELETED)) - dictionary_del_unsafe(dict, namevalue_get_name(nv)); - } + if(should_be_deleted && item_is_not_referenced_and_can_be_removed(dict, item)) { + // this has to be before removing from the linked list, + // otherwise the garbage collector will also kick in! + DICTIONARY_PENDING_DELETES_MINUS1(dict); - internal_error( - retries == 0, - "DICTIONARY: waiting (try %zu) for destruction of dictionary created from %s() %zu@%s, because it has %ld referenced items in it (%ld total).", - retries + 1, - dict->creation_function, - dict->creation_line, - dict->creation_file, - referenced_items, - dict->entries); - - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); - sleep_usec(10000); + item_linked_list_remove(dict, item); + dict_item_free_with_hooks(dict, item); } - } while(referenced_items > 0 && ++retries < 10); - - if(referenced_items) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); + } + else { + // we can't do anything under this mode + item_release(dict, item); + } +} - dict->flags |= DICTIONARY_FLAG_DESTROYED; +static bool dict_item_del(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(unlikely(!name || !*name)) { internal_error( true, - "DICTIONARY: delaying destruction of dictionary created from %s() %zu@%s after %zu retries, because it has %ld referenced items in it (%ld total).", + "DICTIONARY: attempted to %s() without a name on a dictionary created from %s() %zu@%s.", + __FUNCTION__, dict->creation_function, dict->creation_line, - dict->creation_file, - retries, - referenced_items, - dict->entries); + dict->creation_file); + return false; + } - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); - return 0; + if(unlikely(is_dictionary_destroyed(dict))) { + internal_error(true, "DICTIONARY: attempted to dictionary_del() on a destroyed dictionary"); + return false; } - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); + if(name_len == -1) + name_len = (ssize_t)strlen(name) + 1; // we need the terminating null too - size_t freed = 0; - nv = dict->first_item; - while (nv) { - // cache nv->next - // because we are going to free nv - NAME_VALUE *nv_next = nv->next; - freed += namevalue_destroy_unsafe(dict, nv); - nv = nv_next; - // to speed up destruction, we don't - // unlink nv from the linked-list here - } + debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); - dict->first_item = NULL; - dict->last_item = NULL; + // Unfortunately, the JudyHSDel() does not return the value of the + // item that was deleted, so we have to find it before we delete it, + // since we need to release our structures too. - // destroy the dictionary - freed += hashtable_destroy_unsafe(dict); + dictionary_index_lock_wrlock(dict); - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); - freed += dictionary_lock_free(dict); - freed += reference_counter_free(dict); - freed += sizeof(DICTIONARY) + dict->scratchpad_size; - freez(dict); + int ret; + DICTIONARY_ITEM *item = hashtable_get_unsafe(dict, name, name_len); + if(unlikely(!item)) { + dictionary_index_wrlock_unlock(dict); + ret = false; + } + else { + if(hashtable_delete_unsafe(dict, name, name_len, item) == 0) + error("DICTIONARY: INTERNAL ERROR: tried to delete item with name '%s', name_len %zd that is not in the index", name, name_len - 1); + else + pointer_del(dict, item); - return freed; -} + dictionary_index_wrlock_unlock(dict); -// ---------------------------------------------------------------------------- -// helpers + dict_item_free_or_mark_deleted(dict, item); + ret = true; + } -static NAME_VALUE *dictionary_set_name_value_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - if(unlikely(!name)) { - internal_error(true, "DICTIONARY: attempted to dictionary_set() a dictionary item without a name"); + return ret; +} + +static DICTIONARY_ITEM *dict_item_add_or_reset_value_and_acquire(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data, DICTIONARY_ITEM *master_item) { + if(unlikely(!name || !*name)) { + internal_error( + true, + "DICTIONARY: attempted to %s() without a name on a dictionary created from %s() %zu@%s.", + __FUNCTION__, + dict->creation_function, + dict->creation_line, + dict->creation_file); return NULL; } - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_set() on a destroyed dictionary"); return NULL; } - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: inserting dictionary item '%s' without exclusive access to dictionary", name); - - size_t name_len = strlen(name) + 1; // we need the terminating null too + if(name_len == -1) + name_len = (ssize_t)strlen(name) + 1; // we need the terminating null too debug(D_DICTIONARY, "SET dictionary entry with name '%s'.", name); @@ -979,264 +1581,618 @@ static NAME_VALUE *dictionary_set_name_value_unsafe(DICTIONARY *dict, const char // But the caller has the option to do this on his/her own. // So, let's do the fastest here and let the caller decide the flow of calls. - NAME_VALUE *nv, **pnv = hashtable_insert_unsafe(dict, name, name_len); - if(likely(*pnv == 0)) { - // a new item added to the index - nv = *pnv = namevalue_create_unsafe(dict, name, name_len, value, value_len); - hashtable_inserted_name_value_unsafe(dict, nv); - linkedlist_namevalue_link_unsafe(dict, nv); - nv->flags |= NAME_VALUE_FLAG_NEW_OR_UPDATED; - } - else { - // the item is already in the index - // so, either we will return the old one - // or overwrite the value, depending on dictionary flags + dictionary_index_lock_wrlock(dict); - nv = *pnv; + bool added_or_updated = false; + size_t spins = 0; + DICTIONARY_ITEM *item = NULL; + do { + DICTIONARY_ITEM **item_pptr = (DICTIONARY_ITEM **)hashtable_insert_unsafe(dict, name, name_len); + if (likely(*item_pptr == NULL)) { + // a new item added to the index - if(!(dict->flags & DICTIONARY_FLAG_DONT_OVERWRITE_VALUE)) { - namevalue_reset_unsafe(dict, nv, value, value_len); - nv->flags |= NAME_VALUE_FLAG_NEW_OR_UPDATED; - } + // create the dictionary item + item = *item_pptr = + dict_item_create_with_hooks(dict, name, name_len, value, value_len, constructor_data, master_item); - else if(dict->conflict_callback) { - dict->conflict_callback(namevalue_get_name(nv), nv->value, value, dict->conflict_callback_data); - nv->flags |= NAME_VALUE_FLAG_NEW_OR_UPDATED; - } + pointer_add(dict, item); + + // call the hashtable react + hashtable_inserted_item_unsafe(dict, item); + + // unlock the index lock, before we add it to the linked list + // DONT DO IT THE OTHER WAY AROUND - DO NOT CROSS THE LOCKS! + dictionary_index_wrlock_unlock(dict); + + item_linked_list_add(dict, item); + added_or_updated = true; + } else { - // make sure this flag is not set - nv->flags &= ~NAME_VALUE_FLAG_NEW_OR_UPDATED; + pointer_check(dict, *item_pptr); + + if(item_check_and_acquire_advanced(dict, *item_pptr, true) != RC_ITEM_OK) { + spins++; + continue; + } + + // the item is already in the index + // so, either we will return the old one + // or overwrite the value, depending on dictionary flags + + // We should not compare the values here! + // even if they are the same, we have to do the whole job + // so that the callbacks will be called. + + item = *item_pptr; + + if(is_view_dictionary(dict)) { + // view dictionary + // the item is already there and can be used + if(item->shared != master_item->shared) + error("DICTIONARY: changing the master item on a view is not supported. The previous item will remain. To change the key of an item in a view, delete it and add it again."); + } + else { + // master dictionary + // the user wants to reset its value + + if (!(dict->options & DICT_OPTION_DONT_OVERWRITE_VALUE)) { + dict_item_reset_value_with_hooks(dict, item, value, value_len, constructor_data); + added_or_updated = true; + } + + else if (dictionary_execute_conflict_callback(dict, item, value, constructor_data)) { + dictionary_version_increment(dict); + added_or_updated = true; + } + + else { + // conflict callback returned false + // we did really nothing! + ; + } + } + + dictionary_index_wrlock_unlock(dict); } - } + } while(!item); + + + if(unlikely(spins > 0 && dict->stats)) + DICTIONARY_STATS_INSERT_SPINS_PLUS(dict, spins); - return nv; + if(is_master_dictionary(dict) && added_or_updated) + dictionary_execute_react_callback(dict, item, constructor_data); + + return item; } -static NAME_VALUE *dictionary_get_name_value_unsafe(DICTIONARY *dict, const char *name) { - if(unlikely(!name)) { - internal_error(true, "attempted to dictionary_get() without a name"); +static DICTIONARY_ITEM *dict_item_find_and_acquire(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(unlikely(!name || !*name)) { + internal_error( + true, + "DICTIONARY: attempted to %s() without a name on a dictionary created from %s() %zu@%s.", + __FUNCTION__, + dict->creation_function, + dict->creation_line, + dict->creation_file); return NULL; } - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_get() on a destroyed dictionary"); return NULL; } - size_t name_len = strlen(name) + 1; // we need the terminating null too + if(name_len == -1) + name_len = (ssize_t)strlen(name) + 1; // we need the terminating null too debug(D_DICTIONARY, "GET dictionary entry with name '%s'.", name); - NAME_VALUE *nv = hashtable_get_unsafe(dict, name, name_len); - if(unlikely(!nv)) { - debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); - return NULL; + dictionary_index_lock_rdlock(dict); + + DICTIONARY_ITEM *item = hashtable_get_unsafe(dict, name, name_len); + if(unlikely(item && !item_check_and_acquire(dict, item))) { + item = NULL; + DICTIONARY_STATS_SEARCH_IGNORES_PLUS1(dict); } - debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); - return nv; + dictionary_index_rdlock_unlock(dict); + + return item; } // ---------------------------------------------------------------------------- -// API - items management +// delayed destruction of dictionaries + +static bool dictionary_free_all_resources(DICTIONARY *dict, size_t *mem, bool force) { + if(mem) + *mem = 0; + + if(!force && dictionary_referenced_items(dict)) + return false; + + size_t dict_size = 0, counted_items = 0, item_size = 0, index_size = 0; + (void)counted_items; + +#ifdef NETDATA_INTERNAL_CHECKS + long int entries = dict->entries; + long int referenced_items = dict->referenced_items; + long int pending_deletion_items = dict->pending_deletion_items; + const char *creation_function = dict->creation_function; + const char *creation_file = dict->creation_file; + size_t creation_line = dict->creation_line; +#endif + + // destroy the index + dictionary_index_lock_wrlock(dict); + index_size += hashtable_destroy_unsafe(dict); + dictionary_index_wrlock_unlock(dict); + + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + DICTIONARY_ITEM *item = dict->items.list; + while (item) { + // cache item->next + // because we are going to free item + DICTIONARY_ITEM *item_next = item->next; -void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - NAME_VALUE *nv = dictionary_set_name_value_unsafe(dict, name, value, value_len); + item_size += dict_item_free_with_hooks(dict, item); + item = item_next; - if(unlikely(dict->react_callback && nv && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) { - // we need to call the react callback with a reference counter on nv - reference_counter_acquire(dict, nv); - dict->react_callback(namevalue_get_name(nv), nv->value, dict->react_callback_data); - reference_counter_release(dict, nv, false); + // to speed up destruction, we don't + // unlink item from the linked-list here + + counted_items++; } + dict->items.list = NULL; + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); + + dict_size += dictionary_locks_destroy(dict); + dict_size += reference_counter_free(dict); + dict_size += dictionary_hooks_free(dict); + dict_size += sizeof(DICTIONARY); + DICTIONARY_STATS_MINUS_MEMORY(dict, 0, sizeof(DICTIONARY), 0); + + freez(dict); + + internal_error( + false, + "DICTIONARY: Freed dictionary created from %s() %zu@%s, having %ld (counted %zu) entries, %ld referenced, %ld pending deletion, total freed memory: %zu bytes (sizeof(dict) = %zu, sizeof(item) = %zu).", + creation_function, + creation_line, + creation_file, + entries, counted_items, referenced_items, pending_deletion_items, + dict_size + item_size, sizeof(DICTIONARY), sizeof(DICTIONARY_ITEM) + sizeof(DICTIONARY_ITEM_SHARED)); + + if(mem) + *mem = dict_size + item_size + index_size; - return nv ? nv->value : NULL; + return true; } -void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - NAME_VALUE *nv = dictionary_set_name_value_unsafe(dict, name, value, value_len); +netdata_mutex_t dictionaries_waiting_to_be_destroyed_mutex = NETDATA_MUTEX_INITIALIZER; +static DICTIONARY *dictionaries_waiting_to_be_destroyed = NULL; + +void dictionary_queue_for_destruction(DICTIONARY *dict) { + if(is_dictionary_destroyed(dict)) + return; - // we need to get a reference counter for the react callback - // before we unlock the dictionary - if(unlikely(dict->react_callback && nv && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) - reference_counter_acquire(dict, nv); + DICTIONARY_STATS_DICT_DESTROY_QUEUED_PLUS1(dict); + dict_flag_set(dict, DICT_FLAG_DESTROYED); - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + netdata_mutex_lock(&dictionaries_waiting_to_be_destroyed_mutex); - if(unlikely(dict->react_callback && nv && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) { - // we got the reference counter we need, above - dict->react_callback(namevalue_get_name(nv), nv->value, dict->react_callback_data); - reference_counter_release(dict, nv, false); - } + dict->next = dictionaries_waiting_to_be_destroyed; + dictionaries_waiting_to_be_destroyed = dict; - return nv ? nv->value : NULL; + netdata_mutex_unlock(&dictionaries_waiting_to_be_destroyed_mutex); } -DICTIONARY_ITEM *dictionary_set_and_acquire_item_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - NAME_VALUE *nv = dictionary_set_name_value_unsafe(dict, name, value, value_len); +void cleanup_destroyed_dictionaries(void) { + if(!dictionaries_waiting_to_be_destroyed) + return; - if(unlikely(!nv)) - return NULL; + netdata_mutex_lock(&dictionaries_waiting_to_be_destroyed_mutex); + + DICTIONARY *dict, *last = NULL, *next = NULL; + for(dict = dictionaries_waiting_to_be_destroyed; dict ; dict = next) { + next = dict->next; - reference_counter_acquire(dict, nv); +#ifdef NETDATA_INTERNAL_CHECKS + size_t line = dict->creation_line; + const char *file = dict->creation_file; + const char *function = dict->creation_function; +#endif - if(unlikely(dict->react_callback && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) { - dict->react_callback(namevalue_get_name(nv), nv->value, dict->react_callback_data); + DICTIONARY_STATS_DICT_DESTROY_QUEUED_MINUS1(dict); + if(dictionary_free_all_resources(dict, NULL, false)) { + + internal_error( + true, + "DICTIONARY: freed dictionary with delayed destruction, created from %s() %zu@%s.", + function, line, file); + + if(last) last->next = next; + else dictionaries_waiting_to_be_destroyed = next; + } + else { + DICTIONARY_STATS_DICT_DESTROY_QUEUED_PLUS1(dict); + last = dict; + } } - return (DICTIONARY_ITEM *)nv; + netdata_mutex_unlock(&dictionaries_waiting_to_be_destroyed_mutex); } -DICTIONARY_ITEM *dictionary_set_and_acquire_item(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - NAME_VALUE *nv = dictionary_set_name_value_unsafe(dict, name, value, value_len); +// ---------------------------------------------------------------------------- +// API internal checks - // we need to get the reference counter before we unlock - if(nv) reference_counter_acquire(dict, nv); +#ifdef NETDATA_INTERNAL_CHECKS +#define api_internal_check(dict, item, allow_null_dict, allow_null_item) api_internal_check_with_trace(dict, item, __FUNCTION__, allow_null_dict, allow_null_item) +static inline void api_internal_check_with_trace(DICTIONARY *dict, DICTIONARY_ITEM *item, const char *function, bool allow_null_dict, bool allow_null_item) { + if(!allow_null_dict && !dict) { + internal_error( + item, + "DICTIONARY: attempted to %s() with a NULL dictionary, passing an item created from %s() %zu@%s.", + function, + item->dict->creation_function, + item->dict->creation_line, + item->dict->creation_file); + fatal("DICTIONARY: attempted to %s() but dict is NULL", function); + } - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + if(!allow_null_item && !item) { + internal_error( + true, + "DICTIONARY: attempted to %s() without an item on a dictionary created from %s() %zu@%s.", + function, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); + fatal("DICTIONARY: attempted to %s() but item is NULL", function); + } - if(unlikely(dict->react_callback && nv && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) { - // we already have a reference counter, for the caller, no need for another one - dict->react_callback(namevalue_get_name(nv), nv->value, dict->react_callback_data); + if(dict && item && dict != item->dict) { + internal_error( + true, + "DICTIONARY: attempted to %s() an item on a dictionary created from %s() %zu@%s, but the item belongs to the dictionary created from %s() %zu@%s.", + function, + dict->creation_function, + dict->creation_line, + dict->creation_file, + item->dict->creation_function, + item->dict->creation_line, + item->dict->creation_file + ); + fatal("DICTIONARY: %s(): item does not belong to this dictionary.", function); } - return (DICTIONARY_ITEM *)nv; + if(item) { + REFCOUNT refcount = DICTIONARY_ITEM_REFCOUNT_GET(dict, item); + if (unlikely(refcount <= 0)) { + internal_error( + true, + "DICTIONARY: attempted to %s() of an item with reference counter = %d on a dictionary created from %s() %zu@%s", + function, + refcount, + item->dict->creation_function, + item->dict->creation_line, + item->dict->creation_file); + fatal("DICTIONARY: attempted to %s but item is having refcount = %d", function, refcount); + } + } } +#else +#define api_internal_check(dict, item, allow_null_dict, allow_null_item) debug_dummy() +#endif -void *dictionary_get_unsafe(DICTIONARY *dict, const char *name) { - NAME_VALUE *nv = dictionary_get_name_value_unsafe(dict, name); +#define api_is_name_good(dict, name, name_len) api_is_name_good_with_trace(dict, name, name_len, __FUNCTION__) +static bool api_is_name_good_with_trace(DICTIONARY *dict __maybe_unused, const char *name, ssize_t name_len __maybe_unused, const char *function __maybe_unused) { + if(unlikely(!name)) { + internal_error( + true, + "DICTIONARY: attempted to %s() with name = NULL on a dictionary created from %s() %zu@%s.", + function, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); + return false; + } - if(unlikely(!nv)) - return NULL; + if(unlikely(!*name)) { + internal_error( + true, + "DICTIONARY: attempted to %s() with empty name on a dictionary created from %s() %zu@%s.", + function, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); + return false; + } - return nv->value; -} + internal_error( + name_len > 0 && name_len != (ssize_t)(strlen(name) + 1), + "DICTIONARY: attempted to %s() with a name of '%s', having length of %zu (incl. '\\0'), but the supplied name_len = %ld, on a dictionary created from %s() %zu@%s.", + function, + name, + strlen(name) + 1, + (long int) name_len, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); + + internal_error( + name_len <= 0 && name_len != -1, + "DICTIONARY: attempted to %s() with a name of '%s', having length of %zu (incl. '\\0'), but the supplied name_len = %ld, on a dictionary created from %s() %zu@%s.", + function, + name, + strlen(name) + 1, + (long int) name_len, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); -void *dictionary_get(DICTIONARY *dict, const char *name) { - dictionary_lock(dict, DICTIONARY_LOCK_READ); - void *ret = dictionary_get_unsafe(dict, name); - dictionary_unlock(dict, DICTIONARY_LOCK_READ); - return ret; + return true; } -DICTIONARY_ITEM *dictionary_get_and_acquire_item_unsafe(DICTIONARY *dict, const char *name) { - NAME_VALUE *nv = dictionary_get_name_value_unsafe(dict, name); +// ---------------------------------------------------------------------------- +// API - dictionary management - if(unlikely(!nv)) - return NULL; +static DICTIONARY *dictionary_create_internal(DICT_OPTIONS options, struct dictionary_stats *stats) { + cleanup_destroyed_dictionaries(); - reference_counter_acquire(dict, nv); - return (DICTIONARY_ITEM *)nv; -} + DICTIONARY *dict = callocz(1, sizeof(DICTIONARY)); + dict->options = options; + dict->stats = stats; -DICTIONARY_ITEM *dictionary_get_and_acquire_item(DICTIONARY *dict, const char *name) { - dictionary_lock(dict, DICTIONARY_LOCK_READ); - void *ret = dictionary_get_and_acquire_item_unsafe(dict, name); - dictionary_unlock(dict, DICTIONARY_LOCK_READ); - return ret; -} + size_t dict_size = 0; + dict_size += sizeof(DICTIONARY); + dict_size += dictionary_locks_init(dict); + dict_size += reference_counter_init(dict); + dict_size += hashtable_init_unsafe(dict); -DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY_ITEM *item) { - if(unlikely(!item)) return NULL; - reference_counter_increase((NAME_VALUE *)item); - return item; -} + pointer_index_init(dict); -const char *dictionary_acquired_item_name(DICTIONARY_ITEM *item) { - if(unlikely(!item)) return NULL; - return namevalue_get_name((NAME_VALUE *)item); -} + DICTIONARY_STATS_PLUS_MEMORY(dict, 0, dict_size, 0); -void *dictionary_acquired_item_value(DICTIONARY_ITEM *item) { - if(unlikely(!item)) return NULL; - return ((NAME_VALUE *)item)->value; + return dict; } -void dictionary_acquired_item_release_unsafe(DICTIONARY *dict, DICTIONARY_ITEM *item) { - if(unlikely(!item)) return; +#ifdef NETDATA_INTERNAL_CHECKS +DICTIONARY *dictionary_create_advanced_with_trace(DICT_OPTIONS options, struct dictionary_stats *stats, const char *function, size_t line, const char *file) { +#else +DICTIONARY *dictionary_create_advanced(DICT_OPTIONS options, struct dictionary_stats *stats) { +#endif + + DICTIONARY *dict = dictionary_create_internal(options, stats?stats:&dictionary_stats_category_other); #ifdef NETDATA_INTERNAL_CHECKS - if(((NAME_VALUE *)item)->dict != dict) - fatal("DICTIONARY: %s(): name_value item with name '%s' does not belong to this dictionary", __FUNCTION__, namevalue_get_name((NAME_VALUE *)item)); + dict->creation_function = function; + dict->creation_file = file; + dict->creation_line = line; #endif - reference_counter_release(dict, (NAME_VALUE *)item, false); + DICTIONARY_STATS_DICT_CREATIONS_PLUS1(dict); + return dict; } -void dictionary_acquired_item_release(DICTIONARY *dict, DICTIONARY_ITEM *item) { - if(unlikely(!item)) return; +#ifdef NETDATA_INTERNAL_CHECKS +DICTIONARY *dictionary_create_view_with_trace(DICTIONARY *master, const char *function, size_t line, const char *file) { +#else +DICTIONARY *dictionary_create_view(DICTIONARY *master) { +#endif + + DICTIONARY *dict = dictionary_create_internal(master->options, master->stats); + dict->master = master; + + dictionary_hooks_allocate(master); + + if(unlikely(__atomic_load_n(&master->hooks->links, __ATOMIC_SEQ_CST)) < 1) + fatal("DICTIONARY: attempted to create a view that has %d links", master->hooks->links); + + dict->hooks = master->hooks; + __atomic_add_fetch(&master->hooks->links, 1, __ATOMIC_SEQ_CST); #ifdef NETDATA_INTERNAL_CHECKS - if(((NAME_VALUE *)item)->dict != dict) - fatal("DICTIONARY: %s(): name_value item with name '%s' does not belong to this dictionary", __FUNCTION__, namevalue_get_name((NAME_VALUE *)item)); + dict->creation_function = function; + dict->creation_file = file; + dict->creation_line = line; #endif - // no need to get a lock here - // we pass the last parameter to reference_counter_release() as true - // so that the release may get a write-lock if required to clean up + DICTIONARY_STATS_DICT_CREATIONS_PLUS1(dict); + return dict; +} - reference_counter_release(dict, (NAME_VALUE *)item, true); +void dictionary_flush(DICTIONARY *dict) { + if(unlikely(!dict)) + return; - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) - dictionary_destroy(dict); + void *value; + dfe_start_write(dict, value) { + dictionary_del_advanced(dict, item_get_name(value_dfe.item), (ssize_t)item_get_name_len(value_dfe.item) + 1); + } + dfe_done(value); + + DICTIONARY_STATS_DICT_FLUSHES_PLUS1(dict); } -int dictionary_del_unsafe(DICTIONARY *dict, const char *name) { - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { - internal_error(true, "DICTIONARY: attempted to dictionary_del() on a destroyed dictionary"); - return -1; +size_t dictionary_destroy(DICTIONARY *dict) { + cleanup_destroyed_dictionaries(); + + if(!dict) return 0; + + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + + dict_flag_set(dict, DICT_FLAG_DESTROYED); + DICTIONARY_STATS_DICT_DESTRUCTIONS_PLUS1(dict); + + size_t referenced_items = dictionary_referenced_items(dict); + if(referenced_items) { + dictionary_flush(dict); + dictionary_queue_for_destruction(dict); + + internal_error( + true, + "DICTIONARY: delaying destruction of dictionary created from %s() %zu@%s, because it has %ld referenced items in it (%ld total).", + dict->creation_function, + dict->creation_line, + dict->creation_file, + dict->referenced_items, + dict->entries); + + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); + return 0; } - if(unlikely(!name || !*name)) { - internal_error(true, "DICTIONARY: attempted to dictionary_del() without a name"); - return -1; + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); + + size_t freed; + dictionary_free_all_resources(dict, &freed, true); + + return freed; +} + +// ---------------------------------------------------------------------------- +// SET an item to the dictionary + +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) { + if(unlikely(!api_is_name_good(dict, name, name_len))) + return NULL; + + api_internal_check(dict, NULL, false, true); + + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: this dictionary is a view, you cannot add items other than the ones from the master dictionary."); + + DICTIONARY_ITEM *item = + dict_item_add_or_reset_value_and_acquire(dict, name, name_len, value, value_len, constructor_data, NULL); + api_internal_check(dict, item, false, false); + return item; +} + +void *dictionary_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data) { + DICTIONARY_ITEM *item = dictionary_set_and_acquire_item_advanced(dict, name, name_len, value, value_len, constructor_data); + + if(likely(item)) { + void *v = item->shared->value; + item_release(dict, item); + return v; } - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: INTERNAL ERROR: deleting dictionary item '%s' without exclusive access to dictionary", name); + return NULL; +} + +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_view_set_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICTIONARY_ITEM *master_item) { + if(unlikely(!api_is_name_good(dict, name, name_len))) + return NULL; - size_t name_len = strlen(name) + 1; // we need the terminating null too + api_internal_check(dict, NULL, false, true); - debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); + if(unlikely(is_master_dictionary(dict))) + fatal("DICTIONARY: this dictionary is a master, you cannot add items from other dictionaries."); - // Unfortunately, the JudyHSDel() does not return the value of the - // item that was deleted, so we have to find it before we delete it, - // since we need to release our structures too. + dictionary_acquired_item_dup(dict->master, master_item); + DICTIONARY_ITEM *item = dict_item_add_or_reset_value_and_acquire(dict, name, name_len, NULL, 0, NULL, master_item); + dictionary_acquired_item_release(dict->master, master_item); - int ret; - NAME_VALUE *nv = hashtable_get_unsafe(dict, name, name_len); - if(unlikely(!nv)) { - debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); - ret = -1; + api_internal_check(dict, item, false, false); + return item; +} + +void *dictionary_view_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICTIONARY_ITEM *master_item) { + DICTIONARY_ITEM *item = dictionary_view_set_and_acquire_item_advanced(dict, name, name_len, master_item); + + if(likely(item)) { + void *v = item->shared->value; + item_release(dict, item); + return v; } - else { - debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); - if(hashtable_delete_unsafe(dict, name, name_len, nv) == 0) - error("DICTIONARY: INTERNAL ERROR: tried to delete item with name '%s' that is not in the index", name); + return NULL; +} - if(name_value_can_be_deleted(dict, nv)) { - linkedlist_namevalue_unlink_unsafe(dict, nv); - namevalue_destroy_unsafe(dict, nv); - } - else - nv->flags |= NAME_VALUE_FLAG_DELETED; +// ---------------------------------------------------------------------------- +// GET an item from the dictionary - ret = 0; +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_get_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(unlikely(!api_is_name_good(dict, name, name_len))) + return NULL; - DICTIONARY_STATS_ENTRIES_MINUS1(dict); + api_internal_check(dict, NULL, false, true); + DICTIONARY_ITEM *item = dict_item_find_and_acquire(dict, name, name_len); + api_internal_check(dict, item, false, true); + return item; +} + +void *dictionary_get_advanced(DICTIONARY *dict, const char *name, ssize_t name_len) { + DICTIONARY_ITEM *item = dictionary_get_and_acquire_item_advanced(dict, name, name_len); + if(likely(item)) { + void *v = item->shared->value; + item_release(dict, item); + return v; } - return ret; + + return NULL; } -int dictionary_del(DICTIONARY *dict, const char *name) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - int ret = dictionary_del_unsafe(dict, name); - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); - return ret; +// ---------------------------------------------------------------------------- +// DUP/REL an item (increase/decrease its reference counter) + +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item) { + // we allow the item to be NULL here + api_internal_check(dict, item, false, true); + + if(likely(item)) { + item_acquire(dict, item); + api_internal_check(dict, item, false, false); + } + + return item; +} + +void dictionary_acquired_item_release(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item) { + // we allow the item to be NULL here + api_internal_check(dict, item, false, true); + + // no need to get a lock here + // we pass the last parameter to reference_counter_release() as true + // so that the release may get a write-lock if required to clean up + + if(likely(item)) + item_release(dict, item); +} + +// ---------------------------------------------------------------------------- +// get the name/value of an item + +const char *dictionary_acquired_item_name(DICT_ITEM_CONST DICTIONARY_ITEM *item) { + return item_get_name(item); +} + +void *dictionary_acquired_item_value(DICT_ITEM_CONST DICTIONARY_ITEM *item) { + if(likely(item)) + return item->shared->value; + + return NULL; +} + +size_t dictionary_acquired_item_references(DICT_ITEM_CONST DICTIONARY_ITEM *item) { + if(likely(item)) + return DICTIONARY_ITEM_REFCOUNT_GET_SOLE(item); + + return 0; +} + +// ---------------------------------------------------------------------------- +// DEL an item + +bool dictionary_del_advanced(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(unlikely(!api_is_name_good(dict, name, name_len))) + return false; + + api_internal_check(dict, NULL, false, true); + return dict_item_del(dict, name, name_len); } // ---------------------------------------------------------------------------- @@ -1245,150 +2201,165 @@ int dictionary_del(DICTIONARY *dict, const char *name) { void *dictionary_foreach_start_rw(DICTFE *dfe, DICTIONARY *dict, char rw) { if(unlikely(!dfe || !dict)) return NULL; - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_foreach_start_rw() on a destroyed dictionary"); - dfe->last_item = NULL; + dfe->counter = 0; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; return NULL; } + dfe->counter = 0; dfe->dict = dict; dfe->rw = rw; - dfe->started_ut = now_realtime_usec(); - dictionary_lock(dict, dfe->rw); + ll_recursive_lock(dict, dfe->rw); - DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict); + DICTIONARY_STATS_TRAVERSALS_PLUS1(dict); // get the first item from the list - NAME_VALUE *nv = dict->first_item; + DICTIONARY_ITEM *item = dict->items.list; // skip all the deleted items - while(nv && (nv->flags & NAME_VALUE_FLAG_DELETED)) - nv = nv->next; + while(item && !item_check_and_acquire(dict, item)) + item = item->next; - if(likely(nv)) { - dfe->last_item = nv; - dfe->name = (char *)namevalue_get_name(nv); - dfe->value = nv->value; - reference_counter_acquire(dict, nv); + if(likely(item)) { + dfe->item = item; + dfe->name = (char *)item_get_name(item); + dfe->value = item->shared->value; } else { - dfe->last_item = NULL; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; } + if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_unlock(dfe->dict, dfe->rw); + return dfe->value; } void *dictionary_foreach_next(DICTFE *dfe) { if(unlikely(!dfe || !dfe->dict)) return NULL; - if(unlikely(dfe->dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dfe->dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_foreach_next() on a destroyed dictionary"); - dfe->last_item = NULL; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; return NULL; } + if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_lock(dfe->dict, dfe->rw); + // the item we just did - NAME_VALUE *nv = (NAME_VALUE *)dfe->last_item; + DICTIONARY_ITEM *item = dfe->item; // get the next item from the list - NAME_VALUE *nv_next = (nv) ? nv->next : NULL; + DICTIONARY_ITEM *item_next = (item) ? item->next : NULL; - // skip all the deleted items - while(nv_next && (nv_next->flags & NAME_VALUE_FLAG_DELETED)) - nv_next = nv_next->next; + // skip all the deleted items until one that can be acquired is found + while(item_next && !item_check_and_acquire(dfe->dict, item_next)) + item_next = item_next->next; - // release the old, so that it can possibly be deleted - if(likely(nv)) - reference_counter_release(dfe->dict, nv, false); + if(likely(item)) { + dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dfe->dict, item, dfe->rw); + // item_release(dfe->dict, item); + } - if(likely(nv = nv_next)) { - dfe->last_item = nv; - dfe->name = (char *)namevalue_get_name(nv); - dfe->value = nv->value; - reference_counter_acquire(dfe->dict, nv); + item = item_next; + if(likely(item)) { + dfe->item = item; + dfe->name = (char *)item_get_name(item); + dfe->value = item->shared->value; + dfe->counter++; } else { - dfe->last_item = NULL; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; } + if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_unlock(dfe->dict, dfe->rw); + return dfe->value; } -usec_t dictionary_foreach_done(DICTFE *dfe) { - if(unlikely(!dfe || !dfe->dict)) return 0; +void dictionary_foreach_done(DICTFE *dfe) { + if(unlikely(!dfe || !dfe->dict)) return; - if(unlikely(dfe->dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dfe->dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_foreach_next() on a destroyed dictionary"); - return 0; + return; } // the item we just did - NAME_VALUE *nv = (NAME_VALUE *)dfe->last_item; + DICTIONARY_ITEM *item = dfe->item; // release it, so that it can possibly be deleted - if(likely(nv)) - reference_counter_release(dfe->dict, nv, false); + if(likely(item)) { + dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dfe->dict, item, dfe->rw); + // item_release(dfe->dict, item); + } + + if(likely(dfe->rw != DICTIONARY_LOCK_REENTRANT)) + ll_recursive_unlock(dfe->dict, dfe->rw); - dictionary_unlock(dfe->dict, dfe->rw); dfe->dict = NULL; - dfe->last_item = NULL; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; - - usec_t usec = now_realtime_usec() - dfe->started_ut; - dfe->started_ut = 0; - - return usec; + dfe->counter = 0; } // ---------------------------------------------------------------------------- -// API - walk through the dictionary -// the dictionary is locked for reading while this happens +// API - walk through the dictionary. +// The dictionary is locked for reading while this happens // do not use other dictionary calls while walking the dictionary - deadlock! -int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const char *name, void *entry, void *data), void *data) { - if(unlikely(!dict)) return 0; +int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const DICTIONARY_ITEM *item, void *entry, void *data), void *data) { + if(unlikely(!dict || !callback)) return 0; - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_walkthrough_rw() on a destroyed dictionary"); return 0; } - dictionary_lock(dict, rw); + ll_recursive_lock(dict, rw); DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict); // written in such a way, that the callback can delete the active element int ret = 0; - NAME_VALUE *nv = dict->first_item, *nv_next; - while(nv) { + DICTIONARY_ITEM *item = dict->items.list, *item_next; + while(item) { // skip the deleted items - if(unlikely(nv->flags & NAME_VALUE_FLAG_DELETED)) { - nv = nv->next; + if(unlikely(!item_check_and_acquire(dict, item))) { + item = item->next; continue; } - // get a reference counter, so that our item will not be deleted - // while we are using it - reference_counter_acquire(dict, nv); + if(unlikely(rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_unlock(dict, rw); - int r = callback(namevalue_get_name(nv), nv->value, data); + int r = callback(item, item->shared->value, data); + + if(unlikely(rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_lock(dict, rw); // since we have a reference counter, this item cannot be deleted // until we release the reference counter, so the pointers are there - nv_next = nv->next; - reference_counter_release(dict, nv, false); + item_next = item->next; + + dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dict, item, rw); + // item_release(dict, item); if(unlikely(r < 0)) { ret = r; @@ -1397,10 +2368,10 @@ int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const c ret += r; - nv = nv_next; + item = item_next; } - dictionary_unlock(dict, rw); + ll_recursive_unlock(dict, rw); return ret; } @@ -1408,238 +2379,114 @@ int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const c // ---------------------------------------------------------------------------- // sorted walkthrough -static int dictionary_sort_compar(const void *nv1, const void *nv2) { - return strcmp(namevalue_get_name((*(NAME_VALUE **)nv1)), namevalue_get_name((*(NAME_VALUE **)nv2))); +typedef int (*qsort_compar)(const void *item1, const void *item2); + +static int dictionary_sort_compar(const void *item1, const void *item2) { + return strcmp(item_get_name((*(DICTIONARY_ITEM **)item1)), item_get_name((*(DICTIONARY_ITEM **)item2))); } -int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const char *name, void *entry, void *data), void *data) { - if(unlikely(!dict || !dict->entries)) return 0; +int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const DICTIONARY_ITEM *item, void *entry, void *data), void *data, dictionary_sorted_compar compar) { + if(unlikely(!dict || !callback)) return 0; - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_sorted_walkthrough_rw() on a destroyed dictionary"); return 0; } - dictionary_lock(dict, rw); - dictionary_defer_all_deletions_unsafe(dict, rw); - DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict); - size_t count = dict->entries; - NAME_VALUE **array = mallocz(sizeof(NAME_VALUE *) * count); + ll_recursive_lock(dict, rw); + size_t entries = __atomic_load_n(&dict->entries, __ATOMIC_SEQ_CST); + DICTIONARY_ITEM **array = mallocz(sizeof(DICTIONARY_ITEM *) * entries); size_t i; - NAME_VALUE *nv; - for(nv = dict->first_item, i = 0; nv && i < count ;nv = nv->next) { - if(likely(!(nv->flags & NAME_VALUE_FLAG_DELETED))) - array[i++] = nv; + DICTIONARY_ITEM *item; + for(item = dict->items.list, i = 0; item && i < entries; item = item->next) { + if(likely(item_check_and_acquire(dict, item))) + array[i++] = item; } + ll_recursive_unlock(dict, rw); - internal_error(nv != NULL, "DICTIONARY: during sorting expected to have %zu items in dictionary, but there are more. Sorted results may be incomplete. Dictionary fails to maintain an accurate number of the number of entries it has.", count); + if(unlikely(i != entries)) + entries = i; - if(unlikely(i != count)) { - internal_error(true, "DICTIONARY: during sorting expected to have %zu items in dictionary, but there are %zu. Sorted results may be incomplete. Dictionary fails to maintain an accurate number of the number of entries it has.", count, i); - count = i; - } + if(compar) + qsort(array, entries, sizeof(DICTIONARY_ITEM *), (qsort_compar)compar); + else + qsort(array, entries, sizeof(DICTIONARY_ITEM *), dictionary_sort_compar); - qsort(array, count, sizeof(NAME_VALUE *), dictionary_sort_compar); + bool callit = true; + int ret = 0, r; + for(i = 0; i < entries ;i++) { + item = array[i]; - int ret = 0; - for(i = 0; i < count ;i++) { - nv = array[i]; - if(likely(!(nv->flags & NAME_VALUE_FLAG_DELETED))) { - reference_counter_acquire(dict, nv); - int r = callback(namevalue_get_name(nv), nv->value, data); - reference_counter_release(dict, nv, false); - if (r < 0) { - ret = r; - break; - } - ret += r; + if(callit) + r = callback(item, item->shared->value, data); + + dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dict, item, rw); + // item_release(dict, item); + + if(r < 0) { + ret = r; + r = 0; + + // stop calling the callback, + // but we have to continue, to release all the reference counters + callit = false; } + else + ret += r; } - dictionary_restore_all_deletions_unsafe(dict, rw); - dictionary_unlock(dict, rw); freez(array); return ret; } // ---------------------------------------------------------------------------- -// STRING implementation - dedup all STRINGs +// THREAD_CACHE -typedef struct string_entry { -#ifdef DICTIONARY_WITH_AVL - avl_t avl_node; -#endif - uint32_t length; // the string length with the terminating '\0' - uint32_t refcount; // how many times this string is used - const char str[]; // the string itself -} STRING_ENTRY; +static __thread Pvoid_t thread_cache_judy_array = NULL; -#ifdef DICTIONARY_WITH_AVL -static int string_entry_compare(void* a, void* b) { - return strcmp(((STRING_ENTRY *)a)->str, ((STRING_ENTRY *)b)->str); -} - -static void *get_thread_static_string_entry(const char *name) { - static __thread size_t _length = 0; - static __thread STRING_ENTRY *_tmp = NULL; +void *thread_cache_entry_get_or_set(void *key, + ssize_t key_length, + void *value, + void *(*transform_the_value_before_insert)(void *key, size_t key_length, void *value) + ) { + if(unlikely(!key || !key_length)) return NULL; - size_t size = sizeof(STRING_ENTRY) + strlen(name) + 1; - if(likely(_tmp && _length < size)) { - freez(_tmp); - _tmp = NULL; - _length = 0; - } + if(key_length == -1) + key_length = (ssize_t)strlen((char *)key) + 1; - if(unlikely(!_tmp)) { - _tmp = callocz(1, size); - _length = size; + JError_t J_Error; + Pvoid_t *Rc = JudyHSIns(&thread_cache_judy_array, key, key_length, &J_Error); + if (unlikely(Rc == PJERR)) { + fatal("THREAD_CACHE: Cannot insert entry to JudyHS, JU_ERRNO_* == %u, ID == %d", + JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); } - strcpy((char *)&_tmp->str[0], name); - return _tmp; -} -#endif - -DICTIONARY string_dictionary = { -#ifdef DICTIONARY_WITH_AVL - .values_index = { - .root = NULL, - .compar = string_entry_compare - }, - .get_thread_static_name_value = get_thread_static_string_entry, -#endif - - .flags = DICTIONARY_FLAG_EXCLUSIVE_ACCESS, - .rwlock = NETDATA_RWLOCK_INITIALIZER -}; - -static netdata_mutex_t string_mutex = NETDATA_MUTEX_INITIALIZER; - -STRING *string_dup(STRING *string) { - if(unlikely(!string)) return NULL; - - STRING_ENTRY *se = (STRING_ENTRY *)string; - netdata_mutex_lock(&string_mutex); - se->refcount++; - netdata_mutex_unlock(&string_mutex); - return string; -} - -STRING *string_strdupz(const char *str) { - if(unlikely(!str || !*str)) return NULL; + if(*Rc == 0) { + // new item added - netdata_mutex_lock(&string_mutex); - - size_t length = strlen(str) + 1; - STRING_ENTRY *se; - STRING_ENTRY **ptr = (STRING_ENTRY **)hashtable_insert_unsafe(&string_dictionary, str, length); - if(unlikely(*ptr == 0)) { - // a new item added to the index - size_t mem_size = sizeof(STRING_ENTRY) + length; - se = mallocz(mem_size); - strcpy((char *)se->str, str); - se->length = length; - se->refcount = 1; - *ptr = se; - hashtable_inserted_name_value_unsafe(&string_dictionary, se); - string_dictionary.version++; - string_dictionary.inserts++; - string_dictionary.entries++; - string_dictionary.memory += (long)mem_size; - } - else { - // the item is already in the index - se = *ptr; - se->refcount++; - string_dictionary.searches++; + *Rc = (transform_the_value_before_insert) ? transform_the_value_before_insert(key, key_length, value) : value; } - netdata_mutex_unlock(&string_mutex); - return (STRING *)se; + return *Rc; } -void string_freez(STRING *string) { - if(unlikely(!string)) return; - netdata_mutex_lock(&string_mutex); - - STRING_ENTRY *se = (STRING_ENTRY *)string; +void thread_cache_destroy(void) { + if(unlikely(!thread_cache_judy_array)) return; - if(se->refcount == 0) - fatal("STRING: tried to free string that has zero references."); - - se->refcount--; - if(unlikely(se->refcount == 0)) { - if(hashtable_delete_unsafe(&string_dictionary, se->str, se->length, se) == 0) - error("STRING: INTERNAL ERROR: tried to delete '%s' that is not in the index", se->str); - - size_t mem_size = sizeof(STRING_ENTRY) + se->length; - freez(se); - string_dictionary.version++; - string_dictionary.deletes++; - string_dictionary.entries--; - string_dictionary.memory -= (long)mem_size; - } - - netdata_mutex_unlock(&string_mutex); -} - -size_t string_length(STRING *string) { - if(unlikely(!string)) return 0; - return ((STRING_ENTRY *)string)->length - 1; -} - -const char *string2str(STRING *string) { - if(unlikely(!string)) return ""; - return ((STRING_ENTRY *)string)->str; -} - -STRING *string_2way_merge(STRING *a, STRING *b) { - static STRING *X = NULL; - - if(unlikely(!X)) { - X = string_strdupz("[x]"); + JError_t J_Error; + Word_t ret = JudyHSFreeArray(&thread_cache_judy_array, &J_Error); + if(unlikely(ret == (Word_t) JERR)) { + error("THREAD_CACHE: Cannot destroy JudyHS, JU_ERRNO_* == %u, ID == %d", + JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); } - if(unlikely(a == b)) return string_dup(a); - if(unlikely(a == X)) return string_dup(a); - if(unlikely(b == X)) return string_dup(b); - if(unlikely(!a)) return string_dup(X); - if(unlikely(!b)) return string_dup(X); - - size_t alen = string_length(a); - size_t blen = string_length(b); - size_t length = alen + blen + string_length(X) + 1; - char buf1[length + 1], buf2[length + 1], *dst1; - const char *s1, *s2; - - s1 = string2str(a); - s2 = string2str(b); - dst1 = buf1; - for( ; *s1 && *s2 && *s1 == *s2 ;s1++, s2++) - *dst1++ = *s1; - - *dst1 = '\0'; + internal_error(true, "THREAD_CACHE: hash table freed %lu bytes", ret); - if(*s1 != '\0' || *s2 != '\0') { - *dst1++ = '['; - *dst1++ = 'x'; - *dst1++ = ']'; - - s1 = &(string2str(a))[alen - 1]; - s2 = &(string2str(b))[blen - 1]; - char *dst2 = &buf2[length]; - *dst2 = '\0'; - for (; *s1 && *s2 && *s1 == *s2; s1--, s2--) - *(--dst2) = *s1; - - strcpy(dst1, dst2); - } - - return string_strdupz(buf1); + thread_cache_judy_array = NULL; } // ---------------------------------------------------------------------------- @@ -1656,7 +2503,7 @@ static char **dictionary_unittest_generate_names(size_t entries) { char **names = mallocz(sizeof(char *) * entries); for(size_t i = 0; i < entries ;i++) { char buf[25 + 1] = ""; - snprintfz(buf, 25, "name.%zu.0123456789.%zu \t !@#$%%^&*(),./[]{}\\|~`", i, entries / 2 + i); + snprintfz(buf, 25, "name.%zu.0123456789.%zu!@#$%%^&*(),./[]{}\\|~`", i, entries / 2 + i); names[i] = strdupz(buf); } return names; @@ -1686,12 +2533,12 @@ static size_t dictionary_unittest_set_clone(DICTIONARY *dict, char **names, char static size_t dictionary_unittest_set_null(DICTIONARY *dict, char **names, char **values, size_t entries) { (void)values; size_t errors = 0; - long i = 0; - for(; i < (long)entries ;i++) { + size_t i = 0; + for(; i < entries ;i++) { void *val = dictionary_set(dict, names[i], NULL, 0); if(val != NULL) { fprintf(stderr, ">>> %s() returns a non NULL value\n", __FUNCTION__); errors++; } } - if(dictionary_stats_entries(dict) != i) { + if(dictionary_entries(dict) != i) { fprintf(stderr, ">>> %s() dictionary items do not match\n", __FUNCTION__); errors++; } @@ -1743,8 +2590,8 @@ static size_t dictionary_unittest_del_nonexisting(DICTIONARY *dict, char **names (void)names; size_t errors = 0; for(size_t i = 0; i < entries ;i++) { - int ret = dictionary_del(dict, values[i]); - if(ret != -1) { fprintf(stderr, ">>> %s() deleted non-existing item\n", __FUNCTION__); errors++; } + bool ret = dictionary_del(dict, values[i]); + if(ret) { fprintf(stderr, ">>> %s() deleted non-existing item\n", __FUNCTION__); errors++; } } return errors; } @@ -1758,18 +2605,18 @@ static size_t dictionary_unittest_del_existing(DICTIONARY *dict, char **names, c size_t backward_from = middle_to, backward_to = entries; for(size_t i = forward_from; i < forward_to ;i++) { - int ret = dictionary_del(dict, names[i]); - if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (forward) existing item\n", __FUNCTION__); errors++; } + bool ret = dictionary_del(dict, names[i]); + if(!ret) { fprintf(stderr, ">>> %s() didn't delete (forward) existing item\n", __FUNCTION__); errors++; } } for(size_t i = middle_to - 1; i >= middle_from ;i--) { - int ret = dictionary_del(dict, names[i]); - if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (middle) existing item\n", __FUNCTION__); errors++; } + bool ret = dictionary_del(dict, names[i]); + if(!ret) { fprintf(stderr, ">>> %s() didn't delete (middle) existing item\n", __FUNCTION__); errors++; } } for(size_t i = backward_to - 1; i >= backward_from ;i--) { - int ret = dictionary_del(dict, names[i]); - if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (backward) existing item\n", __FUNCTION__); errors++; } + bool ret = dictionary_del(dict, names[i]); + if(!ret) { fprintf(stderr, ">>> %s() didn't delete (backward) existing item\n", __FUNCTION__); errors++; } } return errors; @@ -1812,10 +2659,7 @@ static size_t dictionary_unittest_reset_dont_overwrite_nonclone(DICTIONARY *dict return errors; } -static int dictionary_unittest_walkthrough_callback(const char *name, void *value, void *data) { - (void)name; - (void)value; - (void)data; +static int dictionary_unittest_walkthrough_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) { return 1; } @@ -1827,10 +2671,10 @@ static size_t dictionary_unittest_walkthrough(DICTIONARY *dict, char **names, ch else return sum - entries; } -static int dictionary_unittest_walkthrough_delete_this_callback(const char *name, void *value, void *data) { - (void)value; +static int dictionary_unittest_walkthrough_delete_this_callback(const DICTIONARY_ITEM *item, void *value __maybe_unused, void *data) { + const char *name = dictionary_acquired_item_name((DICTIONARY_ITEM *)item); - if(dictionary_del_having_write_lock((DICTIONARY *)data, name) == -1) + if(!dictionary_del((DICTIONARY *)data, name)) return 0; return 1; @@ -1844,10 +2688,7 @@ static size_t dictionary_unittest_walkthrough_delete_this(DICTIONARY *dict, char else return sum - entries; } -static int dictionary_unittest_walkthrough_stop_callback(const char *name, void *value, void *data) { - (void)name; - (void)value; - (void)data; +static int dictionary_unittest_walkthrough_stop_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) { return -1; } @@ -1881,7 +2722,7 @@ static size_t dictionary_unittest_foreach_delete_this(DICTIONARY *dict, char **n size_t count = 0; char *item; dfe_start_write(dict, item) - if(dictionary_del_having_write_lock(dict, item_name) != -1) count++; + if(dictionary_del(dict, item_dfe.name)) count++; dfe_done(item); if(count > entries) return count - entries; @@ -1907,7 +2748,22 @@ static usec_t dictionary_unittest_run_and_measure_time(DICTIONARY *dict, char *m if(callback == dictionary_unittest_destroy) dict = NULL; - fprintf(stderr, " %zu errors, %ld items in dictionary, %llu usec \n", errs, dict? dictionary_stats_entries(dict):0, dt); + long int found_ok = 0, found_deleted = 0, found_referenced = 0; + if(dict) { + DICTIONARY_ITEM *item; + DOUBLE_LINKED_LIST_FOREACH_FORWARD(dict->items.list, item, prev, next) { + if(item->refcount >= 0 && !(item ->flags & ITEM_FLAG_DELETED)) + found_ok++; + else + found_deleted++; + + if(item->refcount > 0) + found_referenced++; + } + } + + fprintf(stderr, " %zu errors, %ld (found %ld) items in dictionary, %ld (found %ld) referenced, %ld (found %ld) deleted, %llu usec \n", + errs, dict?dict->entries:0, found_ok, dict?dict->referenced_items:0, found_referenced, dict?dict->pending_deletion_items:0, found_deleted, dt); *errors += errs; return dt; } @@ -1943,23 +2799,24 @@ static void dictionary_unittest_nonclone(DICTIONARY *dict, char **names, char ** } struct dictionary_unittest_sorting { - const char *oldname; - const char *oldvalue; + const char *old_name; + const char *old_value; size_t count; }; -static int dictionary_unittest_sorting_callback(const char *name, void *value, void *data) { +static int dictionary_unittest_sorting_callback(const DICTIONARY_ITEM *item, void *value, void *data) { + const char *name = dictionary_acquired_item_name((DICTIONARY_ITEM *)item); struct dictionary_unittest_sorting *t = (struct dictionary_unittest_sorting *)data; const char *v = (const char *)value; int ret = 0; - if(t->oldname && strcmp(t->oldname, name) > 0) { - fprintf(stderr, "name '%s' should be after '%s'\n", t->oldname, name); + if(t->old_name && strcmp(t->old_name, name) > 0) { + fprintf(stderr, "name '%s' should be after '%s'\n", t->old_name, name); ret = 1; } t->count++; - t->oldname = name; - t->oldvalue = v; + t->old_name = name; + t->old_value = v; return ret; } @@ -1967,7 +2824,7 @@ static int dictionary_unittest_sorting_callback(const char *name, void *value, v static size_t dictionary_unittest_sorted_walkthrough(DICTIONARY *dict, char **names, char **values, size_t entries) { (void)names; (void)values; - struct dictionary_unittest_sorting tmp = { .oldname = NULL, .oldvalue = NULL, .count = 0 }; + struct dictionary_unittest_sorting tmp = { .old_name = NULL, .old_value = NULL, .count = 0 }; size_t errors; errors = dictionary_sorted_walkthrough_read(dict, dictionary_unittest_sorting_callback, &tmp); @@ -1989,62 +2846,94 @@ static void dictionary_unittest_null_dfe(DICTIONARY *dict, char **names, char ** } -static int check_dictionary_callback(const char *name, void *value, void *data) { - (void)name; - (void)value; - (void)data; +static int unittest_check_dictionary_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) { return 1; } -static size_t check_dictionary(DICTIONARY *dict, size_t entries, size_t linked_list_members) { +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) { size_t errors = 0; - fprintf(stderr, "dictionary entries %ld, expected %zu...\t\t\t\t\t", dictionary_stats_entries(dict), entries); - if (dictionary_stats_entries(dict) != (long)entries) { + size_t ll = 0; + void *t; + dfe_start_read(dict, t) + ll++; + dfe_done(t); + + fprintf(stderr, "DICT %-20s: dictionary foreach entries %zu, expected %zu...\t\t\t\t\t", + label, ll, traversable); + if(ll != traversable) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - size_t ll = 0; - void *t; - dfe_start_read(dict, t) - ll++; - dfe_done(t); + ll = dictionary_walkthrough_read(dict, unittest_check_dictionary_callback, NULL); + fprintf(stderr, "DICT %-20s: dictionary walkthrough entries %zu, expected %zu...\t\t\t\t", + label, ll, traversable); + if(ll != traversable) { + fprintf(stderr, "FAILED\n"); + errors++; + } + else + fprintf(stderr, "OK\n"); - fprintf(stderr, "dictionary foreach entries %zu, expected %zu...\t\t\t\t", ll, entries); - if(ll != entries) { + ll = dictionary_sorted_walkthrough_read(dict, unittest_check_dictionary_callback, NULL); + fprintf(stderr, "DICT %-20s: dictionary sorted walkthrough entries %zu, expected %zu...\t\t\t", + label, ll, traversable); + if(ll != traversable) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - ll = dictionary_walkthrough_read(dict, check_dictionary_callback, NULL); - fprintf(stderr, "dictionary walkthrough entries %zu, expected %zu...\t\t\t\t", ll, entries); - if(ll != entries) { + DICTIONARY_ITEM *item; + size_t active = 0, deleted = 0, referenced = 0, pending = 0; + for(item = dict->items.list; item; item = item->next) { + if(!(item->flags & ITEM_FLAG_DELETED) && !(item->shared->flags & ITEM_FLAG_DELETED)) + active++; + else { + deleted++; + + if(item->refcount == 0) + pending++; + } + + if(item->refcount > 0) + referenced++; + } + + fprintf(stderr, "DICT %-20s: dictionary active items reported %ld, counted %zu, expected %zu...\t\t\t", + label, dict->entries, active, active_items); + if(active != active_items || active != (size_t)dict->entries) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - ll = dictionary_sorted_walkthrough_read(dict, check_dictionary_callback, NULL); - fprintf(stderr, "dictionary sorted walkthrough entries %zu, expected %zu...\t\t\t", ll, entries); - if(ll != entries) { + fprintf(stderr, "DICT %-20s: dictionary deleted items counted %zu, expected %zu...\t\t\t\t", + label, deleted, deleted_items); + if(deleted != deleted_items) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - NAME_VALUE *nv; - for(ll = 0, nv = dict->first_item; nv ;nv = nv->next) - ll++; + fprintf(stderr, "DICT %-20s: dictionary referenced items reported %ld, counted %zu, expected %zu...\t\t", + label, dict->referenced_items, referenced, referenced_items); + if(referenced != referenced_items || dict->referenced_items != (long int)referenced) { + fprintf(stderr, "FAILED\n"); + errors++; + } + else + fprintf(stderr, "OK\n"); - fprintf(stderr, "dictionary linked list entries %zu, expected %zu...\t\t\t\t", ll, linked_list_members); - if(ll != linked_list_members) { + fprintf(stderr, "DICT %-20s: dictionary pending deletion items reported %ld, counted %zu, expected %zu...\t", + label, dict->pending_deletion_items, pending, pending_deletion); + if(pending != pending_deletion || pending != (size_t)dict->pending_deletion_items) { fprintf(stderr, "FAILED\n"); errors++; } @@ -2054,40 +2943,44 @@ static size_t check_dictionary(DICTIONARY *dict, size_t entries, size_t linked_l return errors; } -static int check_name_value_callback(const char *name, void *value, void *data) { - (void)name; +static int check_item_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value, void *data) { return value == data; } -static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, const char *name, const char *value, unsigned refcount, NAME_VALUE_FLAGS deleted_flags, bool searchable, bool browsable, bool linked) { +static size_t unittest_check_item(const char *label, DICTIONARY *dict, + DICTIONARY_ITEM *item, const char *name, const char *value, int refcount, + ITEM_FLAGS deleted_flags, bool searchable, bool browsable, bool linked) { size_t errors = 0; - fprintf(stderr, "NAME_VALUE name is '%s', expected '%s'...\t\t\t\t", namevalue_get_name(nv), name); - if(strcmp(namevalue_get_name(nv), name) != 0) { + fprintf(stderr, "ITEM %-20s: name is '%s', expected '%s'...\t\t\t\t\t\t", label, item_get_name(item), name); + if(strcmp(item_get_name(item), name) != 0) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - fprintf(stderr, "NAME_VALUE value is '%s', expected '%s'...\t\t\t", (const char *)nv->value, value); - if(strcmp((const char *)nv->value, value) != 0) { + fprintf(stderr, "ITEM %-20s: value is '%s', expected '%s'...\t\t\t\t\t", label, (const char *)item->shared->value, value); + if(strcmp((const char *)item->shared->value, value) != 0) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - fprintf(stderr, "NAME_VALUE refcount is %u, expected %u...\t\t\t\t\t", nv->refcount, refcount); - if (nv->refcount != refcount) { + fprintf(stderr, "ITEM %-20s: refcount is %d, expected %d...\t\t\t\t\t\t\t", label, item->refcount, refcount); + if (item->refcount != refcount) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - fprintf(stderr, "NAME_VALUE deleted flag is %s, expected %s...\t\t\t", (nv->flags & NAME_VALUE_FLAG_DELETED)?"TRUE":"FALSE", (deleted_flags & NAME_VALUE_FLAG_DELETED)?"TRUE":"FALSE"); - if ((nv->flags & NAME_VALUE_FLAG_DELETED) != (deleted_flags & NAME_VALUE_FLAG_DELETED)) { + fprintf(stderr, "ITEM %-20s: deleted flag is %s, expected %s...\t\t\t\t\t", label, + (item->flags & ITEM_FLAG_DELETED || item->shared->flags & ITEM_FLAG_DELETED)?"true":"false", + (deleted_flags & ITEM_FLAG_DELETED)?"true":"false"); + + if ((item->flags & ITEM_FLAG_DELETED || item->shared->flags & ITEM_FLAG_DELETED) != (deleted_flags & ITEM_FLAG_DELETED)) { fprintf(stderr, "FAILED\n"); errors++; } @@ -2095,8 +2988,9 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co fprintf(stderr, "OK\n"); void *v = dictionary_get(dict, name); - bool found = v == nv->value; - fprintf(stderr, "NAME_VALUE searchable %5s, expected %5s...\t\t\t\t", found?"true":"false", searchable?"true":"false"); + bool found = v == item->shared->value; + fprintf(stderr, "ITEM %-20s: searchable %5s, expected %5s...\t\t\t\t\t\t", label, + found?"true":"false", searchable?"true":"false"); if(found != searchable) { fprintf(stderr, "FAILED\n"); errors++; @@ -2107,11 +3001,12 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co found = false; void *t; dfe_start_read(dict, t) { - if(t == nv->value) found = true; + if(t == item->shared->value) found = true; } dfe_done(t); - fprintf(stderr, "NAME_VALUE dfe browsable %5s, expected %5s...\t\t\t", found?"true":"false", browsable?"true":"false"); + fprintf(stderr, "ITEM %-20s: dfe browsable %5s, expected %5s...\t\t\t\t\t", label, + found?"true":"false", browsable?"true":"false"); if(found != browsable) { fprintf(stderr, "FAILED\n"); errors++; @@ -2119,8 +3014,9 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co else fprintf(stderr, "OK\n"); - found = dictionary_walkthrough_read(dict, check_name_value_callback, nv->value); - fprintf(stderr, "NAME_VALUE walkthrough browsable %5s, expected %5s...\t\t", found?"true":"false", browsable?"true":"false"); + found = dictionary_walkthrough_read(dict, check_item_callback, item->shared->value); + fprintf(stderr, "ITEM %-20s: walkthrough browsable %5s, expected %5s...\t\t\t\t", label, + found?"true":"false", browsable?"true":"false"); if(found != browsable) { fprintf(stderr, "FAILED\n"); errors++; @@ -2128,8 +3024,9 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co else fprintf(stderr, "OK\n"); - found = dictionary_sorted_walkthrough_read(dict, check_name_value_callback, nv->value); - fprintf(stderr, "NAME_VALUE sorted walkthrough browsable %5s, expected %5s...\t", found?"true":"false", browsable?"true":"false"); + found = dictionary_sorted_walkthrough_read(dict, check_item_callback, item->shared->value); + fprintf(stderr, "ITEM %-20s: sorted walkthrough browsable %5s, expected %5s...\t\t\t", label, + found?"true":"false", browsable?"true":"false"); if(found != browsable) { fprintf(stderr, "FAILED\n"); errors++; @@ -2138,11 +3035,12 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co fprintf(stderr, "OK\n"); found = false; - NAME_VALUE *n; - for(n = dict->first_item; n ;n = n->next) - if(n == nv) found = true; + DICTIONARY_ITEM *n; + for(n = dict->items.list; n ;n = n->next) + if(n == item) found = true; - fprintf(stderr, "NAME_VALUE linked %5s, expected %5s...\t\t\t\t", found?"true":"false", linked?"true":"false"); + fprintf(stderr, "ITEM %-20s: linked %5s, expected %5s...\t\t\t\t\t\t", label, + found?"true":"false", linked?"true":"false"); if(found != linked) { fprintf(stderr, "FAILED\n"); errors++; @@ -2153,6 +3051,423 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co return errors; } +struct thread_unittest { + int join; + DICTIONARY *dict; + int dups; +}; + +static void *unittest_dict_thread(void *arg) { + struct thread_unittest *tu = arg; + for(; 1 ;) { + if(__atomic_load_n(&tu->join, __ATOMIC_RELAXED)) + break; + + DICT_ITEM_CONST DICTIONARY_ITEM *item = + dictionary_set_and_acquire_item_advanced(tu->dict, "dict thread checking 1234567890", + -1, NULL, 0, NULL); + + + dictionary_get(tu->dict, dictionary_acquired_item_name(item)); + + void *t1; + dfe_start_write(tu->dict, t1) { + + // this should delete the referenced item + dictionary_del(tu->dict, t1_dfe.name); + + void *t2; + dfe_start_write(tu->dict, t2) { + // this should add another + dictionary_set(tu->dict, t2_dfe.name, NULL, 0); + + dictionary_get(tu->dict, dictionary_acquired_item_name(item)); + + // and this should delete it again + dictionary_del(tu->dict, t2_dfe.name); + } + dfe_done(t2); + + // this should fail to add it + dictionary_set(tu->dict, t1_dfe.name, NULL, 0); + dictionary_del(tu->dict, t1_dfe.name); + } + dfe_done(t1); + + for(int i = 0; i < tu->dups ; i++) { + dictionary_acquired_item_dup(tu->dict, item); + dictionary_get(tu->dict, dictionary_acquired_item_name(item)); + } + + for(int i = 0; i < tu->dups ; i++) { + dictionary_acquired_item_release(tu->dict, item); + dictionary_del(tu->dict, dictionary_acquired_item_name(item)); + } + + dictionary_acquired_item_release(tu->dict, item); + dictionary_del(tu->dict, "dict thread checking 1234567890"); + + // test concurrent deletions and flushes + { + if(gettid() % 2) { + char buf [256 + 1]; + + for (int i = 0; i < 1000; i++) { + snprintfz(buf, 256, "del/flush test %d", i); + dictionary_set(tu->dict, buf, NULL, 0); + } + + for (int i = 0; i < 1000; i++) { + snprintfz(buf, 256, "del/flush test %d", i); + dictionary_del(tu->dict, buf); + } + } + else { + for (int i = 0; i < 10; i++) { + dictionary_flush(tu->dict); + } + } + } + } + + return arg; +} + +static int dictionary_unittest_threads() { + + struct thread_unittest tu = { + .join = 0, + .dict = NULL, + .dups = 1, + }; + + // threads testing of dictionary + tu.dict = dictionary_create(DICT_OPTION_DONT_OVERWRITE_VALUE); + time_t seconds_to_run = 5; + int threads_to_create = 2; + fprintf( + stderr, + "\nChecking dictionary concurrency with %d threads for %lld seconds...\n", + threads_to_create, + (long long)seconds_to_run); + + netdata_thread_t threads[threads_to_create]; + tu.join = 0; + for (int i = 0; i < threads_to_create; i++) { + char buf[100 + 1]; + snprintf(buf, 100, "dict%d", i); + netdata_thread_create( + &threads[i], + buf, + NETDATA_THREAD_OPTION_DONT_LOG | NETDATA_THREAD_OPTION_JOINABLE, + unittest_dict_thread, + &tu); + } + sleep_usec(seconds_to_run * USEC_PER_SEC); + + __atomic_store_n(&tu.join, 1, __ATOMIC_RELAXED); + for (int i = 0; i < threads_to_create; i++) { + void *retval; + netdata_thread_join(threads[i], &retval); + } + + fprintf(stderr, + "inserts %zu" + ", deletes %zu" + ", searches %zu" + ", resets %zu" + ", flushes %zu" + ", entries %ld" + ", referenced_items %ld" + ", pending deletions %ld" + ", check spins %zu" + ", insert spins %zu" + ", delete spins %zu" + ", search ignores %zu" + "\n", + tu.dict->stats->ops.inserts, + tu.dict->stats->ops.deletes, + tu.dict->stats->ops.searches, + tu.dict->stats->ops.resets, + tu.dict->stats->ops.flushes, + tu.dict->entries, + tu.dict->referenced_items, + tu.dict->pending_deletion_items, + tu.dict->stats->spin_locks.use_spins, + tu.dict->stats->spin_locks.insert_spins, + tu.dict->stats->spin_locks.delete_spins, + tu.dict->stats->spin_locks.search_spins + ); + dictionary_destroy(tu.dict); + tu.dict = NULL; + + return 0; +} + +struct thread_view_unittest { + int join; + DICTIONARY *master; + DICTIONARY *view; + DICTIONARY_ITEM *item_master; + int dups; +}; + +static void *unittest_dict_master_thread(void *arg) { + struct thread_view_unittest *tv = arg; + + DICTIONARY_ITEM *item = NULL; + int loops = 0; + while(!__atomic_load_n(&tv->join, __ATOMIC_SEQ_CST)) { + + if(!item) + item = dictionary_set_and_acquire_item(tv->master, "ITEM1", "123", strlen("123") + 1); + + if(__atomic_load_n(&tv->item_master, __ATOMIC_SEQ_CST) != NULL) { + dictionary_acquired_item_release(tv->master, item); + dictionary_del(tv->master, "ITEM1"); + item = NULL; + loops++; + continue; + } + + dictionary_acquired_item_dup(tv->master, item); // for the view thread + __atomic_store_n(&tv->item_master, item, __ATOMIC_SEQ_CST); + dictionary_del(tv->master, "ITEM1"); + + + for(int i = 0; i < tv->dups + loops ; i++) { + dictionary_acquired_item_dup(tv->master, item); + } + + for(int i = 0; i < tv->dups + loops ; i++) { + dictionary_acquired_item_release(tv->master, item); + } + + dictionary_acquired_item_release(tv->master, item); + + item = NULL; + loops = 0; + } + + return arg; +} + +static void *unittest_dict_view_thread(void *arg) { + struct thread_view_unittest *tv = arg; + + DICTIONARY_ITEM *m_item = NULL; + + while(!__atomic_load_n(&tv->join, __ATOMIC_SEQ_CST)) { + if(!(m_item = __atomic_load_n(&tv->item_master, __ATOMIC_SEQ_CST))) + continue; + + DICTIONARY_ITEM *v_item = dictionary_view_set_and_acquire_item(tv->view, "ITEM2", m_item); + dictionary_acquired_item_release(tv->master, m_item); + __atomic_store_n(&tv->item_master, NULL, __ATOMIC_SEQ_CST); + + for(int i = 0; i < tv->dups ; i++) { + dictionary_acquired_item_dup(tv->view, v_item); + } + + for(int i = 0; i < tv->dups ; i++) { + dictionary_acquired_item_release(tv->view, v_item); + } + + dictionary_del(tv->view, "ITEM2"); + + while(!__atomic_load_n(&tv->join, __ATOMIC_SEQ_CST) && !(m_item = __atomic_load_n(&tv->item_master, __ATOMIC_SEQ_CST))) { + dictionary_acquired_item_dup(tv->view, v_item); + dictionary_acquired_item_release(tv->view, v_item); + } + + dictionary_acquired_item_release(tv->view, v_item); + } + + return arg; +} + +static int dictionary_unittest_view_threads() { + + struct thread_view_unittest tv = { + .join = 0, + .master = NULL, + .view = NULL, + .item_master = NULL, + .dups = 1, + }; + + // threads testing of dictionary + struct dictionary_stats stats_master = {}; + struct dictionary_stats stats_view = {}; + tv.master = dictionary_create_advanced(DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE, &stats_master); + tv.view = dictionary_create_view(tv.master); + tv.view->stats = &stats_view; + + time_t seconds_to_run = 5; + fprintf( + stderr, + "\nChecking dictionary concurrency with 1 master and 1 view threads for %lld seconds...\n", + (long long)seconds_to_run); + + netdata_thread_t master_thread, view_thread; + tv.join = 0; + + netdata_thread_create( + &master_thread, + "master", + NETDATA_THREAD_OPTION_DONT_LOG | NETDATA_THREAD_OPTION_JOINABLE, + unittest_dict_master_thread, + &tv); + + netdata_thread_create( + &view_thread, + "view", + NETDATA_THREAD_OPTION_DONT_LOG | NETDATA_THREAD_OPTION_JOINABLE, + unittest_dict_view_thread, + &tv); + + sleep_usec(seconds_to_run * USEC_PER_SEC); + + __atomic_store_n(&tv.join, 1, __ATOMIC_RELAXED); + void *retval; + netdata_thread_join(view_thread, &retval); + netdata_thread_join(master_thread, &retval); + + fprintf(stderr, + "MASTER: inserts %zu" + ", deletes %zu" + ", searches %zu" + ", resets %zu" + ", entries %ld" + ", referenced_items %ld" + ", pending deletions %ld" + ", check spins %zu" + ", insert spins %zu" + ", delete spins %zu" + ", search ignores %zu" + "\n", + stats_master.ops.inserts, + stats_master.ops.deletes, + stats_master.ops.searches, + stats_master.ops.resets, + tv.master->entries, + tv.master->referenced_items, + tv.master->pending_deletion_items, + stats_master.spin_locks.use_spins, + stats_master.spin_locks.insert_spins, + stats_master.spin_locks.delete_spins, + stats_master.spin_locks.search_spins + ); + fprintf(stderr, + "VIEW : inserts %zu" + ", deletes %zu" + ", searches %zu" + ", resets %zu" + ", entries %ld" + ", referenced_items %ld" + ", pending deletions %ld" + ", check spins %zu" + ", insert spins %zu" + ", delete spins %zu" + ", search ignores %zu" + "\n", + stats_view.ops.inserts, + stats_view.ops.deletes, + stats_view.ops.searches, + stats_view.ops.resets, + tv.view->entries, + tv.view->referenced_items, + tv.view->pending_deletion_items, + stats_view.spin_locks.use_spins, + stats_view.spin_locks.insert_spins, + stats_view.spin_locks.delete_spins, + stats_view.spin_locks.search_spins + ); + dictionary_destroy(tv.master); + dictionary_destroy(tv.view); + + return 0; +} + +size_t dictionary_unittest_views(void) { + size_t errors = 0; + struct dictionary_stats stats = {}; + DICTIONARY *master = dictionary_create_advanced(DICT_OPTION_NONE, &stats); + DICTIONARY *view = dictionary_create_view(master); + + fprintf(stderr, "\n\nChecking dictionary views...\n"); + + // Add an item to both master and view, then remove the view first and the master second + fprintf(stderr, "\nPASS 1: Adding 1 item to master:\n"); + DICTIONARY_ITEM *item1_on_master = dictionary_set_and_acquire_item(master, "KEY 1", "VALUE1", strlen("VALUE1") + 1); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 1: Adding master item to view:\n"); + DICTIONARY_ITEM *item1_on_view = dictionary_view_set_and_acquire_item(view, "KEY 1 ON VIEW", item1_on_master); + errors += unittest_check_dictionary("view", view, 1, 1, 0, 1, 0); + 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); + + fprintf(stderr, "\nPASS 1: Deleting view item:\n"); + dictionary_del(view, "KEY 1 ON VIEW"); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + 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); + + fprintf(stderr, "\nPASS 1: Releasing the deleted view item:\n"); + dictionary_acquired_item_release(view, item1_on_view); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 1: Releasing the acquired master item:\n"); + dictionary_acquired_item_release(master, item1_on_master); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 0, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 0, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 1: Deleting the released master item:\n"); + dictionary_del(master, "KEY 1"); + errors += unittest_check_dictionary("master", master, 0, 0, 0, 0, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1); + + // The other way now: + // Add an item to both master and view, then remove the master first and verify it is deleted on the view also + fprintf(stderr, "\nPASS 2: Adding 1 item to master:\n"); + item1_on_master = dictionary_set_and_acquire_item(master, "KEY 1", "VALUE1", strlen("VALUE1") + 1); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 2: Adding master item to view:\n"); + item1_on_view = dictionary_view_set_and_acquire_item(view, "KEY 1 ON VIEW", item1_on_master); + errors += unittest_check_dictionary("view", view, 1, 1, 0, 1, 0); + 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); + + fprintf(stderr, "\nPASS 2: Deleting master item:\n"); + dictionary_del(master, "KEY 1"); + dictionary_version(view); + errors += unittest_check_dictionary("master", master, 0, 0, 1, 1, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true); + 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); + + fprintf(stderr, "\nPASS 2: Releasing the acquired master item:\n"); + dictionary_acquired_item_release(master, item1_on_master); + errors += unittest_check_dictionary("master", master, 0, 0, 1, 0, 1); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0); + 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); + + fprintf(stderr, "\nPASS 2: Releasing the deleted view item:\n"); + dictionary_acquired_item_release(view, item1_on_view); + errors += unittest_check_dictionary("master", master, 0, 0, 1, 0, 1); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1); + + dictionary_destroy(master); + dictionary_destroy(view); + return errors; +} + int dictionary_unittest(size_t entries) { if(entries < 10) entries = 10; @@ -2164,23 +3479,28 @@ int dictionary_unittest(size_t entries) { char **values = dictionary_unittest_generate_values(entries); fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED); + dict = dictionary_create(DICT_OPTION_SINGLE_THREADED); dictionary_unittest_clone(dict, names, values, entries, &errors); fprintf(stderr, "\nCreating dictionary multi threaded, clone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_NONE); + dict = dictionary_create(DICT_OPTION_NONE); dictionary_unittest_clone(dict, names, values, entries, &errors); fprintf(stderr, "\nCreating dictionary single threaded, non-clone, add-in-front options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_ADD_IN_FRONT); + dict = dictionary_create( + DICT_OPTION_SINGLE_THREADED | DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | + DICT_OPTION_ADD_IN_FRONT); dictionary_unittest_nonclone(dict, names, values, entries, &errors); fprintf(stderr, "\nCreating dictionary multi threaded, non-clone, add-in-front options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_ADD_IN_FRONT); + dict = dictionary_create( + DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_ADD_IN_FRONT); dictionary_unittest_nonclone(dict, names, values, entries, &errors); fprintf(stderr, "\nCreating dictionary single-threaded, non-clone, don't overwrite options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create( + DICT_OPTION_SINGLE_THREADED | DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | + DICT_OPTION_DONT_OVERWRITE_VALUE); dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); dictionary_unittest_run_and_measure_time(dict, "resetting non-overwrite entries", names, values, entries, &errors, dictionary_unittest_reset_dont_overwrite_nonclone); dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, &errors, dictionary_unittest_foreach); @@ -2189,13 +3509,15 @@ int dictionary_unittest(size_t entries) { dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary multi-threaded, non-clone, don't overwrite options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create( + DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE); dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); dictionary_unittest_run_and_measure_time(dict, "walkthrough write delete this", names, values, entries, &errors, dictionary_unittest_walkthrough_delete_this); dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary multi-threaded, non-clone, don't overwrite options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create( + DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE); dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); dictionary_unittest_run_and_measure_time(dict, "foreach write delete this", names, values, entries, &errors, dictionary_unittest_foreach_delete_this); dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop empty", names, values, 0, &errors, dictionary_unittest_foreach); @@ -2203,208 +3525,100 @@ int dictionary_unittest(size_t entries) { dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED); + dict = dictionary_create(DICT_OPTION_SINGLE_THREADED); dictionary_unittest_sorting(dict, names, values, entries, &errors); dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED); + dict = dictionary_create(DICT_OPTION_SINGLE_THREADED); dictionary_unittest_null_dfe(dict, names, values, entries, &errors); dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary single threaded, noclone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE); + dict = dictionary_create(DICT_OPTION_SINGLE_THREADED | DICT_OPTION_VALUE_LINK_DONT_CLONE); dictionary_unittest_null_dfe(dict, names, values, entries, &errors); dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); // check reference counters { fprintf(stderr, "\nTesting reference counters:\n"); - dict = dictionary_create(DICTIONARY_FLAG_NONE|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE); - errors += check_dictionary(dict, 0, 0); + dict = dictionary_create(DICT_OPTION_NONE | DICT_OPTION_NAME_LINK_DONT_CLONE); + errors += unittest_check_dictionary("", dict, 0, 0, 0, 0, 0); fprintf(stderr, "\nAdding test item to dictionary and acquiring it\n"); dictionary_set(dict, "test", "ITEM1", 6); - NAME_VALUE *nv = (NAME_VALUE *)dictionary_get_and_acquire_item(dict, "test"); + DICTIONARY_ITEM *item = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test"); - errors += check_dictionary(dict, 1, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0); + errors += unittest_check_item("ACQUIRED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true); fprintf(stderr, "\nChecking that reference counters are increased:\n"); void *t; dfe_start_read(dict, t) { - errors += check_dictionary(dict, 1, 1); - errors += - check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 2, NAME_VALUE_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0); + errors += unittest_check_item("ACQUIRED TRAVERSAL", dict, item, "test", "ITEM1", 2, ITEM_FLAG_NONE, true, true, true); } dfe_done(t); fprintf(stderr, "\nChecking that reference counters are decreased:\n"); - errors += check_dictionary(dict, 1, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0); + errors += unittest_check_item("ACQUIRED TRAVERSAL 2", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true); fprintf(stderr, "\nDeleting the item we have acquired:\n"); dictionary_del(dict, "test"); - errors += check_dictionary(dict, 0, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_DELETED, false, false, true); + errors += unittest_check_dictionary("", dict, 0, 0, 1, 1, 0); + errors += unittest_check_item("DELETED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true); fprintf(stderr, "\nAdding another item with the same name of the item we deleted, while being acquired:\n"); dictionary_set(dict, "test", "ITEM2", 6); - errors += check_dictionary(dict, 1, 2); + errors += unittest_check_dictionary("", dict, 1, 1, 1, 1, 0); fprintf(stderr, "\nAcquiring the second item:\n"); - NAME_VALUE *nv2 = (NAME_VALUE *)dictionary_get_and_acquire_item(dict, "test"); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_DELETED, false, false, true); - errors += check_name_value_deleted_flag(dict, nv2, "test", "ITEM2", 1, NAME_VALUE_FLAG_NONE, true, true, true); + DICTIONARY_ITEM *item2 = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test"); + errors += unittest_check_item("FIRST", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true); + errors += unittest_check_item("SECOND", dict, item2, "test", "ITEM2", 1, ITEM_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 1, 2, 0); fprintf(stderr, "\nReleasing the second item (the first is still acquired):\n"); - dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)nv2); - errors += check_dictionary(dict, 1, 2); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_DELETED, false, false, true); - errors += check_name_value_deleted_flag(dict, nv2, "test", "ITEM2", 0, NAME_VALUE_FLAG_NONE, true, true, true); + dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item2); + errors += unittest_check_dictionary("", dict, 1, 1, 1, 1, 0); + errors += unittest_check_item("FIRST", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true); + errors += unittest_check_item("SECOND RELEASED", dict, item2, "test", "ITEM2", 0, ITEM_FLAG_NONE, true, true, true); fprintf(stderr, "\nDeleting the second item (the first is still acquired):\n"); dictionary_del(dict, "test"); - errors += check_dictionary(dict, 0, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_DELETED, false, false, true); + errors += unittest_check_dictionary("", dict, 0, 0, 1, 1, 0); + errors += unittest_check_item("ACQUIRED DELETED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true); fprintf(stderr, "\nReleasing the first item (which we have already deleted):\n"); - dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)nv); - errors += check_dictionary(dict, 0, 0); + dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item); + dfe_start_write(dict, item) ; dfe_done(item); + errors += unittest_check_dictionary("", dict, 0, 0, 1, 0, 1); fprintf(stderr, "\nAdding again the test item to dictionary and acquiring it\n"); dictionary_set(dict, "test", "ITEM1", 6); - nv = (NAME_VALUE *)dictionary_get_and_acquire_item(dict, "test"); + item = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test"); - errors += check_dictionary(dict, 1, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0); + errors += unittest_check_item("RE-ADDITION", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true); fprintf(stderr, "\nDestroying the dictionary while we have acquired an item\n"); dictionary_destroy(dict); fprintf(stderr, "Releasing the item (on a destroyed dictionary)\n"); - dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)nv); - nv = NULL; + dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item); + item = NULL; dict = NULL; } - // check string - { - long string_entries_starting = dictionary_stats_entries(&string_dictionary); - - fprintf(stderr, "\nChecking strings...\n"); - - STRING *s1 = string_strdupz("hello unittest"); - STRING *s2 = string_strdupz("hello unittest"); - if(s1 != s2) { - errors++; - fprintf(stderr, "ERROR: duplicating strings are not deduplicated\n"); - } - else - fprintf(stderr, "OK: duplicating string are deduplicated\n"); - - STRING *s3 = string_dup(s1); - if(s3 != s1) { - errors++; - fprintf(stderr, "ERROR: cloning strings are not deduplicated\n"); - } - else - fprintf(stderr, "OK: cloning string are deduplicated\n"); - - STRING_ENTRY *se = (STRING_ENTRY *)s1; - if(se->refcount != 3) { - errors++; - fprintf(stderr, "ERROR: string refcount is not 3\n"); - } - else - fprintf(stderr, "OK: string refcount is 3\n"); - - STRING *s4 = string_strdupz("world unittest"); - if(s4 == s1) { - errors++; - fprintf(stderr, "ERROR: string is sharing pointers on different strings\n"); - } - else - fprintf(stderr, "OK: string is properly handling different strings\n"); - - usec_t start_ut, end_ut; - STRING **strings = mallocz(entries * sizeof(STRING *)); - - start_ut = now_realtime_usec(); - for(size_t i = 0; i < entries ;i++) { - strings[i] = string_strdupz(names[i]); - } - end_ut = now_realtime_usec(); - fprintf(stderr, "Created %zu strings in %llu usecs\n", entries, end_ut - start_ut); - - start_ut = now_realtime_usec(); - for(size_t i = 0; i < entries ;i++) { - strings[i] = string_dup(strings[i]); - } - end_ut = now_realtime_usec(); - fprintf(stderr, "Cloned %zu strings in %llu usecs\n", entries, end_ut - start_ut); - - start_ut = now_realtime_usec(); - for(size_t i = 0; i < entries ;i++) { - string_freez(strings[i]); - string_freez(strings[i]); - } - end_ut = now_realtime_usec(); - fprintf(stderr, "Freed %zu strings in %llu usecs\n", entries, end_ut - start_ut); - - freez(strings); - - if(dictionary_stats_entries(&string_dictionary) != string_entries_starting + 2) { - errors++; - fprintf(stderr, "ERROR: strings dictionary should have %ld items but it has %ld\n", string_entries_starting + 2, dictionary_stats_entries(&string_dictionary)); - } - else - fprintf(stderr, "OK: strings dictionary has 2 items\n"); - } - - // check 2-way merge - { - struct testcase { - char *src1; char *src2; char *expected; - } tests[] = { - { "", "", ""}, - { "a", "", "[x]"}, - { "", "a", "[x]"}, - { "a", "a", "a"}, - { "abcd", "abcd", "abcd"}, - { "foo_cs", "bar_cs", "[x]_cs"}, - { "cp_UNIQUE_INFIX_cs", "cp_unique_infix_cs", "cp_[x]_cs"}, - { "cp_UNIQUE_INFIX_ci_unique_infix_cs", "cp_unique_infix_ci_UNIQUE_INFIX_cs", "cp_[x]_cs"}, - { "foo[1234]", "foo[4321]", "foo[[x]]"}, - { NULL, NULL, NULL }, - }; - - for (struct testcase *tc = &tests[0]; tc->expected != NULL; tc++) { - STRING *src1 = string_strdupz(tc->src1); - STRING *src2 = string_strdupz(tc->src2); - STRING *expected = string_strdupz(tc->expected); - - STRING *result = string_2way_merge(src1, src2); - if (string_cmp(result, expected) != 0) { - fprintf(stderr, "string_2way_merge(\"%s\", \"%s\") -> \"%s\" (expected=\"%s\")\n", - string2str(src1), - string2str(src2), - string2str(result), - string2str(expected)); - errors++; - } - - string_freez(src1); - string_freez(src2); - string_freez(expected); - string_freez(result); - } - } - dictionary_unittest_free_char_pp(names, entries); dictionary_unittest_free_char_pp(values, entries); + errors += dictionary_unittest_views(); + errors += dictionary_unittest_threads(); + errors += dictionary_unittest_view_threads(); + fprintf(stderr, "\n%zu errors found\n", errors); return errors ? 1 : 0; } diff --git a/libnetdata/dictionary/dictionary.h b/libnetdata/dictionary/dictionary.h index fdb2088c0..0e7b3d39f 100644 --- a/libnetdata/dictionary/dictionary.h +++ b/libnetdata/dictionary/dictionary.h @@ -13,19 +13,19 @@ * Names and Values in the dictionary can be cloned or linked. * In clone mode, the dictionary does all the memory management. * The default is clone for both names and values. - * Set DICTIONARY_FLAG_NAME_LINK_DONT_CLONE to link names. - * Set DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE to link names. + * Set DICT_OPTION_NAME_LINK_DONT_CLONE to link names. + * Set DICT_OPTION_VALUE_LINK_DONT_CLONE to link names. * * ORDERED * Items are ordered in the order they are added (new items are appended at the end). - * You may reverse the order by setting the flag DICTIONARY_FLAG_ADD_IN_FRONT. + * You may reverse the order by setting the flag DICT_OPTION_ADD_IN_FRONT. * * LOOKUP * The dictionary uses JudyHS to maintain a very fast randomly accessible hash table. * * MULTI-THREADED and SINGLE-THREADED * Each dictionary may be single threaded (no locks), or multi-threaded (multiple readers or one writer). - * The default is multi-threaded. Add the flag DICTIONARY_FLAG_SINGLE_THREADED for single-threaded. + * The default is multi-threaded. Add the flag DICT_OPTION_SINGLE_THREADED for single-threaded. * * WALK-THROUGH and FOREACH traversal * The dictionary can be traversed on read or write mode, either with a callback (walkthrough) or with @@ -35,110 +35,186 @@ * */ +#ifdef DICTIONARY_INTERNALS +#define DICTFE_CONST +#define DICT_ITEM_CONST +#else +#define DICTFE_CONST const +#define DICT_ITEM_CONST const +#endif + typedef struct dictionary DICTIONARY; typedef struct dictionary_item DICTIONARY_ITEM; -typedef enum dictionary_flags { - DICTIONARY_FLAG_NONE = 0, // the default is the opposite of all below - DICTIONARY_FLAG_SINGLE_THREADED = (1 << 0), // don't use any locks (default: use locks) - DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE = (1 << 1), // don't copy the value, just point to the one provided (default: copy) - DICTIONARY_FLAG_NAME_LINK_DONT_CLONE = (1 << 2), // don't copy the name, just point to the one provided (default: copy) - DICTIONARY_FLAG_DONT_OVERWRITE_VALUE = (1 << 3), // don't overwrite values of dictionary items (default: overwrite) - DICTIONARY_FLAG_ADD_IN_FRONT = (1 << 4), // add dictionary items at the front of the linked list (default: at the end) - - // to change the value of the following, you also need to change the corresponding #defines in dictionary.c - DICTIONARY_FLAG_RESERVED1 = (1 << 29), // reserved for DICTIONARY_FLAG_EXCLUSIVE_ACCESS - DICTIONARY_FLAG_RESERVED2 = (1 << 30), // reserved for DICTIONARY_FLAG_DESTROYED - DICTIONARY_FLAG_RESERVED3 = (1 << 31), // reserved for DICTIONARY_FLAG_DEFER_ALL_DELETIONS -} DICTIONARY_FLAGS; +typedef enum dictionary_options { + DICT_OPTION_NONE = 0, // the default is the opposite of all below + DICT_OPTION_SINGLE_THREADED = (1 << 0), // don't use any locks (default: use locks) + DICT_OPTION_VALUE_LINK_DONT_CLONE = (1 << 1), // don't copy the value, just point to the one provided (default: copy) + DICT_OPTION_NAME_LINK_DONT_CLONE = (1 << 2), // don't copy the name, just point to the one provided (default: copy) + DICT_OPTION_DONT_OVERWRITE_VALUE = (1 << 3), // don't overwrite values of dictionary items (default: overwrite) + DICT_OPTION_ADD_IN_FRONT = (1 << 4), // add dictionary items at the front of the linked list (default: at the end) +} DICT_OPTIONS; + +struct dictionary_stats { + const char *name; // the name of the category + + struct { + size_t active; // the number of active dictionaries + size_t deleted; // the number of dictionaries queued for destruction + } dictionaries; + + struct { + long entries; // active items in the dictionary + long pending_deletion; // pending deletion items in the dictionary + long referenced; // referenced items in the dictionary + } items; + + struct { + size_t creations; // dictionary creations + size_t destructions; // dictionary destructions + size_t flushes; // dictionary flushes + size_t traversals; // dictionary foreach + size_t walkthroughs; // dictionary walkthrough + size_t garbage_collections; // dictionary garbage collections + size_t searches; // item searches + size_t inserts; // item inserts + size_t resets; // item resets + size_t deletes; // item deletes + } ops; + + struct { + size_t inserts; // number of times the insert callback is called + size_t conflicts; // number of times the conflict callback is called + size_t reacts; // number of times the react callback is called + size_t deletes; // number of times the delete callback is called + } callbacks; + + // memory + struct { + long indexed; // bytes of keys indexed (indication of the index size) + long values; // bytes of caller structures + long dict; // bytes of the structures dictionary needs + } memory; + + // spin locks + struct { + size_t use_spins; // number of times a reference to item had to spin to acquire it or ignore it + size_t search_spins; // number of times a successful search result had to be thrown away + size_t insert_spins; // number of times an insertion to the hash table had to be repeated + size_t delete_spins; // number of times a deletion had to spin to get a decision + } spin_locks; +}; // Create a dictionary #ifdef NETDATA_INTERNAL_CHECKS -#define dictionary_create(flags) dictionary_create_advanced_with_trace(flags, 0, __FUNCTION__, __LINE__, __FILE__); -#define dictionary_create_advanced(flags) dictionary_create_advanced_with_trace(flags, 0, __FUNCTION__, __LINE__, __FILE__); -extern DICTIONARY *dictionary_create_advanced_with_trace(DICTIONARY_FLAGS flags, size_t scratchpad_size, const char *function, size_t line, const char *file); +#define dictionary_create(options) dictionary_create_advanced_with_trace(options, NULL, __FUNCTION__, __LINE__, __FILE__) +#define dictionary_create_advanced(options, stats) dictionary_create_advanced_with_trace(options, stats, __FUNCTION__, __LINE__, __FILE__) +DICTIONARY *dictionary_create_advanced_with_trace(DICT_OPTIONS options, struct dictionary_stats *stats, const char *function, size_t line, const char *file); #else -#define dictionary_create(flags) dictionary_create_advanced(flags, 0); -extern DICTIONARY *dictionary_create_advanced(DICTIONARY_FLAGS flags, size_t scratchpad_size); +#define dictionary_create(options) dictionary_create_advanced(options, NULL); +DICTIONARY *dictionary_create_advanced(DICT_OPTIONS options, struct dictionary_stats *stats); #endif -extern void *dictionary_scratchpad(DICTIONARY *dict); +// Create a view on a dictionary +#ifdef NETDATA_INTERNAL_CHECKS +#define dictionary_create_view(master) dictionary_create_view_with_trace(master, __FUNCTION__, __LINE__, __FILE__) +DICTIONARY *dictionary_create_view_with_trace(DICTIONARY *master, const char *function, size_t line, const char *file); +#else +DICTIONARY *dictionary_create_view(DICTIONARY *master); +#endif // an insert callback to be called just after an item is added to the dictionary // this callback is called while the dictionary is write locked! -extern void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const char *name, void *value, void *data), void *data); +void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data); // a delete callback to be called just before an item is deleted forever // this callback is called while the dictionary is write locked! -extern void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const char *name, void *value, void *data), void *data); +void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data); -// a merge callback to be called when DICTIONARY_FLAG_DONT_OVERWRITE_VALUE +// a merge callback to be called when DICT_OPTION_DONT_OVERWRITE_VALUE // and an item is already found in the dictionary - the dictionary does nothing else in this case // the old_value will remain in the dictionary - the new_value is ignored -extern void dictionary_register_conflict_callback(DICTIONARY *dict, void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data), void *data); +// The callback should return true if the value has been updated (it increases the dictionary version). +void dictionary_register_conflict_callback(DICTIONARY *dict, bool (*conflict_callback)(const DICTIONARY_ITEM *item, void *old_value, void *new_value, void *data), void *data); // a reaction callback to be called after every item insertion or conflict // after the constructors have finished and the items are fully available for use // and the dictionary is not write locked anymore -extern void dictionary_register_react_callback(DICTIONARY *dict, void (*react_callback)(const char *name, void *value, void *data), void *data); +void dictionary_register_react_callback(DICTIONARY *dict, void (*react_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data); // Destroy a dictionary -// returns the number of bytes freed -// the returned value will not include name and value sizes if DICTIONARY_FLAG_WITH_STATISTICS is not set -extern size_t dictionary_destroy(DICTIONARY *dict); +// Returns the number of bytes freed +// The returned value will not include name/key sizes +// Registered delete callbacks will be run for each item in the dictionary. +size_t dictionary_destroy(DICTIONARY *dict); +// Empties a dictionary +// Referenced items will survive, but are not offered anymore. +// Registered delete callbacks will be run for each item in the dictionary. +void dictionary_flush(DICTIONARY *dict); + +void dictionary_version_increment(DICTIONARY *dict); + +// ---------------------------------------------------------------------------- // Set an item in the dictionary +// // - if an item with the same name does not exist, create one // - if an item with the same name exists, then: -// a) if DICTIONARY_FLAG_DONT_OVERWRITE_VALUE is set, just return the existing value (ignore the new value) +// a) if DICT_OPTION_DONT_OVERWRITE_VALUE is set, just return the existing value (ignore the new value) // else b) reset the value to the new value passed at the call // -// When DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE is set, the value is linked, otherwise it is copied -// When DICTIONARY_FLAG_NAME_LINK_DONT_CLONE is set, the name is linked, otherwise it is copied +// When DICT_OPTION_VALUE_LINK_DONT_CLONE is set, the value is linked, otherwise it is copied +// When DICT_OPTION_NAME_LINK_DONT_CLONE is set, the name is linked, otherwise it is copied // -// When neither DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE nor DICTIONARY_FLAG_NAME_LINK_DONT_CLONE are set, all the +// When neither DICT_OPTION_VALUE_LINK_DONT_CLONE nor DICT_OPTION_NAME_LINK_DONT_CLONE are set, all the // memory management for names and values is done by the dictionary. // // Passing NULL as value, the dictionary will callocz() the newly allocated value, otherwise it will copy it. // Passing 0 as value_len, the dictionary will set the value to NULL (no allocations for value will be made). -extern void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len); +#define dictionary_set(dict, name, value, value_len) dictionary_set_advanced(dict, name, -1, value, value_len, NULL) +void *dictionary_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data); + +#define dictionary_set_and_acquire_item(dict, name, value, value_len) dictionary_set_and_acquire_item_advanced(dict, name, -1, value, value_len, NULL) +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); +// set an item in a dictionary view +#define dictionary_view_set_and_acquire_item(dict, name, master_item) dictionary_view_set_and_acquire_item_advanced(dict, name, -1, master_item) +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_view_set_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICTIONARY_ITEM *master_item); +#define dictionary_view_set(dict, name, master_item) dictionary_view_set_advanced(dict, name, -1, master_item) +void *dictionary_view_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICT_ITEM_CONST DICTIONARY_ITEM *master_item); + +// ---------------------------------------------------------------------------- // Get an item from the dictionary // If it returns NULL, the item is not found -extern void *dictionary_get(DICTIONARY *dict, const char *name); +#define dictionary_get(dict, name) dictionary_get_advanced(dict, name, -1) +void *dictionary_get_advanced(DICTIONARY *dict, const char *name, ssize_t name_len); + +#define dictionary_get_and_acquire_item(dict, name) dictionary_get_and_acquire_item_advanced(dict, name, -1) +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_get_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len); + + +// ---------------------------------------------------------------------------- // Delete an item from the dictionary -// returns 0 if the item was found and has been deleted -// returns -1 if the item was not found in the index -extern int dictionary_del(DICTIONARY *dict, const char *name); +// returns true if the item was found and has been deleted +// returns false if the item was not found in the index -extern DICTIONARY_ITEM *dictionary_get_and_acquire_item_unsafe(DICTIONARY *dict, const char *name); -extern DICTIONARY_ITEM *dictionary_get_and_acquire_item(DICTIONARY *dict, const char *name); +#define dictionary_del(dict, name) dictionary_del_advanced(dict, name, -1) +bool dictionary_del_advanced(DICTIONARY *dict, const char *name, ssize_t name_len); -extern DICTIONARY_ITEM *dictionary_set_and_acquire_item_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len); -extern DICTIONARY_ITEM *dictionary_set_and_acquire_item(DICTIONARY *dict, const char *name, void *value, size_t value_len); +// ---------------------------------------------------------------------------- +// reference counters management -extern void dictionary_acquired_item_release_unsafe(DICTIONARY *dict, DICTIONARY_ITEM *item); -extern void dictionary_acquired_item_release(DICTIONARY *dict, DICTIONARY_ITEM *item); +void dictionary_acquired_item_release(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item); -extern DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY_ITEM *item); -extern const char *dictionary_acquired_item_name(DICTIONARY_ITEM *item); -extern void *dictionary_acquired_item_value(DICTIONARY_ITEM *item); +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item); -// UNSAFE functions, without locks -// to be used when the user is traversing with the right lock type -// Read lock is acquired by dictionary_walktrhough_read() and dfe_start_read() -// Write lock is acquired by dictionary_walktrhough_write() and dfe_start_write() -// For code readability, please use these macros: -#define dictionary_get_having_read_lock(dict, name) dictionary_get_unsafe(dict, name) -#define dictionary_get_having_write_lock(dict, name) dictionary_get_unsafe(dict, name) -#define dictionary_set_having_write_lock(dict, name, value, value_len) dictionary_set_unsafe(dict, name, value, value_len) -#define dictionary_del_having_write_lock(dict, name) dictionary_del_unsafe(dict, name) +const char *dictionary_acquired_item_name(DICT_ITEM_CONST DICTIONARY_ITEM *item); +void *dictionary_acquired_item_value(DICT_ITEM_CONST DICTIONARY_ITEM *item); -extern void *dictionary_get_unsafe(DICTIONARY *dict, const char *name); -extern void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len); -extern int dictionary_del_unsafe(DICTIONARY *dict, const char *name); +size_t dictionary_acquired_item_references(DICT_ITEM_CONST DICTIONARY_ITEM *item); +// ---------------------------------------------------------------------------- // Traverse (walk through) the items of the dictionary. // The order of traversal is currently the order of insertion. // @@ -153,12 +229,15 @@ extern int dictionary_del_unsafe(DICTIONARY *dict, const char *name); // #define dictionary_walkthrough_read(dict, callback, data) dictionary_walkthrough_rw(dict, 'r', callback, data) #define dictionary_walkthrough_write(dict, callback, data) dictionary_walkthrough_rw(dict, 'w', callback, data) -extern int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const char *name, void *value, void *data), void *data); +int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data); -#define dictionary_sorted_walkthrough_read(dict, callback, data) dictionary_sorted_walkthrough_rw(dict, 'r', callback, data) -#define dictionary_sorted_walkthrough_write(dict, callback, data) dictionary_sorted_walkthrough_rw(dict, 'w', callback, data) -int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const char *name, void *entry, void *data), void *data); +typedef int (*dictionary_sorted_compar)(const DICTIONARY_ITEM **item1, const DICTIONARY_ITEM **item2); +#define dictionary_sorted_walkthrough_read(dict, callback, data) dictionary_sorted_walkthrough_rw(dict, 'r', callback, data, NULL) +#define dictionary_sorted_walkthrough_write(dict, callback, data) dictionary_sorted_walkthrough_rw(dict, 'w', callback, data, NULL) +int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const DICTIONARY_ITEM *item, void *entry, void *data), void *data, dictionary_sorted_compar compar); + +// ---------------------------------------------------------------------------- // Traverse with foreach // // Use like this: @@ -173,80 +252,72 @@ int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)( // You can only delete the current item from inside a dfe_start_write() - you can add as many as you want. // -#ifdef DICTIONARY_INTERNALS -#define DICTFE_CONST -#else -#define DICTFE_CONST const -#endif +#define DICTIONARY_LOCK_READ 'r' +#define DICTIONARY_LOCK_WRITE 'w' +#define DICTIONARY_LOCK_REENTRANT 'z' -#define DICTIONARY_LOCK_READ 'r' -#define DICTIONARY_LOCK_WRITE 'w' -#define DICTIONARY_LOCK_NONE 'u' +void dictionary_write_lock(DICTIONARY *dict); +void dictionary_write_unlock(DICTIONARY *dict); typedef DICTFE_CONST struct dictionary_foreach { + DICTIONARY *dict; // the dictionary upon we work + + DICTIONARY_ITEM *item; // the item we work on, to remember the position we are at + // this can be used with dictionary_acquired_item_dup() to + // acquire the currently working item. + DICTFE_CONST char *name; // the dictionary name of the last item used void *value; // the dictionary value of the last item used // same as the return value of dictfe_start() and dictfe_next() - // the following are for internal use only - to keep track of the point we are + size_t counter; // counts the number of iterations made, starting from zero + char rw; // the lock mode 'r' or 'w' - usec_t started_ut; // the time the caller started iterating (now_realtime_usec()) - DICTIONARY *dict; // the dictionary upon we work - void *last_item; // the item we work on, to remember the position we are at } DICTFE; #define dfe_start_read(dict, value) dfe_start_rw(dict, value, DICTIONARY_LOCK_READ) #define dfe_start_write(dict, value) dfe_start_rw(dict, value, DICTIONARY_LOCK_WRITE) -#define dfe_start_rw(dict, value, mode) \ - do { \ - DICTFE value ## _dfe = {}; \ - const char *value ## _name; (void)(value ## _name); (void)value; \ - for((value) = dictionary_foreach_start_rw(&value ## _dfe, (dict), (mode)), ( value ## _name ) = value ## _dfe.name; \ - (value ## _dfe.name) ;\ - (value) = dictionary_foreach_next(&value ## _dfe), ( value ## _name ) = value ## _dfe.name) \ +#define dfe_start_reentrant(dict, value) dfe_start_rw(dict, value, DICTIONARY_LOCK_REENTRANT) + +#define dfe_start_rw(dict, value, mode) \ + do { \ + DICTFE value ## _dfe = {}; \ + (void)(value); /* needed to avoid warning when looping without using this */ \ + for((value) = dictionary_foreach_start_rw(&value ## _dfe, (dict), (mode)); \ + (value ## _dfe.item) ; \ + (value) = dictionary_foreach_next(&value ## _dfe)) \ { -#define dfe_done(value) \ - } \ - dictionary_foreach_done(&value ## _dfe); \ +#define dfe_done(value) \ + } \ + dictionary_foreach_done(&value ## _dfe); \ } while(0) -extern void * dictionary_foreach_start_rw(DICTFE *dfe, DICTIONARY *dict, char rw); -extern void * dictionary_foreach_next(DICTFE *dfe); -extern usec_t dictionary_foreach_done(DICTFE *dfe); +void *dictionary_foreach_start_rw(DICTFE *dfe, DICTIONARY *dict, char rw); +void *dictionary_foreach_next(DICTFE *dfe); +void dictionary_foreach_done(DICTFE *dfe); +// ---------------------------------------------------------------------------- // Get statistics about the dictionary -extern long int dictionary_stats_allocated_memory(DICTIONARY *dict); -extern long int dictionary_stats_entries(DICTIONARY *dict); -extern size_t dictionary_stats_version(DICTIONARY *dict); -extern size_t dictionary_stats_inserts(DICTIONARY *dict); -extern size_t dictionary_stats_searches(DICTIONARY *dict); -extern size_t dictionary_stats_deletes(DICTIONARY *dict); -extern size_t dictionary_stats_resets(DICTIONARY *dict); -extern size_t dictionary_stats_walkthroughs(DICTIONARY *dict); -extern size_t dictionary_stats_referenced_items(DICTIONARY *dict); - -extern int dictionary_unittest(size_t entries); -// ---------------------------------------------------------------------------- -// STRING implementation +size_t dictionary_version(DICTIONARY *dict); +size_t dictionary_entries(DICTIONARY *dict); +size_t dictionary_referenced_items(DICTIONARY *dict); +long int dictionary_stats_for_registry(DICTIONARY *dict); -typedef struct netdata_string STRING; -extern STRING *string_strdupz(const char *str); -extern STRING *string_dup(STRING *string); -extern void string_freez(STRING *string); -extern size_t string_length(STRING *string); -extern const char *string2str(STRING *string) NEVERNULL; +// for all cases that the caller does not provide a stats structure, this is where they are accumulated. +extern struct dictionary_stats dictionary_stats_category_other; -// keep common prefix/suffix and replace everything else with [x] -extern STRING *string_2way_merge(STRING *a, STRING *b); +int dictionary_unittest(size_t entries); + +// ---------------------------------------------------------------------------- +// THREAD CACHE -static inline int string_cmp(STRING *s1, STRING *s2) { - // STRINGs are deduplicated, so the same strings have the same pointer - if(unlikely(s1 == s2)) return 0; +void *thread_cache_entry_get_or_set(void *key, + ssize_t key_length, + void *value, + void *(*transform_the_value_before_insert)(void *key, size_t key_length, void *value)); - // they differ, do the typical comparison - return strcmp(string2str(s1), string2str(s2)); -} +void thread_cache_destroy(void); #endif /* NETDATA_DICTIONARY_H */ |