2 * Copyright (c) 2000-2002 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/
35 * XFS directory version 2 implementation - single leaf form
36 * see xfs_dir2_leaf.h for data structures.
37 * These directories have multiple XFS_DIR2_DATA blocks and one
38 * XFS_DIR2_LEAF1 block containing the hash table and freespace map.
45 * Convert a block form directory to a leaf form directory.
48 xfs_dir2_block_to_leaf(
49 xfs_da_args_t
*args
, /* operation arguments */
50 xfs_dabuf_t
*dbp
) /* input block's buffer */
52 xfs_dir2_data_off_t
*bestsp
; /* leaf's bestsp entries */
53 xfs_dablk_t blkno
; /* leaf block's bno */
54 xfs_dir2_block_t
*block
; /* block structure */
55 xfs_dir2_leaf_entry_t
*blp
; /* block's leaf entries */
56 xfs_dir2_block_tail_t
*btp
; /* block's tail */
57 xfs_inode_t
*dp
; /* incore directory inode */
58 int error
; /* error return code */
59 xfs_dabuf_t
*lbp
; /* leaf block's buffer */
60 xfs_dir2_db_t ldb
; /* leaf block's bno */
61 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
62 xfs_dir2_leaf_tail_t
*ltp
; /* leaf's tail */
63 xfs_mount_t
*mp
; /* filesystem mount point */
64 int needlog
; /* need to log block header */
65 int needscan
; /* need to rescan bestfree */
66 xfs_trans_t
*tp
; /* transaction pointer */
68 xfs_dir2_trace_args_b("block_to_leaf", args
, dbp
);
73 * Add the leaf block to the inode.
74 * This interface will only put blocks in the leaf/node range.
75 * Since that's empty now, we'll get the root (block 0 in range).
77 if ((error
= xfs_da_grow_inode(args
, &blkno
))) {
80 ldb
= XFS_DIR2_DA_TO_DB(mp
, blkno
);
81 ASSERT(ldb
== XFS_DIR2_LEAF_FIRSTDB(mp
));
83 * Initialize the leaf block, get a buffer for it.
85 if ((error
= xfs_dir2_leaf_init(args
, ldb
, &lbp
, XFS_DIR2_LEAF1_MAGIC
))) {
91 xfs_dir2_data_check(dp
, dbp
);
92 btp
= XFS_DIR2_BLOCK_TAIL_P(mp
, block
);
93 blp
= XFS_DIR2_BLOCK_LEAF_P_ARCH(btp
, ARCH_CONVERT
);
95 * Set the counts in the leaf header.
97 INT_COPY(leaf
->hdr
.count
, btp
->count
, ARCH_CONVERT
); /* INT_: type change */
98 INT_COPY(leaf
->hdr
.stale
, btp
->stale
, ARCH_CONVERT
); /* INT_: type change */
100 * Could compact these but I think we always do the conversion
101 * after squeezing out stale entries.
103 memcpy(leaf
->ents
, blp
, INT_GET(btp
->count
, ARCH_CONVERT
) * sizeof(xfs_dir2_leaf_entry_t
));
104 xfs_dir2_leaf_log_ents(tp
, lbp
, 0, INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - 1);
108 * Make the space formerly occupied by the leaf entries and block
111 xfs_dir2_data_make_free(tp
, dbp
,
112 (xfs_dir2_data_aoff_t
)((char *)blp
- (char *)block
),
113 (xfs_dir2_data_aoff_t
)((char *)block
+ mp
->m_dirblksize
-
115 &needlog
, &needscan
);
117 * Fix up the block header, make it a data block.
119 INT_SET(block
->hdr
.magic
, ARCH_CONVERT
, XFS_DIR2_DATA_MAGIC
);
121 xfs_dir2_data_freescan(mp
, (xfs_dir2_data_t
*)block
, &needlog
,
124 * Set up leaf tail and bests table.
126 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
127 INT_SET(ltp
->bestcount
, ARCH_CONVERT
, 1);
128 bestsp
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
);
129 INT_COPY(bestsp
[0], block
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
131 * Log the data header and leaf bests table.
134 xfs_dir2_data_log_header(tp
, dbp
);
135 xfs_dir2_leaf_check(dp
, lbp
);
136 xfs_dir2_data_check(dp
, dbp
);
137 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, 0);
138 xfs_da_buf_done(lbp
);
143 * Add an entry to a leaf form directory.
146 xfs_dir2_leaf_addname(
147 xfs_da_args_t
*args
) /* operation arguments */
149 xfs_dir2_data_off_t
*bestsp
; /* freespace table in leaf */
150 int compact
; /* need to compact leaves */
151 xfs_dir2_data_t
*data
; /* data block structure */
152 xfs_dabuf_t
*dbp
; /* data block buffer */
153 xfs_dir2_data_entry_t
*dep
; /* data block entry */
154 xfs_inode_t
*dp
; /* incore directory inode */
155 xfs_dir2_data_unused_t
*dup
; /* data unused entry */
156 int error
; /* error return value */
157 int grown
; /* allocated new data block */
158 int highstale
; /* index of next stale leaf */
159 int i
; /* temporary, index */
160 int index
; /* leaf table position */
161 xfs_dabuf_t
*lbp
; /* leaf's buffer */
162 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
163 int length
; /* length of new entry */
164 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry table pointer */
165 int lfloglow
; /* low leaf logging index */
166 int lfloghigh
; /* high leaf logging index */
167 int lowstale
; /* index of prev stale leaf */
168 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail pointer */
169 xfs_mount_t
*mp
; /* filesystem mount point */
170 int needbytes
; /* leaf block bytes needed */
171 int needlog
; /* need to log data header */
172 int needscan
; /* need to rescan data free */
173 xfs_dir2_data_off_t
*tagp
; /* end of data entry */
174 xfs_trans_t
*tp
; /* transaction pointer */
175 xfs_dir2_db_t use_block
; /* data block number */
177 xfs_dir2_trace_args("leaf_addname", args
);
182 * Read the leaf block.
184 error
= xfs_da_read_buf(tp
, dp
, mp
->m_dirleafblk
, -1, &lbp
,
191 * Look up the entry by hash value and name.
192 * We know it's not there, our caller has already done a lookup.
193 * So the index is of the entry to insert in front of.
194 * But if there are dup hash values the index is of the first of those.
196 index
= xfs_dir2_leaf_search_hash(args
, lbp
);
198 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
199 bestsp
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
);
200 length
= XFS_DIR2_DATA_ENTSIZE(args
->namelen
);
202 * See if there are any entries with the same hash value
203 * and space in their block for the new entry.
204 * This is good because it puts multiple same-hash value entries
205 * in a data block, improving the lookup of those entries.
207 for (use_block
= -1, lep
= &leaf
->ents
[index
];
208 index
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) && INT_GET(lep
->hashval
, ARCH_CONVERT
) == args
->hashval
;
210 if (INT_GET(lep
->address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
212 i
= XFS_DIR2_DATAPTR_TO_DB(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
213 ASSERT(i
< INT_GET(ltp
->bestcount
, ARCH_CONVERT
));
214 ASSERT(INT_GET(bestsp
[i
], ARCH_CONVERT
) != NULLDATAOFF
);
215 if (INT_GET(bestsp
[i
], ARCH_CONVERT
) >= length
) {
221 * Didn't find a block yet, linear search all the data blocks.
223 if (use_block
== -1) {
224 for (i
= 0; i
< INT_GET(ltp
->bestcount
, ARCH_CONVERT
); i
++) {
226 * Remember a block we see that's missing.
228 if (INT_GET(bestsp
[i
], ARCH_CONVERT
) == NULLDATAOFF
&& use_block
== -1)
230 else if (INT_GET(bestsp
[i
], ARCH_CONVERT
) >= length
) {
237 * How many bytes do we need in the leaf block?
240 (!INT_ISZERO(leaf
->hdr
.stale
, ARCH_CONVERT
) ? 0 : (uint
)sizeof(leaf
->ents
[0])) +
241 (use_block
!= -1 ? 0 : (uint
)sizeof(leaf
->bests
[0]));
243 * Now kill use_block if it refers to a missing block, so we
244 * can use it as an indication of allocation needed.
246 if (use_block
!= -1 && INT_GET(bestsp
[use_block
], ARCH_CONVERT
) == NULLDATAOFF
)
249 * If we don't have enough free bytes but we can make enough
250 * by compacting out stale entries, we'll do that.
252 if ((char *)bestsp
- (char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] < needbytes
&&
253 INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) > 1) {
257 * Otherwise if we don't have enough free bytes we need to
258 * convert to node form.
260 else if ((char *)bestsp
- (char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] <
263 * Just checking or no space reservation, give up.
265 if (args
->justcheck
|| args
->total
== 0) {
266 xfs_da_brelse(tp
, lbp
);
267 return XFS_ERROR(ENOSPC
);
270 * Convert to node form.
272 error
= xfs_dir2_leaf_to_node(args
, lbp
);
273 xfs_da_buf_done(lbp
);
277 * Then add the new entry.
279 return xfs_dir2_node_addname(args
);
282 * Otherwise it will fit without compaction.
287 * If just checking, then it will fit unless we needed to allocate
290 if (args
->justcheck
) {
291 xfs_da_brelse(tp
, lbp
);
292 return use_block
== -1 ? XFS_ERROR(ENOSPC
) : 0;
295 * If no allocations are allowed, return now before we've
298 if (args
->total
== 0 && use_block
== -1) {
299 xfs_da_brelse(tp
, lbp
);
300 return XFS_ERROR(ENOSPC
);
303 * Need to compact the leaf entries, removing stale ones.
304 * Leave one stale entry behind - the one closest to our
305 * insertion index - and we'll shift that one to our insertion
309 xfs_dir2_leaf_compact_x1(lbp
, &index
, &lowstale
, &highstale
,
310 &lfloglow
, &lfloghigh
);
313 * There are stale entries, so we'll need log-low and log-high
314 * impossibly bad values later.
316 else if (INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
)) {
317 lfloglow
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
321 * If there was no data block space found, we need to allocate
324 if (use_block
== -1) {
326 * Add the new data block.
328 if ((error
= xfs_dir2_grow_inode(args
, XFS_DIR2_DATA_SPACE
,
330 xfs_da_brelse(tp
, lbp
);
334 * Initialize the block.
336 if ((error
= xfs_dir2_data_init(args
, use_block
, &dbp
))) {
337 xfs_da_brelse(tp
, lbp
);
341 * If we're adding a new data block on the end we need to
342 * extend the bests table. Copy it up one entry.
344 if (use_block
>= INT_GET(ltp
->bestcount
, ARCH_CONVERT
)) {
346 memmove(&bestsp
[0], &bestsp
[1],
347 INT_GET(ltp
->bestcount
, ARCH_CONVERT
) * sizeof(bestsp
[0]));
348 INT_MOD(ltp
->bestcount
, ARCH_CONVERT
, +1);
349 xfs_dir2_leaf_log_tail(tp
, lbp
);
350 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
353 * If we're filling in a previously empty block just log it.
356 xfs_dir2_leaf_log_bests(tp
, lbp
, use_block
, use_block
);
358 INT_COPY(bestsp
[use_block
], data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
362 * Already had space in some data block.
363 * Just read that one in.
367 xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, use_block
),
368 -1, &dbp
, XFS_DATA_FORK
))) {
369 xfs_da_brelse(tp
, lbp
);
375 xfs_dir2_data_check(dp
, dbp
);
377 * Point to the biggest freespace in our data block.
379 dup
= (xfs_dir2_data_unused_t
*)
380 ((char *)data
+ INT_GET(data
->hdr
.bestfree
[0].offset
, ARCH_CONVERT
));
381 ASSERT(INT_GET(dup
->length
, ARCH_CONVERT
) >= length
);
382 needscan
= needlog
= 0;
384 * Mark the initial part of our freespace in use for the new entry.
386 xfs_dir2_data_use_free(tp
, dbp
, dup
,
387 (xfs_dir2_data_aoff_t
)((char *)dup
- (char *)data
), length
,
388 &needlog
, &needscan
);
390 * Initialize our new entry (at last).
392 dep
= (xfs_dir2_data_entry_t
*)dup
;
393 INT_SET(dep
->inumber
, ARCH_CONVERT
, args
->inumber
);
394 dep
->namelen
= args
->namelen
;
395 memcpy(dep
->name
, args
->name
, dep
->namelen
);
396 tagp
= XFS_DIR2_DATA_ENTRY_TAG_P(dep
);
397 INT_SET(*tagp
, ARCH_CONVERT
, (xfs_dir2_data_off_t
)((char *)dep
- (char *)data
));
399 * Need to scan fix up the bestfree table.
402 xfs_dir2_data_freescan(mp
, data
, &needlog
, NULL
);
404 * Need to log the data block's header.
407 xfs_dir2_data_log_header(tp
, dbp
);
408 xfs_dir2_data_log_entry(tp
, dbp
, dep
);
410 * If the bests table needs to be changed, do it.
411 * Log the change unless we've already done that.
413 if (INT_GET(bestsp
[use_block
], ARCH_CONVERT
) != INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
)) {
414 INT_COPY(bestsp
[use_block
], data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
416 xfs_dir2_leaf_log_bests(tp
, lbp
, use_block
, use_block
);
419 * Now we need to make room to insert the leaf entry.
420 * If there are no stale entries, we just insert a hole at index.
422 if (INT_ISZERO(leaf
->hdr
.stale
, ARCH_CONVERT
)) {
424 * lep is still good as the index leaf entry.
426 if (index
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
))
427 memmove(lep
+ 1, lep
,
428 (INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - index
) * sizeof(*lep
));
430 * Record low and high logging indices for the leaf.
433 lfloghigh
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
434 INT_MOD(leaf
->hdr
.count
, ARCH_CONVERT
, +1);
437 * There are stale entries.
438 * We will use one of them for the new entry.
439 * It's probably not at the right location, so we'll have to
440 * shift some up or down first.
444 * If we didn't compact before, we need to find the nearest
445 * stale entries before and after our insertion point.
449 * Find the first stale entry before the insertion
452 for (lowstale
= index
- 1;
454 INT_GET(leaf
->ents
[lowstale
].address
, ARCH_CONVERT
) !=
455 XFS_DIR2_NULL_DATAPTR
;
459 * Find the next stale entry at or after the insertion
460 * point, if any. Stop if we go so far that the
461 * lowstale entry would be better.
463 for (highstale
= index
;
464 highstale
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) &&
465 INT_GET(leaf
->ents
[highstale
].address
, ARCH_CONVERT
) !=
466 XFS_DIR2_NULL_DATAPTR
&&
468 index
- lowstale
- 1 >= highstale
- index
);
473 * If the low one is better, use it.
476 (highstale
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) ||
477 index
- lowstale
- 1 < highstale
- index
)) {
478 ASSERT(index
- lowstale
- 1 >= 0);
479 ASSERT(INT_GET(leaf
->ents
[lowstale
].address
, ARCH_CONVERT
) ==
480 XFS_DIR2_NULL_DATAPTR
);
482 * Copy entries up to cover the stale entry
483 * and make room for the new entry.
485 if (index
- lowstale
- 1 > 0)
486 memmove(&leaf
->ents
[lowstale
],
487 &leaf
->ents
[lowstale
+ 1],
488 (index
- lowstale
- 1) * sizeof(*lep
));
489 lep
= &leaf
->ents
[index
- 1];
490 lfloglow
= MIN(lowstale
, lfloglow
);
491 lfloghigh
= MAX(index
- 1, lfloghigh
);
494 * The high one is better, so use that one.
497 ASSERT(highstale
- index
>= 0);
498 ASSERT(INT_GET(leaf
->ents
[highstale
].address
, ARCH_CONVERT
) ==
499 XFS_DIR2_NULL_DATAPTR
);
501 * Copy entries down to copver the stale entry
502 * and make room for the new entry.
504 if (highstale
- index
> 0)
505 memmove(&leaf
->ents
[index
+ 1],
507 (highstale
- index
) * sizeof(*lep
));
508 lep
= &leaf
->ents
[index
];
509 lfloglow
= MIN(index
, lfloglow
);
510 lfloghigh
= MAX(highstale
, lfloghigh
);
512 INT_MOD(leaf
->hdr
.stale
, ARCH_CONVERT
, -1);
515 * Fill in the new leaf entry.
517 INT_SET(lep
->hashval
, ARCH_CONVERT
, args
->hashval
);
518 INT_SET(lep
->address
, ARCH_CONVERT
, XFS_DIR2_DB_OFF_TO_DATAPTR(mp
, use_block
, INT_GET(*tagp
, ARCH_CONVERT
)));
520 * Log the leaf fields and give up the buffers.
522 xfs_dir2_leaf_log_header(tp
, lbp
);
523 xfs_dir2_leaf_log_ents(tp
, lbp
, lfloglow
, lfloghigh
);
524 xfs_dir2_leaf_check(dp
, lbp
);
525 xfs_da_buf_done(lbp
);
526 xfs_dir2_data_check(dp
, dbp
);
527 xfs_da_buf_done(dbp
);
533 * Check the internal consistency of a leaf1 block.
534 * Pop an assert if something is wrong.
538 xfs_inode_t
*dp
, /* incore directory inode */
539 xfs_dabuf_t
*bp
) /* leaf's buffer */
541 int i
; /* leaf index */
542 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
543 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail pointer */
544 xfs_mount_t
*mp
; /* filesystem mount point */
545 int stale
; /* count of stale leaves */
549 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
);
551 * This value is not restrictive enough.
552 * Should factor in the size of the bests table as well.
553 * We can deduce a value for that from di_size.
555 ASSERT(INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) <= XFS_DIR2_MAX_LEAF_ENTS(mp
));
556 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
558 * Leaves and bests don't overlap.
560 ASSERT((char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] <=
561 (char *)XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
));
563 * Check hash value order, count stale entries.
565 for (i
= stale
= 0; i
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
); i
++) {
566 if (i
+ 1 < INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
))
567 ASSERT(INT_GET(leaf
->ents
[i
].hashval
, ARCH_CONVERT
) <=
568 INT_GET(leaf
->ents
[i
+ 1].hashval
, ARCH_CONVERT
));
569 if (INT_GET(leaf
->ents
[i
].address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
572 ASSERT(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) == stale
);
577 * Compact out any stale entries in the leaf.
578 * Log the header and changed leaf entries, if any.
581 xfs_dir2_leaf_compact(
582 xfs_da_args_t
*args
, /* operation arguments */
583 xfs_dabuf_t
*bp
) /* leaf buffer */
585 int from
; /* source leaf index */
586 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
587 int loglow
; /* first leaf entry to log */
588 int to
; /* target leaf index */
591 if (INT_ISZERO(leaf
->hdr
.stale
, ARCH_CONVERT
)) {
595 * Compress out the stale entries in place.
597 for (from
= to
= 0, loglow
= -1; from
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
); from
++) {
598 if (INT_GET(leaf
->ents
[from
].address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
601 * Only actually copy the entries that are different.
606 leaf
->ents
[to
] = leaf
->ents
[from
];
611 * Update and log the header, log the leaf entries.
613 ASSERT(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) == from
- to
);
614 INT_MOD(leaf
->hdr
.count
, ARCH_CONVERT
, -(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
)));
615 INT_ZERO(leaf
->hdr
.stale
, ARCH_CONVERT
);
616 xfs_dir2_leaf_log_header(args
->trans
, bp
);
618 xfs_dir2_leaf_log_ents(args
->trans
, bp
, loglow
, to
- 1);
622 * Compact the leaf entries, removing stale ones.
623 * Leave one stale entry behind - the one closest to our
624 * insertion index - and the caller will shift that one to our insertion
626 * Return new insertion index, where the remaining stale entry is,
627 * and leaf logging indices.
630 xfs_dir2_leaf_compact_x1(
631 xfs_dabuf_t
*bp
, /* leaf buffer */
632 int *indexp
, /* insertion index */
633 int *lowstalep
, /* out: stale entry before us */
634 int *highstalep
, /* out: stale entry after us */
635 int *lowlogp
, /* out: low log index */
636 int *highlogp
) /* out: high log index */
638 int from
; /* source copy index */
639 int highstale
; /* stale entry at/after index */
640 int index
; /* insertion index */
641 int keepstale
; /* source index of kept stale */
642 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
643 int lowstale
; /* stale entry before index */
644 int newindex
=0; /* new insertion index */
645 int to
; /* destination copy index */
648 ASSERT(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) > 1);
651 * Find the first stale entry before our index, if any.
653 for (lowstale
= index
- 1;
655 INT_GET(leaf
->ents
[lowstale
].address
, ARCH_CONVERT
) != XFS_DIR2_NULL_DATAPTR
;
659 * Find the first stale entry at or after our index, if any.
660 * Stop if the answer would be worse than lowstale.
662 for (highstale
= index
;
663 highstale
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) &&
664 INT_GET(leaf
->ents
[highstale
].address
, ARCH_CONVERT
) != XFS_DIR2_NULL_DATAPTR
&&
665 (lowstale
< 0 || index
- lowstale
> highstale
- index
);
669 * Pick the better of lowstale and highstale.
672 (highstale
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) ||
673 index
- lowstale
<= highstale
- index
))
674 keepstale
= lowstale
;
676 keepstale
= highstale
;
678 * Copy the entries in place, removing all the stale entries
681 for (from
= to
= 0; from
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
); from
++) {
683 * Notice the new value of index.
687 if (from
!= keepstale
&&
688 INT_GET(leaf
->ents
[from
].address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
) {
694 * Record the new keepstale value for the insertion.
696 if (from
== keepstale
)
697 lowstale
= highstale
= to
;
699 * Copy only the entries that have moved.
702 leaf
->ents
[to
] = leaf
->ents
[from
];
707 * If the insertion point was past the last entry,
708 * set the new insertion point accordingly.
714 * Adjust the leaf header values.
716 INT_MOD(leaf
->hdr
.count
, ARCH_CONVERT
, -(from
- to
));
717 INT_SET(leaf
->hdr
.stale
, ARCH_CONVERT
, 1);
719 * Remember the low/high stale value only in the "right"
722 if (lowstale
>= newindex
)
725 highstale
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
726 *highlogp
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - 1;
727 *lowstalep
= lowstale
;
728 *highstalep
= highstale
;
732 * Initialize a new leaf block, leaf1 or leafn magic accepted.
736 xfs_da_args_t
*args
, /* operation arguments */
737 xfs_dir2_db_t bno
, /* directory block number */
738 xfs_dabuf_t
**bpp
, /* out: leaf buffer */
739 int magic
) /* magic number for block */
741 xfs_dabuf_t
*bp
; /* leaf buffer */
742 xfs_inode_t
*dp
; /* incore directory inode */
743 int error
; /* error return code */
744 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
745 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
746 xfs_mount_t
*mp
; /* filesystem mount point */
747 xfs_trans_t
*tp
; /* transaction pointer */
753 ASSERT(bno
>= XFS_DIR2_LEAF_FIRSTDB(mp
) &&
754 bno
< XFS_DIR2_FREE_FIRSTDB(mp
));
756 * Get the buffer for the block.
758 error
= xfs_da_get_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, bno
), -1, &bp
,
766 * Initialize the header.
768 INT_SET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
, magic
);
769 INT_ZERO(leaf
->hdr
.info
.forw
, ARCH_CONVERT
);
770 INT_ZERO(leaf
->hdr
.info
.back
, ARCH_CONVERT
);
771 INT_ZERO(leaf
->hdr
.count
, ARCH_CONVERT
);
772 INT_ZERO(leaf
->hdr
.stale
, ARCH_CONVERT
);
773 xfs_dir2_leaf_log_header(tp
, bp
);
775 * If it's a leaf-format directory initialize the tail.
776 * In this case our caller has the real bests table to copy into
779 if (magic
== XFS_DIR2_LEAF1_MAGIC
) {
780 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
781 INT_ZERO(ltp
->bestcount
, ARCH_CONVERT
);
782 xfs_dir2_leaf_log_tail(tp
, bp
);
789 * Log the bests entries indicated from a leaf1 block.
792 xfs_dir2_leaf_log_bests(
793 xfs_trans_t
*tp
, /* transaction pointer */
794 xfs_dabuf_t
*bp
, /* leaf buffer */
795 int first
, /* first entry to log */
796 int last
) /* last entry to log */
798 xfs_dir2_data_off_t
*firstb
; /* pointer to first entry */
799 xfs_dir2_data_off_t
*lastb
; /* pointer to last entry */
800 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
801 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
804 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
);
805 ltp
= XFS_DIR2_LEAF_TAIL_P(tp
->t_mountp
, leaf
);
806 firstb
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
) + first
;
807 lastb
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
) + last
;
808 xfs_da_log_buf(tp
, bp
, (uint
)((char *)firstb
- (char *)leaf
),
809 (uint
)((char *)lastb
- (char *)leaf
+ sizeof(*lastb
) - 1));
813 * Log the leaf entries indicated from a leaf1 or leafn block.
816 xfs_dir2_leaf_log_ents(
817 xfs_trans_t
*tp
, /* transaction pointer */
818 xfs_dabuf_t
*bp
, /* leaf buffer */
819 int first
, /* first entry to log */
820 int last
) /* last entry to log */
822 xfs_dir2_leaf_entry_t
*firstlep
; /* pointer to first entry */
823 xfs_dir2_leaf_entry_t
*lastlep
; /* pointer to last entry */
824 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
827 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
||
828 INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
829 firstlep
= &leaf
->ents
[first
];
830 lastlep
= &leaf
->ents
[last
];
831 xfs_da_log_buf(tp
, bp
, (uint
)((char *)firstlep
- (char *)leaf
),
832 (uint
)((char *)lastlep
- (char *)leaf
+ sizeof(*lastlep
) - 1));
836 * Log the header of the leaf1 or leafn block.
839 xfs_dir2_leaf_log_header(
840 xfs_trans_t
*tp
, /* transaction pointer */
841 xfs_dabuf_t
*bp
) /* leaf buffer */
843 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
846 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
||
847 INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
848 xfs_da_log_buf(tp
, bp
, (uint
)((char *)&leaf
->hdr
- (char *)leaf
),
849 (uint
)(sizeof(leaf
->hdr
) - 1));
853 * Log the tail of the leaf1 block.
856 xfs_dir2_leaf_log_tail(
857 xfs_trans_t
*tp
, /* transaction pointer */
858 xfs_dabuf_t
*bp
) /* leaf buffer */
860 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
861 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
862 xfs_mount_t
*mp
; /* filesystem mount point */
866 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
);
867 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
868 xfs_da_log_buf(tp
, bp
, (uint
)((char *)ltp
- (char *)leaf
),
869 (uint
)(mp
->m_dirblksize
- 1));
873 * Look up the entry referred to by args in the leaf format directory.
874 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
875 * is also used by the node-format code.
878 xfs_dir2_leaf_lookup(
879 xfs_da_args_t
*args
) /* operation arguments */
881 xfs_dabuf_t
*dbp
; /* data block buffer */
882 xfs_dir2_data_entry_t
*dep
; /* data block entry */
883 xfs_inode_t
*dp
; /* incore directory inode */
884 int error
; /* error return code */
885 int index
; /* found entry index */
886 xfs_dabuf_t
*lbp
; /* leaf buffer */
887 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
888 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
889 xfs_trans_t
*tp
; /* transaction pointer */
891 xfs_dir2_trace_args("leaf_lookup", args
);
893 * Look up name in the leaf block, returning both buffers and index.
895 if ((error
= xfs_dir2_leaf_lookup_int(args
, &lbp
, &index
, &dbp
))) {
900 xfs_dir2_leaf_check(dp
, lbp
);
903 * Get to the leaf entry and contained data entry address.
905 lep
= &leaf
->ents
[index
];
907 * Point to the data entry.
909 dep
= (xfs_dir2_data_entry_t
*)
911 XFS_DIR2_DATAPTR_TO_OFF(dp
->i_mount
, INT_GET(lep
->address
, ARCH_CONVERT
)));
913 * Return the found inode number.
915 args
->inumber
= INT_GET(dep
->inumber
, ARCH_CONVERT
);
916 xfs_da_brelse(tp
, dbp
);
917 xfs_da_brelse(tp
, lbp
);
918 return XFS_ERROR(EEXIST
);
922 * Look up name/hash in the leaf block.
923 * Fill in indexp with the found index, and dbpp with the data buffer.
924 * If not found dbpp will be NULL, and ENOENT comes back.
925 * lbpp will always be filled in with the leaf buffer unless there's an error.
927 STATIC
int /* error */
928 xfs_dir2_leaf_lookup_int(
929 xfs_da_args_t
*args
, /* operation arguments */
930 xfs_dabuf_t
**lbpp
, /* out: leaf buffer */
931 int *indexp
, /* out: index in leaf block */
932 xfs_dabuf_t
**dbpp
) /* out: data buffer */
934 xfs_dir2_db_t curdb
; /* current data block number */
935 xfs_dabuf_t
*dbp
; /* data buffer */
936 xfs_dir2_data_entry_t
*dep
; /* data entry */
937 xfs_inode_t
*dp
; /* incore directory inode */
938 int error
; /* error return code */
939 int index
; /* index in leaf block */
940 xfs_dabuf_t
*lbp
; /* leaf buffer */
941 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
942 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
943 xfs_mount_t
*mp
; /* filesystem mount point */
944 xfs_dir2_db_t newdb
; /* new data block number */
945 xfs_trans_t
*tp
; /* transaction pointer */
951 * Read the leaf block into the buffer.
954 xfs_da_read_buf(tp
, dp
, mp
->m_dirleafblk
, -1, &lbp
,
960 xfs_dir2_leaf_check(dp
, lbp
);
962 * Look for the first leaf entry with our hash value.
964 index
= xfs_dir2_leaf_search_hash(args
, lbp
);
966 * Loop over all the entries with the right hash value
967 * looking to match the name.
969 for (lep
= &leaf
->ents
[index
], dbp
= NULL
, curdb
= -1;
970 index
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) && INT_GET(lep
->hashval
, ARCH_CONVERT
) == args
->hashval
;
973 * Skip over stale leaf entries.
975 if (INT_GET(lep
->address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
978 * Get the new data block number.
980 newdb
= XFS_DIR2_DATAPTR_TO_DB(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
982 * If it's not the same as the old data block number,
983 * need to pitch the old one and read the new one.
985 if (newdb
!= curdb
) {
987 xfs_da_brelse(tp
, dbp
);
989 xfs_da_read_buf(tp
, dp
,
990 XFS_DIR2_DB_TO_DA(mp
, newdb
), -1, &dbp
,
992 xfs_da_brelse(tp
, lbp
);
995 xfs_dir2_data_check(dp
, dbp
);
999 * Point to the data entry.
1001 dep
= (xfs_dir2_data_entry_t
*)
1002 ((char *)dbp
->data
+
1003 XFS_DIR2_DATAPTR_TO_OFF(mp
, INT_GET(lep
->address
, ARCH_CONVERT
)));
1005 * If it matches then return it.
1007 if (dep
->namelen
== args
->namelen
&&
1008 dep
->name
[0] == args
->name
[0] &&
1009 memcmp(dep
->name
, args
->name
, args
->namelen
) == 0) {
1016 * No match found, return ENOENT.
1018 ASSERT(args
->oknoent
);
1020 xfs_da_brelse(tp
, dbp
);
1021 xfs_da_brelse(tp
, lbp
);
1022 return XFS_ERROR(ENOENT
);
1026 * Remove an entry from a leaf format directory.
1029 xfs_dir2_leaf_removename(
1030 xfs_da_args_t
*args
) /* operation arguments */
1032 xfs_dir2_data_off_t
*bestsp
; /* leaf block best freespace */
1033 xfs_dir2_data_t
*data
; /* data block structure */
1034 xfs_dir2_db_t db
; /* data block number */
1035 xfs_dabuf_t
*dbp
; /* data block buffer */
1036 xfs_dir2_data_entry_t
*dep
; /* data entry structure */
1037 xfs_inode_t
*dp
; /* incore directory inode */
1038 int error
; /* error return code */
1039 xfs_dir2_db_t i
; /* temporary data block # */
1040 int index
; /* index into leaf entries */
1041 xfs_dabuf_t
*lbp
; /* leaf buffer */
1042 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1043 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
1044 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
1045 xfs_mount_t
*mp
; /* filesystem mount point */
1046 int needlog
; /* need to log data header */
1047 int needscan
; /* need to rescan data frees */
1048 xfs_dir2_data_off_t oldbest
; /* old value of best free */
1049 xfs_trans_t
*tp
; /* transaction pointer */
1051 xfs_dir2_trace_args("leaf_removename", args
);
1053 * Lookup the leaf entry, get the leaf and data blocks read in.
1055 if ((error
= xfs_dir2_leaf_lookup_int(args
, &lbp
, &index
, &dbp
))) {
1063 xfs_dir2_data_check(dp
, dbp
);
1065 * Point to the leaf entry, use that to point to the data entry.
1067 lep
= &leaf
->ents
[index
];
1068 db
= XFS_DIR2_DATAPTR_TO_DB(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
1069 dep
= (xfs_dir2_data_entry_t
*)
1070 ((char *)data
+ XFS_DIR2_DATAPTR_TO_OFF(mp
, INT_GET(lep
->address
, ARCH_CONVERT
)));
1071 needscan
= needlog
= 0;
1072 oldbest
= INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
1073 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
1074 bestsp
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
);
1075 ASSERT(INT_GET(bestsp
[db
], ARCH_CONVERT
) == oldbest
);
1077 * Mark the former data entry unused.
1079 xfs_dir2_data_make_free(tp
, dbp
,
1080 (xfs_dir2_data_aoff_t
)((char *)dep
- (char *)data
),
1081 XFS_DIR2_DATA_ENTSIZE(dep
->namelen
), &needlog
, &needscan
);
1083 * We just mark the leaf entry stale by putting a null in it.
1085 INT_MOD(leaf
->hdr
.stale
, ARCH_CONVERT
, +1);
1086 xfs_dir2_leaf_log_header(tp
, lbp
);
1087 INT_SET(lep
->address
, ARCH_CONVERT
, XFS_DIR2_NULL_DATAPTR
);
1088 xfs_dir2_leaf_log_ents(tp
, lbp
, index
, index
);
1090 * Scan the freespace in the data block again if necessary,
1091 * log the data block header if necessary.
1094 xfs_dir2_data_freescan(mp
, data
, &needlog
, NULL
);
1096 xfs_dir2_data_log_header(tp
, dbp
);
1098 * If the longest freespace in the data block has changed,
1099 * put the new value in the bests table and log that.
1101 if (INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
) != oldbest
) {
1102 INT_COPY(bestsp
[db
], data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
1103 xfs_dir2_leaf_log_bests(tp
, lbp
, db
, db
);
1105 xfs_dir2_data_check(dp
, dbp
);
1107 * If the data block is now empty then get rid of the data block.
1109 if (INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
) ==
1110 mp
->m_dirblksize
- (uint
)sizeof(data
->hdr
)) {
1111 ASSERT(db
!= mp
->m_dirdatablk
);
1112 if ((error
= xfs_dir2_shrink_inode(args
, db
, dbp
))) {
1114 * Nope, can't get rid of it because it caused
1115 * allocation of a bmap btree block to do so.
1116 * Just go on, returning success, leaving the
1117 * empty block in place.
1119 if (error
== ENOSPC
&& args
->total
== 0) {
1120 xfs_da_buf_done(dbp
);
1123 xfs_dir2_leaf_check(dp
, lbp
);
1124 xfs_da_buf_done(lbp
);
1129 * If this is the last data block then compact the
1130 * bests table by getting rid of entries.
1132 if (db
== INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1) {
1134 * Look for the last active entry (i).
1136 for (i
= db
- 1; i
> 0; i
--) {
1137 if (INT_GET(bestsp
[i
], ARCH_CONVERT
) != NULLDATAOFF
)
1141 * Copy the table down so inactive entries at the
1144 memmove(&bestsp
[db
- i
], bestsp
,
1145 (INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - (db
- i
)) * sizeof(*bestsp
));
1146 INT_MOD(ltp
->bestcount
, ARCH_CONVERT
, -(db
- i
));
1147 xfs_dir2_leaf_log_tail(tp
, lbp
);
1148 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
1150 INT_SET(bestsp
[db
], ARCH_CONVERT
, NULLDATAOFF
);
1153 * If the data block was not the first one, drop it.
1155 else if (db
!= mp
->m_dirdatablk
&& dbp
!= NULL
) {
1156 xfs_da_buf_done(dbp
);
1159 xfs_dir2_leaf_check(dp
, lbp
);
1161 * See if we can convert to block form.
1163 return xfs_dir2_leaf_to_block(args
, lbp
, dbp
);
1167 * Replace the inode number in a leaf format directory entry.
1170 xfs_dir2_leaf_replace(
1171 xfs_da_args_t
*args
) /* operation arguments */
1173 xfs_dabuf_t
*dbp
; /* data block buffer */
1174 xfs_dir2_data_entry_t
*dep
; /* data block entry */
1175 xfs_inode_t
*dp
; /* incore directory inode */
1176 int error
; /* error return code */
1177 int index
; /* index of leaf entry */
1178 xfs_dabuf_t
*lbp
; /* leaf buffer */
1179 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1180 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
1181 xfs_trans_t
*tp
; /* transaction pointer */
1183 xfs_dir2_trace_args("leaf_replace", args
);
1185 * Look up the entry.
1187 if ((error
= xfs_dir2_leaf_lookup_int(args
, &lbp
, &index
, &dbp
))) {
1193 * Point to the leaf entry, get data address from it.
1195 lep
= &leaf
->ents
[index
];
1197 * Point to the data entry.
1199 dep
= (xfs_dir2_data_entry_t
*)
1200 ((char *)dbp
->data
+
1201 XFS_DIR2_DATAPTR_TO_OFF(dp
->i_mount
, INT_GET(lep
->address
, ARCH_CONVERT
)));
1202 ASSERT(args
->inumber
!= INT_GET(dep
->inumber
, ARCH_CONVERT
));
1204 * Put the new inode number in, log it.
1206 INT_SET(dep
->inumber
, ARCH_CONVERT
, args
->inumber
);
1208 xfs_dir2_data_log_entry(tp
, dbp
, dep
);
1209 xfs_da_buf_done(dbp
);
1210 xfs_dir2_leaf_check(dp
, lbp
);
1211 xfs_da_brelse(tp
, lbp
);
1216 * Return index in the leaf block (lbp) which is either the first
1217 * one with this hash value, or if there are none, the insert point
1218 * for that hash value.
1220 int /* index value */
1221 xfs_dir2_leaf_search_hash(
1222 xfs_da_args_t
*args
, /* operation arguments */
1223 xfs_dabuf_t
*lbp
) /* leaf buffer */
1225 xfs_dahash_t hash
=0; /* hash from this entry */
1226 xfs_dahash_t hashwant
; /* hash value looking for */
1227 int high
; /* high leaf index */
1228 int low
; /* low leaf index */
1229 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1230 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
1231 int mid
=0; /* current leaf index */
1235 if (INT_ISZERO(leaf
->hdr
.count
, ARCH_CONVERT
))
1239 * Note, the table cannot be empty, so we have to go through the loop.
1240 * Binary search the leaf entries looking for our hash value.
1242 for (lep
= leaf
->ents
, low
= 0, high
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - 1,
1243 hashwant
= args
->hashval
;
1245 mid
= (low
+ high
) >> 1;
1246 if ((hash
= INT_GET(lep
[mid
].hashval
, ARCH_CONVERT
)) == hashwant
)
1248 if (hash
< hashwant
)
1254 * Found one, back up through all the equal hash values.
1256 if (hash
== hashwant
) {
1257 while (mid
> 0 && INT_GET(lep
[mid
- 1].hashval
, ARCH_CONVERT
) == hashwant
) {
1262 * Need to point to an entry higher than ours.
1264 else if (hash
< hashwant
)
1270 * Trim off a trailing data block. We know it's empty since the leaf
1271 * freespace table says so.
1274 xfs_dir2_leaf_trim_data(
1275 xfs_da_args_t
*args
, /* operation arguments */
1276 xfs_dabuf_t
*lbp
, /* leaf buffer */
1277 xfs_dir2_db_t db
) /* data block number */
1279 xfs_dir2_data_off_t
*bestsp
; /* leaf bests table */
1281 xfs_dir2_data_t
*data
; /* data block structure */
1283 xfs_dabuf_t
*dbp
; /* data block buffer */
1284 xfs_inode_t
*dp
; /* incore directory inode */
1285 int error
; /* error return value */
1286 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1287 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
1288 xfs_mount_t
*mp
; /* filesystem mount point */
1289 xfs_trans_t
*tp
; /* transaction pointer */
1295 * Read the offending data block. We need its buffer.
1297 if ((error
= xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, db
), -1, &dbp
,
1303 ASSERT(INT_GET(data
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_DATA_MAGIC
);
1305 /* this seems to be an error
1306 * data is only valid if DEBUG is defined?
1311 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
1312 ASSERT(INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
) ==
1313 mp
->m_dirblksize
- (uint
)sizeof(data
->hdr
));
1314 ASSERT(db
== INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
1316 * Get rid of the data block.
1318 if ((error
= xfs_dir2_shrink_inode(args
, db
, dbp
))) {
1319 ASSERT(error
!= ENOSPC
);
1320 xfs_da_brelse(tp
, dbp
);
1324 * Eliminate the last bests entry from the table.
1326 bestsp
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
);
1327 INT_MOD(ltp
->bestcount
, ARCH_CONVERT
, -1);
1328 memmove(&bestsp
[1], &bestsp
[0], INT_GET(ltp
->bestcount
, ARCH_CONVERT
) * sizeof(*bestsp
));
1329 xfs_dir2_leaf_log_tail(tp
, lbp
);
1330 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
1335 * Convert node form directory to leaf form directory.
1336 * The root of the node form dir needs to already be a LEAFN block.
1337 * Just return if we can't do anything.
1340 xfs_dir2_node_to_leaf(
1341 xfs_da_state_t
*state
) /* directory operation state */
1343 xfs_da_args_t
*args
; /* operation arguments */
1344 xfs_inode_t
*dp
; /* incore directory inode */
1345 int error
; /* error return code */
1346 xfs_dabuf_t
*fbp
; /* buffer for freespace block */
1347 xfs_fileoff_t fo
; /* freespace file offset */
1348 xfs_dir2_free_t
*free
; /* freespace structure */
1349 xfs_dabuf_t
*lbp
; /* buffer for leaf block */
1350 xfs_dir2_leaf_tail_t
*ltp
; /* tail of leaf structure */
1351 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1352 xfs_mount_t
*mp
; /* filesystem mount point */
1353 int rval
; /* successful free trim? */
1354 xfs_trans_t
*tp
; /* transaction pointer */
1357 * There's more than a leaf level in the btree, so there must
1358 * be multiple leafn blocks. Give up.
1360 if (state
->path
.active
> 1)
1363 xfs_dir2_trace_args("node_to_leaf", args
);
1368 * Get the last offset in the file.
1370 if ((error
= xfs_bmap_last_offset(tp
, dp
, &fo
, XFS_DATA_FORK
))) {
1373 fo
-= mp
->m_dirblkfsbs
;
1375 * If there are freespace blocks other than the first one,
1376 * take this opportunity to remove trailing empty freespace blocks
1377 * that may have been left behind during no-space-reservation
1380 while (fo
> mp
->m_dirfreeblk
) {
1381 if ((error
= xfs_dir2_node_trim_free(args
, fo
, &rval
))) {
1385 fo
-= mp
->m_dirblkfsbs
;
1390 * Now find the block just before the freespace block.
1392 if ((error
= xfs_bmap_last_before(tp
, dp
, &fo
, XFS_DATA_FORK
))) {
1396 * If it's not the single leaf block, give up.
1398 if (XFS_FSB_TO_B(mp
, fo
) > XFS_DIR2_LEAF_OFFSET
+ mp
->m_dirblksize
)
1400 lbp
= state
->path
.blk
[0].bp
;
1402 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
1404 * Read the freespace block.
1406 if ((error
= xfs_da_read_buf(tp
, dp
, mp
->m_dirfreeblk
, -1, &fbp
,
1411 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
1412 ASSERT(INT_ISZERO(free
->hdr
.firstdb
, ARCH_CONVERT
));
1414 * Now see if the leafn and free data will fit in a leaf1.
1415 * If not, release the buffer and give up.
1417 if ((uint
)sizeof(leaf
->hdr
) +
1418 (INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
)) * (uint
)sizeof(leaf
->ents
[0]) +
1419 INT_GET(free
->hdr
.nvalid
, ARCH_CONVERT
) * (uint
)sizeof(leaf
->bests
[0]) +
1420 (uint
)sizeof(leaf
->tail
) >
1422 xfs_da_brelse(tp
, fbp
);
1426 * If the leaf has any stale entries in it, compress them out.
1427 * The compact routine will log the header.
1429 if (INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
))
1430 xfs_dir2_leaf_compact(args
, lbp
);
1432 xfs_dir2_leaf_log_header(tp
, lbp
);
1433 INT_SET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
, XFS_DIR2_LEAF1_MAGIC
);
1435 * Set up the leaf tail from the freespace block.
1437 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
1438 INT_COPY(ltp
->bestcount
, free
->hdr
.nvalid
, ARCH_CONVERT
);
1440 * Set up the leaf bests table.
1442 memcpy(XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
), free
->bests
,
1443 INT_GET(ltp
->bestcount
, ARCH_CONVERT
) * sizeof(leaf
->bests
[0]));
1444 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
1445 xfs_dir2_leaf_log_tail(tp
, lbp
);
1446 xfs_dir2_leaf_check(dp
, lbp
);
1448 * Get rid of the freespace block.
1450 error
= xfs_dir2_shrink_inode(args
, XFS_DIR2_FREE_FIRSTDB(mp
), fbp
);
1453 * This can't fail here because it can only happen when
1454 * punching out the middle of an extent, and this is an
1457 ASSERT(error
!= ENOSPC
);
1462 * Now see if we can convert the single-leaf directory
1463 * down to a block form directory.
1464 * This routine always kills the dabuf for the leaf, so
1465 * eliminate it from the path.
1467 error
= xfs_dir2_leaf_to_block(args
, lbp
, NULL
);
1468 state
->path
.blk
[0].bp
= NULL
;