Skip to content

Commit cc3e094

Browse files
djwongdjwong
committed
xfs: scrub the shape of a metadata btree
Create a function that can check the shape of a btree -- each block passes basic inspection and all the pointers look ok. In the next patch we'll add the ability to check the actual keys and records stored within the btree. Add some helper functions so that we report detailed scrub errors in a uniform manner in dmesg. These are helper functions for subsequent patches. Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com> Reviewed-by: Dave Chinner <dchinner@redhat.com>
1 parent 537964b commit cc3e094

File tree

3 files changed

+274
-7
lines changed

3 files changed

+274
-7
lines changed

‎fs/xfs/libxfs/xfs_btree.c

Lines changed: 14 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1053,7 +1053,7 @@ xfs_btree_setbuf(
10531053
}
10541054
}
10551055

1056-
STATIC int
1056+
bool
10571057
xfs_btree_ptr_is_null(
10581058
struct xfs_btree_cur *cur,
10591059
union xfs_btree_ptr *ptr)
@@ -1078,7 +1078,7 @@ xfs_btree_set_ptr_null(
10781078
/*
10791079
* Get/set/init sibling pointers
10801080
*/
1081-
STATIC void
1081+
void
10821082
xfs_btree_get_sibling(
10831083
struct xfs_btree_cur *cur,
10841084
struct xfs_btree_block *block,
@@ -4940,3 +4940,15 @@ xfs_btree_count_blocks(
49404940
return xfs_btree_visit_blocks(cur, xfs_btree_count_blocks_helper,
49414941
blocks);
49424942
}
4943+
4944+
/* Compare two btree pointers. */
4945+
int64_t
4946+
xfs_btree_diff_two_ptrs(
4947+
struct xfs_btree_cur *cur,
4948+
const union xfs_btree_ptr *a,
4949+
const union xfs_btree_ptr *b)
4950+
{
4951+
if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
4952+
return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l);
4953+
return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s);
4954+
}

‎fs/xfs/libxfs/xfs_btree.h

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -534,5 +534,12 @@ int xfs_btree_lookup_get_block(struct xfs_btree_cur *cur, int level,
534534
union xfs_btree_ptr *pp, struct xfs_btree_block **blkp);
535535
struct xfs_btree_block *xfs_btree_get_block(struct xfs_btree_cur *cur,
536536
int level, struct xfs_buf **bpp);
537+
bool xfs_btree_ptr_is_null(struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr);
538+
int64_t xfs_btree_diff_two_ptrs(struct xfs_btree_cur *cur,
539+
const union xfs_btree_ptr *a,
540+
const union xfs_btree_ptr *b);
541+
void xfs_btree_get_sibling(struct xfs_btree_cur *cur,
542+
struct xfs_btree_block *block,
543+
union xfs_btree_ptr *ptr, int lr);
537544

538545
#endif /* __XFS_BTREE_H__ */

‎fs/xfs/scrub/btree.c

Lines changed: 253 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -92,12 +92,180 @@ xfs_scrub_btree_set_corrupt(
9292
__return_address);
9393
}
9494

