fs/xfs/xfs_trans_ail.c

   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 */