lib/hash.c

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