2 * Copyright (c) 2000 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
)) {
78 #pragma mips_frequency_hint NEVER
81 ldb
= XFS_DIR2_DA_TO_DB(mp
, blkno
);
82 ASSERT(ldb
== XFS_DIR2_LEAF_FIRSTDB(mp
));
84 * Initialize the leaf block, get a buffer for it.
86 if (error
= xfs_dir2_leaf_init(args
, ldb
, &lbp
, XFS_DIR2_LEAF1_MAGIC
)) {
87 #pragma mips_frequency_hint NEVER
93 xfs_dir2_data_check(dp
, dbp
);
94 btp
= XFS_DIR2_BLOCK_TAIL_P(mp
, block
);
95 blp
= XFS_DIR2_BLOCK_LEAF_P_ARCH(btp
, ARCH_CONVERT
);
97 * Set the counts in the leaf header.
99 INT_COPY(leaf
->hdr
.count
, btp
->count
, ARCH_CONVERT
); /* INT_: type change */
100 INT_COPY(leaf
->hdr
.stale
, btp
->stale
, ARCH_CONVERT
); /* INT_: type change */
102 * Could compact these but I think we always do the conversion
103 * after squeezing out stale entries.
105 bcopy(blp
, leaf
->ents
, INT_GET(btp
->count
, ARCH_CONVERT
) * sizeof(xfs_dir2_leaf_entry_t
));
106 xfs_dir2_leaf_log_ents(tp
, lbp
, 0, INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - 1);
110 * Make the space formerly occupied by the leaf entries and block
113 xfs_dir2_data_make_free(tp
, dbp
,
114 (xfs_dir2_data_aoff_t
)((char *)blp
- (char *)block
),
115 (xfs_dir2_data_aoff_t
)((char *)block
+ mp
->m_dirblksize
-
117 &needlog
, &needscan
);
119 * Fix up the block header, make it a data block.
121 INT_SET(block
->hdr
.magic
, ARCH_CONVERT
, XFS_DIR2_DATA_MAGIC
);
123 xfs_dir2_data_freescan(mp
, (xfs_dir2_data_t
*)block
, &needlog
,
126 * Set up leaf tail and bests table.
128 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
129 INT_SET(ltp
->bestcount
, ARCH_CONVERT
, 1);
130 bestsp
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
);
131 INT_COPY(bestsp
[0], block
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
133 * Log the data header and leaf bests table.
136 xfs_dir2_data_log_header(tp
, dbp
);
137 xfs_dir2_leaf_check(dp
, lbp
);
138 xfs_dir2_data_check(dp
, dbp
);
139 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, 0);
140 xfs_da_buf_done(lbp
);
145 * Add an entry to a leaf form directory.
148 xfs_dir2_leaf_addname(
149 xfs_da_args_t
*args
) /* operation arguments */
151 xfs_dir2_data_off_t
*bestsp
; /* freespace table in leaf */
152 int compact
; /* need to compact leaves */
153 xfs_dir2_data_t
*data
; /* data block structure */
154 xfs_dabuf_t
*dbp
; /* data block buffer */
155 xfs_dir2_data_entry_t
*dep
; /* data block entry */
156 xfs_inode_t
*dp
; /* incore directory inode */
157 xfs_dir2_data_unused_t
*dup
; /* data unused entry */
158 int error
; /* error return value */
159 int grown
; /* allocated new data block */
160 int highstale
; /* index of next stale leaf */
161 int i
; /* temporary, index */
162 int index
; /* leaf table position */
163 xfs_dabuf_t
*lbp
; /* leaf's buffer */
164 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
165 int length
; /* length of new entry */
166 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry table pointer */
167 int lfloglow
; /* low leaf logging index */
168 int lfloghigh
; /* high leaf logging index */
169 int lowstale
; /* index of prev stale leaf */
170 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail pointer */
171 xfs_mount_t
*mp
; /* filesystem mount point */
172 int needbytes
; /* leaf block bytes needed */
173 int needlog
; /* need to log data header */
174 int needscan
; /* need to rescan data free */
175 xfs_dir2_data_off_t
*tagp
; /* end of data entry */
176 xfs_trans_t
*tp
; /* transaction pointer */
177 xfs_dir2_db_t use_block
; /* data block number */
179 xfs_dir2_trace_args("leaf_addname", args
);
184 * Read the leaf block.
186 error
= xfs_da_read_buf(tp
, dp
, mp
->m_dirleafblk
, -1, &lbp
,
189 #pragma mips_frequency_hint NEVER
194 * Look up the entry by hash value and name.
195 * We know it's not there, our caller has already done a lookup.
196 * So the index is of the entry to insert in front of.
197 * But if there are dup hash values the index is of the first of those.
199 index
= xfs_dir2_leaf_search_hash(args
, lbp
);
201 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
202 bestsp
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
);
203 length
= XFS_DIR2_DATA_ENTSIZE(args
->namelen
);
205 * See if there are any entries with the same hash value
206 * and space in their block for the new entry.
207 * This is good because it puts multiple same-hash value entries
208 * in a data block, improving the lookup of those entries.
210 for (use_block
= -1, lep
= &leaf
->ents
[index
];
211 index
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) && INT_GET(lep
->hashval
, ARCH_CONVERT
) == args
->hashval
;
213 if (INT_GET(lep
->address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
215 i
= XFS_DIR2_DATAPTR_TO_DB(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
216 ASSERT(i
< INT_GET(ltp
->bestcount
, ARCH_CONVERT
));
217 ASSERT(INT_GET(bestsp
[i
], ARCH_CONVERT
) != NULLDATAOFF
);
218 if (INT_GET(bestsp
[i
], ARCH_CONVERT
) >= length
) {
224 * Didn't find a block yet, linear search all the data blocks.
226 if (use_block
== -1) {
227 for (i
= 0; i
< INT_GET(ltp
->bestcount
, ARCH_CONVERT
); i
++) {
229 * Remember a block we see that's missing.
231 if (INT_GET(bestsp
[i
], ARCH_CONVERT
) == NULLDATAOFF
&& use_block
== -1)
233 else if (INT_GET(bestsp
[i
], ARCH_CONVERT
) >= length
) {
240 * How many bytes do we need in the leaf block?
243 (INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) != 0 ? 0 : (uint
)sizeof(leaf
->ents
[0])) +
244 (use_block
!= -1 ? 0 : (uint
)sizeof(leaf
->bests
[0]));
246 * Now kill use_block if it refers to a missing block, so we
247 * can use it as an indication of allocation needed.
249 if (use_block
!= -1 && INT_GET(bestsp
[use_block
], ARCH_CONVERT
) == NULLDATAOFF
)
252 * If we don't have enough free bytes but we can make enough
253 * by compacting out stale entries, we'll do that.
255 if ((char *)bestsp
- (char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] < needbytes
&&
256 INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) > 1) {
257 #pragma mips_frequency_hint NEVER
261 * Otherwise if we don't have enough free bytes we need to
262 * convert to node form.
264 else if ((char *)bestsp
- (char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] <
266 #pragma mips_frequency_hint NEVER
268 * Just checking or no space reservation, give up.
270 if (args
->justcheck
|| args
->total
== 0) {
271 xfs_da_brelse(tp
, lbp
);
272 return XFS_ERROR(ENOSPC
);
275 * Convert to node form.
277 error
= xfs_dir2_leaf_to_node(args
, lbp
);
278 xfs_da_buf_done(lbp
);
282 * Then add the new entry.
284 return xfs_dir2_node_addname(args
);
287 * Otherwise it will fit without compaction.
292 * If just checking, then it will fit unless we needed to allocate
295 if (args
->justcheck
) {
296 xfs_da_brelse(tp
, lbp
);
297 return use_block
== -1 ? XFS_ERROR(ENOSPC
) : 0;
300 * If no allocations are allowed, return now before we've
303 if (args
->total
== 0 && use_block
== -1) {
304 #pragma mips_frequency_hint NEVER
305 xfs_da_brelse(tp
, lbp
);
306 return XFS_ERROR(ENOSPC
);
309 * Need to compact the leaf entries, removing stale ones.
310 * Leave one stale entry behind - the one closest to our
311 * insertion index - and we'll shift that one to our insertion
315 #pragma mips_frequency_hint NEVER
316 xfs_dir2_leaf_compact_x1(lbp
, &index
, &lowstale
, &highstale
,
317 &lfloglow
, &lfloghigh
);
320 * There are stale entries, so we'll need log-low and log-high
321 * impossibly bad values later.
323 else if (INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
)) {
324 lfloglow
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
328 * If there was no data block space found, we need to allocate
331 if (use_block
== -1) {
332 #pragma mips_frequency_hint NEVER
334 * Add the new data block.
336 if (error
= xfs_dir2_grow_inode(args
, XFS_DIR2_DATA_SPACE
,
338 xfs_da_brelse(tp
, lbp
);
342 * Initialize the block.
344 if (error
= xfs_dir2_data_init(args
, use_block
, &dbp
)) {
345 xfs_da_brelse(tp
, lbp
);
349 * If we're adding a new data block on the end we need to
350 * extend the bests table. Copy it up one entry.
352 if (use_block
>= INT_GET(ltp
->bestcount
, ARCH_CONVERT
)) {
354 ovbcopy(&bestsp
[1], &bestsp
[0],
355 INT_GET(ltp
->bestcount
, ARCH_CONVERT
) * sizeof(bestsp
[0]));
356 INT_MOD(ltp
->bestcount
, ARCH_CONVERT
, +1);
357 xfs_dir2_leaf_log_tail(tp
, lbp
);
358 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
361 * If we're filling in a previously empty block just log it.
364 xfs_dir2_leaf_log_bests(tp
, lbp
, use_block
, use_block
);
366 INT_COPY(bestsp
[use_block
], data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
370 * Already had space in some data block.
371 * Just read that one in.
375 xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, use_block
),
376 -1, &dbp
, XFS_DATA_FORK
)) {
377 #pragma mips_frequency_hint NEVER
378 xfs_da_brelse(tp
, lbp
);
384 xfs_dir2_data_check(dp
, dbp
);
386 * Point to the biggest freespace in our data block.
388 dup
= (xfs_dir2_data_unused_t
*)
389 ((char *)data
+ INT_GET(data
->hdr
.bestfree
[0].offset
, ARCH_CONVERT
));
390 ASSERT(INT_GET(dup
->length
, ARCH_CONVERT
) >= length
);
391 needscan
= needlog
= 0;
393 * Mark the initial part of our freespace in use for the new entry.
395 xfs_dir2_data_use_free(tp
, dbp
, dup
,
396 (xfs_dir2_data_aoff_t
)((char *)dup
- (char *)data
), length
,
397 &needlog
, &needscan
);
399 * Initialize our new entry (at last).
401 dep
= (xfs_dir2_data_entry_t
*)dup
;
402 INT_SET(dep
->inumber
, ARCH_CONVERT
, args
->inumber
);
403 dep
->namelen
= args
->namelen
;
404 bcopy(args
->name
, dep
->name
, dep
->namelen
);
405 tagp
= XFS_DIR2_DATA_ENTRY_TAG_P(dep
);
406 INT_SET(*tagp
, ARCH_CONVERT
, (xfs_dir2_data_off_t
)((char *)dep
- (char *)data
));
408 * Need to scan fix up the bestfree table.
411 xfs_dir2_data_freescan(mp
, data
, &needlog
, NULL
);
413 * Need to log the data block's header.
416 xfs_dir2_data_log_header(tp
, dbp
);
417 xfs_dir2_data_log_entry(tp
, dbp
, dep
);
419 * If the bests table needs to be changed, do it.
420 * Log the change unless we've already done that.
422 if (INT_GET(bestsp
[use_block
], ARCH_CONVERT
) != INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
)) {
423 INT_COPY(bestsp
[use_block
], data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
425 xfs_dir2_leaf_log_bests(tp
, lbp
, use_block
, use_block
);
428 * Now we need to make room to insert the leaf entry.
429 * If there are no stale entries, we just insert a hole at index.
431 if (INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) == 0) {
433 * lep is still good as the index leaf entry.
435 if (index
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
))
436 ovbcopy(lep
, lep
+ 1,
437 (INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - index
) * sizeof(*lep
));
439 * Record low and high logging indices for the leaf.
442 lfloghigh
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
443 INT_MOD(leaf
->hdr
.count
, ARCH_CONVERT
, +1);
446 * There are stale entries.
447 * We will use one of them for the new entry.
448 * It's probably not at the right location, so we'll have to
449 * shift some up or down first.
453 * If we didn't compact before, we need to find the nearest
454 * stale entries before and after our insertion point.
458 * Find the first stale entry before the insertion
461 for (lowstale
= index
- 1;
463 INT_GET(leaf
->ents
[lowstale
].address
, ARCH_CONVERT
) !=
464 XFS_DIR2_NULL_DATAPTR
;
468 * Find the next stale entry at or after the insertion
469 * point, if any. Stop if we go so far that the
470 * lowstale entry would be better.
472 for (highstale
= index
;
473 highstale
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) &&
474 INT_GET(leaf
->ents
[highstale
].address
, ARCH_CONVERT
) !=
475 XFS_DIR2_NULL_DATAPTR
&&
477 index
- lowstale
- 1 >= highstale
- index
);
482 * If the low one is better, use it.
485 (highstale
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) ||
486 index
- lowstale
- 1 < highstale
- index
)) {
487 ASSERT(index
- lowstale
- 1 >= 0);
488 ASSERT(INT_GET(leaf
->ents
[lowstale
].address
, ARCH_CONVERT
) ==
489 XFS_DIR2_NULL_DATAPTR
);
491 * Copy entries up to cover the stale entry
492 * and make room for the new entry.
494 if (index
- lowstale
- 1 > 0)
495 ovbcopy(&leaf
->ents
[lowstale
+ 1],
496 &leaf
->ents
[lowstale
],
497 (index
- lowstale
- 1) * sizeof(*lep
));
498 lep
= &leaf
->ents
[index
- 1];
499 lfloglow
= MIN(lowstale
, lfloglow
);
500 lfloghigh
= MAX(index
- 1, lfloghigh
);
503 * The high one is better, so use that one.
506 ASSERT(highstale
- index
>= 0);
507 ASSERT(INT_GET(leaf
->ents
[highstale
].address
, ARCH_CONVERT
) ==
508 XFS_DIR2_NULL_DATAPTR
);
510 * Copy entries down to copver the stale entry
511 * and make room for the new entry.
513 if (highstale
- index
> 0)
514 ovbcopy(&leaf
->ents
[index
],
515 &leaf
->ents
[index
+ 1],
516 (highstale
- index
) * sizeof(*lep
));
517 lep
= &leaf
->ents
[index
];
518 lfloglow
= MIN(index
, lfloglow
);
519 lfloghigh
= MAX(highstale
, lfloghigh
);
521 INT_MOD(leaf
->hdr
.stale
, ARCH_CONVERT
, -1);
524 * Fill in the new leaf entry.
526 INT_SET(lep
->hashval
, ARCH_CONVERT
, args
->hashval
);
527 INT_SET(lep
->address
, ARCH_CONVERT
, XFS_DIR2_DB_OFF_TO_DATAPTR(mp
, use_block
, INT_GET(*tagp
, ARCH_CONVERT
)));
529 * Log the leaf fields and give up the buffers.
531 xfs_dir2_leaf_log_header(tp
, lbp
);
532 xfs_dir2_leaf_log_ents(tp
, lbp
, lfloglow
, lfloghigh
);
533 xfs_dir2_leaf_check(dp
, lbp
);
534 xfs_da_buf_done(lbp
);
535 xfs_dir2_data_check(dp
, dbp
);
536 xfs_da_buf_done(dbp
);
543 * Check the internal consistency of a leaf1 block.
544 * Pop an assert if something is wrong.
548 xfs_inode_t
*dp
, /* incore directory inode */
549 xfs_dabuf_t
*bp
) /* leaf's buffer */
551 int i
; /* leaf index */
552 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
553 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail pointer */
554 xfs_mount_t
*mp
; /* filesystem mount point */
555 int stale
; /* count of stale leaves */
559 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
);
561 * This value is not restrictive enough.
562 * Should factor in the size of the bests table as well.
563 * We can deduce a value for that from di_size.
565 ASSERT(INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) <= XFS_DIR2_MAX_LEAF_ENTS(mp
));
566 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
568 * Leaves and bests don't overlap.
570 ASSERT((char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] <=
571 (char *)XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
));
573 * Check hash value order, count stale entries.
575 for (i
= stale
= 0; i
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
); i
++) {
576 if (i
+ 1 < INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
))
577 ASSERT(INT_GET(leaf
->ents
[i
].hashval
, ARCH_CONVERT
) <=
578 INT_GET(leaf
->ents
[i
+ 1].hashval
, ARCH_CONVERT
));
579 if (INT_GET(leaf
->ents
[i
].address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
582 ASSERT(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) == stale
);
587 * Compact out any stale entries in the leaf.
588 * Log the header and changed leaf entries, if any.
591 xfs_dir2_leaf_compact(
592 xfs_da_args_t
*args
, /* operation arguments */
593 xfs_dabuf_t
*bp
) /* leaf buffer */
595 int from
; /* source leaf index */
596 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
597 int loglow
; /* first leaf entry to log */
598 int to
; /* target leaf index */
601 if (INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) == 0) {
602 #pragma mips_frequency_hint NEVER
606 * Compress out the stale entries in place.
608 for (from
= to
= 0, loglow
= -1; from
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
); from
++) {
609 if (INT_GET(leaf
->ents
[from
].address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
612 * Only actually copy the entries that are different.
617 leaf
->ents
[to
] = leaf
->ents
[from
];
622 * Update and log the header, log the leaf entries.
624 ASSERT(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) == from
- to
);
625 INT_MOD(leaf
->hdr
.count
, ARCH_CONVERT
, -(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
)));
626 INT_SET(leaf
->hdr
.stale
, ARCH_CONVERT
, 0);
627 xfs_dir2_leaf_log_header(args
->trans
, bp
);
629 xfs_dir2_leaf_log_ents(args
->trans
, bp
, loglow
, to
- 1);
633 * Compact the leaf entries, removing stale ones.
634 * Leave one stale entry behind - the one closest to our
635 * insertion index - and the caller will shift that one to our insertion
637 * Return new insertion index, where the remaining stale entry is,
638 * and leaf logging indices.
641 xfs_dir2_leaf_compact_x1(
642 xfs_dabuf_t
*bp
, /* leaf buffer */
643 int *indexp
, /* insertion index */
644 int *lowstalep
, /* out: stale entry before us */
645 int *highstalep
, /* out: stale entry after us */
646 int *lowlogp
, /* out: low log index */
647 int *highlogp
) /* out: high log index */
649 int from
; /* source copy index */
650 int highstale
; /* stale entry at/after index */
651 int index
; /* insertion index */
652 int keepstale
; /* source index of kept stale */
653 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
654 int lowstale
; /* stale entry before index */
655 int newindex
; /* new insertion index */
656 int to
; /* destination copy index */
659 ASSERT(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) > 1);
662 * Find the first stale entry before our index, if any.
664 for (lowstale
= index
- 1;
666 INT_GET(leaf
->ents
[lowstale
].address
, ARCH_CONVERT
) != XFS_DIR2_NULL_DATAPTR
;
670 * Find the first stale entry at or after our index, if any.
671 * Stop if the answer would be worse than lowstale.
673 for (highstale
= index
;
674 highstale
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) &&
675 INT_GET(leaf
->ents
[highstale
].address
, ARCH_CONVERT
) != XFS_DIR2_NULL_DATAPTR
&&
676 (lowstale
< 0 || index
- lowstale
> highstale
- index
);
680 * Pick the better of lowstale and highstale.
683 (highstale
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) ||
684 index
- lowstale
<= highstale
- index
))
685 keepstale
= lowstale
;
687 keepstale
= highstale
;
689 * Copy the entries in place, removing all the stale entries
692 for (from
= to
= 0; from
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
); from
++) {
694 * Notice the new value of index.
698 if (from
!= keepstale
&&
699 INT_GET(leaf
->ents
[from
].address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
) {
705 * Record the new keepstale value for the insertion.
707 if (from
== keepstale
)
708 lowstale
= highstale
= to
;
710 * Copy only the entries that have moved.
713 leaf
->ents
[to
] = leaf
->ents
[from
];
718 * If the insertion point was past the last entry,
719 * set the new insertion point accordingly.
725 * Adjust the leaf header values.
727 INT_MOD(leaf
->hdr
.count
, ARCH_CONVERT
, -(from
- to
));
728 INT_SET(leaf
->hdr
.stale
, ARCH_CONVERT
, 1);
730 * Remember the low/high stale value only in the "right"
733 if (lowstale
>= newindex
)
736 highstale
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
737 *highlogp
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - 1;
738 *lowstalep
= lowstale
;
739 *highstalep
= highstale
;
743 * Initialize a new leaf block, leaf1 or leafn magic accepted.
747 xfs_da_args_t
*args
, /* operation arguments */
748 xfs_dir2_db_t bno
, /* directory block number */
749 xfs_dabuf_t
**bpp
, /* out: leaf buffer */
750 int magic
) /* magic number for block */
752 xfs_dabuf_t
*bp
; /* leaf buffer */
753 xfs_inode_t
*dp
; /* incore directory inode */
754 int error
; /* error return code */
755 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
756 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
757 xfs_mount_t
*mp
; /* filesystem mount point */
758 xfs_trans_t
*tp
; /* transaction pointer */
764 ASSERT(bno
>= XFS_DIR2_LEAF_FIRSTDB(mp
) &&
765 bno
< XFS_DIR2_FREE_FIRSTDB(mp
));
767 * Get the buffer for the block.
769 error
= xfs_da_get_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, bno
), -1, &bp
,
772 #pragma mips_frequency_hint NEVER
778 * Initialize the header.
780 INT_SET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
, magic
);
781 INT_ZERO(leaf
->hdr
.info
.forw
, ARCH_CONVERT
);
782 INT_ZERO(leaf
->hdr
.info
.back
, ARCH_CONVERT
);
783 INT_ZERO(leaf
->hdr
.count
, ARCH_CONVERT
);
784 INT_ZERO(leaf
->hdr
.stale
, ARCH_CONVERT
);
785 xfs_dir2_leaf_log_header(tp
, bp
);
787 * If it's a leaf-format directory initialize the tail.
788 * In this case our caller has the real bests table to copy into
791 if (magic
== XFS_DIR2_LEAF1_MAGIC
) {
792 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
793 INT_SET(ltp
->bestcount
, ARCH_CONVERT
, 0);
794 xfs_dir2_leaf_log_tail(tp
, bp
);
801 * Log the bests entries indicated from a leaf1 block.
804 xfs_dir2_leaf_log_bests(
805 xfs_trans_t
*tp
, /* transaction pointer */
806 xfs_dabuf_t
*bp
, /* leaf buffer */
807 int first
, /* first entry to log */
808 int last
) /* last entry to log */
810 xfs_dir2_data_off_t
*firstb
; /* pointer to first entry */
811 xfs_dir2_data_off_t
*lastb
; /* pointer to last entry */
812 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
813 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
816 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
);
817 ltp
= XFS_DIR2_LEAF_TAIL_P(tp
->t_mountp
, leaf
);
818 firstb
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
) + first
;
819 lastb
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
) + last
;
820 xfs_da_log_buf(tp
, bp
, (uint
)((char *)firstb
- (char *)leaf
),
821 (uint
)((char *)lastb
- (char *)leaf
+ sizeof(*lastb
) - 1));
825 * Log the leaf entries indicated from a leaf1 or leafn block.
828 xfs_dir2_leaf_log_ents(
829 xfs_trans_t
*tp
, /* transaction pointer */
830 xfs_dabuf_t
*bp
, /* leaf buffer */
831 int first
, /* first entry to log */
832 int last
) /* last entry to log */
834 xfs_dir2_leaf_entry_t
*firstlep
; /* pointer to first entry */
835 xfs_dir2_leaf_entry_t
*lastlep
; /* pointer to last entry */
836 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
839 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
||
840 INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
841 firstlep
= &leaf
->ents
[first
];
842 lastlep
= &leaf
->ents
[last
];
843 xfs_da_log_buf(tp
, bp
, (uint
)((char *)firstlep
- (char *)leaf
),
844 (uint
)((char *)lastlep
- (char *)leaf
+ sizeof(*lastlep
) - 1));
848 * Log the header of the leaf1 or leafn block.
851 xfs_dir2_leaf_log_header(
852 xfs_trans_t
*tp
, /* transaction pointer */
853 xfs_dabuf_t
*bp
) /* leaf buffer */
855 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
858 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
||
859 INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
860 xfs_da_log_buf(tp
, bp
, (uint
)((char *)&leaf
->hdr
- (char *)leaf
),
861 (uint
)(sizeof(leaf
->hdr
) - 1));
865 * Log the tail of the leaf1 block.
868 xfs_dir2_leaf_log_tail(
869 xfs_trans_t
*tp
, /* transaction pointer */
870 xfs_dabuf_t
*bp
) /* leaf buffer */
872 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
873 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
874 xfs_mount_t
*mp
; /* filesystem mount point */
878 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAF1_MAGIC
);
879 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
880 xfs_da_log_buf(tp
, bp
, (uint
)((char *)ltp
- (char *)leaf
),
881 (uint
)(mp
->m_dirblksize
- 1));
885 * Look up the entry referred to by args in the leaf format directory.
886 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
887 * is also used by the node-format code.
890 xfs_dir2_leaf_lookup(
891 xfs_da_args_t
*args
) /* operation arguments */
893 xfs_dabuf_t
*dbp
; /* data block buffer */
894 xfs_dir2_data_entry_t
*dep
; /* data block entry */
895 xfs_inode_t
*dp
; /* incore directory inode */
896 int error
; /* error return code */
897 int index
; /* found entry index */
898 xfs_dabuf_t
*lbp
; /* leaf buffer */
899 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
900 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
901 xfs_trans_t
*tp
; /* transaction pointer */
903 xfs_dir2_trace_args("leaf_lookup", args
);
905 * Look up name in the leaf block, returning both buffers and index.
907 if (error
= xfs_dir2_leaf_lookup_int(args
, &lbp
, &index
, &dbp
)) {
908 #pragma mips_frequency_hint NEVER
913 xfs_dir2_leaf_check(dp
, lbp
);
916 * Get to the leaf entry and contained data entry address.
918 lep
= &leaf
->ents
[index
];
920 * Point to the data entry.
922 dep
= (xfs_dir2_data_entry_t
*)
924 XFS_DIR2_DATAPTR_TO_OFF(dp
->i_mount
, INT_GET(lep
->address
, ARCH_CONVERT
)));
926 * Return the found inode number.
928 args
->inumber
= INT_GET(dep
->inumber
, ARCH_CONVERT
);
929 xfs_da_brelse(tp
, dbp
);
930 xfs_da_brelse(tp
, lbp
);
931 return XFS_ERROR(EEXIST
);
935 * Look up name/hash in the leaf block.
936 * Fill in indexp with the found index, and dbpp with the data buffer.
937 * If not found dbpp will be NULL, and ENOENT comes back.
938 * lbpp will always be filled in with the leaf buffer unless there's an error.
940 STATIC
int /* error */
941 xfs_dir2_leaf_lookup_int(
942 xfs_da_args_t
*args
, /* operation arguments */
943 xfs_dabuf_t
**lbpp
, /* out: leaf buffer */
944 int *indexp
, /* out: index in leaf block */
945 xfs_dabuf_t
**dbpp
) /* out: data buffer */
947 xfs_dir2_db_t curdb
; /* current data block number */
948 xfs_dabuf_t
*dbp
; /* data buffer */
949 xfs_dir2_data_entry_t
*dep
; /* data entry */
950 xfs_inode_t
*dp
; /* incore directory inode */
951 int error
; /* error return code */
952 int index
; /* index in leaf block */
953 xfs_dabuf_t
*lbp
; /* leaf buffer */
954 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
955 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
956 xfs_mount_t
*mp
; /* filesystem mount point */
957 xfs_dir2_db_t newdb
; /* new data block number */
958 xfs_trans_t
*tp
; /* transaction pointer */
964 * Read the leaf block into the buffer.
967 xfs_da_read_buf(tp
, dp
, mp
->m_dirleafblk
, -1, &lbp
,
969 #pragma mips_frequency_hint NEVER
974 xfs_dir2_leaf_check(dp
, lbp
);
976 * Look for the first leaf entry with our hash value.
978 index
= xfs_dir2_leaf_search_hash(args
, lbp
);
980 * Loop over all the entries with the right hash value
981 * looking to match the name.
983 for (lep
= &leaf
->ents
[index
], dbp
= NULL
, curdb
= -1;
984 index
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) && INT_GET(lep
->hashval
, ARCH_CONVERT
) == args
->hashval
;
987 * Skip over stale leaf entries.
989 if (INT_GET(lep
->address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
992 * Get the new data block number.
994 newdb
= XFS_DIR2_DATAPTR_TO_DB(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
996 * If it's not the same as the old data block number,
997 * need to pitch the old one and read the new one.
999 if (newdb
!= curdb
) {
1001 xfs_da_brelse(tp
, dbp
);
1003 xfs_da_read_buf(tp
, dp
,
1004 XFS_DIR2_DB_TO_DA(mp
, newdb
), -1, &dbp
,
1006 #pragma mips_frequency_hint NEVER
1007 xfs_da_brelse(tp
, lbp
);
1010 xfs_dir2_data_check(dp
, dbp
);
1014 * Point to the data entry.
1016 dep
= (xfs_dir2_data_entry_t
*)
1017 ((char *)dbp
->data
+
1018 XFS_DIR2_DATAPTR_TO_OFF(mp
, INT_GET(lep
->address
, ARCH_CONVERT
)));
1020 * If it matches then return it.
1022 if (dep
->namelen
== args
->namelen
&&
1023 dep
->name
[0] == args
->name
[0] &&
1024 bcmp(dep
->name
, args
->name
, args
->namelen
) == 0) {
1031 * No match found, return ENOENT.
1033 ASSERT(args
->oknoent
);
1035 xfs_da_brelse(tp
, dbp
);
1036 xfs_da_brelse(tp
, lbp
);
1037 return XFS_ERROR(ENOENT
);
1041 * Remove an entry from a leaf format directory.
1044 xfs_dir2_leaf_removename(
1045 xfs_da_args_t
*args
) /* operation arguments */
1047 xfs_dir2_data_off_t
*bestsp
; /* leaf block best freespace */
1048 xfs_dir2_data_t
*data
; /* data block structure */
1049 xfs_dir2_db_t db
; /* data block number */
1050 xfs_dabuf_t
*dbp
; /* data block buffer */
1051 xfs_dir2_data_entry_t
*dep
; /* data entry structure */
1052 xfs_inode_t
*dp
; /* incore directory inode */
1053 int error
; /* error return code */
1054 xfs_dir2_db_t i
; /* temporary data block # */
1055 int index
; /* index into leaf entries */
1056 xfs_dabuf_t
*lbp
; /* leaf buffer */
1057 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1058 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
1059 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
1060 xfs_mount_t
*mp
; /* filesystem mount point */
1061 int needlog
; /* need to log data header */
1062 int needscan
; /* need to rescan data frees */
1063 xfs_dir2_data_off_t oldbest
; /* old value of best free */
1064 xfs_trans_t
*tp
; /* transaction pointer */
1066 xfs_dir2_trace_args("leaf_removename", args
);
1068 * Lookup the leaf entry, get the leaf and data blocks read in.
1070 if (error
= xfs_dir2_leaf_lookup_int(args
, &lbp
, &index
, &dbp
)) {
1071 #pragma mips_frequency_hint NEVER
1079 xfs_dir2_data_check(dp
, dbp
);
1081 * Point to the leaf entry, use that to point to the data entry.
1083 lep
= &leaf
->ents
[index
];
1084 db
= XFS_DIR2_DATAPTR_TO_DB(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
1085 dep
= (xfs_dir2_data_entry_t
*)
1086 ((char *)data
+ XFS_DIR2_DATAPTR_TO_OFF(mp
, INT_GET(lep
->address
, ARCH_CONVERT
)));
1087 needscan
= needlog
= 0;
1088 oldbest
= INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
1089 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
1090 bestsp
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
);
1091 ASSERT(INT_GET(bestsp
[db
], ARCH_CONVERT
) == oldbest
);
1093 * Mark the former data entry unused.
1095 xfs_dir2_data_make_free(tp
, dbp
,
1096 (xfs_dir2_data_aoff_t
)((char *)dep
- (char *)data
),
1097 XFS_DIR2_DATA_ENTSIZE(dep
->namelen
), &needlog
, &needscan
);
1099 * We just mark the leaf entry stale by putting a null in it.
1101 INT_MOD(leaf
->hdr
.stale
, ARCH_CONVERT
, +1);
1102 xfs_dir2_leaf_log_header(tp
, lbp
);
1103 INT_SET(lep
->address
, ARCH_CONVERT
, XFS_DIR2_NULL_DATAPTR
);
1104 xfs_dir2_leaf_log_ents(tp
, lbp
, index
, index
);
1106 * Scan the freespace in the data block again if necessary,
1107 * log the data block header if necessary.
1110 xfs_dir2_data_freescan(mp
, data
, &needlog
, NULL
);
1112 xfs_dir2_data_log_header(tp
, dbp
);
1114 * If the longest freespace in the data block has changed,
1115 * put the new value in the bests table and log that.
1117 if (INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
) != oldbest
) {
1118 INT_COPY(bestsp
[db
], data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
1119 xfs_dir2_leaf_log_bests(tp
, lbp
, db
, db
);
1121 xfs_dir2_data_check(dp
, dbp
);
1123 * If the data block is now empty then get rid of the data block.
1125 if (INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
) ==
1126 mp
->m_dirblksize
- (uint
)sizeof(data
->hdr
)) {
1127 #pragma mips_frequency_hint NEVER
1128 ASSERT(db
!= mp
->m_dirdatablk
);
1129 if (error
= xfs_dir2_shrink_inode(args
, db
, dbp
)) {
1131 * Nope, can't get rid of it because it caused
1132 * allocation of a bmap btree block to do so.
1133 * Just go on, returning success, leaving the
1134 * empty block in place.
1136 if (error
== ENOSPC
&& args
->total
== 0) {
1137 xfs_da_buf_done(dbp
);
1140 xfs_dir2_leaf_check(dp
, lbp
);
1141 xfs_da_buf_done(lbp
);
1146 * If this is the last data block then compact the
1147 * bests table by getting rid of entries.
1149 if (db
== INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1) {
1151 * Look for the last active entry (i).
1153 for (i
= db
- 1; i
> 0; i
--) {
1154 if (INT_GET(bestsp
[i
], ARCH_CONVERT
) != NULLDATAOFF
)
1158 * Copy the table down so inactive entries at the
1161 ovbcopy(bestsp
, &bestsp
[db
- i
],
1162 (INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - (db
- i
)) * sizeof(*bestsp
));
1163 INT_MOD(ltp
->bestcount
, ARCH_CONVERT
, -(db
- i
));
1164 xfs_dir2_leaf_log_tail(tp
, lbp
);
1165 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
1167 INT_SET(bestsp
[db
], ARCH_CONVERT
, NULLDATAOFF
);
1170 * If the data block was not the first one, drop it.
1172 else if (db
!= mp
->m_dirdatablk
&& dbp
!= NULL
) {
1173 xfs_da_buf_done(dbp
);
1176 xfs_dir2_leaf_check(dp
, lbp
);
1178 * See if we can convert to block form.
1180 return xfs_dir2_leaf_to_block(args
, lbp
, dbp
);
1184 * Replace the inode number in a leaf format directory entry.
1187 xfs_dir2_leaf_replace(
1188 xfs_da_args_t
*args
) /* operation arguments */
1190 xfs_dabuf_t
*dbp
; /* data block buffer */
1191 xfs_dir2_data_entry_t
*dep
; /* data block entry */
1192 xfs_inode_t
*dp
; /* incore directory inode */
1193 int error
; /* error return code */
1194 int index
; /* index of leaf entry */
1195 xfs_dabuf_t
*lbp
; /* leaf buffer */
1196 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1197 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
1198 xfs_trans_t
*tp
; /* transaction pointer */
1200 xfs_dir2_trace_args("leaf_replace", args
);
1202 * Look up the entry.
1204 if (error
= xfs_dir2_leaf_lookup_int(args
, &lbp
, &index
, &dbp
)) {
1205 #pragma mips_frequency_hint NEVER
1211 * Point to the leaf entry, get data address from it.
1213 lep
= &leaf
->ents
[index
];
1215 * Point to the data entry.
1217 dep
= (xfs_dir2_data_entry_t
*)
1218 ((char *)dbp
->data
+
1219 XFS_DIR2_DATAPTR_TO_OFF(dp
->i_mount
, INT_GET(lep
->address
, ARCH_CONVERT
)));
1220 ASSERT(args
->inumber
!= INT_GET(dep
->inumber
, ARCH_CONVERT
));
1222 * Put the new inode number in, log it.
1224 INT_SET(dep
->inumber
, ARCH_CONVERT
, args
->inumber
);
1226 xfs_dir2_data_log_entry(tp
, dbp
, dep
);
1227 xfs_da_buf_done(dbp
);
1228 xfs_dir2_leaf_check(dp
, lbp
);
1229 xfs_da_brelse(tp
, lbp
);
1234 * Return index in the leaf block (lbp) which is either the first
1235 * one with this hash value, or if there are none, the insert point
1236 * for that hash value.
1238 int /* index value */
1239 xfs_dir2_leaf_search_hash(
1240 xfs_da_args_t
*args
, /* operation arguments */
1241 xfs_dabuf_t
*lbp
) /* leaf buffer */
1243 xfs_dahash_t hash
; /* hash from this entry */
1244 xfs_dahash_t hashwant
; /* hash value looking for */
1245 int high
; /* high leaf index */
1246 int low
; /* low leaf index */
1247 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1248 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
1249 int mid
; /* current leaf index */
1253 if (INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) == 0)
1257 * Note, the table cannot be empty, so we have to go through the loop.
1258 * Binary search the leaf entries looking for our hash value.
1260 for (lep
= leaf
->ents
, low
= 0, high
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - 1,
1261 hashwant
= args
->hashval
;
1263 mid
= (low
+ high
) >> 1;
1264 if ((hash
= INT_GET(lep
[mid
].hashval
, ARCH_CONVERT
)) == hashwant
)
1266 if (hash
< hashwant
)
1272 * Found one, back up through all the equal hash values.
1274 if (hash
== hashwant
) {
1275 while (mid
> 0 && INT_GET(lep
[mid
- 1].hashval
, ARCH_CONVERT
) == hashwant
) {
1276 #pragma mips_frequency_hint NEVER
1281 * Need to point to an entry higher than ours.
1283 else if (hash
< hashwant
)
1289 * Trim off a trailing data block. We know it's empty since the leaf
1290 * freespace table says so.
1293 xfs_dir2_leaf_trim_data(
1294 xfs_da_args_t
*args
, /* operation arguments */
1295 xfs_dabuf_t
*lbp
, /* leaf buffer */
1296 xfs_dir2_db_t db
) /* data block number */
1298 xfs_dir2_data_off_t
*bestsp
; /* leaf bests table */
1300 xfs_dir2_data_t
*data
; /* data block structure */
1302 xfs_dabuf_t
*dbp
; /* data block buffer */
1303 xfs_inode_t
*dp
; /* incore directory inode */
1304 int error
; /* error return value */
1305 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1306 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
1307 xfs_mount_t
*mp
; /* filesystem mount point */
1308 xfs_trans_t
*tp
; /* transaction pointer */
1314 * Read the offending data block. We need its buffer.
1316 if (error
= xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, db
), -1, &dbp
,
1318 #pragma mips_frequency_hint NEVER
1323 ASSERT(INT_GET(data
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_DATA_MAGIC
);
1325 /* this seems to be an error
1326 * data is only valid if DEBUG is defined?
1331 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
1332 ASSERT(INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
) ==
1333 mp
->m_dirblksize
- (uint
)sizeof(data
->hdr
));
1334 ASSERT(db
== INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
1336 * Get rid of the data block.
1338 if (error
= xfs_dir2_shrink_inode(args
, db
, dbp
)) {
1339 #pragma mips_frequency_hint NEVER
1340 ASSERT(error
!= ENOSPC
);
1341 xfs_da_brelse(tp
, dbp
);
1345 * Eliminate the last bests entry from the table.
1347 bestsp
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
);
1348 INT_MOD(ltp
->bestcount
, ARCH_CONVERT
, -1);
1349 ovbcopy(&bestsp
[0], &bestsp
[1], INT_GET(ltp
->bestcount
, ARCH_CONVERT
) * sizeof(*bestsp
));
1350 xfs_dir2_leaf_log_tail(tp
, lbp
);
1351 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
1356 * Convert node form directory to leaf form directory.
1357 * The root of the node form dir needs to already be a LEAFN block.
1358 * Just return if we can't do anything.
1361 xfs_dir2_node_to_leaf(
1362 xfs_da_state_t
*state
) /* directory operation state */
1364 xfs_da_args_t
*args
; /* operation arguments */
1365 xfs_inode_t
*dp
; /* incore directory inode */
1366 int error
; /* error return code */
1367 xfs_dabuf_t
*fbp
; /* buffer for freespace block */
1368 xfs_fileoff_t fo
; /* freespace file offset */
1369 xfs_dir2_free_t
*free
; /* freespace structure */
1370 xfs_dabuf_t
*lbp
; /* buffer for leaf block */
1371 xfs_dir2_leaf_tail_t
*ltp
; /* tail of leaf structure */
1372 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1373 xfs_mount_t
*mp
; /* filesystem mount point */
1374 int rval
; /* successful free trim? */
1375 xfs_trans_t
*tp
; /* transaction pointer */
1378 * There's more than a leaf level in the btree, so there must
1379 * be multiple leafn blocks. Give up.
1381 if (state
->path
.active
> 1)
1384 xfs_dir2_trace_args("node_to_leaf", args
);
1389 * Get the last offset in the file.
1391 if (error
= xfs_bmap_last_offset(tp
, dp
, &fo
, XFS_DATA_FORK
)) {
1392 #pragma mips_frequency_hint NEVER
1395 fo
-= mp
->m_dirblkfsbs
;
1397 * If there are freespace blocks other than the first one,
1398 * take this opportunity to remove trailing empty freespace blocks
1399 * that may have been left behind during no-space-reservation
1402 while (fo
> mp
->m_dirfreeblk
) {
1403 if (error
= xfs_dir2_node_trim_free(args
, fo
, &rval
)) {
1404 #pragma mips_frequency_hint NEVER
1408 fo
-= mp
->m_dirblkfsbs
;
1413 * Now find the block just before the freespace block.
1415 if (error
= xfs_bmap_last_before(tp
, dp
, &fo
, XFS_DATA_FORK
)) {
1416 #pragma mips_frequency_hint NEVER
1420 * If it's not the single leaf block, give up.
1422 if (XFS_FSB_TO_B(mp
, fo
) > XFS_DIR2_LEAF_OFFSET
+ mp
->m_dirblksize
)
1424 lbp
= state
->path
.blk
[0].bp
;
1426 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
1428 * Read the freespace block.
1430 if (error
= xfs_da_read_buf(tp
, dp
, mp
->m_dirfreeblk
, -1, &fbp
,
1432 #pragma mips_frequency_hint NEVER
1436 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
1437 ASSERT(INT_ISZERO(free
->hdr
.firstdb
, ARCH_CONVERT
));
1439 * Now see if the leafn and free data will fit in a leaf1.
1440 * If not, release the buffer and give up.
1442 if ((uint
)sizeof(leaf
->hdr
) +
1443 (INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
)) * (uint
)sizeof(leaf
->ents
[0]) +
1444 INT_GET(free
->hdr
.nvalid
, ARCH_CONVERT
) * (uint
)sizeof(leaf
->bests
[0]) +
1445 (uint
)sizeof(leaf
->tail
) >
1447 xfs_da_brelse(tp
, fbp
);
1451 * If the leaf has any stale entries in it, compress them out.
1452 * The compact routine will log the header.
1454 if (INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
))
1455 xfs_dir2_leaf_compact(args
, lbp
);
1457 xfs_dir2_leaf_log_header(tp
, lbp
);
1458 INT_SET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
, XFS_DIR2_LEAF1_MAGIC
);
1460 * Set up the leaf tail from the freespace block.
1462 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
1463 INT_COPY(ltp
->bestcount
, free
->hdr
.nvalid
, ARCH_CONVERT
);
1465 * Set up the leaf bests table.
1467 bcopy(free
->bests
, XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
),
1468 INT_GET(ltp
->bestcount
, ARCH_CONVERT
) * sizeof(leaf
->bests
[0]));
1469 xfs_dir2_leaf_log_bests(tp
, lbp
, 0, INT_GET(ltp
->bestcount
, ARCH_CONVERT
) - 1);
1470 xfs_dir2_leaf_log_tail(tp
, lbp
);
1471 xfs_dir2_leaf_check(dp
, lbp
);
1473 * Get rid of the freespace block.
1475 error
= xfs_dir2_shrink_inode(args
, XFS_DIR2_FREE_FIRSTDB(mp
), fbp
);
1477 #pragma mips_frequency_hint NEVER
1479 * This can't fail here because it can only happen when
1480 * punching out the middle of an extent, and this is an
1483 ASSERT(error
!= ENOSPC
);
1488 * Now see if we can convert the single-leaf directory
1489 * down to a block form directory.
1490 * This routine always kills the dabuf for the leaf, so
1491 * eliminate it from the path.
1493 error
= xfs_dir2_leaf_to_block(args
, lbp
, NULL
);
1494 state
->path
.blk
[0].bp
= NULL
;