1 /* 2 * Copyright (c) 2000-2003,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_mount.h" 25 #include "xfs_da_format.h" 26 #include "xfs_da_btree.h" 27 #include "xfs_inode.h" 28 #include "xfs_bmap.h" 29 #include "xfs_dir2.h" 30 #include "xfs_dir2_priv.h" 31 #include "xfs_error.h" 32 #include "xfs_trace.h" 33 #include "xfs_trans.h" 34 #include "xfs_buf_item.h" 35 #include "xfs_cksum.h" 36 37 /* 38 * Local function declarations. 39 */ 40 static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, struct xfs_buf **lbpp, 41 int *indexp, struct xfs_buf **dbpp); 42 static void xfs_dir3_leaf_log_bests(struct xfs_da_args *args, 43 struct xfs_buf *bp, int first, int last); 44 static void xfs_dir3_leaf_log_tail(struct xfs_da_args *args, 45 struct xfs_buf *bp); 46 47 /* 48 * Check the internal consistency of a leaf1 block. 49 * Pop an assert if something is wrong. 50 */ 51 #ifdef DEBUG 52 #define xfs_dir3_leaf_check(dp, bp) \ 53 do { \ 54 if (!xfs_dir3_leaf1_check((dp), (bp))) \ 55 ASSERT(0); \ 56 } while (0); 57 58 STATIC bool 59 xfs_dir3_leaf1_check( 60 struct xfs_inode *dp, 61 struct xfs_buf *bp) 62 { 63 struct xfs_dir2_leaf *leaf = bp->b_addr; 64 struct xfs_dir3_icleaf_hdr leafhdr; 65 66 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 67 68 if (leafhdr.magic == XFS_DIR3_LEAF1_MAGIC) { 69 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr; 70 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn) 71 return false; 72 } else if (leafhdr.magic != XFS_DIR2_LEAF1_MAGIC) 73 return false; 74 75 return xfs_dir3_leaf_check_int(dp->i_mount, dp, &leafhdr, leaf); 76 } 77 #else 78 #define xfs_dir3_leaf_check(dp, bp) 79 #endif 80 81 bool 82 xfs_dir3_leaf_check_int( 83 struct xfs_mount *mp, 84 struct xfs_inode *dp, 85 struct xfs_dir3_icleaf_hdr *hdr, 86 struct xfs_dir2_leaf *leaf) 87 { 88 struct xfs_dir2_leaf_entry *ents; 89 xfs_dir2_leaf_tail_t *ltp; 90 int stale; 91 int i; 92 const struct xfs_dir_ops *ops; 93 struct xfs_dir3_icleaf_hdr leafhdr; 94 struct xfs_da_geometry *geo = mp->m_dir_geo; 95 96 /* 97 * we can be passed a null dp here from a verifier, so we need to go the 98 * hard way to get them. 99 */ 100 ops = xfs_dir_get_ops(mp, dp); 101 102 if (!hdr) { 103 ops->leaf_hdr_from_disk(&leafhdr, leaf); 104 hdr = &leafhdr; 105 } 106 107 ents = ops->leaf_ents_p(leaf); 108 ltp = xfs_dir2_leaf_tail_p(geo, leaf); 109 110 /* 111 * XXX (dgc): This value is not restrictive enough. 112 * Should factor in the size of the bests table as well. 113 * We can deduce a value for that from di_size. 114 */ 115 if (hdr->count > ops->leaf_max_ents(geo)) 116 return false; 117 118 /* Leaves and bests don't overlap in leaf format. */ 119 if ((hdr->magic == XFS_DIR2_LEAF1_MAGIC || 120 hdr->magic == XFS_DIR3_LEAF1_MAGIC) && 121 (char *)&ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp)) 122 return false; 123 124 /* Check hash value order, count stale entries. */ 125 for (i = stale = 0; i < hdr->count; i++) { 126 if (i + 1 < hdr->count) { 127 if (be32_to_cpu(ents[i].hashval) > 128 be32_to_cpu(ents[i + 1].hashval)) 129 return false; 130 } 131 if (ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 132 stale++; 133 } 134 if (hdr->stale != stale) 135 return false; 136 return true; 137 } 138 139 /* 140 * We verify the magic numbers before decoding the leaf header so that on debug 141 * kernels we don't get assertion failures in xfs_dir3_leaf_hdr_from_disk() due 142 * to incorrect magic numbers. 143 */ 144 static bool 145 xfs_dir3_leaf_verify( 146 struct xfs_buf *bp, 147 __uint16_t magic) 148 { 149 struct xfs_mount *mp = bp->b_target->bt_mount; 150 struct xfs_dir2_leaf *leaf = bp->b_addr; 151 152 ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC); 153 154 if (xfs_sb_version_hascrc(&mp->m_sb)) { 155 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr; 156 __uint16_t magic3; 157 158 magic3 = (magic == XFS_DIR2_LEAF1_MAGIC) ? XFS_DIR3_LEAF1_MAGIC 159 : XFS_DIR3_LEAFN_MAGIC; 160 161 if (leaf3->info.hdr.magic != cpu_to_be16(magic3)) 162 return false; 163 if (!uuid_equal(&leaf3->info.uuid, &mp->m_sb.sb_uuid)) 164 return false; 165 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn) 166 return false; 167 } else { 168 if (leaf->hdr.info.magic != cpu_to_be16(magic)) 169 return false; 170 } 171 172 return xfs_dir3_leaf_check_int(mp, NULL, NULL, leaf); 173 } 174 175 static void 176 __read_verify( 177 struct xfs_buf *bp, 178 __uint16_t magic) 179 { 180 struct xfs_mount *mp = bp->b_target->bt_mount; 181 182 if (xfs_sb_version_hascrc(&mp->m_sb) && 183 !xfs_buf_verify_cksum(bp, XFS_DIR3_LEAF_CRC_OFF)) 184 xfs_buf_ioerror(bp, -EFSBADCRC); 185 else if (!xfs_dir3_leaf_verify(bp, magic)) 186 xfs_buf_ioerror(bp, -EFSCORRUPTED); 187 188 if (bp->b_error) 189 xfs_verifier_error(bp); 190 } 191 192 static void 193 __write_verify( 194 struct xfs_buf *bp, 195 __uint16_t magic) 196 { 197 struct xfs_mount *mp = bp->b_target->bt_mount; 198 struct xfs_buf_log_item *bip = bp->b_fspriv; 199 struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr; 200 201 if (!xfs_dir3_leaf_verify(bp, magic)) { 202 xfs_buf_ioerror(bp, -EFSCORRUPTED); 203 xfs_verifier_error(bp); 204 return; 205 } 206 207 if (!xfs_sb_version_hascrc(&mp->m_sb)) 208 return; 209 210 if (bip) 211 hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn); 212 213 xfs_buf_update_cksum(bp, XFS_DIR3_LEAF_CRC_OFF); 214 } 215 216 static void 217 xfs_dir3_leaf1_read_verify( 218 struct xfs_buf *bp) 219 { 220 __read_verify(bp, XFS_DIR2_LEAF1_MAGIC); 221 } 222 223 static void 224 xfs_dir3_leaf1_write_verify( 225 struct xfs_buf *bp) 226 { 227 __write_verify(bp, XFS_DIR2_LEAF1_MAGIC); 228 } 229 230 static void 231 xfs_dir3_leafn_read_verify( 232 struct xfs_buf *bp) 233 { 234 __read_verify(bp, XFS_DIR2_LEAFN_MAGIC); 235 } 236 237 static void 238 xfs_dir3_leafn_write_verify( 239 struct xfs_buf *bp) 240 { 241 __write_verify(bp, XFS_DIR2_LEAFN_MAGIC); 242 } 243 244 const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = { 245 .verify_read = xfs_dir3_leaf1_read_verify, 246 .verify_write = xfs_dir3_leaf1_write_verify, 247 }; 248 249 const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = { 250 .verify_read = xfs_dir3_leafn_read_verify, 251 .verify_write = xfs_dir3_leafn_write_verify, 252 }; 253 254 static int 255 xfs_dir3_leaf_read( 256 struct xfs_trans *tp, 257 struct xfs_inode *dp, 258 xfs_dablk_t fbno, 259 xfs_daddr_t mappedbno, 260 struct xfs_buf **bpp) 261 { 262 int err; 263 264 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp, 265 XFS_DATA_FORK, &xfs_dir3_leaf1_buf_ops); 266 if (!err && tp) 267 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF); 268 return err; 269 } 270 271 int 272 xfs_dir3_leafn_read( 273 struct xfs_trans *tp, 274 struct xfs_inode *dp, 275 xfs_dablk_t fbno, 276 xfs_daddr_t mappedbno, 277 struct xfs_buf **bpp) 278 { 279 int err; 280 281 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp, 282 XFS_DATA_FORK, &xfs_dir3_leafn_buf_ops); 283 if (!err && tp) 284 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF); 285 return err; 286 } 287 288 /* 289 * Initialize a new leaf block, leaf1 or leafn magic accepted. 290 */ 291 static void 292 xfs_dir3_leaf_init( 293 struct xfs_mount *mp, 294 struct xfs_trans *tp, 295 struct xfs_buf *bp, 296 xfs_ino_t owner, 297 __uint16_t type) 298 { 299 struct xfs_dir2_leaf *leaf = bp->b_addr; 300 301 ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC); 302 303 if (xfs_sb_version_hascrc(&mp->m_sb)) { 304 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr; 305 306 memset(leaf3, 0, sizeof(*leaf3)); 307 308 leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC) 309 ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) 310 : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC); 311 leaf3->info.blkno = cpu_to_be64(bp->b_bn); 312 leaf3->info.owner = cpu_to_be64(owner); 313 uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_uuid); 314 } else { 315 memset(leaf, 0, sizeof(*leaf)); 316 leaf->hdr.info.magic = cpu_to_be16(type); 317 } 318 319 /* 320 * If it's a leaf-format directory initialize the tail. 321 * Caller is responsible for initialising the bests table. 322 */ 323 if (type == XFS_DIR2_LEAF1_MAGIC) { 324 struct xfs_dir2_leaf_tail *ltp; 325 326 ltp = xfs_dir2_leaf_tail_p(mp->m_dir_geo, leaf); 327 ltp->bestcount = 0; 328 bp->b_ops = &xfs_dir3_leaf1_buf_ops; 329 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF); 330 } else { 331 bp->b_ops = &xfs_dir3_leafn_buf_ops; 332 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF); 333 } 334 } 335 336 int 337 xfs_dir3_leaf_get_buf( 338 xfs_da_args_t *args, 339 xfs_dir2_db_t bno, 340 struct xfs_buf **bpp, 341 __uint16_t magic) 342 { 343 struct xfs_inode *dp = args->dp; 344 struct xfs_trans *tp = args->trans; 345 struct xfs_mount *mp = dp->i_mount; 346 struct xfs_buf *bp; 347 int error; 348 349 ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC); 350 ASSERT(bno >= xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET) && 351 bno < xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET)); 352 353 error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, bno), 354 -1, &bp, XFS_DATA_FORK); 355 if (error) 356 return error; 357 358 xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic); 359 xfs_dir3_leaf_log_header(args, bp); 360 if (magic == XFS_DIR2_LEAF1_MAGIC) 361 xfs_dir3_leaf_log_tail(args, bp); 362 *bpp = bp; 363 return 0; 364 } 365 366 /* 367 * Convert a block form directory to a leaf form directory. 368 */ 369 int /* error */ 370 xfs_dir2_block_to_leaf( 371 xfs_da_args_t *args, /* operation arguments */ 372 struct xfs_buf *dbp) /* input block's buffer */ 373 { 374 __be16 *bestsp; /* leaf's bestsp entries */ 375 xfs_dablk_t blkno; /* leaf block's bno */ 376 xfs_dir2_data_hdr_t *hdr; /* block header */ 377 xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */ 378 xfs_dir2_block_tail_t *btp; /* block's tail */ 379 xfs_inode_t *dp; /* incore directory inode */ 380 int error; /* error return code */ 381 struct xfs_buf *lbp; /* leaf block's buffer */ 382 xfs_dir2_db_t ldb; /* leaf block's bno */ 383 xfs_dir2_leaf_t *leaf; /* leaf structure */ 384 xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */ 385 int needlog; /* need to log block header */ 386 int needscan; /* need to rescan bestfree */ 387 xfs_trans_t *tp; /* transaction pointer */ 388 struct xfs_dir2_data_free *bf; 389 struct xfs_dir2_leaf_entry *ents; 390 struct xfs_dir3_icleaf_hdr leafhdr; 391 392 trace_xfs_dir2_block_to_leaf(args); 393 394 dp = args->dp; 395 tp = args->trans; 396 /* 397 * Add the leaf block to the inode. 398 * This interface will only put blocks in the leaf/node range. 399 * Since that's empty now, we'll get the root (block 0 in range). 400 */ 401 if ((error = xfs_da_grow_inode(args, &blkno))) { 402 return error; 403 } 404 ldb = xfs_dir2_da_to_db(args->geo, blkno); 405 ASSERT(ldb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET)); 406 /* 407 * Initialize the leaf block, get a buffer for it. 408 */ 409 error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC); 410 if (error) 411 return error; 412 413 leaf = lbp->b_addr; 414 hdr = dbp->b_addr; 415 xfs_dir3_data_check(dp, dbp); 416 btp = xfs_dir2_block_tail_p(args->geo, hdr); 417 blp = xfs_dir2_block_leaf_p(btp); 418 bf = dp->d_ops->data_bestfree_p(hdr); 419 ents = dp->d_ops->leaf_ents_p(leaf); 420 421 /* 422 * Set the counts in the leaf header. 423 */ 424 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 425 leafhdr.count = be32_to_cpu(btp->count); 426 leafhdr.stale = be32_to_cpu(btp->stale); 427 dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr); 428 xfs_dir3_leaf_log_header(args, lbp); 429 430 /* 431 * Could compact these but I think we always do the conversion 432 * after squeezing out stale entries. 433 */ 434 memcpy(ents, blp, be32_to_cpu(btp->count) * sizeof(xfs_dir2_leaf_entry_t)); 435 xfs_dir3_leaf_log_ents(args, lbp, 0, leafhdr.count - 1); 436 needscan = 0; 437 needlog = 1; 438 /* 439 * Make the space formerly occupied by the leaf entries and block 440 * tail be free. 441 */ 442 xfs_dir2_data_make_free(args, dbp, 443 (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr), 444 (xfs_dir2_data_aoff_t)((char *)hdr + args->geo->blksize - 445 (char *)blp), 446 &needlog, &needscan); 447 /* 448 * Fix up the block header, make it a data block. 449 */ 450 dbp->b_ops = &xfs_dir3_data_buf_ops; 451 xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF); 452 if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) 453 hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC); 454 else 455 hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC); 456 457 if (needscan) 458 xfs_dir2_data_freescan(dp, hdr, &needlog); 459 /* 460 * Set up leaf tail and bests table. 461 */ 462 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 463 ltp->bestcount = cpu_to_be32(1); 464 bestsp = xfs_dir2_leaf_bests_p(ltp); 465 bestsp[0] = bf[0].length; 466 /* 467 * Log the data header and leaf bests table. 468 */ 469 if (needlog) 470 xfs_dir2_data_log_header(args, dbp); 471 xfs_dir3_leaf_check(dp, lbp); 472 xfs_dir3_data_check(dp, dbp); 473 xfs_dir3_leaf_log_bests(args, lbp, 0, 0); 474 return 0; 475 } 476 477 STATIC void 478 xfs_dir3_leaf_find_stale( 479 struct xfs_dir3_icleaf_hdr *leafhdr, 480 struct xfs_dir2_leaf_entry *ents, 481 int index, 482 int *lowstale, 483 int *highstale) 484 { 485 /* 486 * Find the first stale entry before our index, if any. 487 */ 488 for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) { 489 if (ents[*lowstale].address == 490 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 491 break; 492 } 493 494 /* 495 * Find the first stale entry at or after our index, if any. 496 * Stop if the result would require moving more entries than using 497 * lowstale. 498 */ 499 for (*highstale = index; *highstale < leafhdr->count; ++*highstale) { 500 if (ents[*highstale].address == 501 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 502 break; 503 if (*lowstale >= 0 && index - *lowstale <= *highstale - index) 504 break; 505 } 506 } 507 508 struct xfs_dir2_leaf_entry * 509 xfs_dir3_leaf_find_entry( 510 struct xfs_dir3_icleaf_hdr *leafhdr, 511 struct xfs_dir2_leaf_entry *ents, 512 int index, /* leaf table position */ 513 int compact, /* need to compact leaves */ 514 int lowstale, /* index of prev stale leaf */ 515 int highstale, /* index of next stale leaf */ 516 int *lfloglow, /* low leaf logging index */ 517 int *lfloghigh) /* high leaf logging index */ 518 { 519 if (!leafhdr->stale) { 520 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */ 521 522 /* 523 * Now we need to make room to insert the leaf entry. 524 * 525 * If there are no stale entries, just insert a hole at index. 526 */ 527 lep = &ents[index]; 528 if (index < leafhdr->count) 529 memmove(lep + 1, lep, 530 (leafhdr->count - index) * sizeof(*lep)); 531 532 /* 533 * Record low and high logging indices for the leaf. 534 */ 535 *lfloglow = index; 536 *lfloghigh = leafhdr->count++; 537 return lep; 538 } 539 540 /* 541 * There are stale entries. 542 * 543 * We will use one of them for the new entry. It's probably not at 544 * the right location, so we'll have to shift some up or down first. 545 * 546 * If we didn't compact before, we need to find the nearest stale 547 * entries before and after our insertion point. 548 */ 549 if (compact == 0) 550 xfs_dir3_leaf_find_stale(leafhdr, ents, index, 551 &lowstale, &highstale); 552 553 /* 554 * If the low one is better, use it. 555 */ 556 if (lowstale >= 0 && 557 (highstale == leafhdr->count || 558 index - lowstale - 1 < highstale - index)) { 559 ASSERT(index - lowstale - 1 >= 0); 560 ASSERT(ents[lowstale].address == 561 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)); 562 563 /* 564 * Copy entries up to cover the stale entry and make room 565 * for the new entry. 566 */ 567 if (index - lowstale - 1 > 0) { 568 memmove(&ents[lowstale], &ents[lowstale + 1], 569 (index - lowstale - 1) * 570 sizeof(xfs_dir2_leaf_entry_t)); 571 } 572 *lfloglow = MIN(lowstale, *lfloglow); 573 *lfloghigh = MAX(index - 1, *lfloghigh); 574 leafhdr->stale--; 575 return &ents[index - 1]; 576 } 577 578 /* 579 * The high one is better, so use that one. 580 */ 581 ASSERT(highstale - index >= 0); 582 ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)); 583 584 /* 585 * Copy entries down to cover the stale entry and make room for the 586 * new entry. 587 */ 588 if (highstale - index > 0) { 589 memmove(&ents[index + 1], &ents[index], 590 (highstale - index) * sizeof(xfs_dir2_leaf_entry_t)); 591 } 592 *lfloglow = MIN(index, *lfloglow); 593 *lfloghigh = MAX(highstale, *lfloghigh); 594 leafhdr->stale--; 595 return &ents[index]; 596 } 597 598 /* 599 * Add an entry to a leaf form directory. 600 */ 601 int /* error */ 602 xfs_dir2_leaf_addname( 603 xfs_da_args_t *args) /* operation arguments */ 604 { 605 __be16 *bestsp; /* freespace table in leaf */ 606 int compact; /* need to compact leaves */ 607 xfs_dir2_data_hdr_t *hdr; /* data block header */ 608 struct xfs_buf *dbp; /* data block buffer */ 609 xfs_dir2_data_entry_t *dep; /* data block entry */ 610 xfs_inode_t *dp; /* incore directory inode */ 611 xfs_dir2_data_unused_t *dup; /* data unused entry */ 612 int error; /* error return value */ 613 int grown; /* allocated new data block */ 614 int highstale; /* index of next stale leaf */ 615 int i; /* temporary, index */ 616 int index; /* leaf table position */ 617 struct xfs_buf *lbp; /* leaf's buffer */ 618 xfs_dir2_leaf_t *leaf; /* leaf structure */ 619 int length; /* length of new entry */ 620 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */ 621 int lfloglow; /* low leaf logging index */ 622 int lfloghigh; /* high leaf logging index */ 623 int lowstale; /* index of prev stale leaf */ 624 xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */ 625 int needbytes; /* leaf block bytes needed */ 626 int needlog; /* need to log data header */ 627 int needscan; /* need to rescan data free */ 628 __be16 *tagp; /* end of data entry */ 629 xfs_trans_t *tp; /* transaction pointer */ 630 xfs_dir2_db_t use_block; /* data block number */ 631 struct xfs_dir2_data_free *bf; /* bestfree table */ 632 struct xfs_dir2_leaf_entry *ents; 633 struct xfs_dir3_icleaf_hdr leafhdr; 634 635 trace_xfs_dir2_leaf_addname(args); 636 637 dp = args->dp; 638 tp = args->trans; 639 640 error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp); 641 if (error) 642 return error; 643 644 /* 645 * Look up the entry by hash value and name. 646 * We know it's not there, our caller has already done a lookup. 647 * So the index is of the entry to insert in front of. 648 * But if there are dup hash values the index is of the first of those. 649 */ 650 index = xfs_dir2_leaf_search_hash(args, lbp); 651 leaf = lbp->b_addr; 652 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 653 ents = dp->d_ops->leaf_ents_p(leaf); 654 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 655 bestsp = xfs_dir2_leaf_bests_p(ltp); 656 length = dp->d_ops->data_entsize(args->namelen); 657 658 /* 659 * See if there are any entries with the same hash value 660 * and space in their block for the new entry. 661 * This is good because it puts multiple same-hash value entries 662 * in a data block, improving the lookup of those entries. 663 */ 664 for (use_block = -1, lep = &ents[index]; 665 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval; 666 index++, lep++) { 667 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR) 668 continue; 669 i = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address)); 670 ASSERT(i < be32_to_cpu(ltp->bestcount)); 671 ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF)); 672 if (be16_to_cpu(bestsp[i]) >= length) { 673 use_block = i; 674 break; 675 } 676 } 677 /* 678 * Didn't find a block yet, linear search all the data blocks. 679 */ 680 if (use_block == -1) { 681 for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) { 682 /* 683 * Remember a block we see that's missing. 684 */ 685 if (bestsp[i] == cpu_to_be16(NULLDATAOFF) && 686 use_block == -1) 687 use_block = i; 688 else if (be16_to_cpu(bestsp[i]) >= length) { 689 use_block = i; 690 break; 691 } 692 } 693 } 694 /* 695 * How many bytes do we need in the leaf block? 696 */ 697 needbytes = 0; 698 if (!leafhdr.stale) 699 needbytes += sizeof(xfs_dir2_leaf_entry_t); 700 if (use_block == -1) 701 needbytes += sizeof(xfs_dir2_data_off_t); 702 703 /* 704 * Now kill use_block if it refers to a missing block, so we 705 * can use it as an indication of allocation needed. 706 */ 707 if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF)) 708 use_block = -1; 709 /* 710 * If we don't have enough free bytes but we can make enough 711 * by compacting out stale entries, we'll do that. 712 */ 713 if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes && 714 leafhdr.stale > 1) 715 compact = 1; 716 717 /* 718 * Otherwise if we don't have enough free bytes we need to 719 * convert to node form. 720 */ 721 else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) { 722 /* 723 * Just checking or no space reservation, give up. 724 */ 725 if ((args->op_flags & XFS_DA_OP_JUSTCHECK) || 726 args->total == 0) { 727 xfs_trans_brelse(tp, lbp); 728 return -ENOSPC; 729 } 730 /* 731 * Convert to node form. 732 */ 733 error = xfs_dir2_leaf_to_node(args, lbp); 734 if (error) 735 return error; 736 /* 737 * Then add the new entry. 738 */ 739 return xfs_dir2_node_addname(args); 740 } 741 /* 742 * Otherwise it will fit without compaction. 743 */ 744 else 745 compact = 0; 746 /* 747 * If just checking, then it will fit unless we needed to allocate 748 * a new data block. 749 */ 750 if (args->op_flags & XFS_DA_OP_JUSTCHECK) { 751 xfs_trans_brelse(tp, lbp); 752 return use_block == -1 ? -ENOSPC : 0; 753 } 754 /* 755 * If no allocations are allowed, return now before we've 756 * changed anything. 757 */ 758 if (args->total == 0 && use_block == -1) { 759 xfs_trans_brelse(tp, lbp); 760 return -ENOSPC; 761 } 762 /* 763 * Need to compact the leaf entries, removing stale ones. 764 * Leave one stale entry behind - the one closest to our 765 * insertion index - and we'll shift that one to our insertion 766 * point later. 767 */ 768 if (compact) { 769 xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale, 770 &highstale, &lfloglow, &lfloghigh); 771 } 772 /* 773 * There are stale entries, so we'll need log-low and log-high 774 * impossibly bad values later. 775 */ 776 else if (leafhdr.stale) { 777 lfloglow = leafhdr.count; 778 lfloghigh = -1; 779 } 780 /* 781 * If there was no data block space found, we need to allocate 782 * a new one. 783 */ 784 if (use_block == -1) { 785 /* 786 * Add the new data block. 787 */ 788 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE, 789 &use_block))) { 790 xfs_trans_brelse(tp, lbp); 791 return error; 792 } 793 /* 794 * Initialize the block. 795 */ 796 if ((error = xfs_dir3_data_init(args, use_block, &dbp))) { 797 xfs_trans_brelse(tp, lbp); 798 return error; 799 } 800 /* 801 * If we're adding a new data block on the end we need to 802 * extend the bests table. Copy it up one entry. 803 */ 804 if (use_block >= be32_to_cpu(ltp->bestcount)) { 805 bestsp--; 806 memmove(&bestsp[0], &bestsp[1], 807 be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0])); 808 be32_add_cpu(<p->bestcount, 1); 809 xfs_dir3_leaf_log_tail(args, lbp); 810 xfs_dir3_leaf_log_bests(args, lbp, 0, 811 be32_to_cpu(ltp->bestcount) - 1); 812 } 813 /* 814 * If we're filling in a previously empty block just log it. 815 */ 816 else 817 xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block); 818 hdr = dbp->b_addr; 819 bf = dp->d_ops->data_bestfree_p(hdr); 820 bestsp[use_block] = bf[0].length; 821 grown = 1; 822 } else { 823 /* 824 * Already had space in some data block. 825 * Just read that one in. 826 */ 827 error = xfs_dir3_data_read(tp, dp, 828 xfs_dir2_db_to_da(args->geo, use_block), 829 -1, &dbp); 830 if (error) { 831 xfs_trans_brelse(tp, lbp); 832 return error; 833 } 834 hdr = dbp->b_addr; 835 bf = dp->d_ops->data_bestfree_p(hdr); 836 grown = 0; 837 } 838 /* 839 * Point to the biggest freespace in our data block. 840 */ 841 dup = (xfs_dir2_data_unused_t *) 842 ((char *)hdr + be16_to_cpu(bf[0].offset)); 843 ASSERT(be16_to_cpu(dup->length) >= length); 844 needscan = needlog = 0; 845 /* 846 * Mark the initial part of our freespace in use for the new entry. 847 */ 848 xfs_dir2_data_use_free(args, dbp, dup, 849 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr), length, 850 &needlog, &needscan); 851 /* 852 * Initialize our new entry (at last). 853 */ 854 dep = (xfs_dir2_data_entry_t *)dup; 855 dep->inumber = cpu_to_be64(args->inumber); 856 dep->namelen = args->namelen; 857 memcpy(dep->name, args->name, dep->namelen); 858 dp->d_ops->data_put_ftype(dep, args->filetype); 859 tagp = dp->d_ops->data_entry_tag_p(dep); 860 *tagp = cpu_to_be16((char *)dep - (char *)hdr); 861 /* 862 * Need to scan fix up the bestfree table. 863 */ 864 if (needscan) 865 xfs_dir2_data_freescan(dp, hdr, &needlog); 866 /* 867 * Need to log the data block's header. 868 */ 869 if (needlog) 870 xfs_dir2_data_log_header(args, dbp); 871 xfs_dir2_data_log_entry(args, dbp, dep); 872 /* 873 * If the bests table needs to be changed, do it. 874 * Log the change unless we've already done that. 875 */ 876 if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) { 877 bestsp[use_block] = bf[0].length; 878 if (!grown) 879 xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block); 880 } 881 882 lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale, 883 highstale, &lfloglow, &lfloghigh); 884 885 /* 886 * Fill in the new leaf entry. 887 */ 888 lep->hashval = cpu_to_be32(args->hashval); 889 lep->address = cpu_to_be32( 890 xfs_dir2_db_off_to_dataptr(args->geo, use_block, 891 be16_to_cpu(*tagp))); 892 /* 893 * Log the leaf fields and give up the buffers. 894 */ 895 dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr); 896 xfs_dir3_leaf_log_header(args, lbp); 897 xfs_dir3_leaf_log_ents(args, lbp, lfloglow, lfloghigh); 898 xfs_dir3_leaf_check(dp, lbp); 899 xfs_dir3_data_check(dp, dbp); 900 return 0; 901 } 902 903 /* 904 * Compact out any stale entries in the leaf. 905 * Log the header and changed leaf entries, if any. 906 */ 907 void 908 xfs_dir3_leaf_compact( 909 xfs_da_args_t *args, /* operation arguments */ 910 struct xfs_dir3_icleaf_hdr *leafhdr, 911 struct xfs_buf *bp) /* leaf buffer */ 912 { 913 int from; /* source leaf index */ 914 xfs_dir2_leaf_t *leaf; /* leaf structure */ 915 int loglow; /* first leaf entry to log */ 916 int to; /* target leaf index */ 917 struct xfs_dir2_leaf_entry *ents; 918 struct xfs_inode *dp = args->dp; 919 920 leaf = bp->b_addr; 921 if (!leafhdr->stale) 922 return; 923 924 /* 925 * Compress out the stale entries in place. 926 */ 927 ents = dp->d_ops->leaf_ents_p(leaf); 928 for (from = to = 0, loglow = -1; from < leafhdr->count; from++) { 929 if (ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 930 continue; 931 /* 932 * Only actually copy the entries that are different. 933 */ 934 if (from > to) { 935 if (loglow == -1) 936 loglow = to; 937 ents[to] = ents[from]; 938 } 939 to++; 940 } 941 /* 942 * Update and log the header, log the leaf entries. 943 */ 944 ASSERT(leafhdr->stale == from - to); 945 leafhdr->count -= leafhdr->stale; 946 leafhdr->stale = 0; 947 948 dp->d_ops->leaf_hdr_to_disk(leaf, leafhdr); 949 xfs_dir3_leaf_log_header(args, bp); 950 if (loglow != -1) 951 xfs_dir3_leaf_log_ents(args, bp, loglow, to - 1); 952 } 953 954 /* 955 * Compact the leaf entries, removing stale ones. 956 * Leave one stale entry behind - the one closest to our 957 * insertion index - and the caller will shift that one to our insertion 958 * point later. 959 * Return new insertion index, where the remaining stale entry is, 960 * and leaf logging indices. 961 */ 962 void 963 xfs_dir3_leaf_compact_x1( 964 struct xfs_dir3_icleaf_hdr *leafhdr, 965 struct xfs_dir2_leaf_entry *ents, 966 int *indexp, /* insertion index */ 967 int *lowstalep, /* out: stale entry before us */ 968 int *highstalep, /* out: stale entry after us */ 969 int *lowlogp, /* out: low log index */ 970 int *highlogp) /* out: high log index */ 971 { 972 int from; /* source copy index */ 973 int highstale; /* stale entry at/after index */ 974 int index; /* insertion index */ 975 int keepstale; /* source index of kept stale */ 976 int lowstale; /* stale entry before index */ 977 int newindex=0; /* new insertion index */ 978 int to; /* destination copy index */ 979 980 ASSERT(leafhdr->stale > 1); 981 index = *indexp; 982 983 xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale); 984 985 /* 986 * Pick the better of lowstale and highstale. 987 */ 988 if (lowstale >= 0 && 989 (highstale == leafhdr->count || 990 index - lowstale <= highstale - index)) 991 keepstale = lowstale; 992 else 993 keepstale = highstale; 994 /* 995 * Copy the entries in place, removing all the stale entries 996 * except keepstale. 997 */ 998 for (from = to = 0; from < leafhdr->count; from++) { 999 /* 1000 * Notice the new value of index. 1001 */ 1002 if (index == from) 1003 newindex = to; 1004 if (from != keepstale && 1005 ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) { 1006 if (from == to) 1007 *lowlogp = to; 1008 continue; 1009 } 1010 /* 1011 * Record the new keepstale value for the insertion. 1012 */ 1013 if (from == keepstale) 1014 lowstale = highstale = to; 1015 /* 1016 * Copy only the entries that have moved. 1017 */ 1018 if (from > to) 1019 ents[to] = ents[from]; 1020 to++; 1021 } 1022 ASSERT(from > to); 1023 /* 1024 * If the insertion point was past the last entry, 1025 * set the new insertion point accordingly. 1026 */ 1027 if (index == from) 1028 newindex = to; 1029 *indexp = newindex; 1030 /* 1031 * Adjust the leaf header values. 1032 */ 1033 leafhdr->count -= from - to; 1034 leafhdr->stale = 1; 1035 /* 1036 * Remember the low/high stale value only in the "right" 1037 * direction. 1038 */ 1039 if (lowstale >= newindex) 1040 lowstale = -1; 1041 else 1042 highstale = leafhdr->count; 1043 *highlogp = leafhdr->count - 1; 1044 *lowstalep = lowstale; 1045 *highstalep = highstale; 1046 } 1047 1048 /* 1049 * Log the bests entries indicated from a leaf1 block. 1050 */ 1051 static void 1052 xfs_dir3_leaf_log_bests( 1053 struct xfs_da_args *args, 1054 struct xfs_buf *bp, /* leaf buffer */ 1055 int first, /* first entry to log */ 1056 int last) /* last entry to log */ 1057 { 1058 __be16 *firstb; /* pointer to first entry */ 1059 __be16 *lastb; /* pointer to last entry */ 1060 struct xfs_dir2_leaf *leaf = bp->b_addr; 1061 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 1062 1063 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) || 1064 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)); 1065 1066 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1067 firstb = xfs_dir2_leaf_bests_p(ltp) + first; 1068 lastb = xfs_dir2_leaf_bests_p(ltp) + last; 1069 xfs_trans_log_buf(args->trans, bp, 1070 (uint)((char *)firstb - (char *)leaf), 1071 (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1)); 1072 } 1073 1074 /* 1075 * Log the leaf entries indicated from a leaf1 or leafn block. 1076 */ 1077 void 1078 xfs_dir3_leaf_log_ents( 1079 struct xfs_da_args *args, 1080 struct xfs_buf *bp, 1081 int first, 1082 int last) 1083 { 1084 xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */ 1085 xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */ 1086 struct xfs_dir2_leaf *leaf = bp->b_addr; 1087 struct xfs_dir2_leaf_entry *ents; 1088 1089 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) || 1090 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) || 1091 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) || 1092 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)); 1093 1094 ents = args->dp->d_ops->leaf_ents_p(leaf); 1095 firstlep = &ents[first]; 1096 lastlep = &ents[last]; 1097 xfs_trans_log_buf(args->trans, bp, 1098 (uint)((char *)firstlep - (char *)leaf), 1099 (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1)); 1100 } 1101 1102 /* 1103 * Log the header of the leaf1 or leafn block. 1104 */ 1105 void 1106 xfs_dir3_leaf_log_header( 1107 struct xfs_da_args *args, 1108 struct xfs_buf *bp) 1109 { 1110 struct xfs_dir2_leaf *leaf = bp->b_addr; 1111 1112 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) || 1113 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) || 1114 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) || 1115 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)); 1116 1117 xfs_trans_log_buf(args->trans, bp, 1118 (uint)((char *)&leaf->hdr - (char *)leaf), 1119 args->dp->d_ops->leaf_hdr_size - 1); 1120 } 1121 1122 /* 1123 * Log the tail of the leaf1 block. 1124 */ 1125 STATIC void 1126 xfs_dir3_leaf_log_tail( 1127 struct xfs_da_args *args, 1128 struct xfs_buf *bp) 1129 { 1130 struct xfs_dir2_leaf *leaf = bp->b_addr; 1131 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 1132 1133 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) || 1134 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) || 1135 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) || 1136 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)); 1137 1138 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1139 xfs_trans_log_buf(args->trans, bp, (uint)((char *)ltp - (char *)leaf), 1140 (uint)(args->geo->blksize - 1)); 1141 } 1142 1143 /* 1144 * Look up the entry referred to by args in the leaf format directory. 1145 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which 1146 * is also used by the node-format code. 1147 */ 1148 int 1149 xfs_dir2_leaf_lookup( 1150 xfs_da_args_t *args) /* operation arguments */ 1151 { 1152 struct xfs_buf *dbp; /* data block buffer */ 1153 xfs_dir2_data_entry_t *dep; /* data block entry */ 1154 xfs_inode_t *dp; /* incore directory inode */ 1155 int error; /* error return code */ 1156 int index; /* found entry index */ 1157 struct xfs_buf *lbp; /* leaf buffer */ 1158 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1159 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1160 xfs_trans_t *tp; /* transaction pointer */ 1161 struct xfs_dir2_leaf_entry *ents; 1162 1163 trace_xfs_dir2_leaf_lookup(args); 1164 1165 /* 1166 * Look up name in the leaf block, returning both buffers and index. 1167 */ 1168 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) { 1169 return error; 1170 } 1171 tp = args->trans; 1172 dp = args->dp; 1173 xfs_dir3_leaf_check(dp, lbp); 1174 leaf = lbp->b_addr; 1175 ents = dp->d_ops->leaf_ents_p(leaf); 1176 /* 1177 * Get to the leaf entry and contained data entry address. 1178 */ 1179 lep = &ents[index]; 1180 1181 /* 1182 * Point to the data entry. 1183 */ 1184 dep = (xfs_dir2_data_entry_t *) 1185 ((char *)dbp->b_addr + 1186 xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address))); 1187 /* 1188 * Return the found inode number & CI name if appropriate 1189 */ 1190 args->inumber = be64_to_cpu(dep->inumber); 1191 args->filetype = dp->d_ops->data_get_ftype(dep); 1192 error = xfs_dir_cilookup_result(args, dep->name, dep->namelen); 1193 xfs_trans_brelse(tp, dbp); 1194 xfs_trans_brelse(tp, lbp); 1195 return error; 1196 } 1197 1198 /* 1199 * Look up name/hash in the leaf block. 1200 * Fill in indexp with the found index, and dbpp with the data buffer. 1201 * If not found dbpp will be NULL, and ENOENT comes back. 1202 * lbpp will always be filled in with the leaf buffer unless there's an error. 1203 */ 1204 static int /* error */ 1205 xfs_dir2_leaf_lookup_int( 1206 xfs_da_args_t *args, /* operation arguments */ 1207 struct xfs_buf **lbpp, /* out: leaf buffer */ 1208 int *indexp, /* out: index in leaf block */ 1209 struct xfs_buf **dbpp) /* out: data buffer */ 1210 { 1211 xfs_dir2_db_t curdb = -1; /* current data block number */ 1212 struct xfs_buf *dbp = NULL; /* data buffer */ 1213 xfs_dir2_data_entry_t *dep; /* data entry */ 1214 xfs_inode_t *dp; /* incore directory inode */ 1215 int error; /* error return code */ 1216 int index; /* index in leaf block */ 1217 struct xfs_buf *lbp; /* leaf buffer */ 1218 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1219 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1220 xfs_mount_t *mp; /* filesystem mount point */ 1221 xfs_dir2_db_t newdb; /* new data block number */ 1222 xfs_trans_t *tp; /* transaction pointer */ 1223 xfs_dir2_db_t cidb = -1; /* case match data block no. */ 1224 enum xfs_dacmp cmp; /* name compare result */ 1225 struct xfs_dir2_leaf_entry *ents; 1226 struct xfs_dir3_icleaf_hdr leafhdr; 1227 1228 dp = args->dp; 1229 tp = args->trans; 1230 mp = dp->i_mount; 1231 1232 error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp); 1233 if (error) 1234 return error; 1235 1236 *lbpp = lbp; 1237 leaf = lbp->b_addr; 1238 xfs_dir3_leaf_check(dp, lbp); 1239 ents = dp->d_ops->leaf_ents_p(leaf); 1240 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 1241 1242 /* 1243 * Look for the first leaf entry with our hash value. 1244 */ 1245 index = xfs_dir2_leaf_search_hash(args, lbp); 1246 /* 1247 * Loop over all the entries with the right hash value 1248 * looking to match the name. 1249 */ 1250 for (lep = &ents[index]; 1251 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval; 1252 lep++, index++) { 1253 /* 1254 * Skip over stale leaf entries. 1255 */ 1256 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR) 1257 continue; 1258 /* 1259 * Get the new data block number. 1260 */ 1261 newdb = xfs_dir2_dataptr_to_db(args->geo, 1262 be32_to_cpu(lep->address)); 1263 /* 1264 * If it's not the same as the old data block number, 1265 * need to pitch the old one and read the new one. 1266 */ 1267 if (newdb != curdb) { 1268 if (dbp) 1269 xfs_trans_brelse(tp, dbp); 1270 error = xfs_dir3_data_read(tp, dp, 1271 xfs_dir2_db_to_da(args->geo, newdb), 1272 -1, &dbp); 1273 if (error) { 1274 xfs_trans_brelse(tp, lbp); 1275 return error; 1276 } 1277 curdb = newdb; 1278 } 1279 /* 1280 * Point to the data entry. 1281 */ 1282 dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr + 1283 xfs_dir2_dataptr_to_off(args->geo, 1284 be32_to_cpu(lep->address))); 1285 /* 1286 * Compare name and if it's an exact match, return the index 1287 * and buffer. If it's the first case-insensitive match, store 1288 * the index and buffer and continue looking for an exact match. 1289 */ 1290 cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen); 1291 if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) { 1292 args->cmpresult = cmp; 1293 *indexp = index; 1294 /* case exact match: return the current buffer. */ 1295 if (cmp == XFS_CMP_EXACT) { 1296 *dbpp = dbp; 1297 return 0; 1298 } 1299 cidb = curdb; 1300 } 1301 } 1302 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT); 1303 /* 1304 * Here, we can only be doing a lookup (not a rename or remove). 1305 * If a case-insensitive match was found earlier, re-read the 1306 * appropriate data block if required and return it. 1307 */ 1308 if (args->cmpresult == XFS_CMP_CASE) { 1309 ASSERT(cidb != -1); 1310 if (cidb != curdb) { 1311 xfs_trans_brelse(tp, dbp); 1312 error = xfs_dir3_data_read(tp, dp, 1313 xfs_dir2_db_to_da(args->geo, cidb), 1314 -1, &dbp); 1315 if (error) { 1316 xfs_trans_brelse(tp, lbp); 1317 return error; 1318 } 1319 } 1320 *dbpp = dbp; 1321 return 0; 1322 } 1323 /* 1324 * No match found, return -ENOENT. 1325 */ 1326 ASSERT(cidb == -1); 1327 if (dbp) 1328 xfs_trans_brelse(tp, dbp); 1329 xfs_trans_brelse(tp, lbp); 1330 return -ENOENT; 1331 } 1332 1333 /* 1334 * Remove an entry from a leaf format directory. 1335 */ 1336 int /* error */ 1337 xfs_dir2_leaf_removename( 1338 xfs_da_args_t *args) /* operation arguments */ 1339 { 1340 __be16 *bestsp; /* leaf block best freespace */ 1341 xfs_dir2_data_hdr_t *hdr; /* data block header */ 1342 xfs_dir2_db_t db; /* data block number */ 1343 struct xfs_buf *dbp; /* data block buffer */ 1344 xfs_dir2_data_entry_t *dep; /* data entry structure */ 1345 xfs_inode_t *dp; /* incore directory inode */ 1346 int error; /* error return code */ 1347 xfs_dir2_db_t i; /* temporary data block # */ 1348 int index; /* index into leaf entries */ 1349 struct xfs_buf *lbp; /* leaf buffer */ 1350 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1351 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1352 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 1353 int needlog; /* need to log data header */ 1354 int needscan; /* need to rescan data frees */ 1355 xfs_dir2_data_off_t oldbest; /* old value of best free */ 1356 struct xfs_dir2_data_free *bf; /* bestfree table */ 1357 struct xfs_dir2_leaf_entry *ents; 1358 struct xfs_dir3_icleaf_hdr leafhdr; 1359 1360 trace_xfs_dir2_leaf_removename(args); 1361 1362 /* 1363 * Lookup the leaf entry, get the leaf and data blocks read in. 1364 */ 1365 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) { 1366 return error; 1367 } 1368 dp = args->dp; 1369 leaf = lbp->b_addr; 1370 hdr = dbp->b_addr; 1371 xfs_dir3_data_check(dp, dbp); 1372 bf = dp->d_ops->data_bestfree_p(hdr); 1373 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 1374 ents = dp->d_ops->leaf_ents_p(leaf); 1375 /* 1376 * Point to the leaf entry, use that to point to the data entry. 1377 */ 1378 lep = &ents[index]; 1379 db = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address)); 1380 dep = (xfs_dir2_data_entry_t *)((char *)hdr + 1381 xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address))); 1382 needscan = needlog = 0; 1383 oldbest = be16_to_cpu(bf[0].length); 1384 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1385 bestsp = xfs_dir2_leaf_bests_p(ltp); 1386 ASSERT(be16_to_cpu(bestsp[db]) == oldbest); 1387 /* 1388 * Mark the former data entry unused. 1389 */ 1390 xfs_dir2_data_make_free(args, dbp, 1391 (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr), 1392 dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan); 1393 /* 1394 * We just mark the leaf entry stale by putting a null in it. 1395 */ 1396 leafhdr.stale++; 1397 dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr); 1398 xfs_dir3_leaf_log_header(args, lbp); 1399 1400 lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR); 1401 xfs_dir3_leaf_log_ents(args, lbp, index, index); 1402 1403 /* 1404 * Scan the freespace in the data block again if necessary, 1405 * log the data block header if necessary. 1406 */ 1407 if (needscan) 1408 xfs_dir2_data_freescan(dp, hdr, &needlog); 1409 if (needlog) 1410 xfs_dir2_data_log_header(args, dbp); 1411 /* 1412 * If the longest freespace in the data block has changed, 1413 * put the new value in the bests table and log that. 1414 */ 1415 if (be16_to_cpu(bf[0].length) != oldbest) { 1416 bestsp[db] = bf[0].length; 1417 xfs_dir3_leaf_log_bests(args, lbp, db, db); 1418 } 1419 xfs_dir3_data_check(dp, dbp); 1420 /* 1421 * If the data block is now empty then get rid of the data block. 1422 */ 1423 if (be16_to_cpu(bf[0].length) == 1424 args->geo->blksize - dp->d_ops->data_entry_offset) { 1425 ASSERT(db != args->geo->datablk); 1426 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) { 1427 /* 1428 * Nope, can't get rid of it because it caused 1429 * allocation of a bmap btree block to do so. 1430 * Just go on, returning success, leaving the 1431 * empty block in place. 1432 */ 1433 if (error == -ENOSPC && args->total == 0) 1434 error = 0; 1435 xfs_dir3_leaf_check(dp, lbp); 1436 return error; 1437 } 1438 dbp = NULL; 1439 /* 1440 * If this is the last data block then compact the 1441 * bests table by getting rid of entries. 1442 */ 1443 if (db == be32_to_cpu(ltp->bestcount) - 1) { 1444 /* 1445 * Look for the last active entry (i). 1446 */ 1447 for (i = db - 1; i > 0; i--) { 1448 if (bestsp[i] != cpu_to_be16(NULLDATAOFF)) 1449 break; 1450 } 1451 /* 1452 * Copy the table down so inactive entries at the 1453 * end are removed. 1454 */ 1455 memmove(&bestsp[db - i], bestsp, 1456 (be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp)); 1457 be32_add_cpu(<p->bestcount, -(db - i)); 1458 xfs_dir3_leaf_log_tail(args, lbp); 1459 xfs_dir3_leaf_log_bests(args, lbp, 0, 1460 be32_to_cpu(ltp->bestcount) - 1); 1461 } else 1462 bestsp[db] = cpu_to_be16(NULLDATAOFF); 1463 } 1464 /* 1465 * If the data block was not the first one, drop it. 1466 */ 1467 else if (db != args->geo->datablk) 1468 dbp = NULL; 1469 1470 xfs_dir3_leaf_check(dp, lbp); 1471 /* 1472 * See if we can convert to block form. 1473 */ 1474 return xfs_dir2_leaf_to_block(args, lbp, dbp); 1475 } 1476 1477 /* 1478 * Replace the inode number in a leaf format directory entry. 1479 */ 1480 int /* error */ 1481 xfs_dir2_leaf_replace( 1482 xfs_da_args_t *args) /* operation arguments */ 1483 { 1484 struct xfs_buf *dbp; /* data block buffer */ 1485 xfs_dir2_data_entry_t *dep; /* data block entry */ 1486 xfs_inode_t *dp; /* incore directory inode */ 1487 int error; /* error return code */ 1488 int index; /* index of leaf entry */ 1489 struct xfs_buf *lbp; /* leaf buffer */ 1490 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1491 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1492 xfs_trans_t *tp; /* transaction pointer */ 1493 struct xfs_dir2_leaf_entry *ents; 1494 1495 trace_xfs_dir2_leaf_replace(args); 1496 1497 /* 1498 * Look up the entry. 1499 */ 1500 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) { 1501 return error; 1502 } 1503 dp = args->dp; 1504 leaf = lbp->b_addr; 1505 ents = dp->d_ops->leaf_ents_p(leaf); 1506 /* 1507 * Point to the leaf entry, get data address from it. 1508 */ 1509 lep = &ents[index]; 1510 /* 1511 * Point to the data entry. 1512 */ 1513 dep = (xfs_dir2_data_entry_t *) 1514 ((char *)dbp->b_addr + 1515 xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address))); 1516 ASSERT(args->inumber != be64_to_cpu(dep->inumber)); 1517 /* 1518 * Put the new inode number in, log it. 1519 */ 1520 dep->inumber = cpu_to_be64(args->inumber); 1521 dp->d_ops->data_put_ftype(dep, args->filetype); 1522 tp = args->trans; 1523 xfs_dir2_data_log_entry(args, dbp, dep); 1524 xfs_dir3_leaf_check(dp, lbp); 1525 xfs_trans_brelse(tp, lbp); 1526 return 0; 1527 } 1528 1529 /* 1530 * Return index in the leaf block (lbp) which is either the first 1531 * one with this hash value, or if there are none, the insert point 1532 * for that hash value. 1533 */ 1534 int /* index value */ 1535 xfs_dir2_leaf_search_hash( 1536 xfs_da_args_t *args, /* operation arguments */ 1537 struct xfs_buf *lbp) /* leaf buffer */ 1538 { 1539 xfs_dahash_t hash=0; /* hash from this entry */ 1540 xfs_dahash_t hashwant; /* hash value looking for */ 1541 int high; /* high leaf index */ 1542 int low; /* low leaf index */ 1543 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1544 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1545 int mid=0; /* current leaf index */ 1546 struct xfs_dir2_leaf_entry *ents; 1547 struct xfs_dir3_icleaf_hdr leafhdr; 1548 1549 leaf = lbp->b_addr; 1550 ents = args->dp->d_ops->leaf_ents_p(leaf); 1551 args->dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 1552 1553 /* 1554 * Note, the table cannot be empty, so we have to go through the loop. 1555 * Binary search the leaf entries looking for our hash value. 1556 */ 1557 for (lep = ents, low = 0, high = leafhdr.count - 1, 1558 hashwant = args->hashval; 1559 low <= high; ) { 1560 mid = (low + high) >> 1; 1561 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant) 1562 break; 1563 if (hash < hashwant) 1564 low = mid + 1; 1565 else 1566 high = mid - 1; 1567 } 1568 /* 1569 * Found one, back up through all the equal hash values. 1570 */ 1571 if (hash == hashwant) { 1572 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) { 1573 mid--; 1574 } 1575 } 1576 /* 1577 * Need to point to an entry higher than ours. 1578 */ 1579 else if (hash < hashwant) 1580 mid++; 1581 return mid; 1582 } 1583 1584 /* 1585 * Trim off a trailing data block. We know it's empty since the leaf 1586 * freespace table says so. 1587 */ 1588 int /* error */ 1589 xfs_dir2_leaf_trim_data( 1590 xfs_da_args_t *args, /* operation arguments */ 1591 struct xfs_buf *lbp, /* leaf buffer */ 1592 xfs_dir2_db_t db) /* data block number */ 1593 { 1594 __be16 *bestsp; /* leaf bests table */ 1595 struct xfs_buf *dbp; /* data block buffer */ 1596 xfs_inode_t *dp; /* incore directory inode */ 1597 int error; /* error return value */ 1598 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1599 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 1600 xfs_trans_t *tp; /* transaction pointer */ 1601 1602 dp = args->dp; 1603 tp = args->trans; 1604 /* 1605 * Read the offending data block. We need its buffer. 1606 */ 1607 error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(args->geo, db), 1608 -1, &dbp); 1609 if (error) 1610 return error; 1611 1612 leaf = lbp->b_addr; 1613 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1614 1615 #ifdef DEBUG 1616 { 1617 struct xfs_dir2_data_hdr *hdr = dbp->b_addr; 1618 struct xfs_dir2_data_free *bf = dp->d_ops->data_bestfree_p(hdr); 1619 1620 ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) || 1621 hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC)); 1622 ASSERT(be16_to_cpu(bf[0].length) == 1623 args->geo->blksize - dp->d_ops->data_entry_offset); 1624 ASSERT(db == be32_to_cpu(ltp->bestcount) - 1); 1625 } 1626 #endif 1627 1628 /* 1629 * Get rid of the data block. 1630 */ 1631 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) { 1632 ASSERT(error != -ENOSPC); 1633 xfs_trans_brelse(tp, dbp); 1634 return error; 1635 } 1636 /* 1637 * Eliminate the last bests entry from the table. 1638 */ 1639 bestsp = xfs_dir2_leaf_bests_p(ltp); 1640 be32_add_cpu(<p->bestcount, -1); 1641 memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp)); 1642 xfs_dir3_leaf_log_tail(args, lbp); 1643 xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1); 1644 return 0; 1645 } 1646 1647 static inline size_t 1648 xfs_dir3_leaf_size( 1649 struct xfs_dir3_icleaf_hdr *hdr, 1650 int counts) 1651 { 1652 int entries; 1653 int hdrsize; 1654 1655 entries = hdr->count - hdr->stale; 1656 if (hdr->magic == XFS_DIR2_LEAF1_MAGIC || 1657 hdr->magic == XFS_DIR2_LEAFN_MAGIC) 1658 hdrsize = sizeof(struct xfs_dir2_leaf_hdr); 1659 else 1660 hdrsize = sizeof(struct xfs_dir3_leaf_hdr); 1661 1662 return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t) 1663 + counts * sizeof(xfs_dir2_data_off_t) 1664 + sizeof(xfs_dir2_leaf_tail_t); 1665 } 1666 1667 /* 1668 * Convert node form directory to leaf form directory. 1669 * The root of the node form dir needs to already be a LEAFN block. 1670 * Just return if we can't do anything. 1671 */ 1672 int /* error */ 1673 xfs_dir2_node_to_leaf( 1674 xfs_da_state_t *state) /* directory operation state */ 1675 { 1676 xfs_da_args_t *args; /* operation arguments */ 1677 xfs_inode_t *dp; /* incore directory inode */ 1678 int error; /* error return code */ 1679 struct xfs_buf *fbp; /* buffer for freespace block */ 1680 xfs_fileoff_t fo; /* freespace file offset */ 1681 xfs_dir2_free_t *free; /* freespace structure */ 1682 struct xfs_buf *lbp; /* buffer for leaf block */ 1683 xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */ 1684 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1685 xfs_mount_t *mp; /* filesystem mount point */ 1686 int rval; /* successful free trim? */ 1687 xfs_trans_t *tp; /* transaction pointer */ 1688 struct xfs_dir3_icleaf_hdr leafhdr; 1689 struct xfs_dir3_icfree_hdr freehdr; 1690 1691 /* 1692 * There's more than a leaf level in the btree, so there must 1693 * be multiple leafn blocks. Give up. 1694 */ 1695 if (state->path.active > 1) 1696 return 0; 1697 args = state->args; 1698 1699 trace_xfs_dir2_node_to_leaf(args); 1700 1701 mp = state->mp; 1702 dp = args->dp; 1703 tp = args->trans; 1704 /* 1705 * Get the last offset in the file. 1706 */ 1707 if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK))) { 1708 return error; 1709 } 1710 fo -= args->geo->fsbcount; 1711 /* 1712 * If there are freespace blocks other than the first one, 1713 * take this opportunity to remove trailing empty freespace blocks 1714 * that may have been left behind during no-space-reservation 1715 * operations. 1716 */ 1717 while (fo > args->geo->freeblk) { 1718 if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) { 1719 return error; 1720 } 1721 if (rval) 1722 fo -= args->geo->fsbcount; 1723 else 1724 return 0; 1725 } 1726 /* 1727 * Now find the block just before the freespace block. 1728 */ 1729 if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) { 1730 return error; 1731 } 1732 /* 1733 * If it's not the single leaf block, give up. 1734 */ 1735 if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + args->geo->blksize) 1736 return 0; 1737 lbp = state->path.blk[0].bp; 1738 leaf = lbp->b_addr; 1739 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf); 1740 1741 ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC || 1742 leafhdr.magic == XFS_DIR3_LEAFN_MAGIC); 1743 1744 /* 1745 * Read the freespace block. 1746 */ 1747 error = xfs_dir2_free_read(tp, dp, args->geo->freeblk, &fbp); 1748 if (error) 1749 return error; 1750 free = fbp->b_addr; 1751 dp->d_ops->free_hdr_from_disk(&freehdr, free); 1752 1753 ASSERT(!freehdr.firstdb); 1754 1755 /* 1756 * Now see if the leafn and free data will fit in a leaf1. 1757 * If not, release the buffer and give up. 1758 */ 1759 if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > args->geo->blksize) { 1760 xfs_trans_brelse(tp, fbp); 1761 return 0; 1762 } 1763 1764 /* 1765 * If the leaf has any stale entries in it, compress them out. 1766 */ 1767 if (leafhdr.stale) 1768 xfs_dir3_leaf_compact(args, &leafhdr, lbp); 1769 1770 lbp->b_ops = &xfs_dir3_leaf1_buf_ops; 1771 xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF); 1772 leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC) 1773 ? XFS_DIR2_LEAF1_MAGIC 1774 : XFS_DIR3_LEAF1_MAGIC; 1775 1776 /* 1777 * Set up the leaf tail from the freespace block. 1778 */ 1779 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1780 ltp->bestcount = cpu_to_be32(freehdr.nvalid); 1781 1782 /* 1783 * Set up the leaf bests table. 1784 */ 1785 memcpy(xfs_dir2_leaf_bests_p(ltp), dp->d_ops->free_bests_p(free), 1786 freehdr.nvalid * sizeof(xfs_dir2_data_off_t)); 1787 1788 dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr); 1789 xfs_dir3_leaf_log_header(args, lbp); 1790 xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1); 1791 xfs_dir3_leaf_log_tail(args, lbp); 1792 xfs_dir3_leaf_check(dp, lbp); 1793 1794 /* 1795 * Get rid of the freespace block. 1796 */ 1797 error = xfs_dir2_shrink_inode(args, 1798 xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET), 1799 fbp); 1800 if (error) { 1801 /* 1802 * This can't fail here because it can only happen when 1803 * punching out the middle of an extent, and this is an 1804 * isolated block. 1805 */ 1806 ASSERT(error != -ENOSPC); 1807 return error; 1808 } 1809 fbp = NULL; 1810 /* 1811 * Now see if we can convert the single-leaf directory 1812 * down to a block form directory. 1813 * This routine always kills the dabuf for the leaf, so 1814 * eliminate it from the path. 1815 */ 1816 error = xfs_dir2_leaf_to_block(args, lbp, NULL); 1817 state->path.blk[0].bp = NULL; 1818 return error; 1819 } 1820