1 /* 2 * Copyright (c) 1982, 1986, 1989 Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Scooter Morris at Genentech Inc. 7 * 8 * %sccs.include.redist.c% 9 * 10 * @(#)ufs_lockf.c 7.1 (Berkeley) 02/01/91 11 */ 12 13 #include "param.h" 14 #include "systm.h" 15 #include "user.h" 16 #include "kernel.h" 17 #include "file.h" 18 #include "proc.h" 19 #include "socketvar.h" 20 #include "socket.h" 21 #include "vnode.h" 22 #include "ioctl.h" 23 #include "tty.h" 24 #include "malloc.h" 25 #include "fcntl.h" 26 #include "../ufs/lockf.h" 27 #include "../ufs/quota.h" 28 #include "../ufs/inode.h" 29 30 #ifdef LOCKF_DEBUG 31 int lockf_debug = 0; 32 #endif /* LOCKF_DEBUG */ 33 34 /* 35 * Common code for ufs byte range locking 36 */ 37 38 /* 39 * Add a lock to the list. Upgrade or downgrade our locks, if 40 * they conflict. 41 */ 42 struct lockf * 43 lf_addlock(lock) 44 register struct lockf *lock; 45 { 46 register struct lockf *lf = lock->lf_inode->i_lockf; 47 struct lockf *lastlock = (struct lockf *)0; 48 struct lockf *prev, *overlap, *ltmp; 49 int ovcase; 50 51 /* 52 * First, see if we overlap with anything. 53 */ 54 ovcase = lf_findoverlap(lf, lock, &prev, &overlap); 55 /* 56 * Add the new lock 57 */ 58 if (prev != (struct lockf *)0) 59 prev->lf_next = lock; 60 else 61 lock->lf_inode->i_lockf = lock; 62 lock->lf_next = overlap; 63 /* 64 * Skip over locks owned by other processes. 65 * Merge any locks that are owned by ourselves. 66 */ 67 for (;;) { 68 for (;;) { 69 /* 70 * If no overlap, we are done. 71 */ 72 if (ovcase == 0) 73 return; 74 lf = overlap->lf_next; 75 if (overlap->lf_id == lock->lf_id) 76 break; 77 /* 78 * We overlap with another process. 79 * If it is a block, panic. 80 */ 81 if (lock->lf_type == F_WRLCK || 82 overlap->lf_type == F_WRLCK) 83 panic("blocked in addlock"); 84 ovcase = lf_findoverlap(lf, lock, &prev, &overlap); 85 } 86 /* 87 * Five cases: 88 * 1) overlap == lock 89 * 2) overlap contains lock 90 * 3) lock contains overlap 91 * 4) overlap starts before lock 92 * 5) overlap ends after lock 93 */ 94 switch (ovcase) { 95 96 case 1: /* overlap == lock */ 97 /* 98 * Undo spurious addition of lock to list. 99 */ 100 if (prev != (struct lockf *)0) 101 prev->lf_next = overlap; 102 else 103 lock->lf_inode->i_lockf = overlap; 104 /* 105 * If downgrading lock, others may be 106 * able to acquire it. 107 */ 108 if (lock->lf_type == F_RDLCK && 109 overlap->lf_type == F_WRLCK) 110 lf_wakelock(overlap); 111 overlap->lf_type = lock->lf_type; 112 free(lock, M_LOCKF); 113 return; 114 115 case 2: /* overlap contains lock */ 116 /* 117 * Undo spurious addition of lock to list. 118 */ 119 if (prev != (struct lockf *)0) 120 prev->lf_next = overlap; 121 else 122 lock->lf_inode->i_lockf = overlap; 123 if (overlap->lf_type == lock->lf_type) { 124 free(lock, M_LOCKF); 125 return; 126 } 127 lf_split(overlap, lock); 128 lf_wakelock(overlap); 129 return; 130 131 case 3: /* lock contains overlap */ 132 /* 133 * If downgrading lock, others may be able to 134 * acquire it, otherwise take the list. 135 */ 136 if (lock->lf_type == F_RDLCK && 137 overlap->lf_type == F_WRLCK) { 138 lf_wakelock(overlap); 139 } else { 140 ltmp = lock->lf_block; 141 lock->lf_block = overlap->lf_block; 142 lf_addblock(lock, ltmp); 143 } 144 /* 145 * Delete the overlap. 146 */ 147 lock->lf_next = overlap->lf_next; 148 free(overlap, M_LOCKF); 149 break; 150 151 case 4: /* overlap starts before lock */ 152 /* 153 * Reverse lock and overlap on the list 154 */ 155 if (prev != (struct lockf *)0) 156 prev->lf_next = overlap; 157 else 158 lock->lf_inode->i_lockf = overlap; 159 lock->lf_next = overlap->lf_next; 160 overlap->lf_next = lock; 161 overlap->lf_end = lock->lf_start - 1; 162 lf_wakelock(overlap); 163 break; 164 165 case 5: /* overlap ends after lock */ 166 overlap->lf_start = lock->lf_end + 1; 167 lf_wakelock(overlap); 168 return; 169 } 170 ovcase = lf_findoverlap(lf, lock, &prev, &overlap); 171 } 172 /* NOTREACHED */ 173 } 174 175 /* 176 * Walk the list of locks for an inode and 177 * return the first blocking lock. 178 */ 179 struct lockf * 180 lf_getblock(lock) 181 register struct lockf *lock; 182 { 183 struct lockf *prev, *overlap, *lf = lock->lf_inode->i_lockf; 184 int ovcase; 185 186 while (ovcase = lf_findoverlap(lf, lock, &prev, &overlap)) { 187 /* 188 * We've found an overlap, see if it blocks us 189 */ 190 if ((lock->lf_type == F_WRLCK || overlap->lf_type == F_WRLCK) && 191 overlap->lf_id != lock->lf_id) 192 return (overlap); 193 /* 194 * Nope, point to the next one on the list and 195 * see if it blocks us 196 */ 197 lf = overlap->lf_next; 198 } 199 return ((struct lockf *)0); 200 } 201 202 /* 203 * Walk the list of locks for an inode to 204 * find an overlapping lock (if any). 205 * 206 * NOTE: this returns only the FIRST overlapping lock. There 207 * may be more than one. 208 */ 209 lf_findoverlap(list, lock, prev, overlap) 210 struct lockf *list; 211 struct lockf *lock; 212 struct lockf **prev; 213 struct lockf **overlap; 214 { 215 register struct lockf *lf = list; 216 off_t start, end; 217 218 *prev = (struct lockf *) 0; 219 *overlap = lf; 220 if ((lock == (struct lockf *)0) || (lf == (struct lockf *)0)) 221 return (0); 222 #ifdef LOCKF_DEBUG 223 if (lockf_debug & 1) 224 lf_print("lf_findoverlap: looking for overlap in", lock); 225 #endif /* LOCKF_DEBUG */ 226 start = lock->lf_start; 227 end = lock->lf_end; 228 while (lf != (struct lockf *)0) { 229 #ifdef LOCKF_DEBUG 230 if (lockf_debug & 1) 231 lf_print("\tchecking", lf); 232 #endif /* LOCKF_DEBUG */ 233 /* 234 * Have we gone far enough? 235 */ 236 if (end != -1 && lf->lf_start > end) 237 #ifdef LOCKF_DEBUG 238 if (lockf_debug & 1) 239 print("no overlap\n"); 240 #endif /* LOCKF_DEBUG */ 241 return (0); 242 /* 243 * OK, find the overlap 244 * 245 * Five cases: 246 * 1) overlap == lock 247 * 2) overlap contains lock 248 * 3) lock contains overlap 249 * 4) overlap starts before lock 250 * 5) overlap ends after lock 251 */ 252 if ((lf->lf_start == start) && (lf->lf_end == end)) { 253 /* Case 1 */ 254 #ifdef LOCKF_DEBUG 255 if (lockf_debug & 1) 256 printf("overlap == lock\n"); break; 257 #endif /* LOCKF_DEBUG */ 258 return (1); 259 } else if ((lf->lf_start <= start) && 260 (end != -1) && 261 ((lf->lf_end >= end) || (lf->lf_end == -1))) { 262 /* Case 2 */ 263 #ifdef LOCKF_DEBUG 264 if (lockf_debug & 1) 265 printf("overlap contains lock\n"); break; 266 #endif /* LOCKF_DEBUG */ 267 return (2); 268 } else if ((start <= lf->lf_start) && 269 (lf->lf_end != -1) && 270 ((end == -1) || (end >= lf->lf_end))) { 271 /* Case 3 */ 272 #ifdef LOCKF_DEBUG 273 if (lockf_debug & 1) 274 printf("lock contains overlap\n"); break; 275 #endif /* LOCKF_DEBUG */ 276 return (3); 277 } else if ((lf->lf_start < start) && 278 ((lf->lf_end >= start) || (lf->lf_end == -1))) { 279 /* Case 4 */ 280 #ifdef LOCKF_DEBUG 281 if (lockf_debug & 1) 282 printf("overlap starts before lock\n"); break; 283 #endif /* LOCKF_DEBUG */ 284 return (4); 285 } else if ((lf->lf_start > start) && 286 (end != -1) && 287 ((lf->lf_end > end) || (lf->lf_end == -1))) { 288 /* Case 5 */ 289 #ifdef LOCKF_DEBUG 290 if (lockf_debug & 1) 291 printf("overlap ends after lock\n"); break; 292 #endif /* LOCKF_DEBUG */ 293 return (5); 294 } 295 *prev = lf; 296 *overlap = lf = lf->lf_next; 297 } 298 /* No overlap */ 299 #ifdef LOCKF_DEBUG 300 if (lockf_debug & 1) 301 print("no overlap\n"); 302 #endif /* LOCKF_DEBUG */ 303 return (0); 304 } 305 306 /* 307 * Add a lock to the end of the blocked list. 308 */ 309 lf_addblock(lock, blocked) 310 struct lockf *lock; 311 struct lockf *blocked; 312 { 313 register struct lockf *lf; 314 315 if (lock == (struct lockf *)0) 316 return; 317 if ((lf = lock->lf_block) == (struct lockf *)0) { 318 lock->lf_block = blocked; 319 return; 320 } 321 while (lf->lf_block != (struct lockf *)0) 322 lf = lf->lf_block; 323 lf->lf_block = blocked; 324 return; 325 } 326 327 /* 328 * Combine two locks into a single lock 329 */ 330 lf_combine(lock1, lock2) 331 struct lockf *lock1; 332 struct lockf *lock2; 333 { 334 #ifdef LOCKF_DEBUG 335 if (lockf_debug & 1) { 336 lf_print("lf_combine", lock1); 337 lf_print("combining with", lock2); 338 } 339 #endif /* LOCKF_DEBUG */ 340 /* 341 * Sanity check 342 */ 343 if ( (lock1->lf_id != lock2->lf_id) || 344 (lock1->lf_type != lock2->lf_type) ) 345 panic("lf_combine"); 346 if (lock1->lf_start > lock2->lf_start) 347 lock1->lf_start = lock2->lf_start; 348 if ((lock1->lf_end == -1) || (lock2->lf_end == -1)) 349 lock1->lf_end == -1; 350 else if (lock1->lf_end < lock2->lf_end) 351 lock1->lf_end = lock2->lf_end; 352 /* Add the block lists together */ 353 lf_addblock(lock1, lock2->lf_block); 354 free(lock2, M_LOCKF); 355 } 356 357 /* 358 * Split a lock and a contained region into 359 * three locks 360 */ 361 lf_split(lock1, lock2) 362 register struct lockf *lock1; 363 register struct lockf *lock2; 364 { 365 register struct lockf *splitlock; 366 367 #ifdef LOCKF_DEBUG 368 if (lockf_debug & 1) { 369 lf_print("lf_split", lock1); 370 lf_print("splitting from", lock2); 371 } 372 #endif /* LOCKF_DEBUG */ 373 /* 374 * Make a new lock consisting of the last part of 375 * the encompassing lock 376 */ 377 MALLOC(splitlock, struct lockf *, sizeof *splitlock, M_LOCKF, M_WAITOK); 378 bcopy((caddr_t)lock1, (caddr_t)splitlock, sizeof *splitlock); 379 splitlock->lf_end = lock2->lf_end + 1; 380 lock1->lf_end = lock2->lf_start - 1; 381 /* 382 * OK, now link it in 383 */ 384 splitlock->lf_next = lock1->lf_next; 385 lock2->lf_next = splitlock; 386 lock1->lf_next = lock2; 387 } 388 389 /* 390 * lf_remove: remove a lock (or a portion of a lock) from the lock list 391 */ 392 struct lockf * 393 lf_remove(lfun) 394 register struct lockf *lfun; 395 { 396 struct inode *ip = lfun->lf_inode; 397 register struct lockf *lf = ip->i_lockf; 398 struct lockf *blocklist = (struct lockf *)0; 399 struct lockf *overlap, *prev; 400 int ovcase; 401 402 if (lf == (struct lockf *)0) 403 return((struct lockf *)0); 404 #ifdef LOCKF_DEBUG 405 if (lockf_debug & 1) 406 printf("lf_remove", lfun); 407 #endif LOCKF_DEBUG 408 while (ovcase = lf_findoverlap(lf, lfun, &prev, &overlap)) { 409 /* 410 * Point to the next element for the loop 411 */ 412 lf = overlap->lf_next; 413 /* 414 * Check to see if it is our lock. 415 */ 416 if (lfun->lf_id == overlap->lf_id) { 417 /* 418 * Save the list of locks to be retried. 419 */ 420 if (blocklist == (struct lockf *)0) 421 blocklist = overlap->lf_block; 422 else 423 lf_addblock(blocklist, overlap->lf_block); 424 425 switch (ovcase) { 426 427 case 1: /* overlap == lock */ 428 if (prev != (struct lockf *)0) 429 prev->lf_next = overlap->lf_next; 430 else 431 ip->i_lockf = overlap->lf_next; 432 free(overlap, M_LOCKF); 433 return (blocklist); 434 435 case 2: /* overlap contains lock: split it */ 436 lf_split(overlap, lfun); 437 overlap->lf_next = lfun->lf_next; 438 return (blocklist); 439 440 case 3: /* lock contains overlap */ 441 if (prev != (struct lockf *)0) 442 prev->lf_next = overlap->lf_next; 443 else 444 ip->i_lockf = overlap->lf_next; 445 free(overlap, M_LOCKF); 446 break; 447 448 case 4: /* overlap starts before lock */ 449 overlap->lf_end = lfun->lf_start - 1; 450 break; 451 452 case 5: /* overlap ends after lock */ 453 overlap->lf_start = lfun->lf_end + 1; 454 return (blocklist); 455 } 456 } 457 } 458 return (blocklist); 459 } 460 461 /* 462 * Wakeup a blocklist 463 */ 464 lf_wakelock(blocklist) 465 register struct lockf *blocklist; 466 { 467 register struct lockf *wakelock; 468 469 while (blocklist != (struct lockf *)0) { 470 wakelock = blocklist; 471 blocklist = blocklist->lf_block; 472 wakelock->lf_block = (struct lockf *)0; 473 wakelock->lf_next = (struct lockf *)0; 474 #ifdef LOCKF_DEBUG 475 if (lockf_debug & 4) 476 lf_print("ufs_wakelock: awakening", wakelock); 477 #endif /* LOCKF_DEBUG */ 478 wakeup((caddr_t)wakelock); 479 } 480 } 481 482 #ifdef LOCKF_DEBUG 483 /* 484 * Print out a lock. 485 */ 486 lf_print(tag, lock) 487 char *tag; 488 register lockf *lock; 489 { 490 491 printf("%s: lock 0x%X for proc %d in ino %d on dev <%d, %d>, ", 492 tag, lock, lock->lp_proc->p_pid, lock->lf_inode->i_number, 493 major(lock->lf_inode->i_dev), minor(lock->lf_inode->i_dev)); 494 printf("type %s, start %d, end %d\n", 495 lock->lf_type == F_RDLCK ? "shared" : 496 lock->lf_type == F_WRLCK ? "exclusive" : 497 "unknown", start, end); 498 } 499 #endif /* LOCKF_DEBUG */ 500