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
;