BLASTing Linux Code

Jan Tobias Mühlberg and Gerald Lüttgen
Department of Computer Science, University of York, York YO10 5DD, U.K.


main page | next example


Commit Overview | Files | Comments

Checking Locking Properties: Example 8


Commit Overview

Commit Key fa0726854c4f03f9d2d1e00bb3b67a49ce490c32
Subject [PATCH] ext3: fix race between ext3 make block reservation and reservation window ...
Description This patch fixed a race between ext3_discard_reservation() and
ext3_try_to_allocate_with_rsv().

There is a window where ext3_discard_reservation will remove an already
unlinked reservation window node from the filesystem reservation tree:
It thinks the reservation is still linked in the filesystem reservation
tree, but it is actually temperately removed from the tree by
allocate_new_reservation() when it failed to make a new reservation from
the current group and try to make a new reservation from next block
group.

Here is how it could happen:

CPU 1
try to allocate a block in group1 with given reservation window my_rsv
ext3_try_to_allocate_with_rsv(group
----copy reservation window my_rsv into local rsv_copy
ext3_try_to_allocate(...rsv_copy)
----no free block in existing reservation window,
----need a new reservation window
spin_lock(&rsv_lock);

CPU 2

ext3_discard_reservation
if (!rsv_is_empty()
----this is true
spin_lock(&rsv_lock)
----waiting for thread 1

CPU 1:

allocate_new_reservation
failed to reserve blocks in this group
remove the window from the tree
rsv_window_remove(my_rsv)
----window node is unlinked from the tree here
return -1
spin_unlock(&rsv_lock)
ext3_try_to_allocate_with_rsv() failed in this group
group++

CPU 2
spin_lock(&rsv_lock) succeed
rsv_remove_window ()
---------------break, trying to remove a unlinked node from the tree
....

CPU 1:
ext3_try_to_allocate_with_rsv(group, my_rsv)
rsv_is_empty is true, need a new reservation window
spin_lock(&rsv_lock);
^--------------- spinning forever

We need to re-check whether the reservation window is still linked to
the tree after grab the rsv_lock spin lock in ext3_discard_reservation,
to prevent panic in rsv_remove_window->rb_erase.
Requires Linux 2.6.11 kernel source as from git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/linux-2.6.11.y.git

--- a/fs/ext3/balloc.c
+++ b/fs/ext3/balloc.c
@@ -268,7 +268,8 @@ void ext3_discard_reservation(struct ino
if (!rsv_is_empty(&rsv->rsv_window)) {
spin_lock(rsv_lock);
- rsv_window_remove(inode->i_sb, rsv);
+ if (!rsv_is_empty(&rsv->rsv_window))
+ rsv_window_remove(inode->i_sb, rsv);
spin_unlock(rsv_lock);
}
}

(purple: line numbers and function names; red: line removed; green: line added)

Files

Unmodified sources

Comments

Although this problem is extremely well explained, it was not possible to detect it using BLAST. It requires two kernel threads to operate concurrently on the driver involved, which cannot be modelled in BLAST.

Source: http://www.kernel.org



Jan Tobias Mühlberg, $Date$