diff options
Diffstat (limited to 'lib/hash.c')
| -rw-r--r-- | lib/hash.c | 464 |
1 files changed, 464 insertions, 0 deletions
diff --git a/lib/hash.c b/lib/hash.c new file mode 100644 index 0000000..4b371b4 --- /dev/null +++ b/lib/hash.c @@ -0,0 +1,464 @@ +/* Hash routine. + * Copyright (C) 1998 Kunihiro Ishiguro + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#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" +#include "frr_pthread.h" +#include "libfrr_trace.h" + +DEFINE_MTYPE_STATIC(LIB, HASH, "Hash"); +DEFINE_MTYPE_STATIC(LIB, HASH_BUCKET, "Hash Bucket"); +DEFINE_MTYPE_STATIC(LIB, HASH_INDEX, "Hash Index"); + +static pthread_mutex_t _hashes_mtx = PTHREAD_MUTEX_INITIALIZER; +static struct list *_hashes; + +struct hash *hash_create_size(unsigned int size, + unsigned int (*hash_key)(const void *), + bool (*hash_cmp)(const void *, const void *), + const char *name) +{ + struct hash *hash; + + assert((size & (size - 1)) == 0); + hash = XCALLOC(MTYPE_HASH, sizeof(struct hash)); + hash->index = + XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_bucket *) * size); + hash->size = size; + 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; + + frr_with_mutex (&_hashes_mtx) { + if (!_hashes) + _hashes = list_new(); + + listnode_add(_hashes, hash); + } + + return hash; +} + +struct hash *hash_create(unsigned int (*hash_key)(const void *), + bool (*hash_cmp)(const void *, const void *), + const char *name) +{ + return hash_create_size(HASH_INITIAL_SIZE, hash_key, hash_cmp, name); +} + +void *hash_alloc_intern(void *arg) +{ + return arg; +} + +/* + * ssq = ssq + (new^2 - old^2) + * = ssq + ((new + old) * (new - old)) + */ +#define hash_update_ssq(hz, old, new) \ + do { \ + int _adjust = (new + old) * (new - old); \ + if (_adjust < 0) \ + atomic_fetch_sub_explicit(&hz->stats.ssq, -_adjust, \ + memory_order_relaxed); \ + else \ + atomic_fetch_add_explicit(&hz->stats.ssq, _adjust, \ + memory_order_relaxed); \ + } while (0) + +/* Expand hash if the chain length exceeds the threshold. */ +static void hash_expand(struct hash *hash) +{ + unsigned int i, new_size; + struct hash_bucket *hb, *hbnext, **new_index; + + new_size = hash->size * 2; + + if (hash->max_size && new_size > hash->max_size) + return; + + new_index = XCALLOC(MTYPE_HASH_INDEX, + sizeof(struct hash_bucket *) * new_size); + + hash->stats.empty = new_size; + + for (i = 0; i < hash->size; i++) + for (hb = hash->index[i]; hb; hb = hbnext) { + unsigned int h = hb->key & (new_size - 1); + + 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; + } + + /* Switch to new table */ + XFREE(MTYPE_HASH_INDEX, hash->index); + hash->size = new_size; + hash->index = new_index; +} + +void *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *)) +{ + frrtrace(2, frr_libfrr, hash_get, hash, data); + + unsigned int key; + unsigned int index; + void *newdata; + struct hash_bucket *bucket; + + if (!alloc_func && !hash->count) + return NULL; + + key = (*hash->hash_key)(data); + index = key & (hash->size - 1); + + for (bucket = hash->index[index]; bucket != NULL; + bucket = bucket->next) { + if (bucket->key == key && (*hash->hash_cmp)(bucket->data, data)) + return bucket->data; + } + + if (alloc_func) { + newdata = (*alloc_func)(data); + if (newdata == NULL) + return NULL; + + if (HASH_THRESHOLD(hash->count + 1, hash->size)) { + hash_expand(hash); + index = key & (hash->size - 1); + } + + bucket = XCALLOC(MTYPE_HASH_BUCKET, sizeof(struct hash_bucket)); + bucket->data = newdata; + bucket->key = key; + bucket->next = hash->index[index]; + hash->index[index] = bucket; + hash->count++; + + frrtrace(3, frr_libfrr, hash_insert, hash, data, key); + + int oldlen = bucket->next ? bucket->next->len : 0; + int newlen = oldlen + 1; + + if (newlen == 1) + hash->stats.empty--; + else + bucket->next->len = 0; + + bucket->len = newlen; + + hash_update_ssq(hash, oldlen, newlen); + + return bucket->data; + } + return NULL; +} + +void *hash_lookup(struct hash *hash, void *data) +{ + return hash_get(hash, data, NULL); +} + +unsigned int string_hash_make(const char *str) +{ + unsigned int hash = 0; + + while (*str) + hash = (hash * 33) ^ (unsigned int)*str++; + + return hash; +} + +void *hash_release(struct hash *hash, void *data) +{ + void *ret = NULL; + unsigned int key; + unsigned int index; + struct hash_bucket *bucket; + struct hash_bucket *pp; + + key = (*hash->hash_key)(data); + index = key & (hash->size - 1); + + for (bucket = pp = hash->index[index]; bucket; bucket = bucket->next) { + if (bucket->key == key + && (*hash->hash_cmp)(bucket->data, data)) { + int oldlen = hash->index[index]->len; + int newlen = oldlen - 1; + + if (bucket == pp) + hash->index[index] = bucket->next; + else + pp->next = bucket->next; + + if (hash->index[index]) + hash->index[index]->len = newlen; + else + hash->stats.empty++; + + hash_update_ssq(hash, oldlen, newlen); + + ret = bucket->data; + XFREE(MTYPE_HASH_BUCKET, bucket); + hash->count--; + break; + } + pp = bucket; + } + + frrtrace(3, frr_libfrr, hash_release, hash, data, ret); + + return ret; +} + +void hash_iterate(struct hash *hash, void (*func)(struct hash_bucket *, void *), + void *arg) +{ + unsigned int i; + struct hash_bucket *hb; + struct hash_bucket *hbnext; + + for (i = 0; i < hash->size; i++) + for (hb = hash->index[i]; hb; hb = hbnext) { + /* get pointer to next hash bucket here, in case (*func) + * decides to delete hb by calling hash_release + */ + hbnext = hb->next; + (*func)(hb, arg); + } +} + +void hash_walk(struct hash *hash, int (*func)(struct hash_bucket *, void *), + void *arg) +{ + unsigned int i; + struct hash_bucket *hb; + struct hash_bucket *hbnext; + int ret = HASHWALK_CONTINUE; + + for (i = 0; i < hash->size; i++) { + for (hb = hash->index[i]; hb; hb = hbnext) { + /* get pointer to next hash bucket here, in case (*func) + * decides to delete hb by calling hash_release + */ + hbnext = hb->next; + ret = (*func)(hb, arg); + if (ret == HASHWALK_ABORT) + return; + } + } +} + +void hash_clean(struct hash *hash, void (*free_func)(void *)) +{ + unsigned int i; + struct hash_bucket *hb; + struct hash_bucket *next; + + for (i = 0; i < hash->size; i++) { + for (hb = hash->index[i]; hb; hb = next) { + next = hb->next; + + if (free_func) + (*free_func)(hb->data); + + XFREE(MTYPE_HASH_BUCKET, hb); + hash->count--; + } + hash->index[i] = NULL; + } + + hash->stats.ssq = 0; + hash->stats.empty = hash->size; +} + +static void hash_to_list_iter(struct hash_bucket *hb, void *arg) +{ + struct list *list = arg; + + listnode_add(list, hb->data); +} + +struct list *hash_to_list(struct hash *hash) +{ + struct list *list = list_new(); + + hash_iterate(hash, hash_to_list_iter, list); + return list; +} + +void hash_free(struct hash *hash) +{ + frr_with_mutex (&_hashes_mtx) { + if (_hashes) { + listnode_delete(_hashes, hash); + if (_hashes->count == 0) { + list_delete(&_hashes); + } + } + } + + XFREE(MTYPE_HASH, hash->name); + + XFREE(MTYPE_HASH_INDEX, hash->index); + XFREE(MTYPE_HASH, hash); +} + + +/* CLI commands ------------------------------------------------------------ */ + +DEFUN_NOSH(show_hash_stats, + show_hash_stats_cmd, + "show debugging hashtable [statistics]", + SHOW_STR + DEBUG_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); + if (!_hashes) { + pthread_mutex_unlock(&_hashes_mtx); + ttable_del(tt); + vty_out(vty, "No hash tables in use.\n"); + return CMD_SUCCESS; + } + + for (ALL_LIST_ELEMENTS_RO(_hashes, ln, h)) { + if (!h->name) + continue; + + ssq = (long double)h->stats.ssq; + x2 = h->count * h->count; + 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_out(vty, "%s%s\n", header, frr_protonameinst); + vty_out(vty, "%s\n", underln); + + vty_out(vty, "# allocated: %d\n", _hashes->count); + vty_out(vty, "# named: %d\n\n", tt->nrows - 1); + + if (tt->nrows > 1) { + ttable_colseps(tt, 0, RIGHT, true, '|'); + char *table = ttable_dump(tt, "\n"); + vty_out(vty, "%s\n", table); + XFREE(MTYPE_TMP, table); + } else + vty_out(vty, "No named hash tables to display.\n"); + + ttable_del(tt); + + return CMD_SUCCESS; +} + +void hash_cmd_init(void) +{ + install_element(ENABLE_NODE, &show_hash_stats_cmd); +} |