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