Oops in minixfs_statfs

Oops in minixfs_statfs

[Josh Boyer]

We've had a bug open in Fedora for a while[1] where it's fairly easy to
generate an oops on a MinixV3 filesystem.  I've looked at it a bit and
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;

which causes the loop below it to access bh->b_data outside it's bounds.

I installed minix 3.1.8 (shoot me now) in a KVM guest today, and two out
of the three filesystems work fine.  / and /home are both relatively
small, and a df seems to return fairly accurate numbers.  However, a df
on /usr (which is ~768M) causes the oops.

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:

[   49.114984] imap_blocks 2 zmap_blocks 1 firstdatazone 205
log_zone_size 0 max_size 7fffffff magic 4d5a nzones 4000 blocksize: 1000

[   66.380824] imap_blocks 2 zmap_blocks 2 firstdatazone 2a2
log_zone_size 0 max_size 7fffffff magic 4d5a nzones a700 blocksize: 1000

[  516.859103] imap_blocks 7 zmap_blocks 7 firstdatazone c11
log_zone_size 0 max_size 7fffffff magic 4d5a nzones 3001c blocksize:
1000

The calculation of i on line 38 results in fffffe80 for the last
filesytem when minix_count_free_blocks is called for it.

Does anyone have an idea of what that particular section is trying to
count?  (As an aside, the numbits variable is slightly confusing because
it seems to be a number of blocks, not bits).  I'd be happy to continue
to poke at this, but I'm a bit stumped at the moment.

Oops output below.

josh

[1] https://bugzilla.redhat.com/show_bug.cgi?id=635266 (which is also
https://bugzilla.kernel.org/show_bug.cgi?id=18792)

