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