// SPDX-License-Identifier: GPL-2.0-or-later /* Hash routine. * Copyright (C) 1998 Kunihiro Ishiguro */ #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; } void hash_clean_and_free(struct hash **hash, void (*free_func)(void *)) { if (!*hash) return; hash_clean(*hash, free_func); hash_free(*hash); *hash = NULL; } 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); }