[  518.991374] BUG: unable to handle kernel paging request at ffff88002fffd000
[  518.991379] IP: [<ffffffffa015c116>] count_free+0x116/0x1d4 [minix]
[  518.991385] PGD 1a06063 PUD 1a0a063 PMD 2fffa067 PTE 0
[  518.991389] Oops: 0000 [#1] SMP 
[  518.991396] CPU 0 
[  518.991397] Modules linked in: minix bnep bluetooth rfkill ip6t_REJECT nf_conntrack_ipv6 nf_defrag_ipv6 nf_conntrack_ipv4 nf_defrag_ipv4 ip6table_filter xt_state nf_conntrack ip6_tables joydev microcode snd_hda_intel snd_hda_codec snd_hwdep snd_seq snd_seq_device snd_pcm snd_timer virtio_net virtio_balloon i2c_piix4 snd soundcore snd_page_alloc i2c_core uinput virtio_blk [last unloaded: minix]
[  518.991419] 
[  518.991421] Pid: 1140, comm: df Not tainted 3.1.0-0.rc2.git0.1.1.fc17.x86_64 #1 Bochs Bochs
[  518.991423] RIP: 0010:[<ffffffffa015c116>]  [<ffffffffa015c116>] count_free+0x116/0x1d4 [minix]
[  518.991427] RSP: 0018:ffff88001b6dfdd8  EFLAGS: 00010282
[  518.991428] RAX: 0000000015dc0000 RBX: 0000000083643b08 RCX: 0000000000000000
[  518.991430] RDX: ffff88001a23d000 RSI: 0000000000000001 RDI: 0000000000000202
[  518.991431] RBP: ffff88001b6dfe08 R08: 0000000000000002 R09: 0000000000000000
[  518.991432] R10: 0000ffff00066c0a R11: 0000000000000000 R12: ffff880011a1f870
[  518.991434] R13: 000000000002f40a R14: 00000000fffffe80 R15: 0000000000000006
[  518.991438] FS:  00007fd795a39720(0000) GS:ffff88002ee00000(0000) knlGS:0000000000000000
[  518.991439] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  518.991441] CR2: ffff88002fffd000 CR3: 0000000012323000 CR4: 00000000000006f0
[  518.991447] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[  518.991450] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400
[  518.991452] Process df (pid: 1140, threadinfo ffff88001b6de000, task ffff88001c6c0000)
[  518.991453] Stack:
[  518.991454]  0000000000000000 ffff880015f14390 ffff880015f14390 0000000000800017
[  518.991458]  0000000000000000 0000000000000000 ffff88001b6dfe28 ffffffffa015c391
[  518.991461]  0000000000000000 ffff88001b6dfef0 ffff88001b6dfe58 ffffffffa015e4c0
[  518.991464] Call Trace:
[  518.991467]  [<ffffffffa015c391>] minix_count_free_blocks+0x25/0x30 [minix]
[  518.991470]  [<ffffffffa015e4c0>] minix_statfs+0x58/0xaf [minix]
[  518.991486]  [<ffffffff8116862e>] statfs_by_dentry+0x56/0x6e
[  518.991489]  [<ffffffff81168661>] vfs_statfs+0x1b/0x94
[  518.991491]  [<ffffffff81168711>] user_statfs+0x37/0x4d
[  518.991494]  [<ffffffff8116878d>] sys_statfs+0x20/0x3f
[  518.991506]  [<ffffffff814f9419>] ? retint_swapgs+0x13/0x1b
[  518.991509]  [<ffffffff814ffdc2>] system_call_fastpath+0x16/0x1b
[  518.991510] Code: 16 a0 4a 8d 04 c5 00 00 00 00 49 0f af c7 49 29 c6 31 c0 49 c1 ee 04 45 01 f6 44 89 f1 e8 cb 20 39 e1 31 c0 eb 25 49 8b 54 24 28 <8a> 14 02 48 ff c0 48 89 d1 c0 fa 04 83 e1 0f 83 e2 0f 03 1c 8d 
[  518.991536] RIP  [<ffffffffa015c116>] count_free+0x116/0x1d4 [minix]
[  518.991539]  RSP <ffff88001b6dfdd8>
[  518.991540] CR2: ffff88002fffd000
[  518.991542] ---[ end trace 323fbee5fddba095 ]---
[  518.991548] BUG: sleeping function called from invalid context at kernel/rwsem.c:21
[  518.991549] in_atomic(): 0, irqs_disabled(): 1, pid: 1140, name: df
[  518.991551] INFO: lockdep is turned off.
[  518.991552] irq event stamp: 10574
[  518.991553] hardirqs last  enabled at (10573): [<ffffffff814f9434>] restore_args+0x0/0x30
[  518.991556] hardirqs last disabled at (10574): [<ffffffff814f98f6>] error_sti+0x5/0x6
[  518.991559] softirqs last  enabled at (10572): [<ffffffff81062c90>] __do_softirq+0x200/0x25a
[  518.991568] softirqs last disabled at (10557): [<ffffffff815020bc>] call_softirq+0x1c/0x30
[  518.991572] Pid: 1140, comm: df Tainted: G      D     3.1.0-0.rc2.git0.1.1.fc17.x86_64 #1
[  518.991573] Call Trace:
[  518.991580]  [<ffffffff8108dbd8>] ? print_irqtrace_events+0x9e/0xa2
[  518.991591]  [<ffffffff8104f7a6>] __might_sleep+0x103/0x108
[  518.991594]  [<ffffffff814f7bd4>] down_read+0x26/0x84
[  518.991599]  [<ffffffff8107dde3>] ? hrtimer_try_to_cancel+0x81/0x8f
[  518.991605]  [<ffffffff810a14ff>] acct_collect+0x4d/0x188
[  518.991608]  [<ffffffff81060062>] do_exit+0x223/0x831
[  518.991611]  [<ffffffff8105de56>] ? kmsg_dump+0x131/0x14f
[  518.991613]  [<ffffffff8105ddae>] ? kmsg_dump+0x89/0x14f
[  518.991615]  [<ffffffff814fa341>] oops_end+0xbc/0xc5
[  518.991619]  [<ffffffff814ed939>] no_context+0x208/0x217
[  518.991622]  [<ffffffff814edb18>] __bad_area_nosemaphore+0x1d0/0x1f1
[  518.991625]  [<ffffffff814f9013>] ? _raw_spin_unlock+0x28/0x3b
[  518.991627]  [<ffffffff814ed1aa>] ? pte_offset_kernel+0x19/0x3f
[  518.991629]  [<ffffffff814edb4c>] bad_area_nosemaphore+0x13/0x15
[  518.991631]  [<ffffffff814fc458>] do_page_fault+0x1b1/0x3a2
[  518.991633]  [<ffffffff8108b85d>] ? trace_hardirqs_off+0xd/0xf
[  518.991636]  [<ffffffff814f8fc8>] ? _raw_spin_unlock_irqrestore+0x3e/0x61
[  518.991638]  [<ffffffff8105cf16>] ? console_unlock+0x203/0x212
[  518.991640]  [<ffffffff8108b7f3>] ? trace_hardirqs_off_caller+0x33/0x90
[  518.991647]  [<ffffffff81252f2d>] ? trace_hardirqs_off_thunk+0x3a/0x3c
[  518.991650]  [<ffffffff814f96b5>] page_fault+0x25/0x30
[  518.991653]  [<ffffffffa015c116>] ? count_free+0x116/0x1d4 [minix]
[  518.991657]  [<ffffffffa015c10d>] ? count_free+0x10d/0x1d4 [minix]
[  518.991659]  [<ffffffffa015c391>] minix_count_free_blocks+0x25/0x30 [minix]
[  518.991662]  [<ffffffffa015e4c0>] minix_statfs+0x58/0xaf [minix]
[  518.991664]  [<ffffffff8116862e>] statfs_by_dentry+0x56/0x6e
[  518.991667]  [<ffffffff81168661>] vfs_statfs+0x1b/0x94
[  518.991669]  [<ffffffff81168711>] user_statfs+0x37/0x4d
[  518.991671]  [<ffffffff8116878d>] sys_statfs+0x20/0x3f
[  518.991674]  [<ffffffff814f9419>] ? retint_swapgs+0x13/0x1b
[  518.991676]  [<ffffffff814ffdc2>] system_call_fastpath+0x16/0x1b

Re: Oops in minixfs_statfs

[Bob Copeland]

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

Re: Oops in minixfs_statfs

[Bob Copeland]

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-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Oops in minixfs_statfs

[Josh Boyer]

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@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.

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

Re: Oops in minixfs_statfs

[Josh Boyer]

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@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.

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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Oops in minixfs_statfs

[Al Viro]

On Tue, Aug 16, 2011 at 12:48:09PM -0400, Josh Boyer wrote:
> We've had a bug open in Fedora for a while[1] where it's fairly easy to
> generate an oops on a MinixV3 filesystem.  I've looked at it a bit and
> 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;
> 
> which causes the loop below it to access bh->b_data outside it's bounds.
> 
> I installed minix 3.1.8 (shoot me now) in a KVM guest today, and two out
> of the three filesystems work fine.  / and /home are both relatively
> small, and a df seems to return fairly accurate numbers.  However, a df
> on /usr (which is ~768M) causes the oops.
> 
> 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:
> 
> [   49.114984] imap_blocks 2 zmap_blocks 1 firstdatazone 205
> log_zone_size 0 max_size 7fffffff magic 4d5a nzones 4000 blocksize: 1000
> 
> [   66.380824] imap_blocks 2 zmap_blocks 2 firstdatazone 2a2
> log_zone_size 0 max_size 7fffffff magic 4d5a nzones a700 blocksize: 1000
> 
> [  516.859103] imap_blocks 7 zmap_blocks 7 firstdatazone c11
> log_zone_size 0 max_size 7fffffff magic 4d5a nzones 3001c blocksize:
> 1000
> 
> The calculation of i on line 38 results in fffffe80 for the last
> filesytem when minix_count_free_blocks is called for it.
> 
> Does anyone have an idea of what that particular section is trying to
> count?  (As an aside, the numbits variable is slightly confusing because
> it seems to be a number of blocks, not bits).  I'd be happy to continue
> to poke at this, but I'm a bit stumped at the moment.

The arguments of that function are redundant and it smells like we have
numbits < numblocks * bits_per_block.  Could you print both on that fs?

FWIW, it looks like this thing actually tries to be something like

/* count zero bits in bitmap; bitmap itself is an array of host-endian 16bit */

