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 #include <vppinfra/time.h>
17 #include <vppinfra/cache.h>
18 #include <vppinfra/error.h>
20 #include <vppinfra/heap.h>
21 #include <vppinfra/format.h>
22 #include <vppinfra/random.h>
23 #include <vppinfra/hash.h>
25 #include <vppinfra/flowhash_8_8.h>
27 /* Not actually tested here. But included for compilation purposes. */
28 #include <vppinfra/flowhash_24_16.h>
34 u32 collision_buckets;
40 flowhash_lkey_8_8_t *keys;
42 clib_time_t clib_time;
43 unformat_input_t *input;
46 test_main_t test_main;
49 test_flowhash (test_main_t * tm)
56 tm->hash = flowhash_alloc_8_8 (tm->fixed_entries, tm->collision_buckets);
58 return clib_error_return (0, "Could not alloc hash");
60 fformat (stdout, "Allocated hash memory size: %llu\n",
61 flowhash_memory_size (tm->hash));
63 fformat (stdout, "Pick %lld unique %s keys...\n",
64 tm->nitems, tm->non_random_keys ? "non-random" : "random");
66 for (i = 0; i < tm->nitems; i++)
68 flowhash_lkey_8_8_t rndkey;
69 if (tm->non_random_keys == 0)
72 rndkey.as_u64[0] = random_u64 (&tm->seed);
73 if ((p = hash_get (tm->key_hash, rndkey.as_u64[0])))
77 rndkey.as_u64[0] = (u64) (i + 1) << 16;
79 hash_set (tm->key_hash, rndkey.as_u64[0], i + 1);
80 vec_add1 (tm->keys, rndkey);
83 hash_free (tm->key_hash);
87 before = clib_time_now (&tm->clib_time);
88 fformat (stdout, "Adding %u items...\n", tm->nitems);
89 for (i = 0; i < tm->nitems; i++)
91 u32 hash = flowhash_hash_8_8 (&tm->keys[i]);
93 flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei);
94 if (flowhash_is_overflow (ei))
97 /* Set value (No matter if success) */
98 flowhash_value (tm->hash, ei)->as_u64[0] = i + 1;
100 /* Save value until time > 1 */
101 flowhash_timeout (tm->hash, ei) = 1;
104 delta = clib_time_now (&tm->clib_time) - before;
106 fformat (stdout, "%lld additions in %.6f seconds\n", total, delta);
108 fformat (stdout, "%.f additions per second\n", ((f64) total) / delta);
110 fformat (stdout, "%u elements in table\n", flowhash_elts_8_8 (tm->hash, 1));
111 fformat (stdout, "Flowhash counters:\n");
112 fformat (stdout, " collision-lookup: %lu\n",
113 tm->hash->collision_lookup_counter);
114 fformat (stdout, " not-enough-buckets: %lu\n",
115 tm->hash->not_enough_buckets_counter);
116 fformat (stdout, " overflows: %lu\n", overflow);
118 /* Lookups (very similar to additions) */
120 before = clib_time_now (&tm->clib_time);
121 fformat (stdout, "Looking up %u items %u times...\n", tm->nitems,
124 for (j = 0; j < tm->iterations; j++)
128 for (; i < tm->nitems - tm->prefetch; i++)
131 u32 hash = flowhash_hash_8_8 (&tm->keys[i + tm->prefetch]);
132 flowhash_prefetch (tm->hash, hash);
133 hash = flowhash_hash_8_8 (&tm->keys[i]);
134 flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei);
135 if (flowhash_is_overflow (ei))
137 else if (flowhash_timeout (tm->hash, ei) != 1)
138 clib_warning ("Key not found: %lld\n", tm->keys[i].as_u64[0]);
139 else if (flowhash_value (tm->hash, ei)->as_u64[0] != i + 1)
140 clib_warning ("Value mismatch for key %lld\n",
141 tm->keys[i].as_u64[0]);
144 for (; i < tm->nitems; i++)
147 u32 hash = flowhash_hash_8_8 (&tm->keys[i]);
148 flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei);
149 if (flowhash_is_overflow (ei))
151 else if (flowhash_timeout (tm->hash, ei) != 1)
152 clib_warning ("Key not found: %lld\n", tm->keys[i].as_u64[0]);
153 else if (flowhash_value (tm->hash, ei)->as_u64[0] != i + 1)
154 clib_warning ("Value mismatch for key %lld\n",
155 tm->keys[i].as_u64[0]);
159 delta = clib_time_now (&tm->clib_time) - before;
160 total = tm->nitems * tm->iterations;
161 fformat (stdout, "%lld lookups in %.6f seconds\n", total, delta);
163 fformat (stdout, "%.f lookups per second\n", ((f64) total) / delta);
166 for (i = 0; i < tm->nitems; i++)
168 u32 hash = flowhash_hash_8_8 (&tm->keys[i]);
170 flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei);
171 flowhash_timeout (tm->hash, ei) = 0;
174 fformat (stdout, "%u elements in table\n", flowhash_elts_8_8 (tm->hash, 1));
177 flowhash_free_8_8 (tm->hash);
183 test_flowhash_main (test_main_t * tm)
185 unformat_input_t *i = tm->input;
188 while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
190 if (unformat (i, "seed %u", &tm->seed))
192 else if (unformat (i, "fixed-entries %d", &tm->fixed_entries))
194 else if (unformat (i, "collision-buckets %d", &tm->collision_buckets))
196 else if (unformat (i, "non-random-keys"))
197 tm->non_random_keys = 1;
198 else if (unformat (i, "nitems %d", &tm->nitems))
200 else if (unformat (i, "prefetch %d", &tm->prefetch))
202 else if (unformat (i, "iterations %d", &tm->iterations))
205 return clib_error_return (0, "unknown input '%U'",
206 format_unformat_error, i);
209 error = test_flowhash (tm);
215 main (int argc, char *argv[])
220 test_main_t *tm = &test_main;
222 clib_mem_init (0, 3ULL << 30);
224 tm->fixed_entries = 8 << 20;
225 tm->collision_buckets = 1 << 20;
226 tm->seed = 0xdeadf00l;
230 tm->non_random_keys = 0;
231 tm->key_hash = hash_create (0, sizeof (uword));
233 clib_time_init (&tm->clib_time);
235 unformat_init_command_line (&i, argv);
236 error = test_flowhash_main (tm);
241 clib_error_report (error);
248 #endif /* CLIB_UNIX */
252 * fd.io coding-style-patch-verification: ON
255 * eval: (c-set-style "gnu")