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