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"
24 #include "xfs_trans.h"
28 #include "xfs_mount.h"
29 #include "xfs_da_btree.h"
30 #include "xfs_bmap_btree.h"
31 #include "xfs_dir2_sf.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_dir2_data.h"
40 #include "xfs_dir2_leaf.h"
41 #include "xfs_dir2_block.h"
42 #include "xfs_dir2_node.h"
43 #include "xfs_error.h"
44 #include "xfs_trace.h"
49 * Routines to implement directories as Btrees of hashed names.
52 /*========================================================================
53 * Function prototypes for the kernel.
54 *========================================================================*/
57 * Routines used for growing the Btree.
59 STATIC
int xfs_da_root_split(xfs_da_state_t
*state
,
60 xfs_da_state_blk_t
*existing_root
,
61 xfs_da_state_blk_t
*new_child
);
62 STATIC
int xfs_da_node_split(xfs_da_state_t
*state
,
63 xfs_da_state_blk_t
*existing_blk
,
64 xfs_da_state_blk_t
*split_blk
,
65 xfs_da_state_blk_t
*blk_to_add
,
68 STATIC
void xfs_da_node_rebalance(xfs_da_state_t
*state
,
69 xfs_da_state_blk_t
*node_blk_1
,
70 xfs_da_state_blk_t
*node_blk_2
);
71 STATIC
void xfs_da_node_add(xfs_da_state_t
*state
,
72 xfs_da_state_blk_t
*old_node_blk
,
73 xfs_da_state_blk_t
*new_node_blk
);
76 * Routines used for shrinking the Btree.
78 STATIC
int xfs_da_root_join(xfs_da_state_t
*state
,
79 xfs_da_state_blk_t
*root_blk
);
80 STATIC
int xfs_da_node_toosmall(xfs_da_state_t
*state
, int *retval
);
81 STATIC
void xfs_da_node_remove(xfs_da_state_t
*state
,
82 xfs_da_state_blk_t
*drop_blk
);
83 STATIC
void xfs_da_node_unbalance(xfs_da_state_t
*state
,
84 xfs_da_state_blk_t
*src_node_blk
,
85 xfs_da_state_blk_t
*dst_node_blk
);
90 STATIC uint
xfs_da_node_lasthash(xfs_dabuf_t
*bp
, int *count
);
91 STATIC
int xfs_da_node_order(xfs_dabuf_t
*node1_bp
, xfs_dabuf_t
*node2_bp
);
92 STATIC xfs_dabuf_t
*xfs_da_buf_make(int nbuf
, xfs_buf_t
**bps
, inst_t
*ra
);
93 STATIC
int xfs_da_blk_unlink(xfs_da_state_t
*state
,
94 xfs_da_state_blk_t
*drop_blk
,
95 xfs_da_state_blk_t
*save_blk
);
96 STATIC
void xfs_da_state_kill_altpath(xfs_da_state_t
*state
);
98 /*========================================================================
99 * Routines used for growing the Btree.
100 *========================================================================*/
103 * Create the initial contents of an intermediate node.
106 xfs_da_node_create(xfs_da_args_t
*args
, xfs_dablk_t blkno
, int level
,
107 xfs_dabuf_t
**bpp
, int whichfork
)
109 xfs_da_intnode_t
*node
;
115 error
= xfs_da_get_buf(tp
, args
->dp
, blkno
, -1, &bp
, whichfork
);
120 node
->hdr
.info
.forw
= 0;
121 node
->hdr
.info
.back
= 0;
122 node
->hdr
.info
.magic
= cpu_to_be16(XFS_DA_NODE_MAGIC
);
123 node
->hdr
.info
.pad
= 0;
125 node
->hdr
.level
= cpu_to_be16(level
);
127 xfs_da_log_buf(tp
, bp
,
128 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
135 * Split a leaf node, rebalance, then possibly split
136 * intermediate nodes, rebalance, etc.
139 xfs_da_split(xfs_da_state_t
*state
)
141 xfs_da_state_blk_t
*oldblk
, *newblk
, *addblk
;
142 xfs_da_intnode_t
*node
;
144 int max
, action
, error
, i
;
147 * Walk back up the tree splitting/inserting/adjusting as necessary.
148 * If we need to insert and there isn't room, split the node, then
149 * decide which fragment to insert the new block from below into.
150 * Note that we may split the root this way, but we need more fixup.
152 max
= state
->path
.active
- 1;
153 ASSERT((max
>= 0) && (max
< XFS_DA_NODE_MAXDEPTH
));
154 ASSERT(state
->path
.blk
[max
].magic
== XFS_ATTR_LEAF_MAGIC
||
155 state
->path
.blk
[max
].magic
== XFS_DIR2_LEAFN_MAGIC
);
157 addblk
= &state
->path
.blk
[max
]; /* initial dummy value */
158 for (i
= max
; (i
>= 0) && addblk
; state
->path
.active
--, i
--) {
159 oldblk
= &state
->path
.blk
[i
];
160 newblk
= &state
->altpath
.blk
[i
];
163 * If a leaf node then
164 * Allocate a new leaf node, then rebalance across them.
165 * else if an intermediate node then
166 * We split on the last layer, must we split the node?
168 switch (oldblk
->magic
) {
169 case XFS_ATTR_LEAF_MAGIC
:
170 error
= xfs_attr_leaf_split(state
, oldblk
, newblk
);
171 if ((error
!= 0) && (error
!= ENOSPC
)) {
172 return(error
); /* GROT: attr is inconsistent */
179 * Entry wouldn't fit, split the leaf again.
181 state
->extravalid
= 1;
183 state
->extraafter
= 0; /* before newblk */
184 error
= xfs_attr_leaf_split(state
, oldblk
,
187 state
->extraafter
= 1; /* after newblk */
188 error
= xfs_attr_leaf_split(state
, newblk
,
192 return(error
); /* GROT: attr inconsistent */
195 case XFS_DIR2_LEAFN_MAGIC
:
196 error
= xfs_dir2_leafn_split(state
, oldblk
, newblk
);
201 case XFS_DA_NODE_MAGIC
:
202 error
= xfs_da_node_split(state
, oldblk
, newblk
, addblk
,
204 xfs_da_buf_done(addblk
->bp
);
207 return(error
); /* GROT: dir is inconsistent */
209 * Record the newly split block for the next time thru?
219 * Update the btree to show the new hashval for this child.
221 xfs_da_fixhashpath(state
, &state
->path
);
223 * If we won't need this block again, it's getting dropped
224 * from the active path by the loop control, so we need
225 * to mark it done now.
227 if (i
> 0 || !addblk
)
228 xfs_da_buf_done(oldblk
->bp
);
234 * Split the root node.
236 ASSERT(state
->path
.active
== 0);
237 oldblk
= &state
->path
.blk
[0];
238 error
= xfs_da_root_split(state
, oldblk
, addblk
);
240 xfs_da_buf_done(oldblk
->bp
);
241 xfs_da_buf_done(addblk
->bp
);
243 return(error
); /* GROT: dir is inconsistent */
247 * Update pointers to the node which used to be block 0 and
248 * just got bumped because of the addition of a new root node.
249 * There might be three blocks involved if a double split occurred,
250 * and the original block 0 could be at any position in the list.
253 node
= oldblk
->bp
->data
;
254 if (node
->hdr
.info
.forw
) {
255 if (be32_to_cpu(node
->hdr
.info
.forw
) == addblk
->blkno
) {
258 ASSERT(state
->extravalid
);
259 bp
= state
->extrablk
.bp
;
262 node
->hdr
.info
.back
= cpu_to_be32(oldblk
->blkno
);
263 xfs_da_log_buf(state
->args
->trans
, bp
,
264 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
265 sizeof(node
->hdr
.info
)));
267 node
= oldblk
->bp
->data
;
268 if (node
->hdr
.info
.back
) {
269 if (be32_to_cpu(node
->hdr
.info
.back
) == addblk
->blkno
) {
272 ASSERT(state
->extravalid
);
273 bp
= state
->extrablk
.bp
;
276 node
->hdr
.info
.forw
= cpu_to_be32(oldblk
->blkno
);
277 xfs_da_log_buf(state
->args
->trans
, bp
,
278 XFS_DA_LOGRANGE(node
, &node
->hdr
.info
,
279 sizeof(node
->hdr
.info
)));
281 xfs_da_buf_done(oldblk
->bp
);
282 xfs_da_buf_done(addblk
->bp
);
288 * Split the root. We have to create a new root and point to the two
289 * parts (the split old root) that we just created. Copy block zero to
290 * the EOF, extending the inode in process.
292 STATIC
int /* error */
293 xfs_da_root_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
294 xfs_da_state_blk_t
*blk2
)
296 xfs_da_intnode_t
*node
, *oldroot
;
304 xfs_dir2_leaf_t
*leaf
;
307 * Copy the existing (incorrect) block from the root node position
308 * to a free space somewhere.
311 ASSERT(args
!= NULL
);
312 error
= xfs_da_grow_inode(args
, &blkno
);
318 error
= xfs_da_get_buf(tp
, dp
, blkno
, -1, &bp
, args
->whichfork
);
323 oldroot
= blk1
->bp
->data
;
324 if (be16_to_cpu(oldroot
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
) {
325 size
= (int)((char *)&oldroot
->btree
[be16_to_cpu(oldroot
->hdr
.count
)] -
328 ASSERT(be16_to_cpu(oldroot
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
);
329 leaf
= (xfs_dir2_leaf_t
*)oldroot
;
330 size
= (int)((char *)&leaf
->ents
[be16_to_cpu(leaf
->hdr
.count
)] -
333 memcpy(node
, oldroot
, size
);
334 xfs_da_log_buf(tp
, bp
, 0, size
- 1);
335 xfs_da_buf_done(blk1
->bp
);
340 * Set up the new root node.
342 error
= xfs_da_node_create(args
,
343 (args
->whichfork
== XFS_DATA_FORK
) ? mp
->m_dirleafblk
: 0,
344 be16_to_cpu(node
->hdr
.level
) + 1, &bp
, args
->whichfork
);
348 node
->btree
[0].hashval
= cpu_to_be32(blk1
->hashval
);
349 node
->btree
[0].before
= cpu_to_be32(blk1
->blkno
);
350 node
->btree
[1].hashval
= cpu_to_be32(blk2
->hashval
);
351 node
->btree
[1].before
= cpu_to_be32(blk2
->blkno
);
352 node
->hdr
.count
= cpu_to_be16(2);
355 if (be16_to_cpu(oldroot
->hdr
.info
.magic
) == XFS_DIR2_LEAFN_MAGIC
) {
356 ASSERT(blk1
->blkno
>= mp
->m_dirleafblk
&&
357 blk1
->blkno
< mp
->m_dirfreeblk
);
358 ASSERT(blk2
->blkno
>= mp
->m_dirleafblk
&&
359 blk2
->blkno
< mp
->m_dirfreeblk
);
363 /* Header is already logged by xfs_da_node_create */
364 xfs_da_log_buf(tp
, bp
,
365 XFS_DA_LOGRANGE(node
, node
->btree
,
366 sizeof(xfs_da_node_entry_t
) * 2));
373 * Split the node, rebalance, then add the new entry.
375 STATIC
int /* error */
376 xfs_da_node_split(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
377 xfs_da_state_blk_t
*newblk
,
378 xfs_da_state_blk_t
*addblk
,
379 int treelevel
, int *result
)
381 xfs_da_intnode_t
*node
;
386 node
= oldblk
->bp
->data
;
387 ASSERT(be16_to_cpu(node
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
390 * With V2 dirs the extra block is data or freespace.
392 useextra
= state
->extravalid
&& state
->args
->whichfork
== XFS_ATTR_FORK
;
393 newcount
= 1 + useextra
;
395 * Do we have to split the node?
397 if ((be16_to_cpu(node
->hdr
.count
) + newcount
) > state
->node_ents
) {
399 * Allocate a new node, add to the doubly linked chain of
400 * nodes, then move some of our excess entries into it.
402 error
= xfs_da_grow_inode(state
->args
, &blkno
);
404 return(error
); /* GROT: dir is inconsistent */
406 error
= xfs_da_node_create(state
->args
, blkno
, treelevel
,
407 &newblk
->bp
, state
->args
->whichfork
);
409 return(error
); /* GROT: dir is inconsistent */
410 newblk
->blkno
= blkno
;
411 newblk
->magic
= XFS_DA_NODE_MAGIC
;
412 xfs_da_node_rebalance(state
, oldblk
, newblk
);
413 error
= xfs_da_blk_link(state
, oldblk
, newblk
);
422 * Insert the new entry(s) into the correct block
423 * (updating last hashval in the process).
425 * xfs_da_node_add() inserts BEFORE the given index,
426 * and as a result of using node_lookup_int() we always
427 * point to a valid entry (not after one), but a split
428 * operation always results in a new block whose hashvals
429 * FOLLOW the current block.
431 * If we had double-split op below us, then add the extra block too.
433 node
= oldblk
->bp
->data
;
434 if (oldblk
->index
<= be16_to_cpu(node
->hdr
.count
)) {
436 xfs_da_node_add(state
, oldblk
, addblk
);
438 if (state
->extraafter
)
440 xfs_da_node_add(state
, oldblk
, &state
->extrablk
);
441 state
->extravalid
= 0;
445 xfs_da_node_add(state
, newblk
, addblk
);
447 if (state
->extraafter
)
449 xfs_da_node_add(state
, newblk
, &state
->extrablk
);
450 state
->extravalid
= 0;
458 * Balance the btree elements between two intermediate nodes,
459 * usually one full and one empty.
461 * NOTE: if blk2 is empty, then it will get the upper half of blk1.
464 xfs_da_node_rebalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*blk1
,
465 xfs_da_state_blk_t
*blk2
)
467 xfs_da_intnode_t
*node1
, *node2
, *tmpnode
;
468 xfs_da_node_entry_t
*btree_s
, *btree_d
;
472 node1
= blk1
->bp
->data
;
473 node2
= blk2
->bp
->data
;
475 * Figure out how many entries need to move, and in which direction.
476 * Swap the nodes around if that makes it simpler.
478 if ((be16_to_cpu(node1
->hdr
.count
) > 0) && (be16_to_cpu(node2
->hdr
.count
) > 0) &&
479 ((be32_to_cpu(node2
->btree
[0].hashval
) < be32_to_cpu(node1
->btree
[0].hashval
)) ||
480 (be32_to_cpu(node2
->btree
[be16_to_cpu(node2
->hdr
.count
)-1].hashval
) <
481 be32_to_cpu(node1
->btree
[be16_to_cpu(node1
->hdr
.count
)-1].hashval
)))) {
486 ASSERT(be16_to_cpu(node1
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
487 ASSERT(be16_to_cpu(node2
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
488 count
= (be16_to_cpu(node1
->hdr
.count
) - be16_to_cpu(node2
->hdr
.count
)) / 2;
491 tp
= state
->args
->trans
;
493 * Two cases: high-to-low and low-to-high.
497 * Move elements in node2 up to make a hole.
499 if ((tmp
= be16_to_cpu(node2
->hdr
.count
)) > 0) {
500 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
501 btree_s
= &node2
->btree
[0];
502 btree_d
= &node2
->btree
[count
];
503 memmove(btree_d
, btree_s
, tmp
);
507 * Move the req'd B-tree elements from high in node1 to
510 be16_add_cpu(&node2
->hdr
.count
, count
);
511 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
512 btree_s
= &node1
->btree
[be16_to_cpu(node1
->hdr
.count
) - count
];
513 btree_d
= &node2
->btree
[0];
514 memcpy(btree_d
, btree_s
, tmp
);
515 be16_add_cpu(&node1
->hdr
.count
, -count
);
518 * Move the req'd B-tree elements from low in node2 to
522 tmp
= count
* (uint
)sizeof(xfs_da_node_entry_t
);
523 btree_s
= &node2
->btree
[0];
524 btree_d
= &node1
->btree
[be16_to_cpu(node1
->hdr
.count
)];
525 memcpy(btree_d
, btree_s
, tmp
);
526 be16_add_cpu(&node1
->hdr
.count
, count
);
527 xfs_da_log_buf(tp
, blk1
->bp
,
528 XFS_DA_LOGRANGE(node1
, btree_d
, tmp
));
531 * Move elements in node2 down to fill the hole.
533 tmp
= be16_to_cpu(node2
->hdr
.count
) - count
;
534 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
535 btree_s
= &node2
->btree
[count
];
536 btree_d
= &node2
->btree
[0];
537 memmove(btree_d
, btree_s
, tmp
);
538 be16_add_cpu(&node2
->hdr
.count
, -count
);
542 * Log header of node 1 and all current bits of node 2.
544 xfs_da_log_buf(tp
, blk1
->bp
,
545 XFS_DA_LOGRANGE(node1
, &node1
->hdr
, sizeof(node1
->hdr
)));
546 xfs_da_log_buf(tp
, blk2
->bp
,
547 XFS_DA_LOGRANGE(node2
, &node2
->hdr
,
549 sizeof(node2
->btree
[0]) * be16_to_cpu(node2
->hdr
.count
)));
552 * Record the last hashval from each block for upward propagation.
553 * (note: don't use the swapped node pointers)
555 node1
= blk1
->bp
->data
;
556 node2
= blk2
->bp
->data
;
557 blk1
->hashval
= be32_to_cpu(node1
->btree
[be16_to_cpu(node1
->hdr
.count
)-1].hashval
);
558 blk2
->hashval
= be32_to_cpu(node2
->btree
[be16_to_cpu(node2
->hdr
.count
)-1].hashval
);
561 * Adjust the expected index for insertion.
563 if (blk1
->index
>= be16_to_cpu(node1
->hdr
.count
)) {
564 blk2
->index
= blk1
->index
- be16_to_cpu(node1
->hdr
.count
);
565 blk1
->index
= be16_to_cpu(node1
->hdr
.count
) + 1; /* make it invalid */
570 * Add a new entry to an intermediate node.
573 xfs_da_node_add(xfs_da_state_t
*state
, xfs_da_state_blk_t
*oldblk
,
574 xfs_da_state_blk_t
*newblk
)
576 xfs_da_intnode_t
*node
;
577 xfs_da_node_entry_t
*btree
;
581 node
= oldblk
->bp
->data
;
583 ASSERT(be16_to_cpu(node
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
584 ASSERT((oldblk
->index
>= 0) && (oldblk
->index
<= be16_to_cpu(node
->hdr
.count
)));
585 ASSERT(newblk
->blkno
!= 0);
586 if (state
->args
->whichfork
== XFS_DATA_FORK
)
587 ASSERT(newblk
->blkno
>= mp
->m_dirleafblk
&&
588 newblk
->blkno
< mp
->m_dirfreeblk
);
591 * We may need to make some room before we insert the new node.
594 btree
= &node
->btree
[ oldblk
->index
];
595 if (oldblk
->index
< be16_to_cpu(node
->hdr
.count
)) {
596 tmp
= (be16_to_cpu(node
->hdr
.count
) - oldblk
->index
) * (uint
)sizeof(*btree
);
597 memmove(btree
+ 1, btree
, tmp
);
599 btree
->hashval
= cpu_to_be32(newblk
->hashval
);
600 btree
->before
= cpu_to_be32(newblk
->blkno
);
601 xfs_da_log_buf(state
->args
->trans
, oldblk
->bp
,
602 XFS_DA_LOGRANGE(node
, btree
, tmp
+ sizeof(*btree
)));
603 be16_add_cpu(&node
->hdr
.count
, 1);
604 xfs_da_log_buf(state
->args
->trans
, oldblk
->bp
,
605 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
608 * Copy the last hash value from the oldblk to propagate upwards.
610 oldblk
->hashval
= be32_to_cpu(node
->btree
[be16_to_cpu(node
->hdr
.count
)-1 ].hashval
);
613 /*========================================================================
614 * Routines used for shrinking the Btree.
615 *========================================================================*/
618 * Deallocate an empty leaf node, remove it from its parent,
619 * possibly deallocating that block, etc...
622 xfs_da_join(xfs_da_state_t
*state
)
624 xfs_da_state_blk_t
*drop_blk
, *save_blk
;
628 drop_blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
629 save_blk
= &state
->altpath
.blk
[ state
->path
.active
-1 ];
630 ASSERT(state
->path
.blk
[0].magic
== XFS_DA_NODE_MAGIC
);
631 ASSERT(drop_blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
632 drop_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
635 * Walk back up the tree joining/deallocating as necessary.
636 * When we stop dropping blocks, break out.
638 for ( ; state
->path
.active
>= 2; drop_blk
--, save_blk
--,
639 state
->path
.active
--) {
641 * See if we can combine the block with a neighbor.
642 * (action == 0) => no options, just leave
643 * (action == 1) => coalesce, then unlink
644 * (action == 2) => block empty, unlink it
646 switch (drop_blk
->magic
) {
647 case XFS_ATTR_LEAF_MAGIC
:
648 error
= xfs_attr_leaf_toosmall(state
, &action
);
653 xfs_attr_leaf_unbalance(state
, drop_blk
, save_blk
);
655 case XFS_DIR2_LEAFN_MAGIC
:
656 error
= xfs_dir2_leafn_toosmall(state
, &action
);
661 xfs_dir2_leafn_unbalance(state
, drop_blk
, save_blk
);
663 case XFS_DA_NODE_MAGIC
:
665 * Remove the offending node, fixup hashvals,
666 * check for a toosmall neighbor.
668 xfs_da_node_remove(state
, drop_blk
);
669 xfs_da_fixhashpath(state
, &state
->path
);
670 error
= xfs_da_node_toosmall(state
, &action
);
675 xfs_da_node_unbalance(state
, drop_blk
, save_blk
);
678 xfs_da_fixhashpath(state
, &state
->altpath
);
679 error
= xfs_da_blk_unlink(state
, drop_blk
, save_blk
);
680 xfs_da_state_kill_altpath(state
);
683 error
= xfs_da_shrink_inode(state
->args
, drop_blk
->blkno
,
690 * We joined all the way to the top. If it turns out that
691 * we only have one entry in the root, make the child block
694 xfs_da_node_remove(state
, drop_blk
);
695 xfs_da_fixhashpath(state
, &state
->path
);
696 error
= xfs_da_root_join(state
, &state
->path
.blk
[0]);
701 * We have only one entry in the root. Copy the only remaining child of
702 * the old root to block 0 as the new root node.
705 xfs_da_root_join(xfs_da_state_t
*state
, xfs_da_state_blk_t
*root_blk
)
707 xfs_da_intnode_t
*oldroot
;
709 xfs_da_blkinfo_t
*blkinfo
;
716 ASSERT(args
!= NULL
);
717 ASSERT(root_blk
->magic
== XFS_DA_NODE_MAGIC
);
718 oldroot
= root_blk
->bp
->data
;
719 ASSERT(be16_to_cpu(oldroot
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
720 ASSERT(!oldroot
->hdr
.info
.forw
);
721 ASSERT(!oldroot
->hdr
.info
.back
);
724 * If the root has more than one child, then don't do anything.
726 if (be16_to_cpu(oldroot
->hdr
.count
) > 1)
730 * Read in the (only) child block, then copy those bytes into
731 * the root block's buffer and free the original child block.
733 child
= be32_to_cpu(oldroot
->btree
[0].before
);
735 error
= xfs_da_read_buf(args
->trans
, args
->dp
, child
, -1, &bp
,
741 if (be16_to_cpu(oldroot
->hdr
.level
) == 1) {
742 ASSERT(be16_to_cpu(blkinfo
->magic
) == XFS_DIR2_LEAFN_MAGIC
||
743 be16_to_cpu(blkinfo
->magic
) == XFS_ATTR_LEAF_MAGIC
);
745 ASSERT(be16_to_cpu(blkinfo
->magic
) == XFS_DA_NODE_MAGIC
);
747 ASSERT(!blkinfo
->forw
);
748 ASSERT(!blkinfo
->back
);
749 memcpy(root_blk
->bp
->data
, bp
->data
, state
->blocksize
);
750 xfs_da_log_buf(args
->trans
, root_blk
->bp
, 0, state
->blocksize
- 1);
751 error
= xfs_da_shrink_inode(args
, child
, bp
);
756 * Check a node block and its neighbors to see if the block should be
757 * collapsed into one or the other neighbor. Always keep the block
758 * with the smaller block number.
759 * If the current block is over 50% full, don't try to join it, return 0.
760 * If the block is empty, fill in the state structure and return 2.
761 * If it can be collapsed, fill in the state structure and return 1.
762 * If nothing can be done, return 0.
765 xfs_da_node_toosmall(xfs_da_state_t
*state
, int *action
)
767 xfs_da_intnode_t
*node
;
768 xfs_da_state_blk_t
*blk
;
769 xfs_da_blkinfo_t
*info
;
770 int count
, forward
, error
, retval
, i
;
775 * Check for the degenerate case of the block being over 50% full.
776 * If so, it's not worth even looking to see if we might be able
777 * to coalesce with a sibling.
779 blk
= &state
->path
.blk
[ state
->path
.active
-1 ];
780 info
= blk
->bp
->data
;
781 ASSERT(be16_to_cpu(info
->magic
) == XFS_DA_NODE_MAGIC
);
782 node
= (xfs_da_intnode_t
*)info
;
783 count
= be16_to_cpu(node
->hdr
.count
);
784 if (count
> (state
->node_ents
>> 1)) {
785 *action
= 0; /* blk over 50%, don't try to join */
786 return(0); /* blk over 50%, don't try to join */
790 * Check for the degenerate case of the block being empty.
791 * If the block is empty, we'll simply delete it, no need to
792 * coalesce it with a sibling block. We choose (arbitrarily)
793 * to merge with the forward block unless it is NULL.
797 * Make altpath point to the block we want to keep and
798 * path point to the block we want to drop (this one).
800 forward
= (info
->forw
!= 0);
801 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
802 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
815 * Examine each sibling block to see if we can coalesce with
816 * at least 25% free space to spare. We need to figure out
817 * whether to merge with the forward or the backward block.
818 * We prefer coalescing with the lower numbered sibling so as
819 * to shrink a directory over time.
821 /* start with smaller blk num */
822 forward
= (be32_to_cpu(info
->forw
) < be32_to_cpu(info
->back
));
823 for (i
= 0; i
< 2; forward
= !forward
, i
++) {
825 blkno
= be32_to_cpu(info
->forw
);
827 blkno
= be32_to_cpu(info
->back
);
830 error
= xfs_da_read_buf(state
->args
->trans
, state
->args
->dp
,
831 blkno
, -1, &bp
, state
->args
->whichfork
);
836 node
= (xfs_da_intnode_t
*)info
;
837 count
= state
->node_ents
;
838 count
-= state
->node_ents
>> 2;
839 count
-= be16_to_cpu(node
->hdr
.count
);
841 ASSERT(be16_to_cpu(node
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
842 count
-= be16_to_cpu(node
->hdr
.count
);
843 xfs_da_brelse(state
->args
->trans
, bp
);
845 break; /* fits with at least 25% to spare */
853 * Make altpath point to the block we want to keep (the lower
854 * numbered block) and path point to the block we want to drop.
856 memcpy(&state
->altpath
, &state
->path
, sizeof(state
->path
));
857 if (blkno
< blk
->blkno
) {
858 error
= xfs_da_path_shift(state
, &state
->altpath
, forward
,
868 error
= xfs_da_path_shift(state
, &state
->path
, forward
,
883 * Walk back up the tree adjusting hash values as necessary,
884 * when we stop making changes, return.
887 xfs_da_fixhashpath(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
)
889 xfs_da_state_blk_t
*blk
;
890 xfs_da_intnode_t
*node
;
891 xfs_da_node_entry_t
*btree
;
892 xfs_dahash_t lasthash
=0;
895 level
= path
->active
-1;
896 blk
= &path
->blk
[ level
];
897 switch (blk
->magic
) {
898 case XFS_ATTR_LEAF_MAGIC
:
899 lasthash
= xfs_attr_leaf_lasthash(blk
->bp
, &count
);
903 case XFS_DIR2_LEAFN_MAGIC
:
904 lasthash
= xfs_dir2_leafn_lasthash(blk
->bp
, &count
);
908 case XFS_DA_NODE_MAGIC
:
909 lasthash
= xfs_da_node_lasthash(blk
->bp
, &count
);
914 for (blk
--, level
--; level
>= 0; blk
--, level
--) {
915 node
= blk
->bp
->data
;
916 ASSERT(be16_to_cpu(node
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
917 btree
= &node
->btree
[ blk
->index
];
918 if (be32_to_cpu(btree
->hashval
) == lasthash
)
920 blk
->hashval
= lasthash
;
921 btree
->hashval
= cpu_to_be32(lasthash
);
922 xfs_da_log_buf(state
->args
->trans
, blk
->bp
,
923 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
925 lasthash
= be32_to_cpu(node
->btree
[be16_to_cpu(node
->hdr
.count
)-1].hashval
);
930 * Remove an entry from an intermediate node.
933 xfs_da_node_remove(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
)
935 xfs_da_intnode_t
*node
;
936 xfs_da_node_entry_t
*btree
;
939 node
= drop_blk
->bp
->data
;
940 ASSERT(drop_blk
->index
< be16_to_cpu(node
->hdr
.count
));
941 ASSERT(drop_blk
->index
>= 0);
944 * Copy over the offending entry, or just zero it out.
946 btree
= &node
->btree
[drop_blk
->index
];
947 if (drop_blk
->index
< (be16_to_cpu(node
->hdr
.count
)-1)) {
948 tmp
= be16_to_cpu(node
->hdr
.count
) - drop_blk
->index
- 1;
949 tmp
*= (uint
)sizeof(xfs_da_node_entry_t
);
950 memmove(btree
, btree
+ 1, tmp
);
951 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
952 XFS_DA_LOGRANGE(node
, btree
, tmp
));
953 btree
= &node
->btree
[be16_to_cpu(node
->hdr
.count
)-1];
955 memset((char *)btree
, 0, sizeof(xfs_da_node_entry_t
));
956 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
957 XFS_DA_LOGRANGE(node
, btree
, sizeof(*btree
)));
958 be16_add_cpu(&node
->hdr
.count
, -1);
959 xfs_da_log_buf(state
->args
->trans
, drop_blk
->bp
,
960 XFS_DA_LOGRANGE(node
, &node
->hdr
, sizeof(node
->hdr
)));
963 * Copy the last hash value from the block to propagate upwards.
966 drop_blk
->hashval
= be32_to_cpu(btree
->hashval
);
970 * Unbalance the btree elements between two intermediate nodes,
971 * move all Btree elements from one node into another.
974 xfs_da_node_unbalance(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
975 xfs_da_state_blk_t
*save_blk
)
977 xfs_da_intnode_t
*drop_node
, *save_node
;
978 xfs_da_node_entry_t
*btree
;
982 drop_node
= drop_blk
->bp
->data
;
983 save_node
= save_blk
->bp
->data
;
984 ASSERT(be16_to_cpu(drop_node
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
985 ASSERT(be16_to_cpu(save_node
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
986 tp
= state
->args
->trans
;
989 * If the dying block has lower hashvals, then move all the
990 * elements in the remaining block up to make a hole.
992 if ((be32_to_cpu(drop_node
->btree
[0].hashval
) < be32_to_cpu(save_node
->btree
[ 0 ].hashval
)) ||
993 (be32_to_cpu(drop_node
->btree
[be16_to_cpu(drop_node
->hdr
.count
)-1].hashval
) <
994 be32_to_cpu(save_node
->btree
[be16_to_cpu(save_node
->hdr
.count
)-1].hashval
)))
996 btree
= &save_node
->btree
[be16_to_cpu(drop_node
->hdr
.count
)];
997 tmp
= be16_to_cpu(save_node
->hdr
.count
) * (uint
)sizeof(xfs_da_node_entry_t
);
998 memmove(btree
, &save_node
->btree
[0], tmp
);
999 btree
= &save_node
->btree
[0];
1000 xfs_da_log_buf(tp
, save_blk
->bp
,
1001 XFS_DA_LOGRANGE(save_node
, btree
,
1002 (be16_to_cpu(save_node
->hdr
.count
) + be16_to_cpu(drop_node
->hdr
.count
)) *
1003 sizeof(xfs_da_node_entry_t
)));
1005 btree
= &save_node
->btree
[be16_to_cpu(save_node
->hdr
.count
)];
1006 xfs_da_log_buf(tp
, save_blk
->bp
,
1007 XFS_DA_LOGRANGE(save_node
, btree
,
1008 be16_to_cpu(drop_node
->hdr
.count
) *
1009 sizeof(xfs_da_node_entry_t
)));
1013 * Move all the B-tree elements from drop_blk to save_blk.
1015 tmp
= be16_to_cpu(drop_node
->hdr
.count
) * (uint
)sizeof(xfs_da_node_entry_t
);
1016 memcpy(btree
, &drop_node
->btree
[0], tmp
);
1017 be16_add_cpu(&save_node
->hdr
.count
, be16_to_cpu(drop_node
->hdr
.count
));
1019 xfs_da_log_buf(tp
, save_blk
->bp
,
1020 XFS_DA_LOGRANGE(save_node
, &save_node
->hdr
,
1021 sizeof(save_node
->hdr
)));
1024 * Save the last hashval in the remaining block for upward propagation.
1026 save_blk
->hashval
= be32_to_cpu(save_node
->btree
[be16_to_cpu(save_node
->hdr
.count
)-1].hashval
);
1029 /*========================================================================
1030 * Routines used for finding things in the Btree.
1031 *========================================================================*/
1034 * Walk down the Btree looking for a particular filename, filling
1035 * in the state structure as we go.
1037 * We will set the state structure to point to each of the elements
1038 * in each of the nodes where either the hashval is or should be.
1040 * We support duplicate hashval's so for each entry in the current
1041 * node that could contain the desired hashval, descend. This is a
1042 * pruned depth-first tree search.
1045 xfs_da_node_lookup_int(xfs_da_state_t
*state
, int *result
)
1047 xfs_da_state_blk_t
*blk
;
1048 xfs_da_blkinfo_t
*curr
;
1049 xfs_da_intnode_t
*node
;
1050 xfs_da_node_entry_t
*btree
;
1052 int probe
, span
, max
, error
, retval
;
1053 xfs_dahash_t hashval
, btreehashval
;
1054 xfs_da_args_t
*args
;
1059 * Descend thru the B-tree searching each level for the right
1060 * node to use, until the right hashval is found.
1062 blkno
= (args
->whichfork
== XFS_DATA_FORK
)? state
->mp
->m_dirleafblk
: 0;
1063 for (blk
= &state
->path
.blk
[0], state
->path
.active
= 1;
1064 state
->path
.active
<= XFS_DA_NODE_MAXDEPTH
;
1065 blk
++, state
->path
.active
++) {
1067 * Read the next node down in the tree.
1070 error
= xfs_da_read_buf(args
->trans
, args
->dp
, blkno
,
1071 -1, &blk
->bp
, args
->whichfork
);
1074 state
->path
.active
--;
1077 curr
= blk
->bp
->data
;
1078 blk
->magic
= be16_to_cpu(curr
->magic
);
1079 ASSERT(blk
->magic
== XFS_DA_NODE_MAGIC
||
1080 blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1081 blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1084 * Search an intermediate node for a match.
1086 if (blk
->magic
== XFS_DA_NODE_MAGIC
) {
1087 node
= blk
->bp
->data
;
1088 max
= be16_to_cpu(node
->hdr
.count
);
1089 blk
->hashval
= be32_to_cpu(node
->btree
[max
-1].hashval
);
1092 * Binary search. (note: small blocks will skip loop)
1094 probe
= span
= max
/ 2;
1095 hashval
= args
->hashval
;
1096 for (btree
= &node
->btree
[probe
]; span
> 4;
1097 btree
= &node
->btree
[probe
]) {
1099 btreehashval
= be32_to_cpu(btree
->hashval
);
1100 if (btreehashval
< hashval
)
1102 else if (btreehashval
> hashval
)
1107 ASSERT((probe
>= 0) && (probe
< max
));
1108 ASSERT((span
<= 4) || (be32_to_cpu(btree
->hashval
) == hashval
));
1111 * Since we may have duplicate hashval's, find the first
1112 * matching hashval in the node.
1114 while ((probe
> 0) && (be32_to_cpu(btree
->hashval
) >= hashval
)) {
1118 while ((probe
< max
) && (be32_to_cpu(btree
->hashval
) < hashval
)) {
1124 * Pick the right block to descend on.
1128 blkno
= be32_to_cpu(node
->btree
[max
-1].before
);
1131 blkno
= be32_to_cpu(btree
->before
);
1133 } else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1134 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
, NULL
);
1136 } else if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
) {
1137 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
, NULL
);
1143 * A leaf block that ends in the hashval that we are interested in
1144 * (final hashval == search hashval) means that the next block may
1145 * contain more entries with the same hashval, shift upward to the
1146 * next leaf and keep searching.
1149 if (blk
->magic
== XFS_DIR2_LEAFN_MAGIC
) {
1150 retval
= xfs_dir2_leafn_lookup_int(blk
->bp
, args
,
1151 &blk
->index
, state
);
1152 } else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1153 retval
= xfs_attr_leaf_lookup_int(blk
->bp
, args
);
1154 blk
->index
= args
->index
;
1155 args
->blkno
= blk
->blkno
;
1158 return XFS_ERROR(EFSCORRUPTED
);
1160 if (((retval
== ENOENT
) || (retval
== ENOATTR
)) &&
1161 (blk
->hashval
== args
->hashval
)) {
1162 error
= xfs_da_path_shift(state
, &state
->path
, 1, 1,
1168 } else if (blk
->magic
== XFS_ATTR_LEAF_MAGIC
) {
1169 /* path_shift() gives ENOENT */
1170 retval
= XFS_ERROR(ENOATTR
);
1179 /*========================================================================
1181 *========================================================================*/
1184 * Link a new block into a doubly linked list of blocks (of whatever type).
1187 xfs_da_blk_link(xfs_da_state_t
*state
, xfs_da_state_blk_t
*old_blk
,
1188 xfs_da_state_blk_t
*new_blk
)
1190 xfs_da_blkinfo_t
*old_info
, *new_info
, *tmp_info
;
1191 xfs_da_args_t
*args
;
1192 int before
=0, error
;
1196 * Set up environment.
1199 ASSERT(args
!= NULL
);
1200 old_info
= old_blk
->bp
->data
;
1201 new_info
= new_blk
->bp
->data
;
1202 ASSERT(old_blk
->magic
== XFS_DA_NODE_MAGIC
||
1203 old_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1204 old_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1205 ASSERT(old_blk
->magic
== be16_to_cpu(old_info
->magic
));
1206 ASSERT(new_blk
->magic
== be16_to_cpu(new_info
->magic
));
1207 ASSERT(old_blk
->magic
== new_blk
->magic
);
1209 switch (old_blk
->magic
) {
1210 case XFS_ATTR_LEAF_MAGIC
:
1211 before
= xfs_attr_leaf_order(old_blk
->bp
, new_blk
->bp
);
1213 case XFS_DIR2_LEAFN_MAGIC
:
1214 before
= xfs_dir2_leafn_order(old_blk
->bp
, new_blk
->bp
);
1216 case XFS_DA_NODE_MAGIC
:
1217 before
= xfs_da_node_order(old_blk
->bp
, new_blk
->bp
);
1222 * Link blocks in appropriate order.
1226 * Link new block in before existing block.
1228 new_info
->forw
= cpu_to_be32(old_blk
->blkno
);
1229 new_info
->back
= old_info
->back
;
1230 if (old_info
->back
) {
1231 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1232 be32_to_cpu(old_info
->back
),
1233 -1, &bp
, args
->whichfork
);
1237 tmp_info
= bp
->data
;
1238 ASSERT(be16_to_cpu(tmp_info
->magic
) == be16_to_cpu(old_info
->magic
));
1239 ASSERT(be32_to_cpu(tmp_info
->forw
) == old_blk
->blkno
);
1240 tmp_info
->forw
= cpu_to_be32(new_blk
->blkno
);
1241 xfs_da_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1242 xfs_da_buf_done(bp
);
1244 old_info
->back
= cpu_to_be32(new_blk
->blkno
);
1247 * Link new block in after existing block.
1249 new_info
->forw
= old_info
->forw
;
1250 new_info
->back
= cpu_to_be32(old_blk
->blkno
);
1251 if (old_info
->forw
) {
1252 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1253 be32_to_cpu(old_info
->forw
),
1254 -1, &bp
, args
->whichfork
);
1258 tmp_info
= bp
->data
;
1259 ASSERT(tmp_info
->magic
== old_info
->magic
);
1260 ASSERT(be32_to_cpu(tmp_info
->back
) == old_blk
->blkno
);
1261 tmp_info
->back
= cpu_to_be32(new_blk
->blkno
);
1262 xfs_da_log_buf(args
->trans
, bp
, 0, sizeof(*tmp_info
)-1);
1263 xfs_da_buf_done(bp
);
1265 old_info
->forw
= cpu_to_be32(new_blk
->blkno
);
1268 xfs_da_log_buf(args
->trans
, old_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1269 xfs_da_log_buf(args
->trans
, new_blk
->bp
, 0, sizeof(*tmp_info
) - 1);
1274 * Compare two intermediate nodes for "order".
1277 xfs_da_node_order(xfs_dabuf_t
*node1_bp
, xfs_dabuf_t
*node2_bp
)
1279 xfs_da_intnode_t
*node1
, *node2
;
1281 node1
= node1_bp
->data
;
1282 node2
= node2_bp
->data
;
1283 ASSERT((be16_to_cpu(node1
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
) &&
1284 (be16_to_cpu(node2
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
));
1285 if ((be16_to_cpu(node1
->hdr
.count
) > 0) && (be16_to_cpu(node2
->hdr
.count
) > 0) &&
1286 ((be32_to_cpu(node2
->btree
[0].hashval
) <
1287 be32_to_cpu(node1
->btree
[0].hashval
)) ||
1288 (be32_to_cpu(node2
->btree
[be16_to_cpu(node2
->hdr
.count
)-1].hashval
) <
1289 be32_to_cpu(node1
->btree
[be16_to_cpu(node1
->hdr
.count
)-1].hashval
)))) {
1296 * Pick up the last hashvalue from an intermediate node.
1299 xfs_da_node_lasthash(xfs_dabuf_t
*bp
, int *count
)
1301 xfs_da_intnode_t
*node
;
1304 ASSERT(be16_to_cpu(node
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
1306 *count
= be16_to_cpu(node
->hdr
.count
);
1307 if (!node
->hdr
.count
)
1309 return be32_to_cpu(node
->btree
[be16_to_cpu(node
->hdr
.count
)-1].hashval
);
1313 * Unlink a block from a doubly linked list of blocks.
1315 STATIC
int /* error */
1316 xfs_da_blk_unlink(xfs_da_state_t
*state
, xfs_da_state_blk_t
*drop_blk
,
1317 xfs_da_state_blk_t
*save_blk
)
1319 xfs_da_blkinfo_t
*drop_info
, *save_info
, *tmp_info
;
1320 xfs_da_args_t
*args
;
1325 * Set up environment.
1328 ASSERT(args
!= NULL
);
1329 save_info
= save_blk
->bp
->data
;
1330 drop_info
= drop_blk
->bp
->data
;
1331 ASSERT(save_blk
->magic
== XFS_DA_NODE_MAGIC
||
1332 save_blk
->magic
== XFS_DIR2_LEAFN_MAGIC
||
1333 save_blk
->magic
== XFS_ATTR_LEAF_MAGIC
);
1334 ASSERT(save_blk
->magic
== be16_to_cpu(save_info
->magic
));
1335 ASSERT(drop_blk
->magic
== be16_to_cpu(drop_info
->magic
));
1336 ASSERT(save_blk
->magic
== drop_blk
->magic
);
1337 ASSERT((be32_to_cpu(save_info
->forw
) == drop_blk
->blkno
) ||
1338 (be32_to_cpu(save_info
->back
) == drop_blk
->blkno
));
1339 ASSERT((be32_to_cpu(drop_info
->forw
) == save_blk
->blkno
) ||
1340 (be32_to_cpu(drop_info
->back
) == save_blk
->blkno
));
1343 * Unlink the leaf block from the doubly linked chain of leaves.
1345 if (be32_to_cpu(save_info
->back
) == drop_blk
->blkno
) {
1346 save_info
->back
= drop_info
->back
;
1347 if (drop_info
->back
) {
1348 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1349 be32_to_cpu(drop_info
->back
),
1350 -1, &bp
, args
->whichfork
);
1354 tmp_info
= bp
->data
;
1355 ASSERT(tmp_info
->magic
== save_info
->magic
);
1356 ASSERT(be32_to_cpu(tmp_info
->forw
) == drop_blk
->blkno
);
1357 tmp_info
->forw
= cpu_to_be32(save_blk
->blkno
);
1358 xfs_da_log_buf(args
->trans
, bp
, 0,
1359 sizeof(*tmp_info
) - 1);
1360 xfs_da_buf_done(bp
);
1363 save_info
->forw
= drop_info
->forw
;
1364 if (drop_info
->forw
) {
1365 error
= xfs_da_read_buf(args
->trans
, args
->dp
,
1366 be32_to_cpu(drop_info
->forw
),
1367 -1, &bp
, args
->whichfork
);
1371 tmp_info
= bp
->data
;
1372 ASSERT(tmp_info
->magic
== save_info
->magic
);
1373 ASSERT(be32_to_cpu(tmp_info
->back
) == drop_blk
->blkno
);
1374 tmp_info
->back
= cpu_to_be32(save_blk
->blkno
);
1375 xfs_da_log_buf(args
->trans
, bp
, 0,
1376 sizeof(*tmp_info
) - 1);
1377 xfs_da_buf_done(bp
);
1381 xfs_da_log_buf(args
->trans
, save_blk
->bp
, 0, sizeof(*save_info
) - 1);
1386 * Move a path "forward" or "!forward" one block at the current level.
1388 * This routine will adjust a "path" to point to the next block
1389 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1390 * Btree, including updating pointers to the intermediate nodes between
1391 * the new bottom and the root.
1394 xfs_da_path_shift(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
,
1395 int forward
, int release
, int *result
)
1397 xfs_da_state_blk_t
*blk
;
1398 xfs_da_blkinfo_t
*info
;
1399 xfs_da_intnode_t
*node
;
1400 xfs_da_args_t
*args
;
1401 xfs_dablk_t blkno
=0;
1405 * Roll up the Btree looking for the first block where our
1406 * current index is not at the edge of the block. Note that
1407 * we skip the bottom layer because we want the sibling block.
1410 ASSERT(args
!= NULL
);
1411 ASSERT(path
!= NULL
);
1412 ASSERT((path
->active
> 0) && (path
->active
< XFS_DA_NODE_MAXDEPTH
));
1413 level
= (path
->active
-1) - 1; /* skip bottom layer in path */
1414 for (blk
= &path
->blk
[level
]; level
>= 0; blk
--, level
--) {
1415 ASSERT(blk
->bp
!= NULL
);
1416 node
= blk
->bp
->data
;
1417 ASSERT(be16_to_cpu(node
->hdr
.info
.magic
) == XFS_DA_NODE_MAGIC
);
1418 if (forward
&& (blk
->index
< be16_to_cpu(node
->hdr
.count
)-1)) {
1420 blkno
= be32_to_cpu(node
->btree
[blk
->index
].before
);
1422 } else if (!forward
&& (blk
->index
> 0)) {
1424 blkno
= be32_to_cpu(node
->btree
[blk
->index
].before
);
1429 *result
= XFS_ERROR(ENOENT
); /* we're out of our tree */
1430 ASSERT(args
->op_flags
& XFS_DA_OP_OKNOENT
);
1435 * Roll down the edge of the subtree until we reach the
1436 * same depth we were at originally.
1438 for (blk
++, level
++; level
< path
->active
; blk
++, level
++) {
1440 * Release the old block.
1441 * (if it's dirty, trans won't actually let go)
1444 xfs_da_brelse(args
->trans
, blk
->bp
);
1447 * Read the next child block.
1450 error
= xfs_da_read_buf(args
->trans
, args
->dp
, blkno
, -1,
1451 &blk
->bp
, args
->whichfork
);
1454 ASSERT(blk
->bp
!= NULL
);
1455 info
= blk
->bp
->data
;
1456 ASSERT(be16_to_cpu(info
->magic
) == XFS_DA_NODE_MAGIC
||
1457 be16_to_cpu(info
->magic
) == XFS_DIR2_LEAFN_MAGIC
||
1458 be16_to_cpu(info
->magic
) == XFS_ATTR_LEAF_MAGIC
);
1459 blk
->magic
= be16_to_cpu(info
->magic
);
1460 if (blk
->magic
== XFS_DA_NODE_MAGIC
) {
1461 node
= (xfs_da_intnode_t
*)info
;
1462 blk
->hashval
= be32_to_cpu(node
->btree
[be16_to_cpu(node
->hdr
.count
)-1].hashval
);
1466 blk
->index
= be16_to_cpu(node
->hdr
.count
)-1;
1467 blkno
= be32_to_cpu(node
->btree
[blk
->index
].before
);
1469 ASSERT(level
== path
->active
-1);
1471 switch(blk
->magic
) {
1472 case XFS_ATTR_LEAF_MAGIC
:
1473 blk
->hashval
= xfs_attr_leaf_lasthash(blk
->bp
,
1476 case XFS_DIR2_LEAFN_MAGIC
:
1477 blk
->hashval
= xfs_dir2_leafn_lasthash(blk
->bp
,
1481 ASSERT(blk
->magic
== XFS_ATTR_LEAF_MAGIC
||
1482 blk
->magic
== XFS_DIR2_LEAFN_MAGIC
);
1492 /*========================================================================
1494 *========================================================================*/
1497 * Implement a simple hash on a character string.
1498 * Rotate the hash value by 7 bits, then XOR each character in.
1499 * This is implemented with some source-level loop unrolling.
1502 xfs_da_hashname(const __uint8_t
*name
, int namelen
)
1507 * Do four characters at a time as long as we can.
1509 for (hash
= 0; namelen
>= 4; namelen
-= 4, name
+= 4)
1510 hash
= (name
[0] << 21) ^ (name
[1] << 14) ^ (name
[2] << 7) ^
1511 (name
[3] << 0) ^ rol32(hash
, 7 * 4);
1514 * Now do the rest of the characters.
1518 return (name
[0] << 14) ^ (name
[1] << 7) ^ (name
[2] << 0) ^
1521 return (name
[0] << 7) ^ (name
[1] << 0) ^ rol32(hash
, 7 * 2);
1523 return (name
[0] << 0) ^ rol32(hash
, 7 * 1);
1524 default: /* case 0: */
1531 struct xfs_da_args
*args
,
1532 const unsigned char *name
,
1535 return (args
->namelen
== len
&& memcmp(args
->name
, name
, len
) == 0) ?
1536 XFS_CMP_EXACT
: XFS_CMP_DIFFERENT
;
1540 xfs_default_hashname(
1541 struct xfs_name
*name
)
1543 return xfs_da_hashname(name
->name
, name
->len
);
1546 const struct xfs_nameops xfs_default_nameops
= {
1547 .hashname
= xfs_default_hashname
,
1548 .compname
= xfs_da_compname
1552 * Add a block to the btree ahead of the file.
1553 * Return the new block number to the caller.
1556 xfs_da_grow_inode(xfs_da_args_t
*args
, xfs_dablk_t
*new_blkno
)
1558 xfs_fileoff_t bno
, b
;
1559 xfs_bmbt_irec_t map
;
1560 xfs_bmbt_irec_t
*mapp
;
1562 int nmap
, error
, w
, count
, c
, got
, i
, mapi
;
1565 xfs_drfsbno_t nblks
;
1569 w
= args
->whichfork
;
1571 nblks
= dp
->i_d
.di_nblocks
;
1574 * For new directories adjust the file offset and block count.
1576 if (w
== XFS_DATA_FORK
) {
1577 bno
= mp
->m_dirleafblk
;
1578 count
= mp
->m_dirblkfsbs
;
1584 * Find a spot in the file space to put the new block.
1586 if ((error
= xfs_bmap_first_unused(tp
, dp
, count
, &bno
, w
)))
1588 if (w
== XFS_DATA_FORK
)
1589 ASSERT(bno
>= mp
->m_dirleafblk
&& bno
< mp
->m_dirfreeblk
);
1591 * Try mapping it in one filesystem block.
1594 ASSERT(args
->firstblock
!= NULL
);
1595 if ((error
= xfs_bmapi(tp
, dp
, bno
, count
,
1596 xfs_bmapi_aflag(w
)|XFS_BMAPI_WRITE
|XFS_BMAPI_METADATA
|
1598 args
->firstblock
, args
->total
, &map
, &nmap
,
1608 * If we didn't get it and the block might work if fragmented,
1609 * try without the CONTIG flag. Loop until we get it all.
1611 else if (nmap
== 0 && count
> 1) {
1612 mapp
= kmem_alloc(sizeof(*mapp
) * count
, KM_SLEEP
);
1613 for (b
= bno
, mapi
= 0; b
< bno
+ count
; ) {
1614 nmap
= MIN(XFS_BMAP_MAX_NMAP
, count
);
1615 c
= (int)(bno
+ count
- b
);
1616 if ((error
= xfs_bmapi(tp
, dp
, b
, c
,
1617 xfs_bmapi_aflag(w
)|XFS_BMAPI_WRITE
|
1619 args
->firstblock
, args
->total
,
1620 &mapp
[mapi
], &nmap
, args
->flist
))) {
1627 b
= mapp
[mapi
- 1].br_startoff
+
1628 mapp
[mapi
- 1].br_blockcount
;
1635 * Count the blocks we got, make sure it matches the total.
1637 for (i
= 0, got
= 0; i
< mapi
; i
++)
1638 got
+= mapp
[i
].br_blockcount
;
1639 if (got
!= count
|| mapp
[0].br_startoff
!= bno
||
1640 mapp
[mapi
- 1].br_startoff
+ mapp
[mapi
- 1].br_blockcount
!=
1644 return XFS_ERROR(ENOSPC
);
1648 /* account for newly allocated blocks in reserved blocks total */
1649 args
->total
-= dp
->i_d
.di_nblocks
- nblks
;
1650 *new_blkno
= (xfs_dablk_t
)bno
;
1655 * Ick. We need to always be able to remove a btree block, even
1656 * if there's no space reservation because the filesystem is full.
1657 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
1658 * It swaps the target block with the last block in the file. The
1659 * last block in the file can always be removed since it can't cause
1660 * a bmap btree split to do that.
1663 xfs_da_swap_lastblock(xfs_da_args_t
*args
, xfs_dablk_t
*dead_blknop
,
1664 xfs_dabuf_t
**dead_bufp
)
1666 xfs_dablk_t dead_blkno
, last_blkno
, sib_blkno
, par_blkno
;
1667 xfs_dabuf_t
*dead_buf
, *last_buf
, *sib_buf
, *par_buf
;
1668 xfs_fileoff_t lastoff
;
1672 int error
, w
, entno
, level
, dead_level
;
1673 xfs_da_blkinfo_t
*dead_info
, *sib_info
;
1674 xfs_da_intnode_t
*par_node
, *dead_node
;
1675 xfs_dir2_leaf_t
*dead_leaf2
;
1676 xfs_dahash_t dead_hash
;
1678 dead_buf
= *dead_bufp
;
1679 dead_blkno
= *dead_blknop
;
1682 w
= args
->whichfork
;
1683 ASSERT(w
== XFS_DATA_FORK
);
1685 lastoff
= mp
->m_dirfreeblk
;
1686 error
= xfs_bmap_last_before(tp
, ip
, &lastoff
, w
);
1689 if (unlikely(lastoff
== 0)) {
1690 XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW
,
1692 return XFS_ERROR(EFSCORRUPTED
);
1695 * Read the last block in the btree space.
1697 last_blkno
= (xfs_dablk_t
)lastoff
- mp
->m_dirblkfsbs
;
1698 if ((error
= xfs_da_read_buf(tp
, ip
, last_blkno
, -1, &last_buf
, w
)))
1701 * Copy the last block into the dead buffer and log it.
1703 memcpy(dead_buf
->data
, last_buf
->data
, mp
->m_dirblksize
);
1704 xfs_da_log_buf(tp
, dead_buf
, 0, mp
->m_dirblksize
- 1);
1705 dead_info
= dead_buf
->data
;
1707 * Get values from the moved block.
1709 if (be16_to_cpu(dead_info
->magic
) == XFS_DIR2_LEAFN_MAGIC
) {
1710 dead_leaf2
= (xfs_dir2_leaf_t
*)dead_info
;
1712 dead_hash
= be32_to_cpu(dead_leaf2
->ents
[be16_to_cpu(dead_leaf2
->hdr
.count
) - 1].hashval
);
1714 ASSERT(be16_to_cpu(dead_info
->magic
) == XFS_DA_NODE_MAGIC
);
1715 dead_node
= (xfs_da_intnode_t
*)dead_info
;
1716 dead_level
= be16_to_cpu(dead_node
->hdr
.level
);
1717 dead_hash
= be32_to_cpu(dead_node
->btree
[be16_to_cpu(dead_node
->hdr
.count
) - 1].hashval
);
1719 sib_buf
= par_buf
= NULL
;
1721 * If the moved block has a left sibling, fix up the pointers.
1723 if ((sib_blkno
= be32_to_cpu(dead_info
->back
))) {
1724 if ((error
= xfs_da_read_buf(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
)))
1726 sib_info
= sib_buf
->data
;
1728 be32_to_cpu(sib_info
->forw
) != last_blkno
||
1729 sib_info
->magic
!= dead_info
->magic
)) {
1730 XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
1731 XFS_ERRLEVEL_LOW
, mp
);
1732 error
= XFS_ERROR(EFSCORRUPTED
);
1735 sib_info
->forw
= cpu_to_be32(dead_blkno
);
1736 xfs_da_log_buf(tp
, sib_buf
,
1737 XFS_DA_LOGRANGE(sib_info
, &sib_info
->forw
,
1738 sizeof(sib_info
->forw
)));
1739 xfs_da_buf_done(sib_buf
);
1743 * If the moved block has a right sibling, fix up the pointers.
1745 if ((sib_blkno
= be32_to_cpu(dead_info
->forw
))) {
1746 if ((error
= xfs_da_read_buf(tp
, ip
, sib_blkno
, -1, &sib_buf
, w
)))
1748 sib_info
= sib_buf
->data
;
1750 be32_to_cpu(sib_info
->back
) != last_blkno
||
1751 sib_info
->magic
!= dead_info
->magic
)) {
1752 XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
1753 XFS_ERRLEVEL_LOW
, mp
);
1754 error
= XFS_ERROR(EFSCORRUPTED
);
1757 sib_info
->back
= cpu_to_be32(dead_blkno
);
1758 xfs_da_log_buf(tp
, sib_buf
,
1759 XFS_DA_LOGRANGE(sib_info
, &sib_info
->back
,
1760 sizeof(sib_info
->back
)));
1761 xfs_da_buf_done(sib_buf
);
1764 par_blkno
= mp
->m_dirleafblk
;
1767 * Walk down the tree looking for the parent of the moved block.
1770 if ((error
= xfs_da_read_buf(tp
, ip
, par_blkno
, -1, &par_buf
, w
)))
1772 par_node
= par_buf
->data
;
1774 be16_to_cpu(par_node
->hdr
.info
.magic
) != XFS_DA_NODE_MAGIC
||
1775 (level
>= 0 && level
!= be16_to_cpu(par_node
->hdr
.level
) + 1))) {
1776 XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
1777 XFS_ERRLEVEL_LOW
, mp
);
1778 error
= XFS_ERROR(EFSCORRUPTED
);
1781 level
= be16_to_cpu(par_node
->hdr
.level
);
1783 entno
< be16_to_cpu(par_node
->hdr
.count
) &&
1784 be32_to_cpu(par_node
->btree
[entno
].hashval
) < dead_hash
;
1787 if (unlikely(entno
== be16_to_cpu(par_node
->hdr
.count
))) {
1788 XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
1789 XFS_ERRLEVEL_LOW
, mp
);
1790 error
= XFS_ERROR(EFSCORRUPTED
);
1793 par_blkno
= be32_to_cpu(par_node
->btree
[entno
].before
);
1794 if (level
== dead_level
+ 1)
1796 xfs_da_brelse(tp
, par_buf
);
1800 * We're in the right parent block.
1801 * Look for the right entry.
1805 entno
< be16_to_cpu(par_node
->hdr
.count
) &&
1806 be32_to_cpu(par_node
->btree
[entno
].before
) != last_blkno
;
1809 if (entno
< be16_to_cpu(par_node
->hdr
.count
))
1811 par_blkno
= be32_to_cpu(par_node
->hdr
.info
.forw
);
1812 xfs_da_brelse(tp
, par_buf
);
1814 if (unlikely(par_blkno
== 0)) {
1815 XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
1816 XFS_ERRLEVEL_LOW
, mp
);
1817 error
= XFS_ERROR(EFSCORRUPTED
);
1820 if ((error
= xfs_da_read_buf(tp
, ip
, par_blkno
, -1, &par_buf
, w
)))
1822 par_node
= par_buf
->data
;
1824 be16_to_cpu(par_node
->hdr
.level
) != level
||
1825 be16_to_cpu(par_node
->hdr
.info
.magic
) != XFS_DA_NODE_MAGIC
)) {
1826 XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
1827 XFS_ERRLEVEL_LOW
, mp
);
1828 error
= XFS_ERROR(EFSCORRUPTED
);
1834 * Update the parent entry pointing to the moved block.
1836 par_node
->btree
[entno
].before
= cpu_to_be32(dead_blkno
);
1837 xfs_da_log_buf(tp
, par_buf
,
1838 XFS_DA_LOGRANGE(par_node
, &par_node
->btree
[entno
].before
,
1839 sizeof(par_node
->btree
[entno
].before
)));
1840 xfs_da_buf_done(par_buf
);
1841 xfs_da_buf_done(dead_buf
);
1842 *dead_blknop
= last_blkno
;
1843 *dead_bufp
= last_buf
;
1847 xfs_da_brelse(tp
, par_buf
);
1849 xfs_da_brelse(tp
, sib_buf
);
1850 xfs_da_brelse(tp
, last_buf
);
1855 * Remove a btree block from a directory or attribute.
1858 xfs_da_shrink_inode(xfs_da_args_t
*args
, xfs_dablk_t dead_blkno
,
1859 xfs_dabuf_t
*dead_buf
)
1862 int done
, error
, w
, count
;
1867 w
= args
->whichfork
;
1870 if (w
== XFS_DATA_FORK
)
1871 count
= mp
->m_dirblkfsbs
;
1876 * Remove extents. If we get ENOSPC for a dir we have to move
1877 * the last block to the place we want to kill.
1879 if ((error
= xfs_bunmapi(tp
, dp
, dead_blkno
, count
,
1880 xfs_bmapi_aflag(w
)|XFS_BMAPI_METADATA
,
1881 0, args
->firstblock
, args
->flist
,
1882 &done
)) == ENOSPC
) {
1883 if (w
!= XFS_DATA_FORK
)
1885 if ((error
= xfs_da_swap_lastblock(args
, &dead_blkno
,
1892 xfs_da_binval(tp
, dead_buf
);
1897 * See if the mapping(s) for this btree block are valid, i.e.
1898 * don't contain holes, are logically contiguous, and cover the whole range.
1901 xfs_da_map_covers_blocks(
1903 xfs_bmbt_irec_t
*mapp
,
1910 for (i
= 0, off
= bno
; i
< nmap
; i
++) {
1911 if (mapp
[i
].br_startblock
== HOLESTARTBLOCK
||
1912 mapp
[i
].br_startblock
== DELAYSTARTBLOCK
) {
1915 if (off
!= mapp
[i
].br_startoff
) {
1918 off
+= mapp
[i
].br_blockcount
;
1920 return off
== bno
+ count
;
1925 * Used for get_buf, read_buf, read_bufr, and reada_buf.
1932 xfs_daddr_t
*mappedbnop
,
1938 xfs_buf_t
*bp
= NULL
;
1942 xfs_bmbt_irec_t map
;
1943 xfs_bmbt_irec_t
*mapp
;
1944 xfs_daddr_t mappedbno
;
1952 nfsb
= (whichfork
== XFS_DATA_FORK
) ? mp
->m_dirblkfsbs
: 1;
1953 mappedbno
= *mappedbnop
;
1955 * Caller doesn't have a mapping. -2 means don't complain
1956 * if we land in a hole.
1958 if (mappedbno
== -1 || mappedbno
== -2) {
1960 * Optimize the one-block case.
1966 xfs_bmapi_single(trans
, dp
, whichfork
, &fsb
,
1967 (xfs_fileoff_t
)bno
))) {
1971 if (fsb
== NULLFSBLOCK
) {
1974 map
.br_startblock
= fsb
;
1975 map
.br_startoff
= (xfs_fileoff_t
)bno
;
1976 map
.br_blockcount
= 1;
1980 mapp
= kmem_alloc(sizeof(*mapp
) * nfsb
, KM_SLEEP
);
1982 if ((error
= xfs_bmapi(trans
, dp
, (xfs_fileoff_t
)bno
,
1984 XFS_BMAPI_METADATA
|
1985 xfs_bmapi_aflag(whichfork
),
1986 NULL
, 0, mapp
, &nmap
, NULL
)))
1990 map
.br_startblock
= XFS_DADDR_TO_FSB(mp
, mappedbno
);
1991 map
.br_startoff
= (xfs_fileoff_t
)bno
;
1992 map
.br_blockcount
= nfsb
;
1996 if (!xfs_da_map_covers_blocks(nmap
, mapp
, bno
, nfsb
)) {
1997 error
= mappedbno
== -2 ? 0 : XFS_ERROR(EFSCORRUPTED
);
1998 if (unlikely(error
== EFSCORRUPTED
)) {
1999 if (xfs_error_level
>= XFS_ERRLEVEL_LOW
) {
2000 cmn_err(CE_ALERT
, "xfs_da_do_buf: bno %lld\n",
2002 cmn_err(CE_ALERT
, "dir: inode %lld\n",
2003 (long long)dp
->i_ino
);
2004 for (i
= 0; i
< nmap
; i
++) {
2006 "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d\n",
2008 (long long)mapp
[i
].br_startoff
,
2009 (long long)mapp
[i
].br_startblock
,
2010 (long long)mapp
[i
].br_blockcount
,
2014 XFS_ERROR_REPORT("xfs_da_do_buf(1)",
2015 XFS_ERRLEVEL_LOW
, mp
);
2019 if (caller
!= 3 && nmap
> 1) {
2020 bplist
= kmem_alloc(sizeof(*bplist
) * nmap
, KM_SLEEP
);
2025 * Turn the mapping(s) into buffer(s).
2027 for (i
= 0; i
< nmap
; i
++) {
2030 mappedbno
= XFS_FSB_TO_DADDR(mp
, mapp
[i
].br_startblock
);
2032 *mappedbnop
= mappedbno
;
2033 nmapped
= (int)XFS_FSB_TO_BB(mp
, mapp
[i
].br_blockcount
);
2036 bp
= xfs_trans_get_buf(trans
, mp
->m_ddev_targp
,
2037 mappedbno
, nmapped
, 0);
2038 error
= bp
? XFS_BUF_GETERROR(bp
) : XFS_ERROR(EIO
);
2043 error
= xfs_trans_read_buf(mp
, trans
, mp
->m_ddev_targp
,
2044 mappedbno
, nmapped
, 0, &bp
);
2047 xfs_baread(mp
->m_ddev_targp
, mappedbno
, nmapped
);
2054 xfs_trans_brelse(trans
, bp
);
2060 if (whichfork
== XFS_ATTR_FORK
) {
2061 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_ATTR_BTREE
,
2062 XFS_ATTR_BTREE_REF
);
2064 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_DIR_BTREE
,
2069 bplist
[nbplist
++] = bp
;
2073 * Build a dabuf structure.
2076 rbp
= xfs_da_buf_make(nbplist
, bplist
, ra
);
2078 rbp
= xfs_da_buf_make(1, &bp
, ra
);
2082 * For read_buf, check the magic number.
2085 xfs_dir2_data_t
*data
;
2086 xfs_dir2_free_t
*free
;
2087 xfs_da_blkinfo_t
*info
;
2093 magic
= be16_to_cpu(info
->magic
);
2094 magic1
= be32_to_cpu(data
->hdr
.magic
);
2096 XFS_TEST_ERROR((magic
!= XFS_DA_NODE_MAGIC
) &&
2097 (magic
!= XFS_ATTR_LEAF_MAGIC
) &&
2098 (magic
!= XFS_DIR2_LEAF1_MAGIC
) &&
2099 (magic
!= XFS_DIR2_LEAFN_MAGIC
) &&
2100 (magic1
!= XFS_DIR2_BLOCK_MAGIC
) &&
2101 (magic1
!= XFS_DIR2_DATA_MAGIC
) &&
2102 (be32_to_cpu(free
->hdr
.magic
) != XFS_DIR2_FREE_MAGIC
),
2103 mp
, XFS_ERRTAG_DA_READ_BUF
,
2104 XFS_RANDOM_DA_READ_BUF
))) {
2105 trace_xfs_da_btree_corrupt(rbp
->bps
[0], _RET_IP_
);
2106 XFS_CORRUPTION_ERROR("xfs_da_do_buf(2)",
2107 XFS_ERRLEVEL_LOW
, mp
, info
);
2108 error
= XFS_ERROR(EFSCORRUPTED
);
2109 xfs_da_brelse(trans
, rbp
);
2125 for (i
= 0; i
< nbplist
; i
++)
2126 xfs_trans_brelse(trans
, bplist
[i
]);
2138 * Get a buffer for the dir/attr block.
2145 xfs_daddr_t mappedbno
,
2149 return xfs_da_do_buf(trans
, dp
, bno
, &mappedbno
, bpp
, whichfork
, 0,
2150 (inst_t
*)__return_address
);
2154 * Get a buffer for the dir/attr block, fill in the contents.
2161 xfs_daddr_t mappedbno
,
2165 return xfs_da_do_buf(trans
, dp
, bno
, &mappedbno
, bpp
, whichfork
, 1,
2166 (inst_t
*)__return_address
);
2170 * Readahead the dir/attr block.
2182 if (xfs_da_do_buf(trans
, dp
, bno
, &rval
, NULL
, whichfork
, 3,
2183 (inst_t
*)__return_address
))
2189 kmem_zone_t
*xfs_da_state_zone
; /* anchor for state struct zone */
2190 kmem_zone_t
*xfs_dabuf_zone
; /* dabuf zone */
2193 * Allocate a dir-state structure.
2194 * We don't put them on the stack since they're large.
2197 xfs_da_state_alloc(void)
2199 return kmem_zone_zalloc(xfs_da_state_zone
, KM_NOFS
);
2203 * Kill the altpath contents of a da-state structure.
2206 xfs_da_state_kill_altpath(xfs_da_state_t
*state
)
2210 for (i
= 0; i
< state
->altpath
.active
; i
++) {
2211 if (state
->altpath
.blk
[i
].bp
) {
2212 if (state
->altpath
.blk
[i
].bp
!= state
->path
.blk
[i
].bp
)
2213 xfs_da_buf_done(state
->altpath
.blk
[i
].bp
);
2214 state
->altpath
.blk
[i
].bp
= NULL
;
2217 state
->altpath
.active
= 0;
2221 * Free a da-state structure.
2224 xfs_da_state_free(xfs_da_state_t
*state
)
2228 xfs_da_state_kill_altpath(state
);
2229 for (i
= 0; i
< state
->path
.active
; i
++) {
2230 if (state
->path
.blk
[i
].bp
)
2231 xfs_da_buf_done(state
->path
.blk
[i
].bp
);
2233 if (state
->extravalid
&& state
->extrablk
.bp
)
2234 xfs_da_buf_done(state
->extrablk
.bp
);
2236 memset((char *)state
, 0, sizeof(*state
));
2238 kmem_zone_free(xfs_da_state_zone
, state
);
2241 #ifdef XFS_DABUF_DEBUG
2242 xfs_dabuf_t
*xfs_dabuf_global_list
;
2243 static DEFINE_SPINLOCK(xfs_dabuf_global_lock
);
2250 STATIC xfs_dabuf_t
*
2251 xfs_da_buf_make(int nbuf
, xfs_buf_t
**bps
, inst_t
*ra
)
2259 dabuf
= kmem_zone_alloc(xfs_dabuf_zone
, KM_NOFS
);
2261 dabuf
= kmem_alloc(XFS_DA_BUF_SIZE(nbuf
), KM_NOFS
);
2263 #ifdef XFS_DABUF_DEBUG
2265 dabuf
->target
= XFS_BUF_TARGET(bps
[0]);
2266 dabuf
->blkno
= XFS_BUF_ADDR(bps
[0]);
2271 dabuf
->bbcount
= (short)BTOBB(XFS_BUF_COUNT(bp
));
2272 dabuf
->data
= XFS_BUF_PTR(bp
);
2276 for (i
= 0, dabuf
->bbcount
= 0; i
< nbuf
; i
++) {
2277 dabuf
->bps
[i
] = bp
= bps
[i
];
2278 dabuf
->bbcount
+= BTOBB(XFS_BUF_COUNT(bp
));
2280 dabuf
->data
= kmem_alloc(BBTOB(dabuf
->bbcount
), KM_SLEEP
);
2281 for (i
= off
= 0; i
< nbuf
; i
++, off
+= XFS_BUF_COUNT(bp
)) {
2283 memcpy((char *)dabuf
->data
+ off
, XFS_BUF_PTR(bp
),
2287 #ifdef XFS_DABUF_DEBUG
2291 spin_lock(&xfs_dabuf_global_lock
);
2292 for (p
= xfs_dabuf_global_list
; p
; p
= p
->next
) {
2293 ASSERT(p
->blkno
!= dabuf
->blkno
||
2294 p
->target
!= dabuf
->target
);
2297 if (xfs_dabuf_global_list
)
2298 xfs_dabuf_global_list
->prev
= dabuf
;
2299 dabuf
->next
= xfs_dabuf_global_list
;
2300 xfs_dabuf_global_list
= dabuf
;
2301 spin_unlock(&xfs_dabuf_global_lock
);
2311 xfs_da_buf_clean(xfs_dabuf_t
*dabuf
)
2318 ASSERT(dabuf
->nbuf
> 1);
2320 for (i
= off
= 0; i
< dabuf
->nbuf
;
2321 i
++, off
+= XFS_BUF_COUNT(bp
)) {
2323 memcpy(XFS_BUF_PTR(bp
), (char *)dabuf
->data
+ off
,
2333 xfs_da_buf_done(xfs_dabuf_t
*dabuf
)
2336 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2338 xfs_da_buf_clean(dabuf
);
2339 if (dabuf
->nbuf
> 1)
2340 kmem_free(dabuf
->data
);
2341 #ifdef XFS_DABUF_DEBUG
2343 spin_lock(&xfs_dabuf_global_lock
);
2345 dabuf
->prev
->next
= dabuf
->next
;
2347 xfs_dabuf_global_list
= dabuf
->next
;
2349 dabuf
->next
->prev
= dabuf
->prev
;
2350 spin_unlock(&xfs_dabuf_global_lock
);
2352 memset(dabuf
, 0, XFS_DA_BUF_SIZE(dabuf
->nbuf
));
2354 if (dabuf
->nbuf
== 1)
2355 kmem_zone_free(xfs_dabuf_zone
, dabuf
);
2361 * Log transaction from a dabuf.
2364 xfs_da_log_buf(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
, uint first
, uint last
)
2372 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2373 if (dabuf
->nbuf
== 1) {
2374 ASSERT(dabuf
->data
== (void *)XFS_BUF_PTR(dabuf
->bps
[0]));
2375 xfs_trans_log_buf(tp
, dabuf
->bps
[0], first
, last
);
2379 ASSERT(first
<= last
);
2380 for (i
= off
= 0; i
< dabuf
->nbuf
; i
++, off
+= XFS_BUF_COUNT(bp
)) {
2383 l
= f
+ XFS_BUF_COUNT(bp
) - 1;
2389 xfs_trans_log_buf(tp
, bp
, f
- off
, l
- off
);
2391 * B_DONE is set by xfs_trans_log buf.
2392 * If we don't set it on a new buffer (get not read)
2393 * then if we don't put anything in the buffer it won't
2394 * be set, and at commit it it released into the cache,
2395 * and then a read will fail.
2397 else if (!(XFS_BUF_ISDONE(bp
)))
2404 * Release dabuf from a transaction.
2405 * Have to free up the dabuf before the buffers are released,
2406 * since the synchronization on the dabuf is really the lock on the buffer.
2409 xfs_da_brelse(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
)
2416 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2417 if ((nbuf
= dabuf
->nbuf
) == 1) {
2421 bplist
= kmem_alloc(nbuf
* sizeof(*bplist
), KM_SLEEP
);
2422 memcpy(bplist
, dabuf
->bps
, nbuf
* sizeof(*bplist
));
2424 xfs_da_buf_done(dabuf
);
2425 for (i
= 0; i
< nbuf
; i
++)
2426 xfs_trans_brelse(tp
, bplist
[i
]);
2432 * Invalidate dabuf from a transaction.
2435 xfs_da_binval(xfs_trans_t
*tp
, xfs_dabuf_t
*dabuf
)
2442 ASSERT(dabuf
->nbuf
&& dabuf
->data
&& dabuf
->bbcount
&& dabuf
->bps
[0]);
2443 if ((nbuf
= dabuf
->nbuf
) == 1) {
2447 bplist
= kmem_alloc(nbuf
* sizeof(*bplist
), KM_SLEEP
);
2448 memcpy(bplist
, dabuf
->bps
, nbuf
* sizeof(*bplist
));
2450 xfs_da_buf_done(dabuf
);
2451 for (i
= 0; i
< nbuf
; i
++)
2452 xfs_trans_binval(tp
, bplist
[i
]);
2458 * Get the first daddr from a dabuf.
2461 xfs_da_blkno(xfs_dabuf_t
*dabuf
)
2463 ASSERT(dabuf
->nbuf
);
2464 ASSERT(dabuf
->data
);
2465 return XFS_BUF_ADDR(dabuf
->bps
[0]);