Merge git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6
[wrt350n-kernel.git] / fs / xfs / xfs_trans_ail.c
blob34d9274925aa7d31378af9a03c6effccfd701b2e
1 /*
2 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_types.h"
21 #include "xfs_log.h"
22 #include "xfs_inum.h"
23 #include "xfs_trans.h"
24 #include "xfs_sb.h"
25 #include "xfs_ag.h"
26 #include "xfs_dmapi.h"
27 #include "xfs_mount.h"
28 #include "xfs_trans_priv.h"
29 #include "xfs_error.h"
31 STATIC void xfs_ail_insert(xfs_ail_entry_t *, xfs_log_item_t *);
32 STATIC xfs_log_item_t * xfs_ail_delete(xfs_ail_entry_t *, xfs_log_item_t *);
33 STATIC xfs_log_item_t * xfs_ail_min(xfs_ail_entry_t *);
34 STATIC xfs_log_item_t * xfs_ail_next(xfs_ail_entry_t *, xfs_log_item_t *);
36 #ifdef DEBUG
37 STATIC void xfs_ail_check(xfs_ail_entry_t *, xfs_log_item_t *);
38 #else
39 #define xfs_ail_check(a,l)
40 #endif /* DEBUG */
44 * This is called by the log manager code to determine the LSN
45 * of the tail of the log. This is exactly the LSN of the first
46 * item in the AIL. If the AIL is empty, then this function
47 * returns 0.
49 * We need the AIL lock in order to get a coherent read of the
50 * lsn of the last item in the AIL.
52 xfs_lsn_t
53 xfs_trans_tail_ail(
54 xfs_mount_t *mp)
56 xfs_lsn_t lsn;
57 xfs_log_item_t *lip;
59 spin_lock(&mp->m_ail_lock);
60 lip = xfs_ail_min(&(mp->m_ail.xa_ail));
61 if (lip == NULL) {
62 lsn = (xfs_lsn_t)0;
63 } else {
64 lsn = lip->li_lsn;
66 spin_unlock(&mp->m_ail_lock);
68 return lsn;
72 * xfs_trans_push_ail
74 * This routine is called to move the tail of the AIL forward. It does this by
75 * trying to flush items in the AIL whose lsns are below the given
76 * threshold_lsn.
78 * the push is run asynchronously in a separate thread, so we return the tail
79 * of the log right now instead of the tail after the push. This means we will
80 * either continue right away, or we will sleep waiting on the async thread to
81 * do it's work.
83 * We do this unlocked - we only need to know whether there is anything in the
84 * AIL at the time we are called. We don't need to access the contents of
85 * any of the objects, so the lock is not needed.
87 void
88 xfs_trans_push_ail(
89 xfs_mount_t *mp,
90 xfs_lsn_t threshold_lsn)
92 xfs_log_item_t *lip;
94 lip = xfs_ail_min(&mp->m_ail.xa_ail);
95 if (lip && !XFS_FORCED_SHUTDOWN(mp)) {
96 if (XFS_LSN_CMP(threshold_lsn, mp->m_ail.xa_target) > 0)
97 xfsaild_wakeup(mp, threshold_lsn);
102 * Return the item in the AIL with the current lsn.
103 * Return the current tree generation number for use
104 * in calls to xfs_trans_next_ail().
106 STATIC xfs_log_item_t *
107 xfs_trans_first_push_ail(
108 xfs_mount_t *mp,
109 int *gen,
110 xfs_lsn_t lsn)
112 xfs_log_item_t *lip;
114 lip = xfs_ail_min(&(mp->m_ail.xa_ail));
115 *gen = (int)mp->m_ail.xa_gen;
116 if (lsn == 0)
117 return lip;
119 while (lip && (XFS_LSN_CMP(lip->li_lsn, lsn) < 0))
120 lip = lip->li_ail.ail_forw;
122 return lip;
126 * Function that does the work of pushing on the AIL
128 long
129 xfsaild_push(
130 xfs_mount_t *mp,
131 xfs_lsn_t *last_lsn)
133 long tout = 1000; /* milliseconds */
134 xfs_lsn_t last_pushed_lsn = *last_lsn;
135 xfs_lsn_t target = mp->m_ail.xa_target;
136 xfs_lsn_t lsn;
137 xfs_log_item_t *lip;
138 int gen;
139 int restarts;
140 int flush_log, count, stuck;
142 #define XFS_TRANS_PUSH_AIL_RESTARTS 10
144 spin_lock(&mp->m_ail_lock);
145 lip = xfs_trans_first_push_ail(mp, &gen, *last_lsn);
146 if (!lip || XFS_FORCED_SHUTDOWN(mp)) {
148 * AIL is empty or our push has reached the end.
150 spin_unlock(&mp->m_ail_lock);
151 last_pushed_lsn = 0;
152 goto out;
155 XFS_STATS_INC(xs_push_ail);
158 * While the item we are looking at is below the given threshold
159 * try to flush it out. We'd like not to stop until we've at least
160 * tried to push on everything in the AIL with an LSN less than
161 * the given threshold.
163 * However, we will stop after a certain number of pushes and wait
164 * for a reduced timeout to fire before pushing further. This
165 * prevents use from spinning when we can't do anything or there is
166 * lots of contention on the AIL lists.
168 tout = 10;
169 lsn = lip->li_lsn;
170 flush_log = stuck = count = restarts = 0;
171 while ((XFS_LSN_CMP(lip->li_lsn, target) < 0)) {
172 int lock_result;
174 * If we can lock the item without sleeping, unlock the AIL
175 * lock and flush the item. Then re-grab the AIL lock so we
176 * can look for the next item on the AIL. List changes are
177 * handled by the AIL lookup functions internally
179 * If we can't lock the item, either its holder will flush it
180 * or it is already being flushed or it is being relogged. In
181 * any of these case it is being taken care of and we can just
182 * skip to the next item in the list.
184 lock_result = IOP_TRYLOCK(lip);
185 spin_unlock(&mp->m_ail_lock);
186 switch (lock_result) {
187 case XFS_ITEM_SUCCESS:
188 XFS_STATS_INC(xs_push_ail_success);
189 IOP_PUSH(lip);
190 last_pushed_lsn = lsn;
191 break;
193 case XFS_ITEM_PUSHBUF:
194 XFS_STATS_INC(xs_push_ail_pushbuf);
195 IOP_PUSHBUF(lip);
196 last_pushed_lsn = lsn;
197 break;
199 case XFS_ITEM_PINNED:
200 XFS_STATS_INC(xs_push_ail_pinned);
201 stuck++;
202 flush_log = 1;
203 break;
205 case XFS_ITEM_LOCKED:
206 XFS_STATS_INC(xs_push_ail_locked);
207 last_pushed_lsn = lsn;
208 stuck++;
209 break;
211 case XFS_ITEM_FLUSHING:
212 XFS_STATS_INC(xs_push_ail_flushing);
213 last_pushed_lsn = lsn;
214 stuck++;
215 break;
217 default:
218 ASSERT(0);
219 break;
222 spin_lock(&mp->m_ail_lock);
223 /* should we bother continuing? */
224 if (XFS_FORCED_SHUTDOWN(mp))
225 break;
226 ASSERT(mp->m_log);
228 count++;
231 * Are there too many items we can't do anything with?
232 * If we we are skipping too many items because we can't flush
233 * them or they are already being flushed, we back off and
234 * given them time to complete whatever operation is being
235 * done. i.e. remove pressure from the AIL while we can't make
236 * progress so traversals don't slow down further inserts and
237 * removals to/from the AIL.
239 * The value of 100 is an arbitrary magic number based on
240 * observation.
242 if (stuck > 100)
243 break;
245 lip = xfs_trans_next_ail(mp, lip, &gen, &restarts);
246 if (lip == NULL)
247 break;
248 if (restarts > XFS_TRANS_PUSH_AIL_RESTARTS)
249 break;
250 lsn = lip->li_lsn;
252 spin_unlock(&mp->m_ail_lock);
254 if (flush_log) {
256 * If something we need to push out was pinned, then
257 * push out the log so it will become unpinned and
258 * move forward in the AIL.
260 XFS_STATS_INC(xs_push_ail_flush);
261 xfs_log_force(mp, (xfs_lsn_t)0, XFS_LOG_FORCE);
264 <<<<<<< HEAD:fs/xfs/xfs_trans_ail.c
266 * We reached the target so wait a bit longer for I/O to complete and
267 * remove pushed items from the AIL before we start the next scan from
268 * the start of the AIL.
270 if ((XFS_LSN_CMP(lsn, target) >= 0)) {
271 =======
272 if (!count) {
273 /* We're past our target or empty, so idle */
274 tout = 1000;
275 } else if (XFS_LSN_CMP(lsn, target) >= 0) {
277 * We reached the target so wait a bit longer for I/O to
278 * complete and remove pushed items from the AIL before we
279 * start the next scan from the start of the AIL.
281 >>>>>>> 264e3e889d86e552b4191d69bb60f4f3b383135a:fs/xfs/xfs_trans_ail.c
282 tout += 20;
283 last_pushed_lsn = 0;
284 } else if ((restarts > XFS_TRANS_PUSH_AIL_RESTARTS) ||
285 <<<<<<< HEAD:fs/xfs/xfs_trans_ail.c
286 (count && ((stuck * 100) / count > 90))) {
287 =======
288 ((stuck * 100) / count > 90)) {
289 >>>>>>> 264e3e889d86e552b4191d69bb60f4f3b383135a:fs/xfs/xfs_trans_ail.c
291 * Either there is a lot of contention on the AIL or we
292 * are stuck due to operations in progress. "Stuck" in this
293 * case is defined as >90% of the items we tried to push
294 * were stuck.
296 * Backoff a bit more to allow some I/O to complete before
297 * continuing from where we were.
299 tout += 10;
301 out:
302 *last_lsn = last_pushed_lsn;
303 return tout;
304 } /* xfsaild_push */
308 * This is to be called when an item is unlocked that may have
309 * been in the AIL. It will wake up the first member of the AIL
310 * wait list if this item's unlocking might allow it to progress.
311 * If the item is in the AIL, then we need to get the AIL lock
312 * while doing our checking so we don't race with someone going
313 * to sleep waiting for this event in xfs_trans_push_ail().
315 void
316 xfs_trans_unlocked_item(
317 xfs_mount_t *mp,
318 xfs_log_item_t *lip)
320 xfs_log_item_t *min_lip;
323 * If we're forcibly shutting down, we may have
324 * unlocked log items arbitrarily. The last thing
325 * we want to do is to move the tail of the log
326 * over some potentially valid data.
328 if (!(lip->li_flags & XFS_LI_IN_AIL) ||
329 XFS_FORCED_SHUTDOWN(mp)) {
330 return;
334 * This is the one case where we can call into xfs_ail_min()
335 * without holding the AIL lock because we only care about the
336 * case where we are at the tail of the AIL. If the object isn't
337 * at the tail, it doesn't matter what result we get back. This
338 * is slightly racy because since we were just unlocked, we could
339 * go to sleep between the call to xfs_ail_min and the call to
340 * xfs_log_move_tail, have someone else lock us, commit to us disk,
341 * move us out of the tail of the AIL, and then we wake up. However,
342 * the call to xfs_log_move_tail() doesn't do anything if there's
343 * not enough free space to wake people up so we're safe calling it.
345 min_lip = xfs_ail_min(&mp->m_ail.xa_ail);
347 if (min_lip == lip)
348 xfs_log_move_tail(mp, 1);
349 } /* xfs_trans_unlocked_item */
353 * Update the position of the item in the AIL with the new
354 * lsn. If it is not yet in the AIL, add it. Otherwise, move
355 * it to its new position by removing it and re-adding it.
357 * Wakeup anyone with an lsn less than the item's lsn. If the item
358 * we move in the AIL is the minimum one, update the tail lsn in the
359 * log manager.
361 * Increment the AIL's generation count to indicate that the tree
362 * has changed.
364 * This function must be called with the AIL lock held. The lock
365 * is dropped before returning.
367 void
368 xfs_trans_update_ail(
369 xfs_mount_t *mp,
370 xfs_log_item_t *lip,
371 xfs_lsn_t lsn) __releases(mp->m_ail_lock)
373 xfs_ail_entry_t *ailp;
374 xfs_log_item_t *dlip=NULL;
375 xfs_log_item_t *mlip; /* ptr to minimum lip */
377 ailp = &(mp->m_ail.xa_ail);
378 mlip = xfs_ail_min(ailp);
380 if (lip->li_flags & XFS_LI_IN_AIL) {
381 dlip = xfs_ail_delete(ailp, lip);
382 ASSERT(dlip == lip);
383 } else {
384 lip->li_flags |= XFS_LI_IN_AIL;
387 lip->li_lsn = lsn;
389 xfs_ail_insert(ailp, lip);
390 mp->m_ail.xa_gen++;
392 if (mlip == dlip) {
393 mlip = xfs_ail_min(&(mp->m_ail.xa_ail));
394 spin_unlock(&mp->m_ail_lock);
395 xfs_log_move_tail(mp, mlip->li_lsn);
396 } else {
397 spin_unlock(&mp->m_ail_lock);
401 } /* xfs_trans_update_ail */
404 * Delete the given item from the AIL. It must already be in
405 * the AIL.
407 * Wakeup anyone with an lsn less than item's lsn. If the item
408 * we delete in the AIL is the minimum one, update the tail lsn in the
409 * log manager.
411 * Clear the IN_AIL flag from the item, reset its lsn to 0, and
412 * bump the AIL's generation count to indicate that the tree
413 * has changed.
415 * This function must be called with the AIL lock held. The lock
416 * is dropped before returning.
418 void
419 xfs_trans_delete_ail(
420 xfs_mount_t *mp,
421 xfs_log_item_t *lip) __releases(mp->m_ail_lock)
423 xfs_ail_entry_t *ailp;
424 xfs_log_item_t *dlip;
425 xfs_log_item_t *mlip;
427 if (lip->li_flags & XFS_LI_IN_AIL) {
428 ailp = &(mp->m_ail.xa_ail);
429 mlip = xfs_ail_min(ailp);
430 dlip = xfs_ail_delete(ailp, lip);
431 ASSERT(dlip == lip);
434 lip->li_flags &= ~XFS_LI_IN_AIL;
435 lip->li_lsn = 0;
436 mp->m_ail.xa_gen++;
438 if (mlip == dlip) {
439 mlip = xfs_ail_min(&(mp->m_ail.xa_ail));
440 spin_unlock(&mp->m_ail_lock);
441 xfs_log_move_tail(mp, (mlip ? mlip->li_lsn : 0));
442 } else {
443 spin_unlock(&mp->m_ail_lock);
446 else {
448 * If the file system is not being shutdown, we are in
449 * serious trouble if we get to this stage.
451 if (XFS_FORCED_SHUTDOWN(mp))
452 spin_unlock(&mp->m_ail_lock);
453 else {
454 xfs_cmn_err(XFS_PTAG_AILDELETE, CE_ALERT, mp,
455 "%s: attempting to delete a log item that is not in the AIL",
456 __FUNCTION__);
457 spin_unlock(&mp->m_ail_lock);
458 xfs_force_shutdown(mp, SHUTDOWN_CORRUPT_INCORE);
466 * Return the item in the AIL with the smallest lsn.
467 * Return the current tree generation number for use
468 * in calls to xfs_trans_next_ail().
470 xfs_log_item_t *
471 xfs_trans_first_ail(
472 xfs_mount_t *mp,
473 int *gen)
475 xfs_log_item_t *lip;
477 lip = xfs_ail_min(&(mp->m_ail.xa_ail));
478 *gen = (int)mp->m_ail.xa_gen;
480 return lip;
484 * If the generation count of the tree has not changed since the
485 * caller last took something from the AIL, then return the elmt
486 * in the tree which follows the one given. If the count has changed,
487 * then return the minimum elmt of the AIL and bump the restarts counter
488 * if one is given.
490 xfs_log_item_t *
491 xfs_trans_next_ail(
492 xfs_mount_t *mp,
493 xfs_log_item_t *lip,
494 int *gen,
495 int *restarts)
497 xfs_log_item_t *nlip;
499 ASSERT(mp && lip && gen);
500 if (mp->m_ail.xa_gen == *gen) {
501 nlip = xfs_ail_next(&(mp->m_ail.xa_ail), lip);
502 } else {
503 nlip = xfs_ail_min(&(mp->m_ail).xa_ail);
504 *gen = (int)mp->m_ail.xa_gen;
505 if (restarts != NULL) {
506 XFS_STATS_INC(xs_push_ail_restarts);
507 (*restarts)++;
511 return (nlip);
516 * The active item list (AIL) is a doubly linked list of log
517 * items sorted by ascending lsn. The base of the list is
518 * a forw/back pointer pair embedded in the xfs mount structure.
519 * The base is initialized with both pointers pointing to the
520 * base. This case always needs to be distinguished, because
521 * the base has no lsn to look at. We almost always insert
522 * at the end of the list, so on inserts we search from the
523 * end of the list to find where the new item belongs.
527 * Initialize the doubly linked list to point only to itself.
530 xfs_trans_ail_init(
531 xfs_mount_t *mp)
533 mp->m_ail.xa_ail.ail_forw = (xfs_log_item_t*)&mp->m_ail.xa_ail;
534 mp->m_ail.xa_ail.ail_back = (xfs_log_item_t*)&mp->m_ail.xa_ail;
535 return xfsaild_start(mp);
538 void
539 xfs_trans_ail_destroy(
540 xfs_mount_t *mp)
542 xfsaild_stop(mp);
546 * Insert the given log item into the AIL.
547 * We almost always insert at the end of the list, so on inserts
548 * we search from the end of the list to find where the
549 * new item belongs.
551 STATIC void
552 xfs_ail_insert(
553 xfs_ail_entry_t *base,
554 xfs_log_item_t *lip)
555 /* ARGSUSED */
557 xfs_log_item_t *next_lip;
560 * If the list is empty, just insert the item.
562 if (base->ail_back == (xfs_log_item_t*)base) {
563 base->ail_forw = lip;
564 base->ail_back = lip;
565 lip->li_ail.ail_forw = (xfs_log_item_t*)base;
566 lip->li_ail.ail_back = (xfs_log_item_t*)base;
567 return;
570 next_lip = base->ail_back;
571 while ((next_lip != (xfs_log_item_t*)base) &&
572 (XFS_LSN_CMP(next_lip->li_lsn, lip->li_lsn) > 0)) {
573 next_lip = next_lip->li_ail.ail_back;
575 ASSERT((next_lip == (xfs_log_item_t*)base) ||
576 (XFS_LSN_CMP(next_lip->li_lsn, lip->li_lsn) <= 0));
577 lip->li_ail.ail_forw = next_lip->li_ail.ail_forw;
578 lip->li_ail.ail_back = next_lip;
579 next_lip->li_ail.ail_forw = lip;
580 lip->li_ail.ail_forw->li_ail.ail_back = lip;
582 xfs_ail_check(base, lip);
583 return;
587 * Delete the given item from the AIL. Return a pointer to the item.
589 /*ARGSUSED*/
590 STATIC xfs_log_item_t *
591 xfs_ail_delete(
592 xfs_ail_entry_t *base,
593 xfs_log_item_t *lip)
594 /* ARGSUSED */
596 xfs_ail_check(base, lip);
597 lip->li_ail.ail_forw->li_ail.ail_back = lip->li_ail.ail_back;
598 lip->li_ail.ail_back->li_ail.ail_forw = lip->li_ail.ail_forw;
599 lip->li_ail.ail_forw = NULL;
600 lip->li_ail.ail_back = NULL;
602 return lip;
606 * Return a pointer to the first item in the AIL.
607 * If the AIL is empty, then return NULL.
609 STATIC xfs_log_item_t *
610 xfs_ail_min(
611 xfs_ail_entry_t *base)
612 /* ARGSUSED */
614 register xfs_log_item_t *forw = base->ail_forw;
615 if (forw == (xfs_log_item_t*)base) {
616 return NULL;
618 return forw;
622 * Return a pointer to the item which follows
623 * the given item in the AIL. If the given item
624 * is the last item in the list, then return NULL.
626 STATIC xfs_log_item_t *
627 xfs_ail_next(
628 xfs_ail_entry_t *base,
629 xfs_log_item_t *lip)
630 /* ARGSUSED */
632 if (lip->li_ail.ail_forw == (xfs_log_item_t*)base) {
633 return NULL;
635 return lip->li_ail.ail_forw;
639 #ifdef DEBUG
641 * Check that the list is sorted as it should be.
643 STATIC void
644 xfs_ail_check(
645 xfs_ail_entry_t *base,
646 xfs_log_item_t *lip)
648 xfs_log_item_t *prev_lip;
650 prev_lip = base->ail_forw;
651 if (prev_lip == (xfs_log_item_t*)base) {
653 * Make sure the pointers are correct when the list
654 * is empty.
656 ASSERT(base->ail_back == (xfs_log_item_t*)base);
657 return;
661 * Check the next and previous entries are valid.
663 ASSERT((lip->li_flags & XFS_LI_IN_AIL) != 0);
664 prev_lip = lip->li_ail.ail_back;
665 if (prev_lip != (xfs_log_item_t*)base) {
666 ASSERT(prev_lip->li_ail.ail_forw == lip);
667 ASSERT(XFS_LSN_CMP(prev_lip->li_lsn, lip->li_lsn) <= 0);
669 prev_lip = lip->li_ail.ail_forw;
670 if (prev_lip != (xfs_log_item_t*)base) {
671 ASSERT(prev_lip->li_ail.ail_back == lip);
672 ASSERT(XFS_LSN_CMP(prev_lip->li_lsn, lip->li_lsn) >= 0);
676 #ifdef XFS_TRANS_DEBUG
678 * Walk the list checking forward and backward pointers,
679 * lsn ordering, and that every entry has the XFS_LI_IN_AIL
680 * flag set. This is really expensive, so only do it when
681 * specifically debugging the transaction subsystem.
683 prev_lip = (xfs_log_item_t*)base;
684 while (lip != (xfs_log_item_t*)base) {
685 if (prev_lip != (xfs_log_item_t*)base) {
686 ASSERT(prev_lip->li_ail.ail_forw == lip);
687 ASSERT(XFS_LSN_CMP(prev_lip->li_lsn, lip->li_lsn) <= 0);
689 ASSERT(lip->li_ail.ail_back == prev_lip);
690 ASSERT((lip->li_flags & XFS_LI_IN_AIL) != 0);
691 prev_lip = lip;
692 lip = lip->li_ail.ail_forw;
694 ASSERT(lip == (xfs_log_item_t*)base);
695 ASSERT(base->ail_back == prev_lip);
696 #endif /* XFS_TRANS_DEBUG */
698 #endif /* DEBUG */