[mirror_frr.git] / lib / hash.c

// 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;
}

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);
}
Commit	Line	Data
acddc0ed	1	// SPDX-License-Identifier: GPL-2.0-or-later
718e3744	2	/* Hash routine.
718e3744	3	* Copyright (C) 1998 Kunihiro Ishiguro
718e3744	4	*/
	5
	6	#include <zebra.h>
4db0cff1	7	#include <math.h>
718e3744	8
	9	#include "hash.h"
	10	#include "memory.h"
4db0cff1 QY	11	#include "linklist.h"
	12	#include "termtable.h"
	13	#include "vty.h"
	14	#include "command.h"
6f6f0010	15	#include "libfrr.h"
00dffa8c	16	#include "frr_pthread.h"
912d45a1	17	#include "libfrr_trace.h"
718e3744	18
bf8d3d6a DL	19	DEFINE_MTYPE_STATIC(LIB, HASH, "Hash");
	20	DEFINE_MTYPE_STATIC(LIB, HASH_BUCKET, "Hash Bucket");
	21	DEFINE_MTYPE_STATIC(LIB, HASH_INDEX, "Hash Index");
4a1ab8e4	22
c17faa4b	23	static pthread_mutex_t _hashes_mtx = PTHREAD_MUTEX_INITIALIZER;
4db0cff1 QY	24	static struct list *_hashes;
4db0cff1 QY	25
d62a17ae	26	struct hash *hash_create_size(unsigned int size,
d8b87afe	27	unsigned int (hash_key)(const void ),
74df8d6d	28	bool (hash_cmp)(const void , const void *),
d62a17ae	29	const char *name)
718e3744	30	{
d62a17ae	31	struct hash *hash;
	32
	33	assert((size & (size - 1)) == 0);
	34	hash = XCALLOC(MTYPE_HASH, sizeof(struct hash));
	35	hash->index =
e3b78da8	36	XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_bucket ) size);
d62a17ae	37	hash->size = size;
d62a17ae	38	hash->hash_key = hash_key;
	39	hash->hash_cmp = hash_cmp;
	40	hash->count = 0;
	41	hash->name = name ? XSTRDUP(MTYPE_HASH, name) : NULL;
	42	hash->stats.empty = hash->size;
	43
cb1991af	44	frr_with_mutex (&_hashes_mtx) {
d62a17ae	45	if (!_hashes)
	46	_hashes = list_new();
	47
	48	listnode_add(_hashes, hash);
	49	}
d62a17ae	50
d62a17ae	51	return hash;
718e3744	52	}
718e3744	53
d8b87afe	54	struct hash hash_create(unsigned int (hash_key)(const void *),
74df8d6d	55	bool (hash_cmp)(const void , const void *),
d62a17ae	56	const char *name)
718e3744	57	{
d62a17ae	58	return hash_create_size(HASH_INITIAL_SIZE, hash_key, hash_cmp, name);
718e3744	59	}
718e3744	60
d62a17ae	61	void hash_alloc_intern(void arg)
718e3744	62	{
d62a17ae	63	return arg;
718e3744	64	}
718e3744	65
e6464fdc QY	66	/*
	67	* ssq = ssq + (new^2 - old^2)
	68	* = ssq + ((new + old) * (new - old))
	69	*/
d62a17ae	70	#define hash_update_ssq(hz, old, new) \
e6464fdc QY	71	do { \
	72	int _adjust = (new + old) * (new - old); \
	73	if (_adjust < 0) \
	74	atomic_fetch_sub_explicit(&hz->stats.ssq, -_adjust, \
	75	memory_order_relaxed); \
	76	else \
	77	atomic_fetch_add_explicit(&hz->stats.ssq, _adjust, \
	78	memory_order_relaxed); \
	79	} while (0)
