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