On Tue, Aug 16, 2011 at 06:20:05PM -0400, Bob Copeland wrote:
> On Tue, Aug 16, 2011 at 12:48 PM, Josh Boyer <jwboyer@xxxxxxxxxx> wrote:
> > it seems we're getting a negative number in this particular calculation
> > in fs/minix/bitmap.c, count_free:
> >
> > i = ((numbits - (numblocks-1) * bh->b_size * 8) / 16) * 2;
> [...]
> > I'm not familiar enough with minixfs to know what the above is trying to
> > actually accomplish. I instrumented that function a bit and here is
> > some data from the 3 filesytems in question:
>
> I don't know minix either but I'll take a shot. This is trying to
> count the number of bits in the free map for inodes or data blocks
> that don't fit in a full file system block.
>
> count_free takes 3 params:
> map - an array of buffer heads that represent the free map for a 'thingy'
> (thingy being the technical term for inode, or data block)
> numblocks - the number of blocks to scan
> numbits - the maximum-valued thingy
>
> So, for example, there might be 4800 inodes in the filesystem. That
> means there are 4800/8 = 600 bits to represent their in-use state,
> and supposing a buffer head represents a 512-byte buffer (bh->b_size=512),
> you would need two blocks to store that. numblocks in this hypothetical
> example is 2 and numbits is 4801.
Yep, I gathered that. In the real case, there are 7 blocks, and the
block size of the fs is 4096. Though numbits still seems to be "maximum
number of blocks" based on the value and what is being passed to
count_free.
> Here's some annotated code with uninteresting parts removed:
>
> Loop over all but the last block:
>
> for (i=0; i<numblocks-1; i++) {
> sum += nibblemap[bh->b_data[j] & 0xf]
> + nibblemap[(bh->b_data[j]>>4) & 0xf];
> }
>
> Since we're counting zero bits this is just computing hweight(~x)...
>
> if (numblocks==0 || !(bh=map[numblocks-1]))
> return(0);
>
> Lookout, bh is assigned in the conditional!
>
> Ok so bh is the last block which might not be full of thingys, so
> we only want to look at the part that has thingys and not the rest.
>
> numblocks - 1 * bh->b_size * 8 is the number of bits we've already
> looked at. We'll call it nthingys. numbits - nthingys is the number
> of bits we want to continue to look at. "(x / 16) * 2 is a fancy way
Yes, except here numbits - nthingys winds up being a negative number in
the failing case.
> of saying "x / 8" except the result is on 2-byte boundaries. So that's
> the number of bytes left to look at, except for up to 15 possible
> extra bits.
>
> i = ((numbits - (numblocks-1) * bh->b_size * 8) / 16) * 2;
> for (j=0; j<i; j++) {
> sum += nibblemap[bh->b_data[j] & 0xf]
> + nibblemap[(bh->b_data[j]>>4) & 0xf];
> }
And we blow up in here somewhere.
> And then count the remaining 15 bits by masking off whatever portion
> is less than numbits and doing some fancy u16 casting.
>
> i = numbits%16;
> if (i!=0) {
> i = *(__u16 *)(&bh->b_data[j]) | ~((1<<i) - 1);
> sum += nibblemap[i & 0xf] + nibblemap[(i>>4) & 0xf];
> sum += nibblemap[(i>>8) & 0xf] + nibblemap[(i>>12) & 0xf];
> }
>
> return(sum);
> }
>
> Does that help?
It helps me understand what the code is doing a bit better, yes. Thank
you for that. Unfortunately, it doesn't really tell me why we get a
negative number in this case, and if we should be checking for that here
and what to do about it.
josh
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
