xfs_rmap_btree.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (c) 2014 Red Hat, Inc.
  4. * All Rights Reserved.
  5. */
  6. #include "xfs.h"
  7. #include "xfs_fs.h"
  8. #include "xfs_shared.h"
  9. #include "xfs_format.h"
  10. #include "xfs_log_format.h"
  11. #include "xfs_trans_resv.h"
  12. #include "xfs_mount.h"
  13. #include "xfs_trans.h"
  14. #include "xfs_alloc.h"
  15. #include "xfs_btree.h"
  16. #include "xfs_btree_staging.h"
  17. #include "xfs_rmap.h"
  18. #include "xfs_rmap_btree.h"
  19. #include "xfs_trace.h"
  20. #include "xfs_error.h"
  21. #include "xfs_extent_busy.h"
  22. #include "xfs_ag.h"
  23. #include "xfs_ag_resv.h"
  24. static struct kmem_cache *xfs_rmapbt_cur_cache;
  25. /*
  26. * Reverse map btree.
  27. *
  28. * This is a per-ag tree used to track the owner(s) of a given extent. With
  29. * reflink it is possible for there to be multiple owners, which is a departure
  30. * from classic XFS. Owner records for data extents are inserted when the
  31. * extent is mapped and removed when an extent is unmapped. Owner records for
  32. * all other block types (i.e. metadata) are inserted when an extent is
  33. * allocated and removed when an extent is freed. There can only be one owner
  34. * of a metadata extent, usually an inode or some other metadata structure like
  35. * an AG btree.
  36. *
  37. * The rmap btree is part of the free space management, so blocks for the tree
  38. * are sourced from the agfl. Hence we need transaction reservation support for
  39. * this tree so that the freelist is always large enough. This also impacts on
  40. * the minimum space we need to leave free in the AG.
  41. *
  42. * The tree is ordered by [ag block, owner, offset]. This is a large key size,
  43. * but it is the only way to enforce unique keys when a block can be owned by
  44. * multiple files at any offset. There's no need to order/search by extent
  45. * size for online updating/management of the tree. It is intended that most
  46. * reverse lookups will be to find the owner(s) of a particular block, or to
  47. * try to recover tree and file data from corrupt primary metadata.
  48. */
  49. static struct xfs_btree_cur *
  50. xfs_rmapbt_dup_cursor(
  51. struct xfs_btree_cur *cur)
  52. {
  53. return xfs_rmapbt_init_cursor(cur->bc_mp, cur->bc_tp,
  54. cur->bc_ag.agbp, cur->bc_ag.pag);
  55. }
  56. STATIC void
  57. xfs_rmapbt_set_root(
  58. struct xfs_btree_cur *cur,
  59. const union xfs_btree_ptr *ptr,
  60. int inc)
  61. {
  62. struct xfs_buf *agbp = cur->bc_ag.agbp;
  63. struct xfs_agf *agf = agbp->b_addr;
  64. int btnum = cur->bc_btnum;
  65. ASSERT(ptr->s != 0);
  66. agf->agf_roots[btnum] = ptr->s;
  67. be32_add_cpu(&agf->agf_levels[btnum], inc);
  68. cur->bc_ag.pag->pagf_levels[btnum] += inc;
  69. xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
  70. }
  71. STATIC int
  72. xfs_rmapbt_alloc_block(
  73. struct xfs_btree_cur *cur,
  74. const union xfs_btree_ptr *start,
  75. union xfs_btree_ptr *new,
  76. int *stat)
  77. {
  78. struct xfs_buf *agbp = cur->bc_ag.agbp;
  79. struct xfs_agf *agf = agbp->b_addr;
  80. struct xfs_perag *pag = cur->bc_ag.pag;
  81. int error;
  82. xfs_agblock_t bno;
  83. /* Allocate the new block from the freelist. If we can't, give up. */
  84. error = xfs_alloc_get_freelist(pag, cur->bc_tp, cur->bc_ag.agbp,
  85. &bno, 1);
  86. if (error)
  87. return error;
  88. trace_xfs_rmapbt_alloc_block(cur->bc_mp, pag->pag_agno, bno, 1);
  89. if (bno == NULLAGBLOCK) {
  90. *stat = 0;
  91. return 0;
  92. }
  93. xfs_extent_busy_reuse(cur->bc_mp, pag, bno, 1, false);
  94. new->s = cpu_to_be32(bno);
  95. be32_add_cpu(&agf->agf_rmap_blocks, 1);
  96. xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS);
  97. xfs_ag_resv_rmapbt_alloc(cur->bc_mp, pag->pag_agno);
  98. *stat = 1;
  99. return 0;
  100. }
  101. STATIC int
  102. xfs_rmapbt_free_block(
  103. struct xfs_btree_cur *cur,
  104. struct xfs_buf *bp)
  105. {
  106. struct xfs_buf *agbp = cur->bc_ag.agbp;
  107. struct xfs_agf *agf = agbp->b_addr;
  108. struct xfs_perag *pag = cur->bc_ag.pag;
  109. xfs_agblock_t bno;
  110. int error;
  111. bno = xfs_daddr_to_agbno(cur->bc_mp, xfs_buf_daddr(bp));
  112. trace_xfs_rmapbt_free_block(cur->bc_mp, pag->pag_agno,
  113. bno, 1);
  114. be32_add_cpu(&agf->agf_rmap_blocks, -1);
  115. xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS);
  116. error = xfs_alloc_put_freelist(pag, cur->bc_tp, agbp, NULL, bno, 1);
  117. if (error)
  118. return error;
  119. xfs_extent_busy_insert(cur->bc_tp, pag, bno, 1,
  120. XFS_EXTENT_BUSY_SKIP_DISCARD);
  121. xfs_ag_resv_free_extent(pag, XFS_AG_RESV_RMAPBT, NULL, 1);
  122. return 0;
  123. }
  124. STATIC int
  125. xfs_rmapbt_get_minrecs(
  126. struct xfs_btree_cur *cur,
  127. int level)
  128. {
  129. return cur->bc_mp->m_rmap_mnr[level != 0];
  130. }
  131. STATIC int
  132. xfs_rmapbt_get_maxrecs(
  133. struct xfs_btree_cur *cur,
  134. int level)
  135. {
  136. return cur->bc_mp->m_rmap_mxr[level != 0];
  137. }
  138. STATIC void
  139. xfs_rmapbt_init_key_from_rec(
  140. union xfs_btree_key *key,
  141. const union xfs_btree_rec *rec)
  142. {
  143. key->rmap.rm_startblock = rec->rmap.rm_startblock;
  144. key->rmap.rm_owner = rec->rmap.rm_owner;
  145. key->rmap.rm_offset = rec->rmap.rm_offset;
  146. }
  147. /*
  148. * The high key for a reverse mapping record can be computed by shifting
  149. * the startblock and offset to the highest value that would still map
  150. * to that record. In practice this means that we add blockcount-1 to
  151. * the startblock for all records, and if the record is for a data/attr
  152. * fork mapping, we add blockcount-1 to the offset too.
  153. */
  154. STATIC void
  155. xfs_rmapbt_init_high_key_from_rec(
  156. union xfs_btree_key *key,
  157. const union xfs_btree_rec *rec)
  158. {
  159. uint64_t off;
  160. int adj;
  161. adj = be32_to_cpu(rec->rmap.rm_blockcount) - 1;
  162. key->rmap.rm_startblock = rec->rmap.rm_startblock;
  163. be32_add_cpu(&key->rmap.rm_startblock, adj);
  164. key->rmap.rm_owner = rec->rmap.rm_owner;
  165. key->rmap.rm_offset = rec->rmap.rm_offset;
  166. if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rmap.rm_owner)) ||
  167. XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rmap.rm_offset)))
  168. return;
  169. off = be64_to_cpu(key->rmap.rm_offset);
  170. off = (XFS_RMAP_OFF(off) + adj) | (off & ~XFS_RMAP_OFF_MASK);
  171. key->rmap.rm_offset = cpu_to_be64(off);
  172. }
  173. STATIC void
  174. xfs_rmapbt_init_rec_from_cur(
  175. struct xfs_btree_cur *cur,
  176. union xfs_btree_rec *rec)
  177. {
  178. rec->rmap.rm_startblock = cpu_to_be32(cur->bc_rec.r.rm_startblock);
  179. rec->rmap.rm_blockcount = cpu_to_be32(cur->bc_rec.r.rm_blockcount);
  180. rec->rmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner);
  181. rec->rmap.rm_offset = cpu_to_be64(
  182. xfs_rmap_irec_offset_pack(&cur->bc_rec.r));
  183. }
  184. STATIC void
  185. xfs_rmapbt_init_ptr_from_cur(
  186. struct xfs_btree_cur *cur,
  187. union xfs_btree_ptr *ptr)
  188. {
  189. struct xfs_agf *agf = cur->bc_ag.agbp->b_addr;
  190. ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno));
  191. ptr->s = agf->agf_roots[cur->bc_btnum];
  192. }
  193. STATIC int64_t
  194. xfs_rmapbt_key_diff(
  195. struct xfs_btree_cur *cur,
  196. const union xfs_btree_key *key)
  197. {
  198. struct xfs_rmap_irec *rec = &cur->bc_rec.r;
  199. const struct xfs_rmap_key *kp = &key->rmap;
  200. __u64 x, y;
  201. int64_t d;
  202. d = (int64_t)be32_to_cpu(kp->rm_startblock) - rec->rm_startblock;
  203. if (d)
  204. return d;
  205. x = be64_to_cpu(kp->rm_owner);
  206. y = rec->rm_owner;
  207. if (x > y)
  208. return 1;
  209. else if (y > x)
  210. return -1;
  211. x = XFS_RMAP_OFF(be64_to_cpu(kp->rm_offset));
  212. y = rec->rm_offset;
  213. if (x > y)
  214. return 1;
  215. else if (y > x)
  216. return -1;
  217. return 0;
  218. }
  219. STATIC int64_t
  220. xfs_rmapbt_diff_two_keys(
  221. struct xfs_btree_cur *cur,
  222. const union xfs_btree_key *k1,
  223. const union xfs_btree_key *k2)
  224. {
  225. const struct xfs_rmap_key *kp1 = &k1->rmap;
  226. const struct xfs_rmap_key *kp2 = &k2->rmap;
  227. int64_t d;
  228. __u64 x, y;
  229. d = (int64_t)be32_to_cpu(kp1->rm_startblock) -
  230. be32_to_cpu(kp2->rm_startblock);
  231. if (d)
  232. return d;
  233. x = be64_to_cpu(kp1->rm_owner);
  234. y = be64_to_cpu(kp2->rm_owner);
  235. if (x > y)
  236. return 1;
  237. else if (y > x)
  238. return -1;
  239. x = XFS_RMAP_OFF(be64_to_cpu(kp1->rm_offset));
  240. y = XFS_RMAP_OFF(be64_to_cpu(kp2->rm_offset));
  241. if (x > y)
  242. return 1;
  243. else if (y > x)
  244. return -1;
  245. return 0;
  246. }
  247. static xfs_failaddr_t
  248. xfs_rmapbt_verify(
  249. struct xfs_buf *bp)
  250. {
  251. struct xfs_mount *mp = bp->b_mount;
  252. struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
  253. struct xfs_perag *pag = bp->b_pag;
  254. xfs_failaddr_t fa;
  255. unsigned int level;
  256. /*
  257. * magic number and level verification
  258. *
  259. * During growfs operations, we can't verify the exact level or owner as
  260. * the perag is not fully initialised and hence not attached to the
  261. * buffer. In this case, check against the maximum tree depth.
  262. *
  263. * Similarly, during log recovery we will have a perag structure
  264. * attached, but the agf information will not yet have been initialised
  265. * from the on disk AGF. Again, we can only check against maximum limits
  266. * in this case.
  267. */
  268. if (!xfs_verify_magic(bp, block->bb_magic))
  269. return __this_address;
  270. if (!xfs_has_rmapbt(mp))
  271. return __this_address;
  272. fa = xfs_btree_sblock_v5hdr_verify(bp);
  273. if (fa)
  274. return fa;
  275. level = be16_to_cpu(block->bb_level);
  276. if (pag && pag->pagf_init) {
  277. if (level >= pag->pagf_levels[XFS_BTNUM_RMAPi])
  278. return __this_address;
  279. } else if (level >= mp->m_rmap_maxlevels)
  280. return __this_address;
  281. return xfs_btree_sblock_verify(bp, mp->m_rmap_mxr[level != 0]);
  282. }
  283. static void
  284. xfs_rmapbt_read_verify(
  285. struct xfs_buf *bp)
  286. {
  287. xfs_failaddr_t fa;
  288. if (!xfs_btree_sblock_verify_crc(bp))
  289. xfs_verifier_error(bp, -EFSBADCRC, __this_address);
  290. else {
  291. fa = xfs_rmapbt_verify(bp);
  292. if (fa)
  293. xfs_verifier_error(bp, -EFSCORRUPTED, fa);
  294. }
  295. if (bp->b_error)
  296. trace_xfs_btree_corrupt(bp, _RET_IP_);
  297. }
  298. static void
  299. xfs_rmapbt_write_verify(
  300. struct xfs_buf *bp)
  301. {
  302. xfs_failaddr_t fa;
  303. fa = xfs_rmapbt_verify(bp);
  304. if (fa) {
  305. trace_xfs_btree_corrupt(bp, _RET_IP_);
  306. xfs_verifier_error(bp, -EFSCORRUPTED, fa);
  307. return;
  308. }
  309. xfs_btree_sblock_calc_crc(bp);
  310. }
  311. const struct xfs_buf_ops xfs_rmapbt_buf_ops = {
  312. .name = "xfs_rmapbt",
  313. .magic = { 0, cpu_to_be32(XFS_RMAP_CRC_MAGIC) },
  314. .verify_read = xfs_rmapbt_read_verify,
  315. .verify_write = xfs_rmapbt_write_verify,
  316. .verify_struct = xfs_rmapbt_verify,
  317. };
  318. STATIC int
  319. xfs_rmapbt_keys_inorder(
  320. struct xfs_btree_cur *cur,
  321. const union xfs_btree_key *k1,
  322. const union xfs_btree_key *k2)
  323. {
  324. uint32_t x;
  325. uint32_t y;
  326. uint64_t a;
  327. uint64_t b;
  328. x = be32_to_cpu(k1->rmap.rm_startblock);
  329. y = be32_to_cpu(k2->rmap.rm_startblock);
  330. if (x < y)
  331. return 1;
  332. else if (x > y)
  333. return 0;
  334. a = be64_to_cpu(k1->rmap.rm_owner);
  335. b = be64_to_cpu(k2->rmap.rm_owner);
  336. if (a < b)
  337. return 1;
  338. else if (a > b)
  339. return 0;
  340. a = XFS_RMAP_OFF(be64_to_cpu(k1->rmap.rm_offset));
  341. b = XFS_RMAP_OFF(be64_to_cpu(k2->rmap.rm_offset));
  342. if (a <= b)
  343. return 1;
  344. return 0;
  345. }
  346. STATIC int
  347. xfs_rmapbt_recs_inorder(
  348. struct xfs_btree_cur *cur,
  349. const union xfs_btree_rec *r1,
  350. const union xfs_btree_rec *r2)
  351. {
  352. uint32_t x;
  353. uint32_t y;
  354. uint64_t a;
  355. uint64_t b;
  356. x = be32_to_cpu(r1->rmap.rm_startblock);
  357. y = be32_to_cpu(r2->rmap.rm_startblock);
  358. if (x < y)
  359. return 1;
  360. else if (x > y)
  361. return 0;
  362. a = be64_to_cpu(r1->rmap.rm_owner);
  363. b = be64_to_cpu(r2->rmap.rm_owner);
  364. if (a < b)
  365. return 1;
  366. else if (a > b)
  367. return 0;
  368. a = XFS_RMAP_OFF(be64_to_cpu(r1->rmap.rm_offset));
  369. b = XFS_RMAP_OFF(be64_to_cpu(r2->rmap.rm_offset));
  370. if (a <= b)
  371. return 1;
  372. return 0;
  373. }
  374. static const struct xfs_btree_ops xfs_rmapbt_ops = {
  375. .rec_len = sizeof(struct xfs_rmap_rec),
  376. .key_len = 2 * sizeof(struct xfs_rmap_key),
  377. .dup_cursor = xfs_rmapbt_dup_cursor,
  378. .set_root = xfs_rmapbt_set_root,
  379. .alloc_block = xfs_rmapbt_alloc_block,
  380. .free_block = xfs_rmapbt_free_block,
  381. .get_minrecs = xfs_rmapbt_get_minrecs,
  382. .get_maxrecs = xfs_rmapbt_get_maxrecs,
  383. .init_key_from_rec = xfs_rmapbt_init_key_from_rec,
  384. .init_high_key_from_rec = xfs_rmapbt_init_high_key_from_rec,
  385. .init_rec_from_cur = xfs_rmapbt_init_rec_from_cur,
  386. .init_ptr_from_cur = xfs_rmapbt_init_ptr_from_cur,
  387. .key_diff = xfs_rmapbt_key_diff,
  388. .buf_ops = &xfs_rmapbt_buf_ops,
  389. .diff_two_keys = xfs_rmapbt_diff_two_keys,
  390. .keys_inorder = xfs_rmapbt_keys_inorder,
  391. .recs_inorder = xfs_rmapbt_recs_inorder,
  392. };
  393. static struct xfs_btree_cur *
  394. xfs_rmapbt_init_common(
  395. struct xfs_mount *mp,
  396. struct xfs_trans *tp,
  397. struct xfs_perag *pag)
  398. {
  399. struct xfs_btree_cur *cur;
  400. /* Overlapping btree; 2 keys per pointer. */
  401. cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_RMAP,
  402. mp->m_rmap_maxlevels, xfs_rmapbt_cur_cache);
  403. cur->bc_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_OVERLAPPING;
  404. cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_rmap_2);
  405. cur->bc_ops = &xfs_rmapbt_ops;
  406. /* take a reference for the cursor */
  407. atomic_inc(&pag->pag_ref);
  408. cur->bc_ag.pag = pag;
  409. return cur;
  410. }
  411. /* Create a new reverse mapping btree cursor. */
  412. struct xfs_btree_cur *
  413. xfs_rmapbt_init_cursor(
  414. struct xfs_mount *mp,
  415. struct xfs_trans *tp,
  416. struct xfs_buf *agbp,
  417. struct xfs_perag *pag)
  418. {
  419. struct xfs_agf *agf = agbp->b_addr;
  420. struct xfs_btree_cur *cur;
  421. cur = xfs_rmapbt_init_common(mp, tp, pag);
  422. cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]);
  423. cur->bc_ag.agbp = agbp;
  424. return cur;
  425. }
  426. /* Create a new reverse mapping btree cursor with a fake root for staging. */
  427. struct xfs_btree_cur *
  428. xfs_rmapbt_stage_cursor(
  429. struct xfs_mount *mp,
  430. struct xbtree_afakeroot *afake,
  431. struct xfs_perag *pag)
  432. {
  433. struct xfs_btree_cur *cur;
  434. cur = xfs_rmapbt_init_common(mp, NULL, pag);
  435. xfs_btree_stage_afakeroot(cur, afake);
  436. return cur;
  437. }
  438. /*
  439. * Install a new reverse mapping btree root. Caller is responsible for
  440. * invalidating and freeing the old btree blocks.
  441. */
  442. void
  443. xfs_rmapbt_commit_staged_btree(
  444. struct xfs_btree_cur *cur,
  445. struct xfs_trans *tp,
  446. struct xfs_buf *agbp)
  447. {
  448. struct xfs_agf *agf = agbp->b_addr;
  449. struct xbtree_afakeroot *afake = cur->bc_ag.afake;
  450. ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
  451. agf->agf_roots[cur->bc_btnum] = cpu_to_be32(afake->af_root);
  452. agf->agf_levels[cur->bc_btnum] = cpu_to_be32(afake->af_levels);
  453. agf->agf_rmap_blocks = cpu_to_be32(afake->af_blocks);
  454. xfs_alloc_log_agf(tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS |
  455. XFS_AGF_RMAP_BLOCKS);
  456. xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_rmapbt_ops);
  457. }
  458. /* Calculate number of records in a reverse mapping btree block. */
  459. static inline unsigned int
  460. xfs_rmapbt_block_maxrecs(
  461. unsigned int blocklen,
  462. bool leaf)
  463. {
  464. if (leaf)
  465. return blocklen / sizeof(struct xfs_rmap_rec);
  466. return blocklen /
  467. (2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t));
  468. }
  469. /*
  470. * Calculate number of records in an rmap btree block.
  471. */
  472. int
  473. xfs_rmapbt_maxrecs(
  474. int blocklen,
  475. int leaf)
  476. {
  477. blocklen -= XFS_RMAP_BLOCK_LEN;
  478. return xfs_rmapbt_block_maxrecs(blocklen, leaf);
  479. }
  480. /* Compute the max possible height for reverse mapping btrees. */
  481. unsigned int
  482. xfs_rmapbt_maxlevels_ondisk(void)
  483. {
  484. unsigned int minrecs[2];
  485. unsigned int blocklen;
  486. blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;
  487. minrecs[0] = xfs_rmapbt_block_maxrecs(blocklen, true) / 2;
  488. minrecs[1] = xfs_rmapbt_block_maxrecs(blocklen, false) / 2;
  489. /*
  490. * Compute the asymptotic maxlevels for an rmapbt on any reflink fs.
  491. *
  492. * On a reflink filesystem, each AG block can have up to 2^32 (per the
  493. * refcount record format) owners, which means that theoretically we
  494. * could face up to 2^64 rmap records. However, we're likely to run
  495. * out of blocks in the AG long before that happens, which means that
  496. * we must compute the max height based on what the btree will look
  497. * like if it consumes almost all the blocks in the AG due to maximal
  498. * sharing factor.
  499. */
  500. return xfs_btree_space_to_height(minrecs, XFS_MAX_CRC_AG_BLOCKS);
  501. }
  502. /* Compute the maximum height of an rmap btree. */
  503. void
  504. xfs_rmapbt_compute_maxlevels(
  505. struct xfs_mount *mp)
  506. {
  507. if (!xfs_has_rmapbt(mp)) {
  508. mp->m_rmap_maxlevels = 0;
  509. return;
  510. }
  511. if (xfs_has_reflink(mp)) {
  512. /*
  513. * Compute the asymptotic maxlevels for an rmap btree on a
  514. * filesystem that supports reflink.
  515. *
  516. * On a reflink filesystem, each AG block can have up to 2^32
  517. * (per the refcount record format) owners, which means that
  518. * theoretically we could face up to 2^64 rmap records.
  519. * However, we're likely to run out of blocks in the AG long
  520. * before that happens, which means that we must compute the
  521. * max height based on what the btree will look like if it
  522. * consumes almost all the blocks in the AG due to maximal
  523. * sharing factor.
  524. */
  525. mp->m_rmap_maxlevels = xfs_btree_space_to_height(mp->m_rmap_mnr,
  526. mp->m_sb.sb_agblocks);
  527. } else {
  528. /*
  529. * If there's no block sharing, compute the maximum rmapbt
  530. * height assuming one rmap record per AG block.
  531. */
  532. mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels(
  533. mp->m_rmap_mnr, mp->m_sb.sb_agblocks);
  534. }
  535. ASSERT(mp->m_rmap_maxlevels <= xfs_rmapbt_maxlevels_ondisk());
  536. }
  537. /* Calculate the refcount btree size for some records. */
  538. xfs_extlen_t
  539. xfs_rmapbt_calc_size(
  540. struct xfs_mount *mp,
  541. unsigned long long len)
  542. {
  543. return xfs_btree_calc_size(mp->m_rmap_mnr, len);
  544. }
  545. /*
  546. * Calculate the maximum refcount btree size.
  547. */
  548. xfs_extlen_t
  549. xfs_rmapbt_max_size(
  550. struct xfs_mount *mp,
  551. xfs_agblock_t agblocks)
  552. {
  553. /* Bail out if we're uninitialized, which can happen in mkfs. */
  554. if (mp->m_rmap_mxr[0] == 0)
  555. return 0;
  556. return xfs_rmapbt_calc_size(mp, agblocks);
  557. }
  558. /*
  559. * Figure out how many blocks to reserve and how many are used by this btree.
  560. */
  561. int
  562. xfs_rmapbt_calc_reserves(
  563. struct xfs_mount *mp,
  564. struct xfs_trans *tp,
  565. struct xfs_perag *pag,
  566. xfs_extlen_t *ask,
  567. xfs_extlen_t *used)
  568. {
  569. struct xfs_buf *agbp;
  570. struct xfs_agf *agf;
  571. xfs_agblock_t agblocks;
  572. xfs_extlen_t tree_len;
  573. int error;
  574. if (!xfs_has_rmapbt(mp))
  575. return 0;
  576. error = xfs_alloc_read_agf(pag, tp, 0, &agbp);
  577. if (error)
  578. return error;
  579. agf = agbp->b_addr;
  580. agblocks = be32_to_cpu(agf->agf_length);
  581. tree_len = be32_to_cpu(agf->agf_rmap_blocks);
  582. xfs_trans_brelse(tp, agbp);
  583. /*
  584. * The log is permanently allocated, so the space it occupies will
  585. * never be available for the kinds of things that would require btree
  586. * expansion. We therefore can pretend the space isn't there.
  587. */
  588. if (xfs_ag_contains_log(mp, pag->pag_agno))
  589. agblocks -= mp->m_sb.sb_logblocks;
  590. /* Reserve 1% of the AG or enough for 1 block per record. */
  591. *ask += max(agblocks / 100, xfs_rmapbt_max_size(mp, agblocks));
  592. *used += tree_len;
  593. return error;
  594. }
  595. int __init
  596. xfs_rmapbt_init_cur_cache(void)
  597. {
  598. xfs_rmapbt_cur_cache = kmem_cache_create("xfs_rmapbt_cur",
  599. xfs_btree_cur_sizeof(xfs_rmapbt_maxlevels_ondisk()),
  600. 0, 0, NULL);
  601. if (!xfs_rmapbt_cur_cache)
  602. return -ENOMEM;
  603. return 0;
  604. }
  605. void
  606. xfs_rmapbt_destroy_cur_cache(void)
  607. {
  608. kmem_cache_destroy(xfs_rmapbt_cur_cache);
  609. xfs_rmapbt_cur_cache = NULL;
  610. }