u32 count_free(struct super_block *sb, struct buffer_head *map[], u32 bits)
{
	size_t size = sb->s_blocksize;
	u32 sum = 0;

	while (bits) {
		struct buffer_head *bh = *map++;
		__u16 *p = bh->b_data;
		if (bits >= size * 8) { /* full block */
			__u16 *end = bh->b_data + size;
			while (p < end)
				sum += hweight16(~*p++);
			bits -= size * 8;
		} else { /* bitmap takes only part of it */
			__u16 *end = p + bits / 16;
			/* full 16bit words */
			while (p < end)
				sum += hweight16(~*p++);
			bits %= 16;
			if (bits) { /* partial word, only lower bits matter */
				sum += hweight16(~*p++ & ((1 << bits) - 1));
				bits = 0;
			}
		}
	}

	return sum;
}

Note that this needs update of callers (both have the superblock ready)
*and* minix_fill_super() needs to verify that
	a) sbi->s_ninodes < sbi->s_imap_blocks * sb->s_blocksize * 8
	b) (sbi->s_nzones - sbi->s_firstdatazone + 1) <=
			 sbi->s_zmap_blocks * sb->s_blocksize * 8
and scream if it isn't.

I *think* that what's happening in your case is that we have more blocks
for block bitmap than we would need to hold all bits.  That would explode
in exactly such a way, but I'd like to see confirmation; what arguments
does your count_free() actually get?  The last two arguments, that is...

NOTE: the above is not even compile-testeed.  It also needs an update to
deal with an atrocious kludge on several architectures - minix bitmaps
are *not* always host-endian on Linux and the things get really ugly
when we go into it; see CONFIG_MINIX_FS_.*_ENDIAN for gory details.

Re: Oops in minixfs_statfs

[Bob Copeland]

On Tue, Aug 16, 2011 at 10:18 PM, Al Viro <viro@zeniv.linux.org.uk> wrote:
> I *think* that what's happening in your case is that we have more blocks
> for block bitmap than we would need to hold all bits.  That would explode
> in exactly such a way, but I'd like to see confirmation; what arguments
> does your count_free() actually get?  The last two arguments, that is...

Sounds like it, Josh posted this output before:

[  516.859103] imap_blocks 7 zmap_blocks 7 firstdatazone c11
log_zone_size 0 max_size 7fffffff magic 4d5a nzones 3001c blocksize:
1000

So there are 7 blocks in the zone bitmap but only 0x3001c - 0xc11 = 193547
zones to allocate, which would fit in 6 blocks.

-- 
Bob Copeland %% www.bobcopeland.com

Re: Oops in minixfs_statfs

[Josh Boyer]

On Wed, Aug 17, 2011 at 03:18:20AM +0100, Al Viro wrote:
> On Tue, Aug 16, 2011 at 12:48:09PM -0400, Josh Boyer wrote:
> > We've had a bug open in Fedora for a while[1] where it's fairly easy to
> > generate an oops on a MinixV3 filesystem.  I've looked at it a bit and
> > 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;
> > 
> > which causes the loop below it to access bh->b_data outside it's bounds.
> > 
> > I installed minix 3.1.8 (shoot me now) in a KVM guest today, and two out
> > of the three filesystems work fine.  / and /home are both relatively
> > small, and a df seems to return fairly accurate numbers.  However, a df
> > on /usr (which is ~768M) causes the oops.
> > 
> > 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:
> > 
> > [   49.114984] imap_blocks 2 zmap_blocks 1 firstdatazone 205
> > log_zone_size 0 max_size 7fffffff magic 4d5a nzones 4000 blocksize: 1000
> > 
> > [   66.380824] imap_blocks 2 zmap_blocks 2 firstdatazone 2a2
> > log_zone_size 0 max_size 7fffffff magic 4d5a nzones a700 blocksize: 1000
> > 
> > [  516.859103] imap_blocks 7 zmap_blocks 7 firstdatazone c11
> > log_zone_size 0 max_size 7fffffff magic 4d5a nzones 3001c blocksize:
> > 1000
> > 
> > The calculation of i on line 38 results in fffffe80 for the last
> > filesytem when minix_count_free_blocks is called for it.
> > 
> > Does anyone have an idea of what that particular section is trying to
> > count?  (As an aside, the numbits variable is slightly confusing because
> > it seems to be a number of blocks, not bits).  I'd be happy to continue
> > to poke at this, but I'm a bit stumped at the moment.
> 
> The arguments of that function are redundant and it smells like we have
> numbits < numblocks * bits_per_block.  Could you print both on that fs?

