[PATCH] invalidate buffers on blkdev_put

[PATCH] invalidate buffers on blkdev_put

[Chris Mason]

Hi guys,

I had sent this to Al, but couldn't tell if he hated it, thought it was
broken, or just didn't think it was required.  So, I opted for wider
testing.  This only affects 2.4.10pre15+, as it was caused by the blkdev
changes there.

Anyway, the bug looks like this:

dd if=ext2-image-1 of=/dev/ram0
mount /dev/ram0 /mnt
umount /mnt

dd if=ext2-image-2 of=/dev/ram0
mount /dev/ram0 /mnt
ls -la /mnt (FS looks corrupted and wrong).

The problem is that on unmount, the ramdisk's buffer cache isn't cleared
because bd_openers is still one.  So, even if a new image is copied in, you
still see the old image's superblock/inodes etc on mount.

In this case, we want to leave the dirty pages in the page cache, but get
rid of the buffer cache copies.

This should not drop any updated data in the ramdisk because
rd_blkdev_pagecache_IO dirties pages as the higher layers send down
modified buffer heads (and other rd.c funcs do the same).  Patch is below.
Linus, please consider (pending lack of nays from Al).

An additional patch is probably to remove the second invalidate_buffers
call, since only the filesystems should have buffer cache entries.  

-chris

--- 3.1/fs/block_dev.c Sun, 23 Sep 2001 20:11:16 -0400 
+++ 3.1(w)/fs/block_dev.c Mon, 24 Sep 2001 15:11:49 -0400 
@@ -802,8 +802,10 @@
 			unlock_super(sb);
 			drop_super(sb);
 		}
