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