Merge git://oss.sgi.com:8090/oss/git/xfs-2.6
[linux-2.6] / 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                         AIL_UNLOCK(mp, s);
383                         xfs_force_shutdown(mp, XFS_CORRUPT_INCORE);
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 */