1104e2ed7Sperrin /* 2104e2ed7Sperrin * CDDL HEADER START 3104e2ed7Sperrin * 4104e2ed7Sperrin * The contents of this file are subject to the terms of the 5104e2ed7Sperrin * Common Development and Distribution License (the "License"). 6104e2ed7Sperrin * You may not use this file except in compliance with the License. 7104e2ed7Sperrin * 8104e2ed7Sperrin * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9104e2ed7Sperrin * or http://www.opensolaris.org/os/licensing. 10104e2ed7Sperrin * See the License for the specific language governing permissions 11104e2ed7Sperrin * and limitations under the License. 12104e2ed7Sperrin * 13104e2ed7Sperrin * When distributing Covered Code, include this CDDL HEADER in each 14104e2ed7Sperrin * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15104e2ed7Sperrin * If applicable, add the following below this CDDL HEADER, with the 16104e2ed7Sperrin * fields enclosed by brackets "[]" replaced with your own identifying 17104e2ed7Sperrin * information: Portions Copyright [yyyy] [name of copyright owner] 18104e2ed7Sperrin * 19104e2ed7Sperrin * CDDL HEADER END 20104e2ed7Sperrin */ 21104e2ed7Sperrin /* 220a586ceaSMark Shellenbaum * Copyright 2010 Sun Microsystems, Inc. All rights reserved. 23104e2ed7Sperrin * Use is subject to license terms. 24104e2ed7Sperrin */ 25fb09f5aaSMadhav Suresh /* 26*79315247SMatthew Ahrens * Copyright (c) 2012, 2018 by Delphix. All rights reserved. 27fb09f5aaSMadhav Suresh */ 28104e2ed7Sperrin 29104e2ed7Sperrin /* 30104e2ed7Sperrin * This file contains the code to implement file range locking in 31f7170741SWill Andrews * ZFS, although there isn't much specific to ZFS (all that comes to mind is 32104e2ed7Sperrin * support for growing the blocksize). 33104e2ed7Sperrin * 34104e2ed7Sperrin * Interface 35104e2ed7Sperrin * --------- 36104e2ed7Sperrin * Defined in zfs_rlock.h but essentially: 37*79315247SMatthew Ahrens * lr = rangelock_enter(zp, off, len, lock_type); 38*79315247SMatthew Ahrens * rangelock_reduce(lr, off, len); // optional 39*79315247SMatthew Ahrens * rangelock_exit(lr); 40104e2ed7Sperrin * 41104e2ed7Sperrin * AVL tree 42104e2ed7Sperrin * -------- 43104e2ed7Sperrin * An AVL tree is used to maintain the state of the existing ranges 44104e2ed7Sperrin * that are locked for exclusive (writer) or shared (reader) use. 45104e2ed7Sperrin * The starting range offset is used for searching and sorting the tree. 46104e2ed7Sperrin * 47104e2ed7Sperrin * Common case 48104e2ed7Sperrin * ----------- 49*79315247SMatthew Ahrens * The (hopefully) usual case is of no overlaps or contention for locks. On 50*79315247SMatthew Ahrens * entry to rangelock_enter(), a locked_range_t is allocated; the tree 51*79315247SMatthew Ahrens * searched that finds no overlap, and *this* locked_range_t is placed in the 52*79315247SMatthew Ahrens * tree. 53104e2ed7Sperrin * 54104e2ed7Sperrin * Overlaps/Reference counting/Proxy locks 55104e2ed7Sperrin * --------------------------------------- 56104e2ed7Sperrin * The avl code only allows one node at a particular offset. Also it's very 57104e2ed7Sperrin * inefficient to search through all previous entries looking for overlaps 58104e2ed7Sperrin * (because the very 1st in the ordered list might be at offset 0 but 59104e2ed7Sperrin * cover the whole file). 60104e2ed7Sperrin * So this implementation uses reference counts and proxy range locks. 61104e2ed7Sperrin * Firstly, only reader locks use reference counts and proxy locks, 62104e2ed7Sperrin * because writer locks are exclusive. 63104e2ed7Sperrin * When a reader lock overlaps with another then a proxy lock is created 64104e2ed7Sperrin * for that range and replaces the original lock. If the overlap 65104e2ed7Sperrin * is exact then the reference count of the proxy is simply incremented. 66104e2ed7Sperrin * Otherwise, the proxy lock is split into smaller lock ranges and 67104e2ed7Sperrin * new proxy locks created for non overlapping ranges. 68104e2ed7Sperrin * The reference counts are adjusted accordingly. 69104e2ed7Sperrin * Meanwhile, the orginal lock is kept around (this is the callers handle) 70104e2ed7Sperrin * and its offset and length are used when releasing the lock. 71104e2ed7Sperrin * 72104e2ed7Sperrin * Thread coordination 73104e2ed7Sperrin * ------------------- 74104e2ed7Sperrin * In order to make wakeups efficient and to ensure multiple continuous 75104e2ed7Sperrin * readers on a range don't starve a writer for the same range lock, 76104e2ed7Sperrin * two condition variables are allocated in each rl_t. 77104e2ed7Sperrin * If a writer (or reader) can't get a range it initialises the writer 78104e2ed7Sperrin * (or reader) cv; sets a flag saying there's a writer (or reader) waiting; 79104e2ed7Sperrin * and waits on that cv. When a thread unlocks that range it wakes up all 80104e2ed7Sperrin * writers then all readers before destroying the lock. 81104e2ed7Sperrin * 82104e2ed7Sperrin * Append mode writes 83104e2ed7Sperrin * ------------------ 84104e2ed7Sperrin * Append mode writes need to lock a range at the end of a file. 85104e2ed7Sperrin * The offset of the end of the file is determined under the 86104e2ed7Sperrin * range locking mutex, and the lock type converted from RL_APPEND to 87104e2ed7Sperrin * RL_WRITER and the range locked. 88104e2ed7Sperrin * 89104e2ed7Sperrin * Grow block handling 90104e2ed7Sperrin * ------------------- 91*79315247SMatthew Ahrens * ZFS supports multiple block sizes, up to 16MB. The smallest 92104e2ed7Sperrin * block size is used for the file which is grown as needed. During this 93104e2ed7Sperrin * growth all other writers and readers must be excluded. 94104e2ed7Sperrin * So if the block size needs to be grown then the whole file is 95104e2ed7Sperrin * exclusively locked, then later the caller will reduce the lock 96*79315247SMatthew Ahrens * range to just the range to be written using rangelock_reduce(). 97104e2ed7Sperrin */ 98104e2ed7Sperrin 99*79315247SMatthew Ahrens #include <sys/zfs_context.h> 100104e2ed7Sperrin #include <sys/zfs_rlock.h> 101104e2ed7Sperrin 102*79315247SMatthew Ahrens /* 103*79315247SMatthew Ahrens * AVL comparison function used to order range locks 104*79315247SMatthew Ahrens * Locks are ordered on the start offset of the range. 105*79315247SMatthew Ahrens */ 106*79315247SMatthew Ahrens static int 107*79315247SMatthew Ahrens rangelock_compare(const void *arg1, const void *arg2) 108*79315247SMatthew Ahrens { 109*79315247SMatthew Ahrens const locked_range_t *rl1 = arg1; 110*79315247SMatthew Ahrens const locked_range_t *rl2 = arg2; 111*79315247SMatthew Ahrens 112*79315247SMatthew Ahrens if (rl1->lr_offset > rl2->lr_offset) 113*79315247SMatthew Ahrens return (1); 114*79315247SMatthew Ahrens if (rl1->lr_offset < rl2->lr_offset) 115*79315247SMatthew Ahrens return (-1); 116*79315247SMatthew Ahrens return (0); 117*79315247SMatthew Ahrens } 118*79315247SMatthew Ahrens 119*79315247SMatthew Ahrens /* 120*79315247SMatthew Ahrens * The callback is invoked when acquiring a RL_WRITER or RL_APPEND lock. 121*79315247SMatthew Ahrens * It must convert RL_APPEND to RL_WRITER (starting at the end of the file), 122*79315247SMatthew Ahrens * and may increase the range that's locked for RL_WRITER. 123*79315247SMatthew Ahrens */ 124*79315247SMatthew Ahrens void 125*79315247SMatthew Ahrens rangelock_init(rangelock_t *rl, rangelock_cb_t *cb, void *arg) 126*79315247SMatthew Ahrens { 127*79315247SMatthew Ahrens mutex_init(&rl->rl_lock, NULL, MUTEX_DEFAULT, NULL); 128*79315247SMatthew Ahrens avl_create(&rl->rl_tree, rangelock_compare, 129*79315247SMatthew Ahrens sizeof (locked_range_t), offsetof(locked_range_t, lr_node)); 130*79315247SMatthew Ahrens rl->rl_cb = cb; 131*79315247SMatthew Ahrens rl->rl_arg = arg; 132*79315247SMatthew Ahrens } 133*79315247SMatthew Ahrens 134*79315247SMatthew Ahrens void 135*79315247SMatthew Ahrens rangelock_fini(rangelock_t *rl) 136*79315247SMatthew Ahrens { 137*79315247SMatthew Ahrens mutex_destroy(&rl->rl_lock); 138*79315247SMatthew Ahrens avl_destroy(&rl->rl_tree); 139*79315247SMatthew Ahrens } 140*79315247SMatthew Ahrens 141104e2ed7Sperrin /* 142104e2ed7Sperrin * Check if a write lock can be grabbed, or wait and recheck until available. 143104e2ed7Sperrin */ 144104e2ed7Sperrin static void 145*79315247SMatthew Ahrens rangelock_enter_writer(rangelock_t *rl, locked_range_t *new) 146104e2ed7Sperrin { 147*79315247SMatthew Ahrens avl_tree_t *tree = &rl->rl_tree; 148*79315247SMatthew Ahrens locked_range_t *lr; 149104e2ed7Sperrin avl_index_t where; 150*79315247SMatthew Ahrens uint64_t orig_off = new->lr_offset; 151*79315247SMatthew Ahrens uint64_t orig_len = new->lr_length; 152*79315247SMatthew Ahrens rangelock_type_t orig_type = new->lr_type; 153104e2ed7Sperrin 154104e2ed7Sperrin for (;;) { 155104e2ed7Sperrin /* 156*79315247SMatthew Ahrens * Call callback which can modify new->r_off,len,type. 157*79315247SMatthew Ahrens * Note, the callback is used by the ZPL to handle appending 158*79315247SMatthew Ahrens * and changing blocksizes. It isn't needed for zvols. 159104e2ed7Sperrin */ 160*79315247SMatthew Ahrens if (rl->rl_cb != NULL) { 161*79315247SMatthew Ahrens rl->rl_cb(new, rl->rl_arg); 162104e2ed7Sperrin } 163104e2ed7Sperrin 164*79315247SMatthew Ahrens /* 165*79315247SMatthew Ahrens * If the type was APPEND, the callback must convert it to 166*79315247SMatthew Ahrens * WRITER. 167*79315247SMatthew Ahrens */ 168*79315247SMatthew Ahrens ASSERT3U(new->lr_type, ==, RL_WRITER); 169*79315247SMatthew Ahrens 170104e2ed7Sperrin /* 171104e2ed7Sperrin * First check for the usual case of no locks 172104e2ed7Sperrin */ 173104e2ed7Sperrin if (avl_numnodes(tree) == 0) { 174104e2ed7Sperrin avl_add(tree, new); 175104e2ed7Sperrin return; 176104e2ed7Sperrin } 177104e2ed7Sperrin 178104e2ed7Sperrin /* 179104e2ed7Sperrin * Look for any locks in the range. 180104e2ed7Sperrin */ 181*79315247SMatthew Ahrens lr = avl_find(tree, new, &where); 182*79315247SMatthew Ahrens if (lr != NULL) 183104e2ed7Sperrin goto wait; /* already locked at same offset */ 184104e2ed7Sperrin 185*79315247SMatthew Ahrens lr = (locked_range_t *)avl_nearest(tree, where, AVL_AFTER); 186*79315247SMatthew Ahrens if (lr != NULL && 187*79315247SMatthew Ahrens lr->lr_offset < new->lr_offset + new->lr_length) 188104e2ed7Sperrin goto wait; 189104e2ed7Sperrin 190*79315247SMatthew Ahrens lr = (locked_range_t *)avl_nearest(tree, where, AVL_BEFORE); 191*79315247SMatthew Ahrens if (lr != NULL && 192*79315247SMatthew Ahrens lr->lr_offset + lr->lr_length > new->lr_offset) 193104e2ed7Sperrin goto wait; 194104e2ed7Sperrin 195104e2ed7Sperrin avl_insert(tree, new, where); 196104e2ed7Sperrin return; 197104e2ed7Sperrin wait: 198*79315247SMatthew Ahrens if (!lr->lr_write_wanted) { 199*79315247SMatthew Ahrens cv_init(&lr->lr_write_cv, NULL, CV_DEFAULT, NULL); 200*79315247SMatthew Ahrens lr->lr_write_wanted = B_TRUE; 201104e2ed7Sperrin } 202*79315247SMatthew Ahrens cv_wait(&lr->lr_write_cv, &rl->rl_lock); 203104e2ed7Sperrin 204104e2ed7Sperrin /* reset to original */ 205*79315247SMatthew Ahrens new->lr_offset = orig_off; 206*79315247SMatthew Ahrens new->lr_length = orig_len; 207*79315247SMatthew Ahrens new->lr_type = orig_type; 208104e2ed7Sperrin } 209104e2ed7Sperrin } 210104e2ed7Sperrin 211104e2ed7Sperrin /* 212104e2ed7Sperrin * If this is an original (non-proxy) lock then replace it by 213104e2ed7Sperrin * a proxy and return the proxy. 214104e2ed7Sperrin */ 215*79315247SMatthew Ahrens static locked_range_t * 216*79315247SMatthew Ahrens rangelock_proxify(avl_tree_t *tree, locked_range_t *lr) 217104e2ed7Sperrin { 218*79315247SMatthew Ahrens locked_range_t *proxy; 219104e2ed7Sperrin 220*79315247SMatthew Ahrens if (lr->lr_proxy) 221*79315247SMatthew Ahrens return (lr); /* already a proxy */ 222104e2ed7Sperrin 223*79315247SMatthew Ahrens ASSERT3U(lr->lr_count, ==, 1); 224*79315247SMatthew Ahrens ASSERT(lr->lr_write_wanted == B_FALSE); 225*79315247SMatthew Ahrens ASSERT(lr->lr_read_wanted == B_FALSE); 226*79315247SMatthew Ahrens avl_remove(tree, lr); 227*79315247SMatthew Ahrens lr->lr_count = 0; 228104e2ed7Sperrin 229104e2ed7Sperrin /* create a proxy range lock */ 230*79315247SMatthew Ahrens proxy = kmem_alloc(sizeof (locked_range_t), KM_SLEEP); 231*79315247SMatthew Ahrens proxy->lr_offset = lr->lr_offset; 232*79315247SMatthew Ahrens proxy->lr_length = lr->lr_length; 233*79315247SMatthew Ahrens proxy->lr_count = 1; 234*79315247SMatthew Ahrens proxy->lr_type = RL_READER; 235*79315247SMatthew Ahrens proxy->lr_proxy = B_TRUE; 236*79315247SMatthew Ahrens proxy->lr_write_wanted = B_FALSE; 237*79315247SMatthew Ahrens proxy->lr_read_wanted = B_FALSE; 238104e2ed7Sperrin avl_add(tree, proxy); 239104e2ed7Sperrin 240104e2ed7Sperrin return (proxy); 241104e2ed7Sperrin } 242104e2ed7Sperrin 243104e2ed7Sperrin /* 244104e2ed7Sperrin * Split the range lock at the supplied offset 245104e2ed7Sperrin * returning the *front* proxy. 246104e2ed7Sperrin */ 247*79315247SMatthew Ahrens static locked_range_t * 248*79315247SMatthew Ahrens rangelock_split(avl_tree_t *tree, locked_range_t *lr, uint64_t off) 249104e2ed7Sperrin { 250*79315247SMatthew Ahrens ASSERT3U(lr->lr_length, >, 1); 251*79315247SMatthew Ahrens ASSERT3U(off, >, lr->lr_offset); 252*79315247SMatthew Ahrens ASSERT3U(off, <, lr->lr_offset + lr->lr_length); 253*79315247SMatthew Ahrens ASSERT(lr->lr_write_wanted == B_FALSE); 254*79315247SMatthew Ahrens ASSERT(lr->lr_read_wanted == B_FALSE); 255104e2ed7Sperrin 256104e2ed7Sperrin /* create the rear proxy range lock */ 257*79315247SMatthew Ahrens locked_range_t *rear = kmem_alloc(sizeof (locked_range_t), KM_SLEEP); 258*79315247SMatthew Ahrens rear->lr_offset = off; 259*79315247SMatthew Ahrens rear->lr_length = lr->lr_offset + lr->lr_length - off; 260*79315247SMatthew Ahrens rear->lr_count = lr->lr_count; 261*79315247SMatthew Ahrens rear->lr_type = RL_READER; 262*79315247SMatthew Ahrens rear->lr_proxy = B_TRUE; 263*79315247SMatthew Ahrens rear->lr_write_wanted = B_FALSE; 264*79315247SMatthew Ahrens rear->lr_read_wanted = B_FALSE; 265*79315247SMatthew Ahrens 266*79315247SMatthew Ahrens locked_range_t *front = rangelock_proxify(tree, lr); 267*79315247SMatthew Ahrens front->lr_length = off - lr->lr_offset; 268104e2ed7Sperrin 269104e2ed7Sperrin avl_insert_here(tree, rear, front, AVL_AFTER); 270104e2ed7Sperrin return (front); 271104e2ed7Sperrin } 272104e2ed7Sperrin 273104e2ed7Sperrin /* 274104e2ed7Sperrin * Create and add a new proxy range lock for the supplied range. 275104e2ed7Sperrin */ 276104e2ed7Sperrin static void 277*79315247SMatthew Ahrens rangelock_new_proxy(avl_tree_t *tree, uint64_t off, uint64_t len) 278104e2ed7Sperrin { 279*79315247SMatthew Ahrens ASSERT(len != 0); 280*79315247SMatthew Ahrens locked_range_t *lr = kmem_alloc(sizeof (locked_range_t), KM_SLEEP); 281*79315247SMatthew Ahrens lr->lr_offset = off; 282*79315247SMatthew Ahrens lr->lr_length = len; 283*79315247SMatthew Ahrens lr->lr_count = 1; 284*79315247SMatthew Ahrens lr->lr_type = RL_READER; 285*79315247SMatthew Ahrens lr->lr_proxy = B_TRUE; 286*79315247SMatthew Ahrens lr->lr_write_wanted = B_FALSE; 287*79315247SMatthew Ahrens lr->lr_read_wanted = B_FALSE; 288*79315247SMatthew Ahrens avl_add(tree, lr); 289104e2ed7Sperrin } 290104e2ed7Sperrin 291104e2ed7Sperrin static void 292*79315247SMatthew Ahrens rangelock_add_reader(avl_tree_t *tree, locked_range_t *new, 293*79315247SMatthew Ahrens locked_range_t *prev, avl_index_t where) 294104e2ed7Sperrin { 295*79315247SMatthew Ahrens locked_range_t *next; 296*79315247SMatthew Ahrens uint64_t off = new->lr_offset; 297*79315247SMatthew Ahrens uint64_t len = new->lr_length; 298104e2ed7Sperrin 299104e2ed7Sperrin /* 300104e2ed7Sperrin * prev arrives either: 301104e2ed7Sperrin * - pointing to an entry at the same offset 302104e2ed7Sperrin * - pointing to the entry with the closest previous offset whose 303104e2ed7Sperrin * range may overlap with the new range 304104e2ed7Sperrin * - null, if there were no ranges starting before the new one 305104e2ed7Sperrin */ 306*79315247SMatthew Ahrens if (prev != NULL) { 307*79315247SMatthew Ahrens if (prev->lr_offset + prev->lr_length <= off) { 308104e2ed7Sperrin prev = NULL; 309*79315247SMatthew Ahrens } else if (prev->lr_offset != off) { 310104e2ed7Sperrin /* 311104e2ed7Sperrin * convert to proxy if needed then 312104e2ed7Sperrin * split this entry and bump ref count 313104e2ed7Sperrin */ 314*79315247SMatthew Ahrens prev = rangelock_split(tree, prev, off); 315104e2ed7Sperrin prev = AVL_NEXT(tree, prev); /* move to rear range */ 316104e2ed7Sperrin } 317104e2ed7Sperrin } 318*79315247SMatthew Ahrens ASSERT((prev == NULL) || (prev->lr_offset == off)); 319104e2ed7Sperrin 320*79315247SMatthew Ahrens if (prev != NULL) 321104e2ed7Sperrin next = prev; 322104e2ed7Sperrin else 323*79315247SMatthew Ahrens next = avl_nearest(tree, where, AVL_AFTER); 324104e2ed7Sperrin 325*79315247SMatthew Ahrens if (next == NULL || off + len <= next->lr_offset) { 326104e2ed7Sperrin /* no overlaps, use the original new rl_t in the tree */ 327104e2ed7Sperrin avl_insert(tree, new, where); 328104e2ed7Sperrin return; 329104e2ed7Sperrin } 330104e2ed7Sperrin 331*79315247SMatthew Ahrens if (off < next->lr_offset) { 332104e2ed7Sperrin /* Add a proxy for initial range before the overlap */ 333*79315247SMatthew Ahrens rangelock_new_proxy(tree, off, next->lr_offset - off); 334104e2ed7Sperrin } 335104e2ed7Sperrin 336*79315247SMatthew Ahrens new->lr_count = 0; /* will use proxies in tree */ 337104e2ed7Sperrin /* 338104e2ed7Sperrin * We now search forward through the ranges, until we go past the end 339104e2ed7Sperrin * of the new range. For each entry we make it a proxy if it 340104e2ed7Sperrin * isn't already, then bump its reference count. If there's any 341104e2ed7Sperrin * gaps between the ranges then we create a new proxy range. 342104e2ed7Sperrin */ 343104e2ed7Sperrin for (prev = NULL; next; prev = next, next = AVL_NEXT(tree, next)) { 344*79315247SMatthew Ahrens if (off + len <= next->lr_offset) 345104e2ed7Sperrin break; 346*79315247SMatthew Ahrens if (prev != NULL && prev->lr_offset + prev->lr_length < 347*79315247SMatthew Ahrens next->lr_offset) { 348104e2ed7Sperrin /* there's a gap */ 349*79315247SMatthew Ahrens ASSERT3U(next->lr_offset, >, 350*79315247SMatthew Ahrens prev->lr_offset + prev->lr_length); 351*79315247SMatthew Ahrens rangelock_new_proxy(tree, 352*79315247SMatthew Ahrens prev->lr_offset + prev->lr_length, 353*79315247SMatthew Ahrens next->lr_offset - 354*79315247SMatthew Ahrens (prev->lr_offset + prev->lr_length)); 355104e2ed7Sperrin } 356*79315247SMatthew Ahrens if (off + len == next->lr_offset + next->lr_length) { 357104e2ed7Sperrin /* exact overlap with end */ 358*79315247SMatthew Ahrens next = rangelock_proxify(tree, next); 359*79315247SMatthew Ahrens next->lr_count++; 360104e2ed7Sperrin return; 361104e2ed7Sperrin } 362*79315247SMatthew Ahrens if (off + len < next->lr_offset + next->lr_length) { 363104e2ed7Sperrin /* new range ends in the middle of this block */ 364*79315247SMatthew Ahrens next = rangelock_split(tree, next, off + len); 365*79315247SMatthew Ahrens next->lr_count++; 366104e2ed7Sperrin return; 367104e2ed7Sperrin } 368*79315247SMatthew Ahrens ASSERT3U(off + len, >, next->lr_offset + next->lr_length); 369*79315247SMatthew Ahrens next = rangelock_proxify(tree, next); 370*79315247SMatthew Ahrens next->lr_count++; 371104e2ed7Sperrin } 372104e2ed7Sperrin 373104e2ed7Sperrin /* Add the remaining end range. */ 374*79315247SMatthew Ahrens rangelock_new_proxy(tree, prev->lr_offset + prev->lr_length, 375*79315247SMatthew Ahrens (off + len) - (prev->lr_offset + prev->lr_length)); 376104e2ed7Sperrin } 377104e2ed7Sperrin 378104e2ed7Sperrin /* 379104e2ed7Sperrin * Check if a reader lock can be grabbed, or wait and recheck until available. 380104e2ed7Sperrin */ 381104e2ed7Sperrin static void 382*79315247SMatthew Ahrens rangelock_enter_reader(rangelock_t *rl, locked_range_t *new) 383104e2ed7Sperrin { 384*79315247SMatthew Ahrens avl_tree_t *tree = &rl->rl_tree; 385*79315247SMatthew Ahrens locked_range_t *prev, *next; 386104e2ed7Sperrin avl_index_t where; 387*79315247SMatthew Ahrens uint64_t off = new->lr_offset; 388*79315247SMatthew Ahrens uint64_t len = new->lr_length; 389104e2ed7Sperrin 390104e2ed7Sperrin /* 391104e2ed7Sperrin * Look for any writer locks in the range. 392104e2ed7Sperrin */ 393104e2ed7Sperrin retry: 394104e2ed7Sperrin prev = avl_find(tree, new, &where); 395104e2ed7Sperrin if (prev == NULL) 396*79315247SMatthew Ahrens prev = (locked_range_t *)avl_nearest(tree, where, AVL_BEFORE); 397104e2ed7Sperrin 398104e2ed7Sperrin /* 399104e2ed7Sperrin * Check the previous range for a writer lock overlap. 400104e2ed7Sperrin */ 401*79315247SMatthew Ahrens if (prev && (off < prev->lr_offset + prev->lr_length)) { 402*79315247SMatthew Ahrens if ((prev->lr_type == RL_WRITER) || (prev->lr_write_wanted)) { 403*79315247SMatthew Ahrens if (!prev->lr_read_wanted) { 404*79315247SMatthew Ahrens cv_init(&prev->lr_read_cv, 405*79315247SMatthew Ahrens NULL, CV_DEFAULT, NULL); 406*79315247SMatthew Ahrens prev->lr_read_wanted = B_TRUE; 407104e2ed7Sperrin } 408*79315247SMatthew Ahrens cv_wait(&prev->lr_read_cv, &rl->rl_lock); 409104e2ed7Sperrin goto retry; 410104e2ed7Sperrin } 411*79315247SMatthew Ahrens if (off + len < prev->lr_offset + prev->lr_length) 412104e2ed7Sperrin goto got_lock; 413104e2ed7Sperrin } 414104e2ed7Sperrin 415104e2ed7Sperrin /* 416104e2ed7Sperrin * Search through the following ranges to see if there's 417104e2ed7Sperrin * write lock any overlap. 418104e2ed7Sperrin */ 419*79315247SMatthew Ahrens if (prev != NULL) 420104e2ed7Sperrin next = AVL_NEXT(tree, prev); 421104e2ed7Sperrin else 422*79315247SMatthew Ahrens next = (locked_range_t *)avl_nearest(tree, where, AVL_AFTER); 423*79315247SMatthew Ahrens for (; next != NULL; next = AVL_NEXT(tree, next)) { 424*79315247SMatthew Ahrens if (off + len <= next->lr_offset) 425104e2ed7Sperrin goto got_lock; 426*79315247SMatthew Ahrens if ((next->lr_type == RL_WRITER) || (next->lr_write_wanted)) { 427*79315247SMatthew Ahrens if (!next->lr_read_wanted) { 428*79315247SMatthew Ahrens cv_init(&next->lr_read_cv, 429*79315247SMatthew Ahrens NULL, CV_DEFAULT, NULL); 430*79315247SMatthew Ahrens next->lr_read_wanted = B_TRUE; 431104e2ed7Sperrin } 432*79315247SMatthew Ahrens cv_wait(&next->lr_read_cv, &rl->rl_lock); 433104e2ed7Sperrin goto retry; 434104e2ed7Sperrin } 435*79315247SMatthew Ahrens if (off + len <= next->lr_offset + next->lr_length) 436104e2ed7Sperrin goto got_lock; 437104e2ed7Sperrin } 438104e2ed7Sperrin 439104e2ed7Sperrin got_lock: 440104e2ed7Sperrin /* 441104e2ed7Sperrin * Add the read lock, which may involve splitting existing 442*79315247SMatthew Ahrens * locks and bumping ref counts (r_count). 443104e2ed7Sperrin */ 444*79315247SMatthew Ahrens rangelock_add_reader(tree, new, prev, where); 445104e2ed7Sperrin } 446104e2ed7Sperrin 447104e2ed7Sperrin /* 448*79315247SMatthew Ahrens * Lock a range (offset, length) as either shared (RL_READER) or exclusive 449*79315247SMatthew Ahrens * (RL_WRITER or RL_APPEND). If RL_APPEND is specified, rl_cb() will convert 450*79315247SMatthew Ahrens * it to a RL_WRITER lock (with the offset at the end of the file). Returns 451*79315247SMatthew Ahrens * the range lock structure for later unlocking (or reduce range if the 452*79315247SMatthew Ahrens * entire file is locked as RL_WRITER). 453104e2ed7Sperrin */ 454*79315247SMatthew Ahrens locked_range_t * 455*79315247SMatthew Ahrens rangelock_enter(rangelock_t *rl, uint64_t off, uint64_t len, 456*79315247SMatthew Ahrens rangelock_type_t type) 457104e2ed7Sperrin { 458104e2ed7Sperrin ASSERT(type == RL_READER || type == RL_WRITER || type == RL_APPEND); 459104e2ed7Sperrin 460*79315247SMatthew Ahrens locked_range_t *new = kmem_alloc(sizeof (locked_range_t), KM_SLEEP); 461*79315247SMatthew Ahrens new->lr_rangelock = rl; 462*79315247SMatthew Ahrens new->lr_offset = off; 463ac05c741SMark Maybee if (len + off < off) /* overflow */ 464ac05c741SMark Maybee len = UINT64_MAX - off; 465*79315247SMatthew Ahrens new->lr_length = len; 466*79315247SMatthew Ahrens new->lr_count = 1; /* assume it's going to be in the tree */ 467*79315247SMatthew Ahrens new->lr_type = type; 468*79315247SMatthew Ahrens new->lr_proxy = B_FALSE; 469*79315247SMatthew Ahrens new->lr_write_wanted = B_FALSE; 470*79315247SMatthew Ahrens new->lr_read_wanted = B_FALSE; 471*79315247SMatthew Ahrens 472*79315247SMatthew Ahrens mutex_enter(&rl->rl_lock); 473104e2ed7Sperrin if (type == RL_READER) { 474104e2ed7Sperrin /* 475104e2ed7Sperrin * First check for the usual case of no locks 476104e2ed7Sperrin */ 477*79315247SMatthew Ahrens if (avl_numnodes(&rl->rl_tree) == 0) 478*79315247SMatthew Ahrens avl_add(&rl->rl_tree, new); 479104e2ed7Sperrin else 480*79315247SMatthew Ahrens rangelock_enter_reader(rl, new); 481104e2ed7Sperrin } else 482*79315247SMatthew Ahrens rangelock_enter_writer(rl, new); /* RL_WRITER or RL_APPEND */ 483*79315247SMatthew Ahrens mutex_exit(&rl->rl_lock); 484104e2ed7Sperrin return (new); 485104e2ed7Sperrin } 486104e2ed7Sperrin 487104e2ed7Sperrin /* 488104e2ed7Sperrin * Unlock a reader lock 489104e2ed7Sperrin */ 490104e2ed7Sperrin static void 491*79315247SMatthew Ahrens rangelock_exit_reader(rangelock_t *rl, locked_range_t *remove) 492104e2ed7Sperrin { 493*79315247SMatthew Ahrens avl_tree_t *tree = &rl->rl_tree; 494104e2ed7Sperrin uint64_t len; 495104e2ed7Sperrin 496104e2ed7Sperrin /* 497104e2ed7Sperrin * The common case is when the remove entry is in the tree 498104e2ed7Sperrin * (cnt == 1) meaning there's been no other reader locks overlapping 499104e2ed7Sperrin * with this one. Otherwise the remove entry will have been 500104e2ed7Sperrin * removed from the tree and replaced by proxies (one or 501104e2ed7Sperrin * more ranges mapping to the entire range). 502104e2ed7Sperrin */ 503*79315247SMatthew Ahrens if (remove->lr_count == 1) { 504104e2ed7Sperrin avl_remove(tree, remove); 505*79315247SMatthew Ahrens if (remove->lr_write_wanted) { 506*79315247SMatthew Ahrens cv_broadcast(&remove->lr_write_cv); 507*79315247SMatthew Ahrens cv_destroy(&remove->lr_write_cv); 508c25056deSgw } 509*79315247SMatthew Ahrens if (remove->lr_read_wanted) { 510*79315247SMatthew Ahrens cv_broadcast(&remove->lr_read_cv); 511*79315247SMatthew Ahrens cv_destroy(&remove->lr_read_cv); 512c25056deSgw } 513104e2ed7Sperrin } else { 514*79315247SMatthew Ahrens ASSERT0(remove->lr_count); 515*79315247SMatthew Ahrens ASSERT0(remove->lr_write_wanted); 516*79315247SMatthew Ahrens ASSERT0(remove->lr_read_wanted); 517104e2ed7Sperrin /* 518104e2ed7Sperrin * Find start proxy representing this reader lock, 519104e2ed7Sperrin * then decrement ref count on all proxies 520104e2ed7Sperrin * that make up this range, freeing them as needed. 521104e2ed7Sperrin */ 522*79315247SMatthew Ahrens locked_range_t *lr = avl_find(tree, remove, NULL); 523*79315247SMatthew Ahrens ASSERT3P(lr, !=, NULL); 524*79315247SMatthew Ahrens ASSERT3U(lr->lr_count, !=, 0); 525*79315247SMatthew Ahrens ASSERT3U(lr->lr_type, ==, RL_READER); 526*79315247SMatthew Ahrens locked_range_t *next = NULL; 527*79315247SMatthew Ahrens for (len = remove->lr_length; len != 0; lr = next) { 528*79315247SMatthew Ahrens len -= lr->lr_length; 529*79315247SMatthew Ahrens if (len != 0) { 530*79315247SMatthew Ahrens next = AVL_NEXT(tree, lr); 531*79315247SMatthew Ahrens ASSERT3P(next, !=, NULL); 532*79315247SMatthew Ahrens ASSERT3U(lr->lr_offset + lr->lr_length, ==, 533*79315247SMatthew Ahrens next->lr_offset); 534*79315247SMatthew Ahrens ASSERT3U(next->lr_count, !=, 0); 535*79315247SMatthew Ahrens ASSERT3U(next->lr_type, ==, RL_READER); 536104e2ed7Sperrin } 537*79315247SMatthew Ahrens lr->lr_count--; 538*79315247SMatthew Ahrens if (lr->lr_count == 0) { 539*79315247SMatthew Ahrens avl_remove(tree, lr); 540*79315247SMatthew Ahrens if (lr->lr_write_wanted) { 541*79315247SMatthew Ahrens cv_broadcast(&lr->lr_write_cv); 542*79315247SMatthew Ahrens cv_destroy(&lr->lr_write_cv); 543c25056deSgw } 544*79315247SMatthew Ahrens if (lr->lr_read_wanted) { 545*79315247SMatthew Ahrens cv_broadcast(&lr->lr_read_cv); 546*79315247SMatthew Ahrens cv_destroy(&lr->lr_read_cv); 547c25056deSgw } 548*79315247SMatthew Ahrens kmem_free(lr, sizeof (locked_range_t)); 549104e2ed7Sperrin } 550104e2ed7Sperrin } 551104e2ed7Sperrin } 552*79315247SMatthew Ahrens kmem_free(remove, sizeof (locked_range_t)); 553104e2ed7Sperrin } 554104e2ed7Sperrin 555104e2ed7Sperrin /* 556104e2ed7Sperrin * Unlock range and destroy range lock structure. 557104e2ed7Sperrin */ 558104e2ed7Sperrin void 559*79315247SMatthew Ahrens rangelock_exit(locked_range_t *lr) 560104e2ed7Sperrin { 561*79315247SMatthew Ahrens rangelock_t *rl = lr->lr_rangelock; 562c5c6ffa0Smaybee 563*79315247SMatthew Ahrens ASSERT(lr->lr_type == RL_WRITER || lr->lr_type == RL_READER); 564*79315247SMatthew Ahrens ASSERT(lr->lr_count == 1 || lr->lr_count == 0); 565*79315247SMatthew Ahrens ASSERT(!lr->lr_proxy); 566104e2ed7Sperrin 567*79315247SMatthew Ahrens mutex_enter(&rl->rl_lock); 568*79315247SMatthew Ahrens if (lr->lr_type == RL_WRITER) { 569104e2ed7Sperrin /* writer locks can't be shared or split */ 570*79315247SMatthew Ahrens avl_remove(&rl->rl_tree, lr); 571*79315247SMatthew Ahrens mutex_exit(&rl->rl_lock); 572*79315247SMatthew Ahrens if (lr->lr_write_wanted) { 573*79315247SMatthew Ahrens cv_broadcast(&lr->lr_write_cv); 574*79315247SMatthew Ahrens cv_destroy(&lr->lr_write_cv); 575c25056deSgw } 576*79315247SMatthew Ahrens if (lr->lr_read_wanted) { 577*79315247SMatthew Ahrens cv_broadcast(&lr->lr_read_cv); 578*79315247SMatthew Ahrens cv_destroy(&lr->lr_read_cv); 579c25056deSgw } 580*79315247SMatthew Ahrens kmem_free(lr, sizeof (locked_range_t)); 581104e2ed7Sperrin } else { 582104e2ed7Sperrin /* 583*79315247SMatthew Ahrens * lock may be shared, let rangelock_exit_reader() 584104e2ed7Sperrin * release the lock and free the rl_t 585104e2ed7Sperrin */ 586*79315247SMatthew Ahrens rangelock_exit_reader(rl, lr); 587*79315247SMatthew Ahrens mutex_exit(&rl->rl_lock); 588104e2ed7Sperrin } 589104e2ed7Sperrin } 590104e2ed7Sperrin 591104e2ed7Sperrin /* 592104e2ed7Sperrin * Reduce range locked as RL_WRITER from whole file to specified range. 593*79315247SMatthew Ahrens * Asserts the whole file is exclusively locked and so there's only one 594104e2ed7Sperrin * entry in the tree. 595104e2ed7Sperrin */ 596104e2ed7Sperrin void 597*79315247SMatthew Ahrens rangelock_reduce(locked_range_t *lr, uint64_t off, uint64_t len) 598104e2ed7Sperrin { 599*79315247SMatthew Ahrens rangelock_t *rl = lr->lr_rangelock; 600c5c6ffa0Smaybee 601104e2ed7Sperrin /* Ensure there are no other locks */ 602*79315247SMatthew Ahrens ASSERT3U(avl_numnodes(&rl->rl_tree), ==, 1); 603*79315247SMatthew Ahrens ASSERT3U(lr->lr_offset, ==, 0); 604*79315247SMatthew Ahrens ASSERT3U(lr->lr_type, ==, RL_WRITER); 605*79315247SMatthew Ahrens ASSERT(!lr->lr_proxy); 606*79315247SMatthew Ahrens ASSERT3U(lr->lr_length, ==, UINT64_MAX); 607*79315247SMatthew Ahrens ASSERT3U(lr->lr_count, ==, 1); 608*79315247SMatthew Ahrens 609*79315247SMatthew Ahrens mutex_enter(&rl->rl_lock); 610*79315247SMatthew Ahrens lr->lr_offset = off; 611*79315247SMatthew Ahrens lr->lr_length = len; 612*79315247SMatthew Ahrens mutex_exit(&rl->rl_lock); 613*79315247SMatthew Ahrens if (lr->lr_write_wanted) 614*79315247SMatthew Ahrens cv_broadcast(&lr->lr_write_cv); 615*79315247SMatthew Ahrens if (lr->lr_read_wanted) 616*79315247SMatthew Ahrens cv_broadcast(&lr->lr_read_cv); 617104e2ed7Sperrin } 618