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