4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.gnu.org/licenses/gpl-2.0.html
23 * Range lock is used to allow multiple threads writing a single shared
24 * file given each thread is writing to a non-overlapping portion of the
27 * Refer to the possible upstream kernel version of range lock by
28 * Jan Kara <jack@suse.cz>: https://lkml.org/lkml/2013/1/31/480
30 * This file could later replaced by the upstream kernel version.
33 * Author: Prakash Surya <surya1@llnl.gov>
34 * Author: Bobi Jam <bobijam.xu@intel.com>
36 #ifdef HAVE_SCHED_HEADERS
37 #include <linux/sched/signal.h>
39 #include <uapi/linux/lustre/lustre_user.h>
40 #include <range_lock.h>
43 * Initialize a range lock tree
45 * \param tree [in] an empty range lock tree
47 * Pre: Caller should have allocated the range lock tree.
48 * Post: The range lock tree is ready to function.
50 void range_lock_tree_init(struct range_lock_tree *tree)
52 tree->rlt_root = NULL;
53 tree->rlt_sequence = 0;
54 spin_lock_init(&tree->rlt_lock);
56 EXPORT_SYMBOL(range_lock_tree_init);
59 * Intialize a range lock node
61 * \param lock [in] an empty range lock node
62 * \param start [in] start of the covering region
63 * \param end [in] end of the covering region
65 * Pre: Caller should have allocated the range lock node.
66 * Post: The range lock node is meant to cover [start, end] region
68 int range_lock_init(struct range_lock *lock, __u64 start, __u64 end)
72 interval_init(&lock->rl_node);
73 if (end != LUSTRE_EOF)
75 rc = interval_set(&lock->rl_node, start >> PAGE_SHIFT, end);
79 INIT_LIST_HEAD(&lock->rl_next_lock);
81 lock->rl_lock_count = 0;
82 lock->rl_blocking_ranges = 0;
83 lock->rl_sequence = 0;
86 EXPORT_SYMBOL(range_lock_init);
88 static inline struct range_lock *next_lock(struct range_lock *lock)
90 return list_entry(lock->rl_next_lock.next, typeof(*lock), rl_next_lock);
94 * Helper function of range_unlock()
96 * \param node [in] a range lock found overlapped during interval node
98 * \param arg [in] the range lock to be tested
100 * \retval INTERVAL_ITER_CONT indicate to continue the search for next
101 * overlapping range node
102 * \retval INTERVAL_ITER_STOP indicate to stop the search
104 static enum interval_iter range_unlock_cb(struct interval_node *node, void *arg)
106 struct range_lock *lock = arg;
107 struct range_lock *overlap = node2rangelock(node);
108 struct range_lock *iter;
111 list_for_each_entry(iter, &overlap->rl_next_lock, rl_next_lock) {
112 if (iter->rl_sequence > lock->rl_sequence) {
113 --iter->rl_blocking_ranges;
114 LASSERT(iter->rl_blocking_ranges > 0);
117 if (overlap->rl_sequence > lock->rl_sequence) {
118 --overlap->rl_blocking_ranges;
119 if (overlap->rl_blocking_ranges == 0)
120 wake_up_process(overlap->rl_task);
122 RETURN(INTERVAL_ITER_CONT);
126 * Unlock a range lock, wake up locks blocked by this lock.
128 * \param tree [in] range lock tree
129 * \param lock [in] range lock to be deleted
131 * If this lock has been granted, relase it; if not, just delete it from
132 * the tree or the same region lock list. Wake up those locks only blocked
133 * by this lock through range_unlock_cb().
135 void range_unlock(struct range_lock_tree *tree, struct range_lock *lock)
139 spin_lock(&tree->rlt_lock);
140 if (!list_empty(&lock->rl_next_lock)) {
141 struct range_lock *next;
143 if (interval_is_intree(&lock->rl_node)) { /* first lock */
144 /* Insert the next same range lock into the tree */
145 next = next_lock(lock);
146 next->rl_lock_count = lock->rl_lock_count - 1;
147 interval_erase(&lock->rl_node, &tree->rlt_root);
148 interval_insert(&next->rl_node, &tree->rlt_root);
150 /* find the first lock in tree */
151 list_for_each_entry(next, &lock->rl_next_lock,
153 if (!interval_is_intree(&next->rl_node))
156 LASSERT(next->rl_lock_count > 0);
157 next->rl_lock_count--;
161 list_del_init(&lock->rl_next_lock);
163 LASSERT(interval_is_intree(&lock->rl_node));
164 interval_erase(&lock->rl_node, &tree->rlt_root);
167 interval_search(tree->rlt_root, &lock->rl_node.in_extent,
168 range_unlock_cb, lock);
169 spin_unlock(&tree->rlt_lock);
173 EXPORT_SYMBOL(range_unlock);
176 * Helper function of range_lock()
178 * \param node [in] a range lock found overlapped during interval node
180 * \param arg [in] the range lock to be tested
182 * \retval INTERVAL_ITER_CONT indicate to continue the search for next
183 * overlapping range node
184 * \retval INTERVAL_ITER_STOP indicate to stop the search
186 static enum interval_iter range_lock_cb(struct interval_node *node, void *arg)
188 struct range_lock *lock = (struct range_lock *)arg;
189 struct range_lock *overlap = node2rangelock(node);
191 lock->rl_blocking_ranges += overlap->rl_lock_count + 1;
192 RETURN(INTERVAL_ITER_CONT);
198 * \param tree [in] range lock tree
199 * \param lock [in] range lock node containing the region span
201 * \retval 0 get the range lock
202 * \retval <0 error code while not getting the range lock
204 * If there exists overlapping range lock, the new lock will wait and
205 * retry, if later it find that it is not the chosen one to wake up,
208 int range_lock(struct range_lock_tree *tree, struct range_lock *lock)
210 struct interval_node *node;
214 spin_lock(&tree->rlt_lock);
216 * We need to check for all conflicting intervals
217 * already in the tree.
219 interval_search(tree->rlt_root, &lock->rl_node.in_extent,
220 range_lock_cb, lock);
222 * Insert to the tree if I am unique, otherwise I've been linked to
223 * the rl_next_lock of another lock which has the same range as mine
224 * in range_lock_cb().
226 node = interval_insert(&lock->rl_node, &tree->rlt_root);
228 struct range_lock *tmp = node2rangelock(node);
230 list_add_tail(&lock->rl_next_lock, &tmp->rl_next_lock);
231 tmp->rl_lock_count++;
233 lock->rl_sequence = ++tree->rlt_sequence;
235 while (lock->rl_blocking_ranges > 0) {
236 lock->rl_task = current;
237 __set_current_state(TASK_INTERRUPTIBLE);
238 spin_unlock(&tree->rlt_lock);
241 if (signal_pending(current)) {
242 range_unlock(tree, lock);
243 GOTO(out, rc = -ERESTARTSYS);
245 spin_lock(&tree->rlt_lock);
247 spin_unlock(&tree->rlt_lock);
251 EXPORT_SYMBOL(range_lock);