finalized dictionary.c

diff --git a/profile/benchmark-dictionary.c b/profile/benchmark-dictionary.c
new file mode 100644 (file)
index 0000000..163f442
--- /dev/null
+++ b/profile/benchmark-dictionary.c
@@ -0,0 +1,132 @@
+
+/*
+ * 1. build netdata (as normally)
+ * 2. cd profile/
+ * 3. compile with:
+ *    gcc -O3 -Wall -Wextra -I ../src/ -I ../ -o benchmark-dictionary benchmark-dictionary.c ../src/dictionary.o ../src/log.o ../src/avl.o ../src/common.o -pthread
+ *
+ */
+
+#include <stdio.h>
+#include <inttypes.h>
+
+#include "dictionary.h"
+#include "main.h"
+#include "log.h"
+#include "common.h"
+
+struct myvalue {
+       int i;
+};
+
+int main(int argc, char **argv) {
+       if(argc || argv) {;}
+
+       DICTIONARY *dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED);
+       if(!dict) fatal("Cannot create dictionary.");
+
+       struct rusage start, end;
+       unsigned long long dt;
+       char buf[100 + 1];
+       struct myvalue value, *v;
+       int i, max = 1000000, max2;
+
+       // ------------------------------------------------------------------------
+
+       getrusage(RUSAGE_SELF, &start);
+       dict->inserts = dict->deletes = dict->searches = 0ULL;
+       fprintf(stderr, "Inserting %d entries in the dictionary\n", max);
+       for(i = 0; i < max; i++) {
+               value.i = i;
+               snprintf(buf, 100, "%d", i);
+
+               dictionary_set(dict, buf, &value, sizeof(struct myvalue));
+       }
+       getrusage(RUSAGE_SELF, &end);
+       dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec);
+       fprintf(stderr, "Added %d entries in %llu nanoseconds: %llu inserts per second\n", max, dt, max * 1000000ULL / dt);
+       fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches);
+
+       // ------------------------------------------------------------------------
+
+       getrusage(RUSAGE_SELF, &start);
+       dict->inserts = dict->deletes = dict->searches = 0ULL;
+       fprintf(stderr, "Retrieving %d entries from the dictionary\n", max);
+       for(i = 0; i < max; i++) {
+               value.i = i;
+               snprintf(buf, 100, "%d", i);
+
+               v = dictionary_get(dict, buf);
+               if(!v)
+                       fprintf(stderr, "ERROR: cannot get value %d from the dictionary\n", i);
+               else if(v->i != i)
+                       fprintf(stderr, "ERROR: expected %d but got %d\n", i, v->i);
+       }
+       getrusage(RUSAGE_SELF, &end);
+       dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec);
+       fprintf(stderr, "Read %d entries in %llu nanoseconds: %llu searches per second\n", max, dt, max * 1000000ULL / dt);
+       fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches);
+
+       // ------------------------------------------------------------------------
+
+       getrusage(RUSAGE_SELF, &start);
+       dict->inserts = dict->deletes = dict->searches = 0ULL;
+       fprintf(stderr, "Resetting %d entries in the dictionary\n", max);
+       for(i = 0; i < max; i++) {
+               value.i = i;
+               snprintf(buf, 100, "%d", i);
+
+               dictionary_set(dict, buf, &value, sizeof(struct myvalue));
+       }
+       getrusage(RUSAGE_SELF, &end);
+       dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec);
+       fprintf(stderr, "Reset %d entries in %llu nanoseconds: %llu inserts per second\n", max, dt, max * 1000000ULL / dt);
+       fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches);
+
+       // ------------------------------------------------------------------------
+
+       getrusage(RUSAGE_SELF, &start);
+       dict->inserts = dict->deletes = dict->searches = 0ULL;
+       fprintf(stderr, "Searching  %d non-existing entries in the dictionary\n", max);
+       max2 = max * 2;
+       for(i = max; i < max2; i++) {
+               value.i = i;
+               snprintf(buf, 100, "%d", i);
+
+               v = dictionary_get(dict, buf);
+               if(v)
+                       fprintf(stderr, "ERROR: cannot got non-existing value %d from the dictionary\n", i);
+       }
+       getrusage(RUSAGE_SELF, &end);
+       dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec);
+       fprintf(stderr, "Searched %d non-existing entries in %llu nanoseconds: %llu searches per second\n", max, dt, max * 1000000ULL / dt);
+       fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches);
+
+       // ------------------------------------------------------------------------
+
+       getrusage(RUSAGE_SELF, &start);
+       dict->inserts = dict->deletes = dict->searches = 0ULL;
+       fprintf(stderr, "Deleting %d entries from the dictionary\n", max);
+       for(i = 0; i < max; i++) {
+               value.i = i;
+               snprintf(buf, 100, "%d", i);
+
+               dictionary_del(dict, buf);
+       }
+       getrusage(RUSAGE_SELF, &end);
+       dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec);
+       fprintf(stderr, "Deleted %d entries in %llu nanoseconds: %llu deletes per second\n", max, dt, max * 1000000ULL / dt);
+       fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches);
+
+       // ------------------------------------------------------------------------
+
+       getrusage(RUSAGE_SELF, &start);
+       dict->inserts = dict->deletes = dict->searches = 0ULL;
+       fprintf(stderr, "Destroying dictionary\n");
+       dictionary_destroy(dict);
+       getrusage(RUSAGE_SELF, &end);
+       dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec);
+       fprintf(stderr, "Destroyed in %llu nanoseconds\n", dt);
+
+       return 0;
+}

