Re: [PATCH v2 07/17] libtraceeval: Convert hist array into a hash table

[Ross Zwisler <zwisler@google.com>]

On Fri, Aug 11, 2023 at 01:39:30AM -0400, Steven Rostedt wrote:
> From: "Steven Rostedt (Google)" <rostedt@goodmis.org>
> 
> 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@goodmis.org>
> ---
>  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;
>  }