~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/xfs/xfs_btree.c

Version: ~ [ linux-5.2-rc6 ] ~ [ linux-5.1.15 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.56 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.130 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.183 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.183 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.69 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
  3  * All Rights Reserved.
  4  *
  5  * This program is free software; you can redistribute it and/or
  6  * modify it under the terms of the GNU General Public License as
  7  * published by the Free Software Foundation.
  8  *
  9  * This program is distributed in the hope that it would be useful,
 10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 12  * GNU General Public License for more details.
 13  *
 14  * You should have received a copy of the GNU General Public License
 15  * along with this program; if not, write the Free Software Foundation,
 16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 17  */
 18 #include "xfs.h"
 19 #include "xfs_fs.h"
 20 #include "xfs_types.h"
 21 #include "xfs_bit.h"
 22 #include "xfs_log.h"
 23 #include "xfs_trans.h"
 24 #include "xfs_sb.h"
 25 #include "xfs_ag.h"
 26 #include "xfs_mount.h"
 27 #include "xfs_bmap_btree.h"
 28 #include "xfs_alloc_btree.h"
 29 #include "xfs_ialloc_btree.h"
 30 #include "xfs_dinode.h"
 31 #include "xfs_inode.h"
 32 #include "xfs_inode_item.h"
 33 #include "xfs_buf_item.h"
 34 #include "xfs_btree.h"
 35 #include "xfs_error.h"
 36 #include "xfs_trace.h"
 37 #include "xfs_cksum.h"
 38 
 39 /*
 40  * Cursor allocation zone.
 41  */
 42 kmem_zone_t     *xfs_btree_cur_zone;
 43 
 44 /*
 45  * Btree magic numbers.
 46  */
 47 static const __uint32_t xfs_magics[2][XFS_BTNUM_MAX] = {
 48         { XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, XFS_BMAP_MAGIC, XFS_IBT_MAGIC },
 49         { XFS_ABTB_CRC_MAGIC, XFS_ABTC_CRC_MAGIC,
 50           XFS_BMAP_CRC_MAGIC, XFS_IBT_CRC_MAGIC }
 51 };
 52 #define xfs_btree_magic(cur) \
 53         xfs_magics[!!((cur)->bc_flags & XFS_BTREE_CRC_BLOCKS)][cur->bc_btnum]
 54 
 55 
 56 STATIC int                              /* error (0 or EFSCORRUPTED) */
 57 xfs_btree_check_lblock(
 58         struct xfs_btree_cur    *cur,   /* btree cursor */
 59         struct xfs_btree_block  *block, /* btree long form block pointer */
 60         int                     level,  /* level of the btree block */
 61         struct xfs_buf          *bp)    /* buffer for block, if any */
 62 {
 63         int                     lblock_ok = 1; /* block passes checks */
 64         struct xfs_mount        *mp;    /* file system mount point */
 65 
 66         mp = cur->bc_mp;
 67 
 68         if (xfs_sb_version_hascrc(&mp->m_sb)) {
 69                 lblock_ok = lblock_ok &&
 70                         uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_uuid) &&
 71                         block->bb_u.l.bb_blkno == cpu_to_be64(
 72                                 bp ? bp->b_bn : XFS_BUF_DADDR_NULL);
 73         }
 74 
 75         lblock_ok = lblock_ok &&
 76                 be32_to_cpu(block->bb_magic) == xfs_btree_magic(cur) &&
 77                 be16_to_cpu(block->bb_level) == level &&
 78                 be16_to_cpu(block->bb_numrecs) <=
 79                         cur->bc_ops->get_maxrecs(cur, level) &&
 80                 block->bb_u.l.bb_leftsib &&
 81                 (block->bb_u.l.bb_leftsib == cpu_to_be64(NULLDFSBNO) ||
 82                  XFS_FSB_SANITY_CHECK(mp,
 83                         be64_to_cpu(block->bb_u.l.bb_leftsib))) &&
 84                 block->bb_u.l.bb_rightsib &&
 85                 (block->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO) ||
 86                  XFS_FSB_SANITY_CHECK(mp,
 87                         be64_to_cpu(block->bb_u.l.bb_rightsib)));
 88 
 89         if (unlikely(XFS_TEST_ERROR(!lblock_ok, mp,
 90                         XFS_ERRTAG_BTREE_CHECK_LBLOCK,
 91                         XFS_RANDOM_BTREE_CHECK_LBLOCK))) {
 92                 if (bp)
 93                         trace_xfs_btree_corrupt(bp, _RET_IP_);
 94                 XFS_ERROR_REPORT(__func__, XFS_ERRLEVEL_LOW, mp);
 95                 return XFS_ERROR(EFSCORRUPTED);
 96         }
 97         return 0;
 98 }
 99 