In the failing case, numblocks is 7 and numbits is 0x2f40c.  So given we
have a 4k block size, numbits is definitely smaller than numblocks *
bits_per_block.

> FWIW, it looks like this thing actually tries to be something like
> 
> /* count zero bits in bitmap; bitmap itself is an array of host-endian 16bit */
> 
> u32 count_free(struct super_block *sb, struct buffer_head *map[], u32 bits)
> {
> 	size_t size = sb->s_blocksize;
> 	u32 sum = 0;
> 
> 	while (bits) {
> 		struct buffer_head *bh = *map++;
> 		__u16 *p = bh->b_data;
> 		if (bits >= size * 8) { /* full block */
> 			__u16 *end = bh->b_data + size;
> 			while (p < end)
> 				sum += hweight16(~*p++);
> 			bits -= size * 8;
> 		} else { /* bitmap takes only part of it */
> 			__u16 *end = p + bits / 16;
> 			/* full 16bit words */
> 			while (p < end)
> 				sum += hweight16(~*p++);
> 			bits %= 16;
> 			if (bits) { /* partial word, only lower bits matter */
> 				sum += hweight16(~*p++ & ((1 << bits) - 1));
> 				bits = 0;
> 			}
> 		}
> 	}
> 
> 	return sum;
> }
> 
> Note that this needs update of callers (both have the superblock ready)
> *and* minix_fill_super() needs to verify that
> 	a) sbi->s_ninodes < sbi->s_imap_blocks * sb->s_blocksize * 8
> 	b) (sbi->s_nzones - sbi->s_firstdatazone + 1) <=
> 			 sbi->s_zmap_blocks * sb->s_blocksize * 8
> and scream if it isn't.

Making it scream is easy to do, but should it fail to mount, or fix
things up?

An alternative would be to have minix_statfs pass
minix_count_free_{inodes,blocks} the superblock, and have those two
functions calculate a and b above, respectively.  Then you could do
something like (for the free blocks case):

        struct minix_sb_info *sbi = minix_sb(sb);
        int blocks = sbi->s_zmap_blocks;
        u32 bits = sbi->s_nzones - sbi->s_firstdatazone + 1;

        /* Make sure minix didn't allocate more blocks than needed
	 * for the amount of bits
         */
        if (bits < blocks * sb->s_blocksize * 8)
                blocks--;

and pass blocks and bits to count_free.

That's untested, and it really doesn't fully check how many extra blocks
were allocated, but it illustrates the point.  The benefit is the fix
here is localized to the two functions.  Although, I have no idea why
minix would allocate an extra block so I have no idea if simply ignoring
it during the counting is a viable solution or not.

> I *think* that what's happening in your case is that we have more blocks
> for block bitmap than we would need to hold all bits.  That would explode
> in exactly such a way, but I'd like to see confirmation; what arguments
> does your count_free() actually get?  The last two arguments, that is...

Yeah, seems so.  Bob provided the math in his email.

As I said, I don't know why minix decided to allocate an extra zmap block,
but there isn't really anything we can do about that.

> NOTE: the above is not even compile-testeed.  It also needs an update to
> deal with an atrocious kludge on several architectures - minix bitmaps
> are *not* always host-endian on Linux and the things get really ugly
> when we go into it; see CONFIG_MINIX_FS_.*_ENDIAN for gory details.

Ugh.

josh

Re: Oops in minixfs_statfs

[Josh Boyer]

