]> git.proxmox.com Git - mirror_frr.git/commit - lib/hash.c
lib, vtysh: hashtable statistics
authorQuentin Young <qlyoung@cumulusnetworks.com>
Mon, 19 Jun 2017 14:22:26 +0000 (14:22 +0000)
committerQuentin Young <qlyoung@cumulusnetworks.com>
Sat, 1 Jul 2017 23:18:35 +0000 (19:18 -0400)
commit6f6f00107e72cc9c01a6604ff514a5b25d52106d
tree65f2663d0c7808a8d1921df8be185d6ba6627fa5
parent4db0cff16a1b16671384102f1876bebb7f481d89
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>
lib/command.c
lib/hash.c
lib/hash.h
vtysh/vtysh.c