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             c +=
 157               zap64 (CLIB_MEM_OVERFLOW
 158                      (clib_mem_unaligned (q + 2, u64), q + 2, sizeof (u64)),
 159                      n % sizeof (u64)) << 8;
 160           else
 161             {
 162               clib_memcpy_fast (tmp.as_u8, q + 2, n % sizeof (u64));
 163               c += zap64 (tmp.as_u64, n % sizeof (u64)) << 8;
 164             }
 165         }
 166       break;
 167
 168     case 1:
 169       a += clib_mem_unaligned (q + 0, u64);
 170       if (n % sizeof (u64))
 171         {
 172           if (PREDICT_TRUE (page_boundary_crossing == 0))
 173             b +=
 174               zap64 (CLIB_MEM_OVERFLOW
 175                      (clib_mem_unaligned (q + 1, u64), q + 1, sizeof (u64)),
 176                      n % sizeof (u64));
 177           else
 178             {
 179               clib_memcpy_fast (tmp.as_u8, q + 1, n % sizeof (u64));
 180               b += zap64 (tmp.as_u64, n % sizeof (u64));
 181             }
 182         }
 183       break;
 184
 185     case 0:
 186       if (n % sizeof (u64))
 187         {
 188           if (PREDICT_TRUE (page_boundary_crossing == 0))
 189             a +=
 190               zap64 (CLIB_MEM_OVERFLOW
 191                      (clib_mem_unaligned (q + 0, u64), q + 0, sizeof (u64)),
 192                      n % sizeof (u64));
 193           else
 194             {
 195               clib_memcpy_fast (tmp.as_u8, q, n % sizeof (u64));
 196               a += zap64 (tmp.as_u64, n % sizeof (u64));
 197             }
 198         }
 199       break;
 200     }
 201
 202   hash_mix64 (a, b, c);
 203
 204   return c;
 205 }
 206
 207 #else /* if uword_bits == 64 */
 208
 209 static inline u32
 210 zap32 (u32 x, word n)
 211 {
 212 #define _(n) (((u32) 1 << (u32) (8*(n))) - (u32) 1)
 213   static u32 masks_little_endian[] = {
 214     0, _(1), _(2), _(3),
 215   };
 216   static u32 masks_big_endian[] = {
 217     0, ~_(3), ~_(2), ~_(1),
 218   };
 219 #undef _
 220   if (clib_arch_is_big_endian)
 221     return x & masks_big_endian[n];
 222   else
 223     return x & masks_little_endian[n];
 224 }
 225
 226 static inline u32
 227 hash_memory32 (void *p, word n_bytes, u32 state)
 228 {
 229   u32 *q = p;
 230   u32 a, b, c, n;
 231
 232   a = b = 0x9e3779b9;
 233   c = state;
 234   n = n_bytes;
 235
 236   while (n >= 3 * sizeof (u32))
 237     {
 238       a += clib_mem_unaligned (q + 0, u32);
 239       b += clib_mem_unaligned (q + 1, u32);
 240       c += clib_mem_unaligned (q + 2, u32);
 241       hash_mix32 (a, b, c);
 242       n -= 3 * sizeof (u32);
 243       q += 3;
 244     }
 245
 246   c += n_bytes;
 247   switch (n / sizeof (u32))
 248     {
 249     case 2:
 250       a += clib_mem_unaligned (q + 0, u32);
 251       b += clib_mem_unaligned (q + 1, u32);
 252       if (n % sizeof (u32))
 253         c += zap32 (clib_mem_unaligned (q + 2, u32), n % sizeof (u32)) << 8;
 254       break;
 255
 256     case 1:
 257       a += clib_mem_unaligned (q + 0, u32);
 258       if (n % sizeof (u32))
 259         b += zap32 (clib_mem_unaligned (q + 1, u32), n % sizeof (u32));
 260       break;
 261
 262     case 0:
 263       if (n % sizeof (u32))
 264         a += zap32 (clib_mem_unaligned (q + 0, u32), n % sizeof (u32));
 265       break;
 266     }
 267
 268   hash_mix32 (a, b, c);
 269
 270   return c;
 271 }
 272 #endif
 273
 274 __clib_export uword
 275 hash_memory (void *p, word n_bytes, uword state)
 276 {
 277   uword *q = p;
 278
 279 #if uword_bits == 64
 280   return hash_memory64 (q, n_bytes, state);
 281 #else
 282   return hash_memory32 (q, n_bytes, state);
 283 #endif
 284 }
 285
 286 #if uword_bits == 64
 287 always_inline uword
 288 hash_uword (uword x)
 289 {
 290   u64 a, b, c;
 291
 292   a = b = 0x9e3779b97f4a7c13LL;
 293   c = 0;
 294   a += x;
 295   hash_mix64 (a, b, c);
 296   return c;
 297 }
 298 #else
 299 always_inline uword
 300 hash_uword (uword x)
 301 {
 302   u32 a, b, c;
 303
 304   a = b = 0x9e3779b9;
 305   c = 0;
 306   a += x;
 307   hash_mix32 (a, b, c);
 308   return c;
 309 }
 310 #endif
 311
 312 /* Call sum function.  Hash code will be sum function value
 313    modulo the prime length of the hash table. */
 314 always_inline uword
 315 key_sum (hash_t * h, uword key)
 316 {
 317   uword sum;
 318   switch (pointer_to_uword ((void *) h->key_sum))
 319     {
 320     case KEY_FUNC_NONE:
 321       sum = hash_uword (key);
 322       break;
 323
 324     case KEY_FUNC_POINTER_UWORD:
 325       sum = hash_uword (*uword_to_pointer (key, uword *));
 326       break;
 327
 328     case KEY_FUNC_POINTER_U32:
 329       sum = hash_uword (*uword_to_pointer (key, u32 *));
 330       break;
 331
 332     case KEY_FUNC_STRING:
 333       sum = string_key_sum (h, key);
 334       break;
 335
 336     case KEY_FUNC_MEM:
 337       sum = mem_key_sum (h, key);
 338       break;
 339
 340     default:
 341       sum = h->key_sum (h, key);
 342       break;
 343     }
 344
 345   return sum;
 346 }
 347
 348 always_inline uword
 349 key_equal1 (hash_t * h, uword key1, uword key2, uword e)
 350 {
 351   switch (pointer_to_uword ((void *) h->key_equal))
 352     {
 353     case KEY_FUNC_NONE:
 354       break;
 355
 356     case KEY_FUNC_POINTER_UWORD:
 357       e =
 358         *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
 359                                                                 uword *);
 360       break;
 361
 362     case KEY_FUNC_POINTER_U32:
 363       e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
 364       break;
 365
 366     case KEY_FUNC_STRING:
 367       e = string_key_equal (h, key1, key2);
 368       break;
 369
 370     case KEY_FUNC_MEM:
 371       e = mem_key_equal (h, key1, key2);
 372       break;
 373
 374     default:
 375       e = h->key_equal (h, key1, key2);
 376       break;
 377     }
 378   return e;
 379 }
 380
 381 /* Compares two keys: returns 1 if equal, 0 if not. */
 382 always_inline uword
 383 key_equal (hash_t * h, uword key1, uword key2)
 384 {
 385   uword e = key1 == key2;
 386   if (CLIB_DEBUG > 0 && key1 == key2)
 387     ASSERT (key_equal1 (h, key1, key2, e));
 388   if (!e)
 389     e = key_equal1 (h, key1, key2, e);
 390   return e;
 391 }
 392
 393 static hash_pair_union_t *
 394 get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
 395 {
 396   hash_t *h = hash_header (v);
 397   hash_pair_t *p0, *p1;
 398
 399   p0 = p1 = pi->pairs;
 400   if (h->log2_pair_size > 0)
 401     p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
 402   else
 403     p1 += vec_len (p0);
 404
 405   while (p0 < p1)
 406     {
 407       if (key_equal (h, p0->key, key))
 408         return (hash_pair_union_t *) p0;
 409       p0 = hash_forward1 (h, p0);
 410     }
 411
 412   return (hash_pair_union_t *) 0;
 413 }
 414
 415 static hash_pair_union_t *
 416 set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
 417 {
 418   hash_t *h = hash_header (v);
 419   hash_pair_t *q;
 420   hash_pair_indirect_t *pi = &p->indirect;
 421   uword log2_bytes = 0;
 422
 423   if (h->log2_pair_size == 0)
 424     q = vec_new (hash_pair_t, 2);
 425   else
 426     {
 427       log2_bytes = 1 + hash_pair_log2_bytes (h);
 428       q = clib_mem_alloc (1ULL << log2_bytes);
 429     }
 430   clib_memcpy_fast (q, &p->direct, hash_pair_bytes (h));
 431
 432   pi->pairs = q;
 433   if (h->log2_pair_size > 0)
 434     indirect_pair_set (pi, log2_bytes, 2);
 435
 436   set_is_user (v, i, 0);
 437
 438   /* First element is used by existing pair, second will be used by caller. */
 439   q = hash_forward1 (h, q);
 440   q->key = key;
 441   init_pair (h, q);
 442   return (hash_pair_union_t *) q;
 443 }
 444
 445 static hash_pair_union_t *
 446 set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
 447               uword * found_key)
 448 {
 449   hash_t *h = hash_header (v);
 450   hash_pair_t *new_pair;
 451   hash_pair_union_t *q;
 452
 453   q = get_indirect (v, pi, key);
 454   if (q)
 455     {
 456       *found_key = 1;
 457       return q;
 458     }
 459
 460   if (h->log2_pair_size == 0)
 461     vec_add2 (pi->pairs, new_pair, 1);
 462   else
 463     {
 464       uword len, new_len, log2_bytes;
 465
 466       len = indirect_pair_get_len (pi);
 467       log2_bytes = indirect_pair_get_log2_bytes (pi);
 468
 469       new_len = len + 1;
 470       if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
 471         {
 472           pi->pairs = clib_mem_realloc (pi->pairs,
 473                                         1ULL << (log2_bytes + 1),
 474                                         1ULL << log2_bytes);
 475           log2_bytes++;
 476         }
 477
 478       indirect_pair_set (pi, log2_bytes, new_len);
 479       new_pair = pi->pairs + (len << h->log2_pair_size);
 480     }
 481   new_pair->key = key;
 482   init_pair (h, new_pair);
 483   *found_key = 0;
 484   return (hash_pair_union_t *) new_pair;
 485 }
 486
 487 static void
 488 unset_indirect (void *v, uword i, hash_pair_t * q)
 489 {
 490   hash_t *h = hash_header (v);
 491   hash_pair_union_t *p = get_pair (v, i);
 492   hash_pair_t *e;
 493   hash_pair_indirect_t *pi = &p->indirect;
 494   uword len, is_vec;
 495
 496   is_vec = h->log2_pair_size == 0;
 497
 498   ASSERT (!hash_is_user (v, i));
 499   len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
 500   e = hash_forward (h, pi->pairs, len - 1);
 501   ASSERT (q >= pi->pairs && q <= e);
 502
 503   /* We have two or fewer pairs and we are delete one pair.
 504      Make indirect pointer direct and free indirect memory. */
 505   if (len <= 2)
 506     {
 507       hash_pair_t *r = pi->pairs;
 508
 509       if (len == 2)
 510         {
 511           clib_memcpy_fast (p, q == r ? hash_forward1 (h, r) : r,
 512                             hash_pair_bytes (h));
 513           set_is_user (v, i, 1);
 514         }
 515       else
 516         zero_pair (h, &p->direct);
 517
 518       if (is_vec)
 519         vec_free (r);
 520       else if (r)
 521         clib_mem_free (r);
 522     }
 523   else
 524     {
 525       /* If deleting a pair we need to keep non-null pairs together. */
 526       if (q < e)
 527         clib_memcpy_fast (q, e, hash_pair_bytes (h));
 528       else
 529         zero_pair (h, q);
 530       if (is_vec)
 531         _vec_len (pi->pairs) -= 1;
 532       else
 533         indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
 534     }
 535 }
 536
 537 enum lookup_opcode
 538 {
 539   GET = 1,
 540   SET = 2,
 541   UNSET = 3,
 542 };
 543
 544 static hash_pair_t *
 545 lookup (void *v, uword key, enum lookup_opcode op,
 546         void *new_value, void *old_value)
 547 {
 548   hash_t *h = hash_header (v);
 549   hash_pair_union_t *p = 0;
 550   uword found_key = 0;
 551   uword value_bytes;
 552   uword i;
 553
 554   if (!v)
 555     return 0;
 556
 557   i = key_sum (h, key) & (_vec_len (v) - 1);
 558   p = get_pair (v, i);
 559   value_bytes = hash_value_bytes (h);
 560
 561   if (hash_is_user (v, i))
 562     {
 563       found_key = key_equal (h, p->direct.key, key);
 564       if (found_key)
 565         {
 566           if (op == UNSET)
 567             {
 568               set_is_user (v, i, 0);
 569               if (old_value && value_bytes)
 570                 clib_memcpy_fast (old_value, p->direct.value, value_bytes);
 571               zero_pair (h, &p->direct);
 572             }
 573         }
 574       else
 575         {
 576           if (op == SET)
 577             p = set_indirect_is_user (v, i, p, key);
 578           else
 579             p = 0;
 580         }
 581     }
 582   else
 583     {
 584       hash_pair_indirect_t *pi = &p->indirect;
 585
 586       if (op == SET)
 587         {
 588           if (!pi->pairs)
 589             {
 590               p->direct.key = key;
 591               set_is_user (v, i, 1);
 592             }
 593           else
 594             p = set_indirect (v, pi, key, &found_key);
 595         }
 596       else
 597         {
 598           p = get_indirect (v, pi, key);
 599           found_key = p != 0;
 600           if (found_key && op == UNSET)
 601             {
 602               if (old_value && value_bytes)
 603                 clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
 604
 605               unset_indirect (v, i, &p->direct);
 606
 607               /* Nullify p (since it's just been deleted).
 608                  Otherwise we might be tempted to play with it. */
 609               p = 0;
 610             }
 611         }
 612     }
 613
 614   if (op == SET && p != 0 && value_bytes)
 615     {
 616       /* Save away old value for caller. */
 617       if (old_value && found_key)
 618         clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
 619       clib_memcpy_fast (&p->direct.value, new_value, value_bytes);
 620     }
 621
 622   if (op == SET)
 623     h->elts += !found_key;
 624   if (op == UNSET)
 625     h->elts -= found_key;
 626
 627   return &p->direct;
 628 }
 629
 630 /* Fetch value of key. */
 631 __clib_export uword *
 632 _hash_get (void *v, uword key)
 633 {
 634   hash_t *h = hash_header (v);
 635   hash_pair_t *p;
 636
 637   /* Don't even search table if its empty. */
 638   if (!v || h->elts == 0)
 639     return 0;
 640
 641   p = lookup (v, key, GET, 0, 0);
 642   if (!p)
 643     return 0;
 644   if (h->log2_pair_size == 0)
 645     return &p->key;
 646   else
 647     return &p->value[0];
 648 }
 649
 650 __clib_export hash_pair_t *
 651 _hash_get_pair (void *v, uword key)
 652 {
 653   return lookup (v, key, GET, 0, 0);
 654 }
 655
 656 __clib_export hash_pair_t *
 657 hash_next (void *v, hash_next_t *hn)
 658 {
 659   hash_t *h = hash_header (v);
 660   hash_pair_t *p;
 661
 662   while (1)
 663     {
 664       if (hn->i == 0 && hn->j == 0)
 665         {
 666           /* Save flags. */
 667           hn->f = h->flags;
 668
 669           /* Prevent others from re-sizing hash table. */
 670           h->flags |=
 671             (HASH_FLAG_NO_AUTO_GROW
 672              | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
 673         }
 674       else if (hn->i >= hash_capacity (v))
 675         {
 676           /* Restore flags. */
 677           h->flags = hn->f;
 678           clib_memset (hn, 0, sizeof (hn[0]));
 679           return 0;
 680         }
 681
 682       p = hash_forward (h, v, hn->i);
 683       if (hash_is_user (v, hn->i))
 684         {
 685           hn->i++;
 686           return p;
 687         }
 688       else
 689         {
 690           hash_pair_indirect_t *pi = (void *) p;
 691           uword n;
 692
 693           if (h->log2_pair_size > 0)
 694             n = indirect_pair_get_len (pi);
 695           else
 696             n = vec_len (pi->pairs);
 697
 698           if (hn->j >= n)
 699             {
 700               hn->i++;
 701               hn->j = 0;
 702             }
 703           else
 704             return hash_forward (h, pi->pairs, hn->j++);
 705         }
 706     }
 707 }
 708
 709 /* Remove key from table. */
 710 __clib_export void *
 711 _hash_unset (void *v, uword key, void *old_value)
 712 {
 713   hash_t *h;
 714
 715   if (!v)
 716     return v;
 717
 718   (void) lookup (v, key, UNSET, 0, old_value);
 719
 720   h = hash_header (v);
 721   if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
 722     {
 723       /* Resize when 1/4 full. */
 724       if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
 725         v = hash_resize (v, vec_len (v) / 2);
 726     }
 727
 728   return v;
 729 }
 730
 731 __clib_export void *
 732 _hash_create (uword elts, hash_t * h_user)
 733 {
 734   hash_t *h;
 735   uword log2_pair_size;
 736   void *v;
 737
 738   /* Size of hash is power of 2 >= ELTS and larger than
 739      number of bits in is_user bitmap elements. */
 740   elts = clib_max (elts, BITS (h->is_user[0]));
 741   elts = 1ULL << max_log2 (elts);
 742
 743   log2_pair_size = 1;
 744   if (h_user)
 745     log2_pair_size = h_user->log2_pair_size;
 746
 747   v = _vec_resize ((void *) 0,
 748                    /* vec len: */ elts,
 749                    /* data bytes: */
 750                    (elts << log2_pair_size) * sizeof (hash_pair_t),
 751                    /* header bytes: */
 752                    sizeof (h[0]) +
 753                    (elts / BITS (h->is_user[0])) * sizeof (h->is_user[0]),
 754                    /* alignment */ sizeof (hash_pair_t));
 755   h = hash_header (v);
 756
 757   if (h_user)
 758     h[0] = h_user[0];
 759
 760   h->log2_pair_size = log2_pair_size;
 761   h->elts = 0;
 762
 763   /* Default flags to never shrinking hash tables.
 764      Shrinking tables can cause "jackpot" cases. */
 765   if (!h_user)
 766     h->flags = HASH_FLAG_NO_AUTO_SHRINK;
 767
 768   if (!h->format_pair)
 769     {
 770       h->format_pair = hash_format_pair_default;
 771       h->format_pair_arg = 0;
 772     }
 773
 774   return v;
 775 }
 776
 777 __clib_export void *
 778 _hash_free (void *v)
 779 {
 780   hash_t *h = hash_header (v);
 781   hash_pair_union_t *p;
 782   uword i;
 783
 784   if (!v)
 785     return v;
 786
 787   /* We zero all freed memory in case user would be tempted to use it. */
 788   for (i = 0; i < hash_capacity (v); i++)
 789     {
 790       if (hash_is_user (v, i))
 791         continue;
 792       p = get_pair (v, i);
 793       if (h->log2_pair_size == 0)
 794         vec_free (p->indirect.pairs);
 795       else if (p->indirect.pairs)
 796         clib_mem_free (p->indirect.pairs);
 797     }
 798
 799   vec_free_header (h);
 800
 801   return 0;
 802 }
 803
 804 static void *
 805 hash_resize_internal (void *old, uword new_size, uword free_old)
 806 {
 807   void *new;
 808   hash_pair_t *p;
 809
 810   new = 0;
 811   if (new_size > 0)
 812     {
 813       hash_t *h = old ? hash_header (old) : 0;
 814       new = _hash_create (new_size, h);
 815       /* *INDENT-OFF* */
 816       hash_foreach_pair (p, old, {
 817         new = _hash_set3 (new, p->key, &p->value[0], 0);
 818       });
 819       /* *INDENT-ON* */
 820     }
 821
 822   if (free_old)
 823     hash_free (old);
 824   return new;
 825 }
 826
 827 void *
 828 hash_resize (void *old, uword new_size)
 829 {
 830   return hash_resize_internal (old, new_size, 1);
 831 }
 832
 833 __clib_export void *
 834 hash_dup (void *old)
 835 {
 836   return hash_resize_internal (old, vec_len (old), 0);
 837 }
 838
 839 __clib_export void *
 840 _hash_set3 (void *v, uword key, void *value, void *old_value)
 841 {
 842   hash_t *h;
 843
 844   if (!v)
 845     v = hash_create (0, sizeof (uword));
 846
 847   h = hash_header (v);
 848   (void) lookup (v, key, SET, value, old_value);
 849
 850   if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
 851     {
 852       /* Resize when 3/4 full. */
 853       if (4 * (h->elts + 1) > 3 * vec_len (v))
 854         v = hash_resize (v, 2 * vec_len (v));
 855     }
 856
 857   return v;
 858 }
 859
 860 __clib_export uword
 861 vec_key_sum (hash_t * h, uword key)
 862 {
 863   void *v = uword_to_pointer (key, void *);
 864   return hash_memory (v, vec_len (v) * h->user, 0);
 865 }
 866
 867 __clib_export uword
 868 vec_key_equal (hash_t * h, uword key1, uword key2)
 869 {
 870   void *v1 = uword_to_pointer (key1, void *);
 871   void *v2 = uword_to_pointer (key2, void *);
 872   uword l1 = vec_len (v1);
 873   uword l2 = vec_len (v2);
 874   return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
 875 }
 876
 877 __clib_export u8 *
 878 vec_key_format_pair (u8 * s, va_list * args)
 879 {
 880   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 881   void *v = va_arg (*args, void *);
 882   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 883   hash_t *h = hash_header (v);
 884   void *u = uword_to_pointer (p->key, void *);
 885   int i;
 886
 887   switch (h->user)
 888     {
 889     case 1:
 890       s = format (s, "%v", u);
 891       break;
 892
 893     case 2:
 894       {
 895         u16 *w = u;
 896         for (i = 0; i < vec_len (w); i++)
 897           s = format (s, "0x%x, ", w[i]);
 898         break;
 899       }
 900
 901     case 4:
 902       {
 903         u32 *w = u;
 904         for (i = 0; i < vec_len (w); i++)
 905           s = format (s, "0x%x, ", w[i]);
 906         break;
 907       }
 908
 909     case 8:
 910       {
 911         u64 *w = u;
 912         for (i = 0; i < vec_len (w); i++)
 913           s = format (s, "0x%Lx, ", w[i]);
 914         break;
 915       }
 916
 917     default:
 918       s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
 919       break;
 920     }
 921
 922   if (hash_value_bytes (h) > 0)
 923     s = format (s, " -> 0x%wx", p->value[0]);
 924
 925   return s;
 926 }
 927
 928 __clib_export uword
 929 mem_key_sum (hash_t * h, uword key)
 930 {
 931   uword *v = uword_to_pointer (key, void *);
 932   return hash_memory (v, h->user, 0);
 933 }
 934
 935 __clib_export uword
 936 mem_key_equal (hash_t * h, uword key1, uword key2)
 937 {
 938   void *v1 = uword_to_pointer (key1, void *);
 939   void *v2 = uword_to_pointer (key2, void *);
 940   return v1 && v2 && 0 == memcmp (v1, v2, h->user);
 941 }
 942
 943 uword
 944 string_key_sum (hash_t * h, uword key)
 945 {
 946   char *v = uword_to_pointer (key, char *);
 947   return hash_memory (v, strlen (v), 0);
 948 }
 949
 950 uword
 951 string_key_equal (hash_t * h, uword key1, uword key2)
 952 {
 953   void *v1 = uword_to_pointer (key1, void *);
 954   void *v2 = uword_to_pointer (key2, void *);
 955   return v1 && v2 && 0 == strcmp (v1, v2);
 956 }
 957
 958 u8 *
 959 string_key_format_pair (u8 * s, va_list * args)
 960 {
 961   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 962   void *v = va_arg (*args, void *);
 963   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 964   hash_t *h = hash_header (v);
 965   void *u = uword_to_pointer (p->key, void *);
 966
 967   s = format (s, "%s", u);
 968
 969   if (hash_value_bytes (h) > 0)
 970     s =
 971       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 972               hash_value_bytes (h));
 973
 974   return s;
 975 }
 976
 977 static u8 *
 978 hash_format_pair_default (u8 * s, va_list * args)
 979 {
 980   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 981   void *v = va_arg (*args, void *);
 982   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 983   hash_t *h = hash_header (v);
 984
 985   s = format (s, "0x%08x", p->key);
 986   if (hash_value_bytes (h) > 0)
 987     s =
 988       format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 989               hash_value_bytes (h));
 990   return s;
 991 }
 992
 993 __clib_export uword
 994 hash_bytes (void *v)
 995 {
 996   uword i, bytes;
 997   hash_t *h = hash_header (v);
 998
 999   if (!v)
1000     return 0;
1001
1002   bytes = vec_capacity (v, hash_header_bytes (v));
1003
1004   for (i = 0; i < hash_capacity (v); i++)
1005     {
1006       if (!hash_is_user (v, i))
1007         {
1008           hash_pair_union_t *p = get_pair (v, i);
1009           if (h->log2_pair_size > 0)
1010             bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
1011           else
1012             bytes += vec_capacity (p->indirect.pairs, 0);
1013         }
1014     }
1015   return bytes;
1016 }
1017
1018 __clib_export u8 *
1019 format_hash (u8 *s, va_list *va)
1020 {
1021   void *v = va_arg (*va, void *);
1022   int verbose = va_arg (*va, int);
1023   hash_pair_t *p;
1024   hash_t *h = hash_header (v);
1025   uword i;
1026
1027   s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
1028               v, hash_elts (v), hash_capacity (v), hash_bytes (v));
1029
1030   {
1031     uword *occupancy = 0;
1032
1033     /* Count number of buckets with each occupancy. */
1034     for (i = 0; i < hash_capacity (v); i++)
1035       {
1036         uword j;
1037
1038         if (hash_is_user (v, i))
1039           {
1040             j = 1;
1041           }
1042         else
1043           {
1044             hash_pair_union_t *p = get_pair (v, i);
1045             if (h->log2_pair_size > 0)
1046               j = indirect_pair_get_len (&p->indirect);
1047             else
1048               j = vec_len (p->indirect.pairs);
1049           }
1050
1051         vec_validate (occupancy, j);
1052         occupancy[j]++;
1053       }
1054
1055     s = format (s, "  profile ");
1056     for (i = 0; i < vec_len (occupancy); i++)
1057       s = format (s, "%wd%c", occupancy[i],
1058                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
1059
1060     s = format (s, "  lookup # of compares: ");
1061     for (i = 1; i < vec_len (occupancy); i++)
1062       s = format (s, "%wd: .%03d%c", i,
1063                   (1000 * i * occupancy[i]) / hash_elts (v),
1064                   i + 1 == vec_len (occupancy) ? '\n' : ' ');
1065
1066     vec_free (occupancy);
1067   }
1068
1069   if (verbose)
1070     {
1071       /* *INDENT-OFF* */
1072       hash_foreach_pair (p, v, {
1073         s = format (s, "  %U\n", h->format_pair, h->format_pair_arg, v, p);
1074       });
1075       /* *INDENT-ON* */
1076     }
1077
1078   return s;
1079 }
1080
1081 static uword
1082 unformat_hash_string_internal (unformat_input_t * input,
1083                                va_list * va, int is_vec)
1084 {
1085   uword *hash = va_arg (*va, uword *);
1086   int *result = va_arg (*va, int *);
1087   u8 *string = 0;
1088   uword *p;
1089
1090   if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
1091     return 0;
1092
1093   p = hash_get_mem (hash, string);
1094   if (p)
1095     *result = *p;
1096
1097   vec_free (string);
1098   return p ? 1 : 0;
1099 }
1100
1101 __clib_export uword
1102 unformat_hash_vec_string (unformat_input_t * input, va_list * va)
1103 {
1104   return unformat_hash_string_internal (input, va, /* is_vec */ 1);
1105 }
1106
1107 __clib_export uword
1108 unformat_hash_string (unformat_input_t * input, va_list * va)
1109 {
1110   return unformat_hash_string_internal (input, va, /* is_vec */ 0);
1111 }
1112
1113 __clib_export clib_error_t *
1114 hash_validate (void *v)
1115 {
1116   hash_t *h = hash_header (v);
1117   uword i, j;
1118   uword *keys = 0;
1119   clib_error_t *error = 0;
1120
1121 #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
1122
1123   for (i = 0; i < hash_capacity (v); i++)
1124     {
1125       hash_pair_union_t *pu = get_pair (v, i);
1126
1127       if (hash_is_user (v, i))
1128         {
1129           CHECK (pu->direct.key != 0);
1130           vec_add1 (keys, pu->direct.key);
1131         }
1132       else
1133         {
1134           hash_pair_t *p;
1135           hash_pair_indirect_t *pi = &pu->indirect;
1136           uword n;
1137
1138           n = h->log2_pair_size > 0
1139             ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
1140
1141           for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
1142             {
1143               /* Assert key uniqueness. */
1144               for (j = 0; j < vec_len (keys); j++)
1145                 CHECK (keys[j] != p->key);
1146               vec_add1 (keys, p->key);
1147             }
1148         }
1149     }
1150
1151   CHECK (vec_len (keys) == h->elts);
1152
1153   vec_free (keys);
1154 done:
1155   return error;
1156 }
1157
1158 /*
1159  * fd.io coding-style-patch-verification: ON
1160  *
1161  * Local Variables:
1162  * eval: (c-set-style "gnu")
1163  * End:
1164  */