On Wed, Aug 17, 2011 at 01:18:29PM -0400, Josh Boyer wrote:
> On Wed, Aug 17, 2011 at 03:18:20AM +0100, Al Viro wrote:
> > On Tue, Aug 16, 2011 at 12:48:09PM -0400, Josh Boyer wrote:
> > > We've had a bug open in Fedora for a while[1] where it's fairly easy to
> > > generate an oops on a MinixV3 filesystem.  I've looked at it a bit and
> > > 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;
> > > 
> > > which causes the loop below it to access bh->b_data outside it's bounds.
> > > 
> > > I installed minix 3.1.8 (shoot me now) in a KVM guest today, and two out
> > > of the three filesystems work fine.  / and /home are both relatively
> > > small, and a df seems to return fairly accurate numbers.  However, a df
> > > on /usr (which is ~768M) causes the oops.
> > > 
> > > 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:
> > > 
> > > [   49.114984] imap_blocks 2 zmap_blocks 1 firstdatazone 205
> > > log_zone_size 0 max_size 7fffffff magic 4d5a nzones 4000 blocksize: 1000
> > > 
> > > [   66.380824] imap_blocks 2 zmap_blocks 2 firstdatazone 2a2
> > > log_zone_size 0 max_size 7fffffff magic 4d5a nzones a700 blocksize: 1000
> > > 
> > > [  516.859103] imap_blocks 7 zmap_blocks 7 firstdatazone c11
> > > log_zone_size 0 max_size 7fffffff magic 4d5a nzones 3001c blocksize:
> > > 1000
> > > 
> > > The calculation of i on line 38 results in fffffe80 for the last
> > > filesytem when minix_count_free_blocks is called for it.
> > > 
> > > Does anyone have an idea of what that particular section is trying to
> > > count?  (As an aside, the numbits variable is slightly confusing because
> > > it seems to be a number of blocks, not bits).  I'd be happy to continue
> > > to poke at this, but I'm a bit stumped at the moment.
> > 
> > The arguments of that function are redundant and it smells like we have
> > numbits < numblocks * bits_per_block.  Could you print both on that fs?
> 
> In the failing case, numblocks is 7 and numbits is 0x2f40c.  So given we
> have a 4k block size, numbits is definitely smaller than numblocks *
> bits_per_block.
> 
> > FWIW, it looks like this thing actually tries to be something like
> > 
> > /* count zero bits in bitmap; bitmap itself is an array of host-endian 16bit */
> > 
> > u32 count_free(struct super_block *sb, struct buffer_head *map[], u32 bits)
> > {
> > 	size_t size = sb->s_blocksize;
> > 	u32 sum = 0;
> > 
> > 	while (bits) {
> > 		struct buffer_head *bh = *map++;
> > 		__u16 *p = bh->b_data;
> > 		if (bits >= size * 8) { /* full block */
> > 			__u16 *end = bh->b_data + size;
> > 			while (p < end)
> > 				sum += hweight16(~*p++);
> > 			bits -= size * 8;
> > 		} else { /* bitmap takes only part of it */
> > 			__u16 *end = p + bits / 16;
> > 			/* full 16bit words */
> > 			while (p < end)
> > 				sum += hweight16(~*p++);
> > 			bits %= 16;
> > 			if (bits) { /* partial word, only lower bits matter */
> > 				sum += hweight16(~*p++ & ((1 << bits) - 1));
> > 				bits = 0;
> > 			}
> > 		}
> > 	}
> > 
> > 	return sum;
> > }
> > 
> > Note that this needs update of callers (both have the superblock ready)
> > *and* minix_fill_super() needs to verify that
> > 	a) sbi->s_ninodes < sbi->s_imap_blocks * sb->s_blocksize * 8
> > 	b) (sbi->s_nzones - sbi->s_firstdatazone + 1) <=
> > 			 sbi->s_zmap_blocks * sb->s_blocksize * 8
> > and scream if it isn't.
> 
> Making it scream is easy to do, but should it fail to mount, or fix
> things up?
> 
> An alternative would be to have minix_statfs pass
> minix_count_free_{inodes,blocks} the superblock, and have those two
> functions calculate a and b above, respectively.  Then you could do
> something like (for the free blocks case):
> 
>         struct minix_sb_info *sbi = minix_sb(sb);
>         int blocks = sbi->s_zmap_blocks;
>         u32 bits = sbi->s_nzones - sbi->s_firstdatazone + 1;
> 
>         /* Make sure minix didn't allocate more blocks than needed
> 	 * for the amount of bits
>          */
>         if (bits < blocks * sb->s_blocksize * 8)
>                 blocks--;
> 
> and pass blocks and bits to count_free.
> 
> That's untested, and it really doesn't fully check how many extra blocks
> were allocated, but it illustrates the point.  The benefit is the fix
> here is localized to the two functions.  Although, I have no idea why
> minix would allocate an extra block so I have no idea if simply ignoring
> it during the counting is a viable solution or not.

I came up with the patch below.  It avoids the oops and does a bit of
verification on mount.  I still have no idea if it's valid to ignore
that extra block, but at the moment it's the best I could come up with.

