btree.c 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * Copyright (C) 2017 Oracle. All Rights Reserved.
  4. * Author: Darrick J. Wong <[email protected]>
  5. */
  6. #include "xfs.h"
  7. #include "xfs_fs.h"
  8. #include "xfs_shared.h"
  9. #include "xfs_format.h"
  10. #include "xfs_trans_resv.h"
  11. #include "xfs_mount.h"
  12. #include "xfs_inode.h"
  13. #include "xfs_btree.h"
  14. #include "scrub/scrub.h"
  15. #include "scrub/common.h"
  16. #include "scrub/btree.h"
  17. #include "scrub/trace.h"
  18. /* btree scrubbing */
  19. /*
  20. * Check for btree operation errors. See the section about handling
  21. * operational errors in common.c.
  22. */
  23. static bool
  24. __xchk_btree_process_error(
  25. struct xfs_scrub *sc,
  26. struct xfs_btree_cur *cur,
  27. int level,
  28. int *error,
  29. __u32 errflag,
  30. void *ret_ip)
  31. {
  32. if (*error == 0)
  33. return true;
  34. switch (*error) {
  35. case -EDEADLOCK:
  36. /* Used to restart an op with deadlock avoidance. */
  37. trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
  38. break;
  39. case -EFSBADCRC:
  40. case -EFSCORRUPTED:
  41. /* Note the badness but don't abort. */
  42. sc->sm->sm_flags |= errflag;
  43. *error = 0;
  44. fallthrough;
  45. default:
  46. if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
  47. trace_xchk_ifork_btree_op_error(sc, cur, level,
  48. *error, ret_ip);
  49. else
  50. trace_xchk_btree_op_error(sc, cur, level,
  51. *error, ret_ip);
  52. break;
  53. }
  54. return false;
  55. }
  56. bool
  57. xchk_btree_process_error(
  58. struct xfs_scrub *sc,
  59. struct xfs_btree_cur *cur,
  60. int level,
  61. int *error)
  62. {
  63. return __xchk_btree_process_error(sc, cur, level, error,
  64. XFS_SCRUB_OFLAG_CORRUPT, __return_address);
  65. }
  66. bool
  67. xchk_btree_xref_process_error(
  68. struct xfs_scrub *sc,
  69. struct xfs_btree_cur *cur,
  70. int level,
  71. int *error)
  72. {
  73. return __xchk_btree_process_error(sc, cur, level, error,
  74. XFS_SCRUB_OFLAG_XFAIL, __return_address);
  75. }
  76. /* Record btree block corruption. */
  77. static void
  78. __xchk_btree_set_corrupt(
  79. struct xfs_scrub *sc,
  80. struct xfs_btree_cur *cur,
  81. int level,
  82. __u32 errflag,
  83. void *ret_ip)
  84. {
  85. sc->sm->sm_flags |= errflag;
  86. if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
  87. trace_xchk_ifork_btree_error(sc, cur, level,
  88. ret_ip);
  89. else
  90. trace_xchk_btree_error(sc, cur, level,
  91. ret_ip);
  92. }
  93. void
  94. xchk_btree_set_corrupt(
  95. struct xfs_scrub *sc,
  96. struct xfs_btree_cur *cur,
  97. int level)
  98. {
  99. __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
  100. __return_address);
  101. }
  102. void
  103. xchk_btree_xref_set_corrupt(
  104. struct xfs_scrub *sc,
  105. struct xfs_btree_cur *cur,
  106. int level)
  107. {
  108. __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
  109. __return_address);
  110. }
  111. /*
  112. * Make sure this record is in order and doesn't stray outside of the parent
  113. * keys.
  114. */
  115. STATIC void
  116. xchk_btree_rec(
  117. struct xchk_btree *bs)
  118. {
  119. struct xfs_btree_cur *cur = bs->cur;
  120. union xfs_btree_rec *rec;
  121. union xfs_btree_key key;
  122. union xfs_btree_key hkey;
  123. union xfs_btree_key *keyp;
  124. struct xfs_btree_block *block;
  125. struct xfs_btree_block *keyblock;
  126. struct xfs_buf *bp;
  127. block = xfs_btree_get_block(cur, 0, &bp);
  128. rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block);
  129. trace_xchk_btree_rec(bs->sc, cur, 0);
  130. /* If this isn't the first record, are they in order? */
  131. if (cur->bc_levels[0].ptr > 1 &&
  132. !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
  133. xchk_btree_set_corrupt(bs->sc, cur, 0);
  134. memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
  135. if (cur->bc_nlevels == 1)
  136. return;
  137. /* Is this at least as large as the parent low key? */
  138. cur->bc_ops->init_key_from_rec(&key, rec);
  139. keyblock = xfs_btree_get_block(cur, 1, &bp);
  140. keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
  141. if (cur->bc_ops->diff_two_keys(cur, &key, keyp) < 0)
  142. xchk_btree_set_corrupt(bs->sc, cur, 1);
  143. if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
  144. return;
  145. /* Is this no larger than the parent high key? */
  146. cur->bc_ops->init_high_key_from_rec(&hkey, rec);
  147. keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
  148. if (cur->bc_ops->diff_two_keys(cur, keyp, &hkey) < 0)
  149. xchk_btree_set_corrupt(bs->sc, cur, 1);
  150. }
  151. /*
  152. * Make sure this key is in order and doesn't stray outside of the parent
  153. * keys.
  154. */
  155. STATIC void
  156. xchk_btree_key(
  157. struct xchk_btree *bs,
  158. int level)
  159. {
  160. struct xfs_btree_cur *cur = bs->cur;
  161. union xfs_btree_key *key;
  162. union xfs_btree_key *keyp;
  163. struct xfs_btree_block *block;
  164. struct xfs_btree_block *keyblock;
  165. struct xfs_buf *bp;
  166. block = xfs_btree_get_block(cur, level, &bp);
  167. key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);
  168. trace_xchk_btree_key(bs->sc, cur, level);
  169. /* If this isn't the first key, are they in order? */
  170. if (cur->bc_levels[level].ptr > 1 &&
  171. !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1], key))
  172. xchk_btree_set_corrupt(bs->sc, cur, level);
  173. memcpy(&bs->lastkey[level - 1], key, cur->bc_ops->key_len);
  174. if (level + 1 >= cur->bc_nlevels)
  175. return;
  176. /* Is this at least as large as the parent low key? */
  177. keyblock = xfs_btree_get_block(cur, level + 1, &bp);
  178. keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock);
  179. if (cur->bc_ops->diff_two_keys(cur, key, keyp) < 0)
  180. xchk_btree_set_corrupt(bs->sc, cur, level);
  181. if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
  182. return;
  183. /* Is this no larger than the parent high key? */
  184. key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block);
  185. keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
  186. keyblock);
  187. if (cur->bc_ops->diff_two_keys(cur, keyp, key) < 0)
  188. xchk_btree_set_corrupt(bs->sc, cur, level);
  189. }
  190. /*
  191. * Check a btree pointer. Returns true if it's ok to use this pointer.
  192. * Callers do not need to set the corrupt flag.
  193. */
  194. static bool
  195. xchk_btree_ptr_ok(
  196. struct xchk_btree *bs,
  197. int level,
  198. union xfs_btree_ptr *ptr)
  199. {
  200. bool res;
  201. /* A btree rooted in an inode has no block pointer to the root. */
  202. if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
  203. level == bs->cur->bc_nlevels)
  204. return true;
  205. /* Otherwise, check the pointers. */
  206. if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
  207. res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
  208. else
  209. res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
  210. if (!res)
  211. xchk_btree_set_corrupt(bs->sc, bs->cur, level);
  212. return res;
  213. }
  214. /* Check that a btree block's sibling matches what we expect it. */
  215. STATIC int
  216. xchk_btree_block_check_sibling(
  217. struct xchk_btree *bs,
  218. int level,
  219. int direction,
  220. union xfs_btree_ptr *sibling)
  221. {
  222. struct xfs_btree_cur *cur = bs->cur;
  223. struct xfs_btree_block *pblock;
  224. struct xfs_buf *pbp;
  225. struct xfs_btree_cur *ncur = NULL;
  226. union xfs_btree_ptr *pp;
  227. int success;
  228. int error;
  229. error = xfs_btree_dup_cursor(cur, &ncur);
  230. if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
  231. !ncur)
  232. return error;
  233. /*
  234. * If the pointer is null, we shouldn't be able to move the upper
  235. * level pointer anywhere.
  236. */
  237. if (xfs_btree_ptr_is_null(cur, sibling)) {
  238. if (direction > 0)
  239. error = xfs_btree_increment(ncur, level + 1, &success);
  240. else
  241. error = xfs_btree_decrement(ncur, level + 1, &success);
  242. if (error == 0 && success)
  243. xchk_btree_set_corrupt(bs->sc, cur, level);
  244. error = 0;
  245. goto out;
  246. }
  247. /* Increment upper level pointer. */
  248. if (direction > 0)
  249. error = xfs_btree_increment(ncur, level + 1, &success);
  250. else
  251. error = xfs_btree_decrement(ncur, level + 1, &success);
  252. if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
  253. goto out;
  254. if (!success) {
  255. xchk_btree_set_corrupt(bs->sc, cur, level + 1);
  256. goto out;
  257. }
  258. /* Compare upper level pointer to sibling pointer. */
  259. pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
  260. pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock);
  261. if (!xchk_btree_ptr_ok(bs, level + 1, pp))
  262. goto out;
  263. if (pbp)
  264. xchk_buffer_recheck(bs->sc, pbp);
  265. if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
  266. xchk_btree_set_corrupt(bs->sc, cur, level);
  267. out:
  268. xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
  269. return error;
  270. }
  271. /* Check the siblings of a btree block. */
  272. STATIC int
  273. xchk_btree_block_check_siblings(
  274. struct xchk_btree *bs,
  275. struct xfs_btree_block *block)
  276. {
  277. struct xfs_btree_cur *cur = bs->cur;
  278. union xfs_btree_ptr leftsib;
  279. union xfs_btree_ptr rightsib;
  280. int level;
  281. int error = 0;
  282. xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
  283. xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
  284. level = xfs_btree_get_level(block);
  285. /* Root block should never have siblings. */
  286. if (level == cur->bc_nlevels - 1) {
  287. if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
  288. !xfs_btree_ptr_is_null(cur, &rightsib))
  289. xchk_btree_set_corrupt(bs->sc, cur, level);
  290. goto out;
  291. }
  292. /*
  293. * Does the left & right sibling pointers match the adjacent
  294. * parent level pointers?
  295. * (These function absorbs error codes for us.)
  296. */
  297. error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
  298. if (error)
  299. return error;
  300. error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
  301. if (error)
  302. return error;
  303. out:
  304. return error;
  305. }
  306. struct check_owner {
  307. struct list_head list;
  308. xfs_daddr_t daddr;
  309. int level;
  310. };
  311. /*
  312. * Make sure this btree block isn't in the free list and that there's
  313. * an rmap record for it.
  314. */
  315. STATIC int
  316. xchk_btree_check_block_owner(
  317. struct xchk_btree *bs,
  318. int level,
  319. xfs_daddr_t daddr)
  320. {
  321. xfs_agnumber_t agno;
  322. xfs_agblock_t agbno;
  323. xfs_btnum_t btnum;
  324. bool init_sa;
  325. int error = 0;
  326. if (!bs->cur)
  327. return 0;
  328. btnum = bs->cur->bc_btnum;
  329. agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
  330. agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
  331. init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
  332. if (init_sa) {
  333. error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
  334. if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
  335. level, &error))
  336. goto out_free;
  337. }
  338. xchk_xref_is_used_space(bs->sc, agbno, 1);
  339. /*
  340. * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we
  341. * have to nullify it (to shut down further block owner checks) if
  342. * self-xref encounters problems.
  343. */
  344. if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
  345. bs->cur = NULL;
  346. xchk_xref_is_owned_by(bs->sc, agbno, 1, bs->oinfo);
  347. if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
  348. bs->cur = NULL;
  349. out_free:
  350. if (init_sa)
  351. xchk_ag_free(bs->sc, &bs->sc->sa);
  352. return error;
  353. }
  354. /* Check the owner of a btree block. */
  355. STATIC int
  356. xchk_btree_check_owner(
  357. struct xchk_btree *bs,
  358. int level,
  359. struct xfs_buf *bp)
  360. {
  361. struct xfs_btree_cur *cur = bs->cur;
  362. struct check_owner *co;
  363. /*
  364. * In theory, xfs_btree_get_block should only give us a null buffer
  365. * pointer for the root of a root-in-inode btree type, but we need
  366. * to check defensively here in case the cursor state is also screwed
  367. * up.
  368. */
  369. if (bp == NULL) {
  370. if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
  371. xchk_btree_set_corrupt(bs->sc, bs->cur, level);
  372. return 0;
  373. }
  374. /*
  375. * We want to cross-reference each btree block with the bnobt
  376. * and the rmapbt. We cannot cross-reference the bnobt or
  377. * rmapbt while scanning the bnobt or rmapbt, respectively,
  378. * because we cannot alter the cursor and we'd prefer not to
  379. * duplicate cursors. Therefore, save the buffer daddr for
  380. * later scanning.
  381. */
  382. if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
  383. co = kmem_alloc(sizeof(struct check_owner),
  384. KM_MAYFAIL);
  385. if (!co)
  386. return -ENOMEM;
  387. co->level = level;
  388. co->daddr = xfs_buf_daddr(bp);
  389. list_add_tail(&co->list, &bs->to_check);
  390. return 0;
  391. }
  392. return xchk_btree_check_block_owner(bs, level, xfs_buf_daddr(bp));
  393. }
  394. /* Decide if we want to check minrecs of a btree block in the inode root. */
  395. static inline bool
  396. xchk_btree_check_iroot_minrecs(
  397. struct xchk_btree *bs)
  398. {
  399. /*
  400. * xfs_bmap_add_attrfork_btree had an implementation bug wherein it
  401. * would miscalculate the space required for the data fork bmbt root
  402. * when adding an attr fork, and promote the iroot contents to an
  403. * external block unnecessarily. This went unnoticed for many years
  404. * until scrub found filesystems in this state. Inode rooted btrees are
  405. * not supposed to have immediate child blocks that are small enough
  406. * that the contents could fit in the inode root, but we can't fail
  407. * existing filesystems, so instead we disable the check for data fork
  408. * bmap btrees when there's an attr fork.
  409. */
  410. if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
  411. bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
  412. xfs_inode_has_attr_fork(bs->sc->ip))
  413. return false;
  414. return true;
  415. }
  416. /*
  417. * Check that this btree block has at least minrecs records or is one of the
  418. * special blocks that don't require that.
  419. */
  420. STATIC void
  421. xchk_btree_check_minrecs(
  422. struct xchk_btree *bs,
  423. int level,
  424. struct xfs_btree_block *block)
  425. {
  426. struct xfs_btree_cur *cur = bs->cur;
  427. unsigned int root_level = cur->bc_nlevels - 1;
  428. unsigned int numrecs = be16_to_cpu(block->bb_numrecs);
  429. /* More records than minrecs means the block is ok. */
  430. if (numrecs >= cur->bc_ops->get_minrecs(cur, level))
  431. return;
  432. /*
  433. * For btrees rooted in the inode, it's possible that the root block
  434. * contents spilled into a regular ondisk block because there wasn't
  435. * enough space in the inode root. The number of records in that
  436. * child block might be less than the standard minrecs, but that's ok
  437. * provided that there's only one direct child of the root.
  438. */
  439. if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
  440. level == cur->bc_nlevels - 2) {
  441. struct xfs_btree_block *root_block;
  442. struct xfs_buf *root_bp;
  443. int root_maxrecs;
  444. root_block = xfs_btree_get_block(cur, root_level, &root_bp);
  445. root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
  446. if (xchk_btree_check_iroot_minrecs(bs) &&
  447. (be16_to_cpu(root_block->bb_numrecs) != 1 ||
  448. numrecs <= root_maxrecs))
  449. xchk_btree_set_corrupt(bs->sc, cur, level);
  450. return;
  451. }
  452. /*
  453. * Otherwise, only the root level is allowed to have fewer than minrecs
  454. * records or keyptrs.
  455. */
  456. if (level < root_level)
  457. xchk_btree_set_corrupt(bs->sc, cur, level);
  458. }
  459. /*
  460. * Grab and scrub a btree block given a btree pointer. Returns block
  461. * and buffer pointers (if applicable) if they're ok to use.
  462. */
  463. STATIC int
  464. xchk_btree_get_block(
  465. struct xchk_btree *bs,
  466. int level,
  467. union xfs_btree_ptr *pp,
  468. struct xfs_btree_block **pblock,
  469. struct xfs_buf **pbp)
  470. {
  471. xfs_failaddr_t failed_at;
  472. int error;
  473. *pblock = NULL;
  474. *pbp = NULL;
  475. error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
  476. if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
  477. !*pblock)
  478. return error;
  479. xfs_btree_get_block(bs->cur, level, pbp);
  480. if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
  481. failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
  482. level, *pbp);
  483. else
  484. failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
  485. level, *pbp);
  486. if (failed_at) {
  487. xchk_btree_set_corrupt(bs->sc, bs->cur, level);
  488. return 0;
  489. }
  490. if (*pbp)
  491. xchk_buffer_recheck(bs->sc, *pbp);
  492. xchk_btree_check_minrecs(bs, level, *pblock);
  493. /*
  494. * Check the block's owner; this function absorbs error codes
  495. * for us.
  496. */
  497. error = xchk_btree_check_owner(bs, level, *pbp);
  498. if (error)
  499. return error;
  500. /*
  501. * Check the block's siblings; this function absorbs error codes
  502. * for us.
  503. */
  504. return xchk_btree_block_check_siblings(bs, *pblock);
  505. }
  506. /*
  507. * Check that the low and high keys of this block match the keys stored
  508. * in the parent block.
  509. */
  510. STATIC void
  511. xchk_btree_block_keys(
  512. struct xchk_btree *bs,
  513. int level,
  514. struct xfs_btree_block *block)
  515. {
  516. union xfs_btree_key block_keys;
  517. struct xfs_btree_cur *cur = bs->cur;
  518. union xfs_btree_key *high_bk;
  519. union xfs_btree_key *parent_keys;
  520. union xfs_btree_key *high_pk;
  521. struct xfs_btree_block *parent_block;
  522. struct xfs_buf *bp;
  523. if (level >= cur->bc_nlevels - 1)
  524. return;
  525. /* Calculate the keys for this block. */
  526. xfs_btree_get_keys(cur, block, &block_keys);
  527. /* Obtain the parent's copy of the keys for this block. */
  528. parent_block = xfs_btree_get_block(cur, level + 1, &bp);
  529. parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
  530. parent_block);
  531. if (cur->bc_ops->diff_two_keys(cur, &block_keys, parent_keys) != 0)
  532. xchk_btree_set_corrupt(bs->sc, cur, 1);
  533. if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
  534. return;
  535. /* Get high keys */
  536. high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
  537. high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
  538. parent_block);
  539. if (cur->bc_ops->diff_two_keys(cur, high_bk, high_pk) != 0)
  540. xchk_btree_set_corrupt(bs->sc, cur, 1);
  541. }
  542. /*
  543. * Visit all nodes and leaves of a btree. Check that all pointers and
  544. * records are in order, that the keys reflect the records, and use a callback
  545. * so that the caller can verify individual records.
  546. */
  547. int
  548. xchk_btree(
  549. struct xfs_scrub *sc,
  550. struct xfs_btree_cur *cur,
  551. xchk_btree_rec_fn scrub_fn,
  552. const struct xfs_owner_info *oinfo,
  553. void *private)
  554. {
  555. union xfs_btree_ptr ptr;
  556. struct xchk_btree *bs;
  557. union xfs_btree_ptr *pp;
  558. union xfs_btree_rec *recp;
  559. struct xfs_btree_block *block;
  560. struct xfs_buf *bp;
  561. struct check_owner *co;
  562. struct check_owner *n;
  563. size_t cur_sz;
  564. int level;
  565. int error = 0;
  566. /*
  567. * Allocate the btree scrub context from the heap, because this
  568. * structure can get rather large. Don't let a caller feed us a
  569. * totally absurd size.
  570. */
  571. cur_sz = xchk_btree_sizeof(cur->bc_nlevels);
  572. if (cur_sz > PAGE_SIZE) {
  573. xchk_btree_set_corrupt(sc, cur, 0);
  574. return 0;
  575. }
  576. bs = kmem_zalloc(cur_sz, KM_NOFS | KM_MAYFAIL);
  577. if (!bs)
  578. return -ENOMEM;
  579. bs->cur = cur;
  580. bs->scrub_rec = scrub_fn;
  581. bs->oinfo = oinfo;
  582. bs->private = private;
  583. bs->sc = sc;
  584. /* Initialize scrub state */
  585. INIT_LIST_HEAD(&bs->to_check);
  586. /*
  587. * Load the root of the btree. The helper function absorbs
  588. * error codes for us.
  589. */
  590. level = cur->bc_nlevels - 1;
  591. cur->bc_ops->init_ptr_from_cur(cur, &ptr);
  592. if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr))
  593. goto out;
  594. error = xchk_btree_get_block(bs, level, &ptr, &block, &bp);
  595. if (error || !block)
  596. goto out;
  597. cur->bc_levels[level].ptr = 1;
  598. while (level < cur->bc_nlevels) {
  599. block = xfs_btree_get_block(cur, level, &bp);
  600. if (level == 0) {
  601. /* End of leaf, pop back towards the root. */
  602. if (cur->bc_levels[level].ptr >
  603. be16_to_cpu(block->bb_numrecs)) {
  604. xchk_btree_block_keys(bs, level, block);
  605. if (level < cur->bc_nlevels - 1)
  606. cur->bc_levels[level + 1].ptr++;
  607. level++;
  608. continue;
  609. }
  610. /* Records in order for scrub? */
  611. xchk_btree_rec(bs);
  612. /* Call out to the record checker. */
  613. recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,
  614. block);
  615. error = bs->scrub_rec(bs, recp);
  616. if (error)
  617. break;
  618. if (xchk_should_terminate(sc, &error) ||
  619. (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
  620. break;
  621. cur->bc_levels[level].ptr++;
  622. continue;
  623. }
  624. /* End of node, pop back towards the root. */
  625. if (cur->bc_levels[level].ptr >
  626. be16_to_cpu(block->bb_numrecs)) {
  627. xchk_btree_block_keys(bs, level, block);
  628. if (level < cur->bc_nlevels - 1)
  629. cur->bc_levels[level + 1].ptr++;
  630. level++;
  631. continue;
  632. }
  633. /* Keys in order for scrub? */
  634. xchk_btree_key(bs, level);
  635. /* Drill another level deeper. */
  636. pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);
  637. if (!xchk_btree_ptr_ok(bs, level, pp)) {
  638. cur->bc_levels[level].ptr++;
  639. continue;
  640. }
  641. level--;
  642. error = xchk_btree_get_block(bs, level, pp, &block, &bp);
  643. if (error || !block)
  644. goto out;
  645. cur->bc_levels[level].ptr = 1;
  646. }
  647. out:
  648. /* Process deferred owner checks on btree blocks. */
  649. list_for_each_entry_safe(co, n, &bs->to_check, list) {
  650. if (!error && bs->cur)
  651. error = xchk_btree_check_block_owner(bs, co->level,
  652. co->daddr);
  653. list_del(&co->list);
  654. kmem_free(co);
  655. }
  656. kmem_free(bs);
  657. return error;
  658. }