lustre/obdclass/range_lock.c

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   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.
   9  *
  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).
  15  *
  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
  19  *
  20  * GPL HEADER END
  21  */
  22 /*
  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
  25  * file.
  26  *
  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
  29  *
  30  * This file could later replaced by the upstream kernel version.
  31  */
  32 /*
  33  * Author: Prakash Surya <surya1@llnl.gov>
  34  * Author: Bobi Jam <bobijam.xu@intel.com>
  35  */
  36 #ifdef HAVE_SCHED_HEADERS
  37 #include <linux/sched/signal.h>
  38 #endif
  39 #include <uapi/linux/lustre/lustre_user.h>
  40 #include <range_lock.h>
  41
  42 /**
  43  * Initialize a range lock tree
  44  *
  45  * \param tree [in]     an empty range lock tree
  46  *
  47  * Pre:  Caller should have allocated the range lock tree.
  48  * Post: The range lock tree is ready to function.
  49  */
  50 void range_lock_tree_init(struct range_lock_tree *tree)
  51 {
  52         tree->rlt_root = NULL;
  53         tree->rlt_sequence = 0;
  54         spin_lock_init(&tree->rlt_lock);
  55 }
  56 EXPORT_SYMBOL(range_lock_tree_init);
  57
  58 /**
  59  * Intialize a range lock node
  60  *
  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
  64  *
  65  * Pre:  Caller should have allocated the range lock node.
  66  * Post: The range lock node is meant to cover [start, end] region
  67  */
  68 int range_lock_init(struct range_lock *lock, __u64 start, __u64 end)
  69 {
  70         int rc;
  71
  72         interval_init(&lock->rl_node);
  73         if (end != LUSTRE_EOF)
  74                 end >>= PAGE_SHIFT;
  75         rc = interval_set(&lock->rl_node, start >> PAGE_SHIFT, end);
  76         if (rc)
  77                 return rc;
  78
  79         INIT_LIST_HEAD(&lock->rl_next_lock);
  80         lock->rl_task = NULL;
  81         lock->rl_lock_count = 0;
  82         lock->rl_blocking_ranges = 0;
  83         lock->rl_sequence = 0;
  84         return rc;
  85 }
  86 EXPORT_SYMBOL(range_lock_init);
  87
  88 static inline struct range_lock *next_lock(struct range_lock *lock)
  89 {
  90         return list_entry(lock->rl_next_lock.next, typeof(*lock), rl_next_lock);
  91 }
  92
  93 /**
  94  * Helper function of range_unlock()
  95  *
  96  * \param node [in]     a range lock found overlapped during interval node
  97  *                      search
  98  * \param arg [in]      the range lock to be tested
  99  *
 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
 103  */
 104 static enum interval_iter range_unlock_cb(struct interval_node *node, void *arg)
 105 {
 106         struct range_lock *lock = arg;
 107         struct range_lock *overlap = node2rangelock(node);
 108         struct range_lock *iter;
 109         ENTRY;
 110
 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);
 115                 }
 116         }
 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);
 121         }
 122         RETURN(INTERVAL_ITER_CONT);
 123 }
 124
 125 /**
 126  * Unlock a range lock, wake up locks blocked by this lock.
 127  *
 128  * \param tree [in]     range lock tree
 129  * \param lock [in]     range lock to be deleted
 130  *
 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().
 134  */
 135 void range_unlock(struct range_lock_tree *tree, struct range_lock *lock)
 136 {
 137         ENTRY;
 138
 139         spin_lock(&tree->rlt_lock);
 140         if (!list_empty(&lock->rl_next_lock)) {
 141                 struct range_lock *next;
 142
 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);
 149                 } else {
 150                         /* find the first lock in tree */
 151                         list_for_each_entry(next, &lock->rl_next_lock,
 152                                             rl_next_lock) {
 153                                 if (!interval_is_intree(&next->rl_node))
 154                                         continue;
 155
 156                                 LASSERT(next->rl_lock_count > 0);
 157                                 next->rl_lock_count--;
 158                                 break;
 159                         }
 160                 }
 161                 list_del_init(&lock->rl_next_lock);
 162         } else {
 163                 LASSERT(interval_is_intree(&lock->rl_node));
 164                 interval_erase(&lock->rl_node, &tree->rlt_root);
 165         }
 166
 167         interval_search(tree->rlt_root, &lock->rl_node.in_extent,
 168                         range_unlock_cb, lock);
 169         spin_unlock(&tree->rlt_lock);
 170
 171         EXIT;
 172 }
 173 EXPORT_SYMBOL(range_unlock);
 174
 175 /**
 176  * Helper function of range_lock()
 177  *
 178  * \param node [in]     a range lock found overlapped during interval node
 179  *                      search
 180  * \param arg [in]      the range lock to be tested
 181  *
 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
 185  */
 186 static enum interval_iter range_lock_cb(struct interval_node *node, void *arg)
 187 {
 188         struct range_lock *lock = (struct range_lock *)arg;
 189         struct range_lock *overlap = node2rangelock(node);
 190
 191         lock->rl_blocking_ranges += overlap->rl_lock_count + 1;
 192         RETURN(INTERVAL_ITER_CONT);
 193 }
 194
 195 /**
 196  * Lock a region
 197  *
 198  * \param tree [in]     range lock tree
 199  * \param lock [in]     range lock node containing the region span
 200  *
 201  * \retval 0    get the range lock
 202  * \retval <0   error code while not getting the range lock
 203  *
 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,
 206  * it wait again.
 207  */
 208 int range_lock(struct range_lock_tree *tree, struct range_lock *lock)
 209 {
 210         struct interval_node *node;
 211         int rc = 0;
 212         ENTRY;
 213
 214         spin_lock(&tree->rlt_lock);
 215         /*
 216          * We need to check for all conflicting intervals
 217          * already in the tree.
 218          */
 219         interval_search(tree->rlt_root, &lock->rl_node.in_extent,
 220                         range_lock_cb, lock);
 221         /*
 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().
 225          */
 226         node = interval_insert(&lock->rl_node, &tree->rlt_root);
 227         if (node != NULL) {
 228                 struct range_lock *tmp = node2rangelock(node);
 229
 230                 list_add_tail(&lock->rl_next_lock, &tmp->rl_next_lock);
 231                 tmp->rl_lock_count++;
 232         }
 233         lock->rl_sequence = ++tree->rlt_sequence;
 234
 235         while (lock->rl_blocking_ranges > 0) {
 236                 lock->rl_task = current;
 237                 __set_current_state(TASK_INTERRUPTIBLE);
 238                 spin_unlock(&tree->rlt_lock);
 239                 schedule();
 240
 241                 if (signal_pending(current)) {
 242                         range_unlock(tree, lock);
 243                         GOTO(out, rc = -ERESTARTSYS);
 244                 }
 245                 spin_lock(&tree->rlt_lock);
 246         }
 247         spin_unlock(&tree->rlt_lock);
 248 out:
 249         RETURN(rc);
 250 }
 251 EXPORT_SYMBOL(range_lock);