josh

---------

>From 8fc8c5c88fb7ff773299ef2bb9f0d4b83f91799d Mon Sep 17 00:00:00 2001
From: Josh Boyer <jwboyer@redhat.com>
Date: Thu, 18 Aug 2011 16:57:24 -0400
Subject: [PATCH] fs/minix: Verify bitmap block counts before mounting

Newer versions of MINIX can create filesystems that allocate an extra
bitmap block.  Mounting of this succeeds, but doing a statfs call will
result in an oops in count_free because of a negative number being used
for the bh index.

Avoid this by verifying the number of allocated blocks at mount time,
erroring out if there are not enough and make statfs ignore the extras
if there are too many.

This fixes https://bugzilla.kernel.org/show_bug.cgi?id=18792

Signed-off-by: Josh Boyer <jwboyer@redhat.com>
---
 fs/minix/bitmap.c |   25 ++++++++++++++++++++-----
 fs/minix/inode.c  |   33 +++++++++++++++++++++++++++++++--
 fs/minix/minix.h  |   13 +++++++++++--
 3 files changed, 62 insertions(+), 9 deletions(-)

diff --git a/fs/minix/bitmap.c b/fs/minix/bitmap.c
index 3f32bcb..c7bbd2a 100644
--- a/fs/minix/bitmap.c
+++ b/fs/minix/bitmap.c
@@ -105,10 +105,17 @@ int minix_new_block(struct inode * inode)
 	return 0;
 }
 
-unsigned long minix_count_free_blocks(struct minix_sb_info *sbi)
+unsigned long minix_count_free_blocks(struct super_block *sb)
 {
-	return (count_free(sbi->s_zmap, sbi->s_zmap_blocks,
-		sbi->s_nzones - sbi->s_firstdatazone + 1)
+	struct minix_sb_info *sbi = minix_sb(sb);
+	unsigned blocks = sbi->s_zmap_blocks;
+	u32 bits = sbi->s_nzones - sbi->s_firstdatazone + 1;
+	unsigned blocks_needed = minix_blocks_needed(bits, sb->s_blocksize);
+	
+	if (blocks != blocks_needed)
+		blocks = blocks_needed;
+
+	return (count_free(sbi->s_zmap, blocks, bits)
 		<< sbi->s_log_zone_size);
 }
 
@@ -273,7 +280,15 @@ struct inode *minix_new_inode(const struct inode *dir, int mode, int *error)
 	return inode;
 }
 
-unsigned long minix_count_free_inodes(struct minix_sb_info *sbi)
+unsigned long minix_count_free_inodes(struct super_block *sb)
 {
-	return count_free(sbi->s_imap, sbi->s_imap_blocks, sbi->s_ninodes + 1);
+	struct minix_sb_info *sbi = minix_sb(sb);
+	unsigned blocks = sbi->s_imap_blocks;
+	u32 bits = sbi->s_ninodes + 1;
+	unsigned blocks_needed = minix_blocks_needed(bits, sb->s_blocksize);
+
+	if (blocks != blocks_needed)
+		blocks = blocks_needed;
+
+	return count_free(sbi->s_imap, blocks, bits);
 }
diff --git a/fs/minix/inode.c b/fs/minix/inode.c
index e7d23e2..e2a3fdf 100644
--- a/fs/minix/inode.c
+++ b/fs/minix/inode.c
@@ -279,6 +279,35 @@ static int minix_fill_super(struct super_block *s, void *data, int silent)
  	else if (sbi->s_mount_state & MINIX_ERROR_FS)
 		printk("MINIX-fs: mounting file system with errors, "
 			"running fsck is recommended\n");
+
+	/* Apparently minix can create filesystems that allocate more blocks for
+	 * the bitmaps than needed.  Check for this and complain.
+	 */
+	block = minix_blocks_needed(sbi->s_ninodes, s->s_blocksize);
+	if (sbi->s_imap_blocks != block) {
+		if (sbi->s_imap_blocks > block)
+			printk("MINIX-fs: mounting file system with extra "
+					"imap blocks, ignoring.\n");
+		else {
+			printk("MINIX-fs: file system does not have enough "
+					"imap blocks allocated.\n");
+			goto out_iput;
+		}
+	}
+
+	block = minix_blocks_needed(
+			(sbi->s_nzones - sbi->s_firstdatazone + 1), s->s_blocksize);
+	if (sbi->s_imap_blocks != block) {
+		if (sbi->s_zmap_blocks > block)
+			printk("MINIX-fs: mounting file system with extra "
+					"zmap blocks, ignoring.\n");
+		else {
+			printk("MINIX-fs: file system does not have enough "
+					"zmap blocks allocated.\n");
+			goto out_iput;
+		}
+	}
+
 	return 0;
 
 out_iput:
