2 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
3 * Copyright (c) 2013 Red Hat, Inc.
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
8 * published by the Free Software Foundation.
10 * This program is distributed in the hope that it would be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 #include "xfs_types.h"
24 #include "xfs_trans.h"
27 #include "xfs_mount.h"
28 #include "xfs_da_btree.h"
29 #include "xfs_bmap_btree.h"
31 #include "xfs_dir2_format.h"
32 #include "xfs_dir2_priv.h"
33 #include "xfs_dinode.h"
34 #include "xfs_inode.h"
35 #include "xfs_inode_item.h"
36 #include "xfs_alloc.h"
39 #include "xfs_attr_leaf.h"
40 #include "xfs_error.h"
41 #include "xfs_trace.h"
42 #include "xfs_cksum.h"
43 #include "xfs_buf_item.h"
48 * Routines to implement directories as Btrees of hashed names.
51 /*========================================================================
52 * Function prototypes for the kernel.
53 *========================================================================*/
56 * Routines used for growing the Btree.
58 STATIC
int xfs_da3_root_split(xfs_da_state_t
*state
,
59 xfs_da_state_blk_t
*existing_root
,
60 xfs_da_state_blk_t
*new_child
);
61 STATIC
int xfs_da3_node_split(xfs_da_state_t
*state
,
62 xfs_da_state_blk_t
*existing_blk
,
63 xfs_da_state_blk_t
*split_blk
,
64 xfs_da_state_blk_t
*blk_to_add
,
67 STATIC
void xfs_da3_node_rebalance(xfs_da_state_t
*state
,
68 xfs_da_state_blk_t
*node_blk_1
,
69 xfs_da_state_blk_t
*node_blk_2
);
70 STATIC
void xfs_da3_node_add(xfs_da_state_t
*state
,
71 xfs_da_state_blk_t
*old_node_blk
,
72 xfs_da_state_blk_t
*new_node_blk
);
75 * Routines used for shrinking the Btree.
77 STATIC
int xfs_da3_root_join(xfs_da_state_t
*state
,
78 xfs_da_state_blk_t
*root_blk
);
79 STATIC
int xfs_da3_node_toosmall(xfs_da_state_t
*state
, int *retval
);
80 STATIC
void xfs_da3_node_remove(xfs_da_state_t
*state
,
81 xfs_da_state_blk_t
*drop_blk
);
82 STATIC
void xfs_da3_node_unbalance(xfs_da_state_t
*state
,
83 xfs_da_state_blk_t
*src_node_blk
,
84 xfs_da_state_blk_t
*dst_node_blk
);
89 STATIC
int xfs_da3_blk_unlink(xfs_da_state_t
*state
,
90 xfs_da_state_blk_t
*drop_blk
,
91 xfs_da_state_blk_t
*save_blk
);
94 kmem_zone_t
*xfs_da_state_zone
; /* anchor for state struct zone */
97 * Allocate a dir-state structure.
98 * We don't put them on the stack since they're large.
101 xfs_da_state_alloc(void)
103 return kmem_zone_zalloc(xfs_da_state_zone
, KM_NOFS
);
107 * Kill the altpath contents of a da-state structure.
110 xfs_da_state_kill_altpath(xfs_da_state_t
*state
)
114 for (i
= 0; i
< state
->altpath
.active
; i
++)
115 state
->altpath
.blk
[i
].bp
= NULL
;
116 state
->altpath
.active
= 0;
120 * Free a da-state structure.
123 xfs_da_state_free(xfs_da_state_t
*state
)
125 xfs_da_state_kill_altpath(state
);
127 memset((char *)state
, 0, sizeof(*state
));
129 kmem_zone_free(xfs_da_state_zone
, state
);
133 xfs_da3_node_hdr_from_disk(
134 struct xfs_da3_icnode_hdr
*to
,
135 struct xfs_da_intnode
*from
)
137 ASSERT(from
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
) ||
138 from
->hdr
.info
.magic
== cpu_to_be16(XFS_DA3_NODE_MAGIC
));
140 if (from
->hdr
.info
.magic
== cpu_to_be16(XFS_DA3_NODE_MAGIC
)) {
141 struct xfs_da3_node_hdr
*hdr3
= (struct xfs_da3_node_hdr
*)from
;
143 to
->forw
= be32_to_cpu(hdr3
->info
.hdr
.forw
);
144 to
->back
= be32_to_cpu(hdr3
->info
.hdr
.back
);
145 to
->magic
= be16_to_cpu(hdr3
->info
.hdr
.magic
);
146 to
->count
= be16_to_cpu(hdr3
->__count
);
147 to
->level
= be16_to_cpu(hdr3
->__level
);
150 to
->forw
= be32_to_cpu(from
->hdr
.info
.forw
);
151 to
->back
= be32_to_cpu(from
->hdr
.info
.back
);
152 to
->magic
= be16_to_cpu(from
->hdr
.info
.magic
);
153 to
->count
= be16_to_cpu(from
->hdr
.__count
);
154 to
->level
= be16_to_cpu(from
->hdr
.__level
);
158 xfs_da3_node_hdr_to_disk(
159 struct xfs_da_intnode
*to
,
160 struct xfs_da3_icnode_hdr
*from
)
162 ASSERT(from
->magic
== XFS_DA_NODE_MAGIC
||
163 from
->magic
== XFS_DA3_NODE_MAGIC
);
165 if (from
->magic
== XFS_DA3_NODE_MAGIC
) {
166 struct xfs_da3_node_hdr
*hdr3
= (struct xfs_da3_node_hdr
*)to
;
168 hdr3
->info
.hdr
.forw
= cpu_to_be32(from
->forw
);
169 hdr3
->info
.hdr
.back
= cpu_to_be32(from
->back
);
170 hdr3
->info
.hdr
.magic
= cpu_to_be16(from
->magic
);
171 hdr3
->__count
= cpu_to_be16(from
->count
);
172 hdr3
->__level
= cpu_to_be16(from
->level
);
175 to
->hdr
.info
.forw
= cpu_to_be32(from
->forw
);
176 to
->hdr
.info
.back
= cpu_to_be32(from
->back
);
177 to
->hdr
.info
.magic
= cpu_to_be16(from
->magic
);
178 to
->hdr
.__count
= cpu_to_be16(from
->count
);
179 to
->hdr
.__level
= cpu_to_be16(from
->level
);
186 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
187 struct xfs_da_intnode
*hdr
= bp
->b_addr
;
188 struct xfs_da3_icnode_hdr ichdr
;
190 xfs_da3_node_hdr_from_disk(&ichdr
, hdr
);
192 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
193 struct xfs_da3_node_hdr
*hdr3
= bp
->b_addr
;
195 if (ichdr
.magic
!= XFS_DA3_NODE_MAGIC
)
198 if (!uuid_equal(&hdr3
->info
.uuid
, &mp
->m_sb
.sb_uuid
))
200 if (be64_to_cpu(hdr3
->info
.blkno
) != bp
->b_bn
)
203 if (ichdr
.magic
!= XFS_DA_NODE_MAGIC
)
206 if (ichdr
.level
== 0)
208 if (ichdr
.level
> XFS_DA_NODE_MAXDEPTH
)
210 if (ichdr
.count
== 0)
214 * we don't know if the node is for and attribute or directory tree,
215 * so only fail if the count is outside both bounds
217 if (ichdr
.count
> mp
->m_dir_node_ents
&&
218 ichdr
.count
> mp
->m_attr_node_ents
)
221 /* XXX: hash order check? */
227 xfs_da3_node_write_verify(
230 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
231 struct xfs_buf_log_item
*bip
= bp
->b_fspriv
;
232 struct xfs_da3_node_hdr
*hdr3
= bp
->b_addr
;
234 if (!xfs_da3_node_verify(bp
)) {
235 XFS_CORRUPTION_ERROR(__func__
, XFS_ERRLEVEL_LOW
, mp
, bp
->b_addr
);
236 xfs_buf_ioerror(bp
, EFSCORRUPTED
);
240 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
244 hdr3
->info
.lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
246 xfs_update_cksum(bp
->b_addr
, BBTOB(bp
->b_length
), XFS_DA3_NODE_CRC_OFF
);
250 * leaf/node format detection on trees is sketchy, so a node read can be done on
251 * leaf level blocks when detection identifies the tree as a node format tree
252 * incorrectly. In this case, we need to swap the verifier to match the correct
253 * format of the block being read.
256 xfs_da3_node_read_verify(
259 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
260 struct xfs_da_blkinfo
*info
= bp
->b_addr
;
262 switch (be16_to_cpu(info
->magic
)) {
263 case XFS_DA3_NODE_MAGIC
:
264 if (!xfs_verify_cksum(bp
->b_addr
, BBTOB(bp
->b_length
),
265 XFS_DA3_NODE_CRC_OFF
))
268 case XFS_DA_NODE_MAGIC
:
269 if (!xfs_da3_node_verify(bp
))
272 case XFS_ATTR_LEAF_MAGIC
:
273 bp
->b_ops
= &xfs_attr3_leaf_buf_ops
;
274 bp
->b_ops
->verify_read(bp
);
276 case XFS_DIR2_LEAFN_MAGIC
:
277 case XFS_DIR3_LEAFN_MAGIC
:
278 bp
->b_ops
= &xfs_dir3_leafn_buf_ops
;
279 bp
->b_ops
->verify_read(bp
);
286 XFS_CORRUPTION_ERROR(__func__
, XFS_ERRLEVEL_LOW
, mp
, bp
->b_addr
);
287 xfs_buf_ioerror(bp
, EFSCORRUPTED
);
290 const struct xfs_buf_ops xfs_da3_node_buf_ops
= {
291 .verify_read
= xfs_da3_node_read_verify
,
292 .verify_write
= xfs_da3_node_write_verify
,
297 struct xfs_trans
*tp
,
298 struct xfs_inode
*dp
,
300 xfs_daddr_t mappedbno
,
301 struct xfs_buf
**bpp
,
306 err
= xfs_da_read_buf(tp
, dp
, bno
, mappedbno
, bpp
,
307 which_fork
, &xfs_da3_node_buf_ops
);
309 struct xfs_da_blkinfo
*info
= (*bpp
)->b_addr
;
312 switch (be16_to_cpu(info
->magic
)) {
313 case XFS_DA_NODE_MAGIC
:
314 case XFS_DA3_NODE_MAGIC
:
315 type
= XFS_BLFT_DA_NODE_BUF
;
317 case XFS_ATTR_LEAF_MAGIC
:
318 case XFS_ATTR3_LEAF_MAGIC
:
319 type
= XFS_BLFT_ATTR_LEAF_BUF
;
321 case XFS_DIR2_LEAFN_MAGIC
:
322 case XFS_DIR3_LEAFN_MAGIC
:
323 type
= XFS_BLFT_DIR_LEAFN_BUF
;
330 xfs_trans_buf_set_type(tp
, *bpp
, type
);
335 /*========================================================================
336 * Routines used for growing the Btree.
337 *========================================================================*/
340 * Create the initial contents of an intermediate node.
344 struct xfs_da_args
*args
,
347 struct xfs_buf
**bpp
,
350 struct xfs_da_intnode
*node
;
351 struct xfs_trans
*tp
= args
->trans
;
352 struct xfs_mount
*mp
= tp
->t_mountp
;
353 struct xfs_da3_icnode_hdr ichdr
= {0};
357 trace_xfs_da_node_create(args
);
358 ASSERT(level
<= XFS_DA_NODE_MAXDEPTH
);
360 error
= xfs_da_get_buf(tp
, args
->dp
, blkno
, -1, &bp
, whichfork
);
363 bp
->b_ops
= &xfs_da3_node_buf_ops
;
364 xfs_trans_buf_set_type(tp
, bp
, XFS_BLFT_DA_NODE_BUF
);
367 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
368 struct xfs_da3_node_hdr
*hdr3
= bp
->b_addr
;
370 ichdr
.magic
= XFS_DA3_NODE_MAGIC
;
371 hdr3
->info
.blkno
= cpu_to_be64(bp
->b_bn
);
372 hdr3
->info
.owner
= cpu_to_be64(args
->dp
->i_ino
);
373 uuid_copy(&hdr3
->info
.uuid
, &mp
->m_sb
.sb_uuid
);
375 ichdr
.magic
= XFS_DA_NODE_MAGIC
;
379 xfs_da3_node_hdr_to_disk(node
, &ichdr
);
380 xfs_trans_log_buf(tp
, bp
,
381 XFS_DA_LOGRANGE(node
, &node
->hdr
, xfs_da3_node_hdr_size(node
)));
388 * Split a leaf node, rebalance, then possibly split
389 * intermediate nodes, rebalance, etc.
393 struct xfs_da_state
*state
)
395 struct xfs_da_state_blk
*oldblk
;
396 struct xfs_da_state_blk
*newblk
;
397 struct xfs_da_state_blk
*addblk
;
398 struct xfs_da_intnode
*node
;
405 trace_xfs_da_split(state
->args
);
408 * Walk back up the tree splitting/inserting/adjusting as necessary.
409 * If we need to insert and there isn't room, split the node, then
410 * decide which fragment to insert the new block from below into.
411 * Note that we may split the root this way, but we need more fixup.
413 max
= state
->path
.active
- 1;
414 ASSERT((max
>= 0) && (max
< XFS_DA_NODE_MAXDEPTH
));
415 ASSERT(state
->path
.blk
[max
].magic
== XFS_ATTR_LEAF_MAGIC
||
416 state
->path
.blk
[max
].magic
== XFS_DIR2_LEAFN_MAGIC
);
418 addblk
= &state
->path
.blk
[max
]; /* initial dummy value */
419 for (i
= max
; (i
>= 0) && addblk
; state
->path
.active
--, i
--) {
420 oldblk
= &state
->path
.blk
[i
];
421 newblk
= &state
->altpath
.blk
[i
];
424 * If a leaf node then
425 * Allocate a new leaf node, then rebalance across them.
426 * else if an intermediate node then
427 * We split on the last layer, must we split the node?
429 switch (oldblk
->magic
) {
430 case XFS_ATTR_LEAF_MAGIC
:
431 error
= xfs_attr3_leaf_split(state
, oldblk
, newblk
);
432 if ((error
!= 0) && (error
!= ENOSPC
)) {
433 return(error
); /* GROT: attr is inconsistent */
440 * Entry wouldn't fit, split the leaf again.
442 state
->extravalid
= 1;
444 state
->extraafter
= 0; /* before newblk */
445 trace_xfs_attr_leaf_split_before(state
->args
);
446 error
= xfs_attr3_leaf_split(state
, oldblk
,
449 state
->extraafter
= 1; /* after newblk */
450 trace_xfs_attr_leaf_split_after(state
->args
);
451 error
= xfs_attr3_leaf_split(state
, newblk
,
455 return(error
); /* GROT: attr inconsistent */
458 case XFS_DIR2_LEAFN_MAGIC
:
459 error
= xfs_dir2_leafn_split(state
, oldblk
, newblk
);
464 case XFS_DA_NODE_MAGIC
:
465 error
= xfs_da3_node_split(state
, oldblk
, newblk
, addblk
,
469 return(error
); /* GROT: dir is inconsistent */
471 * Record the newly split block for the next time thru?
481 * Update the btree to show the new hashval for this child.
483 xfs_da3_fixhashpath(state
, &state
->path
);
489 * Split the root node.
491 ASSERT(state
->path
.active
== 0);
492 oldblk
= &state
->path
.blk
[0];
493 error
= xfs_da3_root_split(state
, oldblk
, addblk
);
496 return(error
); /* GROT: dir is inconsistent */
500 * Update pointers to the node which used to be block 0 and
501 * just got bumped because of the addition of a new root node.
502 * There might be three blocks involved if a double split occurred,
503 * and the original block 0 could be at any position in the list.
505 * Note: the magic numbers and sibling pointers are in the same
506 * physical place for both v2 and v3 headers (by design). Hence it
507 * doesn't matter which version of the xfs_da_intnode structure we use
508 * here as the result will be the same using either structure.
510 node
= oldblk
->bp
->b_addr
;
511 if (node
->hdr
.info
.forw
) {
512 if (be32_to_cpu(node
->hdr
.info
.forw
) == addblk
->blkno
) {
515 ASSERT(state
->extravalid
);
516 bp
= state
->extrablk
.bp
;
519 node
->hdr
.info
.back
= cpu_to_be32(oldblk
->blkno
);
520 xfs_trans_log_buf(state
->args
->trans
, bp
,
521 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
522 sizeof(node
->hdr
.info
)));
524 node
= oldblk
->bp
->b_addr
;
525 if (node
->hdr
.info
.back
) {
526 if (be32_to_cpu(node
->hdr
.info
.back
) == addblk
->blkno
) {
529 ASSERT(state
->extravalid
);
530 bp
= state
->extrablk
.bp
;
533 node
->hdr
.info
.forw
= cpu_to_be32(oldblk
->blkno
);
534 xfs_trans_log_buf(state
->args
->trans
, bp
,
535 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
536 sizeof(node
->hdr
.info
)));
543 * Split the root. We have to create a new root and point to the two
544 * parts (the split old root) that we just created. Copy block zero to
545 * the EOF, extending the inode in process.
547 STATIC
int /* error */
549 struct xfs_da_state
*state
,
550 struct xfs_da_state_blk
*blk1
,
551 struct xfs_da_state_blk
*blk2
)
553 struct xfs_da_intnode
*node
;
554 struct xfs_da_intnode
*oldroot
;
555 struct xfs_da_node_entry
*btree
;
556 struct xfs_da3_icnode_hdr nodehdr
;
557 struct xfs_da_args
*args
;
559 struct xfs_inode
*dp
;
560 struct xfs_trans
*tp
;
561 struct xfs_mount
*mp
;
562 struct xfs_dir2_leaf
*leaf
;
568 trace_xfs_da_root_split(state
->args
);
571 * Copy the existing (incorrect) block from the root node position
572 * to a free space somewhere.
575 error
= xfs_da_grow_inode(args
, &blkno
);
582 error
= xfs_da_get_buf(tp
, dp
, blkno
, -1, &bp
, args
->whichfork
);
586 oldroot
= blk1
->bp
->b_addr
;
587 if (oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
) ||
588 oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DA3_NODE_MAGIC
)) {
589 struct xfs_da3_icnode_hdr nodehdr
;
591 xfs_da3_node_hdr_from_disk(&nodehdr
, oldroot
);
592 btree
= xfs_da3_node_tree_p(oldroot
);
593 size
= (int)((char *)&btree
[nodehdr
.count
] - (char *)oldroot
);
594 level
= nodehdr
.level
;
597 * we are about to copy oldroot to bp, so set up the type
598 * of bp while we know exactly what it will be.
600 xfs_trans_buf_set_type(tp
, bp
, XFS_BLFT_DA_NODE_BUF
);
602 struct xfs_dir3_icleaf_hdr leafhdr
;
603 struct xfs_dir2_leaf_entry
*ents
;
605 leaf
= (xfs_dir2_leaf_t
*)oldroot
;
606 xfs_dir3_leaf_hdr_from_disk(&leafhdr
, leaf
);
607 ents
= xfs_dir3_leaf_ents_p(leaf
);
609 ASSERT(leafhdr
.magic
== XFS_DIR2_LEAFN_MAGIC
||
610 leafhdr
.magic
== XFS_DIR3_LEAFN_MAGIC
);
611 size
= (int)((char *)&ents
[leafhdr
.count
] - (char *)leaf
);
615 * we are about to copy oldroot to bp, so set up the type
616 * of bp while we know exactly what it will be.
618 xfs_trans_buf_set_type(tp
, bp
, XFS_BLFT_DIR_LEAFN_BUF
);
622 * we can copy most of the information in the node from one block to
623 * another, but for CRC enabled headers we have to make sure that the
624 * block specific identifiers are kept intact. We update the buffer
627 memcpy(node
, oldroot
, size
);
628 if (oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DA3_NODE_MAGIC
) ||
629 oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DIR3_LEAFN_MAGIC
)) {
630 struct xfs_da3_intnode
*node3
= (struct xfs_da3_intnode
*)node
;
632 node3
->hdr
.info
.blkno
= cpu_to_be64(bp
->b_bn
);
634 xfs_trans_log_buf(tp
, bp
, 0, size
- 1);
636 bp
->b_ops
= blk1
->bp
->b_ops
;
641 * Set up the new root node.
643 error
= xfs_da3_node_create(args
,
644 (args
->whichfork
== XFS_DATA_FORK
) ? mp
->m_dirleafblk
: 0,
645 level
+ 1, &bp
, args
->whichfork
);
650 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
651 btree
= xfs_da3_node_tree_p(node
);
652 btree
[0].hashval
= cpu_to_be32(blk1
->hashval
);
653 btree
[0].before
= cpu_to_be32(blk1
->blkno
);
654 btree
[1].hashval
= cpu_to_be32(blk2
->hashval
);
655 btree
[1].before
= cpu_to_be32(blk2
->blkno
);
657 xfs_da3_node_hdr_to_disk(node
, &nodehdr
);
660 if (oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
) ||
661 oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DIR3_LEAFN_MAGIC
)) {
662 ASSERT(blk1
->blkno
>= mp
->m_dirleafblk
&&
663 blk1
->blkno
< mp
->m_dirfreeblk
);
664 ASSERT(blk2
->blkno
>= mp
->m_dirleafblk
&&
665 blk2
->blkno
< mp
->m_dirfreeblk
);
669 /* Header is already logged by xfs_da_node_create */
670 xfs_trans_log_buf(tp
, bp
,
671 XFS_DA_LOGRANGE(node
, btree
, sizeof(xfs_da_node_entry_t
) * 2));
677 * Split the node, rebalance, then add the new entry.
679 STATIC
int /* error */
681 struct xfs_da_state
*state
,
682 struct xfs_da_state_blk
*oldblk
,
683 struct xfs_da_state_blk
*newblk
,
684 struct xfs_da_state_blk
*addblk
,
688 struct xfs_da_intnode
*node
;
689 struct xfs_da3_icnode_hdr nodehdr
;
695 trace_xfs_da_node_split(state
->args
);
697 node
= oldblk
->bp
->b_addr
;
698 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
701 * With V2 dirs the extra block is data or freespace.
703 useextra
= state
->extravalid
&& state
->args
->whichfork
== XFS_ATTR_FORK
;
704 newcount
= 1 + useextra
;
706 * Do we have to split the node?
708 if (nodehdr
.count
+ newcount
> state
->node_ents
) {
710 * Allocate a new node, add to the doubly linked chain of
711 * nodes, then move some of our excess entries into it.
713 error
= xfs_da_grow_inode(state
->args
, &blkno
);
715 return(error
); /* GROT: dir is inconsistent */
717 error
= xfs_da3_node_create(state
->args
, blkno
, treelevel
,
718 &newblk
->bp
, state
->args
->whichfork
);
720 return(error
); /* GROT: dir is inconsistent */
721 newblk
->blkno
= blkno
;
722 newblk
->magic
= XFS_DA_NODE_MAGIC
;
723 xfs_da3_node_rebalance(state
, oldblk
, newblk
);
724 error
= xfs_da3_blk_link(state
, oldblk
, newblk
);
733 * Insert the new entry(s) into the correct block
734 * (updating last hashval in the process).
736 * xfs_da3_node_add() inserts BEFORE the given index,
737 * and as a result of using node_lookup_int() we always
738 * point to a valid entry (not after one), but a split
739 * operation always results in a new block whose hashvals
740 * FOLLOW the current block.
742 * If we had double-split op below us, then add the extra block too.
744 node
= oldblk
->bp
->b_addr
;
745 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
746 if (oldblk
->index
<= nodehdr
.count
) {
748 xfs_da3_node_add(state
, oldblk
, addblk
);
750 if (state
->extraafter
)
752 xfs_da3_node_add(state
, oldblk
, &state
->extrablk
);
753 state
->extravalid
= 0;
757 xfs_da3_node_add(state
, newblk
, addblk
);
759 if (state
->extraafter
)
761 xfs_da3_node_add(state
, newblk
, &state
->extrablk
);
762 state
->extravalid
= 0;
770 * Balance the btree elements between two intermediate nodes,
771 * usually one full and one empty.
773 * NOTE: if blk2 is empty, then it will get the upper half of blk1.
776 xfs_da3_node_rebalance(
777 struct xfs_da_state
*state
,
778 struct xfs_da_state_blk
*blk1
,
779 struct xfs_da_state_blk
*blk2
)
781 struct xfs_da_intnode
*node1
;
782 struct xfs_da_intnode
*node2
;
783 struct xfs_da_intnode
*tmpnode
;
784 struct xfs_da_node_entry
*btree1
;
785 struct xfs_da_node_entry
*btree2
;
786 struct xfs_da_node_entry
*btree_s
;
787 struct xfs_da_node_entry
*btree_d
;
788 struct xfs_da3_icnode_hdr nodehdr1
;
789 struct xfs_da3_icnode_hdr nodehdr2
;
790 struct xfs_trans
*tp
;
795 trace_xfs_da_node_rebalance(state
->args
);
797 node1
= blk1
->bp
->b_addr
;
798 node2
= blk2
->bp
->b_addr
;
799 xfs_da3_node_hdr_from_disk(&nodehdr1
, node1
);
800 xfs_da3_node_hdr_from_disk(&nodehdr2
, node2
);
801 btree1
= xfs_da3_node_tree_p(node1
);
802 btree2
= xfs_da3_node_tree_p(node2
);
805 * Figure out how many entries need to move, and in which direction.
806 * Swap the nodes around if that makes it simpler.
808 if (nodehdr1
.count
> 0 && nodehdr2
.count
> 0 &&
809 ((be32_to_cpu(btree2
[0].hashval
) < be32_to_cpu(btree1
[0].hashval
)) ||
810 (be32_to_cpu(btree2
[nodehdr2
.count
- 1].hashval
) <
811 be32_to_cpu(btree1
[nodehdr1
.count
- 1].hashval
)))) {
815 xfs_da3_node_hdr_from_disk(&nodehdr1
, node1
);
816 xfs_da3_node_hdr_from_disk(&nodehdr2
, node2
);
817 btree1
= xfs_da3_node_tree_p(node1
);
818 btree2
= xfs_da3_node_tree_p(node2
);
822 count
= (nodehdr1
.count
- nodehdr2
.count
) / 2;
825 tp
= state
->args
->trans
;
827 * Two cases: high-to-low and low-to-high.
831 * Move elements in node2 up to make a hole.
833 tmp
= nodehdr2
.count
;
835 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
836 btree_s
= &btree2
[0];
837 btree_d
= &btree2
[count
];
838 memmove(btree_d
, btree_s
, tmp
);
842 * Move the req'd B-tree elements from high in node1 to
845 nodehdr2
.count
+= count
;
846 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
847 btree_s
= &btree1
[nodehdr1
.count
- count
];
848 btree_d
= &btree2
[0];
849 memcpy(btree_d
, btree_s
, tmp
);
850 nodehdr1
.count
-= count
;
853 * Move the req'd B-tree elements from low in node2 to
857 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
858 btree_s
= &btree2
[0];
859 btree_d
= &btree1
[nodehdr1
.count
];
860 memcpy(btree_d
, btree_s
, tmp
);
861 nodehdr1
.count
+= count
;
863 xfs_trans_log_buf(tp
, blk1
->bp
,
864 XFS_DA_LOGRANGE(node1
, btree_d
, tmp
));
867 * Move elements in node2 down to fill the hole.
869 tmp
= nodehdr2
.count
- count
;
870 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
871 btree_s
= &btree2
[count
];
872 btree_d
= &btree2
[0];
873 memmove(btree_d
, btree_s
, tmp
);
874 nodehdr2
.count
-= count
;
878 * Log header of node 1 and all current bits of node 2.
880 xfs_da3_node_hdr_to_disk(node1
, &nodehdr1
);
881 xfs_trans_log_buf(tp
, blk1
->bp
,
882 XFS_DA_LOGRANGE(node1
, &node1
->hdr
,
883 xfs_da3_node_hdr_size(node1
)));
885 xfs_da3_node_hdr_to_disk(node2
, &nodehdr2
);
886 xfs_trans_log_buf(tp
, blk2
->bp
,
887 XFS_DA_LOGRANGE(node2
, &node2
->hdr
,
888 xfs_da3_node_hdr_size(node2
) +
889 (sizeof(btree2
[0]) * nodehdr2
.count
)));
892 * Record the last hashval from each block for upward propagation.
893 * (note: don't use the swapped node pointers)
896 node1
= blk1
->bp
->b_addr
;
897 node2
= blk2
->bp
->b_addr
;
898 xfs_da3_node_hdr_from_disk(&nodehdr1
, node1
);
899 xfs_da3_node_hdr_from_disk(&nodehdr2
, node2
);
900 btree1
= xfs_da3_node_tree_p(node1
);
901 btree2
= xfs_da3_node_tree_p(node2
);
903 blk1
->hashval
= be32_to_cpu(btree1
[nodehdr1
.count
- 1].hashval
);
904 blk2
->hashval
= be32_to_cpu(btree2
[nodehdr2
.count
- 1].hashval
);
907 * Adjust the expected index for insertion.
909 if (blk1
->index
>= nodehdr1
.count
) {
910 blk2
->index
= blk1
->index
- nodehdr1
.count
;
911 blk1
->index
= nodehdr1
.count
+ 1; /* make it invalid */
916 * Add a new entry to an intermediate node.
920 struct xfs_da_state
*state
,
921 struct xfs_da_state_blk
*oldblk
,
922 struct xfs_da_state_blk
*newblk
)
924 struct xfs_da_intnode
*node
;
925 struct xfs_da3_icnode_hdr nodehdr
;
926 struct xfs_da_node_entry
*btree
;
929 trace_xfs_da_node_add(state
->args
);
931 node
= oldblk
->bp
->b_addr
;
932 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
933 btree
= xfs_da3_node_tree_p(node
);
935 ASSERT(oldblk
->index
>= 0 && oldblk
->index
<= nodehdr
.count
);
936 ASSERT(newblk
->blkno
!= 0);
937 if (state
->args
->whichfork
== XFS_DATA_FORK
)
938 ASSERT(newblk
->blkno
>= state
->mp
->m_dirleafblk
&&
939 newblk
->blkno
< state
->mp
->m_dirfreeblk
);
942 * We may need to make some room before we insert the new node.
945 if (oldblk
->index
< nodehdr
.count
) {
946 tmp
= (nodehdr
.count
- oldblk
->index
) * (uint
)sizeof(*btree
);
947 memmove(&btree
[oldblk
->index
+ 1], &btree
[oldblk
->index
], tmp
);
949 btree
[oldblk
->index
].hashval
= cpu_to_be32(newblk
->hashval
);
950 btree
[oldblk
->index
].before
= cpu_to_be32(newblk
->blkno
);
951 xfs_trans_log_buf(state
->args
->trans
, oldblk
->bp
,
952 XFS_DA_LOGRANGE(node
, &btree
[oldblk
->index
],
953 tmp
+ sizeof(*btree
)));
956 xfs_da3_node_hdr_to_disk(node
, &nodehdr
);
957 xfs_trans_log_buf(state
->args
->trans
, oldblk
->bp
,
958 XFS_DA_LOGRANGE(node
, &node
->hdr
, xfs_da3_node_hdr_size(node
)));
961 * Copy the last hash value from the oldblk to propagate upwards.
963 oldblk
->hashval
= be32_to_cpu(btree
[nodehdr
.count
- 1].hashval
);
966 /*========================================================================
967 * Routines used for shrinking the Btree.
968 *========================================================================*/
971 * Deallocate an empty leaf node, remove it from its parent,
972 * possibly deallocating that block, etc...
976 struct xfs_da_state
*state
)
978 struct xfs_da_state_blk
*drop_blk
;
979 struct xfs_da_state_blk
*save_blk
;
983 trace_xfs_da_join(state
->args
);
985 drop_blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
986 save_blk
= &state
->altpath
.blk
[ state
->path
.active
-1 ];
987 ASSERT(state
->path
.blk
[0].magic
== XFS_DA_NODE_MAGIC
);
988 ASSERT(drop_blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
989 drop_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
992 * Walk back up the tree joining/deallocating as necessary.
993 * When we stop dropping blocks, break out.
995 for ( ; state
->path
.active
>= 2; drop_blk
--, save_blk
--,
996 state
->path
.active
--) {
998 * See if we can combine the block with a neighbor.
999 * (action == 0) => no options, just leave
1000 * (action == 1) => coalesce, then unlink
1001 * (action == 2) => block empty, unlink it
1003 switch (drop_blk
->magic
) {
1004 case XFS_ATTR_LEAF_MAGIC
:
1005 error
= xfs_attr3_leaf_toosmall(state
, &action
);
1010 xfs_attr3_leaf_unbalance(state
, drop_blk
, save_blk
);
1012 case XFS_DIR2_LEAFN_MAGIC
:
1013 error
= xfs_dir2_leafn_toosmall(state
, &action
);
1018 xfs_dir2_leafn_unbalance(state
, drop_blk
, save_blk
);
1020 case XFS_DA_NODE_MAGIC
:
1022 * Remove the offending node, fixup hashvals,
1023 * check for a toosmall neighbor.
1025 xfs_da3_node_remove(state
, drop_blk
);
1026 xfs_da3_fixhashpath(state
, &state
->path
);
1027 error
= xfs_da3_node_toosmall(state
, &action
);
1032 xfs_da3_node_unbalance(state
, drop_blk
, save_blk
);
1035 xfs_da3_fixhashpath(state
, &state
->altpath
);
1036 error
= xfs_da3_blk_unlink(state
, drop_blk
, save_blk
);
1037 xfs_da_state_kill_altpath(state
);
1040 error
= xfs_da_shrink_inode(state
->args
, drop_blk
->blkno
,
1042 drop_blk
->bp
= NULL
;
1047 * We joined all the way to the top. If it turns out that
1048 * we only have one entry in the root, make the child block
1051 xfs_da3_node_remove(state
, drop_blk
);
1052 xfs_da3_fixhashpath(state
, &state
->path
);
1053 error
= xfs_da3_root_join(state
, &state
->path
.blk
[0]);
1059 xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo
*blkinfo
, __u16 level
)
1061 __be16 magic
= blkinfo
->magic
;
1064 ASSERT(magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
) ||
1065 magic
== cpu_to_be16(XFS_DIR3_LEAFN_MAGIC
) ||
1066 magic
== cpu_to_be16(XFS_ATTR_LEAF_MAGIC
) ||
1067 magic
== cpu_to_be16(XFS_ATTR3_LEAF_MAGIC
));
1069 ASSERT(magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
) ||
1070 magic
== cpu_to_be16(XFS_DA3_NODE_MAGIC
));
1072 ASSERT(!blkinfo
->forw
);
1073 ASSERT(!blkinfo
->back
);
1076 #define xfs_da_blkinfo_onlychild_validate(blkinfo, level)
1080 * We have only one entry in the root. Copy the only remaining child of
1081 * the old root to block 0 as the new root node.
1085 struct xfs_da_state
*state
,
1086 struct xfs_da_state_blk
*root_blk
)
1088 struct xfs_da_intnode
*oldroot
;
1089 struct xfs_da_args
*args
;
1092 struct xfs_da3_icnode_hdr oldroothdr
;
1093 struct xfs_da_node_entry
*btree
;
1096 trace_xfs_da_root_join(state
->args
);
1098 ASSERT(root_blk
->magic
== XFS_DA_NODE_MAGIC
);
1101 oldroot
= root_blk
->bp
->b_addr
;
1102 xfs_da3_node_hdr_from_disk(&oldroothdr
, oldroot
);
1103 ASSERT(oldroothdr
.forw
== 0);
1104 ASSERT(oldroothdr
.back
== 0);
1107 * If the root has more than one child, then don't do anything.
1109 if (oldroothdr
.count
> 1)
1113 * Read in the (only) child block, then copy those bytes into
1114 * the root block's buffer and free the original child block.
1116 btree
= xfs_da3_node_tree_p(oldroot
);
1117 child
= be32_to_cpu(btree
[0].before
);
1119 error
= xfs_da3_node_read(args
->trans
, args
->dp
, child
, -1, &bp
,
1123 xfs_da_blkinfo_onlychild_validate(bp
->b_addr
, oldroothdr
.level
);
1126 * This could be copying a leaf back into the root block in the case of
1127 * there only being a single leaf block left in the tree. Hence we have
1128 * to update the b_ops pointer as well to match the buffer type change
1129 * that could occur. For dir3 blocks we also need to update the block
1130 * number in the buffer header.
1132 memcpy(root_blk
->bp
->b_addr
, bp
->b_addr
, state
->blocksize
);
1133 root_blk
->bp
->b_ops
= bp
->b_ops
;
1134 xfs_trans_buf_copy_type(root_blk
->bp
, bp
);
1135 if (oldroothdr
.magic
== XFS_DA3_NODE_MAGIC
) {
1136 struct xfs_da3_blkinfo
*da3
= root_blk
->bp
->b_addr
;
1137 da3
->blkno
= cpu_to_be64(root_blk
->bp
->b_bn
);
1139 xfs_trans_log_buf(args
->trans
, root_blk
->bp
, 0, state
->blocksize
- 1);
1140 error
= xfs_da_shrink_inode(args
, child
, bp
);
1145 * Check a node block and its neighbors to see if the block should be
1146 * collapsed into one or the other neighbor. Always keep the block
1147 * with the smaller block number.
1148 * If the current block is over 50% full, don't try to join it, return 0.
1149 * If the block is empty, fill in the state structure and return 2.
1150 * If it can be collapsed, fill in the state structure and return 1.
1151 * If nothing can be done, return 0.
1154 xfs_da3_node_toosmall(
1155 struct xfs_da_state
*state
,
1158 struct xfs_da_intnode
*node
;
1159 struct xfs_da_state_blk
*blk
;
1160 struct xfs_da_blkinfo
*info
;
1163 struct xfs_da3_icnode_hdr nodehdr
;
1170 trace_xfs_da_node_toosmall(state
->args
);
1173 * Check for the degenerate case of the block being over 50% full.
1174 * If so, it's not worth even looking to see if we might be able
1175 * to coalesce with a sibling.
1177 blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
1178 info
= blk
->bp
->b_addr
;
1179 node
= (xfs_da_intnode_t
*)info
;
1180 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
1181 if (nodehdr
.count
> (state
->node_ents
>> 1)) {
1182 *action
= 0; /* blk over 50%, don't try to join */
1183 return(0); /* blk over 50%, don't try to join */
1187 * Check for the degenerate case of the block being empty.
1188 * If the block is empty, we'll simply delete it, no need to
1189 * coalesce it with a sibling block. We choose (arbitrarily)
1190 * to merge with the forward block unless it is NULL.
1192 if (nodehdr
.count
== 0) {
1194 * Make altpath point to the block we want to keep and
1195 * path point to the block we want to drop (this one).
1197 forward
= (info
->forw
!= 0);
1198 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
1199 error
= xfs_da3_path_shift(state
, &state
->altpath
, forward
,
1212 * Examine each sibling block to see if we can coalesce with
1213 * at least 25% free space to spare. We need to figure out
1214 * whether to merge with the forward or the backward block.
1215 * We prefer coalescing with the lower numbered sibling so as
1216 * to shrink a directory over time.
1218 count
= state
->node_ents
;
1219 count
-= state
->node_ents
>> 2;
1220 count
-= nodehdr
.count
;
1222 /* start with smaller blk num */
1223 forward
= nodehdr
.forw
< nodehdr
.back
;
1224 for (i
= 0; i
< 2; forward
= !forward
, i
++) {
1226 blkno
= nodehdr
.forw
;
1228 blkno
= nodehdr
.back
;
1231 error
= xfs_da3_node_read(state
->args
->trans
, state
->args
->dp
,
1232 blkno
, -1, &bp
, state
->args
->whichfork
);
1237 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
1238 xfs_trans_brelse(state
->args
->trans
, bp
);
1240 if (count
- nodehdr
.count
>= 0)
1241 break; /* fits with at least 25% to spare */
1249 * Make altpath point to the block we want to keep (the lower
1250 * numbered block) and path point to the block we want to drop.
1252 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
1253 if (blkno
< blk
->blkno
) {
1254 error
= xfs_da3_path_shift(state
, &state
->altpath
, forward
,
1257 error
= xfs_da3_path_shift(state
, &state
->path
, forward
,
1271 * Pick up the last hashvalue from an intermediate node.
1274 xfs_da3_node_lasthash(
1278 struct xfs_da_intnode
*node
;
1279 struct xfs_da_node_entry
*btree
;
1280 struct xfs_da3_icnode_hdr nodehdr
;
1283 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
1285 *count
= nodehdr
.count
;
1288 btree
= xfs_da3_node_tree_p(node
);
1289 return be32_to_cpu(btree
[nodehdr
.count
- 1].hashval
);
1293 * Walk back up the tree adjusting hash values as necessary,
1294 * when we stop making changes, return.
1297 xfs_da3_fixhashpath(
1298 struct xfs_da_state
*state
,
1299 struct xfs_da_state_path
*path
)
1301 struct xfs_da_state_blk
*blk
;
1302 struct xfs_da_intnode
*node
;
1303 struct xfs_da_node_entry
*btree
;
1304 xfs_dahash_t lasthash
=0;
1308 trace_xfs_da_fixhashpath(state
->args
);
1310 level
= path
->active
-1;
1311 blk
= &path
->blk
[ level
];
1312 switch (blk
->magic
) {
1313 case XFS_ATTR_LEAF_MAGIC
:
1314 lasthash
= xfs_attr_leaf_lasthash(blk
->bp
, &count
);
1318 case XFS_DIR2_LEAFN_MAGIC
:
1319 lasthash
= xfs_dir2_leafn_lasthash(blk
->bp
, &count
);
1323 case XFS_DA_NODE_MAGIC
:
1324 lasthash
= xfs_da3_node_lasthash(blk
->bp
, &count
);
1329 for (blk
--, level
--; level
>= 0; blk
--, level
--) {
1330 struct xfs_da3_icnode_hdr nodehdr
;
1332 node
= blk
->bp
->b_addr
;
1333 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
1334 btree
= xfs_da3_node_tree_p(node
);
1335 if (be32_to_cpu(btree
->hashval
) == lasthash
)
1337 blk
->hashval
= lasthash
;
1338 btree
[blk
->index
].hashval
= cpu_to_be32(lasthash
);
1339 xfs_trans_log_buf(state
->args
->trans
, blk
->bp
,
1340 XFS_DA_LOGRANGE(node
, &btree
[blk
->index
],
1343 lasthash
= be32_to_cpu(btree
[nodehdr
.count
- 1].hashval
);
1348 * Remove an entry from an intermediate node.
1351 xfs_da3_node_remove(
1352 struct xfs_da_state
*state
,
1353 struct xfs_da_state_blk
*drop_blk
)
1355 struct xfs_da_intnode
*node
;
1356 struct xfs_da3_icnode_hdr nodehdr
;
1357 struct xfs_da_node_entry
*btree
;
1361 trace_xfs_da_node_remove(state
->args
);
1363 node
= drop_blk
->bp
->b_addr
;
1364 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
1365 ASSERT(drop_blk
->index
< nodehdr
.count
);
1366 ASSERT(drop_blk
->index
>= 0);
1369 * Copy over the offending entry, or just zero it out.
1371 index
= drop_blk
->index
;
1372 btree
= xfs_da3_node_tree_p(node
);
1373 if (index
< nodehdr
.count
- 1) {
1374 tmp
= nodehdr
.count
- index
- 1;
1375 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
1376 memmove(&btree
[index
], &btree
[index
+ 1], tmp
);
1377 xfs_trans_log_buf(state
->args
->trans
, drop_blk
->bp
,
1378 XFS_DA_LOGRANGE(node
, &btree
[index
], tmp
));
1379 index
= nodehdr
.count
- 1;
1381 memset(&btree
[index
], 0, sizeof(xfs_da_node_entry_t
));
1382 xfs_trans_log_buf(state
->args
->trans
, drop_blk
->bp
,
1383 XFS_DA_LOGRANGE(node
, &btree
[index
], sizeof(btree
[index
])));
1385 xfs_da3_node_hdr_to_disk(node
, &nodehdr
);
1386 xfs_trans_log_buf(state
->args
->trans
, drop_blk
->bp
,
1387 XFS_DA_LOGRANGE(node
, &node
->hdr
, xfs_da3_node_hdr_size(node
)));
1390 * Copy the last hash value from the block to propagate upwards.
1392 drop_blk
->hashval
= be32_to_cpu(btree
[index
- 1].hashval
);
1396 * Unbalance the elements between two intermediate nodes,
1397 * move all Btree elements from one node into another.
1400 xfs_da3_node_unbalance(
1401 struct xfs_da_state
*state
,
1402 struct xfs_da_state_blk
*drop_blk
,
1403 struct xfs_da_state_blk
*save_blk
)
1405 struct xfs_da_intnode
*drop_node
;
1406 struct xfs_da_intnode
*save_node
;
1407 struct xfs_da_node_entry
*drop_btree
;
1408 struct xfs_da_node_entry
*save_btree
;
1409 struct xfs_da3_icnode_hdr drop_hdr
;
1410 struct xfs_da3_icnode_hdr save_hdr
;
1411 struct xfs_trans
*tp
;
1415 trace_xfs_da_node_unbalance(state
->args
);
1417 drop_node
= drop_blk
->bp
->b_addr
;
1418 save_node
= save_blk
->bp
->b_addr
;
1419 xfs_da3_node_hdr_from_disk(&drop_hdr
, drop_node
);
1420 xfs_da3_node_hdr_from_disk(&save_hdr
, save_node
);
1421 drop_btree
= xfs_da3_node_tree_p(drop_node
);
1422 save_btree
= xfs_da3_node_tree_p(save_node
);
1423 tp
= state
->args
->trans
;
1426 * If the dying block has lower hashvals, then move all the
1427 * elements in the remaining block up to make a hole.
1429 if ((be32_to_cpu(drop_btree
[0].hashval
) <
1430 be32_to_cpu(save_btree
[0].hashval
)) ||
1431 (be32_to_cpu(drop_btree
[drop_hdr
.count
- 1].hashval
) <
1432 be32_to_cpu(save_btree
[save_hdr
.count
- 1].hashval
))) {
1433 /* XXX: check this - is memmove dst correct? */
1434 tmp
= save_hdr
.count
* sizeof(xfs_da_node_entry_t
);
1435 memmove(&save_btree
[drop_hdr
.count
], &save_btree
[0], tmp
);
1438 xfs_trans_log_buf(tp
, save_blk
->bp
,
1439 XFS_DA_LOGRANGE(save_node
, &save_btree
[0],
1440 (save_hdr
.count
+ drop_hdr
.count
) *
1441 sizeof(xfs_da_node_entry_t
)));
1443 sindex
= save_hdr
.count
;
1444 xfs_trans_log_buf(tp
, save_blk
->bp
,
1445 XFS_DA_LOGRANGE(save_node
, &save_btree
[sindex
],
1446 drop_hdr
.count
* sizeof(xfs_da_node_entry_t
)));
1450 * Move all the B-tree elements from drop_blk to save_blk.
1452 tmp
= drop_hdr
.count
* (uint
)sizeof(xfs_da_node_entry_t
);
1453 memcpy(&save_btree
[sindex
], &drop_btree
[0], tmp
);
1454 save_hdr
.count
+= drop_hdr
.count
;
1456 xfs_da3_node_hdr_to_disk(save_node
, &save_hdr
);
1457 xfs_trans_log_buf(tp
, save_blk
->bp
,
1458 XFS_DA_LOGRANGE(save_node
, &save_node
->hdr
,
1459 xfs_da3_node_hdr_size(save_node
)));
1462 * Save the last hashval in the remaining block for upward propagation.
1464 save_blk
->hashval
= be32_to_cpu(save_btree
[save_hdr
.count
- 1].hashval
);
1467 /*========================================================================
1468 * Routines used for finding things in the Btree.
1469 *========================================================================*/
1472 * Walk down the Btree looking for a particular filename, filling
1473 * in the state structure as we go.
1475 * We will set the state structure to point to each of the elements
1476 * in each of the nodes where either the hashval is or should be.
1478 * We support duplicate hashval's so for each entry in the current
1479 * node that could contain the desired hashval, descend. This is a
1480 * pruned depth-first tree search.
1483 xfs_da3_node_lookup_int(
1484 struct xfs_da_state
*state
,
1487 struct xfs_da_state_blk
*blk
;
1488 struct xfs_da_blkinfo
*curr
;
1489 struct xfs_da_intnode
*node
;
1490 struct xfs_da_node_entry
*btree
;
1491 struct xfs_da3_icnode_hdr nodehdr
;
1492 struct xfs_da_args
*args
;
1494 xfs_dahash_t hashval
;
1495 xfs_dahash_t btreehashval
;
1505 * Descend thru the B-tree searching each level for the right
1506 * node to use, until the right hashval is found.
1508 blkno
= (args
->whichfork
== XFS_DATA_FORK
)? state
->mp
->m_dirleafblk
: 0;
1509 for (blk
= &state
->path
.blk
[0], state
->path
.active
= 1;
1510 state
->path
.active
<= XFS_DA_NODE_MAXDEPTH
;
1511 blk
++, state
->path
.active
++) {
1513 * Read the next node down in the tree.
1516 error
= xfs_da3_node_read(args
->trans
, args
->dp
, blkno
,
1517 -1, &blk
->bp
, args
->whichfork
);
1520 state
->path
.active
--;
1523 curr
= blk
->bp
->b_addr
;
1524 blk
->magic
= be16_to_cpu(curr
->magic
);
1526 if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
1527 blk
->magic
== XFS_ATTR3_LEAF_MAGIC
) {
1528 blk
->magic
= XFS_ATTR_LEAF_MAGIC
;
1529 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
, NULL
);
1533 if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1534 blk
->magic
== XFS_DIR3_LEAFN_MAGIC
) {
1535 blk
->magic
= XFS_DIR2_LEAFN_MAGIC
;
1536 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
, NULL
);
1540 blk
->magic
= XFS_DA_NODE_MAGIC
;
1544 * Search an intermediate node for a match.
1546 node
= blk
->bp
->b_addr
;
1547 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
1548 btree
= xfs_da3_node_tree_p(node
);
1550 max
= nodehdr
.count
;
1551 blk
->hashval
= be32_to_cpu(btree
[max
- 1].hashval
);
1554 * Binary search. (note: small blocks will skip loop)
1556 probe
= span
= max
/ 2;
1557 hashval
= args
->hashval
;
1560 btreehashval
= be32_to_cpu(btree
[probe
].hashval
);
1561 if (btreehashval
< hashval
)
1563 else if (btreehashval
> hashval
)
1568 ASSERT((probe
>= 0) && (probe
< max
));
1569 ASSERT((span
<= 4) ||
1570 (be32_to_cpu(btree
[probe
].hashval
) == hashval
));
1573 * Since we may have duplicate hashval's, find the first
1574 * matching hashval in the node.
1577 be32_to_cpu(btree
[probe
].hashval
) >= hashval
) {
1580 while (probe
< max
&&
1581 be32_to_cpu(btree
[probe
].hashval
) < hashval
) {
1586 * Pick the right block to descend on.
1589 blk
->index
= max
- 1;
1590 blkno
= be32_to_cpu(btree
[max
- 1].before
);
1593 blkno
= be32_to_cpu(btree
[probe
].before
);
1598 * A leaf block that ends in the hashval that we are interested in
1599 * (final hashval == search hashval) means that the next block may
1600 * contain more entries with the same hashval, shift upward to the
1601 * next leaf and keep searching.
1604 if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
) {
1605 retval
= xfs_dir2_leafn_lookup_int(blk
->bp
, args
,
1606 &blk
->index
, state
);
1607 } else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1608 retval
= xfs_attr3_leaf_lookup_int(blk
->bp
, args
);
1609 blk
->index
= args
->index
;
1610 args
->blkno
= blk
->blkno
;
1613 return XFS_ERROR(EFSCORRUPTED
);
1615 if (((retval
== ENOENT
) || (retval
== ENOATTR
)) &&
1616 (blk
->hashval
== args
->hashval
)) {
1617 error
= xfs_da3_path_shift(state
, &state
->path
, 1, 1,
1623 } else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1624 /* path_shift() gives ENOENT */
1625 retval
= XFS_ERROR(ENOATTR
);
1634 /*========================================================================
1636 *========================================================================*/
1639 * Compare two intermediate nodes for "order".
1643 struct xfs_buf
*node1_bp
,
1644 struct xfs_buf
*node2_bp
)
1646 struct xfs_da_intnode
*node1
;
1647 struct xfs_da_intnode
*node2
;
1648 struct xfs_da_node_entry
*btree1
;
1649 struct xfs_da_node_entry
*btree2
;
1650 struct xfs_da3_icnode_hdr node1hdr
;
1651 struct xfs_da3_icnode_hdr node2hdr
;
1653 node1
= node1_bp
->b_addr
;
1654 node2
= node2_bp
->b_addr
;
1655 xfs_da3_node_hdr_from_disk(&node1hdr
, node1
);
1656 xfs_da3_node_hdr_from_disk(&node2hdr
, node2
);
1657 btree1
= xfs_da3_node_tree_p(node1
);
1658 btree2
= xfs_da3_node_tree_p(node2
);
1660 if (node1hdr
.count
> 0 && node2hdr
.count
> 0 &&
1661 ((be32_to_cpu(btree2
[0].hashval
) < be32_to_cpu(btree1
[0].hashval
)) ||
1662 (be32_to_cpu(btree2
[node2hdr
.count
- 1].hashval
) <
1663 be32_to_cpu(btree1
[node1hdr
.count
- 1].hashval
)))) {
1670 * Link a new block into a doubly linked list of blocks (of whatever type).
1674 struct xfs_da_state
*state
,
1675 struct xfs_da_state_blk
*old_blk
,
1676 struct xfs_da_state_blk
*new_blk
)
1678 struct xfs_da_blkinfo
*old_info
;
1679 struct xfs_da_blkinfo
*new_info
;
1680 struct xfs_da_blkinfo
*tmp_info
;
1681 struct xfs_da_args
*args
;
1687 * Set up environment.
1690 ASSERT(args
!= NULL
);
1691 old_info
= old_blk
->bp
->b_addr
;
1692 new_info
= new_blk
->bp
->b_addr
;
1693 ASSERT(old_blk
->magic
== XFS_DA_NODE_MAGIC
||
1694 old_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1695 old_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1697 switch (old_blk
->magic
) {
1698 case XFS_ATTR_LEAF_MAGIC
:
1699 before
= xfs_attr_leaf_order(old_blk
->bp
, new_blk
->bp
);
1701 case XFS_DIR2_LEAFN_MAGIC
:
1702 before
= xfs_dir2_leafn_order(old_blk
->bp
, new_blk
->bp
);
1704 case XFS_DA_NODE_MAGIC
:
1705 before
= xfs_da3_node_order(old_blk
->bp
, new_blk
->bp
);
1710 * Link blocks in appropriate order.
1714 * Link new block in before existing block.
1716 trace_xfs_da_link_before(args
);
1717 new_info
->forw
= cpu_to_be32(old_blk
->blkno
);
1718 new_info
->back
= old_info
->back
;
1719 if (old_info
->back
) {
1720 error
= xfs_da3_node_read(args
->trans
, args
->dp
,
1721 be32_to_cpu(old_info
->back
),
1722 -1, &bp
, args
->whichfork
);
1726 tmp_info
= bp
->b_addr
;
1727 ASSERT(tmp_info
->magic
== old_info
->magic
);
1728 ASSERT(be32_to_cpu(tmp_info
->forw
) == old_blk
->blkno
);
1729 tmp_info
->forw
= cpu_to_be32(new_blk
->blkno
);
1730 xfs_trans_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1732 old_info
->back
= cpu_to_be32(new_blk
->blkno
);
1735 * Link new block in after existing block.
1737 trace_xfs_da_link_after(args
);
1738 new_info
->forw
= old_info
->forw
;
1739 new_info
->back
= cpu_to_be32(old_blk
->blkno
);
1740 if (old_info
->forw
) {
1741 error
= xfs_da3_node_read(args
->trans
, args
->dp
,
1742 be32_to_cpu(old_info
->forw
),
1743 -1, &bp
, args
->whichfork
);
1747 tmp_info
= bp
->b_addr
;
1748 ASSERT(tmp_info
->magic
== old_info
->magic
);
1749 ASSERT(be32_to_cpu(tmp_info
->back
) == old_blk
->blkno
);
1750 tmp_info
->back
= cpu_to_be32(new_blk
->blkno
);
1751 xfs_trans_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1753 old_info
->forw
= cpu_to_be32(new_blk
->blkno
);
1756 xfs_trans_log_buf(args
->trans
, old_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1757 xfs_trans_log_buf(args
->trans
, new_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1762 * Unlink a block from a doubly linked list of blocks.
1764 STATIC
int /* error */
1766 struct xfs_da_state
*state
,
1767 struct xfs_da_state_blk
*drop_blk
,
1768 struct xfs_da_state_blk
*save_blk
)
1770 struct xfs_da_blkinfo
*drop_info
;
1771 struct xfs_da_blkinfo
*save_info
;
1772 struct xfs_da_blkinfo
*tmp_info
;
1773 struct xfs_da_args
*args
;
1778 * Set up environment.
1781 ASSERT(args
!= NULL
);
1782 save_info
= save_blk
->bp
->b_addr
;
1783 drop_info
= drop_blk
->bp
->b_addr
;
1784 ASSERT(save_blk
->magic
== XFS_DA_NODE_MAGIC
||
1785 save_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1786 save_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1787 ASSERT(save_blk
->magic
== drop_blk
->magic
);
1788 ASSERT((be32_to_cpu(save_info
->forw
) == drop_blk
->blkno
) ||
1789 (be32_to_cpu(save_info
->back
) == drop_blk
->blkno
));
1790 ASSERT((be32_to_cpu(drop_info
->forw
) == save_blk
->blkno
) ||
1791 (be32_to_cpu(drop_info
->back
) == save_blk
->blkno
));
1794 * Unlink the leaf block from the doubly linked chain of leaves.
1796 if (be32_to_cpu(save_info
->back
) == drop_blk
->blkno
) {
1797 trace_xfs_da_unlink_back(args
);
1798 save_info
->back
= drop_info
->back
;
1799 if (drop_info
->back
) {
1800 error
= xfs_da3_node_read(args
->trans
, args
->dp
,
1801 be32_to_cpu(drop_info
->back
),
1802 -1, &bp
, args
->whichfork
);
1806 tmp_info
= bp
->b_addr
;
1807 ASSERT(tmp_info
->magic
== save_info
->magic
);
1808 ASSERT(be32_to_cpu(tmp_info
->forw
) == drop_blk
->blkno
);
1809 tmp_info
->forw
= cpu_to_be32(save_blk
->blkno
);
1810 xfs_trans_log_buf(args
->trans
, bp
, 0,
1811 sizeof(*tmp_info
) - 1);
1814 trace_xfs_da_unlink_forward(args
);
1815 save_info
->forw
= drop_info
->forw
;
1816 if (drop_info
->forw
) {
1817 error
= xfs_da3_node_read(args
->trans
, args
->dp
,
1818 be32_to_cpu(drop_info
->forw
),
1819 -1, &bp
, args
->whichfork
);
1823 tmp_info
= bp
->b_addr
;
1824 ASSERT(tmp_info
->magic
== save_info
->magic
);
1825 ASSERT(be32_to_cpu(tmp_info
->back
) == drop_blk
->blkno
);
1826 tmp_info
->back
= cpu_to_be32(save_blk
->blkno
);
1827 xfs_trans_log_buf(args
->trans
, bp
, 0,
1828 sizeof(*tmp_info
) - 1);
1832 xfs_trans_log_buf(args
->trans
, save_blk
->bp
, 0, sizeof(*save_info
) - 1);
1837 * Move a path "forward" or "!forward" one block at the current level.
1839 * This routine will adjust a "path" to point to the next block
1840 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1841 * Btree, including updating pointers to the intermediate nodes between
1842 * the new bottom and the root.
1846 struct xfs_da_state
*state
,
1847 struct xfs_da_state_path
*path
,
1852 struct xfs_da_state_blk
*blk
;
1853 struct xfs_da_blkinfo
*info
;
1854 struct xfs_da_intnode
*node
;
1855 struct xfs_da_args
*args
;
1856 struct xfs_da_node_entry
*btree
;
1857 struct xfs_da3_icnode_hdr nodehdr
;
1858 xfs_dablk_t blkno
= 0;
1862 trace_xfs_da_path_shift(state
->args
);
1865 * Roll up the Btree looking for the first block where our
1866 * current index is not at the edge of the block. Note that
1867 * we skip the bottom layer because we want the sibling block.
1870 ASSERT(args
!= NULL
);
1871 ASSERT(path
!= NULL
);
1872 ASSERT((path
->active
> 0) && (path
->active
< XFS_DA_NODE_MAXDEPTH
));
1873 level
= (path
->active
-1) - 1; /* skip bottom layer in path */
1874 for (blk
= &path
->blk
[level
]; level
>= 0; blk
--, level
--) {
1875 node
= blk
->bp
->b_addr
;
1876 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
1877 btree
= xfs_da3_node_tree_p(node
);
1879 if (forward
&& (blk
->index
< nodehdr
.count
- 1)) {
1881 blkno
= be32_to_cpu(btree
[blk
->index
].before
);
1883 } else if (!forward
&& (blk
->index
> 0)) {
1885 blkno
= be32_to_cpu(btree
[blk
->index
].before
);
1890 *result
= XFS_ERROR(ENOENT
); /* we're out of our tree */
1891 ASSERT(args
->op_flags
& XFS_DA_OP_OKNOENT
);
1896 * Roll down the edge of the subtree until we reach the
1897 * same depth we were at originally.
1899 for (blk
++, level
++; level
< path
->active
; blk
++, level
++) {
1901 * Release the old block.
1902 * (if it's dirty, trans won't actually let go)
1905 xfs_trans_brelse(args
->trans
, blk
->bp
);
1908 * Read the next child block.
1911 error
= xfs_da3_node_read(args
->trans
, args
->dp
, blkno
, -1,
1912 &blk
->bp
, args
->whichfork
);
1915 info
= blk
->bp
->b_addr
;
1916 ASSERT(info
->magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
) ||
1917 info
->magic
== cpu_to_be16(XFS_DA3_NODE_MAGIC
) ||
1918 info
->magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
) ||
1919 info
->magic
== cpu_to_be16(XFS_DIR3_LEAFN_MAGIC
) ||
1920 info
->magic
== cpu_to_be16(XFS_ATTR_LEAF_MAGIC
) ||
1921 info
->magic
== cpu_to_be16(XFS_ATTR3_LEAF_MAGIC
));
1925 * Note: we flatten the magic number to a single type so we
1926 * don't have to compare against crc/non-crc types elsewhere.
1928 switch (be16_to_cpu(info
->magic
)) {
1929 case XFS_DA_NODE_MAGIC
:
1930 case XFS_DA3_NODE_MAGIC
:
1931 blk
->magic
= XFS_DA_NODE_MAGIC
;
1932 node
= (xfs_da_intnode_t
*)info
;
1933 xfs_da3_node_hdr_from_disk(&nodehdr
, node
);
1934 btree
= xfs_da3_node_tree_p(node
);
1935 blk
->hashval
= be32_to_cpu(btree
[nodehdr
.count
- 1].hashval
);
1939 blk
->index
= nodehdr
.count
- 1;
1940 blkno
= be32_to_cpu(btree
[blk
->index
].before
);
1942 case XFS_ATTR_LEAF_MAGIC
:
1943 case XFS_ATTR3_LEAF_MAGIC
:
1944 blk
->magic
= XFS_ATTR_LEAF_MAGIC
;
1945 ASSERT(level
== path
->active
-1);
1947 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
,
1950 case XFS_DIR2_LEAFN_MAGIC
:
1951 case XFS_DIR3_LEAFN_MAGIC
:
1952 blk
->magic
= XFS_DIR2_LEAFN_MAGIC
;
1953 ASSERT(level
== path
->active
-1);
1955 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
,
1968 /*========================================================================
1970 *========================================================================*/
1973 * Implement a simple hash on a character string.
1974 * Rotate the hash value by 7 bits, then XOR each character in.
1975 * This is implemented with some source-level loop unrolling.
1978 xfs_da_hashname(const __uint8_t
*name
, int namelen
)
1983 * Do four characters at a time as long as we can.
1985 for (hash
= 0; namelen
>= 4; namelen
-= 4, name
+= 4)
1986 hash
= (name
[0] << 21) ^ (name
[1] << 14) ^ (name
[2] << 7) ^
1987 (name
[3] << 0) ^ rol32(hash
, 7 * 4);
1990 * Now do the rest of the characters.
1994 return (name
[0] << 14) ^ (name
[1] << 7) ^ (name
[2] << 0) ^
1997 return (name
[0] << 7) ^ (name
[1] << 0) ^ rol32(hash
, 7 * 2);
1999 return (name
[0] << 0) ^ rol32(hash
, 7 * 1);
2000 default: /* case 0: */
2007 struct xfs_da_args
*args
,
2008 const unsigned char *name
,
2011 return (args
->namelen
== len
&& memcmp(args
->name
, name
, len
) == 0) ?
2012 XFS_CMP_EXACT
: XFS_CMP_DIFFERENT
;
2016 xfs_default_hashname(
2017 struct xfs_name
*name
)
2019 return xfs_da_hashname(name
->name
, name
->len
);
2022 const struct xfs_nameops xfs_default_nameops
= {
2023 .hashname
= xfs_default_hashname
,
2024 .compname
= xfs_da_compname
2028 xfs_da_grow_inode_int(
2029 struct xfs_da_args
*args
,
2033 struct xfs_trans
*tp
= args
->trans
;
2034 struct xfs_inode
*dp
= args
->dp
;
2035 int w
= args
->whichfork
;
2036 xfs_drfsbno_t nblks
= dp
->i_d
.di_nblocks
;
2037 struct xfs_bmbt_irec map
, *mapp
;
2038 int nmap
, error
, got
, i
, mapi
;
2041 * Find a spot in the file space to put the new block.
2043 error
= xfs_bmap_first_unused(tp
, dp
, count
, bno
, w
);
2048 * Try mapping it in one filesystem block.
2051 ASSERT(args
->firstblock
!= NULL
);
2052 error
= xfs_bmapi_write(tp
, dp
, *bno
, count
,
2053 xfs_bmapi_aflag(w
)|XFS_BMAPI_METADATA
|XFS_BMAPI_CONTIG
,
2054 args
->firstblock
, args
->total
, &map
, &nmap
,
2063 } else if (nmap
== 0 && count
> 1) {
2068 * If we didn't get it and the block might work if fragmented,
2069 * try without the CONTIG flag. Loop until we get it all.
2071 mapp
= kmem_alloc(sizeof(*mapp
) * count
, KM_SLEEP
);
2072 for (b
= *bno
, mapi
= 0; b
< *bno
+ count
; ) {
2073 nmap
= MIN(XFS_BMAP_MAX_NMAP
, count
);
2074 c
= (int)(*bno
+ count
- b
);
2075 error
= xfs_bmapi_write(tp
, dp
, b
, c
,
2076 xfs_bmapi_aflag(w
)|XFS_BMAPI_METADATA
,
2077 args
->firstblock
, args
->total
,
2078 &mapp
[mapi
], &nmap
, args
->flist
);
2084 b
= mapp
[mapi
- 1].br_startoff
+
2085 mapp
[mapi
- 1].br_blockcount
;
2093 * Count the blocks we got, make sure it matches the total.
2095 for (i
= 0, got
= 0; i
< mapi
; i
++)
2096 got
+= mapp
[i
].br_blockcount
;
2097 if (got
!= count
|| mapp
[0].br_startoff
!= *bno
||
2098 mapp
[mapi
- 1].br_startoff
+ mapp
[mapi
- 1].br_blockcount
!=
2100 error
= XFS_ERROR(ENOSPC
);
2104 /* account for newly allocated blocks in reserved blocks total */
2105 args
->total
-= dp
->i_d
.di_nblocks
- nblks
;
2114 * Add a block to the btree ahead of the file.
2115 * Return the new block number to the caller.
2119 struct xfs_da_args
*args
,
2120 xfs_dablk_t
*new_blkno
)
2126 trace_xfs_da_grow_inode(args
);
2128 if (args
->whichfork
== XFS_DATA_FORK
) {
2129 bno
= args
->dp
->i_mount
->m_dirleafblk
;
2130 count
= args
->dp
->i_mount
->m_dirblkfsbs
;
2136 error
= xfs_da_grow_inode_int(args
, &bno
, count
);
2138 *new_blkno
= (xfs_dablk_t
)bno
;
2143 * Ick. We need to always be able to remove a btree block, even
2144 * if there's no space reservation because the filesystem is full.
2145 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
2146 * It swaps the target block with the last block in the file. The
2147 * last block in the file can always be removed since it can't cause
2148 * a bmap btree split to do that.
2151 xfs_da3_swap_lastblock(
2152 struct xfs_da_args
*args
,
2153 xfs_dablk_t
*dead_blknop
,
2154 struct xfs_buf
**dead_bufp
)
2156 struct xfs_da_blkinfo
*dead_info
;
2157 struct xfs_da_blkinfo
*sib_info
;
2158 struct xfs_da_intnode
*par_node
;
2159 struct xfs_da_intnode
*dead_node
;
2160 struct xfs_dir2_leaf
*dead_leaf2
;
2161 struct xfs_da_node_entry
*btree
;
2162 struct xfs_da3_icnode_hdr par_hdr
;
2163 struct xfs_inode
*ip
;
2164 struct xfs_trans
*tp
;
2165 struct xfs_mount
*mp
;
2166 struct xfs_buf
*dead_buf
;
2167 struct xfs_buf
*last_buf
;
2168 struct xfs_buf
*sib_buf
;
2169 struct xfs_buf
*par_buf
;
2170 xfs_dahash_t dead_hash
;
2171 xfs_fileoff_t lastoff
;
2172 xfs_dablk_t dead_blkno
;
2173 xfs_dablk_t last_blkno
;
2174 xfs_dablk_t sib_blkno
;
2175 xfs_dablk_t par_blkno
;
2182 trace_xfs_da_swap_lastblock(args
);
2184 dead_buf
= *dead_bufp
;
2185 dead_blkno
= *dead_blknop
;
2188 w
= args
->whichfork
;
2189 ASSERT(w
== XFS_DATA_FORK
);
2191 lastoff
= mp
->m_dirfreeblk
;
2192 error
= xfs_bmap_last_before(tp
, ip
, &lastoff
, w
);
2195 if (unlikely(lastoff
== 0)) {
2196 XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW
,
2198 return XFS_ERROR(EFSCORRUPTED
);
2201 * Read the last block in the btree space.
2203 last_blkno
= (xfs_dablk_t
)lastoff
- mp
->m_dirblkfsbs
;
2204 error
= xfs_da3_node_read(tp
, ip
, last_blkno
, -1, &last_buf
, w
);
2208 * Copy the last block into the dead buffer and log it.
2210 memcpy(dead_buf
->b_addr
, last_buf
->b_addr
, mp
->m_dirblksize
);
2211 xfs_trans_log_buf(tp
, dead_buf
, 0, mp
->m_dirblksize
- 1);
2212 dead_info
= dead_buf
->b_addr
;
2214 * Get values from the moved block.
2216 if (dead_info
->magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
) ||
2217 dead_info
->magic
== cpu_to_be16(XFS_DIR3_LEAFN_MAGIC
)) {
2218 struct xfs_dir3_icleaf_hdr leafhdr
;
2219 struct xfs_dir2_leaf_entry
*ents
;
2221 dead_leaf2
= (xfs_dir2_leaf_t
*)dead_info
;
2222 xfs_dir3_leaf_hdr_from_disk(&leafhdr
, dead_leaf2
);
2223 ents
= xfs_dir3_leaf_ents_p(dead_leaf2
);
2225 dead_hash
= be32_to_cpu(ents
[leafhdr
.count
- 1].hashval
);
2227 struct xfs_da3_icnode_hdr deadhdr
;
2229 dead_node
= (xfs_da_intnode_t
*)dead_info
;
2230 xfs_da3_node_hdr_from_disk(&deadhdr
, dead_node
);
2231 btree
= xfs_da3_node_tree_p(dead_node
);
2232 dead_level
= deadhdr
.level
;
2233 dead_hash
= be32_to_cpu(btree
[deadhdr
.count
- 1].hashval
);
2235 sib_buf
= par_buf
= NULL
;
2237 * If the moved block has a left sibling, fix up the pointers.
2239 if ((sib_blkno
= be32_to_cpu(dead_info
->back
))) {
2240 error
= xfs_da3_node_read(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
);
2243 sib_info
= sib_buf
->b_addr
;
2245 be32_to_cpu(sib_info
->forw
) != last_blkno
||
2246 sib_info
->magic
!= dead_info
->magic
)) {
2247 XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
2248 XFS_ERRLEVEL_LOW
, mp
);
2249 error
= XFS_ERROR(EFSCORRUPTED
);
2252 sib_info
->forw
= cpu_to_be32(dead_blkno
);
2253 xfs_trans_log_buf(tp
, sib_buf
,
2254 XFS_DA_LOGRANGE(sib_info
, &sib_info
->forw
,
2255 sizeof(sib_info
->forw
)));
2259 * If the moved block has a right sibling, fix up the pointers.
2261 if ((sib_blkno
= be32_to_cpu(dead_info
->forw
))) {
2262 error
= xfs_da3_node_read(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
);
2265 sib_info
= sib_buf
->b_addr
;
2267 be32_to_cpu(sib_info
->back
) != last_blkno
||
2268 sib_info
->magic
!= dead_info
->magic
)) {
2269 XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
2270 XFS_ERRLEVEL_LOW
, mp
);
2271 error
= XFS_ERROR(EFSCORRUPTED
);
2274 sib_info
->back
= cpu_to_be32(dead_blkno
);
2275 xfs_trans_log_buf(tp
, sib_buf
,
2276 XFS_DA_LOGRANGE(sib_info
, &sib_info
->back
,
2277 sizeof(sib_info
->back
)));
2280 par_blkno
= mp
->m_dirleafblk
;
2283 * Walk down the tree looking for the parent of the moved block.
2286 error
= xfs_da3_node_read(tp
, ip
, par_blkno
, -1, &par_buf
, w
);
2289 par_node
= par_buf
->b_addr
;
2290 xfs_da3_node_hdr_from_disk(&par_hdr
, par_node
);
2291 if (level
>= 0 && level
!= par_hdr
.level
+ 1) {
2292 XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
2293 XFS_ERRLEVEL_LOW
, mp
);
2294 error
= XFS_ERROR(EFSCORRUPTED
);
2297 level
= par_hdr
.level
;
2298 btree
= xfs_da3_node_tree_p(par_node
);
2300 entno
< par_hdr
.count
&&
2301 be32_to_cpu(btree
[entno
].hashval
) < dead_hash
;
2304 if (entno
== par_hdr
.count
) {
2305 XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
2306 XFS_ERRLEVEL_LOW
, mp
);
2307 error
= XFS_ERROR(EFSCORRUPTED
);
2310 par_blkno
= be32_to_cpu(btree
[entno
].before
);
2311 if (level
== dead_level
+ 1)
2313 xfs_trans_brelse(tp
, par_buf
);
2317 * We're in the right parent block.
2318 * Look for the right entry.
2322 entno
< par_hdr
.count
&&
2323 be32_to_cpu(btree
[entno
].before
) != last_blkno
;
2326 if (entno
< par_hdr
.count
)
2328 par_blkno
= par_hdr
.forw
;
2329 xfs_trans_brelse(tp
, par_buf
);
2331 if (unlikely(par_blkno
== 0)) {
2332 XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
2333 XFS_ERRLEVEL_LOW
, mp
);
2334 error
= XFS_ERROR(EFSCORRUPTED
);
2337 error
= xfs_da3_node_read(tp
, ip
, par_blkno
, -1, &par_buf
, w
);
2340 par_node
= par_buf
->b_addr
;
2341 xfs_da3_node_hdr_from_disk(&par_hdr
, par_node
);
2342 if (par_hdr
.level
!= level
) {
2343 XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
2344 XFS_ERRLEVEL_LOW
, mp
);
2345 error
= XFS_ERROR(EFSCORRUPTED
);
2348 btree
= xfs_da3_node_tree_p(par_node
);
2352 * Update the parent entry pointing to the moved block.
2354 btree
[entno
].before
= cpu_to_be32(dead_blkno
);
2355 xfs_trans_log_buf(tp
, par_buf
,
2356 XFS_DA_LOGRANGE(par_node
, &btree
[entno
].before
,
2357 sizeof(btree
[entno
].before
)));
2358 *dead_blknop
= last_blkno
;
2359 *dead_bufp
= last_buf
;
2363 xfs_trans_brelse(tp
, par_buf
);
2365 xfs_trans_brelse(tp
, sib_buf
);
2366 xfs_trans_brelse(tp
, last_buf
);
2371 * Remove a btree block from a directory or attribute.
2374 xfs_da_shrink_inode(
2375 xfs_da_args_t
*args
,
2376 xfs_dablk_t dead_blkno
,
2377 struct xfs_buf
*dead_buf
)
2380 int done
, error
, w
, count
;
2384 trace_xfs_da_shrink_inode(args
);
2387 w
= args
->whichfork
;
2390 if (w
== XFS_DATA_FORK
)
2391 count
= mp
->m_dirblkfsbs
;
2396 * Remove extents. If we get ENOSPC for a dir we have to move
2397 * the last block to the place we want to kill.
2399 error
= xfs_bunmapi(tp
, dp
, dead_blkno
, count
,
2400 xfs_bmapi_aflag(w
)|XFS_BMAPI_METADATA
,
2401 0, args
->firstblock
, args
->flist
, &done
);
2402 if (error
== ENOSPC
) {
2403 if (w
!= XFS_DATA_FORK
)
2405 error
= xfs_da3_swap_lastblock(args
, &dead_blkno
,
2413 xfs_trans_binval(tp
, dead_buf
);
2418 * See if the mapping(s) for this btree block are valid, i.e.
2419 * don't contain holes, are logically contiguous, and cover the whole range.
2422 xfs_da_map_covers_blocks(
2424 xfs_bmbt_irec_t
*mapp
,
2431 for (i
= 0, off
= bno
; i
< nmap
; i
++) {
2432 if (mapp
[i
].br_startblock
== HOLESTARTBLOCK
||
2433 mapp
[i
].br_startblock
== DELAYSTARTBLOCK
) {
2436 if (off
!= mapp
[i
].br_startoff
) {
2439 off
+= mapp
[i
].br_blockcount
;
2441 return off
== bno
+ count
;
2445 * Convert a struct xfs_bmbt_irec to a struct xfs_buf_map.
2447 * For the single map case, it is assumed that the caller has provided a pointer
2448 * to a valid xfs_buf_map. For the multiple map case, this function will
2449 * allocate the xfs_buf_map to hold all the maps and replace the caller's single
2450 * map pointer with the allocated map.
2453 xfs_buf_map_from_irec(
2454 struct xfs_mount
*mp
,
2455 struct xfs_buf_map
**mapp
,
2456 unsigned int *nmaps
,
2457 struct xfs_bmbt_irec
*irecs
,
2458 unsigned int nirecs
)
2460 struct xfs_buf_map
*map
;
2463 ASSERT(*nmaps
== 1);
2464 ASSERT(nirecs
>= 1);
2467 map
= kmem_zalloc(nirecs
* sizeof(struct xfs_buf_map
), KM_SLEEP
);
2475 for (i
= 0; i
< *nmaps
; i
++) {
2476 ASSERT(irecs
[i
].br_startblock
!= DELAYSTARTBLOCK
&&
2477 irecs
[i
].br_startblock
!= HOLESTARTBLOCK
);
2478 map
[i
].bm_bn
= XFS_FSB_TO_DADDR(mp
, irecs
[i
].br_startblock
);
2479 map
[i
].bm_len
= XFS_FSB_TO_BB(mp
, irecs
[i
].br_blockcount
);
2485 * Map the block we are given ready for reading. There are three possible return
2487 * -1 - will be returned if we land in a hole and mappedbno == -2 so the
2488 * caller knows not to execute a subsequent read.
2489 * 0 - if we mapped the block successfully
2490 * >0 - positive error number if there was an error.
2494 struct xfs_trans
*trans
,
2495 struct xfs_inode
*dp
,
2497 xfs_daddr_t mappedbno
,
2499 struct xfs_buf_map
**map
,
2502 struct xfs_mount
*mp
= dp
->i_mount
;
2505 struct xfs_bmbt_irec irec
;
2506 struct xfs_bmbt_irec
*irecs
= &irec
;
2509 ASSERT(map
&& *map
);
2510 ASSERT(*nmaps
== 1);
2512 nfsb
= (whichfork
== XFS_DATA_FORK
) ? mp
->m_dirblkfsbs
: 1;
2515 * Caller doesn't have a mapping. -2 means don't complain
2516 * if we land in a hole.
2518 if (mappedbno
== -1 || mappedbno
== -2) {
2520 * Optimize the one-block case.
2523 irecs
= kmem_zalloc(sizeof(irec
) * nfsb
, KM_SLEEP
);
2526 error
= xfs_bmapi_read(dp
, (xfs_fileoff_t
)bno
, nfsb
, irecs
,
2527 &nirecs
, xfs_bmapi_aflag(whichfork
));
2531 irecs
->br_startblock
= XFS_DADDR_TO_FSB(mp
, mappedbno
);
2532 irecs
->br_startoff
= (xfs_fileoff_t
)bno
;
2533 irecs
->br_blockcount
= nfsb
;
2534 irecs
->br_state
= 0;
2538 if (!xfs_da_map_covers_blocks(nirecs
, irecs
, bno
, nfsb
)) {
2539 error
= mappedbno
== -2 ? -1 : XFS_ERROR(EFSCORRUPTED
);
2540 if (unlikely(error
== EFSCORRUPTED
)) {
2541 if (xfs_error_level
>= XFS_ERRLEVEL_LOW
) {
2543 xfs_alert(mp
, "%s: bno %lld dir: inode %lld",
2544 __func__
, (long long)bno
,
2545 (long long)dp
->i_ino
);
2546 for (i
= 0; i
< *nmaps
; i
++) {
2548 "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
2550 (long long)irecs
[i
].br_startoff
,
2551 (long long)irecs
[i
].br_startblock
,
2552 (long long)irecs
[i
].br_blockcount
,
2556 XFS_ERROR_REPORT("xfs_da_do_buf(1)",
2557 XFS_ERRLEVEL_LOW
, mp
);
2561 error
= xfs_buf_map_from_irec(mp
, map
, nmaps
, irecs
, nirecs
);
2569 * Get a buffer for the dir/attr block.
2573 struct xfs_trans
*trans
,
2574 struct xfs_inode
*dp
,
2576 xfs_daddr_t mappedbno
,
2577 struct xfs_buf
**bpp
,
2581 struct xfs_buf_map map
;
2582 struct xfs_buf_map
*mapp
;
2589 error
= xfs_dabuf_map(trans
, dp
, bno
, mappedbno
, whichfork
,
2592 /* mapping a hole is not an error, but we don't continue */
2598 bp
= xfs_trans_get_buf_map(trans
, dp
->i_mount
->m_ddev_targp
,
2600 error
= bp
? bp
->b_error
: XFS_ERROR(EIO
);
2602 xfs_trans_brelse(trans
, bp
);
2616 * Get a buffer for the dir/attr block, fill in the contents.
2620 struct xfs_trans
*trans
,
2621 struct xfs_inode
*dp
,
2623 xfs_daddr_t mappedbno
,
2624 struct xfs_buf
**bpp
,
2626 const struct xfs_buf_ops
*ops
)
2629 struct xfs_buf_map map
;
2630 struct xfs_buf_map
*mapp
;
2637 error
= xfs_dabuf_map(trans
, dp
, bno
, mappedbno
, whichfork
,
2640 /* mapping a hole is not an error, but we don't continue */
2646 error
= xfs_trans_read_buf_map(dp
->i_mount
, trans
,
2647 dp
->i_mount
->m_ddev_targp
,
2648 mapp
, nmap
, 0, &bp
, ops
);
2652 if (whichfork
== XFS_ATTR_FORK
)
2653 xfs_buf_set_ref(bp
, XFS_ATTR_BTREE_REF
);
2655 xfs_buf_set_ref(bp
, XFS_DIR_BTREE_REF
);
2658 * This verification code will be moved to a CRC verification callback
2659 * function so just leave it here unchanged until then.
2662 xfs_dir2_data_hdr_t
*hdr
= bp
->b_addr
;
2663 xfs_dir2_free_t
*free
= bp
->b_addr
;
2664 xfs_da_blkinfo_t
*info
= bp
->b_addr
;
2666 struct xfs_mount
*mp
= dp
->i_mount
;
2668 magic
= be16_to_cpu(info
->magic
);
2669 magic1
= be32_to_cpu(hdr
->magic
);
2671 XFS_TEST_ERROR((magic
!= XFS_DA_NODE_MAGIC
) &&
2672 (magic
!= XFS_DA3_NODE_MAGIC
) &&
2673 (magic
!= XFS_ATTR_LEAF_MAGIC
) &&
2674 (magic
!= XFS_ATTR3_LEAF_MAGIC
) &&
2675 (magic
!= XFS_DIR2_LEAF1_MAGIC
) &&
2676 (magic
!= XFS_DIR3_LEAF1_MAGIC
) &&
2677 (magic
!= XFS_DIR2_LEAFN_MAGIC
) &&
2678 (magic
!= XFS_DIR3_LEAFN_MAGIC
) &&
2679 (magic1
!= XFS_DIR2_BLOCK_MAGIC
) &&
2680 (magic1
!= XFS_DIR3_BLOCK_MAGIC
) &&
2681 (magic1
!= XFS_DIR2_DATA_MAGIC
) &&
2682 (magic1
!= XFS_DIR3_DATA_MAGIC
) &&
2684 cpu_to_be32(XFS_DIR2_FREE_MAGIC
)) &&
2686 cpu_to_be32(XFS_DIR3_FREE_MAGIC
)),
2687 mp
, XFS_ERRTAG_DA_READ_BUF
,
2688 XFS_RANDOM_DA_READ_BUF
))) {
2689 trace_xfs_da_btree_corrupt(bp
, _RET_IP_
);
2690 XFS_CORRUPTION_ERROR("xfs_da_do_buf(2)",
2691 XFS_ERRLEVEL_LOW
, mp
, info
);
2692 error
= XFS_ERROR(EFSCORRUPTED
);
2693 xfs_trans_brelse(trans
, bp
);
2706 * Readahead the dir/attr block.
2710 struct xfs_trans
*trans
,
2711 struct xfs_inode
*dp
,
2713 xfs_daddr_t mappedbno
,
2715 const struct xfs_buf_ops
*ops
)
2717 struct xfs_buf_map map
;
2718 struct xfs_buf_map
*mapp
;
2724 error
= xfs_dabuf_map(trans
, dp
, bno
, mappedbno
, whichfork
,
2727 /* mapping a hole is not an error, but we don't continue */
2733 mappedbno
= mapp
[0].bm_bn
;
2734 xfs_buf_readahead_map(dp
->i_mount
->m_ddev_targp
, mapp
, nmap
, ops
);