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));
28 #if defined(CLIB_HAVE_VEC128) && ! defined (__ALTIVEC__)
37 sh_compare (pfhash_show_t * sh0, pfhash_show_t * sh1)
39 return ((i32) (sh0->value) - ((i32) sh1->value));
43 format_pfhash (u8 * s, va_list * args)
45 pfhash_t *p = va_arg (*args, pfhash_t *);
46 int verbose = va_arg (*args, int);
48 if (p == 0 || p->overflow_hash == 0 || p->buckets == 0)
50 s = format (s, "*** uninitialized ***");
54 s = format (s, "Prefetch hash '%s'\n", p->name);
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)));
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));
68 pfhash_show_t *shs = 0, *sh;
72 for (i = 0; i < vec_len (p->buckets); i++)
77 pfhash_kv_8v8_t *kv8v8;
80 if (p->buckets[i] == 0 || p->buckets[i] == PFHASH_BUCKET_OVERFLOW)
83 kv = pool_elt_at_index (p->kvp, p->buckets[i]);
89 for (j = 0; j < 3; j++)
91 if (kv16->values[j] != (u32) ~ 0)
93 vec_add2 (shs, sh, 1);
94 clib_memcpy (sh->key, &kv16->kb.k_u32x4[j],
96 sh->value = kv16->values[j];
101 if (p->value_size == 4)
104 for (j = 0; j < 5; j++)
106 if (kv8->values[j] != (u32) ~ 0)
108 vec_add2 (shs, sh, 1);
109 clib_memcpy (sh->key, &kv8->kb.k_u64[j],
111 sh->value = kv8->values[j];
118 for (j = 0; j < 4; j++)
120 if (kv8v8->values[j] != (u64) ~ 0)
122 vec_add2 (shs, sh, 1);
123 clib_memcpy (sh->key, &kv8v8->kb.k_u64[j],
125 sh->value = kv8v8->values[j];
133 for (j = 0; j < 8; j++)
135 if (kv4->values[j] != (u32) ~ 0)
137 vec_add2 (shs, sh, 1);
138 clib_memcpy (sh->key, &kv4->kb.kb[j], p->key_size);
139 sh->value = kv4->values[j];
147 hash_foreach_pair (hp, p->overflow_hash,
149 vec_add2 (shs, sh, 1);
150 clib_memcpy (sh->key, (u8 *)hp->key, p->key_size);
151 sh->value = hp->value[0];
155 vec_sort_with_function (shs, sh_compare);
157 for (i = 0; i < vec_len (shs); i++)
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);
172 pfhash_init (pfhash_t * p, char *name, u32 key_size, u32 value_size,
176 memset (p, 0, sizeof (*p));
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));
210 nbuckets = 1 << (max_log2 (nbuckets));
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;
218 * Unset buckets implicitly point at the 0th pool elt.
219 * All search routines will return ~0 if they go there.
221 pool_get_aligned (p->kvp, kv, 16);
222 memset (kv, 0xff, sizeof (*kv));
225 static pfhash_kv_16_t *
226 pfhash_get_kv_16 (pfhash_t * p, u32 bucket_contents,
227 u32x4 * key, u32 * match_index)
231 pfhash_kv_16_t *kv = 0;
233 *match_index = (u32) ~ 0;
235 kv = &p->kvp[bucket_contents].kv16;
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]);
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;
255 static pfhash_kv_8_t *
256 pfhash_get_kv_8 (pfhash_t * p, u32 bucket_contents,
257 u64 * key, u32 * match_index)
261 *match_index = (u32) ~ 0;
263 kv = &p->kvp[bucket_contents].kv8;
265 if (kv->kb.k_u64[0] == key[0])
267 if (kv->kb.k_u64[1] == key[0])
269 if (kv->kb.k_u64[2] == key[0])
271 if (kv->kb.k_u64[3] == key[0])
273 if (kv->kb.k_u64[4] == key[0])
279 static pfhash_kv_8v8_t *
280 pfhash_get_kv_8v8 (pfhash_t * p,
281 u32 bucket_contents, u64 * key, u32 * match_index)
285 *match_index = (u32) ~ 0;
287 kv = &p->kvp[bucket_contents].kv8v8;
289 if (kv->kb.k_u64[0] == key[0])
291 if (kv->kb.k_u64[1] == key[0])
293 if (kv->kb.k_u64[2] == key[0])
295 if (kv->kb.k_u64[3] == key[0])
301 static pfhash_kv_4_t *
302 pfhash_get_kv_4 (pfhash_t * p, u32 bucket_contents,
303 u32 * key, u32 * match_index)
307 u32 zbm[2], winner_index;
310 *match_index = (u32) ~ 0;
312 kv = &p->kvp[bucket_contents].kv4;
314 vector_key = u32x4_splat (key[0]);
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;
321 if (PREDICT_FALSE ((zbm[0] == 0) && (zbm[1] == 0)))
324 winner_index = min_log2 (zbm[0]) >> 2;
325 winner_index = zbm[1] ? (4 + (min_log2 (zbm[1]) >> 2)) : winner_index;
327 *match_index = winner_index;
332 pfhash_get_internal (pfhash_t * p, u32 bucket_contents,
333 void *key, u32 * match_index)
341 (pfhash_kv_t *) pfhash_get_kv_16 (p, bucket_contents, key,
345 if (p->value_size == 4)
346 kv = (pfhash_kv_t *) pfhash_get_kv_8 (p, bucket_contents,
349 kv = (pfhash_kv_t *) pfhash_get_kv_8v8 (p, bucket_contents,
354 (pfhash_kv_t *) pfhash_get_kv_4 (p, bucket_contents, key,
364 pfhash_get (pfhash_t * p, u32 bucket, void *key)
367 u32 match_index = ~0;
368 pfhash_kv_16_t *kv16;
370 pfhash_kv_8v8_t *kv8v8;
373 u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
375 if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
379 hp = hash_get_mem (p->overflow_hash, key);
385 kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
386 if (match_index == (u32) ~ 0)
397 return (kv16->values[match_index] == (u32) ~ 0)
398 ? (u64) ~ 0 : (u64) kv16->values[match_index];
400 if (p->value_size == 4)
401 return (kv8->values[match_index] == (u32) ~ 0)
402 ? (u64) ~ 0 : (u64) kv8->values[match_index];
404 return kv8v8->values[match_index];
406 return (kv4->values[match_index] == (u32) ~ 0)
407 ? (u64) ~ 0 : (u64) kv4->values[match_index];
415 pfhash_set (pfhash_t * p, u32 bucket, void *key, void *value)
417 u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
418 u32 match_index = (u32) ~ 0;
420 pfhash_kv_16_t *kv16;
422 pfhash_kv_8v8_t *kv8v8;
427 if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
430 hp = hash_get_pair_mem (p->overflow_hash, key);
433 clib_warning ("replace value 0x%08x with value 0x%08x",
434 hp->value[0], (u64) value);
435 hp->value[0] = (u64) value;
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);
442 p->nitems_in_overflow++;
446 if (bucket_contents == 0)
448 pool_get_aligned (p->kvp, kv, 16);
449 memset (kv, 0xff, sizeof (*kv));
450 p->buckets[bucket] = kv - p->kvp;
453 kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
462 if (match_index != (u32) ~ 0)
467 kv16->values[match_index] = (u32) (u64) value;
471 if (p->value_size == 4)
472 kv8->values[match_index] = (u32) (u64) value;
474 kv8v8->values[match_index] = (u64) value;
478 kv4->values[match_index] = (u64) value;
489 for (i = 0; i < 3; i++)
491 if (kv16->values[i] == (u32) ~ 0)
493 clib_memcpy (&kv16->kb.k_u32x4[i], key, p->key_size);
494 kv16->values[i] = (u32) (u64) value;
498 /* copy bucket contents to overflow hash tbl */
499 for (i = 0; i < 3; i++)
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++;
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;
512 p->nitems_in_overflow++;
516 if (p->value_size == 4)
518 for (i = 0; i < 5; i++)
520 if (kv8->values[i] == (u32) ~ 0)
522 clib_memcpy (&kv8->kb.k_u64[i], key, 8);
523 kv8->values[i] = (u32) (u64) value;
527 /* copy bucket contents to overflow hash tbl */
528 for (i = 0; i < 5; i++)
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++;
538 for (i = 0; i < 4; i++)
540 if (kv8v8->values[i] == (u64) ~ 0)
542 clib_memcpy (&kv8v8->kb.k_u64[i], key, 8);
543 kv8v8->values[i] = (u64) value;
547 /* copy bucket contents to overflow hash tbl */
548 for (i = 0; i < 4; i++)
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++;
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;
563 p->nitems_in_overflow++;
567 for (i = 0; i < 8; i++)
569 if (kv4->values[i] == (u32) ~ 0)
571 clib_memcpy (&kv4->kb.kb[i], key, 4);
572 kv4->values[i] = (u32) (u64) value;
576 /* copy bucket contents to overflow hash tbl */
577 for (i = 0; i < 8; i++)
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++;
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;
590 p->nitems_in_overflow++;
599 pfhash_unset (pfhash_t * p, u32 bucket, void *key)
601 u32 bucket_contents = pfhash_read_bucket_prefetch_kv (p, bucket);
602 u32 match_index = (u32) ~ 0;
604 pfhash_kv_16_t *kv16;
606 pfhash_kv_8v8_t *kv8v8;
610 if (bucket_contents == PFHASH_BUCKET_OVERFLOW)
613 hp = hash_get_pair_mem (p->overflow_hash, key);
616 oldkey = (void *) hp->key;
617 hash_unset_mem (p->overflow_hash, key);
618 clib_mem_free (oldkey);
620 p->nitems_in_overflow--;
625 kv = pfhash_get_internal (p, bucket_contents, key, &match_index);
626 if (match_index == (u32) ~ 0)
639 kv16->values[match_index] = (u32) ~ 0;
643 if (p->value_size == 4)
644 kv8->values[match_index] = (u32) ~ 0;
646 kv8v8->values[match_index] = (u64) ~ 0;
650 kv4->values[match_index] = (u32) ~ 0;
659 pfhash_free (pfhash_t * p)
670 hash_foreach_pair (hp, p->overflow_hash,
672 vec_add1 (keys, (u8 *)hp->key);
675 hash_free (p->overflow_hash);
676 for (i = 0; i < vec_len (keys); i++)
684 * fd.io coding-style-patch-verification: ON
687 * eval: (c-set-style "gnu")