X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Ftest_bihash_template.c;h=17cc05629ae2f5d73ad2db6adfbd367a303a7ba8;hb=e8ea6be8dfb626b5bb4ff3355ce8037724ce1d83;hp=2d4b553d259d9ec18c540da4d37cf5d39515c826;hpb=e7d212fe41de88863884dc24dff9e24e5f37b421;p=vpp.git diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c index 2d4b553d259..17cc05629ae 100644 --- a/src/vppinfra/test_bihash_template.c +++ b/src/vppinfra/test_bihash_template.c @@ -17,6 +17,7 @@ #include #include #include +#include #include #include @@ -25,19 +26,26 @@ typedef struct { + volatile u32 thread_barrier; + volatile u32 threads_running; + volatile u64 sequence_number; u64 seed; u32 nbuckets; u32 nitems; u32 ncycles; u32 report_every_n; u32 search_iter; + u32 noverwritten; int careful_delete_tests; int verbose; int non_random_keys; + u32 nthreads; uword *key_hash; u64 *keys; + uword hash_memory_size; BVT (clib_bihash) hash; clib_time_t clib_time; + void *global_heap; unformat_input_t *input; @@ -64,7 +72,13 @@ test_bihash_vec64 (test_main_t * tm) h = &tm->hash; +#if BIHASH_32_64_SVM + BV (clib_bihash_initiator_init_svm) (h, "test", user_buckets, + 0x30000000 /* base_addr */ , + user_memory_size); +#else BV (clib_bihash_init) (h, "test", user_buckets, user_memory_size); +#endif before = clib_time_now (&tm->clib_time); @@ -88,6 +102,205 @@ test_bihash_vec64 (test_main_t * tm) return 0; } +static int +stale_cb (BVT (clib_bihash_kv) * kv, void *ctx) +{ + test_main_t *tm = ctx; + + tm->noverwritten++; + + return 1; +} + +static clib_error_t * +test_bihash_stale_overwrite (test_main_t * tm) +{ + BVT (clib_bihash) * h; + BVT (clib_bihash_kv) kv; + int i; + tm->noverwritten = 0; + + h = &tm->hash; + +#if BIHASH_32_64_SVM + BV (clib_bihash_initiator_init_svm) (h, "test", tm->nbuckets, + 0x30000000 /* base_addr */ , + tm->hash_memory_size); +#else + BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); +#endif + + fformat (stdout, "Add %d items to %d buckets\n", tm->nitems, tm->nbuckets); + + for (i = 0; i < tm->nitems; i++) + { + kv.key = i; + kv.value = 1; + + BV (clib_bihash_add_or_overwrite_stale) (h, &kv, stale_cb, tm); + } + + fformat (stdout, "%d items overwritten\n", tm->noverwritten); + fformat (stdout, "%U", BV (format_bihash), h, 0); + + return 0; +} + +void * +test_bihash_thread_fn (void *arg) +{ + BVT (clib_bihash) * h; + BVT (clib_bihash_kv) kv; + test_main_t *tm = &test_main; + + int i, j; + + u32 my_thread_index = (u32) (u64) arg; + __os_thread_index = my_thread_index; + clib_mem_set_per_cpu_heap (tm->global_heap); + + while (tm->thread_barrier) + ; + + h = &tm->hash; + + for (i = 0; i < tm->ncycles; i++) + { + for (j = 0; j < tm->nitems; j++) + { + kv.key = ((u64) my_thread_index << 32) | (u64) j; + kv.value = ((u64) my_thread_index << 32) | (u64) j; + (void) __atomic_add_fetch (&tm->sequence_number, 1, + __ATOMIC_ACQUIRE); + BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ ); + } + for (j = 0; j < tm->nitems; j++) + { + kv.key = ((u64) my_thread_index << 32) | (u64) j; + kv.value = ((u64) my_thread_index << 32) | (u64) j; + (void) __atomic_add_fetch (&tm->sequence_number, 1, + __ATOMIC_ACQUIRE); + BV (clib_bihash_add_del) (h, &kv, 0 /* is_add */ ); + } + } + + (void) __atomic_sub_fetch (&tm->threads_running, 1, __ATOMIC_ACQUIRE); + while (1) + { + struct timespec ts, tsrem; + ts.tv_sec = 1; + ts.tv_nsec = 0; + + while (nanosleep (&ts, &tsrem) < 0) + ts = tsrem; + } + return (0); /* not so much */ +} + +static clib_error_t * +test_bihash_threads (test_main_t * tm) +{ + int i; + pthread_t handle; + BVT (clib_bihash) * h; + int rv; + + h = &tm->hash; + +#if BIHASH_32_64_SVM + BV (clib_bihash_initiator_init_svm) (h, "test", tm->nbuckets, + 0x30000000 /* base_addr */ , + tm->hash_memory_size); +#else + BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); +#endif + + tm->thread_barrier = 1; + + /* Start the worker threads */ + for (i = 0; i < tm->nthreads; i++) + { + rv = pthread_create (&handle, NULL, test_bihash_thread_fn, + (void *) (u64) i); + if (rv) + { + clib_unix_warning ("pthread_create returned %d", rv); + } + } + tm->threads_running = i; + tm->sequence_number = 0; + CLIB_MEMORY_BARRIER (); + + /* start the workers */ + tm->thread_barrier = 0; + + while (tm->threads_running) + { + struct timespec ts, tsrem; + ts.tv_sec = 0; + ts.tv_nsec = 20 * 1000 * 1000; /* sleep for 20ms at a time */ + + while (nanosleep (&ts, &tsrem) < 0) + ts = tsrem; + } + + return 0; +} + +static clib_error_t * +test_bihash_vanilla_overwrite (test_main_t *tm) +{ + int i; + BVT (clib_bihash) * h; + BVT (clib_bihash_kv) kv; + + h = &tm->hash; + +#if BIHASH_32_64_SVM + BV (clib_bihash_initiator_init_svm) + (h, "test", tm->nbuckets, 0x30000000 /* base_addr */, tm->hash_memory_size); +#else + BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); +#endif + + for (i = 0; i < 100; i++) + { + kv.key = 12345; + kv.value = i; + + BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */); + } + + fformat (stdout, "End of run, should one item...\n"); + fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */); + BV (clib_bihash_free) (h); + return 0; +} + +static clib_error_t * +test_bihash_value_assert (test_main_t *tm) +{ + BVT (clib_bihash) * h; + BVT (clib_bihash_kv) kv; + + h = &tm->hash; + +#if BIHASH_32_64_SVM + BV (clib_bihash_initiator_init_svm) + (h, "test", tm->nbuckets, 0x30000000 /* base_addr */, tm->hash_memory_size); +#else + BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); +#endif + + kv.key = 12345; + kv.value = 0xFEEDFACE8BADF00DULL; + + fformat (stderr, "The following add should ASSERT...\n"); + BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */); + + return 0; +} + static clib_error_t * test_bihash (test_main_t * tm) { @@ -101,8 +314,13 @@ test_bihash (test_main_t * tm) h = &tm->hash; - BV (clib_bihash_init) (h, "test", tm->nbuckets, 3ULL << 30); - +#if BIHASH_32_64_SVM + BV (clib_bihash_initiator_init_svm) (h, "test", tm->nbuckets, + 0x30000000 /* base_addr */ , + tm->hash_memory_size); +#else + BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); +#endif for (acycle = 0; acycle < tm->ncycles; acycle++) { @@ -172,6 +390,16 @@ test_bihash (test_main_t * tm) { for (i = 0; i < tm->nitems; i++) { + /* Prefetch buckets 8 iterations ahead */ + if (1 && (i < ((i64) tm->nitems - 8))) + { + BVT (clib_bihash_kv) pref_kv; + u64 pref_hash; + pref_kv.key = tm->keys[i + 8]; + pref_hash = BV (clib_bihash_hash) (&pref_kv); + BV (clib_bihash_prefetch_bucket) (h, pref_hash); + } + kv.key = tm->keys[i]; if (BV (clib_bihash_search) (h, &kv, &kv) < 0) if (BV (clib_bihash_search) (h, &kv, &kv) < 0) @@ -191,8 +419,10 @@ test_bihash (test_main_t * tm) total_searches = (uword) tm->search_iter * (uword) tm->nitems; if (delta > 0) - fformat (stdout, "%.f searches per second\n", - ((f64) total_searches) / delta); + fformat (stdout, + "%.f searches per second, %.2f nsec per search\n", + ((f64) total_searches) / delta, + 1e9 * (delta / ((f64) total_searches))); fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta); @@ -244,6 +474,16 @@ test_bihash (test_main_t * tm) { for (j = 0; j < tm->nitems; j++) { + /* Prefetch buckets 8 iterations ahead */ + if (1 && (j < ((i64) tm->nitems - 8))) + { + BVT (clib_bihash_kv) pref_kv; + u64 pref_hash; + pref_kv.key = tm->keys[j + 8]; + pref_hash = BV (clib_bihash_hash) (&pref_kv); + BV (clib_bihash_prefetch_bucket) (h, pref_hash); + } + kv.key = tm->keys[j]; rv = BV (clib_bihash_search) (h, &kv, &kv); if (j <= i && rv >= 0) @@ -269,47 +509,18 @@ test_bihash (test_main_t * tm) } /* Clean up side-bet hash table and random key vector */ - for (i = 0; i < tm->nitems; i++) - hash_unset (tm->key_hash, tm->keys[i]); - + hash_free (tm->key_hash); vec_reset_length (tm->keys); + /* Recreate hash table if we're going to need it again */ + if (acycle != (tm->ncycles - 1)) + tm->key_hash = hash_create (tm->nitems, sizeof (uword)); } fformat (stdout, "End of run, should be empty...\n"); fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ ); - return 0; -} - -clib_error_t * -test_bihash_cache (test_main_t * tm) -{ - u32 lru; - BVT (clib_bihash_bucket) _b, *b = &_b; - - BV (clib_bihash_reset_cache) (b); - - fformat (stdout, "Initial LRU config: %U\n", BV (format_bihash_lru), b); - - BV (clib_bihash_update_lru_not_inline) (b, 3); - - fformat (stdout, "use slot 3, LRU config: %U\n", BV (format_bihash_lru), b); - - BV (clib_bihash_update_lru) (b, 1); - fformat (stdout, "use slot 1 LRU config: %U\n", BV (format_bihash_lru), b); - - lru = BV (clib_bihash_get_lru) (b); - - fformat (stdout, "least-recently-used is %d\n", lru); - - BV (clib_bihash_update_lru) (b, 4); - - fformat (stdout, "use slot 4 LRU config: %U\n", BV (format_bihash_lru), b); - - lru = BV (clib_bihash_get_lru) (b); - - fformat (stdout, "least-recently-used is %d\n", lru); + BV (clib_bihash_free) (h); return 0; } @@ -322,6 +533,7 @@ test_bihash_main (test_main_t * tm) int which = 0; tm->report_every_n = 1; + tm->hash_memory_size = 1ULL << 30; while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT) { @@ -344,18 +556,31 @@ test_bihash_main (test_main_t * tm) ; else if (unformat (i, "report-every %d", &tm->report_every_n)) ; + else if (unformat (i, "memory-size %U", + unformat_memory_size, &tm->hash_memory_size)) + ; else if (unformat (i, "vec64")) which = 1; - else if (unformat (i, "cache")) + else if (unformat (i, "threads %u", &tm->nthreads)) which = 2; - else if (unformat (i, "verbose")) tm->verbose = 1; + else if (unformat (i, "stale-overwrite")) + which = 3; + else if (unformat (i, "overwrite")) + which = 4; + else if (unformat (i, "value-assert")) + which = 5; else return clib_error_return (0, "unknown input '%U'", format_unformat_error, i); } + /* Preallocate hash table, key vector */ + tm->key_hash = hash_create (tm->nitems, sizeof (uword)); + vec_validate (tm->keys, tm->nitems - 1); + vec_set_len (tm->keys, 0); + switch (which) { case 0: @@ -367,7 +592,19 @@ test_bihash_main (test_main_t * tm) break; case 2: - error = test_bihash_cache (tm); + error = test_bihash_threads (tm); + break; + + case 3: + error = test_bihash_stale_overwrite (tm); + break; + + case 4: + error = test_bihash_vanilla_overwrite (tm); + break; + + case 5: + error = test_bihash_value_assert (tm); break; default: @@ -385,7 +622,9 @@ main (int argc, char *argv[]) clib_error_t *error; test_main_t *tm = &test_main; - clib_mem_init (0, 3ULL << 30); + clib_mem_init (0, 4095ULL << 20); + + tm->global_heap = clib_mem_get_per_cpu_heap (); tm->input = &i; tm->seed = 0xdeaddabe; @@ -396,7 +635,6 @@ main (int argc, char *argv[]) tm->verbose = 1; tm->search_iter = 1; tm->careful_delete_tests = 0; - tm->key_hash = hash_create (0, sizeof (uword)); clib_time_init (&tm->clib_time); unformat_init_command_line (&i, argv);