src/vppinfra/test_mhash.c - fdio/vpp - Gitiles

 /* 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 */
	/* 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 */