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/
38 * Routines to implement leaf blocks of directories as Btrees of hashed names.
42 * Validate a given inode number.
45 xfs_dir_ino_validate(xfs_mount_t
*mp
, xfs_ino_t ino
)
47 xfs_agblock_t agblkno
;
53 agno
= XFS_INO_TO_AGNO(mp
, ino
);
54 agblkno
= XFS_INO_TO_AGBNO(mp
, ino
);
55 ioff
= XFS_INO_TO_OFFSET(mp
, ino
);
56 agino
= XFS_OFFBNO_TO_AGINO(mp
, agblkno
, ioff
);
58 agno
< mp
->m_sb
.sb_agcount
&&
59 agblkno
< mp
->m_sb
.sb_agblocks
&&
61 ioff
< (1 << mp
->m_sb
.sb_inopblog
) &&
62 XFS_AGINO_TO_INO(mp
, agno
, agino
) == ino
;
63 if (XFS_TEST_ERROR(!ino_ok
, mp
, XFS_ERRTAG_DIR_INO_VALIDATE
,
64 XFS_RANDOM_DIR_INO_VALIDATE
)) {
65 xfs_fs_cmn_err(CE_WARN
, mp
, "Invalid inode number 0x%Lx\n",
66 (unsigned long long) ino
);
67 return XFS_ERROR(EFSCORRUPTED
);
73 * Create the initial contents of a shortform directory.
76 xfs_dir_shortform_create(xfs_da_args_t
*args
, xfs_ino_t parent
)
78 xfs_dir_sf_hdr_t
*hdr
;
83 ASSERT(dp
->i_d
.di_size
== 0);
84 if (dp
->i_d
.di_format
== XFS_DINODE_FMT_EXTENTS
) {
85 dp
->i_df
.if_flags
&= ~XFS_IFEXTENTS
; /* just in case */
86 dp
->i_d
.di_format
= XFS_DINODE_FMT_LOCAL
;
87 xfs_trans_log_inode(args
->trans
, dp
, XFS_ILOG_CORE
);
88 dp
->i_df
.if_flags
|= XFS_IFINLINE
;
90 ASSERT(dp
->i_df
.if_flags
& XFS_IFINLINE
);
91 ASSERT(dp
->i_df
.if_bytes
== 0);
92 xfs_idata_realloc(dp
, sizeof(*hdr
), XFS_DATA_FORK
);
93 hdr
= (xfs_dir_sf_hdr_t
*)dp
->i_df
.if_u1
.if_data
;
94 XFS_DIR_SF_PUT_DIRINO_ARCH(&parent
, &hdr
->parent
, ARCH_CONVERT
);
96 INT_ZERO(hdr
->count
, ARCH_CONVERT
);
97 dp
->i_d
.di_size
= sizeof(*hdr
);
98 xfs_trans_log_inode(args
->trans
, dp
, XFS_ILOG_CORE
| XFS_ILOG_DDATA
);
103 * Add a name to the shortform directory structure.
104 * Overflow from the inode has already been checked for.
107 xfs_dir_shortform_addname(xfs_da_args_t
*args
)
109 xfs_dir_shortform_t
*sf
;
110 xfs_dir_sf_entry_t
*sfe
;
115 ASSERT(dp
->i_df
.if_flags
& XFS_IFINLINE
);
117 * Catch the case where the conversion from shortform to leaf
118 * failed part way through.
120 if (dp
->i_d
.di_size
< sizeof(xfs_dir_sf_hdr_t
)) {
121 ASSERT(XFS_FORCED_SHUTDOWN(dp
->i_mount
));
122 return XFS_ERROR(EIO
);
124 ASSERT(dp
->i_df
.if_bytes
== dp
->i_d
.di_size
);
125 ASSERT(dp
->i_df
.if_u1
.if_data
!= NULL
);
126 sf
= (xfs_dir_shortform_t
*)dp
->i_df
.if_u1
.if_data
;
128 for (i
= INT_GET(sf
->hdr
.count
, ARCH_CONVERT
)-1; i
>= 0; i
--) {
129 if (sfe
->namelen
== args
->namelen
&&
130 args
->name
[0] == sfe
->name
[0] &&
131 bcmp(args
->name
, sfe
->name
, args
->namelen
) == 0)
132 return(XFS_ERROR(EEXIST
));
133 sfe
= XFS_DIR_SF_NEXTENTRY(sfe
);
136 offset
= (int)((char *)sfe
- (char *)sf
);
137 size
= XFS_DIR_SF_ENTSIZE_BYNAME(args
->namelen
);
138 xfs_idata_realloc(dp
, size
, XFS_DATA_FORK
);
139 sf
= (xfs_dir_shortform_t
*)dp
->i_df
.if_u1
.if_data
;
140 sfe
= (xfs_dir_sf_entry_t
*)((char *)sf
+ offset
);
142 XFS_DIR_SF_PUT_DIRINO_ARCH(&args
->inumber
, &sfe
->inumber
, ARCH_CONVERT
);
143 sfe
->namelen
= args
->namelen
;
144 bcopy(args
->name
, sfe
->name
, sfe
->namelen
);
145 INT_MOD(sf
->hdr
.count
, ARCH_CONVERT
, +1);
147 dp
->i_d
.di_size
+= size
;
148 xfs_trans_log_inode(args
->trans
, dp
, XFS_ILOG_CORE
| XFS_ILOG_DDATA
);
154 * Remove a name from the shortform directory structure.
157 xfs_dir_shortform_removename(xfs_da_args_t
*args
)
159 xfs_dir_shortform_t
*sf
;
160 xfs_dir_sf_entry_t
*sfe
;
161 int base
, size
= 0, i
;
165 ASSERT(dp
->i_df
.if_flags
& XFS_IFINLINE
);
167 * Catch the case where the conversion from shortform to leaf
168 * failed part way through.
170 if (dp
->i_d
.di_size
< sizeof(xfs_dir_sf_hdr_t
)) {
171 ASSERT(XFS_FORCED_SHUTDOWN(dp
->i_mount
));
172 return XFS_ERROR(EIO
);
174 ASSERT(dp
->i_df
.if_bytes
== dp
->i_d
.di_size
);
175 ASSERT(dp
->i_df
.if_u1
.if_data
!= NULL
);
176 base
= sizeof(xfs_dir_sf_hdr_t
);
177 sf
= (xfs_dir_shortform_t
*)dp
->i_df
.if_u1
.if_data
;
179 for (i
= INT_GET(sf
->hdr
.count
, ARCH_CONVERT
)-1; i
>= 0; i
--) {
180 size
= XFS_DIR_SF_ENTSIZE_BYENTRY(sfe
);
181 if (sfe
->namelen
== args
->namelen
&&
182 sfe
->name
[0] == args
->name
[0] &&
183 bcmp(sfe
->name
, args
->name
, args
->namelen
) == 0)
186 sfe
= XFS_DIR_SF_NEXTENTRY(sfe
);
189 ASSERT(args
->oknoent
);
190 return(XFS_ERROR(ENOENT
));
193 if ((base
+ size
) != dp
->i_d
.di_size
) {
194 ovbcopy(&((char *)sf
)[base
+size
], &((char *)sf
)[base
],
195 dp
->i_d
.di_size
- (base
+size
));
197 INT_MOD(sf
->hdr
.count
, ARCH_CONVERT
, -1);
199 xfs_idata_realloc(dp
, -size
, XFS_DATA_FORK
);
200 dp
->i_d
.di_size
-= size
;
201 xfs_trans_log_inode(args
->trans
, dp
, XFS_ILOG_CORE
| XFS_ILOG_DDATA
);
207 * Look up a name in a shortform directory structure.
210 xfs_dir_shortform_lookup(xfs_da_args_t
*args
)
212 xfs_dir_shortform_t
*sf
;
213 xfs_dir_sf_entry_t
*sfe
;
218 ASSERT(dp
->i_df
.if_flags
& XFS_IFINLINE
);
220 * Catch the case where the conversion from shortform to leaf
221 * failed part way through.
223 if (dp
->i_d
.di_size
< sizeof(xfs_dir_sf_hdr_t
)) {
224 ASSERT(XFS_FORCED_SHUTDOWN(dp
->i_mount
));
225 return XFS_ERROR(EIO
);
227 ASSERT(dp
->i_df
.if_bytes
== dp
->i_d
.di_size
);
228 ASSERT(dp
->i_df
.if_u1
.if_data
!= NULL
);
229 sf
= (xfs_dir_shortform_t
*)dp
->i_df
.if_u1
.if_data
;
230 if (args
->namelen
== 2 &&
231 args
->name
[0] == '.' && args
->name
[1] == '.') {
232 XFS_DIR_SF_GET_DIRINO_ARCH(&sf
->hdr
.parent
, &args
->inumber
, ARCH_CONVERT
);
233 return(XFS_ERROR(EEXIST
));
235 if (args
->namelen
== 1 && args
->name
[0] == '.') {
236 args
->inumber
= dp
->i_ino
;
237 return(XFS_ERROR(EEXIST
));
240 for (i
= INT_GET(sf
->hdr
.count
, ARCH_CONVERT
)-1; i
>= 0; i
--) {
241 if (sfe
->namelen
== args
->namelen
&&
242 sfe
->name
[0] == args
->name
[0] &&
243 bcmp(args
->name
, sfe
->name
, args
->namelen
) == 0) {
244 XFS_DIR_SF_GET_DIRINO_ARCH(&sfe
->inumber
, &args
->inumber
, ARCH_CONVERT
);
245 return(XFS_ERROR(EEXIST
));
247 sfe
= XFS_DIR_SF_NEXTENTRY(sfe
);
249 ASSERT(args
->oknoent
);
250 return(XFS_ERROR(ENOENT
));
254 * Convert from using the shortform to the leaf.
257 xfs_dir_shortform_to_leaf(xfs_da_args_t
*iargs
)
260 xfs_dir_shortform_t
*sf
;
261 xfs_dir_sf_entry_t
*sfe
;
271 * Catch the case where the conversion from shortform to leaf
272 * failed part way through.
274 if (dp
->i_d
.di_size
< sizeof(xfs_dir_sf_hdr_t
)) {
275 ASSERT(XFS_FORCED_SHUTDOWN(dp
->i_mount
));
276 return XFS_ERROR(EIO
);
278 ASSERT(dp
->i_df
.if_bytes
== dp
->i_d
.di_size
);
279 ASSERT(dp
->i_df
.if_u1
.if_data
!= NULL
);
280 size
= dp
->i_df
.if_bytes
;
281 tmpbuffer
= kmem_alloc(size
, KM_SLEEP
);
282 ASSERT(tmpbuffer
!= NULL
);
284 bcopy(dp
->i_df
.if_u1
.if_data
, tmpbuffer
, size
);
286 sf
= (xfs_dir_shortform_t
*)tmpbuffer
;
287 XFS_DIR_SF_GET_DIRINO_ARCH(&sf
->hdr
.parent
, &inumber
, ARCH_CONVERT
);
289 xfs_idata_realloc(dp
, -size
, XFS_DATA_FORK
);
291 xfs_trans_log_inode(iargs
->trans
, dp
, XFS_ILOG_CORE
);
292 retval
= xfs_da_grow_inode(iargs
, &blkno
);
297 retval
= xfs_dir_leaf_create(iargs
, blkno
, &bp
);
304 args
.hashval
= xfs_dir_hash_dot
;
305 args
.inumber
= dp
->i_ino
;
307 args
.firstblock
= iargs
->firstblock
;
308 args
.flist
= iargs
->flist
;
309 args
.total
= iargs
->total
;
310 args
.whichfork
= XFS_DATA_FORK
;
311 args
.trans
= iargs
->trans
;
313 args
.addname
= args
.oknoent
= 1;
314 retval
= xfs_dir_leaf_addname(&args
);
320 args
.hashval
= xfs_dir_hash_dotdot
;
321 args
.inumber
= inumber
;
322 retval
= xfs_dir_leaf_addname(&args
);
327 for (i
= 0; i
< INT_GET(sf
->hdr
.count
, ARCH_CONVERT
); i
++) {
328 args
.name
= (char *)(sfe
->name
);
329 args
.namelen
= sfe
->namelen
;
330 args
.hashval
= xfs_da_hashname((char *)(sfe
->name
),
332 XFS_DIR_SF_GET_DIRINO_ARCH(&sfe
->inumber
, &args
.inumber
, ARCH_CONVERT
);
333 retval
= xfs_dir_leaf_addname(&args
);
336 sfe
= XFS_DIR_SF_NEXTENTRY(sfe
);
341 kmem_free(tmpbuffer
, size
);
346 * Look up a name in a shortform directory structure, replace the inode number.
349 xfs_dir_shortform_replace(xfs_da_args_t
*args
)
351 xfs_dir_shortform_t
*sf
;
352 xfs_dir_sf_entry_t
*sfe
;
357 ASSERT(dp
->i_df
.if_flags
& XFS_IFINLINE
);
359 * Catch the case where the conversion from shortform to leaf
360 * failed part way through.
362 if (dp
->i_d
.di_size
< sizeof(xfs_dir_sf_hdr_t
)) {
363 ASSERT(XFS_FORCED_SHUTDOWN(dp
->i_mount
));
364 return XFS_ERROR(EIO
);
366 ASSERT(dp
->i_df
.if_bytes
== dp
->i_d
.di_size
);
367 ASSERT(dp
->i_df
.if_u1
.if_data
!= NULL
);
368 sf
= (xfs_dir_shortform_t
*)dp
->i_df
.if_u1
.if_data
;
369 if (args
->namelen
== 2 &&
370 args
->name
[0] == '.' && args
->name
[1] == '.') {
371 /* XXX - replace assert? */
372 XFS_DIR_SF_PUT_DIRINO_ARCH(&args
->inumber
, &sf
->hdr
.parent
, ARCH_CONVERT
);
373 xfs_trans_log_inode(args
->trans
, dp
, XFS_ILOG_DDATA
);
376 ASSERT(args
->namelen
!= 1 || args
->name
[0] != '.');
378 for (i
= INT_GET(sf
->hdr
.count
, ARCH_CONVERT
)-1; i
>= 0; i
--) {
379 if (sfe
->namelen
== args
->namelen
&&
380 sfe
->name
[0] == args
->name
[0] &&
381 bcmp(args
->name
, sfe
->name
, args
->namelen
) == 0) {
382 ASSERT(bcmp((char *)&args
->inumber
,
383 (char *)&sfe
->inumber
, sizeof(xfs_ino_t
)));
384 XFS_DIR_SF_PUT_DIRINO_ARCH(&args
->inumber
, &sfe
->inumber
, ARCH_CONVERT
);
385 xfs_trans_log_inode(args
->trans
, dp
, XFS_ILOG_DDATA
);
388 sfe
= XFS_DIR_SF_NEXTENTRY(sfe
);
390 ASSERT(args
->oknoent
);
391 return(XFS_ERROR(ENOENT
));
395 * Convert a leaf directory to shortform structure
398 xfs_dir_leaf_to_shortform(xfs_da_args_t
*iargs
)
400 xfs_dir_leafblock_t
*leaf
;
401 xfs_dir_leaf_hdr_t
*hdr
;
402 xfs_dir_leaf_entry_t
*entry
;
403 xfs_dir_leaf_name_t
*namest
;
412 tmpbuffer
= kmem_alloc(XFS_LBSIZE(dp
->i_mount
), KM_SLEEP
);
413 ASSERT(tmpbuffer
!= NULL
);
415 retval
= xfs_da_read_buf(iargs
->trans
, iargs
->dp
, 0, -1, &bp
,
420 bcopy(bp
->data
, tmpbuffer
, XFS_LBSIZE(dp
->i_mount
));
421 leaf
= (xfs_dir_leafblock_t
*)tmpbuffer
;
422 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
423 bzero(bp
->data
, XFS_LBSIZE(dp
->i_mount
));
426 * Find and special case the parent inode number
429 entry
= &leaf
->entries
[0];
430 for (i
= INT_GET(hdr
->count
, ARCH_CONVERT
)-1; i
>= 0; entry
++, i
--) {
431 namest
= XFS_DIR_LEAF_NAMESTRUCT(leaf
, INT_GET(entry
->nameidx
, ARCH_CONVERT
));
432 if ((entry
->namelen
== 2) &&
433 (namest
->name
[0] == '.') &&
434 (namest
->name
[1] == '.')) {
435 XFS_DIR_SF_GET_DIRINO_ARCH(&namest
->inumber
, &parent
, ARCH_CONVERT
);
436 INT_ZERO(entry
->nameidx
, ARCH_CONVERT
);
437 } else if ((entry
->namelen
== 1) && (namest
->name
[0] == '.')) {
438 INT_ZERO(entry
->nameidx
, ARCH_CONVERT
);
441 retval
= xfs_da_shrink_inode(iargs
, 0, bp
);
444 retval
= xfs_dir_shortform_create(iargs
, parent
);
449 * Copy the rest of the filenames
451 entry
= &leaf
->entries
[0];
453 args
.firstblock
= iargs
->firstblock
;
454 args
.flist
= iargs
->flist
;
455 args
.total
= iargs
->total
;
456 args
.whichfork
= XFS_DATA_FORK
;
457 args
.trans
= iargs
->trans
;
459 args
.addname
= args
.oknoent
= 1;
460 for (i
= 0; i
< INT_GET(hdr
->count
, ARCH_CONVERT
); entry
++, i
++) {
461 if (INT_ISZERO(entry
->nameidx
, ARCH_CONVERT
))
463 namest
= XFS_DIR_LEAF_NAMESTRUCT(leaf
, INT_GET(entry
->nameidx
, ARCH_CONVERT
));
464 args
.name
= (char *)(namest
->name
);
465 args
.namelen
= entry
->namelen
;
466 args
.hashval
= INT_GET(entry
->hashval
, ARCH_CONVERT
);
467 XFS_DIR_SF_GET_DIRINO_ARCH(&namest
->inumber
, &args
.inumber
, ARCH_CONVERT
);
468 xfs_dir_shortform_addname(&args
);
472 kmem_free(tmpbuffer
, XFS_LBSIZE(dp
->i_mount
));
477 * Convert from using a single leaf to a root node and a leaf.
480 xfs_dir_leaf_to_node(xfs_da_args_t
*args
)
482 xfs_dir_leafblock_t
*leaf
;
483 xfs_da_intnode_t
*node
;
485 xfs_dabuf_t
*bp1
, *bp2
;
490 retval
= xfs_da_grow_inode(args
, &blkno
);
494 retval
= xfs_da_read_buf(args
->trans
, args
->dp
, 0, -1, &bp1
,
499 retval
= xfs_da_get_buf(args
->trans
, args
->dp
, 1, -1, &bp2
,
502 xfs_da_buf_done(bp1
);
506 bcopy(bp1
->data
, bp2
->data
, XFS_LBSIZE(dp
->i_mount
));
507 xfs_da_buf_done(bp1
);
508 xfs_da_log_buf(args
->trans
, bp2
, 0, XFS_LBSIZE(dp
->i_mount
) - 1);
511 * Set up the new root node.
513 retval
= xfs_da_node_create(args
, 0, 1, &bp1
, XFS_DATA_FORK
);
515 xfs_da_buf_done(bp2
);
520 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
521 INT_SET(node
->btree
[0].hashval
, ARCH_CONVERT
, INT_GET(leaf
->entries
[ INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
));
522 xfs_da_buf_done(bp2
);
523 INT_SET(node
->btree
[0].before
, ARCH_CONVERT
, blkno
);
524 INT_SET(node
->hdr
.count
, ARCH_CONVERT
, 1);
525 xfs_da_log_buf(args
->trans
, bp1
,
526 XFS_DA_LOGRANGE(node
, &node
->btree
[0], sizeof(node
->btree
[0])));
527 xfs_da_buf_done(bp1
);
533 /*========================================================================
534 * Routines used for growing the Btree.
535 *========================================================================*/
538 * Create the initial contents of a leaf directory
539 * or a leaf in a node directory.
542 xfs_dir_leaf_create(xfs_da_args_t
*args
, xfs_dablk_t blkno
, xfs_dabuf_t
**bpp
)
544 xfs_dir_leafblock_t
*leaf
;
545 xfs_dir_leaf_hdr_t
*hdr
;
552 retval
= xfs_da_get_buf(args
->trans
, dp
, blkno
, -1, &bp
, XFS_DATA_FORK
);
557 bzero((char *)leaf
, XFS_LBSIZE(dp
->i_mount
));
559 INT_SET(hdr
->info
.magic
, ARCH_CONVERT
, XFS_DIR_LEAF_MAGIC
);
560 INT_SET(hdr
->firstused
, ARCH_CONVERT
, XFS_LBSIZE(dp
->i_mount
));
561 if (INT_ISZERO(hdr
->firstused
, ARCH_CONVERT
))
562 INT_SET(hdr
->firstused
, ARCH_CONVERT
, XFS_LBSIZE(dp
->i_mount
) - 1);
563 INT_SET(hdr
->freemap
[0].base
, ARCH_CONVERT
, sizeof(xfs_dir_leaf_hdr_t
));
564 INT_SET(hdr
->freemap
[0].size
, ARCH_CONVERT
, INT_GET(hdr
->firstused
, ARCH_CONVERT
) - INT_GET(hdr
->freemap
[0].base
, ARCH_CONVERT
));
566 xfs_da_log_buf(args
->trans
, bp
, 0, XFS_LBSIZE(dp
->i_mount
) - 1);
573 * Split the leaf node, rebalance, then add the new entry.
576 xfs_dir_leaf_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
577 xfs_da_state_blk_t
*newblk
)
584 * Allocate space for a new leaf node.
587 ASSERT(args
!= NULL
);
588 ASSERT(oldblk
->magic
== XFS_DIR_LEAF_MAGIC
);
589 error
= xfs_da_grow_inode(args
, &blkno
);
592 error
= xfs_dir_leaf_create(args
, blkno
, &newblk
->bp
);
595 newblk
->blkno
= blkno
;
596 newblk
->magic
= XFS_DIR_LEAF_MAGIC
;
599 * Rebalance the entries across the two leaves.
601 xfs_dir_leaf_rebalance(state
, oldblk
, newblk
);
602 error
= xfs_da_blk_link(state
, oldblk
, newblk
);
607 * Insert the new entry in the correct block.
610 error
= xfs_dir_leaf_add(oldblk
->bp
, args
, oldblk
->index
);
612 error
= xfs_dir_leaf_add(newblk
->bp
, args
, newblk
->index
);
616 * Update last hashval in each block since we added the name.
618 oldblk
->hashval
= xfs_dir_leaf_lasthash(oldblk
->bp
, NULL
);
619 newblk
->hashval
= xfs_dir_leaf_lasthash(newblk
->bp
, NULL
);
624 * Add a name to the leaf directory structure.
626 * Must take into account fragmented leaves and leaves where spacemap has
627 * lost some freespace information (ie: holes).
630 xfs_dir_leaf_add(xfs_dabuf_t
*bp
, xfs_da_args_t
*args
, int index
)
632 xfs_dir_leafblock_t
*leaf
;
633 xfs_dir_leaf_hdr_t
*hdr
;
634 xfs_dir_leaf_map_t
*map
;
635 int tablesize
, entsize
, sum
, i
, tmp
, error
;
638 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
639 ASSERT((index
>= 0) && (index
<= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)));
641 entsize
= XFS_DIR_LEAF_ENTSIZE_BYNAME(args
->namelen
);
644 * Search through freemap for first-fit on new name length.
645 * (may need to figure in size of entry struct too)
647 tablesize
= (INT_GET(hdr
->count
, ARCH_CONVERT
) + 1) * (uint
)sizeof(xfs_dir_leaf_entry_t
)
648 + (uint
)sizeof(xfs_dir_leaf_hdr_t
);
649 map
= &hdr
->freemap
[XFS_DIR_LEAF_MAPSIZE
-1];
650 for (sum
= 0, i
= XFS_DIR_LEAF_MAPSIZE
-1; i
>= 0; map
--, i
--) {
651 if (tablesize
> INT_GET(hdr
->firstused
, ARCH_CONVERT
)) {
652 sum
+= INT_GET(map
->size
, ARCH_CONVERT
);
655 if (INT_ISZERO(map
->size
, ARCH_CONVERT
))
656 continue; /* no space in this map */
658 if (INT_GET(map
->base
, ARCH_CONVERT
) < INT_GET(hdr
->firstused
, ARCH_CONVERT
))
659 tmp
+= (uint
)sizeof(xfs_dir_leaf_entry_t
);
660 if (INT_GET(map
->size
, ARCH_CONVERT
) >= tmp
) {
661 if (!args
->justcheck
)
662 xfs_dir_leaf_add_work(bp
, args
, index
, i
);
665 sum
+= INT_GET(map
->size
, ARCH_CONVERT
);
669 * If there are no holes in the address space of the block,
670 * and we don't have enough freespace, then compaction will do us
671 * no good and we should just give up.
673 if (!hdr
->holes
&& (sum
< entsize
))
674 return(XFS_ERROR(ENOSPC
));
677 * Compact the entries to coalesce free space.
678 * Pass the justcheck flag so the checking pass can return
679 * an error, without changing anything, if it won't fit.
681 error
= xfs_dir_leaf_compact(args
->trans
, bp
,
684 (uint
)sizeof(xfs_dir_leaf_entry_t
) : 0,
689 * After compaction, the block is guaranteed to have only one
690 * free region, in freemap[0]. If it is not big enough, give up.
692 if (INT_GET(hdr
->freemap
[0].size
, ARCH_CONVERT
) <
693 (entsize
+ (uint
)sizeof(xfs_dir_leaf_entry_t
)))
694 return(XFS_ERROR(ENOSPC
));
696 if (!args
->justcheck
)
697 xfs_dir_leaf_add_work(bp
, args
, index
, 0);
702 * Add a name to a leaf directory structure.
705 xfs_dir_leaf_add_work(xfs_dabuf_t
*bp
, xfs_da_args_t
*args
, int index
,
708 xfs_dir_leafblock_t
*leaf
;
709 xfs_dir_leaf_hdr_t
*hdr
;
710 xfs_dir_leaf_entry_t
*entry
;
711 xfs_dir_leaf_name_t
*namest
;
712 xfs_dir_leaf_map_t
*map
;
718 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
720 ASSERT((mapindex
>= 0) && (mapindex
< XFS_DIR_LEAF_MAPSIZE
));
721 ASSERT((index
>= 0) && (index
<= INT_GET(hdr
->count
, ARCH_CONVERT
)));
724 * Force open some space in the entry array and fill it in.
726 entry
= &leaf
->entries
[index
];
727 if (index
< INT_GET(hdr
->count
, ARCH_CONVERT
)) {
728 tmp
= INT_GET(hdr
->count
, ARCH_CONVERT
) - index
;
729 tmp
*= (uint
)sizeof(xfs_dir_leaf_entry_t
);
730 ovbcopy(entry
, entry
+ 1, tmp
);
731 xfs_da_log_buf(args
->trans
, bp
,
732 XFS_DA_LOGRANGE(leaf
, entry
, tmp
+ (uint
)sizeof(*entry
)));
734 INT_MOD(hdr
->count
, ARCH_CONVERT
, +1);
737 * Allocate space for the new string (at the end of the run).
739 map
= &hdr
->freemap
[mapindex
];
740 mp
= args
->trans
->t_mountp
;
741 ASSERT(INT_GET(map
->base
, ARCH_CONVERT
) < XFS_LBSIZE(mp
));
742 ASSERT(INT_GET(map
->size
, ARCH_CONVERT
) >= XFS_DIR_LEAF_ENTSIZE_BYNAME(args
->namelen
));
743 ASSERT(INT_GET(map
->size
, ARCH_CONVERT
) < XFS_LBSIZE(mp
));
744 INT_MOD(map
->size
, ARCH_CONVERT
, -(XFS_DIR_LEAF_ENTSIZE_BYNAME(args
->namelen
)));
745 INT_SET(entry
->nameidx
, ARCH_CONVERT
, INT_GET(map
->base
, ARCH_CONVERT
) + INT_GET(map
->size
, ARCH_CONVERT
));
746 INT_SET(entry
->hashval
, ARCH_CONVERT
, args
->hashval
);
747 entry
->namelen
= args
->namelen
;
748 xfs_da_log_buf(args
->trans
, bp
,
749 XFS_DA_LOGRANGE(leaf
, entry
, sizeof(*entry
)));
752 * Copy the string and inode number into the new space.
754 namest
= XFS_DIR_LEAF_NAMESTRUCT(leaf
, INT_GET(entry
->nameidx
, ARCH_CONVERT
));
755 XFS_DIR_SF_PUT_DIRINO_ARCH(&args
->inumber
, &namest
->inumber
, ARCH_CONVERT
);
756 bcopy(args
->name
, namest
->name
, args
->namelen
);
757 xfs_da_log_buf(args
->trans
, bp
,
758 XFS_DA_LOGRANGE(leaf
, namest
, XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry
)));
761 * Update the control info for this leaf node
763 if (INT_GET(entry
->nameidx
, ARCH_CONVERT
) < INT_GET(hdr
->firstused
, ARCH_CONVERT
))
764 INT_COPY(hdr
->firstused
, entry
->nameidx
, ARCH_CONVERT
);
765 ASSERT(INT_GET(hdr
->firstused
, ARCH_CONVERT
) >= ((INT_GET(hdr
->count
, ARCH_CONVERT
)*sizeof(*entry
))+sizeof(*hdr
)));
766 tmp
= (INT_GET(hdr
->count
, ARCH_CONVERT
)-1) * (uint
)sizeof(xfs_dir_leaf_entry_t
)
767 + (uint
)sizeof(xfs_dir_leaf_hdr_t
);
768 map
= &hdr
->freemap
[0];
769 for (i
= 0; i
< XFS_DIR_LEAF_MAPSIZE
; map
++, i
++) {
770 if (INT_GET(map
->base
, ARCH_CONVERT
) == tmp
) {
771 INT_MOD(map
->base
, ARCH_CONVERT
, (uint
)sizeof(xfs_dir_leaf_entry_t
));
772 INT_MOD(map
->size
, ARCH_CONVERT
, -((uint
)sizeof(xfs_dir_leaf_entry_t
)));
775 INT_MOD(hdr
->namebytes
, ARCH_CONVERT
, args
->namelen
);
776 xfs_da_log_buf(args
->trans
, bp
,
777 XFS_DA_LOGRANGE(leaf
, hdr
, sizeof(*hdr
)));
781 * Garbage collect a leaf directory block by copying it to a new buffer.
784 xfs_dir_leaf_compact(xfs_trans_t
*trans
, xfs_dabuf_t
*bp
, int musthave
,
787 xfs_dir_leafblock_t
*leaf_s
, *leaf_d
;
788 xfs_dir_leaf_hdr_t
*hdr_s
, *hdr_d
;
791 char *tmpbuffer2
=NULL
;
795 mp
= trans
->t_mountp
;
796 lbsize
= XFS_LBSIZE(mp
);
797 tmpbuffer
= kmem_alloc(lbsize
, KM_SLEEP
);
798 ASSERT(tmpbuffer
!= NULL
);
799 bcopy(bp
->data
, tmpbuffer
, lbsize
);
802 * Make a second copy in case xfs_dir_leaf_moveents()
803 * below destroys the original.
805 if (musthave
|| justcheck
) {
806 tmpbuffer2
= kmem_alloc(lbsize
, KM_SLEEP
);
807 bcopy(bp
->data
, tmpbuffer2
, lbsize
);
809 bzero(bp
->data
, lbsize
);
812 * Copy basic information
814 leaf_s
= (xfs_dir_leafblock_t
*)tmpbuffer
;
816 hdr_s
= &leaf_s
->hdr
;
817 hdr_d
= &leaf_d
->hdr
;
818 hdr_d
->info
= hdr_s
->info
; /* struct copy */
819 INT_SET(hdr_d
->firstused
, ARCH_CONVERT
, lbsize
);
820 if (INT_ISZERO(hdr_d
->firstused
, ARCH_CONVERT
))
821 INT_SET(hdr_d
->firstused
, ARCH_CONVERT
, lbsize
- 1);
822 INT_ZERO(hdr_d
->namebytes
, ARCH_CONVERT
);
823 INT_ZERO(hdr_d
->count
, ARCH_CONVERT
);
825 INT_SET(hdr_d
->freemap
[0].base
, ARCH_CONVERT
, sizeof(xfs_dir_leaf_hdr_t
));
826 INT_SET(hdr_d
->freemap
[0].size
, ARCH_CONVERT
, INT_GET(hdr_d
->firstused
, ARCH_CONVERT
) - INT_GET(hdr_d
->freemap
[0].base
, ARCH_CONVERT
));
829 * Copy all entry's in the same (sorted) order,
830 * but allocate filenames packed and in sequence.
831 * This changes the source (leaf_s) as well.
833 xfs_dir_leaf_moveents(leaf_s
, 0, leaf_d
, 0, (int)INT_GET(hdr_s
->count
, ARCH_CONVERT
), mp
);
835 if (musthave
&& INT_GET(hdr_d
->freemap
[0].size
, ARCH_CONVERT
) < musthave
)
836 rval
= XFS_ERROR(ENOSPC
);
840 if (justcheck
|| rval
== ENOSPC
) {
842 bcopy(tmpbuffer2
, bp
->data
, lbsize
);
844 xfs_da_log_buf(trans
, bp
, 0, lbsize
- 1);
847 kmem_free(tmpbuffer
, lbsize
);
848 if (musthave
|| justcheck
)
849 kmem_free(tmpbuffer2
, lbsize
);
854 * Redistribute the directory entries between two leaf nodes,
855 * taking into account the size of the new entry.
857 * NOTE: if new block is empty, then it will get the upper half of old block.
860 xfs_dir_leaf_rebalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
861 xfs_da_state_blk_t
*blk2
)
863 xfs_da_state_blk_t
*tmp_blk
;
864 xfs_dir_leafblock_t
*leaf1
, *leaf2
;
865 xfs_dir_leaf_hdr_t
*hdr1
, *hdr2
;
866 int count
, totallen
, max
, space
, swap
;
869 * Set up environment.
871 ASSERT(blk1
->magic
== XFS_DIR_LEAF_MAGIC
);
872 ASSERT(blk2
->magic
== XFS_DIR_LEAF_MAGIC
);
873 leaf1
= blk1
->bp
->data
;
874 leaf2
= blk2
->bp
->data
;
875 ASSERT(INT_GET(leaf1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
876 ASSERT(INT_GET(leaf2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
879 * Check ordering of blocks, reverse if it makes things simpler.
882 if (xfs_dir_leaf_order(blk1
->bp
, blk2
->bp
)) {
886 leaf1
= blk1
->bp
->data
;
887 leaf2
= blk2
->bp
->data
;
894 * Examine entries until we reduce the absolute difference in
895 * byte usage between the two blocks to a minimum. Then get
896 * the direction to copy and the number of elements to move.
898 state
->inleaf
= xfs_dir_leaf_figure_balance(state
, blk1
, blk2
,
901 state
->inleaf
= !state
->inleaf
;
904 * Move any entries required from leaf to leaf:
906 if (count
< INT_GET(hdr1
->count
, ARCH_CONVERT
)) {
908 * Figure the total bytes to be added to the destination leaf.
910 count
= INT_GET(hdr1
->count
, ARCH_CONVERT
) - count
; /* number entries being moved */
911 space
= INT_GET(hdr1
->namebytes
, ARCH_CONVERT
) - totallen
;
912 space
+= count
* ((uint
)sizeof(xfs_dir_leaf_name_t
)-1);
913 space
+= count
* (uint
)sizeof(xfs_dir_leaf_entry_t
);
916 * leaf2 is the destination, compact it if it looks tight.
918 max
= INT_GET(hdr2
->firstused
, ARCH_CONVERT
) - (uint
)sizeof(xfs_dir_leaf_hdr_t
);
919 max
-= INT_GET(hdr2
->count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_dir_leaf_entry_t
);
921 xfs_dir_leaf_compact(state
->args
->trans
, blk2
->bp
,
926 * Move high entries from leaf1 to low end of leaf2.
928 xfs_dir_leaf_moveents(leaf1
, INT_GET(hdr1
->count
, ARCH_CONVERT
) - count
,
929 leaf2
, 0, count
, state
->mp
);
931 xfs_da_log_buf(state
->args
->trans
, blk1
->bp
, 0,
933 xfs_da_log_buf(state
->args
->trans
, blk2
->bp
, 0,
936 } else if (count
> INT_GET(hdr1
->count
, ARCH_CONVERT
)) {
938 * Figure the total bytes to be added to the destination leaf.
940 count
-= INT_GET(hdr1
->count
, ARCH_CONVERT
); /* number entries being moved */
941 space
= totallen
- INT_GET(hdr1
->namebytes
, ARCH_CONVERT
);
942 space
+= count
* ((uint
)sizeof(xfs_dir_leaf_name_t
)-1);
943 space
+= count
* (uint
)sizeof(xfs_dir_leaf_entry_t
);
946 * leaf1 is the destination, compact it if it looks tight.
948 max
= INT_GET(hdr1
->firstused
, ARCH_CONVERT
) - (uint
)sizeof(xfs_dir_leaf_hdr_t
);
949 max
-= INT_GET(hdr1
->count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_dir_leaf_entry_t
);
951 xfs_dir_leaf_compact(state
->args
->trans
, blk1
->bp
,
956 * Move low entries from leaf2 to high end of leaf1.
958 xfs_dir_leaf_moveents(leaf2
, 0, leaf1
, (int)INT_GET(hdr1
->count
, ARCH_CONVERT
),
961 xfs_da_log_buf(state
->args
->trans
, blk1
->bp
, 0,
963 xfs_da_log_buf(state
->args
->trans
, blk2
->bp
, 0,
968 * Copy out last hashval in each block for B-tree code.
970 blk1
->hashval
= INT_GET(leaf1
->entries
[ INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
971 blk2
->hashval
= INT_GET(leaf2
->entries
[ INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
974 * Adjust the expected index for insertion.
975 * GROT: this doesn't work unless blk2 was originally empty.
977 if (!state
->inleaf
) {
978 blk2
->index
= blk1
->index
- INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
);
983 * Examine entries until we reduce the absolute difference in
984 * byte usage between the two blocks to a minimum.
985 * GROT: Is this really necessary? With other than a 512 byte blocksize,
986 * GROT: there will always be enough room in either block for a new entry.
987 * GROT: Do a double-split for this case?
990 xfs_dir_leaf_figure_balance(xfs_da_state_t
*state
,
991 xfs_da_state_blk_t
*blk1
,
992 xfs_da_state_blk_t
*blk2
,
993 int *countarg
, int *namebytesarg
)
995 xfs_dir_leafblock_t
*leaf1
, *leaf2
;
996 xfs_dir_leaf_hdr_t
*hdr1
, *hdr2
;
997 xfs_dir_leaf_entry_t
*entry
;
998 int count
, max
, totallen
, half
;
999 int lastdelta
, foundit
, tmp
;
1002 * Set up environment.
1004 leaf1
= blk1
->bp
->data
;
1005 leaf2
= blk2
->bp
->data
;
1012 * Examine entries until we reduce the absolute difference in
1013 * byte usage between the two blocks to a minimum.
1015 max
= INT_GET(hdr1
->count
, ARCH_CONVERT
) + INT_GET(hdr2
->count
, ARCH_CONVERT
);
1016 half
= (max
+1) * (uint
)(sizeof(*entry
)+sizeof(xfs_dir_leaf_entry_t
)-1);
1017 half
+= INT_GET(hdr1
->namebytes
, ARCH_CONVERT
) + INT_GET(hdr2
->namebytes
, ARCH_CONVERT
) + state
->args
->namelen
;
1019 lastdelta
= state
->blocksize
;
1020 entry
= &leaf1
->entries
[0];
1021 for (count
= 0; count
< max
; entry
++, count
++) {
1023 #define XFS_DIR_ABS(A) (((A) < 0) ? -(A) : (A))
1025 * The new entry is in the first block, account for it.
1027 if (count
== blk1
->index
) {
1028 tmp
= totallen
+ (uint
)sizeof(*entry
)
1029 + XFS_DIR_LEAF_ENTSIZE_BYNAME(state
->args
->namelen
);
1030 if (XFS_DIR_ABS(half
- tmp
) > lastdelta
)
1032 lastdelta
= XFS_DIR_ABS(half
- tmp
);
1038 * Wrap around into the second block if necessary.
1040 if (count
== INT_GET(hdr1
->count
, ARCH_CONVERT
)) {
1042 entry
= &leaf1
->entries
[0];
1046 * Figure out if next leaf entry would be too much.
1048 tmp
= totallen
+ (uint
)sizeof(*entry
)
1049 + XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry
);
1050 if (XFS_DIR_ABS(half
- tmp
) > lastdelta
)
1052 lastdelta
= XFS_DIR_ABS(half
- tmp
);
1058 * Calculate the number of namebytes that will end up in lower block.
1059 * If new entry not in lower block, fix up the count.
1062 count
* (uint
)(sizeof(*entry
)+sizeof(xfs_dir_leaf_entry_t
)-1);
1064 totallen
-= (sizeof(*entry
)+sizeof(xfs_dir_leaf_entry_t
)-1) +
1065 state
->args
->namelen
;
1069 *namebytesarg
= totallen
;
1073 /*========================================================================
1074 * Routines used for shrinking the Btree.
1075 *========================================================================*/
1078 * Check a leaf block and its neighbors to see if the block should be
1079 * collapsed into one or the other neighbor. Always keep the block
1080 * with the smaller block number.
1081 * If the current block is over 50% full, don't try to join it, return 0.
1082 * If the block is empty, fill in the state structure and return 2.
1083 * If it can be collapsed, fill in the state structure and return 1.
1084 * If nothing can be done, return 0.
1087 xfs_dir_leaf_toosmall(xfs_da_state_t
*state
, int *action
)
1089 xfs_dir_leafblock_t
*leaf
;
1090 xfs_da_state_blk_t
*blk
;
1091 xfs_da_blkinfo_t
*info
;
1092 int count
, bytes
, forward
, error
, retval
, i
;
1097 * Check for the degenerate case of the block being over 50% full.
1098 * If so, it's not worth even looking to see if we might be able
1099 * to coalesce with a sibling.
1101 blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
1102 info
= blk
->bp
->data
;
1103 ASSERT(INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1104 leaf
= (xfs_dir_leafblock_t
*)info
;
1105 count
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
1106 bytes
= (uint
)sizeof(xfs_dir_leaf_hdr_t
) +
1107 count
* (uint
)sizeof(xfs_dir_leaf_entry_t
) +
1108 count
* ((uint
)sizeof(xfs_dir_leaf_name_t
)-1) +
1109 INT_GET(leaf
->hdr
.namebytes
, ARCH_CONVERT
);
1110 if (bytes
> (state
->blocksize
>> 1)) {
1111 *action
= 0; /* blk over 50%, dont try to join */
1116 * Check for the degenerate case of the block being empty.
1117 * If the block is empty, we'll simply delete it, no need to
1118 * coalesce it with a sibling block. We choose (aribtrarily)
1119 * to merge with the forward block unless it is NULL.
1123 * Make altpath point to the block we want to keep and
1124 * path point to the block we want to drop (this one).
1126 forward
= !INT_ISZERO(info
->forw
, ARCH_CONVERT
);
1127 bcopy(&state
->path
, &state
->altpath
, sizeof(state
->path
));
1128 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
1141 * Examine each sibling block to see if we can coalesce with
1142 * at least 25% free space to spare. We need to figure out
1143 * whether to merge with the forward or the backward block.
1144 * We prefer coalescing with the lower numbered sibling so as
1145 * to shrink a directory over time.
1147 forward
= (INT_GET(info
->forw
, ARCH_CONVERT
) < INT_GET(info
->back
, ARCH_CONVERT
)); /* start with smaller blk num */
1148 for (i
= 0; i
< 2; forward
= !forward
, i
++) {
1150 blkno
= INT_GET(info
->forw
, ARCH_CONVERT
);
1152 blkno
= INT_GET(info
->back
, ARCH_CONVERT
);
1155 error
= xfs_da_read_buf(state
->args
->trans
, state
->args
->dp
,
1162 leaf
= (xfs_dir_leafblock_t
*)info
;
1163 count
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
1164 bytes
= state
->blocksize
- (state
->blocksize
>>2);
1165 bytes
-= INT_GET(leaf
->hdr
.namebytes
, ARCH_CONVERT
);
1167 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1168 count
+= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
1169 bytes
-= INT_GET(leaf
->hdr
.namebytes
, ARCH_CONVERT
);
1170 bytes
-= count
* ((uint
)sizeof(xfs_dir_leaf_name_t
) - 1);
1171 bytes
-= count
* (uint
)sizeof(xfs_dir_leaf_entry_t
);
1172 bytes
-= (uint
)sizeof(xfs_dir_leaf_hdr_t
);
1174 break; /* fits with at least 25% to spare */
1176 xfs_da_brelse(state
->args
->trans
, bp
);
1182 xfs_da_buf_done(bp
);
1185 * Make altpath point to the block we want to keep (the lower
1186 * numbered block) and path point to the block we want to drop.
1188 bcopy(&state
->path
, &state
->altpath
, sizeof(state
->path
));
1189 if (blkno
< blk
->blkno
) {
1190 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
1193 error
= xfs_da_path_shift(state
, &state
->path
, forward
,
1207 * Remove a name from the leaf directory structure.
1209 * Return 1 if leaf is less than 37% full, 0 if >= 37% full.
1210 * If two leaves are 37% full, when combined they will leave 25% free.
1213 xfs_dir_leaf_remove(xfs_trans_t
*trans
, xfs_dabuf_t
*bp
, int index
)
1215 xfs_dir_leafblock_t
*leaf
;
1216 xfs_dir_leaf_hdr_t
*hdr
;
1217 xfs_dir_leaf_map_t
*map
;
1218 xfs_dir_leaf_entry_t
*entry
;
1219 xfs_dir_leaf_name_t
*namest
;
1220 int before
, after
, smallest
, entsize
;
1221 int tablesize
, tmp
, i
;
1225 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1227 mp
= trans
->t_mountp
;
1228 ASSERT((INT_GET(hdr
->count
, ARCH_CONVERT
) > 0) && (INT_GET(hdr
->count
, ARCH_CONVERT
) < (XFS_LBSIZE(mp
)/8)));
1229 ASSERT((index
>= 0) && (index
< INT_GET(hdr
->count
, ARCH_CONVERT
)));
1230 ASSERT(INT_GET(hdr
->firstused
, ARCH_CONVERT
) >= ((INT_GET(hdr
->count
, ARCH_CONVERT
)*sizeof(*entry
))+sizeof(*hdr
)));
1231 entry
= &leaf
->entries
[index
];
1232 ASSERT(INT_GET(entry
->nameidx
, ARCH_CONVERT
) >= INT_GET(hdr
->firstused
, ARCH_CONVERT
));
1233 ASSERT(INT_GET(entry
->nameidx
, ARCH_CONVERT
) < XFS_LBSIZE(mp
));
1236 * Scan through free region table:
1237 * check for adjacency of free'd entry with an existing one,
1238 * find smallest free region in case we need to replace it,
1239 * adjust any map that borders the entry table,
1241 tablesize
= INT_GET(hdr
->count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_dir_leaf_entry_t
)
1242 + (uint
)sizeof(xfs_dir_leaf_hdr_t
);
1243 map
= &hdr
->freemap
[0];
1244 tmp
= INT_GET(map
->size
, ARCH_CONVERT
);
1245 before
= after
= -1;
1246 smallest
= XFS_DIR_LEAF_MAPSIZE
- 1;
1247 entsize
= XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry
);
1248 for (i
= 0; i
< XFS_DIR_LEAF_MAPSIZE
; map
++, i
++) {
1249 ASSERT(INT_GET(map
->base
, ARCH_CONVERT
) < XFS_LBSIZE(mp
));
1250 ASSERT(INT_GET(map
->size
, ARCH_CONVERT
) < XFS_LBSIZE(mp
));
1251 if (INT_GET(map
->base
, ARCH_CONVERT
) == tablesize
) {
1252 INT_MOD(map
->base
, ARCH_CONVERT
, -((uint
)sizeof(xfs_dir_leaf_entry_t
)));
1253 INT_MOD(map
->size
, ARCH_CONVERT
, (uint
)sizeof(xfs_dir_leaf_entry_t
));
1256 if ((INT_GET(map
->base
, ARCH_CONVERT
) + INT_GET(map
->size
, ARCH_CONVERT
)) == INT_GET(entry
->nameidx
, ARCH_CONVERT
)) {
1258 } else if (INT_GET(map
->base
, ARCH_CONVERT
) == (INT_GET(entry
->nameidx
, ARCH_CONVERT
) + entsize
)) {
1260 } else if (INT_GET(map
->size
, ARCH_CONVERT
) < tmp
) {
1261 tmp
= INT_GET(map
->size
, ARCH_CONVERT
);
1267 * Coalesce adjacent freemap regions,
1268 * or replace the smallest region.
1270 if ((before
>= 0) || (after
>= 0)) {
1271 if ((before
>= 0) && (after
>= 0)) {
1272 map
= &hdr
->freemap
[before
];
1273 INT_MOD(map
->size
, ARCH_CONVERT
, entsize
);
1274 INT_MOD(map
->size
, ARCH_CONVERT
, INT_GET(hdr
->freemap
[after
].size
, ARCH_CONVERT
));
1275 INT_ZERO(hdr
->freemap
[after
].base
, ARCH_CONVERT
);
1276 INT_ZERO(hdr
->freemap
[after
].size
, ARCH_CONVERT
);
1277 } else if (before
>= 0) {
1278 map
= &hdr
->freemap
[before
];
1279 INT_MOD(map
->size
, ARCH_CONVERT
, entsize
);
1281 map
= &hdr
->freemap
[after
];
1282 INT_COPY(map
->base
, entry
->nameidx
, ARCH_CONVERT
);
1283 INT_MOD(map
->size
, ARCH_CONVERT
, entsize
);
1287 * Replace smallest region (if it is smaller than free'd entry)
1289 map
= &hdr
->freemap
[smallest
];
1290 if (INT_GET(map
->size
, ARCH_CONVERT
) < entsize
) {
1291 INT_COPY(map
->base
, entry
->nameidx
, ARCH_CONVERT
);
1292 INT_SET(map
->size
, ARCH_CONVERT
, entsize
);
1297 * Did we remove the first entry?
1299 if (INT_GET(entry
->nameidx
, ARCH_CONVERT
) == INT_GET(hdr
->firstused
, ARCH_CONVERT
))
1305 * Compress the remaining entries and zero out the removed stuff.
1307 namest
= XFS_DIR_LEAF_NAMESTRUCT(leaf
, INT_GET(entry
->nameidx
, ARCH_CONVERT
));
1308 bzero((char *)namest
, entsize
);
1309 xfs_da_log_buf(trans
, bp
, XFS_DA_LOGRANGE(leaf
, namest
, entsize
));
1311 INT_MOD(hdr
->namebytes
, ARCH_CONVERT
, -(entry
->namelen
));
1312 tmp
= (INT_GET(hdr
->count
, ARCH_CONVERT
) - index
) * (uint
)sizeof(xfs_dir_leaf_entry_t
);
1313 ovbcopy(entry
+ 1, entry
, tmp
);
1314 INT_MOD(hdr
->count
, ARCH_CONVERT
, -1);
1315 xfs_da_log_buf(trans
, bp
,
1316 XFS_DA_LOGRANGE(leaf
, entry
, tmp
+ (uint
)sizeof(*entry
)));
1317 entry
= &leaf
->entries
[INT_GET(hdr
->count
, ARCH_CONVERT
)];
1318 bzero((char *)entry
, sizeof(xfs_dir_leaf_entry_t
));
1321 * If we removed the first entry, re-find the first used byte
1322 * in the name area. Note that if the entry was the "firstused",
1323 * then we don't have a "hole" in our block resulting from
1324 * removing the name.
1327 tmp
= XFS_LBSIZE(mp
);
1328 entry
= &leaf
->entries
[0];
1329 for (i
= INT_GET(hdr
->count
, ARCH_CONVERT
)-1; i
>= 0; entry
++, i
--) {
1330 ASSERT(INT_GET(entry
->nameidx
, ARCH_CONVERT
) >= INT_GET(hdr
->firstused
, ARCH_CONVERT
));
1331 ASSERT(INT_GET(entry
->nameidx
, ARCH_CONVERT
) < XFS_LBSIZE(mp
));
1332 if (INT_GET(entry
->nameidx
, ARCH_CONVERT
) < tmp
)
1333 tmp
= INT_GET(entry
->nameidx
, ARCH_CONVERT
);
1335 INT_SET(hdr
->firstused
, ARCH_CONVERT
, tmp
);
1336 if (INT_ISZERO(hdr
->firstused
, ARCH_CONVERT
))
1337 INT_SET(hdr
->firstused
, ARCH_CONVERT
, tmp
- 1);
1339 hdr
->holes
= 1; /* mark as needing compaction */
1342 xfs_da_log_buf(trans
, bp
, XFS_DA_LOGRANGE(leaf
, hdr
, sizeof(*hdr
)));
1345 * Check if leaf is less than 50% full, caller may want to
1346 * "join" the leaf with a sibling if so.
1348 tmp
= (uint
)sizeof(xfs_dir_leaf_hdr_t
);
1349 tmp
+= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_dir_leaf_entry_t
);
1350 tmp
+= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) * ((uint
)sizeof(xfs_dir_leaf_name_t
) - 1);
1351 tmp
+= INT_GET(leaf
->hdr
.namebytes
, ARCH_CONVERT
);
1352 if (tmp
< mp
->m_dir_magicpct
)
1353 return(1); /* leaf is < 37% full */
1358 * Move all the directory entries from drop_leaf into save_leaf.
1361 xfs_dir_leaf_unbalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
1362 xfs_da_state_blk_t
*save_blk
)
1364 xfs_dir_leafblock_t
*drop_leaf
, *save_leaf
, *tmp_leaf
;
1365 xfs_dir_leaf_hdr_t
*drop_hdr
, *save_hdr
, *tmp_hdr
;
1370 * Set up environment.
1373 ASSERT(drop_blk
->magic
== XFS_DIR_LEAF_MAGIC
);
1374 ASSERT(save_blk
->magic
== XFS_DIR_LEAF_MAGIC
);
1375 drop_leaf
= drop_blk
->bp
->data
;
1376 save_leaf
= save_blk
->bp
->data
;
1377 ASSERT(INT_GET(drop_leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1378 ASSERT(INT_GET(save_leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1379 drop_hdr
= &drop_leaf
->hdr
;
1380 save_hdr
= &save_leaf
->hdr
;
1383 * Save last hashval from dying block for later Btree fixup.
1385 drop_blk
->hashval
= INT_GET(drop_leaf
->entries
[ drop_leaf
->hdr
.count
-1 ].hashval
, ARCH_CONVERT
);
1388 * Check if we need a temp buffer, or can we do it in place.
1389 * Note that we don't check "leaf" for holes because we will
1390 * always be dropping it, toosmall() decided that for us already.
1392 if (save_hdr
->holes
== 0) {
1394 * dest leaf has no holes, so we add there. May need
1395 * to make some room in the entry array.
1397 if (xfs_dir_leaf_order(save_blk
->bp
, drop_blk
->bp
)) {
1398 xfs_dir_leaf_moveents(drop_leaf
, 0, save_leaf
, 0,
1399 (int)INT_GET(drop_hdr
->count
, ARCH_CONVERT
), mp
);
1401 xfs_dir_leaf_moveents(drop_leaf
, 0,
1402 save_leaf
, INT_GET(save_hdr
->count
, ARCH_CONVERT
),
1403 (int)INT_GET(drop_hdr
->count
, ARCH_CONVERT
), mp
);
1407 * Destination has holes, so we make a temporary copy
1408 * of the leaf and add them both to that.
1410 tmpbuffer
= kmem_alloc(state
->blocksize
, KM_SLEEP
);
1411 ASSERT(tmpbuffer
!= NULL
);
1412 bzero(tmpbuffer
, state
->blocksize
);
1413 tmp_leaf
= (xfs_dir_leafblock_t
*)tmpbuffer
;
1414 tmp_hdr
= &tmp_leaf
->hdr
;
1415 tmp_hdr
->info
= save_hdr
->info
; /* struct copy */
1416 INT_ZERO(tmp_hdr
->count
, ARCH_CONVERT
);
1417 INT_SET(tmp_hdr
->firstused
, ARCH_CONVERT
, state
->blocksize
);
1418 if (INT_ISZERO(tmp_hdr
->firstused
, ARCH_CONVERT
))
1419 INT_SET(tmp_hdr
->firstused
, ARCH_CONVERT
, state
->blocksize
- 1);
1420 INT_ZERO(tmp_hdr
->namebytes
, ARCH_CONVERT
);
1421 if (xfs_dir_leaf_order(save_blk
->bp
, drop_blk
->bp
)) {
1422 xfs_dir_leaf_moveents(drop_leaf
, 0, tmp_leaf
, 0,
1423 (int)INT_GET(drop_hdr
->count
, ARCH_CONVERT
), mp
);
1424 xfs_dir_leaf_moveents(save_leaf
, 0,
1425 tmp_leaf
, INT_GET(tmp_leaf
->hdr
.count
, ARCH_CONVERT
),
1426 (int)INT_GET(save_hdr
->count
, ARCH_CONVERT
), mp
);
1428 xfs_dir_leaf_moveents(save_leaf
, 0, tmp_leaf
, 0,
1429 (int)INT_GET(save_hdr
->count
, ARCH_CONVERT
), mp
);
1430 xfs_dir_leaf_moveents(drop_leaf
, 0,
1431 tmp_leaf
, INT_GET(tmp_leaf
->hdr
.count
, ARCH_CONVERT
),
1432 (int)INT_GET(drop_hdr
->count
, ARCH_CONVERT
), mp
);
1434 bcopy(tmp_leaf
, save_leaf
, state
->blocksize
);
1435 kmem_free(tmpbuffer
, state
->blocksize
);
1438 xfs_da_log_buf(state
->args
->trans
, save_blk
->bp
, 0,
1439 state
->blocksize
- 1);
1442 * Copy out last hashval in each block for B-tree code.
1444 save_blk
->hashval
= INT_GET(save_leaf
->entries
[ INT_GET(save_leaf
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1448 /*========================================================================
1449 * Routines used for finding things in the Btree.
1450 *========================================================================*/
1453 * Look up a name in a leaf directory structure.
1454 * This is the internal routine, it uses the caller's buffer.
1456 * Note that duplicate keys are allowed, but only check within the
1457 * current leaf node. The Btree code must check in adjacent leaf nodes.
1459 * Return in *index the index into the entry[] array of either the found
1460 * entry, or where the entry should have been (insert before that entry).
1462 * Don't change the args->inumber unless we find the filename.
1465 xfs_dir_leaf_lookup_int(xfs_dabuf_t
*bp
, xfs_da_args_t
*args
, int *index
)
1467 xfs_dir_leafblock_t
*leaf
;
1468 xfs_dir_leaf_entry_t
*entry
;
1469 xfs_dir_leaf_name_t
*namest
;
1471 xfs_dahash_t hashval
;
1474 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1475 ASSERT(INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) < (XFS_LBSIZE(args
->dp
->i_mount
)/8));
1478 * Binary search. (note: small blocks will skip this loop)
1480 hashval
= args
->hashval
;
1481 probe
= span
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) / 2;
1482 for (entry
= &leaf
->entries
[probe
]; span
> 4;
1483 entry
= &leaf
->entries
[probe
]) {
1485 if (INT_GET(entry
->hashval
, ARCH_CONVERT
) < hashval
)
1487 else if (INT_GET(entry
->hashval
, ARCH_CONVERT
) > hashval
)
1492 ASSERT((probe
>= 0) && \
1493 ((INT_ISZERO(leaf
->hdr
.count
, ARCH_CONVERT
)) || (probe
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
))));
1494 ASSERT((span
<= 4) || (INT_GET(entry
->hashval
, ARCH_CONVERT
) == hashval
));
1497 * Since we may have duplicate hashval's, find the first matching
1498 * hashval in the leaf.
1500 while ((probe
> 0) && (INT_GET(entry
->hashval
, ARCH_CONVERT
) >= hashval
)) {
1504 while ((probe
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)) && (INT_GET(entry
->hashval
, ARCH_CONVERT
) < hashval
)) {
1508 if ((probe
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)) || (INT_GET(entry
->hashval
, ARCH_CONVERT
) != hashval
)) {
1510 ASSERT(args
->oknoent
);
1511 return(XFS_ERROR(ENOENT
));
1515 * Duplicate keys may be present, so search all of them for a match.
1517 while ((probe
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)) && (INT_GET(entry
->hashval
, ARCH_CONVERT
) == hashval
)) {
1518 namest
= XFS_DIR_LEAF_NAMESTRUCT(leaf
, INT_GET(entry
->nameidx
, ARCH_CONVERT
));
1519 if (entry
->namelen
== args
->namelen
&&
1520 namest
->name
[0] == args
->name
[0] &&
1521 bcmp(args
->name
, namest
->name
, args
->namelen
) == 0) {
1522 XFS_DIR_SF_GET_DIRINO_ARCH(&namest
->inumber
, &args
->inumber
, ARCH_CONVERT
);
1524 return(XFS_ERROR(EEXIST
));
1530 ASSERT(probe
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) || args
->oknoent
);
1531 return(XFS_ERROR(ENOENT
));
1534 /*========================================================================
1536 *========================================================================*/
1539 * Move the indicated entries from one leaf to another.
1540 * NOTE: this routine modifies both source and destination leaves.
1544 xfs_dir_leaf_moveents(xfs_dir_leafblock_t
*leaf_s
, int start_s
,
1545 xfs_dir_leafblock_t
*leaf_d
, int start_d
,
1546 int count
, xfs_mount_t
*mp
)
1548 xfs_dir_leaf_hdr_t
*hdr_s
, *hdr_d
;
1549 xfs_dir_leaf_entry_t
*entry_s
, *entry_d
;
1553 * Check for nothing to do.
1559 * Set up environment.
1561 ASSERT(INT_GET(leaf_s
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1562 ASSERT(INT_GET(leaf_d
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1563 hdr_s
= &leaf_s
->hdr
;
1564 hdr_d
= &leaf_d
->hdr
;
1565 ASSERT((INT_GET(hdr_s
->count
, ARCH_CONVERT
) > 0) && (INT_GET(hdr_s
->count
, ARCH_CONVERT
) < (XFS_LBSIZE(mp
)/8)));
1566 ASSERT(INT_GET(hdr_s
->firstused
, ARCH_CONVERT
) >=
1567 ((INT_GET(hdr_s
->count
, ARCH_CONVERT
)*sizeof(*entry_s
))+sizeof(*hdr_s
)));
1568 ASSERT(INT_GET(hdr_d
->count
, ARCH_CONVERT
) < (XFS_LBSIZE(mp
)/8));
1569 ASSERT(INT_GET(hdr_d
->firstused
, ARCH_CONVERT
) >=
1570 ((INT_GET(hdr_d
->count
, ARCH_CONVERT
)*sizeof(*entry_d
))+sizeof(*hdr_d
)));
1572 ASSERT(start_s
< INT_GET(hdr_s
->count
, ARCH_CONVERT
));
1573 ASSERT(start_d
<= INT_GET(hdr_d
->count
, ARCH_CONVERT
));
1574 ASSERT(count
<= INT_GET(hdr_s
->count
, ARCH_CONVERT
));
1577 * Move the entries in the destination leaf up to make a hole?
1579 if (start_d
< INT_GET(hdr_d
->count
, ARCH_CONVERT
)) {
1580 tmp
= INT_GET(hdr_d
->count
, ARCH_CONVERT
) - start_d
;
1581 tmp
*= (uint
)sizeof(xfs_dir_leaf_entry_t
);
1582 entry_s
= &leaf_d
->entries
[start_d
];
1583 entry_d
= &leaf_d
->entries
[start_d
+ count
];
1584 bcopy(entry_s
, entry_d
, tmp
);
1588 * Copy all entry's in the same (sorted) order,
1589 * but allocate filenames packed and in sequence.
1591 entry_s
= &leaf_s
->entries
[start_s
];
1592 entry_d
= &leaf_d
->entries
[start_d
];
1593 for (i
= 0; i
< count
; entry_s
++, entry_d
++, i
++) {
1594 ASSERT(INT_GET(entry_s
->nameidx
, ARCH_CONVERT
) >= INT_GET(hdr_s
->firstused
, ARCH_CONVERT
));
1595 ASSERT(entry_s
->namelen
< MAXNAMELEN
);
1596 tmp
= XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry_s
);
1597 INT_MOD(hdr_d
->firstused
, ARCH_CONVERT
, -(tmp
));
1598 entry_d
->hashval
= entry_s
->hashval
; /* INT_: direct copy */
1599 INT_COPY(entry_d
->nameidx
, hdr_d
->firstused
, ARCH_CONVERT
);
1600 entry_d
->namelen
= entry_s
->namelen
;
1601 ASSERT(INT_GET(entry_d
->nameidx
, ARCH_CONVERT
) + tmp
<= XFS_LBSIZE(mp
));
1602 bcopy(XFS_DIR_LEAF_NAMESTRUCT(leaf_s
, INT_GET(entry_s
->nameidx
, ARCH_CONVERT
)),
1603 XFS_DIR_LEAF_NAMESTRUCT(leaf_d
, INT_GET(entry_d
->nameidx
, ARCH_CONVERT
)), tmp
);
1604 ASSERT(INT_GET(entry_s
->nameidx
, ARCH_CONVERT
) + tmp
<= XFS_LBSIZE(mp
));
1605 bzero((char *)XFS_DIR_LEAF_NAMESTRUCT(leaf_s
, INT_GET(entry_s
->nameidx
, ARCH_CONVERT
)),
1607 INT_MOD(hdr_s
->namebytes
, ARCH_CONVERT
, -(entry_d
->namelen
));
1608 INT_MOD(hdr_d
->namebytes
, ARCH_CONVERT
, entry_d
->namelen
);
1609 INT_MOD(hdr_s
->count
, ARCH_CONVERT
, -1);
1610 INT_MOD(hdr_d
->count
, ARCH_CONVERT
, +1);
1611 tmp
= INT_GET(hdr_d
->count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_dir_leaf_entry_t
)
1612 + (uint
)sizeof(xfs_dir_leaf_hdr_t
);
1613 ASSERT(INT_GET(hdr_d
->firstused
, ARCH_CONVERT
) >= tmp
);
1618 * Zero out the entries we just copied.
1620 if (start_s
== INT_GET(hdr_s
->count
, ARCH_CONVERT
)) {
1621 tmp
= count
* (uint
)sizeof(xfs_dir_leaf_entry_t
);
1622 entry_s
= &leaf_s
->entries
[start_s
];
1623 ASSERT((char *)entry_s
+ tmp
<= (char *)leaf_s
+ XFS_LBSIZE(mp
));
1624 bzero((char *)entry_s
, tmp
);
1627 * Move the remaining entries down to fill the hole,
1628 * then zero the entries at the top.
1630 tmp
= INT_GET(hdr_s
->count
, ARCH_CONVERT
) - count
;
1631 tmp
*= (uint
)sizeof(xfs_dir_leaf_entry_t
);
1632 entry_s
= &leaf_s
->entries
[start_s
+ count
];
1633 entry_d
= &leaf_s
->entries
[start_s
];
1634 bcopy(entry_s
, entry_d
, tmp
);
1636 tmp
= count
* (uint
)sizeof(xfs_dir_leaf_entry_t
);
1637 entry_s
= &leaf_s
->entries
[INT_GET(hdr_s
->count
, ARCH_CONVERT
)];
1638 ASSERT((char *)entry_s
+ tmp
<= (char *)leaf_s
+ XFS_LBSIZE(mp
));
1639 bzero((char *)entry_s
, tmp
);
1643 * Fill in the freemap information
1645 INT_SET(hdr_d
->freemap
[0].base
, ARCH_CONVERT
, (uint
)sizeof(xfs_dir_leaf_hdr_t
));
1646 INT_MOD(hdr_d
->freemap
[0].base
, ARCH_CONVERT
, INT_GET(hdr_d
->count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_dir_leaf_entry_t
));
1647 INT_SET(hdr_d
->freemap
[0].size
, ARCH_CONVERT
, INT_GET(hdr_d
->firstused
, ARCH_CONVERT
) - INT_GET(hdr_d
->freemap
[0].base
, ARCH_CONVERT
));
1648 INT_SET(hdr_d
->freemap
[1].base
, ARCH_CONVERT
, INT_ZERO(hdr_d
->freemap
[2].base
, ARCH_CONVERT
));
1649 INT_SET(hdr_d
->freemap
[1].size
, ARCH_CONVERT
, INT_ZERO(hdr_d
->freemap
[2].size
, ARCH_CONVERT
));
1650 hdr_s
->holes
= 1; /* leaf may not be compact */
1654 * Compare two leaf blocks "order".
1657 xfs_dir_leaf_order(xfs_dabuf_t
*leaf1_bp
, xfs_dabuf_t
*leaf2_bp
)
1659 xfs_dir_leafblock_t
*leaf1
, *leaf2
;
1661 leaf1
= leaf1_bp
->data
;
1662 leaf2
= leaf2_bp
->data
;
1663 ASSERT((INT_GET(leaf1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
) &&
1664 (INT_GET(leaf2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
));
1665 if ((INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) > 0) && (INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
) > 0) &&
1666 ((INT_GET(leaf2
->entries
[ 0 ].hashval
, ARCH_CONVERT
) <
1667 INT_GET(leaf1
->entries
[ 0 ].hashval
, ARCH_CONVERT
)) ||
1668 (INT_GET(leaf2
->entries
[ INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
1669 INT_GET(leaf1
->entries
[ INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))) {
1676 * Pick up the last hashvalue from a leaf block.
1679 xfs_dir_leaf_lasthash(xfs_dabuf_t
*bp
, int *count
)
1681 xfs_dir_leafblock_t
*leaf
;
1684 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
);
1686 *count
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
1687 if (INT_ISZERO(leaf
->hdr
.count
, ARCH_CONVERT
))
1689 return(INT_GET(leaf
->entries
[ INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
));