1 /* 2 * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved. 3 * 4 * This program is free software; you can redistribute it and/or modify it 5 * under the terms of version 2 of the GNU General Public License as 6 * published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it would be useful, but 9 * WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 11 * 12 * Further, this software is distributed without any warranty that it is 13 * free of the rightful claim of any third person regarding infringement 14 * or the like. Any license provided herein, whether implied or 15 * otherwise, applies only to this software file. Patent licenses, if 16 * any, provided herein do not apply to combinations of this program with 17 * other software, or any other product whatsoever. 18 * 19 * You should have received a copy of the GNU General Public License along 20 * with this program; if not, write the Free Software Foundation, Inc., 59 21 * Temple Place - Suite 330, Boston MA 02111-1307, USA. 22 * 23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy, 24 * Mountain View, CA 94043, or: 25 * 26 * http://www.sgi.com 27 * 28 * For further information regarding this notice, see: 29 * 30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/ 31 */ 32 33 #include "xfs.h" 34 #include "xfs_macros.h" 35 #include "xfs_types.h" 36 #include "xfs_inum.h" 37 #include "xfs_log.h" 38 #include "xfs_trans.h" 39 #include "xfs_sb.h" 40 #include "xfs_dir.h" 41 #include "xfs_dmapi.h" 42 #include "xfs_mount.h" 43 #include "xfs_trans_priv.h" 44 #include "xfs_error.h" 45 46 STATIC void xfs_ail_insert(xfs_ail_entry_t *, xfs_log_item_t *); 47 STATIC xfs_log_item_t * xfs_ail_delete(xfs_ail_entry_t *, xfs_log_item_t *); 48 STATIC xfs_log_item_t * xfs_ail_min(xfs_ail_entry_t *); 49 STATIC xfs_log_item_t * xfs_ail_next(xfs_ail_entry_t *, xfs_log_item_t *); 50 51 #ifdef DEBUG 52 STATIC void xfs_ail_check(xfs_ail_entry_t *); 53 #else 54 #define xfs_ail_check(a) 55 #endif /* DEBUG */ 56 57 58 /* 59 * This is called by the log manager code to determine the LSN 60 * of the tail of the log. This is exactly the LSN of the first 61 * item in the AIL. If the AIL is empty, then this function 62 * returns 0. 63 * 64 * We need the AIL lock in order to get a coherent read of the 65 * lsn of the last item in the AIL. 66 */ 67 xfs_lsn_t 68 xfs_trans_tail_ail( 69 xfs_mount_t *mp) 70 { 71 xfs_lsn_t lsn; 72 xfs_log_item_t *lip; 73 SPLDECL(s); 74 75 AIL_LOCK(mp,s); 76 lip = xfs_ail_min(&(mp->m_ail)); 77 if (lip == NULL) { 78 lsn = (xfs_lsn_t)0; 79 } else { 80 lsn = lip->li_lsn; 81 } 82 AIL_UNLOCK(mp, s); 83 84 return lsn; 85 } 86 87 /* 88 * xfs_trans_push_ail 89 * 90 * This routine is called to move the tail of the AIL 91 * forward. It does this by trying to flush items in the AIL 92 * whose lsns are below the given threshold_lsn. 93 * 94 * The routine returns the lsn of the tail of the log. 95 */ 96 xfs_lsn_t 97 xfs_trans_push_ail( 98 xfs_mount_t *mp, 99 xfs_lsn_t threshold_lsn) 100 { 101 xfs_lsn_t lsn; 102 xfs_log_item_t *lip; 103 int gen; 104 int restarts; 105 int lock_result; 106 int flush_log; 107 SPLDECL(s); 108 109 #define XFS_TRANS_PUSH_AIL_RESTARTS 10 110 111 AIL_LOCK(mp,s); 112 lip = xfs_trans_first_ail(mp, &gen); 113 if (lip == NULL || XFS_FORCED_SHUTDOWN(mp)) { 114 /* 115 * Just return if the AIL is empty. 116 */ 117 AIL_UNLOCK(mp, s); 118 return (xfs_lsn_t)0; 119 } 120 121 XFS_STATS_INC(xs_push_ail); 122 123 /* 124 * While the item we are looking at is below the given threshold 125 * try to flush it out. Make sure to limit the number of times 126 * we allow xfs_trans_next_ail() to restart scanning from the 127 * beginning of the list. We'd like not to stop until we've at least 128 * tried to push on everything in the AIL with an LSN less than 129 * the given threshold. However, we may give up before that if 130 * we realize that we've been holding the AIL_LOCK for 'too long', 131 * blocking interrupts. Currently, too long is < 500us roughly. 132 */ 133 flush_log = 0; 134 restarts = 0; 135 while (((restarts < XFS_TRANS_PUSH_AIL_RESTARTS) && 136 (XFS_LSN_CMP(lip->li_lsn, threshold_lsn) < 0))) { 137 /* 138 * If we can lock the item without sleeping, unlock 139 * the AIL lock and flush the item. Then re-grab the 140 * AIL lock so we can look for the next item on the 141 * AIL. Since we unlock the AIL while we flush the 142 * item, the next routine may start over again at the 143 * the beginning of the list if anything has changed. 144 * That is what the generation count is for. 145 * 146 * If we can't lock the item, either its holder will flush 147 * it or it is already being flushed or it is being relogged. 148 * In any of these case it is being taken care of and we 149 * can just skip to the next item in the list. 150 */ 151 lock_result = IOP_TRYLOCK(lip); 152 switch (lock_result) { 153 case XFS_ITEM_SUCCESS: 154 AIL_UNLOCK(mp, s); 155 XFS_STATS_INC(xs_push_ail_success); 156 IOP_PUSH(lip); 157 AIL_LOCK(mp,s); 158 break; 159 160 case XFS_ITEM_PUSHBUF: 161 AIL_UNLOCK(mp, s); 162 XFS_STATS_INC(xs_push_ail_pushbuf); 163 #ifdef XFSRACEDEBUG 164 delay_for_intr(); 165 delay(300); 166 #endif 167 ASSERT(lip->li_ops->iop_pushbuf); 168 ASSERT(lip); 169 IOP_PUSHBUF(lip); 170 AIL_LOCK(mp,s); 171 break; 172 173 case XFS_ITEM_PINNED: 174 XFS_STATS_INC(xs_push_ail_pinned); 175 flush_log = 1; 176 break; 177 178 case XFS_ITEM_LOCKED: 179 XFS_STATS_INC(xs_push_ail_locked); 180 break; 181 182 case XFS_ITEM_FLUSHING: 183 XFS_STATS_INC(xs_push_ail_flushing); 184 break; 185 186 default: 187 ASSERT(0); 188 break; 189 } 190 191 lip = xfs_trans_next_ail(mp, lip, &gen, &restarts); 192 if (lip == NULL) { 193 break; 194 } 195 if (XFS_FORCED_SHUTDOWN(mp)) { 196 /* 197 * Just return if we shut down during the last try. 198 */ 199 AIL_UNLOCK(mp, s); 200 return (xfs_lsn_t)0; 201 } 202 203 } 204 205 if (flush_log) { 206 /* 207 * If something we need to push out was pinned, then 208 * push out the log so it will become unpinned and 209 * move forward in the AIL. 210 */ 211 AIL_UNLOCK(mp, s); 212 XFS_STATS_INC(xs_push_ail_flush); 213 xfs_log_force(mp, (xfs_lsn_t)0, XFS_LOG_FORCE); 214 AIL_LOCK(mp, s); 215 } 216 217 lip = xfs_ail_min(&(mp->m_ail)); 218 if (lip == NULL) { 219 lsn = (xfs_lsn_t)0; 220 } else { 221 lsn = lip->li_lsn; 222 } 223 224 AIL_UNLOCK(mp, s); 225 return lsn; 226 } /* xfs_trans_push_ail */ 227 228 229 /* 230 * This is to be called when an item is unlocked that may have 231 * been in the AIL. It will wake up the first member of the AIL 232 * wait list if this item's unlocking might allow it to progress. 233 * If the item is in the AIL, then we need to get the AIL lock 234 * while doing our checking so we don't race with someone going 235 * to sleep waiting for this event in xfs_trans_push_ail(). 236 */ 237 void 238 xfs_trans_unlocked_item( 239 xfs_mount_t *mp, 240 xfs_log_item_t *lip) 241 { 242 xfs_log_item_t *min_lip; 243 244 /* 245 * If we're forcibly shutting down, we may have 246 * unlocked log items arbitrarily. The last thing 247 * we want to do is to move the tail of the log 248 * over some potentially valid data. 249 */ 250 if (!(lip->li_flags & XFS_LI_IN_AIL) || 251 XFS_FORCED_SHUTDOWN(mp)) { 252 return; 253 } 254 255 /* 256 * This is the one case where we can call into xfs_ail_min() 257 * without holding the AIL lock because we only care about the 258 * case where we are at the tail of the AIL. If the object isn't 259 * at the tail, it doesn't matter what result we get back. This 260 * is slightly racy because since we were just unlocked, we could 261 * go to sleep between the call to xfs_ail_min and the call to 262 * xfs_log_move_tail, have someone else lock us, commit to us disk, 263 * move us out of the tail of the AIL, and then we wake up. However, 264 * the call to xfs_log_move_tail() doesn't do anything if there's 265 * not enough free space to wake people up so we're safe calling it. 266 */ 267 min_lip = xfs_ail_min(&mp->m_ail); 268 269 if (min_lip == lip) 270 xfs_log_move_tail(mp, 1); 271 } /* xfs_trans_unlocked_item */ 272 273 274 /* 275 * Update the position of the item in the AIL with the new 276 * lsn. If it is not yet in the AIL, add it. Otherwise, move 277 * it to its new position by removing it and re-adding it. 278 * 279 * Wakeup anyone with an lsn less than the item's lsn. If the item 280 * we move in the AIL is the minimum one, update the tail lsn in the 281 * log manager. 282 * 283 * Increment the AIL's generation count to indicate that the tree 284 * has changed. 285 * 286 * This function must be called with the AIL lock held. The lock 287 * is dropped before returning, so the caller must pass in the 288 * cookie returned by AIL_LOCK. 289 */ 290 void 291 xfs_trans_update_ail( 292 xfs_mount_t *mp, 293 xfs_log_item_t *lip, 294 xfs_lsn_t lsn, 295 unsigned long s) 296 { 297 xfs_ail_entry_t *ailp; 298 xfs_log_item_t *dlip=NULL; 299 xfs_log_item_t *mlip; /* ptr to minimum lip */ 300 301 ailp = &(mp->m_ail); 302 mlip = xfs_ail_min(ailp); 303 304 if (lip->li_flags & XFS_LI_IN_AIL) { 305 dlip = xfs_ail_delete(ailp, lip); 306 ASSERT(dlip == lip); 307 } else { 308 lip->li_flags |= XFS_LI_IN_AIL; 309 } 310 311 lip->li_lsn = lsn; 312 313 xfs_ail_insert(ailp, lip); 314 mp->m_ail_gen++; 315 316 if (mlip == dlip) { 317 mlip = xfs_ail_min(&(mp->m_ail)); 318 AIL_UNLOCK(mp, s); 319 xfs_log_move_tail(mp, mlip->li_lsn); 320 } else { 321 AIL_UNLOCK(mp, s); 322 } 323 324 325 } /* xfs_trans_update_ail */ 326 327 /* 328 * Delete the given item from the AIL. It must already be in 329 * the AIL. 330 * 331 * Wakeup anyone with an lsn less than item's lsn. If the item 332 * we delete in the AIL is the minimum one, update the tail lsn in the 333 * log manager. 334 * 335 * Clear the IN_AIL flag from the item, reset its lsn to 0, and 336 * bump the AIL's generation count to indicate that the tree 337 * has changed. 338 * 339 * This function must be called with the AIL lock held. The lock 340 * is dropped before returning, so the caller must pass in the 341 * cookie returned by AIL_LOCK. 342 */ 343 void 344 xfs_trans_delete_ail( 345 xfs_mount_t *mp, 346 xfs_log_item_t *lip, 347 unsigned long s) 348 { 349 xfs_ail_entry_t *ailp; 350 xfs_log_item_t *dlip; 351 xfs_log_item_t *mlip; 352 353 if (lip->li_flags & XFS_LI_IN_AIL) { 354 ailp = &(mp->m_ail); 355 mlip = xfs_ail_min(ailp); 356 dlip = xfs_ail_delete(ailp, lip); 357 ASSERT(dlip == lip); 358 359 360 lip->li_flags &= ~XFS_LI_IN_AIL; 361 lip->li_lsn = 0; 362 mp->m_ail_gen++; 363 364 if (mlip == dlip) { 365 mlip = xfs_ail_min(&(mp->m_ail)); 366 AIL_UNLOCK(mp, s); 367 xfs_log_move_tail(mp, (mlip ? mlip->li_lsn : 0)); 368 } else { 369 AIL_UNLOCK(mp, s); 370 } 371 } 372 else { 373 /* 374 * If the file system is not being shutdown, we are in 375 * serious trouble if we get to this stage. 376 */ 377 if (XFS_FORCED_SHUTDOWN(mp)) 378 AIL_UNLOCK(mp, s); 379 else { 380 xfs_cmn_err(XFS_PTAG_AILDELETE, CE_ALERT, mp, 381 "xfs_trans_delete_ail: attempting to delete a log item that is not in the AIL"); 382 xfs_force_shutdown(mp, XFS_CORRUPT_INCORE); 383 AIL_UNLOCK(mp, s); 384 } 385 } 386 } 387 388 389 390 /* 391 * Return the item in the AIL with the smallest lsn. 392 * Return the current tree generation number for use 393 * in calls to xfs_trans_next_ail(). 394 */ 395 xfs_log_item_t * 396 xfs_trans_first_ail( 397 xfs_mount_t *mp, 398 int *gen) 399 { 400 xfs_log_item_t *lip; 401 402 lip = xfs_ail_min(&(mp->m_ail)); 403 *gen = (int)mp->m_ail_gen; 404 405 return (lip); 406 } 407 408 /* 409 * If the generation count of the tree has not changed since the 410 * caller last took something from the AIL, then return the elmt 411 * in the tree which follows the one given. If the count has changed, 412 * then return the minimum elmt of the AIL and bump the restarts counter 413 * if one is given. 414 */ 415 xfs_log_item_t * 416 xfs_trans_next_ail( 417 xfs_mount_t *mp, 418 xfs_log_item_t *lip, 419 int *gen, 420 int *restarts) 421 { 422 xfs_log_item_t *nlip; 423 424 ASSERT(mp && lip && gen); 425 if (mp->m_ail_gen == *gen) { 426 nlip = xfs_ail_next(&(mp->m_ail), lip); 427 } else { 428 nlip = xfs_ail_min(&(mp->m_ail)); 429 *gen = (int)mp->m_ail_gen; 430 if (restarts != NULL) { 431 XFS_STATS_INC(xs_push_ail_restarts); 432 (*restarts)++; 433 } 434 } 435 436 return (nlip); 437 } 438 439 440 /* 441 * The active item list (AIL) is a doubly linked list of log 442 * items sorted by ascending lsn. The base of the list is 443 * a forw/back pointer pair embedded in the xfs mount structure. 444 * The base is initialized with both pointers pointing to the 445 * base. This case always needs to be distinguished, because 446 * the base has no lsn to look at. We almost always insert 447 * at the end of the list, so on inserts we search from the 448 * end of the list to find where the new item belongs. 449 */ 450 451 /* 452 * Initialize the doubly linked list to point only to itself. 453 */ 454 void 455 xfs_trans_ail_init( 456 xfs_mount_t *mp) 457 { 458 mp->m_ail.ail_forw = (xfs_log_item_t*)&(mp->m_ail); 459 mp->m_ail.ail_back = (xfs_log_item_t*)&(mp->m_ail); 460 } 461 462 /* 463 * Insert the given log item into the AIL. 464 * We almost always insert at the end of the list, so on inserts 465 * we search from the end of the list to find where the 466 * new item belongs. 467 */ 468 STATIC void 469 xfs_ail_insert( 470 xfs_ail_entry_t *base, 471 xfs_log_item_t *lip) 472 /* ARGSUSED */ 473 { 474 xfs_log_item_t *next_lip; 475 476 /* 477 * If the list is empty, just insert the item. 478 */ 479 if (base->ail_back == (xfs_log_item_t*)base) { 480 base->ail_forw = lip; 481 base->ail_back = lip; 482 lip->li_ail.ail_forw = (xfs_log_item_t*)base; 483 lip->li_ail.ail_back = (xfs_log_item_t*)base; 484 return; 485 } 486 487 next_lip = base->ail_back; 488 while ((next_lip != (xfs_log_item_t*)base) && 489 (XFS_LSN_CMP(next_lip->li_lsn, lip->li_lsn) > 0)) { 490 next_lip = next_lip->li_ail.ail_back; 491 } 492 ASSERT((next_lip == (xfs_log_item_t*)base) || 493 (XFS_LSN_CMP(next_lip->li_lsn, lip->li_lsn) <= 0)); 494 lip->li_ail.ail_forw = next_lip->li_ail.ail_forw; 495 lip->li_ail.ail_back = next_lip; 496 next_lip->li_ail.ail_forw = lip; 497 lip->li_ail.ail_forw->li_ail.ail_back = lip; 498 499 xfs_ail_check(base); 500 return; 501 } 502 503 /* 504 * Delete the given item from the AIL. Return a pointer to the item. 505 */ 506 /*ARGSUSED*/ 507 STATIC xfs_log_item_t * 508 xfs_ail_delete( 509 xfs_ail_entry_t *base, 510 xfs_log_item_t *lip) 511 /* ARGSUSED */ 512 { 513 lip->li_ail.ail_forw->li_ail.ail_back = lip->li_ail.ail_back; 514 lip->li_ail.ail_back->li_ail.ail_forw = lip->li_ail.ail_forw; 515 lip->li_ail.ail_forw = NULL; 516 lip->li_ail.ail_back = NULL; 517 518 xfs_ail_check(base); 519 return lip; 520 } 521 522 /* 523 * Return a pointer to the first item in the AIL. 524 * If the AIL is empty, then return NULL. 525 */ 526 STATIC xfs_log_item_t * 527 xfs_ail_min( 528 xfs_ail_entry_t *base) 529 /* ARGSUSED */ 530 { 531 register xfs_log_item_t *forw = base->ail_forw; 532 if (forw == (xfs_log_item_t*)base) { 533 return NULL; 534 } 535 return forw; 536 } 537 538 /* 539 * Return a pointer to the item which follows 540 * the given item in the AIL. If the given item 541 * is the last item in the list, then return NULL. 542 */ 543 STATIC xfs_log_item_t * 544 xfs_ail_next( 545 xfs_ail_entry_t *base, 546 xfs_log_item_t *lip) 547 /* ARGSUSED */ 548 { 549 if (lip->li_ail.ail_forw == (xfs_log_item_t*)base) { 550 return NULL; 551 } 552 return lip->li_ail.ail_forw; 553 554 } 555 556 #ifdef DEBUG 557 /* 558 * Check that the list is sorted as it should be. 559 */ 560 STATIC void 561 xfs_ail_check( 562 xfs_ail_entry_t *base) 563 { 564 xfs_log_item_t *lip; 565 xfs_log_item_t *prev_lip; 566 567 lip = base->ail_forw; 568 if (lip == (xfs_log_item_t*)base) { 569 /* 570 * Make sure the pointers are correct when the list 571 * is empty. 572 */ 573 ASSERT(base->ail_back == (xfs_log_item_t*)base); 574 return; 575 } 576 577 /* 578 * Walk the list checking forward and backward pointers, 579 * lsn ordering, and that every entry has the XFS_LI_IN_AIL 580 * flag set. 581 */ 582 prev_lip = (xfs_log_item_t*)base; 583 while (lip != (xfs_log_item_t*)base) { 584 if (prev_lip != (xfs_log_item_t*)base) { 585 ASSERT(prev_lip->li_ail.ail_forw == lip); 586 ASSERT(XFS_LSN_CMP(prev_lip->li_lsn, lip->li_lsn) <= 0); 587 } 588 ASSERT(lip->li_ail.ail_back == prev_lip); 589 ASSERT((lip->li_flags & XFS_LI_IN_AIL) != 0); 590 prev_lip = lip; 591 lip = lip->li_ail.ail_forw; 592 } 593 ASSERT(lip == (xfs_log_item_t*)base); 594 ASSERT(base->ail_back == prev_lip); 595 } 596 #endif /* DEBUG */ 597