Reiserfs/kill-bkl tree v2
Hi everyone,
I'm pleased to announce the v2 of the reiserfs/kill-bkl tree. (Has there been a v1 actually...I'm not sure).
This work was first borned and hosted in the tip:kill-the-bkl tree and has then been detached as a seperate branch.
This patchset consists in dropping the bkl locking scheme from reiserfs 3 and replacing it with a per superblock mutex.
I) Deal with the BKL scheme
The first obstacle was to deal with the bkl based locking scheme in which the whole reiserfs code is based on:
Bkl behaviour:
- disables preemption
- is relaxed while scheduling
- can be acquired recursively by a task
The resulting reiserfs code:
- some callsites acquire the lock, sometimes recursively. In the latter case, it's often hard to fix
- after every calls to functions that might sleep, reiserfs performs checks to ensure the tree hasn't changed and compute fixups in the latter case.
These properties have resulted in the creation of an ad-hoc locking primitive based on a mutex but that can be acquired recursively. Also most might-sleep-callsites have been explicitly surrounded with a relax of the lock.
II) Deal with performance regressions
The bkl is based on a spinlock whereas the new lock is based on a mutex. We couldn't safely make it a spinlock because the code locked by the bkl can sleep, and such conversion would have needed a lot of rewrites.
There are a lot of reasons that can make a spinlock more efficient than a mutex.
But still we have now two nice properties:
- the mutexes have the spin on owner features, making them closer to a spinlock behaviour.
- the bkl is *forced* to be relaxed on schedule(). And sometimes this is a weakness. After a simple kmalloc, we have to check the filesystem hasn't changed behind us and to fixup in that case. That can be very costly. Sometimes this is something we want, sometimes not. At least with a mutex, we can choose.
III) Benchmarks
Comparisons have been made using dbench between vanilla throughput (bkl based) and the head of the reiserfs/kill-bkl tree (mutex based). Both kernel had the same config (CONFIG_PREEMPT=n, CONFIG_SMP=y)
- Dbench with 1 thread during 600 seconds (better with the mutex):
Lock Throughput in the end
Bkl 232.54 MB/sec
Mutex 237.71 MB/sec
Complete trace:
Bkl: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/bkl-600-1.log
Mutex: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/mut-600-1.log
Graphical comparison:
http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/dbench-1.pdf
- Dbench with 30 threads during 600 seconds (better with the bkl):
Lock Throughput in the end
Bkl 92.41 MB/sec
Mutex 82.25 MB/sec
Complete trace:
Bkl: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/bkl-600-30.log
Mutex: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/mut-600-30.log
Graphical comparison:
http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/dbench-30.pdf
- Dbench with 100 threads during 600 seconds (better with the mutex):
Lock Throughput in the end
Bkl 37.89 MB/sec
Mutex 40.58 MB/sec
Complete trace:
Bkl: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/bkl-600-100.log
Mutex: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/mut-600-100.log
Graphical comparison:
http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/dbench-100.pdf
- Dbench with two threads, writing on a seperate partition simultaneoulsy, during 600 seconds (better with the mutex):
Lock Thread #1 Thread #2
Bkl 199.95 MB/sec 186.16 MB/sec
Mutex 213.91 MB/sec 203.84 MB/sec
Complete trace:
Bkl, thread #1: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/dual-bkl-600-1.log
Bkl, thread #2: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/dual2-bkl-600-1.log
Mutex, thread #1: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/dual-mut-600-1.log
Mutex, thread #2: http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/dual2-mut-600-1.log
Graphical comparison:
http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/dbench-dual.pdf
IV) Testing and review
You can fetch the git tree, this one will keep being the most up to date:
git://git.kernel.org/pub/scm/linux/kernel/git/frederic/random-tracing.git reiserfs/kill-bkl
Or you can either apply the raw diff:
http://www.kernel.org/pub/linux/kernel/people/frederic/bench-3107/reis_full.diff
Tests/reviews/any kind of contributions are very welcome!
Thanks,
Frederic.
Quoted 1 line · Frederic Weisbecker
IV) Testing and review
You seem to have done a lot of benchmarks, but did you also do stress testing?
While a performance issue wouldn't be good, corrupting someone's file system would be really bad.
e.g. running all the file system stress tests from LTP would be a good idea, ideally multiple at a time on a multi processor system on a ram disk or perhaps AIM9.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only.
Quoted 7 lines · Andi Kleen
Quoted 1 line · Frederic Weisbecker
IV) Testing and review
You seem to have done a lot of benchmarks, but did you also do stress testing?
While a performance issue wouldn't be good, corrupting someone's file system would be really bad.
Heh, your are fairly right.
I've been focusing so much on performances regressions, that I forgot this step.
Well, actually no I haven't forgot about it, but...
The problem is that the only SMP box I have is my personal laptop. It has been sufficient to perform the dbench tests I've posted, but I could do more (and more finegrained) tests with a separate box.
Then, indeed I could launch some stress tests in my laptop, but stress tests should be run in another way than throughput tests, ideally stress tests should run this tree for long hours (no, ideally: all the time), whereas throughput tests can make it with punctual tests (though still, it would be nicer to do more and more finegrained).
I have UP test boxes however, I will do long hours stress tests on it next week but I fear that UP, even with CONFIG_PREEMPT can't open enough racy windows to unearth the real wicked bugs that are waiting.
That said, and as you can guess while reading between the aboves lines, one of my secret hopes while posting this announce was to get people to test it, why not with stress tests, using better hardware ressources than I have :-)
Quoted 3 lines
e.g. running all the file system stress tests from LTP would be a good idea, ideally multiple at a time on a multi processor system on a ram disk or perhaps AIM9.
Yeah good idea. But again, I fear my laptop hasn't enough memory to support big enough ramdisks mount points to host selftests.
Anyway, I'll launch stress tests on one of my UP boxes next week, and also some in my laptop.
Thanks!
Quoted 6 lines · Frederic Weisbecker
Quoted 3 lines
e.g. running all the file system stress tests from LTP would be a good idea, ideally multiple at a time on a multi processor system on a ram disk or perhaps AIM9.
Yeah good idea. But again, I fear my laptop hasn't enough memory to support big enough ramdisks mount points to host selftests.
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
Patch submitters cannot possibly test every crazy possibility that is out there - nor should they: it just doesnt scale. What we expect people to do is to write clean patches, to test the bits on their own boxes and submit them to lkml and address specific review feedback.
Ingo
Quoted 15 lines · Ingo Molnar
Quoted 6 lines · Frederic Weisbecker
Quoted 3 lines
e.g. running all the file system stress tests from LTP would be a good idea, ideally multiple at a time on a multi processor system on a ram disk or perhaps AIM9.
Yeah good idea. But again, I fear my laptop hasn't enough memory to support big enough ramdisks mount points to host selftests.
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
Quoted 5 lines
Patch submitters cannot possibly test every crazy possibility that is out there - nor should they: it just doesnt scale. What we expect people to do is to write clean patches, to test the bits on their own boxes and submit them to lkml and address specific review feedback.
Is this the case for patches against drivers which the submitter doesn't have or can't get a hold of?
Daniel
Quoted 8 lines · Ingo Molnar
Quoted 2 lines
Yeah good idea. But again, I fear my laptop hasn't enough memory to support big enough ramdisks mount points to host selftests.
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
What guideline can you offer as to what is "due diligence" level of stress testing, as compared to delegating this task to eyeballed reviews + incidental use on the integration trees?
- FChE
Quoted 12 lines · Frank Ch. Eigler
Quoted 9 lines · Ingo Molnar
Quoted 3 lines
Yeah good idea. But again, I fear my laptop hasn't enough memory to support big enough ramdisks mount points to host selftests.
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
Quoted 3 lines
What guideline can you offer as to what is "due diligence" level of stress testing, as compared to delegating this task to eyeballed reviews + incidental use on the integration trees?
The kind of testing the VFS tree itself gets is a good starting point i suspect - and it is a far more critical tree as it can affects all filesystems. AFAICS the VFS tree relies on linux-next and -mm for testing mostly and that's a good model IMO.
Ingo
Quoted 15 lines · Ingo Molnar
Quoted 12 lines · Frank Ch. Eigler
Quoted 9 lines · Ingo Molnar
Quoted 3 lines
Yeah good idea. But again, I fear my laptop hasn't enough memory to support big enough ramdisks mount points to host selftests.
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
Quoted 9 lines
Quoted 3 lines
What guideline can you offer as to what is "due diligence" level of stress testing, as compared to delegating this task to eyeballed reviews + incidental use on the integration trees?
The kind of testing the VFS tree itself gets is a good starting point i suspect - and it is a far more critical tree as it can affects all filesystems. AFAICS the VFS tree relies on linux-next and -mm for testing mostly and that's a good model IMO.
I've asked Al Viro to integrate this branch in the VFS tree. He wasn't opposed to that. Then I sent him the individual patches for integration in VFS but hadn't any answer since then.
I've kept him cc'ed for any further patches too.
If Al still agrees about this integration, I would be pleased.
Frederic.
Quoted 7 lines
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
Quoted 5 lines
Patch submitters cannot possibly test every crazy possibility that is out there - nor should they: it just doesnt scale. What we expect people to do is to write clean patches, to test the bits on their own boxes and submit them to lkml and address specific review feedback.
I respectfully disagree in this case. For patches that touch, say, something hardware dependent where the patch submitter doesn't have all the variations on the hardware, yes, I agree, scale the testing by running the code on many machines. But for the code in question, where some very fundamental and complex changes are being made to filesystem locking, I don't think that testing really scales -- after all, if there is some race then it's quite likely that testers will just see some rare filesystem corruption, which could easily waste weeks of debugging before the BKL/reiserfs patches were even implicated.
- R.
Quoted 13 lines · Roland Dreier
Quoted 7 lines
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
Quoted 5 lines
Patch submitters cannot possibly test every crazy possibility that is out there - nor should they: it just doesnt scale. What we expect people to do is to write clean patches, to test the bits on their own boxes and submit them to lkml and address specific review feedback.
Quoted 9 lines
I respectfully disagree in this case. For patches that touch, say, something hardware dependent where the patch submitter doesn't have all the variations on the hardware, yes, I agree, scale the testing by running the code on many machines. But for the code in question, where some very fundamental and complex changes are being made to filesystem locking, I don't think that testing really scales -- after all, if there is some race then it's quite likely that testers will just see some rare filesystem corruption, which could easily waste weeks of debugging before the BKL/reiserfs patches were even implicated.
Definitely, the cost of the rare bug is much higher. The good news is that reiserfs tends to pile its races into a few spots. Most of them can be found with a 12 hour run of the namesys stress.sh program and a lot of memory pressure. I'd compile with preemption on and you'll have a good test on any SMP machine.
http://oss.oracle.com/~mason/stress.sh
stress.sh just copies a source directory into the test filesystem, then reads it back and deletes it in a loop. I'd run with 50 procs and enough memory pressure for the box to lightly swap (booting w/mem= is a fine way to make memory pressure). This way you make sure to hammer on the metadata writeback paths, which is where all of the difficult races come in.
Testing with an fsx-linux process running at the same time will make sure all of the mmap/truncate paths are working correctly as well.
-chris
Quoted 15 lines · Chris Mason
Definitely, the cost of the rare bug is much higher. The good news is that reiserfs tends to pile its races into a few spots. Most of them can be found with a 12 hour run of the namesys
stress.shprogram and a lot of memory pressure. I'd compile with preemption on and you'll have a good test on any SMP machine.http://oss.oracle.com/~mason/stress.sh
stress.shjust copies a source directory into the test filesystem, then reads it back and deletes it in a loop. I'd run with 50 procs and enough memory pressure for the box to lightly swap (booting w/mem= is a fine way to make memory pressure). This way you make sure to hammer on the metadata writeback paths, which is where all of the difficult races come in.
Quoted 3 lines
Testing with an fsx-linux process running at the same time will make sure all of the mmap/truncate paths are working correctly as well.
Ok, that definitely looks like something feasible to run for Frederic too, thanks for the detailed suggestion!
Ingo
Quoted 39 lines · Chris Mason
Quoted 13 lines · Roland Dreier
Quoted 7 lines
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
Quoted 5 lines
Patch submitters cannot possibly test every crazy possibility that is out there - nor should they: it just doesnt scale. What we expect people to do is to write clean patches, to test the bits on their own boxes and submit them to lkml and address specific review feedback.
Quoted 9 lines
I respectfully disagree in this case. For patches that touch, say, something hardware dependent where the patch submitter doesn't have all the variations on the hardware, yes, I agree, scale the testing by running the code on many machines. But for the code in question, where some very fundamental and complex changes are being made to filesystem locking, I don't think that testing really scales -- after all, if there is some race then it's quite likely that testers will just see some rare filesystem corruption, which could easily waste weeks of debugging before the BKL/reiserfs patches were even implicated.
Definitely, the cost of the rare bug is much higher. The good news is that reiserfs tends to pile its races into a few spots. Most of them can be found with a 12 hour run of the namesys
stress.shprogram and a lot of memory pressure. I'd compile with preemption on and you'll have a good test on any SMP machine.http://oss.oracle.com/~mason/stress.sh
stress.shjust copies a source directory into the test filesystem, then reads it back and deletes it in a loop. I'd run with 50 procs and enough memory pressure for the box to lightly swap (booting w/mem= is a fine way to make memory pressure). This way you make sure to hammer on the metadata writeback paths, which is where all of the difficult races come in.
Quoted 4 lines
Testing with an fsx-linux process running at the same time will make sure all of the mmap/truncate paths are working correctly as well.
-chris
Thanks a lot for this script Chris, I'm going to test with that.
PATCH 1/1 kill-the-bkl/reiserfs: fix early readdir offset increment
In reply to Chris MasonQuoted 15 lines · Chris Mason
Definitely, the cost of the rare bug is much higher. The good news is that reiserfs tends to pile its races into a few spots. Most of them can be found with a 12 hour run of the namesys
stress.shprogram and a lot of memory pressure. I'd compile with preemption on and you'll have a good test on any SMP machine.http://oss.oracle.com/~mason/stress.sh
stress.shjust copies a source directory into the test filesystem, then reads it back and deletes it in a loop. I'd run with 50 procs and enough memory pressure for the box to lightly swap (booting w/mem= is a fine way to make memory pressure). This way you make sure to hammer on the metadata writeback paths, which is where all of the difficult races come in.
Quoted 5 lines
Testing with an fsx-linux process running at the same time will make sure all of the mmap/truncate paths are working correctly as well.
-chris
Running this script has unearthed a bug introduced in my last commit. This is fixed in the patch below.
Thanks for this script, I'm now running it very often, only on PREEMPT UP for now.
---
From a22c48509ca7b54206c0616141278e5561f119ef Mon Sep 17 00:00:00 2001
From: Frederic Weisbecker <[email protected]>
Date: Mon, 10 Aug 2009 00:53:45 +0200
Subject: [PATCH] kill-the-bkl/reiserfs: fix early readdir offset increment
The previous commit:
"kill-the-bkl/reiserfs: release the lock only for first entry in readdir" brought a bug which increments the readdir offset even if we failed to copy a directory entry through filldir.
Then if we are in the end of the user buffer, there are chances that getdents() will be subsequently called with a new buffer to continue fetching the directory. At this time the directory entry offset will be wrong because it has omitted the previous entry that failed to copy.
We need to increment the directory offset after fetching an entry, not before.
This fixes weird bugs in which a directory seems not empty whereas it is.
--- fs/reiserfs/dir.c | 21 +++++++++++---------- 1 files changed, 11 insertions(+), 10 deletions(-)
fs/reiserfs/dir.c +11 -10
@@ -195,12 +195,6 @@ int reiserfs_readdir_dentry(struct dentry *dentry, void *dirent, *pos = d_off; d_ino =deh_objectid (deh); -/* -* next entry should be looked for with such -* offset -*/ - next_pos =deh_offset (deh) +1 ; -if (first_entry) {int fillret;
@@ -221,11 +215,18 @@ int reiserfs_readdir_dentry(struct dentry *dentry, void *dirent,if (item_moved (&tmp_ih, &path_to_entry)) goto research; -continue ; - } -if (filldir (dirent, d_name, d_reclen, d_off, - d_ino,DT_UNKNOWN ) <0 ) + }else { +if (filldir (dirent, d_name, d_reclen, + d_off, d_ino,DT_UNKNOWN ) <0 ) goto end; + } + +/* +* next entry should be looked for with such +* offset +*/ + next_pos =deh_offset (deh) +1 ; + }/* for */ }
Signature · 10 lines
1.6.2.3 You can find this patch and the other in this series in the following git tree: git://git.kernel.org/pub/scm/linux/kernel/git/frederic/random-tracing.git reiserfs/kill-bkl Thanks.
Quoted 16 lines · Ingo Molnar
Quoted 6 lines · Frederic Weisbecker
Quoted 3 lines
e.g. running all the file system stress tests from LTP would be a good idea, ideally multiple at a time on a multi processor system on a ram disk or perhaps AIM9.
Yeah good idea. But again, I fear my laptop hasn't enough memory to support big enough ramdisks mount points to host selftests.
Well, dont waste too much time on it (beyond the due diligence level) - Andi forgot that the right way to stress-test patches is to get through the review process and then through the integration trees which have far more test exposure than any single contributor can test.
Quoted 7 lines
Patch submitters cannot possibly test every crazy possibility that is out there - nor should they: it just doesnt scale. What we expect people to do is to write clean patches, to test the bits on their own boxes and submit them to lkml and address specific review feedback.
Ingo
Yeah, I know that doesn't scale. But I really would like to test it, at least with the minimum scope I have.
Such fundamental change in a filesystem is scary :)