diff --git a/src/appconfig.c b/src/appconfig.c
index 73b9465085556dd6d448f03fc9de35864211a71e..770f315e2eb51c78a3fa880cabedfd28f8bfcfe2 100644 (file)
--- a/src/appconfig.c
+++ b/src/appconfig.c
@@ -90,11 +90,13 @@ static int config_compare(void* a, void* b) {
 avl_tree config_root_index = {
                NULL,
                config_compare,
+#ifndef AVL_WITHOUT_PTHREADS
 #ifdef AVL_LOCK_WITH_MUTEX
                PTHREAD_MUTEX_INITIALIZER
 #else
                PTHREAD_RWLOCK_INITIALIZER
 #endif
+#endif
 };
 
 #define config_index_add(cfg) avl_insert(&config_root_index, (avl *)(cfg))

diff --git a/src/dictionary.c b/src/dictionary.c
index 31f4d52e1990e057f5774b845332e7fe848eaff3..7c6a8342d04b49906e8938ce057a97389d76b689 100644 (file)
--- a/src/dictionary.c
+++ b/src/dictionary.c
@@ -22,93 +22,110 @@ static int name_value_compare(void* a, void* b) {
        else return strcmp(((NAME_VALUE *)a)->name, ((NAME_VALUE *)b)->name);
 }
 
-#define name_value_index_add(dict, cv) avl_insert(&((dict)->values_index), (avl *)(cv))
-#define name_value_index_del(dict, cv) avl_remove(&((dict)->values_index), (avl *)(cv))
+#define dictionary_name_value_index_add_nolock(dict, nv) do { (dict)->inserts++; avl_insert(&((dict)->values_index), (avl *)(nv)); } while(0)
+#define dictionary_name_value_index_del_nolock(dict, nv) do { (dict)->deletes++; avl_remove(&(dict->values_index), (avl *)(nv)); } while(0)
 
-static NAME_VALUE *dictionary_name_value_index_find(DICTIONARY *dict, const char *name, uint32_t hash) {
+static inline NAME_VALUE *dictionary_name_value_index_find_nolock(DICTIONARY *dict, const char *name, uint32_t hash) {
        NAME_VALUE *result = NULL, tmp;
        tmp.hash = (hash)?hash:simple_hash(name);
        tmp.name = (char *)name;
 
+       dict->searches++;
        avl_search(&(dict->values_index), (avl *)&tmp, name_value_iterator, (avl **)&result);
        return result;
 }
 
+static void dictionary_read_lock(DICTIONARY *dict) {
+       if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)))
+               pthread_rwlock_rdlock(&dict->rwlock);
+}
+
+static void dictionary_write_lock(DICTIONARY *dict) {
+       if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)))
+               pthread_rwlock_wrlock(&dict->rwlock);
+}
+
+static void dictionary_unlock(DICTIONARY *dict) {
+       if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)))
+               pthread_rwlock_unlock(&dict->rwlock);
+}
+
 // ----------------------------------------------------------------------------
 
