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                    (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
 758                    /* alignment */ sizeof (hash_pair_t));
 759   h = hash_header (v);
 760
 761   if (h_user)
 762     h[0] = h_user[0];
 763
 764   h->log2_pair_size = log2_pair_size;
 765   h->elts = 0;
 766
 767   /* Default flags to never shrinking hash tables.
 768      Shrinking tables can cause "jackpot" cases. */
 769   if (!h_user)
 770     h->flags = HASH_FLAG_NO_AUTO_SHRINK;
 771
 772   if (!h->format_pair)
 773     {
 774       h->format_pair = hash_format_pair_default;
 775       h->format_pair_arg = 0;
 776     }
 777
 778   return v;
 779 }
 780
 781 __clib_export void *
 782 _hash_free (void *v)
 783 {
 784   hash_t *h = hash_header (v);
 785   hash_pair_union_t *p;
 786   uword i;
 787
 788   if (!v)
 789     return v;
 790
 791   /* We zero all freed memory in case user would be tempted to use it. */
 792   for (i = 0; i < hash_capacity (v); i++)
 793     {
 794       if (hash_is_user (v, i))
 795         continue;
 796       p = get_pair (v, i);
 797       if (h->log2_pair_size == 0)
 798         vec_free (p->indirect.pairs);
 799       else if (p->indirect.pairs)
 800         clib_mem_free (p->indirect.pairs);
 801     }
 802
 803   vec_free_header (h);
 804
 805   return 0;
 806 }
 807
 808 static void *
 809 hash_resize_internal (void *old, uword new_size, uword free_old)
 810 {
 811   void *new;
 812   hash_pair_t *p;
 813
 814   new = 0;
 815   if (new_size > 0)
 816     {
 817       hash_t *h = old ? hash_header (old) : 0;
 818       new = _hash_create (new_size, h);
 819       /* *INDENT-OFF* */
 820       hash_foreach_pair (p, old, {
 821         new = _hash_set3 (new, p->key, &p->value[0], 0);
 822       });
 823       /* *INDENT-ON* */
 824     }
 825
 826   if (free_old)
 827     hash_free (old);
 828   return new;
 829 }
 830
 831 void *
 832 hash_resize (void *old, uword new_size)
 833 {
 834   return hash_resize_internal (old, new_size, 1);
 835 }
 836
 837 __clib_export void *
 838 hash_dup (void *old)
 839 {
 840   return hash_resize_internal (old, vec_len (old), 0);
 841 }
 842
 843 __clib_export void *
 844 _hash_set3 (void *v, uword key, void *value, void *old_value)
 845 {
 846   hash_t *h;
 847
 848   if (!v)
 849     v = hash_create (0, sizeof (uword));
 850
 851   h = hash_header (v);
 852   (void) lookup (v, key, SET, value, old_value);
 853
 854   if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
 855     {
 856       /* Resize when 3/4 full. */
 857       if (4 * (h->elts + 1) > 3 * vec_len (v))
 858         v = hash_resize (v, 2 * vec_len (v));
 859     }
 860
 861   return v;
 862 }
 863
 864 __clib_export uword
 865 vec_key_sum (hash_t * h, uword key)
 866 {
 867   void *v = uword_to_pointer (key, void *);
 868   return hash_memory (v, vec_len (v) * h->user, 0);
 869 }
 870
 871 __clib_export uword
 872 vec_key_equal (hash_t * h, uword key1, uword key2)
 873 {
 874   void *v1 = uword_to_pointer (key1, void *);
 875   void *v2 = uword_to_pointer (key2, void *);
 876   uword l1 = vec_len (v1);
 877   uword l2 = vec_len (v2);
 878   return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
 879 }
 880
 881 __clib_export u8 *
 882 vec_key_format_pair (u8 * s, va_list * args)
 883 {
 884   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 885   void *v = va_arg (*args, void *);
 886   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 887   hash_t *h = hash_header (v);
 888   void *u = uword_to_pointer (p->key, void *);
 889   int i;
 890
 891   switch (h->user)
 892     {
 893     case 1:
 894       s = format (s, "%v", u);
 895       break;
 896
 897     case 2:
 898       {
 899         u16 *w = u;
 900         for (i = 0; i < vec_len (w); i++)
 901           s = format (s, "0x%x, ", w[i]);
 902         break;
 903       }
 904
 905     case 4:
 906       {
 907         u32 *w = u;
 908         for (i = 0; i < vec_len (w); i++)
 909           s = format (s, "0x%x, ", w[i]);
 910         break;
 911       }
 912
 913     case 8:
 914       {
 915         u64 *w = u;
 916         for (i = 0; i < vec_len (w); i++)
 917           s = format (s, "0x%Lx, ", w[i]);
 918         break;
 919       }
 920
 921     default:
 922       s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
 923       break;
 924     }
 925
 926   if (hash_value_bytes (h) > 0)
 927     s = format (s, " -> 0x%wx", p->value[0]);
 928
 929   return s;
 930 }
 931
 932 __clib_export uword
 933 mem_key_sum (hash_t * h, uword key)
 934 {
 935   uword *v = uword_to_pointer (key, void *);
 936   return hash_memory (v, h->user, 0);
 937 }
 938
 939 __clib_export uword
 940 mem_key_equal (hash_t * h, uword key1, uword key2)
 941 {
 942   void *v1 = uword_to_pointer (key1, void *);
 943   void *v2 = uword_to_pointer (key2, void *);
 944   return v1 && v2 && 0 == memcmp (v1, v2, h->user);
 945 }
 946
 947 uword
 948 string_key_sum (hash_t * h, uword key)
 949 {
 950   char *v = uword_to_pointer (key, char *);
 951   return hash_memory (v, strlen (v), 0);
 952 }
 953
 954 uword
 955 string_key_equal (hash_t * h, uword key1, uword key2)
 956 {
 957   void *v1 = uword_to_pointer (key1, void *);
 958   void *v2 = uword_to_pointer (key2, void *);
 959   return v1 && v2 && 0 == strcmp (v1, v2);
 960 }
 961
 962 u8 *
 963 string_key_format_pair (u8 * s, va_list * args)
 964 {
 965   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 966   void *v = va_arg (*args, void *);
 967   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 968   hash_t *h = hash_header (v);
 969   void *u = uword_to_pointer (p->key, void *);
 970
 971   s = format (s, "%s", u);
 972
 973   if (hash_value_bytes (h) > 0)
 974     s =
 975       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 976               hash_value_bytes (h));
 977
 978   return s;
 979 }
 980
 981 static u8 *
 982 hash_format_pair_default (u8 * s, va_list * args)
 983 {
 984   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 985   void *v = va_arg (*args, void *);
 986   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 987   hash_t *h = hash_header (v);
 988
 989   s = format (s, "0x%08x", p->key);
 990   if (hash_value_bytes (h) > 0)
 991     s =
 992       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 993               hash_value_bytes (h));
 994   return s;
 995 }
 996
 997 __clib_export uword
 998 hash_bytes (void *v)
 999 {
1000   uword i, bytes;
1001   hash_t *h = hash_header (v);
1002
1003   if (!v)
1004     return 0;
1005
1006   bytes = vec_capacity (v, hash_header_bytes (v));
1007
1008   for (i = 0; i < hash_capacity (v); i++)
1009     {
1010       if (!hash_is_user (v, i))
1011         {
1012           hash_pair_union_t *p = get_pair (v, i);
1013           if (h->log2_pair_size > 0)
1014             bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
1015           else
1016             bytes += vec_capacity (p->indirect.pairs, 0);
1017         }
1018     }
1019   return bytes;
1020 }
1021
1022 __clib_export u8 *
1023 format_hash (u8 *s, va_list *va)
1024 {
1025   void *v = va_arg (*va, void *);
1026   int verbose = va_arg (*va, int);
1027   hash_pair_t *p;
1028   hash_t *h = hash_header (v);
1029   uword i;
1030
1031   s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
1032               v, hash_elts (v), hash_capacity (v), hash_bytes (v));
1033
1034   {
1035     uword *occupancy = 0;
1036
1037     /* Count number of buckets with each occupancy. */
1038     for (i = 0; i < hash_capacity (v); i++)
1039       {
1040         uword j;
1041
1042         if (hash_is_user (v, i))
1043           {
1044             j = 1;
1045           }
1046         else
1047           {
1048             hash_pair_union_t *p = get_pair (v, i);
1049             if (h->log2_pair_size > 0)
1050               j = indirect_pair_get_len (&p->indirect);
1051             else
1052               j = vec_len (p->indirect.pairs);
1053           }
1054
1055         vec_validate (occupancy, j);
1056         occupancy[j]++;
1057       }
1058
1059     s = format (s, "  profile ");
1060     for (i = 0; i < vec_len (occupancy); i++)
1061       s = format (s, "%wd%c", occupancy[i],
1062                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
1063
1064     s = format (s, "  lookup # of compares: ");
1065     for (i = 1; i < vec_len (occupancy); i++)
1066       s = format (s, "%wd: .%03d%c", i,
1067                   (1000 * i * occupancy[i]) / hash_elts (v),
1068                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
1069
1070     vec_free (occupancy);
1071   }
1072
1073   if (verbose)
1074     {
1075       /* *INDENT-OFF* */
1076       hash_foreach_pair (p, v, {
1077         s = format (s, "  %U\n", h->format_pair, h->format_pair_arg, v, p);
1078       });
1079       /* *INDENT-ON* */
1080     }
1081
1082   return s;
1083 }
1084
1085 static uword
1086 unformat_hash_string_internal (unformat_input_t * input,
1087                                va_list * va, int is_vec)
1088 {
1089   uword *hash = va_arg (*va, uword *);
1090   int *result = va_arg (*va, int *);
1091   u8 *string = 0;
1092   uword *p;
1093
1094   if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1095     return 0;
1096
1097   p = hash_get_mem (hash, string);
1098   if (p)
1099     *result = *p;
1100
1101   vec_free (string);
1102   return p ? 1 : 0;
1103 }
1104
1105 __clib_export uword
1106 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1107 {
1108   return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1109 }
1110
1111 __clib_export uword
1112 unformat_hash_string (unformat_input_t * input, va_list * va)
1113 {
1114   return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1115 }
1116
1117 __clib_export clib_error_t *
1118 hash_validate (void *v)
1119 {
1120   hash_t *h = hash_header (v);
1121   uword i, j;
1122   uword *keys = 0;
1123   clib_error_t *error = 0;
1124
1125 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1126
1127   for (i = 0; i < hash_capacity (v); i++)
1128     {
1129       hash_pair_union_t *pu = get_pair (v, i);
1130
1131       if (hash_is_user (v, i))
1132         {
1133           CHECK (pu->direct.key != 0);
1134           vec_add1 (keys, pu->direct.key);
1135         }
1136       else
1137         {
1138           hash_pair_t *p;
1139           hash_pair_indirect_t *pi = &pu->indirect;
1140           uword n;
1141
1142           n = h->log2_pair_size > 0
1143             ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1144
1145           for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1146             {
1147               /* Assert key uniqueness. */
1148               for (j = 0; j < vec_len (keys); j++)
1149                 CHECK (keys[j] != p->key);
1150               vec_add1 (keys, p->key);
1151             }
1152         }
1153     }
1154
1155   CHECK (vec_len (keys) == h->elts);
1156
1157   vec_free (keys);
1158 done:
1159   return error;
1160 }
1161
1162 /*
1163  * fd.io coding-style-patch-verification: ON
1164  *
1165  * Local Variables:
1166  * eval: (c-set-style "gnu")
1167  * End:
1168  */