lkml.org 
[lkml]   [2011]   [Aug]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: Oops in minixfs_statfs
From
On Tue, Aug 16, 2011 at 12:48 PM, Josh Boyer <jwboyer@redhat.com> 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.

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
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 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?

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

\
 
 \ /
  Last update: 2011-08-17 00:23    [W:0.062 / U:0.108 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site