-static NAME_VALUE *dictionary_name_value_create(DICTIONARY *dict, const char *name, void *value, size_t value_len) {
+static NAME_VALUE *dictionary_name_value_create_nolock(DICTIONARY *dict, const char *name, void *value, size_t value_len, uint32_t hash) {
        debug(D_DICTIONARY, "Creating name value entry for name '%s', value '%s'.", name, value);
 
        NAME_VALUE *nv = calloc(1, sizeof(NAME_VALUE));
-       if(!nv) {
-               fatal("Cannot allocate name_value of size %z", sizeof(NAME_VALUE));
-               exit(1);
-       }
+       if(unlikely(!nv)) fatal("Cannot allocate name_value of size %z", sizeof(NAME_VALUE));
 
        nv->name = strdup(name);
-       if(!nv->name) fatal("Cannot allocate name_value.name of size %z", strlen(name));
-       nv->hash = simple_hash(nv->name);
+       if(unlikely(!nv->name))
+               fatal("Cannot allocate name_value.name of size %z", strlen(name));
 
-       nv->value = malloc(value_len);
-       if(!nv->value) fatal("Cannot allocate name_value.value of size %z", value_len);
-       memcpy(nv->value, value, value_len);
+       nv->hash = (hash)?hash:simple_hash(nv->name);
 
-       // link it
-       pthread_rwlock_wrlock(&dict->rwlock);
-       nv->next = dict->values;
-       dict->values = nv;
-       pthread_rwlock_unlock(&dict->rwlock);
+       if(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)
+               nv->value = value;
+       else {
+               nv->value = malloc(value_len);
+               if (unlikely(!nv->value))
+                       fatal("Cannot allocate name_value.value of size %z", value_len);
+
+               memcpy(nv->value, value, value_len);
+       }
+
+       dictionary_write_lock(dict);
 
        // index it
-       name_value_index_add(dict, nv);
+       dictionary_name_value_index_add_nolock(dict, nv);
+
+       dict->entries++;
+
+       dictionary_unlock(dict);
 
        return nv;
 }
 
-static void dictionary_name_value_destroy(DICTIONARY *dict, NAME_VALUE *nv) {
+static void dictionary_name_value_destroy_nolock(DICTIONARY *dict, NAME_VALUE *nv) {
        debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", nv->name);
 
-       pthread_rwlock_wrlock(&dict->rwlock);
-       if(dict->values == nv) dict->values = nv->next;
-       else {
-               NAME_VALUE *n = dict->values;
-               while(n && n->next && n->next != nv) nv = nv->next;
-               if(!n || n->next != nv) {
-                       fatal("Cannot find name_value with name '%s' in dictionary.", nv->name);
-                       exit(1);
-               }
-               n->next = nv->next;
-               nv->next = NULL;
-       }
-       pthread_rwlock_unlock(&dict->rwlock);
+       dictionary_name_value_index_del_nolock(dict, nv);
+
+       dict->entries--;
+
+       free(nv->name);
+
+       if(!(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE))
+               free(nv->value);
 
-       free(nv->value);
        free(nv);
 }
 
 // ----------------------------------------------------------------------------
 
-DICTIONARY *dictionary_create(void) {
+DICTIONARY *dictionary_create(uint32_t flags) {
        debug(D_DICTIONARY, "Creating dictionary.");
 
        DICTIONARY *dict = calloc(1, sizeof(DICTIONARY));
-       if(!dict) {
-               fatal("Cannot allocate DICTIONARY");
-               exit(1);
-       }
+       if(unlikely(!dict)) fatal("Cannot allocate DICTIONARY");
 
        avl_init(&dict->values_index, name_value_compare);
        pthread_rwlock_init(&dict->rwlock, NULL);
 
+       dict->flags = flags;
+
        return dict;
 }
 
 void dictionary_destroy(DICTIONARY *dict) {
        debug(D_DICTIONARY, "Destroying dictionary.");
 
-       pthread_rwlock_wrlock(&dict->rwlock);
-       while(dict->values) dictionary_name_value_destroy(dict, dict->values);
-       pthread_rwlock_unlock(&dict->rwlock);
+       dictionary_write_lock(dict);
+
+       while(dict->values_index.root)
+               dictionary_name_value_destroy_nolock(dict, (NAME_VALUE *)dict->values_index.root);
+
+       dictionary_unlock(dict);
 
        free(dict);
 }
@@ -118,27 +135,40 @@ void dictionary_destroy(DICTIONARY *dict) {
 void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) {
        debug(D_DICTIONARY, "SET dictionary entry with name '%s'.", name);
 
-       pthread_rwlock_rdlock(&dict->rwlock);
-       NAME_VALUE *nv = dictionary_name_value_index_find(dict, name, 0);
-       pthread_rwlock_unlock(&dict->rwlock);
-       if(!nv) {
+       uint32_t hash = simple_hash(name);
+
+       dictionary_read_lock(dict);
+       NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, hash);
+       dictionary_unlock(dict);
+
+       if(unlikely(!nv)) {
                debug(D_DICTIONARY, "Dictionary entry with name '%s' not found. Creating a new one.", name);
-               nv = dictionary_name_value_create(dict, name, value, value_len);
-               if(!nv) {
+
+               pthread_rwlock_wrlock(&dict->rwlock);
+               nv = dictionary_name_value_create_nolock(dict, name, value, value_len, hash);
+
+               if(unlikely(!nv))
                        fatal("Cannot create name_value.");
-                       exit(1);
-               }
-               return nv->value;
+
+               dictionary_unlock(dict);
        }
        else {
                debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", name);
-               pthread_rwlock_wrlock(&dict->rwlock);
-               void *old = nv->value;
-               nv->value = malloc(value_len);
-               if(!nv->value) fatal("Cannot allocate value of size %z", value_len);
-               memcpy(nv->value, value, value_len);
-               pthread_rwlock_unlock(&dict->rwlock);
-               free(old);
+
+               if(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)
+                       nv->value = value;
+               else {
+                       void *value = malloc(value_len),
+                                       *old = nv->value;
+
+                       if(unlikely(!nv->value))
+                               fatal("Cannot allocate value of size %z", value_len);
+
+                       memcpy(value, value, value_len);
+                       nv->value = value;
+
+                       free(old);
+               }
        }
 
        return nv->value;
@@ -147,10 +177,11 @@ void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t val
 void *dictionary_get(DICTIONARY *dict, const char *name) {
        debug(D_DICTIONARY, "GET dictionary entry with name '%s'.", name);
 
-       pthread_rwlock_rdlock(&dict->rwlock);
-       NAME_VALUE *nv = dictionary_name_value_index_find(dict, name, 0);
-       pthread_rwlock_unlock(&dict->rwlock);
-       if(!nv) {
+       dictionary_read_lock(dict);
+       NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, 0);
+       dictionary_unlock(dict);
+
+       if(unlikely(!nv)) {
                debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name);
                return NULL;
        }
@@ -158,3 +189,21 @@ void *dictionary_get(DICTIONARY *dict, const char *name) {
        debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name);
        return nv->value;
 }
+
+void dictionary_del(DICTIONARY *dict, const char *name) {
+       debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name);
+
+       dictionary_read_lock(dict);
+       NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, 0);
+       dictionary_unlock(dict);
+
+       if(unlikely(!nv)) {
+               debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name);
+               return;
+       }
+
+       debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name);
+       pthread_rwlock_wrlock(&dict->rwlock);
+       dictionary_name_value_destroy_nolock(dict, nv);
+       dictionary_unlock(dict);
+}

