On Fri, Aug 11, 2023 at 01:39:30AM -0400, Steven Rostedt wrote:
> From: "Steven Rostedt (Google)" <rostedt@xxxxxxxxxxx>
>
> The lookups need to be extremely fast. Instead of doing a linear search
> across all entries (which could be thousands), do a hash lookup instead.
>
> Signed-off-by: Steven Rostedt (Google) <rostedt@xxxxxxxxxxx>
> ---
> include/traceeval-hist.h | 7 ++
> src/histograms.c | 172 +++++++++++++++++++++++++++++++++------
> 2 files changed, 153 insertions(+), 26 deletions(-)
>
> diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> index 412efdbe8681..4baed4237787 100644
> --- a/include/traceeval-hist.h
> +++ b/include/traceeval-hist.h
<>
> @@ -12,6 +13,14 @@
>
> #include <traceeval-hist.h>
>
> +#define offset_of(type, field) (&(((type *)(NULL))->field))
This currently returns a pointer type, but the kernel implementation(s) have
this cast back to a size_t, which makes sense I think.
https://elixir.bootlin.com/linux/latest/source/tools/include/nolibc/types.h#L220
> +#define container_of(ptr, type, field) \
> + (type *)((void *)(ptr) - (void *)offset_of(type, field))
> +
> +#define HASH_BITS 10 /* Start with 1K of buckets */
> +#define HASH_SIZE(bits) (1 << (bits))
> +#define HASH_MASK(bits) (HASH_SIZE(bits) - 1)
> +
> /*
> * Compare two integers of variable length.
> *
<>
> @@ -365,16 +406,19 @@ static void clean_entry(struct entry *entry, struct traceeval *teval)
> */
> static void hist_table_release(struct traceeval *teval)
This probably wants to be 'hash_table_release()' now since 'hist_table' is
gone.
> {
> - struct hist_table *hist = teval->hist;
> + struct hash_table *hist = teval->hist;
>
> if (!hist)
> return;
>
> - for (size_t i = 0; i < hist->nr_entries; i++) {
> - clean_entry(hist->map + i, teval);
> + for (size_t i = 0; i < HASH_SIZE(hist->bits); i++) {
> + if (!hist->hash[i])
> + continue;
> +
> + free_entries(teval, hist->hash[i]);
> }
>
> - free(hist->map);
> + free(hist->hash);
> free(hist);
> teval->hist = NULL;
> }
|