blob: 73e53009e126d8174c22828e107300386a82cf51 [file] [log] [blame]
Chris Mason6cbd5572007-06-12 09:07:21 -04001/*
Chris Masond352ac62008-09-29 15:18:18 -04002 * Copyright (C) 2007,2008 Oracle. All rights reserved.
Chris Mason6cbd5572007-06-12 09:07:21 -04003 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
17 */
18
Chris Masona6b6e752007-10-15 16:22:39 -040019#include <linux/sched.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090020#include <linux/slab.h>
Chris Masoneb60cea2007-02-02 09:18:22 -050021#include "ctree.h"
22#include "disk-io.h"
Chris Mason7f5c1512007-03-23 15:56:19 -040023#include "transaction.h"
Chris Mason5f39d392007-10-15 16:14:19 -040024#include "print-tree.h"
Chris Mason925baed2008-06-25 16:01:30 -040025#include "locking.h"
Chris Mason9a8dd152007-02-23 08:38:36 -050026
Chris Masone089f052007-03-16 16:20:31 -040027static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
28 *root, struct btrfs_path *path, int level);
29static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Masond4dbff92007-04-04 14:08:15 -040030 *root, struct btrfs_key *ins_key,
Chris Masoncc0c5532007-10-25 15:42:57 -040031 struct btrfs_path *path, int data_size, int extend);
Chris Mason5f39d392007-10-15 16:14:19 -040032static int push_node_left(struct btrfs_trans_handle *trans,
33 struct btrfs_root *root, struct extent_buffer *dst,
Chris Mason971a1f62008-04-24 10:54:32 -040034 struct extent_buffer *src, int empty);
Chris Mason5f39d392007-10-15 16:14:19 -040035static int balance_node_right(struct btrfs_trans_handle *trans,
36 struct btrfs_root *root,
37 struct extent_buffer *dst_buf,
38 struct extent_buffer *src_buf);
Chris Masone089f052007-03-16 16:20:31 -040039static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
40 struct btrfs_path *path, int level, int slot);
Yan, Zhengad48fd752009-11-12 09:33:58 +000041static int setup_items_for_insert(struct btrfs_trans_handle *trans,
42 struct btrfs_root *root, struct btrfs_path *path,
43 struct btrfs_key *cpu_key, u32 *data_size,
44 u32 total_data, u32 total_size, int nr);
45
Chris Masond97e63b2007-02-20 16:40:44 -050046
Chris Mason2c90e5d2007-04-02 10:50:19 -040047struct btrfs_path *btrfs_alloc_path(void)
48{
Chris Masondf24a2b2007-04-04 09:36:31 -040049 struct btrfs_path *path;
Jeff Mahoneye00f7302009-02-12 14:11:25 -050050 path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
51 if (path)
Chris Mason2cc58cf2007-08-27 16:49:44 -040052 path->reada = 1;
Chris Masondf24a2b2007-04-04 09:36:31 -040053 return path;
Chris Mason2c90e5d2007-04-02 10:50:19 -040054}
55
Chris Masonb4ce94d2009-02-04 09:25:08 -050056/*
57 * set all locked nodes in the path to blocking locks. This should
58 * be done before scheduling
59 */
60noinline void btrfs_set_path_blocking(struct btrfs_path *p)
61{
62 int i;
63 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
64 if (p->nodes[i] && p->locks[i])
65 btrfs_set_lock_blocking(p->nodes[i]);
66 }
67}
68
69/*
70 * reset all the locked nodes in the patch to spinning locks.
Chris Mason4008c042009-02-12 14:09:45 -050071 *
72 * held is used to keep lockdep happy, when lockdep is enabled
73 * we set held to a blocking lock before we go around and
74 * retake all the spinlocks in the path. You can safely use NULL
75 * for held
Chris Masonb4ce94d2009-02-04 09:25:08 -050076 */
Chris Mason4008c042009-02-12 14:09:45 -050077noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
78 struct extent_buffer *held)
Chris Masonb4ce94d2009-02-04 09:25:08 -050079{
80 int i;
Chris Mason4008c042009-02-12 14:09:45 -050081
82#ifdef CONFIG_DEBUG_LOCK_ALLOC
83 /* lockdep really cares that we take all of these spinlocks
84 * in the right order. If any of the locks in the path are not
85 * currently blocking, it is going to complain. So, make really
86 * really sure by forcing the path to blocking before we clear
87 * the path blocking.
88 */
89 if (held)
90 btrfs_set_lock_blocking(held);
91 btrfs_set_path_blocking(p);
92#endif
93
94 for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
Chris Masonb4ce94d2009-02-04 09:25:08 -050095 if (p->nodes[i] && p->locks[i])
96 btrfs_clear_lock_blocking(p->nodes[i]);
97 }
Chris Mason4008c042009-02-12 14:09:45 -050098
99#ifdef CONFIG_DEBUG_LOCK_ALLOC
100 if (held)
101 btrfs_clear_lock_blocking(held);
102#endif
Chris Masonb4ce94d2009-02-04 09:25:08 -0500103}
104
Chris Masond352ac62008-09-29 15:18:18 -0400105/* this also releases the path */
Chris Mason2c90e5d2007-04-02 10:50:19 -0400106void btrfs_free_path(struct btrfs_path *p)
107{
Jesper Juhlff175d52010-12-25 21:22:30 +0000108 if (!p)
109 return;
Chris Masondf24a2b2007-04-04 09:36:31 -0400110 btrfs_release_path(NULL, p);
Chris Mason2c90e5d2007-04-02 10:50:19 -0400111 kmem_cache_free(btrfs_path_cachep, p);
112}
113
Chris Masond352ac62008-09-29 15:18:18 -0400114/*
115 * path release drops references on the extent buffers in the path
116 * and it drops any locks held by this path
117 *
118 * It is safe to call this on paths that no locks or extent buffers held.
119 */
Chris Masond3977122009-01-05 21:25:51 -0500120noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
Chris Masoneb60cea2007-02-02 09:18:22 -0500121{
122 int i;
Chris Masona2135012008-06-25 16:01:30 -0400123
Chris Mason234b63a2007-03-13 10:46:10 -0400124 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
Chris Mason3f157a22008-06-25 16:01:31 -0400125 p->slots[i] = 0;
Chris Masoneb60cea2007-02-02 09:18:22 -0500126 if (!p->nodes[i])
Chris Mason925baed2008-06-25 16:01:30 -0400127 continue;
128 if (p->locks[i]) {
129 btrfs_tree_unlock(p->nodes[i]);
130 p->locks[i] = 0;
131 }
Chris Mason5f39d392007-10-15 16:14:19 -0400132 free_extent_buffer(p->nodes[i]);
Chris Mason3f157a22008-06-25 16:01:31 -0400133 p->nodes[i] = NULL;
Chris Masoneb60cea2007-02-02 09:18:22 -0500134 }
135}
136
Chris Masond352ac62008-09-29 15:18:18 -0400137/*
138 * safely gets a reference on the root node of a tree. A lock
139 * is not taken, so a concurrent writer may put a different node
140 * at the root of the tree. See btrfs_lock_root_node for the
141 * looping required.
142 *
143 * The extent buffer returned by this has a reference taken, so
144 * it won't disappear. It may stop being the root of the tree
145 * at any time because there are no locks held.
146 */
Chris Mason925baed2008-06-25 16:01:30 -0400147struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
148{
149 struct extent_buffer *eb;
150 spin_lock(&root->node_lock);
151 eb = root->node;
152 extent_buffer_get(eb);
153 spin_unlock(&root->node_lock);
154 return eb;
155}
156
Chris Masond352ac62008-09-29 15:18:18 -0400157/* loop around taking references on and locking the root node of the
158 * tree until you end up with a lock on the root. A locked buffer
159 * is returned, with a reference held.
160 */
Chris Mason925baed2008-06-25 16:01:30 -0400161struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
162{
163 struct extent_buffer *eb;
164
Chris Masond3977122009-01-05 21:25:51 -0500165 while (1) {
Chris Mason925baed2008-06-25 16:01:30 -0400166 eb = btrfs_root_node(root);
167 btrfs_tree_lock(eb);
168
169 spin_lock(&root->node_lock);
170 if (eb == root->node) {
171 spin_unlock(&root->node_lock);
172 break;
173 }
174 spin_unlock(&root->node_lock);
175
176 btrfs_tree_unlock(eb);
177 free_extent_buffer(eb);
178 }
179 return eb;
180}
181
Chris Masond352ac62008-09-29 15:18:18 -0400182/* cowonly root (everything not a reference counted cow subvolume), just get
183 * put onto a simple dirty list. transaction.c walks this to make sure they
184 * get properly updated on disk.
185 */
Chris Mason0b86a832008-03-24 15:01:56 -0400186static void add_root_to_dirty_list(struct btrfs_root *root)
187{
188 if (root->track_dirty && list_empty(&root->dirty_list)) {
189 list_add(&root->dirty_list,
190 &root->fs_info->dirty_cowonly_roots);
191 }
192}
193
Chris Masond352ac62008-09-29 15:18:18 -0400194/*
195 * used by snapshot creation to make a copy of a root for a tree with
196 * a given objectid. The buffer with the new root node is returned in
197 * cow_ret, and this func returns zero on success or a negative error code.
198 */
Chris Masonbe20aa92007-12-17 20:14:01 -0500199int btrfs_copy_root(struct btrfs_trans_handle *trans,
200 struct btrfs_root *root,
201 struct extent_buffer *buf,
202 struct extent_buffer **cow_ret, u64 new_root_objectid)
203{
204 struct extent_buffer *cow;
Chris Masonbe20aa92007-12-17 20:14:01 -0500205 int ret = 0;
206 int level;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400207 struct btrfs_disk_key disk_key;
Chris Masonbe20aa92007-12-17 20:14:01 -0500208
209 WARN_ON(root->ref_cows && trans->transid !=
210 root->fs_info->running_transaction->transid);
211 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
212
213 level = btrfs_header_level(buf);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400214 if (level == 0)
215 btrfs_item_key(buf, &disk_key, 0);
216 else
217 btrfs_node_key(buf, &disk_key, 0);
Zheng Yan31840ae2008-09-23 13:14:14 -0400218
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400219 cow = btrfs_alloc_free_block(trans, root, buf->len, 0,
220 new_root_objectid, &disk_key, level,
221 buf->start, 0);
222 if (IS_ERR(cow))
Chris Masonbe20aa92007-12-17 20:14:01 -0500223 return PTR_ERR(cow);
224
225 copy_extent_buffer(cow, buf, 0, 0, cow->len);
226 btrfs_set_header_bytenr(cow, cow->start);
227 btrfs_set_header_generation(cow, trans->transid);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400228 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
229 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
230 BTRFS_HEADER_FLAG_RELOC);
231 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
232 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
233 else
234 btrfs_set_header_owner(cow, new_root_objectid);
Chris Masonbe20aa92007-12-17 20:14:01 -0500235
Yan Zheng2b820322008-11-17 21:11:30 -0500236 write_extent_buffer(cow, root->fs_info->fsid,
237 (unsigned long)btrfs_header_fsid(cow),
238 BTRFS_FSID_SIZE);
239
Chris Masonbe20aa92007-12-17 20:14:01 -0500240 WARN_ON(btrfs_header_generation(buf) > trans->transid);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400241 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
242 ret = btrfs_inc_ref(trans, root, cow, 1);
243 else
244 ret = btrfs_inc_ref(trans, root, cow, 0);
Chris Mason4aec2b52007-12-18 16:25:45 -0500245
Chris Masonbe20aa92007-12-17 20:14:01 -0500246 if (ret)
247 return ret;
248
249 btrfs_mark_buffer_dirty(cow);
250 *cow_ret = cow;
251 return 0;
252}
253
Chris Masond352ac62008-09-29 15:18:18 -0400254/*
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400255 * check if the tree block can be shared by multiple trees
256 */
257int btrfs_block_can_be_shared(struct btrfs_root *root,
258 struct extent_buffer *buf)
259{
260 /*
261 * Tree blocks not in refernece counted trees and tree roots
262 * are never shared. If a block was allocated after the last
263 * snapshot and the block was not allocated by tree relocation,
264 * we know the block is not shared.
265 */
266 if (root->ref_cows &&
267 buf != root->node && buf != root->commit_root &&
268 (btrfs_header_generation(buf) <=
269 btrfs_root_last_snapshot(&root->root_item) ||
270 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
271 return 1;
272#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
273 if (root->ref_cows &&
274 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
275 return 1;
276#endif
277 return 0;
278}
279
280static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
281 struct btrfs_root *root,
282 struct extent_buffer *buf,
Yan, Zhengf0486c62010-05-16 10:46:25 -0400283 struct extent_buffer *cow,
284 int *last_ref)
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400285{
286 u64 refs;
287 u64 owner;
288 u64 flags;
289 u64 new_flags = 0;
290 int ret;
291
292 /*
293 * Backrefs update rules:
294 *
295 * Always use full backrefs for extent pointers in tree block
296 * allocated by tree relocation.
297 *
298 * If a shared tree block is no longer referenced by its owner
299 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
300 * use full backrefs for extent pointers in tree block.
301 *
302 * If a tree block is been relocating
303 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
304 * use full backrefs for extent pointers in tree block.
305 * The reason for this is some operations (such as drop tree)
306 * are only allowed for blocks use full backrefs.
307 */
308
309 if (btrfs_block_can_be_shared(root, buf)) {
310 ret = btrfs_lookup_extent_info(trans, root, buf->start,
311 buf->len, &refs, &flags);
312 BUG_ON(ret);
313 BUG_ON(refs == 0);
314 } else {
315 refs = 1;
316 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
317 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
318 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
319 else
320 flags = 0;
321 }
322
323 owner = btrfs_header_owner(buf);
324 BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
325 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
326
327 if (refs > 1) {
328 if ((owner == root->root_key.objectid ||
329 root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
330 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
331 ret = btrfs_inc_ref(trans, root, buf, 1);
332 BUG_ON(ret);
333
334 if (root->root_key.objectid ==
335 BTRFS_TREE_RELOC_OBJECTID) {
336 ret = btrfs_dec_ref(trans, root, buf, 0);
337 BUG_ON(ret);
338 ret = btrfs_inc_ref(trans, root, cow, 1);
339 BUG_ON(ret);
340 }
341 new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
342 } else {
343
344 if (root->root_key.objectid ==
345 BTRFS_TREE_RELOC_OBJECTID)
346 ret = btrfs_inc_ref(trans, root, cow, 1);
347 else
348 ret = btrfs_inc_ref(trans, root, cow, 0);
349 BUG_ON(ret);
350 }
351 if (new_flags != 0) {
352 ret = btrfs_set_disk_extent_flags(trans, root,
353 buf->start,
354 buf->len,
355 new_flags, 0);
356 BUG_ON(ret);
357 }
358 } else {
359 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
360 if (root->root_key.objectid ==
361 BTRFS_TREE_RELOC_OBJECTID)
362 ret = btrfs_inc_ref(trans, root, cow, 1);
363 else
364 ret = btrfs_inc_ref(trans, root, cow, 0);
365 BUG_ON(ret);
366 ret = btrfs_dec_ref(trans, root, buf, 1);
367 BUG_ON(ret);
368 }
369 clean_tree_block(trans, root, buf);
Yan, Zhengf0486c62010-05-16 10:46:25 -0400370 *last_ref = 1;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400371 }
372 return 0;
373}
374
375/*
Chris Masond3977122009-01-05 21:25:51 -0500376 * does the dirty work in cow of a single block. The parent block (if
377 * supplied) is updated to point to the new cow copy. The new buffer is marked
378 * dirty and returned locked. If you modify the block it needs to be marked
379 * dirty again.
Chris Masond352ac62008-09-29 15:18:18 -0400380 *
381 * search_start -- an allocation hint for the new block
382 *
Chris Masond3977122009-01-05 21:25:51 -0500383 * empty_size -- a hint that you plan on doing more cow. This is the size in
384 * bytes the allocator should try to find free next to the block it returns.
385 * This is just a hint and may be ignored by the allocator.
Chris Masond352ac62008-09-29 15:18:18 -0400386 */
Chris Masond3977122009-01-05 21:25:51 -0500387static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
Chris Mason5f39d392007-10-15 16:14:19 -0400388 struct btrfs_root *root,
389 struct extent_buffer *buf,
390 struct extent_buffer *parent, int parent_slot,
391 struct extent_buffer **cow_ret,
Chris Mason9fa8cfe2009-03-13 10:24:59 -0400392 u64 search_start, u64 empty_size)
Chris Mason6702ed42007-08-07 16:15:09 -0400393{
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400394 struct btrfs_disk_key disk_key;
Chris Mason5f39d392007-10-15 16:14:19 -0400395 struct extent_buffer *cow;
Chris Mason7bb86312007-12-11 09:25:06 -0500396 int level;
Yan, Zhengf0486c62010-05-16 10:46:25 -0400397 int last_ref = 0;
Chris Mason925baed2008-06-25 16:01:30 -0400398 int unlock_orig = 0;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400399 u64 parent_start;
Chris Mason6702ed42007-08-07 16:15:09 -0400400
Chris Mason925baed2008-06-25 16:01:30 -0400401 if (*cow_ret == buf)
402 unlock_orig = 1;
403
Chris Masonb9447ef2009-03-09 11:45:38 -0400404 btrfs_assert_tree_locked(buf);
Chris Mason925baed2008-06-25 16:01:30 -0400405
Chris Mason7bb86312007-12-11 09:25:06 -0500406 WARN_ON(root->ref_cows && trans->transid !=
407 root->fs_info->running_transaction->transid);
Chris Mason6702ed42007-08-07 16:15:09 -0400408 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
Chris Mason5f39d392007-10-15 16:14:19 -0400409
Chris Mason7bb86312007-12-11 09:25:06 -0500410 level = btrfs_header_level(buf);
Zheng Yan31840ae2008-09-23 13:14:14 -0400411
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400412 if (level == 0)
413 btrfs_item_key(buf, &disk_key, 0);
414 else
415 btrfs_node_key(buf, &disk_key, 0);
416
417 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
418 if (parent)
419 parent_start = parent->start;
420 else
421 parent_start = 0;
422 } else
423 parent_start = 0;
424
425 cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start,
426 root->root_key.objectid, &disk_key,
427 level, search_start, empty_size);
Chris Mason6702ed42007-08-07 16:15:09 -0400428 if (IS_ERR(cow))
429 return PTR_ERR(cow);
430
Chris Masonb4ce94d2009-02-04 09:25:08 -0500431 /* cow is set to blocking by btrfs_init_new_buffer */
432
Chris Mason5f39d392007-10-15 16:14:19 -0400433 copy_extent_buffer(cow, buf, 0, 0, cow->len);
Chris Masondb945352007-10-15 16:15:53 -0400434 btrfs_set_header_bytenr(cow, cow->start);
Chris Mason5f39d392007-10-15 16:14:19 -0400435 btrfs_set_header_generation(cow, trans->transid);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400436 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
437 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
438 BTRFS_HEADER_FLAG_RELOC);
439 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
440 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
441 else
442 btrfs_set_header_owner(cow, root->root_key.objectid);
Chris Mason6702ed42007-08-07 16:15:09 -0400443
Yan Zheng2b820322008-11-17 21:11:30 -0500444 write_extent_buffer(cow, root->fs_info->fsid,
445 (unsigned long)btrfs_header_fsid(cow),
446 BTRFS_FSID_SIZE);
447
Yan, Zhengf0486c62010-05-16 10:46:25 -0400448 update_ref_for_cow(trans, root, buf, cow, &last_ref);
Zheng Yan1a40e232008-09-26 10:09:34 -0400449
Yan, Zheng3fd0a552010-05-16 10:49:59 -0400450 if (root->ref_cows)
451 btrfs_reloc_cow_block(trans, root, buf, cow);
452
Chris Mason6702ed42007-08-07 16:15:09 -0400453 if (buf == root->node) {
Chris Mason925baed2008-06-25 16:01:30 -0400454 WARN_ON(parent && parent != buf);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400455 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
456 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
457 parent_start = buf->start;
458 else
459 parent_start = 0;
Chris Mason925baed2008-06-25 16:01:30 -0400460
461 spin_lock(&root->node_lock);
Chris Mason6702ed42007-08-07 16:15:09 -0400462 root->node = cow;
Chris Mason5f39d392007-10-15 16:14:19 -0400463 extent_buffer_get(cow);
Chris Mason925baed2008-06-25 16:01:30 -0400464 spin_unlock(&root->node_lock);
465
Yan, Zhengf0486c62010-05-16 10:46:25 -0400466 btrfs_free_tree_block(trans, root, buf, parent_start,
467 last_ref);
Chris Mason5f39d392007-10-15 16:14:19 -0400468 free_extent_buffer(buf);
Chris Mason0b86a832008-03-24 15:01:56 -0400469 add_root_to_dirty_list(root);
Chris Mason6702ed42007-08-07 16:15:09 -0400470 } else {
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400471 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
472 parent_start = parent->start;
473 else
474 parent_start = 0;
475
476 WARN_ON(trans->transid != btrfs_header_generation(parent));
Chris Mason5f39d392007-10-15 16:14:19 -0400477 btrfs_set_node_blockptr(parent, parent_slot,
Chris Masondb945352007-10-15 16:15:53 -0400478 cow->start);
Chris Mason74493f72007-12-11 09:25:06 -0500479 btrfs_set_node_ptr_generation(parent, parent_slot,
480 trans->transid);
Chris Mason6702ed42007-08-07 16:15:09 -0400481 btrfs_mark_buffer_dirty(parent);
Yan, Zhengf0486c62010-05-16 10:46:25 -0400482 btrfs_free_tree_block(trans, root, buf, parent_start,
483 last_ref);
Chris Mason6702ed42007-08-07 16:15:09 -0400484 }
Chris Mason925baed2008-06-25 16:01:30 -0400485 if (unlock_orig)
486 btrfs_tree_unlock(buf);
Chris Mason5f39d392007-10-15 16:14:19 -0400487 free_extent_buffer(buf);
Chris Mason6702ed42007-08-07 16:15:09 -0400488 btrfs_mark_buffer_dirty(cow);
489 *cow_ret = cow;
490 return 0;
491}
492
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400493static inline int should_cow_block(struct btrfs_trans_handle *trans,
494 struct btrfs_root *root,
495 struct extent_buffer *buf)
496{
497 if (btrfs_header_generation(buf) == trans->transid &&
498 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
499 !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
500 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
501 return 0;
502 return 1;
503}
504
Chris Masond352ac62008-09-29 15:18:18 -0400505/*
506 * cows a single block, see __btrfs_cow_block for the real work.
507 * This version of it has extra checks so that a block isn't cow'd more than
508 * once per transaction, as long as it hasn't been written yet
509 */
Chris Masond3977122009-01-05 21:25:51 -0500510noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
Chris Mason5f39d392007-10-15 16:14:19 -0400511 struct btrfs_root *root, struct extent_buffer *buf,
512 struct extent_buffer *parent, int parent_slot,
Chris Mason9fa8cfe2009-03-13 10:24:59 -0400513 struct extent_buffer **cow_ret)
Chris Mason02217ed2007-03-02 16:08:05 -0500514{
Chris Mason6702ed42007-08-07 16:15:09 -0400515 u64 search_start;
Chris Masonf510cfe2007-10-15 16:14:48 -0400516 int ret;
Chris Masondc17ff82008-01-08 15:46:30 -0500517
Chris Masonccd467d2007-06-28 15:57:36 -0400518 if (trans->transaction != root->fs_info->running_transaction) {
Chris Masond3977122009-01-05 21:25:51 -0500519 printk(KERN_CRIT "trans %llu running %llu\n",
520 (unsigned long long)trans->transid,
521 (unsigned long long)
Chris Masonccd467d2007-06-28 15:57:36 -0400522 root->fs_info->running_transaction->transid);
523 WARN_ON(1);
524 }
525 if (trans->transid != root->fs_info->generation) {
Chris Masond3977122009-01-05 21:25:51 -0500526 printk(KERN_CRIT "trans %llu running %llu\n",
527 (unsigned long long)trans->transid,
528 (unsigned long long)root->fs_info->generation);
Chris Masonccd467d2007-06-28 15:57:36 -0400529 WARN_ON(1);
530 }
Chris Masondc17ff82008-01-08 15:46:30 -0500531
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400532 if (!should_cow_block(trans, root, buf)) {
Chris Mason02217ed2007-03-02 16:08:05 -0500533 *cow_ret = buf;
534 return 0;
535 }
Chris Masonc4876852009-02-04 09:24:25 -0500536
Chris Mason0b86a832008-03-24 15:01:56 -0400537 search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
Chris Masonb4ce94d2009-02-04 09:25:08 -0500538
539 if (parent)
540 btrfs_set_lock_blocking(parent);
541 btrfs_set_lock_blocking(buf);
542
Chris Masonf510cfe2007-10-15 16:14:48 -0400543 ret = __btrfs_cow_block(trans, root, buf, parent,
Chris Mason9fa8cfe2009-03-13 10:24:59 -0400544 parent_slot, cow_ret, search_start, 0);
Chris Masonf510cfe2007-10-15 16:14:48 -0400545 return ret;
Chris Mason6702ed42007-08-07 16:15:09 -0400546}
547
Chris Masond352ac62008-09-29 15:18:18 -0400548/*
549 * helper function for defrag to decide if two blocks pointed to by a
550 * node are actually close by
551 */
Chris Mason6b800532007-10-15 16:17:34 -0400552static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
Chris Mason6702ed42007-08-07 16:15:09 -0400553{
Chris Mason6b800532007-10-15 16:17:34 -0400554 if (blocknr < other && other - (blocknr + blocksize) < 32768)
Chris Mason6702ed42007-08-07 16:15:09 -0400555 return 1;
Chris Mason6b800532007-10-15 16:17:34 -0400556 if (blocknr > other && blocknr - (other + blocksize) < 32768)
Chris Mason6702ed42007-08-07 16:15:09 -0400557 return 1;
Chris Mason02217ed2007-03-02 16:08:05 -0500558 return 0;
559}
560
Chris Mason081e9572007-11-06 10:26:24 -0500561/*
562 * compare two keys in a memcmp fashion
563 */
564static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
565{
566 struct btrfs_key k1;
567
568 btrfs_disk_key_to_cpu(&k1, disk);
569
Diego Calleja20736ab2009-07-24 11:06:52 -0400570 return btrfs_comp_cpu_keys(&k1, k2);
Chris Mason081e9572007-11-06 10:26:24 -0500571}
572
Josef Bacikf3465ca2008-11-12 14:19:50 -0500573/*
574 * same as comp_keys only with two btrfs_key's
575 */
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400576int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
Josef Bacikf3465ca2008-11-12 14:19:50 -0500577{
578 if (k1->objectid > k2->objectid)
579 return 1;
580 if (k1->objectid < k2->objectid)
581 return -1;
582 if (k1->type > k2->type)
583 return 1;
584 if (k1->type < k2->type)
585 return -1;
586 if (k1->offset > k2->offset)
587 return 1;
588 if (k1->offset < k2->offset)
589 return -1;
590 return 0;
591}
Chris Mason081e9572007-11-06 10:26:24 -0500592
Chris Masond352ac62008-09-29 15:18:18 -0400593/*
594 * this is used by the defrag code to go through all the
595 * leaves pointed to by a node and reallocate them so that
596 * disk order is close to key order
597 */
Chris Mason6702ed42007-08-07 16:15:09 -0400598int btrfs_realloc_node(struct btrfs_trans_handle *trans,
Chris Mason5f39d392007-10-15 16:14:19 -0400599 struct btrfs_root *root, struct extent_buffer *parent,
Chris Masona6b6e752007-10-15 16:22:39 -0400600 int start_slot, int cache_only, u64 *last_ret,
601 struct btrfs_key *progress)
Chris Mason6702ed42007-08-07 16:15:09 -0400602{
Chris Mason6b800532007-10-15 16:17:34 -0400603 struct extent_buffer *cur;
Chris Mason6702ed42007-08-07 16:15:09 -0400604 u64 blocknr;
Chris Masonca7a79a2008-05-12 12:59:19 -0400605 u64 gen;
Chris Masone9d0b132007-08-10 14:06:19 -0400606 u64 search_start = *last_ret;
607 u64 last_block = 0;
Chris Mason6702ed42007-08-07 16:15:09 -0400608 u64 other;
609 u32 parent_nritems;
Chris Mason6702ed42007-08-07 16:15:09 -0400610 int end_slot;
611 int i;
612 int err = 0;
Chris Masonf2183bd2007-08-10 14:42:37 -0400613 int parent_level;
Chris Mason6b800532007-10-15 16:17:34 -0400614 int uptodate;
615 u32 blocksize;
Chris Mason081e9572007-11-06 10:26:24 -0500616 int progress_passed = 0;
617 struct btrfs_disk_key disk_key;
Chris Mason6702ed42007-08-07 16:15:09 -0400618
Chris Mason5708b952007-10-25 15:43:18 -0400619 parent_level = btrfs_header_level(parent);
620 if (cache_only && parent_level != 1)
621 return 0;
622
Chris Masond3977122009-01-05 21:25:51 -0500623 if (trans->transaction != root->fs_info->running_transaction)
Chris Mason6702ed42007-08-07 16:15:09 -0400624 WARN_ON(1);
Chris Masond3977122009-01-05 21:25:51 -0500625 if (trans->transid != root->fs_info->generation)
Chris Mason6702ed42007-08-07 16:15:09 -0400626 WARN_ON(1);
Chris Mason86479a02007-09-10 19:58:16 -0400627
Chris Mason6b800532007-10-15 16:17:34 -0400628 parent_nritems = btrfs_header_nritems(parent);
Chris Mason6b800532007-10-15 16:17:34 -0400629 blocksize = btrfs_level_size(root, parent_level - 1);
Chris Mason6702ed42007-08-07 16:15:09 -0400630 end_slot = parent_nritems;
631
632 if (parent_nritems == 1)
633 return 0;
634
Chris Masonb4ce94d2009-02-04 09:25:08 -0500635 btrfs_set_lock_blocking(parent);
636
Chris Mason6702ed42007-08-07 16:15:09 -0400637 for (i = start_slot; i < end_slot; i++) {
638 int close = 1;
Chris Masona6b6e752007-10-15 16:22:39 -0400639
Chris Mason5708b952007-10-25 15:43:18 -0400640 if (!parent->map_token) {
641 map_extent_buffer(parent,
642 btrfs_node_key_ptr_offset(i),
643 sizeof(struct btrfs_key_ptr),
644 &parent->map_token, &parent->kaddr,
645 &parent->map_start, &parent->map_len,
646 KM_USER1);
647 }
Chris Mason081e9572007-11-06 10:26:24 -0500648 btrfs_node_key(parent, &disk_key, i);
649 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
650 continue;
651
652 progress_passed = 1;
Chris Mason6b800532007-10-15 16:17:34 -0400653 blocknr = btrfs_node_blockptr(parent, i);
Chris Masonca7a79a2008-05-12 12:59:19 -0400654 gen = btrfs_node_ptr_generation(parent, i);
Chris Masone9d0b132007-08-10 14:06:19 -0400655 if (last_block == 0)
656 last_block = blocknr;
Chris Mason5708b952007-10-25 15:43:18 -0400657
Chris Mason6702ed42007-08-07 16:15:09 -0400658 if (i > 0) {
Chris Mason6b800532007-10-15 16:17:34 -0400659 other = btrfs_node_blockptr(parent, i - 1);
660 close = close_blocks(blocknr, other, blocksize);
Chris Mason6702ed42007-08-07 16:15:09 -0400661 }
Chris Mason0ef3e662008-05-24 14:04:53 -0400662 if (!close && i < end_slot - 2) {
Chris Mason6b800532007-10-15 16:17:34 -0400663 other = btrfs_node_blockptr(parent, i + 1);
664 close = close_blocks(blocknr, other, blocksize);
Chris Mason6702ed42007-08-07 16:15:09 -0400665 }
Chris Masone9d0b132007-08-10 14:06:19 -0400666 if (close) {
667 last_block = blocknr;
Chris Mason6702ed42007-08-07 16:15:09 -0400668 continue;
Chris Masone9d0b132007-08-10 14:06:19 -0400669 }
Chris Mason5708b952007-10-25 15:43:18 -0400670 if (parent->map_token) {
671 unmap_extent_buffer(parent, parent->map_token,
672 KM_USER1);
673 parent->map_token = NULL;
674 }
Chris Mason6702ed42007-08-07 16:15:09 -0400675
Chris Mason6b800532007-10-15 16:17:34 -0400676 cur = btrfs_find_tree_block(root, blocknr, blocksize);
677 if (cur)
Chris Mason1259ab72008-05-12 13:39:03 -0400678 uptodate = btrfs_buffer_uptodate(cur, gen);
Chris Mason6b800532007-10-15 16:17:34 -0400679 else
680 uptodate = 0;
Chris Mason5708b952007-10-25 15:43:18 -0400681 if (!cur || !uptodate) {
Chris Mason6702ed42007-08-07 16:15:09 -0400682 if (cache_only) {
Chris Mason6b800532007-10-15 16:17:34 -0400683 free_extent_buffer(cur);
Chris Mason6702ed42007-08-07 16:15:09 -0400684 continue;
685 }
Chris Mason6b800532007-10-15 16:17:34 -0400686 if (!cur) {
687 cur = read_tree_block(root, blocknr,
Chris Masonca7a79a2008-05-12 12:59:19 -0400688 blocksize, gen);
Chris Mason6b800532007-10-15 16:17:34 -0400689 } else if (!uptodate) {
Chris Masonca7a79a2008-05-12 12:59:19 -0400690 btrfs_read_buffer(cur, gen);
Chris Masonf2183bd2007-08-10 14:42:37 -0400691 }
Chris Mason6702ed42007-08-07 16:15:09 -0400692 }
Chris Masone9d0b132007-08-10 14:06:19 -0400693 if (search_start == 0)
Chris Mason6b800532007-10-15 16:17:34 -0400694 search_start = last_block;
Chris Masone9d0b132007-08-10 14:06:19 -0400695
Chris Masone7a84562008-06-25 16:01:31 -0400696 btrfs_tree_lock(cur);
Chris Masonb4ce94d2009-02-04 09:25:08 -0500697 btrfs_set_lock_blocking(cur);
Chris Mason6b800532007-10-15 16:17:34 -0400698 err = __btrfs_cow_block(trans, root, cur, parent, i,
Chris Masone7a84562008-06-25 16:01:31 -0400699 &cur, search_start,
Chris Mason6b800532007-10-15 16:17:34 -0400700 min(16 * blocksize,
Chris Mason9fa8cfe2009-03-13 10:24:59 -0400701 (end_slot - i) * blocksize));
Yan252c38f2007-08-29 09:11:44 -0400702 if (err) {
Chris Masone7a84562008-06-25 16:01:31 -0400703 btrfs_tree_unlock(cur);
Chris Mason6b800532007-10-15 16:17:34 -0400704 free_extent_buffer(cur);
Chris Mason6702ed42007-08-07 16:15:09 -0400705 break;
Yan252c38f2007-08-29 09:11:44 -0400706 }
Chris Masone7a84562008-06-25 16:01:31 -0400707 search_start = cur->start;
708 last_block = cur->start;
Chris Masonf2183bd2007-08-10 14:42:37 -0400709 *last_ret = search_start;
Chris Masone7a84562008-06-25 16:01:31 -0400710 btrfs_tree_unlock(cur);
711 free_extent_buffer(cur);
Chris Mason6702ed42007-08-07 16:15:09 -0400712 }
Chris Mason5708b952007-10-25 15:43:18 -0400713 if (parent->map_token) {
714 unmap_extent_buffer(parent, parent->map_token,
715 KM_USER1);
716 parent->map_token = NULL;
717 }
Chris Mason6702ed42007-08-07 16:15:09 -0400718 return err;
719}
720
Chris Mason74123bd2007-02-02 11:05:29 -0500721/*
722 * The leaf data grows from end-to-front in the node.
723 * this returns the address of the start of the last item,
724 * which is the stop of the leaf data stack
725 */
Chris Mason123abc82007-03-14 14:14:43 -0400726static inline unsigned int leaf_data_end(struct btrfs_root *root,
Chris Mason5f39d392007-10-15 16:14:19 -0400727 struct extent_buffer *leaf)
Chris Masonbe0e5c02007-01-26 15:51:26 -0500728{
Chris Mason5f39d392007-10-15 16:14:19 -0400729 u32 nr = btrfs_header_nritems(leaf);
Chris Masonbe0e5c02007-01-26 15:51:26 -0500730 if (nr == 0)
Chris Mason123abc82007-03-14 14:14:43 -0400731 return BTRFS_LEAF_DATA_SIZE(root);
Chris Mason5f39d392007-10-15 16:14:19 -0400732 return btrfs_item_offset_nr(leaf, nr - 1);
Chris Masonbe0e5c02007-01-26 15:51:26 -0500733}
734
Chris Masonaa5d6be2007-02-28 16:35:06 -0500735
Chris Mason74123bd2007-02-02 11:05:29 -0500736/*
Chris Mason5f39d392007-10-15 16:14:19 -0400737 * search for key in the extent_buffer. The items start at offset p,
738 * and they are item_size apart. There are 'max' items in p.
739 *
Chris Mason74123bd2007-02-02 11:05:29 -0500740 * the slot in the array is returned via slot, and it points to
741 * the place where you would insert key if it is not found in
742 * the array.
743 *
744 * slot may point to max if the key is bigger than all of the keys
745 */
Chris Masone02119d2008-09-05 16:13:11 -0400746static noinline int generic_bin_search(struct extent_buffer *eb,
747 unsigned long p,
748 int item_size, struct btrfs_key *key,
749 int max, int *slot)
Chris Masonbe0e5c02007-01-26 15:51:26 -0500750{
751 int low = 0;
752 int high = max;
753 int mid;
754 int ret;
Chris Mason479965d2007-10-15 16:14:27 -0400755 struct btrfs_disk_key *tmp = NULL;
Chris Mason5f39d392007-10-15 16:14:19 -0400756 struct btrfs_disk_key unaligned;
757 unsigned long offset;
758 char *map_token = NULL;
759 char *kaddr = NULL;
760 unsigned long map_start = 0;
761 unsigned long map_len = 0;
Chris Mason479965d2007-10-15 16:14:27 -0400762 int err;
Chris Masonbe0e5c02007-01-26 15:51:26 -0500763
Chris Masond3977122009-01-05 21:25:51 -0500764 while (low < high) {
Chris Masonbe0e5c02007-01-26 15:51:26 -0500765 mid = (low + high) / 2;
Chris Mason5f39d392007-10-15 16:14:19 -0400766 offset = p + mid * item_size;
767
768 if (!map_token || offset < map_start ||
769 (offset + sizeof(struct btrfs_disk_key)) >
770 map_start + map_len) {
Chris Mason479965d2007-10-15 16:14:27 -0400771 if (map_token) {
Chris Mason5f39d392007-10-15 16:14:19 -0400772 unmap_extent_buffer(eb, map_token, KM_USER0);
Chris Mason479965d2007-10-15 16:14:27 -0400773 map_token = NULL;
774 }
Chris Mason934d3752008-12-08 16:43:10 -0500775
776 err = map_private_extent_buffer(eb, offset,
Chris Mason479965d2007-10-15 16:14:27 -0400777 sizeof(struct btrfs_disk_key),
778 &map_token, &kaddr,
779 &map_start, &map_len, KM_USER0);
Chris Mason5f39d392007-10-15 16:14:19 -0400780
Chris Mason479965d2007-10-15 16:14:27 -0400781 if (!err) {
782 tmp = (struct btrfs_disk_key *)(kaddr + offset -
783 map_start);
784 } else {
785 read_extent_buffer(eb, &unaligned,
786 offset, sizeof(unaligned));
787 tmp = &unaligned;
788 }
789
Chris Mason5f39d392007-10-15 16:14:19 -0400790 } else {
791 tmp = (struct btrfs_disk_key *)(kaddr + offset -
792 map_start);
793 }
Chris Masonbe0e5c02007-01-26 15:51:26 -0500794 ret = comp_keys(tmp, key);
795
796 if (ret < 0)
797 low = mid + 1;
798 else if (ret > 0)
799 high = mid;
800 else {
801 *slot = mid;
Chris Mason479965d2007-10-15 16:14:27 -0400802 if (map_token)
803 unmap_extent_buffer(eb, map_token, KM_USER0);
Chris Masonbe0e5c02007-01-26 15:51:26 -0500804 return 0;
805 }
806 }
807 *slot = low;
Chris Mason5f39d392007-10-15 16:14:19 -0400808 if (map_token)
809 unmap_extent_buffer(eb, map_token, KM_USER0);
Chris Masonbe0e5c02007-01-26 15:51:26 -0500810 return 1;
811}
812
Chris Mason97571fd2007-02-24 13:39:08 -0500813/*
814 * simple bin_search frontend that does the right thing for
815 * leaves vs nodes
816 */
Chris Mason5f39d392007-10-15 16:14:19 -0400817static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
818 int level, int *slot)
Chris Masonbe0e5c02007-01-26 15:51:26 -0500819{
Chris Mason5f39d392007-10-15 16:14:19 -0400820 if (level == 0) {
821 return generic_bin_search(eb,
822 offsetof(struct btrfs_leaf, items),
Chris Mason0783fcf2007-03-12 20:12:07 -0400823 sizeof(struct btrfs_item),
Chris Mason5f39d392007-10-15 16:14:19 -0400824 key, btrfs_header_nritems(eb),
Chris Mason7518a232007-03-12 12:01:18 -0400825 slot);
Chris Masonbe0e5c02007-01-26 15:51:26 -0500826 } else {
Chris Mason5f39d392007-10-15 16:14:19 -0400827 return generic_bin_search(eb,
828 offsetof(struct btrfs_node, ptrs),
Chris Mason123abc82007-03-14 14:14:43 -0400829 sizeof(struct btrfs_key_ptr),
Chris Mason5f39d392007-10-15 16:14:19 -0400830 key, btrfs_header_nritems(eb),
Chris Mason7518a232007-03-12 12:01:18 -0400831 slot);
Chris Masonbe0e5c02007-01-26 15:51:26 -0500832 }
833 return -1;
834}
835
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400836int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
837 int level, int *slot)
838{
839 return bin_search(eb, key, level, slot);
840}
841
Yan, Zhengf0486c62010-05-16 10:46:25 -0400842static void root_add_used(struct btrfs_root *root, u32 size)
843{
844 spin_lock(&root->accounting_lock);
845 btrfs_set_root_used(&root->root_item,
846 btrfs_root_used(&root->root_item) + size);
847 spin_unlock(&root->accounting_lock);
848}
849
850static void root_sub_used(struct btrfs_root *root, u32 size)
851{
852 spin_lock(&root->accounting_lock);
853 btrfs_set_root_used(&root->root_item,
854 btrfs_root_used(&root->root_item) - size);
855 spin_unlock(&root->accounting_lock);
856}
857
Chris Masond352ac62008-09-29 15:18:18 -0400858/* given a node and slot number, this reads the blocks it points to. The
859 * extent buffer is returned with a reference taken (but unlocked).
860 * NULL is returned on error.
861 */
Chris Masone02119d2008-09-05 16:13:11 -0400862static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
Chris Mason5f39d392007-10-15 16:14:19 -0400863 struct extent_buffer *parent, int slot)
Chris Masonbb803952007-03-01 12:04:21 -0500864{
Chris Masonca7a79a2008-05-12 12:59:19 -0400865 int level = btrfs_header_level(parent);
Chris Masonbb803952007-03-01 12:04:21 -0500866 if (slot < 0)
867 return NULL;
Chris Mason5f39d392007-10-15 16:14:19 -0400868 if (slot >= btrfs_header_nritems(parent))
Chris Masonbb803952007-03-01 12:04:21 -0500869 return NULL;
Chris Masonca7a79a2008-05-12 12:59:19 -0400870
871 BUG_ON(level == 0);
872
Chris Masondb945352007-10-15 16:15:53 -0400873 return read_tree_block(root, btrfs_node_blockptr(parent, slot),
Chris Masonca7a79a2008-05-12 12:59:19 -0400874 btrfs_level_size(root, level - 1),
875 btrfs_node_ptr_generation(parent, slot));
Chris Masonbb803952007-03-01 12:04:21 -0500876}
877
Chris Masond352ac62008-09-29 15:18:18 -0400878/*
879 * node level balancing, used to make sure nodes are in proper order for
880 * item deletion. We balance from the top down, so we have to make sure
881 * that a deletion won't leave an node completely empty later on.
882 */
Chris Masone02119d2008-09-05 16:13:11 -0400883static noinline int balance_level(struct btrfs_trans_handle *trans,
Chris Mason98ed5172008-01-03 10:01:48 -0500884 struct btrfs_root *root,
885 struct btrfs_path *path, int level)
Chris Masonbb803952007-03-01 12:04:21 -0500886{
Chris Mason5f39d392007-10-15 16:14:19 -0400887 struct extent_buffer *right = NULL;
888 struct extent_buffer *mid;
889 struct extent_buffer *left = NULL;
890 struct extent_buffer *parent = NULL;
Chris Masonbb803952007-03-01 12:04:21 -0500891 int ret = 0;
892 int wret;
893 int pslot;
Chris Masonbb803952007-03-01 12:04:21 -0500894 int orig_slot = path->slots[level];
Chris Mason79f95c82007-03-01 15:16:26 -0500895 u64 orig_ptr;
Chris Masonbb803952007-03-01 12:04:21 -0500896
897 if (level == 0)
898 return 0;
899
Chris Mason5f39d392007-10-15 16:14:19 -0400900 mid = path->nodes[level];
Chris Masonb4ce94d2009-02-04 09:25:08 -0500901
Chris Mason925baed2008-06-25 16:01:30 -0400902 WARN_ON(!path->locks[level]);
Chris Mason7bb86312007-12-11 09:25:06 -0500903 WARN_ON(btrfs_header_generation(mid) != trans->transid);
904
Chris Mason1d4f8a02007-03-13 09:28:32 -0400905 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
Chris Mason79f95c82007-03-01 15:16:26 -0500906
Chris Mason234b63a2007-03-13 10:46:10 -0400907 if (level < BTRFS_MAX_LEVEL - 1)
Chris Mason5f39d392007-10-15 16:14:19 -0400908 parent = path->nodes[level + 1];
Chris Masonbb803952007-03-01 12:04:21 -0500909 pslot = path->slots[level + 1];
910
Chris Mason40689472007-03-17 14:29:23 -0400911 /*
912 * deal with the case where there is only one pointer in the root
913 * by promoting the node below to a root
914 */
Chris Mason5f39d392007-10-15 16:14:19 -0400915 if (!parent) {
916 struct extent_buffer *child;
Chris Masonbb803952007-03-01 12:04:21 -0500917
Chris Mason5f39d392007-10-15 16:14:19 -0400918 if (btrfs_header_nritems(mid) != 1)
Chris Masonbb803952007-03-01 12:04:21 -0500919 return 0;
920
921 /* promote the child to a root */
Chris Mason5f39d392007-10-15 16:14:19 -0400922 child = read_node_slot(root, mid, 0);
Jeff Mahoney7951f3c2009-02-12 10:06:15 -0500923 BUG_ON(!child);
Chris Mason925baed2008-06-25 16:01:30 -0400924 btrfs_tree_lock(child);
Chris Masonb4ce94d2009-02-04 09:25:08 -0500925 btrfs_set_lock_blocking(child);
Chris Mason9fa8cfe2009-03-13 10:24:59 -0400926 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
Yan, Zhengf0486c62010-05-16 10:46:25 -0400927 if (ret) {
928 btrfs_tree_unlock(child);
929 free_extent_buffer(child);
930 goto enospc;
931 }
Yan2f375ab2008-02-01 14:58:07 -0500932
Chris Mason925baed2008-06-25 16:01:30 -0400933 spin_lock(&root->node_lock);
Chris Masonbb803952007-03-01 12:04:21 -0500934 root->node = child;
Chris Mason925baed2008-06-25 16:01:30 -0400935 spin_unlock(&root->node_lock);
936
Chris Mason0b86a832008-03-24 15:01:56 -0400937 add_root_to_dirty_list(root);
Chris Mason925baed2008-06-25 16:01:30 -0400938 btrfs_tree_unlock(child);
Chris Masonb4ce94d2009-02-04 09:25:08 -0500939
Chris Mason925baed2008-06-25 16:01:30 -0400940 path->locks[level] = 0;
Chris Masonbb803952007-03-01 12:04:21 -0500941 path->nodes[level] = NULL;
Chris Mason5f39d392007-10-15 16:14:19 -0400942 clean_tree_block(trans, root, mid);
Chris Mason925baed2008-06-25 16:01:30 -0400943 btrfs_tree_unlock(mid);
Chris Masonbb803952007-03-01 12:04:21 -0500944 /* once for the path */
Chris Mason5f39d392007-10-15 16:14:19 -0400945 free_extent_buffer(mid);
Yan, Zhengf0486c62010-05-16 10:46:25 -0400946
947 root_sub_used(root, mid->len);
948 btrfs_free_tree_block(trans, root, mid, 0, 1);
Chris Masonbb803952007-03-01 12:04:21 -0500949 /* once for the root ptr */
Chris Mason5f39d392007-10-15 16:14:19 -0400950 free_extent_buffer(mid);
Yan, Zhengf0486c62010-05-16 10:46:25 -0400951 return 0;
Chris Masonbb803952007-03-01 12:04:21 -0500952 }
Chris Mason5f39d392007-10-15 16:14:19 -0400953 if (btrfs_header_nritems(mid) >
Chris Mason123abc82007-03-14 14:14:43 -0400954 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
Chris Masonbb803952007-03-01 12:04:21 -0500955 return 0;
956
Andi Kleen559af822010-10-29 15:14:37 -0400957 btrfs_header_nritems(mid);
Chris Mason54aa1f42007-06-22 14:16:25 -0400958
Chris Mason5f39d392007-10-15 16:14:19 -0400959 left = read_node_slot(root, parent, pslot - 1);
960 if (left) {
Chris Mason925baed2008-06-25 16:01:30 -0400961 btrfs_tree_lock(left);
Chris Masonb4ce94d2009-02-04 09:25:08 -0500962 btrfs_set_lock_blocking(left);
Chris Mason5f39d392007-10-15 16:14:19 -0400963 wret = btrfs_cow_block(trans, root, left,
Chris Mason9fa8cfe2009-03-13 10:24:59 -0400964 parent, pslot - 1, &left);
Chris Mason54aa1f42007-06-22 14:16:25 -0400965 if (wret) {
966 ret = wret;
967 goto enospc;
968 }
Chris Mason2cc58cf2007-08-27 16:49:44 -0400969 }
Chris Mason5f39d392007-10-15 16:14:19 -0400970 right = read_node_slot(root, parent, pslot + 1);
971 if (right) {
Chris Mason925baed2008-06-25 16:01:30 -0400972 btrfs_tree_lock(right);
Chris Masonb4ce94d2009-02-04 09:25:08 -0500973 btrfs_set_lock_blocking(right);
Chris Mason5f39d392007-10-15 16:14:19 -0400974 wret = btrfs_cow_block(trans, root, right,
Chris Mason9fa8cfe2009-03-13 10:24:59 -0400975 parent, pslot + 1, &right);
Chris Mason2cc58cf2007-08-27 16:49:44 -0400976 if (wret) {
977 ret = wret;
978 goto enospc;
979 }
980 }
981
982 /* first, try to make some room in the middle buffer */
Chris Mason5f39d392007-10-15 16:14:19 -0400983 if (left) {
984 orig_slot += btrfs_header_nritems(left);
Chris Masonbce4eae2008-04-24 14:42:46 -0400985 wret = push_node_left(trans, root, left, mid, 1);
Chris Mason79f95c82007-03-01 15:16:26 -0500986 if (wret < 0)
987 ret = wret;
Andi Kleen559af822010-10-29 15:14:37 -0400988 btrfs_header_nritems(mid);
Chris Masonbb803952007-03-01 12:04:21 -0500989 }
Chris Mason79f95c82007-03-01 15:16:26 -0500990
991 /*
992 * then try to empty the right most buffer into the middle
993 */
Chris Mason5f39d392007-10-15 16:14:19 -0400994 if (right) {
Chris Mason971a1f62008-04-24 10:54:32 -0400995 wret = push_node_left(trans, root, mid, right, 1);
Chris Mason54aa1f42007-06-22 14:16:25 -0400996 if (wret < 0 && wret != -ENOSPC)
Chris Mason79f95c82007-03-01 15:16:26 -0500997 ret = wret;
Chris Mason5f39d392007-10-15 16:14:19 -0400998 if (btrfs_header_nritems(right) == 0) {
Chris Mason5f39d392007-10-15 16:14:19 -0400999 clean_tree_block(trans, root, right);
Chris Mason925baed2008-06-25 16:01:30 -04001000 btrfs_tree_unlock(right);
Chris Masone089f052007-03-16 16:20:31 -04001001 wret = del_ptr(trans, root, path, level + 1, pslot +
1002 1);
Chris Masonbb803952007-03-01 12:04:21 -05001003 if (wret)
1004 ret = wret;
Yan, Zhengf0486c62010-05-16 10:46:25 -04001005 root_sub_used(root, right->len);
1006 btrfs_free_tree_block(trans, root, right, 0, 1);
1007 free_extent_buffer(right);
1008 right = NULL;
Chris Masonbb803952007-03-01 12:04:21 -05001009 } else {
Chris Mason5f39d392007-10-15 16:14:19 -04001010 struct btrfs_disk_key right_key;
1011 btrfs_node_key(right, &right_key, 0);
1012 btrfs_set_node_key(parent, &right_key, pslot + 1);
1013 btrfs_mark_buffer_dirty(parent);
Chris Masonbb803952007-03-01 12:04:21 -05001014 }
1015 }
Chris Mason5f39d392007-10-15 16:14:19 -04001016 if (btrfs_header_nritems(mid) == 1) {
Chris Mason79f95c82007-03-01 15:16:26 -05001017 /*
1018 * we're not allowed to leave a node with one item in the
1019 * tree during a delete. A deletion from lower in the tree
1020 * could try to delete the only pointer in this node.
1021 * So, pull some keys from the left.
1022 * There has to be a left pointer at this point because
1023 * otherwise we would have pulled some pointers from the
1024 * right
1025 */
Chris Mason5f39d392007-10-15 16:14:19 -04001026 BUG_ON(!left);
1027 wret = balance_node_right(trans, root, mid, left);
Chris Mason54aa1f42007-06-22 14:16:25 -04001028 if (wret < 0) {
Chris Mason79f95c82007-03-01 15:16:26 -05001029 ret = wret;
Chris Mason54aa1f42007-06-22 14:16:25 -04001030 goto enospc;
1031 }
Chris Masonbce4eae2008-04-24 14:42:46 -04001032 if (wret == 1) {
1033 wret = push_node_left(trans, root, left, mid, 1);
1034 if (wret < 0)
1035 ret = wret;
1036 }
Chris Mason79f95c82007-03-01 15:16:26 -05001037 BUG_ON(wret == 1);
1038 }
Chris Mason5f39d392007-10-15 16:14:19 -04001039 if (btrfs_header_nritems(mid) == 0) {
Chris Mason5f39d392007-10-15 16:14:19 -04001040 clean_tree_block(trans, root, mid);
Chris Mason925baed2008-06-25 16:01:30 -04001041 btrfs_tree_unlock(mid);
Chris Masone089f052007-03-16 16:20:31 -04001042 wret = del_ptr(trans, root, path, level + 1, pslot);
Chris Masonbb803952007-03-01 12:04:21 -05001043 if (wret)
1044 ret = wret;
Yan, Zhengf0486c62010-05-16 10:46:25 -04001045 root_sub_used(root, mid->len);
1046 btrfs_free_tree_block(trans, root, mid, 0, 1);
1047 free_extent_buffer(mid);
1048 mid = NULL;
Chris Mason79f95c82007-03-01 15:16:26 -05001049 } else {
1050 /* update the parent key to reflect our changes */
Chris Mason5f39d392007-10-15 16:14:19 -04001051 struct btrfs_disk_key mid_key;
1052 btrfs_node_key(mid, &mid_key, 0);
1053 btrfs_set_node_key(parent, &mid_key, pslot);
1054 btrfs_mark_buffer_dirty(parent);
Chris Mason79f95c82007-03-01 15:16:26 -05001055 }
Chris Masonbb803952007-03-01 12:04:21 -05001056
Chris Mason79f95c82007-03-01 15:16:26 -05001057 /* update the path */
Chris Mason5f39d392007-10-15 16:14:19 -04001058 if (left) {
1059 if (btrfs_header_nritems(left) > orig_slot) {
1060 extent_buffer_get(left);
Chris Mason925baed2008-06-25 16:01:30 -04001061 /* left was locked after cow */
Chris Mason5f39d392007-10-15 16:14:19 -04001062 path->nodes[level] = left;
Chris Masonbb803952007-03-01 12:04:21 -05001063 path->slots[level + 1] -= 1;
1064 path->slots[level] = orig_slot;
Chris Mason925baed2008-06-25 16:01:30 -04001065 if (mid) {
1066 btrfs_tree_unlock(mid);
Chris Mason5f39d392007-10-15 16:14:19 -04001067 free_extent_buffer(mid);
Chris Mason925baed2008-06-25 16:01:30 -04001068 }
Chris Masonbb803952007-03-01 12:04:21 -05001069 } else {
Chris Mason5f39d392007-10-15 16:14:19 -04001070 orig_slot -= btrfs_header_nritems(left);
Chris Masonbb803952007-03-01 12:04:21 -05001071 path->slots[level] = orig_slot;
1072 }
1073 }
Chris Mason79f95c82007-03-01 15:16:26 -05001074 /* double check we haven't messed things up */
Chris Masone20d96d2007-03-22 12:13:20 -04001075 if (orig_ptr !=
Chris Mason5f39d392007-10-15 16:14:19 -04001076 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
Chris Mason79f95c82007-03-01 15:16:26 -05001077 BUG();
Chris Mason54aa1f42007-06-22 14:16:25 -04001078enospc:
Chris Mason925baed2008-06-25 16:01:30 -04001079 if (right) {
1080 btrfs_tree_unlock(right);
Chris Mason5f39d392007-10-15 16:14:19 -04001081 free_extent_buffer(right);
Chris Mason925baed2008-06-25 16:01:30 -04001082 }
1083 if (left) {
1084 if (path->nodes[level] != left)
1085 btrfs_tree_unlock(left);
Chris Mason5f39d392007-10-15 16:14:19 -04001086 free_extent_buffer(left);
Chris Mason925baed2008-06-25 16:01:30 -04001087 }
Chris Masonbb803952007-03-01 12:04:21 -05001088 return ret;
1089}
1090
Chris Masond352ac62008-09-29 15:18:18 -04001091/* Node balancing for insertion. Here we only split or push nodes around
1092 * when they are completely full. This is also done top down, so we
1093 * have to be pessimistic.
1094 */
Chris Masond3977122009-01-05 21:25:51 -05001095static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
Chris Mason98ed5172008-01-03 10:01:48 -05001096 struct btrfs_root *root,
1097 struct btrfs_path *path, int level)
Chris Masone66f7092007-04-20 13:16:02 -04001098{
Chris Mason5f39d392007-10-15 16:14:19 -04001099 struct extent_buffer *right = NULL;
1100 struct extent_buffer *mid;
1101 struct extent_buffer *left = NULL;
1102 struct extent_buffer *parent = NULL;
Chris Masone66f7092007-04-20 13:16:02 -04001103 int ret = 0;
1104 int wret;
1105 int pslot;
1106 int orig_slot = path->slots[level];
Chris Masone66f7092007-04-20 13:16:02 -04001107
1108 if (level == 0)
1109 return 1;
1110
Chris Mason5f39d392007-10-15 16:14:19 -04001111 mid = path->nodes[level];
Chris Mason7bb86312007-12-11 09:25:06 -05001112 WARN_ON(btrfs_header_generation(mid) != trans->transid);
Chris Masone66f7092007-04-20 13:16:02 -04001113
1114 if (level < BTRFS_MAX_LEVEL - 1)
Chris Mason5f39d392007-10-15 16:14:19 -04001115 parent = path->nodes[level + 1];
Chris Masone66f7092007-04-20 13:16:02 -04001116 pslot = path->slots[level + 1];
1117
Chris Mason5f39d392007-10-15 16:14:19 -04001118 if (!parent)
Chris Masone66f7092007-04-20 13:16:02 -04001119 return 1;
Chris Masone66f7092007-04-20 13:16:02 -04001120
Chris Mason5f39d392007-10-15 16:14:19 -04001121 left = read_node_slot(root, parent, pslot - 1);
Chris Masone66f7092007-04-20 13:16:02 -04001122
1123 /* first, try to make some room in the middle buffer */
Chris Mason5f39d392007-10-15 16:14:19 -04001124 if (left) {
Chris Masone66f7092007-04-20 13:16:02 -04001125 u32 left_nr;
Chris Mason925baed2008-06-25 16:01:30 -04001126
1127 btrfs_tree_lock(left);
Chris Masonb4ce94d2009-02-04 09:25:08 -05001128 btrfs_set_lock_blocking(left);
1129
Chris Mason5f39d392007-10-15 16:14:19 -04001130 left_nr = btrfs_header_nritems(left);
Chris Mason33ade1f2007-04-20 13:48:57 -04001131 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1132 wret = 1;
1133 } else {
Chris Mason5f39d392007-10-15 16:14:19 -04001134 ret = btrfs_cow_block(trans, root, left, parent,
Chris Mason9fa8cfe2009-03-13 10:24:59 -04001135 pslot - 1, &left);
Chris Mason54aa1f42007-06-22 14:16:25 -04001136 if (ret)
1137 wret = 1;
1138 else {
Chris Mason54aa1f42007-06-22 14:16:25 -04001139 wret = push_node_left(trans, root,
Chris Mason971a1f62008-04-24 10:54:32 -04001140 left, mid, 0);
Chris Mason54aa1f42007-06-22 14:16:25 -04001141 }
Chris Mason33ade1f2007-04-20 13:48:57 -04001142 }
Chris Masone66f7092007-04-20 13:16:02 -04001143 if (wret < 0)
1144 ret = wret;
1145 if (wret == 0) {
Chris Mason5f39d392007-10-15 16:14:19 -04001146 struct btrfs_disk_key disk_key;
Chris Masone66f7092007-04-20 13:16:02 -04001147 orig_slot += left_nr;
Chris Mason5f39d392007-10-15 16:14:19 -04001148 btrfs_node_key(mid, &disk_key, 0);
1149 btrfs_set_node_key(parent, &disk_key, pslot);
1150 btrfs_mark_buffer_dirty(parent);
1151 if (btrfs_header_nritems(left) > orig_slot) {
1152 path->nodes[level] = left;
Chris Masone66f7092007-04-20 13:16:02 -04001153 path->slots[level + 1] -= 1;
1154 path->slots[level] = orig_slot;
Chris Mason925baed2008-06-25 16:01:30 -04001155 btrfs_tree_unlock(mid);
Chris Mason5f39d392007-10-15 16:14:19 -04001156 free_extent_buffer(mid);
Chris Masone66f7092007-04-20 13:16:02 -04001157 } else {
1158 orig_slot -=
Chris Mason5f39d392007-10-15 16:14:19 -04001159 btrfs_header_nritems(left);
Chris Masone66f7092007-04-20 13:16:02 -04001160 path->slots[level] = orig_slot;
Chris Mason925baed2008-06-25 16:01:30 -04001161 btrfs_tree_unlock(left);
Chris Mason5f39d392007-10-15 16:14:19 -04001162 free_extent_buffer(left);
Chris Masone66f7092007-04-20 13:16:02 -04001163 }
Chris Masone66f7092007-04-20 13:16:02 -04001164 return 0;
1165 }
Chris Mason925baed2008-06-25 16:01:30 -04001166 btrfs_tree_unlock(left);
Chris Mason5f39d392007-10-15 16:14:19 -04001167 free_extent_buffer(left);
Chris Masone66f7092007-04-20 13:16:02 -04001168 }
Chris Mason925baed2008-06-25 16:01:30 -04001169 right = read_node_slot(root, parent, pslot + 1);
Chris Masone66f7092007-04-20 13:16:02 -04001170
1171 /*
1172 * then try to empty the right most buffer into the middle
1173 */
Chris Mason5f39d392007-10-15 16:14:19 -04001174 if (right) {
Chris Mason33ade1f2007-04-20 13:48:57 -04001175 u32 right_nr;
Chris Masonb4ce94d2009-02-04 09:25:08 -05001176
Chris Mason925baed2008-06-25 16:01:30 -04001177 btrfs_tree_lock(right);
Chris Masonb4ce94d2009-02-04 09:25:08 -05001178 btrfs_set_lock_blocking(right);
1179
Chris Mason5f39d392007-10-15 16:14:19 -04001180 right_nr = btrfs_header_nritems(right);
Chris Mason33ade1f2007-04-20 13:48:57 -04001181 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1182 wret = 1;
1183 } else {
Chris Mason5f39d392007-10-15 16:14:19 -04001184 ret = btrfs_cow_block(trans, root, right,
1185 parent, pslot + 1,
Chris Mason9fa8cfe2009-03-13 10:24:59 -04001186 &right);
Chris Mason54aa1f42007-06-22 14:16:25 -04001187 if (ret)
1188 wret = 1;
1189 else {
Chris Mason54aa1f42007-06-22 14:16:25 -04001190 wret = balance_node_right(trans, root,
Chris Mason5f39d392007-10-15 16:14:19 -04001191 right, mid);
Chris Mason54aa1f42007-06-22 14:16:25 -04001192 }
Chris Mason33ade1f2007-04-20 13:48:57 -04001193 }
Chris Masone66f7092007-04-20 13:16:02 -04001194 if (wret < 0)
1195 ret = wret;
1196 if (wret == 0) {
Chris Mason5f39d392007-10-15 16:14:19 -04001197 struct btrfs_disk_key disk_key;
1198
1199 btrfs_node_key(right, &disk_key, 0);
1200 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1201 btrfs_mark_buffer_dirty(parent);
1202
1203 if (btrfs_header_nritems(mid) <= orig_slot) {
1204 path->nodes[level] = right;
Chris Masone66f7092007-04-20 13:16:02 -04001205 path->slots[level + 1] += 1;
1206 path->slots[level] = orig_slot -
Chris Mason5f39d392007-10-15 16:14:19 -04001207 btrfs_header_nritems(mid);
Chris Mason925baed2008-06-25 16:01:30 -04001208 btrfs_tree_unlock(mid);
Chris Mason5f39d392007-10-15 16:14:19 -04001209 free_extent_buffer(mid);
Chris Masone66f7092007-04-20 13:16:02 -04001210 } else {
Chris Mason925baed2008-06-25 16:01:30 -04001211 btrfs_tree_unlock(right);
Chris Mason5f39d392007-10-15 16:14:19 -04001212 free_extent_buffer(right);
Chris Masone66f7092007-04-20 13:16:02 -04001213 }
Chris Masone66f7092007-04-20 13:16:02 -04001214 return 0;
1215 }
Chris Mason925baed2008-06-25 16:01:30 -04001216 btrfs_tree_unlock(right);
Chris Mason5f39d392007-10-15 16:14:19 -04001217 free_extent_buffer(right);
Chris Masone66f7092007-04-20 13:16:02 -04001218 }
Chris Masone66f7092007-04-20 13:16:02 -04001219 return 1;
1220}
1221
Chris Mason74123bd2007-02-02 11:05:29 -05001222/*
Chris Masond352ac62008-09-29 15:18:18 -04001223 * readahead one full node of leaves, finding things that are close
1224 * to the block in 'slot', and triggering ra on them.
Chris Mason3c69fae2007-08-07 15:52:22 -04001225 */
Chris Masonc8c42862009-04-03 10:14:18 -04001226static void reada_for_search(struct btrfs_root *root,
1227 struct btrfs_path *path,
1228 int level, int slot, u64 objectid)
Chris Mason3c69fae2007-08-07 15:52:22 -04001229{
Chris Mason5f39d392007-10-15 16:14:19 -04001230 struct extent_buffer *node;
Chris Mason01f46652007-12-21 16:24:26 -05001231 struct btrfs_disk_key disk_key;
Chris Mason3c69fae2007-08-07 15:52:22 -04001232 u32 nritems;
Chris Mason3c69fae2007-08-07 15:52:22 -04001233 u64 search;
Chris Masona7175312009-01-22 09:23:10 -05001234 u64 target;
Chris Mason6b800532007-10-15 16:17:34 -04001235 u64 nread = 0;
Chris Mason3c69fae2007-08-07 15:52:22 -04001236 int direction = path->reada;
Chris Mason5f39d392007-10-15 16:14:19 -04001237 struct extent_buffer *eb;
Chris Mason6b800532007-10-15 16:17:34 -04001238 u32 nr;
1239 u32 blocksize;
1240 u32 nscan = 0;
Chris Masondb945352007-10-15 16:15:53 -04001241
Chris Masona6b6e752007-10-15 16:22:39 -04001242 if (level != 1)
Chris Mason3c69fae2007-08-07 15:52:22 -04001243 return;
1244
Chris Mason6702ed42007-08-07 16:15:09 -04001245 if (!path->nodes[level])
1246 return;
1247
Chris Mason5f39d392007-10-15 16:14:19 -04001248 node = path->nodes[level];
Chris Mason925baed2008-06-25 16:01:30 -04001249
Chris Mason3c69fae2007-08-07 15:52:22 -04001250 search = btrfs_node_blockptr(node, slot);
Chris Mason6b800532007-10-15 16:17:34 -04001251 blocksize = btrfs_level_size(root, level - 1);
1252 eb = btrfs_find_tree_block(root, search, blocksize);
Chris Mason5f39d392007-10-15 16:14:19 -04001253 if (eb) {
1254 free_extent_buffer(eb);
Chris Mason3c69fae2007-08-07 15:52:22 -04001255 return;
1256 }
1257
Chris Masona7175312009-01-22 09:23:10 -05001258 target = search;
Chris Mason6b800532007-10-15 16:17:34 -04001259
Chris Mason5f39d392007-10-15 16:14:19 -04001260 nritems = btrfs_header_nritems(node);
Chris Mason6b800532007-10-15 16:17:34 -04001261 nr = slot;
Chris Masond3977122009-01-05 21:25:51 -05001262 while (1) {
Chris Mason6b800532007-10-15 16:17:34 -04001263 if (direction < 0) {
1264 if (nr == 0)
1265 break;
1266 nr--;
1267 } else if (direction > 0) {
1268 nr++;
1269 if (nr >= nritems)
1270 break;
Chris Mason3c69fae2007-08-07 15:52:22 -04001271 }
Chris Mason01f46652007-12-21 16:24:26 -05001272 if (path->reada < 0 && objectid) {
1273 btrfs_node_key(node, &disk_key, nr);
1274 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1275 break;
1276 }
Chris Mason6b800532007-10-15 16:17:34 -04001277 search = btrfs_node_blockptr(node, nr);
Chris Masona7175312009-01-22 09:23:10 -05001278 if ((search <= target && target - search <= 65536) ||
1279 (search > target && search - target <= 65536)) {
Chris Masonca7a79a2008-05-12 12:59:19 -04001280 readahead_tree_block(root, search, blocksize,
1281 btrfs_node_ptr_generation(node, nr));
Chris Mason6b800532007-10-15 16:17:34 -04001282 nread += blocksize;
1283 }
1284 nscan++;
Chris Masona7175312009-01-22 09:23:10 -05001285 if ((nread > 65536 || nscan > 32))
Chris Mason6b800532007-10-15 16:17:34 -04001286 break;
Chris Mason3c69fae2007-08-07 15:52:22 -04001287 }
1288}
Chris Mason925baed2008-06-25 16:01:30 -04001289
Chris Masond352ac62008-09-29 15:18:18 -04001290/*
Chris Masonb4ce94d2009-02-04 09:25:08 -05001291 * returns -EAGAIN if it had to drop the path, or zero if everything was in
1292 * cache
1293 */
1294static noinline int reada_for_balance(struct btrfs_root *root,
1295 struct btrfs_path *path, int level)
1296{
1297 int slot;
1298 int nritems;
1299 struct extent_buffer *parent;
1300 struct extent_buffer *eb;
1301 u64 gen;
1302 u64 block1 = 0;
1303 u64 block2 = 0;
1304 int ret = 0;
1305 int blocksize;
1306
Chris Mason8c594ea2009-04-20 15:50:10 -04001307 parent = path->nodes[level + 1];
Chris Masonb4ce94d2009-02-04 09:25:08 -05001308 if (!parent)
1309 return 0;
1310
1311 nritems = btrfs_header_nritems(parent);
Chris Mason8c594ea2009-04-20 15:50:10 -04001312 slot = path->slots[level + 1];
Chris Masonb4ce94d2009-02-04 09:25:08 -05001313 blocksize = btrfs_level_size(root, level);
1314
1315 if (slot > 0) {
1316 block1 = btrfs_node_blockptr(parent, slot - 1);
1317 gen = btrfs_node_ptr_generation(parent, slot - 1);
1318 eb = btrfs_find_tree_block(root, block1, blocksize);
1319 if (eb && btrfs_buffer_uptodate(eb, gen))
1320 block1 = 0;
1321 free_extent_buffer(eb);
1322 }
Chris Mason8c594ea2009-04-20 15:50:10 -04001323 if (slot + 1 < nritems) {
Chris Masonb4ce94d2009-02-04 09:25:08 -05001324 block2 = btrfs_node_blockptr(parent, slot + 1);
1325 gen = btrfs_node_ptr_generation(parent, slot + 1);
1326 eb = btrfs_find_tree_block(root, block2, blocksize);
1327 if (eb && btrfs_buffer_uptodate(eb, gen))
1328 block2 = 0;
1329 free_extent_buffer(eb);
1330 }
1331 if (block1 || block2) {
1332 ret = -EAGAIN;
Chris Mason8c594ea2009-04-20 15:50:10 -04001333
1334 /* release the whole path */
Chris Masonb4ce94d2009-02-04 09:25:08 -05001335 btrfs_release_path(root, path);
Chris Mason8c594ea2009-04-20 15:50:10 -04001336
1337 /* read the blocks */
Chris Masonb4ce94d2009-02-04 09:25:08 -05001338 if (block1)
1339 readahead_tree_block(root, block1, blocksize, 0);
1340 if (block2)
1341 readahead_tree_block(root, block2, blocksize, 0);
1342
1343 if (block1) {
1344 eb = read_tree_block(root, block1, blocksize, 0);
1345 free_extent_buffer(eb);
1346 }
Chris Mason8c594ea2009-04-20 15:50:10 -04001347 if (block2) {
Chris Masonb4ce94d2009-02-04 09:25:08 -05001348 eb = read_tree_block(root, block2, blocksize, 0);
1349 free_extent_buffer(eb);
1350 }
1351 }
1352 return ret;
1353}
1354
1355
1356/*
Chris Masond3977122009-01-05 21:25:51 -05001357 * when we walk down the tree, it is usually safe to unlock the higher layers
1358 * in the tree. The exceptions are when our path goes through slot 0, because
1359 * operations on the tree might require changing key pointers higher up in the
1360 * tree.
Chris Masond352ac62008-09-29 15:18:18 -04001361 *
Chris Masond3977122009-01-05 21:25:51 -05001362 * callers might also have set path->keep_locks, which tells this code to keep
1363 * the lock if the path points to the last slot in the block. This is part of
1364 * walking through the tree, and selecting the next slot in the higher block.
Chris Masond352ac62008-09-29 15:18:18 -04001365 *
Chris Masond3977122009-01-05 21:25:51 -05001366 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
1367 * if lowest_unlock is 1, level 0 won't be unlocked
Chris Masond352ac62008-09-29 15:18:18 -04001368 */
Chris Masone02119d2008-09-05 16:13:11 -04001369static noinline void unlock_up(struct btrfs_path *path, int level,
1370 int lowest_unlock)
Chris Mason925baed2008-06-25 16:01:30 -04001371{
1372 int i;
1373 int skip_level = level;
Chris Mason051e1b92008-06-25 16:01:30 -04001374 int no_skips = 0;
Chris Mason925baed2008-06-25 16:01:30 -04001375 struct extent_buffer *t;
1376
1377 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1378 if (!path->nodes[i])
1379 break;
1380 if (!path->locks[i])
1381 break;
Chris Mason051e1b92008-06-25 16:01:30 -04001382 if (!no_skips && path->slots[i] == 0) {
Chris Mason925baed2008-06-25 16:01:30 -04001383 skip_level = i + 1;
1384 continue;
1385 }
Chris Mason051e1b92008-06-25 16:01:30 -04001386 if (!no_skips && path->keep_locks) {
Chris Mason925baed2008-06-25 16:01:30 -04001387 u32 nritems;
1388 t = path->nodes[i];
1389 nritems = btrfs_header_nritems(t);
Chris Mason051e1b92008-06-25 16:01:30 -04001390 if (nritems < 1 || path->slots[i] >= nritems - 1) {
Chris Mason925baed2008-06-25 16:01:30 -04001391 skip_level = i + 1;
1392 continue;
1393 }
1394 }
Chris Mason051e1b92008-06-25 16:01:30 -04001395 if (skip_level < i && i >= lowest_unlock)
1396 no_skips = 1;
1397
Chris Mason925baed2008-06-25 16:01:30 -04001398 t = path->nodes[i];
1399 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
1400 btrfs_tree_unlock(t);
1401 path->locks[i] = 0;
1402 }
1403 }
1404}
1405
Chris Mason3c69fae2007-08-07 15:52:22 -04001406/*
Chris Masonb4ce94d2009-02-04 09:25:08 -05001407 * This releases any locks held in the path starting at level and
1408 * going all the way up to the root.
1409 *
1410 * btrfs_search_slot will keep the lock held on higher nodes in a few
1411 * corner cases, such as COW of the block at slot zero in the node. This
1412 * ignores those rules, and it should only be called when there are no
1413 * more updates to be done higher up in the tree.
1414 */
1415noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
1416{
1417 int i;
1418
Yan Zheng5d4f98a2009-06-10 10:45:14 -04001419 if (path->keep_locks)
Chris Masonb4ce94d2009-02-04 09:25:08 -05001420 return;
1421
1422 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1423 if (!path->nodes[i])
Chris Mason12f4dac2009-02-04 09:31:42 -05001424 continue;
Chris Masonb4ce94d2009-02-04 09:25:08 -05001425 if (!path->locks[i])
Chris Mason12f4dac2009-02-04 09:31:42 -05001426 continue;
Chris Masonb4ce94d2009-02-04 09:25:08 -05001427 btrfs_tree_unlock(path->nodes[i]);
1428 path->locks[i] = 0;
1429 }
1430}
1431
1432/*
Chris Masonc8c42862009-04-03 10:14:18 -04001433 * helper function for btrfs_search_slot. The goal is to find a block
1434 * in cache without setting the path to blocking. If we find the block
1435 * we return zero and the path is unchanged.
1436 *
1437 * If we can't find the block, we set the path blocking and do some
1438 * reada. -EAGAIN is returned and the search must be repeated.
1439 */
1440static int
1441read_block_for_search(struct btrfs_trans_handle *trans,
1442 struct btrfs_root *root, struct btrfs_path *p,
1443 struct extent_buffer **eb_ret, int level, int slot,
1444 struct btrfs_key *key)
1445{
1446 u64 blocknr;
1447 u64 gen;
1448 u32 blocksize;
1449 struct extent_buffer *b = *eb_ret;
1450 struct extent_buffer *tmp;
Chris Mason76a05b32009-05-14 13:24:30 -04001451 int ret;
Chris Masonc8c42862009-04-03 10:14:18 -04001452
1453 blocknr = btrfs_node_blockptr(b, slot);
1454 gen = btrfs_node_ptr_generation(b, slot);
1455 blocksize = btrfs_level_size(root, level - 1);
1456
1457 tmp = btrfs_find_tree_block(root, blocknr, blocksize);
Chris Masoncb449212010-10-24 11:01:27 -04001458 if (tmp) {
1459 if (btrfs_buffer_uptodate(tmp, 0)) {
1460 if (btrfs_buffer_uptodate(tmp, gen)) {
1461 /*
1462 * we found an up to date block without
1463 * sleeping, return
1464 * right away
1465 */
1466 *eb_ret = tmp;
1467 return 0;
1468 }
1469 /* the pages were up to date, but we failed
1470 * the generation number check. Do a full
1471 * read for the generation number that is correct.
1472 * We must do this without dropping locks so
1473 * we can trust our generation number
1474 */
1475 free_extent_buffer(tmp);
1476 tmp = read_tree_block(root, blocknr, blocksize, gen);
1477 if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
1478 *eb_ret = tmp;
1479 return 0;
1480 }
1481 free_extent_buffer(tmp);
1482 btrfs_release_path(NULL, p);
1483 return -EIO;
1484 }
Chris Masonc8c42862009-04-03 10:14:18 -04001485 }
1486
1487 /*
1488 * reduce lock contention at high levels
1489 * of the btree by dropping locks before
Chris Mason76a05b32009-05-14 13:24:30 -04001490 * we read. Don't release the lock on the current
1491 * level because we need to walk this node to figure
1492 * out which blocks to read.
Chris Masonc8c42862009-04-03 10:14:18 -04001493 */
Chris Mason8c594ea2009-04-20 15:50:10 -04001494 btrfs_unlock_up_safe(p, level + 1);
1495 btrfs_set_path_blocking(p);
1496
Chris Masoncb449212010-10-24 11:01:27 -04001497 free_extent_buffer(tmp);
Chris Masonc8c42862009-04-03 10:14:18 -04001498 if (p->reada)
1499 reada_for_search(root, p, level, slot, key->objectid);
1500
Chris Mason8c594ea2009-04-20 15:50:10 -04001501 btrfs_release_path(NULL, p);
Chris Mason76a05b32009-05-14 13:24:30 -04001502
1503 ret = -EAGAIN;
Yan, Zheng5bdd3532010-05-26 11:20:30 -04001504 tmp = read_tree_block(root, blocknr, blocksize, 0);
Chris Mason76a05b32009-05-14 13:24:30 -04001505 if (tmp) {
1506 /*
1507 * If the read above didn't mark this buffer up to date,
1508 * it will never end up being up to date. Set ret to EIO now
1509 * and give up so that our caller doesn't loop forever
1510 * on our EAGAINs.
1511 */
1512 if (!btrfs_buffer_uptodate(tmp, 0))
1513 ret = -EIO;
Chris Masonc8c42862009-04-03 10:14:18 -04001514 free_extent_buffer(tmp);
Chris Mason76a05b32009-05-14 13:24:30 -04001515 }
1516 return ret;
Chris Masonc8c42862009-04-03 10:14:18 -04001517}
1518
1519/*
1520 * helper function for btrfs_search_slot. This does all of the checks
1521 * for node-level blocks and does any balancing required based on
1522 * the ins_len.
1523 *
1524 * If no extra work was required, zero is returned. If we had to
1525 * drop the path, -EAGAIN is returned and btrfs_search_slot must
1526 * start over
1527 */
1528static int
1529setup_nodes_for_search(struct btrfs_trans_handle *trans,
1530 struct btrfs_root *root, struct btrfs_path *p,
1531 struct extent_buffer *b, int level, int ins_len)
1532{
1533 int ret;
1534 if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
1535 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1536 int sret;
1537
1538 sret = reada_for_balance(root, p, level);
1539 if (sret)
1540 goto again;
1541
1542 btrfs_set_path_blocking(p);
1543 sret = split_node(trans, root, p, level);
1544 btrfs_clear_path_blocking(p, NULL);
1545
1546 BUG_ON(sret > 0);
1547 if (sret) {
1548 ret = sret;
1549 goto done;
1550 }
1551 b = p->nodes[level];
1552 } else if (ins_len < 0 && btrfs_header_nritems(b) <
Chris Masoncfbb9302009-05-18 10:41:58 -04001553 BTRFS_NODEPTRS_PER_BLOCK(root) / 2) {
Chris Masonc8c42862009-04-03 10:14:18 -04001554 int sret;
1555
1556 sret = reada_for_balance(root, p, level);
1557 if (sret)
1558 goto again;
1559
1560 btrfs_set_path_blocking(p);
1561 sret = balance_level(trans, root, p, level);
1562 btrfs_clear_path_blocking(p, NULL);
1563
1564 if (sret) {
1565 ret = sret;
1566 goto done;
1567 }
1568 b = p->nodes[level];
1569 if (!b) {
1570 btrfs_release_path(NULL, p);
1571 goto again;
1572 }
1573 BUG_ON(btrfs_header_nritems(b) == 1);
1574 }
1575 return 0;
1576
1577again:
1578 ret = -EAGAIN;
1579done:
1580 return ret;
1581}
1582
1583/*
Chris Mason74123bd2007-02-02 11:05:29 -05001584 * look for key in the tree. path is filled in with nodes along the way
1585 * if key is found, we return zero and you can find the item in the leaf
1586 * level of the path (level 0)
1587 *
1588 * If the key isn't found, the path points to the slot where it should
Chris Masonaa5d6be2007-02-28 16:35:06 -05001589 * be inserted, and 1 is returned. If there are other errors during the
1590 * search a negative error number is returned.
Chris Mason97571fd2007-02-24 13:39:08 -05001591 *
1592 * if ins_len > 0, nodes and leaves will be split as we walk down the
1593 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1594 * possible)
Chris Mason74123bd2007-02-02 11:05:29 -05001595 */
Chris Masone089f052007-03-16 16:20:31 -04001596int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1597 *root, struct btrfs_key *key, struct btrfs_path *p, int
1598 ins_len, int cow)
Chris Masonbe0e5c02007-01-26 15:51:26 -05001599{
Chris Mason5f39d392007-10-15 16:14:19 -04001600 struct extent_buffer *b;
Chris Masonbe0e5c02007-01-26 15:51:26 -05001601 int slot;
1602 int ret;
Yan Zheng33c66f42009-07-22 09:59:00 -04001603 int err;
Chris Masonbe0e5c02007-01-26 15:51:26 -05001604 int level;
Chris Mason925baed2008-06-25 16:01:30 -04001605 int lowest_unlock = 1;
Chris Mason9f3a7422007-08-07 15:52:19 -04001606 u8 lowest_level = 0;
1607
Chris Mason6702ed42007-08-07 16:15:09 -04001608 lowest_level = p->lowest_level;
Chris Mason323ac952008-10-01 19:05:46 -04001609 WARN_ON(lowest_level && ins_len > 0);
Chris Mason22b0ebd2007-03-30 08:47:31 -04001610 WARN_ON(p->nodes[0] != NULL);
Josef Bacik25179202008-10-29 14:49:05 -04001611
Chris Mason925baed2008-06-25 16:01:30 -04001612 if (ins_len < 0)
1613 lowest_unlock = 2;
Chris Mason65b51a02008-08-01 15:11:20 -04001614
Chris Masonbb803952007-03-01 12:04:21 -05001615again:
Yan Zheng5d4f98a2009-06-10 10:45:14 -04001616 if (p->search_commit_root) {
1617 b = root->commit_root;
1618 extent_buffer_get(b);
1619 if (!p->skip_locking)
1620 btrfs_tree_lock(b);
1621 } else {
1622 if (p->skip_locking)
1623 b = btrfs_root_node(root);
1624 else
1625 b = btrfs_lock_root_node(root);
1626 }
Chris Mason925baed2008-06-25 16:01:30 -04001627
Chris Masoneb60cea2007-02-02 09:18:22 -05001628 while (b) {
Chris Mason5f39d392007-10-15 16:14:19 -04001629 level = btrfs_header_level(b);
Chris Mason65b51a02008-08-01 15:11:20 -04001630
1631 /*
1632 * setup the path here so we can release it under lock
1633 * contention with the cow code
1634 */
1635 p->nodes[level] = b;
1636 if (!p->skip_locking)
1637 p->locks[level] = 1;
1638
Chris Mason02217ed2007-03-02 16:08:05 -05001639 if (cow) {
Chris Masonc8c42862009-04-03 10:14:18 -04001640 /*
1641 * if we don't really need to cow this block
1642 * then we don't want to set the path blocking,
1643 * so we test it here
1644 */
Yan Zheng5d4f98a2009-06-10 10:45:14 -04001645 if (!should_cow_block(trans, root, b))
Chris Mason65b51a02008-08-01 15:11:20 -04001646 goto cow_done;
Yan Zheng5d4f98a2009-06-10 10:45:14 -04001647
Chris Masonb4ce94d2009-02-04 09:25:08 -05001648 btrfs_set_path_blocking(p);
1649
Yan Zheng33c66f42009-07-22 09:59:00 -04001650 err = btrfs_cow_block(trans, root, b,
1651 p->nodes[level + 1],
1652 p->slots[level + 1], &b);
1653 if (err) {
Yan Zheng33c66f42009-07-22 09:59:00 -04001654 ret = err;
Chris Mason65b51a02008-08-01 15:11:20 -04001655 goto done;
Chris Mason54aa1f42007-06-22 14:16:25 -04001656 }
Chris Mason02217ed2007-03-02 16:08:05 -05001657 }
Chris Mason65b51a02008-08-01 15:11:20 -04001658cow_done:
Chris Mason02217ed2007-03-02 16:08:05 -05001659 BUG_ON(!cow && ins_len);
Chris Mason5f39d392007-10-15 16:14:19 -04001660 if (level != btrfs_header_level(b))
Chris Mason2c90e5d2007-04-02 10:50:19 -04001661 WARN_ON(1);
Chris Mason5f39d392007-10-15 16:14:19 -04001662 level = btrfs_header_level(b);
Chris Mason65b51a02008-08-01 15:11:20 -04001663
Chris Masoneb60cea2007-02-02 09:18:22 -05001664 p->nodes[level] = b;
Chris Mason5cd57b22008-06-25 16:01:30 -04001665 if (!p->skip_locking)
1666 p->locks[level] = 1;
Chris Mason65b51a02008-08-01 15:11:20 -04001667
Chris Mason4008c042009-02-12 14:09:45 -05001668 btrfs_clear_path_blocking(p, NULL);
Chris Masonb4ce94d2009-02-04 09:25:08 -05001669
1670 /*
1671 * we have a lock on b and as long as we aren't changing
1672 * the tree, there is no way to for the items in b to change.
1673 * It is safe to drop the lock on our parent before we
1674 * go through the expensive btree search on b.
1675 *
1676 * If cow is true, then we might be changing slot zero,
1677 * which may require changing the parent. So, we can't
1678 * drop the lock until after we know which slot we're
1679 * operating on.
1680 */
1681 if (!cow)
1682 btrfs_unlock_up_safe(p, level + 1);
1683
Chris Mason5f39d392007-10-15 16:14:19 -04001684 ret = bin_search(b, key, level, &slot);
Chris Masonb4ce94d2009-02-04 09:25:08 -05001685
Chris Mason5f39d392007-10-15 16:14:19 -04001686 if (level != 0) {
Yan Zheng33c66f42009-07-22 09:59:00 -04001687 int dec = 0;
1688 if (ret && slot > 0) {
1689 dec = 1;
Chris Masonbe0e5c02007-01-26 15:51:26 -05001690 slot -= 1;
Yan Zheng33c66f42009-07-22 09:59:00 -04001691 }
Chris Masonbe0e5c02007-01-26 15:51:26 -05001692 p->slots[level] = slot;
Yan Zheng33c66f42009-07-22 09:59:00 -04001693 err = setup_nodes_for_search(trans, root, p, b, level,
Chris Masonc8c42862009-04-03 10:14:18 -04001694 ins_len);
Yan Zheng33c66f42009-07-22 09:59:00 -04001695 if (err == -EAGAIN)
Chris Masonc8c42862009-04-03 10:14:18 -04001696 goto again;
Yan Zheng33c66f42009-07-22 09:59:00 -04001697 if (err) {
1698 ret = err;
Chris Masonc8c42862009-04-03 10:14:18 -04001699 goto done;
Yan Zheng33c66f42009-07-22 09:59:00 -04001700 }
Chris Masonc8c42862009-04-03 10:14:18 -04001701 b = p->nodes[level];
1702 slot = p->slots[level];
Chris Masonb4ce94d2009-02-04 09:25:08 -05001703
Chris Masonf9efa9c2008-06-25 16:14:04 -04001704 unlock_up(p, level, lowest_unlock);
1705
Chris Mason925baed2008-06-25 16:01:30 -04001706 if (level == lowest_level) {
Yan Zheng33c66f42009-07-22 09:59:00 -04001707 if (dec)
1708 p->slots[level]++;
Zheng Yan5b21f2e2008-09-26 10:05:38 -04001709 goto done;
Chris Mason925baed2008-06-25 16:01:30 -04001710 }
Chris Masonca7a79a2008-05-12 12:59:19 -04001711
Yan Zheng33c66f42009-07-22 09:59:00 -04001712 err = read_block_for_search(trans, root, p,
Chris Masonc8c42862009-04-03 10:14:18 -04001713 &b, level, slot, key);
Yan Zheng33c66f42009-07-22 09:59:00 -04001714 if (err == -EAGAIN)
Chris Masonc8c42862009-04-03 10:14:18 -04001715 goto again;
Yan Zheng33c66f42009-07-22 09:59:00 -04001716 if (err) {
1717 ret = err;
Chris Mason76a05b32009-05-14 13:24:30 -04001718 goto done;
Yan Zheng33c66f42009-07-22 09:59:00 -04001719 }
Chris Mason76a05b32009-05-14 13:24:30 -04001720
Chris Masonb4ce94d2009-02-04 09:25:08 -05001721 if (!p->skip_locking) {
Chris Mason4008c042009-02-12 14:09:45 -05001722 btrfs_clear_path_blocking(p, NULL);
Yan Zheng33c66f42009-07-22 09:59:00 -04001723 err = btrfs_try_spin_lock(b);
Chris Masonb4ce94d2009-02-04 09:25:08 -05001724
Yan Zheng33c66f42009-07-22 09:59:00 -04001725 if (!err) {
Chris Masonb4ce94d2009-02-04 09:25:08 -05001726 btrfs_set_path_blocking(p);
1727 btrfs_tree_lock(b);
Chris Mason4008c042009-02-12 14:09:45 -05001728 btrfs_clear_path_blocking(p, b);
Chris Masonb4ce94d2009-02-04 09:25:08 -05001729 }
1730 }
Chris Masonbe0e5c02007-01-26 15:51:26 -05001731 } else {
1732 p->slots[level] = slot;
Yan Zheng87b29b22008-12-17 10:21:48 -05001733 if (ins_len > 0 &&
1734 btrfs_leaf_free_space(root, b) < ins_len) {
Chris Masonb4ce94d2009-02-04 09:25:08 -05001735 btrfs_set_path_blocking(p);
Yan Zheng33c66f42009-07-22 09:59:00 -04001736 err = split_leaf(trans, root, key,
1737 p, ins_len, ret == 0);
Chris Mason4008c042009-02-12 14:09:45 -05001738 btrfs_clear_path_blocking(p, NULL);
Chris Masonb4ce94d2009-02-04 09:25:08 -05001739
Yan Zheng33c66f42009-07-22 09:59:00 -04001740 BUG_ON(err > 0);
1741 if (err) {
1742 ret = err;
Chris Mason65b51a02008-08-01 15:11:20 -04001743 goto done;
1744 }
Chris Mason5c680ed2007-02-22 11:39:13 -05001745 }
Chris Mason459931e2008-12-10 09:10:46 -05001746 if (!p->search_for_split)
1747 unlock_up(p, level, lowest_unlock);
Chris Mason65b51a02008-08-01 15:11:20 -04001748 goto done;
Chris Masonbe0e5c02007-01-26 15:51:26 -05001749 }
1750 }
Chris Mason65b51a02008-08-01 15:11:20 -04001751 ret = 1;
1752done:
Chris Masonb4ce94d2009-02-04 09:25:08 -05001753 /*
1754 * we don't really know what they plan on doing with the path
1755 * from here on, so for now just mark it as blocking
1756 */
Chris Masonb9473432009-03-13 11:00:37 -04001757 if (!p->leave_spinning)
1758 btrfs_set_path_blocking(p);
Chris Mason76a05b32009-05-14 13:24:30 -04001759 if (ret < 0)
1760 btrfs_release_path(root, p);
Chris Mason65b51a02008-08-01 15:11:20 -04001761 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05001762}
1763
Chris Mason74123bd2007-02-02 11:05:29 -05001764/*
1765 * adjust the pointers going up the tree, starting at level
1766 * making sure the right key of each node is points to 'key'.
1767 * This is used after shifting pointers to the left, so it stops
1768 * fixing up pointers when a given leaf/node is not in slot 0 of the
1769 * higher levels
Chris Masonaa5d6be2007-02-28 16:35:06 -05001770 *
1771 * If this fails to write a tree block, it returns -1, but continues
1772 * fixing up the blocks in ram so the tree is consistent.
Chris Mason74123bd2007-02-02 11:05:29 -05001773 */
Chris Mason5f39d392007-10-15 16:14:19 -04001774static int fixup_low_keys(struct btrfs_trans_handle *trans,
1775 struct btrfs_root *root, struct btrfs_path *path,
1776 struct btrfs_disk_key *key, int level)
Chris Masonbe0e5c02007-01-26 15:51:26 -05001777{
1778 int i;
Chris Masonaa5d6be2007-02-28 16:35:06 -05001779 int ret = 0;
Chris Mason5f39d392007-10-15 16:14:19 -04001780 struct extent_buffer *t;
1781
Chris Mason234b63a2007-03-13 10:46:10 -04001782 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
Chris Masonbe0e5c02007-01-26 15:51:26 -05001783 int tslot = path->slots[i];
Chris Masoneb60cea2007-02-02 09:18:22 -05001784 if (!path->nodes[i])
Chris Masonbe0e5c02007-01-26 15:51:26 -05001785 break;
Chris Mason5f39d392007-10-15 16:14:19 -04001786 t = path->nodes[i];
1787 btrfs_set_node_key(t, key, tslot);
Chris Masond6025572007-03-30 14:27:56 -04001788 btrfs_mark_buffer_dirty(path->nodes[i]);
Chris Masonbe0e5c02007-01-26 15:51:26 -05001789 if (tslot != 0)
1790 break;
1791 }
Chris Masonaa5d6be2007-02-28 16:35:06 -05001792 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05001793}
1794
Chris Mason74123bd2007-02-02 11:05:29 -05001795/*
Zheng Yan31840ae2008-09-23 13:14:14 -04001796 * update item key.
1797 *
1798 * This function isn't completely safe. It's the caller's responsibility
1799 * that the new key won't break the order
1800 */
1801int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1802 struct btrfs_root *root, struct btrfs_path *path,
1803 struct btrfs_key *new_key)
1804{
1805 struct btrfs_disk_key disk_key;
1806 struct extent_buffer *eb;
1807 int slot;
1808
1809 eb = path->nodes[0];
1810 slot = path->slots[0];
1811 if (slot > 0) {
1812 btrfs_item_key(eb, &disk_key, slot - 1);
1813 if (comp_keys(&disk_key, new_key) >= 0)
1814 return -1;
1815 }
1816 if (slot < btrfs_header_nritems(eb) - 1) {
1817 btrfs_item_key(eb, &disk_key, slot + 1);
1818 if (comp_keys(&disk_key, new_key) <= 0)
1819 return -1;
1820 }
1821
1822 btrfs_cpu_key_to_disk(&disk_key, new_key);
1823 btrfs_set_item_key(eb, &disk_key, slot);
1824 btrfs_mark_buffer_dirty(eb);
1825 if (slot == 0)
1826 fixup_low_keys(trans, root, path, &disk_key, 1);
1827 return 0;
1828}
1829
1830/*
Chris Mason74123bd2007-02-02 11:05:29 -05001831 * try to push data from one node into the next node left in the
Chris Mason79f95c82007-03-01 15:16:26 -05001832 * tree.
Chris Masonaa5d6be2007-02-28 16:35:06 -05001833 *
1834 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1835 * error, and > 0 if there was no room in the left hand block.
Chris Mason74123bd2007-02-02 11:05:29 -05001836 */
Chris Mason98ed5172008-01-03 10:01:48 -05001837static int push_node_left(struct btrfs_trans_handle *trans,
1838 struct btrfs_root *root, struct extent_buffer *dst,
Chris Mason971a1f62008-04-24 10:54:32 -04001839 struct extent_buffer *src, int empty)
Chris Masonbe0e5c02007-01-26 15:51:26 -05001840{
Chris Masonbe0e5c02007-01-26 15:51:26 -05001841 int push_items = 0;
Chris Masonbb803952007-03-01 12:04:21 -05001842 int src_nritems;
1843 int dst_nritems;
Chris Masonaa5d6be2007-02-28 16:35:06 -05001844 int ret = 0;
Chris Masonbe0e5c02007-01-26 15:51:26 -05001845
Chris Mason5f39d392007-10-15 16:14:19 -04001846 src_nritems = btrfs_header_nritems(src);
1847 dst_nritems = btrfs_header_nritems(dst);
Chris Mason123abc82007-03-14 14:14:43 -04001848 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
Chris Mason7bb86312007-12-11 09:25:06 -05001849 WARN_ON(btrfs_header_generation(src) != trans->transid);
1850 WARN_ON(btrfs_header_generation(dst) != trans->transid);
Chris Mason54aa1f42007-06-22 14:16:25 -04001851
Chris Masonbce4eae2008-04-24 14:42:46 -04001852 if (!empty && src_nritems <= 8)
Chris Mason971a1f62008-04-24 10:54:32 -04001853 return 1;
1854
Chris Masond3977122009-01-05 21:25:51 -05001855 if (push_items <= 0)
Chris Masonbe0e5c02007-01-26 15:51:26 -05001856 return 1;
1857
Chris Masonbce4eae2008-04-24 14:42:46 -04001858 if (empty) {
Chris Mason971a1f62008-04-24 10:54:32 -04001859 push_items = min(src_nritems, push_items);
Chris Masonbce4eae2008-04-24 14:42:46 -04001860 if (push_items < src_nritems) {
1861 /* leave at least 8 pointers in the node if
1862 * we aren't going to empty it
1863 */
1864 if (src_nritems - push_items < 8) {
1865 if (push_items <= 8)
1866 return 1;
1867 push_items -= 8;
1868 }
1869 }
1870 } else
1871 push_items = min(src_nritems - 8, push_items);
Chris Mason79f95c82007-03-01 15:16:26 -05001872
Chris Mason5f39d392007-10-15 16:14:19 -04001873 copy_extent_buffer(dst, src,
1874 btrfs_node_key_ptr_offset(dst_nritems),
1875 btrfs_node_key_ptr_offset(0),
Chris Masond3977122009-01-05 21:25:51 -05001876 push_items * sizeof(struct btrfs_key_ptr));
Chris Mason5f39d392007-10-15 16:14:19 -04001877
Chris Masonbb803952007-03-01 12:04:21 -05001878 if (push_items < src_nritems) {
Chris Mason5f39d392007-10-15 16:14:19 -04001879 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1880 btrfs_node_key_ptr_offset(push_items),
1881 (src_nritems - push_items) *
1882 sizeof(struct btrfs_key_ptr));
Chris Masonbb803952007-03-01 12:04:21 -05001883 }
Chris Mason5f39d392007-10-15 16:14:19 -04001884 btrfs_set_header_nritems(src, src_nritems - push_items);
1885 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1886 btrfs_mark_buffer_dirty(src);
1887 btrfs_mark_buffer_dirty(dst);
Zheng Yan31840ae2008-09-23 13:14:14 -04001888
Chris Masonbb803952007-03-01 12:04:21 -05001889 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05001890}
1891
Chris Mason97571fd2007-02-24 13:39:08 -05001892/*
Chris Mason79f95c82007-03-01 15:16:26 -05001893 * try to push data from one node into the next node right in the
1894 * tree.
1895 *
1896 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1897 * error, and > 0 if there was no room in the right hand block.
1898 *
1899 * this will only push up to 1/2 the contents of the left node over
1900 */
Chris Mason5f39d392007-10-15 16:14:19 -04001901static int balance_node_right(struct btrfs_trans_handle *trans,
1902 struct btrfs_root *root,
1903 struct extent_buffer *dst,
1904 struct extent_buffer *src)
Chris Mason79f95c82007-03-01 15:16:26 -05001905{
Chris Mason79f95c82007-03-01 15:16:26 -05001906 int push_items = 0;
1907 int max_push;
1908 int src_nritems;
1909 int dst_nritems;
1910 int ret = 0;
Chris Mason79f95c82007-03-01 15:16:26 -05001911
Chris Mason7bb86312007-12-11 09:25:06 -05001912 WARN_ON(btrfs_header_generation(src) != trans->transid);
1913 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1914
Chris Mason5f39d392007-10-15 16:14:19 -04001915 src_nritems = btrfs_header_nritems(src);
1916 dst_nritems = btrfs_header_nritems(dst);
Chris Mason123abc82007-03-14 14:14:43 -04001917 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
Chris Masond3977122009-01-05 21:25:51 -05001918 if (push_items <= 0)
Chris Mason79f95c82007-03-01 15:16:26 -05001919 return 1;
Chris Masonbce4eae2008-04-24 14:42:46 -04001920
Chris Masond3977122009-01-05 21:25:51 -05001921 if (src_nritems < 4)
Chris Masonbce4eae2008-04-24 14:42:46 -04001922 return 1;
Chris Mason79f95c82007-03-01 15:16:26 -05001923
1924 max_push = src_nritems / 2 + 1;
1925 /* don't try to empty the node */
Chris Masond3977122009-01-05 21:25:51 -05001926 if (max_push >= src_nritems)
Chris Mason79f95c82007-03-01 15:16:26 -05001927 return 1;
Yan252c38f2007-08-29 09:11:44 -04001928
Chris Mason79f95c82007-03-01 15:16:26 -05001929 if (max_push < push_items)
1930 push_items = max_push;
1931
Chris Mason5f39d392007-10-15 16:14:19 -04001932 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1933 btrfs_node_key_ptr_offset(0),
1934 (dst_nritems) *
1935 sizeof(struct btrfs_key_ptr));
Chris Masond6025572007-03-30 14:27:56 -04001936
Chris Mason5f39d392007-10-15 16:14:19 -04001937 copy_extent_buffer(dst, src,
1938 btrfs_node_key_ptr_offset(0),
1939 btrfs_node_key_ptr_offset(src_nritems - push_items),
Chris Masond3977122009-01-05 21:25:51 -05001940 push_items * sizeof(struct btrfs_key_ptr));
Chris Mason79f95c82007-03-01 15:16:26 -05001941
Chris Mason5f39d392007-10-15 16:14:19 -04001942 btrfs_set_header_nritems(src, src_nritems - push_items);
1943 btrfs_set_header_nritems(dst, dst_nritems + push_items);
Chris Mason79f95c82007-03-01 15:16:26 -05001944
Chris Mason5f39d392007-10-15 16:14:19 -04001945 btrfs_mark_buffer_dirty(src);
1946 btrfs_mark_buffer_dirty(dst);
Zheng Yan31840ae2008-09-23 13:14:14 -04001947
Chris Mason79f95c82007-03-01 15:16:26 -05001948 return ret;
1949}
1950
1951/*
Chris Mason97571fd2007-02-24 13:39:08 -05001952 * helper function to insert a new root level in the tree.
1953 * A new node is allocated, and a single item is inserted to
1954 * point to the existing root
Chris Masonaa5d6be2007-02-28 16:35:06 -05001955 *
1956 * returns zero on success or < 0 on failure.
Chris Mason97571fd2007-02-24 13:39:08 -05001957 */
Chris Masond3977122009-01-05 21:25:51 -05001958static noinline int insert_new_root(struct btrfs_trans_handle *trans,
Chris Mason5f39d392007-10-15 16:14:19 -04001959 struct btrfs_root *root,
1960 struct btrfs_path *path, int level)
Chris Mason5c680ed2007-02-22 11:39:13 -05001961{
Chris Mason7bb86312007-12-11 09:25:06 -05001962 u64 lower_gen;
Chris Mason5f39d392007-10-15 16:14:19 -04001963 struct extent_buffer *lower;
1964 struct extent_buffer *c;
Chris Mason925baed2008-06-25 16:01:30 -04001965 struct extent_buffer *old;
Chris Mason5f39d392007-10-15 16:14:19 -04001966 struct btrfs_disk_key lower_key;
Chris Mason5c680ed2007-02-22 11:39:13 -05001967
1968 BUG_ON(path->nodes[level]);
1969 BUG_ON(path->nodes[level-1] != root->node);
1970
Chris Mason7bb86312007-12-11 09:25:06 -05001971 lower = path->nodes[level-1];
1972 if (level == 1)
1973 btrfs_item_key(lower, &lower_key, 0);
1974 else
1975 btrfs_node_key(lower, &lower_key, 0);
1976
Zheng Yan31840ae2008-09-23 13:14:14 -04001977 c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
Yan Zheng5d4f98a2009-06-10 10:45:14 -04001978 root->root_key.objectid, &lower_key,
Christoph Hellwigad3d81b2008-09-05 16:43:28 -04001979 level, root->node->start, 0);
Chris Mason5f39d392007-10-15 16:14:19 -04001980 if (IS_ERR(c))
1981 return PTR_ERR(c);
Chris Mason925baed2008-06-25 16:01:30 -04001982
Yan, Zhengf0486c62010-05-16 10:46:25 -04001983 root_add_used(root, root->nodesize);
1984
Yan Zheng5d4f98a2009-06-10 10:45:14 -04001985 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
Chris Mason5f39d392007-10-15 16:14:19 -04001986 btrfs_set_header_nritems(c, 1);
1987 btrfs_set_header_level(c, level);
Chris Masondb945352007-10-15 16:15:53 -04001988 btrfs_set_header_bytenr(c, c->start);
Chris Mason5f39d392007-10-15 16:14:19 -04001989 btrfs_set_header_generation(c, trans->transid);
Yan Zheng5d4f98a2009-06-10 10:45:14 -04001990 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
Chris Mason5f39d392007-10-15 16:14:19 -04001991 btrfs_set_header_owner(c, root->root_key.objectid);
Chris Masond5719762007-03-23 10:01:08 -04001992
Chris Mason5f39d392007-10-15 16:14:19 -04001993 write_extent_buffer(c, root->fs_info->fsid,
1994 (unsigned long)btrfs_header_fsid(c),
1995 BTRFS_FSID_SIZE);
Chris Masone17cade2008-04-15 15:41:47 -04001996
1997 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
1998 (unsigned long)btrfs_header_chunk_tree_uuid(c),
1999 BTRFS_UUID_SIZE);
2000
Chris Mason5f39d392007-10-15 16:14:19 -04002001 btrfs_set_node_key(c, &lower_key, 0);
Chris Masondb945352007-10-15 16:15:53 -04002002 btrfs_set_node_blockptr(c, 0, lower->start);
Chris Mason7bb86312007-12-11 09:25:06 -05002003 lower_gen = btrfs_header_generation(lower);
Zheng Yan31840ae2008-09-23 13:14:14 -04002004 WARN_ON(lower_gen != trans->transid);
Chris Mason7bb86312007-12-11 09:25:06 -05002005
2006 btrfs_set_node_ptr_generation(c, 0, lower_gen);
Chris Mason5f39d392007-10-15 16:14:19 -04002007
2008 btrfs_mark_buffer_dirty(c);
Chris Masond5719762007-03-23 10:01:08 -04002009
Chris Mason925baed2008-06-25 16:01:30 -04002010 spin_lock(&root->node_lock);
2011 old = root->node;
Chris Mason5f39d392007-10-15 16:14:19 -04002012 root->node = c;
Chris Mason925baed2008-06-25 16:01:30 -04002013 spin_unlock(&root->node_lock);
2014
2015 /* the super has an extra ref to root->node */
2016 free_extent_buffer(old);
2017
Chris Mason0b86a832008-03-24 15:01:56 -04002018 add_root_to_dirty_list(root);
Chris Mason5f39d392007-10-15 16:14:19 -04002019 extent_buffer_get(c);
2020 path->nodes[level] = c;
Chris Mason925baed2008-06-25 16:01:30 -04002021 path->locks[level] = 1;
Chris Mason5c680ed2007-02-22 11:39:13 -05002022 path->slots[level] = 0;
2023 return 0;
2024}
2025
Chris Mason74123bd2007-02-02 11:05:29 -05002026/*
2027 * worker function to insert a single pointer in a node.
2028 * the node should have enough room for the pointer already
Chris Mason97571fd2007-02-24 13:39:08 -05002029 *
Chris Mason74123bd2007-02-02 11:05:29 -05002030 * slot and level indicate where you want the key to go, and
2031 * blocknr is the block the key points to.
Chris Masonaa5d6be2007-02-28 16:35:06 -05002032 *
2033 * returns zero on success and < 0 on any error
Chris Mason74123bd2007-02-02 11:05:29 -05002034 */
Chris Masone089f052007-03-16 16:20:31 -04002035static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
2036 *root, struct btrfs_path *path, struct btrfs_disk_key
Chris Masondb945352007-10-15 16:15:53 -04002037 *key, u64 bytenr, int slot, int level)
Chris Mason74123bd2007-02-02 11:05:29 -05002038{
Chris Mason5f39d392007-10-15 16:14:19 -04002039 struct extent_buffer *lower;
Chris Mason74123bd2007-02-02 11:05:29 -05002040 int nritems;
Chris Mason5c680ed2007-02-22 11:39:13 -05002041
2042 BUG_ON(!path->nodes[level]);
Yan, Zhengf0486c62010-05-16 10:46:25 -04002043 btrfs_assert_tree_locked(path->nodes[level]);
Chris Mason5f39d392007-10-15 16:14:19 -04002044 lower = path->nodes[level];
2045 nritems = btrfs_header_nritems(lower);
Stoyan Gaydarovc2934982009-04-02 17:05:11 -04002046 BUG_ON(slot > nritems);
Chris Mason123abc82007-03-14 14:14:43 -04002047 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
Chris Mason74123bd2007-02-02 11:05:29 -05002048 BUG();
2049 if (slot != nritems) {
Chris Mason5f39d392007-10-15 16:14:19 -04002050 memmove_extent_buffer(lower,
2051 btrfs_node_key_ptr_offset(slot + 1),
2052 btrfs_node_key_ptr_offset(slot),
Chris Masond6025572007-03-30 14:27:56 -04002053 (nritems - slot) * sizeof(struct btrfs_key_ptr));
Chris Mason74123bd2007-02-02 11:05:29 -05002054 }
Chris Mason5f39d392007-10-15 16:14:19 -04002055 btrfs_set_node_key(lower, key, slot);
Chris Masondb945352007-10-15 16:15:53 -04002056 btrfs_set_node_blockptr(lower, slot, bytenr);
Chris Mason74493f72007-12-11 09:25:06 -05002057 WARN_ON(trans->transid == 0);
2058 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
Chris Mason5f39d392007-10-15 16:14:19 -04002059 btrfs_set_header_nritems(lower, nritems + 1);
2060 btrfs_mark_buffer_dirty(lower);
Chris Mason74123bd2007-02-02 11:05:29 -05002061 return 0;
2062}
2063
Chris Mason97571fd2007-02-24 13:39:08 -05002064/*
2065 * split the node at the specified level in path in two.
2066 * The path is corrected to point to the appropriate node after the split
2067 *
2068 * Before splitting this tries to make some room in the node by pushing
2069 * left and right, if either one works, it returns right away.
Chris Masonaa5d6be2007-02-28 16:35:06 -05002070 *
2071 * returns 0 on success and < 0 on failure
Chris Mason97571fd2007-02-24 13:39:08 -05002072 */
Chris Masone02119d2008-09-05 16:13:11 -04002073static noinline int split_node(struct btrfs_trans_handle *trans,
2074 struct btrfs_root *root,
2075 struct btrfs_path *path, int level)
Chris Masonbe0e5c02007-01-26 15:51:26 -05002076{
Chris Mason5f39d392007-10-15 16:14:19 -04002077 struct extent_buffer *c;
2078 struct extent_buffer *split;
2079 struct btrfs_disk_key disk_key;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002080 int mid;
Chris Mason5c680ed2007-02-22 11:39:13 -05002081 int ret;
Chris Masonaa5d6be2007-02-28 16:35:06 -05002082 int wret;
Chris Mason7518a232007-03-12 12:01:18 -04002083 u32 c_nritems;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002084
Chris Mason5f39d392007-10-15 16:14:19 -04002085 c = path->nodes[level];
Chris Mason7bb86312007-12-11 09:25:06 -05002086 WARN_ON(btrfs_header_generation(c) != trans->transid);
Chris Mason5f39d392007-10-15 16:14:19 -04002087 if (c == root->node) {
Chris Mason5c680ed2007-02-22 11:39:13 -05002088 /* trying to split the root, lets make a new one */
Chris Masone089f052007-03-16 16:20:31 -04002089 ret = insert_new_root(trans, root, path, level + 1);
Chris Mason5c680ed2007-02-22 11:39:13 -05002090 if (ret)
2091 return ret;
Chris Masonb3612422009-05-13 19:12:15 -04002092 } else {
Chris Masone66f7092007-04-20 13:16:02 -04002093 ret = push_nodes_for_insert(trans, root, path, level);
Chris Mason5f39d392007-10-15 16:14:19 -04002094 c = path->nodes[level];
2095 if (!ret && btrfs_header_nritems(c) <
Chris Masonc448acf2008-04-24 09:34:34 -04002096 BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
Chris Masone66f7092007-04-20 13:16:02 -04002097 return 0;
Chris Mason54aa1f42007-06-22 14:16:25 -04002098 if (ret < 0)
2099 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002100 }
Chris Masone66f7092007-04-20 13:16:02 -04002101
Chris Mason5f39d392007-10-15 16:14:19 -04002102 c_nritems = btrfs_header_nritems(c);
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002103 mid = (c_nritems + 1) / 2;
2104 btrfs_node_key(c, &disk_key, mid);
Chris Mason7bb86312007-12-11 09:25:06 -05002105
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002106 split = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
Zheng Yan31840ae2008-09-23 13:14:14 -04002107 root->root_key.objectid,
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002108 &disk_key, level, c->start, 0);
Chris Mason5f39d392007-10-15 16:14:19 -04002109 if (IS_ERR(split))
2110 return PTR_ERR(split);
Chris Mason54aa1f42007-06-22 14:16:25 -04002111
Yan, Zhengf0486c62010-05-16 10:46:25 -04002112 root_add_used(root, root->nodesize);
2113
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002114 memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
Chris Mason5f39d392007-10-15 16:14:19 -04002115 btrfs_set_header_level(split, btrfs_header_level(c));
Chris Masondb945352007-10-15 16:15:53 -04002116 btrfs_set_header_bytenr(split, split->start);
Chris Mason5f39d392007-10-15 16:14:19 -04002117 btrfs_set_header_generation(split, trans->transid);
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002118 btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
Chris Mason5f39d392007-10-15 16:14:19 -04002119 btrfs_set_header_owner(split, root->root_key.objectid);
2120 write_extent_buffer(split, root->fs_info->fsid,
2121 (unsigned long)btrfs_header_fsid(split),
2122 BTRFS_FSID_SIZE);
Chris Masone17cade2008-04-15 15:41:47 -04002123 write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
2124 (unsigned long)btrfs_header_chunk_tree_uuid(split),
2125 BTRFS_UUID_SIZE);
Chris Mason5f39d392007-10-15 16:14:19 -04002126
Chris Mason5f39d392007-10-15 16:14:19 -04002127
2128 copy_extent_buffer(split, c,
2129 btrfs_node_key_ptr_offset(0),
2130 btrfs_node_key_ptr_offset(mid),
2131 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
2132 btrfs_set_header_nritems(split, c_nritems - mid);
2133 btrfs_set_header_nritems(c, mid);
Chris Masonaa5d6be2007-02-28 16:35:06 -05002134 ret = 0;
2135
Chris Mason5f39d392007-10-15 16:14:19 -04002136 btrfs_mark_buffer_dirty(c);
2137 btrfs_mark_buffer_dirty(split);
2138
Chris Masondb945352007-10-15 16:15:53 -04002139 wret = insert_ptr(trans, root, path, &disk_key, split->start,
Chris Mason5f39d392007-10-15 16:14:19 -04002140 path->slots[level + 1] + 1,
Chris Mason123abc82007-03-14 14:14:43 -04002141 level + 1);
Chris Masonaa5d6be2007-02-28 16:35:06 -05002142 if (wret)
2143 ret = wret;
2144
Chris Mason5de08d72007-02-24 06:24:44 -05002145 if (path->slots[level] >= mid) {
Chris Mason5c680ed2007-02-22 11:39:13 -05002146 path->slots[level] -= mid;
Chris Mason925baed2008-06-25 16:01:30 -04002147 btrfs_tree_unlock(c);
Chris Mason5f39d392007-10-15 16:14:19 -04002148 free_extent_buffer(c);
2149 path->nodes[level] = split;
Chris Mason5c680ed2007-02-22 11:39:13 -05002150 path->slots[level + 1] += 1;
2151 } else {
Chris Mason925baed2008-06-25 16:01:30 -04002152 btrfs_tree_unlock(split);
Chris Mason5f39d392007-10-15 16:14:19 -04002153 free_extent_buffer(split);
Chris Masonbe0e5c02007-01-26 15:51:26 -05002154 }
Chris Masonaa5d6be2007-02-28 16:35:06 -05002155 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002156}
2157
Chris Mason74123bd2007-02-02 11:05:29 -05002158/*
2159 * how many bytes are required to store the items in a leaf. start
2160 * and nr indicate which items in the leaf to check. This totals up the
2161 * space used both by the item structs and the item data
2162 */
Chris Mason5f39d392007-10-15 16:14:19 -04002163static int leaf_space_used(struct extent_buffer *l, int start, int nr)
Chris Masonbe0e5c02007-01-26 15:51:26 -05002164{
2165 int data_len;
Chris Mason5f39d392007-10-15 16:14:19 -04002166 int nritems = btrfs_header_nritems(l);
Chris Masond4dbff92007-04-04 14:08:15 -04002167 int end = min(nritems, start + nr) - 1;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002168
2169 if (!nr)
2170 return 0;
Chris Mason5f39d392007-10-15 16:14:19 -04002171 data_len = btrfs_item_end_nr(l, start);
2172 data_len = data_len - btrfs_item_offset_nr(l, end);
Chris Mason0783fcf2007-03-12 20:12:07 -04002173 data_len += sizeof(struct btrfs_item) * nr;
Chris Masond4dbff92007-04-04 14:08:15 -04002174 WARN_ON(data_len < 0);
Chris Masonbe0e5c02007-01-26 15:51:26 -05002175 return data_len;
2176}
2177
Chris Mason74123bd2007-02-02 11:05:29 -05002178/*
Chris Masond4dbff92007-04-04 14:08:15 -04002179 * The space between the end of the leaf items and
2180 * the start of the leaf data. IOW, how much room
2181 * the leaf has left for both items and data
2182 */
Chris Masond3977122009-01-05 21:25:51 -05002183noinline int btrfs_leaf_free_space(struct btrfs_root *root,
Chris Masone02119d2008-09-05 16:13:11 -04002184 struct extent_buffer *leaf)
Chris Masond4dbff92007-04-04 14:08:15 -04002185{
Chris Mason5f39d392007-10-15 16:14:19 -04002186 int nritems = btrfs_header_nritems(leaf);
2187 int ret;
2188 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
2189 if (ret < 0) {
Chris Masond3977122009-01-05 21:25:51 -05002190 printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, "
2191 "used %d nritems %d\n",
Jens Axboeae2f5412007-10-19 09:22:59 -04002192 ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
Chris Mason5f39d392007-10-15 16:14:19 -04002193 leaf_space_used(leaf, 0, nritems), nritems);
2194 }
2195 return ret;
Chris Masond4dbff92007-04-04 14:08:15 -04002196}
2197
Chris Mason99d8f832010-07-07 10:51:48 -04002198/*
2199 * min slot controls the lowest index we're willing to push to the
2200 * right. We'll push up to and including min_slot, but no lower
2201 */
Chris Mason44871b12009-03-13 10:04:31 -04002202static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
2203 struct btrfs_root *root,
2204 struct btrfs_path *path,
2205 int data_size, int empty,
2206 struct extent_buffer *right,
Chris Mason99d8f832010-07-07 10:51:48 -04002207 int free_space, u32 left_nritems,
2208 u32 min_slot)
Chris Mason00ec4c52007-02-24 12:47:20 -05002209{
Chris Mason5f39d392007-10-15 16:14:19 -04002210 struct extent_buffer *left = path->nodes[0];
Chris Mason44871b12009-03-13 10:04:31 -04002211 struct extent_buffer *upper = path->nodes[1];
Chris Mason5f39d392007-10-15 16:14:19 -04002212 struct btrfs_disk_key disk_key;
Chris Mason00ec4c52007-02-24 12:47:20 -05002213 int slot;
Chris Mason34a38212007-11-07 13:31:03 -05002214 u32 i;
Chris Mason00ec4c52007-02-24 12:47:20 -05002215 int push_space = 0;
2216 int push_items = 0;
Chris Mason0783fcf2007-03-12 20:12:07 -04002217 struct btrfs_item *item;
Chris Mason34a38212007-11-07 13:31:03 -05002218 u32 nr;
Chris Mason7518a232007-03-12 12:01:18 -04002219 u32 right_nritems;
Chris Mason5f39d392007-10-15 16:14:19 -04002220 u32 data_end;
Chris Masondb945352007-10-15 16:15:53 -04002221 u32 this_item_size;
Chris Mason00ec4c52007-02-24 12:47:20 -05002222
Chris Mason34a38212007-11-07 13:31:03 -05002223 if (empty)
2224 nr = 0;
2225 else
Chris Mason99d8f832010-07-07 10:51:48 -04002226 nr = max_t(u32, 1, min_slot);
Chris Mason34a38212007-11-07 13:31:03 -05002227
Zheng Yan31840ae2008-09-23 13:14:14 -04002228 if (path->slots[0] >= left_nritems)
Yan Zheng87b29b22008-12-17 10:21:48 -05002229 push_space += data_size;
Zheng Yan31840ae2008-09-23 13:14:14 -04002230
Chris Mason44871b12009-03-13 10:04:31 -04002231 slot = path->slots[1];
Chris Mason34a38212007-11-07 13:31:03 -05002232 i = left_nritems - 1;
2233 while (i >= nr) {
Chris Mason5f39d392007-10-15 16:14:19 -04002234 item = btrfs_item_nr(left, i);
Chris Masondb945352007-10-15 16:15:53 -04002235
Zheng Yan31840ae2008-09-23 13:14:14 -04002236 if (!empty && push_items > 0) {
2237 if (path->slots[0] > i)
2238 break;
2239 if (path->slots[0] == i) {
2240 int space = btrfs_leaf_free_space(root, left);
2241 if (space + push_space * 2 > free_space)
2242 break;
2243 }
2244 }
2245
Chris Mason00ec4c52007-02-24 12:47:20 -05002246 if (path->slots[0] == i)
Yan Zheng87b29b22008-12-17 10:21:48 -05002247 push_space += data_size;
Chris Masondb945352007-10-15 16:15:53 -04002248
2249 if (!left->map_token) {
2250 map_extent_buffer(left, (unsigned long)item,
2251 sizeof(struct btrfs_item),
2252 &left->map_token, &left->kaddr,
2253 &left->map_start, &left->map_len,
2254 KM_USER1);
2255 }
2256
2257 this_item_size = btrfs_item_size(left, item);
2258 if (this_item_size + sizeof(*item) + push_space > free_space)
Chris Mason00ec4c52007-02-24 12:47:20 -05002259 break;
Zheng Yan31840ae2008-09-23 13:14:14 -04002260
Chris Mason00ec4c52007-02-24 12:47:20 -05002261 push_items++;
Chris Masondb945352007-10-15 16:15:53 -04002262 push_space += this_item_size + sizeof(*item);
Chris Mason34a38212007-11-07 13:31:03 -05002263 if (i == 0)
2264 break;
2265 i--;
Chris Masondb945352007-10-15 16:15:53 -04002266 }
2267 if (left->map_token) {
2268 unmap_extent_buffer(left, left->map_token, KM_USER1);
2269 left->map_token = NULL;
Chris Mason00ec4c52007-02-24 12:47:20 -05002270 }
Chris Mason5f39d392007-10-15 16:14:19 -04002271
Chris Mason925baed2008-06-25 16:01:30 -04002272 if (push_items == 0)
2273 goto out_unlock;
Chris Mason5f39d392007-10-15 16:14:19 -04002274
Chris Mason34a38212007-11-07 13:31:03 -05002275 if (!empty && push_items == left_nritems)
Chris Masona429e512007-04-18 16:15:28 -04002276 WARN_ON(1);
Chris Mason5f39d392007-10-15 16:14:19 -04002277
Chris Mason00ec4c52007-02-24 12:47:20 -05002278 /* push left to right */
Chris Mason5f39d392007-10-15 16:14:19 -04002279 right_nritems = btrfs_header_nritems(right);
Chris Mason34a38212007-11-07 13:31:03 -05002280
Chris Mason5f39d392007-10-15 16:14:19 -04002281 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
Chris Mason123abc82007-03-14 14:14:43 -04002282 push_space -= leaf_data_end(root, left);
Chris Mason5f39d392007-10-15 16:14:19 -04002283
Chris Mason00ec4c52007-02-24 12:47:20 -05002284 /* make room in the right data area */
Chris Mason5f39d392007-10-15 16:14:19 -04002285 data_end = leaf_data_end(root, right);
2286 memmove_extent_buffer(right,
2287 btrfs_leaf_data(right) + data_end - push_space,
2288 btrfs_leaf_data(right) + data_end,
2289 BTRFS_LEAF_DATA_SIZE(root) - data_end);
2290
Chris Mason00ec4c52007-02-24 12:47:20 -05002291 /* copy from the left data area */
Chris Mason5f39d392007-10-15 16:14:19 -04002292 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
Chris Masond6025572007-03-30 14:27:56 -04002293 BTRFS_LEAF_DATA_SIZE(root) - push_space,
2294 btrfs_leaf_data(left) + leaf_data_end(root, left),
2295 push_space);
Chris Mason5f39d392007-10-15 16:14:19 -04002296
2297 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
2298 btrfs_item_nr_offset(0),
2299 right_nritems * sizeof(struct btrfs_item));
2300
Chris Mason00ec4c52007-02-24 12:47:20 -05002301 /* copy the items from left to right */
Chris Mason5f39d392007-10-15 16:14:19 -04002302 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
2303 btrfs_item_nr_offset(left_nritems - push_items),
2304 push_items * sizeof(struct btrfs_item));
Chris Mason00ec4c52007-02-24 12:47:20 -05002305
2306 /* update the item pointers */
Chris Mason7518a232007-03-12 12:01:18 -04002307 right_nritems += push_items;
Chris Mason5f39d392007-10-15 16:14:19 -04002308 btrfs_set_header_nritems(right, right_nritems);
Chris Mason123abc82007-03-14 14:14:43 -04002309 push_space = BTRFS_LEAF_DATA_SIZE(root);
Chris Mason7518a232007-03-12 12:01:18 -04002310 for (i = 0; i < right_nritems; i++) {
Chris Mason5f39d392007-10-15 16:14:19 -04002311 item = btrfs_item_nr(right, i);
Chris Masondb945352007-10-15 16:15:53 -04002312 if (!right->map_token) {
2313 map_extent_buffer(right, (unsigned long)item,
2314 sizeof(struct btrfs_item),
2315 &right->map_token, &right->kaddr,
2316 &right->map_start, &right->map_len,
2317 KM_USER1);
2318 }
2319 push_space -= btrfs_item_size(right, item);
2320 btrfs_set_item_offset(right, item, push_space);
2321 }
2322
2323 if (right->map_token) {
2324 unmap_extent_buffer(right, right->map_token, KM_USER1);
2325 right->map_token = NULL;
Chris Mason00ec4c52007-02-24 12:47:20 -05002326 }
Chris Mason7518a232007-03-12 12:01:18 -04002327 left_nritems -= push_items;
Chris Mason5f39d392007-10-15 16:14:19 -04002328 btrfs_set_header_nritems(left, left_nritems);
Chris Mason00ec4c52007-02-24 12:47:20 -05002329
Chris Mason34a38212007-11-07 13:31:03 -05002330 if (left_nritems)
2331 btrfs_mark_buffer_dirty(left);
Yan, Zhengf0486c62010-05-16 10:46:25 -04002332 else
2333 clean_tree_block(trans, root, left);
2334
Chris Mason5f39d392007-10-15 16:14:19 -04002335 btrfs_mark_buffer_dirty(right);
Chris Masona429e512007-04-18 16:15:28 -04002336
Chris Mason5f39d392007-10-15 16:14:19 -04002337 btrfs_item_key(right, &disk_key, 0);
2338 btrfs_set_node_key(upper, &disk_key, slot + 1);
Chris Masond6025572007-03-30 14:27:56 -04002339 btrfs_mark_buffer_dirty(upper);
Chris Mason02217ed2007-03-02 16:08:05 -05002340
Chris Mason00ec4c52007-02-24 12:47:20 -05002341 /* then fixup the leaf pointer in the path */
Chris Mason7518a232007-03-12 12:01:18 -04002342 if (path->slots[0] >= left_nritems) {
2343 path->slots[0] -= left_nritems;
Chris Mason925baed2008-06-25 16:01:30 -04002344 if (btrfs_header_nritems(path->nodes[0]) == 0)
2345 clean_tree_block(trans, root, path->nodes[0]);
2346 btrfs_tree_unlock(path->nodes[0]);
Chris Mason5f39d392007-10-15 16:14:19 -04002347 free_extent_buffer(path->nodes[0]);
2348 path->nodes[0] = right;
Chris Mason00ec4c52007-02-24 12:47:20 -05002349 path->slots[1] += 1;
2350 } else {
Chris Mason925baed2008-06-25 16:01:30 -04002351 btrfs_tree_unlock(right);
Chris Mason5f39d392007-10-15 16:14:19 -04002352 free_extent_buffer(right);
Chris Mason00ec4c52007-02-24 12:47:20 -05002353 }
2354 return 0;
Chris Mason925baed2008-06-25 16:01:30 -04002355
2356out_unlock:
2357 btrfs_tree_unlock(right);
2358 free_extent_buffer(right);
2359 return 1;
Chris Mason00ec4c52007-02-24 12:47:20 -05002360}
Chris Mason925baed2008-06-25 16:01:30 -04002361
Chris Mason00ec4c52007-02-24 12:47:20 -05002362/*
Chris Mason44871b12009-03-13 10:04:31 -04002363 * push some data in the path leaf to the right, trying to free up at
2364 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2365 *
2366 * returns 1 if the push failed because the other node didn't have enough
2367 * room, 0 if everything worked out and < 0 if there were major errors.
Chris Mason99d8f832010-07-07 10:51:48 -04002368 *
2369 * this will push starting from min_slot to the end of the leaf. It won't
2370 * push any slot lower than min_slot
Chris Mason44871b12009-03-13 10:04:31 -04002371 */
2372static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Mason99d8f832010-07-07 10:51:48 -04002373 *root, struct btrfs_path *path,
2374 int min_data_size, int data_size,
2375 int empty, u32 min_slot)
Chris Mason44871b12009-03-13 10:04:31 -04002376{
2377 struct extent_buffer *left = path->nodes[0];
2378 struct extent_buffer *right;
2379 struct extent_buffer *upper;
2380 int slot;
2381 int free_space;
2382 u32 left_nritems;
2383 int ret;
2384
2385 if (!path->nodes[1])
2386 return 1;
2387
2388 slot = path->slots[1];
2389 upper = path->nodes[1];
2390 if (slot >= btrfs_header_nritems(upper) - 1)
2391 return 1;
2392
2393 btrfs_assert_tree_locked(path->nodes[1]);
2394
2395 right = read_node_slot(root, upper, slot + 1);
Tsutomu Itoh91ca3382011-01-05 02:32:22 +00002396 if (right == NULL)
2397 return 1;
2398
Chris Mason44871b12009-03-13 10:04:31 -04002399 btrfs_tree_lock(right);
2400 btrfs_set_lock_blocking(right);
2401
2402 free_space = btrfs_leaf_free_space(root, right);
2403 if (free_space < data_size)
2404 goto out_unlock;
2405
2406 /* cow and double check */
2407 ret = btrfs_cow_block(trans, root, right, upper,
2408 slot + 1, &right);
2409 if (ret)
2410 goto out_unlock;
2411
2412 free_space = btrfs_leaf_free_space(root, right);
2413 if (free_space < data_size)
2414 goto out_unlock;
2415
2416 left_nritems = btrfs_header_nritems(left);
2417 if (left_nritems == 0)
2418 goto out_unlock;
2419
Chris Mason99d8f832010-07-07 10:51:48 -04002420 return __push_leaf_right(trans, root, path, min_data_size, empty,
2421 right, free_space, left_nritems, min_slot);
Chris Mason44871b12009-03-13 10:04:31 -04002422out_unlock:
2423 btrfs_tree_unlock(right);
2424 free_extent_buffer(right);
2425 return 1;
2426}
2427
2428/*
Chris Mason74123bd2007-02-02 11:05:29 -05002429 * push some data in the path leaf to the left, trying to free up at
2430 * least data_size bytes. returns zero if the push worked, nonzero otherwise
Chris Mason99d8f832010-07-07 10:51:48 -04002431 *
2432 * max_slot can put a limit on how far into the leaf we'll push items. The
2433 * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
2434 * items
Chris Mason74123bd2007-02-02 11:05:29 -05002435 */
Chris Mason44871b12009-03-13 10:04:31 -04002436static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
2437 struct btrfs_root *root,
2438 struct btrfs_path *path, int data_size,
2439 int empty, struct extent_buffer *left,
Chris Mason99d8f832010-07-07 10:51:48 -04002440 int free_space, u32 right_nritems,
2441 u32 max_slot)
Chris Masonbe0e5c02007-01-26 15:51:26 -05002442{
Chris Mason5f39d392007-10-15 16:14:19 -04002443 struct btrfs_disk_key disk_key;
2444 struct extent_buffer *right = path->nodes[0];
Chris Masonbe0e5c02007-01-26 15:51:26 -05002445 int i;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002446 int push_space = 0;
2447 int push_items = 0;
Chris Mason0783fcf2007-03-12 20:12:07 -04002448 struct btrfs_item *item;
Chris Mason7518a232007-03-12 12:01:18 -04002449 u32 old_left_nritems;
Chris Mason34a38212007-11-07 13:31:03 -05002450 u32 nr;
Chris Masonaa5d6be2007-02-28 16:35:06 -05002451 int ret = 0;
2452 int wret;
Chris Masondb945352007-10-15 16:15:53 -04002453 u32 this_item_size;
2454 u32 old_left_item_size;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002455
Chris Mason34a38212007-11-07 13:31:03 -05002456 if (empty)
Chris Mason99d8f832010-07-07 10:51:48 -04002457 nr = min(right_nritems, max_slot);
Chris Mason34a38212007-11-07 13:31:03 -05002458 else
Chris Mason99d8f832010-07-07 10:51:48 -04002459 nr = min(right_nritems - 1, max_slot);
Chris Mason34a38212007-11-07 13:31:03 -05002460
2461 for (i = 0; i < nr; i++) {
Chris Mason5f39d392007-10-15 16:14:19 -04002462 item = btrfs_item_nr(right, i);
Chris Masondb945352007-10-15 16:15:53 -04002463 if (!right->map_token) {
2464 map_extent_buffer(right, (unsigned long)item,
2465 sizeof(struct btrfs_item),
2466 &right->map_token, &right->kaddr,
2467 &right->map_start, &right->map_len,
2468 KM_USER1);
2469 }
2470
Zheng Yan31840ae2008-09-23 13:14:14 -04002471 if (!empty && push_items > 0) {
2472 if (path->slots[0] < i)
2473 break;
2474 if (path->slots[0] == i) {
2475 int space = btrfs_leaf_free_space(root, right);
2476 if (space + push_space * 2 > free_space)
2477 break;
2478 }
2479 }
2480
Chris Masonbe0e5c02007-01-26 15:51:26 -05002481 if (path->slots[0] == i)
Yan Zheng87b29b22008-12-17 10:21:48 -05002482 push_space += data_size;
Chris Masondb945352007-10-15 16:15:53 -04002483
2484 this_item_size = btrfs_item_size(right, item);
2485 if (this_item_size + sizeof(*item) + push_space > free_space)
Chris Masonbe0e5c02007-01-26 15:51:26 -05002486 break;
Chris Masondb945352007-10-15 16:15:53 -04002487
Chris Masonbe0e5c02007-01-26 15:51:26 -05002488 push_items++;
Chris Masondb945352007-10-15 16:15:53 -04002489 push_space += this_item_size + sizeof(*item);
Chris Masonbe0e5c02007-01-26 15:51:26 -05002490 }
Chris Masondb945352007-10-15 16:15:53 -04002491
2492 if (right->map_token) {
2493 unmap_extent_buffer(right, right->map_token, KM_USER1);
2494 right->map_token = NULL;
2495 }
2496
Chris Masonbe0e5c02007-01-26 15:51:26 -05002497 if (push_items == 0) {
Chris Mason925baed2008-06-25 16:01:30 -04002498 ret = 1;
2499 goto out;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002500 }
Chris Mason34a38212007-11-07 13:31:03 -05002501 if (!empty && push_items == btrfs_header_nritems(right))
Chris Masona429e512007-04-18 16:15:28 -04002502 WARN_ON(1);
Chris Mason5f39d392007-10-15 16:14:19 -04002503
Chris Masonbe0e5c02007-01-26 15:51:26 -05002504 /* push data from right to left */
Chris Mason5f39d392007-10-15 16:14:19 -04002505 copy_extent_buffer(left, right,
2506 btrfs_item_nr_offset(btrfs_header_nritems(left)),
2507 btrfs_item_nr_offset(0),
2508 push_items * sizeof(struct btrfs_item));
2509
Chris Mason123abc82007-03-14 14:14:43 -04002510 push_space = BTRFS_LEAF_DATA_SIZE(root) -
Chris Masond3977122009-01-05 21:25:51 -05002511 btrfs_item_offset_nr(right, push_items - 1);
Chris Mason5f39d392007-10-15 16:14:19 -04002512
2513 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
Chris Masond6025572007-03-30 14:27:56 -04002514 leaf_data_end(root, left) - push_space,
2515 btrfs_leaf_data(right) +
Chris Mason5f39d392007-10-15 16:14:19 -04002516 btrfs_item_offset_nr(right, push_items - 1),
Chris Masond6025572007-03-30 14:27:56 -04002517 push_space);
Chris Mason5f39d392007-10-15 16:14:19 -04002518 old_left_nritems = btrfs_header_nritems(left);
Yan Zheng87b29b22008-12-17 10:21:48 -05002519 BUG_ON(old_left_nritems <= 0);
Chris Masoneb60cea2007-02-02 09:18:22 -05002520
Chris Masondb945352007-10-15 16:15:53 -04002521 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
Chris Mason0783fcf2007-03-12 20:12:07 -04002522 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
Chris Mason5f39d392007-10-15 16:14:19 -04002523 u32 ioff;
Chris Masondb945352007-10-15 16:15:53 -04002524
Chris Mason5f39d392007-10-15 16:14:19 -04002525 item = btrfs_item_nr(left, i);
Chris Masondb945352007-10-15 16:15:53 -04002526 if (!left->map_token) {
2527 map_extent_buffer(left, (unsigned long)item,
2528 sizeof(struct btrfs_item),
2529 &left->map_token, &left->kaddr,
2530 &left->map_start, &left->map_len,
2531 KM_USER1);
2532 }
2533
Chris Mason5f39d392007-10-15 16:14:19 -04002534 ioff = btrfs_item_offset(left, item);
2535 btrfs_set_item_offset(left, item,
Chris Masondb945352007-10-15 16:15:53 -04002536 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
Chris Masonbe0e5c02007-01-26 15:51:26 -05002537 }
Chris Mason5f39d392007-10-15 16:14:19 -04002538 btrfs_set_header_nritems(left, old_left_nritems + push_items);
Chris Masondb945352007-10-15 16:15:53 -04002539 if (left->map_token) {
2540 unmap_extent_buffer(left, left->map_token, KM_USER1);
2541 left->map_token = NULL;
2542 }
Chris Masonbe0e5c02007-01-26 15:51:26 -05002543
2544 /* fixup right node */
Chris Mason34a38212007-11-07 13:31:03 -05002545 if (push_items > right_nritems) {
Chris Masond3977122009-01-05 21:25:51 -05002546 printk(KERN_CRIT "push items %d nr %u\n", push_items,
2547 right_nritems);
Chris Mason34a38212007-11-07 13:31:03 -05002548 WARN_ON(1);
2549 }
Chris Mason5f39d392007-10-15 16:14:19 -04002550
Chris Mason34a38212007-11-07 13:31:03 -05002551 if (push_items < right_nritems) {
2552 push_space = btrfs_item_offset_nr(right, push_items - 1) -
2553 leaf_data_end(root, right);
2554 memmove_extent_buffer(right, btrfs_leaf_data(right) +
2555 BTRFS_LEAF_DATA_SIZE(root) - push_space,
2556 btrfs_leaf_data(right) +
2557 leaf_data_end(root, right), push_space);
2558
2559 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
Chris Mason5f39d392007-10-15 16:14:19 -04002560 btrfs_item_nr_offset(push_items),
2561 (btrfs_header_nritems(right) - push_items) *
2562 sizeof(struct btrfs_item));
Chris Mason34a38212007-11-07 13:31:03 -05002563 }
Yaneef1c492007-11-26 10:58:13 -05002564 right_nritems -= push_items;
2565 btrfs_set_header_nritems(right, right_nritems);
Chris Mason123abc82007-03-14 14:14:43 -04002566 push_space = BTRFS_LEAF_DATA_SIZE(root);
Chris Mason5f39d392007-10-15 16:14:19 -04002567 for (i = 0; i < right_nritems; i++) {
2568 item = btrfs_item_nr(right, i);
Chris Masondb945352007-10-15 16:15:53 -04002569
2570 if (!right->map_token) {
2571 map_extent_buffer(right, (unsigned long)item,
2572 sizeof(struct btrfs_item),
2573 &right->map_token, &right->kaddr,
2574 &right->map_start, &right->map_len,
2575 KM_USER1);
2576 }
2577
2578 push_space = push_space - btrfs_item_size(right, item);
2579 btrfs_set_item_offset(right, item, push_space);
2580 }
2581 if (right->map_token) {
2582 unmap_extent_buffer(right, right->map_token, KM_USER1);
2583 right->map_token = NULL;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002584 }
Chris Masoneb60cea2007-02-02 09:18:22 -05002585
Chris Mason5f39d392007-10-15 16:14:19 -04002586 btrfs_mark_buffer_dirty(left);
Chris Mason34a38212007-11-07 13:31:03 -05002587 if (right_nritems)
2588 btrfs_mark_buffer_dirty(right);
Yan, Zhengf0486c62010-05-16 10:46:25 -04002589 else
2590 clean_tree_block(trans, root, right);
Chris Mason098f59c2007-05-11 11:33:21 -04002591
Chris Mason5f39d392007-10-15 16:14:19 -04002592 btrfs_item_key(right, &disk_key, 0);
2593 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
Chris Masonaa5d6be2007-02-28 16:35:06 -05002594 if (wret)
2595 ret = wret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002596
2597 /* then fixup the leaf pointer in the path */
2598 if (path->slots[0] < push_items) {
2599 path->slots[0] += old_left_nritems;
Chris Mason925baed2008-06-25 16:01:30 -04002600 btrfs_tree_unlock(path->nodes[0]);
Chris Mason5f39d392007-10-15 16:14:19 -04002601 free_extent_buffer(path->nodes[0]);
2602 path->nodes[0] = left;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002603 path->slots[1] -= 1;
2604 } else {
Chris Mason925baed2008-06-25 16:01:30 -04002605 btrfs_tree_unlock(left);
Chris Mason5f39d392007-10-15 16:14:19 -04002606 free_extent_buffer(left);
Chris Masonbe0e5c02007-01-26 15:51:26 -05002607 path->slots[0] -= push_items;
2608 }
Chris Masoneb60cea2007-02-02 09:18:22 -05002609 BUG_ON(path->slots[0] < 0);
Chris Masonaa5d6be2007-02-28 16:35:06 -05002610 return ret;
Chris Mason925baed2008-06-25 16:01:30 -04002611out:
2612 btrfs_tree_unlock(left);
2613 free_extent_buffer(left);
2614 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002615}
2616
Chris Mason74123bd2007-02-02 11:05:29 -05002617/*
Chris Mason44871b12009-03-13 10:04:31 -04002618 * push some data in the path leaf to the left, trying to free up at
2619 * least data_size bytes. returns zero if the push worked, nonzero otherwise
Chris Mason99d8f832010-07-07 10:51:48 -04002620 *
2621 * max_slot can put a limit on how far into the leaf we'll push items. The
2622 * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the
2623 * items
Chris Mason44871b12009-03-13 10:04:31 -04002624 */
2625static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Mason99d8f832010-07-07 10:51:48 -04002626 *root, struct btrfs_path *path, int min_data_size,
2627 int data_size, int empty, u32 max_slot)
Chris Mason44871b12009-03-13 10:04:31 -04002628{
2629 struct extent_buffer *right = path->nodes[0];
2630 struct extent_buffer *left;
2631 int slot;
2632 int free_space;
2633 u32 right_nritems;
2634 int ret = 0;
2635
2636 slot = path->slots[1];
2637 if (slot == 0)
2638 return 1;
2639 if (!path->nodes[1])
2640 return 1;
2641
2642 right_nritems = btrfs_header_nritems(right);
2643 if (right_nritems == 0)
2644 return 1;
2645
2646 btrfs_assert_tree_locked(path->nodes[1]);
2647
2648 left = read_node_slot(root, path->nodes[1], slot - 1);
Tsutomu Itoh91ca3382011-01-05 02:32:22 +00002649 if (left == NULL)
2650 return 1;
2651
Chris Mason44871b12009-03-13 10:04:31 -04002652 btrfs_tree_lock(left);
2653 btrfs_set_lock_blocking(left);
2654
2655 free_space = btrfs_leaf_free_space(root, left);
2656 if (free_space < data_size) {
2657 ret = 1;
2658 goto out;
2659 }
2660
2661 /* cow and double check */
2662 ret = btrfs_cow_block(trans, root, left,
2663 path->nodes[1], slot - 1, &left);
2664 if (ret) {
2665 /* we hit -ENOSPC, but it isn't fatal here */
2666 ret = 1;
2667 goto out;
2668 }
2669
2670 free_space = btrfs_leaf_free_space(root, left);
2671 if (free_space < data_size) {
2672 ret = 1;
2673 goto out;
2674 }
2675
Chris Mason99d8f832010-07-07 10:51:48 -04002676 return __push_leaf_left(trans, root, path, min_data_size,
2677 empty, left, free_space, right_nritems,
2678 max_slot);
Chris Mason44871b12009-03-13 10:04:31 -04002679out:
2680 btrfs_tree_unlock(left);
2681 free_extent_buffer(left);
2682 return ret;
2683}
2684
2685/*
Chris Mason74123bd2007-02-02 11:05:29 -05002686 * split the path's leaf in two, making sure there is at least data_size
2687 * available for the resulting leaf level of the path.
Chris Masonaa5d6be2007-02-28 16:35:06 -05002688 *
2689 * returns 0 if all went well and < 0 on failure.
Chris Mason74123bd2007-02-02 11:05:29 -05002690 */
Chris Mason44871b12009-03-13 10:04:31 -04002691static noinline int copy_for_split(struct btrfs_trans_handle *trans,
Chris Masone02119d2008-09-05 16:13:11 -04002692 struct btrfs_root *root,
Chris Mason44871b12009-03-13 10:04:31 -04002693 struct btrfs_path *path,
2694 struct extent_buffer *l,
2695 struct extent_buffer *right,
2696 int slot, int mid, int nritems)
Chris Masonbe0e5c02007-01-26 15:51:26 -05002697{
Chris Masonbe0e5c02007-01-26 15:51:26 -05002698 int data_copy_size;
2699 int rt_data_off;
2700 int i;
Chris Masond4dbff92007-04-04 14:08:15 -04002701 int ret = 0;
Chris Masonaa5d6be2007-02-28 16:35:06 -05002702 int wret;
Chris Masond4dbff92007-04-04 14:08:15 -04002703 struct btrfs_disk_key disk_key;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002704
Chris Mason5f39d392007-10-15 16:14:19 -04002705 nritems = nritems - mid;
2706 btrfs_set_header_nritems(right, nritems);
2707 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2708
2709 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2710 btrfs_item_nr_offset(mid),
2711 nritems * sizeof(struct btrfs_item));
2712
2713 copy_extent_buffer(right, l,
Chris Masond6025572007-03-30 14:27:56 -04002714 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2715 data_copy_size, btrfs_leaf_data(l) +
2716 leaf_data_end(root, l), data_copy_size);
Chris Mason74123bd2007-02-02 11:05:29 -05002717
Chris Mason5f39d392007-10-15 16:14:19 -04002718 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2719 btrfs_item_end_nr(l, mid);
2720
2721 for (i = 0; i < nritems; i++) {
2722 struct btrfs_item *item = btrfs_item_nr(right, i);
Chris Masondb945352007-10-15 16:15:53 -04002723 u32 ioff;
2724
2725 if (!right->map_token) {
2726 map_extent_buffer(right, (unsigned long)item,
2727 sizeof(struct btrfs_item),
2728 &right->map_token, &right->kaddr,
2729 &right->map_start, &right->map_len,
2730 KM_USER1);
2731 }
2732
2733 ioff = btrfs_item_offset(right, item);
Chris Mason5f39d392007-10-15 16:14:19 -04002734 btrfs_set_item_offset(right, item, ioff + rt_data_off);
Chris Mason0783fcf2007-03-12 20:12:07 -04002735 }
Chris Mason74123bd2007-02-02 11:05:29 -05002736
Chris Masondb945352007-10-15 16:15:53 -04002737 if (right->map_token) {
2738 unmap_extent_buffer(right, right->map_token, KM_USER1);
2739 right->map_token = NULL;
2740 }
2741
Chris Mason5f39d392007-10-15 16:14:19 -04002742 btrfs_set_header_nritems(l, mid);
Chris Masonaa5d6be2007-02-28 16:35:06 -05002743 ret = 0;
Chris Mason5f39d392007-10-15 16:14:19 -04002744 btrfs_item_key(right, &disk_key, 0);
Chris Masondb945352007-10-15 16:15:53 -04002745 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2746 path->slots[1] + 1, 1);
Chris Masonaa5d6be2007-02-28 16:35:06 -05002747 if (wret)
2748 ret = wret;
Chris Mason5f39d392007-10-15 16:14:19 -04002749
2750 btrfs_mark_buffer_dirty(right);
2751 btrfs_mark_buffer_dirty(l);
Chris Masoneb60cea2007-02-02 09:18:22 -05002752 BUG_ON(path->slots[0] != slot);
Chris Mason5f39d392007-10-15 16:14:19 -04002753
Chris Masonbe0e5c02007-01-26 15:51:26 -05002754 if (mid <= slot) {
Chris Mason925baed2008-06-25 16:01:30 -04002755 btrfs_tree_unlock(path->nodes[0]);
Chris Mason5f39d392007-10-15 16:14:19 -04002756 free_extent_buffer(path->nodes[0]);
2757 path->nodes[0] = right;
Chris Masonbe0e5c02007-01-26 15:51:26 -05002758 path->slots[0] -= mid;
2759 path->slots[1] += 1;
Chris Mason925baed2008-06-25 16:01:30 -04002760 } else {
2761 btrfs_tree_unlock(right);
Chris Mason5f39d392007-10-15 16:14:19 -04002762 free_extent_buffer(right);
Chris Mason925baed2008-06-25 16:01:30 -04002763 }
Chris Mason5f39d392007-10-15 16:14:19 -04002764
Chris Masoneb60cea2007-02-02 09:18:22 -05002765 BUG_ON(path->slots[0] < 0);
Chris Masond4dbff92007-04-04 14:08:15 -04002766
Chris Mason44871b12009-03-13 10:04:31 -04002767 return ret;
2768}
2769
2770/*
Chris Mason99d8f832010-07-07 10:51:48 -04002771 * double splits happen when we need to insert a big item in the middle
2772 * of a leaf. A double split can leave us with 3 mostly empty leaves:
2773 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
2774 * A B C
2775 *
2776 * We avoid this by trying to push the items on either side of our target
2777 * into the adjacent leaves. If all goes well we can avoid the double split
2778 * completely.
2779 */
2780static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
2781 struct btrfs_root *root,
2782 struct btrfs_path *path,
2783 int data_size)
2784{
2785 int ret;
2786 int progress = 0;
2787 int slot;
2788 u32 nritems;
2789
2790 slot = path->slots[0];
2791
2792 /*
2793 * try to push all the items after our slot into the
2794 * right leaf
2795 */
2796 ret = push_leaf_right(trans, root, path, 1, data_size, 0, slot);
2797 if (ret < 0)
2798 return ret;
2799
2800 if (ret == 0)
2801 progress++;
2802
2803 nritems = btrfs_header_nritems(path->nodes[0]);
2804 /*
2805 * our goal is to get our slot at the start or end of a leaf. If
2806 * we've done so we're done
2807 */
2808 if (path->slots[0] == 0 || path->slots[0] == nritems)
2809 return 0;
2810
2811 if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
2812 return 0;
2813
2814 /* try to push all the items before our slot into the next leaf */
2815 slot = path->slots[0];
2816 ret = push_leaf_left(trans, root, path, 1, data_size, 0, slot);
2817 if (ret < 0)
2818 return ret;
2819
2820 if (ret == 0)
2821 progress++;
2822
2823 if (progress)
2824 return 0;
2825 return 1;
2826}
2827
2828/*
Chris Mason44871b12009-03-13 10:04:31 -04002829 * split the path's leaf in two, making sure there is at least data_size
2830 * available for the resulting leaf level of the path.
2831 *
2832 * returns 0 if all went well and < 0 on failure.
2833 */
2834static noinline int split_leaf(struct btrfs_trans_handle *trans,
2835 struct btrfs_root *root,
2836 struct btrfs_key *ins_key,
2837 struct btrfs_path *path, int data_size,
2838 int extend)
2839{
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002840 struct btrfs_disk_key disk_key;
Chris Mason44871b12009-03-13 10:04:31 -04002841 struct extent_buffer *l;
2842 u32 nritems;
2843 int mid;
2844 int slot;
2845 struct extent_buffer *right;
2846 int ret = 0;
2847 int wret;
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002848 int split;
Chris Mason44871b12009-03-13 10:04:31 -04002849 int num_doubles = 0;
Chris Mason99d8f832010-07-07 10:51:48 -04002850 int tried_avoid_double = 0;
Chris Mason44871b12009-03-13 10:04:31 -04002851
Yan, Zhenga5719522009-09-24 09:17:31 -04002852 l = path->nodes[0];
2853 slot = path->slots[0];
2854 if (extend && data_size + btrfs_item_size_nr(l, slot) +
2855 sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root))
2856 return -EOVERFLOW;
2857
Chris Mason44871b12009-03-13 10:04:31 -04002858 /* first try to make some room by pushing left and right */
Chris Mason99d8f832010-07-07 10:51:48 -04002859 if (data_size) {
2860 wret = push_leaf_right(trans, root, path, data_size,
2861 data_size, 0, 0);
Chris Mason44871b12009-03-13 10:04:31 -04002862 if (wret < 0)
2863 return wret;
2864 if (wret) {
Chris Mason99d8f832010-07-07 10:51:48 -04002865 wret = push_leaf_left(trans, root, path, data_size,
2866 data_size, 0, (u32)-1);
Chris Mason44871b12009-03-13 10:04:31 -04002867 if (wret < 0)
2868 return wret;
2869 }
2870 l = path->nodes[0];
2871
2872 /* did the pushes work? */
2873 if (btrfs_leaf_free_space(root, l) >= data_size)
2874 return 0;
2875 }
2876
2877 if (!path->nodes[1]) {
2878 ret = insert_new_root(trans, root, path, 1);
2879 if (ret)
2880 return ret;
2881 }
2882again:
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002883 split = 1;
Chris Mason44871b12009-03-13 10:04:31 -04002884 l = path->nodes[0];
2885 slot = path->slots[0];
2886 nritems = btrfs_header_nritems(l);
2887 mid = (nritems + 1) / 2;
2888
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002889 if (mid <= slot) {
2890 if (nritems == 1 ||
2891 leaf_space_used(l, mid, nritems - mid) + data_size >
2892 BTRFS_LEAF_DATA_SIZE(root)) {
2893 if (slot >= nritems) {
2894 split = 0;
2895 } else {
2896 mid = slot;
2897 if (mid != nritems &&
2898 leaf_space_used(l, mid, nritems - mid) +
2899 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
Chris Mason99d8f832010-07-07 10:51:48 -04002900 if (data_size && !tried_avoid_double)
2901 goto push_for_double;
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002902 split = 2;
2903 }
2904 }
2905 }
2906 } else {
2907 if (leaf_space_used(l, 0, mid) + data_size >
2908 BTRFS_LEAF_DATA_SIZE(root)) {
2909 if (!extend && data_size && slot == 0) {
2910 split = 0;
2911 } else if ((extend || !data_size) && slot == 0) {
2912 mid = 1;
2913 } else {
2914 mid = slot;
2915 if (mid != nritems &&
2916 leaf_space_used(l, mid, nritems - mid) +
2917 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
Chris Mason99d8f832010-07-07 10:51:48 -04002918 if (data_size && !tried_avoid_double)
2919 goto push_for_double;
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002920 split = 2 ;
2921 }
2922 }
2923 }
2924 }
2925
2926 if (split == 0)
2927 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2928 else
2929 btrfs_item_key(l, &disk_key, mid);
2930
2931 right = btrfs_alloc_free_block(trans, root, root->leafsize, 0,
Chris Mason44871b12009-03-13 10:04:31 -04002932 root->root_key.objectid,
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002933 &disk_key, 0, l->start, 0);
Yan, Zhengf0486c62010-05-16 10:46:25 -04002934 if (IS_ERR(right))
Chris Mason44871b12009-03-13 10:04:31 -04002935 return PTR_ERR(right);
Yan, Zhengf0486c62010-05-16 10:46:25 -04002936
2937 root_add_used(root, root->leafsize);
Chris Mason44871b12009-03-13 10:04:31 -04002938
2939 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2940 btrfs_set_header_bytenr(right, right->start);
2941 btrfs_set_header_generation(right, trans->transid);
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002942 btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
Chris Mason44871b12009-03-13 10:04:31 -04002943 btrfs_set_header_owner(right, root->root_key.objectid);
2944 btrfs_set_header_level(right, 0);
2945 write_extent_buffer(right, root->fs_info->fsid,
2946 (unsigned long)btrfs_header_fsid(right),
2947 BTRFS_FSID_SIZE);
2948
2949 write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2950 (unsigned long)btrfs_header_chunk_tree_uuid(right),
2951 BTRFS_UUID_SIZE);
2952
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002953 if (split == 0) {
2954 if (mid <= slot) {
2955 btrfs_set_header_nritems(right, 0);
2956 wret = insert_ptr(trans, root, path,
2957 &disk_key, right->start,
2958 path->slots[1] + 1, 1);
2959 if (wret)
2960 ret = wret;
Chris Mason44871b12009-03-13 10:04:31 -04002961
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002962 btrfs_tree_unlock(path->nodes[0]);
2963 free_extent_buffer(path->nodes[0]);
2964 path->nodes[0] = right;
2965 path->slots[0] = 0;
2966 path->slots[1] += 1;
2967 } else {
2968 btrfs_set_header_nritems(right, 0);
2969 wret = insert_ptr(trans, root, path,
2970 &disk_key,
2971 right->start,
2972 path->slots[1], 1);
2973 if (wret)
2974 ret = wret;
2975 btrfs_tree_unlock(path->nodes[0]);
2976 free_extent_buffer(path->nodes[0]);
2977 path->nodes[0] = right;
2978 path->slots[0] = 0;
2979 if (path->slots[1] == 0) {
2980 wret = fixup_low_keys(trans, root,
2981 path, &disk_key, 1);
Chris Mason44871b12009-03-13 10:04:31 -04002982 if (wret)
2983 ret = wret;
Chris Mason44871b12009-03-13 10:04:31 -04002984 }
2985 }
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002986 btrfs_mark_buffer_dirty(right);
2987 return ret;
Chris Mason44871b12009-03-13 10:04:31 -04002988 }
2989
2990 ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
2991 BUG_ON(ret);
2992
Yan Zheng5d4f98a2009-06-10 10:45:14 -04002993 if (split == 2) {
Chris Masoncc0c5532007-10-25 15:42:57 -04002994 BUG_ON(num_doubles != 0);
2995 num_doubles++;
2996 goto again;
Chris Mason3326d1b2007-10-15 16:18:25 -04002997 }
Chris Mason44871b12009-03-13 10:04:31 -04002998
Chris Masonbe0e5c02007-01-26 15:51:26 -05002999 return ret;
Chris Mason99d8f832010-07-07 10:51:48 -04003000
3001push_for_double:
3002 push_for_double_split(trans, root, path, data_size);
3003 tried_avoid_double = 1;
3004 if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
3005 return 0;
3006 goto again;
Chris Masonbe0e5c02007-01-26 15:51:26 -05003007}
3008
Yan, Zhengad48fd752009-11-12 09:33:58 +00003009static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
3010 struct btrfs_root *root,
3011 struct btrfs_path *path, int ins_len)
Chris Mason459931e2008-12-10 09:10:46 -05003012{
Yan, Zhengad48fd752009-11-12 09:33:58 +00003013 struct btrfs_key key;
Chris Mason459931e2008-12-10 09:10:46 -05003014 struct extent_buffer *leaf;
Yan, Zhengad48fd752009-11-12 09:33:58 +00003015 struct btrfs_file_extent_item *fi;
3016 u64 extent_len = 0;
3017 u32 item_size;
3018 int ret;
Chris Mason459931e2008-12-10 09:10:46 -05003019
3020 leaf = path->nodes[0];
Yan, Zhengad48fd752009-11-12 09:33:58 +00003021 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3022
3023 BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
3024 key.type != BTRFS_EXTENT_CSUM_KEY);
3025
3026 if (btrfs_leaf_free_space(root, leaf) >= ins_len)
3027 return 0;
Chris Mason459931e2008-12-10 09:10:46 -05003028
3029 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
Yan, Zhengad48fd752009-11-12 09:33:58 +00003030 if (key.type == BTRFS_EXTENT_DATA_KEY) {
3031 fi = btrfs_item_ptr(leaf, path->slots[0],
3032 struct btrfs_file_extent_item);
3033 extent_len = btrfs_file_extent_num_bytes(leaf, fi);
3034 }
Chris Mason459931e2008-12-10 09:10:46 -05003035 btrfs_release_path(root, path);
3036
Chris Mason459931e2008-12-10 09:10:46 -05003037 path->keep_locks = 1;
Yan, Zhengad48fd752009-11-12 09:33:58 +00003038 path->search_for_split = 1;
3039 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
Chris Mason459931e2008-12-10 09:10:46 -05003040 path->search_for_split = 0;
Yan, Zhengad48fd752009-11-12 09:33:58 +00003041 if (ret < 0)
3042 goto err;
Chris Mason459931e2008-12-10 09:10:46 -05003043
Yan, Zhengad48fd752009-11-12 09:33:58 +00003044 ret = -EAGAIN;
3045 leaf = path->nodes[0];
Chris Mason459931e2008-12-10 09:10:46 -05003046 /* if our item isn't there or got smaller, return now */
Yan, Zhengad48fd752009-11-12 09:33:58 +00003047 if (ret > 0 || item_size != btrfs_item_size_nr(leaf, path->slots[0]))
3048 goto err;
3049
Chris Mason109f6ae2010-04-02 09:20:18 -04003050 /* the leaf has changed, it now has room. return now */
3051 if (btrfs_leaf_free_space(root, path->nodes[0]) >= ins_len)
3052 goto err;
3053
Yan, Zhengad48fd752009-11-12 09:33:58 +00003054 if (key.type == BTRFS_EXTENT_DATA_KEY) {
3055 fi = btrfs_item_ptr(leaf, path->slots[0],
3056 struct btrfs_file_extent_item);
3057 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
3058 goto err;
Chris Mason459931e2008-12-10 09:10:46 -05003059 }
3060
Chris Masonb9473432009-03-13 11:00:37 -04003061 btrfs_set_path_blocking(path);
Yan, Zhengad48fd752009-11-12 09:33:58 +00003062 ret = split_leaf(trans, root, &key, path, ins_len, 1);
Yan, Zhengf0486c62010-05-16 10:46:25 -04003063 if (ret)
3064 goto err;
Chris Mason459931e2008-12-10 09:10:46 -05003065
Yan, Zhengad48fd752009-11-12 09:33:58 +00003066 path->keep_locks = 0;
Chris Masonb9473432009-03-13 11:00:37 -04003067 btrfs_unlock_up_safe(path, 1);
Yan, Zhengad48fd752009-11-12 09:33:58 +00003068 return 0;
3069err:
3070 path->keep_locks = 0;
3071 return ret;
3072}
3073
3074static noinline int split_item(struct btrfs_trans_handle *trans,
3075 struct btrfs_root *root,
3076 struct btrfs_path *path,
3077 struct btrfs_key *new_key,
3078 unsigned long split_offset)
3079{
3080 struct extent_buffer *leaf;
3081 struct btrfs_item *item;
3082 struct btrfs_item *new_item;
3083 int slot;
3084 char *buf;
3085 u32 nritems;
3086 u32 item_size;
3087 u32 orig_offset;
3088 struct btrfs_disk_key disk_key;
3089
Chris Masonb9473432009-03-13 11:00:37 -04003090 leaf = path->nodes[0];
3091 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
3092
Chris Masonb4ce94d2009-02-04 09:25:08 -05003093 btrfs_set_path_blocking(path);
3094
Chris Mason459931e2008-12-10 09:10:46 -05003095 item = btrfs_item_nr(leaf, path->slots[0]);
3096 orig_offset = btrfs_item_offset(leaf, item);
3097 item_size = btrfs_item_size(leaf, item);
3098
Chris Mason459931e2008-12-10 09:10:46 -05003099 buf = kmalloc(item_size, GFP_NOFS);
Yan, Zhengad48fd752009-11-12 09:33:58 +00003100 if (!buf)
3101 return -ENOMEM;
3102
Chris Mason459931e2008-12-10 09:10:46 -05003103 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3104 path->slots[0]), item_size);
Yan, Zhengad48fd752009-11-12 09:33:58 +00003105
Chris Mason459931e2008-12-10 09:10:46 -05003106 slot = path->slots[0] + 1;
Chris Mason459931e2008-12-10 09:10:46 -05003107 nritems = btrfs_header_nritems(leaf);
Chris Mason459931e2008-12-10 09:10:46 -05003108 if (slot != nritems) {
3109 /* shift the items */
3110 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
Yan, Zhengad48fd752009-11-12 09:33:58 +00003111 btrfs_item_nr_offset(slot),
3112 (nritems - slot) * sizeof(struct btrfs_item));
Chris Mason459931e2008-12-10 09:10:46 -05003113 }
3114
3115 btrfs_cpu_key_to_disk(&disk_key, new_key);
3116 btrfs_set_item_key(leaf, &disk_key, slot);
3117
3118 new_item = btrfs_item_nr(leaf, slot);
3119
3120 btrfs_set_item_offset(leaf, new_item, orig_offset);
3121 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
3122
3123 btrfs_set_item_offset(leaf, item,
3124 orig_offset + item_size - split_offset);
3125 btrfs_set_item_size(leaf, item, split_offset);
3126
3127 btrfs_set_header_nritems(leaf, nritems + 1);
3128
3129 /* write the data for the start of the original item */
3130 write_extent_buffer(leaf, buf,
3131 btrfs_item_ptr_offset(leaf, path->slots[0]),
3132 split_offset);
3133
3134 /* write the data for the new item */
3135 write_extent_buffer(leaf, buf + split_offset,
3136 btrfs_item_ptr_offset(leaf, slot),
3137 item_size - split_offset);
3138 btrfs_mark_buffer_dirty(leaf);
3139
Yan, Zhengad48fd752009-11-12 09:33:58 +00003140 BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
Chris Mason459931e2008-12-10 09:10:46 -05003141 kfree(buf);
Yan, Zhengad48fd752009-11-12 09:33:58 +00003142 return 0;
3143}
3144
3145/*
3146 * This function splits a single item into two items,
3147 * giving 'new_key' to the new item and splitting the
3148 * old one at split_offset (from the start of the item).
3149 *
3150 * The path may be released by this operation. After
3151 * the split, the path is pointing to the old item. The
3152 * new item is going to be in the same node as the old one.
3153 *
3154 * Note, the item being split must be smaller enough to live alone on
3155 * a tree block with room for one extra struct btrfs_item
3156 *
3157 * This allows us to split the item in place, keeping a lock on the
3158 * leaf the entire time.
3159 */
3160int btrfs_split_item(struct btrfs_trans_handle *trans,
3161 struct btrfs_root *root,
3162 struct btrfs_path *path,
3163 struct btrfs_key *new_key,
3164 unsigned long split_offset)
3165{
3166 int ret;
3167 ret = setup_leaf_for_split(trans, root, path,
3168 sizeof(struct btrfs_item));
3169 if (ret)
3170 return ret;
3171
3172 ret = split_item(trans, root, path, new_key, split_offset);
Chris Mason459931e2008-12-10 09:10:46 -05003173 return ret;
3174}
3175
3176/*
Yan, Zhengad48fd752009-11-12 09:33:58 +00003177 * This function duplicate a item, giving 'new_key' to the new item.
3178 * It guarantees both items live in the same tree leaf and the new item
3179 * is contiguous with the original item.
3180 *
3181 * This allows us to split file extent in place, keeping a lock on the
3182 * leaf the entire time.
3183 */
3184int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
3185 struct btrfs_root *root,
3186 struct btrfs_path *path,
3187 struct btrfs_key *new_key)
3188{
3189 struct extent_buffer *leaf;
3190 int ret;
3191 u32 item_size;
3192
3193 leaf = path->nodes[0];
3194 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3195 ret = setup_leaf_for_split(trans, root, path,
3196 item_size + sizeof(struct btrfs_item));
3197 if (ret)
3198 return ret;
3199
3200 path->slots[0]++;
3201 ret = setup_items_for_insert(trans, root, path, new_key, &item_size,
3202 item_size, item_size +
3203 sizeof(struct btrfs_item), 1);
3204 BUG_ON(ret);
3205
3206 leaf = path->nodes[0];
3207 memcpy_extent_buffer(leaf,
3208 btrfs_item_ptr_offset(leaf, path->slots[0]),
3209 btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
3210 item_size);
3211 return 0;
3212}
3213
3214/*
Chris Masond352ac62008-09-29 15:18:18 -04003215 * make the item pointed to by the path smaller. new_size indicates
3216 * how small to make it, and from_end tells us if we just chop bytes
3217 * off the end of the item or if we shift the item to chop bytes off
3218 * the front.
3219 */
Chris Masonb18c6682007-04-17 13:26:50 -04003220int btrfs_truncate_item(struct btrfs_trans_handle *trans,
3221 struct btrfs_root *root,
3222 struct btrfs_path *path,
Chris Mason179e29e2007-11-01 11:28:41 -04003223 u32 new_size, int from_end)
Chris Masonb18c6682007-04-17 13:26:50 -04003224{
3225 int ret = 0;
3226 int slot;
Chris Mason5f39d392007-10-15 16:14:19 -04003227 struct extent_buffer *leaf;
3228 struct btrfs_item *item;
Chris Masonb18c6682007-04-17 13:26:50 -04003229 u32 nritems;
3230 unsigned int data_end;
3231 unsigned int old_data_start;
3232 unsigned int old_size;
3233 unsigned int size_diff;
3234 int i;
3235
Chris Mason5f39d392007-10-15 16:14:19 -04003236 leaf = path->nodes[0];
Chris Mason179e29e2007-11-01 11:28:41 -04003237 slot = path->slots[0];
3238
3239 old_size = btrfs_item_size_nr(leaf, slot);
3240 if (old_size == new_size)
3241 return 0;
Chris Masonb18c6682007-04-17 13:26:50 -04003242
Chris Mason5f39d392007-10-15 16:14:19 -04003243 nritems = btrfs_header_nritems(leaf);
Chris Masonb18c6682007-04-17 13:26:50 -04003244 data_end = leaf_data_end(root, leaf);
3245
Chris Mason5f39d392007-10-15 16:14:19 -04003246 old_data_start = btrfs_item_offset_nr(leaf, slot);
Chris Mason179e29e2007-11-01 11:28:41 -04003247
Chris Masonb18c6682007-04-17 13:26:50 -04003248 size_diff = old_size - new_size;
3249
3250 BUG_ON(slot < 0);
3251 BUG_ON(slot >= nritems);
3252
3253 /*
3254 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3255 */
3256 /* first correct the data pointers */
3257 for (i = slot; i < nritems; i++) {
Chris Mason5f39d392007-10-15 16:14:19 -04003258 u32 ioff;
3259 item = btrfs_item_nr(leaf, i);
Chris Masondb945352007-10-15 16:15:53 -04003260
3261 if (!leaf->map_token) {
3262 map_extent_buffer(leaf, (unsigned long)item,
3263 sizeof(struct btrfs_item),
3264 &leaf->map_token, &leaf->kaddr,
3265 &leaf->map_start, &leaf->map_len,
3266 KM_USER1);
3267 }
3268
Chris Mason5f39d392007-10-15 16:14:19 -04003269 ioff = btrfs_item_offset(leaf, item);
3270 btrfs_set_item_offset(leaf, item, ioff + size_diff);
Chris Masonb18c6682007-04-17 13:26:50 -04003271 }
Chris Masondb945352007-10-15 16:15:53 -04003272
3273 if (leaf->map_token) {
3274 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3275 leaf->map_token = NULL;
3276 }
3277
Chris Masonb18c6682007-04-17 13:26:50 -04003278 /* shift the data */
Chris Mason179e29e2007-11-01 11:28:41 -04003279 if (from_end) {
3280 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3281 data_end + size_diff, btrfs_leaf_data(leaf) +
3282 data_end, old_data_start + new_size - data_end);
3283 } else {
3284 struct btrfs_disk_key disk_key;
3285 u64 offset;
3286
3287 btrfs_item_key(leaf, &disk_key, slot);
3288
3289 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
3290 unsigned long ptr;
3291 struct btrfs_file_extent_item *fi;
3292
3293 fi = btrfs_item_ptr(leaf, slot,
3294 struct btrfs_file_extent_item);
3295 fi = (struct btrfs_file_extent_item *)(
3296 (unsigned long)fi - size_diff);
3297
3298 if (btrfs_file_extent_type(leaf, fi) ==
3299 BTRFS_FILE_EXTENT_INLINE) {
3300 ptr = btrfs_item_ptr_offset(leaf, slot);
3301 memmove_extent_buffer(leaf, ptr,
Chris Masond3977122009-01-05 21:25:51 -05003302 (unsigned long)fi,
3303 offsetof(struct btrfs_file_extent_item,
Chris Mason179e29e2007-11-01 11:28:41 -04003304 disk_bytenr));
3305 }
3306 }
3307
3308 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3309 data_end + size_diff, btrfs_leaf_data(leaf) +
3310 data_end, old_data_start - data_end);
3311
3312 offset = btrfs_disk_key_offset(&disk_key);
3313 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
3314 btrfs_set_item_key(leaf, &disk_key, slot);
3315 if (slot == 0)
3316 fixup_low_keys(trans, root, path, &disk_key, 1);
3317 }
Chris Mason5f39d392007-10-15 16:14:19 -04003318
3319 item = btrfs_item_nr(leaf, slot);
3320 btrfs_set_item_size(leaf, item, new_size);
3321 btrfs_mark_buffer_dirty(leaf);
Chris Masonb18c6682007-04-17 13:26:50 -04003322
3323 ret = 0;
Chris Mason5f39d392007-10-15 16:14:19 -04003324 if (btrfs_leaf_free_space(root, leaf) < 0) {
3325 btrfs_print_leaf(root, leaf);
Chris Masonb18c6682007-04-17 13:26:50 -04003326 BUG();
Chris Mason5f39d392007-10-15 16:14:19 -04003327 }
Chris Masonb18c6682007-04-17 13:26:50 -04003328 return ret;
3329}
3330
Chris Masond352ac62008-09-29 15:18:18 -04003331/*
3332 * make the item pointed to by the path bigger, data_size is the new size.
3333 */
Chris Mason5f39d392007-10-15 16:14:19 -04003334int btrfs_extend_item(struct btrfs_trans_handle *trans,
3335 struct btrfs_root *root, struct btrfs_path *path,
3336 u32 data_size)
Chris Mason6567e832007-04-16 09:22:45 -04003337{
3338 int ret = 0;
3339 int slot;
Chris Mason5f39d392007-10-15 16:14:19 -04003340 struct extent_buffer *leaf;
3341 struct btrfs_item *item;
Chris Mason6567e832007-04-16 09:22:45 -04003342 u32 nritems;
3343 unsigned int data_end;
3344 unsigned int old_data;
3345 unsigned int old_size;
3346 int i;
3347
Chris Mason5f39d392007-10-15 16:14:19 -04003348 leaf = path->nodes[0];
Chris Mason6567e832007-04-16 09:22:45 -04003349
Chris Mason5f39d392007-10-15 16:14:19 -04003350 nritems = btrfs_header_nritems(leaf);
Chris Mason6567e832007-04-16 09:22:45 -04003351 data_end = leaf_data_end(root, leaf);
3352
Chris Mason5f39d392007-10-15 16:14:19 -04003353 if (btrfs_leaf_free_space(root, leaf) < data_size) {
3354 btrfs_print_leaf(root, leaf);
Chris Mason6567e832007-04-16 09:22:45 -04003355 BUG();
Chris Mason5f39d392007-10-15 16:14:19 -04003356 }
Chris Mason6567e832007-04-16 09:22:45 -04003357 slot = path->slots[0];
Chris Mason5f39d392007-10-15 16:14:19 -04003358 old_data = btrfs_item_end_nr(leaf, slot);
Chris Mason6567e832007-04-16 09:22:45 -04003359
3360 BUG_ON(slot < 0);
Chris Mason3326d1b2007-10-15 16:18:25 -04003361 if (slot >= nritems) {
3362 btrfs_print_leaf(root, leaf);
Chris Masond3977122009-01-05 21:25:51 -05003363 printk(KERN_CRIT "slot %d too large, nritems %d\n",
3364 slot, nritems);
Chris Mason3326d1b2007-10-15 16:18:25 -04003365 BUG_ON(1);
3366 }
Chris Mason6567e832007-04-16 09:22:45 -04003367
3368 /*
3369 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3370 */
3371 /* first correct the data pointers */
3372 for (i = slot; i < nritems; i++) {
Chris Mason5f39d392007-10-15 16:14:19 -04003373 u32 ioff;
3374 item = btrfs_item_nr(leaf, i);
Chris Masondb945352007-10-15 16:15:53 -04003375
3376 if (!leaf->map_token) {
3377 map_extent_buffer(leaf, (unsigned long)item,
3378 sizeof(struct btrfs_item),
3379 &leaf->map_token, &leaf->kaddr,
3380 &leaf->map_start, &leaf->map_len,
3381 KM_USER1);
3382 }
Chris Mason5f39d392007-10-15 16:14:19 -04003383 ioff = btrfs_item_offset(leaf, item);
3384 btrfs_set_item_offset(leaf, item, ioff - data_size);
Chris Mason6567e832007-04-16 09:22:45 -04003385 }
Chris Mason5f39d392007-10-15 16:14:19 -04003386
Chris Masondb945352007-10-15 16:15:53 -04003387 if (leaf->map_token) {
3388 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3389 leaf->map_token = NULL;
3390 }
3391
Chris Mason6567e832007-04-16 09:22:45 -04003392 /* shift the data */
Chris Mason5f39d392007-10-15 16:14:19 -04003393 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
Chris Mason6567e832007-04-16 09:22:45 -04003394 data_end - data_size, btrfs_leaf_data(leaf) +
3395 data_end, old_data - data_end);
Chris Mason5f39d392007-10-15 16:14:19 -04003396
Chris Mason6567e832007-04-16 09:22:45 -04003397 data_end = old_data;
Chris Mason5f39d392007-10-15 16:14:19 -04003398 old_size = btrfs_item_size_nr(leaf, slot);
3399 item = btrfs_item_nr(leaf, slot);
3400 btrfs_set_item_size(leaf, item, old_size + data_size);
3401 btrfs_mark_buffer_dirty(leaf);
Chris Mason6567e832007-04-16 09:22:45 -04003402
3403 ret = 0;
Chris Mason5f39d392007-10-15 16:14:19 -04003404 if (btrfs_leaf_free_space(root, leaf) < 0) {
3405 btrfs_print_leaf(root, leaf);
Chris Mason6567e832007-04-16 09:22:45 -04003406 BUG();
Chris Mason5f39d392007-10-15 16:14:19 -04003407 }
Chris Mason6567e832007-04-16 09:22:45 -04003408 return ret;
3409}
3410
Chris Mason74123bd2007-02-02 11:05:29 -05003411/*
Chris Masond352ac62008-09-29 15:18:18 -04003412 * Given a key and some data, insert items into the tree.
Chris Mason74123bd2007-02-02 11:05:29 -05003413 * This does all the path init required, making room in the tree if needed.
Josef Bacikf3465ca2008-11-12 14:19:50 -05003414 * Returns the number of keys that were inserted.
3415 */
3416int btrfs_insert_some_items(struct btrfs_trans_handle *trans,
3417 struct btrfs_root *root,
3418 struct btrfs_path *path,
3419 struct btrfs_key *cpu_key, u32 *data_size,
3420 int nr)
3421{
3422 struct extent_buffer *leaf;
3423 struct btrfs_item *item;
3424 int ret = 0;
3425 int slot;
Josef Bacikf3465ca2008-11-12 14:19:50 -05003426 int i;
3427 u32 nritems;
3428 u32 total_data = 0;
3429 u32 total_size = 0;
3430 unsigned int data_end;
3431 struct btrfs_disk_key disk_key;
3432 struct btrfs_key found_key;
3433
Yan Zheng87b29b22008-12-17 10:21:48 -05003434 for (i = 0; i < nr; i++) {
3435 if (total_size + data_size[i] + sizeof(struct btrfs_item) >
3436 BTRFS_LEAF_DATA_SIZE(root)) {
3437 break;
3438 nr = i;
3439 }
Josef Bacikf3465ca2008-11-12 14:19:50 -05003440 total_data += data_size[i];
Yan Zheng87b29b22008-12-17 10:21:48 -05003441 total_size += data_size[i] + sizeof(struct btrfs_item);
3442 }
3443 BUG_ON(nr == 0);
Josef Bacikf3465ca2008-11-12 14:19:50 -05003444
Josef Bacikf3465ca2008-11-12 14:19:50 -05003445 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3446 if (ret == 0)
3447 return -EEXIST;
3448 if (ret < 0)
3449 goto out;
3450
Josef Bacikf3465ca2008-11-12 14:19:50 -05003451 leaf = path->nodes[0];
3452
3453 nritems = btrfs_header_nritems(leaf);
3454 data_end = leaf_data_end(root, leaf);
3455
3456 if (btrfs_leaf_free_space(root, leaf) < total_size) {
3457 for (i = nr; i >= 0; i--) {
3458 total_data -= data_size[i];
3459 total_size -= data_size[i] + sizeof(struct btrfs_item);
3460 if (total_size < btrfs_leaf_free_space(root, leaf))
3461 break;
3462 }
3463 nr = i;
3464 }
3465
3466 slot = path->slots[0];
3467 BUG_ON(slot < 0);
3468
3469 if (slot != nritems) {
3470 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3471
3472 item = btrfs_item_nr(leaf, slot);
3473 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3474
3475 /* figure out how many keys we can insert in here */
3476 total_data = data_size[0];
3477 for (i = 1; i < nr; i++) {
Yan Zheng5d4f98a2009-06-10 10:45:14 -04003478 if (btrfs_comp_cpu_keys(&found_key, cpu_key + i) <= 0)
Josef Bacikf3465ca2008-11-12 14:19:50 -05003479 break;
3480 total_data += data_size[i];
3481 }
3482 nr = i;
3483
3484 if (old_data < data_end) {
3485 btrfs_print_leaf(root, leaf);
Chris Masond3977122009-01-05 21:25:51 -05003486 printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
Josef Bacikf3465ca2008-11-12 14:19:50 -05003487 slot, old_data, data_end);
3488 BUG_ON(1);
3489 }
3490 /*
3491 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3492 */
3493 /* first correct the data pointers */
3494 WARN_ON(leaf->map_token);
3495 for (i = slot; i < nritems; i++) {
3496 u32 ioff;
3497
3498 item = btrfs_item_nr(leaf, i);
3499 if (!leaf->map_token) {
3500 map_extent_buffer(leaf, (unsigned long)item,
3501 sizeof(struct btrfs_item),
3502 &leaf->map_token, &leaf->kaddr,
3503 &leaf->map_start, &leaf->map_len,
3504 KM_USER1);
3505 }
3506
3507 ioff = btrfs_item_offset(leaf, item);
3508 btrfs_set_item_offset(leaf, item, ioff - total_data);
3509 }
3510 if (leaf->map_token) {
3511 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3512 leaf->map_token = NULL;
3513 }
3514
3515 /* shift the items */
3516 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3517 btrfs_item_nr_offset(slot),
3518 (nritems - slot) * sizeof(struct btrfs_item));
3519
3520 /* shift the data */
3521 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3522 data_end - total_data, btrfs_leaf_data(leaf) +
3523 data_end, old_data - data_end);
3524 data_end = old_data;
3525 } else {
3526 /*
3527 * this sucks but it has to be done, if we are inserting at
3528 * the end of the leaf only insert 1 of the items, since we
3529 * have no way of knowing whats on the next leaf and we'd have
3530 * to drop our current locks to figure it out
3531 */
3532 nr = 1;
3533 }
3534
3535 /* setup the item for the new data */
3536 for (i = 0; i < nr; i++) {
3537 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3538 btrfs_set_item_key(leaf, &disk_key, slot + i);
3539 item = btrfs_item_nr(leaf, slot + i);
3540 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3541 data_end -= data_size[i];
3542 btrfs_set_item_size(leaf, item, data_size[i]);
3543 }
3544 btrfs_set_header_nritems(leaf, nritems + nr);
3545 btrfs_mark_buffer_dirty(leaf);
3546
3547 ret = 0;
3548 if (slot == 0) {
3549 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3550 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3551 }
3552
3553 if (btrfs_leaf_free_space(root, leaf) < 0) {
3554 btrfs_print_leaf(root, leaf);
3555 BUG();
3556 }
3557out:
3558 if (!ret)
3559 ret = nr;
3560 return ret;
3561}
3562
3563/*
Chris Mason44871b12009-03-13 10:04:31 -04003564 * this is a helper for btrfs_insert_empty_items, the main goal here is
3565 * to save stack depth by doing the bulk of the work in a function
3566 * that doesn't call btrfs_search_slot
Chris Mason74123bd2007-02-02 11:05:29 -05003567 */
Chris Mason44871b12009-03-13 10:04:31 -04003568static noinline_for_stack int
3569setup_items_for_insert(struct btrfs_trans_handle *trans,
3570 struct btrfs_root *root, struct btrfs_path *path,
3571 struct btrfs_key *cpu_key, u32 *data_size,
3572 u32 total_data, u32 total_size, int nr)
Chris Masonbe0e5c02007-01-26 15:51:26 -05003573{
Chris Mason5f39d392007-10-15 16:14:19 -04003574 struct btrfs_item *item;
Chris Mason9c583092008-01-29 15:15:18 -05003575 int i;
Chris Mason7518a232007-03-12 12:01:18 -04003576 u32 nritems;
Chris Masonbe0e5c02007-01-26 15:51:26 -05003577 unsigned int data_end;
Chris Masone2fa7222007-03-12 16:22:34 -04003578 struct btrfs_disk_key disk_key;
Chris Mason44871b12009-03-13 10:04:31 -04003579 int ret;
3580 struct extent_buffer *leaf;
3581 int slot;
Chris Masone2fa7222007-03-12 16:22:34 -04003582
Chris Mason5f39d392007-10-15 16:14:19 -04003583 leaf = path->nodes[0];
Chris Mason44871b12009-03-13 10:04:31 -04003584 slot = path->slots[0];
Chris Mason74123bd2007-02-02 11:05:29 -05003585
Chris Mason5f39d392007-10-15 16:14:19 -04003586 nritems = btrfs_header_nritems(leaf);
Chris Mason123abc82007-03-14 14:14:43 -04003587 data_end = leaf_data_end(root, leaf);
Chris Masoneb60cea2007-02-02 09:18:22 -05003588
Chris Masonf25956c2008-09-12 15:32:53 -04003589 if (btrfs_leaf_free_space(root, leaf) < total_size) {
Chris Mason3326d1b2007-10-15 16:18:25 -04003590 btrfs_print_leaf(root, leaf);
Chris Masond3977122009-01-05 21:25:51 -05003591 printk(KERN_CRIT "not enough freespace need %u have %d\n",
Chris Mason9c583092008-01-29 15:15:18 -05003592 total_size, btrfs_leaf_free_space(root, leaf));
Chris Masonbe0e5c02007-01-26 15:51:26 -05003593 BUG();
Chris Masond4dbff92007-04-04 14:08:15 -04003594 }
Chris Mason5f39d392007-10-15 16:14:19 -04003595
Chris Masonbe0e5c02007-01-26 15:51:26 -05003596 if (slot != nritems) {
Chris Mason5f39d392007-10-15 16:14:19 -04003597 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
Chris Masonbe0e5c02007-01-26 15:51:26 -05003598
Chris Mason5f39d392007-10-15 16:14:19 -04003599 if (old_data < data_end) {
3600 btrfs_print_leaf(root, leaf);
Chris Masond3977122009-01-05 21:25:51 -05003601 printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
Chris Mason5f39d392007-10-15 16:14:19 -04003602 slot, old_data, data_end);
3603 BUG_ON(1);
3604 }
Chris Masonbe0e5c02007-01-26 15:51:26 -05003605 /*
3606 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3607 */
3608 /* first correct the data pointers */
Chris Masondb945352007-10-15 16:15:53 -04003609 WARN_ON(leaf->map_token);
Chris Mason0783fcf2007-03-12 20:12:07 -04003610 for (i = slot; i < nritems; i++) {
Chris Mason5f39d392007-10-15 16:14:19 -04003611 u32 ioff;
Chris Masondb945352007-10-15 16:15:53 -04003612
Chris Mason5f39d392007-10-15 16:14:19 -04003613 item = btrfs_item_nr(leaf, i);
Chris Masondb945352007-10-15 16:15:53 -04003614 if (!leaf->map_token) {
3615 map_extent_buffer(leaf, (unsigned long)item,
3616 sizeof(struct btrfs_item),
3617 &leaf->map_token, &leaf->kaddr,
3618 &leaf->map_start, &leaf->map_len,
3619 KM_USER1);
3620 }
3621
Chris Mason5f39d392007-10-15 16:14:19 -04003622 ioff = btrfs_item_offset(leaf, item);
Chris Mason9c583092008-01-29 15:15:18 -05003623 btrfs_set_item_offset(leaf, item, ioff - total_data);
Chris Mason0783fcf2007-03-12 20:12:07 -04003624 }
Chris Masondb945352007-10-15 16:15:53 -04003625 if (leaf->map_token) {
3626 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3627 leaf->map_token = NULL;
3628 }
Chris Masonbe0e5c02007-01-26 15:51:26 -05003629
3630 /* shift the items */
Chris Mason9c583092008-01-29 15:15:18 -05003631 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
Chris Mason5f39d392007-10-15 16:14:19 -04003632 btrfs_item_nr_offset(slot),
Chris Masond6025572007-03-30 14:27:56 -04003633 (nritems - slot) * sizeof(struct btrfs_item));
Chris Masonbe0e5c02007-01-26 15:51:26 -05003634
3635 /* shift the data */
Chris Mason5f39d392007-10-15 16:14:19 -04003636 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
Chris Mason9c583092008-01-29 15:15:18 -05003637 data_end - total_data, btrfs_leaf_data(leaf) +
Chris Masond6025572007-03-30 14:27:56 -04003638 data_end, old_data - data_end);
Chris Masonbe0e5c02007-01-26 15:51:26 -05003639 data_end = old_data;
3640 }
Chris Mason5f39d392007-10-15 16:14:19 -04003641
Chris Mason62e27492007-03-15 12:56:47 -04003642 /* setup the item for the new data */
Chris Mason9c583092008-01-29 15:15:18 -05003643 for (i = 0; i < nr; i++) {
3644 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3645 btrfs_set_item_key(leaf, &disk_key, slot + i);
3646 item = btrfs_item_nr(leaf, slot + i);
3647 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3648 data_end -= data_size[i];
3649 btrfs_set_item_size(leaf, item, data_size[i]);
3650 }
Chris Mason44871b12009-03-13 10:04:31 -04003651
Chris Mason9c583092008-01-29 15:15:18 -05003652 btrfs_set_header_nritems(leaf, nritems + nr);
Chris Masonaa5d6be2007-02-28 16:35:06 -05003653
3654 ret = 0;
Chris Mason5a01a2e2008-01-30 11:43:54 -05003655 if (slot == 0) {
Chris Mason44871b12009-03-13 10:04:31 -04003656 struct btrfs_disk_key disk_key;
Chris Mason5a01a2e2008-01-30 11:43:54 -05003657 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
Chris Masone089f052007-03-16 16:20:31 -04003658 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
Chris Mason5a01a2e2008-01-30 11:43:54 -05003659 }
Chris Masonb9473432009-03-13 11:00:37 -04003660 btrfs_unlock_up_safe(path, 1);
3661 btrfs_mark_buffer_dirty(leaf);
Chris Masonaa5d6be2007-02-28 16:35:06 -05003662
Chris Mason5f39d392007-10-15 16:14:19 -04003663 if (btrfs_leaf_free_space(root, leaf) < 0) {
3664 btrfs_print_leaf(root, leaf);
Chris Masonbe0e5c02007-01-26 15:51:26 -05003665 BUG();
Chris Mason5f39d392007-10-15 16:14:19 -04003666 }
Chris Mason44871b12009-03-13 10:04:31 -04003667 return ret;
3668}
3669
3670/*
3671 * Given a key and some data, insert items into the tree.
3672 * This does all the path init required, making room in the tree if needed.
3673 */
3674int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3675 struct btrfs_root *root,
3676 struct btrfs_path *path,
3677 struct btrfs_key *cpu_key, u32 *data_size,
3678 int nr)
3679{
Chris Mason44871b12009-03-13 10:04:31 -04003680 int ret = 0;
3681 int slot;
3682 int i;
3683 u32 total_size = 0;
3684 u32 total_data = 0;
3685
3686 for (i = 0; i < nr; i++)
3687 total_data += data_size[i];
3688
3689 total_size = total_data + (nr * sizeof(struct btrfs_item));
3690 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3691 if (ret == 0)
3692 return -EEXIST;
3693 if (ret < 0)
3694 goto out;
3695
Chris Mason44871b12009-03-13 10:04:31 -04003696 slot = path->slots[0];
3697 BUG_ON(slot < 0);
3698
3699 ret = setup_items_for_insert(trans, root, path, cpu_key, data_size,
3700 total_data, total_size, nr);
3701
Chris Masoned2ff2c2007-03-01 18:59:40 -05003702out:
Chris Mason62e27492007-03-15 12:56:47 -04003703 return ret;
3704}
3705
3706/*
3707 * Given a key and some data, insert an item into the tree.
3708 * This does all the path init required, making room in the tree if needed.
3709 */
Chris Masone089f052007-03-16 16:20:31 -04003710int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
3711 *root, struct btrfs_key *cpu_key, void *data, u32
3712 data_size)
Chris Mason62e27492007-03-15 12:56:47 -04003713{
3714 int ret = 0;
Chris Mason2c90e5d2007-04-02 10:50:19 -04003715 struct btrfs_path *path;
Chris Mason5f39d392007-10-15 16:14:19 -04003716 struct extent_buffer *leaf;
3717 unsigned long ptr;
Chris Mason62e27492007-03-15 12:56:47 -04003718
Chris Mason2c90e5d2007-04-02 10:50:19 -04003719 path = btrfs_alloc_path();
3720 BUG_ON(!path);
Chris Mason2c90e5d2007-04-02 10:50:19 -04003721 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
Chris Mason62e27492007-03-15 12:56:47 -04003722 if (!ret) {
Chris Mason5f39d392007-10-15 16:14:19 -04003723 leaf = path->nodes[0];
3724 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
3725 write_extent_buffer(leaf, data, ptr, data_size);
3726 btrfs_mark_buffer_dirty(leaf);
Chris Mason62e27492007-03-15 12:56:47 -04003727 }
Chris Mason2c90e5d2007-04-02 10:50:19 -04003728 btrfs_free_path(path);
Chris Masonaa5d6be2007-02-28 16:35:06 -05003729 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05003730}
3731
Chris Mason74123bd2007-02-02 11:05:29 -05003732/*
Chris Mason5de08d72007-02-24 06:24:44 -05003733 * delete the pointer from a given node.
Chris Mason74123bd2007-02-02 11:05:29 -05003734 *
Chris Masond352ac62008-09-29 15:18:18 -04003735 * the tree should have been previously balanced so the deletion does not
3736 * empty a node.
Chris Mason74123bd2007-02-02 11:05:29 -05003737 */
Chris Masone089f052007-03-16 16:20:31 -04003738static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3739 struct btrfs_path *path, int level, int slot)
Chris Masonbe0e5c02007-01-26 15:51:26 -05003740{
Chris Mason5f39d392007-10-15 16:14:19 -04003741 struct extent_buffer *parent = path->nodes[level];
Chris Mason7518a232007-03-12 12:01:18 -04003742 u32 nritems;
Chris Masonaa5d6be2007-02-28 16:35:06 -05003743 int ret = 0;
Chris Masonbb803952007-03-01 12:04:21 -05003744 int wret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05003745
Chris Mason5f39d392007-10-15 16:14:19 -04003746 nritems = btrfs_header_nritems(parent);
Chris Masond3977122009-01-05 21:25:51 -05003747 if (slot != nritems - 1) {
Chris Mason5f39d392007-10-15 16:14:19 -04003748 memmove_extent_buffer(parent,
3749 btrfs_node_key_ptr_offset(slot),
3750 btrfs_node_key_ptr_offset(slot + 1),
Chris Masond6025572007-03-30 14:27:56 -04003751 sizeof(struct btrfs_key_ptr) *
3752 (nritems - slot - 1));
Chris Masonbb803952007-03-01 12:04:21 -05003753 }
Chris Mason7518a232007-03-12 12:01:18 -04003754 nritems--;
Chris Mason5f39d392007-10-15 16:14:19 -04003755 btrfs_set_header_nritems(parent, nritems);
Chris Mason7518a232007-03-12 12:01:18 -04003756 if (nritems == 0 && parent == root->node) {
Chris Mason5f39d392007-10-15 16:14:19 -04003757 BUG_ON(btrfs_header_level(root->node) != 1);
Chris Masonbb803952007-03-01 12:04:21 -05003758 /* just turn the root into a leaf and break */
Chris Mason5f39d392007-10-15 16:14:19 -04003759 btrfs_set_header_level(root->node, 0);
Chris Masonbb803952007-03-01 12:04:21 -05003760 } else if (slot == 0) {
Chris Mason5f39d392007-10-15 16:14:19 -04003761 struct btrfs_disk_key disk_key;
3762
3763 btrfs_node_key(parent, &disk_key, 0);
3764 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
Chris Mason0f70abe2007-02-28 16:46:22 -05003765 if (wret)
3766 ret = wret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05003767 }
Chris Masond6025572007-03-30 14:27:56 -04003768 btrfs_mark_buffer_dirty(parent);
Chris Masonaa5d6be2007-02-28 16:35:06 -05003769 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05003770}
3771
Chris Mason74123bd2007-02-02 11:05:29 -05003772/*
Chris Mason323ac952008-10-01 19:05:46 -04003773 * a helper function to delete the leaf pointed to by path->slots[1] and
Yan Zheng5d4f98a2009-06-10 10:45:14 -04003774 * path->nodes[1].
Chris Mason323ac952008-10-01 19:05:46 -04003775 *
3776 * This deletes the pointer in path->nodes[1] and frees the leaf
3777 * block extent. zero is returned if it all worked out, < 0 otherwise.
3778 *
3779 * The path must have already been setup for deleting the leaf, including
3780 * all the proper balancing. path->nodes[1] must be locked.
3781 */
Yan Zheng5d4f98a2009-06-10 10:45:14 -04003782static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
3783 struct btrfs_root *root,
3784 struct btrfs_path *path,
3785 struct extent_buffer *leaf)
Chris Mason323ac952008-10-01 19:05:46 -04003786{
3787 int ret;
Chris Mason323ac952008-10-01 19:05:46 -04003788
Yan Zheng5d4f98a2009-06-10 10:45:14 -04003789 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
Chris Mason323ac952008-10-01 19:05:46 -04003790 ret = del_ptr(trans, root, path, 1, path->slots[1]);
3791 if (ret)
3792 return ret;
3793
Chris Mason4d081c42009-02-04 09:31:28 -05003794 /*
3795 * btrfs_free_extent is expensive, we want to make sure we
3796 * aren't holding any locks when we call it
3797 */
3798 btrfs_unlock_up_safe(path, 0);
3799
Yan, Zhengf0486c62010-05-16 10:46:25 -04003800 root_sub_used(root, leaf->len);
3801
3802 btrfs_free_tree_block(trans, root, leaf, 0, 1);
3803 return 0;
Chris Mason323ac952008-10-01 19:05:46 -04003804}
3805/*
Chris Mason74123bd2007-02-02 11:05:29 -05003806 * delete the item at the leaf level in path. If that empties
3807 * the leaf, remove it from the tree
3808 */
Chris Mason85e21ba2008-01-29 15:11:36 -05003809int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3810 struct btrfs_path *path, int slot, int nr)
Chris Masonbe0e5c02007-01-26 15:51:26 -05003811{
Chris Mason5f39d392007-10-15 16:14:19 -04003812 struct extent_buffer *leaf;
3813 struct btrfs_item *item;
Chris Mason85e21ba2008-01-29 15:11:36 -05003814 int last_off;
3815 int dsize = 0;
Chris Masonaa5d6be2007-02-28 16:35:06 -05003816 int ret = 0;
3817 int wret;
Chris Mason85e21ba2008-01-29 15:11:36 -05003818 int i;
Chris Mason7518a232007-03-12 12:01:18 -04003819 u32 nritems;
Chris Masonbe0e5c02007-01-26 15:51:26 -05003820
Chris Mason5f39d392007-10-15 16:14:19 -04003821 leaf = path->nodes[0];
Chris Mason85e21ba2008-01-29 15:11:36 -05003822 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
3823
3824 for (i = 0; i < nr; i++)
3825 dsize += btrfs_item_size_nr(leaf, slot + i);
3826
Chris Mason5f39d392007-10-15 16:14:19 -04003827 nritems = btrfs_header_nritems(leaf);
Chris Masonbe0e5c02007-01-26 15:51:26 -05003828
Chris Mason85e21ba2008-01-29 15:11:36 -05003829 if (slot + nr != nritems) {
Chris Mason123abc82007-03-14 14:14:43 -04003830 int data_end = leaf_data_end(root, leaf);
Chris Mason5f39d392007-10-15 16:14:19 -04003831
3832 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
Chris Masond6025572007-03-30 14:27:56 -04003833 data_end + dsize,
3834 btrfs_leaf_data(leaf) + data_end,
Chris Mason85e21ba2008-01-29 15:11:36 -05003835 last_off - data_end);
Chris Mason5f39d392007-10-15 16:14:19 -04003836
Chris Mason85e21ba2008-01-29 15:11:36 -05003837 for (i = slot + nr; i < nritems; i++) {
Chris Mason5f39d392007-10-15 16:14:19 -04003838 u32 ioff;
Chris Masondb945352007-10-15 16:15:53 -04003839
Chris Mason5f39d392007-10-15 16:14:19 -04003840 item = btrfs_item_nr(leaf, i);
Chris Masondb945352007-10-15 16:15:53 -04003841 if (!leaf->map_token) {
3842 map_extent_buffer(leaf, (unsigned long)item,
3843 sizeof(struct btrfs_item),
3844 &leaf->map_token, &leaf->kaddr,
3845 &leaf->map_start, &leaf->map_len,
3846 KM_USER1);
3847 }
Chris Mason5f39d392007-10-15 16:14:19 -04003848 ioff = btrfs_item_offset(leaf, item);
3849 btrfs_set_item_offset(leaf, item, ioff + dsize);
Chris Mason0783fcf2007-03-12 20:12:07 -04003850 }
Chris Masondb945352007-10-15 16:15:53 -04003851
3852 if (leaf->map_token) {
3853 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3854 leaf->map_token = NULL;
3855 }
3856
Chris Mason5f39d392007-10-15 16:14:19 -04003857 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
Chris Mason85e21ba2008-01-29 15:11:36 -05003858 btrfs_item_nr_offset(slot + nr),
Chris Masond6025572007-03-30 14:27:56 -04003859 sizeof(struct btrfs_item) *
Chris Mason85e21ba2008-01-29 15:11:36 -05003860 (nritems - slot - nr));
Chris Masonbe0e5c02007-01-26 15:51:26 -05003861 }
Chris Mason85e21ba2008-01-29 15:11:36 -05003862 btrfs_set_header_nritems(leaf, nritems - nr);
3863 nritems -= nr;
Chris Mason5f39d392007-10-15 16:14:19 -04003864
Chris Mason74123bd2007-02-02 11:05:29 -05003865 /* delete the leaf if we've emptied it */
Chris Mason7518a232007-03-12 12:01:18 -04003866 if (nritems == 0) {
Chris Mason5f39d392007-10-15 16:14:19 -04003867 if (leaf == root->node) {
3868 btrfs_set_header_level(leaf, 0);
Chris Mason9a8dd152007-02-23 08:38:36 -05003869 } else {
Yan, Zhengf0486c62010-05-16 10:46:25 -04003870 btrfs_set_path_blocking(path);
3871 clean_tree_block(trans, root, leaf);
Yan Zheng5d4f98a2009-06-10 10:45:14 -04003872 ret = btrfs_del_leaf(trans, root, path, leaf);
Chris Mason323ac952008-10-01 19:05:46 -04003873 BUG_ON(ret);
Chris Mason9a8dd152007-02-23 08:38:36 -05003874 }
Chris Masonbe0e5c02007-01-26 15:51:26 -05003875 } else {
Chris Mason7518a232007-03-12 12:01:18 -04003876 int used = leaf_space_used(leaf, 0, nritems);
Chris Masonaa5d6be2007-02-28 16:35:06 -05003877 if (slot == 0) {
Chris Mason5f39d392007-10-15 16:14:19 -04003878 struct btrfs_disk_key disk_key;
3879
3880 btrfs_item_key(leaf, &disk_key, 0);
Chris Masone089f052007-03-16 16:20:31 -04003881 wret = fixup_low_keys(trans, root, path,
Chris Mason5f39d392007-10-15 16:14:19 -04003882 &disk_key, 1);
Chris Masonaa5d6be2007-02-28 16:35:06 -05003883 if (wret)
3884 ret = wret;
3885 }
Chris Masonaa5d6be2007-02-28 16:35:06 -05003886
Chris Mason74123bd2007-02-02 11:05:29 -05003887 /* delete the leaf if it is mostly empty */
Yan Zhengd717aa12009-07-24 12:42:46 -04003888 if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
Chris Masonbe0e5c02007-01-26 15:51:26 -05003889 /* push_leaf_left fixes the path.
3890 * make sure the path still points to our leaf
3891 * for possible call to del_ptr below
3892 */
Chris Mason4920c9a2007-01-26 16:38:42 -05003893 slot = path->slots[1];
Chris Mason5f39d392007-10-15 16:14:19 -04003894 extent_buffer_get(leaf);
3895
Chris Masonb9473432009-03-13 11:00:37 -04003896 btrfs_set_path_blocking(path);
Chris Mason99d8f832010-07-07 10:51:48 -04003897 wret = push_leaf_left(trans, root, path, 1, 1,
3898 1, (u32)-1);
Chris Mason54aa1f42007-06-22 14:16:25 -04003899 if (wret < 0 && wret != -ENOSPC)
Chris Masonaa5d6be2007-02-28 16:35:06 -05003900 ret = wret;
Chris Mason5f39d392007-10-15 16:14:19 -04003901
3902 if (path->nodes[0] == leaf &&
3903 btrfs_header_nritems(leaf)) {
Chris Mason99d8f832010-07-07 10:51:48 -04003904 wret = push_leaf_right(trans, root, path, 1,
3905 1, 1, 0);
Chris Mason54aa1f42007-06-22 14:16:25 -04003906 if (wret < 0 && wret != -ENOSPC)
Chris Masonaa5d6be2007-02-28 16:35:06 -05003907 ret = wret;
3908 }
Chris Mason5f39d392007-10-15 16:14:19 -04003909
3910 if (btrfs_header_nritems(leaf) == 0) {
Chris Mason323ac952008-10-01 19:05:46 -04003911 path->slots[1] = slot;
Yan Zheng5d4f98a2009-06-10 10:45:14 -04003912 ret = btrfs_del_leaf(trans, root, path, leaf);
Chris Mason323ac952008-10-01 19:05:46 -04003913 BUG_ON(ret);
Chris Mason5f39d392007-10-15 16:14:19 -04003914 free_extent_buffer(leaf);
Chris Mason5de08d72007-02-24 06:24:44 -05003915 } else {
Chris Mason925baed2008-06-25 16:01:30 -04003916 /* if we're still in the path, make sure
3917 * we're dirty. Otherwise, one of the
3918 * push_leaf functions must have already
3919 * dirtied this buffer
3920 */
3921 if (path->nodes[0] == leaf)
3922 btrfs_mark_buffer_dirty(leaf);
Chris Mason5f39d392007-10-15 16:14:19 -04003923 free_extent_buffer(leaf);
Chris Masonbe0e5c02007-01-26 15:51:26 -05003924 }
Chris Masond5719762007-03-23 10:01:08 -04003925 } else {
Chris Mason5f39d392007-10-15 16:14:19 -04003926 btrfs_mark_buffer_dirty(leaf);
Chris Masonbe0e5c02007-01-26 15:51:26 -05003927 }
3928 }
Chris Masonaa5d6be2007-02-28 16:35:06 -05003929 return ret;
Chris Masonbe0e5c02007-01-26 15:51:26 -05003930}
3931
Chris Mason97571fd2007-02-24 13:39:08 -05003932/*
Chris Mason925baed2008-06-25 16:01:30 -04003933 * search the tree again to find a leaf with lesser keys
Chris Mason7bb86312007-12-11 09:25:06 -05003934 * returns 0 if it found something or 1 if there are no lesser leaves.
3935 * returns < 0 on io errors.
Chris Masond352ac62008-09-29 15:18:18 -04003936 *
3937 * This may release the path, and so you may lose any locks held at the
3938 * time you call it.
Chris Mason7bb86312007-12-11 09:25:06 -05003939 */
3940int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
3941{
Chris Mason925baed2008-06-25 16:01:30 -04003942 struct btrfs_key key;
3943 struct btrfs_disk_key found_key;
3944 int ret;
Chris Mason7bb86312007-12-11 09:25:06 -05003945
Chris Mason925baed2008-06-25 16:01:30 -04003946 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
Chris Mason7bb86312007-12-11 09:25:06 -05003947
Chris Mason925baed2008-06-25 16:01:30 -04003948 if (key.offset > 0)
3949 key.offset--;
3950 else if (key.type > 0)
3951 key.type--;
3952 else if (key.objectid > 0)
3953 key.objectid--;
3954 else
3955 return 1;
Chris Mason7bb86312007-12-11 09:25:06 -05003956
Chris Mason925baed2008-06-25 16:01:30 -04003957 btrfs_release_path(root, path);
3958 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3959 if (ret < 0)
3960 return ret;
3961 btrfs_item_key(path->nodes[0], &found_key, 0);
3962 ret = comp_keys(&found_key, &key);
3963 if (ret < 0)
3964 return 0;
3965 return 1;
Chris Mason7bb86312007-12-11 09:25:06 -05003966}
3967
Chris Mason3f157a22008-06-25 16:01:31 -04003968/*
3969 * A helper function to walk down the tree starting at min_key, and looking
3970 * for nodes or leaves that are either in cache or have a minimum
Chris Masond352ac62008-09-29 15:18:18 -04003971 * transaction id. This is used by the btree defrag code, and tree logging
Chris Mason3f157a22008-06-25 16:01:31 -04003972 *
3973 * This does not cow, but it does stuff the starting key it finds back
3974 * into min_key, so you can call btrfs_search_slot with cow=1 on the
3975 * key and get a writable path.
3976 *
3977 * This does lock as it descends, and path->keep_locks should be set
3978 * to 1 by the caller.
3979 *
3980 * This honors path->lowest_level to prevent descent past a given level
3981 * of the tree.
3982 *
Chris Masond352ac62008-09-29 15:18:18 -04003983 * min_trans indicates the oldest transaction that you are interested
3984 * in walking through. Any nodes or leaves older than min_trans are
3985 * skipped over (without reading them).
3986 *
Chris Mason3f157a22008-06-25 16:01:31 -04003987 * returns zero if something useful was found, < 0 on error and 1 if there
3988 * was nothing in the tree that matched the search criteria.
3989 */
3990int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
Chris Masone02119d2008-09-05 16:13:11 -04003991 struct btrfs_key *max_key,
Chris Mason3f157a22008-06-25 16:01:31 -04003992 struct btrfs_path *path, int cache_only,
3993 u64 min_trans)
3994{
3995 struct extent_buffer *cur;
3996 struct btrfs_key found_key;
3997 int slot;
Yan96524802008-07-24 12:19:49 -04003998 int sret;
Chris Mason3f157a22008-06-25 16:01:31 -04003999 u32 nritems;
4000 int level;
4001 int ret = 1;
4002
Chris Mason934d3752008-12-08 16:43:10 -05004003 WARN_ON(!path->keep_locks);
Chris Mason3f157a22008-06-25 16:01:31 -04004004again:
4005 cur = btrfs_lock_root_node(root);
4006 level = btrfs_header_level(cur);
Chris Masone02119d2008-09-05 16:13:11 -04004007 WARN_ON(path->nodes[level]);
Chris Mason3f157a22008-06-25 16:01:31 -04004008 path->nodes[level] = cur;
4009 path->locks[level] = 1;
4010
4011 if (btrfs_header_generation(cur) < min_trans) {
4012 ret = 1;
4013 goto out;
4014 }
Chris Masond3977122009-01-05 21:25:51 -05004015 while (1) {
Chris Mason3f157a22008-06-25 16:01:31 -04004016 nritems = btrfs_header_nritems(cur);
4017 level = btrfs_header_level(cur);
Yan96524802008-07-24 12:19:49 -04004018 sret = bin_search(cur, min_key, level, &slot);
Chris Mason3f157a22008-06-25 16:01:31 -04004019
Chris Mason323ac952008-10-01 19:05:46 -04004020 /* at the lowest level, we're done, setup the path and exit */
4021 if (level == path->lowest_level) {
Chris Masone02119d2008-09-05 16:13:11 -04004022 if (slot >= nritems)
4023 goto find_next_key;
Chris Mason3f157a22008-06-25 16:01:31 -04004024 ret = 0;
4025 path->slots[level] = slot;
4026 btrfs_item_key_to_cpu(cur, &found_key, slot);
4027 goto out;
4028 }
Yan96524802008-07-24 12:19:49 -04004029 if (sret && slot > 0)
4030 slot--;
Chris Mason3f157a22008-06-25 16:01:31 -04004031 /*
4032 * check this node pointer against the cache_only and
4033 * min_trans parameters. If it isn't in cache or is too
4034 * old, skip to the next one.
4035 */
Chris Masond3977122009-01-05 21:25:51 -05004036 while (slot < nritems) {
Chris Mason3f157a22008-06-25 16:01:31 -04004037 u64 blockptr;
4038 u64 gen;
4039 struct extent_buffer *tmp;
Chris Masone02119d2008-09-05 16:13:11 -04004040 struct btrfs_disk_key disk_key;
4041
Chris Mason3f157a22008-06-25 16:01:31 -04004042 blockptr = btrfs_node_blockptr(cur, slot);
4043 gen = btrfs_node_ptr_generation(cur, slot);
4044 if (gen < min_trans) {
4045 slot++;
4046 continue;
4047 }
4048 if (!cache_only)
4049 break;
4050
Chris Masone02119d2008-09-05 16:13:11 -04004051 if (max_key) {
4052 btrfs_node_key(cur, &disk_key, slot);
4053 if (comp_keys(&disk_key, max_key) >= 0) {
4054 ret = 1;
4055 goto out;
4056 }
4057 }
4058
Chris Mason3f157a22008-06-25 16:01:31 -04004059 tmp = btrfs_find_tree_block(root, blockptr,
4060 btrfs_level_size(root, level - 1));
4061
4062 if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
4063 free_extent_buffer(tmp);
4064 break;
4065 }
4066 if (tmp)
4067 free_extent_buffer(tmp);
4068 slot++;
4069 }
Chris Masone02119d2008-09-05 16:13:11 -04004070find_next_key:
Chris Mason3f157a22008-06-25 16:01:31 -04004071 /*
4072 * we didn't find a candidate key in this node, walk forward
4073 * and find another one
4074 */
4075 if (slot >= nritems) {
Chris Masone02119d2008-09-05 16:13:11 -04004076 path->slots[level] = slot;
Chris Masonb4ce94d2009-02-04 09:25:08 -05004077 btrfs_set_path_blocking(path);
Chris Masone02119d2008-09-05 16:13:11 -04004078 sret = btrfs_find_next_key(root, path, min_key, level,
Chris Mason3f157a22008-06-25 16:01:31 -04004079 cache_only, min_trans);
Chris Masone02119d2008-09-05 16:13:11 -04004080 if (sret == 0) {
Chris Mason3f157a22008-06-25 16:01:31 -04004081 btrfs_release_path(root, path);
4082 goto again;
4083 } else {
4084 goto out;
4085 }
4086 }
4087 /* save our key for returning back */
4088 btrfs_node_key_to_cpu(cur, &found_key, slot);
4089 path->slots[level] = slot;
4090 if (level == path->lowest_level) {
4091 ret = 0;
4092 unlock_up(path, level, 1);
4093 goto out;
4094 }
Chris Masonb4ce94d2009-02-04 09:25:08 -05004095 btrfs_set_path_blocking(path);
Chris Mason3f157a22008-06-25 16:01:31 -04004096 cur = read_node_slot(root, cur, slot);
4097
4098 btrfs_tree_lock(cur);
Chris Masonb4ce94d2009-02-04 09:25:08 -05004099
Chris Mason3f157a22008-06-25 16:01:31 -04004100 path->locks[level - 1] = 1;
4101 path->nodes[level - 1] = cur;
4102 unlock_up(path, level, 1);
Chris Mason4008c042009-02-12 14:09:45 -05004103 btrfs_clear_path_blocking(path, NULL);
Chris Mason3f157a22008-06-25 16:01:31 -04004104 }
4105out:
4106 if (ret == 0)
4107 memcpy(min_key, &found_key, sizeof(found_key));
Chris Masonb4ce94d2009-02-04 09:25:08 -05004108 btrfs_set_path_blocking(path);
Chris Mason3f157a22008-06-25 16:01:31 -04004109 return ret;
4110}
4111
4112/*
4113 * this is similar to btrfs_next_leaf, but does not try to preserve
4114 * and fixup the path. It looks for and returns the next key in the
4115 * tree based on the current path and the cache_only and min_trans
4116 * parameters.
4117 *
4118 * 0 is returned if another key is found, < 0 if there are any errors
4119 * and 1 is returned if there are no higher keys in the tree
4120 *
4121 * path->keep_locks should be set to 1 on the search made before
4122 * calling this function.
4123 */
Chris Masone7a84562008-06-25 16:01:31 -04004124int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
Yan Zheng33c66f42009-07-22 09:59:00 -04004125 struct btrfs_key *key, int level,
Chris Mason3f157a22008-06-25 16:01:31 -04004126 int cache_only, u64 min_trans)
Chris Masone7a84562008-06-25 16:01:31 -04004127{
Chris Masone7a84562008-06-25 16:01:31 -04004128 int slot;
4129 struct extent_buffer *c;
4130
Chris Mason934d3752008-12-08 16:43:10 -05004131 WARN_ON(!path->keep_locks);
Chris Masond3977122009-01-05 21:25:51 -05004132 while (level < BTRFS_MAX_LEVEL) {
Chris Masone7a84562008-06-25 16:01:31 -04004133 if (!path->nodes[level])
4134 return 1;
4135
4136 slot = path->slots[level] + 1;
4137 c = path->nodes[level];
Chris Mason3f157a22008-06-25 16:01:31 -04004138next:
Chris Masone7a84562008-06-25 16:01:31 -04004139 if (slot >= btrfs_header_nritems(c)) {
Yan Zheng33c66f42009-07-22 09:59:00 -04004140 int ret;
4141 int orig_lowest;
4142 struct btrfs_key cur_key;
4143 if (level + 1 >= BTRFS_MAX_LEVEL ||
4144 !path->nodes[level + 1])
Chris Masone7a84562008-06-25 16:01:31 -04004145 return 1;
Yan Zheng33c66f42009-07-22 09:59:00 -04004146
4147 if (path->locks[level + 1]) {
4148 level++;
4149 continue;
4150 }
4151
4152 slot = btrfs_header_nritems(c) - 1;
4153 if (level == 0)
4154 btrfs_item_key_to_cpu(c, &cur_key, slot);
4155 else
4156 btrfs_node_key_to_cpu(c, &cur_key, slot);
4157
4158 orig_lowest = path->lowest_level;
4159 btrfs_release_path(root, path);
4160 path->lowest_level = level;
4161 ret = btrfs_search_slot(NULL, root, &cur_key, path,
4162 0, 0);
4163 path->lowest_level = orig_lowest;
4164 if (ret < 0)
4165 return ret;
4166
4167 c = path->nodes[level];
4168 slot = path->slots[level];
4169 if (ret == 0)
4170 slot++;
4171 goto next;
Chris Masone7a84562008-06-25 16:01:31 -04004172 }
Yan Zheng33c66f42009-07-22 09:59:00 -04004173
Chris Masone7a84562008-06-25 16:01:31 -04004174 if (level == 0)
4175 btrfs_item_key_to_cpu(c, key, slot);
Chris Mason3f157a22008-06-25 16:01:31 -04004176 else {
4177 u64 blockptr = btrfs_node_blockptr(c, slot);
4178 u64 gen = btrfs_node_ptr_generation(c, slot);
4179
4180 if (cache_only) {
4181 struct extent_buffer *cur;
4182 cur = btrfs_find_tree_block(root, blockptr,
4183 btrfs_level_size(root, level - 1));
4184 if (!cur || !btrfs_buffer_uptodate(cur, gen)) {
4185 slot++;
4186 if (cur)
4187 free_extent_buffer(cur);
4188 goto next;
4189 }
4190 free_extent_buffer(cur);
4191 }
4192 if (gen < min_trans) {
4193 slot++;
4194 goto next;
4195 }
Chris Masone7a84562008-06-25 16:01:31 -04004196 btrfs_node_key_to_cpu(c, key, slot);
Chris Mason3f157a22008-06-25 16:01:31 -04004197 }
Chris Masone7a84562008-06-25 16:01:31 -04004198 return 0;
4199 }
4200 return 1;
4201}
4202
Chris Mason7bb86312007-12-11 09:25:06 -05004203/*
Chris Mason925baed2008-06-25 16:01:30 -04004204 * search the tree again to find a leaf with greater keys
Chris Mason0f70abe2007-02-28 16:46:22 -05004205 * returns 0 if it found something or 1 if there are no greater leaves.
4206 * returns < 0 on io errors.
Chris Mason97571fd2007-02-24 13:39:08 -05004207 */
Chris Mason234b63a2007-03-13 10:46:10 -04004208int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
Chris Masond97e63b2007-02-20 16:40:44 -05004209{
4210 int slot;
Chris Mason8e73f272009-04-03 10:14:18 -04004211 int level;
Chris Mason5f39d392007-10-15 16:14:19 -04004212 struct extent_buffer *c;
Chris Mason8e73f272009-04-03 10:14:18 -04004213 struct extent_buffer *next;
Chris Mason925baed2008-06-25 16:01:30 -04004214 struct btrfs_key key;
4215 u32 nritems;
4216 int ret;
Chris Mason8e73f272009-04-03 10:14:18 -04004217 int old_spinning = path->leave_spinning;
4218 int force_blocking = 0;
Chris Mason925baed2008-06-25 16:01:30 -04004219
4220 nritems = btrfs_header_nritems(path->nodes[0]);
Chris Masond3977122009-01-05 21:25:51 -05004221 if (nritems == 0)
Chris Mason925baed2008-06-25 16:01:30 -04004222 return 1;
Chris Mason925baed2008-06-25 16:01:30 -04004223
Chris Mason8e73f272009-04-03 10:14:18 -04004224 /*
4225 * we take the blocks in an order that upsets lockdep. Using
4226 * blocking mode is the only way around it.
4227 */
4228#ifdef CONFIG_DEBUG_LOCK_ALLOC
4229 force_blocking = 1;
4230#endif
Chris Mason925baed2008-06-25 16:01:30 -04004231
Chris Mason8e73f272009-04-03 10:14:18 -04004232 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4233again:
4234 level = 1;
4235 next = NULL;
Chris Mason925baed2008-06-25 16:01:30 -04004236 btrfs_release_path(root, path);
Chris Mason8e73f272009-04-03 10:14:18 -04004237
Chris Masona2135012008-06-25 16:01:30 -04004238 path->keep_locks = 1;
Chris Mason8e73f272009-04-03 10:14:18 -04004239
4240 if (!force_blocking)
4241 path->leave_spinning = 1;
4242
Chris Mason925baed2008-06-25 16:01:30 -04004243 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4244 path->keep_locks = 0;
4245
4246 if (ret < 0)
4247 return ret;
4248
Chris Masona2135012008-06-25 16:01:30 -04004249 nritems = btrfs_header_nritems(path->nodes[0]);
Chris Mason168fd7d2008-06-25 16:01:30 -04004250 /*
4251 * by releasing the path above we dropped all our locks. A balance
4252 * could have added more items next to the key that used to be
4253 * at the very end of the block. So, check again here and
4254 * advance the path if there are now more items available.
4255 */
Chris Masona2135012008-06-25 16:01:30 -04004256 if (nritems > 0 && path->slots[0] < nritems - 1) {
Yan Zhenge457afe2009-07-22 09:59:00 -04004257 if (ret == 0)
4258 path->slots[0]++;
Chris Mason8e73f272009-04-03 10:14:18 -04004259 ret = 0;
Chris Mason925baed2008-06-25 16:01:30 -04004260 goto done;
4261 }
Chris Masond97e63b2007-02-20 16:40:44 -05004262
Chris Masond3977122009-01-05 21:25:51 -05004263 while (level < BTRFS_MAX_LEVEL) {
Chris Mason8e73f272009-04-03 10:14:18 -04004264 if (!path->nodes[level]) {
4265 ret = 1;
4266 goto done;
4267 }
Chris Mason5f39d392007-10-15 16:14:19 -04004268
Chris Masond97e63b2007-02-20 16:40:44 -05004269 slot = path->slots[level] + 1;
4270 c = path->nodes[level];
Chris Mason5f39d392007-10-15 16:14:19 -04004271 if (slot >= btrfs_header_nritems(c)) {
Chris Masond97e63b2007-02-20 16:40:44 -05004272 level++;
Chris Mason8e73f272009-04-03 10:14:18 -04004273 if (level == BTRFS_MAX_LEVEL) {
4274 ret = 1;
4275 goto done;
4276 }
Chris Masond97e63b2007-02-20 16:40:44 -05004277 continue;
4278 }
Chris Mason5f39d392007-10-15 16:14:19 -04004279
Chris Mason925baed2008-06-25 16:01:30 -04004280 if (next) {
4281 btrfs_tree_unlock(next);
Chris Mason5f39d392007-10-15 16:14:19 -04004282 free_extent_buffer(next);
Chris Mason925baed2008-06-25 16:01:30 -04004283 }
Chris Mason5f39d392007-10-15 16:14:19 -04004284
Chris Mason8e73f272009-04-03 10:14:18 -04004285 next = c;
4286 ret = read_block_for_search(NULL, root, path, &next, level,
4287 slot, &key);
4288 if (ret == -EAGAIN)
4289 goto again;
Chris Mason5f39d392007-10-15 16:14:19 -04004290
Chris Mason76a05b32009-05-14 13:24:30 -04004291 if (ret < 0) {
4292 btrfs_release_path(root, path);
4293 goto done;
4294 }
4295
Chris Mason5cd57b22008-06-25 16:01:30 -04004296 if (!path->skip_locking) {
Chris Mason8e73f272009-04-03 10:14:18 -04004297 ret = btrfs_try_spin_lock(next);
4298 if (!ret) {
4299 btrfs_set_path_blocking(path);
4300 btrfs_tree_lock(next);
4301 if (!force_blocking)
4302 btrfs_clear_path_blocking(path, next);
4303 }
4304 if (force_blocking)
4305 btrfs_set_lock_blocking(next);
Chris Mason5cd57b22008-06-25 16:01:30 -04004306 }
Chris Masond97e63b2007-02-20 16:40:44 -05004307 break;
4308 }
4309 path->slots[level] = slot;
Chris Masond3977122009-01-05 21:25:51 -05004310 while (1) {
Chris Masond97e63b2007-02-20 16:40:44 -05004311 level--;
4312 c = path->nodes[level];
Chris Mason925baed2008-06-25 16:01:30 -04004313 if (path->locks[level])
4314 btrfs_tree_unlock(c);
Chris Mason8e73f272009-04-03 10:14:18 -04004315
Chris Mason5f39d392007-10-15 16:14:19 -04004316 free_extent_buffer(c);
Chris Masond97e63b2007-02-20 16:40:44 -05004317 path->nodes[level] = next;
4318 path->slots[level] = 0;
Chris Masona74a4b92008-06-25 16:01:31 -04004319 if (!path->skip_locking)
4320 path->locks[level] = 1;
Chris Mason8e73f272009-04-03 10:14:18 -04004321
Chris Masond97e63b2007-02-20 16:40:44 -05004322 if (!level)
4323 break;
Chris Masonb4ce94d2009-02-04 09:25:08 -05004324
Chris Mason8e73f272009-04-03 10:14:18 -04004325 ret = read_block_for_search(NULL, root, path, &next, level,
4326 0, &key);
4327 if (ret == -EAGAIN)
4328 goto again;
4329
Chris Mason76a05b32009-05-14 13:24:30 -04004330 if (ret < 0) {
4331 btrfs_release_path(root, path);
4332 goto done;
4333 }
4334
Chris Mason5cd57b22008-06-25 16:01:30 -04004335 if (!path->skip_locking) {
Chris Masonb9447ef2009-03-09 11:45:38 -04004336 btrfs_assert_tree_locked(path->nodes[level]);
Chris Mason8e73f272009-04-03 10:14:18 -04004337 ret = btrfs_try_spin_lock(next);
4338 if (!ret) {
4339 btrfs_set_path_blocking(path);
4340 btrfs_tree_lock(next);
4341 if (!force_blocking)
4342 btrfs_clear_path_blocking(path, next);
4343 }
4344 if (force_blocking)
4345 btrfs_set_lock_blocking(next);
Chris Mason5cd57b22008-06-25 16:01:30 -04004346 }
Chris Masond97e63b2007-02-20 16:40:44 -05004347 }
Chris Mason8e73f272009-04-03 10:14:18 -04004348 ret = 0;
Chris Mason925baed2008-06-25 16:01:30 -04004349done:
4350 unlock_up(path, 0, 1);
Chris Mason8e73f272009-04-03 10:14:18 -04004351 path->leave_spinning = old_spinning;
4352 if (!old_spinning)
4353 btrfs_set_path_blocking(path);
4354
4355 return ret;
Chris Masond97e63b2007-02-20 16:40:44 -05004356}
Chris Mason0b86a832008-03-24 15:01:56 -04004357
Chris Mason3f157a22008-06-25 16:01:31 -04004358/*
4359 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
4360 * searching until it gets past min_objectid or finds an item of 'type'
4361 *
4362 * returns 0 if something is found, 1 if nothing was found and < 0 on error
4363 */
Chris Mason0b86a832008-03-24 15:01:56 -04004364int btrfs_previous_item(struct btrfs_root *root,
4365 struct btrfs_path *path, u64 min_objectid,
4366 int type)
4367{
4368 struct btrfs_key found_key;
4369 struct extent_buffer *leaf;
Chris Masone02119d2008-09-05 16:13:11 -04004370 u32 nritems;
Chris Mason0b86a832008-03-24 15:01:56 -04004371 int ret;
4372
Chris Masond3977122009-01-05 21:25:51 -05004373 while (1) {
Chris Mason0b86a832008-03-24 15:01:56 -04004374 if (path->slots[0] == 0) {
Chris Masonb4ce94d2009-02-04 09:25:08 -05004375 btrfs_set_path_blocking(path);
Chris Mason0b86a832008-03-24 15:01:56 -04004376 ret = btrfs_prev_leaf(root, path);
4377 if (ret != 0)
4378 return ret;
4379 } else {
4380 path->slots[0]--;
4381 }
4382 leaf = path->nodes[0];
Chris Masone02119d2008-09-05 16:13:11 -04004383 nritems = btrfs_header_nritems(leaf);
4384 if (nritems == 0)
4385 return 1;
4386 if (path->slots[0] == nritems)
4387 path->slots[0]--;
4388
Chris Mason0b86a832008-03-24 15:01:56 -04004389 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
Chris Masone02119d2008-09-05 16:13:11 -04004390 if (found_key.objectid < min_objectid)
4391 break;
Yan Zheng0a4eefb2009-07-24 11:06:53 -04004392 if (found_key.type == type)
4393 return 0;
Chris Masone02119d2008-09-05 16:13:11 -04004394 if (found_key.objectid == min_objectid &&
4395 found_key.type < type)
4396 break;
Chris Mason0b86a832008-03-24 15:01:56 -04004397 }
4398 return 1;
4399}