Merging upstream version 1.41.0.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 146 insertions, 84 deletions

diff --git a/libnetdata/string/string.c b/libnetdata/string/string.c
index 9385aa6e8..373d0c24c 100644
--- a/libnetdata/string/string.c
+++ b/libnetdata/string/string.c
@@ -8,6 +8,11 @@ typedef int32_t REFCOUNT;
 // ----------------------------------------------------------------------------
 // STRING implementation - dedup all STRING
 
+#define STRING_PARTITION_SHIFTS (0)
+#define STRING_PARTITIONS (256 >> STRING_PARTITION_SHIFTS)
+#define string_partition_str(str) ((uint8_t)((str)[0]) >> STRING_PARTITION_SHIFTS)
+#define string_partition(string) (string_partition_str((string)->str))
+
 struct netdata_string {
     uint32_t length;    // the string length including the terminating '\0'
 
@@ -18,20 +23,22 @@ struct netdata_string {
     const char str[];   // the string itself, is appended to this structure
 };
 
-static struct string_hashtable {
-    Pvoid_t JudyHSArray;        // the Judy array - hashtable
-    netdata_rwlock_t rwlock;    // the R/W lock to protect the Judy array
+static struct string_partition {
+    RW_SPINLOCK spinlock;       // the R/W spinlock to protect the Judy array
 
-    long int entries;           // the number of entries in the index
-    long int active_references; // the number of active references alive
-    long int memory;            // the memory used, without the JudyHS index
+    Pvoid_t JudyHSArray;        // the Judy array - hashtable
 
-    size_t inserts;             // the number of successful inserts to the index
-    size_t deletes;             // the number of successful deleted from the index
     size_t searches;            // the number of successful searches in the index
     size_t duplications;        // when a string is referenced
     size_t releases;            // when a string is unreferenced
 
+    size_t inserts;             // the number of successful inserts to the index
+    size_t deletes;             // the number of successful deleted from the index
+
+    long int entries;           // the number of entries in the index
+    long int active_references; // the number of active references alive
+    long int memory;            // the memory used, without the JudyHS index
+
 #ifdef NETDATA_INTERNAL_CHECKS
     // internal statistics
     size_t found_deleted_on_search;
@@ -41,50 +48,45 @@ static struct string_hashtable {
     size_t spins;
 #endif
 
-} string_base = {
-    .JudyHSArray = NULL,
-    .rwlock = NETDATA_RWLOCK_INITIALIZER,
-};
+} string_base[STRING_PARTITIONS] = { 0 };
 
 #ifdef NETDATA_INTERNAL_CHECKS
-#define string_internal_stats_add(var, val) __atomic_add_fetch(&string_base.var, val, __ATOMIC_RELAXED)
+#define string_internal_stats_add(partition, var, val) __atomic_add_fetch(&string_base[partition].var, val, __ATOMIC_RELAXED)
 #else
-#define string_internal_stats_add(var, val) do {;} while(0)
+#define string_internal_stats_add(partition, var, val) do {;} while(0)
 #endif
 
-#define string_stats_atomic_increment(var) __atomic_add_fetch(&string_base.var, 1, __ATOMIC_RELAXED)
-#define string_stats_atomic_decrement(var) __atomic_sub_fetch(&string_base.var, 1, __ATOMIC_RELAXED)
+#define string_stats_atomic_increment(partition, var) __atomic_add_fetch(&string_base[partition].var, 1, __ATOMIC_RELAXED)
+#define string_stats_atomic_decrement(partition, var) __atomic_sub_fetch(&string_base[partition].var, 1, __ATOMIC_RELAXED)
 
 void string_statistics(size_t *inserts, size_t *deletes, size_t *searches, size_t *entries, size_t *references, size_t *memory, size_t *duplications, size_t *releases) {
-    if(inserts)
-        *inserts = string_base.inserts;
-
-    if(deletes)
-        *deletes = string_base.deletes;
-
-    if(searches)
-        *searches = string_base.searches;
-
-    if(entries)
-        *entries = (size_t)string_base.entries;
-
-    if(references)
-        *references = (size_t)string_base.active_references;
-
-    if(memory)
-        *memory = (size_t)string_base.memory;
-
-    if(duplications)
-        *duplications = string_base.duplications;
-
-    if(releases)
-        *releases = string_base.releases;
+    if (inserts) *inserts = 0;
+    if (deletes) *deletes = 0;
+    if (searches) *searches = 0;
+    if (entries) *entries = 0;
+    if (references) *references = 0;
+    if (memory) *memory = 0;
+    if (duplications) *duplications = 0;
+    if (releases) *releases = 0;
+
+    for(size_t i = 0; i < STRING_PARTITIONS ;i++) {
+        if (inserts)        *inserts        += string_base[i].inserts;
+        if (deletes)        *deletes        += string_base[i].deletes;
+        if (searches)       *searches       += string_base[i].searches;
+        if (entries)        *entries        += (size_t) string_base[i].entries;
+        if (references)     *references     += (size_t) string_base[i].active_references;
+        if (memory)         *memory         += (size_t) string_base[i].memory;
+        if (duplications)   *duplications   += string_base[i].duplications;
+        if (releases)       *releases       += string_base[i].releases;
+    }
 }
 
 #define string_entry_acquire(se) __atomic_add_fetch(&((se)->refcount), 1, __ATOMIC_SEQ_CST);
 #define string_entry_release(se) __atomic_sub_fetch(&((se)->refcount), 1, __ATOMIC_SEQ_CST);
 
 static inline bool string_entry_check_and_acquire(STRING *se) {
+    uint8_t partition = string_partition(se);
+
     REFCOUNT expected, desired, count = 0;
 
     expected = __atomic_load_n(&se->refcount, __ATOMIC_SEQ_CST);
@@ -96,7 +98,7 @@ static inline bool string_entry_check_and_acquire(STRING *se) {
             // We cannot use this.
             // The reference counter reached value zero,
             // so another thread is deleting this.
-            string_internal_stats_add(spins, count - 1);
+            string_internal_stats_add(partition, spins, count - 1);
             return false;
         }
 
@@ -104,11 +106,11 @@ static inline bool string_entry_check_and_acquire(STRING *se) {
 
     } while(!__atomic_compare_exchange_n(&se->refcount, &expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST));
 
-    string_internal_stats_add(spins, count - 1);
+    string_internal_stats_add(partition, spins, count - 1);
 
     // statistics
     // string_base.active_references is altered at the in string_strdupz() and string_freez()
-    string_stats_atomic_increment(duplications);
+    string_stats_atomic_increment(partition, duplications);
 
     return true;
 }
@@ -123,9 +125,11 @@ STRING *string_dup(STRING *string) {
 
     string_entry_acquire(string);
 
+    uint8_t partition = string_partition(string);
+
     // statistics
-    string_stats_atomic_increment(active_references);
-    string_stats_atomic_increment(duplications);
+    string_stats_atomic_increment(partition, active_references);
+    string_stats_atomic_increment(partition, duplications);
 
     return string;
 }
@@ -134,26 +138,28 @@ STRING *string_dup(STRING *string) {
 static inline STRING *string_index_search(const char *str, size_t length) {
     STRING *string;
 
+    uint8_t partition = string_partition_str(str);
+
     // Find the string in the index
     // With a read-lock so that multiple readers can use the index concurrently.
 
-    netdata_rwlock_rdlock(&string_base.rwlock);
+    rw_spinlock_read_lock(&string_base[partition].spinlock);
 
     Pvoid_t *Rc;
-    Rc = JudyHSGet(string_base.JudyHSArray, (void *)str, length);
+    Rc = JudyHSGet(string_base[partition].JudyHSArray, (void *)str, length - 1);
     if(likely(Rc)) {
         // found in the hash table
         string = *Rc;
 
         if(string_entry_check_and_acquire(string)) {
             // we can use this entry
-            string_internal_stats_add(found_available_on_search, 1);
+            string_internal_stats_add(partition, found_available_on_search, 1);
         }
         else {
             // this entry is about to be deleted by another thread
             // do not touch it, let it go...
             string = NULL;
-            string_internal_stats_add(found_deleted_on_search, 1);
+            string_internal_stats_add(partition, found_deleted_on_search, 1);
         }
     }
     else {
@@ -161,8 +167,8 @@ static inline STRING *string_index_search(const char *str, size_t length) {
         string = NULL;
     }
 
-    string_stats_atomic_increment(searches);
-    netdata_rwlock_unlock(&string_base.rwlock);
+    string_stats_atomic_increment(partition, searches);
+    rw_spinlock_read_unlock(&string_base[partition].spinlock);
 
     return string;
 }
@@ -175,12 +181,14 @@ static inline STRING *string_index_search(const char *str, size_t length) {
 static inline STRING *string_index_insert(const char *str, size_t length) {
     STRING *string;
 
-    netdata_rwlock_wrlock(&string_base.rwlock);
+    uint8_t partition = string_partition_str(str);
+
+    rw_spinlock_write_lock(&string_base[partition].spinlock);
 
     STRING **ptr;
     {
         JError_t J_Error;
-        Pvoid_t *Rc = JudyHSIns(&string_base.JudyHSArray, (void *)str, length, &J_Error);
+        Pvoid_t *Rc = JudyHSIns(&string_base[partition].JudyHSArray, (void *)str, length - 1, &J_Error);
         if (unlikely(Rc == PJERR)) {
             fatal(
                 "STRING: Cannot insert entry with name '%s' to JudyHS, JU_ERRNO_* == %u, ID == %d",
@@ -199,9 +207,9 @@ static inline STRING *string_index_insert(const char *str, size_t length) {
         string->length = length;
         string->refcount = 1;
         *ptr = string;
-        string_base.inserts++;
-        string_base.entries++;
-        string_base.memory += (long)(mem_size + JUDYHS_INDEX_SIZE_ESTIMATE(length));
+        string_base[partition].inserts++;
+        string_base[partition].entries++;
+        string_base[partition].memory += (long)(mem_size + JUDYHS_INDEX_SIZE_ESTIMATE(length));
     }
     else {
         // the item is already in the index
@@ -209,25 +217,27 @@ static inline STRING *string_index_insert(const char *str, size_t length) {
 
         if(string_entry_check_and_acquire(string)) {
             // we can use this entry
-            string_internal_stats_add(found_available_on_insert, 1);
+            string_internal_stats_add(partition, found_available_on_insert, 1);
         }
         else {
             // this entry is about to be deleted by another thread
             // do not touch it, let it go...
             string = NULL;
-            string_internal_stats_add(found_deleted_on_insert, 1);
+            string_internal_stats_add(partition, found_deleted_on_insert, 1);
         }
 
-        string_stats_atomic_increment(searches);
+        string_stats_atomic_increment(partition, searches);
     }
 
-    netdata_rwlock_unlock(&string_base.rwlock);
+    rw_spinlock_write_unlock(&string_base[partition].spinlock);
     return string;
 }
 
 // delete an entry from the index
 static inline void string_index_delete(STRING *string) {
-    netdata_rwlock_wrlock(&string_base.rwlock);
+    uint8_t partition = string_partition(string);
+
+    rw_spinlock_write_lock(&string_base[partition].spinlock);
 
 #ifdef NETDATA_INTERNAL_CHECKS
     if(unlikely(__atomic_load_n(&string->refcount, __ATOMIC_SEQ_CST) != 0))
@@ -236,11 +246,11 @@ static inline void string_index_delete(STRING *string) {
 
     bool deleted = false;
 
-    if (likely(string_base.JudyHSArray)) {
+    if (likely(string_base[partition].JudyHSArray)) {
         JError_t J_Error;
-        int ret = JudyHSDel(&string_base.JudyHSArray, (void *)string->str, string->length, &J_Error);
+        int ret = JudyHSDel(&string_base[partition].JudyHSArray, (void *)string->str, string->length - 1, &J_Error);
         if (unlikely(ret == JERR)) {
-            error(
+            netdata_log_error(
                 "STRING: Cannot delete entry with name '%s' from JudyHS, JU_ERRNO_* == %u, ID == %d",
                 string->str,
                 JU_ERRNO(&J_Error),
@@ -250,21 +260,23 @@ static inline void string_index_delete(STRING *string) {
     }
 
     if (unlikely(!deleted))
-        error("STRING: tried to delete '%s' that is not in the index. Ignoring it.", string->str);
+        netdata_log_error("STRING: tried to delete '%s' that is not in the index. Ignoring it.", string->str);
     else {
         size_t mem_size = sizeof(STRING) + string->length;
-        string_base.deletes++;
-        string_base.entries--;
-        string_base.memory -= (long)(mem_size + JUDYHS_INDEX_SIZE_ESTIMATE(string->length));
+        string_base[partition].deletes++;
+        string_base[partition].entries--;
+        string_base[partition].memory -= (long)(mem_size + JUDYHS_INDEX_SIZE_ESTIMATE(string->length));
         freez(string);
     }
 
-    netdata_rwlock_unlock(&string_base.rwlock);
+    rw_spinlock_write_unlock(&string_base[partition].spinlock);
 }
 
 STRING *string_strdupz(const char *str) {
     if(unlikely(!str || !*str)) return NULL;
 
+    uint8_t partition = string_partition_str(str);
+
     size_t length = strlen(str) + 1;
     STRING *string = string_index_search(str, length);
 
@@ -277,7 +289,7 @@ STRING *string_strdupz(const char *str) {
     }
 
     // statistics
-    string_stats_atomic_increment(active_references);
+    string_stats_atomic_increment(partition, active_references);
 
     return string;
 }
@@ -285,6 +297,7 @@ STRING *string_strdupz(const char *str) {
 void string_freez(STRING *string) {
     if(unlikely(!string)) return;
 
+    uint8_t partition = string_partition(string);
     REFCOUNT refcount = string_entry_release(string);
 
 #ifdef NETDATA_INTERNAL_CHECKS
@@ -296,8 +309,8 @@ void string_freez(STRING *string) {
         string_index_delete(string);
 
     // statistics
-    string_stats_atomic_decrement(active_references);
-    string_stats_atomic_increment(releases);
+    string_stats_atomic_decrement(partition, active_references);
+    string_stats_atomic_increment(partition, releases);
 }
 
 inline size_t string_strlen(STRING *string) {
@@ -405,6 +418,54 @@ static void string_unittest_free_char_pp(char **pp, size_t entries) {
     freez(pp);
 }
 
+static long unittest_string_entries(void) {
+    long entries = 0;
+    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
+        entries += string_base[p].entries;
+
+    return entries;
+}
+
+#ifdef NETDATA_INTERNAL_CHECKS
+
+static size_t unittest_string_found_deleted_on_search(void) {
+    size_t entries = 0;
+    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
+        entries += string_base[p].found_deleted_on_search;
+
+    return entries;
+}
+static size_t unittest_string_found_available_on_search(void) {
+    size_t entries = 0;
+    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
+        entries += string_base[p].found_available_on_search;
+
+    return entries;
+}
+static size_t unittest_string_found_deleted_on_insert(void) {
+    size_t entries = 0;
+    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
+        entries += string_base[p].found_deleted_on_insert;
+
+    return entries;
+}
+static size_t unittest_string_found_available_on_insert(void) {
+    size_t entries = 0;
+    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
+        entries += string_base[p].found_available_on_insert;
+
+    return entries;
+}
+static size_t unittest_string_spins(void) {
+    size_t entries = 0;
+    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
+        entries += string_base[p].spins;
+
+    return entries;
+}
+
+#endif // NETDATA_INTERNAL_CHECKS
+
 int string_unittest(size_t entries) {
     size_t errors = 0;
 
@@ -413,7 +474,7 @@ int string_unittest(size_t entries) {
 
     // check string
     {
-        long int string_entries_starting = string_base.entries;
+        long entries_starting = unittest_string_entries();
 
         fprintf(stderr, "\nChecking strings...\n");
 
@@ -496,9 +557,10 @@ int string_unittest(size_t entries) {
 
         freez(strings);
 
-        if(string_base.entries != string_entries_starting + 2) {
+        if(unittest_string_entries() != entries_starting + 2) {
             errors++;
-            fprintf(stderr, "ERROR: strings dictionary should have %ld items but it has %ld\n", string_entries_starting + 2, string_base.entries);
+            fprintf(stderr, "ERROR: strings dictionary should have %ld items but it has %ld\n",
+                    entries_starting + 2, unittest_string_entries());
         }
         else
             fprintf(stderr, "OK: strings dictionary has 2 items\n");
@@ -551,11 +613,11 @@ int string_unittest(size_t entries) {
         };
 
 #ifdef NETDATA_INTERNAL_CHECKS
-        size_t ofound_deleted_on_search = string_base.found_deleted_on_search,
-               ofound_available_on_search = string_base.found_available_on_search,
-               ofound_deleted_on_insert = string_base.found_deleted_on_insert,
-               ofound_available_on_insert = string_base.found_available_on_insert,
-               ospins = string_base.spins;
+        size_t ofound_deleted_on_search = unittest_string_found_deleted_on_search(),
+               ofound_available_on_search = unittest_string_found_available_on_search(),
+               ofound_deleted_on_insert = unittest_string_found_deleted_on_insert(),
+               ofound_available_on_insert = unittest_string_found_available_on_insert(),
+               ospins = unittest_string_spins();
 #endif
 
         size_t oinserts, odeletes, osearches, oentries, oreferences, omemory, oduplications, oreleases;
@@ -592,11 +654,11 @@ int string_unittest(size_t entries) {
                 inserts - oinserts, deletes - odeletes, searches - osearches, sentries - oentries, references - oreferences, memory - omemory, duplications - oduplications, releases - oreleases);
 
 #ifdef NETDATA_INTERNAL_CHECKS
-        size_t found_deleted_on_search = string_base.found_deleted_on_search,
-               found_available_on_search = string_base.found_available_on_search,
-               found_deleted_on_insert = string_base.found_deleted_on_insert,
-               found_available_on_insert = string_base.found_available_on_insert,
-               spins = string_base.spins;
+        size_t found_deleted_on_search = unittest_string_found_deleted_on_search(),
+               found_available_on_search = unittest_string_found_available_on_search(),
+               found_deleted_on_insert = unittest_string_found_deleted_on_insert(),
+               found_available_on_insert = unittest_string_found_available_on_insert(),
+               spins = unittest_string_spins();
 
         fprintf(stderr, "on insert: %zu ok + %zu deleted\non search: %zu ok + %zu deleted\nspins: %zu\n",
                 found_available_on_insert - ofound_available_on_insert,