Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.

[Paul Mundt]

On Thu, Jan 19, 2006 at 09:28:30PM -0600, James Bottomley wrote:
> On Wed, 2006-01-18 at 19:11 -0800, Paul Jackson wrote:
> > Could you look Mundt's patch, and see if it looks ok?
> 
> Not being on lkml, this was harder than it sounds, but I eventually
> found the actual patch on marc.  However, no, it doesn't look right.
> 
> This:
> 
> > +		/* find space in the bitmap */
> > +		for (j = 0; j < span; j++)
> > +			if ((bitmap[index + j] & (mask << offset))) {
> 
> 
> Is wrong.  You're looking for an unset span of order bits at a given
> offset.  So you get the byte offset for the first, then all the
> following bitmap[n] need to be zero until you need to do an offset in
> reverse for the last bit.  i.e. (assuming BITS_PER_LONG=32) for a span
> of 126 at offset 1, you check
> 
> bitmap[0] & 0xfffffffe == 0
> bitmap[1] & 0xffffffff == 0
> bitmap[2] & 0xffffffff == 0
> bitmap[3] & 0x7fffffff == 0
> 
> and so on.
> 
This code operates on the assumption that offset is always 0 for the
pages == BITS_PER_LONG case. It's calculated in this order:

        unsigned int pages = 1 << order;
        int i;
        int span = (pages + (BITS_PER_LONG - 1)) / BITS_PER_LONG;

        if (pages > BITS_PER_LONG)
                pages = BITS_PER_LONG;

...
        for (i = 0; i < bits; i += pages) {
                int index = i/BITS_PER_LONG;
                int offset = i - (index * BITS_PER_LONG);
...

So in the case of pages >= BITS_PER_LONG the mask will be 0xffffffff, and
offset will be 0, and the span will define how many adjacent words we
need to set. Unless I'm missing something, I don't see how your case
would happen. I did test this quite a bit mixing both tiny and large
orders.

Attachment: pgp00000.pgp
Description: PGP signature