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