-	} else if (kind == BDEV_FS)
+	} else if (kind == BDEV_FS) {
 		fsync_no_super(rdev);
+		invalidate_buffers(rdev);
+	}
 	if (!--bdev->bd_openers) {
 		truncate_inode_pages(bd_inode->i_mapping, 0);
 		invalidate_buffers(rdev);

Re: [PATCH] invalidate buffers on blkdev_put

[Alexander Viro]

On Mon, 24 Sep 2001, Chris Mason wrote:

> 
> Hi guys,
> 
> I had sent this to Al, but couldn't tell if he hated it, thought it was
> broken, or just didn't think it was required.  So, I opted for wider
> testing.  This only affects 2.4.10pre15+, as it was caused by the blkdev
> changes there.
> 
> Anyway, the bug looks like this:
> 
> dd if=ext2-image-1 of=/dev/ram0
> mount /dev/ram0 /mnt
> umount /mnt
> 
> dd if=ext2-image-2 of=/dev/ram0
> mount /dev/ram0 /mnt
> ls -la /mnt (FS looks corrupted and wrong).
> 
> The problem is that on unmount, the ramdisk's buffer cache isn't cleared
> because bd_openers is still one.  So, even if a new image is copied in, you
> still see the old image's superblock/inodes etc on mount.
> 
> In this case, we want to leave the dirty pages in the page cache, but get
> rid of the buffer cache copies.
> 
> This should not drop any updated data in the ramdisk because
> rd_blkdev_pagecache_IO dirties pages as the higher layers send down
> modified buffer heads (and other rd.c funcs do the same).  Patch is below.
> Linus, please consider (pending lack of nays from Al).

OK, not exactly nay, but...  What you are trying to do is a workaround
for problem that can be solved in somewhat saner way.  Namely, we can
make getblk() return buffres backed by pages from device page cache.

It's _not_ an obvious step.  The most sensitive parts are
	* need to allocate all bdev pages with GFP_BUFFER.  Otherwise
we'll eat flaming death on VM deadlocks.  Doable (we can set ->i_data.gfp_mask)
but may lead to interesting effects wrt VM balancing.
	* implementation of bforget()
	* we'll need to kill buffer hash or deal with the new access path
to page-private buffer_heads.

It's solvable, but not obvious.  It _does_ solve coherency problems between
device page cache and buffer cache (thus killing update_buffers() and its
ilk), but the last issue (new access path to page-private buffer_heads)
may be rather nasty.

Re: [PATCH] invalidate buffers on blkdev_put

[Linus Torvalds]

On Mon, 24 Sep 2001, Alexander Viro wrote:
>
> OK, not exactly nay, but...  What you are trying to do is a workaround
> for problem that can be solved in somewhat saner way.  Namely, we can
> make getblk() return buffres backed by pages from device page cache.

I now have the patches for this, but I have to fix up fs/block_dev.c to
also honour the block size thing because otherwise the two are still not
in sync.

I'll send out a test-patch later this evening, I hope.

> It's solvable, but not obvious.  It _does_ solve coherency problems between
> device page cache and buffer cache (thus killing update_buffers() and its
> ilk), but the last issue (new access path to page-private buffer_heads)
> may be rather nasty.

It's certainly solvable, but it is also certainly very fraught with tons
of small details. I'll be very happy if people end up looking through the
patches _very_ critically (and don't even bother testing them if you don't
have a machine where you can lose a filesystem or two).

Hopefully in another hour or two (but the first version is going to have
some ugly stuff in it still).

		Linus

Re: [PATCH] invalidate buffers on blkdev_put

[Anton Altaparmakov]

At 05:21 25/09/01, Linus Torvalds wrote:
>On Mon, 24 Sep 2001, Alexander Viro wrote:
> > OK, not exactly nay, but...  What you are trying to do is a workaround
> > for problem that can be solved in somewhat saner way.  Namely, we can
> > make getblk() return buffres backed by pages from device page cache.
>
>I now have the patches for this, but I have to fix up fs/block_dev.c to
>also honour the block size thing because otherwise the two are still not
>in sync.
>
>I'll send out a test-patch later this evening, I hope.
>
> > It's solvable, but not obvious.  It _does_ solve coherency problems between
> > device page cache and buffer cache (thus killing update_buffers() and its
> > ilk), but the last issue (new access path to page-private buffer_heads)
> > may be rather nasty.
>
>It's certainly solvable, but it is also certainly very fraught with tons
>of small details. I'll be very happy if people end up looking through the
>patches _very_ critically (and don't even bother testing them if you don't
>have a machine where you can lose a filesystem or two).
>
>Hopefully in another hour or two (but the first version is going to have
>some ugly stuff in it still).

Looking at the patch, you introduce a static inline blksize_bits. Wouldn't 
it be a lot more efficient to change the function to say:

static inline unsigned int blksize_bits(unsigned int size)
{
         return ffs(size) - 1;
}

and optionally, throw in a power of two assertion a-la:

static inline unsigned int blksize_bits(unsigned int size)
{
         if (!(size & size - 1))
                 return ffs(size) - 1;
         BUG();
}

Or am I barking mad and block sizes which are not a power of two are valid? (-;

Your version is not too happy with such beasts either but it does round 
down rather than do god knows what in arch specific ffs() implementation... 
Haven't looked at non-ia32 code but at least ia32's implementation fails 
miserably for non-powers of two by it's design. But it should be a lot 
faster than doing the while loop considering ffs() just uses a single CPU 
instruction instead of the loop (on ia32 anyway).

Best regards,

         Anton


-- 
   "Nothing succeeds like success." - Alexandre Dumas
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Linux NTFS Maintainer / WWW: http://linux-ntfs.sf.net/
ICQ: 8561279 / WWW: http://www-stu.christs.cam.ac.uk/~aia21/

Re: [PATCH] invalidate buffers on blkdev_put

[Linus Torvalds]

On Tue, 25 Sep 2001, Anton Altaparmakov wrote:
>
> Looking at the patch, you introduce a static inline blksize_bits. Wouldn't
> it be a lot more efficient to change the function to say:

More efficient? Probably not. We know that the result of blksize_bits is
in the range of 9-12 on x86, and if you look at the thing it uses that
knowledge.

More importantly, I think the whole code will go away, because the bits
(and the size) should be in the bdev structure in the first place (or,
even better, the inode, at which point all the special-case functions go
away and just become calls to the generic ones)

		Linus

Re: [PATCH] invalidate buffers on blkdev_put

[Anton Altaparmakov]

At 04:39 26/09/01, Linus Torvalds wrote:
>On Tue, 25 Sep 2001, Anton Altaparmakov wrote:
> > Looking at the patch, you introduce a static inline blksize_bits. Wouldn't
> > it be a lot more efficient to change the function to say:
>
>More efficient? Probably not. We know that the result of blksize_bits is
>in the range of 9-12 on x86, and if you look at the thing it uses that
>knowledge.

Of course. I saw that. However the do/while approach is a O(N) algorithm 
while the ffs() using algorithm can be O(1) if the CPU allows it.

I wrote a quick benchmark program + script (appended at bottom of this 
mail) and did 50 million iterations of either the do/while function or the 
ffs() equivalent (including the BUG() check for power of 2) and it turns 
out that on all CPUs tested (Pentium 133S, Pentium III 800, Alpha EV56 
533(or so), Athlon 1.33GHz 266FSB) the do/while loop is marginally faster 
for sizes of 256 and 512 (except P3/800 where the ffs is faster even for 
these smaller sizes) but is increasingly slower for increasing sizes. For 
large sizes the do/while loop becomes significantly slower than the ffs() 
approach, which of course is irrelevant at the moment with the block size 
limitation...

The values in below tables are in seconds (user field from time output) 
needed to complete 50 million cycles.

For those who prefer graphs rather than tables, I have created line charts 
comparing the two methods for each CPU which you can view at URL (note the 
charts contain data points for higher sizes, too, not shown in below tables 
and also note that each point shown is from a single benchmark run simply 
because I couldn't be bothered to do the stats on more than one go, but the 
values shown are representative of several runs, if you don't believe me, 
the program and script are at the bottom of this mail...):
         http://www-stu.christs.cam.ac.uk/~aia21/ffs_test.gif

do/while based function
=======================

                 | Size
CPU             | 256   512     1024    2048    4096    8192    16384
---------------+----------------------------------------------------
P1/133          | 2.26  2.38    4.62    5.29    6.04    6.78    7.56
P3/800          | 0.30  0.30    0.42    0.56    0.70    1.40    1.65
Alpha/533       | 0.48  0.48    1.93    2.22    2.52    2.31    2.61
Athlon/1333     | 0.13  0.14    0.27    0.34    0.41    0.49    0.57


ffs based function
==================

                 | Size
CPU             | 256   512     1024    2048    4096    8192    16384
---------------+----------------------------------------------------
P1/133          | 3.73  3.73    3.78    3.77    3.77    3.78    3.84
P3/800          | 0.27  0.26    0.25    0.26    0.26    0.25    0.27
Alpha/533       | 0.58  0.58    0.58    0.58    0.58    0.58    0.58
Athlon/1333     | 0.15  0.15    0.15    0.15    0.15    0.15    0.15

And just for fun the comparison for the completely irrelevant and insane 
size of 2^30 (1073741824), again 50 million iterations:

CPU             | do/while | ffs
---------------+----------+--------
P1/133          | 19.62    | 3.76
P3/800          |  3.70    | 0.25
Alpha/533       |  7.25    | 0.58
Athlon/1333     |  2.18    | 0.15

Yeah, I know, benchmarks are to be taken with a pinch of salt, are 
meaningless most of the time, etc, but it was fun doing this just to see 
how different CPUs perform (on this specific piece of code). And it was a 
good way to relax my brain after 11 hours of work at the lab today... (-:

>More importantly, I think the whole code will go away, because the bits
>(and the size) should be in the bdev structure in the first place (or,
>even better, the inode, at which point all the special-case functions go
>away and just become calls to the generic ones)

Yes, that would be a very good thing indeed and yes it renders the 
discussion pointless. But a lot of code in the kernel does the same 
calculation all the time, in particular in file systems and block devices 
(which will probably go away once we have the value in the inode) and 
almost none I have seen use ffs() but use variations of unoptimized 
for/while/do loops and I think the above benchmark results show that using 
ffs() would benefit all those cases unless they expect the normal case to 
be a size of less or equal 512.

Best regards,

         Anton

--- test_ffs.sh ---
#!/bin/bash
iters=50000000
if [ ! -f ./test_ffs ]; then
         gcc -O2 -m486 -o test_ffs test_ffs.c
fi
echo
echo Performing $iters iterations with each blocksize.
for l in 256 512 1024 2048 4096 8192 16384 32768 65536 131072 1073741824; do
         time ./test_ffs 1 $iters $l
         time ./test_ffs 2 $iters $l
done
exit 0
--- test_ffs.c ---
static inline unsigned int blksize_bits(unsigned int size)
{
         unsigned int bits = 8;
         do {
                 bits++;
                 size >>= 1;
         } while (size > 256);
         return bits;
}

/*
  * Replace this with ffs() from linux/include/asm/bitops.h
  * for your arch on non ia32.
  */
static __inline__ int kernel_ia32_ffs(int x)
{
         int r;
         __asm__("bsfl %1,%0\n\t"
                 "jnz 1f\n\t"
                 "movl $-1,%0\n"
                 "1:" : "=r" (r) : "g" (x));
         return r+1;
}

static inline unsigned int blksize_bits_ffs(unsigned int size)
{
         if (!(size & size - 1))
                 return kernel_ia32_ffs(size) - 1;
         puts("size not power of 2!");
         exit(1);
}

int main(int argc, char *argv[])
{
         long i, j, iters, testval;
         char test;
         if (argc != 4) {
parm_err:
                 printf("Syntax: test_ffs test iterations testvalue\n"
                                 "test = 1 -> use do/while blksize_bits\n"
                                 "test = 2 -> use ffs blksize_bits\n"
                                 "iterations = number of iterations of "
                                 "blksize_bits call\n"
                                 "testvalue = value to pass to 
blksize_bits\n");
                 exit(1);
         }
         test = *argv[1];
         if (test != '1' && test != '2')
                 goto parm_err;
         iters = atol(argv[2]);
         testval = atol(argv[3]);
         if (iters <= 0 || testval <= 0)
                 goto parm_err;
         printf("\n\nPerforming %li million iterations of %s test with test "
                         "value %li.\n", iters/1000000, test == '1' ?
                         "do/while" : "ffs", testval);
         switch (test) {
         case '1':
                 for (i = 0; i < iters; i++)
                         j = blksize_bits(testval);
                 break;
         case '2':
                 for (i = 0; i < iters; i++)
                         j = blksize_bits_ffs(testval);
                 break;
         }
         return 0;
}



-- 
   "Nothing succeeds like success." - Alexandre Dumas
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Linux NTFS Maintainer / WWW: http://linux-ntfs.sf.net/
ICQ: 8561279 / WWW: http://www-stu.christs.cam.ac.uk/~aia21/

Re: [PATCH] invalidate buffers on blkdev_put

[Andreas Dilger]

On Sep 26, 2001  23:42 +0100, Anton Altaparmakov wrote:
> I wrote a quick benchmark program + script (appended at bottom of this 
> mail) and did 50 million iterations of either the do/while function or the 
> ffs() equivalent (including the BUG() check for power of 2) and it turns 
> out that on all CPUs tested (Pentium 133S, Pentium III 800, Alpha EV56 
> 533(or so), Athlon 1.33GHz 266FSB) the do/while loop is marginally faster 
> for sizes of 256 and 512 (except P3/800 where the ffs is faster even for 
> these smaller sizes) but is increasingly slower for increasing sizes. For 
> large sizes the do/while loop becomes significantly slower than the ffs() 
> approach, which of course is irrelevant at the moment with the block size 
> limitation...

How does this comapre with:

switch(blocksize) {
case  512: bits =  9; break;
case 1024: bits = 10; break;
case 2048: bits = 11; break;
case 4096: bits = 12; break;
case 8192: bits = 13; break;
default: BUG();
}

Cheers, Andreas
--
Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert

Re: [PATCH] invalidate buffers on blkdev_put

[Pavel Machek]

Hi!

> > OK, not exactly nay, but...  What you are trying to do is a workaround
> > for problem that can be solved in somewhat saner way.  Namely, we can
> > make getblk() return buffres backed by pages from device page cache.
> 
> I now have the patches for this, but I have to fix up fs/block_dev.c to
> also honour the block size thing because otherwise the two are still not
> in sync.
> 
> I'll send out a test-patch later this evening, I hope.
> 
> > It's solvable, but not obvious.  It _does_ solve coherency problems between
> > device page cache and buffer cache (thus killing update_buffers() and its
> > ilk), but the last issue (new access path to page-private buffer_heads)
> > may be rather nasty.
> 
> It's certainly solvable, but it is also certainly very fraught with tons
> of small details. I'll be very happy if people end up looking through the
> patches _very_ critically (and don't even bother testing them if you don't
> have a machine where you can lose a filesystem or two).

Time to rename 2.4.10 to 2.5.0? ;-)
								Pavel

-- 
Philips Velo 1: 1"x4"x8", 300gram, 60, 12MB, 40bogomips, linux, mutt,
details at http://atrey.karlin.mff.cuni.cz/~pavel/velo/index.html.

Re: [PATCH] invalidate buffers on blkdev_put

[Dave Cinege]

On Thursday 27 September 2001 10:03, Pavel Machek wrote:
> Hi!
>
> > > It's solvable, but not obvious.  It _does_ solve coherency problems
> > > between device page cache and buffer cache (thus killing
> > > update_buffers() and its ilk), but the last issue (new access path to
> > > page-private buffer_heads) may be rather nasty.
> >
> > It's certainly solvable, but it is also certainly very fraught with tons
> > of small details. I'll be very happy if people end up looking through the
> > patches _very_ critically (and don't even bother testing them if you
> > don't have a machine where you can lose a filesystem or two).
>
> Time to rename 2.4.10 to 2.5.0? ;-)

<Waving hand> It broke my feature patch. Good enough for me.  ; >

-- 
The time is now 22:19 (Totalitarian)  -  http://www.ccops.org/clock.html