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