Commit | Line | Data |
---|---|---|
ec23eb54 MCC |
1 | ================= |
2 | Directory Locking | |
3 | ================= | |
4 | ||
5 | ||
6 | Locking scheme used for directory operations is based on two | |
d42b3868 | 7 | kinds of locks - per-inode (->i_rwsem) and per-filesystem |
c2b38989 | 8 | (->s_vfs_rename_mutex). |
1da177e4 | 9 | |
ec23eb54 | 10 | When taking the i_rwsem on multiple non-directory objects, we |
6cedba89 BF |
11 | always acquire the locks in order by increasing address. We'll call |
12 | that "inode pointer" order in the following. | |
13 | ||
ec23eb54 | 14 | For our purposes all operations fall in 5 classes: |
1da177e4 LT |
15 | |
16 | 1) read access. Locking rules: caller locks directory we are accessing. | |
d42b3868 | 17 | The lock is taken shared. |
1da177e4 | 18 | |
d42b3868 AV |
19 | 2) object creation. Locking rules: same as above, but the lock is taken |
20 | exclusive. | |
1da177e4 LT |
21 | |
22 | 3) object removal. Locking rules: caller locks parent, finds victim, | |
d42b3868 | 23 | locks victim and calls the method. Locks are exclusive. |
1da177e4 LT |
24 | |
25 | 4) rename() that is _not_ cross-directory. Locking rules: caller locks | |
d42b3868 | 26 | the parent and finds source and target. In case of exchange (with |
18fc84da | 27 | RENAME_EXCHANGE in flags argument) lock both. In any case, |
d42b3868 AV |
28 | if the target already exists, lock it. If the source is a non-directory, |
29 | lock it. If we need to lock both, lock them in inode pointer order. | |
30 | Then call the method. All locks are exclusive. | |
31 | NB: we might get away with locking the the source (and target in exchange | |
32 | case) shared. | |
1da177e4 LT |
33 | |
34 | 5) link creation. Locking rules: | |
ec23eb54 | 35 | |
1da177e4 LT |
36 | * lock parent |
37 | * check that source is not a directory | |
38 | * lock source | |
39 | * call the method. | |
ec23eb54 | 40 | |
d42b3868 | 41 | All locks are exclusive. |
1da177e4 LT |
42 | |
43 | 6) cross-directory rename. The trickiest in the whole bunch. Locking | |
44 | rules: | |
ec23eb54 | 45 | |
1da177e4 LT |
46 | * lock the filesystem |
47 | * lock parents in "ancestors first" order. | |
48 | * find source and target. | |
49 | * if old parent is equal to or is a descendent of target | |
ec23eb54 | 50 | fail with -ENOTEMPTY |
1da177e4 | 51 | * if new parent is equal to or is a descendent of source |
ec23eb54 | 52 | fail with -ELOOP |
d42b3868 AV |
53 | * If it's an exchange, lock both the source and the target. |
54 | * If the target exists, lock it. If the source is a non-directory, | |
55 | lock it. If we need to lock both, do so in inode pointer order. | |
1da177e4 | 56 | * call the method. |
ec23eb54 | 57 | |
d42b3868 AV |
58 | All ->i_rwsem are taken exclusive. Again, we might get away with locking |
59 | the the source (and target in exchange case) shared. | |
1da177e4 LT |
60 | |
61 | The rules above obviously guarantee that all directories that are going to be | |
62 | read, modified or removed by method will be locked by caller. | |
63 | ||
64 | ||
65 | If no directory is its own ancestor, the scheme above is deadlock-free. | |
ec23eb54 | 66 | |
1da177e4 LT |
67 | Proof: |
68 | ||
69 | First of all, at any moment we have a partial ordering of the | |
ec23eb54 | 70 | objects - A < B iff A is an ancestor of B. |
1da177e4 LT |
71 | |
72 | That ordering can change. However, the following is true: | |
73 | ||
74 | (1) if object removal or non-cross-directory rename holds lock on A and | |
75 | attempts to acquire lock on B, A will remain the parent of B until we | |
76 | acquire the lock on B. (Proof: only cross-directory rename can change | |
77 | the parent of object and it would have to lock the parent). | |
78 | ||
79 | (2) if cross-directory rename holds the lock on filesystem, order will not | |
80 | change until rename acquires all locks. (Proof: other cross-directory | |
81 | renames will be blocked on filesystem lock and we don't start changing | |
82 | the order until we had acquired all locks). | |
83 | ||
6cedba89 BF |
84 | (3) locks on non-directory objects are acquired only after locks on |
85 | directory objects, and are acquired in inode pointer order. | |
86 | (Proof: all operations but renames take lock on at most one | |
87 | non-directory object, except renames, which take locks on source and | |
88 | target in inode pointer order in the case they are not directories.) | |
1da177e4 | 89 | |
ec23eb54 | 90 | Now consider the minimal deadlock. Each process is blocked on |
1da177e4 LT |
91 | attempt to acquire some lock and already holds at least one lock. Let's |
92 | consider the set of contended locks. First of all, filesystem lock is | |
93 | not contended, since any process blocked on it is not holding any locks. | |
d42b3868 | 94 | Thus all processes are blocked on ->i_rwsem. |
1da177e4 | 95 | |
ec23eb54 | 96 | By (3), any process holding a non-directory lock can only be |
6cedba89 BF |
97 | waiting on another non-directory lock with a larger address. Therefore |
98 | the process holding the "largest" such lock can always make progress, and | |
99 | non-directory objects are not included in the set of contended locks. | |
100 | ||
ec23eb54 | 101 | Thus link creation can't be a part of deadlock - it can't be |
6cedba89 | 102 | blocked on source and it means that it doesn't hold any locks. |
1da177e4 | 103 | |
ec23eb54 | 104 | Any contended object is either held by cross-directory rename or |
1da177e4 LT |
105 | has a child that is also contended. Indeed, suppose that it is held by |
106 | operation other than cross-directory rename. Then the lock this operation | |
107 | is blocked on belongs to child of that object due to (1). | |
108 | ||
ec23eb54 | 109 | It means that one of the operations is cross-directory rename. |
1da177e4 LT |
110 | Otherwise the set of contended objects would be infinite - each of them |
111 | would have a contended child and we had assumed that no object is its | |
112 | own descendent. Moreover, there is exactly one cross-directory rename | |
113 | (see above). | |
114 | ||
ec23eb54 | 115 | Consider the object blocking the cross-directory rename. One |
1da177e4 | 116 | of its descendents is locked by cross-directory rename (otherwise we |
670e9f34 | 117 | would again have an infinite set of contended objects). But that |
1da177e4 LT |
118 | means that cross-directory rename is taking locks out of order. Due |
119 | to (2) the order hadn't changed since we had acquired filesystem lock. | |
120 | But locking rules for cross-directory rename guarantee that we do not | |
121 | try to acquire lock on descendent before the lock on ancestor. | |
122 | Contradiction. I.e. deadlock is impossible. Q.E.D. | |
123 | ||
124 | ||
ec23eb54 | 125 | These operations are guaranteed to avoid loop creation. Indeed, |
1da177e4 LT |
126 | the only operation that could introduce loops is cross-directory rename. |
127 | Since the only new (parent, child) pair added by rename() is (new parent, | |
128 | source), such loop would have to contain these objects and the rest of it | |
129 | would have to exist before rename(). I.e. at the moment of loop creation | |
130 | rename() responsible for that would be holding filesystem lock and new parent | |
131 | would have to be equal to or a descendent of source. But that means that | |
132 | new parent had been equal to or a descendent of source since the moment when | |
133 | we had acquired filesystem lock and rename() would fail with -ELOOP in that | |
134 | case. | |
135 | ||
ec23eb54 | 136 | While this locking scheme works for arbitrary DAGs, it relies on |
1da177e4 LT |
137 | ability to check that directory is a descendent of another object. Current |
138 | implementation assumes that directory graph is a tree. This assumption is | |
139 | also preserved by all operations (cross-directory rename on a tree that would | |
140 | not introduce a cycle will leave it a tree and link() fails for directories). | |
141 | ||
ec23eb54 | 142 | Notice that "directory" in the above == "anything that might have |
1da177e4 LT |
143 | children", so if we are going to introduce hybrid objects we will need |
144 | either to make sure that link(2) doesn't work for them or to make changes | |
145 | in is_subdir() that would make it work even in presence of such beasts. |