2 * Copyright (c) 2000-2003 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
34 #include "xfs_types.h"
38 #include "xfs_trans.h"
43 #include "xfs_dmapi.h"
44 #include "xfs_mount.h"
45 #include "xfs_da_btree.h"
46 #include "xfs_bmap_btree.h"
47 #include "xfs_attr_sf.h"
48 #include "xfs_dir_sf.h"
49 #include "xfs_dir2_sf.h"
50 #include "xfs_dinode.h"
51 #include "xfs_inode.h"
53 #include "xfs_dir2_data.h"
54 #include "xfs_dir2_leaf.h"
55 #include "xfs_dir2_block.h"
56 #include "xfs_dir2_node.h"
57 #include "xfs_dir2_trace.h"
58 #include "xfs_error.h"
61 * Local function declarations.
64 static void xfs_dir2_leaf_check(xfs_inode_t *dp, xfs_dabuf_t *bp);
66 #define xfs_dir2_leaf_check(dp, bp)
68 static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, xfs_dabuf_t **lbpp,
69 int *indexp, xfs_dabuf_t **dbpp);
70 static void xfs_dir2_leaf_log_bests(struct xfs_trans *tp, struct xfs_dabuf *bp,
72 static void xfs_dir2_leaf_log_tail(struct xfs_trans *tp, struct xfs_dabuf *bp);
76 * Convert a block form directory to a leaf form directory.
79 xfs_dir2_block_to_leaf(
80 xfs_da_args_t *args, /* operation arguments */
81 xfs_dabuf_t *dbp) /* input block's buffer */
83 xfs_dir2_data_off_t *bestsp; /* leaf's bestsp entries */
84 xfs_dablk_t blkno; /* leaf block's bno */
85 xfs_dir2_block_t *block; /* block structure */
86 xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */
87 xfs_dir2_block_tail_t *btp; /* block's tail */
88 xfs_inode_t *dp; /* incore directory inode */
89 int error; /* error return code */
90 xfs_dabuf_t *lbp; /* leaf block's buffer */
91 xfs_dir2_db_t ldb; /* leaf block's bno */
92 xfs_dir2_leaf_t *leaf; /* leaf structure */
93 xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */
94 xfs_mount_t *mp; /* filesystem mount point */
95 int needlog; /* need to log block header */
96 int needscan; /* need to rescan bestfree */
97 xfs_trans_t *tp; /* transaction pointer */
99 xfs_dir2_trace_args_b("block_to_leaf", args, dbp);
104 * Add the leaf block to the inode.
105 * This interface will only put blocks in the leaf/node range.
106 * Since that's empty now, we'll get the root (block 0 in range).
108 if ((error = xfs_da_grow_inode(args, &blkno))) {
111 ldb = XFS_DIR2_DA_TO_DB(mp, blkno);
112 ASSERT(ldb == XFS_DIR2_LEAF_FIRSTDB(mp));
114 * Initialize the leaf block, get a buffer for it.
116 if ((error = xfs_dir2_leaf_init(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC))) {
122 xfs_dir2_data_check(dp, dbp);
123 btp = XFS_DIR2_BLOCK_TAIL_P(mp, block);
124 blp = XFS_DIR2_BLOCK_LEAF_P(btp);
126 * Set the counts in the leaf header.
128 INT_COPY(leaf->hdr.count, btp->count, ARCH_CONVERT); /* INT_: type change */
129 INT_COPY(leaf->hdr.stale, btp->stale, ARCH_CONVERT); /* INT_: type change */
131 * Could compact these but I think we always do the conversion
132 * after squeezing out stale entries.
134 memcpy(leaf->ents, blp, INT_GET(btp->count, ARCH_CONVERT) * sizeof(xfs_dir2_leaf_entry_t));
135 xfs_dir2_leaf_log_ents(tp, lbp, 0, INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1);
139 * Make the space formerly occupied by the leaf entries and block
142 xfs_dir2_data_make_free(tp, dbp,
143 (xfs_dir2_data_aoff_t)((char *)blp - (char *)block),
144 (xfs_dir2_data_aoff_t)((char *)block + mp->m_dirblksize -
146 &needlog, &needscan);
148 * Fix up the block header, make it a data block.
150 INT_SET(block->hdr.magic, ARCH_CONVERT, XFS_DIR2_DATA_MAGIC);
152 xfs_dir2_data_freescan(mp, (xfs_dir2_data_t *)block, &needlog,
155 * Set up leaf tail and bests table.
157 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
158 INT_SET(ltp->bestcount, ARCH_CONVERT, 1);
159 bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
160 INT_COPY(bestsp[0], block->hdr.bestfree[0].length, ARCH_CONVERT);
162 * Log the data header and leaf bests table.
165 xfs_dir2_data_log_header(tp, dbp);
166 xfs_dir2_leaf_check(dp, lbp);
167 xfs_dir2_data_check(dp, dbp);
168 xfs_dir2_leaf_log_bests(tp, lbp, 0, 0);
169 xfs_da_buf_done(lbp);
174 * Add an entry to a leaf form directory.
177 xfs_dir2_leaf_addname(
178 xfs_da_args_t *args) /* operation arguments */
180 xfs_dir2_data_off_t *bestsp; /* freespace table in leaf */
181 int compact; /* need to compact leaves */
182 xfs_dir2_data_t *data; /* data block structure */
183 xfs_dabuf_t *dbp; /* data block buffer */
184 xfs_dir2_data_entry_t *dep; /* data block entry */
185 xfs_inode_t *dp; /* incore directory inode */
186 xfs_dir2_data_unused_t *dup; /* data unused entry */
187 int error; /* error return value */
188 int grown; /* allocated new data block */
189 int highstale; /* index of next stale leaf */
190 int i; /* temporary, index */
191 int index; /* leaf table position */
192 xfs_dabuf_t *lbp; /* leaf's buffer */
193 xfs_dir2_leaf_t *leaf; /* leaf structure */
194 int length; /* length of new entry */
195 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
196 int lfloglow; /* low leaf logging index */
197 int lfloghigh; /* high leaf logging index */
198 int lowstale; /* index of prev stale leaf */
199 xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
200 xfs_mount_t *mp; /* filesystem mount point */
201 int needbytes; /* leaf block bytes needed */
202 int needlog; /* need to log data header */
203 int needscan; /* need to rescan data free */
204 xfs_dir2_data_off_t *tagp; /* end of data entry */
205 xfs_trans_t *tp; /* transaction pointer */
206 xfs_dir2_db_t use_block; /* data block number */
208 xfs_dir2_trace_args("leaf_addname", args);
213 * Read the leaf block.
215 error = xfs_da_read_buf(tp, dp, mp->m_dirleafblk, -1, &lbp,
222 * Look up the entry by hash value and name.
223 * We know it's not there, our caller has already done a lookup.
224 * So the index is of the entry to insert in front of.
225 * But if there are dup hash values the index is of the first of those.
227 index = xfs_dir2_leaf_search_hash(args, lbp);
229 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
230 bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
231 length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
233 * See if there are any entries with the same hash value
234 * and space in their block for the new entry.
235 * This is good because it puts multiple same-hash value entries
236 * in a data block, improving the lookup of those entries.
238 for (use_block = -1, lep = &leaf->ents[index];
239 index < INT_GET(leaf->hdr.count, ARCH_CONVERT) && INT_GET(lep->hashval, ARCH_CONVERT) == args->hashval;
241 if (INT_GET(lep->address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
243 i = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
244 ASSERT(i < INT_GET(ltp->bestcount, ARCH_CONVERT));
245 ASSERT(INT_GET(bestsp[i], ARCH_CONVERT) != NULLDATAOFF);
246 if (INT_GET(bestsp[i], ARCH_CONVERT) >= length) {
252 * Didn't find a block yet, linear search all the data blocks.
254 if (use_block == -1) {
255 for (i = 0; i < INT_GET(ltp->bestcount, ARCH_CONVERT); i++) {
257 * Remember a block we see that's missing.
259 if (INT_GET(bestsp[i], ARCH_CONVERT) == NULLDATAOFF && use_block == -1)
261 else if (INT_GET(bestsp[i], ARCH_CONVERT) >= length) {
268 * How many bytes do we need in the leaf block?
271 (leaf->hdr.stale ? 0 : (uint)sizeof(leaf->ents[0])) +
272 (use_block != -1 ? 0 : (uint)sizeof(leaf->bests[0]));
274 * Now kill use_block if it refers to a missing block, so we
275 * can use it as an indication of allocation needed.
277 if (use_block != -1 && INT_GET(bestsp[use_block], ARCH_CONVERT) == NULLDATAOFF)
280 * If we don't have enough free bytes but we can make enough
281 * by compacting out stale entries, we'll do that.
283 if ((char *)bestsp - (char *)&leaf->ents[INT_GET(leaf->hdr.count, ARCH_CONVERT)] < needbytes &&
284 INT_GET(leaf->hdr.stale, ARCH_CONVERT) > 1) {
288 * Otherwise if we don't have enough free bytes we need to
289 * convert to node form.
291 else if ((char *)bestsp - (char *)&leaf->ents[INT_GET(leaf->hdr.count, ARCH_CONVERT)] <
294 * Just checking or no space reservation, give up.
296 if (args->justcheck || args->total == 0) {
297 xfs_da_brelse(tp, lbp);
298 return XFS_ERROR(ENOSPC);
301 * Convert to node form.
303 error = xfs_dir2_leaf_to_node(args, lbp);
304 xfs_da_buf_done(lbp);
308 * Then add the new entry.
310 return xfs_dir2_node_addname(args);
313 * Otherwise it will fit without compaction.
318 * If just checking, then it will fit unless we needed to allocate
321 if (args->justcheck) {
322 xfs_da_brelse(tp, lbp);
323 return use_block == -1 ? XFS_ERROR(ENOSPC) : 0;
326 * If no allocations are allowed, return now before we've
329 if (args->total == 0 && use_block == -1) {
330 xfs_da_brelse(tp, lbp);
331 return XFS_ERROR(ENOSPC);
334 * Need to compact the leaf entries, removing stale ones.
335 * Leave one stale entry behind - the one closest to our
336 * insertion index - and we'll shift that one to our insertion
340 xfs_dir2_leaf_compact_x1(lbp, &index, &lowstale, &highstale,
341 &lfloglow, &lfloghigh);
344 * There are stale entries, so we'll need log-low and log-high
345 * impossibly bad values later.
347 else if (INT_GET(leaf->hdr.stale, ARCH_CONVERT)) {
348 lfloglow = INT_GET(leaf->hdr.count, ARCH_CONVERT);
352 * If there was no data block space found, we need to allocate
355 if (use_block == -1) {
357 * Add the new data block.
359 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
361 xfs_da_brelse(tp, lbp);
365 * Initialize the block.
367 if ((error = xfs_dir2_data_init(args, use_block, &dbp))) {
368 xfs_da_brelse(tp, lbp);
372 * If we're adding a new data block on the end we need to
373 * extend the bests table. Copy it up one entry.
375 if (use_block >= INT_GET(ltp->bestcount, ARCH_CONVERT)) {
377 memmove(&bestsp[0], &bestsp[1],
378 INT_GET(ltp->bestcount, ARCH_CONVERT) * sizeof(bestsp[0]));
379 INT_MOD(ltp->bestcount, ARCH_CONVERT, +1);
380 xfs_dir2_leaf_log_tail(tp, lbp);
381 xfs_dir2_leaf_log_bests(tp, lbp, 0, INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
384 * If we're filling in a previously empty block just log it.
387 xfs_dir2_leaf_log_bests(tp, lbp, use_block, use_block);
389 INT_COPY(bestsp[use_block], data->hdr.bestfree[0].length, ARCH_CONVERT);
393 * Already had space in some data block.
394 * Just read that one in.
398 xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, use_block),
399 -1, &dbp, XFS_DATA_FORK))) {
400 xfs_da_brelse(tp, lbp);
406 xfs_dir2_data_check(dp, dbp);
408 * Point to the biggest freespace in our data block.
410 dup = (xfs_dir2_data_unused_t *)
411 ((char *)data + INT_GET(data->hdr.bestfree[0].offset, ARCH_CONVERT));
412 ASSERT(INT_GET(dup->length, ARCH_CONVERT) >= length);
413 needscan = needlog = 0;
415 * Mark the initial part of our freespace in use for the new entry.
417 xfs_dir2_data_use_free(tp, dbp, dup,
418 (xfs_dir2_data_aoff_t)((char *)dup - (char *)data), length,
419 &needlog, &needscan);
421 * Initialize our new entry (at last).
423 dep = (xfs_dir2_data_entry_t *)dup;
424 INT_SET(dep->inumber, ARCH_CONVERT, args->inumber);
425 dep->namelen = args->namelen;
426 memcpy(dep->name, args->name, dep->namelen);
427 tagp = XFS_DIR2_DATA_ENTRY_TAG_P(dep);
428 INT_SET(*tagp, ARCH_CONVERT, (xfs_dir2_data_off_t)((char *)dep - (char *)data));
430 * Need to scan fix up the bestfree table.
433 xfs_dir2_data_freescan(mp, data, &needlog, NULL);
435 * Need to log the data block's header.
438 xfs_dir2_data_log_header(tp, dbp);
439 xfs_dir2_data_log_entry(tp, dbp, dep);
441 * If the bests table needs to be changed, do it.
442 * Log the change unless we've already done that.
444 if (INT_GET(bestsp[use_block], ARCH_CONVERT) != INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT)) {
445 INT_COPY(bestsp[use_block], data->hdr.bestfree[0].length, ARCH_CONVERT);
447 xfs_dir2_leaf_log_bests(tp, lbp, use_block, use_block);
450 * Now we need to make room to insert the leaf entry.
451 * If there are no stale entries, we just insert a hole at index.
453 if (!leaf->hdr.stale) {
455 * lep is still good as the index leaf entry.
457 if (index < INT_GET(leaf->hdr.count, ARCH_CONVERT))
458 memmove(lep + 1, lep,
459 (INT_GET(leaf->hdr.count, ARCH_CONVERT) - index) * sizeof(*lep));
461 * Record low and high logging indices for the leaf.
464 lfloghigh = INT_GET(leaf->hdr.count, ARCH_CONVERT);
465 INT_MOD(leaf->hdr.count, ARCH_CONVERT, +1);
468 * There are stale entries.
469 * We will use one of them for the new entry.
470 * It's probably not at the right location, so we'll have to
471 * shift some up or down first.
475 * If we didn't compact before, we need to find the nearest
476 * stale entries before and after our insertion point.
480 * Find the first stale entry before the insertion
483 for (lowstale = index - 1;
485 INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) !=
486 XFS_DIR2_NULL_DATAPTR;
490 * Find the next stale entry at or after the insertion
491 * point, if any. Stop if we go so far that the
492 * lowstale entry would be better.
494 for (highstale = index;
495 highstale < INT_GET(leaf->hdr.count, ARCH_CONVERT) &&
496 INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) !=
497 XFS_DIR2_NULL_DATAPTR &&
499 index - lowstale - 1 >= highstale - index);
504 * If the low one is better, use it.
507 (highstale == INT_GET(leaf->hdr.count, ARCH_CONVERT) ||
508 index - lowstale - 1 < highstale - index)) {
509 ASSERT(index - lowstale - 1 >= 0);
510 ASSERT(INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) ==
511 XFS_DIR2_NULL_DATAPTR);
513 * Copy entries up to cover the stale entry
514 * and make room for the new entry.
516 if (index - lowstale - 1 > 0)
517 memmove(&leaf->ents[lowstale],
518 &leaf->ents[lowstale + 1],
519 (index - lowstale - 1) * sizeof(*lep));
520 lep = &leaf->ents[index - 1];
521 lfloglow = MIN(lowstale, lfloglow);
522 lfloghigh = MAX(index - 1, lfloghigh);
525 * The high one is better, so use that one.
528 ASSERT(highstale - index >= 0);
529 ASSERT(INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) ==
530 XFS_DIR2_NULL_DATAPTR);
532 * Copy entries down to copver the stale entry
533 * and make room for the new entry.
535 if (highstale - index > 0)
536 memmove(&leaf->ents[index + 1],
538 (highstale - index) * sizeof(*lep));
539 lep = &leaf->ents[index];
540 lfloglow = MIN(index, lfloglow);
541 lfloghigh = MAX(highstale, lfloghigh);
543 INT_MOD(leaf->hdr.stale, ARCH_CONVERT, -1);
546 * Fill in the new leaf entry.
548 INT_SET(lep->hashval, ARCH_CONVERT, args->hashval);
549 INT_SET(lep->address, ARCH_CONVERT, XFS_DIR2_DB_OFF_TO_DATAPTR(mp, use_block, INT_GET(*tagp, ARCH_CONVERT)));
551 * Log the leaf fields and give up the buffers.
553 xfs_dir2_leaf_log_header(tp, lbp);
554 xfs_dir2_leaf_log_ents(tp, lbp, lfloglow, lfloghigh);
555 xfs_dir2_leaf_check(dp, lbp);
556 xfs_da_buf_done(lbp);
557 xfs_dir2_data_check(dp, dbp);
558 xfs_da_buf_done(dbp);
564 * Check the internal consistency of a leaf1 block.
565 * Pop an assert if something is wrong.
569 xfs_inode_t *dp, /* incore directory inode */
570 xfs_dabuf_t *bp) /* leaf's buffer */
572 int i; /* leaf index */
573 xfs_dir2_leaf_t *leaf; /* leaf structure */
574 xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
575 xfs_mount_t *mp; /* filesystem mount point */
576 int stale; /* count of stale leaves */
580 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC);
582 * This value is not restrictive enough.
583 * Should factor in the size of the bests table as well.
584 * We can deduce a value for that from di_size.
586 ASSERT(INT_GET(leaf->hdr.count, ARCH_CONVERT) <= XFS_DIR2_MAX_LEAF_ENTS(mp));
587 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
589 * Leaves and bests don't overlap.
591 ASSERT((char *)&leaf->ents[INT_GET(leaf->hdr.count, ARCH_CONVERT)] <=
592 (char *)XFS_DIR2_LEAF_BESTS_P(ltp));
594 * Check hash value order, count stale entries.
596 for (i = stale = 0; i < INT_GET(leaf->hdr.count, ARCH_CONVERT); i++) {
597 if (i + 1 < INT_GET(leaf->hdr.count, ARCH_CONVERT))
598 ASSERT(INT_GET(leaf->ents[i].hashval, ARCH_CONVERT) <=
599 INT_GET(leaf->ents[i + 1].hashval, ARCH_CONVERT));
600 if (INT_GET(leaf->ents[i].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
603 ASSERT(INT_GET(leaf->hdr.stale, ARCH_CONVERT) == stale);
608 * Compact out any stale entries in the leaf.
609 * Log the header and changed leaf entries, if any.
612 xfs_dir2_leaf_compact(
613 xfs_da_args_t *args, /* operation arguments */
614 xfs_dabuf_t *bp) /* leaf buffer */
616 int from; /* source leaf index */
617 xfs_dir2_leaf_t *leaf; /* leaf structure */
618 int loglow; /* first leaf entry to log */
619 int to; /* target leaf index */
622 if (!leaf->hdr.stale) {
626 * Compress out the stale entries in place.
628 for (from = to = 0, loglow = -1; from < INT_GET(leaf->hdr.count, ARCH_CONVERT); from++) {
629 if (INT_GET(leaf->ents[from].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
632 * Only actually copy the entries that are different.
637 leaf->ents[to] = leaf->ents[from];
642 * Update and log the header, log the leaf entries.
644 ASSERT(INT_GET(leaf->hdr.stale, ARCH_CONVERT) == from - to);
645 INT_MOD(leaf->hdr.count, ARCH_CONVERT, -(INT_GET(leaf->hdr.stale, ARCH_CONVERT)));
647 xfs_dir2_leaf_log_header(args->trans, bp);
649 xfs_dir2_leaf_log_ents(args->trans, bp, loglow, to - 1);
653 * Compact the leaf entries, removing stale ones.
654 * Leave one stale entry behind - the one closest to our
655 * insertion index - and the caller will shift that one to our insertion
657 * Return new insertion index, where the remaining stale entry is,
658 * and leaf logging indices.
661 xfs_dir2_leaf_compact_x1(
662 xfs_dabuf_t *bp, /* leaf buffer */
663 int *indexp, /* insertion index */
664 int *lowstalep, /* out: stale entry before us */
665 int *highstalep, /* out: stale entry after us */
666 int *lowlogp, /* out: low log index */
667 int *highlogp) /* out: high log index */
669 int from; /* source copy index */
670 int highstale; /* stale entry at/after index */
671 int index; /* insertion index */
672 int keepstale; /* source index of kept stale */
673 xfs_dir2_leaf_t *leaf; /* leaf structure */
674 int lowstale; /* stale entry before index */
675 int newindex=0; /* new insertion index */
676 int to; /* destination copy index */
679 ASSERT(INT_GET(leaf->hdr.stale, ARCH_CONVERT) > 1);
682 * Find the first stale entry before our index, if any.
684 for (lowstale = index - 1;
686 INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) != XFS_DIR2_NULL_DATAPTR;
690 * Find the first stale entry at or after our index, if any.
691 * Stop if the answer would be worse than lowstale.
693 for (highstale = index;
694 highstale < INT_GET(leaf->hdr.count, ARCH_CONVERT) &&
695 INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) != XFS_DIR2_NULL_DATAPTR &&
696 (lowstale < 0 || index - lowstale > highstale - index);
700 * Pick the better of lowstale and highstale.
703 (highstale == INT_GET(leaf->hdr.count, ARCH_CONVERT) ||
704 index - lowstale <= highstale - index))
705 keepstale = lowstale;
707 keepstale = highstale;
709 * Copy the entries in place, removing all the stale entries
712 for (from = to = 0; from < INT_GET(leaf->hdr.count, ARCH_CONVERT); from++) {
714 * Notice the new value of index.
718 if (from != keepstale &&
719 INT_GET(leaf->ents[from].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR) {
725 * Record the new keepstale value for the insertion.
727 if (from == keepstale)
728 lowstale = highstale = to;
730 * Copy only the entries that have moved.
733 leaf->ents[to] = leaf->ents[from];
738 * If the insertion point was past the last entry,
739 * set the new insertion point accordingly.
745 * Adjust the leaf header values.
747 INT_MOD(leaf->hdr.count, ARCH_CONVERT, -(from - to));
748 INT_SET(leaf->hdr.stale, ARCH_CONVERT, 1);
750 * Remember the low/high stale value only in the "right"
753 if (lowstale >= newindex)
756 highstale = INT_GET(leaf->hdr.count, ARCH_CONVERT);
757 *highlogp = INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1;
758 *lowstalep = lowstale;
759 *highstalep = highstale;
763 * Getdents (readdir) for leaf and node directories.
764 * This reads the data blocks only, so is the same for both forms.
767 xfs_dir2_leaf_getdents(
768 xfs_trans_t *tp, /* transaction pointer */
769 xfs_inode_t *dp, /* incore directory inode */
770 uio_t *uio, /* I/O control & vectors */
771 int *eofp, /* out: reached end of dir */
772 xfs_dirent_t *dbp, /* caller's buffer */
773 xfs_dir2_put_t put) /* ABI formatting routine */
775 xfs_dabuf_t *bp; /* data block buffer */
776 int byteoff; /* offset in current block */
777 xfs_dir2_db_t curdb; /* db for current block */
778 xfs_dir2_off_t curoff; /* current overall offset */
779 xfs_dir2_data_t *data; /* data block structure */
780 xfs_dir2_data_entry_t *dep; /* data entry */
781 xfs_dir2_data_unused_t *dup; /* unused entry */
782 int eof; /* reached end of directory */
783 int error=0; /* error return value */
784 int i; /* temporary loop index */
785 int j; /* temporary loop index */
786 int length; /* temporary length value */
787 xfs_bmbt_irec_t *map; /* map vector for blocks */
788 xfs_extlen_t map_blocks; /* number of fsbs in map */
789 xfs_dablk_t map_off; /* last mapped file offset */
790 int map_size; /* total entries in *map */
791 int map_valid; /* valid entries in *map */
792 xfs_mount_t *mp; /* filesystem mount point */
793 xfs_dir2_off_t newoff; /* new curoff after new blk */
794 int nmap; /* mappings to ask xfs_bmapi */
795 xfs_dir2_put_args_t p; /* formatting arg bundle */
796 char *ptr=NULL; /* pointer to current data */
797 int ra_current; /* number of read-ahead blks */
798 int ra_index; /* *map index for read-ahead */
799 int ra_offset; /* map entry offset for ra */
800 int ra_want; /* readahead count wanted */
803 * If the offset is at or past the largest allowed value,
804 * give up right away, return eof.
806 if (uio->uio_offset >= XFS_DIR2_MAX_DATAPTR) {
812 * Setup formatting arguments.
818 * Set up to bmap a number of blocks based on the caller's
819 * buffer size, the directory block size, and the filesystem
823 howmany(uio->uio_resid + mp->m_dirblksize,
824 mp->m_sb.sb_blocksize);
825 map = kmem_alloc(map_size * sizeof(*map), KM_SLEEP);
826 map_valid = ra_index = ra_offset = ra_current = map_blocks = 0;
830 * Inside the loop we keep the main offset value as a byte offset
831 * in the directory file.
833 curoff = XFS_DIR2_DATAPTR_TO_BYTE(mp, uio->uio_offset);
835 * Force this conversion through db so we truncate the offset
836 * down to get the start of the data block.
838 map_off = XFS_DIR2_DB_TO_DA(mp, XFS_DIR2_BYTE_TO_DB(mp, curoff));
840 * Loop over directory entries until we reach the end offset.
841 * Get more blocks and readahead as necessary.
843 while (curoff < XFS_DIR2_LEAF_OFFSET) {
845 * If we have no buffer, or we're off the end of the
846 * current buffer, need to get another one.
848 if (!bp || ptr >= (char *)bp->data + mp->m_dirblksize) {
850 * If we have a buffer, we need to release it and
851 * take it out of the mapping.
854 xfs_da_brelse(tp, bp);
856 map_blocks -= mp->m_dirblkfsbs;
858 * Loop to get rid of the extents for the
861 for (i = mp->m_dirblkfsbs; i > 0; ) {
862 j = MIN((int)map->br_blockcount, i);
863 map->br_blockcount -= j;
864 map->br_startblock += j;
865 map->br_startoff += j;
867 * If mapping is done, pitch it from
870 if (!map->br_blockcount && --map_valid)
871 memmove(&map[0], &map[1],
878 * Recalculate the readahead blocks wanted.
880 ra_want = howmany(uio->uio_resid + mp->m_dirblksize,
881 mp->m_sb.sb_blocksize) - 1;
883 * If we don't have as many as we want, and we haven't
884 * run out of data blocks, get some more mappings.
886 if (1 + ra_want > map_blocks &&
888 XFS_DIR2_BYTE_TO_DA(mp, XFS_DIR2_LEAF_OFFSET)) {
890 * Get more bmaps, fill in after the ones
891 * we already have in the table.
893 nmap = map_size - map_valid;
894 error = xfs_bmapi(tp, dp,
896 XFS_DIR2_BYTE_TO_DA(mp,
897 XFS_DIR2_LEAF_OFFSET) - map_off,
898 XFS_BMAPI_METADATA, NULL, 0,
899 &map[map_valid], &nmap, NULL);
901 * Don't know if we should ignore this or
902 * try to return an error.
903 * The trouble with returning errors
904 * is that readdir will just stop without
905 * actually passing the error through.
910 * If we got all the mappings we asked for,
911 * set the final map offset based on the
912 * last bmap value received.
913 * Otherwise, we've reached the end.
915 if (nmap == map_size - map_valid)
917 map[map_valid + nmap - 1].br_startoff +
918 map[map_valid + nmap - 1].br_blockcount;
921 XFS_DIR2_BYTE_TO_DA(mp,
922 XFS_DIR2_LEAF_OFFSET);
924 * Look for holes in the mapping, and
925 * eliminate them. Count up the valid blocks.
927 for (i = map_valid; i < map_valid + nmap; ) {
928 if (map[i].br_startblock ==
931 length = map_valid + nmap - i;
939 map[i].br_blockcount;
946 * No valid mappings, so no more data blocks.
949 curoff = XFS_DIR2_DA_TO_BYTE(mp, map_off);
953 * Read the directory block starting at the first
956 curdb = XFS_DIR2_DA_TO_DB(mp, map->br_startoff);
957 error = xfs_da_read_buf(tp, dp, map->br_startoff,
958 map->br_blockcount >= mp->m_dirblkfsbs ?
959 XFS_FSB_TO_DADDR(mp, map->br_startblock) :
963 * Should just skip over the data block instead
969 * Adjust the current amount of read-ahead: we just
970 * read a block that was previously ra.
973 ra_current -= mp->m_dirblkfsbs;
975 * Do we need more readahead?
977 for (ra_index = ra_offset = i = 0;
978 ra_want > ra_current && i < map_blocks;
979 i += mp->m_dirblkfsbs) {
980 ASSERT(ra_index < map_valid);
982 * Read-ahead a contiguous directory block.
984 if (i > ra_current &&
985 map[ra_index].br_blockcount >=
987 xfs_baread(mp->m_ddev_targp,
989 map[ra_index].br_startblock +
991 (int)BTOBB(mp->m_dirblksize));
995 * Read-ahead a non-contiguous directory block.
996 * This doesn't use our mapping, but this
997 * is a very rare case.
999 else if (i > ra_current) {
1000 (void)xfs_da_reada_buf(tp, dp,
1001 map[ra_index].br_startoff +
1002 ra_offset, XFS_DATA_FORK);
1006 * Advance offset through the mapping table.
1008 for (j = 0; j < mp->m_dirblkfsbs; j++) {
1010 * The rest of this extent but not
1011 * more than a dir block.
1013 length = MIN(mp->m_dirblkfsbs,
1014 (int)(map[ra_index].br_blockcount -
1017 ra_offset += length;
1019 * Advance to the next mapping if
1020 * this one is used up.
1023 map[ra_index].br_blockcount) {
1030 * Having done a read, we need to set a new offset.
1032 newoff = XFS_DIR2_DB_OFF_TO_BYTE(mp, curdb, 0);
1034 * Start of the current block.
1036 if (curoff < newoff)
1039 * Make sure we're in the right block.
1041 else if (curoff > newoff)
1042 ASSERT(XFS_DIR2_BYTE_TO_DB(mp, curoff) ==
1045 xfs_dir2_data_check(dp, bp);
1047 * Find our position in the block.
1049 ptr = (char *)&data->u;
1050 byteoff = XFS_DIR2_BYTE_TO_OFF(mp, curoff);
1052 * Skip past the header.
1055 curoff += (uint)sizeof(data->hdr);
1057 * Skip past entries until we reach our offset.
1060 while ((char *)ptr - (char *)data < byteoff) {
1061 dup = (xfs_dir2_data_unused_t *)ptr;
1063 if (INT_GET(dup->freetag, ARCH_CONVERT)
1064 == XFS_DIR2_DATA_FREE_TAG) {
1066 length = INT_GET(dup->length,
1071 dep = (xfs_dir2_data_entry_t *)ptr;
1073 XFS_DIR2_DATA_ENTSIZE(dep->namelen);
1077 * Now set our real offset.
1080 XFS_DIR2_DB_OFF_TO_BYTE(mp,
1081 XFS_DIR2_BYTE_TO_DB(mp, curoff),
1082 (char *)ptr - (char *)data);
1083 if (ptr >= (char *)data + mp->m_dirblksize) {
1089 * We have a pointer to an entry.
1092 dup = (xfs_dir2_data_unused_t *)ptr;
1094 * No, it's unused, skip over it.
1096 if (INT_GET(dup->freetag, ARCH_CONVERT)
1097 == XFS_DIR2_DATA_FREE_TAG) {
1098 length = INT_GET(dup->length, ARCH_CONVERT);
1105 * Copy the entry into the putargs, and try formatting it.
1107 dep = (xfs_dir2_data_entry_t *)ptr;
1109 p.namelen = dep->namelen;
1111 length = XFS_DIR2_DATA_ENTSIZE(p.namelen);
1113 p.cook = XFS_DIR2_BYTE_TO_DATAPTR(mp, curoff + length);
1115 p.ino = INT_GET(dep->inumber, ARCH_CONVERT);
1117 p.ino += mp->m_inoadd;
1119 p.name = (char *)dep->name;
1124 * Won't fit. Return to caller.
1131 * Advance to next entry in the block.
1138 * All done. Set output offset value to current offset.
1141 if (curoff > XFS_DIR2_DATAPTR_TO_BYTE(mp, XFS_DIR2_MAX_DATAPTR))
1142 uio->uio_offset = XFS_DIR2_MAX_DATAPTR;
1144 uio->uio_offset = XFS_DIR2_BYTE_TO_DATAPTR(mp, curoff);
1145 kmem_free(map, map_size * sizeof(*map));
1147 xfs_da_brelse(tp, bp);
1152 * Initialize a new leaf block, leaf1 or leafn magic accepted.
1156 xfs_da_args_t *args, /* operation arguments */
1157 xfs_dir2_db_t bno, /* directory block number */
1158 xfs_dabuf_t **bpp, /* out: leaf buffer */
1159 int magic) /* magic number for block */
1161 xfs_dabuf_t *bp; /* leaf buffer */
1162 xfs_inode_t *dp; /* incore directory inode */
1163 int error; /* error return code */
1164 xfs_dir2_leaf_t *leaf; /* leaf structure */
1165 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1166 xfs_mount_t *mp; /* filesystem mount point */
1167 xfs_trans_t *tp; /* transaction pointer */
1173 ASSERT(bno >= XFS_DIR2_LEAF_FIRSTDB(mp) &&
1174 bno < XFS_DIR2_FREE_FIRSTDB(mp));
1176 * Get the buffer for the block.
1178 error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, bno), -1, &bp,
1186 * Initialize the header.
1188 INT_SET(leaf->hdr.info.magic, ARCH_CONVERT, magic);
1189 leaf->hdr.info.forw = 0;
1190 leaf->hdr.info.back = 0;
1191 leaf->hdr.count = 0;
1192 leaf->hdr.stale = 0;
1193 xfs_dir2_leaf_log_header(tp, bp);
1195 * If it's a leaf-format directory initialize the tail.
1196 * In this case our caller has the real bests table to copy into
1199 if (magic == XFS_DIR2_LEAF1_MAGIC) {
1200 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1202 xfs_dir2_leaf_log_tail(tp, bp);
1209 * Log the bests entries indicated from a leaf1 block.
1212 xfs_dir2_leaf_log_bests(
1213 xfs_trans_t *tp, /* transaction pointer */
1214 xfs_dabuf_t *bp, /* leaf buffer */
1215 int first, /* first entry to log */
1216 int last) /* last entry to log */
1218 xfs_dir2_data_off_t *firstb; /* pointer to first entry */
1219 xfs_dir2_data_off_t *lastb; /* pointer to last entry */
1220 xfs_dir2_leaf_t *leaf; /* leaf structure */
1221 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1224 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC);
1225 ltp = XFS_DIR2_LEAF_TAIL_P(tp->t_mountp, leaf);
1226 firstb = XFS_DIR2_LEAF_BESTS_P(ltp) + first;
1227 lastb = XFS_DIR2_LEAF_BESTS_P(ltp) + last;
1228 xfs_da_log_buf(tp, bp, (uint)((char *)firstb - (char *)leaf),
1229 (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
1233 * Log the leaf entries indicated from a leaf1 or leafn block.
1236 xfs_dir2_leaf_log_ents(
1237 xfs_trans_t *tp, /* transaction pointer */
1238 xfs_dabuf_t *bp, /* leaf buffer */
1239 int first, /* first entry to log */
1240 int last) /* last entry to log */
1242 xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */
1243 xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */
1244 xfs_dir2_leaf_t *leaf; /* leaf structure */
1247 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC ||
1248 INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1249 firstlep = &leaf->ents[first];
1250 lastlep = &leaf->ents[last];
1251 xfs_da_log_buf(tp, bp, (uint)((char *)firstlep - (char *)leaf),
1252 (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
1256 * Log the header of the leaf1 or leafn block.
1259 xfs_dir2_leaf_log_header(
1260 xfs_trans_t *tp, /* transaction pointer */
1261 xfs_dabuf_t *bp) /* leaf buffer */
1263 xfs_dir2_leaf_t *leaf; /* leaf structure */
1266 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC ||
1267 INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1268 xfs_da_log_buf(tp, bp, (uint)((char *)&leaf->hdr - (char *)leaf),
1269 (uint)(sizeof(leaf->hdr) - 1));
1273 * Log the tail of the leaf1 block.
1276 xfs_dir2_leaf_log_tail(
1277 xfs_trans_t *tp, /* transaction pointer */
1278 xfs_dabuf_t *bp) /* leaf buffer */
1280 xfs_dir2_leaf_t *leaf; /* leaf structure */
1281 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1282 xfs_mount_t *mp; /* filesystem mount point */
1286 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC);
1287 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1288 xfs_da_log_buf(tp, bp, (uint)((char *)ltp - (char *)leaf),
1289 (uint)(mp->m_dirblksize - 1));
1293 * Look up the entry referred to by args in the leaf format directory.
1294 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
1295 * is also used by the node-format code.
1298 xfs_dir2_leaf_lookup(
1299 xfs_da_args_t *args) /* operation arguments */
1301 xfs_dabuf_t *dbp; /* data block buffer */
1302 xfs_dir2_data_entry_t *dep; /* data block entry */
1303 xfs_inode_t *dp; /* incore directory inode */
1304 int error; /* error return code */
1305 int index; /* found entry index */
1306 xfs_dabuf_t *lbp; /* leaf buffer */
1307 xfs_dir2_leaf_t *leaf; /* leaf structure */
1308 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1309 xfs_trans_t *tp; /* transaction pointer */
1311 xfs_dir2_trace_args("leaf_lookup", args);
1313 * Look up name in the leaf block, returning both buffers and index.
1315 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1320 xfs_dir2_leaf_check(dp, lbp);
1323 * Get to the leaf entry and contained data entry address.
1325 lep = &leaf->ents[index];
1327 * Point to the data entry.
1329 dep = (xfs_dir2_data_entry_t *)
1330 ((char *)dbp->data +
1331 XFS_DIR2_DATAPTR_TO_OFF(dp->i_mount, INT_GET(lep->address, ARCH_CONVERT)));
1333 * Return the found inode number.
1335 args->inumber = INT_GET(dep->inumber, ARCH_CONVERT);
1336 xfs_da_brelse(tp, dbp);
1337 xfs_da_brelse(tp, lbp);
1338 return XFS_ERROR(EEXIST);
1342 * Look up name/hash in the leaf block.
1343 * Fill in indexp with the found index, and dbpp with the data buffer.
1344 * If not found dbpp will be NULL, and ENOENT comes back.
1345 * lbpp will always be filled in with the leaf buffer unless there's an error.
1347 static int /* error */
1348 xfs_dir2_leaf_lookup_int(
1349 xfs_da_args_t *args, /* operation arguments */
1350 xfs_dabuf_t **lbpp, /* out: leaf buffer */
1351 int *indexp, /* out: index in leaf block */
1352 xfs_dabuf_t **dbpp) /* out: data buffer */
1354 xfs_dir2_db_t curdb; /* current data block number */
1355 xfs_dabuf_t *dbp; /* data buffer */
1356 xfs_dir2_data_entry_t *dep; /* data entry */
1357 xfs_inode_t *dp; /* incore directory inode */
1358 int error; /* error return code */
1359 int index; /* index in leaf block */
1360 xfs_dabuf_t *lbp; /* leaf buffer */
1361 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1362 xfs_dir2_leaf_t *leaf; /* leaf structure */
1363 xfs_mount_t *mp; /* filesystem mount point */
1364 xfs_dir2_db_t newdb; /* new data block number */
1365 xfs_trans_t *tp; /* transaction pointer */
1371 * Read the leaf block into the buffer.
1374 xfs_da_read_buf(tp, dp, mp->m_dirleafblk, -1, &lbp,
1380 xfs_dir2_leaf_check(dp, lbp);
1382 * Look for the first leaf entry with our hash value.
1384 index = xfs_dir2_leaf_search_hash(args, lbp);
1386 * Loop over all the entries with the right hash value
1387 * looking to match the name.
1389 for (lep = &leaf->ents[index], dbp = NULL, curdb = -1;
1390 index < INT_GET(leaf->hdr.count, ARCH_CONVERT) && INT_GET(lep->hashval, ARCH_CONVERT) == args->hashval;
1393 * Skip over stale leaf entries.
1395 if (INT_GET(lep->address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
1398 * Get the new data block number.
1400 newdb = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
1402 * If it's not the same as the old data block number,
1403 * need to pitch the old one and read the new one.
1405 if (newdb != curdb) {
1407 xfs_da_brelse(tp, dbp);
1409 xfs_da_read_buf(tp, dp,
1410 XFS_DIR2_DB_TO_DA(mp, newdb), -1, &dbp,
1412 xfs_da_brelse(tp, lbp);
1415 xfs_dir2_data_check(dp, dbp);
1419 * Point to the data entry.
1421 dep = (xfs_dir2_data_entry_t *)
1422 ((char *)dbp->data +
1423 XFS_DIR2_DATAPTR_TO_OFF(mp, INT_GET(lep->address, ARCH_CONVERT)));
1425 * If it matches then return it.
1427 if (dep->namelen == args->namelen &&
1428 dep->name[0] == args->name[0] &&
1429 memcmp(dep->name, args->name, args->namelen) == 0) {
1436 * No match found, return ENOENT.
1438 ASSERT(args->oknoent);
1440 xfs_da_brelse(tp, dbp);
1441 xfs_da_brelse(tp, lbp);
1442 return XFS_ERROR(ENOENT);
1446 * Remove an entry from a leaf format directory.
1449 xfs_dir2_leaf_removename(
1450 xfs_da_args_t *args) /* operation arguments */
1452 xfs_dir2_data_off_t *bestsp; /* leaf block best freespace */
1453 xfs_dir2_data_t *data; /* data block structure */
1454 xfs_dir2_db_t db; /* data block number */
1455 xfs_dabuf_t *dbp; /* data block buffer */
1456 xfs_dir2_data_entry_t *dep; /* data entry structure */
1457 xfs_inode_t *dp; /* incore directory inode */
1458 int error; /* error return code */
1459 xfs_dir2_db_t i; /* temporary data block # */
1460 int index; /* index into leaf entries */
1461 xfs_dabuf_t *lbp; /* leaf buffer */
1462 xfs_dir2_leaf_t *leaf; /* leaf structure */
1463 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1464 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1465 xfs_mount_t *mp; /* filesystem mount point */
1466 int needlog; /* need to log data header */
1467 int needscan; /* need to rescan data frees */
1468 xfs_dir2_data_off_t oldbest; /* old value of best free */
1469 xfs_trans_t *tp; /* transaction pointer */
1471 xfs_dir2_trace_args("leaf_removename", args);
1473 * Lookup the leaf entry, get the leaf and data blocks read in.
1475 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1483 xfs_dir2_data_check(dp, dbp);
1485 * Point to the leaf entry, use that to point to the data entry.
1487 lep = &leaf->ents[index];
1488 db = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
1489 dep = (xfs_dir2_data_entry_t *)
1490 ((char *)data + XFS_DIR2_DATAPTR_TO_OFF(mp, INT_GET(lep->address, ARCH_CONVERT)));
1491 needscan = needlog = 0;
1492 oldbest = INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT);
1493 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1494 bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
1495 ASSERT(INT_GET(bestsp[db], ARCH_CONVERT) == oldbest);
1497 * Mark the former data entry unused.
1499 xfs_dir2_data_make_free(tp, dbp,
1500 (xfs_dir2_data_aoff_t)((char *)dep - (char *)data),
1501 XFS_DIR2_DATA_ENTSIZE(dep->namelen), &needlog, &needscan);
1503 * We just mark the leaf entry stale by putting a null in it.
1505 INT_MOD(leaf->hdr.stale, ARCH_CONVERT, +1);
1506 xfs_dir2_leaf_log_header(tp, lbp);
1507 INT_SET(lep->address, ARCH_CONVERT, XFS_DIR2_NULL_DATAPTR);
1508 xfs_dir2_leaf_log_ents(tp, lbp, index, index);
1510 * Scan the freespace in the data block again if necessary,
1511 * log the data block header if necessary.
1514 xfs_dir2_data_freescan(mp, data, &needlog, NULL);
1516 xfs_dir2_data_log_header(tp, dbp);
1518 * If the longest freespace in the data block has changed,
1519 * put the new value in the bests table and log that.
1521 if (INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT) != oldbest) {
1522 INT_COPY(bestsp[db], data->hdr.bestfree[0].length, ARCH_CONVERT);
1523 xfs_dir2_leaf_log_bests(tp, lbp, db, db);
1525 xfs_dir2_data_check(dp, dbp);
1527 * If the data block is now empty then get rid of the data block.
1529 if (INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT) ==
1530 mp->m_dirblksize - (uint)sizeof(data->hdr)) {
1531 ASSERT(db != mp->m_dirdatablk);
1532 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1534 * Nope, can't get rid of it because it caused
1535 * allocation of a bmap btree block to do so.
1536 * Just go on, returning success, leaving the
1537 * empty block in place.
1539 if (error == ENOSPC && args->total == 0) {
1540 xfs_da_buf_done(dbp);
1543 xfs_dir2_leaf_check(dp, lbp);
1544 xfs_da_buf_done(lbp);
1549 * If this is the last data block then compact the
1550 * bests table by getting rid of entries.
1552 if (db == INT_GET(ltp->bestcount, ARCH_CONVERT) - 1) {
1554 * Look for the last active entry (i).
1556 for (i = db - 1; i > 0; i--) {
1557 if (INT_GET(bestsp[i], ARCH_CONVERT) != NULLDATAOFF)
1561 * Copy the table down so inactive entries at the
1564 memmove(&bestsp[db - i], bestsp,
1565 (INT_GET(ltp->bestcount, ARCH_CONVERT) - (db - i)) * sizeof(*bestsp));
1566 INT_MOD(ltp->bestcount, ARCH_CONVERT, -(db - i));
1567 xfs_dir2_leaf_log_tail(tp, lbp);
1568 xfs_dir2_leaf_log_bests(tp, lbp, 0, INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
1570 INT_SET(bestsp[db], ARCH_CONVERT, NULLDATAOFF);
1573 * If the data block was not the first one, drop it.
1575 else if (db != mp->m_dirdatablk && dbp != NULL) {
1576 xfs_da_buf_done(dbp);
1579 xfs_dir2_leaf_check(dp, lbp);
1581 * See if we can convert to block form.
1583 return xfs_dir2_leaf_to_block(args, lbp, dbp);
1587 * Replace the inode number in a leaf format directory entry.
1590 xfs_dir2_leaf_replace(
1591 xfs_da_args_t *args) /* operation arguments */
1593 xfs_dabuf_t *dbp; /* data block buffer */
1594 xfs_dir2_data_entry_t *dep; /* data block entry */
1595 xfs_inode_t *dp; /* incore directory inode */
1596 int error; /* error return code */
1597 int index; /* index of leaf entry */
1598 xfs_dabuf_t *lbp; /* leaf buffer */
1599 xfs_dir2_leaf_t *leaf; /* leaf structure */
1600 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1601 xfs_trans_t *tp; /* transaction pointer */
1603 xfs_dir2_trace_args("leaf_replace", args);
1605 * Look up the entry.
1607 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1613 * Point to the leaf entry, get data address from it.
1615 lep = &leaf->ents[index];
1617 * Point to the data entry.
1619 dep = (xfs_dir2_data_entry_t *)
1620 ((char *)dbp->data +
1621 XFS_DIR2_DATAPTR_TO_OFF(dp->i_mount, INT_GET(lep->address, ARCH_CONVERT)));
1622 ASSERT(args->inumber != INT_GET(dep->inumber, ARCH_CONVERT));
1624 * Put the new inode number in, log it.
1626 INT_SET(dep->inumber, ARCH_CONVERT, args->inumber);
1628 xfs_dir2_data_log_entry(tp, dbp, dep);
1629 xfs_da_buf_done(dbp);
1630 xfs_dir2_leaf_check(dp, lbp);
1631 xfs_da_brelse(tp, lbp);
1636 * Return index in the leaf block (lbp) which is either the first
1637 * one with this hash value, or if there are none, the insert point
1638 * for that hash value.
1640 int /* index value */
1641 xfs_dir2_leaf_search_hash(
1642 xfs_da_args_t *args, /* operation arguments */
1643 xfs_dabuf_t *lbp) /* leaf buffer */
1645 xfs_dahash_t hash=0; /* hash from this entry */
1646 xfs_dahash_t hashwant; /* hash value looking for */
1647 int high; /* high leaf index */
1648 int low; /* low leaf index */
1649 xfs_dir2_leaf_t *leaf; /* leaf structure */
1650 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1651 int mid=0; /* current leaf index */
1655 if (!leaf->hdr.count)
1659 * Note, the table cannot be empty, so we have to go through the loop.
1660 * Binary search the leaf entries looking for our hash value.
1662 for (lep = leaf->ents, low = 0, high = INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1,
1663 hashwant = args->hashval;
1665 mid = (low + high) >> 1;
1666 if ((hash = INT_GET(lep[mid].hashval, ARCH_CONVERT)) == hashwant)
1668 if (hash < hashwant)
1674 * Found one, back up through all the equal hash values.
1676 if (hash == hashwant) {
1677 while (mid > 0 && INT_GET(lep[mid - 1].hashval, ARCH_CONVERT) == hashwant) {
1682 * Need to point to an entry higher than ours.
1684 else if (hash < hashwant)
1690 * Trim off a trailing data block. We know it's empty since the leaf
1691 * freespace table says so.
1694 xfs_dir2_leaf_trim_data(
1695 xfs_da_args_t *args, /* operation arguments */
1696 xfs_dabuf_t *lbp, /* leaf buffer */
1697 xfs_dir2_db_t db) /* data block number */
1699 xfs_dir2_data_off_t *bestsp; /* leaf bests table */
1701 xfs_dir2_data_t *data; /* data block structure */
1703 xfs_dabuf_t *dbp; /* data block buffer */
1704 xfs_inode_t *dp; /* incore directory inode */
1705 int error; /* error return value */
1706 xfs_dir2_leaf_t *leaf; /* leaf structure */
1707 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1708 xfs_mount_t *mp; /* filesystem mount point */
1709 xfs_trans_t *tp; /* transaction pointer */
1715 * Read the offending data block. We need its buffer.
1717 if ((error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, db), -1, &dbp,
1723 ASSERT(INT_GET(data->hdr.magic, ARCH_CONVERT) == XFS_DIR2_DATA_MAGIC);
1725 /* this seems to be an error
1726 * data is only valid if DEBUG is defined?
1731 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1732 ASSERT(INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT) ==
1733 mp->m_dirblksize - (uint)sizeof(data->hdr));
1734 ASSERT(db == INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
1736 * Get rid of the data block.
1738 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1739 ASSERT(error != ENOSPC);
1740 xfs_da_brelse(tp, dbp);
1744 * Eliminate the last bests entry from the table.
1746 bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
1747 INT_MOD(ltp->bestcount, ARCH_CONVERT, -1);
1748 memmove(&bestsp[1], &bestsp[0], INT_GET(ltp->bestcount, ARCH_CONVERT) * sizeof(*bestsp));
1749 xfs_dir2_leaf_log_tail(tp, lbp);
1750 xfs_dir2_leaf_log_bests(tp, lbp, 0, INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
1755 * Convert node form directory to leaf form directory.
1756 * The root of the node form dir needs to already be a LEAFN block.
1757 * Just return if we can't do anything.
1760 xfs_dir2_node_to_leaf(
1761 xfs_da_state_t *state) /* directory operation state */
1763 xfs_da_args_t *args; /* operation arguments */
1764 xfs_inode_t *dp; /* incore directory inode */
1765 int error; /* error return code */
1766 xfs_dabuf_t *fbp; /* buffer for freespace block */
1767 xfs_fileoff_t fo; /* freespace file offset */
1768 xfs_dir2_free_t *free; /* freespace structure */
1769 xfs_dabuf_t *lbp; /* buffer for leaf block */
1770 xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */
1771 xfs_dir2_leaf_t *leaf; /* leaf structure */
1772 xfs_mount_t *mp; /* filesystem mount point */
1773 int rval; /* successful free trim? */
1774 xfs_trans_t *tp; /* transaction pointer */
1777 * There's more than a leaf level in the btree, so there must
1778 * be multiple leafn blocks. Give up.
1780 if (state->path.active > 1)
1783 xfs_dir2_trace_args("node_to_leaf", args);
1788 * Get the last offset in the file.
1790 if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK))) {
1793 fo -= mp->m_dirblkfsbs;
1795 * If there are freespace blocks other than the first one,
1796 * take this opportunity to remove trailing empty freespace blocks
1797 * that may have been left behind during no-space-reservation
1800 while (fo > mp->m_dirfreeblk) {
1801 if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
1805 fo -= mp->m_dirblkfsbs;
1810 * Now find the block just before the freespace block.
1812 if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
1816 * If it's not the single leaf block, give up.
1818 if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + mp->m_dirblksize)
1820 lbp = state->path.blk[0].bp;
1822 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1824 * Read the freespace block.
1826 if ((error = xfs_da_read_buf(tp, dp, mp->m_dirfreeblk, -1, &fbp,
1831 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
1832 ASSERT(!free->hdr.firstdb);
1834 * Now see if the leafn and free data will fit in a leaf1.
1835 * If not, release the buffer and give up.
1837 if ((uint)sizeof(leaf->hdr) +
1838 (INT_GET(leaf->hdr.count, ARCH_CONVERT) - INT_GET(leaf->hdr.stale, ARCH_CONVERT)) * (uint)sizeof(leaf->ents[0]) +
1839 INT_GET(free->hdr.nvalid, ARCH_CONVERT) * (uint)sizeof(leaf->bests[0]) +
1840 (uint)sizeof(leaf->tail) >
1842 xfs_da_brelse(tp, fbp);
1846 * If the leaf has any stale entries in it, compress them out.
1847 * The compact routine will log the header.
1849 if (INT_GET(leaf->hdr.stale, ARCH_CONVERT))
1850 xfs_dir2_leaf_compact(args, lbp);
1852 xfs_dir2_leaf_log_header(tp, lbp);
1853 INT_SET(leaf->hdr.info.magic, ARCH_CONVERT, XFS_DIR2_LEAF1_MAGIC);
1855 * Set up the leaf tail from the freespace block.
1857 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1858 INT_COPY(ltp->bestcount, free->hdr.nvalid, ARCH_CONVERT);
1860 * Set up the leaf bests table.
1862 memcpy(XFS_DIR2_LEAF_BESTS_P(ltp), free->bests,
1863 INT_GET(ltp->bestcount, ARCH_CONVERT) * sizeof(leaf->bests[0]));
1864 xfs_dir2_leaf_log_bests(tp, lbp, 0, INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
1865 xfs_dir2_leaf_log_tail(tp, lbp);
1866 xfs_dir2_leaf_check(dp, lbp);
1868 * Get rid of the freespace block.
1870 error = xfs_dir2_shrink_inode(args, XFS_DIR2_FREE_FIRSTDB(mp), fbp);
1873 * This can't fail here because it can only happen when
1874 * punching out the middle of an extent, and this is an
1877 ASSERT(error != ENOSPC);
1882 * Now see if we can convert the single-leaf directory
1883 * down to a block form directory.
1884 * This routine always kills the dabuf for the leaf, so
1885 * eliminate it from the path.
1887 error = xfs_dir2_leaf_to_block(args, lbp, NULL);
1888 state->path.blk[0].bp = NULL;