src/vppinfra/pfhash.c

   1 /*
   2   Copyright (c) 2013 Cisco and/or its affiliates.
   3
   4   * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15 */
  16
  17 #include <vppinfra/pfhash.h>
  18 #include <vppinfra/format.h>
  19
  20 /* This is incredibly handy when debugging */
  21 u32 vl (void *v) __attribute__ ((weak));
  22 u32
  23 vl (void *v)
  24 {
  25   return vec_len (v);
  26 }
  27
  28 #if defined(CLIB_HAVE_VEC128) && ! defined (__ALTIVEC__)
  29
  30 typedef struct
  31 {
  32   u8 *key[16];
  33   u64 value;
  34 } pfhash_show_t;
  35
  36 static int
  37 sh_compare (pfhash_show_t * sh0, pfhash_show_t * sh1)
  38 {
  39   return ((i32) (sh0->value) - ((i32) sh1->value));
  40 }
  41
  42 u8 *
  43 format_pfhash (u8 * s, va_list * args)
  44 {
  45   pfhash_t *p = va_arg (*args, pfhash_t *);
  46   int verbose = va_arg (*args, int);
  47
  48   if (p == 0 || p->overflow_hash == 0 || p->buckets == 0)
  49     {
  50       s = format (s, "*** uninitialized ***");
  51       return s;
  52     }
  53
  54   s = format (s, "Prefetch hash '%s'\n", p->name);
  55   s =
  56     format (s, " %d buckets, %u bucket overflows, %.1f%% bucket overflow \n",
  57             vec_len (p->buckets), p->overflow_count,
  58             100.0 * ((f64) p->overflow_count) / ((f64) vec_len (p->buckets)));
  59   if (p->nitems)
  60     s =
  61       format (s,
  62               "  %u items, %u items in overflow, %.1f%% items in overflow\n",
  63               p->nitems, p->nitems_in_overflow,
  64               100.0 * ((f64) p->nitems_in_overflow) / ((f64) p->nitems));
  65
  66   if (verbose)
  67     {
  68       pfhash_show_t *shs = 0, *sh;
  69       hash_pair_t *hp;
  70       int i, j;
  71
  72       for (i = 0; i < vec_len (p->buckets); i++)
  73         {
  74           pfhash_kv_t *kv;
  75           pfhash_kv_16_t *kv16;
  76           pfhash_kv_8_t *kv8;
  77           pfhash_kv_8v8_t *kv8v8;
  78           pfhash_kv_4_t *kv4;
  79
  80           if (p->buckets[i] == 0 || p->buckets[i] == PFHASH_BUCKET_OVERFLOW)
  81             continue;
  82
  83           kv = pool_elt_at_index (p->kvp, p->buckets[i]);
  84
  85           switch (p->key_size)
  86             {
  87             case 16:
  88               kv16 = &kv->kv16;
  89               for (j = 0; j < 3; j++)
  90                 {
  91                   if (kv16->values[j] != (u32) ~ 0)
  92                     {
  93                       vec_add2 (shs, sh, 1);
  94                       clib_memcpy (sh->key, &kv16->kb.k_u32x4[j],
  95                                    p->key_size);
  96                       sh->value = kv16->values[j];
  97                     }
  98                 }
  99               break;
 100             case 8:
 101               if (p->value_size == 4)
 102                 {
 103                   kv8 = &kv->kv8;
 104                   for (j = 0; j < 5; j++)
 105                     {
 106                       if (kv8->values[j] != (u32) ~ 0)
 107                         {
 108                           vec_add2 (shs, sh, 1);
 109                           clib_memcpy (sh->key, &kv8->kb.k_u64[j],
 110                                        p->key_size);
 111                           sh->value = kv8->values[j];
 112                         }
 113                     }
 114                 }
 115               else
 116                 {
 117                   kv8v8 = &kv->kv8v8;
 118                   for (j = 0; j < 4; j++)
 119                     {
 120                       if (kv8v8->values[j] != (u64) ~ 0)
 121                         {
 122                           vec_add2 (shs, sh, 1);
 123                           clib_memcpy (sh->key, &kv8v8->kb.k_u64[j],
 124                                        p->key_size);
 125                           sh->value = kv8v8->values[j];
 126                         }
 127                     }
 128
 129                 }
 130               break;
 131             case 4:
 132               kv4 = &kv->kv4;
 133               for (j = 0; j < 8; j++)
 134                 {
 135                   if (kv4->values[j] != (u32) ~ 0)
 136                     {
 137                       vec_add2 (shs, sh, 1);
 138                       clib_memcpy (sh->key, &kv4->kb.kb[j], p->key_size);
 139                       sh->value = kv4->values[j];
 140                     }
 141                 }
 142               break;
 143             }
 144         }
 145
 146       /* *INDENT-OFF* */
 147       hash_foreach_pair (hp, p->overflow_hash,
 148       ({
 149         vec_add2 (shs, sh, 1);
 150         clib_memcpy (sh->key, (u8 *)hp->key, p->key_size);
 151         sh->value = hp->value[0];
 152       }));
 153       /* *INDENT-ON* */
 154
 155       vec_sort_with_function (shs, sh_compare);
 156
 157       for (i = 0; i < vec_len (shs); i++)
 158         {
 159           sh = vec_elt_at_index (shs, i);
 160           s = format (s, " %U value %u\n", format_hex_bytes, sh->key,
 161                       p->key_size, sh->value);
 162         }
 163       vec_free (shs);
 164     }
 165   return s;
 166 }
 167
 168
 169 void abort (void);
 170
 171 void
 172 pfhash_init (pfhash_t * p, char *name, u32 key_size, u32 value_size,
 173              u32 nbuckets)
 174 {
 175   pfhash_kv_t *kv;
 176   memset (p, 0, sizeof (*p));
 177   u32 key_bytes;
 178
 179   switch (key_size)
 180     {
 181     case 4:
 182       key_bytes = 4;
 183       break;
 184     case 8:
 185       key_bytes = 8;
 186       break;
 187     case 16:
 188       key_bytes = 16;
 189       break;
 190     default:
 191       ASSERT (0);
 192       abort ();
 193     }
 194
 195   switch (value_size)
 196     {
 197     case 4:
 198     case 8:
 199       break;
 200     default:
 201       ASSERT (0);
 202       abort ();
 203     }
 204
 205
 206   p->name = format (0, "%s", name);
 207   vec_add1 (p->name, 0);
 208   p->overflow_hash = hash_create_mem (0, key_bytes, sizeof (uword));
 209
 210   nbuckets = 1 << (max_log2 (nbuckets));
 211
 212   /* This sets the entire bucket array to zero */
 213   vec_validate (p->buckets, nbuckets - 1);
 214   p->key_size = key_size;
 215   p->value_size = value_size;
 216
 217   /*
 218    * Unset buckets implicitly point at the 0th pool elt.
 219    * All search routines will return ~0 if they go there.
 220    */
 221   pool_get_aligned (p->kvp, kv, 16);
 222   memset (kv, 0xff, sizeof (*kv));
 223 }
 224
 225 static pfhash_kv_16_t *
 226 pfhash_get_kv_16 (pfhash_t * p, u32 bucket_contents,
 227                   u32x4 * key, u32 * match_index)
 228 {
 229   u32x4 diff[3];
 230   u32 is_equal[3];
 231   pfhash_kv_16_t *kv = 0;
 232
 233   *match_index = (u32) ~ 0;
 234
 235   kv = &p->kvp[bucket_contents].kv16;
 236
 237   diff[0] = u32x4_sub (kv->kb.k_u32x4[0], key[0]);
 238   diff[1] = u32x4_sub (kv->kb.k_u32x4[1], key[0]);
 239   diff[2] = u32x4_sub (kv->kb.k_u32x4[2], key[0]);
 240
 241   is_equal[0] = u32x4_zero_byte_mask (diff[0]) == 0xffff;
 242   is_equal[1] = u32x4_zero_byte_mask (diff[1]) == 0xffff;
 243   is_equal[2] = u32x4_zero_byte_mask (diff[2]) == 0xffff;
 244
 245   if (is_equal[0])
 246     *match_index = 0;
 247   if (is_equal[1])
 248     *match_index = 1;
 249   if (is_equal[2])
 250     *match_index = 2;
 251
 252   return kv;
 253 }
 254
 255 static pfhash_kv_8_t *
 256 pfhash_get_kv_8 (pfhash_t * p, u32 bucket_contents,
 257                  u64 * key, u32 * match_index)
 258 {
 259   pfhash_kv_8_t *kv;
 260
 261   *match_index = (u32) ~ 0;
 262
 263   kv = &p->kvp[bucket_contents].kv8;
 264
 265   if (kv->kb.k_u64[0] == key[0])
 266     *match_index = 0;
 267   if (kv->kb.k_u64[1] == key[0])
 268     *match_index = 1;
 269   if (kv->kb.k_u64[2] == key[0])
 270     *match_index = 2;
 271   if (kv->kb.k_u64[3] == key[0])
 272     *match_index = 3;
 273   if (kv->kb.k_u64[4] == key[0])
 274     *match_index = 4;
 275
 276   return kv;
 277 }
 278
 279 static pfhash_kv_8v8_t *
 280 pfhash_get_kv_8v8 (pfhash_t * p,
 281                    u32 bucket_contents, u64 * key, u32 * match_index)
 282 {
 283   pfhash_kv_8v8_t *kv;
 284
 285   *match_index = (u32) ~ 0;
 286
 287   kv = &p->kvp[bucket_contents].kv8v8;
 288
 289   if (kv->kb.k_u64[0] == key[0])
 290     *match_index = 0;
 291   if (kv->kb.k_u64[1] == key[0])
 292     *match_index = 1;
 293   if (kv->kb.k_u64[2] == key[0])
 294     *match_index = 2;
 295   if (kv->kb.k_u64[3] == key[0])
 296     *match_index = 3;
 297
 298   return kv;
 299 }
 300
 301 static pfhash_kv_4_t *
 302 pfhash_get_kv_4 (pfhash_t * p, u32 bucket_contents,
 303                  u32 * key, u32 * match_index)
 304 {
 305   u32x4 vector_key;
 306   u32x4 is_equal[2];
 307   u32 zbm[2], winner_index;
 308   pfhash_kv_4_t *kv;
 309
 310   *match_index = (u32) ~ 0;
 311
 312   kv = &p->kvp[bucket_contents].kv4;
 313
 314   vector_key = u32x4_splat (key[0]);
 315
 316   is_equal[0] = u32x4_is_equal (kv->kb.k_u32x4[0], vector_key);
 317   is_equal[1] = u32x4_is_equal (kv->kb.k_u32x4[1], vector_key);
 318   zbm[0] = ~u32x4_zero_byte_mask (is_equal[0]) & 0xFFFF;
 319   zbm[1] = ~u32x4_zero_byte_mask (is_equal[1]) & 0xFFFF;
 320
 321   if (PREDICT_FALSE ((zbm[0] == 0) && (zbm[1] == 0)))
 322     return kv;
 323
 324   winner_index = min_log2 (zbm[0]) >> 2;
 325   winner_index = zbm[1] ? (4 + (min_log2 (zbm[1]) >> 2)) : winner_index;
 326
 327   *match_index = winner_index;
 328   return kv;
 329 }
 330
 331 static pfhash_kv_t *
 332 pfhash_get_internal (pfhash_t * p, u32 bucket_contents,
 333                      void *key, u32 * match_index)
 334 {
 335   pfhash_kv_t *kv = 0;
 336
 337   switch (p->key_size)
 338     {
 339     case 16:
 340       kv =
 341         (pfhash_kv_t *) pfhash_get_kv_16 (p, bucket_contents, key,
 342                                           match_index);
 343       break;
 344     case 8:
 345       if (p->value_size == 4)
 346         kv = (pfhash_kv_t *) pfhash_get_kv_8 (p, bucket_contents,
 347                                               key, match_index);
 348       else
 349         kv = (pfhash_kv_t *) pfhash_get_kv_8v8 (p, bucket_contents,
 350                                                 key, match_index);
 351       break;
 352     case 4:
 353       kv =
 354         (pfhash_kv_t *) pfhash_get_kv_4 (p, bucket_contents, key,
 355                                          match_index);
 356       break;
 357     default:
 358       ASSERT (0);
 359     }
 360   return kv;
 361 }
 362
 363 u64
 364 pfhash_get (pfhash_t * p, u32 bucket, void *key)
 365 {
 366   pfhash_kv_t *kv;
 367   u32 match_index = ~0;
 368   pfhash_kv_16_t *kv16;
 369   pfhash_kv_8_t *kv8;
 370   pfhash_kv_8v8_t *kv8v8;
 371   pfhash_kv_4_t *kv4;
 372
 373   u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
 374
 375   if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
 376     {
 377       uword *hp;
 378
 379       hp = hash_get_mem (p->overflow_hash, key);
 380       if (hp)
 381         return hp[0];
 382       return (u64) ~ 0;
 383     }
 384
 385   kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
 386   if (match_index == (u32) ~ 0)
 387     return (u64) ~ 0;
 388
 389   kv16 = (void *) kv;
 390   kv8 = (void *) kv;
 391   kv4 = (void *) kv;
 392   kv8v8 = (void *) kv;
 393
 394   switch (p->key_size)
 395     {
 396     case 16:
 397       return (kv16->values[match_index] == (u32) ~ 0)
 398         ? (u64) ~ 0 : (u64) kv16->values[match_index];
 399     case 8:
 400       if (p->value_size == 4)
 401         return (kv8->values[match_index] == (u32) ~ 0)
 402           ? (u64) ~ 0 : (u64) kv8->values[match_index];
 403       else
 404         return kv8v8->values[match_index];
 405     case 4:
 406       return (kv4->values[match_index] == (u32) ~ 0)
 407         ? (u64) ~ 0 : (u64) kv4->values[match_index];
 408     default:
 409       ASSERT (0);
 410     }
 411   return (u64) ~ 0;
 412 }
 413
 414 void
 415 pfhash_set (pfhash_t * p, u32 bucket, void *key, void *value)
 416 {
 417   u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
 418   u32 match_index = (u32) ~ 0;
 419   pfhash_kv_t *kv;
 420   pfhash_kv_16_t *kv16;
 421   pfhash_kv_8_t *kv8;
 422   pfhash_kv_8v8_t *kv8v8;
 423   pfhash_kv_4_t *kv4;
 424   int i;
 425   u8 *kcopy;
 426
 427   if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
 428     {
 429       hash_pair_t *hp;
 430       hp = hash_get_pair_mem (p->overflow_hash, key);
 431       if (hp)
 432         {
 433           clib_warning ("replace value 0x%08x with value 0x%08x",
 434                         hp->value[0], (u64) value);
 435           hp->value[0] = (u64) value;
 436           return;
 437         }
 438       kcopy = clib_mem_alloc (p->key_size);
 439       clib_memcpy (kcopy, key, p->key_size);
 440       hash_set_mem (p->overflow_hash, kcopy, value);
 441       p->nitems++;
 442       p->nitems_in_overflow++;
 443       return;
 444     }
 445
 446   if (bucket_contents == 0)
 447     {
 448       pool_get_aligned (p->kvp, kv, 16);
 449       memset (kv, 0xff, sizeof (*kv));
 450       p->buckets[bucket] = kv - p->kvp;
 451     }
 452   else
 453     kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
 454
 455   kv16 = (void *) kv;
 456   kv8 = (void *) kv;
 457   kv8v8 = (void *) kv;
 458   kv4 = (void *) kv;
 459
 460   p->nitems++;
 461
 462   if (match_index != (u32) ~ 0)
 463     {
 464       switch (p->key_size)
 465         {
 466         case 16:
 467           kv16->values[match_index] = (u32) (u64) value;
 468           return;
 469
 470         case 8:
 471           if (p->value_size == 4)
 472             kv8->values[match_index] = (u32) (u64) value;
 473           else
 474             kv8v8->values[match_index] = (u64) value;
 475           return;
 476
 477         case 4:
 478           kv4->values[match_index] = (u64) value;
 479           return;
 480
 481         default:
 482           ASSERT (0);
 483         }
 484     }
 485
 486   switch (p->key_size)
 487     {
 488     case 16:
 489       for (i = 0; i < 3; i++)
 490         {
 491           if (kv16->values[i] == (u32) ~ 0)
 492             {
 493               clib_memcpy (&kv16->kb.k_u32x4[i], key, p->key_size);
 494               kv16->values[i] = (u32) (u64) value;
 495               return;
 496             }
 497         }
 498       /* copy bucket contents to overflow hash tbl */
 499       for (i = 0; i < 3; i++)
 500         {
 501           kcopy = clib_mem_alloc (p->key_size);
 502           clib_memcpy (kcopy, &kv16->kb.k_u32x4[i], p->key_size);
 503           hash_set_mem (p->overflow_hash, kcopy, kv16->values[i]);
 504           p->nitems_in_overflow++;
 505         }
 506       /* Add new key to overflow */
 507       kcopy = clib_mem_alloc (p->key_size);
 508       clib_memcpy (kcopy, key, p->key_size);
 509       hash_set_mem (p->overflow_hash, kcopy, value);
 510       p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW;
 511       p->overflow_count++;
 512       p->nitems_in_overflow++;
 513       return;
 514
 515     case 8:
 516       if (p->value_size == 4)
 517         {
 518           for (i = 0; i < 5; i++)
 519             {
 520               if (kv8->values[i] == (u32) ~ 0)
 521                 {
 522                   clib_memcpy (&kv8->kb.k_u64[i], key, 8);
 523                   kv8->values[i] = (u32) (u64) value;
 524                   return;
 525                 }
 526             }
 527           /* copy bucket contents to overflow hash tbl */
 528           for (i = 0; i < 5; i++)
 529             {
 530               kcopy = clib_mem_alloc (p->key_size);
 531               clib_memcpy (kcopy, &kv8->kb.k_u64[i], 8);
 532               hash_set_mem (p->overflow_hash, kcopy, kv8->values[i]);
 533               p->nitems_in_overflow++;
 534             }
 535         }
 536       else
 537         {
 538           for (i = 0; i < 4; i++)
 539             {
 540               if (kv8v8->values[i] == (u64) ~ 0)
 541                 {
 542                   clib_memcpy (&kv8v8->kb.k_u64[i], key, 8);
 543                   kv8v8->values[i] = (u64) value;
 544                   return;
 545                 }
 546             }
 547           /* copy bucket contents to overflow hash tbl */
 548           for (i = 0; i < 4; i++)
 549             {
 550               kcopy = clib_mem_alloc (p->key_size);
 551               clib_memcpy (kcopy, &kv8v8->kb.k_u64[i], 8);
 552               hash_set_mem (p->overflow_hash, kcopy, kv8v8->values[i]);
 553               p->nitems_in_overflow++;
 554             }
 555
 556         }
 557       /* Add new key to overflow */
 558       kcopy = clib_mem_alloc (p->key_size);
 559       clib_memcpy (kcopy, key, p->key_size);
 560       hash_set_mem (p->overflow_hash, kcopy, value);
 561       p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW;
 562       p->overflow_count++;
 563       p->nitems_in_overflow++;
 564       return;
 565
 566     case 4:
 567       for (i = 0; i < 8; i++)
 568         {
 569           if (kv4->values[i] == (u32) ~ 0)
 570             {
 571               clib_memcpy (&kv4->kb.kb[i], key, 4);
 572               kv4->values[i] = (u32) (u64) value;
 573               return;
 574             }
 575         }
 576       /* copy bucket contents to overflow hash tbl */
 577       for (i = 0; i < 8; i++)
 578         {
 579           kcopy = clib_mem_alloc (p->key_size);
 580           clib_memcpy (kcopy, &kv4->kb.kb[i], 4);
 581           hash_set_mem (p->overflow_hash, kcopy, kv4->values[i]);
 582           p->nitems_in_overflow++;
 583         }
 584       /* Add new key to overflow */
 585       kcopy = clib_mem_alloc (p->key_size);
 586       clib_memcpy (kcopy, key, p->key_size);
 587       hash_set_mem (p->overflow_hash, kcopy, value);
 588       p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW;
 589       p->overflow_count++;
 590       p->nitems_in_overflow++;
 591       return;
 592
 593     default:
 594       ASSERT (0);
 595     }
 596 }
 597
 598 void
 599 pfhash_unset (pfhash_t * p, u32 bucket, void *key)
 600 {
 601   u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
 602   u32 match_index = (u32) ~ 0;
 603   pfhash_kv_t *kv;
 604   pfhash_kv_16_t *kv16;
 605   pfhash_kv_8_t *kv8;
 606   pfhash_kv_8v8_t *kv8v8;
 607   pfhash_kv_4_t *kv4;
 608   void *oldkey;
 609
 610   if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
 611     {
 612       hash_pair_t *hp;
 613       hp = hash_get_pair_mem (p->overflow_hash, key);
 614       if (hp)
 615         {
 616           oldkey = (void *) hp->key;
 617           hash_unset_mem (p->overflow_hash, key);
 618           clib_mem_free (oldkey);
 619           p->nitems--;
 620           p->nitems_in_overflow--;
 621         }
 622       return;
 623     }
 624
 625   kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
 626   if (match_index == (u32) ~ 0)
 627     return;
 628
 629   p->nitems--;
 630
 631   kv16 = (void *) kv;
 632   kv8 = (void *) kv;
 633   kv8v8 = (void *) kv;
 634   kv4 = (void *) kv;
 635
 636   switch (p->key_size)
 637     {
 638     case 16:
 639       kv16->values[match_index] = (u32) ~ 0;
 640       return;
 641
 642     case 8:
 643       if (p->value_size == 4)
 644         kv8->values[match_index] = (u32) ~ 0;
 645       else
 646         kv8v8->values[match_index] = (u64) ~ 0;
 647       return;
 648
 649     case 4:
 650       kv4->values[match_index] = (u32) ~ 0;
 651       return;
 652
 653     default:
 654       ASSERT (0);
 655     }
 656 }
 657
 658 void
 659 pfhash_free (pfhash_t * p)
 660 {
 661   hash_pair_t *hp;
 662   int i;
 663   u8 **keys = 0;
 664
 665   vec_free (p->name);
 666
 667   pool_free (p->kvp);
 668
 669   /* *INDENT-OFF* */
 670   hash_foreach_pair (hp, p->overflow_hash,
 671   ({
 672     vec_add1 (keys, (u8 *)hp->key);
 673   }));
 674   /* *INDENT-ON* */
 675   hash_free (p->overflow_hash);
 676   for (i = 0; i < vec_len (keys); i++)
 677     vec_free (keys[i]);
 678   vec_free (keys);
 679 }
 680
 681 #endif
 682
 683 /*
 684  * fd.io coding-style-patch-verification: ON
 685  *
 686  * Local Variables:
 687  * eval: (c-set-style "gnu")
 688  * End:
 689  */