blob: 2385f8cd08ab9f1cdf19ad3a9a8473a5e4e34eb3 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Nathan Scott7b718762005-11-02 14:58:39 +11002 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
Dave Chinnerf5ea1102013-04-24 18:58:02 +10003 * Copyright (c) 2013 Red Hat, Inc.
Nathan Scott7b718762005-11-02 14:58:39 +11004 * All Rights Reserved.
Linus Torvalds1da177e2005-04-16 15:20:36 -07005 *
Nathan Scott7b718762005-11-02 14:58:39 +11006 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
Linus Torvalds1da177e2005-04-16 15:20:36 -07008 * published by the Free Software Foundation.
9 *
Nathan Scott7b718762005-11-02 14:58:39 +110010 * This program is distributed in the hope that it would be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
Linus Torvalds1da177e2005-04-16 15:20:36 -070014 *
Nathan Scott7b718762005-11-02 14:58:39 +110015 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Linus Torvalds1da177e2005-04-16 15:20:36 -070018 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070019#include "xfs.h"
Nathan Scotta844f452005-11-02 14:38:42 +110020#include "xfs_fs.h"
Dave Chinner70a9883c2013-10-23 10:36:05 +110021#include "xfs_shared.h"
Dave Chinner239880e2013-10-23 10:50:10 +110022#include "xfs_format.h"
23#include "xfs_log_format.h"
24#include "xfs_trans_resv.h"
Nathan Scotta844f452005-11-02 14:38:42 +110025#include "xfs_bit.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070026#include "xfs_mount.h"
Dave Chinner57062782013-10-15 09:17:51 +110027#include "xfs_da_format.h"
Nathan Scotta844f452005-11-02 14:38:42 +110028#include "xfs_da_btree.h"
Dave Chinner2b9ab5a2013-08-12 20:49:37 +100029#include "xfs_dir2.h"
Christoph Hellwig57926642011-07-13 13:43:48 +020030#include "xfs_dir2_priv.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070031#include "xfs_inode.h"
Dave Chinner239880e2013-10-23 10:50:10 +110032#include "xfs_trans.h"
Nathan Scotta844f452005-11-02 14:38:42 +110033#include "xfs_inode_item.h"
34#include "xfs_alloc.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070035#include "xfs_bmap.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070036#include "xfs_attr.h"
37#include "xfs_attr_leaf.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070038#include "xfs_error.h"
Christoph Hellwig0b1b2132009-12-14 23:14:59 +000039#include "xfs_trace.h"
Dave Chinnerf5ea1102013-04-24 18:58:02 +100040#include "xfs_cksum.h"
41#include "xfs_buf_item.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070042
43/*
44 * xfs_da_btree.c
45 *
46 * Routines to implement directories as Btrees of hashed names.
47 */
48
49/*========================================================================
50 * Function prototypes for the kernel.
51 *========================================================================*/
52
53/*
54 * Routines used for growing the Btree.
55 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +100056STATIC int xfs_da3_root_split(xfs_da_state_t *state,
Linus Torvalds1da177e2005-04-16 15:20:36 -070057 xfs_da_state_blk_t *existing_root,
58 xfs_da_state_blk_t *new_child);
Dave Chinnerf5ea1102013-04-24 18:58:02 +100059STATIC int xfs_da3_node_split(xfs_da_state_t *state,
Linus Torvalds1da177e2005-04-16 15:20:36 -070060 xfs_da_state_blk_t *existing_blk,
61 xfs_da_state_blk_t *split_blk,
62 xfs_da_state_blk_t *blk_to_add,
63 int treelevel,
64 int *result);
Dave Chinnerf5ea1102013-04-24 18:58:02 +100065STATIC void xfs_da3_node_rebalance(xfs_da_state_t *state,
Linus Torvalds1da177e2005-04-16 15:20:36 -070066 xfs_da_state_blk_t *node_blk_1,
67 xfs_da_state_blk_t *node_blk_2);
Dave Chinnerf5ea1102013-04-24 18:58:02 +100068STATIC void xfs_da3_node_add(xfs_da_state_t *state,
Linus Torvalds1da177e2005-04-16 15:20:36 -070069 xfs_da_state_blk_t *old_node_blk,
70 xfs_da_state_blk_t *new_node_blk);
71
72/*
73 * Routines used for shrinking the Btree.
74 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +100075STATIC int xfs_da3_root_join(xfs_da_state_t *state,
Linus Torvalds1da177e2005-04-16 15:20:36 -070076 xfs_da_state_blk_t *root_blk);
Dave Chinnerf5ea1102013-04-24 18:58:02 +100077STATIC int xfs_da3_node_toosmall(xfs_da_state_t *state, int *retval);
78STATIC void xfs_da3_node_remove(xfs_da_state_t *state,
Linus Torvalds1da177e2005-04-16 15:20:36 -070079 xfs_da_state_blk_t *drop_blk);
Dave Chinnerf5ea1102013-04-24 18:58:02 +100080STATIC void xfs_da3_node_unbalance(xfs_da_state_t *state,
Linus Torvalds1da177e2005-04-16 15:20:36 -070081 xfs_da_state_blk_t *src_node_blk,
82 xfs_da_state_blk_t *dst_node_blk);
83
84/*
85 * Utility routines.
86 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +100087STATIC int xfs_da3_blk_unlink(xfs_da_state_t *state,
Christoph Hellwigba0f32d2005-06-21 15:36:52 +100088 xfs_da_state_blk_t *drop_blk,
89 xfs_da_state_blk_t *save_blk);
Linus Torvalds1da177e2005-04-16 15:20:36 -070090
Dave Chinnerf5ea1102013-04-24 18:58:02 +100091
92kmem_zone_t *xfs_da_state_zone; /* anchor for state struct zone */
93
94/*
95 * Allocate a dir-state structure.
96 * We don't put them on the stack since they're large.
97 */
98xfs_da_state_t *
99xfs_da_state_alloc(void)
100{
101 return kmem_zone_zalloc(xfs_da_state_zone, KM_NOFS);
102}
103
104/*
105 * Kill the altpath contents of a da-state structure.
106 */
107STATIC void
108xfs_da_state_kill_altpath(xfs_da_state_t *state)
109{
110 int i;
111
112 for (i = 0; i < state->altpath.active; i++)
113 state->altpath.blk[i].bp = NULL;
114 state->altpath.active = 0;
115}
116
117/*
118 * Free a da-state structure.
119 */
120void
121xfs_da_state_free(xfs_da_state_t *state)
122{
123 xfs_da_state_kill_altpath(state);
124#ifdef DEBUG
125 memset((char *)state, 0, sizeof(*state));
126#endif /* DEBUG */
127 kmem_zone_free(xfs_da_state_zone, state);
128}
129
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000130static bool
131xfs_da3_node_verify(
Dave Chinnerd9392a42012-11-12 22:54:17 +1100132 struct xfs_buf *bp)
133{
134 struct xfs_mount *mp = bp->b_target->bt_mount;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000135 struct xfs_da_intnode *hdr = bp->b_addr;
136 struct xfs_da3_icnode_hdr ichdr;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100137 const struct xfs_dir_ops *ops;
Dave Chinnerd9392a42012-11-12 22:54:17 +1100138
Dave Chinner01ba43b2013-10-29 22:11:52 +1100139 ops = xfs_dir_get_ops(mp, NULL);
140
141 ops->node_hdr_from_disk(&ichdr, hdr);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000142
143 if (xfs_sb_version_hascrc(&mp->m_sb)) {
144 struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
145
146 if (ichdr.magic != XFS_DA3_NODE_MAGIC)
147 return false;
148
149 if (!uuid_equal(&hdr3->info.uuid, &mp->m_sb.sb_uuid))
150 return false;
151 if (be64_to_cpu(hdr3->info.blkno) != bp->b_bn)
152 return false;
153 } else {
154 if (ichdr.magic != XFS_DA_NODE_MAGIC)
155 return false;
Dave Chinnerd9392a42012-11-12 22:54:17 +1100156 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000157 if (ichdr.level == 0)
158 return false;
159 if (ichdr.level > XFS_DA_NODE_MAXDEPTH)
160 return false;
161 if (ichdr.count == 0)
162 return false;
Dave Chinnerd9392a42012-11-12 22:54:17 +1100163
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000164 /*
165 * we don't know if the node is for and attribute or directory tree,
166 * so only fail if the count is outside both bounds
167 */
Dave Chinner7ab610f2014-06-06 15:20:02 +1000168 if (ichdr.count > mp->m_dir_geo->node_ents &&
169 ichdr.count > mp->m_attr_geo->node_ents)
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000170 return false;
171
172 /* XXX: hash order check? */
173
174 return true;
Dave Chinnerd9392a42012-11-12 22:54:17 +1100175}
176
177static void
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000178xfs_da3_node_write_verify(
Dave Chinner612cfbf2012-11-14 17:52:32 +1100179 struct xfs_buf *bp)
180{
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000181 struct xfs_mount *mp = bp->b_target->bt_mount;
182 struct xfs_buf_log_item *bip = bp->b_fspriv;
183 struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
184
185 if (!xfs_da3_node_verify(bp)) {
Dave Chinner24513372014-06-25 14:58:08 +1000186 xfs_buf_ioerror(bp, -EFSCORRUPTED);
Eric Sandeence5028c2014-02-27 15:23:10 +1100187 xfs_verifier_error(bp);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000188 return;
189 }
190
191 if (!xfs_sb_version_hascrc(&mp->m_sb))
192 return;
193
194 if (bip)
195 hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
196
Eric Sandeenf1dbcd72014-02-27 15:18:23 +1100197 xfs_buf_update_cksum(bp, XFS_DA3_NODE_CRC_OFF);
Dave Chinner612cfbf2012-11-14 17:52:32 +1100198}
199
Dave Chinner1813dd62012-11-14 17:54:40 +1100200/*
201 * leaf/node format detection on trees is sketchy, so a node read can be done on
202 * leaf level blocks when detection identifies the tree as a node format tree
203 * incorrectly. In this case, we need to swap the verifier to match the correct
204 * format of the block being read.
205 */
Dave Chinner612cfbf2012-11-14 17:52:32 +1100206static void
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000207xfs_da3_node_read_verify(
Dave Chinnerd9392a42012-11-12 22:54:17 +1100208 struct xfs_buf *bp)
209{
Dave Chinnerd9392a42012-11-12 22:54:17 +1100210 struct xfs_da_blkinfo *info = bp->b_addr;
211
212 switch (be16_to_cpu(info->magic)) {
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000213 case XFS_DA3_NODE_MAGIC:
Eric Sandeence5028c2014-02-27 15:23:10 +1100214 if (!xfs_buf_verify_cksum(bp, XFS_DA3_NODE_CRC_OFF)) {
Dave Chinner24513372014-06-25 14:58:08 +1000215 xfs_buf_ioerror(bp, -EFSBADCRC);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000216 break;
Eric Sandeence5028c2014-02-27 15:23:10 +1100217 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000218 /* fall through */
Dave Chinnerd9392a42012-11-12 22:54:17 +1100219 case XFS_DA_NODE_MAGIC:
Eric Sandeence5028c2014-02-27 15:23:10 +1100220 if (!xfs_da3_node_verify(bp)) {
Dave Chinner24513372014-06-25 14:58:08 +1000221 xfs_buf_ioerror(bp, -EFSCORRUPTED);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000222 break;
Eric Sandeence5028c2014-02-27 15:23:10 +1100223 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000224 return;
Dave Chinnerd9392a42012-11-12 22:54:17 +1100225 case XFS_ATTR_LEAF_MAGIC:
Dave Chinner7ced60c2013-05-20 09:51:13 +1000226 case XFS_ATTR3_LEAF_MAGIC:
Dave Chinner517c2222013-04-24 18:58:55 +1000227 bp->b_ops = &xfs_attr3_leaf_buf_ops;
Dave Chinner1813dd62012-11-14 17:54:40 +1100228 bp->b_ops->verify_read(bp);
Dave Chinnerd9392a42012-11-12 22:54:17 +1100229 return;
230 case XFS_DIR2_LEAFN_MAGIC:
Dave Chinner24df33b2013-04-12 07:30:21 +1000231 case XFS_DIR3_LEAFN_MAGIC:
232 bp->b_ops = &xfs_dir3_leafn_buf_ops;
Dave Chinner1813dd62012-11-14 17:54:40 +1100233 bp->b_ops->verify_read(bp);
Dave Chinnerd9392a42012-11-12 22:54:17 +1100234 return;
235 default:
236 break;
237 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000238
239 /* corrupt block */
Eric Sandeence5028c2014-02-27 15:23:10 +1100240 xfs_verifier_error(bp);
Dave Chinnerd9392a42012-11-12 22:54:17 +1100241}
242
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000243const struct xfs_buf_ops xfs_da3_node_buf_ops = {
244 .verify_read = xfs_da3_node_read_verify,
245 .verify_write = xfs_da3_node_write_verify,
Dave Chinner1813dd62012-11-14 17:54:40 +1100246};
247
Dave Chinnerd9392a42012-11-12 22:54:17 +1100248int
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000249xfs_da3_node_read(
Dave Chinnerd9392a42012-11-12 22:54:17 +1100250 struct xfs_trans *tp,
251 struct xfs_inode *dp,
252 xfs_dablk_t bno,
253 xfs_daddr_t mappedbno,
254 struct xfs_buf **bpp,
255 int which_fork)
256{
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100257 int err;
258
259 err = xfs_da_read_buf(tp, dp, bno, mappedbno, bpp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000260 which_fork, &xfs_da3_node_buf_ops);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100261 if (!err && tp) {
262 struct xfs_da_blkinfo *info = (*bpp)->b_addr;
263 int type;
264
265 switch (be16_to_cpu(info->magic)) {
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100266 case XFS_DA_NODE_MAGIC:
Dave Chinnercab09a82013-04-30 21:39:36 +1000267 case XFS_DA3_NODE_MAGIC:
Dave Chinner61fe1352013-04-03 16:11:30 +1100268 type = XFS_BLFT_DA_NODE_BUF;
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100269 break;
270 case XFS_ATTR_LEAF_MAGIC:
271 case XFS_ATTR3_LEAF_MAGIC:
Dave Chinner61fe1352013-04-03 16:11:30 +1100272 type = XFS_BLFT_ATTR_LEAF_BUF;
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100273 break;
274 case XFS_DIR2_LEAFN_MAGIC:
275 case XFS_DIR3_LEAFN_MAGIC:
Dave Chinner61fe1352013-04-03 16:11:30 +1100276 type = XFS_BLFT_DIR_LEAFN_BUF;
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100277 break;
278 default:
279 type = 0;
280 ASSERT(0);
281 break;
282 }
283 xfs_trans_buf_set_type(tp, *bpp, type);
284 }
285 return err;
Dave Chinnerd9392a42012-11-12 22:54:17 +1100286}
287
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288/*========================================================================
289 * Routines used for growing the Btree.
290 *========================================================================*/
291
292/*
293 * Create the initial contents of an intermediate node.
294 */
295int
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000296xfs_da3_node_create(
297 struct xfs_da_args *args,
298 xfs_dablk_t blkno,
299 int level,
300 struct xfs_buf **bpp,
301 int whichfork)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302{
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000303 struct xfs_da_intnode *node;
304 struct xfs_trans *tp = args->trans;
305 struct xfs_mount *mp = tp->t_mountp;
306 struct xfs_da3_icnode_hdr ichdr = {0};
307 struct xfs_buf *bp;
308 int error;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100309 struct xfs_inode *dp = args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700310
Dave Chinner5a5881c2012-03-22 05:15:13 +0000311 trace_xfs_da_node_create(args);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000312 ASSERT(level <= XFS_DA_NODE_MAXDEPTH);
Dave Chinner5a5881c2012-03-22 05:15:13 +0000313
Dave Chinner01ba43b2013-10-29 22:11:52 +1100314 error = xfs_da_get_buf(tp, dp, blkno, -1, &bp, whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000316 return error;
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100317 bp->b_ops = &xfs_da3_node_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +1100318 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000319 node = bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700320
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000321 if (xfs_sb_version_hascrc(&mp->m_sb)) {
322 struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
323
324 ichdr.magic = XFS_DA3_NODE_MAGIC;
325 hdr3->info.blkno = cpu_to_be64(bp->b_bn);
326 hdr3->info.owner = cpu_to_be64(args->dp->i_ino);
327 uuid_copy(&hdr3->info.uuid, &mp->m_sb.sb_uuid);
328 } else {
329 ichdr.magic = XFS_DA_NODE_MAGIC;
330 }
331 ichdr.level = level;
332
Dave Chinner01ba43b2013-10-29 22:11:52 +1100333 dp->d_ops->node_hdr_to_disk(node, &ichdr);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000334 xfs_trans_log_buf(tp, bp,
Dave Chinner1c9a5b22013-10-30 09:15:02 +1100335 XFS_DA_LOGRANGE(node, &node->hdr, dp->d_ops->node_hdr_size));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336
337 *bpp = bp;
Eric Sandeend99831f2014-06-22 15:03:54 +1000338 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700339}
340
341/*
342 * Split a leaf node, rebalance, then possibly split
343 * intermediate nodes, rebalance, etc.
344 */
345int /* error */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000346xfs_da3_split(
347 struct xfs_da_state *state)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700348{
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000349 struct xfs_da_state_blk *oldblk;
350 struct xfs_da_state_blk *newblk;
351 struct xfs_da_state_blk *addblk;
352 struct xfs_da_intnode *node;
353 struct xfs_buf *bp;
354 int max;
Dave Chinner836a94a2013-08-12 20:49:44 +1000355 int action = 0;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000356 int error;
357 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358
Dave Chinner5a5881c2012-03-22 05:15:13 +0000359 trace_xfs_da_split(state->args);
360
Linus Torvalds1da177e2005-04-16 15:20:36 -0700361 /*
362 * Walk back up the tree splitting/inserting/adjusting as necessary.
363 * If we need to insert and there isn't room, split the node, then
364 * decide which fragment to insert the new block from below into.
365 * Note that we may split the root this way, but we need more fixup.
366 */
367 max = state->path.active - 1;
368 ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
369 ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
Nathan Scottf6c2d1f2006-06-20 13:04:51 +1000370 state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700371
372 addblk = &state->path.blk[max]; /* initial dummy value */
373 for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
374 oldblk = &state->path.blk[i];
375 newblk = &state->altpath.blk[i];
376
377 /*
378 * If a leaf node then
379 * Allocate a new leaf node, then rebalance across them.
380 * else if an intermediate node then
381 * We split on the last layer, must we split the node?
382 */
383 switch (oldblk->magic) {
384 case XFS_ATTR_LEAF_MAGIC:
Dave Chinner517c2222013-04-24 18:58:55 +1000385 error = xfs_attr3_leaf_split(state, oldblk, newblk);
Dave Chinner24513372014-06-25 14:58:08 +1000386 if ((error != 0) && (error != -ENOSPC)) {
Eric Sandeend99831f2014-06-22 15:03:54 +1000387 return error; /* GROT: attr is inconsistent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388 }
389 if (!error) {
390 addblk = newblk;
391 break;
392 }
393 /*
394 * Entry wouldn't fit, split the leaf again.
395 */
396 state->extravalid = 1;
397 if (state->inleaf) {
398 state->extraafter = 0; /* before newblk */
Dave Chinner5a5881c2012-03-22 05:15:13 +0000399 trace_xfs_attr_leaf_split_before(state->args);
Dave Chinner517c2222013-04-24 18:58:55 +1000400 error = xfs_attr3_leaf_split(state, oldblk,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700401 &state->extrablk);
402 } else {
403 state->extraafter = 1; /* after newblk */
Dave Chinner5a5881c2012-03-22 05:15:13 +0000404 trace_xfs_attr_leaf_split_after(state->args);
Dave Chinner517c2222013-04-24 18:58:55 +1000405 error = xfs_attr3_leaf_split(state, newblk,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700406 &state->extrablk);
407 }
408 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000409 return error; /* GROT: attr inconsistent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700410 addblk = newblk;
411 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700412 case XFS_DIR2_LEAFN_MAGIC:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700413 error = xfs_dir2_leafn_split(state, oldblk, newblk);
414 if (error)
415 return error;
416 addblk = newblk;
417 break;
418 case XFS_DA_NODE_MAGIC:
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000419 error = xfs_da3_node_split(state, oldblk, newblk, addblk,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700420 max - i, &action);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700421 addblk->bp = NULL;
422 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000423 return error; /* GROT: dir is inconsistent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700424 /*
425 * Record the newly split block for the next time thru?
426 */
427 if (action)
428 addblk = newblk;
429 else
430 addblk = NULL;
431 break;
432 }
433
434 /*
435 * Update the btree to show the new hashval for this child.
436 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000437 xfs_da3_fixhashpath(state, &state->path);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438 }
439 if (!addblk)
Eric Sandeend99831f2014-06-22 15:03:54 +1000440 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700441
442 /*
443 * Split the root node.
444 */
445 ASSERT(state->path.active == 0);
446 oldblk = &state->path.blk[0];
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000447 error = xfs_da3_root_split(state, oldblk, addblk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700448 if (error) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700449 addblk->bp = NULL;
Eric Sandeend99831f2014-06-22 15:03:54 +1000450 return error; /* GROT: dir is inconsistent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700451 }
452
453 /*
454 * Update pointers to the node which used to be block 0 and
455 * just got bumped because of the addition of a new root node.
456 * There might be three blocks involved if a double split occurred,
457 * and the original block 0 could be at any position in the list.
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000458 *
459 * Note: the magic numbers and sibling pointers are in the same
460 * physical place for both v2 and v3 headers (by design). Hence it
461 * doesn't matter which version of the xfs_da_intnode structure we use
462 * here as the result will be the same using either structure.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700463 */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000464 node = oldblk->bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465 if (node->hdr.info.forw) {
Nathan Scott89da0542006-03-17 17:28:40 +1100466 if (be32_to_cpu(node->hdr.info.forw) == addblk->blkno) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467 bp = addblk->bp;
468 } else {
469 ASSERT(state->extravalid);
470 bp = state->extrablk.bp;
471 }
Dave Chinner1d9025e2012-06-22 18:50:14 +1000472 node = bp->b_addr;
Nathan Scott89da0542006-03-17 17:28:40 +1100473 node->hdr.info.back = cpu_to_be32(oldblk->blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000474 xfs_trans_log_buf(state->args->trans, bp,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700475 XFS_DA_LOGRANGE(node, &node->hdr.info,
476 sizeof(node->hdr.info)));
477 }
Dave Chinner1d9025e2012-06-22 18:50:14 +1000478 node = oldblk->bp->b_addr;
Nathan Scott89da0542006-03-17 17:28:40 +1100479 if (node->hdr.info.back) {
480 if (be32_to_cpu(node->hdr.info.back) == addblk->blkno) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700481 bp = addblk->bp;
482 } else {
483 ASSERT(state->extravalid);
484 bp = state->extrablk.bp;
485 }
Dave Chinner1d9025e2012-06-22 18:50:14 +1000486 node = bp->b_addr;
Nathan Scott89da0542006-03-17 17:28:40 +1100487 node->hdr.info.forw = cpu_to_be32(oldblk->blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000488 xfs_trans_log_buf(state->args->trans, bp,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700489 XFS_DA_LOGRANGE(node, &node->hdr.info,
490 sizeof(node->hdr.info)));
491 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492 addblk->bp = NULL;
Eric Sandeend99831f2014-06-22 15:03:54 +1000493 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700494}
495
496/*
497 * Split the root. We have to create a new root and point to the two
498 * parts (the split old root) that we just created. Copy block zero to
499 * the EOF, extending the inode in process.
500 */
501STATIC int /* error */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000502xfs_da3_root_split(
503 struct xfs_da_state *state,
504 struct xfs_da_state_blk *blk1,
505 struct xfs_da_state_blk *blk2)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700506{
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000507 struct xfs_da_intnode *node;
508 struct xfs_da_intnode *oldroot;
509 struct xfs_da_node_entry *btree;
510 struct xfs_da3_icnode_hdr nodehdr;
511 struct xfs_da_args *args;
512 struct xfs_buf *bp;
513 struct xfs_inode *dp;
514 struct xfs_trans *tp;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000515 struct xfs_dir2_leaf *leaf;
516 xfs_dablk_t blkno;
517 int level;
518 int error;
519 int size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700520
Dave Chinner5a5881c2012-03-22 05:15:13 +0000521 trace_xfs_da_root_split(state->args);
522
Linus Torvalds1da177e2005-04-16 15:20:36 -0700523 /*
524 * Copy the existing (incorrect) block from the root node position
525 * to a free space somewhere.
526 */
527 args = state->args;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700528 error = xfs_da_grow_inode(args, &blkno);
529 if (error)
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000530 return error;
531
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532 dp = args->dp;
533 tp = args->trans;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700534 error = xfs_da_get_buf(tp, dp, blkno, -1, &bp, args->whichfork);
535 if (error)
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000536 return error;
Dave Chinner1d9025e2012-06-22 18:50:14 +1000537 node = bp->b_addr;
538 oldroot = blk1->bp->b_addr;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000539 if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
540 oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC)) {
Fabian Frederick29916df2015-03-25 14:55:25 +1100541 struct xfs_da3_icnode_hdr icnodehdr;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000542
Fabian Frederick29916df2015-03-25 14:55:25 +1100543 dp->d_ops->node_hdr_from_disk(&icnodehdr, oldroot);
Dave Chinner4bceb182013-10-29 22:11:51 +1100544 btree = dp->d_ops->node_tree_p(oldroot);
Fabian Frederick29916df2015-03-25 14:55:25 +1100545 size = (int)((char *)&btree[icnodehdr.count] - (char *)oldroot);
546 level = icnodehdr.level;
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100547
548 /*
549 * we are about to copy oldroot to bp, so set up the type
550 * of bp while we know exactly what it will be.
551 */
Dave Chinner61fe1352013-04-03 16:11:30 +1100552 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553 } else {
Dave Chinner24df33b2013-04-12 07:30:21 +1000554 struct xfs_dir3_icleaf_hdr leafhdr;
555 struct xfs_dir2_leaf_entry *ents;
556
Linus Torvalds1da177e2005-04-16 15:20:36 -0700557 leaf = (xfs_dir2_leaf_t *)oldroot;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100558 dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
Dave Chinner41419562013-10-29 22:11:50 +1100559 ents = dp->d_ops->leaf_ents_p(leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +1000560
561 ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
562 leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
563 size = (int)((char *)&ents[leafhdr.count] - (char *)leaf);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000564 level = 0;
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100565
566 /*
567 * we are about to copy oldroot to bp, so set up the type
568 * of bp while we know exactly what it will be.
569 */
Dave Chinner61fe1352013-04-03 16:11:30 +1100570 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000572
573 /*
574 * we can copy most of the information in the node from one block to
575 * another, but for CRC enabled headers we have to make sure that the
576 * block specific identifiers are kept intact. We update the buffer
577 * directly for this.
578 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579 memcpy(node, oldroot, size);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000580 if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
581 oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
582 struct xfs_da3_intnode *node3 = (struct xfs_da3_intnode *)node;
583
584 node3->hdr.info.blkno = cpu_to_be64(bp->b_bn);
585 }
Dave Chinner1d9025e2012-06-22 18:50:14 +1000586 xfs_trans_log_buf(tp, bp, 0, size - 1);
Dave Chinnerb0f539d2012-11-14 17:53:49 +1100587
Dave Chinner1813dd62012-11-14 17:54:40 +1100588 bp->b_ops = blk1->bp->b_ops;
Dave Chinner0a4edc82013-09-02 10:32:01 +1000589 xfs_trans_buf_copy_type(bp, blk1->bp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700590 blk1->bp = bp;
591 blk1->blkno = blkno;
592
593 /*
594 * Set up the new root node.
595 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000596 error = xfs_da3_node_create(args,
Dave Chinner7dda6e82014-06-06 15:11:18 +1000597 (args->whichfork == XFS_DATA_FORK) ? args->geo->leafblk : 0,
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000598 level + 1, &bp, args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700599 if (error)
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000600 return error;
601
Dave Chinner1d9025e2012-06-22 18:50:14 +1000602 node = bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100603 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinner4bceb182013-10-29 22:11:51 +1100604 btree = dp->d_ops->node_tree_p(node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000605 btree[0].hashval = cpu_to_be32(blk1->hashval);
606 btree[0].before = cpu_to_be32(blk1->blkno);
607 btree[1].hashval = cpu_to_be32(blk2->hashval);
608 btree[1].before = cpu_to_be32(blk2->blkno);
609 nodehdr.count = 2;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100610 dp->d_ops->node_hdr_to_disk(node, &nodehdr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700611
612#ifdef DEBUG
Dave Chinner24df33b2013-04-12 07:30:21 +1000613 if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
614 oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
Dave Chinner7dda6e82014-06-06 15:11:18 +1000615 ASSERT(blk1->blkno >= args->geo->leafblk &&
616 blk1->blkno < args->geo->freeblk);
617 ASSERT(blk2->blkno >= args->geo->leafblk &&
618 blk2->blkno < args->geo->freeblk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619 }
620#endif
621
622 /* Header is already logged by xfs_da_node_create */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000623 xfs_trans_log_buf(tp, bp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000624 XFS_DA_LOGRANGE(node, btree, sizeof(xfs_da_node_entry_t) * 2));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700625
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000626 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627}
628
629/*
630 * Split the node, rebalance, then add the new entry.
631 */
632STATIC int /* error */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000633xfs_da3_node_split(
634 struct xfs_da_state *state,
635 struct xfs_da_state_blk *oldblk,
636 struct xfs_da_state_blk *newblk,
637 struct xfs_da_state_blk *addblk,
638 int treelevel,
639 int *result)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640{
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000641 struct xfs_da_intnode *node;
642 struct xfs_da3_icnode_hdr nodehdr;
643 xfs_dablk_t blkno;
644 int newcount;
645 int error;
646 int useextra;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100647 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648
Dave Chinner5a5881c2012-03-22 05:15:13 +0000649 trace_xfs_da_node_split(state->args);
650
Dave Chinner1d9025e2012-06-22 18:50:14 +1000651 node = oldblk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100652 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653
654 /*
Nathan Scottf6c2d1f2006-06-20 13:04:51 +1000655 * With V2 dirs the extra block is data or freespace.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656 */
Nathan Scottf6c2d1f2006-06-20 13:04:51 +1000657 useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700658 newcount = 1 + useextra;
659 /*
660 * Do we have to split the node?
661 */
Dave Chinnerb2a21e72014-06-06 15:22:04 +1000662 if (nodehdr.count + newcount > state->args->geo->node_ents) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663 /*
664 * Allocate a new node, add to the doubly linked chain of
665 * nodes, then move some of our excess entries into it.
666 */
667 error = xfs_da_grow_inode(state->args, &blkno);
668 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000669 return error; /* GROT: dir is inconsistent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000671 error = xfs_da3_node_create(state->args, blkno, treelevel,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672 &newblk->bp, state->args->whichfork);
673 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000674 return error; /* GROT: dir is inconsistent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675 newblk->blkno = blkno;
676 newblk->magic = XFS_DA_NODE_MAGIC;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000677 xfs_da3_node_rebalance(state, oldblk, newblk);
678 error = xfs_da3_blk_link(state, oldblk, newblk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700679 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000680 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681 *result = 1;
682 } else {
683 *result = 0;
684 }
685
686 /*
687 * Insert the new entry(s) into the correct block
688 * (updating last hashval in the process).
689 *
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000690 * xfs_da3_node_add() inserts BEFORE the given index,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691 * and as a result of using node_lookup_int() we always
692 * point to a valid entry (not after one), but a split
693 * operation always results in a new block whose hashvals
694 * FOLLOW the current block.
695 *
696 * If we had double-split op below us, then add the extra block too.
697 */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000698 node = oldblk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100699 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000700 if (oldblk->index <= nodehdr.count) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700701 oldblk->index++;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000702 xfs_da3_node_add(state, oldblk, addblk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700703 if (useextra) {
704 if (state->extraafter)
705 oldblk->index++;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000706 xfs_da3_node_add(state, oldblk, &state->extrablk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700707 state->extravalid = 0;
708 }
709 } else {
710 newblk->index++;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000711 xfs_da3_node_add(state, newblk, addblk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700712 if (useextra) {
713 if (state->extraafter)
714 newblk->index++;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000715 xfs_da3_node_add(state, newblk, &state->extrablk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700716 state->extravalid = 0;
717 }
718 }
719
Eric Sandeend99831f2014-06-22 15:03:54 +1000720 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700721}
722
723/*
724 * Balance the btree elements between two intermediate nodes,
725 * usually one full and one empty.
726 *
727 * NOTE: if blk2 is empty, then it will get the upper half of blk1.
728 */
729STATIC void
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000730xfs_da3_node_rebalance(
731 struct xfs_da_state *state,
732 struct xfs_da_state_blk *blk1,
733 struct xfs_da_state_blk *blk2)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700734{
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000735 struct xfs_da_intnode *node1;
736 struct xfs_da_intnode *node2;
737 struct xfs_da_intnode *tmpnode;
738 struct xfs_da_node_entry *btree1;
739 struct xfs_da_node_entry *btree2;
740 struct xfs_da_node_entry *btree_s;
741 struct xfs_da_node_entry *btree_d;
742 struct xfs_da3_icnode_hdr nodehdr1;
743 struct xfs_da3_icnode_hdr nodehdr2;
744 struct xfs_trans *tp;
745 int count;
746 int tmp;
747 int swap = 0;
Dave Chinner4bceb182013-10-29 22:11:51 +1100748 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749
Dave Chinner5a5881c2012-03-22 05:15:13 +0000750 trace_xfs_da_node_rebalance(state->args);
751
Dave Chinner1d9025e2012-06-22 18:50:14 +1000752 node1 = blk1->bp->b_addr;
753 node2 = blk2->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100754 dp->d_ops->node_hdr_from_disk(&nodehdr1, node1);
755 dp->d_ops->node_hdr_from_disk(&nodehdr2, node2);
Dave Chinner4bceb182013-10-29 22:11:51 +1100756 btree1 = dp->d_ops->node_tree_p(node1);
757 btree2 = dp->d_ops->node_tree_p(node2);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000758
Linus Torvalds1da177e2005-04-16 15:20:36 -0700759 /*
760 * Figure out how many entries need to move, and in which direction.
761 * Swap the nodes around if that makes it simpler.
762 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000763 if (nodehdr1.count > 0 && nodehdr2.count > 0 &&
764 ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
765 (be32_to_cpu(btree2[nodehdr2.count - 1].hashval) <
766 be32_to_cpu(btree1[nodehdr1.count - 1].hashval)))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700767 tmpnode = node1;
768 node1 = node2;
769 node2 = tmpnode;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100770 dp->d_ops->node_hdr_from_disk(&nodehdr1, node1);
771 dp->d_ops->node_hdr_from_disk(&nodehdr2, node2);
Dave Chinner4bceb182013-10-29 22:11:51 +1100772 btree1 = dp->d_ops->node_tree_p(node1);
773 btree2 = dp->d_ops->node_tree_p(node2);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000774 swap = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700775 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000776
777 count = (nodehdr1.count - nodehdr2.count) / 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700778 if (count == 0)
779 return;
780 tp = state->args->trans;
781 /*
782 * Two cases: high-to-low and low-to-high.
783 */
784 if (count > 0) {
785 /*
786 * Move elements in node2 up to make a hole.
787 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000788 tmp = nodehdr2.count;
789 if (tmp > 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700790 tmp *= (uint)sizeof(xfs_da_node_entry_t);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000791 btree_s = &btree2[0];
792 btree_d = &btree2[count];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700793 memmove(btree_d, btree_s, tmp);
794 }
795
796 /*
797 * Move the req'd B-tree elements from high in node1 to
798 * low in node2.
799 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000800 nodehdr2.count += count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801 tmp = count * (uint)sizeof(xfs_da_node_entry_t);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000802 btree_s = &btree1[nodehdr1.count - count];
803 btree_d = &btree2[0];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700804 memcpy(btree_d, btree_s, tmp);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000805 nodehdr1.count -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700806 } else {
807 /*
808 * Move the req'd B-tree elements from low in node2 to
809 * high in node1.
810 */
811 count = -count;
812 tmp = count * (uint)sizeof(xfs_da_node_entry_t);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000813 btree_s = &btree2[0];
814 btree_d = &btree1[nodehdr1.count];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700815 memcpy(btree_d, btree_s, tmp);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000816 nodehdr1.count += count;
817
Dave Chinner1d9025e2012-06-22 18:50:14 +1000818 xfs_trans_log_buf(tp, blk1->bp,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819 XFS_DA_LOGRANGE(node1, btree_d, tmp));
820
821 /*
822 * Move elements in node2 down to fill the hole.
823 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000824 tmp = nodehdr2.count - count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700825 tmp *= (uint)sizeof(xfs_da_node_entry_t);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000826 btree_s = &btree2[count];
827 btree_d = &btree2[0];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700828 memmove(btree_d, btree_s, tmp);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000829 nodehdr2.count -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700830 }
831
832 /*
833 * Log header of node 1 and all current bits of node 2.
834 */
Dave Chinner01ba43b2013-10-29 22:11:52 +1100835 dp->d_ops->node_hdr_to_disk(node1, &nodehdr1);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000836 xfs_trans_log_buf(tp, blk1->bp,
Dave Chinner1c9a5b22013-10-30 09:15:02 +1100837 XFS_DA_LOGRANGE(node1, &node1->hdr, dp->d_ops->node_hdr_size));
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000838
Dave Chinner01ba43b2013-10-29 22:11:52 +1100839 dp->d_ops->node_hdr_to_disk(node2, &nodehdr2);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000840 xfs_trans_log_buf(tp, blk2->bp,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700841 XFS_DA_LOGRANGE(node2, &node2->hdr,
Dave Chinner1c9a5b22013-10-30 09:15:02 +1100842 dp->d_ops->node_hdr_size +
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000843 (sizeof(btree2[0]) * nodehdr2.count)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844
845 /*
846 * Record the last hashval from each block for upward propagation.
847 * (note: don't use the swapped node pointers)
848 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000849 if (swap) {
850 node1 = blk1->bp->b_addr;
851 node2 = blk2->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100852 dp->d_ops->node_hdr_from_disk(&nodehdr1, node1);
853 dp->d_ops->node_hdr_from_disk(&nodehdr2, node2);
Dave Chinner4bceb182013-10-29 22:11:51 +1100854 btree1 = dp->d_ops->node_tree_p(node1);
855 btree2 = dp->d_ops->node_tree_p(node2);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000856 }
857 blk1->hashval = be32_to_cpu(btree1[nodehdr1.count - 1].hashval);
858 blk2->hashval = be32_to_cpu(btree2[nodehdr2.count - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700859
860 /*
861 * Adjust the expected index for insertion.
862 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000863 if (blk1->index >= nodehdr1.count) {
864 blk2->index = blk1->index - nodehdr1.count;
865 blk1->index = nodehdr1.count + 1; /* make it invalid */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700866 }
867}
868
869/*
870 * Add a new entry to an intermediate node.
871 */
872STATIC void
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000873xfs_da3_node_add(
874 struct xfs_da_state *state,
875 struct xfs_da_state_blk *oldblk,
876 struct xfs_da_state_blk *newblk)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700877{
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000878 struct xfs_da_intnode *node;
879 struct xfs_da3_icnode_hdr nodehdr;
880 struct xfs_da_node_entry *btree;
881 int tmp;
Dave Chinner4bceb182013-10-29 22:11:51 +1100882 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700883
Dave Chinner5a5881c2012-03-22 05:15:13 +0000884 trace_xfs_da_node_add(state->args);
885
Dave Chinner1d9025e2012-06-22 18:50:14 +1000886 node = oldblk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100887 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinner4bceb182013-10-29 22:11:51 +1100888 btree = dp->d_ops->node_tree_p(node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000889
890 ASSERT(oldblk->index >= 0 && oldblk->index <= nodehdr.count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700891 ASSERT(newblk->blkno != 0);
Nathan Scottf6c2d1f2006-06-20 13:04:51 +1000892 if (state->args->whichfork == XFS_DATA_FORK)
Dave Chinner7dda6e82014-06-06 15:11:18 +1000893 ASSERT(newblk->blkno >= state->args->geo->leafblk &&
894 newblk->blkno < state->args->geo->freeblk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895
896 /*
897 * We may need to make some room before we insert the new node.
898 */
899 tmp = 0;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000900 if (oldblk->index < nodehdr.count) {
901 tmp = (nodehdr.count - oldblk->index) * (uint)sizeof(*btree);
902 memmove(&btree[oldblk->index + 1], &btree[oldblk->index], tmp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700903 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000904 btree[oldblk->index].hashval = cpu_to_be32(newblk->hashval);
905 btree[oldblk->index].before = cpu_to_be32(newblk->blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000906 xfs_trans_log_buf(state->args->trans, oldblk->bp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000907 XFS_DA_LOGRANGE(node, &btree[oldblk->index],
908 tmp + sizeof(*btree)));
909
910 nodehdr.count += 1;
Dave Chinner01ba43b2013-10-29 22:11:52 +1100911 dp->d_ops->node_hdr_to_disk(node, &nodehdr);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000912 xfs_trans_log_buf(state->args->trans, oldblk->bp,
Dave Chinner1c9a5b22013-10-30 09:15:02 +1100913 XFS_DA_LOGRANGE(node, &node->hdr, dp->d_ops->node_hdr_size));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700914
915 /*
916 * Copy the last hash value from the oldblk to propagate upwards.
917 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000918 oldblk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700919}
920
921/*========================================================================
922 * Routines used for shrinking the Btree.
923 *========================================================================*/
924
925/*
926 * Deallocate an empty leaf node, remove it from its parent,
927 * possibly deallocating that block, etc...
928 */
929int
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000930xfs_da3_join(
931 struct xfs_da_state *state)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700932{
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000933 struct xfs_da_state_blk *drop_blk;
934 struct xfs_da_state_blk *save_blk;
935 int action = 0;
936 int error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700937
Dave Chinner5a5881c2012-03-22 05:15:13 +0000938 trace_xfs_da_join(state->args);
939
Linus Torvalds1da177e2005-04-16 15:20:36 -0700940 drop_blk = &state->path.blk[ state->path.active-1 ];
941 save_blk = &state->altpath.blk[ state->path.active-1 ];
942 ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
943 ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC ||
Nathan Scottf6c2d1f2006-06-20 13:04:51 +1000944 drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945
946 /*
947 * Walk back up the tree joining/deallocating as necessary.
948 * When we stop dropping blocks, break out.
949 */
950 for ( ; state->path.active >= 2; drop_blk--, save_blk--,
951 state->path.active--) {
952 /*
953 * See if we can combine the block with a neighbor.
954 * (action == 0) => no options, just leave
955 * (action == 1) => coalesce, then unlink
956 * (action == 2) => block empty, unlink it
957 */
958 switch (drop_blk->magic) {
959 case XFS_ATTR_LEAF_MAGIC:
Dave Chinner517c2222013-04-24 18:58:55 +1000960 error = xfs_attr3_leaf_toosmall(state, &action);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700961 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000962 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700963 if (action == 0)
Eric Sandeend99831f2014-06-22 15:03:54 +1000964 return 0;
Dave Chinner517c2222013-04-24 18:58:55 +1000965 xfs_attr3_leaf_unbalance(state, drop_blk, save_blk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700966 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967 case XFS_DIR2_LEAFN_MAGIC:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968 error = xfs_dir2_leafn_toosmall(state, &action);
969 if (error)
970 return error;
971 if (action == 0)
972 return 0;
973 xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
974 break;
975 case XFS_DA_NODE_MAGIC:
976 /*
977 * Remove the offending node, fixup hashvals,
978 * check for a toosmall neighbor.
979 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000980 xfs_da3_node_remove(state, drop_blk);
981 xfs_da3_fixhashpath(state, &state->path);
982 error = xfs_da3_node_toosmall(state, &action);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700983 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000984 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700985 if (action == 0)
986 return 0;
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000987 xfs_da3_node_unbalance(state, drop_blk, save_blk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700988 break;
989 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +1000990 xfs_da3_fixhashpath(state, &state->altpath);
991 error = xfs_da3_blk_unlink(state, drop_blk, save_blk);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700992 xfs_da_state_kill_altpath(state);
993 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000994 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700995 error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
996 drop_blk->bp);
997 drop_blk->bp = NULL;
998 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +1000999 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001000 }
1001 /*
1002 * We joined all the way to the top. If it turns out that
1003 * we only have one entry in the root, make the child block
1004 * the new root.
1005 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001006 xfs_da3_node_remove(state, drop_blk);
1007 xfs_da3_fixhashpath(state, &state->path);
1008 error = xfs_da3_root_join(state, &state->path.blk[0]);
Eric Sandeend99831f2014-06-22 15:03:54 +10001009 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001010}
1011
Alex Elder1c4f3322011-07-18 18:14:09 +00001012#ifdef DEBUG
1013static void
1014xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
1015{
1016 __be16 magic = blkinfo->magic;
1017
1018 if (level == 1) {
1019 ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
Dave Chinner24df33b2013-04-12 07:30:21 +10001020 magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
Dave Chinner517c2222013-04-24 18:58:55 +10001021 magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
1022 magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001023 } else {
1024 ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
1025 magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
1026 }
Alex Elder1c4f3322011-07-18 18:14:09 +00001027 ASSERT(!blkinfo->forw);
1028 ASSERT(!blkinfo->back);
1029}
1030#else /* !DEBUG */
1031#define xfs_da_blkinfo_onlychild_validate(blkinfo, level)
1032#endif /* !DEBUG */
1033
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034/*
1035 * We have only one entry in the root. Copy the only remaining child of
1036 * the old root to block 0 as the new root node.
1037 */
1038STATIC int
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001039xfs_da3_root_join(
1040 struct xfs_da_state *state,
1041 struct xfs_da_state_blk *root_blk)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001042{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001043 struct xfs_da_intnode *oldroot;
1044 struct xfs_da_args *args;
1045 xfs_dablk_t child;
1046 struct xfs_buf *bp;
1047 struct xfs_da3_icnode_hdr oldroothdr;
1048 struct xfs_da_node_entry *btree;
1049 int error;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001050 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051
Dave Chinner5a5881c2012-03-22 05:15:13 +00001052 trace_xfs_da_root_join(state->args);
1053
Linus Torvalds1da177e2005-04-16 15:20:36 -07001054 ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001055
1056 args = state->args;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001057 oldroot = root_blk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001058 dp->d_ops->node_hdr_from_disk(&oldroothdr, oldroot);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001059 ASSERT(oldroothdr.forw == 0);
1060 ASSERT(oldroothdr.back == 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001061
1062 /*
1063 * If the root has more than one child, then don't do anything.
1064 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001065 if (oldroothdr.count > 1)
1066 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001067
1068 /*
1069 * Read in the (only) child block, then copy those bytes into
1070 * the root block's buffer and free the original child block.
1071 */
Dave Chinner01ba43b2013-10-29 22:11:52 +11001072 btree = dp->d_ops->node_tree_p(oldroot);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001073 child = be32_to_cpu(btree[0].before);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001074 ASSERT(child != 0);
Dave Chinner01ba43b2013-10-29 22:11:52 +11001075 error = xfs_da3_node_read(args->trans, dp, child, -1, &bp,
Dave Chinnerd9392a42012-11-12 22:54:17 +11001076 args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001077 if (error)
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001078 return error;
1079 xfs_da_blkinfo_onlychild_validate(bp->b_addr, oldroothdr.level);
Alex Elder1c4f3322011-07-18 18:14:09 +00001080
Dave Chinner612cfbf2012-11-14 17:52:32 +11001081 /*
1082 * This could be copying a leaf back into the root block in the case of
1083 * there only being a single leaf block left in the tree. Hence we have
Dave Chinner1813dd62012-11-14 17:54:40 +11001084 * to update the b_ops pointer as well to match the buffer type change
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001085 * that could occur. For dir3 blocks we also need to update the block
1086 * number in the buffer header.
Dave Chinner612cfbf2012-11-14 17:52:32 +11001087 */
Dave Chinnerb2a21e72014-06-06 15:22:04 +10001088 memcpy(root_blk->bp->b_addr, bp->b_addr, args->geo->blksize);
Dave Chinner1813dd62012-11-14 17:54:40 +11001089 root_blk->bp->b_ops = bp->b_ops;
Dave Chinnerd75afeb2013-04-03 16:11:29 +11001090 xfs_trans_buf_copy_type(root_blk->bp, bp);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001091 if (oldroothdr.magic == XFS_DA3_NODE_MAGIC) {
1092 struct xfs_da3_blkinfo *da3 = root_blk->bp->b_addr;
1093 da3->blkno = cpu_to_be64(root_blk->bp->b_bn);
1094 }
Dave Chinnerb2a21e72014-06-06 15:22:04 +10001095 xfs_trans_log_buf(args->trans, root_blk->bp, 0,
1096 args->geo->blksize - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001097 error = xfs_da_shrink_inode(args, child, bp);
Eric Sandeend99831f2014-06-22 15:03:54 +10001098 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001099}
1100
1101/*
1102 * Check a node block and its neighbors to see if the block should be
1103 * collapsed into one or the other neighbor. Always keep the block
1104 * with the smaller block number.
1105 * If the current block is over 50% full, don't try to join it, return 0.
1106 * If the block is empty, fill in the state structure and return 2.
1107 * If it can be collapsed, fill in the state structure and return 1.
1108 * If nothing can be done, return 0.
1109 */
1110STATIC int
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001111xfs_da3_node_toosmall(
1112 struct xfs_da_state *state,
1113 int *action)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001114{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001115 struct xfs_da_intnode *node;
1116 struct xfs_da_state_blk *blk;
1117 struct xfs_da_blkinfo *info;
1118 xfs_dablk_t blkno;
1119 struct xfs_buf *bp;
1120 struct xfs_da3_icnode_hdr nodehdr;
1121 int count;
1122 int forward;
1123 int error;
1124 int retval;
1125 int i;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001126 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001127
Dave Chinneree732592012-11-12 22:53:53 +11001128 trace_xfs_da_node_toosmall(state->args);
1129
Linus Torvalds1da177e2005-04-16 15:20:36 -07001130 /*
1131 * Check for the degenerate case of the block being over 50% full.
1132 * If so, it's not worth even looking to see if we might be able
1133 * to coalesce with a sibling.
1134 */
1135 blk = &state->path.blk[ state->path.active-1 ];
Dave Chinner1d9025e2012-06-22 18:50:14 +10001136 info = blk->bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001137 node = (xfs_da_intnode_t *)info;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001138 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinnerb2a21e72014-06-06 15:22:04 +10001139 if (nodehdr.count > (state->args->geo->node_ents >> 1)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001140 *action = 0; /* blk over 50%, don't try to join */
Eric Sandeend99831f2014-06-22 15:03:54 +10001141 return 0; /* blk over 50%, don't try to join */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001142 }
1143
1144 /*
1145 * Check for the degenerate case of the block being empty.
1146 * If the block is empty, we'll simply delete it, no need to
Nathan Scottc41564b2006-03-29 08:55:14 +10001147 * coalesce it with a sibling block. We choose (arbitrarily)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001148 * to merge with the forward block unless it is NULL.
1149 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001150 if (nodehdr.count == 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001151 /*
1152 * Make altpath point to the block we want to keep and
1153 * path point to the block we want to drop (this one).
1154 */
Nathan Scott89da0542006-03-17 17:28:40 +11001155 forward = (info->forw != 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001156 memcpy(&state->altpath, &state->path, sizeof(state->path));
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001157 error = xfs_da3_path_shift(state, &state->altpath, forward,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001158 0, &retval);
1159 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +10001160 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001161 if (retval) {
1162 *action = 0;
1163 } else {
1164 *action = 2;
1165 }
Eric Sandeend99831f2014-06-22 15:03:54 +10001166 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001167 }
1168
1169 /*
1170 * Examine each sibling block to see if we can coalesce with
1171 * at least 25% free space to spare. We need to figure out
1172 * whether to merge with the forward or the backward block.
1173 * We prefer coalescing with the lower numbered sibling so as
1174 * to shrink a directory over time.
1175 */
Dave Chinnerb2a21e72014-06-06 15:22:04 +10001176 count = state->args->geo->node_ents;
1177 count -= state->args->geo->node_ents >> 2;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001178 count -= nodehdr.count;
1179
Linus Torvalds1da177e2005-04-16 15:20:36 -07001180 /* start with smaller blk num */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001181 forward = nodehdr.forw < nodehdr.back;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001182 for (i = 0; i < 2; forward = !forward, i++) {
Mark Tinguely997def22013-09-23 12:18:58 -05001183 struct xfs_da3_icnode_hdr thdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001184 if (forward)
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001185 blkno = nodehdr.forw;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001186 else
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001187 blkno = nodehdr.back;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001188 if (blkno == 0)
1189 continue;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001190 error = xfs_da3_node_read(state->args->trans, dp,
Dave Chinnerd9392a42012-11-12 22:54:17 +11001191 blkno, -1, &bp, state->args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001192 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +10001193 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001194
Dave Chinner1d9025e2012-06-22 18:50:14 +10001195 node = bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001196 dp->d_ops->node_hdr_from_disk(&thdr, node);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001197 xfs_trans_brelse(state->args->trans, bp);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001198
Mark Tinguely997def22013-09-23 12:18:58 -05001199 if (count - thdr.count >= 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001200 break; /* fits with at least 25% to spare */
1201 }
1202 if (i >= 2) {
1203 *action = 0;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001204 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205 }
1206
1207 /*
1208 * Make altpath point to the block we want to keep (the lower
1209 * numbered block) and path point to the block we want to drop.
1210 */
1211 memcpy(&state->altpath, &state->path, sizeof(state->path));
1212 if (blkno < blk->blkno) {
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001213 error = xfs_da3_path_shift(state, &state->altpath, forward,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001214 0, &retval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215 } else {
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001216 error = xfs_da3_path_shift(state, &state->path, forward,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001217 0, &retval);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001218 }
1219 if (error)
1220 return error;
1221 if (retval) {
1222 *action = 0;
1223 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001224 }
1225 *action = 1;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001226 return 0;
1227}
1228
1229/*
1230 * Pick up the last hashvalue from an intermediate node.
1231 */
1232STATIC uint
1233xfs_da3_node_lasthash(
Dave Chinner4bceb182013-10-29 22:11:51 +11001234 struct xfs_inode *dp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001235 struct xfs_buf *bp,
1236 int *count)
1237{
1238 struct xfs_da_intnode *node;
1239 struct xfs_da_node_entry *btree;
1240 struct xfs_da3_icnode_hdr nodehdr;
1241
1242 node = bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001243 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001244 if (count)
1245 *count = nodehdr.count;
1246 if (!nodehdr.count)
1247 return 0;
Dave Chinner4bceb182013-10-29 22:11:51 +11001248 btree = dp->d_ops->node_tree_p(node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001249 return be32_to_cpu(btree[nodehdr.count - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001250}
1251
1252/*
1253 * Walk back up the tree adjusting hash values as necessary,
1254 * when we stop making changes, return.
1255 */
1256void
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001257xfs_da3_fixhashpath(
1258 struct xfs_da_state *state,
1259 struct xfs_da_state_path *path)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001260{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001261 struct xfs_da_state_blk *blk;
1262 struct xfs_da_intnode *node;
1263 struct xfs_da_node_entry *btree;
1264 xfs_dahash_t lasthash=0;
1265 int level;
1266 int count;
Dave Chinner4bceb182013-10-29 22:11:51 +11001267 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001268
Dave Chinneree732592012-11-12 22:53:53 +11001269 trace_xfs_da_fixhashpath(state->args);
1270
Linus Torvalds1da177e2005-04-16 15:20:36 -07001271 level = path->active-1;
1272 blk = &path->blk[ level ];
1273 switch (blk->magic) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001274 case XFS_ATTR_LEAF_MAGIC:
1275 lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
1276 if (count == 0)
1277 return;
1278 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001279 case XFS_DIR2_LEAFN_MAGIC:
Dave Chinner4bceb182013-10-29 22:11:51 +11001280 lasthash = xfs_dir2_leafn_lasthash(dp, blk->bp, &count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001281 if (count == 0)
1282 return;
1283 break;
1284 case XFS_DA_NODE_MAGIC:
Dave Chinner4bceb182013-10-29 22:11:51 +11001285 lasthash = xfs_da3_node_lasthash(dp, blk->bp, &count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001286 if (count == 0)
1287 return;
1288 break;
1289 }
1290 for (blk--, level--; level >= 0; blk--, level--) {
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001291 struct xfs_da3_icnode_hdr nodehdr;
1292
Dave Chinner1d9025e2012-06-22 18:50:14 +10001293 node = blk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001294 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinner4bceb182013-10-29 22:11:51 +11001295 btree = dp->d_ops->node_tree_p(node);
Mark Tinguelyc88547a2014-04-04 07:10:49 +11001296 if (be32_to_cpu(btree[blk->index].hashval) == lasthash)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001297 break;
1298 blk->hashval = lasthash;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001299 btree[blk->index].hashval = cpu_to_be32(lasthash);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001300 xfs_trans_log_buf(state->args->trans, blk->bp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001301 XFS_DA_LOGRANGE(node, &btree[blk->index],
1302 sizeof(*btree)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001303
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001304 lasthash = be32_to_cpu(btree[nodehdr.count - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001305 }
1306}
1307
1308/*
1309 * Remove an entry from an intermediate node.
1310 */
1311STATIC void
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001312xfs_da3_node_remove(
1313 struct xfs_da_state *state,
1314 struct xfs_da_state_blk *drop_blk)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001315{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001316 struct xfs_da_intnode *node;
1317 struct xfs_da3_icnode_hdr nodehdr;
1318 struct xfs_da_node_entry *btree;
1319 int index;
1320 int tmp;
Dave Chinner4bceb182013-10-29 22:11:51 +11001321 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001322
Dave Chinner5a5881c2012-03-22 05:15:13 +00001323 trace_xfs_da_node_remove(state->args);
1324
Dave Chinner1d9025e2012-06-22 18:50:14 +10001325 node = drop_blk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001326 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001327 ASSERT(drop_blk->index < nodehdr.count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001328 ASSERT(drop_blk->index >= 0);
1329
1330 /*
1331 * Copy over the offending entry, or just zero it out.
1332 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001333 index = drop_blk->index;
Dave Chinner4bceb182013-10-29 22:11:51 +11001334 btree = dp->d_ops->node_tree_p(node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001335 if (index < nodehdr.count - 1) {
1336 tmp = nodehdr.count - index - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001337 tmp *= (uint)sizeof(xfs_da_node_entry_t);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001338 memmove(&btree[index], &btree[index + 1], tmp);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001339 xfs_trans_log_buf(state->args->trans, drop_blk->bp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001340 XFS_DA_LOGRANGE(node, &btree[index], tmp));
1341 index = nodehdr.count - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001342 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001343 memset(&btree[index], 0, sizeof(xfs_da_node_entry_t));
Dave Chinner1d9025e2012-06-22 18:50:14 +10001344 xfs_trans_log_buf(state->args->trans, drop_blk->bp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001345 XFS_DA_LOGRANGE(node, &btree[index], sizeof(btree[index])));
1346 nodehdr.count -= 1;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001347 dp->d_ops->node_hdr_to_disk(node, &nodehdr);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001348 xfs_trans_log_buf(state->args->trans, drop_blk->bp,
Dave Chinner1c9a5b22013-10-30 09:15:02 +11001349 XFS_DA_LOGRANGE(node, &node->hdr, dp->d_ops->node_hdr_size));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001350
1351 /*
1352 * Copy the last hash value from the block to propagate upwards.
1353 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001354 drop_blk->hashval = be32_to_cpu(btree[index - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001355}
1356
1357/*
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001358 * Unbalance the elements between two intermediate nodes,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359 * move all Btree elements from one node into another.
1360 */
1361STATIC void
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001362xfs_da3_node_unbalance(
1363 struct xfs_da_state *state,
1364 struct xfs_da_state_blk *drop_blk,
1365 struct xfs_da_state_blk *save_blk)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001366{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001367 struct xfs_da_intnode *drop_node;
1368 struct xfs_da_intnode *save_node;
1369 struct xfs_da_node_entry *drop_btree;
1370 struct xfs_da_node_entry *save_btree;
1371 struct xfs_da3_icnode_hdr drop_hdr;
1372 struct xfs_da3_icnode_hdr save_hdr;
1373 struct xfs_trans *tp;
1374 int sindex;
1375 int tmp;
Dave Chinner4bceb182013-10-29 22:11:51 +11001376 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001377
Dave Chinner5a5881c2012-03-22 05:15:13 +00001378 trace_xfs_da_node_unbalance(state->args);
1379
Dave Chinner1d9025e2012-06-22 18:50:14 +10001380 drop_node = drop_blk->bp->b_addr;
1381 save_node = save_blk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001382 dp->d_ops->node_hdr_from_disk(&drop_hdr, drop_node);
1383 dp->d_ops->node_hdr_from_disk(&save_hdr, save_node);
Dave Chinner4bceb182013-10-29 22:11:51 +11001384 drop_btree = dp->d_ops->node_tree_p(drop_node);
1385 save_btree = dp->d_ops->node_tree_p(save_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386 tp = state->args->trans;
1387
1388 /*
1389 * If the dying block has lower hashvals, then move all the
1390 * elements in the remaining block up to make a hole.
1391 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001392 if ((be32_to_cpu(drop_btree[0].hashval) <
1393 be32_to_cpu(save_btree[0].hashval)) ||
1394 (be32_to_cpu(drop_btree[drop_hdr.count - 1].hashval) <
1395 be32_to_cpu(save_btree[save_hdr.count - 1].hashval))) {
1396 /* XXX: check this - is memmove dst correct? */
1397 tmp = save_hdr.count * sizeof(xfs_da_node_entry_t);
1398 memmove(&save_btree[drop_hdr.count], &save_btree[0], tmp);
1399
1400 sindex = 0;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001401 xfs_trans_log_buf(tp, save_blk->bp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001402 XFS_DA_LOGRANGE(save_node, &save_btree[0],
1403 (save_hdr.count + drop_hdr.count) *
1404 sizeof(xfs_da_node_entry_t)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001405 } else {
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001406 sindex = save_hdr.count;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001407 xfs_trans_log_buf(tp, save_blk->bp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001408 XFS_DA_LOGRANGE(save_node, &save_btree[sindex],
1409 drop_hdr.count * sizeof(xfs_da_node_entry_t)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001410 }
1411
1412 /*
1413 * Move all the B-tree elements from drop_blk to save_blk.
1414 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001415 tmp = drop_hdr.count * (uint)sizeof(xfs_da_node_entry_t);
1416 memcpy(&save_btree[sindex], &drop_btree[0], tmp);
1417 save_hdr.count += drop_hdr.count;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001418
Dave Chinner01ba43b2013-10-29 22:11:52 +11001419 dp->d_ops->node_hdr_to_disk(save_node, &save_hdr);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001420 xfs_trans_log_buf(tp, save_blk->bp,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001421 XFS_DA_LOGRANGE(save_node, &save_node->hdr,
Dave Chinner1c9a5b22013-10-30 09:15:02 +11001422 dp->d_ops->node_hdr_size));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001423
1424 /*
1425 * Save the last hashval in the remaining block for upward propagation.
1426 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001427 save_blk->hashval = be32_to_cpu(save_btree[save_hdr.count - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428}
1429
1430/*========================================================================
1431 * Routines used for finding things in the Btree.
1432 *========================================================================*/
1433
1434/*
1435 * Walk down the Btree looking for a particular filename, filling
1436 * in the state structure as we go.
1437 *
1438 * We will set the state structure to point to each of the elements
1439 * in each of the nodes where either the hashval is or should be.
1440 *
1441 * We support duplicate hashval's so for each entry in the current
1442 * node that could contain the desired hashval, descend. This is a
1443 * pruned depth-first tree search.
1444 */
1445int /* error */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001446xfs_da3_node_lookup_int(
1447 struct xfs_da_state *state,
1448 int *result)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001449{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001450 struct xfs_da_state_blk *blk;
1451 struct xfs_da_blkinfo *curr;
1452 struct xfs_da_intnode *node;
1453 struct xfs_da_node_entry *btree;
1454 struct xfs_da3_icnode_hdr nodehdr;
1455 struct xfs_da_args *args;
1456 xfs_dablk_t blkno;
1457 xfs_dahash_t hashval;
1458 xfs_dahash_t btreehashval;
1459 int probe;
1460 int span;
1461 int max;
1462 int error;
1463 int retval;
Dave Chinner4bceb182013-10-29 22:11:51 +11001464 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001465
1466 args = state->args;
1467
1468 /*
1469 * Descend thru the B-tree searching each level for the right
1470 * node to use, until the right hashval is found.
1471 */
Dave Chinner7dda6e82014-06-06 15:11:18 +10001472 blkno = (args->whichfork == XFS_DATA_FORK)? args->geo->leafblk : 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001473 for (blk = &state->path.blk[0], state->path.active = 1;
1474 state->path.active <= XFS_DA_NODE_MAXDEPTH;
1475 blk++, state->path.active++) {
1476 /*
1477 * Read the next node down in the tree.
1478 */
1479 blk->blkno = blkno;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001480 error = xfs_da3_node_read(args->trans, args->dp, blkno,
Dave Chinnerd9392a42012-11-12 22:54:17 +11001481 -1, &blk->bp, args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001482 if (error) {
1483 blk->blkno = 0;
1484 state->path.active--;
Eric Sandeend99831f2014-06-22 15:03:54 +10001485 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001486 }
Dave Chinner1d9025e2012-06-22 18:50:14 +10001487 curr = blk->bp->b_addr;
Nathan Scottd432c802006-09-28 11:03:44 +10001488 blk->magic = be16_to_cpu(curr->magic);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001489
Dave Chinner517c2222013-04-24 18:58:55 +10001490 if (blk->magic == XFS_ATTR_LEAF_MAGIC ||
1491 blk->magic == XFS_ATTR3_LEAF_MAGIC) {
1492 blk->magic = XFS_ATTR_LEAF_MAGIC;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001493 blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
1494 break;
1495 }
1496
1497 if (blk->magic == XFS_DIR2_LEAFN_MAGIC ||
1498 blk->magic == XFS_DIR3_LEAFN_MAGIC) {
1499 blk->magic = XFS_DIR2_LEAFN_MAGIC;
Dave Chinner41419562013-10-29 22:11:50 +11001500 blk->hashval = xfs_dir2_leafn_lasthash(args->dp,
1501 blk->bp, NULL);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001502 break;
1503 }
1504
1505 blk->magic = XFS_DA_NODE_MAGIC;
1506
Linus Torvalds1da177e2005-04-16 15:20:36 -07001507
1508 /*
1509 * Search an intermediate node for a match.
1510 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001511 node = blk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001512 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinner4bceb182013-10-29 22:11:51 +11001513 btree = dp->d_ops->node_tree_p(node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001514
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001515 max = nodehdr.count;
1516 blk->hashval = be32_to_cpu(btree[max - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001517
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001518 /*
1519 * Binary search. (note: small blocks will skip loop)
1520 */
1521 probe = span = max / 2;
1522 hashval = args->hashval;
1523 while (span > 4) {
1524 span /= 2;
1525 btreehashval = be32_to_cpu(btree[probe].hashval);
1526 if (btreehashval < hashval)
1527 probe += span;
1528 else if (btreehashval > hashval)
1529 probe -= span;
1530 else
1531 break;
1532 }
1533 ASSERT((probe >= 0) && (probe < max));
1534 ASSERT((span <= 4) ||
1535 (be32_to_cpu(btree[probe].hashval) == hashval));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001536
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001537 /*
1538 * Since we may have duplicate hashval's, find the first
1539 * matching hashval in the node.
1540 */
1541 while (probe > 0 &&
1542 be32_to_cpu(btree[probe].hashval) >= hashval) {
1543 probe--;
1544 }
1545 while (probe < max &&
1546 be32_to_cpu(btree[probe].hashval) < hashval) {
1547 probe++;
1548 }
1549
1550 /*
1551 * Pick the right block to descend on.
1552 */
1553 if (probe == max) {
1554 blk->index = max - 1;
1555 blkno = be32_to_cpu(btree[max - 1].before);
1556 } else {
1557 blk->index = probe;
1558 blkno = be32_to_cpu(btree[probe].before);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001559 }
1560 }
1561
1562 /*
1563 * A leaf block that ends in the hashval that we are interested in
1564 * (final hashval == search hashval) means that the next block may
1565 * contain more entries with the same hashval, shift upward to the
1566 * next leaf and keep searching.
1567 */
1568 for (;;) {
Nathan Scottf6c2d1f2006-06-20 13:04:51 +10001569 if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001570 retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
1571 &blk->index, state);
Nathan Scottd432c802006-09-28 11:03:44 +10001572 } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
Dave Chinner517c2222013-04-24 18:58:55 +10001573 retval = xfs_attr3_leaf_lookup_int(blk->bp, args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001574 blk->index = args->index;
1575 args->blkno = blk->blkno;
Nathan Scottd432c802006-09-28 11:03:44 +10001576 } else {
1577 ASSERT(0);
Dave Chinner24513372014-06-25 14:58:08 +10001578 return -EFSCORRUPTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001579 }
Dave Chinner24513372014-06-25 14:58:08 +10001580 if (((retval == -ENOENT) || (retval == -ENOATTR)) &&
Linus Torvalds1da177e2005-04-16 15:20:36 -07001581 (blk->hashval == args->hashval)) {
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001582 error = xfs_da3_path_shift(state, &state->path, 1, 1,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001583 &retval);
1584 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +10001585 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001586 if (retval == 0) {
1587 continue;
Nathan Scottd432c802006-09-28 11:03:44 +10001588 } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001589 /* path_shift() gives ENOENT */
Dave Chinner24513372014-06-25 14:58:08 +10001590 retval = -ENOATTR;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001591 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001592 }
1593 break;
1594 }
1595 *result = retval;
Eric Sandeend99831f2014-06-22 15:03:54 +10001596 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001597}
1598
1599/*========================================================================
1600 * Utility routines.
1601 *========================================================================*/
1602
1603/*
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001604 * Compare two intermediate nodes for "order".
1605 */
1606STATIC int
1607xfs_da3_node_order(
Dave Chinner4bceb182013-10-29 22:11:51 +11001608 struct xfs_inode *dp,
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001609 struct xfs_buf *node1_bp,
1610 struct xfs_buf *node2_bp)
1611{
1612 struct xfs_da_intnode *node1;
1613 struct xfs_da_intnode *node2;
1614 struct xfs_da_node_entry *btree1;
1615 struct xfs_da_node_entry *btree2;
1616 struct xfs_da3_icnode_hdr node1hdr;
1617 struct xfs_da3_icnode_hdr node2hdr;
1618
1619 node1 = node1_bp->b_addr;
1620 node2 = node2_bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001621 dp->d_ops->node_hdr_from_disk(&node1hdr, node1);
1622 dp->d_ops->node_hdr_from_disk(&node2hdr, node2);
Dave Chinner4bceb182013-10-29 22:11:51 +11001623 btree1 = dp->d_ops->node_tree_p(node1);
1624 btree2 = dp->d_ops->node_tree_p(node2);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001625
1626 if (node1hdr.count > 0 && node2hdr.count > 0 &&
1627 ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
1628 (be32_to_cpu(btree2[node2hdr.count - 1].hashval) <
1629 be32_to_cpu(btree1[node1hdr.count - 1].hashval)))) {
1630 return 1;
1631 }
1632 return 0;
1633}
1634
1635/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001636 * Link a new block into a doubly linked list of blocks (of whatever type).
1637 */
1638int /* error */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001639xfs_da3_blk_link(
1640 struct xfs_da_state *state,
1641 struct xfs_da_state_blk *old_blk,
1642 struct xfs_da_state_blk *new_blk)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001643{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001644 struct xfs_da_blkinfo *old_info;
1645 struct xfs_da_blkinfo *new_info;
1646 struct xfs_da_blkinfo *tmp_info;
1647 struct xfs_da_args *args;
1648 struct xfs_buf *bp;
1649 int before = 0;
1650 int error;
Dave Chinner4bceb182013-10-29 22:11:51 +11001651 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001652
1653 /*
1654 * Set up environment.
1655 */
1656 args = state->args;
1657 ASSERT(args != NULL);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001658 old_info = old_blk->bp->b_addr;
1659 new_info = new_blk->bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001660 ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||
Nathan Scottf6c2d1f2006-06-20 13:04:51 +10001661 old_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001662 old_blk->magic == XFS_ATTR_LEAF_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001663
1664 switch (old_blk->magic) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001665 case XFS_ATTR_LEAF_MAGIC:
1666 before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
1667 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001668 case XFS_DIR2_LEAFN_MAGIC:
Dave Chinner4bceb182013-10-29 22:11:51 +11001669 before = xfs_dir2_leafn_order(dp, old_blk->bp, new_blk->bp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001670 break;
1671 case XFS_DA_NODE_MAGIC:
Dave Chinner4bceb182013-10-29 22:11:51 +11001672 before = xfs_da3_node_order(dp, old_blk->bp, new_blk->bp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001673 break;
1674 }
1675
1676 /*
1677 * Link blocks in appropriate order.
1678 */
1679 if (before) {
1680 /*
1681 * Link new block in before existing block.
1682 */
Dave Chinner5a5881c2012-03-22 05:15:13 +00001683 trace_xfs_da_link_before(args);
Nathan Scott89da0542006-03-17 17:28:40 +11001684 new_info->forw = cpu_to_be32(old_blk->blkno);
1685 new_info->back = old_info->back;
1686 if (old_info->back) {
Dave Chinner4bceb182013-10-29 22:11:51 +11001687 error = xfs_da3_node_read(args->trans, dp,
Nathan Scott89da0542006-03-17 17:28:40 +11001688 be32_to_cpu(old_info->back),
Dave Chinnerd9392a42012-11-12 22:54:17 +11001689 -1, &bp, args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001690 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +10001691 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001692 ASSERT(bp != NULL);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001693 tmp_info = bp->b_addr;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001694 ASSERT(tmp_info->magic == old_info->magic);
Nathan Scott89da0542006-03-17 17:28:40 +11001695 ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);
1696 tmp_info->forw = cpu_to_be32(new_blk->blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001697 xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001698 }
Nathan Scott89da0542006-03-17 17:28:40 +11001699 old_info->back = cpu_to_be32(new_blk->blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001700 } else {
1701 /*
1702 * Link new block in after existing block.
1703 */
Dave Chinner5a5881c2012-03-22 05:15:13 +00001704 trace_xfs_da_link_after(args);
Nathan Scott89da0542006-03-17 17:28:40 +11001705 new_info->forw = old_info->forw;
1706 new_info->back = cpu_to_be32(old_blk->blkno);
1707 if (old_info->forw) {
Dave Chinner4bceb182013-10-29 22:11:51 +11001708 error = xfs_da3_node_read(args->trans, dp,
Nathan Scott89da0542006-03-17 17:28:40 +11001709 be32_to_cpu(old_info->forw),
Dave Chinnerd9392a42012-11-12 22:54:17 +11001710 -1, &bp, args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001711 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +10001712 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001713 ASSERT(bp != NULL);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001714 tmp_info = bp->b_addr;
Nathan Scott89da0542006-03-17 17:28:40 +11001715 ASSERT(tmp_info->magic == old_info->magic);
1716 ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
1717 tmp_info->back = cpu_to_be32(new_blk->blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001718 xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001719 }
Nathan Scott89da0542006-03-17 17:28:40 +11001720 old_info->forw = cpu_to_be32(new_blk->blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001721 }
1722
Dave Chinner1d9025e2012-06-22 18:50:14 +10001723 xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
1724 xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
Eric Sandeend99831f2014-06-22 15:03:54 +10001725 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001726}
1727
1728/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001729 * Unlink a block from a doubly linked list of blocks.
1730 */
Christoph Hellwigba0f32d2005-06-21 15:36:52 +10001731STATIC int /* error */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001732xfs_da3_blk_unlink(
1733 struct xfs_da_state *state,
1734 struct xfs_da_state_blk *drop_blk,
1735 struct xfs_da_state_blk *save_blk)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001736{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001737 struct xfs_da_blkinfo *drop_info;
1738 struct xfs_da_blkinfo *save_info;
1739 struct xfs_da_blkinfo *tmp_info;
1740 struct xfs_da_args *args;
1741 struct xfs_buf *bp;
1742 int error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001743
1744 /*
1745 * Set up environment.
1746 */
1747 args = state->args;
1748 ASSERT(args != NULL);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001749 save_info = save_blk->bp->b_addr;
1750 drop_info = drop_blk->bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001751 ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||
Nathan Scottf6c2d1f2006-06-20 13:04:51 +10001752 save_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001753 save_blk->magic == XFS_ATTR_LEAF_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001754 ASSERT(save_blk->magic == drop_blk->magic);
Nathan Scott89da0542006-03-17 17:28:40 +11001755 ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
1756 (be32_to_cpu(save_info->back) == drop_blk->blkno));
1757 ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) ||
1758 (be32_to_cpu(drop_info->back) == save_blk->blkno));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001759
1760 /*
1761 * Unlink the leaf block from the doubly linked chain of leaves.
1762 */
Nathan Scott89da0542006-03-17 17:28:40 +11001763 if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
Dave Chinner5a5881c2012-03-22 05:15:13 +00001764 trace_xfs_da_unlink_back(args);
Nathan Scott89da0542006-03-17 17:28:40 +11001765 save_info->back = drop_info->back;
1766 if (drop_info->back) {
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001767 error = xfs_da3_node_read(args->trans, args->dp,
Nathan Scott89da0542006-03-17 17:28:40 +11001768 be32_to_cpu(drop_info->back),
Dave Chinnerd9392a42012-11-12 22:54:17 +11001769 -1, &bp, args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001770 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +10001771 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001772 ASSERT(bp != NULL);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001773 tmp_info = bp->b_addr;
Nathan Scott89da0542006-03-17 17:28:40 +11001774 ASSERT(tmp_info->magic == save_info->magic);
1775 ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
1776 tmp_info->forw = cpu_to_be32(save_blk->blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001777 xfs_trans_log_buf(args->trans, bp, 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001778 sizeof(*tmp_info) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001779 }
1780 } else {
Dave Chinner5a5881c2012-03-22 05:15:13 +00001781 trace_xfs_da_unlink_forward(args);
Nathan Scott89da0542006-03-17 17:28:40 +11001782 save_info->forw = drop_info->forw;
1783 if (drop_info->forw) {
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001784 error = xfs_da3_node_read(args->trans, args->dp,
Nathan Scott89da0542006-03-17 17:28:40 +11001785 be32_to_cpu(drop_info->forw),
Dave Chinnerd9392a42012-11-12 22:54:17 +11001786 -1, &bp, args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001787 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +10001788 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001789 ASSERT(bp != NULL);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001790 tmp_info = bp->b_addr;
Nathan Scott89da0542006-03-17 17:28:40 +11001791 ASSERT(tmp_info->magic == save_info->magic);
1792 ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
1793 tmp_info->back = cpu_to_be32(save_blk->blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001794 xfs_trans_log_buf(args->trans, bp, 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001795 sizeof(*tmp_info) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001796 }
1797 }
1798
Dave Chinner1d9025e2012-06-22 18:50:14 +10001799 xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
Eric Sandeend99831f2014-06-22 15:03:54 +10001800 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001801}
1802
1803/*
1804 * Move a path "forward" or "!forward" one block at the current level.
1805 *
1806 * This routine will adjust a "path" to point to the next block
1807 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1808 * Btree, including updating pointers to the intermediate nodes between
1809 * the new bottom and the root.
1810 */
1811int /* error */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001812xfs_da3_path_shift(
1813 struct xfs_da_state *state,
1814 struct xfs_da_state_path *path,
1815 int forward,
1816 int release,
1817 int *result)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001818{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001819 struct xfs_da_state_blk *blk;
1820 struct xfs_da_blkinfo *info;
1821 struct xfs_da_intnode *node;
1822 struct xfs_da_args *args;
1823 struct xfs_da_node_entry *btree;
1824 struct xfs_da3_icnode_hdr nodehdr;
1825 xfs_dablk_t blkno = 0;
1826 int level;
1827 int error;
Dave Chinner4bceb182013-10-29 22:11:51 +11001828 struct xfs_inode *dp = state->args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001829
Dave Chinneree732592012-11-12 22:53:53 +11001830 trace_xfs_da_path_shift(state->args);
1831
Linus Torvalds1da177e2005-04-16 15:20:36 -07001832 /*
1833 * Roll up the Btree looking for the first block where our
1834 * current index is not at the edge of the block. Note that
1835 * we skip the bottom layer because we want the sibling block.
1836 */
1837 args = state->args;
1838 ASSERT(args != NULL);
1839 ASSERT(path != NULL);
1840 ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
1841 level = (path->active-1) - 1; /* skip bottom layer in path */
1842 for (blk = &path->blk[level]; level >= 0; blk--, level--) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001843 node = blk->bp->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001844 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinner4bceb182013-10-29 22:11:51 +11001845 btree = dp->d_ops->node_tree_p(node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001846
1847 if (forward && (blk->index < nodehdr.count - 1)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001848 blk->index++;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001849 blkno = be32_to_cpu(btree[blk->index].before);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001850 break;
1851 } else if (!forward && (blk->index > 0)) {
1852 blk->index--;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001853 blkno = be32_to_cpu(btree[blk->index].before);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001854 break;
1855 }
1856 }
1857 if (level < 0) {
Dave Chinner24513372014-06-25 14:58:08 +10001858 *result = -ENOENT; /* we're out of our tree */
Barry Naujok6a178102008-05-21 16:42:05 +10001859 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
Eric Sandeend99831f2014-06-22 15:03:54 +10001860 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001861 }
1862
1863 /*
1864 * Roll down the edge of the subtree until we reach the
1865 * same depth we were at originally.
1866 */
1867 for (blk++, level++; level < path->active; blk++, level++) {
1868 /*
1869 * Release the old block.
1870 * (if it's dirty, trans won't actually let go)
1871 */
1872 if (release)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001873 xfs_trans_brelse(args->trans, blk->bp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001874
1875 /*
1876 * Read the next child block.
1877 */
1878 blk->blkno = blkno;
Dave Chinner4bceb182013-10-29 22:11:51 +11001879 error = xfs_da3_node_read(args->trans, dp, blkno, -1,
Dave Chinnerd9392a42012-11-12 22:54:17 +11001880 &blk->bp, args->whichfork);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001881 if (error)
Eric Sandeend99831f2014-06-22 15:03:54 +10001882 return error;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001883 info = blk->bp->b_addr;
Christoph Hellwig69ef9212011-07-08 14:36:05 +02001884 ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001885 info->magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
Christoph Hellwig69ef9212011-07-08 14:36:05 +02001886 info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
Dave Chinner24df33b2013-04-12 07:30:21 +10001887 info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
Dave Chinner517c2222013-04-24 18:58:55 +10001888 info->magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
1889 info->magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001890
1891
1892 /*
1893 * Note: we flatten the magic number to a single type so we
1894 * don't have to compare against crc/non-crc types elsewhere.
1895 */
1896 switch (be16_to_cpu(info->magic)) {
1897 case XFS_DA_NODE_MAGIC:
1898 case XFS_DA3_NODE_MAGIC:
1899 blk->magic = XFS_DA_NODE_MAGIC;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001900 node = (xfs_da_intnode_t *)info;
Dave Chinner01ba43b2013-10-29 22:11:52 +11001901 dp->d_ops->node_hdr_from_disk(&nodehdr, node);
Dave Chinner4bceb182013-10-29 22:11:51 +11001902 btree = dp->d_ops->node_tree_p(node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001903 blk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001904 if (forward)
1905 blk->index = 0;
1906 else
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001907 blk->index = nodehdr.count - 1;
1908 blkno = be32_to_cpu(btree[blk->index].before);
1909 break;
1910 case XFS_ATTR_LEAF_MAGIC:
Dave Chinner517c2222013-04-24 18:58:55 +10001911 case XFS_ATTR3_LEAF_MAGIC:
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001912 blk->magic = XFS_ATTR_LEAF_MAGIC;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001913 ASSERT(level == path->active-1);
1914 blk->index = 0;
Dave Chinner41419562013-10-29 22:11:50 +11001915 blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001916 break;
1917 case XFS_DIR2_LEAFN_MAGIC:
1918 case XFS_DIR3_LEAFN_MAGIC:
1919 blk->magic = XFS_DIR2_LEAFN_MAGIC;
1920 ASSERT(level == path->active-1);
1921 blk->index = 0;
Dave Chinner41419562013-10-29 22:11:50 +11001922 blk->hashval = xfs_dir2_leafn_lasthash(args->dp,
1923 blk->bp, NULL);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001924 break;
1925 default:
1926 ASSERT(0);
1927 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001928 }
1929 }
1930 *result = 0;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10001931 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001932}
1933
1934
1935/*========================================================================
1936 * Utility routines.
1937 *========================================================================*/
1938
1939/*
1940 * Implement a simple hash on a character string.
1941 * Rotate the hash value by 7 bits, then XOR each character in.
1942 * This is implemented with some source-level loop unrolling.
1943 */
1944xfs_dahash_t
Christoph Hellwiga5687782009-02-09 08:37:39 +01001945xfs_da_hashname(const __uint8_t *name, int namelen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001946{
1947 xfs_dahash_t hash;
1948
Linus Torvalds1da177e2005-04-16 15:20:36 -07001949 /*
1950 * Do four characters at a time as long as we can.
1951 */
1952 for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
1953 hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
1954 (name[3] << 0) ^ rol32(hash, 7 * 4);
1955
1956 /*
1957 * Now do the rest of the characters.
1958 */
1959 switch (namelen) {
1960 case 3:
1961 return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
1962 rol32(hash, 7 * 3);
1963 case 2:
1964 return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
1965 case 1:
1966 return (name[0] << 0) ^ rol32(hash, 7 * 1);
Nathan Scott2b3b6d02005-11-02 15:12:28 +11001967 default: /* case 0: */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001968 return hash;
1969 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001970}
1971
Barry Naujok5163f952008-05-21 16:41:01 +10001972enum xfs_dacmp
1973xfs_da_compname(
1974 struct xfs_da_args *args,
Dave Chinner2bc75422010-01-20 10:47:17 +11001975 const unsigned char *name,
1976 int len)
Barry Naujok5163f952008-05-21 16:41:01 +10001977{
1978 return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
1979 XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
1980}
1981
1982static xfs_dahash_t
1983xfs_default_hashname(
1984 struct xfs_name *name)
1985{
1986 return xfs_da_hashname(name->name, name->len);
1987}
1988
1989const struct xfs_nameops xfs_default_nameops = {
1990 .hashname = xfs_default_hashname,
1991 .compname = xfs_da_compname
1992};
1993
Linus Torvalds1da177e2005-04-16 15:20:36 -07001994int
Christoph Hellwig77936d02011-07-13 13:43:49 +02001995xfs_da_grow_inode_int(
1996 struct xfs_da_args *args,
1997 xfs_fileoff_t *bno,
1998 int count)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001999{
Christoph Hellwig77936d02011-07-13 13:43:49 +02002000 struct xfs_trans *tp = args->trans;
2001 struct xfs_inode *dp = args->dp;
2002 int w = args->whichfork;
Christoph Hellwigd5cf09b2014-07-30 09:12:05 +10002003 xfs_rfsblock_t nblks = dp->i_d.di_nblocks;
Christoph Hellwig77936d02011-07-13 13:43:49 +02002004 struct xfs_bmbt_irec map, *mapp;
2005 int nmap, error, got, i, mapi;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002006
Linus Torvalds1da177e2005-04-16 15:20:36 -07002007 /*
2008 * Find a spot in the file space to put the new block.
2009 */
Christoph Hellwig77936d02011-07-13 13:43:49 +02002010 error = xfs_bmap_first_unused(tp, dp, count, bno, w);
2011 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002012 return error;
Christoph Hellwig77936d02011-07-13 13:43:49 +02002013
Linus Torvalds1da177e2005-04-16 15:20:36 -07002014 /*
2015 * Try mapping it in one filesystem block.
2016 */
2017 nmap = 1;
2018 ASSERT(args->firstblock != NULL);
Dave Chinnerc0dc7822011-09-18 20:40:52 +00002019 error = xfs_bmapi_write(tp, dp, *bno, count,
2020 xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002021 args->firstblock, args->total, &map, &nmap,
Christoph Hellwig77936d02011-07-13 13:43:49 +02002022 args->flist);
2023 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002024 return error;
Christoph Hellwig77936d02011-07-13 13:43:49 +02002025
Linus Torvalds1da177e2005-04-16 15:20:36 -07002026 ASSERT(nmap <= 1);
2027 if (nmap == 1) {
2028 mapp = &map;
2029 mapi = 1;
Christoph Hellwig77936d02011-07-13 13:43:49 +02002030 } else if (nmap == 0 && count > 1) {
2031 xfs_fileoff_t b;
2032 int c;
2033
2034 /*
2035 * If we didn't get it and the block might work if fragmented,
2036 * try without the CONTIG flag. Loop until we get it all.
2037 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002038 mapp = kmem_alloc(sizeof(*mapp) * count, KM_SLEEP);
Christoph Hellwig77936d02011-07-13 13:43:49 +02002039 for (b = *bno, mapi = 0; b < *bno + count; ) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002040 nmap = MIN(XFS_BMAP_MAX_NMAP, count);
Christoph Hellwig77936d02011-07-13 13:43:49 +02002041 c = (int)(*bno + count - b);
Dave Chinnerc0dc7822011-09-18 20:40:52 +00002042 error = xfs_bmapi_write(tp, dp, b, c,
2043 xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002044 args->firstblock, args->total,
Christoph Hellwig77936d02011-07-13 13:43:49 +02002045 &mapp[mapi], &nmap, args->flist);
2046 if (error)
2047 goto out_free_map;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002048 if (nmap < 1)
2049 break;
2050 mapi += nmap;
2051 b = mapp[mapi - 1].br_startoff +
2052 mapp[mapi - 1].br_blockcount;
2053 }
2054 } else {
2055 mapi = 0;
2056 mapp = NULL;
2057 }
Christoph Hellwig77936d02011-07-13 13:43:49 +02002058
Linus Torvalds1da177e2005-04-16 15:20:36 -07002059 /*
2060 * Count the blocks we got, make sure it matches the total.
2061 */
2062 for (i = 0, got = 0; i < mapi; i++)
2063 got += mapp[i].br_blockcount;
Christoph Hellwig77936d02011-07-13 13:43:49 +02002064 if (got != count || mapp[0].br_startoff != *bno ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07002065 mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
Christoph Hellwig77936d02011-07-13 13:43:49 +02002066 *bno + count) {
Dave Chinner24513372014-06-25 14:58:08 +10002067 error = -ENOSPC;
Christoph Hellwig77936d02011-07-13 13:43:49 +02002068 goto out_free_map;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002069 }
Christoph Hellwig77936d02011-07-13 13:43:49 +02002070
David Chinnera7444052008-10-30 17:38:12 +11002071 /* account for newly allocated blocks in reserved blocks total */
2072 args->total -= dp->i_d.di_nblocks - nblks;
Christoph Hellwig77936d02011-07-13 13:43:49 +02002073
2074out_free_map:
2075 if (mapp != &map)
2076 kmem_free(mapp);
2077 return error;
2078}
2079
2080/*
2081 * Add a block to the btree ahead of the file.
2082 * Return the new block number to the caller.
2083 */
2084int
2085xfs_da_grow_inode(
2086 struct xfs_da_args *args,
2087 xfs_dablk_t *new_blkno)
2088{
2089 xfs_fileoff_t bno;
Christoph Hellwig77936d02011-07-13 13:43:49 +02002090 int error;
2091
Dave Chinner5a5881c2012-03-22 05:15:13 +00002092 trace_xfs_da_grow_inode(args);
2093
Dave Chinnerd6cf1302014-06-06 15:14:11 +10002094 bno = args->geo->leafblk;
2095 error = xfs_da_grow_inode_int(args, &bno, args->geo->fsbcount);
Christoph Hellwig77936d02011-07-13 13:43:49 +02002096 if (!error)
2097 *new_blkno = (xfs_dablk_t)bno;
2098 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002099}
2100
2101/*
2102 * Ick. We need to always be able to remove a btree block, even
2103 * if there's no space reservation because the filesystem is full.
2104 * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
2105 * It swaps the target block with the last block in the file. The
2106 * last block in the file can always be removed since it can't cause
2107 * a bmap btree split to do that.
2108 */
2109STATIC int
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002110xfs_da3_swap_lastblock(
2111 struct xfs_da_args *args,
2112 xfs_dablk_t *dead_blknop,
2113 struct xfs_buf **dead_bufp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002114{
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002115 struct xfs_da_blkinfo *dead_info;
2116 struct xfs_da_blkinfo *sib_info;
2117 struct xfs_da_intnode *par_node;
2118 struct xfs_da_intnode *dead_node;
2119 struct xfs_dir2_leaf *dead_leaf2;
2120 struct xfs_da_node_entry *btree;
2121 struct xfs_da3_icnode_hdr par_hdr;
Dave Chinner4bceb182013-10-29 22:11:51 +11002122 struct xfs_inode *dp;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002123 struct xfs_trans *tp;
2124 struct xfs_mount *mp;
2125 struct xfs_buf *dead_buf;
2126 struct xfs_buf *last_buf;
2127 struct xfs_buf *sib_buf;
2128 struct xfs_buf *par_buf;
2129 xfs_dahash_t dead_hash;
2130 xfs_fileoff_t lastoff;
2131 xfs_dablk_t dead_blkno;
2132 xfs_dablk_t last_blkno;
2133 xfs_dablk_t sib_blkno;
2134 xfs_dablk_t par_blkno;
2135 int error;
2136 int w;
2137 int entno;
2138 int level;
2139 int dead_level;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002140
Dave Chinner5a5881c2012-03-22 05:15:13 +00002141 trace_xfs_da_swap_lastblock(args);
2142
Linus Torvalds1da177e2005-04-16 15:20:36 -07002143 dead_buf = *dead_bufp;
2144 dead_blkno = *dead_blknop;
2145 tp = args->trans;
Dave Chinner4bceb182013-10-29 22:11:51 +11002146 dp = args->dp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002147 w = args->whichfork;
2148 ASSERT(w == XFS_DATA_FORK);
Dave Chinner4bceb182013-10-29 22:11:51 +11002149 mp = dp->i_mount;
Dave Chinner7dda6e82014-06-06 15:11:18 +10002150 lastoff = args->geo->freeblk;
Dave Chinner4bceb182013-10-29 22:11:51 +11002151 error = xfs_bmap_last_before(tp, dp, &lastoff, w);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002152 if (error)
2153 return error;
2154 if (unlikely(lastoff == 0)) {
2155 XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW,
2156 mp);
Dave Chinner24513372014-06-25 14:58:08 +10002157 return -EFSCORRUPTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002158 }
2159 /*
2160 * Read the last block in the btree space.
2161 */
Dave Chinnerd6cf1302014-06-06 15:14:11 +10002162 last_blkno = (xfs_dablk_t)lastoff - args->geo->fsbcount;
Dave Chinner4bceb182013-10-29 22:11:51 +11002163 error = xfs_da3_node_read(tp, dp, last_blkno, -1, &last_buf, w);
Dave Chinner4bb20a82012-11-12 22:54:10 +11002164 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002165 return error;
2166 /*
2167 * Copy the last block into the dead buffer and log it.
2168 */
Dave Chinner8f661932014-06-06 15:15:59 +10002169 memcpy(dead_buf->b_addr, last_buf->b_addr, args->geo->blksize);
2170 xfs_trans_log_buf(tp, dead_buf, 0, args->geo->blksize - 1);
Dave Chinner1d9025e2012-06-22 18:50:14 +10002171 dead_info = dead_buf->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002172 /*
2173 * Get values from the moved block.
2174 */
Dave Chinner24df33b2013-04-12 07:30:21 +10002175 if (dead_info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
2176 dead_info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
2177 struct xfs_dir3_icleaf_hdr leafhdr;
2178 struct xfs_dir2_leaf_entry *ents;
2179
Linus Torvalds1da177e2005-04-16 15:20:36 -07002180 dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;
Dave Chinner01ba43b2013-10-29 22:11:52 +11002181 dp->d_ops->leaf_hdr_from_disk(&leafhdr, dead_leaf2);
Dave Chinner4bceb182013-10-29 22:11:51 +11002182 ents = dp->d_ops->leaf_ents_p(dead_leaf2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002183 dead_level = 0;
Dave Chinner24df33b2013-04-12 07:30:21 +10002184 dead_hash = be32_to_cpu(ents[leafhdr.count - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002185 } else {
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002186 struct xfs_da3_icnode_hdr deadhdr;
2187
Linus Torvalds1da177e2005-04-16 15:20:36 -07002188 dead_node = (xfs_da_intnode_t *)dead_info;
Dave Chinner01ba43b2013-10-29 22:11:52 +11002189 dp->d_ops->node_hdr_from_disk(&deadhdr, dead_node);
Dave Chinner4bceb182013-10-29 22:11:51 +11002190 btree = dp->d_ops->node_tree_p(dead_node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002191 dead_level = deadhdr.level;
2192 dead_hash = be32_to_cpu(btree[deadhdr.count - 1].hashval);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002193 }
2194 sib_buf = par_buf = NULL;
2195 /*
2196 * If the moved block has a left sibling, fix up the pointers.
2197 */
Nathan Scott89da0542006-03-17 17:28:40 +11002198 if ((sib_blkno = be32_to_cpu(dead_info->back))) {
Dave Chinner4bceb182013-10-29 22:11:51 +11002199 error = xfs_da3_node_read(tp, dp, sib_blkno, -1, &sib_buf, w);
Dave Chinner4bb20a82012-11-12 22:54:10 +11002200 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002201 goto done;
Dave Chinner1d9025e2012-06-22 18:50:14 +10002202 sib_info = sib_buf->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002203 if (unlikely(
Nathan Scott89da0542006-03-17 17:28:40 +11002204 be32_to_cpu(sib_info->forw) != last_blkno ||
2205 sib_info->magic != dead_info->magic)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002206 XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
2207 XFS_ERRLEVEL_LOW, mp);
Dave Chinner24513372014-06-25 14:58:08 +10002208 error = -EFSCORRUPTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002209 goto done;
2210 }
Nathan Scott89da0542006-03-17 17:28:40 +11002211 sib_info->forw = cpu_to_be32(dead_blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +10002212 xfs_trans_log_buf(tp, sib_buf,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002213 XFS_DA_LOGRANGE(sib_info, &sib_info->forw,
2214 sizeof(sib_info->forw)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002215 sib_buf = NULL;
2216 }
2217 /*
2218 * If the moved block has a right sibling, fix up the pointers.
2219 */
Nathan Scott89da0542006-03-17 17:28:40 +11002220 if ((sib_blkno = be32_to_cpu(dead_info->forw))) {
Dave Chinner4bceb182013-10-29 22:11:51 +11002221 error = xfs_da3_node_read(tp, dp, sib_blkno, -1, &sib_buf, w);
Dave Chinner4bb20a82012-11-12 22:54:10 +11002222 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002223 goto done;
Dave Chinner1d9025e2012-06-22 18:50:14 +10002224 sib_info = sib_buf->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002225 if (unlikely(
Nathan Scott89da0542006-03-17 17:28:40 +11002226 be32_to_cpu(sib_info->back) != last_blkno ||
2227 sib_info->magic != dead_info->magic)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002228 XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
2229 XFS_ERRLEVEL_LOW, mp);
Dave Chinner24513372014-06-25 14:58:08 +10002230 error = -EFSCORRUPTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002231 goto done;
2232 }
Nathan Scott89da0542006-03-17 17:28:40 +11002233 sib_info->back = cpu_to_be32(dead_blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +10002234 xfs_trans_log_buf(tp, sib_buf,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002235 XFS_DA_LOGRANGE(sib_info, &sib_info->back,
2236 sizeof(sib_info->back)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002237 sib_buf = NULL;
2238 }
Dave Chinner7dda6e82014-06-06 15:11:18 +10002239 par_blkno = args->geo->leafblk;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002240 level = -1;
2241 /*
2242 * Walk down the tree looking for the parent of the moved block.
2243 */
2244 for (;;) {
Dave Chinner4bceb182013-10-29 22:11:51 +11002245 error = xfs_da3_node_read(tp, dp, par_blkno, -1, &par_buf, w);
Dave Chinner4bb20a82012-11-12 22:54:10 +11002246 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002247 goto done;
Dave Chinner1d9025e2012-06-22 18:50:14 +10002248 par_node = par_buf->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11002249 dp->d_ops->node_hdr_from_disk(&par_hdr, par_node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002250 if (level >= 0 && level != par_hdr.level + 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002251 XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
2252 XFS_ERRLEVEL_LOW, mp);
Dave Chinner24513372014-06-25 14:58:08 +10002253 error = -EFSCORRUPTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002254 goto done;
2255 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002256 level = par_hdr.level;
Dave Chinner4bceb182013-10-29 22:11:51 +11002257 btree = dp->d_ops->node_tree_p(par_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002258 for (entno = 0;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002259 entno < par_hdr.count &&
2260 be32_to_cpu(btree[entno].hashval) < dead_hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002261 entno++)
2262 continue;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002263 if (entno == par_hdr.count) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002264 XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
2265 XFS_ERRLEVEL_LOW, mp);
Dave Chinner24513372014-06-25 14:58:08 +10002266 error = -EFSCORRUPTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002267 goto done;
2268 }
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002269 par_blkno = be32_to_cpu(btree[entno].before);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002270 if (level == dead_level + 1)
2271 break;
Dave Chinner1d9025e2012-06-22 18:50:14 +10002272 xfs_trans_brelse(tp, par_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002273 par_buf = NULL;
2274 }
2275 /*
2276 * We're in the right parent block.
2277 * Look for the right entry.
2278 */
2279 for (;;) {
2280 for (;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002281 entno < par_hdr.count &&
2282 be32_to_cpu(btree[entno].before) != last_blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002283 entno++)
2284 continue;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002285 if (entno < par_hdr.count)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002286 break;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002287 par_blkno = par_hdr.forw;
Dave Chinner1d9025e2012-06-22 18:50:14 +10002288 xfs_trans_brelse(tp, par_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002289 par_buf = NULL;
2290 if (unlikely(par_blkno == 0)) {
2291 XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
2292 XFS_ERRLEVEL_LOW, mp);
Dave Chinner24513372014-06-25 14:58:08 +10002293 error = -EFSCORRUPTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002294 goto done;
2295 }
Dave Chinner4bceb182013-10-29 22:11:51 +11002296 error = xfs_da3_node_read(tp, dp, par_blkno, -1, &par_buf, w);
Dave Chinner4bb20a82012-11-12 22:54:10 +11002297 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002298 goto done;
Dave Chinner1d9025e2012-06-22 18:50:14 +10002299 par_node = par_buf->b_addr;
Dave Chinner01ba43b2013-10-29 22:11:52 +11002300 dp->d_ops->node_hdr_from_disk(&par_hdr, par_node);
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002301 if (par_hdr.level != level) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002302 XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
2303 XFS_ERRLEVEL_LOW, mp);
Dave Chinner24513372014-06-25 14:58:08 +10002304 error = -EFSCORRUPTED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002305 goto done;
2306 }
Dave Chinner4bceb182013-10-29 22:11:51 +11002307 btree = dp->d_ops->node_tree_p(par_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002308 entno = 0;
2309 }
2310 /*
2311 * Update the parent entry pointing to the moved block.
2312 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002313 btree[entno].before = cpu_to_be32(dead_blkno);
Dave Chinner1d9025e2012-06-22 18:50:14 +10002314 xfs_trans_log_buf(tp, par_buf,
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002315 XFS_DA_LOGRANGE(par_node, &btree[entno].before,
2316 sizeof(btree[entno].before)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002317 *dead_blknop = last_blkno;
2318 *dead_bufp = last_buf;
2319 return 0;
2320done:
2321 if (par_buf)
Dave Chinner1d9025e2012-06-22 18:50:14 +10002322 xfs_trans_brelse(tp, par_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002323 if (sib_buf)
Dave Chinner1d9025e2012-06-22 18:50:14 +10002324 xfs_trans_brelse(tp, sib_buf);
2325 xfs_trans_brelse(tp, last_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002326 return error;
2327}
2328
2329/*
2330 * Remove a btree block from a directory or attribute.
2331 */
2332int
Dave Chinner1d9025e2012-06-22 18:50:14 +10002333xfs_da_shrink_inode(
2334 xfs_da_args_t *args,
2335 xfs_dablk_t dead_blkno,
2336 struct xfs_buf *dead_buf)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002337{
2338 xfs_inode_t *dp;
2339 int done, error, w, count;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002340 xfs_trans_t *tp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002341
Dave Chinner5a5881c2012-03-22 05:15:13 +00002342 trace_xfs_da_shrink_inode(args);
2343
Linus Torvalds1da177e2005-04-16 15:20:36 -07002344 dp = args->dp;
2345 w = args->whichfork;
2346 tp = args->trans;
Dave Chinnerd6cf1302014-06-06 15:14:11 +10002347 count = args->geo->fsbcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002348 for (;;) {
2349 /*
2350 * Remove extents. If we get ENOSPC for a dir we have to move
2351 * the last block to the place we want to kill.
2352 */
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002353 error = xfs_bunmapi(tp, dp, dead_blkno, count,
2354 xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
2355 0, args->firstblock, args->flist, &done);
Dave Chinner24513372014-06-25 14:58:08 +10002356 if (error == -ENOSPC) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002357 if (w != XFS_DATA_FORK)
Nathan Scottf6c2d1f2006-06-20 13:04:51 +10002358 break;
Dave Chinnerf5ea1102013-04-24 18:58:02 +10002359 error = xfs_da3_swap_lastblock(args, &dead_blkno,
2360 &dead_buf);
2361 if (error)
Nathan Scottf6c2d1f2006-06-20 13:04:51 +10002362 break;
2363 } else {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002364 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002365 }
2366 }
Dave Chinner1d9025e2012-06-22 18:50:14 +10002367 xfs_trans_binval(tp, dead_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002368 return error;
2369}
2370
2371/*
2372 * See if the mapping(s) for this btree block are valid, i.e.
2373 * don't contain holes, are logically contiguous, and cover the whole range.
2374 */
2375STATIC int
2376xfs_da_map_covers_blocks(
2377 int nmap,
2378 xfs_bmbt_irec_t *mapp,
2379 xfs_dablk_t bno,
2380 int count)
2381{
2382 int i;
2383 xfs_fileoff_t off;
2384
2385 for (i = 0, off = bno; i < nmap; i++) {
2386 if (mapp[i].br_startblock == HOLESTARTBLOCK ||
2387 mapp[i].br_startblock == DELAYSTARTBLOCK) {
2388 return 0;
2389 }
2390 if (off != mapp[i].br_startoff) {
2391 return 0;
2392 }
2393 off += mapp[i].br_blockcount;
2394 }
2395 return off == bno + count;
2396}
2397
2398/*
Dave Chinner36054312012-06-22 18:50:13 +10002399 * Convert a struct xfs_bmbt_irec to a struct xfs_buf_map.
2400 *
2401 * For the single map case, it is assumed that the caller has provided a pointer
2402 * to a valid xfs_buf_map. For the multiple map case, this function will
2403 * allocate the xfs_buf_map to hold all the maps and replace the caller's single
2404 * map pointer with the allocated map.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002405 */
Dave Chinner36054312012-06-22 18:50:13 +10002406static int
2407xfs_buf_map_from_irec(
2408 struct xfs_mount *mp,
2409 struct xfs_buf_map **mapp,
Dave Chinner836a94a2013-08-12 20:49:44 +10002410 int *nmaps,
Dave Chinner36054312012-06-22 18:50:13 +10002411 struct xfs_bmbt_irec *irecs,
Dave Chinner836a94a2013-08-12 20:49:44 +10002412 int nirecs)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002413{
Dave Chinner36054312012-06-22 18:50:13 +10002414 struct xfs_buf_map *map;
2415 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002416
Dave Chinner36054312012-06-22 18:50:13 +10002417 ASSERT(*nmaps == 1);
2418 ASSERT(nirecs >= 1);
2419
2420 if (nirecs > 1) {
Dave Chinnerb17cb362013-05-20 09:51:12 +10002421 map = kmem_zalloc(nirecs * sizeof(struct xfs_buf_map),
2422 KM_SLEEP | KM_NOFS);
Dave Chinner36054312012-06-22 18:50:13 +10002423 if (!map)
Dave Chinner24513372014-06-25 14:58:08 +10002424 return -ENOMEM;
Dave Chinner36054312012-06-22 18:50:13 +10002425 *mapp = map;
2426 }
2427
2428 *nmaps = nirecs;
2429 map = *mapp;
2430 for (i = 0; i < *nmaps; i++) {
2431 ASSERT(irecs[i].br_startblock != DELAYSTARTBLOCK &&
2432 irecs[i].br_startblock != HOLESTARTBLOCK);
2433 map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);
2434 map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);
2435 }
2436 return 0;
2437}
2438
2439/*
2440 * Map the block we are given ready for reading. There are three possible return
2441 * values:
2442 * -1 - will be returned if we land in a hole and mappedbno == -2 so the
2443 * caller knows not to execute a subsequent read.
2444 * 0 - if we mapped the block successfully
2445 * >0 - positive error number if there was an error.
2446 */
2447static int
2448xfs_dabuf_map(
Dave Chinner36054312012-06-22 18:50:13 +10002449 struct xfs_inode *dp,
2450 xfs_dablk_t bno,
2451 xfs_daddr_t mappedbno,
2452 int whichfork,
2453 struct xfs_buf_map **map,
2454 int *nmaps)
2455{
2456 struct xfs_mount *mp = dp->i_mount;
2457 int nfsb;
2458 int error = 0;
2459 struct xfs_bmbt_irec irec;
2460 struct xfs_bmbt_irec *irecs = &irec;
2461 int nirecs;
2462
2463 ASSERT(map && *map);
2464 ASSERT(*nmaps == 1);
2465
Dave Chinnerd6cf1302014-06-06 15:14:11 +10002466 if (whichfork == XFS_DATA_FORK)
2467 nfsb = mp->m_dir_geo->fsbcount;
2468 else
2469 nfsb = mp->m_attr_geo->fsbcount;
Dave Chinner36054312012-06-22 18:50:13 +10002470
Linus Torvalds1da177e2005-04-16 15:20:36 -07002471 /*
2472 * Caller doesn't have a mapping. -2 means don't complain
2473 * if we land in a hole.
2474 */
2475 if (mappedbno == -1 || mappedbno == -2) {
2476 /*
2477 * Optimize the one-block case.
2478 */
Dave Chinner36054312012-06-22 18:50:13 +10002479 if (nfsb != 1)
Dave Chinnerb17cb362013-05-20 09:51:12 +10002480 irecs = kmem_zalloc(sizeof(irec) * nfsb,
2481 KM_SLEEP | KM_NOFS);
Dave Chinner5b777ad2011-09-18 20:40:46 +00002482
Dave Chinner36054312012-06-22 18:50:13 +10002483 nirecs = nfsb;
2484 error = xfs_bmapi_read(dp, (xfs_fileoff_t)bno, nfsb, irecs,
2485 &nirecs, xfs_bmapi_aflag(whichfork));
Dave Chinner5b777ad2011-09-18 20:40:46 +00002486 if (error)
Dave Chinner36054312012-06-22 18:50:13 +10002487 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002488 } else {
Dave Chinner36054312012-06-22 18:50:13 +10002489 irecs->br_startblock = XFS_DADDR_TO_FSB(mp, mappedbno);
2490 irecs->br_startoff = (xfs_fileoff_t)bno;
2491 irecs->br_blockcount = nfsb;
2492 irecs->br_state = 0;
2493 nirecs = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002494 }
Dave Chinner36054312012-06-22 18:50:13 +10002495
2496 if (!xfs_da_map_covers_blocks(nirecs, irecs, bno, nfsb)) {
Dave Chinner24513372014-06-25 14:58:08 +10002497 error = mappedbno == -2 ? -1 : -EFSCORRUPTED;
2498 if (unlikely(error == -EFSCORRUPTED)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002499 if (xfs_error_level >= XFS_ERRLEVEL_LOW) {
Dave Chinner36054312012-06-22 18:50:13 +10002500 int i;
Dave Chinner0b932cc2011-03-07 10:08:35 +11002501 xfs_alert(mp, "%s: bno %lld dir: inode %lld",
2502 __func__, (long long)bno,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002503 (long long)dp->i_ino);
Dave Chinner36054312012-06-22 18:50:13 +10002504 for (i = 0; i < *nmaps; i++) {
Dave Chinner0b932cc2011-03-07 10:08:35 +11002505 xfs_alert(mp,
2506"[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
Linus Torvalds1da177e2005-04-16 15:20:36 -07002507 i,
Dave Chinner36054312012-06-22 18:50:13 +10002508 (long long)irecs[i].br_startoff,
2509 (long long)irecs[i].br_startblock,
2510 (long long)irecs[i].br_blockcount,
2511 irecs[i].br_state);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002512 }
2513 }
2514 XFS_ERROR_REPORT("xfs_da_do_buf(1)",
2515 XFS_ERRLEVEL_LOW, mp);
2516 }
Dave Chinner36054312012-06-22 18:50:13 +10002517 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002518 }
Dave Chinner36054312012-06-22 18:50:13 +10002519 error = xfs_buf_map_from_irec(mp, map, nmaps, irecs, nirecs);
2520out:
2521 if (irecs != &irec)
2522 kmem_free(irecs);
2523 return error;
2524}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002525
Dave Chinner36054312012-06-22 18:50:13 +10002526/*
2527 * Get a buffer for the dir/attr block.
2528 */
2529int
2530xfs_da_get_buf(
2531 struct xfs_trans *trans,
2532 struct xfs_inode *dp,
2533 xfs_dablk_t bno,
2534 xfs_daddr_t mappedbno,
Dave Chinner1d9025e2012-06-22 18:50:14 +10002535 struct xfs_buf **bpp,
Dave Chinner36054312012-06-22 18:50:13 +10002536 int whichfork)
2537{
2538 struct xfs_buf *bp;
2539 struct xfs_buf_map map;
2540 struct xfs_buf_map *mapp;
2541 int nmap;
2542 int error;
2543
2544 *bpp = NULL;
2545 mapp = &map;
2546 nmap = 1;
Eric Sandeen9df2dd02014-04-14 19:01:59 +10002547 error = xfs_dabuf_map(dp, bno, mappedbno, whichfork,
Dave Chinner36054312012-06-22 18:50:13 +10002548 &mapp, &nmap);
2549 if (error) {
2550 /* mapping a hole is not an error, but we don't continue */
2551 if (error == -1)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002552 error = 0;
Dave Chinner36054312012-06-22 18:50:13 +10002553 goto out_free;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002554 }
Dave Chinner36054312012-06-22 18:50:13 +10002555
2556 bp = xfs_trans_get_buf_map(trans, dp->i_mount->m_ddev_targp,
2557 mapp, nmap, 0);
Dave Chinner24513372014-06-25 14:58:08 +10002558 error = bp ? bp->b_error : -EIO;
Dave Chinner36054312012-06-22 18:50:13 +10002559 if (error) {
Eric Sandeen6ee49a22014-10-02 09:23:49 +10002560 if (bp)
2561 xfs_trans_brelse(trans, bp);
Dave Chinner36054312012-06-22 18:50:13 +10002562 goto out_free;
2563 }
2564
Dave Chinner1d9025e2012-06-22 18:50:14 +10002565 *bpp = bp;
Dave Chinner36054312012-06-22 18:50:13 +10002566
2567out_free:
2568 if (mapp != &map)
2569 kmem_free(mapp);
2570
2571 return error;
2572}
2573
2574/*
2575 * Get a buffer for the dir/attr block, fill in the contents.
2576 */
2577int
2578xfs_da_read_buf(
2579 struct xfs_trans *trans,
2580 struct xfs_inode *dp,
2581 xfs_dablk_t bno,
2582 xfs_daddr_t mappedbno,
Dave Chinner1d9025e2012-06-22 18:50:14 +10002583 struct xfs_buf **bpp,
Dave Chinner4bb20a82012-11-12 22:54:10 +11002584 int whichfork,
Dave Chinner1813dd62012-11-14 17:54:40 +11002585 const struct xfs_buf_ops *ops)
Dave Chinner36054312012-06-22 18:50:13 +10002586{
2587 struct xfs_buf *bp;
2588 struct xfs_buf_map map;
2589 struct xfs_buf_map *mapp;
2590 int nmap;
2591 int error;
2592
2593 *bpp = NULL;
2594 mapp = &map;
2595 nmap = 1;
Eric Sandeen9df2dd02014-04-14 19:01:59 +10002596 error = xfs_dabuf_map(dp, bno, mappedbno, whichfork,
Dave Chinner36054312012-06-22 18:50:13 +10002597 &mapp, &nmap);
2598 if (error) {
2599 /* mapping a hole is not an error, but we don't continue */
2600 if (error == -1)
2601 error = 0;
2602 goto out_free;
2603 }
2604
2605 error = xfs_trans_read_buf_map(dp->i_mount, trans,
2606 dp->i_mount->m_ddev_targp,
Dave Chinner1813dd62012-11-14 17:54:40 +11002607 mapp, nmap, 0, &bp, ops);
Dave Chinner36054312012-06-22 18:50:13 +10002608 if (error)
2609 goto out_free;
2610
2611 if (whichfork == XFS_ATTR_FORK)
2612 xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002613 else
Dave Chinner36054312012-06-22 18:50:13 +10002614 xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
Dave Chinner1d9025e2012-06-22 18:50:14 +10002615 *bpp = bp;
Dave Chinner36054312012-06-22 18:50:13 +10002616out_free:
Linus Torvalds1da177e2005-04-16 15:20:36 -07002617 if (mapp != &map)
Denys Vlasenkof0e2d932008-05-19 16:31:57 +10002618 kmem_free(mapp);
Dave Chinner36054312012-06-22 18:50:13 +10002619
Linus Torvalds1da177e2005-04-16 15:20:36 -07002620 return error;
2621}
2622
2623/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07002624 * Readahead the dir/attr block.
2625 */
2626xfs_daddr_t
2627xfs_da_reada_buf(
Dave Chinner36054312012-06-22 18:50:13 +10002628 struct xfs_inode *dp,
2629 xfs_dablk_t bno,
Dave Chinnerda6958c2012-11-12 22:54:18 +11002630 xfs_daddr_t mappedbno,
Dave Chinner4bb20a82012-11-12 22:54:10 +11002631 int whichfork,
Dave Chinner1813dd62012-11-14 17:54:40 +11002632 const struct xfs_buf_ops *ops)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002633{
Dave Chinner36054312012-06-22 18:50:13 +10002634 struct xfs_buf_map map;
2635 struct xfs_buf_map *mapp;
2636 int nmap;
2637 int error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002638
Dave Chinner36054312012-06-22 18:50:13 +10002639 mapp = &map;
2640 nmap = 1;
Eric Sandeen9df2dd02014-04-14 19:01:59 +10002641 error = xfs_dabuf_map(dp, bno, mappedbno, whichfork,
Dave Chinner36054312012-06-22 18:50:13 +10002642 &mapp, &nmap);
2643 if (error) {
2644 /* mapping a hole is not an error, but we don't continue */
2645 if (error == -1)
2646 error = 0;
2647 goto out_free;
2648 }
2649
2650 mappedbno = mapp[0].bm_bn;
Dave Chinner1813dd62012-11-14 17:54:40 +11002651 xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap, ops);
Dave Chinner36054312012-06-22 18:50:13 +10002652
2653out_free:
2654 if (mapp != &map)
2655 kmem_free(mapp);
2656
2657 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002658 return -1;
Dave Chinner36054312012-06-22 18:50:13 +10002659 return mappedbno;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002660}