]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libxfs/xfs_dir2_node.c
2 * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
35 * XFS directory implementation, version 2, node form files
36 * See data structures in xfs_dir2_node.h and xfs_da_btree.h.
42 * Log entries from a freespace block.
45 xfs_dir2_free_log_bests(
46 xfs_trans_t
*tp
, /* transaction pointer */
47 xfs_dabuf_t
*bp
, /* freespace buffer */
48 int first
, /* first entry to log */
49 int last
) /* last entry to log */
51 xfs_dir2_free_t
*free
; /* freespace structure */
54 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
55 xfs_da_log_buf(tp
, bp
,
56 (uint
)((char *)&free
->bests
[first
] - (char *)free
),
57 (uint
)((char *)&free
->bests
[last
] - (char *)free
+
58 sizeof(free
->bests
[0]) - 1));
62 * Log header from a freespace block.
65 xfs_dir2_free_log_header(
66 xfs_trans_t
*tp
, /* transaction pointer */
67 xfs_dabuf_t
*bp
) /* freespace buffer */
69 xfs_dir2_free_t
*free
; /* freespace structure */
72 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
73 xfs_da_log_buf(tp
, bp
, (uint
)((char *)&free
->hdr
- (char *)free
),
74 (uint
)(sizeof(xfs_dir2_free_hdr_t
) - 1));
78 * Convert a leaf-format directory to a node-format directory.
79 * We need to change the magic number of the leaf block, and copy
80 * the freespace table out of the leaf block into its own block.
83 xfs_dir2_leaf_to_node(
84 xfs_da_args_t
*args
, /* operation arguments */
85 xfs_dabuf_t
*lbp
) /* leaf buffer */
87 xfs_inode_t
*dp
; /* incore directory inode */
88 int error
; /* error return value */
89 xfs_dabuf_t
*fbp
; /* freespace buffer */
90 xfs_dir2_db_t fdb
; /* freespace block number */
91 xfs_dir2_free_t
*free
; /* freespace structure */
92 xfs_dir2_data_off_t
*from
; /* pointer to freespace entry */
93 int i
; /* leaf freespace index */
94 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
95 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
96 xfs_mount_t
*mp
; /* filesystem mount point */
97 int n
; /* count of live freespc ents */
98 xfs_dir2_data_off_t off
; /* freespace entry value */
99 xfs_dir2_data_off_t
*to
; /* pointer to freespace entry */
100 xfs_trans_t
*tp
; /* transaction pointer */
102 xfs_dir2_trace_args_b("leaf_to_node", args
, lbp
);
107 * Add a freespace block to the directory.
109 if ((error
= xfs_dir2_grow_inode(args
, XFS_DIR2_FREE_SPACE
, &fdb
))) {
112 ASSERT(fdb
== XFS_DIR2_FREE_FIRSTDB(mp
));
114 * Get the buffer for the new freespace block.
116 if ((error
= xfs_da_get_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, fdb
), -1, &fbp
,
123 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
125 * Initialize the freespace block header.
127 INT_SET(free
->hdr
.magic
, ARCH_CONVERT
, XFS_DIR2_FREE_MAGIC
);
128 INT_ZERO(free
->hdr
.firstdb
, ARCH_CONVERT
);
129 ASSERT(INT_GET(ltp
->bestcount
, ARCH_CONVERT
) <= (uint
)dp
->i_d
.di_size
/ mp
->m_dirblksize
);
130 INT_COPY(free
->hdr
.nvalid
, ltp
->bestcount
, ARCH_CONVERT
);
132 * Copy freespace entries from the leaf block to the new block.
133 * Count active entries.
135 for (i
= n
= 0, from
= XFS_DIR2_LEAF_BESTS_P_ARCH(ltp
, ARCH_CONVERT
), to
= free
->bests
;
136 i
< INT_GET(ltp
->bestcount
, ARCH_CONVERT
); i
++, from
++, to
++) {
137 if ((off
= INT_GET(*from
, ARCH_CONVERT
)) != NULLDATAOFF
)
139 INT_SET(*to
, ARCH_CONVERT
, off
);
141 INT_SET(free
->hdr
.nused
, ARCH_CONVERT
, n
);
142 INT_SET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
, XFS_DIR2_LEAFN_MAGIC
);
146 xfs_dir2_leaf_log_header(tp
, lbp
);
147 xfs_dir2_free_log_header(tp
, fbp
);
148 xfs_dir2_free_log_bests(tp
, fbp
, 0, INT_GET(free
->hdr
.nvalid
, ARCH_CONVERT
) - 1);
149 xfs_da_buf_done(fbp
);
150 xfs_dir2_leafn_check(dp
, lbp
);
155 * Add a leaf entry to a leaf block in a node-form directory.
156 * The other work necessary is done from the caller.
158 static int /* error */
160 xfs_dabuf_t
*bp
, /* leaf buffer */
161 xfs_da_args_t
*args
, /* operation arguments */
162 int index
) /* insertion pt for new entry */
164 int compact
; /* compacting stale leaves */
165 xfs_inode_t
*dp
; /* incore directory inode */
166 int highstale
; /* next stale entry */
167 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
168 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
169 int lfloghigh
; /* high leaf entry logging */
170 int lfloglow
; /* low leaf entry logging */
171 int lowstale
; /* previous stale entry */
172 xfs_mount_t
*mp
; /* filesystem mount point */
173 xfs_trans_t
*tp
; /* transaction pointer */
175 xfs_dir2_trace_args_sb("leafn_add", args
, index
, bp
);
181 * If there are already the maximum number of leaf entries in
182 * the block, if there are no stale entries it won't fit.
183 * Caller will do a split. If there are stale entries we'll do
186 if (INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) == XFS_DIR2_MAX_LEAF_ENTS(mp
)) {
187 if (INT_ISZERO(leaf
->hdr
.stale
, ARCH_CONVERT
))
188 return XFS_ERROR(ENOSPC
);
189 compact
= INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) > 1;
192 ASSERT(index
== 0 || INT_GET(leaf
->ents
[index
- 1].hashval
, ARCH_CONVERT
) <= args
->hashval
);
193 ASSERT(index
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) ||
194 INT_GET(leaf
->ents
[index
].hashval
, ARCH_CONVERT
) >= args
->hashval
);
200 * Compact out all but one stale leaf entry. Leaves behind
201 * the entry closest to index.
204 xfs_dir2_leaf_compact_x1(bp
, &index
, &lowstale
, &highstale
,
205 &lfloglow
, &lfloghigh
);
208 * Set impossible logging indices for this case.
210 else if (!INT_ISZERO(leaf
->hdr
.stale
, ARCH_CONVERT
)) {
211 lfloglow
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
215 * No stale entries, just insert a space for the new entry.
217 if (INT_ISZERO(leaf
->hdr
.stale
, ARCH_CONVERT
)) {
218 lep
= &leaf
->ents
[index
];
219 if (index
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
))
220 ovbcopy(lep
, lep
+ 1,
221 (INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - index
) * sizeof(*lep
));
223 lfloghigh
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
224 INT_MOD(leaf
->hdr
.count
, ARCH_CONVERT
, +1);
227 * There are stale entries. We'll use one for the new entry.
231 * If we didn't do a compact then we need to figure out
232 * which stale entry will be used.
236 * Find first stale entry before our insertion point.
238 for (lowstale
= index
- 1;
240 INT_GET(leaf
->ents
[lowstale
].address
, ARCH_CONVERT
) !=
241 XFS_DIR2_NULL_DATAPTR
;
245 * Find next stale entry after insertion point.
246 * Stop looking if the answer would be worse than
247 * lowstale already found.
249 for (highstale
= index
;
250 highstale
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) &&
251 INT_GET(leaf
->ents
[highstale
].address
, ARCH_CONVERT
) !=
252 XFS_DIR2_NULL_DATAPTR
&&
254 index
- lowstale
- 1 >= highstale
- index
);
259 * Using the low stale entry.
260 * Shift entries up toward the stale slot.
263 (highstale
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) ||
264 index
- lowstale
- 1 < highstale
- index
)) {
265 ASSERT(INT_GET(leaf
->ents
[lowstale
].address
, ARCH_CONVERT
) ==
266 XFS_DIR2_NULL_DATAPTR
);
267 ASSERT(index
- lowstale
- 1 >= 0);
268 if (index
- lowstale
- 1 > 0)
269 ovbcopy(&leaf
->ents
[lowstale
+ 1],
270 &leaf
->ents
[lowstale
],
271 (index
- lowstale
- 1) * sizeof(*lep
));
272 lep
= &leaf
->ents
[index
- 1];
273 lfloglow
= MIN(lowstale
, lfloglow
);
274 lfloghigh
= MAX(index
- 1, lfloghigh
);
277 * Using the high stale entry.
278 * Shift entries down toward the stale slot.
281 ASSERT(INT_GET(leaf
->ents
[highstale
].address
, ARCH_CONVERT
) ==
282 XFS_DIR2_NULL_DATAPTR
);
283 ASSERT(highstale
- index
>= 0);
284 if (highstale
- index
> 0)
285 ovbcopy(&leaf
->ents
[index
],
286 &leaf
->ents
[index
+ 1],
287 (highstale
- index
) * sizeof(*lep
));
288 lep
= &leaf
->ents
[index
];
289 lfloglow
= MIN(index
, lfloglow
);
290 lfloghigh
= MAX(highstale
, lfloghigh
);
292 INT_MOD(leaf
->hdr
.stale
, ARCH_CONVERT
, -1);
295 * Insert the new entry, log everything.
297 INT_SET(lep
->hashval
, ARCH_CONVERT
, args
->hashval
);
298 INT_SET(lep
->address
, ARCH_CONVERT
, XFS_DIR2_DB_OFF_TO_DATAPTR(mp
, args
->blkno
, args
->index
));
299 xfs_dir2_leaf_log_header(tp
, bp
);
300 xfs_dir2_leaf_log_ents(tp
, bp
, lfloglow
, lfloghigh
);
301 xfs_dir2_leafn_check(dp
, bp
);
307 * Check internal consistency of a leafn block.
310 xfs_dir2_leafn_check(
311 xfs_inode_t
*dp
, /* incore directory inode */
312 xfs_dabuf_t
*bp
) /* leaf buffer */
314 int i
; /* leaf index */
315 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
316 xfs_mount_t
*mp
; /* filesystem mount point */
317 int stale
; /* count of stale leaves */
321 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
322 ASSERT(INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) <= XFS_DIR2_MAX_LEAF_ENTS(mp
));
323 for (i
= stale
= 0; i
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
); i
++) {
324 if (i
+ 1 < INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)) {
325 ASSERT(INT_GET(leaf
->ents
[i
].hashval
, ARCH_CONVERT
) <=
326 INT_GET(leaf
->ents
[i
+ 1].hashval
, ARCH_CONVERT
));
328 if (INT_GET(leaf
->ents
[i
].address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
331 ASSERT(INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
) == stale
);
336 * Return the last hash value in the leaf.
337 * Stale entries are ok.
339 xfs_dahash_t
/* hash value */
340 xfs_dir2_leafn_lasthash(
341 xfs_dabuf_t
*bp
, /* leaf buffer */
342 int *count
) /* count of entries in leaf */
344 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
347 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
349 *count
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
);
350 if (INT_ISZERO(leaf
->hdr
.count
, ARCH_CONVERT
))
352 return INT_GET(leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
356 * Look up a leaf entry in a node-format leaf block.
357 * If this is an addname then the extrablk in state is a freespace block,
358 * otherwise it's a data block.
361 xfs_dir2_leafn_lookup_int(
362 xfs_dabuf_t
*bp
, /* leaf buffer */
363 xfs_da_args_t
*args
, /* operation arguments */
364 int *indexp
, /* out: leaf entry index */
365 xfs_da_state_t
*state
) /* state to fill in */
367 xfs_dabuf_t
*curbp
; /* current data/free buffer */
368 xfs_dir2_db_t curdb
; /* current data block number */
369 xfs_dir2_db_t curfdb
; /* current free block number */
370 xfs_dir2_data_entry_t
*dep
; /* data block entry */
371 xfs_inode_t
*dp
; /* incore directory inode */
372 int error
; /* error return value */
373 int fi
; /* free entry index */
374 xfs_dir2_free_t
*free
=NULL
; /* free block structure */
375 int index
; /* leaf entry index */
376 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
377 int length
=0; /* length of new data entry */
378 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
379 xfs_mount_t
*mp
; /* filesystem mount point */
380 xfs_dir2_db_t newdb
; /* new data block number */
381 xfs_dir2_db_t newfdb
; /* new free block number */
382 xfs_trans_t
*tp
; /* transaction pointer */
388 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
390 ASSERT(INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) > 0);
392 xfs_dir2_leafn_check(dp
, bp
);
394 * Look up the hash value in the leaf entries.
396 index
= xfs_dir2_leaf_search_hash(args
, bp
);
398 * Do we have a buffer coming in?
400 if (state
->extravalid
)
401 curbp
= state
->extrablk
.bp
;
405 * For addname, it's a free block buffer, get the block number.
408 curfdb
= curbp
? state
->extrablk
.blkno
: -1;
410 length
= XFS_DIR2_DATA_ENTSIZE(args
->namelen
);
411 if ((free
= (curbp
? curbp
->data
: NULL
)))
412 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
415 * For others, it's a data block buffer, get the block number.
419 curdb
= curbp
? state
->extrablk
.blkno
: -1;
422 * Loop over leaf entries with the right hash value.
424 for (lep
= &leaf
->ents
[index
];
425 index
< INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) && INT_GET(lep
->hashval
, ARCH_CONVERT
) == args
->hashval
;
428 * Skip stale leaf entries.
430 if (INT_GET(lep
->address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
433 * Pull the data block number from the entry.
435 newdb
= XFS_DIR2_DATAPTR_TO_DB(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
437 * For addname, we're looking for a place to put the new entry.
438 * We want to use a data block with an entry of equal
439 * hash value to ours if there is one with room.
443 * If this block isn't the data block we already have
444 * in hand, take a look at it.
446 if (newdb
!= curdb
) {
449 * Convert the data block to the free block
450 * holding its freespace information.
452 newfdb
= XFS_DIR2_DB_TO_FDB(mp
, newdb
);
454 * If it's not the one we have in hand,
457 if (newfdb
!= curfdb
) {
459 * If we had one before, drop it.
462 xfs_da_brelse(tp
, curbp
);
464 * Read the free block.
466 if ((error
= xfs_da_read_buf(tp
, dp
,
467 XFS_DIR2_DB_TO_DA(mp
,
475 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) ==
476 XFS_DIR2_FREE_MAGIC
);
477 ASSERT((INT_GET(free
->hdr
.firstdb
, ARCH_CONVERT
) %
478 XFS_DIR2_MAX_FREE_BESTS(mp
)) ==
480 ASSERT(INT_GET(free
->hdr
.firstdb
, ARCH_CONVERT
) <= curdb
);
482 INT_GET(free
->hdr
.firstdb
, ARCH_CONVERT
) +
483 INT_GET(free
->hdr
.nvalid
, ARCH_CONVERT
));
486 * Get the index for our entry.
488 fi
= XFS_DIR2_DB_TO_FDINDEX(mp
, curdb
);
490 * If it has room, return it.
492 if (INT_GET(free
->bests
[fi
], ARCH_CONVERT
) == NULLDATAOFF
) {
493 return XFS_ERROR(EFSCORRUPTED
);
495 if (INT_GET(free
->bests
[fi
], ARCH_CONVERT
) >= length
) {
497 state
->extravalid
= 1;
498 state
->extrablk
.bp
= curbp
;
499 state
->extrablk
.blkno
= curfdb
;
500 state
->extrablk
.index
= fi
;
501 state
->extrablk
.magic
=
503 ASSERT(args
->oknoent
);
504 return XFS_ERROR(ENOENT
);
509 * Not adding a new entry, so we really want to find
510 * the name given to us.
514 * If it's a different data block, go get it.
516 if (newdb
!= curdb
) {
518 * If we had a block before, drop it.
521 xfs_da_brelse(tp
, curbp
);
523 * Read the data block.
526 xfs_da_read_buf(tp
, dp
,
527 XFS_DIR2_DB_TO_DA(mp
, newdb
), -1,
528 &curbp
, XFS_DATA_FORK
))) {
531 xfs_dir2_data_check(dp
, curbp
);
535 * Point to the data entry.
537 dep
= (xfs_dir2_data_entry_t
*)
538 ((char *)curbp
->data
+
539 XFS_DIR2_DATAPTR_TO_OFF(mp
, INT_GET(lep
->address
, ARCH_CONVERT
)));
541 * Compare the entry, return it if it matches.
543 if (dep
->namelen
== args
->namelen
&&
544 dep
->name
[0] == args
->name
[0] &&
545 bcmp(dep
->name
, args
->name
, args
->namelen
) == 0) {
546 args
->inumber
= INT_GET(dep
->inumber
, ARCH_CONVERT
);
548 state
->extravalid
= 1;
549 state
->extrablk
.bp
= curbp
;
550 state
->extrablk
.blkno
= curdb
;
551 state
->extrablk
.index
=
553 (char *)curbp
->data
);
554 state
->extrablk
.magic
= XFS_DIR2_DATA_MAGIC
;
555 return XFS_ERROR(EEXIST
);
560 * Didn't find a match.
561 * If we are holding a buffer, give it back in case our caller
564 if ((state
->extravalid
= (curbp
!= NULL
))) {
565 state
->extrablk
.bp
= curbp
;
566 state
->extrablk
.index
= -1;
568 * For addname, giving back a free block.
571 state
->extrablk
.blkno
= curfdb
;
572 state
->extrablk
.magic
= XFS_DIR2_FREE_MAGIC
;
575 * For other callers, giving back a data block.
578 state
->extrablk
.blkno
= curdb
;
579 state
->extrablk
.magic
= XFS_DIR2_DATA_MAGIC
;
583 * Return the final index, that will be the insertion point.
586 ASSERT(index
== INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) || args
->oknoent
);
587 return XFS_ERROR(ENOENT
);
591 * Move count leaf entries from source to destination leaf.
592 * Log entries and headers. Stale entries are preserved.
595 xfs_dir2_leafn_moveents(
596 xfs_da_args_t
*args
, /* operation arguments */
597 xfs_dabuf_t
*bp_s
, /* source leaf buffer */
598 int start_s
, /* source leaf index */
599 xfs_dabuf_t
*bp_d
, /* destination leaf buffer */
600 int start_d
, /* destination leaf index */
601 int count
) /* count of leaves to copy */
603 xfs_dir2_leaf_t
*leaf_d
; /* destination leaf structure */
604 xfs_dir2_leaf_t
*leaf_s
; /* source leaf structure */
605 int stale
; /* count stale leaves copied */
606 xfs_trans_t
*tp
; /* transaction pointer */
608 xfs_dir2_trace_args_bibii("leafn_moveents", args
, bp_s
, start_s
, bp_d
,
611 * Silently return if nothing to do.
620 * If the destination index is not the end of the current
621 * destination leaf entries, open up a hole in the destination
622 * to hold the new entries.
624 if (start_d
< INT_GET(leaf_d
->hdr
.count
, ARCH_CONVERT
)) {
625 ovbcopy(&leaf_d
->ents
[start_d
], &leaf_d
->ents
[start_d
+ count
],
626 (INT_GET(leaf_d
->hdr
.count
, ARCH_CONVERT
) - start_d
) *
627 sizeof(xfs_dir2_leaf_entry_t
));
628 xfs_dir2_leaf_log_ents(tp
, bp_d
, start_d
+ count
,
629 count
+ INT_GET(leaf_d
->hdr
.count
, ARCH_CONVERT
) - 1);
632 * If the source has stale leaves, count the ones in the copy range
633 * so we can update the header correctly.
635 if (!INT_ISZERO(leaf_s
->hdr
.stale
, ARCH_CONVERT
)) {
636 int i
; /* temp leaf index */
638 for (i
= start_s
, stale
= 0; i
< start_s
+ count
; i
++) {
639 if (INT_GET(leaf_s
->ents
[i
].address
, ARCH_CONVERT
) == XFS_DIR2_NULL_DATAPTR
)
645 * Copy the leaf entries from source to destination.
647 bcopy(&leaf_s
->ents
[start_s
], &leaf_d
->ents
[start_d
],
648 count
* sizeof(xfs_dir2_leaf_entry_t
));
649 xfs_dir2_leaf_log_ents(tp
, bp_d
, start_d
, start_d
+ count
- 1);
651 * If there are source entries after the ones we copied,
652 * delete the ones we copied by sliding the next ones down.
654 if (start_s
+ count
< INT_GET(leaf_s
->hdr
.count
, ARCH_CONVERT
)) {
655 ovbcopy(&leaf_s
->ents
[start_s
+ count
], &leaf_s
->ents
[start_s
],
656 count
* sizeof(xfs_dir2_leaf_entry_t
));
657 xfs_dir2_leaf_log_ents(tp
, bp_s
, start_s
, start_s
+ count
- 1);
660 * Update the headers and log them.
662 INT_MOD(leaf_s
->hdr
.count
, ARCH_CONVERT
, -(count
));
663 INT_MOD(leaf_s
->hdr
.stale
, ARCH_CONVERT
, -(stale
));
664 INT_MOD(leaf_d
->hdr
.count
, ARCH_CONVERT
, count
);
665 INT_MOD(leaf_d
->hdr
.stale
, ARCH_CONVERT
, stale
);
666 xfs_dir2_leaf_log_header(tp
, bp_s
);
667 xfs_dir2_leaf_log_header(tp
, bp_d
);
668 xfs_dir2_leafn_check(args
->dp
, bp_s
);
669 xfs_dir2_leafn_check(args
->dp
, bp_d
);
673 * Determine the sort order of two leaf blocks.
674 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
677 xfs_dir2_leafn_order(
678 xfs_dabuf_t
*leaf1_bp
, /* leaf1 buffer */
679 xfs_dabuf_t
*leaf2_bp
) /* leaf2 buffer */
681 xfs_dir2_leaf_t
*leaf1
; /* leaf1 structure */
682 xfs_dir2_leaf_t
*leaf2
; /* leaf2 structure */
684 leaf1
= leaf1_bp
->data
;
685 leaf2
= leaf2_bp
->data
;
686 ASSERT(INT_GET(leaf1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
687 ASSERT(INT_GET(leaf2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
688 if (INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) > 0 &&
689 INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
) > 0 &&
690 (INT_GET(leaf2
->ents
[0].hashval
, ARCH_CONVERT
) < INT_GET(leaf1
->ents
[0].hashval
, ARCH_CONVERT
) ||
691 INT_GET(leaf2
->ents
[INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
) <
692 INT_GET(leaf1
->ents
[INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
)))
698 * Rebalance leaf entries between two leaf blocks.
699 * This is actually only called when the second block is new,
700 * though the code deals with the general case.
701 * A new entry will be inserted in one of the blocks, and that
702 * entry is taken into account when balancing.
705 xfs_dir2_leafn_rebalance(
706 xfs_da_state_t
*state
, /* btree cursor */
707 xfs_da_state_blk_t
*blk1
, /* first btree block */
708 xfs_da_state_blk_t
*blk2
) /* second btree block */
710 xfs_da_args_t
*args
; /* operation arguments */
711 int count
; /* count (& direction) leaves */
712 int isleft
; /* new goes in left leaf */
713 xfs_dir2_leaf_t
*leaf1
; /* first leaf structure */
714 xfs_dir2_leaf_t
*leaf2
; /* second leaf structure */
715 int mid
; /* midpoint leaf index */
717 int oldstale
; /* old count of stale leaves */
719 int oldsum
; /* old total leaf count */
720 int swap
; /* swapped leaf blocks */
724 * If the block order is wrong, swap the arguments.
726 if ((swap
= xfs_dir2_leafn_order(blk1
->bp
, blk2
->bp
))) {
727 xfs_da_state_blk_t
*tmp
; /* temp for block swap */
733 leaf1
= blk1
->bp
->data
;
734 leaf2
= blk2
->bp
->data
;
735 oldsum
= INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) + INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
);
737 oldstale
= INT_GET(leaf1
->hdr
.stale
, ARCH_CONVERT
) + INT_GET(leaf2
->hdr
.stale
, ARCH_CONVERT
);
741 * If the old leaf count was odd then the new one will be even,
742 * so we need to divide the new count evenly.
745 xfs_dahash_t midhash
; /* middle entry hash value */
747 if (mid
>= INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
))
748 midhash
= INT_GET(leaf2
->ents
[mid
- INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
)].hashval
, ARCH_CONVERT
);
750 midhash
= INT_GET(leaf1
->ents
[mid
].hashval
, ARCH_CONVERT
);
751 isleft
= args
->hashval
<= midhash
;
754 * If the old count is even then the new count is odd, so there's
755 * no preferred side for the new entry.
761 * Calculate moved entry count. Positive means left-to-right,
762 * negative means right-to-left. Then move the entries.
764 count
= INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) - mid
+ (isleft
== 0);
766 xfs_dir2_leafn_moveents(args
, blk1
->bp
,
767 INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) - count
, blk2
->bp
, 0, count
);
769 xfs_dir2_leafn_moveents(args
, blk2
->bp
, 0, blk1
->bp
,
770 INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
), count
);
771 ASSERT(INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) + INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
) == oldsum
);
772 ASSERT(INT_GET(leaf1
->hdr
.stale
, ARCH_CONVERT
) + INT_GET(leaf2
->hdr
.stale
, ARCH_CONVERT
) == oldstale
);
774 * Mark whether we're inserting into the old or new leaf.
776 if (INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) < INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
))
777 state
->inleaf
= swap
;
778 else if (INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
) > INT_GET(leaf2
->hdr
.count
, ARCH_CONVERT
))
779 state
->inleaf
= !swap
;
782 swap
^ (args
->hashval
< INT_GET(leaf2
->ents
[0].hashval
, ARCH_CONVERT
));
784 * Adjust the expected index for insertion.
787 blk2
->index
= blk1
->index
- INT_GET(leaf1
->hdr
.count
, ARCH_CONVERT
);
791 * Remove an entry from a node directory.
792 * This removes the leaf entry and the data entry,
793 * and updates the free block if necessary.
795 STATIC
int /* error */
796 xfs_dir2_leafn_remove(
797 xfs_da_args_t
*args
, /* operation arguments */
798 xfs_dabuf_t
*bp
, /* leaf buffer */
799 int index
, /* leaf entry index */
800 xfs_da_state_blk_t
*dblk
, /* data block */
801 int *rval
) /* resulting block needs join */
803 xfs_dir2_data_t
*data
; /* data block structure */
804 xfs_dir2_db_t db
; /* data block number */
805 xfs_dabuf_t
*dbp
; /* data block buffer */
806 xfs_dir2_data_entry_t
*dep
; /* data block entry */
807 xfs_inode_t
*dp
; /* incore directory inode */
808 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
809 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
810 int longest
; /* longest data free entry */
811 int off
; /* data block entry offset */
812 xfs_mount_t
*mp
; /* filesystem mount point */
813 int needlog
; /* need to log data header */
814 int needscan
; /* need to rescan data frees */
815 xfs_trans_t
*tp
; /* transaction pointer */
817 xfs_dir2_trace_args_sb("leafn_remove", args
, index
, bp
);
822 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
824 * Point to the entry we're removing.
826 lep
= &leaf
->ents
[index
];
828 * Extract the data block and offset from the entry.
830 db
= XFS_DIR2_DATAPTR_TO_DB(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
831 ASSERT(dblk
->blkno
== db
);
832 off
= XFS_DIR2_DATAPTR_TO_OFF(mp
, INT_GET(lep
->address
, ARCH_CONVERT
));
833 ASSERT(dblk
->index
== off
);
835 * Kill the leaf entry by marking it stale.
836 * Log the leaf block changes.
838 INT_MOD(leaf
->hdr
.stale
, ARCH_CONVERT
, +1);
839 xfs_dir2_leaf_log_header(tp
, bp
);
840 INT_SET(lep
->address
, ARCH_CONVERT
, XFS_DIR2_NULL_DATAPTR
);
841 xfs_dir2_leaf_log_ents(tp
, bp
, index
, index
);
843 * Make the data entry free. Keep track of the longest freespace
844 * in the data block in case it changes.
848 dep
= (xfs_dir2_data_entry_t
*)((char *)data
+ off
);
849 longest
= INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
850 needlog
= needscan
= 0;
851 xfs_dir2_data_make_free(tp
, dbp
, off
,
852 XFS_DIR2_DATA_ENTSIZE(dep
->namelen
), &needlog
, &needscan
);
854 * Rescan the data block freespaces for bestfree.
855 * Log the data block header if needed.
858 xfs_dir2_data_freescan(mp
, data
, &needlog
, NULL
);
860 xfs_dir2_data_log_header(tp
, dbp
);
861 xfs_dir2_data_check(dp
, dbp
);
863 * If the longest data block freespace changes, need to update
864 * the corresponding freeblock entry.
866 if (longest
< INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
)) {
867 int error
; /* error return value */
868 xfs_dabuf_t
*fbp
; /* freeblock buffer */
869 xfs_dir2_db_t fdb
; /* freeblock block number */
870 int findex
; /* index in freeblock entries */
871 xfs_dir2_free_t
*free
; /* freeblock structure */
872 int logfree
; /* need to log free entry */
875 * Convert the data block number to a free block,
876 * read in the free block.
878 fdb
= XFS_DIR2_DB_TO_FDB(mp
, db
);
879 if ((error
= xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, fdb
),
880 -1, &fbp
, XFS_DATA_FORK
))) {
884 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
885 ASSERT(INT_GET(free
->hdr
.firstdb
, ARCH_CONVERT
) ==
886 XFS_DIR2_MAX_FREE_BESTS(mp
) *
887 (fdb
- XFS_DIR2_FREE_FIRSTDB(mp
)));
889 * Calculate which entry we need to fix.
891 findex
= XFS_DIR2_DB_TO_FDINDEX(mp
, db
);
892 longest
= INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
894 * If the data block is now empty we can get rid of it
897 if (longest
== mp
->m_dirblksize
- (uint
)sizeof(data
->hdr
)) {
899 * Try to punch out the data block.
901 error
= xfs_dir2_shrink_inode(args
, db
, dbp
);
907 * We can get ENOSPC if there's no space reservation.
908 * In this case just drop the buffer and some one else
909 * will eventually get rid of the empty block.
911 else if (error
== ENOSPC
&& args
->total
== 0)
912 xfs_da_buf_done(dbp
);
917 * If we got rid of the data block, we can eliminate that entry
922 * One less used entry in the free table.
924 INT_MOD(free
->hdr
.nused
, ARCH_CONVERT
, -1);
925 xfs_dir2_free_log_header(tp
, fbp
);
927 * If this was the last entry in the table, we can
928 * trim the table size back. There might be other
929 * entries at the end referring to non-existent
930 * data blocks, get those too.
932 if (findex
== INT_GET(free
->hdr
.nvalid
, ARCH_CONVERT
) - 1) {
933 int i
; /* free entry index */
936 i
>= 0 && INT_GET(free
->bests
[i
], ARCH_CONVERT
) == NULLDATAOFF
;
939 INT_SET(free
->hdr
.nvalid
, ARCH_CONVERT
, i
+ 1);
943 * Not the last entry, just punch it out.
946 INT_SET(free
->bests
[findex
], ARCH_CONVERT
, NULLDATAOFF
);
950 * If there are no useful entries left in the block,
951 * get rid of the block if we can.
953 if (INT_ISZERO(free
->hdr
.nused
, ARCH_CONVERT
)) {
954 error
= xfs_dir2_shrink_inode(args
, fdb
, fbp
);
958 } else if (error
!= ENOSPC
|| args
->total
!= 0)
961 * It's possible to get ENOSPC if there is no
962 * space reservation. In this case some one
963 * else will eventually get rid of this block.
968 * Data block is not empty, just set the free entry to
972 INT_SET(free
->bests
[findex
], ARCH_CONVERT
, longest
);
976 * Log the free entry that changed, unless we got rid of it.
979 xfs_dir2_free_log_bests(tp
, fbp
, findex
, findex
);
981 * Drop the buffer if we still have it.
984 xfs_da_buf_done(fbp
);
986 xfs_dir2_leafn_check(dp
, bp
);
988 * Return indication of whether this leaf block is emtpy enough
989 * to justify trying to join it with a neighbor.
992 ((uint
)sizeof(leaf
->hdr
) +
993 (uint
)sizeof(leaf
->ents
[0]) *
994 (INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
))) <
1000 * Split the leaf entries in the old block into old and new blocks.
1003 xfs_dir2_leafn_split(
1004 xfs_da_state_t
*state
, /* btree cursor */
1005 xfs_da_state_blk_t
*oldblk
, /* original block */
1006 xfs_da_state_blk_t
*newblk
) /* newly created block */
1008 xfs_da_args_t
*args
; /* operation arguments */
1009 xfs_dablk_t blkno
; /* new leaf block number */
1010 int error
; /* error return value */
1011 xfs_mount_t
*mp
; /* filesystem mount point */
1014 * Allocate space for a new leaf node.
1017 mp
= args
->dp
->i_mount
;
1018 ASSERT(args
!= NULL
);
1019 ASSERT(oldblk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1020 error
= xfs_da_grow_inode(args
, &blkno
);
1025 * Initialize the new leaf block.
1027 error
= xfs_dir2_leaf_init(args
, XFS_DIR2_DA_TO_DB(mp
, blkno
),
1028 &newblk
->bp
, XFS_DIR2_LEAFN_MAGIC
);
1032 newblk
->blkno
= blkno
;
1033 newblk
->magic
= XFS_DIR2_LEAFN_MAGIC
;
1035 * Rebalance the entries across the two leaves, link the new
1036 * block into the leaves.
1038 xfs_dir2_leafn_rebalance(state
, oldblk
, newblk
);
1039 error
= xfs_da_blk_link(state
, oldblk
, newblk
);
1044 * Insert the new entry in the correct block.
1047 error
= xfs_dir2_leafn_add(oldblk
->bp
, args
, oldblk
->index
);
1049 error
= xfs_dir2_leafn_add(newblk
->bp
, args
, newblk
->index
);
1051 * Update last hashval in each block since we added the name.
1053 oldblk
->hashval
= xfs_dir2_leafn_lasthash(oldblk
->bp
, NULL
);
1054 newblk
->hashval
= xfs_dir2_leafn_lasthash(newblk
->bp
, NULL
);
1055 xfs_dir2_leafn_check(args
->dp
, oldblk
->bp
);
1056 xfs_dir2_leafn_check(args
->dp
, newblk
->bp
);
1061 * Check a leaf block and its neighbors to see if the block should be
1062 * collapsed into one or the other neighbor. Always keep the block
1063 * with the smaller block number.
1064 * If the current block is over 50% full, don't try to join it, return 0.
1065 * If the block is empty, fill in the state structure and return 2.
1066 * If it can be collapsed, fill in the state structure and return 1.
1067 * If nothing can be done, return 0.
1070 xfs_dir2_leafn_toosmall(
1071 xfs_da_state_t
*state
, /* btree cursor */
1072 int *action
) /* resulting action to take */
1074 xfs_da_state_blk_t
*blk
; /* leaf block */
1075 xfs_dablk_t blkno
; /* leaf block number */
1076 xfs_dabuf_t
*bp
; /* leaf buffer */
1077 int bytes
; /* bytes in use */
1078 int count
; /* leaf live entry count */
1079 int error
; /* error return value */
1080 int forward
; /* sibling block direction */
1081 int i
; /* sibling counter */
1082 xfs_da_blkinfo_t
*info
; /* leaf block header */
1083 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1084 int rval
; /* result from path_shift */
1087 * Check for the degenerate case of the block being over 50% full.
1088 * If so, it's not worth even looking to see if we might be able
1089 * to coalesce with a sibling.
1091 blk
= &state
->path
.blk
[state
->path
.active
- 1];
1092 info
= blk
->bp
->data
;
1093 ASSERT(INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
1094 leaf
= (xfs_dir2_leaf_t
*)info
;
1095 count
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
);
1096 bytes
= (uint
)sizeof(leaf
->hdr
) + count
* (uint
)sizeof(leaf
->ents
[0]);
1097 if (bytes
> (state
->blocksize
>> 1)) {
1099 * Blk over 50%, don't try to join.
1105 * Check for the degenerate case of the block being empty.
1106 * If the block is empty, we'll simply delete it, no need to
1107 * coalesce it with a sibling block. We choose (arbitrarily)
1108 * to merge with the forward block unless it is NULL.
1112 * Make altpath point to the block we want to keep and
1113 * path point to the block we want to drop (this one).
1115 forward
= !INT_ISZERO(info
->forw
, ARCH_CONVERT
);
1116 bcopy(&state
->path
, &state
->altpath
, sizeof(state
->path
));
1117 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
, 0,
1121 *action
= rval
? 2 : 0;
1125 * Examine each sibling block to see if we can coalesce with
1126 * at least 25% free space to spare. We need to figure out
1127 * whether to merge with the forward or the backward block.
1128 * We prefer coalescing with the lower numbered sibling so as
1129 * to shrink a directory over time.
1131 forward
= INT_GET(info
->forw
, ARCH_CONVERT
) < INT_GET(info
->back
, ARCH_CONVERT
);
1132 for (i
= 0, bp
= NULL
; i
< 2; forward
= !forward
, i
++) {
1133 blkno
= forward
?INT_GET( info
->forw
, ARCH_CONVERT
) : INT_GET(info
->back
, ARCH_CONVERT
);
1137 * Read the sibling leaf block.
1140 xfs_da_read_buf(state
->args
->trans
, state
->args
->dp
, blkno
,
1141 -1, &bp
, XFS_DATA_FORK
))) {
1146 * Count bytes in the two blocks combined.
1148 leaf
= (xfs_dir2_leaf_t
*)info
;
1149 count
= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
);
1150 bytes
= state
->blocksize
- (state
->blocksize
>> 2);
1152 ASSERT(INT_GET(leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
1153 count
+= INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
) - INT_GET(leaf
->hdr
.stale
, ARCH_CONVERT
);
1154 bytes
-= count
* (uint
)sizeof(leaf
->ents
[0]);
1156 * Fits with at least 25% to spare.
1160 xfs_da_brelse(state
->args
->trans
, bp
);
1163 * Didn't like either block, give up.
1170 * Done with the sibling leaf block here, drop the dabuf
1171 * so path_shift can get it.
1173 xfs_da_buf_done(bp
);
1175 * Make altpath point to the block we want to keep (the lower
1176 * numbered block) and path point to the block we want to drop.
1178 bcopy(&state
->path
, &state
->altpath
, sizeof(state
->path
));
1179 if (blkno
< blk
->blkno
)
1180 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
, 0,
1183 error
= xfs_da_path_shift(state
, &state
->path
, forward
, 0,
1188 *action
= rval
? 0 : 1;
1193 * Move all the leaf entries from drop_blk to save_blk.
1194 * This is done as part of a join operation.
1197 xfs_dir2_leafn_unbalance(
1198 xfs_da_state_t
*state
, /* cursor */
1199 xfs_da_state_blk_t
*drop_blk
, /* dead block */
1200 xfs_da_state_blk_t
*save_blk
) /* surviving block */
1202 xfs_da_args_t
*args
; /* operation arguments */
1203 xfs_dir2_leaf_t
*drop_leaf
; /* dead leaf structure */
1204 xfs_dir2_leaf_t
*save_leaf
; /* surviving leaf structure */
1207 ASSERT(drop_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1208 ASSERT(save_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1209 drop_leaf
= drop_blk
->bp
->data
;
1210 save_leaf
= save_blk
->bp
->data
;
1211 ASSERT(INT_GET(drop_leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
1212 ASSERT(INT_GET(save_leaf
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
1214 * If there are any stale leaf entries, take this opportunity
1217 if (INT_GET(drop_leaf
->hdr
.stale
, ARCH_CONVERT
))
1218 xfs_dir2_leaf_compact(args
, drop_blk
->bp
);
1219 if (INT_GET(save_leaf
->hdr
.stale
, ARCH_CONVERT
))
1220 xfs_dir2_leaf_compact(args
, save_blk
->bp
);
1222 * Move the entries from drop to the appropriate end of save.
1224 drop_blk
->hashval
= INT_GET(drop_leaf
->ents
[INT_GET(drop_leaf
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1225 if (xfs_dir2_leafn_order(save_blk
->bp
, drop_blk
->bp
))
1226 xfs_dir2_leafn_moveents(args
, drop_blk
->bp
, 0, save_blk
->bp
, 0,
1227 INT_GET(drop_leaf
->hdr
.count
, ARCH_CONVERT
));
1229 xfs_dir2_leafn_moveents(args
, drop_blk
->bp
, 0, save_blk
->bp
,
1230 INT_GET(save_leaf
->hdr
.count
, ARCH_CONVERT
), INT_GET(drop_leaf
->hdr
.count
, ARCH_CONVERT
));
1231 save_blk
->hashval
= INT_GET(save_leaf
->ents
[INT_GET(save_leaf
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1232 xfs_dir2_leafn_check(args
->dp
, save_blk
->bp
);
1236 * Top-level node form directory addname routine.
1239 xfs_dir2_node_addname(
1240 xfs_da_args_t
*args
) /* operation arguments */
1242 xfs_da_state_blk_t
*blk
; /* leaf block for insert */
1243 int error
; /* error return value */
1244 int rval
; /* sub-return value */
1245 xfs_da_state_t
*state
; /* btree cursor */
1247 xfs_dir2_trace_args("node_addname", args
);
1249 * Allocate and initialize the state (btree cursor).
1251 state
= xfs_da_state_alloc();
1253 state
->mp
= args
->dp
->i_mount
;
1254 state
->blocksize
= state
->mp
->m_dirblksize
;
1256 * Look up the name. We're not supposed to find it, but
1257 * this gives us the insertion point.
1259 error
= xfs_da_node_lookup_int(state
, &rval
);
1262 if (rval
!= ENOENT
) {
1266 * Add the data entry to a data block.
1267 * Extravalid is set to a freeblock found by lookup.
1269 rval
= xfs_dir2_node_addname_int(args
,
1270 state
->extravalid
? &state
->extrablk
: NULL
);
1274 blk
= &state
->path
.blk
[state
->path
.active
- 1];
1275 ASSERT(blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1277 * Add the new leaf entry.
1279 rval
= xfs_dir2_leafn_add(blk
->bp
, args
, blk
->index
);
1282 * It worked, fix the hash values up the btree.
1284 if (!args
->justcheck
)
1285 xfs_da_fixhashpath(state
, &state
->path
);
1288 * It didn't work, we need to split the leaf block.
1290 if (args
->total
== 0) {
1291 ASSERT(rval
== ENOSPC
);
1295 * Split the leaf block and insert the new entry.
1297 rval
= xfs_da_split(state
);
1300 xfs_da_state_free(state
);
1306 * Add the data entry for a node-format directory name addition.
1307 * The leaf entry is added in xfs_dir2_leafn_add.
1308 * We may enter with a freespace block that the lookup found.
1310 STATIC
int /* error */
1311 xfs_dir2_node_addname_int(
1312 xfs_da_args_t
*args
, /* operation arguments */
1313 xfs_da_state_blk_t
*fblk
) /* optional freespace block */
1315 xfs_dir2_data_t
*data
; /* data block structure */
1316 xfs_dir2_db_t dbno
; /* data block number */
1317 xfs_dabuf_t
*dbp
; /* data block buffer */
1318 xfs_dir2_data_entry_t
*dep
; /* data entry pointer */
1319 xfs_inode_t
*dp
; /* incore directory inode */
1320 xfs_dir2_data_unused_t
*dup
; /* data unused entry pointer */
1321 int error
; /* error return value */
1322 xfs_dir2_db_t fbno
; /* freespace block number */
1323 xfs_dabuf_t
*fbp
; /* freespace buffer */
1324 int findex
; /* freespace entry index */
1325 xfs_dir2_db_t foundbno
=0; /* found freespace block no */
1326 int foundindex
=0; /* found freespace entry idx */
1327 xfs_dir2_free_t
*free
=NULL
; /* freespace block structure */
1328 xfs_dir2_db_t ifbno
; /* initial freespace block no */
1329 xfs_dir2_db_t lastfbno
=0; /* highest freespace block no */
1330 int length
; /* length of the new entry */
1331 int logfree
; /* need to log free entry */
1332 xfs_mount_t
*mp
; /* filesystem mount point */
1333 int needlog
; /* need to log data header */
1334 int needscan
; /* need to rescan data frees */
1335 xfs_dir2_data_off_t
*tagp
; /* data entry tag pointer */
1336 xfs_trans_t
*tp
; /* transaction pointer */
1341 length
= XFS_DIR2_DATA_ENTSIZE(args
->namelen
);
1343 * If we came in with a freespace block that means that lookup
1344 * found an entry with our hash value. This is the freespace
1345 * block for that data entry.
1350 * Remember initial freespace block number.
1352 ifbno
= fblk
->blkno
;
1354 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
1355 findex
= fblk
->index
;
1357 * This means the free entry showed that the data block had
1358 * space for our entry, so we remembered it.
1359 * Use that data block.
1362 ASSERT(findex
< INT_GET(free
->hdr
.nvalid
, ARCH_CONVERT
));
1363 ASSERT(INT_GET(free
->bests
[findex
], ARCH_CONVERT
) != NULLDATAOFF
);
1364 ASSERT(INT_GET(free
->bests
[findex
], ARCH_CONVERT
) >= length
);
1365 dbno
= INT_GET(free
->hdr
.firstdb
, ARCH_CONVERT
) + findex
;
1368 * The data block looked at didn't have enough room.
1369 * We'll start at the beginning of the freespace entries.
1377 * Didn't come in with a freespace block, so don't have a data block.
1385 * If we don't have a data block yet, we're going to scan the
1386 * freespace blocks looking for one. Figure out what the
1387 * highest freespace block number is.
1390 xfs_fileoff_t fo
; /* freespace block number */
1392 if ((error
= xfs_bmap_last_offset(tp
, dp
, &fo
, XFS_DATA_FORK
)))
1394 lastfbno
= XFS_DIR2_DA_TO_DB(mp
, (xfs_dablk_t
)fo
);
1399 * While we haven't identified a data block, search the freeblock
1400 * data for a good data block. If we find a null freeblock entry,
1401 * indicating a hole in the data blocks, remember that.
1403 while (dbno
== -1) {
1405 * If we don't have a freeblock in hand, get the next one.
1409 * Happens the first time through unless lookup gave
1410 * us a freespace block to start with.
1413 fbno
= XFS_DIR2_FREE_FIRSTDB(mp
);
1415 * If it's ifbno we already looked at it.
1420 * If it's off the end we're done.
1422 if (fbno
>= lastfbno
)
1425 * Read the block. There can be holes in the
1426 * freespace blocks, so this might not succeed.
1427 * This should be really rare, so there's no reason
1430 if ((error
= xfs_da_read_buf(tp
, dp
,
1431 XFS_DIR2_DB_TO_DA(mp
, fbno
), -1, &fbp
,
1439 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
1443 * Look at the current free entry. Is it good enough?
1445 if (INT_GET(free
->bests
[findex
], ARCH_CONVERT
) != NULLDATAOFF
&&
1446 INT_GET(free
->bests
[findex
], ARCH_CONVERT
) >= length
)
1447 dbno
= INT_GET(free
->hdr
.firstdb
, ARCH_CONVERT
) + findex
;
1450 * If we haven't found an empty entry yet, and this
1451 * one is empty, remember this slot.
1453 if (foundindex
== -1 &&
1454 INT_GET(free
->bests
[findex
], ARCH_CONVERT
) == NULLDATAOFF
) {
1455 foundindex
= findex
;
1459 * Are we done with the freeblock?
1461 if (++findex
== INT_GET(free
->hdr
.nvalid
, ARCH_CONVERT
)) {
1463 * If there is space left in this freeblock,
1464 * and we don't have an empty entry yet,
1465 * remember this slot.
1467 if (foundindex
== -1 &&
1468 findex
< XFS_DIR2_MAX_FREE_BESTS(mp
)) {
1469 foundindex
= findex
;
1475 xfs_da_brelse(tp
, fbp
);
1477 if (fblk
&& fblk
->bp
)
1483 * If we don't have a data block, and there's no free slot in a
1484 * freeblock, we need to add a new freeblock.
1486 if (dbno
== -1 && foundindex
== -1) {
1488 * Not allowed to allocate, so return failure.
1490 if (args
->justcheck
|| args
->total
== 0) {
1491 return XFS_ERROR(ENOSPC
);
1494 * Add the new freeblock.
1496 if ((error
= xfs_dir2_grow_inode(args
, XFS_DIR2_FREE_SPACE
,
1501 * Get a buffer for the new block.
1503 if ((error
= xfs_da_get_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, fbno
),
1504 -1, &fbp
, XFS_DATA_FORK
))) {
1507 ASSERT(fbp
!= NULL
);
1509 * Initialize the new block to be empty, and remember
1510 * its first slot as our empty slot.
1513 INT_SET(free
->hdr
.magic
, ARCH_CONVERT
, XFS_DIR2_FREE_MAGIC
);
1514 INT_SET(free
->hdr
.firstdb
, ARCH_CONVERT
, (fbno
- XFS_DIR2_FREE_FIRSTDB(mp
)) *
1515 XFS_DIR2_MAX_FREE_BESTS(mp
));
1516 INT_ZERO(free
->hdr
.nused
, ARCH_CONVERT
);
1517 INT_ZERO(free
->hdr
.nvalid
, ARCH_CONVERT
);
1522 * If we don't have a data block, and we don't have a freeblock buffer
1523 * in hand (we dropped the one with the free slot in it),
1524 * go read the freeblock again.
1526 if (dbno
== -1 && fbp
== NULL
) {
1528 * We're going to use the empty slot we found before.
1530 findex
= foundindex
;
1532 if ((error
= xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, fbno
),
1533 -1, &fbp
, XFS_DATA_FORK
))) {
1536 ASSERT(fbp
!= NULL
);
1538 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
1541 * If we don't have a data block, we need to allocate one and make
1542 * the freespace entries refer to it.
1546 * Not allowed to allocate, return failure.
1548 if (args
->justcheck
|| args
->total
== 0) {
1550 * Drop the freespace buffer unless it came from our
1553 if (fblk
== NULL
|| fblk
->bp
== NULL
)
1554 xfs_da_buf_done(fbp
);
1555 return XFS_ERROR(ENOSPC
);
1558 * Allocate and initialize the new data block.
1560 if ((error
= xfs_dir2_grow_inode(args
, XFS_DIR2_DATA_SPACE
,
1562 (error
= xfs_dir2_data_init(args
, dbno
, &dbp
))) {
1564 * Drop the freespace buffer unless it came from our
1567 if (fblk
== NULL
|| fblk
->bp
== NULL
)
1568 xfs_da_buf_done(fbp
);
1572 * If the freespace entry for this data block is not in the
1573 * freespace block we have in hand, drop the one we have
1574 * and get the right one.
1576 if (XFS_DIR2_DB_TO_FDB(mp
, dbno
) != fbno
) {
1577 xfs_da_brelse(tp
, fbp
);
1578 if (fblk
&& fblk
->bp
)
1580 fbno
= XFS_DIR2_DB_TO_FDB(mp
, dbno
);
1581 if ((error
= xfs_da_read_buf(tp
, dp
,
1582 XFS_DIR2_DB_TO_DA(mp
, fbno
), -1, &fbp
,
1584 xfs_da_buf_done(dbp
);
1587 ASSERT(fbp
!= NULL
);
1589 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
1592 * Set the freespace block index from the data block number.
1594 findex
= XFS_DIR2_DB_TO_FDINDEX(mp
, dbno
);
1596 * If it's after the end of the current entries in the
1597 * freespace block, extend that table.
1599 if (findex
>= INT_GET(free
->hdr
.nvalid
, ARCH_CONVERT
)) {
1600 ASSERT(findex
< XFS_DIR2_MAX_FREE_BESTS(mp
));
1601 INT_SET(free
->hdr
.nvalid
, ARCH_CONVERT
, findex
+ 1);
1603 * Tag new entry so nused will go up.
1605 INT_SET(free
->bests
[findex
], ARCH_CONVERT
, NULLDATAOFF
);
1608 * If this entry was for an empty data block
1609 * (this should always be true) then update the header.
1611 if (INT_GET(free
->bests
[findex
], ARCH_CONVERT
) == NULLDATAOFF
) {
1612 INT_MOD(free
->hdr
.nused
, ARCH_CONVERT
, +1);
1613 xfs_dir2_free_log_header(tp
, fbp
);
1616 * Update the real value in the table.
1617 * We haven't allocated the data entry yet so this will
1621 INT_COPY(free
->bests
[findex
], data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
1625 * We had a data block so we don't have to make a new one.
1629 * If just checking, we succeeded.
1631 if (args
->justcheck
) {
1632 if (fblk
== NULL
|| fblk
->bp
== NULL
)
1633 xfs_da_buf_done(fbp
);
1637 * Read the data block in.
1639 if ((error
= xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, dbno
),
1640 -1, &dbp
, XFS_DATA_FORK
))) {
1641 if (fblk
== NULL
|| fblk
->bp
== NULL
)
1642 xfs_da_buf_done(fbp
);
1648 ASSERT(INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
) >= length
);
1650 * Point to the existing unused space.
1652 dup
= (xfs_dir2_data_unused_t
*)
1653 ((char *)data
+ INT_GET(data
->hdr
.bestfree
[0].offset
, ARCH_CONVERT
));
1654 needscan
= needlog
= 0;
1656 * Mark the first part of the unused space, inuse for us.
1658 xfs_dir2_data_use_free(tp
, dbp
, dup
,
1659 (xfs_dir2_data_aoff_t
)((char *)dup
- (char *)data
), length
,
1660 &needlog
, &needscan
);
1662 * Fill in the new entry and log it.
1664 dep
= (xfs_dir2_data_entry_t
*)dup
;
1665 INT_SET(dep
->inumber
, ARCH_CONVERT
, args
->inumber
);
1666 dep
->namelen
= args
->namelen
;
1667 bcopy(args
->name
, dep
->name
, dep
->namelen
);
1668 tagp
= XFS_DIR2_DATA_ENTRY_TAG_P(dep
);
1669 INT_SET(*tagp
, ARCH_CONVERT
, (xfs_dir2_data_off_t
)((char *)dep
- (char *)data
));
1670 xfs_dir2_data_log_entry(tp
, dbp
, dep
);
1672 * Rescan the block for bestfree if needed.
1675 xfs_dir2_data_freescan(mp
, data
, &needlog
, NULL
);
1677 * Log the data block header if needed.
1680 xfs_dir2_data_log_header(tp
, dbp
);
1682 * If the freespace entry is now wrong, update it.
1684 if (INT_GET(free
->bests
[findex
], ARCH_CONVERT
) != INT_GET(data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
)) {
1685 INT_COPY(free
->bests
[findex
], data
->hdr
.bestfree
[0].length
, ARCH_CONVERT
);
1689 * Log the freespace entry if needed.
1692 xfs_dir2_free_log_bests(tp
, fbp
, findex
, findex
);
1694 * If the caller didn't hand us the freespace block, drop it.
1696 if (fblk
== NULL
|| fblk
->bp
== NULL
)
1697 xfs_da_buf_done(fbp
);
1699 * Return the data block and offset in args, then drop the data block.
1701 args
->blkno
= (xfs_dablk_t
)dbno
;
1702 args
->index
= INT_GET(*tagp
, ARCH_CONVERT
);
1703 xfs_da_buf_done(dbp
);
1708 * Lookup an entry in a node-format directory.
1709 * All the real work happens in xfs_da_node_lookup_int.
1710 * The only real output is the inode number of the entry.
1713 xfs_dir2_node_lookup(
1714 xfs_da_args_t
*args
) /* operation arguments */
1716 int error
; /* error return value */
1717 int i
; /* btree level */
1718 int rval
; /* operation return value */
1719 xfs_da_state_t
*state
; /* btree cursor */
1721 xfs_dir2_trace_args("node_lookup", args
);
1723 * Allocate and initialize the btree cursor.
1725 state
= xfs_da_state_alloc();
1727 state
->mp
= args
->dp
->i_mount
;
1728 state
->blocksize
= state
->mp
->m_dirblksize
;
1730 * Fill in the path to the entry in the cursor.
1732 error
= xfs_da_node_lookup_int(state
, &rval
);
1736 * Release the btree blocks and leaf block.
1738 for (i
= 0; i
< state
->path
.active
; i
++) {
1739 xfs_da_brelse(args
->trans
, state
->path
.blk
[i
].bp
);
1740 state
->path
.blk
[i
].bp
= NULL
;
1743 * Release the data block if we have it.
1745 if (state
->extravalid
&& state
->extrablk
.bp
) {
1746 xfs_da_brelse(args
->trans
, state
->extrablk
.bp
);
1747 state
->extrablk
.bp
= NULL
;
1749 xfs_da_state_free(state
);
1754 * Remove an entry from a node-format directory.
1757 xfs_dir2_node_removename(
1758 xfs_da_args_t
*args
) /* operation arguments */
1760 xfs_da_state_blk_t
*blk
; /* leaf block */
1761 int error
; /* error return value */
1762 int rval
; /* operation return value */
1763 xfs_da_state_t
*state
; /* btree cursor */
1765 xfs_dir2_trace_args("node_removename", args
);
1767 * Allocate and initialize the btree cursor.
1769 state
= xfs_da_state_alloc();
1771 state
->mp
= args
->dp
->i_mount
;
1772 state
->blocksize
= state
->mp
->m_dirblksize
;
1774 * Look up the entry we're deleting, set up the cursor.
1776 error
= xfs_da_node_lookup_int(state
, &rval
);
1781 * Didn't find it, upper layer screwed up.
1783 if (rval
!= EEXIST
) {
1784 xfs_da_state_free(state
);
1787 blk
= &state
->path
.blk
[state
->path
.active
- 1];
1788 ASSERT(blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1789 ASSERT(state
->extravalid
);
1791 * Remove the leaf and data entries.
1792 * Extrablk refers to the data block.
1794 error
= xfs_dir2_leafn_remove(args
, blk
->bp
, blk
->index
,
1795 &state
->extrablk
, &rval
);
1800 * Fix the hash values up the btree.
1802 xfs_da_fixhashpath(state
, &state
->path
);
1804 * If we need to join leaf blocks, do it.
1806 if (rval
&& state
->path
.active
> 1)
1807 error
= xfs_da_join(state
);
1809 * If no errors so far, try conversion to leaf format.
1812 error
= xfs_dir2_node_to_leaf(state
);
1813 xfs_da_state_free(state
);
1818 * Replace an entry's inode number in a node-format directory.
1821 xfs_dir2_node_replace(
1822 xfs_da_args_t
*args
) /* operation arguments */
1824 xfs_da_state_blk_t
*blk
; /* leaf block */
1825 xfs_dir2_data_t
*data
; /* data block structure */
1826 xfs_dir2_data_entry_t
*dep
; /* data entry changed */
1827 int error
; /* error return value */
1828 int i
; /* btree level */
1829 xfs_ino_t inum
; /* new inode number */
1830 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1831 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry being changed */
1832 int rval
; /* internal return value */
1833 xfs_da_state_t
*state
; /* btree cursor */
1835 xfs_dir2_trace_args("node_replace", args
);
1837 * Allocate and initialize the btree cursor.
1839 state
= xfs_da_state_alloc();
1841 state
->mp
= args
->dp
->i_mount
;
1842 state
->blocksize
= state
->mp
->m_dirblksize
;
1843 inum
= args
->inumber
;
1845 * Lookup the entry to change in the btree.
1847 error
= xfs_da_node_lookup_int(state
, &rval
);
1852 * It should be found, since the vnodeops layer has looked it up
1853 * and locked it. But paranoia is good.
1855 if (rval
== EEXIST
) {
1857 * Find the leaf entry.
1859 blk
= &state
->path
.blk
[state
->path
.active
- 1];
1860 ASSERT(blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1861 leaf
= blk
->bp
->data
;
1862 lep
= &leaf
->ents
[blk
->index
];
1863 ASSERT(state
->extravalid
);
1865 * Point to the data entry.
1867 data
= state
->extrablk
.bp
->data
;
1868 ASSERT(INT_GET(data
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_DATA_MAGIC
);
1869 dep
= (xfs_dir2_data_entry_t
*)
1871 XFS_DIR2_DATAPTR_TO_OFF(state
->mp
, INT_GET(lep
->address
, ARCH_CONVERT
)));
1872 ASSERT(inum
!= INT_GET(dep
->inumber
, ARCH_CONVERT
));
1874 * Fill in the new inode number and log the entry.
1876 INT_SET(dep
->inumber
, ARCH_CONVERT
, inum
);
1877 xfs_dir2_data_log_entry(args
->trans
, state
->extrablk
.bp
, dep
);
1881 * Didn't find it, and we're holding a data block. Drop it.
1883 else if (state
->extravalid
) {
1884 xfs_da_brelse(args
->trans
, state
->extrablk
.bp
);
1885 state
->extrablk
.bp
= NULL
;
1888 * Release all the buffers in the cursor.
1890 for (i
= 0; i
< state
->path
.active
; i
++) {
1891 xfs_da_brelse(args
->trans
, state
->path
.blk
[i
].bp
);
1892 state
->path
.blk
[i
].bp
= NULL
;
1894 xfs_da_state_free(state
);
1899 * Trim off a trailing empty freespace block.
1900 * Return (in rvalp) 1 if we did it, 0 if not.
1903 xfs_dir2_node_trim_free(
1904 xfs_da_args_t
*args
, /* operation arguments */
1905 xfs_fileoff_t fo
, /* free block number */
1906 int *rvalp
) /* out: did something */
1908 xfs_dabuf_t
*bp
; /* freespace buffer */
1909 xfs_inode_t
*dp
; /* incore directory inode */
1910 int error
; /* error return code */
1911 xfs_dir2_free_t
*free
; /* freespace structure */
1912 xfs_mount_t
*mp
; /* filesystem mount point */
1913 xfs_trans_t
*tp
; /* transaction pointer */
1919 * Read the freespace block.
1921 if ((error
= xfs_da_read_buf(tp
, dp
, (xfs_dablk_t
)fo
, -1, &bp
,
1926 ASSERT(INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) == XFS_DIR2_FREE_MAGIC
);
1928 * If there are used entries, there's nothing to do.
1930 if (INT_GET(free
->hdr
.nused
, ARCH_CONVERT
) > 0) {
1931 xfs_da_brelse(tp
, bp
);
1936 * Blow the block away.
1939 xfs_dir2_shrink_inode(args
, XFS_DIR2_DA_TO_DB(mp
, (xfs_dablk_t
)fo
),
1942 * Can't fail with ENOSPC since that only happens with no
1943 * space reservation, when breaking up an extent into two
1944 * pieces. This is the last block of an extent.
1946 ASSERT(error
!= ENOSPC
);
1947 xfs_da_brelse(tp
, bp
);
1951 * Return that we succeeded.