@@ -339,10 +368,10 @@ static int minix_statfs(struct dentry *dentry, struct kstatfs *buf)
 	buf->f_type = sb->s_magic;
 	buf->f_bsize = sb->s_blocksize;
 	buf->f_blocks = (sbi->s_nzones - sbi->s_firstdatazone) << sbi->s_log_zone_size;
-	buf->f_bfree = minix_count_free_blocks(sbi);
+	buf->f_bfree = minix_count_free_blocks(sb);
 	buf->f_bavail = buf->f_bfree;
 	buf->f_files = sbi->s_ninodes;
-	buf->f_ffree = minix_count_free_inodes(sbi);
+	buf->f_ffree = minix_count_free_inodes(sb);
 	buf->f_namelen = sbi->s_namelen;
 	buf->f_fsid.val[0] = (u32)id;
 	buf->f_fsid.val[1] = (u32)(id >> 32);
diff --git a/fs/minix/minix.h b/fs/minix/minix.h
index 341e212..9850080 100644
--- a/fs/minix/minix.h
+++ b/fs/minix/minix.h
@@ -48,10 +48,10 @@ extern struct minix_inode * minix_V1_raw_inode(struct super_block *, ino_t, stru
 extern struct minix2_inode * minix_V2_raw_inode(struct super_block *, ino_t, struct buffer_head **);
 extern struct inode * minix_new_inode(const struct inode *, int, int *);
 extern void minix_free_inode(struct inode * inode);
-extern unsigned long minix_count_free_inodes(struct minix_sb_info *sbi);
+extern unsigned long minix_count_free_inodes(struct super_block *sb);
 extern int minix_new_block(struct inode * inode);
 extern void minix_free_block(struct inode *inode, unsigned long block);
-extern unsigned long minix_count_free_blocks(struct minix_sb_info *sbi);
+extern unsigned long minix_count_free_blocks(struct super_block *sb);
 extern int minix_getattr(struct vfsmount *, struct dentry *, struct kstat *);
 extern int minix_prepare_chunk(struct page *page, loff_t pos, unsigned len);
 
@@ -88,6 +88,15 @@ static inline struct minix_inode_info *minix_i(struct inode *inode)
 	return list_entry(inode, struct minix_inode_info, vfs_inode);
 }
 
+static inline unsigned minix_blocks_needed(unsigned bits, unsigned blocksize)
+{
+	unsigned blocks = bits / (blocksize * 8);
+
+	if (bits % (blocksize * 8))
+		blocks++;
+	return blocks;
+}
+
 #if defined(CONFIG_MINIX_FS_NATIVE_ENDIAN) && \
 	defined(CONFIG_MINIX_FS_BIG_ENDIAN_16BIT_INDEXED)
 
-- 
1.7.6

Re: Oops in minixfs_statfs

[Al Viro]

On Thu, Aug 18, 2011 at 05:13:21PM -0400, Josh Boyer wrote:

> +	if (blocks != blocks_needed)
> +		blocks = blocks_needed;

????

Re: Oops in minixfs_statfs

[Josh Boyer]

On Thu, Aug 18, 2011 at 10:16:20PM +0100, Al Viro wrote:
> On Thu, Aug 18, 2011 at 05:13:21PM -0400, Josh Boyer wrote:
> 
> > +	if (blocks != blocks_needed)
> > +		blocks = blocks_needed;
> 
> ????

Er.. yeah.  That's a left over from before I moved some verification
into fill_super, and then it got simplified to the point of being
utterly stupid.  It's been a long day.

I guess I could either just reassign sbi->s_[iz]map_blocks right then
and truly ignore the extra block, or just always pass the calculated
blocks_needed to count_free.  Which would you prefer?

josh