LCOV - code coverage report
Current view: top level - fs/xfs/libxfs - xfs_da_btree.c (source / functions) Hit Total Coverage
Test: fstests of 6.5.0-rc3-acha @ Mon Jul 31 20:08:06 PDT 2023 Lines: 1094 1504 72.7 %
Date: 2023-07-31 20:08:07 Functions: 44 45 97.8 %

          Line data    Source code
       1             : // SPDX-License-Identifier: GPL-2.0
       2             : /*
       3             :  * Copyright (c) 2000-2005 Silicon Graphics, Inc.
       4             :  * Copyright (c) 2013 Red Hat, Inc.
       5             :  * All Rights Reserved.
       6             :  */
       7             : #include "xfs.h"
       8             : #include "xfs_fs.h"
       9             : #include "xfs_shared.h"
      10             : #include "xfs_format.h"
      11             : #include "xfs_log_format.h"
      12             : #include "xfs_trans_resv.h"
      13             : #include "xfs_bit.h"
      14             : #include "xfs_mount.h"
      15             : #include "xfs_inode.h"
      16             : #include "xfs_dir2.h"
      17             : #include "xfs_dir2_priv.h"
      18             : #include "xfs_trans.h"
      19             : #include "xfs_bmap.h"
      20             : #include "xfs_attr_leaf.h"
      21             : #include "xfs_error.h"
      22             : #include "xfs_trace.h"
      23             : #include "xfs_buf_item.h"
      24             : #include "xfs_log.h"
      25             : #include "xfs_errortag.h"
      26             : #include "xfs_health.h"
      27             : 
      28             : /*
      29             :  * xfs_da_btree.c
      30             :  *
      31             :  * Routines to implement directories as Btrees of hashed names.
      32             :  */
      33             : 
      34             : /*========================================================================
      35             :  * Function prototypes for the kernel.
      36             :  *========================================================================*/
      37             : 
      38             : /*
      39             :  * Routines used for growing the Btree.
      40             :  */
      41             : STATIC int xfs_da3_root_split(xfs_da_state_t *state,
      42             :                                             xfs_da_state_blk_t *existing_root,
      43             :                                             xfs_da_state_blk_t *new_child);
      44             : STATIC int xfs_da3_node_split(xfs_da_state_t *state,
      45             :                                             xfs_da_state_blk_t *existing_blk,
      46             :                                             xfs_da_state_blk_t *split_blk,
      47             :                                             xfs_da_state_blk_t *blk_to_add,
      48             :                                             int treelevel,
      49             :                                             int *result);
      50             : STATIC void xfs_da3_node_rebalance(xfs_da_state_t *state,
      51             :                                          xfs_da_state_blk_t *node_blk_1,
      52             :                                          xfs_da_state_blk_t *node_blk_2);
      53             : STATIC void xfs_da3_node_add(xfs_da_state_t *state,
      54             :                                    xfs_da_state_blk_t *old_node_blk,
      55             :                                    xfs_da_state_blk_t *new_node_blk);
      56             : 
      57             : /*
      58             :  * Routines used for shrinking the Btree.
      59             :  */
      60             : STATIC int xfs_da3_root_join(xfs_da_state_t *state,
      61             :                                            xfs_da_state_blk_t *root_blk);
      62             : STATIC int xfs_da3_node_toosmall(xfs_da_state_t *state, int *retval);
      63             : STATIC void xfs_da3_node_remove(xfs_da_state_t *state,
      64             :                                               xfs_da_state_blk_t *drop_blk);
      65             : STATIC void xfs_da3_node_unbalance(xfs_da_state_t *state,
      66             :                                          xfs_da_state_blk_t *src_node_blk,
      67             :                                          xfs_da_state_blk_t *dst_node_blk);
      68             : 
      69             : /*
      70             :  * Utility routines.
      71             :  */
      72             : STATIC int      xfs_da3_blk_unlink(xfs_da_state_t *state,
      73             :                                   xfs_da_state_blk_t *drop_blk,
      74             :                                   xfs_da_state_blk_t *save_blk);
      75             : 
      76             : 
      77             : struct kmem_cache       *xfs_da_state_cache;    /* anchor for dir/attr state */
      78             : 
      79             : /*
      80             :  * Allocate a dir-state structure.
      81             :  * We don't put them on the stack since they're large.
      82             :  */
      83             : struct xfs_da_state *
      84   151759467 : xfs_da_state_alloc(
      85             :         struct xfs_da_args      *args)
      86             : {
      87   151759467 :         struct xfs_da_state     *state;
      88             : 
      89   151759467 :         state = kmem_cache_zalloc(xfs_da_state_cache, GFP_NOFS | __GFP_NOFAIL);
      90   151743173 :         state->args = args;
      91   151743173 :         state->mp = args->dp->i_mount;
      92   151743173 :         return state;
      93             : }
      94             : 
      95             : /*
      96             :  * Kill the altpath contents of a da-state structure.
      97             :  */
      98             : STATIC void
      99   151802927 : xfs_da_state_kill_altpath(xfs_da_state_t *state)
     100             : {
     101   151802927 :         int     i;
     102             : 
     103   151849431 :         for (i = 0; i < state->altpath.active; i++)
     104       46504 :                 state->altpath.blk[i].bp = NULL;
     105   151802927 :         state->altpath.active = 0;
     106   151802927 : }
     107             : 
     108             : /*
     109             :  * Free a da-state structure.
     110             :  */
     111             : void
     112   151773452 : xfs_da_state_free(xfs_da_state_t *state)
     113             : {
     114   151773452 :         xfs_da_state_kill_altpath(state);
     115             : #ifdef DEBUG
     116   151775030 :         memset((char *)state, 0, sizeof(*state));
     117             : #endif /* DEBUG */
     118   151775030 :         kmem_cache_free(xfs_da_state_cache, state);
     119   151773674 : }
     120             : 
     121             : void
     122       12145 : xfs_da_state_reset(
     123             :         struct xfs_da_state     *state,
     124             :         struct xfs_da_args      *args)
     125             : {
     126       12145 :         xfs_da_state_kill_altpath(state);
     127       12145 :         memset(state, 0, sizeof(struct xfs_da_state));
     128       12145 :         state->args = args;
     129       12145 :         state->mp = state->args->dp->i_mount;
     130       12145 : }
     131             : 
     132             : static inline int xfs_dabuf_nfsb(struct xfs_mount *mp, int whichfork)
     133             : {
     134  1848606913 :         if (whichfork == XFS_DATA_FORK)
     135   898409380 :                 return mp->m_dir_geo->fsbcount;
     136   950197533 :         return mp->m_attr_geo->fsbcount;
     137             : }
     138             : 
     139             : void
     140   585667997 : xfs_da3_node_hdr_from_disk(
     141             :         struct xfs_mount                *mp,
     142             :         struct xfs_da3_icnode_hdr       *to,
     143             :         struct xfs_da_intnode           *from)
     144             : {
     145   585667997 :         if (xfs_has_crc(mp)) {
     146   585667997 :                 struct xfs_da3_intnode  *from3 = (struct xfs_da3_intnode *)from;
     147             : 
     148   585667997 :                 to->forw = be32_to_cpu(from3->hdr.info.hdr.forw);
     149   585667997 :                 to->back = be32_to_cpu(from3->hdr.info.hdr.back);
     150   585667997 :                 to->magic = be16_to_cpu(from3->hdr.info.hdr.magic);
     151   585667997 :                 to->count = be16_to_cpu(from3->hdr.__count);
     152   585667997 :                 to->level = be16_to_cpu(from3->hdr.__level);
     153   585667997 :                 to->btree = from3->__btree;
     154   585667997 :                 ASSERT(to->magic == XFS_DA3_NODE_MAGIC);
     155             :         } else {
     156           0 :                 to->forw = be32_to_cpu(from->hdr.info.forw);
     157           0 :                 to->back = be32_to_cpu(from->hdr.info.back);
     158           0 :                 to->magic = be16_to_cpu(from->hdr.info.magic);
     159           0 :                 to->count = be16_to_cpu(from->hdr.__count);
     160           0 :                 to->level = be16_to_cpu(from->hdr.__level);
     161           0 :                 to->btree = from->__btree;
     162           0 :                 ASSERT(to->magic == XFS_DA_NODE_MAGIC);
     163             :         }
     164   585667997 : }
     165             : 
     166             : void
     167      190399 : xfs_da3_node_hdr_to_disk(
     168             :         struct xfs_mount                *mp,
     169             :         struct xfs_da_intnode           *to,
     170             :         struct xfs_da3_icnode_hdr       *from)
     171             : {
     172      190399 :         if (xfs_has_crc(mp)) {
     173      190399 :                 struct xfs_da3_intnode  *to3 = (struct xfs_da3_intnode *)to;
     174             : 
     175      190399 :                 ASSERT(from->magic == XFS_DA3_NODE_MAGIC);
     176      190399 :                 to3->hdr.info.hdr.forw = cpu_to_be32(from->forw);
     177      190399 :                 to3->hdr.info.hdr.back = cpu_to_be32(from->back);
     178      190399 :                 to3->hdr.info.hdr.magic = cpu_to_be16(from->magic);
     179      190399 :                 to3->hdr.__count = cpu_to_be16(from->count);
     180      380798 :                 to3->hdr.__level = cpu_to_be16(from->level);
     181             :         } else {
     182           0 :                 ASSERT(from->magic == XFS_DA_NODE_MAGIC);
     183           0 :                 to->hdr.info.forw = cpu_to_be32(from->forw);
     184           0 :                 to->hdr.info.back = cpu_to_be32(from->back);
     185           0 :                 to->hdr.info.magic = cpu_to_be16(from->magic);
     186           0 :                 to->hdr.__count = cpu_to_be16(from->count);
     187           0 :                 to->hdr.__level = cpu_to_be16(from->level);
     188             :         }
     189      190399 : }
     190             : 
     191             : /*
     192             :  * Verify an xfs_da3_blkinfo structure. Note that the da3 fields are only
     193             :  * accessible on v5 filesystems. This header format is common across da node,
     194             :  * attr leaf and dir leaf blocks.
     195             :  */
     196             : xfs_failaddr_t
     197    25286175 : xfs_da3_blkinfo_verify(
     198             :         struct xfs_buf          *bp,
     199             :         struct xfs_da3_blkinfo  *hdr3)
     200             : {
     201    25286175 :         struct xfs_mount        *mp = bp->b_mount;
     202    25286175 :         struct xfs_da_blkinfo   *hdr = &hdr3->hdr;
     203             : 
     204    25286175 :         if (!xfs_verify_magic16(bp, hdr->magic))
     205           0 :                 return __this_address;
     206             : 
     207    25286183 :         if (xfs_has_crc(mp)) {
     208    25286183 :                 if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))
     209           0 :                         return __this_address;
     210    25286202 :                 if (be64_to_cpu(hdr3->blkno) != xfs_buf_daddr(bp))
     211           0 :                         return __this_address;
     212    25286209 :                 if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->lsn)))
     213           0 :                         return __this_address;
     214             :         }
     215             : 
     216             :         return NULL;
     217             : }
     218             : 
     219             : static xfs_failaddr_t
     220      150406 : xfs_da3_node_verify(
     221             :         struct xfs_buf          *bp)
     222             : {
     223      150406 :         struct xfs_mount        *mp = bp->b_mount;
     224      150406 :         struct xfs_da_intnode   *hdr = bp->b_addr;
     225      150406 :         struct xfs_da3_icnode_hdr ichdr;
     226      150406 :         xfs_failaddr_t          fa;
     227             : 
     228      150406 :         xfs_da3_node_hdr_from_disk(mp, &ichdr, hdr);
     229             : 
     230      150406 :         fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);
     231      150406 :         if (fa)
     232             :                 return fa;
     233             : 
     234      150406 :         if (ichdr.level == 0)
     235           0 :                 return __this_address;
     236      150406 :         if (ichdr.level > XFS_DA_NODE_MAXDEPTH)
     237           0 :                 return __this_address;
     238      150406 :         if (ichdr.count == 0)
     239           0 :                 return __this_address;
     240             : 
     241             :         /*
     242             :          * we don't know if the node is for and attribute or directory tree,
     243             :          * so only fail if the count is outside both bounds
     244             :          */
     245      150406 :         if (ichdr.count > mp->m_dir_geo->node_ents &&
     246           0 :             ichdr.count > mp->m_attr_geo->node_ents)
     247           0 :                 return __this_address;
     248             : 
     249             :         /* XXX: hash order check? */
     250             : 
     251             :         return NULL;
     252             : }
     253             : 
     254             : xfs_failaddr_t
     255   154318283 : xfs_da3_node_header_check(
     256             :         struct xfs_buf          *bp,
     257             :         xfs_ino_t               owner)
     258             : {
     259   154318283 :         struct xfs_mount        *mp = bp->b_mount;
     260             : 
     261   154318283 :         if (xfs_has_crc(mp)) {
     262   154318283 :                 struct xfs_da3_blkinfo *hdr3 = bp->b_addr;
     263             : 
     264   154318283 :                 ASSERT(hdr3->hdr.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
     265             : 
     266   154318283 :                 if (be64_to_cpu(hdr3->owner) != owner)
     267          54 :                         return __this_address;
     268             :         }
     269             : 
     270             :         return NULL;
     271             : }
     272             : 
     273             : xfs_failaddr_t
     274     1599203 : xfs_da3_header_check(
     275             :         struct xfs_buf          *bp,
     276             :         xfs_ino_t               owner)
     277             : {
     278     1599203 :         struct xfs_mount        *mp = bp->b_mount;
     279     1599203 :         struct xfs_da_blkinfo   *hdr = bp->b_addr;
     280             : 
     281     1599203 :         if (!xfs_has_crc(mp))
     282             :                 return NULL;
     283             : 
     284     1599203 :         switch (hdr->magic) {
     285     1325108 :         case cpu_to_be16(XFS_ATTR3_LEAF_MAGIC):
     286     1325108 :                 return xfs_attr3_leaf_header_check(bp, owner);
     287       38850 :         case cpu_to_be16(XFS_DA3_NODE_MAGIC):
     288       38850 :                 return xfs_da3_node_header_check(bp, owner);
     289      235245 :         case cpu_to_be16(XFS_DIR3_LEAF1_MAGIC):
     290             :         case cpu_to_be16(XFS_DIR3_LEAFN_MAGIC):
     291      235245 :                 return xfs_dir3_leaf_header_check(bp, owner);
     292             :         }
     293             : 
     294           0 :         ASSERT(0);
     295           0 :         return NULL;
     296             : }
     297             : 
     298             : static void
     299       79540 : xfs_da3_node_write_verify(
     300             :         struct xfs_buf  *bp)
     301             : {
     302       79540 :         struct xfs_mount        *mp = bp->b_mount;
     303       79540 :         struct xfs_buf_log_item *bip = bp->b_log_item;
     304       79540 :         struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
     305       79540 :         xfs_failaddr_t          fa;
     306             : 
     307       79540 :         fa = xfs_da3_node_verify(bp);
     308       79540 :         if (fa) {
     309           0 :                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
     310           0 :                 return;
     311             :         }
     312             : 
     313       79540 :         if (!xfs_has_crc(mp))
     314             :                 return;
     315             : 
     316       79540 :         if (bip)
     317       79540 :                 hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
     318             : 
     319       79540 :         xfs_buf_update_cksum(bp, XFS_DA3_NODE_CRC_OFF);
     320             : }
     321             : 
     322             : /*
     323             :  * leaf/node format detection on trees is sketchy, so a node read can be done on
     324             :  * leaf level blocks when detection identifies the tree as a node format tree
     325             :  * incorrectly. In this case, we need to swap the verifier to match the correct
     326             :  * format of the block being read.
     327             :  */
     328             : static void
     329      128107 : xfs_da3_node_read_verify(
     330             :         struct xfs_buf          *bp)
     331             : {
     332      128107 :         struct xfs_da_blkinfo   *info = bp->b_addr;
     333      128107 :         xfs_failaddr_t          fa;
     334             : 
     335      128107 :         switch (be16_to_cpu(info->magic)) {
     336             :                 case XFS_DA3_NODE_MAGIC:
     337       31989 :                         if (!xfs_buf_verify_cksum(bp, XFS_DA3_NODE_CRC_OFF)) {
     338          16 :                                 xfs_verifier_error(bp, -EFSBADCRC,
     339           8 :                                                 __this_address);
     340           8 :                                 break;
     341             :                         }
     342       31981 :                         fallthrough;
     343             :                 case XFS_DA_NODE_MAGIC:
     344       31981 :                         fa = xfs_da3_node_verify(bp);
     345       31981 :                         if (fa)
     346           0 :                                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
     347             :                         return;
     348       28004 :                 case XFS_ATTR_LEAF_MAGIC:
     349             :                 case XFS_ATTR3_LEAF_MAGIC:
     350       28004 :                         bp->b_ops = &xfs_attr3_leaf_buf_ops;
     351       28004 :                         bp->b_ops->verify_read(bp);
     352       28004 :                         return;
     353       68112 :                 case XFS_DIR2_LEAFN_MAGIC:
     354             :                 case XFS_DIR3_LEAFN_MAGIC:
     355       68112 :                         bp->b_ops = &xfs_dir3_leafn_buf_ops;
     356       68112 :                         bp->b_ops->verify_read(bp);
     357       68112 :                         return;
     358             :                 default:
     359           2 :                         xfs_verifier_error(bp, -EFSCORRUPTED, __this_address);
     360           2 :                         break;
     361             :         }
     362             : }
     363             : 
     364             : /* Verify the structure of a da3 block. */
     365             : static xfs_failaddr_t
     366       38885 : xfs_da3_node_verify_struct(
     367             :         struct xfs_buf          *bp)
     368             : {
     369       38885 :         struct xfs_da_blkinfo   *info = bp->b_addr;
     370             : 
     371       38885 :         switch (be16_to_cpu(info->magic)) {
     372       38885 :         case XFS_DA3_NODE_MAGIC:
     373             :         case XFS_DA_NODE_MAGIC:
     374       38885 :                 return xfs_da3_node_verify(bp);
     375           0 :         case XFS_ATTR_LEAF_MAGIC:
     376             :         case XFS_ATTR3_LEAF_MAGIC:
     377           0 :                 bp->b_ops = &xfs_attr3_leaf_buf_ops;
     378           0 :                 return bp->b_ops->verify_struct(bp);
     379           0 :         case XFS_DIR2_LEAFN_MAGIC:
     380             :         case XFS_DIR3_LEAFN_MAGIC:
     381           0 :                 bp->b_ops = &xfs_dir3_leafn_buf_ops;
     382           0 :                 return bp->b_ops->verify_struct(bp);
     383             :         default:
     384           0 :                 return __this_address;
     385             :         }
     386             : }
     387             : 
     388             : const struct xfs_buf_ops xfs_da3_node_buf_ops = {
     389             :         .name = "xfs_da3_node",
     390             :         .magic16 = { cpu_to_be16(XFS_DA_NODE_MAGIC),
     391             :                      cpu_to_be16(XFS_DA3_NODE_MAGIC) },
     392             :         .verify_read = xfs_da3_node_read_verify,
     393             :         .verify_write = xfs_da3_node_write_verify,
     394             :         .verify_struct = xfs_da3_node_verify_struct,
     395             : };
     396             : 
     397             : static int
     398   584965064 : xfs_da3_node_set_type(
     399             :         struct xfs_trans        *tp,
     400             :         struct xfs_inode        *dp,
     401             :         int                     whichfork,
     402             :         struct xfs_buf          *bp)
     403             : {
     404   584965064 :         struct xfs_da_blkinfo   *info = bp->b_addr;
     405             : 
     406   584965064 :         switch (be16_to_cpu(info->magic)) {
     407   141617752 :         case XFS_DA_NODE_MAGIC:
     408             :         case XFS_DA3_NODE_MAGIC:
     409   141617752 :                 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
     410   141617752 :                 return 0;
     411   309212239 :         case XFS_ATTR_LEAF_MAGIC:
     412             :         case XFS_ATTR3_LEAF_MAGIC:
     413   309212239 :                 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_ATTR_LEAF_BUF);
     414   309212239 :                 return 0;
     415   134135073 :         case XFS_DIR2_LEAFN_MAGIC:
     416             :         case XFS_DIR3_LEAFN_MAGIC:
     417   134135073 :                 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
     418   134135073 :                 return 0;
     419           0 :         default:
     420           0 :                 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, tp->t_mountp,
     421             :                                 info, sizeof(*info));
     422           0 :                 xfs_trans_brelse(tp, bp);
     423           0 :                 xfs_dirattr_mark_sick(dp, whichfork);
     424           0 :                 return -EFSCORRUPTED;
     425             :         }
     426             : }
     427             : 
     428             : int
     429   610112787 : xfs_da3_node_read(
     430             :         struct xfs_trans        *tp,
     431             :         struct xfs_inode        *dp,
     432             :         xfs_dablk_t             bno,
     433             :         struct xfs_buf          **bpp,
     434             :         int                     whichfork)
     435             : {
     436   610112787 :         int                     error;
     437             : 
     438   610112787 :         error = xfs_da_read_buf(tp, dp, bno, 0, bpp, whichfork,
     439             :                         &xfs_da3_node_buf_ops);
     440   610223031 :         if (error || !*bpp || !tp)
     441             :                 return error;
     442   584917518 :         return xfs_da3_node_set_type(tp, dp, whichfork, *bpp);
     443             : }
     444             : 
     445             : int
     446       22628 : xfs_da3_node_read_mapped(
     447             :         struct xfs_trans        *tp,
     448             :         struct xfs_inode        *dp,
     449             :         xfs_daddr_t             mappedbno,
     450             :         struct xfs_buf          **bpp,
     451             :         int                     whichfork)
     452             : {
     453       22628 :         struct xfs_mount        *mp = dp->i_mount;
     454       22628 :         int                     error;
     455             : 
     456       22628 :         error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, mappedbno,
     457       22628 :                         XFS_FSB_TO_BB(mp, xfs_dabuf_nfsb(mp, whichfork)), 0,
     458             :                         bpp, &xfs_da3_node_buf_ops);
     459       22628 :         if (xfs_metadata_is_sick(error))
     460           0 :                 xfs_dirattr_mark_sick(dp, whichfork);
     461       22628 :         if (error || !*bpp)
     462             :                 return error;
     463             : 
     464       22628 :         if (whichfork == XFS_ATTR_FORK)
     465       22628 :                 xfs_buf_set_ref(*bpp, XFS_ATTR_BTREE_REF);
     466             :         else
     467           0 :                 xfs_buf_set_ref(*bpp, XFS_DIR_BTREE_REF);
     468             : 
     469       22628 :         if (!tp)
     470             :                 return 0;
     471       22628 :         return xfs_da3_node_set_type(tp, dp, whichfork, *bpp);
     472             : }
     473             : 
     474             : /*========================================================================
     475             :  * Routines used for growing the Btree.
     476             :  *========================================================================*/
     477             : 
     478             : /*
     479             :  * Create the initial contents of an intermediate node.
     480             :  */
     481             : int
     482       39992 : xfs_da3_node_create(
     483             :         struct xfs_da_args      *args,
     484             :         xfs_dablk_t             blkno,
     485             :         int                     level,
     486             :         struct xfs_buf          **bpp,
     487             :         int                     whichfork)
     488             : {
     489       39992 :         struct xfs_da_intnode   *node;
     490       39992 :         struct xfs_trans        *tp = args->trans;
     491       39992 :         struct xfs_mount        *mp = tp->t_mountp;
     492       39992 :         struct xfs_da3_icnode_hdr ichdr = {0};
     493       39992 :         struct xfs_buf          *bp;
     494       39992 :         int                     error;
     495       39992 :         struct xfs_inode        *dp = args->dp;
     496             : 
     497       39992 :         trace_xfs_da_node_create(args);
     498       39992 :         ASSERT(level <= XFS_DA_NODE_MAXDEPTH);
     499             : 
     500       39992 :         error = xfs_da_get_buf(tp, dp, blkno, &bp, whichfork);
     501       39992 :         if (error)
     502             :                 return error;
     503       39992 :         bp->b_ops = &xfs_da3_node_buf_ops;
     504       39992 :         xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
     505       39992 :         node = bp->b_addr;
     506             : 
     507       39992 :         if (xfs_has_crc(mp)) {
     508       39992 :                 struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
     509             : 
     510       39992 :                 memset(hdr3, 0, sizeof(struct xfs_da3_node_hdr));
     511       39992 :                 ichdr.magic = XFS_DA3_NODE_MAGIC;
     512       39992 :                 hdr3->info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
     513       39992 :                 hdr3->info.owner = cpu_to_be64(args->owner);
     514       39992 :                 uuid_copy(&hdr3->info.uuid, &mp->m_sb.sb_meta_uuid);
     515             :         } else {
     516           0 :                 ichdr.magic = XFS_DA_NODE_MAGIC;
     517             :         }
     518       39992 :         ichdr.level = level;
     519             : 
     520       39992 :         xfs_da3_node_hdr_to_disk(dp->i_mount, node, &ichdr);
     521       39992 :         xfs_trans_log_buf(tp, bp,
     522       39992 :                 XFS_DA_LOGRANGE(node, &node->hdr, args->geo->node_hdr_size));
     523             : 
     524       39992 :         *bpp = bp;
     525       39992 :         return 0;
     526             : }
     527             : 
     528             : /*
     529             :  * Split a leaf node, rebalance, then possibly split
     530             :  * intermediate nodes, rebalance, etc.
     531             :  */
     532             : int                                                     /* error */
     533       89182 : xfs_da3_split(
     534             :         struct xfs_da_state     *state)
     535             : {
     536       89182 :         struct xfs_da_state_blk *oldblk;
     537       89182 :         struct xfs_da_state_blk *newblk;
     538       89182 :         struct xfs_da_state_blk *addblk;
     539       89182 :         struct xfs_da_intnode   *node;
     540       89182 :         int                     max;
     541       89182 :         int                     action = 0;
     542       89182 :         int                     error;
     543       89182 :         int                     i;
     544             : 
     545       89182 :         trace_xfs_da_split(state->args);
     546             : 
     547       89182 :         if (XFS_TEST_ERROR(false, state->mp, XFS_ERRTAG_DA_LEAF_SPLIT))
     548             :                 return -EIO;
     549             : 
     550             :         /*
     551             :          * Walk back up the tree splitting/inserting/adjusting as necessary.
     552             :          * If we need to insert and there isn't room, split the node, then
     553             :          * decide which fragment to insert the new block from below into.
     554             :          * Note that we may split the root this way, but we need more fixup.
     555             :          */
     556       89180 :         max = state->path.active - 1;
     557       89180 :         ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
     558       89180 :         ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
     559             :                state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
     560             : 
     561       89180 :         addblk = &state->path.blk[max];          /* initial dummy value */
     562      266028 :         for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
     563      176850 :                 oldblk = &state->path.blk[i];
     564      176850 :                 newblk = &state->altpath.blk[i];
     565             : 
     566             :                 /*
     567             :                  * If a leaf node then
     568             :                  *     Allocate a new leaf node, then rebalance across them.
     569             :                  * else if an intermediate node then
     570             :                  *     We split on the last layer, must we split the node?
     571             :                  */
     572      176850 :                 switch (oldblk->magic) {
     573       60323 :                 case XFS_ATTR_LEAF_MAGIC:
     574       60323 :                         error = xfs_attr3_leaf_split(state, oldblk, newblk);
     575       60322 :                         if ((error != 0) && (error != -ENOSPC)) {
     576           0 :                                 return error;   /* GROT: attr is inconsistent */
     577             :                         }
     578       60322 :                         if (!error) {
     579             :                                 addblk = newblk;
     580             :                                 break;
     581             :                         }
     582             :                         /*
     583             :                          * Entry wouldn't fit, split the leaf again. The new
     584             :                          * extrablk will be consumed by xfs_da3_node_split if
     585             :                          * the node is split.
     586             :                          */
     587           0 :                         state->extravalid = 1;
     588           0 :                         if (state->inleaf) {
     589           0 :                                 state->extraafter = 0;       /* before newblk */
     590           0 :                                 trace_xfs_attr_leaf_split_before(state->args);
     591           0 :                                 error = xfs_attr3_leaf_split(state, oldblk,
     592           0 :                                                             &state->extrablk);
     593             :                         } else {
     594           0 :                                 state->extraafter = 1;       /* after newblk */
     595           0 :                                 trace_xfs_attr_leaf_split_after(state->args);
     596           0 :                                 error = xfs_attr3_leaf_split(state, newblk,
     597           0 :                                                             &state->extrablk);
     598             :                         }
     599           0 :                         if (error)
     600           0 :                                 return error;   /* GROT: attr inconsistent */
     601             :                         addblk = newblk;
     602             :                         break;
     603       28856 :                 case XFS_DIR2_LEAFN_MAGIC:
     604       28856 :                         error = xfs_dir2_leafn_split(state, oldblk, newblk);
     605       28857 :                         if (error)
     606           0 :                                 return error;
     607             :                         addblk = newblk;
     608             :                         break;
     609       87671 :                 case XFS_DA_NODE_MAGIC:
     610       87671 :                         error = xfs_da3_node_split(state, oldblk, newblk, addblk,
     611             :                                                          max - i, &action);
     612       87670 :                         addblk->bp = NULL;
     613       87670 :                         if (error)
     614           0 :                                 return error;   /* GROT: dir is inconsistent */
     615             :                         /*
     616             :                          * Record the newly split block for the next time thru?
     617             :                          */
     618       87670 :                         if (action)
     619             :                                 addblk = newblk;
     620             :                         else
     621       87609 :                                 addblk = NULL;
     622             :                         break;
     623             :                 }
     624             : 
     625             :                 /*
     626             :                  * Update the btree to show the new hashval for this child.
     627             :                  */
     628      176849 :                 xfs_da3_fixhashpath(state, &state->path);
     629             :         }
     630       89178 :         if (!addblk)
     631             :                 return 0;
     632             : 
     633             :         /*
     634             :          * xfs_da3_node_split() should have consumed any extra blocks we added
     635             :          * during a double leaf split in the attr fork. This is guaranteed as
     636             :          * we can't be here if the attr fork only has a single leaf block.
     637             :          */
     638        1570 :         ASSERT(state->extravalid == 0 ||
     639             :                state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
     640             : 
     641             :         /*
     642             :          * Split the root node.
     643             :          */
     644        1570 :         ASSERT(state->path.active == 0);
     645        1570 :         oldblk = &state->path.blk[0];
     646        1570 :         error = xfs_da3_root_split(state, oldblk, addblk);
     647        1570 :         if (error)
     648           0 :                 goto out;
     649             : 
     650             :         /*
     651             :          * Update pointers to the node which used to be block 0 and just got
     652             :          * bumped because of the addition of a new root node.  Note that the
     653             :          * original block 0 could be at any position in the list of blocks in
     654             :          * the tree.
     655             :          *
     656             :          * Note: the magic numbers and sibling pointers are in the same physical
     657             :          * place for both v2 and v3 headers (by design). Hence it doesn't matter
     658             :          * which version of the xfs_da_intnode structure we use here as the
     659             :          * result will be the same using either structure.
     660             :          */
     661        1570 :         node = oldblk->bp->b_addr;
     662        1570 :         if (node->hdr.info.forw) {
     663        3140 :                 if (be32_to_cpu(node->hdr.info.forw) != addblk->blkno) {
     664           0 :                         xfs_buf_mark_corrupt(oldblk->bp);
     665           0 :                         xfs_da_mark_sick(state->args);
     666           0 :                         error = -EFSCORRUPTED;
     667           0 :                         goto out;
     668             :                 }
     669        1570 :                 node = addblk->bp->b_addr;
     670        1570 :                 node->hdr.info.back = cpu_to_be32(oldblk->blkno);
     671        1570 :                 xfs_trans_log_buf(state->args->trans, addblk->bp,
     672             :                                   XFS_DA_LOGRANGE(node, &node->hdr.info,
     673             :                                   sizeof(node->hdr.info)));
     674             :         }
     675        1570 :         node = oldblk->bp->b_addr;
     676        1570 :         if (node->hdr.info.back) {
     677           0 :                 if (be32_to_cpu(node->hdr.info.back) != addblk->blkno) {
     678           0 :                         xfs_buf_mark_corrupt(oldblk->bp);
     679           0 :                         xfs_da_mark_sick(state->args);
     680           0 :                         error = -EFSCORRUPTED;
     681           0 :                         goto out;
     682             :                 }
     683           0 :                 node = addblk->bp->b_addr;
     684           0 :                 node->hdr.info.forw = cpu_to_be32(oldblk->blkno);
     685           0 :                 xfs_trans_log_buf(state->args->trans, addblk->bp,
     686             :                                   XFS_DA_LOGRANGE(node, &node->hdr.info,
     687             :                                   sizeof(node->hdr.info)));
     688             :         }
     689        1570 : out:
     690        1570 :         addblk->bp = NULL;
     691        1570 :         return error;
     692             : }
     693             : 
     694             : /*
     695             :  * Split the root.  We have to create a new root and point to the two
     696             :  * parts (the split old root) that we just created.  Copy block zero to
     697             :  * the EOF, extending the inode in process.
     698             :  */
     699             : STATIC int                                              /* error */
     700        1570 : xfs_da3_root_split(
     701             :         struct xfs_da_state     *state,
     702             :         struct xfs_da_state_blk *blk1,
     703             :         struct xfs_da_state_blk *blk2)
     704             : {
     705        1570 :         struct xfs_da_intnode   *node;
     706        1570 :         struct xfs_da_intnode   *oldroot;
     707        1570 :         struct xfs_da_node_entry *btree;
     708        1570 :         struct xfs_da3_icnode_hdr nodehdr;
     709        1570 :         struct xfs_da_args      *args;
     710        1570 :         struct xfs_buf          *bp;
     711        1570 :         struct xfs_inode        *dp;
     712        1570 :         struct xfs_trans        *tp;
     713        1570 :         struct xfs_dir2_leaf    *leaf;
     714        1570 :         xfs_dablk_t             blkno;
     715        1570 :         int                     level;
     716        1570 :         int                     error;
     717        1570 :         int                     size;
     718             : 
     719        1570 :         trace_xfs_da_root_split(state->args);
     720             : 
     721             :         /*
     722             :          * Copy the existing (incorrect) block from the root node position
     723             :          * to a free space somewhere.
     724             :          */
     725        1570 :         args = state->args;
     726        1570 :         error = xfs_da_grow_inode(args, &blkno);
     727        1570 :         if (error)
     728             :                 return error;
     729             : 
     730        1570 :         dp = args->dp;
     731        1570 :         tp = args->trans;
     732        1570 :         error = xfs_da_get_buf(tp, dp, blkno, &bp, args->whichfork);
     733        1570 :         if (error)
     734             :                 return error;
     735        1570 :         node = bp->b_addr;
     736        1570 :         oldroot = blk1->bp->b_addr;
     737        1570 :         if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
     738             :             oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC)) {
     739           6 :                 struct xfs_da3_icnode_hdr icnodehdr;
     740             : 
     741           6 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &icnodehdr, oldroot);
     742           6 :                 btree = icnodehdr.btree;
     743           6 :                 size = (int)((char *)&btree[icnodehdr.count] - (char *)oldroot);
     744           6 :                 level = icnodehdr.level;
     745             : 
     746             :                 /*
     747             :                  * we are about to copy oldroot to bp, so set up the type
     748             :                  * of bp while we know exactly what it will be.
     749             :                  */
     750           6 :                 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
     751             :         } else {
     752        1564 :                 struct xfs_dir3_icleaf_hdr leafhdr;
     753             : 
     754        1564 :                 leaf = (xfs_dir2_leaf_t *)oldroot;
     755        1564 :                 xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
     756             : 
     757        1564 :                 ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
     758             :                        leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
     759        1564 :                 size = (int)((char *)&leafhdr.ents[leafhdr.count] -
     760             :                         (char *)leaf);
     761        1564 :                 level = 0;
     762             : 
     763             :                 /*
     764             :                  * we are about to copy oldroot to bp, so set up the type
     765             :                  * of bp while we know exactly what it will be.
     766             :                  */
     767        1564 :                 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
     768             :         }
     769             : 
     770             :         /*
     771             :          * we can copy most of the information in the node from one block to
     772             :          * another, but for CRC enabled headers we have to make sure that the
     773             :          * block specific identifiers are kept intact. We update the buffer
     774             :          * directly for this.
     775             :          */
     776        3140 :         memcpy(node, oldroot, size);
     777        1570 :         if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
     778             :             oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
     779        1570 :                 struct xfs_da3_intnode *node3 = (struct xfs_da3_intnode *)node;
     780             : 
     781        1570 :                 node3->hdr.info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
     782             :         }
     783        1570 :         xfs_trans_log_buf(tp, bp, 0, size - 1);
     784             : 
     785        1570 :         bp->b_ops = blk1->bp->b_ops;
     786        1570 :         xfs_trans_buf_copy_type(bp, blk1->bp);
     787        1570 :         blk1->bp = bp;
     788        1570 :         blk1->blkno = blkno;
     789             : 
     790             :         /*
     791             :          * Set up the new root node.
     792             :          */
     793        1570 :         error = xfs_da3_node_create(args,
     794        1570 :                 (args->whichfork == XFS_DATA_FORK) ? args->geo->leafblk : 0,
     795             :                 level + 1, &bp, args->whichfork);
     796        1570 :         if (error)
     797             :                 return error;
     798             : 
     799        1570 :         node = bp->b_addr;
     800        1570 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
     801        1570 :         btree = nodehdr.btree;
     802        1570 :         btree[0].hashval = cpu_to_be32(blk1->hashval);
     803        1570 :         btree[0].before = cpu_to_be32(blk1->blkno);
     804        1570 :         btree[1].hashval = cpu_to_be32(blk2->hashval);
     805        1570 :         btree[1].before = cpu_to_be32(blk2->blkno);
     806        1570 :         nodehdr.count = 2;
     807        1570 :         xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
     808             : 
     809             : #ifdef DEBUG
     810        1570 :         if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
     811             :             oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
     812           0 :                 ASSERT(blk1->blkno >= args->geo->leafblk &&
     813             :                        blk1->blkno < args->geo->freeblk);
     814           0 :                 ASSERT(blk2->blkno >= args->geo->leafblk &&
     815             :                        blk2->blkno < args->geo->freeblk);
     816             :         }
     817             : #endif
     818             : 
     819             :         /* Header is already logged by xfs_da_node_create */
     820        1570 :         xfs_trans_log_buf(tp, bp,
     821        1570 :                 XFS_DA_LOGRANGE(node, btree, sizeof(xfs_da_node_entry_t) * 2));
     822             : 
     823        1570 :         return 0;
     824             : }
     825             : 
     826             : /*
     827             :  * Split the node, rebalance, then add the new entry.
     828             :  */
     829             : STATIC int                                              /* error */
     830       87671 : xfs_da3_node_split(
     831             :         struct xfs_da_state     *state,
     832             :         struct xfs_da_state_blk *oldblk,
     833             :         struct xfs_da_state_blk *newblk,
     834             :         struct xfs_da_state_blk *addblk,
     835             :         int                     treelevel,
     836             :         int                     *result)
     837             : {
     838       87671 :         struct xfs_da_intnode   *node;
     839       87671 :         struct xfs_da3_icnode_hdr nodehdr;
     840       87671 :         xfs_dablk_t             blkno;
     841       87671 :         int                     newcount;
     842       87671 :         int                     error;
     843       87671 :         int                     useextra;
     844       87671 :         struct xfs_inode        *dp = state->args->dp;
     845             : 
     846       87671 :         trace_xfs_da_node_split(state->args);
     847             : 
     848       87671 :         node = oldblk->bp->b_addr;
     849       87671 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
     850             : 
     851             :         /*
     852             :          * With V2 dirs the extra block is data or freespace.
     853             :          */
     854       87670 :         useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
     855       87670 :         newcount = 1 + useextra;
     856             :         /*
     857             :          * Do we have to split the node?
     858             :          */
     859       87670 :         if (nodehdr.count + newcount > state->args->geo->node_ents) {
     860             :                 /*
     861             :                  * Allocate a new node, add to the doubly linked chain of
     862             :                  * nodes, then move some of our excess entries into it.
     863             :                  */
     864          61 :                 error = xfs_da_grow_inode(state->args, &blkno);
     865          61 :                 if (error)
     866             :                         return error;   /* GROT: dir is inconsistent */
     867             : 
     868          61 :                 error = xfs_da3_node_create(state->args, blkno, treelevel,
     869             :                                            &newblk->bp, state->args->whichfork);
     870          61 :                 if (error)
     871             :                         return error;   /* GROT: dir is inconsistent */
     872          61 :                 newblk->blkno = blkno;
     873          61 :                 newblk->magic = XFS_DA_NODE_MAGIC;
     874          61 :                 xfs_da3_node_rebalance(state, oldblk, newblk);
     875          61 :                 error = xfs_da3_blk_link(state, oldblk, newblk);
     876          61 :                 if (error)
     877             :                         return error;
     878          61 :                 *result = 1;
     879             :         } else {
     880       87609 :                 *result = 0;
     881             :         }
     882             : 
     883             :         /*
     884             :          * Insert the new entry(s) into the correct block
     885             :          * (updating last hashval in the process).
     886             :          *
     887             :          * xfs_da3_node_add() inserts BEFORE the given index,
     888             :          * and as a result of using node_lookup_int() we always
     889             :          * point to a valid entry (not after one), but a split
     890             :          * operation always results in a new block whose hashvals
     891             :          * FOLLOW the current block.
     892             :          *
     893             :          * If we had double-split op below us, then add the extra block too.
     894             :          */
     895       87670 :         node = oldblk->bp->b_addr;
     896       87670 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
     897       87669 :         if (oldblk->index <= nodehdr.count) {
     898       87635 :                 oldblk->index++;
     899       87635 :                 xfs_da3_node_add(state, oldblk, addblk);
     900       87637 :                 if (useextra) {
     901           0 :                         if (state->extraafter)
     902           0 :                                 oldblk->index++;
     903           0 :                         xfs_da3_node_add(state, oldblk, &state->extrablk);
     904           0 :                         state->extravalid = 0;
     905             :                 }
     906             :         } else {
     907          34 :                 newblk->index++;
     908          34 :                 xfs_da3_node_add(state, newblk, addblk);
     909          34 :                 if (useextra) {
     910           0 :                         if (state->extraafter)
     911           0 :                                 newblk->index++;
     912           0 :                         xfs_da3_node_add(state, newblk, &state->extrablk);
     913           0 :                         state->extravalid = 0;
     914             :                 }
     915             :         }
     916             : 
     917             :         return 0;
     918             : }
     919             : 
     920             : /*
     921             :  * Balance the btree elements between two intermediate nodes,
     922             :  * usually one full and one empty.
     923             :  *
     924             :  * NOTE: if blk2 is empty, then it will get the upper half of blk1.
     925             :  */
     926             : STATIC void
     927          61 : xfs_da3_node_rebalance(
     928             :         struct xfs_da_state     *state,
     929             :         struct xfs_da_state_blk *blk1,
     930             :         struct xfs_da_state_blk *blk2)
     931             : {
     932          61 :         struct xfs_da_intnode   *node1;
     933          61 :         struct xfs_da_intnode   *node2;
     934          61 :         struct xfs_da_node_entry *btree1;
     935          61 :         struct xfs_da_node_entry *btree2;
     936          61 :         struct xfs_da_node_entry *btree_s;
     937          61 :         struct xfs_da_node_entry *btree_d;
     938          61 :         struct xfs_da3_icnode_hdr nodehdr1;
     939          61 :         struct xfs_da3_icnode_hdr nodehdr2;
     940          61 :         struct xfs_trans        *tp;
     941          61 :         int                     count;
     942          61 :         int                     tmp;
     943          61 :         int                     swap = 0;
     944          61 :         struct xfs_inode        *dp = state->args->dp;
     945             : 
     946          61 :         trace_xfs_da_node_rebalance(state->args);
     947             : 
     948          61 :         node1 = blk1->bp->b_addr;
     949          61 :         node2 = blk2->bp->b_addr;
     950          61 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
     951          61 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
     952          61 :         btree1 = nodehdr1.btree;
     953          61 :         btree2 = nodehdr2.btree;
     954             : 
     955             :         /*
     956             :          * Figure out how many entries need to move, and in which direction.
     957             :          * Swap the nodes around if that makes it simpler.
     958             :          */
     959          61 :         if (nodehdr1.count > 0 && nodehdr2.count > 0 &&
     960           0 :             ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
     961           0 :              (be32_to_cpu(btree2[nodehdr2.count - 1].hashval) <
     962           0 :                         be32_to_cpu(btree1[nodehdr1.count - 1].hashval)))) {
     963           0 :                 swap(node1, node2);
     964           0 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
     965           0 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
     966           0 :                 btree1 = nodehdr1.btree;
     967           0 :                 btree2 = nodehdr2.btree;
     968           0 :                 swap = 1;
     969             :         }
     970             : 
     971          61 :         count = (nodehdr1.count - nodehdr2.count) / 2;
     972          61 :         if (count == 0)
     973           0 :                 return;
     974          61 :         tp = state->args->trans;
     975             :         /*
     976             :          * Two cases: high-to-low and low-to-high.
     977             :          */
     978          61 :         if (count > 0) {
     979             :                 /*
     980             :                  * Move elements in node2 up to make a hole.
     981             :                  */
     982          61 :                 tmp = nodehdr2.count;
     983          61 :                 if (tmp > 0) {
     984           0 :                         tmp *= (uint)sizeof(xfs_da_node_entry_t);
     985           0 :                         btree_s = &btree2[0];
     986           0 :                         btree_d = &btree2[count];
     987           0 :                         memmove(btree_d, btree_s, tmp);
     988             :                 }
     989             : 
     990             :                 /*
     991             :                  * Move the req'd B-tree elements from high in node1 to
     992             :                  * low in node2.
     993             :                  */
     994          61 :                 nodehdr2.count += count;
     995          61 :                 tmp = count * (uint)sizeof(xfs_da_node_entry_t);
     996          61 :                 btree_s = &btree1[nodehdr1.count - count];
     997          61 :                 btree_d = &btree2[0];
     998         122 :                 memcpy(btree_d, btree_s, tmp);
     999          61 :                 nodehdr1.count -= count;
    1000             :         } else {
    1001             :                 /*
    1002             :                  * Move the req'd B-tree elements from low in node2 to
    1003             :                  * high in node1.
    1004             :                  */
    1005           0 :                 count = -count;
    1006           0 :                 tmp = count * (uint)sizeof(xfs_da_node_entry_t);
    1007           0 :                 btree_s = &btree2[0];
    1008           0 :                 btree_d = &btree1[nodehdr1.count];
    1009           0 :                 memcpy(btree_d, btree_s, tmp);
    1010           0 :                 nodehdr1.count += count;
    1011             : 
    1012           0 :                 xfs_trans_log_buf(tp, blk1->bp,
    1013           0 :                         XFS_DA_LOGRANGE(node1, btree_d, tmp));
    1014             : 
    1015             :                 /*
    1016             :                  * Move elements in node2 down to fill the hole.
    1017             :                  */
    1018           0 :                 tmp  = nodehdr2.count - count;
    1019           0 :                 tmp *= (uint)sizeof(xfs_da_node_entry_t);
    1020           0 :                 btree_s = &btree2[count];
    1021           0 :                 btree_d = &btree2[0];
    1022           0 :                 memmove(btree_d, btree_s, tmp);
    1023           0 :                 nodehdr2.count -= count;
    1024             :         }
    1025             : 
    1026             :         /*
    1027             :          * Log header of node 1 and all current bits of node 2.
    1028             :          */
    1029          61 :         xfs_da3_node_hdr_to_disk(dp->i_mount, node1, &nodehdr1);
    1030          61 :         xfs_trans_log_buf(tp, blk1->bp,
    1031          61 :                 XFS_DA_LOGRANGE(node1, &node1->hdr,
    1032             :                                 state->args->geo->node_hdr_size));
    1033             : 
    1034          61 :         xfs_da3_node_hdr_to_disk(dp->i_mount, node2, &nodehdr2);
    1035          61 :         xfs_trans_log_buf(tp, blk2->bp,
    1036          61 :                 XFS_DA_LOGRANGE(node2, &node2->hdr,
    1037             :                                 state->args->geo->node_hdr_size +
    1038             :                                 (sizeof(btree2[0]) * nodehdr2.count)));
    1039             : 
    1040             :         /*
    1041             :          * Record the last hashval from each block for upward propagation.
    1042             :          * (note: don't use the swapped node pointers)
    1043             :          */
    1044          61 :         if (swap) {
    1045           0 :                 node1 = blk1->bp->b_addr;
    1046           0 :                 node2 = blk2->bp->b_addr;
    1047           0 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
    1048           0 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
    1049           0 :                 btree1 = nodehdr1.btree;
    1050           0 :                 btree2 = nodehdr2.btree;
    1051             :         }
    1052          61 :         blk1->hashval = be32_to_cpu(btree1[nodehdr1.count - 1].hashval);
    1053          61 :         blk2->hashval = be32_to_cpu(btree2[nodehdr2.count - 1].hashval);
    1054             : 
    1055             :         /*
    1056             :          * Adjust the expected index for insertion.
    1057             :          */
    1058          61 :         if (blk1->index >= nodehdr1.count) {
    1059          34 :                 blk2->index = blk1->index - nodehdr1.count;
    1060          34 :                 blk1->index = nodehdr1.count + 1;    /* make it invalid */
    1061             :         }
    1062             : }
    1063             : 
    1064             : /*
    1065             :  * Add a new entry to an intermediate node.
    1066             :  */
    1067             : STATIC void
    1068       87669 : xfs_da3_node_add(
    1069             :         struct xfs_da_state     *state,
    1070             :         struct xfs_da_state_blk *oldblk,
    1071             :         struct xfs_da_state_blk *newblk)
    1072             : {
    1073       87669 :         struct xfs_da_intnode   *node;
    1074       87669 :         struct xfs_da3_icnode_hdr nodehdr;
    1075       87669 :         struct xfs_da_node_entry *btree;
    1076       87669 :         int                     tmp;
    1077       87669 :         struct xfs_inode        *dp = state->args->dp;
    1078             : 
    1079       87669 :         trace_xfs_da_node_add(state->args);
    1080             : 
    1081       87669 :         node = oldblk->bp->b_addr;
    1082       87669 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
    1083       87671 :         btree = nodehdr.btree;
    1084             : 
    1085       87671 :         ASSERT(oldblk->index >= 0 && oldblk->index <= nodehdr.count);
    1086       87671 :         ASSERT(newblk->blkno != 0);
    1087       87671 :         if (state->args->whichfork == XFS_DATA_FORK)
    1088       27296 :                 ASSERT(newblk->blkno >= state->args->geo->leafblk &&
    1089             :                        newblk->blkno < state->args->geo->freeblk);
    1090             : 
    1091             :         /*
    1092             :          * We may need to make some room before we insert the new node.
    1093             :          */
    1094       87671 :         tmp = 0;
    1095       87671 :         if (oldblk->index < nodehdr.count) {
    1096       25744 :                 tmp = (nodehdr.count - oldblk->index) * (uint)sizeof(*btree);
    1097       51488 :                 memmove(&btree[oldblk->index + 1], &btree[oldblk->index], tmp);
    1098             :         }
    1099       87671 :         btree[oldblk->index].hashval = cpu_to_be32(newblk->hashval);
    1100       87671 :         btree[oldblk->index].before = cpu_to_be32(newblk->blkno);
    1101       87671 :         xfs_trans_log_buf(state->args->trans, oldblk->bp,
    1102       87671 :                 XFS_DA_LOGRANGE(node, &btree[oldblk->index],
    1103             :                                 tmp + sizeof(*btree)));
    1104             : 
    1105       87668 :         nodehdr.count += 1;
    1106       87668 :         xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
    1107       87671 :         xfs_trans_log_buf(state->args->trans, oldblk->bp,
    1108       87671 :                 XFS_DA_LOGRANGE(node, &node->hdr,
    1109             :                                 state->args->geo->node_hdr_size));
    1110             : 
    1111             :         /*
    1112             :          * Copy the last hash value from the oldblk to propagate upwards.
    1113             :          */
    1114       87668 :         oldblk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
    1115       87668 : }
    1116             : 
    1117             : /*========================================================================
    1118             :  * Routines used for shrinking the Btree.
    1119             :  *========================================================================*/
    1120             : 
    1121             : /*
    1122             :  * Deallocate an empty leaf node, remove it from its parent,
    1123             :  * possibly deallocating that block, etc...
    1124             :  */
    1125             : int
    1126     2827262 : xfs_da3_join(
    1127             :         struct xfs_da_state     *state)
    1128             : {
    1129     2827262 :         struct xfs_da_state_blk *drop_blk;
    1130     2827262 :         struct xfs_da_state_blk *save_blk;
    1131     2827262 :         int                     action = 0;
    1132     2827262 :         int                     error;
    1133             : 
    1134     2827262 :         trace_xfs_da_join(state->args);
    1135             : 
    1136     2827299 :         drop_blk = &state->path.blk[ state->path.active-1 ];
    1137     2827299 :         save_blk = &state->altpath.blk[ state->path.active-1 ];
    1138     2827299 :         ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
    1139     2827299 :         ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC ||
    1140             :                drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
    1141             : 
    1142             :         /*
    1143             :          * Walk back up the tree joining/deallocating as necessary.
    1144             :          * When we stop dropping blocks, break out.
    1145             :          */
    1146     2849958 :         for (  ; state->path.active >= 2; drop_blk--, save_blk--,
    1147       22659 :                  state->path.active--) {
    1148             :                 /*
    1149             :                  * See if we can combine the block with a neighbor.
    1150             :                  *   (action == 0) => no options, just leave
    1151             :                  *   (action == 1) => coalesce, then unlink
    1152             :                  *   (action == 2) => block empty, unlink it
    1153             :                  */
    1154     2828422 :                 switch (drop_blk->magic) {
    1155      946997 :                 case XFS_ATTR_LEAF_MAGIC:
    1156      946997 :                         error = xfs_attr3_leaf_toosmall(state, &action);
    1157      947011 :                         if (error)
    1158           2 :                                 return error;
    1159      947009 :                         if (action == 0)
    1160             :                                 return 0;
    1161         768 :                         xfs_attr3_leaf_unbalance(state, drop_blk, save_blk);
    1162         768 :                         break;
    1163     1880281 :                 case XFS_DIR2_LEAFN_MAGIC:
    1164     1880281 :                         error = xfs_dir2_leafn_toosmall(state, &action);
    1165     1880293 :                         if (error)
    1166           0 :                                 return error;
    1167     1880293 :                         if (action == 0)
    1168             :                                 return 0;
    1169       21907 :                         xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
    1170       21907 :                         break;
    1171        1144 :                 case XFS_DA_NODE_MAGIC:
    1172             :                         /*
    1173             :                          * Remove the offending node, fixup hashvals,
    1174             :                          * check for a toosmall neighbor.
    1175             :                          */
    1176        1144 :                         xfs_da3_node_remove(state, drop_blk);
    1177        1144 :                         xfs_da3_fixhashpath(state, &state->path);
    1178        1144 :                         error = xfs_da3_node_toosmall(state, &action);
    1179        1144 :                         if (error)
    1180           0 :                                 return error;
    1181        1144 :                         if (action == 0)
    1182             :                                 return 0;
    1183           5 :                         xfs_da3_node_unbalance(state, drop_blk, save_blk);
    1184           5 :                         break;
    1185             :                 }
    1186       22680 :                 xfs_da3_fixhashpath(state, &state->altpath);
    1187       22680 :                 error = xfs_da3_blk_unlink(state, drop_blk, save_blk);
    1188       22680 :                 xfs_da_state_kill_altpath(state);
    1189       22680 :                 if (error)
    1190           0 :                         return error;
    1191       22680 :                 error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
    1192             :                                                          drop_blk->bp);
    1193       22659 :                 drop_blk->bp = NULL;
    1194       22659 :                 if (error)
    1195           0 :                         return error;
    1196             :         }
    1197             :         /*
    1198             :          * We joined all the way to the top.  If it turns out that
    1199             :          * we only have one entry in the root, make the child block
    1200             :          * the new root.
    1201             :          */
    1202       21536 :         xfs_da3_node_remove(state, drop_blk);
    1203       21536 :         xfs_da3_fixhashpath(state, &state->path);
    1204       21536 :         error = xfs_da3_root_join(state, &state->path.blk[0]);
    1205       21536 :         return error;
    1206             : }
    1207             : 
    1208             : #ifdef  DEBUG
    1209             : static void
    1210        1129 : xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
    1211             : {
    1212        1129 :         __be16  magic = blkinfo->magic;
    1213             : 
    1214        1129 :         if (level == 1) {
    1215        1128 :                 ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
    1216             :                        magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
    1217             :                        magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
    1218             :                        magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
    1219             :         } else {
    1220           1 :                 ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
    1221             :                        magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
    1222             :         }
    1223        1129 :         ASSERT(!blkinfo->forw);
    1224        1129 :         ASSERT(!blkinfo->back);
    1225        1129 : }
    1226             : #else   /* !DEBUG */
    1227             : #define xfs_da_blkinfo_onlychild_validate(blkinfo, level)
    1228             : #endif  /* !DEBUG */
    1229             : 
    1230             : /*
    1231             :  * We have only one entry in the root.  Copy the only remaining child of
    1232             :  * the old root to block 0 as the new root node.
    1233             :  */
    1234             : STATIC int
    1235       21536 : xfs_da3_root_join(
    1236             :         struct xfs_da_state     *state,
    1237             :         struct xfs_da_state_blk *root_blk)
    1238             : {
    1239       21536 :         struct xfs_da_intnode   *oldroot;
    1240       21536 :         struct xfs_da_args      *args;
    1241       21536 :         xfs_dablk_t             child;
    1242       21536 :         struct xfs_buf          *bp;
    1243       21536 :         struct xfs_da3_icnode_hdr oldroothdr;
    1244       21536 :         int                     error;
    1245       21536 :         struct xfs_inode        *dp = state->args->dp;
    1246       21536 :         xfs_failaddr_t          fa;
    1247             : 
    1248       21536 :         trace_xfs_da_root_join(state->args);
    1249             : 
    1250       21536 :         ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
    1251             : 
    1252       21536 :         args = state->args;
    1253       21536 :         oldroot = root_blk->bp->b_addr;
    1254       21536 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &oldroothdr, oldroot);
    1255       21536 :         ASSERT(oldroothdr.forw == 0);
    1256       21536 :         ASSERT(oldroothdr.back == 0);
    1257             : 
    1258             :         /*
    1259             :          * If the root has more than one child, then don't do anything.
    1260             :          */
    1261       21536 :         if (oldroothdr.count > 1)
    1262             :                 return 0;
    1263             : 
    1264             :         /*
    1265             :          * Read in the (only) child block, then copy those bytes into
    1266             :          * the root block's buffer and free the original child block.
    1267             :          */
    1268        1129 :         child = be32_to_cpu(oldroothdr.btree[0].before);
    1269        1129 :         ASSERT(child != 0);
    1270        1129 :         error = xfs_da3_node_read(args->trans, dp, child, &bp, args->whichfork);
    1271        1129 :         if (error)
    1272             :                 return error;
    1273        1129 :         fa = xfs_da3_header_check(bp, args->owner);
    1274        1129 :         if (fa) {
    1275           0 :                 __xfs_buf_mark_corrupt(bp, fa);
    1276           0 :                 xfs_trans_brelse(args->trans, bp);
    1277           0 :                 xfs_da_mark_sick(args);
    1278           0 :                 return -EFSCORRUPTED;
    1279             :         }
    1280        1129 :         xfs_da_blkinfo_onlychild_validate(bp->b_addr, oldroothdr.level);
    1281             : 
    1282             :         /*
    1283             :          * This could be copying a leaf back into the root block in the case of
    1284             :          * there only being a single leaf block left in the tree. Hence we have
    1285             :          * to update the b_ops pointer as well to match the buffer type change
    1286             :          * that could occur. For dir3 blocks we also need to update the block
    1287             :          * number in the buffer header.
    1288             :          */
    1289        2258 :         memcpy(root_blk->bp->b_addr, bp->b_addr, args->geo->blksize);
    1290        1129 :         root_blk->bp->b_ops = bp->b_ops;
    1291        1129 :         xfs_trans_buf_copy_type(root_blk->bp, bp);
    1292        1129 :         if (oldroothdr.magic == XFS_DA3_NODE_MAGIC) {
    1293        1129 :                 struct xfs_da3_blkinfo *da3 = root_blk->bp->b_addr;
    1294        1129 :                 da3->blkno = cpu_to_be64(xfs_buf_daddr(root_blk->bp));
    1295             :         }
    1296        1129 :         xfs_trans_log_buf(args->trans, root_blk->bp, 0,
    1297        1129 :                           args->geo->blksize - 1);
    1298        1129 :         error = xfs_da_shrink_inode(args, child, bp);
    1299        1129 :         return error;
    1300             : }
    1301             : 
    1302             : /*
    1303             :  * Check a node block and its neighbors to see if the block should be
    1304             :  * collapsed into one or the other neighbor.  Always keep the block
    1305             :  * with the smaller block number.
    1306             :  * If the current block is over 50% full, don't try to join it, return 0.
    1307             :  * If the block is empty, fill in the state structure and return 2.
    1308             :  * If it can be collapsed, fill in the state structure and return 1.
    1309             :  * If nothing can be done, return 0.
    1310             :  */
    1311             : STATIC int
    1312        1144 : xfs_da3_node_toosmall(
    1313             :         struct xfs_da_state     *state,
    1314             :         int                     *action)
    1315             : {
    1316        1144 :         struct xfs_da_intnode   *node;
    1317        1144 :         struct xfs_da_state_blk *blk;
    1318        1144 :         struct xfs_da_blkinfo   *info;
    1319        1144 :         xfs_dablk_t             blkno;
    1320        1144 :         struct xfs_buf          *bp;
    1321        1144 :         xfs_failaddr_t          fa;
    1322        1144 :         struct xfs_da3_icnode_hdr nodehdr;
    1323        1144 :         int                     count;
    1324        1144 :         int                     forward;
    1325        1144 :         int                     error;
    1326        1144 :         int                     retval;
    1327        1144 :         int                     i;
    1328        1144 :         struct xfs_inode        *dp = state->args->dp;
    1329             : 
    1330        1144 :         trace_xfs_da_node_toosmall(state->args);
    1331             : 
    1332             :         /*
    1333             :          * Check for the degenerate case of the block being over 50% full.
    1334             :          * If so, it's not worth even looking to see if we might be able
    1335             :          * to coalesce with a sibling.
    1336             :          */
    1337        1144 :         blk = &state->path.blk[ state->path.active-1 ];
    1338        1144 :         info = blk->bp->b_addr;
    1339        1144 :         node = (xfs_da_intnode_t *)info;
    1340        1144 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
    1341        1144 :         if (nodehdr.count > (state->args->geo->node_ents >> 1)) {
    1342         506 :                 *action = 0;    /* blk over 50%, don't try to join */
    1343         506 :                 return 0;       /* blk over 50%, don't try to join */
    1344             :         }
    1345             : 
    1346             :         /*
    1347             :          * Check for the degenerate case of the block being empty.
    1348             :          * If the block is empty, we'll simply delete it, no need to
    1349             :          * coalesce it with a sibling block.  We choose (arbitrarily)
    1350             :          * to merge with the forward block unless it is NULL.
    1351             :          */
    1352         638 :         if (nodehdr.count == 0) {
    1353             :                 /*
    1354             :                  * Make altpath point to the block we want to keep and
    1355             :                  * path point to the block we want to drop (this one).
    1356             :                  */
    1357           0 :                 forward = (info->forw != 0);
    1358           0 :                 memcpy(&state->altpath, &state->path, sizeof(state->path));
    1359           0 :                 error = xfs_da3_path_shift(state, &state->altpath, forward,
    1360             :                                                  0, &retval);
    1361           0 :                 if (error)
    1362             :                         return error;
    1363           0 :                 if (retval) {
    1364           0 :                         *action = 0;
    1365             :                 } else {
    1366           0 :                         *action = 2;
    1367             :                 }
    1368           0 :                 return 0;
    1369             :         }
    1370             : 
    1371             :         /*
    1372             :          * Examine each sibling block to see if we can coalesce with
    1373             :          * at least 25% free space to spare.  We need to figure out
    1374             :          * whether to merge with the forward or the backward block.
    1375             :          * We prefer coalescing with the lower numbered sibling so as
    1376             :          * to shrink a directory over time.
    1377             :          */
    1378         638 :         count  = state->args->geo->node_ents;
    1379         638 :         count -= state->args->geo->node_ents >> 2;
    1380         638 :         count -= nodehdr.count;
    1381             : 
    1382             :         /* start with smaller blk num */
    1383         638 :         forward = nodehdr.forw < nodehdr.back;
    1384        1909 :         for (i = 0; i < 2; forward = !forward, i++) {
    1385        1276 :                 struct xfs_da3_icnode_hdr thdr;
    1386        1276 :                 if (forward)
    1387             :                         blkno = nodehdr.forw;
    1388             :                 else
    1389         638 :                         blkno = nodehdr.back;
    1390        1276 :                 if (blkno == 0)
    1391         413 :                         continue;
    1392         863 :                 error = xfs_da3_node_read(state->args->trans, dp, blkno, &bp,
    1393             :                                 state->args->whichfork);
    1394         863 :                 if (error)
    1395           0 :                         return error;
    1396         863 :                 fa = xfs_da3_node_header_check(bp, state->args->owner);
    1397         863 :                 if (fa) {
    1398           0 :                         __xfs_buf_mark_corrupt(bp, fa);
    1399           0 :                         xfs_trans_brelse(state->args->trans, bp);
    1400           0 :                         xfs_da_mark_sick(state->args);
    1401           0 :                         return -EFSCORRUPTED;
    1402             :                 }
    1403             : 
    1404         863 :                 node = bp->b_addr;
    1405         863 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &thdr, node);
    1406         863 :                 xfs_trans_brelse(state->args->trans, bp);
    1407             : 
    1408         863 :                 if (count - thdr.count >= 0)
    1409             :                         break;  /* fits with at least 25% to spare */
    1410             :         }
    1411         638 :         if (i >= 2) {
    1412         633 :                 *action = 0;
    1413         633 :                 return 0;
    1414             :         }
    1415             : 
    1416             :         /*
    1417             :          * Make altpath point to the block we want to keep (the lower
    1418             :          * numbered block) and path point to the block we want to drop.
    1419             :          */
    1420          10 :         memcpy(&state->altpath, &state->path, sizeof(state->path));
    1421           5 :         if (blkno < blk->blkno) {
    1422           2 :                 error = xfs_da3_path_shift(state, &state->altpath, forward,
    1423             :                                                  0, &retval);
    1424             :         } else {
    1425           3 :                 error = xfs_da3_path_shift(state, &state->path, forward,
    1426             :                                                  0, &retval);
    1427             :         }
    1428           5 :         if (error)
    1429             :                 return error;
    1430           5 :         if (retval) {
    1431           0 :                 *action = 0;
    1432           0 :                 return 0;
    1433             :         }
    1434           5 :         *action = 1;
    1435           5 :         return 0;
    1436             : }
    1437             : 
    1438             : /*
    1439             :  * Pick up the last hashvalue from an intermediate node.
    1440             :  */
    1441             : STATIC uint
    1442      110356 : xfs_da3_node_lasthash(
    1443             :         struct xfs_inode        *dp,
    1444             :         struct xfs_buf          *bp,
    1445             :         int                     *count)
    1446             : {
    1447      110356 :         struct xfs_da3_icnode_hdr nodehdr;
    1448             : 
    1449      110356 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, bp->b_addr);
    1450      110354 :         if (count)
    1451      110354 :                 *count = nodehdr.count;
    1452      110354 :         if (!nodehdr.count)
    1453             :                 return 0;
    1454      110354 :         return be32_to_cpu(nodehdr.btree[nodehdr.count - 1].hashval);
    1455             : }
    1456             : 
    1457             : /*
    1458             :  * Walk back up the tree adjusting hash values as necessary,
    1459             :  * when we stop making changes, return.
    1460             :  */
    1461             : void
    1462    65267701 : xfs_da3_fixhashpath(
    1463             :         struct xfs_da_state     *state,
    1464             :         struct xfs_da_state_path *path)
    1465             : {
    1466    65267701 :         struct xfs_da_state_blk *blk;
    1467    65267701 :         struct xfs_da_intnode   *node;
    1468    65267701 :         struct xfs_da_node_entry *btree;
    1469    65267701 :         xfs_dahash_t            lasthash=0;
    1470    65267701 :         int                     level;
    1471    65267701 :         int                     count;
    1472    65267701 :         struct xfs_inode        *dp = state->args->dp;
    1473             : 
    1474    65267701 :         trace_xfs_da_fixhashpath(state->args);
    1475             : 
    1476    65271120 :         level = path->active-1;
    1477    65271120 :         blk = &path->blk[ level ];
    1478    65271120 :         switch (blk->magic) {
    1479     2550179 :         case XFS_ATTR_LEAF_MAGIC:
    1480     2550179 :                 lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
    1481     2550179 :                 if (count == 0)
    1482           4 :                         return;
    1483             :                 break;
    1484    62610587 :         case XFS_DIR2_LEAFN_MAGIC:
    1485    62610587 :                 lasthash = xfs_dir2_leaf_lasthash(dp, blk->bp, &count);
    1486    62611861 :                 if (count == 0)
    1487             :                         return;
    1488             :                 break;
    1489      110354 :         case XFS_DA_NODE_MAGIC:
    1490      110354 :                 lasthash = xfs_da3_node_lasthash(dp, blk->bp, &count);
    1491      110354 :                 if (count == 0)
    1492             :                         return;
    1493             :                 break;
    1494             :         }
    1495    67635550 :         for (blk--, level--; level >= 0; blk--, level--) {
    1496    65177615 :                 struct xfs_da3_icnode_hdr nodehdr;
    1497             : 
    1498    65177615 :                 node = blk->bp->b_addr;
    1499    65177615 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
    1500    65176470 :                 btree = nodehdr.btree;
    1501   130352940 :                 if (be32_to_cpu(btree[blk->index].hashval) == lasthash)
    1502             :                         break;
    1503     2363237 :                 blk->hashval = lasthash;
    1504     2363237 :                 btree[blk->index].hashval = cpu_to_be32(lasthash);
    1505     2363237 :                 xfs_trans_log_buf(state->args->trans, blk->bp,
    1506     2363237 :                                   XFS_DA_LOGRANGE(node, &btree[blk->index],
    1507             :                                                   sizeof(*btree)));
    1508             : 
    1509     2363160 :                 lasthash = be32_to_cpu(btree[nodehdr.count - 1].hashval);
    1510             :         }
    1511             : }
    1512             : 
    1513             : /*
    1514             :  * Remove an entry from an intermediate node.
    1515             :  */
    1516             : STATIC void
    1517       22680 : xfs_da3_node_remove(
    1518             :         struct xfs_da_state     *state,
    1519             :         struct xfs_da_state_blk *drop_blk)
    1520             : {
    1521       22680 :         struct xfs_da_intnode   *node;
    1522       22680 :         struct xfs_da3_icnode_hdr nodehdr;
    1523       22680 :         struct xfs_da_node_entry *btree;
    1524       22680 :         int                     index;
    1525       22680 :         int                     tmp;
    1526       22680 :         struct xfs_inode        *dp = state->args->dp;
    1527             : 
    1528       22680 :         trace_xfs_da_node_remove(state->args);
    1529             : 
    1530       22680 :         node = drop_blk->bp->b_addr;
    1531       22680 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
    1532       22680 :         ASSERT(drop_blk->index < nodehdr.count);
    1533       22680 :         ASSERT(drop_blk->index >= 0);
    1534             : 
    1535             :         /*
    1536             :          * Copy over the offending entry, or just zero it out.
    1537             :          */
    1538       22680 :         index = drop_blk->index;
    1539       22680 :         btree = nodehdr.btree;
    1540       22680 :         if (index < nodehdr.count - 1) {
    1541       21996 :                 tmp  = nodehdr.count - index - 1;
    1542       21996 :                 tmp *= (uint)sizeof(xfs_da_node_entry_t);
    1543       43992 :                 memmove(&btree[index], &btree[index + 1], tmp);
    1544       21996 :                 xfs_trans_log_buf(state->args->trans, drop_blk->bp,
    1545       21996 :                     XFS_DA_LOGRANGE(node, &btree[index], tmp));
    1546       21996 :                 index = nodehdr.count - 1;
    1547             :         }
    1548       22680 :         memset(&btree[index], 0, sizeof(xfs_da_node_entry_t));
    1549       22680 :         xfs_trans_log_buf(state->args->trans, drop_blk->bp,
    1550       22680 :             XFS_DA_LOGRANGE(node, &btree[index], sizeof(btree[index])));
    1551       22680 :         nodehdr.count -= 1;
    1552       22680 :         xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
    1553       22680 :         xfs_trans_log_buf(state->args->trans, drop_blk->bp,
    1554       22680 :             XFS_DA_LOGRANGE(node, &node->hdr, state->args->geo->node_hdr_size));
    1555             : 
    1556             :         /*
    1557             :          * Copy the last hash value from the block to propagate upwards.
    1558             :          */
    1559       22680 :         drop_blk->hashval = be32_to_cpu(btree[index - 1].hashval);
    1560       22680 : }
    1561             : 
    1562             : /*
    1563             :  * Unbalance the elements between two intermediate nodes,
    1564             :  * move all Btree elements from one node into another.
    1565             :  */
    1566             : STATIC void
    1567           5 : xfs_da3_node_unbalance(
    1568             :         struct xfs_da_state     *state,
    1569             :         struct xfs_da_state_blk *drop_blk,
    1570             :         struct xfs_da_state_blk *save_blk)
    1571             : {
    1572           5 :         struct xfs_da_intnode   *drop_node;
    1573           5 :         struct xfs_da_intnode   *save_node;
    1574           5 :         struct xfs_da_node_entry *drop_btree;
    1575           5 :         struct xfs_da_node_entry *save_btree;
    1576           5 :         struct xfs_da3_icnode_hdr drop_hdr;
    1577           5 :         struct xfs_da3_icnode_hdr save_hdr;
    1578           5 :         struct xfs_trans        *tp;
    1579           5 :         int                     sindex;
    1580           5 :         int                     tmp;
    1581           5 :         struct xfs_inode        *dp = state->args->dp;
    1582             : 
    1583           5 :         trace_xfs_da_node_unbalance(state->args);
    1584             : 
    1585           5 :         drop_node = drop_blk->bp->b_addr;
    1586           5 :         save_node = save_blk->bp->b_addr;
    1587           5 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &drop_hdr, drop_node);
    1588           5 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &save_hdr, save_node);
    1589           5 :         drop_btree = drop_hdr.btree;
    1590           5 :         save_btree = save_hdr.btree;
    1591           5 :         tp = state->args->trans;
    1592             : 
    1593             :         /*
    1594             :          * If the dying block has lower hashvals, then move all the
    1595             :          * elements in the remaining block up to make a hole.
    1596             :          */
    1597          10 :         if ((be32_to_cpu(drop_btree[0].hashval) <
    1598           9 :                         be32_to_cpu(save_btree[0].hashval)) ||
    1599           4 :             (be32_to_cpu(drop_btree[drop_hdr.count - 1].hashval) <
    1600           4 :                         be32_to_cpu(save_btree[save_hdr.count - 1].hashval))) {
    1601             :                 /* XXX: check this - is memmove dst correct? */
    1602           1 :                 tmp = save_hdr.count * sizeof(xfs_da_node_entry_t);
    1603           2 :                 memmove(&save_btree[drop_hdr.count], &save_btree[0], tmp);
    1604             : 
    1605           1 :                 sindex = 0;
    1606           1 :                 xfs_trans_log_buf(tp, save_blk->bp,
    1607           1 :                         XFS_DA_LOGRANGE(save_node, &save_btree[0],
    1608             :                                 (save_hdr.count + drop_hdr.count) *
    1609             :                                                 sizeof(xfs_da_node_entry_t)));
    1610             :         } else {
    1611           4 :                 sindex = save_hdr.count;
    1612           4 :                 xfs_trans_log_buf(tp, save_blk->bp,
    1613           4 :                         XFS_DA_LOGRANGE(save_node, &save_btree[sindex],
    1614             :                                 drop_hdr.count * sizeof(xfs_da_node_entry_t)));
    1615             :         }
    1616             : 
    1617             :         /*
    1618             :          * Move all the B-tree elements from drop_blk to save_blk.
    1619             :          */
    1620           5 :         tmp = drop_hdr.count * (uint)sizeof(xfs_da_node_entry_t);
    1621          10 :         memcpy(&save_btree[sindex], &drop_btree[0], tmp);
    1622           5 :         save_hdr.count += drop_hdr.count;
    1623             : 
    1624           5 :         xfs_da3_node_hdr_to_disk(dp->i_mount, save_node, &save_hdr);
    1625           5 :         xfs_trans_log_buf(tp, save_blk->bp,
    1626           5 :                 XFS_DA_LOGRANGE(save_node, &save_node->hdr,
    1627             :                                 state->args->geo->node_hdr_size));
    1628             : 
    1629             :         /*
    1630             :          * Save the last hashval in the remaining block for upward propagation.
    1631             :          */
    1632           5 :         save_blk->hashval = be32_to_cpu(save_btree[save_hdr.count - 1].hashval);
    1633           5 : }
    1634             : 
    1635             : /*========================================================================
    1636             :  * Routines used for finding things in the Btree.
    1637             :  *========================================================================*/
    1638             : 
    1639             : /*
    1640             :  * Walk down the Btree looking for a particular filename, filling
    1641             :  * in the state structure as we go.
    1642             :  *
    1643             :  * We will set the state structure to point to each of the elements
    1644             :  * in each of the nodes where either the hashval is or should be.
    1645             :  *
    1646             :  * We support duplicate hashval's so for each entry in the current
    1647             :  * node that could contain the desired hashval, descend.  This is a
    1648             :  * pruned depth-first tree search.
    1649             :  */
    1650             : int                                                     /* error */
    1651   150207509 : xfs_da3_node_lookup_int(
    1652             :         struct xfs_da_state     *state,
    1653             :         int                     *result)
    1654             : {
    1655   150207509 :         struct xfs_da_state_blk *blk;
    1656   150207509 :         struct xfs_da_blkinfo   *curr;
    1657   150207509 :         struct xfs_da_intnode   *node;
    1658   150207509 :         struct xfs_da_node_entry *btree;
    1659   150207509 :         struct xfs_da3_icnode_hdr nodehdr;
    1660   150207509 :         struct xfs_da_args      *args;
    1661   150207509 :         xfs_failaddr_t          fa;
    1662   150207509 :         xfs_dablk_t             blkno;
    1663   150207509 :         xfs_dahash_t            hashval;
    1664   150207509 :         xfs_dahash_t            btreehashval;
    1665   150207509 :         int                     probe;
    1666   150207509 :         int                     span;
    1667   150207509 :         int                     max;
    1668   150207509 :         int                     error;
    1669   150207509 :         int                     retval;
    1670   150207509 :         unsigned int            expected_level = 0;
    1671   150207509 :         uint16_t                magic;
    1672   150207509 :         struct xfs_inode        *dp = state->args->dp;
    1673             : 
    1674   150207509 :         args = state->args;
    1675             : 
    1676             :         /*
    1677             :          * Descend thru the B-tree searching each level for the right
    1678             :          * node to use, until the right hashval is found.
    1679             :          */
    1680   150207509 :         blkno = args->geo->leafblk;
    1681   150207509 :         for (blk = &state->path.blk[0], state->path.active = 1;
    1682   302955263 :                          state->path.active <= XFS_DA_NODE_MAXDEPTH;
    1683   152747754 :                          blk++, state->path.active++) {
    1684             :                 /*
    1685             :                  * Read the next node down in the tree.
    1686             :                  */
    1687   302955263 :                 blk->blkno = blkno;
    1688   302955263 :                 error = xfs_da3_node_read(args->trans, args->dp, blkno,
    1689             :                                         &blk->bp, args->whichfork);
    1690   302965320 :                 if (error) {
    1691       12032 :                         blk->blkno = 0;
    1692       12032 :                         state->path.active--;
    1693       12032 :                         return error;
    1694             :                 }
    1695   302953288 :                 curr = blk->bp->b_addr;
    1696   302953288 :                 magic = be16_to_cpu(curr->magic);
    1697             : 
    1698   302953288 :                 if (magic == XFS_ATTR_LEAF_MAGIC ||
    1699   302953288 :                     magic == XFS_ATTR3_LEAF_MAGIC) {
    1700     6155876 :                         fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);
    1701     6155850 :                         if (fa) {
    1702           0 :                                 __xfs_buf_mark_corrupt(blk->bp, fa);
    1703           0 :                                 xfs_da_mark_sick(args);
    1704           0 :                                 return -EFSCORRUPTED;
    1705             :                         }
    1706     6155850 :                         blk->magic = XFS_ATTR_LEAF_MAGIC;
    1707     6155850 :                         blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
    1708     6155827 :                         break;
    1709             :                 }
    1710             : 
    1711   296797412 :                 if (magic == XFS_DIR2_LEAFN_MAGIC ||
    1712   296797412 :                     magic == XFS_DIR3_LEAFN_MAGIC) {
    1713   144058573 :                         fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);
    1714   144069233 :                         if (fa) {
    1715           0 :                                 __xfs_buf_mark_corrupt(blk->bp, fa);
    1716           0 :                                 xfs_da_mark_sick(args);
    1717           0 :                                 return -EFSCORRUPTED;
    1718             :                         }
    1719   144069233 :                         blk->magic = XFS_DIR2_LEAFN_MAGIC;
    1720   144069233 :                         blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
    1721             :                                                               blk->bp, NULL);
    1722   144064141 :                         break;
    1723             :                 }
    1724             : 
    1725   152738839 :                 if (magic != XFS_DA_NODE_MAGIC && magic != XFS_DA3_NODE_MAGIC) {
    1726           0 :                         xfs_buf_mark_corrupt(blk->bp);
    1727           0 :                         xfs_da_mark_sick(args);
    1728           0 :                         return -EFSCORRUPTED;
    1729             :                 }
    1730             : 
    1731   152738839 :                 fa = xfs_da3_node_header_check(blk->bp, args->owner);
    1732   152746594 :                 if (fa) {
    1733           0 :                         __xfs_buf_mark_corrupt(blk->bp, fa);
    1734           0 :                         xfs_da_mark_sick(args);
    1735           0 :                         return -EFSCORRUPTED;
    1736             :                 }
    1737             : 
    1738   152746594 :                 blk->magic = XFS_DA_NODE_MAGIC;
    1739             : 
    1740             :                 /*
    1741             :                  * Search an intermediate node for a match.
    1742             :                  */
    1743   152746594 :                 node = blk->bp->b_addr;
    1744   152746594 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
    1745   152747754 :                 btree = nodehdr.btree;
    1746             : 
    1747             :                 /* Tree taller than we can handle; bail out! */
    1748   152747754 :                 if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {
    1749           0 :                         xfs_buf_mark_corrupt(blk->bp);
    1750           0 :                         xfs_da_mark_sick(args);
    1751           0 :                         return -EFSCORRUPTED;
    1752             :                 }
    1753             : 
    1754             :                 /* Check the level from the root. */
    1755   152747754 :                 if (blkno == args->geo->leafblk)
    1756   150178251 :                         expected_level = nodehdr.level - 1;
    1757     2572499 :                 else if (expected_level != nodehdr.level) {
    1758           0 :                         xfs_buf_mark_corrupt(blk->bp);
    1759           0 :                         xfs_da_mark_sick(args);
    1760           0 :                         return -EFSCORRUPTED;
    1761             :                 } else
    1762     2572499 :                         expected_level--;
    1763             : 
    1764   152747754 :                 max = nodehdr.count;
    1765   152747754 :                 blk->hashval = be32_to_cpu(btree[max - 1].hashval);
    1766             : 
    1767             :                 /*
    1768             :                  * Binary search.  (note: small blocks will skip loop)
    1769             :                  */
    1770   152747754 :                 probe = span = max / 2;
    1771   152747754 :                 hashval = args->hashval;
    1772   314350386 :                 while (span > 4) {
    1773   161846807 :                         span /= 2;
    1774   161846807 :                         btreehashval = be32_to_cpu(btree[probe].hashval);
    1775   161846807 :                         if (btreehashval < hashval)
    1776    79433265 :                                 probe += span;
    1777    82413542 :                         else if (btreehashval > hashval)
    1778    82169367 :                                 probe -= span;
    1779             :                         else
    1780             :                                 break;
    1781             :                 }
    1782   152747754 :                 ASSERT((probe >= 0) && (probe < max));
    1783   152925699 :                 ASSERT((span <= 4) ||
    1784             :                         (be32_to_cpu(btree[probe].hashval) == hashval));
    1785             : 
    1786             :                 /*
    1787             :                  * Since we may have duplicate hashval's, find the first
    1788             :                  * matching hashval in the node.
    1789             :                  */
    1790   791734153 :                 while (probe > 0 &&
    1791   361240030 :                        be32_to_cpu(btree[probe].hashval) >= hashval) {
    1792   277746369 :                         probe--;
    1793             :                 }
    1794   653224428 :                 while (probe < max &&
    1795   325224259 :                        be32_to_cpu(btree[probe].hashval) < hashval) {
    1796   175252415 :                         probe++;
    1797             :                 }
    1798             : 
    1799             :                 /*
    1800             :                  * Pick the right block to descend on.
    1801             :                  */
    1802   152747754 :                 if (probe == max) {
    1803     2779014 :                         blk->index = max - 1;
    1804     2779014 :                         blkno = be32_to_cpu(btree[max - 1].before);
    1805             :                 } else {
    1806   149968740 :                         blk->index = probe;
    1807   149968740 :                         blkno = be32_to_cpu(btree[probe].before);
    1808             :                 }
    1809             : 
    1810             :                 /* We can't point back to the root. */
    1811   152747754 :                 if (XFS_IS_CORRUPT(dp->i_mount, blkno == args->geo->leafblk)) {
    1812           0 :                         xfs_da_mark_sick(args);
    1813           0 :                         return -EFSCORRUPTED;
    1814             :                 }
    1815             :         }
    1816             : 
    1817   150219968 :         if (XFS_IS_CORRUPT(dp->i_mount, expected_level != 0)) {
    1818           0 :                 xfs_da_mark_sick(args);
    1819           0 :                 return -EFSCORRUPTED;
    1820             :         }
    1821             : 
    1822             :         /*
    1823             :          * A leaf block that ends in the hashval that we are interested in
    1824             :          * (final hashval == search hashval) means that the next block may
    1825             :          * contain more entries with the same hashval, shift upward to the
    1826             :          * next leaf and keep searching.
    1827             :          */
    1828   756577296 :         for (;;) {
    1829   453398632 :                 if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
    1830   145046406 :                         retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
    1831             :                                                         &blk->index, state);
    1832   308352226 :                 } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
    1833   308352226 :                         retval = xfs_attr3_leaf_lookup_int(blk->bp, args);
    1834   308350372 :                         blk->index = args->index;
    1835   308350372 :                         args->blkno = blk->blkno;
    1836             :                 } else {
    1837           0 :                         ASSERT(0);
    1838           0 :                         xfs_da_mark_sick(args);
    1839           0 :                         return -EFSCORRUPTED;
    1840             :                 }
    1841   453377670 :                 if (((retval == -ENOENT) || (retval == -ENOATTR)) &&
    1842   346081875 :                     (blk->hashval == args->hashval)) {
    1843   303464074 :                         error = xfs_da3_path_shift(state, &state->path, 1, 1,
    1844             :                                                          &retval);
    1845   303465770 :                         if (error)
    1846           0 :                                 return error;
    1847   303465770 :                         if (retval == 0) {
    1848   303178664 :                                 continue;
    1849      287106 :                         } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
    1850             :                                 /* path_shift() gives ENOENT */
    1851      136189 :                                 retval = -ENOATTR;
    1852             :                         }
    1853             :                 }
    1854   150217178 :                 break;
    1855             :         }
    1856   150217178 :         *result = retval;
    1857   150217178 :         return 0;
    1858             : }
    1859             : 
    1860             : /*========================================================================
    1861             :  * Utility routines.
    1862             :  *========================================================================*/
    1863             : 
    1864             : /*
    1865             :  * Compare two intermediate nodes for "order".
    1866             :  */
    1867             : STATIC int
    1868          61 : xfs_da3_node_order(
    1869             :         struct xfs_inode *dp,
    1870             :         struct xfs_buf  *node1_bp,
    1871             :         struct xfs_buf  *node2_bp)
    1872             : {
    1873          61 :         struct xfs_da_intnode   *node1;
    1874          61 :         struct xfs_da_intnode   *node2;
    1875          61 :         struct xfs_da_node_entry *btree1;
    1876          61 :         struct xfs_da_node_entry *btree2;
    1877          61 :         struct xfs_da3_icnode_hdr node1hdr;
    1878          61 :         struct xfs_da3_icnode_hdr node2hdr;
    1879             : 
    1880          61 :         node1 = node1_bp->b_addr;
    1881          61 :         node2 = node2_bp->b_addr;
    1882          61 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &node1hdr, node1);
    1883          61 :         xfs_da3_node_hdr_from_disk(dp->i_mount, &node2hdr, node2);
    1884          61 :         btree1 = node1hdr.btree;
    1885          61 :         btree2 = node2hdr.btree;
    1886             : 
    1887         122 :         if (node1hdr.count > 0 && node2hdr.count > 0 &&
    1888         183 :             ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
    1889          61 :              (be32_to_cpu(btree2[node2hdr.count - 1].hashval) <
    1890          61 :               be32_to_cpu(btree1[node1hdr.count - 1].hashval)))) {
    1891           0 :                 return 1;
    1892             :         }
    1893             :         return 0;
    1894             : }
    1895             : 
    1896             : /*
    1897             :  * Link a new block into a doubly linked list of blocks (of whatever type).
    1898             :  */
    1899             : int                                                     /* error */
    1900       89240 : xfs_da3_blk_link(
    1901             :         struct xfs_da_state     *state,
    1902             :         struct xfs_da_state_blk *old_blk,
    1903             :         struct xfs_da_state_blk *new_blk)
    1904             : {
    1905       89240 :         struct xfs_da_blkinfo   *old_info;
    1906       89240 :         struct xfs_da_blkinfo   *new_info;
    1907       89240 :         struct xfs_da_blkinfo   *tmp_info;
    1908       89240 :         struct xfs_da_args      *args;
    1909       89240 :         struct xfs_buf          *bp;
    1910       89240 :         xfs_failaddr_t          fa;
    1911       89240 :         int                     before = 0;
    1912       89240 :         int                     error;
    1913       89240 :         struct xfs_inode        *dp = state->args->dp;
    1914             : 
    1915             :         /*
    1916             :          * Set up environment.
    1917             :          */
    1918       89240 :         args = state->args;
    1919       89240 :         ASSERT(args != NULL);
    1920       89240 :         old_info = old_blk->bp->b_addr;
    1921       89240 :         new_info = new_blk->bp->b_addr;
    1922       89240 :         ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||
    1923             :                old_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
    1924             :                old_blk->magic == XFS_ATTR_LEAF_MAGIC);
    1925             : 
    1926       89240 :         switch (old_blk->magic) {
    1927       60322 :         case XFS_ATTR_LEAF_MAGIC:
    1928       60322 :                 before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
    1929       60322 :                 break;
    1930       28857 :         case XFS_DIR2_LEAFN_MAGIC:
    1931       28857 :                 before = xfs_dir2_leafn_order(dp, old_blk->bp, new_blk->bp);
    1932       28857 :                 break;
    1933          61 :         case XFS_DA_NODE_MAGIC:
    1934          61 :                 before = xfs_da3_node_order(dp, old_blk->bp, new_blk->bp);
    1935          61 :                 break;
    1936             :         }
    1937             : 
    1938             :         /*
    1939             :          * Link blocks in appropriate order.
    1940             :          */
    1941       89240 :         if (before) {
    1942             :                 /*
    1943             :                  * Link new block in before existing block.
    1944             :                  */
    1945           0 :                 trace_xfs_da_link_before(args);
    1946           0 :                 new_info->forw = cpu_to_be32(old_blk->blkno);
    1947           0 :                 new_info->back = old_info->back;
    1948           0 :                 if (old_info->back) {
    1949           0 :                         error = xfs_da3_node_read(args->trans, dp,
    1950           0 :                                                 be32_to_cpu(old_info->back),
    1951             :                                                 &bp, args->whichfork);
    1952           0 :                         if (error)
    1953             :                                 return error;
    1954           0 :                         fa = xfs_da3_header_check(bp, args->owner);
    1955           0 :                         if (fa) {
    1956           0 :                                 __xfs_buf_mark_corrupt(bp, fa);
    1957           0 :                                 xfs_trans_brelse(args->trans, bp);
    1958           0 :                                 xfs_da_mark_sick(args);
    1959           0 :                                 return -EFSCORRUPTED;
    1960             :                         }
    1961           0 :                         ASSERT(bp != NULL);
    1962           0 :                         tmp_info = bp->b_addr;
    1963           0 :                         ASSERT(tmp_info->magic == old_info->magic);
    1964           0 :                         ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);
    1965           0 :                         tmp_info->forw = cpu_to_be32(new_blk->blkno);
    1966           0 :                         xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
    1967             :                 }
    1968           0 :                 old_info->back = cpu_to_be32(new_blk->blkno);
    1969             :         } else {
    1970             :                 /*
    1971             :                  * Link new block in after existing block.
    1972             :                  */
    1973       89240 :                 trace_xfs_da_link_after(args);
    1974       89240 :                 new_info->forw = old_info->forw;
    1975       89240 :                 new_info->back = cpu_to_be32(old_blk->blkno);
    1976       89240 :                 if (old_info->forw) {
    1977       25756 :                         error = xfs_da3_node_read(args->trans, dp,
    1978       25756 :                                                 be32_to_cpu(old_info->forw),
    1979             :                                                 &bp, args->whichfork);
    1980       25756 :                         if (error)
    1981             :                                 return error;
    1982       25756 :                         fa = xfs_da3_header_check(bp, args->owner);
    1983       25756 :                         if (fa) {
    1984           0 :                                 __xfs_buf_mark_corrupt(bp, fa);
    1985           0 :                                 xfs_trans_brelse(args->trans, bp);
    1986           0 :                                 xfs_da_mark_sick(args);
    1987           0 :                                 return -EFSCORRUPTED;
    1988             :                         }
    1989       25756 :                         ASSERT(bp != NULL);
    1990       25756 :                         tmp_info = bp->b_addr;
    1991       25756 :                         ASSERT(tmp_info->magic == old_info->magic);
    1992       51512 :                         ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
    1993       25756 :                         tmp_info->back = cpu_to_be32(new_blk->blkno);
    1994       25756 :                         xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
    1995             :                 }
    1996      178480 :                 old_info->forw = cpu_to_be32(new_blk->blkno);
    1997             :         }
    1998             : 
    1999       89240 :         xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
    2000       89241 :         xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
    2001       89241 :         return 0;
    2002             : }
    2003             : 
    2004             : /*
    2005             :  * Unlink a block from a doubly linked list of blocks.
    2006             :  */
    2007             : STATIC int                                              /* error */
    2008       22680 : xfs_da3_blk_unlink(
    2009             :         struct xfs_da_state     *state,
    2010             :         struct xfs_da_state_blk *drop_blk,
    2011             :         struct xfs_da_state_blk *save_blk)
    2012             : {
    2013       22680 :         struct xfs_da_blkinfo   *drop_info;
    2014       22680 :         struct xfs_da_blkinfo   *save_info;
    2015       22680 :         struct xfs_da_blkinfo   *tmp_info;
    2016       22680 :         struct xfs_da_args      *args;
    2017       22680 :         struct xfs_buf          *bp;
    2018       22680 :         xfs_failaddr_t          fa;
    2019       22680 :         int                     error;
    2020             : 
    2021             :         /*
    2022             :          * Set up environment.
    2023             :          */
    2024       22680 :         args = state->args;
    2025       22680 :         ASSERT(args != NULL);
    2026       22680 :         save_info = save_blk->bp->b_addr;
    2027       22680 :         drop_info = drop_blk->bp->b_addr;
    2028       22680 :         ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||
    2029             :                save_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
    2030             :                save_blk->magic == XFS_ATTR_LEAF_MAGIC);
    2031       22680 :         ASSERT(save_blk->magic == drop_blk->magic);
    2032       48572 :         ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
    2033             :                (be32_to_cpu(save_info->back) == drop_blk->blkno));
    2034       64828 :         ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) ||
    2035             :                (be32_to_cpu(drop_info->back) == save_blk->blkno));
    2036             : 
    2037             :         /*
    2038             :          * Unlink the leaf block from the doubly linked chain of leaves.
    2039             :          */
    2040       45360 :         if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
    2041        3212 :                 trace_xfs_da_unlink_back(args);
    2042        3212 :                 save_info->back = drop_info->back;
    2043        3212 :                 if (drop_info->back) {
    2044        2051 :                         error = xfs_da3_node_read(args->trans, args->dp,
    2045        2051 :                                                 be32_to_cpu(drop_info->back),
    2046             :                                                 &bp, args->whichfork);
    2047        2051 :                         if (error)
    2048             :                                 return error;
    2049        2051 :                         fa = xfs_da3_header_check(bp, args->owner);
    2050        2051 :                         if (fa) {
    2051           0 :                                 __xfs_buf_mark_corrupt(bp, fa);
    2052           0 :                                 xfs_trans_brelse(args->trans, bp);
    2053           0 :                                 xfs_da_mark_sick(args);
    2054           0 :                                 return -EFSCORRUPTED;
    2055             :                         }
    2056        2051 :                         ASSERT(bp != NULL);
    2057        2051 :                         tmp_info = bp->b_addr;
    2058        2051 :                         ASSERT(tmp_info->magic == save_info->magic);
    2059        4102 :                         ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
    2060        2051 :                         tmp_info->forw = cpu_to_be32(save_blk->blkno);
    2061        2051 :                         xfs_trans_log_buf(args->trans, bp, 0,
    2062             :                                                     sizeof(*tmp_info) - 1);
    2063             :                 }
    2064             :         } else {
    2065       19468 :                 trace_xfs_da_unlink_forward(args);
    2066       19468 :                 save_info->forw = drop_info->forw;
    2067       19468 :                 if (drop_info->forw) {
    2068       18787 :                         error = xfs_da3_node_read(args->trans, args->dp,
    2069       18787 :                                                 be32_to_cpu(drop_info->forw),
    2070             :                                                 &bp, args->whichfork);
    2071       18787 :                         if (error)
    2072             :                                 return error;
    2073       18787 :                         fa = xfs_da3_header_check(bp, args->owner);
    2074       18787 :                         if (fa) {
    2075           0 :                                 __xfs_buf_mark_corrupt(bp, fa);
    2076           0 :                                 xfs_trans_brelse(args->trans, bp);
    2077           0 :                                 xfs_da_mark_sick(args);
    2078           0 :                                 return -EFSCORRUPTED;
    2079             :                         }
    2080       18787 :                         ASSERT(bp != NULL);
    2081       18787 :                         tmp_info = bp->b_addr;
    2082       18787 :                         ASSERT(tmp_info->magic == save_info->magic);
    2083       37574 :                         ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
    2084       18787 :                         tmp_info->back = cpu_to_be32(save_blk->blkno);
    2085       18787 :                         xfs_trans_log_buf(args->trans, bp, 0,
    2086             :                                                     sizeof(*tmp_info) - 1);
    2087             :                 }
    2088             :         }
    2089             : 
    2090       22680 :         xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
    2091       22680 :         return 0;
    2092             : }
    2093             : 
    2094             : /*
    2095             :  * Move a path "forward" or "!forward" one block at the current level.
    2096             :  *
    2097             :  * This routine will adjust a "path" to point to the next block
    2098             :  * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
    2099             :  * Btree, including updating pointers to the intermediate nodes between
    2100             :  * the new bottom and the root.
    2101             :  */
    2102             : int                                                     /* error */
    2103   304004403 : xfs_da3_path_shift(
    2104             :         struct xfs_da_state     *state,
    2105             :         struct xfs_da_state_path *path,
    2106             :         int                     forward,
    2107             :         int                     release,
    2108             :         int                     *result)
    2109             : {
    2110   304004403 :         struct xfs_da_state_blk *blk;
    2111   304004403 :         struct xfs_da_blkinfo   *info;
    2112   304004403 :         struct xfs_da_args      *args;
    2113   304004403 :         struct xfs_da_node_entry *btree;
    2114   304004403 :         struct xfs_da3_icnode_hdr nodehdr;
    2115   304004403 :         struct xfs_buf          *bp;
    2116   304004403 :         xfs_failaddr_t          fa;
    2117   304004403 :         xfs_dablk_t             blkno = 0;
    2118   304004403 :         int                     level;
    2119   304004403 :         int                     error;
    2120   304004403 :         struct xfs_inode        *dp = state->args->dp;
    2121             : 
    2122   304004403 :         trace_xfs_da_path_shift(state->args);
    2123             : 
    2124             :         /*
    2125             :          * Roll up the Btree looking for the first block where our
    2126             :          * current index is not at the edge of the block.  Note that
    2127             :          * we skip the bottom layer because we want the sibling block.
    2128             :          */
    2129   304004403 :         args = state->args;
    2130   304004403 :         ASSERT(args != NULL);
    2131   304004403 :         ASSERT(path != NULL);
    2132   304004403 :         ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
    2133   304004403 :         level = (path->active-1) - 1;        /* skip bottom layer in path */
    2134   304904151 :         for (; level >= 0; level--) {
    2135   304539469 :                 blk = &path->blk[level];
    2136   304539469 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
    2137   304539469 :                                            blk->bp->b_addr);
    2138             : 
    2139   304539471 :                 if (forward && (blk->index < nodehdr.count - 1)) {
    2140   303413497 :                         blk->index++;
    2141   303413497 :                         blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
    2142             :                         break;
    2143     1125974 :                 } else if (!forward && (blk->index > 0)) {
    2144      226226 :                         blk->index--;
    2145      226226 :                         blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
    2146             :                         break;
    2147             :                 }
    2148             :         }
    2149   304004405 :         if (level < 0) {
    2150      364682 :                 *result = -ENOENT;      /* we're out of our tree */
    2151      364682 :                 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
    2152      364682 :                 return 0;
    2153             :         }
    2154             : 
    2155             :         /*
    2156             :          * Roll down the edge of the subtree until we reach the
    2157             :          * same depth we were at originally.
    2158             :          */
    2159   607716050 :         for (blk++, level++; level < path->active; blk++, level++) {
    2160             :                 /*
    2161             :                  * Read the next child block into a local buffer.
    2162             :                  */
    2163   304076328 :                 error = xfs_da3_node_read(args->trans, dp, blkno, &bp,
    2164             :                                           args->whichfork);
    2165   304076327 :                 if (error)
    2166           0 :                         return error;
    2167             : 
    2168             :                 /*
    2169             :                  * Release the old block (if it's dirty, the trans doesn't
    2170             :                  * actually let go) and swap the local buffer into the path
    2171             :                  * structure. This ensures failure of the above read doesn't set
    2172             :                  * a NULL buffer in an active slot in the path.
    2173             :                  */
    2174   304076327 :                 if (release)
    2175   303615205 :                         xfs_trans_brelse(args->trans, blk->bp);
    2176   304076327 :                 blk->blkno = blkno;
    2177   304076327 :                 blk->bp = bp;
    2178             : 
    2179   304076327 :                 info = blk->bp->b_addr;
    2180   304076327 :                 ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
    2181             :                        info->magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
    2182             :                        info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
    2183             :                        info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
    2184             :                        info->magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
    2185             :                        info->magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
    2186             : 
    2187             : 
    2188             :                 /*
    2189             :                  * Note: we flatten the magic number to a single type so we
    2190             :                  * don't have to compare against crc/non-crc types elsewhere.
    2191             :                  */
    2192   304076327 :                 switch (be16_to_cpu(info->magic)) {
    2193      436674 :                 case XFS_DA_NODE_MAGIC:
    2194             :                 case XFS_DA3_NODE_MAGIC:
    2195      436674 :                         fa = xfs_da3_node_header_check(blk->bp, args->owner);
    2196      436674 :                         if (fa) {
    2197           0 :                                 __xfs_buf_mark_corrupt(blk->bp, fa);
    2198           0 :                                 xfs_da_mark_sick(args);
    2199           0 :                                 return -EFSCORRUPTED;
    2200             :                         }
    2201      436674 :                         blk->magic = XFS_DA_NODE_MAGIC;
    2202      436674 :                         xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
    2203      436674 :                                                    bp->b_addr);
    2204      436674 :                         btree = nodehdr.btree;
    2205      436674 :                         blk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
    2206      436674 :                         if (forward)
    2207      436609 :                                 blk->index = 0;
    2208             :                         else
    2209          65 :                                 blk->index = nodehdr.count - 1;
    2210      436674 :                         blkno = be32_to_cpu(btree[blk->index].before);
    2211             :                         break;
    2212   302293944 :                 case XFS_ATTR_LEAF_MAGIC:
    2213             :                 case XFS_ATTR3_LEAF_MAGIC:
    2214   302293944 :                         fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);
    2215   302293944 :                         if (fa) {
    2216           0 :                                 __xfs_buf_mark_corrupt(blk->bp, fa);
    2217           0 :                                 xfs_da_mark_sick(args);
    2218           0 :                                 return -EFSCORRUPTED;
    2219             :                         }
    2220   302293944 :                         blk->magic = XFS_ATTR_LEAF_MAGIC;
    2221   302293944 :                         ASSERT(level == path->active-1);
    2222   302293944 :                         blk->index = 0;
    2223   302293944 :                         blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
    2224   302293944 :                         break;
    2225     1345709 :                 case XFS_DIR2_LEAFN_MAGIC:
    2226             :                 case XFS_DIR3_LEAFN_MAGIC:
    2227     1345709 :                         fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);
    2228     1345710 :                         if (fa) {
    2229           0 :                                 __xfs_buf_mark_corrupt(blk->bp, fa);
    2230           0 :                                 xfs_da_mark_sick(args);
    2231           0 :                                 return -EFSCORRUPTED;
    2232             :                         }
    2233     1345710 :                         blk->magic = XFS_DIR2_LEAFN_MAGIC;
    2234     1345710 :                         ASSERT(level == path->active-1);
    2235     1345710 :                         blk->index = 0;
    2236     1345710 :                         blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
    2237             :                                                               blk->bp, NULL);
    2238     1345709 :                         break;
    2239           0 :                 default:
    2240           0 :                         ASSERT(0);
    2241           0 :                         break;
    2242             :                 }
    2243             :         }
    2244   303639722 :         *result = 0;
    2245   303639722 :         return 0;
    2246             : }
    2247             : 
    2248             : 
    2249             : /*========================================================================
    2250             :  * Utility routines.
    2251             :  *========================================================================*/
    2252             : 
    2253             : /*
    2254             :  * Implement a simple hash on a character string.
    2255             :  * Rotate the hash value by 7 bits, then XOR each character in.
    2256             :  * This is implemented with some source-level loop unrolling.
    2257             :  */
    2258             : xfs_dahash_t
    2259  3514221458 : xfs_da_hashname(const uint8_t *name, int namelen)
    2260             : {
    2261  3514221458 :         xfs_dahash_t hash;
    2262             : 
    2263             :         /*
    2264             :          * Do four characters at a time as long as we can.
    2265             :          */
    2266  7924427435 :         for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
    2267  4410205977 :                 hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
    2268  4410205977 :                        (name[3] << 0) ^ rol32(hash, 7 * 4);
    2269             : 
    2270             :         /*
    2271             :          * Now do the rest of the characters.
    2272             :          */
    2273  3514221458 :         switch (namelen) {
    2274   486115098 :         case 3:
    2275   486115098 :                 return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
    2276             :                        rol32(hash, 7 * 3);
    2277   877091554 :         case 2:
    2278   877091554 :                 return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
    2279  1259064606 :         case 1:
    2280  1259064606 :                 return (name[0] << 0) ^ rol32(hash, 7 * 1);
    2281             :         default: /* case 0: */
    2282             :                 return hash;
    2283             :         }
    2284             : }
    2285             : 
    2286             : enum xfs_dacmp
    2287  1460864479 : xfs_da_compname(
    2288             :         struct xfs_da_args *args,
    2289             :         const unsigned char *name,
    2290             :         int             len)
    2291             : {
    2292  1327039944 :         return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
    2293  2787904423 :                                         XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
    2294             : }
    2295             : 
    2296             : int
    2297     4750506 : xfs_da_grow_inode_int(
    2298             :         struct xfs_da_args      *args,
    2299             :         xfs_fileoff_t           *bno,
    2300             :         int                     count)
    2301             : {
    2302     4750506 :         struct xfs_trans        *tp = args->trans;
    2303     4750506 :         struct xfs_inode        *dp = args->dp;
    2304     4750506 :         int                     w = args->whichfork;
    2305     4750506 :         xfs_rfsblock_t          nblks = dp->i_nblocks;
    2306     4750506 :         struct xfs_bmbt_irec    map, *mapp;
    2307     4750506 :         int                     nmap, error, got, i, mapi;
    2308             : 
    2309             :         /*
    2310             :          * Find a spot in the file space to put the new block.
    2311             :          */
    2312     4750506 :         error = xfs_bmap_first_unused(tp, dp, count, bno, w);
    2313     4750518 :         if (error)
    2314             :                 return error;
    2315             : 
    2316             :         /*
    2317             :          * Try mapping it in one filesystem block.
    2318             :          */
    2319     4750518 :         nmap = 1;
    2320     4750518 :         error = xfs_bmapi_write(tp, dp, *bno, count,
    2321     4750518 :                         xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
    2322             :                         args->total, &map, &nmap);
    2323     4749536 :         if (error)
    2324             :                 return error;
    2325             : 
    2326     4749532 :         ASSERT(nmap <= 1);
    2327     4749532 :         if (nmap == 1) {
    2328             :                 mapp = &map;
    2329             :                 mapi = 1;
    2330          40 :         } else if (nmap == 0 && count > 1) {
    2331          40 :                 xfs_fileoff_t           b;
    2332          40 :                 int                     c;
    2333             : 
    2334             :                 /*
    2335             :                  * If we didn't get it and the block might work if fragmented,
    2336             :                  * try without the CONTIG flag.  Loop until we get it all.
    2337             :                  */
    2338          40 :                 mapp = kmem_alloc(sizeof(*mapp) * count, 0);
    2339          80 :                 for (b = *bno, mapi = 0; b < *bno + count; ) {
    2340          40 :                         c = (int)(*bno + count - b);
    2341          40 :                         nmap = min(XFS_BMAP_MAX_NMAP, c);
    2342          40 :                         error = xfs_bmapi_write(tp, dp, b, c,
    2343          40 :                                         xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
    2344          40 :                                         args->total, &mapp[mapi], &nmap);
    2345          40 :                         if (error)
    2346           0 :                                 goto out_free_map;
    2347          40 :                         if (nmap < 1)
    2348             :                                 break;
    2349          40 :                         mapi += nmap;
    2350          40 :                         b = mapp[mapi - 1].br_startoff +
    2351          40 :                             mapp[mapi - 1].br_blockcount;
    2352             :                 }
    2353             :         } else {
    2354             :                 mapi = 0;
    2355             :                 mapp = NULL;
    2356             :         }
    2357             : 
    2358             :         /*
    2359             :          * Count the blocks we got, make sure it matches the total.
    2360             :          */
    2361     9499797 :         for (i = 0, got = 0; i < mapi; i++)
    2362     4750265 :                 got += mapp[i].br_blockcount;
    2363     4749532 :         if (got != count || mapp[0].br_startoff != *bno ||
    2364     4749905 :             mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
    2365     4749905 :             *bno + count) {
    2366           0 :                 error = -ENOSPC;
    2367           0 :                 goto out_free_map;
    2368             :         }
    2369             : 
    2370             :         /* account for newly allocated blocks in reserved blocks total */
    2371     4749895 :         args->total -= dp->i_nblocks - nblks;
    2372             : 
    2373     4749532 : out_free_map:
    2374     4749532 :         if (mapp != &map)
    2375          40 :                 kmem_free(mapp);
    2376             :         return error;
    2377             : }
    2378             : 
    2379             : /*
    2380             :  * Add a block to the btree ahead of the file.
    2381             :  * Return the new block number to the caller.
    2382             :  */
    2383             : int
    2384     4397486 : xfs_da_grow_inode(
    2385             :         struct xfs_da_args      *args,
    2386             :         xfs_dablk_t             *new_blkno)
    2387             : {
    2388     4397486 :         xfs_fileoff_t           bno;
    2389     4397486 :         int                     error;
    2390             : 
    2391     4397486 :         trace_xfs_da_grow_inode(args);
    2392             : 
    2393     4397588 :         bno = args->geo->leafblk;
    2394     4397588 :         error = xfs_da_grow_inode_int(args, &bno, args->geo->fsbcount);
    2395     4397019 :         if (!error)
    2396     4397017 :                 *new_blkno = (xfs_dablk_t)bno;
    2397     4397019 :         return error;
    2398             : }
    2399             : 
    2400             : /*
    2401             :  * Ick.  We need to always be able to remove a btree block, even
    2402             :  * if there's no space reservation because the filesystem is full.
    2403             :  * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
    2404             :  * It swaps the target block with the last block in the file.  The
    2405             :  * last block in the file can always be removed since it can't cause
    2406             :  * a bmap btree split to do that.
    2407             :  */
    2408             : STATIC int
    2409           0 : xfs_da3_swap_lastblock(
    2410             :         struct xfs_da_args      *args,
    2411             :         xfs_dablk_t             *dead_blknop,
    2412             :         struct xfs_buf          **dead_bufp)
    2413           0 : {
    2414           0 :         struct xfs_da_blkinfo   *dead_info;
    2415           0 :         struct xfs_da_blkinfo   *sib_info;
    2416           0 :         struct xfs_da_intnode   *par_node;
    2417           0 :         struct xfs_da_intnode   *dead_node;
    2418           0 :         struct xfs_dir2_leaf    *dead_leaf2;
    2419           0 :         struct xfs_da_node_entry *btree;
    2420           0 :         struct xfs_da3_icnode_hdr par_hdr;
    2421           0 :         struct xfs_inode        *dp;
    2422           0 :         struct xfs_trans        *tp;
    2423           0 :         struct xfs_mount        *mp;
    2424           0 :         struct xfs_buf          *dead_buf;
    2425           0 :         struct xfs_buf          *last_buf;
    2426           0 :         struct xfs_buf          *sib_buf;
    2427           0 :         struct xfs_buf          *par_buf;
    2428           0 :         xfs_failaddr_t          fa;
    2429           0 :         xfs_dahash_t            dead_hash;
    2430           0 :         xfs_fileoff_t           lastoff;
    2431           0 :         xfs_dablk_t             dead_blkno;
    2432           0 :         xfs_dablk_t             last_blkno;
    2433           0 :         xfs_dablk_t             sib_blkno;
    2434           0 :         xfs_dablk_t             par_blkno;
    2435           0 :         int                     error;
    2436           0 :         int                     w;
    2437           0 :         int                     entno;
    2438           0 :         int                     level;
    2439           0 :         int                     dead_level;
    2440             : 
    2441           0 :         trace_xfs_da_swap_lastblock(args);
    2442             : 
    2443           0 :         dead_buf = *dead_bufp;
    2444           0 :         dead_blkno = *dead_blknop;
    2445           0 :         tp = args->trans;
    2446           0 :         dp = args->dp;
    2447           0 :         w = args->whichfork;
    2448           0 :         ASSERT(w == XFS_DATA_FORK);
    2449           0 :         mp = dp->i_mount;
    2450           0 :         lastoff = args->geo->freeblk;
    2451           0 :         error = xfs_bmap_last_before(tp, dp, &lastoff, w);
    2452           0 :         if (error)
    2453             :                 return error;
    2454           0 :         if (XFS_IS_CORRUPT(mp, lastoff == 0)) {
    2455           0 :                 xfs_da_mark_sick(args);
    2456           0 :                 return -EFSCORRUPTED;
    2457             :         }
    2458             :         /*
    2459             :          * Read the last block in the btree space.
    2460             :          */
    2461           0 :         last_blkno = (xfs_dablk_t)lastoff - args->geo->fsbcount;
    2462           0 :         error = xfs_da3_node_read(tp, dp, last_blkno, &last_buf, w);
    2463           0 :         if (error)
    2464             :                 return error;
    2465           0 :         fa = xfs_da3_header_check(last_buf, args->owner);
    2466           0 :         if (fa) {
    2467           0 :                 __xfs_buf_mark_corrupt(last_buf, fa);
    2468           0 :                 xfs_trans_brelse(tp, last_buf);
    2469           0 :                 xfs_da_mark_sick(args);
    2470           0 :                 return -EFSCORRUPTED;
    2471             :         }
    2472             : 
    2473             :         /*
    2474             :          * Copy the last block into the dead buffer and log it.
    2475             :          */
    2476           0 :         memcpy(dead_buf->b_addr, last_buf->b_addr, args->geo->blksize);
    2477           0 :         xfs_trans_log_buf(tp, dead_buf, 0, args->geo->blksize - 1);
    2478           0 :         dead_info = dead_buf->b_addr;
    2479             :         /*
    2480             :          * Get values from the moved block.
    2481             :          */
    2482           0 :         if (dead_info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
    2483             :             dead_info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
    2484           0 :                 struct xfs_dir3_icleaf_hdr leafhdr;
    2485           0 :                 struct xfs_dir2_leaf_entry *ents;
    2486             : 
    2487           0 :                 dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;
    2488           0 :                 xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr,
    2489             :                                             dead_leaf2);
    2490           0 :                 ents = leafhdr.ents;
    2491           0 :                 dead_level = 0;
    2492           0 :                 dead_hash = be32_to_cpu(ents[leafhdr.count - 1].hashval);
    2493             :         } else {
    2494           0 :                 struct xfs_da3_icnode_hdr deadhdr;
    2495             : 
    2496           0 :                 dead_node = (xfs_da_intnode_t *)dead_info;
    2497           0 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &deadhdr, dead_node);
    2498           0 :                 btree = deadhdr.btree;
    2499           0 :                 dead_level = deadhdr.level;
    2500           0 :                 dead_hash = be32_to_cpu(btree[deadhdr.count - 1].hashval);
    2501             :         }
    2502           0 :         sib_buf = par_buf = NULL;
    2503             :         /*
    2504             :          * If the moved block has a left sibling, fix up the pointers.
    2505             :          */
    2506           0 :         if ((sib_blkno = be32_to_cpu(dead_info->back))) {
    2507           0 :                 error = xfs_da3_node_read(tp, dp, sib_blkno, &sib_buf, w);
    2508           0 :                 if (error)
    2509           0 :                         goto done;
    2510           0 :                 fa = xfs_da3_header_check(sib_buf, args->owner);
    2511           0 :                 if (fa) {
    2512           0 :                         __xfs_buf_mark_corrupt(sib_buf, fa);
    2513           0 :                         xfs_da_mark_sick(args);
    2514           0 :                         error = -EFSCORRUPTED;
    2515           0 :                         goto done;
    2516             :                 }
    2517           0 :                 sib_info = sib_buf->b_addr;
    2518           0 :                 if (XFS_IS_CORRUPT(mp,
    2519             :                                    be32_to_cpu(sib_info->forw) != last_blkno ||
    2520             :                                    sib_info->magic != dead_info->magic)) {
    2521           0 :                         xfs_da_mark_sick(args);
    2522           0 :                         error = -EFSCORRUPTED;
    2523           0 :                         goto done;
    2524             :                 }
    2525           0 :                 sib_info->forw = cpu_to_be32(dead_blkno);
    2526           0 :                 xfs_trans_log_buf(tp, sib_buf,
    2527             :                         XFS_DA_LOGRANGE(sib_info, &sib_info->forw,
    2528             :                                         sizeof(sib_info->forw)));
    2529           0 :                 sib_buf = NULL;
    2530             :         }
    2531             :         /*
    2532             :          * If the moved block has a right sibling, fix up the pointers.
    2533             :          */
    2534           0 :         if ((sib_blkno = be32_to_cpu(dead_info->forw))) {
    2535           0 :                 error = xfs_da3_node_read(tp, dp, sib_blkno, &sib_buf, w);
    2536           0 :                 if (error)
    2537           0 :                         goto done;
    2538           0 :                 fa = xfs_da3_header_check(sib_buf, args->owner);
    2539           0 :                 if (fa) {
    2540           0 :                         __xfs_buf_mark_corrupt(sib_buf, fa);
    2541           0 :                         xfs_da_mark_sick(args);
    2542           0 :                         error = -EFSCORRUPTED;
    2543           0 :                         goto done;
    2544             :                 }
    2545           0 :                 sib_info = sib_buf->b_addr;
    2546           0 :                 if (XFS_IS_CORRUPT(mp,
    2547             :                                    be32_to_cpu(sib_info->back) != last_blkno ||
    2548             :                                    sib_info->magic != dead_info->magic)) {
    2549           0 :                         xfs_da_mark_sick(args);
    2550           0 :                         error = -EFSCORRUPTED;
    2551           0 :                         goto done;
    2552             :                 }
    2553           0 :                 sib_info->back = cpu_to_be32(dead_blkno);
    2554           0 :                 xfs_trans_log_buf(tp, sib_buf,
    2555             :                         XFS_DA_LOGRANGE(sib_info, &sib_info->back,
    2556             :                                         sizeof(sib_info->back)));
    2557           0 :                 sib_buf = NULL;
    2558             :         }
    2559           0 :         par_blkno = args->geo->leafblk;
    2560           0 :         level = -1;
    2561             :         /*
    2562             :          * Walk down the tree looking for the parent of the moved block.
    2563             :          */
    2564           0 :         for (;;) {
    2565           0 :                 error = xfs_da3_node_read(tp, dp, par_blkno, &par_buf, w);
    2566           0 :                 if (error)
    2567           0 :                         goto done;
    2568           0 :                 fa = xfs_da3_node_header_check(par_buf, args->owner);
    2569           0 :                 if (fa) {
    2570           0 :                         __xfs_buf_mark_corrupt(par_buf, fa);
    2571           0 :                         xfs_da_mark_sick(args);
    2572           0 :                         error = -EFSCORRUPTED;
    2573           0 :                         goto done;
    2574             :                 }
    2575           0 :                 par_node = par_buf->b_addr;
    2576           0 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &par_hdr, par_node);
    2577           0 :                 if (XFS_IS_CORRUPT(mp,
    2578             :                                    level >= 0 && level != par_hdr.level + 1)) {
    2579           0 :                         xfs_da_mark_sick(args);
    2580           0 :                         error = -EFSCORRUPTED;
    2581           0 :                         goto done;
    2582             :                 }
    2583           0 :                 level = par_hdr.level;
    2584           0 :                 btree = par_hdr.btree;
    2585           0 :                 for (entno = 0;
    2586           0 :                      entno < par_hdr.count &&
    2587           0 :                      be32_to_cpu(btree[entno].hashval) < dead_hash;
    2588           0 :                      entno++)
    2589           0 :                         continue;
    2590           0 :                 if (XFS_IS_CORRUPT(mp, entno == par_hdr.count)) {
    2591           0 :                         xfs_da_mark_sick(args);
    2592           0 :                         error = -EFSCORRUPTED;
    2593           0 :                         goto done;
    2594             :                 }
    2595           0 :                 par_blkno = be32_to_cpu(btree[entno].before);
    2596           0 :                 if (level == dead_level + 1)
    2597             :                         break;
    2598           0 :                 xfs_trans_brelse(tp, par_buf);
    2599           0 :                 par_buf = NULL;
    2600             :         }
    2601             :         /*
    2602             :          * We're in the right parent block.
    2603             :          * Look for the right entry.
    2604             :          */
    2605           0 :         for (;;) {
    2606           0 :                 for (;
    2607           0 :                      entno < par_hdr.count &&
    2608           0 :                      be32_to_cpu(btree[entno].before) != last_blkno;
    2609           0 :                      entno++)
    2610           0 :                         continue;
    2611           0 :                 if (entno < par_hdr.count)
    2612             :                         break;
    2613           0 :                 par_blkno = par_hdr.forw;
    2614           0 :                 xfs_trans_brelse(tp, par_buf);
    2615           0 :                 par_buf = NULL;
    2616           0 :                 if (XFS_IS_CORRUPT(mp, par_blkno == 0)) {
    2617           0 :                         xfs_da_mark_sick(args);
    2618           0 :                         error = -EFSCORRUPTED;
    2619           0 :                         goto done;
    2620             :                 }
    2621           0 :                 error = xfs_da3_node_read(tp, dp, par_blkno, &par_buf, w);
    2622           0 :                 if (error)
    2623           0 :                         goto done;
    2624           0 :                 fa = xfs_da3_node_header_check(par_buf, args->owner);
    2625           0 :                 if (fa) {
    2626           0 :                         __xfs_buf_mark_corrupt(par_buf, fa);
    2627           0 :                         xfs_da_mark_sick(args);
    2628           0 :                         error = -EFSCORRUPTED;
    2629           0 :                         goto done;
    2630             :                 }
    2631           0 :                 par_node = par_buf->b_addr;
    2632           0 :                 xfs_da3_node_hdr_from_disk(dp->i_mount, &par_hdr, par_node);
    2633           0 :                 if (XFS_IS_CORRUPT(mp, par_hdr.level != level)) {
    2634           0 :                         xfs_da_mark_sick(args);
    2635           0 :                         error = -EFSCORRUPTED;
    2636           0 :                         goto done;
    2637             :                 }
    2638           0 :                 btree = par_hdr.btree;
    2639           0 :                 entno = 0;
    2640             :         }
    2641             :         /*
    2642             :          * Update the parent entry pointing to the moved block.
    2643             :          */
    2644           0 :         btree[entno].before = cpu_to_be32(dead_blkno);
    2645           0 :         xfs_trans_log_buf(tp, par_buf,
    2646           0 :                 XFS_DA_LOGRANGE(par_node, &btree[entno].before,
    2647             :                                 sizeof(btree[entno].before)));
    2648           0 :         *dead_blknop = last_blkno;
    2649           0 :         *dead_bufp = last_buf;
    2650           0 :         return 0;
    2651           0 : done:
    2652           0 :         if (par_buf)
    2653           0 :                 xfs_trans_brelse(tp, par_buf);
    2654           0 :         if (sib_buf)
    2655           0 :                 xfs_trans_brelse(tp, sib_buf);
    2656           0 :         xfs_trans_brelse(tp, last_buf);
    2657           0 :         return error;
    2658             : }
    2659             : 
    2660             : /*
    2661             :  * Remove a btree block from a directory or attribute.
    2662             :  */
    2663             : int
    2664     2271173 : xfs_da_shrink_inode(
    2665             :         struct xfs_da_args      *args,
    2666             :         xfs_dablk_t             dead_blkno,
    2667             :         struct xfs_buf          *dead_buf)
    2668             : {
    2669     2271173 :         struct xfs_inode        *dp;
    2670     2271173 :         int                     done, error, w, count;
    2671     2271173 :         struct xfs_trans        *tp;
    2672             : 
    2673     2271173 :         trace_xfs_da_shrink_inode(args);
    2674             : 
    2675     2271207 :         dp = args->dp;
    2676     2271207 :         w = args->whichfork;
    2677     2271207 :         tp = args->trans;
    2678     2271207 :         count = args->geo->fsbcount;
    2679     2271207 :         for (;;) {
    2680             :                 /*
    2681             :                  * Remove extents.  If we get ENOSPC for a dir we have to move
    2682             :                  * the last block to the place we want to kill.
    2683             :                  */
    2684     2298328 :                 error = xfs_bunmapi(tp, dp, dead_blkno, count,
    2685             :                                     xfs_bmapi_aflag(w), 0, &done);
    2686     2271159 :                 if (error == -ENOSPC) {
    2687           0 :                         if (w != XFS_DATA_FORK)
    2688             :                                 break;
    2689           0 :                         error = xfs_da3_swap_lastblock(args, &dead_blkno,
    2690             :                                                       &dead_buf);
    2691           0 :                         if (error)
    2692             :                                 break;
    2693             :                 } else {
    2694             :                         break;
    2695             :                 }
    2696             :         }
    2697     2271159 :         xfs_trans_binval(tp, dead_buf);
    2698     2271189 :         return error;
    2699             : }
    2700             : 
    2701             : static int
    2702  1848584285 : xfs_dabuf_map(
    2703             :         struct xfs_inode        *dp,
    2704             :         xfs_dablk_t             bno,
    2705             :         unsigned int            flags,
    2706             :         int                     whichfork,
    2707             :         struct xfs_buf_map      **mapp,
    2708             :         int                     *nmaps)
    2709             : {
    2710  1848584285 :         struct xfs_mount        *mp = dp->i_mount;
    2711  1848584285 :         int                     nfsb = xfs_dabuf_nfsb(mp, whichfork);
    2712  1848584285 :         struct xfs_bmbt_irec    irec, *irecs = &irec;
    2713  1848584285 :         struct xfs_buf_map      *map = *mapp;
    2714  1848584285 :         xfs_fileoff_t           off = bno;
    2715  1848584285 :         int                     error = 0, nirecs, i;
    2716             : 
    2717  1848584285 :         if (nfsb > 1)
    2718      647072 :                 irecs = kmem_zalloc(sizeof(irec) * nfsb, KM_NOFS);
    2719             : 
    2720  1848966092 :         nirecs = nfsb;
    2721  2747679724 :         error = xfs_bmapi_read(dp, bno, nfsb, irecs, &nirecs,
    2722             :                         xfs_bmapi_aflag(whichfork));
    2723  1849654439 :         if (error)
    2724         170 :                 goto out_free_irecs;
    2725             : 
    2726             :         /*
    2727             :          * Use the caller provided map for the single map case, else allocate a
    2728             :          * larger one that needs to be free by the caller.
    2729             :          */
    2730  1849654269 :         if (nirecs > 1) {
    2731       68748 :                 map = kmem_zalloc(nirecs * sizeof(struct xfs_buf_map), KM_NOFS);
    2732       68748 :                 if (!map) {
    2733           0 :                         error = -ENOMEM;
    2734           0 :                         goto out_free_irecs;
    2735             :                 }
    2736       68748 :                 *mapp = map;
    2737             :         }
    2738             : 
    2739  3698854908 :         for (i = 0; i < nirecs; i++) {
    2740  1849471457 :                 if (irecs[i].br_startblock == HOLESTARTBLOCK ||
    2741             :                     irecs[i].br_startblock == DELAYSTARTBLOCK)
    2742      270818 :                         goto invalid_mapping;
    2743  1849200639 :                 if (off != irecs[i].br_startoff)
    2744           0 :                         goto invalid_mapping;
    2745             : 
    2746  1849200639 :                 map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);
    2747  1849200639 :                 map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);
    2748  1849200639 :                 off += irecs[i].br_blockcount;
    2749             :         }
    2750             : 
    2751  1849383451 :         if (off != bno + nfsb)
    2752           0 :                 goto invalid_mapping;
    2753             : 
    2754  1849383451 :         *nmaps = nirecs;
    2755  1849654439 : out_free_irecs:
    2756  1849654439 :         if (irecs != &irec)
    2757      647072 :                 kmem_free(irecs);
    2758  1849654439 :         return error;
    2759             : 
    2760      270818 : invalid_mapping:
    2761             :         /* Caller ok with no mapping. */
    2762      270818 :         if (XFS_IS_CORRUPT(mp, !(flags & XFS_DABUF_MAP_HOLE_OK))) {
    2763           0 :                 xfs_dirattr_mark_sick(dp, whichfork);
    2764           0 :                 error = -EFSCORRUPTED;
    2765           0 :                 if (xfs_error_level >= XFS_ERRLEVEL_LOW) {
    2766           0 :                         xfs_alert(mp, "%s: bno %u inode %llu",
    2767             :                                         __func__, bno, dp->i_ino);
    2768             : 
    2769           0 :                         for (i = 0; i < nirecs; i++) {
    2770           0 :                                 xfs_alert(mp,
    2771             : "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
    2772             :                                         i, irecs[i].br_startoff,
    2773             :                                         irecs[i].br_startblock,
    2774             :                                         irecs[i].br_blockcount,
    2775             :                                         irecs[i].br_state);
    2776             :                         }
    2777             :                 }
    2778             :         } else {
    2779      270818 :                 *nmaps = 0;
    2780             :         }
    2781      270818 :         goto out_free_irecs;
    2782             : }
    2783             : 
    2784             : /*
    2785             :  * Get a buffer for the dir/attr block.
    2786             :  */
    2787             : int
    2788     4790041 : xfs_da_get_buf(
    2789             :         struct xfs_trans        *tp,
    2790             :         struct xfs_inode        *dp,
    2791             :         xfs_dablk_t             bno,
    2792             :         struct xfs_buf          **bpp,
    2793             :         int                     whichfork)
    2794             : {
    2795     4790041 :         struct xfs_mount        *mp = dp->i_mount;
    2796     4790041 :         struct xfs_buf          *bp;
    2797     4790041 :         struct xfs_buf_map      map, *mapp = &map;
    2798     4790041 :         int                     nmap = 1;
    2799     4790041 :         int                     error;
    2800             : 
    2801     4790041 :         *bpp = NULL;
    2802     4790041 :         error = xfs_dabuf_map(dp, bno, 0, whichfork, &mapp, &nmap);
    2803     4789949 :         if (error || nmap == 0)
    2804           0 :                 goto out_free;
    2805             : 
    2806     4789949 :         error = xfs_trans_get_buf_map(tp, mp->m_ddev_targp, mapp, nmap, 0, &bp);
    2807     4790337 :         if (error)
    2808           0 :                 goto out_free;
    2809             : 
    2810     4790337 :         *bpp = bp;
    2811             : 
    2812     4790337 : out_free:
    2813     4790337 :         if (mapp != &map)
    2814          42 :                 kmem_free(mapp);
    2815             : 
    2816     4790337 :         return error;
    2817             : }
    2818             : 
    2819             : /*
    2820             :  * Get a buffer for the dir/attr block, fill in the contents.
    2821             :  */
    2822             : int
    2823  1703829481 : xfs_da_read_buf(
    2824             :         struct xfs_trans        *tp,
    2825             :         struct xfs_inode        *dp,
    2826             :         xfs_dablk_t             bno,
    2827             :         unsigned int            flags,
    2828             :         struct xfs_buf          **bpp,
    2829             :         int                     whichfork,
    2830             :         const struct xfs_buf_ops *ops)
    2831             : {
    2832  1703829481 :         struct xfs_mount        *mp = dp->i_mount;
    2833  1703829481 :         struct xfs_buf          *bp;
    2834  1703829481 :         struct xfs_buf_map      map, *mapp = &map;
    2835  1703829481 :         int                     nmap = 1;
    2836  1703829481 :         int                     error;
    2837             : 
    2838  1703829481 :         *bpp = NULL;
    2839  1703829481 :         error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
    2840  1704619594 :         if (error || !nmap)
    2841      270978 :                 goto out_free;
    2842             : 
    2843  1704348616 :         error = xfs_trans_read_buf_map(mp, tp, mp->m_ddev_targp, mapp, nmap, 0,
    2844             :                         &bp, ops);
    2845  1704285811 :         if (xfs_metadata_is_sick(error))
    2846         246 :                 xfs_dirattr_mark_sick(dp, whichfork);
    2847  1704285811 :         if (error)
    2848       17272 :                 goto out_free;
    2849             : 
    2850  1704268539 :         if (whichfork == XFS_ATTR_FORK)
    2851   945924397 :                 xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
    2852             :         else
    2853   758344142 :                 xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
    2854  1704405418 :         *bpp = bp;
    2855  1704693668 : out_free:
    2856  1704693668 :         if (mapp != &map)
    2857       68706 :                 kmem_free(mapp);
    2858             : 
    2859  1704693668 :         return error;
    2860             : }
    2861             : 
    2862             : /*
    2863             :  * Readahead the dir/attr block.
    2864             :  */
    2865             : int
    2866   140193097 : xfs_da_reada_buf(
    2867             :         struct xfs_inode        *dp,
    2868             :         xfs_dablk_t             bno,
    2869             :         unsigned int            flags,
    2870             :         int                     whichfork,
    2871             :         const struct xfs_buf_ops *ops)
    2872             : {
    2873   140193097 :         struct xfs_buf_map      map;
    2874   140193097 :         struct xfs_buf_map      *mapp;
    2875   140193097 :         int                     nmap;
    2876   140193097 :         int                     error;
    2877             : 
    2878   140193097 :         mapp = &map;
    2879   140193097 :         nmap = 1;
    2880   140193097 :         error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
    2881   140217969 :         if (error || !nmap)
    2882          10 :                 goto out_free;
    2883             : 
    2884   140217959 :         xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap, ops);
    2885             : 
    2886   140226281 : out_free:
    2887   140226281 :         if (mapp != &map)
    2888           0 :                 kmem_free(mapp);
    2889             : 
    2890   140226281 :         return error;
    2891             : }

Generated by: LCOV version 1.14