2 * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
38 * Routines to implement directories as Btrees of hashed names.
42 /*========================================================================
43 * Routines used for growing the Btree.
44 *========================================================================*/
47 * Create the initial contents of an intermediate node.
50 xfs_da_node_create(xfs_da_args_t
*args
, xfs_dablk_t blkno
, int level
,
51 xfs_dabuf_t
**bpp
, int whichfork
)
53 xfs_da_intnode_t
*node
;
59 error
= xfs_da_get_buf(tp
, args
->dp
, blkno
, -1, &bp
, whichfork
);
64 INT_ZERO(node
->hdr
.info
.forw
, ARCH_CONVERT
);
65 INT_ZERO(node
->hdr
.info
.back
, ARCH_CONVERT
);
66 INT_SET(node
->hdr
.info
.magic
, ARCH_CONVERT
, XFS_DA_NODE_MAGIC
);
67 INT_ZERO(node
->hdr
.info
.pad
, ARCH_CONVERT
);
68 INT_ZERO(node
->hdr
.count
, ARCH_CONVERT
);
69 INT_SET(node
->hdr
.level
, ARCH_CONVERT
, level
);
71 xfs_da_log_buf(tp
, bp
,
72 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
79 * Split a leaf node, rebalance, then possibly split
80 * intermediate nodes, rebalance, etc.
83 xfs_da_split(xfs_da_state_t
*state
)
85 xfs_da_state_blk_t
*oldblk
, *newblk
, *addblk
;
86 xfs_da_intnode_t
*node
;
88 int max
, action
, error
, i
;
91 * Walk back up the tree splitting/inserting/adjusting as necessary.
92 * If we need to insert and there isn't room, split the node, then
93 * decide which fragment to insert the new block from below into.
94 * Note that we may split the root this way, but we need more fixup.
96 max
= state
->path
.active
- 1;
97 ASSERT((max
>= 0) && (max
< XFS_DA_NODE_MAXDEPTH
));
98 ASSERT(state
->path
.blk
[max
].magic
== XFS_ATTR_LEAF_MAGIC
||
99 state
->path
.blk
[max
].magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
));
101 addblk
= &state
->path
.blk
[max
]; /* initial dummy value */
102 for (i
= max
; (i
>= 0) && addblk
; state
->path
.active
--, i
--) {
103 oldblk
= &state
->path
.blk
[i
];
104 newblk
= &state
->altpath
.blk
[i
];
107 * If a leaf node then
108 * Allocate a new leaf node, then rebalance across them.
109 * else if an intermediate node then
110 * We split on the last layer, must we split the node?
112 switch (oldblk
->magic
) {
113 case XFS_ATTR_LEAF_MAGIC
:
117 error
= xfs_attr_leaf_split(state
, oldblk
, newblk
);
118 if ((error
!= 0) && (error
!= ENOSPC
)) {
119 return(error
); /* GROT: attr is inconsistent */
126 * Entry wouldn't fit, split the leaf again.
128 state
->extravalid
= 1;
130 state
->extraafter
= 0; /* before newblk */
131 error
= xfs_attr_leaf_split(state
, oldblk
,
134 state
->extraafter
= 1; /* after newblk */
135 error
= xfs_attr_leaf_split(state
, newblk
,
139 return(error
); /* GROT: attr inconsistent */
143 case XFS_DIR_LEAF_MAGIC
:
144 ASSERT(XFS_DIR_IS_V1(state
->mp
));
145 error
= xfs_dir_leaf_split(state
, oldblk
, newblk
);
146 if ((error
!= 0) && (error
!= ENOSPC
)) {
147 return(error
); /* GROT: dir is inconsistent */
154 * Entry wouldn't fit, split the leaf again.
156 state
->extravalid
= 1;
158 state
->extraafter
= 0; /* before newblk */
159 error
= xfs_dir_leaf_split(state
, oldblk
,
162 return(error
); /* GROT: dir incon. */
165 state
->extraafter
= 1; /* after newblk */
166 error
= xfs_dir_leaf_split(state
, newblk
,
169 return(error
); /* GROT: dir incon. */
173 case XFS_DIR2_LEAFN_MAGIC
:
174 ASSERT(XFS_DIR_IS_V2(state
->mp
));
175 error
= xfs_dir2_leafn_split(state
, oldblk
, newblk
);
180 case XFS_DA_NODE_MAGIC
:
181 error
= xfs_da_node_split(state
, oldblk
, newblk
, addblk
,
183 xfs_da_buf_done(addblk
->bp
);
186 return(error
); /* GROT: dir is inconsistent */
188 * Record the newly split block for the next time thru?
198 * Update the btree to show the new hashval for this child.
200 xfs_da_fixhashpath(state
, &state
->path
);
202 * If we won't need this block again, it's getting dropped
203 * from the active path by the loop control, so we need
204 * to mark it done now.
206 if (i
> 0 || !addblk
)
207 xfs_da_buf_done(oldblk
->bp
);
213 * Split the root node.
215 ASSERT(state
->path
.active
== 0);
216 oldblk
= &state
->path
.blk
[0];
217 error
= xfs_da_root_split(state
, oldblk
, addblk
);
219 xfs_da_buf_done(oldblk
->bp
);
220 xfs_da_buf_done(addblk
->bp
);
222 return(error
); /* GROT: dir is inconsistent */
226 * Update pointers to the node which used to be block 0 and
227 * just got bumped because of the addition of a new root node.
228 * There might be three blocks involved if a double split occurred,
229 * and the original block 0 could be at any position in the list.
232 node
= oldblk
->bp
->data
;
233 if (!INT_ISZERO(node
->hdr
.info
.forw
, ARCH_CONVERT
)) {
234 if (INT_GET(node
->hdr
.info
.forw
, ARCH_CONVERT
) == addblk
->blkno
) {
237 ASSERT(state
->extravalid
);
238 bp
= state
->extrablk
.bp
;
241 INT_SET(node
->hdr
.info
.back
, ARCH_CONVERT
, oldblk
->blkno
);
242 xfs_da_log_buf(state
->args
->trans
, bp
,
243 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
244 sizeof(node
->hdr
.info
)));
246 node
= oldblk
->bp
->data
;
247 if (INT_GET(node
->hdr
.info
.back
, ARCH_CONVERT
)) {
248 if (INT_GET(node
->hdr
.info
.back
, ARCH_CONVERT
) == addblk
->blkno
) {
251 ASSERT(state
->extravalid
);
252 bp
= state
->extrablk
.bp
;
255 INT_SET(node
->hdr
.info
.forw
, ARCH_CONVERT
, oldblk
->blkno
);
256 xfs_da_log_buf(state
->args
->trans
, bp
,
257 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
258 sizeof(node
->hdr
.info
)));
260 xfs_da_buf_done(oldblk
->bp
);
261 xfs_da_buf_done(addblk
->bp
);
267 * Split the root. We have to create a new root and point to the two
268 * parts (the split old root) that we just created. Copy block zero to
269 * the EOF, extending the inode in process.
271 STATIC
int /* error */
272 xfs_da_root_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
273 xfs_da_state_blk_t
*blk2
)
275 xfs_da_intnode_t
*node
, *oldroot
;
283 xfs_dir2_leaf_t
*leaf
;
286 * Copy the existing (incorrect) block from the root node position
287 * to a free space somewhere.
290 ASSERT(args
!= NULL
);
291 error
= xfs_da_grow_inode(args
, &blkno
);
297 error
= xfs_da_get_buf(tp
, dp
, blkno
, -1, &bp
, args
->whichfork
);
302 oldroot
= blk1
->bp
->data
;
303 if (INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
304 size
= (int)((char *)&oldroot
->btree
[INT_GET(oldroot
->hdr
.count
, ARCH_CONVERT
)] -
307 ASSERT(XFS_DIR_IS_V2(mp
));
308 ASSERT(INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
);
309 leaf
= (xfs_dir2_leaf_t
*)oldroot
;
310 size
= (int)((char *)&leaf
->ents
[INT_GET(leaf
->hdr
.count
, ARCH_CONVERT
)] -
313 bcopy(oldroot
, node
, size
);
314 xfs_da_log_buf(tp
, bp
, 0, size
- 1);
315 xfs_da_buf_done(blk1
->bp
);
320 * Set up the new root node.
322 error
= xfs_da_node_create(args
,
323 args
->whichfork
== XFS_DATA_FORK
&&
324 XFS_DIR_IS_V2(mp
) ? mp
->m_dirleafblk
: 0,
325 INT_GET(node
->hdr
.level
, ARCH_CONVERT
) + 1, &bp
, args
->whichfork
);
329 INT_SET(node
->btree
[0].hashval
, ARCH_CONVERT
, blk1
->hashval
);
330 INT_SET(node
->btree
[0].before
, ARCH_CONVERT
, blk1
->blkno
);
331 INT_SET(node
->btree
[1].hashval
, ARCH_CONVERT
, blk2
->hashval
);
332 INT_SET(node
->btree
[1].before
, ARCH_CONVERT
, blk2
->blkno
);
333 INT_SET(node
->hdr
.count
, ARCH_CONVERT
, 2);
334 if (XFS_DIR_IS_V2(mp
)) {
335 ASSERT(blk1
->blkno
>= mp
->m_dirleafblk
&&
336 blk1
->blkno
< mp
->m_dirfreeblk
);
337 ASSERT(blk2
->blkno
>= mp
->m_dirleafblk
&&
338 blk2
->blkno
< mp
->m_dirfreeblk
);
340 /* Header is already logged by xfs_da_node_create */
341 xfs_da_log_buf(tp
, bp
,
342 XFS_DA_LOGRANGE(node
, node
->btree
,
343 sizeof(xfs_da_node_entry_t
) * 2));
350 * Split the node, rebalance, then add the new entry.
352 STATIC
int /* error */
353 xfs_da_node_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
354 xfs_da_state_blk_t
*newblk
,
355 xfs_da_state_blk_t
*addblk
,
356 int treelevel
, int *result
)
358 xfs_da_intnode_t
*node
;
363 node
= oldblk
->bp
->data
;
364 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
367 * With V2 the extra block is data or freespace.
369 useextra
= state
->extravalid
&& XFS_DIR_IS_V1(state
->mp
);
370 newcount
= 1 + useextra
;
372 * Do we have to split the node?
374 if ((INT_GET(node
->hdr
.count
, ARCH_CONVERT
) + newcount
) > XFS_DA_NODE_ENTRIES(state
->mp
)) {
376 * Allocate a new node, add to the doubly linked chain of
377 * nodes, then move some of our excess entries into it.
379 error
= xfs_da_grow_inode(state
->args
, &blkno
);
381 return(error
); /* GROT: dir is inconsistent */
383 error
= xfs_da_node_create(state
->args
, blkno
, treelevel
,
384 &newblk
->bp
, state
->args
->whichfork
);
386 return(error
); /* GROT: dir is inconsistent */
387 newblk
->blkno
= blkno
;
388 newblk
->magic
= XFS_DA_NODE_MAGIC
;
389 xfs_da_node_rebalance(state
, oldblk
, newblk
);
390 error
= xfs_da_blk_link(state
, oldblk
, newblk
);
399 * Insert the new entry(s) into the correct block
400 * (updating last hashval in the process).
402 * xfs_da_node_add() inserts BEFORE the given index,
403 * and as a result of using node_lookup_int() we always
404 * point to a valid entry (not after one), but a split
405 * operation always results in a new block whose hashvals
406 * FOLLOW the current block.
408 * If we had double-split op below us, then add the extra block too.
410 node
= oldblk
->bp
->data
;
411 if (oldblk
->index
<= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)) {
413 xfs_da_node_add(state
, oldblk
, addblk
);
415 if (state
->extraafter
)
417 xfs_da_node_add(state
, oldblk
, &state
->extrablk
);
418 state
->extravalid
= 0;
422 xfs_da_node_add(state
, newblk
, addblk
);
424 if (state
->extraafter
)
426 xfs_da_node_add(state
, newblk
, &state
->extrablk
);
427 state
->extravalid
= 0;
435 * Balance the btree elements between two intermediate nodes,
436 * usually one full and one empty.
438 * NOTE: if blk2 is empty, then it will get the upper half of blk1.
441 xfs_da_node_rebalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
442 xfs_da_state_blk_t
*blk2
)
444 xfs_da_intnode_t
*node1
, *node2
, *tmpnode
;
445 xfs_da_node_entry_t
*btree_s
, *btree_d
;
449 node1
= blk1
->bp
->data
;
450 node2
= blk2
->bp
->data
;
452 * Figure out how many entries need to move, and in which direction.
453 * Swap the nodes around if that makes it simpler.
455 if ((INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) > 0) && (INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) > 0) &&
456 ((INT_GET(node2
->btree
[ 0 ].hashval
, ARCH_CONVERT
) < INT_GET(node1
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
457 (INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
458 INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))) {
463 ASSERT(INT_GET(node1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
464 ASSERT(INT_GET(node2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
465 count
= (INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) - INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)) / 2;
468 tp
= state
->args
->trans
;
470 * Two cases: high-to-low and low-to-high.
474 * Move elements in node2 up to make a hole.
476 if ((tmp
= INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)) > 0) {
477 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
478 btree_s
= &node2
->btree
[0];
479 btree_d
= &node2
->btree
[count
];
480 ovbcopy(btree_s
, btree_d
, tmp
);
484 * Move the req'd B-tree elements from high in node1 to
487 INT_MOD(node2
->hdr
.count
, ARCH_CONVERT
, count
);
488 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
489 btree_s
= &node1
->btree
[INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) - count
];
490 btree_d
= &node2
->btree
[0];
491 bcopy(btree_s
, btree_d
, tmp
);
492 INT_MOD(node1
->hdr
.count
, ARCH_CONVERT
, -(count
));
496 * Move the req'd B-tree elements from low in node2 to
500 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
501 btree_s
= &node2
->btree
[0];
502 btree_d
= &node1
->btree
[INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)];
503 bcopy(btree_s
, btree_d
, tmp
);
504 INT_MOD(node1
->hdr
.count
, ARCH_CONVERT
, count
);
505 xfs_da_log_buf(tp
, blk1
->bp
,
506 XFS_DA_LOGRANGE(node1
, btree_d
, tmp
));
509 * Move elements in node2 down to fill the hole.
511 tmp
= INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) - count
;
512 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
513 btree_s
= &node2
->btree
[count
];
514 btree_d
= &node2
->btree
[0];
515 ovbcopy(btree_s
, btree_d
, tmp
);
516 INT_MOD(node2
->hdr
.count
, ARCH_CONVERT
, -(count
));
520 * Log header of node 1 and all current bits of node 2.
522 xfs_da_log_buf(tp
, blk1
->bp
,
523 XFS_DA_LOGRANGE(node1
, &node1
->hdr
, sizeof(node1
->hdr
)));
524 xfs_da_log_buf(tp
, blk2
->bp
,
525 XFS_DA_LOGRANGE(node2
, &node2
->hdr
,
527 sizeof(node2
->btree
[0]) * INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)));
530 * Record the last hashval from each block for upward propagation.
531 * (note: don't use the swapped node pointers)
533 node1
= blk1
->bp
->data
;
534 node2
= blk2
->bp
->data
;
535 blk1
->hashval
= INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
536 blk2
->hashval
= INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
539 * Adjust the expected index for insertion.
541 if (blk1
->index
>= INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)) {
542 blk2
->index
= blk1
->index
- INT_GET(node1
->hdr
.count
, ARCH_CONVERT
);
543 blk1
->index
= INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) + 1; /* make it invalid */
548 * Add a new entry to an intermediate node.
551 xfs_da_node_add(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
552 xfs_da_state_blk_t
*newblk
)
554 xfs_da_intnode_t
*node
;
555 xfs_da_node_entry_t
*btree
;
559 node
= oldblk
->bp
->data
;
561 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
562 ASSERT((oldblk
->index
>= 0) && (oldblk
->index
<= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)));
563 ASSERT(newblk
->blkno
!= 0);
564 if (state
->args
->whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
565 ASSERT(newblk
->blkno
>= mp
->m_dirleafblk
&&
566 newblk
->blkno
< mp
->m_dirfreeblk
);
569 * We may need to make some room before we insert the new node.
572 btree
= &node
->btree
[ oldblk
->index
];
573 if (oldblk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
)) {
574 tmp
= (INT_GET(node
->hdr
.count
, ARCH_CONVERT
) - oldblk
->index
) * (uint
)sizeof(*btree
);
575 ovbcopy(btree
, btree
+ 1, tmp
);
577 INT_SET(btree
->hashval
, ARCH_CONVERT
, newblk
->hashval
);
578 INT_SET(btree
->before
, ARCH_CONVERT
, newblk
->blkno
);
579 xfs_da_log_buf(state
->args
->trans
, oldblk
->bp
,
580 XFS_DA_LOGRANGE(node
, btree
, tmp
+ sizeof(*btree
)));
581 INT_MOD(node
->hdr
.count
, ARCH_CONVERT
, +1);
582 xfs_da_log_buf(state
->args
->trans
, oldblk
->bp
,
583 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
586 * Copy the last hash value from the oldblk to propagate upwards.
588 oldblk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
591 /*========================================================================
592 * Routines used for shrinking the Btree.
593 *========================================================================*/
596 * Deallocate an empty leaf node, remove it from its parent,
597 * possibly deallocating that block, etc...
600 xfs_da_join(xfs_da_state_t
*state
)
602 xfs_da_state_blk_t
*drop_blk
, *save_blk
;
606 drop_blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
607 save_blk
= &state
->altpath
.blk
[ state
->path
.active
-1 ];
608 ASSERT(state
->path
.blk
[0].magic
== XFS_DA_NODE_MAGIC
);
609 ASSERT(drop_blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
610 drop_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
));
613 * Walk back up the tree joining/deallocating as necessary.
614 * When we stop dropping blocks, break out.
616 for ( ; state
->path
.active
>= 2; drop_blk
--, save_blk
--,
617 state
->path
.active
--) {
619 * See if we can combine the block with a neighbor.
620 * (action == 0) => no options, just leave
621 * (action == 1) => coalesce, then unlink
622 * (action == 2) => block empty, unlink it
624 switch (drop_blk
->magic
) {
625 case XFS_ATTR_LEAF_MAGIC
:
629 error
= xfs_attr_leaf_toosmall(state
, &action
);
636 xfs_attr_leaf_unbalance(state
, drop_blk
, save_blk
);
639 case XFS_DIR_LEAF_MAGIC
:
640 ASSERT(XFS_DIR_IS_V1(state
->mp
));
641 error
= xfs_dir_leaf_toosmall(state
, &action
);
646 xfs_dir_leaf_unbalance(state
, drop_blk
, save_blk
);
648 case XFS_DIR2_LEAFN_MAGIC
:
649 ASSERT(XFS_DIR_IS_V2(state
->mp
));
650 error
= xfs_dir2_leafn_toosmall(state
, &action
);
655 xfs_dir2_leafn_unbalance(state
, drop_blk
, save_blk
);
657 case XFS_DA_NODE_MAGIC
:
659 * Remove the offending node, fixup hashvals,
660 * check for a toosmall neighbor.
662 xfs_da_node_remove(state
, drop_blk
);
663 xfs_da_fixhashpath(state
, &state
->path
);
664 error
= xfs_da_node_toosmall(state
, &action
);
669 xfs_da_node_unbalance(state
, drop_blk
, save_blk
);
672 xfs_da_fixhashpath(state
, &state
->altpath
);
673 error
= xfs_da_blk_unlink(state
, drop_blk
, save_blk
);
674 xfs_da_state_kill_altpath(state
);
677 error
= xfs_da_shrink_inode(state
->args
, drop_blk
->blkno
,
684 * We joined all the way to the top. If it turns out that
685 * we only have one entry in the root, make the child block
688 xfs_da_node_remove(state
, drop_blk
);
689 xfs_da_fixhashpath(state
, &state
->path
);
690 error
= xfs_da_root_join(state
, &state
->path
.blk
[0]);
695 * We have only one entry in the root. Copy the only remaining child of
696 * the old root to block 0 as the new root node.
699 xfs_da_root_join(xfs_da_state_t
*state
, xfs_da_state_blk_t
*root_blk
)
701 xfs_da_intnode_t
*oldroot
;
703 xfs_da_blkinfo_t
*blkinfo
;
710 ASSERT(args
!= NULL
);
711 ASSERT(root_blk
->magic
== XFS_DA_NODE_MAGIC
);
712 oldroot
= root_blk
->bp
->data
;
713 ASSERT(INT_GET(oldroot
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
714 ASSERT(INT_ISZERO(oldroot
->hdr
.info
.forw
, ARCH_CONVERT
));
715 ASSERT(INT_ISZERO(oldroot
->hdr
.info
.back
, ARCH_CONVERT
));
718 * If the root has more than one child, then don't do anything.
720 if (INT_GET(oldroot
->hdr
.count
, ARCH_CONVERT
) > 1)
724 * Read in the (only) child block, then copy those bytes into
725 * the root block's buffer and free the original child block.
727 child
= INT_GET(oldroot
->btree
[ 0 ].before
, ARCH_CONVERT
);
729 error
= xfs_da_read_buf(args
->trans
, args
->dp
, child
, -1, &bp
,
735 if (INT_GET(oldroot
->hdr
.level
, ARCH_CONVERT
) == 1) {
736 ASSERT(INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
737 INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
739 ASSERT(INT_GET(blkinfo
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
741 ASSERT(INT_ISZERO(blkinfo
->forw
, ARCH_CONVERT
));
742 ASSERT(INT_ISZERO(blkinfo
->back
, ARCH_CONVERT
));
743 bcopy(bp
->data
, root_blk
->bp
->data
, state
->blocksize
);
744 xfs_da_log_buf(args
->trans
, root_blk
->bp
, 0, state
->blocksize
- 1);
745 error
= xfs_da_shrink_inode(args
, child
, bp
);
750 * Check a node block and its neighbors to see if the block should be
751 * collapsed into one or the other neighbor. Always keep the block
752 * with the smaller block number.
753 * If the current block is over 50% full, don't try to join it, return 0.
754 * If the block is empty, fill in the state structure and return 2.
755 * If it can be collapsed, fill in the state structure and return 1.
756 * If nothing can be done, return 0.
759 xfs_da_node_toosmall(xfs_da_state_t
*state
, int *action
)
761 xfs_da_intnode_t
*node
;
762 xfs_da_state_blk_t
*blk
;
763 xfs_da_blkinfo_t
*info
;
764 int count
, forward
, error
, retval
, i
;
769 * Check for the degenerate case of the block being over 50% full.
770 * If so, it's not worth even looking to see if we might be able
771 * to coalesce with a sibling.
773 blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
774 info
= blk
->bp
->data
;
775 ASSERT(INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
776 node
= (xfs_da_intnode_t
*)info
;
777 count
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
778 if (count
> (XFS_DA_NODE_ENTRIES(state
->mp
) >> 1)) {
779 *action
= 0; /* blk over 50%, dont try to join */
780 return(0); /* blk over 50%, dont try to join */
784 * Check for the degenerate case of the block being empty.
785 * If the block is empty, we'll simply delete it, no need to
786 * coalesce it with a sibling block. We choose (aribtrarily)
787 * to merge with the forward block unless it is NULL.
791 * Make altpath point to the block we want to keep and
792 * path point to the block we want to drop (this one).
794 forward
= (!INT_ISZERO(info
->forw
, ARCH_CONVERT
));
795 bcopy(&state
->path
, &state
->altpath
, sizeof(state
->path
));
796 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
809 * Examine each sibling block to see if we can coalesce with
810 * at least 25% free space to spare. We need to figure out
811 * whether to merge with the forward or the backward block.
812 * We prefer coalescing with the lower numbered sibling so as
813 * to shrink a directory over time.
815 /* start with smaller blk num */
816 forward
= (INT_GET(info
->forw
, ARCH_CONVERT
)
817 < INT_GET(info
->back
, ARCH_CONVERT
));
818 for (i
= 0; i
< 2; forward
= !forward
, i
++) {
820 blkno
= INT_GET(info
->forw
, ARCH_CONVERT
);
822 blkno
= INT_GET(info
->back
, ARCH_CONVERT
);
825 error
= xfs_da_read_buf(state
->args
->trans
, state
->args
->dp
,
826 blkno
, -1, &bp
, state
->args
->whichfork
);
831 node
= (xfs_da_intnode_t
*)info
;
832 count
= XFS_DA_NODE_ENTRIES(state
->mp
);
833 count
-= XFS_DA_NODE_ENTRIES(state
->mp
) >> 2;
834 count
-= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
836 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
837 count
-= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
838 xfs_da_brelse(state
->args
->trans
, bp
);
840 break; /* fits with at least 25% to spare */
848 * Make altpath point to the block we want to keep (the lower
849 * numbered block) and path point to the block we want to drop.
851 bcopy(&state
->path
, &state
->altpath
, sizeof(state
->path
));
852 if (blkno
< blk
->blkno
) {
853 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
863 error
= xfs_da_path_shift(state
, &state
->path
, forward
,
879 * Walk back up the tree adjusting hash values as necessary,
880 * when we stop making changes, return.
883 xfs_da_fixhashpath(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
)
885 xfs_da_state_blk_t
*blk
;
886 xfs_da_intnode_t
*node
;
887 xfs_da_node_entry_t
*btree
;
888 xfs_dahash_t lasthash
=0;
891 level
= path
->active
-1;
892 blk
= &path
->blk
[ level
];
893 switch (blk
->magic
) {
895 case XFS_ATTR_LEAF_MAGIC
:
896 lasthash
= xfs_attr_leaf_lasthash(blk
->bp
, &count
);
901 case XFS_DIR_LEAF_MAGIC
:
902 ASSERT(XFS_DIR_IS_V1(state
->mp
));
903 lasthash
= xfs_dir_leaf_lasthash(blk
->bp
, &count
);
907 case XFS_DIR2_LEAFN_MAGIC
:
908 ASSERT(XFS_DIR_IS_V2(state
->mp
));
909 lasthash
= xfs_dir2_leafn_lasthash(blk
->bp
, &count
);
913 case XFS_DA_NODE_MAGIC
:
914 lasthash
= xfs_da_node_lasthash(blk
->bp
, &count
);
919 for (blk
--, level
--; level
>= 0; blk
--, level
--) {
920 node
= blk
->bp
->data
;
921 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
922 btree
= &node
->btree
[ blk
->index
];
923 if (INT_GET(btree
->hashval
, ARCH_CONVERT
) == lasthash
)
925 blk
->hashval
= lasthash
;
926 INT_SET(btree
->hashval
, ARCH_CONVERT
, lasthash
);
927 xfs_da_log_buf(state
->args
->trans
, blk
->bp
,
928 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
930 lasthash
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
937 * Remove an entry from an intermediate node.
940 xfs_da_node_remove(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
)
942 xfs_da_intnode_t
*node
;
943 xfs_da_node_entry_t
*btree
;
946 node
= drop_blk
->bp
->data
;
947 ASSERT(drop_blk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
));
948 ASSERT(drop_blk
->index
>= 0);
951 * Copy over the offending entry, or just zero it out.
953 btree
= &node
->btree
[drop_blk
->index
];
954 if (drop_blk
->index
< (INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1)) {
955 tmp
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
) - drop_blk
->index
- 1;
956 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
957 ovbcopy(btree
+ 1, btree
, tmp
);
958 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
959 XFS_DA_LOGRANGE(node
, btree
, tmp
));
960 btree
= &node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ];
962 bzero((char *)btree
, sizeof(xfs_da_node_entry_t
));
963 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
964 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
965 INT_MOD(node
->hdr
.count
, ARCH_CONVERT
, -1);
966 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
967 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
970 * Copy the last hash value from the block to propagate upwards.
973 drop_blk
->hashval
= INT_GET(btree
->hashval
, ARCH_CONVERT
);
977 * Unbalance the btree elements between two intermediate nodes,
978 * move all Btree elements from one node into another.
981 xfs_da_node_unbalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
982 xfs_da_state_blk_t
*save_blk
)
984 xfs_da_intnode_t
*drop_node
, *save_node
;
985 xfs_da_node_entry_t
*btree
;
989 drop_node
= drop_blk
->bp
->data
;
990 save_node
= save_blk
->bp
->data
;
991 ASSERT(INT_GET(drop_node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
992 ASSERT(INT_GET(save_node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
993 tp
= state
->args
->trans
;
996 * If the dying block has lower hashvals, then move all the
997 * elements in the remaining block up to make a hole.
999 if ((INT_GET(drop_node
->btree
[ 0 ].hashval
, ARCH_CONVERT
) < INT_GET(save_node
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
1000 (INT_GET(drop_node
->btree
[ INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
1001 INT_GET(save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))
1003 btree
= &save_node
->btree
[ INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) ];
1004 tmp
= INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_da_node_entry_t
);
1005 ovbcopy(&save_node
->btree
[0], btree
, tmp
);
1006 btree
= &save_node
->btree
[0];
1007 xfs_da_log_buf(tp
, save_blk
->bp
,
1008 XFS_DA_LOGRANGE(save_node
, btree
,
1009 (INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) + INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
)) *
1010 sizeof(xfs_da_node_entry_t
)));
1012 btree
= &save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
) ];
1013 xfs_da_log_buf(tp
, save_blk
->bp
,
1014 XFS_DA_LOGRANGE(save_node
, btree
,
1015 INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) *
1016 sizeof(xfs_da_node_entry_t
)));
1020 * Move all the B-tree elements from drop_blk to save_blk.
1022 tmp
= INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
) * (uint
)sizeof(xfs_da_node_entry_t
);
1023 bcopy(&drop_node
->btree
[0], btree
, tmp
);
1024 INT_MOD(save_node
->hdr
.count
, ARCH_CONVERT
, INT_GET(drop_node
->hdr
.count
, ARCH_CONVERT
));
1026 xfs_da_log_buf(tp
, save_blk
->bp
,
1027 XFS_DA_LOGRANGE(save_node
, &save_node
->hdr
,
1028 sizeof(save_node
->hdr
)));
1031 * Save the last hashval in the remaining block for upward propagation.
1033 save_blk
->hashval
= INT_GET(save_node
->btree
[ INT_GET(save_node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1037 /*========================================================================
1038 * Routines used for finding things in the Btree.
1039 *========================================================================*/
1042 * Walk down the Btree looking for a particular filename, filling
1043 * in the state structure as we go.
1045 * We will set the state structure to point to each of the elements
1046 * in each of the nodes where either the hashval is or should be.
1048 * We support duplicate hashval's so for each entry in the current
1049 * node that could contain the desired hashval, descend. This is a
1050 * pruned depth-first tree search.
1053 xfs_da_node_lookup_int(xfs_da_state_t
*state
, int *result
)
1055 xfs_da_state_blk_t
*blk
;
1056 xfs_da_blkinfo_t
*curr
;
1057 xfs_da_intnode_t
*node
;
1058 xfs_da_node_entry_t
*btree
;
1060 int probe
, span
, max
, error
, retval
;
1061 xfs_dahash_t hashval
;
1062 xfs_da_args_t
*args
;
1066 * Descend thru the B-tree searching each level for the right
1067 * node to use, until the right hashval is found.
1069 if (args
->whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(state
->mp
))
1070 blkno
= state
->mp
->m_dirleafblk
;
1073 for (blk
= &state
->path
.blk
[0], state
->path
.active
= 1;
1074 state
->path
.active
<= XFS_DA_NODE_MAXDEPTH
;
1075 blk
++, state
->path
.active
++) {
1077 * Read the next node down in the tree.
1080 error
= xfs_da_read_buf(state
->args
->trans
, state
->args
->dp
,
1081 blkno
, -1, &blk
->bp
,
1082 state
->args
->whichfork
);
1085 state
->path
.active
--;
1088 ASSERT(blk
->bp
!= NULL
);
1089 curr
= blk
->bp
->data
;
1090 ASSERT(INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
||
1091 INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1092 INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
1095 * Search an intermediate node for a match.
1097 blk
->magic
= INT_GET(curr
->magic
, ARCH_CONVERT
);
1098 if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
1099 node
= blk
->bp
->data
;
1100 blk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1103 * Binary search. (note: small blocks will skip loop)
1105 max
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
1106 probe
= span
= max
/ 2;
1107 hashval
= state
->args
->hashval
;
1108 for (btree
= &node
->btree
[probe
]; span
> 4;
1109 btree
= &node
->btree
[probe
]) {
1111 if (INT_GET(btree
->hashval
, ARCH_CONVERT
) < hashval
)
1113 else if (INT_GET(btree
->hashval
, ARCH_CONVERT
) > hashval
)
1118 ASSERT((probe
>= 0) && (probe
< max
));
1119 ASSERT((span
<= 4) || (INT_GET(btree
->hashval
, ARCH_CONVERT
) == hashval
));
1122 * Since we may have duplicate hashval's, find the first
1123 * matching hashval in the node.
1125 while ((probe
> 0) && (INT_GET(btree
->hashval
, ARCH_CONVERT
) >= hashval
)) {
1129 while ((probe
< max
) && (INT_GET(btree
->hashval
, ARCH_CONVERT
) < hashval
)) {
1135 * Pick the right block to descend on.
1139 blkno
= INT_GET(node
->btree
[ max
-1 ].before
, ARCH_CONVERT
);
1142 blkno
= INT_GET(btree
->before
, ARCH_CONVERT
);
1146 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
) {
1147 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
, NULL
);
1151 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
) {
1152 blk
->hashval
= xfs_dir_leaf_lasthash(blk
->bp
, NULL
);
1155 else if (INT_GET(curr
->magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
) {
1156 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
, NULL
);
1162 * A leaf block that ends in the hashval that we are interested in
1163 * (final hashval == search hashval) means that the next block may
1164 * contain more entries with the same hashval, shift upward to the
1165 * next leaf and keep searching.
1168 if (blk
->magic
== XFS_DIR_LEAF_MAGIC
) {
1169 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1170 retval
= xfs_dir_leaf_lookup_int(blk
->bp
, state
->args
,
1172 } else if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
) {
1173 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1174 retval
= xfs_dir2_leafn_lookup_int(blk
->bp
, state
->args
,
1175 &blk
->index
, state
);
1178 else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1179 retval
= xfs_attr_leaf_lookup_int(blk
->bp
, state
->args
);
1180 blk
->index
= state
->args
->index
;
1181 state
->args
->blkno
= blk
->blkno
;
1184 if (((retval
== ENOENT
) || (retval
== ENOATTR
)) &&
1185 (blk
->hashval
== state
->args
->hashval
)) {
1186 error
= xfs_da_path_shift(state
, &state
->path
, 1, 1,
1194 else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1195 /* path_shift() gives ENOENT */
1196 retval
= XFS_ERROR(ENOATTR
);
1207 /*========================================================================
1209 *========================================================================*/
1212 * Link a new block into a doubly linked list of blocks (of whatever type).
1215 xfs_da_blk_link(xfs_da_state_t
*state
, xfs_da_state_blk_t
*old_blk
,
1216 xfs_da_state_blk_t
*new_blk
)
1218 xfs_da_blkinfo_t
*old_info
, *new_info
, *tmp_info
;
1219 xfs_da_args_t
*args
;
1220 int before
=0, error
;
1224 * Set up environment.
1227 ASSERT(args
!= NULL
);
1228 old_info
= old_blk
->bp
->data
;
1229 new_info
= new_blk
->bp
->data
;
1230 ASSERT(old_blk
->magic
== XFS_DA_NODE_MAGIC
||
1231 old_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1232 old_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1233 ASSERT(old_blk
->magic
== INT_GET(old_info
->magic
, ARCH_CONVERT
));
1234 ASSERT(new_blk
->magic
== INT_GET(new_info
->magic
, ARCH_CONVERT
));
1235 ASSERT(old_blk
->magic
== new_blk
->magic
);
1237 switch (old_blk
->magic
) {
1239 case XFS_ATTR_LEAF_MAGIC
:
1240 before
= xfs_attr_leaf_order(old_blk
->bp
, new_blk
->bp
);
1243 case XFS_DIR_LEAF_MAGIC
:
1244 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1245 before
= xfs_dir_leaf_order(old_blk
->bp
, new_blk
->bp
);
1247 case XFS_DIR2_LEAFN_MAGIC
:
1248 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1249 before
= xfs_dir2_leafn_order(old_blk
->bp
, new_blk
->bp
);
1251 case XFS_DA_NODE_MAGIC
:
1252 before
= xfs_da_node_order(old_blk
->bp
, new_blk
->bp
);
1257 * Link blocks in appropriate order.
1261 * Link new block in before existing block.
1263 INT_SET(new_info
->forw
, ARCH_CONVERT
, old_blk
->blkno
);
1264 new_info
->back
= old_info
->back
; /* INT_: direct copy */
1265 if (INT_GET(old_info
->back
, ARCH_CONVERT
)) {
1266 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1267 INT_GET(old_info
->back
,
1268 ARCH_CONVERT
), -1, &bp
,
1273 tmp_info
= bp
->data
;
1274 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
) == INT_GET(old_info
->magic
, ARCH_CONVERT
));
1275 ASSERT(INT_GET(tmp_info
->forw
, ARCH_CONVERT
) == old_blk
->blkno
);
1276 INT_SET(tmp_info
->forw
, ARCH_CONVERT
, new_blk
->blkno
);
1277 xfs_da_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1278 xfs_da_buf_done(bp
);
1280 INT_SET(old_info
->back
, ARCH_CONVERT
, new_blk
->blkno
);
1283 * Link new block in after existing block.
1285 new_info
->forw
= old_info
->forw
; /* INT_: direct copy */
1286 INT_SET(new_info
->back
, ARCH_CONVERT
, old_blk
->blkno
);
1287 if (INT_GET(old_info
->forw
, ARCH_CONVERT
)) {
1288 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1289 INT_GET(old_info
->forw
, ARCH_CONVERT
), -1, &bp
,
1294 tmp_info
= bp
->data
;
1295 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
)
1296 == INT_GET(old_info
->magic
, ARCH_CONVERT
));
1297 ASSERT(INT_GET(tmp_info
->back
, ARCH_CONVERT
)
1299 INT_SET(tmp_info
->back
, ARCH_CONVERT
, new_blk
->blkno
);
1300 xfs_da_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1301 xfs_da_buf_done(bp
);
1303 INT_SET(old_info
->forw
, ARCH_CONVERT
, new_blk
->blkno
);
1306 xfs_da_log_buf(args
->trans
, old_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1307 xfs_da_log_buf(args
->trans
, new_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1313 * Compare two intermediate nodes for "order".
1316 xfs_da_node_order(xfs_dabuf_t
*node1_bp
, xfs_dabuf_t
*node2_bp
)
1318 xfs_da_intnode_t
*node1
, *node2
;
1320 node1
= node1_bp
->data
;
1321 node2
= node2_bp
->data
;
1322 ASSERT((INT_GET(node1
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) &&
1323 (INT_GET(node2
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
));
1324 if ((INT_GET(node1
->hdr
.count
, ARCH_CONVERT
) > 0) && (INT_GET(node2
->hdr
.count
, ARCH_CONVERT
) > 0) &&
1325 ((INT_GET(node2
->btree
[ 0 ].hashval
, ARCH_CONVERT
) <
1326 INT_GET(node1
->btree
[ 0 ].hashval
, ARCH_CONVERT
)) ||
1327 (INT_GET(node2
->btree
[ INT_GET(node2
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
) <
1328 INT_GET(node1
->btree
[ INT_GET(node1
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
)))) {
1336 * Pick up the last hashvalue from an intermediate node.
1339 xfs_da_node_lasthash(xfs_dabuf_t
*bp
, int *count
)
1341 xfs_da_intnode_t
*node
;
1344 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1346 *count
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
);
1347 if (INT_ISZERO(node
->hdr
.count
, ARCH_CONVERT
))
1349 return(INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
));
1353 * Unlink a block from a doubly linked list of blocks.
1356 xfs_da_blk_unlink(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
1357 xfs_da_state_blk_t
*save_blk
)
1359 xfs_da_blkinfo_t
*drop_info
, *save_info
, *tmp_info
;
1360 xfs_da_args_t
*args
;
1365 * Set up environment.
1368 ASSERT(args
!= NULL
);
1369 save_info
= save_blk
->bp
->data
;
1370 drop_info
= drop_blk
->bp
->data
;
1371 ASSERT(save_blk
->magic
== XFS_DA_NODE_MAGIC
||
1372 save_blk
->magic
== XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1373 save_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1374 ASSERT(save_blk
->magic
== INT_GET(save_info
->magic
, ARCH_CONVERT
));
1375 ASSERT(drop_blk
->magic
== INT_GET(drop_info
->magic
, ARCH_CONVERT
));
1376 ASSERT(save_blk
->magic
== drop_blk
->magic
);
1377 ASSERT((INT_GET(save_info
->forw
, ARCH_CONVERT
) == drop_blk
->blkno
) ||
1378 (INT_GET(save_info
->back
, ARCH_CONVERT
) == drop_blk
->blkno
));
1379 ASSERT((INT_GET(drop_info
->forw
, ARCH_CONVERT
) == save_blk
->blkno
) ||
1380 (INT_GET(drop_info
->back
, ARCH_CONVERT
) == save_blk
->blkno
));
1383 * Unlink the leaf block from the doubly linked chain of leaves.
1385 if (INT_GET(save_info
->back
, ARCH_CONVERT
) == drop_blk
->blkno
) {
1386 save_info
->back
= drop_info
->back
; /* INT_: direct copy */
1387 if (INT_GET(drop_info
->back
, ARCH_CONVERT
)) {
1388 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1389 INT_GET(drop_info
->back
,
1390 ARCH_CONVERT
), -1, &bp
,
1395 tmp_info
= bp
->data
;
1396 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
) == INT_GET(save_info
->magic
, ARCH_CONVERT
));
1397 ASSERT(INT_GET(tmp_info
->forw
, ARCH_CONVERT
) == drop_blk
->blkno
);
1398 INT_SET(tmp_info
->forw
, ARCH_CONVERT
, save_blk
->blkno
);
1399 xfs_da_log_buf(args
->trans
, bp
, 0,
1400 sizeof(*tmp_info
) - 1);
1401 xfs_da_buf_done(bp
);
1404 save_info
->forw
= drop_info
->forw
; /* INT_: direct copy */
1405 if (INT_GET(drop_info
->forw
, ARCH_CONVERT
)) {
1406 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1407 INT_GET(drop_info
->forw
, ARCH_CONVERT
), -1, &bp
,
1412 tmp_info
= bp
->data
;
1413 ASSERT(INT_GET(tmp_info
->magic
, ARCH_CONVERT
)
1414 == INT_GET(save_info
->magic
, ARCH_CONVERT
));
1415 ASSERT(INT_GET(tmp_info
->back
, ARCH_CONVERT
)
1416 == drop_blk
->blkno
);
1417 INT_SET(tmp_info
->back
, ARCH_CONVERT
, save_blk
->blkno
);
1418 xfs_da_log_buf(args
->trans
, bp
, 0,
1419 sizeof(*tmp_info
) - 1);
1420 xfs_da_buf_done(bp
);
1424 xfs_da_log_buf(args
->trans
, save_blk
->bp
, 0, sizeof(*save_info
) - 1);
1429 * Move a path "forward" or "!forward" one block at the current level.
1431 * This routine will adjust a "path" to point to the next block
1432 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1433 * Btree, including updating pointers to the intermediate nodes between
1434 * the new bottom and the root.
1437 xfs_da_path_shift(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
,
1438 int forward
, int release
, int *result
)
1440 xfs_da_state_blk_t
*blk
;
1441 xfs_da_blkinfo_t
*info
;
1442 xfs_da_intnode_t
*node
;
1443 xfs_da_args_t
*args
;
1444 xfs_dablk_t blkno
=0;
1448 * Roll up the Btree looking for the first block where our
1449 * current index is not at the edge of the block. Note that
1450 * we skip the bottom layer because we want the sibling block.
1453 ASSERT(args
!= NULL
);
1454 ASSERT(path
!= NULL
);
1455 ASSERT((path
->active
> 0) && (path
->active
< XFS_DA_NODE_MAXDEPTH
));
1456 level
= (path
->active
-1) - 1; /* skip bottom layer in path */
1457 for (blk
= &path
->blk
[level
]; level
>= 0; blk
--, level
--) {
1458 ASSERT(blk
->bp
!= NULL
);
1459 node
= blk
->bp
->data
;
1460 ASSERT(INT_GET(node
->hdr
.info
.magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1461 if (forward
&& (blk
->index
< INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1)) {
1463 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1465 } else if (!forward
&& (blk
->index
> 0)) {
1467 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1472 *result
= XFS_ERROR(ENOENT
); /* we're out of our tree */
1473 ASSERT(args
->oknoent
);
1478 * Roll down the edge of the subtree until we reach the
1479 * same depth we were at originally.
1481 for (blk
++, level
++; level
< path
->active
; blk
++, level
++) {
1483 * Release the old block.
1484 * (if it's dirty, trans won't actually let go)
1487 xfs_da_brelse(args
->trans
, blk
->bp
);
1490 * Read the next child block.
1493 error
= xfs_da_read_buf(args
->trans
, args
->dp
, blkno
, -1,
1494 &blk
->bp
, args
->whichfork
);
1497 ASSERT(blk
->bp
!= NULL
);
1498 info
= blk
->bp
->data
;
1499 ASSERT(INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
||
1500 INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DIRX_LEAF_MAGIC(state
->mp
) ||
1501 INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_ATTR_LEAF_MAGIC
);
1502 blk
->magic
= INT_GET(info
->magic
, ARCH_CONVERT
);
1503 if (INT_GET(info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
) {
1504 node
= (xfs_da_intnode_t
*)info
;
1505 blk
->hashval
= INT_GET(node
->btree
[ INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1 ].hashval
, ARCH_CONVERT
);
1509 blk
->index
= INT_GET(node
->hdr
.count
, ARCH_CONVERT
)-1;
1510 blkno
= INT_GET(node
->btree
[ blk
->index
].before
, ARCH_CONVERT
);
1512 ASSERT(level
== path
->active
-1);
1514 switch(blk
->magic
) {
1516 case XFS_ATTR_LEAF_MAGIC
:
1517 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
,
1521 case XFS_DIR_LEAF_MAGIC
:
1522 ASSERT(XFS_DIR_IS_V1(state
->mp
));
1523 blk
->hashval
= xfs_dir_leaf_lasthash(blk
->bp
,
1526 case XFS_DIR2_LEAFN_MAGIC
:
1527 ASSERT(XFS_DIR_IS_V2(state
->mp
));
1528 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
,
1532 ASSERT(blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
1534 XFS_DIRX_LEAF_MAGIC(state
->mp
));
1544 /*========================================================================
1546 *========================================================================*/
1549 * Implement a simple hash on a character string.
1550 * Rotate the hash value by 7 bits, then XOR each character in.
1551 * This is implemented with some source-level loop unrolling.
1554 xfs_da_hashname(uchar_t
*name
, int namelen
)
1558 #define ROTL(x,y) (((x) << (y)) | ((x) >> (32 - (y))))
1561 * This is the old one-byte-at-a-time version.
1563 for (hash
= 0; namelen
> 0; namelen
--) {
1564 hash
= *name
++ ^ ROTL(hash
, 7);
1569 * Do four characters at a time as long as we can.
1571 for (hash
= 0; namelen
>= 4; namelen
-= 4, name
+= 4) {
1572 hash
= (name
[0] << 21) ^ (name
[1] << 14) ^ (name
[2] << 7) ^
1573 (name
[3] << 0) ^ ROTL(hash
, 7 * 4);
1576 * Now do the rest of the characters.
1580 return (name
[0] << 14) ^ (name
[1] << 7) ^ (name
[2] << 0) ^
1583 return (name
[0] << 7) ^ (name
[1] << 0) ^ ROTL(hash
, 7 * 2);
1585 return (name
[0] << 0) ^ ROTL(hash
, 7 * 1);
1592 return 0; /* keep gcc happy */
1596 * Add a block to the btree ahead of the file.
1597 * Return the new block number to the caller.
1600 xfs_da_grow_inode(xfs_da_args_t
*args
, xfs_dablk_t
*new_blkno
)
1602 xfs_fileoff_t bno
, b
;
1603 xfs_bmbt_irec_t map
;
1604 xfs_bmbt_irec_t
*mapp
;
1606 int nmap
, error
, w
, count
, c
, got
, i
, mapi
;
1613 w
= args
->whichfork
;
1616 * For new directories adjust the file offset and block count.
1618 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
)) {
1619 bno
= mp
->m_dirleafblk
;
1620 count
= mp
->m_dirblkfsbs
;
1626 * Find a spot in the file space to put the new block.
1628 if ((error
= xfs_bmap_first_unused(tp
, dp
, count
, &bno
, w
))) {
1631 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
1632 ASSERT(bno
>= mp
->m_dirleafblk
&& bno
< mp
->m_dirfreeblk
);
1634 * Try mapping it in one filesystem block.
1637 ASSERT(args
->firstblock
!= NULL
);
1638 if ((error
= xfs_bmapi(tp
, dp
, bno
, count
,
1639 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_WRITE
|XFS_BMAPI_METADATA
|
1641 args
->firstblock
, args
->total
, &map
, &nmap
,
1651 * If we didn't get it and the block might work if fragmented,
1652 * try without the CONTIG flag. Loop until we get it all.
1654 else if (nmap
== 0 && count
> 1) {
1655 mapp
= kmem_alloc(sizeof(*mapp
) * count
, KM_SLEEP
);
1656 for (b
= bno
, mapi
= 0; b
< bno
+ count
; ) {
1657 nmap
= MIN(XFS_BMAP_MAX_NMAP
, count
);
1658 c
= (int)(bno
+ count
- b
);
1659 if ((error
= xfs_bmapi(tp
, dp
, b
, c
,
1660 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_WRITE
|
1662 args
->firstblock
, args
->total
,
1663 &mapp
[mapi
], &nmap
, args
->flist
))) {
1664 kmem_free(mapp
, sizeof(*mapp
) * count
);
1670 b
= mapp
[mapi
- 1].br_startoff
+
1671 mapp
[mapi
- 1].br_blockcount
;
1678 * Count the blocks we got, make sure it matches the total.
1680 for (i
= 0, got
= 0; i
< mapi
; i
++)
1681 got
+= mapp
[i
].br_blockcount
;
1682 if (got
!= count
|| mapp
[0].br_startoff
!= bno
||
1683 mapp
[mapi
- 1].br_startoff
+ mapp
[mapi
- 1].br_blockcount
!=
1686 kmem_free(mapp
, sizeof(*mapp
) * count
);
1687 return XFS_ERROR(ENOSPC
);
1690 kmem_free(mapp
, sizeof(*mapp
) * count
);
1691 *new_blkno
= (xfs_dablk_t
)bno
;
1693 * For version 1 directories, adjust the file size if it changed.
1695 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V1(mp
)) {
1697 if ((error
= xfs_bmap_last_offset(tp
, dp
, &bno
, w
)))
1699 size
= XFS_FSB_TO_B(mp
, bno
);
1700 if (size
!= dp
->i_d
.di_size
) {
1701 dp
->i_d
.di_size
= size
;
1702 xfs_trans_log_inode(tp
, dp
, XFS_ILOG_CORE
);
1710 * Ick. We need to always be able to remove a btree block, even
1711 * if there's no space reservation because the filesystem is full.
1712 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
1713 * It swaps the target block with the last block in the file. The
1714 * last block in the file can always be removed since it can't cause
1715 * a bmap btree split to do that.
1718 xfs_da_swap_lastblock(xfs_da_args_t
*args
, xfs_dablk_t
*dead_blknop
,
1719 xfs_dabuf_t
**dead_bufp
)
1721 xfs_dablk_t dead_blkno
, last_blkno
, sib_blkno
, par_blkno
;
1722 xfs_dabuf_t
*dead_buf
, *last_buf
, *sib_buf
, *par_buf
;
1723 xfs_fileoff_t lastoff
;
1727 int error
, w
, entno
, level
, dead_level
;
1728 xfs_da_blkinfo_t
*dead_info
, *sib_info
;
1729 xfs_da_intnode_t
*par_node
, *dead_node
;
1730 xfs_dir_leafblock_t
*dead_leaf
;
1731 xfs_dir2_leaf_t
*dead_leaf2
;
1732 xfs_dahash_t dead_hash
;
1734 dead_buf
= *dead_bufp
;
1735 dead_blkno
= *dead_blknop
;
1738 w
= args
->whichfork
;
1739 ASSERT(w
== XFS_DATA_FORK
);
1741 if (XFS_DIR_IS_V2(mp
)) {
1742 lastoff
= mp
->m_dirfreeblk
;
1743 error
= xfs_bmap_last_before(tp
, ip
, &lastoff
, w
);
1745 error
= xfs_bmap_last_offset(tp
, ip
, &lastoff
, w
);
1749 return XFS_ERROR(EFSCORRUPTED
);
1751 * Read the last block in the btree space.
1753 last_blkno
= (xfs_dablk_t
)lastoff
- mp
->m_dirblkfsbs
;
1754 if ((error
= xfs_da_read_buf(tp
, ip
, last_blkno
, -1, &last_buf
, w
)))
1757 * Copy the last block into the dead buffer and log it.
1759 bcopy(last_buf
->data
, dead_buf
->data
, mp
->m_dirblksize
);
1760 xfs_da_log_buf(tp
, dead_buf
, 0, mp
->m_dirblksize
- 1);
1761 dead_info
= dead_buf
->data
;
1763 * Get values from the moved block.
1765 if (INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DIR_LEAF_MAGIC
) {
1766 ASSERT(XFS_DIR_IS_V1(mp
));
1767 dead_leaf
= (xfs_dir_leafblock_t
*)dead_info
;
1770 INT_GET(dead_leaf
->entries
[INT_GET(dead_leaf
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1771 } else if (INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DIR2_LEAFN_MAGIC
) {
1772 ASSERT(XFS_DIR_IS_V2(mp
));
1773 dead_leaf2
= (xfs_dir2_leaf_t
*)dead_info
;
1775 dead_hash
= INT_GET(dead_leaf2
->ents
[INT_GET(dead_leaf2
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1777 ASSERT(INT_GET(dead_info
->magic
, ARCH_CONVERT
) == XFS_DA_NODE_MAGIC
);
1778 dead_node
= (xfs_da_intnode_t
*)dead_info
;
1779 dead_level
= INT_GET(dead_node
->hdr
.level
, ARCH_CONVERT
);
1780 dead_hash
= INT_GET(dead_node
->btree
[INT_GET(dead_node
->hdr
.count
, ARCH_CONVERT
) - 1].hashval
, ARCH_CONVERT
);
1782 sib_buf
= par_buf
= NULL
;
1784 * If the moved block has a left sibling, fix up the pointers.
1786 if ((sib_blkno
= INT_GET(dead_info
->back
, ARCH_CONVERT
))) {
1787 if ((error
= xfs_da_read_buf(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
)))
1789 sib_info
= sib_buf
->data
;
1790 if (INT_GET(sib_info
->forw
, ARCH_CONVERT
) != last_blkno
||
1791 INT_GET(sib_info
->magic
, ARCH_CONVERT
) != INT_GET(dead_info
->magic
, ARCH_CONVERT
)) {
1792 error
= XFS_ERROR(EFSCORRUPTED
);
1795 INT_SET(sib_info
->forw
, ARCH_CONVERT
, dead_blkno
);
1796 xfs_da_log_buf(tp
, sib_buf
,
1797 XFS_DA_LOGRANGE(sib_info
, &sib_info
->forw
,
1798 sizeof(sib_info
->forw
)));
1799 xfs_da_buf_done(sib_buf
);
1803 * If the moved block has a right sibling, fix up the pointers.
1805 if ((sib_blkno
= INT_GET(dead_info
->forw
, ARCH_CONVERT
))) {
1806 if ((error
= xfs_da_read_buf(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
)))
1808 sib_info
= sib_buf
->data
;
1809 if ( INT_GET(sib_info
->back
, ARCH_CONVERT
) != last_blkno
1810 || INT_GET(sib_info
->magic
, ARCH_CONVERT
)
1811 != INT_GET(dead_info
->magic
, ARCH_CONVERT
)) {
1812 error
= XFS_ERROR(EFSCORRUPTED
);
1815 INT_SET(sib_info
->back
, ARCH_CONVERT
, dead_blkno
);
1816 xfs_da_log_buf(tp
, sib_buf
,
1817 XFS_DA_LOGRANGE(sib_info
, &sib_info
->back
,
1818 sizeof(sib_info
->back
)));
1819 xfs_da_buf_done(sib_buf
);
1822 par_blkno
= XFS_DIR_IS_V1(mp
) ? 0 : mp
->m_dirleafblk
;
1825 * Walk down the tree looking for the parent of the moved block.
1828 if ((error
= xfs_da_read_buf(tp
, ip
, par_blkno
, -1, &par_buf
, w
)))
1830 par_node
= par_buf
->data
;
1831 if (INT_GET(par_node
->hdr
.info
.magic
, ARCH_CONVERT
) != XFS_DA_NODE_MAGIC
||
1832 (level
>= 0 && level
!= INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
) + 1)) {
1833 error
= XFS_ERROR(EFSCORRUPTED
);
1836 level
= INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
);
1838 entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
) &&
1839 INT_GET(par_node
->btree
[entno
].hashval
, ARCH_CONVERT
) < dead_hash
;
1842 if (entno
== INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
)) {
1843 error
= XFS_ERROR(EFSCORRUPTED
);
1846 par_blkno
= INT_GET(par_node
->btree
[entno
].before
, ARCH_CONVERT
);
1847 if (level
== dead_level
+ 1)
1849 xfs_da_brelse(tp
, par_buf
);
1853 * We're in the right parent block.
1854 * Look for the right entry.
1858 entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
) &&
1859 INT_GET(par_node
->btree
[entno
].before
, ARCH_CONVERT
) != last_blkno
;
1862 if (entno
< INT_GET(par_node
->hdr
.count
, ARCH_CONVERT
))
1864 par_blkno
= INT_GET(par_node
->hdr
.info
.forw
, ARCH_CONVERT
);
1865 xfs_da_brelse(tp
, par_buf
);
1867 if (par_blkno
== 0) {
1868 error
= XFS_ERROR(EFSCORRUPTED
);
1871 if ((error
= xfs_da_read_buf(tp
, ip
, par_blkno
, -1, &par_buf
, w
)))
1873 par_node
= par_buf
->data
;
1874 if (INT_GET(par_node
->hdr
.level
, ARCH_CONVERT
) != level
||
1875 INT_GET(par_node
->hdr
.info
.magic
, ARCH_CONVERT
) != XFS_DA_NODE_MAGIC
) {
1876 error
= XFS_ERROR(EFSCORRUPTED
);
1882 * Update the parent entry pointing to the moved block.
1884 INT_SET(par_node
->btree
[entno
].before
, ARCH_CONVERT
, dead_blkno
);
1885 xfs_da_log_buf(tp
, par_buf
,
1886 XFS_DA_LOGRANGE(par_node
, &par_node
->btree
[entno
].before
,
1887 sizeof(par_node
->btree
[entno
].before
)));
1888 xfs_da_buf_done(par_buf
);
1889 xfs_da_buf_done(dead_buf
);
1890 *dead_blknop
= last_blkno
;
1891 *dead_bufp
= last_buf
;
1895 xfs_da_brelse(tp
, par_buf
);
1897 xfs_da_brelse(tp
, sib_buf
);
1898 xfs_da_brelse(tp
, last_buf
);
1903 * Remove a btree block from a directory or attribute.
1906 xfs_da_shrink_inode(xfs_da_args_t
*args
, xfs_dablk_t dead_blkno
,
1907 xfs_dabuf_t
*dead_buf
)
1910 int done
, error
, w
, count
;
1917 w
= args
->whichfork
;
1920 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
1921 count
= mp
->m_dirblkfsbs
;
1926 * Remove extents. If we get ENOSPC for a dir we have to move
1927 * the last block to the place we want to kill.
1929 if ((error
= xfs_bunmapi(tp
, dp
, dead_blkno
, count
,
1930 XFS_BMAPI_AFLAG(w
)|XFS_BMAPI_METADATA
,
1931 0, args
->firstblock
, args
->flist
,
1932 &done
)) == ENOSPC
) {
1933 if (w
!= XFS_DATA_FORK
)
1935 if ((error
= xfs_da_swap_lastblock(args
, &dead_blkno
,
1944 xfs_da_binval(tp
, dead_buf
);
1946 * Adjust the directory size for version 1.
1948 if (w
== XFS_DATA_FORK
&& XFS_DIR_IS_V1(mp
)) {
1949 if ((error
= xfs_bmap_last_offset(tp
, dp
, &bno
, w
)))
1951 size
= XFS_FSB_TO_B(dp
->i_mount
, bno
);
1952 if (size
!= dp
->i_d
.di_size
) {
1953 dp
->i_d
.di_size
= size
;
1954 xfs_trans_log_inode(tp
, dp
, XFS_ILOG_CORE
);
1959 xfs_da_binval(tp
, dead_buf
);
1964 * See if the mapping(s) for this btree block are valid, i.e.
1965 * don't contain holes, are logically contiguous, and cover the whole range.
1968 xfs_da_map_covers_blocks(
1970 xfs_bmbt_irec_t
*mapp
,
1977 for (i
= 0, off
= bno
; i
< nmap
; i
++) {
1978 if (mapp
[i
].br_startblock
== HOLESTARTBLOCK
||
1979 mapp
[i
].br_startblock
== DELAYSTARTBLOCK
) {
1982 if (off
!= mapp
[i
].br_startoff
) {
1985 off
+= mapp
[i
].br_blockcount
;
1987 return off
== bno
+ count
;
1992 * Used for get_buf, read_buf, read_bufr, and reada_buf.
1999 xfs_daddr_t
*mappedbnop
,
2009 xfs_bmbt_irec_t map
;
2010 xfs_bmbt_irec_t
*mapp
;
2011 xfs_daddr_t mappedbno
;
2019 if (whichfork
== XFS_DATA_FORK
&& XFS_DIR_IS_V2(mp
))
2020 nfsb
= mp
->m_dirblkfsbs
;
2023 mappedbno
= *mappedbnop
;
2025 * Caller doesn't have a mapping. -2 means don't complain
2026 * if we land in a hole.
2028 if (mappedbno
== -1 || mappedbno
== -2) {
2030 * Optimize the one-block case.
2036 xfs_bmapi_single(trans
, dp
, whichfork
, &fsb
,
2037 (xfs_fileoff_t
)bno
))) {
2041 if (fsb
== NULLFSBLOCK
) {
2044 map
.br_startblock
= fsb
;
2045 map
.br_startoff
= (xfs_fileoff_t
)bno
;
2046 map
.br_blockcount
= 1;
2050 xfs_fsblock_t firstblock
;
2052 firstblock
= NULLFSBLOCK
;
2053 mapp
= kmem_alloc(sizeof(*mapp
) * nfsb
, KM_SLEEP
);
2055 if ((error
= xfs_bmapi(trans
, dp
, (xfs_fileoff_t
)bno
,
2057 XFS_BMAPI_METADATA
|
2058 XFS_BMAPI_AFLAG(whichfork
),
2059 &firstblock
, 0, mapp
, &nmap
, NULL
)))
2063 map
.br_startblock
= XFS_DADDR_TO_FSB(mp
, mappedbno
);
2064 map
.br_startoff
= (xfs_fileoff_t
)bno
;
2065 map
.br_blockcount
= nfsb
;
2069 if (!xfs_da_map_covers_blocks(nmap
, mapp
, bno
, nfsb
)) {
2070 error
= mappedbno
== -2 ? 0 : XFS_ERROR(EFSCORRUPTED
);
2073 if (caller
!= 3 && nmap
> 1) {
2074 bplist
= kmem_alloc(sizeof(*bplist
) * nmap
, KM_SLEEP
);
2079 * Turn the mapping(s) into buffer(s).
2081 for (i
= 0; i
< nmap
; i
++) {
2084 mappedbno
= XFS_FSB_TO_DADDR(mp
, mapp
[i
].br_startblock
);
2086 *mappedbnop
= mappedbno
;
2087 nmapped
= (int)XFS_FSB_TO_BB(mp
, mapp
[i
].br_blockcount
);
2090 bp
= xfs_trans_get_buf(trans
, mp
->m_ddev_targp
,
2091 mappedbno
, nmapped
, 0);
2092 error
= bp
? XFS_BUF_GETERROR(bp
) : XFS_ERROR(EIO
);
2099 error
= xfs_trans_read_buf(mp
, trans
, mp
->m_ddev_targp
,
2100 mappedbno
, nmapped
, 0, &bp
);
2104 xfs_baread(mp
->m_ddev_targp
, mappedbno
, nmapped
);
2112 xfs_trans_brelse(trans
, bp
);
2118 if (whichfork
== XFS_ATTR_FORK
) {
2119 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_ATTR_BTREE
,
2120 XFS_ATTR_BTREE_REF
);
2122 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_DIR_BTREE
,
2127 bplist
[nbplist
++] = bp
;
2131 * Build a dabuf structure.
2134 rbp
= xfs_da_buf_make(nbplist
, bplist
, ra
);
2136 rbp
= xfs_da_buf_make(1, &bp
, ra
);
2140 * For read_buf, check the magic number.
2143 xfs_dir2_data_t
*data
;
2144 xfs_dir2_free_t
*free
;
2145 xfs_da_blkinfo_t
*info
;
2151 magic
= INT_GET(info
->magic
, ARCH_CONVERT
);
2152 magic1
= INT_GET(data
->hdr
.magic
, ARCH_CONVERT
);
2153 if (XFS_TEST_ERROR((magic
!= XFS_DA_NODE_MAGIC
) &&
2154 (magic
!= XFS_DIR_LEAF_MAGIC
) &&
2155 (magic
!= XFS_ATTR_LEAF_MAGIC
) &&
2156 (magic
!= XFS_DIR2_LEAF1_MAGIC
) &&
2157 (magic
!= XFS_DIR2_LEAFN_MAGIC
) &&
2158 (magic1
!= XFS_DIR2_BLOCK_MAGIC
) &&
2159 (magic1
!= XFS_DIR2_DATA_MAGIC
) &&
2160 (INT_GET(free
->hdr
.magic
, ARCH_CONVERT
) != XFS_DIR2_FREE_MAGIC
),
2161 mp
, XFS_ERRTAG_DA_READ_BUF
,
2162 XFS_RANDOM_DA_READ_BUF
)) {
2163 xfs_buftrace("DA READ ERROR", rbp
->bps
[0]);
2164 error
= XFS_ERROR(EFSCORRUPTED
);
2165 xfs_da_brelse(trans
, rbp
);
2171 kmem_free(bplist
, sizeof(*bplist
) * nmap
);
2174 kmem_free(mapp
, sizeof(*mapp
) * nfsb
);
2181 for (i
= 0; i
< nbplist
; i
++)
2182 xfs_trans_brelse(trans
, bplist
[i
]);
2183 kmem_free(bplist
, sizeof(*bplist
) * nmap
);
2187 kmem_free(mapp
, sizeof(*mapp
) * nfsb
);
2194 * Get a buffer for the dir/attr block.
2201 xfs_daddr_t mappedbno
,
2205 return xfs_da_do_buf(trans
, dp
, bno
, &mappedbno
, bpp
, whichfork
, 0,
2206 (inst_t
*)__return_address
);
2210 * Get a buffer for the dir/attr block, fill in the contents.
2217 xfs_daddr_t mappedbno
,
2221 return xfs_da_do_buf(trans
, dp
, bno
, &mappedbno
, bpp
, whichfork
, 1,
2222 (inst_t
*)__return_address
);
2226 * Calculate the number of bits needed to hold i different values.
2229 xfs_da_log2_roundup(uint i
)
2233 for (rval
= 0; rval
< NBBY
* sizeof(i
); rval
++) {
2234 if ((1 << rval
) >= i
)
2240 xfs_zone_t
*xfs_da_state_zone
; /* anchor for state struct zone */
2241 xfs_zone_t
*xfs_dabuf_zone
; /* dabuf zone */
2244 * Allocate a dir-state structure.
2245 * We don't put them on the stack since they're large.
2248 xfs_da_state_alloc(void)
2250 return kmem_zone_zalloc(xfs_da_state_zone
, KM_SLEEP
);
2254 * Kill the altpath contents of a da-state structure.
2257 xfs_da_state_kill_altpath(xfs_da_state_t
*state
)
2261 for (i
= 0; i
< state
->altpath
.active
; i
++) {
2262 if (state
->altpath
.blk
[i
].bp
) {
2263 if (state
->altpath
.blk
[i
].bp
!= state
->path
.blk
[i
].bp
)
2264 xfs_da_buf_done(state
->altpath
.blk
[i
].bp
);
2265 state
->altpath
.blk
[i
].bp
= NULL
;
2268 state
->altpath
.active
= 0;
2272 * Free a da-state structure.
2275 xfs_da_state_free(xfs_da_state_t
*state
)
2279 xfs_da_state_kill_altpath(state
);
2280 for (i
= 0; i
< state
->path
.active
; i
++) {
2281 if (state
->path
.blk
[i
].bp
)
2282 xfs_da_buf_done(state
->path
.blk
[i
].bp
);
2284 if (state
->extravalid
&& state
->extrablk
.bp
)
2285 xfs_da_buf_done(state
->extrablk
.bp
);
2287 bzero((char *)state
, sizeof(*state
));
2289 kmem_zone_free(xfs_da_state_zone
, state
);
2292 #ifdef XFS_DABUF_DEBUG
2293 xfs_dabuf_t
*xfs_dabuf_global_list
;
2294 lock_t xfs_dabuf_global_lock
;
2301 STATIC xfs_dabuf_t
*
2302 xfs_da_buf_make(int nbuf
, xfs_buf_t
**bps
, inst_t
*ra
)
2310 dabuf
= kmem_zone_alloc(xfs_dabuf_zone
, KM_SLEEP
);
2312 dabuf
= kmem_alloc(XFS_DA_BUF_SIZE(nbuf
), KM_SLEEP
);
2314 #ifdef XFS_DABUF_DEBUG
2316 dabuf
->dev
= XFS_BUF_TARGET(bps
[0]);
2317 dabuf
->blkno
= XFS_BUF_ADDR(bps
[0]);
2322 dabuf
->bbcount
= (short)BTOBB(XFS_BUF_COUNT(bp
));
2323 dabuf
->data
= XFS_BUF_PTR(bp
);
2327 for (i
= 0, dabuf
->bbcount
= 0; i
< nbuf
; i
++) {
2328 dabuf
->bps
[i
] = bp
= bps
[i
];
2329 dabuf
->bbcount
+= BTOBB(XFS_BUF_COUNT(bp
));
2331 dabuf
->data
= kmem_alloc(BBTOB(dabuf
->bbcount
), KM_SLEEP
);
2332 for (i
= off
= 0; i
< nbuf
; i
++, off
+= XFS_BUF_COUNT(bp
)) {
2334 bcopy(XFS_BUF_PTR(bp
), (char *)dabuf
->data
+ off
,
2338 #ifdef XFS_DABUF_DEBUG
2343 s
= mutex_spinlock(&xfs_dabuf_global_lock
);
2344 for (p
= xfs_dabuf_global_list
; p
; p
= p
->next
) {
2345 ASSERT(p
->blkno
!= dabuf
->blkno
||
2346 p
->dev
!= dabuf
->dev
);
2349 if (xfs_dabuf_global_list
)
2350 xfs_dabuf_global_list
->prev
= dabuf
;
2351 dabuf
->next
= xfs_dabuf_global_list
;
2352 xfs_dabuf_global_list
= dabuf
;
2353 mutex_spinunlock(&xfs_dabuf_global_lock
, s
);
2363 xfs_da_buf_clean(xfs_dabuf_t
*dabuf
)
2370 ASSERT(dabuf
->nbuf
> 1);
2372 for (i
= off
= 0; i
< dabuf
->nbuf
;
2373 i
++, off
+= XFS_BUF_COUNT(bp
)) {
2375 bcopy((char *)dabuf
->data
+ off
, XFS_BUF_PTR(bp
),
2385 xfs_da_buf_done(xfs_dabuf_t
*dabuf
)
2388 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2390 xfs_da_buf_clean(dabuf
);
2391 if (dabuf
->nbuf
> 1)
2392 kmem_free(dabuf
->data
, BBTOB(dabuf
->bbcount
));
2393 #ifdef XFS_DABUF_DEBUG
2397 s
= mutex_spinlock(&xfs_dabuf_global_lock
);
2399 dabuf
->prev
->next
= dabuf
->next
;
2401 xfs_dabuf_global_list
= dabuf
->next
;
2403 dabuf
->next
->prev
= dabuf
->prev
;
2404 mutex_spinunlock(&xfs_dabuf_global_lock
, s
);
2406 bzero(dabuf
, XFS_DA_BUF_SIZE(dabuf
->nbuf
));
2408 if (dabuf
->nbuf
== 1)
2409 kmem_zone_free(xfs_dabuf_zone
, dabuf
);
2411 kmem_free(dabuf
, XFS_DA_BUF_SIZE(dabuf
->nbuf
));
2415 * Log transaction from a dabuf.
2418 xfs_da_log_buf(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
, uint first
, uint last
)
2426 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2427 if (dabuf
->nbuf
== 1) {
2428 ASSERT(dabuf
->data
== (void *)XFS_BUF_PTR(dabuf
->bps
[0]));
2429 xfs_trans_log_buf(tp
, dabuf
->bps
[0], first
, last
);
2433 ASSERT(first
<= last
);
2434 for (i
= off
= 0; i
< dabuf
->nbuf
; i
++, off
+= XFS_BUF_COUNT(bp
)) {
2437 l
= f
+ XFS_BUF_COUNT(bp
) - 1;
2443 xfs_trans_log_buf(tp
, bp
, f
- off
, l
- off
);
2445 * B_DONE is set by xfs_trans_log buf.
2446 * If we don't set it on a new buffer (get not read)
2447 * then if we don't put anything in the buffer it won't
2448 * be set, and at commit it it released into the cache,
2449 * and then a read will fail.
2451 else if (!(XFS_BUF_ISDONE(bp
)))
2458 * Release dabuf from a transaction.
2459 * Have to free up the dabuf before the buffers are released,
2460 * since the synchronization on the dabuf is really the lock on the buffer.
2463 xfs_da_brelse(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
)
2470 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2471 if ((nbuf
= dabuf
->nbuf
) == 1) {
2475 bplist
= kmem_alloc(nbuf
* sizeof(*bplist
), KM_SLEEP
);
2476 bcopy(dabuf
->bps
, bplist
, nbuf
* sizeof(*bplist
));
2478 xfs_da_buf_done(dabuf
);
2479 for (i
= 0; i
< nbuf
; i
++)
2480 xfs_trans_brelse(tp
, bplist
[i
]);
2482 kmem_free(bplist
, nbuf
* sizeof(*bplist
));
2486 * Invalidate dabuf from a transaction.
2489 xfs_da_binval(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
)
2496 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2497 if ((nbuf
= dabuf
->nbuf
) == 1) {
2501 bplist
= kmem_alloc(nbuf
* sizeof(*bplist
), KM_SLEEP
);
2502 bcopy(dabuf
->bps
, bplist
, nbuf
* sizeof(*bplist
));
2504 xfs_da_buf_done(dabuf
);
2505 for (i
= 0; i
< nbuf
; i
++)
2506 xfs_trans_binval(tp
, bplist
[i
]);
2508 kmem_free(bplist
, nbuf
* sizeof(*bplist
));