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