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