Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 : /*
3 : * Copyright (c) 2000-2005 Silicon Graphics, Inc.
4 : * Copyright (c) 2013 Red Hat, Inc.
5 : * All Rights Reserved.
6 : */
7 : #include "xfs.h"
8 : #include "xfs_fs.h"
9 : #include "xfs_shared.h"
10 : #include "xfs_format.h"
11 : #include "xfs_log_format.h"
12 : #include "xfs_trans_resv.h"
13 : #include "xfs_bit.h"
14 : #include "xfs_mount.h"
15 : #include "xfs_inode.h"
16 : #include "xfs_dir2.h"
17 : #include "xfs_dir2_priv.h"
18 : #include "xfs_trans.h"
19 : #include "xfs_bmap.h"
20 : #include "xfs_attr_leaf.h"
21 : #include "xfs_error.h"
22 : #include "xfs_trace.h"
23 : #include "xfs_buf_item.h"
24 : #include "xfs_log.h"
25 : #include "xfs_errortag.h"
26 : #include "xfs_health.h"
27 :
28 : /*
29 : * xfs_da_btree.c
30 : *
31 : * Routines to implement directories as Btrees of hashed names.
32 : */
33 :
34 : /*========================================================================
35 : * Function prototypes for the kernel.
36 : *========================================================================*/
37 :
38 : /*
39 : * Routines used for growing the Btree.
40 : */
41 : STATIC int xfs_da3_root_split(xfs_da_state_t *state,
42 : xfs_da_state_blk_t *existing_root,
43 : xfs_da_state_blk_t *new_child);
44 : STATIC int xfs_da3_node_split(xfs_da_state_t *state,
45 : xfs_da_state_blk_t *existing_blk,
46 : xfs_da_state_blk_t *split_blk,
47 : xfs_da_state_blk_t *blk_to_add,
48 : int treelevel,
49 : int *result);
50 : STATIC void xfs_da3_node_rebalance(xfs_da_state_t *state,
51 : xfs_da_state_blk_t *node_blk_1,
52 : xfs_da_state_blk_t *node_blk_2);
53 : STATIC void xfs_da3_node_add(xfs_da_state_t *state,
54 : xfs_da_state_blk_t *old_node_blk,
55 : xfs_da_state_blk_t *new_node_blk);
56 :
57 : /*
58 : * Routines used for shrinking the Btree.
59 : */
60 : STATIC int xfs_da3_root_join(xfs_da_state_t *state,
61 : xfs_da_state_blk_t *root_blk);
62 : STATIC int xfs_da3_node_toosmall(xfs_da_state_t *state, int *retval);
63 : STATIC void xfs_da3_node_remove(xfs_da_state_t *state,
64 : xfs_da_state_blk_t *drop_blk);
65 : STATIC void xfs_da3_node_unbalance(xfs_da_state_t *state,
66 : xfs_da_state_blk_t *src_node_blk,
67 : xfs_da_state_blk_t *dst_node_blk);
68 :
69 : /*
70 : * Utility routines.
71 : */
72 : STATIC int xfs_da3_blk_unlink(xfs_da_state_t *state,
73 : xfs_da_state_blk_t *drop_blk,
74 : xfs_da_state_blk_t *save_blk);
75 :
76 :
77 : struct kmem_cache *xfs_da_state_cache; /* anchor for dir/attr state */
78 :
79 : /*
80 : * Allocate a dir-state structure.
81 : * We don't put them on the stack since they're large.
82 : */
83 : struct xfs_da_state *
84 149682528 : xfs_da_state_alloc(
85 : struct xfs_da_args *args)
86 : {
87 149682528 : struct xfs_da_state *state;
88 :
89 149682528 : state = kmem_cache_zalloc(xfs_da_state_cache, GFP_NOFS | __GFP_NOFAIL);
90 149683658 : state->args = args;
91 149683658 : state->mp = args->dp->i_mount;
92 149683658 : return state;
93 : }
94 :
95 : /*
96 : * Kill the altpath contents of a da-state structure.
97 : */
98 : STATIC void
99 149718957 : xfs_da_state_kill_altpath(xfs_da_state_t *state)
100 : {
101 149718957 : int i;
102 :
103 149767447 : for (i = 0; i < state->altpath.active; i++)
104 48490 : state->altpath.blk[i].bp = NULL;
105 149718957 : state->altpath.active = 0;
106 149718957 : }
107 :
108 : /*
109 : * Free a da-state structure.
110 : */
111 : void
112 149684679 : xfs_da_state_free(xfs_da_state_t *state)
113 : {
114 149684679 : xfs_da_state_kill_altpath(state);
115 : #ifdef DEBUG
116 149687027 : memset((char *)state, 0, sizeof(*state));
117 : #endif /* DEBUG */
118 149687027 : kmem_cache_free(xfs_da_state_cache, state);
119 149692919 : }
120 :
121 : void
122 9462 : xfs_da_state_reset(
123 : struct xfs_da_state *state,
124 : struct xfs_da_args *args)
125 : {
126 9462 : xfs_da_state_kill_altpath(state);
127 9462 : memset(state, 0, sizeof(struct xfs_da_state));
128 9462 : state->args = args;
129 9462 : state->mp = state->args->dp->i_mount;
130 9462 : }
131 :
132 : static inline int xfs_dabuf_nfsb(struct xfs_mount *mp, int whichfork)
133 : {
134 2132513799 : if (whichfork == XFS_DATA_FORK)
135 818228385 : return mp->m_dir_geo->fsbcount;
136 1314285414 : return mp->m_attr_geo->fsbcount;
137 : }
138 :
139 : void
140 575304865 : xfs_da3_node_hdr_from_disk(
141 : struct xfs_mount *mp,
142 : struct xfs_da3_icnode_hdr *to,
143 : struct xfs_da_intnode *from)
144 : {
145 575304865 : if (xfs_has_crc(mp)) {
146 575304865 : struct xfs_da3_intnode *from3 = (struct xfs_da3_intnode *)from;
147 :
148 575304865 : to->forw = be32_to_cpu(from3->hdr.info.hdr.forw);
149 575304865 : to->back = be32_to_cpu(from3->hdr.info.hdr.back);
150 575304865 : to->magic = be16_to_cpu(from3->hdr.info.hdr.magic);
151 575304865 : to->count = be16_to_cpu(from3->hdr.__count);
152 575304865 : to->level = be16_to_cpu(from3->hdr.__level);
153 575304865 : to->btree = from3->__btree;
154 575304865 : ASSERT(to->magic == XFS_DA3_NODE_MAGIC);
155 : } else {
156 0 : to->forw = be32_to_cpu(from->hdr.info.forw);
157 0 : to->back = be32_to_cpu(from->hdr.info.back);
158 0 : to->magic = be16_to_cpu(from->hdr.info.magic);
159 0 : to->count = be16_to_cpu(from->hdr.__count);
160 0 : to->level = be16_to_cpu(from->hdr.__level);
161 0 : to->btree = from->__btree;
162 0 : ASSERT(to->magic == XFS_DA_NODE_MAGIC);
163 : }
164 575304865 : }
165 :
166 : void
167 327821 : xfs_da3_node_hdr_to_disk(
168 : struct xfs_mount *mp,
169 : struct xfs_da_intnode *to,
170 : struct xfs_da3_icnode_hdr *from)
171 : {
172 327821 : if (xfs_has_crc(mp)) {
173 327821 : struct xfs_da3_intnode *to3 = (struct xfs_da3_intnode *)to;
174 :
175 327821 : ASSERT(from->magic == XFS_DA3_NODE_MAGIC);
176 327821 : to3->hdr.info.hdr.forw = cpu_to_be32(from->forw);
177 327821 : to3->hdr.info.hdr.back = cpu_to_be32(from->back);
178 327821 : to3->hdr.info.hdr.magic = cpu_to_be16(from->magic);
179 327821 : to3->hdr.__count = cpu_to_be16(from->count);
180 655642 : to3->hdr.__level = cpu_to_be16(from->level);
181 : } else {
182 0 : ASSERT(from->magic == XFS_DA_NODE_MAGIC);
183 0 : to->hdr.info.forw = cpu_to_be32(from->forw);
184 0 : to->hdr.info.back = cpu_to_be32(from->back);
185 0 : to->hdr.info.magic = cpu_to_be16(from->magic);
186 0 : to->hdr.__count = cpu_to_be16(from->count);
187 0 : to->hdr.__level = cpu_to_be16(from->level);
188 : }
189 327821 : }
190 :
191 : /*
192 : * Verify an xfs_da3_blkinfo structure. Note that the da3 fields are only
193 : * accessible on v5 filesystems. This header format is common across da node,
194 : * attr leaf and dir leaf blocks.
195 : */
196 : xfs_failaddr_t
197 54011004 : xfs_da3_blkinfo_verify(
198 : struct xfs_buf *bp,
199 : struct xfs_da3_blkinfo *hdr3)
200 : {
201 54011004 : struct xfs_mount *mp = bp->b_mount;
202 54011004 : struct xfs_da_blkinfo *hdr = &hdr3->hdr;
203 :
204 54011004 : if (!xfs_verify_magic16(bp, hdr->magic))
205 0 : return __this_address;
206 :
207 54011184 : if (xfs_has_crc(mp)) {
208 54011184 : if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))
209 0 : return __this_address;
210 54011162 : if (be64_to_cpu(hdr3->blkno) != xfs_buf_daddr(bp))
211 6 : return __this_address;
212 54011226 : if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->lsn)))
213 0 : return __this_address;
214 : }
215 :
216 : return NULL;
217 : }
218 :
219 : static xfs_failaddr_t
220 259687 : xfs_da3_node_verify(
221 : struct xfs_buf *bp)
222 : {
223 259687 : struct xfs_mount *mp = bp->b_mount;
224 259687 : struct xfs_da_intnode *hdr = bp->b_addr;
225 259687 : struct xfs_da3_icnode_hdr ichdr;
226 259687 : xfs_failaddr_t fa;
227 :
228 259687 : xfs_da3_node_hdr_from_disk(mp, &ichdr, hdr);
229 :
230 259687 : fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);
231 259687 : if (fa)
232 : return fa;
233 :
234 259687 : if (ichdr.level == 0)
235 0 : return __this_address;
236 259687 : if (ichdr.level > XFS_DA_NODE_MAXDEPTH)
237 0 : return __this_address;
238 259687 : if (ichdr.count == 0)
239 0 : return __this_address;
240 :
241 : /*
242 : * we don't know if the node is for and attribute or directory tree,
243 : * so only fail if the count is outside both bounds
244 : */
245 259687 : if (ichdr.count > mp->m_dir_geo->node_ents &&
246 0 : ichdr.count > mp->m_attr_geo->node_ents)
247 0 : return __this_address;
248 :
249 : /* XXX: hash order check? */
250 :
251 : return NULL;
252 : }
253 :
254 : xfs_failaddr_t
255 152449397 : xfs_da3_node_header_check(
256 : struct xfs_buf *bp,
257 : xfs_ino_t owner)
258 : {
259 152449397 : struct xfs_mount *mp = bp->b_mount;
260 :
261 152449397 : if (xfs_has_crc(mp)) {
262 152449397 : struct xfs_da3_blkinfo *hdr3 = bp->b_addr;
263 :
264 152449397 : ASSERT(hdr3->hdr.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
265 :
266 152449397 : if (be64_to_cpu(hdr3->owner) != owner)
267 0 : return __this_address;
268 : }
269 :
270 : return NULL;
271 : }
272 :
273 : xfs_failaddr_t
274 2484956 : xfs_da3_header_check(
275 : struct xfs_buf *bp,
276 : xfs_ino_t owner)
277 : {
278 2484956 : struct xfs_mount *mp = bp->b_mount;
279 2484956 : struct xfs_da_blkinfo *hdr = bp->b_addr;
280 :
281 2484956 : if (!xfs_has_crc(mp))
282 : return NULL;
283 :
284 2484956 : switch (hdr->magic) {
285 2229882 : case cpu_to_be16(XFS_ATTR3_LEAF_MAGIC):
286 2229882 : return xfs_attr3_leaf_header_check(bp, owner);
287 53698 : case cpu_to_be16(XFS_DA3_NODE_MAGIC):
288 53698 : return xfs_da3_node_header_check(bp, owner);
289 201376 : case cpu_to_be16(XFS_DIR3_LEAF1_MAGIC):
290 : case cpu_to_be16(XFS_DIR3_LEAFN_MAGIC):
291 201376 : return xfs_dir3_leaf_header_check(bp, owner);
292 : }
293 :
294 0 : ASSERT(0);
295 0 : return NULL;
296 : }
297 :
298 : static void
299 171908 : xfs_da3_node_write_verify(
300 : struct xfs_buf *bp)
301 : {
302 171908 : struct xfs_mount *mp = bp->b_mount;
303 171908 : struct xfs_buf_log_item *bip = bp->b_log_item;
304 171908 : struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
305 171908 : xfs_failaddr_t fa;
306 :
307 171908 : fa = xfs_da3_node_verify(bp);
308 171908 : if (fa) {
309 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
310 0 : return;
311 : }
312 :
313 171908 : if (!xfs_has_crc(mp))
314 : return;
315 :
316 171908 : if (bip)
317 171908 : hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
318 :
319 171908 : xfs_buf_update_cksum(bp, XFS_DA3_NODE_CRC_OFF);
320 : }
321 :
322 : /*
323 : * leaf/node format detection on trees is sketchy, so a node read can be done on
324 : * leaf level blocks when detection identifies the tree as a node format tree
325 : * incorrectly. In this case, we need to swap the verifier to match the correct
326 : * format of the block being read.
327 : */
328 : static void
329 137081 : xfs_da3_node_read_verify(
330 : struct xfs_buf *bp)
331 : {
332 137081 : struct xfs_da_blkinfo *info = bp->b_addr;
333 137081 : xfs_failaddr_t fa;
334 :
335 137081 : switch (be16_to_cpu(info->magic)) {
336 : case XFS_DA3_NODE_MAGIC:
337 34049 : if (!xfs_buf_verify_cksum(bp, XFS_DA3_NODE_CRC_OFF)) {
338 16 : xfs_verifier_error(bp, -EFSBADCRC,
339 8 : __this_address);
340 8 : break;
341 : }
342 34041 : fallthrough;
343 : case XFS_DA_NODE_MAGIC:
344 34041 : fa = xfs_da3_node_verify(bp);
345 34041 : if (fa)
346 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
347 : return;
348 31285 : case XFS_ATTR_LEAF_MAGIC:
349 : case XFS_ATTR3_LEAF_MAGIC:
350 31285 : bp->b_ops = &xfs_attr3_leaf_buf_ops;
351 31285 : bp->b_ops->verify_read(bp);
352 31285 : return;
353 71745 : case XFS_DIR2_LEAFN_MAGIC:
354 : case XFS_DIR3_LEAFN_MAGIC:
355 71745 : bp->b_ops = &xfs_dir3_leafn_buf_ops;
356 71745 : bp->b_ops->verify_read(bp);
357 71745 : return;
358 : default:
359 2 : xfs_verifier_error(bp, -EFSCORRUPTED, __this_address);
360 2 : break;
361 : }
362 : }
363 :
364 : /* Verify the structure of a da3 block. */
365 : static xfs_failaddr_t
366 53738 : xfs_da3_node_verify_struct(
367 : struct xfs_buf *bp)
368 : {
369 53738 : struct xfs_da_blkinfo *info = bp->b_addr;
370 :
371 53738 : switch (be16_to_cpu(info->magic)) {
372 53738 : case XFS_DA3_NODE_MAGIC:
373 : case XFS_DA_NODE_MAGIC:
374 53738 : return xfs_da3_node_verify(bp);
375 0 : case XFS_ATTR_LEAF_MAGIC:
376 : case XFS_ATTR3_LEAF_MAGIC:
377 0 : bp->b_ops = &xfs_attr3_leaf_buf_ops;
378 0 : return bp->b_ops->verify_struct(bp);
379 0 : case XFS_DIR2_LEAFN_MAGIC:
380 : case XFS_DIR3_LEAFN_MAGIC:
381 0 : bp->b_ops = &xfs_dir3_leafn_buf_ops;
382 0 : return bp->b_ops->verify_struct(bp);
383 : default:
384 0 : return __this_address;
385 : }
386 : }
387 :
388 : const struct xfs_buf_ops xfs_da3_node_buf_ops = {
389 : .name = "xfs_da3_node",
390 : .magic16 = { cpu_to_be16(XFS_DA_NODE_MAGIC),
391 : cpu_to_be16(XFS_DA3_NODE_MAGIC) },
392 : .verify_read = xfs_da3_node_read_verify,
393 : .verify_write = xfs_da3_node_write_verify,
394 : .verify_struct = xfs_da3_node_verify_struct,
395 : };
396 :
397 : static int
398 571687600 : xfs_da3_node_set_type(
399 : struct xfs_trans *tp,
400 : struct xfs_inode *dp,
401 : int whichfork,
402 : struct xfs_buf *bp)
403 : {
404 571687600 : struct xfs_da_blkinfo *info = bp->b_addr;
405 :
406 571687600 : switch (be16_to_cpu(info->magic)) {
407 134457850 : case XFS_DA_NODE_MAGIC:
408 : case XFS_DA3_NODE_MAGIC:
409 134457850 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
410 134457850 : return 0;
411 316610734 : case XFS_ATTR_LEAF_MAGIC:
412 : case XFS_ATTR3_LEAF_MAGIC:
413 316610734 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_ATTR_LEAF_BUF);
414 316610734 : return 0;
415 120619016 : case XFS_DIR2_LEAFN_MAGIC:
416 : case XFS_DIR3_LEAFN_MAGIC:
417 120619016 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
418 120619016 : return 0;
419 0 : default:
420 0 : XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, tp->t_mountp,
421 : info, sizeof(*info));
422 0 : xfs_trans_brelse(tp, bp);
423 0 : xfs_dirattr_mark_sick(dp, whichfork);
424 0 : return -EFSCORRUPTED;
425 : }
426 : }
427 :
428 : int
429 607506804 : xfs_da3_node_read(
430 : struct xfs_trans *tp,
431 : struct xfs_inode *dp,
432 : xfs_dablk_t bno,
433 : struct xfs_buf **bpp,
434 : int whichfork)
435 : {
436 607506804 : int error;
437 :
438 607506804 : error = xfs_da_read_buf(tp, dp, bno, 0, bpp, whichfork,
439 : &xfs_da3_node_buf_ops);
440 607601659 : if (error || !*bpp || !tp)
441 : return error;
442 571645113 : return xfs_da3_node_set_type(tp, dp, whichfork, *bpp);
443 : }
444 :
445 : int
446 48911 : xfs_da3_node_read_mapped(
447 : struct xfs_trans *tp,
448 : struct xfs_inode *dp,
449 : xfs_daddr_t mappedbno,
450 : struct xfs_buf **bpp,
451 : int whichfork)
452 : {
453 48911 : struct xfs_mount *mp = dp->i_mount;
454 48911 : int error;
455 :
456 48911 : error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, mappedbno,
457 48911 : XFS_FSB_TO_BB(mp, xfs_dabuf_nfsb(mp, whichfork)), 0,
458 : bpp, &xfs_da3_node_buf_ops);
459 48911 : if (xfs_metadata_is_sick(error))
460 0 : xfs_dirattr_mark_sick(dp, whichfork);
461 48911 : if (error || !*bpp)
462 : return error;
463 :
464 48911 : if (whichfork == XFS_ATTR_FORK)
465 48911 : xfs_buf_set_ref(*bpp, XFS_ATTR_BTREE_REF);
466 : else
467 0 : xfs_buf_set_ref(*bpp, XFS_DIR_BTREE_REF);
468 :
469 48911 : if (!tp)
470 : return 0;
471 48911 : return xfs_da3_node_set_type(tp, dp, whichfork, *bpp);
472 : }
473 :
474 : /*========================================================================
475 : * Routines used for growing the Btree.
476 : *========================================================================*/
477 :
478 : /*
479 : * Create the initial contents of an intermediate node.
480 : */
481 : int
482 81752 : xfs_da3_node_create(
483 : struct xfs_da_args *args,
484 : xfs_dablk_t blkno,
485 : int level,
486 : struct xfs_buf **bpp,
487 : int whichfork)
488 : {
489 81752 : struct xfs_da_intnode *node;
490 81752 : struct xfs_trans *tp = args->trans;
491 81752 : struct xfs_mount *mp = tp->t_mountp;
492 81752 : struct xfs_da3_icnode_hdr ichdr = {0};
493 81752 : struct xfs_buf *bp;
494 81752 : int error;
495 81752 : struct xfs_inode *dp = args->dp;
496 :
497 81752 : trace_xfs_da_node_create(args);
498 81752 : ASSERT(level <= XFS_DA_NODE_MAXDEPTH);
499 :
500 81752 : error = xfs_da_get_buf(tp, dp, blkno, &bp, whichfork);
501 81752 : if (error)
502 : return error;
503 81752 : bp->b_ops = &xfs_da3_node_buf_ops;
504 81752 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
505 81752 : node = bp->b_addr;
506 :
507 81752 : if (xfs_has_crc(mp)) {
508 81752 : struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
509 :
510 81752 : memset(hdr3, 0, sizeof(struct xfs_da3_node_hdr));
511 81752 : ichdr.magic = XFS_DA3_NODE_MAGIC;
512 81752 : hdr3->info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
513 81752 : hdr3->info.owner = cpu_to_be64(args->owner);
514 81752 : uuid_copy(&hdr3->info.uuid, &mp->m_sb.sb_meta_uuid);
515 : } else {
516 0 : ichdr.magic = XFS_DA_NODE_MAGIC;
517 : }
518 81752 : ichdr.level = level;
519 :
520 81752 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &ichdr);
521 81752 : xfs_trans_log_buf(tp, bp,
522 81752 : XFS_DA_LOGRANGE(node, &node->hdr, args->geo->node_hdr_size));
523 :
524 81752 : *bpp = bp;
525 81752 : return 0;
526 : }
527 :
528 : /*
529 : * Split a leaf node, rebalance, then possibly split
530 : * intermediate nodes, rebalance, etc.
531 : */
532 : int /* error */
533 142100 : xfs_da3_split(
534 : struct xfs_da_state *state)
535 : {
536 142100 : struct xfs_da_state_blk *oldblk;
537 142100 : struct xfs_da_state_blk *newblk;
538 142100 : struct xfs_da_state_blk *addblk;
539 142100 : struct xfs_da_intnode *node;
540 142100 : int max;
541 142100 : int action = 0;
542 142100 : int error;
543 142100 : int i;
544 :
545 142100 : trace_xfs_da_split(state->args);
546 :
547 142100 : if (XFS_TEST_ERROR(false, state->mp, XFS_ERRTAG_DA_LEAF_SPLIT))
548 : return -EIO;
549 :
550 : /*
551 : * Walk back up the tree splitting/inserting/adjusting as necessary.
552 : * If we need to insert and there isn't room, split the node, then
553 : * decide which fragment to insert the new block from below into.
554 : * Note that we may split the root this way, but we need more fixup.
555 : */
556 142098 : max = state->path.active - 1;
557 142098 : ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
558 142098 : ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
559 : state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
560 :
561 142098 : addblk = &state->path.blk[max]; /* initial dummy value */
562 424749 : for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
563 282651 : oldblk = &state->path.blk[i];
564 282651 : newblk = &state->altpath.blk[i];
565 :
566 : /*
567 : * If a leaf node then
568 : * Allocate a new leaf node, then rebalance across them.
569 : * else if an intermediate node then
570 : * We split on the last layer, must we split the node?
571 : */
572 282651 : switch (oldblk->magic) {
573 108622 : case XFS_ATTR_LEAF_MAGIC:
574 108622 : error = xfs_attr3_leaf_split(state, oldblk, newblk);
575 108622 : if ((error != 0) && (error != -ENOSPC)) {
576 0 : return error; /* GROT: attr is inconsistent */
577 : }
578 108622 : if (!error) {
579 : addblk = newblk;
580 : break;
581 : }
582 : /*
583 : * Entry wouldn't fit, split the leaf again. The new
584 : * extrablk will be consumed by xfs_da3_node_split if
585 : * the node is split.
586 : */
587 0 : state->extravalid = 1;
588 0 : if (state->inleaf) {
589 0 : state->extraafter = 0; /* before newblk */
590 0 : trace_xfs_attr_leaf_split_before(state->args);
591 0 : error = xfs_attr3_leaf_split(state, oldblk,
592 0 : &state->extrablk);
593 : } else {
594 0 : state->extraafter = 1; /* after newblk */
595 0 : trace_xfs_attr_leaf_split_after(state->args);
596 0 : error = xfs_attr3_leaf_split(state, newblk,
597 0 : &state->extrablk);
598 : }
599 0 : if (error)
600 0 : return error; /* GROT: attr inconsistent */
601 : addblk = newblk;
602 : break;
603 33476 : case XFS_DIR2_LEAFN_MAGIC:
604 33476 : error = xfs_dir2_leafn_split(state, oldblk, newblk);
605 33476 : if (error)
606 0 : return error;
607 : addblk = newblk;
608 : break;
609 140553 : case XFS_DA_NODE_MAGIC:
610 140553 : error = xfs_da3_node_split(state, oldblk, newblk, addblk,
611 : max - i, &action);
612 140553 : addblk->bp = NULL;
613 140553 : if (error)
614 0 : return error; /* GROT: dir is inconsistent */
615 : /*
616 : * Record the newly split block for the next time thru?
617 : */
618 140553 : if (action)
619 : addblk = newblk;
620 : else
621 140494 : addblk = NULL;
622 : break;
623 : }
624 :
625 : /*
626 : * Update the btree to show the new hashval for this child.
627 : */
628 282651 : xfs_da3_fixhashpath(state, &state->path);
629 : }
630 142098 : if (!addblk)
631 : return 0;
632 :
633 : /*
634 : * xfs_da3_node_split() should have consumed any extra blocks we added
635 : * during a double leaf split in the attr fork. This is guaranteed as
636 : * we can't be here if the attr fork only has a single leaf block.
637 : */
638 1604 : ASSERT(state->extravalid == 0 ||
639 : state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
640 :
641 : /*
642 : * Split the root node.
643 : */
644 1604 : ASSERT(state->path.active == 0);
645 1604 : oldblk = &state->path.blk[0];
646 1604 : error = xfs_da3_root_split(state, oldblk, addblk);
647 1604 : if (error)
648 0 : goto out;
649 :
650 : /*
651 : * Update pointers to the node which used to be block 0 and just got
652 : * bumped because of the addition of a new root node. Note that the
653 : * original block 0 could be at any position in the list of blocks in
654 : * the tree.
655 : *
656 : * Note: the magic numbers and sibling pointers are in the same physical
657 : * place for both v2 and v3 headers (by design). Hence it doesn't matter
658 : * which version of the xfs_da_intnode structure we use here as the
659 : * result will be the same using either structure.
660 : */
661 1604 : node = oldblk->bp->b_addr;
662 1604 : if (node->hdr.info.forw) {
663 3208 : if (be32_to_cpu(node->hdr.info.forw) != addblk->blkno) {
664 0 : xfs_buf_mark_corrupt(oldblk->bp);
665 0 : xfs_da_mark_sick(state->args);
666 0 : error = -EFSCORRUPTED;
667 0 : goto out;
668 : }
669 1604 : node = addblk->bp->b_addr;
670 1604 : node->hdr.info.back = cpu_to_be32(oldblk->blkno);
671 1604 : xfs_trans_log_buf(state->args->trans, addblk->bp,
672 : XFS_DA_LOGRANGE(node, &node->hdr.info,
673 : sizeof(node->hdr.info)));
674 : }
675 1604 : node = oldblk->bp->b_addr;
676 1604 : if (node->hdr.info.back) {
677 0 : if (be32_to_cpu(node->hdr.info.back) != addblk->blkno) {
678 0 : xfs_buf_mark_corrupt(oldblk->bp);
679 0 : xfs_da_mark_sick(state->args);
680 0 : error = -EFSCORRUPTED;
681 0 : goto out;
682 : }
683 0 : node = addblk->bp->b_addr;
684 0 : node->hdr.info.forw = cpu_to_be32(oldblk->blkno);
685 0 : xfs_trans_log_buf(state->args->trans, addblk->bp,
686 : XFS_DA_LOGRANGE(node, &node->hdr.info,
687 : sizeof(node->hdr.info)));
688 : }
689 1604 : out:
690 1604 : addblk->bp = NULL;
691 1604 : return error;
692 : }
693 :
694 : /*
695 : * Split the root. We have to create a new root and point to the two
696 : * parts (the split old root) that we just created. Copy block zero to
697 : * the EOF, extending the inode in process.
698 : */
699 : STATIC int /* error */
700 1604 : xfs_da3_root_split(
701 : struct xfs_da_state *state,
702 : struct xfs_da_state_blk *blk1,
703 : struct xfs_da_state_blk *blk2)
704 : {
705 1604 : struct xfs_da_intnode *node;
706 1604 : struct xfs_da_intnode *oldroot;
707 1604 : struct xfs_da_node_entry *btree;
708 1604 : struct xfs_da3_icnode_hdr nodehdr;
709 1604 : struct xfs_da_args *args;
710 1604 : struct xfs_buf *bp;
711 1604 : struct xfs_inode *dp;
712 1604 : struct xfs_trans *tp;
713 1604 : struct xfs_dir2_leaf *leaf;
714 1604 : xfs_dablk_t blkno;
715 1604 : int level;
716 1604 : int error;
717 1604 : int size;
718 :
719 1604 : trace_xfs_da_root_split(state->args);
720 :
721 : /*
722 : * Copy the existing (incorrect) block from the root node position
723 : * to a free space somewhere.
724 : */
725 1604 : args = state->args;
726 1604 : error = xfs_da_grow_inode(args, &blkno);
727 1604 : if (error)
728 : return error;
729 :
730 1604 : dp = args->dp;
731 1604 : tp = args->trans;
732 1604 : error = xfs_da_get_buf(tp, dp, blkno, &bp, args->whichfork);
733 1604 : if (error)
734 : return error;
735 1604 : node = bp->b_addr;
736 1604 : oldroot = blk1->bp->b_addr;
737 1604 : if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
738 : oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC)) {
739 6 : struct xfs_da3_icnode_hdr icnodehdr;
740 :
741 6 : xfs_da3_node_hdr_from_disk(dp->i_mount, &icnodehdr, oldroot);
742 6 : btree = icnodehdr.btree;
743 6 : size = (int)((char *)&btree[icnodehdr.count] - (char *)oldroot);
744 6 : level = icnodehdr.level;
745 :
746 : /*
747 : * we are about to copy oldroot to bp, so set up the type
748 : * of bp while we know exactly what it will be.
749 : */
750 6 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
751 : } else {
752 1598 : struct xfs_dir3_icleaf_hdr leafhdr;
753 :
754 1598 : leaf = (xfs_dir2_leaf_t *)oldroot;
755 1598 : xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
756 :
757 1598 : ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
758 : leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
759 1598 : size = (int)((char *)&leafhdr.ents[leafhdr.count] -
760 : (char *)leaf);
761 1598 : level = 0;
762 :
763 : /*
764 : * we are about to copy oldroot to bp, so set up the type
765 : * of bp while we know exactly what it will be.
766 : */
767 1598 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
768 : }
769 :
770 : /*
771 : * we can copy most of the information in the node from one block to
772 : * another, but for CRC enabled headers we have to make sure that the
773 : * block specific identifiers are kept intact. We update the buffer
774 : * directly for this.
775 : */
776 3208 : memcpy(node, oldroot, size);
777 1604 : if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
778 : oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
779 1604 : struct xfs_da3_intnode *node3 = (struct xfs_da3_intnode *)node;
780 :
781 1604 : node3->hdr.info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
782 : }
783 1604 : xfs_trans_log_buf(tp, bp, 0, size - 1);
784 :
785 1604 : bp->b_ops = blk1->bp->b_ops;
786 1604 : xfs_trans_buf_copy_type(bp, blk1->bp);
787 1604 : blk1->bp = bp;
788 1604 : blk1->blkno = blkno;
789 :
790 : /*
791 : * Set up the new root node.
792 : */
793 1604 : error = xfs_da3_node_create(args,
794 1604 : (args->whichfork == XFS_DATA_FORK) ? args->geo->leafblk : 0,
795 : level + 1, &bp, args->whichfork);
796 1604 : if (error)
797 : return error;
798 :
799 1604 : node = bp->b_addr;
800 1604 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
801 1604 : btree = nodehdr.btree;
802 1604 : btree[0].hashval = cpu_to_be32(blk1->hashval);
803 1604 : btree[0].before = cpu_to_be32(blk1->blkno);
804 1604 : btree[1].hashval = cpu_to_be32(blk2->hashval);
805 1604 : btree[1].before = cpu_to_be32(blk2->blkno);
806 1604 : nodehdr.count = 2;
807 1604 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
808 :
809 : #ifdef DEBUG
810 1604 : if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
811 : oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
812 0 : ASSERT(blk1->blkno >= args->geo->leafblk &&
813 : blk1->blkno < args->geo->freeblk);
814 0 : ASSERT(blk2->blkno >= args->geo->leafblk &&
815 : blk2->blkno < args->geo->freeblk);
816 : }
817 : #endif
818 :
819 : /* Header is already logged by xfs_da_node_create */
820 1604 : xfs_trans_log_buf(tp, bp,
821 1604 : XFS_DA_LOGRANGE(node, btree, sizeof(xfs_da_node_entry_t) * 2));
822 :
823 1604 : return 0;
824 : }
825 :
826 : /*
827 : * Split the node, rebalance, then add the new entry.
828 : */
829 : STATIC int /* error */
830 140553 : xfs_da3_node_split(
831 : struct xfs_da_state *state,
832 : struct xfs_da_state_blk *oldblk,
833 : struct xfs_da_state_blk *newblk,
834 : struct xfs_da_state_blk *addblk,
835 : int treelevel,
836 : int *result)
837 : {
838 140553 : struct xfs_da_intnode *node;
839 140553 : struct xfs_da3_icnode_hdr nodehdr;
840 140553 : xfs_dablk_t blkno;
841 140553 : int newcount;
842 140553 : int error;
843 140553 : int useextra;
844 140553 : struct xfs_inode *dp = state->args->dp;
845 :
846 140553 : trace_xfs_da_node_split(state->args);
847 :
848 140553 : node = oldblk->bp->b_addr;
849 140553 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
850 :
851 : /*
852 : * With V2 dirs the extra block is data or freespace.
853 : */
854 140553 : useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
855 140553 : newcount = 1 + useextra;
856 : /*
857 : * Do we have to split the node?
858 : */
859 140553 : if (nodehdr.count + newcount > state->args->geo->node_ents) {
860 : /*
861 : * Allocate a new node, add to the doubly linked chain of
862 : * nodes, then move some of our excess entries into it.
863 : */
864 59 : error = xfs_da_grow_inode(state->args, &blkno);
865 59 : if (error)
866 : return error; /* GROT: dir is inconsistent */
867 :
868 59 : error = xfs_da3_node_create(state->args, blkno, treelevel,
869 : &newblk->bp, state->args->whichfork);
870 59 : if (error)
871 : return error; /* GROT: dir is inconsistent */
872 59 : newblk->blkno = blkno;
873 59 : newblk->magic = XFS_DA_NODE_MAGIC;
874 59 : xfs_da3_node_rebalance(state, oldblk, newblk);
875 59 : error = xfs_da3_blk_link(state, oldblk, newblk);
876 59 : if (error)
877 : return error;
878 59 : *result = 1;
879 : } else {
880 140494 : *result = 0;
881 : }
882 :
883 : /*
884 : * Insert the new entry(s) into the correct block
885 : * (updating last hashval in the process).
886 : *
887 : * xfs_da3_node_add() inserts BEFORE the given index,
888 : * and as a result of using node_lookup_int() we always
889 : * point to a valid entry (not after one), but a split
890 : * operation always results in a new block whose hashvals
891 : * FOLLOW the current block.
892 : *
893 : * If we had double-split op below us, then add the extra block too.
894 : */
895 140553 : node = oldblk->bp->b_addr;
896 140553 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
897 140553 : if (oldblk->index <= nodehdr.count) {
898 140515 : oldblk->index++;
899 140515 : xfs_da3_node_add(state, oldblk, addblk);
900 140515 : if (useextra) {
901 0 : if (state->extraafter)
902 0 : oldblk->index++;
903 0 : xfs_da3_node_add(state, oldblk, &state->extrablk);
904 0 : state->extravalid = 0;
905 : }
906 : } else {
907 38 : newblk->index++;
908 38 : xfs_da3_node_add(state, newblk, addblk);
909 38 : if (useextra) {
910 0 : if (state->extraafter)
911 0 : newblk->index++;
912 0 : xfs_da3_node_add(state, newblk, &state->extrablk);
913 0 : state->extravalid = 0;
914 : }
915 : }
916 :
917 : return 0;
918 : }
919 :
920 : /*
921 : * Balance the btree elements between two intermediate nodes,
922 : * usually one full and one empty.
923 : *
924 : * NOTE: if blk2 is empty, then it will get the upper half of blk1.
925 : */
926 : STATIC void
927 59 : xfs_da3_node_rebalance(
928 : struct xfs_da_state *state,
929 : struct xfs_da_state_blk *blk1,
930 : struct xfs_da_state_blk *blk2)
931 : {
932 59 : struct xfs_da_intnode *node1;
933 59 : struct xfs_da_intnode *node2;
934 59 : struct xfs_da_node_entry *btree1;
935 59 : struct xfs_da_node_entry *btree2;
936 59 : struct xfs_da_node_entry *btree_s;
937 59 : struct xfs_da_node_entry *btree_d;
938 59 : struct xfs_da3_icnode_hdr nodehdr1;
939 59 : struct xfs_da3_icnode_hdr nodehdr2;
940 59 : struct xfs_trans *tp;
941 59 : int count;
942 59 : int tmp;
943 59 : int swap = 0;
944 59 : struct xfs_inode *dp = state->args->dp;
945 :
946 59 : trace_xfs_da_node_rebalance(state->args);
947 :
948 59 : node1 = blk1->bp->b_addr;
949 59 : node2 = blk2->bp->b_addr;
950 59 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
951 59 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
952 59 : btree1 = nodehdr1.btree;
953 59 : btree2 = nodehdr2.btree;
954 :
955 : /*
956 : * Figure out how many entries need to move, and in which direction.
957 : * Swap the nodes around if that makes it simpler.
958 : */
959 59 : if (nodehdr1.count > 0 && nodehdr2.count > 0 &&
960 0 : ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
961 0 : (be32_to_cpu(btree2[nodehdr2.count - 1].hashval) <
962 0 : be32_to_cpu(btree1[nodehdr1.count - 1].hashval)))) {
963 0 : swap(node1, node2);
964 0 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
965 0 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
966 0 : btree1 = nodehdr1.btree;
967 0 : btree2 = nodehdr2.btree;
968 0 : swap = 1;
969 : }
970 :
971 59 : count = (nodehdr1.count - nodehdr2.count) / 2;
972 59 : if (count == 0)
973 0 : return;
974 59 : tp = state->args->trans;
975 : /*
976 : * Two cases: high-to-low and low-to-high.
977 : */
978 59 : if (count > 0) {
979 : /*
980 : * Move elements in node2 up to make a hole.
981 : */
982 59 : tmp = nodehdr2.count;
983 59 : if (tmp > 0) {
984 0 : tmp *= (uint)sizeof(xfs_da_node_entry_t);
985 0 : btree_s = &btree2[0];
986 0 : btree_d = &btree2[count];
987 0 : memmove(btree_d, btree_s, tmp);
988 : }
989 :
990 : /*
991 : * Move the req'd B-tree elements from high in node1 to
992 : * low in node2.
993 : */
994 59 : nodehdr2.count += count;
995 59 : tmp = count * (uint)sizeof(xfs_da_node_entry_t);
996 59 : btree_s = &btree1[nodehdr1.count - count];
997 59 : btree_d = &btree2[0];
998 118 : memcpy(btree_d, btree_s, tmp);
999 59 : nodehdr1.count -= count;
1000 : } else {
1001 : /*
1002 : * Move the req'd B-tree elements from low in node2 to
1003 : * high in node1.
1004 : */
1005 0 : count = -count;
1006 0 : tmp = count * (uint)sizeof(xfs_da_node_entry_t);
1007 0 : btree_s = &btree2[0];
1008 0 : btree_d = &btree1[nodehdr1.count];
1009 0 : memcpy(btree_d, btree_s, tmp);
1010 0 : nodehdr1.count += count;
1011 :
1012 0 : xfs_trans_log_buf(tp, blk1->bp,
1013 0 : XFS_DA_LOGRANGE(node1, btree_d, tmp));
1014 :
1015 : /*
1016 : * Move elements in node2 down to fill the hole.
1017 : */
1018 0 : tmp = nodehdr2.count - count;
1019 0 : tmp *= (uint)sizeof(xfs_da_node_entry_t);
1020 0 : btree_s = &btree2[count];
1021 0 : btree_d = &btree2[0];
1022 0 : memmove(btree_d, btree_s, tmp);
1023 0 : nodehdr2.count -= count;
1024 : }
1025 :
1026 : /*
1027 : * Log header of node 1 and all current bits of node 2.
1028 : */
1029 59 : xfs_da3_node_hdr_to_disk(dp->i_mount, node1, &nodehdr1);
1030 59 : xfs_trans_log_buf(tp, blk1->bp,
1031 59 : XFS_DA_LOGRANGE(node1, &node1->hdr,
1032 : state->args->geo->node_hdr_size));
1033 :
1034 59 : xfs_da3_node_hdr_to_disk(dp->i_mount, node2, &nodehdr2);
1035 59 : xfs_trans_log_buf(tp, blk2->bp,
1036 59 : XFS_DA_LOGRANGE(node2, &node2->hdr,
1037 : state->args->geo->node_hdr_size +
1038 : (sizeof(btree2[0]) * nodehdr2.count)));
1039 :
1040 : /*
1041 : * Record the last hashval from each block for upward propagation.
1042 : * (note: don't use the swapped node pointers)
1043 : */
1044 59 : if (swap) {
1045 0 : node1 = blk1->bp->b_addr;
1046 0 : node2 = blk2->bp->b_addr;
1047 0 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
1048 0 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
1049 0 : btree1 = nodehdr1.btree;
1050 0 : btree2 = nodehdr2.btree;
1051 : }
1052 59 : blk1->hashval = be32_to_cpu(btree1[nodehdr1.count - 1].hashval);
1053 59 : blk2->hashval = be32_to_cpu(btree2[nodehdr2.count - 1].hashval);
1054 :
1055 : /*
1056 : * Adjust the expected index for insertion.
1057 : */
1058 59 : if (blk1->index >= nodehdr1.count) {
1059 38 : blk2->index = blk1->index - nodehdr1.count;
1060 38 : blk1->index = nodehdr1.count + 1; /* make it invalid */
1061 : }
1062 : }
1063 :
1064 : /*
1065 : * Add a new entry to an intermediate node.
1066 : */
1067 : STATIC void
1068 140553 : xfs_da3_node_add(
1069 : struct xfs_da_state *state,
1070 : struct xfs_da_state_blk *oldblk,
1071 : struct xfs_da_state_blk *newblk)
1072 : {
1073 140553 : struct xfs_da_intnode *node;
1074 140553 : struct xfs_da3_icnode_hdr nodehdr;
1075 140553 : struct xfs_da_node_entry *btree;
1076 140553 : int tmp;
1077 140553 : struct xfs_inode *dp = state->args->dp;
1078 :
1079 140553 : trace_xfs_da_node_add(state->args);
1080 :
1081 140553 : node = oldblk->bp->b_addr;
1082 140553 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1083 140552 : btree = nodehdr.btree;
1084 :
1085 140552 : ASSERT(oldblk->index >= 0 && oldblk->index <= nodehdr.count);
1086 140552 : ASSERT(newblk->blkno != 0);
1087 140552 : if (state->args->whichfork == XFS_DATA_FORK)
1088 31881 : ASSERT(newblk->blkno >= state->args->geo->leafblk &&
1089 : newblk->blkno < state->args->geo->freeblk);
1090 :
1091 : /*
1092 : * We may need to make some room before we insert the new node.
1093 : */
1094 140552 : tmp = 0;
1095 140552 : if (oldblk->index < nodehdr.count) {
1096 29245 : tmp = (nodehdr.count - oldblk->index) * (uint)sizeof(*btree);
1097 58490 : memmove(&btree[oldblk->index + 1], &btree[oldblk->index], tmp);
1098 : }
1099 140552 : btree[oldblk->index].hashval = cpu_to_be32(newblk->hashval);
1100 140552 : btree[oldblk->index].before = cpu_to_be32(newblk->blkno);
1101 140552 : xfs_trans_log_buf(state->args->trans, oldblk->bp,
1102 140552 : XFS_DA_LOGRANGE(node, &btree[oldblk->index],
1103 : tmp + sizeof(*btree)));
1104 :
1105 140553 : nodehdr.count += 1;
1106 140553 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
1107 140553 : xfs_trans_log_buf(state->args->trans, oldblk->bp,
1108 140553 : XFS_DA_LOGRANGE(node, &node->hdr,
1109 : state->args->geo->node_hdr_size));
1110 :
1111 : /*
1112 : * Copy the last hash value from the oldblk to propagate upwards.
1113 : */
1114 140553 : oldblk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
1115 140553 : }
1116 :
1117 : /*========================================================================
1118 : * Routines used for shrinking the Btree.
1119 : *========================================================================*/
1120 :
1121 : /*
1122 : * Deallocate an empty leaf node, remove it from its parent,
1123 : * possibly deallocating that block, etc...
1124 : */
1125 : int
1126 3624534 : xfs_da3_join(
1127 : struct xfs_da_state *state)
1128 : {
1129 3624534 : struct xfs_da_state_blk *drop_blk;
1130 3624534 : struct xfs_da_state_blk *save_blk;
1131 3624534 : int action = 0;
1132 3624534 : int error;
1133 :
1134 3624534 : trace_xfs_da_join(state->args);
1135 :
1136 3624579 : drop_blk = &state->path.blk[ state->path.active-1 ];
1137 3624579 : save_blk = &state->altpath.blk[ state->path.active-1 ];
1138 3624579 : ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
1139 3624579 : ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC ||
1140 : drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1141 :
1142 : /*
1143 : * Walk back up the tree joining/deallocating as necessary.
1144 : * When we stop dropping blocks, break out.
1145 : */
1146 3648260 : for ( ; state->path.active >= 2; drop_blk--, save_blk--,
1147 23681 : state->path.active--) {
1148 : /*
1149 : * See if we can combine the block with a neighbor.
1150 : * (action == 0) => no options, just leave
1151 : * (action == 1) => coalesce, then unlink
1152 : * (action == 2) => block empty, unlink it
1153 : */
1154 3625644 : switch (drop_blk->magic) {
1155 2065382 : case XFS_ATTR_LEAF_MAGIC:
1156 2065382 : error = xfs_attr3_leaf_toosmall(state, &action);
1157 2065398 : if (error)
1158 2 : return error;
1159 2065396 : if (action == 0)
1160 : return 0;
1161 1473 : xfs_attr3_leaf_unbalance(state, drop_blk, save_blk);
1162 1473 : break;
1163 1559177 : case XFS_DIR2_LEAFN_MAGIC:
1164 1559177 : error = xfs_dir2_leafn_toosmall(state, &action);
1165 1559179 : if (error)
1166 0 : return error;
1167 1559179 : if (action == 0)
1168 : return 0;
1169 22224 : xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
1170 22224 : break;
1171 1085 : case XFS_DA_NODE_MAGIC:
1172 : /*
1173 : * Remove the offending node, fixup hashvals,
1174 : * check for a toosmall neighbor.
1175 : */
1176 1085 : xfs_da3_node_remove(state, drop_blk);
1177 1085 : xfs_da3_fixhashpath(state, &state->path);
1178 1085 : error = xfs_da3_node_toosmall(state, &action);
1179 1085 : if (error)
1180 0 : return error;
1181 1085 : if (action == 0)
1182 : return 0;
1183 4 : xfs_da3_node_unbalance(state, drop_blk, save_blk);
1184 4 : break;
1185 : }
1186 23701 : xfs_da3_fixhashpath(state, &state->altpath);
1187 23701 : error = xfs_da3_blk_unlink(state, drop_blk, save_blk);
1188 23701 : xfs_da_state_kill_altpath(state);
1189 23701 : if (error)
1190 0 : return error;
1191 23701 : error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
1192 : drop_blk->bp);
1193 23681 : drop_blk->bp = NULL;
1194 23681 : if (error)
1195 0 : return error;
1196 : }
1197 : /*
1198 : * We joined all the way to the top. If it turns out that
1199 : * we only have one entry in the root, make the child block
1200 : * the new root.
1201 : */
1202 22616 : xfs_da3_node_remove(state, drop_blk);
1203 22616 : xfs_da3_fixhashpath(state, &state->path);
1204 22616 : error = xfs_da3_root_join(state, &state->path.blk[0]);
1205 22616 : return error;
1206 : }
1207 :
1208 : #ifdef DEBUG
1209 : static void
1210 1167 : xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
1211 : {
1212 1167 : __be16 magic = blkinfo->magic;
1213 :
1214 1167 : if (level == 1) {
1215 1166 : ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1216 : magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
1217 : magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
1218 : magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
1219 : } else {
1220 1 : ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
1221 : magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
1222 : }
1223 1167 : ASSERT(!blkinfo->forw);
1224 1167 : ASSERT(!blkinfo->back);
1225 1167 : }
1226 : #else /* !DEBUG */
1227 : #define xfs_da_blkinfo_onlychild_validate(blkinfo, level)
1228 : #endif /* !DEBUG */
1229 :
1230 : /*
1231 : * We have only one entry in the root. Copy the only remaining child of
1232 : * the old root to block 0 as the new root node.
1233 : */
1234 : STATIC int
1235 22616 : xfs_da3_root_join(
1236 : struct xfs_da_state *state,
1237 : struct xfs_da_state_blk *root_blk)
1238 : {
1239 22616 : struct xfs_da_intnode *oldroot;
1240 22616 : struct xfs_da_args *args;
1241 22616 : xfs_dablk_t child;
1242 22616 : struct xfs_buf *bp;
1243 22616 : struct xfs_da3_icnode_hdr oldroothdr;
1244 22616 : int error;
1245 22616 : struct xfs_inode *dp = state->args->dp;
1246 22616 : xfs_failaddr_t fa;
1247 :
1248 22616 : trace_xfs_da_root_join(state->args);
1249 :
1250 22616 : ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
1251 :
1252 22616 : args = state->args;
1253 22616 : oldroot = root_blk->bp->b_addr;
1254 22616 : xfs_da3_node_hdr_from_disk(dp->i_mount, &oldroothdr, oldroot);
1255 22616 : ASSERT(oldroothdr.forw == 0);
1256 22616 : ASSERT(oldroothdr.back == 0);
1257 :
1258 : /*
1259 : * If the root has more than one child, then don't do anything.
1260 : */
1261 22616 : if (oldroothdr.count > 1)
1262 : return 0;
1263 :
1264 : /*
1265 : * Read in the (only) child block, then copy those bytes into
1266 : * the root block's buffer and free the original child block.
1267 : */
1268 1167 : child = be32_to_cpu(oldroothdr.btree[0].before);
1269 1167 : ASSERT(child != 0);
1270 1167 : error = xfs_da3_node_read(args->trans, dp, child, &bp, args->whichfork);
1271 1167 : if (error)
1272 : return error;
1273 1167 : fa = xfs_da3_header_check(bp, args->owner);
1274 1167 : if (fa) {
1275 0 : __xfs_buf_mark_corrupt(bp, fa);
1276 0 : xfs_trans_brelse(args->trans, bp);
1277 0 : xfs_da_mark_sick(args);
1278 0 : return -EFSCORRUPTED;
1279 : }
1280 1167 : xfs_da_blkinfo_onlychild_validate(bp->b_addr, oldroothdr.level);
1281 :
1282 : /*
1283 : * This could be copying a leaf back into the root block in the case of
1284 : * there only being a single leaf block left in the tree. Hence we have
1285 : * to update the b_ops pointer as well to match the buffer type change
1286 : * that could occur. For dir3 blocks we also need to update the block
1287 : * number in the buffer header.
1288 : */
1289 2334 : memcpy(root_blk->bp->b_addr, bp->b_addr, args->geo->blksize);
1290 1167 : root_blk->bp->b_ops = bp->b_ops;
1291 1167 : xfs_trans_buf_copy_type(root_blk->bp, bp);
1292 1167 : if (oldroothdr.magic == XFS_DA3_NODE_MAGIC) {
1293 1167 : struct xfs_da3_blkinfo *da3 = root_blk->bp->b_addr;
1294 1167 : da3->blkno = cpu_to_be64(xfs_buf_daddr(root_blk->bp));
1295 : }
1296 1167 : xfs_trans_log_buf(args->trans, root_blk->bp, 0,
1297 1167 : args->geo->blksize - 1);
1298 1167 : error = xfs_da_shrink_inode(args, child, bp);
1299 1167 : return error;
1300 : }
1301 :
1302 : /*
1303 : * Check a node block and its neighbors to see if the block should be
1304 : * collapsed into one or the other neighbor. Always keep the block
1305 : * with the smaller block number.
1306 : * If the current block is over 50% full, don't try to join it, return 0.
1307 : * If the block is empty, fill in the state structure and return 2.
1308 : * If it can be collapsed, fill in the state structure and return 1.
1309 : * If nothing can be done, return 0.
1310 : */
1311 : STATIC int
1312 1085 : xfs_da3_node_toosmall(
1313 : struct xfs_da_state *state,
1314 : int *action)
1315 : {
1316 1085 : struct xfs_da_intnode *node;
1317 1085 : struct xfs_da_state_blk *blk;
1318 1085 : struct xfs_da_blkinfo *info;
1319 1085 : xfs_dablk_t blkno;
1320 1085 : struct xfs_buf *bp;
1321 1085 : xfs_failaddr_t fa;
1322 1085 : struct xfs_da3_icnode_hdr nodehdr;
1323 1085 : int count;
1324 1085 : int forward;
1325 1085 : int error;
1326 1085 : int retval;
1327 1085 : int i;
1328 1085 : struct xfs_inode *dp = state->args->dp;
1329 :
1330 1085 : trace_xfs_da_node_toosmall(state->args);
1331 :
1332 : /*
1333 : * Check for the degenerate case of the block being over 50% full.
1334 : * If so, it's not worth even looking to see if we might be able
1335 : * to coalesce with a sibling.
1336 : */
1337 1085 : blk = &state->path.blk[ state->path.active-1 ];
1338 1085 : info = blk->bp->b_addr;
1339 1085 : node = (xfs_da_intnode_t *)info;
1340 1085 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1341 1085 : if (nodehdr.count > (state->args->geo->node_ents >> 1)) {
1342 462 : *action = 0; /* blk over 50%, don't try to join */
1343 462 : return 0; /* blk over 50%, don't try to join */
1344 : }
1345 :
1346 : /*
1347 : * Check for the degenerate case of the block being empty.
1348 : * If the block is empty, we'll simply delete it, no need to
1349 : * coalesce it with a sibling block. We choose (arbitrarily)
1350 : * to merge with the forward block unless it is NULL.
1351 : */
1352 623 : if (nodehdr.count == 0) {
1353 : /*
1354 : * Make altpath point to the block we want to keep and
1355 : * path point to the block we want to drop (this one).
1356 : */
1357 0 : forward = (info->forw != 0);
1358 0 : memcpy(&state->altpath, &state->path, sizeof(state->path));
1359 0 : error = xfs_da3_path_shift(state, &state->altpath, forward,
1360 : 0, &retval);
1361 0 : if (error)
1362 : return error;
1363 0 : if (retval) {
1364 0 : *action = 0;
1365 : } else {
1366 0 : *action = 2;
1367 : }
1368 0 : return 0;
1369 : }
1370 :
1371 : /*
1372 : * Examine each sibling block to see if we can coalesce with
1373 : * at least 25% free space to spare. We need to figure out
1374 : * whether to merge with the forward or the backward block.
1375 : * We prefer coalescing with the lower numbered sibling so as
1376 : * to shrink a directory over time.
1377 : */
1378 623 : count = state->args->geo->node_ents;
1379 623 : count -= state->args->geo->node_ents >> 2;
1380 623 : count -= nodehdr.count;
1381 :
1382 : /* start with smaller blk num */
1383 623 : forward = nodehdr.forw < nodehdr.back;
1384 1865 : for (i = 0; i < 2; forward = !forward, i++) {
1385 1246 : struct xfs_da3_icnode_hdr thdr;
1386 1246 : if (forward)
1387 : blkno = nodehdr.forw;
1388 : else
1389 623 : blkno = nodehdr.back;
1390 1246 : if (blkno == 0)
1391 468 : continue;
1392 778 : error = xfs_da3_node_read(state->args->trans, dp, blkno, &bp,
1393 : state->args->whichfork);
1394 778 : if (error)
1395 0 : return error;
1396 778 : fa = xfs_da3_node_header_check(bp, state->args->owner);
1397 778 : if (fa) {
1398 0 : __xfs_buf_mark_corrupt(bp, fa);
1399 0 : xfs_trans_brelse(state->args->trans, bp);
1400 0 : xfs_da_mark_sick(state->args);
1401 0 : return -EFSCORRUPTED;
1402 : }
1403 :
1404 778 : node = bp->b_addr;
1405 778 : xfs_da3_node_hdr_from_disk(dp->i_mount, &thdr, node);
1406 778 : xfs_trans_brelse(state->args->trans, bp);
1407 :
1408 778 : if (count - thdr.count >= 0)
1409 : break; /* fits with at least 25% to spare */
1410 : }
1411 623 : if (i >= 2) {
1412 619 : *action = 0;
1413 619 : return 0;
1414 : }
1415 :
1416 : /*
1417 : * Make altpath point to the block we want to keep (the lower
1418 : * numbered block) and path point to the block we want to drop.
1419 : */
1420 8 : memcpy(&state->altpath, &state->path, sizeof(state->path));
1421 4 : if (blkno < blk->blkno) {
1422 2 : error = xfs_da3_path_shift(state, &state->altpath, forward,
1423 : 0, &retval);
1424 : } else {
1425 2 : error = xfs_da3_path_shift(state, &state->path, forward,
1426 : 0, &retval);
1427 : }
1428 4 : if (error)
1429 : return error;
1430 4 : if (retval) {
1431 0 : *action = 0;
1432 0 : return 0;
1433 : }
1434 4 : *action = 1;
1435 4 : return 0;
1436 : }
1437 :
1438 : /*
1439 : * Pick up the last hashvalue from an intermediate node.
1440 : */
1441 : STATIC uint
1442 164258 : xfs_da3_node_lasthash(
1443 : struct xfs_inode *dp,
1444 : struct xfs_buf *bp,
1445 : int *count)
1446 : {
1447 164258 : struct xfs_da3_icnode_hdr nodehdr;
1448 :
1449 164258 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, bp->b_addr);
1450 164258 : if (count)
1451 164258 : *count = nodehdr.count;
1452 164258 : if (!nodehdr.count)
1453 : return 0;
1454 164258 : return be32_to_cpu(nodehdr.btree[nodehdr.count - 1].hashval);
1455 : }
1456 :
1457 : /*
1458 : * Walk back up the tree adjusting hash values as necessary,
1459 : * when we stop making changes, return.
1460 : */
1461 : void
1462 66243545 : xfs_da3_fixhashpath(
1463 : struct xfs_da_state *state,
1464 : struct xfs_da_state_path *path)
1465 : {
1466 66243545 : struct xfs_da_state_blk *blk;
1467 66243545 : struct xfs_da_intnode *node;
1468 66243545 : struct xfs_da_node_entry *btree;
1469 66243545 : xfs_dahash_t lasthash=0;
1470 66243545 : int level;
1471 66243545 : int count;
1472 66243545 : struct xfs_inode *dp = state->args->dp;
1473 :
1474 66243545 : trace_xfs_da_fixhashpath(state->args);
1475 :
1476 66250155 : level = path->active-1;
1477 66250155 : blk = &path->blk[ level ];
1478 66250155 : switch (blk->magic) {
1479 5287046 : case XFS_ATTR_LEAF_MAGIC:
1480 5287046 : lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
1481 5287129 : if (count == 0)
1482 4 : return;
1483 : break;
1484 60798851 : case XFS_DIR2_LEAFN_MAGIC:
1485 60798851 : lasthash = xfs_dir2_leaf_lasthash(dp, blk->bp, &count);
1486 60800899 : if (count == 0)
1487 : return;
1488 : break;
1489 164258 : case XFS_DA_NODE_MAGIC:
1490 164258 : lasthash = xfs_da3_node_lasthash(dp, blk->bp, &count);
1491 164258 : if (count == 0)
1492 : return;
1493 : break;
1494 : }
1495 68684285 : for (blk--, level--; level >= 0; blk--, level--) {
1496 66101258 : struct xfs_da3_icnode_hdr nodehdr;
1497 :
1498 66101258 : node = blk->bp->b_addr;
1499 66101258 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1500 66102877 : btree = nodehdr.btree;
1501 132205754 : if (be32_to_cpu(btree[blk->index].hashval) == lasthash)
1502 : break;
1503 2432167 : blk->hashval = lasthash;
1504 2432167 : btree[blk->index].hashval = cpu_to_be32(lasthash);
1505 2432167 : xfs_trans_log_buf(state->args->trans, blk->bp,
1506 2432167 : XFS_DA_LOGRANGE(node, &btree[blk->index],
1507 : sizeof(*btree)));
1508 :
1509 2432003 : lasthash = be32_to_cpu(btree[nodehdr.count - 1].hashval);
1510 : }
1511 : }
1512 :
1513 : /*
1514 : * Remove an entry from an intermediate node.
1515 : */
1516 : STATIC void
1517 23701 : xfs_da3_node_remove(
1518 : struct xfs_da_state *state,
1519 : struct xfs_da_state_blk *drop_blk)
1520 : {
1521 23701 : struct xfs_da_intnode *node;
1522 23701 : struct xfs_da3_icnode_hdr nodehdr;
1523 23701 : struct xfs_da_node_entry *btree;
1524 23701 : int index;
1525 23701 : int tmp;
1526 23701 : struct xfs_inode *dp = state->args->dp;
1527 :
1528 23701 : trace_xfs_da_node_remove(state->args);
1529 :
1530 23701 : node = drop_blk->bp->b_addr;
1531 23701 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1532 23701 : ASSERT(drop_blk->index < nodehdr.count);
1533 23701 : ASSERT(drop_blk->index >= 0);
1534 :
1535 : /*
1536 : * Copy over the offending entry, or just zero it out.
1537 : */
1538 23701 : index = drop_blk->index;
1539 23701 : btree = nodehdr.btree;
1540 23701 : if (index < nodehdr.count - 1) {
1541 22905 : tmp = nodehdr.count - index - 1;
1542 22905 : tmp *= (uint)sizeof(xfs_da_node_entry_t);
1543 45810 : memmove(&btree[index], &btree[index + 1], tmp);
1544 22905 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1545 22905 : XFS_DA_LOGRANGE(node, &btree[index], tmp));
1546 22905 : index = nodehdr.count - 1;
1547 : }
1548 23701 : memset(&btree[index], 0, sizeof(xfs_da_node_entry_t));
1549 23701 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1550 23701 : XFS_DA_LOGRANGE(node, &btree[index], sizeof(btree[index])));
1551 23701 : nodehdr.count -= 1;
1552 23701 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
1553 23701 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1554 23701 : XFS_DA_LOGRANGE(node, &node->hdr, state->args->geo->node_hdr_size));
1555 :
1556 : /*
1557 : * Copy the last hash value from the block to propagate upwards.
1558 : */
1559 23701 : drop_blk->hashval = be32_to_cpu(btree[index - 1].hashval);
1560 23701 : }
1561 :
1562 : /*
1563 : * Unbalance the elements between two intermediate nodes,
1564 : * move all Btree elements from one node into another.
1565 : */
1566 : STATIC void
1567 4 : xfs_da3_node_unbalance(
1568 : struct xfs_da_state *state,
1569 : struct xfs_da_state_blk *drop_blk,
1570 : struct xfs_da_state_blk *save_blk)
1571 : {
1572 4 : struct xfs_da_intnode *drop_node;
1573 4 : struct xfs_da_intnode *save_node;
1574 4 : struct xfs_da_node_entry *drop_btree;
1575 4 : struct xfs_da_node_entry *save_btree;
1576 4 : struct xfs_da3_icnode_hdr drop_hdr;
1577 4 : struct xfs_da3_icnode_hdr save_hdr;
1578 4 : struct xfs_trans *tp;
1579 4 : int sindex;
1580 4 : int tmp;
1581 4 : struct xfs_inode *dp = state->args->dp;
1582 :
1583 4 : trace_xfs_da_node_unbalance(state->args);
1584 :
1585 4 : drop_node = drop_blk->bp->b_addr;
1586 4 : save_node = save_blk->bp->b_addr;
1587 4 : xfs_da3_node_hdr_from_disk(dp->i_mount, &drop_hdr, drop_node);
1588 4 : xfs_da3_node_hdr_from_disk(dp->i_mount, &save_hdr, save_node);
1589 4 : drop_btree = drop_hdr.btree;
1590 4 : save_btree = save_hdr.btree;
1591 4 : tp = state->args->trans;
1592 :
1593 : /*
1594 : * If the dying block has lower hashvals, then move all the
1595 : * elements in the remaining block up to make a hole.
1596 : */
1597 8 : if ((be32_to_cpu(drop_btree[0].hashval) <
1598 7 : be32_to_cpu(save_btree[0].hashval)) ||
1599 3 : (be32_to_cpu(drop_btree[drop_hdr.count - 1].hashval) <
1600 3 : be32_to_cpu(save_btree[save_hdr.count - 1].hashval))) {
1601 : /* XXX: check this - is memmove dst correct? */
1602 1 : tmp = save_hdr.count * sizeof(xfs_da_node_entry_t);
1603 2 : memmove(&save_btree[drop_hdr.count], &save_btree[0], tmp);
1604 :
1605 1 : sindex = 0;
1606 1 : xfs_trans_log_buf(tp, save_blk->bp,
1607 1 : XFS_DA_LOGRANGE(save_node, &save_btree[0],
1608 : (save_hdr.count + drop_hdr.count) *
1609 : sizeof(xfs_da_node_entry_t)));
1610 : } else {
1611 3 : sindex = save_hdr.count;
1612 3 : xfs_trans_log_buf(tp, save_blk->bp,
1613 3 : XFS_DA_LOGRANGE(save_node, &save_btree[sindex],
1614 : drop_hdr.count * sizeof(xfs_da_node_entry_t)));
1615 : }
1616 :
1617 : /*
1618 : * Move all the B-tree elements from drop_blk to save_blk.
1619 : */
1620 4 : tmp = drop_hdr.count * (uint)sizeof(xfs_da_node_entry_t);
1621 8 : memcpy(&save_btree[sindex], &drop_btree[0], tmp);
1622 4 : save_hdr.count += drop_hdr.count;
1623 :
1624 4 : xfs_da3_node_hdr_to_disk(dp->i_mount, save_node, &save_hdr);
1625 4 : xfs_trans_log_buf(tp, save_blk->bp,
1626 4 : XFS_DA_LOGRANGE(save_node, &save_node->hdr,
1627 : state->args->geo->node_hdr_size));
1628 :
1629 : /*
1630 : * Save the last hashval in the remaining block for upward propagation.
1631 : */
1632 4 : save_blk->hashval = be32_to_cpu(save_btree[save_hdr.count - 1].hashval);
1633 4 : }
1634 :
1635 : /*========================================================================
1636 : * Routines used for finding things in the Btree.
1637 : *========================================================================*/
1638 :
1639 : /*
1640 : * Walk down the Btree looking for a particular filename, filling
1641 : * in the state structure as we go.
1642 : *
1643 : * We will set the state structure to point to each of the elements
1644 : * in each of the nodes where either the hashval is or should be.
1645 : *
1646 : * We support duplicate hashval's so for each entry in the current
1647 : * node that could contain the desired hashval, descend. This is a
1648 : * pruned depth-first tree search.
1649 : */
1650 : int /* error */
1651 147335649 : xfs_da3_node_lookup_int(
1652 : struct xfs_da_state *state,
1653 : int *result)
1654 : {
1655 147335649 : struct xfs_da_state_blk *blk;
1656 147335649 : struct xfs_da_blkinfo *curr;
1657 147335649 : struct xfs_da_intnode *node;
1658 147335649 : struct xfs_da_node_entry *btree;
1659 147335649 : struct xfs_da3_icnode_hdr nodehdr;
1660 147335649 : struct xfs_da_args *args;
1661 147335649 : xfs_failaddr_t fa;
1662 147335649 : xfs_dablk_t blkno;
1663 147335649 : xfs_dahash_t hashval;
1664 147335649 : xfs_dahash_t btreehashval;
1665 147335649 : int probe;
1666 147335649 : int span;
1667 147335649 : int max;
1668 147335649 : int error;
1669 147335649 : int retval;
1670 147335649 : unsigned int expected_level = 0;
1671 147335649 : uint16_t magic;
1672 147335649 : struct xfs_inode *dp = state->args->dp;
1673 :
1674 147335649 : args = state->args;
1675 :
1676 : /*
1677 : * Descend thru the B-tree searching each level for the right
1678 : * node to use, until the right hashval is found.
1679 : */
1680 147335649 : blkno = args->geo->leafblk;
1681 147335649 : for (blk = &state->path.blk[0], state->path.active = 1;
1682 297179438 : state->path.active <= XFS_DA_NODE_MAXDEPTH;
1683 149843789 : blk++, state->path.active++) {
1684 : /*
1685 : * Read the next node down in the tree.
1686 : */
1687 297179438 : blk->blkno = blkno;
1688 297179438 : error = xfs_da3_node_read(args->trans, args->dp, blkno,
1689 : &blk->bp, args->whichfork);
1690 297179011 : if (error) {
1691 5895 : blk->blkno = 0;
1692 5895 : state->path.active--;
1693 5895 : return error;
1694 : }
1695 297173116 : curr = blk->bp->b_addr;
1696 297173116 : magic = be16_to_cpu(curr->magic);
1697 :
1698 297173116 : if (magic == XFS_ATTR_LEAF_MAGIC ||
1699 297173116 : magic == XFS_ATTR3_LEAF_MAGIC) {
1700 12710022 : fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);
1701 12710104 : if (fa) {
1702 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
1703 0 : xfs_da_mark_sick(args);
1704 0 : return -EFSCORRUPTED;
1705 : }
1706 12710104 : blk->magic = XFS_ATTR_LEAF_MAGIC;
1707 12710104 : blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
1708 12709965 : break;
1709 : }
1710 :
1711 284463094 : if (magic == XFS_DIR2_LEAFN_MAGIC ||
1712 284463094 : magic == XFS_DIR3_LEAFN_MAGIC) {
1713 134630179 : fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);
1714 134638161 : if (fa) {
1715 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
1716 0 : xfs_da_mark_sick(args);
1717 0 : return -EFSCORRUPTED;
1718 : }
1719 134638161 : blk->magic = XFS_DIR2_LEAFN_MAGIC;
1720 134638161 : blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
1721 : blk->bp, NULL);
1722 134636898 : break;
1723 : }
1724 :
1725 149832915 : if (magic != XFS_DA_NODE_MAGIC && magic != XFS_DA3_NODE_MAGIC) {
1726 0 : xfs_buf_mark_corrupt(blk->bp);
1727 0 : xfs_da_mark_sick(args);
1728 0 : return -EFSCORRUPTED;
1729 : }
1730 :
1731 149832915 : fa = xfs_da3_node_header_check(blk->bp, args->owner);
1732 149836719 : if (fa) {
1733 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
1734 0 : xfs_da_mark_sick(args);
1735 0 : return -EFSCORRUPTED;
1736 : }
1737 :
1738 149836719 : blk->magic = XFS_DA_NODE_MAGIC;
1739 :
1740 : /*
1741 : * Search an intermediate node for a match.
1742 : */
1743 149836719 : node = blk->bp->b_addr;
1744 149836719 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1745 149843789 : btree = nodehdr.btree;
1746 :
1747 : /* Tree taller than we can handle; bail out! */
1748 149843789 : if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {
1749 0 : xfs_buf_mark_corrupt(blk->bp);
1750 0 : xfs_da_mark_sick(args);
1751 0 : return -EFSCORRUPTED;
1752 : }
1753 :
1754 : /* Check the level from the root. */
1755 149843789 : if (blkno == args->geo->leafblk)
1756 147304751 : expected_level = nodehdr.level - 1;
1757 2539038 : else if (expected_level != nodehdr.level) {
1758 0 : xfs_buf_mark_corrupt(blk->bp);
1759 0 : xfs_da_mark_sick(args);
1760 0 : return -EFSCORRUPTED;
1761 : } else
1762 2539038 : expected_level--;
1763 :
1764 149843789 : max = nodehdr.count;
1765 149843789 : blk->hashval = be32_to_cpu(btree[max - 1].hashval);
1766 :
1767 : /*
1768 : * Binary search. (note: small blocks will skip loop)
1769 : */
1770 149843789 : probe = span = max / 2;
1771 149843789 : hashval = args->hashval;
1772 343685587 : while (span > 4) {
1773 194084672 : span /= 2;
1774 194084672 : btreehashval = be32_to_cpu(btree[probe].hashval);
1775 194084672 : if (btreehashval < hashval)
1776 92474980 : probe += span;
1777 101609692 : else if (btreehashval > hashval)
1778 101366818 : probe -= span;
1779 : else
1780 : break;
1781 : }
1782 149843789 : ASSERT((probe >= 0) && (probe < max));
1783 150021505 : ASSERT((span <= 4) ||
1784 : (be32_to_cpu(btree[probe].hashval) == hashval));
1785 :
1786 : /*
1787 : * Since we may have duplicate hashval's, find the first
1788 : * matching hashval in the node.
1789 : */
1790 744762831 : while (probe > 0 &&
1791 338760764 : be32_to_cpu(btree[probe].hashval) >= hashval) {
1792 256158278 : probe--;
1793 : }
1794 642778573 : while (probe < max &&
1795 319884353 : be32_to_cpu(btree[probe].hashval) < hashval) {
1796 173050431 : probe++;
1797 : }
1798 :
1799 : /*
1800 : * Pick the right block to descend on.
1801 : */
1802 149843789 : if (probe == max) {
1803 3010289 : blk->index = max - 1;
1804 3010289 : blkno = be32_to_cpu(btree[max - 1].before);
1805 : } else {
1806 146833500 : blk->index = probe;
1807 146833500 : blkno = be32_to_cpu(btree[probe].before);
1808 : }
1809 :
1810 : /* We can't point back to the root. */
1811 149843789 : if (XFS_IS_CORRUPT(dp->i_mount, blkno == args->geo->leafblk)) {
1812 0 : xfs_da_mark_sick(args);
1813 0 : return -EFSCORRUPTED;
1814 : }
1815 : }
1816 :
1817 147346863 : if (XFS_IS_CORRUPT(dp->i_mount, expected_level != 0)) {
1818 0 : xfs_da_mark_sick(args);
1819 0 : return -EFSCORRUPTED;
1820 : }
1821 :
1822 : /*
1823 : * A leaf block that ends in the hashval that we are interested in
1824 : * (final hashval == search hashval) means that the next block may
1825 : * contain more entries with the same hashval, shift upward to the
1826 : * next leaf and keep searching.
1827 : */
1828 753691147 : for (;;) {
1829 450519005 : if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
1830 135620987 : retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
1831 : &blk->index, state);
1832 314898025 : } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1833 314898025 : retval = xfs_attr3_leaf_lookup_int(blk->bp, args);
1834 314896707 : blk->index = args->index;
1835 314896707 : args->blkno = blk->blkno;
1836 : } else {
1837 0 : ASSERT(0);
1838 0 : xfs_da_mark_sick(args);
1839 0 : return -EFSCORRUPTED;
1840 : }
1841 450503413 : if (((retval == -ENOENT) || (retval == -ENOATTR)) &&
1842 352663795 : (blk->hashval == args->hashval)) {
1843 303327755 : error = xfs_da3_path_shift(state, &state->path, 1, 1,
1844 : &retval);
1845 303329109 : if (error)
1846 0 : return error;
1847 303329109 : if (retval == 0) {
1848 303172142 : continue;
1849 156967 : } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1850 : /* path_shift() gives ENOENT */
1851 5855 : retval = -ENOATTR;
1852 : }
1853 : }
1854 147343329 : break;
1855 : }
1856 147343329 : *result = retval;
1857 147343329 : return 0;
1858 : }
1859 :
1860 : /*========================================================================
1861 : * Utility routines.
1862 : *========================================================================*/
1863 :
1864 : /*
1865 : * Compare two intermediate nodes for "order".
1866 : */
1867 : STATIC int
1868 59 : xfs_da3_node_order(
1869 : struct xfs_inode *dp,
1870 : struct xfs_buf *node1_bp,
1871 : struct xfs_buf *node2_bp)
1872 : {
1873 59 : struct xfs_da_intnode *node1;
1874 59 : struct xfs_da_intnode *node2;
1875 59 : struct xfs_da_node_entry *btree1;
1876 59 : struct xfs_da_node_entry *btree2;
1877 59 : struct xfs_da3_icnode_hdr node1hdr;
1878 59 : struct xfs_da3_icnode_hdr node2hdr;
1879 :
1880 59 : node1 = node1_bp->b_addr;
1881 59 : node2 = node2_bp->b_addr;
1882 59 : xfs_da3_node_hdr_from_disk(dp->i_mount, &node1hdr, node1);
1883 59 : xfs_da3_node_hdr_from_disk(dp->i_mount, &node2hdr, node2);
1884 59 : btree1 = node1hdr.btree;
1885 59 : btree2 = node2hdr.btree;
1886 :
1887 118 : if (node1hdr.count > 0 && node2hdr.count > 0 &&
1888 177 : ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
1889 59 : (be32_to_cpu(btree2[node2hdr.count - 1].hashval) <
1890 59 : be32_to_cpu(btree1[node1hdr.count - 1].hashval)))) {
1891 0 : return 1;
1892 : }
1893 : return 0;
1894 : }
1895 :
1896 : /*
1897 : * Link a new block into a doubly linked list of blocks (of whatever type).
1898 : */
1899 : int /* error */
1900 142157 : xfs_da3_blk_link(
1901 : struct xfs_da_state *state,
1902 : struct xfs_da_state_blk *old_blk,
1903 : struct xfs_da_state_blk *new_blk)
1904 : {
1905 142157 : struct xfs_da_blkinfo *old_info;
1906 142157 : struct xfs_da_blkinfo *new_info;
1907 142157 : struct xfs_da_blkinfo *tmp_info;
1908 142157 : struct xfs_da_args *args;
1909 142157 : struct xfs_buf *bp;
1910 142157 : xfs_failaddr_t fa;
1911 142157 : int before = 0;
1912 142157 : int error;
1913 142157 : struct xfs_inode *dp = state->args->dp;
1914 :
1915 : /*
1916 : * Set up environment.
1917 : */
1918 142157 : args = state->args;
1919 142157 : ASSERT(args != NULL);
1920 142157 : old_info = old_blk->bp->b_addr;
1921 142157 : new_info = new_blk->bp->b_addr;
1922 142157 : ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||
1923 : old_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
1924 : old_blk->magic == XFS_ATTR_LEAF_MAGIC);
1925 :
1926 142157 : switch (old_blk->magic) {
1927 108622 : case XFS_ATTR_LEAF_MAGIC:
1928 108622 : before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
1929 108622 : break;
1930 33476 : case XFS_DIR2_LEAFN_MAGIC:
1931 33476 : before = xfs_dir2_leafn_order(dp, old_blk->bp, new_blk->bp);
1932 33476 : break;
1933 59 : case XFS_DA_NODE_MAGIC:
1934 59 : before = xfs_da3_node_order(dp, old_blk->bp, new_blk->bp);
1935 59 : break;
1936 : }
1937 :
1938 : /*
1939 : * Link blocks in appropriate order.
1940 : */
1941 142157 : if (before) {
1942 : /*
1943 : * Link new block in before existing block.
1944 : */
1945 0 : trace_xfs_da_link_before(args);
1946 0 : new_info->forw = cpu_to_be32(old_blk->blkno);
1947 0 : new_info->back = old_info->back;
1948 0 : if (old_info->back) {
1949 0 : error = xfs_da3_node_read(args->trans, dp,
1950 0 : be32_to_cpu(old_info->back),
1951 : &bp, args->whichfork);
1952 0 : if (error)
1953 : return error;
1954 0 : fa = xfs_da3_header_check(bp, args->owner);
1955 0 : if (fa) {
1956 0 : __xfs_buf_mark_corrupt(bp, fa);
1957 0 : xfs_trans_brelse(args->trans, bp);
1958 0 : xfs_da_mark_sick(args);
1959 0 : return -EFSCORRUPTED;
1960 : }
1961 0 : ASSERT(bp != NULL);
1962 0 : tmp_info = bp->b_addr;
1963 0 : ASSERT(tmp_info->magic == old_info->magic);
1964 0 : ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);
1965 0 : tmp_info->forw = cpu_to_be32(new_blk->blkno);
1966 0 : xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1967 : }
1968 0 : old_info->back = cpu_to_be32(new_blk->blkno);
1969 : } else {
1970 : /*
1971 : * Link new block in after existing block.
1972 : */
1973 142157 : trace_xfs_da_link_after(args);
1974 142157 : new_info->forw = old_info->forw;
1975 142157 : new_info->back = cpu_to_be32(old_blk->blkno);
1976 142157 : if (old_info->forw) {
1977 29258 : error = xfs_da3_node_read(args->trans, dp,
1978 29258 : be32_to_cpu(old_info->forw),
1979 : &bp, args->whichfork);
1980 29258 : if (error)
1981 : return error;
1982 29258 : fa = xfs_da3_header_check(bp, args->owner);
1983 29258 : if (fa) {
1984 0 : __xfs_buf_mark_corrupt(bp, fa);
1985 0 : xfs_trans_brelse(args->trans, bp);
1986 0 : xfs_da_mark_sick(args);
1987 0 : return -EFSCORRUPTED;
1988 : }
1989 29258 : ASSERT(bp != NULL);
1990 29258 : tmp_info = bp->b_addr;
1991 29258 : ASSERT(tmp_info->magic == old_info->magic);
1992 58516 : ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
1993 29258 : tmp_info->back = cpu_to_be32(new_blk->blkno);
1994 29258 : xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1995 : }
1996 284314 : old_info->forw = cpu_to_be32(new_blk->blkno);
1997 : }
1998 :
1999 142157 : xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
2000 142157 : xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
2001 142157 : return 0;
2002 : }
2003 :
2004 : /*
2005 : * Unlink a block from a doubly linked list of blocks.
2006 : */
2007 : STATIC int /* error */
2008 23701 : xfs_da3_blk_unlink(
2009 : struct xfs_da_state *state,
2010 : struct xfs_da_state_blk *drop_blk,
2011 : struct xfs_da_state_blk *save_blk)
2012 : {
2013 23701 : struct xfs_da_blkinfo *drop_info;
2014 23701 : struct xfs_da_blkinfo *save_info;
2015 23701 : struct xfs_da_blkinfo *tmp_info;
2016 23701 : struct xfs_da_args *args;
2017 23701 : struct xfs_buf *bp;
2018 23701 : xfs_failaddr_t fa;
2019 23701 : int error;
2020 :
2021 : /*
2022 : * Set up environment.
2023 : */
2024 23701 : args = state->args;
2025 23701 : ASSERT(args != NULL);
2026 23701 : save_info = save_blk->bp->b_addr;
2027 23701 : drop_info = drop_blk->bp->b_addr;
2028 23701 : ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||
2029 : save_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
2030 : save_blk->magic == XFS_ATTR_LEAF_MAGIC);
2031 23701 : ASSERT(save_blk->magic == drop_blk->magic);
2032 50951 : ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
2033 : (be32_to_cpu(save_info->back) == drop_blk->blkno));
2034 67554 : ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) ||
2035 : (be32_to_cpu(drop_info->back) == save_blk->blkno));
2036 :
2037 : /*
2038 : * Unlink the leaf block from the doubly linked chain of leaves.
2039 : */
2040 47402 : if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
2041 3549 : trace_xfs_da_unlink_back(args);
2042 3549 : save_info->back = drop_info->back;
2043 3549 : if (drop_info->back) {
2044 2396 : error = xfs_da3_node_read(args->trans, args->dp,
2045 2396 : be32_to_cpu(drop_info->back),
2046 : &bp, args->whichfork);
2047 2396 : if (error)
2048 : return error;
2049 2396 : fa = xfs_da3_header_check(bp, args->owner);
2050 2396 : if (fa) {
2051 0 : __xfs_buf_mark_corrupt(bp, fa);
2052 0 : xfs_trans_brelse(args->trans, bp);
2053 0 : xfs_da_mark_sick(args);
2054 0 : return -EFSCORRUPTED;
2055 : }
2056 2396 : ASSERT(bp != NULL);
2057 2396 : tmp_info = bp->b_addr;
2058 2396 : ASSERT(tmp_info->magic == save_info->magic);
2059 4792 : ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
2060 2396 : tmp_info->forw = cpu_to_be32(save_blk->blkno);
2061 2396 : xfs_trans_log_buf(args->trans, bp, 0,
2062 : sizeof(*tmp_info) - 1);
2063 : }
2064 : } else {
2065 20152 : trace_xfs_da_unlink_forward(args);
2066 20152 : save_info->forw = drop_info->forw;
2067 20152 : if (drop_info->forw) {
2068 19357 : error = xfs_da3_node_read(args->trans, args->dp,
2069 19357 : be32_to_cpu(drop_info->forw),
2070 : &bp, args->whichfork);
2071 19357 : if (error)
2072 : return error;
2073 19357 : fa = xfs_da3_header_check(bp, args->owner);
2074 19357 : if (fa) {
2075 0 : __xfs_buf_mark_corrupt(bp, fa);
2076 0 : xfs_trans_brelse(args->trans, bp);
2077 0 : xfs_da_mark_sick(args);
2078 0 : return -EFSCORRUPTED;
2079 : }
2080 19357 : ASSERT(bp != NULL);
2081 19357 : tmp_info = bp->b_addr;
2082 19357 : ASSERT(tmp_info->magic == save_info->magic);
2083 38714 : ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
2084 19357 : tmp_info->back = cpu_to_be32(save_blk->blkno);
2085 19357 : xfs_trans_log_buf(args->trans, bp, 0,
2086 : sizeof(*tmp_info) - 1);
2087 : }
2088 : }
2089 :
2090 23701 : xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
2091 23701 : return 0;
2092 : }
2093 :
2094 : /*
2095 : * Move a path "forward" or "!forward" one block at the current level.
2096 : *
2097 : * This routine will adjust a "path" to point to the next block
2098 : * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
2099 : * Btree, including updating pointers to the intermediate nodes between
2100 : * the new bottom and the root.
2101 : */
2102 : int /* error */
2103 303874288 : xfs_da3_path_shift(
2104 : struct xfs_da_state *state,
2105 : struct xfs_da_state_path *path,
2106 : int forward,
2107 : int release,
2108 : int *result)
2109 : {
2110 303874288 : struct xfs_da_state_blk *blk;
2111 303874288 : struct xfs_da_blkinfo *info;
2112 303874288 : struct xfs_da_args *args;
2113 303874288 : struct xfs_da_node_entry *btree;
2114 303874288 : struct xfs_da3_icnode_hdr nodehdr;
2115 303874288 : struct xfs_buf *bp;
2116 303874288 : xfs_failaddr_t fa;
2117 303874288 : xfs_dablk_t blkno = 0;
2118 303874288 : int level;
2119 303874288 : int error;
2120 303874288 : struct xfs_inode *dp = state->args->dp;
2121 :
2122 303874288 : trace_xfs_da_path_shift(state->args);
2123 :
2124 : /*
2125 : * Roll up the Btree looking for the first block where our
2126 : * current index is not at the edge of the block. Note that
2127 : * we skip the bottom layer because we want the sibling block.
2128 : */
2129 303874288 : args = state->args;
2130 303874288 : ASSERT(args != NULL);
2131 303874288 : ASSERT(path != NULL);
2132 303874288 : ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
2133 303874288 : level = (path->active-1) - 1; /* skip bottom layer in path */
2134 304575073 : for (; level >= 0; level--) {
2135 304310817 : blk = &path->blk[level];
2136 304310817 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
2137 304310817 : blk->bp->b_addr);
2138 :
2139 304310818 : if (forward && (blk->index < nodehdr.count - 1)) {
2140 303394749 : blk->index++;
2141 303394749 : blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
2142 : break;
2143 916069 : } else if (!forward && (blk->index > 0)) {
2144 215284 : blk->index--;
2145 215284 : blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
2146 : break;
2147 : }
2148 : }
2149 303874289 : if (level < 0) {
2150 264257 : *result = -ENOENT; /* we're out of our tree */
2151 264257 : ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
2152 264257 : return 0;
2153 : }
2154 :
2155 : /*
2156 : * Roll down the edge of the subtree until we reach the
2157 : * same depth we were at originally.
2158 : */
2159 607656658 : for (blk++, level++; level < path->active; blk++, level++) {
2160 : /*
2161 : * Read the next child block into a local buffer.
2162 : */
2163 304046625 : error = xfs_da3_node_read(args->trans, dp, blkno, &bp,
2164 : args->whichfork);
2165 304046626 : if (error)
2166 0 : return error;
2167 :
2168 : /*
2169 : * Release the old block (if it's dirty, the trans doesn't
2170 : * actually let go) and swap the local buffer into the path
2171 : * structure. This ensures failure of the above read doesn't set
2172 : * a NULL buffer in an active slot in the path.
2173 : */
2174 304046626 : if (release)
2175 303608673 : xfs_trans_brelse(args->trans, blk->bp);
2176 304046626 : blk->blkno = blkno;
2177 304046626 : blk->bp = bp;
2178 :
2179 304046626 : info = blk->bp->b_addr;
2180 304046626 : ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
2181 : info->magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
2182 : info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
2183 : info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
2184 : info->magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
2185 : info->magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
2186 :
2187 :
2188 : /*
2189 : * Note: we flatten the magic number to a single type so we
2190 : * don't have to compare against crc/non-crc types elsewhere.
2191 : */
2192 304046626 : switch (be16_to_cpu(info->magic)) {
2193 436659 : case XFS_DA_NODE_MAGIC:
2194 : case XFS_DA3_NODE_MAGIC:
2195 436659 : fa = xfs_da3_node_header_check(blk->bp, args->owner);
2196 436659 : if (fa) {
2197 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2198 0 : xfs_da_mark_sick(args);
2199 0 : return -EFSCORRUPTED;
2200 : }
2201 436659 : blk->magic = XFS_DA_NODE_MAGIC;
2202 436659 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
2203 436659 : bp->b_addr);
2204 436659 : btree = nodehdr.btree;
2205 436659 : blk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
2206 436659 : if (forward)
2207 436596 : blk->index = 0;
2208 : else
2209 63 : blk->index = nodehdr.count - 1;
2210 436659 : blkno = be32_to_cpu(btree[blk->index].before);
2211 : break;
2212 302327618 : case XFS_ATTR_LEAF_MAGIC:
2213 : case XFS_ATTR3_LEAF_MAGIC:
2214 302327618 : fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);
2215 302327619 : if (fa) {
2216 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2217 0 : xfs_da_mark_sick(args);
2218 0 : return -EFSCORRUPTED;
2219 : }
2220 302327619 : blk->magic = XFS_ATTR_LEAF_MAGIC;
2221 302327619 : ASSERT(level == path->active-1);
2222 302327619 : blk->index = 0;
2223 302327619 : blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
2224 302327619 : break;
2225 1282349 : case XFS_DIR2_LEAFN_MAGIC:
2226 : case XFS_DIR3_LEAFN_MAGIC:
2227 1282349 : fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);
2228 1282349 : if (fa) {
2229 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2230 0 : xfs_da_mark_sick(args);
2231 0 : return -EFSCORRUPTED;
2232 : }
2233 1282349 : blk->magic = XFS_DIR2_LEAFN_MAGIC;
2234 1282349 : ASSERT(level == path->active-1);
2235 1282349 : blk->index = 0;
2236 1282349 : blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
2237 : blk->bp, NULL);
2238 1282348 : break;
2239 0 : default:
2240 0 : ASSERT(0);
2241 0 : break;
2242 : }
2243 : }
2244 303610033 : *result = 0;
2245 303610033 : return 0;
2246 : }
2247 :
2248 :
2249 : /*========================================================================
2250 : * Utility routines.
2251 : *========================================================================*/
2252 :
2253 : /*
2254 : * Implement a simple hash on a character string.
2255 : * Rotate the hash value by 7 bits, then XOR each character in.
2256 : * This is implemented with some source-level loop unrolling.
2257 : */
2258 : xfs_dahash_t
2259 3727180594 : xfs_da_hashname(const uint8_t *name, int namelen)
2260 : {
2261 3727180594 : xfs_dahash_t hash;
2262 :
2263 : /*
2264 : * Do four characters at a time as long as we can.
2265 : */
2266 8094314254 : for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
2267 4367133660 : hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
2268 4367133660 : (name[3] << 0) ^ rol32(hash, 7 * 4);
2269 :
2270 : /*
2271 : * Now do the rest of the characters.
2272 : */
2273 3727180594 : switch (namelen) {
2274 550691817 : case 3:
2275 550691817 : return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
2276 : rol32(hash, 7 * 3);
2277 934912485 : case 2:
2278 934912485 : return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
2279 1408313120 : case 1:
2280 1408313120 : return (name[0] << 0) ^ rol32(hash, 7 * 1);
2281 : default: /* case 0: */
2282 : return hash;
2283 : }
2284 : }
2285 :
2286 : enum xfs_dacmp
2287 1504493401 : xfs_da_compname(
2288 : struct xfs_da_args *args,
2289 : const unsigned char *name,
2290 : int len)
2291 : {
2292 1368032739 : return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
2293 2872526140 : XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
2294 : }
2295 :
2296 : int
2297 9264929 : xfs_da_grow_inode_int(
2298 : struct xfs_da_args *args,
2299 : xfs_fileoff_t *bno,
2300 : int count)
2301 : {
2302 9264929 : struct xfs_trans *tp = args->trans;
2303 9264929 : struct xfs_inode *dp = args->dp;
2304 9264929 : int w = args->whichfork;
2305 9264929 : xfs_rfsblock_t nblks = dp->i_nblocks;
2306 9264929 : struct xfs_bmbt_irec map, *mapp;
2307 9264929 : int nmap, error, got, i, mapi;
2308 :
2309 : /*
2310 : * Find a spot in the file space to put the new block.
2311 : */
2312 9264929 : error = xfs_bmap_first_unused(tp, dp, count, bno, w);
2313 9264980 : if (error)
2314 : return error;
2315 :
2316 : /*
2317 : * Try mapping it in one filesystem block.
2318 : */
2319 9264980 : nmap = 1;
2320 9264980 : error = xfs_bmapi_write(tp, dp, *bno, count,
2321 9264980 : xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
2322 : args->total, &map, &nmap);
2323 9264065 : if (error)
2324 : return error;
2325 :
2326 9264064 : ASSERT(nmap <= 1);
2327 9264064 : if (nmap == 1) {
2328 : mapp = ↦
2329 : mapi = 1;
2330 40 : } else if (nmap == 0 && count > 1) {
2331 40 : xfs_fileoff_t b;
2332 40 : int c;
2333 :
2334 : /*
2335 : * If we didn't get it and the block might work if fragmented,
2336 : * try without the CONTIG flag. Loop until we get it all.
2337 : */
2338 40 : mapp = kmem_alloc(sizeof(*mapp) * count, 0);
2339 80 : for (b = *bno, mapi = 0; b < *bno + count; ) {
2340 40 : c = (int)(*bno + count - b);
2341 40 : nmap = min(XFS_BMAP_MAX_NMAP, c);
2342 40 : error = xfs_bmapi_write(tp, dp, b, c,
2343 40 : xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
2344 40 : args->total, &mapp[mapi], &nmap);
2345 40 : if (error)
2346 0 : goto out_free_map;
2347 40 : if (nmap < 1)
2348 : break;
2349 40 : mapi += nmap;
2350 40 : b = mapp[mapi - 1].br_startoff +
2351 40 : mapp[mapi - 1].br_blockcount;
2352 : }
2353 : } else {
2354 : mapi = 0;
2355 : mapp = NULL;
2356 : }
2357 :
2358 : /*
2359 : * Count the blocks we got, make sure it matches the total.
2360 : */
2361 18528607 : for (i = 0, got = 0; i < mapi; i++)
2362 9264543 : got += mapp[i].br_blockcount;
2363 9264064 : if (got != count || mapp[0].br_startoff != *bno ||
2364 9264419 : mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
2365 9264419 : *bno + count) {
2366 0 : error = -ENOSPC;
2367 0 : goto out_free_map;
2368 : }
2369 :
2370 : /* account for newly allocated blocks in reserved blocks total */
2371 9264329 : args->total -= dp->i_nblocks - nblks;
2372 :
2373 9264064 : out_free_map:
2374 9264064 : if (mapp != &map)
2375 40 : kmem_free(mapp);
2376 : return error;
2377 : }
2378 :
2379 : /*
2380 : * Add a block to the btree ahead of the file.
2381 : * Return the new block number to the caller.
2382 : */
2383 : int
2384 8817026 : xfs_da_grow_inode(
2385 : struct xfs_da_args *args,
2386 : xfs_dablk_t *new_blkno)
2387 : {
2388 8817026 : xfs_fileoff_t bno;
2389 8817026 : int error;
2390 :
2391 8817026 : trace_xfs_da_grow_inode(args);
2392 :
2393 8817298 : bno = args->geo->leafblk;
2394 8817298 : error = xfs_da_grow_inode_int(args, &bno, args->geo->fsbcount);
2395 8816743 : if (!error)
2396 8816415 : *new_blkno = (xfs_dablk_t)bno;
2397 8816743 : return error;
2398 : }
2399 :
2400 : /*
2401 : * Ick. We need to always be able to remove a btree block, even
2402 : * if there's no space reservation because the filesystem is full.
2403 : * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
2404 : * It swaps the target block with the last block in the file. The
2405 : * last block in the file can always be removed since it can't cause
2406 : * a bmap btree split to do that.
2407 : */
2408 : STATIC int
2409 0 : xfs_da3_swap_lastblock(
2410 : struct xfs_da_args *args,
2411 : xfs_dablk_t *dead_blknop,
2412 : struct xfs_buf **dead_bufp)
2413 0 : {
2414 0 : struct xfs_da_blkinfo *dead_info;
2415 0 : struct xfs_da_blkinfo *sib_info;
2416 0 : struct xfs_da_intnode *par_node;
2417 0 : struct xfs_da_intnode *dead_node;
2418 0 : struct xfs_dir2_leaf *dead_leaf2;
2419 0 : struct xfs_da_node_entry *btree;
2420 0 : struct xfs_da3_icnode_hdr par_hdr;
2421 0 : struct xfs_inode *dp;
2422 0 : struct xfs_trans *tp;
2423 0 : struct xfs_mount *mp;
2424 0 : struct xfs_buf *dead_buf;
2425 0 : struct xfs_buf *last_buf;
2426 0 : struct xfs_buf *sib_buf;
2427 0 : struct xfs_buf *par_buf;
2428 0 : xfs_failaddr_t fa;
2429 0 : xfs_dahash_t dead_hash;
2430 0 : xfs_fileoff_t lastoff;
2431 0 : xfs_dablk_t dead_blkno;
2432 0 : xfs_dablk_t last_blkno;
2433 0 : xfs_dablk_t sib_blkno;
2434 0 : xfs_dablk_t par_blkno;
2435 0 : int error;
2436 0 : int w;
2437 0 : int entno;
2438 0 : int level;
2439 0 : int dead_level;
2440 :
2441 0 : trace_xfs_da_swap_lastblock(args);
2442 :
2443 0 : dead_buf = *dead_bufp;
2444 0 : dead_blkno = *dead_blknop;
2445 0 : tp = args->trans;
2446 0 : dp = args->dp;
2447 0 : w = args->whichfork;
2448 0 : ASSERT(w == XFS_DATA_FORK);
2449 0 : mp = dp->i_mount;
2450 0 : lastoff = args->geo->freeblk;
2451 0 : error = xfs_bmap_last_before(tp, dp, &lastoff, w);
2452 0 : if (error)
2453 : return error;
2454 0 : if (XFS_IS_CORRUPT(mp, lastoff == 0)) {
2455 0 : xfs_da_mark_sick(args);
2456 0 : return -EFSCORRUPTED;
2457 : }
2458 : /*
2459 : * Read the last block in the btree space.
2460 : */
2461 0 : last_blkno = (xfs_dablk_t)lastoff - args->geo->fsbcount;
2462 0 : error = xfs_da3_node_read(tp, dp, last_blkno, &last_buf, w);
2463 0 : if (error)
2464 : return error;
2465 0 : fa = xfs_da3_header_check(last_buf, args->owner);
2466 0 : if (fa) {
2467 0 : __xfs_buf_mark_corrupt(last_buf, fa);
2468 0 : xfs_trans_brelse(tp, last_buf);
2469 0 : xfs_da_mark_sick(args);
2470 0 : return -EFSCORRUPTED;
2471 : }
2472 :
2473 : /*
2474 : * Copy the last block into the dead buffer and log it.
2475 : */
2476 0 : memcpy(dead_buf->b_addr, last_buf->b_addr, args->geo->blksize);
2477 0 : xfs_trans_log_buf(tp, dead_buf, 0, args->geo->blksize - 1);
2478 0 : dead_info = dead_buf->b_addr;
2479 : /*
2480 : * Get values from the moved block.
2481 : */
2482 0 : if (dead_info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
2483 : dead_info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
2484 0 : struct xfs_dir3_icleaf_hdr leafhdr;
2485 0 : struct xfs_dir2_leaf_entry *ents;
2486 :
2487 0 : dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;
2488 0 : xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr,
2489 : dead_leaf2);
2490 0 : ents = leafhdr.ents;
2491 0 : dead_level = 0;
2492 0 : dead_hash = be32_to_cpu(ents[leafhdr.count - 1].hashval);
2493 : } else {
2494 0 : struct xfs_da3_icnode_hdr deadhdr;
2495 :
2496 0 : dead_node = (xfs_da_intnode_t *)dead_info;
2497 0 : xfs_da3_node_hdr_from_disk(dp->i_mount, &deadhdr, dead_node);
2498 0 : btree = deadhdr.btree;
2499 0 : dead_level = deadhdr.level;
2500 0 : dead_hash = be32_to_cpu(btree[deadhdr.count - 1].hashval);
2501 : }
2502 0 : sib_buf = par_buf = NULL;
2503 : /*
2504 : * If the moved block has a left sibling, fix up the pointers.
2505 : */
2506 0 : if ((sib_blkno = be32_to_cpu(dead_info->back))) {
2507 0 : error = xfs_da3_node_read(tp, dp, sib_blkno, &sib_buf, w);
2508 0 : if (error)
2509 0 : goto done;
2510 0 : fa = xfs_da3_header_check(sib_buf, args->owner);
2511 0 : if (fa) {
2512 0 : __xfs_buf_mark_corrupt(sib_buf, fa);
2513 0 : xfs_da_mark_sick(args);
2514 0 : error = -EFSCORRUPTED;
2515 0 : goto done;
2516 : }
2517 0 : sib_info = sib_buf->b_addr;
2518 0 : if (XFS_IS_CORRUPT(mp,
2519 : be32_to_cpu(sib_info->forw) != last_blkno ||
2520 : sib_info->magic != dead_info->magic)) {
2521 0 : xfs_da_mark_sick(args);
2522 0 : error = -EFSCORRUPTED;
2523 0 : goto done;
2524 : }
2525 0 : sib_info->forw = cpu_to_be32(dead_blkno);
2526 0 : xfs_trans_log_buf(tp, sib_buf,
2527 : XFS_DA_LOGRANGE(sib_info, &sib_info->forw,
2528 : sizeof(sib_info->forw)));
2529 0 : sib_buf = NULL;
2530 : }
2531 : /*
2532 : * If the moved block has a right sibling, fix up the pointers.
2533 : */
2534 0 : if ((sib_blkno = be32_to_cpu(dead_info->forw))) {
2535 0 : error = xfs_da3_node_read(tp, dp, sib_blkno, &sib_buf, w);
2536 0 : if (error)
2537 0 : goto done;
2538 0 : fa = xfs_da3_header_check(sib_buf, args->owner);
2539 0 : if (fa) {
2540 0 : __xfs_buf_mark_corrupt(sib_buf, fa);
2541 0 : xfs_da_mark_sick(args);
2542 0 : error = -EFSCORRUPTED;
2543 0 : goto done;
2544 : }
2545 0 : sib_info = sib_buf->b_addr;
2546 0 : if (XFS_IS_CORRUPT(mp,
2547 : be32_to_cpu(sib_info->back) != last_blkno ||
2548 : sib_info->magic != dead_info->magic)) {
2549 0 : xfs_da_mark_sick(args);
2550 0 : error = -EFSCORRUPTED;
2551 0 : goto done;
2552 : }
2553 0 : sib_info->back = cpu_to_be32(dead_blkno);
2554 0 : xfs_trans_log_buf(tp, sib_buf,
2555 : XFS_DA_LOGRANGE(sib_info, &sib_info->back,
2556 : sizeof(sib_info->back)));
2557 0 : sib_buf = NULL;
2558 : }
2559 0 : par_blkno = args->geo->leafblk;
2560 0 : level = -1;
2561 : /*
2562 : * Walk down the tree looking for the parent of the moved block.
2563 : */
2564 0 : for (;;) {
2565 0 : error = xfs_da3_node_read(tp, dp, par_blkno, &par_buf, w);
2566 0 : if (error)
2567 0 : goto done;
2568 0 : fa = xfs_da3_node_header_check(par_buf, args->owner);
2569 0 : if (fa) {
2570 0 : __xfs_buf_mark_corrupt(par_buf, fa);
2571 0 : xfs_da_mark_sick(args);
2572 0 : error = -EFSCORRUPTED;
2573 0 : goto done;
2574 : }
2575 0 : par_node = par_buf->b_addr;
2576 0 : xfs_da3_node_hdr_from_disk(dp->i_mount, &par_hdr, par_node);
2577 0 : if (XFS_IS_CORRUPT(mp,
2578 : level >= 0 && level != par_hdr.level + 1)) {
2579 0 : xfs_da_mark_sick(args);
2580 0 : error = -EFSCORRUPTED;
2581 0 : goto done;
2582 : }
2583 0 : level = par_hdr.level;
2584 0 : btree = par_hdr.btree;
2585 0 : for (entno = 0;
2586 0 : entno < par_hdr.count &&
2587 0 : be32_to_cpu(btree[entno].hashval) < dead_hash;
2588 0 : entno++)
2589 0 : continue;
2590 0 : if (XFS_IS_CORRUPT(mp, entno == par_hdr.count)) {
2591 0 : xfs_da_mark_sick(args);
2592 0 : error = -EFSCORRUPTED;
2593 0 : goto done;
2594 : }
2595 0 : par_blkno = be32_to_cpu(btree[entno].before);
2596 0 : if (level == dead_level + 1)
2597 : break;
2598 0 : xfs_trans_brelse(tp, par_buf);
2599 0 : par_buf = NULL;
2600 : }
2601 : /*
2602 : * We're in the right parent block.
2603 : * Look for the right entry.
2604 : */
2605 0 : for (;;) {
2606 0 : for (;
2607 0 : entno < par_hdr.count &&
2608 0 : be32_to_cpu(btree[entno].before) != last_blkno;
2609 0 : entno++)
2610 0 : continue;
2611 0 : if (entno < par_hdr.count)
2612 : break;
2613 0 : par_blkno = par_hdr.forw;
2614 0 : xfs_trans_brelse(tp, par_buf);
2615 0 : par_buf = NULL;
2616 0 : if (XFS_IS_CORRUPT(mp, par_blkno == 0)) {
2617 0 : xfs_da_mark_sick(args);
2618 0 : error = -EFSCORRUPTED;
2619 0 : goto done;
2620 : }
2621 0 : error = xfs_da3_node_read(tp, dp, par_blkno, &par_buf, w);
2622 0 : if (error)
2623 0 : goto done;
2624 0 : fa = xfs_da3_node_header_check(par_buf, args->owner);
2625 0 : if (fa) {
2626 0 : __xfs_buf_mark_corrupt(par_buf, fa);
2627 0 : xfs_da_mark_sick(args);
2628 0 : error = -EFSCORRUPTED;
2629 0 : goto done;
2630 : }
2631 0 : par_node = par_buf->b_addr;
2632 0 : xfs_da3_node_hdr_from_disk(dp->i_mount, &par_hdr, par_node);
2633 0 : if (XFS_IS_CORRUPT(mp, par_hdr.level != level)) {
2634 0 : xfs_da_mark_sick(args);
2635 0 : error = -EFSCORRUPTED;
2636 0 : goto done;
2637 : }
2638 0 : btree = par_hdr.btree;
2639 0 : entno = 0;
2640 : }
2641 : /*
2642 : * Update the parent entry pointing to the moved block.
2643 : */
2644 0 : btree[entno].before = cpu_to_be32(dead_blkno);
2645 0 : xfs_trans_log_buf(tp, par_buf,
2646 0 : XFS_DA_LOGRANGE(par_node, &btree[entno].before,
2647 : sizeof(btree[entno].before)));
2648 0 : *dead_blknop = last_blkno;
2649 0 : *dead_bufp = last_buf;
2650 0 : return 0;
2651 0 : done:
2652 0 : if (par_buf)
2653 0 : xfs_trans_brelse(tp, par_buf);
2654 0 : if (sib_buf)
2655 0 : xfs_trans_brelse(tp, sib_buf);
2656 0 : xfs_trans_brelse(tp, last_buf);
2657 0 : return error;
2658 : }
2659 :
2660 : /*
2661 : * Remove a btree block from a directory or attribute.
2662 : */
2663 : int
2664 4530327 : xfs_da_shrink_inode(
2665 : struct xfs_da_args *args,
2666 : xfs_dablk_t dead_blkno,
2667 : struct xfs_buf *dead_buf)
2668 : {
2669 4530327 : struct xfs_inode *dp;
2670 4530327 : int done, error, w, count;
2671 4530327 : struct xfs_trans *tp;
2672 :
2673 4530327 : trace_xfs_da_shrink_inode(args);
2674 :
2675 4530427 : dp = args->dp;
2676 4530427 : w = args->whichfork;
2677 4530427 : tp = args->trans;
2678 4530427 : count = args->geo->fsbcount;
2679 4530419 : for (;;) {
2680 : /*
2681 : * Remove extents. If we get ENOSPC for a dir we have to move
2682 : * the last block to the place we want to kill.
2683 : */
2684 4558283 : error = xfs_bunmapi(tp, dp, dead_blkno, count,
2685 : xfs_bmapi_aflag(w), 0, &done);
2686 4530394 : if (error == -ENOSPC) {
2687 0 : if (w != XFS_DATA_FORK)
2688 : break;
2689 0 : error = xfs_da3_swap_lastblock(args, &dead_blkno,
2690 : &dead_buf);
2691 0 : if (error)
2692 : break;
2693 : } else {
2694 : break;
2695 : }
2696 : }
2697 4530394 : xfs_trans_binval(tp, dead_buf);
2698 4530421 : return error;
2699 : }
2700 :
2701 : static int
2702 2132464888 : xfs_dabuf_map(
2703 : struct xfs_inode *dp,
2704 : xfs_dablk_t bno,
2705 : unsigned int flags,
2706 : int whichfork,
2707 : struct xfs_buf_map **mapp,
2708 : int *nmaps)
2709 : {
2710 2132464888 : struct xfs_mount *mp = dp->i_mount;
2711 2132464888 : int nfsb = xfs_dabuf_nfsb(mp, whichfork);
2712 2132464888 : struct xfs_bmbt_irec irec, *irecs = &irec;
2713 2132464888 : struct xfs_buf_map *map = *mapp;
2714 2132464888 : xfs_fileoff_t off = bno;
2715 2132464888 : int error = 0, nirecs, i;
2716 :
2717 2132464888 : if (nfsb > 1)
2718 647072 : irecs = kmem_zalloc(sizeof(irec) * nfsb, KM_NOFS);
2719 :
2720 2132954573 : nirecs = nfsb;
2721 2951494140 : error = xfs_bmapi_read(dp, bno, nfsb, irecs, &nirecs,
2722 : xfs_bmapi_aflag(whichfork));
2723 2133871907 : if (error)
2724 179 : goto out_free_irecs;
2725 :
2726 : /*
2727 : * Use the caller provided map for the single map case, else allocate a
2728 : * larger one that needs to be free by the caller.
2729 : */
2730 2133871728 : if (nirecs > 1) {
2731 68748 : map = kmem_zalloc(nirecs * sizeof(struct xfs_buf_map), KM_NOFS);
2732 68748 : if (!map) {
2733 0 : error = -ENOMEM;
2734 0 : goto out_free_irecs;
2735 : }
2736 68748 : *mapp = map;
2737 : }
2738 :
2739 4267276793 : for (i = 0; i < nirecs; i++) {
2740 2133591210 : if (irecs[i].br_startblock == HOLESTARTBLOCK ||
2741 : irecs[i].br_startblock == DELAYSTARTBLOCK)
2742 186145 : goto invalid_mapping;
2743 2133405065 : if (off != irecs[i].br_startoff)
2744 0 : goto invalid_mapping;
2745 :
2746 2133405065 : map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);
2747 2133405065 : map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);
2748 2133405065 : off += irecs[i].br_blockcount;
2749 : }
2750 :
2751 2133685583 : if (off != bno + nfsb)
2752 0 : goto invalid_mapping;
2753 :
2754 2133685583 : *nmaps = nirecs;
2755 2133871907 : out_free_irecs:
2756 2133871907 : if (irecs != &irec)
2757 647072 : kmem_free(irecs);
2758 2133871907 : return error;
2759 :
2760 186145 : invalid_mapping:
2761 : /* Caller ok with no mapping. */
2762 186145 : if (XFS_IS_CORRUPT(mp, !(flags & XFS_DABUF_MAP_HOLE_OK))) {
2763 0 : xfs_dirattr_mark_sick(dp, whichfork);
2764 0 : error = -EFSCORRUPTED;
2765 0 : if (xfs_error_level >= XFS_ERRLEVEL_LOW) {
2766 0 : xfs_alert(mp, "%s: bno %u inode %llu",
2767 : __func__, bno, dp->i_ino);
2768 :
2769 0 : for (i = 0; i < nirecs; i++) {
2770 0 : xfs_alert(mp,
2771 : "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
2772 : i, irecs[i].br_startoff,
2773 : irecs[i].br_startblock,
2774 : irecs[i].br_blockcount,
2775 : irecs[i].br_state);
2776 : }
2777 : }
2778 : } else {
2779 186145 : *nmaps = 0;
2780 : }
2781 186145 : goto out_free_irecs;
2782 : }
2783 :
2784 : /*
2785 : * Get a buffer for the dir/attr block.
2786 : */
2787 : int
2788 9346111 : xfs_da_get_buf(
2789 : struct xfs_trans *tp,
2790 : struct xfs_inode *dp,
2791 : xfs_dablk_t bno,
2792 : struct xfs_buf **bpp,
2793 : int whichfork)
2794 : {
2795 9346111 : struct xfs_mount *mp = dp->i_mount;
2796 9346111 : struct xfs_buf *bp;
2797 9346111 : struct xfs_buf_map map, *mapp = ↦
2798 9346111 : int nmap = 1;
2799 9346111 : int error;
2800 :
2801 9346111 : *bpp = NULL;
2802 9346111 : error = xfs_dabuf_map(dp, bno, 0, whichfork, &mapp, &nmap);
2803 9346283 : if (error || nmap == 0)
2804 2 : goto out_free;
2805 :
2806 9346281 : error = xfs_trans_get_buf_map(tp, mp->m_ddev_targp, mapp, nmap, 0, &bp);
2807 9346527 : if (error)
2808 0 : goto out_free;
2809 :
2810 9346527 : *bpp = bp;
2811 :
2812 9346529 : out_free:
2813 9346529 : if (mapp != &map)
2814 42 : kmem_free(mapp);
2815 :
2816 9346529 : return error;
2817 : }
2818 :
2819 : /*
2820 : * Get a buffer for the dir/attr block, fill in the contents.
2821 : */
2822 : int
2823 2004305360 : xfs_da_read_buf(
2824 : struct xfs_trans *tp,
2825 : struct xfs_inode *dp,
2826 : xfs_dablk_t bno,
2827 : unsigned int flags,
2828 : struct xfs_buf **bpp,
2829 : int whichfork,
2830 : const struct xfs_buf_ops *ops)
2831 : {
2832 2004305360 : struct xfs_mount *mp = dp->i_mount;
2833 2004305360 : struct xfs_buf *bp;
2834 2004305360 : struct xfs_buf_map map, *mapp = ↦
2835 2004305360 : int nmap = 1;
2836 2004305360 : int error;
2837 :
2838 2004305360 : *bpp = NULL;
2839 2004305360 : error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
2840 2005585056 : if (error || !nmap)
2841 186314 : goto out_free;
2842 :
2843 2005398742 : error = xfs_trans_read_buf_map(mp, tp, mp->m_ddev_targp, mapp, nmap, 0,
2844 : &bp, ops);
2845 2005330525 : if (xfs_metadata_is_sick(error))
2846 246 : xfs_dirattr_mark_sick(dp, whichfork);
2847 2005330525 : if (error)
2848 9319 : goto out_free;
2849 :
2850 2005321206 : if (whichfork == XFS_ATTR_FORK)
2851 1305769366 : xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
2852 : else
2853 699551840 : xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
2854 2005556124 : *bpp = bp;
2855 2005751757 : out_free:
2856 2005751757 : if (mapp != &map)
2857 68706 : kmem_free(mapp);
2858 :
2859 2005751757 : return error;
2860 : }
2861 :
2862 : /*
2863 : * Readahead the dir/attr block.
2864 : */
2865 : int
2866 118729695 : xfs_da_reada_buf(
2867 : struct xfs_inode *dp,
2868 : xfs_dablk_t bno,
2869 : unsigned int flags,
2870 : int whichfork,
2871 : const struct xfs_buf_ops *ops)
2872 : {
2873 118729695 : struct xfs_buf_map map;
2874 118729695 : struct xfs_buf_map *mapp;
2875 118729695 : int nmap;
2876 118729695 : int error;
2877 :
2878 118729695 : mapp = ↦
2879 118729695 : nmap = 1;
2880 118729695 : error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
2881 118748787 : if (error || !nmap)
2882 8 : goto out_free;
2883 :
2884 118748779 : xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap, ops);
2885 :
2886 118736802 : out_free:
2887 118736802 : if (mapp != &map)
2888 0 : kmem_free(mapp);
2889 :
2890 118736802 : return error;
2891 : }
|
