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_format.h" 22 #include "xfs_log_format.h" 23 #include "xfs_trans_resv.h" 24 #include "xfs_sb.h" 25 #include "xfs_ag.h" 26 #include "xfs_mount.h" 27 #include "xfs_da_format.h" 28 #include "xfs_da_btree.h" 29 #include "xfs_inode.h" 30 #include "xfs_bmap.h" 31 #include "xfs_dir2.h" 32 #include "xfs_dir2_priv.h" 33 #include "xfs_error.h" 34 #include "xfs_trace.h" 35 #include "xfs_trans.h" 36 #include "xfs_buf_item.h" 37 #include "xfs_cksum.h" 38 39 /* 40 * Function declarations. 41 */ 42 static int xfs_dir2_leafn_add(struct xfs_buf *bp, xfs_da_args_t *args, 43 int index); 44 static void xfs_dir2_leafn_rebalance(xfs_da_state_t *state, 45 xfs_da_state_blk_t *blk1, 46 xfs_da_state_blk_t *blk2); 47 static int xfs_dir2_leafn_remove(xfs_da_args_t *args, struct xfs_buf *bp, 48 int index, xfs_da_state_blk_t *dblk, 49 int *rval); 50 static int xfs_dir2_node_addname_int(xfs_da_args_t *args, 51 xfs_da_state_blk_t *fblk); 52 53 /* 54 * Check internal consistency of a leafn block. 55 */ 56 #ifdef DEBUG 57 #define xfs_dir3_leaf_check(dp, bp) \ 58 do { \ 59 if (!xfs_dir3_leafn_check((dp), (bp))) \ 60 ASSERT(0); \ 61 } while (0); 62 63 static bool 64 xfs_dir3_leafn_check( 65 struct xfs_inode *dp, 66 struct xfs_buf *bp) 67 { 68 struct xfs_dir2_leaf *leaf = bp->b_addr; 69 struct xfs_dir3_icleaf_hdr leafhdr; 70 71 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 72 73 if (leafhdr.magic == XFS_DIR3_LEAFN_MAGIC) { 74 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr; 75 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn) 76 return false; 77 } else if (leafhdr.magic != XFS_DIR2_LEAFN_MAGIC) 78 return false; 79 80 return xfs_dir3_leaf_check_int(dp->i_mount, dp, &leafhdr, leaf); 81 } 82 #else 83 #define xfs_dir3_leaf_check(dp, bp) 84 #endif 85 86 static bool 87 xfs_dir3_free_verify( 88 struct xfs_buf *bp) 89 { 90 struct xfs_mount *mp = bp->b_target->bt_mount; 91 struct xfs_dir2_free_hdr *hdr = bp->b_addr; 92 93 if (xfs_sb_version_hascrc(&mp->m_sb)) { 94 struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr; 95 96 if (hdr3->magic != cpu_to_be32(XFS_DIR3_FREE_MAGIC)) 97 return false; 98 if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_uuid)) 99 return false; 100 if (be64_to_cpu(hdr3->blkno) != bp->b_bn) 101 return false; 102 } else { 103 if (hdr->magic != cpu_to_be32(XFS_DIR2_FREE_MAGIC)) 104 return false; 105 } 106 107 /* XXX: should bounds check the xfs_dir3_icfree_hdr here */ 108 109 return true; 110 } 111 112 static void 113 xfs_dir3_free_read_verify( 114 struct xfs_buf *bp) 115 { 116 struct xfs_mount *mp = bp->b_target->bt_mount; 117 118 if (xfs_sb_version_hascrc(&mp->m_sb) && 119 !xfs_buf_verify_cksum(bp, XFS_DIR3_FREE_CRC_OFF)) 120 xfs_buf_ioerror(bp, -EFSBADCRC); 121 else if (!xfs_dir3_free_verify(bp)) 122 xfs_buf_ioerror(bp, -EFSCORRUPTED); 123 124 if (bp->b_error) 125 xfs_verifier_error(bp); 126 } 127 128 static void 129 xfs_dir3_free_write_verify( 130 struct xfs_buf *bp) 131 { 132 struct xfs_mount *mp = bp->b_target->bt_mount; 133 struct xfs_buf_log_item *bip = bp->b_fspriv; 134 struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr; 135 136 if (!xfs_dir3_free_verify(bp)) { 137 xfs_buf_ioerror(bp, -EFSCORRUPTED); 138 xfs_verifier_error(bp); 139 return; 140 } 141 142 if (!xfs_sb_version_hascrc(&mp->m_sb)) 143 return; 144 145 if (bip) 146 hdr3->lsn = cpu_to_be64(bip->bli_item.li_lsn); 147 148 xfs_buf_update_cksum(bp, XFS_DIR3_FREE_CRC_OFF); 149 } 150 151 const struct xfs_buf_ops xfs_dir3_free_buf_ops = { 152 .verify_read = xfs_dir3_free_read_verify, 153 .verify_write = xfs_dir3_free_write_verify, 154 }; 155 156 157 static int 158 __xfs_dir3_free_read( 159 struct xfs_trans *tp, 160 struct xfs_inode *dp, 161 xfs_dablk_t fbno, 162 xfs_daddr_t mappedbno, 163 struct xfs_buf **bpp) 164 { 165 int err; 166 167 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp, 168 XFS_DATA_FORK, &xfs_dir3_free_buf_ops); 169 170 /* try read returns without an error or *bpp if it lands in a hole */ 171 if (!err && tp && *bpp) 172 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_FREE_BUF); 173 return err; 174 } 175 176 int 177 xfs_dir2_free_read( 178 struct xfs_trans *tp, 179 struct xfs_inode *dp, 180 xfs_dablk_t fbno, 181 struct xfs_buf **bpp) 182 { 183 return __xfs_dir3_free_read(tp, dp, fbno, -1, bpp); 184 } 185 186 static int 187 xfs_dir2_free_try_read( 188 struct xfs_trans *tp, 189 struct xfs_inode *dp, 190 xfs_dablk_t fbno, 191 struct xfs_buf **bpp) 192 { 193 return __xfs_dir3_free_read(tp, dp, fbno, -2, bpp); 194 } 195 196 static int 197 xfs_dir3_free_get_buf( 198 xfs_da_args_t *args, 199 xfs_dir2_db_t fbno, 200 struct xfs_buf **bpp) 201 { 202 struct xfs_trans *tp = args->trans; 203 struct xfs_inode *dp = args->dp; 204 struct xfs_mount *mp = dp->i_mount; 205 struct xfs_buf *bp; 206 int error; 207 struct xfs_dir3_icfree_hdr hdr; 208 209 error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, fbno), 210 -1, &bp, XFS_DATA_FORK); 211 if (error) 212 return error; 213 214 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_FREE_BUF); 215 bp->b_ops = &xfs_dir3_free_buf_ops; 216 217 /* 218 * Initialize the new block to be empty, and remember 219 * its first slot as our empty slot. 220 */ 221 memset(bp->b_addr, 0, sizeof(struct xfs_dir3_free_hdr)); 222 memset(&hdr, 0, sizeof(hdr)); 223 224 if (xfs_sb_version_hascrc(&mp->m_sb)) { 225 struct xfs_dir3_free_hdr *hdr3 = bp->b_addr; 226 227 hdr.magic = XFS_DIR3_FREE_MAGIC; 228 229 hdr3->hdr.blkno = cpu_to_be64(bp->b_bn); 230 hdr3->hdr.owner = cpu_to_be64(dp->i_ino); 231 uuid_copy(&hdr3->hdr.uuid, &mp->m_sb.sb_uuid); 232 } else 233 hdr.magic = XFS_DIR2_FREE_MAGIC; 234 dp->d_ops->free_hdr_to_disk(bp->b_addr, &hdr); 235 *bpp = bp; 236 return 0; 237 } 238 239 /* 240 * Log entries from a freespace block. 241 */ 242 STATIC void 243 xfs_dir2_free_log_bests( 244 struct xfs_da_args *args, 245 struct xfs_buf *bp, 246 int first, /* first entry to log */ 247 int last) /* last entry to log */ 248 { 249 xfs_dir2_free_t *free; /* freespace structure */ 250 __be16 *bests; 251 252 free = bp->b_addr; 253 bests = args->dp->d_ops->free_bests_p(free); 254 ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) || 255 free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC)); 256 xfs_trans_log_buf(args->trans, bp, 257 (uint)((char *)&bests[first] - (char *)free), 258 (uint)((char *)&bests[last] - (char *)free + 259 sizeof(bests[0]) - 1)); 260 } 261 262 /* 263 * Log header from a freespace block. 264 */ 265 static void 266 xfs_dir2_free_log_header( 267 struct xfs_da_args *args, 268 struct xfs_buf *bp) 269 { 270 #ifdef DEBUG 271 xfs_dir2_free_t *free; /* freespace structure */ 272 273 free = bp->b_addr; 274 ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) || 275 free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC)); 276 #endif 277 xfs_trans_log_buf(args->trans, bp, 0, 278 args->dp->d_ops->free_hdr_size - 1); 279 } 280 281 /* 282 * Convert a leaf-format directory to a node-format directory. 283 * We need to change the magic number of the leaf block, and copy 284 * the freespace table out of the leaf block into its own block. 285 */ 286 int /* error */ 287 xfs_dir2_leaf_to_node( 288 xfs_da_args_t *args, /* operation arguments */ 289 struct xfs_buf *lbp) /* leaf buffer */ 290 { 291 xfs_inode_t *dp; /* incore directory inode */ 292 int error; /* error return value */ 293 struct xfs_buf *fbp; /* freespace buffer */ 294 xfs_dir2_db_t fdb; /* freespace block number */ 295 xfs_dir2_free_t *free; /* freespace structure */ 296 __be16 *from; /* pointer to freespace entry */ 297 int i; /* leaf freespace index */ 298 xfs_dir2_leaf_t *leaf; /* leaf structure */ 299 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 300 xfs_mount_t *mp; /* filesystem mount point */ 301 int n; /* count of live freespc ents */ 302 xfs_dir2_data_off_t off; /* freespace entry value */ 303 __be16 *to; /* pointer to freespace entry */ 304 xfs_trans_t *tp; /* transaction pointer */ 305 struct xfs_dir3_icfree_hdr freehdr; 306 307 trace_xfs_dir2_leaf_to_node(args); 308 309 dp = args->dp; 310 mp = dp->i_mount; 311 tp = args->trans; 312 /* 313 * Add a freespace block to the directory. 314 */ 315 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, &fdb))) { 316 return error; 317 } 318 ASSERT(fdb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET)); 319 /* 320 * Get the buffer for the new freespace block. 321 */ 322 error = xfs_dir3_free_get_buf(args, fdb, &fbp); 323 if (error) 324 return error; 325 326 free = fbp->b_addr; 327 dp->d_ops->free_hdr_from_disk(&freehdr, free); 328 leaf = lbp->b_addr; 329 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 330 ASSERT(be32_to_cpu(ltp->bestcount) <= 331 (uint)dp->i_d.di_size / args->geo->blksize); 332 333 /* 334 * Copy freespace entries from the leaf block to the new block. 335 * Count active entries. 336 */ 337 from = xfs_dir2_leaf_bests_p(ltp); 338 to = dp->d_ops->free_bests_p(free); 339 for (i = n = 0; i < be32_to_cpu(ltp->bestcount); i++, from++, to++) { 340 if ((off = be16_to_cpu(*from)) != NULLDATAOFF) 341 n++; 342 *to = cpu_to_be16(off); 343 } 344 345 /* 346 * Now initialize the freespace block header. 347 */ 348 freehdr.nused = n; 349 freehdr.nvalid = be32_to_cpu(ltp->bestcount); 350 351 dp->d_ops->free_hdr_to_disk(fbp->b_addr, &freehdr); 352 xfs_dir2_free_log_bests(args, fbp, 0, freehdr.nvalid - 1); 353 xfs_dir2_free_log_header(args, fbp); 354 355 /* 356 * Converting the leaf to a leafnode is just a matter of changing the 357 * magic number and the ops. Do the change directly to the buffer as 358 * it's less work (and less code) than decoding the header to host 359 * format and back again. 360 */ 361 if (leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC)) 362 leaf->hdr.info.magic = cpu_to_be16(XFS_DIR2_LEAFN_MAGIC); 363 else 364 leaf->hdr.info.magic = cpu_to_be16(XFS_DIR3_LEAFN_MAGIC); 365 lbp->b_ops = &xfs_dir3_leafn_buf_ops; 366 xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAFN_BUF); 367 xfs_dir3_leaf_log_header(args, lbp); 368 xfs_dir3_leaf_check(dp, lbp); 369 return 0; 370 } 371 372 /* 373 * Add a leaf entry to a leaf block in a node-form directory. 374 * The other work necessary is done from the caller. 375 */ 376 static int /* error */ 377 xfs_dir2_leafn_add( 378 struct xfs_buf *bp, /* leaf buffer */ 379 xfs_da_args_t *args, /* operation arguments */ 380 int index) /* insertion pt for new entry */ 381 { 382 int compact; /* compacting stale leaves */ 383 xfs_inode_t *dp; /* incore directory inode */ 384 int highstale; /* next stale entry */ 385 xfs_dir2_leaf_t *leaf; /* leaf structure */ 386 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 387 int lfloghigh; /* high leaf entry logging */ 388 int lfloglow; /* low leaf entry logging */ 389 int lowstale; /* previous stale entry */ 390 xfs_mount_t *mp; /* filesystem mount point */ 391 xfs_trans_t *tp; /* transaction pointer */ 392 struct xfs_dir3_icleaf_hdr leafhdr; 393 struct xfs_dir2_leaf_entry *ents; 394 395 trace_xfs_dir2_leafn_add(args, index); 396 397 dp = args->dp; 398 mp = dp->i_mount; 399 tp = args->trans; 400 leaf = bp->b_addr; 401 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 402 ents = dp->d_ops->leaf_ents_p(leaf); 403 404 /* 405 * Quick check just to make sure we are not going to index 406 * into other peoples memory 407 */ 408 if (index < 0) 409 return -EFSCORRUPTED; 410 411 /* 412 * If there are already the maximum number of leaf entries in 413 * the block, if there are no stale entries it won't fit. 414 * Caller will do a split. If there are stale entries we'll do 415 * a compact. 416 */ 417 418 if (leafhdr.count == dp->d_ops->leaf_max_ents(args->geo)) { 419 if (!leafhdr.stale) 420 return -ENOSPC; 421 compact = leafhdr.stale > 1; 422 } else 423 compact = 0; 424 ASSERT(index == 0 || be32_to_cpu(ents[index - 1].hashval) <= args->hashval); 425 ASSERT(index == leafhdr.count || 426 be32_to_cpu(ents[index].hashval) >= args->hashval); 427 428 if (args->op_flags & XFS_DA_OP_JUSTCHECK) 429 return 0; 430 431 /* 432 * Compact out all but one stale leaf entry. Leaves behind 433 * the entry closest to index. 434 */ 435 if (compact) 436 xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale, 437 &highstale, &lfloglow, &lfloghigh); 438 else if (leafhdr.stale) { 439 /* 440 * Set impossible logging indices for this case. 441 */ 442 lfloglow = leafhdr.count; 443 lfloghigh = -1; 444 } 445 446 /* 447 * Insert the new entry, log everything. 448 */ 449 lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale, 450 highstale, &lfloglow, &lfloghigh); 451 452 lep->hashval = cpu_to_be32(args->hashval); 453 lep->address = cpu_to_be32(xfs_dir2_db_off_to_dataptr(args->geo, 454 args->blkno, args->index)); 455 456 dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr); 457 xfs_dir3_leaf_log_header(args, bp); 458 xfs_dir3_leaf_log_ents(args, bp, lfloglow, lfloghigh); 459 xfs_dir3_leaf_check(dp, bp); 460 return 0; 461 } 462 463 #ifdef DEBUG 464 static void 465 xfs_dir2_free_hdr_check( 466 struct xfs_inode *dp, 467 struct xfs_buf *bp, 468 xfs_dir2_db_t db) 469 { 470 struct xfs_dir3_icfree_hdr hdr; 471 472 dp->d_ops->free_hdr_from_disk(&hdr, bp->b_addr); 473 474 ASSERT((hdr.firstdb % 475 dp->d_ops->free_max_bests(dp->i_mount->m_dir_geo)) == 0); 476 ASSERT(hdr.firstdb <= db); 477 ASSERT(db < hdr.firstdb + hdr.nvalid); 478 } 479 #else 480 #define xfs_dir2_free_hdr_check(dp, bp, db) 481 #endif /* DEBUG */ 482 483 /* 484 * Return the last hash value in the leaf. 485 * Stale entries are ok. 486 */ 487 xfs_dahash_t /* hash value */ 488 xfs_dir2_leafn_lasthash( 489 struct xfs_inode *dp, 490 struct xfs_buf *bp, /* leaf buffer */ 491 int *count) /* count of entries in leaf */ 492 { 493 struct xfs_dir2_leaf *leaf = bp->b_addr; 494 struct xfs_dir2_leaf_entry *ents; 495 struct xfs_dir3_icleaf_hdr leafhdr; 496 497 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 498 499 ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC || 500 leafhdr.magic == XFS_DIR3_LEAFN_MAGIC); 501 502 if (count) 503 *count = leafhdr.count; 504 if (!leafhdr.count) 505 return 0; 506 507 ents = dp->d_ops->leaf_ents_p(leaf); 508 return be32_to_cpu(ents[leafhdr.count - 1].hashval); 509 } 510 511 /* 512 * Look up a leaf entry for space to add a name in a node-format leaf block. 513 * The extrablk in state is a freespace block. 514 */ 515 STATIC int 516 xfs_dir2_leafn_lookup_for_addname( 517 struct xfs_buf *bp, /* leaf buffer */ 518 xfs_da_args_t *args, /* operation arguments */ 519 int *indexp, /* out: leaf entry index */ 520 xfs_da_state_t *state) /* state to fill in */ 521 { 522 struct xfs_buf *curbp = NULL; /* current data/free buffer */ 523 xfs_dir2_db_t curdb = -1; /* current data block number */ 524 xfs_dir2_db_t curfdb = -1; /* current free block number */ 525 xfs_inode_t *dp; /* incore directory inode */ 526 int error; /* error return value */ 527 int fi; /* free entry index */ 528 xfs_dir2_free_t *free = NULL; /* free block structure */ 529 int index; /* leaf entry index */ 530 xfs_dir2_leaf_t *leaf; /* leaf structure */ 531 int length; /* length of new data entry */ 532 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 533 xfs_mount_t *mp; /* filesystem mount point */ 534 xfs_dir2_db_t newdb; /* new data block number */ 535 xfs_dir2_db_t newfdb; /* new free block number */ 536 xfs_trans_t *tp; /* transaction pointer */ 537 struct xfs_dir2_leaf_entry *ents; 538 struct xfs_dir3_icleaf_hdr leafhdr; 539 540 dp = args->dp; 541 tp = args->trans; 542 mp = dp->i_mount; 543 leaf = bp->b_addr; 544 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 545 ents = dp->d_ops->leaf_ents_p(leaf); 546 547 xfs_dir3_leaf_check(dp, bp); 548 ASSERT(leafhdr.count > 0); 549 550 /* 551 * Look up the hash value in the leaf entries. 552 */ 553 index = xfs_dir2_leaf_search_hash(args, bp); 554 /* 555 * Do we have a buffer coming in? 556 */ 557 if (state->extravalid) { 558 /* If so, it's a free block buffer, get the block number. */ 559 curbp = state->extrablk.bp; 560 curfdb = state->extrablk.blkno; 561 free = curbp->b_addr; 562 ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC) || 563 free->hdr.magic == cpu_to_be32(XFS_DIR3_FREE_MAGIC)); 564 } 565 length = dp->d_ops->data_entsize(args->namelen); 566 /* 567 * Loop over leaf entries with the right hash value. 568 */ 569 for (lep = &ents[index]; 570 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval; 571 lep++, index++) { 572 /* 573 * Skip stale leaf entries. 574 */ 575 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR) 576 continue; 577 /* 578 * Pull the data block number from the entry. 579 */ 580 newdb = xfs_dir2_dataptr_to_db(args->geo, 581 be32_to_cpu(lep->address)); 582 /* 583 * For addname, we're looking for a place to put the new entry. 584 * We want to use a data block with an entry of equal 585 * hash value to ours if there is one with room. 586 * 587 * If this block isn't the data block we already have 588 * in hand, take a look at it. 589 */ 590 if (newdb != curdb) { 591 __be16 *bests; 592 593 curdb = newdb; 594 /* 595 * Convert the data block to the free block 596 * holding its freespace information. 597 */ 598 newfdb = dp->d_ops->db_to_fdb(args->geo, newdb); 599 /* 600 * If it's not the one we have in hand, read it in. 601 */ 602 if (newfdb != curfdb) { 603 /* 604 * If we had one before, drop it. 605 */ 606 if (curbp) 607 xfs_trans_brelse(tp, curbp); 608 609 error = xfs_dir2_free_read(tp, dp, 610 xfs_dir2_db_to_da(args->geo, 611 newfdb), 612 &curbp); 613 if (error) 614 return error; 615 free = curbp->b_addr; 616 617 xfs_dir2_free_hdr_check(dp, curbp, curdb); 618 } 619 /* 620 * Get the index for our entry. 621 */ 622 fi = dp->d_ops->db_to_fdindex(args->geo, curdb); 623 /* 624 * If it has room, return it. 625 */ 626 bests = dp->d_ops->free_bests_p(free); 627 if (unlikely(bests[fi] == cpu_to_be16(NULLDATAOFF))) { 628 XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int", 629 XFS_ERRLEVEL_LOW, mp); 630 if (curfdb != newfdb) 631 xfs_trans_brelse(tp, curbp); 632 return -EFSCORRUPTED; 633 } 634 curfdb = newfdb; 635 if (be16_to_cpu(bests[fi]) >= length) 636 goto out; 637 } 638 } 639 /* Didn't find any space */ 640 fi = -1; 641 out: 642 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT); 643 if (curbp) { 644 /* Giving back a free block. */ 645 state->extravalid = 1; 646 state->extrablk.bp = curbp; 647 state->extrablk.index = fi; 648 state->extrablk.blkno = curfdb; 649 650 /* 651 * Important: this magic number is not in the buffer - it's for 652 * buffer type information and therefore only the free/data type 653 * matters here, not whether CRCs are enabled or not. 654 */ 655 state->extrablk.magic = XFS_DIR2_FREE_MAGIC; 656 } else { 657 state->extravalid = 0; 658 } 659 /* 660 * Return the index, that will be the insertion point. 661 */ 662 *indexp = index; 663 return -ENOENT; 664 } 665 666 /* 667 * Look up a leaf entry in a node-format leaf block. 668 * The extrablk in state a data block. 669 */ 670 STATIC int 671 xfs_dir2_leafn_lookup_for_entry( 672 struct xfs_buf *bp, /* leaf buffer */ 673 xfs_da_args_t *args, /* operation arguments */ 674 int *indexp, /* out: leaf entry index */ 675 xfs_da_state_t *state) /* state to fill in */ 676 { 677 struct xfs_buf *curbp = NULL; /* current data/free buffer */ 678 xfs_dir2_db_t curdb = -1; /* current data block number */ 679 xfs_dir2_data_entry_t *dep; /* data block entry */ 680 xfs_inode_t *dp; /* incore directory inode */ 681 int error; /* error return value */ 682 int index; /* leaf entry index */ 683 xfs_dir2_leaf_t *leaf; /* leaf structure */ 684 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 685 xfs_mount_t *mp; /* filesystem mount point */ 686 xfs_dir2_db_t newdb; /* new data block number */ 687 xfs_trans_t *tp; /* transaction pointer */ 688 enum xfs_dacmp cmp; /* comparison result */ 689 struct xfs_dir2_leaf_entry *ents; 690 struct xfs_dir3_icleaf_hdr leafhdr; 691 692 dp = args->dp; 693 tp = args->trans; 694 mp = dp->i_mount; 695 leaf = bp->b_addr; 696 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 697 ents = dp->d_ops->leaf_ents_p(leaf); 698 699 xfs_dir3_leaf_check(dp, bp); 700 ASSERT(leafhdr.count > 0); 701 702 /* 703 * Look up the hash value in the leaf entries. 704 */ 705 index = xfs_dir2_leaf_search_hash(args, bp); 706 /* 707 * Do we have a buffer coming in? 708 */ 709 if (state->extravalid) { 710 curbp = state->extrablk.bp; 711 curdb = state->extrablk.blkno; 712 } 713 /* 714 * Loop over leaf entries with the right hash value. 715 */ 716 for (lep = &ents[index]; 717 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval; 718 lep++, index++) { 719 /* 720 * Skip stale leaf entries. 721 */ 722 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR) 723 continue; 724 /* 725 * Pull the data block number from the entry. 726 */ 727 newdb = xfs_dir2_dataptr_to_db(args->geo, 728 be32_to_cpu(lep->address)); 729 /* 730 * Not adding a new entry, so we really want to find 731 * the name given to us. 732 * 733 * If it's a different data block, go get it. 734 */ 735 if (newdb != curdb) { 736 /* 737 * If we had a block before that we aren't saving 738 * for a CI name, drop it 739 */ 740 if (curbp && (args->cmpresult == XFS_CMP_DIFFERENT || 741 curdb != state->extrablk.blkno)) 742 xfs_trans_brelse(tp, curbp); 743 /* 744 * If needing the block that is saved with a CI match, 745 * use it otherwise read in the new data block. 746 */ 747 if (args->cmpresult != XFS_CMP_DIFFERENT && 748 newdb == state->extrablk.blkno) { 749 ASSERT(state->extravalid); 750 curbp = state->extrablk.bp; 751 } else { 752 error = xfs_dir3_data_read(tp, dp, 753 xfs_dir2_db_to_da(args->geo, 754 newdb), 755 -1, &curbp); 756 if (error) 757 return error; 758 } 759 xfs_dir3_data_check(dp, curbp); 760 curdb = newdb; 761 } 762 /* 763 * Point to the data entry. 764 */ 765 dep = (xfs_dir2_data_entry_t *)((char *)curbp->b_addr + 766 xfs_dir2_dataptr_to_off(args->geo, 767 be32_to_cpu(lep->address))); 768 /* 769 * Compare the entry and if it's an exact match, return 770 * EEXIST immediately. If it's the first case-insensitive 771 * match, store the block & inode number and continue looking. 772 */ 773 cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen); 774 if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) { 775 /* If there is a CI match block, drop it */ 776 if (args->cmpresult != XFS_CMP_DIFFERENT && 777 curdb != state->extrablk.blkno) 778 xfs_trans_brelse(tp, state->extrablk.bp); 779 args->cmpresult = cmp; 780 args->inumber = be64_to_cpu(dep->inumber); 781 args->filetype = dp->d_ops->data_get_ftype(dep); 782 *indexp = index; 783 state->extravalid = 1; 784 state->extrablk.bp = curbp; 785 state->extrablk.blkno = curdb; 786 state->extrablk.index = (int)((char *)dep - 787 (char *)curbp->b_addr); 788 state->extrablk.magic = XFS_DIR2_DATA_MAGIC; 789 curbp->b_ops = &xfs_dir3_data_buf_ops; 790 xfs_trans_buf_set_type(tp, curbp, XFS_BLFT_DIR_DATA_BUF); 791 if (cmp == XFS_CMP_EXACT) 792 return -EEXIST; 793 } 794 } 795 ASSERT(index == leafhdr.count || (args->op_flags & XFS_DA_OP_OKNOENT)); 796 if (curbp) { 797 if (args->cmpresult == XFS_CMP_DIFFERENT) { 798 /* Giving back last used data block. */ 799 state->extravalid = 1; 800 state->extrablk.bp = curbp; 801 state->extrablk.index = -1; 802 state->extrablk.blkno = curdb; 803 state->extrablk.magic = XFS_DIR2_DATA_MAGIC; 804 curbp->b_ops = &xfs_dir3_data_buf_ops; 805 xfs_trans_buf_set_type(tp, curbp, XFS_BLFT_DIR_DATA_BUF); 806 } else { 807 /* If the curbp is not the CI match block, drop it */ 808 if (state->extrablk.bp != curbp) 809 xfs_trans_brelse(tp, curbp); 810 } 811 } else { 812 state->extravalid = 0; 813 } 814 *indexp = index; 815 return -ENOENT; 816 } 817 818 /* 819 * Look up a leaf entry in a node-format leaf block. 820 * If this is an addname then the extrablk in state is a freespace block, 821 * otherwise it's a data block. 822 */ 823 int 824 xfs_dir2_leafn_lookup_int( 825 struct xfs_buf *bp, /* leaf buffer */ 826 xfs_da_args_t *args, /* operation arguments */ 827 int *indexp, /* out: leaf entry index */ 828 xfs_da_state_t *state) /* state to fill in */ 829 { 830 if (args->op_flags & XFS_DA_OP_ADDNAME) 831 return xfs_dir2_leafn_lookup_for_addname(bp, args, indexp, 832 state); 833 return xfs_dir2_leafn_lookup_for_entry(bp, args, indexp, state); 834 } 835 836 /* 837 * Move count leaf entries from source to destination leaf. 838 * Log entries and headers. Stale entries are preserved. 839 */ 840 static void 841 xfs_dir3_leafn_moveents( 842 xfs_da_args_t *args, /* operation arguments */ 843 struct xfs_buf *bp_s, /* source */ 844 struct xfs_dir3_icleaf_hdr *shdr, 845 struct xfs_dir2_leaf_entry *sents, 846 int start_s,/* source leaf index */ 847 struct xfs_buf *bp_d, /* destination */ 848 struct xfs_dir3_icleaf_hdr *dhdr, 849 struct xfs_dir2_leaf_entry *dents, 850 int start_d,/* destination leaf index */ 851 int count) /* count of leaves to copy */ 852 { 853 int stale; /* count stale leaves copied */ 854 855 trace_xfs_dir2_leafn_moveents(args, start_s, start_d, count); 856 857 /* 858 * Silently return if nothing to do. 859 */ 860 if (count == 0) 861 return; 862 863 /* 864 * If the destination index is not the end of the current 865 * destination leaf entries, open up a hole in the destination 866 * to hold the new entries. 867 */ 868 if (start_d < dhdr->count) { 869 memmove(&dents[start_d + count], &dents[start_d], 870 (dhdr->count - start_d) * sizeof(xfs_dir2_leaf_entry_t)); 871 xfs_dir3_leaf_log_ents(args, bp_d, start_d + count, 872 count + dhdr->count - 1); 873 } 874 /* 875 * If the source has stale leaves, count the ones in the copy range 876 * so we can update the header correctly. 877 */ 878 if (shdr->stale) { 879 int i; /* temp leaf index */ 880 881 for (i = start_s, stale = 0; i < start_s + count; i++) { 882 if (sents[i].address == 883 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 884 stale++; 885 } 886 } else 887 stale = 0; 888 /* 889 * Copy the leaf entries from source to destination. 890 */ 891 memcpy(&dents[start_d], &sents[start_s], 892 count * sizeof(xfs_dir2_leaf_entry_t)); 893 xfs_dir3_leaf_log_ents(args, bp_d, start_d, start_d + count - 1); 894 895 /* 896 * If there are source entries after the ones we copied, 897 * delete the ones we copied by sliding the next ones down. 898 */ 899 if (start_s + count < shdr->count) { 900 memmove(&sents[start_s], &sents[start_s + count], 901 count * sizeof(xfs_dir2_leaf_entry_t)); 902 xfs_dir3_leaf_log_ents(args, bp_s, start_s, start_s + count - 1); 903 } 904 905 /* 906 * Update the headers and log them. 907 */ 908 shdr->count -= count; 909 shdr->stale -= stale; 910 dhdr->count += count; 911 dhdr->stale += stale; 912 } 913 914 /* 915 * Determine the sort order of two leaf blocks. 916 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0. 917 */ 918 int /* sort order */ 919 xfs_dir2_leafn_order( 920 struct xfs_inode *dp, 921 struct xfs_buf *leaf1_bp, /* leaf1 buffer */ 922 struct xfs_buf *leaf2_bp) /* leaf2 buffer */ 923 { 924 struct xfs_dir2_leaf *leaf1 = leaf1_bp->b_addr; 925 struct xfs_dir2_leaf *leaf2 = leaf2_bp->b_addr; 926 struct xfs_dir2_leaf_entry *ents1; 927 struct xfs_dir2_leaf_entry *ents2; 928 struct xfs_dir3_icleaf_hdr hdr1; 929 struct xfs_dir3_icleaf_hdr hdr2; 930 931 dp->d_ops->leaf_hdr_from_disk(&hdr1, leaf1); 932 dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf2); 933 ents1 = dp->d_ops->leaf_ents_p(leaf1); 934 ents2 = dp->d_ops->leaf_ents_p(leaf2); 935 936 if (hdr1.count > 0 && hdr2.count > 0 && 937 (be32_to_cpu(ents2[0].hashval) < be32_to_cpu(ents1[0].hashval) || 938 be32_to_cpu(ents2[hdr2.count - 1].hashval) < 939 be32_to_cpu(ents1[hdr1.count - 1].hashval))) 940 return 1; 941 return 0; 942 } 943 944 /* 945 * Rebalance leaf entries between two leaf blocks. 946 * This is actually only called when the second block is new, 947 * though the code deals with the general case. 948 * A new entry will be inserted in one of the blocks, and that 949 * entry is taken into account when balancing. 950 */ 951 static void 952 xfs_dir2_leafn_rebalance( 953 xfs_da_state_t *state, /* btree cursor */ 954 xfs_da_state_blk_t *blk1, /* first btree block */ 955 xfs_da_state_blk_t *blk2) /* second btree block */ 956 { 957 xfs_da_args_t *args; /* operation arguments */ 958 int count; /* count (& direction) leaves */ 959 int isleft; /* new goes in left leaf */ 960 xfs_dir2_leaf_t *leaf1; /* first leaf structure */ 961 xfs_dir2_leaf_t *leaf2; /* second leaf structure */ 962 int mid; /* midpoint leaf index */ 963 #if defined(DEBUG) || defined(XFS_WARN) 964 int oldstale; /* old count of stale leaves */ 965 #endif 966 int oldsum; /* old total leaf count */ 967 int swap; /* swapped leaf blocks */ 968 struct xfs_dir2_leaf_entry *ents1; 969 struct xfs_dir2_leaf_entry *ents2; 970 struct xfs_dir3_icleaf_hdr hdr1; 971 struct xfs_dir3_icleaf_hdr hdr2; 972 struct xfs_inode *dp = state->args->dp; 973 974 args = state->args; 975 /* 976 * If the block order is wrong, swap the arguments. 977 */ 978 if ((swap = xfs_dir2_leafn_order(dp, blk1->bp, blk2->bp))) { 979 xfs_da_state_blk_t *tmp; /* temp for block swap */ 980 981 tmp = blk1; 982 blk1 = blk2; 983 blk2 = tmp; 984 } 985 leaf1 = blk1->bp->b_addr; 986 leaf2 = blk2->bp->b_addr; 987 dp->d_ops->leaf_hdr_from_disk(&hdr1, leaf1); 988 dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf2); 989 ents1 = dp->d_ops->leaf_ents_p(leaf1); 990 ents2 = dp->d_ops->leaf_ents_p(leaf2); 991 992 oldsum = hdr1.count + hdr2.count; 993 #if defined(DEBUG) || defined(XFS_WARN) 994 oldstale = hdr1.stale + hdr2.stale; 995 #endif 996 mid = oldsum >> 1; 997 998 /* 999 * If the old leaf count was odd then the new one will be even, 1000 * so we need to divide the new count evenly. 1001 */ 1002 if (oldsum & 1) { 1003 xfs_dahash_t midhash; /* middle entry hash value */ 1004 1005 if (mid >= hdr1.count) 1006 midhash = be32_to_cpu(ents2[mid - hdr1.count].hashval); 1007 else 1008 midhash = be32_to_cpu(ents1[mid].hashval); 1009 isleft = args->hashval <= midhash; 1010 } 1011 /* 1012 * If the old count is even then the new count is odd, so there's 1013 * no preferred side for the new entry. 1014 * Pick the left one. 1015 */ 1016 else 1017 isleft = 1; 1018 /* 1019 * Calculate moved entry count. Positive means left-to-right, 1020 * negative means right-to-left. Then move the entries. 1021 */ 1022 count = hdr1.count - mid + (isleft == 0); 1023 if (count > 0) 1024 xfs_dir3_leafn_moveents(args, blk1->bp, &hdr1, ents1, 1025 hdr1.count - count, blk2->bp, 1026 &hdr2, ents2, 0, count); 1027 else if (count < 0) 1028 xfs_dir3_leafn_moveents(args, blk2->bp, &hdr2, ents2, 0, 1029 blk1->bp, &hdr1, ents1, 1030 hdr1.count, count); 1031 1032 ASSERT(hdr1.count + hdr2.count == oldsum); 1033 ASSERT(hdr1.stale + hdr2.stale == oldstale); 1034 1035 /* log the changes made when moving the entries */ 1036 dp->d_ops->leaf_hdr_to_disk(leaf1, &hdr1); 1037 dp->d_ops->leaf_hdr_to_disk(leaf2, &hdr2); 1038 xfs_dir3_leaf_log_header(args, blk1->bp); 1039 xfs_dir3_leaf_log_header(args, blk2->bp); 1040 1041 xfs_dir3_leaf_check(dp, blk1->bp); 1042 xfs_dir3_leaf_check(dp, blk2->bp); 1043 1044 /* 1045 * Mark whether we're inserting into the old or new leaf. 1046 */ 1047 if (hdr1.count < hdr2.count) 1048 state->inleaf = swap; 1049 else if (hdr1.count > hdr2.count) 1050 state->inleaf = !swap; 1051 else 1052 state->inleaf = swap ^ (blk1->index <= hdr1.count); 1053 /* 1054 * Adjust the expected index for insertion. 1055 */ 1056 if (!state->inleaf) 1057 blk2->index = blk1->index - hdr1.count; 1058 1059 /* 1060 * Finally sanity check just to make sure we are not returning a 1061 * negative index 1062 */ 1063 if (blk2->index < 0) { 1064 state->inleaf = 1; 1065 blk2->index = 0; 1066 xfs_alert(dp->i_mount, 1067 "%s: picked the wrong leaf? reverting original leaf: blk1->index %d", 1068 __func__, blk1->index); 1069 } 1070 } 1071 1072 static int 1073 xfs_dir3_data_block_free( 1074 xfs_da_args_t *args, 1075 struct xfs_dir2_data_hdr *hdr, 1076 struct xfs_dir2_free *free, 1077 xfs_dir2_db_t fdb, 1078 int findex, 1079 struct xfs_buf *fbp, 1080 int longest) 1081 { 1082 int logfree = 0; 1083 __be16 *bests; 1084 struct xfs_dir3_icfree_hdr freehdr; 1085 struct xfs_inode *dp = args->dp; 1086 1087 dp->d_ops->free_hdr_from_disk(&freehdr, free); 1088 bests = dp->d_ops->free_bests_p(free); 1089 if (hdr) { 1090 /* 1091 * Data block is not empty, just set the free entry to the new 1092 * value. 1093 */ 1094 bests[findex] = cpu_to_be16(longest); 1095 xfs_dir2_free_log_bests(args, fbp, findex, findex); 1096 return 0; 1097 } 1098 1099 /* One less used entry in the free table. */ 1100 freehdr.nused--; 1101 1102 /* 1103 * If this was the last entry in the table, we can trim the table size 1104 * back. There might be other entries at the end referring to 1105 * non-existent data blocks, get those too. 1106 */ 1107 if (findex == freehdr.nvalid - 1) { 1108 int i; /* free entry index */ 1109 1110 for (i = findex - 1; i >= 0; i--) { 1111 if (bests[i] != cpu_to_be16(NULLDATAOFF)) 1112 break; 1113 } 1114 freehdr.nvalid = i + 1; 1115 logfree = 0; 1116 } else { 1117 /* Not the last entry, just punch it out. */ 1118 bests[findex] = cpu_to_be16(NULLDATAOFF); 1119 logfree = 1; 1120 } 1121 1122 dp->d_ops->free_hdr_to_disk(free, &freehdr); 1123 xfs_dir2_free_log_header(args, fbp); 1124 1125 /* 1126 * If there are no useful entries left in the block, get rid of the 1127 * block if we can. 1128 */ 1129 if (!freehdr.nused) { 1130 int error; 1131 1132 error = xfs_dir2_shrink_inode(args, fdb, fbp); 1133 if (error == 0) { 1134 fbp = NULL; 1135 logfree = 0; 1136 } else if (error != -ENOSPC || args->total != 0) 1137 return error; 1138 /* 1139 * It's possible to get ENOSPC if there is no 1140 * space reservation. In this case some one 1141 * else will eventually get rid of this block. 1142 */ 1143 } 1144 1145 /* Log the free entry that changed, unless we got rid of it. */ 1146 if (logfree) 1147 xfs_dir2_free_log_bests(args, fbp, findex, findex); 1148 return 0; 1149 } 1150 1151 /* 1152 * Remove an entry from a node directory. 1153 * This removes the leaf entry and the data entry, 1154 * and updates the free block if necessary. 1155 */ 1156 static int /* error */ 1157 xfs_dir2_leafn_remove( 1158 xfs_da_args_t *args, /* operation arguments */ 1159 struct xfs_buf *bp, /* leaf buffer */ 1160 int index, /* leaf entry index */ 1161 xfs_da_state_blk_t *dblk, /* data block */ 1162 int *rval) /* resulting block needs join */ 1163 { 1164 xfs_dir2_data_hdr_t *hdr; /* data block header */ 1165 xfs_dir2_db_t db; /* data block number */ 1166 struct xfs_buf *dbp; /* data block buffer */ 1167 xfs_dir2_data_entry_t *dep; /* data block entry */ 1168 xfs_inode_t *dp; /* incore directory inode */ 1169 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1170 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1171 int longest; /* longest data free entry */ 1172 int off; /* data block entry offset */ 1173 xfs_mount_t *mp; /* filesystem mount point */ 1174 int needlog; /* need to log data header */ 1175 int needscan; /* need to rescan data frees */ 1176 xfs_trans_t *tp; /* transaction pointer */ 1177 struct xfs_dir2_data_free *bf; /* bestfree table */ 1178 struct xfs_dir3_icleaf_hdr leafhdr; 1179 struct xfs_dir2_leaf_entry *ents; 1180 1181 trace_xfs_dir2_leafn_remove(args, index); 1182 1183 dp = args->dp; 1184 tp = args->trans; 1185 mp = dp->i_mount; 1186 leaf = bp->b_addr; 1187 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 1188 ents = dp->d_ops->leaf_ents_p(leaf); 1189 1190 /* 1191 * Point to the entry we're removing. 1192 */ 1193 lep = &ents[index]; 1194 1195 /* 1196 * Extract the data block and offset from the entry. 1197 */ 1198 db = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address)); 1199 ASSERT(dblk->blkno == db); 1200 off = xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)); 1201 ASSERT(dblk->index == off); 1202 1203 /* 1204 * Kill the leaf entry by marking it stale. 1205 * Log the leaf block changes. 1206 */ 1207 leafhdr.stale++; 1208 dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr); 1209 xfs_dir3_leaf_log_header(args, bp); 1210 1211 lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR); 1212 xfs_dir3_leaf_log_ents(args, bp, index, index); 1213 1214 /* 1215 * Make the data entry free. Keep track of the longest freespace 1216 * in the data block in case it changes. 1217 */ 1218 dbp = dblk->bp; 1219 hdr = dbp->b_addr; 1220 dep = (xfs_dir2_data_entry_t *)((char *)hdr + off); 1221 bf = dp->d_ops->data_bestfree_p(hdr); 1222 longest = be16_to_cpu(bf[0].length); 1223 needlog = needscan = 0; 1224 xfs_dir2_data_make_free(args, dbp, off, 1225 dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan); 1226 /* 1227 * Rescan the data block freespaces for bestfree. 1228 * Log the data block header if needed. 1229 */ 1230 if (needscan) 1231 xfs_dir2_data_freescan(dp, hdr, &needlog); 1232 if (needlog) 1233 xfs_dir2_data_log_header(args, dbp); 1234 xfs_dir3_data_check(dp, dbp); 1235 /* 1236 * If the longest data block freespace changes, need to update 1237 * the corresponding freeblock entry. 1238 */ 1239 if (longest < be16_to_cpu(bf[0].length)) { 1240 int error; /* error return value */ 1241 struct xfs_buf *fbp; /* freeblock buffer */ 1242 xfs_dir2_db_t fdb; /* freeblock block number */ 1243 int findex; /* index in freeblock entries */ 1244 xfs_dir2_free_t *free; /* freeblock structure */ 1245 1246 /* 1247 * Convert the data block number to a free block, 1248 * read in the free block. 1249 */ 1250 fdb = dp->d_ops->db_to_fdb(args->geo, db); 1251 error = xfs_dir2_free_read(tp, dp, 1252 xfs_dir2_db_to_da(args->geo, fdb), 1253 &fbp); 1254 if (error) 1255 return error; 1256 free = fbp->b_addr; 1257 #ifdef DEBUG 1258 { 1259 struct xfs_dir3_icfree_hdr freehdr; 1260 dp->d_ops->free_hdr_from_disk(&freehdr, free); 1261 ASSERT(freehdr.firstdb == dp->d_ops->free_max_bests(args->geo) * 1262 (fdb - xfs_dir2_byte_to_db(args->geo, 1263 XFS_DIR2_FREE_OFFSET))); 1264 } 1265 #endif 1266 /* 1267 * Calculate which entry we need to fix. 1268 */ 1269 findex = dp->d_ops->db_to_fdindex(args->geo, db); 1270 longest = be16_to_cpu(bf[0].length); 1271 /* 1272 * If the data block is now empty we can get rid of it 1273 * (usually). 1274 */ 1275 if (longest == args->geo->blksize - 1276 dp->d_ops->data_entry_offset) { 1277 /* 1278 * Try to punch out the data block. 1279 */ 1280 error = xfs_dir2_shrink_inode(args, db, dbp); 1281 if (error == 0) { 1282 dblk->bp = NULL; 1283 hdr = NULL; 1284 } 1285 /* 1286 * We can get ENOSPC if there's no space reservation. 1287 * In this case just drop the buffer and some one else 1288 * will eventually get rid of the empty block. 1289 */ 1290 else if (!(error == -ENOSPC && args->total == 0)) 1291 return error; 1292 } 1293 /* 1294 * If we got rid of the data block, we can eliminate that entry 1295 * in the free block. 1296 */ 1297 error = xfs_dir3_data_block_free(args, hdr, free, 1298 fdb, findex, fbp, longest); 1299 if (error) 1300 return error; 1301 } 1302 1303 xfs_dir3_leaf_check(dp, bp); 1304 /* 1305 * Return indication of whether this leaf block is empty enough 1306 * to justify trying to join it with a neighbor. 1307 */ 1308 *rval = (dp->d_ops->leaf_hdr_size + 1309 (uint)sizeof(ents[0]) * (leafhdr.count - leafhdr.stale)) < 1310 args->geo->magicpct; 1311 return 0; 1312 } 1313 1314 /* 1315 * Split the leaf entries in the old block into old and new blocks. 1316 */ 1317 int /* error */ 1318 xfs_dir2_leafn_split( 1319 xfs_da_state_t *state, /* btree cursor */ 1320 xfs_da_state_blk_t *oldblk, /* original block */ 1321 xfs_da_state_blk_t *newblk) /* newly created block */ 1322 { 1323 xfs_da_args_t *args; /* operation arguments */ 1324 xfs_dablk_t blkno; /* new leaf block number */ 1325 int error; /* error return value */ 1326 xfs_mount_t *mp; /* filesystem mount point */ 1327 struct xfs_inode *dp; 1328 1329 /* 1330 * Allocate space for a new leaf node. 1331 */ 1332 args = state->args; 1333 dp = args->dp; 1334 mp = dp->i_mount; 1335 ASSERT(oldblk->magic == XFS_DIR2_LEAFN_MAGIC); 1336 error = xfs_da_grow_inode(args, &blkno); 1337 if (error) { 1338 return error; 1339 } 1340 /* 1341 * Initialize the new leaf block. 1342 */ 1343 error = xfs_dir3_leaf_get_buf(args, xfs_dir2_da_to_db(args->geo, blkno), 1344 &newblk->bp, XFS_DIR2_LEAFN_MAGIC); 1345 if (error) 1346 return error; 1347 1348 newblk->blkno = blkno; 1349 newblk->magic = XFS_DIR2_LEAFN_MAGIC; 1350 /* 1351 * Rebalance the entries across the two leaves, link the new 1352 * block into the leaves. 1353 */ 1354 xfs_dir2_leafn_rebalance(state, oldblk, newblk); 1355 error = xfs_da3_blk_link(state, oldblk, newblk); 1356 if (error) { 1357 return error; 1358 } 1359 /* 1360 * Insert the new entry in the correct block. 1361 */ 1362 if (state->inleaf) 1363 error = xfs_dir2_leafn_add(oldblk->bp, args, oldblk->index); 1364 else 1365 error = xfs_dir2_leafn_add(newblk->bp, args, newblk->index); 1366 /* 1367 * Update last hashval in each block since we added the name. 1368 */ 1369 oldblk->hashval = xfs_dir2_leafn_lasthash(dp, oldblk->bp, NULL); 1370 newblk->hashval = xfs_dir2_leafn_lasthash(dp, newblk->bp, NULL); 1371 xfs_dir3_leaf_check(dp, oldblk->bp); 1372 xfs_dir3_leaf_check(dp, newblk->bp); 1373 return error; 1374 } 1375 1376 /* 1377 * Check a leaf block and its neighbors to see if the block should be 1378 * collapsed into one or the other neighbor. Always keep the block 1379 * with the smaller block number. 1380 * If the current block is over 50% full, don't try to join it, return 0. 1381 * If the block is empty, fill in the state structure and return 2. 1382 * If it can be collapsed, fill in the state structure and return 1. 1383 * If nothing can be done, return 0. 1384 */ 1385 int /* error */ 1386 xfs_dir2_leafn_toosmall( 1387 xfs_da_state_t *state, /* btree cursor */ 1388 int *action) /* resulting action to take */ 1389 { 1390 xfs_da_state_blk_t *blk; /* leaf block */ 1391 xfs_dablk_t blkno; /* leaf block number */ 1392 struct xfs_buf *bp; /* leaf buffer */ 1393 int bytes; /* bytes in use */ 1394 int count; /* leaf live entry count */ 1395 int error; /* error return value */ 1396 int forward; /* sibling block direction */ 1397 int i; /* sibling counter */ 1398 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1399 int rval; /* result from path_shift */ 1400 struct xfs_dir3_icleaf_hdr leafhdr; 1401 struct xfs_dir2_leaf_entry *ents; 1402 struct xfs_inode *dp = state->args->dp; 1403 1404 /* 1405 * Check for the degenerate case of the block being over 50% full. 1406 * If so, it's not worth even looking to see if we might be able 1407 * to coalesce with a sibling. 1408 */ 1409 blk = &state->path.blk[state->path.active - 1]; 1410 leaf = blk->bp->b_addr; 1411 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 1412 ents = dp->d_ops->leaf_ents_p(leaf); 1413 xfs_dir3_leaf_check(dp, blk->bp); 1414 1415 count = leafhdr.count - leafhdr.stale; 1416 bytes = dp->d_ops->leaf_hdr_size + count * sizeof(ents[0]); 1417 if (bytes > (state->args->geo->blksize >> 1)) { 1418 /* 1419 * Blk over 50%, don't try to join. 1420 */ 1421 *action = 0; 1422 return 0; 1423 } 1424 /* 1425 * Check for the degenerate case of the block being empty. 1426 * If the block is empty, we'll simply delete it, no need to 1427 * coalesce it with a sibling block. We choose (arbitrarily) 1428 * to merge with the forward block unless it is NULL. 1429 */ 1430 if (count == 0) { 1431 /* 1432 * Make altpath point to the block we want to keep and 1433 * path point to the block we want to drop (this one). 1434 */ 1435 forward = (leafhdr.forw != 0); 1436 memcpy(&state->altpath, &state->path, sizeof(state->path)); 1437 error = xfs_da3_path_shift(state, &state->altpath, forward, 0, 1438 &rval); 1439 if (error) 1440 return error; 1441 *action = rval ? 2 : 0; 1442 return 0; 1443 } 1444 /* 1445 * Examine each sibling block to see if we can coalesce with 1446 * at least 25% free space to spare. We need to figure out 1447 * whether to merge with the forward or the backward block. 1448 * We prefer coalescing with the lower numbered sibling so as 1449 * to shrink a directory over time. 1450 */ 1451 forward = leafhdr.forw < leafhdr.back; 1452 for (i = 0, bp = NULL; i < 2; forward = !forward, i++) { 1453 struct xfs_dir3_icleaf_hdr hdr2; 1454 1455 blkno = forward ? leafhdr.forw : leafhdr.back; 1456 if (blkno == 0) 1457 continue; 1458 /* 1459 * Read the sibling leaf block. 1460 */ 1461 error = xfs_dir3_leafn_read(state->args->trans, dp, 1462 blkno, -1, &bp); 1463 if (error) 1464 return error; 1465 1466 /* 1467 * Count bytes in the two blocks combined. 1468 */ 1469 count = leafhdr.count - leafhdr.stale; 1470 bytes = state->args->geo->blksize - 1471 (state->args->geo->blksize >> 2); 1472 1473 leaf = bp->b_addr; 1474 dp->d_ops->leaf_hdr_from_disk(&hdr2, leaf); 1475 ents = dp->d_ops->leaf_ents_p(leaf); 1476 count += hdr2.count - hdr2.stale; 1477 bytes -= count * sizeof(ents[0]); 1478 1479 /* 1480 * Fits with at least 25% to spare. 1481 */ 1482 if (bytes >= 0) 1483 break; 1484 xfs_trans_brelse(state->args->trans, bp); 1485 } 1486 /* 1487 * Didn't like either block, give up. 1488 */ 1489 if (i >= 2) { 1490 *action = 0; 1491 return 0; 1492 } 1493 1494 /* 1495 * Make altpath point to the block we want to keep (the lower 1496 * numbered block) and path point to the block we want to drop. 1497 */ 1498 memcpy(&state->altpath, &state->path, sizeof(state->path)); 1499 if (blkno < blk->blkno) 1500 error = xfs_da3_path_shift(state, &state->altpath, forward, 0, 1501 &rval); 1502 else 1503 error = xfs_da3_path_shift(state, &state->path, forward, 0, 1504 &rval); 1505 if (error) { 1506 return error; 1507 } 1508 *action = rval ? 0 : 1; 1509 return 0; 1510 } 1511 1512 /* 1513 * Move all the leaf entries from drop_blk to save_blk. 1514 * This is done as part of a join operation. 1515 */ 1516 void 1517 xfs_dir2_leafn_unbalance( 1518 xfs_da_state_t *state, /* cursor */ 1519 xfs_da_state_blk_t *drop_blk, /* dead block */ 1520 xfs_da_state_blk_t *save_blk) /* surviving block */ 1521 { 1522 xfs_da_args_t *args; /* operation arguments */ 1523 xfs_dir2_leaf_t *drop_leaf; /* dead leaf structure */ 1524 xfs_dir2_leaf_t *save_leaf; /* surviving leaf structure */ 1525 struct xfs_dir3_icleaf_hdr savehdr; 1526 struct xfs_dir3_icleaf_hdr drophdr; 1527 struct xfs_dir2_leaf_entry *sents; 1528 struct xfs_dir2_leaf_entry *dents; 1529 struct xfs_inode *dp = state->args->dp; 1530 1531 args = state->args; 1532 ASSERT(drop_blk->magic == XFS_DIR2_LEAFN_MAGIC); 1533 ASSERT(save_blk->magic == XFS_DIR2_LEAFN_MAGIC); 1534 drop_leaf = drop_blk->bp->b_addr; 1535 save_leaf = save_blk->bp->b_addr; 1536 1537 dp->d_ops->leaf_hdr_from_disk(&savehdr, save_leaf); 1538 dp->d_ops->leaf_hdr_from_disk(&drophdr, drop_leaf); 1539 sents = dp->d_ops->leaf_ents_p(save_leaf); 1540 dents = dp->d_ops->leaf_ents_p(drop_leaf); 1541 1542 /* 1543 * If there are any stale leaf entries, take this opportunity 1544 * to purge them. 1545 */ 1546 if (drophdr.stale) 1547 xfs_dir3_leaf_compact(args, &drophdr, drop_blk->bp); 1548 if (savehdr.stale) 1549 xfs_dir3_leaf_compact(args, &savehdr, save_blk->bp); 1550 1551 /* 1552 * Move the entries from drop to the appropriate end of save. 1553 */ 1554 drop_blk->hashval = be32_to_cpu(dents[drophdr.count - 1].hashval); 1555 if (xfs_dir2_leafn_order(dp, save_blk->bp, drop_blk->bp)) 1556 xfs_dir3_leafn_moveents(args, drop_blk->bp, &drophdr, dents, 0, 1557 save_blk->bp, &savehdr, sents, 0, 1558 drophdr.count); 1559 else 1560 xfs_dir3_leafn_moveents(args, drop_blk->bp, &drophdr, dents, 0, 1561 save_blk->bp, &savehdr, sents, 1562 savehdr.count, drophdr.count); 1563 save_blk->hashval = be32_to_cpu(sents[savehdr.count - 1].hashval); 1564 1565 /* log the changes made when moving the entries */ 1566 dp->d_ops->leaf_hdr_to_disk(save_leaf, &savehdr); 1567 dp->d_ops->leaf_hdr_to_disk(drop_leaf, &drophdr); 1568 xfs_dir3_leaf_log_header(args, save_blk->bp); 1569 xfs_dir3_leaf_log_header(args, drop_blk->bp); 1570 1571 xfs_dir3_leaf_check(dp, save_blk->bp); 1572 xfs_dir3_leaf_check(dp, drop_blk->bp); 1573 } 1574 1575 /* 1576 * Top-level node form directory addname routine. 1577 */ 1578 int /* error */ 1579 xfs_dir2_node_addname( 1580 xfs_da_args_t *args) /* operation arguments */ 1581 { 1582 xfs_da_state_blk_t *blk; /* leaf block for insert */ 1583 int error; /* error return value */ 1584 int rval; /* sub-return value */ 1585 xfs_da_state_t *state; /* btree cursor */ 1586 1587 trace_xfs_dir2_node_addname(args); 1588 1589 /* 1590 * Allocate and initialize the state (btree cursor). 1591 */ 1592 state = xfs_da_state_alloc(); 1593 state->args = args; 1594 state->mp = args->dp->i_mount; 1595 /* 1596 * Look up the name. We're not supposed to find it, but 1597 * this gives us the insertion point. 1598 */ 1599 error = xfs_da3_node_lookup_int(state, &rval); 1600 if (error) 1601 rval = error; 1602 if (rval != -ENOENT) { 1603 goto done; 1604 } 1605 /* 1606 * Add the data entry to a data block. 1607 * Extravalid is set to a freeblock found by lookup. 1608 */ 1609 rval = xfs_dir2_node_addname_int(args, 1610 state->extravalid ? &state->extrablk : NULL); 1611 if (rval) { 1612 goto done; 1613 } 1614 blk = &state->path.blk[state->path.active - 1]; 1615 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC); 1616 /* 1617 * Add the new leaf entry. 1618 */ 1619 rval = xfs_dir2_leafn_add(blk->bp, args, blk->index); 1620 if (rval == 0) { 1621 /* 1622 * It worked, fix the hash values up the btree. 1623 */ 1624 if (!(args->op_flags & XFS_DA_OP_JUSTCHECK)) 1625 xfs_da3_fixhashpath(state, &state->path); 1626 } else { 1627 /* 1628 * It didn't work, we need to split the leaf block. 1629 */ 1630 if (args->total == 0) { 1631 ASSERT(rval == -ENOSPC); 1632 goto done; 1633 } 1634 /* 1635 * Split the leaf block and insert the new entry. 1636 */ 1637 rval = xfs_da3_split(state); 1638 } 1639 done: 1640 xfs_da_state_free(state); 1641 return rval; 1642 } 1643 1644 /* 1645 * Add the data entry for a node-format directory name addition. 1646 * The leaf entry is added in xfs_dir2_leafn_add. 1647 * We may enter with a freespace block that the lookup found. 1648 */ 1649 static int /* error */ 1650 xfs_dir2_node_addname_int( 1651 xfs_da_args_t *args, /* operation arguments */ 1652 xfs_da_state_blk_t *fblk) /* optional freespace block */ 1653 { 1654 xfs_dir2_data_hdr_t *hdr; /* data block header */ 1655 xfs_dir2_db_t dbno; /* data block number */ 1656 struct xfs_buf *dbp; /* data block buffer */ 1657 xfs_dir2_data_entry_t *dep; /* data entry pointer */ 1658 xfs_inode_t *dp; /* incore directory inode */ 1659 xfs_dir2_data_unused_t *dup; /* data unused entry pointer */ 1660 int error; /* error return value */ 1661 xfs_dir2_db_t fbno; /* freespace block number */ 1662 struct xfs_buf *fbp; /* freespace buffer */ 1663 int findex; /* freespace entry index */ 1664 xfs_dir2_free_t *free=NULL; /* freespace block structure */ 1665 xfs_dir2_db_t ifbno; /* initial freespace block no */ 1666 xfs_dir2_db_t lastfbno=0; /* highest freespace block no */ 1667 int length; /* length of the new entry */ 1668 int logfree; /* need to log free entry */ 1669 xfs_mount_t *mp; /* filesystem mount point */ 1670 int needlog; /* need to log data header */ 1671 int needscan; /* need to rescan data frees */ 1672 __be16 *tagp; /* data entry tag pointer */ 1673 xfs_trans_t *tp; /* transaction pointer */ 1674 __be16 *bests; 1675 struct xfs_dir3_icfree_hdr freehdr; 1676 struct xfs_dir2_data_free *bf; 1677 1678 dp = args->dp; 1679 mp = dp->i_mount; 1680 tp = args->trans; 1681 length = dp->d_ops->data_entsize(args->namelen); 1682 /* 1683 * If we came in with a freespace block that means that lookup 1684 * found an entry with our hash value. This is the freespace 1685 * block for that data entry. 1686 */ 1687 if (fblk) { 1688 fbp = fblk->bp; 1689 /* 1690 * Remember initial freespace block number. 1691 */ 1692 ifbno = fblk->blkno; 1693 free = fbp->b_addr; 1694 findex = fblk->index; 1695 bests = dp->d_ops->free_bests_p(free); 1696 dp->d_ops->free_hdr_from_disk(&freehdr, free); 1697 1698 /* 1699 * This means the free entry showed that the data block had 1700 * space for our entry, so we remembered it. 1701 * Use that data block. 1702 */ 1703 if (findex >= 0) { 1704 ASSERT(findex < freehdr.nvalid); 1705 ASSERT(be16_to_cpu(bests[findex]) != NULLDATAOFF); 1706 ASSERT(be16_to_cpu(bests[findex]) >= length); 1707 dbno = freehdr.firstdb + findex; 1708 } else { 1709 /* 1710 * The data block looked at didn't have enough room. 1711 * We'll start at the beginning of the freespace entries. 1712 */ 1713 dbno = -1; 1714 findex = 0; 1715 } 1716 } else { 1717 /* 1718 * Didn't come in with a freespace block, so no data block. 1719 */ 1720 ifbno = dbno = -1; 1721 fbp = NULL; 1722 findex = 0; 1723 } 1724 1725 /* 1726 * If we don't have a data block yet, we're going to scan the 1727 * freespace blocks looking for one. Figure out what the 1728 * highest freespace block number is. 1729 */ 1730 if (dbno == -1) { 1731 xfs_fileoff_t fo; /* freespace block number */ 1732 1733 if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK))) 1734 return error; 1735 lastfbno = xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo); 1736 fbno = ifbno; 1737 } 1738 /* 1739 * While we haven't identified a data block, search the freeblock 1740 * data for a good data block. If we find a null freeblock entry, 1741 * indicating a hole in the data blocks, remember that. 1742 */ 1743 while (dbno == -1) { 1744 /* 1745 * If we don't have a freeblock in hand, get the next one. 1746 */ 1747 if (fbp == NULL) { 1748 /* 1749 * Happens the first time through unless lookup gave 1750 * us a freespace block to start with. 1751 */ 1752 if (++fbno == 0) 1753 fbno = xfs_dir2_byte_to_db(args->geo, 1754 XFS_DIR2_FREE_OFFSET); 1755 /* 1756 * If it's ifbno we already looked at it. 1757 */ 1758 if (fbno == ifbno) 1759 fbno++; 1760 /* 1761 * If it's off the end we're done. 1762 */ 1763 if (fbno >= lastfbno) 1764 break; 1765 /* 1766 * Read the block. There can be holes in the 1767 * freespace blocks, so this might not succeed. 1768 * This should be really rare, so there's no reason 1769 * to avoid it. 1770 */ 1771 error = xfs_dir2_free_try_read(tp, dp, 1772 xfs_dir2_db_to_da(args->geo, fbno), 1773 &fbp); 1774 if (error) 1775 return error; 1776 if (!fbp) 1777 continue; 1778 free = fbp->b_addr; 1779 findex = 0; 1780 } 1781 /* 1782 * Look at the current free entry. Is it good enough? 1783 * 1784 * The bests initialisation should be where the bufer is read in 1785 * the above branch. But gcc is too stupid to realise that bests 1786 * and the freehdr are actually initialised if they are placed 1787 * there, so we have to do it here to avoid warnings. Blech. 1788 */ 1789 bests = dp->d_ops->free_bests_p(free); 1790 dp->d_ops->free_hdr_from_disk(&freehdr, free); 1791 if (be16_to_cpu(bests[findex]) != NULLDATAOFF && 1792 be16_to_cpu(bests[findex]) >= length) 1793 dbno = freehdr.firstdb + findex; 1794 else { 1795 /* 1796 * Are we done with the freeblock? 1797 */ 1798 if (++findex == freehdr.nvalid) { 1799 /* 1800 * Drop the block. 1801 */ 1802 xfs_trans_brelse(tp, fbp); 1803 fbp = NULL; 1804 if (fblk && fblk->bp) 1805 fblk->bp = NULL; 1806 } 1807 } 1808 } 1809 /* 1810 * If we don't have a data block, we need to allocate one and make 1811 * the freespace entries refer to it. 1812 */ 1813 if (unlikely(dbno == -1)) { 1814 /* 1815 * Not allowed to allocate, return failure. 1816 */ 1817 if ((args->op_flags & XFS_DA_OP_JUSTCHECK) || args->total == 0) 1818 return -ENOSPC; 1819 1820 /* 1821 * Allocate and initialize the new data block. 1822 */ 1823 if (unlikely((error = xfs_dir2_grow_inode(args, 1824 XFS_DIR2_DATA_SPACE, 1825 &dbno)) || 1826 (error = xfs_dir3_data_init(args, dbno, &dbp)))) 1827 return error; 1828 1829 /* 1830 * If (somehow) we have a freespace block, get rid of it. 1831 */ 1832 if (fbp) 1833 xfs_trans_brelse(tp, fbp); 1834 if (fblk && fblk->bp) 1835 fblk->bp = NULL; 1836 1837 /* 1838 * Get the freespace block corresponding to the data block 1839 * that was just allocated. 1840 */ 1841 fbno = dp->d_ops->db_to_fdb(args->geo, dbno); 1842 error = xfs_dir2_free_try_read(tp, dp, 1843 xfs_dir2_db_to_da(args->geo, fbno), 1844 &fbp); 1845 if (error) 1846 return error; 1847 1848 /* 1849 * If there wasn't a freespace block, the read will 1850 * return a NULL fbp. Allocate and initialize a new one. 1851 */ 1852 if (!fbp) { 1853 error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, 1854 &fbno); 1855 if (error) 1856 return error; 1857 1858 if (dp->d_ops->db_to_fdb(args->geo, dbno) != fbno) { 1859 xfs_alert(mp, 1860 "%s: dir ino %llu needed freesp block %lld for\n" 1861 " data block %lld, got %lld ifbno %llu lastfbno %d", 1862 __func__, (unsigned long long)dp->i_ino, 1863 (long long)dp->d_ops->db_to_fdb( 1864 args->geo, dbno), 1865 (long long)dbno, (long long)fbno, 1866 (unsigned long long)ifbno, lastfbno); 1867 if (fblk) { 1868 xfs_alert(mp, 1869 " fblk 0x%p blkno %llu index %d magic 0x%x", 1870 fblk, 1871 (unsigned long long)fblk->blkno, 1872 fblk->index, 1873 fblk->magic); 1874 } else { 1875 xfs_alert(mp, " ... fblk is NULL"); 1876 } 1877 XFS_ERROR_REPORT("xfs_dir2_node_addname_int", 1878 XFS_ERRLEVEL_LOW, mp); 1879 return -EFSCORRUPTED; 1880 } 1881 1882 /* 1883 * Get a buffer for the new block. 1884 */ 1885 error = xfs_dir3_free_get_buf(args, fbno, &fbp); 1886 if (error) 1887 return error; 1888 free = fbp->b_addr; 1889 bests = dp->d_ops->free_bests_p(free); 1890 dp->d_ops->free_hdr_from_disk(&freehdr, free); 1891 1892 /* 1893 * Remember the first slot as our empty slot. 1894 */ 1895 freehdr.firstdb = 1896 (fbno - xfs_dir2_byte_to_db(args->geo, 1897 XFS_DIR2_FREE_OFFSET)) * 1898 dp->d_ops->free_max_bests(args->geo); 1899 } else { 1900 free = fbp->b_addr; 1901 bests = dp->d_ops->free_bests_p(free); 1902 dp->d_ops->free_hdr_from_disk(&freehdr, free); 1903 } 1904 1905 /* 1906 * Set the freespace block index from the data block number. 1907 */ 1908 findex = dp->d_ops->db_to_fdindex(args->geo, dbno); 1909 /* 1910 * If it's after the end of the current entries in the 1911 * freespace block, extend that table. 1912 */ 1913 if (findex >= freehdr.nvalid) { 1914 ASSERT(findex < dp->d_ops->free_max_bests(args->geo)); 1915 freehdr.nvalid = findex + 1; 1916 /* 1917 * Tag new entry so nused will go up. 1918 */ 1919 bests[findex] = cpu_to_be16(NULLDATAOFF); 1920 } 1921 /* 1922 * If this entry was for an empty data block 1923 * (this should always be true) then update the header. 1924 */ 1925 if (bests[findex] == cpu_to_be16(NULLDATAOFF)) { 1926 freehdr.nused++; 1927 dp->d_ops->free_hdr_to_disk(fbp->b_addr, &freehdr); 1928 xfs_dir2_free_log_header(args, fbp); 1929 } 1930 /* 1931 * Update the real value in the table. 1932 * We haven't allocated the data entry yet so this will 1933 * change again. 1934 */ 1935 hdr = dbp->b_addr; 1936 bf = dp->d_ops->data_bestfree_p(hdr); 1937 bests[findex] = bf[0].length; 1938 logfree = 1; 1939 } 1940 /* 1941 * We had a data block so we don't have to make a new one. 1942 */ 1943 else { 1944 /* 1945 * If just checking, we succeeded. 1946 */ 1947 if (args->op_flags & XFS_DA_OP_JUSTCHECK) 1948 return 0; 1949 1950 /* 1951 * Read the data block in. 1952 */ 1953 error = xfs_dir3_data_read(tp, dp, 1954 xfs_dir2_db_to_da(args->geo, dbno), 1955 -1, &dbp); 1956 if (error) 1957 return error; 1958 hdr = dbp->b_addr; 1959 bf = dp->d_ops->data_bestfree_p(hdr); 1960 logfree = 0; 1961 } 1962 ASSERT(be16_to_cpu(bf[0].length) >= length); 1963 /* 1964 * Point to the existing unused space. 1965 */ 1966 dup = (xfs_dir2_data_unused_t *) 1967 ((char *)hdr + be16_to_cpu(bf[0].offset)); 1968 needscan = needlog = 0; 1969 /* 1970 * Mark the first part of the unused space, inuse for us. 1971 */ 1972 xfs_dir2_data_use_free(args, dbp, dup, 1973 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr), length, 1974 &needlog, &needscan); 1975 /* 1976 * Fill in the new entry and log it. 1977 */ 1978 dep = (xfs_dir2_data_entry_t *)dup; 1979 dep->inumber = cpu_to_be64(args->inumber); 1980 dep->namelen = args->namelen; 1981 memcpy(dep->name, args->name, dep->namelen); 1982 dp->d_ops->data_put_ftype(dep, args->filetype); 1983 tagp = dp->d_ops->data_entry_tag_p(dep); 1984 *tagp = cpu_to_be16((char *)dep - (char *)hdr); 1985 xfs_dir2_data_log_entry(args, dbp, dep); 1986 /* 1987 * Rescan the block for bestfree if needed. 1988 */ 1989 if (needscan) 1990 xfs_dir2_data_freescan(dp, hdr, &needlog); 1991 /* 1992 * Log the data block header if needed. 1993 */ 1994 if (needlog) 1995 xfs_dir2_data_log_header(args, dbp); 1996 /* 1997 * If the freespace entry is now wrong, update it. 1998 */ 1999 bests = dp->d_ops->free_bests_p(free); /* gcc is so stupid */ 2000 if (be16_to_cpu(bests[findex]) != be16_to_cpu(bf[0].length)) { 2001 bests[findex] = bf[0].length; 2002 logfree = 1; 2003 } 2004 /* 2005 * Log the freespace entry if needed. 2006 */ 2007 if (logfree) 2008 xfs_dir2_free_log_bests(args, fbp, findex, findex); 2009 /* 2010 * Return the data block and offset in args, then drop the data block. 2011 */ 2012 args->blkno = (xfs_dablk_t)dbno; 2013 args->index = be16_to_cpu(*tagp); 2014 return 0; 2015 } 2016 2017 /* 2018 * Lookup an entry in a node-format directory. 2019 * All the real work happens in xfs_da3_node_lookup_int. 2020 * The only real output is the inode number of the entry. 2021 */ 2022 int /* error */ 2023 xfs_dir2_node_lookup( 2024 xfs_da_args_t *args) /* operation arguments */ 2025 { 2026 int error; /* error return value */ 2027 int i; /* btree level */ 2028 int rval; /* operation return value */ 2029 xfs_da_state_t *state; /* btree cursor */ 2030 2031 trace_xfs_dir2_node_lookup(args); 2032 2033 /* 2034 * Allocate and initialize the btree cursor. 2035 */ 2036 state = xfs_da_state_alloc(); 2037 state->args = args; 2038 state->mp = args->dp->i_mount; 2039 /* 2040 * Fill in the path to the entry in the cursor. 2041 */ 2042 error = xfs_da3_node_lookup_int(state, &rval); 2043 if (error) 2044 rval = error; 2045 else if (rval == -ENOENT && args->cmpresult == XFS_CMP_CASE) { 2046 /* If a CI match, dup the actual name and return -EEXIST */ 2047 xfs_dir2_data_entry_t *dep; 2048 2049 dep = (xfs_dir2_data_entry_t *) 2050 ((char *)state->extrablk.bp->b_addr + 2051 state->extrablk.index); 2052 rval = xfs_dir_cilookup_result(args, dep->name, dep->namelen); 2053 } 2054 /* 2055 * Release the btree blocks and leaf block. 2056 */ 2057 for (i = 0; i < state->path.active; i++) { 2058 xfs_trans_brelse(args->trans, state->path.blk[i].bp); 2059 state->path.blk[i].bp = NULL; 2060 } 2061 /* 2062 * Release the data block if we have it. 2063 */ 2064 if (state->extravalid && state->extrablk.bp) { 2065 xfs_trans_brelse(args->trans, state->extrablk.bp); 2066 state->extrablk.bp = NULL; 2067 } 2068 xfs_da_state_free(state); 2069 return rval; 2070 } 2071 2072 /* 2073 * Remove an entry from a node-format directory. 2074 */ 2075 int /* error */ 2076 xfs_dir2_node_removename( 2077 struct xfs_da_args *args) /* operation arguments */ 2078 { 2079 struct xfs_da_state_blk *blk; /* leaf block */ 2080 int error; /* error return value */ 2081 int rval; /* operation return value */ 2082 struct xfs_da_state *state; /* btree cursor */ 2083 2084 trace_xfs_dir2_node_removename(args); 2085 2086 /* 2087 * Allocate and initialize the btree cursor. 2088 */ 2089 state = xfs_da_state_alloc(); 2090 state->args = args; 2091 state->mp = args->dp->i_mount; 2092 2093 /* Look up the entry we're deleting, set up the cursor. */ 2094 error = xfs_da3_node_lookup_int(state, &rval); 2095 if (error) 2096 goto out_free; 2097 2098 /* Didn't find it, upper layer screwed up. */ 2099 if (rval != -EEXIST) { 2100 error = rval; 2101 goto out_free; 2102 } 2103 2104 blk = &state->path.blk[state->path.active - 1]; 2105 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC); 2106 ASSERT(state->extravalid); 2107 /* 2108 * Remove the leaf and data entries. 2109 * Extrablk refers to the data block. 2110 */ 2111 error = xfs_dir2_leafn_remove(args, blk->bp, blk->index, 2112 &state->extrablk, &rval); 2113 if (error) 2114 goto out_free; 2115 /* 2116 * Fix the hash values up the btree. 2117 */ 2118 xfs_da3_fixhashpath(state, &state->path); 2119 /* 2120 * If we need to join leaf blocks, do it. 2121 */ 2122 if (rval && state->path.active > 1) 2123 error = xfs_da3_join(state); 2124 /* 2125 * If no errors so far, try conversion to leaf format. 2126 */ 2127 if (!error) 2128 error = xfs_dir2_node_to_leaf(state); 2129 out_free: 2130 xfs_da_state_free(state); 2131 return error; 2132 } 2133 2134 /* 2135 * Replace an entry's inode number in a node-format directory. 2136 */ 2137 int /* error */ 2138 xfs_dir2_node_replace( 2139 xfs_da_args_t *args) /* operation arguments */ 2140 { 2141 xfs_da_state_blk_t *blk; /* leaf block */ 2142 xfs_dir2_data_hdr_t *hdr; /* data block header */ 2143 xfs_dir2_data_entry_t *dep; /* data entry changed */ 2144 int error; /* error return value */ 2145 int i; /* btree level */ 2146 xfs_ino_t inum; /* new inode number */ 2147 xfs_dir2_leaf_t *leaf; /* leaf structure */ 2148 xfs_dir2_leaf_entry_t *lep; /* leaf entry being changed */ 2149 int rval; /* internal return value */ 2150 xfs_da_state_t *state; /* btree cursor */ 2151 2152 trace_xfs_dir2_node_replace(args); 2153 2154 /* 2155 * Allocate and initialize the btree cursor. 2156 */ 2157 state = xfs_da_state_alloc(); 2158 state->args = args; 2159 state->mp = args->dp->i_mount; 2160 inum = args->inumber; 2161 /* 2162 * Lookup the entry to change in the btree. 2163 */ 2164 error = xfs_da3_node_lookup_int(state, &rval); 2165 if (error) { 2166 rval = error; 2167 } 2168 /* 2169 * It should be found, since the vnodeops layer has looked it up 2170 * and locked it. But paranoia is good. 2171 */ 2172 if (rval == -EEXIST) { 2173 struct xfs_dir2_leaf_entry *ents; 2174 /* 2175 * Find the leaf entry. 2176 */ 2177 blk = &state->path.blk[state->path.active - 1]; 2178 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC); 2179 leaf = blk->bp->b_addr; 2180 ents = args->dp->d_ops->leaf_ents_p(leaf); 2181 lep = &ents[blk->index]; 2182 ASSERT(state->extravalid); 2183 /* 2184 * Point to the data entry. 2185 */ 2186 hdr = state->extrablk.bp->b_addr; 2187 ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) || 2188 hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC)); 2189 dep = (xfs_dir2_data_entry_t *) 2190 ((char *)hdr + 2191 xfs_dir2_dataptr_to_off(args->geo, 2192 be32_to_cpu(lep->address))); 2193 ASSERT(inum != be64_to_cpu(dep->inumber)); 2194 /* 2195 * Fill in the new inode number and log the entry. 2196 */ 2197 dep->inumber = cpu_to_be64(inum); 2198 args->dp->d_ops->data_put_ftype(dep, args->filetype); 2199 xfs_dir2_data_log_entry(args, state->extrablk.bp, dep); 2200 rval = 0; 2201 } 2202 /* 2203 * Didn't find it, and we're holding a data block. Drop it. 2204 */ 2205 else if (state->extravalid) { 2206 xfs_trans_brelse(args->trans, state->extrablk.bp); 2207 state->extrablk.bp = NULL; 2208 } 2209 /* 2210 * Release all the buffers in the cursor. 2211 */ 2212 for (i = 0; i < state->path.active; i++) { 2213 xfs_trans_brelse(args->trans, state->path.blk[i].bp); 2214 state->path.blk[i].bp = NULL; 2215 } 2216 xfs_da_state_free(state); 2217 return rval; 2218 } 2219 2220 /* 2221 * Trim off a trailing empty freespace block. 2222 * Return (in rvalp) 1 if we did it, 0 if not. 2223 */ 2224 int /* error */ 2225 xfs_dir2_node_trim_free( 2226 xfs_da_args_t *args, /* operation arguments */ 2227 xfs_fileoff_t fo, /* free block number */ 2228 int *rvalp) /* out: did something */ 2229 { 2230 struct xfs_buf *bp; /* freespace buffer */ 2231 xfs_inode_t *dp; /* incore directory inode */ 2232 int error; /* error return code */ 2233 xfs_dir2_free_t *free; /* freespace structure */ 2234 xfs_mount_t *mp; /* filesystem mount point */ 2235 xfs_trans_t *tp; /* transaction pointer */ 2236 struct xfs_dir3_icfree_hdr freehdr; 2237 2238 dp = args->dp; 2239 mp = dp->i_mount; 2240 tp = args->trans; 2241 /* 2242 * Read the freespace block. 2243 */ 2244 error = xfs_dir2_free_try_read(tp, dp, fo, &bp); 2245 if (error) 2246 return error; 2247 /* 2248 * There can be holes in freespace. If fo is a hole, there's 2249 * nothing to do. 2250 */ 2251 if (!bp) 2252 return 0; 2253 free = bp->b_addr; 2254 dp->d_ops->free_hdr_from_disk(&freehdr, free); 2255 2256 /* 2257 * If there are used entries, there's nothing to do. 2258 */ 2259 if (freehdr.nused > 0) { 2260 xfs_trans_brelse(tp, bp); 2261 *rvalp = 0; 2262 return 0; 2263 } 2264 /* 2265 * Blow the block away. 2266 */ 2267 error = xfs_dir2_shrink_inode(args, 2268 xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo), bp); 2269 if (error) { 2270 /* 2271 * Can't fail with ENOSPC since that only happens with no 2272 * space reservation, when breaking up an extent into two 2273 * pieces. This is the last block of an extent. 2274 */ 2275 ASSERT(error != -ENOSPC); 2276 xfs_trans_brelse(tp, bp); 2277 return error; 2278 } 2279 /* 2280 * Return that we succeeded. 2281 */ 2282 *rvalp = 1; 2283 return 0; 2284 } 2285