xfs_extent_busy.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604
  1. /*
  2. * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
  3. * Copyright (c) 2010 David Chinner.
  4. * Copyright (c) 2011 Christoph Hellwig.
  5. * All Rights Reserved.
  6. *
  7. * This program is free software; you can redistribute it and/or
  8. * modify it under the terms of the GNU General Public License as
  9. * published by the Free Software Foundation.
  10. *
  11. * This program is distributed in the hope that it would be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. * GNU General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with this program; if not, write the Free Software Foundation,
  18. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19. */
  20. #include "xfs.h"
  21. #include "xfs_fs.h"
  22. #include "xfs_format.h"
  23. #include "xfs_log_format.h"
  24. #include "xfs_shared.h"
  25. #include "xfs_trans_resv.h"
  26. #include "xfs_sb.h"
  27. #include "xfs_mount.h"
  28. #include "xfs_alloc.h"
  29. #include "xfs_extent_busy.h"
  30. #include "xfs_trace.h"
  31. #include "xfs_trans.h"
  32. #include "xfs_log.h"
  33. void
  34. xfs_extent_busy_insert(
  35. struct xfs_trans *tp,
  36. xfs_agnumber_t agno,
  37. xfs_agblock_t bno,
  38. xfs_extlen_t len,
  39. unsigned int flags)
  40. {
  41. struct xfs_extent_busy *new;
  42. struct xfs_extent_busy *busyp;
  43. struct xfs_perag *pag;
  44. struct rb_node **rbp;
  45. struct rb_node *parent = NULL;
  46. new = kmem_zalloc(sizeof(struct xfs_extent_busy), KM_MAYFAIL);
  47. if (!new) {
  48. /*
  49. * No Memory! Since it is now not possible to track the free
  50. * block, make this a synchronous transaction to insure that
  51. * the block is not reused before this transaction commits.
  52. */
  53. trace_xfs_extent_busy_enomem(tp->t_mountp, agno, bno, len);
  54. xfs_trans_set_sync(tp);
  55. return;
  56. }
  57. new->agno = agno;
  58. new->bno = bno;
  59. new->length = len;
  60. INIT_LIST_HEAD(&new->list);
  61. new->flags = flags;
  62. /* trace before insert to be able to see failed inserts */
  63. trace_xfs_extent_busy(tp->t_mountp, agno, bno, len);
  64. pag = xfs_perag_get(tp->t_mountp, new->agno);
  65. spin_lock(&pag->pagb_lock);
  66. rbp = &pag->pagb_tree.rb_node;
  67. while (*rbp) {
  68. parent = *rbp;
  69. busyp = rb_entry(parent, struct xfs_extent_busy, rb_node);
  70. if (new->bno < busyp->bno) {
  71. rbp = &(*rbp)->rb_left;
  72. ASSERT(new->bno + new->length <= busyp->bno);
  73. } else if (new->bno > busyp->bno) {
  74. rbp = &(*rbp)->rb_right;
  75. ASSERT(bno >= busyp->bno + busyp->length);
  76. } else {
  77. ASSERT(0);
  78. }
  79. }
  80. rb_link_node(&new->rb_node, parent, rbp);
  81. rb_insert_color(&new->rb_node, &pag->pagb_tree);
  82. list_add(&new->list, &tp->t_busy);
  83. spin_unlock(&pag->pagb_lock);
  84. xfs_perag_put(pag);
  85. }
  86. /*
  87. * Search for a busy extent within the range of the extent we are about to
  88. * allocate. You need to be holding the busy extent tree lock when calling
  89. * xfs_extent_busy_search(). This function returns 0 for no overlapping busy
  90. * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
  91. * match. This is done so that a non-zero return indicates an overlap that
  92. * will require a synchronous transaction, but it can still be
  93. * used to distinguish between a partial or exact match.
  94. */
  95. int
  96. xfs_extent_busy_search(
  97. struct xfs_mount *mp,
  98. xfs_agnumber_t agno,
  99. xfs_agblock_t bno,
  100. xfs_extlen_t len)
  101. {
  102. struct xfs_perag *pag;
  103. struct rb_node *rbp;
  104. struct xfs_extent_busy *busyp;
  105. int match = 0;
  106. pag = xfs_perag_get(mp, agno);
  107. spin_lock(&pag->pagb_lock);
  108. rbp = pag->pagb_tree.rb_node;
  109. /* find closest start bno overlap */
  110. while (rbp) {
  111. busyp = rb_entry(rbp, struct xfs_extent_busy, rb_node);
  112. if (bno < busyp->bno) {
  113. /* may overlap, but exact start block is lower */
  114. if (bno + len > busyp->bno)
  115. match = -1;
  116. rbp = rbp->rb_left;
  117. } else if (bno > busyp->bno) {
  118. /* may overlap, but exact start block is higher */
  119. if (bno < busyp->bno + busyp->length)
  120. match = -1;
  121. rbp = rbp->rb_right;
  122. } else {
  123. /* bno matches busyp, length determines exact match */
  124. match = (busyp->length == len) ? 1 : -1;
  125. break;
  126. }
  127. }
  128. spin_unlock(&pag->pagb_lock);
  129. xfs_perag_put(pag);
  130. return match;
  131. }
  132. /*
  133. * The found free extent [fbno, fend] overlaps part or all of the given busy
  134. * extent. If the overlap covers the beginning, the end, or all of the busy
  135. * extent, the overlapping portion can be made unbusy and used for the
  136. * allocation. We can't split a busy extent because we can't modify a
  137. * transaction/CIL context busy list, but we can update an entry's block
  138. * number or length.
  139. *
  140. * Returns true if the extent can safely be reused, or false if the search
  141. * needs to be restarted.
  142. */
  143. STATIC bool
  144. xfs_extent_busy_update_extent(
  145. struct xfs_mount *mp,
  146. struct xfs_perag *pag,
  147. struct xfs_extent_busy *busyp,
  148. xfs_agblock_t fbno,
  149. xfs_extlen_t flen,
  150. bool userdata) __releases(&pag->pagb_lock)
  151. __acquires(&pag->pagb_lock)
  152. {
  153. xfs_agblock_t fend = fbno + flen;
  154. xfs_agblock_t bbno = busyp->bno;
  155. xfs_agblock_t bend = bbno + busyp->length;
  156. /*
  157. * This extent is currently being discarded. Give the thread
  158. * performing the discard a chance to mark the extent unbusy
  159. * and retry.
  160. */
  161. if (busyp->flags & XFS_EXTENT_BUSY_DISCARDED) {
  162. spin_unlock(&pag->pagb_lock);
  163. delay(1);
  164. spin_lock(&pag->pagb_lock);
  165. return false;
  166. }
  167. /*
  168. * If there is a busy extent overlapping a user allocation, we have
  169. * no choice but to force the log and retry the search.
  170. *
  171. * Fortunately this does not happen during normal operation, but
  172. * only if the filesystem is very low on space and has to dip into
  173. * the AGFL for normal allocations.
  174. */
  175. if (userdata)
  176. goto out_force_log;
  177. if (bbno < fbno && bend > fend) {
  178. /*
  179. * Case 1:
  180. * bbno bend
  181. * +BBBBBBBBBBBBBBBBB+
  182. * +---------+
  183. * fbno fend
  184. */
  185. /*
  186. * We would have to split the busy extent to be able to track
  187. * it correct, which we cannot do because we would have to
  188. * modify the list of busy extents attached to the transaction
  189. * or CIL context, which is immutable.
  190. *
  191. * Force out the log to clear the busy extent and retry the
  192. * search.
  193. */
  194. goto out_force_log;
  195. } else if (bbno >= fbno && bend <= fend) {
  196. /*
  197. * Case 2:
  198. * bbno bend
  199. * +BBBBBBBBBBBBBBBBB+
  200. * +-----------------+
  201. * fbno fend
  202. *
  203. * Case 3:
  204. * bbno bend
  205. * +BBBBBBBBBBBBBBBBB+
  206. * +--------------------------+
  207. * fbno fend
  208. *
  209. * Case 4:
  210. * bbno bend
  211. * +BBBBBBBBBBBBBBBBB+
  212. * +--------------------------+
  213. * fbno fend
  214. *
  215. * Case 5:
  216. * bbno bend
  217. * +BBBBBBBBBBBBBBBBB+
  218. * +-----------------------------------+
  219. * fbno fend
  220. *
  221. */
  222. /*
  223. * The busy extent is fully covered by the extent we are
  224. * allocating, and can simply be removed from the rbtree.
  225. * However we cannot remove it from the immutable list
  226. * tracking busy extents in the transaction or CIL context,
  227. * so set the length to zero to mark it invalid.
  228. *
  229. * We also need to restart the busy extent search from the
  230. * tree root, because erasing the node can rearrange the
  231. * tree topology.
  232. */
  233. rb_erase(&busyp->rb_node, &pag->pagb_tree);
  234. busyp->length = 0;
  235. return false;
  236. } else if (fend < bend) {
  237. /*
  238. * Case 6:
  239. * bbno bend
  240. * +BBBBBBBBBBBBBBBBB+
  241. * +---------+
  242. * fbno fend
  243. *
  244. * Case 7:
  245. * bbno bend
  246. * +BBBBBBBBBBBBBBBBB+
  247. * +------------------+
  248. * fbno fend
  249. *
  250. */
  251. busyp->bno = fend;
  252. } else if (bbno < fbno) {
  253. /*
  254. * Case 8:
  255. * bbno bend
  256. * +BBBBBBBBBBBBBBBBB+
  257. * +-------------+
  258. * fbno fend
  259. *
  260. * Case 9:
  261. * bbno bend
  262. * +BBBBBBBBBBBBBBBBB+
  263. * +----------------------+
  264. * fbno fend
  265. */
  266. busyp->length = fbno - busyp->bno;
  267. } else {
  268. ASSERT(0);
  269. }
  270. trace_xfs_extent_busy_reuse(mp, pag->pag_agno, fbno, flen);
  271. return true;
  272. out_force_log:
  273. spin_unlock(&pag->pagb_lock);
  274. xfs_log_force(mp, XFS_LOG_SYNC);
  275. trace_xfs_extent_busy_force(mp, pag->pag_agno, fbno, flen);
  276. spin_lock(&pag->pagb_lock);
  277. return false;
  278. }
  279. /*
  280. * For a given extent [fbno, flen], make sure we can reuse it safely.
  281. */
  282. void
  283. xfs_extent_busy_reuse(
  284. struct xfs_mount *mp,
  285. xfs_agnumber_t agno,
  286. xfs_agblock_t fbno,
  287. xfs_extlen_t flen,
  288. bool userdata)
  289. {
  290. struct xfs_perag *pag;
  291. struct rb_node *rbp;
  292. ASSERT(flen > 0);
  293. pag = xfs_perag_get(mp, agno);
  294. spin_lock(&pag->pagb_lock);
  295. restart:
  296. rbp = pag->pagb_tree.rb_node;
  297. while (rbp) {
  298. struct xfs_extent_busy *busyp =
  299. rb_entry(rbp, struct xfs_extent_busy, rb_node);
  300. xfs_agblock_t bbno = busyp->bno;
  301. xfs_agblock_t bend = bbno + busyp->length;
  302. if (fbno + flen <= bbno) {
  303. rbp = rbp->rb_left;
  304. continue;
  305. } else if (fbno >= bend) {
  306. rbp = rbp->rb_right;
  307. continue;
  308. }
  309. if (!xfs_extent_busy_update_extent(mp, pag, busyp, fbno, flen,
  310. userdata))
  311. goto restart;
  312. }
  313. spin_unlock(&pag->pagb_lock);
  314. xfs_perag_put(pag);
  315. }
  316. /*
  317. * For a given extent [fbno, flen], search the busy extent list to find a
  318. * subset of the extent that is not busy. If *rlen is smaller than
  319. * args->minlen no suitable extent could be found, and the higher level
  320. * code needs to force out the log and retry the allocation.
  321. */
  322. void
  323. xfs_extent_busy_trim(
  324. struct xfs_alloc_arg *args,
  325. xfs_agblock_t bno,
  326. xfs_extlen_t len,
  327. xfs_agblock_t *rbno,
  328. xfs_extlen_t *rlen)
  329. {
  330. xfs_agblock_t fbno;
  331. xfs_extlen_t flen;
  332. struct rb_node *rbp;
  333. ASSERT(len > 0);
  334. spin_lock(&args->pag->pagb_lock);
  335. restart:
  336. fbno = bno;
  337. flen = len;
  338. rbp = args->pag->pagb_tree.rb_node;
  339. while (rbp && flen >= args->minlen) {
  340. struct xfs_extent_busy *busyp =
  341. rb_entry(rbp, struct xfs_extent_busy, rb_node);
  342. xfs_agblock_t fend = fbno + flen;
  343. xfs_agblock_t bbno = busyp->bno;
  344. xfs_agblock_t bend = bbno + busyp->length;
  345. if (fend <= bbno) {
  346. rbp = rbp->rb_left;
  347. continue;
  348. } else if (fbno >= bend) {
  349. rbp = rbp->rb_right;
  350. continue;
  351. }
  352. /*
  353. * If this is a metadata allocation, try to reuse the busy
  354. * extent instead of trimming the allocation.
  355. */
  356. if (!args->userdata &&
  357. !(busyp->flags & XFS_EXTENT_BUSY_DISCARDED)) {
  358. if (!xfs_extent_busy_update_extent(args->mp, args->pag,
  359. busyp, fbno, flen,
  360. false))
  361. goto restart;
  362. continue;
  363. }
  364. if (bbno <= fbno) {
  365. /* start overlap */
  366. /*
  367. * Case 1:
  368. * bbno bend
  369. * +BBBBBBBBBBBBBBBBB+
  370. * +---------+
  371. * fbno fend
  372. *
  373. * Case 2:
  374. * bbno bend
  375. * +BBBBBBBBBBBBBBBBB+
  376. * +-------------+
  377. * fbno fend
  378. *
  379. * Case 3:
  380. * bbno bend
  381. * +BBBBBBBBBBBBBBBBB+
  382. * +-------------+
  383. * fbno fend
  384. *
  385. * Case 4:
  386. * bbno bend
  387. * +BBBBBBBBBBBBBBBBB+
  388. * +-----------------+
  389. * fbno fend
  390. *
  391. * No unbusy region in extent, return failure.
  392. */
  393. if (fend <= bend)
  394. goto fail;
  395. /*
  396. * Case 5:
  397. * bbno bend
  398. * +BBBBBBBBBBBBBBBBB+
  399. * +----------------------+
  400. * fbno fend
  401. *
  402. * Case 6:
  403. * bbno bend
  404. * +BBBBBBBBBBBBBBBBB+
  405. * +--------------------------+
  406. * fbno fend
  407. *
  408. * Needs to be trimmed to:
  409. * +-------+
  410. * fbno fend
  411. */
  412. fbno = bend;
  413. } else if (bend >= fend) {
  414. /* end overlap */
  415. /*
  416. * Case 7:
  417. * bbno bend
  418. * +BBBBBBBBBBBBBBBBB+
  419. * +------------------+
  420. * fbno fend
  421. *
  422. * Case 8:
  423. * bbno bend
  424. * +BBBBBBBBBBBBBBBBB+
  425. * +--------------------------+
  426. * fbno fend
  427. *
  428. * Needs to be trimmed to:
  429. * +-------+
  430. * fbno fend
  431. */
  432. fend = bbno;
  433. } else {
  434. /* middle overlap */
  435. /*
  436. * Case 9:
  437. * bbno bend
  438. * +BBBBBBBBBBBBBBBBB+
  439. * +-----------------------------------+
  440. * fbno fend
  441. *
  442. * Can be trimmed to:
  443. * +-------+ OR +-------+
  444. * fbno fend fbno fend
  445. *
  446. * Backward allocation leads to significant
  447. * fragmentation of directories, which degrades
  448. * directory performance, therefore we always want to
  449. * choose the option that produces forward allocation
  450. * patterns.
  451. * Preferring the lower bno extent will make the next
  452. * request use "fend" as the start of the next
  453. * allocation; if the segment is no longer busy at
  454. * that point, we'll get a contiguous allocation, but
  455. * even if it is still busy, we will get a forward
  456. * allocation.
  457. * We try to avoid choosing the segment at "bend",
  458. * because that can lead to the next allocation
  459. * taking the segment at "fbno", which would be a
  460. * backward allocation. We only use the segment at
  461. * "fbno" if it is much larger than the current
  462. * requested size, because in that case there's a
  463. * good chance subsequent allocations will be
  464. * contiguous.
  465. */
  466. if (bbno - fbno >= args->maxlen) {
  467. /* left candidate fits perfect */
  468. fend = bbno;
  469. } else if (fend - bend >= args->maxlen * 4) {
  470. /* right candidate has enough free space */
  471. fbno = bend;
  472. } else if (bbno - fbno >= args->minlen) {
  473. /* left candidate fits minimum requirement */
  474. fend = bbno;
  475. } else {
  476. goto fail;
  477. }
  478. }
  479. flen = fend - fbno;
  480. }
  481. spin_unlock(&args->pag->pagb_lock);
  482. if (fbno != bno || flen != len) {
  483. trace_xfs_extent_busy_trim(args->mp, args->agno, bno, len,
  484. fbno, flen);
  485. }
  486. *rbno = fbno;
  487. *rlen = flen;
  488. return;
  489. fail:
  490. /*
  491. * Return a zero extent length as failure indications. All callers
  492. * re-check if the trimmed extent satisfies the minlen requirement.
  493. */
  494. spin_unlock(&args->pag->pagb_lock);
  495. trace_xfs_extent_busy_trim(args->mp, args->agno, bno, len, fbno, 0);
  496. *rbno = fbno;
  497. *rlen = 0;
  498. }
  499. STATIC void
  500. xfs_extent_busy_clear_one(
  501. struct xfs_mount *mp,
  502. struct xfs_perag *pag,
  503. struct xfs_extent_busy *busyp)
  504. {
  505. if (busyp->length) {
  506. trace_xfs_extent_busy_clear(mp, busyp->agno, busyp->bno,
  507. busyp->length);
  508. rb_erase(&busyp->rb_node, &pag->pagb_tree);
  509. }
  510. list_del_init(&busyp->list);
  511. kmem_free(busyp);
  512. }
  513. /*
  514. * Remove all extents on the passed in list from the busy extents tree.
  515. * If do_discard is set skip extents that need to be discarded, and mark
  516. * these as undergoing a discard operation instead.
  517. */
  518. void
  519. xfs_extent_busy_clear(
  520. struct xfs_mount *mp,
  521. struct list_head *list,
  522. bool do_discard)
  523. {
  524. struct xfs_extent_busy *busyp, *n;
  525. struct xfs_perag *pag = NULL;
  526. xfs_agnumber_t agno = NULLAGNUMBER;
  527. list_for_each_entry_safe(busyp, n, list, list) {
  528. if (busyp->agno != agno) {
  529. if (pag) {
  530. spin_unlock(&pag->pagb_lock);
  531. xfs_perag_put(pag);
  532. }
  533. pag = xfs_perag_get(mp, busyp->agno);
  534. spin_lock(&pag->pagb_lock);
  535. agno = busyp->agno;
  536. }
  537. if (do_discard && busyp->length &&
  538. !(busyp->flags & XFS_EXTENT_BUSY_SKIP_DISCARD))
  539. busyp->flags = XFS_EXTENT_BUSY_DISCARDED;
  540. else
  541. xfs_extent_busy_clear_one(mp, pag, busyp);
  542. }
  543. if (pag) {
  544. spin_unlock(&pag->pagb_lock);
  545. xfs_perag_put(pag);
  546. }
  547. }
  548. /*
  549. * Callback for list_sort to sort busy extents by the AG they reside in.
  550. */
  551. int
  552. xfs_extent_busy_ag_cmp(
  553. void *priv,
  554. struct list_head *a,
  555. struct list_head *b)
  556. {
  557. return container_of(a, struct xfs_extent_busy, list)->agno -
  558. container_of(b, struct xfs_extent_busy, list)->agno;
  559. }