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

[Steven Rostedt <rostedt@goodmis.org>]

On Tue, 15 Aug 2023 12:44:21 -0600
Ross Zwisler <zwisler@google.com> wrote:

> 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

As this is under an MIT license, I created this without looking at the GPL version.

It's really too small and common to be licensed, but still. I'll make the update.


> 
> > +#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.

I actually purposely kept the "hist" name (teval->hist) for this local file.

Just because that's what Stevie called it ;-)

-- Steve

> 
> >  {
> > -	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;
> >  }