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

[Thomas Gleixner]

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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/