diff options
Diffstat (limited to 'libnetdata/dictionary')
| -rw-r--r-- | libnetdata/dictionary/README.md | 74 | ||||
| -rw-r--r-- | libnetdata/dictionary/dictionary.c | 1795 | ||||
| -rw-r--r-- | libnetdata/dictionary/dictionary.h | 108 |
3 files changed, 1602 insertions, 375 deletions
diff --git a/libnetdata/dictionary/README.md b/libnetdata/dictionary/README.md index 28d0cfbbd..879c1bcc1 100644 --- a/libnetdata/dictionary/README.md +++ b/libnetdata/dictionary/README.md @@ -22,7 +22,7 @@ Dictionaries are **ordered**, meaning that the order they have been added is pre 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` 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` (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. ## Memory management @@ -31,13 +31,13 @@ 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. -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 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. -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 used after an item is deleted from the dictionary. +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. @@ -63,7 +63,7 @@ The dictionary supports the following operations supported by the hash table: 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. The exception is the registration of a deletion callback function that can be called on deletion of an item, 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. ### dictionary_set() @@ -72,7 +72,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. +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. @@ -89,14 +89,16 @@ Where: * `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. It should never be called without an active lock on the dictionary, which can only be acquired while traversing. +> **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. ### 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 `JudyHS` hash table for making the lookup. For **multi-threaded** operation, the `dictionary_get()` call gets a shared read lock on the dictionary. +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. + The format is: ```c @@ -114,7 +116,7 @@ Where: This call is used to delete an item from the dictionary, given its name. -If there is a delete callback registered to the dictionary (`dictionary_register_delete_callback()`), it is called prior to the actual deletion of the item. +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. @@ -131,29 +133,65 @@ Where: > **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 **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. + +Example: + +```c +// create the dictionary +DICTIONARY *dict = dictionary_create(DICTIONARY_FLAGS_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"); + +// extract its value +char *value = (char *)dictionary_acquired_item_value(dict, item); + +// now value points to the string "value" +printf("I got value = '%s'\n", value); + +// release the item, so that it can deleted +dictionary_acquired_item_release(dict, item); + +// destroy the dictionary +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. + +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. + ## Traversal -Dictionaries offer 2 ways to traverse the entire dictionary: +Dictionaries offer 3 ways to traverse the entire dictionary: - **walkthrough**, implemented by setting a callback function to be called for every item. +- **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. -Both of these methods are available in **read** or **write** mode. In **read** mode only lookups are allowed to the dictionary. In **write** both lookups but also deletion of the currently working item is also allowed. +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 deadlock may arise. +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. ### walkthrough (callback) -There are 2 calls: +There are 4 calls: -- `dictionary_walkthrough_read()` that acquires a shared read lock, and it calls 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 add or remove item from the dictionary. -- `dictionary_walkthrough_write()` that acquires an exclusive write lock, and it calls a callback function for every item of the dictionary. This is to be used when items need to be added to the dictionary, or when the current item may need to be deleted. If the callback function deletes any other items, the behavior may be undefined (actually, the item next to the one currently working should not be deleted - a pointer to it is held by the traversal function to move on traversing the dictionary). +- `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.** -The items are traversed 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 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 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 callbacks 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. +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. ### foreach (for-next loop) @@ -186,14 +224,14 @@ else something else; ``` -In the above, the `if(x)` 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(x == 1)` condition will work as expected. It will do the foreach loop when x 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. -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 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 using the unsafe functions. The rules are the same with the unsorted walkthrough callback functions. PS: DFE is Dictionary For Each. diff --git a/libnetdata/dictionary/dictionary.c b/libnetdata/dictionary/dictionary.c index 42285037d..c1325ecb5 100644 --- a/libnetdata/dictionary/dictionary.c +++ b/libnetdata/dictionary/dictionary.c @@ -1,7 +1,12 @@ // SPDX-License-Identifier: GPL-3.0-or-later -// NOT TO BE USED BY USERS YET -#define DICTIONARY_FLAG_REFERENCE_COUNTERS (1 << 6) // maintain reference counter in walkthrough and foreach +// 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 @@ -19,99 +24,49 @@ typedef struct dictionary DICTIONARY; #include <Judy.h> #endif -/* - * This version uses JudyHS arrays to index the dictionary - * - * The following output is from the unit test, at the end of this file: - * - * This is the JudyHS version: - * - * 1000000 x dictionary_set() (dictionary size 0 entries, 0 KB)... - * 1000000 x dictionary_get(existing) (dictionary size 1000000 entries, 74001 KB)... - * 1000000 x dictionary_get(non-existing) (dictionary size 1000000 entries, 74001 KB)... - * Walking through the dictionary (dictionary size 1000000 entries, 74001 KB)... - * 1000000 x dictionary_del(existing) (dictionary size 1000000 entries, 74001 KB)... - * 1000000 x dictionary_set() (dictionary size 0 entries, 0 KB)... - * Destroying dictionary (dictionary size 1000000 entries, 74001 KB)... - * - * TIMINGS: - * adding 316027 usec, positive search 156740 usec, negative search 84524, walk through 15036 usec, deleting 361444, destroy 107394 usec - * - * This is from the JudySL version: - * - * Creating dictionary of 1000000 entries... - * Checking index of 1000000 entries... - * Walking 1000000 entries and checking name-value pairs... - * Created and checked 1000000 entries, found 0 errors - used 58376 KB of memory - * Destroying dictionary of 1000000 entries... - * Deleted 1000000 entries - * create 338975 usec, check 156080 usec, walk 80764 usec, destroy 444569 usec - * - * This is the AVL version: - * - * Creating dictionary of 1000000 entries... - * Checking index of 1000000 entries... - * Walking 1000000 entries and checking name-value pairs... - * Created and checked 1000000 entries, found 0 errors - used 89626 KB of memory - * Destroying dictionary of 1000000 entries... - * create 413892 usec, check 220006 usec, walk 34247 usec, destroy 98062 usec - * - * So, the JudySL is a lot slower to WALK and DESTROY (DESTROY does a WALK) - * It is slower, because for every item, JudySL copies the KEY/NAME to a - * caller supplied buffer (Index). So, by just walking over 1 million items, - * JudySL does 1 million strcpy() !!! - * - * It also seems that somehow JudySLDel() is unbelievably slow too! - * - */ +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) + // 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 +#ifdef NETDATA_INTERNAL_CHECKS + DICTIONARY *dict; +#endif + struct name_value *next; // a double linked list to allow fast insertions and deletions struct name_value *prev; - char *name; // the name of the dictionary item + 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 + 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 + }; } NAME_VALUE; -/* - * When DICTIONARY_FLAG_WITH_STATISTICS is set, we need to keep track of all the memory - * we allocate and free. So, we need to keep track of the sizes of all names and values. - * We do this by overloading NAME_VALUE with the following additional fields. - */ - -typedef enum name_value_flags { - NAME_VALUE_FLAG_NONE = 0, - NAME_VALUE_FLAG_DELETED = (1 << 0), // this item is deleted -} NAME_VALUE_FLAGS; - -typedef struct name_value_with_stats { - NAME_VALUE name_value_data_here; // never used - just to put the lengths at the right position - - size_t name_len; // the size of the name, including the terminating zero - size_t value_len; // the size of the value (assumed binary) - - size_t refcount; // the reference counter - NAME_VALUE_FLAGS flags; // the flags for this item -} NAME_VALUE_WITH_STATS; - -struct dictionary_stats { - size_t inserts; - size_t deletes; - size_t searches; - size_t resets; - size_t entries; - size_t memory; -}; - struct dictionary { +#ifdef NETDATA_INTERNAL_CHECKS + const char *creation_function; + const char *creation_file; + size_t creation_line; +#endif + DICTIONARY_FLAGS flags; // the flags of the dictionary NAME_VALUE *first_item; // the double linked list base pointers @@ -120,26 +75,51 @@ struct dictionary { #ifdef DICTIONARY_WITH_AVL avl_tree_type values_index; NAME_VALUE *hash_base; + void *(*get_thread_static_name_value)(const char *name); #endif #ifdef DICTIONARY_WITH_JUDYHS Pvoid_t JudyHSArray; // the hash table #endif - netdata_rwlock_t *rwlock; // the r/w lock when DICTIONARY_FLAG_SINGLE_THREADED is not set + netdata_rwlock_t rwlock; // the r/w lock when DICTIONARY_FLAG_SINGLE_THREADED is not set void (*ins_callback)(const char *name, void *value, void *data); void *ins_callback_data; + void (*react_callback)(const char *name, void *value, void *data); + void *react_callback_data; + void (*del_callback)(const char *name, void *value, void *data); void *del_callback_data; void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data); void *conflict_callback_data; - struct dictionary_stats *stats; // the statistics when DICTIONARY_FLAG_WITH_STATISTICS is set + 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 }; +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); + +// ---------------------------------------------------------------------------- +// 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; @@ -155,63 +135,156 @@ void dictionary_register_conflict_callback(DICTIONARY *dict, void (*conflict_cal dict->conflict_callback_data = data; } +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; +} + // ---------------------------------------------------------------------------- // dictionary statistics maintenance -size_t dictionary_stats_allocated_memory(DICTIONARY *dict) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) - return dict->stats->memory; - return 0; +long int dictionary_stats_allocated_memory(DICTIONARY *dict) { + return dict->memory; } -size_t dictionary_stats_entries(DICTIONARY *dict) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) - return dict->stats->entries; - return 0; +long int dictionary_stats_entries(DICTIONARY *dict) { + return dict->entries; +} +size_t dictionary_stats_version(DICTIONARY *dict) { + return dict->version; } size_t dictionary_stats_searches(DICTIONARY *dict) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) - return dict->stats->searches; - return 0; + return dict->searches; } size_t dictionary_stats_inserts(DICTIONARY *dict) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) - return dict->stats->inserts; - return 0; + return dict->inserts; } size_t dictionary_stats_deletes(DICTIONARY *dict) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) - return dict->stats->deletes; - return 0; + return dict->deletes; } size_t dictionary_stats_resets(DICTIONARY *dict) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) - return dict->stats->resets; - return 0; + return dict->resets; +} +size_t dictionary_stats_walkthroughs(DICTIONARY *dict) { + return dict->walkthroughs; +} +size_t dictionary_stats_referenced_items(DICTIONARY *dict) { + return __atomic_load_n(&dict->referenced_items, __ATOMIC_SEQ_CST); } static inline void DICTIONARY_STATS_SEARCHES_PLUS1(DICTIONARY *dict) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) - dict->stats->searches++; + if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { + dict->searches++; + } + else { + __atomic_fetch_add(&dict->searches, 1, __ATOMIC_RELAXED); + } } static inline void DICTIONARY_STATS_ENTRIES_PLUS1(DICTIONARY *dict, size_t size) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { - dict->stats->inserts++; - dict->stats->entries++; - dict->stats->memory += size; + if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { + dict->version++; + dict->inserts++; + dict->entries++; + dict->memory += (long)size; + } + 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); } } -static inline void DICTIONARY_STATS_ENTRIES_MINUS1(DICTIONARY *dict, size_t size) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { - dict->stats->deletes++; - dict->stats->entries--; - dict->stats->memory -= size; +static inline void DICTIONARY_STATS_ENTRIES_MINUS1(DICTIONARY *dict) { + if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { + dict->version++; + dict->deletes++; + 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); } } static inline void DICTIONARY_STATS_VALUE_RESETS_PLUS1(DICTIONARY *dict, size_t oldsize, size_t newsize) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { - dict->stats->resets++; - dict->stats->memory += newsize; - dict->stats->memory -= oldsize; + if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { + dict->version++; + dict->resets++; + dict->memory += (long)newsize; + dict->memory -= (long)oldsize; + } + 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_WALKTHROUGHS_PLUS1(DICTIONARY *dict) { + if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { + dict->walkthroughs++; + } + else { + __atomic_fetch_add(&dict->walkthroughs, 1, __ATOMIC_RELAXED); + } +} + +static inline size_t DICTIONARY_STATS_REFERENCED_ITEMS_PLUS1(DICTIONARY *dict) { + return __atomic_add_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); +} + +static inline size_t DICTIONARY_STATS_REFERENCED_ITEMS_MINUS1(DICTIONARY *dict) { + return __atomic_sub_fetch(&dict->referenced_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 size_t DICTIONARY_STATS_PENDING_DELETES_MINUS1(DICTIONARY *dict) { + return __atomic_sub_fetch(&dict->pending_deletion_items, 1, __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 int DICTIONARY_NAME_VALUE_REFCOUNT_GET(NAME_VALUE *nv) { + return __atomic_load_n(&nv->refcount, __ATOMIC_SEQ_CST); +} + +// ---------------------------------------------------------------------------- +// garbage collector +// it is called every time someone gets a write lock to the dictionary + +static void garbage_collect_pending_deletes_unsafe(DICTIONARY *dict) { + if(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS)) return; + + if(likely(!DICTIONARY_STATS_PENDING_DELETES_GET(dict))) return; + + 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; + + linkedlist_namevalue_unlink_unsafe(dict, nv); + namevalue_destroy_unsafe(dict, nv); + + size_t pending = DICTIONARY_STATS_PENDING_DELETES_MINUS1(dict); + if(!pending) break; + + nv = nv_next; + } + else + nv = nv->next; } } @@ -220,41 +293,104 @@ static inline void DICTIONARY_STATS_VALUE_RESETS_PLUS1(DICTIONARY *dict, size_t static inline size_t dictionary_lock_init(DICTIONARY *dict) { if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { - dict->rwlock = mallocz(sizeof(netdata_rwlock_t)); - netdata_rwlock_init(dict->rwlock); - return sizeof(netdata_rwlock_t); + netdata_rwlock_init(&dict->rwlock); + + if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) + dict->flags &= ~DICTIONARY_FLAG_EXCLUSIVE_ACCESS; + + return 0; } - dict->rwlock = NULL; + + // 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); - freez(dict->rwlock); - return sizeof(netdata_rwlock_t); + netdata_rwlock_destroy(&dict->rwlock); + return 0; } return 0; } -static inline void dictionary_lock_rlock(DICTIONARY *dict) { - if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { - // debug(D_DICTIONARY, "Dictionary READ lock"); - netdata_rwlock_rdlock(dict->rwlock); +static void dictionary_lock(DICTIONARY *dict, char rw) { + if(rw == 'u' || rw == 'U') return; + + 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); + } + + if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) + return; + + if(rw == 'r' || rw == 'R') { + // read lock + netdata_rwlock_rdlock(&dict->rwlock); + + 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; + } + } + else { + // write lock + netdata_rwlock_wrlock(&dict->rwlock); + + dict->flags |= DICTIONARY_FLAG_EXCLUSIVE_ACCESS; } } -static inline void dictionary_lock_wrlock(DICTIONARY *dict) { - if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { - // debug(D_DICTIONARY, "Dictionary WRITE lock"); - netdata_rwlock_wrlock(dict->rwlock); +static void dictionary_unlock(DICTIONARY *dict, char rw) { + if(rw == 'u' || rw == 'U') return; + + if(rw == 'r' || rw == 'R') { + // read unlock + __atomic_sub_fetch(&dict->readers, 1, __ATOMIC_RELAXED); + } + else { + // write unlock + garbage_collect_pending_deletes_unsafe(dict); + __atomic_sub_fetch(&dict->writers, 1, __ATOMIC_RELAXED); } + + if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) + return; + + if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) + dict->flags &= ~DICTIONARY_FLAG_EXCLUSIVE_ACCESS; + + netdata_rwlock_unlock(&dict->rwlock); } -static inline void dictionary_unlock(DICTIONARY *dict) { - if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { - // debug(D_DICTIONARY, "Dictionary UNLOCK lock"); - netdata_rwlock_unlock(dict->rwlock); +// ---------------------------------------------------------------------------- +// deferred deletions + +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; + } +} + +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; } } @@ -277,39 +413,90 @@ static inline size_t reference_counter_free(DICTIONARY *dict) { return 0; } -static void reference_counter_acquire(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(dict->flags & DICTIONARY_FLAG_REFERENCE_COUNTERS)) { - NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; - __atomic_fetch_add(&nvs->refcount, 1, __ATOMIC_SEQ_CST); - } +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 reference_counter_release(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(dict->flags & DICTIONARY_FLAG_REFERENCE_COUNTERS)) { - NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; - __atomic_fetch_sub(&nvs->refcount, 1, __ATOMIC_SEQ_CST); +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(refcount == 1) { + // referenced items counts number of unique items referenced + // so, we increase it only when refcount == 1 + DICTIONARY_STATS_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); } + + return refcount; } -static int reference_counter_mark_deleted(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(dict->flags & DICTIONARY_FLAG_REFERENCE_COUNTERS)) { - NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; - nvs->flags |= NAME_VALUE_FLAG_DELETED; - return 1; +static uint32_t reference_counter_release(DICTIONARY *dict, NAME_VALUE *nv, bool can_get_write_lock) { + // 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 + + 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); + + 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)); } - return 0; + + if(refcount == 1) { + if((nv->flags & NAME_VALUE_FLAG_DELETED)) + DICTIONARY_STATS_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); + } + + if(can_get_write_lock && DICTIONARY_STATS_PENDING_DELETES_GET(dict)) { + // we can garbage collect now + + dictionary_lock(dict, DICTIONARY_LOCK_WRITE); + garbage_collect_pending_deletes_unsafe(dict); + dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + } + + return refcount; } // ---------------------------------------------------------------------------- // hash table #ifdef DICTIONARY_WITH_AVL +static inline const char *namevalue_get_name(NAME_VALUE *nv); + static int name_value_compare(void* a, void* b) { - return strcmp(((NAME_VALUE *)a)->name, ((NAME_VALUE *)b)->name); + return strcmp(namevalue_get_name((NAME_VALUE *)a), namevalue_get_name((NAME_VALUE *)b)); +} + +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; } 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; } static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { @@ -317,7 +504,7 @@ static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { return 0; } -static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, NAME_VALUE *nv) { +static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *nv) { (void)name; (void)name_len; @@ -330,9 +517,8 @@ 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) { (void)name_len; - NAME_VALUE tmp; - tmp.name = (char *)name; - return (NAME_VALUE *)avl_search(&(dict->values_index), (avl_t *) &tmp); + void *tmp = dict->get_thread_static_name_value(name); + return (NAME_VALUE *)avl_search(&(dict->values_index), (avl_t *)tmp); } static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { @@ -346,13 +532,10 @@ static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char return &dict->hash_base; } -static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, const char *name, size_t name_len, NAME_VALUE *nv) { +static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, void *nv) { // we have our new NAME_VALUE object. // Let's index it. - (void)name; - (void)name_len; - if(unlikely(avl_insert(&((dict)->values_index), (avl_t *)(nv)) != (avl_t *)nv)) error("dictionary: INTERNAL ERROR: duplicate insertion to dictionary."); } @@ -380,6 +563,8 @@ static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { } 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); + JError_t J_Error; Pvoid_t *Rc = JudyHSIns(&dict->JudyHSArray, (void *)name, name_len, &J_Error); if (unlikely(Rc == PJERR)) { @@ -397,9 +582,10 @@ static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char return (NAME_VALUE **)Rc; } -static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, NAME_VALUE *nv) { - (void)nv; +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; JError_t J_Error; @@ -440,10 +626,8 @@ static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *nam } } -static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, const char *name, size_t name_len, NAME_VALUE *nv) { +static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, void *nv) { (void)dict; - (void)name; - (void)name_len; (void)nv; ; } @@ -454,6 +638,8 @@ static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, const // 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); + if (unlikely(!dict->first_item)) { // we are the only ones here nv->next = NULL; @@ -481,6 +667,8 @@ static inline void linkedlist_namevalue_link_unsafe(DICTIONARY *dict, NAME_VALUE } 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); + 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; @@ -490,54 +678,47 @@ static inline void linkedlist_namevalue_unlink_unsafe(DICTIONARY *dict, NAME_VAL // ---------------------------------------------------------------------------- // NAME_VALUE methods -static inline size_t namevalue_alloc_size(DICTIONARY *dict) { - return (dict->flags & DICTIONARY_FLAG_WITH_STATISTICS) ? sizeof(NAME_VALUE_WITH_STATS) : sizeof(NAME_VALUE); -} - -static inline size_t namevalue_get_namelen(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { - NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; - return nvs->name_len; +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; } - return 0; + + nv->string_name = string_strdupz(name); + nv->flags |= NAME_VALUE_FLAG_NAME_IS_ALLOCATED; + return name_len; } -static inline size_t namevalue_get_valuelen(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { - NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; - return nvs->value_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); + return 0; } -static inline void namevalue_set_valuelen(DICTIONARY *dict, NAME_VALUE *nv, size_t value_len) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { - NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; - nvs->value_len = value_len; - } -} -static inline void namevalue_set_namevaluelen(DICTIONARY *dict, NAME_VALUE *nv, size_t name_len, size_t value_len) { - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { - NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; - nvs->name_len = name_len; - nvs->value_len = value_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); + else + return nv->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); - size_t size = namevalue_alloc_size(dict); + size_t size = sizeof(NAME_VALUE); NAME_VALUE *nv = mallocz(size); size_t allocated = size; - namevalue_set_namevaluelen(dict, nv, name_len, value_len); +#ifdef NETDATA_INTERNAL_CHECKS + nv->dict = dict; +#endif - if(likely(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE)) - nv->name = (char *)name; - else { - nv->name = mallocz(name_len); - memcpy(nv->name, name, name_len); - allocated += name_len; - } + nv->refcount = 0; + nv->flags = NAME_VALUE_FLAG_NONE; + nv->value_len = value_len; + + allocated += namevalue_set_name(dict, nv, name, name_len); if(likely(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) nv->value = value; @@ -556,7 +737,7 @@ static NAME_VALUE *namevalue_create_unsafe(DICTIONARY *dict, const char *name, s } } else { - // the caller want an item without any value + // the caller wants an item without any value nv->value = NULL; } @@ -565,107 +746,189 @@ static NAME_VALUE *namevalue_create_unsafe(DICTIONARY *dict, const char *name, s DICTIONARY_STATS_ENTRIES_PLUS1(dict, allocated); + if(dict->ins_callback) + dict->ins_callback(namevalue_get_name(nv), nv->value, dict->ins_callback_data); + return nv; } 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.", nv->name); + debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", namevalue_get_name(nv)); + + DICTIONARY_STATS_VALUE_RESETS_PLUS1(dict, nv->value_len, value_len); + + if(dict->del_callback) + dict->del_callback(namevalue_get_name(nv), nv->value, dict->del_callback_data); if(likely(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) { - debug(D_DICTIONARY, "Dictionary: linking value to '%s'", nv->name); + debug(D_DICTIONARY, "Dictionary: linking value to '%s'", namevalue_get_name(nv)); nv->value = value; - namevalue_set_valuelen(dict, nv, value_len); + nv->value_len = value_len; } else { - debug(D_DICTIONARY, "Dictionary: cloning value to '%s'", nv->name); - DICTIONARY_STATS_VALUE_RESETS_PLUS1(dict, namevalue_get_valuelen(dict, nv), value_len); - - void *old = nv->value; - void *new = mallocz(value_len); - memcpy(new, value, value_len); - nv->value = new; - namevalue_set_valuelen(dict, nv, value_len); + debug(D_DICTIONARY, "Dictionary: cloning value to '%s'", namevalue_get_name(nv)); + + void *oldvalue = nv->value; + void *newvalue = NULL; + if(value_len) { + newvalue = mallocz(value_len); + if(value) memcpy(newvalue, value, value_len); + else memset(newvalue, 0, value_len); + } + nv->value = newvalue; + nv->value_len = value_len; - debug(D_DICTIONARY, "Dictionary: freeing old value of '%s'", nv->name); - freez(old); + debug(D_DICTIONARY, "Dictionary: freeing old value of '%s'", namevalue_get_name(nv)); + freez(oldvalue); } + + if(dict->ins_callback) + dict->ins_callback(namevalue_get_name(nv), nv->value, dict->ins_callback_data); } static size_t namevalue_destroy_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { - debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", nv->name); + debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", namevalue_get_name(nv)); + + if(dict->del_callback) + dict->del_callback(namevalue_get_name(nv), nv->value, dict->del_callback_data); size_t freed = 0; if(unlikely(!(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE))) { - debug(D_DICTIONARY, "Dictionary freeing value of '%s'", nv->name); + debug(D_DICTIONARY, "Dictionary freeing value of '%s'", namevalue_get_name(nv)); freez(nv->value); - freed += namevalue_get_valuelen(dict, nv); + freed += nv->value_len; } if(unlikely(!(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE))) { - debug(D_DICTIONARY, "Dictionary freeing name '%s'", nv->name); - freez(nv->name); - freed += namevalue_get_namelen(dict, nv); + debug(D_DICTIONARY, "Dictionary freeing name '%s'", namevalue_get_name(nv)); + freed += namevalue_free_name(dict, nv); } freez(nv); - freed += namevalue_alloc_size(dict); + freed += sizeof(NAME_VALUE); - DICTIONARY_STATS_ENTRIES_MINUS1(dict, freed); + DICTIONARY_STATS_ENTRIES_MINUS_MEMORY(dict, freed); return freed; } +// 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; + + if(unlikely(DICTIONARY_NAME_VALUE_REFCOUNT_GET(nv) > 0)) + return false; + + return true; +} + // ---------------------------------------------------------------------------- // API - dictionary management - -DICTIONARY *dictionary_create(DICTIONARY_FLAGS flags) { +#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."); - if((flags & DICTIONARY_FLAG_REFERENCE_COUNTERS) && (flags & DICTIONARY_FLAG_SINGLE_THREADED)) { - error("DICTIONARY: requested reference counters on single threaded dictionary. Not adding reference counters."); - flags &= ~DICTIONARY_FLAG_REFERENCE_COUNTERS; - } + if(unlikely(flags & DICTIONARY_FLAGS_RESERVED)) + flags &= ~DICTIONARY_FLAGS_RESERVED; - if(flags & DICTIONARY_FLAG_REFERENCE_COUNTERS) { - // we need statistics to allocate the extra NAME_VALUE attributes - flags |= DICTIONARY_FLAG_WITH_STATISTICS; - } - - DICTIONARY *dict = callocz(1, sizeof(DICTIONARY)); - size_t allocated = sizeof(DICTIONARY); + DICTIONARY *dict = callocz(1, sizeof(DICTIONARY) + scratchpad_size); + size_t allocated = sizeof(DICTIONARY) + scratchpad_size; + dict->scratchpad_size = scratchpad_size; dict->flags = flags; dict->first_item = dict->last_item = NULL; allocated += dictionary_lock_init(dict); allocated += reference_counter_init(dict); - - if(flags & DICTIONARY_FLAG_WITH_STATISTICS) { - dict->stats = callocz(1, sizeof(struct dictionary_stats)); - allocated += sizeof(struct dictionary_stats); - dict->stats->memory = allocated; - } - else - dict->stats = NULL; + dict->memory = (long)allocated; hashtable_init_unsafe(dict); + +#ifdef NETDATA_INTERNAL_CHECKS + dict->creation_function = function; + dict->creation_file = file; + dict->creation_line = line; +#endif + return (DICTIONARY *)dict; } +void *dictionary_scratchpad(DICTIONARY *dict) { + return &dict->scratchpad; +} + size_t dictionary_destroy(DICTIONARY *dict) { + if(!dict) return 0; + + NAME_VALUE *nv; + debug(D_DICTIONARY, "Destroying dictionary."); - dictionary_lock_wrlock(dict); + 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)); + } + + 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); + } + } while(referenced_items > 0 && ++retries < 10); + + if(referenced_items) { + dictionary_lock(dict, DICTIONARY_LOCK_WRITE); + + dict->flags |= DICTIONARY_FLAG_DESTROYED; + 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).", + dict->creation_function, + dict->creation_line, + dict->creation_file, + retries, + referenced_items, + dict->entries); + + dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + return 0; + } + + dictionary_lock(dict, DICTIONARY_LOCK_WRITE); size_t freed = 0; - NAME_VALUE *nv = dict->first_item; + nv = dict->first_item; while (nv) { // cache nv->next // because we are going to free nv - NAME_VALUE *nvnext = nv->next; + NAME_VALUE *nv_next = nv->next; freed += namevalue_destroy_unsafe(dict, nv); - nv = nvnext; + nv = nv_next; // to speed up destruction, we don't // unlink nv from the linked-list here } @@ -676,31 +939,31 @@ size_t dictionary_destroy(DICTIONARY *dict) { // destroy the dictionary freed += hashtable_destroy_unsafe(dict); - dictionary_unlock(dict); + dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); freed += dictionary_lock_free(dict); freed += reference_counter_free(dict); - - if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { - freez(dict->stats); - dict->stats = NULL; - freed += sizeof(struct dictionary_stats); - } - + freed += sizeof(DICTIONARY) + dict->scratchpad_size; freez(dict); - freed += sizeof(DICTIONARY); return freed; } // ---------------------------------------------------------------------------- -// API - items management +// helpers -void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - if(unlikely(!name || !*name)) { - error("Attempted to dictionary_set() a dictionary item without a name"); +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 NULL; } + if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + 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 debug(D_DICTIONARY, "SET dictionary entry with name '%s'.", name); @@ -720,11 +983,9 @@ void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, siz 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, name, name_len, nv); + hashtable_inserted_name_value_unsafe(dict, nv); linkedlist_namevalue_link_unsafe(dict, nv); - - if(dict->ins_callback) - dict->ins_callback(nv->name, nv->value, dict->ins_callback_data); + nv->flags |= NAME_VALUE_FLAG_NEW_OR_UPDATED; } else { // the item is already in the index @@ -732,33 +993,34 @@ void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, siz // or overwrite the value, depending on dictionary flags nv = *pnv; - if(!(dict->flags & DICTIONARY_FLAG_DONT_OVERWRITE_VALUE)) { - - if(dict->del_callback) - dict->del_callback(nv->name, nv->value, dict->del_callback_data); + if(!(dict->flags & DICTIONARY_FLAG_DONT_OVERWRITE_VALUE)) { namevalue_reset_unsafe(dict, nv, value, value_len); + nv->flags |= NAME_VALUE_FLAG_NEW_OR_UPDATED; + } - if(dict->ins_callback) - dict->ins_callback(nv->name, nv->value, dict->ins_callback_data); + 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; + } + + else { + // make sure this flag is not set + nv->flags &= ~NAME_VALUE_FLAG_NEW_OR_UPDATED; } - else if(dict->conflict_callback) - dict->conflict_callback(nv->name, nv->value, value, dict->conflict_callback_data); } - return nv->value; + return nv; } -void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - dictionary_lock_wrlock(dict); - void *ret = dictionary_set_unsafe(dict, name, value, value_len); - dictionary_unlock(dict); - return ret; -} +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"); + return NULL; + } -void *dictionary_get_unsafe(DICTIONARY *dict, const char *name) { - if(unlikely(!name || !*name)) { - error("Attempted to dictionary_get() without a name"); + if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + internal_error(true, "DICTIONARY: attempted to dictionary_get() on a destroyed dictionary"); return NULL; } @@ -773,22 +1035,168 @@ void *dictionary_get_unsafe(DICTIONARY *dict, const char *name) { } debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); + return nv; +} + +// ---------------------------------------------------------------------------- +// API - items management + +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); + + 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); + } + + return nv ? nv->value : NULL; +} + +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); + + // 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_unlock(dict, DICTIONARY_LOCK_WRITE); + + 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); + } + + return nv ? nv->value : NULL; +} + +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); + + if(unlikely(!nv)) + return NULL; + + reference_counter_acquire(dict, nv); + + 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); + } + + return (DICTIONARY_ITEM *)nv; +} + +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); + + // we need to get the reference counter before we unlock + if(nv) reference_counter_acquire(dict, nv); + + dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + + 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); + } + + return (DICTIONARY_ITEM *)nv; +} + +void *dictionary_get_unsafe(DICTIONARY *dict, const char *name) { + NAME_VALUE *nv = dictionary_get_name_value_unsafe(dict, name); + + if(unlikely(!nv)) + return NULL; + return nv->value; } void *dictionary_get(DICTIONARY *dict, const char *name) { - dictionary_lock_rlock(dict); + dictionary_lock(dict, DICTIONARY_LOCK_READ); void *ret = dictionary_get_unsafe(dict, name); - dictionary_unlock(dict); + dictionary_unlock(dict, DICTIONARY_LOCK_READ); return ret; } +DICTIONARY_ITEM *dictionary_get_and_acquire_item_unsafe(DICTIONARY *dict, const char *name) { + NAME_VALUE *nv = dictionary_get_name_value_unsafe(dict, name); + + if(unlikely(!nv)) + return NULL; + + reference_counter_acquire(dict, nv); + return (DICTIONARY_ITEM *)nv; +} + +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; +} + +DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY_ITEM *item) { + if(unlikely(!item)) return NULL; + reference_counter_increase((NAME_VALUE *)item); + return item; +} + +const char *dictionary_acquired_item_name(DICTIONARY_ITEM *item) { + if(unlikely(!item)) return NULL; + return namevalue_get_name((NAME_VALUE *)item); +} + +void *dictionary_acquired_item_value(DICTIONARY_ITEM *item) { + if(unlikely(!item)) return NULL; + return ((NAME_VALUE *)item)->value; +} + +void dictionary_acquired_item_release_unsafe(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(unlikely(!item)) return; + +#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)); +#endif + + reference_counter_release(dict, (NAME_VALUE *)item, false); +} + +void dictionary_acquired_item_release(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(unlikely(!item)) return; + +#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)); +#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 + + reference_counter_release(dict, (NAME_VALUE *)item, true); + + if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) + dictionary_destroy(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; + } + if(unlikely(!name || !*name)) { - error("Attempted to dictionary_det() without a name"); + internal_error(true, "DICTIONARY: attempted to dictionary_del() without a name"); return -1; } + internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: INTERNAL ERROR: deleting dictionary item '%s' without exclusive access to dictionary", name); + size_t name_len = strlen(name) + 1; // we need the terminating null too debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); @@ -809,23 +1217,25 @@ int dictionary_del_unsafe(DICTIONARY *dict, const char *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); - if(!reference_counter_mark_deleted(dict, nv)) { + if(name_value_can_be_deleted(dict, nv)) { linkedlist_namevalue_unlink_unsafe(dict, nv); - - if(dict->del_callback) - dict->del_callback(nv->name, nv->value, dict->del_callback_data); - namevalue_destroy_unsafe(dict, nv); } + else + nv->flags |= NAME_VALUE_FLAG_DELETED; + ret = 0; + + DICTIONARY_STATS_ENTRIES_MINUS1(dict); + } return ret; } int dictionary_del(DICTIONARY *dict, const char *name) { - dictionary_lock_wrlock(dict); + dictionary_lock(dict, DICTIONARY_LOCK_WRITE); int ret = dictionary_del_unsafe(dict, name); - dictionary_unlock(dict); + dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); return ret; } @@ -835,25 +1245,37 @@ 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)) { + internal_error(true, "DICTIONARY: attempted to dictionary_foreach_start_rw() on a destroyed dictionary"); + dfe->last_item = NULL; + dfe->name = NULL; + dfe->value = NULL; + return NULL; + } + dfe->dict = dict; + dfe->rw = rw; dfe->started_ut = now_realtime_usec(); - if(rw == 'r' || rw == 'R') - dictionary_lock_rlock(dict); - else - dictionary_lock_wrlock(dict); + dictionary_lock(dict, dfe->rw); + + DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict); + // get the first item from the list NAME_VALUE *nv = dict->first_item; - dfe->last_position_index = (void *)nv; + + // skip all the deleted items + while(nv && (nv->flags & NAME_VALUE_FLAG_DELETED)) + nv = nv->next; if(likely(nv)) { - dfe->next_position_index = (void *)nv->next; - dfe->name = nv->name; - dfe->value = (void *)nv->value; + dfe->last_item = nv; + dfe->name = (char *)namevalue_get_name(nv); + dfe->value = nv->value; reference_counter_acquire(dict, nv); } else { - dfe->next_position_index = NULL; + dfe->last_item = NULL; dfe->name = NULL; dfe->value = NULL; } @@ -864,21 +1286,36 @@ void *dictionary_foreach_start_rw(DICTFE *dfe, DICTIONARY *dict, char rw) { void *dictionary_foreach_next(DICTFE *dfe) { if(unlikely(!dfe || !dfe->dict)) return NULL; - NAME_VALUE *nv = (NAME_VALUE *)dfe->last_position_index; - if(likely(nv)) - reference_counter_release(dfe->dict, nv); + if(unlikely(dfe->dict->flags & DICTIONARY_FLAG_DESTROYED)) { + internal_error(true, "DICTIONARY: attempted to dictionary_foreach_next() on a destroyed dictionary"); + dfe->last_item = NULL; + dfe->name = NULL; + dfe->value = NULL; + return NULL; + } - nv = dfe->last_position_index = dfe->next_position_index; + // the item we just did + NAME_VALUE *nv = (NAME_VALUE *)dfe->last_item; - if(likely(nv)) { - dfe->next_position_index = (void *)nv->next; - dfe->name = nv->name; - dfe->value = (void *)nv->value; + // get the next item from the list + NAME_VALUE *nv_next = (nv) ? nv->next : NULL; + + // skip all the deleted items + while(nv_next && (nv_next->flags & NAME_VALUE_FLAG_DELETED)) + nv_next = nv_next->next; + // release the old, so that it can possibly be deleted + if(likely(nv)) + reference_counter_release(dfe->dict, nv, false); + + 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); } else { - dfe->next_position_index = NULL; + dfe->last_item = NULL; dfe->name = NULL; dfe->value = NULL; } @@ -889,14 +1326,21 @@ void *dictionary_foreach_next(DICTFE *dfe) { usec_t dictionary_foreach_done(DICTFE *dfe) { if(unlikely(!dfe || !dfe->dict)) return 0; - NAME_VALUE *nv = (NAME_VALUE *)dfe->last_position_index; - if(nv) - reference_counter_release(dfe->dict, nv); + if(unlikely(dfe->dict->flags & DICTIONARY_FLAG_DESTROYED)) { + internal_error(true, "DICTIONARY: attempted to dictionary_foreach_next() on a destroyed dictionary"); + return 0; + } + + // the item we just did + NAME_VALUE *nv = (NAME_VALUE *)dfe->last_item; + + // release it, so that it can possibly be deleted + if(likely(nv)) + reference_counter_release(dfe->dict, nv, false); - dictionary_unlock((DICTIONARY *)dfe->dict); + dictionary_unlock(dfe->dict, dfe->rw); dfe->dict = NULL; - dfe->last_position_index = NULL; - dfe->next_position_index = NULL; + dfe->last_item = NULL; dfe->name = NULL; dfe->value = NULL; @@ -912,21 +1356,40 @@ usec_t dictionary_foreach_done(DICTFE *dfe) { // 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(rw == 'r' || rw == 'R') - dictionary_lock_rlock(dict); - else - dictionary_lock_wrlock(dict); + if(unlikely(!dict)) return 0; + + if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + internal_error(true, "DICTIONARY: attempted to dictionary_walkthrough_rw() on a destroyed dictionary"); + return 0; + } + + dictionary_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) { - nv_next = nv->next; + // skip the deleted items + if(unlikely(nv->flags & NAME_VALUE_FLAG_DELETED)) { + nv = nv->next; + continue; + } + + // get a reference counter, so that our item will not be deleted + // while we are using it reference_counter_acquire(dict, nv); - int r = callback(nv->name, nv->value, data); - reference_counter_release(dict, nv); + + int r = callback(namevalue_get_name(nv), nv->value, data); + + // 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); + if(unlikely(r < 0)) { ret = r; break; @@ -937,12 +1400,249 @@ int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const c nv = nv_next; } - dictionary_unlock(dict); + dictionary_unlock(dict, rw); return ret; } // ---------------------------------------------------------------------------- +// 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))); +} + +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; + + if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + 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); + + 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; + } + + 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 != 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; + } + + qsort(array, count, sizeof(NAME_VALUE *), dictionary_sort_compar); + + 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; + } + } + + dictionary_restore_all_deletions_unsafe(dict, rw); + dictionary_unlock(dict, rw); + freez(array); + + return ret; +} + +// ---------------------------------------------------------------------------- +// STRING implementation - dedup all STRINGs + +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; + +#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; + + size_t size = sizeof(STRING_ENTRY) + strlen(name) + 1; + if(likely(_tmp && _length < size)) { + freez(_tmp); + _tmp = NULL; + _length = 0; + } + + if(unlikely(!_tmp)) { + _tmp = callocz(1, size); + _length = size; + } + + 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; + + 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++; + } + + netdata_mutex_unlock(&string_mutex); + return (STRING *)se; +} + +void string_freez(STRING *string) { + if(unlikely(!string)) return; + netdata_mutex_lock(&string_mutex); + + STRING_ENTRY *se = (STRING_ENTRY *)string; + + 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]"); + } + + 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'; + + 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); +} + +// ---------------------------------------------------------------------------- // unit test static void dictionary_unittest_free_char_pp(char **pp, size_t entries) { @@ -983,6 +1683,22 @@ static size_t dictionary_unittest_set_clone(DICTIONARY *dict, char **names, char return errors; } +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++) { + 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) { + fprintf(stderr, ">>> %s() dictionary items do not match\n", __FUNCTION__); + errors++; + } + return errors; +} + + static size_t dictionary_unittest_set_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) { size_t errors = 0; for(size_t i = 0; i < entries ;i++) { @@ -1182,7 +1898,7 @@ static size_t dictionary_unittest_destroy(DICTIONARY *dict, char **names, char * } static usec_t dictionary_unittest_run_and_measure_time(DICTIONARY *dict, char *message, char **names, char **values, size_t entries, size_t *errors, size_t (*callback)(DICTIONARY *dict, char **names, char **values, size_t entries)) { - fprintf(stderr, "%-40s... ", message); + fprintf(stderr, "%40s ... ", message); usec_t started = now_realtime_usec(); size_t errs = callback(dict, names, values, entries); @@ -1191,12 +1907,12 @@ static usec_t dictionary_unittest_run_and_measure_time(DICTIONARY *dict, char *m if(callback == dictionary_unittest_destroy) dict = NULL; - fprintf(stderr, " %zu errors, %zu items in dictionary, %llu usec \n", errs, dict? dictionary_stats_entries(dict):0, dt); + fprintf(stderr, " %zu errors, %ld items in dictionary, %llu usec \n", errs, dict? dictionary_stats_entries(dict):0, dt); *errors += errs; return dt; } -void dictionary_unittest_clone(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) { +static void dictionary_unittest_clone(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) { dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, errors, dictionary_unittest_set_clone); dictionary_unittest_run_and_measure_time(dict, "getting entries", names, values, entries, errors, dictionary_unittest_get_clone); dictionary_unittest_run_and_measure_time(dict, "getting non-existing entries", names, values, entries, errors, dictionary_unittest_get_nonexisting); @@ -1211,7 +1927,7 @@ void dictionary_unittest_clone(DICTIONARY *dict, char **names, char **values, si dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, errors, dictionary_unittest_destroy); } -void dictionary_unittest_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) { +static void dictionary_unittest_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) { dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, errors, dictionary_unittest_set_nonclone); dictionary_unittest_run_and_measure_time(dict, "getting entries", names, values, entries, errors, dictionary_unittest_get_nonclone); dictionary_unittest_run_and_measure_time(dict, "getting non-existing entries", names, values, entries, errors, dictionary_unittest_get_nonexisting); @@ -1226,6 +1942,217 @@ void dictionary_unittest_nonclone(DICTIONARY *dict, char **names, char **values, dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, errors, dictionary_unittest_destroy); } +struct dictionary_unittest_sorting { + const char *oldname; + const char *oldvalue; + size_t count; +}; + +static int dictionary_unittest_sorting_callback(const char *name, void *value, void *data) { + 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); + ret = 1; + } + t->count++; + t->oldname = name; + t->oldvalue = v; + + return ret; +} + +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 }; + size_t errors; + errors = dictionary_sorted_walkthrough_read(dict, dictionary_unittest_sorting_callback, &tmp); + + if(tmp.count != entries) { + fprintf(stderr, "Expected %zu entries, counted %zu\n", entries, tmp.count); + errors++; + } + return errors; +} + +static void dictionary_unittest_sorting(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) { + dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, errors, dictionary_unittest_set_clone); + dictionary_unittest_run_and_measure_time(dict, "sorted walkthrough", names, values, entries, errors, dictionary_unittest_sorted_walkthrough); +} + +static void dictionary_unittest_null_dfe(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) { + dictionary_unittest_run_and_measure_time(dict, "adding null value entries", names, values, entries, errors, dictionary_unittest_set_null); + dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, errors, dictionary_unittest_foreach); +} + + +static int check_dictionary_callback(const char *name, void *value, void *data) { + (void)name; + (void)value; + (void)data; + return 1; +} + +static size_t check_dictionary(DICTIONARY *dict, size_t entries, size_t linked_list_members) { + 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) { + 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); + + fprintf(stderr, "dictionary foreach entries %zu, expected %zu...\t\t\t\t", ll, entries); + if(ll != entries) { + 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) { + 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, "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, "dictionary linked list entries %zu, expected %zu...\t\t\t\t", ll, linked_list_members); + if(ll != linked_list_members) { + fprintf(stderr, "FAILED\n"); + errors++; + } + else + fprintf(stderr, "OK\n"); + + return errors; +} + +static int check_name_value_callback(const char *name, void *value, void *data) { + (void)name; + 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) { + 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, "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, "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, "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, "FAILED\n"); + errors++; + } + else + 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"); + if(found != searchable) { + fprintf(stderr, "FAILED\n"); + errors++; + } + else + fprintf(stderr, "OK\n"); + + found = false; + void *t; + dfe_start_read(dict, t) { + if(t == nv->value) found = true; + } + dfe_done(t); + + fprintf(stderr, "NAME_VALUE dfe browsable %5s, expected %5s...\t\t\t", found?"true":"false", browsable?"true":"false"); + if(found != browsable) { + fprintf(stderr, "FAILED\n"); + errors++; + } + 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"); + if(found != browsable) { + fprintf(stderr, "FAILED\n"); + errors++; + } + 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"); + if(found != browsable) { + fprintf(stderr, "FAILED\n"); + errors++; + } + else + fprintf(stderr, "OK\n"); + + found = false; + NAME_VALUE *n; + for(n = dict->first_item; n ;n = n->next) + if(n == nv) found = true; + + fprintf(stderr, "NAME_VALUE linked %5s, expected %5s...\t\t\t\t", found?"true":"false", linked?"true":"false"); + if(found != linked) { + fprintf(stderr, "FAILED\n"); + errors++; + } + else + fprintf(stderr, "OK\n"); + + return errors; +} + int dictionary_unittest(size_t entries) { if(entries < 10) entries = 10; @@ -1237,23 +2164,23 @@ 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|DICTIONARY_FLAG_WITH_STATISTICS); + dict = dictionary_create(DICTIONARY_FLAG_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_WITH_STATISTICS); + dict = dictionary_create(DICTIONARY_FLAG_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_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_ADD_IN_FRONT); + dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_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_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_ADD_IN_FRONT); + dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_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_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_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); @@ -1262,22 +2189,222 @@ 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_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_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_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_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); dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback empty", names, values, 0, &errors, dictionary_unittest_walkthrough); 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); + 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); + 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); + 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); + + 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"); + + errors += check_dictionary(dict, 1, 1); + errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_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); + } + 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); + + 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); + + 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); + + 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); + + 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); + + 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); + + 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); + + 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"); + + errors += check_dictionary(dict, 1, 1); + errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_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; + 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); fprintf(stderr, "\n%zu errors found\n", errors); - return (int)errors; + return errors ? 1 : 0; } diff --git a/libnetdata/dictionary/dictionary.h b/libnetdata/dictionary/dictionary.h index 356bf1895..fdb2088c0 100644 --- a/libnetdata/dictionary/dictionary.h +++ b/libnetdata/dictionary/dictionary.h @@ -35,23 +35,34 @@ * */ -#ifndef DICTIONARY_INTERNALS -typedef void DICTIONARY; -#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_WITH_STATISTICS = (1 << 3), // maintain statistics about dictionary operations (default: disabled) - DICTIONARY_FLAG_DONT_OVERWRITE_VALUE = (1 << 4), // don't overwrite values of dictionary items (default: overwrite) - DICTIONARY_FLAG_ADD_IN_FRONT = (1 << 5), // add dictionary items at the front of the linked list (default: at the end) - DICTIONARY_FLAG_RESERVED1 = (1 << 6), // this is reserved for DICTIONARY_FLAG_REFERENCE_COUNTERS + 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; // Create a dictionary -extern DICTIONARY *dictionary_create(DICTIONARY_FLAGS flags); +#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); +#else +#define dictionary_create(flags) dictionary_create_advanced(flags, 0); +extern DICTIONARY *dictionary_create_advanced(DICTIONARY_FLAGS flags, size_t scratchpad_size); +#endif + +extern void *dictionary_scratchpad(DICTIONARY *dict); // 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! @@ -66,6 +77,11 @@ extern void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_cal // 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); +// 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); + // 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 @@ -85,7 +101,7 @@ extern size_t dictionary_destroy(DICTIONARY *dict); // // 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) NEVERNULL; +extern void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len); // Get an item from the dictionary // If it returns NULL, the item is not found @@ -96,6 +112,19 @@ extern void *dictionary_get(DICTIONARY *dict, const char *name); // returns -1 if the item was not found in the index extern int dictionary_del(DICTIONARY *dict, const char *name); +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); + +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); + +extern void dictionary_acquired_item_release_unsafe(DICTIONARY *dict, DICTIONARY_ITEM *item); +extern void dictionary_acquired_item_release(DICTIONARY *dict, 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); + // 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() @@ -126,6 +155,10 @@ extern int dictionary_del_unsafe(DICTIONARY *dict, const char *name); #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); +#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); + // Traverse with foreach // // Use like this: @@ -146,29 +179,35 @@ extern int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)( #define DICTFE_CONST const #endif +#define DICTIONARY_LOCK_READ 'r' +#define DICTIONARY_LOCK_WRITE 'w' +#define DICTIONARY_LOCK_NONE 'u' + typedef DICTFE_CONST struct dictionary_foreach { 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 + 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_position_index; // the internal position index, to remember the position we are at - void *next_position_index; // the internal position index, of the next item + 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, 'r') -#define dfe_start_write(dict, value) dfe_start_rw(dict, value, 'w') +#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); \ + 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) ;\ - (value) = dictionary_foreach_next(&value ## _dfe), ( value ## _name ) = value ## _dfe.name) + (value ## _dfe.name) ;\ + (value) = dictionary_foreach_next(&value ## _dfe), ( value ## _name ) = value ## _dfe.name) \ + { #define dfe_done(value) \ + } \ dictionary_foreach_done(&value ## _dfe); \ } while(0) @@ -177,14 +216,37 @@ extern void * dictionary_foreach_next(DICTFE *dfe); extern usec_t dictionary_foreach_done(DICTFE *dfe); // Get statistics about the dictionary -// If DICTIONARY_FLAG_WITH_STATISTICS is not set, these return zero -extern size_t dictionary_stats_allocated_memory(DICTIONARY *dict); -extern size_t dictionary_stats_entries(DICTIONARY *dict); +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 + +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; + +// keep common prefix/suffix and replace everything else with [x] +extern STRING *string_2way_merge(STRING *a, STRING *b); + +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; + + // they differ, do the typical comparison + return strcmp(string2str(s1), string2str(s2)); +} + #endif /* NETDATA_DICTIONARY_H */ |