]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - fs/xfs/xfs_dir2_node.c
2 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 #include "xfs_types.h"
23 #include "xfs_trans.h"
26 #include "xfs_dmapi.h"
27 #include "xfs_mount.h"
28 #include "xfs_da_btree.h"
29 #include "xfs_bmap_btree.h"
30 #include "xfs_dir2_sf.h"
31 #include "xfs_attr_sf.h"
32 #include "xfs_dinode.h"
33 #include "xfs_inode.h"
35 #include "xfs_dir2_data.h"
36 #include "xfs_dir2_leaf.h"
37 #include "xfs_dir2_block.h"
38 #include "xfs_dir2_node.h"
39 #include "xfs_dir2_trace.h"
40 #include "xfs_error.h"
43 * Function declarations.
45 static void xfs_dir2_free_log_header(xfs_trans_t
*tp
, xfs_dabuf_t
*bp
);
46 static int xfs_dir2_leafn_add(xfs_dabuf_t
*bp
, xfs_da_args_t
*args
, int index
);
48 static void xfs_dir2_leafn_check(xfs_inode_t
*dp
, xfs_dabuf_t
*bp
);
50 #define xfs_dir2_leafn_check(dp, bp)
52 static void xfs_dir2_leafn_moveents(xfs_da_args_t
*args
, xfs_dabuf_t
*bp_s
,
53 int start_s
, xfs_dabuf_t
*bp_d
, int start_d
,
55 static void xfs_dir2_leafn_rebalance(xfs_da_state_t
*state
,
56 xfs_da_state_blk_t
*blk1
,
57 xfs_da_state_blk_t
*blk2
);
58 static int xfs_dir2_leafn_remove(xfs_da_args_t
*args
, xfs_dabuf_t
*bp
,
59 int index
, xfs_da_state_blk_t
*dblk
,
61 static int xfs_dir2_node_addname_int(xfs_da_args_t
*args
,
62 xfs_da_state_blk_t
*fblk
);
65 * Log entries from a freespace block.
68 xfs_dir2_free_log_bests(
69 xfs_trans_t
*tp
, /* transaction pointer */
70 xfs_dabuf_t
*bp
, /* freespace buffer */
71 int first
, /* first entry to log */
72 int last
) /* last entry to log */
74 xfs_dir2_free_t
*free
; /* freespace structure */
77 ASSERT(be32_to_cpu(free
->hdr
.magic
) == XFS_DIR2_FREE_MAGIC
);
78 xfs_da_log_buf(tp
, bp
,
79 (uint
)((char *)&free
->bests
[first
] - (char *)free
),
80 (uint
)((char *)&free
->bests
[last
] - (char *)free
+
81 sizeof(free
->bests
[0]) - 1));
85 * Log header from a freespace block.
88 xfs_dir2_free_log_header(
89 xfs_trans_t
*tp
, /* transaction pointer */
90 xfs_dabuf_t
*bp
) /* freespace buffer */
92 xfs_dir2_free_t
*free
; /* freespace structure */
95 ASSERT(be32_to_cpu(free
->hdr
.magic
) == XFS_DIR2_FREE_MAGIC
);
96 xfs_da_log_buf(tp
, bp
, (uint
)((char *)&free
->hdr
- (char *)free
),
97 (uint
)(sizeof(xfs_dir2_free_hdr_t
) - 1));
101 * Convert a leaf-format directory to a node-format directory.
102 * We need to change the magic number of the leaf block, and copy
103 * the freespace table out of the leaf block into its own block.
106 xfs_dir2_leaf_to_node(
107 xfs_da_args_t
*args
, /* operation arguments */
108 xfs_dabuf_t
*lbp
) /* leaf buffer */
110 xfs_inode_t
*dp
; /* incore directory inode */
111 int error
; /* error return value */
112 xfs_dabuf_t
*fbp
; /* freespace buffer */
113 xfs_dir2_db_t fdb
; /* freespace block number */
114 xfs_dir2_free_t
*free
; /* freespace structure */
115 __be16
*from
; /* pointer to freespace entry */
116 int i
; /* leaf freespace index */
117 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
118 xfs_dir2_leaf_tail_t
*ltp
; /* leaf tail structure */
119 xfs_mount_t
*mp
; /* filesystem mount point */
120 int n
; /* count of live freespc ents */
121 xfs_dir2_data_off_t off
; /* freespace entry value */
122 __be16
*to
; /* pointer to freespace entry */
123 xfs_trans_t
*tp
; /* transaction pointer */
125 xfs_dir2_trace_args_b("leaf_to_node", args
, lbp
);
130 * Add a freespace block to the directory.
132 if ((error
= xfs_dir2_grow_inode(args
, XFS_DIR2_FREE_SPACE
, &fdb
))) {
135 ASSERT(fdb
== XFS_DIR2_FREE_FIRSTDB(mp
));
137 * Get the buffer for the new freespace block.
139 if ((error
= xfs_da_get_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, fdb
), -1, &fbp
,
146 ltp
= XFS_DIR2_LEAF_TAIL_P(mp
, leaf
);
148 * Initialize the freespace block header.
150 free
->hdr
.magic
= cpu_to_be32(XFS_DIR2_FREE_MAGIC
);
151 free
->hdr
.firstdb
= 0;
152 ASSERT(be32_to_cpu(ltp
->bestcount
) <= (uint
)dp
->i_d
.di_size
/ mp
->m_dirblksize
);
153 free
->hdr
.nvalid
= ltp
->bestcount
;
155 * Copy freespace entries from the leaf block to the new block.
156 * Count active entries.
158 for (i
= n
= 0, from
= XFS_DIR2_LEAF_BESTS_P(ltp
), to
= free
->bests
;
159 i
< be32_to_cpu(ltp
->bestcount
); i
++, from
++, to
++) {
160 if ((off
= be16_to_cpu(*from
)) != NULLDATAOFF
)
162 *to
= cpu_to_be16(off
);
164 free
->hdr
.nused
= cpu_to_be32(n
);
165 leaf
->hdr
.info
.magic
= cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
);
169 xfs_dir2_leaf_log_header(tp
, lbp
);
170 xfs_dir2_free_log_header(tp
, fbp
);
171 xfs_dir2_free_log_bests(tp
, fbp
, 0, be32_to_cpu(free
->hdr
.nvalid
) - 1);
172 xfs_da_buf_done(fbp
);
173 xfs_dir2_leafn_check(dp
, lbp
);
178 * Add a leaf entry to a leaf block in a node-form directory.
179 * The other work necessary is done from the caller.
181 static int /* error */
183 xfs_dabuf_t
*bp
, /* leaf buffer */
184 xfs_da_args_t
*args
, /* operation arguments */
185 int index
) /* insertion pt for new entry */
187 int compact
; /* compacting stale leaves */
188 xfs_inode_t
*dp
; /* incore directory inode */
189 int highstale
; /* next stale entry */
190 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
191 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
192 int lfloghigh
; /* high leaf entry logging */
193 int lfloglow
; /* low leaf entry logging */
194 int lowstale
; /* previous stale entry */
195 xfs_mount_t
*mp
; /* filesystem mount point */
196 xfs_trans_t
*tp
; /* transaction pointer */
198 xfs_dir2_trace_args_sb("leafn_add", args
, index
, bp
);
205 * Quick check just to make sure we are not going to index
206 * into other peoples memory
209 return XFS_ERROR(EFSCORRUPTED
);
212 * If there are already the maximum number of leaf entries in
213 * the block, if there are no stale entries it won't fit.
214 * Caller will do a split. If there are stale entries we'll do
218 if (be16_to_cpu(leaf
->hdr
.count
) == XFS_DIR2_MAX_LEAF_ENTS(mp
)) {
219 if (!leaf
->hdr
.stale
)
220 return XFS_ERROR(ENOSPC
);
221 compact
= be16_to_cpu(leaf
->hdr
.stale
) > 1;
224 ASSERT(index
== 0 || be32_to_cpu(leaf
->ents
[index
- 1].hashval
) <= args
->hashval
);
225 ASSERT(index
== be16_to_cpu(leaf
->hdr
.count
) ||
226 be32_to_cpu(leaf
->ents
[index
].hashval
) >= args
->hashval
);
232 * Compact out all but one stale leaf entry. Leaves behind
233 * the entry closest to index.
236 xfs_dir2_leaf_compact_x1(bp
, &index
, &lowstale
, &highstale
,
237 &lfloglow
, &lfloghigh
);
240 * Set impossible logging indices for this case.
242 else if (leaf
->hdr
.stale
) {
243 lfloglow
= be16_to_cpu(leaf
->hdr
.count
);
247 * No stale entries, just insert a space for the new entry.
249 if (!leaf
->hdr
.stale
) {
250 lep
= &leaf
->ents
[index
];
251 if (index
< be16_to_cpu(leaf
->hdr
.count
))
252 memmove(lep
+ 1, lep
,
253 (be16_to_cpu(leaf
->hdr
.count
) - index
) * sizeof(*lep
));
255 lfloghigh
= be16_to_cpu(leaf
->hdr
.count
);
256 be16_add(&leaf
->hdr
.count
, 1);
259 * There are stale entries. We'll use one for the new entry.
263 * If we didn't do a compact then we need to figure out
264 * which stale entry will be used.
268 * Find first stale entry before our insertion point.
270 for (lowstale
= index
- 1;
272 be32_to_cpu(leaf
->ents
[lowstale
].address
) !=
273 XFS_DIR2_NULL_DATAPTR
;
277 * Find next stale entry after insertion point.
278 * Stop looking if the answer would be worse than
279 * lowstale already found.
281 for (highstale
= index
;
282 highstale
< be16_to_cpu(leaf
->hdr
.count
) &&
283 be32_to_cpu(leaf
->ents
[highstale
].address
) !=
284 XFS_DIR2_NULL_DATAPTR
&&
286 index
- lowstale
- 1 >= highstale
- index
);
291 * Using the low stale entry.
292 * Shift entries up toward the stale slot.
295 (highstale
== be16_to_cpu(leaf
->hdr
.count
) ||
296 index
- lowstale
- 1 < highstale
- index
)) {
297 ASSERT(be32_to_cpu(leaf
->ents
[lowstale
].address
) ==
298 XFS_DIR2_NULL_DATAPTR
);
299 ASSERT(index
- lowstale
- 1 >= 0);
300 if (index
- lowstale
- 1 > 0)
301 memmove(&leaf
->ents
[lowstale
],
302 &leaf
->ents
[lowstale
+ 1],
303 (index
- lowstale
- 1) * sizeof(*lep
));
304 lep
= &leaf
->ents
[index
- 1];
305 lfloglow
= MIN(lowstale
, lfloglow
);
306 lfloghigh
= MAX(index
- 1, lfloghigh
);
309 * Using the high stale entry.
310 * Shift entries down toward the stale slot.
313 ASSERT(be32_to_cpu(leaf
->ents
[highstale
].address
) ==
314 XFS_DIR2_NULL_DATAPTR
);
315 ASSERT(highstale
- index
>= 0);
316 if (highstale
- index
> 0)
317 memmove(&leaf
->ents
[index
+ 1],
319 (highstale
- index
) * sizeof(*lep
));
320 lep
= &leaf
->ents
[index
];
321 lfloglow
= MIN(index
, lfloglow
);
322 lfloghigh
= MAX(highstale
, lfloghigh
);
324 be16_add(&leaf
->hdr
.stale
, -1);
327 * Insert the new entry, log everything.
329 lep
->hashval
= cpu_to_be32(args
->hashval
);
330 lep
->address
= cpu_to_be32(XFS_DIR2_DB_OFF_TO_DATAPTR(mp
,
331 args
->blkno
, args
->index
));
332 xfs_dir2_leaf_log_header(tp
, bp
);
333 xfs_dir2_leaf_log_ents(tp
, bp
, lfloglow
, lfloghigh
);
334 xfs_dir2_leafn_check(dp
, bp
);
340 * Check internal consistency of a leafn block.
343 xfs_dir2_leafn_check(
344 xfs_inode_t
*dp
, /* incore directory inode */
345 xfs_dabuf_t
*bp
) /* leaf buffer */
347 int i
; /* leaf index */
348 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
349 xfs_mount_t
*mp
; /* filesystem mount point */
350 int stale
; /* count of stale leaves */
354 ASSERT(be16_to_cpu(leaf
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
355 ASSERT(be16_to_cpu(leaf
->hdr
.count
) <= XFS_DIR2_MAX_LEAF_ENTS(mp
));
356 for (i
= stale
= 0; i
< be16_to_cpu(leaf
->hdr
.count
); i
++) {
357 if (i
+ 1 < be16_to_cpu(leaf
->hdr
.count
)) {
358 ASSERT(be32_to_cpu(leaf
->ents
[i
].hashval
) <=
359 be32_to_cpu(leaf
->ents
[i
+ 1].hashval
));
361 if (be32_to_cpu(leaf
->ents
[i
].address
) == XFS_DIR2_NULL_DATAPTR
)
364 ASSERT(be16_to_cpu(leaf
->hdr
.stale
) == stale
);
369 * Return the last hash value in the leaf.
370 * Stale entries are ok.
372 xfs_dahash_t
/* hash value */
373 xfs_dir2_leafn_lasthash(
374 xfs_dabuf_t
*bp
, /* leaf buffer */
375 int *count
) /* count of entries in leaf */
377 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
380 ASSERT(be16_to_cpu(leaf
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
382 *count
= be16_to_cpu(leaf
->hdr
.count
);
383 if (!leaf
->hdr
.count
)
385 return be32_to_cpu(leaf
->ents
[be16_to_cpu(leaf
->hdr
.count
) - 1].hashval
);
389 * Look up a leaf entry in a node-format leaf block.
390 * If this is an addname then the extrablk in state is a freespace block,
391 * otherwise it's a data block.
394 xfs_dir2_leafn_lookup_int(
395 xfs_dabuf_t
*bp
, /* leaf buffer */
396 xfs_da_args_t
*args
, /* operation arguments */
397 int *indexp
, /* out: leaf entry index */
398 xfs_da_state_t
*state
) /* state to fill in */
400 xfs_dabuf_t
*curbp
; /* current data/free buffer */
401 xfs_dir2_db_t curdb
; /* current data block number */
402 xfs_dir2_db_t curfdb
; /* current free block number */
403 xfs_dir2_data_entry_t
*dep
; /* data block entry */
404 xfs_inode_t
*dp
; /* incore directory inode */
405 int error
; /* error return value */
406 int fi
; /* free entry index */
407 xfs_dir2_free_t
*free
=NULL
; /* free block structure */
408 int index
; /* leaf entry index */
409 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
410 int length
=0; /* length of new data entry */
411 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
412 xfs_mount_t
*mp
; /* filesystem mount point */
413 xfs_dir2_db_t newdb
; /* new data block number */
414 xfs_dir2_db_t newfdb
; /* new free block number */
415 xfs_trans_t
*tp
; /* transaction pointer */
421 ASSERT(be16_to_cpu(leaf
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
423 ASSERT(be16_to_cpu(leaf
->hdr
.count
) > 0);
425 xfs_dir2_leafn_check(dp
, bp
);
427 * Look up the hash value in the leaf entries.
429 index
= xfs_dir2_leaf_search_hash(args
, bp
);
431 * Do we have a buffer coming in?
433 if (state
->extravalid
)
434 curbp
= state
->extrablk
.bp
;
438 * For addname, it's a free block buffer, get the block number.
441 curfdb
= curbp
? state
->extrablk
.blkno
: -1;
443 length
= XFS_DIR2_DATA_ENTSIZE(args
->namelen
);
444 if ((free
= (curbp
? curbp
->data
: NULL
)))
445 ASSERT(be32_to_cpu(free
->hdr
.magic
) == XFS_DIR2_FREE_MAGIC
);
448 * For others, it's a data block buffer, get the block number.
452 curdb
= curbp
? state
->extrablk
.blkno
: -1;
455 * Loop over leaf entries with the right hash value.
457 for (lep
= &leaf
->ents
[index
];
458 index
< be16_to_cpu(leaf
->hdr
.count
) && be32_to_cpu(lep
->hashval
) == args
->hashval
;
461 * Skip stale leaf entries.
463 if (be32_to_cpu(lep
->address
) == XFS_DIR2_NULL_DATAPTR
)
466 * Pull the data block number from the entry.
468 newdb
= XFS_DIR2_DATAPTR_TO_DB(mp
, be32_to_cpu(lep
->address
));
470 * For addname, we're looking for a place to put the new entry.
471 * We want to use a data block with an entry of equal
472 * hash value to ours if there is one with room.
476 * If this block isn't the data block we already have
477 * in hand, take a look at it.
479 if (newdb
!= curdb
) {
482 * Convert the data block to the free block
483 * holding its freespace information.
485 newfdb
= XFS_DIR2_DB_TO_FDB(mp
, newdb
);
487 * If it's not the one we have in hand,
490 if (newfdb
!= curfdb
) {
492 * If we had one before, drop it.
495 xfs_da_brelse(tp
, curbp
);
497 * Read the free block.
499 if ((error
= xfs_da_read_buf(tp
, dp
,
500 XFS_DIR2_DB_TO_DA(mp
,
507 ASSERT(be32_to_cpu(free
->hdr
.magic
) ==
508 XFS_DIR2_FREE_MAGIC
);
509 ASSERT((be32_to_cpu(free
->hdr
.firstdb
) %
510 XFS_DIR2_MAX_FREE_BESTS(mp
)) ==
512 ASSERT(be32_to_cpu(free
->hdr
.firstdb
) <= curdb
);
514 be32_to_cpu(free
->hdr
.firstdb
) +
515 be32_to_cpu(free
->hdr
.nvalid
));
518 * Get the index for our entry.
520 fi
= XFS_DIR2_DB_TO_FDINDEX(mp
, curdb
);
522 * If it has room, return it.
524 if (unlikely(be16_to_cpu(free
->bests
[fi
]) == NULLDATAOFF
)) {
525 XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int",
526 XFS_ERRLEVEL_LOW
, mp
);
527 if (curfdb
!= newfdb
)
528 xfs_da_brelse(tp
, curbp
);
529 return XFS_ERROR(EFSCORRUPTED
);
532 if (be16_to_cpu(free
->bests
[fi
]) >= length
) {
534 state
->extravalid
= 1;
535 state
->extrablk
.bp
= curbp
;
536 state
->extrablk
.blkno
= curfdb
;
537 state
->extrablk
.index
= fi
;
538 state
->extrablk
.magic
=
540 ASSERT(args
->oknoent
);
541 return XFS_ERROR(ENOENT
);
546 * Not adding a new entry, so we really want to find
547 * the name given to us.
551 * If it's a different data block, go get it.
553 if (newdb
!= curdb
) {
555 * If we had a block before, drop it.
558 xfs_da_brelse(tp
, curbp
);
560 * Read the data block.
563 xfs_da_read_buf(tp
, dp
,
564 XFS_DIR2_DB_TO_DA(mp
, newdb
), -1,
565 &curbp
, XFS_DATA_FORK
))) {
568 xfs_dir2_data_check(dp
, curbp
);
572 * Point to the data entry.
574 dep
= (xfs_dir2_data_entry_t
*)
575 ((char *)curbp
->data
+
576 XFS_DIR2_DATAPTR_TO_OFF(mp
, be32_to_cpu(lep
->address
)));
578 * Compare the entry, return it if it matches.
580 if (dep
->namelen
== args
->namelen
&&
581 dep
->name
[0] == args
->name
[0] &&
582 memcmp(dep
->name
, args
->name
, args
->namelen
) == 0) {
583 args
->inumber
= be64_to_cpu(dep
->inumber
);
585 state
->extravalid
= 1;
586 state
->extrablk
.bp
= curbp
;
587 state
->extrablk
.blkno
= curdb
;
588 state
->extrablk
.index
=
590 (char *)curbp
->data
);
591 state
->extrablk
.magic
= XFS_DIR2_DATA_MAGIC
;
592 return XFS_ERROR(EEXIST
);
597 * Didn't find a match.
598 * If we are holding a buffer, give it back in case our caller
601 if ((state
->extravalid
= (curbp
!= NULL
))) {
602 state
->extrablk
.bp
= curbp
;
603 state
->extrablk
.index
= -1;
605 * For addname, giving back a free block.
608 state
->extrablk
.blkno
= curfdb
;
609 state
->extrablk
.magic
= XFS_DIR2_FREE_MAGIC
;
612 * For other callers, giving back a data block.
615 state
->extrablk
.blkno
= curdb
;
616 state
->extrablk
.magic
= XFS_DIR2_DATA_MAGIC
;
620 * Return the final index, that will be the insertion point.
623 ASSERT(index
== be16_to_cpu(leaf
->hdr
.count
) || args
->oknoent
);
624 return XFS_ERROR(ENOENT
);
628 * Move count leaf entries from source to destination leaf.
629 * Log entries and headers. Stale entries are preserved.
632 xfs_dir2_leafn_moveents(
633 xfs_da_args_t
*args
, /* operation arguments */
634 xfs_dabuf_t
*bp_s
, /* source leaf buffer */
635 int start_s
, /* source leaf index */
636 xfs_dabuf_t
*bp_d
, /* destination leaf buffer */
637 int start_d
, /* destination leaf index */
638 int count
) /* count of leaves to copy */
640 xfs_dir2_leaf_t
*leaf_d
; /* destination leaf structure */
641 xfs_dir2_leaf_t
*leaf_s
; /* source leaf structure */
642 int stale
; /* count stale leaves copied */
643 xfs_trans_t
*tp
; /* transaction pointer */
645 xfs_dir2_trace_args_bibii("leafn_moveents", args
, bp_s
, start_s
, bp_d
,
648 * Silently return if nothing to do.
657 * If the destination index is not the end of the current
658 * destination leaf entries, open up a hole in the destination
659 * to hold the new entries.
661 if (start_d
< be16_to_cpu(leaf_d
->hdr
.count
)) {
662 memmove(&leaf_d
->ents
[start_d
+ count
], &leaf_d
->ents
[start_d
],
663 (be16_to_cpu(leaf_d
->hdr
.count
) - start_d
) *
664 sizeof(xfs_dir2_leaf_entry_t
));
665 xfs_dir2_leaf_log_ents(tp
, bp_d
, start_d
+ count
,
666 count
+ be16_to_cpu(leaf_d
->hdr
.count
) - 1);
669 * If the source has stale leaves, count the ones in the copy range
670 * so we can update the header correctly.
672 if (leaf_s
->hdr
.stale
) {
673 int i
; /* temp leaf index */
675 for (i
= start_s
, stale
= 0; i
< start_s
+ count
; i
++) {
676 if (be32_to_cpu(leaf_s
->ents
[i
].address
) == XFS_DIR2_NULL_DATAPTR
)
682 * Copy the leaf entries from source to destination.
684 memcpy(&leaf_d
->ents
[start_d
], &leaf_s
->ents
[start_s
],
685 count
* sizeof(xfs_dir2_leaf_entry_t
));
686 xfs_dir2_leaf_log_ents(tp
, bp_d
, start_d
, start_d
+ count
- 1);
688 * If there are source entries after the ones we copied,
689 * delete the ones we copied by sliding the next ones down.
691 if (start_s
+ count
< be16_to_cpu(leaf_s
->hdr
.count
)) {
692 memmove(&leaf_s
->ents
[start_s
], &leaf_s
->ents
[start_s
+ count
],
693 count
* sizeof(xfs_dir2_leaf_entry_t
));
694 xfs_dir2_leaf_log_ents(tp
, bp_s
, start_s
, start_s
+ count
- 1);
697 * Update the headers and log them.
699 be16_add(&leaf_s
->hdr
.count
, -(count
));
700 be16_add(&leaf_s
->hdr
.stale
, -(stale
));
701 be16_add(&leaf_d
->hdr
.count
, count
);
702 be16_add(&leaf_d
->hdr
.stale
, stale
);
703 xfs_dir2_leaf_log_header(tp
, bp_s
);
704 xfs_dir2_leaf_log_header(tp
, bp_d
);
705 xfs_dir2_leafn_check(args
->dp
, bp_s
);
706 xfs_dir2_leafn_check(args
->dp
, bp_d
);
710 * Determine the sort order of two leaf blocks.
711 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
714 xfs_dir2_leafn_order(
715 xfs_dabuf_t
*leaf1_bp
, /* leaf1 buffer */
716 xfs_dabuf_t
*leaf2_bp
) /* leaf2 buffer */
718 xfs_dir2_leaf_t
*leaf1
; /* leaf1 structure */
719 xfs_dir2_leaf_t
*leaf2
; /* leaf2 structure */
721 leaf1
= leaf1_bp
->data
;
722 leaf2
= leaf2_bp
->data
;
723 ASSERT(be16_to_cpu(leaf1
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
724 ASSERT(be16_to_cpu(leaf2
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
725 if (be16_to_cpu(leaf1
->hdr
.count
) > 0 &&
726 be16_to_cpu(leaf2
->hdr
.count
) > 0 &&
727 (be32_to_cpu(leaf2
->ents
[0].hashval
) < be32_to_cpu(leaf1
->ents
[0].hashval
) ||
728 be32_to_cpu(leaf2
->ents
[be16_to_cpu(leaf2
->hdr
.count
) - 1].hashval
) <
729 be32_to_cpu(leaf1
->ents
[be16_to_cpu(leaf1
->hdr
.count
) - 1].hashval
)))
735 * Rebalance leaf entries between two leaf blocks.
736 * This is actually only called when the second block is new,
737 * though the code deals with the general case.
738 * A new entry will be inserted in one of the blocks, and that
739 * entry is taken into account when balancing.
742 xfs_dir2_leafn_rebalance(
743 xfs_da_state_t
*state
, /* btree cursor */
744 xfs_da_state_blk_t
*blk1
, /* first btree block */
745 xfs_da_state_blk_t
*blk2
) /* second btree block */
747 xfs_da_args_t
*args
; /* operation arguments */
748 int count
; /* count (& direction) leaves */
749 int isleft
; /* new goes in left leaf */
750 xfs_dir2_leaf_t
*leaf1
; /* first leaf structure */
751 xfs_dir2_leaf_t
*leaf2
; /* second leaf structure */
752 int mid
; /* midpoint leaf index */
754 int oldstale
; /* old count of stale leaves */
756 int oldsum
; /* old total leaf count */
757 int swap
; /* swapped leaf blocks */
761 * If the block order is wrong, swap the arguments.
763 if ((swap
= xfs_dir2_leafn_order(blk1
->bp
, blk2
->bp
))) {
764 xfs_da_state_blk_t
*tmp
; /* temp for block swap */
770 leaf1
= blk1
->bp
->data
;
771 leaf2
= blk2
->bp
->data
;
772 oldsum
= be16_to_cpu(leaf1
->hdr
.count
) + be16_to_cpu(leaf2
->hdr
.count
);
774 oldstale
= be16_to_cpu(leaf1
->hdr
.stale
) + be16_to_cpu(leaf2
->hdr
.stale
);
778 * If the old leaf count was odd then the new one will be even,
779 * so we need to divide the new count evenly.
782 xfs_dahash_t midhash
; /* middle entry hash value */
784 if (mid
>= be16_to_cpu(leaf1
->hdr
.count
))
785 midhash
= be32_to_cpu(leaf2
->ents
[mid
- be16_to_cpu(leaf1
->hdr
.count
)].hashval
);
787 midhash
= be32_to_cpu(leaf1
->ents
[mid
].hashval
);
788 isleft
= args
->hashval
<= midhash
;
791 * If the old count is even then the new count is odd, so there's
792 * no preferred side for the new entry.
798 * Calculate moved entry count. Positive means left-to-right,
799 * negative means right-to-left. Then move the entries.
801 count
= be16_to_cpu(leaf1
->hdr
.count
) - mid
+ (isleft
== 0);
803 xfs_dir2_leafn_moveents(args
, blk1
->bp
,
804 be16_to_cpu(leaf1
->hdr
.count
) - count
, blk2
->bp
, 0, count
);
806 xfs_dir2_leafn_moveents(args
, blk2
->bp
, 0, blk1
->bp
,
807 be16_to_cpu(leaf1
->hdr
.count
), count
);
808 ASSERT(be16_to_cpu(leaf1
->hdr
.count
) + be16_to_cpu(leaf2
->hdr
.count
) == oldsum
);
809 ASSERT(be16_to_cpu(leaf1
->hdr
.stale
) + be16_to_cpu(leaf2
->hdr
.stale
) == oldstale
);
811 * Mark whether we're inserting into the old or new leaf.
813 if (be16_to_cpu(leaf1
->hdr
.count
) < be16_to_cpu(leaf2
->hdr
.count
))
814 state
->inleaf
= swap
;
815 else if (be16_to_cpu(leaf1
->hdr
.count
) > be16_to_cpu(leaf2
->hdr
.count
))
816 state
->inleaf
= !swap
;
819 swap
^ (blk1
->index
<= be16_to_cpu(leaf1
->hdr
.count
));
821 * Adjust the expected index for insertion.
824 blk2
->index
= blk1
->index
- be16_to_cpu(leaf1
->hdr
.count
);
827 * Finally sanity check just to make sure we are not returning a negative index
829 if(blk2
->index
< 0) {
833 "xfs_dir2_leafn_rebalance: picked the wrong leaf? reverting original leaf: "
840 * Remove an entry from a node directory.
841 * This removes the leaf entry and the data entry,
842 * and updates the free block if necessary.
844 static int /* error */
845 xfs_dir2_leafn_remove(
846 xfs_da_args_t
*args
, /* operation arguments */
847 xfs_dabuf_t
*bp
, /* leaf buffer */
848 int index
, /* leaf entry index */
849 xfs_da_state_blk_t
*dblk
, /* data block */
850 int *rval
) /* resulting block needs join */
852 xfs_dir2_data_t
*data
; /* data block structure */
853 xfs_dir2_db_t db
; /* data block number */
854 xfs_dabuf_t
*dbp
; /* data block buffer */
855 xfs_dir2_data_entry_t
*dep
; /* data block entry */
856 xfs_inode_t
*dp
; /* incore directory inode */
857 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
858 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry */
859 int longest
; /* longest data free entry */
860 int off
; /* data block entry offset */
861 xfs_mount_t
*mp
; /* filesystem mount point */
862 int needlog
; /* need to log data header */
863 int needscan
; /* need to rescan data frees */
864 xfs_trans_t
*tp
; /* transaction pointer */
866 xfs_dir2_trace_args_sb("leafn_remove", args
, index
, bp
);
871 ASSERT(be16_to_cpu(leaf
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
873 * Point to the entry we're removing.
875 lep
= &leaf
->ents
[index
];
877 * Extract the data block and offset from the entry.
879 db
= XFS_DIR2_DATAPTR_TO_DB(mp
, be32_to_cpu(lep
->address
));
880 ASSERT(dblk
->blkno
== db
);
881 off
= XFS_DIR2_DATAPTR_TO_OFF(mp
, be32_to_cpu(lep
->address
));
882 ASSERT(dblk
->index
== off
);
884 * Kill the leaf entry by marking it stale.
885 * Log the leaf block changes.
887 be16_add(&leaf
->hdr
.stale
, 1);
888 xfs_dir2_leaf_log_header(tp
, bp
);
889 lep
->address
= cpu_to_be32(XFS_DIR2_NULL_DATAPTR
);
890 xfs_dir2_leaf_log_ents(tp
, bp
, index
, index
);
892 * Make the data entry free. Keep track of the longest freespace
893 * in the data block in case it changes.
897 dep
= (xfs_dir2_data_entry_t
*)((char *)data
+ off
);
898 longest
= be16_to_cpu(data
->hdr
.bestfree
[0].length
);
899 needlog
= needscan
= 0;
900 xfs_dir2_data_make_free(tp
, dbp
, off
,
901 XFS_DIR2_DATA_ENTSIZE(dep
->namelen
), &needlog
, &needscan
);
903 * Rescan the data block freespaces for bestfree.
904 * Log the data block header if needed.
907 xfs_dir2_data_freescan(mp
, data
, &needlog
, NULL
);
909 xfs_dir2_data_log_header(tp
, dbp
);
910 xfs_dir2_data_check(dp
, dbp
);
912 * If the longest data block freespace changes, need to update
913 * the corresponding freeblock entry.
915 if (longest
< be16_to_cpu(data
->hdr
.bestfree
[0].length
)) {
916 int error
; /* error return value */
917 xfs_dabuf_t
*fbp
; /* freeblock buffer */
918 xfs_dir2_db_t fdb
; /* freeblock block number */
919 int findex
; /* index in freeblock entries */
920 xfs_dir2_free_t
*free
; /* freeblock structure */
921 int logfree
; /* need to log free entry */
924 * Convert the data block number to a free block,
925 * read in the free block.
927 fdb
= XFS_DIR2_DB_TO_FDB(mp
, db
);
928 if ((error
= xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, fdb
),
929 -1, &fbp
, XFS_DATA_FORK
))) {
933 ASSERT(be32_to_cpu(free
->hdr
.magic
) == XFS_DIR2_FREE_MAGIC
);
934 ASSERT(be32_to_cpu(free
->hdr
.firstdb
) ==
935 XFS_DIR2_MAX_FREE_BESTS(mp
) *
936 (fdb
- XFS_DIR2_FREE_FIRSTDB(mp
)));
938 * Calculate which entry we need to fix.
940 findex
= XFS_DIR2_DB_TO_FDINDEX(mp
, db
);
941 longest
= be16_to_cpu(data
->hdr
.bestfree
[0].length
);
943 * If the data block is now empty we can get rid of it
946 if (longest
== mp
->m_dirblksize
- (uint
)sizeof(data
->hdr
)) {
948 * Try to punch out the data block.
950 error
= xfs_dir2_shrink_inode(args
, db
, dbp
);
956 * We can get ENOSPC if there's no space reservation.
957 * In this case just drop the buffer and some one else
958 * will eventually get rid of the empty block.
960 else if (error
== ENOSPC
&& args
->total
== 0)
961 xfs_da_buf_done(dbp
);
966 * If we got rid of the data block, we can eliminate that entry
971 * One less used entry in the free table.
973 be32_add(&free
->hdr
.nused
, -1);
974 xfs_dir2_free_log_header(tp
, fbp
);
976 * If this was the last entry in the table, we can
977 * trim the table size back. There might be other
978 * entries at the end referring to non-existent
979 * data blocks, get those too.
981 if (findex
== be32_to_cpu(free
->hdr
.nvalid
) - 1) {
982 int i
; /* free entry index */
985 i
>= 0 && be16_to_cpu(free
->bests
[i
]) == NULLDATAOFF
;
988 free
->hdr
.nvalid
= cpu_to_be32(i
+ 1);
992 * Not the last entry, just punch it out.
995 free
->bests
[findex
] = cpu_to_be16(NULLDATAOFF
);
999 * If there are no useful entries left in the block,
1000 * get rid of the block if we can.
1002 if (!free
->hdr
.nused
) {
1003 error
= xfs_dir2_shrink_inode(args
, fdb
, fbp
);
1007 } else if (error
!= ENOSPC
|| args
->total
!= 0)
1010 * It's possible to get ENOSPC if there is no
1011 * space reservation. In this case some one
1012 * else will eventually get rid of this block.
1017 * Data block is not empty, just set the free entry to
1021 free
->bests
[findex
] = cpu_to_be16(longest
);
1025 * Log the free entry that changed, unless we got rid of it.
1028 xfs_dir2_free_log_bests(tp
, fbp
, findex
, findex
);
1030 * Drop the buffer if we still have it.
1033 xfs_da_buf_done(fbp
);
1035 xfs_dir2_leafn_check(dp
, bp
);
1037 * Return indication of whether this leaf block is emtpy enough
1038 * to justify trying to join it with a neighbor.
1041 ((uint
)sizeof(leaf
->hdr
) +
1042 (uint
)sizeof(leaf
->ents
[0]) *
1043 (be16_to_cpu(leaf
->hdr
.count
) - be16_to_cpu(leaf
->hdr
.stale
))) <
1049 * Split the leaf entries in the old block into old and new blocks.
1052 xfs_dir2_leafn_split(
1053 xfs_da_state_t
*state
, /* btree cursor */
1054 xfs_da_state_blk_t
*oldblk
, /* original block */
1055 xfs_da_state_blk_t
*newblk
) /* newly created block */
1057 xfs_da_args_t
*args
; /* operation arguments */
1058 xfs_dablk_t blkno
; /* new leaf block number */
1059 int error
; /* error return value */
1060 xfs_mount_t
*mp
; /* filesystem mount point */
1063 * Allocate space for a new leaf node.
1066 mp
= args
->dp
->i_mount
;
1067 ASSERT(args
!= NULL
);
1068 ASSERT(oldblk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1069 error
= xfs_da_grow_inode(args
, &blkno
);
1074 * Initialize the new leaf block.
1076 error
= xfs_dir2_leaf_init(args
, XFS_DIR2_DA_TO_DB(mp
, blkno
),
1077 &newblk
->bp
, XFS_DIR2_LEAFN_MAGIC
);
1081 newblk
->blkno
= blkno
;
1082 newblk
->magic
= XFS_DIR2_LEAFN_MAGIC
;
1084 * Rebalance the entries across the two leaves, link the new
1085 * block into the leaves.
1087 xfs_dir2_leafn_rebalance(state
, oldblk
, newblk
);
1088 error
= xfs_da_blk_link(state
, oldblk
, newblk
);
1093 * Insert the new entry in the correct block.
1096 error
= xfs_dir2_leafn_add(oldblk
->bp
, args
, oldblk
->index
);
1098 error
= xfs_dir2_leafn_add(newblk
->bp
, args
, newblk
->index
);
1100 * Update last hashval in each block since we added the name.
1102 oldblk
->hashval
= xfs_dir2_leafn_lasthash(oldblk
->bp
, NULL
);
1103 newblk
->hashval
= xfs_dir2_leafn_lasthash(newblk
->bp
, NULL
);
1104 xfs_dir2_leafn_check(args
->dp
, oldblk
->bp
);
1105 xfs_dir2_leafn_check(args
->dp
, newblk
->bp
);
1110 * Check a leaf block and its neighbors to see if the block should be
1111 * collapsed into one or the other neighbor. Always keep the block
1112 * with the smaller block number.
1113 * If the current block is over 50% full, don't try to join it, return 0.
1114 * If the block is empty, fill in the state structure and return 2.
1115 * If it can be collapsed, fill in the state structure and return 1.
1116 * If nothing can be done, return 0.
1119 xfs_dir2_leafn_toosmall(
1120 xfs_da_state_t
*state
, /* btree cursor */
1121 int *action
) /* resulting action to take */
1123 xfs_da_state_blk_t
*blk
; /* leaf block */
1124 xfs_dablk_t blkno
; /* leaf block number */
1125 xfs_dabuf_t
*bp
; /* leaf buffer */
1126 int bytes
; /* bytes in use */
1127 int count
; /* leaf live entry count */
1128 int error
; /* error return value */
1129 int forward
; /* sibling block direction */
1130 int i
; /* sibling counter */
1131 xfs_da_blkinfo_t
*info
; /* leaf block header */
1132 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1133 int rval
; /* result from path_shift */
1136 * Check for the degenerate case of the block being over 50% full.
1137 * If so, it's not worth even looking to see if we might be able
1138 * to coalesce with a sibling.
1140 blk
= &state
->path
.blk
[state
->path
.active
- 1];
1141 info
= blk
->bp
->data
;
1142 ASSERT(be16_to_cpu(info
->magic
) == XFS_DIR2_LEAFN_MAGIC
);
1143 leaf
= (xfs_dir2_leaf_t
*)info
;
1144 count
= be16_to_cpu(leaf
->hdr
.count
) - be16_to_cpu(leaf
->hdr
.stale
);
1145 bytes
= (uint
)sizeof(leaf
->hdr
) + count
* (uint
)sizeof(leaf
->ents
[0]);
1146 if (bytes
> (state
->blocksize
>> 1)) {
1148 * Blk over 50%, don't try to join.
1154 * Check for the degenerate case of the block being empty.
1155 * If the block is empty, we'll simply delete it, no need to
1156 * coalesce it with a sibling block. We choose (arbitrarily)
1157 * to merge with the forward block unless it is NULL.
1161 * Make altpath point to the block we want to keep and
1162 * path point to the block we want to drop (this one).
1164 forward
= (info
->forw
!= 0);
1165 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
1166 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
, 0,
1170 *action
= rval
? 2 : 0;
1174 * Examine each sibling block to see if we can coalesce with
1175 * at least 25% free space to spare. We need to figure out
1176 * whether to merge with the forward or the backward block.
1177 * We prefer coalescing with the lower numbered sibling so as
1178 * to shrink a directory over time.
1180 forward
= be32_to_cpu(info
->forw
) < be32_to_cpu(info
->back
);
1181 for (i
= 0, bp
= NULL
; i
< 2; forward
= !forward
, i
++) {
1182 blkno
= forward
? be32_to_cpu(info
->forw
) : be32_to_cpu(info
->back
);
1186 * Read the sibling leaf block.
1189 xfs_da_read_buf(state
->args
->trans
, state
->args
->dp
, blkno
,
1190 -1, &bp
, XFS_DATA_FORK
))) {
1195 * Count bytes in the two blocks combined.
1197 leaf
= (xfs_dir2_leaf_t
*)info
;
1198 count
= be16_to_cpu(leaf
->hdr
.count
) - be16_to_cpu(leaf
->hdr
.stale
);
1199 bytes
= state
->blocksize
- (state
->blocksize
>> 2);
1201 ASSERT(be16_to_cpu(leaf
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
1202 count
+= be16_to_cpu(leaf
->hdr
.count
) - be16_to_cpu(leaf
->hdr
.stale
);
1203 bytes
-= count
* (uint
)sizeof(leaf
->ents
[0]);
1205 * Fits with at least 25% to spare.
1209 xfs_da_brelse(state
->args
->trans
, bp
);
1212 * Didn't like either block, give up.
1219 * Done with the sibling leaf block here, drop the dabuf
1220 * so path_shift can get it.
1222 xfs_da_buf_done(bp
);
1224 * Make altpath point to the block we want to keep (the lower
1225 * numbered block) and path point to the block we want to drop.
1227 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
1228 if (blkno
< blk
->blkno
)
1229 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
, 0,
1232 error
= xfs_da_path_shift(state
, &state
->path
, forward
, 0,
1237 *action
= rval
? 0 : 1;
1242 * Move all the leaf entries from drop_blk to save_blk.
1243 * This is done as part of a join operation.
1246 xfs_dir2_leafn_unbalance(
1247 xfs_da_state_t
*state
, /* cursor */
1248 xfs_da_state_blk_t
*drop_blk
, /* dead block */
1249 xfs_da_state_blk_t
*save_blk
) /* surviving block */
1251 xfs_da_args_t
*args
; /* operation arguments */
1252 xfs_dir2_leaf_t
*drop_leaf
; /* dead leaf structure */
1253 xfs_dir2_leaf_t
*save_leaf
; /* surviving leaf structure */
1256 ASSERT(drop_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1257 ASSERT(save_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1258 drop_leaf
= drop_blk
->bp
->data
;
1259 save_leaf
= save_blk
->bp
->data
;
1260 ASSERT(be16_to_cpu(drop_leaf
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
1261 ASSERT(be16_to_cpu(save_leaf
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
1263 * If there are any stale leaf entries, take this opportunity
1266 if (drop_leaf
->hdr
.stale
)
1267 xfs_dir2_leaf_compact(args
, drop_blk
->bp
);
1268 if (save_leaf
->hdr
.stale
)
1269 xfs_dir2_leaf_compact(args
, save_blk
->bp
);
1271 * Move the entries from drop to the appropriate end of save.
1273 drop_blk
->hashval
= be32_to_cpu(drop_leaf
->ents
[be16_to_cpu(drop_leaf
->hdr
.count
) - 1].hashval
);
1274 if (xfs_dir2_leafn_order(save_blk
->bp
, drop_blk
->bp
))
1275 xfs_dir2_leafn_moveents(args
, drop_blk
->bp
, 0, save_blk
->bp
, 0,
1276 be16_to_cpu(drop_leaf
->hdr
.count
));
1278 xfs_dir2_leafn_moveents(args
, drop_blk
->bp
, 0, save_blk
->bp
,
1279 be16_to_cpu(save_leaf
->hdr
.count
), be16_to_cpu(drop_leaf
->hdr
.count
));
1280 save_blk
->hashval
= be32_to_cpu(save_leaf
->ents
[be16_to_cpu(save_leaf
->hdr
.count
) - 1].hashval
);
1281 xfs_dir2_leafn_check(args
->dp
, save_blk
->bp
);
1285 * Top-level node form directory addname routine.
1288 xfs_dir2_node_addname(
1289 xfs_da_args_t
*args
) /* operation arguments */
1291 xfs_da_state_blk_t
*blk
; /* leaf block for insert */
1292 int error
; /* error return value */
1293 int rval
; /* sub-return value */
1294 xfs_da_state_t
*state
; /* btree cursor */
1296 xfs_dir2_trace_args("node_addname", args
);
1298 * Allocate and initialize the state (btree cursor).
1300 state
= xfs_da_state_alloc();
1302 state
->mp
= args
->dp
->i_mount
;
1303 state
->blocksize
= state
->mp
->m_dirblksize
;
1304 state
->node_ents
= state
->mp
->m_dir_node_ents
;
1306 * Look up the name. We're not supposed to find it, but
1307 * this gives us the insertion point.
1309 error
= xfs_da_node_lookup_int(state
, &rval
);
1312 if (rval
!= ENOENT
) {
1316 * Add the data entry to a data block.
1317 * Extravalid is set to a freeblock found by lookup.
1319 rval
= xfs_dir2_node_addname_int(args
,
1320 state
->extravalid
? &state
->extrablk
: NULL
);
1324 blk
= &state
->path
.blk
[state
->path
.active
- 1];
1325 ASSERT(blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1327 * Add the new leaf entry.
1329 rval
= xfs_dir2_leafn_add(blk
->bp
, args
, blk
->index
);
1332 * It worked, fix the hash values up the btree.
1334 if (!args
->justcheck
)
1335 xfs_da_fixhashpath(state
, &state
->path
);
1338 * It didn't work, we need to split the leaf block.
1340 if (args
->total
== 0) {
1341 ASSERT(rval
== ENOSPC
);
1345 * Split the leaf block and insert the new entry.
1347 rval
= xfs_da_split(state
);
1350 xfs_da_state_free(state
);
1355 * Add the data entry for a node-format directory name addition.
1356 * The leaf entry is added in xfs_dir2_leafn_add.
1357 * We may enter with a freespace block that the lookup found.
1359 static int /* error */
1360 xfs_dir2_node_addname_int(
1361 xfs_da_args_t
*args
, /* operation arguments */
1362 xfs_da_state_blk_t
*fblk
) /* optional freespace block */
1364 xfs_dir2_data_t
*data
; /* data block structure */
1365 xfs_dir2_db_t dbno
; /* data block number */
1366 xfs_dabuf_t
*dbp
; /* data block buffer */
1367 xfs_dir2_data_entry_t
*dep
; /* data entry pointer */
1368 xfs_inode_t
*dp
; /* incore directory inode */
1369 xfs_dir2_data_unused_t
*dup
; /* data unused entry pointer */
1370 int error
; /* error return value */
1371 xfs_dir2_db_t fbno
; /* freespace block number */
1372 xfs_dabuf_t
*fbp
; /* freespace buffer */
1373 int findex
; /* freespace entry index */
1374 xfs_dir2_free_t
*free
=NULL
; /* freespace block structure */
1375 xfs_dir2_db_t ifbno
; /* initial freespace block no */
1376 xfs_dir2_db_t lastfbno
=0; /* highest freespace block no */
1377 int length
; /* length of the new entry */
1378 int logfree
; /* need to log free entry */
1379 xfs_mount_t
*mp
; /* filesystem mount point */
1380 int needlog
; /* need to log data header */
1381 int needscan
; /* need to rescan data frees */
1382 __be16
*tagp
; /* data entry tag pointer */
1383 xfs_trans_t
*tp
; /* transaction pointer */
1388 length
= XFS_DIR2_DATA_ENTSIZE(args
->namelen
);
1390 * If we came in with a freespace block that means that lookup
1391 * found an entry with our hash value. This is the freespace
1392 * block for that data entry.
1397 * Remember initial freespace block number.
1399 ifbno
= fblk
->blkno
;
1401 ASSERT(be32_to_cpu(free
->hdr
.magic
) == XFS_DIR2_FREE_MAGIC
);
1402 findex
= fblk
->index
;
1404 * This means the free entry showed that the data block had
1405 * space for our entry, so we remembered it.
1406 * Use that data block.
1409 ASSERT(findex
< be32_to_cpu(free
->hdr
.nvalid
));
1410 ASSERT(be16_to_cpu(free
->bests
[findex
]) != NULLDATAOFF
);
1411 ASSERT(be16_to_cpu(free
->bests
[findex
]) >= length
);
1412 dbno
= be32_to_cpu(free
->hdr
.firstdb
) + findex
;
1415 * The data block looked at didn't have enough room.
1416 * We'll start at the beginning of the freespace entries.
1424 * Didn't come in with a freespace block, so don't have a data block.
1432 * If we don't have a data block yet, we're going to scan the
1433 * freespace blocks looking for one. Figure out what the
1434 * highest freespace block number is.
1437 xfs_fileoff_t fo
; /* freespace block number */
1439 if ((error
= xfs_bmap_last_offset(tp
, dp
, &fo
, XFS_DATA_FORK
)))
1441 lastfbno
= XFS_DIR2_DA_TO_DB(mp
, (xfs_dablk_t
)fo
);
1445 * While we haven't identified a data block, search the freeblock
1446 * data for a good data block. If we find a null freeblock entry,
1447 * indicating a hole in the data blocks, remember that.
1449 while (dbno
== -1) {
1451 * If we don't have a freeblock in hand, get the next one.
1455 * Happens the first time through unless lookup gave
1456 * us a freespace block to start with.
1459 fbno
= XFS_DIR2_FREE_FIRSTDB(mp
);
1461 * If it's ifbno we already looked at it.
1466 * If it's off the end we're done.
1468 if (fbno
>= lastfbno
)
1471 * Read the block. There can be holes in the
1472 * freespace blocks, so this might not succeed.
1473 * This should be really rare, so there's no reason
1476 if ((error
= xfs_da_read_buf(tp
, dp
,
1477 XFS_DIR2_DB_TO_DA(mp
, fbno
), -2, &fbp
,
1481 if (unlikely(fbp
== NULL
)) {
1485 ASSERT(be32_to_cpu(free
->hdr
.magic
) == XFS_DIR2_FREE_MAGIC
);
1489 * Look at the current free entry. Is it good enough?
1491 if (be16_to_cpu(free
->bests
[findex
]) != NULLDATAOFF
&&
1492 be16_to_cpu(free
->bests
[findex
]) >= length
)
1493 dbno
= be32_to_cpu(free
->hdr
.firstdb
) + findex
;
1496 * Are we done with the freeblock?
1498 if (++findex
== be32_to_cpu(free
->hdr
.nvalid
)) {
1502 xfs_da_brelse(tp
, fbp
);
1504 if (fblk
&& fblk
->bp
)
1510 * If we don't have a data block, we need to allocate one and make
1511 * the freespace entries refer to it.
1513 if (unlikely(dbno
== -1)) {
1515 * Not allowed to allocate, return failure.
1517 if (args
->justcheck
|| args
->total
== 0) {
1519 * Drop the freespace buffer unless it came from our
1522 if ((fblk
== NULL
|| fblk
->bp
== NULL
) && fbp
!= NULL
)
1523 xfs_da_buf_done(fbp
);
1524 return XFS_ERROR(ENOSPC
);
1527 * Allocate and initialize the new data block.
1529 if (unlikely((error
= xfs_dir2_grow_inode(args
,
1530 XFS_DIR2_DATA_SPACE
,
1532 (error
= xfs_dir2_data_init(args
, dbno
, &dbp
)))) {
1534 * Drop the freespace buffer unless it came from our
1537 if ((fblk
== NULL
|| fblk
->bp
== NULL
) && fbp
!= NULL
)
1538 xfs_da_buf_done(fbp
);
1542 * If (somehow) we have a freespace block, get rid of it.
1545 xfs_da_brelse(tp
, fbp
);
1546 if (fblk
&& fblk
->bp
)
1550 * Get the freespace block corresponding to the data block
1551 * that was just allocated.
1553 fbno
= XFS_DIR2_DB_TO_FDB(mp
, dbno
);
1554 if (unlikely(error
= xfs_da_read_buf(tp
, dp
,
1555 XFS_DIR2_DB_TO_DA(mp
, fbno
), -2, &fbp
,
1557 xfs_da_buf_done(dbp
);
1561 * If there wasn't a freespace block, the read will
1562 * return a NULL fbp. Allocate and initialize a new one.
1565 if ((error
= xfs_dir2_grow_inode(args
, XFS_DIR2_FREE_SPACE
,
1570 if (unlikely(XFS_DIR2_DB_TO_FDB(mp
, dbno
) != fbno
)) {
1572 "xfs_dir2_node_addname_int: dir ino "
1573 "%llu needed freesp block %lld for\n"
1574 " data block %lld, got %lld\n"
1575 " ifbno %llu lastfbno %d\n",
1576 (unsigned long long)dp
->i_ino
,
1577 (long long)XFS_DIR2_DB_TO_FDB(mp
, dbno
),
1578 (long long)dbno
, (long long)fbno
,
1579 (unsigned long long)ifbno
, lastfbno
);
1582 " fblk 0x%p blkno %llu "
1583 "index %d magic 0x%x\n",
1585 (unsigned long long)fblk
->blkno
,
1590 " ... fblk is NULL\n");
1592 XFS_ERROR_REPORT("xfs_dir2_node_addname_int",
1593 XFS_ERRLEVEL_LOW
, mp
);
1594 return XFS_ERROR(EFSCORRUPTED
);
1598 * Get a buffer for the new block.
1600 if ((error
= xfs_da_get_buf(tp
, dp
,
1601 XFS_DIR2_DB_TO_DA(mp
, fbno
),
1602 -1, &fbp
, XFS_DATA_FORK
))) {
1605 ASSERT(fbp
!= NULL
);
1608 * Initialize the new block to be empty, and remember
1609 * its first slot as our empty slot.
1612 free
->hdr
.magic
= cpu_to_be32(XFS_DIR2_FREE_MAGIC
);
1613 free
->hdr
.firstdb
= cpu_to_be32(
1614 (fbno
- XFS_DIR2_FREE_FIRSTDB(mp
)) *
1615 XFS_DIR2_MAX_FREE_BESTS(mp
));
1616 free
->hdr
.nvalid
= 0;
1617 free
->hdr
.nused
= 0;
1620 ASSERT(be32_to_cpu(free
->hdr
.magic
) == XFS_DIR2_FREE_MAGIC
);
1624 * Set the freespace block index from the data block number.
1626 findex
= XFS_DIR2_DB_TO_FDINDEX(mp
, dbno
);
1628 * If it's after the end of the current entries in the
1629 * freespace block, extend that table.
1631 if (findex
>= be32_to_cpu(free
->hdr
.nvalid
)) {
1632 ASSERT(findex
< XFS_DIR2_MAX_FREE_BESTS(mp
));
1633 free
->hdr
.nvalid
= cpu_to_be32(findex
+ 1);
1635 * Tag new entry so nused will go up.
1637 free
->bests
[findex
] = cpu_to_be16(NULLDATAOFF
);
1640 * If this entry was for an empty data block
1641 * (this should always be true) then update the header.
1643 if (be16_to_cpu(free
->bests
[findex
]) == NULLDATAOFF
) {
1644 be32_add(&free
->hdr
.nused
, 1);
1645 xfs_dir2_free_log_header(tp
, fbp
);
1648 * Update the real value in the table.
1649 * We haven't allocated the data entry yet so this will
1653 free
->bests
[findex
] = data
->hdr
.bestfree
[0].length
;
1657 * We had a data block so we don't have to make a new one.
1661 * If just checking, we succeeded.
1663 if (args
->justcheck
) {
1664 if ((fblk
== NULL
|| fblk
->bp
== NULL
) && fbp
!= NULL
)
1665 xfs_da_buf_done(fbp
);
1669 * Read the data block in.
1672 error
= xfs_da_read_buf(tp
, dp
, XFS_DIR2_DB_TO_DA(mp
, dbno
),
1673 -1, &dbp
, XFS_DATA_FORK
))) {
1674 if ((fblk
== NULL
|| fblk
->bp
== NULL
) && fbp
!= NULL
)
1675 xfs_da_buf_done(fbp
);
1681 ASSERT(be16_to_cpu(data
->hdr
.bestfree
[0].length
) >= length
);
1683 * Point to the existing unused space.
1685 dup
= (xfs_dir2_data_unused_t
*)
1686 ((char *)data
+ be16_to_cpu(data
->hdr
.bestfree
[0].offset
));
1687 needscan
= needlog
= 0;
1689 * Mark the first part of the unused space, inuse for us.
1691 xfs_dir2_data_use_free(tp
, dbp
, dup
,
1692 (xfs_dir2_data_aoff_t
)((char *)dup
- (char *)data
), length
,
1693 &needlog
, &needscan
);
1695 * Fill in the new entry and log it.
1697 dep
= (xfs_dir2_data_entry_t
*)dup
;
1698 dep
->inumber
= cpu_to_be64(args
->inumber
);
1699 dep
->namelen
= args
->namelen
;
1700 memcpy(dep
->name
, args
->name
, dep
->namelen
);
1701 tagp
= XFS_DIR2_DATA_ENTRY_TAG_P(dep
);
1702 *tagp
= cpu_to_be16((char *)dep
- (char *)data
);
1703 xfs_dir2_data_log_entry(tp
, dbp
, dep
);
1705 * Rescan the block for bestfree if needed.
1708 xfs_dir2_data_freescan(mp
, data
, &needlog
, NULL
);
1710 * Log the data block header if needed.
1713 xfs_dir2_data_log_header(tp
, dbp
);
1715 * If the freespace entry is now wrong, update it.
1717 if (be16_to_cpu(free
->bests
[findex
]) != be16_to_cpu(data
->hdr
.bestfree
[0].length
)) {
1718 free
->bests
[findex
] = data
->hdr
.bestfree
[0].length
;
1722 * Log the freespace entry if needed.
1725 xfs_dir2_free_log_bests(tp
, fbp
, findex
, findex
);
1727 * If the caller didn't hand us the freespace block, drop it.
1729 if ((fblk
== NULL
|| fblk
->bp
== NULL
) && fbp
!= NULL
)
1730 xfs_da_buf_done(fbp
);
1732 * Return the data block and offset in args, then drop the data block.
1734 args
->blkno
= (xfs_dablk_t
)dbno
;
1735 args
->index
= be16_to_cpu(*tagp
);
1736 xfs_da_buf_done(dbp
);
1741 * Lookup an entry in a node-format directory.
1742 * All the real work happens in xfs_da_node_lookup_int.
1743 * The only real output is the inode number of the entry.
1746 xfs_dir2_node_lookup(
1747 xfs_da_args_t
*args
) /* operation arguments */
1749 int error
; /* error return value */
1750 int i
; /* btree level */
1751 int rval
; /* operation return value */
1752 xfs_da_state_t
*state
; /* btree cursor */
1754 xfs_dir2_trace_args("node_lookup", args
);
1756 * Allocate and initialize the btree cursor.
1758 state
= xfs_da_state_alloc();
1760 state
->mp
= args
->dp
->i_mount
;
1761 state
->blocksize
= state
->mp
->m_dirblksize
;
1762 state
->node_ents
= state
->mp
->m_dir_node_ents
;
1764 * Fill in the path to the entry in the cursor.
1766 error
= xfs_da_node_lookup_int(state
, &rval
);
1770 * Release the btree blocks and leaf block.
1772 for (i
= 0; i
< state
->path
.active
; i
++) {
1773 xfs_da_brelse(args
->trans
, state
->path
.blk
[i
].bp
);
1774 state
->path
.blk
[i
].bp
= NULL
;
1777 * Release the data block if we have it.
1779 if (state
->extravalid
&& state
->extrablk
.bp
) {
1780 xfs_da_brelse(args
->trans
, state
->extrablk
.bp
);
1781 state
->extrablk
.bp
= NULL
;
1783 xfs_da_state_free(state
);
1788 * Remove an entry from a node-format directory.
1791 xfs_dir2_node_removename(
1792 xfs_da_args_t
*args
) /* operation arguments */
1794 xfs_da_state_blk_t
*blk
; /* leaf block */
1795 int error
; /* error return value */
1796 int rval
; /* operation return value */
1797 xfs_da_state_t
*state
; /* btree cursor */
1799 xfs_dir2_trace_args("node_removename", args
);
1801 * Allocate and initialize the btree cursor.
1803 state
= xfs_da_state_alloc();
1805 state
->mp
= args
->dp
->i_mount
;
1806 state
->blocksize
= state
->mp
->m_dirblksize
;
1807 state
->node_ents
= state
->mp
->m_dir_node_ents
;
1809 * Look up the entry we're deleting, set up the cursor.
1811 error
= xfs_da_node_lookup_int(state
, &rval
);
1816 * Didn't find it, upper layer screwed up.
1818 if (rval
!= EEXIST
) {
1819 xfs_da_state_free(state
);
1822 blk
= &state
->path
.blk
[state
->path
.active
- 1];
1823 ASSERT(blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1824 ASSERT(state
->extravalid
);
1826 * Remove the leaf and data entries.
1827 * Extrablk refers to the data block.
1829 error
= xfs_dir2_leafn_remove(args
, blk
->bp
, blk
->index
,
1830 &state
->extrablk
, &rval
);
1835 * Fix the hash values up the btree.
1837 xfs_da_fixhashpath(state
, &state
->path
);
1839 * If we need to join leaf blocks, do it.
1841 if (rval
&& state
->path
.active
> 1)
1842 error
= xfs_da_join(state
);
1844 * If no errors so far, try conversion to leaf format.
1847 error
= xfs_dir2_node_to_leaf(state
);
1848 xfs_da_state_free(state
);
1853 * Replace an entry's inode number in a node-format directory.
1856 xfs_dir2_node_replace(
1857 xfs_da_args_t
*args
) /* operation arguments */
1859 xfs_da_state_blk_t
*blk
; /* leaf block */
1860 xfs_dir2_data_t
*data
; /* data block structure */
1861 xfs_dir2_data_entry_t
*dep
; /* data entry changed */
1862 int error
; /* error return value */
1863 int i
; /* btree level */
1864 xfs_ino_t inum
; /* new inode number */
1865 xfs_dir2_leaf_t
*leaf
; /* leaf structure */
1866 xfs_dir2_leaf_entry_t
*lep
; /* leaf entry being changed */
1867 int rval
; /* internal return value */
1868 xfs_da_state_t
*state
; /* btree cursor */
1870 xfs_dir2_trace_args("node_replace", args
);
1872 * Allocate and initialize the btree cursor.
1874 state
= xfs_da_state_alloc();
1876 state
->mp
= args
->dp
->i_mount
;
1877 state
->blocksize
= state
->mp
->m_dirblksize
;
1878 state
->node_ents
= state
->mp
->m_dir_node_ents
;
1879 inum
= args
->inumber
;
1881 * Lookup the entry to change in the btree.
1883 error
= xfs_da_node_lookup_int(state
, &rval
);
1888 * It should be found, since the vnodeops layer has looked it up
1889 * and locked it. But paranoia is good.
1891 if (rval
== EEXIST
) {
1893 * Find the leaf entry.
1895 blk
= &state
->path
.blk
[state
->path
.active
- 1];
1896 ASSERT(blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1897 leaf
= blk
->bp
->data
;
1898 lep
= &leaf
->ents
[blk
->index
];
1899 ASSERT(state
->extravalid
);
1901 * Point to the data entry.
1903 data
= state
->extrablk
.bp
->data
;
1904 ASSERT(be32_to_cpu(data
->hdr
.magic
) == XFS_DIR2_DATA_MAGIC
);
1905 dep
= (xfs_dir2_data_entry_t
*)
1907 XFS_DIR2_DATAPTR_TO_OFF(state
->mp
, be32_to_cpu(lep
->address
)));
1908 ASSERT(inum
!= be64_to_cpu(dep
->inumber
));
1910 * Fill in the new inode number and log the entry.
1912 dep
->inumber
= cpu_to_be64(inum
);
1913 xfs_dir2_data_log_entry(args
->trans
, state
->extrablk
.bp
, dep
);
1917 * Didn't find it, and we're holding a data block. Drop it.
1919 else if (state
->extravalid
) {
1920 xfs_da_brelse(args
->trans
, state
->extrablk
.bp
);
1921 state
->extrablk
.bp
= NULL
;
1924 * Release all the buffers in the cursor.
1926 for (i
= 0; i
< state
->path
.active
; i
++) {
1927 xfs_da_brelse(args
->trans
, state
->path
.blk
[i
].bp
);
1928 state
->path
.blk
[i
].bp
= NULL
;
1930 xfs_da_state_free(state
);
1935 * Trim off a trailing empty freespace block.
1936 * Return (in rvalp) 1 if we did it, 0 if not.
1939 xfs_dir2_node_trim_free(
1940 xfs_da_args_t
*args
, /* operation arguments */
1941 xfs_fileoff_t fo
, /* free block number */
1942 int *rvalp
) /* out: did something */
1944 xfs_dabuf_t
*bp
; /* freespace buffer */
1945 xfs_inode_t
*dp
; /* incore directory inode */
1946 int error
; /* error return code */
1947 xfs_dir2_free_t
*free
; /* freespace structure */
1948 xfs_mount_t
*mp
; /* filesystem mount point */
1949 xfs_trans_t
*tp
; /* transaction pointer */
1955 * Read the freespace block.
1957 if (unlikely(error
= xfs_da_read_buf(tp
, dp
, (xfs_dablk_t
)fo
, -2, &bp
,
1963 * There can be holes in freespace. If fo is a hole, there's
1970 ASSERT(be32_to_cpu(free
->hdr
.magic
) == XFS_DIR2_FREE_MAGIC
);
1972 * If there are used entries, there's nothing to do.
1974 if (be32_to_cpu(free
->hdr
.nused
) > 0) {
1975 xfs_da_brelse(tp
, bp
);
1980 * Blow the block away.
1983 xfs_dir2_shrink_inode(args
, XFS_DIR2_DA_TO_DB(mp
, (xfs_dablk_t
)fo
),
1986 * Can't fail with ENOSPC since that only happens with no
1987 * space reservation, when breaking up an extent into two
1988 * pieces. This is the last block of an extent.
1990 ASSERT(error
!= ENOSPC
);
1991 xfs_da_brelse(tp
, bp
);
1995 * Return that we succeeded.