2 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 #include "xfs_types.h"
23 #include "xfs_trans.h"
26 #include "xfs_mount.h"
27 #include "xfs_da_btree.h"
28 #include "xfs_bmap_btree.h"
30 #include "xfs_dir2_format.h"
31 #include "xfs_dir2_priv.h"
32 #include "xfs_dinode.h"
33 #include "xfs_inode.h"
34 #include "xfs_inode_item.h"
35 #include "xfs_alloc.h"
38 #include "xfs_attr_leaf.h"
39 #include "xfs_error.h"
40 #include "xfs_trace.h"
45 * Routines to implement directories as Btrees of hashed names.
48 /*========================================================================
49 * Function prototypes for the kernel.
50 *========================================================================*/
53 * Routines used for growing the Btree.
55 STATIC
int xfs_da_root_split(xfs_da_state_t
*state
,
56 xfs_da_state_blk_t
*existing_root
,
57 xfs_da_state_blk_t
*new_child
);
58 STATIC
int xfs_da_node_split(xfs_da_state_t
*state
,
59 xfs_da_state_blk_t
*existing_blk
,
60 xfs_da_state_blk_t
*split_blk
,
61 xfs_da_state_blk_t
*blk_to_add
,
64 STATIC
void xfs_da_node_rebalance(xfs_da_state_t
*state
,
65 xfs_da_state_blk_t
*node_blk_1
,
66 xfs_da_state_blk_t
*node_blk_2
);
67 STATIC
void xfs_da_node_add(xfs_da_state_t
*state
,
68 xfs_da_state_blk_t
*old_node_blk
,
69 xfs_da_state_blk_t
*new_node_blk
);
72 * Routines used for shrinking the Btree.
74 STATIC
int xfs_da_root_join(xfs_da_state_t
*state
,
75 xfs_da_state_blk_t
*root_blk
);
76 STATIC
int xfs_da_node_toosmall(xfs_da_state_t
*state
, int *retval
);
77 STATIC
void xfs_da_node_remove(xfs_da_state_t
*state
,
78 xfs_da_state_blk_t
*drop_blk
);
79 STATIC
void xfs_da_node_unbalance(xfs_da_state_t
*state
,
80 xfs_da_state_blk_t
*src_node_blk
,
81 xfs_da_state_blk_t
*dst_node_blk
);
86 STATIC uint
xfs_da_node_lasthash(struct xfs_buf
*bp
, int *count
);
87 STATIC
int xfs_da_node_order(struct xfs_buf
*node1_bp
,
88 struct xfs_buf
*node2_bp
);
89 STATIC
int xfs_da_blk_unlink(xfs_da_state_t
*state
,
90 xfs_da_state_blk_t
*drop_blk
,
91 xfs_da_state_blk_t
*save_blk
);
92 STATIC
void xfs_da_state_kill_altpath(xfs_da_state_t
*state
);
98 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
99 struct xfs_da_node_hdr
*hdr
= bp
->b_addr
;
102 block_ok
= hdr
->info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
);
103 block_ok
= block_ok
&&
104 be16_to_cpu(hdr
->level
) > 0 &&
105 be16_to_cpu(hdr
->count
) > 0 ;
107 XFS_CORRUPTION_ERROR(__func__
, XFS_ERRLEVEL_LOW
, mp
, hdr
);
108 xfs_buf_ioerror(bp
, EFSCORRUPTED
);
114 xfs_da_node_write_verify(
117 xfs_da_node_verify(bp
);
121 xfs_da_node_read_verify(
124 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
125 struct xfs_da_blkinfo
*info
= bp
->b_addr
;
127 switch (be16_to_cpu(info
->magic
)) {
128 case XFS_DA_NODE_MAGIC
:
129 xfs_da_node_verify(bp
);
131 case XFS_ATTR_LEAF_MAGIC
:
132 xfs_attr_leaf_read_verify(bp
);
134 case XFS_DIR2_LEAFN_MAGIC
:
135 xfs_dir2_leafn_read_verify(bp
);
138 XFS_CORRUPTION_ERROR(__func__
, XFS_ERRLEVEL_LOW
,
140 xfs_buf_ioerror(bp
, EFSCORRUPTED
);
144 bp
->b_pre_io
= xfs_da_node_write_verify
;
146 xfs_buf_ioend(bp
, 0);
151 struct xfs_trans
*tp
,
152 struct xfs_inode
*dp
,
154 xfs_daddr_t mappedbno
,
155 struct xfs_buf
**bpp
,
158 return xfs_da_read_buf(tp
, dp
, bno
, mappedbno
, bpp
,
159 which_fork
, xfs_da_node_read_verify
);
162 /*========================================================================
163 * Routines used for growing the Btree.
164 *========================================================================*/
167 * Create the initial contents of an intermediate node.
170 xfs_da_node_create(xfs_da_args_t
*args
, xfs_dablk_t blkno
, int level
,
171 struct xfs_buf
**bpp
, int whichfork
)
173 xfs_da_intnode_t
*node
;
178 trace_xfs_da_node_create(args
);
181 error
= xfs_da_get_buf(tp
, args
->dp
, blkno
, -1, &bp
, whichfork
);
186 node
->hdr
.info
.forw
= 0;
187 node
->hdr
.info
.back
= 0;
188 node
->hdr
.info
.magic
= cpu_to_be16(XFS_DA_NODE_MAGIC
);
189 node
->hdr
.info
.pad
= 0;
191 node
->hdr
.level
= cpu_to_be16(level
);
193 xfs_trans_log_buf(tp
, bp
,
194 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
201 * Split a leaf node, rebalance, then possibly split
202 * intermediate nodes, rebalance, etc.
205 xfs_da_split(xfs_da_state_t
*state
)
207 xfs_da_state_blk_t
*oldblk
, *newblk
, *addblk
;
208 xfs_da_intnode_t
*node
;
210 int max
, action
, error
, i
;
212 trace_xfs_da_split(state
->args
);
215 * Walk back up the tree splitting/inserting/adjusting as necessary.
216 * If we need to insert and there isn't room, split the node, then
217 * decide which fragment to insert the new block from below into.
218 * Note that we may split the root this way, but we need more fixup.
220 max
= state
->path
.active
- 1;
221 ASSERT((max
>= 0) && (max
< XFS_DA_NODE_MAXDEPTH
));
222 ASSERT(state
->path
.blk
[max
].magic
== XFS_ATTR_LEAF_MAGIC
||
223 state
->path
.blk
[max
].magic
== XFS_DIR2_LEAFN_MAGIC
);
225 addblk
= &state
->path
.blk
[max
]; /* initial dummy value */
226 for (i
= max
; (i
>= 0) && addblk
; state
->path
.active
--, i
--) {
227 oldblk
= &state
->path
.blk
[i
];
228 newblk
= &state
->altpath
.blk
[i
];
231 * If a leaf node then
232 * Allocate a new leaf node, then rebalance across them.
233 * else if an intermediate node then
234 * We split on the last layer, must we split the node?
236 switch (oldblk
->magic
) {
237 case XFS_ATTR_LEAF_MAGIC
:
238 error
= xfs_attr_leaf_split(state
, oldblk
, newblk
);
239 if ((error
!= 0) && (error
!= ENOSPC
)) {
240 return(error
); /* GROT: attr is inconsistent */
247 * Entry wouldn't fit, split the leaf again.
249 state
->extravalid
= 1;
251 state
->extraafter
= 0; /* before newblk */
252 trace_xfs_attr_leaf_split_before(state
->args
);
253 error
= xfs_attr_leaf_split(state
, oldblk
,
256 state
->extraafter
= 1; /* after newblk */
257 trace_xfs_attr_leaf_split_after(state
->args
);
258 error
= xfs_attr_leaf_split(state
, newblk
,
262 return(error
); /* GROT: attr inconsistent */
265 case XFS_DIR2_LEAFN_MAGIC
:
266 error
= xfs_dir2_leafn_split(state
, oldblk
, newblk
);
271 case XFS_DA_NODE_MAGIC
:
272 error
= xfs_da_node_split(state
, oldblk
, newblk
, addblk
,
276 return(error
); /* GROT: dir is inconsistent */
278 * Record the newly split block for the next time thru?
288 * Update the btree to show the new hashval for this child.
290 xfs_da_fixhashpath(state
, &state
->path
);
296 * Split the root node.
298 ASSERT(state
->path
.active
== 0);
299 oldblk
= &state
->path
.blk
[0];
300 error
= xfs_da_root_split(state
, oldblk
, addblk
);
303 return(error
); /* GROT: dir is inconsistent */
307 * Update pointers to the node which used to be block 0 and
308 * just got bumped because of the addition of a new root node.
309 * There might be three blocks involved if a double split occurred,
310 * and the original block 0 could be at any position in the list.
313 node
= oldblk
->bp
->b_addr
;
314 if (node
->hdr
.info
.forw
) {
315 if (be32_to_cpu(node
->hdr
.info
.forw
) == addblk
->blkno
) {
318 ASSERT(state
->extravalid
);
319 bp
= state
->extrablk
.bp
;
322 node
->hdr
.info
.back
= cpu_to_be32(oldblk
->blkno
);
323 xfs_trans_log_buf(state
->args
->trans
, bp
,
324 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
325 sizeof(node
->hdr
.info
)));
327 node
= oldblk
->bp
->b_addr
;
328 if (node
->hdr
.info
.back
) {
329 if (be32_to_cpu(node
->hdr
.info
.back
) == addblk
->blkno
) {
332 ASSERT(state
->extravalid
);
333 bp
= state
->extrablk
.bp
;
336 node
->hdr
.info
.forw
= cpu_to_be32(oldblk
->blkno
);
337 xfs_trans_log_buf(state
->args
->trans
, bp
,
338 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
339 sizeof(node
->hdr
.info
)));
346 * Split the root. We have to create a new root and point to the two
347 * parts (the split old root) that we just created. Copy block zero to
348 * the EOF, extending the inode in process.
350 STATIC
int /* error */
351 xfs_da_root_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
352 xfs_da_state_blk_t
*blk2
)
354 xfs_da_intnode_t
*node
, *oldroot
;
362 xfs_dir2_leaf_t
*leaf
;
364 trace_xfs_da_root_split(state
->args
);
367 * Copy the existing (incorrect) block from the root node position
368 * to a free space somewhere.
371 ASSERT(args
!= NULL
);
372 error
= xfs_da_grow_inode(args
, &blkno
);
378 error
= xfs_da_get_buf(tp
, dp
, blkno
, -1, &bp
, args
->whichfork
);
383 oldroot
= blk1
->bp
->b_addr
;
384 if (oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
)) {
385 size
= (int)((char *)&oldroot
->btree
[be16_to_cpu(oldroot
->hdr
.count
)] -
388 ASSERT(oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
));
389 leaf
= (xfs_dir2_leaf_t
*)oldroot
;
390 size
= (int)((char *)&leaf
->ents
[be16_to_cpu(leaf
->hdr
.count
)] -
393 memcpy(node
, oldroot
, size
);
394 xfs_trans_log_buf(tp
, bp
, 0, size
- 1);
399 * Set up the new root node.
401 error
= xfs_da_node_create(args
,
402 (args
->whichfork
== XFS_DATA_FORK
) ? mp
->m_dirleafblk
: 0,
403 be16_to_cpu(node
->hdr
.level
) + 1, &bp
, args
->whichfork
);
407 node
->btree
[0].hashval
= cpu_to_be32(blk1
->hashval
);
408 node
->btree
[0].before
= cpu_to_be32(blk1
->blkno
);
409 node
->btree
[1].hashval
= cpu_to_be32(blk2
->hashval
);
410 node
->btree
[1].before
= cpu_to_be32(blk2
->blkno
);
411 node
->hdr
.count
= cpu_to_be16(2);
414 if (oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
)) {
415 ASSERT(blk1
->blkno
>= mp
->m_dirleafblk
&&
416 blk1
->blkno
< mp
->m_dirfreeblk
);
417 ASSERT(blk2
->blkno
>= mp
->m_dirleafblk
&&
418 blk2
->blkno
< mp
->m_dirfreeblk
);
422 /* Header is already logged by xfs_da_node_create */
423 xfs_trans_log_buf(tp
, bp
,
424 XFS_DA_LOGRANGE(node
, node
->btree
,
425 sizeof(xfs_da_node_entry_t
) * 2));
431 * Split the node, rebalance, then add the new entry.
433 STATIC
int /* error */
434 xfs_da_node_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
435 xfs_da_state_blk_t
*newblk
,
436 xfs_da_state_blk_t
*addblk
,
437 int treelevel
, int *result
)
439 xfs_da_intnode_t
*node
;
444 trace_xfs_da_node_split(state
->args
);
446 node
= oldblk
->bp
->b_addr
;
447 ASSERT(node
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
450 * With V2 dirs the extra block is data or freespace.
452 useextra
= state
->extravalid
&& state
->args
->whichfork
== XFS_ATTR_FORK
;
453 newcount
= 1 + useextra
;
455 * Do we have to split the node?
457 if ((be16_to_cpu(node
->hdr
.count
) + newcount
) > state
->node_ents
) {
459 * Allocate a new node, add to the doubly linked chain of
460 * nodes, then move some of our excess entries into it.
462 error
= xfs_da_grow_inode(state
->args
, &blkno
);
464 return(error
); /* GROT: dir is inconsistent */
466 error
= xfs_da_node_create(state
->args
, blkno
, treelevel
,
467 &newblk
->bp
, state
->args
->whichfork
);
469 return(error
); /* GROT: dir is inconsistent */
470 newblk
->blkno
= blkno
;
471 newblk
->magic
= XFS_DA_NODE_MAGIC
;
472 xfs_da_node_rebalance(state
, oldblk
, newblk
);
473 error
= xfs_da_blk_link(state
, oldblk
, newblk
);
482 * Insert the new entry(s) into the correct block
483 * (updating last hashval in the process).
485 * xfs_da_node_add() inserts BEFORE the given index,
486 * and as a result of using node_lookup_int() we always
487 * point to a valid entry (not after one), but a split
488 * operation always results in a new block whose hashvals
489 * FOLLOW the current block.
491 * If we had double-split op below us, then add the extra block too.
493 node
= oldblk
->bp
->b_addr
;
494 if (oldblk
->index
<= be16_to_cpu(node
->hdr
.count
)) {
496 xfs_da_node_add(state
, oldblk
, addblk
);
498 if (state
->extraafter
)
500 xfs_da_node_add(state
, oldblk
, &state
->extrablk
);
501 state
->extravalid
= 0;
505 xfs_da_node_add(state
, newblk
, addblk
);
507 if (state
->extraafter
)
509 xfs_da_node_add(state
, newblk
, &state
->extrablk
);
510 state
->extravalid
= 0;
518 * Balance the btree elements between two intermediate nodes,
519 * usually one full and one empty.
521 * NOTE: if blk2 is empty, then it will get the upper half of blk1.
524 xfs_da_node_rebalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
525 xfs_da_state_blk_t
*blk2
)
527 xfs_da_intnode_t
*node1
, *node2
, *tmpnode
;
528 xfs_da_node_entry_t
*btree_s
, *btree_d
;
532 trace_xfs_da_node_rebalance(state
->args
);
534 node1
= blk1
->bp
->b_addr
;
535 node2
= blk2
->bp
->b_addr
;
537 * Figure out how many entries need to move, and in which direction.
538 * Swap the nodes around if that makes it simpler.
540 if ((be16_to_cpu(node1
->hdr
.count
) > 0) && (be16_to_cpu(node2
->hdr
.count
) > 0) &&
541 ((be32_to_cpu(node2
->btree
[0].hashval
) < be32_to_cpu(node1
->btree
[0].hashval
)) ||
542 (be32_to_cpu(node2
->btree
[be16_to_cpu(node2
->hdr
.count
)-1].hashval
) <
543 be32_to_cpu(node1
->btree
[be16_to_cpu(node1
->hdr
.count
)-1].hashval
)))) {
548 ASSERT(node1
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
549 ASSERT(node2
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
550 count
= (be16_to_cpu(node1
->hdr
.count
) - be16_to_cpu(node2
->hdr
.count
)) / 2;
553 tp
= state
->args
->trans
;
555 * Two cases: high-to-low and low-to-high.
559 * Move elements in node2 up to make a hole.
561 if ((tmp
= be16_to_cpu(node2
->hdr
.count
)) > 0) {
562 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
563 btree_s
= &node2
->btree
[0];
564 btree_d
= &node2
->btree
[count
];
565 memmove(btree_d
, btree_s
, tmp
);
569 * Move the req'd B-tree elements from high in node1 to
572 be16_add_cpu(&node2
->hdr
.count
, count
);
573 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
574 btree_s
= &node1
->btree
[be16_to_cpu(node1
->hdr
.count
) - count
];
575 btree_d
= &node2
->btree
[0];
576 memcpy(btree_d
, btree_s
, tmp
);
577 be16_add_cpu(&node1
->hdr
.count
, -count
);
580 * Move the req'd B-tree elements from low in node2 to
584 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
585 btree_s
= &node2
->btree
[0];
586 btree_d
= &node1
->btree
[be16_to_cpu(node1
->hdr
.count
)];
587 memcpy(btree_d
, btree_s
, tmp
);
588 be16_add_cpu(&node1
->hdr
.count
, count
);
589 xfs_trans_log_buf(tp
, blk1
->bp
,
590 XFS_DA_LOGRANGE(node1
, btree_d
, tmp
));
593 * Move elements in node2 down to fill the hole.
595 tmp
= be16_to_cpu(node2
->hdr
.count
) - count
;
596 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
597 btree_s
= &node2
->btree
[count
];
598 btree_d
= &node2
->btree
[0];
599 memmove(btree_d
, btree_s
, tmp
);
600 be16_add_cpu(&node2
->hdr
.count
, -count
);
604 * Log header of node 1 and all current bits of node 2.
606 xfs_trans_log_buf(tp
, blk1
->bp
,
607 XFS_DA_LOGRANGE(node1
, &node1
->hdr
, sizeof(node1
->hdr
)));
608 xfs_trans_log_buf(tp
, blk2
->bp
,
609 XFS_DA_LOGRANGE(node2
, &node2
->hdr
,
611 sizeof(node2
->btree
[0]) * be16_to_cpu(node2
->hdr
.count
)));
614 * Record the last hashval from each block for upward propagation.
615 * (note: don't use the swapped node pointers)
617 node1
= blk1
->bp
->b_addr
;
618 node2
= blk2
->bp
->b_addr
;
619 blk1
->hashval
= be32_to_cpu(node1
->btree
[be16_to_cpu(node1
->hdr
.count
)-1].hashval
);
620 blk2
->hashval
= be32_to_cpu(node2
->btree
[be16_to_cpu(node2
->hdr
.count
)-1].hashval
);
623 * Adjust the expected index for insertion.
625 if (blk1
->index
>= be16_to_cpu(node1
->hdr
.count
)) {
626 blk2
->index
= blk1
->index
- be16_to_cpu(node1
->hdr
.count
);
627 blk1
->index
= be16_to_cpu(node1
->hdr
.count
) + 1; /* make it invalid */
632 * Add a new entry to an intermediate node.
635 xfs_da_node_add(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
636 xfs_da_state_blk_t
*newblk
)
638 xfs_da_intnode_t
*node
;
639 xfs_da_node_entry_t
*btree
;
642 trace_xfs_da_node_add(state
->args
);
644 node
= oldblk
->bp
->b_addr
;
645 ASSERT(node
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
646 ASSERT((oldblk
->index
>= 0) && (oldblk
->index
<= be16_to_cpu(node
->hdr
.count
)));
647 ASSERT(newblk
->blkno
!= 0);
648 if (state
->args
->whichfork
== XFS_DATA_FORK
)
649 ASSERT(newblk
->blkno
>= state
->mp
->m_dirleafblk
&&
650 newblk
->blkno
< state
->mp
->m_dirfreeblk
);
653 * We may need to make some room before we insert the new node.
656 btree
= &node
->btree
[ oldblk
->index
];
657 if (oldblk
->index
< be16_to_cpu(node
->hdr
.count
)) {
658 tmp
= (be16_to_cpu(node
->hdr
.count
) - oldblk
->index
) * (uint
)sizeof(*btree
);
659 memmove(btree
+ 1, btree
, tmp
);
661 btree
->hashval
= cpu_to_be32(newblk
->hashval
);
662 btree
->before
= cpu_to_be32(newblk
->blkno
);
663 xfs_trans_log_buf(state
->args
->trans
, oldblk
->bp
,
664 XFS_DA_LOGRANGE(node
, btree
, tmp
+ sizeof(*btree
)));
665 be16_add_cpu(&node
->hdr
.count
, 1);
666 xfs_trans_log_buf(state
->args
->trans
, oldblk
->bp
,
667 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
670 * Copy the last hash value from the oldblk to propagate upwards.
672 oldblk
->hashval
= be32_to_cpu(node
->btree
[be16_to_cpu(node
->hdr
.count
)-1 ].hashval
);
675 /*========================================================================
676 * Routines used for shrinking the Btree.
677 *========================================================================*/
680 * Deallocate an empty leaf node, remove it from its parent,
681 * possibly deallocating that block, etc...
684 xfs_da_join(xfs_da_state_t
*state
)
686 xfs_da_state_blk_t
*drop_blk
, *save_blk
;
689 trace_xfs_da_join(state
->args
);
692 drop_blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
693 save_blk
= &state
->altpath
.blk
[ state
->path
.active
-1 ];
694 ASSERT(state
->path
.blk
[0].magic
== XFS_DA_NODE_MAGIC
);
695 ASSERT(drop_blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
696 drop_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
699 * Walk back up the tree joining/deallocating as necessary.
700 * When we stop dropping blocks, break out.
702 for ( ; state
->path
.active
>= 2; drop_blk
--, save_blk
--,
703 state
->path
.active
--) {
705 * See if we can combine the block with a neighbor.
706 * (action == 0) => no options, just leave
707 * (action == 1) => coalesce, then unlink
708 * (action == 2) => block empty, unlink it
710 switch (drop_blk
->magic
) {
711 case XFS_ATTR_LEAF_MAGIC
:
712 error
= xfs_attr_leaf_toosmall(state
, &action
);
717 xfs_attr_leaf_unbalance(state
, drop_blk
, save_blk
);
719 case XFS_DIR2_LEAFN_MAGIC
:
720 error
= xfs_dir2_leafn_toosmall(state
, &action
);
725 xfs_dir2_leafn_unbalance(state
, drop_blk
, save_blk
);
727 case XFS_DA_NODE_MAGIC
:
729 * Remove the offending node, fixup hashvals,
730 * check for a toosmall neighbor.
732 xfs_da_node_remove(state
, drop_blk
);
733 xfs_da_fixhashpath(state
, &state
->path
);
734 error
= xfs_da_node_toosmall(state
, &action
);
739 xfs_da_node_unbalance(state
, drop_blk
, save_blk
);
742 xfs_da_fixhashpath(state
, &state
->altpath
);
743 error
= xfs_da_blk_unlink(state
, drop_blk
, save_blk
);
744 xfs_da_state_kill_altpath(state
);
747 error
= xfs_da_shrink_inode(state
->args
, drop_blk
->blkno
,
754 * We joined all the way to the top. If it turns out that
755 * we only have one entry in the root, make the child block
758 xfs_da_node_remove(state
, drop_blk
);
759 xfs_da_fixhashpath(state
, &state
->path
);
760 error
= xfs_da_root_join(state
, &state
->path
.blk
[0]);
766 xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo
*blkinfo
, __u16 level
)
768 __be16 magic
= blkinfo
->magic
;
771 ASSERT(magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
) ||
772 magic
== cpu_to_be16(XFS_ATTR_LEAF_MAGIC
));
774 ASSERT(magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
775 ASSERT(!blkinfo
->forw
);
776 ASSERT(!blkinfo
->back
);
779 #define xfs_da_blkinfo_onlychild_validate(blkinfo, level)
783 * We have only one entry in the root. Copy the only remaining child of
784 * the old root to block 0 as the new root node.
787 xfs_da_root_join(xfs_da_state_t
*state
, xfs_da_state_blk_t
*root_blk
)
789 xfs_da_intnode_t
*oldroot
;
795 trace_xfs_da_root_join(state
->args
);
798 ASSERT(args
!= NULL
);
799 ASSERT(root_blk
->magic
== XFS_DA_NODE_MAGIC
);
800 oldroot
= root_blk
->bp
->b_addr
;
801 ASSERT(oldroot
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
802 ASSERT(!oldroot
->hdr
.info
.forw
);
803 ASSERT(!oldroot
->hdr
.info
.back
);
806 * If the root has more than one child, then don't do anything.
808 if (be16_to_cpu(oldroot
->hdr
.count
) > 1)
812 * Read in the (only) child block, then copy those bytes into
813 * the root block's buffer and free the original child block.
815 child
= be32_to_cpu(oldroot
->btree
[0].before
);
817 error
= xfs_da_node_read(args
->trans
, args
->dp
, child
, -1, &bp
,
822 xfs_da_blkinfo_onlychild_validate(bp
->b_addr
,
823 be16_to_cpu(oldroot
->hdr
.level
));
826 * This could be copying a leaf back into the root block in the case of
827 * there only being a single leaf block left in the tree. Hence we have
828 * to update the pre_io pointer as well to match the buffer type change
831 memcpy(root_blk
->bp
->b_addr
, bp
->b_addr
, state
->blocksize
);
832 root_blk
->bp
->b_pre_io
= bp
->b_pre_io
;
833 xfs_trans_log_buf(args
->trans
, root_blk
->bp
, 0, state
->blocksize
- 1);
834 error
= xfs_da_shrink_inode(args
, child
, bp
);
839 * Check a node block and its neighbors to see if the block should be
840 * collapsed into one or the other neighbor. Always keep the block
841 * with the smaller block number.
842 * If the current block is over 50% full, don't try to join it, return 0.
843 * If the block is empty, fill in the state structure and return 2.
844 * If it can be collapsed, fill in the state structure and return 1.
845 * If nothing can be done, return 0.
848 xfs_da_node_toosmall(xfs_da_state_t
*state
, int *action
)
850 xfs_da_intnode_t
*node
;
851 xfs_da_state_blk_t
*blk
;
852 xfs_da_blkinfo_t
*info
;
853 int count
, forward
, error
, retval
, i
;
857 trace_xfs_da_node_toosmall(state
->args
);
860 * Check for the degenerate case of the block being over 50% full.
861 * If so, it's not worth even looking to see if we might be able
862 * to coalesce with a sibling.
864 blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
865 info
= blk
->bp
->b_addr
;
866 ASSERT(info
->magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
867 node
= (xfs_da_intnode_t
*)info
;
868 count
= be16_to_cpu(node
->hdr
.count
);
869 if (count
> (state
->node_ents
>> 1)) {
870 *action
= 0; /* blk over 50%, don't try to join */
871 return(0); /* blk over 50%, don't try to join */
875 * Check for the degenerate case of the block being empty.
876 * If the block is empty, we'll simply delete it, no need to
877 * coalesce it with a sibling block. We choose (arbitrarily)
878 * to merge with the forward block unless it is NULL.
882 * Make altpath point to the block we want to keep and
883 * path point to the block we want to drop (this one).
885 forward
= (info
->forw
!= 0);
886 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
887 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
900 * Examine each sibling block to see if we can coalesce with
901 * at least 25% free space to spare. We need to figure out
902 * whether to merge with the forward or the backward block.
903 * We prefer coalescing with the lower numbered sibling so as
904 * to shrink a directory over time.
906 /* start with smaller blk num */
907 forward
= (be32_to_cpu(info
->forw
) < be32_to_cpu(info
->back
));
908 for (i
= 0; i
< 2; forward
= !forward
, i
++) {
910 blkno
= be32_to_cpu(info
->forw
);
912 blkno
= be32_to_cpu(info
->back
);
915 error
= xfs_da_node_read(state
->args
->trans
, state
->args
->dp
,
916 blkno
, -1, &bp
, state
->args
->whichfork
);
921 node
= (xfs_da_intnode_t
*)info
;
922 count
= state
->node_ents
;
923 count
-= state
->node_ents
>> 2;
924 count
-= be16_to_cpu(node
->hdr
.count
);
926 ASSERT(node
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
927 count
-= be16_to_cpu(node
->hdr
.count
);
928 xfs_trans_brelse(state
->args
->trans
, bp
);
930 break; /* fits with at least 25% to spare */
938 * Make altpath point to the block we want to keep (the lower
939 * numbered block) and path point to the block we want to drop.
941 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
942 if (blkno
< blk
->blkno
) {
943 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
953 error
= xfs_da_path_shift(state
, &state
->path
, forward
,
968 * Walk back up the tree adjusting hash values as necessary,
969 * when we stop making changes, return.
972 xfs_da_fixhashpath(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
)
974 xfs_da_state_blk_t
*blk
;
975 xfs_da_intnode_t
*node
;
976 xfs_da_node_entry_t
*btree
;
977 xfs_dahash_t lasthash
=0;
980 trace_xfs_da_fixhashpath(state
->args
);
982 level
= path
->active
-1;
983 blk
= &path
->blk
[ level
];
984 switch (blk
->magic
) {
985 case XFS_ATTR_LEAF_MAGIC
:
986 lasthash
= xfs_attr_leaf_lasthash(blk
->bp
, &count
);
990 case XFS_DIR2_LEAFN_MAGIC
:
991 lasthash
= xfs_dir2_leafn_lasthash(blk
->bp
, &count
);
995 case XFS_DA_NODE_MAGIC
:
996 lasthash
= xfs_da_node_lasthash(blk
->bp
, &count
);
1001 for (blk
--, level
--; level
>= 0; blk
--, level
--) {
1002 node
= blk
->bp
->b_addr
;
1003 ASSERT(node
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
1004 btree
= &node
->btree
[ blk
->index
];
1005 if (be32_to_cpu(btree
->hashval
) == lasthash
)
1007 blk
->hashval
= lasthash
;
1008 btree
->hashval
= cpu_to_be32(lasthash
);
1009 xfs_trans_log_buf(state
->args
->trans
, blk
->bp
,
1010 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
1012 lasthash
= be32_to_cpu(node
->btree
[be16_to_cpu(node
->hdr
.count
)-1].hashval
);
1017 * Remove an entry from an intermediate node.
1020 xfs_da_node_remove(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
)
1022 xfs_da_intnode_t
*node
;
1023 xfs_da_node_entry_t
*btree
;
1026 trace_xfs_da_node_remove(state
->args
);
1028 node
= drop_blk
->bp
->b_addr
;
1029 ASSERT(drop_blk
->index
< be16_to_cpu(node
->hdr
.count
));
1030 ASSERT(drop_blk
->index
>= 0);
1033 * Copy over the offending entry, or just zero it out.
1035 btree
= &node
->btree
[drop_blk
->index
];
1036 if (drop_blk
->index
< (be16_to_cpu(node
->hdr
.count
)-1)) {
1037 tmp
= be16_to_cpu(node
->hdr
.count
) - drop_blk
->index
- 1;
1038 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
1039 memmove(btree
, btree
+ 1, tmp
);
1040 xfs_trans_log_buf(state
->args
->trans
, drop_blk
->bp
,
1041 XFS_DA_LOGRANGE(node
, btree
, tmp
));
1042 btree
= &node
->btree
[be16_to_cpu(node
->hdr
.count
)-1];
1044 memset((char *)btree
, 0, sizeof(xfs_da_node_entry_t
));
1045 xfs_trans_log_buf(state
->args
->trans
, drop_blk
->bp
,
1046 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
1047 be16_add_cpu(&node
->hdr
.count
, -1);
1048 xfs_trans_log_buf(state
->args
->trans
, drop_blk
->bp
,
1049 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
1052 * Copy the last hash value from the block to propagate upwards.
1055 drop_blk
->hashval
= be32_to_cpu(btree
->hashval
);
1059 * Unbalance the btree elements between two intermediate nodes,
1060 * move all Btree elements from one node into another.
1063 xfs_da_node_unbalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
1064 xfs_da_state_blk_t
*save_blk
)
1066 xfs_da_intnode_t
*drop_node
, *save_node
;
1067 xfs_da_node_entry_t
*btree
;
1071 trace_xfs_da_node_unbalance(state
->args
);
1073 drop_node
= drop_blk
->bp
->b_addr
;
1074 save_node
= save_blk
->bp
->b_addr
;
1075 ASSERT(drop_node
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
1076 ASSERT(save_node
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
1077 tp
= state
->args
->trans
;
1080 * If the dying block has lower hashvals, then move all the
1081 * elements in the remaining block up to make a hole.
1083 if ((be32_to_cpu(drop_node
->btree
[0].hashval
) < be32_to_cpu(save_node
->btree
[ 0 ].hashval
)) ||
1084 (be32_to_cpu(drop_node
->btree
[be16_to_cpu(drop_node
->hdr
.count
)-1].hashval
) <
1085 be32_to_cpu(save_node
->btree
[be16_to_cpu(save_node
->hdr
.count
)-1].hashval
)))
1087 btree
= &save_node
->btree
[be16_to_cpu(drop_node
->hdr
.count
)];
1088 tmp
= be16_to_cpu(save_node
->hdr
.count
) * (uint
)sizeof(xfs_da_node_entry_t
);
1089 memmove(btree
, &save_node
->btree
[0], tmp
);
1090 btree
= &save_node
->btree
[0];
1091 xfs_trans_log_buf(tp
, save_blk
->bp
,
1092 XFS_DA_LOGRANGE(save_node
, btree
,
1093 (be16_to_cpu(save_node
->hdr
.count
) + be16_to_cpu(drop_node
->hdr
.count
)) *
1094 sizeof(xfs_da_node_entry_t
)));
1096 btree
= &save_node
->btree
[be16_to_cpu(save_node
->hdr
.count
)];
1097 xfs_trans_log_buf(tp
, save_blk
->bp
,
1098 XFS_DA_LOGRANGE(save_node
, btree
,
1099 be16_to_cpu(drop_node
->hdr
.count
) *
1100 sizeof(xfs_da_node_entry_t
)));
1104 * Move all the B-tree elements from drop_blk to save_blk.
1106 tmp
= be16_to_cpu(drop_node
->hdr
.count
) * (uint
)sizeof(xfs_da_node_entry_t
);
1107 memcpy(btree
, &drop_node
->btree
[0], tmp
);
1108 be16_add_cpu(&save_node
->hdr
.count
, be16_to_cpu(drop_node
->hdr
.count
));
1110 xfs_trans_log_buf(tp
, save_blk
->bp
,
1111 XFS_DA_LOGRANGE(save_node
, &save_node
->hdr
,
1112 sizeof(save_node
->hdr
)));
1115 * Save the last hashval in the remaining block for upward propagation.
1117 save_blk
->hashval
= be32_to_cpu(save_node
->btree
[be16_to_cpu(save_node
->hdr
.count
)-1].hashval
);
1120 /*========================================================================
1121 * Routines used for finding things in the Btree.
1122 *========================================================================*/
1125 * Walk down the Btree looking for a particular filename, filling
1126 * in the state structure as we go.
1128 * We will set the state structure to point to each of the elements
1129 * in each of the nodes where either the hashval is or should be.
1131 * We support duplicate hashval's so for each entry in the current
1132 * node that could contain the desired hashval, descend. This is a
1133 * pruned depth-first tree search.
1136 xfs_da_node_lookup_int(xfs_da_state_t
*state
, int *result
)
1138 xfs_da_state_blk_t
*blk
;
1139 xfs_da_blkinfo_t
*curr
;
1140 xfs_da_intnode_t
*node
;
1141 xfs_da_node_entry_t
*btree
;
1143 int probe
, span
, max
, error
, retval
;
1144 xfs_dahash_t hashval
, btreehashval
;
1145 xfs_da_args_t
*args
;
1150 * Descend thru the B-tree searching each level for the right
1151 * node to use, until the right hashval is found.
1153 blkno
= (args
->whichfork
== XFS_DATA_FORK
)? state
->mp
->m_dirleafblk
: 0;
1154 for (blk
= &state
->path
.blk
[0], state
->path
.active
= 1;
1155 state
->path
.active
<= XFS_DA_NODE_MAXDEPTH
;
1156 blk
++, state
->path
.active
++) {
1158 * Read the next node down in the tree.
1161 error
= xfs_da_node_read(args
->trans
, args
->dp
, blkno
,
1162 -1, &blk
->bp
, args
->whichfork
);
1165 state
->path
.active
--;
1168 curr
= blk
->bp
->b_addr
;
1169 blk
->magic
= be16_to_cpu(curr
->magic
);
1170 ASSERT(blk
->magic
== XFS_DA_NODE_MAGIC
||
1171 blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1172 blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1175 * Search an intermediate node for a match.
1177 if (blk
->magic
== XFS_DA_NODE_MAGIC
) {
1178 node
= blk
->bp
->b_addr
;
1179 max
= be16_to_cpu(node
->hdr
.count
);
1180 blk
->hashval
= be32_to_cpu(node
->btree
[max
-1].hashval
);
1183 * Binary search. (note: small blocks will skip loop)
1185 probe
= span
= max
/ 2;
1186 hashval
= args
->hashval
;
1187 for (btree
= &node
->btree
[probe
]; span
> 4;
1188 btree
= &node
->btree
[probe
]) {
1190 btreehashval
= be32_to_cpu(btree
->hashval
);
1191 if (btreehashval
< hashval
)
1193 else if (btreehashval
> hashval
)
1198 ASSERT((probe
>= 0) && (probe
< max
));
1199 ASSERT((span
<= 4) || (be32_to_cpu(btree
->hashval
) == hashval
));
1202 * Since we may have duplicate hashval's, find the first
1203 * matching hashval in the node.
1205 while ((probe
> 0) && (be32_to_cpu(btree
->hashval
) >= hashval
)) {
1209 while ((probe
< max
) && (be32_to_cpu(btree
->hashval
) < hashval
)) {
1215 * Pick the right block to descend on.
1219 blkno
= be32_to_cpu(node
->btree
[max
-1].before
);
1222 blkno
= be32_to_cpu(btree
->before
);
1224 } else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1225 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
, NULL
);
1227 } else if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
) {
1228 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
, NULL
);
1234 * A leaf block that ends in the hashval that we are interested in
1235 * (final hashval == search hashval) means that the next block may
1236 * contain more entries with the same hashval, shift upward to the
1237 * next leaf and keep searching.
1240 if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
) {
1241 retval
= xfs_dir2_leafn_lookup_int(blk
->bp
, args
,
1242 &blk
->index
, state
);
1243 } else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1244 retval
= xfs_attr_leaf_lookup_int(blk
->bp
, args
);
1245 blk
->index
= args
->index
;
1246 args
->blkno
= blk
->blkno
;
1249 return XFS_ERROR(EFSCORRUPTED
);
1251 if (((retval
== ENOENT
) || (retval
== ENOATTR
)) &&
1252 (blk
->hashval
== args
->hashval
)) {
1253 error
= xfs_da_path_shift(state
, &state
->path
, 1, 1,
1259 } else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1260 /* path_shift() gives ENOENT */
1261 retval
= XFS_ERROR(ENOATTR
);
1270 /*========================================================================
1272 *========================================================================*/
1275 * Link a new block into a doubly linked list of blocks (of whatever type).
1278 xfs_da_blk_link(xfs_da_state_t
*state
, xfs_da_state_blk_t
*old_blk
,
1279 xfs_da_state_blk_t
*new_blk
)
1281 xfs_da_blkinfo_t
*old_info
, *new_info
, *tmp_info
;
1282 xfs_da_args_t
*args
;
1283 int before
=0, error
;
1287 * Set up environment.
1290 ASSERT(args
!= NULL
);
1291 old_info
= old_blk
->bp
->b_addr
;
1292 new_info
= new_blk
->bp
->b_addr
;
1293 ASSERT(old_blk
->magic
== XFS_DA_NODE_MAGIC
||
1294 old_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1295 old_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1296 ASSERT(old_blk
->magic
== be16_to_cpu(old_info
->magic
));
1297 ASSERT(new_blk
->magic
== be16_to_cpu(new_info
->magic
));
1298 ASSERT(old_blk
->magic
== new_blk
->magic
);
1300 switch (old_blk
->magic
) {
1301 case XFS_ATTR_LEAF_MAGIC
:
1302 before
= xfs_attr_leaf_order(old_blk
->bp
, new_blk
->bp
);
1304 case XFS_DIR2_LEAFN_MAGIC
:
1305 before
= xfs_dir2_leafn_order(old_blk
->bp
, new_blk
->bp
);
1307 case XFS_DA_NODE_MAGIC
:
1308 before
= xfs_da_node_order(old_blk
->bp
, new_blk
->bp
);
1313 * Link blocks in appropriate order.
1317 * Link new block in before existing block.
1319 trace_xfs_da_link_before(args
);
1320 new_info
->forw
= cpu_to_be32(old_blk
->blkno
);
1321 new_info
->back
= old_info
->back
;
1322 if (old_info
->back
) {
1323 error
= xfs_da_node_read(args
->trans
, args
->dp
,
1324 be32_to_cpu(old_info
->back
),
1325 -1, &bp
, args
->whichfork
);
1329 tmp_info
= bp
->b_addr
;
1330 ASSERT(be16_to_cpu(tmp_info
->magic
) == be16_to_cpu(old_info
->magic
));
1331 ASSERT(be32_to_cpu(tmp_info
->forw
) == old_blk
->blkno
);
1332 tmp_info
->forw
= cpu_to_be32(new_blk
->blkno
);
1333 xfs_trans_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1335 old_info
->back
= cpu_to_be32(new_blk
->blkno
);
1338 * Link new block in after existing block.
1340 trace_xfs_da_link_after(args
);
1341 new_info
->forw
= old_info
->forw
;
1342 new_info
->back
= cpu_to_be32(old_blk
->blkno
);
1343 if (old_info
->forw
) {
1344 error
= xfs_da_node_read(args
->trans
, args
->dp
,
1345 be32_to_cpu(old_info
->forw
),
1346 -1, &bp
, args
->whichfork
);
1350 tmp_info
= bp
->b_addr
;
1351 ASSERT(tmp_info
->magic
== old_info
->magic
);
1352 ASSERT(be32_to_cpu(tmp_info
->back
) == old_blk
->blkno
);
1353 tmp_info
->back
= cpu_to_be32(new_blk
->blkno
);
1354 xfs_trans_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1356 old_info
->forw
= cpu_to_be32(new_blk
->blkno
);
1359 xfs_trans_log_buf(args
->trans
, old_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1360 xfs_trans_log_buf(args
->trans
, new_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1365 * Compare two intermediate nodes for "order".
1369 struct xfs_buf
*node1_bp
,
1370 struct xfs_buf
*node2_bp
)
1372 xfs_da_intnode_t
*node1
, *node2
;
1374 node1
= node1_bp
->b_addr
;
1375 node2
= node2_bp
->b_addr
;
1376 ASSERT(node1
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
) &&
1377 node2
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
1378 if ((be16_to_cpu(node1
->hdr
.count
) > 0) && (be16_to_cpu(node2
->hdr
.count
) > 0) &&
1379 ((be32_to_cpu(node2
->btree
[0].hashval
) <
1380 be32_to_cpu(node1
->btree
[0].hashval
)) ||
1381 (be32_to_cpu(node2
->btree
[be16_to_cpu(node2
->hdr
.count
)-1].hashval
) <
1382 be32_to_cpu(node1
->btree
[be16_to_cpu(node1
->hdr
.count
)-1].hashval
)))) {
1389 * Pick up the last hashvalue from an intermediate node.
1392 xfs_da_node_lasthash(
1396 xfs_da_intnode_t
*node
;
1399 ASSERT(node
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
1401 *count
= be16_to_cpu(node
->hdr
.count
);
1402 if (!node
->hdr
.count
)
1404 return be32_to_cpu(node
->btree
[be16_to_cpu(node
->hdr
.count
)-1].hashval
);
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
->b_addr
;
1425 drop_info
= drop_blk
->bp
->b_addr
;
1426 ASSERT(save_blk
->magic
== XFS_DA_NODE_MAGIC
||
1427 save_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1428 save_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1429 ASSERT(save_blk
->magic
== be16_to_cpu(save_info
->magic
));
1430 ASSERT(drop_blk
->magic
== be16_to_cpu(drop_info
->magic
));
1431 ASSERT(save_blk
->magic
== drop_blk
->magic
);
1432 ASSERT((be32_to_cpu(save_info
->forw
) == drop_blk
->blkno
) ||
1433 (be32_to_cpu(save_info
->back
) == drop_blk
->blkno
));
1434 ASSERT((be32_to_cpu(drop_info
->forw
) == save_blk
->blkno
) ||
1435 (be32_to_cpu(drop_info
->back
) == save_blk
->blkno
));
1438 * Unlink the leaf block from the doubly linked chain of leaves.
1440 if (be32_to_cpu(save_info
->back
) == drop_blk
->blkno
) {
1441 trace_xfs_da_unlink_back(args
);
1442 save_info
->back
= drop_info
->back
;
1443 if (drop_info
->back
) {
1444 error
= xfs_da_node_read(args
->trans
, args
->dp
,
1445 be32_to_cpu(drop_info
->back
),
1446 -1, &bp
, args
->whichfork
);
1450 tmp_info
= bp
->b_addr
;
1451 ASSERT(tmp_info
->magic
== save_info
->magic
);
1452 ASSERT(be32_to_cpu(tmp_info
->forw
) == drop_blk
->blkno
);
1453 tmp_info
->forw
= cpu_to_be32(save_blk
->blkno
);
1454 xfs_trans_log_buf(args
->trans
, bp
, 0,
1455 sizeof(*tmp_info
) - 1);
1458 trace_xfs_da_unlink_forward(args
);
1459 save_info
->forw
= drop_info
->forw
;
1460 if (drop_info
->forw
) {
1461 error
= xfs_da_node_read(args
->trans
, args
->dp
,
1462 be32_to_cpu(drop_info
->forw
),
1463 -1, &bp
, args
->whichfork
);
1467 tmp_info
= bp
->b_addr
;
1468 ASSERT(tmp_info
->magic
== save_info
->magic
);
1469 ASSERT(be32_to_cpu(tmp_info
->back
) == drop_blk
->blkno
);
1470 tmp_info
->back
= cpu_to_be32(save_blk
->blkno
);
1471 xfs_trans_log_buf(args
->trans
, bp
, 0,
1472 sizeof(*tmp_info
) - 1);
1476 xfs_trans_log_buf(args
->trans
, save_blk
->bp
, 0, sizeof(*save_info
) - 1);
1481 * Move a path "forward" or "!forward" one block at the current level.
1483 * This routine will adjust a "path" to point to the next block
1484 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1485 * Btree, including updating pointers to the intermediate nodes between
1486 * the new bottom and the root.
1489 xfs_da_path_shift(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
,
1490 int forward
, int release
, int *result
)
1492 xfs_da_state_blk_t
*blk
;
1493 xfs_da_blkinfo_t
*info
;
1494 xfs_da_intnode_t
*node
;
1495 xfs_da_args_t
*args
;
1496 xfs_dablk_t blkno
=0;
1499 trace_xfs_da_path_shift(state
->args
);
1502 * Roll up the Btree looking for the first block where our
1503 * current index is not at the edge of the block. Note that
1504 * we skip the bottom layer because we want the sibling block.
1507 ASSERT(args
!= NULL
);
1508 ASSERT(path
!= NULL
);
1509 ASSERT((path
->active
> 0) && (path
->active
< XFS_DA_NODE_MAXDEPTH
));
1510 level
= (path
->active
-1) - 1; /* skip bottom layer in path */
1511 for (blk
= &path
->blk
[level
]; level
>= 0; blk
--, level
--) {
1512 ASSERT(blk
->bp
!= NULL
);
1513 node
= blk
->bp
->b_addr
;
1514 ASSERT(node
->hdr
.info
.magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
1515 if (forward
&& (blk
->index
< be16_to_cpu(node
->hdr
.count
)-1)) {
1517 blkno
= be32_to_cpu(node
->btree
[blk
->index
].before
);
1519 } else if (!forward
&& (blk
->index
> 0)) {
1521 blkno
= be32_to_cpu(node
->btree
[blk
->index
].before
);
1526 *result
= XFS_ERROR(ENOENT
); /* we're out of our tree */
1527 ASSERT(args
->op_flags
& XFS_DA_OP_OKNOENT
);
1532 * Roll down the edge of the subtree until we reach the
1533 * same depth we were at originally.
1535 for (blk
++, level
++; level
< path
->active
; blk
++, level
++) {
1537 * Release the old block.
1538 * (if it's dirty, trans won't actually let go)
1541 xfs_trans_brelse(args
->trans
, blk
->bp
);
1544 * Read the next child block.
1547 error
= xfs_da_node_read(args
->trans
, args
->dp
, blkno
, -1,
1548 &blk
->bp
, args
->whichfork
);
1551 ASSERT(blk
->bp
!= NULL
);
1552 info
= blk
->bp
->b_addr
;
1553 ASSERT(info
->magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
) ||
1554 info
->magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
) ||
1555 info
->magic
== cpu_to_be16(XFS_ATTR_LEAF_MAGIC
));
1556 blk
->magic
= be16_to_cpu(info
->magic
);
1557 if (blk
->magic
== XFS_DA_NODE_MAGIC
) {
1558 node
= (xfs_da_intnode_t
*)info
;
1559 blk
->hashval
= be32_to_cpu(node
->btree
[be16_to_cpu(node
->hdr
.count
)-1].hashval
);
1563 blk
->index
= be16_to_cpu(node
->hdr
.count
)-1;
1564 blkno
= be32_to_cpu(node
->btree
[blk
->index
].before
);
1566 ASSERT(level
== path
->active
-1);
1568 switch(blk
->magic
) {
1569 case XFS_ATTR_LEAF_MAGIC
:
1570 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
,
1573 case XFS_DIR2_LEAFN_MAGIC
:
1574 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
,
1578 ASSERT(blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
1579 blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1589 /*========================================================================
1591 *========================================================================*/
1594 * Implement a simple hash on a character string.
1595 * Rotate the hash value by 7 bits, then XOR each character in.
1596 * This is implemented with some source-level loop unrolling.
1599 xfs_da_hashname(const __uint8_t
*name
, int namelen
)
1604 * Do four characters at a time as long as we can.
1606 for (hash
= 0; namelen
>= 4; namelen
-= 4, name
+= 4)
1607 hash
= (name
[0] << 21) ^ (name
[1] << 14) ^ (name
[2] << 7) ^
1608 (name
[3] << 0) ^ rol32(hash
, 7 * 4);
1611 * Now do the rest of the characters.
1615 return (name
[0] << 14) ^ (name
[1] << 7) ^ (name
[2] << 0) ^
1618 return (name
[0] << 7) ^ (name
[1] << 0) ^ rol32(hash
, 7 * 2);
1620 return (name
[0] << 0) ^ rol32(hash
, 7 * 1);
1621 default: /* case 0: */
1628 struct xfs_da_args
*args
,
1629 const unsigned char *name
,
1632 return (args
->namelen
== len
&& memcmp(args
->name
, name
, len
) == 0) ?
1633 XFS_CMP_EXACT
: XFS_CMP_DIFFERENT
;
1637 xfs_default_hashname(
1638 struct xfs_name
*name
)
1640 return xfs_da_hashname(name
->name
, name
->len
);
1643 const struct xfs_nameops xfs_default_nameops
= {
1644 .hashname
= xfs_default_hashname
,
1645 .compname
= xfs_da_compname
1649 xfs_da_grow_inode_int(
1650 struct xfs_da_args
*args
,
1654 struct xfs_trans
*tp
= args
->trans
;
1655 struct xfs_inode
*dp
= args
->dp
;
1656 int w
= args
->whichfork
;
1657 xfs_drfsbno_t nblks
= dp
->i_d
.di_nblocks
;
1658 struct xfs_bmbt_irec map
, *mapp
;
1659 int nmap
, error
, got
, i
, mapi
;
1662 * Find a spot in the file space to put the new block.
1664 error
= xfs_bmap_first_unused(tp
, dp
, count
, bno
, w
);
1669 * Try mapping it in one filesystem block.
1672 ASSERT(args
->firstblock
!= NULL
);
1673 error
= xfs_bmapi_write(tp
, dp
, *bno
, count
,
1674 xfs_bmapi_aflag(w
)|XFS_BMAPI_METADATA
|XFS_BMAPI_CONTIG
,
1675 args
->firstblock
, args
->total
, &map
, &nmap
,
1684 } else if (nmap
== 0 && count
> 1) {
1689 * If we didn't get it and the block might work if fragmented,
1690 * try without the CONTIG flag. Loop until we get it all.
1692 mapp
= kmem_alloc(sizeof(*mapp
) * count
, KM_SLEEP
);
1693 for (b
= *bno
, mapi
= 0; b
< *bno
+ count
; ) {
1694 nmap
= MIN(XFS_BMAP_MAX_NMAP
, count
);
1695 c
= (int)(*bno
+ count
- b
);
1696 error
= xfs_bmapi_write(tp
, dp
, b
, c
,
1697 xfs_bmapi_aflag(w
)|XFS_BMAPI_METADATA
,
1698 args
->firstblock
, args
->total
,
1699 &mapp
[mapi
], &nmap
, args
->flist
);
1705 b
= mapp
[mapi
- 1].br_startoff
+
1706 mapp
[mapi
- 1].br_blockcount
;
1714 * Count the blocks we got, make sure it matches the total.
1716 for (i
= 0, got
= 0; i
< mapi
; i
++)
1717 got
+= mapp
[i
].br_blockcount
;
1718 if (got
!= count
|| mapp
[0].br_startoff
!= *bno
||
1719 mapp
[mapi
- 1].br_startoff
+ mapp
[mapi
- 1].br_blockcount
!=
1721 error
= XFS_ERROR(ENOSPC
);
1725 /* account for newly allocated blocks in reserved blocks total */
1726 args
->total
-= dp
->i_d
.di_nblocks
- nblks
;
1735 * Add a block to the btree ahead of the file.
1736 * Return the new block number to the caller.
1740 struct xfs_da_args
*args
,
1741 xfs_dablk_t
*new_blkno
)
1747 trace_xfs_da_grow_inode(args
);
1749 if (args
->whichfork
== XFS_DATA_FORK
) {
1750 bno
= args
->dp
->i_mount
->m_dirleafblk
;
1751 count
= args
->dp
->i_mount
->m_dirblkfsbs
;
1757 error
= xfs_da_grow_inode_int(args
, &bno
, count
);
1759 *new_blkno
= (xfs_dablk_t
)bno
;
1764 * Ick. We need to always be able to remove a btree block, even
1765 * if there's no space reservation because the filesystem is full.
1766 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
1767 * It swaps the target block with the last block in the file. The
1768 * last block in the file can always be removed since it can't cause
1769 * a bmap btree split to do that.
1772 xfs_da_swap_lastblock(
1773 xfs_da_args_t
*args
,
1774 xfs_dablk_t
*dead_blknop
,
1775 struct xfs_buf
**dead_bufp
)
1777 xfs_dablk_t dead_blkno
, last_blkno
, sib_blkno
, par_blkno
;
1778 struct xfs_buf
*dead_buf
, *last_buf
, *sib_buf
, *par_buf
;
1779 xfs_fileoff_t lastoff
;
1783 int error
, w
, entno
, level
, dead_level
;
1784 xfs_da_blkinfo_t
*dead_info
, *sib_info
;
1785 xfs_da_intnode_t
*par_node
, *dead_node
;
1786 xfs_dir2_leaf_t
*dead_leaf2
;
1787 xfs_dahash_t dead_hash
;
1789 trace_xfs_da_swap_lastblock(args
);
1791 dead_buf
= *dead_bufp
;
1792 dead_blkno
= *dead_blknop
;
1795 w
= args
->whichfork
;
1796 ASSERT(w
== XFS_DATA_FORK
);
1798 lastoff
= mp
->m_dirfreeblk
;
1799 error
= xfs_bmap_last_before(tp
, ip
, &lastoff
, w
);
1802 if (unlikely(lastoff
== 0)) {
1803 XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW
,
1805 return XFS_ERROR(EFSCORRUPTED
);
1808 * Read the last block in the btree space.
1810 last_blkno
= (xfs_dablk_t
)lastoff
- mp
->m_dirblkfsbs
;
1811 error
= xfs_da_node_read(tp
, ip
, last_blkno
, -1, &last_buf
, w
);
1815 * Copy the last block into the dead buffer and log it.
1817 memcpy(dead_buf
->b_addr
, last_buf
->b_addr
, mp
->m_dirblksize
);
1818 xfs_trans_log_buf(tp
, dead_buf
, 0, mp
->m_dirblksize
- 1);
1819 dead_info
= dead_buf
->b_addr
;
1821 * Get values from the moved block.
1823 if (dead_info
->magic
== cpu_to_be16(XFS_DIR2_LEAFN_MAGIC
)) {
1824 dead_leaf2
= (xfs_dir2_leaf_t
*)dead_info
;
1826 dead_hash
= be32_to_cpu(dead_leaf2
->ents
[be16_to_cpu(dead_leaf2
->hdr
.count
) - 1].hashval
);
1828 ASSERT(dead_info
->magic
== cpu_to_be16(XFS_DA_NODE_MAGIC
));
1829 dead_node
= (xfs_da_intnode_t
*)dead_info
;
1830 dead_level
= be16_to_cpu(dead_node
->hdr
.level
);
1831 dead_hash
= be32_to_cpu(dead_node
->btree
[be16_to_cpu(dead_node
->hdr
.count
) - 1].hashval
);
1833 sib_buf
= par_buf
= NULL
;
1835 * If the moved block has a left sibling, fix up the pointers.
1837 if ((sib_blkno
= be32_to_cpu(dead_info
->back
))) {
1838 error
= xfs_da_node_read(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
);
1841 sib_info
= sib_buf
->b_addr
;
1843 be32_to_cpu(sib_info
->forw
) != last_blkno
||
1844 sib_info
->magic
!= dead_info
->magic
)) {
1845 XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
1846 XFS_ERRLEVEL_LOW
, mp
);
1847 error
= XFS_ERROR(EFSCORRUPTED
);
1850 sib_info
->forw
= cpu_to_be32(dead_blkno
);
1851 xfs_trans_log_buf(tp
, sib_buf
,
1852 XFS_DA_LOGRANGE(sib_info
, &sib_info
->forw
,
1853 sizeof(sib_info
->forw
)));
1857 * If the moved block has a right sibling, fix up the pointers.
1859 if ((sib_blkno
= be32_to_cpu(dead_info
->forw
))) {
1860 error
= xfs_da_node_read(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
);
1863 sib_info
= sib_buf
->b_addr
;
1865 be32_to_cpu(sib_info
->back
) != last_blkno
||
1866 sib_info
->magic
!= dead_info
->magic
)) {
1867 XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
1868 XFS_ERRLEVEL_LOW
, mp
);
1869 error
= XFS_ERROR(EFSCORRUPTED
);
1872 sib_info
->back
= cpu_to_be32(dead_blkno
);
1873 xfs_trans_log_buf(tp
, sib_buf
,
1874 XFS_DA_LOGRANGE(sib_info
, &sib_info
->back
,
1875 sizeof(sib_info
->back
)));
1878 par_blkno
= mp
->m_dirleafblk
;
1881 * Walk down the tree looking for the parent of the moved block.
1884 error
= xfs_da_node_read(tp
, ip
, par_blkno
, -1, &par_buf
, w
);
1887 par_node
= par_buf
->b_addr
;
1888 if (unlikely(par_node
->hdr
.info
.magic
!=
1889 cpu_to_be16(XFS_DA_NODE_MAGIC
) ||
1890 (level
>= 0 && level
!= be16_to_cpu(par_node
->hdr
.level
) + 1))) {
1891 XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
1892 XFS_ERRLEVEL_LOW
, mp
);
1893 error
= XFS_ERROR(EFSCORRUPTED
);
1896 level
= be16_to_cpu(par_node
->hdr
.level
);
1898 entno
< be16_to_cpu(par_node
->hdr
.count
) &&
1899 be32_to_cpu(par_node
->btree
[entno
].hashval
) < dead_hash
;
1902 if (unlikely(entno
== be16_to_cpu(par_node
->hdr
.count
))) {
1903 XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
1904 XFS_ERRLEVEL_LOW
, mp
);
1905 error
= XFS_ERROR(EFSCORRUPTED
);
1908 par_blkno
= be32_to_cpu(par_node
->btree
[entno
].before
);
1909 if (level
== dead_level
+ 1)
1911 xfs_trans_brelse(tp
, par_buf
);
1915 * We're in the right parent block.
1916 * Look for the right entry.
1920 entno
< be16_to_cpu(par_node
->hdr
.count
) &&
1921 be32_to_cpu(par_node
->btree
[entno
].before
) != last_blkno
;
1924 if (entno
< be16_to_cpu(par_node
->hdr
.count
))
1926 par_blkno
= be32_to_cpu(par_node
->hdr
.info
.forw
);
1927 xfs_trans_brelse(tp
, par_buf
);
1929 if (unlikely(par_blkno
== 0)) {
1930 XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
1931 XFS_ERRLEVEL_LOW
, mp
);
1932 error
= XFS_ERROR(EFSCORRUPTED
);
1935 error
= xfs_da_node_read(tp
, ip
, par_blkno
, -1, &par_buf
, w
);
1938 par_node
= par_buf
->b_addr
;
1940 be16_to_cpu(par_node
->hdr
.level
) != level
||
1941 par_node
->hdr
.info
.magic
!= cpu_to_be16(XFS_DA_NODE_MAGIC
))) {
1942 XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
1943 XFS_ERRLEVEL_LOW
, mp
);
1944 error
= XFS_ERROR(EFSCORRUPTED
);
1950 * Update the parent entry pointing to the moved block.
1952 par_node
->btree
[entno
].before
= cpu_to_be32(dead_blkno
);
1953 xfs_trans_log_buf(tp
, par_buf
,
1954 XFS_DA_LOGRANGE(par_node
, &par_node
->btree
[entno
].before
,
1955 sizeof(par_node
->btree
[entno
].before
)));
1956 *dead_blknop
= last_blkno
;
1957 *dead_bufp
= last_buf
;
1961 xfs_trans_brelse(tp
, par_buf
);
1963 xfs_trans_brelse(tp
, sib_buf
);
1964 xfs_trans_brelse(tp
, last_buf
);
1969 * Remove a btree block from a directory or attribute.
1972 xfs_da_shrink_inode(
1973 xfs_da_args_t
*args
,
1974 xfs_dablk_t dead_blkno
,
1975 struct xfs_buf
*dead_buf
)
1978 int done
, error
, w
, count
;
1982 trace_xfs_da_shrink_inode(args
);
1985 w
= args
->whichfork
;
1988 if (w
== XFS_DATA_FORK
)
1989 count
= mp
->m_dirblkfsbs
;
1994 * Remove extents. If we get ENOSPC for a dir we have to move
1995 * the last block to the place we want to kill.
1997 if ((error
= xfs_bunmapi(tp
, dp
, dead_blkno
, count
,
1998 xfs_bmapi_aflag(w
)|XFS_BMAPI_METADATA
,
1999 0, args
->firstblock
, args
->flist
,
2000 &done
)) == ENOSPC
) {
2001 if (w
!= XFS_DATA_FORK
)
2003 if ((error
= xfs_da_swap_lastblock(args
, &dead_blkno
,
2010 xfs_trans_binval(tp
, dead_buf
);
2015 * See if the mapping(s) for this btree block are valid, i.e.
2016 * don't contain holes, are logically contiguous, and cover the whole range.
2019 xfs_da_map_covers_blocks(
2021 xfs_bmbt_irec_t
*mapp
,
2028 for (i
= 0, off
= bno
; i
< nmap
; i
++) {
2029 if (mapp
[i
].br_startblock
== HOLESTARTBLOCK
||
2030 mapp
[i
].br_startblock
== DELAYSTARTBLOCK
) {
2033 if (off
!= mapp
[i
].br_startoff
) {
2036 off
+= mapp
[i
].br_blockcount
;
2038 return off
== bno
+ count
;
2042 * Convert a struct xfs_bmbt_irec to a struct xfs_buf_map.
2044 * For the single map case, it is assumed that the caller has provided a pointer
2045 * to a valid xfs_buf_map. For the multiple map case, this function will
2046 * allocate the xfs_buf_map to hold all the maps and replace the caller's single
2047 * map pointer with the allocated map.
2050 xfs_buf_map_from_irec(
2051 struct xfs_mount
*mp
,
2052 struct xfs_buf_map
**mapp
,
2053 unsigned int *nmaps
,
2054 struct xfs_bmbt_irec
*irecs
,
2055 unsigned int nirecs
)
2057 struct xfs_buf_map
*map
;
2060 ASSERT(*nmaps
== 1);
2061 ASSERT(nirecs
>= 1);
2064 map
= kmem_zalloc(nirecs
* sizeof(struct xfs_buf_map
), KM_SLEEP
);
2072 for (i
= 0; i
< *nmaps
; i
++) {
2073 ASSERT(irecs
[i
].br_startblock
!= DELAYSTARTBLOCK
&&
2074 irecs
[i
].br_startblock
!= HOLESTARTBLOCK
);
2075 map
[i
].bm_bn
= XFS_FSB_TO_DADDR(mp
, irecs
[i
].br_startblock
);
2076 map
[i
].bm_len
= XFS_FSB_TO_BB(mp
, irecs
[i
].br_blockcount
);
2082 * Map the block we are given ready for reading. There are three possible return
2084 * -1 - will be returned if we land in a hole and mappedbno == -2 so the
2085 * caller knows not to execute a subsequent read.
2086 * 0 - if we mapped the block successfully
2087 * >0 - positive error number if there was an error.
2091 struct xfs_trans
*trans
,
2092 struct xfs_inode
*dp
,
2094 xfs_daddr_t mappedbno
,
2096 struct xfs_buf_map
**map
,
2099 struct xfs_mount
*mp
= dp
->i_mount
;
2102 struct xfs_bmbt_irec irec
;
2103 struct xfs_bmbt_irec
*irecs
= &irec
;
2106 ASSERT(map
&& *map
);
2107 ASSERT(*nmaps
== 1);
2109 nfsb
= (whichfork
== XFS_DATA_FORK
) ? mp
->m_dirblkfsbs
: 1;
2112 * Caller doesn't have a mapping. -2 means don't complain
2113 * if we land in a hole.
2115 if (mappedbno
== -1 || mappedbno
== -2) {
2117 * Optimize the one-block case.
2120 irecs
= kmem_zalloc(sizeof(irec
) * nfsb
, KM_SLEEP
);
2123 error
= xfs_bmapi_read(dp
, (xfs_fileoff_t
)bno
, nfsb
, irecs
,
2124 &nirecs
, xfs_bmapi_aflag(whichfork
));
2128 irecs
->br_startblock
= XFS_DADDR_TO_FSB(mp
, mappedbno
);
2129 irecs
->br_startoff
= (xfs_fileoff_t
)bno
;
2130 irecs
->br_blockcount
= nfsb
;
2131 irecs
->br_state
= 0;
2135 if (!xfs_da_map_covers_blocks(nirecs
, irecs
, bno
, nfsb
)) {
2136 error
= mappedbno
== -2 ? -1 : XFS_ERROR(EFSCORRUPTED
);
2137 if (unlikely(error
== EFSCORRUPTED
)) {
2138 if (xfs_error_level
>= XFS_ERRLEVEL_LOW
) {
2140 xfs_alert(mp
, "%s: bno %lld dir: inode %lld",
2141 __func__
, (long long)bno
,
2142 (long long)dp
->i_ino
);
2143 for (i
= 0; i
< *nmaps
; i
++) {
2145 "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
2147 (long long)irecs
[i
].br_startoff
,
2148 (long long)irecs
[i
].br_startblock
,
2149 (long long)irecs
[i
].br_blockcount
,
2153 XFS_ERROR_REPORT("xfs_da_do_buf(1)",
2154 XFS_ERRLEVEL_LOW
, mp
);
2158 error
= xfs_buf_map_from_irec(mp
, map
, nmaps
, irecs
, nirecs
);
2166 * Get a buffer for the dir/attr block.
2170 struct xfs_trans
*trans
,
2171 struct xfs_inode
*dp
,
2173 xfs_daddr_t mappedbno
,
2174 struct xfs_buf
**bpp
,
2178 struct xfs_buf_map map
;
2179 struct xfs_buf_map
*mapp
;
2186 error
= xfs_dabuf_map(trans
, dp
, bno
, mappedbno
, whichfork
,
2189 /* mapping a hole is not an error, but we don't continue */
2195 bp
= xfs_trans_get_buf_map(trans
, dp
->i_mount
->m_ddev_targp
,
2197 error
= bp
? bp
->b_error
: XFS_ERROR(EIO
);
2199 xfs_trans_brelse(trans
, bp
);
2213 * Get a buffer for the dir/attr block, fill in the contents.
2217 struct xfs_trans
*trans
,
2218 struct xfs_inode
*dp
,
2220 xfs_daddr_t mappedbno
,
2221 struct xfs_buf
**bpp
,
2223 xfs_buf_iodone_t verifier
)
2226 struct xfs_buf_map map
;
2227 struct xfs_buf_map
*mapp
;
2234 error
= xfs_dabuf_map(trans
, dp
, bno
, mappedbno
, whichfork
,
2237 /* mapping a hole is not an error, but we don't continue */
2243 error
= xfs_trans_read_buf_map(dp
->i_mount
, trans
,
2244 dp
->i_mount
->m_ddev_targp
,
2245 mapp
, nmap
, 0, &bp
, verifier
);
2249 if (whichfork
== XFS_ATTR_FORK
)
2250 xfs_buf_set_ref(bp
, XFS_ATTR_BTREE_REF
);
2252 xfs_buf_set_ref(bp
, XFS_DIR_BTREE_REF
);
2255 * This verification code will be moved to a CRC verification callback
2256 * function so just leave it here unchanged until then.
2259 xfs_dir2_data_hdr_t
*hdr
= bp
->b_addr
;
2260 xfs_dir2_free_t
*free
= bp
->b_addr
;
2261 xfs_da_blkinfo_t
*info
= bp
->b_addr
;
2263 struct xfs_mount
*mp
= dp
->i_mount
;
2265 magic
= be16_to_cpu(info
->magic
);
2266 magic1
= be32_to_cpu(hdr
->magic
);
2268 XFS_TEST_ERROR((magic
!= XFS_DA_NODE_MAGIC
) &&
2269 (magic
!= XFS_ATTR_LEAF_MAGIC
) &&
2270 (magic
!= XFS_DIR2_LEAF1_MAGIC
) &&
2271 (magic
!= XFS_DIR2_LEAFN_MAGIC
) &&
2272 (magic1
!= XFS_DIR2_BLOCK_MAGIC
) &&
2273 (magic1
!= XFS_DIR2_DATA_MAGIC
) &&
2274 (free
->hdr
.magic
!= cpu_to_be32(XFS_DIR2_FREE_MAGIC
)),
2275 mp
, XFS_ERRTAG_DA_READ_BUF
,
2276 XFS_RANDOM_DA_READ_BUF
))) {
2277 trace_xfs_da_btree_corrupt(bp
, _RET_IP_
);
2278 XFS_CORRUPTION_ERROR("xfs_da_do_buf(2)",
2279 XFS_ERRLEVEL_LOW
, mp
, info
);
2280 error
= XFS_ERROR(EFSCORRUPTED
);
2281 xfs_trans_brelse(trans
, bp
);
2294 * Readahead the dir/attr block.
2298 struct xfs_trans
*trans
,
2299 struct xfs_inode
*dp
,
2301 xfs_daddr_t mappedbno
,
2303 xfs_buf_iodone_t verifier
)
2305 struct xfs_buf_map map
;
2306 struct xfs_buf_map
*mapp
;
2312 error
= xfs_dabuf_map(trans
, dp
, bno
, mappedbno
, whichfork
,
2315 /* mapping a hole is not an error, but we don't continue */
2321 mappedbno
= mapp
[0].bm_bn
;
2322 xfs_buf_readahead_map(dp
->i_mount
->m_ddev_targp
, mapp
, nmap
, NULL
);
2333 kmem_zone_t
*xfs_da_state_zone
; /* anchor for state struct zone */
2336 * Allocate a dir-state structure.
2337 * We don't put them on the stack since they're large.
2340 xfs_da_state_alloc(void)
2342 return kmem_zone_zalloc(xfs_da_state_zone
, KM_NOFS
);
2346 * Kill the altpath contents of a da-state structure.
2349 xfs_da_state_kill_altpath(xfs_da_state_t
*state
)
2353 for (i
= 0; i
< state
->altpath
.active
; i
++)
2354 state
->altpath
.blk
[i
].bp
= NULL
;
2355 state
->altpath
.active
= 0;
2359 * Free a da-state structure.
2362 xfs_da_state_free(xfs_da_state_t
*state
)
2364 xfs_da_state_kill_altpath(state
);
2366 memset((char *)state
, 0, sizeof(*state
));
2368 kmem_zone_free(xfs_da_state_zone
, state
);