diff options
| -rw-r--r-- | src/vppinfra/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/vppinfra/heap.c | 1 | ||||
| -rw-r--r-- | src/vppinfra/mhash.c | 52 | ||||
| -rw-r--r-- | src/vppinfra/mhash.h | 5 | ||||
| -rw-r--r-- | src/vppinfra/test_mhash.c | 403 |
5 files changed, 455 insertions, 7 deletions
diff --git a/src/vppinfra/CMakeLists.txt b/src/vppinfra/CMakeLists.txt index 5878f0612f0..154e3a77cb1 100644 --- a/src/vppinfra/CMakeLists.txt +++ b/src/vppinfra/CMakeLists.txt @@ -265,6 +265,7 @@ if(VPP_BUILD_VPPINFRA_TESTS) longjmp macros maplog + mhash pmalloc pool_alloc pool_iterate diff --git a/src/vppinfra/heap.c b/src/vppinfra/heap.c index 7db814200f8..9920528732d 100644 --- a/src/vppinfra/heap.c +++ b/src/vppinfra/heap.c @@ -680,6 +680,7 @@ debug_elt (u8 * s, void *v, word i, word n) i = -n / 2; for (e = e0; 1; e = heap_next (e)) { + s = format (s, " "); if (heap_is_free (e)) s = format (s, "index %4d, free\n", e - h->elts); else if (h->format_elt) diff --git a/src/vppinfra/mhash.c b/src/vppinfra/mhash.c index f0f1aa470d7..babaaeec726 100644 --- a/src/vppinfra/mhash.c +++ b/src/vppinfra/mhash.c @@ -164,6 +164,8 @@ mhash_sanitize_hash_user (mhash_t * mh) h->user = pointer_to_uword (mh); } +static u8 *mhash_format_pair_default (u8 *s, va_list *args); + __clib_export void mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes) { @@ -208,12 +210,12 @@ mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes) vec_validate (h->key_tmps, os_get_nthreads () - 1); ASSERT (n_key_bytes < ARRAY_LEN (t)); - h->hash = hash_create2 ( /* elts */ 0, + h->hash = hash_create2 (/* elts */ 0, /* user */ pointer_to_uword (h), /* value_bytes */ n_value_bytes, t[n_key_bytes].key_sum, t[n_key_bytes].key_equal, /* format pair/arg */ - 0, 0); + mhash_format_pair_default, 0); } static uword @@ -331,8 +333,8 @@ mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value) { if (key_alloc_from_free_list) { - h->key_vector_free_indices[l] = i; - vec_set_len (h->key_vector_free_indices, l + 1); + vec_set_len (h->key_vector_free_indices, l); + h->key_vector_free_indices[l - 1] = i; } else vec_dec_len (h->key_vector_or_heap, h->n_key_bytes); @@ -371,8 +373,8 @@ mhash_unset (mhash_t * h, void *key, uword * old_value) return 1; } -u8 * -format_mhash_key (u8 * s, va_list * va) +__clib_export u8 * +format_mhash_key (u8 *s, va_list *va) { mhash_t *h = va_arg (*va, mhash_t *); u32 ki = va_arg (*va, u32); @@ -387,7 +389,43 @@ format_mhash_key (u8 * s, va_list * va) else if (h->format_key) s = format (s, "%U", h->format_key, k); else - s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes); + s = format (s, "0x%U", format_hex_bytes, k, h->n_key_bytes); + + return s; +} + +static u8 * +mhash_format_pair_default (u8 *s, va_list *args) +{ + void *CLIB_UNUSED (user_arg) = va_arg (*args, void *); + void *v = va_arg (*args, void *); + hash_pair_t *p = va_arg (*args, hash_pair_t *); + hash_t *h = hash_header (v); + mhash_t *mh = uword_to_pointer (h->user, mhash_t *); + + s = format (s, "%U", format_mhash_key, mh, (u32) p->key); + if (hash_value_bytes (h) > 0) + s = format (s, " -> 0x%8U", format_hex_bytes, &p->value[0], + hash_value_bytes (h)); + return s; +} + +__clib_export u8 * +format_mhash (u8 *s, va_list *va) +{ + mhash_t *h = va_arg (*va, mhash_t *); + int verbose = va_arg (*va, int); + + s = format (s, "mhash %p, %wd elts, \n", h, mhash_elts (h)); + if (mhash_key_vector_is_heap (h)) + s = format (s, " %U", format_heap, h->key_vector_or_heap, verbose); + else + s = format (s, " keys %wd elts, %wd size, %wd free, %wd bytes used\n", + vec_len (h->key_vector_or_heap) / h->n_key_bytes, + h->n_key_bytes, vec_len (h->key_vector_free_indices), + vec_bytes (h->key_vector_or_heap) + + vec_bytes (h->key_vector_free_indices)); + s = format (s, " %U", format_hash, h->hash, verbose); return s; } diff --git a/src/vppinfra/mhash.h b/src/vppinfra/mhash.h index 7eb1918384e..62aee365fa3 100644 --- a/src/vppinfra/mhash.h +++ b/src/vppinfra/mhash.h @@ -166,8 +166,13 @@ do { \ })); \ } while (0) +u8 *format_mhash (u8 *s, va_list *va); + format_function_t format_mhash_key; +/* Main test routine. */ +int test_mhash_main (unformat_input_t *input); + #endif /* included_clib_mhash_h */ /* diff --git a/src/vppinfra/test_mhash.c b/src/vppinfra/test_mhash.c new file mode 100644 index 00000000000..70be2b9b382 --- /dev/null +++ b/src/vppinfra/test_mhash.c @@ -0,0 +1,403 @@ +/* SPDX-License-Identifier: Apache-2.0 + * Copyright(c) 2023 Yandex LLC. + */ + +#ifdef CLIB_LINUX_KERNEL +#include <linux/unistd.h> +#endif + +#ifdef CLIB_UNIX +#include <unistd.h> +#include <stdlib.h> +#include <stdio.h> +#include <vppinfra/time.h> +#endif + +#include <vppinfra/random.h> +#include <vppinfra/mem.h> +#include <vppinfra/hash.h> +#include <vppinfra/mhash.h> +#include <vppinfra/error.h> +#include <vppinfra/format.h> +#include <vppinfra/bitmap.h> + +static int verbose; +#define if_verbose(format, args...) \ + if (verbose) \ + { \ + clib_warning (format, ##args); \ + } + +typedef struct +{ + int n_iterations; + + int n_iterations_per_print; + + /* Number of pairs to insert into mhash. */ + int n_pairs; + + /* True to validate correctness of mhash functions. */ + int n_iterations_per_validate; + + /* Verbosity level for mhash formats. */ + int verbose; + + /* Random number seed. */ + u32 seed; +} mhash_test_t; + +static clib_error_t * +mhash_next_test (mhash_t *h) +{ + hash_next_t hn = { 0 }; + hash_pair_t *p0, *p1; + clib_error_t *error = 0; + + hash_foreach_pair (p0, h->hash, { + p1 = hash_next (h->hash, &hn); + error = CLIB_ERROR_ASSERT (p0 == p1); + if (error) + break; + }); + + if (!error) + error = CLIB_ERROR_ASSERT (!hash_next (h->hash, &hn)); + + return error; +} + +static clib_error_t * +test_word_key (mhash_test_t *ht) +{ + mhash_t _h = { 0 }, *h = &_h; + word i, j; + + word *keys = 0, *vals = 0; + uword *is_inserted = 0; + + clib_error_t *error = 0; + + vec_resize (keys, ht->n_pairs); + vec_resize (vals, vec_len (keys)); + + mhash_init (h, sizeof (vals[0]), sizeof (keys[0])); + /* borrow 0 elt to make index keys non-zero */ + vec_validate (h->key_vector_or_heap, 0); + + { + uword *unique = 0; + u32 k; + + for (i = 0; i < vec_len (keys); i++) + { + do + { + k = random_u32 (&ht->seed) & 0xfffff; + } + while (clib_bitmap_get (unique, k)); + unique = clib_bitmap_ori (unique, k); + keys[i] = k; + vals[i] = i; + } + + clib_bitmap_free (unique); + } + + for (i = 0; i < ht->n_iterations; i++) + { + u32 vi = random_u32 (&ht->seed) % vec_len (keys); + + if (clib_bitmap_get (is_inserted, vi)) + { + mhash_unset (h, &keys[vi], 0); + mhash_unset (h, &keys[vi], 0); + } + else + { + mhash_set (h, &keys[vi], vals[vi], 0); + mhash_set (h, &keys[vi], vals[vi], 0); + } + + is_inserted = clib_bitmap_xori (is_inserted, vi); + + if (ht->n_iterations_per_print > 0 && + ((i + 1) % ht->n_iterations_per_print) == 0) + if_verbose ("iteration %d\n %U", i + 1, format_mhash, h, ht->verbose); + + if (ht->n_iterations_per_validate == 0 || + (i + 1) % ht->n_iterations_per_validate) + continue; + + { + uword ki, *k, *v; + + mhash_foreach (k, v, h, { + ki = v[0]; + ASSERT (keys[ki] == k[0]); + }); + } + + if ((error = hash_validate (h->hash))) + goto done; + + for (j = 0; j < vec_len (keys); j++) + { + uword *v; + v = mhash_get (h, &keys[j]); + if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == + (v != 0)))) + goto done; + if (v) + { + if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j]))) + goto done; + } + } + } + + if ((error = mhash_next_test (h))) + goto done; + + if_verbose ("%U", format_mhash, h, ht->verbose); + + for (i = 0; i < vec_len (keys); i++) + { + if (!clib_bitmap_get (is_inserted, i)) + continue; + + mhash_unset (h, &keys[i], 0); + mhash_unset (h, &keys[i], 0); + is_inserted = clib_bitmap_xori (is_inserted, i); + + if (ht->n_iterations_per_validate == 0 || + (i + 1) % ht->n_iterations_per_validate) + continue; + + if ((error = hash_validate (h->hash))) + goto done; + + for (j = 0; j < vec_len (keys); j++) + { + uword *v; + v = mhash_get (h, &keys[j]); + if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == + (v != 0)))) + goto done; + if (v) + { + if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j]))) + goto done; + } + } + } + +done: + mhash_free (h); + vec_free (keys); + vec_free (vals); + clib_bitmap_free (is_inserted); + + if (verbose) + fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0); + + return error; +} + +static u8 * +test2_format (u8 *s, va_list *args) +{ + void *CLIB_UNUSED (user_arg) = va_arg (*args, void *); + void *v = va_arg (*args, void *); + hash_pair_t *p = va_arg (*args, hash_pair_t *); + hash_t *h = hash_header (v); + mhash_t *mh = uword_to_pointer (h->user, mhash_t *); + + return format (s, "0x%8U <- %U", format_hex_bytes, &p->value[0], + hash_value_bytes (h), format_mhash_key, mh, (u32) p->key); +} + +static clib_error_t * +test_string_key (mhash_test_t *ht, uword is_c_string) +{ + mhash_t _h = { 0 }, *h = &_h; + word i, j; + + u8 **keys = 0; + word *vals = 0; + uword *is_inserted = 0; + + clib_error_t *error = 0; + + vec_resize (keys, ht->n_pairs); + vec_resize (vals, vec_len (keys)); + + if (is_c_string) + mhash_init_c_string (h, sizeof (vals[0])); + else + mhash_init_vec_string (h, sizeof (vals[0])); + hash_set_pair_format (h->hash, test2_format, 0); + + for (i = 0; i < vec_len (keys); i++) + { + keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf)); + keys[i] = format (keys[i], "%x", i); + if (is_c_string) + vec_terminate_c_string (keys[i]); + vals[i] = random_u32 (&ht->seed); + } + + for (i = 0; i < ht->n_iterations; i++) + { + u32 vi = random_u32 (&ht->seed) % vec_len (keys); + + if (clib_bitmap_get (is_inserted, vi)) + { + mhash_unset (h, keys[vi], 0); + mhash_unset (h, keys[vi], 0); + } + else + { + mhash_set (h, keys[vi], vals[vi], 0); + mhash_set (h, keys[vi], vals[vi], 0); + } + + is_inserted = clib_bitmap_xori (is_inserted, vi); + + if (ht->n_iterations_per_print > 0 && + ((i + 1) % ht->n_iterations_per_print) == 0) + if_verbose ("iteration %d\n %U", i + 1, format_mhash, h, ht->verbose); + + if (ht->n_iterations_per_validate == 0 || + (i + 1) % ht->n_iterations_per_validate) + continue; + + if ((error = hash_validate (h->hash))) + goto done; + + for (j = 0; j < vec_len (keys); j++) + { + uword *v; + v = mhash_get (h, keys[j]); + if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == + (v != 0)))) + goto done; + if (v) + { + if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j]))) + goto done; + } + } + } + + if ((error = mhash_next_test (h))) + goto done; + + if_verbose ("%U", format_mhash, h, ht->verbose); + + for (i = 0; i < vec_len (keys); i++) + { + if (!clib_bitmap_get (is_inserted, i)) + continue; + + mhash_unset (h, keys[i], 0); + mhash_unset (h, keys[i], 0); + is_inserted = clib_bitmap_xori (is_inserted, i); + + if (ht->n_iterations_per_validate == 0 || + (i + 1) % ht->n_iterations_per_validate) + continue; + + if ((error = hash_validate (h->hash))) + goto done; + + for (j = 0; j < vec_len (keys); j++) + { + uword *v; + v = mhash_get (h, keys[j]); + if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == + (v != 0)))) + goto done; + if (v) + { + if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j]))) + goto done; + } + } + } + +done: + mhash_free (h); + vec_free (vals); + clib_bitmap_free (is_inserted); + + for (i = 0; i < vec_len (keys); i++) + vec_free (keys[i]); + vec_free (keys); + + if (verbose) + fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0); + + return error; +} + +int +test_mhash_main (unformat_input_t *input) +{ + mhash_test_t _ht = { 0 }, *ht = &_ht; + clib_error_t *error; + + ht->n_iterations = 100; + ht->n_pairs = 10; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (0 == unformat (input, "iter %d", &ht->n_iterations) && + 0 == unformat (input, "print %d", &ht->n_iterations_per_print) && + 0 == unformat (input, "elts %d", &ht->n_pairs) && + 0 == unformat (input, "seed %d", &ht->seed) && + 0 == unformat (input, "verbose %=", &ht->verbose, 1) && + 0 == unformat (input, "valid %d", &ht->n_iterations_per_validate)) + { + clib_warning ("unknown input `%U'", format_unformat_error, input); + return 1; + } + } + + if (!ht->seed) + ht->seed = random_default_seed (); + + if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed); + + error = test_word_key (ht); + if (error) + clib_error_report (error); + + error = test_string_key (ht, 0); + if (error) + clib_error_report (error); + + error = test_string_key (ht, 1); + if (error) + clib_error_report (error); + + return 0; +} + +#ifdef CLIB_UNIX +int +main (int argc, char *argv[]) +{ + unformat_input_t i; + int ret; + + clib_mem_init (0, 3ULL << 30); + + verbose = (argc > 1); + unformat_init_command_line (&i, argv); + ret = test_mhash_main (&i); + unformat_free (&i); + + return ret; +} +#endif /* CLIB_UNIX */ |