95+
/*
96+
* Check a btree pointer. Returns true if it's ok to use this pointer.
97+
* Callers do not need to set the corrupt flag.
98+
*/
99+
static bool
100+
xfs_scrub_btree_ptr_ok(
101+
struct xfs_scrub_btree *bs,
102+
int level,
103+
union xfs_btree_ptr *ptr)
104+
{
105+
bool res;
106+
107+
/* A btree rooted in an inode has no block pointer to the root. */
108+
if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
109+
level == bs->cur->bc_nlevels)
110+
return true;
111+
112+
/* Otherwise, check the pointers. */
113+
if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
114+
res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
115+
else
116+
res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
117+
if (!res)
118+
xfs_scrub_btree_set_corrupt(bs->sc, bs->cur, level);
119+
120+
return res;
121+
}
122+
123+
/* Check that a btree block's sibling matches what we expect it. */
124+
STATIC int
125+
xfs_scrub_btree_block_check_sibling(
126+
struct xfs_scrub_btree *bs,
127+
int level,
128+
int direction,
129+
union xfs_btree_ptr *sibling)
130+
{
131+
struct xfs_btree_cur *cur = bs->cur;
132+
struct xfs_btree_block *pblock;
133+
struct xfs_buf *pbp;
134+
struct xfs_btree_cur *ncur = NULL;
135+
union xfs_btree_ptr *pp;
136+
int success;
137+
int error;
138+
139+
error = xfs_btree_dup_cursor(cur, &ncur);
140+
if (!xfs_scrub_btree_process_error(bs->sc, cur, level + 1, &error) ||
141+
!ncur)
142+
return error;
143+
144+
/*
145+
* If the pointer is null, we shouldn't be able to move the upper
146+
* level pointer anywhere.
147+
*/
148+
if (xfs_btree_ptr_is_null(cur, sibling)) {
149+
if (direction > 0)
150+
error = xfs_btree_increment(ncur, level + 1, &success);
151+
else
152+
error = xfs_btree_decrement(ncur, level + 1, &success);
153+
if (error == 0 && success)
154+
xfs_scrub_btree_set_corrupt(bs->sc, cur, level);
155+
error = 0;
156+
goto out;
157+
}
158+
159+
/* Increment upper level pointer. */
160+
if (direction > 0)
161+
error = xfs_btree_increment(ncur, level + 1, &success);
162+
else
163+
error = xfs_btree_decrement(ncur, level + 1, &success);
164+
if (!xfs_scrub_btree_process_error(bs->sc, cur, level + 1, &error))
165+
goto out;
166+
if (!success) {
167+
xfs_scrub_btree_set_corrupt(bs->sc, cur, level + 1);
168+
goto out;
169+
}
170+
171+
/* Compare upper level pointer to sibling pointer. */
172+
pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
173+
pp = xfs_btree_ptr_addr(ncur, ncur->bc_ptrs[level + 1], pblock);
174+
if (!xfs_scrub_btree_ptr_ok(bs, level + 1, pp))
175+
goto out;
176+
177+
if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
178+
xfs_scrub_btree_set_corrupt(bs->sc, cur, level);
179+
out:
180+
xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
181+
return error;
182+
}
183+
184+
/* Check the siblings of a btree block. */
185+
STATIC int
186+
xfs_scrub_btree_block_check_siblings(
187+
struct xfs_scrub_btree *bs,
188+
struct xfs_btree_block *block)
189+
{
190+
struct xfs_btree_cur *cur = bs->cur;
191+
union xfs_btree_ptr leftsib;
192+
union xfs_btree_ptr rightsib;
193+
int level;
194+
int error = 0;
195+
196+
xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
197+
xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
198+
level = xfs_btree_get_level(block);
199+
200+
/* Root block should never have siblings. */
201+
if (level == cur->bc_nlevels - 1) {
202+
if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
203+
!xfs_btree_ptr_is_null(cur, &rightsib))
204+
xfs_scrub_btree_set_corrupt(bs->sc, cur, level);
205+
goto out;
206+
}
207+
208+
/*
209+
* Does the left & right sibling pointers match the adjacent
210+
* parent level pointers?
211+
* (These function absorbs error codes for us.)
212+
*/
213+
error = xfs_scrub_btree_block_check_sibling(bs, level, -1, &leftsib);
214+
if (error)
215+
return error;
216+
error = xfs_scrub_btree_block_check_sibling(bs, level, 1, &rightsib);
217+
if (error)
218+
return error;
219+
out:
220+
return error;
221+
}
222+
223+
/*
224+
* Grab and scrub a btree block given a btree pointer. Returns block
225+
* and buffer pointers (if applicable) if they're ok to use.
226+
*/
227+
STATIC int
228+
xfs_scrub_btree_get_block(
229+
struct xfs_scrub_btree *bs,
230+
int level,
231+
union xfs_btree_ptr *pp,
232+
struct xfs_btree_block **pblock,
233+
struct xfs_buf **pbp)
234+
{
235+
void *failed_at;
236+
int error;
237+
238+
*pblock = NULL;
239+
*pbp = NULL;
240+
241+
error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
242+
if (!xfs_scrub_btree_process_error(bs->sc, bs->cur, level, &error) ||
243+
!pblock)
244+
return error;
245+
246+
xfs_btree_get_block(bs->cur, level, pbp);
247+
if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
248+
failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
249+
level, *pbp);
250+
else
251+
failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
252+
level, *pbp);
253+
if (failed_at) {
254+
xfs_scrub_btree_set_corrupt(bs->sc, bs->cur, level);
255+
return 0;
256+
}
257+
258+
/*
259+
* Check the block's siblings; this function absorbs error codes
260+
* for us.
261+
*/
262+
return xfs_scrub_btree_block_check_siblings(bs, *pblock);
263+
}
264+
95265
/*
96266
* Visit all nodes and leaves of a btree. Check that all pointers and
97267
* records are in order, that the keys reflect the records, and use a callback
98-
* so that the caller can verify individual records. The callback is the same
99-
* as the one for xfs_btree_query_range, so therefore this function also
100-
* returns XFS_BTREE_QUERY_RANGE_ABORT, zero, or a negative error code.
268+
* so that the caller can verify individual records.
101269
*/
102270
int
103271
xfs_scrub_btree(
@@ -107,8 +275,88 @@ xfs_scrub_btree(
107275
struct xfs_owner_info *oinfo,
108276
void *private)
109277
{
110-
int error = -EOPNOTSUPP;
278+
struct xfs_scrub_btree bs = {0};
279+
union xfs_btree_ptr ptr;
280+
union xfs_btree_ptr *pp;
281+
struct xfs_btree_block *block;
282+
int level;
283+
struct xfs_buf *bp;
284+
int i;
285+
int error = 0;
286+
287+
/* Initialize scrub state */
288+
bs.cur = cur;
289+
bs.scrub_rec = scrub_fn;
290+
bs.oinfo = oinfo;
291+
bs.firstrec = true;
292+
bs.private = private;
293+
bs.sc = sc;
294+
for (i = 0; i < XFS_BTREE_MAXLEVELS; i++)
295+
bs.firstkey[i] = true;
296+
INIT_LIST_HEAD(&bs.to_check);
297+
298+
/* Don't try to check a tree with a height we can't handle. */
299+
if (cur->bc_nlevels > XFS_BTREE_MAXLEVELS) {
300+
xfs_scrub_btree_set_corrupt(sc, cur, 0);
301+
goto out;
302+
}
303+
304+
/*
305+
* Load the root of the btree. The helper function absorbs
306+
* error codes for us.
307+
*/
308+
level = cur->bc_nlevels - 1;
309+
cur->bc_ops->init_ptr_from_cur(cur, &ptr);
310+
if (!xfs_scrub_btree_ptr_ok(&bs, cur->bc_nlevels, &ptr))
311+
goto out;
312+
error = xfs_scrub_btree_get_block(&bs, level, &ptr, &block, &bp);
313+
if (error || !block)
314+
goto out;
315+
316+
cur->bc_ptrs[level] = 1;
317+
318+
while (level < cur->bc_nlevels) {
319+
block = xfs_btree_get_block(cur, level, &bp);
320+
321+
if (level == 0) {
322+
/* End of leaf, pop back towards the root. */
323+
if (cur->bc_ptrs[level] >
324+
be16_to_cpu(block->bb_numrecs)) {
325+
if (level < cur->bc_nlevels - 1)
326+
cur->bc_ptrs[level + 1]++;
327+
level++;
328+
continue;
329+
}
330+
331+
if (xfs_scrub_should_terminate(sc, &error))
332+
break;
333+
334+
cur->bc_ptrs[level]++;
335+
continue;
336+
}
337+
338+
/* End of node, pop back towards the root. */
339+
if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
340+
if (level < cur->bc_nlevels - 1)
341+
cur->bc_ptrs[level + 1]++;
342+
level++;
343+
continue;
344+
}
345+
346+
/* Drill another level deeper. */
347+
pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
348+
if (!xfs_scrub_btree_ptr_ok(&bs, level, pp)) {
349+
cur->bc_ptrs[level]++;
350+
continue;
351+
}
352+
level--;
353+
error = xfs_scrub_btree_get_block(&bs, level, pp, &block, &bp);
354+
if (error || !block)
355+
goto out;
356+
357+
cur->bc_ptrs[level] = 1;
358+
}
111359

112-
xfs_scrub_btree_process_error(sc, cur, 0, &error);
360+
out:
113361
return error;
114362
}

0 commit comments

Comments
 (0)