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