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 231971170 : xfs_da_state_alloc(
85 : struct xfs_da_args *args)
86 : {
87 231971170 : struct xfs_da_state *state;
88 :
89 231971170 : state = kmem_cache_zalloc(xfs_da_state_cache, GFP_NOFS | __GFP_NOFAIL);
90 232633531 : state->args = args;
91 232633531 : state->mp = args->dp->i_mount;
92 232633531 : return state;
93 : }
94 :
95 : /*
96 : * Kill the altpath contents of a da-state structure.
97 : */
98 : STATIC void
99 232323278 : xfs_da_state_kill_altpath(xfs_da_state_t *state)
100 : {
101 232323278 : int i;
102 :
103 232459472 : for (i = 0; i < state->altpath.active; i++)
104 229072 : state->altpath.blk[i].bp = NULL;
105 232230400 : state->altpath.active = 0;
106 232230400 : }
107 :
108 : /*
109 : * Free a da-state structure.
110 : */
111 : void
112 232437586 : xfs_da_state_free(xfs_da_state_t *state)
113 : {
114 232437586 : xfs_da_state_kill_altpath(state);
115 : #ifdef DEBUG
116 232290675 : memset((char *)state, 0, sizeof(*state));
117 : #endif /* DEBUG */
118 232290675 : kmem_cache_free(xfs_da_state_cache, state);
119 232383247 : }
120 :
121 : void
122 7850 : xfs_da_state_reset(
123 : struct xfs_da_state *state,
124 : struct xfs_da_args *args)
125 : {
126 7850 : xfs_da_state_kill_altpath(state);
127 7850 : memset(state, 0, sizeof(struct xfs_da_state));
128 7850 : state->args = args;
129 7850 : state->mp = state->args->dp->i_mount;
130 7850 : }
131 :
132 : static inline int xfs_dabuf_nfsb(struct xfs_mount *mp, int whichfork)
133 : {
134 3738821531 : if (whichfork == XFS_DATA_FORK)
135 1782219505 : return mp->m_dir_geo->fsbcount;
136 1956602026 : return mp->m_attr_geo->fsbcount;
137 : }
138 :
139 : void
140 1018297383 : 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 1018297383 : if (xfs_has_crc(mp)) {
146 1018297383 : struct xfs_da3_intnode *from3 = (struct xfs_da3_intnode *)from;
147 :
148 1018297383 : to->forw = be32_to_cpu(from3->hdr.info.hdr.forw);
149 1018297383 : to->back = be32_to_cpu(from3->hdr.info.hdr.back);
150 1018297383 : to->magic = be16_to_cpu(from3->hdr.info.hdr.magic);
151 1018297383 : to->count = be16_to_cpu(from3->hdr.__count);
152 1018297383 : to->level = be16_to_cpu(from3->hdr.__level);
153 1018297383 : to->btree = from3->__btree;
154 1018297383 : 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 1018297383 : }
165 :
166 : void
167 505076 : 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 505076 : if (xfs_has_crc(mp)) {
173 505076 : struct xfs_da3_intnode *to3 = (struct xfs_da3_intnode *)to;
174 :
175 505076 : ASSERT(from->magic == XFS_DA3_NODE_MAGIC);
176 505076 : to3->hdr.info.hdr.forw = cpu_to_be32(from->forw);
177 505076 : to3->hdr.info.hdr.back = cpu_to_be32(from->back);
178 505076 : to3->hdr.info.hdr.magic = cpu_to_be16(from->magic);
179 505076 : to3->hdr.__count = cpu_to_be16(from->count);
180 505076 : 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 505076 : }
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 47507003 : xfs_da3_blkinfo_verify(
198 : struct xfs_buf *bp,
199 : struct xfs_da3_blkinfo *hdr3)
200 : {
201 47507003 : struct xfs_mount *mp = bp->b_mount;
202 47507003 : struct xfs_da_blkinfo *hdr = &hdr3->hdr;
203 :
204 47507003 : if (!xfs_verify_magic16(bp, hdr->magic))
205 0 : return __this_address;
206 :
207 47491350 : if (xfs_has_crc(mp)) {
208 47491350 : if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))
209 0 : return __this_address;
210 47492587 : if (be64_to_cpu(hdr3->blkno) != xfs_buf_daddr(bp))
211 0 : return __this_address;
212 47492587 : 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 240455 : xfs_da3_node_verify(
221 : struct xfs_buf *bp)
222 : {
223 240455 : struct xfs_mount *mp = bp->b_mount;
224 240455 : struct xfs_da_intnode *hdr = bp->b_addr;
225 240455 : struct xfs_da3_icnode_hdr ichdr;
226 240455 : xfs_failaddr_t fa;
227 :
228 240455 : xfs_da3_node_hdr_from_disk(mp, &ichdr, hdr);
229 :
230 240457 : fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);
231 240451 : if (fa)
232 : return fa;
233 :
234 240453 : if (ichdr.level == 0)
235 0 : return __this_address;
236 240453 : if (ichdr.level > XFS_DA_NODE_MAXDEPTH)
237 0 : return __this_address;
238 240453 : 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 240453 : 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 255665902 : xfs_da3_node_header_check(
256 : struct xfs_buf *bp,
257 : xfs_ino_t owner)
258 : {
259 255665902 : struct xfs_mount *mp = bp->b_mount;
260 :
261 255665902 : if (xfs_has_crc(mp)) {
262 255665902 : struct xfs_da3_blkinfo *hdr3 = bp->b_addr;
263 :
264 255665902 : ASSERT(hdr3->hdr.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
265 :
266 255665902 : if (be64_to_cpu(hdr3->owner) != owner)
267 0 : return __this_address;
268 : }
269 :
270 : return NULL;
271 : }
272 :
273 : xfs_failaddr_t
274 2884865 : xfs_da3_header_check(
275 : struct xfs_buf *bp,
276 : xfs_ino_t owner)
277 : {
278 2884865 : struct xfs_mount *mp = bp->b_mount;
279 2884865 : struct xfs_da_blkinfo *hdr = bp->b_addr;
280 :
281 2884865 : if (!xfs_has_crc(mp))
282 : return NULL;
283 :
284 2884865 : switch (hdr->magic) {
285 2463185 : case cpu_to_be16(XFS_ATTR3_LEAF_MAGIC):
286 2463185 : return xfs_attr3_leaf_header_check(bp, owner);
287 66851 : case cpu_to_be16(XFS_DA3_NODE_MAGIC):
288 66851 : return xfs_da3_node_header_check(bp, owner);
289 354829 : case cpu_to_be16(XFS_DIR3_LEAF1_MAGIC):
290 : case cpu_to_be16(XFS_DIR3_LEAFN_MAGIC):
291 354829 : return xfs_dir3_leaf_header_check(bp, owner);
292 : }
293 :
294 0 : ASSERT(0);
295 0 : return NULL;
296 : }
297 :
298 : static void
299 135876 : xfs_da3_node_write_verify(
300 : struct xfs_buf *bp)
301 : {
302 135876 : struct xfs_mount *mp = bp->b_mount;
303 135876 : struct xfs_buf_log_item *bip = bp->b_log_item;
304 135876 : struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
305 135876 : xfs_failaddr_t fa;
306 :
307 135876 : fa = xfs_da3_node_verify(bp);
308 135876 : if (fa) {
309 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
310 0 : return;
311 : }
312 :
313 135876 : if (!xfs_has_crc(mp))
314 : return;
315 :
316 135876 : if (bip)
317 135876 : hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
318 :
319 135876 : 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 230913 : xfs_da3_node_read_verify(
330 : struct xfs_buf *bp)
331 : {
332 230913 : struct xfs_da_blkinfo *info = bp->b_addr;
333 230913 : xfs_failaddr_t fa;
334 :
335 230913 : switch (be16_to_cpu(info->magic)) {
336 : case XFS_DA3_NODE_MAGIC:
337 37205 : if (!xfs_buf_verify_cksum(bp, XFS_DA3_NODE_CRC_OFF)) {
338 80 : xfs_verifier_error(bp, -EFSBADCRC,
339 40 : __this_address);
340 40 : break;
341 : }
342 37165 : fallthrough;
343 : case XFS_DA_NODE_MAGIC:
344 37165 : fa = xfs_da3_node_verify(bp);
345 37165 : if (fa)
346 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
347 : return;
348 72058 : case XFS_ATTR_LEAF_MAGIC:
349 : case XFS_ATTR3_LEAF_MAGIC:
350 72058 : bp->b_ops = &xfs_attr3_leaf_buf_ops;
351 72058 : bp->b_ops->verify_read(bp);
352 72058 : return;
353 121641 : case XFS_DIR2_LEAFN_MAGIC:
354 : case XFS_DIR3_LEAFN_MAGIC:
355 121641 : bp->b_ops = &xfs_dir3_leafn_buf_ops;
356 121641 : bp->b_ops->verify_read(bp);
357 121641 : return;
358 : default:
359 9 : xfs_verifier_error(bp, -EFSCORRUPTED, __this_address);
360 9 : break;
361 : }
362 : }
363 :
364 : /* Verify the structure of a da3 block. */
365 : static xfs_failaddr_t
366 67414 : xfs_da3_node_verify_struct(
367 : struct xfs_buf *bp)
368 : {
369 67414 : struct xfs_da_blkinfo *info = bp->b_addr;
370 :
371 67414 : switch (be16_to_cpu(info->magic)) {
372 67414 : case XFS_DA3_NODE_MAGIC:
373 : case XFS_DA_NODE_MAGIC:
374 67414 : 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 979633633 : 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 979633633 : struct xfs_da_blkinfo *info = bp->b_addr;
405 :
406 979633633 : switch (be16_to_cpu(info->magic)) {
407 208093861 : case XFS_DA_NODE_MAGIC:
408 : case XFS_DA3_NODE_MAGIC:
409 208093861 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
410 208093861 : return 0;
411 589372860 : case XFS_ATTR_LEAF_MAGIC:
412 : case XFS_ATTR3_LEAF_MAGIC:
413 589372860 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_ATTR_LEAF_BUF);
414 589372860 : return 0;
415 182166912 : case XFS_DIR2_LEAFN_MAGIC:
416 : case XFS_DIR3_LEAFN_MAGIC:
417 182166912 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
418 182166912 : 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 1071830992 : 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 1071830992 : int error;
437 :
438 1071830992 : error = xfs_da_read_buf(tp, dp, bno, 0, bpp, whichfork,
439 : &xfs_da3_node_buf_ops);
440 1072950424 : if (error || !*bpp || !tp)
441 : return error;
442 979692391 : return xfs_da3_node_set_type(tp, dp, whichfork, *bpp);
443 : }
444 :
445 : int
446 44374 : 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 44374 : struct xfs_mount *mp = dp->i_mount;
454 44374 : int error;
455 :
456 44374 : error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, mappedbno,
457 88748 : XFS_FSB_TO_BB(mp, xfs_dabuf_nfsb(mp, whichfork)), 0,
458 : bpp, &xfs_da3_node_buf_ops);
459 44376 : if (xfs_metadata_is_sick(error))
460 0 : xfs_dirattr_mark_sick(dp, whichfork);
461 44376 : if (error || !*bpp)
462 : return error;
463 :
464 44376 : if (whichfork == XFS_ATTR_FORK)
465 44376 : xfs_buf_set_ref(*bpp, XFS_ATTR_BTREE_REF);
466 : else
467 0 : xfs_buf_set_ref(*bpp, XFS_DIR_BTREE_REF);
468 :
469 44373 : if (!tp)
470 : return 0;
471 44373 : 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 85524 : 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 85524 : struct xfs_da_intnode *node;
490 85524 : struct xfs_trans *tp = args->trans;
491 85524 : struct xfs_mount *mp = tp->t_mountp;
492 85524 : struct xfs_da3_icnode_hdr ichdr = {0};
493 85524 : struct xfs_buf *bp;
494 85524 : int error;
495 85524 : struct xfs_inode *dp = args->dp;
496 :
497 85524 : trace_xfs_da_node_create(args);
498 85524 : ASSERT(level <= XFS_DA_NODE_MAXDEPTH);
499 :
500 85524 : error = xfs_da_get_buf(tp, dp, blkno, &bp, whichfork);
501 85524 : if (error)
502 : return error;
503 85524 : bp->b_ops = &xfs_da3_node_buf_ops;
504 85524 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
505 85524 : node = bp->b_addr;
506 :
507 85524 : if (xfs_has_crc(mp)) {
508 85524 : struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
509 :
510 85524 : memset(hdr3, 0, sizeof(struct xfs_da3_node_hdr));
511 85524 : ichdr.magic = XFS_DA3_NODE_MAGIC;
512 85524 : hdr3->info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
513 85524 : hdr3->info.owner = cpu_to_be64(args->owner);
514 85524 : uuid_copy(&hdr3->info.uuid, &mp->m_sb.sb_meta_uuid);
515 : } else {
516 0 : ichdr.magic = XFS_DA_NODE_MAGIC;
517 : }
518 85524 : ichdr.level = level;
519 :
520 85524 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &ichdr);
521 85524 : xfs_trans_log_buf(tp, bp,
522 85524 : XFS_DA_LOGRANGE(node, &node->hdr, args->geo->node_hdr_size));
523 :
524 85524 : *bpp = bp;
525 85524 : return 0;
526 : }
527 :
528 : /*
529 : * Split a leaf node, rebalance, then possibly split
530 : * intermediate nodes, rebalance, etc.
531 : */
532 : int /* error */
533 280738 : xfs_da3_split(
534 : struct xfs_da_state *state)
535 : {
536 280738 : struct xfs_da_state_blk *oldblk;
537 280738 : struct xfs_da_state_blk *newblk;
538 280738 : struct xfs_da_state_blk *addblk;
539 280738 : struct xfs_da_intnode *node;
540 280738 : int max;
541 280738 : int action = 0;
542 280738 : int error;
543 280738 : int i;
544 :
545 280738 : trace_xfs_da_split(state->args);
546 :
547 280736 : 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 280725 : max = state->path.active - 1;
557 280725 : ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
558 280725 : ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
559 : state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
560 :
561 280726 : addblk = &state->path.blk[max]; /* initial dummy value */
562 832726 : for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
563 552000 : oldblk = &state->path.blk[i];
564 552000 : 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 551999 : switch (oldblk->magic) {
573 195153 : case XFS_ATTR_LEAF_MAGIC:
574 195153 : error = xfs_attr3_leaf_split(state, oldblk, newblk);
575 195153 : if ((error != 0) && (error != -ENOSPC)) {
576 0 : return error; /* GROT: attr is inconsistent */
577 : }
578 195153 : 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 85572 : case XFS_DIR2_LEAFN_MAGIC:
604 85572 : error = xfs_dir2_leafn_split(state, oldblk, newblk);
605 85577 : if (error)
606 0 : return error;
607 : addblk = newblk;
608 : break;
609 271274 : case XFS_DA_NODE_MAGIC:
610 271274 : error = xfs_da3_node_split(state, oldblk, newblk, addblk,
611 : max - i, &action);
612 271273 : addblk->bp = NULL;
613 271273 : if (error)
614 0 : return error; /* GROT: dir is inconsistent */
615 : /*
616 : * Record the newly split block for the next time thru?
617 : */
618 271273 : if (action)
619 : addblk = newblk;
620 : else
621 270748 : addblk = NULL;
622 : break;
623 : }
624 :
625 : /*
626 : * Update the btree to show the new hashval for this child.
627 : */
628 552003 : xfs_da3_fixhashpath(state, &state->path);
629 : }
630 280726 : 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 9980 : ASSERT(state->extravalid == 0 ||
639 : state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
640 :
641 : /*
642 : * Split the root node.
643 : */
644 9980 : ASSERT(state->path.active == 0);
645 9980 : oldblk = &state->path.blk[0];
646 9980 : error = xfs_da3_root_split(state, oldblk, addblk);
647 9980 : 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 9980 : node = oldblk->bp->b_addr;
662 9980 : if (node->hdr.info.forw) {
663 9980 : 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 9980 : node = addblk->bp->b_addr;
670 9980 : node->hdr.info.back = cpu_to_be32(oldblk->blkno);
671 9980 : xfs_trans_log_buf(state->args->trans, addblk->bp,
672 : XFS_DA_LOGRANGE(node, &node->hdr.info,
673 : sizeof(node->hdr.info)));
674 : }
675 9980 : node = oldblk->bp->b_addr;
676 9980 : 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 9980 : out:
690 9980 : addblk->bp = NULL;
691 9980 : 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 9980 : 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 9980 : struct xfs_da_intnode *node;
706 9980 : struct xfs_da_intnode *oldroot;
707 9980 : struct xfs_da_node_entry *btree;
708 9980 : struct xfs_da3_icnode_hdr nodehdr;
709 9980 : struct xfs_da_args *args;
710 9980 : struct xfs_buf *bp;
711 9980 : struct xfs_inode *dp;
712 9980 : struct xfs_trans *tp;
713 9980 : struct xfs_dir2_leaf *leaf;
714 9980 : xfs_dablk_t blkno;
715 9980 : int level;
716 9980 : int error;
717 9980 : int size;
718 :
719 9980 : 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 9980 : args = state->args;
726 9980 : error = xfs_da_grow_inode(args, &blkno);
727 9980 : if (error)
728 : return error;
729 :
730 9980 : dp = args->dp;
731 9980 : tp = args->trans;
732 9980 : error = xfs_da_get_buf(tp, dp, blkno, &bp, args->whichfork);
733 9980 : if (error)
734 : return error;
735 9980 : node = bp->b_addr;
736 9980 : oldroot = blk1->bp->b_addr;
737 9980 : 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 49 : struct xfs_da3_icnode_hdr icnodehdr;
740 :
741 49 : xfs_da3_node_hdr_from_disk(dp->i_mount, &icnodehdr, oldroot);
742 49 : btree = icnodehdr.btree;
743 49 : size = (int)((char *)&btree[icnodehdr.count] - (char *)oldroot);
744 49 : 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 49 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
751 : } else {
752 9931 : struct xfs_dir3_icleaf_hdr leafhdr;
753 :
754 9931 : leaf = (xfs_dir2_leaf_t *)oldroot;
755 9931 : xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
756 :
757 9931 : ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
758 : leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
759 9931 : size = (int)((char *)&leafhdr.ents[leafhdr.count] -
760 : (char *)leaf);
761 9931 : 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 9931 : 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 19960 : memcpy(node, oldroot, size);
777 9980 : 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 9980 : struct xfs_da3_intnode *node3 = (struct xfs_da3_intnode *)node;
780 :
781 9980 : node3->hdr.info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
782 : }
783 9980 : xfs_trans_log_buf(tp, bp, 0, size - 1);
784 :
785 9980 : bp->b_ops = blk1->bp->b_ops;
786 9980 : xfs_trans_buf_copy_type(bp, blk1->bp);
787 9980 : blk1->bp = bp;
788 9980 : blk1->blkno = blkno;
789 :
790 : /*
791 : * Set up the new root node.
792 : */
793 19921 : error = xfs_da3_node_create(args,
794 9941 : (args->whichfork == XFS_DATA_FORK) ? args->geo->leafblk : 0,
795 : level + 1, &bp, args->whichfork);
796 9979 : if (error)
797 : return error;
798 :
799 9979 : node = bp->b_addr;
800 9979 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
801 9979 : btree = nodehdr.btree;
802 9979 : btree[0].hashval = cpu_to_be32(blk1->hashval);
803 9979 : btree[0].before = cpu_to_be32(blk1->blkno);
804 9979 : btree[1].hashval = cpu_to_be32(blk2->hashval);
805 9979 : btree[1].before = cpu_to_be32(blk2->blkno);
806 9979 : nodehdr.count = 2;
807 9979 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
808 :
809 : #ifdef DEBUG
810 9979 : 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 9979 : xfs_trans_log_buf(tp, bp,
821 9979 : XFS_DA_LOGRANGE(node, btree, sizeof(xfs_da_node_entry_t) * 2));
822 :
823 9979 : return 0;
824 : }
825 :
826 : /*
827 : * Split the node, rebalance, then add the new entry.
828 : */
829 : STATIC int /* error */
830 271273 : 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 271273 : struct xfs_da_intnode *node;
839 271273 : struct xfs_da3_icnode_hdr nodehdr;
840 271273 : xfs_dablk_t blkno;
841 271273 : int newcount;
842 271273 : int error;
843 271273 : int useextra;
844 271273 : struct xfs_inode *dp = state->args->dp;
845 :
846 271273 : trace_xfs_da_node_split(state->args);
847 :
848 271272 : node = oldblk->bp->b_addr;
849 271272 : 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 271271 : useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
855 271271 : newcount = 1 + useextra;
856 : /*
857 : * Do we have to split the node?
858 : */
859 271271 : 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 524 : error = xfs_da_grow_inode(state->args, &blkno);
865 524 : if (error)
866 : return error; /* GROT: dir is inconsistent */
867 :
868 524 : error = xfs_da3_node_create(state->args, blkno, treelevel,
869 524 : &newblk->bp, state->args->whichfork);
870 524 : if (error)
871 : return error; /* GROT: dir is inconsistent */
872 524 : newblk->blkno = blkno;
873 524 : newblk->magic = XFS_DA_NODE_MAGIC;
874 524 : xfs_da3_node_rebalance(state, oldblk, newblk);
875 524 : error = xfs_da3_blk_link(state, oldblk, newblk);
876 524 : if (error)
877 : return error;
878 524 : *result = 1;
879 : } else {
880 270747 : *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 271271 : node = oldblk->bp->b_addr;
896 271271 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
897 271272 : if (oldblk->index <= nodehdr.count) {
898 270882 : oldblk->index++;
899 270882 : xfs_da3_node_add(state, oldblk, addblk);
900 270883 : 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 390 : newblk->index++;
908 390 : xfs_da3_node_add(state, newblk, addblk);
909 390 : 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 524 : 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 524 : struct xfs_da_intnode *node1;
933 524 : struct xfs_da_intnode *node2;
934 524 : struct xfs_da_node_entry *btree1;
935 524 : struct xfs_da_node_entry *btree2;
936 524 : struct xfs_da_node_entry *btree_s;
937 524 : struct xfs_da_node_entry *btree_d;
938 524 : struct xfs_da3_icnode_hdr nodehdr1;
939 524 : struct xfs_da3_icnode_hdr nodehdr2;
940 524 : struct xfs_trans *tp;
941 524 : int count;
942 524 : int tmp;
943 524 : int swap = 0;
944 524 : struct xfs_inode *dp = state->args->dp;
945 :
946 524 : trace_xfs_da_node_rebalance(state->args);
947 :
948 524 : node1 = blk1->bp->b_addr;
949 524 : node2 = blk2->bp->b_addr;
950 524 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
951 524 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
952 524 : btree1 = nodehdr1.btree;
953 524 : 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 524 : 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 524 : count = (nodehdr1.count - nodehdr2.count) / 2;
972 524 : if (count == 0)
973 0 : return;
974 524 : tp = state->args->trans;
975 : /*
976 : * Two cases: high-to-low and low-to-high.
977 : */
978 524 : if (count > 0) {
979 : /*
980 : * Move elements in node2 up to make a hole.
981 : */
982 524 : tmp = nodehdr2.count;
983 524 : 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 524 : nodehdr2.count += count;
995 524 : tmp = count * (uint)sizeof(xfs_da_node_entry_t);
996 524 : btree_s = &btree1[nodehdr1.count - count];
997 524 : btree_d = &btree2[0];
998 1048 : memcpy(btree_d, btree_s, tmp);
999 524 : 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 524 : xfs_da3_node_hdr_to_disk(dp->i_mount, node1, &nodehdr1);
1030 524 : xfs_trans_log_buf(tp, blk1->bp,
1031 524 : XFS_DA_LOGRANGE(node1, &node1->hdr,
1032 : state->args->geo->node_hdr_size));
1033 :
1034 524 : xfs_da3_node_hdr_to_disk(dp->i_mount, node2, &nodehdr2);
1035 524 : xfs_trans_log_buf(tp, blk2->bp,
1036 524 : 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 524 : 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 524 : blk1->hashval = be32_to_cpu(btree1[nodehdr1.count - 1].hashval);
1053 524 : blk2->hashval = be32_to_cpu(btree2[nodehdr2.count - 1].hashval);
1054 :
1055 : /*
1056 : * Adjust the expected index for insertion.
1057 : */
1058 524 : if (blk1->index >= nodehdr1.count) {
1059 390 : blk2->index = blk1->index - nodehdr1.count;
1060 390 : 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 271272 : 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 271272 : struct xfs_da_intnode *node;
1074 271272 : struct xfs_da3_icnode_hdr nodehdr;
1075 271272 : struct xfs_da_node_entry *btree;
1076 271272 : int tmp;
1077 271272 : struct xfs_inode *dp = state->args->dp;
1078 :
1079 271272 : trace_xfs_da_node_add(state->args);
1080 :
1081 271270 : node = oldblk->bp->b_addr;
1082 271270 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1083 271271 : btree = nodehdr.btree;
1084 :
1085 271271 : ASSERT(oldblk->index >= 0 && oldblk->index <= nodehdr.count);
1086 271271 : ASSERT(newblk->blkno != 0);
1087 271271 : if (state->args->whichfork == XFS_DATA_FORK)
1088 75676 : 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 271271 : tmp = 0;
1095 271271 : if (oldblk->index < nodehdr.count) {
1096 83650 : tmp = (nodehdr.count - oldblk->index) * (uint)sizeof(*btree);
1097 167300 : memmove(&btree[oldblk->index + 1], &btree[oldblk->index], tmp);
1098 : }
1099 271271 : btree[oldblk->index].hashval = cpu_to_be32(newblk->hashval);
1100 271271 : btree[oldblk->index].before = cpu_to_be32(newblk->blkno);
1101 271271 : xfs_trans_log_buf(state->args->trans, oldblk->bp,
1102 271271 : XFS_DA_LOGRANGE(node, &btree[oldblk->index],
1103 : tmp + sizeof(*btree)));
1104 :
1105 271274 : nodehdr.count += 1;
1106 271274 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
1107 271271 : xfs_trans_log_buf(state->args->trans, oldblk->bp,
1108 271271 : 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 271274 : oldblk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
1115 271274 : }
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 4720960 : xfs_da3_join(
1127 : struct xfs_da_state *state)
1128 : {
1129 4720960 : struct xfs_da_state_blk *drop_blk;
1130 4720960 : struct xfs_da_state_blk *save_blk;
1131 4720960 : int action = 0;
1132 4720960 : int error;
1133 :
1134 4720960 : trace_xfs_da_join(state->args);
1135 :
1136 4720909 : drop_blk = &state->path.blk[ state->path.active-1 ];
1137 4720918 : save_blk = &state->altpath.blk[ state->path.active-1 ];
1138 4720920 : ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
1139 4720920 : 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 4783115 : for ( ; state->path.active >= 2; drop_blk--, save_blk--,
1147 62195 : 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 4732685 : switch (drop_blk->magic) {
1155 1904036 : case XFS_ATTR_LEAF_MAGIC:
1156 1904036 : error = xfs_attr3_leaf_toosmall(state, &action);
1157 1904024 : if (error)
1158 10 : return error;
1159 1904014 : if (action == 0)
1160 : return 0;
1161 2278 : xfs_attr3_leaf_unbalance(state, drop_blk, save_blk);
1162 2278 : break;
1163 2816884 : case XFS_DIR2_LEAFN_MAGIC:
1164 2816884 : error = xfs_dir2_leafn_toosmall(state, &action);
1165 2816927 : if (error)
1166 0 : return error;
1167 2816927 : if (action == 0)
1168 : return 0;
1169 59876 : xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
1170 59876 : break;
1171 11765 : case XFS_DA_NODE_MAGIC:
1172 : /*
1173 : * Remove the offending node, fixup hashvals,
1174 : * check for a toosmall neighbor.
1175 : */
1176 11765 : xfs_da3_node_remove(state, drop_blk);
1177 11765 : xfs_da3_fixhashpath(state, &state->path);
1178 11765 : error = xfs_da3_node_toosmall(state, &action);
1179 11765 : if (error)
1180 0 : return error;
1181 11765 : if (action == 0)
1182 : return 0;
1183 41 : xfs_da3_node_unbalance(state, drop_blk, save_blk);
1184 41 : break;
1185 : }
1186 62195 : xfs_da3_fixhashpath(state, &state->altpath);
1187 62195 : error = xfs_da3_blk_unlink(state, drop_blk, save_blk);
1188 62195 : xfs_da_state_kill_altpath(state);
1189 62195 : if (error)
1190 0 : return error;
1191 62195 : error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
1192 : drop_blk->bp);
1193 62195 : drop_blk->bp = NULL;
1194 62195 : 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 50430 : xfs_da3_node_remove(state, drop_blk);
1203 50430 : xfs_da3_fixhashpath(state, &state->path);
1204 50430 : error = xfs_da3_root_join(state, &state->path.blk[0]);
1205 50430 : return error;
1206 : }
1207 :
1208 : #ifdef DEBUG
1209 : static void
1210 7360 : xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
1211 : {
1212 7360 : __be16 magic = blkinfo->magic;
1213 :
1214 7360 : if (level == 1) {
1215 7350 : 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 10 : ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
1221 : magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
1222 : }
1223 7360 : ASSERT(!blkinfo->forw);
1224 7360 : ASSERT(!blkinfo->back);
1225 7360 : }
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 50430 : xfs_da3_root_join(
1236 : struct xfs_da_state *state,
1237 : struct xfs_da_state_blk *root_blk)
1238 : {
1239 50430 : struct xfs_da_intnode *oldroot;
1240 50430 : struct xfs_da_args *args;
1241 50430 : xfs_dablk_t child;
1242 50430 : struct xfs_buf *bp;
1243 50430 : struct xfs_da3_icnode_hdr oldroothdr;
1244 50430 : int error;
1245 50430 : struct xfs_inode *dp = state->args->dp;
1246 50430 : xfs_failaddr_t fa;
1247 :
1248 50430 : trace_xfs_da_root_join(state->args);
1249 :
1250 50430 : ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
1251 :
1252 50430 : args = state->args;
1253 50430 : oldroot = root_blk->bp->b_addr;
1254 50430 : xfs_da3_node_hdr_from_disk(dp->i_mount, &oldroothdr, oldroot);
1255 50430 : ASSERT(oldroothdr.forw == 0);
1256 50430 : ASSERT(oldroothdr.back == 0);
1257 :
1258 : /*
1259 : * If the root has more than one child, then don't do anything.
1260 : */
1261 50430 : 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 7360 : child = be32_to_cpu(oldroothdr.btree[0].before);
1269 7360 : ASSERT(child != 0);
1270 7360 : error = xfs_da3_node_read(args->trans, dp, child, &bp, args->whichfork);
1271 7360 : if (error)
1272 : return error;
1273 7360 : fa = xfs_da3_header_check(bp, args->owner);
1274 7360 : 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 7360 : 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 14720 : memcpy(root_blk->bp->b_addr, bp->b_addr, args->geo->blksize);
1290 7360 : root_blk->bp->b_ops = bp->b_ops;
1291 7360 : xfs_trans_buf_copy_type(root_blk->bp, bp);
1292 7360 : if (oldroothdr.magic == XFS_DA3_NODE_MAGIC) {
1293 7360 : struct xfs_da3_blkinfo *da3 = root_blk->bp->b_addr;
1294 7360 : da3->blkno = cpu_to_be64(xfs_buf_daddr(root_blk->bp));
1295 : }
1296 7360 : xfs_trans_log_buf(args->trans, root_blk->bp, 0,
1297 7360 : args->geo->blksize - 1);
1298 7360 : error = xfs_da_shrink_inode(args, child, bp);
1299 7360 : 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 11765 : xfs_da3_node_toosmall(
1313 : struct xfs_da_state *state,
1314 : int *action)
1315 : {
1316 11765 : struct xfs_da_intnode *node;
1317 11765 : struct xfs_da_state_blk *blk;
1318 11765 : struct xfs_da_blkinfo *info;
1319 11765 : xfs_dablk_t blkno;
1320 11765 : struct xfs_buf *bp;
1321 11765 : xfs_failaddr_t fa;
1322 11765 : struct xfs_da3_icnode_hdr nodehdr;
1323 11765 : int count;
1324 11765 : int forward;
1325 11765 : int error;
1326 11765 : int retval;
1327 11765 : int i;
1328 11765 : struct xfs_inode *dp = state->args->dp;
1329 :
1330 11765 : 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 11765 : blk = &state->path.blk[ state->path.active-1 ];
1338 11765 : info = blk->bp->b_addr;
1339 11765 : node = (xfs_da_intnode_t *)info;
1340 11765 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1341 11765 : if (nodehdr.count > (state->args->geo->node_ents >> 1)) {
1342 6524 : *action = 0; /* blk over 50%, don't try to join */
1343 6524 : 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 5241 : 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 5241 : count = state->args->geo->node_ents;
1379 5241 : count -= state->args->geo->node_ents >> 2;
1380 5241 : count -= nodehdr.count;
1381 :
1382 : /* start with smaller blk num */
1383 5241 : forward = nodehdr.forw < nodehdr.back;
1384 15682 : for (i = 0; i < 2; forward = !forward, i++) {
1385 10482 : struct xfs_da3_icnode_hdr thdr;
1386 10482 : if (forward)
1387 : blkno = nodehdr.forw;
1388 : else
1389 5241 : blkno = nodehdr.back;
1390 10482 : if (blkno == 0)
1391 3939 : continue;
1392 6543 : error = xfs_da3_node_read(state->args->trans, dp, blkno, &bp,
1393 6543 : state->args->whichfork);
1394 6543 : if (error)
1395 0 : return error;
1396 6543 : fa = xfs_da3_node_header_check(bp, state->args->owner);
1397 6543 : 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 6543 : node = bp->b_addr;
1405 6543 : xfs_da3_node_hdr_from_disk(dp->i_mount, &thdr, node);
1406 6543 : xfs_trans_brelse(state->args->trans, bp);
1407 :
1408 6543 : if (count - thdr.count >= 0)
1409 : break; /* fits with at least 25% to spare */
1410 : }
1411 5241 : if (i >= 2) {
1412 5200 : *action = 0;
1413 5200 : 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 82 : memcpy(&state->altpath, &state->path, sizeof(state->path));
1421 41 : if (blkno < blk->blkno) {
1422 11 : error = xfs_da3_path_shift(state, &state->altpath, forward,
1423 : 0, &retval);
1424 : } else {
1425 30 : error = xfs_da3_path_shift(state, &state->path, forward,
1426 : 0, &retval);
1427 : }
1428 41 : if (error)
1429 : return error;
1430 41 : if (retval) {
1431 0 : *action = 0;
1432 0 : return 0;
1433 : }
1434 41 : *action = 1;
1435 41 : return 0;
1436 : }
1437 :
1438 : /*
1439 : * Pick up the last hashvalue from an intermediate node.
1440 : */
1441 : STATIC uint
1442 333507 : xfs_da3_node_lasthash(
1443 : struct xfs_inode *dp,
1444 : struct xfs_buf *bp,
1445 : int *count)
1446 : {
1447 333507 : struct xfs_da3_icnode_hdr nodehdr;
1448 :
1449 333507 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, bp->b_addr);
1450 333506 : if (count)
1451 333506 : *count = nodehdr.count;
1452 333506 : if (!nodehdr.count)
1453 : return 0;
1454 333506 : 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 96438373 : xfs_da3_fixhashpath(
1463 : struct xfs_da_state *state,
1464 : struct xfs_da_state_path *path)
1465 : {
1466 96438373 : struct xfs_da_state_blk *blk;
1467 96438373 : struct xfs_da_intnode *node;
1468 96438373 : struct xfs_da_node_entry *btree;
1469 96438373 : xfs_dahash_t lasthash=0;
1470 96438373 : int level;
1471 96438373 : int count;
1472 96438373 : struct xfs_inode *dp = state->args->dp;
1473 :
1474 96438373 : trace_xfs_da_fixhashpath(state->args);
1475 :
1476 96215883 : level = path->active-1;
1477 96215883 : blk = &path->blk[ level ];
1478 96228383 : switch (blk->magic) {
1479 5491672 : case XFS_ATTR_LEAF_MAGIC:
1480 5491672 : lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
1481 5491850 : if (count == 0)
1482 22 : return;
1483 : break;
1484 90403204 : case XFS_DIR2_LEAFN_MAGIC:
1485 90403204 : lasthash = xfs_dir2_leaf_lasthash(dp, blk->bp, &count);
1486 90564166 : if (count == 0)
1487 : return;
1488 : break;
1489 333507 : case XFS_DA_NODE_MAGIC:
1490 333507 : lasthash = xfs_da3_node_lasthash(dp, blk->bp, &count);
1491 333506 : if (count == 0)
1492 : return;
1493 : break;
1494 : }
1495 100038948 : for (blk--, level--; level >= 0; blk--, level--) {
1496 96198065 : struct xfs_da3_icnode_hdr nodehdr;
1497 :
1498 96198065 : node = blk->bp->b_addr;
1499 96198065 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1500 96214551 : btree = nodehdr.btree;
1501 96214551 : if (be32_to_cpu(btree[blk->index].hashval) == lasthash)
1502 : break;
1503 3645225 : blk->hashval = lasthash;
1504 3645225 : btree[blk->index].hashval = cpu_to_be32(lasthash);
1505 3645225 : xfs_trans_log_buf(state->args->trans, blk->bp,
1506 3645225 : XFS_DA_LOGRANGE(node, &btree[blk->index],
1507 : sizeof(*btree)));
1508 :
1509 3649448 : 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 62195 : xfs_da3_node_remove(
1518 : struct xfs_da_state *state,
1519 : struct xfs_da_state_blk *drop_blk)
1520 : {
1521 62195 : struct xfs_da_intnode *node;
1522 62195 : struct xfs_da3_icnode_hdr nodehdr;
1523 62195 : struct xfs_da_node_entry *btree;
1524 62195 : int index;
1525 62195 : int tmp;
1526 62195 : struct xfs_inode *dp = state->args->dp;
1527 :
1528 62195 : trace_xfs_da_node_remove(state->args);
1529 :
1530 62195 : node = drop_blk->bp->b_addr;
1531 62195 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1532 62195 : ASSERT(drop_blk->index < nodehdr.count);
1533 62195 : ASSERT(drop_blk->index >= 0);
1534 :
1535 : /*
1536 : * Copy over the offending entry, or just zero it out.
1537 : */
1538 62195 : index = drop_blk->index;
1539 62195 : btree = nodehdr.btree;
1540 62195 : if (index < nodehdr.count - 1) {
1541 57113 : tmp = nodehdr.count - index - 1;
1542 57113 : tmp *= (uint)sizeof(xfs_da_node_entry_t);
1543 114226 : memmove(&btree[index], &btree[index + 1], tmp);
1544 57113 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1545 57113 : XFS_DA_LOGRANGE(node, &btree[index], tmp));
1546 57113 : index = nodehdr.count - 1;
1547 : }
1548 62195 : memset(&btree[index], 0, sizeof(xfs_da_node_entry_t));
1549 62195 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1550 62195 : XFS_DA_LOGRANGE(node, &btree[index], sizeof(btree[index])));
1551 62195 : nodehdr.count -= 1;
1552 62195 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
1553 62195 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1554 62195 : 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 62195 : drop_blk->hashval = be32_to_cpu(btree[index - 1].hashval);
1560 62195 : }
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 41 : 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 41 : struct xfs_da_intnode *drop_node;
1573 41 : struct xfs_da_intnode *save_node;
1574 41 : struct xfs_da_node_entry *drop_btree;
1575 41 : struct xfs_da_node_entry *save_btree;
1576 41 : struct xfs_da3_icnode_hdr drop_hdr;
1577 41 : struct xfs_da3_icnode_hdr save_hdr;
1578 41 : struct xfs_trans *tp;
1579 41 : int sindex;
1580 41 : int tmp;
1581 41 : struct xfs_inode *dp = state->args->dp;
1582 :
1583 41 : trace_xfs_da_node_unbalance(state->args);
1584 :
1585 41 : drop_node = drop_blk->bp->b_addr;
1586 41 : save_node = save_blk->bp->b_addr;
1587 41 : xfs_da3_node_hdr_from_disk(dp->i_mount, &drop_hdr, drop_node);
1588 41 : xfs_da3_node_hdr_from_disk(dp->i_mount, &save_hdr, save_node);
1589 41 : drop_btree = drop_hdr.btree;
1590 41 : save_btree = save_hdr.btree;
1591 41 : 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 41 : if ((be32_to_cpu(drop_btree[0].hashval) <
1598 41 : be32_to_cpu(save_btree[0].hashval)) ||
1599 21 : (be32_to_cpu(drop_btree[drop_hdr.count - 1].hashval) <
1600 21 : be32_to_cpu(save_btree[save_hdr.count - 1].hashval))) {
1601 : /* XXX: check this - is memmove dst correct? */
1602 20 : tmp = save_hdr.count * sizeof(xfs_da_node_entry_t);
1603 40 : memmove(&save_btree[drop_hdr.count], &save_btree[0], tmp);
1604 :
1605 20 : sindex = 0;
1606 20 : xfs_trans_log_buf(tp, save_blk->bp,
1607 20 : 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 21 : sindex = save_hdr.count;
1612 21 : xfs_trans_log_buf(tp, save_blk->bp,
1613 21 : 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 41 : tmp = drop_hdr.count * (uint)sizeof(xfs_da_node_entry_t);
1621 82 : memcpy(&save_btree[sindex], &drop_btree[0], tmp);
1622 41 : save_hdr.count += drop_hdr.count;
1623 :
1624 41 : xfs_da3_node_hdr_to_disk(dp->i_mount, save_node, &save_hdr);
1625 41 : xfs_trans_log_buf(tp, save_blk->bp,
1626 41 : 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 41 : save_blk->hashval = be32_to_cpu(save_btree[save_hdr.count - 1].hashval);
1633 41 : }
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 230024298 : xfs_da3_node_lookup_int(
1652 : struct xfs_da_state *state,
1653 : int *result)
1654 : {
1655 230024298 : struct xfs_da_state_blk *blk;
1656 230024298 : struct xfs_da_blkinfo *curr;
1657 230024298 : struct xfs_da_intnode *node;
1658 230024298 : struct xfs_da_node_entry *btree;
1659 230024298 : struct xfs_da3_icnode_hdr nodehdr;
1660 230024298 : struct xfs_da_args *args;
1661 230024298 : xfs_failaddr_t fa;
1662 230024298 : xfs_dablk_t blkno;
1663 230024298 : xfs_dahash_t hashval;
1664 230024298 : xfs_dahash_t btreehashval;
1665 230024298 : int probe;
1666 230024298 : int span;
1667 230024298 : int max;
1668 230024298 : int error;
1669 230024298 : int retval;
1670 230024298 : unsigned int expected_level = 0;
1671 230024298 : uint16_t magic;
1672 230024298 : struct xfs_inode *dp = state->args->dp;
1673 :
1674 230024298 : 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 230024298 : blkno = args->geo->leafblk;
1681 230024298 : for (blk = &state->path.blk[0], state->path.active = 1;
1682 481254867 : state->path.active <= XFS_DA_NODE_MAXDEPTH;
1683 251230569 : blk++, state->path.active++) {
1684 : /*
1685 : * Read the next node down in the tree.
1686 : */
1687 481254867 : blk->blkno = blkno;
1688 481254867 : error = xfs_da3_node_read(args->trans, args->dp, blkno,
1689 : &blk->bp, args->whichfork);
1690 482270274 : if (error) {
1691 1405 : blk->blkno = 0;
1692 1405 : state->path.active--;
1693 1405 : return error;
1694 : }
1695 482268869 : curr = blk->bp->b_addr;
1696 482268869 : magic = be16_to_cpu(curr->magic);
1697 :
1698 482268869 : if (magic == XFS_ATTR_LEAF_MAGIC ||
1699 482268869 : magic == XFS_ATTR3_LEAF_MAGIC) {
1700 13103061 : fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);
1701 13102748 : if (fa) {
1702 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
1703 0 : xfs_da_mark_sick(args);
1704 0 : return -EFSCORRUPTED;
1705 : }
1706 13102748 : blk->magic = XFS_ATTR_LEAF_MAGIC;
1707 13102748 : blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
1708 13102717 : break;
1709 : }
1710 :
1711 469165808 : if (magic == XFS_DIR2_LEAFN_MAGIC ||
1712 469165808 : magic == XFS_DIR3_LEAFN_MAGIC) {
1713 217120422 : fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);
1714 216633839 : if (fa) {
1715 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
1716 0 : xfs_da_mark_sick(args);
1717 0 : return -EFSCORRUPTED;
1718 : }
1719 216633839 : blk->magic = XFS_DIR2_LEAFN_MAGIC;
1720 216633839 : blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
1721 : blk->bp, NULL);
1722 216424147 : break;
1723 : }
1724 :
1725 252045386 : 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 252045386 : fa = xfs_da3_node_header_check(blk->bp, args->owner);
1732 251461155 : 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 251461155 : blk->magic = XFS_DA_NODE_MAGIC;
1739 :
1740 : /*
1741 : * Search an intermediate node for a match.
1742 : */
1743 251461155 : node = blk->bp->b_addr;
1744 251461155 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1745 251230569 : btree = nodehdr.btree;
1746 :
1747 : /* Tree taller than we can handle; bail out! */
1748 251230569 : 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 251230569 : if (blkno == args->geo->leafblk)
1756 228514592 : expected_level = nodehdr.level - 1;
1757 22715977 : 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 22715977 : expected_level--;
1763 :
1764 251230569 : max = nodehdr.count;
1765 251230569 : blk->hashval = be32_to_cpu(btree[max - 1].hashval);
1766 :
1767 : /*
1768 : * Binary search. (note: small blocks will skip loop)
1769 : */
1770 251230569 : probe = span = max / 2;
1771 251230569 : hashval = args->hashval;
1772 614943706 : while (span > 4) {
1773 364874257 : span /= 2;
1774 364874257 : btreehashval = be32_to_cpu(btree[probe].hashval);
1775 364874257 : if (btreehashval < hashval)
1776 181410398 : probe += span;
1777 183463859 : else if (btreehashval > hashval)
1778 182302739 : probe -= span;
1779 : else
1780 : break;
1781 : }
1782 251230569 : ASSERT((probe >= 0) && (probe < max));
1783 251230569 : 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 653213317 : while (probe > 0 &&
1791 548672153 : be32_to_cpu(btree[probe].hashval) >= hashval) {
1792 401982748 : probe--;
1793 : }
1794 551892129 : while (probe < max &&
1795 547121237 : be32_to_cpu(btree[probe].hashval) < hashval) {
1796 300661560 : probe++;
1797 : }
1798 :
1799 : /*
1800 : * Pick the right block to descend on.
1801 : */
1802 251230569 : if (probe == max) {
1803 5279430 : blk->index = max - 1;
1804 5279430 : blkno = be32_to_cpu(btree[max - 1].before);
1805 : } else {
1806 245951139 : blk->index = probe;
1807 245951139 : blkno = be32_to_cpu(btree[probe].before);
1808 : }
1809 :
1810 : /* We can't point back to the root. */
1811 251230569 : 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 229526864 : 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 1393105092 : for (;;) {
1829 811315978 : if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
1830 223852993 : retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
1831 : &blk->index, state);
1832 587462985 : } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1833 587462985 : retval = xfs_attr3_leaf_lookup_int(blk->bp, args);
1834 587500035 : blk->index = args->index;
1835 587500035 : args->blkno = blk->blkno;
1836 : } else {
1837 0 : ASSERT(0);
1838 0 : xfs_da_mark_sick(args);
1839 0 : return -EFSCORRUPTED;
1840 : }
1841 811254580 : if (((retval == -ENOENT) || (retval == -ENOATTR)) &&
1842 666285460 : (blk->hashval == args->hashval)) {
1843 583278896 : error = xfs_da3_path_shift(state, &state->path, 1, 1,
1844 : &retval);
1845 583125167 : if (error)
1846 0 : return error;
1847 583125167 : if (retval == 0) {
1848 581789114 : continue;
1849 1336053 : } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1850 : /* path_shift() gives ENOENT */
1851 378979 : retval = -ENOATTR;
1852 : }
1853 : }
1854 229311737 : break;
1855 : }
1856 229311737 : *result = retval;
1857 229311737 : return 0;
1858 : }
1859 :
1860 : /*========================================================================
1861 : * Utility routines.
1862 : *========================================================================*/
1863 :
1864 : /*
1865 : * Compare two intermediate nodes for "order".
1866 : */
1867 : STATIC int
1868 524 : xfs_da3_node_order(
1869 : struct xfs_inode *dp,
1870 : struct xfs_buf *node1_bp,
1871 : struct xfs_buf *node2_bp)
1872 : {
1873 524 : struct xfs_da_intnode *node1;
1874 524 : struct xfs_da_intnode *node2;
1875 524 : struct xfs_da_node_entry *btree1;
1876 524 : struct xfs_da_node_entry *btree2;
1877 524 : struct xfs_da3_icnode_hdr node1hdr;
1878 524 : struct xfs_da3_icnode_hdr node2hdr;
1879 :
1880 524 : node1 = node1_bp->b_addr;
1881 524 : node2 = node2_bp->b_addr;
1882 524 : xfs_da3_node_hdr_from_disk(dp->i_mount, &node1hdr, node1);
1883 524 : xfs_da3_node_hdr_from_disk(dp->i_mount, &node2hdr, node2);
1884 524 : btree1 = node1hdr.btree;
1885 524 : btree2 = node2hdr.btree;
1886 :
1887 524 : if (node1hdr.count > 0 && node2hdr.count > 0 &&
1888 524 : ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
1889 524 : (be32_to_cpu(btree2[node2hdr.count - 1].hashval) <
1890 524 : 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 281248 : 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 281248 : struct xfs_da_blkinfo *old_info;
1906 281248 : struct xfs_da_blkinfo *new_info;
1907 281248 : struct xfs_da_blkinfo *tmp_info;
1908 281248 : struct xfs_da_args *args;
1909 281248 : struct xfs_buf *bp;
1910 281248 : xfs_failaddr_t fa;
1911 281248 : int before = 0;
1912 281248 : int error;
1913 281248 : struct xfs_inode *dp = state->args->dp;
1914 :
1915 : /*
1916 : * Set up environment.
1917 : */
1918 281248 : args = state->args;
1919 281248 : ASSERT(args != NULL);
1920 281248 : old_info = old_blk->bp->b_addr;
1921 281248 : new_info = new_blk->bp->b_addr;
1922 281248 : 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 281248 : switch (old_blk->magic) {
1927 195152 : case XFS_ATTR_LEAF_MAGIC:
1928 195152 : before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
1929 195152 : break;
1930 85572 : case XFS_DIR2_LEAFN_MAGIC:
1931 85572 : before = xfs_dir2_leafn_order(dp, old_blk->bp, new_blk->bp);
1932 85572 : break;
1933 524 : case XFS_DA_NODE_MAGIC:
1934 524 : before = xfs_da3_node_order(dp, old_blk->bp, new_blk->bp);
1935 524 : break;
1936 : }
1937 :
1938 : /*
1939 : * Link blocks in appropriate order.
1940 : */
1941 281250 : 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 : 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 281250 : trace_xfs_da_link_after(args);
1974 281248 : new_info->forw = old_info->forw;
1975 281248 : new_info->back = cpu_to_be32(old_blk->blkno);
1976 281248 : if (old_info->forw) {
1977 83887 : error = xfs_da3_node_read(args->trans, dp,
1978 : be32_to_cpu(old_info->forw),
1979 : &bp, args->whichfork);
1980 83890 : if (error)
1981 : return error;
1982 83890 : fa = xfs_da3_header_check(bp, args->owner);
1983 83890 : 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 83890 : ASSERT(bp != NULL);
1990 83890 : tmp_info = bp->b_addr;
1991 83890 : ASSERT(tmp_info->magic == old_info->magic);
1992 83890 : ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
1993 83890 : tmp_info->back = cpu_to_be32(new_blk->blkno);
1994 83890 : xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1995 : }
1996 281250 : old_info->forw = cpu_to_be32(new_blk->blkno);
1997 : }
1998 :
1999 281250 : xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
2000 281251 : xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
2001 281251 : return 0;
2002 : }
2003 :
2004 : /*
2005 : * Unlink a block from a doubly linked list of blocks.
2006 : */
2007 : STATIC int /* error */
2008 62195 : 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 62195 : struct xfs_da_blkinfo *drop_info;
2014 62195 : struct xfs_da_blkinfo *save_info;
2015 62195 : struct xfs_da_blkinfo *tmp_info;
2016 62195 : struct xfs_da_args *args;
2017 62195 : struct xfs_buf *bp;
2018 62195 : xfs_failaddr_t fa;
2019 62195 : int error;
2020 :
2021 : /*
2022 : * Set up environment.
2023 : */
2024 62195 : args = state->args;
2025 62195 : ASSERT(args != NULL);
2026 62195 : save_info = save_blk->bp->b_addr;
2027 62195 : drop_info = drop_blk->bp->b_addr;
2028 62195 : 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 62195 : ASSERT(save_blk->magic == drop_blk->magic);
2032 62195 : ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
2033 : (be32_to_cpu(save_info->back) == drop_blk->blkno));
2034 62195 : 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 62195 : if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
2041 19474 : trace_xfs_da_unlink_back(args);
2042 19474 : save_info->back = drop_info->back;
2043 19474 : if (drop_info->back) {
2044 12046 : error = xfs_da3_node_read(args->trans, args->dp,
2045 : be32_to_cpu(drop_info->back),
2046 : &bp, args->whichfork);
2047 12046 : if (error)
2048 : return error;
2049 12046 : fa = xfs_da3_header_check(bp, args->owner);
2050 12046 : 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 12046 : ASSERT(bp != NULL);
2057 12046 : tmp_info = bp->b_addr;
2058 12046 : ASSERT(tmp_info->magic == save_info->magic);
2059 12046 : ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
2060 12046 : tmp_info->forw = cpu_to_be32(save_blk->blkno);
2061 12046 : xfs_trans_log_buf(args->trans, bp, 0,
2062 : sizeof(*tmp_info) - 1);
2063 : }
2064 : } else {
2065 42721 : trace_xfs_da_unlink_forward(args);
2066 42721 : save_info->forw = drop_info->forw;
2067 42721 : if (drop_info->forw) {
2068 37671 : error = xfs_da3_node_read(args->trans, args->dp,
2069 : be32_to_cpu(drop_info->forw),
2070 : &bp, args->whichfork);
2071 37671 : if (error)
2072 : return error;
2073 37671 : fa = xfs_da3_header_check(bp, args->owner);
2074 37671 : 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 37671 : ASSERT(bp != NULL);
2081 37671 : tmp_info = bp->b_addr;
2082 37671 : ASSERT(tmp_info->magic == save_info->magic);
2083 37671 : ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
2084 37671 : tmp_info->back = cpu_to_be32(save_blk->blkno);
2085 37671 : xfs_trans_log_buf(args->trans, bp, 0,
2086 : sizeof(*tmp_info) - 1);
2087 : }
2088 : }
2089 :
2090 62195 : xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
2091 62195 : 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 584131116 : 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 584131116 : struct xfs_da_state_blk *blk;
2111 584131116 : struct xfs_da_blkinfo *info;
2112 584131116 : struct xfs_da_args *args;
2113 584131116 : struct xfs_da_node_entry *btree;
2114 584131116 : struct xfs_da3_icnode_hdr nodehdr;
2115 584131116 : struct xfs_buf *bp;
2116 584131116 : xfs_failaddr_t fa;
2117 584131116 : xfs_dablk_t blkno = 0;
2118 584131116 : int level;
2119 584131116 : int error;
2120 584131116 : struct xfs_inode *dp = state->args->dp;
2121 :
2122 584131116 : 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 584135428 : args = state->args;
2130 584135428 : ASSERT(args != NULL);
2131 584135428 : ASSERT(path != NULL);
2132 584135428 : ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
2133 584135428 : level = (path->active-1) - 1; /* skip bottom layer in path */
2134 587350447 : for (; level >= 0; level--) {
2135 585881682 : blk = &path->blk[level];
2136 585881673 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
2137 585881673 : blk->bp->b_addr);
2138 :
2139 585885098 : if (forward && (blk->index < nodehdr.count - 1)) {
2140 582234841 : blk->index++;
2141 582234841 : blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
2142 582234841 : break;
2143 3650257 : } else if (!forward && (blk->index > 0)) {
2144 435238 : blk->index--;
2145 435238 : blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
2146 435238 : break;
2147 : }
2148 : }
2149 584138844 : if (level < 0) {
2150 1468516 : *result = -ENOENT; /* we're out of our tree */
2151 1468516 : ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
2152 1468516 : 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 1166841716 : for (blk++, level++; level < path->active; blk++, level++) {
2160 : /*
2161 : * Read the next child block into a local buffer.
2162 : */
2163 584173928 : error = xfs_da3_node_read(args->trans, dp, blkno, &bp,
2164 : args->whichfork);
2165 584145454 : 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 584145454 : if (release)
2175 583267836 : xfs_trans_brelse(args->trans, blk->bp);
2176 584154075 : blk->blkno = blkno;
2177 584154075 : blk->bp = bp;
2178 :
2179 584154075 : info = blk->bp->b_addr;
2180 584154075 : 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 584154075 : switch (be16_to_cpu(info->magic)) {
2193 1500654 : case XFS_DA_NODE_MAGIC:
2194 : case XFS_DA3_NODE_MAGIC:
2195 1500654 : fa = xfs_da3_node_header_check(blk->bp, args->owner);
2196 1500654 : if (fa) {
2197 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2198 0 : xfs_da_mark_sick(args);
2199 0 : return -EFSCORRUPTED;
2200 : }
2201 1500654 : blk->magic = XFS_DA_NODE_MAGIC;
2202 1500654 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
2203 1500654 : bp->b_addr);
2204 1500654 : btree = nodehdr.btree;
2205 1500654 : blk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
2206 1500654 : if (forward)
2207 1499823 : blk->index = 0;
2208 : else
2209 831 : blk->index = nodehdr.count - 1;
2210 1500654 : blkno = be32_to_cpu(btree[blk->index].before);
2211 1500654 : break;
2212 574806372 : case XFS_ATTR_LEAF_MAGIC:
2213 : case XFS_ATTR3_LEAF_MAGIC:
2214 574806372 : fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);
2215 574806869 : if (fa) {
2216 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2217 0 : xfs_da_mark_sick(args);
2218 0 : return -EFSCORRUPTED;
2219 : }
2220 574806869 : blk->magic = XFS_ATTR_LEAF_MAGIC;
2221 574806869 : ASSERT(level == path->active-1);
2222 574806869 : blk->index = 0;
2223 574806869 : blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
2224 574823682 : break;
2225 7847049 : case XFS_DIR2_LEAFN_MAGIC:
2226 : case XFS_DIR3_LEAFN_MAGIC:
2227 7847049 : fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);
2228 7847045 : if (fa) {
2229 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2230 0 : xfs_da_mark_sick(args);
2231 0 : return -EFSCORRUPTED;
2232 : }
2233 7847045 : blk->magic = XFS_DIR2_LEAFN_MAGIC;
2234 7847045 : ASSERT(level == path->active-1);
2235 7847045 : blk->index = 0;
2236 7847045 : blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
2237 : blk->bp, NULL);
2238 7847052 : break;
2239 0 : default:
2240 0 : ASSERT(0);
2241 0 : break;
2242 : }
2243 : }
2244 582667788 : *result = 0;
2245 582667788 : 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 5328359573 : xfs_da_hashname(const uint8_t *name, int namelen)
2260 : {
2261 5328359573 : xfs_dahash_t hash;
2262 :
2263 : /*
2264 : * Do four characters at a time as long as we can.
2265 : */
2266 12935049949 : for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
2267 7606690376 : hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
2268 7606690376 : (name[3] << 0) ^ rol32(hash, 7 * 4);
2269 :
2270 : /*
2271 : * Now do the rest of the characters.
2272 : */
2273 5328359573 : switch (namelen) {
2274 1261752324 : case 3:
2275 1261752324 : return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
2276 : rol32(hash, 7 * 3);
2277 1386314830 : case 2:
2278 1386314830 : return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
2279 1239427391 : case 1:
2280 1239427391 : return (name[0] << 0) ^ rol32(hash, 7 * 1);
2281 : default: /* case 0: */
2282 : return hash;
2283 : }
2284 : }
2285 :
2286 : enum xfs_dacmp
2287 1912548020 : xfs_da_compname(
2288 : struct xfs_da_args *args,
2289 : const unsigned char *name,
2290 : int len)
2291 : {
2292 1733267137 : return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
2293 3645815157 : XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
2294 : }
2295 :
2296 : int
2297 9497651 : xfs_da_grow_inode_int(
2298 : struct xfs_da_args *args,
2299 : xfs_fileoff_t *bno,
2300 : int count)
2301 : {
2302 9497651 : struct xfs_trans *tp = args->trans;
2303 9497651 : struct xfs_inode *dp = args->dp;
2304 9497651 : int w = args->whichfork;
2305 9497651 : xfs_rfsblock_t nblks = dp->i_nblocks;
2306 9497651 : struct xfs_bmbt_irec map, *mapp;
2307 9497651 : int nmap, error, got, i, mapi;
2308 :
2309 : /*
2310 : * Find a spot in the file space to put the new block.
2311 : */
2312 9497651 : error = xfs_bmap_first_unused(tp, dp, count, bno, w);
2313 9496515 : if (error)
2314 : return error;
2315 :
2316 : /*
2317 : * Try mapping it in one filesystem block.
2318 : */
2319 9496515 : nmap = 1;
2320 9496515 : error = xfs_bmapi_write(tp, dp, *bno, count,
2321 9496515 : xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
2322 : args->total, &map, &nmap);
2323 9490009 : if (error)
2324 : return error;
2325 :
2326 9490006 : ASSERT(nmap <= 1);
2327 9490006 : if (nmap == 1) {
2328 : mapp = ↦
2329 : mapi = 1;
2330 161 : } else if (nmap == 0 && count > 1) {
2331 160 : xfs_fileoff_t b;
2332 160 : 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 160 : mapp = kmem_alloc(sizeof(*mapp) * count, 0);
2339 320 : for (b = *bno, mapi = 0; b < *bno + count; ) {
2340 160 : c = (int)(*bno + count - b);
2341 160 : nmap = min(XFS_BMAP_MAX_NMAP, c);
2342 320 : error = xfs_bmapi_write(tp, dp, b, c,
2343 160 : xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
2344 160 : args->total, &mapp[mapi], &nmap);
2345 160 : if (error)
2346 0 : goto out_free_map;
2347 160 : if (nmap < 1)
2348 : break;
2349 160 : mapi += nmap;
2350 160 : b = mapp[mapi - 1].br_startoff +
2351 160 : 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 18979150 : for (i = 0, got = 0; i < mapi; i++)
2362 9489144 : got += mapp[i].br_blockcount;
2363 9490006 : if (got != count || mapp[0].br_startoff != *bno ||
2364 9487150 : mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
2365 9487150 : *bno + count) {
2366 138 : error = -ENOSPC;
2367 138 : goto out_free_map;
2368 : }
2369 :
2370 : /* account for newly allocated blocks in reserved blocks total */
2371 9490407 : args->total -= dp->i_nblocks - nblks;
2372 :
2373 9490006 : out_free_map:
2374 9490006 : if (mapp != &map)
2375 161 : 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 8632987 : xfs_da_grow_inode(
2385 : struct xfs_da_args *args,
2386 : xfs_dablk_t *new_blkno)
2387 : {
2388 8632987 : xfs_fileoff_t bno;
2389 8632987 : int error;
2390 :
2391 8632987 : trace_xfs_da_grow_inode(args);
2392 :
2393 8632198 : bno = args->geo->leafblk;
2394 8632198 : error = xfs_da_grow_inode_int(args, &bno, args->geo->fsbcount);
2395 8625714 : if (!error)
2396 8625688 : *new_blkno = (xfs_dablk_t)bno;
2397 8625714 : 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 4400550 : xfs_da_shrink_inode(
2665 : struct xfs_da_args *args,
2666 : xfs_dablk_t dead_blkno,
2667 : struct xfs_buf *dead_buf)
2668 : {
2669 4400550 : struct xfs_inode *dp;
2670 4400550 : int done, error, w, count;
2671 4400550 : struct xfs_trans *tp;
2672 :
2673 4400550 : trace_xfs_da_shrink_inode(args);
2674 :
2675 4400330 : dp = args->dp;
2676 4400330 : w = args->whichfork;
2677 4400330 : tp = args->trans;
2678 4400330 : count = args->geo->fsbcount;
2679 4400334 : 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 4490423 : error = xfs_bunmapi(tp, dp, dead_blkno, count,
2685 : xfs_bmapi_aflag(w), 0, &done);
2686 4400027 : 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 5 : if (error)
2692 : break;
2693 : } else {
2694 : break;
2695 : }
2696 : }
2697 4400027 : xfs_trans_binval(tp, dead_buf);
2698 4400569 : return error;
2699 : }
2700 :
2701 : static int
2702 3738777157 : 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 3738777157 : struct xfs_mount *mp = dp->i_mount;
2711 3738777157 : int nfsb = xfs_dabuf_nfsb(mp, whichfork);
2712 3738777157 : struct xfs_bmbt_irec irec, *irecs = &irec;
2713 3738777157 : struct xfs_buf_map *map = *mapp;
2714 3738777157 : xfs_fileoff_t off = bno;
2715 3738777157 : int error = 0, nirecs, i;
2716 :
2717 3738777157 : if (nfsb > 1)
2718 220041437 : irecs = kmem_zalloc(sizeof(irec) * nfsb, KM_NOFS);
2719 :
2720 3735403647 : nirecs = nfsb;
2721 5515244652 : error = xfs_bmapi_read(dp, bno, nfsb, irecs, &nirecs,
2722 : xfs_bmapi_aflag(whichfork));
2723 3739044482 : if (error)
2724 212 : 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 3739044270 : if (nirecs > 1) {
2731 248741 : map = kmem_zalloc(nirecs * sizeof(struct xfs_buf_map), KM_NOFS);
2732 248741 : if (!map) {
2733 0 : error = -ENOMEM;
2734 0 : goto out_free_irecs;
2735 : }
2736 248741 : *mapp = map;
2737 : }
2738 :
2739 7475066911 : for (i = 0; i < nirecs; i++) {
2740 3739096361 : if (irecs[i].br_startblock == HOLESTARTBLOCK ||
2741 : irecs[i].br_startblock == DELAYSTARTBLOCK)
2742 282210 : goto invalid_mapping;
2743 3738814151 : if (off != irecs[i].br_startoff)
2744 0 : goto invalid_mapping;
2745 :
2746 3738814151 : map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);
2747 3736022641 : map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);
2748 3736022641 : off += irecs[i].br_blockcount;
2749 : }
2750 :
2751 3735970550 : if (off != bno + nfsb)
2752 0 : goto invalid_mapping;
2753 :
2754 3735970550 : *nmaps = nirecs;
2755 3736252972 : out_free_irecs:
2756 3736252972 : if (irecs != &irec)
2757 220052645 : kmem_free(irecs);
2758 3736290781 : return error;
2759 :
2760 282210 : invalid_mapping:
2761 : /* Caller ok with no mapping. */
2762 282210 : 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 282210 : *nmaps = 0;
2780 : }
2781 282210 : goto out_free_irecs;
2782 : }
2783 :
2784 : /*
2785 : * Get a buffer for the dir/attr block.
2786 : */
2787 : int
2788 9571492 : 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 9571492 : struct xfs_mount *mp = dp->i_mount;
2796 9571492 : struct xfs_buf *bp;
2797 9571492 : struct xfs_buf_map map, *mapp = ↦
2798 9571492 : int nmap = 1;
2799 9571492 : int error;
2800 :
2801 9571492 : *bpp = NULL;
2802 9571492 : error = xfs_dabuf_map(dp, bno, 0, whichfork, &mapp, &nmap);
2803 9574903 : if (error || nmap == 0)
2804 0 : goto out_free;
2805 :
2806 9574903 : error = xfs_trans_get_buf_map(tp, mp->m_ddev_targp, mapp, nmap, 0, &bp);
2807 9577526 : if (error)
2808 0 : goto out_free;
2809 :
2810 9577526 : *bpp = bp;
2811 :
2812 9577526 : out_free:
2813 9577526 : if (mapp != &map)
2814 166 : kmem_free(mapp);
2815 :
2816 9577526 : return error;
2817 : }
2818 :
2819 : /*
2820 : * Get a buffer for the dir/attr block, fill in the contents.
2821 : */
2822 : int
2823 3535171596 : 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 3535171596 : struct xfs_mount *mp = dp->i_mount;
2833 3535171596 : struct xfs_buf *bp;
2834 3535171596 : struct xfs_buf_map map, *mapp = ↦
2835 3535171596 : int nmap = 1;
2836 3535171596 : int error;
2837 :
2838 3535171596 : *bpp = NULL;
2839 3535171596 : error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
2840 3532794532 : if (error || !nmap)
2841 282420 : goto out_free;
2842 :
2843 3532512112 : error = xfs_trans_read_buf_map(mp, tp, mp->m_ddev_targp, mapp, nmap, 0,
2844 : &bp, ops);
2845 3533517363 : if (xfs_metadata_is_sick(error))
2846 238 : xfs_dirattr_mark_sick(dp, whichfork);
2847 3533517363 : if (error)
2848 2987 : goto out_free;
2849 :
2850 3533514376 : if (whichfork == XFS_ATTR_FORK)
2851 1947541192 : xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
2852 : else
2853 1585973184 : xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
2854 3532986734 : *bpp = bp;
2855 3533272141 : out_free:
2856 3533272141 : if (mapp != &map)
2857 248458 : kmem_free(mapp);
2858 :
2859 3533272141 : return error;
2860 : }
2861 :
2862 : /*
2863 : * Readahead the dir/attr block.
2864 : */
2865 : int
2866 193039014 : 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 193039014 : struct xfs_buf_map map;
2874 193039014 : struct xfs_buf_map *mapp;
2875 193039014 : int nmap;
2876 193039014 : int error;
2877 :
2878 193039014 : mapp = ↦
2879 193039014 : nmap = 1;
2880 193039014 : error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
2881 193093011 : if (error || !nmap)
2882 2 : goto out_free;
2883 :
2884 193093009 : xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap, ops);
2885 :
2886 193104639 : out_free:
2887 193104639 : if (mapp != &map)
2888 117 : kmem_free(mapp);
2889 :
2890 193104639 : return error;
2891 : }
|