6f6f0010	80
97c84db0	81	/* Expand hash if the chain length exceeds the threshold. */
d62a17ae	82	static void hash_expand(struct hash *hash)
97c84db0	83	{
8b2a6222	84	unsigned int i, new_size;
e3b78da8	85	struct hash_bucket hb, hbnext, **new_index;
97c84db0	86
d62a17ae	87	new_size = hash->size * 2;
40520c36 DW	88
	89	if (hash->max_size && new_size > hash->max_size)
	90	return;
	91
d62a17ae	92	new_index = XCALLOC(MTYPE_HASH_INDEX,
e3b78da8	93	sizeof(struct hash_bucket ) new_size);
97c84db0	94
d62a17ae	95	hash->stats.empty = new_size;
6f6f0010	96
d62a17ae	97	for (i = 0; i < hash->size; i++)
	98	for (hb = hash->index[i]; hb; hb = hbnext) {
	99	unsigned int h = hb->key & (new_size - 1);
97c84db0	100
d62a17ae	101	hbnext = hb->next;
d62a17ae	102	hb->next = new_index[h];
6f6f0010	103
d62a17ae	104	int oldlen = hb->next ? hb->next->len : 0;
d62a17ae	105	int newlen = oldlen + 1;
6f6f0010	106
d62a17ae	107	if (newlen == 1)
	108	hash->stats.empty--;
	109	else
	110	hb->next->len = 0;
6f6f0010	111
d62a17ae	112	hb->len = newlen;
6f6f0010	113
d62a17ae	114	hash_update_ssq(hash, oldlen, newlen);
6f6f0010	115
d62a17ae	116	new_index[h] = hb;
d62a17ae	117	}
97c84db0	118
d62a17ae	119	/* Switch to new table */
	120	XFREE(MTYPE_HASH_INDEX, hash->index);
	121	hash->size = new_size;
	122	hash->index = new_index;
97c84db0 SH	123	}
97c84db0 SH	124
d62a17ae	125	void hash_get(struct hash hash, void data, void (alloc_func)(void ))
718e3744	126	{
c7bb4f00	127	frrtrace(2, frr_libfrr, hash_get, hash, data);
abf96a87	128
d62a17ae	129	unsigned int key;
	130	unsigned int index;
	131	void *newdata;
e3b78da8	132	struct hash_bucket *bucket;
d62a17ae	133
efb149d9 DS	134	if (!alloc_func && !hash->count)
	135	return NULL;
	136
d62a17ae	137	key = (*hash->hash_key)(data);
d62a17ae	138	index = key & (hash->size - 1);
d62a17ae	139
e3b78da8 TB	140	for (bucket = hash->index[index]; bucket != NULL;
	141	bucket = bucket->next) {
	142	if (bucket->key == key && (*hash->hash_cmp)(bucket->data, data))
	143	return bucket->data;
97c84db0 SH	144	}
97c84db0 SH	145
d62a17ae	146	if (alloc_func) {
	147	newdata = (*alloc_func)(data);
	148	if (newdata == NULL)
	149	return NULL;
6f6f0010	150
bed7ad83	151	if (HASH_THRESHOLD(hash->count + 1, hash->size)) {
d62a17ae	152	hash_expand(hash);
	153	index = key & (hash->size - 1);
	154	}
6f6f0010	155
1ac88792	156	bucket = XCALLOC(MTYPE_HASH_BUCKET, sizeof(struct hash_bucket));
e3b78da8 TB	157	bucket->data = newdata;
	158	bucket->key = key;
	159	bucket->next = hash->index[index];
	160	hash->index[index] = bucket;
d62a17ae	161	hash->count++;
6f6f0010	162
c7bb4f00	163	frrtrace(3, frr_libfrr, hash_insert, hash, data, key);
67a485d1	164
e3b78da8	165	int oldlen = bucket->next ? bucket->next->len : 0;
d62a17ae	166	int newlen = oldlen + 1;
6f6f0010	167
d62a17ae	168	if (newlen == 1)
	169	hash->stats.empty--;
	170	else
e3b78da8	171	bucket->next->len = 0;
6f6f0010	172
e3b78da8	173	bucket->len = newlen;
d62a17ae	174
	175	hash_update_ssq(hash, oldlen, newlen);
	176
e3b78da8	177	return bucket->data;
d62a17ae	178	}
d62a17ae	179	return NULL;
718e3744	180	}
718e3744	181
d62a17ae	182	void hash_lookup(struct hash hash, void *data)
718e3744	183	{
d62a17ae	184	return hash_get(hash, data, NULL);
718e3744	185	}
718e3744	186
d62a17ae	187	unsigned int string_hash_make(const char *str)
6392aa83	188	{
d62a17ae	189	unsigned int hash = 0;
6392aa83	190
d62a17ae	191	while (*str)
d62a17ae	192	hash = (hash * 33) ^ (unsigned int)*str++;
6392aa83	193
d62a17ae	194	return hash;
6392aa83 SH	195	}
6392aa83 SH	196
d62a17ae	197	void hash_release(struct hash hash, void *data)
718e3744	198	{
abf96a87	199	void *ret = NULL;
d62a17ae	200	unsigned int key;
d62a17ae	201	unsigned int index;
e3b78da8 TB	202	struct hash_bucket *bucket;
e3b78da8 TB	203	struct hash_bucket *pp;
d62a17ae	204
	205	key = (*hash->hash_key)(data);
	206	index = key & (hash->size - 1);
	207
e3b78da8 TB	208	for (bucket = pp = hash->index[index]; bucket; bucket = bucket->next) {
	209	if (bucket->key == key
	210	&& (*hash->hash_cmp)(bucket->data, data)) {
d62a17ae	211	int oldlen = hash->index[index]->len;
	212	int newlen = oldlen - 1;
	213
e3b78da8 TB	214	if (bucket == pp)
e3b78da8 TB	215	hash->index[index] = bucket->next;
d62a17ae	216	else
e3b78da8	217	pp->next = bucket->next;
d62a17ae	218
	219	if (hash->index[index])
	220	hash->index[index]->len = newlen;
	221	else
	222	hash->stats.empty++;
	223
	224	hash_update_ssq(hash, oldlen, newlen);
	225
e3b78da8	226	ret = bucket->data;
1ac88792	227	XFREE(MTYPE_HASH_BUCKET, bucket);
d62a17ae	228	hash->count--;
abf96a87	229	break;
d62a17ae	230	}
e3b78da8	231	pp = bucket;
718e3744	232	}
abf96a87	233
c7bb4f00	234	frrtrace(3, frr_libfrr, hash_release, hash, data, ret);
abf96a87 QY	235
abf96a87 QY	236	return ret;
718e3744	237	}
718e3744	238
e3b78da8	239	void hash_iterate(struct hash hash, void (func)(struct hash_bucket , void ),
d62a17ae	240	void *arg)
718e3744	241	{
d62a17ae	242	unsigned int i;
e3b78da8 TB	243	struct hash_bucket *hb;
e3b78da8 TB	244	struct hash_bucket *hbnext;
d62a17ae	245
df66eb2e	246	for (i = 0; i < hash->size; i++)
d62a17ae	247	for (hb = hash->index[i]; hb; hb = hbnext) {
e3b78da8	248	/* get pointer to next hash bucket here, in case (*func)
d62a17ae	249	* decides to delete hb by calling hash_release
	250	*/
	251	hbnext = hb->next;
	252	(*func)(hb, arg);
	253	}
718e3744	254	}
718e3744	255
e3b78da8	256	void hash_walk(struct hash hash, int (func)(struct hash_bucket , void ),
d62a17ae	257	void *arg)
3f9c7369	258	{
d62a17ae	259	unsigned int i;
e3b78da8 TB	260	struct hash_bucket *hb;
e3b78da8 TB	261	struct hash_bucket *hbnext;
d62a17ae	262	int ret = HASHWALK_CONTINUE;
	263
	264	for (i = 0; i < hash->size; i++) {
	265	for (hb = hash->index[i]; hb; hb = hbnext) {
e3b78da8	266	/* get pointer to next hash bucket here, in case (*func)
d62a17ae	267	* decides to delete hb by calling hash_release
	268	*/
	269	hbnext = hb->next;
	270	ret = (*func)(hb, arg);
	271	if (ret == HASHWALK_ABORT)
	272	return;
	273	}
3f9c7369	274	}
3f9c7369 DS	275	}
3f9c7369 DS	276
d62a17ae	277	void hash_clean(struct hash hash, void (free_func)(void *))
718e3744	278	{
d62a17ae	279	unsigned int i;
e3b78da8 TB	280	struct hash_bucket *hb;
e3b78da8 TB	281	struct hash_bucket *next;
718e3744	282
d62a17ae	283	for (i = 0; i < hash->size; i++) {
	284	for (hb = hash->index[i]; hb; hb = next) {
	285	next = hb->next;
	286
	287	if (free_func)
	288	(*free_func)(hb->data);
718e3744	289
1ac88792	290	XFREE(MTYPE_HASH_BUCKET, hb);
d62a17ae	291	hash->count--;
	292	}
	293	hash->index[i] = NULL;
718e3744	294	}
6f6f0010	295
d62a17ae	296	hash->stats.ssq = 0;
d62a17ae	297	hash->stats.empty = hash->size;
718e3744	298	}
718e3744	299
e3b78da8	300	static void hash_to_list_iter(struct hash_bucket hb, void arg)
91f10370 QY	301	{
	302	struct list *list = arg;
	303
	304	listnode_add(list, hb->data);
	305	}
	306
	307	struct list hash_to_list(struct hash hash)
	308	{
	309	struct list *list = list_new();
	310
	311	hash_iterate(hash, hash_to_list_iter, list);
	312	return list;
	313	}
	314
