src/vppinfra/hash.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001-2005 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #include <vppinfra/hash.h>
  39 #include <vppinfra/error.h>
  40 #include <vppinfra/mem.h>
  41 #include <vppinfra/byte_order.h>        /* for clib_arch_is_big_endian */
  42
  43 always_inline void
  44 zero_pair (hash_t * h, hash_pair_t * p)
  45 {
  46   clib_memset (p, 0, hash_pair_bytes (h));
  47 }
  48
  49 always_inline void
  50 init_pair (hash_t * h, hash_pair_t * p)
  51 {
  52   clib_memset (p->value, ~0, hash_value_bytes (h));
  53 }
  54
  55 always_inline hash_pair_union_t *
  56 get_pair (void *v, uword i)
  57 {
  58   hash_t *h = hash_header (v);
  59   hash_pair_t *p;
  60   ASSERT (i < vec_len (v));
  61   p = v;
  62   p += i << h->log2_pair_size;
  63   return (hash_pair_union_t *) p;
  64 }
  65
  66 always_inline void
  67 set_is_user (void *v, uword i, uword is_user)
  68 {
  69   hash_t *h = hash_header (v);
  70   uword i0 = i / BITS (h->is_user[0]);
  71   uword i1 = (uword) 1 << (i % BITS (h->is_user[0]));
  72   if (is_user)
  73     h->is_user[i0] |= i1;
  74   else
  75     h->is_user[i0] &= ~i1;
  76 }
  77
  78 static u8 *hash_format_pair_default (u8 * s, va_list * args);
  79
  80 #if uword_bits == 64
  81
  82 static inline u64
  83 zap64 (u64 x, word n)
  84 {
  85 #define _(n) (((u64) 1 << (u64) (8*(n))) - (u64) 1)
  86   static u64 masks_little_endian[] = {
  87     0, _(1), _(2), _(3), _(4), _(5), _(6), _(7),
  88   };
  89   static u64 masks_big_endian[] = {
  90     0, ~_(7), ~_(6), ~_(5), ~_(4), ~_(3), ~_(2), ~_(1),
  91   };
  92 #undef _
  93   if (clib_arch_is_big_endian)
  94     return x & masks_big_endian[n];
  95   else
  96     return x & masks_little_endian[n];
  97 }
  98
  99 /**
 100  * make address-sanitizer skip this:
 101  * clib_mem_unaligned + zap64 casts its input as u64, computes a mask
 102  * according to the input length, and returns the casted maked value.
 103  * Therefore all the 8 Bytes of the u64 are systematically read, which
 104  * rightfully causes address-sanitizer to raise an error on smaller inputs.
 105  *
 106  * However the invalid Bytes are discarded within zap64(), which is why
 107  * this can be silenced safely.
 108  *
 109  * The above is true *unless* the extra bytes cross a page boundary
 110  * into unmapped or no-access space, hence the boundary crossing check.
 111  */
 112 static inline u64
 113 hash_memory64 (void *p, word n_bytes, u64 state)
 114 {
 115   u64 *q = p;
 116   u64 a, b, c, n;
 117   int page_boundary_crossing;
 118   u64 start_addr, end_addr;
 119   union
 120   {
 121     u8 as_u8[8];
 122     u64 as_u64;
 123   } tmp;
 124
 125   /*
 126    * If the request crosses a 4k boundary, it's not OK to assume
 127    * that the zap64 game is safe. 4k is the minimum known page size.
 128    */
 129   start_addr = (u64) p;
 130   end_addr = start_addr + n_bytes + 7;
 131   page_boundary_crossing = (start_addr >> 12) != (end_addr >> 12);
 132
 133   a = b = 0x9e3779b97f4a7c13LL;
 134   c = state;
 135   n = n_bytes;
 136
 137   while (n >= 3 * sizeof (u64))
 138     {
 139       a += clib_mem_unaligned (q + 0, u64);
 140       b += clib_mem_unaligned (q + 1, u64);
 141       c += clib_mem_unaligned (q + 2, u64);
 142       hash_mix64 (a, b, c);
 143       n -= 3 * sizeof (u64);
 144       q += 3;
 145     }
 146
 147   c += n_bytes;
 148   switch (n / sizeof (u64))
 149     {
 150     case 2:
 151       a += clib_mem_unaligned (q + 0, u64);
 152       b += clib_mem_unaligned (q + 1, u64);
 153       if (n % sizeof (u64))
 154         {
 155           if (PREDICT_TRUE (page_boundary_crossing == 0))
 156             {
 157               CLIB_MEM_OVERFLOW_PUSH (q + 2, sizeof (u64));
 158               c += zap64 (clib_mem_unaligned (q + 2, u64), n % sizeof (u64))
 159                    << 8;
 160               CLIB_MEM_OVERFLOW_POP ();
 161             }
 162           else
 163             {
 164               clib_memcpy_fast (tmp.as_u8, q + 2, n % sizeof (u64));
 165               c += zap64 (tmp.as_u64, n % sizeof (u64)) << 8;
 166             }
 167         }
 168       break;
 169
 170     case 1:
 171       a += clib_mem_unaligned (q + 0, u64);
 172       if (n % sizeof (u64))
 173         {
 174           if (PREDICT_TRUE (page_boundary_crossing == 0))
 175             {
 176               CLIB_MEM_OVERFLOW_PUSH (q + 1, sizeof (u64));
 177               b += zap64 (clib_mem_unaligned (q + 1, u64), n % sizeof (u64));
 178               CLIB_MEM_OVERFLOW_POP ();
 179             }
 180           else
 181             {
 182               clib_memcpy_fast (tmp.as_u8, q + 1, n % sizeof (u64));
 183               b += zap64 (tmp.as_u64, n % sizeof (u64));
 184             }
 185         }
 186       break;
 187
 188     case 0:
 189       if (n % sizeof (u64))
 190         {
 191           if (PREDICT_TRUE (page_boundary_crossing == 0))
 192             {
 193               CLIB_MEM_OVERFLOW_PUSH (q + 0, sizeof (u64));
 194               a += zap64 (clib_mem_unaligned (q + 0, u64), n % sizeof (u64));
 195               CLIB_MEM_OVERFLOW_POP ();
 196             }
 197           else
 198             {
 199               clib_memcpy_fast (tmp.as_u8, q, n % sizeof (u64));
 200               a += zap64 (tmp.as_u64, n % sizeof (u64));
 201             }
 202         }
 203       break;
 204     }
 205
 206   hash_mix64 (a, b, c);
 207
 208   return c;
 209 }
 210
 211 #else /* if uword_bits == 64 */
 212
 213 static inline u32
 214 zap32 (u32 x, word n)
 215 {
 216 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
 217   static u32 masks_little_endian[] = {
 218     0, _(1), _(2), _(3),
 219   };
 220   static u32 masks_big_endian[] = {
 221     0, ~_(3), ~_(2), ~_(1),
 222   };
 223 #undef _
 224   if (clib_arch_is_big_endian)
 225     return x & masks_big_endian[n];
 226   else
 227     return x & masks_little_endian[n];
 228 }
 229
 230 static inline u32
 231 hash_memory32 (void *p, word n_bytes, u32 state)
 232 {
 233   u32 *q = p;
 234   u32 a, b, c, n;
 235
 236   a = b = 0x9e3779b9;
 237   c = state;
 238   n = n_bytes;
 239
 240   while (n >= 3 * sizeof (u32))
 241     {
 242       a += clib_mem_unaligned (q + 0, u32);
 243       b += clib_mem_unaligned (q + 1, u32);
 244       c += clib_mem_unaligned (q + 2, u32);
 245       hash_mix32 (a, b, c);
 246       n -= 3 * sizeof (u32);
 247       q += 3;
 248     }
 249
 250   c += n_bytes;
 251   switch (n / sizeof (u32))
 252     {
 253     case 2:
 254       a += clib_mem_unaligned (q + 0, u32);
 255       b += clib_mem_unaligned (q + 1, u32);
 256       if (n % sizeof (u32))
 257         c += zap32 (clib_mem_unaligned (q + 2, u32), n % sizeof (u32)) << 8;
 258       break;
 259
 260     case 1:
 261       a += clib_mem_unaligned (q + 0, u32);
 262       if (n % sizeof (u32))
 263         b += zap32 (clib_mem_unaligned (q + 1, u32), n % sizeof (u32));
 264       break;
 265
 266     case 0:
 267       if (n % sizeof (u32))
 268         a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32));
 269       break;
 270     }
 271
 272   hash_mix32 (a, b, c);
 273
 274   return c;
 275 }
 276 #endif
 277
 278 __clib_export uword
 279 hash_memory (void *p, word n_bytes, uword state)
 280 {
 281   uword *q = p;
 282
 283 #if uword_bits == 64
 284   return hash_memory64 (q, n_bytes, state);
 285 #else
 286   return hash_memory32 (q, n_bytes, state);
 287 #endif
 288 }
 289
 290 #if uword_bits == 64
 291 always_inline uword
 292 hash_uword (uword x)
 293 {
 294   u64 a, b, c;
 295
 296   a = b = 0x9e3779b97f4a7c13LL;
 297   c = 0;
 298   a += x;
 299   hash_mix64 (a, b, c);
 300   return c;
 301 }
 302 #else
 303 always_inline uword
 304 hash_uword (uword x)
 305 {
 306   u32 a, b, c;
 307
 308   a = b = 0x9e3779b9;
 309   c = 0;
 310   a += x;
 311   hash_mix32 (a, b, c);
 312   return c;
 313 }
 314 #endif
 315
 316 /* Call sum function.  Hash code will be sum function value
 317    modulo the prime length of the hash table. */
 318 always_inline uword
 319 key_sum (hash_t * h, uword key)
 320 {
 321   uword sum;
 322   switch (pointer_to_uword ((void *) h->key_sum))
 323     {
 324     case KEY_FUNC_NONE:
 325       sum = hash_uword (key);
 326       break;
 327
 328     case KEY_FUNC_POINTER_UWORD:
 329       sum = hash_uword (*uword_to_pointer (key, uword *));
 330       break;
 331
 332     case KEY_FUNC_POINTER_U32:
 333       sum = hash_uword (*uword_to_pointer (key, u32 *));
 334       break;
 335
 336     case KEY_FUNC_STRING:
 337       sum = string_key_sum (h, key);
 338       break;
 339
 340     case KEY_FUNC_MEM:
 341       sum = mem_key_sum (h, key);
 342       break;
 343
 344     default:
 345       sum = h->key_sum (h, key);
 346       break;
 347     }
 348
 349   return sum;
 350 }
 351
 352 always_inline uword
 353 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
 354 {
 355   switch (pointer_to_uword ((void *) h->key_equal))
 356     {
 357     case KEY_FUNC_NONE:
 358       break;
 359
 360     case KEY_FUNC_POINTER_UWORD:
 361       e =
 362         *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
 363                                                                 uword *);
 364       break;
 365
 366     case KEY_FUNC_POINTER_U32:
 367       e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
 368       break;
 369
 370     case KEY_FUNC_STRING:
 371       e = string_key_equal (h, key1, key2);
 372       break;
 373
 374     case KEY_FUNC_MEM:
 375       e = mem_key_equal (h, key1, key2);
 376       break;
 377
 378     default:
 379       e = h->key_equal (h, key1, key2);
 380       break;
 381     }
 382   return e;
 383 }
 384
 385 /* Compares two keys: returns 1 if equal, 0 if not. */
 386 always_inline uword
 387 key_equal (hash_t * h, uword key1, uword key2)
 388 {
 389   uword e = key1 == key2;
 390   if (CLIB_DEBUG > 0 && key1 == key2)
 391     ASSERT (key_equal1 (h, key1, key2, e));
 392   if (!e)
 393     e = key_equal1 (h, key1, key2, e);
 394   return e;
 395 }
 396
 397 static hash_pair_union_t *
 398 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
 399 {
 400   hash_t *h = hash_header (v);
 401   hash_pair_t *p0, *p1;
 402
 403   p0 = p1 = pi->pairs;
 404   if (h->log2_pair_size > 0)
 405     p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
 406   else
 407     p1 += vec_len (p0);
 408
 409   while (p0 < p1)
 410     {
 411       if (key_equal (h, p0->key, key))
 412         return (hash_pair_union_t *) p0;
 413       p0 = hash_forward1 (h, p0);
 414     }
 415
 416   return (hash_pair_union_t *) 0;
 417 }
 418
 419 static hash_pair_union_t *
 420 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
 421 {
 422   hash_t *h = hash_header (v);
 423   hash_pair_t *q;
 424   hash_pair_indirect_t *pi = &p->indirect;
 425   uword log2_bytes = 0;
 426
 427   if (h->log2_pair_size == 0)
 428     q = vec_new (hash_pair_t, 2);
 429   else
 430     {
 431       log2_bytes = 1 + hash_pair_log2_bytes (h);
 432       q = clib_mem_alloc (1ULL << log2_bytes);
 433     }
 434   clib_memcpy_fast (q, &p->direct, hash_pair_bytes (h));
 435
 436   pi->pairs = q;
 437   if (h->log2_pair_size > 0)
 438     indirect_pair_set (pi, log2_bytes, 2);
 439
 440   set_is_user (v, i, 0);
 441
 442   /* First element is used by existing pair, second will be used by caller. */
 443   q = hash_forward1 (h, q);
 444   q->key = key;
 445   init_pair (h, q);
 446   return (hash_pair_union_t *) q;
 447 }
 448
 449 static hash_pair_union_t *
 450 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
 451               uword * found_key)
 452 {
 453   hash_t *h = hash_header (v);
 454   hash_pair_t *new_pair;
 455   hash_pair_union_t *q;
 456
 457   q = get_indirect (v, pi, key);
 458   if (q)
 459     {
 460       *found_key = 1;
 461       return q;
 462     }
 463
 464   if (h->log2_pair_size == 0)
 465     vec_add2 (pi->pairs, new_pair, 1);
 466   else
 467     {
 468       uword len, new_len, log2_bytes;
 469
 470       len = indirect_pair_get_len (pi);
 471       log2_bytes = indirect_pair_get_log2_bytes (pi);
 472
 473       new_len = len + 1;
 474       if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
 475         {
 476           pi->pairs = clib_mem_realloc (pi->pairs,
 477                                         1ULL << (log2_bytes + 1),
 478                                         1ULL << log2_bytes);
 479           log2_bytes++;
 480         }
 481
 482       indirect_pair_set (pi, log2_bytes, new_len);
 483       new_pair = pi->pairs + (len << h->log2_pair_size);
 484     }
 485   new_pair->key = key;
 486   init_pair (h, new_pair);
 487   *found_key = 0;
 488   return (hash_pair_union_t *) new_pair;
 489 }
 490
 491 static void
 492 unset_indirect (void *v, uword i, hash_pair_t * q)
 493 {
 494   hash_t *h = hash_header (v);
 495   hash_pair_union_t *p = get_pair (v, i);
 496   hash_pair_t *e;
 497   hash_pair_indirect_t *pi = &p->indirect;
 498   uword len, is_vec;
 499
 500   is_vec = h->log2_pair_size == 0;
 501
 502   ASSERT (!hash_is_user (v, i));
 503   len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
 504   e = hash_forward (h, pi->pairs, len - 1);
 505   ASSERT (q >= pi->pairs && q <= e);
 506
 507   /* We have two or fewer pairs and we are delete one pair.
 508      Make indirect pointer direct and free indirect memory. */
 509   if (len <= 2)
 510     {
 511       hash_pair_t *r = pi->pairs;
 512
 513       if (len == 2)
 514         {
 515           clib_memcpy_fast (p, q == r ? hash_forward1 (h, r) : r,
 516                             hash_pair_bytes (h));
 517           set_is_user (v, i, 1);
 518         }
 519       else
 520         zero_pair (h, &p->direct);
 521
 522       if (is_vec)
 523         vec_free (r);
 524       else if (r)
 525         clib_mem_free (r);
 526     }
 527   else
 528     {
 529       /* If deleting a pair we need to keep non-null pairs together. */
 530       if (q < e)
 531         clib_memcpy_fast (q, e, hash_pair_bytes (h));
 532       else
 533         zero_pair (h, q);
 534       if (is_vec)
 535         _vec_len (pi->pairs) -= 1;
 536       else
 537         indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
 538     }
 539 }
 540
 541 enum lookup_opcode
 542 {
 543   GET = 1,
 544   SET = 2,
 545   UNSET = 3,
 546 };
 547
 548 static hash_pair_t *
 549 lookup (void *v, uword key, enum lookup_opcode op,
 550         void *new_value, void *old_value)
 551 {
 552   hash_t *h = hash_header (v);
 553   hash_pair_union_t *p = 0;
 554   uword found_key = 0;
 555   uword value_bytes;
 556   uword i;
 557
 558   if (!v)
 559     return 0;
 560
 561   i = key_sum (h, key) & (_vec_len (v) - 1);
 562   p = get_pair (v, i);
 563   value_bytes = hash_value_bytes (h);
 564
 565   if (hash_is_user (v, i))
 566     {
 567       found_key = key_equal (h, p->direct.key, key);
 568       if (found_key)
 569         {
 570           if (op == UNSET)
 571             {
 572               set_is_user (v, i, 0);
 573               if (old_value && value_bytes)
 574                 clib_memcpy_fast (old_value, p->direct.value, value_bytes);
 575               zero_pair (h, &p->direct);
 576             }
 577         }
 578       else
 579         {
 580           if (op == SET)
 581             p = set_indirect_is_user (v, i, p, key);
 582           else
 583             p = 0;
 584         }
 585     }
 586   else
 587     {
 588       hash_pair_indirect_t *pi = &p->indirect;
 589
 590       if (op == SET)
 591         {
 592           if (!pi->pairs)
 593             {
 594               p->direct.key = key;
 595               set_is_user (v, i, 1);
 596             }
 597           else
 598             p = set_indirect (v, pi, key, &found_key);
 599         }
 600       else
 601         {
 602           p = get_indirect (v, pi, key);
 603           found_key = p != 0;
 604           if (found_key && op == UNSET)
 605             {
 606               if (old_value && value_bytes)
 607                 clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
 608
 609               unset_indirect (v, i, &p->direct);
 610
 611               /* Nullify p (since it's just been deleted).
 612                  Otherwise we might be tempted to play with it. */
 613               p = 0;
 614             }
 615         }
 616     }
 617
 618   if (op == SET && p != 0 && value_bytes)
 619     {
 620       /* Save away old value for caller. */
 621       if (old_value && found_key)
 622         clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
 623       clib_memcpy_fast (&p->direct.value, new_value, value_bytes);
 624     }
 625
 626   if (op == SET)
 627     h->elts += !found_key;
 628   if (op == UNSET)
 629     h->elts -= found_key;
 630
 631   return &p->direct;
 632 }
 633
 634 /* Fetch value of key. */
 635 __clib_export uword *
 636 _hash_get (void *v, uword key)
 637 {
 638   hash_t *h = hash_header (v);
 639   hash_pair_t *p;
 640
 641   /* Don't even search table if its empty. */
 642   if (!v || h->elts == 0)
 643     return 0;
 644
 645   p = lookup (v, key, GET, 0, 0);
 646   if (!p)
 647     return 0;
 648   if (h->log2_pair_size == 0)
 649     return &p->key;
 650   else
 651     return &p->value[0];
 652 }
 653
 654 __clib_export hash_pair_t *
 655 _hash_get_pair (void *v, uword key)
 656 {
 657   return lookup (v, key, GET, 0, 0);
 658 }
 659
 660 __clib_export hash_pair_t *
 661 hash_next (void *v, hash_next_t *hn)
 662 {
 663   hash_t *h = hash_header (v);
 664   hash_pair_t *p;
 665
 666   while (1)
 667     {
 668       if (hn->i == 0 && hn->j == 0)
 669         {
 670           /* Save flags. */
 671           hn->f = h->flags;
 672
 673           /* Prevent others from re-sizing hash table. */
 674           h->flags |=
 675             (HASH_FLAG_NO_AUTO_GROW
 676              | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
 677         }
 678       else if (hn->i >= hash_capacity (v))
 679         {
 680           /* Restore flags. */
 681           h->flags = hn->f;
 682           clib_memset (hn, 0, sizeof (hn[0]));
 683           return 0;
 684         }
 685
 686       p = hash_forward (h, v, hn->i);
 687       if (hash_is_user (v, hn->i))
 688         {
 689           hn->i++;
 690           return p;
 691         }
 692       else
 693         {
 694           hash_pair_indirect_t *pi = (void *) p;
 695           uword n;
 696
 697           if (h->log2_pair_size > 0)
 698             n = indirect_pair_get_len (pi);
 699           else
 700             n = vec_len (pi->pairs);
 701
 702           if (hn->j >= n)
 703             {
 704               hn->i++;
 705               hn->j = 0;
 706             }
 707           else
 708             return hash_forward (h, pi->pairs, hn->j++);
 709         }
 710     }
 711 }
 712
 713 /* Remove key from table. */
 714 __clib_export void *
 715 _hash_unset (void *v, uword key, void *old_value)
 716 {
 717   hash_t *h;
 718
 719   if (!v)
 720     return v;
 721
 722   (void) lookup (v, key, UNSET, 0, old_value);
 723
 724   h = hash_header (v);
 725   if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
 726     {
 727       /* Resize when 1/4 full. */
 728       if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
 729         v = hash_resize (v, vec_len (v) / 2);
 730     }
 731
 732   return v;
 733 }
 734
 735 __clib_export void *
 736 _hash_create (uword elts, hash_t * h_user)
 737 {
 738   hash_t *h;
 739   uword log2_pair_size;
 740   void *v;
 741
 742   /* Size of hash is power of 2 >= ELTS and larger than
 743      number of bits in is_user bitmap elements. */
 744   elts = clib_max (elts, BITS (h->is_user[0]));
 745   elts = 1ULL << max_log2 (elts);
 746
 747   log2_pair_size = 1;
 748   if (h_user)
 749     log2_pair_size = h_user->log2_pair_size;
 750
 751   v = _vec_resize ((void *) 0,
 752                    /* vec len: */ elts,
 753                    /* data bytes: */
 754                    (elts << log2_pair_size) * sizeof (hash_pair_t),
 755                    /* header bytes: */
 756                    sizeof (h[0]),
 757                    /* alignment */ sizeof (hash_pair_t));
 758   h = hash_header (v);
 759
 760   if (h_user)
 761     {
 762       h[0] = h_user[0];
 763       h->is_user = 0;
 764     }
 765
 766   vec_validate_aligned (
 767     h->is_user, ((elts / BITS (h->is_user[0])) * sizeof (h->is_user[0])) - 1,
 768     CLIB_CACHE_LINE_BYTES);
 769   h->log2_pair_size = log2_pair_size;
 770   h->elts = 0;
 771
 772   /* Default flags to never shrinking hash tables.
 773      Shrinking tables can cause "jackpot" cases. */
 774   if (!h_user)
 775     h->flags = HASH_FLAG_NO_AUTO_SHRINK;
 776
 777   if (!h->format_pair)
 778     {
 779       h->format_pair = hash_format_pair_default;
 780       h->format_pair_arg = 0;
 781     }
 782
 783   return v;
 784 }
 785
 786 __clib_export void *
 787 _hash_free (void *v)
 788 {
 789   hash_t *h = hash_header (v);
 790   hash_pair_union_t *p;
 791   uword i;
 792
 793   if (!v)
 794     return v;
 795
 796   /* We zero all freed memory in case user would be tempted to use it. */
 797   for (i = 0; i < hash_capacity (v); i++)
 798     {
 799       if (hash_is_user (v, i))
 800         continue;
 801       p = get_pair (v, i);
 802       if (h->log2_pair_size == 0)
 803         vec_free (p->indirect.pairs);
 804       else if (p->indirect.pairs)
 805         clib_mem_free (p->indirect.pairs);
 806     }
 807
 808   vec_free (h->is_user);
 809   vec_free_header (h);
 810
 811   return 0;
 812 }
 813
 814 static void *
 815 hash_resize_internal (void *old, uword new_size, uword free_old)
 816 {
 817   void *new;
 818   hash_pair_t *p;
 819
 820   new = 0;
 821   if (new_size > 0)
 822     {
 823       hash_t *h = old ? hash_header (old) : 0;
 824       new = _hash_create (new_size, h);
 825       /* *INDENT-OFF* */
 826       hash_foreach_pair (p, old, {
 827         new = _hash_set3 (new, p->key, &p->value[0], 0);
 828       });
 829       /* *INDENT-ON* */
 830     }
 831
 832   if (free_old)
 833     hash_free (old);
 834   return new;
 835 }
 836
 837 __clib_export void *
 838 hash_resize (void *old, uword new_size)
 839 {
 840   return hash_resize_internal (old, new_size, 1);
 841 }
 842
 843 __clib_export void *
 844 hash_dup (void *old)
 845 {
 846   return hash_resize_internal (old, vec_len (old), 0);
 847 }
 848
 849 __clib_export void *
 850 _hash_set3 (void *v, uword key, void *value, void *old_value)
 851 {
 852   hash_t *h;
 853
 854   if (!v)
 855     v = hash_create (0, sizeof (uword));
 856
 857   h = hash_header (v);
 858   (void) lookup (v, key, SET, value, old_value);
 859
 860   if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
 861     {
 862       /* Resize when 3/4 full. */
 863       if (4 * (h->elts + 1) > 3 * vec_len (v))
 864         v = hash_resize (v, 2 * vec_len (v));
 865     }
 866
 867   return v;
 868 }
 869
 870 __clib_export uword
 871 vec_key_sum (hash_t * h, uword key)
 872 {
 873   void *v = uword_to_pointer (key, void *);
 874   return hash_memory (v, vec_len (v) * h->user, 0);
 875 }
 876
 877 __clib_export uword
 878 vec_key_equal (hash_t * h, uword key1, uword key2)
 879 {
 880   void *v1 = uword_to_pointer (key1, void *);
 881   void *v2 = uword_to_pointer (key2, void *);
 882   uword l1 = vec_len (v1);
 883   uword l2 = vec_len (v2);
 884   return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
 885 }
 886
 887 __clib_export u8 *
 888 vec_key_format_pair (u8 * s, va_list * args)
 889 {
 890   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 891   void *v = va_arg (*args, void *);
 892   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 893   hash_t *h = hash_header (v);
 894   void *u = uword_to_pointer (p->key, void *);
 895   int i;
 896
 897   switch (h->user)
 898     {
 899     case 1:
 900       s = format (s, "%v", u);
 901       break;
 902
 903     case 2:
 904       {
 905         u16 *w = u;
 906         for (i = 0; i < vec_len (w); i++)
 907           s = format (s, "0x%x, ", w[i]);
 908         break;
 909       }
 910
 911     case 4:
 912       {
 913         u32 *w = u;
 914         for (i = 0; i < vec_len (w); i++)
 915           s = format (s, "0x%x, ", w[i]);
 916         break;
 917       }
 918
 919     case 8:
 920       {
 921         u64 *w = u;
 922         for (i = 0; i < vec_len (w); i++)
 923           s = format (s, "0x%Lx, ", w[i]);
 924         break;
 925       }
 926
 927     default:
 928       s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
 929       break;
 930     }
 931
 932   if (hash_value_bytes (h) > 0)
 933     s = format (s, " -> 0x%wx", p->value[0]);
 934
 935   return s;
 936 }
 937
 938 __clib_export uword
 939 mem_key_sum (hash_t * h, uword key)
 940 {
 941   uword *v = uword_to_pointer (key, void *);
 942   return hash_memory (v, h->user, 0);
 943 }
 944
 945 __clib_export uword
 946 mem_key_equal (hash_t * h, uword key1, uword key2)
 947 {
 948   void *v1 = uword_to_pointer (key1, void *);
 949   void *v2 = uword_to_pointer (key2, void *);
 950   return v1 && v2 && 0 == memcmp (v1, v2, h->user);
 951 }
 952
 953 uword
 954 string_key_sum (hash_t * h, uword key)
 955 {
 956   char *v = uword_to_pointer (key, char *);
 957   return hash_memory (v, strlen (v), 0);
 958 }
 959
 960 uword
 961 string_key_equal (hash_t * h, uword key1, uword key2)
 962 {
 963   void *v1 = uword_to_pointer (key1, void *);
 964   void *v2 = uword_to_pointer (key2, void *);
 965   return v1 && v2 && 0 == strcmp (v1, v2);
 966 }
 967
 968 u8 *
 969 string_key_format_pair (u8 * s, va_list * args)
 970 {
 971   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 972   void *v = va_arg (*args, void *);
 973   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 974   hash_t *h = hash_header (v);
 975   void *u = uword_to_pointer (p->key, void *);
 976
 977   s = format (s, "%s", u);
 978
 979   if (hash_value_bytes (h) > 0)
 980     s =
 981       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 982               hash_value_bytes (h));
 983
 984   return s;
 985 }
 986
 987 static u8 *
 988 hash_format_pair_default (u8 * s, va_list * args)
 989 {
 990   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 991   void *v = va_arg (*args, void *);
 992   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 993   hash_t *h = hash_header (v);
 994
 995   s = format (s, "0x%08x", p->key);
 996   if (hash_value_bytes (h) > 0)
 997     s =
 998       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 999               hash_value_bytes (h));
