Re: [patch 1/2] infrastructure to debug (dynamic) objects

Thomas Gleixner
2008-03-02T10:07:03Z

On Sat, 1 Mar 2008, Peter Zijlstra wrote:
> On Sat, 2008-03-01 at 12:44 +0100, Thomas Gleixner wrote:
> > On Sat, 1 Mar 2008, Andrew Morton wrote:
>
> > > > +
> > > > +#define ODEBUG_HASH_SIZE 4096
> > >
> > > power-of-2 is said to be a very poor size for a hash table.
> >
> > The hash is not a randomized hash as one would expect. It's purely
> > generated from the object address to simplify the lookup during the
> > free check. So the power of 2 size is a good thing :) /me adds
> > comment.
>
> Power of two buckets work when used along with a golden ratio based hash
> map - as done by linux/hash.h.
>
> Power of two hash maps otoh suck royally.

Well, using a real hash algorithm sucks royally if you need to do the
reverse check on *free(). With the direct object address to hash
bucket mapping we have usually only one bucket to look at, otherwise
we end up looking at multiple buckets and doing the list walk on each
of them. We have to decide which suckage is worse :)

Thanks,
tglx