2 * Copyright (c) 2000-2005 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
34 #include "xfs_types.h"
38 #include "xfs_trans.h"
43 #include "xfs_dmapi.h"
44 #include "xfs_mount.h"
45 #include "xfs_da_btree.h"
46 #include "xfs_bmap_btree.h"
47 #include "xfs_alloc_btree.h"
48 #include "xfs_ialloc_btree.h"
49 #include "xfs_dir_sf.h"
50 #include "xfs_dir2_sf.h"
51 #include "xfs_attr_sf.h"
52 #include "xfs_dinode.h"
53 #include "xfs_inode.h"
54 #include "xfs_inode_item.h"
55 #include "xfs_alloc.h"
56 #include "xfs_btree.h"
59 #include "xfs_attr_leaf.h"
60 #include "xfs_dir_leaf.h"
61 #include "xfs_dir2_data.h"
62 #include "xfs_dir2_leaf.h"
63 #include "xfs_dir2_block.h"
64 #include "xfs_dir2_node.h"
65 #include "xfs_error.h"
70 * Routines to implement directories as Btrees of hashed names.
73 /*========================================================================
74 * Function prototypes for the kernel.
75 *========================================================================*/
78 * Routines used for growing the Btree.
80 STATIC
int xfs_da_root_split(xfs_da_state_t
*state
,
81 xfs_da_state_blk_t
*existing_root
,
82 xfs_da_state_blk_t
*new_child
);
83 STATIC
int xfs_da_node_split(xfs_da_state_t
*state
,
84 xfs_da_state_blk_t
*existing_blk
,
85 xfs_da_state_blk_t
*split_blk
,
86 xfs_da_state_blk_t
*blk_to_add
,
89 STATIC
void xfs_da_node_rebalance(xfs_da_state_t
*state
,
90 xfs_da_state_blk_t
*node_blk_1
,
91 xfs_da_state_blk_t
*node_blk_2
);
92 STATIC
void xfs_da_node_add(xfs_da_state_t
*state
,
93 xfs_da_state_blk_t
*old_node_blk
,
94 xfs_da_state_blk_t
*new_node_blk
);
97 * Routines used for shrinking the Btree.
99 STATIC
int xfs_da_root_join(xfs_da_state_t
*state
,
100 xfs_da_state_blk_t
*root_blk
);
101 STATIC
int xfs_da_node_toosmall(xfs_da_state_t
*state
, int *retval
);
102 STATIC
void xfs_da_node_remove(xfs_da_state_t
*state
,
103 xfs_da_state_blk_t
*drop_blk
);
104 STATIC
void xfs_da_node_unbalance(xfs_da_state_t
*state
,
105 xfs_da_state_blk_t
*src_node_blk
,
106 xfs_da_state_blk_t
*dst_node_blk
);
111 STATIC uint
xfs_da_node_lasthash(xfs_dabuf_t
*bp
, int *count
);
112 STATIC
int xfs_da_node_order(xfs_dabuf_t
*node1_bp
, xfs_dabuf_t
*node2_bp
);
113 STATIC xfs_dabuf_t
*xfs_da_buf_make(int nbuf
, xfs_buf_t
**bps
, inst_t
*ra
);
114 STATIC
int xfs_da_blk_unlink(xfs_da_state_t
*state
,
115 xfs_da_state_blk_t
*drop_blk
,
116 xfs_da_state_blk_t
*save_blk
);
117 STATIC
void xfs_da_state_kill_altpath(xfs_da_state_t
*state
);
119 /*========================================================================
120 * Routines used for growing the Btree.
121 *========================================================================*/
124 * Create the initial contents of an intermediate node.
127 xfs_da_node_create(xfs_da_args_t
*args
, xfs_dablk_t blkno
, int level
,
128 xfs_dabuf_t
**bpp
, int whichfork
)
130 xfs_da_intnode_t
*node
;
136 error
= xfs_da_get_buf(tp
, args
->dp
, blkno
, -1, &bp
, whichfork
);
141 node
->hdr
.info
.forw
= 0;
142 node
->hdr
.info
.back
= 0;
143 INT_SET(node
->hdr
.info
.magic
, ARCH_CONVERT
, XFS_DA_NODE_MAGIC
);
144 node
->hdr
.info
.pad
= 0;
146 INT_SET(node
->hdr
.level
, ARCH_CONVERT
, level
);
148 xfs_da_log_buf(tp
, bp
,
149 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
156 * Split a leaf node, rebalance, then possibly split
157 * intermediate nodes, rebalance, etc.
160 xfs_da_split(xfs_da_state_t
*state
)
162 xfs_da_state_blk_t
*oldblk
, *newblk
, *addblk
;
163 xfs_da_intnode_t
*node
;
165 int max
, action
, error
, i
;
168 * Walk back up the tree splitting/inserting/adjusting as necessary.
169 * If we need to insert and there isn't room, split the node, then
170 * decide which fragment to insert the new block from below into.
171 * Note that we may split the root this way, but we need more fixup.
173 max
= state
->path
.active
- 1;
174 ASSERT((max
>= 0) && (max
< XFS_DA_NODE_MAXDEPTH
));
175 ASSERT(state
->path
.blk
[max
].magic
== XFS_ATTR_LEAF_MAGIC
||
176 state
->path
.blk
[max
].magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
));
178 addblk
= &state
->path
.blk
[max
]; /* initial dummy value */
179 for (i
= max
; (i
>= 0) && addblk
; state
->path
.active
--, i
--) {
180 oldblk
= &state
->path
.blk
[i
];
181 newblk
= &state
->altpath
.blk
[i
];
184 * If a leaf node then
185 * Allocate a new leaf node, then rebalance across them.
186 * else if an intermediate node then
187 * We split on the last layer, must we split the node?
189 switch (oldblk
->magic
) {
190 case XFS_ATTR_LEAF_MAGIC
:
191 error
= xfs_attr_leaf_split(state
, oldblk
, newblk
);
192 if ((error
!= 0) && (error
!= ENOSPC
)) {
193 return(error
); /* GROT: attr is inconsistent */
200 * Entry wouldn't fit, split the leaf again.
202 state
->extravalid
= 1;
204 state
->extraafter
= 0; /* before newblk */
205 error
= xfs_attr_leaf_split(state
, oldblk
,
208 state
->extraafter
= 1; /* after newblk */
209 error
= xfs_attr_leaf_split(state
, newblk
,
213 return(error
); /* GROT: attr inconsistent */
216 case XFS_DIR_LEAF_MAGIC
:
217 ASSERT(XFS_DIR_IS_V1(state
->mp
));
218 error
= xfs_dir_leaf_split(state
, oldblk
, newblk
);
219 if ((error
!= 0) && (error
!= ENOSPC
)) {
220 return(error
); /* GROT: dir is inconsistent */
227 * Entry wouldn't fit, split the leaf again.
229 state
->extravalid
= 1;
231 state
->extraafter
= 0; /* before newblk */
232 error
= xfs_dir_leaf_split(state
, oldblk
,
235 return(error
); /* GROT: dir incon. */
238 state
->extraafter
= 1; /* after newblk */
239 error
= xfs_dir_leaf_split(state
, newblk
,
242 return(error
); /* GROT: dir incon. */
246 case XFS_DIR2_LEAFN_MAGIC
:
247 ASSERT(XFS_DIR_IS_V2(state
->mp
));
248 error
= xfs_dir2_leafn_split(state
, oldblk
, newblk
);
253 case XFS_DA_NODE_MAGIC
:
254 error
= xfs_da_node_split(state
, oldblk
, newblk
, addblk
,
256 xfs_da_buf_done(addblk
->bp
);
259 return(error
); /* GROT: dir is inconsistent */
261 * Record the newly split block for the next time thru?
271 * Update the btree to show the new hashval for this child.
273 xfs_da_fixhashpath(state
, &state
->path
);
275 * If we won't need this block again, it's getting dropped
276 * from the active path by the loop control, so we need
277 * to mark it done now.
279 if (i
> 0 || !addblk
)
280 xfs_da_buf_done(oldblk
->bp
);
286 * Split the root node.
288 ASSERT(state
->path
.active
== 0);
289 oldblk
= &state
->path
.blk
[0];
290 error
= xfs_da_root_split(state
, oldblk
, addblk
);
292 xfs_da_buf_done(oldblk
->bp
);
293 xfs_da_buf_done(addblk
->bp
);
295 return(error
); /* GROT: dir is inconsistent */
299 * Update pointers to the node which used to be block 0 and
300 * just got bumped because of the addition of a new root node.
301 * There might be three blocks involved if a double split occurred,
302 * and the original block 0 could be at any position in the list.
305 node
= oldblk
->bp
->data
;
306 if (node
->hdr
.info
.forw
) {
307 if (INT_GET(node
->hdr
.info
.forw
, ARCH_CONVERT
) == addblk
->blkno
) {
310 ASSERT(state
->extravalid
);
311 bp
= state
->extrablk
.bp
;
314 INT_SET(node
->hdr
.info
.back
, ARCH_CONVERT
, oldblk
->blkno
);
315 xfs_da_log_buf(state
->args
->trans
, bp
,
316 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
317 sizeof(node
->hdr
.info
)));
319 node
= oldblk
->bp
->data
;
320 if (INT_GET(node
->hdr
.info
.back
, ARCH_CONVERT
)) {
321 if (INT_GET(node
->hdr
.info
.back
, ARCH_CONVERT
) == addblk
->blkno
) {
324 ASSERT(state
->extravalid
);
325 bp
= state
->extrablk
.bp
;
328 INT_SET(node
->hdr
.info
.forw
, ARCH_CONVERT
, oldblk
->blkno
);
329 xfs_da_log_buf(state
->args
->trans
, bp
,
330 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
331 sizeof(node
->hdr
.info
)));
333 xfs_da_buf_done(oldblk
->bp
);
334 xfs_da_buf_done(addblk
->bp
);
340 * Split the root. We have to create a new root and point to the two
341 * parts (the split old root) that we just created. Copy block zero to
342 * the EOF, extending the inode in process.
344 STATIC
int /* error */
345 xfs_da_root_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
346 xfs_da_state_blk_t
*blk2
)
348 xfs_da_intnode_t
*node
, *oldroot
;
356 xfs_dir2_leaf_t
*leaf
;
359 * Copy the existing (incorrect) block from the root node position
360 * to a free space somewhere.
363 ASSERT(args
!= NULL
);
364 error
= xfs_da_grow_inode(args
, &blkno
);
370 error
= xfs_da_get_buf(tp
, dp
, blkno
, -1, &bp
, args
->whichfork
);
375 oldroot
= blk1
->bp
->data
;
376 if (INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
377 size
= (int)((char *)&oldroot
->btree
[INT_GET(oldroot
->hdr
.count
, ARCH_CONVERT
)] -
380 ASSERT(XFS_DIR_IS_V2(mp
));
381 ASSERT(INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
382 leaf
= (xfs_dir2_leaf_t
*)oldroot
;
383 size
= (int)((char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] -
386 memcpy(node
, oldroot
, size
);
387 xfs_da_log_buf(tp
, bp
, 0, size
- 1);
388 xfs_da_buf_done(blk1
->bp
);
393 * Set up the new root node.
395 error
= xfs_da_node_create(args
,
396 args
->whichfork
== XFS_DATA_FORK
&&
397 XFS_DIR_IS_V2(mp
) ? mp
->m_dirleafblk
: 0,
398 INT_GET(node
->hdr
.level
, ARCH_CONVERT
) + 1, &bp
, args
->whichfork
);
402 INT_SET(node
->btree
[0].hashval
, ARCH_CONVERT
, blk1
->hashval
);
403 INT_SET(node
->btree
[0].before
, ARCH_CONVERT
, blk1
->blkno
);
404 INT_SET(node
->btree
[1].hashval
, ARCH_CONVERT
, blk2
->hashval
);
405 INT_SET(node
->btree
[1].before
, ARCH_CONVERT
, blk2
->blkno
);
406 INT_SET(node
->hdr
.count
, ARCH_CONVERT
, 2);
409 if (INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
) {
410 ASSERT(blk1
->blkno
>= mp
->m_dirleafblk
&&
411 blk1
->blkno
< mp
->m_dirfreeblk
);
412 ASSERT(blk2
->blkno
>= mp
->m_dirleafblk
&&
413 blk2
->blkno
< mp
->m_dirfreeblk
);
417 /* Header is already logged by xfs_da_node_create */
418 xfs_da_log_buf(tp
, bp
,
419 XFS_DA_LOGRANGE(node
, node
->btree
,
420 sizeof(xfs_da_node_entry_t
) * 2));
427 * Split the node, rebalance, then add the new entry.
429 STATIC
int /* error */
430 xfs_da_node_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
431 xfs_da_state_blk_t
*newblk
,
432 xfs_da_state_blk_t
*addblk
,
433 int treelevel
, int *result
)
435 xfs_da_intnode_t
*node
;
440 node
= oldblk
->bp
->data
;
441 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
444 * With V2 the extra block is data or freespace.
446 useextra
= state
->extravalid
&& XFS_DIR_IS_V1(state
->mp
);
447 newcount
= 1 + useextra
;
449 * Do we have to split the node?
451 if ((INT_GET(node
->hdr
.count
, ARCH_CONVERT
) + newcount
) > state
->node_ents
) {
453 * Allocate a new node, add to the doubly linked chain of
454 * nodes, then move some of our excess entries into it.
456 error
= xfs_da_grow_inode(state
->args
, &blkno
);
458 return(error
); /* GROT: dir is inconsistent */
460 error
= xfs_da_node_create(state
->args
, blkno
, treelevel
,
461 &newblk
->bp
, state
->args
->whichfork
);
463 return(error
); /* GROT: dir is inconsistent */
464 newblk
->blkno
= blkno
;
465 newblk
->magic
= XFS_DA_NODE_MAGIC
;
466 xfs_da_node_rebalance(state
, oldblk
, newblk
);
467 error
= xfs_da_blk_link(state
, oldblk
, newblk
);
476 * Insert the new entry(s) into the correct block
477 * (updating last hashval in the process).
479 * xfs_da_node_add() inserts BEFORE the given index,
480 * and as a result of using node_lookup_int() we always
481 * point to a valid entry (not after one), but a split
482 * operation always results in a new block whose hashvals
483 * FOLLOW the current block.
485 * If we had double-split op below us, then add the extra block too.
487 node
= oldblk
->bp
->data
;
488 if (oldblk
->index
<= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)) {
490 xfs_da_node_add(state
, oldblk
, addblk
);
492 if (state
->extraafter
)
494 xfs_da_node_add(state
, oldblk
, &state
->extrablk
);
495 state
->extravalid
= 0;
499 xfs_da_node_add(state
, newblk
, addblk
);
501 if (state
->extraafter
)
503 xfs_da_node_add(state
, newblk
, &state
->extrablk
);
504 state
->extravalid
= 0;
512 * Balance the btree elements between two intermediate nodes,
513 * usually one full and one empty.
515 * NOTE: if blk2 is empty, then it will get the upper half of blk1.
518 xfs_da_node_rebalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
519 xfs_da_state_blk_t
*blk2
)
521 xfs_da_intnode_t
*node1
, *node2
, *tmpnode
;
522 xfs_da_node_entry_t
*btree_s
, *btree_d
;
526 node1
= blk1
->bp
->data
;
527 node2
= blk2
->bp
->data
;
529 * Figure out how many entries need to move, and in which direction.
530 * Swap the nodes around if that makes it simpler.
532 if ((INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) > 0) && (INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) > 0) &&
533 ((INT_GET(node2
->btree
[ 0 ].hashval
, ARCH_CONVERT
) < INT_GET(node1
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
534 (INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
535 INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))) {
540 ASSERT(INT_GET(node1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
541 ASSERT(INT_GET(node2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
542 count
= (INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) - INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)) / 2;
545 tp
= state
->args
->trans
;
547 * Two cases: high-to-low and low-to-high.
551 * Move elements in node2 up to make a hole.
553 if ((tmp
= INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)) > 0) {
554 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
555 btree_s
= &node2
->btree
[0];
556 btree_d
= &node2
->btree
[count
];
557 memmove(btree_d
, btree_s
, tmp
);
561 * Move the req'd B-tree elements from high in node1 to
564 INT_MOD(node2
->hdr
.count
, ARCH_CONVERT
, count
);
565 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
566 btree_s
= &node1
->btree
[INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) - count
];
567 btree_d
= &node2
->btree
[0];
568 memcpy(btree_d
, btree_s
, tmp
);
569 INT_MOD(node1
->hdr
.count
, ARCH_CONVERT
, -(count
));
573 * Move the req'd B-tree elements from low in node2 to
577 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
578 btree_s
= &node2
->btree
[0];
579 btree_d
= &node1
->btree
[INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)];
580 memcpy(btree_d
, btree_s
, tmp
);
581 INT_MOD(node1
->hdr
.count
, ARCH_CONVERT
, count
);
582 xfs_da_log_buf(tp
, blk1
->bp
,
583 XFS_DA_LOGRANGE(node1
, btree_d
, tmp
));
586 * Move elements in node2 down to fill the hole.
588 tmp
= INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) - count
;
589 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
590 btree_s
= &node2
->btree
[count
];
591 btree_d
= &node2
->btree
[0];
592 memmove(btree_d
, btree_s
, tmp
);
593 INT_MOD(node2
->hdr
.count
, ARCH_CONVERT
, -(count
));
597 * Log header of node 1 and all current bits of node 2.
599 xfs_da_log_buf(tp
, blk1
->bp
,
600 XFS_DA_LOGRANGE(node1
, &node1
->hdr
, sizeof(node1
->hdr
)));
601 xfs_da_log_buf(tp
, blk2
->bp
,
602 XFS_DA_LOGRANGE(node2
, &node2
->hdr
,
604 sizeof(node2
->btree
[0]) * INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)));
607 * Record the last hashval from each block for upward propagation.
608 * (note: don't use the swapped node pointers)
610 node1
= blk1
->bp
->data
;
611 node2
= blk2
->bp
->data
;
612 blk1
->hashval
= INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
613 blk2
->hashval
= INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
616 * Adjust the expected index for insertion.
618 if (blk1
->index
>= INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)) {
619 blk2
->index
= blk1
->index
- INT_GET(node1
->hdr
.count
, ARCH_CONVERT
);
620 blk1
->index
= INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) + 1; /* make it invalid */
625 * Add a new entry to an intermediate node.
628 xfs_da_node_add(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
629 xfs_da_state_blk_t
*newblk
)
631 xfs_da_intnode_t
*node
;
632 xfs_da_node_entry_t
*btree
;
636 node
= oldblk
->bp
->data
;
638 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
639 ASSERT((oldblk
->index
>= 0) && (oldblk
->index
<= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)));
640 ASSERT(newblk
->blkno
!= 0);
641 if (state
->args
->whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
642 ASSERT(newblk
->blkno
>= mp
->m_dirleafblk
&&
643 newblk
->blkno
< mp
->m_dirfreeblk
);
646 * We may need to make some room before we insert the new node.
649 btree
= &node
->btree
[ oldblk
->index
];
650 if (oldblk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
)) {
651 tmp
= (INT_GET(node
->hdr
.count
, ARCH_CONVERT
) - oldblk
->index
) * (uint
)sizeof(*btree
);
652 memmove(btree
+ 1, btree
, tmp
);
654 INT_SET(btree
->hashval
, ARCH_CONVERT
, newblk
->hashval
);
655 INT_SET(btree
->before
, ARCH_CONVERT
, newblk
->blkno
);
656 xfs_da_log_buf(state
->args
->trans
, oldblk
->bp
,
657 XFS_DA_LOGRANGE(node
, btree
, tmp
+ sizeof(*btree
)));
658 INT_MOD(node
->hdr
.count
, ARCH_CONVERT
, +1);
659 xfs_da_log_buf(state
->args
->trans
, oldblk
->bp
,
660 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
663 * Copy the last hash value from the oldblk to propagate upwards.
665 oldblk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
668 /*========================================================================
669 * Routines used for shrinking the Btree.
670 *========================================================================*/
673 * Deallocate an empty leaf node, remove it from its parent,
674 * possibly deallocating that block, etc...
677 xfs_da_join(xfs_da_state_t
*state
)
679 xfs_da_state_blk_t
*drop_blk
, *save_blk
;
683 drop_blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
684 save_blk
= &state
->altpath
.blk
[ state
->path
.active
-1 ];
685 ASSERT(state
->path
.blk
[0].magic
== XFS_DA_NODE_MAGIC
);
686 ASSERT(drop_blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
687 drop_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
));
690 * Walk back up the tree joining/deallocating as necessary.
691 * When we stop dropping blocks, break out.
693 for ( ; state
->path
.active
>= 2; drop_blk
--, save_blk
--,
694 state
->path
.active
--) {
696 * See if we can combine the block with a neighbor.
697 * (action == 0) => no options, just leave
698 * (action == 1) => coalesce, then unlink
699 * (action == 2) => block empty, unlink it
701 switch (drop_blk
->magic
) {
702 case XFS_ATTR_LEAF_MAGIC
:
703 error
= xfs_attr_leaf_toosmall(state
, &action
);
708 xfs_attr_leaf_unbalance(state
, drop_blk
, save_blk
);
710 case XFS_DIR_LEAF_MAGIC
:
711 ASSERT(XFS_DIR_IS_V1(state
->mp
));
712 error
= xfs_dir_leaf_toosmall(state
, &action
);
717 xfs_dir_leaf_unbalance(state
, drop_blk
, save_blk
);
719 case XFS_DIR2_LEAFN_MAGIC
:
720 ASSERT(XFS_DIR_IS_V2(state
->mp
));
721 error
= xfs_dir2_leafn_toosmall(state
, &action
);
726 xfs_dir2_leafn_unbalance(state
, drop_blk
, save_blk
);
728 case XFS_DA_NODE_MAGIC
:
730 * Remove the offending node, fixup hashvals,
731 * check for a toosmall neighbor.
733 xfs_da_node_remove(state
, drop_blk
);
734 xfs_da_fixhashpath(state
, &state
->path
);
735 error
= xfs_da_node_toosmall(state
, &action
);
740 xfs_da_node_unbalance(state
, drop_blk
, save_blk
);
743 xfs_da_fixhashpath(state
, &state
->altpath
);
744 error
= xfs_da_blk_unlink(state
, drop_blk
, save_blk
);
745 xfs_da_state_kill_altpath(state
);
748 error
= xfs_da_shrink_inode(state
->args
, drop_blk
->blkno
,
755 * We joined all the way to the top. If it turns out that
756 * we only have one entry in the root, make the child block
759 xfs_da_node_remove(state
, drop_blk
);
760 xfs_da_fixhashpath(state
, &state
->path
);
761 error
= xfs_da_root_join(state
, &state
->path
.blk
[0]);
766 * We have only one entry in the root. Copy the only remaining child of
767 * the old root to block 0 as the new root node.
770 xfs_da_root_join(xfs_da_state_t
*state
, xfs_da_state_blk_t
*root_blk
)
772 xfs_da_intnode_t
*oldroot
;
774 xfs_da_blkinfo_t
*blkinfo
;
781 ASSERT(args
!= NULL
);
782 ASSERT(root_blk
->magic
== XFS_DA_NODE_MAGIC
);
783 oldroot
= root_blk
->bp
->data
;
784 ASSERT(INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
785 ASSERT(!oldroot
->hdr
.info
.forw
);
786 ASSERT(!oldroot
->hdr
.info
.back
);
789 * If the root has more than one child, then don't do anything.
791 if (INT_GET(oldroot
->hdr
.count
, ARCH_CONVERT
) > 1)
795 * Read in the (only) child block, then copy those bytes into
796 * the root block's buffer and free the original child block.
798 child
= INT_GET(oldroot
->btree
[ 0 ].before
, ARCH_CONVERT
);
800 error
= xfs_da_read_buf(args
->trans
, args
->dp
, child
, -1, &bp
,
806 if (INT_GET(oldroot
->hdr
.level
, ARCH_CONVERT
) == 1) {
807 ASSERT(INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
808 INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
810 ASSERT(INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
812 ASSERT(!blkinfo
->forw
);
813 ASSERT(!blkinfo
->back
);
814 memcpy(root_blk
->bp
->data
, bp
->data
, state
->blocksize
);
815 xfs_da_log_buf(args
->trans
, root_blk
->bp
, 0, state
->blocksize
- 1);
816 error
= xfs_da_shrink_inode(args
, child
, bp
);
821 * Check a node block and its neighbors to see if the block should be
822 * collapsed into one or the other neighbor. Always keep the block
823 * with the smaller block number.
824 * If the current block is over 50% full, don't try to join it, return 0.
825 * If the block is empty, fill in the state structure and return 2.
826 * If it can be collapsed, fill in the state structure and return 1.
827 * If nothing can be done, return 0.
830 xfs_da_node_toosmall(xfs_da_state_t
*state
, int *action
)
832 xfs_da_intnode_t
*node
;
833 xfs_da_state_blk_t
*blk
;
834 xfs_da_blkinfo_t
*info
;
835 int count
, forward
, error
, retval
, i
;
840 * Check for the degenerate case of the block being over 50% full.
841 * If so, it's not worth even looking to see if we might be able
842 * to coalesce with a sibling.
844 blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
845 info
= blk
->bp
->data
;
846 ASSERT(INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
847 node
= (xfs_da_intnode_t
*)info
;
848 count
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
849 if (count
> (state
->node_ents
>> 1)) {
850 *action
= 0; /* blk over 50%, don't try to join */
851 return(0); /* blk over 50%, don't try to join */
855 * Check for the degenerate case of the block being empty.
856 * If the block is empty, we'll simply delete it, no need to
857 * coalesce it with a sibling block. We choose (aribtrarily)
858 * to merge with the forward block unless it is NULL.
862 * Make altpath point to the block we want to keep and
863 * path point to the block we want to drop (this one).
865 forward
= info
->forw
;
866 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
867 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
880 * Examine each sibling block to see if we can coalesce with
881 * at least 25% free space to spare. We need to figure out
882 * whether to merge with the forward or the backward block.
883 * We prefer coalescing with the lower numbered sibling so as
884 * to shrink a directory over time.
886 /* start with smaller blk num */
887 forward
= (INT_GET(info
->forw
, ARCH_CONVERT
)
888 < INT_GET(info
->back
, ARCH_CONVERT
));
889 for (i
= 0; i
< 2; forward
= !forward
, i
++) {
891 blkno
= INT_GET(info
->forw
, ARCH_CONVERT
);
893 blkno
= INT_GET(info
->back
, ARCH_CONVERT
);
896 error
= xfs_da_read_buf(state
->args
->trans
, state
->args
->dp
,
897 blkno
, -1, &bp
, state
->args
->whichfork
);
902 node
= (xfs_da_intnode_t
*)info
;
903 count
= state
->node_ents
;
904 count
-= state
->node_ents
>> 2;
905 count
-= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
907 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
908 count
-= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
909 xfs_da_brelse(state
->args
->trans
, bp
);
911 break; /* fits with at least 25% to spare */
919 * Make altpath point to the block we want to keep (the lower
920 * numbered block) and path point to the block we want to drop.
922 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
923 if (blkno
< blk
->blkno
) {
924 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
934 error
= xfs_da_path_shift(state
, &state
->path
, forward
,
949 * Walk back up the tree adjusting hash values as necessary,
950 * when we stop making changes, return.
953 xfs_da_fixhashpath(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
)
955 xfs_da_state_blk_t
*blk
;
956 xfs_da_intnode_t
*node
;
957 xfs_da_node_entry_t
*btree
;
958 xfs_dahash_t lasthash
=0;
961 level
= path
->active
-1;
962 blk
= &path
->blk
[ level
];
963 switch (blk
->magic
) {
964 case XFS_ATTR_LEAF_MAGIC
:
965 lasthash
= xfs_attr_leaf_lasthash(blk
->bp
, &count
);
969 case XFS_DIR_LEAF_MAGIC
:
970 ASSERT(XFS_DIR_IS_V1(state
->mp
));
971 lasthash
= xfs_dir_leaf_lasthash(blk
->bp
, &count
);
975 case XFS_DIR2_LEAFN_MAGIC
:
976 ASSERT(XFS_DIR_IS_V2(state
->mp
));
977 lasthash
= xfs_dir2_leafn_lasthash(blk
->bp
, &count
);
981 case XFS_DA_NODE_MAGIC
:
982 lasthash
= xfs_da_node_lasthash(blk
->bp
, &count
);
987 for (blk
--, level
--; level
>= 0; blk
--, level
--) {
988 node
= blk
->bp
->data
;
989 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
990 btree
= &node
->btree
[ blk
->index
];
991 if (INT_GET(btree
->hashval
, ARCH_CONVERT
) == lasthash
)
993 blk
->hashval
= lasthash
;
994 INT_SET(btree
->hashval
, ARCH_CONVERT
, lasthash
);
995 xfs_da_log_buf(state
->args
->trans
, blk
->bp
,
996 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
998 lasthash
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1003 * Remove an entry from an intermediate node.
1006 xfs_da_node_remove(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
)
1008 xfs_da_intnode_t
*node
;
1009 xfs_da_node_entry_t
*btree
;
1012 node
= drop_blk
->bp
->data
;
1013 ASSERT(drop_blk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
));
1014 ASSERT(drop_blk
->index
>= 0);
1017 * Copy over the offending entry, or just zero it out.
1019 btree
= &node
->btree
[drop_blk
->index
];
1020 if (drop_blk
->index
< (INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1)) {
1021 tmp
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
) - drop_blk
->index
- 1;
1022 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
1023 memmove(btree
, btree
+ 1, tmp
);
1024 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
1025 XFS_DA_LOGRANGE(node
, btree
, tmp
));
1026 btree
= &node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ];
1028 memset((char *)btree
, 0, sizeof(xfs_da_node_entry_t
));
1029 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
1030 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
1031 INT_MOD(node
->hdr
.count
, ARCH_CONVERT
, -1);
1032 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
1033 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
1036 * Copy the last hash value from the block to propagate upwards.
1039 drop_blk
->hashval
= INT_GET(btree
->hashval
, ARCH_CONVERT
);
1043 * Unbalance the btree elements between two intermediate nodes,
1044 * move all Btree elements from one node into another.
1047 xfs_da_node_unbalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
1048 xfs_da_state_blk_t
*save_blk
)
1050 xfs_da_intnode_t
*drop_node
, *save_node
;
1051 xfs_da_node_entry_t
*btree
;
1055 drop_node
= drop_blk
->bp
->data
;
1056 save_node
= save_blk
->bp
->data
;
1057 ASSERT(INT_GET(drop_node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1058 ASSERT(INT_GET(save_node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1059 tp
= state
->args
->trans
;
1062 * If the dying block has lower hashvals, then move all the
1063 * elements in the remaining block up to make a hole.
1065 if ((INT_GET(drop_node
->btree
[ 0 ].hashval
, ARCH_CONVERT
) < INT_GET(save_node
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
1066 (INT_GET(drop_node
->btree
[ INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
1067 INT_GET(save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))
1069 btree
= &save_node
->btree
[ INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) ];
1070 tmp
= INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_da_node_entry_t
);
1071 memmove(btree
, &save_node
->btree
[0], tmp
);
1072 btree
= &save_node
->btree
[0];
1073 xfs_da_log_buf(tp
, save_blk
->bp
,
1074 XFS_DA_LOGRANGE(save_node
, btree
,
1075 (INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) + INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
)) *
1076 sizeof(xfs_da_node_entry_t
)));
1078 btree
= &save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) ];
1079 xfs_da_log_buf(tp
, save_blk
->bp
,
1080 XFS_DA_LOGRANGE(save_node
, btree
,
1081 INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) *
1082 sizeof(xfs_da_node_entry_t
)));
1086 * Move all the B-tree elements from drop_blk to save_blk.
1088 tmp
= INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_da_node_entry_t
);
1089 memcpy(btree
, &drop_node
->btree
[0], tmp
);
1090 INT_MOD(save_node
->hdr
.count
, ARCH_CONVERT
, INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
));
1092 xfs_da_log_buf(tp
, save_blk
->bp
,
1093 XFS_DA_LOGRANGE(save_node
, &save_node
->hdr
,
1094 sizeof(save_node
->hdr
)));
1097 * Save the last hashval in the remaining block for upward propagation.
1099 save_blk
->hashval
= INT_GET(save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1102 /*========================================================================
1103 * Routines used for finding things in the Btree.
1104 *========================================================================*/
1107 * Walk down the Btree looking for a particular filename, filling
1108 * in the state structure as we go.
1110 * We will set the state structure to point to each of the elements
1111 * in each of the nodes where either the hashval is or should be.
1113 * We support duplicate hashval's so for each entry in the current
1114 * node that could contain the desired hashval, descend. This is a
1115 * pruned depth-first tree search.
1118 xfs_da_node_lookup_int(xfs_da_state_t
*state
, int *result
)
1120 xfs_da_state_blk_t
*blk
;
1121 xfs_da_blkinfo_t
*curr
;
1122 xfs_da_intnode_t
*node
;
1123 xfs_da_node_entry_t
*btree
;
1125 int probe
, span
, max
, error
, retval
;
1126 xfs_dahash_t hashval
;
1127 xfs_da_args_t
*args
;
1132 * Descend thru the B-tree searching each level for the right
1133 * node to use, until the right hashval is found.
1135 if (args
->whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(state
->mp
))
1136 blkno
= state
->mp
->m_dirleafblk
;
1139 for (blk
= &state
->path
.blk
[0], state
->path
.active
= 1;
1140 state
->path
.active
<= XFS_DA_NODE_MAXDEPTH
;
1141 blk
++, state
->path
.active
++) {
1143 * Read the next node down in the tree.
1146 error
= xfs_da_read_buf(args
->trans
, args
->dp
, blkno
,
1147 -1, &blk
->bp
, args
->whichfork
);
1150 state
->path
.active
--;
1153 curr
= blk
->bp
->data
;
1154 ASSERT(INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
||
1155 INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1156 INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
1159 * Search an intermediate node for a match.
1161 blk
->magic
= INT_GET(curr
->magic
, ARCH_CONVERT
);
1162 if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
1163 node
= blk
->bp
->data
;
1164 blk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1167 * Binary search. (note: small blocks will skip loop)
1169 max
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
1170 probe
= span
= max
/ 2;
1171 hashval
= args
->hashval
;
1172 for (btree
= &node
->btree
[probe
]; span
> 4;
1173 btree
= &node
->btree
[probe
]) {
1175 if (INT_GET(btree
->hashval
, ARCH_CONVERT
) < hashval
)
1177 else if (INT_GET(btree
->hashval
, ARCH_CONVERT
) > hashval
)
1182 ASSERT((probe
>= 0) && (probe
< max
));
1183 ASSERT((span
<= 4) || (INT_GET(btree
->hashval
, ARCH_CONVERT
) == hashval
));
1186 * Since we may have duplicate hashval's, find the first
1187 * matching hashval in the node.
1189 while ((probe
> 0) && (INT_GET(btree
->hashval
, ARCH_CONVERT
) >= hashval
)) {
1193 while ((probe
< max
) && (INT_GET(btree
->hashval
, ARCH_CONVERT
) < hashval
)) {
1199 * Pick the right block to descend on.
1203 blkno
= INT_GET(node
->btree
[ max
-1 ].before
, ARCH_CONVERT
);
1206 blkno
= INT_GET(btree
->before
, ARCH_CONVERT
);
1209 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
) {
1210 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
, NULL
);
1213 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
) {
1214 blk
->hashval
= xfs_dir_leaf_lasthash(blk
->bp
, NULL
);
1217 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
) {
1218 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
, NULL
);
1224 * A leaf block that ends in the hashval that we are interested in
1225 * (final hashval == search hashval) means that the next block may
1226 * contain more entries with the same hashval, shift upward to the
1227 * next leaf and keep searching.
1230 if (blk
->magic
== XFS_DIR_LEAF_MAGIC
) {
1231 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1232 retval
= xfs_dir_leaf_lookup_int(blk
->bp
, args
,
1234 } else if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
) {
1235 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1236 retval
= xfs_dir2_leafn_lookup_int(blk
->bp
, args
,
1237 &blk
->index
, state
);
1239 else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1240 retval
= xfs_attr_leaf_lookup_int(blk
->bp
, args
);
1241 blk
->index
= args
->index
;
1242 args
->blkno
= blk
->blkno
;
1244 if (((retval
== ENOENT
) || (retval
== ENOATTR
)) &&
1245 (blk
->hashval
== args
->hashval
)) {
1246 error
= xfs_da_path_shift(state
, &state
->path
, 1, 1,
1253 else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1254 /* path_shift() gives ENOENT */
1255 retval
= XFS_ERROR(ENOATTR
);
1264 /*========================================================================
1266 *========================================================================*/
1269 * Link a new block into a doubly linked list of blocks (of whatever type).
1272 xfs_da_blk_link(xfs_da_state_t
*state
, xfs_da_state_blk_t
*old_blk
,
1273 xfs_da_state_blk_t
*new_blk
)
1275 xfs_da_blkinfo_t
*old_info
, *new_info
, *tmp_info
;
1276 xfs_da_args_t
*args
;
1277 int before
=0, error
;
1281 * Set up environment.
1284 ASSERT(args
!= NULL
);
1285 old_info
= old_blk
->bp
->data
;
1286 new_info
= new_blk
->bp
->data
;
1287 ASSERT(old_blk
->magic
== XFS_DA_NODE_MAGIC
||
1288 old_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1289 old_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1290 ASSERT(old_blk
->magic
== INT_GET(old_info
->magic
, ARCH_CONVERT
));
1291 ASSERT(new_blk
->magic
== INT_GET(new_info
->magic
, ARCH_CONVERT
));
1292 ASSERT(old_blk
->magic
== new_blk
->magic
);
1294 switch (old_blk
->magic
) {
1295 case XFS_ATTR_LEAF_MAGIC
:
1296 before
= xfs_attr_leaf_order(old_blk
->bp
, new_blk
->bp
);
1298 case XFS_DIR_LEAF_MAGIC
:
1299 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1300 before
= xfs_dir_leaf_order(old_blk
->bp
, new_blk
->bp
);
1302 case XFS_DIR2_LEAFN_MAGIC
:
1303 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1304 before
= xfs_dir2_leafn_order(old_blk
->bp
, new_blk
->bp
);
1306 case XFS_DA_NODE_MAGIC
:
1307 before
= xfs_da_node_order(old_blk
->bp
, new_blk
->bp
);
1312 * Link blocks in appropriate order.
1316 * Link new block in before existing block.
1318 INT_SET(new_info
->forw
, ARCH_CONVERT
, old_blk
->blkno
);
1319 new_info
->back
= old_info
->back
; /* INT_: direct copy */
1320 if (INT_GET(old_info
->back
, ARCH_CONVERT
)) {
1321 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1322 INT_GET(old_info
->back
,
1323 ARCH_CONVERT
), -1, &bp
,
1328 tmp_info
= bp
->data
;
1329 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
) == INT_GET(old_info
->magic
, ARCH_CONVERT
));
1330 ASSERT(INT_GET(tmp_info
->forw
, ARCH_CONVERT
) == old_blk
->blkno
);
1331 INT_SET(tmp_info
->forw
, ARCH_CONVERT
, new_blk
->blkno
);
1332 xfs_da_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1333 xfs_da_buf_done(bp
);
1335 INT_SET(old_info
->back
, ARCH_CONVERT
, new_blk
->blkno
);
1338 * Link new block in after existing block.
1340 new_info
->forw
= old_info
->forw
; /* INT_: direct copy */
1341 INT_SET(new_info
->back
, ARCH_CONVERT
, old_blk
->blkno
);
1342 if (INT_GET(old_info
->forw
, ARCH_CONVERT
)) {
1343 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1344 INT_GET(old_info
->forw
, ARCH_CONVERT
), -1, &bp
,
1349 tmp_info
= bp
->data
;
1350 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
)
1351 == INT_GET(old_info
->magic
, ARCH_CONVERT
));
1352 ASSERT(INT_GET(tmp_info
->back
, ARCH_CONVERT
)
1354 INT_SET(tmp_info
->back
, ARCH_CONVERT
, new_blk
->blkno
);
1355 xfs_da_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1356 xfs_da_buf_done(bp
);
1358 INT_SET(old_info
->forw
, ARCH_CONVERT
, new_blk
->blkno
);
1361 xfs_da_log_buf(args
->trans
, old_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1362 xfs_da_log_buf(args
->trans
, new_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1367 * Compare two intermediate nodes for "order".
1370 xfs_da_node_order(xfs_dabuf_t
*node1_bp
, xfs_dabuf_t
*node2_bp
)
1372 xfs_da_intnode_t
*node1
, *node2
;
1374 node1
= node1_bp
->data
;
1375 node2
= node2_bp
->data
;
1376 ASSERT((INT_GET(node1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) &&
1377 (INT_GET(node2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
));
1378 if ((INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) > 0) && (INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) > 0) &&
1379 ((INT_GET(node2
->btree
[ 0 ].hashval
, ARCH_CONVERT
) <
1380 INT_GET(node1
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
1381 (INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
1382 INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))) {
1389 * Pick up the last hashvalue from an intermediate node.
1392 xfs_da_node_lasthash(xfs_dabuf_t
*bp
, int *count
)
1394 xfs_da_intnode_t
*node
;
1397 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1399 *count
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
1400 if (!node
->hdr
.count
)
1402 return(INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
));
1406 * Unlink a block from a doubly linked list of blocks.
1408 STATIC
int /* error */
1409 xfs_da_blk_unlink(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
1410 xfs_da_state_blk_t
*save_blk
)
1412 xfs_da_blkinfo_t
*drop_info
, *save_info
, *tmp_info
;
1413 xfs_da_args_t
*args
;
1418 * Set up environment.
1421 ASSERT(args
!= NULL
);
1422 save_info
= save_blk
->bp
->data
;
1423 drop_info
= drop_blk
->bp
->data
;
1424 ASSERT(save_blk
->magic
== XFS_DA_NODE_MAGIC
||
1425 save_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1426 save_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1427 ASSERT(save_blk
->magic
== INT_GET(save_info
->magic
, ARCH_CONVERT
));
1428 ASSERT(drop_blk
->magic
== INT_GET(drop_info
->magic
, ARCH_CONVERT
));
1429 ASSERT(save_blk
->magic
== drop_blk
->magic
);
1430 ASSERT((INT_GET(save_info
->forw
, ARCH_CONVERT
) == drop_blk
->blkno
) ||
1431 (INT_GET(save_info
->back
, ARCH_CONVERT
) == drop_blk
->blkno
));
1432 ASSERT((INT_GET(drop_info
->forw
, ARCH_CONVERT
) == save_blk
->blkno
) ||
1433 (INT_GET(drop_info
->back
, ARCH_CONVERT
) == save_blk
->blkno
));
1436 * Unlink the leaf block from the doubly linked chain of leaves.
1438 if (INT_GET(save_info
->back
, ARCH_CONVERT
) == drop_blk
->blkno
) {
1439 save_info
->back
= drop_info
->back
; /* INT_: direct copy */
1440 if (INT_GET(drop_info
->back
, ARCH_CONVERT
)) {
1441 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1442 INT_GET(drop_info
->back
,
1443 ARCH_CONVERT
), -1, &bp
,
1448 tmp_info
= bp
->data
;
1449 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
) == INT_GET(save_info
->magic
, ARCH_CONVERT
));
1450 ASSERT(INT_GET(tmp_info
->forw
, ARCH_CONVERT
) == drop_blk
->blkno
);
1451 INT_SET(tmp_info
->forw
, ARCH_CONVERT
, save_blk
->blkno
);
1452 xfs_da_log_buf(args
->trans
, bp
, 0,
1453 sizeof(*tmp_info
) - 1);
1454 xfs_da_buf_done(bp
);
1457 save_info
->forw
= drop_info
->forw
; /* INT_: direct copy */
1458 if (INT_GET(drop_info
->forw
, ARCH_CONVERT
)) {
1459 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1460 INT_GET(drop_info
->forw
, ARCH_CONVERT
), -1, &bp
,
1465 tmp_info
= bp
->data
;
1466 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
)
1467 == INT_GET(save_info
->magic
, ARCH_CONVERT
));
1468 ASSERT(INT_GET(tmp_info
->back
, ARCH_CONVERT
)
1469 == drop_blk
->blkno
);
1470 INT_SET(tmp_info
->back
, ARCH_CONVERT
, save_blk
->blkno
);
1471 xfs_da_log_buf(args
->trans
, bp
, 0,
1472 sizeof(*tmp_info
) - 1);
1473 xfs_da_buf_done(bp
);
1477 xfs_da_log_buf(args
->trans
, save_blk
->bp
, 0, sizeof(*save_info
) - 1);
1482 * Move a path "forward" or "!forward" one block at the current level.
1484 * This routine will adjust a "path" to point to the next block
1485 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1486 * Btree, including updating pointers to the intermediate nodes between
1487 * the new bottom and the root.
1490 xfs_da_path_shift(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
,
1491 int forward
, int release
, int *result
)
1493 xfs_da_state_blk_t
*blk
;
1494 xfs_da_blkinfo_t
*info
;
1495 xfs_da_intnode_t
*node
;
1496 xfs_da_args_t
*args
;
1497 xfs_dablk_t blkno
=0;
1501 * Roll up the Btree looking for the first block where our
1502 * current index is not at the edge of the block. Note that
1503 * we skip the bottom layer because we want the sibling block.
1506 ASSERT(args
!= NULL
);
1507 ASSERT(path
!= NULL
);
1508 ASSERT((path
->active
> 0) && (path
->active
< XFS_DA_NODE_MAXDEPTH
));
1509 level
= (path
->active
-1) - 1; /* skip bottom layer in path */
1510 for (blk
= &path
->blk
[level
]; level
>= 0; blk
--, level
--) {
1511 ASSERT(blk
->bp
!= NULL
);
1512 node
= blk
->bp
->data
;
1513 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1514 if (forward
&& (blk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1)) {
1516 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1518 } else if (!forward
&& (blk
->index
> 0)) {
1520 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1525 *result
= XFS_ERROR(ENOENT
); /* we're out of our tree */
1526 ASSERT(args
->oknoent
);
1531 * Roll down the edge of the subtree until we reach the
1532 * same depth we were at originally.
1534 for (blk
++, level
++; level
< path
->active
; blk
++, level
++) {
1536 * Release the old block.
1537 * (if it's dirty, trans won't actually let go)
1540 xfs_da_brelse(args
->trans
, blk
->bp
);
1543 * Read the next child block.
1546 error
= xfs_da_read_buf(args
->trans
, args
->dp
, blkno
, -1,
1547 &blk
->bp
, args
->whichfork
);
1550 ASSERT(blk
->bp
!= NULL
);
1551 info
= blk
->bp
->data
;
1552 ASSERT(INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
||
1553 INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1554 INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
1555 blk
->magic
= INT_GET(info
->magic
, ARCH_CONVERT
);
1556 if (INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
1557 node
= (xfs_da_intnode_t
*)info
;
1558 blk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1562 blk
->index
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1;
1563 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1565 ASSERT(level
== path
->active
-1);
1567 switch(blk
->magic
) {
1568 case XFS_ATTR_LEAF_MAGIC
:
1569 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
,
1572 case XFS_DIR_LEAF_MAGIC
:
1573 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1574 blk
->hashval
= xfs_dir_leaf_lasthash(blk
->bp
,
1577 case XFS_DIR2_LEAFN_MAGIC
:
1578 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1579 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
,
1583 ASSERT(blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
1585 XFS_DIRX_LEAF_MAGIC(state
->mp
));
1595 /*========================================================================
1597 *========================================================================*/
1600 * Implement a simple hash on a character string.
1601 * Rotate the hash value by 7 bits, then XOR each character in.
1602 * This is implemented with some source-level loop unrolling.
1605 xfs_da_hashname(const uchar_t
*name
, int namelen
)
1611 * This is the old one-byte-at-a-time version.
1613 for (hash
= 0; namelen
> 0; namelen
--)
1614 hash
= *name
++ ^ rol32(hash
, 7);
1619 * Do four characters at a time as long as we can.
1621 for (hash
= 0; namelen
>= 4; namelen
-= 4, name
+= 4)
1622 hash
= (name
[0] << 21) ^ (name
[1] << 14) ^ (name
[2] << 7) ^
1623 (name
[3] << 0) ^ rol32(hash
, 7 * 4);
1626 * Now do the rest of the characters.
1630 return (name
[0] << 14) ^ (name
[1] << 7) ^ (name
[2] << 0) ^
1633 return (name
[0] << 7) ^ (name
[1] << 0) ^ rol32(hash
, 7 * 2);
1635 return (name
[0] << 0) ^ rol32(hash
, 7 * 1);
1641 return 0; /* keep gcc happy */
1645 * Add a block to the btree ahead of the file.
1646 * Return the new block number to the caller.
1649 xfs_da_grow_inode(xfs_da_args_t
*args
, xfs_dablk_t
*new_blkno
)
1651 xfs_fileoff_t bno
, b
;
1652 xfs_bmbt_irec_t map
;
1653 xfs_bmbt_irec_t
*mapp
;
1655 int nmap
, error
, w
, count
, c
, got
, i
, mapi
;
1662 w
= args
->whichfork
;
1665 * For new directories adjust the file offset and block count.
1667 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
)) {
1668 bno
= mp
->m_dirleafblk
;
1669 count
= mp
->m_dirblkfsbs
;
1675 * Find a spot in the file space to put the new block.
1677 if ((error
= xfs_bmap_first_unused(tp
, dp
, count
, &bno
, w
))) {
1680 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
1681 ASSERT(bno
>= mp
->m_dirleafblk
&& bno
< mp
->m_dirfreeblk
);
1683 * Try mapping it in one filesystem block.
1686 ASSERT(args
->firstblock
!= NULL
);
1687 if ((error
= xfs_bmapi(tp
, dp
, bno
, count
,
1688 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_WRITE
|XFS_BMAPI_METADATA
|
1690 args
->firstblock
, args
->total
, &map
, &nmap
,
1700 * If we didn't get it and the block might work if fragmented,
1701 * try without the CONTIG flag. Loop until we get it all.
1703 else if (nmap
== 0 && count
> 1) {
1704 mapp
= kmem_alloc(sizeof(*mapp
) * count
, KM_SLEEP
);
1705 for (b
= bno
, mapi
= 0; b
< bno
+ count
; ) {
1706 nmap
= MIN(XFS_BMAP_MAX_NMAP
, count
);
1707 c
= (int)(bno
+ count
- b
);
1708 if ((error
= xfs_bmapi(tp
, dp
, b
, c
,
1709 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_WRITE
|
1711 args
->firstblock
, args
->total
,
1712 &mapp
[mapi
], &nmap
, args
->flist
))) {
1713 kmem_free(mapp
, sizeof(*mapp
) * count
);
1719 b
= mapp
[mapi
- 1].br_startoff
+
1720 mapp
[mapi
- 1].br_blockcount
;
1727 * Count the blocks we got, make sure it matches the total.
1729 for (i
= 0, got
= 0; i
< mapi
; i
++)
1730 got
+= mapp
[i
].br_blockcount
;
1731 if (got
!= count
|| mapp
[0].br_startoff
!= bno
||
1732 mapp
[mapi
- 1].br_startoff
+ mapp
[mapi
- 1].br_blockcount
!=
1735 kmem_free(mapp
, sizeof(*mapp
) * count
);
1736 return XFS_ERROR(ENOSPC
);
1739 kmem_free(mapp
, sizeof(*mapp
) * count
);
1740 *new_blkno
= (xfs_dablk_t
)bno
;
1742 * For version 1 directories, adjust the file size if it changed.
1744 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V1(mp
)) {
1746 if ((error
= xfs_bmap_last_offset(tp
, dp
, &bno
, w
)))
1748 size
= XFS_FSB_TO_B(mp
, bno
);
1749 if (size
!= dp
->i_d
.di_size
) {
1750 dp
->i_d
.di_size
= size
;
1751 xfs_trans_log_inode(tp
, dp
, XFS_ILOG_CORE
);
1758 * Ick. We need to always be able to remove a btree block, even
1759 * if there's no space reservation because the filesystem is full.
1760 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
1761 * It swaps the target block with the last block in the file. The
1762 * last block in the file can always be removed since it can't cause
1763 * a bmap btree split to do that.
1766 xfs_da_swap_lastblock(xfs_da_args_t
*args
, xfs_dablk_t
*dead_blknop
,
1767 xfs_dabuf_t
**dead_bufp
)
1769 xfs_dablk_t dead_blkno
, last_blkno
, sib_blkno
, par_blkno
;
1770 xfs_dabuf_t
*dead_buf
, *last_buf
, *sib_buf
, *par_buf
;
1771 xfs_fileoff_t lastoff
;
1775 int error
, w
, entno
, level
, dead_level
;
1776 xfs_da_blkinfo_t
*dead_info
, *sib_info
;
1777 xfs_da_intnode_t
*par_node
, *dead_node
;
1778 xfs_dir_leafblock_t
*dead_leaf
;
1779 xfs_dir2_leaf_t
*dead_leaf2
;
1780 xfs_dahash_t dead_hash
;
1782 dead_buf
= *dead_bufp
;
1783 dead_blkno
= *dead_blknop
;
1786 w
= args
->whichfork
;
1787 ASSERT(w
== XFS_DATA_FORK
);
1789 if (XFS_DIR_IS_V2(mp
)) {
1790 lastoff
= mp
->m_dirfreeblk
;
1791 error
= xfs_bmap_last_before(tp
, ip
, &lastoff
, w
);
1793 error
= xfs_bmap_last_offset(tp
, ip
, &lastoff
, w
);
1796 if (unlikely(lastoff
== 0)) {
1797 XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW
,
1799 return XFS_ERROR(EFSCORRUPTED
);
1802 * Read the last block in the btree space.
1804 last_blkno
= (xfs_dablk_t
)lastoff
- mp
->m_dirblkfsbs
;
1805 if ((error
= xfs_da_read_buf(tp
, ip
, last_blkno
, -1, &last_buf
, w
)))
1808 * Copy the last block into the dead buffer and log it.
1810 memcpy(dead_buf
->data
, last_buf
->data
, mp
->m_dirblksize
);
1811 xfs_da_log_buf(tp
, dead_buf
, 0, mp
->m_dirblksize
- 1);
1812 dead_info
= dead_buf
->data
;
1814 * Get values from the moved block.
1816 if (INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
) {
1817 ASSERT(XFS_DIR_IS_V1(mp
));
1818 dead_leaf
= (xfs_dir_leafblock_t
*)dead_info
;
1821 INT_GET(dead_leaf
->entries
[INT_GET(dead_leaf
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1822 } else if (INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
) {
1823 ASSERT(XFS_DIR_IS_V2(mp
));
1824 dead_leaf2
= (xfs_dir2_leaf_t
*)dead_info
;
1826 dead_hash
= INT_GET(dead_leaf2
->ents
[INT_GET(dead_leaf2
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1828 ASSERT(INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1829 dead_node
= (xfs_da_intnode_t
*)dead_info
;
1830 dead_level
= INT_GET(dead_node
->hdr
.level
, ARCH_CONVERT
);
1831 dead_hash
= INT_GET(dead_node
->btree
[INT_GET(dead_node
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1833 sib_buf
= par_buf
= NULL
;
1835 * If the moved block has a left sibling, fix up the pointers.
1837 if ((sib_blkno
= INT_GET(dead_info
->back
, ARCH_CONVERT
))) {
1838 if ((error
= xfs_da_read_buf(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
)))
1840 sib_info
= sib_buf
->data
;
1842 INT_GET(sib_info
->forw
, ARCH_CONVERT
) != last_blkno
||
1843 INT_GET(sib_info
->magic
, ARCH_CONVERT
) != INT_GET(dead_info
->magic
, ARCH_CONVERT
))) {
1844 XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
1845 XFS_ERRLEVEL_LOW
, mp
);
1846 error
= XFS_ERROR(EFSCORRUPTED
);
1849 INT_SET(sib_info
->forw
, ARCH_CONVERT
, dead_blkno
);
1850 xfs_da_log_buf(tp
, sib_buf
,
1851 XFS_DA_LOGRANGE(sib_info
, &sib_info
->forw
,
1852 sizeof(sib_info
->forw
)));
1853 xfs_da_buf_done(sib_buf
);
1857 * If the moved block has a right sibling, fix up the pointers.
1859 if ((sib_blkno
= INT_GET(dead_info
->forw
, ARCH_CONVERT
))) {
1860 if ((error
= xfs_da_read_buf(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
)))
1862 sib_info
= sib_buf
->data
;
1864 INT_GET(sib_info
->back
, ARCH_CONVERT
) != last_blkno
1865 || INT_GET(sib_info
->magic
, ARCH_CONVERT
)
1866 != INT_GET(dead_info
->magic
, ARCH_CONVERT
))) {
1867 XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
1868 XFS_ERRLEVEL_LOW
, mp
);
1869 error
= XFS_ERROR(EFSCORRUPTED
);
1872 INT_SET(sib_info
->back
, ARCH_CONVERT
, dead_blkno
);
1873 xfs_da_log_buf(tp
, sib_buf
,
1874 XFS_DA_LOGRANGE(sib_info
, &sib_info
->back
,
1875 sizeof(sib_info
->back
)));
1876 xfs_da_buf_done(sib_buf
);
1879 par_blkno
= XFS_DIR_IS_V1(mp
) ? 0 : mp
->m_dirleafblk
;
1882 * Walk down the tree looking for the parent of the moved block.
1885 if ((error
= xfs_da_read_buf(tp
, ip
, par_blkno
, -1, &par_buf
, w
)))
1887 par_node
= par_buf
->data
;
1889 INT_GET(par_node
->hdr
.info
.magic
, ARCH_CONVERT
) != XFS_DA_NODE_MAGIC
||
1890 (level
>= 0 && level
!= INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
) + 1))) {
1891 XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
1892 XFS_ERRLEVEL_LOW
, mp
);
1893 error
= XFS_ERROR(EFSCORRUPTED
);
1896 level
= INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
);
1898 entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
) &&
1899 INT_GET(par_node
->btree
[entno
].hashval
, ARCH_CONVERT
) < dead_hash
;
1902 if (unlikely(entno
== INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
))) {
1903 XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
1904 XFS_ERRLEVEL_LOW
, mp
);
1905 error
= XFS_ERROR(EFSCORRUPTED
);
1908 par_blkno
= INT_GET(par_node
->btree
[entno
].before
, ARCH_CONVERT
);
1909 if (level
== dead_level
+ 1)
1911 xfs_da_brelse(tp
, par_buf
);
1915 * We're in the right parent block.
1916 * Look for the right entry.
1920 entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
) &&
1921 INT_GET(par_node
->btree
[entno
].before
, ARCH_CONVERT
) != last_blkno
;
1924 if (entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
))
1926 par_blkno
= INT_GET(par_node
->hdr
.info
.forw
, ARCH_CONVERT
);
1927 xfs_da_brelse(tp
, par_buf
);
1929 if (unlikely(par_blkno
== 0)) {
1930 XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
1931 XFS_ERRLEVEL_LOW
, mp
);
1932 error
= XFS_ERROR(EFSCORRUPTED
);
1935 if ((error
= xfs_da_read_buf(tp
, ip
, par_blkno
, -1, &par_buf
, w
)))
1937 par_node
= par_buf
->data
;
1939 INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
) != level
||
1940 INT_GET(par_node
->hdr
.info
.magic
, ARCH_CONVERT
) != XFS_DA_NODE_MAGIC
)) {
1941 XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
1942 XFS_ERRLEVEL_LOW
, mp
);
1943 error
= XFS_ERROR(EFSCORRUPTED
);
1949 * Update the parent entry pointing to the moved block.
1951 INT_SET(par_node
->btree
[entno
].before
, ARCH_CONVERT
, dead_blkno
);
1952 xfs_da_log_buf(tp
, par_buf
,
1953 XFS_DA_LOGRANGE(par_node
, &par_node
->btree
[entno
].before
,
1954 sizeof(par_node
->btree
[entno
].before
)));
1955 xfs_da_buf_done(par_buf
);
1956 xfs_da_buf_done(dead_buf
);
1957 *dead_blknop
= last_blkno
;
1958 *dead_bufp
= last_buf
;
1962 xfs_da_brelse(tp
, par_buf
);
1964 xfs_da_brelse(tp
, sib_buf
);
1965 xfs_da_brelse(tp
, last_buf
);
1970 * Remove a btree block from a directory or attribute.
1973 xfs_da_shrink_inode(xfs_da_args_t
*args
, xfs_dablk_t dead_blkno
,
1974 xfs_dabuf_t
*dead_buf
)
1977 int done
, error
, w
, count
;
1984 w
= args
->whichfork
;
1987 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
1988 count
= mp
->m_dirblkfsbs
;
1993 * Remove extents. If we get ENOSPC for a dir we have to move
1994 * the last block to the place we want to kill.
1996 if ((error
= xfs_bunmapi(tp
, dp
, dead_blkno
, count
,
1997 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_METADATA
,
1998 0, args
->firstblock
, args
->flist
,
1999 &done
)) == ENOSPC
) {
2000 if (w
!= XFS_DATA_FORK
)
2002 if ((error
= xfs_da_swap_lastblock(args
, &dead_blkno
,
2011 xfs_da_binval(tp
, dead_buf
);
2013 * Adjust the directory size for version 1.
2015 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V1(mp
)) {
2016 if ((error
= xfs_bmap_last_offset(tp
, dp
, &bno
, w
)))
2018 size
= XFS_FSB_TO_B(dp
->i_mount
, bno
);
2019 if (size
!= dp
->i_d
.di_size
) {
2020 dp
->i_d
.di_size
= size
;
2021 xfs_trans_log_inode(tp
, dp
, XFS_ILOG_CORE
);
2026 xfs_da_binval(tp
, dead_buf
);
2031 * See if the mapping(s) for this btree block are valid, i.e.
2032 * don't contain holes, are logically contiguous, and cover the whole range.
2035 xfs_da_map_covers_blocks(
2037 xfs_bmbt_irec_t
*mapp
,
2044 for (i
= 0, off
= bno
; i
< nmap
; i
++) {
2045 if (mapp
[i
].br_startblock
== HOLESTARTBLOCK
||
2046 mapp
[i
].br_startblock
== DELAYSTARTBLOCK
) {
2049 if (off
!= mapp
[i
].br_startoff
) {
2052 off
+= mapp
[i
].br_blockcount
;
2054 return off
== bno
+ count
;
2059 * Used for get_buf, read_buf, read_bufr, and reada_buf.
2066 xfs_daddr_t
*mappedbnop
,
2072 xfs_buf_t
*bp
= NULL
;
2076 xfs_bmbt_irec_t map
;
2077 xfs_bmbt_irec_t
*mapp
;
2078 xfs_daddr_t mappedbno
;
2086 if (whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
2087 nfsb
= mp
->m_dirblkfsbs
;
2090 mappedbno
= *mappedbnop
;
2092 * Caller doesn't have a mapping. -2 means don't complain
2093 * if we land in a hole.
2095 if (mappedbno
== -1 || mappedbno
== -2) {
2097 * Optimize the one-block case.
2103 xfs_bmapi_single(trans
, dp
, whichfork
, &fsb
,
2104 (xfs_fileoff_t
)bno
))) {
2108 if (fsb
== NULLFSBLOCK
) {
2111 map
.br_startblock
= fsb
;
2112 map
.br_startoff
= (xfs_fileoff_t
)bno
;
2113 map
.br_blockcount
= 1;
2117 mapp
= kmem_alloc(sizeof(*mapp
) * nfsb
, KM_SLEEP
);
2119 if ((error
= xfs_bmapi(trans
, dp
, (xfs_fileoff_t
)bno
,
2121 XFS_BMAPI_METADATA
|
2122 XFS_BMAPI_AFLAG(whichfork
),
2123 NULL
, 0, mapp
, &nmap
, NULL
)))
2127 map
.br_startblock
= XFS_DADDR_TO_FSB(mp
, mappedbno
);
2128 map
.br_startoff
= (xfs_fileoff_t
)bno
;
2129 map
.br_blockcount
= nfsb
;
2133 if (!xfs_da_map_covers_blocks(nmap
, mapp
, bno
, nfsb
)) {
2134 error
= mappedbno
== -2 ? 0 : XFS_ERROR(EFSCORRUPTED
);
2135 if (unlikely(error
== EFSCORRUPTED
)) {
2136 if (xfs_error_level
>= XFS_ERRLEVEL_LOW
) {
2138 cmn_err(CE_ALERT
, "xfs_da_do_buf: bno %lld\n",
2140 cmn_err(CE_ALERT
, "dir: inode %lld\n",
2141 (long long)dp
->i_ino
);
2142 for (i
= 0; i
< nmap
; i
++) {
2144 "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d\n",
2146 (long long)mapp
[i
].br_startoff
,
2147 (long long)mapp
[i
].br_startblock
,
2148 (long long)mapp
[i
].br_blockcount
,
2152 XFS_ERROR_REPORT("xfs_da_do_buf(1)",
2153 XFS_ERRLEVEL_LOW
, mp
);
2157 if (caller
!= 3 && nmap
> 1) {
2158 bplist
= kmem_alloc(sizeof(*bplist
) * nmap
, KM_SLEEP
);
2163 * Turn the mapping(s) into buffer(s).
2165 for (i
= 0; i
< nmap
; i
++) {
2168 mappedbno
= XFS_FSB_TO_DADDR(mp
, mapp
[i
].br_startblock
);
2170 *mappedbnop
= mappedbno
;
2171 nmapped
= (int)XFS_FSB_TO_BB(mp
, mapp
[i
].br_blockcount
);
2174 bp
= xfs_trans_get_buf(trans
, mp
->m_ddev_targp
,
2175 mappedbno
, nmapped
, 0);
2176 error
= bp
? XFS_BUF_GETERROR(bp
) : XFS_ERROR(EIO
);
2181 error
= xfs_trans_read_buf(mp
, trans
, mp
->m_ddev_targp
,
2182 mappedbno
, nmapped
, 0, &bp
);
2185 xfs_baread(mp
->m_ddev_targp
, mappedbno
, nmapped
);
2192 xfs_trans_brelse(trans
, bp
);
2198 if (whichfork
== XFS_ATTR_FORK
) {
2199 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_ATTR_BTREE
,
2200 XFS_ATTR_BTREE_REF
);
2202 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_DIR_BTREE
,
2207 bplist
[nbplist
++] = bp
;
2211 * Build a dabuf structure.
2214 rbp
= xfs_da_buf_make(nbplist
, bplist
, ra
);
2216 rbp
= xfs_da_buf_make(1, &bp
, ra
);
2220 * For read_buf, check the magic number.
2223 xfs_dir2_data_t
*data
;
2224 xfs_dir2_free_t
*free
;
2225 xfs_da_blkinfo_t
*info
;
2231 magic
= INT_GET(info
->magic
, ARCH_CONVERT
);
2232 magic1
= INT_GET(data
->hdr
.magic
, ARCH_CONVERT
);
2234 XFS_TEST_ERROR((magic
!= XFS_DA_NODE_MAGIC
) &&
2235 (magic
!= XFS_DIR_LEAF_MAGIC
) &&
2236 (magic
!= XFS_ATTR_LEAF_MAGIC
) &&
2237 (magic
!= XFS_DIR2_LEAF1_MAGIC
) &&
2238 (magic
!= XFS_DIR2_LEAFN_MAGIC
) &&
2239 (magic1
!= XFS_DIR2_BLOCK_MAGIC
) &&
2240 (magic1
!= XFS_DIR2_DATA_MAGIC
) &&
2241 (INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) != XFS_DIR2_FREE_MAGIC
),
2242 mp
, XFS_ERRTAG_DA_READ_BUF
,
2243 XFS_RANDOM_DA_READ_BUF
))) {
2244 xfs_buftrace("DA READ ERROR", rbp
->bps
[0]);
2245 XFS_CORRUPTION_ERROR("xfs_da_do_buf(2)",
2246 XFS_ERRLEVEL_LOW
, mp
, info
);
2247 error
= XFS_ERROR(EFSCORRUPTED
);
2248 xfs_da_brelse(trans
, rbp
);
2254 kmem_free(bplist
, sizeof(*bplist
) * nmap
);
2257 kmem_free(mapp
, sizeof(*mapp
) * nfsb
);
2264 for (i
= 0; i
< nbplist
; i
++)
2265 xfs_trans_brelse(trans
, bplist
[i
]);
2266 kmem_free(bplist
, sizeof(*bplist
) * nmap
);
2270 kmem_free(mapp
, sizeof(*mapp
) * nfsb
);
2277 * Get a buffer for the dir/attr block.
2284 xfs_daddr_t mappedbno
,
2288 return xfs_da_do_buf(trans
, dp
, bno
, &mappedbno
, bpp
, whichfork
, 0,
2289 (inst_t
*)__return_address
);
2293 * Get a buffer for the dir/attr block, fill in the contents.
2300 xfs_daddr_t mappedbno
,
2304 return xfs_da_do_buf(trans
, dp
, bno
, &mappedbno
, bpp
, whichfork
, 1,
2305 (inst_t
*)__return_address
);
2309 * Readahead the dir/attr block.
2321 if (xfs_da_do_buf(trans
, dp
, bno
, &rval
, NULL
, whichfork
, 3,
2322 (inst_t
*)__return_address
))
2329 * Calculate the number of bits needed to hold i different values.
2332 xfs_da_log2_roundup(uint i
)
2336 for (rval
= 0; rval
< NBBY
* sizeof(i
); rval
++) {
2337 if ((1 << rval
) >= i
)
2343 kmem_zone_t
*xfs_da_state_zone
; /* anchor for state struct zone */
2344 kmem_zone_t
*xfs_dabuf_zone
; /* dabuf zone */
2347 * Allocate a dir-state structure.
2348 * We don't put them on the stack since they're large.
2351 xfs_da_state_alloc(void)
2353 return kmem_zone_zalloc(xfs_da_state_zone
, KM_SLEEP
);
2357 * Kill the altpath contents of a da-state structure.
2360 xfs_da_state_kill_altpath(xfs_da_state_t
*state
)
2364 for (i
= 0; i
< state
->altpath
.active
; i
++) {
2365 if (state
->altpath
.blk
[i
].bp
) {
2366 if (state
->altpath
.blk
[i
].bp
!= state
->path
.blk
[i
].bp
)
2367 xfs_da_buf_done(state
->altpath
.blk
[i
].bp
);
2368 state
->altpath
.blk
[i
].bp
= NULL
;
2371 state
->altpath
.active
= 0;
2375 * Free a da-state structure.
2378 xfs_da_state_free(xfs_da_state_t
*state
)
2382 xfs_da_state_kill_altpath(state
);
2383 for (i
= 0; i
< state
->path
.active
; i
++) {
2384 if (state
->path
.blk
[i
].bp
)
2385 xfs_da_buf_done(state
->path
.blk
[i
].bp
);
2387 if (state
->extravalid
&& state
->extrablk
.bp
)
2388 xfs_da_buf_done(state
->extrablk
.bp
);
2390 memset((char *)state
, 0, sizeof(*state
));
2392 kmem_zone_free(xfs_da_state_zone
, state
);
2395 #ifdef XFS_DABUF_DEBUG
2396 xfs_dabuf_t
*xfs_dabuf_global_list
;
2397 lock_t xfs_dabuf_global_lock
;
2404 STATIC xfs_dabuf_t
*
2405 xfs_da_buf_make(int nbuf
, xfs_buf_t
**bps
, inst_t
*ra
)
2413 dabuf
= kmem_zone_alloc(xfs_dabuf_zone
, KM_SLEEP
);
2415 dabuf
= kmem_alloc(XFS_DA_BUF_SIZE(nbuf
), KM_SLEEP
);
2417 #ifdef XFS_DABUF_DEBUG
2419 dabuf
->target
= XFS_BUF_TARGET(bps
[0]);
2420 dabuf
->blkno
= XFS_BUF_ADDR(bps
[0]);
2425 dabuf
->bbcount
= (short)BTOBB(XFS_BUF_COUNT(bp
));
2426 dabuf
->data
= XFS_BUF_PTR(bp
);
2430 for (i
= 0, dabuf
->bbcount
= 0; i
< nbuf
; i
++) {
2431 dabuf
->bps
[i
] = bp
= bps
[i
];
2432 dabuf
->bbcount
+= BTOBB(XFS_BUF_COUNT(bp
));
2434 dabuf
->data
= kmem_alloc(BBTOB(dabuf
->bbcount
), KM_SLEEP
);
2435 for (i
= off
= 0; i
< nbuf
; i
++, off
+= XFS_BUF_COUNT(bp
)) {
2437 memcpy((char *)dabuf
->data
+ off
, XFS_BUF_PTR(bp
),
2441 #ifdef XFS_DABUF_DEBUG
2446 s
= mutex_spinlock(&xfs_dabuf_global_lock
);
2447 for (p
= xfs_dabuf_global_list
; p
; p
= p
->next
) {
2448 ASSERT(p
->blkno
!= dabuf
->blkno
||
2449 p
->target
!= dabuf
->target
);
2452 if (xfs_dabuf_global_list
)
2453 xfs_dabuf_global_list
->prev
= dabuf
;
2454 dabuf
->next
= xfs_dabuf_global_list
;
2455 xfs_dabuf_global_list
= dabuf
;
2456 mutex_spinunlock(&xfs_dabuf_global_lock
, s
);
2466 xfs_da_buf_clean(xfs_dabuf_t
*dabuf
)
2473 ASSERT(dabuf
->nbuf
> 1);
2475 for (i
= off
= 0; i
< dabuf
->nbuf
;
2476 i
++, off
+= XFS_BUF_COUNT(bp
)) {
2478 memcpy(XFS_BUF_PTR(bp
), (char *)dabuf
->data
+ off
,
2488 xfs_da_buf_done(xfs_dabuf_t
*dabuf
)
2491 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2493 xfs_da_buf_clean(dabuf
);
2494 if (dabuf
->nbuf
> 1)
2495 kmem_free(dabuf
->data
, BBTOB(dabuf
->bbcount
));
2496 #ifdef XFS_DABUF_DEBUG
2500 s
= mutex_spinlock(&xfs_dabuf_global_lock
);
2502 dabuf
->prev
->next
= dabuf
->next
;
2504 xfs_dabuf_global_list
= dabuf
->next
;
2506 dabuf
->next
->prev
= dabuf
->prev
;
2507 mutex_spinunlock(&xfs_dabuf_global_lock
, s
);
2509 memset(dabuf
, 0, XFS_DA_BUF_SIZE(dabuf
->nbuf
));
2511 if (dabuf
->nbuf
== 1)
2512 kmem_zone_free(xfs_dabuf_zone
, dabuf
);
2514 kmem_free(dabuf
, XFS_DA_BUF_SIZE(dabuf
->nbuf
));
2518 * Log transaction from a dabuf.
2521 xfs_da_log_buf(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
, uint first
, uint last
)
2529 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2530 if (dabuf
->nbuf
== 1) {
2531 ASSERT(dabuf
->data
== (void *)XFS_BUF_PTR(dabuf
->bps
[0]));
2532 xfs_trans_log_buf(tp
, dabuf
->bps
[0], first
, last
);
2536 ASSERT(first
<= last
);
2537 for (i
= off
= 0; i
< dabuf
->nbuf
; i
++, off
+= XFS_BUF_COUNT(bp
)) {
2540 l
= f
+ XFS_BUF_COUNT(bp
) - 1;
2546 xfs_trans_log_buf(tp
, bp
, f
- off
, l
- off
);
2548 * B_DONE is set by xfs_trans_log buf.
2549 * If we don't set it on a new buffer (get not read)
2550 * then if we don't put anything in the buffer it won't
2551 * be set, and at commit it it released into the cache,
2552 * and then a read will fail.
2554 else if (!(XFS_BUF_ISDONE(bp
)))
2561 * Release dabuf from a transaction.
2562 * Have to free up the dabuf before the buffers are released,
2563 * since the synchronization on the dabuf is really the lock on the buffer.
2566 xfs_da_brelse(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
)
2573 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2574 if ((nbuf
= dabuf
->nbuf
) == 1) {
2578 bplist
= kmem_alloc(nbuf
* sizeof(*bplist
), KM_SLEEP
);
2579 memcpy(bplist
, dabuf
->bps
, nbuf
* sizeof(*bplist
));
2581 xfs_da_buf_done(dabuf
);
2582 for (i
= 0; i
< nbuf
; i
++)
2583 xfs_trans_brelse(tp
, bplist
[i
]);
2585 kmem_free(bplist
, nbuf
* sizeof(*bplist
));
2589 * Invalidate dabuf from a transaction.
2592 xfs_da_binval(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
)
2599 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2600 if ((nbuf
= dabuf
->nbuf
) == 1) {
2604 bplist
= kmem_alloc(nbuf
* sizeof(*bplist
), KM_SLEEP
);
2605 memcpy(bplist
, dabuf
->bps
, nbuf
* sizeof(*bplist
));
2607 xfs_da_buf_done(dabuf
);
2608 for (i
= 0; i
< nbuf
; i
++)
2609 xfs_trans_binval(tp
, bplist
[i
]);
2611 kmem_free(bplist
, nbuf
* sizeof(*bplist
));
2615 * Get the first daddr from a dabuf.
2618 xfs_da_blkno(xfs_dabuf_t
*dabuf
)
2620 ASSERT(dabuf
->nbuf
);
2621 ASSERT(dabuf
->data
);
2622 return XFS_BUF_ADDR(dabuf
->bps
[0]);