On Tue, 15 Aug 2023 12:44:21 -0600
Ross Zwisler <zwisler@xxxxxxxxxx> wrote:
> 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
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;
> > }
|