diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/command.c | 3 | ||||
| -rw-r--r-- | lib/distribute.c | 3 | ||||
| -rw-r--r-- | lib/frr_pthread.c | 2 | ||||
| -rw-r--r-- | lib/hash.c | 234 | ||||
| -rw-r--r-- | lib/hash.h | 26 | ||||
| -rw-r--r-- | lib/if_rmap.c | 2 | ||||
| -rw-r--r-- | lib/qobj.c | 2 | ||||
| -rw-r--r-- | lib/routemap.c | 6 | ||||
| -rw-r--r-- | lib/thread.c | 2 |
9 files changed, 252 insertions, 28 deletions
diff --git a/lib/command.c b/lib/command.c index f019473308..de8899687c 100644 --- a/lib/command.c +++ b/lib/command.c @@ -233,7 +233,7 @@ install_node (struct cmd_node *node, // add start node struct cmd_token *token = cmd_token_new (START_TKN, CMD_ATTR_NORMAL, NULL, NULL); graph_new_node (node->cmdgraph, token, (void (*)(void *)) &cmd_token_del); - node->cmd_hash = hash_create (cmd_hash_key, cmd_hash_cmp); + node->cmd_hash = hash_create (cmd_hash_key, cmd_hash_cmp, NULL); } /** @@ -2520,6 +2520,7 @@ cmd_init (int terminal) thread_cmd_init (); workqueue_cmd_init (); + hash_cmd_init (); } install_element (CONFIG_NODE, &hostname_cmd); diff --git a/lib/distribute.c b/lib/distribute.c index c771f018c2..79d7b18ff5 100644 --- a/lib/distribute.c +++ b/lib/distribute.c @@ -522,7 +522,8 @@ void distribute_list_init (int node) { disthash = hash_create (distribute_hash_make, - (int (*) (const void *, const void *)) distribute_cmp); + (int (*) (const void *, const void *)) + distribute_cmp, NULL); /* vtysh command-extraction doesn't grok install_element(node, ) */ if (node == RIP_NODE) { diff --git a/lib/frr_pthread.c b/lib/frr_pthread.c index 614c722be1..4b9bed4524 100644 --- a/lib/frr_pthread.c +++ b/lib/frr_pthread.c @@ -55,7 +55,7 @@ void frr_pthread_init() pthread_mutex_lock(&pthread_table_mtx); { pthread_table = - hash_create(pthread_table_hash_key, pthread_table_hash_cmp); + hash_create(pthread_table_hash_key, pthread_table_hash_cmp, NULL); } pthread_mutex_unlock(&pthread_table_mtx); } diff --git a/lib/hash.c b/lib/hash.c index 553a137eb6..95643bbae0 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -19,23 +19,33 @@ */ #include <zebra.h> +#include <math.h> #include "hash.h" #include "memory.h" +#include "linklist.h" +#include "termtable.h" +#include "vty.h" +#include "command.h" +#include "libfrr.h" DEFINE_MTYPE( LIB, HASH, "Hash") DEFINE_MTYPE( LIB, HASH_BACKET, "Hash Bucket") DEFINE_MTYPE_STATIC(LIB, HASH_INDEX, "Hash Index") +pthread_mutex_t _hashes_mtx = PTHREAD_MUTEX_INITIALIZER; +static struct list *_hashes; + /* Allocate a new hash. */ struct hash * hash_create_size (unsigned int size, unsigned int (*hash_key) (void *), - int (*hash_cmp) (const void *, const void *)) + int (*hash_cmp) (const void *, const void *), + const char *name) { struct hash *hash; assert ((size & (size-1)) == 0); - hash = XMALLOC (MTYPE_HASH, sizeof (struct hash)); + hash = XCALLOC (MTYPE_HASH, sizeof (struct hash)); hash->index = XCALLOC (MTYPE_HASH_INDEX, sizeof (struct hash_backet *) * size); hash->size = size; @@ -43,6 +53,17 @@ hash_create_size (unsigned int size, unsigned int (*hash_key) (void *), hash->hash_key = hash_key; hash->hash_cmp = hash_cmp; hash->count = 0; + hash->name = name ? XSTRDUP(MTYPE_HASH, name) : NULL; + hash->stats.empty = hash->size; + + pthread_mutex_lock (&_hashes_mtx); + { + if (!_hashes) + _hashes = list_new(); + + listnode_add (_hashes, hash); + } + pthread_mutex_unlock (&_hashes_mtx); return hash; } @@ -50,9 +71,10 @@ hash_create_size (unsigned int size, unsigned int (*hash_key) (void *), /* Allocate a new hash with default hash size. */ struct hash * hash_create (unsigned int (*hash_key) (void *), - int (*hash_cmp) (const void *, const void *)) + int (*hash_cmp) (const void *, const void *), + const char *name) { - return hash_create_size (HASH_INITIAL_SIZE, hash_key, hash_cmp); + return hash_create_size (HASH_INITIAL_SIZE, hash_key, hash_cmp, name); } /* Utility function for hash_get(). When this function is specified @@ -64,6 +86,15 @@ hash_alloc_intern (void *arg) return arg; } +#define hash_update_ssq(hz, old, new) \ + do { \ + long double res; \ + res = powl(old, 2.0); \ + hz->stats.ssq -= (uint64_t) res;\ + res = powl(new, 2.0); \ + hz->stats.ssq += (uint64_t) res; \ + } while (0); \ + /* Expand hash if the chain length exceeds the threshold. */ static void hash_expand (struct hash *hash) { @@ -75,6 +106,8 @@ static void hash_expand (struct hash *hash) if (new_index == NULL) return; + hash->stats.empty = new_size; + for (i = 0; i < hash->size; i++) for (hb = hash->index[i]; hb; hb = hbnext) { @@ -82,6 +115,19 @@ static void hash_expand (struct hash *hash) hbnext = hb->next; hb->next = new_index[h]; + + int oldlen = hb->next ? hb->next->len : 0; + int newlen = oldlen + 1; + + if (newlen == 1) + hash->stats.empty--; + else + hb->next->len = 0; + + hb->len = newlen; + + hash_update_ssq(hash, oldlen, newlen); + new_index[h] = hb; } @@ -91,19 +137,17 @@ static void hash_expand (struct hash *hash) hash->index = new_index; /* Ideally, new index should have chains half as long as the original. - If expansion didn't help, then not worth expanding again, - the problem is the hash function. */ + * If expansion didn't help, then not worth expanding again, + * the problem is the hash function. */ losers = 0; for (i = 0; i < hash->size; i++) { - unsigned int len = 0; - for (hb = hash->index[i]; hb; hb = hb->next) - { - if (++len > HASH_THRESHOLD/2) - ++losers; - if (len >= HASH_THRESHOLD) - hash->no_expand = 1; - } + unsigned int len = hash->index[i] ? hash->index[i]->len : 0; + + if (len > HASH_THRESHOLD/2) + ++losers; + if (len >= HASH_THRESHOLD) + hash->no_expand = 1; } if (losers > hash->count / 2) @@ -145,12 +189,25 @@ hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *)) index = key & (hash->size - 1); } - backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet)); + backet = XCALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet)); backet->data = newdata; backet->key = key; backet->next = hash->index[index]; hash->index[index] = backet; hash->count++; + + int oldlen = backet->next ? backet->next->len : 0; + int newlen = oldlen + 1; + + if (newlen == 1) + hash->stats.empty--; + else + backet->next->len = 0; + + backet->len = newlen; + + hash_update_ssq(hash, oldlen, newlen); + return backet->data; } return NULL; @@ -193,11 +250,21 @@ hash_release (struct hash *hash, void *data) { if (backet->key == key && (*hash->hash_cmp) (backet->data, data)) { - if (backet == pp) + int oldlen = hash->index[index]->len; + int newlen = oldlen - 1; + + if (backet == pp) hash->index[index] = backet->next; - else + else pp->next = backet->next; + if (hash->index[index]) + hash->index[index]->len = newlen; + else + hash->stats.empty++; + + hash_update_ssq(hash, oldlen, newlen); + ret = backet->data; XFREE (MTYPE_HASH_BACKET, backet); hash->count--; @@ -275,6 +342,9 @@ hash_clean (struct hash *hash, void (*free_func) (void *)) } hash->index[i] = NULL; } + + hash->stats.ssq = 0; + hash->stats.empty = hash->size; } /* Free hash memory. You may call hash_clean before call this @@ -282,6 +352,136 @@ hash_clean (struct hash *hash, void (*free_func) (void *)) void hash_free (struct hash *hash) { + pthread_mutex_lock (&_hashes_mtx); + { + if (_hashes) + { + listnode_delete (_hashes, hash); + if (_hashes->count == 0) + { + list_delete (_hashes); + _hashes = NULL; + } + } + } + pthread_mutex_unlock (&_hashes_mtx); + + if (hash->name) + XFREE (MTYPE_HASH, hash->name); + XFREE (MTYPE_HASH_INDEX, hash->index); XFREE (MTYPE_HASH, hash); } + + +/* CLI commands ------------------------------------------------------------ */ + +DEFUN(show_hash_stats, + show_hash_stats_cmd, + "show hashtable [statistics]", + SHOW_STR + "Statistics about hash tables\n" + "Statistics about hash tables\n") +{ + struct hash *h; + struct listnode *ln; + struct ttable *tt = ttable_new (&ttable_styles[TTSTYLE_BLANK]); + + ttable_add_row (tt, "Hash table|Buckets|Entries|Empty|LF|SD|FLF|SD"); + tt->style.cell.lpad = 2; + tt->style.cell.rpad = 1; + tt->style.corner = '+'; + ttable_restyle (tt); + ttable_rowseps (tt, 0, BOTTOM, true, '-'); + + /* Summary statistics calculated are: + * + * - Load factor: This is the number of elements in the table divided by the + * number of buckets. Since this hash table implementation uses chaining, + * this value can be greater than 1. This number provides information on + * how 'full' the table is, but does not provide information on how evenly + * distributed the elements are. Notably, a load factor >= 1 does not imply + * that every bucket has an element; with a pathological hash function, all + * elements could be in a single bucket. + * + * - Full load factor: this is the number of elements in the table divided by + * the number of buckets that have some elements in them. + * + * - Std. Dev.: This is the standard deviation calculated from the relevant + * load factor. If the load factor is the mean of number of elements per + * bucket, the standard deviation measures how much any particular bucket + * is likely to deviate from the mean. As a rule of thumb this number + * should be less than 2, and ideally <= 1 for optimal performance. A + * number larger than 3 generally indicates a poor hash function. + */ + + double lf; // load factor + double flf; // full load factor + double var; // overall variance + double fvar; // full variance + double stdv; // overall stddev + double fstdv; // full stddev + + long double x2; // h->count ^ 2 + long double ldc; // (long double) h->count + long double full; // h->size - h->stats.empty + long double ssq; // ssq casted to long double + + pthread_mutex_lock (&_hashes_mtx); + for (ALL_LIST_ELEMENTS_RO (_hashes, ln, h)) + { + if (!h->name) + continue; + + ssq = (long double) h->stats.ssq; + x2 = powl(h->count, 2.0); + ldc = (long double) h->count; + full = h->size - h->stats.empty; + lf = h->count / (double) h->size; + flf = full ? h->count / (double) (full) : 0; + var = ldc ? (1.0 / ldc) * (ssq - x2 / ldc) : 0; + fvar = full ? (1.0 / full) * (ssq - x2 / full) : 0; + var = (var < .0001) ? 0 : var; + fvar = (fvar < .0001) ? 0 : fvar; + stdv = sqrt(var); + fstdv = sqrt(fvar); + + ttable_add_row (tt, "%s|%d|%ld|%.0f%%|%.2lf|%.2lf|%.2lf|%.2lf", h->name, + h->size, h->count, + (h->stats.empty / (double) h->size)*100, lf, stdv, flf, + fstdv); + } + pthread_mutex_unlock (&_hashes_mtx); + + /* display header */ + char header[] = "Showing hash table statistics for "; + char underln[sizeof(header) + strlen(frr_protonameinst)]; + memset (underln, '-', sizeof(underln)); + underln[sizeof(underln) - 1] = '\0'; + vty_outln (vty, "%s%s", header, frr_protonameinst); + vty_outln (vty, "%s", underln); + + vty_outln (vty, "# allocated: %d", _hashes->count); + vty_outln (vty, "# named: %d%s", tt->nrows - 1, VTYNL); + + if (tt->nrows > 1) + { + ttable_colseps (tt, 0, RIGHT, true, '|'); + char *table = ttable_dump (tt, VTYNL); + vty_out (vty, "%s%s", table, VTYNL); + XFREE (MTYPE_TMP, table); + } + else + vty_outln (vty, "No named hash tables to display."); + + ttable_del (tt); + + return CMD_SUCCESS; +} + +void +hash_cmd_init () +{ + _hashes = list_new(); + install_element (ENABLE_NODE, &show_hash_stats_cmd); +} diff --git a/lib/hash.h b/lib/hash.h index bafb35a2a3..9395440acb 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -22,6 +22,7 @@ #define _ZEBRA_HASH_H #include "memory.h" +#include "frratomic.h" DECLARE_MTYPE(HASH) DECLARE_MTYPE(HASH_BACKET) @@ -35,6 +36,10 @@ DECLARE_MTYPE(HASH_BACKET) struct hash_backet { + /* if this backet is the head of the linked listed, len denotes the number of + * elements in the list */ + int len; + /* Linked list. */ struct hash_backet *next; @@ -45,6 +50,14 @@ struct hash_backet void *data; }; +struct hashstats +{ + /* number of empty hash buckets */ + _Atomic int empty; + /* sum of squares of bucket length */ + _Atomic uint64_t ssq; +}; + struct hash { /* Hash backet. */ @@ -64,12 +77,19 @@ struct hash /* Backet alloc. */ unsigned long count; + + struct hashstats stats; + + /* hash name */ + char *name; }; extern struct hash *hash_create (unsigned int (*) (void *), - int (*) (const void *, const void *)); + int (*) (const void *, const void *), + const char *); extern struct hash *hash_create_size (unsigned int, unsigned int (*) (void *), - int (*) (const void *, const void *)); + int (*) (const void *, const void *), + const char *); extern void *hash_get (struct hash *, void *, void * (*) (void *)); extern void *hash_alloc_intern (void *); @@ -87,4 +107,6 @@ extern void hash_free (struct hash *); extern unsigned int string_hash_make (const char *); +extern void hash_cmd_init (void); + #endif /* _ZEBRA_HASH_H */ diff --git a/lib/if_rmap.c b/lib/if_rmap.c index f9c6a55d7b..32bebd67ff 100644 --- a/lib/if_rmap.c +++ b/lib/if_rmap.c @@ -316,7 +316,7 @@ if_rmap_reset () void if_rmap_init (int node) { - ifrmaphash = hash_create (if_rmap_hash_make, if_rmap_hash_cmp); + ifrmaphash = hash_create (if_rmap_hash_make, if_rmap_hash_cmp, NULL); if (node == RIPNG_NODE) { } else if (node == RIP_NODE) { install_element (RIP_NODE, &if_rmap_cmd); diff --git a/lib/qobj.c b/lib/qobj.c index 4cf7fbca7b..8fa8163970 100644 --- a/lib/qobj.c +++ b/lib/qobj.c @@ -97,7 +97,7 @@ void qobj_init (void) if (!nodes) { pthread_rwlock_init (&nodes_lock, NULL); - nodes = hash_create (qobj_key, qobj_cmp); + nodes = hash_create (qobj_key, qobj_cmp, NULL); } } diff --git a/lib/routemap.c b/lib/routemap.c index 9eb28888ad..caba8afd71 100644 --- a/lib/routemap.c +++ b/lib/routemap.c @@ -1767,7 +1767,7 @@ route_map_dep_hash_alloc(void *p) dep_entry = XCALLOC(MTYPE_ROUTE_MAP_DEP, sizeof(struct route_map_dep)); dep_entry->dep_name = XSTRDUP(MTYPE_ROUTE_MAP_NAME, dep_name); dep_entry->dep_rmap_hash = hash_create(route_map_dep_hash_make_key, - route_map_rmap_hash_cmp); + route_map_rmap_hash_cmp, NULL); dep_entry->this_hash = NULL; return((void *)dep_entry); @@ -2986,11 +2986,11 @@ route_map_init (void) /* Make vector for match and set. */ route_match_vec = vector_init (1); route_set_vec = vector_init (1); - route_map_master_hash = hash_create(route_map_hash_key_make, route_map_hash_cmp); + route_map_master_hash = hash_create(route_map_hash_key_make, route_map_hash_cmp, NULL); for (i = 1; i < ROUTE_MAP_DEP_MAX; i++) route_map_dep_hash[i] = hash_create(route_map_dep_hash_make_key, - route_map_dep_hash_cmp); + route_map_dep_hash_cmp, NULL); cmd_variable_handler_register(rmap_var_handlers); diff --git a/lib/thread.c b/lib/thread.c index 71b0bb2aed..4e72d4c96f 100644 --- a/lib/thread.c +++ b/lib/thread.c @@ -388,7 +388,7 @@ thread_master_create (const char *name) rv->cpu_record = hash_create ((unsigned int (*) (void *))cpu_record_hash_key, (int (*) (const void *, const void *)) - cpu_record_hash_cmp); + cpu_record_hash_cmp, NULL); /* Initialize the timer queues */ |