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