diff --git a/src/dictionary.h b/src/dictionary.h
index 9822b23c22c47efcb0ea831bf50c030554646d10..e9edab4c231d0d54fa2954d86862c54a74e21479 100644 (file)
--- a/src/dictionary.h
+++ b/src/dictionary.h
@@ -1,4 +1,7 @@
+#include <pthread.h>
+
 #include "web_buffer.h"
+#include "avl.h"
 
 #ifndef NETDATA_DICTIONARY_H
 #define NETDATA_DICTIONARY_H 1
@@ -8,22 +11,30 @@ typedef struct name_value {
 
        uint32_t hash;                  // a simple hash to speed up searching
                                                        // we first compare hashes, and only if the hashes are equal we do string comparisons
-
        char *name;
-       char *value;
-
-       struct name_value *next;
+       void *value;
 } NAME_VALUE;
 
 typedef struct dictionary {
-       NAME_VALUE *values;
+       uint32_t flags;
+
+       unsigned long long inserts;
+       unsigned long long deletes;
+       unsigned long long searches;
+       unsigned long long entries;
+
        avl_tree values_index;
        pthread_rwlock_t rwlock;
 } DICTIONARY;
 
-extern DICTIONARY *dictionary_create(void);
+#define DICTIONARY_FLAG_DEFAULT                                        0x00000000
+#define DICTIONARY_FLAG_SINGLE_THREADED                        0x00000001
+#define DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE  0x00000002
+
+extern DICTIONARY *dictionary_create(uint32_t flags);
 extern void dictionary_destroy(DICTIONARY *dict);
 extern void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len);
 extern void *dictionary_get(DICTIONARY *dict, const char *name);
