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)
89 for (j = 0; j < 3; j++)
91 if (kv16->values[j] != (
u32) ~ 0)
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)
111 sh->value = kv8->values[j];
118 for (j = 0; j < 4; j++)
120 if (kv8v8->values[j] != (
u64) ~ 0)
125 sh->value = kv8v8->values[j];
133 for (j = 0; j < 8; j++)
135 if (kv4->values[j] != (
u32) ~ 0)
138 clib_memcpy (sh->key, &kv4->kb.kb[j], p->key_size);
139 sh->value = kv4->values[j];
149 vec_add2 (shs, sh, 1);
150 clib_memcpy (sh->key, (u8 *)hp->key, p->key_size);
151 sh->value = hp->value[0];
157 for (i = 0; i <
vec_len (shs); i++)
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);
210 nbuckets = 1 << (
max_log2 (nbuckets));
214 p->key_size = key_size;
215 p->value_size = value_size;
222 memset (kv, 0xff,
sizeof (*kv));
225 static pfhash_kv_16_t *
226 pfhash_get_kv_16 (pfhash_t * p,
u32 bucket_contents,
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]);
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;
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)
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)
442 p->nitems_in_overflow++;
446 if (bucket_contents == 0)
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;
499 for (i = 0; i < 3; i++)
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++;
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)
523 kv8->values[
i] = (
u32) (
u64) value;
528 for (i = 0; i < 5; i++)
533 p->nitems_in_overflow++;
538 for (i = 0; i < 4; i++)
540 if (kv8v8->values[i] == (
u64) ~ 0)
543 kv8v8->values[
i] = (
u64) value;
548 for (i = 0; i < 4; i++)
552 hash_set_mem (p->overflow_hash, kcopy, kv8v8->values[i]);
553 p->nitems_in_overflow++;
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)
572 kv4->values[
i] = (
u32) (
u64) value;
577 for (i = 0; i < 8; i++)
582 p->nitems_in_overflow++;
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)
616 oldkey = (
void *) hp->
key;
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)
672 vec_add1 (keys, (u8 *)hp->key);
676 for (i = 0; i <
vec_len (keys); i++)
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
static u32x4 u32x4_is_equal(u32x4 x, u32x4 y)
sll srl srl sll sra u16x4 i
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
#define hash_set_mem(h, key, value)
#define hash_get_pair_mem(h, key)
static uword min_log2(uword x)
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
#define hash_create_mem(elts, key_bytes, value_bytes)
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
#define hash_unset_mem(h, key)
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P (general version).
#define pool_free(p)
Free a pool.
#define vec_free(V)
Free vector's memory (no header).
#define clib_warning(format, args...)
#define clib_memcpy(a, b, c)
static void clib_mem_free(void *p)
static void * clib_mem_alloc(uword size)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
static uword max_log2(uword x)
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
#define hash_get_mem(h, key)
static u32 u32x4_zero_byte_mask(u32x4 x)