xfs_trans_ail.c 14 KB

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