Re: 2.4.19pre2aa1

[Andrea Arcangeli <andrea@suse.de>]

On Thu, Mar 07, 2002 at 03:38:09PM -0500, Richard B. Johnson wrote:
> On Thu, 7 Mar 2002, William Lee Irwin III wrote:
> 
> > On Thu, Mar 07, 2002 at 06:03:00PM +0100, Andrea Arcangeli wrote:
> > > For the other points I think you shouldn't really complain (both at
> > > runtime and in code style as well, please see how clean it is with the
> > > wait_table_t thing), I made a definitive improvement to your code, the
> > > only not obvious part is the hashfn but I really cannot see yours
> > > beating mine because of the total random input, infact it could be the
> > > other way around due the fact if something there's the probability the
> > > pages are physically consecutive and I take care of that fine.
> > 
> > 
> > I don't know whose definition of clean code this is:
> > 
> > +static inline wait_queue_head_t * wait_table_hashfn(struct page * page, wait_table_t * wait_table)
> > +{
> > +#define i (((unsigned long) page)/(sizeof(struct page) & ~ (sizeof(struct page) - 1)))
> > +#define s(x) ((x)+((x)>>wait_table->shift))
> > +	return wait_table->head + (s(i) & (wait_table->size-1));
> > +#undef i
> > +#undef s
> > +}
> > 
> > 
> > I'm not sure I want to find out.
> > 
> > 
> > Bill
> 
> Methinks there is entirely too much white-space in the code. It
> is almost readable *;). It probably could be fixed up to slip through
> the compiler with no possibility of human interpretation, but that would
> take a bit more work ;^)

well, to me it is very readable, but I'm certainly biased I admit.

You have to think it this way:

-	"i" is the random not predictable input
-	"i" is generated by dropping the non random bits of the "page"
		with a cute trick that drops the bit with
		a shiftright with an immediate argument, it's not a
		division so it's faster it could been
		"page/sizeof(struct page)" but it would been slower
-	s(i) takes into account not just the last "wait_table->shift" bytes
	of the random information in "i", but also the next "shift"
	bytes, so it's more random even if some of those lower or higher
	bits is generating patterns for whatever reason
-	finally you mask out the resulting random information s(i) with
	size-1, so you fit into the wait_table->head memory.

The result is that it exploits most of the random input, and physically
consecutive pages are liekly to use the same cacheline in case there is
some pattern. That looks a good algorithm to me.

Andrea