+extern void dictionary_del(DICTIONARY *dict, const char *name);
 
 #endif /* NETDATA_DICTIONARY_H */

diff --git a/src/plugin_tc.c b/src/plugin_tc.c
index 2c7a55ceea910c4c50e249baba5a9ff09a3d2753..d70f52650b5601b5c52891b6c29df881eee6ab60 100644 (file)
--- a/src/plugin_tc.c
+++ b/src/plugin_tc.c
@@ -94,11 +94,13 @@ static int tc_device_compare(void* a, void* b) {
 avl_tree tc_device_root_index = {
                NULL,
                tc_device_compare,
+#ifndef AVL_WITHOUT_PTHREADS
 #ifdef AVL_LOCK_WITH_MUTEX
                PTHREAD_MUTEX_INITIALIZER
 #else
                PTHREAD_RWLOCK_INITIALIZER
 #endif
+#endif
 };
 
 #define tc_device_index_add(st) avl_insert(&tc_device_root_index, (avl *)(st))
@@ -349,10 +351,12 @@ static struct tc_device *tc_device_create(char *id)
                d->classes_index.compar = tc_class_compare;
 
                int lock;
+#ifndef AVL_WITHOUT_PTHREADS
 #ifdef AVL_LOCK_WITH_MUTEX
                lock = pthread_mutex_init(&d->classes_index.mutex, NULL);
 #else
                lock = pthread_rwlock_init(&d->classes_index.rwlock, NULL);
+#endif
 #endif
                if(lock != 0)
                        fatal("Failed to initialize plugin_tc mutex/rwlock, return code %d.", lock);