2 Copyright (c) 2013 Cisco and/or its affiliates.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <vppinfra/pfhash.h>
18 #include <vppinfra/format.h>
20 /* This is incredibly handy when debugging */
21 u32 vl (void *v) __attribute__ ((weak));
22 u32 vl (void *v) { return vec_len(v); }
24 #if defined(CLIB_HAVE_VEC128) && ! defined (__ALTIVEC__)
31 static int sh_compare (pfhash_show_t * sh0, pfhash_show_t * sh1)
32 { return ((i32)(sh0->value) - ((i32)sh1->value)); }
34 u8 * format_pfhash (u8 * s, va_list * args)
36 pfhash_t * p = va_arg (*args, pfhash_t *);
37 int verbose = va_arg (*args, int);
39 if (p == 0 || p->overflow_hash == 0 || p->buckets == 0)
41 s = format (s, "*** uninitialized ***");
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)));
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));
56 pfhash_show_t * shs = 0, * sh;
60 for (i = 0; i < vec_len (p->buckets); i++)
63 pfhash_kv_16_t * kv16;
65 pfhash_kv_8v8_t * kv8v8;
68 if (p->buckets[i] == 0 || p->buckets[i] == PFHASH_BUCKET_OVERFLOW)
71 kv = pool_elt_at_index (p->kvp, p->buckets[i]);
77 for (j = 0; j < 3; j++)
79 if (kv16->values[j] != (u32)~0)
81 vec_add2 (shs, sh, 1);
82 clib_memcpy (sh->key, &kv16->kb.k_u32x4[j], p->key_size);
83 sh->value = kv16->values[j];
88 if (p->value_size == 4)
91 for (j = 0; j < 5; j++)
93 if (kv8->values[j] != (u32)~0)
95 vec_add2 (shs, sh, 1);
96 clib_memcpy (sh->key, &kv8->kb.k_u64[j], p->key_size);
97 sh->value = kv8->values[j];
104 for (j = 0; j < 4; j++)
106 if (kv8v8->values[j] != (u64)~0)
108 vec_add2 (shs, sh, 1);
109 clib_memcpy (sh->key, &kv8v8->kb.k_u64[j], p->key_size);
110 sh->value = kv8v8->values[j];
118 for (j = 0; j < 8; j++)
120 if (kv4->values[j] != (u32)~0)
122 vec_add2 (shs, sh, 1);
123 clib_memcpy (sh->key, &kv4->kb.kb[j], p->key_size);
124 sh->value = kv4->values[j];
131 hash_foreach_pair (hp, p->overflow_hash,
133 vec_add2 (shs, sh, 1);
134 clib_memcpy (sh->key, (u8 *)hp->key, p->key_size);
135 sh->value = hp->value[0];
138 vec_sort_with_function (shs, sh_compare);
140 for (i = 0; i < vec_len (shs); i++)
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);
154 void pfhash_init (pfhash_t * p, char * name, u32 key_size, u32 value_size,
158 memset (p, 0, sizeof (*p));
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));
192 nbuckets = 1 << (max_log2 (nbuckets));
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;
200 * Unset buckets implicitly point at the 0th pool elt.
201 * All search routines will return ~0 if they go there.
203 pool_get_aligned (p->kvp, kv, 16);
204 memset (kv, 0xff, sizeof (*kv));
207 static pfhash_kv_16_t * pfhash_get_kv_16 (pfhash_t * p, u32 bucket_contents,
208 u32x4 * key, u32 *match_index)
212 pfhash_kv_16_t *kv = 0;
214 *match_index = (u32)~0;
216 kv = &p->kvp[bucket_contents].kv16;
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]);
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;
236 static pfhash_kv_8_t * pfhash_get_kv_8 (pfhash_t * p, u32 bucket_contents,
237 u64 * key, u32 * match_index)
241 *match_index = (u32)~0;
243 kv = &p->kvp[bucket_contents].kv8;
245 if (kv->kb.k_u64[0] == key[0])
247 if (kv->kb.k_u64[1] == key[0])
249 if (kv->kb.k_u64[2] == key[0])
251 if (kv->kb.k_u64[3] == key[0])
253 if (kv->kb.k_u64[4] == key[0])
259 static pfhash_kv_8v8_t * pfhash_get_kv_8v8 (pfhash_t * p,
261 u64 * key, u32 * match_index)
265 *match_index = (u32)~0;
267 kv = &p->kvp[bucket_contents].kv8v8;
269 if (kv->kb.k_u64[0] == key[0])
271 if (kv->kb.k_u64[1] == key[0])
273 if (kv->kb.k_u64[2] == key[0])
275 if (kv->kb.k_u64[3] == key[0])
281 static pfhash_kv_4_t * pfhash_get_kv_4 (pfhash_t * p, u32 bucket_contents,
282 u32 * key, u32 * match_index)
286 u32 zbm[2], winner_index;
289 *match_index = (u32)~0;
291 kv = &p->kvp[bucket_contents].kv4;
293 vector_key = u32x4_splat (key[0]);
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;
300 if (PREDICT_FALSE((zbm[0] == 0) &&(zbm[1] == 0)))
303 winner_index = min_log2 (zbm[0])>>2;
304 winner_index = zbm[1] ? (4 + (min_log2 (zbm[1])>>2)) : winner_index;
306 *match_index = winner_index;
310 static pfhash_kv_t * pfhash_get_internal (pfhash_t * p, u32 bucket_contents,
311 void * key, u32 *match_index)
318 kv = (pfhash_kv_t *) pfhash_get_kv_16 (p, bucket_contents, key, match_index);
321 if (p->value_size == 4)
322 kv = (pfhash_kv_t *) pfhash_get_kv_8 (p, bucket_contents,
325 kv = (pfhash_kv_t *) pfhash_get_kv_8v8 (p, bucket_contents,
329 kv = (pfhash_kv_t *) pfhash_get_kv_4 (p, bucket_contents, key, match_index);
337 u64 pfhash_get (pfhash_t * p, u32 bucket, void * key)
341 pfhash_kv_16_t * kv16;
343 pfhash_kv_8v8_t * kv8v8;
346 u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
348 if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
352 hp = hash_get_mem (p->overflow_hash, key);
358 kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
359 if (match_index == (u32)~0)
370 return (kv16->values[match_index] == (u32)~0)
371 ? (u64)~0 : (u64) kv16->values[match_index];
373 if (p->value_size == 4)
374 return (kv8->values[match_index] == (u32)~0)
375 ? (u64)~0 : (u64) kv8->values[match_index];
377 return kv8v8->values[match_index];
379 return (kv4->values[match_index] == (u32)~0)
380 ? (u64)~0 : (u64) kv4->values[match_index];
387 void pfhash_set (pfhash_t * p, u32 bucket, void * key, void * value)
389 u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
390 u32 match_index = (u32)~0;
392 pfhash_kv_16_t * kv16;
394 pfhash_kv_8v8_t * kv8v8;
399 if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
402 hp = hash_get_pair_mem (p->overflow_hash, key);
405 clib_warning ("replace value 0x%08x with value 0x%08x",
406 hp->value[0], (u64) value);
407 hp->value[0] = (u64) value;
410 kcopy = clib_mem_alloc (p->key_size);
411 clib_memcpy (kcopy, key, p->key_size);
412 hash_set_mem (p->overflow_hash, kcopy, value);
414 p->nitems_in_overflow++;
418 if (bucket_contents == 0)
420 pool_get_aligned (p->kvp, kv, 16);
421 memset (kv, 0xff, sizeof (*kv));
422 p->buckets[bucket] = kv - p->kvp;
425 kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
434 if (match_index != (u32)~0)
439 kv16->values[match_index] = (u32)(u64) value;
443 if (p->value_size == 4)
444 kv8->values[match_index] = (u32)(u64) value;
446 kv8v8->values[match_index] = (u64) value;
450 kv4->values[match_index] = (u64) value;
461 for (i = 0; i < 3; i++)
463 if (kv16->values[i] == (u32)~0)
465 clib_memcpy (&kv16->kb.k_u32x4[i], key, p->key_size);
466 kv16->values[i] = (u32)(u64) value;
470 /* copy bucket contents to overflow hash tbl */
471 for (i = 0; i < 3; i++)
473 kcopy = clib_mem_alloc (p->key_size);
474 clib_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++;
478 /* Add new key to overflow */
479 kcopy = clib_mem_alloc (p->key_size);
480 clib_memcpy (kcopy, key, p->key_size);
481 hash_set_mem (p->overflow_hash, kcopy, value);
482 p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW;
484 p->nitems_in_overflow++;
488 if (p->value_size == 4)
490 for (i = 0; i < 5; i++)
492 if (kv8->values[i] == (u32)~0)
494 clib_memcpy (&kv8->kb.k_u64[i], key, 8);
495 kv8->values[i] = (u32)(u64) value;
499 /* copy bucket contents to overflow hash tbl */
500 for (i = 0; i < 5; i++)
502 kcopy = clib_mem_alloc (p->key_size);
503 clib_memcpy (kcopy, &kv8->kb.k_u64[i], 8);
504 hash_set_mem (p->overflow_hash, kcopy, kv8->values[i]);
505 p->nitems_in_overflow++;
510 for (i = 0; i < 4; i++)
512 if (kv8v8->values[i] == (u64)~0)
514 clib_memcpy (&kv8v8->kb.k_u64[i], key, 8);
515 kv8v8->values[i] = (u64) value;
519 /* copy bucket contents to overflow hash tbl */
520 for (i = 0; i < 4; i++)
522 kcopy = clib_mem_alloc (p->key_size);
523 clib_memcpy (kcopy, &kv8v8->kb.k_u64[i], 8);
524 hash_set_mem (p->overflow_hash, kcopy, kv8v8->values[i]);
525 p->nitems_in_overflow++;
529 /* Add new key to overflow */
530 kcopy = clib_mem_alloc (p->key_size);
531 clib_memcpy (kcopy, key, p->key_size);
532 hash_set_mem (p->overflow_hash, kcopy, value);
533 p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW;
535 p->nitems_in_overflow++;
539 for (i = 0; i < 8; i++)
541 if (kv4->values[i] == (u32)~0)
543 clib_memcpy (&kv4->kb.kb[i], key, 4);
544 kv4->values[i] = (u32)(u64) value;
548 /* copy bucket contents to overflow hash tbl */
549 for (i = 0; i < 8; i++)
551 kcopy = clib_mem_alloc (p->key_size);
552 clib_memcpy (kcopy, &kv4->kb.kb[i], 4);
553 hash_set_mem (p->overflow_hash, kcopy, kv4->values[i]);
554 p->nitems_in_overflow++;
556 /* Add new key to overflow */
557 kcopy = clib_mem_alloc (p->key_size);
558 clib_memcpy (kcopy, key, p->key_size);
559 hash_set_mem (p->overflow_hash, kcopy, value);
560 p->buckets[bucket] = PFHASH_BUCKET_OVERFLOW;
562 p->nitems_in_overflow++;
570 void pfhash_unset (pfhash_t * p, u32 bucket, void * key)
572 u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
573 u32 match_index = (u32)~0;
575 pfhash_kv_16_t * kv16;
577 pfhash_kv_8v8_t * kv8v8;
581 if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
584 hp = hash_get_pair_mem (p->overflow_hash, key);
587 oldkey = (void *) hp->key;
588 hash_unset_mem (p->overflow_hash, key);
589 clib_mem_free (oldkey);
591 p->nitems_in_overflow--;
596 kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
597 if (match_index == (u32)~0)
610 kv16->values[match_index] = (u32)~0;
614 if (p->value_size == 4)
615 kv8->values[match_index] = (u32)~0;
617 kv8v8->values[match_index] = (u64)~0;
621 kv4->values[match_index] = (u32)~0;
629 void pfhash_free (pfhash_t * p)
639 hash_foreach_pair (hp, p->overflow_hash,
641 vec_add1 (keys, (u8 *)hp->key);
643 hash_free (p->overflow_hash);
644 for (i = 0; i < vec_len (keys); i++)