lib, vtysh: hashtable statistics

Adds the ability to name hash tables, and a new cli command that will
show various summary statistics for named hash tables.

Statistics computed are
  - load factor
  - full load factor (see comments)
  - stddev of full load factor

Standard deviation is computed by storing the sum of squares of bucket
lengths. This is somewhat susceptible to overflow. On platforms where a
double is 32 bits, placing 65535 or more elements into a hash table
opens up the potential for overflow, depending on how they are arranged
in buckets (which depends on the hash function). For example, placing
65535 elements into one hash bucket would cause ssq overflow, but
distributing 40000000 elements evenly among 400000 buckets (100 elements
per bucket) would not.

These cases are extremely degenerate, so the vague possibility of
overflow in an informational command is deemed an acceptable tradeoff
for constant time calculation of variance without locks or compromising
efficiency of actual table operations.

Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>

1 files changed, 20 insertions, 6 deletions

diff --git a/lib/hash.h b/lib/hash.h
index 15afc249ab..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. */
@@ -65,14 +78,18 @@ struct hash
   /* Backet alloc. */
   unsigned long count;
 
+  struct hashstats stats;
+
   /* hash name */
-  const char *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 *);
@@ -90,9 +107,6 @@ extern void hash_free (struct hash *);
 
 extern unsigned int string_hash_make (const char *);
 
-extern void hash_stats (struct hash *, double *, double *, int *, int *, int *, double *);
 extern void hash_cmd_init (void);
-extern void hash_register (struct hash *, const char *);
-extern void hash_unregister (struct hash *);
 
 #endif /* _ZEBRA_HASH_H */