d62a17ae	315	void hash_free(struct hash *hash)
718e3744	316	{
cb1991af	317	frr_with_mutex (&_hashes_mtx) {
d62a17ae	318	if (_hashes) {
	319	listnode_delete(_hashes, hash);
	320	if (_hashes->count == 0) {
6a154c88	321	list_delete(&_hashes);
d62a17ae	322	}
	323	}
	324	}
d62a17ae	325
0a22ddfb	326	XFREE(MTYPE_HASH, hash->name);
d62a17ae	327
	328	XFREE(MTYPE_HASH_INDEX, hash->index);
	329	XFREE(MTYPE_HASH, hash);
4db0cff1 QY	330	}
4db0cff1 QY	331
6f6f0010 QY	332
6f6f0010 QY	333	/* CLI commands ------------------------------------------------------------ */
4db0cff1	334
40818cec DL	335	DEFUN_NOSH(show_hash_stats,
	336	show_hash_stats_cmd,
	337	"show debugging hashtable [statistics]",
	338	SHOW_STR
	339	DEBUG_STR
	340	"Statistics about hash tables\n"
	341	"Statistics about hash tables\n")
4db0cff1	342	{
d62a17ae	343	struct hash *h;
	344	struct listnode *ln;
	345	struct ttable *tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]);
	346
	347	ttable_add_row(tt, "Hash table\|Buckets\|Entries\|Empty\|LF\|SD\|FLF\|SD");
	348	tt->style.cell.lpad = 2;
	349	tt->style.cell.rpad = 1;
	350	tt->style.corner = '+';
	351	ttable_restyle(tt);
	352	ttable_rowseps(tt, 0, BOTTOM, true, '-');
	353
	354	/* Summary statistics calculated are:
	355	*
c7d3895e CF	356	* - Load factor: This is the number of elements in the table divided
	357	* by the number of buckets. Since this hash table implementation
	358	* uses chaining, this value can be greater than 1.
	359	* This number provides information on how 'full' the table is, but
	360	* does not provide information on how evenly distributed the
	361	* elements are.
	362	* Notably, a load factor >= 1 does not imply that every bucket has
	363	* an element; with a pathological hash function, all elements could
	364	* be in a single bucket.
d62a17ae	365	*
d62a17ae	366	* - Full load factor: this is the number of elements in the table
c7d3895e	367	* divided by the number of buckets that have some elements in them.
d62a17ae	368	*
d62a17ae	369	* - Std. Dev.: This is the standard deviation calculated from the
c7d3895e CF	370	* relevant load factor. If the load factor is the mean of number of
	371	* elements per bucket, the standard deviation measures how much any
	372	* particular bucket is likely to deviate from the mean.
	373	* As a rule of thumb this number should be less than 2, and ideally
	374	* <= 1 for optimal performance. A number larger than 3 generally
	375	* indicates a poor hash function.
d62a17ae	376	*/
	377
	378	double lf; // load factor
	379	double flf; // full load factor
	380	double var; // overall variance
	381	double fvar; // full variance
	382	double stdv; // overall stddev
	383	double fstdv; // full stddev
	384
	385	long double x2; // h->count ^ 2
	386	long double ldc; // (long double) h->count
	387	long double full; // h->size - h->stats.empty
	388	long double ssq; // ssq casted to long double
	389
	390	pthread_mutex_lock(&_hashes_mtx);
	391	if (!_hashes) {
	392	pthread_mutex_unlock(&_hashes_mtx);
44f12f20	393	ttable_del(tt);
d62a17ae	394	vty_out(vty, "No hash tables in use.\n");
	395	return CMD_SUCCESS;
	396	}
	397
	398	for (ALL_LIST_ELEMENTS_RO(_hashes, ln, h)) {
	399	if (!h->name)
	400	continue;
	401
	402	ssq = (long double)h->stats.ssq;
61b9e9d6	403	x2 = h->count * h->count;
d62a17ae	404	ldc = (long double)h->count;
	405	full = h->size - h->stats.empty;
	406	lf = h->count / (double)h->size;
	407	flf = full ? h->count / (double)(full) : 0;
	408	var = ldc ? (1.0 / ldc) * (ssq - x2 / ldc) : 0;
	409	fvar = full ? (1.0 / full) * (ssq - x2 / full) : 0;
	410	var = (var < .0001) ? 0 : var;
	411	fvar = (fvar < .0001) ? 0 : fvar;
	412	stdv = sqrt(var);
	413	fstdv = sqrt(fvar);
	414
	415	ttable_add_row(tt, "%s\|%d\|%ld\|%.0f%%\|%.2lf\|%.2lf\|%.2lf\|%.2lf",
	416	h->name, h->size, h->count,
	417	(h->stats.empty / (double)h->size) * 100, lf,
	418	stdv, flf, fstdv);
	419	}
	420	pthread_mutex_unlock(&_hashes_mtx);
	421
	422	/* display header */
	423	char header[] = "Showing hash table statistics for ";
	424	char underln[sizeof(header) + strlen(frr_protonameinst)];
	425	memset(underln, '-', sizeof(underln));
	426	underln[sizeof(underln) - 1] = '\0';
	427	vty_out(vty, "%s%s\n", header, frr_protonameinst);
	428	vty_out(vty, "%s\n", underln);
	429
	430	vty_out(vty, "# allocated: %d\n", _hashes->count);
	431	vty_out(vty, "# named: %d\n\n", tt->nrows - 1);
	432
	433	if (tt->nrows > 1) {
	434	ttable_colseps(tt, 0, RIGHT, true, '\|');
	435	char *table = ttable_dump(tt, "\n");
	436	vty_out(vty, "%s\n", table);
	437	XFREE(MTYPE_TMP, table);
	438	} else
	439	vty_out(vty, "No named hash tables to display.\n");
	440
	441	ttable_del(tt);
	442
	443	return CMD_SUCCESS;
4db0cff1 QY	444	}
4db0cff1 QY	445
4d762f26	446	void hash_cmd_init(void)
4db0cff1	447	{
d62a17ae	448	install_element(ENABLE_NODE, &show_hash_stats_cmd);
4db0cff1	449	}