get_order() broken !

get_order() broken !

[Benjamin Herrenschmidt]

Ok, maybe I have lots of shit in my eyes.... but it looks like get_order
in asm-generic/page.h is broken.

AFAIK, get_order() should round up (and we have code here or there
assuming such).

However, it seems to assume that ilog2 rounds up, which it doesn't. It
rounds down. At least the generic implementation seems to do so and the
powerpc optimized one too.

So I end up for example with get_order(0x1020) returning ... 0 (which
explains some memory corruption problems I'm having on ppc32 among
others0.

So who is right and who is wrong ? Should we audit all users of these
things ?

Cheers,
Ben.

Re: get_order() broken !

[Linus Torvalds]

On Tue, 6 Mar 2007, Benjamin Herrenschmidt wrote:
>
> Ok, maybe I have lots of shit in my eyes.... but it looks like get_order
> in asm-generic/page.h is broken.
> 
> AFAIK, get_order() should round up (and we have code here or there
> assuming such).
> 
> However, it seems to assume that ilog2 rounds up, which it doesn't. It
> rounds down. At least the generic implementation seems to do so and the
> powerpc optimized one too.

Yeah, I think the recent get_order() changes to change it to use ilog2() 
are just crap. I actually looked at it when it went in, but I assumed that 
it had been tested. I don't think it has.

Let's just revert that entirely.

David, quick comments before I undo commit 39d61db0?

		Linus

Re: get_order() broken !

[David Howells]

Linus Torvalds <torvalds@linux-foundation.org> wrote:

> Yeah, I think the recent get_order() changes to change it to use ilog2() 
> are just crap. I actually looked at it when it went in, but I assumed that 
> it had been tested. I don't think it has.

It had, it's just that the testing totally failed to show up the problem; that
and I think my userspace testing went wrong because I made the wrong
assumptions about what the answer should be.

However, having discussed it with Ben, HPA and David Woodhouse and others I've
come up with a patch (sent separately) that should fix it by using:

	ilog2((n) - 1) + 1 

as the basis for the calculation as this should round up the result.  I've
encapsulated this as a function called ilog2_up() and fixed the docs to make
it cleared how ilog2() and co actually work.

David