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 151759467 : xfs_da_state_alloc(
85 : struct xfs_da_args *args)
86 : {
87 151759467 : struct xfs_da_state *state;
88 :
89 151759467 : state = kmem_cache_zalloc(xfs_da_state_cache, GFP_NOFS | __GFP_NOFAIL);
90 151743173 : state->args = args;
91 151743173 : state->mp = args->dp->i_mount;
92 151743173 : return state;
93 : }
94 :
95 : /*
96 : * Kill the altpath contents of a da-state structure.
97 : */
98 : STATIC void
99 151802927 : xfs_da_state_kill_altpath(xfs_da_state_t *state)
100 : {
101 151802927 : int i;
102 :
103 151849431 : for (i = 0; i < state->altpath.active; i++)
104 46504 : state->altpath.blk[i].bp = NULL;
105 151802927 : state->altpath.active = 0;
106 151802927 : }
107 :
108 : /*
109 : * Free a da-state structure.
110 : */
111 : void
112 151773452 : xfs_da_state_free(xfs_da_state_t *state)
113 : {
114 151773452 : xfs_da_state_kill_altpath(state);
115 : #ifdef DEBUG
116 151775030 : memset((char *)state, 0, sizeof(*state));
117 : #endif /* DEBUG */
118 151775030 : kmem_cache_free(xfs_da_state_cache, state);
119 151773674 : }
120 :
121 : void
122 12145 : xfs_da_state_reset(
123 : struct xfs_da_state *state,
124 : struct xfs_da_args *args)
125 : {
126 12145 : xfs_da_state_kill_altpath(state);
127 12145 : memset(state, 0, sizeof(struct xfs_da_state));
128 12145 : state->args = args;
129 12145 : state->mp = state->args->dp->i_mount;
130 12145 : }
131 :
132 : static inline int xfs_dabuf_nfsb(struct xfs_mount *mp, int whichfork)
133 : {
134 1848606913 : if (whichfork == XFS_DATA_FORK)
135 898409380 : return mp->m_dir_geo->fsbcount;
136 950197533 : return mp->m_attr_geo->fsbcount;
137 : }
138 :
139 : void
140 585667997 : 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 585667997 : if (xfs_has_crc(mp)) {
146 585667997 : struct xfs_da3_intnode *from3 = (struct xfs_da3_intnode *)from;
147 :
148 585667997 : to->forw = be32_to_cpu(from3->hdr.info.hdr.forw);
149 585667997 : to->back = be32_to_cpu(from3->hdr.info.hdr.back);
150 585667997 : to->magic = be16_to_cpu(from3->hdr.info.hdr.magic);
151 585667997 : to->count = be16_to_cpu(from3->hdr.__count);
152 585667997 : to->level = be16_to_cpu(from3->hdr.__level);
153 585667997 : to->btree = from3->__btree;
154 585667997 : 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 585667997 : }
165 :
166 : void
167 190399 : 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 190399 : if (xfs_has_crc(mp)) {
173 190399 : struct xfs_da3_intnode *to3 = (struct xfs_da3_intnode *)to;
174 :
175 190399 : ASSERT(from->magic == XFS_DA3_NODE_MAGIC);
176 190399 : to3->hdr.info.hdr.forw = cpu_to_be32(from->forw);
177 190399 : to3->hdr.info.hdr.back = cpu_to_be32(from->back);
178 190399 : to3->hdr.info.hdr.magic = cpu_to_be16(from->magic);
179 190399 : to3->hdr.__count = cpu_to_be16(from->count);
180 380798 : 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 190399 : }
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 25286175 : xfs_da3_blkinfo_verify(
198 : struct xfs_buf *bp,
199 : struct xfs_da3_blkinfo *hdr3)
200 : {
201 25286175 : struct xfs_mount *mp = bp->b_mount;
202 25286175 : struct xfs_da_blkinfo *hdr = &hdr3->hdr;
203 :
204 25286175 : if (!xfs_verify_magic16(bp, hdr->magic))
205 0 : return __this_address;
206 :
207 25286183 : if (xfs_has_crc(mp)) {
208 25286183 : if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))
209 0 : return __this_address;
210 25286202 : if (be64_to_cpu(hdr3->blkno) != xfs_buf_daddr(bp))
211 0 : return __this_address;
212 25286209 : 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 150406 : xfs_da3_node_verify(
221 : struct xfs_buf *bp)
222 : {
223 150406 : struct xfs_mount *mp = bp->b_mount;
224 150406 : struct xfs_da_intnode *hdr = bp->b_addr;
225 150406 : struct xfs_da3_icnode_hdr ichdr;
226 150406 : xfs_failaddr_t fa;
227 :
228 150406 : xfs_da3_node_hdr_from_disk(mp, &ichdr, hdr);
229 :
230 150406 : fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);
231 150406 : if (fa)
232 : return fa;
233 :
234 150406 : if (ichdr.level == 0)
235 0 : return __this_address;
236 150406 : if (ichdr.level > XFS_DA_NODE_MAXDEPTH)
237 0 : return __this_address;
238 150406 : 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 150406 : 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 154318283 : xfs_da3_node_header_check(
256 : struct xfs_buf *bp,
257 : xfs_ino_t owner)
258 : {
259 154318283 : struct xfs_mount *mp = bp->b_mount;
260 :
261 154318283 : if (xfs_has_crc(mp)) {
262 154318283 : struct xfs_da3_blkinfo *hdr3 = bp->b_addr;
263 :
264 154318283 : ASSERT(hdr3->hdr.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
265 :
266 154318283 : if (be64_to_cpu(hdr3->owner) != owner)
267 54 : return __this_address;
268 : }
269 :
270 : return NULL;
271 : }
272 :
273 : xfs_failaddr_t
274 1599203 : xfs_da3_header_check(
275 : struct xfs_buf *bp,
276 : xfs_ino_t owner)
277 : {
278 1599203 : struct xfs_mount *mp = bp->b_mount;
279 1599203 : struct xfs_da_blkinfo *hdr = bp->b_addr;
280 :
281 1599203 : if (!xfs_has_crc(mp))
282 : return NULL;
283 :
284 1599203 : switch (hdr->magic) {
285 1325108 : case cpu_to_be16(XFS_ATTR3_LEAF_MAGIC):
286 1325108 : return xfs_attr3_leaf_header_check(bp, owner);
287 38850 : case cpu_to_be16(XFS_DA3_NODE_MAGIC):
288 38850 : return xfs_da3_node_header_check(bp, owner);
289 235245 : case cpu_to_be16(XFS_DIR3_LEAF1_MAGIC):
290 : case cpu_to_be16(XFS_DIR3_LEAFN_MAGIC):
291 235245 : return xfs_dir3_leaf_header_check(bp, owner);
292 : }
293 :
294 0 : ASSERT(0);
295 0 : return NULL;
296 : }
297 :
298 : static void
299 79540 : xfs_da3_node_write_verify(
300 : struct xfs_buf *bp)
301 : {
302 79540 : struct xfs_mount *mp = bp->b_mount;
303 79540 : struct xfs_buf_log_item *bip = bp->b_log_item;
304 79540 : struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
305 79540 : xfs_failaddr_t fa;
306 :
307 79540 : fa = xfs_da3_node_verify(bp);
308 79540 : if (fa) {
309 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
310 0 : return;
311 : }
312 :
313 79540 : if (!xfs_has_crc(mp))
314 : return;
315 :
316 79540 : if (bip)
317 79540 : hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
318 :
319 79540 : 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 128107 : xfs_da3_node_read_verify(
330 : struct xfs_buf *bp)
331 : {
332 128107 : struct xfs_da_blkinfo *info = bp->b_addr;
333 128107 : xfs_failaddr_t fa;
334 :
335 128107 : switch (be16_to_cpu(info->magic)) {
336 : case XFS_DA3_NODE_MAGIC:
337 31989 : if (!xfs_buf_verify_cksum(bp, XFS_DA3_NODE_CRC_OFF)) {
338 16 : xfs_verifier_error(bp, -EFSBADCRC,
339 8 : __this_address);
340 8 : break;
341 : }
342 31981 : fallthrough;
343 : case XFS_DA_NODE_MAGIC:
344 31981 : fa = xfs_da3_node_verify(bp);
345 31981 : if (fa)
346 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
347 : return;
348 28004 : case XFS_ATTR_LEAF_MAGIC:
349 : case XFS_ATTR3_LEAF_MAGIC:
350 28004 : bp->b_ops = &xfs_attr3_leaf_buf_ops;
351 28004 : bp->b_ops->verify_read(bp);
352 28004 : return;
353 68112 : case XFS_DIR2_LEAFN_MAGIC:
354 : case XFS_DIR3_LEAFN_MAGIC:
355 68112 : bp->b_ops = &xfs_dir3_leafn_buf_ops;
356 68112 : bp->b_ops->verify_read(bp);
357 68112 : return;
358 : default:
359 2 : xfs_verifier_error(bp, -EFSCORRUPTED, __this_address);
360 2 : break;
361 : }
362 : }
363 :
364 : /* Verify the structure of a da3 block. */
365 : static xfs_failaddr_t
366 38885 : xfs_da3_node_verify_struct(
367 : struct xfs_buf *bp)
368 : {
369 38885 : struct xfs_da_blkinfo *info = bp->b_addr;
370 :
371 38885 : switch (be16_to_cpu(info->magic)) {
372 38885 : case XFS_DA3_NODE_MAGIC:
373 : case XFS_DA_NODE_MAGIC:
374 38885 : 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 584965064 : 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 584965064 : struct xfs_da_blkinfo *info = bp->b_addr;
405 :
406 584965064 : switch (be16_to_cpu(info->magic)) {
407 141617752 : case XFS_DA_NODE_MAGIC:
408 : case XFS_DA3_NODE_MAGIC:
409 141617752 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
410 141617752 : return 0;
411 309212239 : case XFS_ATTR_LEAF_MAGIC:
412 : case XFS_ATTR3_LEAF_MAGIC:
413 309212239 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_ATTR_LEAF_BUF);
414 309212239 : return 0;
415 134135073 : case XFS_DIR2_LEAFN_MAGIC:
416 : case XFS_DIR3_LEAFN_MAGIC:
417 134135073 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
418 134135073 : 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 610112787 : 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 610112787 : int error;
437 :
438 610112787 : error = xfs_da_read_buf(tp, dp, bno, 0, bpp, whichfork,
439 : &xfs_da3_node_buf_ops);
440 610223031 : if (error || !*bpp || !tp)
441 : return error;
442 584917518 : return xfs_da3_node_set_type(tp, dp, whichfork, *bpp);
443 : }
444 :
445 : int
446 22628 : 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 22628 : struct xfs_mount *mp = dp->i_mount;
454 22628 : int error;
455 :
456 22628 : error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, mappedbno,
457 22628 : XFS_FSB_TO_BB(mp, xfs_dabuf_nfsb(mp, whichfork)), 0,
458 : bpp, &xfs_da3_node_buf_ops);
459 22628 : if (xfs_metadata_is_sick(error))
460 0 : xfs_dirattr_mark_sick(dp, whichfork);
461 22628 : if (error || !*bpp)
462 : return error;
463 :
464 22628 : if (whichfork == XFS_ATTR_FORK)
465 22628 : xfs_buf_set_ref(*bpp, XFS_ATTR_BTREE_REF);
466 : else
467 0 : xfs_buf_set_ref(*bpp, XFS_DIR_BTREE_REF);
468 :
469 22628 : if (!tp)
470 : return 0;
471 22628 : 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 39992 : 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 39992 : struct xfs_da_intnode *node;
490 39992 : struct xfs_trans *tp = args->trans;
491 39992 : struct xfs_mount *mp = tp->t_mountp;
492 39992 : struct xfs_da3_icnode_hdr ichdr = {0};
493 39992 : struct xfs_buf *bp;
494 39992 : int error;
495 39992 : struct xfs_inode *dp = args->dp;
496 :
497 39992 : trace_xfs_da_node_create(args);
498 39992 : ASSERT(level <= XFS_DA_NODE_MAXDEPTH);
499 :
500 39992 : error = xfs_da_get_buf(tp, dp, blkno, &bp, whichfork);
501 39992 : if (error)
502 : return error;
503 39992 : bp->b_ops = &xfs_da3_node_buf_ops;
504 39992 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
505 39992 : node = bp->b_addr;
506 :
507 39992 : if (xfs_has_crc(mp)) {
508 39992 : struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
509 :
510 39992 : memset(hdr3, 0, sizeof(struct xfs_da3_node_hdr));
511 39992 : ichdr.magic = XFS_DA3_NODE_MAGIC;
512 39992 : hdr3->info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
513 39992 : hdr3->info.owner = cpu_to_be64(args->owner);
514 39992 : uuid_copy(&hdr3->info.uuid, &mp->m_sb.sb_meta_uuid);
515 : } else {
516 0 : ichdr.magic = XFS_DA_NODE_MAGIC;
517 : }
518 39992 : ichdr.level = level;
519 :
520 39992 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &ichdr);
521 39992 : xfs_trans_log_buf(tp, bp,
522 39992 : XFS_DA_LOGRANGE(node, &node->hdr, args->geo->node_hdr_size));
523 :
524 39992 : *bpp = bp;
525 39992 : return 0;
526 : }
527 :
528 : /*
529 : * Split a leaf node, rebalance, then possibly split
530 : * intermediate nodes, rebalance, etc.
531 : */
532 : int /* error */
533 89182 : xfs_da3_split(
534 : struct xfs_da_state *state)
535 : {
536 89182 : struct xfs_da_state_blk *oldblk;
537 89182 : struct xfs_da_state_blk *newblk;
538 89182 : struct xfs_da_state_blk *addblk;
539 89182 : struct xfs_da_intnode *node;
540 89182 : int max;
541 89182 : int action = 0;
542 89182 : int error;
543 89182 : int i;
544 :
545 89182 : trace_xfs_da_split(state->args);
546 :
547 89182 : 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 89180 : max = state->path.active - 1;
557 89180 : ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
558 89180 : ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
559 : state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
560 :
561 89180 : addblk = &state->path.blk[max]; /* initial dummy value */
562 266028 : for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
563 176850 : oldblk = &state->path.blk[i];
564 176850 : 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 176850 : switch (oldblk->magic) {
573 60323 : case XFS_ATTR_LEAF_MAGIC:
574 60323 : error = xfs_attr3_leaf_split(state, oldblk, newblk);
575 60322 : if ((error != 0) && (error != -ENOSPC)) {
576 0 : return error; /* GROT: attr is inconsistent */
577 : }
578 60322 : 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 28856 : case XFS_DIR2_LEAFN_MAGIC:
604 28856 : error = xfs_dir2_leafn_split(state, oldblk, newblk);
605 28857 : if (error)
606 0 : return error;
607 : addblk = newblk;
608 : break;
609 87671 : case XFS_DA_NODE_MAGIC:
610 87671 : error = xfs_da3_node_split(state, oldblk, newblk, addblk,
611 : max - i, &action);
612 87670 : addblk->bp = NULL;
613 87670 : if (error)
614 0 : return error; /* GROT: dir is inconsistent */
615 : /*
616 : * Record the newly split block for the next time thru?
617 : */
618 87670 : if (action)
619 : addblk = newblk;
620 : else
621 87609 : addblk = NULL;
622 : break;
623 : }
624 :
625 : /*
626 : * Update the btree to show the new hashval for this child.
627 : */
628 176849 : xfs_da3_fixhashpath(state, &state->path);
629 : }
630 89178 : 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 1570 : ASSERT(state->extravalid == 0 ||
639 : state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
640 :
641 : /*
642 : * Split the root node.
643 : */
644 1570 : ASSERT(state->path.active == 0);
645 1570 : oldblk = &state->path.blk[0];
646 1570 : error = xfs_da3_root_split(state, oldblk, addblk);
647 1570 : 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 1570 : node = oldblk->bp->b_addr;
662 1570 : if (node->hdr.info.forw) {
663 3140 : 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 1570 : node = addblk->bp->b_addr;
670 1570 : node->hdr.info.back = cpu_to_be32(oldblk->blkno);
671 1570 : xfs_trans_log_buf(state->args->trans, addblk->bp,
672 : XFS_DA_LOGRANGE(node, &node->hdr.info,
673 : sizeof(node->hdr.info)));
674 : }
675 1570 : node = oldblk->bp->b_addr;
676 1570 : 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 1570 : out:
690 1570 : addblk->bp = NULL;
691 1570 : 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 1570 : 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 1570 : struct xfs_da_intnode *node;
706 1570 : struct xfs_da_intnode *oldroot;
707 1570 : struct xfs_da_node_entry *btree;
708 1570 : struct xfs_da3_icnode_hdr nodehdr;
709 1570 : struct xfs_da_args *args;
710 1570 : struct xfs_buf *bp;
711 1570 : struct xfs_inode *dp;
712 1570 : struct xfs_trans *tp;
713 1570 : struct xfs_dir2_leaf *leaf;
714 1570 : xfs_dablk_t blkno;
715 1570 : int level;
716 1570 : int error;
717 1570 : int size;
718 :
719 1570 : 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 1570 : args = state->args;
726 1570 : error = xfs_da_grow_inode(args, &blkno);
727 1570 : if (error)
728 : return error;
729 :
730 1570 : dp = args->dp;
731 1570 : tp = args->trans;
732 1570 : error = xfs_da_get_buf(tp, dp, blkno, &bp, args->whichfork);
733 1570 : if (error)
734 : return error;
735 1570 : node = bp->b_addr;
736 1570 : oldroot = blk1->bp->b_addr;
737 1570 : if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
738 : oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC)) {
739 6 : struct xfs_da3_icnode_hdr icnodehdr;
740 :
741 6 : xfs_da3_node_hdr_from_disk(dp->i_mount, &icnodehdr, oldroot);
742 6 : btree = icnodehdr.btree;
743 6 : size = (int)((char *)&btree[icnodehdr.count] - (char *)oldroot);
744 6 : level = icnodehdr.level;
745 :
746 : /*
747 : * we are about to copy oldroot to bp, so set up the type
748 : * of bp while we know exactly what it will be.
749 : */
750 6 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
751 : } else {
752 1564 : struct xfs_dir3_icleaf_hdr leafhdr;
753 :
754 1564 : leaf = (xfs_dir2_leaf_t *)oldroot;
755 1564 : xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
756 :
757 1564 : ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
758 : leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
759 1564 : size = (int)((char *)&leafhdr.ents[leafhdr.count] -
760 : (char *)leaf);
761 1564 : 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 1564 : 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 3140 : memcpy(node, oldroot, size);
777 1570 : 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 1570 : struct xfs_da3_intnode *node3 = (struct xfs_da3_intnode *)node;
780 :
781 1570 : node3->hdr.info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
782 : }
783 1570 : xfs_trans_log_buf(tp, bp, 0, size - 1);
784 :
785 1570 : bp->b_ops = blk1->bp->b_ops;
786 1570 : xfs_trans_buf_copy_type(bp, blk1->bp);
787 1570 : blk1->bp = bp;
788 1570 : blk1->blkno = blkno;
789 :
790 : /*
791 : * Set up the new root node.
792 : */
793 1570 : error = xfs_da3_node_create(args,
794 1570 : (args->whichfork == XFS_DATA_FORK) ? args->geo->leafblk : 0,
795 : level + 1, &bp, args->whichfork);
796 1570 : if (error)
797 : return error;
798 :
799 1570 : node = bp->b_addr;
800 1570 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
801 1570 : btree = nodehdr.btree;
802 1570 : btree[0].hashval = cpu_to_be32(blk1->hashval);
803 1570 : btree[0].before = cpu_to_be32(blk1->blkno);
804 1570 : btree[1].hashval = cpu_to_be32(blk2->hashval);
805 1570 : btree[1].before = cpu_to_be32(blk2->blkno);
806 1570 : nodehdr.count = 2;
807 1570 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
808 :
809 : #ifdef DEBUG
810 1570 : 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 1570 : xfs_trans_log_buf(tp, bp,
821 1570 : XFS_DA_LOGRANGE(node, btree, sizeof(xfs_da_node_entry_t) * 2));
822 :
823 1570 : return 0;
824 : }
825 :
826 : /*
827 : * Split the node, rebalance, then add the new entry.
828 : */
829 : STATIC int /* error */
830 87671 : 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 87671 : struct xfs_da_intnode *node;
839 87671 : struct xfs_da3_icnode_hdr nodehdr;
840 87671 : xfs_dablk_t blkno;
841 87671 : int newcount;
842 87671 : int error;
843 87671 : int useextra;
844 87671 : struct xfs_inode *dp = state->args->dp;
845 :
846 87671 : trace_xfs_da_node_split(state->args);
847 :
848 87671 : node = oldblk->bp->b_addr;
849 87671 : 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 87670 : useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
855 87670 : newcount = 1 + useextra;
856 : /*
857 : * Do we have to split the node?
858 : */
859 87670 : 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 61 : error = xfs_da_grow_inode(state->args, &blkno);
865 61 : if (error)
866 : return error; /* GROT: dir is inconsistent */
867 :
868 61 : error = xfs_da3_node_create(state->args, blkno, treelevel,
869 : &newblk->bp, state->args->whichfork);
870 61 : if (error)
871 : return error; /* GROT: dir is inconsistent */
872 61 : newblk->blkno = blkno;
873 61 : newblk->magic = XFS_DA_NODE_MAGIC;
874 61 : xfs_da3_node_rebalance(state, oldblk, newblk);
875 61 : error = xfs_da3_blk_link(state, oldblk, newblk);
876 61 : if (error)
877 : return error;
878 61 : *result = 1;
879 : } else {
880 87609 : *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 87670 : node = oldblk->bp->b_addr;
896 87670 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
897 87669 : if (oldblk->index <= nodehdr.count) {
898 87635 : oldblk->index++;
899 87635 : xfs_da3_node_add(state, oldblk, addblk);
900 87637 : 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 34 : newblk->index++;
908 34 : xfs_da3_node_add(state, newblk, addblk);
909 34 : 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 61 : 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 61 : struct xfs_da_intnode *node1;
933 61 : struct xfs_da_intnode *node2;
934 61 : struct xfs_da_node_entry *btree1;
935 61 : struct xfs_da_node_entry *btree2;
936 61 : struct xfs_da_node_entry *btree_s;
937 61 : struct xfs_da_node_entry *btree_d;
938 61 : struct xfs_da3_icnode_hdr nodehdr1;
939 61 : struct xfs_da3_icnode_hdr nodehdr2;
940 61 : struct xfs_trans *tp;
941 61 : int count;
942 61 : int tmp;
943 61 : int swap = 0;
944 61 : struct xfs_inode *dp = state->args->dp;
945 :
946 61 : trace_xfs_da_node_rebalance(state->args);
947 :
948 61 : node1 = blk1->bp->b_addr;
949 61 : node2 = blk2->bp->b_addr;
950 61 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
951 61 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
952 61 : btree1 = nodehdr1.btree;
953 61 : 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 61 : 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 61 : count = (nodehdr1.count - nodehdr2.count) / 2;
972 61 : if (count == 0)
973 0 : return;
974 61 : tp = state->args->trans;
975 : /*
976 : * Two cases: high-to-low and low-to-high.
977 : */
978 61 : if (count > 0) {
979 : /*
980 : * Move elements in node2 up to make a hole.
981 : */
982 61 : tmp = nodehdr2.count;
983 61 : 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 61 : nodehdr2.count += count;
995 61 : tmp = count * (uint)sizeof(xfs_da_node_entry_t);
996 61 : btree_s = &btree1[nodehdr1.count - count];
997 61 : btree_d = &btree2[0];
998 122 : memcpy(btree_d, btree_s, tmp);
999 61 : 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 61 : xfs_da3_node_hdr_to_disk(dp->i_mount, node1, &nodehdr1);
1030 61 : xfs_trans_log_buf(tp, blk1->bp,
1031 61 : XFS_DA_LOGRANGE(node1, &node1->hdr,
1032 : state->args->geo->node_hdr_size));
1033 :
1034 61 : xfs_da3_node_hdr_to_disk(dp->i_mount, node2, &nodehdr2);
1035 61 : xfs_trans_log_buf(tp, blk2->bp,
1036 61 : 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 61 : 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 61 : blk1->hashval = be32_to_cpu(btree1[nodehdr1.count - 1].hashval);
1053 61 : blk2->hashval = be32_to_cpu(btree2[nodehdr2.count - 1].hashval);
1054 :
1055 : /*
1056 : * Adjust the expected index for insertion.
1057 : */
1058 61 : if (blk1->index >= nodehdr1.count) {
1059 34 : blk2->index = blk1->index - nodehdr1.count;
1060 34 : 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 87669 : 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 87669 : struct xfs_da_intnode *node;
1074 87669 : struct xfs_da3_icnode_hdr nodehdr;
1075 87669 : struct xfs_da_node_entry *btree;
1076 87669 : int tmp;
1077 87669 : struct xfs_inode *dp = state->args->dp;
1078 :
1079 87669 : trace_xfs_da_node_add(state->args);
1080 :
1081 87669 : node = oldblk->bp->b_addr;
1082 87669 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1083 87671 : btree = nodehdr.btree;
1084 :
1085 87671 : ASSERT(oldblk->index >= 0 && oldblk->index <= nodehdr.count);
1086 87671 : ASSERT(newblk->blkno != 0);
1087 87671 : if (state->args->whichfork == XFS_DATA_FORK)
1088 27296 : 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 87671 : tmp = 0;
1095 87671 : if (oldblk->index < nodehdr.count) {
1096 25744 : tmp = (nodehdr.count - oldblk->index) * (uint)sizeof(*btree);
1097 51488 : memmove(&btree[oldblk->index + 1], &btree[oldblk->index], tmp);
1098 : }
1099 87671 : btree[oldblk->index].hashval = cpu_to_be32(newblk->hashval);
1100 87671 : btree[oldblk->index].before = cpu_to_be32(newblk->blkno);
1101 87671 : xfs_trans_log_buf(state->args->trans, oldblk->bp,
1102 87671 : XFS_DA_LOGRANGE(node, &btree[oldblk->index],
1103 : tmp + sizeof(*btree)));
1104 :
1105 87668 : nodehdr.count += 1;
1106 87668 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
1107 87671 : xfs_trans_log_buf(state->args->trans, oldblk->bp,
1108 87671 : 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 87668 : oldblk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
1115 87668 : }
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 2827262 : xfs_da3_join(
1127 : struct xfs_da_state *state)
1128 : {
1129 2827262 : struct xfs_da_state_blk *drop_blk;
1130 2827262 : struct xfs_da_state_blk *save_blk;
1131 2827262 : int action = 0;
1132 2827262 : int error;
1133 :
1134 2827262 : trace_xfs_da_join(state->args);
1135 :
1136 2827299 : drop_blk = &state->path.blk[ state->path.active-1 ];
1137 2827299 : save_blk = &state->altpath.blk[ state->path.active-1 ];
1138 2827299 : ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
1139 2827299 : 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 2849958 : for ( ; state->path.active >= 2; drop_blk--, save_blk--,
1147 22659 : 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 2828422 : switch (drop_blk->magic) {
1155 946997 : case XFS_ATTR_LEAF_MAGIC:
1156 946997 : error = xfs_attr3_leaf_toosmall(state, &action);
1157 947011 : if (error)
1158 2 : return error;
1159 947009 : if (action == 0)
1160 : return 0;
1161 768 : xfs_attr3_leaf_unbalance(state, drop_blk, save_blk);
1162 768 : break;
1163 1880281 : case XFS_DIR2_LEAFN_MAGIC:
1164 1880281 : error = xfs_dir2_leafn_toosmall(state, &action);
1165 1880293 : if (error)
1166 0 : return error;
1167 1880293 : if (action == 0)
1168 : return 0;
1169 21907 : xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
1170 21907 : break;
1171 1144 : case XFS_DA_NODE_MAGIC:
1172 : /*
1173 : * Remove the offending node, fixup hashvals,
1174 : * check for a toosmall neighbor.
1175 : */
1176 1144 : xfs_da3_node_remove(state, drop_blk);
1177 1144 : xfs_da3_fixhashpath(state, &state->path);
1178 1144 : error = xfs_da3_node_toosmall(state, &action);
1179 1144 : if (error)
1180 0 : return error;
1181 1144 : if (action == 0)
1182 : return 0;
1183 5 : xfs_da3_node_unbalance(state, drop_blk, save_blk);
1184 5 : break;
1185 : }
1186 22680 : xfs_da3_fixhashpath(state, &state->altpath);
1187 22680 : error = xfs_da3_blk_unlink(state, drop_blk, save_blk);
1188 22680 : xfs_da_state_kill_altpath(state);
1189 22680 : if (error)
1190 0 : return error;
1191 22680 : error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
1192 : drop_blk->bp);
1193 22659 : drop_blk->bp = NULL;
1194 22659 : 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 21536 : xfs_da3_node_remove(state, drop_blk);
1203 21536 : xfs_da3_fixhashpath(state, &state->path);
1204 21536 : error = xfs_da3_root_join(state, &state->path.blk[0]);
1205 21536 : return error;
1206 : }
1207 :
1208 : #ifdef DEBUG
1209 : static void
1210 1129 : xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
1211 : {
1212 1129 : __be16 magic = blkinfo->magic;
1213 :
1214 1129 : if (level == 1) {
1215 1128 : ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1216 : magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
1217 : magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
1218 : magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
1219 : } else {
1220 1 : ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
1221 : magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
1222 : }
1223 1129 : ASSERT(!blkinfo->forw);
1224 1129 : ASSERT(!blkinfo->back);
1225 1129 : }
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 21536 : xfs_da3_root_join(
1236 : struct xfs_da_state *state,
1237 : struct xfs_da_state_blk *root_blk)
1238 : {
1239 21536 : struct xfs_da_intnode *oldroot;
1240 21536 : struct xfs_da_args *args;
1241 21536 : xfs_dablk_t child;
1242 21536 : struct xfs_buf *bp;
1243 21536 : struct xfs_da3_icnode_hdr oldroothdr;
1244 21536 : int error;
1245 21536 : struct xfs_inode *dp = state->args->dp;
1246 21536 : xfs_failaddr_t fa;
1247 :
1248 21536 : trace_xfs_da_root_join(state->args);
1249 :
1250 21536 : ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
1251 :
1252 21536 : args = state->args;
1253 21536 : oldroot = root_blk->bp->b_addr;
1254 21536 : xfs_da3_node_hdr_from_disk(dp->i_mount, &oldroothdr, oldroot);
1255 21536 : ASSERT(oldroothdr.forw == 0);
1256 21536 : ASSERT(oldroothdr.back == 0);
1257 :
1258 : /*
1259 : * If the root has more than one child, then don't do anything.
1260 : */
1261 21536 : 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 1129 : child = be32_to_cpu(oldroothdr.btree[0].before);
1269 1129 : ASSERT(child != 0);
1270 1129 : error = xfs_da3_node_read(args->trans, dp, child, &bp, args->whichfork);
1271 1129 : if (error)
1272 : return error;
1273 1129 : fa = xfs_da3_header_check(bp, args->owner);
1274 1129 : 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 1129 : 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 2258 : memcpy(root_blk->bp->b_addr, bp->b_addr, args->geo->blksize);
1290 1129 : root_blk->bp->b_ops = bp->b_ops;
1291 1129 : xfs_trans_buf_copy_type(root_blk->bp, bp);
1292 1129 : if (oldroothdr.magic == XFS_DA3_NODE_MAGIC) {
1293 1129 : struct xfs_da3_blkinfo *da3 = root_blk->bp->b_addr;
1294 1129 : da3->blkno = cpu_to_be64(xfs_buf_daddr(root_blk->bp));
1295 : }
1296 1129 : xfs_trans_log_buf(args->trans, root_blk->bp, 0,
1297 1129 : args->geo->blksize - 1);
1298 1129 : error = xfs_da_shrink_inode(args, child, bp);
1299 1129 : 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 1144 : xfs_da3_node_toosmall(
1313 : struct xfs_da_state *state,
1314 : int *action)
1315 : {
1316 1144 : struct xfs_da_intnode *node;
1317 1144 : struct xfs_da_state_blk *blk;
1318 1144 : struct xfs_da_blkinfo *info;
1319 1144 : xfs_dablk_t blkno;
1320 1144 : struct xfs_buf *bp;
1321 1144 : xfs_failaddr_t fa;
1322 1144 : struct xfs_da3_icnode_hdr nodehdr;
1323 1144 : int count;
1324 1144 : int forward;
1325 1144 : int error;
1326 1144 : int retval;
1327 1144 : int i;
1328 1144 : struct xfs_inode *dp = state->args->dp;
1329 :
1330 1144 : 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 1144 : blk = &state->path.blk[ state->path.active-1 ];
1338 1144 : info = blk->bp->b_addr;
1339 1144 : node = (xfs_da_intnode_t *)info;
1340 1144 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1341 1144 : if (nodehdr.count > (state->args->geo->node_ents >> 1)) {
1342 506 : *action = 0; /* blk over 50%, don't try to join */
1343 506 : 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 638 : 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 638 : count = state->args->geo->node_ents;
1379 638 : count -= state->args->geo->node_ents >> 2;
1380 638 : count -= nodehdr.count;
1381 :
1382 : /* start with smaller blk num */
1383 638 : forward = nodehdr.forw < nodehdr.back;
1384 1909 : for (i = 0; i < 2; forward = !forward, i++) {
1385 1276 : struct xfs_da3_icnode_hdr thdr;
1386 1276 : if (forward)
1387 : blkno = nodehdr.forw;
1388 : else
1389 638 : blkno = nodehdr.back;
1390 1276 : if (blkno == 0)
1391 413 : continue;
1392 863 : error = xfs_da3_node_read(state->args->trans, dp, blkno, &bp,
1393 : state->args->whichfork);
1394 863 : if (error)
1395 0 : return error;
1396 863 : fa = xfs_da3_node_header_check(bp, state->args->owner);
1397 863 : 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 863 : node = bp->b_addr;
1405 863 : xfs_da3_node_hdr_from_disk(dp->i_mount, &thdr, node);
1406 863 : xfs_trans_brelse(state->args->trans, bp);
1407 :
1408 863 : if (count - thdr.count >= 0)
1409 : break; /* fits with at least 25% to spare */
1410 : }
1411 638 : if (i >= 2) {
1412 633 : *action = 0;
1413 633 : 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 10 : memcpy(&state->altpath, &state->path, sizeof(state->path));
1421 5 : if (blkno < blk->blkno) {
1422 2 : error = xfs_da3_path_shift(state, &state->altpath, forward,
1423 : 0, &retval);
1424 : } else {
1425 3 : error = xfs_da3_path_shift(state, &state->path, forward,
1426 : 0, &retval);
1427 : }
1428 5 : if (error)
1429 : return error;
1430 5 : if (retval) {
1431 0 : *action = 0;
1432 0 : return 0;
1433 : }
1434 5 : *action = 1;
1435 5 : return 0;
1436 : }
1437 :
1438 : /*
1439 : * Pick up the last hashvalue from an intermediate node.
1440 : */
1441 : STATIC uint
1442 110356 : xfs_da3_node_lasthash(
1443 : struct xfs_inode *dp,
1444 : struct xfs_buf *bp,
1445 : int *count)
1446 : {
1447 110356 : struct xfs_da3_icnode_hdr nodehdr;
1448 :
1449 110356 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, bp->b_addr);
1450 110354 : if (count)
1451 110354 : *count = nodehdr.count;
1452 110354 : if (!nodehdr.count)
1453 : return 0;
1454 110354 : 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 65267701 : xfs_da3_fixhashpath(
1463 : struct xfs_da_state *state,
1464 : struct xfs_da_state_path *path)
1465 : {
1466 65267701 : struct xfs_da_state_blk *blk;
1467 65267701 : struct xfs_da_intnode *node;
1468 65267701 : struct xfs_da_node_entry *btree;
1469 65267701 : xfs_dahash_t lasthash=0;
1470 65267701 : int level;
1471 65267701 : int count;
1472 65267701 : struct xfs_inode *dp = state->args->dp;
1473 :
1474 65267701 : trace_xfs_da_fixhashpath(state->args);
1475 :
1476 65271120 : level = path->active-1;
1477 65271120 : blk = &path->blk[ level ];
1478 65271120 : switch (blk->magic) {
1479 2550179 : case XFS_ATTR_LEAF_MAGIC:
1480 2550179 : lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
1481 2550179 : if (count == 0)
1482 4 : return;
1483 : break;
1484 62610587 : case XFS_DIR2_LEAFN_MAGIC:
1485 62610587 : lasthash = xfs_dir2_leaf_lasthash(dp, blk->bp, &count);
1486 62611861 : if (count == 0)
1487 : return;
1488 : break;
1489 110354 : case XFS_DA_NODE_MAGIC:
1490 110354 : lasthash = xfs_da3_node_lasthash(dp, blk->bp, &count);
1491 110354 : if (count == 0)
1492 : return;
1493 : break;
1494 : }
1495 67635550 : for (blk--, level--; level >= 0; blk--, level--) {
1496 65177615 : struct xfs_da3_icnode_hdr nodehdr;
1497 :
1498 65177615 : node = blk->bp->b_addr;
1499 65177615 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1500 65176470 : btree = nodehdr.btree;
1501 130352940 : if (be32_to_cpu(btree[blk->index].hashval) == lasthash)
1502 : break;
1503 2363237 : blk->hashval = lasthash;
1504 2363237 : btree[blk->index].hashval = cpu_to_be32(lasthash);
1505 2363237 : xfs_trans_log_buf(state->args->trans, blk->bp,
1506 2363237 : XFS_DA_LOGRANGE(node, &btree[blk->index],
1507 : sizeof(*btree)));
1508 :
1509 2363160 : 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 22680 : xfs_da3_node_remove(
1518 : struct xfs_da_state *state,
1519 : struct xfs_da_state_blk *drop_blk)
1520 : {
1521 22680 : struct xfs_da_intnode *node;
1522 22680 : struct xfs_da3_icnode_hdr nodehdr;
1523 22680 : struct xfs_da_node_entry *btree;
1524 22680 : int index;
1525 22680 : int tmp;
1526 22680 : struct xfs_inode *dp = state->args->dp;
1527 :
1528 22680 : trace_xfs_da_node_remove(state->args);
1529 :
1530 22680 : node = drop_blk->bp->b_addr;
1531 22680 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1532 22680 : ASSERT(drop_blk->index < nodehdr.count);
1533 22680 : ASSERT(drop_blk->index >= 0);
1534 :
1535 : /*
1536 : * Copy over the offending entry, or just zero it out.
1537 : */
1538 22680 : index = drop_blk->index;
1539 22680 : btree = nodehdr.btree;
1540 22680 : if (index < nodehdr.count - 1) {
1541 21996 : tmp = nodehdr.count - index - 1;
1542 21996 : tmp *= (uint)sizeof(xfs_da_node_entry_t);
1543 43992 : memmove(&btree[index], &btree[index + 1], tmp);
1544 21996 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1545 21996 : XFS_DA_LOGRANGE(node, &btree[index], tmp));
1546 21996 : index = nodehdr.count - 1;
1547 : }
1548 22680 : memset(&btree[index], 0, sizeof(xfs_da_node_entry_t));
1549 22680 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1550 22680 : XFS_DA_LOGRANGE(node, &btree[index], sizeof(btree[index])));
1551 22680 : nodehdr.count -= 1;
1552 22680 : xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
1553 22680 : xfs_trans_log_buf(state->args->trans, drop_blk->bp,
1554 22680 : 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 22680 : drop_blk->hashval = be32_to_cpu(btree[index - 1].hashval);
1560 22680 : }
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 5 : 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 5 : struct xfs_da_intnode *drop_node;
1573 5 : struct xfs_da_intnode *save_node;
1574 5 : struct xfs_da_node_entry *drop_btree;
1575 5 : struct xfs_da_node_entry *save_btree;
1576 5 : struct xfs_da3_icnode_hdr drop_hdr;
1577 5 : struct xfs_da3_icnode_hdr save_hdr;
1578 5 : struct xfs_trans *tp;
1579 5 : int sindex;
1580 5 : int tmp;
1581 5 : struct xfs_inode *dp = state->args->dp;
1582 :
1583 5 : trace_xfs_da_node_unbalance(state->args);
1584 :
1585 5 : drop_node = drop_blk->bp->b_addr;
1586 5 : save_node = save_blk->bp->b_addr;
1587 5 : xfs_da3_node_hdr_from_disk(dp->i_mount, &drop_hdr, drop_node);
1588 5 : xfs_da3_node_hdr_from_disk(dp->i_mount, &save_hdr, save_node);
1589 5 : drop_btree = drop_hdr.btree;
1590 5 : save_btree = save_hdr.btree;
1591 5 : 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 10 : if ((be32_to_cpu(drop_btree[0].hashval) <
1598 9 : be32_to_cpu(save_btree[0].hashval)) ||
1599 4 : (be32_to_cpu(drop_btree[drop_hdr.count - 1].hashval) <
1600 4 : be32_to_cpu(save_btree[save_hdr.count - 1].hashval))) {
1601 : /* XXX: check this - is memmove dst correct? */
1602 1 : tmp = save_hdr.count * sizeof(xfs_da_node_entry_t);
1603 2 : memmove(&save_btree[drop_hdr.count], &save_btree[0], tmp);
1604 :
1605 1 : sindex = 0;
1606 1 : xfs_trans_log_buf(tp, save_blk->bp,
1607 1 : XFS_DA_LOGRANGE(save_node, &save_btree[0],
1608 : (save_hdr.count + drop_hdr.count) *
1609 : sizeof(xfs_da_node_entry_t)));
1610 : } else {
1611 4 : sindex = save_hdr.count;
1612 4 : xfs_trans_log_buf(tp, save_blk->bp,
1613 4 : 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 5 : tmp = drop_hdr.count * (uint)sizeof(xfs_da_node_entry_t);
1621 10 : memcpy(&save_btree[sindex], &drop_btree[0], tmp);
1622 5 : save_hdr.count += drop_hdr.count;
1623 :
1624 5 : xfs_da3_node_hdr_to_disk(dp->i_mount, save_node, &save_hdr);
1625 5 : xfs_trans_log_buf(tp, save_blk->bp,
1626 5 : 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 5 : save_blk->hashval = be32_to_cpu(save_btree[save_hdr.count - 1].hashval);
1633 5 : }
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 150207509 : xfs_da3_node_lookup_int(
1652 : struct xfs_da_state *state,
1653 : int *result)
1654 : {
1655 150207509 : struct xfs_da_state_blk *blk;
1656 150207509 : struct xfs_da_blkinfo *curr;
1657 150207509 : struct xfs_da_intnode *node;
1658 150207509 : struct xfs_da_node_entry *btree;
1659 150207509 : struct xfs_da3_icnode_hdr nodehdr;
1660 150207509 : struct xfs_da_args *args;
1661 150207509 : xfs_failaddr_t fa;
1662 150207509 : xfs_dablk_t blkno;
1663 150207509 : xfs_dahash_t hashval;
1664 150207509 : xfs_dahash_t btreehashval;
1665 150207509 : int probe;
1666 150207509 : int span;
1667 150207509 : int max;
1668 150207509 : int error;
1669 150207509 : int retval;
1670 150207509 : unsigned int expected_level = 0;
1671 150207509 : uint16_t magic;
1672 150207509 : struct xfs_inode *dp = state->args->dp;
1673 :
1674 150207509 : 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 150207509 : blkno = args->geo->leafblk;
1681 150207509 : for (blk = &state->path.blk[0], state->path.active = 1;
1682 302955263 : state->path.active <= XFS_DA_NODE_MAXDEPTH;
1683 152747754 : blk++, state->path.active++) {
1684 : /*
1685 : * Read the next node down in the tree.
1686 : */
1687 302955263 : blk->blkno = blkno;
1688 302955263 : error = xfs_da3_node_read(args->trans, args->dp, blkno,
1689 : &blk->bp, args->whichfork);
1690 302965320 : if (error) {
1691 12032 : blk->blkno = 0;
1692 12032 : state->path.active--;
1693 12032 : return error;
1694 : }
1695 302953288 : curr = blk->bp->b_addr;
1696 302953288 : magic = be16_to_cpu(curr->magic);
1697 :
1698 302953288 : if (magic == XFS_ATTR_LEAF_MAGIC ||
1699 302953288 : magic == XFS_ATTR3_LEAF_MAGIC) {
1700 6155876 : fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);
1701 6155850 : if (fa) {
1702 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
1703 0 : xfs_da_mark_sick(args);
1704 0 : return -EFSCORRUPTED;
1705 : }
1706 6155850 : blk->magic = XFS_ATTR_LEAF_MAGIC;
1707 6155850 : blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
1708 6155827 : break;
1709 : }
1710 :
1711 296797412 : if (magic == XFS_DIR2_LEAFN_MAGIC ||
1712 296797412 : magic == XFS_DIR3_LEAFN_MAGIC) {
1713 144058573 : fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);
1714 144069233 : if (fa) {
1715 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
1716 0 : xfs_da_mark_sick(args);
1717 0 : return -EFSCORRUPTED;
1718 : }
1719 144069233 : blk->magic = XFS_DIR2_LEAFN_MAGIC;
1720 144069233 : blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
1721 : blk->bp, NULL);
1722 144064141 : break;
1723 : }
1724 :
1725 152738839 : 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 152738839 : fa = xfs_da3_node_header_check(blk->bp, args->owner);
1732 152746594 : 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 152746594 : blk->magic = XFS_DA_NODE_MAGIC;
1739 :
1740 : /*
1741 : * Search an intermediate node for a match.
1742 : */
1743 152746594 : node = blk->bp->b_addr;
1744 152746594 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
1745 152747754 : btree = nodehdr.btree;
1746 :
1747 : /* Tree taller than we can handle; bail out! */
1748 152747754 : 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 152747754 : if (blkno == args->geo->leafblk)
1756 150178251 : expected_level = nodehdr.level - 1;
1757 2572499 : 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 2572499 : expected_level--;
1763 :
1764 152747754 : max = nodehdr.count;
1765 152747754 : blk->hashval = be32_to_cpu(btree[max - 1].hashval);
1766 :
1767 : /*
1768 : * Binary search. (note: small blocks will skip loop)
1769 : */
1770 152747754 : probe = span = max / 2;
1771 152747754 : hashval = args->hashval;
1772 314350386 : while (span > 4) {
1773 161846807 : span /= 2;
1774 161846807 : btreehashval = be32_to_cpu(btree[probe].hashval);
1775 161846807 : if (btreehashval < hashval)
1776 79433265 : probe += span;
1777 82413542 : else if (btreehashval > hashval)
1778 82169367 : probe -= span;
1779 : else
1780 : break;
1781 : }
1782 152747754 : ASSERT((probe >= 0) && (probe < max));
1783 152925699 : 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 791734153 : while (probe > 0 &&
1791 361240030 : be32_to_cpu(btree[probe].hashval) >= hashval) {
1792 277746369 : probe--;
1793 : }
1794 653224428 : while (probe < max &&
1795 325224259 : be32_to_cpu(btree[probe].hashval) < hashval) {
1796 175252415 : probe++;
1797 : }
1798 :
1799 : /*
1800 : * Pick the right block to descend on.
1801 : */
1802 152747754 : if (probe == max) {
1803 2779014 : blk->index = max - 1;
1804 2779014 : blkno = be32_to_cpu(btree[max - 1].before);
1805 : } else {
1806 149968740 : blk->index = probe;
1807 149968740 : blkno = be32_to_cpu(btree[probe].before);
1808 : }
1809 :
1810 : /* We can't point back to the root. */
1811 152747754 : 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 150219968 : 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 756577296 : for (;;) {
1829 453398632 : if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
1830 145046406 : retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
1831 : &blk->index, state);
1832 308352226 : } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1833 308352226 : retval = xfs_attr3_leaf_lookup_int(blk->bp, args);
1834 308350372 : blk->index = args->index;
1835 308350372 : args->blkno = blk->blkno;
1836 : } else {
1837 0 : ASSERT(0);
1838 0 : xfs_da_mark_sick(args);
1839 0 : return -EFSCORRUPTED;
1840 : }
1841 453377670 : if (((retval == -ENOENT) || (retval == -ENOATTR)) &&
1842 346081875 : (blk->hashval == args->hashval)) {
1843 303464074 : error = xfs_da3_path_shift(state, &state->path, 1, 1,
1844 : &retval);
1845 303465770 : if (error)
1846 0 : return error;
1847 303465770 : if (retval == 0) {
1848 303178664 : continue;
1849 287106 : } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1850 : /* path_shift() gives ENOENT */
1851 136189 : retval = -ENOATTR;
1852 : }
1853 : }
1854 150217178 : break;
1855 : }
1856 150217178 : *result = retval;
1857 150217178 : return 0;
1858 : }
1859 :
1860 : /*========================================================================
1861 : * Utility routines.
1862 : *========================================================================*/
1863 :
1864 : /*
1865 : * Compare two intermediate nodes for "order".
1866 : */
1867 : STATIC int
1868 61 : xfs_da3_node_order(
1869 : struct xfs_inode *dp,
1870 : struct xfs_buf *node1_bp,
1871 : struct xfs_buf *node2_bp)
1872 : {
1873 61 : struct xfs_da_intnode *node1;
1874 61 : struct xfs_da_intnode *node2;
1875 61 : struct xfs_da_node_entry *btree1;
1876 61 : struct xfs_da_node_entry *btree2;
1877 61 : struct xfs_da3_icnode_hdr node1hdr;
1878 61 : struct xfs_da3_icnode_hdr node2hdr;
1879 :
1880 61 : node1 = node1_bp->b_addr;
1881 61 : node2 = node2_bp->b_addr;
1882 61 : xfs_da3_node_hdr_from_disk(dp->i_mount, &node1hdr, node1);
1883 61 : xfs_da3_node_hdr_from_disk(dp->i_mount, &node2hdr, node2);
1884 61 : btree1 = node1hdr.btree;
1885 61 : btree2 = node2hdr.btree;
1886 :
1887 122 : if (node1hdr.count > 0 && node2hdr.count > 0 &&
1888 183 : ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
1889 61 : (be32_to_cpu(btree2[node2hdr.count - 1].hashval) <
1890 61 : 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 89240 : 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 89240 : struct xfs_da_blkinfo *old_info;
1906 89240 : struct xfs_da_blkinfo *new_info;
1907 89240 : struct xfs_da_blkinfo *tmp_info;
1908 89240 : struct xfs_da_args *args;
1909 89240 : struct xfs_buf *bp;
1910 89240 : xfs_failaddr_t fa;
1911 89240 : int before = 0;
1912 89240 : int error;
1913 89240 : struct xfs_inode *dp = state->args->dp;
1914 :
1915 : /*
1916 : * Set up environment.
1917 : */
1918 89240 : args = state->args;
1919 89240 : ASSERT(args != NULL);
1920 89240 : old_info = old_blk->bp->b_addr;
1921 89240 : new_info = new_blk->bp->b_addr;
1922 89240 : 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 89240 : switch (old_blk->magic) {
1927 60322 : case XFS_ATTR_LEAF_MAGIC:
1928 60322 : before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
1929 60322 : break;
1930 28857 : case XFS_DIR2_LEAFN_MAGIC:
1931 28857 : before = xfs_dir2_leafn_order(dp, old_blk->bp, new_blk->bp);
1932 28857 : break;
1933 61 : case XFS_DA_NODE_MAGIC:
1934 61 : before = xfs_da3_node_order(dp, old_blk->bp, new_blk->bp);
1935 61 : break;
1936 : }
1937 :
1938 : /*
1939 : * Link blocks in appropriate order.
1940 : */
1941 89240 : if (before) {
1942 : /*
1943 : * Link new block in before existing block.
1944 : */
1945 0 : trace_xfs_da_link_before(args);
1946 0 : new_info->forw = cpu_to_be32(old_blk->blkno);
1947 0 : new_info->back = old_info->back;
1948 0 : if (old_info->back) {
1949 0 : error = xfs_da3_node_read(args->trans, dp,
1950 0 : be32_to_cpu(old_info->back),
1951 : &bp, args->whichfork);
1952 0 : if (error)
1953 : return error;
1954 0 : fa = xfs_da3_header_check(bp, args->owner);
1955 0 : if (fa) {
1956 0 : __xfs_buf_mark_corrupt(bp, fa);
1957 0 : xfs_trans_brelse(args->trans, bp);
1958 0 : xfs_da_mark_sick(args);
1959 0 : return -EFSCORRUPTED;
1960 : }
1961 0 : ASSERT(bp != NULL);
1962 0 : tmp_info = bp->b_addr;
1963 0 : ASSERT(tmp_info->magic == old_info->magic);
1964 0 : ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);
1965 0 : tmp_info->forw = cpu_to_be32(new_blk->blkno);
1966 0 : xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1967 : }
1968 0 : old_info->back = cpu_to_be32(new_blk->blkno);
1969 : } else {
1970 : /*
1971 : * Link new block in after existing block.
1972 : */
1973 89240 : trace_xfs_da_link_after(args);
1974 89240 : new_info->forw = old_info->forw;
1975 89240 : new_info->back = cpu_to_be32(old_blk->blkno);
1976 89240 : if (old_info->forw) {
1977 25756 : error = xfs_da3_node_read(args->trans, dp,
1978 25756 : be32_to_cpu(old_info->forw),
1979 : &bp, args->whichfork);
1980 25756 : if (error)
1981 : return error;
1982 25756 : fa = xfs_da3_header_check(bp, args->owner);
1983 25756 : 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 25756 : ASSERT(bp != NULL);
1990 25756 : tmp_info = bp->b_addr;
1991 25756 : ASSERT(tmp_info->magic == old_info->magic);
1992 51512 : ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
1993 25756 : tmp_info->back = cpu_to_be32(new_blk->blkno);
1994 25756 : xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1995 : }
1996 178480 : old_info->forw = cpu_to_be32(new_blk->blkno);
1997 : }
1998 :
1999 89240 : xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
2000 89241 : xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
2001 89241 : return 0;
2002 : }
2003 :
2004 : /*
2005 : * Unlink a block from a doubly linked list of blocks.
2006 : */
2007 : STATIC int /* error */
2008 22680 : 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 22680 : struct xfs_da_blkinfo *drop_info;
2014 22680 : struct xfs_da_blkinfo *save_info;
2015 22680 : struct xfs_da_blkinfo *tmp_info;
2016 22680 : struct xfs_da_args *args;
2017 22680 : struct xfs_buf *bp;
2018 22680 : xfs_failaddr_t fa;
2019 22680 : int error;
2020 :
2021 : /*
2022 : * Set up environment.
2023 : */
2024 22680 : args = state->args;
2025 22680 : ASSERT(args != NULL);
2026 22680 : save_info = save_blk->bp->b_addr;
2027 22680 : drop_info = drop_blk->bp->b_addr;
2028 22680 : 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 22680 : ASSERT(save_blk->magic == drop_blk->magic);
2032 48572 : ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
2033 : (be32_to_cpu(save_info->back) == drop_blk->blkno));
2034 64828 : 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 45360 : if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
2041 3212 : trace_xfs_da_unlink_back(args);
2042 3212 : save_info->back = drop_info->back;
2043 3212 : if (drop_info->back) {
2044 2051 : error = xfs_da3_node_read(args->trans, args->dp,
2045 2051 : be32_to_cpu(drop_info->back),
2046 : &bp, args->whichfork);
2047 2051 : if (error)
2048 : return error;
2049 2051 : fa = xfs_da3_header_check(bp, args->owner);
2050 2051 : 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 2051 : ASSERT(bp != NULL);
2057 2051 : tmp_info = bp->b_addr;
2058 2051 : ASSERT(tmp_info->magic == save_info->magic);
2059 4102 : ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
2060 2051 : tmp_info->forw = cpu_to_be32(save_blk->blkno);
2061 2051 : xfs_trans_log_buf(args->trans, bp, 0,
2062 : sizeof(*tmp_info) - 1);
2063 : }
2064 : } else {
2065 19468 : trace_xfs_da_unlink_forward(args);
2066 19468 : save_info->forw = drop_info->forw;
2067 19468 : if (drop_info->forw) {
2068 18787 : error = xfs_da3_node_read(args->trans, args->dp,
2069 18787 : be32_to_cpu(drop_info->forw),
2070 : &bp, args->whichfork);
2071 18787 : if (error)
2072 : return error;
2073 18787 : fa = xfs_da3_header_check(bp, args->owner);
2074 18787 : 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 18787 : ASSERT(bp != NULL);
2081 18787 : tmp_info = bp->b_addr;
2082 18787 : ASSERT(tmp_info->magic == save_info->magic);
2083 37574 : ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
2084 18787 : tmp_info->back = cpu_to_be32(save_blk->blkno);
2085 18787 : xfs_trans_log_buf(args->trans, bp, 0,
2086 : sizeof(*tmp_info) - 1);
2087 : }
2088 : }
2089 :
2090 22680 : xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
2091 22680 : 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 304004403 : 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 304004403 : struct xfs_da_state_blk *blk;
2111 304004403 : struct xfs_da_blkinfo *info;
2112 304004403 : struct xfs_da_args *args;
2113 304004403 : struct xfs_da_node_entry *btree;
2114 304004403 : struct xfs_da3_icnode_hdr nodehdr;
2115 304004403 : struct xfs_buf *bp;
2116 304004403 : xfs_failaddr_t fa;
2117 304004403 : xfs_dablk_t blkno = 0;
2118 304004403 : int level;
2119 304004403 : int error;
2120 304004403 : struct xfs_inode *dp = state->args->dp;
2121 :
2122 304004403 : 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 304004403 : args = state->args;
2130 304004403 : ASSERT(args != NULL);
2131 304004403 : ASSERT(path != NULL);
2132 304004403 : ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
2133 304004403 : level = (path->active-1) - 1; /* skip bottom layer in path */
2134 304904151 : for (; level >= 0; level--) {
2135 304539469 : blk = &path->blk[level];
2136 304539469 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
2137 304539469 : blk->bp->b_addr);
2138 :
2139 304539471 : if (forward && (blk->index < nodehdr.count - 1)) {
2140 303413497 : blk->index++;
2141 303413497 : blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
2142 : break;
2143 1125974 : } else if (!forward && (blk->index > 0)) {
2144 226226 : blk->index--;
2145 226226 : blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
2146 : break;
2147 : }
2148 : }
2149 304004405 : if (level < 0) {
2150 364682 : *result = -ENOENT; /* we're out of our tree */
2151 364682 : ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
2152 364682 : 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 607716050 : for (blk++, level++; level < path->active; blk++, level++) {
2160 : /*
2161 : * Read the next child block into a local buffer.
2162 : */
2163 304076328 : error = xfs_da3_node_read(args->trans, dp, blkno, &bp,
2164 : args->whichfork);
2165 304076327 : 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 304076327 : if (release)
2175 303615205 : xfs_trans_brelse(args->trans, blk->bp);
2176 304076327 : blk->blkno = blkno;
2177 304076327 : blk->bp = bp;
2178 :
2179 304076327 : info = blk->bp->b_addr;
2180 304076327 : 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 304076327 : switch (be16_to_cpu(info->magic)) {
2193 436674 : case XFS_DA_NODE_MAGIC:
2194 : case XFS_DA3_NODE_MAGIC:
2195 436674 : fa = xfs_da3_node_header_check(blk->bp, args->owner);
2196 436674 : if (fa) {
2197 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2198 0 : xfs_da_mark_sick(args);
2199 0 : return -EFSCORRUPTED;
2200 : }
2201 436674 : blk->magic = XFS_DA_NODE_MAGIC;
2202 436674 : xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
2203 436674 : bp->b_addr);
2204 436674 : btree = nodehdr.btree;
2205 436674 : blk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
2206 436674 : if (forward)
2207 436609 : blk->index = 0;
2208 : else
2209 65 : blk->index = nodehdr.count - 1;
2210 436674 : blkno = be32_to_cpu(btree[blk->index].before);
2211 : break;
2212 302293944 : case XFS_ATTR_LEAF_MAGIC:
2213 : case XFS_ATTR3_LEAF_MAGIC:
2214 302293944 : fa = xfs_attr3_leaf_header_check(blk->bp, args->owner);
2215 302293944 : if (fa) {
2216 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2217 0 : xfs_da_mark_sick(args);
2218 0 : return -EFSCORRUPTED;
2219 : }
2220 302293944 : blk->magic = XFS_ATTR_LEAF_MAGIC;
2221 302293944 : ASSERT(level == path->active-1);
2222 302293944 : blk->index = 0;
2223 302293944 : blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
2224 302293944 : break;
2225 1345709 : case XFS_DIR2_LEAFN_MAGIC:
2226 : case XFS_DIR3_LEAFN_MAGIC:
2227 1345709 : fa = xfs_dir3_leaf_header_check(blk->bp, args->owner);
2228 1345710 : if (fa) {
2229 0 : __xfs_buf_mark_corrupt(blk->bp, fa);
2230 0 : xfs_da_mark_sick(args);
2231 0 : return -EFSCORRUPTED;
2232 : }
2233 1345710 : blk->magic = XFS_DIR2_LEAFN_MAGIC;
2234 1345710 : ASSERT(level == path->active-1);
2235 1345710 : blk->index = 0;
2236 1345710 : blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
2237 : blk->bp, NULL);
2238 1345709 : break;
2239 0 : default:
2240 0 : ASSERT(0);
2241 0 : break;
2242 : }
2243 : }
2244 303639722 : *result = 0;
2245 303639722 : 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 3514221458 : xfs_da_hashname(const uint8_t *name, int namelen)
2260 : {
2261 3514221458 : xfs_dahash_t hash;
2262 :
2263 : /*
2264 : * Do four characters at a time as long as we can.
2265 : */
2266 7924427435 : for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
2267 4410205977 : hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
2268 4410205977 : (name[3] << 0) ^ rol32(hash, 7 * 4);
2269 :
2270 : /*
2271 : * Now do the rest of the characters.
2272 : */
2273 3514221458 : switch (namelen) {
2274 486115098 : case 3:
2275 486115098 : return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
2276 : rol32(hash, 7 * 3);
2277 877091554 : case 2:
2278 877091554 : return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
2279 1259064606 : case 1:
2280 1259064606 : return (name[0] << 0) ^ rol32(hash, 7 * 1);
2281 : default: /* case 0: */
2282 : return hash;
2283 : }
2284 : }
2285 :
2286 : enum xfs_dacmp
2287 1460864479 : xfs_da_compname(
2288 : struct xfs_da_args *args,
2289 : const unsigned char *name,
2290 : int len)
2291 : {
2292 1327039944 : return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
2293 2787904423 : XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
2294 : }
2295 :
2296 : int
2297 4750506 : xfs_da_grow_inode_int(
2298 : struct xfs_da_args *args,
2299 : xfs_fileoff_t *bno,
2300 : int count)
2301 : {
2302 4750506 : struct xfs_trans *tp = args->trans;
2303 4750506 : struct xfs_inode *dp = args->dp;
2304 4750506 : int w = args->whichfork;
2305 4750506 : xfs_rfsblock_t nblks = dp->i_nblocks;
2306 4750506 : struct xfs_bmbt_irec map, *mapp;
2307 4750506 : int nmap, error, got, i, mapi;
2308 :
2309 : /*
2310 : * Find a spot in the file space to put the new block.
2311 : */
2312 4750506 : error = xfs_bmap_first_unused(tp, dp, count, bno, w);
2313 4750518 : if (error)
2314 : return error;
2315 :
2316 : /*
2317 : * Try mapping it in one filesystem block.
2318 : */
2319 4750518 : nmap = 1;
2320 4750518 : error = xfs_bmapi_write(tp, dp, *bno, count,
2321 4750518 : xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
2322 : args->total, &map, &nmap);
2323 4749536 : if (error)
2324 : return error;
2325 :
2326 4749532 : ASSERT(nmap <= 1);
2327 4749532 : if (nmap == 1) {
2328 : mapp = ↦
2329 : mapi = 1;
2330 40 : } else if (nmap == 0 && count > 1) {
2331 40 : xfs_fileoff_t b;
2332 40 : int c;
2333 :
2334 : /*
2335 : * If we didn't get it and the block might work if fragmented,
2336 : * try without the CONTIG flag. Loop until we get it all.
2337 : */
2338 40 : mapp = kmem_alloc(sizeof(*mapp) * count, 0);
2339 80 : for (b = *bno, mapi = 0; b < *bno + count; ) {
2340 40 : c = (int)(*bno + count - b);
2341 40 : nmap = min(XFS_BMAP_MAX_NMAP, c);
2342 40 : error = xfs_bmapi_write(tp, dp, b, c,
2343 40 : xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
2344 40 : args->total, &mapp[mapi], &nmap);
2345 40 : if (error)
2346 0 : goto out_free_map;
2347 40 : if (nmap < 1)
2348 : break;
2349 40 : mapi += nmap;
2350 40 : b = mapp[mapi - 1].br_startoff +
2351 40 : mapp[mapi - 1].br_blockcount;
2352 : }
2353 : } else {
2354 : mapi = 0;
2355 : mapp = NULL;
2356 : }
2357 :
2358 : /*
2359 : * Count the blocks we got, make sure it matches the total.
2360 : */
2361 9499797 : for (i = 0, got = 0; i < mapi; i++)
2362 4750265 : got += mapp[i].br_blockcount;
2363 4749532 : if (got != count || mapp[0].br_startoff != *bno ||
2364 4749905 : mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
2365 4749905 : *bno + count) {
2366 0 : error = -ENOSPC;
2367 0 : goto out_free_map;
2368 : }
2369 :
2370 : /* account for newly allocated blocks in reserved blocks total */
2371 4749895 : args->total -= dp->i_nblocks - nblks;
2372 :
2373 4749532 : out_free_map:
2374 4749532 : if (mapp != &map)
2375 40 : kmem_free(mapp);
2376 : return error;
2377 : }
2378 :
2379 : /*
2380 : * Add a block to the btree ahead of the file.
2381 : * Return the new block number to the caller.
2382 : */
2383 : int
2384 4397486 : xfs_da_grow_inode(
2385 : struct xfs_da_args *args,
2386 : xfs_dablk_t *new_blkno)
2387 : {
2388 4397486 : xfs_fileoff_t bno;
2389 4397486 : int error;
2390 :
2391 4397486 : trace_xfs_da_grow_inode(args);
2392 :
2393 4397588 : bno = args->geo->leafblk;
2394 4397588 : error = xfs_da_grow_inode_int(args, &bno, args->geo->fsbcount);
2395 4397019 : if (!error)
2396 4397017 : *new_blkno = (xfs_dablk_t)bno;
2397 4397019 : 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 2271173 : xfs_da_shrink_inode(
2665 : struct xfs_da_args *args,
2666 : xfs_dablk_t dead_blkno,
2667 : struct xfs_buf *dead_buf)
2668 : {
2669 2271173 : struct xfs_inode *dp;
2670 2271173 : int done, error, w, count;
2671 2271173 : struct xfs_trans *tp;
2672 :
2673 2271173 : trace_xfs_da_shrink_inode(args);
2674 :
2675 2271207 : dp = args->dp;
2676 2271207 : w = args->whichfork;
2677 2271207 : tp = args->trans;
2678 2271207 : count = args->geo->fsbcount;
2679 2271207 : 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 2298328 : error = xfs_bunmapi(tp, dp, dead_blkno, count,
2685 : xfs_bmapi_aflag(w), 0, &done);
2686 2271159 : if (error == -ENOSPC) {
2687 0 : if (w != XFS_DATA_FORK)
2688 : break;
2689 0 : error = xfs_da3_swap_lastblock(args, &dead_blkno,
2690 : &dead_buf);
2691 0 : if (error)
2692 : break;
2693 : } else {
2694 : break;
2695 : }
2696 : }
2697 2271159 : xfs_trans_binval(tp, dead_buf);
2698 2271189 : return error;
2699 : }
2700 :
2701 : static int
2702 1848584285 : 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 1848584285 : struct xfs_mount *mp = dp->i_mount;
2711 1848584285 : int nfsb = xfs_dabuf_nfsb(mp, whichfork);
2712 1848584285 : struct xfs_bmbt_irec irec, *irecs = &irec;
2713 1848584285 : struct xfs_buf_map *map = *mapp;
2714 1848584285 : xfs_fileoff_t off = bno;
2715 1848584285 : int error = 0, nirecs, i;
2716 :
2717 1848584285 : if (nfsb > 1)
2718 647072 : irecs = kmem_zalloc(sizeof(irec) * nfsb, KM_NOFS);
2719 :
2720 1848966092 : nirecs = nfsb;
2721 2747679724 : error = xfs_bmapi_read(dp, bno, nfsb, irecs, &nirecs,
2722 : xfs_bmapi_aflag(whichfork));
2723 1849654439 : if (error)
2724 170 : 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 1849654269 : if (nirecs > 1) {
2731 68748 : map = kmem_zalloc(nirecs * sizeof(struct xfs_buf_map), KM_NOFS);
2732 68748 : if (!map) {
2733 0 : error = -ENOMEM;
2734 0 : goto out_free_irecs;
2735 : }
2736 68748 : *mapp = map;
2737 : }
2738 :
2739 3698854908 : for (i = 0; i < nirecs; i++) {
2740 1849471457 : if (irecs[i].br_startblock == HOLESTARTBLOCK ||
2741 : irecs[i].br_startblock == DELAYSTARTBLOCK)
2742 270818 : goto invalid_mapping;
2743 1849200639 : if (off != irecs[i].br_startoff)
2744 0 : goto invalid_mapping;
2745 :
2746 1849200639 : map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);
2747 1849200639 : map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);
2748 1849200639 : off += irecs[i].br_blockcount;
2749 : }
2750 :
2751 1849383451 : if (off != bno + nfsb)
2752 0 : goto invalid_mapping;
2753 :
2754 1849383451 : *nmaps = nirecs;
2755 1849654439 : out_free_irecs:
2756 1849654439 : if (irecs != &irec)
2757 647072 : kmem_free(irecs);
2758 1849654439 : return error;
2759 :
2760 270818 : invalid_mapping:
2761 : /* Caller ok with no mapping. */
2762 270818 : 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 270818 : *nmaps = 0;
2780 : }
2781 270818 : goto out_free_irecs;
2782 : }
2783 :
2784 : /*
2785 : * Get a buffer for the dir/attr block.
2786 : */
2787 : int
2788 4790041 : 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 4790041 : struct xfs_mount *mp = dp->i_mount;
2796 4790041 : struct xfs_buf *bp;
2797 4790041 : struct xfs_buf_map map, *mapp = ↦
2798 4790041 : int nmap = 1;
2799 4790041 : int error;
2800 :
2801 4790041 : *bpp = NULL;
2802 4790041 : error = xfs_dabuf_map(dp, bno, 0, whichfork, &mapp, &nmap);
2803 4789949 : if (error || nmap == 0)
2804 0 : goto out_free;
2805 :
2806 4789949 : error = xfs_trans_get_buf_map(tp, mp->m_ddev_targp, mapp, nmap, 0, &bp);
2807 4790337 : if (error)
2808 0 : goto out_free;
2809 :
2810 4790337 : *bpp = bp;
2811 :
2812 4790337 : out_free:
2813 4790337 : if (mapp != &map)
2814 42 : kmem_free(mapp);
2815 :
2816 4790337 : return error;
2817 : }
2818 :
2819 : /*
2820 : * Get a buffer for the dir/attr block, fill in the contents.
2821 : */
2822 : int
2823 1703829481 : 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 1703829481 : struct xfs_mount *mp = dp->i_mount;
2833 1703829481 : struct xfs_buf *bp;
2834 1703829481 : struct xfs_buf_map map, *mapp = ↦
2835 1703829481 : int nmap = 1;
2836 1703829481 : int error;
2837 :
2838 1703829481 : *bpp = NULL;
2839 1703829481 : error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
2840 1704619594 : if (error || !nmap)
2841 270978 : goto out_free;
2842 :
2843 1704348616 : error = xfs_trans_read_buf_map(mp, tp, mp->m_ddev_targp, mapp, nmap, 0,
2844 : &bp, ops);
2845 1704285811 : if (xfs_metadata_is_sick(error))
2846 246 : xfs_dirattr_mark_sick(dp, whichfork);
2847 1704285811 : if (error)
2848 17272 : goto out_free;
2849 :
2850 1704268539 : if (whichfork == XFS_ATTR_FORK)
2851 945924397 : xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
2852 : else
2853 758344142 : xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
2854 1704405418 : *bpp = bp;
2855 1704693668 : out_free:
2856 1704693668 : if (mapp != &map)
2857 68706 : kmem_free(mapp);
2858 :
2859 1704693668 : return error;
2860 : }
2861 :
2862 : /*
2863 : * Readahead the dir/attr block.
2864 : */
2865 : int
2866 140193097 : 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 140193097 : struct xfs_buf_map map;
2874 140193097 : struct xfs_buf_map *mapp;
2875 140193097 : int nmap;
2876 140193097 : int error;
2877 :
2878 140193097 : mapp = ↦
2879 140193097 : nmap = 1;
2880 140193097 : error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
2881 140217969 : if (error || !nmap)
2882 10 : goto out_free;
2883 :
2884 140217959 : xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap, ops);
2885 :
2886 140226281 : out_free:
2887 140226281 : if (mapp != &map)
2888 0 : kmem_free(mapp);
2889 :
2890 140226281 : return error;
2891 : }
|
