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/
35 #include "xfs_macros.h"
36 #include "xfs_types.h"
39 #include "xfs_trans.h"
44 #include "xfs_dmapi.h"
45 #include "xfs_mount.h"
46 #include "xfs_alloc_btree.h"
47 #include "xfs_bmap_btree.h"
48 #include "xfs_ialloc_btree.h"
49 #include "xfs_alloc.h"
50 #include "xfs_btree.h"
51 #include "xfs_attr_sf.h"
52 #include "xfs_dir_sf.h"
53 #include "xfs_dir2_sf.h"
54 #include "xfs_dinode.h"
55 #include "xfs_inode_item.h"
56 #include "xfs_inode.h"
58 #include "xfs_da_btree.h"
60 #include "xfs_attr_leaf.h"
61 #include "xfs_dir_leaf.h"
62 #include "xfs_dir2_data.h"
63 #include "xfs_dir2_leaf.h"
64 #include "xfs_dir2_block.h"
65 #include "xfs_dir2_node.h"
66 #include "xfs_error.h"
72 * Routines to implement directories as Btrees of hashed names.
75 /*========================================================================
76 * Function prototypes for the kernel.
77 *========================================================================*/
80 * Routines used for growing the Btree.
82 STATIC
int xfs_da_root_split(xfs_da_state_t
*state
,
83 xfs_da_state_blk_t
*existing_root
,
84 xfs_da_state_blk_t
*new_child
);
85 STATIC
int xfs_da_node_split(xfs_da_state_t
*state
,
86 xfs_da_state_blk_t
*existing_blk
,
87 xfs_da_state_blk_t
*split_blk
,
88 xfs_da_state_blk_t
*blk_to_add
,
91 STATIC
void xfs_da_node_rebalance(xfs_da_state_t
*state
,
92 xfs_da_state_blk_t
*node_blk_1
,
93 xfs_da_state_blk_t
*node_blk_2
);
94 STATIC
void xfs_da_node_add(xfs_da_state_t
*state
,
95 xfs_da_state_blk_t
*old_node_blk
,
96 xfs_da_state_blk_t
*new_node_blk
);
99 * Routines used for shrinking the Btree.
101 STATIC
int xfs_da_root_join(xfs_da_state_t
*state
,
102 xfs_da_state_blk_t
*root_blk
);
103 STATIC
int xfs_da_node_toosmall(xfs_da_state_t
*state
, int *retval
);
104 STATIC
void xfs_da_node_remove(xfs_da_state_t
*state
,
105 xfs_da_state_blk_t
*drop_blk
);
106 STATIC
void xfs_da_node_unbalance(xfs_da_state_t
*state
,
107 xfs_da_state_blk_t
*src_node_blk
,
108 xfs_da_state_blk_t
*dst_node_blk
);
113 STATIC uint
xfs_da_node_lasthash(xfs_dabuf_t
*bp
, int *count
);
114 STATIC
int xfs_da_node_order(xfs_dabuf_t
*node1_bp
, xfs_dabuf_t
*node2_bp
);
115 STATIC xfs_dabuf_t
*xfs_da_buf_make(int nbuf
, xfs_buf_t
**bps
, inst_t
*ra
);
116 STATIC
int xfs_da_blk_unlink(xfs_da_state_t
*state
,
117 xfs_da_state_blk_t
*drop_blk
,
118 xfs_da_state_blk_t
*save_blk
);
119 STATIC
void xfs_da_state_kill_altpath(xfs_da_state_t
*state
);
121 /*========================================================================
122 * Routines used for growing the Btree.
123 *========================================================================*/
126 * Create the initial contents of an intermediate node.
129 xfs_da_node_create(xfs_da_args_t
*args
, xfs_dablk_t blkno
, int level
,
130 xfs_dabuf_t
**bpp
, int whichfork
)
132 xfs_da_intnode_t
*node
;
138 error
= xfs_da_get_buf(tp
, args
->dp
, blkno
, -1, &bp
, whichfork
);
143 node
->hdr
.info
.forw
= 0;
144 node
->hdr
.info
.back
= 0;
145 INT_SET(node
->hdr
.info
.magic
, ARCH_CONVERT
, XFS_DA_NODE_MAGIC
);
146 node
->hdr
.info
.pad
= 0;
148 INT_SET(node
->hdr
.level
, ARCH_CONVERT
, level
);
150 xfs_da_log_buf(tp
, bp
,
151 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
158 * Split a leaf node, rebalance, then possibly split
159 * intermediate nodes, rebalance, etc.
162 xfs_da_split(xfs_da_state_t
*state
)
164 xfs_da_state_blk_t
*oldblk
, *newblk
, *addblk
;
165 xfs_da_intnode_t
*node
;
167 int max
, action
, error
, i
;
170 * Walk back up the tree splitting/inserting/adjusting as necessary.
171 * If we need to insert and there isn't room, split the node, then
172 * decide which fragment to insert the new block from below into.
173 * Note that we may split the root this way, but we need more fixup.
175 max
= state
->path
.active
- 1;
176 ASSERT((max
>= 0) && (max
< XFS_DA_NODE_MAXDEPTH
));
177 ASSERT(state
->path
.blk
[max
].magic
== XFS_ATTR_LEAF_MAGIC
||
178 state
->path
.blk
[max
].magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
));
180 addblk
= &state
->path
.blk
[max
]; /* initial dummy value */
181 for (i
= max
; (i
>= 0) && addblk
; state
->path
.active
--, i
--) {
182 oldblk
= &state
->path
.blk
[i
];
183 newblk
= &state
->altpath
.blk
[i
];
186 * If a leaf node then
187 * Allocate a new leaf node, then rebalance across them.
188 * else if an intermediate node then
189 * We split on the last layer, must we split the node?
191 switch (oldblk
->magic
) {
192 case XFS_ATTR_LEAF_MAGIC
:
193 error
= xfs_attr_leaf_split(state
, oldblk
, newblk
);
194 if ((error
!= 0) && (error
!= ENOSPC
)) {
195 return(error
); /* GROT: attr is inconsistent */
202 * Entry wouldn't fit, split the leaf again.
204 state
->extravalid
= 1;
206 state
->extraafter
= 0; /* before newblk */
207 error
= xfs_attr_leaf_split(state
, oldblk
,
210 state
->extraafter
= 1; /* after newblk */
211 error
= xfs_attr_leaf_split(state
, newblk
,
215 return(error
); /* GROT: attr inconsistent */
218 case XFS_DIR_LEAF_MAGIC
:
219 ASSERT(XFS_DIR_IS_V1(state
->mp
));
220 error
= xfs_dir_leaf_split(state
, oldblk
, newblk
);
221 if ((error
!= 0) && (error
!= ENOSPC
)) {
222 return(error
); /* GROT: dir is inconsistent */
229 * Entry wouldn't fit, split the leaf again.
231 state
->extravalid
= 1;
233 state
->extraafter
= 0; /* before newblk */
234 error
= xfs_dir_leaf_split(state
, oldblk
,
237 return(error
); /* GROT: dir incon. */
240 state
->extraafter
= 1; /* after newblk */
241 error
= xfs_dir_leaf_split(state
, newblk
,
244 return(error
); /* GROT: dir incon. */
248 case XFS_DIR2_LEAFN_MAGIC
:
249 ASSERT(XFS_DIR_IS_V2(state
->mp
));
250 error
= xfs_dir2_leafn_split(state
, oldblk
, newblk
);
255 case XFS_DA_NODE_MAGIC
:
256 error
= xfs_da_node_split(state
, oldblk
, newblk
, addblk
,
258 xfs_da_buf_done(addblk
->bp
);
261 return(error
); /* GROT: dir is inconsistent */
263 * Record the newly split block for the next time thru?
273 * Update the btree to show the new hashval for this child.
275 xfs_da_fixhashpath(state
, &state
->path
);
277 * If we won't need this block again, it's getting dropped
278 * from the active path by the loop control, so we need
279 * to mark it done now.
281 if (i
> 0 || !addblk
)
282 xfs_da_buf_done(oldblk
->bp
);
288 * Split the root node.
290 ASSERT(state
->path
.active
== 0);
291 oldblk
= &state
->path
.blk
[0];
292 error
= xfs_da_root_split(state
, oldblk
, addblk
);
294 xfs_da_buf_done(oldblk
->bp
);
295 xfs_da_buf_done(addblk
->bp
);
297 return(error
); /* GROT: dir is inconsistent */
301 * Update pointers to the node which used to be block 0 and
302 * just got bumped because of the addition of a new root node.
303 * There might be three blocks involved if a double split occurred,
304 * and the original block 0 could be at any position in the list.
307 node
= oldblk
->bp
->data
;
308 if (node
->hdr
.info
.forw
) {
309 if (INT_GET(node
->hdr
.info
.forw
, ARCH_CONVERT
) == addblk
->blkno
) {
312 ASSERT(state
->extravalid
);
313 bp
= state
->extrablk
.bp
;
316 INT_SET(node
->hdr
.info
.back
, ARCH_CONVERT
, oldblk
->blkno
);
317 xfs_da_log_buf(state
->args
->trans
, bp
,
318 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
319 sizeof(node
->hdr
.info
)));
321 node
= oldblk
->bp
->data
;
322 if (INT_GET(node
->hdr
.info
.back
, ARCH_CONVERT
)) {
323 if (INT_GET(node
->hdr
.info
.back
, ARCH_CONVERT
) == addblk
->blkno
) {
326 ASSERT(state
->extravalid
);
327 bp
= state
->extrablk
.bp
;
330 INT_SET(node
->hdr
.info
.forw
, ARCH_CONVERT
, oldblk
->blkno
);
331 xfs_da_log_buf(state
->args
->trans
, bp
,
332 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
333 sizeof(node
->hdr
.info
)));
335 xfs_da_buf_done(oldblk
->bp
);
336 xfs_da_buf_done(addblk
->bp
);
342 * Split the root. We have to create a new root and point to the two
343 * parts (the split old root) that we just created. Copy block zero to
344 * the EOF, extending the inode in process.
346 STATIC
int /* error */
347 xfs_da_root_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
348 xfs_da_state_blk_t
*blk2
)
350 xfs_da_intnode_t
*node
, *oldroot
;
358 xfs_dir2_leaf_t
*leaf
;
361 * Copy the existing (incorrect) block from the root node position
362 * to a free space somewhere.
365 ASSERT(args
!= NULL
);
366 error
= xfs_da_grow_inode(args
, &blkno
);
372 error
= xfs_da_get_buf(tp
, dp
, blkno
, -1, &bp
, args
->whichfork
);
377 oldroot
= blk1
->bp
->data
;
378 if (INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
379 size
= (int)((char *)&oldroot
->btree
[INT_GET(oldroot
->hdr
.count
, ARCH_CONVERT
)] -
382 ASSERT(XFS_DIR_IS_V2(mp
));
383 ASSERT(INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
384 leaf
= (xfs_dir2_leaf_t
*)oldroot
;
385 size
= (int)((char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] -
388 memcpy(node
, oldroot
, size
);
389 xfs_da_log_buf(tp
, bp
, 0, size
- 1);
390 xfs_da_buf_done(blk1
->bp
);
395 * Set up the new root node.
397 error
= xfs_da_node_create(args
,
398 args
->whichfork
== XFS_DATA_FORK
&&
399 XFS_DIR_IS_V2(mp
) ? mp
->m_dirleafblk
: 0,
400 INT_GET(node
->hdr
.level
, ARCH_CONVERT
) + 1, &bp
, args
->whichfork
);
404 INT_SET(node
->btree
[0].hashval
, ARCH_CONVERT
, blk1
->hashval
);
405 INT_SET(node
->btree
[0].before
, ARCH_CONVERT
, blk1
->blkno
);
406 INT_SET(node
->btree
[1].hashval
, ARCH_CONVERT
, blk2
->hashval
);
407 INT_SET(node
->btree
[1].before
, ARCH_CONVERT
, blk2
->blkno
);
408 INT_SET(node
->hdr
.count
, ARCH_CONVERT
, 2);
411 if (INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
) {
412 ASSERT(blk1
->blkno
>= mp
->m_dirleafblk
&&
413 blk1
->blkno
< mp
->m_dirfreeblk
);
414 ASSERT(blk2
->blkno
>= mp
->m_dirleafblk
&&
415 blk2
->blkno
< mp
->m_dirfreeblk
);
419 /* Header is already logged by xfs_da_node_create */
420 xfs_da_log_buf(tp
, bp
,
421 XFS_DA_LOGRANGE(node
, node
->btree
,
422 sizeof(xfs_da_node_entry_t
) * 2));
429 * Split the node, rebalance, then add the new entry.
431 STATIC
int /* error */
432 xfs_da_node_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
433 xfs_da_state_blk_t
*newblk
,
434 xfs_da_state_blk_t
*addblk
,
435 int treelevel
, int *result
)
437 xfs_da_intnode_t
*node
;
442 node
= oldblk
->bp
->data
;
443 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
446 * With V2 the extra block is data or freespace.
448 useextra
= state
->extravalid
&& XFS_DIR_IS_V1(state
->mp
);
449 newcount
= 1 + useextra
;
451 * Do we have to split the node?
453 if ((INT_GET(node
->hdr
.count
, ARCH_CONVERT
) + newcount
) > state
->node_ents
) {
455 * Allocate a new node, add to the doubly linked chain of
456 * nodes, then move some of our excess entries into it.
458 error
= xfs_da_grow_inode(state
->args
, &blkno
);
460 return(error
); /* GROT: dir is inconsistent */
462 error
= xfs_da_node_create(state
->args
, blkno
, treelevel
,
463 &newblk
->bp
, state
->args
->whichfork
);
465 return(error
); /* GROT: dir is inconsistent */
466 newblk
->blkno
= blkno
;
467 newblk
->magic
= XFS_DA_NODE_MAGIC
;
468 xfs_da_node_rebalance(state
, oldblk
, newblk
);
469 error
= xfs_da_blk_link(state
, oldblk
, newblk
);
478 * Insert the new entry(s) into the correct block
479 * (updating last hashval in the process).
481 * xfs_da_node_add() inserts BEFORE the given index,
482 * and as a result of using node_lookup_int() we always
483 * point to a valid entry (not after one), but a split
484 * operation always results in a new block whose hashvals
485 * FOLLOW the current block.
487 * If we had double-split op below us, then add the extra block too.
489 node
= oldblk
->bp
->data
;
490 if (oldblk
->index
<= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)) {
492 xfs_da_node_add(state
, oldblk
, addblk
);
494 if (state
->extraafter
)
496 xfs_da_node_add(state
, oldblk
, &state
->extrablk
);
497 state
->extravalid
= 0;
501 xfs_da_node_add(state
, newblk
, addblk
);
503 if (state
->extraafter
)
505 xfs_da_node_add(state
, newblk
, &state
->extrablk
);
506 state
->extravalid
= 0;
514 * Balance the btree elements between two intermediate nodes,
515 * usually one full and one empty.
517 * NOTE: if blk2 is empty, then it will get the upper half of blk1.
520 xfs_da_node_rebalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
521 xfs_da_state_blk_t
*blk2
)
523 xfs_da_intnode_t
*node1
, *node2
, *tmpnode
;
524 xfs_da_node_entry_t
*btree_s
, *btree_d
;
528 node1
= blk1
->bp
->data
;
529 node2
= blk2
->bp
->data
;
531 * Figure out how many entries need to move, and in which direction.
532 * Swap the nodes around if that makes it simpler.
534 if ((INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) > 0) && (INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) > 0) &&
535 ((INT_GET(node2
->btree
[ 0 ].hashval
, ARCH_CONVERT
) < INT_GET(node1
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
536 (INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
537 INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))) {
542 ASSERT(INT_GET(node1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
543 ASSERT(INT_GET(node2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
544 count
= (INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) - INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)) / 2;
547 tp
= state
->args
->trans
;
549 * Two cases: high-to-low and low-to-high.
553 * Move elements in node2 up to make a hole.
555 if ((tmp
= INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)) > 0) {
556 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
557 btree_s
= &node2
->btree
[0];
558 btree_d
= &node2
->btree
[count
];
559 memmove(btree_d
, btree_s
, tmp
);
563 * Move the req'd B-tree elements from high in node1 to
566 INT_MOD(node2
->hdr
.count
, ARCH_CONVERT
, count
);
567 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
568 btree_s
= &node1
->btree
[INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) - count
];
569 btree_d
= &node2
->btree
[0];
570 memcpy(btree_d
, btree_s
, tmp
);
571 INT_MOD(node1
->hdr
.count
, ARCH_CONVERT
, -(count
));
575 * Move the req'd B-tree elements from low in node2 to
579 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
580 btree_s
= &node2
->btree
[0];
581 btree_d
= &node1
->btree
[INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)];
582 memcpy(btree_d
, btree_s
, tmp
);
583 INT_MOD(node1
->hdr
.count
, ARCH_CONVERT
, count
);
584 xfs_da_log_buf(tp
, blk1
->bp
,
585 XFS_DA_LOGRANGE(node1
, btree_d
, tmp
));
588 * Move elements in node2 down to fill the hole.
590 tmp
= INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) - count
;
591 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
592 btree_s
= &node2
->btree
[count
];
593 btree_d
= &node2
->btree
[0];
594 memmove(btree_d
, btree_s
, tmp
);
595 INT_MOD(node2
->hdr
.count
, ARCH_CONVERT
, -(count
));
599 * Log header of node 1 and all current bits of node 2.
601 xfs_da_log_buf(tp
, blk1
->bp
,
602 XFS_DA_LOGRANGE(node1
, &node1
->hdr
, sizeof(node1
->hdr
)));
603 xfs_da_log_buf(tp
, blk2
->bp
,
604 XFS_DA_LOGRANGE(node2
, &node2
->hdr
,
606 sizeof(node2
->btree
[0]) * INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)));
609 * Record the last hashval from each block for upward propagation.
610 * (note: don't use the swapped node pointers)
612 node1
= blk1
->bp
->data
;
613 node2
= blk2
->bp
->data
;
614 blk1
->hashval
= INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
615 blk2
->hashval
= INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
618 * Adjust the expected index for insertion.
620 if (blk1
->index
>= INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)) {
621 blk2
->index
= blk1
->index
- INT_GET(node1
->hdr
.count
, ARCH_CONVERT
);
622 blk1
->index
= INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) + 1; /* make it invalid */
627 * Add a new entry to an intermediate node.
630 xfs_da_node_add(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
631 xfs_da_state_blk_t
*newblk
)
633 xfs_da_intnode_t
*node
;
634 xfs_da_node_entry_t
*btree
;
638 node
= oldblk
->bp
->data
;
640 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
641 ASSERT((oldblk
->index
>= 0) && (oldblk
->index
<= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)));
642 ASSERT(newblk
->blkno
!= 0);
643 if (state
->args
->whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
644 ASSERT(newblk
->blkno
>= mp
->m_dirleafblk
&&
645 newblk
->blkno
< mp
->m_dirfreeblk
);
648 * We may need to make some room before we insert the new node.
651 btree
= &node
->btree
[ oldblk
->index
];
652 if (oldblk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
)) {
653 tmp
= (INT_GET(node
->hdr
.count
, ARCH_CONVERT
) - oldblk
->index
) * (uint
)sizeof(*btree
);
654 memmove(btree
+ 1, btree
, tmp
);
656 INT_SET(btree
->hashval
, ARCH_CONVERT
, newblk
->hashval
);
657 INT_SET(btree
->before
, ARCH_CONVERT
, newblk
->blkno
);
658 xfs_da_log_buf(state
->args
->trans
, oldblk
->bp
,
659 XFS_DA_LOGRANGE(node
, btree
, tmp
+ sizeof(*btree
)));
660 INT_MOD(node
->hdr
.count
, ARCH_CONVERT
, +1);
661 xfs_da_log_buf(state
->args
->trans
, oldblk
->bp
,
662 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
665 * Copy the last hash value from the oldblk to propagate upwards.
667 oldblk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
670 /*========================================================================
671 * Routines used for shrinking the Btree.
672 *========================================================================*/
675 * Deallocate an empty leaf node, remove it from its parent,
676 * possibly deallocating that block, etc...
679 xfs_da_join(xfs_da_state_t
*state
)
681 xfs_da_state_blk_t
*drop_blk
, *save_blk
;
685 drop_blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
686 save_blk
= &state
->altpath
.blk
[ state
->path
.active
-1 ];
687 ASSERT(state
->path
.blk
[0].magic
== XFS_DA_NODE_MAGIC
);
688 ASSERT(drop_blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
689 drop_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
));
692 * Walk back up the tree joining/deallocating as necessary.
693 * When we stop dropping blocks, break out.
695 for ( ; state
->path
.active
>= 2; drop_blk
--, save_blk
--,
696 state
->path
.active
--) {
698 * See if we can combine the block with a neighbor.
699 * (action == 0) => no options, just leave
700 * (action == 1) => coalesce, then unlink
701 * (action == 2) => block empty, unlink it
703 switch (drop_blk
->magic
) {
704 case XFS_ATTR_LEAF_MAGIC
:
705 error
= xfs_attr_leaf_toosmall(state
, &action
);
710 xfs_attr_leaf_unbalance(state
, drop_blk
, save_blk
);
712 case XFS_DIR_LEAF_MAGIC
:
713 ASSERT(XFS_DIR_IS_V1(state
->mp
));
714 error
= xfs_dir_leaf_toosmall(state
, &action
);
719 xfs_dir_leaf_unbalance(state
, drop_blk
, save_blk
);
721 case XFS_DIR2_LEAFN_MAGIC
:
722 ASSERT(XFS_DIR_IS_V2(state
->mp
));
723 error
= xfs_dir2_leafn_toosmall(state
, &action
);
728 xfs_dir2_leafn_unbalance(state
, drop_blk
, save_blk
);
730 case XFS_DA_NODE_MAGIC
:
732 * Remove the offending node, fixup hashvals,
733 * check for a toosmall neighbor.
735 xfs_da_node_remove(state
, drop_blk
);
736 xfs_da_fixhashpath(state
, &state
->path
);
737 error
= xfs_da_node_toosmall(state
, &action
);
742 xfs_da_node_unbalance(state
, drop_blk
, save_blk
);
745 xfs_da_fixhashpath(state
, &state
->altpath
);
746 error
= xfs_da_blk_unlink(state
, drop_blk
, save_blk
);
747 xfs_da_state_kill_altpath(state
);
750 error
= xfs_da_shrink_inode(state
->args
, drop_blk
->blkno
,
757 * We joined all the way to the top. If it turns out that
758 * we only have one entry in the root, make the child block
761 xfs_da_node_remove(state
, drop_blk
);
762 xfs_da_fixhashpath(state
, &state
->path
);
763 error
= xfs_da_root_join(state
, &state
->path
.blk
[0]);
768 * We have only one entry in the root. Copy the only remaining child of
769 * the old root to block 0 as the new root node.
772 xfs_da_root_join(xfs_da_state_t
*state
, xfs_da_state_blk_t
*root_blk
)
774 xfs_da_intnode_t
*oldroot
;
776 xfs_da_blkinfo_t
*blkinfo
;
783 ASSERT(args
!= NULL
);
784 ASSERT(root_blk
->magic
== XFS_DA_NODE_MAGIC
);
785 oldroot
= root_blk
->bp
->data
;
786 ASSERT(INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
787 ASSERT(!oldroot
->hdr
.info
.forw
);
788 ASSERT(!oldroot
->hdr
.info
.back
);
791 * If the root has more than one child, then don't do anything.
793 if (INT_GET(oldroot
->hdr
.count
, ARCH_CONVERT
) > 1)
797 * Read in the (only) child block, then copy those bytes into
798 * the root block's buffer and free the original child block.
800 child
= INT_GET(oldroot
->btree
[ 0 ].before
, ARCH_CONVERT
);
802 error
= xfs_da_read_buf(args
->trans
, args
->dp
, child
, -1, &bp
,
808 if (INT_GET(oldroot
->hdr
.level
, ARCH_CONVERT
) == 1) {
809 ASSERT(INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
810 INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
812 ASSERT(INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
814 ASSERT(!blkinfo
->forw
);
815 ASSERT(!blkinfo
->back
);
816 memcpy(root_blk
->bp
->data
, bp
->data
, state
->blocksize
);
817 xfs_da_log_buf(args
->trans
, root_blk
->bp
, 0, state
->blocksize
- 1);
818 error
= xfs_da_shrink_inode(args
, child
, bp
);
823 * Check a node block and its neighbors to see if the block should be
824 * collapsed into one or the other neighbor. Always keep the block
825 * with the smaller block number.
826 * If the current block is over 50% full, don't try to join it, return 0.
827 * If the block is empty, fill in the state structure and return 2.
828 * If it can be collapsed, fill in the state structure and return 1.
829 * If nothing can be done, return 0.
832 xfs_da_node_toosmall(xfs_da_state_t
*state
, int *action
)
834 xfs_da_intnode_t
*node
;
835 xfs_da_state_blk_t
*blk
;
836 xfs_da_blkinfo_t
*info
;
837 int count
, forward
, error
, retval
, i
;
842 * Check for the degenerate case of the block being over 50% full.
843 * If so, it's not worth even looking to see if we might be able
844 * to coalesce with a sibling.
846 blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
847 info
= blk
->bp
->data
;
848 ASSERT(INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
849 node
= (xfs_da_intnode_t
*)info
;
850 count
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
851 if (count
> (state
->node_ents
>> 1)) {
852 *action
= 0; /* blk over 50%, don't try to join */
853 return(0); /* blk over 50%, don't try to join */
857 * Check for the degenerate case of the block being empty.
858 * If the block is empty, we'll simply delete it, no need to
859 * coalesce it with a sibling block. We choose (aribtrarily)
860 * to merge with the forward block unless it is NULL.
864 * Make altpath point to the block we want to keep and
865 * path point to the block we want to drop (this one).
867 forward
= info
->forw
;
868 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
869 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
882 * Examine each sibling block to see if we can coalesce with
883 * at least 25% free space to spare. We need to figure out
884 * whether to merge with the forward or the backward block.
885 * We prefer coalescing with the lower numbered sibling so as
886 * to shrink a directory over time.
888 /* start with smaller blk num */
889 forward
= (INT_GET(info
->forw
, ARCH_CONVERT
)
890 < INT_GET(info
->back
, ARCH_CONVERT
));
891 for (i
= 0; i
< 2; forward
= !forward
, i
++) {
893 blkno
= INT_GET(info
->forw
, ARCH_CONVERT
);
895 blkno
= INT_GET(info
->back
, ARCH_CONVERT
);
898 error
= xfs_da_read_buf(state
->args
->trans
, state
->args
->dp
,
899 blkno
, -1, &bp
, state
->args
->whichfork
);
904 node
= (xfs_da_intnode_t
*)info
;
905 count
= state
->node_ents
;
906 count
-= state
->node_ents
>> 2;
907 count
-= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
909 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
910 count
-= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
911 xfs_da_brelse(state
->args
->trans
, bp
);
913 break; /* fits with at least 25% to spare */
921 * Make altpath point to the block we want to keep (the lower
922 * numbered block) and path point to the block we want to drop.
924 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
925 if (blkno
< blk
->blkno
) {
926 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
936 error
= xfs_da_path_shift(state
, &state
->path
, forward
,
951 * Walk back up the tree adjusting hash values as necessary,
952 * when we stop making changes, return.
955 xfs_da_fixhashpath(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
)
957 xfs_da_state_blk_t
*blk
;
958 xfs_da_intnode_t
*node
;
959 xfs_da_node_entry_t
*btree
;
960 xfs_dahash_t lasthash
=0;
963 level
= path
->active
-1;
964 blk
= &path
->blk
[ level
];
965 switch (blk
->magic
) {
966 case XFS_ATTR_LEAF_MAGIC
:
967 lasthash
= xfs_attr_leaf_lasthash(blk
->bp
, &count
);
971 case XFS_DIR_LEAF_MAGIC
:
972 ASSERT(XFS_DIR_IS_V1(state
->mp
));
973 lasthash
= xfs_dir_leaf_lasthash(blk
->bp
, &count
);
977 case XFS_DIR2_LEAFN_MAGIC
:
978 ASSERT(XFS_DIR_IS_V2(state
->mp
));
979 lasthash
= xfs_dir2_leafn_lasthash(blk
->bp
, &count
);
983 case XFS_DA_NODE_MAGIC
:
984 lasthash
= xfs_da_node_lasthash(blk
->bp
, &count
);
989 for (blk
--, level
--; level
>= 0; blk
--, level
--) {
990 node
= blk
->bp
->data
;
991 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
992 btree
= &node
->btree
[ blk
->index
];
993 if (INT_GET(btree
->hashval
, ARCH_CONVERT
) == lasthash
)
995 blk
->hashval
= lasthash
;
996 INT_SET(btree
->hashval
, ARCH_CONVERT
, lasthash
);
997 xfs_da_log_buf(state
->args
->trans
, blk
->bp
,
998 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
1000 lasthash
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1005 * Remove an entry from an intermediate node.
1008 xfs_da_node_remove(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
)
1010 xfs_da_intnode_t
*node
;
1011 xfs_da_node_entry_t
*btree
;
1014 node
= drop_blk
->bp
->data
;
1015 ASSERT(drop_blk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
));
1016 ASSERT(drop_blk
->index
>= 0);
1019 * Copy over the offending entry, or just zero it out.
1021 btree
= &node
->btree
[drop_blk
->index
];
1022 if (drop_blk
->index
< (INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1)) {
1023 tmp
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
) - drop_blk
->index
- 1;
1024 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
1025 memmove(btree
, btree
+ 1, tmp
);
1026 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
1027 XFS_DA_LOGRANGE(node
, btree
, tmp
));
1028 btree
= &node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ];
1030 memset((char *)btree
, 0, sizeof(xfs_da_node_entry_t
));
1031 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
1032 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
1033 INT_MOD(node
->hdr
.count
, ARCH_CONVERT
, -1);
1034 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
1035 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
1038 * Copy the last hash value from the block to propagate upwards.
1041 drop_blk
->hashval
= INT_GET(btree
->hashval
, ARCH_CONVERT
);
1045 * Unbalance the btree elements between two intermediate nodes,
1046 * move all Btree elements from one node into another.
1049 xfs_da_node_unbalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
1050 xfs_da_state_blk_t
*save_blk
)
1052 xfs_da_intnode_t
*drop_node
, *save_node
;
1053 xfs_da_node_entry_t
*btree
;
1057 drop_node
= drop_blk
->bp
->data
;
1058 save_node
= save_blk
->bp
->data
;
1059 ASSERT(INT_GET(drop_node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1060 ASSERT(INT_GET(save_node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1061 tp
= state
->args
->trans
;
1064 * If the dying block has lower hashvals, then move all the
1065 * elements in the remaining block up to make a hole.
1067 if ((INT_GET(drop_node
->btree
[ 0 ].hashval
, ARCH_CONVERT
) < INT_GET(save_node
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
1068 (INT_GET(drop_node
->btree
[ INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
1069 INT_GET(save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))
1071 btree
= &save_node
->btree
[ INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) ];
1072 tmp
= INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_da_node_entry_t
);
1073 memmove(btree
, &save_node
->btree
[0], tmp
);
1074 btree
= &save_node
->btree
[0];
1075 xfs_da_log_buf(tp
, save_blk
->bp
,
1076 XFS_DA_LOGRANGE(save_node
, btree
,
1077 (INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) + INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
)) *
1078 sizeof(xfs_da_node_entry_t
)));
1080 btree
= &save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) ];
1081 xfs_da_log_buf(tp
, save_blk
->bp
,
1082 XFS_DA_LOGRANGE(save_node
, btree
,
1083 INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) *
1084 sizeof(xfs_da_node_entry_t
)));
1088 * Move all the B-tree elements from drop_blk to save_blk.
1090 tmp
= INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_da_node_entry_t
);
1091 memcpy(btree
, &drop_node
->btree
[0], tmp
);
1092 INT_MOD(save_node
->hdr
.count
, ARCH_CONVERT
, INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
));
1094 xfs_da_log_buf(tp
, save_blk
->bp
,
1095 XFS_DA_LOGRANGE(save_node
, &save_node
->hdr
,
1096 sizeof(save_node
->hdr
)));
1099 * Save the last hashval in the remaining block for upward propagation.
1101 save_blk
->hashval
= INT_GET(save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1104 /*========================================================================
1105 * Routines used for finding things in the Btree.
1106 *========================================================================*/
1109 * Walk down the Btree looking for a particular filename, filling
1110 * in the state structure as we go.
1112 * We will set the state structure to point to each of the elements
1113 * in each of the nodes where either the hashval is or should be.
1115 * We support duplicate hashval's so for each entry in the current
1116 * node that could contain the desired hashval, descend. This is a
1117 * pruned depth-first tree search.
1120 xfs_da_node_lookup_int(xfs_da_state_t
*state
, int *result
)
1122 xfs_da_state_blk_t
*blk
;
1123 xfs_da_blkinfo_t
*curr
;
1124 xfs_da_intnode_t
*node
;
1125 xfs_da_node_entry_t
*btree
;
1127 int probe
, span
, max
, error
, retval
;
1128 xfs_dahash_t hashval
;
1129 xfs_da_args_t
*args
;
1134 * Descend thru the B-tree searching each level for the right
1135 * node to use, until the right hashval is found.
1137 if (args
->whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(state
->mp
))
1138 blkno
= state
->mp
->m_dirleafblk
;
1141 for (blk
= &state
->path
.blk
[0], state
->path
.active
= 1;
1142 state
->path
.active
<= XFS_DA_NODE_MAXDEPTH
;
1143 blk
++, state
->path
.active
++) {
1145 * Read the next node down in the tree.
1148 error
= xfs_da_read_buf(args
->trans
, args
->dp
, blkno
,
1149 -1, &blk
->bp
, args
->whichfork
);
1152 state
->path
.active
--;
1155 curr
= blk
->bp
->data
;
1156 ASSERT(INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
||
1157 INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1158 INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
1161 * Search an intermediate node for a match.
1163 blk
->magic
= INT_GET(curr
->magic
, ARCH_CONVERT
);
1164 if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
1165 node
= blk
->bp
->data
;
1166 blk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1169 * Binary search. (note: small blocks will skip loop)
1171 max
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
1172 probe
= span
= max
/ 2;
1173 hashval
= args
->hashval
;
1174 for (btree
= &node
->btree
[probe
]; span
> 4;
1175 btree
= &node
->btree
[probe
]) {
1177 if (INT_GET(btree
->hashval
, ARCH_CONVERT
) < hashval
)
1179 else if (INT_GET(btree
->hashval
, ARCH_CONVERT
) > hashval
)
1184 ASSERT((probe
>= 0) && (probe
< max
));
1185 ASSERT((span
<= 4) || (INT_GET(btree
->hashval
, ARCH_CONVERT
) == hashval
));
1188 * Since we may have duplicate hashval's, find the first
1189 * matching hashval in the node.
1191 while ((probe
> 0) && (INT_GET(btree
->hashval
, ARCH_CONVERT
) >= hashval
)) {
1195 while ((probe
< max
) && (INT_GET(btree
->hashval
, ARCH_CONVERT
) < hashval
)) {
1201 * Pick the right block to descend on.
1205 blkno
= INT_GET(node
->btree
[ max
-1 ].before
, ARCH_CONVERT
);
1208 blkno
= INT_GET(btree
->before
, ARCH_CONVERT
);
1211 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
) {
1212 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
, NULL
);
1215 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
) {
1216 blk
->hashval
= xfs_dir_leaf_lasthash(blk
->bp
, NULL
);
1219 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
) {
1220 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
, NULL
);
1226 * A leaf block that ends in the hashval that we are interested in
1227 * (final hashval == search hashval) means that the next block may
1228 * contain more entries with the same hashval, shift upward to the
1229 * next leaf and keep searching.
1232 if (blk
->magic
== XFS_DIR_LEAF_MAGIC
) {
1233 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1234 retval
= xfs_dir_leaf_lookup_int(blk
->bp
, args
,
1236 } else if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
) {
1237 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1238 retval
= xfs_dir2_leafn_lookup_int(blk
->bp
, args
,
1239 &blk
->index
, state
);
1241 else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1242 retval
= xfs_attr_leaf_lookup_int(blk
->bp
, args
);
1243 blk
->index
= args
->index
;
1244 args
->blkno
= blk
->blkno
;
1246 if (((retval
== ENOENT
) || (retval
== ENOATTR
)) &&
1247 (blk
->hashval
== args
->hashval
)) {
1248 error
= xfs_da_path_shift(state
, &state
->path
, 1, 1,
1255 else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1256 /* path_shift() gives ENOENT */
1257 retval
= XFS_ERROR(ENOATTR
);
1266 /*========================================================================
1268 *========================================================================*/
1271 * Link a new block into a doubly linked list of blocks (of whatever type).
1274 xfs_da_blk_link(xfs_da_state_t
*state
, xfs_da_state_blk_t
*old_blk
,
1275 xfs_da_state_blk_t
*new_blk
)
1277 xfs_da_blkinfo_t
*old_info
, *new_info
, *tmp_info
;
1278 xfs_da_args_t
*args
;
1279 int before
=0, error
;
1283 * Set up environment.
1286 ASSERT(args
!= NULL
);
1287 old_info
= old_blk
->bp
->data
;
1288 new_info
= new_blk
->bp
->data
;
1289 ASSERT(old_blk
->magic
== XFS_DA_NODE_MAGIC
||
1290 old_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1291 old_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1292 ASSERT(old_blk
->magic
== INT_GET(old_info
->magic
, ARCH_CONVERT
));
1293 ASSERT(new_blk
->magic
== INT_GET(new_info
->magic
, ARCH_CONVERT
));
1294 ASSERT(old_blk
->magic
== new_blk
->magic
);
1296 switch (old_blk
->magic
) {
1297 case XFS_ATTR_LEAF_MAGIC
:
1298 before
= xfs_attr_leaf_order(old_blk
->bp
, new_blk
->bp
);
1300 case XFS_DIR_LEAF_MAGIC
:
1301 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1302 before
= xfs_dir_leaf_order(old_blk
->bp
, new_blk
->bp
);
1304 case XFS_DIR2_LEAFN_MAGIC
:
1305 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1306 before
= xfs_dir2_leafn_order(old_blk
->bp
, new_blk
->bp
);
1308 case XFS_DA_NODE_MAGIC
:
1309 before
= xfs_da_node_order(old_blk
->bp
, new_blk
->bp
);
1314 * Link blocks in appropriate order.
1318 * Link new block in before existing block.
1320 INT_SET(new_info
->forw
, ARCH_CONVERT
, old_blk
->blkno
);
1321 new_info
->back
= old_info
->back
; /* INT_: direct copy */
1322 if (INT_GET(old_info
->back
, ARCH_CONVERT
)) {
1323 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1324 INT_GET(old_info
->back
,
1325 ARCH_CONVERT
), -1, &bp
,
1330 tmp_info
= bp
->data
;
1331 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
) == INT_GET(old_info
->magic
, ARCH_CONVERT
));
1332 ASSERT(INT_GET(tmp_info
->forw
, ARCH_CONVERT
) == old_blk
->blkno
);
1333 INT_SET(tmp_info
->forw
, ARCH_CONVERT
, new_blk
->blkno
);
1334 xfs_da_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1335 xfs_da_buf_done(bp
);
1337 INT_SET(old_info
->back
, ARCH_CONVERT
, new_blk
->blkno
);
1340 * Link new block in after existing block.
1342 new_info
->forw
= old_info
->forw
; /* INT_: direct copy */
1343 INT_SET(new_info
->back
, ARCH_CONVERT
, old_blk
->blkno
);
1344 if (INT_GET(old_info
->forw
, ARCH_CONVERT
)) {
1345 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1346 INT_GET(old_info
->forw
, ARCH_CONVERT
), -1, &bp
,
1351 tmp_info
= bp
->data
;
1352 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
)
1353 == INT_GET(old_info
->magic
, ARCH_CONVERT
));
1354 ASSERT(INT_GET(tmp_info
->back
, ARCH_CONVERT
)
1356 INT_SET(tmp_info
->back
, ARCH_CONVERT
, new_blk
->blkno
);
1357 xfs_da_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1358 xfs_da_buf_done(bp
);
1360 INT_SET(old_info
->forw
, ARCH_CONVERT
, new_blk
->blkno
);
1363 xfs_da_log_buf(args
->trans
, old_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1364 xfs_da_log_buf(args
->trans
, new_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1369 * Compare two intermediate nodes for "order".
1372 xfs_da_node_order(xfs_dabuf_t
*node1_bp
, xfs_dabuf_t
*node2_bp
)
1374 xfs_da_intnode_t
*node1
, *node2
;
1376 node1
= node1_bp
->data
;
1377 node2
= node2_bp
->data
;
1378 ASSERT((INT_GET(node1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) &&
1379 (INT_GET(node2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
));
1380 if ((INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) > 0) && (INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) > 0) &&
1381 ((INT_GET(node2
->btree
[ 0 ].hashval
, ARCH_CONVERT
) <
1382 INT_GET(node1
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
1383 (INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
1384 INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))) {
1391 * Pick up the last hashvalue from an intermediate node.
1394 xfs_da_node_lasthash(xfs_dabuf_t
*bp
, int *count
)
1396 xfs_da_intnode_t
*node
;
1399 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1401 *count
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
1402 if (!node
->hdr
.count
)
1404 return(INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
));
1408 * Unlink a block from a doubly linked list of blocks.
1410 STATIC
int /* error */
1411 xfs_da_blk_unlink(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
1412 xfs_da_state_blk_t
*save_blk
)
1414 xfs_da_blkinfo_t
*drop_info
, *save_info
, *tmp_info
;
1415 xfs_da_args_t
*args
;
1420 * Set up environment.
1423 ASSERT(args
!= NULL
);
1424 save_info
= save_blk
->bp
->data
;
1425 drop_info
= drop_blk
->bp
->data
;
1426 ASSERT(save_blk
->magic
== XFS_DA_NODE_MAGIC
||
1427 save_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1428 save_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1429 ASSERT(save_blk
->magic
== INT_GET(save_info
->magic
, ARCH_CONVERT
));
1430 ASSERT(drop_blk
->magic
== INT_GET(drop_info
->magic
, ARCH_CONVERT
));
1431 ASSERT(save_blk
->magic
== drop_blk
->magic
);
1432 ASSERT((INT_GET(save_info
->forw
, ARCH_CONVERT
) == drop_blk
->blkno
) ||
1433 (INT_GET(save_info
->back
, ARCH_CONVERT
) == drop_blk
->blkno
));
1434 ASSERT((INT_GET(drop_info
->forw
, ARCH_CONVERT
) == save_blk
->blkno
) ||
1435 (INT_GET(drop_info
->back
, ARCH_CONVERT
) == save_blk
->blkno
));
1438 * Unlink the leaf block from the doubly linked chain of leaves.
1440 if (INT_GET(save_info
->back
, ARCH_CONVERT
) == drop_blk
->blkno
) {
1441 save_info
->back
= drop_info
->back
; /* INT_: direct copy */
1442 if (INT_GET(drop_info
->back
, ARCH_CONVERT
)) {
1443 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1444 INT_GET(drop_info
->back
,
1445 ARCH_CONVERT
), -1, &bp
,
1450 tmp_info
= bp
->data
;
1451 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
) == INT_GET(save_info
->magic
, ARCH_CONVERT
));
1452 ASSERT(INT_GET(tmp_info
->forw
, ARCH_CONVERT
) == drop_blk
->blkno
);
1453 INT_SET(tmp_info
->forw
, ARCH_CONVERT
, save_blk
->blkno
);
1454 xfs_da_log_buf(args
->trans
, bp
, 0,
1455 sizeof(*tmp_info
) - 1);
1456 xfs_da_buf_done(bp
);
1459 save_info
->forw
= drop_info
->forw
; /* INT_: direct copy */
1460 if (INT_GET(drop_info
->forw
, ARCH_CONVERT
)) {
1461 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1462 INT_GET(drop_info
->forw
, ARCH_CONVERT
), -1, &bp
,
1467 tmp_info
= bp
->data
;
1468 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
)
1469 == INT_GET(save_info
->magic
, ARCH_CONVERT
));
1470 ASSERT(INT_GET(tmp_info
->back
, ARCH_CONVERT
)
1471 == drop_blk
->blkno
);
1472 INT_SET(tmp_info
->back
, ARCH_CONVERT
, save_blk
->blkno
);
1473 xfs_da_log_buf(args
->trans
, bp
, 0,
1474 sizeof(*tmp_info
) - 1);
1475 xfs_da_buf_done(bp
);
1479 xfs_da_log_buf(args
->trans
, save_blk
->bp
, 0, sizeof(*save_info
) - 1);
1484 * Move a path "forward" or "!forward" one block at the current level.
1486 * This routine will adjust a "path" to point to the next block
1487 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1488 * Btree, including updating pointers to the intermediate nodes between
1489 * the new bottom and the root.
1492 xfs_da_path_shift(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
,
1493 int forward
, int release
, int *result
)
1495 xfs_da_state_blk_t
*blk
;
1496 xfs_da_blkinfo_t
*info
;
1497 xfs_da_intnode_t
*node
;
1498 xfs_da_args_t
*args
;
1499 xfs_dablk_t blkno
=0;
1503 * Roll up the Btree looking for the first block where our
1504 * current index is not at the edge of the block. Note that
1505 * we skip the bottom layer because we want the sibling block.
1508 ASSERT(args
!= NULL
);
1509 ASSERT(path
!= NULL
);
1510 ASSERT((path
->active
> 0) && (path
->active
< XFS_DA_NODE_MAXDEPTH
));
1511 level
= (path
->active
-1) - 1; /* skip bottom layer in path */
1512 for (blk
= &path
->blk
[level
]; level
>= 0; blk
--, level
--) {
1513 ASSERT(blk
->bp
!= NULL
);
1514 node
= blk
->bp
->data
;
1515 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1516 if (forward
&& (blk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1)) {
1518 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1520 } else if (!forward
&& (blk
->index
> 0)) {
1522 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1527 *result
= XFS_ERROR(ENOENT
); /* we're out of our tree */
1528 ASSERT(args
->oknoent
);
1533 * Roll down the edge of the subtree until we reach the
1534 * same depth we were at originally.
1536 for (blk
++, level
++; level
< path
->active
; blk
++, level
++) {
1538 * Release the old block.
1539 * (if it's dirty, trans won't actually let go)
1542 xfs_da_brelse(args
->trans
, blk
->bp
);
1545 * Read the next child block.
1548 error
= xfs_da_read_buf(args
->trans
, args
->dp
, blkno
, -1,
1549 &blk
->bp
, args
->whichfork
);
1552 ASSERT(blk
->bp
!= NULL
);
1553 info
= blk
->bp
->data
;
1554 ASSERT(INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
||
1555 INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1556 INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
1557 blk
->magic
= INT_GET(info
->magic
, ARCH_CONVERT
);
1558 if (INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
1559 node
= (xfs_da_intnode_t
*)info
;
1560 blk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1564 blk
->index
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1;
1565 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1567 ASSERT(level
== path
->active
-1);
1569 switch(blk
->magic
) {
1570 case XFS_ATTR_LEAF_MAGIC
:
1571 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
,
1574 case XFS_DIR_LEAF_MAGIC
:
1575 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1576 blk
->hashval
= xfs_dir_leaf_lasthash(blk
->bp
,
1579 case XFS_DIR2_LEAFN_MAGIC
:
1580 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1581 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
,
1585 ASSERT(blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
1587 XFS_DIRX_LEAF_MAGIC(state
->mp
));
1597 /*========================================================================
1599 *========================================================================*/
1602 * Implement a simple hash on a character string.
1603 * Rotate the hash value by 7 bits, then XOR each character in.
1604 * This is implemented with some source-level loop unrolling.
1607 xfs_da_hashname(uchar_t
*name
, int namelen
)
1613 * This is the old one-byte-at-a-time version.
1615 for (hash
= 0; namelen
> 0; namelen
--)
1616 hash
= *name
++ ^ rol32(hash
, 7);
1621 * Do four characters at a time as long as we can.
1623 for (hash
= 0; namelen
>= 4; namelen
-= 4, name
+= 4)
1624 hash
= (name
[0] << 21) ^ (name
[1] << 14) ^ (name
[2] << 7) ^
1625 (name
[3] << 0) ^ rol32(hash
, 7 * 4);
1628 * Now do the rest of the characters.
1632 return (name
[0] << 14) ^ (name
[1] << 7) ^ (name
[2] << 0) ^
1635 return (name
[0] << 7) ^ (name
[1] << 0) ^ rol32(hash
, 7 * 2);
1637 return (name
[0] << 0) ^ rol32(hash
, 7 * 1);
1643 return 0; /* keep gcc happy */
1647 * Add a block to the btree ahead of the file.
1648 * Return the new block number to the caller.
1651 xfs_da_grow_inode(xfs_da_args_t
*args
, xfs_dablk_t
*new_blkno
)
1653 xfs_fileoff_t bno
, b
;
1654 xfs_bmbt_irec_t map
;
1655 xfs_bmbt_irec_t
*mapp
;
1657 int nmap
, error
, w
, count
, c
, got
, i
, mapi
;
1664 w
= args
->whichfork
;
1667 * For new directories adjust the file offset and block count.
1669 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
)) {
1670 bno
= mp
->m_dirleafblk
;
1671 count
= mp
->m_dirblkfsbs
;
1677 * Find a spot in the file space to put the new block.
1679 if ((error
= xfs_bmap_first_unused(tp
, dp
, count
, &bno
, w
))) {
1682 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
1683 ASSERT(bno
>= mp
->m_dirleafblk
&& bno
< mp
->m_dirfreeblk
);
1685 * Try mapping it in one filesystem block.
1688 ASSERT(args
->firstblock
!= NULL
);
1689 if ((error
= xfs_bmapi(tp
, dp
, bno
, count
,
1690 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_WRITE
|XFS_BMAPI_METADATA
|
1692 args
->firstblock
, args
->total
, &map
, &nmap
,
1702 * If we didn't get it and the block might work if fragmented,
1703 * try without the CONTIG flag. Loop until we get it all.
1705 else if (nmap
== 0 && count
> 1) {
1706 mapp
= kmem_alloc(sizeof(*mapp
) * count
, KM_SLEEP
);
1707 for (b
= bno
, mapi
= 0; b
< bno
+ count
; ) {
1708 nmap
= MIN(XFS_BMAP_MAX_NMAP
, count
);
1709 c
= (int)(bno
+ count
- b
);
1710 if ((error
= xfs_bmapi(tp
, dp
, b
, c
,
1711 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_WRITE
|
1713 args
->firstblock
, args
->total
,
1714 &mapp
[mapi
], &nmap
, args
->flist
))) {
1715 kmem_free(mapp
, sizeof(*mapp
) * count
);
1721 b
= mapp
[mapi
- 1].br_startoff
+
1722 mapp
[mapi
- 1].br_blockcount
;
1729 * Count the blocks we got, make sure it matches the total.
1731 for (i
= 0, got
= 0; i
< mapi
; i
++)
1732 got
+= mapp
[i
].br_blockcount
;
1733 if (got
!= count
|| mapp
[0].br_startoff
!= bno
||
1734 mapp
[mapi
- 1].br_startoff
+ mapp
[mapi
- 1].br_blockcount
!=
1737 kmem_free(mapp
, sizeof(*mapp
) * count
);
1738 return XFS_ERROR(ENOSPC
);
1741 kmem_free(mapp
, sizeof(*mapp
) * count
);
1742 *new_blkno
= (xfs_dablk_t
)bno
;
1744 * For version 1 directories, adjust the file size if it changed.
1746 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V1(mp
)) {
1748 if ((error
= xfs_bmap_last_offset(tp
, dp
, &bno
, w
)))
1750 size
= XFS_FSB_TO_B(mp
, bno
);
1751 if (size
!= dp
->i_d
.di_size
) {
1752 dp
->i_d
.di_size
= size
;
1753 xfs_trans_log_inode(tp
, dp
, XFS_ILOG_CORE
);
1760 * Ick. We need to always be able to remove a btree block, even
1761 * if there's no space reservation because the filesystem is full.
1762 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
1763 * It swaps the target block with the last block in the file. The
1764 * last block in the file can always be removed since it can't cause
1765 * a bmap btree split to do that.
1768 xfs_da_swap_lastblock(xfs_da_args_t
*args
, xfs_dablk_t
*dead_blknop
,
1769 xfs_dabuf_t
**dead_bufp
)
1771 xfs_dablk_t dead_blkno
, last_blkno
, sib_blkno
, par_blkno
;
1772 xfs_dabuf_t
*dead_buf
, *last_buf
, *sib_buf
, *par_buf
;
1773 xfs_fileoff_t lastoff
;
1777 int error
, w
, entno
, level
, dead_level
;
1778 xfs_da_blkinfo_t
*dead_info
, *sib_info
;
1779 xfs_da_intnode_t
*par_node
, *dead_node
;
1780 xfs_dir_leafblock_t
*dead_leaf
;
1781 xfs_dir2_leaf_t
*dead_leaf2
;
1782 xfs_dahash_t dead_hash
;
1784 dead_buf
= *dead_bufp
;
1785 dead_blkno
= *dead_blknop
;
1788 w
= args
->whichfork
;
1789 ASSERT(w
== XFS_DATA_FORK
);
1791 if (XFS_DIR_IS_V2(mp
)) {
1792 lastoff
= mp
->m_dirfreeblk
;
1793 error
= xfs_bmap_last_before(tp
, ip
, &lastoff
, w
);
1795 error
= xfs_bmap_last_offset(tp
, ip
, &lastoff
, w
);
1798 if (unlikely(lastoff
== 0)) {
1799 XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW
,
1801 return XFS_ERROR(EFSCORRUPTED
);
1804 * Read the last block in the btree space.
1806 last_blkno
= (xfs_dablk_t
)lastoff
- mp
->m_dirblkfsbs
;
1807 if ((error
= xfs_da_read_buf(tp
, ip
, last_blkno
, -1, &last_buf
, w
)))
1810 * Copy the last block into the dead buffer and log it.
1812 memcpy(dead_buf
->data
, last_buf
->data
, mp
->m_dirblksize
);
1813 xfs_da_log_buf(tp
, dead_buf
, 0, mp
->m_dirblksize
- 1);
1814 dead_info
= dead_buf
->data
;
1816 * Get values from the moved block.
1818 if (INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
) {
1819 ASSERT(XFS_DIR_IS_V1(mp
));
1820 dead_leaf
= (xfs_dir_leafblock_t
*)dead_info
;
1823 INT_GET(dead_leaf
->entries
[INT_GET(dead_leaf
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1824 } else if (INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
) {
1825 ASSERT(XFS_DIR_IS_V2(mp
));
1826 dead_leaf2
= (xfs_dir2_leaf_t
*)dead_info
;
1828 dead_hash
= INT_GET(dead_leaf2
->ents
[INT_GET(dead_leaf2
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1830 ASSERT(INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1831 dead_node
= (xfs_da_intnode_t
*)dead_info
;
1832 dead_level
= INT_GET(dead_node
->hdr
.level
, ARCH_CONVERT
);
1833 dead_hash
= INT_GET(dead_node
->btree
[INT_GET(dead_node
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1835 sib_buf
= par_buf
= NULL
;
1837 * If the moved block has a left sibling, fix up the pointers.
1839 if ((sib_blkno
= INT_GET(dead_info
->back
, ARCH_CONVERT
))) {
1840 if ((error
= xfs_da_read_buf(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
)))
1842 sib_info
= sib_buf
->data
;
1844 INT_GET(sib_info
->forw
, ARCH_CONVERT
) != last_blkno
||
1845 INT_GET(sib_info
->magic
, ARCH_CONVERT
) != INT_GET(dead_info
->magic
, ARCH_CONVERT
))) {
1846 XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
1847 XFS_ERRLEVEL_LOW
, mp
);
1848 error
= XFS_ERROR(EFSCORRUPTED
);
1851 INT_SET(sib_info
->forw
, ARCH_CONVERT
, dead_blkno
);
1852 xfs_da_log_buf(tp
, sib_buf
,
1853 XFS_DA_LOGRANGE(sib_info
, &sib_info
->forw
,
1854 sizeof(sib_info
->forw
)));
1855 xfs_da_buf_done(sib_buf
);
1859 * If the moved block has a right sibling, fix up the pointers.
1861 if ((sib_blkno
= INT_GET(dead_info
->forw
, ARCH_CONVERT
))) {
1862 if ((error
= xfs_da_read_buf(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
)))
1864 sib_info
= sib_buf
->data
;
1866 INT_GET(sib_info
->back
, ARCH_CONVERT
) != last_blkno
1867 || INT_GET(sib_info
->magic
, ARCH_CONVERT
)
1868 != INT_GET(dead_info
->magic
, ARCH_CONVERT
))) {
1869 XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
1870 XFS_ERRLEVEL_LOW
, mp
);
1871 error
= XFS_ERROR(EFSCORRUPTED
);
1874 INT_SET(sib_info
->back
, ARCH_CONVERT
, dead_blkno
);
1875 xfs_da_log_buf(tp
, sib_buf
,
1876 XFS_DA_LOGRANGE(sib_info
, &sib_info
->back
,
1877 sizeof(sib_info
->back
)));
1878 xfs_da_buf_done(sib_buf
);
1881 par_blkno
= XFS_DIR_IS_V1(mp
) ? 0 : mp
->m_dirleafblk
;
1884 * Walk down the tree looking for the parent of the moved block.
1887 if ((error
= xfs_da_read_buf(tp
, ip
, par_blkno
, -1, &par_buf
, w
)))
1889 par_node
= par_buf
->data
;
1891 INT_GET(par_node
->hdr
.info
.magic
, ARCH_CONVERT
) != XFS_DA_NODE_MAGIC
||
1892 (level
>= 0 && level
!= INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
) + 1))) {
1893 XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
1894 XFS_ERRLEVEL_LOW
, mp
);
1895 error
= XFS_ERROR(EFSCORRUPTED
);
1898 level
= INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
);
1900 entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
) &&
1901 INT_GET(par_node
->btree
[entno
].hashval
, ARCH_CONVERT
) < dead_hash
;
1904 if (unlikely(entno
== INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
))) {
1905 XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
1906 XFS_ERRLEVEL_LOW
, mp
);
1907 error
= XFS_ERROR(EFSCORRUPTED
);
1910 par_blkno
= INT_GET(par_node
->btree
[entno
].before
, ARCH_CONVERT
);
1911 if (level
== dead_level
+ 1)
1913 xfs_da_brelse(tp
, par_buf
);
1917 * We're in the right parent block.
1918 * Look for the right entry.
1922 entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
) &&
1923 INT_GET(par_node
->btree
[entno
].before
, ARCH_CONVERT
) != last_blkno
;
1926 if (entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
))
1928 par_blkno
= INT_GET(par_node
->hdr
.info
.forw
, ARCH_CONVERT
);
1929 xfs_da_brelse(tp
, par_buf
);
1931 if (unlikely(par_blkno
== 0)) {
1932 XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
1933 XFS_ERRLEVEL_LOW
, mp
);
1934 error
= XFS_ERROR(EFSCORRUPTED
);
1937 if ((error
= xfs_da_read_buf(tp
, ip
, par_blkno
, -1, &par_buf
, w
)))
1939 par_node
= par_buf
->data
;
1941 INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
) != level
||
1942 INT_GET(par_node
->hdr
.info
.magic
, ARCH_CONVERT
) != XFS_DA_NODE_MAGIC
)) {
1943 XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
1944 XFS_ERRLEVEL_LOW
, mp
);
1945 error
= XFS_ERROR(EFSCORRUPTED
);
1951 * Update the parent entry pointing to the moved block.
1953 INT_SET(par_node
->btree
[entno
].before
, ARCH_CONVERT
, dead_blkno
);
1954 xfs_da_log_buf(tp
, par_buf
,
1955 XFS_DA_LOGRANGE(par_node
, &par_node
->btree
[entno
].before
,
1956 sizeof(par_node
->btree
[entno
].before
)));
1957 xfs_da_buf_done(par_buf
);
1958 xfs_da_buf_done(dead_buf
);
1959 *dead_blknop
= last_blkno
;
1960 *dead_bufp
= last_buf
;
1964 xfs_da_brelse(tp
, par_buf
);
1966 xfs_da_brelse(tp
, sib_buf
);
1967 xfs_da_brelse(tp
, last_buf
);
1972 * Remove a btree block from a directory or attribute.
1975 xfs_da_shrink_inode(xfs_da_args_t
*args
, xfs_dablk_t dead_blkno
,
1976 xfs_dabuf_t
*dead_buf
)
1979 int done
, error
, w
, count
;
1986 w
= args
->whichfork
;
1989 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
1990 count
= mp
->m_dirblkfsbs
;
1995 * Remove extents. If we get ENOSPC for a dir we have to move
1996 * the last block to the place we want to kill.
1998 if ((error
= xfs_bunmapi(tp
, dp
, dead_blkno
, count
,
1999 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_METADATA
,
2000 0, args
->firstblock
, args
->flist
,
2001 &done
)) == ENOSPC
) {
2002 if (w
!= XFS_DATA_FORK
)
2004 if ((error
= xfs_da_swap_lastblock(args
, &dead_blkno
,
2013 xfs_da_binval(tp
, dead_buf
);
2015 * Adjust the directory size for version 1.
2017 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V1(mp
)) {
2018 if ((error
= xfs_bmap_last_offset(tp
, dp
, &bno
, w
)))
2020 size
= XFS_FSB_TO_B(dp
->i_mount
, bno
);
2021 if (size
!= dp
->i_d
.di_size
) {
2022 dp
->i_d
.di_size
= size
;
2023 xfs_trans_log_inode(tp
, dp
, XFS_ILOG_CORE
);
2028 xfs_da_binval(tp
, dead_buf
);
2033 * See if the mapping(s) for this btree block are valid, i.e.
2034 * don't contain holes, are logically contiguous, and cover the whole range.
2037 xfs_da_map_covers_blocks(
2039 xfs_bmbt_irec_t
*mapp
,
2046 for (i
= 0, off
= bno
; i
< nmap
; i
++) {
2047 if (mapp
[i
].br_startblock
== HOLESTARTBLOCK
||
2048 mapp
[i
].br_startblock
== DELAYSTARTBLOCK
) {
2051 if (off
!= mapp
[i
].br_startoff
) {
2054 off
+= mapp
[i
].br_blockcount
;
2056 return off
== bno
+ count
;
2061 * Used for get_buf, read_buf, read_bufr, and reada_buf.
2068 xfs_daddr_t
*mappedbnop
,
2074 xfs_buf_t
*bp
= NULL
;
2078 xfs_bmbt_irec_t map
;
2079 xfs_bmbt_irec_t
*mapp
;
2080 xfs_daddr_t mappedbno
;
2088 if (whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
2089 nfsb
= mp
->m_dirblkfsbs
;
2092 mappedbno
= *mappedbnop
;
2094 * Caller doesn't have a mapping. -2 means don't complain
2095 * if we land in a hole.
2097 if (mappedbno
== -1 || mappedbno
== -2) {
2099 * Optimize the one-block case.
2105 xfs_bmapi_single(trans
, dp
, whichfork
, &fsb
,
2106 (xfs_fileoff_t
)bno
))) {
2110 if (fsb
== NULLFSBLOCK
) {
2113 map
.br_startblock
= fsb
;
2114 map
.br_startoff
= (xfs_fileoff_t
)bno
;
2115 map
.br_blockcount
= 1;
2119 mapp
= kmem_alloc(sizeof(*mapp
) * nfsb
, KM_SLEEP
);
2121 if ((error
= xfs_bmapi(trans
, dp
, (xfs_fileoff_t
)bno
,
2123 XFS_BMAPI_METADATA
|
2124 XFS_BMAPI_AFLAG(whichfork
),
2125 NULL
, 0, mapp
, &nmap
, NULL
)))
2129 map
.br_startblock
= XFS_DADDR_TO_FSB(mp
, mappedbno
);
2130 map
.br_startoff
= (xfs_fileoff_t
)bno
;
2131 map
.br_blockcount
= nfsb
;
2135 if (!xfs_da_map_covers_blocks(nmap
, mapp
, bno
, nfsb
)) {
2136 error
= mappedbno
== -2 ? 0 : XFS_ERROR(EFSCORRUPTED
);
2137 if (unlikely(error
== EFSCORRUPTED
)) {
2138 if (xfs_error_level
>= XFS_ERRLEVEL_LOW
) {
2140 cmn_err(CE_ALERT
, "xfs_da_do_buf: bno %lld\n",
2142 cmn_err(CE_ALERT
, "dir: inode %lld\n",
2143 (long long)dp
->i_ino
);
2144 for (i
= 0; i
< nmap
; i
++) {
2146 "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d\n",
2148 (long long)mapp
[i
].br_startoff
,
2149 (long long)mapp
[i
].br_startblock
,
2150 (long long)mapp
[i
].br_blockcount
,
2154 XFS_ERROR_REPORT("xfs_da_do_buf(1)",
2155 XFS_ERRLEVEL_LOW
, mp
);
2159 if (caller
!= 3 && nmap
> 1) {
2160 bplist
= kmem_alloc(sizeof(*bplist
) * nmap
, KM_SLEEP
);
2165 * Turn the mapping(s) into buffer(s).
2167 for (i
= 0; i
< nmap
; i
++) {
2170 mappedbno
= XFS_FSB_TO_DADDR(mp
, mapp
[i
].br_startblock
);
2172 *mappedbnop
= mappedbno
;
2173 nmapped
= (int)XFS_FSB_TO_BB(mp
, mapp
[i
].br_blockcount
);
2176 bp
= xfs_trans_get_buf(trans
, mp
->m_ddev_targp
,
2177 mappedbno
, nmapped
, 0);
2178 error
= bp
? XFS_BUF_GETERROR(bp
) : XFS_ERROR(EIO
);
2183 error
= xfs_trans_read_buf(mp
, trans
, mp
->m_ddev_targp
,
2184 mappedbno
, nmapped
, 0, &bp
);
2187 xfs_baread(mp
->m_ddev_targp
, mappedbno
, nmapped
);
2194 xfs_trans_brelse(trans
, bp
);
2200 if (whichfork
== XFS_ATTR_FORK
) {
2201 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_ATTR_BTREE
,
2202 XFS_ATTR_BTREE_REF
);
2204 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_DIR_BTREE
,
2209 bplist
[nbplist
++] = bp
;
2213 * Build a dabuf structure.
2216 rbp
= xfs_da_buf_make(nbplist
, bplist
, ra
);
2218 rbp
= xfs_da_buf_make(1, &bp
, ra
);
2222 * For read_buf, check the magic number.
2225 xfs_dir2_data_t
*data
;
2226 xfs_dir2_free_t
*free
;
2227 xfs_da_blkinfo_t
*info
;
2233 magic
= INT_GET(info
->magic
, ARCH_CONVERT
);
2234 magic1
= INT_GET(data
->hdr
.magic
, ARCH_CONVERT
);
2236 XFS_TEST_ERROR((magic
!= XFS_DA_NODE_MAGIC
) &&
2237 (magic
!= XFS_DIR_LEAF_MAGIC
) &&
2238 (magic
!= XFS_ATTR_LEAF_MAGIC
) &&
2239 (magic
!= XFS_DIR2_LEAF1_MAGIC
) &&
2240 (magic
!= XFS_DIR2_LEAFN_MAGIC
) &&
2241 (magic1
!= XFS_DIR2_BLOCK_MAGIC
) &&
2242 (magic1
!= XFS_DIR2_DATA_MAGIC
) &&
2243 (INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) != XFS_DIR2_FREE_MAGIC
),
2244 mp
, XFS_ERRTAG_DA_READ_BUF
,
2245 XFS_RANDOM_DA_READ_BUF
))) {
2246 xfs_buftrace("DA READ ERROR", rbp
->bps
[0]);
2247 XFS_CORRUPTION_ERROR("xfs_da_do_buf(2)",
2248 XFS_ERRLEVEL_LOW
, mp
, info
);
2249 error
= XFS_ERROR(EFSCORRUPTED
);
2250 xfs_da_brelse(trans
, rbp
);
2256 kmem_free(bplist
, sizeof(*bplist
) * nmap
);
2259 kmem_free(mapp
, sizeof(*mapp
) * nfsb
);
2266 for (i
= 0; i
< nbplist
; i
++)
2267 xfs_trans_brelse(trans
, bplist
[i
]);
2268 kmem_free(bplist
, sizeof(*bplist
) * nmap
);
2272 kmem_free(mapp
, sizeof(*mapp
) * nfsb
);
2279 * Get a buffer for the dir/attr block.
2286 xfs_daddr_t mappedbno
,
2290 return xfs_da_do_buf(trans
, dp
, bno
, &mappedbno
, bpp
, whichfork
, 0,
2291 (inst_t
*)__return_address
);
2295 * Get a buffer for the dir/attr block, fill in the contents.
2302 xfs_daddr_t mappedbno
,
2306 return xfs_da_do_buf(trans
, dp
, bno
, &mappedbno
, bpp
, whichfork
, 1,
2307 (inst_t
*)__return_address
);
2311 * Readahead the dir/attr block.
2323 if (xfs_da_do_buf(trans
, dp
, bno
, &rval
, NULL
, whichfork
, 3,
2324 (inst_t
*)__return_address
))
2331 * Calculate the number of bits needed to hold i different values.
2334 xfs_da_log2_roundup(uint i
)
2338 for (rval
= 0; rval
< NBBY
* sizeof(i
); rval
++) {
2339 if ((1 << rval
) >= i
)
2345 kmem_zone_t
*xfs_da_state_zone
; /* anchor for state struct zone */
2346 kmem_zone_t
*xfs_dabuf_zone
; /* dabuf zone */
2349 * Allocate a dir-state structure.
2350 * We don't put them on the stack since they're large.
2353 xfs_da_state_alloc(void)
2355 return kmem_zone_zalloc(xfs_da_state_zone
, KM_SLEEP
);
2359 * Kill the altpath contents of a da-state structure.
2362 xfs_da_state_kill_altpath(xfs_da_state_t
*state
)
2366 for (i
= 0; i
< state
->altpath
.active
; i
++) {
2367 if (state
->altpath
.blk
[i
].bp
) {
2368 if (state
->altpath
.blk
[i
].bp
!= state
->path
.blk
[i
].bp
)
2369 xfs_da_buf_done(state
->altpath
.blk
[i
].bp
);
2370 state
->altpath
.blk
[i
].bp
= NULL
;
2373 state
->altpath
.active
= 0;
2377 * Free a da-state structure.
2380 xfs_da_state_free(xfs_da_state_t
*state
)
2384 xfs_da_state_kill_altpath(state
);
2385 for (i
= 0; i
< state
->path
.active
; i
++) {
2386 if (state
->path
.blk
[i
].bp
)
2387 xfs_da_buf_done(state
->path
.blk
[i
].bp
);
2389 if (state
->extravalid
&& state
->extrablk
.bp
)
2390 xfs_da_buf_done(state
->extrablk
.bp
);
2392 memset((char *)state
, 0, sizeof(*state
));
2394 kmem_zone_free(xfs_da_state_zone
, state
);
2397 #ifdef XFS_DABUF_DEBUG
2398 xfs_dabuf_t
*xfs_dabuf_global_list
;
2399 lock_t xfs_dabuf_global_lock
;
2406 STATIC xfs_dabuf_t
*
2407 xfs_da_buf_make(int nbuf
, xfs_buf_t
**bps
, inst_t
*ra
)
2415 dabuf
= kmem_zone_alloc(xfs_dabuf_zone
, KM_SLEEP
);
2417 dabuf
= kmem_alloc(XFS_DA_BUF_SIZE(nbuf
), KM_SLEEP
);
2419 #ifdef XFS_DABUF_DEBUG
2421 dabuf
->target
= XFS_BUF_TARGET(bps
[0]);
2422 dabuf
->blkno
= XFS_BUF_ADDR(bps
[0]);
2427 dabuf
->bbcount
= (short)BTOBB(XFS_BUF_COUNT(bp
));
2428 dabuf
->data
= XFS_BUF_PTR(bp
);
2432 for (i
= 0, dabuf
->bbcount
= 0; i
< nbuf
; i
++) {
2433 dabuf
->bps
[i
] = bp
= bps
[i
];
2434 dabuf
->bbcount
+= BTOBB(XFS_BUF_COUNT(bp
));
2436 dabuf
->data
= kmem_alloc(BBTOB(dabuf
->bbcount
), KM_SLEEP
);
2437 for (i
= off
= 0; i
< nbuf
; i
++, off
+= XFS_BUF_COUNT(bp
)) {
2439 memcpy((char *)dabuf
->data
+ off
, XFS_BUF_PTR(bp
),
2443 #ifdef XFS_DABUF_DEBUG
2448 s
= mutex_spinlock(&xfs_dabuf_global_lock
);
2449 for (p
= xfs_dabuf_global_list
; p
; p
= p
->next
) {
2450 ASSERT(p
->blkno
!= dabuf
->blkno
||
2451 p
->target
!= dabuf
->target
);
2454 if (xfs_dabuf_global_list
)
2455 xfs_dabuf_global_list
->prev
= dabuf
;
2456 dabuf
->next
= xfs_dabuf_global_list
;
2457 xfs_dabuf_global_list
= dabuf
;
2458 mutex_spinunlock(&xfs_dabuf_global_lock
, s
);
2468 xfs_da_buf_clean(xfs_dabuf_t
*dabuf
)
2475 ASSERT(dabuf
->nbuf
> 1);
2477 for (i
= off
= 0; i
< dabuf
->nbuf
;
2478 i
++, off
+= XFS_BUF_COUNT(bp
)) {
2480 memcpy(XFS_BUF_PTR(bp
), (char *)dabuf
->data
+ off
,
2490 xfs_da_buf_done(xfs_dabuf_t
*dabuf
)
2493 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2495 xfs_da_buf_clean(dabuf
);
2496 if (dabuf
->nbuf
> 1)
2497 kmem_free(dabuf
->data
, BBTOB(dabuf
->bbcount
));
2498 #ifdef XFS_DABUF_DEBUG
2502 s
= mutex_spinlock(&xfs_dabuf_global_lock
);
2504 dabuf
->prev
->next
= dabuf
->next
;
2506 xfs_dabuf_global_list
= dabuf
->next
;
2508 dabuf
->next
->prev
= dabuf
->prev
;
2509 mutex_spinunlock(&xfs_dabuf_global_lock
, s
);
2511 memset(dabuf
, 0, XFS_DA_BUF_SIZE(dabuf
->nbuf
));
2513 if (dabuf
->nbuf
== 1)
2514 kmem_zone_free(xfs_dabuf_zone
, dabuf
);
2516 kmem_free(dabuf
, XFS_DA_BUF_SIZE(dabuf
->nbuf
));
2520 * Log transaction from a dabuf.
2523 xfs_da_log_buf(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
, uint first
, uint last
)
2531 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2532 if (dabuf
->nbuf
== 1) {
2533 ASSERT(dabuf
->data
== (void *)XFS_BUF_PTR(dabuf
->bps
[0]));
2534 xfs_trans_log_buf(tp
, dabuf
->bps
[0], first
, last
);
2538 ASSERT(first
<= last
);
2539 for (i
= off
= 0; i
< dabuf
->nbuf
; i
++, off
+= XFS_BUF_COUNT(bp
)) {
2542 l
= f
+ XFS_BUF_COUNT(bp
) - 1;
2548 xfs_trans_log_buf(tp
, bp
, f
- off
, l
- off
);
2550 * B_DONE is set by xfs_trans_log buf.
2551 * If we don't set it on a new buffer (get not read)
2552 * then if we don't put anything in the buffer it won't
2553 * be set, and at commit it it released into the cache,
2554 * and then a read will fail.
2556 else if (!(XFS_BUF_ISDONE(bp
)))
2563 * Release dabuf from a transaction.
2564 * Have to free up the dabuf before the buffers are released,
2565 * since the synchronization on the dabuf is really the lock on the buffer.
2568 xfs_da_brelse(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
)
2575 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2576 if ((nbuf
= dabuf
->nbuf
) == 1) {
2580 bplist
= kmem_alloc(nbuf
* sizeof(*bplist
), KM_SLEEP
);
2581 memcpy(bplist
, dabuf
->bps
, nbuf
* sizeof(*bplist
));
2583 xfs_da_buf_done(dabuf
);
2584 for (i
= 0; i
< nbuf
; i
++)
2585 xfs_trans_brelse(tp
, bplist
[i
]);
2587 kmem_free(bplist
, nbuf
* sizeof(*bplist
));
2591 * Invalidate dabuf from a transaction.
2594 xfs_da_binval(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
)
2601 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2602 if ((nbuf
= dabuf
->nbuf
) == 1) {
2606 bplist
= kmem_alloc(nbuf
* sizeof(*bplist
), KM_SLEEP
);
2607 memcpy(bplist
, dabuf
->bps
, nbuf
* sizeof(*bplist
));
2609 xfs_da_buf_done(dabuf
);
2610 for (i
= 0; i
< nbuf
; i
++)
2611 xfs_trans_binval(tp
, bplist
[i
]);
2613 kmem_free(bplist
, nbuf
* sizeof(*bplist
));
2617 * Get the first daddr from a dabuf.
2620 xfs_da_blkno(xfs_dabuf_t
*dabuf
)
2622 ASSERT(dabuf
->nbuf
);
2623 ASSERT(dabuf
->data
);
2624 return XFS_BUF_ADDR(dabuf
->bps
[0]);