1282 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.4 * Copyright (c) 2013 Red Hat, Inc.5 * All Rights Reserved.6 */7#include "xfs.h"8#include "xfs_fs.h"9#include "xfs_shared.h"10#include "xfs_format.h"11#include "xfs_log_format.h"12#include "xfs_trans_resv.h"13#include "xfs_mount.h"14#include "xfs_inode.h"15#include "xfs_trans.h"16#include "xfs_bmap.h"17#include "xfs_buf_item.h"18#include "xfs_dir2.h"19#include "xfs_dir2_priv.h"20#include "xfs_error.h"21#include "xfs_trace.h"22#include "xfs_log.h"23#include "xfs_health.h"24 25/*26 * Local function prototypes.27 */28static void xfs_dir2_block_log_leaf(xfs_trans_t *tp, struct xfs_buf *bp,29 int first, int last);30static void xfs_dir2_block_log_tail(xfs_trans_t *tp, struct xfs_buf *bp);31static int xfs_dir2_block_lookup_int(xfs_da_args_t *args, struct xfs_buf **bpp,32 int *entno);33static int xfs_dir2_block_sort(const void *a, const void *b);34 35static xfs_dahash_t xfs_dir_hash_dot, xfs_dir_hash_dotdot;36 37/*38 * One-time startup routine called from xfs_init().39 */40void41xfs_dir_startup(void)42{43 xfs_dir_hash_dot = xfs_da_hashname((unsigned char *)".", 1);44 xfs_dir_hash_dotdot = xfs_da_hashname((unsigned char *)"..", 2);45}46 47static xfs_failaddr_t48xfs_dir3_block_verify(49 struct xfs_buf *bp)50{51 struct xfs_mount *mp = bp->b_mount;52 struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr;53 54 if (!xfs_verify_magic(bp, hdr3->magic))55 return __this_address;56 57 if (xfs_has_crc(mp)) {58 if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))59 return __this_address;60 if (be64_to_cpu(hdr3->blkno) != xfs_buf_daddr(bp))61 return __this_address;62 if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->lsn)))63 return __this_address;64 }65 return __xfs_dir3_data_check(NULL, bp);66}67 68static void69xfs_dir3_block_read_verify(70 struct xfs_buf *bp)71{72 struct xfs_mount *mp = bp->b_mount;73 xfs_failaddr_t fa;74 75 if (xfs_has_crc(mp) &&76 !xfs_buf_verify_cksum(bp, XFS_DIR3_DATA_CRC_OFF))77 xfs_verifier_error(bp, -EFSBADCRC, __this_address);78 else {79 fa = xfs_dir3_block_verify(bp);80 if (fa)81 xfs_verifier_error(bp, -EFSCORRUPTED, fa);82 }83}84 85static void86xfs_dir3_block_write_verify(87 struct xfs_buf *bp)88{89 struct xfs_mount *mp = bp->b_mount;90 struct xfs_buf_log_item *bip = bp->b_log_item;91 struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr;92 xfs_failaddr_t fa;93 94 fa = xfs_dir3_block_verify(bp);95 if (fa) {96 xfs_verifier_error(bp, -EFSCORRUPTED, fa);97 return;98 }99 100 if (!xfs_has_crc(mp))101 return;102 103 if (bip)104 hdr3->lsn = cpu_to_be64(bip->bli_item.li_lsn);105 106 xfs_buf_update_cksum(bp, XFS_DIR3_DATA_CRC_OFF);107}108 109const struct xfs_buf_ops xfs_dir3_block_buf_ops = {110 .name = "xfs_dir3_block",111 .magic = { cpu_to_be32(XFS_DIR2_BLOCK_MAGIC),112 cpu_to_be32(XFS_DIR3_BLOCK_MAGIC) },113 .verify_read = xfs_dir3_block_read_verify,114 .verify_write = xfs_dir3_block_write_verify,115 .verify_struct = xfs_dir3_block_verify,116};117 118xfs_failaddr_t119xfs_dir3_block_header_check(120 struct xfs_buf *bp,121 xfs_ino_t owner)122{123 struct xfs_mount *mp = bp->b_mount;124 125 if (xfs_has_crc(mp)) {126 struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr;127 128 if (hdr3->magic != cpu_to_be32(XFS_DIR3_BLOCK_MAGIC))129 return __this_address;130 131 if (be64_to_cpu(hdr3->owner) != owner)132 return __this_address;133 }134 135 return NULL;136}137 138int139xfs_dir3_block_read(140 struct xfs_trans *tp,141 struct xfs_inode *dp,142 xfs_ino_t owner,143 struct xfs_buf **bpp)144{145 struct xfs_mount *mp = dp->i_mount;146 xfs_failaddr_t fa;147 int err;148 149 err = xfs_da_read_buf(tp, dp, mp->m_dir_geo->datablk, 0, bpp,150 XFS_DATA_FORK, &xfs_dir3_block_buf_ops);151 if (err || !*bpp)152 return err;153 154 /* Check things that we can't do in the verifier. */155 fa = xfs_dir3_block_header_check(*bpp, owner);156 if (fa) {157 __xfs_buf_mark_corrupt(*bpp, fa);158 xfs_trans_brelse(tp, *bpp);159 *bpp = NULL;160 xfs_dirattr_mark_sick(dp, XFS_DATA_FORK);161 return -EFSCORRUPTED;162 }163 164 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_BLOCK_BUF);165 return err;166}167 168static void169xfs_dir3_block_init(170 struct xfs_da_args *args,171 struct xfs_buf *bp)172{173 struct xfs_trans *tp = args->trans;174 struct xfs_inode *dp = args->dp;175 struct xfs_mount *mp = dp->i_mount;176 struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr;177 178 bp->b_ops = &xfs_dir3_block_buf_ops;179 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_BLOCK_BUF);180 181 if (xfs_has_crc(mp)) {182 memset(hdr3, 0, sizeof(*hdr3));183 hdr3->magic = cpu_to_be32(XFS_DIR3_BLOCK_MAGIC);184 hdr3->blkno = cpu_to_be64(xfs_buf_daddr(bp));185 hdr3->owner = cpu_to_be64(args->owner);186 uuid_copy(&hdr3->uuid, &mp->m_sb.sb_meta_uuid);187 return;188 189 }190 hdr3->magic = cpu_to_be32(XFS_DIR2_BLOCK_MAGIC);191}192 193static void194xfs_dir2_block_need_space(195 struct xfs_inode *dp,196 struct xfs_dir2_data_hdr *hdr,197 struct xfs_dir2_block_tail *btp,198 struct xfs_dir2_leaf_entry *blp,199 __be16 **tagpp,200 struct xfs_dir2_data_unused **dupp,201 struct xfs_dir2_data_unused **enddupp,202 int *compact,203 int len)204{205 struct xfs_dir2_data_free *bf;206 __be16 *tagp = NULL;207 struct xfs_dir2_data_unused *dup = NULL;208 struct xfs_dir2_data_unused *enddup = NULL;209 210 *compact = 0;211 bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);212 213 /*214 * If there are stale entries we'll use one for the leaf.215 */216 if (btp->stale) {217 if (be16_to_cpu(bf[0].length) >= len) {218 /*219 * The biggest entry enough to avoid compaction.220 */221 dup = (xfs_dir2_data_unused_t *)222 ((char *)hdr + be16_to_cpu(bf[0].offset));223 goto out;224 }225 226 /*227 * Will need to compact to make this work.228 * Tag just before the first leaf entry.229 */230 *compact = 1;231 tagp = (__be16 *)blp - 1;232 233 /* Data object just before the first leaf entry. */234 dup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));235 236 /*237 * If it's not free then the data will go where the238 * leaf data starts now, if it works at all.239 */240 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {241 if (be16_to_cpu(dup->length) + (be32_to_cpu(btp->stale) - 1) *242 (uint)sizeof(*blp) < len)243 dup = NULL;244 } else if ((be32_to_cpu(btp->stale) - 1) * (uint)sizeof(*blp) < len)245 dup = NULL;246 else247 dup = (xfs_dir2_data_unused_t *)blp;248 goto out;249 }250 251 /*252 * no stale entries, so just use free space.253 * Tag just before the first leaf entry.254 */255 tagp = (__be16 *)blp - 1;256 257 /* Data object just before the first leaf entry. */258 enddup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));259 260 /*261 * If it's not free then can't do this add without cleaning up:262 * the space before the first leaf entry needs to be free so it263 * can be expanded to hold the pointer to the new entry.264 */265 if (be16_to_cpu(enddup->freetag) == XFS_DIR2_DATA_FREE_TAG) {266 /*267 * Check out the biggest freespace and see if it's the same one.268 */269 dup = (xfs_dir2_data_unused_t *)270 ((char *)hdr + be16_to_cpu(bf[0].offset));271 if (dup != enddup) {272 /*273 * Not the same free entry, just check its length.274 */275 if (be16_to_cpu(dup->length) < len)276 dup = NULL;277 goto out;278 }279 280 /*281 * It is the biggest freespace, can it hold the leaf too?282 */283 if (be16_to_cpu(dup->length) < len + (uint)sizeof(*blp)) {284 /*285 * Yes, use the second-largest entry instead if it works.286 */287 if (be16_to_cpu(bf[1].length) >= len)288 dup = (xfs_dir2_data_unused_t *)289 ((char *)hdr + be16_to_cpu(bf[1].offset));290 else291 dup = NULL;292 }293 }294out:295 *tagpp = tagp;296 *dupp = dup;297 *enddupp = enddup;298}299 300/*301 * compact the leaf entries.302 * Leave the highest-numbered stale entry stale.303 * XXX should be the one closest to mid but mid is not yet computed.304 */305static void306xfs_dir2_block_compact(307 struct xfs_da_args *args,308 struct xfs_buf *bp,309 struct xfs_dir2_data_hdr *hdr,310 struct xfs_dir2_block_tail *btp,311 struct xfs_dir2_leaf_entry *blp,312 int *needlog,313 int *lfloghigh,314 int *lfloglow)315{316 int fromidx; /* source leaf index */317 int toidx; /* target leaf index */318 int needscan = 0;319 int highstale; /* high stale index */320 321 fromidx = toidx = be32_to_cpu(btp->count) - 1;322 highstale = *lfloghigh = -1;323 for (; fromidx >= 0; fromidx--) {324 if (blp[fromidx].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {325 if (highstale == -1)326 highstale = toidx;327 else {328 if (*lfloghigh == -1)329 *lfloghigh = toidx;330 continue;331 }332 }333 if (fromidx < toidx)334 blp[toidx] = blp[fromidx];335 toidx--;336 }337 *lfloglow = toidx + 1 - (be32_to_cpu(btp->stale) - 1);338 *lfloghigh -= be32_to_cpu(btp->stale) - 1;339 be32_add_cpu(&btp->count, -(be32_to_cpu(btp->stale) - 1));340 xfs_dir2_data_make_free(args, bp,341 (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),342 (xfs_dir2_data_aoff_t)((be32_to_cpu(btp->stale) - 1) * sizeof(*blp)),343 needlog, &needscan);344 btp->stale = cpu_to_be32(1);345 /*346 * If we now need to rebuild the bestfree map, do so.347 * This needs to happen before the next call to use_free.348 */349 if (needscan)350 xfs_dir2_data_freescan(args->dp->i_mount, hdr, needlog);351}352 353/*354 * Add an entry to a block directory.355 */356int /* error */357xfs_dir2_block_addname(358 xfs_da_args_t *args) /* directory op arguments */359{360 xfs_dir2_data_hdr_t *hdr; /* block header */361 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */362 struct xfs_buf *bp; /* buffer for block */363 xfs_dir2_block_tail_t *btp; /* block tail */364 int compact; /* need to compact leaf ents */365 xfs_dir2_data_entry_t *dep; /* block data entry */366 xfs_inode_t *dp; /* directory inode */367 xfs_dir2_data_unused_t *dup; /* block unused entry */368 int error; /* error return value */369 xfs_dir2_data_unused_t *enddup=NULL; /* unused at end of data */370 xfs_dahash_t hash; /* hash value of found entry */371 int high; /* high index for binary srch */372 int highstale; /* high stale index */373 int lfloghigh=0; /* last final leaf to log */374 int lfloglow=0; /* first final leaf to log */375 int len; /* length of the new entry */376 int low; /* low index for binary srch */377 int lowstale; /* low stale index */378 int mid=0; /* midpoint for binary srch */379 int needlog; /* need to log header */380 int needscan; /* need to rescan freespace */381 __be16 *tagp; /* pointer to tag value */382 xfs_trans_t *tp; /* transaction structure */383 384 trace_xfs_dir2_block_addname(args);385 386 dp = args->dp;387 tp = args->trans;388 389 /* Read the (one and only) directory block into bp. */390 error = xfs_dir3_block_read(tp, dp, args->owner, &bp);391 if (error)392 return error;393 394 len = xfs_dir2_data_entsize(dp->i_mount, args->namelen);395 396 /*397 * Set up pointers to parts of the block.398 */399 hdr = bp->b_addr;400 btp = xfs_dir2_block_tail_p(args->geo, hdr);401 blp = xfs_dir2_block_leaf_p(btp);402 403 /*404 * Find out if we can reuse stale entries or whether we need extra405 * space for entry and new leaf.406 */407 xfs_dir2_block_need_space(dp, hdr, btp, blp, &tagp, &dup,408 &enddup, &compact, len);409 410 /*411 * Done everything we need for a space check now.412 */413 if (args->op_flags & XFS_DA_OP_JUSTCHECK) {414 xfs_trans_brelse(tp, bp);415 if (!dup)416 return -ENOSPC;417 return 0;418 }419 420 /*421 * If we don't have space for the new entry & leaf ...422 */423 if (!dup) {424 /* Don't have a space reservation: return no-space. */425 if (args->total == 0)426 return -ENOSPC;427 /*428 * Convert to the next larger format.429 * Then add the new entry in that format.430 */431 error = xfs_dir2_block_to_leaf(args, bp);432 if (error)433 return error;434 return xfs_dir2_leaf_addname(args);435 }436 437 needlog = needscan = 0;438 439 /*440 * If need to compact the leaf entries, do it now.441 */442 if (compact) {443 xfs_dir2_block_compact(args, bp, hdr, btp, blp, &needlog,444 &lfloghigh, &lfloglow);445 /* recalculate blp post-compaction */446 blp = xfs_dir2_block_leaf_p(btp);447 } else if (btp->stale) {448 /*449 * Set leaf logging boundaries to impossible state.450 * For the no-stale case they're set explicitly.451 */452 lfloglow = be32_to_cpu(btp->count);453 lfloghigh = -1;454 }455 456 /*457 * Find the slot that's first lower than our hash value, -1 if none.458 */459 for (low = 0, high = be32_to_cpu(btp->count) - 1; low <= high; ) {460 mid = (low + high) >> 1;461 if ((hash = be32_to_cpu(blp[mid].hashval)) == args->hashval)462 break;463 if (hash < args->hashval)464 low = mid + 1;465 else466 high = mid - 1;467 }468 while (mid >= 0 && be32_to_cpu(blp[mid].hashval) >= args->hashval) {469 mid--;470 }471 /*472 * No stale entries, will use enddup space to hold new leaf.473 */474 if (!btp->stale) {475 xfs_dir2_data_aoff_t aoff;476 477 /*478 * Mark the space needed for the new leaf entry, now in use.479 */480 aoff = (xfs_dir2_data_aoff_t)((char *)enddup - (char *)hdr +481 be16_to_cpu(enddup->length) - sizeof(*blp));482 error = xfs_dir2_data_use_free(args, bp, enddup, aoff,483 (xfs_dir2_data_aoff_t)sizeof(*blp), &needlog,484 &needscan);485 if (error)486 return error;487 488 /*489 * Update the tail (entry count).490 */491 be32_add_cpu(&btp->count, 1);492 /*493 * If we now need to rebuild the bestfree map, do so.494 * This needs to happen before the next call to use_free.495 */496 if (needscan) {497 xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);498 needscan = 0;499 }500 /*501 * Adjust pointer to the first leaf entry, we're about to move502 * the table up one to open up space for the new leaf entry.503 * Then adjust our index to match.504 */505 blp--;506 mid++;507 if (mid)508 memmove(blp, &blp[1], mid * sizeof(*blp));509 lfloglow = 0;510 lfloghigh = mid;511 }512 /*513 * Use a stale leaf for our new entry.514 */515 else {516 for (lowstale = mid;517 lowstale >= 0 &&518 blp[lowstale].address !=519 cpu_to_be32(XFS_DIR2_NULL_DATAPTR);520 lowstale--)521 continue;522 for (highstale = mid + 1;523 highstale < be32_to_cpu(btp->count) &&524 blp[highstale].address !=525 cpu_to_be32(XFS_DIR2_NULL_DATAPTR) &&526 (lowstale < 0 || mid - lowstale > highstale - mid);527 highstale++)528 continue;529 /*530 * Move entries toward the low-numbered stale entry.531 */532 if (lowstale >= 0 &&533 (highstale == be32_to_cpu(btp->count) ||534 mid - lowstale <= highstale - mid)) {535 if (mid - lowstale)536 memmove(&blp[lowstale], &blp[lowstale + 1],537 (mid - lowstale) * sizeof(*blp));538 lfloglow = min(lowstale, lfloglow);539 lfloghigh = max(mid, lfloghigh);540 }541 /*542 * Move entries toward the high-numbered stale entry.543 */544 else {545 ASSERT(highstale < be32_to_cpu(btp->count));546 mid++;547 if (highstale - mid)548 memmove(&blp[mid + 1], &blp[mid],549 (highstale - mid) * sizeof(*blp));550 lfloglow = min(mid, lfloglow);551 lfloghigh = max(highstale, lfloghigh);552 }553 be32_add_cpu(&btp->stale, -1);554 }555 /*556 * Point to the new data entry.557 */558 dep = (xfs_dir2_data_entry_t *)dup;559 /*560 * Fill in the leaf entry.561 */562 blp[mid].hashval = cpu_to_be32(args->hashval);563 blp[mid].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(564 (char *)dep - (char *)hdr));565 xfs_dir2_block_log_leaf(tp, bp, lfloglow, lfloghigh);566 /*567 * Mark space for the data entry used.568 */569 error = xfs_dir2_data_use_free(args, bp, dup,570 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),571 (xfs_dir2_data_aoff_t)len, &needlog, &needscan);572 if (error)573 return error;574 /*575 * Create the new data entry.576 */577 dep->inumber = cpu_to_be64(args->inumber);578 dep->namelen = args->namelen;579 memcpy(dep->name, args->name, args->namelen);580 xfs_dir2_data_put_ftype(dp->i_mount, dep, args->filetype);581 tagp = xfs_dir2_data_entry_tag_p(dp->i_mount, dep);582 *tagp = cpu_to_be16((char *)dep - (char *)hdr);583 /*584 * Clean up the bestfree array and log the header, tail, and entry.585 */586 if (needscan)587 xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);588 if (needlog)589 xfs_dir2_data_log_header(args, bp);590 xfs_dir2_block_log_tail(tp, bp);591 xfs_dir2_data_log_entry(args, bp, dep);592 xfs_dir3_data_check(dp, bp);593 return 0;594}595 596/*597 * Log leaf entries from the block.598 */599static void600xfs_dir2_block_log_leaf(601 xfs_trans_t *tp, /* transaction structure */602 struct xfs_buf *bp, /* block buffer */603 int first, /* index of first logged leaf */604 int last) /* index of last logged leaf */605{606 xfs_dir2_data_hdr_t *hdr = bp->b_addr;607 xfs_dir2_leaf_entry_t *blp;608 xfs_dir2_block_tail_t *btp;609 610 btp = xfs_dir2_block_tail_p(tp->t_mountp->m_dir_geo, hdr);611 blp = xfs_dir2_block_leaf_p(btp);612 xfs_trans_log_buf(tp, bp, (uint)((char *)&blp[first] - (char *)hdr),613 (uint)((char *)&blp[last + 1] - (char *)hdr - 1));614}615 616/*617 * Log the block tail.618 */619static void620xfs_dir2_block_log_tail(621 xfs_trans_t *tp, /* transaction structure */622 struct xfs_buf *bp) /* block buffer */623{624 xfs_dir2_data_hdr_t *hdr = bp->b_addr;625 xfs_dir2_block_tail_t *btp;626 627 btp = xfs_dir2_block_tail_p(tp->t_mountp->m_dir_geo, hdr);628 xfs_trans_log_buf(tp, bp, (uint)((char *)btp - (char *)hdr),629 (uint)((char *)(btp + 1) - (char *)hdr - 1));630}631 632/*633 * Look up an entry in the block. This is the external routine,634 * xfs_dir2_block_lookup_int does the real work.635 */636int /* error */637xfs_dir2_block_lookup(638 xfs_da_args_t *args) /* dir lookup arguments */639{640 xfs_dir2_data_hdr_t *hdr; /* block header */641 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */642 struct xfs_buf *bp; /* block buffer */643 xfs_dir2_block_tail_t *btp; /* block tail */644 xfs_dir2_data_entry_t *dep; /* block data entry */645 xfs_inode_t *dp; /* incore inode */646 int ent; /* entry index */647 int error; /* error return value */648 649 trace_xfs_dir2_block_lookup(args);650 651 /*652 * Get the buffer, look up the entry.653 * If not found (ENOENT) then return, have no buffer.654 */655 if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent)))656 return error;657 dp = args->dp;658 hdr = bp->b_addr;659 xfs_dir3_data_check(dp, bp);660 btp = xfs_dir2_block_tail_p(args->geo, hdr);661 blp = xfs_dir2_block_leaf_p(btp);662 /*663 * Get the offset from the leaf entry, to point to the data.664 */665 dep = (xfs_dir2_data_entry_t *)((char *)hdr +666 xfs_dir2_dataptr_to_off(args->geo,667 be32_to_cpu(blp[ent].address)));668 /*669 * Fill in inode number, CI name if appropriate, release the block.670 */671 args->inumber = be64_to_cpu(dep->inumber);672 args->filetype = xfs_dir2_data_get_ftype(dp->i_mount, dep);673 error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);674 xfs_trans_brelse(args->trans, bp);675 return error;676}677 678/*679 * Internal block lookup routine.680 */681static int /* error */682xfs_dir2_block_lookup_int(683 xfs_da_args_t *args, /* dir lookup arguments */684 struct xfs_buf **bpp, /* returned block buffer */685 int *entno) /* returned entry number */686{687 xfs_dir2_dataptr_t addr; /* data entry address */688 xfs_dir2_data_hdr_t *hdr; /* block header */689 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */690 struct xfs_buf *bp; /* block buffer */691 xfs_dir2_block_tail_t *btp; /* block tail */692 xfs_dir2_data_entry_t *dep; /* block data entry */693 xfs_inode_t *dp; /* incore inode */694 int error; /* error return value */695 xfs_dahash_t hash; /* found hash value */696 int high; /* binary search high index */697 int low; /* binary search low index */698 int mid; /* binary search current idx */699 xfs_trans_t *tp; /* transaction pointer */700 enum xfs_dacmp cmp; /* comparison result */701 702 dp = args->dp;703 tp = args->trans;704 705 error = xfs_dir3_block_read(tp, dp, args->owner, &bp);706 if (error)707 return error;708 709 hdr = bp->b_addr;710 xfs_dir3_data_check(dp, bp);711 btp = xfs_dir2_block_tail_p(args->geo, hdr);712 blp = xfs_dir2_block_leaf_p(btp);713 /*714 * Loop doing a binary search for our hash value.715 * Find our entry, ENOENT if it's not there.716 */717 for (low = 0, high = be32_to_cpu(btp->count) - 1; ; ) {718 ASSERT(low <= high);719 mid = (low + high) >> 1;720 if ((hash = be32_to_cpu(blp[mid].hashval)) == args->hashval)721 break;722 if (hash < args->hashval)723 low = mid + 1;724 else725 high = mid - 1;726 if (low > high) {727 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);728 xfs_trans_brelse(tp, bp);729 return -ENOENT;730 }731 }732 /*733 * Back up to the first one with the right hash value.734 */735 while (mid > 0 && be32_to_cpu(blp[mid - 1].hashval) == args->hashval) {736 mid--;737 }738 /*739 * Now loop forward through all the entries with the740 * right hash value looking for our name.741 */742 do {743 if ((addr = be32_to_cpu(blp[mid].address)) == XFS_DIR2_NULL_DATAPTR)744 continue;745 /*746 * Get pointer to the entry from the leaf.747 */748 dep = (xfs_dir2_data_entry_t *)749 ((char *)hdr + xfs_dir2_dataptr_to_off(args->geo, addr));750 /*751 * Compare name and if it's an exact match, return the index752 * and buffer. If it's the first case-insensitive match, store753 * the index and buffer and continue looking for an exact match.754 */755 cmp = xfs_dir2_compname(args, dep->name, dep->namelen);756 if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {757 args->cmpresult = cmp;758 *bpp = bp;759 *entno = mid;760 if (cmp == XFS_CMP_EXACT)761 return 0;762 }763 } while (++mid < be32_to_cpu(btp->count) &&764 be32_to_cpu(blp[mid].hashval) == hash);765 766 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);767 /*768 * Here, we can only be doing a lookup (not a rename or replace).769 * If a case-insensitive match was found earlier, return success.770 */771 if (args->cmpresult == XFS_CMP_CASE)772 return 0;773 /*774 * No match, release the buffer and return ENOENT.775 */776 xfs_trans_brelse(tp, bp);777 return -ENOENT;778}779 780/*781 * Remove an entry from a block format directory.782 * If that makes the block small enough to fit in shortform, transform it.783 */784int /* error */785xfs_dir2_block_removename(786 xfs_da_args_t *args) /* directory operation args */787{788 xfs_dir2_data_hdr_t *hdr; /* block header */789 xfs_dir2_leaf_entry_t *blp; /* block leaf pointer */790 struct xfs_buf *bp; /* block buffer */791 xfs_dir2_block_tail_t *btp; /* block tail */792 xfs_dir2_data_entry_t *dep; /* block data entry */793 xfs_inode_t *dp; /* incore inode */794 int ent; /* block leaf entry index */795 int error; /* error return value */796 int needlog; /* need to log block header */797 int needscan; /* need to fixup bestfree */798 xfs_dir2_sf_hdr_t sfh; /* shortform header */799 int size; /* shortform size */800 xfs_trans_t *tp; /* transaction pointer */801 802 trace_xfs_dir2_block_removename(args);803 804 /*805 * Look up the entry in the block. Gets the buffer and entry index.806 * It will always be there, the vnodeops level does a lookup first.807 */808 if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent))) {809 return error;810 }811 dp = args->dp;812 tp = args->trans;813 hdr = bp->b_addr;814 btp = xfs_dir2_block_tail_p(args->geo, hdr);815 blp = xfs_dir2_block_leaf_p(btp);816 /*817 * Point to the data entry using the leaf entry.818 */819 dep = (xfs_dir2_data_entry_t *)((char *)hdr +820 xfs_dir2_dataptr_to_off(args->geo,821 be32_to_cpu(blp[ent].address)));822 /*823 * Mark the data entry's space free.824 */825 needlog = needscan = 0;826 xfs_dir2_data_make_free(args, bp,827 (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),828 xfs_dir2_data_entsize(dp->i_mount, dep->namelen), &needlog,829 &needscan);830 /*831 * Fix up the block tail.832 */833 be32_add_cpu(&btp->stale, 1);834 xfs_dir2_block_log_tail(tp, bp);835 /*836 * Remove the leaf entry by marking it stale.837 */838 blp[ent].address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);839 xfs_dir2_block_log_leaf(tp, bp, ent, ent);840 /*841 * Fix up bestfree, log the header if necessary.842 */843 if (needscan)844 xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);845 if (needlog)846 xfs_dir2_data_log_header(args, bp);847 xfs_dir3_data_check(dp, bp);848 /*849 * See if the size as a shortform is good enough.850 */851 size = xfs_dir2_block_sfsize(dp, hdr, &sfh);852 if (size > xfs_inode_data_fork_size(dp))853 return 0;854 855 /*856 * If it works, do the conversion.857 */858 return xfs_dir2_block_to_sf(args, bp, size, &sfh);859}860 861/*862 * Replace an entry in a V2 block directory.863 * Change the inode number to the new value.864 */865int /* error */866xfs_dir2_block_replace(867 xfs_da_args_t *args) /* directory operation args */868{869 xfs_dir2_data_hdr_t *hdr; /* block header */870 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */871 struct xfs_buf *bp; /* block buffer */872 xfs_dir2_block_tail_t *btp; /* block tail */873 xfs_dir2_data_entry_t *dep; /* block data entry */874 xfs_inode_t *dp; /* incore inode */875 int ent; /* leaf entry index */876 int error; /* error return value */877 878 trace_xfs_dir2_block_replace(args);879 880 /*881 * Lookup the entry in the directory. Get buffer and entry index.882 * This will always succeed since the caller has already done a lookup.883 */884 if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent))) {885 return error;886 }887 dp = args->dp;888 hdr = bp->b_addr;889 btp = xfs_dir2_block_tail_p(args->geo, hdr);890 blp = xfs_dir2_block_leaf_p(btp);891 /*892 * Point to the data entry we need to change.893 */894 dep = (xfs_dir2_data_entry_t *)((char *)hdr +895 xfs_dir2_dataptr_to_off(args->geo,896 be32_to_cpu(blp[ent].address)));897 ASSERT(be64_to_cpu(dep->inumber) != args->inumber);898 /*899 * Change the inode number to the new value.900 */901 dep->inumber = cpu_to_be64(args->inumber);902 xfs_dir2_data_put_ftype(dp->i_mount, dep, args->filetype);903 xfs_dir2_data_log_entry(args, bp, dep);904 xfs_dir3_data_check(dp, bp);905 return 0;906}907 908/*909 * Qsort comparison routine for the block leaf entries.910 */911static int /* sort order */912xfs_dir2_block_sort(913 const void *a, /* first leaf entry */914 const void *b) /* second leaf entry */915{916 const xfs_dir2_leaf_entry_t *la; /* first leaf entry */917 const xfs_dir2_leaf_entry_t *lb; /* second leaf entry */918 919 la = a;920 lb = b;921 return be32_to_cpu(la->hashval) < be32_to_cpu(lb->hashval) ? -1 :922 (be32_to_cpu(la->hashval) > be32_to_cpu(lb->hashval) ? 1 : 0);923}924 925/*926 * Convert a V2 leaf directory to a V2 block directory if possible.927 */928int /* error */929xfs_dir2_leaf_to_block(930 xfs_da_args_t *args, /* operation arguments */931 struct xfs_buf *lbp, /* leaf buffer */932 struct xfs_buf *dbp) /* data buffer */933{934 __be16 *bestsp; /* leaf bests table */935 xfs_dir2_data_hdr_t *hdr; /* block header */936 xfs_dir2_block_tail_t *btp; /* block tail */937 xfs_inode_t *dp; /* incore directory inode */938 xfs_dir2_data_unused_t *dup; /* unused data entry */939 int error; /* error return value */940 int from; /* leaf from index */941 xfs_dir2_leaf_t *leaf; /* leaf structure */942 xfs_dir2_leaf_entry_t *lep; /* leaf entry */943 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */944 xfs_mount_t *mp; /* file system mount point */945 int needlog; /* need to log data header */946 int needscan; /* need to scan for bestfree */947 xfs_dir2_sf_hdr_t sfh; /* shortform header */948 int size; /* bytes used */949 __be16 *tagp; /* end of entry (tag) */950 int to; /* block/leaf to index */951 xfs_trans_t *tp; /* transaction pointer */952 struct xfs_dir3_icleaf_hdr leafhdr;953 954 trace_xfs_dir2_leaf_to_block(args);955 956 dp = args->dp;957 tp = args->trans;958 mp = dp->i_mount;959 leaf = lbp->b_addr;960 xfs_dir2_leaf_hdr_from_disk(mp, &leafhdr, leaf);961 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);962 963 ASSERT(leafhdr.magic == XFS_DIR2_LEAF1_MAGIC ||964 leafhdr.magic == XFS_DIR3_LEAF1_MAGIC);965 /*966 * If there are data blocks other than the first one, take this967 * opportunity to remove trailing empty data blocks that may have968 * been left behind during no-space-reservation operations.969 * These will show up in the leaf bests table.970 */971 while (dp->i_disk_size > args->geo->blksize) {972 int hdrsz;973 974 hdrsz = args->geo->data_entry_offset;975 bestsp = xfs_dir2_leaf_bests_p(ltp);976 if (be16_to_cpu(bestsp[be32_to_cpu(ltp->bestcount) - 1]) ==977 args->geo->blksize - hdrsz) {978 if ((error =979 xfs_dir2_leaf_trim_data(args, lbp,980 (xfs_dir2_db_t)(be32_to_cpu(ltp->bestcount) - 1))))981 return error;982 } else983 return 0;984 }985 /*986 * Read the data block if we don't already have it, give up if it fails.987 */988 if (!dbp) {989 error = xfs_dir3_data_read(tp, dp, args->owner,990 args->geo->datablk, 0, &dbp);991 if (error)992 return error;993 }994 hdr = dbp->b_addr;995 ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||996 hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));997 998 /*999 * Size of the "leaf" area in the block.1000 */1001 size = (uint)sizeof(xfs_dir2_block_tail_t) +1002 (uint)sizeof(*lep) * (leafhdr.count - leafhdr.stale);1003 /*1004 * Look at the last data entry.1005 */1006 tagp = (__be16 *)((char *)hdr + args->geo->blksize) - 1;1007 dup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));1008 /*1009 * If it's not free or is too short we can't do it.1010 */1011 if (be16_to_cpu(dup->freetag) != XFS_DIR2_DATA_FREE_TAG ||1012 be16_to_cpu(dup->length) < size)1013 return 0;1014 1015 /*1016 * Start converting it to block form.1017 */1018 xfs_dir3_block_init(args, dbp);1019 1020 needlog = 1;1021 needscan = 0;1022 /*1023 * Use up the space at the end of the block (blp/btp).1024 */1025 error = xfs_dir2_data_use_free(args, dbp, dup,1026 args->geo->blksize - size, size, &needlog, &needscan);1027 if (error)1028 return error;1029 /*1030 * Initialize the block tail.1031 */1032 btp = xfs_dir2_block_tail_p(args->geo, hdr);1033 btp->count = cpu_to_be32(leafhdr.count - leafhdr.stale);1034 btp->stale = 0;1035 xfs_dir2_block_log_tail(tp, dbp);1036 /*1037 * Initialize the block leaf area. We compact out stale entries.1038 */1039 lep = xfs_dir2_block_leaf_p(btp);1040 for (from = to = 0; from < leafhdr.count; from++) {1041 if (leafhdr.ents[from].address ==1042 cpu_to_be32(XFS_DIR2_NULL_DATAPTR))1043 continue;1044 lep[to++] = leafhdr.ents[from];1045 }1046 ASSERT(to == be32_to_cpu(btp->count));1047 xfs_dir2_block_log_leaf(tp, dbp, 0, be32_to_cpu(btp->count) - 1);1048 /*1049 * Scan the bestfree if we need it and log the data block header.1050 */1051 if (needscan)1052 xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);1053 if (needlog)1054 xfs_dir2_data_log_header(args, dbp);1055 /*1056 * Pitch the old leaf block.1057 */1058 error = xfs_da_shrink_inode(args, args->geo->leafblk, lbp);1059 if (error)1060 return error;1061 1062 /*1063 * Now see if the resulting block can be shrunken to shortform.1064 */1065 size = xfs_dir2_block_sfsize(dp, hdr, &sfh);1066 if (size > xfs_inode_data_fork_size(dp))1067 return 0;1068 1069 return xfs_dir2_block_to_sf(args, dbp, size, &sfh);1070}1071 1072/*1073 * Convert the shortform directory to block form.1074 */1075int /* error */1076xfs_dir2_sf_to_block(1077 struct xfs_da_args *args)1078{1079 struct xfs_trans *tp = args->trans;1080 struct xfs_inode *dp = args->dp;1081 struct xfs_mount *mp = dp->i_mount;1082 struct xfs_ifork *ifp = xfs_ifork_ptr(dp, XFS_DATA_FORK);1083 struct xfs_da_geometry *geo = args->geo;1084 xfs_dir2_db_t blkno; /* dir-relative block # (0) */1085 xfs_dir2_data_hdr_t *hdr; /* block header */1086 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */1087 struct xfs_buf *bp; /* block buffer */1088 xfs_dir2_block_tail_t *btp; /* block tail pointer */1089 xfs_dir2_data_entry_t *dep; /* data entry pointer */1090 int dummy; /* trash */1091 xfs_dir2_data_unused_t *dup; /* unused entry pointer */1092 int endoffset; /* end of data objects */1093 int error; /* error return value */1094 int i; /* index */1095 int needlog; /* need to log block header */1096 int needscan; /* need to scan block freespc */1097 int newoffset; /* offset from current entry */1098 unsigned int offset = geo->data_entry_offset;1099 xfs_dir2_sf_entry_t *sfep; /* sf entry pointer */1100 struct xfs_dir2_sf_hdr *oldsfp = ifp->if_data;1101 xfs_dir2_sf_hdr_t *sfp; /* shortform header */1102 __be16 *tagp; /* end of data entry */1103 struct xfs_name name;1104 1105 trace_xfs_dir2_sf_to_block(args);1106 1107 ASSERT(ifp->if_format == XFS_DINODE_FMT_LOCAL);1108 ASSERT(dp->i_disk_size >= offsetof(struct xfs_dir2_sf_hdr, parent));1109 1110 ASSERT(ifp->if_bytes == dp->i_disk_size);1111 ASSERT(oldsfp != NULL);1112 ASSERT(dp->i_disk_size >= xfs_dir2_sf_hdr_size(oldsfp->i8count));1113 ASSERT(dp->i_df.if_nextents == 0);1114 1115 /*1116 * Copy the directory into a temporary buffer.1117 * Then pitch the incore inode data so we can make extents.1118 */1119 sfp = kmalloc(ifp->if_bytes, GFP_KERNEL | __GFP_NOFAIL);1120 memcpy(sfp, oldsfp, ifp->if_bytes);1121 1122 xfs_idata_realloc(dp, -ifp->if_bytes, XFS_DATA_FORK);1123 xfs_bmap_local_to_extents_empty(tp, dp, XFS_DATA_FORK);1124 dp->i_disk_size = 0;1125 1126 /*1127 * Add block 0 to the inode.1128 */1129 error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE, &blkno);1130 if (error)1131 goto out_free;1132 /*1133 * Initialize the data block, then convert it to block format.1134 */1135 error = xfs_dir3_data_init(args, blkno, &bp);1136 if (error)1137 goto out_free;1138 xfs_dir3_block_init(args, bp);1139 hdr = bp->b_addr;1140 1141 /*1142 * Compute size of block "tail" area.1143 */1144 i = (uint)sizeof(*btp) +1145 (sfp->count + 2) * (uint)sizeof(xfs_dir2_leaf_entry_t);1146 /*1147 * The whole thing is initialized to free by the init routine.1148 * Say we're using the leaf and tail area.1149 */1150 dup = bp->b_addr + offset;1151 needlog = needscan = 0;1152 error = xfs_dir2_data_use_free(args, bp, dup, args->geo->blksize - i,1153 i, &needlog, &needscan);1154 if (error)1155 goto out_free;1156 ASSERT(needscan == 0);1157 /*1158 * Fill in the tail.1159 */1160 btp = xfs_dir2_block_tail_p(args->geo, hdr);1161 btp->count = cpu_to_be32(sfp->count + 2); /* ., .. */1162 btp->stale = 0;1163 blp = xfs_dir2_block_leaf_p(btp);1164 endoffset = (uint)((char *)blp - (char *)hdr);1165 /*1166 * Remove the freespace, we'll manage it.1167 */1168 error = xfs_dir2_data_use_free(args, bp, dup,1169 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),1170 be16_to_cpu(dup->length), &needlog, &needscan);1171 if (error)1172 goto out_free;1173 1174 /*1175 * Create entry for .1176 */1177 dep = bp->b_addr + offset;1178 dep->inumber = cpu_to_be64(args->owner);1179 dep->namelen = 1;1180 dep->name[0] = '.';1181 xfs_dir2_data_put_ftype(mp, dep, XFS_DIR3_FT_DIR);1182 tagp = xfs_dir2_data_entry_tag_p(mp, dep);1183 *tagp = cpu_to_be16(offset);1184 xfs_dir2_data_log_entry(args, bp, dep);1185 blp[0].hashval = cpu_to_be32(xfs_dir_hash_dot);1186 blp[0].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(offset));1187 offset += xfs_dir2_data_entsize(mp, dep->namelen);1188 1189 /*1190 * Create entry for ..1191 */1192 dep = bp->b_addr + offset;1193 dep->inumber = cpu_to_be64(xfs_dir2_sf_get_parent_ino(sfp));1194 dep->namelen = 2;1195 dep->name[0] = dep->name[1] = '.';1196 xfs_dir2_data_put_ftype(mp, dep, XFS_DIR3_FT_DIR);1197 tagp = xfs_dir2_data_entry_tag_p(mp, dep);1198 *tagp = cpu_to_be16(offset);1199 xfs_dir2_data_log_entry(args, bp, dep);1200 blp[1].hashval = cpu_to_be32(xfs_dir_hash_dotdot);1201 blp[1].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(offset));1202 offset += xfs_dir2_data_entsize(mp, dep->namelen);1203 1204 /*1205 * Loop over existing entries, stuff them in.1206 */1207 i = 0;1208 if (!sfp->count)1209 sfep = NULL;1210 else1211 sfep = xfs_dir2_sf_firstentry(sfp);1212 1213 /*1214 * Need to preserve the existing offset values in the sf directory.1215 * Insert holes (unused entries) where necessary.1216 */1217 while (offset < endoffset) {1218 /*1219 * sfep is null when we reach the end of the list.1220 */1221 if (sfep == NULL)1222 newoffset = endoffset;1223 else1224 newoffset = xfs_dir2_sf_get_offset(sfep);1225 /*1226 * There should be a hole here, make one.1227 */1228 if (offset < newoffset) {1229 dup = bp->b_addr + offset;1230 dup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);1231 dup->length = cpu_to_be16(newoffset - offset);1232 *xfs_dir2_data_unused_tag_p(dup) = cpu_to_be16(offset);1233 xfs_dir2_data_log_unused(args, bp, dup);1234 xfs_dir2_data_freeinsert(hdr,1235 xfs_dir2_data_bestfree_p(mp, hdr),1236 dup, &dummy);1237 offset += be16_to_cpu(dup->length);1238 continue;1239 }1240 /*1241 * Copy a real entry.1242 */1243 dep = bp->b_addr + newoffset;1244 dep->inumber = cpu_to_be64(xfs_dir2_sf_get_ino(mp, sfp, sfep));1245 dep->namelen = sfep->namelen;1246 xfs_dir2_data_put_ftype(mp, dep,1247 xfs_dir2_sf_get_ftype(mp, sfep));1248 memcpy(dep->name, sfep->name, dep->namelen);1249 tagp = xfs_dir2_data_entry_tag_p(mp, dep);1250 *tagp = cpu_to_be16(newoffset);1251 xfs_dir2_data_log_entry(args, bp, dep);1252 name.name = sfep->name;1253 name.len = sfep->namelen;1254 blp[2 + i].hashval = cpu_to_be32(xfs_dir2_hashname(mp, &name));1255 blp[2 + i].address =1256 cpu_to_be32(xfs_dir2_byte_to_dataptr(newoffset));1257 offset = (int)((char *)(tagp + 1) - (char *)hdr);1258 if (++i == sfp->count)1259 sfep = NULL;1260 else1261 sfep = xfs_dir2_sf_nextentry(mp, sfp, sfep);1262 }1263 /* Done with the temporary buffer */1264 kfree(sfp);1265 /*1266 * Sort the leaf entries by hash value.1267 */1268 xfs_sort(blp, be32_to_cpu(btp->count), sizeof(*blp), xfs_dir2_block_sort);1269 /*1270 * Log the leaf entry area and tail.1271 * Already logged the header in data_init, ignore needlog.1272 */1273 ASSERT(needscan == 0);1274 xfs_dir2_block_log_leaf(tp, bp, 0, be32_to_cpu(btp->count) - 1);1275 xfs_dir2_block_log_tail(tp, bp);1276 xfs_dir3_data_check(dp, bp);1277 return 0;1278out_free:1279 kfree(sfp);1280 return error;1281}1282