vppinfra: fix mhash oob after unset and add tests

Fix out of buffer access after mhash_unset
Add format mhash pair functions
Add related mhash tests, similar to hash ones

Type: fix
Signed-off-by: Vladislav Grishenko <themiron@yandex-team.ru>
Change-Id: Idbefd7d32c4cd16b55d84ad4006c38251b4e2c33

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