From 2ce28d6014f44a98f5b3387a4709dd56dbc2f8df Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Fri, 3 May 2019 12:58:01 -0400 Subject: Add bihash statistics hook Example / unit-test in .../src/plugins/unittest/bihash_test.c Change-Id: I23fd0ba742d65291667a755965aee1a3d3477ca2 Signed-off-by: Dave Barach --- src/plugins/unittest/bihash_test.c | 68 ++++++++++++++++++++++++- src/vppinfra/bihash_16_8.h | 2 + src/vppinfra/bihash_16_8_32.h | 3 ++ src/vppinfra/bihash_24_8.h | 2 + src/vppinfra/bihash_40_8.h | 2 + src/vppinfra/bihash_48_8.h | 2 + src/vppinfra/bihash_8_8.h | 2 + src/vppinfra/bihash_8_8_stats.h | 101 +++++++++++++++++++++++++++++++++++++ src/vppinfra/bihash_template.c | 18 +++++++ src/vppinfra/bihash_template.h | 68 +++++++++++++++++++++++-- src/vppinfra/bihash_vec8_8.h | 2 + 11 files changed, 264 insertions(+), 6 deletions(-) create mode 100644 src/vppinfra/bihash_8_8_stats.h (limited to 'src') diff --git a/src/plugins/unittest/bihash_test.c b/src/plugins/unittest/bihash_test.c index 5768d0e14ea..2dbc6b1b002 100644 --- a/src/plugins/unittest/bihash_test.c +++ b/src/plugins/unittest/bihash_test.c @@ -20,11 +20,26 @@ #include #include -#include +#include #include #include +typedef struct +{ + u64 alloc_add; + u64 add; + u64 split_add; + u64 replace; + u64 update; + u64 del; + u64 del_free; + u64 linear; + u64 resplit; + u64 working_copy_lost; + u64 *splits; +} bihash_stats_t; + typedef struct { volatile u32 thread_barrier; @@ -51,10 +66,53 @@ typedef struct /* convenience */ vlib_main_t *vlib_main; + + CLIB_CACHE_LINE_ALIGN_MARK (stat_align); + bihash_stats_t stats; + } bihash_test_main_t; static bihash_test_main_t bihash_test_main; +u8 * +format_bihash_stats (u8 * s, va_list * args) +{ + BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *); + int verbose = va_arg (*args, int); + int i; + bihash_stats_t *sp = h->inc_stats_context; + +#define _(a) s = format (s, "%20s: %lld\n", #a, sp->a); + foreach_bihash_stat; +#undef _ + for (i = 0; i < vec_len (sp->splits); i++) + { + if (sp->splits[i] > 0 || verbose) + s = format (s, " splits[%d]: %lld\n", 1 << i, sp->splits[i]); + } + return s; +} + + +static void +inc_stats_callback (BVT (clib_bihash) * h, int stat_id, u64 count) +{ + uword *statp = h->inc_stats_context; + bihash_stats_t *for_splits; + + if (PREDICT_TRUE (stat_id * sizeof (u64) + < STRUCT_OFFSET_OF (bihash_stats_t, splits))) + { + statp[stat_id] += count; + return; + } + + for_splits = h->inc_stats_context; + vec_validate (for_splits->splits, count); + for_splits->splits[count] += 1; +} + + static clib_error_t * test_bihash_vec64 (bihash_test_main_t * tm) { @@ -69,6 +127,7 @@ test_bihash_vec64 (bihash_test_main_t * tm) h = &tm->hash; BV (clib_bihash_init) (h, "test", user_buckets, user_memory_size); + BV (clib_bihash_set_stats_callback) (h, inc_stats_callback, &tm->stats); before = clib_time_now (&tm->clib_time); @@ -143,6 +202,7 @@ test_bihash_threads (bihash_test_main_t * tm) h = &tm->hash; BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); + BV (clib_bihash_set_stats_callback) (h, inc_stats_callback, &tm->stats); tm->thread_barrier = 1; @@ -176,6 +236,7 @@ test_bihash_threads (bihash_test_main_t * tm) 0.0 ? ((f64) ((u64) tm->nthreads * (u64) tm->nitems)) / delta : 0.0); + fformat (stdout, "Stats:\n%U", format_bihash_stats, h, 1 /* verbose */ ); BV (clib_bihash_free) (h); return 0; } @@ -204,6 +265,7 @@ test_bihash (bihash_test_main_t * tm) h = &tm->hash; BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); + BV (clib_bihash_set_stats_callback) (h, inc_stats_callback, &tm->stats); for (acycle = 0; acycle < tm->ncycles; acycle++) { @@ -384,6 +446,8 @@ test_bihash (bihash_test_main_t * tm) /* ASSERTs if any items remain */ BV (clib_bihash_foreach_key_value_pair) (h, count_items, 0); + fformat (stdout, "Stats:\n%U", format_bihash_stats, h, 1 /* verbose */ ); + BV (clib_bihash_free) (h); vec_free (tm->keys); @@ -407,6 +471,8 @@ test_bihash_command_fn (vlib_main_t * vm, tm->report_every_n = 50000; tm->seed = 0x1badf00d; + memset (&tm->stats, 0, sizeof (tm->stats)); + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) { if (unformat (input, "seed %u", &tm->seed)) diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h index f6515b8aea0..b6b0766b8ee 100644 --- a/src/vppinfra/bihash_16_8.h +++ b/src/vppinfra/bihash_16_8.h @@ -14,6 +14,8 @@ */ #undef BIHASH_TYPE #undef BIHASH_KVP_PER_PAGE +#undef BIHASH_32_64_SVM +#undef BIHASH_ENABLE_STATS #define BIHASH_TYPE _16_8 #define BIHASH_KVP_PER_PAGE 4 diff --git a/src/vppinfra/bihash_16_8_32.h b/src/vppinfra/bihash_16_8_32.h index 3e83ad2c52f..e66954f4838 100644 --- a/src/vppinfra/bihash_16_8_32.h +++ b/src/vppinfra/bihash_16_8_32.h @@ -14,6 +14,9 @@ */ #undef BIHASH_TYPE #undef BIHASH_KVP_PER_PAGE +#undef BIHASH_32_64_SVM +#undef BIHASH_ENABLE_STATS + #define BIHASH_TYPE _16_8_32 #define BIHASH_KVP_PER_PAGE 4 diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h index 6d1cdd310bd..463521d8126 100644 --- a/src/vppinfra/bihash_24_8.h +++ b/src/vppinfra/bihash_24_8.h @@ -14,6 +14,8 @@ */ #undef BIHASH_TYPE #undef BIHASH_KVP_PER_PAGE +#undef BIHASH_32_64_SVM +#undef BIHASH_ENABLE_STATS #define BIHASH_TYPE _24_8 #define BIHASH_KVP_PER_PAGE 4 diff --git a/src/vppinfra/bihash_40_8.h b/src/vppinfra/bihash_40_8.h index b85adb09712..b50e5eb5ac4 100644 --- a/src/vppinfra/bihash_40_8.h +++ b/src/vppinfra/bihash_40_8.h @@ -15,6 +15,8 @@ #undef BIHASH_TYPE #undef BIHASH_KVP_PER_PAGE +#undef BIHASH_32_64_SVM +#undef BIHASH_ENABLE_STATS #define BIHASH_TYPE _40_8 #define BIHASH_KVP_PER_PAGE 4 diff --git a/src/vppinfra/bihash_48_8.h b/src/vppinfra/bihash_48_8.h index 328a90b0fd4..2a6381faa61 100644 --- a/src/vppinfra/bihash_48_8.h +++ b/src/vppinfra/bihash_48_8.h @@ -15,6 +15,8 @@ #undef BIHASH_TYPE #undef BIHASH_KVP_PER_PAGE +#undef BIHASH_32_64_SVM +#undef BIHASH_ENABLE_STATS #define BIHASH_TYPE _48_8 #define BIHASH_KVP_PER_PAGE 4 diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h index 604cf30808f..a4a18a1d7eb 100644 --- a/src/vppinfra/bihash_8_8.h +++ b/src/vppinfra/bihash_8_8.h @@ -14,6 +14,8 @@ */ #undef BIHASH_TYPE #undef BIHASH_KVP_PER_PAGE +#undef BIHASH_32_64_SVM +#undef BIHASH_ENABLE_STATS #define BIHASH_TYPE _8_8 #define BIHASH_KVP_PER_PAGE 4 diff --git a/src/vppinfra/bihash_8_8_stats.h b/src/vppinfra/bihash_8_8_stats.h new file mode 100644 index 00000000000..a6c947ab5c4 --- /dev/null +++ b/src/vppinfra/bihash_8_8_stats.h @@ -0,0 +1,101 @@ +/* + * Copyright (c) 2015 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#undef BIHASH_TYPE +#undef BIHASH_KVP_PER_PAGE +#undef BIHASH_32_64_SVM +#undef BIHASH_ENABLE_STATS + +#define BIHASH_TYPE _8_8_stats +#define BIHASH_KVP_PER_PAGE 4 +#define BIHASH_ENABLE_STATS 1 + +#ifndef __included_bihash_8_8_stats_h__ +#define __included_bihash_8_8__stats_h__ + +#include +#include +#include +#include +#include + +/** 8 octet key, 8 octet key value pair */ +typedef struct +{ + u64 key; /**< the key */ + u64 value; /**< the value */ +} clib_bihash_kv_8_8_stats_t; + +/** Decide if a clib_bihash_kv_8_8_t instance is free + @param v- pointer to the (key,value) pair +*/ +static inline int +clib_bihash_is_free_8_8_stats (clib_bihash_kv_8_8_stats_t * v) +{ + if (v->key == ~0ULL && v->value == ~0ULL) + return 1; + return 0; +} + +/** Hash a clib_bihash_kv_8_8_t instance + @param v - pointer to the (key,value) pair, hash the key (only) +*/ +static inline u64 +clib_bihash_hash_8_8_stats (clib_bihash_kv_8_8_stats_t * v) +{ + /* Note: to torture-test linear scan, make this fn return a constant */ +#ifdef clib_crc32c_uses_intrinsics + return clib_crc32c ((u8 *) & v->key, 8); +#else + return clib_xxhash (v->key); +#endif +} + +/** Format a clib_bihash_kv_8_8_t instance + @param s - u8 * vector under construction + @param args (vararg) - the (key,value) pair to format + @return s - the u8 * vector under construction +*/ +static inline u8 * +format_bihash_kvp_8_8_stats (u8 * s, va_list * args) +{ + clib_bihash_kv_8_8_stats_t *v = + va_arg (*args, clib_bihash_kv_8_8_stats_t *); + + s = format (s, "key %llu value %llu", v->key, v->value); + return s; +} + +/** Compare two clib_bihash_kv_8_8_t instances + @param a - first key + @param b - second key +*/ +static inline int +clib_bihash_key_compare_8_8_stats (u64 a, u64 b) +{ + return a == b; +} + +#undef __included_bihash_template_h__ +#include + +#endif /* __included_bihash_8_8_stats_h__ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 2840342a5ce..9de1df4c59c 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -291,6 +291,9 @@ BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b) (h, sizeof (working_copy[0]) * (1 << b->log2_pages)); h->working_copy_lengths[thread_index] = b->log2_pages; h->working_copies[thread_index] = working_copy; + + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_working_copy_lost, + 1ULL << b->log2_pages); } v = BV (clib_bihash_get_value) (h, b->offset); @@ -442,6 +445,8 @@ static inline int BV (clib_bihash_add_del_inline) CLIB_MEMORY_BARRIER (); b->as_u64 = tmp_b.as_u64; /* unlocks the bucket */ + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_alloc_add, 1); + return (0); } @@ -473,6 +478,7 @@ static inline int BV (clib_bihash_add_del_inline) CLIB_MEMORY_BARRIER (); /* Add a delay */ clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v)); BV (clib_bihash_unlock_bucket) (b); + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1); return (0); } } @@ -495,6 +501,7 @@ static inline int BV (clib_bihash_add_del_inline) b->refcnt++; ASSERT (b->refcnt > 0); BV (clib_bihash_unlock_bucket) (b); + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_add, 1); return (0); } } @@ -508,6 +515,7 @@ static inline int BV (clib_bihash_add_del_inline) CLIB_MEMORY_BARRIER (); clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v)); BV (clib_bihash_unlock_bucket) (b); + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1); return (0); } } @@ -527,6 +535,7 @@ static inline int BV (clib_bihash_add_del_inline) { b->refcnt--; BV (clib_bihash_unlock_bucket) (b); + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1); return (0); } else /* yes, free it */ @@ -544,6 +553,8 @@ static inline int BV (clib_bihash_add_del_inline) v = BV (clib_bihash_get_value) (h, tmp_b.offset); BV (value_free) (h, v, tmp_b.log2_pages); BV (clib_bihash_alloc_unlock) (h); + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del_free, + 1); return (0); } } @@ -562,9 +573,12 @@ static inline int BV (clib_bihash_add_del_inline) old_log2_pages = h->saved_bucket.log2_pages; new_log2_pages = old_log2_pages + 1; mark_bucket_linear = 0; + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_split_add, 1); + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, old_log2_pages); working_copy = h->working_copies[thread_index]; resplit_once = 0; + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, 1); new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages, new_log2_pages); @@ -585,7 +599,11 @@ static inline int BV (clib_bihash_add_del_inline) BV (split_and_rehash_linear) (h, working_copy, old_log2_pages, new_log2_pages); mark_bucket_linear = 1; + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_linear, 1); } + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_resplit, 1); + BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, + old_log2_pages + 1); } /* Try to add the new entry */ diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 98dcf14673f..d145b61952a 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -52,6 +52,10 @@ #define __bvt(a,b) _bvt(a,b) #define BVT(a) __bvt(a,BIHASH_TYPE) +#define _bvs(a,b) struct a##b +#define __bvs(a,b) _bvs(a,b) +#define BVS(a) __bvs(a,BIHASH_TYPE) + #if _LP64 == 0 #define OVERFLOW_ASSERT(x) ASSERT(((x) & 0xFFFFFFFF00000000ULL) == 0) #define u64_to_pointer(x) (void *)(u32)((x)) @@ -113,14 +117,15 @@ typedef CLIB_PACKED (struct { STATIC_ASSERT_SIZEOF (BVT (clib_bihash_shared_header), 8 * sizeof (u64)); -typedef struct +typedef +BVS (clib_bihash) { BVT (clib_bihash_bucket) * buckets; volatile u32 *alloc_lock; - BVT (clib_bihash_value) ** working_copies; + BVT (clib_bihash_value) ** working_copies; int *working_copy_lengths; - BVT (clib_bihash_bucket) saved_bucket; + BVT (clib_bihash_bucket) saved_bucket; u32 nbuckets; u32 log2_nbuckets; @@ -129,10 +134,10 @@ typedef struct u64 *freelists; #if BIHASH_32_64_SVM - BVT (clib_bihash_shared_header) * sh; + BVT (clib_bihash_shared_header) * sh; int memfd; #else - BVT (clib_bihash_shared_header) sh; + BVT (clib_bihash_shared_header) sh; #endif u64 alloc_arena; /* Base of the allocation arena */ @@ -142,6 +147,14 @@ typedef struct */ format_function_t *fmt_fn; + /** Optional statistics-gathering callback */ +#if BIHASH_ENABLE_STATS + void (*inc_stats_callback) (BVS (clib_bihash) *, int stat_id, u64 count); + + /** Statistics callback context (e.g. address of stats data structure) */ + void *inc_stats_context; +#endif + } BVT (clib_bihash); #if BIHASH_32_64_SVM @@ -164,6 +177,51 @@ typedef struct #define CLIB_BIHASH_READY_MAGIC 0 #endif +#ifndef BIHASH_STAT_IDS +#define BIHASH_STAT_IDS 1 + +#define foreach_bihash_stat \ +_(alloc_add) \ +_(add) \ +_(split_add) \ +_(replace) \ +_(update) \ +_(del) \ +_(del_free) \ +_(linear) \ +_(resplit) \ +_(working_copy_lost) \ +_(splits) /* must be last */ + +typedef enum +{ +#define _(a) BIHASH_STAT_##a, + foreach_bihash_stat +#undef _ + BIHASH_STAT_N_STATS, +} BVT (clib_bihash_stat_id); +#endif /* BIHASH_STAT_IDS */ + +static inline void BV (clib_bihash_increment_stat) (BVT (clib_bihash) * h, + int stat_id, u64 count) +{ +#if BIHASH_ENABLE_STATS + if (PREDICT_FALSE (h->inc_stats_callback != 0)) + h->inc_stats_callback (h, stat_id, count); +#endif +} + +#if BIHASH_ENABLE_STATS +static inline void BV (clib_bihash_set_stats_callback) + (BVT (clib_bihash) * h, void (*cb) (BVT (clib_bihash) *, int, u64), + void *ctx) +{ + h->inc_stats_callback = cb; + h->inc_stats_context = ctx; +} +#endif + + static inline void BV (clib_bihash_alloc_lock) (BVT (clib_bihash) * h) { while (__atomic_test_and_set (h->alloc_lock, __ATOMIC_ACQUIRE)) diff --git a/src/vppinfra/bihash_vec8_8.h b/src/vppinfra/bihash_vec8_8.h index 2394600ba7c..f50234e5d97 100644 --- a/src/vppinfra/bihash_vec8_8.h +++ b/src/vppinfra/bihash_vec8_8.h @@ -14,6 +14,8 @@ */ #undef BIHASH_TYPE #undef BIHASH_KVP_PER_PAGE +#undef BIHASH_32_64_SVM +#undef BIHASH_ENABLE_STATS #define BIHASH_TYPE _vec8_8 #define BIHASH_KVP_PER_PAGE 4 -- cgit 1.2.3-korg