lib/hash.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /* Hash routine.
   3  * Copyright (C) 1998 Kunihiro Ishiguro
   4  */
   5
   6 #include <zebra.h>
   7 #include <math.h>
   8
   9 #include "hash.h"
  10 #include "memory.h"
  11 #include "linklist.h"
  12 #include "termtable.h"
  13 #include "vty.h"
  14 #include "command.h"
  15 #include "libfrr.h"
  16 #include "frr_pthread.h"
  17 #include "libfrr_trace.h"
  18
  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");
  22
  23 static pthread_mutex_t _hashes_mtx = PTHREAD_MUTEX_INITIALIZER;
  24 static struct list *_hashes;
  25
  26 struct hash *hash_create_size(unsigned int size,
  27                               unsigned int (*hash_key)(const void *),
  28                               bool (*hash_cmp)(const void *, const void *),
  29                               const char *name)
  30 {
  31         struct hash *hash;
  32
  33         assert((size & (size - 1)) == 0);
  34         hash = XCALLOC(MTYPE_HASH, sizeof(struct hash));
  35         hash->index =
  36                 XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_bucket *) * size);
  37         hash->size = size;
  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
  44         frr_with_mutex (&_hashes_mtx) {
  45                 if (!_hashes)
  46                         _hashes = list_new();
  47
  48                 listnode_add(_hashes, hash);
  49         }
  50
  51         return hash;
  52 }
  53
  54 struct hash *hash_create(unsigned int (*hash_key)(const void *),
  55                          bool (*hash_cmp)(const void *, const void *),
  56                          const char *name)
  57 {
  58         return hash_create_size(HASH_INITIAL_SIZE, hash_key, hash_cmp, name);
  59 }
  60
  61 void *hash_alloc_intern(void *arg)
  62 {
  63         return arg;
  64 }
  65
  66 /*
  67  * ssq = ssq + (new^2 - old^2)
  68  *     = ssq + ((new + old) * (new - old))
  69  */
  70 #define hash_update_ssq(hz, old, new)                                          \
  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)
  80
  81 /* Expand hash if the chain length exceeds the threshold. */
  82 static void hash_expand(struct hash *hash)
  83 {
  84         unsigned int i, new_size;
  85         struct hash_bucket *hb, *hbnext, **new_index;
  86
  87         new_size = hash->size * 2;
  88
  89         if (hash->max_size && new_size > hash->max_size)
  90                 return;
  91
  92         new_index = XCALLOC(MTYPE_HASH_INDEX,
  93                             sizeof(struct hash_bucket *) * new_size);
  94
  95         hash->stats.empty = new_size;
  96
  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);
 100
 101                         hbnext = hb->next;
 102                         hb->next = new_index[h];
 103
 104                         int oldlen = hb->next ? hb->next->len : 0;
 105                         int newlen = oldlen + 1;
 106
 107                         if (newlen == 1)
 108                                 hash->stats.empty--;
 109                         else
 110                                 hb->next->len = 0;
 111
 112                         hb->len = newlen;
 113
 114                         hash_update_ssq(hash, oldlen, newlen);
 115
 116                         new_index[h] = hb;
 117                 }
 118
 119         /* Switch to new table */
 120         XFREE(MTYPE_HASH_INDEX, hash->index);
 121         hash->size = new_size;
 122         hash->index = new_index;
 123 }
 124
 125 void *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *))
 126 {
 127         frrtrace(2, frr_libfrr, hash_get, hash, data);
 128
 129         unsigned int key;
 130         unsigned int index;
 131         void *newdata;
 132         struct hash_bucket *bucket;
 133
 134         if (!alloc_func && !hash->count)
 135                 return NULL;
 136
 137         key = (*hash->hash_key)(data);
 138         index = key & (hash->size - 1);
 139
 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;
 144         }
 145
 146         if (alloc_func) {
 147                 newdata = (*alloc_func)(data);
 148                 if (newdata == NULL)
 149                         return NULL;
 150
 151                 if (HASH_THRESHOLD(hash->count + 1, hash->size)) {
 152                         hash_expand(hash);
 153                         index = key & (hash->size - 1);
 154                 }
 155
 156                 bucket = XCALLOC(MTYPE_HASH_BUCKET, sizeof(struct hash_bucket));
 157                 bucket->data = newdata;
 158                 bucket->key = key;
 159                 bucket->next = hash->index[index];
 160                 hash->index[index] = bucket;
 161                 hash->count++;
 162
 163                 frrtrace(3, frr_libfrr, hash_insert, hash, data, key);
 164
 165                 int oldlen = bucket->next ? bucket->next->len : 0;
 166                 int newlen = oldlen + 1;
 167
 168                 if (newlen == 1)
 169                         hash->stats.empty--;
 170                 else
 171                         bucket->next->len = 0;
 172
 173                 bucket->len = newlen;
 174
 175                 hash_update_ssq(hash, oldlen, newlen);
 176
 177                 return bucket->data;
 178         }
 179         return NULL;
 180 }
 181
 182 void *hash_lookup(struct hash *hash, void *data)
 183 {
 184         return hash_get(hash, data, NULL);
 185 }
 186
 187 unsigned int string_hash_make(const char *str)
 188 {
 189         unsigned int hash = 0;
 190
 191         while (*str)
 192                 hash = (hash * 33) ^ (unsigned int)*str++;
 193
 194         return hash;
 195 }
 196
 197 void *hash_release(struct hash *hash, void *data)
 198 {
 199         void *ret = NULL;
 200         unsigned int key;
 201         unsigned int index;
 202         struct hash_bucket *bucket;
 203         struct hash_bucket *pp;
 204
 205         key = (*hash->hash_key)(data);
 206         index = key & (hash->size - 1);
 207
 208         for (bucket = pp = hash->index[index]; bucket; bucket = bucket->next) {
 209                 if (bucket->key == key
 210                     && (*hash->hash_cmp)(bucket->data, data)) {
 211                         int oldlen = hash->index[index]->len;
 212                         int newlen = oldlen - 1;
 213
 214                         if (bucket == pp)
 215                                 hash->index[index] = bucket->next;
 216                         else
 217                                 pp->next = bucket->next;
 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
 226                         ret = bucket->data;
 227                         XFREE(MTYPE_HASH_BUCKET, bucket);
 228                         hash->count--;
 229                         break;
 230                 }
 231                 pp = bucket;
 232         }
 233
 234         frrtrace(3, frr_libfrr, hash_release, hash, data, ret);
 235
 236         return ret;
 237 }
 238
 239 void hash_iterate(struct hash *hash, void (*func)(struct hash_bucket *, void *),
 240                   void *arg)
 241 {
 242         unsigned int i;
 243         struct hash_bucket *hb;
 244         struct hash_bucket *hbnext;
 245
 246         for (i = 0; i < hash->size; i++)
 247                 for (hb = hash->index[i]; hb; hb = hbnext) {
 248                         /* get pointer to next hash bucket here, in case (*func)
 249                          * decides to delete hb by calling hash_release
 250                          */
 251                         hbnext = hb->next;
 252                         (*func)(hb, arg);
 253                 }
 254 }
 255
 256 void hash_walk(struct hash *hash, int (*func)(struct hash_bucket *, void *),
 257                void *arg)
 258 {
 259         unsigned int i;
 260         struct hash_bucket *hb;
 261         struct hash_bucket *hbnext;
 262         int ret = HASHWALK_CONTINUE;
 263
 264         for (i = 0; i < hash->size; i++) {
 265                 for (hb = hash->index[i]; hb; hb = hbnext) {
 266                         /* get pointer to next hash bucket here, in case (*func)
 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                 }
 274         }
 275 }
 276
 277 void hash_clean(struct hash *hash, void (*free_func)(void *))
 278 {
 279         unsigned int i;
 280         struct hash_bucket *hb;
 281         struct hash_bucket *next;
 282
 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);
 289
 290                         XFREE(MTYPE_HASH_BUCKET, hb);
 291                         hash->count--;
 292                 }
 293                 hash->index[i] = NULL;
 294         }
 295
 296         hash->stats.ssq = 0;
 297         hash->stats.empty = hash->size;
 298 }
 299
 300 static void hash_to_list_iter(struct hash_bucket *hb, void *arg)
 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
 315 void hash_free(struct hash *hash)
 316 {
 317         frr_with_mutex (&_hashes_mtx) {
 318                 if (_hashes) {
 319                         listnode_delete(_hashes, hash);
 320                         if (_hashes->count == 0) {
 321                                 list_delete(&_hashes);
 322                         }
 323                 }
 324         }
 325
 326         XFREE(MTYPE_HASH, hash->name);
 327
 328         XFREE(MTYPE_HASH_INDEX, hash->index);
 329         XFREE(MTYPE_HASH, hash);
 330 }
 331
 332
 333 /* CLI commands ------------------------------------------------------------ */
 334
 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")
 342 {
 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          *
 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.
 365          *
 366          * - Full load factor: this is the number of elements in the table
 367          *   divided by the number of buckets that have some elements in them.
 368          *
 369          * - Std. Dev.: This is the standard deviation calculated from the
 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.
 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);
 393                 ttable_del(tt);
 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;
 403                 x2 = h->count * h->count;
 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;
 444 }
 445
 446 void hash_cmd_init(void)
 447 {
 448         install_element(ENABLE_NODE, &show_hash_stats_cmd);
 449 }