Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 : /*
3 : * Copyright (c) 2000-2002,2005 Silicon Graphics, 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_bit.h"
13 : #include "xfs_mount.h"
14 : #include "xfs_inode.h"
15 : #include "xfs_trans.h"
16 : #include "xfs_buf_item.h"
17 : #include "xfs_btree.h"
18 : #include "xfs_errortag.h"
19 : #include "xfs_error.h"
20 : #include "xfs_trace.h"
21 : #include "xfs_alloc.h"
22 : #include "xfs_log.h"
23 : #include "xfs_btree_staging.h"
24 : #include "xfs_ag.h"
25 : #include "xfs_alloc_btree.h"
26 : #include "xfs_ialloc_btree.h"
27 : #include "xfs_bmap_btree.h"
28 : #include "xfs_rmap_btree.h"
29 : #include "xfs_refcount_btree.h"
30 :
31 : /*
32 : * Btree magic numbers.
33 : */
34 : static const uint32_t xfs_magics[2][XFS_BTNUM_MAX] = {
35 : { XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, 0, XFS_BMAP_MAGIC, XFS_IBT_MAGIC,
36 : XFS_FIBT_MAGIC, 0 },
37 : { XFS_ABTB_CRC_MAGIC, XFS_ABTC_CRC_MAGIC, XFS_RMAP_CRC_MAGIC,
38 : XFS_BMAP_CRC_MAGIC, XFS_IBT_CRC_MAGIC, XFS_FIBT_CRC_MAGIC,
39 : XFS_REFC_CRC_MAGIC }
40 : };
41 :
42 : uint32_t
43 >14211*10^7 : xfs_btree_magic(
44 : int crc,
45 : xfs_btnum_t btnum)
46 : {
47 >14211*10^7 : uint32_t magic = xfs_magics[crc][btnum];
48 :
49 : /* Ensure we asked for crc for crc-only magics. */
50 >14225*10^7 : ASSERT(magic != 0);
51 >14225*10^7 : return magic;
52 : }
53 :
54 : /*
55 : * These sibling pointer checks are optimised for null sibling pointers. This
56 : * happens a lot, and we don't need to byte swap at runtime if the sibling
57 : * pointer is NULL.
58 : *
59 : * These are explicitly marked at inline because the cost of calling them as
60 : * functions instead of inlining them is about 36 bytes extra code per call site
61 : * on x86-64. Yes, gcc-11 fails to inline them, and explicit inlining of these
62 : * two sibling check functions reduces the compiled code size by over 300
63 : * bytes.
64 : */
65 : static inline xfs_failaddr_t
66 897438245 : xfs_btree_check_lblock_siblings(
67 : struct xfs_mount *mp,
68 : struct xfs_btree_cur *cur,
69 : int level,
70 : xfs_fsblock_t fsb,
71 : __be64 dsibling)
72 : {
73 897438245 : xfs_fsblock_t sibling;
74 :
75 897438245 : if (dsibling == cpu_to_be64(NULLFSBLOCK))
76 : return NULL;
77 :
78 479171769 : sibling = be64_to_cpu(dsibling);
79 479171769 : if (sibling == fsb)
80 0 : return __this_address;
81 479171769 : if (level >= 0) {
82 468280626 : if (!xfs_btree_check_lptr(cur, sibling, level + 1))
83 0 : return __this_address;
84 : } else {
85 10892495 : if (!xfs_verify_fsbno(mp, sibling))
86 0 : return __this_address;
87 : }
88 :
89 : return NULL;
90 : }
91 :
92 : static inline xfs_failaddr_t
93 >28396*10^7 : xfs_btree_check_sblock_siblings(
94 : struct xfs_perag *pag,
95 : struct xfs_btree_cur *cur,
96 : int level,
97 : xfs_agblock_t agbno,
98 : __be32 dsibling)
99 : {
100 >28396*10^7 : xfs_agblock_t sibling;
101 :
102 >28396*10^7 : if (dsibling == cpu_to_be32(NULLAGBLOCK))
103 : return NULL;
104 :
105 >20857*10^7 : sibling = be32_to_cpu(dsibling);
106 >20857*10^7 : if (sibling == agbno)
107 0 : return __this_address;
108 >20857*10^7 : if (level >= 0) {
109 >20853*10^7 : if (!xfs_btree_check_sptr(cur, sibling, level + 1))
110 0 : return __this_address;
111 : } else {
112 45227951 : if (!xfs_verify_agbno(pag, sibling))
113 0 : return __this_address;
114 : }
115 : return NULL;
116 : }
117 :
118 : /*
119 : * Check a long btree block header. Return the address of the failing check,
120 : * or NULL if everything is ok.
121 : */
122 : xfs_failaddr_t
123 437774686 : __xfs_btree_check_lblock(
124 : struct xfs_btree_cur *cur,
125 : struct xfs_btree_block *block,
126 : int level,
127 : struct xfs_buf *bp)
128 : {
129 437774686 : struct xfs_mount *mp = cur->bc_mp;
130 437774686 : xfs_btnum_t btnum = cur->bc_btnum;
131 437774686 : int crc = xfs_has_crc(mp);
132 437774686 : xfs_failaddr_t fa;
133 437774686 : xfs_fsblock_t fsb = NULLFSBLOCK;
134 :
135 437774686 : if (crc) {
136 437772138 : if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))
137 0 : return __this_address;
138 875539920 : if (block->bb_u.l.bb_blkno !=
139 437769960 : cpu_to_be64(bp ? xfs_buf_daddr(bp) : XFS_BUF_DADDR_NULL))
140 0 : return __this_address;
141 437769960 : if (block->bb_u.l.bb_pad != cpu_to_be32(0))
142 0 : return __this_address;
143 : }
144 :
145 875545016 : if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum))
146 0 : return __this_address;
147 437772021 : if (be16_to_cpu(block->bb_level) != level)
148 10 : return __this_address;
149 875546359 : if (be16_to_cpu(block->bb_numrecs) >
150 437773711 : cur->bc_ops->get_maxrecs(cur, level))
151 0 : return __this_address;
152 :
153 437772648 : if (bp)
154 413006611 : fsb = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
155 :
156 437774220 : fa = xfs_btree_check_lblock_siblings(mp, cur, level, fsb,
157 : block->bb_u.l.bb_leftsib);
158 437775650 : if (!fa)
159 437776265 : fa = xfs_btree_check_lblock_siblings(mp, cur, level, fsb,
160 : block->bb_u.l.bb_rightsib);
161 : return fa;
162 : }
163 :
164 : /* Check a long btree block header. */
165 : static int
166 432390832 : xfs_btree_check_lblock(
167 : struct xfs_btree_cur *cur,
168 : struct xfs_btree_block *block,
169 : int level,
170 : struct xfs_buf *bp)
171 : {
172 432390832 : struct xfs_mount *mp = cur->bc_mp;
173 432390832 : xfs_failaddr_t fa;
174 :
175 432390832 : fa = __xfs_btree_check_lblock(cur, block, level, bp);
176 864784410 : if (XFS_IS_CORRUPT(mp, fa != NULL) ||
177 432391067 : XFS_TEST_ERROR(false, mp, XFS_ERRTAG_BTREE_CHECK_LBLOCK)) {
178 0 : if (bp)
179 0 : trace_xfs_btree_corrupt(bp, _RET_IP_);
180 0 : return -EFSCORRUPTED;
181 : }
182 : return 0;
183 : }
184 :
185 : /*
186 : * Check a short btree block header. Return the address of the failing check,
187 : * or NULL if everything is ok.
188 : */
189 : xfs_failaddr_t
190 >14172*10^7 : __xfs_btree_check_sblock(
191 : struct xfs_btree_cur *cur,
192 : struct xfs_btree_block *block,
193 : int level,
194 : struct xfs_buf *bp)
195 : {
196 >14172*10^7 : struct xfs_mount *mp = cur->bc_mp;
197 >14172*10^7 : struct xfs_perag *pag = cur->bc_ag.pag;
198 >14172*10^7 : xfs_btnum_t btnum = cur->bc_btnum;
199 >14172*10^7 : int crc = xfs_has_crc(mp);
200 >14172*10^7 : xfs_failaddr_t fa;
201 >14172*10^7 : xfs_agblock_t agbno = NULLAGBLOCK;
202 :
203 >14172*10^7 : if (crc) {
204 >14167*10^7 : if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))
205 0 : return __this_address;
206 >28362*10^7 : if (block->bb_u.s.bb_blkno !=
207 >14181*10^7 : cpu_to_be64(bp ? xfs_buf_daddr(bp) : XFS_BUF_DADDR_NULL))
208 0 : return __this_address;
209 : }
210 :
211 >28374*10^7 : if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum))
212 0 : return __this_address;
213 >14184*10^7 : if (be16_to_cpu(block->bb_level) != level)
214 0 : return __this_address;
215 >28359*10^7 : if (be16_to_cpu(block->bb_numrecs) >
216 >14196*10^7 : cur->bc_ops->get_maxrecs(cur, level))
217 0 : return __this_address;
218 :
219 >14162*10^7 : if (bp)
220 >14162*10^7 : agbno = xfs_daddr_to_agbno(mp, xfs_buf_daddr(bp));
221 :
222 >14187*10^7 : fa = xfs_btree_check_sblock_siblings(pag, cur, level, agbno,
223 : block->bb_u.s.bb_leftsib);
224 >14194*10^7 : if (!fa)
225 >14196*10^7 : fa = xfs_btree_check_sblock_siblings(pag, cur, level, agbno,
226 : block->bb_u.s.bb_rightsib);
227 : return fa;
228 : }
229 :
230 : /* Check a short btree block header. */
231 : STATIC int
232 >14162*10^7 : xfs_btree_check_sblock(
233 : struct xfs_btree_cur *cur,
234 : struct xfs_btree_block *block,
235 : int level,
236 : struct xfs_buf *bp)
237 : {
238 >14162*10^7 : struct xfs_mount *mp = cur->bc_mp;
239 >14162*10^7 : xfs_failaddr_t fa;
240 :
241 >14162*10^7 : fa = __xfs_btree_check_sblock(cur, block, level, bp);
242 >28474*10^7 : if (XFS_IS_CORRUPT(mp, fa != NULL) ||
243 >14206*10^7 : XFS_TEST_ERROR(false, mp, XFS_ERRTAG_BTREE_CHECK_SBLOCK)) {
244 0 : if (bp)
245 0 : trace_xfs_btree_corrupt(bp, _RET_IP_);
246 0 : return -EFSCORRUPTED;
247 : }
248 : return 0;
249 : }
250 :
251 : /*
252 : * Debug routine: check that block header is ok.
253 : */
254 : int
255 >14225*10^7 : xfs_btree_check_block(
256 : struct xfs_btree_cur *cur, /* btree cursor */
257 : struct xfs_btree_block *block, /* generic btree block pointer */
258 : int level, /* level of the btree block */
259 : struct xfs_buf *bp) /* buffer containing block, if any */
260 : {
261 >14225*10^7 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
262 432389929 : return xfs_btree_check_lblock(cur, block, level, bp);
263 : else
264 >14181*10^7 : return xfs_btree_check_sblock(cur, block, level, bp);
265 : }
266 :
267 : /* Check that this long pointer is valid and points within the fs. */
268 : bool
269 4123013 : xfs_btree_check_lptr(
270 : struct xfs_btree_cur *cur,
271 : xfs_fsblock_t fsbno,
272 : int level)
273 : {
274 1126681801 : if (level <= 0)
275 : return false;
276 1126682041 : return xfs_verify_fsbno(cur->bc_mp, fsbno);
277 : }
278 :
279 : /* Check that this short pointer is valid and points within the AG. */
280 : bool
281 19357489 : xfs_btree_check_sptr(
282 : struct xfs_btree_cur *cur,
283 : xfs_agblock_t agbno,
284 : int level)
285 : {
286 >23669*10^7 : if (level <= 0)
287 : return false;
288 >23669*10^7 : return xfs_verify_agbno(cur->bc_ag.pag, agbno);
289 : }
290 :
291 : /*
292 : * Check that a given (indexed) btree pointer at a certain level of a
293 : * btree is valid and doesn't point past where it should.
294 : */
295 : static int
296 28798150576 : xfs_btree_check_ptr(
297 : struct xfs_btree_cur *cur,
298 : const union xfs_btree_ptr *ptr,
299 : int index,
300 : int level)
301 : {
302 28798150576 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
303 1308560190 : if (xfs_btree_check_lptr(cur, be64_to_cpu((&ptr->l)[index]),
304 : level))
305 : return 0;
306 3 : xfs_err(cur->bc_mp,
307 : "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.",
308 : cur->bc_ino.ip->i_ino,
309 : cur->bc_ino.whichfork, cur->bc_btnum,
310 : level, index);
311 : } else {
312 28143871062 : if (xfs_btree_check_sptr(cur, be32_to_cpu((&ptr->s)[index]),
313 : level))
314 : return 0;
315 167023 : xfs_err(cur->bc_mp,
316 : "AG %u: Corrupt btree %d pointer at level %d index %d.",
317 : cur->bc_ag.pag->pag_agno, cur->bc_btnum,
318 : level, index);
319 : }
320 :
321 : return -EFSCORRUPTED;
322 : }
323 :
324 : #ifdef DEBUG
325 : # define xfs_btree_debug_check_ptr xfs_btree_check_ptr
326 : #else
327 : # define xfs_btree_debug_check_ptr(...) (0)
328 : #endif
329 :
330 : /*
331 : * Calculate CRC on the whole btree block and stuff it into the
332 : * long-form btree header.
333 : *
334 : * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
335 : * it into the buffer so recovery knows what the last modification was that made
336 : * it to disk.
337 : */
338 : void
339 2577952 : xfs_btree_lblock_calc_crc(
340 : struct xfs_buf *bp)
341 : {
342 2577952 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
343 2577952 : struct xfs_buf_log_item *bip = bp->b_log_item;
344 :
345 2577952 : if (!xfs_has_crc(bp->b_mount))
346 : return;
347 2577952 : if (bip)
348 2577952 : block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
349 2577952 : xfs_buf_update_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF);
350 : }
351 :
352 : bool
353 4497353 : xfs_btree_lblock_verify_crc(
354 : struct xfs_buf *bp)
355 : {
356 4497353 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
357 4497353 : struct xfs_mount *mp = bp->b_mount;
358 :
359 4497353 : if (xfs_has_crc(mp)) {
360 4497353 : if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn)))
361 : return false;
362 4497353 : return xfs_buf_verify_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF);
363 : }
364 :
365 : return true;
366 : }
367 :
368 : /*
369 : * Calculate CRC on the whole btree block and stuff it into the
370 : * short-form btree header.
371 : *
372 : * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
373 : * it into the buffer so recovery knows what the last modification was that made
374 : * it to disk.
375 : */
376 : void
377 12950044 : xfs_btree_sblock_calc_crc(
378 : struct xfs_buf *bp)
379 : {
380 12950044 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
381 12950044 : struct xfs_buf_log_item *bip = bp->b_log_item;
382 :
383 12950044 : if (!xfs_has_crc(bp->b_mount))
384 : return;
385 12943160 : if (bip)
386 12910712 : block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
387 12943160 : xfs_buf_update_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF);
388 : }
389 :
390 : bool
391 2268015 : xfs_btree_sblock_verify_crc(
392 : struct xfs_buf *bp)
393 : {
394 2268015 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
395 2268015 : struct xfs_mount *mp = bp->b_mount;
396 :
397 2268015 : if (xfs_has_crc(mp)) {
398 2267863 : if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn)))
399 : return false;
400 2267863 : return xfs_buf_verify_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF);
401 : }
402 :
403 : return true;
404 : }
405 :
406 : static int
407 347896 : xfs_btree_free_block(
408 : struct xfs_btree_cur *cur,
409 : struct xfs_buf *bp)
410 : {
411 347896 : int error;
412 :
413 347896 : error = cur->bc_ops->free_block(cur, bp);
414 347896 : if (!error) {
415 347896 : xfs_trans_binval(cur->bc_tp, bp);
416 347896 : XFS_BTREE_STATS_INC(cur, free);
417 : }
418 347896 : return error;
419 : }
420 :
421 : /*
422 : * Delete the btree cursor.
423 : */
424 : void
425 4790329009 : xfs_btree_del_cursor(
426 : struct xfs_btree_cur *cur, /* btree cursor */
427 : int error) /* del because of error */
428 : {
429 4790329009 : int i; /* btree level */
430 :
431 : /*
432 : * Clear the buffer pointers and release the buffers. If we're doing
433 : * this because of an error, inspect all of the entries in the bc_bufs
434 : * array for buffers to be unlocked. This is because some of the btree
435 : * code works from level n down to 0, and if we get an error along the
436 : * way we won't have initialized all the entries down to 0.
437 : */
438 11766229980 : for (i = 0; i < cur->bc_nlevels; i++) {
439 7135107575 : if (cur->bc_levels[i].bp)
440 5831535386 : xfs_trans_brelse(cur->bc_tp, cur->bc_levels[i].bp);
441 1303572189 : else if (!error)
442 : break;
443 : }
444 :
445 : /*
446 : * If we are doing a BMBT update, the number of unaccounted blocks
447 : * allocated during this cursor life time should be zero. If it's not
448 : * zero, then we should be shut down or on our way to shutdown due to
449 : * cancelling a dirty transaction on error.
450 : */
451 4791145821 : ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP || cur->bc_ino.allocated == 0 ||
452 : xfs_is_shutdown(cur->bc_mp) || error != 0);
453 4791145821 : if (unlikely(cur->bc_flags & XFS_BTREE_STAGING))
454 0 : kmem_free(cur->bc_ops);
455 4791145821 : if (!(cur->bc_flags & XFS_BTREE_LONG_PTRS) && cur->bc_ag.pag)
456 4644622315 : xfs_perag_put(cur->bc_ag.pag);
457 4791096041 : kmem_cache_free(cur->bc_cache, cur);
458 4791573859 : }
459 :
460 : /*
461 : * Duplicate the btree cursor.
462 : * Allocate a new one, copy the record, re-get the buffers.
463 : */
464 : int /* error */
465 142040086 : xfs_btree_dup_cursor(
466 : struct xfs_btree_cur *cur, /* input cursor */
467 : struct xfs_btree_cur **ncur) /* output cursor */
468 : {
469 142040086 : struct xfs_buf *bp; /* btree block's buffer pointer */
470 142040086 : int error; /* error return value */
471 142040086 : int i; /* level number of btree block */
472 142040086 : xfs_mount_t *mp; /* mount structure for filesystem */
473 142040086 : struct xfs_btree_cur *new; /* new cursor value */
474 142040086 : xfs_trans_t *tp; /* transaction pointer, can be NULL */
475 :
476 142040086 : tp = cur->bc_tp;
477 142040086 : mp = cur->bc_mp;
478 :
479 : /*
480 : * Allocate a new cursor like the old one.
481 : */
482 142040086 : new = cur->bc_ops->dup_cursor(cur);
483 :
484 : /*
485 : * Copy the record currently in the cursor.
486 : */
487 142043568 : new->bc_rec = cur->bc_rec;
488 :
489 : /*
490 : * For each level current, re-get the buffer and copy the ptr value.
491 : */
492 444680770 : for (i = 0; i < new->bc_nlevels; i++) {
493 302637064 : new->bc_levels[i].ptr = cur->bc_levels[i].ptr;
494 302637064 : new->bc_levels[i].ra = cur->bc_levels[i].ra;
495 302637064 : bp = cur->bc_levels[i].bp;
496 302637064 : if (bp) {
497 261417708 : error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
498 : xfs_buf_daddr(bp), mp->m_bsize,
499 : 0, &bp,
500 261417708 : cur->bc_ops->buf_ops);
501 261417864 : if (error) {
502 18 : xfs_btree_del_cursor(new, error);
503 18 : *ncur = NULL;
504 18 : return error;
505 : }
506 : }
507 302637202 : new->bc_levels[i].bp = bp;
508 : }
509 142043706 : *ncur = new;
510 142043706 : return 0;
511 : }
512 :
513 : /*
514 : * XFS btree block layout and addressing:
515 : *
516 : * There are two types of blocks in the btree: leaf and non-leaf blocks.
517 : *
518 : * The leaf record start with a header then followed by records containing
519 : * the values. A non-leaf block also starts with the same header, and
520 : * then first contains lookup keys followed by an equal number of pointers
521 : * to the btree blocks at the previous level.
522 : *
523 : * +--------+-------+-------+-------+-------+-------+-------+
524 : * Leaf: | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N |
525 : * +--------+-------+-------+-------+-------+-------+-------+
526 : *
527 : * +--------+-------+-------+-------+-------+-------+-------+
528 : * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
529 : * +--------+-------+-------+-------+-------+-------+-------+
530 : *
531 : * The header is called struct xfs_btree_block for reasons better left unknown
532 : * and comes in different versions for short (32bit) and long (64bit) block
533 : * pointers. The record and key structures are defined by the btree instances
534 : * and opaque to the btree core. The block pointers are simple disk endian
535 : * integers, available in a short (32bit) and long (64bit) variant.
536 : *
537 : * The helpers below calculate the offset of a given record, key or pointer
538 : * into a btree block (xfs_btree_*_offset) or return a pointer to the given
539 : * record, key or pointer (xfs_btree_*_addr). Note that all addressing
540 : * inside the btree block is done using indices starting at one, not zero!
541 : *
542 : * If XFS_BTREE_OVERLAPPING is set, then this btree supports keys containing
543 : * overlapping intervals. In such a tree, records are still sorted lowest to
544 : * highest and indexed by the smallest key value that refers to the record.
545 : * However, nodes are different: each pointer has two associated keys -- one
546 : * indexing the lowest key available in the block(s) below (the same behavior
547 : * as the key in a regular btree) and another indexing the highest key
548 : * available in the block(s) below. Because records are /not/ sorted by the
549 : * highest key, all leaf block updates require us to compute the highest key
550 : * that matches any record in the leaf and to recursively update the high keys
551 : * in the nodes going further up in the tree, if necessary. Nodes look like
552 : * this:
553 : *
554 : * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
555 : * Non-Leaf: | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
556 : * +--------+-----+-----+-----+-----+-----+-------+-------+-----+
557 : *
558 : * To perform an interval query on an overlapped tree, perform the usual
559 : * depth-first search and use the low and high keys to decide if we can skip
560 : * that particular node. If a leaf node is reached, return the records that
561 : * intersect the interval. Note that an interval query may return numerous
562 : * entries. For a non-overlapped tree, simply search for the record associated
563 : * with the lowest key and iterate forward until a non-matching record is
564 : * found. Section 14.3 ("Interval Trees") of _Introduction to Algorithms_ by
565 : * Cormen, Leiserson, Rivest, and Stein (2nd or 3rd ed. only) discuss this in
566 : * more detail.
567 : *
568 : * Why do we care about overlapping intervals? Let's say you have a bunch of
569 : * reverse mapping records on a reflink filesystem:
570 : *
571 : * 1: +- file A startblock B offset C length D -----------+
572 : * 2: +- file E startblock F offset G length H --------------+
573 : * 3: +- file I startblock F offset J length K --+
574 : * 4: +- file L... --+
575 : *
576 : * Now say we want to map block (B+D) into file A at offset (C+D). Ideally,
577 : * we'd simply increment the length of record 1. But how do we find the record
578 : * that ends at (B+D-1) (i.e. record 1)? A LE lookup of (B+D-1) would return
579 : * record 3 because the keys are ordered first by startblock. An interval
580 : * query would return records 1 and 2 because they both overlap (B+D-1), and
581 : * from that we can pick out record 1 as the appropriate left neighbor.
582 : *
583 : * In the non-overlapped case you can do a LE lookup and decrement the cursor
584 : * because a record's interval must end before the next record.
585 : */
586 :
587 : /*
588 : * Return size of the btree block header for this btree instance.
589 : */
590 >31929*10^7 : static inline size_t xfs_btree_block_len(struct xfs_btree_cur *cur)
591 : {
592 >31929*10^7 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
593 3134579938 : if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
594 : return XFS_BTREE_LBLOCK_CRC_LEN;
595 0 : return XFS_BTREE_LBLOCK_LEN;
596 : }
597 >31616*10^7 : if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
598 >31617*10^7 : return XFS_BTREE_SBLOCK_CRC_LEN;
599 : return XFS_BTREE_SBLOCK_LEN;
600 : }
601 :
602 : /*
603 : * Return size of btree block pointers for this btree instance.
604 : */
605 : static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur *cur)
606 : {
607 26738684056 : return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
608 26738684056 : sizeof(__be64) : sizeof(__be32);
609 : }
610 :
611 : /*
612 : * Calculate offset of the n-th record in a btree block.
613 : */
614 : STATIC size_t
615 >22538*10^7 : xfs_btree_rec_offset(
616 : struct xfs_btree_cur *cur,
617 : int n)
618 : {
619 >22538*10^7 : return xfs_btree_block_len(cur) +
620 >22538*10^7 : (n - 1) * cur->bc_ops->rec_len;
621 : }
622 :
623 : /*
624 : * Calculate offset of the n-th key in a btree block.
625 : */
626 : STATIC size_t
627 40111296271 : xfs_btree_key_offset(
628 : struct xfs_btree_cur *cur,
629 : int n)
630 : {
631 40111296271 : return xfs_btree_block_len(cur) +
632 40111296271 : (n - 1) * cur->bc_ops->key_len;
633 : }
634 :
635 : /*
636 : * Calculate offset of the n-th high key in a btree block.
637 : */
638 : STATIC size_t
639 28203105290 : xfs_btree_high_key_offset(
640 : struct xfs_btree_cur *cur,
641 : int n)
642 : {
643 28203105290 : return xfs_btree_block_len(cur) +
644 28203105290 : (n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2);
645 : }
646 :
647 : /*
648 : * Calculate offset of the n-th block pointer in a btree block.
649 : */
650 : STATIC size_t
651 26732901385 : xfs_btree_ptr_offset(
652 : struct xfs_btree_cur *cur,
653 : int n,
654 : int level)
655 : {
656 26732901385 : return xfs_btree_block_len(cur) +
657 53469483370 : cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
658 53236498622 : (n - 1) * xfs_btree_ptr_len(cur);
659 : }
660 :
661 : /*
662 : * Return a pointer to the n-th record in the btree block.
663 : */
664 : union xfs_btree_rec *
665 2183480106 : xfs_btree_rec_addr(
666 : struct xfs_btree_cur *cur,
667 : int n,
668 : struct xfs_btree_block *block)
669 : {
670 >22287*10^7 : return (union xfs_btree_rec *)
671 >22287*10^7 : ((char *)block + xfs_btree_rec_offset(cur, n));
672 : }
673 :
674 : /*
675 : * Return a pointer to the n-th key in the btree block.
676 : */
677 : union xfs_btree_key *
678 2181238085 : xfs_btree_key_addr(
679 : struct xfs_btree_cur *cur,
680 : int n,
681 : struct xfs_btree_block *block)
682 : {
683 39910895223 : return (union xfs_btree_key *)
684 39910895223 : ((char *)block + xfs_btree_key_offset(cur, n));
685 : }
686 :
687 : /*
688 : * Return a pointer to the n-th high key in the btree block.
689 : */
690 : union xfs_btree_key *
691 1699805309 : xfs_btree_high_key_addr(
692 : struct xfs_btree_cur *cur,
693 : int n,
694 : struct xfs_btree_block *block)
695 : {
696 28211606711 : return (union xfs_btree_key *)
697 28211606711 : ((char *)block + xfs_btree_high_key_offset(cur, n));
698 : }
699 :
700 : /*
701 : * Return a pointer to the n-th block pointer in the btree block.
702 : */
703 : union xfs_btree_ptr *
704 26728816609 : xfs_btree_ptr_addr(
705 : struct xfs_btree_cur *cur,
706 : int n,
707 : struct xfs_btree_block *block)
708 : {
709 26728816609 : int level = xfs_btree_get_level(block);
710 :
711 26728816609 : ASSERT(block->bb_level != 0);
712 :
713 53459996638 : return (union xfs_btree_ptr *)
714 26728816609 : ((char *)block + xfs_btree_ptr_offset(cur, n, level));
715 : }
716 :
717 : struct xfs_ifork *
718 267043355 : xfs_btree_ifork_ptr(
719 : struct xfs_btree_cur *cur)
720 : {
721 267043355 : ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
722 :
723 267043355 : if (cur->bc_flags & XFS_BTREE_STAGING)
724 0 : return cur->bc_ino.ifake->if_fork;
725 267043355 : return xfs_ifork_ptr(cur->bc_ino.ip, cur->bc_ino.whichfork);
726 : }
727 :
728 : /*
729 : * Get the root block which is stored in the inode.
730 : *
731 : * For now this btree implementation assumes the btree root is always
732 : * stored in the if_broot field of an inode fork.
733 : */
734 : STATIC struct xfs_btree_block *
735 267040742 : xfs_btree_get_iroot(
736 : struct xfs_btree_cur *cur)
737 : {
738 267040742 : struct xfs_ifork *ifp = xfs_btree_ifork_ptr(cur);
739 :
740 267045551 : return (struct xfs_btree_block *)ifp->if_broot;
741 : }
742 :
743 : /*
744 : * Retrieve the block pointer from the cursor at the given level.
745 : * This may be an inode btree root or from a buffer.
746 : */
747 : struct xfs_btree_block * /* generic btree block pointer */
748 >21831*10^7 : xfs_btree_get_block(
749 : struct xfs_btree_cur *cur, /* btree cursor */
750 : int level, /* level in btree */
751 : struct xfs_buf **bpp) /* buffer containing the block */
752 : {
753 >21831*10^7 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
754 1128997019 : (level == cur->bc_nlevels - 1)) {
755 144034564 : *bpp = NULL;
756 144034564 : return xfs_btree_get_iroot(cur);
757 : }
758 :
759 >21816*10^7 : *bpp = cur->bc_levels[level].bp;
760 >21816*10^7 : return XFS_BUF_TO_BLOCK(*bpp);
761 : }
762 :
763 : /*
764 : * Change the cursor to point to the first record at the given level.
765 : * Other levels are unaffected.
766 : */
767 : STATIC int /* success=1, failure=0 */
768 60590049 : xfs_btree_firstrec(
769 : struct xfs_btree_cur *cur, /* btree cursor */
770 : int level) /* level to change */
771 : {
772 60590049 : struct xfs_btree_block *block; /* generic btree block pointer */
773 60590049 : struct xfs_buf *bp; /* buffer containing block */
774 :
775 : /*
776 : * Get the block pointer for this level.
777 : */
778 60590049 : block = xfs_btree_get_block(cur, level, &bp);
779 60590064 : if (xfs_btree_check_block(cur, block, level, bp))
780 : return 0;
781 : /*
782 : * It's empty, there is no such record.
783 : */
784 60590120 : if (!block->bb_numrecs)
785 : return 0;
786 : /*
787 : * Set the ptr value to 1, that's the first record/key.
788 : */
789 60590120 : cur->bc_levels[level].ptr = 1;
790 60590120 : return 1;
791 : }
792 :
793 : /*
794 : * Change the cursor to point to the last record in the current block
795 : * at the given level. Other levels are unaffected.
796 : */
797 : STATIC int /* success=1, failure=0 */
798 60671608 : xfs_btree_lastrec(
799 : struct xfs_btree_cur *cur, /* btree cursor */
800 : int level) /* level to change */
801 : {
802 60671608 : struct xfs_btree_block *block; /* generic btree block pointer */
803 60671608 : struct xfs_buf *bp; /* buffer containing block */
804 :
805 : /*
806 : * Get the block pointer for this level.
807 : */
808 60671608 : block = xfs_btree_get_block(cur, level, &bp);
809 60671899 : if (xfs_btree_check_block(cur, block, level, bp))
810 : return 0;
811 : /*
812 : * It's empty, there is no such record.
813 : */
814 60672502 : if (!block->bb_numrecs)
815 : return 0;
816 : /*
817 : * Set the ptr value to numrecs, that's the last record/key.
818 : */
819 60672502 : cur->bc_levels[level].ptr = be16_to_cpu(block->bb_numrecs);
820 60672502 : return 1;
821 : }
822 :
823 : /*
824 : * Compute first and last byte offsets for the fields given.
825 : * Interprets the offsets table, which contains struct field offsets.
826 : */
827 : void
828 958749944 : xfs_btree_offsets(
829 : uint32_t fields, /* bitmask of fields */
830 : const short *offsets, /* table of field offsets */
831 : int nbits, /* number of bits to inspect */
832 : int *first, /* output: first byte offset */
833 : int *last) /* output: last byte offset */
834 : {
835 958749944 : int i; /* current bit number */
836 958749944 : uint32_t imask; /* mask for current bit number */
837 :
838 958749944 : ASSERT(fields != 0);
839 : /*
840 : * Find the lowest bit, so the first byte offset.
841 : */
842 4065703287 : for (i = 0, imask = 1u; ; i++, imask <<= 1) {
843 4065703287 : if (imask & fields) {
844 958749944 : *first = offsets[i];
845 958749944 : break;
846 : }
847 : }
848 : /*
849 : * Find the highest bit, so the last byte offset.
850 : */
851 958749944 : for (i = nbits - 1, imask = 1u << i; ; i--, imask >>= 1) {
852 6654769884 : if (imask & fields) {
853 958749944 : *last = offsets[i + 1] - 1;
854 958749944 : break;
855 : }
856 : }
857 958749944 : }
858 :
859 : /*
860 : * Get a buffer for the block, return it read in.
861 : * Long-form addressing.
862 : */
863 : int
864 393359993 : xfs_btree_read_bufl(
865 : struct xfs_mount *mp, /* file system mount point */
866 : struct xfs_trans *tp, /* transaction pointer */
867 : xfs_fsblock_t fsbno, /* file system block number */
868 : struct xfs_buf **bpp, /* buffer for fsbno */
869 : int refval, /* ref count value for buffer */
870 : const struct xfs_buf_ops *ops)
871 : {
872 393359993 : struct xfs_buf *bp; /* return value */
873 393359993 : xfs_daddr_t d; /* real disk block address */
874 393359993 : int error;
875 :
876 393359993 : if (!xfs_verify_fsbno(mp, fsbno))
877 : return -EFSCORRUPTED;
878 393360808 : d = XFS_FSB_TO_DADDR(mp, fsbno);
879 393360815 : error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
880 : mp->m_bsize, 0, &bp, ops);
881 393361342 : if (error)
882 : return error;
883 393361273 : if (bp)
884 393361273 : xfs_buf_set_ref(bp, refval);
885 393361271 : *bpp = bp;
886 393361271 : return 0;
887 : }
888 :
889 : /*
890 : * Read-ahead the block, don't wait for it, don't return a buffer.
891 : * Long-form addressing.
892 : */
893 : /* ARGSUSED */
894 : void
895 40147597 : xfs_btree_reada_bufl(
896 : struct xfs_mount *mp, /* file system mount point */
897 : xfs_fsblock_t fsbno, /* file system block number */
898 : xfs_extlen_t count, /* count of filesystem blocks */
899 : const struct xfs_buf_ops *ops)
900 : {
901 40147597 : xfs_daddr_t d;
902 :
903 40147597 : ASSERT(fsbno != NULLFSBLOCK);
904 40147597 : d = XFS_FSB_TO_DADDR(mp, fsbno);
905 40147601 : xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
906 40147601 : }
907 :
908 : /*
909 : * Read-ahead the block, don't wait for it, don't return a buffer.
910 : * Short-form addressing.
911 : */
912 : /* ARGSUSED */
913 : void
914 3408702961 : xfs_btree_reada_bufs(
915 : struct xfs_mount *mp, /* file system mount point */
916 : xfs_agnumber_t agno, /* allocation group number */
917 : xfs_agblock_t agbno, /* allocation group block number */
918 : xfs_extlen_t count, /* count of filesystem blocks */
919 : const struct xfs_buf_ops *ops)
920 : {
921 3408702961 : xfs_daddr_t d;
922 :
923 3408702961 : ASSERT(agno != NULLAGNUMBER);
924 3408702961 : ASSERT(agbno != NULLAGBLOCK);
925 3408702961 : d = XFS_AGB_TO_DADDR(mp, agno, agbno);
926 3408702961 : xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
927 3410166694 : }
928 :
929 : STATIC int
930 40147659 : xfs_btree_readahead_lblock(
931 : struct xfs_btree_cur *cur,
932 : int lr,
933 : struct xfs_btree_block *block)
934 : {
935 40147659 : int rval = 0;
936 40147659 : xfs_fsblock_t left = be64_to_cpu(block->bb_u.l.bb_leftsib);
937 40147659 : xfs_fsblock_t right = be64_to_cpu(block->bb_u.l.bb_rightsib);
938 :
939 40147659 : if ((lr & XFS_BTCUR_LEFTRA) && left != NULLFSBLOCK) {
940 17579676 : xfs_btree_reada_bufl(cur->bc_mp, left, 1,
941 17579676 : cur->bc_ops->buf_ops);
942 17579676 : rval++;
943 : }
944 :
945 40147660 : if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLFSBLOCK) {
946 22567923 : xfs_btree_reada_bufl(cur->bc_mp, right, 1,
947 22567923 : cur->bc_ops->buf_ops);
948 22567925 : rval++;
949 : }
950 :
951 40147662 : return rval;
952 : }
953 :
954 : STATIC int
955 1050969802 : xfs_btree_readahead_sblock(
956 : struct xfs_btree_cur *cur,
957 : int lr,
958 : struct xfs_btree_block *block)
959 : {
960 1050969802 : int rval = 0;
961 1050969802 : xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib);
962 1050969802 : xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib);
963 :
964 :
965 1050969802 : if ((lr & XFS_BTCUR_LEFTRA) && left != NULLAGBLOCK) {
966 54042945 : xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno,
967 54042945 : left, 1, cur->bc_ops->buf_ops);
968 54042945 : rval++;
969 : }
970 :
971 1050970012 : if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLAGBLOCK) {
972 996940941 : xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno,
973 996940941 : right, 1, cur->bc_ops->buf_ops);
974 997013514 : rval++;
975 : }
976 :
977 1051042585 : return rval;
978 : }
979 :
980 : /*
981 : * Read-ahead btree blocks, at the given level.
982 : * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
983 : */
984 : STATIC int
985 68764551661 : xfs_btree_readahead(
986 : struct xfs_btree_cur *cur, /* btree cursor */
987 : int lev, /* level in btree */
988 : int lr) /* left/right bits */
989 : {
990 68764551661 : struct xfs_btree_block *block;
991 :
992 : /*
993 : * No readahead needed if we are at the root level and the
994 : * btree root is stored in the inode.
995 : */
996 68764551661 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
997 57138695 : (lev == cur->bc_nlevels - 1))
998 : return 0;
999 :
1000 68757085834 : if ((cur->bc_levels[lev].ra | lr) == cur->bc_levels[lev].ra)
1001 : return 0;
1002 :
1003 1091128536 : cur->bc_levels[lev].ra |= lr;
1004 1091128536 : block = XFS_BUF_TO_BLOCK(cur->bc_levels[lev].bp);
1005 :
1006 1091128536 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1007 40147606 : return xfs_btree_readahead_lblock(cur, lr, block);
1008 1050980930 : return xfs_btree_readahead_sblock(cur, lr, block);
1009 : }
1010 :
1011 : STATIC int
1012 24218672125 : xfs_btree_ptr_to_daddr(
1013 : struct xfs_btree_cur *cur,
1014 : const union xfs_btree_ptr *ptr,
1015 : xfs_daddr_t *daddr)
1016 : {
1017 24218672125 : xfs_fsblock_t fsbno;
1018 24218672125 : xfs_agblock_t agbno;
1019 24218672125 : int error;
1020 :
1021 24218672125 : error = xfs_btree_check_ptr(cur, ptr, 0, 1);
1022 24228798304 : if (error)
1023 : return error;
1024 :
1025 24228798304 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1026 456165230 : fsbno = be64_to_cpu(ptr->l);
1027 456165230 : *daddr = XFS_FSB_TO_DADDR(cur->bc_mp, fsbno);
1028 : } else {
1029 23772633074 : agbno = be32_to_cpu(ptr->s);
1030 23772633074 : *daddr = XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_ag.pag->pag_agno,
1031 : agbno);
1032 : }
1033 :
1034 : return 0;
1035 : }
1036 :
1037 : /*
1038 : * Readahead @count btree blocks at the given @ptr location.
1039 : *
1040 : * We don't need to care about long or short form btrees here as we have a
1041 : * method of converting the ptr directly to a daddr available to us.
1042 : */
1043 : STATIC void
1044 4238956 : xfs_btree_readahead_ptr(
1045 : struct xfs_btree_cur *cur,
1046 : union xfs_btree_ptr *ptr,
1047 : xfs_extlen_t count)
1048 : {
1049 4238956 : xfs_daddr_t daddr;
1050 :
1051 4238956 : if (xfs_btree_ptr_to_daddr(cur, ptr, &daddr))
1052 0 : return;
1053 4238957 : xfs_buf_readahead(cur->bc_mp->m_ddev_targp, daddr,
1054 4238957 : cur->bc_mp->m_bsize * count, cur->bc_ops->buf_ops);
1055 : }
1056 :
1057 : /*
1058 : * Set the buffer for level "lev" in the cursor to bp, releasing
1059 : * any previous buffer.
1060 : */
1061 : STATIC void
1062 6356317165 : xfs_btree_setbuf(
1063 : struct xfs_btree_cur *cur, /* btree cursor */
1064 : int lev, /* level in btree */
1065 : struct xfs_buf *bp) /* new buffer to set */
1066 : {
1067 6356317165 : struct xfs_btree_block *b; /* btree block */
1068 :
1069 6356317165 : if (cur->bc_levels[lev].bp)
1070 784374850 : xfs_trans_brelse(cur->bc_tp, cur->bc_levels[lev].bp);
1071 6354121543 : cur->bc_levels[lev].bp = bp;
1072 6354121543 : cur->bc_levels[lev].ra = 0;
1073 :
1074 6354121543 : b = XFS_BUF_TO_BLOCK(bp);
1075 6354121543 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1076 207448413 : if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK))
1077 64570236 : cur->bc_levels[lev].ra |= XFS_BTCUR_LEFTRA;
1078 207448413 : if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK))
1079 163217169 : cur->bc_levels[lev].ra |= XFS_BTCUR_RIGHTRA;
1080 : } else {
1081 6146673130 : if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK))
1082 4261032181 : cur->bc_levels[lev].ra |= XFS_BTCUR_LEFTRA;
1083 6146673130 : if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK))
1084 4231686510 : cur->bc_levels[lev].ra |= XFS_BTCUR_RIGHTRA;
1085 : }
1086 6354121543 : }
1087 :
1088 : bool
1089 29491332 : xfs_btree_ptr_is_null(
1090 : struct xfs_btree_cur *cur,
1091 : const union xfs_btree_ptr *ptr)
1092 : {
1093 100017919 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1094 357492351 : return ptr->l == cpu_to_be64(NULLFSBLOCK);
1095 : else
1096 3005923590 : return ptr->s == cpu_to_be32(NULLAGBLOCK);
1097 : }
1098 :
1099 : void
1100 0 : xfs_btree_set_ptr_null(
1101 : struct xfs_btree_cur *cur,
1102 : union xfs_btree_ptr *ptr)
1103 : {
1104 0 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1105 117362386 : ptr->l = cpu_to_be64(NULLFSBLOCK);
1106 : else
1107 528237231 : ptr->s = cpu_to_be32(NULLAGBLOCK);
1108 0 : }
1109 :
1110 : /*
1111 : * Get/set/init sibling pointers
1112 : */
1113 : void
1114 2960275373 : xfs_btree_get_sibling(
1115 : struct xfs_btree_cur *cur,
1116 : struct xfs_btree_block *block,
1117 : union xfs_btree_ptr *ptr,
1118 : int lr)
1119 : {
1120 2960275373 : ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
1121 :
1122 2960275373 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1123 238238652 : if (lr == XFS_BB_RIGHTSIB)
1124 167591271 : ptr->l = block->bb_u.l.bb_rightsib;
1125 : else
1126 70647381 : ptr->l = block->bb_u.l.bb_leftsib;
1127 : } else {
1128 2722036721 : if (lr == XFS_BB_RIGHTSIB)
1129 2633585119 : ptr->s = block->bb_u.s.bb_rightsib;
1130 : else
1131 88451602 : ptr->s = block->bb_u.s.bb_leftsib;
1132 : }
1133 2960275373 : }
1134 :
1135 : void
1136 2613997 : xfs_btree_set_sibling(
1137 : struct xfs_btree_cur *cur,
1138 : struct xfs_btree_block *block,
1139 : const union xfs_btree_ptr *ptr,
1140 : int lr)
1141 : {
1142 2613997 : ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
1143 :
1144 2613997 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1145 764732 : if (lr == XFS_BB_RIGHTSIB)
1146 547753 : block->bb_u.l.bb_rightsib = ptr->l;
1147 : else
1148 216979 : block->bb_u.l.bb_leftsib = ptr->l;
1149 : } else {
1150 1849265 : if (lr == XFS_BB_RIGHTSIB)
1151 995851 : block->bb_u.s.bb_rightsib = ptr->s;
1152 : else
1153 853414 : block->bb_u.s.bb_leftsib = ptr->s;
1154 : }
1155 2613997 : }
1156 :
1157 : void
1158 4930133 : xfs_btree_init_block_int(
1159 : struct xfs_mount *mp,
1160 : struct xfs_btree_block *buf,
1161 : xfs_daddr_t blkno,
1162 : xfs_btnum_t btnum,
1163 : __u16 level,
1164 : __u16 numrecs,
1165 : __u64 owner,
1166 : unsigned int flags)
1167 : {
1168 4930133 : int crc = xfs_has_crc(mp);
1169 4930133 : __u32 magic = xfs_btree_magic(crc, btnum);
1170 :
1171 4930133 : buf->bb_magic = cpu_to_be32(magic);
1172 4930133 : buf->bb_level = cpu_to_be16(level);
1173 4930133 : buf->bb_numrecs = cpu_to_be16(numrecs);
1174 :
1175 4930133 : if (flags & XFS_BTREE_LONG_PTRS) {
1176 4474551 : buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK);
1177 4474551 : buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK);
1178 4474551 : if (crc) {
1179 4474551 : buf->bb_u.l.bb_blkno = cpu_to_be64(blkno);
1180 4474551 : buf->bb_u.l.bb_owner = cpu_to_be64(owner);
1181 4474551 : uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid);
1182 4474550 : buf->bb_u.l.bb_pad = 0;
1183 4474550 : buf->bb_u.l.bb_lsn = 0;
1184 : }
1185 : } else {
1186 : /* owner is a 32 bit value on short blocks */
1187 455582 : __u32 __owner = (__u32)owner;
1188 :
1189 455582 : buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK);
1190 455582 : buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK);
1191 455582 : if (crc) {
1192 448736 : buf->bb_u.s.bb_blkno = cpu_to_be64(blkno);
1193 448736 : buf->bb_u.s.bb_owner = cpu_to_be32(__owner);
1194 448736 : uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid);
1195 448736 : buf->bb_u.s.bb_lsn = 0;
1196 : }
1197 : }
1198 4930132 : }
1199 :
1200 : void
1201 39294 : xfs_btree_init_block(
1202 : struct xfs_mount *mp,
1203 : struct xfs_buf *bp,
1204 : xfs_btnum_t btnum,
1205 : __u16 level,
1206 : __u16 numrecs,
1207 : __u64 owner)
1208 : {
1209 39294 : xfs_btree_init_block_int(mp, XFS_BUF_TO_BLOCK(bp), xfs_buf_daddr(bp),
1210 : btnum, level, numrecs, owner, 0);
1211 39294 : }
1212 :
1213 : void
1214 621153 : xfs_btree_init_block_cur(
1215 : struct xfs_btree_cur *cur,
1216 : struct xfs_buf *bp,
1217 : int level,
1218 : int numrecs)
1219 : {
1220 621153 : __u64 owner;
1221 :
1222 : /*
1223 : * we can pull the owner from the cursor right now as the different
1224 : * owners align directly with the pointer size of the btree. This may
1225 : * change in future, but is safe for current users of the generic btree
1226 : * code.
1227 : */
1228 621153 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1229 204865 : owner = cur->bc_ino.ip->i_ino;
1230 : else
1231 416288 : owner = cur->bc_ag.pag->pag_agno;
1232 :
1233 621153 : xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp),
1234 : xfs_buf_daddr(bp), cur->bc_btnum, level,
1235 : numrecs, owner, cur->bc_flags);
1236 621153 : }
1237 :
1238 : /*
1239 : * Return true if ptr is the last record in the btree and
1240 : * we need to track updates to this record. The decision
1241 : * will be further refined in the update_lastrec method.
1242 : */
1243 : STATIC int
1244 897708308 : xfs_btree_is_lastrec(
1245 : struct xfs_btree_cur *cur,
1246 : struct xfs_btree_block *block,
1247 : int level)
1248 : {
1249 897708308 : union xfs_btree_ptr ptr;
1250 :
1251 897708308 : if (level > 0)
1252 : return 0;
1253 896786134 : if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE))
1254 : return 0;
1255 :
1256 145835732 : xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1257 291670300 : if (!xfs_btree_ptr_is_null(cur, &ptr))
1258 11823275 : return 0;
1259 : return 1;
1260 : }
1261 :
1262 : STATIC void
1263 621157 : xfs_btree_buf_to_ptr(
1264 : struct xfs_btree_cur *cur,
1265 : struct xfs_buf *bp,
1266 : union xfs_btree_ptr *ptr)
1267 : {
1268 621157 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1269 204869 : ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp,
1270 : xfs_buf_daddr(bp)));
1271 : else {
1272 416288 : ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp,
1273 : xfs_buf_daddr(bp)));
1274 : }
1275 621157 : }
1276 :
1277 : STATIC void
1278 6457803981 : xfs_btree_set_refs(
1279 : struct xfs_btree_cur *cur,
1280 : struct xfs_buf *bp)
1281 : {
1282 6457803981 : switch (cur->bc_btnum) {
1283 1065701989 : case XFS_BTNUM_BNO:
1284 : case XFS_BTNUM_CNT:
1285 1065701989 : xfs_buf_set_ref(bp, XFS_ALLOC_BTREE_REF);
1286 1065701989 : break;
1287 2360374295 : case XFS_BTNUM_INO:
1288 : case XFS_BTNUM_FINO:
1289 2360374295 : xfs_buf_set_ref(bp, XFS_INO_BTREE_REF);
1290 2360374295 : break;
1291 251636310 : case XFS_BTNUM_BMAP:
1292 251636310 : xfs_buf_set_ref(bp, XFS_BMAP_BTREE_REF);
1293 251636310 : break;
1294 1780998566 : case XFS_BTNUM_RMAP:
1295 1780998566 : xfs_buf_set_ref(bp, XFS_RMAP_BTREE_REF);
1296 1780998566 : break;
1297 999092821 : case XFS_BTNUM_REFC:
1298 999092821 : xfs_buf_set_ref(bp, XFS_REFC_BTREE_REF);
1299 999092821 : break;
1300 0 : default:
1301 0 : ASSERT(0);
1302 : }
1303 6457924205 : }
1304 :
1305 : int
1306 623353 : xfs_btree_get_buf_block(
1307 : struct xfs_btree_cur *cur,
1308 : const union xfs_btree_ptr *ptr,
1309 : struct xfs_btree_block **block,
1310 : struct xfs_buf **bpp)
1311 : {
1312 623353 : struct xfs_mount *mp = cur->bc_mp;
1313 623353 : xfs_daddr_t d;
1314 623353 : int error;
1315 :
1316 623353 : error = xfs_btree_ptr_to_daddr(cur, ptr, &d);
1317 623353 : if (error)
1318 : return error;
1319 623353 : error = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d, mp->m_bsize,
1320 : 0, bpp);
1321 623353 : if (error)
1322 : return error;
1323 :
1324 623353 : (*bpp)->b_ops = cur->bc_ops->buf_ops;
1325 623353 : *block = XFS_BUF_TO_BLOCK(*bpp);
1326 623353 : return 0;
1327 : }
1328 :
1329 : /*
1330 : * Read in the buffer at the given ptr and return the buffer and
1331 : * the block pointer within the buffer.
1332 : */
1333 : STATIC int
1334 6454678041 : xfs_btree_read_buf_block(
1335 : struct xfs_btree_cur *cur,
1336 : const union xfs_btree_ptr *ptr,
1337 : int flags,
1338 : struct xfs_btree_block **block,
1339 : struct xfs_buf **bpp)
1340 : {
1341 6454678041 : struct xfs_mount *mp = cur->bc_mp;
1342 6454678041 : xfs_daddr_t d;
1343 6454678041 : int error;
1344 :
1345 : /* need to sort out how callers deal with failures first */
1346 6454678041 : ASSERT(!(flags & XBF_TRYLOCK));
1347 :
1348 6454678041 : error = xfs_btree_ptr_to_daddr(cur, ptr, &d);
1349 6455676844 : if (error)
1350 : return error;
1351 6454824844 : error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d,
1352 : mp->m_bsize, flags, bpp,
1353 6454824844 : cur->bc_ops->buf_ops);
1354 6457157623 : if (error)
1355 : return error;
1356 :
1357 6457156885 : xfs_btree_set_refs(cur, *bpp);
1358 6457334009 : *block = XFS_BUF_TO_BLOCK(*bpp);
1359 6457334009 : return 0;
1360 : }
1361 :
1362 : /*
1363 : * Copy keys from one btree block to another.
1364 : */
1365 : void
1366 144347854 : xfs_btree_copy_keys(
1367 : struct xfs_btree_cur *cur,
1368 : union xfs_btree_key *dst_key,
1369 : const union xfs_btree_key *src_key,
1370 : int numkeys)
1371 : {
1372 144347854 : ASSERT(numkeys >= 0);
1373 288695708 : memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len);
1374 144347854 : }
1375 :
1376 : /*
1377 : * Copy records from one btree block to another.
1378 : */
1379 : STATIC void
1380 738587745 : xfs_btree_copy_recs(
1381 : struct xfs_btree_cur *cur,
1382 : union xfs_btree_rec *dst_rec,
1383 : union xfs_btree_rec *src_rec,
1384 : int numrecs)
1385 : {
1386 738587745 : ASSERT(numrecs >= 0);
1387 1477175490 : memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len);
1388 738587745 : }
1389 :
1390 : /*
1391 : * Copy block pointers from one btree block to another.
1392 : */
1393 : void
1394 4950419 : xfs_btree_copy_ptrs(
1395 : struct xfs_btree_cur *cur,
1396 : union xfs_btree_ptr *dst_ptr,
1397 : const union xfs_btree_ptr *src_ptr,
1398 : int numptrs)
1399 : {
1400 4950419 : ASSERT(numptrs >= 0);
1401 11773162 : memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur));
1402 4950419 : }
1403 :
1404 : /*
1405 : * Shift keys one index left/right inside a single btree block.
1406 : */
1407 : STATIC void
1408 832252 : xfs_btree_shift_keys(
1409 : struct xfs_btree_cur *cur,
1410 : union xfs_btree_key *key,
1411 : int dir,
1412 : int numkeys)
1413 : {
1414 832252 : char *dst_key;
1415 :
1416 832252 : ASSERT(numkeys >= 0);
1417 832252 : ASSERT(dir == 1 || dir == -1);
1418 :
1419 832252 : dst_key = (char *)key + (dir * cur->bc_ops->key_len);
1420 1664504 : memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
1421 832252 : }
1422 :
1423 : /*
1424 : * Shift records one index left/right inside a single btree block.
1425 : */
1426 : STATIC void
1427 620271573 : xfs_btree_shift_recs(
1428 : struct xfs_btree_cur *cur,
1429 : union xfs_btree_rec *rec,
1430 : int dir,
1431 : int numrecs)
1432 : {
1433 620271573 : char *dst_rec;
1434 :
1435 620271573 : ASSERT(numrecs >= 0);
1436 620271573 : ASSERT(dir == 1 || dir == -1);
1437 :
1438 620271573 : dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);
1439 1240543146 : memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);
1440 620271573 : }
1441 :
1442 : /*
1443 : * Shift block pointers one index left/right inside a single btree block.
1444 : */
1445 : STATIC void
1446 832252 : xfs_btree_shift_ptrs(
1447 : struct xfs_btree_cur *cur,
1448 : union xfs_btree_ptr *ptr,
1449 : int dir,
1450 : int numptrs)
1451 : {
1452 832252 : char *dst_ptr;
1453 :
1454 832252 : ASSERT(numptrs >= 0);
1455 832252 : ASSERT(dir == 1 || dir == -1);
1456 :
1457 832252 : dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur));
1458 1664504 : memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur));
1459 832252 : }
1460 :
1461 : /*
1462 : * Log key values from the btree block.
1463 : */
1464 : STATIC void
1465 143988475 : xfs_btree_log_keys(
1466 : struct xfs_btree_cur *cur,
1467 : struct xfs_buf *bp,
1468 : int first,
1469 : int last)
1470 : {
1471 :
1472 143988475 : if (bp) {
1473 132338797 : xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1474 132338870 : xfs_trans_log_buf(cur->bc_tp, bp,
1475 132338870 : xfs_btree_key_offset(cur, first),
1476 132338870 : xfs_btree_key_offset(cur, last + 1) - 1);
1477 : } else {
1478 11649678 : xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1479 11649678 : xfs_ilog_fbroot(cur->bc_ino.whichfork));
1480 : }
1481 143988529 : }
1482 :
1483 : /*
1484 : * Log record values from the btree block.
1485 : */
1486 : void
1487 998696776 : xfs_btree_log_recs(
1488 : struct xfs_btree_cur *cur,
1489 : struct xfs_buf *bp,
1490 : int first,
1491 : int last)
1492 : {
1493 :
1494 998696776 : xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1495 998740998 : xfs_trans_log_buf(cur->bc_tp, bp,
1496 998740998 : xfs_btree_rec_offset(cur, first),
1497 998740998 : xfs_btree_rec_offset(cur, last + 1) - 1);
1498 :
1499 998807492 : }
1500 :
1501 : /*
1502 : * Log block pointer fields from a btree block (nonleaf).
1503 : */
1504 : STATIC void
1505 923407 : xfs_btree_log_ptrs(
1506 : struct xfs_btree_cur *cur, /* btree cursor */
1507 : struct xfs_buf *bp, /* buffer containing btree block */
1508 : int first, /* index of first pointer to log */
1509 : int last) /* index of last pointer to log */
1510 : {
1511 :
1512 923407 : if (bp) {
1513 874476 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
1514 874476 : int level = xfs_btree_get_level(block);
1515 :
1516 874476 : xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1517 874476 : xfs_trans_log_buf(cur->bc_tp, bp,
1518 874476 : xfs_btree_ptr_offset(cur, first, level),
1519 874476 : xfs_btree_ptr_offset(cur, last + 1, level) - 1);
1520 : } else {
1521 48931 : xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1522 48931 : xfs_ilog_fbroot(cur->bc_ino.whichfork));
1523 : }
1524 :
1525 923407 : }
1526 :
1527 : /*
1528 : * Log fields from a btree block header.
1529 : */
1530 : void
1531 767431951 : xfs_btree_log_block(
1532 : struct xfs_btree_cur *cur, /* btree cursor */
1533 : struct xfs_buf *bp, /* buffer containing btree block */
1534 : uint32_t fields) /* mask of fields: XFS_BB_... */
1535 : {
1536 767431951 : int first; /* first byte offset logged */
1537 767431951 : int last; /* last byte offset logged */
1538 767431951 : static const short soffsets[] = { /* table of offsets (short) */
1539 : offsetof(struct xfs_btree_block, bb_magic),
1540 : offsetof(struct xfs_btree_block, bb_level),
1541 : offsetof(struct xfs_btree_block, bb_numrecs),
1542 : offsetof(struct xfs_btree_block, bb_u.s.bb_leftsib),
1543 : offsetof(struct xfs_btree_block, bb_u.s.bb_rightsib),
1544 : offsetof(struct xfs_btree_block, bb_u.s.bb_blkno),
1545 : offsetof(struct xfs_btree_block, bb_u.s.bb_lsn),
1546 : offsetof(struct xfs_btree_block, bb_u.s.bb_uuid),
1547 : offsetof(struct xfs_btree_block, bb_u.s.bb_owner),
1548 : offsetof(struct xfs_btree_block, bb_u.s.bb_crc),
1549 : XFS_BTREE_SBLOCK_CRC_LEN
1550 : };
1551 767431951 : static const short loffsets[] = { /* table of offsets (long) */
1552 : offsetof(struct xfs_btree_block, bb_magic),
1553 : offsetof(struct xfs_btree_block, bb_level),
1554 : offsetof(struct xfs_btree_block, bb_numrecs),
1555 : offsetof(struct xfs_btree_block, bb_u.l.bb_leftsib),
1556 : offsetof(struct xfs_btree_block, bb_u.l.bb_rightsib),
1557 : offsetof(struct xfs_btree_block, bb_u.l.bb_blkno),
1558 : offsetof(struct xfs_btree_block, bb_u.l.bb_lsn),
1559 : offsetof(struct xfs_btree_block, bb_u.l.bb_uuid),
1560 : offsetof(struct xfs_btree_block, bb_u.l.bb_owner),
1561 : offsetof(struct xfs_btree_block, bb_u.l.bb_crc),
1562 : offsetof(struct xfs_btree_block, bb_u.l.bb_pad),
1563 : XFS_BTREE_LBLOCK_CRC_LEN
1564 : };
1565 :
1566 767431951 : if (bp) {
1567 767338966 : int nbits;
1568 :
1569 767338966 : if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
1570 : /*
1571 : * We don't log the CRC when updating a btree
1572 : * block but instead recreate it during log
1573 : * recovery. As the log buffers have checksums
1574 : * of their own this is safe and avoids logging a crc
1575 : * update in a lot of places.
1576 : */
1577 767338149 : if (fields == XFS_BB_ALL_BITS)
1578 899096 : fields = XFS_BB_ALL_BITS_CRC;
1579 : nbits = XFS_BB_NUM_BITS_CRC;
1580 : } else {
1581 : nbits = XFS_BB_NUM_BITS;
1582 : }
1583 767338966 : xfs_btree_offsets(fields,
1584 767338966 : (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
1585 : loffsets : soffsets,
1586 : nbits, &first, &last);
1587 767389281 : xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1588 767397181 : xfs_trans_log_buf(cur->bc_tp, bp, first, last);
1589 : } else {
1590 92985 : xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1591 92985 : xfs_ilog_fbroot(cur->bc_ino.whichfork));
1592 : }
1593 767402648 : }
1594 :
1595 : /*
1596 : * Increment cursor by one record at the level.
1597 : * For nonzero levels the leaf-ward information is untouched.
1598 : */
1599 : int /* error */
1600 68112988211 : xfs_btree_increment(
1601 : struct xfs_btree_cur *cur,
1602 : int level,
1603 : int *stat) /* success/failure */
1604 : {
1605 68112988211 : struct xfs_btree_block *block;
1606 68112988211 : union xfs_btree_ptr ptr;
1607 68112988211 : struct xfs_buf *bp;
1608 68112988211 : int error; /* error return value */
1609 68112988211 : int lev;
1610 :
1611 68112988211 : ASSERT(level < cur->bc_nlevels);
1612 :
1613 : /* Read-ahead to the right at this level. */
1614 68112988211 : xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1615 :
1616 : /* Get a pointer to the btree block. */
1617 68213001595 : block = xfs_btree_get_block(cur, level, &bp);
1618 :
1619 : #ifdef DEBUG
1620 68295234766 : error = xfs_btree_check_block(cur, block, level, bp);
1621 67513937863 : if (error)
1622 0 : goto error0;
1623 : #endif
1624 :
1625 : /* We're done if we remain in the block after the increment. */
1626 67513937863 : if (++cur->bc_levels[level].ptr <= xfs_btree_get_numrecs(block))
1627 65438792987 : goto out1;
1628 :
1629 : /* Fail if we just went off the right edge of the tree. */
1630 2075144876 : xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1631 4150706818 : if (xfs_btree_ptr_is_null(cur, &ptr))
1632 1660311560 : goto out0;
1633 :
1634 415041849 : XFS_BTREE_STATS_INC(cur, increment);
1635 :
1636 : /*
1637 : * March up the tree incrementing pointers.
1638 : * Stop when we don't go off the right edge of a block.
1639 : */
1640 419009601 : for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1641 419007229 : block = xfs_btree_get_block(cur, lev, &bp);
1642 :
1643 : #ifdef DEBUG
1644 419000057 : error = xfs_btree_check_block(cur, block, lev, bp);
1645 418971075 : if (error)
1646 0 : goto error0;
1647 : #endif
1648 :
1649 418971075 : if (++cur->bc_levels[lev].ptr <= xfs_btree_get_numrecs(block))
1650 : break;
1651 :
1652 : /* Read-ahead the right block for the next loop. */
1653 3947857 : xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1654 : }
1655 :
1656 : /*
1657 : * If we went off the root then we are either seriously
1658 : * confused or have the tree root in an inode.
1659 : */
1660 415025590 : if (lev == cur->bc_nlevels) {
1661 0 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1662 0 : goto out0;
1663 0 : ASSERT(0);
1664 0 : error = -EFSCORRUPTED;
1665 0 : goto error0;
1666 : }
1667 415025590 : ASSERT(lev < cur->bc_nlevels);
1668 :
1669 : /*
1670 : * Now walk back down the tree, fixing up the cursor's buffer
1671 : * pointers and key numbers.
1672 : */
1673 833995487 : for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1674 418987455 : union xfs_btree_ptr *ptrp;
1675 :
1676 418987455 : ptrp = xfs_btree_ptr_addr(cur, cur->bc_levels[lev].ptr, block);
1677 418999608 : --lev;
1678 418999608 : error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);
1679 419006168 : if (error)
1680 6 : goto error0;
1681 :
1682 419006162 : xfs_btree_setbuf(cur, lev, bp);
1683 418969897 : cur->bc_levels[lev].ptr = 1;
1684 : }
1685 415025286 : out1:
1686 65853818273 : *stat = 1;
1687 65853818273 : return 0;
1688 :
1689 1660311560 : out0:
1690 1660311560 : *stat = 0;
1691 1660311560 : return 0;
1692 :
1693 : error0:
1694 : return error;
1695 : }
1696 :
1697 : /*
1698 : * Decrement cursor by one record at the level.
1699 : * For nonzero levels the leaf-ward information is untouched.
1700 : */
1701 : int /* error */
1702 572264100 : xfs_btree_decrement(
1703 : struct xfs_btree_cur *cur,
1704 : int level,
1705 : int *stat) /* success/failure */
1706 : {
1707 572264100 : struct xfs_btree_block *block;
1708 572264100 : struct xfs_buf *bp;
1709 572264100 : int error; /* error return value */
1710 572264100 : int lev;
1711 572264100 : union xfs_btree_ptr ptr;
1712 :
1713 572264100 : ASSERT(level < cur->bc_nlevels);
1714 :
1715 : /* Read-ahead to the left at this level. */
1716 572264100 : xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1717 :
1718 : /* We're done if we remain in the block after the decrement. */
1719 572271382 : if (--cur->bc_levels[level].ptr > 0)
1720 527031042 : goto out1;
1721 :
1722 : /* Get a pointer to the btree block. */
1723 45240340 : block = xfs_btree_get_block(cur, level, &bp);
1724 :
1725 : #ifdef DEBUG
1726 45240331 : error = xfs_btree_check_block(cur, block, level, bp);
1727 45240329 : if (error)
1728 0 : goto error0;
1729 : #endif
1730 :
1731 : /* Fail if we just went off the left edge of the tree. */
1732 45240329 : xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
1733 90480728 : if (xfs_btree_ptr_is_null(cur, &ptr))
1734 4809297 : goto out0;
1735 :
1736 40431067 : XFS_BTREE_STATS_INC(cur, decrement);
1737 :
1738 : /*
1739 : * March up the tree decrementing pointers.
1740 : * Stop when we don't go off the left edge of a block.
1741 : */
1742 40521678 : for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1743 40521677 : if (--cur->bc_levels[lev].ptr > 0)
1744 : break;
1745 : /* Read-ahead the left block for the next loop. */
1746 90595 : xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1747 : }
1748 :
1749 : /*
1750 : * If we went off the root then we are seriously confused.
1751 : * or the root of the tree is in an inode.
1752 : */
1753 40431083 : if (lev == cur->bc_nlevels) {
1754 0 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1755 0 : goto out0;
1756 0 : ASSERT(0);
1757 0 : error = -EFSCORRUPTED;
1758 0 : goto error0;
1759 : }
1760 40431083 : ASSERT(lev < cur->bc_nlevels);
1761 :
1762 : /*
1763 : * Now walk back down the tree, fixing up the cursor's buffer
1764 : * pointers and key numbers.
1765 : */
1766 80952686 : for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1767 40521665 : union xfs_btree_ptr *ptrp;
1768 :
1769 40521665 : ptrp = xfs_btree_ptr_addr(cur, cur->bc_levels[lev].ptr, block);
1770 40521674 : --lev;
1771 40521674 : error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);
1772 40521658 : if (error)
1773 5 : goto error0;
1774 40521653 : xfs_btree_setbuf(cur, lev, bp);
1775 40521603 : cur->bc_levels[lev].ptr = xfs_btree_get_numrecs(block);
1776 : }
1777 40431013 : out1:
1778 567462055 : *stat = 1;
1779 567462055 : return 0;
1780 :
1781 4809297 : out0:
1782 4809297 : *stat = 0;
1783 4809297 : return 0;
1784 :
1785 : error0:
1786 : return error;
1787 : }
1788 :
1789 : int
1790 17890924605 : xfs_btree_lookup_get_block(
1791 : struct xfs_btree_cur *cur, /* btree cursor */
1792 : int level, /* level in the btree */
1793 : const union xfs_btree_ptr *pp, /* ptr to btree block */
1794 : struct xfs_btree_block **blkp) /* return btree block */
1795 : {
1796 17890924605 : struct xfs_buf *bp; /* buffer pointer for btree block */
1797 17890924605 : xfs_daddr_t daddr;
1798 17890924605 : int error = 0;
1799 :
1800 : /* special case the root block if in an inode */
1801 17890924605 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1802 324388553 : (level == cur->bc_nlevels - 1)) {
1803 122915627 : *blkp = xfs_btree_get_iroot(cur);
1804 122915703 : return 0;
1805 : }
1806 :
1807 : /*
1808 : * If the old buffer at this level for the disk address we are
1809 : * looking for re-use it.
1810 : *
1811 : * Otherwise throw it away and get a new one.
1812 : */
1813 17768008978 : bp = cur->bc_levels[level].bp;
1814 17768008978 : error = xfs_btree_ptr_to_daddr(cur, pp, &daddr);
1815 17776352902 : if (error)
1816 : return error;
1817 17776352902 : if (bp && xfs_buf_daddr(bp) == daddr) {
1818 11878927333 : *blkp = XFS_BUF_TO_BLOCK(bp);
1819 11878927333 : return 0;
1820 : }
1821 :
1822 5897425569 : error = xfs_btree_read_buf_block(cur, pp, 0, blkp, &bp);
1823 5896143368 : if (error)
1824 : return error;
1825 :
1826 : /* Check the inode owner since the verifiers don't. */
1827 5896138719 : if (xfs_has_crc(cur->bc_mp) &&
1828 5896681583 : !(cur->bc_ino.flags & XFS_BTCUR_BMBT_INVALID_OWNER) &&
1829 5896722062 : (cur->bc_flags & XFS_BTREE_LONG_PTRS) &&
1830 171930072 : be64_to_cpu((*blkp)->bb_u.l.bb_owner) !=
1831 171930072 : cur->bc_ino.ip->i_ino)
1832 0 : goto out_bad;
1833 :
1834 : /* Did we get the level we were looking for? */
1835 5896138719 : if (be16_to_cpu((*blkp)->bb_level) != level)
1836 0 : goto out_bad;
1837 :
1838 : /* Check that internal nodes have at least one record. */
1839 5896138719 : if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0)
1840 0 : goto out_bad;
1841 :
1842 5896138719 : xfs_btree_setbuf(cur, level, bp);
1843 5896138719 : return 0;
1844 :
1845 0 : out_bad:
1846 0 : *blkp = NULL;
1847 0 : xfs_buf_mark_corrupt(bp);
1848 0 : xfs_trans_brelse(cur->bc_tp, bp);
1849 0 : return -EFSCORRUPTED;
1850 : }
1851 :
1852 : /*
1853 : * Get current search key. For level 0 we don't actually have a key
1854 : * structure so we make one up from the record. For all other levels
1855 : * we just return the right key.
1856 : */
1857 : STATIC union xfs_btree_key *
1858 70072208428 : xfs_lookup_get_search_key(
1859 : struct xfs_btree_cur *cur,
1860 : int level,
1861 : int keyno,
1862 : struct xfs_btree_block *block,
1863 : union xfs_btree_key *kp)
1864 : {
1865 70072208428 : if (level == 0) {
1866 54499808304 : cur->bc_ops->init_key_from_rec(kp,
1867 : xfs_btree_rec_addr(cur, keyno, block));
1868 54499808304 : return kp;
1869 : }
1870 :
1871 15572400124 : return xfs_btree_key_addr(cur, keyno, block);
1872 : }
1873 :
1874 : /*
1875 : * Lookup the record. The cursor is made to point to it, based on dir.
1876 : * stat is set to 0 if can't find any such record, 1 for success.
1877 : */
1878 : int /* error */
1879 11439107637 : xfs_btree_lookup(
1880 : struct xfs_btree_cur *cur, /* btree cursor */
1881 : xfs_lookup_t dir, /* <=, ==, or >= */
1882 : int *stat) /* success/failure */
1883 : {
1884 11439107637 : struct xfs_btree_block *block; /* current btree block */
1885 11439107637 : int64_t diff; /* difference for the current key */
1886 11439107637 : int error; /* error return value */
1887 11439107637 : int keyno; /* current key number */
1888 11439107637 : int level; /* level in the btree */
1889 11439107637 : union xfs_btree_ptr *pp; /* ptr to btree block */
1890 11439107637 : union xfs_btree_ptr ptr; /* ptr to btree block */
1891 :
1892 11439107637 : XFS_BTREE_STATS_INC(cur, lookup);
1893 :
1894 : /* No such thing as a zero-level tree. */
1895 11440786132 : if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0))
1896 0 : return -EFSCORRUPTED;
1897 :
1898 11440786132 : block = NULL;
1899 11440786132 : keyno = 0;
1900 :
1901 : /* initialise start pointer from cursor */
1902 11440786132 : cur->bc_ops->init_ptr_from_cur(cur, &ptr);
1903 11440586044 : pp = &ptr;
1904 :
1905 : /*
1906 : * Iterate over each level in the btree, starting at the root.
1907 : * For each level above the leaves, find the key we need, based
1908 : * on the lookup record, then follow the corresponding block
1909 : * pointer down to the next level.
1910 : */
1911 26828333857 : for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1912 : /* Get the block we need to do the lookup on. */
1913 15993618619 : error = xfs_btree_lookup_get_block(cur, level, pp, &block);
1914 15991500483 : if (error)
1915 4580 : goto error0;
1916 :
1917 15991495903 : if (diff == 0) {
1918 : /*
1919 : * If we already had a key match at a higher level, we
1920 : * know we need to use the first entry in this block.
1921 : */
1922 : keyno = 1;
1923 : } else {
1924 : /* Otherwise search this block. Do a binary search. */
1925 :
1926 15979236271 : int high; /* high entry number */
1927 15979236271 : int low; /* low entry number */
1928 :
1929 : /* Set low and high entry numbers, 1-based. */
1930 15979236271 : low = 1;
1931 15979236271 : high = xfs_btree_get_numrecs(block);
1932 15979236271 : if (!high) {
1933 : /* Block is empty, must be an empty leaf. */
1934 609132077 : if (level != 0 || cur->bc_nlevels != 1) {
1935 0 : XFS_CORRUPTION_ERROR(__func__,
1936 : XFS_ERRLEVEL_LOW,
1937 : cur->bc_mp, block,
1938 : sizeof(*block));
1939 0 : return -EFSCORRUPTED;
1940 : }
1941 :
1942 609132077 : cur->bc_levels[0].ptr = dir != XFS_LOOKUP_LE;
1943 609132077 : *stat = 0;
1944 609132077 : return 0;
1945 : }
1946 :
1947 : /* Binary search the block. */
1948 84356105663 : while (low <= high) {
1949 70076589992 : union xfs_btree_key key;
1950 70076589992 : union xfs_btree_key *kp;
1951 :
1952 70076589992 : XFS_BTREE_STATS_INC(cur, compare);
1953 :
1954 : /* keyno is average of low and high. */
1955 70012894355 : keyno = (low + high) >> 1;
1956 :
1957 : /* Get current search key */
1958 70012894355 : kp = xfs_lookup_get_search_key(cur, level,
1959 : keyno, block, &key);
1960 :
1961 : /*
1962 : * Compute difference to get next direction:
1963 : * - less than, move right
1964 : * - greater than, move left
1965 : * - equal, we're done
1966 : */
1967 70010601301 : diff = cur->bc_ops->key_diff(cur, kp);
1968 70082095530 : if (diff < 0)
1969 37827573500 : low = keyno + 1;
1970 32254522030 : else if (diff > 0)
1971 31158427969 : high = keyno - 1;
1972 : else
1973 : break;
1974 : }
1975 : }
1976 :
1977 : /*
1978 : * If there are more levels, set up for the next level
1979 : * by getting the block number and filling in the cursor.
1980 : */
1981 15387869364 : if (level > 0) {
1982 : /*
1983 : * If we moved left, need the previous key number,
1984 : * unless there isn't one.
1985 : */
1986 4552832362 : if (diff > 0 && --keyno < 1)
1987 : keyno = 1;
1988 4552832362 : pp = xfs_btree_ptr_addr(cur, keyno, block);
1989 :
1990 4552751974 : error = xfs_btree_debug_check_ptr(cur, pp, 0, level);
1991 4552710811 : if (error)
1992 0 : goto error0;
1993 :
1994 4552710811 : cur->bc_levels[level].ptr = keyno;
1995 : }
1996 : }
1997 :
1998 : /* Done with the search. See if we need to adjust the results. */
1999 10834715238 : if (dir != XFS_LOOKUP_LE && diff < 0) {
2000 321671481 : keyno++;
2001 : /*
2002 : * If ge search and we went off the end of the block, but it's
2003 : * not the last block, we're in the wrong block.
2004 : */
2005 321671481 : xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
2006 321674703 : if (dir == XFS_LOOKUP_GE &&
2007 203504417 : keyno > xfs_btree_get_numrecs(block) &&
2008 : !xfs_btree_ptr_is_null(cur, &ptr)) {
2009 942883 : int i;
2010 :
2011 942883 : cur->bc_levels[0].ptr = keyno;
2012 942883 : error = xfs_btree_increment(cur, 0, &i);
2013 942883 : if (error)
2014 0 : goto error0;
2015 942883 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
2016 942883 : return -EFSCORRUPTED;
2017 942883 : *stat = 1;
2018 942883 : return 0;
2019 : }
2020 10513043757 : } else if (dir == XFS_LOOKUP_LE && diff > 0)
2021 5815763473 : keyno--;
2022 10833775577 : cur->bc_levels[0].ptr = keyno;
2023 :
2024 : /* Return if we succeeded or not. */
2025 10833775577 : if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))
2026 2992580467 : *stat = 0;
2027 7841195110 : else if (dir != XFS_LOOKUP_EQ || diff == 0)
2028 7632778075 : *stat = 1;
2029 : else
2030 208417035 : *stat = 0;
2031 : return 0;
2032 :
2033 : error0:
2034 : return error;
2035 : }
2036 :
2037 : /* Find the high key storage area from a regular key. */
2038 : union xfs_btree_key *
2039 597178781 : xfs_btree_high_key_from_key(
2040 : struct xfs_btree_cur *cur,
2041 : union xfs_btree_key *key)
2042 : {
2043 597178781 : ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING);
2044 597178781 : return (union xfs_btree_key *)((char *)key +
2045 597178781 : (cur->bc_ops->key_len / 2));
2046 : }
2047 :
2048 : /* Determine the low (and high if overlapped) keys of a leaf block */
2049 : STATIC void
2050 418326331 : xfs_btree_get_leaf_keys(
2051 : struct xfs_btree_cur *cur,
2052 : struct xfs_btree_block *block,
2053 : union xfs_btree_key *key)
2054 : {
2055 418326331 : union xfs_btree_key max_hkey;
2056 418326331 : union xfs_btree_key hkey;
2057 418326331 : union xfs_btree_rec *rec;
2058 418326331 : union xfs_btree_key *high;
2059 418326331 : int n;
2060 :
2061 418326331 : rec = xfs_btree_rec_addr(cur, 1, block);
2062 418326331 : cur->bc_ops->init_key_from_rec(key, rec);
2063 :
2064 418335408 : if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2065 :
2066 271458778 : cur->bc_ops->init_high_key_from_rec(&max_hkey, rec);
2067 41426225032 : for (n = 2; n <= xfs_btree_get_numrecs(block); n++) {
2068 40883306971 : rec = xfs_btree_rec_addr(cur, n, block);
2069 40883306971 : cur->bc_ops->init_high_key_from_rec(&hkey, rec);
2070 40891254157 : if (xfs_btree_keycmp_gt(cur, &hkey, &max_hkey))
2071 40767138470 : max_hkey = hkey;
2072 : }
2073 :
2074 271459283 : high = xfs_btree_high_key_from_key(cur, key);
2075 542915714 : memcpy(high, &max_hkey, cur->bc_ops->key_len / 2);
2076 : }
2077 418334487 : }
2078 :
2079 : /* Determine the low (and high if overlapped) keys of a node block */
2080 : STATIC void
2081 54267034 : xfs_btree_get_node_keys(
2082 : struct xfs_btree_cur *cur,
2083 : struct xfs_btree_block *block,
2084 : union xfs_btree_key *key)
2085 : {
2086 54267034 : union xfs_btree_key *hkey;
2087 54267034 : union xfs_btree_key *max_hkey;
2088 54267034 : union xfs_btree_key *high;
2089 54267034 : int n;
2090 :
2091 54267034 : if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2092 108443440 : memcpy(key, xfs_btree_key_addr(cur, 1, block),
2093 : cur->bc_ops->key_len / 2);
2094 :
2095 54221720 : max_hkey = xfs_btree_high_key_addr(cur, 1, block);
2096 4483852952 : for (n = 2; n <= xfs_btree_get_numrecs(block); n++) {
2097 4429631246 : hkey = xfs_btree_high_key_addr(cur, n, block);
2098 4429631246 : if (xfs_btree_keycmp_gt(cur, hkey, max_hkey))
2099 4416547578 : max_hkey = hkey;
2100 : }
2101 :
2102 54221706 : high = xfs_btree_high_key_from_key(cur, key);
2103 108443370 : memcpy(high, max_hkey, cur->bc_ops->key_len / 2);
2104 : } else {
2105 90628 : memcpy(key, xfs_btree_key_addr(cur, 1, block),
2106 : cur->bc_ops->key_len);
2107 : }
2108 54266999 : }
2109 :
2110 : /* Derive the keys for any btree block. */
2111 : void
2112 418295709 : xfs_btree_get_keys(
2113 : struct xfs_btree_cur *cur,
2114 : struct xfs_btree_block *block,
2115 : union xfs_btree_key *key)
2116 : {
2117 418295709 : if (be16_to_cpu(block->bb_level) == 0)
2118 417699507 : xfs_btree_get_leaf_keys(cur, block, key);
2119 : else
2120 596802 : xfs_btree_get_node_keys(cur, block, key);
2121 418312901 : }
2122 :
2123 : /*
2124 : * Decide if we need to update the parent keys of a btree block. For
2125 : * a standard btree this is only necessary if we're updating the first
2126 : * record/key. For an overlapping btree, we must always update the
2127 : * keys because the highest key can be in any of the records or keys
2128 : * in the block.
2129 : */
2130 : static inline bool
2131 : xfs_btree_needs_key_update(
2132 : struct xfs_btree_cur *cur,
2133 : int ptr)
2134 : {
2135 593076616 : return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1;
2136 : }
2137 :
2138 : /*
2139 : * Update the low and high parent keys of the given level, progressing
2140 : * towards the root. If force_all is false, stop if the keys for a given
2141 : * level do not need updating.
2142 : */
2143 : STATIC int
2144 274472554 : __xfs_btree_updkeys(
2145 : struct xfs_btree_cur *cur,
2146 : int level,
2147 : struct xfs_btree_block *block,
2148 : struct xfs_buf *bp0,
2149 : bool force_all)
2150 : {
2151 274472554 : union xfs_btree_key key; /* keys from current level */
2152 274472554 : union xfs_btree_key *lkey; /* keys from the next level up */
2153 274472554 : union xfs_btree_key *hkey;
2154 274472554 : union xfs_btree_key *nlkey; /* keys from the next level up */
2155 274472554 : union xfs_btree_key *nhkey;
2156 274472554 : struct xfs_buf *bp;
2157 274472554 : int ptr;
2158 :
2159 274472554 : ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING);
2160 :
2161 : /* Exit if there aren't any parent levels to update. */
2162 274472554 : if (level + 1 >= cur->bc_nlevels)
2163 : return 0;
2164 :
2165 262865287 : trace_xfs_btree_updkeys(cur, level, bp0);
2166 :
2167 262865932 : lkey = &key;
2168 262865932 : hkey = xfs_btree_high_key_from_key(cur, lkey);
2169 262866084 : xfs_btree_get_keys(cur, block, lkey);
2170 579394877 : for (level++; level < cur->bc_nlevels; level++) {
2171 : #ifdef DEBUG
2172 316528793 : int error;
2173 : #endif
2174 316528793 : block = xfs_btree_get_block(cur, level, &bp);
2175 316529168 : trace_xfs_btree_updkeys(cur, level, bp);
2176 : #ifdef DEBUG
2177 316529230 : error = xfs_btree_check_block(cur, block, level, bp);
2178 316528610 : if (error)
2179 0 : return error;
2180 : #endif
2181 316528610 : ptr = cur->bc_levels[level].ptr;
2182 316528610 : nlkey = xfs_btree_key_addr(cur, ptr, block);
2183 316528610 : nhkey = xfs_btree_high_key_addr(cur, ptr, block);
2184 632851897 : if (!force_all &&
2185 288549922 : xfs_btree_keycmp_eq(cur, nlkey, lkey) &&
2186 : xfs_btree_keycmp_eq(cur, nhkey, hkey))
2187 : break;
2188 69812559 : xfs_btree_copy_keys(cur, nlkey, lkey, 1);
2189 69812874 : xfs_btree_log_keys(cur, bp, ptr, ptr);
2190 69812877 : if (level + 1 >= cur->bc_nlevels)
2191 : break;
2192 53663024 : xfs_btree_get_node_keys(cur, block, lkey);
2193 : }
2194 :
2195 : return 0;
2196 : }
2197 :
2198 : /* Update all the keys from some level in cursor back to the root. */
2199 : STATIC int
2200 116432 : xfs_btree_updkeys_force(
2201 : struct xfs_btree_cur *cur,
2202 : int level)
2203 : {
2204 116432 : struct xfs_buf *bp;
2205 116432 : struct xfs_btree_block *block;
2206 :
2207 116432 : block = xfs_btree_get_block(cur, level, &bp);
2208 116432 : return __xfs_btree_updkeys(cur, level, block, bp, true);
2209 : }
2210 :
2211 : /*
2212 : * Update the parent keys of the given level, progressing towards the root.
2213 : */
2214 : STATIC int
2215 413116214 : xfs_btree_update_keys(
2216 : struct xfs_btree_cur *cur,
2217 : int level)
2218 : {
2219 413116214 : struct xfs_btree_block *block;
2220 413116214 : struct xfs_buf *bp;
2221 413116214 : union xfs_btree_key *kp;
2222 413116214 : union xfs_btree_key key;
2223 413116214 : int ptr;
2224 :
2225 413116214 : ASSERT(level >= 0);
2226 :
2227 413116214 : block = xfs_btree_get_block(cur, level, &bp);
2228 413141150 : if (cur->bc_flags & XFS_BTREE_OVERLAPPING)
2229 274357312 : return __xfs_btree_updkeys(cur, level, block, bp, false);
2230 :
2231 : /*
2232 : * Go up the tree from this level toward the root.
2233 : * At each level, update the key value to the value input.
2234 : * Stop when we reach a level where the cursor isn't pointing
2235 : * at the first entry in the block.
2236 : */
2237 138783838 : xfs_btree_get_keys(cur, block, &key);
2238 212035512 : for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
2239 : #ifdef DEBUG
2240 73252105 : int error;
2241 : #endif
2242 73252105 : block = xfs_btree_get_block(cur, level, &bp);
2243 : #ifdef DEBUG
2244 73252150 : error = xfs_btree_check_block(cur, block, level, bp);
2245 73251905 : if (error)
2246 0 : return error;
2247 : #endif
2248 73251905 : ptr = cur->bc_levels[level].ptr;
2249 73251905 : kp = xfs_btree_key_addr(cur, ptr, block);
2250 73251905 : xfs_btree_copy_keys(cur, kp, &key, 1);
2251 73252196 : xfs_btree_log_keys(cur, bp, ptr, ptr);
2252 : }
2253 :
2254 : return 0;
2255 : }
2256 :
2257 : /*
2258 : * Update the record referred to by cur to the value in the
2259 : * given record. This either works (return 0) or gets an
2260 : * EFSCORRUPTED error.
2261 : */
2262 : int
2263 321141361 : xfs_btree_update(
2264 : struct xfs_btree_cur *cur,
2265 : union xfs_btree_rec *rec)
2266 : {
2267 321141361 : struct xfs_btree_block *block;
2268 321141361 : struct xfs_buf *bp;
2269 321141361 : int error;
2270 321141361 : int ptr;
2271 321141361 : union xfs_btree_rec *rp;
2272 :
2273 : /* Pick up the current block. */
2274 321141361 : block = xfs_btree_get_block(cur, 0, &bp);
2275 :
2276 : #ifdef DEBUG
2277 321152015 : error = xfs_btree_check_block(cur, block, 0, bp);
2278 321131562 : if (error)
2279 0 : goto error0;
2280 : #endif
2281 : /* Get the address of the rec to be updated. */
2282 321131562 : ptr = cur->bc_levels[0].ptr;
2283 321131562 : rp = xfs_btree_rec_addr(cur, ptr, block);
2284 :
2285 : /* Fill in the new contents and log them. */
2286 321131562 : xfs_btree_copy_recs(cur, rp, rec, 1);
2287 321170161 : xfs_btree_log_recs(cur, bp, ptr, ptr);
2288 :
2289 : /*
2290 : * If we are tracking the last record in the tree and
2291 : * we are at the far right edge of the tree, update it.
2292 : */
2293 321170464 : if (xfs_btree_is_lastrec(cur, block, 0)) {
2294 0 : cur->bc_ops->update_lastrec(cur, block, rec,
2295 : ptr, LASTREC_UPDATE);
2296 : }
2297 :
2298 : /* Pass new key value up to our parent. */
2299 613489955 : if (xfs_btree_needs_key_update(cur, ptr)) {
2300 85501054 : error = xfs_btree_update_keys(cur, 0);
2301 85500181 : if (error)
2302 0 : goto error0;
2303 : }
2304 :
2305 : return 0;
2306 :
2307 : error0:
2308 : return error;
2309 : }
2310 :
2311 : /*
2312 : * Move 1 record left from cur/level if possible.
2313 : * Update cur to reflect the new path.
2314 : */
2315 : STATIC int /* error */
2316 56938053 : xfs_btree_lshift(
2317 : struct xfs_btree_cur *cur,
2318 : int level,
2319 : int *stat) /* success/failure */
2320 : {
2321 56938053 : struct xfs_buf *lbp; /* left buffer pointer */
2322 56938053 : struct xfs_btree_block *left; /* left btree block */
2323 56938053 : int lrecs; /* left record count */
2324 56938053 : struct xfs_buf *rbp; /* right buffer pointer */
2325 56938053 : struct xfs_btree_block *right; /* right btree block */
2326 56938053 : struct xfs_btree_cur *tcur; /* temporary btree cursor */
2327 56938053 : int rrecs; /* right record count */
2328 56938053 : union xfs_btree_ptr lptr; /* left btree pointer */
2329 56938053 : union xfs_btree_key *rkp = NULL; /* right btree key */
2330 56938053 : union xfs_btree_ptr *rpp = NULL; /* right address pointer */
2331 56938053 : union xfs_btree_rec *rrp = NULL; /* right record pointer */
2332 56938053 : int error; /* error return value */
2333 56938053 : int i;
2334 :
2335 56938053 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2336 26168895 : level == cur->bc_nlevels - 1)
2337 0 : goto out0;
2338 :
2339 : /* Set up variables for this block as "right". */
2340 56938053 : right = xfs_btree_get_block(cur, level, &rbp);
2341 :
2342 : #ifdef DEBUG
2343 56937978 : error = xfs_btree_check_block(cur, right, level, rbp);
2344 56937915 : if (error)
2345 0 : goto error0;
2346 : #endif
2347 :
2348 : /* If we've got no left sibling then we can't shift an entry left. */
2349 56937915 : xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2350 113875962 : if (xfs_btree_ptr_is_null(cur, &lptr))
2351 25280 : goto out0;
2352 :
2353 : /*
2354 : * If the cursor entry is the one that would be moved, don't
2355 : * do it... it's too complicated.
2356 : */
2357 56912701 : if (cur->bc_levels[level].ptr <= 1)
2358 7377 : goto out0;
2359 :
2360 : /* Set up the left neighbor as "left". */
2361 56905324 : error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
2362 56905337 : if (error)
2363 56 : goto error0;
2364 :
2365 : /* If it's full, it can't take another entry. */
2366 56905281 : lrecs = xfs_btree_get_numrecs(left);
2367 56905281 : if (lrecs == cur->bc_ops->get_maxrecs(cur, level))
2368 572876 : goto out0;
2369 :
2370 56332420 : rrecs = xfs_btree_get_numrecs(right);
2371 :
2372 : /*
2373 : * We add one entry to the left side and remove one for the right side.
2374 : * Account for it here, the changes will be updated on disk and logged
2375 : * later.
2376 : */
2377 56332420 : lrecs++;
2378 56332420 : rrecs--;
2379 :
2380 56332420 : XFS_BTREE_STATS_INC(cur, lshift);
2381 56332435 : XFS_BTREE_STATS_ADD(cur, moves, 1);
2382 :
2383 : /*
2384 : * If non-leaf, copy a key and a ptr to the left block.
2385 : * Log the changes to the left block.
2386 : */
2387 56332360 : if (level > 0) {
2388 : /* It's a non-leaf. Move keys and pointers. */
2389 71105 : union xfs_btree_key *lkp; /* left btree key */
2390 71105 : union xfs_btree_ptr *lpp; /* left address pointer */
2391 :
2392 71105 : lkp = xfs_btree_key_addr(cur, lrecs, left);
2393 71105 : rkp = xfs_btree_key_addr(cur, 1, right);
2394 :
2395 71105 : lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2396 71105 : rpp = xfs_btree_ptr_addr(cur, 1, right);
2397 :
2398 71105 : error = xfs_btree_debug_check_ptr(cur, rpp, 0, level);
2399 71105 : if (error)
2400 0 : goto error0;
2401 :
2402 71105 : xfs_btree_copy_keys(cur, lkp, rkp, 1);
2403 71105 : xfs_btree_copy_ptrs(cur, lpp, rpp, 1);
2404 :
2405 71105 : xfs_btree_log_keys(cur, lbp, lrecs, lrecs);
2406 71105 : xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs);
2407 :
2408 71105 : ASSERT(cur->bc_ops->keys_inorder(cur,
2409 : xfs_btree_key_addr(cur, lrecs - 1, left), lkp));
2410 : } else {
2411 : /* It's a leaf. Move records. */
2412 56261255 : union xfs_btree_rec *lrp; /* left record pointer */
2413 :
2414 56261255 : lrp = xfs_btree_rec_addr(cur, lrecs, left);
2415 56261255 : rrp = xfs_btree_rec_addr(cur, 1, right);
2416 :
2417 56261255 : xfs_btree_copy_recs(cur, lrp, rrp, 1);
2418 56261339 : xfs_btree_log_recs(cur, lbp, lrecs, lrecs);
2419 :
2420 56261339 : ASSERT(cur->bc_ops->recs_inorder(cur,
2421 : xfs_btree_rec_addr(cur, lrecs - 1, left), lrp));
2422 : }
2423 :
2424 56332454 : xfs_btree_set_numrecs(left, lrecs);
2425 56332439 : xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2426 :
2427 56332380 : xfs_btree_set_numrecs(right, rrecs);
2428 56332394 : xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2429 :
2430 : /*
2431 : * Slide the contents of right down one entry.
2432 : */
2433 56332430 : XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1);
2434 56332447 : if (level > 0) {
2435 : /* It's a nonleaf. operate on keys and ptrs */
2436 13146779 : for (i = 0; i < rrecs; i++) {
2437 13075674 : error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level);
2438 13075674 : if (error)
2439 0 : goto error0;
2440 : }
2441 :
2442 71105 : xfs_btree_shift_keys(cur,
2443 : xfs_btree_key_addr(cur, 2, right),
2444 : -1, rrecs);
2445 71105 : xfs_btree_shift_ptrs(cur,
2446 : xfs_btree_ptr_addr(cur, 2, right),
2447 : -1, rrecs);
2448 :
2449 71105 : xfs_btree_log_keys(cur, rbp, 1, rrecs);
2450 71105 : xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2451 : } else {
2452 : /* It's a leaf. operate on records */
2453 56261342 : xfs_btree_shift_recs(cur,
2454 : xfs_btree_rec_addr(cur, 2, right),
2455 : -1, rrecs);
2456 56261338 : xfs_btree_log_recs(cur, rbp, 1, rrecs);
2457 : }
2458 :
2459 : /*
2460 : * Using a temporary cursor, update the parent key values of the
2461 : * block on the left.
2462 : */
2463 56332463 : if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2464 15778590 : error = xfs_btree_dup_cursor(cur, &tcur);
2465 15778592 : if (error)
2466 0 : goto error0;
2467 15778592 : i = xfs_btree_firstrec(tcur, level);
2468 15778585 : if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) {
2469 0 : error = -EFSCORRUPTED;
2470 0 : goto error0;
2471 : }
2472 :
2473 15778585 : error = xfs_btree_decrement(tcur, level, &i);
2474 15778591 : if (error)
2475 0 : goto error1;
2476 :
2477 : /* Update the parent high keys of the left block, if needed. */
2478 15778591 : error = xfs_btree_update_keys(tcur, level);
2479 15778589 : if (error)
2480 0 : goto error1;
2481 :
2482 15778589 : xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2483 : }
2484 :
2485 : /* Update the parent keys of the right block. */
2486 56332458 : error = xfs_btree_update_keys(cur, level);
2487 56332443 : if (error)
2488 0 : goto error0;
2489 :
2490 : /* Slide the cursor value left one. */
2491 56332443 : cur->bc_levels[level].ptr--;
2492 :
2493 56332443 : *stat = 1;
2494 56332443 : return 0;
2495 :
2496 605533 : out0:
2497 605533 : *stat = 0;
2498 605533 : return 0;
2499 :
2500 : error0:
2501 : return error;
2502 :
2503 0 : error1:
2504 0 : xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2505 0 : return error;
2506 : }
2507 :
2508 : /*
2509 : * Move 1 record right from cur/level if possible.
2510 : * Update cur to reflect the new path.
2511 : */
2512 : STATIC int /* error */
2513 86807280 : xfs_btree_rshift(
2514 : struct xfs_btree_cur *cur,
2515 : int level,
2516 : int *stat) /* success/failure */
2517 : {
2518 86807280 : struct xfs_buf *lbp; /* left buffer pointer */
2519 86807280 : struct xfs_btree_block *left; /* left btree block */
2520 86807280 : struct xfs_buf *rbp; /* right buffer pointer */
2521 86807280 : struct xfs_btree_block *right; /* right btree block */
2522 86807280 : struct xfs_btree_cur *tcur; /* temporary btree cursor */
2523 86807280 : union xfs_btree_ptr rptr; /* right block pointer */
2524 86807280 : union xfs_btree_key *rkp; /* right btree key */
2525 86807280 : int rrecs; /* right record count */
2526 86807280 : int lrecs; /* left record count */
2527 86807280 : int error; /* error return value */
2528 86807280 : int i; /* loop counter */
2529 :
2530 86807280 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2531 43893634 : (level == cur->bc_nlevels - 1))
2532 0 : goto out0;
2533 :
2534 : /* Set up variables for this block as "left". */
2535 86807280 : left = xfs_btree_get_block(cur, level, &lbp);
2536 :
2537 : #ifdef DEBUG
2538 86805786 : error = xfs_btree_check_block(cur, left, level, lbp);
2539 86804872 : if (error)
2540 0 : goto error0;
2541 : #endif
2542 :
2543 : /* If we've got no right sibling then we can't shift an entry right. */
2544 86804872 : xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2545 173611192 : if (xfs_btree_ptr_is_null(cur, &rptr))
2546 36802225 : goto out0;
2547 :
2548 : /*
2549 : * If the cursor entry is the one that would be moved, don't
2550 : * do it... it's too complicated.
2551 : */
2552 50003371 : lrecs = xfs_btree_get_numrecs(left);
2553 50003371 : if (cur->bc_levels[level].ptr >= lrecs)
2554 6208745 : goto out0;
2555 :
2556 : /* Set up the right neighbor as "right". */
2557 43794626 : error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
2558 43790075 : if (error)
2559 133 : goto error0;
2560 :
2561 : /* If it's full, it can't take another entry. */
2562 43789942 : rrecs = xfs_btree_get_numrecs(right);
2563 43789942 : if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
2564 5842495 : goto out0;
2565 :
2566 37949218 : XFS_BTREE_STATS_INC(cur, rshift);
2567 37950523 : XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2568 :
2569 : /*
2570 : * Make a hole at the start of the right neighbor block, then
2571 : * copy the last left block entry to the hole.
2572 : */
2573 37950299 : if (level > 0) {
2574 : /* It's a nonleaf. make a hole in the keys and ptrs */
2575 10838 : union xfs_btree_key *lkp;
2576 10838 : union xfs_btree_ptr *lpp;
2577 10838 : union xfs_btree_ptr *rpp;
2578 :
2579 10838 : lkp = xfs_btree_key_addr(cur, lrecs, left);
2580 10838 : lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2581 10838 : rkp = xfs_btree_key_addr(cur, 1, right);
2582 10838 : rpp = xfs_btree_ptr_addr(cur, 1, right);
2583 :
2584 817661 : for (i = rrecs - 1; i >= 0; i--) {
2585 806823 : error = xfs_btree_debug_check_ptr(cur, rpp, i, level);
2586 806823 : if (error)
2587 0 : goto error0;
2588 : }
2589 :
2590 10838 : xfs_btree_shift_keys(cur, rkp, 1, rrecs);
2591 10838 : xfs_btree_shift_ptrs(cur, rpp, 1, rrecs);
2592 :
2593 10838 : error = xfs_btree_debug_check_ptr(cur, lpp, 0, level);
2594 10838 : if (error)
2595 0 : goto error0;
2596 :
2597 : /* Now put the new data in, and log it. */
2598 10838 : xfs_btree_copy_keys(cur, rkp, lkp, 1);
2599 10838 : xfs_btree_copy_ptrs(cur, rpp, lpp, 1);
2600 :
2601 10838 : xfs_btree_log_keys(cur, rbp, 1, rrecs + 1);
2602 10838 : xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
2603 :
2604 10838 : ASSERT(cur->bc_ops->keys_inorder(cur, rkp,
2605 : xfs_btree_key_addr(cur, 2, right)));
2606 : } else {
2607 : /* It's a leaf. make a hole in the records */
2608 37939461 : union xfs_btree_rec *lrp;
2609 37939461 : union xfs_btree_rec *rrp;
2610 :
2611 37939461 : lrp = xfs_btree_rec_addr(cur, lrecs, left);
2612 37939461 : rrp = xfs_btree_rec_addr(cur, 1, right);
2613 :
2614 37939461 : xfs_btree_shift_recs(cur, rrp, 1, rrecs);
2615 :
2616 : /* Now put the new data in, and log it. */
2617 37939517 : xfs_btree_copy_recs(cur, rrp, lrp, 1);
2618 37939948 : xfs_btree_log_recs(cur, rbp, 1, rrecs + 1);
2619 : }
2620 :
2621 : /*
2622 : * Decrement and log left's numrecs, bump and log right's numrecs.
2623 : */
2624 37951289 : xfs_btree_set_numrecs(left, --lrecs);
2625 37951411 : xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2626 :
2627 37950543 : xfs_btree_set_numrecs(right, ++rrecs);
2628 37950614 : xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2629 :
2630 : /*
2631 : * Using a temporary cursor, update the parent key values of the
2632 : * block on the right.
2633 : */
2634 37950498 : error = xfs_btree_dup_cursor(cur, &tcur);
2635 37952601 : if (error)
2636 2 : goto error0;
2637 37952599 : i = xfs_btree_lastrec(tcur, level);
2638 37953343 : if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) {
2639 0 : error = -EFSCORRUPTED;
2640 0 : goto error0;
2641 : }
2642 :
2643 37953343 : error = xfs_btree_increment(tcur, level, &i);
2644 37953759 : if (error)
2645 0 : goto error1;
2646 :
2647 : /* Update the parent high keys of the left block, if needed. */
2648 37953759 : if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2649 11146533 : error = xfs_btree_update_keys(cur, level);
2650 11146535 : if (error)
2651 0 : goto error1;
2652 : }
2653 :
2654 : /* Update the parent keys of the right block. */
2655 37953761 : error = xfs_btree_update_keys(tcur, level);
2656 37953735 : if (error)
2657 0 : goto error1;
2658 :
2659 37953735 : xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2660 :
2661 37953735 : *stat = 1;
2662 37953735 : return 0;
2663 :
2664 48853465 : out0:
2665 48853465 : *stat = 0;
2666 48853465 : return 0;
2667 :
2668 : error0:
2669 : return error;
2670 :
2671 0 : error1:
2672 0 : xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2673 0 : return error;
2674 : }
2675 :
2676 : /*
2677 : * Split cur/level block in half.
2678 : * Return new block number and the key to its first
2679 : * record (to be inserted into parent).
2680 : */
2681 : STATIC int /* error */
2682 605533 : __xfs_btree_split(
2683 : struct xfs_btree_cur *cur,
2684 : int level,
2685 : union xfs_btree_ptr *ptrp,
2686 : union xfs_btree_key *key,
2687 : struct xfs_btree_cur **curp,
2688 : int *stat) /* success/failure */
2689 : {
2690 605533 : union xfs_btree_ptr lptr; /* left sibling block ptr */
2691 605533 : struct xfs_buf *lbp; /* left buffer pointer */
2692 605533 : struct xfs_btree_block *left; /* left btree block */
2693 605533 : union xfs_btree_ptr rptr; /* right sibling block ptr */
2694 605533 : struct xfs_buf *rbp; /* right buffer pointer */
2695 605533 : struct xfs_btree_block *right; /* right btree block */
2696 605533 : union xfs_btree_ptr rrptr; /* right-right sibling ptr */
2697 605533 : struct xfs_buf *rrbp; /* right-right buffer pointer */
2698 605533 : struct xfs_btree_block *rrblock; /* right-right btree block */
2699 605533 : int lrecs;
2700 605533 : int rrecs;
2701 605533 : int src_index;
2702 605533 : int error; /* error return value */
2703 605533 : int i;
2704 :
2705 605533 : XFS_BTREE_STATS_INC(cur, split);
2706 :
2707 : /* Set up left block (current one). */
2708 605533 : left = xfs_btree_get_block(cur, level, &lbp);
2709 :
2710 : #ifdef DEBUG
2711 605533 : error = xfs_btree_check_block(cur, left, level, lbp);
2712 605533 : if (error)
2713 0 : goto error0;
2714 : #endif
2715 :
2716 605533 : xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2717 :
2718 : /* Allocate the new block. If we can't do it, we're toast. Give up. */
2719 605533 : error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat);
2720 605533 : if (error)
2721 4 : goto error0;
2722 605529 : if (*stat == 0)
2723 0 : goto out0;
2724 605529 : XFS_BTREE_STATS_INC(cur, alloc);
2725 :
2726 : /* Set up the new block as "right". */
2727 605529 : error = xfs_btree_get_buf_block(cur, &rptr, &right, &rbp);
2728 605529 : if (error)
2729 0 : goto error0;
2730 :
2731 : /* Fill in the btree header for the new right block. */
2732 605529 : xfs_btree_init_block_cur(cur, rbp, xfs_btree_get_level(left), 0);
2733 :
2734 : /*
2735 : * Split the entries between the old and the new block evenly.
2736 : * Make sure that if there's an odd number of entries now, that
2737 : * each new block will have the same number of entries.
2738 : */
2739 605529 : lrecs = xfs_btree_get_numrecs(left);
2740 605529 : rrecs = lrecs / 2;
2741 605529 : if ((lrecs & 1) && cur->bc_levels[level].ptr <= rrecs + 1)
2742 19484 : rrecs++;
2743 605529 : src_index = (lrecs - rrecs + 1);
2744 :
2745 605529 : XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2746 :
2747 : /* Adjust numrecs for the later get_*_keys() calls. */
2748 605529 : lrecs -= rrecs;
2749 605529 : xfs_btree_set_numrecs(left, lrecs);
2750 605529 : xfs_btree_set_numrecs(right, xfs_btree_get_numrecs(right) + rrecs);
2751 :
2752 : /*
2753 : * Copy btree block entries from the left block over to the
2754 : * new block, the right. Update the right block and log the
2755 : * changes.
2756 : */
2757 605529 : if (level > 0) {
2758 : /* It's a non-leaf. Move keys and pointers. */
2759 1994 : union xfs_btree_key *lkp; /* left btree key */
2760 1994 : union xfs_btree_ptr *lpp; /* left address pointer */
2761 1994 : union xfs_btree_key *rkp; /* right btree key */
2762 1994 : union xfs_btree_ptr *rpp; /* right address pointer */
2763 :
2764 1994 : lkp = xfs_btree_key_addr(cur, src_index, left);
2765 1994 : lpp = xfs_btree_ptr_addr(cur, src_index, left);
2766 1994 : rkp = xfs_btree_key_addr(cur, 1, right);
2767 1994 : rpp = xfs_btree_ptr_addr(cur, 1, right);
2768 :
2769 3988 : for (i = src_index; i < rrecs; i++) {
2770 0 : error = xfs_btree_debug_check_ptr(cur, lpp, i, level);
2771 0 : if (error)
2772 0 : goto error0;
2773 : }
2774 :
2775 : /* Copy the keys & pointers to the new block. */
2776 1994 : xfs_btree_copy_keys(cur, rkp, lkp, rrecs);
2777 1994 : xfs_btree_copy_ptrs(cur, rpp, lpp, rrecs);
2778 :
2779 1994 : xfs_btree_log_keys(cur, rbp, 1, rrecs);
2780 1994 : xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2781 :
2782 : /* Stash the keys of the new block for later insertion. */
2783 1994 : xfs_btree_get_node_keys(cur, right, key);
2784 : } else {
2785 : /* It's a leaf. Move records. */
2786 603535 : union xfs_btree_rec *lrp; /* left record pointer */
2787 603535 : union xfs_btree_rec *rrp; /* right record pointer */
2788 :
2789 603535 : lrp = xfs_btree_rec_addr(cur, src_index, left);
2790 603535 : rrp = xfs_btree_rec_addr(cur, 1, right);
2791 :
2792 : /* Copy records to the new block. */
2793 603535 : xfs_btree_copy_recs(cur, rrp, lrp, rrecs);
2794 603535 : xfs_btree_log_recs(cur, rbp, 1, rrecs);
2795 :
2796 : /* Stash the keys of the new block for later insertion. */
2797 603535 : xfs_btree_get_leaf_keys(cur, right, key);
2798 : }
2799 :
2800 : /*
2801 : * Find the left block number by looking in the buffer.
2802 : * Adjust sibling pointers.
2803 : */
2804 605529 : xfs_btree_get_sibling(cur, left, &rrptr, XFS_BB_RIGHTSIB);
2805 605529 : xfs_btree_set_sibling(cur, right, &rrptr, XFS_BB_RIGHTSIB);
2806 605529 : xfs_btree_set_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2807 605529 : xfs_btree_set_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2808 :
2809 605529 : xfs_btree_log_block(cur, rbp, XFS_BB_ALL_BITS);
2810 605529 : xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
2811 :
2812 : /*
2813 : * If there's a block to the new block's right, make that block
2814 : * point back to right instead of to left.
2815 : */
2816 1211058 : if (!xfs_btree_ptr_is_null(cur, &rrptr)) {
2817 303588 : error = xfs_btree_read_buf_block(cur, &rrptr,
2818 : 0, &rrblock, &rrbp);
2819 303588 : if (error)
2820 257 : goto error0;
2821 303331 : xfs_btree_set_sibling(cur, rrblock, &rptr, XFS_BB_LEFTSIB);
2822 303331 : xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
2823 : }
2824 :
2825 : /* Update the parent high keys of the left block, if needed. */
2826 605272 : if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2827 290624 : error = xfs_btree_update_keys(cur, level);
2828 290624 : if (error)
2829 0 : goto error0;
2830 : }
2831 :
2832 : /*
2833 : * If the cursor is really in the right block, move it there.
2834 : * If it's just pointing past the last entry in left, then we'll
2835 : * insert there, so don't change anything in that case.
2836 : */
2837 605272 : if (cur->bc_levels[level].ptr > lrecs + 1) {
2838 471342 : xfs_btree_setbuf(cur, level, rbp);
2839 471342 : cur->bc_levels[level].ptr -= lrecs;
2840 : }
2841 : /*
2842 : * If there are more levels, we'll need another cursor which refers
2843 : * the right block, no matter where this cursor was.
2844 : */
2845 605272 : if (level + 1 < cur->bc_nlevels) {
2846 589648 : error = xfs_btree_dup_cursor(cur, curp);
2847 589648 : if (error)
2848 15 : goto error0;
2849 589633 : (*curp)->bc_levels[level + 1].ptr++;
2850 : }
2851 605257 : *ptrp = rptr;
2852 605257 : *stat = 1;
2853 605257 : return 0;
2854 : out0:
2855 0 : *stat = 0;
2856 0 : return 0;
2857 :
2858 : error0:
2859 : return error;
2860 : }
2861 :
2862 : #ifdef __KERNEL__
2863 : struct xfs_btree_split_args {
2864 : struct xfs_btree_cur *cur;
2865 : int level;
2866 : union xfs_btree_ptr *ptrp;
2867 : union xfs_btree_key *key;
2868 : struct xfs_btree_cur **curp;
2869 : int *stat; /* success/failure */
2870 : int result;
2871 : bool kswapd; /* allocation in kswapd context */
2872 : struct completion *done;
2873 : struct work_struct work;
2874 : };
2875 :
2876 : /*
2877 : * Stack switching interfaces for allocation
2878 : */
2879 : static void
2880 10350 : xfs_btree_split_worker(
2881 : struct work_struct *work)
2882 : {
2883 10350 : struct xfs_btree_split_args *args = container_of(work,
2884 : struct xfs_btree_split_args, work);
2885 10350 : unsigned long pflags;
2886 10350 : unsigned long new_pflags = 0;
2887 :
2888 : /*
2889 : * we are in a transaction context here, but may also be doing work
2890 : * in kswapd context, and hence we may need to inherit that state
2891 : * temporarily to ensure that we don't block waiting for memory reclaim
2892 : * in any way.
2893 : */
2894 10350 : if (args->kswapd)
2895 0 : new_pflags |= PF_MEMALLOC | PF_KSWAPD;
2896 :
2897 10350 : current_set_flags_nested(&pflags, new_pflags);
2898 10350 : xfs_trans_set_context(args->cur->bc_tp);
2899 :
2900 10350 : args->result = __xfs_btree_split(args->cur, args->level, args->ptrp,
2901 : args->key, args->curp, args->stat);
2902 :
2903 10350 : xfs_trans_clear_context(args->cur->bc_tp);
2904 10350 : current_restore_flags_nested(&pflags, new_pflags);
2905 :
2906 : /*
2907 : * Do not access args after complete() has run here. We don't own args
2908 : * and the owner may run and free args before we return here.
2909 : */
2910 10350 : complete(args->done);
2911 :
2912 10350 : }
2913 :
2914 : /*
2915 : * BMBT split requests often come in with little stack to work on so we push
2916 : * them off to a worker thread so there is lots of stack to use. For the other
2917 : * btree types, just call directly to avoid the context switch overhead here.
2918 : *
2919 : * Care must be taken here - the work queue rescuer thread introduces potential
2920 : * AGF <> worker queue deadlocks if the BMBT block allocation has to lock new
2921 : * AGFs to allocate blocks. A task being run by the rescuer could attempt to
2922 : * lock an AGF that is already locked by a task queued to run by the rescuer,
2923 : * resulting in an ABBA deadlock as the rescuer cannot run the lock holder to
2924 : * release it until the current thread it is running gains the lock.
2925 : *
2926 : * To avoid this issue, we only ever queue BMBT splits that don't have an AGF
2927 : * already locked to allocate from. The only place that doesn't hold an AGF
2928 : * locked is unwritten extent conversion at IO completion, but that has already
2929 : * been offloaded to a worker thread and hence has no stack consumption issues
2930 : * we have to worry about.
2931 : */
2932 : STATIC int /* error */
2933 605533 : xfs_btree_split(
2934 : struct xfs_btree_cur *cur,
2935 : int level,
2936 : union xfs_btree_ptr *ptrp,
2937 : union xfs_btree_key *key,
2938 : struct xfs_btree_cur **curp,
2939 : int *stat) /* success/failure */
2940 : {
2941 605533 : struct xfs_btree_split_args args;
2942 605533 : DECLARE_COMPLETION_ONSTACK(done);
2943 :
2944 605533 : if (cur->bc_btnum != XFS_BTNUM_BMAP ||
2945 204869 : cur->bc_tp->t_highest_agno == NULLAGNUMBER)
2946 595183 : return __xfs_btree_split(cur, level, ptrp, key, curp, stat);
2947 :
2948 10350 : args.cur = cur;
2949 10350 : args.level = level;
2950 10350 : args.ptrp = ptrp;
2951 10350 : args.key = key;
2952 10350 : args.curp = curp;
2953 10350 : args.stat = stat;
2954 10350 : args.done = &done;
2955 10350 : args.kswapd = current_is_kswapd();
2956 10350 : INIT_WORK_ONSTACK(&args.work, xfs_btree_split_worker);
2957 10350 : queue_work(xfs_alloc_wq, &args.work);
2958 10350 : wait_for_completion(&done);
2959 10350 : destroy_work_on_stack(&args.work);
2960 10350 : return args.result;
2961 : }
2962 : #else
2963 : #define xfs_btree_split __xfs_btree_split
2964 : #endif /* __KERNEL__ */
2965 :
2966 :
2967 : /*
2968 : * Copy the old inode root contents into a real block and make the
2969 : * broot point to it.
2970 : */
2971 : int /* error */
2972 2200 : xfs_btree_new_iroot(
2973 : struct xfs_btree_cur *cur, /* btree cursor */
2974 : int *logflags, /* logging flags for inode */
2975 : int *stat) /* return status - 0 fail */
2976 : {
2977 2200 : struct xfs_buf *cbp; /* buffer for cblock */
2978 2200 : struct xfs_btree_block *block; /* btree block */
2979 2200 : struct xfs_btree_block *cblock; /* child btree block */
2980 2200 : union xfs_btree_key *ckp; /* child key pointer */
2981 2200 : union xfs_btree_ptr *cpp; /* child ptr pointer */
2982 2200 : union xfs_btree_key *kp; /* pointer to btree key */
2983 2200 : union xfs_btree_ptr *pp; /* pointer to block addr */
2984 2200 : union xfs_btree_ptr nptr; /* new block addr */
2985 2200 : int level; /* btree level */
2986 2200 : int error; /* error return code */
2987 2200 : int i; /* loop counter */
2988 :
2989 2200 : XFS_BTREE_STATS_INC(cur, newroot);
2990 :
2991 2200 : ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
2992 :
2993 2200 : level = cur->bc_nlevels - 1;
2994 :
2995 2200 : block = xfs_btree_get_iroot(cur);
2996 2200 : pp = xfs_btree_ptr_addr(cur, 1, block);
2997 :
2998 : /* Allocate the new block. If we can't do it, we're toast. Give up. */
2999 2200 : error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat);
3000 2200 : if (error)
3001 0 : goto error0;
3002 2200 : if (*stat == 0)
3003 : return 0;
3004 :
3005 2200 : XFS_BTREE_STATS_INC(cur, alloc);
3006 :
3007 : /* Copy the root into a real block. */
3008 2200 : error = xfs_btree_get_buf_block(cur, &nptr, &cblock, &cbp);
3009 2200 : if (error)
3010 0 : goto error0;
3011 :
3012 : /*
3013 : * we can't just memcpy() the root in for CRC enabled btree blocks.
3014 : * In that case have to also ensure the blkno remains correct
3015 : */
3016 4400 : memcpy(cblock, block, xfs_btree_block_len(cur));
3017 2200 : if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
3018 2200 : __be64 bno = cpu_to_be64(xfs_buf_daddr(cbp));
3019 2200 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
3020 2200 : cblock->bb_u.l.bb_blkno = bno;
3021 : else
3022 0 : cblock->bb_u.s.bb_blkno = bno;
3023 : }
3024 :
3025 2200 : be16_add_cpu(&block->bb_level, 1);
3026 2200 : xfs_btree_set_numrecs(block, 1);
3027 2200 : cur->bc_nlevels++;
3028 2200 : ASSERT(cur->bc_nlevels <= cur->bc_maxlevels);
3029 2200 : cur->bc_levels[level + 1].ptr = 1;
3030 :
3031 2200 : kp = xfs_btree_key_addr(cur, 1, block);
3032 2200 : ckp = xfs_btree_key_addr(cur, 1, cblock);
3033 2200 : xfs_btree_copy_keys(cur, ckp, kp, xfs_btree_get_numrecs(cblock));
3034 :
3035 2200 : cpp = xfs_btree_ptr_addr(cur, 1, cblock);
3036 48400 : for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
3037 44000 : error = xfs_btree_debug_check_ptr(cur, pp, i, level);
3038 44000 : if (error)
3039 0 : goto error0;
3040 : }
3041 :
3042 2200 : xfs_btree_copy_ptrs(cur, cpp, pp, xfs_btree_get_numrecs(cblock));
3043 :
3044 2200 : error = xfs_btree_debug_check_ptr(cur, &nptr, 0, level);
3045 2200 : if (error)
3046 0 : goto error0;
3047 :
3048 2200 : xfs_btree_copy_ptrs(cur, pp, &nptr, 1);
3049 :
3050 2200 : xfs_iroot_realloc(cur->bc_ino.ip,
3051 2200 : 1 - xfs_btree_get_numrecs(cblock),
3052 2200 : cur->bc_ino.whichfork);
3053 :
3054 2200 : xfs_btree_setbuf(cur, level, cbp);
3055 :
3056 : /*
3057 : * Do all this logging at the end so that
3058 : * the root is at the right level.
3059 : */
3060 2200 : xfs_btree_log_block(cur, cbp, XFS_BB_ALL_BITS);
3061 2200 : xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
3062 2200 : xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
3063 :
3064 4400 : *logflags |=
3065 2200 : XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork);
3066 2200 : *stat = 1;
3067 2200 : return 0;
3068 : error0:
3069 : return error;
3070 : }
3071 :
3072 : /*
3073 : * Allocate a new root block, fill it in.
3074 : */
3075 : STATIC int /* error */
3076 15624 : xfs_btree_new_root(
3077 : struct xfs_btree_cur *cur, /* btree cursor */
3078 : int *stat) /* success/failure */
3079 : {
3080 15624 : struct xfs_btree_block *block; /* one half of the old root block */
3081 15624 : struct xfs_buf *bp; /* buffer containing block */
3082 15624 : int error; /* error return value */
3083 15624 : struct xfs_buf *lbp; /* left buffer pointer */
3084 15624 : struct xfs_btree_block *left; /* left btree block */
3085 15624 : struct xfs_buf *nbp; /* new (root) buffer */
3086 15624 : struct xfs_btree_block *new; /* new (root) btree block */
3087 15624 : int nptr; /* new value for key index, 1 or 2 */
3088 15624 : struct xfs_buf *rbp; /* right buffer pointer */
3089 15624 : struct xfs_btree_block *right; /* right btree block */
3090 15624 : union xfs_btree_ptr rptr;
3091 15624 : union xfs_btree_ptr lptr;
3092 :
3093 15624 : XFS_BTREE_STATS_INC(cur, newroot);
3094 :
3095 : /* initialise our start point from the cursor */
3096 15624 : cur->bc_ops->init_ptr_from_cur(cur, &rptr);
3097 :
3098 : /* Allocate the new block. If we can't do it, we're toast. Give up. */
3099 15624 : error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat);
3100 15624 : if (error)
3101 0 : goto error0;
3102 15624 : if (*stat == 0)
3103 0 : goto out0;
3104 15624 : XFS_BTREE_STATS_INC(cur, alloc);
3105 :
3106 : /* Set up the new block. */
3107 15624 : error = xfs_btree_get_buf_block(cur, &lptr, &new, &nbp);
3108 15624 : if (error)
3109 0 : goto error0;
3110 :
3111 : /* Set the root in the holding structure increasing the level by 1. */
3112 15624 : cur->bc_ops->set_root(cur, &lptr, 1);
3113 :
3114 : /*
3115 : * At the previous root level there are now two blocks: the old root,
3116 : * and the new block generated when it was split. We don't know which
3117 : * one the cursor is pointing at, so we set up variables "left" and
3118 : * "right" for each case.
3119 : */
3120 15624 : block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp);
3121 :
3122 : #ifdef DEBUG
3123 15624 : error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp);
3124 15624 : if (error)
3125 0 : goto error0;
3126 : #endif
3127 :
3128 15624 : xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3129 31248 : if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3130 : /* Our block is left, pick up the right block. */
3131 8303 : lbp = bp;
3132 8303 : xfs_btree_buf_to_ptr(cur, lbp, &lptr);
3133 8303 : left = block;
3134 8303 : error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
3135 8303 : if (error)
3136 0 : goto error0;
3137 8303 : bp = rbp;
3138 8303 : nptr = 1;
3139 : } else {
3140 : /* Our block is right, pick up the left block. */
3141 7321 : rbp = bp;
3142 7321 : xfs_btree_buf_to_ptr(cur, rbp, &rptr);
3143 7321 : right = block;
3144 7321 : xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
3145 7321 : error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
3146 7321 : if (error)
3147 0 : goto error0;
3148 7321 : bp = lbp;
3149 7321 : nptr = 2;
3150 : }
3151 :
3152 : /* Fill in the new block's btree header and log it. */
3153 15624 : xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2);
3154 15624 : xfs_btree_log_block(cur, nbp, XFS_BB_ALL_BITS);
3155 46872 : ASSERT(!xfs_btree_ptr_is_null(cur, &lptr) &&
3156 : !xfs_btree_ptr_is_null(cur, &rptr));
3157 :
3158 : /* Fill in the key data in the new root. */
3159 15624 : if (xfs_btree_get_level(left) > 0) {
3160 : /*
3161 : * Get the keys for the left block's keys and put them directly
3162 : * in the parent block. Do the same for the right block.
3163 : */
3164 244 : xfs_btree_get_node_keys(cur, left,
3165 : xfs_btree_key_addr(cur, 1, new));
3166 244 : xfs_btree_get_node_keys(cur, right,
3167 : xfs_btree_key_addr(cur, 2, new));
3168 : } else {
3169 : /*
3170 : * Get the keys for the left block's records and put them
3171 : * directly in the parent block. Do the same for the right
3172 : * block.
3173 : */
3174 15380 : xfs_btree_get_leaf_keys(cur, left,
3175 : xfs_btree_key_addr(cur, 1, new));
3176 15380 : xfs_btree_get_leaf_keys(cur, right,
3177 : xfs_btree_key_addr(cur, 2, new));
3178 : }
3179 15624 : xfs_btree_log_keys(cur, nbp, 1, 2);
3180 :
3181 : /* Fill in the pointer data in the new root. */
3182 15624 : xfs_btree_copy_ptrs(cur,
3183 : xfs_btree_ptr_addr(cur, 1, new), &lptr, 1);
3184 15624 : xfs_btree_copy_ptrs(cur,
3185 : xfs_btree_ptr_addr(cur, 2, new), &rptr, 1);
3186 15624 : xfs_btree_log_ptrs(cur, nbp, 1, 2);
3187 :
3188 : /* Fix up the cursor. */
3189 15624 : xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
3190 15624 : cur->bc_levels[cur->bc_nlevels].ptr = nptr;
3191 15624 : cur->bc_nlevels++;
3192 15624 : ASSERT(cur->bc_nlevels <= cur->bc_maxlevels);
3193 15624 : *stat = 1;
3194 15624 : return 0;
3195 : error0:
3196 : return error;
3197 : out0:
3198 0 : *stat = 0;
3199 0 : return 0;
3200 : }
3201 :
3202 : STATIC int
3203 66396420 : xfs_btree_make_block_unfull(
3204 : struct xfs_btree_cur *cur, /* btree cursor */
3205 : int level, /* btree level */
3206 : int numrecs,/* # of recs in block */
3207 : int *oindex,/* old tree index */
3208 : int *index, /* new tree index */
3209 : union xfs_btree_ptr *nptr, /* new btree ptr */
3210 : struct xfs_btree_cur **ncur, /* new btree cursor */
3211 : union xfs_btree_key *key, /* key of new block */
3212 : int *stat)
3213 : {
3214 66396420 : int error = 0;
3215 :
3216 66396420 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
3217 26940243 : level == cur->bc_nlevels - 1) {
3218 50919 : struct xfs_inode *ip = cur->bc_ino.ip;
3219 :
3220 50919 : if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) {
3221 : /* A root block that can be made bigger. */
3222 48719 : xfs_iroot_realloc(ip, 1, cur->bc_ino.whichfork);
3223 48719 : *stat = 1;
3224 : } else {
3225 : /* A root block that needs replacing */
3226 2200 : int logflags = 0;
3227 :
3228 2200 : error = xfs_btree_new_iroot(cur, &logflags, stat);
3229 2200 : if (error || *stat == 0)
3230 0 : return error;
3231 :
3232 2200 : xfs_trans_log_inode(cur->bc_tp, ip, logflags);
3233 : }
3234 :
3235 50919 : return 0;
3236 : }
3237 :
3238 : /* First, try shifting an entry to the right neighbor. */
3239 66345501 : error = xfs_btree_rshift(cur, level, stat);
3240 66345348 : if (error || *stat)
3241 : return error;
3242 :
3243 : /* Next, try shifting an entry to the left neighbor. */
3244 48853443 : error = xfs_btree_lshift(cur, level, stat);
3245 48853450 : if (error)
3246 : return error;
3247 :
3248 48853394 : if (*stat) {
3249 48247861 : *oindex = *index = cur->bc_levels[level].ptr;
3250 48247861 : return 0;
3251 : }
3252 :
3253 : /*
3254 : * Next, try splitting the current block in half.
3255 : *
3256 : * If this works we have to re-set our variables because we
3257 : * could be in a different block now.
3258 : */
3259 605533 : error = xfs_btree_split(cur, level, nptr, key, ncur, stat);
3260 605533 : if (error || *stat == 0)
3261 : return error;
3262 :
3263 :
3264 605257 : *index = cur->bc_levels[level].ptr;
3265 605257 : return 0;
3266 : }
3267 :
3268 : /*
3269 : * Insert one record/level. Return information to the caller
3270 : * allowing the next level up to proceed if necessary.
3271 : */
3272 : STATIC int
3273 323095678 : xfs_btree_insrec(
3274 : struct xfs_btree_cur *cur, /* btree cursor */
3275 : int level, /* level to insert record at */
3276 : union xfs_btree_ptr *ptrp, /* i/o: block number inserted */
3277 : union xfs_btree_rec *rec, /* record to insert */
3278 : union xfs_btree_key *key, /* i/o: block key for ptrp */
3279 : struct xfs_btree_cur **curp, /* output: new cursor replacing cur */
3280 : int *stat) /* success/failure */
3281 : {
3282 323095678 : struct xfs_btree_block *block; /* btree block */
3283 323095678 : struct xfs_buf *bp; /* buffer for block */
3284 323095678 : union xfs_btree_ptr nptr; /* new block ptr */
3285 323095678 : struct xfs_btree_cur *ncur = NULL; /* new btree cursor */
3286 323095678 : union xfs_btree_key nkey; /* new block key */
3287 323095678 : union xfs_btree_key *lkey;
3288 323095678 : int optr; /* old key/record index */
3289 323095678 : int ptr; /* key/record index */
3290 323095678 : int numrecs;/* number of records */
3291 323095678 : int error; /* error return value */
3292 323095678 : int i;
3293 323095678 : xfs_daddr_t old_bn;
3294 :
3295 323095678 : ncur = NULL;
3296 323095678 : lkey = &nkey;
3297 :
3298 : /*
3299 : * If we have an external root pointer, and we've made it to the
3300 : * root level, allocate a new root block and we're done.
3301 : */
3302 323095678 : if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
3303 264315559 : (level >= cur->bc_nlevels)) {
3304 15624 : error = xfs_btree_new_root(cur, stat);
3305 15624 : xfs_btree_set_ptr_null(cur, ptrp);
3306 :
3307 15624 : return error;
3308 : }
3309 :
3310 : /* If we're off the left edge, return failure. */
3311 323080054 : ptr = cur->bc_levels[level].ptr;
3312 323080054 : if (ptr == 0) {
3313 0 : *stat = 0;
3314 0 : return 0;
3315 : }
3316 :
3317 323080054 : optr = ptr;
3318 :
3319 323080054 : XFS_BTREE_STATS_INC(cur, insrec);
3320 :
3321 : /* Get pointers to the btree buffer and block. */
3322 323083610 : block = xfs_btree_get_block(cur, level, &bp);
3323 323078926 : old_bn = bp ? xfs_buf_daddr(bp) : XFS_BUF_DADDR_NULL;
3324 323078926 : numrecs = xfs_btree_get_numrecs(block);
3325 :
3326 : #ifdef DEBUG
3327 323078926 : error = xfs_btree_check_block(cur, block, level, bp);
3328 323085433 : if (error)
3329 0 : goto error0;
3330 :
3331 : /* Check that the new entry is being inserted in the right place. */
3332 323085433 : if (ptr <= numrecs) {
3333 247884209 : if (level == 0) {
3334 247593341 : ASSERT(cur->bc_ops->recs_inorder(cur, rec,
3335 : xfs_btree_rec_addr(cur, ptr, block)));
3336 : } else {
3337 290868 : ASSERT(cur->bc_ops->keys_inorder(cur, key,
3338 : xfs_btree_key_addr(cur, ptr, block)));
3339 : }
3340 : }
3341 : #endif
3342 :
3343 : /*
3344 : * If the block is full, we can't insert the new entry until we
3345 : * make the block un-full.
3346 : */
3347 323089280 : xfs_btree_set_ptr_null(cur, &nptr);
3348 323089280 : if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) {
3349 66396334 : error = xfs_btree_make_block_unfull(cur, level, numrecs,
3350 : &optr, &ptr, &nptr, &ncur, lkey, stat);
3351 66396422 : if (error || *stat == 0)
3352 467 : goto error0;
3353 : }
3354 :
3355 : /*
3356 : * The current block may have changed if the block was
3357 : * previously full and we have just made space in it.
3358 : */
3359 323086681 : block = xfs_btree_get_block(cur, level, &bp);
3360 323067492 : numrecs = xfs_btree_get_numrecs(block);
3361 :
3362 : #ifdef DEBUG
3363 323067492 : error = xfs_btree_check_block(cur, block, level, bp);
3364 323062123 : if (error)
3365 0 : goto error0;
3366 : #endif
3367 :
3368 : /*
3369 : * At this point we know there's room for our new entry in the block
3370 : * we're pointing at.
3371 : */
3372 323062123 : XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1);
3373 :
3374 323075904 : if (level > 0) {
3375 : /* It's a nonleaf. make a hole in the keys and ptrs */
3376 589628 : union xfs_btree_key *kp;
3377 589628 : union xfs_btree_ptr *pp;
3378 :
3379 589628 : kp = xfs_btree_key_addr(cur, ptr, block);
3380 589628 : pp = xfs_btree_ptr_addr(cur, ptr, block);
3381 :
3382 8730169 : for (i = numrecs - ptr; i >= 0; i--) {
3383 7550913 : error = xfs_btree_debug_check_ptr(cur, pp, i, level);
3384 7550913 : if (error)
3385 0 : goto error0;
3386 : }
3387 :
3388 589628 : xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1);
3389 589628 : xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1);
3390 :
3391 589628 : error = xfs_btree_debug_check_ptr(cur, ptrp, 0, level);
3392 589628 : if (error)
3393 0 : goto error0;
3394 :
3395 : /* Now put the new data in, bump numrecs and log it. */
3396 589628 : xfs_btree_copy_keys(cur, kp, key, 1);
3397 589628 : xfs_btree_copy_ptrs(cur, pp, ptrp, 1);
3398 589628 : numrecs++;
3399 589628 : xfs_btree_set_numrecs(block, numrecs);
3400 589628 : xfs_btree_log_ptrs(cur, bp, ptr, numrecs);
3401 589628 : xfs_btree_log_keys(cur, bp, ptr, numrecs);
3402 : #ifdef DEBUG
3403 589628 : if (ptr < numrecs) {
3404 290845 : ASSERT(cur->bc_ops->keys_inorder(cur, kp,
3405 : xfs_btree_key_addr(cur, ptr + 1, block)));
3406 : }
3407 : #endif
3408 : } else {
3409 : /* It's a leaf. make a hole in the records */
3410 322486276 : union xfs_btree_rec *rp;
3411 :
3412 322486276 : rp = xfs_btree_rec_addr(cur, ptr, block);
3413 :
3414 322486276 : xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1);
3415 :
3416 : /* Now put the new data in, bump numrecs and log it. */
3417 322481960 : xfs_btree_copy_recs(cur, rp, rec, 1);
3418 322487709 : xfs_btree_set_numrecs(block, ++numrecs);
3419 322488602 : xfs_btree_log_recs(cur, bp, ptr, numrecs);
3420 : #ifdef DEBUG
3421 322485848 : if (ptr < numrecs) {
3422 247594910 : ASSERT(cur->bc_ops->recs_inorder(cur, rp,
3423 : xfs_btree_rec_addr(cur, ptr + 1, block)));
3424 : }
3425 : #endif
3426 : }
3427 :
3428 : /* Log the new number of records in the btree header. */
3429 323077858 : xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3430 :
3431 : /*
3432 : * If we just inserted into a new tree block, we have to
3433 : * recalculate nkey here because nkey is out of date.
3434 : *
3435 : * Otherwise we're just updating an existing block (having shoved
3436 : * some records into the new tree block), so use the regular key
3437 : * update mechanism.
3438 : */
3439 323086587 : if (bp && xfs_buf_daddr(bp) != old_bn) {
3440 473538 : xfs_btree_get_keys(cur, block, lkey);
3441 531636150 : } else if (xfs_btree_needs_key_update(cur, optr)) {
3442 124994759 : error = xfs_btree_update_keys(cur, level);
3443 124994160 : if (error)
3444 0 : goto error0;
3445 : }
3446 :
3447 : /*
3448 : * If we are tracking the last record in the tree and
3449 : * we are at the far right edge of the tree, update it.
3450 : */
3451 323085988 : if (xfs_btree_is_lastrec(cur, block, level)) {
3452 69238937 : cur->bc_ops->update_lastrec(cur, block, rec,
3453 : ptr, LASTREC_INSREC);
3454 : }
3455 :
3456 : /*
3457 : * Return the new block number, if any.
3458 : * If there is one, give back a record value and a cursor too.
3459 : */
3460 323089228 : *ptrp = nptr;
3461 646178456 : if (!xfs_btree_ptr_is_null(cur, &nptr)) {
3462 605257 : xfs_btree_copy_keys(cur, key, lkey, 1);
3463 605257 : *curp = ncur;
3464 : }
3465 :
3466 323089228 : *stat = 1;
3467 323089228 : return 0;
3468 :
3469 467 : error0:
3470 467 : if (ncur)
3471 0 : xfs_btree_del_cursor(ncur, error);
3472 : return error;
3473 : }
3474 :
3475 : /*
3476 : * Insert the record at the point referenced by cur.
3477 : *
3478 : * A multi-level split of the tree on insert will invalidate the original
3479 : * cursor. All callers of this function should assume that the cursor is
3480 : * no longer valid and revalidate it.
3481 : */
3482 : int
3483 322494713 : xfs_btree_insert(
3484 : struct xfs_btree_cur *cur,
3485 : int *stat)
3486 : {
3487 322494713 : int error; /* error return value */
3488 322494713 : int i; /* result value, 0 for failure */
3489 322494713 : int level; /* current level number in btree */
3490 322494713 : union xfs_btree_ptr nptr; /* new block number (split result) */
3491 322494713 : struct xfs_btree_cur *ncur; /* new cursor (split result) */
3492 322494713 : struct xfs_btree_cur *pcur; /* previous level's cursor */
3493 322494713 : union xfs_btree_key bkey; /* key of block to insert */
3494 322494713 : union xfs_btree_key *key;
3495 322494713 : union xfs_btree_rec rec; /* record to insert */
3496 :
3497 322494713 : level = 0;
3498 322494713 : ncur = NULL;
3499 322494713 : pcur = cur;
3500 322494713 : key = &bkey;
3501 :
3502 322494713 : xfs_btree_set_ptr_null(cur, &nptr);
3503 :
3504 : /* Make a key out of the record data to be inserted, and save it. */
3505 322494713 : cur->bc_ops->init_rec_from_cur(cur, &rec);
3506 322493407 : cur->bc_ops->init_key_from_rec(key, &rec);
3507 :
3508 : /*
3509 : * Loop going up the tree, starting at the leaf level.
3510 : * Stop when we don't get a split block, that must mean that
3511 : * the insert is finished with this level.
3512 : */
3513 323104055 : do {
3514 : /*
3515 : * Insert nrec/nptr into this level of the tree.
3516 : * Note if we fail, nptr will be null.
3517 : */
3518 323104055 : error = xfs_btree_insrec(pcur, level, &nptr, &rec, key,
3519 : &ncur, &i);
3520 323100540 : if (error) {
3521 467 : if (pcur != cur)
3522 5 : xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
3523 467 : goto error0;
3524 : }
3525 :
3526 323100073 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3527 0 : error = -EFSCORRUPTED;
3528 0 : goto error0;
3529 : }
3530 323100073 : level++;
3531 :
3532 : /*
3533 : * See if the cursor we just used is trash.
3534 : * Can't trash the caller's cursor, but otherwise we should
3535 : * if ncur is a new cursor or we're about to be done.
3536 : */
3537 323100073 : if (pcur != cur &&
3538 1177994 : (ncur || xfs_btree_ptr_is_null(cur, &nptr))) {
3539 : /* Save the state from the cursor before we trash it */
3540 589628 : if (cur->bc_ops->update_cursor)
3541 204865 : cur->bc_ops->update_cursor(pcur, cur);
3542 589628 : cur->bc_nlevels = pcur->bc_nlevels;
3543 589628 : xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
3544 : }
3545 : /* If we got a new cursor, switch to it. */
3546 323105762 : if (ncur) {
3547 594997 : pcur = ncur;
3548 594997 : ncur = NULL;
3549 : }
3550 646211524 : } while (!xfs_btree_ptr_is_null(cur, &nptr));
3551 :
3552 322495151 : *stat = i;
3553 322495151 : return 0;
3554 : error0:
3555 : return error;
3556 : }
3557 :
3558 : /*
3559 : * Try to merge a non-leaf block back into the inode root.
3560 : *
3561 : * Note: the killroot names comes from the fact that we're effectively
3562 : * killing the old root block. But because we can't just delete the
3563 : * inode we have to copy the single block it was pointing to into the
3564 : * inode.
3565 : */
3566 : STATIC int
3567 1971545 : xfs_btree_kill_iroot(
3568 : struct xfs_btree_cur *cur)
3569 : {
3570 1971545 : int whichfork = cur->bc_ino.whichfork;
3571 1971545 : struct xfs_inode *ip = cur->bc_ino.ip;
3572 1971545 : struct xfs_ifork *ifp = xfs_ifork_ptr(ip, whichfork);
3573 1971543 : struct xfs_btree_block *block;
3574 1971543 : struct xfs_btree_block *cblock;
3575 1971543 : union xfs_btree_key *kp;
3576 1971543 : union xfs_btree_key *ckp;
3577 1971543 : union xfs_btree_ptr *pp;
3578 1971543 : union xfs_btree_ptr *cpp;
3579 1971543 : struct xfs_buf *cbp;
3580 1971543 : int level;
3581 1971543 : int index;
3582 1971543 : int numrecs;
3583 1971543 : int error;
3584 : #ifdef DEBUG
3585 1971543 : union xfs_btree_ptr ptr;
3586 : #endif
3587 1971543 : int i;
3588 :
3589 1971543 : ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
3590 1971543 : ASSERT(cur->bc_nlevels > 1);
3591 :
3592 : /*
3593 : * Don't deal with the root block needs to be a leaf case.
3594 : * We're just going to turn the thing back into extents anyway.
3595 : */
3596 1971543 : level = cur->bc_nlevels - 1;
3597 1971543 : if (level == 1)
3598 1879020 : goto out0;
3599 :
3600 : /*
3601 : * Give up if the root has multiple children.
3602 : */
3603 92523 : block = xfs_btree_get_iroot(cur);
3604 92523 : if (xfs_btree_get_numrecs(block) != 1)
3605 5 : goto out0;
3606 :
3607 92518 : cblock = xfs_btree_get_block(cur, level - 1, &cbp);
3608 92518 : numrecs = xfs_btree_get_numrecs(cblock);
3609 :
3610 : /*
3611 : * Only do this if the next level will fit.
3612 : * Then the data must be copied up to the inode,
3613 : * instead of freeing the root you free the next level.
3614 : */
3615 92518 : if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level))
3616 90495 : goto out0;
3617 :
3618 2023 : XFS_BTREE_STATS_INC(cur, killroot);
3619 :
3620 : #ifdef DEBUG
3621 2023 : xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
3622 4046 : ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3623 2023 : xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
3624 4046 : ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3625 : #endif
3626 :
3627 2023 : index = numrecs - cur->bc_ops->get_maxrecs(cur, level);
3628 2023 : if (index) {
3629 2023 : xfs_iroot_realloc(cur->bc_ino.ip, index,
3630 2023 : cur->bc_ino.whichfork);
3631 2023 : block = ifp->if_broot;
3632 : }
3633 :
3634 2023 : be16_add_cpu(&block->bb_numrecs, index);
3635 2023 : ASSERT(block->bb_numrecs == cblock->bb_numrecs);
3636 :
3637 2023 : kp = xfs_btree_key_addr(cur, 1, block);
3638 2023 : ckp = xfs_btree_key_addr(cur, 1, cblock);
3639 2023 : xfs_btree_copy_keys(cur, kp, ckp, numrecs);
3640 :
3641 2023 : pp = xfs_btree_ptr_addr(cur, 1, block);
3642 2023 : cpp = xfs_btree_ptr_addr(cur, 1, cblock);
3643 :
3644 44506 : for (i = 0; i < numrecs; i++) {
3645 40460 : error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1);
3646 40460 : if (error)
3647 0 : return error;
3648 : }
3649 :
3650 2023 : xfs_btree_copy_ptrs(cur, pp, cpp, numrecs);
3651 :
3652 2023 : error = xfs_btree_free_block(cur, cbp);
3653 2023 : if (error)
3654 : return error;
3655 :
3656 2023 : cur->bc_levels[level - 1].bp = NULL;
3657 2023 : be16_add_cpu(&block->bb_level, -1);
3658 4046 : xfs_trans_log_inode(cur->bc_tp, ip,
3659 2023 : XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork));
3660 2023 : cur->bc_nlevels--;
3661 : out0:
3662 : return 0;
3663 : }
3664 :
3665 : /*
3666 : * Kill the current root node, and replace it with it's only child node.
3667 : */
3668 : STATIC int
3669 13327 : xfs_btree_kill_root(
3670 : struct xfs_btree_cur *cur,
3671 : struct xfs_buf *bp,
3672 : int level,
3673 : union xfs_btree_ptr *newroot)
3674 : {
3675 13327 : int error;
3676 :
3677 13327 : XFS_BTREE_STATS_INC(cur, killroot);
3678 :
3679 : /*
3680 : * Update the root pointer, decreasing the level by 1 and then
3681 : * free the old root.
3682 : */
3683 13327 : cur->bc_ops->set_root(cur, newroot, -1);
3684 :
3685 13327 : error = xfs_btree_free_block(cur, bp);
3686 13327 : if (error)
3687 : return error;
3688 :
3689 13327 : cur->bc_levels[level].bp = NULL;
3690 13327 : cur->bc_levels[level].ra = 0;
3691 13327 : cur->bc_nlevels--;
3692 :
3693 13327 : return 0;
3694 : }
3695 :
3696 : STATIC int
3697 148841078 : xfs_btree_dec_cursor(
3698 : struct xfs_btree_cur *cur,
3699 : int level,
3700 : int *stat)
3701 : {
3702 148841078 : int error;
3703 148841078 : int i;
3704 :
3705 148841078 : if (level > 0) {
3706 318049 : error = xfs_btree_decrement(cur, level, &i);
3707 318049 : if (error)
3708 : return error;
3709 : }
3710 :
3711 148841078 : *stat = 1;
3712 148841078 : return 0;
3713 : }
3714 :
3715 : /*
3716 : * Single level of the btree record deletion routine.
3717 : * Delete record pointed to by cur/level.
3718 : * Remove the record from its block then rebalance the tree.
3719 : * Return 0 for error, 1 for done, 2 to go on to the next level.
3720 : */
3721 : STATIC int /* error */
3722 253585403 : xfs_btree_delrec(
3723 : struct xfs_btree_cur *cur, /* btree cursor */
3724 : int level, /* level removing record from */
3725 : int *stat) /* fail/done/go-on */
3726 : {
3727 253585403 : struct xfs_btree_block *block; /* btree block */
3728 253585403 : union xfs_btree_ptr cptr; /* current block ptr */
3729 253585403 : struct xfs_buf *bp; /* buffer for block */
3730 253585403 : int error; /* error return value */
3731 253585403 : int i; /* loop counter */
3732 253585403 : union xfs_btree_ptr lptr; /* left sibling block ptr */
3733 253585403 : struct xfs_buf *lbp; /* left buffer pointer */
3734 253585403 : struct xfs_btree_block *left; /* left btree block */
3735 253585403 : int lrecs = 0; /* left record count */
3736 253585403 : int ptr; /* key/record index */
3737 253585403 : union xfs_btree_ptr rptr; /* right sibling block ptr */
3738 253585403 : struct xfs_buf *rbp; /* right buffer pointer */
3739 253585403 : struct xfs_btree_block *right; /* right btree block */
3740 253585403 : struct xfs_btree_block *rrblock; /* right-right btree block */
3741 253585403 : struct xfs_buf *rrbp; /* right-right buffer pointer */
3742 253585403 : int rrecs = 0; /* right record count */
3743 253585403 : struct xfs_btree_cur *tcur; /* temporary btree cursor */
3744 253585403 : int numrecs; /* temporary numrec count */
3745 :
3746 253585403 : tcur = NULL;
3747 :
3748 : /* Get the index of the entry being deleted, check for nothing there. */
3749 253585403 : ptr = cur->bc_levels[level].ptr;
3750 253585403 : if (ptr == 0) {
3751 0 : *stat = 0;
3752 0 : return 0;
3753 : }
3754 :
3755 : /* Get the buffer & block containing the record or key/ptr. */
3756 253585403 : block = xfs_btree_get_block(cur, level, &bp);
3757 253586187 : numrecs = xfs_btree_get_numrecs(block);
3758 :
3759 : #ifdef DEBUG
3760 253586187 : error = xfs_btree_check_block(cur, block, level, bp);
3761 253588317 : if (error)
3762 0 : goto error0;
3763 : #endif
3764 :
3765 : /* Fail if we're off the end of the block. */
3766 253588317 : if (ptr > numrecs) {
3767 0 : *stat = 0;
3768 0 : return 0;
3769 : }
3770 :
3771 253588317 : XFS_BTREE_STATS_INC(cur, delrec);
3772 253592784 : XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr);
3773 :
3774 : /* Excise the entries being deleted. */
3775 253593079 : if (level > 0) {
3776 : /* It's a nonleaf. operate on keys and ptrs */
3777 332546 : union xfs_btree_key *lkp;
3778 332546 : union xfs_btree_ptr *lpp;
3779 :
3780 332546 : lkp = xfs_btree_key_addr(cur, ptr + 1, block);
3781 332546 : lpp = xfs_btree_ptr_addr(cur, ptr + 1, block);
3782 :
3783 6095966 : for (i = 0; i < numrecs - ptr; i++) {
3784 5763420 : error = xfs_btree_debug_check_ptr(cur, lpp, i, level);
3785 5763420 : if (error)
3786 0 : goto error0;
3787 : }
3788 :
3789 332546 : if (ptr < numrecs) {
3790 160681 : xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr);
3791 160681 : xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr);
3792 160681 : xfs_btree_log_keys(cur, bp, ptr, numrecs - 1);
3793 160681 : xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1);
3794 : }
3795 : } else {
3796 : /* It's a leaf. operate on records */
3797 253260533 : if (ptr < numrecs) {
3798 203682324 : xfs_btree_shift_recs(cur,
3799 : xfs_btree_rec_addr(cur, ptr + 1, block),
3800 : -1, numrecs - ptr);
3801 203684185 : xfs_btree_log_recs(cur, bp, ptr, numrecs - 1);
3802 : }
3803 : }
3804 :
3805 : /*
3806 : * Decrement and log the number of entries in the block.
3807 : */
3808 253595604 : xfs_btree_set_numrecs(block, --numrecs);
3809 253590120 : xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3810 :
3811 : /*
3812 : * If we are tracking the last record in the tree and
3813 : * we are at the far right edge of the tree, update it.
3814 : */
3815 253591490 : if (xfs_btree_is_lastrec(cur, block, level)) {
3816 64775516 : cur->bc_ops->update_lastrec(cur, block, NULL,
3817 : ptr, LASTREC_DELREC);
3818 : }
3819 :
3820 : /*
3821 : * We're at the root level. First, shrink the root block in-memory.
3822 : * Try to get rid of the next level down. If we can't then there's
3823 : * nothing left to do.
3824 : */
3825 253591751 : if (level == cur->bc_nlevels - 1) {
3826 84084285 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3827 44267 : xfs_iroot_realloc(cur->bc_ino.ip, -1,
3828 44267 : cur->bc_ino.whichfork);
3829 :
3830 44267 : error = xfs_btree_kill_iroot(cur);
3831 44267 : if (error)
3832 0 : goto error0;
3833 :
3834 44267 : error = xfs_btree_dec_cursor(cur, level, stat);
3835 44267 : if (error)
3836 0 : goto error0;
3837 44267 : *stat = 1;
3838 44267 : return 0;
3839 : }
3840 :
3841 : /*
3842 : * If this is the root level, and there's only one entry left,
3843 : * and it's NOT the leaf level, then we can get rid of this
3844 : * level.
3845 : */
3846 84040018 : if (numrecs == 1 && level > 0) {
3847 13327 : union xfs_btree_ptr *pp;
3848 : /*
3849 : * pp is still set to the first pointer in the block.
3850 : * Make it the new root of the btree.
3851 : */
3852 13327 : pp = xfs_btree_ptr_addr(cur, 1, block);
3853 13327 : error = xfs_btree_kill_root(cur, bp, level, pp);
3854 13327 : if (error)
3855 0 : goto error0;
3856 84026691 : } else if (level > 0) {
3857 82196 : error = xfs_btree_dec_cursor(cur, level, stat);
3858 82196 : if (error)
3859 0 : goto error0;
3860 : }
3861 84040018 : *stat = 1;
3862 84040018 : return 0;
3863 : }
3864 :
3865 : /*
3866 : * If we deleted the leftmost entry in the block, update the
3867 : * key values above us in the tree.
3868 : */
3869 261242194 : if (xfs_btree_needs_key_update(cur, ptr)) {
3870 81147010 : error = xfs_btree_update_keys(cur, level);
3871 81147043 : if (error)
3872 0 : goto error0;
3873 : }
3874 :
3875 : /*
3876 : * If the number of records remaining in the block is at least
3877 : * the minimum, we're done.
3878 : */
3879 169507499 : if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {
3880 138702944 : error = xfs_btree_dec_cursor(cur, level, stat);
3881 138702728 : if (error)
3882 0 : goto error0;
3883 : return 0;
3884 : }
3885 :
3886 : /*
3887 : * Otherwise, we have to move some records around to keep the
3888 : * tree balanced. Look at the left and right sibling blocks to
3889 : * see if we can re-balance by moving only one record.
3890 : */
3891 30806251 : xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3892 30806257 : xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB);
3893 :
3894 30806269 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3895 : /*
3896 : * One child of root, need to get a chance to copy its contents
3897 : * into the root and delete it. Can't go up to next level,
3898 : * there's nothing to delete there.
3899 : */
3900 57317093 : if (xfs_btree_ptr_is_null(cur, &rptr) &&
3901 1927278 : xfs_btree_ptr_is_null(cur, &lptr) &&
3902 1927278 : level == cur->bc_nlevels - 2) {
3903 1927278 : error = xfs_btree_kill_iroot(cur);
3904 1927278 : if (!error)
3905 1927279 : error = xfs_btree_dec_cursor(cur, level, stat);
3906 1927270 : if (error)
3907 0 : goto error0;
3908 : return 0;
3909 : }
3910 : }
3911 :
3912 75277394 : ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) ||
3913 : !xfs_btree_ptr_is_null(cur, &lptr));
3914 :
3915 : /*
3916 : * Duplicate the cursor so our btree manipulations here won't
3917 : * disrupt the next level up.
3918 : */
3919 28878991 : error = xfs_btree_dup_cursor(cur, &tcur);
3920 28878993 : if (error)
3921 1 : goto error0;
3922 :
3923 : /*
3924 : * If there's a right sibling, see if it's ok to shift an entry
3925 : * out of it.
3926 : */
3927 57757984 : if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3928 : /*
3929 : * Move the temp cursor to the last entry in the next block.
3930 : * Actually any entry but the first would suffice.
3931 : */
3932 11359581 : i = xfs_btree_lastrec(tcur, level);
3933 11359586 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3934 0 : error = -EFSCORRUPTED;
3935 0 : goto error0;
3936 : }
3937 :
3938 11359586 : error = xfs_btree_increment(tcur, level, &i);
3939 11359583 : if (error)
3940 3 : goto error0;
3941 11359580 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3942 0 : error = -EFSCORRUPTED;
3943 0 : goto error0;
3944 : }
3945 :
3946 11359580 : i = xfs_btree_lastrec(tcur, level);
3947 11359582 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3948 0 : error = -EFSCORRUPTED;
3949 0 : goto error0;
3950 : }
3951 :
3952 : /* Grab a pointer to the block. */
3953 11359582 : right = xfs_btree_get_block(tcur, level, &rbp);
3954 : #ifdef DEBUG
3955 11359584 : error = xfs_btree_check_block(tcur, right, level, rbp);
3956 11359583 : if (error)
3957 0 : goto error0;
3958 : #endif
3959 : /* Grab the current block number, for future use. */
3960 11359583 : xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB);
3961 :
3962 : /*
3963 : * If right block is full enough so that removing one entry
3964 : * won't make it too empty, and left-shifting an entry out
3965 : * of right to us works, we're done.
3966 : */
3967 11359580 : if (xfs_btree_get_numrecs(right) - 1 >=
3968 11359583 : cur->bc_ops->get_minrecs(tcur, level)) {
3969 8084597 : error = xfs_btree_lshift(tcur, level, &i);
3970 8084600 : if (error)
3971 0 : goto error0;
3972 8084600 : if (i) {
3973 8084598 : ASSERT(xfs_btree_get_numrecs(block) >=
3974 : cur->bc_ops->get_minrecs(tcur, level));
3975 :
3976 8084599 : xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3977 8084599 : tcur = NULL;
3978 :
3979 8084599 : error = xfs_btree_dec_cursor(cur, level, stat);
3980 8084600 : if (error)
3981 0 : goto error0;
3982 : return 0;
3983 : }
3984 : }
3985 :
3986 : /*
3987 : * Otherwise, grab the number of records in right for
3988 : * future reference, and fix up the temp cursor to point
3989 : * to our block again (last record).
3990 : */
3991 3274985 : rrecs = xfs_btree_get_numrecs(right);
3992 6549970 : if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3993 3257608 : i = xfs_btree_firstrec(tcur, level);
3994 3257608 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3995 0 : error = -EFSCORRUPTED;
3996 0 : goto error0;
3997 : }
3998 :
3999 3257608 : error = xfs_btree_decrement(tcur, level, &i);
4000 3257608 : if (error)
4001 0 : goto error0;
4002 3257608 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
4003 0 : error = -EFSCORRUPTED;
4004 0 : goto error0;
4005 : }
4006 : }
4007 : }
4008 :
4009 : /*
4010 : * If there's a left sibling, see if it's ok to shift an entry
4011 : * out of it.
4012 : */
4013 41588792 : if (!xfs_btree_ptr_is_null(cur, &lptr)) {
4014 : /*
4015 : * Move the temp cursor to the first entry in the
4016 : * previous block.
4017 : */
4018 20777001 : i = xfs_btree_firstrec(tcur, level);
4019 20776992 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
4020 0 : error = -EFSCORRUPTED;
4021 0 : goto error0;
4022 : }
4023 :
4024 20776992 : error = xfs_btree_decrement(tcur, level, &i);
4025 20777008 : if (error)
4026 0 : goto error0;
4027 20777008 : i = xfs_btree_firstrec(tcur, level);
4028 20777015 : if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
4029 0 : error = -EFSCORRUPTED;
4030 0 : goto error0;
4031 : }
4032 :
4033 : /* Grab a pointer to the block. */
4034 20777015 : left = xfs_btree_get_block(tcur, level, &lbp);
4035 : #ifdef DEBUG
4036 20777017 : error = xfs_btree_check_block(cur, left, level, lbp);
4037 20777015 : if (error)
4038 0 : goto error0;
4039 : #endif
4040 : /* Grab the current block number, for future use. */
4041 20777015 : xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB);
4042 :
4043 : /*
4044 : * If left block is full enough so that removing one entry
4045 : * won't make it too empty, and right-shifting an entry out
4046 : * of left to us works, we're done.
4047 : */
4048 20777018 : if (xfs_btree_get_numrecs(left) - 1 >=
4049 20777017 : cur->bc_ops->get_minrecs(tcur, level)) {
4050 20461848 : error = xfs_btree_rshift(tcur, level, &i);
4051 20461849 : if (error)
4052 0 : goto error0;
4053 20461849 : if (i) {
4054 20461850 : ASSERT(xfs_btree_get_numrecs(block) >=
4055 : cur->bc_ops->get_minrecs(tcur, level));
4056 20461850 : xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
4057 20461851 : tcur = NULL;
4058 20461851 : if (level == 0)
4059 20460913 : cur->bc_levels[0].ptr++;
4060 :
4061 20461851 : *stat = 1;
4062 20461851 : return 0;
4063 : }
4064 : }
4065 :
4066 : /*
4067 : * Otherwise, grab the number of records in right for
4068 : * future reference.
4069 : */
4070 315169 : lrecs = xfs_btree_get_numrecs(left);
4071 : }
4072 :
4073 : /* Delete the temp cursor, we're done with it. */
4074 332564 : xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
4075 332546 : tcur = NULL;
4076 :
4077 : /* If here, we need to do a join to keep the tree balanced. */
4078 665092 : ASSERT(!xfs_btree_ptr_is_null(cur, &cptr));
4079 :
4080 980261 : if (!xfs_btree_ptr_is_null(cur, &lptr) &&
4081 315169 : lrecs + xfs_btree_get_numrecs(block) <=
4082 315169 : cur->bc_ops->get_maxrecs(cur, level)) {
4083 : /*
4084 : * Set "right" to be the starting block,
4085 : * "left" to be the left neighbor.
4086 : */
4087 315169 : rptr = cptr;
4088 315169 : right = block;
4089 315169 : rbp = bp;
4090 315169 : error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
4091 315169 : if (error)
4092 0 : goto error0;
4093 :
4094 : /*
4095 : * If that won't work, see if we can join with the right neighbor block.
4096 : */
4097 52131 : } else if (!xfs_btree_ptr_is_null(cur, &rptr) &&
4098 17377 : rrecs + xfs_btree_get_numrecs(block) <=
4099 17377 : cur->bc_ops->get_maxrecs(cur, level)) {
4100 : /*
4101 : * Set "left" to be the starting block,
4102 : * "right" to be the right neighbor.
4103 : */
4104 17377 : lptr = cptr;
4105 17377 : left = block;
4106 17377 : lbp = bp;
4107 17377 : error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
4108 17377 : if (error)
4109 0 : goto error0;
4110 :
4111 : /*
4112 : * Otherwise, we can't fix the imbalance.
4113 : * Just return. This is probably a logic error, but it's not fatal.
4114 : */
4115 : } else {
4116 0 : error = xfs_btree_dec_cursor(cur, level, stat);
4117 0 : if (error)
4118 0 : goto error0;
4119 : return 0;
4120 : }
4121 :
4122 332546 : rrecs = xfs_btree_get_numrecs(right);
4123 332546 : lrecs = xfs_btree_get_numrecs(left);
4124 :
4125 : /*
4126 : * We're now going to join "left" and "right" by moving all the stuff
4127 : * in "right" to "left" and deleting "right".
4128 : */
4129 332546 : XFS_BTREE_STATS_ADD(cur, moves, rrecs);
4130 332546 : if (level > 0) {
4131 : /* It's a non-leaf. Move keys and pointers. */
4132 232 : union xfs_btree_key *lkp; /* left btree key */
4133 232 : union xfs_btree_ptr *lpp; /* left address pointer */
4134 232 : union xfs_btree_key *rkp; /* right btree key */
4135 232 : union xfs_btree_ptr *rpp; /* right address pointer */
4136 :
4137 232 : lkp = xfs_btree_key_addr(cur, lrecs + 1, left);
4138 232 : lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left);
4139 232 : rkp = xfs_btree_key_addr(cur, 1, right);
4140 232 : rpp = xfs_btree_ptr_addr(cur, 1, right);
4141 :
4142 12405 : for (i = 1; i < rrecs; i++) {
4143 12173 : error = xfs_btree_debug_check_ptr(cur, rpp, i, level);
4144 12173 : if (error)
4145 0 : goto error0;
4146 : }
4147 :
4148 232 : xfs_btree_copy_keys(cur, lkp, rkp, rrecs);
4149 232 : xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs);
4150 :
4151 232 : xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
4152 232 : xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
4153 : } else {
4154 : /* It's a leaf. Move records. */
4155 332314 : union xfs_btree_rec *lrp; /* left record pointer */
4156 332314 : union xfs_btree_rec *rrp; /* right record pointer */
4157 :
4158 332314 : lrp = xfs_btree_rec_addr(cur, lrecs + 1, left);
4159 332314 : rrp = xfs_btree_rec_addr(cur, 1, right);
4160 :
4161 332314 : xfs_btree_copy_recs(cur, lrp, rrp, rrecs);
4162 332314 : xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
4163 : }
4164 :
4165 332546 : XFS_BTREE_STATS_INC(cur, join);
4166 :
4167 : /*
4168 : * Fix up the number of records and right block pointer in the
4169 : * surviving block, and log it.
4170 : */
4171 332546 : xfs_btree_set_numrecs(left, lrecs + rrecs);
4172 332546 : xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB);
4173 332546 : xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
4174 332546 : xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
4175 :
4176 : /* If there is a right sibling, point it to the remaining block. */
4177 332546 : xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
4178 665092 : if (!xfs_btree_ptr_is_null(cur, &cptr)) {
4179 161533 : error = xfs_btree_read_buf_block(cur, &cptr, 0, &rrblock, &rrbp);
4180 161533 : if (error)
4181 0 : goto error0;
4182 161533 : xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB);
4183 161533 : xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
4184 : }
4185 :
4186 : /* Free the deleted block. */
4187 332546 : error = xfs_btree_free_block(cur, rbp);
4188 332546 : if (error)
4189 0 : goto error0;
4190 :
4191 : /*
4192 : * If we joined with the left neighbor, set the buffer in the
4193 : * cursor to the left block, and fix up the index.
4194 : */
4195 332546 : if (bp != lbp) {
4196 315169 : cur->bc_levels[level].bp = lbp;
4197 315169 : cur->bc_levels[level].ptr += lrecs;
4198 315169 : cur->bc_levels[level].ra = 0;
4199 : }
4200 : /*
4201 : * If we joined with the right neighbor and there's a level above
4202 : * us, increment the cursor at that level.
4203 : */
4204 17377 : else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) ||
4205 16944 : (level + 1 < cur->bc_nlevels)) {
4206 17377 : error = xfs_btree_increment(cur, level + 1, &i);
4207 17377 : if (error)
4208 0 : goto error0;
4209 : }
4210 :
4211 : /*
4212 : * Readjust the ptr at this level if it's not a leaf, since it's
4213 : * still pointing at the deletion point, which makes the cursor
4214 : * inconsistent. If this makes the ptr 0, the caller fixes it up.
4215 : * We can't use decrement because it would change the next level up.
4216 : */
4217 332546 : if (level > 0)
4218 232 : cur->bc_levels[level].ptr--;
4219 :
4220 : /*
4221 : * We combined blocks, so we have to update the parent keys if the
4222 : * btree supports overlapped intervals. However,
4223 : * bc_levels[level + 1].ptr points to the old block so that the caller
4224 : * knows which record to delete. Therefore, the caller must be savvy
4225 : * enough to call updkeys for us if we return stat == 2. The other
4226 : * exit points from this function don't require deletions further up
4227 : * the tree, so they can call updkeys directly.
4228 : */
4229 :
4230 : /* Return value means the next level up has something to do. */
4231 332546 : *stat = 2;
4232 332546 : return 0;
4233 :
4234 4 : error0:
4235 4 : if (tcur)
4236 3 : xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
4237 : return error;
4238 : }
4239 :
4240 : /*
4241 : * Delete the record pointed to by cur.
4242 : * The cursor refers to the place where the record was (could be inserted)
4243 : * when the operation returns.
4244 : */
4245 : int /* error */
4246 253251070 : xfs_btree_delete(
4247 : struct xfs_btree_cur *cur,
4248 : int *stat) /* success/failure */
4249 : {
4250 253251070 : int error; /* error return value */
4251 253251070 : int level;
4252 253251070 : int i;
4253 253251070 : bool joined = false;
4254 :
4255 : /*
4256 : * Go up the tree, starting at leaf level.
4257 : *
4258 : * If 2 is returned then a join was done; go to the next level.
4259 : * Otherwise we are done.
4260 : */
4261 506838943 : for (level = 0, i = 2; i == 2; level++) {
4262 253585727 : error = xfs_btree_delrec(cur, level, &i);
4263 253587877 : if (error)
4264 4 : goto error0;
4265 253587873 : if (i == 2)
4266 332546 : joined = true;
4267 : }
4268 :
4269 : /*
4270 : * If we combined blocks as part of deleting the record, delrec won't
4271 : * have updated the parent high keys so we have to do that here.
4272 : */
4273 253253216 : if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) {
4274 116432 : error = xfs_btree_updkeys_force(cur, 0);
4275 116432 : if (error)
4276 0 : goto error0;
4277 : }
4278 :
4279 253253216 : if (i == 0) {
4280 0 : for (level = 1; level < cur->bc_nlevels; level++) {
4281 0 : if (cur->bc_levels[level].ptr == 0) {
4282 0 : error = xfs_btree_decrement(cur, level, &i);
4283 0 : if (error)
4284 0 : goto error0;
4285 : break;
4286 : }
4287 : }
4288 : }
4289 :
4290 253253216 : *stat = i;
4291 253253216 : return 0;
4292 : error0:
4293 : return error;
4294 : }
4295 :
4296 : /*
4297 : * Get the data from the pointed-to record.
4298 : */
4299 : int /* error */
4300 74278325174 : xfs_btree_get_rec(
4301 : struct xfs_btree_cur *cur, /* btree cursor */
4302 : union xfs_btree_rec **recp, /* output: btree record */
4303 : int *stat) /* output: success/failure */
4304 : {
4305 74278325174 : struct xfs_btree_block *block; /* btree block */
4306 74278325174 : struct xfs_buf *bp; /* buffer pointer */
4307 74278325174 : int ptr; /* record number */
4308 : #ifdef DEBUG
4309 74278325174 : int error; /* error return value */
4310 : #endif
4311 :
4312 74278325174 : ptr = cur->bc_levels[0].ptr;
4313 74278325174 : block = xfs_btree_get_block(cur, 0, &bp);
4314 :
4315 : #ifdef DEBUG
4316 74213930129 : error = xfs_btree_check_block(cur, block, 0, bp);
4317 72299978984 : if (error)
4318 : return error;
4319 : #endif
4320 :
4321 : /*
4322 : * Off the right end or left end, return failure.
4323 : */
4324 72299978984 : if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) {
4325 5897496 : *stat = 0;
4326 5897496 : return 0;
4327 : }
4328 :
4329 : /*
4330 : * Point to the record and extract its data.
4331 : */
4332 72294081488 : *recp = xfs_btree_rec_addr(cur, ptr, block);
4333 72294081488 : *stat = 1;
4334 72294081488 : return 0;
4335 : }
4336 :
4337 : /* Visit a block in a btree. */
4338 : STATIC int
4339 104367795 : xfs_btree_visit_block(
4340 : struct xfs_btree_cur *cur,
4341 : int level,
4342 : xfs_btree_visit_blocks_fn fn,
4343 : void *data)
4344 : {
4345 104367795 : struct xfs_btree_block *block;
4346 104367795 : struct xfs_buf *bp;
4347 104367795 : union xfs_btree_ptr rptr;
4348 104367795 : int error;
4349 :
4350 : /* do right sibling readahead */
4351 104367795 : xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
4352 104368167 : block = xfs_btree_get_block(cur, level, &bp);
4353 :
4354 : /* process the block */
4355 104368167 : error = fn(cur, level, data);
4356 104368485 : if (error)
4357 : return error;
4358 :
4359 : /* now read rh sibling block for next iteration */
4360 104368521 : xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
4361 208737724 : if (xfs_btree_ptr_is_null(cur, &rptr))
4362 : return -ENOENT;
4363 :
4364 : /*
4365 : * We only visit blocks once in this walk, so we have to avoid the
4366 : * internal xfs_btree_lookup_get_block() optimisation where it will
4367 : * return the same block without checking if the right sibling points
4368 : * back to us and creates a cyclic reference in the btree.
4369 : */
4370 84685719 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
4371 4257969 : if (be64_to_cpu(rptr.l) == XFS_DADDR_TO_FSB(cur->bc_mp,
4372 : xfs_buf_daddr(bp)))
4373 : return -EFSCORRUPTED;
4374 : } else {
4375 160855500 : if (be32_to_cpu(rptr.s) == xfs_daddr_to_agbno(cur->bc_mp,
4376 : xfs_buf_daddr(bp)))
4377 : return -EFSCORRUPTED;
4378 : }
4379 84685719 : return xfs_btree_lookup_get_block(cur, level, &rptr, &block);
4380 : }
4381 :
4382 :
4383 : /* Visit every block in a btree. */
4384 : int
4385 15847339 : xfs_btree_visit_blocks(
4386 : struct xfs_btree_cur *cur,
4387 : xfs_btree_visit_blocks_fn fn,
4388 : unsigned int flags,
4389 : void *data)
4390 : {
4391 15847339 : union xfs_btree_ptr lptr;
4392 15847339 : int level;
4393 15847339 : struct xfs_btree_block *block = NULL;
4394 15847339 : int error = 0;
4395 :
4396 15847339 : cur->bc_ops->init_ptr_from_cur(cur, &lptr);
4397 :
4398 : /* for each level */
4399 35934350 : for (level = cur->bc_nlevels - 1; level >= 0; level--) {
4400 : /* grab the left hand block */
4401 20086715 : error = xfs_btree_lookup_get_block(cur, level, &lptr, &block);
4402 20086391 : if (error)
4403 69 : return error;
4404 :
4405 : /* readahead the left most block for the next level down */
4406 20086322 : if (level > 0) {
4407 4238957 : union xfs_btree_ptr *ptr;
4408 :
4409 4238957 : ptr = xfs_btree_ptr_addr(cur, 1, block);
4410 4238956 : xfs_btree_readahead_ptr(cur, ptr, 1);
4411 :
4412 : /* save for the next iteration of the loop */
4413 4238960 : xfs_btree_copy_ptrs(cur, &lptr, ptr, 1);
4414 :
4415 4238959 : if (!(flags & XFS_BTREE_VISIT_LEAVES))
4416 403730 : continue;
4417 15847365 : } else if (!(flags & XFS_BTREE_VISIT_RECORDS)) {
4418 0 : continue;
4419 : }
4420 :
4421 : /* for each buffer in the level */
4422 104368118 : do {
4423 104368118 : error = xfs_btree_visit_block(cur, level, fn, data);
4424 104368499 : } while (!error);
4425 :
4426 19682975 : if (error != -ENOENT)
4427 0 : return error;
4428 : }
4429 :
4430 : return 0;
4431 : }
4432 :
4433 : /*
4434 : * Change the owner of a btree.
4435 : *
4436 : * The mechanism we use here is ordered buffer logging. Because we don't know
4437 : * how many buffers were are going to need to modify, we don't really want to
4438 : * have to make transaction reservations for the worst case of every buffer in a
4439 : * full size btree as that may be more space that we can fit in the log....
4440 : *
4441 : * We do the btree walk in the most optimal manner possible - we have sibling
4442 : * pointers so we can just walk all the blocks on each level from left to right
4443 : * in a single pass, and then move to the next level and do the same. We can
4444 : * also do readahead on the sibling pointers to get IO moving more quickly,
4445 : * though for slow disks this is unlikely to make much difference to performance
4446 : * as the amount of CPU work we have to do before moving to the next block is
4447 : * relatively small.
4448 : *
4449 : * For each btree block that we load, modify the owner appropriately, set the
4450 : * buffer as an ordered buffer and log it appropriately. We need to ensure that
4451 : * we mark the region we change dirty so that if the buffer is relogged in
4452 : * a subsequent transaction the changes we make here as an ordered buffer are
4453 : * correctly relogged in that transaction. If we are in recovery context, then
4454 : * just queue the modified buffer as delayed write buffer so the transaction
4455 : * recovery completion writes the changes to disk.
4456 : */
4457 : struct xfs_btree_block_change_owner_info {
4458 : uint64_t new_owner;
4459 : struct list_head *buffer_list;
4460 : };
4461 :
4462 : static int
4463 0 : xfs_btree_block_change_owner(
4464 : struct xfs_btree_cur *cur,
4465 : int level,
4466 : void *data)
4467 : {
4468 0 : struct xfs_btree_block_change_owner_info *bbcoi = data;
4469 0 : struct xfs_btree_block *block;
4470 0 : struct xfs_buf *bp;
4471 :
4472 : /* modify the owner */
4473 0 : block = xfs_btree_get_block(cur, level, &bp);
4474 0 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
4475 0 : if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner))
4476 : return 0;
4477 0 : block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner);
4478 : } else {
4479 0 : if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner))
4480 : return 0;
4481 0 : block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner);
4482 : }
4483 :
4484 : /*
4485 : * If the block is a root block hosted in an inode, we might not have a
4486 : * buffer pointer here and we shouldn't attempt to log the change as the
4487 : * information is already held in the inode and discarded when the root
4488 : * block is formatted into the on-disk inode fork. We still change it,
4489 : * though, so everything is consistent in memory.
4490 : */
4491 0 : if (!bp) {
4492 0 : ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
4493 0 : ASSERT(level == cur->bc_nlevels - 1);
4494 0 : return 0;
4495 : }
4496 :
4497 0 : if (cur->bc_tp) {
4498 0 : if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) {
4499 0 : xfs_btree_log_block(cur, bp, XFS_BB_OWNER);
4500 0 : return -EAGAIN;
4501 : }
4502 : } else {
4503 0 : xfs_buf_delwri_queue(bp, bbcoi->buffer_list);
4504 : }
4505 :
4506 : return 0;
4507 : }
4508 :
4509 : int
4510 0 : xfs_btree_change_owner(
4511 : struct xfs_btree_cur *cur,
4512 : uint64_t new_owner,
4513 : struct list_head *buffer_list)
4514 : {
4515 0 : struct xfs_btree_block_change_owner_info bbcoi;
4516 :
4517 0 : bbcoi.new_owner = new_owner;
4518 0 : bbcoi.buffer_list = buffer_list;
4519 :
4520 0 : return xfs_btree_visit_blocks(cur, xfs_btree_block_change_owner,
4521 : XFS_BTREE_VISIT_ALL, &bbcoi);
4522 : }
4523 :
4524 : /* Verify the v5 fields of a long-format btree block. */
4525 : xfs_failaddr_t
4526 10944703 : xfs_btree_lblock_v5hdr_verify(
4527 : struct xfs_buf *bp,
4528 : uint64_t owner)
4529 : {
4530 10944703 : struct xfs_mount *mp = bp->b_mount;
4531 10944703 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
4532 :
4533 10944703 : if (!xfs_has_crc(mp))
4534 0 : return __this_address;
4535 10944703 : if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))
4536 0 : return __this_address;
4537 10944725 : if (block->bb_u.l.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp)))
4538 0 : return __this_address;
4539 10944725 : if (owner != XFS_RMAP_OWN_UNKNOWN &&
4540 0 : be64_to_cpu(block->bb_u.l.bb_owner) != owner)
4541 0 : return __this_address;
4542 : return NULL;
4543 : }
4544 :
4545 : /* Verify a long-format btree block. */
4546 : xfs_failaddr_t
4547 10944720 : xfs_btree_lblock_verify(
4548 : struct xfs_buf *bp,
4549 : unsigned int max_recs)
4550 : {
4551 10944720 : struct xfs_mount *mp = bp->b_mount;
4552 10944720 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
4553 10944720 : xfs_fsblock_t fsb;
4554 10944720 : xfs_failaddr_t fa;
4555 :
4556 : /* numrecs verification */
4557 10944720 : if (be16_to_cpu(block->bb_numrecs) > max_recs)
4558 0 : return __this_address;
4559 :
4560 : /* sibling pointer verification */
4561 10944725 : fsb = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
4562 10944724 : fa = xfs_btree_check_lblock_siblings(mp, NULL, -1, fsb,
4563 : block->bb_u.l.bb_leftsib);
4564 10944724 : if (!fa)
4565 10944725 : fa = xfs_btree_check_lblock_siblings(mp, NULL, -1, fsb,
4566 : block->bb_u.l.bb_rightsib);
4567 : return fa;
4568 : }
4569 :
4570 : /**
4571 : * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4572 : * btree block
4573 : *
4574 : * @bp: buffer containing the btree block
4575 : */
4576 : xfs_failaddr_t
4577 34568208 : xfs_btree_sblock_v5hdr_verify(
4578 : struct xfs_buf *bp)
4579 : {
4580 34568208 : struct xfs_mount *mp = bp->b_mount;
4581 34568208 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
4582 34568208 : struct xfs_perag *pag = bp->b_pag;
4583 :
4584 34568208 : if (!xfs_has_crc(mp))
4585 0 : return __this_address;
4586 34568208 : if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))
4587 0 : return __this_address;
4588 34568299 : if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp)))
4589 0 : return __this_address;
4590 69104150 : if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
4591 18 : return __this_address;
4592 : return NULL;
4593 : }
4594 :
4595 : /**
4596 : * xfs_btree_sblock_verify() -- verify a short-format btree block
4597 : *
4598 : * @bp: buffer containing the btree block
4599 : * @max_recs: maximum records allowed in this btree node
4600 : */
4601 : xfs_failaddr_t
4602 34575326 : xfs_btree_sblock_verify(
4603 : struct xfs_buf *bp,
4604 : unsigned int max_recs)
4605 : {
4606 34575326 : struct xfs_mount *mp = bp->b_mount;
4607 34575326 : struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
4608 34575326 : xfs_agblock_t agbno;
4609 34575326 : xfs_failaddr_t fa;
4610 :
4611 : /* numrecs verification */
4612 34575326 : if (be16_to_cpu(block->bb_numrecs) > max_recs)
4613 1 : return __this_address;
4614 :
4615 : /* sibling pointer verification */
4616 34575361 : agbno = xfs_daddr_to_agbno(mp, xfs_buf_daddr(bp));
4617 34575333 : fa = xfs_btree_check_sblock_siblings(bp->b_pag, NULL, -1, agbno,
4618 : block->bb_u.s.bb_leftsib);
4619 34575326 : if (!fa)
4620 34575348 : fa = xfs_btree_check_sblock_siblings(bp->b_pag, NULL, -1, agbno,
4621 : block->bb_u.s.bb_rightsib);
4622 : return fa;
4623 : }
4624 :
4625 : /*
4626 : * For the given limits on leaf and keyptr records per block, calculate the
4627 : * height of the tree needed to index the number of leaf records.
4628 : */
4629 : unsigned int
4630 202049 : xfs_btree_compute_maxlevels(
4631 : const unsigned int *limits,
4632 : unsigned long long records)
4633 : {
4634 202049 : unsigned long long level_blocks = howmany_64(records, limits[0]);
4635 202049 : unsigned int height = 1;
4636 :
4637 1322421 : while (level_blocks > 1) {
4638 1120372 : level_blocks = howmany_64(level_blocks, limits[1]);
4639 1120372 : height++;
4640 : }
4641 :
4642 202049 : return height;
4643 : }
4644 :
4645 : /*
4646 : * For the given limits on leaf and keyptr records per block, calculate the
4647 : * number of blocks needed to index the given number of leaf records.
4648 : */
4649 : unsigned long long
4650 12205920 : xfs_btree_calc_size(
4651 : const unsigned int *limits,
4652 : unsigned long long records)
4653 : {
4654 12205920 : unsigned long long level_blocks = howmany_64(records, limits[0]);
4655 12205920 : unsigned long long blocks = level_blocks;
4656 :
4657 33272590 : while (level_blocks > 1) {
4658 21066498 : level_blocks = howmany_64(level_blocks, limits[1]);
4659 21066670 : blocks += level_blocks;
4660 : }
4661 :
4662 12205922 : return blocks;
4663 : }
4664 :
4665 : /*
4666 : * Given a number of available blocks for the btree to consume with records and
4667 : * pointers, calculate the height of the tree needed to index all the records
4668 : * that space can hold based on the number of pointers each interior node
4669 : * holds.
4670 : *
4671 : * We start by assuming a single level tree consumes a single block, then track
4672 : * the number of blocks each node level consumes until we no longer have space
4673 : * to store the next node level. At this point, we are indexing all the leaf
4674 : * blocks in the space, and there's no more free space to split the tree any
4675 : * further. That's our maximum btree height.
4676 : */
4677 : unsigned int
4678 44548 : xfs_btree_space_to_height(
4679 : const unsigned int *limits,
4680 : unsigned long long leaf_blocks)
4681 : {
4682 : /*
4683 : * The root btree block can have fewer than minrecs pointers in it
4684 : * because the tree might not be big enough to require that amount of
4685 : * fanout. Hence it has a minimum size of 2 pointers, not limits[1].
4686 : */
4687 44548 : unsigned long long node_blocks = 2;
4688 44548 : unsigned long long blocks_left = leaf_blocks - 1;
4689 44548 : unsigned int height = 1;
4690 :
4691 44548 : if (leaf_blocks < 1)
4692 : return 0;
4693 :
4694 328580 : while (node_blocks < blocks_left) {
4695 284032 : blocks_left -= node_blocks;
4696 284032 : node_blocks *= limits[1];
4697 284032 : height++;
4698 : }
4699 :
4700 : return height;
4701 : }
4702 :
4703 : /*
4704 : * Query a regular btree for all records overlapping a given interval.
4705 : * Start with a LE lookup of the key of low_rec and return all records
4706 : * until we find a record with a key greater than the key of high_rec.
4707 : */
4708 : STATIC int
4709 2602466048 : xfs_btree_simple_query_range(
4710 : struct xfs_btree_cur *cur,
4711 : const union xfs_btree_key *low_key,
4712 : const union xfs_btree_key *high_key,
4713 : xfs_btree_query_range_fn fn,
4714 : void *priv)
4715 : {
4716 2602466048 : union xfs_btree_rec *recp;
4717 2602466048 : union xfs_btree_key rec_key;
4718 2602466048 : int stat;
4719 2602466048 : bool firstrec = true;
4720 2602466048 : int error;
4721 :
4722 2602466048 : ASSERT(cur->bc_ops->init_high_key_from_rec);
4723 2602466048 : ASSERT(cur->bc_ops->diff_two_keys);
4724 :
4725 : /*
4726 : * Find the leftmost record. The btree cursor must be set
4727 : * to the low record used to generate low_key.
4728 : */
4729 2602466048 : stat = 0;
4730 2602466048 : error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, &stat);
4731 2602457076 : if (error)
4732 4 : goto out;
4733 :
4734 : /* Nothing? See if there's anything to the right. */
4735 2602457072 : if (!stat) {
4736 922899703 : error = xfs_btree_increment(cur, 0, &stat);
4737 922921015 : if (error)
4738 0 : goto out;
4739 : }
4740 :
4741 54118876085 : while (stat) {
4742 : /* Find the record. */
4743 53541436288 : error = xfs_btree_get_rec(cur, &recp, &stat);
4744 53512282745 : if (error || !stat)
4745 : break;
4746 :
4747 : /* Skip if low_key > high_key(rec). */
4748 53512282745 : if (firstrec) {
4749 2123560552 : cur->bc_ops->init_high_key_from_rec(&rec_key, recp);
4750 2123568732 : firstrec = false;
4751 2123568732 : if (xfs_btree_keycmp_gt(cur, low_key, &rec_key))
4752 1679678420 : goto advloop;
4753 : }
4754 :
4755 : /* Stop if low_key(rec) > high_key. */
4756 51832626169 : cur->bc_ops->init_key_from_rec(&rec_key, recp);
4757 51764892330 : if (xfs_btree_keycmp_gt(cur, &rec_key, high_key))
4758 : break;
4759 :
4760 : /* Callback */
4761 49962400446 : error = fn(cur, recp, priv);
4762 49997257647 : if (error)
4763 : break;
4764 :
4765 49997257635 : advloop:
4766 : /* Move on to the next record. */
4767 51676936055 : error = xfs_btree_increment(cur, 0, &stat);
4768 51516397701 : if (error)
4769 : break;
4770 : }
4771 :
4772 2602586062 : out:
4773 2602586066 : return error;
4774 : }
4775 :
4776 : /*
4777 : * Query an overlapped interval btree for all records overlapping a given
4778 : * interval. This function roughly follows the algorithm given in
4779 : * "Interval Trees" of _Introduction to Algorithms_, which is section
4780 : * 14.3 in the 2nd and 3rd editions.
4781 : *
4782 : * First, generate keys for the low and high records passed in.
4783 : *
4784 : * For any leaf node, generate the high and low keys for the record.
4785 : * If the record keys overlap with the query low/high keys, pass the
4786 : * record to the function iterator.
4787 : *
4788 : * For any internal node, compare the low and high keys of each
4789 : * pointer against the query low/high keys. If there's an overlap,
4790 : * follow the pointer.
4791 : *
4792 : * As an optimization, we stop scanning a block when we find a low key
4793 : * that is greater than the query's high key.
4794 : */
4795 : STATIC int
4796 744500208 : xfs_btree_overlapped_query_range(
4797 : struct xfs_btree_cur *cur,
4798 : const union xfs_btree_key *low_key,
4799 : const union xfs_btree_key *high_key,
4800 : xfs_btree_query_range_fn fn,
4801 : void *priv)
4802 : {
4803 744500208 : union xfs_btree_ptr ptr;
4804 744500208 : union xfs_btree_ptr *pp;
4805 744500208 : union xfs_btree_key rec_key;
4806 744500208 : union xfs_btree_key rec_hkey;
4807 744500208 : union xfs_btree_key *lkp;
4808 744500208 : union xfs_btree_key *hkp;
4809 744500208 : union xfs_btree_rec *recp;
4810 744500208 : struct xfs_btree_block *block;
4811 744500208 : int level;
4812 744500208 : struct xfs_buf *bp;
4813 744500208 : int i;
4814 744500208 : int error;
4815 :
4816 : /* Load the root of the btree. */
4817 744500208 : level = cur->bc_nlevels - 1;
4818 744500208 : cur->bc_ops->init_ptr_from_cur(cur, &ptr);
4819 744506555 : error = xfs_btree_lookup_get_block(cur, level, &ptr, &block);
4820 744505451 : if (error)
4821 : return error;
4822 744505554 : xfs_btree_get_block(cur, level, &bp);
4823 744499936 : trace_xfs_btree_overlapped_query_range(cur, level, bp);
4824 : #ifdef DEBUG
4825 744499703 : error = xfs_btree_check_block(cur, block, level, bp);
4826 744505052 : if (error)
4827 0 : goto out;
4828 : #endif
4829 744505052 : cur->bc_levels[level].ptr = 1;
4830 :
4831 73661181713 : while (level < cur->bc_nlevels) {
4832 72917188419 : block = xfs_btree_get_block(cur, level, &bp);
4833 :
4834 : /* End of node, pop back towards the root. */
4835 72916807351 : if (cur->bc_levels[level].ptr >
4836 72916807351 : be16_to_cpu(block->bb_numrecs)) {
4837 158910054 : pop_up:
4838 1786092126 : if (level < cur->bc_nlevels - 1)
4839 1042069596 : cur->bc_levels[level + 1].ptr++;
4840 1786092126 : level++;
4841 1786092126 : continue;
4842 : }
4843 :
4844 72757897297 : if (level == 0) {
4845 : /* Handle a leaf node. */
4846 51046477471 : recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,
4847 : block);
4848 :
4849 51046477471 : cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp);
4850 51031842654 : cur->bc_ops->init_key_from_rec(&rec_key, recp);
4851 :
4852 : /*
4853 : * If (query's high key < record's low key), then there
4854 : * are no more interesting records in this block. Pop
4855 : * up to the leaf level to find more record blocks.
4856 : *
4857 : * If (record's high key >= query's low key) and
4858 : * (query's high key >= record's low key), then
4859 : * this record overlaps the query range; callback.
4860 : */
4861 51022938407 : if (xfs_btree_keycmp_lt(cur, high_key, &rec_key))
4862 708018672 : goto pop_up;
4863 50325749637 : if (xfs_btree_keycmp_ge(cur, &rec_hkey, low_key)) {
4864 1998974761 : error = fn(cur, recp, priv);
4865 1998976679 : if (error)
4866 : break;
4867 : }
4868 50334283140 : cur->bc_levels[level].ptr++;
4869 50334283140 : continue;
4870 : }
4871 :
4872 : /* Handle an internal node. */
4873 21711419826 : lkp = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);
4874 21711419826 : hkp = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr,
4875 : block);
4876 21711419826 : pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);
4877 :
4878 : /*
4879 : * If (query's high key < pointer's low key), then there are no
4880 : * more interesting keys in this block. Pop up one leaf level
4881 : * to continue looking for records.
4882 : *
4883 : * If (pointer's high key >= query's low key) and
4884 : * (query's high key >= pointer's low key), then
4885 : * this record overlaps the query range; follow pointer.
4886 : */
4887 21703763966 : if (xfs_btree_keycmp_lt(cur, high_key, lkp))
4888 919163400 : goto pop_up;
4889 20790094063 : if (xfs_btree_keycmp_ge(cur, hkp, low_key)) {
4890 1042446990 : level--;
4891 1042446990 : error = xfs_btree_lookup_get_block(cur, level, pp,
4892 : &block);
4893 1042455506 : if (error)
4894 0 : goto out;
4895 1042455506 : xfs_btree_get_block(cur, level, &bp);
4896 1042448360 : trace_xfs_btree_overlapped_query_range(cur, level, bp);
4897 : #ifdef DEBUG
4898 1042445680 : error = xfs_btree_check_block(cur, block, level, bp);
4899 1042465541 : if (error)
4900 0 : goto out;
4901 : #endif
4902 1042465541 : cur->bc_levels[level].ptr = 1;
4903 1042465541 : continue;
4904 : }
4905 19753835854 : cur->bc_levels[level].ptr++;
4906 : }
4907 :
4908 744493102 : out:
4909 : /*
4910 : * If we don't end this function with the cursor pointing at a record
4911 : * block, a subsequent non-error cursor deletion will not release
4912 : * node-level buffers, causing a buffer leak. This is quite possible
4913 : * with a zero-results range query, so release the buffers if we
4914 : * failed to return any results.
4915 : */
4916 744493102 : if (cur->bc_levels[0].bp == NULL) {
4917 1118 : for (i = 0; i < cur->bc_nlevels; i++) {
4918 791 : if (cur->bc_levels[i].bp) {
4919 450 : xfs_trans_brelse(cur->bc_tp,
4920 : cur->bc_levels[i].bp);
4921 450 : cur->bc_levels[i].bp = NULL;
4922 450 : cur->bc_levels[i].ptr = 0;
4923 450 : cur->bc_levels[i].ra = 0;
4924 : }
4925 : }
4926 : }
4927 :
4928 : return error;
4929 : }
4930 :
4931 : static inline void
4932 12351668071 : xfs_btree_key_from_irec(
4933 : struct xfs_btree_cur *cur,
4934 : union xfs_btree_key *key,
4935 : const union xfs_btree_irec *irec)
4936 : {
4937 12351668071 : union xfs_btree_rec rec;
4938 :
4939 12351668071 : cur->bc_rec = *irec;
4940 12351668071 : cur->bc_ops->init_rec_from_cur(cur, &rec);
4941 12351587278 : cur->bc_ops->init_key_from_rec(key, &rec);
4942 12351598854 : }
4943 :
4944 : /*
4945 : * Query a btree for all records overlapping a given interval of keys. The
4946 : * supplied function will be called with each record found; return one of the
4947 : * XFS_BTREE_QUERY_RANGE_{CONTINUE,ABORT} values or the usual negative error
4948 : * code. This function returns -ECANCELED, zero, or a negative error code.
4949 : */
4950 : int
4951 3339895330 : xfs_btree_query_range(
4952 : struct xfs_btree_cur *cur,
4953 : const union xfs_btree_irec *low_rec,
4954 : const union xfs_btree_irec *high_rec,
4955 : xfs_btree_query_range_fn fn,
4956 : void *priv)
4957 : {
4958 3339895330 : union xfs_btree_key low_key;
4959 3339895330 : union xfs_btree_key high_key;
4960 :
4961 : /* Find the keys of both ends of the interval. */
4962 3339895330 : xfs_btree_key_from_irec(cur, &high_key, high_rec);
4963 3339989025 : xfs_btree_key_from_irec(cur, &low_key, low_rec);
4964 :
4965 : /* Enforce low key <= high key. */
4966 3339978872 : if (!xfs_btree_keycmp_le(cur, &low_key, &high_key))
4967 : return -EINVAL;
4968 :
4969 3340173608 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
4970 2595669201 : return xfs_btree_simple_query_range(cur, &low_key,
4971 : &high_key, fn, priv);
4972 744504407 : return xfs_btree_overlapped_query_range(cur, &low_key, &high_key,
4973 : fn, priv);
4974 : }
4975 :
4976 : /* Query a btree for all records. */
4977 : int
4978 6849384 : xfs_btree_query_all(
4979 : struct xfs_btree_cur *cur,
4980 : xfs_btree_query_range_fn fn,
4981 : void *priv)
4982 : {
4983 6849384 : union xfs_btree_key low_key;
4984 6849384 : union xfs_btree_key high_key;
4985 :
4986 6849384 : memset(&cur->bc_rec, 0, sizeof(cur->bc_rec));
4987 6849384 : memset(&low_key, 0, sizeof(low_key));
4988 6849384 : memset(&high_key, 0xFF, sizeof(high_key));
4989 :
4990 6849384 : return xfs_btree_simple_query_range(cur, &low_key, &high_key, fn, priv);
4991 : }
4992 :
4993 : static int
4994 91180275 : xfs_btree_count_blocks_helper(
4995 : struct xfs_btree_cur *cur,
4996 : int level,
4997 : void *data)
4998 : {
4999 91180275 : xfs_extlen_t *blocks = data;
5000 91180275 : (*blocks)++;
5001 :
5002 91180275 : return 0;
5003 : }
5004 :
5005 : /* Count the blocks in a btree and return the result in *blocks. */
5006 : int
5007 12173546 : xfs_btree_count_blocks(
5008 : struct xfs_btree_cur *cur,
5009 : xfs_extlen_t *blocks)
5010 : {
5011 12173546 : *blocks = 0;
5012 12173546 : return xfs_btree_visit_blocks(cur, xfs_btree_count_blocks_helper,
5013 : XFS_BTREE_VISIT_ALL, blocks);
5014 : }
5015 :
5016 : /* Compare two btree pointers. */
5017 : int64_t
5018 11038991 : xfs_btree_diff_two_ptrs(
5019 : struct xfs_btree_cur *cur,
5020 : const union xfs_btree_ptr *a,
5021 : const union xfs_btree_ptr *b)
5022 : {
5023 11038991 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
5024 1044759 : return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l);
5025 9994232 : return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s);
5026 : }
5027 :
5028 : struct xfs_btree_has_records {
5029 : /* Keys for the start and end of the range we want to know about. */
5030 : union xfs_btree_key start_key;
5031 : union xfs_btree_key end_key;
5032 :
5033 : /* Mask for key comparisons, if desired. */
5034 : const union xfs_btree_key *key_mask;
5035 :
5036 : /* Highest record key we've seen so far. */
5037 : union xfs_btree_key high_key;
5038 :
5039 : enum xbtree_recpacking outcome;
5040 : };
5041 :
5042 : STATIC int
5043 0 : xfs_btree_has_records_helper(
5044 : struct xfs_btree_cur *cur,
5045 : const union xfs_btree_rec *rec,
5046 : void *priv)
5047 : {
5048 0 : union xfs_btree_key rec_key;
5049 0 : union xfs_btree_key rec_high_key;
5050 0 : struct xfs_btree_has_records *info = priv;
5051 0 : enum xbtree_key_contig key_contig;
5052 :
5053 0 : cur->bc_ops->init_key_from_rec(&rec_key, rec);
5054 :
5055 0 : if (info->outcome == XBTREE_RECPACKING_EMPTY) {
5056 0 : info->outcome = XBTREE_RECPACKING_SPARSE;
5057 :
5058 : /*
5059 : * If the first record we find does not overlap the start key,
5060 : * then there is a hole at the start of the search range.
5061 : * Classify this as sparse and stop immediately.
5062 : */
5063 0 : if (xfs_btree_masked_keycmp_lt(cur, &info->start_key, &rec_key,
5064 : info->key_mask))
5065 : return -ECANCELED;
5066 : } else {
5067 : /*
5068 : * If a subsequent record does not overlap with the any record
5069 : * we've seen so far, there is a hole in the middle of the
5070 : * search range. Classify this as sparse and stop.
5071 : * If the keys overlap and this btree does not allow overlap,
5072 : * signal corruption.
5073 : */
5074 0 : key_contig = cur->bc_ops->keys_contiguous(cur, &info->high_key,
5075 : &rec_key, info->key_mask);
5076 0 : if (key_contig == XBTREE_KEY_OVERLAP &&
5077 0 : !(cur->bc_flags & XFS_BTREE_OVERLAPPING))
5078 : return -EFSCORRUPTED;
5079 0 : if (key_contig == XBTREE_KEY_GAP)
5080 : return -ECANCELED;
5081 : }
5082 :
5083 : /*
5084 : * If high_key(rec) is larger than any other high key we've seen,
5085 : * remember it for later.
5086 : */
5087 0 : cur->bc_ops->init_high_key_from_rec(&rec_high_key, rec);
5088 0 : if (xfs_btree_masked_keycmp_gt(cur, &rec_high_key, &info->high_key,
5089 : info->key_mask))
5090 0 : info->high_key = rec_high_key; /* struct copy */
5091 :
5092 : return 0;
5093 : }
5094 :
5095 : /*
5096 : * Scan part of the keyspace of a btree and tell us if that keyspace does not
5097 : * map to any records; is fully mapped to records; or is partially mapped to
5098 : * records. This is the btree record equivalent to determining if a file is
5099 : * sparse.
5100 : *
5101 : * For most btree types, the record scan should use all available btree key
5102 : * fields to compare the keys encountered. These callers should pass NULL for
5103 : * @mask. However, some callers (e.g. scanning physical space in the rmapbt)
5104 : * want to ignore some part of the btree record keyspace when performing the
5105 : * comparison. These callers should pass in a union xfs_btree_key object with
5106 : * the fields that *should* be a part of the comparison set to any nonzero
5107 : * value, and the rest zeroed.
5108 : */
5109 : int
5110 2836598142 : xfs_btree_has_records(
5111 : struct xfs_btree_cur *cur,
5112 : const union xfs_btree_irec *low,
5113 : const union xfs_btree_irec *high,
5114 : const union xfs_btree_key *mask,
5115 : enum xbtree_recpacking *outcome)
5116 : {
5117 2836598142 : struct xfs_btree_has_records info = {
5118 : .outcome = XBTREE_RECPACKING_EMPTY,
5119 : .key_mask = mask,
5120 : };
5121 2836598142 : int error;
5122 :
5123 : /* Not all btrees support this operation. */
5124 2836598142 : if (!cur->bc_ops->keys_contiguous) {
5125 0 : ASSERT(0);
5126 0 : return -EOPNOTSUPP;
5127 : }
5128 :
5129 2836598142 : xfs_btree_key_from_irec(cur, &info.start_key, low);
5130 2836644252 : xfs_btree_key_from_irec(cur, &info.end_key, high);
5131 :
5132 2836508840 : error = xfs_btree_query_range(cur, low, high,
5133 : xfs_btree_has_records_helper, &info);
5134 2836721965 : if (error == -ECANCELED)
5135 0 : goto out;
5136 2836721965 : if (error)
5137 : return error;
5138 :
5139 2836721965 : if (info.outcome == XBTREE_RECPACKING_EMPTY)
5140 2836721965 : goto out;
5141 :
5142 : /*
5143 : * If the largest high_key(rec) we saw during the walk is greater than
5144 : * the end of the search range, classify this as full. Otherwise,
5145 : * there is a hole at the end of the search range.
5146 : */
5147 0 : if (xfs_btree_masked_keycmp_ge(cur, &info.high_key, &info.end_key,
5148 : mask))
5149 0 : info.outcome = XBTREE_RECPACKING_FULL;
5150 :
5151 0 : out:
5152 2836721965 : *outcome = info.outcome;
5153 2836721965 : return 0;
5154 : }
5155 :
5156 : /* Are there more records in this btree? */
5157 : bool
5158 0 : xfs_btree_has_more_records(
5159 : struct xfs_btree_cur *cur)
5160 : {
5161 0 : struct xfs_btree_block *block;
5162 0 : struct xfs_buf *bp;
5163 :
5164 0 : block = xfs_btree_get_block(cur, 0, &bp);
5165 :
5166 : /* There are still records in this block. */
5167 0 : if (cur->bc_levels[0].ptr < xfs_btree_get_numrecs(block))
5168 : return true;
5169 :
5170 : /* There are more record blocks. */
5171 0 : if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
5172 0 : return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK);
5173 : else
5174 0 : return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK);
5175 : }
5176 :
5177 : /* Set up all the btree cursor caches. */
5178 : int __init
5179 12 : xfs_btree_init_cur_caches(void)
5180 : {
5181 12 : int error;
5182 :
5183 12 : error = xfs_allocbt_init_cur_cache();
5184 12 : if (error)
5185 : return error;
5186 12 : error = xfs_inobt_init_cur_cache();
5187 12 : if (error)
5188 0 : goto err;
5189 12 : error = xfs_bmbt_init_cur_cache();
5190 12 : if (error)
5191 0 : goto err;
5192 12 : error = xfs_rmapbt_init_cur_cache();
5193 12 : if (error)
5194 0 : goto err;
5195 12 : error = xfs_refcountbt_init_cur_cache();
5196 12 : if (error)
5197 0 : goto err;
5198 :
5199 : return 0;
5200 0 : err:
5201 0 : xfs_btree_destroy_cur_caches();
5202 0 : return error;
5203 : }
5204 :
5205 : /* Destroy all the btree cursor caches, if they've been allocated. */
5206 : void
5207 12 : xfs_btree_destroy_cur_caches(void)
5208 : {
5209 12 : xfs_allocbt_destroy_cur_cache();
5210 12 : xfs_inobt_destroy_cur_cache();
5211 12 : xfs_bmbt_destroy_cur_cache();
5212 12 : xfs_rmapbt_destroy_cur_cache();
5213 12 : xfs_refcountbt_destroy_cur_cache();
5214 12 : }
|
