2 * Copyright (c) 2015 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
18 Permission is hereby granted, free of charge, to any person obtaining
19 a copy of this software and associated documentation files (the
20 "Software"), to deal in the Software without restriction, including
21 without limitation the rights to use, copy, modify, merge, publish,
22 distribute, sublicense, and/or sell copies of the Software, and to
23 permit persons to whom the Software is furnished to do so, subject to
24 the following conditions:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
29 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38 #ifdef CLIB_LINUX_KERNEL
39 #include <linux/unistd.h>
46 #include <vppinfra/time.h>
49 #include <vppinfra/random.h>
50 #include <vppinfra/mem.h>
51 #include <vppinfra/hash.h>
52 #include <vppinfra/error.h>
53 #include <vppinfra/format.h>
54 #include <vppinfra/bitmap.h>
57 #define if_verbose(format,args...) \
58 if (verbose) { clib_warning(format, ## args); }
63 int n_iterations_per_print;
65 /* Number of pairs to insert into hash. */
68 /* True to validate correctness of hash functions. */
69 int n_iterations_per_validate;
71 /* Non-zero if hash table size is to be fixed. */
74 /* Verbosity level for hash formats. */
77 /* Random number seed. */
81 static clib_error_t * hash_next_test (word * h)
84 hash_pair_t * p0, * p1;
85 clib_error_t * error = 0;
87 hash_foreach_pair (p0, h, {
88 p1 = hash_next (h, &hn);
89 error = CLIB_ERROR_ASSERT (p0 == p1);
95 error = CLIB_ERROR_ASSERT (! hash_next (h, &hn));
100 static u8 * test1_format (u8 * s, va_list * args)
102 void * CLIB_UNUSED (user_arg) = va_arg (*args, void *);
103 void * v = va_arg (*args, void *);
104 hash_pair_t * p = va_arg (*args, hash_pair_t *);
105 hash_t * h = hash_header (v);
107 return format (s, "0x%8U -> 0x%8U",
108 format_hex_bytes, &p->key, sizeof (p->key),
109 format_hex_bytes, &p->value[0], hash_value_bytes (h));
112 static clib_error_t * test_word_key (hash_test_t * ht)
117 word * keys = 0, * vals = 0;
118 uword * is_inserted = 0;
120 clib_error_t * error = 0;
122 vec_resize (keys, ht->n_pairs);
123 vec_resize (vals, vec_len (keys));
125 h = hash_create (ht->fixed_hash_size, sizeof (vals[0]));
127 hash_set_pair_format (h, test1_format, 0);
128 if (ht->fixed_hash_size)
129 hash_set_flags (h, HASH_FLAG_NO_AUTO_GROW | HASH_FLAG_NO_AUTO_SHRINK);
135 for (i = 0; i < vec_len (keys); i++)
138 k = random_u32 (&ht->seed) & 0xfffff;
139 } while (clib_bitmap_get (unique, k));
140 unique = clib_bitmap_ori (unique, k);
145 clib_bitmap_free (unique);
148 for (i = 0; i < ht->n_iterations; i++)
150 u32 vi = random_u32 (&ht->seed) % vec_len (keys);
152 if (clib_bitmap_get (is_inserted, vi))
153 hash_unset (h, keys[vi]);
155 hash_set (h, keys[vi], vals[vi]);
157 is_inserted = clib_bitmap_xori (is_inserted, vi);
159 if (ht->n_iterations_per_print > 0
160 && ((i + 1) % ht->n_iterations_per_print) == 0)
161 if_verbose ("iteration %d\n %U", i + 1, format_hash, h, ht->verbose);
163 if (ht->n_iterations_per_validate == 0
164 || (i + 1) % ht->n_iterations_per_validate)
171 hash_foreach_pair (p, h, {
173 ASSERT (keys[ki] == p->key);
177 clib_mem_validate ();
179 if ((error = hash_validate (h)))
182 for (j = 0; j < vec_len (keys); j++)
185 v = hash_get (h, keys[j]);
186 if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == (v != 0))))
189 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
195 if ((error = hash_next_test (h)))
198 if_verbose ("%U", format_hash, h, ht->verbose);
200 for (i = 0; i < vec_len (keys); i++)
202 if (! clib_bitmap_get (is_inserted, i))
205 hash_unset (h, keys[i]);
206 is_inserted = clib_bitmap_xori (is_inserted, i);
208 if (ht->n_iterations_per_validate == 0
209 || (i + 1) % ht->n_iterations_per_validate)
212 clib_mem_validate ();
214 if ((error = hash_validate (h)))
217 for (j = 0; j < vec_len (keys); j++)
220 v = hash_get (h, keys[j]);
221 if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == (v != 0))))
224 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
234 clib_bitmap_free (is_inserted);
236 if (verbose) fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
241 static u8 * test2_format (u8 * s, va_list * args)
243 void * CLIB_UNUSED (user_arg) = va_arg (*args, void *);
244 void * v = va_arg (*args, void *);
245 hash_pair_t * p = va_arg (*args, hash_pair_t *);
246 hash_t * h = hash_header (v);
248 return format (s, "0x%8U <- %v",
249 format_hex_bytes, &p->value[0], hash_value_bytes (h),
253 static clib_error_t * test_string_key (hash_test_t * ht)
259 uword * is_inserted = 0;
263 clib_error_t * error = 0;
265 vec_resize (keys, ht->n_pairs);
266 vec_resize (vals, vec_len (keys));
268 h = hash_create_vec (ht->fixed_hash_size, sizeof (keys[0][0]), sizeof (uword));
269 hash_set_pair_format (h, test2_format, 0);
270 if (ht->fixed_hash_size)
271 hash_set_flags (h, HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_NO_AUTO_GROW);
273 for (i = 0; i < vec_len (keys); i++)
275 keys[i] = random_string (&ht->seed,
276 5 + (random_u32 (&ht->seed) & 0xf));
277 keys[i] = format (keys[i], "%x", i);
278 vals[i] = random_u32 (&ht->seed);
281 for (i = 0; i < ht->n_iterations; i++)
283 u32 vi = random_u32 (&ht->seed) % vec_len (keys);
285 if (clib_bitmap_get (is_inserted, vi))
286 hash_unset_mem (h, keys[vi]);
288 hash_set_mem (h, keys[vi], vals[vi]);
290 is_inserted = clib_bitmap_xori (is_inserted, vi);
292 if (ht->n_iterations_per_print > 0
293 && ((i + 1) % ht->n_iterations_per_print) == 0)
294 if_verbose ("iteration %d\n %U", i + 1, format_hash, h, ht->verbose);
296 if (ht->n_iterations_per_validate == 0
297 || (i + 1) % ht->n_iterations_per_validate)
300 clib_mem_validate ();
302 if ((error = hash_validate (h)))
305 for (j = 0; j < vec_len (keys); j++)
308 v = hash_get_mem (h, keys[j]);
309 if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == (v != 0))))
312 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
318 if ((error = hash_next_test (h)))
321 if_verbose ("%U", format_hash, h, ht->verbose);
323 for (i = 0; i < vec_len (keys); i++)
325 if (! clib_bitmap_get (is_inserted, i))
328 hash_unset_mem (h, keys[i]);
329 is_inserted = clib_bitmap_xori (is_inserted, i);
331 if (ht->n_iterations_per_validate == 0
332 || (i + 1) % ht->n_iterations_per_validate)
335 clib_mem_validate ();
337 if ((error = hash_validate (h)))
340 for (j = 0; j < vec_len (keys); j++)
343 v = hash_get_mem (h, keys[j]);
344 if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == (v != 0))))
347 if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j])))
356 clib_bitmap_free (is_inserted);
358 for (i = 0; i < vec_len (keys); i++)
362 if (verbose) fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0);
367 int test_hash_main (unformat_input_t * input)
369 hash_test_t _ht = {0}, * ht = &_ht;
370 clib_error_t * error;
372 ht->n_iterations = 100;
374 ht->fixed_hash_size = 0; /* zero means non-fixed size */
376 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
378 if (0 == unformat (input, "iter %d", &ht->n_iterations)
379 && 0 == unformat (input, "print %d", &ht->n_iterations_per_print)
380 && 0 == unformat (input, "elts %d", &ht->n_pairs)
381 && 0 == unformat (input, "size %d", &ht->fixed_hash_size)
382 && 0 == unformat (input, "seed %d", &ht->seed)
383 && 0 == unformat (input, "verbose %=", &ht->verbose, 1)
384 && 0 == unformat (input, "valid %d", &ht->n_iterations_per_validate))
386 clib_warning ("unknown input `%U'", format_unformat_error, input);
392 ht->seed = random_default_seed ();
394 if_verbose ("testing %d iterations, seed %d",
395 ht->n_iterations, ht->seed);
397 error = test_word_key (ht);
399 clib_error_report (error);
401 error = test_string_key (ht);
403 clib_error_report (error);
409 int main (int argc, char * argv[])
414 verbose = (argc > 1);
415 unformat_init_command_line (&i, argv);
416 ret = test_hash_main (&i);
421 #endif /* CLIB_UNIX */