1000   return s;
1001 }
1002
1003 __clib_export uword
1004 hash_bytes (void *v)
1005 {
1006   uword i, bytes;
1007   hash_t *h = hash_header (v);
1008
1009   if (!v)
1010     return 0;
1011
1012   bytes = vec_mem_size (v);
1013
1014   for (i = 0; i < hash_capacity (v); i++)
1015     {
1016       if (!hash_is_user (v, i))
1017         {
1018           hash_pair_union_t *p = get_pair (v, i);
1019           if (h->log2_pair_size > 0)
1020             bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
1021           else
1022             bytes += vec_mem_size (p->indirect.pairs);
1023         }
1024     }
1025   return bytes;
1026 }
1027
1028 __clib_export u8 *
1029 format_hash (u8 *s, va_list *va)
1030 {
1031   void *v = va_arg (*va, void *);
1032   int verbose = va_arg (*va, int);
1033   hash_pair_t *p;
1034   hash_t *h = hash_header (v);
1035   uword i;
1036
1037   s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
1038               v, hash_elts (v), hash_capacity (v), hash_bytes (v));
1039
1040   {
1041     uword *occupancy = 0;
1042
1043     /* Count number of buckets with each occupancy. */
1044     for (i = 0; i < hash_capacity (v); i++)
1045       {
1046         uword j;
1047
1048         if (hash_is_user (v, i))
1049           {
1050             j = 1;
1051           }
1052         else
1053           {
1054             hash_pair_union_t *p = get_pair (v, i);
1055             if (h->log2_pair_size > 0)
1056               j = indirect_pair_get_len (&p->indirect);
1057             else
1058               j = vec_len (p->indirect.pairs);
1059           }
1060
1061         vec_validate (occupancy, j);
1062         occupancy[j]++;
1063       }
1064
1065     s = format (s, "  profile ");
1066     for (i = 0; i < vec_len (occupancy); i++)
1067       s = format (s, "%wd%c", occupancy[i],
1068                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
1069
1070     s = format (s, "  lookup # of compares: ");
1071     for (i = 1; i < vec_len (occupancy); i++)
1072       s = format (s, "%wd: .%03d%c", i,
1073                   (1000 * i * occupancy[i]) / hash_elts (v),
1074                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
1075
1076     vec_free (occupancy);
1077   }
1078
1079   if (verbose)
1080     {
1081       /* *INDENT-OFF* */
1082       hash_foreach_pair (p, v, {
1083         s = format (s, "  %U\n", h->format_pair, h->format_pair_arg, v, p);
1084       });
1085       /* *INDENT-ON* */
1086     }
1087
1088   return s;
1089 }
1090
1091 static uword
1092 unformat_hash_string_internal (unformat_input_t * input,
1093                                va_list * va, int is_vec)
1094 {
1095   uword *hash = va_arg (*va, uword *);
1096   int *result = va_arg (*va, int *);
1097   u8 *string = 0;
1098   uword *p;
1099
1100   if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1101     return 0;
1102
1103   p = hash_get_mem (hash, string);
1104   if (p)
1105     *result = *p;
1106
1107   vec_free (string);
1108   return p ? 1 : 0;
1109 }
1110
1111 __clib_export uword
1112 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1113 {
1114   return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1115 }
1116
1117 __clib_export uword
1118 unformat_hash_string (unformat_input_t * input, va_list * va)
1119 {
1120   return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1121 }
1122
1123 __clib_export clib_error_t *
1124 hash_validate (void *v)
1125 {
1126   hash_t *h = hash_header (v);
1127   uword i, j;
1128   uword *keys = 0;
1129   clib_error_t *error = 0;
1130
1131 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1132
1133   for (i = 0; i < hash_capacity (v); i++)
1134     {
1135       hash_pair_union_t *pu = get_pair (v, i);
1136
1137       if (hash_is_user (v, i))
1138         {
1139           CHECK (pu->direct.key != 0);
1140           vec_add1 (keys, pu->direct.key);
1141         }
1142       else
1143         {
1144           hash_pair_t *p;
1145           hash_pair_indirect_t *pi = &pu->indirect;
1146           uword n;
1147
1148           n = h->log2_pair_size > 0
1149             ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1150
1151           for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1152             {
1153               /* Assert key uniqueness. */
1154               for (j = 0; j < vec_len (keys); j++)
1155                 CHECK (keys[j] != p->key);
1156               vec_add1 (keys, p->key);
1157             }
1158         }
1159     }
1160
1161   CHECK (vec_len (keys) == h->elts);
1162
1163   vec_free (keys);
1164 done:
1165   return error;
1166 }
1167
1168 /*
1169  * fd.io coding-style-patch-verification: ON
1170  *
1171  * Local Variables:
1172  * eval: (c-set-style "gnu")
1173  * End:
1174  */