100 STATIC int                              /* error (0 or EFSCORRUPTED) */
101 xfs_btree_check_sblock(
102         struct xfs_btree_cur    *cur,   /* btree cursor */
103         struct xfs_btree_block  *block, /* btree short form block pointer */
104         int                     level,  /* level of the btree block */
105         struct xfs_buf          *bp)    /* buffer containing block */
106 {
107         struct xfs_mount        *mp;    /* file system mount point */
108         struct xfs_buf          *agbp;  /* buffer for ag. freespace struct */
109         struct xfs_agf          *agf;   /* ag. freespace structure */
110         xfs_agblock_t           agflen; /* native ag. freespace length */
111         int                     sblock_ok = 1; /* block passes checks */
112 
113         mp = cur->bc_mp;
114         agbp = cur->bc_private.a.agbp;
115         agf = XFS_BUF_TO_AGF(agbp);
116         agflen = be32_to_cpu(agf->agf_length);
117 
118         if (xfs_sb_version_hascrc(&mp->m_sb)) {
119                 sblock_ok = sblock_ok &&
120                         uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid) &&
121                         block->bb_u.s.bb_blkno == cpu_to_be64(
122                                 bp ? bp->b_bn : XFS_BUF_DADDR_NULL);
123         }
124 
125         sblock_ok = sblock_ok &&
126                 be32_to_cpu(block->bb_magic) == xfs_btree_magic(cur) &&
127                 be16_to_cpu(block->bb_level) == level &&
128                 be16_to_cpu(block->bb_numrecs) <=
129                         cur->bc_ops->get_maxrecs(cur, level) &&
130                 (block->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK) ||
131                  be32_to_cpu(block->bb_u.s.bb_leftsib) < agflen) &&
132                 block->bb_u.s.bb_leftsib &&
133                 (block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK) ||
134                  be32_to_cpu(block->bb_u.s.bb_rightsib) < agflen) &&
135                 block->bb_u.s.bb_rightsib;
136 
137         if (unlikely(XFS_TEST_ERROR(!sblock_ok, mp,
138                         XFS_ERRTAG_BTREE_CHECK_SBLOCK,
139                         XFS_RANDOM_BTREE_CHECK_SBLOCK))) {
140                 if (bp)
141                         trace_xfs_btree_corrupt(bp, _RET_IP_);
142                 XFS_ERROR_REPORT(__func__, XFS_ERRLEVEL_LOW, mp);
143                 return XFS_ERROR(EFSCORRUPTED);
144         }
145         return 0;
146 }
147 
148 /*
149  * Debug routine: check that block header is ok.
150  */
151 int
152 xfs_btree_check_block(
153         struct xfs_btree_cur    *cur,   /* btree cursor */
154         struct xfs_btree_block  *block, /* generic btree block pointer */
155         int                     level,  /* level of the btree block */
156         struct xfs_buf          *bp)    /* buffer containing block, if any */
157 {
158         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
159                 return xfs_btree_check_lblock(cur, block, level, bp);
160         else
161                 return xfs_btree_check_sblock(cur, block, level, bp);
162 }
163 
164 /*
165  * Check that (long) pointer is ok.
166  */
167 int                                     /* error (0 or EFSCORRUPTED) */
168 xfs_btree_check_lptr(
169         struct xfs_btree_cur    *cur,   /* btree cursor */
170         xfs_dfsbno_t            bno,    /* btree block disk address */
171         int                     level)  /* btree block level */
172 {
173         XFS_WANT_CORRUPTED_RETURN(
174                 level > 0 &&
175                 bno != NULLDFSBNO &&
176                 XFS_FSB_SANITY_CHECK(cur->bc_mp, bno));
177         return 0;
178 }
179 
180 #ifdef DEBUG
181 /*
182  * Check that (short) pointer is ok.
183  */
184 STATIC int                              /* error (0 or EFSCORRUPTED) */
185 xfs_btree_check_sptr(
186         struct xfs_btree_cur    *cur,   /* btree cursor */
187         xfs_agblock_t           bno,    /* btree block disk address */
188         int                     level)  /* btree block level */
189 {
190         xfs_agblock_t           agblocks = cur->bc_mp->m_sb.sb_agblocks;
191 
192         XFS_WANT_CORRUPTED_RETURN(
193                 level > 0 &&
194                 bno != NULLAGBLOCK &&
195                 bno != 0 &&
196                 bno < agblocks);
197         return 0;
198 }
199 
200 /*
201  * Check that block ptr is ok.
202  */
203 STATIC int                              /* error (0 or EFSCORRUPTED) */
204 xfs_btree_check_ptr(
205         struct xfs_btree_cur    *cur,   /* btree cursor */
206         union xfs_btree_ptr     *ptr,   /* btree block disk address */
207         int                     index,  /* offset from ptr to check */
208         int                     level)  /* btree block level */
209 {
210         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
211                 return xfs_btree_check_lptr(cur,
212                                 be64_to_cpu((&ptr->l)[index]), level);
213         } else {
214                 return xfs_btree_check_sptr(cur,
215                                 be32_to_cpu((&ptr->s)[index]), level);
216         }
217 }
218 #endif
219 
220 /*
221  * Calculate CRC on the whole btree block and stuff it into the
222  * long-form btree header.
223  *
224  * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
225  * it into the buffer so recovery knows what the last modifcation was that made
226  * it to disk.
227  */
228 void
229 xfs_btree_lblock_calc_crc(
230         struct xfs_buf          *bp)
231 {
232         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
233         struct xfs_buf_log_item *bip = bp->b_fspriv;
234 
235         if (!xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb))
236                 return;
237         if (bip)
238                 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
239         xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length),
240                          XFS_BTREE_LBLOCK_CRC_OFF);
241 }
242 
243 bool
244 xfs_btree_lblock_verify_crc(
245         struct xfs_buf          *bp)
246 {
247         if (xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb))
248                 return xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
249                                         XFS_BTREE_LBLOCK_CRC_OFF);
250         return true;
251 }
252 
253 /*
254  * Calculate CRC on the whole btree block and stuff it into the
255  * short-form btree header.
256  *
257  * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
258  * it into the buffer so recovery knows what the last modifcation was that made
259  * it to disk.
260  */
261 void
262 xfs_btree_sblock_calc_crc(
263         struct xfs_buf          *bp)
264 {
265         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
266         struct xfs_buf_log_item *bip = bp->b_fspriv;
267 
268         if (!xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb))
269                 return;
270         if (bip)
271                 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
272         xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length),
273                          XFS_BTREE_SBLOCK_CRC_OFF);
274 }
275 
276 bool
277 xfs_btree_sblock_verify_crc(
278         struct xfs_buf          *bp)
279 {
280         if (xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb))
281                 return xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
282                                         XFS_BTREE_SBLOCK_CRC_OFF);
283         return true;
284 }
285 
286 /*
287  * Delete the btree cursor.
288  */
289 void
290 xfs_btree_del_cursor(
291         xfs_btree_cur_t *cur,           /* btree cursor */
292         int             error)          /* del because of error */
293 {
294         int             i;              /* btree level */
295 
296         /*
297          * Clear the buffer pointers, and release the buffers.
298          * If we're doing this in the face of an error, we
299          * need to make sure to inspect all of the entries
300          * in the bc_bufs array for buffers to be unlocked.
301          * This is because some of the btree code works from
302          * level n down to 0, and if we get an error along
303          * the way we won't have initialized all the entries
304          * down to 0.
305          */
306         for (i = 0; i < cur->bc_nlevels; i++) {
307                 if (cur->bc_bufs[i])
308                         xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]);
309                 else if (!error)
310                         break;
311         }
312         /*
313          * Can't free a bmap cursor without having dealt with the
314          * allocated indirect blocks' accounting.
315          */
316         ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP ||
317                cur->bc_private.b.allocated == 0);
318         /*
319          * Free the cursor.
320          */
321         kmem_zone_free(xfs_btree_cur_zone, cur);
322 }
323 
324 /*
325  * Duplicate the btree cursor.
326  * Allocate a new one, copy the record, re-get the buffers.
327  */
328 int                                     /* error */
329 xfs_btree_dup_cursor(
330         xfs_btree_cur_t *cur,           /* input cursor */
331         xfs_btree_cur_t **ncur)         /* output cursor */
332 {
333         xfs_buf_t       *bp;            /* btree block's buffer pointer */
334         int             error;          /* error return value */
335         int             i;              /* level number of btree block */
336         xfs_mount_t     *mp;            /* mount structure for filesystem */
337         xfs_btree_cur_t *new;           /* new cursor value */
338         xfs_trans_t     *tp;            /* transaction pointer, can be NULL */
339 
340         tp = cur->bc_tp;
341         mp = cur->bc_mp;
342 
343         /*
344          * Allocate a new cursor like the old one.
345          */
346         new = cur->bc_ops->dup_cursor(cur);
347 
348         /*
349          * Copy the record currently in the cursor.
350          */
351         new->bc_rec = cur->bc_rec;
352 
353         /*
354          * For each level current, re-get the buffer and copy the ptr value.
355          */
356         for (i = 0; i < new->bc_nlevels; i++) {
357                 new->bc_ptrs[i] = cur->bc_ptrs[i];
358                 new->bc_ra[i] = cur->bc_ra[i];
359                 bp = cur->bc_bufs[i];
360                 if (bp) {
361                         error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
362                                                    XFS_BUF_ADDR(bp), mp->m_bsize,
363                                                    0, &bp,
364                                                    cur->bc_ops->buf_ops);
365                         if (error) {
366                                 xfs_btree_del_cursor(new, error);
367                                 *ncur = NULL;
368                                 return error;
369                         }
370                 }
371                 new->bc_bufs[i] = bp;
372         }
373         *ncur = new;
374         return 0;
375 }
376 
377 /*
378  * XFS btree block layout and addressing:
379  *
380  * There are two types of blocks in the btree: leaf and non-leaf blocks.
381  *
382  * The leaf record start with a header then followed by records containing
383  * the values.  A non-leaf block also starts with the same header, and
384  * then first contains lookup keys followed by an equal number of pointers
385  * to the btree blocks at the previous level.
386  *
387  *              +--------+-------+-------+-------+-------+-------+-------+
388  * Leaf:        | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N |
389  *              +--------+-------+-------+-------+-------+-------+-------+
390  *
391  *              +--------+-------+-------+-------+-------+-------+-------+
392  * Non-Leaf:    | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
393  *              +--------+-------+-------+-------+-------+-------+-------+
394  *
395  * The header is called struct xfs_btree_block for reasons better left unknown
396  * and comes in different versions for short (32bit) and long (64bit) block
397  * pointers.  The record and key structures are defined by the btree instances
398  * and opaque to the btree core.  The block pointers are simple disk endian
399  * integers, available in a short (32bit) and long (64bit) variant.
400  *
401  * The helpers below calculate the offset of a given record, key or pointer
402  * into a btree block (xfs_btree_*_offset) or return a pointer to the given
403  * record, key or pointer (xfs_btree_*_addr).  Note that all addressing
404  * inside the btree block is done using indices starting at one, not zero!
405  */
406 
407 /*
408  * Return size of the btree block header for this btree instance.
409  */
410 static inline size_t xfs_btree_block_len(struct xfs_btree_cur *cur)
411 {
412         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
413                 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
414                         return XFS_BTREE_LBLOCK_CRC_LEN;
415                 return XFS_BTREE_LBLOCK_LEN;
416         }
417         if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
418                 return XFS_BTREE_SBLOCK_CRC_LEN;
419         return XFS_BTREE_SBLOCK_LEN;
420 }
421 
422 /*
423  * Return size of btree block pointers for this btree instance.
424  */
425 static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur *cur)
426 {
427         return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
428                 sizeof(__be64) : sizeof(__be32);
429 }
430 
431 /*
432  * Calculate offset of the n-th record in a btree block.
433  */
434 STATIC size_t
435 xfs_btree_rec_offset(
436         struct xfs_btree_cur    *cur,
437         int                     n)
438 {
439         return xfs_btree_block_len(cur) +
440                 (n - 1) * cur->bc_ops->rec_len;
441 }
442 
443 /*
444  * Calculate offset of the n-th key in a btree block.
445  */
446 STATIC size_t
447 xfs_btree_key_offset(
448         struct xfs_btree_cur    *cur,
449         int                     n)
450 {
451         return xfs_btree_block_len(cur) +
452                 (n - 1) * cur->bc_ops->key_len;
453 }
454 
455 /*
456  * Calculate offset of the n-th block pointer in a btree block.
457  */
458 STATIC size_t
459 xfs_btree_ptr_offset(
460         struct xfs_btree_cur    *cur,
461         int                     n,
462         int                     level)
463 {
464         return xfs_btree_block_len(cur) +
465                 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
466                 (n - 1) * xfs_btree_ptr_len(cur);
467 }
468 
469 /*
470  * Return a pointer to the n-th record in the btree block.
471  */
472 STATIC union xfs_btree_rec *
473 xfs_btree_rec_addr(
474         struct xfs_btree_cur    *cur,
475         int                     n,
476         struct xfs_btree_block  *block)
477 {
478         return (union xfs_btree_rec *)
479                 ((char *)block + xfs_btree_rec_offset(cur, n));
480 }
481 
482 /*
483  * Return a pointer to the n-th key in the btree block.
484  */
485 STATIC union xfs_btree_key *
486 xfs_btree_key_addr(
487         struct xfs_btree_cur    *cur,
488         int                     n,
489         struct xfs_btree_block  *block)
490 {
491         return (union xfs_btree_key *)
492                 ((char *)block + xfs_btree_key_offset(cur, n));
493 }
494 
495 /*
496  * Return a pointer to the n-th block pointer in the btree block.
497  */
498 STATIC union xfs_btree_ptr *
499 xfs_btree_ptr_addr(
500         struct xfs_btree_cur    *cur,
501         int                     n,
502         struct xfs_btree_block  *block)
503 {
504         int                     level = xfs_btree_get_level(block);
505 
506         ASSERT(block->bb_level != 0);
507 
508         return (union xfs_btree_ptr *)
509                 ((char *)block + xfs_btree_ptr_offset(cur, n, level));
510 }
511 
512 /*
513  * Get a the root block which is stored in the inode.
514  *
515  * For now this btree implementation assumes the btree root is always
516  * stored in the if_broot field of an inode fork.
517  */
518 STATIC struct xfs_btree_block *
519 xfs_btree_get_iroot(
520        struct xfs_btree_cur    *cur)
521 {
522        struct xfs_ifork        *ifp;
523 
524        ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, cur->bc_private.b.whichfork);
525        return (struct xfs_btree_block *)ifp->if_broot;
526 }
527 
528 /*
529  * Retrieve the block pointer from the cursor at the given level.
530  * This may be an inode btree root or from a buffer.
531  */
532 STATIC struct xfs_btree_block *         /* generic btree block pointer */
533 xfs_btree_get_block(
534         struct xfs_btree_cur    *cur,   /* btree cursor */
535         int                     level,  /* level in btree */
536         struct xfs_buf          **bpp)  /* buffer containing the block */
537 {
538         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
539             (level == cur->bc_nlevels - 1)) {
540                 *bpp = NULL;
541                 return xfs_btree_get_iroot(cur);
542         }
543 
544         *bpp = cur->bc_bufs[level];
545         return XFS_BUF_TO_BLOCK(*bpp);
546 }
547 
548 /*
549  * Get a buffer for the block, return it with no data read.
550  * Long-form addressing.
551  */
552 xfs_buf_t *                             /* buffer for fsbno */
553 xfs_btree_get_bufl(
554         xfs_mount_t     *mp,            /* file system mount point */
555         xfs_trans_t     *tp,            /* transaction pointer */
556         xfs_fsblock_t   fsbno,          /* file system block number */
557         uint            lock)           /* lock flags for get_buf */
558 {
559         xfs_buf_t       *bp;            /* buffer pointer (return value) */
560         xfs_daddr_t             d;              /* real disk block address */
561 
562         ASSERT(fsbno != NULLFSBLOCK);
563         d = XFS_FSB_TO_DADDR(mp, fsbno);
564         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
565         ASSERT(!xfs_buf_geterror(bp));
566         return bp;
567 }
568 
569 /*
570  * Get a buffer for the block, return it with no data read.
571  * Short-form addressing.
572  */
573 xfs_buf_t *                             /* buffer for agno/agbno */
574 xfs_btree_get_bufs(
575         xfs_mount_t     *mp,            /* file system mount point */
576         xfs_trans_t     *tp,            /* transaction pointer */
577         xfs_agnumber_t  agno,           /* allocation group number */
578         xfs_agblock_t   agbno,          /* allocation group block number */
579         uint            lock)           /* lock flags for get_buf */
580 {
581         xfs_buf_t       *bp;            /* buffer pointer (return value) */
582         xfs_daddr_t             d;              /* real disk block address */
583 
584         ASSERT(agno != NULLAGNUMBER);
585         ASSERT(agbno != NULLAGBLOCK);
586         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
587         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
588         ASSERT(!xfs_buf_geterror(bp));
589         return bp;
590 }
591 
592 /*
593  * Check for the cursor referring to the last block at the given level.
594  */
595 int                                     /* 1=is last block, 0=not last block */
596 xfs_btree_islastblock(
597         xfs_btree_cur_t         *cur,   /* btree cursor */
598         int                     level)  /* level to check */
599 {
600         struct xfs_btree_block  *block; /* generic btree block pointer */
601         xfs_buf_t               *bp;    /* buffer containing block */
602 
603         block = xfs_btree_get_block(cur, level, &bp);
604         xfs_btree_check_block(cur, block, level, bp);
605         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
606                 return block->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO);
607         else
608                 return block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK);
609 }
610 
611 /*
612  * Change the cursor to point to the first record at the given level.
613  * Other levels are unaffected.
614  */
615 STATIC int                              /* success=1, failure=0 */
616 xfs_btree_firstrec(
617         xfs_btree_cur_t         *cur,   /* btree cursor */
618         int                     level)  /* level to change */
619 {
620         struct xfs_btree_block  *block; /* generic btree block pointer */
621         xfs_buf_t               *bp;    /* buffer containing block */
622 
623         /*
624          * Get the block pointer for this level.
625          */
626         block = xfs_btree_get_block(cur, level, &bp);
627         xfs_btree_check_block(cur, block, level, bp);
628         /*
629          * It's empty, there is no such record.
630          */
631         if (!block->bb_numrecs)
632                 return 0;
633         /*
634          * Set the ptr value to 1, that's the first record/key.
635          */
636         cur->bc_ptrs[level] = 1;
637         return 1;
638 }
639 
640 /*
641  * Change the cursor to point to the last record in the current block
642  * at the given level.  Other levels are unaffected.
643  */
644 STATIC int                              /* success=1, failure=0 */
645 xfs_btree_lastrec(
646         xfs_btree_cur_t         *cur,   /* btree cursor */
647         int                     level)  /* level to change */
648 {
649         struct xfs_btree_block  *block; /* generic btree block pointer */
650         xfs_buf_t               *bp;    /* buffer containing block */
651 
652         /*
653          * Get the block pointer for this level.
654          */
655         block = xfs_btree_get_block(cur, level, &bp);
656         xfs_btree_check_block(cur, block, level, bp);
657         /*
658          * It's empty, there is no such record.
659          */
660         if (!block->bb_numrecs)
661                 return 0;
662         /*
663          * Set the ptr value to numrecs, that's the last record/key.
664          */
665         cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs);
666         return 1;
667 }
668 
669 /*
670  * Compute first and last byte offsets for the fields given.
671  * Interprets the offsets table, which contains struct field offsets.
672  */
673 void
674 xfs_btree_offsets(
675         __int64_t       fields,         /* bitmask of fields */
676         const short     *offsets,       /* table of field offsets */
677         int             nbits,          /* number of bits to inspect */
678         int             *first,         /* output: first byte offset */
679         int             *last)          /* output: last byte offset */
680 {
681         int             i;              /* current bit number */
682         __int64_t       imask;          /* mask for current bit number */
683 
684         ASSERT(fields != 0);
685         /*
686          * Find the lowest bit, so the first byte offset.
687          */
688         for (i = 0, imask = 1LL; ; i++, imask <<= 1) {
689                 if (imask & fields) {
690                         *first = offsets[i];
691                         break;
692                 }
693         }
694         /*
695          * Find the highest bit, so the last byte offset.
696          */
697         for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) {
698                 if (imask & fields) {
699                         *last = offsets[i + 1] - 1;
700                         break;
701                 }
702         }
703 }
704 
705 /*
706  * Get a buffer for the block, return it read in.
707  * Long-form addressing.
708  */
709 int
710 xfs_btree_read_bufl(
711         struct xfs_mount        *mp,            /* file system mount point */
712         struct xfs_trans        *tp,            /* transaction pointer */
713         xfs_fsblock_t           fsbno,          /* file system block number */
714         uint                    lock,           /* lock flags for read_buf */
715         struct xfs_buf          **bpp,          /* buffer for fsbno */
716         int                     refval,         /* ref count value for buffer */
717         const struct xfs_buf_ops *ops)
718 {
719         struct xfs_buf          *bp;            /* return value */
720         xfs_daddr_t             d;              /* real disk block address */
721         int                     error;
722 
723         ASSERT(fsbno != NULLFSBLOCK);
724         d = XFS_FSB_TO_DADDR(mp, fsbno);
725         error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
726                                    mp->m_bsize, lock, &bp, ops);
727         if (error)
728                 return error;
729         ASSERT(!xfs_buf_geterror(bp));
730         if (bp)
731                 xfs_buf_set_ref(bp, refval);
732         *bpp = bp;
733         return 0;
734 }
735 
736 /*
737  * Read-ahead the block, don't wait for it, don't return a buffer.
738  * Long-form addressing.
739  */
740 /* ARGSUSED */
741 void
742 xfs_btree_reada_bufl(
743         struct xfs_mount        *mp,            /* file system mount point */
744         xfs_fsblock_t           fsbno,          /* file system block number */
745         xfs_extlen_t            count,          /* count of filesystem blocks */
746         const struct xfs_buf_ops *ops)
747 {
748         xfs_daddr_t             d;
749 
750         ASSERT(fsbno != NULLFSBLOCK);
751         d = XFS_FSB_TO_DADDR(mp, fsbno);
752         xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
753 }
754 
755 /*
756  * Read-ahead the block, don't wait for it, don't return a buffer.
757  * Short-form addressing.
758  */
759 /* ARGSUSED */
760 void
761 xfs_btree_reada_bufs(
762         struct xfs_mount        *mp,            /* file system mount point */
763         xfs_agnumber_t          agno,           /* allocation group number */
764         xfs_agblock_t           agbno,          /* allocation group block number */
765         xfs_extlen_t            count,          /* count of filesystem blocks */
766         const struct xfs_buf_ops *ops)
767 {
768         xfs_daddr_t             d;
769 
770         ASSERT(agno != NULLAGNUMBER);
771         ASSERT(agbno != NULLAGBLOCK);
772         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
773         xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
774 }
775 
776 STATIC int
777 xfs_btree_readahead_lblock(
778         struct xfs_btree_cur    *cur,
779         int                     lr,
780         struct xfs_btree_block  *block)
781 {
782         int                     rval = 0;
783         xfs_dfsbno_t            left = be64_to_cpu(block->bb_u.l.bb_leftsib);
784         xfs_dfsbno_t            right = be64_to_cpu(block->bb_u.l.bb_rightsib);
785 
786         if ((lr & XFS_BTCUR_LEFTRA) && left != NULLDFSBNO) {
787                 xfs_btree_reada_bufl(cur->bc_mp, left, 1,
788                                      cur->bc_ops->buf_ops);
789                 rval++;
790         }
791 
792         if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLDFSBNO) {
793                 xfs_btree_reada_bufl(cur->bc_mp, right, 1,
794                                      cur->bc_ops->buf_ops);
795                 rval++;
796         }
797 
798         return rval;
799 }
800 
801 STATIC int
802 xfs_btree_readahead_sblock(
803         struct xfs_btree_cur    *cur,
804         int                     lr,
805         struct xfs_btree_block *block)
806 {
807         int                     rval = 0;
808         xfs_agblock_t           left = be32_to_cpu(block->bb_u.s.bb_leftsib);
809         xfs_agblock_t           right = be32_to_cpu(block->bb_u.s.bb_rightsib);
810 
811 
812         if ((lr & XFS_BTCUR_LEFTRA) && left != NULLAGBLOCK) {
813                 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
814                                      left, 1, cur->bc_ops->buf_ops);
815                 rval++;
816         }
817 
818         if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLAGBLOCK) {
819                 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
820                                      right, 1, cur->bc_ops->buf_ops);
821                 rval++;
822         }
823 
824         return rval;
825 }
826 
827 /*
828  * Read-ahead btree blocks, at the given level.
829  * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
830  */
831 STATIC int
832 xfs_btree_readahead(
833         struct xfs_btree_cur    *cur,           /* btree cursor */
834         int                     lev,            /* level in btree */
835         int                     lr)             /* left/right bits */
836 {
837         struct xfs_btree_block  *block;
838 
839         /*
840          * No readahead needed if we are at the root level and the
841          * btree root is stored in the inode.
842          */
843         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
844             (lev == cur->bc_nlevels - 1))
845                 return 0;
846 
847         if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev])
848                 return 0;
849 
850         cur->bc_ra[lev] |= lr;
851         block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]);
852 
853         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
854                 return xfs_btree_readahead_lblock(cur, lr, block);
855         return xfs_btree_readahead_sblock(cur, lr, block);
856 }
857 
858 /*
859  * Set the buffer for level "lev" in the cursor to bp, releasing
860  * any previous buffer.
861  */
862 STATIC void
863 xfs_btree_setbuf(
864         xfs_btree_cur_t         *cur,   /* btree cursor */
865         int                     lev,    /* level in btree */
866         xfs_buf_t               *bp)    /* new buffer to set */
867 {
868         struct xfs_btree_block  *b;     /* btree block */
869 
870         if (cur->bc_bufs[lev])
871                 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[lev]);
872         cur->bc_bufs[lev] = bp;
873         cur->bc_ra[lev] = 0;
874 
875         b = XFS_BUF_TO_BLOCK(bp);
876         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
877                 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLDFSBNO))
878                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
879                 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO))
880                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
881         } else {
882                 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK))
883                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
884                 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK))
885                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
886         }
887 }
888 
889 STATIC int
890 xfs_btree_ptr_is_null(
891         struct xfs_btree_cur    *cur,
892         union xfs_btree_ptr     *ptr)
893 {
894         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
895                 return ptr->l == cpu_to_be64(NULLDFSBNO);
896         else
897                 return ptr->s == cpu_to_be32(NULLAGBLOCK);
898 }
899 
900 STATIC void
901 xfs_btree_set_ptr_null(
902         struct xfs_btree_cur    *cur,
903         union xfs_btree_ptr     *ptr)
904 {
905         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
906                 ptr->l = cpu_to_be64(NULLDFSBNO);
907         else
908                 ptr->s = cpu_to_be32(NULLAGBLOCK);
909 }
910 
911 /*
912  * Get/set/init sibling pointers
913  */
914 STATIC void
915 xfs_btree_get_sibling(
916         struct xfs_btree_cur    *cur,
917         struct xfs_btree_block  *block,
918         union xfs_btree_ptr     *ptr,
919         int                     lr)
920 {
921         ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
922 
923         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
924                 if (lr == XFS_BB_RIGHTSIB)
925                         ptr->l = block->bb_u.l.bb_rightsib;
926                 else
927                         ptr->l = block->bb_u.l.bb_leftsib;
928         } else {
929                 if (lr == XFS_BB_RIGHTSIB)
930                         ptr->s = block->bb_u.s.bb_rightsib;
931                 else
932                         ptr->s = block->bb_u.s.bb_leftsib;
933         }
934 }
935 
936 STATIC void
937 xfs_btree_set_sibling(
938         struct xfs_btree_cur    *cur,
939         struct xfs_btree_block  *block,
940         union xfs_btree_ptr     *ptr,
941         int                     lr)
942 {
943         ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
944 
945         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
946                 if (lr == XFS_BB_RIGHTSIB)
947                         block->bb_u.l.bb_rightsib = ptr->l;
948                 else
949                         block->bb_u.l.bb_leftsib = ptr->l;
950         } else {
951                 if (lr == XFS_BB_RIGHTSIB)
952                         block->bb_u.s.bb_rightsib = ptr->s;
953                 else
954                         block->bb_u.s.bb_leftsib = ptr->s;
955         }
956 }
957 
958 void
959 xfs_btree_init_block_int(
960         struct xfs_mount        *mp,
961         struct xfs_btree_block  *buf,
962         xfs_daddr_t             blkno,
963         __u32                   magic,
964         __u16                   level,
965         __u16                   numrecs,
966         __u64                   owner,
967         unsigned int            flags)
968 {
969         buf->bb_magic = cpu_to_be32(magic);
970         buf->bb_level = cpu_to_be16(level);
971         buf->bb_numrecs = cpu_to_be16(numrecs);
972 
973         if (flags & XFS_BTREE_LONG_PTRS) {
974                 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLDFSBNO);
975                 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLDFSBNO);
976                 if (flags & XFS_BTREE_CRC_BLOCKS) {
977                         buf->bb_u.l.bb_blkno = cpu_to_be64(blkno);
978                         buf->bb_u.l.bb_owner = cpu_to_be64(owner);
979                         uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_uuid);
980                         buf->bb_u.l.bb_pad = 0;
981                 }
982         } else {
983                 /* owner is a 32 bit value on short blocks */
984                 __u32 __owner = (__u32)owner;
985 
986                 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK);
987                 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK);
988                 if (flags & XFS_BTREE_CRC_BLOCKS) {
989                         buf->bb_u.s.bb_blkno = cpu_to_be64(blkno);
990                         buf->bb_u.s.bb_owner = cpu_to_be32(__owner);
991                         uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid);
992                 }
993         }
994 }
995 
996 void
997 xfs_btree_init_block(
998         struct xfs_mount *mp,
999         struct xfs_buf  *bp,
1000         __u32           magic,
1001         __u16           level,
1002         __u16           numrecs,
1003         __u64           owner,
1004         unsigned int    flags)
1005 {
1006         xfs_btree_init_block_int(mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn,
1007                                  magic, level, numrecs, owner, flags);
1008 }
1009 
1010 STATIC void
1011 xfs_btree_init_block_cur(
1012         struct xfs_btree_cur    *cur,
1013         struct xfs_buf          *bp,
1014         int                     level,
1015         int                     numrecs)
1016 {
1017         __u64 owner;
1018 
1019         /*
1020          * we can pull the owner from the cursor right now as the different
1021          * owners align directly with the pointer size of the btree. This may
1022          * change in future, but is safe for current users of the generic btree
1023          * code.
1024          */
1025         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1026                 owner = cur->bc_private.b.ip->i_ino;
1027         else
1028                 owner = cur->bc_private.a.agno;
1029 
1030         xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn,
1031                                  xfs_btree_magic(cur), level, numrecs,
1032                                  owner, cur->bc_flags);
1033 }
1034 
1035 /*
1036  * Return true if ptr is the last record in the btree and
1037  * we need to track updates to this record.  The decision
1038  * will be further refined in the update_lastrec method.
1039  */
1040 STATIC int
1041 xfs_btree_is_lastrec(
1042         struct xfs_btree_cur    *cur,
1043         struct xfs_btree_block  *block,
1044         int                     level)
1045 {
1046         union xfs_btree_ptr     ptr;
1047 
1048         if (level > 0)
1049                 return 0;
1050         if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE))
1051                 return 0;
1052 
1053         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1054         if (!xfs_btree_ptr_is_null(cur, &ptr))
1055                 return 0;
1056         return 1;
1057 }
1058 
1059 STATIC void
1060 xfs_btree_buf_to_ptr(
1061         struct xfs_btree_cur    *cur,
1062         struct xfs_buf          *bp,
1063         union xfs_btree_ptr     *ptr)
1064 {
1065         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1066                 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp,
1067                                         XFS_BUF_ADDR(bp)));
1068         else {
1069                 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp,
1070                                         XFS_BUF_ADDR(bp)));
1071         }
1072 }
1073 
1074 STATIC xfs_daddr_t
1075 xfs_btree_ptr_to_daddr(
1076         struct xfs_btree_cur    *cur,
1077         union xfs_btree_ptr     *ptr)
1078 {
1079         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1080                 ASSERT(ptr->l != cpu_to_be64(NULLDFSBNO));
1081 
1082                 return XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l));
1083         } else {
1084                 ASSERT(cur->bc_private.a.agno != NULLAGNUMBER);
1085                 ASSERT(ptr->s != cpu_to_be32(NULLAGBLOCK));
1086 
1087                 return XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_private.a.agno,
1088                                         be32_to_cpu(ptr->s));
1089         }
1090 }
1091 
1092 STATIC void
1093 xfs_btree_set_refs(
1094         struct xfs_btree_cur    *cur,
1095         struct xfs_buf          *bp)
1096 {
1097         switch (cur->bc_btnum) {
1098         case XFS_BTNUM_BNO:
1099         case XFS_BTNUM_CNT:
1100                 xfs_buf_set_ref(bp, XFS_ALLOC_BTREE_REF);
1101                 break;
1102         case XFS_BTNUM_INO:
1103                 xfs_buf_set_ref(bp, XFS_INO_BTREE_REF);
1104                 break;
1105         case XFS_BTNUM_BMAP:
1106                 xfs_buf_set_ref(bp, XFS_BMAP_BTREE_REF);
1107                 break;
1108         default:
1109                 ASSERT(0);
1110         }
1111 }
1112 
1113 STATIC int
1114 xfs_btree_get_buf_block(
1115         struct xfs_btree_cur    *cur,
1116         union xfs_btree_ptr     *ptr,
1117         int                     flags,
1118         struct xfs_btree_block  **block,
1119         struct xfs_buf          **bpp)
1120 {
1121         struct xfs_mount        *mp = cur->bc_mp;
1122         xfs_daddr_t             d;
1123 
1124         /* need to sort out how callers deal with failures first */
1125         ASSERT(!(flags & XBF_TRYLOCK));
1126 
1127         d = xfs_btree_ptr_to_daddr(cur, ptr);
1128         *bpp = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d,
1129                                  mp->m_bsize, flags);
1130 
1131         if (!*bpp)
1132                 return ENOMEM;
1133 
1134         (*bpp)->b_ops = cur->bc_ops->buf_ops;
1135         *block = XFS_BUF_TO_BLOCK(*bpp);
1136         return 0;
1137 }
1138 
1139 /*
1140  * Read in the buffer at the given ptr and return the buffer and
1141  * the block pointer within the buffer.
1142  */
1143 STATIC int
1144 xfs_btree_read_buf_block(
1145         struct xfs_btree_cur    *cur,
1146         union xfs_btree_ptr     *ptr,
1147         int                     level,
1148         int                     flags,
1149         struct xfs_btree_block  **block,
1150         struct xfs_buf          **bpp)
1151 {
1152         struct xfs_mount        *mp = cur->bc_mp;
1153         xfs_daddr_t             d;
1154         int                     error;
1155 
1156         /* need to sort out how callers deal with failures first */
1157         ASSERT(!(flags & XBF_TRYLOCK));
1158 
1159         d = xfs_btree_ptr_to_daddr(cur, ptr);
1160         error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d,
1161                                    mp->m_bsize, flags, bpp,
1162                                    cur->bc_ops->buf_ops);
1163         if (error)
1164                 return error;
1165 
1166         ASSERT(!xfs_buf_geterror(*bpp));
1167         xfs_btree_set_refs(cur, *bpp);
1168         *block = XFS_BUF_TO_BLOCK(*bpp);
1169         return 0;
1170 }
1171 
1172 /*
1173  * Copy keys from one btree block to another.
1174  */
1175 STATIC void
1176 xfs_btree_copy_keys(
1177         struct xfs_btree_cur    *cur,
1178         union xfs_btree_key     *dst_key,
1179         union xfs_btree_key     *src_key,
1180         int                     numkeys)
1181 {
1182         ASSERT(numkeys >= 0);
1183         memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len);
1184 }
1185 
1186 /*
1187  * Copy records from one btree block to another.
1188  */
1189 STATIC void
1190 xfs_btree_copy_recs(
1191         struct xfs_btree_cur    *cur,
1192         union xfs_btree_rec     *dst_rec,
1193         union xfs_btree_rec     *src_rec,
1194         int                     numrecs)
1195 {
1196         ASSERT(numrecs >= 0);
1197         memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len);
1198 }
1199 
1200 /*
1201  * Copy block pointers from one btree block to another.
1202  */
1203 STATIC void
1204 xfs_btree_copy_ptrs(
1205         struct xfs_btree_cur    *cur,
1206         union xfs_btree_ptr     *dst_ptr,
1207         union xfs_btree_ptr     *src_ptr,
1208         int                     numptrs)
1209 {
1210         ASSERT(numptrs >= 0);
1211         memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur));
1212 }
1213 
1214 /*
1215  * Shift keys one index left/right inside a single btree block.
1216  */
1217 STATIC void
1218 xfs_btree_shift_keys(
1219         struct xfs_btree_cur    *cur,
1220         union xfs_btree_key     *key,
1221         int                     dir,
1222         int                     numkeys)
1223 {
1224         char                    *dst_key;
1225 
1226         ASSERT(numkeys >= 0);
1227         ASSERT(dir == 1 || dir == -1);
1228 
1229         dst_key = (char *)key + (dir * cur->bc_ops->key_len);
1230         memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
1231 }
1232 
1233 /*
1234  * Shift records one index left/right inside a single btree block.
1235  */
1236 STATIC void
1237 xfs_btree_shift_recs(
1238         struct xfs_btree_cur    *cur,
1239         union xfs_btree_rec     *rec,
1240         int                     dir,
1241         int                     numrecs)
1242 {
1243         char                    *dst_rec;
1244 
1245         ASSERT(numrecs >= 0);
1246         ASSERT(dir == 1 || dir == -1);
1247 
1248         dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);
1249         memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);
1250 }
1251 
1252 /*
1253  * Shift block pointers one index left/right inside a single btree block.
1254  */
1255 STATIC void
1256 xfs_btree_shift_ptrs(
1257         struct xfs_btree_cur    *cur,
1258         union xfs_btree_ptr     *ptr,
1259         int                     dir,
1260         int                     numptrs)
1261 {
1262         char                    *dst_ptr;
1263 
1264         ASSERT(numptrs >= 0);
1265         ASSERT(dir == 1 || dir == -1);
1266 
1267         dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur));
1268         memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur));
1269 }
1270 
1271 /*
1272  * Log key values from the btree block.
1273  */
1274 STATIC void
1275 xfs_btree_log_keys(
1276         struct xfs_btree_cur    *cur,
1277         struct xfs_buf          *bp,
1278         int                     first,
1279         int                     last)
1280 {
1281         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1282         XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1283 
1284         if (bp) {
1285                 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1286                 xfs_trans_log_buf(cur->bc_tp, bp,
1287                                   xfs_btree_key_offset(cur, first),
1288                                   xfs_btree_key_offset(cur, last + 1) - 1);
1289         } else {
1290                 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1291                                 xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1292         }
1293 
1294         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1295 }
1296 
1297 /*
1298  * Log record values from the btree block.
1299  */
1300 void
1301 xfs_btree_log_recs(
1302         struct xfs_btree_cur    *cur,
1303         struct xfs_buf          *bp,
1304         int                     first,
1305         int                     last)
1306 {
1307         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1308         XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1309 
1310         xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1311         xfs_trans_log_buf(cur->bc_tp, bp,
1312                           xfs_btree_rec_offset(cur, first),
1313                           xfs_btree_rec_offset(cur, last + 1) - 1);
1314 
1315         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1316 }
1317 
1318 /*
1319  * Log block pointer fields from a btree block (nonleaf).
1320  */
1321 STATIC void
1322 xfs_btree_log_ptrs(
1323         struct xfs_btree_cur    *cur,   /* btree cursor */
1324         struct xfs_buf          *bp,    /* buffer containing btree block */
1325         int                     first,  /* index of first pointer to log */
1326         int                     last)   /* index of last pointer to log */
1327 {
1328         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1329         XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1330 
1331         if (bp) {
1332                 struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
1333                 int                     level = xfs_btree_get_level(block);
1334 
1335                 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1336                 xfs_trans_log_buf(cur->bc_tp, bp,
1337                                 xfs_btree_ptr_offset(cur, first, level),
1338                                 xfs_btree_ptr_offset(cur, last + 1, level) - 1);
1339         } else {
1340                 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1341                         xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1342         }
1343 
1344         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1345 }
1346 
1347 /*
1348  * Log fields from a btree block header.
1349  */
1350 void
1351 xfs_btree_log_block(
1352         struct xfs_btree_cur    *cur,   /* btree cursor */
1353         struct xfs_buf          *bp,    /* buffer containing btree block */
1354         int                     fields) /* mask of fields: XFS_BB_... */
1355 {
1356         int                     first;  /* first byte offset logged */
1357         int                     last;   /* last byte offset logged */
1358         static const short      soffsets[] = {  /* table of offsets (short) */
1359                 offsetof(struct xfs_btree_block, bb_magic),
1360                 offsetof(struct xfs_btree_block, bb_level),
1361                 offsetof(struct xfs_btree_block, bb_numrecs),
1362                 offsetof(struct xfs_btree_block, bb_u.s.bb_leftsib),
1363                 offsetof(struct xfs_btree_block, bb_u.s.bb_rightsib),
1364                 offsetof(struct xfs_btree_block, bb_u.s.bb_blkno),
1365                 offsetof(struct xfs_btree_block, bb_u.s.bb_lsn),
1366                 offsetof(struct xfs_btree_block, bb_u.s.bb_uuid),
1367                 offsetof(struct xfs_btree_block, bb_u.s.bb_owner),
1368                 offsetof(struct xfs_btree_block, bb_u.s.bb_crc),
1369                 XFS_BTREE_SBLOCK_CRC_LEN
1370         };
1371         static const short      loffsets[] = {  /* table of offsets (long) */
1372                 offsetof(struct xfs_btree_block, bb_magic),
1373                 offsetof(struct xfs_btree_block, bb_level),
1374                 offsetof(struct xfs_btree_block, bb_numrecs),
1375                 offsetof(struct xfs_btree_block, bb_u.l.bb_leftsib),
1376                 offsetof(struct xfs_btree_block, bb_u.l.bb_rightsib),
1377                 offsetof(struct xfs_btree_block, bb_u.l.bb_blkno),
1378                 offsetof(struct xfs_btree_block, bb_u.l.bb_lsn),
1379                 offsetof(struct xfs_btree_block, bb_u.l.bb_uuid),
1380                 offsetof(struct xfs_btree_block, bb_u.l.bb_owner),
1381                 offsetof(struct xfs_btree_block, bb_u.l.bb_crc),
1382                 offsetof(struct xfs_btree_block, bb_u.l.bb_pad),
1383                 XFS_BTREE_LBLOCK_CRC_LEN
1384         };
1385 
1386         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1387         XFS_BTREE_TRACE_ARGBI(cur, bp, fields);
1388 
1389         if (bp) {
1390                 int nbits;
1391 
1392                 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
1393                         /*
1394                          * We don't log the CRC when updating a btree
1395                          * block but instead recreate it during log
1396                          * recovery.  As the log buffers have checksums
1397                          * of their own this is safe and avoids logging a crc
1398                          * update in a lot of places.
1399                          */
1400                         if (fields == XFS_BB_ALL_BITS)
1401                                 fields = XFS_BB_ALL_BITS_CRC;
1402                         nbits = XFS_BB_NUM_BITS_CRC;
1403                 } else {
1404                         nbits = XFS_BB_NUM_BITS;
1405                 }
1406                 xfs_btree_offsets(fields,
1407                                   (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
1408                                         loffsets : soffsets,
1409                                   nbits, &first, &last);
1410                 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1411                 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
1412         } else {
1413                 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1414                         xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1415         }
1416 
1417         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1418 }
1419 
1420 /*
1421  * Increment cursor by one record at the level.
1422  * For nonzero levels the leaf-ward information is untouched.
1423  */
1424 int                                             /* error */
1425 xfs_btree_increment(
1426         struct xfs_btree_cur    *cur,
1427         int                     level,
1428         int                     *stat)          /* success/failure */
1429 {
1430         struct xfs_btree_block  *block;
1431         union xfs_btree_ptr     ptr;
1432         struct xfs_buf          *bp;
1433         int                     error;          /* error return value */
1434         int                     lev;
1435 
1436         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1437         XFS_BTREE_TRACE_ARGI(cur, level);
1438 
1439         ASSERT(level < cur->bc_nlevels);
1440 
1441         /* Read-ahead to the right at this level. */
1442         xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1443 
1444         /* Get a pointer to the btree block. */
1445         block = xfs_btree_get_block(cur, level, &bp);
1446 
1447 #ifdef DEBUG
1448         error = xfs_btree_check_block(cur, block, level, bp);
1449         if (error)
1450                 goto error0;
1451 #endif
1452 
1453         /* We're done if we remain in the block after the increment. */
1454         if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block))
1455                 goto out1;
1456 
1457         /* Fail if we just went off the right edge of the tree. */
1458         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1459         if (xfs_btree_ptr_is_null(cur, &ptr))
1460                 goto out0;
1461 
1462         XFS_BTREE_STATS_INC(cur, increment);
1463 
1464         /*
1465          * March up the tree incrementing pointers.
1466          * Stop when we don't go off the right edge of a block.
1467          */
1468         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1469                 block = xfs_btree_get_block(cur, lev, &bp);
1470 
1471 #ifdef DEBUG
1472                 error = xfs_btree_check_block(cur, block, lev, bp);
1473                 if (error)
1474                         goto error0;
1475 #endif
1476 
1477                 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block))
1478                         break;
1479 
1480                 /* Read-ahead the right block for the next loop. */
1481                 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1482         }
1483 
1484         /*
1485          * If we went off the root then we are either seriously
1486          * confused or have the tree root in an inode.
1487          */
1488         if (lev == cur->bc_nlevels) {
1489                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1490                         goto out0;
1491                 ASSERT(0);
1492                 error = EFSCORRUPTED;
1493                 goto error0;
1494         }
1495         ASSERT(lev < cur->bc_nlevels);
1496 
1497         /*
1498          * Now walk back down the tree, fixing up the cursor's buffer
1499          * pointers and key numbers.
1500          */
1501         for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1502                 union xfs_btree_ptr     *ptrp;
1503 
1504                 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1505                 error = xfs_btree_read_buf_block(cur, ptrp, --lev,
1506                                                         0, &block, &bp);
1507                 if (error)
1508                         goto error0;
1509 
1510                 xfs_btree_setbuf(cur, lev, bp);
1511                 cur->bc_ptrs[lev] = 1;
1512         }
1513 out1:
1514         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1515         *stat = 1;
1516         return 0;
1517 
1518 out0:
1519         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1520         *stat = 0;
1521         return 0;
1522 
1523 error0:
1524         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1525         return error;
1526 }
1527 
1528 /*
1529  * Decrement cursor by one record at the level.
1530  * For nonzero levels the leaf-ward information is untouched.
1531  */
1532 int                                             /* error */
1533 xfs_btree_decrement(
1534         struct xfs_btree_cur    *cur,
1535         int                     level,
1536         int                     *stat)          /* success/failure */
1537 {
1538         struct xfs_btree_block  *block;
1539         xfs_buf_t               *bp;
1540         int                     error;          /* error return value */
1541         int                     lev;
1542         union xfs_btree_ptr     ptr;
1543 
1544         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1545         XFS_BTREE_TRACE_ARGI(cur, level);
1546 
1547         ASSERT(level < cur->bc_nlevels);
1548 
1549         /* Read-ahead to the left at this level. */
1550         xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1551 
1552         /* We're done if we remain in the block after the decrement. */
1553         if (--cur->bc_ptrs[level] > 0)
1554                 goto out1;
1555 
1556         /* Get a pointer to the btree block. */
1557         block = xfs_btree_get_block(cur, level, &bp);
1558 
1559 #ifdef DEBUG
1560         error = xfs_btree_check_block(cur, block, level, bp);
1561         if (error)
1562                 goto error0;
1563 #endif
1564 
1565         /* Fail if we just went off the left edge of the tree. */
1566         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
1567         if (xfs_btree_ptr_is_null(cur, &ptr))
1568                 goto out0;
1569 
1570         XFS_BTREE_STATS_INC(cur, decrement);
1571 
1572         /*
1573          * March up the tree decrementing pointers.
1574          * Stop when we don't go off the left edge of a block.
1575          */
1576         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1577                 if (--cur->bc_ptrs[lev] > 0)
1578                         break;
1579                 /* Read-ahead the left block for the next loop. */
1580                 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1581         }
1582 
1583         /*
1584          * If we went off the root then we are seriously confused.
1585          * or the root of the tree is in an inode.
1586          */
1587         if (lev == cur->bc_nlevels) {
1588                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1589                         goto out0;
1590                 ASSERT(0);
1591                 error = EFSCORRUPTED;
1592                 goto error0;
1593         }
1594         ASSERT(lev < cur->bc_nlevels);
1595 
1596         /*
1597          * Now walk back down the tree, fixing up the cursor's buffer
1598          * pointers and key numbers.
1599          */
1600         for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1601                 union xfs_btree_ptr     *ptrp;
1602 
1603                 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1604                 error = xfs_btree_read_buf_block(cur, ptrp, --lev,
1605                                                         0, &block, &bp);
1606                 if (error)
1607                         goto error0;
1608                 xfs_btree_setbuf(cur, lev, bp);
1609                 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block);
1610         }
1611 out1:
1612         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1613         *stat = 1;
1614         return 0;
1615 
1616 out0:
1617         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1618         *stat = 0;
1619         return 0;
1620 
1621 error0:
1622         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1623         return error;
1624 }
1625 
1626 STATIC int
1627 xfs_btree_lookup_get_block(
1628         struct xfs_btree_cur    *cur,   /* btree cursor */
1629         int                     level,  /* level in the btree */
1630         union xfs_btree_ptr     *pp,    /* ptr to btree block */
1631         struct xfs_btree_block  **blkp) /* return btree block */
1632 {
1633         struct xfs_buf          *bp;    /* buffer pointer for btree block */
1634         int                     error = 0;
1635 
1636         /* special case the root block if in an inode */
1637         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1638             (level == cur->bc_nlevels - 1)) {
1639                 *blkp = xfs_btree_get_iroot(cur);
1640                 return 0;
1641         }
1642 
1643         /*
1644          * If the old buffer at this level for the disk address we are
1645          * looking for re-use it.
1646          *
1647          * Otherwise throw it away and get a new one.
1648          */
1649         bp = cur->bc_bufs[level];
1650         if (bp && XFS_BUF_ADDR(bp) == xfs_btree_ptr_to_daddr(cur, pp)) {
1651                 *blkp = XFS_BUF_TO_BLOCK(bp);
1652                 return 0;
1653         }
1654 
1655         error = xfs_btree_read_buf_block(cur, pp, level, 0, blkp, &bp);
1656         if (error)
1657                 return error;
1658 
1659         xfs_btree_setbuf(cur, level, bp);
1660         return 0;
1661 }
1662 
1663 /*
1664  * Get current search key.  For level 0 we don't actually have a key
1665  * structure so we make one up from the record.  For all other levels
1666  * we just return the right key.
1667  */
1668 STATIC union xfs_btree_key *
1669 xfs_lookup_get_search_key(
1670         struct xfs_btree_cur    *cur,
1671         int                     level,
1672         int                     keyno,
1673         struct xfs_btree_block  *block,
1674         union xfs_btree_key     *kp)
1675 {
1676         if (level == 0) {
1677                 cur->bc_ops->init_key_from_rec(kp,
1678                                 xfs_btree_rec_addr(cur, keyno, block));
1679                 return kp;
1680         }
1681 
1682         return xfs_btree_key_addr(cur, keyno, block);
1683 }
1684 
1685 /*
1686  * Lookup the record.  The cursor is made to point to it, based on dir.
1687  * Return 0 if can't find any such record, 1 for success.
1688  */
1689 int                                     /* error */
1690 xfs_btree_lookup(
1691         struct xfs_btree_cur    *cur,   /* btree cursor */
1692         xfs_lookup_t            dir,    /* <=, ==, or >= */
1693         int                     *stat)  /* success/failure */
1694 {
1695         struct xfs_btree_block  *block; /* current btree block */
1696         __int64_t               diff;   /* difference for the current key */
1697         int                     error;  /* error return value */
1698         int                     keyno;  /* current key number */
1699         int                     level;  /* level in the btree */
1700         union xfs_btree_ptr     *pp;    /* ptr to btree block */
1701         union xfs_btree_ptr     ptr;    /* ptr to btree block */
1702 
1703         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1704         XFS_BTREE_TRACE_ARGI(cur, dir);
1705 
1706         XFS_BTREE_STATS_INC(cur, lookup);
1707 
1708         block = NULL;
1709         keyno = 0;
1710 
1711         /* initialise start pointer from cursor */
1712         cur->bc_ops->init_ptr_from_cur(cur, &ptr);
1713         pp = &ptr;
1714 
1715         /*
1716          * Iterate over each level in the btree, starting at the root.
1717          * For each level above the leaves, find the key we need, based
1718          * on the lookup record, then follow the corresponding block
1719          * pointer down to the next level.
1720          */
1721         for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1722                 /* Get the block we need to do the lookup on. */
1723                 error = xfs_btree_lookup_get_block(cur, level, pp, &block);
1724                 if (error)
1725                         goto error0;
1726 
1727                 if (diff == 0) {
1728                         /*
1729                          * If we already had a key match at a higher level, we
1730                          * know we need to use the first entry in this block.
1731                          */
1732                         keyno = 1;
1733                 } else {
1734                         /* Otherwise search this block. Do a binary search. */
1735 
1736                         int     high;   /* high entry number */
1737                         int     low;    /* low entry number */
1738 
1739                         /* Set low and high entry numbers, 1-based. */
1740                         low = 1;
1741                         high = xfs_btree_get_numrecs(block);
1742                         if (!high) {
1743                                 /* Block is empty, must be an empty leaf. */
1744                                 ASSERT(level == 0 && cur->bc_nlevels == 1);
1745 
1746                                 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1747                                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1748                                 *stat = 0;
1749                                 return 0;
1750                         }
1751 
1752                         /* Binary search the block. */
1753                         while (low <= high) {
1754                                 union xfs_btree_key     key;
1755                                 union xfs_btree_key     *kp;
1756 
1757                                 XFS_BTREE_STATS_INC(cur, compare);
1758 
1759                                 /* keyno is average of low and high. */
1760                                 keyno = (low + high) >> 1;
1761 
1762                                 /* Get current search key */
1763                                 kp = xfs_lookup_get_search_key(cur, level,
1764                                                 keyno, block, &key);
1765 
1766                                 /*
1767                                  * Compute difference to get next direction:
1768                                  *  - less than, move right
1769                                  *  - greater than, move left
1770                                  *  - equal, we're done
1771                                  */
1772                                 diff = cur->bc_ops->key_diff(cur, kp);
1773                                 if (diff < 0)
1774                                         low = keyno + 1;
1775                                 else if (diff > 0)
1776                                         high = keyno - 1;
1777                                 else
1778                                         break;
1779                         }
1780                 }
1781 
1782                 /*
1783                  * If there are more levels, set up for the next level
1784                  * by getting the block number and filling in the cursor.
1785                  */
1786                 if (level > 0) {
1787                         /*
1788                          * If we moved left, need the previous key number,
1789                          * unless there isn't one.
1790                          */
1791                         if (diff > 0 && --keyno < 1)
1792                                 keyno = 1;
1793                         pp = xfs_btree_ptr_addr(cur, keyno, block);
1794 
1795 #ifdef DEBUG
1796                         error = xfs_btree_check_ptr(cur, pp, 0, level);
1797                         if (error)
1798                                 goto error0;
1799 #endif
1800                         cur->bc_ptrs[level] = keyno;
1801                 }
1802         }
1803 
1804         /* Done with the search. See if we need to adjust the results. */
1805         if (dir != XFS_LOOKUP_LE && diff < 0) {
1806                 keyno++;
1807                 /*
1808                  * If ge search and we went off the end of the block, but it's
1809                  * not the last block, we're in the wrong block.
1810                  */
1811                 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1812                 if (dir == XFS_LOOKUP_GE &&
1813                     keyno > xfs_btree_get_numrecs(block) &&
1814                     !xfs_btree_ptr_is_null(cur, &ptr)) {
1815                         int     i;
1816 
1817                         cur->bc_ptrs[0] = keyno;
1818                         error = xfs_btree_increment(cur, 0, &i);
1819                         if (error)
1820                                 goto error0;
1821                         XFS_WANT_CORRUPTED_RETURN(i == 1);
1822                         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1823                         *stat = 1;
1824                         return 0;
1825                 }
1826         } else if (dir == XFS_LOOKUP_LE && diff > 0)
1827                 keyno--;
1828         cur->bc_ptrs[0] = keyno;
1829 
1830         /* Return if we succeeded or not. */
1831         if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))
1832                 *stat = 0;
1833         else if (dir != XFS_LOOKUP_EQ || diff == 0)
1834                 *stat = 1;
1835         else
1836                 *stat = 0;
1837         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1838         return 0;
1839 
1840 error0:
1841         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1842         return error;
1843 }
1844 
1845 /*
1846  * Update keys at all levels from here to the root along the cursor's path.
1847  */
1848 STATIC int
1849 xfs_btree_updkey(
1850         struct xfs_btree_cur    *cur,
1851         union xfs_btree_key     *keyp,
1852         int                     level)
1853 {
1854         struct xfs_btree_block  *block;
1855         struct xfs_buf          *bp;
1856         union xfs_btree_key     *kp;
1857         int                     ptr;
1858 
1859         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1860         XFS_BTREE_TRACE_ARGIK(cur, level, keyp);
1861 
1862         ASSERT(!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || level >= 1);
1863 
1864         /*
1865          * Go up the tree from this level toward the root.
1866          * At each level, update the key value to the value input.
1867          * Stop when we reach a level where the cursor isn't pointing
1868          * at the first entry in the block.
1869          */
1870         for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1871 #ifdef DEBUG
1872                 int             error;
1873 #endif
1874                 block = xfs_btree_get_block(cur, level, &bp);
1875 #ifdef DEBUG
1876                 error = xfs_btree_check_block(cur, block, level, bp);
1877                 if (error) {
1878                         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1879                         return error;
1880                 }
1881 #endif
1882                 ptr = cur->bc_ptrs[level];
1883                 kp = xfs_btree_key_addr(cur, ptr, block);
1884                 xfs_btree_copy_keys(cur, kp, keyp, 1);
1885                 xfs_btree_log_keys(cur, bp, ptr, ptr);
1886         }
1887 
1888         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1889         return 0;
1890 }
1891 
1892 /*
1893  * Update the record referred to by cur to the value in the
1894  * given record. This either works (return 0) or gets an
1895  * EFSCORRUPTED error.
1896  */
1897 int
1898 xfs_btree_update(
1899         struct xfs_btree_cur    *cur,
1900         union xfs_btree_rec     *rec)
1901 {
1902         struct xfs_btree_block  *block;
1903         struct xfs_buf          *bp;
1904         int                     error;
1905         int                     ptr;
1906         union xfs_btree_rec     *rp;
1907 
1908         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1909         XFS_BTREE_TRACE_ARGR(cur, rec);
1910 
1911         /* Pick up the current block. */
1912         block = xfs_btree_get_block(cur, 0, &bp);
1913 
1914 #ifdef DEBUG
1915         error = xfs_btree_check_block(cur, block, 0, bp);
1916         if (error)
1917                 goto error0;
1918 #endif
1919         /* Get the address of the rec to be updated. */
1920         ptr = cur->bc_ptrs[0];
1921         rp = xfs_btree_rec_addr(cur, ptr, block);
1922 
1923         /* Fill in the new contents and log them. */
1924         xfs_btree_copy_recs(cur, rp, rec, 1);
1925         xfs_btree_log_recs(cur, bp, ptr, ptr);
1926 
1927         /*
1928          * If we are tracking the last record in the tree and
1929          * we are at the far right edge of the tree, update it.
1930          */
1931         if (xfs_btree_is_lastrec(cur, block, 0)) {
1932                 cur->bc_ops->update_lastrec(cur, block, rec,
1933                                             ptr, LASTREC_UPDATE);
1934         }
1935 
1936         /* Updating first rec in leaf. Pass new key value up to our parent. */
1937         if (ptr == 1) {
1938                 union xfs_btree_key     key;
1939 
1940                 cur->bc_ops->init_key_from_rec(&key, rec);
1941                 error = xfs_btree_updkey(cur, &key, 1);
1942                 if (error)
1943                         goto error0;
1944         }
1945 
1946         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1947         return 0;
1948 
1949 error0:
1950         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1951         return error;
1952 }
1953 
1954 /*
1955  * Move 1 record left from cur/level if possible.
1956  * Update cur to reflect the new path.
1957  */
1958 STATIC int                                      /* error */
1959 xfs_btree_lshift(
1960         struct xfs_btree_cur    *cur,
1961         int                     level,
1962         int                     *stat)          /* success/failure */
1963 {
1964         union xfs_btree_key     key;            /* btree key */
1965         struct xfs_buf          *lbp;           /* left buffer pointer */
1966         struct xfs_btree_block  *left;          /* left btree block */
1967         int                     lrecs;          /* left record count */
1968         struct xfs_buf          *rbp;           /* right buffer pointer */
1969         struct xfs_btree_block  *right;         /* right btree block */
1970         int                     rrecs;          /* right record count */
1971         union xfs_btree_ptr     lptr;           /* left btree pointer */
1972         union xfs_btree_key     *rkp = NULL;    /* right btree key */
1973         union xfs_btree_ptr     *rpp = NULL;    /* right address pointer */
1974         union xfs_btree_rec     *rrp = NULL;    /* right record pointer */
1975         int                     error;          /* error return value */
1976 
1977         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1978         XFS_BTREE_TRACE_ARGI(cur, level);
1979 
1980         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1981             level == cur->bc_nlevels - 1)
1982                 goto out0;
1983 
1984         /* Set up variables for this block as "right". */
1985         right = xfs_btree_get_block(cur, level, &rbp);
1986 
1987 #ifdef DEBUG
1988         error = xfs_btree_check_block(cur, right, level, rbp);
1989         if (error)
1990                 goto error0;
1991 #endif
1992 
1993         /* If we've got no left sibling then we can't shift an entry left. */
1994         xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
1995         if (xfs_btree_ptr_is_null(cur, &lptr))
1996                 goto out0;
1997 
1998         /*
1999          * If the cursor entry is the one that would be moved, don't
2000          * do it... it's too complicated.
2001          */
2002         if (cur->bc_ptrs[level] <= 1)
2003                 goto out0;
2004 
2005         /* Set up the left neighbor as "left". */
2006         error = xfs_btree_read_buf_block(cur, &lptr, level, 0, &left, &lbp);
2007         if (error)
2008                 goto error0;
2009 
2010         /* If it's full, it can't take another entry. */
2011         lrecs = xfs_btree_get_numrecs(left);
2012         if (lrecs == cur->bc_ops->get_maxrecs(cur, level))
2013                 goto out0;
2014 
2015         rrecs = xfs_btree_get_numrecs(right);
2016 
2017         /*
2018          * We add one entry to the left side and remove one for the right side.
2019          * Account for it here, the changes will be updated on disk and logged
2020          * later.
2021          */
2022         lrecs++;
2023         rrecs--;
2024 
2025         XFS_BTREE_STATS_INC(cur, lshift);
2026         XFS_BTREE_STATS_ADD(cur, moves, 1);
2027 
2028         /*
2029          * If non-leaf, copy a key and a ptr to the left block.
2030          * Log the changes to the left block.
2031          */
2032         if (level > 0) {
2033                 /* It's a non-leaf.  Move keys and pointers. */
2034                 union xfs_btree_key     *lkp;   /* left btree key */
2035                 union xfs_btree_ptr     *lpp;   /* left address pointer */
2036 
2037                 lkp = xfs_btree_key_addr(cur, lrecs, left);
2038                 rkp = xfs_btree_key_addr(cur, 1, right);
2039 
2040                 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2041                 rpp = xfs_btree_ptr_addr(cur, 1, right);
2042 #ifdef DEBUG
2043                 error = xfs_btree_check_ptr(cur, rpp, 0, level);
2044                 if (error)
2045                         goto error0;
2046 #endif
2047                 xfs_btree_copy_keys(cur, lkp, rkp, 1);
2048                 xfs_btree_copy_ptrs(cur, lpp, rpp, 1);
2049 
2050                 xfs_btree_log_keys(cur, lbp, lrecs, lrecs);
2051                 xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs);
2052 
2053                 ASSERT(cur->bc_ops->keys_inorder(cur,
2054                         xfs_btree_key_addr(cur, lrecs - 1, left), lkp));
2055         } else {
2056                 /* It's a leaf.  Move records.  */
2057                 union xfs_btree_rec     *lrp;   /* left record pointer */
2058 
2059                 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2060                 rrp = xfs_btree_rec_addr(cur, 1, right);
2061 
2062                 xfs_btree_copy_recs(cur, lrp, rrp, 1);
2063                 xfs_btree_log_recs(cur, lbp, lrecs, lrecs);
2064 
2065                 ASSERT(cur->bc_ops->recs_inorder(cur,
2066                         xfs_btree_rec_addr(cur, lrecs - 1, left), lrp));
2067         }
2068 
2069         xfs_btree_set_numrecs(left, lrecs);
2070         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2071 
2072         xfs_btree_set_numrecs(right, rrecs);
2073         xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2074 
2075         /*
2076          * Slide the contents of right down one entry.
2077          */
2078         XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1);
2079         if (level > 0) {
2080                 /* It's a nonleaf. operate on keys and ptrs */
2081 #ifdef DEBUG
2082                 int                     i;              /* loop index */
2083 
2084                 for (i = 0; i < rrecs; i++) {
2085                         error = xfs_btree_check_ptr(cur, rpp, i + 1, level);
2086                         if (error)
2087                                 goto error0;
2088                 }
2089 #endif
2090                 xfs_btree_shift_keys(cur,
2091                                 xfs_btree_key_addr(cur, 2, right),
2092                                 -1, rrecs);
2093                 xfs_btree_shift_ptrs(cur,
2094                                 xfs_btree_ptr_addr(cur, 2, right),
2095                                 -1, rrecs);
2096 
2097                 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2098                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2099         } else {
2100                 /* It's a leaf. operate on records */
2101                 xfs_btree_shift_recs(cur,
2102                         xfs_btree_rec_addr(cur, 2, right),
2103                         -1, rrecs);
2104                 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2105 
2106                 /*
2107                  * If it's the first record in the block, we'll need a key
2108                  * structure to pass up to the next level (updkey).
2109                  */
2110                 cur->bc_ops->init_key_from_rec(&key,
2111                         xfs_btree_rec_addr(cur, 1, right));
2112                 rkp = &key;
2113         }
2114 
2115         /* Update the parent key values of right. */
2116         error = xfs_btree_updkey(cur, rkp, level + 1);
2117         if (error)
2118                 goto error0;
2119 
2120         /* Slide the cursor value left one. */
2121         cur->bc_ptrs[level]--;
2122 
2123         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2124         *stat = 1;
2125         return 0;
2126 
2127 out0:
2128         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2129         *stat = 0;
2130         return 0;
2131 
2132 error0:
2133         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2134         return error;
2135 }
2136 
2137 /*
2138  * Move 1 record right from cur/level if possible.
2139  * Update cur to reflect the new path.
2140  */
2141 STATIC int                                      /* error */
2142 xfs_btree_rshift(
2143         struct xfs_btree_cur    *cur,
2144         int                     level,
2145         int                     *stat)          /* success/failure */
2146 {
2147         union xfs_btree_key     key;            /* btree key */
2148         struct xfs_buf          *lbp;           /* left buffer pointer */
2149         struct xfs_btree_block  *left;          /* left btree block */
2150         struct xfs_buf          *rbp;           /* right buffer pointer */
2151         struct xfs_btree_block  *right;         /* right btree block */
2152         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
2153         union xfs_btree_ptr     rptr;           /* right block pointer */
2154         union xfs_btree_key     *rkp;           /* right btree key */
2155         int                     rrecs;          /* right record count */
2156         int                     lrecs;          /* left record count */
2157         int                     error;          /* error return value */
2158         int                     i;              /* loop counter */
2159 
2160         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2161         XFS_BTREE_TRACE_ARGI(cur, level);
2162 
2163         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2164             (level == cur->bc_nlevels - 1))
2165                 goto out0;
2166 
2167         /* Set up variables for this block as "left". */
2168         left = xfs_btree_get_block(cur, level, &lbp);
2169 
2170 #ifdef DEBUG
2171         error = xfs_btree_check_block(cur, left, level, lbp);
2172         if (error)
2173                 goto error0;
2174 #endif
2175 
2176         /* If we've got no right sibling then we can't shift an entry right. */
2177         xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2178         if (xfs_btree_ptr_is_null(cur, &rptr))
2179                 goto out0;
2180 
2181         /*
2182          * If the cursor entry is the one that would be moved, don't
2183          * do it... it's too complicated.
2184          */
2185         lrecs = xfs_btree_get_numrecs(left);
2186         if (cur->bc_ptrs[level] >= lrecs)
2187                 goto out0;
2188 
2189         /* Set up the right neighbor as "right". */
2190         error = xfs_btree_read_buf_block(cur, &rptr, level, 0, &right, &rbp);
2191         if (error)
2192                 goto error0;
2193 
2194         /* If it's full, it can't take another entry. */
2195         rrecs = xfs_btree_get_numrecs(right);
2196         if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
2197                 goto out0;
2198 
2199         XFS_BTREE_STATS_INC(cur, rshift);
2200         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2201 
2202         /*
2203          * Make a hole at the start of the right neighbor block, then
2204          * copy the last left block entry to the hole.
2205          */
2206         if (level > 0) {
2207                 /* It's a nonleaf. make a hole in the keys and ptrs */
2208                 union xfs_btree_key     *lkp;
2209                 union xfs_btree_ptr     *lpp;
2210                 union xfs_btree_ptr     *rpp;
2211 
2212                 lkp = xfs_btree_key_addr(cur, lrecs, left);
2213                 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2214                 rkp = xfs_btree_key_addr(cur, 1, right);
2215                 rpp = xfs_btree_ptr_addr(cur, 1, right);
2216 
2217 #ifdef DEBUG
2218                 for (i = rrecs - 1; i >= 0; i--) {
2219                         error = xfs_btree_check_ptr(cur, rpp, i, level);
2220                         if (error)
2221                                 goto error0;
2222                 }
2223 #endif
2224 
2225                 xfs_btree_shift_keys(cur, rkp, 1, rrecs);
2226                 xfs_btree_shift_ptrs(cur, rpp, 1, rrecs);
2227 
2228 #ifdef DEBUG
2229                 error = xfs_btree_check_ptr(cur, lpp, 0, level);
2230                 if (error)
2231                         goto error0;
2232 #endif
2233 
2234                 /* Now put the new data in, and log it. */
2235                 xfs_btree_copy_keys(cur, rkp, lkp, 1);
2236                 xfs_btree_copy_ptrs(cur, rpp, lpp, 1);
2237 
2238                 xfs_btree_log_keys(cur, rbp, 1, rrecs + 1);
2239                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
2240 
2241                 ASSERT(cur->bc_ops->keys_inorder(cur, rkp,
2242                         xfs_btree_key_addr(cur, 2, right)));
2243         } else {
2244                 /* It's a leaf. make a hole in the records */
2245                 union xfs_btree_rec     *lrp;
2246                 union xfs_btree_rec     *rrp;
2247 
2248                 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2249                 rrp = xfs_btree_rec_addr(cur, 1, right);
2250 
2251                 xfs_btree_shift_recs(cur, rrp, 1, rrecs);
2252 
2253                 /* Now put the new data in, and log it. */
2254                 xfs_btree_copy_recs(cur, rrp, lrp, 1);
2255                 xfs_btree_log_recs(cur, rbp, 1, rrecs + 1);
2256 
2257                 cur->bc_ops->init_key_from_rec(&key, rrp);
2258                 rkp = &key;
2259 
2260                 ASSERT(cur->bc_ops->recs_inorder(cur, rrp,
2261                         xfs_btree_rec_addr(cur, 2, right)));
2262         }
2263 
2264         /*
2265          * Decrement and log left's numrecs, bump and log right's numrecs.
2266          */
2267         xfs_btree_set_numrecs(left, --lrecs);
2268         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2269 
2270         xfs_btree_set_numrecs(right, ++rrecs);
2271         xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2272 
2273         /*
2274          * Using a temporary cursor, update the parent key values of the
2275          * block on the right.
2276          */
2277         error = xfs_btree_dup_cursor(cur, &tcur);
2278         if (error)
2279                 goto error0;
2280         i = xfs_btree_lastrec(tcur, level);
2281         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
2282 
2283         error = xfs_btree_increment(tcur, level, &i);
2284         if (error)
2285                 goto error1;
2286 
2287         error = xfs_btree_updkey(tcur, rkp, level + 1);
2288         if (error)
2289                 goto error1;
2290 
2291         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2292 
2293         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2294         *stat = 1;
2295         return 0;
2296 
2297 out0:
2298         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2299         *stat = 0;
2300         return 0;
2301 
2302 error0:
2303         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2304         return error;
2305 
2306 error1:
2307         XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR);
2308         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2309         return error;
2310 }
2311 
2312 /*
2313  * Split cur/level block in half.
2314  * Return new block number and the key to its first
2315  * record (to be inserted into parent).
2316  */
2317 STATIC int                                      /* error */
2318 xfs_btree_split(
2319         struct xfs_btree_cur    *cur,
2320         int                     level,
2321         union xfs_btree_ptr     *ptrp,
2322         union xfs_btree_key     *key,
2323         struct xfs_btree_cur    **curp,
2324         int                     *stat)          /* success/failure */
2325 {
2326         union xfs_btree_ptr     lptr;           /* left sibling block ptr */
2327         struct xfs_buf          *lbp;           /* left buffer pointer */
2328         struct xfs_btree_block  *left;          /* left btree block */
2329         union xfs_btree_ptr     rptr;           /* right sibling block ptr */
2330         struct xfs_buf          *rbp;           /* right buffer pointer */
2331         struct xfs_btree_block  *right;         /* right btree block */
2332         union xfs_btree_ptr     rrptr;          /* right-right sibling ptr */
2333         struct xfs_buf          *rrbp;          /* right-right buffer pointer */
2334         struct xfs_btree_block  *rrblock;       /* right-right btree block */
2335         int                     lrecs;
2336         int                     rrecs;
2337         int                     src_index;
2338         int                     error;          /* error return value */
2339 #ifdef DEBUG
2340         int                     i;
2341 #endif
2342 
2343         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2344         XFS_BTREE_TRACE_ARGIPK(cur, level, *ptrp, key);
2345 
2346         XFS_BTREE_STATS_INC(cur, split);
2347 
2348         /* Set up left block (current one). */
2349         left = xfs_btree_get_block(cur, level, &lbp);
2350 
2351 #ifdef DEBUG
2352         error = xfs_btree_check_block(cur, left, level, lbp);
2353         if (error)
2354                 goto error0;
2355 #endif
2356 
2357         xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2358 
2359         /* Allocate the new block. If we can't do it, we're toast. Give up. */
2360         error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, 1, stat);
2361         if (error)
2362                 goto error0;
2363         if (*stat == 0)
2364                 goto out0;
2365         XFS_BTREE_STATS_INC(cur, alloc);
2366 
2367         /* Set up the new block as "right". */
2368         error = xfs_btree_get_buf_block(cur, &rptr, 0, &right, &rbp);
2369         if (error)
2370                 goto error0;
2371 
2372         /* Fill in the btree header for the new right block. */
2373         xfs_btree_init_block_cur(cur, rbp, xfs_btree_get_level(left), 0);
2374 
2375         /*
2376          * Split the entries between the old and the new block evenly.
2377          * Make sure that if there's an odd number of entries now, that
2378          * each new block will have the same number of entries.
2379          */
2380         lrecs = xfs_btree_get_numrecs(left);
2381         rrecs = lrecs / 2;
2382         if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1)
2383                 rrecs++;
2384         src_index = (lrecs - rrecs + 1);
2385 
2386         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2387 
2388         /*
2389          * Copy btree block entries from the left block over to the
2390          * new block, the right. Update the right block and log the
2391          * changes.
2392          */
2393         if (level > 0) {
2394                 /* It's a non-leaf.  Move keys and pointers. */
2395                 union xfs_btree_key     *lkp;   /* left btree key */
2396                 union xfs_btree_ptr     *lpp;   /* left address pointer */
2397                 union xfs_btree_key     *rkp;   /* right btree key */
2398                 union xfs_btree_ptr     *rpp;   /* right address pointer */
2399 
2400                 lkp = xfs_btree_key_addr(cur, src_index, left);
2401                 lpp = xfs_btree_ptr_addr(cur, src_index, left);
2402                 rkp = xfs_btree_key_addr(cur, 1, right);
2403                 rpp = xfs_btree_ptr_addr(cur, 1, right);
2404 
2405 #ifdef DEBUG
2406                 for (i = src_index; i < rrecs; i++) {
2407                         error = xfs_btree_check_ptr(cur, lpp, i, level);
2408                         if (error)
2409                                 goto error0;
2410                 }
2411 #endif
2412 
2413                 xfs_btree_copy_keys(cur, rkp, lkp, rrecs);
2414                 xfs_btree_copy_ptrs(cur, rpp, lpp, rrecs);
2415 
2416                 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2417                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2418 
2419                 /* Grab the keys to the entries moved to the right block */
2420                 xfs_btree_copy_keys(cur, key, rkp, 1);
2421         } else {
2422                 /* It's a leaf.  Move records.  */
2423                 union xfs_btree_rec     *lrp;   /* left record pointer */
2424                 union xfs_btree_rec     *rrp;   /* right record pointer */
2425 
2426                 lrp = xfs_btree_rec_addr(cur, src_index, left);
2427                 rrp = xfs_btree_rec_addr(cur, 1, right);
2428 
2429                 xfs_btree_copy_recs(cur, rrp, lrp, rrecs);
2430                 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2431 
2432                 cur->bc_ops->init_key_from_rec(key,
2433                         xfs_btree_rec_addr(cur, 1, right));
2434         }
2435 
2436 
2437         /*
2438          * Find the left block number by looking in the buffer.
2439          * Adjust numrecs, sibling pointers.
2440          */
2441         xfs_btree_get_sibling(cur, left, &rrptr, XFS_BB_RIGHTSIB);
2442         xfs_btree_set_sibling(cur, right, &rrptr, XFS_BB_RIGHTSIB);
2443         xfs_btree_set_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2444         xfs_btree_set_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2445 
2446         lrecs -= rrecs;
2447         xfs_btree_set_numrecs(left, lrecs);
2448         xfs_btree_set_numrecs(right, xfs_btree_get_numrecs(right) + rrecs);
2449 
2450         xfs_btree_log_block(cur, rbp, XFS_BB_ALL_BITS);
2451         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
2452 
2453         /*
2454          * If there's a block to the new block's right, make that block
2455          * point back to right instead of to left.
2456          */
2457         if (!xfs_btree_ptr_is_null(cur, &rrptr)) {
2458                 error = xfs_btree_read_buf_block(cur, &rrptr, level,
2459                                                         0, &rrblock, &rrbp);
2460                 if (error)
2461                         goto error0;
2462                 xfs_btree_set_sibling(cur, rrblock, &rptr, XFS_BB_LEFTSIB);
2463                 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
2464         }
2465         /*
2466          * If the cursor is really in the right block, move it there.
2467          * If it's just pointing past the last entry in left, then we'll
2468          * insert there, so don't change anything in that case.
2469          */
2470         if (cur->bc_ptrs[level] > lrecs + 1) {
2471                 xfs_btree_setbuf(cur, level, rbp);
2472                 cur->bc_ptrs[level] -= lrecs;
2473         }
2474         /*
2475          * If there are more levels, we'll need another cursor which refers
2476          * the right block, no matter where this cursor was.
2477          */
2478         if (level + 1 < cur->bc_nlevels) {
2479                 error = xfs_btree_dup_cursor(cur, curp);
2480                 if (error)
2481                         goto error0;
2482                 (*curp)->bc_ptrs[level + 1]++;
2483         }
2484         *ptrp = rptr;
2485         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2486         *stat = 1;
2487         return 0;
2488 out0:
2489         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2490         *stat = 0;
2491         return 0;
2492 
2493 error0:
2494         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2495         return error;
2496 }
2497 
2498 /*
2499  * Copy the old inode root contents into a real block and make the
2500  * broot point to it.
2501  */
2502 int                                             /* error */
2503 xfs_btree_new_iroot(
2504         struct xfs_btree_cur    *cur,           /* btree cursor */
2505         int                     *logflags,      /* logging flags for inode */
2506         int                     *stat)          /* return status - 0 fail */
2507 {
2508         struct xfs_buf          *cbp;           /* buffer for cblock */
2509         struct xfs_btree_block  *block;         /* btree block */
2510         struct xfs_btree_block  *cblock;        /* child btree block */
2511         union xfs_btree_key     *ckp;           /* child key pointer */
2512         union xfs_btree_ptr     *cpp;           /* child ptr pointer */
2513         union xfs_btree_key     *kp;            /* pointer to btree key */
2514         union xfs_btree_ptr     *pp;            /* pointer to block addr */
2515         union xfs_btree_ptr     nptr;           /* new block addr */
2516         int                     level;          /* btree level */
2517         int                     error;          /* error return code */
2518 #ifdef DEBUG
2519         int                     i;              /* loop counter */
2520 #endif
2521 
2522         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2523         XFS_BTREE_STATS_INC(cur, newroot);
2524 
2525         ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
2526 
2527         level = cur->bc_nlevels - 1;
2528 
2529         block = xfs_btree_get_iroot(cur);
2530         pp = xfs_btree_ptr_addr(cur, 1, block);
2531 
2532         /* Allocate the new block. If we can't do it, we're toast. Give up. */
2533         error = cur->bc_ops->alloc_block(cur, pp, &nptr, 1, stat);
2534         if (error)
2535                 goto error0;
2536         if (*stat == 0) {
2537                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2538                 return 0;
2539         }
2540         XFS_BTREE_STATS_INC(cur, alloc);
2541 
2542         /* Copy the root into a real block. */
2543         error = xfs_btree_get_buf_block(cur, &nptr, 0, &cblock, &cbp);
2544         if (error)
2545                 goto error0;
2546 
2547         /*
2548          * we can't just memcpy() the root in for CRC enabled btree blocks.
2549          * In that case have to also ensure the blkno remains correct
2550          */
2551         memcpy(cblock, block, xfs_btree_block_len(cur));
2552         if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
2553                 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
2554                         cblock->bb_u.l.bb_blkno = cpu_to_be64(cbp->b_bn);
2555                 else
2556                         cblock->bb_u.s.bb_blkno = cpu_to_be64(cbp->b_bn);
2557         }
2558 
2559         be16_add_cpu(&block->bb_level, 1);
2560         xfs_btree_set_numrecs(block, 1);
2561         cur->bc_nlevels++;
2562         cur->bc_ptrs[level + 1] = 1;
2563 
2564         kp = xfs_btree_key_addr(cur, 1, block);
2565         ckp = xfs_btree_key_addr(cur, 1, cblock);
2566         xfs_btree_copy_keys(cur, ckp, kp, xfs_btree_get_numrecs(cblock));
2567 
2568         cpp = xfs_btree_ptr_addr(cur, 1, cblock);
2569 #ifdef DEBUG
2570         for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
2571                 error = xfs_btree_check_ptr(cur, pp, i, level);
2572                 if (error)
2573                         goto error0;
2574         }
2575 #endif
2576         xfs_btree_copy_ptrs(cur, cpp, pp, xfs_btree_get_numrecs(cblock));
2577 
2578 #ifdef DEBUG
2579         error = xfs_btree_check_ptr(cur, &nptr, 0, level);
2580         if (error)
2581                 goto error0;
2582 #endif
2583         xfs_btree_copy_ptrs(cur, pp, &nptr, 1);
2584 
2585         xfs_iroot_realloc(cur->bc_private.b.ip,
2586                           1 - xfs_btree_get_numrecs(cblock),
2587                           cur->bc_private.b.whichfork);
2588 
2589         xfs_btree_setbuf(cur, level, cbp);
2590 
2591         /*
2592          * Do all this logging at the end so that
2593          * the root is at the right level.
2594          */
2595         xfs_btree_log_block(cur, cbp, XFS_BB_ALL_BITS);
2596         xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
2597         xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
2598 
2599         *logflags |=
2600                 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_private.b.whichfork);
2601         *stat = 1;
2602         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2603         return 0;
2604 error0:
2605         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2606         return error;
2607 }
2608 
2609 /*
2610  * Allocate a new root block, fill it in.
2611  */
2612 STATIC int                              /* error */
2613 xfs_btree_new_root(
2614         struct xfs_btree_cur    *cur,   /* btree cursor */
2615         int                     *stat)  /* success/failure */
2616 {
2617         struct xfs_btree_block  *block; /* one half of the old root block */
2618         struct xfs_buf          *bp;    /* buffer containing block */
2619         int                     error;  /* error return value */
2620         struct xfs_buf          *lbp;   /* left buffer pointer */
2621         struct xfs_btree_block  *left;  /* left btree block */
2622         struct xfs_buf          *nbp;   /* new (root) buffer */
2623         struct xfs_btree_block  *new;   /* new (root) btree block */
2624         int                     nptr;   /* new value for key index, 1 or 2 */
2625         struct xfs_buf          *rbp;   /* right buffer pointer */
2626         struct xfs_btree_block  *right; /* right btree block */
2627         union xfs_btree_ptr     rptr;
2628         union xfs_btree_ptr     lptr;
2629 
2630         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2631         XFS_BTREE_STATS_INC(cur, newroot);
2632 
2633         /* initialise our start point from the cursor */
2634         cur->bc_ops->init_ptr_from_cur(cur, &rptr);
2635 
2636         /* Allocate the new block. If we can't do it, we're toast. Give up. */
2637         error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, 1, stat);
2638         if (error)
2639                 goto error0;
2640         if (*stat == 0)
2641                 goto out0;
2642         XFS_BTREE_STATS_INC(cur, alloc);
2643 
2644         /* Set up the new block. */
2645         error = xfs_btree_get_buf_block(cur, &lptr, 0, &new, &nbp);
2646         if (error)
2647                 goto error0;
2648 
2649         /* Set the root in the holding structure  increasing the level by 1. */
2650         cur->bc_ops->set_root(cur, &lptr, 1);
2651 
2652         /*
2653          * At the previous root level there are now two blocks: the old root,
2654          * and the new block generated when it was split.  We don't know which
2655          * one the cursor is pointing at, so we set up variables "left" and
2656          * "right" for each case.
2657          */
2658         block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp);
2659 
2660 #ifdef DEBUG
2661         error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp);
2662         if (error)
2663                 goto error0;
2664 #endif
2665 
2666         xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
2667         if (!xfs_btree_ptr_is_null(cur, &rptr)) {
2668                 /* Our block is left, pick up the right block. */
2669                 lbp = bp;
2670                 xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2671                 left = block;
2672                 error = xfs_btree_read_buf_block(cur, &rptr,
2673                                         cur->bc_nlevels - 1, 0, &right, &rbp);
2674                 if (error)
2675                         goto error0;
2676                 bp = rbp;
2677                 nptr = 1;
2678         } else {
2679                 /* Our block is right, pick up the left block. */
2680                 rbp = bp;
2681                 xfs_btree_buf_to_ptr(cur, rbp, &rptr);
2682                 right = block;
2683                 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2684                 error = xfs_btree_read_buf_block(cur, &lptr,
2685                                         cur->bc_nlevels - 1, 0, &left, &lbp);
2686                 if (error)
2687                         goto error0;
2688                 bp = lbp;
2689                 nptr = 2;
2690         }
2691         /* Fill in the new block's btree header and log it. */
2692         xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2);
2693         xfs_btree_log_block(cur, nbp, XFS_BB_ALL_BITS);
2694         ASSERT(!xfs_btree_ptr_is_null(cur, &lptr) &&
2695                         !xfs_btree_ptr_is_null(cur, &rptr));
2696 
2697         /* Fill in the key data in the new root. */
2698         if (xfs_btree_get_level(left) > 0) {
2699                 xfs_btree_copy_keys(cur,
2700                                 xfs_btree_key_addr(cur, 1, new),
2701                                 xfs_btree_key_addr(cur, 1, left), 1);
2702                 xfs_btree_copy_keys(cur,
2703                                 xfs_btree_key_addr(cur, 2, new),
2704                                 xfs_btree_key_addr(cur, 1, right), 1);
2705         } else {
2706                 cur->bc_ops->init_key_from_rec(
2707                                 xfs_btree_key_addr(cur, 1, new),
2708                                 xfs_btree_rec_addr(cur, 1, left));
2709                 cur->bc_ops->init_key_from_rec(
2710                                 xfs_btree_key_addr(cur, 2, new),
2711                                 xfs_btree_rec_addr(cur, 1, right));
2712         }
2713         xfs_btree_log_keys(cur, nbp, 1, 2);
2714 
2715         /* Fill in the pointer data in the new root. */
2716         xfs_btree_copy_ptrs(cur,
2717                 xfs_btree_ptr_addr(cur, 1, new), &lptr, 1);
2718         xfs_btree_copy_ptrs(cur,
2719                 xfs_btree_ptr_addr(cur, 2, new), &rptr, 1);
2720         xfs_btree_log_ptrs(cur, nbp, 1, 2);
2721 
2722         /* Fix up the cursor. */
2723         xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
2724         cur->bc_ptrs[cur->bc_nlevels] = nptr;
2725         cur->bc_nlevels++;
2726         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2727         *stat = 1;
2728         return 0;
2729 error0:
2730         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2731         return error;
2732 out0:
2733         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2734         *stat = 0;
2735         return 0;
2736 }
2737 
2738 STATIC int
2739 xfs_btree_make_block_unfull(
2740         struct xfs_btree_cur    *cur,   /* btree cursor */
2741         int                     level,  /* btree level */
2742         int                     numrecs,/* # of recs in block */
2743         int                     *oindex,/* old tree index */
2744         int                     *index, /* new tree index */
2745         union xfs_btree_ptr     *nptr,  /* new btree ptr */
2746         struct xfs_btree_cur    **ncur, /* new btree cursor */
2747         union xfs_btree_rec     *nrec,  /* new record */
2748         int                     *stat)
2749 {
2750         union xfs_btree_key     key;    /* new btree key value */
2751         int                     error = 0;
2752 
2753         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2754             level == cur->bc_nlevels - 1) {
2755                 struct xfs_inode *ip = cur->bc_private.b.ip;
2756 
2757                 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) {
2758                         /* A root block that can be made bigger. */
2759 
2760                         xfs_iroot_realloc(ip, 1, cur->bc_private.b.whichfork);
2761                 } else {
2762                         /* A root block that needs replacing */
2763                         int     logflags = 0;
2764 
2765                         error = xfs_btree_new_iroot(cur, &logflags, stat);
2766                         if (error || *stat == 0)
2767                                 return error;
2768 
2769                         xfs_trans_log_inode(cur->bc_tp, ip, logflags);
2770                 }
2771 
2772                 return 0;
2773         }
2774 
2775         /* First, try shifting an entry to the right neighbor. */
2776         error = xfs_btree_rshift(cur, level, stat);
2777         if (error || *stat)
2778                 return error;
2779 
2780         /* Next, try shifting an entry to the left neighbor. */
2781         error = xfs_btree_lshift(cur, level, stat);
2782         if (error)
2783                 return error;
2784 
2785         if (*stat) {
2786                 *oindex = *index = cur->bc_ptrs[level];
2787                 return 0;
2788         }
2789 
2790         /*
2791          * Next, try splitting the current block in half.
2792          *
2793          * If this works we have to re-set our variables because we
2794          * could be in a different block now.
2795          */
2796         error = xfs_btree_split(cur, level, nptr, &key, ncur, stat);
2797         if (error || *stat == 0)
2798                 return error;
2799 
2800 
2801         *index = cur->bc_ptrs[level];
2802         cur->bc_ops->init_rec_from_key(&key, nrec);
2803         return 0;
2804 }
2805 
2806 /*
2807  * Insert one record/level.  Return information to the caller
2808  * allowing the next level up to proceed if necessary.
2809  */
2810 STATIC int
2811 xfs_btree_insrec(
2812         struct xfs_btree_cur    *cur,   /* btree cursor */
2813         int                     level,  /* level to insert record at */
2814         union xfs_btree_ptr     *ptrp,  /* i/o: block number inserted */
2815         union xfs_btree_rec     *recp,  /* i/o: record data inserted */
2816         struct xfs_btree_cur    **curp, /* output: new cursor replacing cur */
2817         int                     *stat)  /* success/failure */
2818 {
2819         struct xfs_btree_block  *block; /* btree block */
2820         struct xfs_buf          *bp;    /* buffer for block */
2821         union xfs_btree_key     key;    /* btree key */
2822         union xfs_btree_ptr     nptr;   /* new block ptr */
2823         struct xfs_btree_cur    *ncur;  /* new btree cursor */
2824         union xfs_btree_rec     nrec;   /* new record count */
2825         int                     optr;   /* old key/record index */
2826         int                     ptr;    /* key/record index */
2827         int                     numrecs;/* number of records */
2828         int                     error;  /* error return value */
2829 #ifdef DEBUG
2830         int                     i;
2831 #endif
2832 
2833         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2834         XFS_BTREE_TRACE_ARGIPR(cur, level, *ptrp, recp);
2835 
2836         ncur = NULL;
2837 
2838         /*
2839          * If we have an external root pointer, and we've made it to the
2840          * root level, allocate a new root block and we're done.
2841          */
2842         if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2843             (level >= cur->bc_nlevels)) {
2844                 error = xfs_btree_new_root(cur, stat);
2845                 xfs_btree_set_ptr_null(cur, ptrp);
2846 
2847                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2848                 return error;
2849         }
2850 
2851         /* If we're off the left edge, return failure. */
2852         ptr = cur->bc_ptrs[level];
2853         if (ptr == 0) {
2854                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2855                 *stat = 0;
2856                 return 0;
2857         }
2858 
2859         /* Make a key out of the record data to be inserted, and save it. */
2860         cur->bc_ops->init_key_from_rec(&key, recp);
2861 
2862         optr = ptr;
2863 
2864         XFS_BTREE_STATS_INC(cur, insrec);
2865 
2866         /* Get pointers to the btree buffer and block. */
2867         block = xfs_btree_get_block(cur, level, &bp);
2868         numrecs = xfs_btree_get_numrecs(block);
2869 
2870 #ifdef DEBUG
2871         error = xfs_btree_check_block(cur, block, level, bp);
2872         if (error)
2873                 goto error0;
2874 
2875         /* Check that the new entry is being inserted in the right place. */
2876         if (ptr <= numrecs) {
2877                 if (level == 0) {
2878                         ASSERT(cur->bc_ops->recs_inorder(cur, recp,
2879                                 xfs_btree_rec_addr(cur, ptr, block)));
2880                 } else {
2881                         ASSERT(cur->bc_ops->keys_inorder(cur, &key,
2882                                 xfs_btree_key_addr(cur, ptr, block)));
2883                 }
2884         }
2885 #endif
2886 
2887         /*
2888          * If the block is full, we can't insert the new entry until we
2889          * make the block un-full.
2890          */
2891         xfs_btree_set_ptr_null(cur, &nptr);
2892         if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) {
2893                 error = xfs_btree_make_block_unfull(cur, level, numrecs,
2894                                         &optr, &ptr, &nptr, &ncur, &nrec, stat);
2895                 if (error || *stat == 0)
2896                         goto error0;
2897         }
2898 
2899         /*
2900          * The current block may have changed if the block was
2901          * previously full and we have just made space in it.
2902          */
2903         block = xfs_btree_get_block(cur, level, &bp);
2904         numrecs = xfs_btree_get_numrecs(block);
2905 
2906 #ifdef DEBUG
2907         error = xfs_btree_check_block(cur, block, level, bp);
2908         if (error)
2909                 return error;
2910 #endif
2911 
2912         /*
2913          * At this point we know there's room for our new entry in the block
2914          * we're pointing at.
2915          */
2916         XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1);
2917 
2918         if (level > 0) {
2919                 /* It's a nonleaf. make a hole in the keys and ptrs */
2920                 union xfs_btree_key     *kp;
2921                 union xfs_btree_ptr     *pp;
2922 
2923                 kp = xfs_btree_key_addr(cur, ptr, block);
2924                 pp = xfs_btree_ptr_addr(cur, ptr, block);
2925 
2926 #ifdef DEBUG
2927                 for (i = numrecs - ptr; i >= 0; i--) {
2928                         error = xfs_btree_check_ptr(cur, pp, i, level);
2929                         if (error)
2930                                 return error;
2931                 }
2932 #endif
2933 
2934                 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1);
2935                 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1);
2936 
2937 #ifdef DEBUG
2938                 error = xfs_btree_check_ptr(cur, ptrp, 0, level);
2939                 if (error)
2940                         goto error0;
2941 #endif
2942 
2943                 /* Now put the new data in, bump numrecs and log it. */
2944                 xfs_btree_copy_keys(cur, kp, &key, 1);
2945                 xfs_btree_copy_ptrs(cur, pp, ptrp, 1);
2946                 numrecs++;
2947                 xfs_btree_set_numrecs(block, numrecs);
2948                 xfs_btree_log_ptrs(cur, bp, ptr, numrecs);
2949                 xfs_btree_log_keys(cur, bp, ptr, numrecs);
2950 #ifdef DEBUG
2951                 if (ptr < numrecs) {
2952                         ASSERT(cur->bc_ops->keys_inorder(cur, kp,
2953                                 xfs_btree_key_addr(cur, ptr + 1, block)));
2954                 }
2955 #endif
2956         } else {
2957                 /* It's a leaf. make a hole in the records */
2958                 union xfs_btree_rec             *rp;
2959 
2960                 rp = xfs_btree_rec_addr(cur, ptr, block);
2961 
2962                 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1);
2963 
2964                 /* Now put the new data in, bump numrecs and log it. */
2965                 xfs_btree_copy_recs(cur, rp, recp, 1);
2966                 xfs_btree_set_numrecs(block, ++numrecs);
2967                 xfs_btree_log_recs(cur, bp, ptr, numrecs);
2968 #ifdef DEBUG
2969                 if (ptr < numrecs) {
2970                         ASSERT(cur->bc_ops->recs_inorder(cur, rp,
2971                                 xfs_btree_rec_addr(cur, ptr + 1, block)));
2972                 }
2973 #endif
2974         }
2975 
2976         /* Log the new number of records in the btree header. */
2977         xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
2978 
2979         /* If we inserted at the start of a block, update the parents' keys. */
2980         if (optr == 1) {
2981                 error = xfs_btree_updkey(cur, &key, level + 1);
2982                 if (error)
2983                         goto error0;
2984         }
2985 
2986         /*
2987          * If we are tracking the last record in the tree and
2988          * we are at the far right edge of the tree, update it.
2989          */
2990         if (xfs_btree_is_lastrec(cur, block, level)) {
2991                 cur->bc_ops->update_lastrec(cur, block, recp,
2992                                             ptr, LASTREC_INSREC);
2993         }
2994 
2995         /*
2996          * Return the new block number, if any.
2997          * If there is one, give back a record value and a cursor too.
2998          */
2999         *ptrp = nptr;
3000         if (!xfs_btree_ptr_is_null(cur, &nptr)) {
3001                 *recp = nrec;
3002                 *curp = ncur;
3003         }
3004 
3005         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3006         *stat = 1;
3007         return 0;
3008 
3009 error0:
3010         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3011         return error;
3012 }
3013 
3014 /*
3015  * Insert the record at the point referenced by cur.
3016  *
3017  * A multi-level split of the tree on insert will invalidate the original
3018  * cursor.  All callers of this function should assume that the cursor is
3019  * no longer valid and revalidate it.
3020  */
3021 int
3022 xfs_btree_insert(
3023         struct xfs_btree_cur    *cur,
3024         int                     *stat)
3025 {
3026         int                     error;  /* error return value */
3027         int                     i;      /* result value, 0 for failure */
3028         int                     level;  /* current level number in btree */
3029         union xfs_btree_ptr     nptr;   /* new block number (split result) */
3030         struct xfs_btree_cur    *ncur;  /* new cursor (split result) */
3031         struct xfs_btree_cur    *pcur;  /* previous level's cursor */
3032         union xfs_btree_rec     rec;    /* record to insert */
3033 
3034         level = 0;
3035         ncur = NULL;
3036         pcur = cur;
3037 
3038         xfs_btree_set_ptr_null(cur, &nptr);
3039         cur->bc_ops->init_rec_from_cur(cur, &rec);
3040 
3041         /*
3042          * Loop going up the tree, starting at the leaf level.
3043          * Stop when we don't get a split block, that must mean that
3044          * the insert is finished with this level.
3045          */
3046         do {
3047                 /*
3048                  * Insert nrec/nptr into this level of the tree.
3049                  * Note if we fail, nptr will be null.
3050                  */
3051                 error = xfs_btree_insrec(pcur, level, &nptr, &rec, &ncur, &i);
3052                 if (error) {
3053                         if (pcur != cur)
3054                                 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
3055                         goto error0;
3056                 }
3057 
3058                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3059                 level++;
3060 
3061                 /*
3062                  * See if the cursor we just used is trash.
3063                  * Can't trash the caller's cursor, but otherwise we should
3064                  * if ncur is a new cursor or we're about to be done.
3065                  */
3066                 if (pcur != cur &&
3067                     (ncur || xfs_btree_ptr_is_null(cur, &nptr))) {
3068                         /* Save the state from the cursor before we trash it */
3069                         if (cur->bc_ops->update_cursor)
3070                                 cur->bc_ops->update_cursor(pcur, cur);
3071                         cur->bc_nlevels = pcur->bc_nlevels;
3072                         xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
3073                 }
3074                 /* If we got a new cursor, switch to it. */
3075                 if (ncur) {
3076                         pcur = ncur;
3077                         ncur = NULL;
3078                 }
3079         } while (!xfs_btree_ptr_is_null(cur, &nptr));
3080 
3081         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3082         *stat = i;
3083         return 0;
3084 error0:
3085         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3086         return error;
3087 }
3088 
3089 /*
3090  * Try to merge a non-leaf block back into the inode root.
3091  *
3092  * Note: the killroot names comes from the fact that we're effectively
3093  * killing the old root block.  But because we can't just delete the
3094  * inode we have to copy the single block it was pointing to into the
3095  * inode.
3096  */
3097 STATIC int
3098 xfs_btree_kill_iroot(
3099         struct xfs_btree_cur    *cur)
3100 {
3101         int                     whichfork = cur->bc_private.b.whichfork;
3102         struct xfs_inode        *ip = cur->bc_private.b.ip;
3103         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
3104         struct xfs_btree_block  *block;
3105         struct xfs_btree_block  *cblock;
3106         union xfs_btree_key     *kp;
3107         union xfs_btree_key     *ckp;
3108         union xfs_btree_ptr     *pp;
3109         union xfs_btree_ptr     *cpp;
3110         struct xfs_buf          *cbp;
3111         int                     level;
3112         int                     index;
3113         int                     numrecs;
3114 #ifdef DEBUG
3115         union xfs_btree_ptr     ptr;
3116         int                     i;
3117 #endif
3118 
3119         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3120 
3121         ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
3122         ASSERT(cur->bc_nlevels > 1);
3123 
3124         /*
3125          * Don't deal with the root block needs to be a leaf case.
3126          * We're just going to turn the thing back into extents anyway.
3127          */
3128         level = cur->bc_nlevels - 1;
3129         if (level == 1)
3130                 goto out0;
3131 
3132         /*
3133          * Give up if the root has multiple children.
3134          */
3135         block = xfs_btree_get_iroot(cur);
3136         if (xfs_btree_get_numrecs(block) != 1)
3137                 goto out0;
3138 
3139         cblock = xfs_btree_get_block(cur, level - 1, &cbp);
3140         numrecs = xfs_btree_get_numrecs(cblock);
3141 
3142         /*
3143          * Only do this if the next level will fit.
3144          * Then the data must be copied up to the inode,
3145          * instead of freeing the root you free the next level.
3146          */
3147         if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level))
3148                 goto out0;
3149 
3150         XFS_BTREE_STATS_INC(cur, killroot);
3151 
3152 #ifdef DEBUG
3153         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
3154         ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3155         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
3156         ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3157 #endif
3158 
3159         index = numrecs - cur->bc_ops->get_maxrecs(cur, level);
3160         if (index) {
3161                 xfs_iroot_realloc(cur->bc_private.b.ip, index,
3162                                   cur->bc_private.b.whichfork);
3163                 block = ifp->if_broot;
3164         }
3165 
3166         be16_add_cpu(&block->bb_numrecs, index);
3167         ASSERT(block->bb_numrecs == cblock->bb_numrecs);
3168 
3169         kp = xfs_btree_key_addr(cur, 1, block);
3170         ckp = xfs_btree_key_addr(cur, 1, cblock);
3171         xfs_btree_copy_keys(cur, kp, ckp, numrecs);
3172 
3173         pp = xfs_btree_ptr_addr(cur, 1, block);
3174         cpp = xfs_btree_ptr_addr(cur, 1, cblock);
3175 #ifdef DEBUG
3176         for (i = 0; i < numrecs; i++) {
3177                 int             error;
3178 
3179                 error = xfs_btree_check_ptr(cur, cpp, i, level - 1);
3180                 if (error) {
3181                         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3182                         return error;
3183                 }
3184         }
3185 #endif
3186         xfs_btree_copy_ptrs(cur, pp, cpp, numrecs);
3187 
3188         cur->bc_ops->free_block(cur, cbp);
3189         XFS_BTREE_STATS_INC(cur, free);
3190 
3191         cur->bc_bufs[level - 1] = NULL;
3192         be16_add_cpu(&block->bb_level, -1);
3193         xfs_trans_log_inode(cur->bc_tp, ip,
3194                 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_private.b.whichfork));
3195         cur->bc_nlevels--;
3196 out0:
3197         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3198         return 0;
3199 }
3200 
3201 /*
3202  * Kill the current root node, and replace it with it's only child node.
3203  */
3204 STATIC int
3205 xfs_btree_kill_root(
3206         struct xfs_btree_cur    *cur,
3207         struct xfs_buf          *bp,
3208         int                     level,
3209         union xfs_btree_ptr     *newroot)
3210 {
3211         int                     error;
3212 
3213         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3214         XFS_BTREE_STATS_INC(cur, killroot);
3215 
3216         /*
3217          * Update the root pointer, decreasing the level by 1 and then
3218          * free the old root.
3219          */
3220         cur->bc_ops->set_root(cur, newroot, -1);
3221 
3222         error = cur->bc_ops->free_block(cur, bp);
3223         if (error) {
3224                 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3225                 return error;
3226         }
3227 
3228         XFS_BTREE_STATS_INC(cur, free);
3229 
3230         cur->bc_bufs[level] = NULL;
3231         cur->bc_ra[level] = 0;
3232         cur->bc_nlevels--;
3233 
3234         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3235         return 0;
3236 }
3237 
3238 STATIC int
3239 xfs_btree_dec_cursor(
3240         struct xfs_btree_cur    *cur,
3241         int                     level,
3242         int                     *stat)
3243 {
3244         int                     error;
3245         int                     i;
3246 
3247         if (level > 0) {
3248                 error = xfs_btree_decrement(cur, level, &i);
3249                 if (error)
3250                         return error;
3251         }
3252 
3253         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3254         *stat = 1;
3255         return 0;
3256 }
3257 
3258 /*
3259  * Single level of the btree record deletion routine.
3260  * Delete record pointed to by cur/level.
3261  * Remove the record from its block then rebalance the tree.
3262  * Return 0 for error, 1 for done, 2 to go on to the next level.
3263  */
3264 STATIC int                                      /* error */
3265 xfs_btree_delrec(
3266         struct xfs_btree_cur    *cur,           /* btree cursor */
3267         int                     level,          /* level removing record from */
3268         int                     *stat)          /* fail/done/go-on */
3269 {
3270         struct xfs_btree_block  *block;         /* btree block */
3271         union xfs_btree_ptr     cptr;           /* current block ptr */
3272         struct xfs_buf          *bp;            /* buffer for block */
3273         int                     error;          /* error return value */
3274         int                     i;              /* loop counter */
3275         union xfs_btree_key     key;            /* storage for keyp */
3276         union xfs_btree_key     *keyp = &key;   /* passed to the next level */
3277         union xfs_btree_ptr     lptr;           /* left sibling block ptr */
3278         struct xfs_buf          *lbp;           /* left buffer pointer */
3279         struct xfs_btree_block  *left;          /* left btree block */
3280         int                     lrecs = 0;      /* left record count */
3281         int                     ptr;            /* key/record index */
3282         union xfs_btree_ptr     rptr;           /* right sibling block ptr */
3283         struct xfs_buf          *rbp;           /* right buffer pointer */
3284         struct xfs_btree_block  *right;         /* right btree block */
3285         struct xfs_btree_block  *rrblock;       /* right-right btree block */
3286         struct xfs_buf          *rrbp;          /* right-right buffer pointer */
3287         int                     rrecs = 0;      /* right record count */
3288         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
3289         int                     numrecs;        /* temporary numrec count */
3290 
3291         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3292         XFS_BTREE_TRACE_ARGI(cur, level);
3293 
3294         tcur = NULL;
3295 
3296         /* Get the index of the entry being deleted, check for nothing there. */
3297         ptr = cur->bc_ptrs[level];
3298         if (ptr == 0) {
3299                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3300                 *stat = 0;
3301                 return 0;
3302         }
3303 
3304         /* Get the buffer & block containing the record or key/ptr. */
3305         block = xfs_btree_get_block(cur, level, &bp);
3306         numrecs = xfs_btree_get_numrecs(block);
3307 
3308 #ifdef DEBUG
3309         error = xfs_btree_check_block(cur, block, level, bp);
3310         if (error)
3311                 goto error0;
3312 #endif
3313 
3314         /* Fail if we're off the end of the block. */
3315         if (ptr > numrecs) {
3316                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3317                 *stat = 0;
3318                 return 0;
3319         }
3320 
3321         XFS_BTREE_STATS_INC(cur, delrec);
3322         XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr);
3323 
3324         /* Excise the entries being deleted. */
3325         if (level > 0) {
3326                 /* It's a nonleaf. operate on keys and ptrs */
3327                 union xfs_btree_key     *lkp;
3328                 union xfs_btree_ptr     *lpp;
3329 
3330                 lkp = xfs_btree_key_addr(cur, ptr + 1, block);
3331                 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block);
3332 
3333 #ifdef DEBUG
3334                 for (i = 0; i < numrecs - ptr; i++) {
3335                         error = xfs_btree_check_ptr(cur, lpp, i, level);
3336                         if (error)
3337                                 goto error0;
3338                 }
3339 #endif
3340 
3341                 if (ptr < numrecs) {
3342                         xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr);
3343                         xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr);
3344                         xfs_btree_log_keys(cur, bp, ptr, numrecs - 1);
3345                         xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1);
3346                 }
3347 
3348                 /*
3349                  * If it's the first record in the block, we'll need to pass a
3350                  * key up to the next level (updkey).
3351                  */
3352                 if (ptr == 1)
3353                         keyp = xfs_btree_key_addr(cur, 1, block);
3354         } else {
3355                 /* It's a leaf. operate on records */
3356                 if (ptr < numrecs) {
3357                         xfs_btree_shift_recs(cur,
3358                                 xfs_btree_rec_addr(cur, ptr + 1, block),
3359                                 -1, numrecs - ptr);
3360                         xfs_btree_log_recs(cur, bp, ptr, numrecs - 1);
3361                 }
3362 
3363                 /*
3364                  * If it's the first record in the block, we'll need a key
3365                  * structure to pass up to the next level (updkey).
3366                  */
3367                 if (ptr == 1) {
3368                         cur->bc_ops->init_key_from_rec(&key,
3369                                         xfs_btree_rec_addr(cur, 1, block));
3370                         keyp = &key;
3371                 }
3372         }
3373 
3374         /*
3375          * Decrement and log the number of entries in the block.
3376          */
3377         xfs_btree_set_numrecs(block, --numrecs);
3378         xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3379 
3380         /*
3381          * If we are tracking the last record in the tree and
3382          * we are at the far right edge of the tree, update it.
3383          */
3384         if (xfs_btree_is_lastrec(cur, block, level)) {
3385                 cur->bc_ops->update_lastrec(cur, block, NULL,
3386                                             ptr, LASTREC_DELREC);
3387         }
3388 
3389         /*
3390          * We're at the root level.  First, shrink the root block in-memory.
3391          * Try to get rid of the next level down.  If we can't then there's
3392          * nothing left to do.
3393          */
3394         if (level == cur->bc_nlevels - 1) {
3395                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3396                         xfs_iroot_realloc(cur->bc_private.b.ip, -1,
3397                                           cur->bc_private.b.whichfork);
3398 
3399                         error = xfs_btree_kill_iroot(cur);
3400                         if (error)
3401                                 goto error0;
3402 
3403                         error = xfs_btree_dec_cursor(cur, level, stat);
3404                         if (error)
3405                                 goto error0;
3406                         *stat = 1;
3407                         return 0;
3408                 }
3409 
3410                 /*
3411                  * If this is the root level, and there's only one entry left,
3412                  * and it's NOT the leaf level, then we can get rid of this
3413                  * level.
3414                  */
3415                 if (numrecs == 1 && level > 0) {
3416                         union xfs_btree_ptr     *pp;
3417                         /*
3418                          * pp is still set to the first pointer in the block.
3419                          * Make it the new root of the btree.
3420                          */
3421                         pp = xfs_btree_ptr_addr(cur, 1, block);
3422                         error = xfs_btree_kill_root(cur, bp, level, pp);
3423                         if (error)
3424                                 goto error0;
3425                 } else if (level > 0) {
3426                         error = xfs_btree_dec_cursor(cur, level, stat);
3427                         if (error)
3428                                 goto error0;
3429                 }
3430                 *stat = 1;
3431                 return 0;
3432         }
3433 
3434         /*
3435          * If we deleted the leftmost entry in the block, update the
3436          * key values above us in the tree.
3437          */
3438         if (ptr == 1) {
3439                 error = xfs_btree_updkey(cur, keyp, level + 1);
3440                 if (error)
3441                         goto error0;
3442         }
3443 
3444         /*
3445          * If the number of records remaining in the block is at least
3446          * the minimum, we're done.
3447          */
3448         if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {
3449                 error = xfs_btree_dec_cursor(cur, level, stat);
3450                 if (error)
3451                         goto error0;
3452                 return 0;
3453         }
3454 
3455         /*
3456          * Otherwise, we have to move some records around to keep the
3457          * tree balanced.  Look at the left and right sibling blocks to
3458          * see if we can re-balance by moving only one record.
3459          */
3460         xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3461         xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB);
3462 
3463         if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3464                 /*
3465                  * One child of root, need to get a chance to copy its contents
3466                  * into the root and delete it. Can't go up to next level,
3467                  * there's nothing to delete there.
3468                  */
3469                 if (xfs_btree_ptr_is_null(cur, &rptr) &&
3470                     xfs_btree_ptr_is_null(cur, &lptr) &&
3471                     level == cur->bc_nlevels - 2) {
3472                         error = xfs_btree_kill_iroot(cur);
3473                         if (!error)
3474                                 error = xfs_btree_dec_cursor(cur, level, stat);
3475                         if (error)
3476                                 goto error0;
3477                         return 0;
3478                 }
3479         }
3480 
3481         ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) ||
3482                !xfs_btree_ptr_is_null(cur, &lptr));
3483 
3484         /*
3485          * Duplicate the cursor so our btree manipulations here won't
3486          * disrupt the next level up.
3487          */
3488         error = xfs_btree_dup_cursor(cur, &tcur);
3489         if (error)
3490                 goto error0;
3491 
3492         /*
3493          * If there's a right sibling, see if it's ok to shift an entry
3494          * out of it.
3495          */
3496         if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3497                 /*
3498                  * Move the temp cursor to the last entry in the next block.
3499                  * Actually any entry but the first would suffice.
3500                  */
3501                 i = xfs_btree_lastrec(tcur, level);
3502                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3503 
3504                 error = xfs_btree_increment(tcur, level, &i);
3505                 if (error)
3506                         goto error0;
3507                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3508 
3509                 i = xfs_btree_lastrec(tcur, level);
3510                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3511 
3512                 /* Grab a pointer to the block. */
3513                 right = xfs_btree_get_block(tcur, level, &rbp);
3514 #ifdef DEBUG
3515                 error = xfs_btree_check_block(tcur, right, level, rbp);
3516                 if (error)
3517                         goto error0;
3518 #endif
3519                 /* Grab the current block number, for future use. */
3520                 xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB);
3521 
3522                 /*
3523                  * If right block is full enough so that removing one entry
3524                  * won't make it too empty, and left-shifting an entry out
3525                  * of right to us works, we're done.
3526                  */
3527                 if (xfs_btree_get_numrecs(right) - 1 >=
3528                     cur->bc_ops->get_minrecs(tcur, level)) {
3529                         error = xfs_btree_lshift(tcur, level, &i);
3530                         if (error)
3531                                 goto error0;
3532                         if (i) {
3533                                 ASSERT(xfs_btree_get_numrecs(block) >=
3534                                        cur->bc_ops->get_minrecs(tcur, level));
3535 
3536                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3537                                 tcur = NULL;
3538 
3539                                 error = xfs_btree_dec_cursor(cur, level, stat);
3540                                 if (error)
3541                                         goto error0;
3542                                 return 0;
3543                         }
3544                 }
3545 
3546                 /*
3547                  * Otherwise, grab the number of records in right for
3548                  * future reference, and fix up the temp cursor to point
3549                  * to our block again (last record).
3550                  */
3551                 rrecs = xfs_btree_get_numrecs(right);
3552                 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3553                         i = xfs_btree_firstrec(tcur, level);
3554                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3555 
3556                         error = xfs_btree_decrement(tcur, level, &i);
3557                         if (error)
3558                                 goto error0;
3559                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3560                 }
3561         }
3562 
3563         /*
3564          * If there's a left sibling, see if it's ok to shift an entry
3565          * out of it.
3566          */
3567         if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3568                 /*
3569                  * Move the temp cursor to the first entry in the
3570                  * previous block.
3571                  */
3572                 i = xfs_btree_firstrec(tcur, level);
3573                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3574 
3575                 error = xfs_btree_decrement(tcur, level, &i);
3576                 if (error)
3577                         goto error0;
3578                 i = xfs_btree_firstrec(tcur, level);
3579                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3580 
3581                 /* Grab a pointer to the block. */
3582                 left = xfs_btree_get_block(tcur, level, &lbp);
3583 #ifdef DEBUG
3584                 error = xfs_btree_check_block(cur, left, level, lbp);
3585                 if (error)
3586                         goto error0;
3587 #endif
3588                 /* Grab the current block number, for future use. */
3589                 xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB);
3590 
3591                 /*
3592                  * If left block is full enough so that removing one entry
3593                  * won't make it too empty, and right-shifting an entry out
3594                  * of left to us works, we're done.
3595                  */
3596                 if (xfs_btree_get_numrecs(left) - 1 >=
3597                     cur->bc_ops->get_minrecs(tcur, level)) {
3598                         error = xfs_btree_rshift(tcur, level, &i);
3599                         if (error)
3600                                 goto error0;
3601                         if (i) {
3602                                 ASSERT(xfs_btree_get_numrecs(block) >=
3603                                        cur->bc_ops->get_minrecs(tcur, level));
3604                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3605                                 tcur = NULL;
3606                                 if (level == 0)
3607                                         cur->bc_ptrs[0]++;
3608                                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3609                                 *stat = 1;
3610                                 return 0;
3611                         }
3612                 }
3613 
3614                 /*
3615                  * Otherwise, grab the number of records in right for
3616                  * future reference.
3617                  */
3618                 lrecs = xfs_btree_get_numrecs(left);
3619         }
3620 
3621         /* Delete the temp cursor, we're done with it. */
3622         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3623         tcur = NULL;
3624 
3625         /* If here, we need to do a join to keep the tree balanced. */
3626         ASSERT(!xfs_btree_ptr_is_null(cur, &cptr));
3627 
3628         if (!xfs_btree_ptr_is_null(cur, &lptr) &&
3629             lrecs + xfs_btree_get_numrecs(block) <=
3630                         cur->bc_ops->get_maxrecs(cur, level)) {
3631                 /*
3632                  * Set "right" to be the starting block,
3633                  * "left" to be the left neighbor.
3634                  */
3635                 rptr = cptr;
3636                 right = block;
3637                 rbp = bp;
3638                 error = xfs_btree_read_buf_block(cur, &lptr, level,
3639                                                         0, &left, &lbp);
3640                 if (error)
3641                         goto error0;
3642 
3643         /*
3644          * If that won't work, see if we can join with the right neighbor block.
3645          */
3646         } else if (!xfs_btree_ptr_is_null(cur, &rptr) &&
3647                    rrecs + xfs_btree_get_numrecs(block) <=
3648                         cur->bc_ops->get_maxrecs(cur, level)) {
3649                 /*
3650                  * Set "left" to be the starting block,
3651                  * "right" to be the right neighbor.
3652                  */
3653                 lptr = cptr;
3654                 left = block;
3655                 lbp = bp;
3656                 error = xfs_btree_read_buf_block(cur, &rptr, level,
3657                                                         0, &right, &rbp);
3658                 if (error)
3659                         goto error0;
3660 
3661         /*
3662          * Otherwise, we can't fix the imbalance.
3663          * Just return.  This is probably a logic error, but it's not fatal.
3664          */
3665         } else {
3666                 error = xfs_btree_dec_cursor(cur, level, stat);
3667                 if (error)
3668                         goto error0;
3669                 return 0;
3670         }
3671 
3672         rrecs = xfs_btree_get_numrecs(right);
3673         lrecs = xfs_btree_get_numrecs(left);
3674 
3675         /*
3676          * We're now going to join "left" and "right" by moving all the stuff
3677          * in "right" to "left" and deleting "right".
3678          */
3679         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
3680         if (level > 0) {
3681                 /* It's a non-leaf.  Move keys and pointers. */
3682                 union xfs_btree_key     *lkp;   /* left btree key */
3683                 union xfs_btree_ptr     *lpp;   /* left address pointer */
3684                 union xfs_btree_key     *rkp;   /* right btree key */
3685                 union xfs_btree_ptr     *rpp;   /* right address pointer */
3686 
3687                 lkp = xfs_btree_key_addr(cur, lrecs + 1, left);
3688                 lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left);
3689                 rkp = xfs_btree_key_addr(cur, 1, right);
3690                 rpp = xfs_btree_ptr_addr(cur, 1, right);
3691 #ifdef DEBUG
3692                 for (i = 1; i < rrecs; i++) {
3693                         error = xfs_btree_check_ptr(cur, rpp, i, level);
3694                         if (error)
3695                                 goto error0;
3696                 }
3697 #endif
3698                 xfs_btree_copy_keys(cur, lkp, rkp, rrecs);
3699                 xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs);
3700 
3701                 xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
3702                 xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
3703         } else {
3704                 /* It's a leaf.  Move records.  */
3705                 union xfs_btree_rec     *lrp;   /* left record pointer */
3706                 union xfs_btree_rec     *rrp;   /* right record pointer */
3707 
3708                 lrp = xfs_btree_rec_addr(cur, lrecs + 1, left);
3709                 rrp = xfs_btree_rec_addr(cur, 1, right);
3710 
3711                 xfs_btree_copy_recs(cur, lrp, rrp, rrecs);
3712                 xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
3713         }
3714 
3715         XFS_BTREE_STATS_INC(cur, join);
3716 
3717         /*
3718          * Fix up the number of records and right block pointer in the
3719          * surviving block, and log it.
3720          */
3721         xfs_btree_set_numrecs(left, lrecs + rrecs);
3722         xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB),
3723         xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
3724         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
3725 
3726         /* If there is a right sibling, point it to the remaining block. */
3727         xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
3728         if (!xfs_btree_ptr_is_null(cur, &cptr)) {
3729                 error = xfs_btree_read_buf_block(cur, &cptr, level,
3730                                                         0, &rrblock, &rrbp);
3731                 if (error)
3732                         goto error0;
3733                 xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB);
3734                 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
3735         }
3736 
3737         /* Free the deleted block. */
3738         error = cur->bc_ops->free_block(cur, rbp);
3739         if (error)
3740                 goto error0;
3741         XFS_BTREE_STATS_INC(cur, free);
3742 
3743         /*
3744          * If we joined with the left neighbor, set the buffer in the
3745          * cursor to the left block, and fix up the index.
3746          */
3747         if (bp != lbp) {
3748                 cur->bc_bufs[level] = lbp;
3749                 cur->bc_ptrs[level] += lrecs;
3750                 cur->bc_ra[level] = 0;
3751         }
3752         /*
3753          * If we joined with the right neighbor and there's a level above
3754          * us, increment the cursor at that level.
3755          */
3756         else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) ||
3757                    (level + 1 < cur->bc_nlevels)) {
3758                 error = xfs_btree_increment(cur, level + 1, &i);
3759                 if (error)
3760                         goto error0;
3761         }
3762 
3763         /*
3764          * Readjust the ptr at this level if it's not a leaf, since it's
3765          * still pointing at the deletion point, which makes the cursor
3766          * inconsistent.  If this makes the ptr 0, the caller fixes it up.
3767          * We can't use decrement because it would change the next level up.
3768          */
3769         if (level > 0)
3770                 cur->bc_ptrs[level]--;
3771 
3772         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3773         /* Return value means the next level up has something to do. */
3774         *stat = 2;
3775         return 0;
3776 
3777 error0:
3778         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3779         if (tcur)
3780                 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
3781         return error;
3782 }
3783 
3784 /*
3785  * Delete the record pointed to by cur.
3786  * The cursor refers to the place where the record was (could be inserted)
3787  * when the operation returns.
3788  */
3789 int                                     /* error */
3790 xfs_btree_delete(
3791         struct xfs_btree_cur    *cur,
3792         int                     *stat)  /* success/failure */
3793 {
3794         int                     error;  /* error return value */
3795         int                     level;
3796         int                     i;
3797 
3798         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3799 
3800         /*
3801          * Go up the tree, starting at leaf level.
3802          *
3803          * If 2 is returned then a join was done; go to the next level.
3804          * Otherwise we are done.
3805          */
3806         for (level = 0, i = 2; i == 2; level++) {
3807                 error = xfs_btree_delrec(cur, level, &i);
3808                 if (error)
3809                         goto error0;
3810         }
3811 
3812         if (i == 0) {
3813                 for (level = 1; level < cur->bc_nlevels; level++) {
3814                         if (cur->bc_ptrs[level] == 0) {
3815                                 error = xfs_btree_decrement(cur, level, &i);
3816                                 if (error)
3817                                         goto error0;
3818                                 break;
3819                         }
3820                 }
3821         }
3822 
3823         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3824         *stat = i;
3825         return 0;
3826 error0:
3827         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3828         return error;
3829 }
3830 
3831 /*
3832  * Get the data from the pointed-to record.
3833  */
3834 int                                     /* error */
3835 xfs_btree_get_rec(
3836         struct xfs_btree_cur    *cur,   /* btree cursor */
3837         union xfs_btree_rec     **recp, /* output: btree record */
3838         int                     *stat)  /* output: success/failure */
3839 {
3840         struct xfs_btree_block  *block; /* btree block */
3841         struct xfs_buf          *bp;    /* buffer pointer */
3842         int                     ptr;    /* record number */
3843 #ifdef DEBUG
3844         int                     error;  /* error return value */
3845 #endif
3846 
3847         ptr = cur->bc_ptrs[0];
3848         block = xfs_btree_get_block(cur, 0, &bp);
3849 
3850 #ifdef DEBUG
3851         error = xfs_btree_check_block(cur, block, 0, bp);
3852         if (error)
3853                 return error;
3854 #endif
3855 
3856         /*
3857          * Off the right end or left end, return failure.
3858          */
3859         if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) {
3860                 *stat = 0;
3861                 return 0;
3862         }
3863 
3864         /*
3865          * Point to the record and extract its data.
3866          */
3867         *recp = xfs_btree_rec_addr(cur, ptr, block);
3868         *stat = 1;
3869         return 0;
3870 }
3871 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp