extent-tree.c 154.1 KB
Newer Older
C
Chris Mason 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/*
 * Copyright (C) 2007 Oracle.  All rights reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License v2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 021110-1307, USA.
 */
Z
Zach Brown 已提交
18
#include <linux/sched.h>
19
#include <linux/pagemap.h>
20
#include <linux/writeback.h>
21
#include <linux/blkdev.h>
22
#include <linux/sort.h>
23
#include <linux/rcupdate.h>
C
Chris Mason 已提交
24
#include "compat.h"
25
#include "hash.h"
26
#include "crc32c.h"
27 28 29
#include "ctree.h"
#include "disk-io.h"
#include "print-tree.h"
30
#include "transaction.h"
31
#include "volumes.h"
32
#include "locking.h"
Y
Yan Zheng 已提交
33
#include "ref-cache.h"
34

Z
Zheng Yan 已提交
35 36 37 38 39 40 41 42 43 44 45 46 47
#define PENDING_EXTENT_INSERT 0
#define PENDING_EXTENT_DELETE 1
#define PENDING_BACKREF_UPDATE 2

struct pending_extent_op {
	int type;
	u64 bytenr;
	u64 num_bytes;
	u64 parent;
	u64 orig_parent;
	u64 generation;
	u64 orig_generation;
	int level;
48 49
	struct list_head list;
	int del;
Z
Zheng Yan 已提交
50 51
};

52 53 54 55 56 57 58
static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
					 struct btrfs_root *root, u64 parent,
					 u64 root_objectid, u64 ref_generation,
					 u64 owner, struct btrfs_key *ins,
					 int ref_mod);
static int update_reserved_extents(struct btrfs_root *root,
				   u64 bytenr, u64 num, int reserve);
59 60 61 62
static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
			      u64 bytenr, u64 num_bytes, int alloc,
			      int mark_free);
63 64 65 66 67 68
static noinline int __btrfs_free_extent(struct btrfs_trans_handle *trans,
					struct btrfs_root *root,
					u64 bytenr, u64 num_bytes, u64 parent,
					u64 root_objectid, u64 ref_generation,
					u64 owner_objectid, int pin,
					int ref_to_drop);
69

J
Josef Bacik 已提交
70 71 72 73
static int do_chunk_alloc(struct btrfs_trans_handle *trans,
			  struct btrfs_root *extent_root, u64 alloc_bytes,
			  u64 flags, int force);

J
Josef Bacik 已提交
74 75 76 77 78 79 80 81 82
static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
{
	return (cache->flags & bits) == bits;
}

/*
 * this adds the block group to the fs_info rb tree for the block group
 * cache
 */
83
static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
J
Josef Bacik 已提交
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
				struct btrfs_block_group_cache *block_group)
{
	struct rb_node **p;
	struct rb_node *parent = NULL;
	struct btrfs_block_group_cache *cache;

	spin_lock(&info->block_group_cache_lock);
	p = &info->block_group_cache_tree.rb_node;

	while (*p) {
		parent = *p;
		cache = rb_entry(parent, struct btrfs_block_group_cache,
				 cache_node);
		if (block_group->key.objectid < cache->key.objectid) {
			p = &(*p)->rb_left;
		} else if (block_group->key.objectid > cache->key.objectid) {
			p = &(*p)->rb_right;
		} else {
			spin_unlock(&info->block_group_cache_lock);
			return -EEXIST;
		}
	}

	rb_link_node(&block_group->cache_node, parent, p);
	rb_insert_color(&block_group->cache_node,
			&info->block_group_cache_tree);
	spin_unlock(&info->block_group_cache_lock);

	return 0;
}

/*
 * This will return the block group at or after bytenr if contains is 0, else
 * it will return the block group that contains the bytenr
 */
static struct btrfs_block_group_cache *
block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
			      int contains)
{
	struct btrfs_block_group_cache *cache, *ret = NULL;
	struct rb_node *n;
	u64 end, start;

	spin_lock(&info->block_group_cache_lock);
	n = info->block_group_cache_tree.rb_node;

	while (n) {
		cache = rb_entry(n, struct btrfs_block_group_cache,
				 cache_node);
		end = cache->key.objectid + cache->key.offset - 1;
		start = cache->key.objectid;

		if (bytenr < start) {
			if (!contains && (!ret || start < ret->key.objectid))
				ret = cache;
			n = n->rb_left;
		} else if (bytenr > start) {
			if (contains && bytenr <= end) {
				ret = cache;
				break;
			}
			n = n->rb_right;
		} else {
			ret = cache;
			break;
		}
	}
151 152
	if (ret)
		atomic_inc(&ret->count);
J
Josef Bacik 已提交
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
	spin_unlock(&info->block_group_cache_lock);

	return ret;
}

/*
 * this is only called by cache_block_group, since we could have freed extents
 * we need to check the pinned_extents for any extents that can't be used yet
 * since their free space will be released as soon as the transaction commits.
 */
static int add_new_free_space(struct btrfs_block_group_cache *block_group,
			      struct btrfs_fs_info *info, u64 start, u64 end)
{
	u64 extent_start, extent_end, size;
	int ret;

169
	mutex_lock(&info->pinned_mutex);
J
Josef Bacik 已提交
170 171 172 173 174 175 176 177 178 179 180
	while (start < end) {
		ret = find_first_extent_bit(&info->pinned_extents, start,
					    &extent_start, &extent_end,
					    EXTENT_DIRTY);
		if (ret)
			break;

		if (extent_start == start) {
			start = extent_end + 1;
		} else if (extent_start > start && extent_start < end) {
			size = extent_start - start;
181 182
			ret = btrfs_add_free_space(block_group, start,
						   size);
J
Josef Bacik 已提交
183 184 185 186 187 188 189 190 191
			BUG_ON(ret);
			start = extent_end + 1;
		} else {
			break;
		}
	}

	if (start < end) {
		size = end - start;
192
		ret = btrfs_add_free_space(block_group, start, size);
J
Josef Bacik 已提交
193 194
		BUG_ON(ret);
	}
195
	mutex_unlock(&info->pinned_mutex);
J
Josef Bacik 已提交
196 197 198 199

	return 0;
}

Y
Yan Zheng 已提交
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222
static int remove_sb_from_cache(struct btrfs_root *root,
				struct btrfs_block_group_cache *cache)
{
	u64 bytenr;
	u64 *logical;
	int stripe_len;
	int i, nr, ret;

	for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
		bytenr = btrfs_sb_offset(i);
		ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
				       cache->key.objectid, bytenr, 0,
				       &logical, &nr, &stripe_len);
		BUG_ON(ret);
		while (nr--) {
			btrfs_remove_free_space(cache, logical[nr],
						stripe_len);
		}
		kfree(logical);
	}
	return 0;
}

223 224 225 226
static int cache_block_group(struct btrfs_root *root,
			     struct btrfs_block_group_cache *block_group)
{
	struct btrfs_path *path;
227
	int ret = 0;
228
	struct btrfs_key key;
229
	struct extent_buffer *leaf;
230
	int slot;
Y
Yan Zheng 已提交
231
	u64 last;
232

233 234 235
	if (!block_group)
		return 0;

236 237 238 239
	root = root->fs_info->extent_root;

	if (block_group->cached)
		return 0;
240

241 242 243
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
244

245
	path->reada = 2;
246 247 248 249 250 251
	/*
	 * we get into deadlocks with paths held by callers of this function.
	 * since the alloc_mutex is protecting things right now, just
	 * skip the locking here
	 */
	path->skip_locking = 1;
Y
Yan Zheng 已提交
252 253
	last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
	key.objectid = last;
254 255 256 257
	key.offset = 0;
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
258
		goto err;
Y
Yan Zheng 已提交
259

C
Chris Mason 已提交
260
	while (1) {
261
		leaf = path->nodes[0];
262
		slot = path->slots[0];
263
		if (slot >= btrfs_header_nritems(leaf)) {
264
			ret = btrfs_next_leaf(root, path);
265 266
			if (ret < 0)
				goto err;
J
Josef Bacik 已提交
267
			if (ret == 0)
268
				continue;
J
Josef Bacik 已提交
269
			else
270 271
				break;
		}
272
		btrfs_item_key_to_cpu(leaf, &key, slot);
J
Josef Bacik 已提交
273
		if (key.objectid < block_group->key.objectid)
274
			goto next;
J
Josef Bacik 已提交
275

276
		if (key.objectid >= block_group->key.objectid +
J
Josef Bacik 已提交
277
		    block_group->key.offset)
278
			break;
279

280
		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
J
Josef Bacik 已提交
281 282 283
			add_new_free_space(block_group, root->fs_info, last,
					   key.objectid);

284
			last = key.objectid + key.offset;
285
		}
286
next:
287 288 289
		path->slots[0]++;
	}

J
Josef Bacik 已提交
290 291 292 293
	add_new_free_space(block_group, root->fs_info, last,
			   block_group->key.objectid +
			   block_group->key.offset);

Y
Yan Zheng 已提交
294
	remove_sb_from_cache(root, block_group);
295
	block_group->cached = 1;
296
	ret = 0;
297
err:
298
	btrfs_free_path(path);
299
	return ret;
300 301
}

J
Josef Bacik 已提交
302 303 304
/*
 * return the block group that starts at or after bytenr
 */
C
Chris Mason 已提交
305 306
static struct btrfs_block_group_cache *
btrfs_lookup_first_block_group(struct btrfs_fs_info *info, u64 bytenr)
C
Chris Mason 已提交
307
{
J
Josef Bacik 已提交
308
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
309

J
Josef Bacik 已提交
310
	cache = block_group_cache_tree_search(info, bytenr, 0);
C
Chris Mason 已提交
311

J
Josef Bacik 已提交
312
	return cache;
C
Chris Mason 已提交
313 314
}

J
Josef Bacik 已提交
315 316 317
/*
 * return the block group that contains teh given bytenr
 */
C
Chris Mason 已提交
318 319 320
struct btrfs_block_group_cache *btrfs_lookup_block_group(
						 struct btrfs_fs_info *info,
						 u64 bytenr)
C
Chris Mason 已提交
321
{
J
Josef Bacik 已提交
322
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
323

J
Josef Bacik 已提交
324
	cache = block_group_cache_tree_search(info, bytenr, 1);
325

J
Josef Bacik 已提交
326
	return cache;
C
Chris Mason 已提交
327
}
328

329 330 331 332 333 334
static inline void put_block_group(struct btrfs_block_group_cache *cache)
{
	if (atomic_dec_and_test(&cache->count))
		kfree(cache);
}

J
Josef Bacik 已提交
335 336
static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
						  u64 flags)
337
{
J
Josef Bacik 已提交
338 339
	struct list_head *head = &info->space_info;
	struct btrfs_space_info *found;
340 341 342 343 344

	rcu_read_lock();
	list_for_each_entry_rcu(found, head, list) {
		if (found->flags == flags) {
			rcu_read_unlock();
J
Josef Bacik 已提交
345
			return found;
346
		}
J
Josef Bacik 已提交
347
	}
348
	rcu_read_unlock();
J
Josef Bacik 已提交
349
	return NULL;
350 351
}

352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
/*
 * after adding space to the filesystem, we need to clear the full flags
 * on all the space infos.
 */
void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
{
	struct list_head *head = &info->space_info;
	struct btrfs_space_info *found;

	rcu_read_lock();
	list_for_each_entry_rcu(found, head, list)
		found->full = 0;
	rcu_read_unlock();
}

367 368 369 370 371 372 373 374 375
static u64 div_factor(u64 num, int factor)
{
	if (factor == 10)
		return num;
	num *= factor;
	do_div(num, 10);
	return num;
}

376 377
u64 btrfs_find_block_group(struct btrfs_root *root,
			   u64 search_start, u64 search_hint, int owner)
C
Chris Mason 已提交
378
{
379
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
380
	u64 used;
381 382
	u64 last = max(search_hint, search_start);
	u64 group_start = 0;
383
	int full_search = 0;
384
	int factor = 9;
C
Chris Mason 已提交
385
	int wrapped = 0;
386
again:
387 388
	while (1) {
		cache = btrfs_lookup_first_block_group(root->fs_info, last);
J
Josef Bacik 已提交
389 390
		if (!cache)
			break;
391

392
		spin_lock(&cache->lock);
393 394 395
		last = cache->key.objectid + cache->key.offset;
		used = btrfs_block_group_used(&cache->item);

396 397
		if ((full_search || !cache->ro) &&
		    block_group_bits(cache, BTRFS_BLOCK_GROUP_METADATA)) {
398
			if (used + cache->pinned + cache->reserved <
399 400
			    div_factor(cache->key.offset, factor)) {
				group_start = cache->key.objectid;
401
				spin_unlock(&cache->lock);
402
				put_block_group(cache);
403 404
				goto found;
			}
405
		}
406
		spin_unlock(&cache->lock);
407
		put_block_group(cache);
408
		cond_resched();
C
Chris Mason 已提交
409
	}
C
Chris Mason 已提交
410 411 412 413 414 415
	if (!wrapped) {
		last = search_start;
		wrapped = 1;
		goto again;
	}
	if (!full_search && factor < 10) {
C
Chris Mason 已提交
416
		last = search_start;
417
		full_search = 1;
C
Chris Mason 已提交
418
		factor = 10;
419 420
		goto again;
	}
C
Chris Mason 已提交
421
found:
422
	return group_start;
423
}
J
Josef Bacik 已提交
424

425
/* simple helper to search for an existing extent at a given offset */
Z
Zheng Yan 已提交
426
int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
427 428 429
{
	int ret;
	struct btrfs_key key;
Z
Zheng Yan 已提交
430
	struct btrfs_path *path;
431

Z
Zheng Yan 已提交
432 433
	path = btrfs_alloc_path();
	BUG_ON(!path);
434 435 436 437 438
	key.objectid = start;
	key.offset = len;
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
				0, 0);
Z
Zheng Yan 已提交
439
	btrfs_free_path(path);
440 441 442
	return ret;
}

443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459
/*
 * Back reference rules.  Back refs have three main goals:
 *
 * 1) differentiate between all holders of references to an extent so that
 *    when a reference is dropped we can make sure it was a valid reference
 *    before freeing the extent.
 *
 * 2) Provide enough information to quickly find the holders of an extent
 *    if we notice a given block is corrupted or bad.
 *
 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 *    maintenance.  This is actually the same as #2, but with a slightly
 *    different use case.
 *
 * File extents can be referenced by:
 *
 * - multiple snapshots, subvolumes, or different generations in one subvol
Z
Zheng Yan 已提交
460
 * - different files inside a single subvolume
461 462 463 464 465 466 467
 * - different offsets inside a file (bookend extents in file.c)
 *
 * The extent ref structure has fields for:
 *
 * - Objectid of the subvolume root
 * - Generation number of the tree holding the reference
 * - objectid of the file holding the reference
Z
Zheng Yan 已提交
468 469 470 471
 * - number of references holding by parent node (alway 1 for tree blocks)
 *
 * Btree leaf may hold multiple references to a file extent. In most cases,
 * these references are from same file and the corresponding offsets inside
472
 * the file are close together.
473 474
 *
 * When a file extent is allocated the fields are filled in:
475
 *     (root_key.objectid, trans->transid, inode objectid, 1)
476 477
 *
 * When a leaf is cow'd new references are added for every file extent found
Z
Zheng Yan 已提交
478 479
 * in the leaf.  It looks similar to the create case, but trans->transid will
 * be different when the block is cow'd.
480
 *
481
 *     (root_key.objectid, trans->transid, inode objectid,
Z
Zheng Yan 已提交
482
 *      number of references in the leaf)
483
 *
484 485 486
 * When a file extent is removed either during snapshot deletion or
 * file truncation, we find the corresponding back reference and check
 * the following fields:
487
 *
488 489
 *     (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
 *      inode objectid)
490 491 492 493 494 495 496 497
 *
 * Btree extents can be referenced by:
 *
 * - Different subvolumes
 * - Different generations of the same subvolume
 *
 * When a tree block is created, back references are inserted:
 *
498
 * (root->root_key.objectid, trans->transid, level, 1)
499
 *
Z
Zheng Yan 已提交
500 501 502 503
 * When a tree block is cow'd, new back references are added for all the
 * blocks it points to. If the tree block isn't in reference counted root,
 * the old back references are removed. These new back references are of
 * the form (trans->transid will have increased since creation):
504
 *
505
 * (root->root_key.objectid, trans->transid, level, 1)
506
 *
Z
Zheng Yan 已提交
507
 * When a backref is in deleting, the following fields are checked:
508 509
 *
 * if backref was for a tree root:
510
 *     (btrfs_header_owner(itself), btrfs_header_generation(itself), level)
511
 * else
512
 *     (btrfs_header_owner(parent), btrfs_header_generation(parent), level)
513
 *
Z
Zheng Yan 已提交
514
 * Back Reference Key composing:
515
 *
Z
Zheng Yan 已提交
516 517 518 519
 * The key objectid corresponds to the first byte in the extent, the key
 * type is set to BTRFS_EXTENT_REF_KEY, and the key offset is the first
 * byte of parent extent. If a extent is tree root, the key offset is set
 * to the key objectid.
520
 */
Z
Zheng Yan 已提交
521

C
Chris Mason 已提交
522
static noinline int lookup_extent_backref(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
523
					  struct btrfs_root *root,
524 525 526 527
					  struct btrfs_path *path,
					  u64 bytenr, u64 parent,
					  u64 ref_root, u64 ref_generation,
					  u64 owner_objectid, int del)
528 529
{
	struct btrfs_key key;
Z
Zheng Yan 已提交
530 531
	struct btrfs_extent_ref *ref;
	struct extent_buffer *leaf;
532
	u64 ref_objectid;
533 534
	int ret;

Z
Zheng Yan 已提交
535 536 537 538 539 540 541 542 543 544 545 546 547 548
	key.objectid = bytenr;
	key.type = BTRFS_EXTENT_REF_KEY;
	key.offset = parent;

	ret = btrfs_search_slot(trans, root, &key, path, del ? -1 : 0, 1);
	if (ret < 0)
		goto out;
	if (ret > 0) {
		ret = -ENOENT;
		goto out;
	}

	leaf = path->nodes[0];
	ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
549
	ref_objectid = btrfs_ref_objectid(leaf, ref);
Z
Zheng Yan 已提交
550
	if (btrfs_ref_root(leaf, ref) != ref_root ||
551 552 553
	    btrfs_ref_generation(leaf, ref) != ref_generation ||
	    (ref_objectid != owner_objectid &&
	     ref_objectid != BTRFS_MULTIPLE_OBJECTIDS)) {
Z
Zheng Yan 已提交
554 555 556 557 558 559 560 561 562
		ret = -EIO;
		WARN_ON(1);
		goto out;
	}
	ret = 0;
out:
	return ret;
}

C
Chris Mason 已提交
563
static noinline int insert_extent_backref(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
564 565 566 567
					  struct btrfs_root *root,
					  struct btrfs_path *path,
					  u64 bytenr, u64 parent,
					  u64 ref_root, u64 ref_generation,
568 569
					  u64 owner_objectid,
					  int refs_to_add)
Z
Zheng Yan 已提交
570 571 572 573 574 575
{
	struct btrfs_key key;
	struct extent_buffer *leaf;
	struct btrfs_extent_ref *ref;
	u32 num_refs;
	int ret;
576 577 578

	key.objectid = bytenr;
	key.type = BTRFS_EXTENT_REF_KEY;
Z
Zheng Yan 已提交
579
	key.offset = parent;
580

Z
Zheng Yan 已提交
581 582 583 584 585 586 587 588
	ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*ref));
	if (ret == 0) {
		leaf = path->nodes[0];
		ref = btrfs_item_ptr(leaf, path->slots[0],
				     struct btrfs_extent_ref);
		btrfs_set_ref_root(leaf, ref, ref_root);
		btrfs_set_ref_generation(leaf, ref, ref_generation);
		btrfs_set_ref_objectid(leaf, ref, owner_objectid);
589
		btrfs_set_ref_num_refs(leaf, ref, refs_to_add);
Z
Zheng Yan 已提交
590 591
	} else if (ret == -EEXIST) {
		u64 existing_owner;
592

Z
Zheng Yan 已提交
593 594 595 596 597 598 599 600
		BUG_ON(owner_objectid < BTRFS_FIRST_FREE_OBJECTID);
		leaf = path->nodes[0];
		ref = btrfs_item_ptr(leaf, path->slots[0],
				     struct btrfs_extent_ref);
		if (btrfs_ref_root(leaf, ref) != ref_root ||
		    btrfs_ref_generation(leaf, ref) != ref_generation) {
			ret = -EIO;
			WARN_ON(1);
601
			goto out;
Z
Zheng Yan 已提交
602 603 604 605
		}

		num_refs = btrfs_ref_num_refs(leaf, ref);
		BUG_ON(num_refs == 0);
606
		btrfs_set_ref_num_refs(leaf, ref, num_refs + refs_to_add);
Z
Zheng Yan 已提交
607 608

		existing_owner = btrfs_ref_objectid(leaf, ref);
609 610
		if (existing_owner != owner_objectid &&
		    existing_owner != BTRFS_MULTIPLE_OBJECTIDS) {
Z
Zheng Yan 已提交
611 612 613 614 615
			btrfs_set_ref_objectid(leaf, ref,
					BTRFS_MULTIPLE_OBJECTIDS);
		}
		ret = 0;
	} else {
616
		goto out;
Z
Zheng Yan 已提交
617
	}
618
	btrfs_unlock_up_safe(path, 1);
619 620 621 622
	btrfs_mark_buffer_dirty(path->nodes[0]);
out:
	btrfs_release_path(root, path);
	return ret;
623 624
}

C
Chris Mason 已提交
625
static noinline int remove_extent_backref(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
626
					  struct btrfs_root *root,
627 628
					  struct btrfs_path *path,
					  int refs_to_drop)
Z
Zheng Yan 已提交
629 630 631 632 633 634 635 636 637
{
	struct extent_buffer *leaf;
	struct btrfs_extent_ref *ref;
	u32 num_refs;
	int ret = 0;

	leaf = path->nodes[0];
	ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
	num_refs = btrfs_ref_num_refs(leaf, ref);
638 639
	BUG_ON(num_refs < refs_to_drop);
	num_refs -= refs_to_drop;
Z
Zheng Yan 已提交
640 641 642 643 644 645 646 647 648 649
	if (num_refs == 0) {
		ret = btrfs_del_item(trans, root, path);
	} else {
		btrfs_set_ref_num_refs(leaf, ref, num_refs);
		btrfs_mark_buffer_dirty(leaf);
	}
	btrfs_release_path(root, path);
	return ret;
}

C
Chris Mason 已提交
650
#ifdef BIO_RW_DISCARD
651 652 653 654 655
static void btrfs_issue_discard(struct block_device *bdev,
				u64 start, u64 len)
{
	blkdev_issue_discard(bdev, start >> 9, len >> 9, GFP_KERNEL);
}
C
Chris Mason 已提交
656
#endif
657

658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689
static int btrfs_discard_extent(struct btrfs_root *root, u64 bytenr,
				u64 num_bytes)
{
#ifdef BIO_RW_DISCARD
	int ret;
	u64 map_length = num_bytes;
	struct btrfs_multi_bio *multi = NULL;

	/* Tell the block device(s) that the sectors can be discarded */
	ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
			      bytenr, &map_length, &multi, 0);
	if (!ret) {
		struct btrfs_bio_stripe *stripe = multi->stripes;
		int i;

		if (map_length > num_bytes)
			map_length = num_bytes;

		for (i = 0; i < multi->num_stripes; i++, stripe++) {
			btrfs_issue_discard(stripe->dev->bdev,
					    stripe->physical,
					    map_length);
		}
		kfree(multi);
	}

	return ret;
#else
	return 0;
#endif
}

Z
Zheng Yan 已提交
690 691
static int __btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
				     struct btrfs_root *root, u64 bytenr,
692
				     u64 num_bytes,
Z
Zheng Yan 已提交
693 694 695
				     u64 orig_parent, u64 parent,
				     u64 orig_root, u64 ref_root,
				     u64 orig_generation, u64 ref_generation,
696
				     u64 owner_objectid)
Z
Zheng Yan 已提交
697 698
{
	int ret;
699
	int pin = owner_objectid < BTRFS_FIRST_FREE_OBJECTID;
Z
Zheng Yan 已提交
700

701 702 703 704
	ret = btrfs_update_delayed_ref(trans, bytenr, num_bytes,
				       orig_parent, parent, orig_root,
				       ref_root, orig_generation,
				       ref_generation, owner_objectid, pin);
Z
Zheng Yan 已提交
705 706 707 708 709 710
	BUG_ON(ret);
	return ret;
}

int btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
			    struct btrfs_root *root, u64 bytenr,
711
			    u64 num_bytes, u64 orig_parent, u64 parent,
Z
Zheng Yan 已提交
712
			    u64 ref_root, u64 ref_generation,
713
			    u64 owner_objectid)
Z
Zheng Yan 已提交
714 715 716 717 718
{
	int ret;
	if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
	    owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
		return 0;
719 720 721 722 723

	ret = __btrfs_update_extent_ref(trans, root, bytenr, num_bytes,
					orig_parent, parent, ref_root,
					ref_root, ref_generation,
					ref_generation, owner_objectid);
Z
Zheng Yan 已提交
724 725
	return ret;
}
726
static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
727
				  struct btrfs_root *root, u64 bytenr,
728
				  u64 num_bytes,
Z
Zheng Yan 已提交
729 730 731
				  u64 orig_parent, u64 parent,
				  u64 orig_root, u64 ref_root,
				  u64 orig_generation, u64 ref_generation,
732
				  u64 owner_objectid)
733 734 735 736 737 738 739 740 741 742 743 744 745 746 747
{
	int ret;

	ret = btrfs_add_delayed_ref(trans, bytenr, num_bytes, parent, ref_root,
				    ref_generation, owner_objectid,
				    BTRFS_ADD_DELAYED_REF, 0);
	BUG_ON(ret);
	return ret;
}

static noinline_for_stack int add_extent_ref(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root, u64 bytenr,
			  u64 num_bytes, u64 parent, u64 ref_root,
			  u64 ref_generation, u64 owner_objectid,
			  int refs_to_add)
C
Chris Mason 已提交
748
{
749
	struct btrfs_path *path;
C
Chris Mason 已提交
750
	int ret;
C
Chris Mason 已提交
751
	struct btrfs_key key;
752
	struct extent_buffer *l;
C
Chris Mason 已提交
753
	struct btrfs_extent_item *item;
C
Chris Mason 已提交
754
	u32 refs;
C
Chris Mason 已提交
755

756
	path = btrfs_alloc_path();
757 758
	if (!path)
		return -ENOMEM;
759

760
	path->reada = 1;
761
	path->leave_spinning = 1;
762
	key.objectid = bytenr;
Z
Zheng Yan 已提交
763
	key.type = BTRFS_EXTENT_ITEM_KEY;
764
	key.offset = num_bytes;
Z
Zheng Yan 已提交
765

766 767 768
	/* first find the extent item and update its reference count */
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key,
				path, 0, 1);
769 770
	if (ret < 0) {
		btrfs_set_path_blocking(path);
771
		return ret;
772
	}
Z
Zheng Yan 已提交
773

774 775 776 777 778
	if (ret > 0) {
		WARN_ON(1);
		btrfs_free_path(path);
		return -EIO;
	}
779
	l = path->nodes[0];
Z
Zheng Yan 已提交
780 781

	btrfs_item_key_to_cpu(l, &key, path->slots[0]);
782 783
	if (key.objectid != bytenr) {
		btrfs_print_leaf(root->fs_info->extent_root, path->nodes[0]);
C
Chris Mason 已提交
784 785 786
		printk(KERN_ERR "btrfs wanted %llu found %llu\n",
		       (unsigned long long)bytenr,
		       (unsigned long long)key.objectid);
787 788
		BUG();
	}
Z
Zheng Yan 已提交
789 790
	BUG_ON(key.type != BTRFS_EXTENT_ITEM_KEY);

791 792 793 794
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);

	refs = btrfs_extent_refs(l, item);
	btrfs_set_extent_refs(l, item, refs + refs_to_add);
795 796
	btrfs_unlock_up_safe(path, 1);

797 798 799 800 801
	btrfs_mark_buffer_dirty(path->nodes[0]);

	btrfs_release_path(root->fs_info->extent_root, path);

	path->reada = 1;
802 803
	path->leave_spinning = 1;

804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933
	/* now insert the actual backref */
	ret = insert_extent_backref(trans, root->fs_info->extent_root,
				    path, bytenr, parent,
				    ref_root, ref_generation,
				    owner_objectid, refs_to_add);
	BUG_ON(ret);
	btrfs_free_path(path);
	return 0;
}

int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root,
			 u64 bytenr, u64 num_bytes, u64 parent,
			 u64 ref_root, u64 ref_generation,
			 u64 owner_objectid)
{
	int ret;
	if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
	    owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
		return 0;

	ret = __btrfs_inc_extent_ref(trans, root, bytenr, num_bytes, 0, parent,
				     0, ref_root, 0, ref_generation,
				     owner_objectid);
	return ret;
}

static int drop_delayed_ref(struct btrfs_trans_handle *trans,
					struct btrfs_root *root,
					struct btrfs_delayed_ref_node *node)
{
	int ret = 0;
	struct btrfs_delayed_ref *ref = btrfs_delayed_node_to_ref(node);

	BUG_ON(node->ref_mod == 0);
	ret = __btrfs_free_extent(trans, root, node->bytenr, node->num_bytes,
				  node->parent, ref->root, ref->generation,
				  ref->owner_objectid, ref->pin, node->ref_mod);

	return ret;
}

/* helper function to actually process a single delayed ref entry */
static noinline int run_one_delayed_ref(struct btrfs_trans_handle *trans,
					struct btrfs_root *root,
					struct btrfs_delayed_ref_node *node,
					int insert_reserved)
{
	int ret;
	struct btrfs_delayed_ref *ref;

	if (node->parent == (u64)-1) {
		struct btrfs_delayed_ref_head *head;
		/*
		 * we've hit the end of the chain and we were supposed
		 * to insert this extent into the tree.  But, it got
		 * deleted before we ever needed to insert it, so all
		 * we have to do is clean up the accounting
		 */
		if (insert_reserved) {
			update_reserved_extents(root, node->bytenr,
						node->num_bytes, 0);
		}
		head = btrfs_delayed_node_to_head(node);
		mutex_unlock(&head->mutex);
		return 0;
	}

	ref = btrfs_delayed_node_to_ref(node);
	if (ref->action == BTRFS_ADD_DELAYED_REF) {
		if (insert_reserved) {
			struct btrfs_key ins;

			ins.objectid = node->bytenr;
			ins.offset = node->num_bytes;
			ins.type = BTRFS_EXTENT_ITEM_KEY;

			/* record the full extent allocation */
			ret = __btrfs_alloc_reserved_extent(trans, root,
					node->parent, ref->root,
					ref->generation, ref->owner_objectid,
					&ins, node->ref_mod);
			update_reserved_extents(root, node->bytenr,
						node->num_bytes, 0);
		} else {
			/* just add one backref */
			ret = add_extent_ref(trans, root, node->bytenr,
				     node->num_bytes,
				     node->parent, ref->root, ref->generation,
				     ref->owner_objectid, node->ref_mod);
		}
		BUG_ON(ret);
	} else if (ref->action == BTRFS_DROP_DELAYED_REF) {
		WARN_ON(insert_reserved);
		ret = drop_delayed_ref(trans, root, node);
	}
	return 0;
}

static noinline struct btrfs_delayed_ref_node *
select_delayed_ref(struct btrfs_delayed_ref_head *head)
{
	struct rb_node *node;
	struct btrfs_delayed_ref_node *ref;
	int action = BTRFS_ADD_DELAYED_REF;
again:
	/*
	 * select delayed ref of type BTRFS_ADD_DELAYED_REF first.
	 * this prevents ref count from going down to zero when
	 * there still are pending delayed ref.
	 */
	node = rb_prev(&head->node.rb_node);
	while (1) {
		if (!node)
			break;
		ref = rb_entry(node, struct btrfs_delayed_ref_node,
				rb_node);
		if (ref->bytenr != head->node.bytenr)
			break;
		if (btrfs_delayed_node_to_ref(ref)->action == action)
			return ref;
		node = rb_prev(node);
	}
	if (action == BTRFS_ADD_DELAYED_REF) {
		action = BTRFS_DROP_DELAYED_REF;
		goto again;
	}
	return NULL;
}

934 935 936
static noinline int run_clustered_refs(struct btrfs_trans_handle *trans,
				       struct btrfs_root *root,
				       struct list_head *cluster)
937 938 939 940 941
{
	struct btrfs_delayed_ref_root *delayed_refs;
	struct btrfs_delayed_ref_node *ref;
	struct btrfs_delayed_ref_head *locked_ref = NULL;
	int ret;
942
	int count = 0;
943 944 945 946 947
	int must_insert_reserved = 0;

	delayed_refs = &trans->transaction->delayed_refs;
	while (1) {
		if (!locked_ref) {
948 949
			/* pick a new head ref from the cluster list */
			if (list_empty(cluster))
950 951
				break;

952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968
			locked_ref = list_entry(cluster->next,
				     struct btrfs_delayed_ref_head, cluster);

			/* grab the lock that says we are going to process
			 * all the refs for this head */
			ret = btrfs_delayed_ref_lock(trans, locked_ref);

			/*
			 * we may have dropped the spin lock to get the head
			 * mutex lock, and that might have given someone else
			 * time to free the head.  If that's true, it has been
			 * removed from our list and we can move on.
			 */
			if (ret == -EAGAIN) {
				locked_ref = NULL;
				count++;
				continue;
969 970
			}
		}
971

972 973 974 975 976 977
		/*
		 * record the must insert reserved flag before we
		 * drop the spin lock.
		 */
		must_insert_reserved = locked_ref->must_insert_reserved;
		locked_ref->must_insert_reserved = 0;
978

979 980 981 982 983 984 985 986 987 988 989
		/*
		 * locked_ref is the head node, so we have to go one
		 * node back for any delayed ref updates
		 */
		ref = select_delayed_ref(locked_ref);
		if (!ref) {
			/* All delayed refs have been processed, Go ahead
			 * and send the head node to run_one_delayed_ref,
			 * so that any accounting fixes can happen
			 */
			ref = &locked_ref->node;
990
			list_del_init(&locked_ref->cluster);
991 992
			locked_ref = NULL;
		}
C
Chris Mason 已提交
993

994 995 996 997
		ref->in_tree = 0;
		rb_erase(&ref->rb_node, &delayed_refs->root);
		delayed_refs->num_entries--;
		spin_unlock(&delayed_refs->lock);
998

999 1000 1001 1002
		ret = run_one_delayed_ref(trans, root, ref,
					  must_insert_reserved);
		BUG_ON(ret);
		btrfs_put_delayed_ref(ref);
1003

1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043
		count++;
		cond_resched();
		spin_lock(&delayed_refs->lock);
	}
	return count;
}

/*
 * this starts processing the delayed reference count updates and
 * extent insertions we have queued up so far.  count can be
 * 0, which means to process everything in the tree at the start
 * of the run (but not newly added entries), or it can be some target
 * number you'd like to process.
 */
int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root, unsigned long count)
{
	struct rb_node *node;
	struct btrfs_delayed_ref_root *delayed_refs;
	struct btrfs_delayed_ref_node *ref;
	struct list_head cluster;
	int ret;
	int run_all = count == (unsigned long)-1;
	int run_most = 0;

	if (root == root->fs_info->extent_root)
		root = root->fs_info->tree_root;

	delayed_refs = &trans->transaction->delayed_refs;
	INIT_LIST_HEAD(&cluster);
again:
	spin_lock(&delayed_refs->lock);
	if (count == 0) {
		count = delayed_refs->num_entries * 2;
		run_most = 1;
	}
	while (1) {
		if (!(run_all || run_most) &&
		    delayed_refs->num_heads_ready < 64)
			break;
1044

1045
		/*
1046 1047 1048 1049
		 * go find something we can process in the rbtree.  We start at
		 * the beginning of the tree, and then build a cluster
		 * of refs to process starting at the first one we are able to
		 * lock
1050
		 */
1051 1052 1053
		ret = btrfs_find_ref_cluster(trans, &cluster,
					     delayed_refs->run_delayed_start);
		if (ret)
1054 1055
			break;

1056 1057 1058 1059 1060 1061 1062
		ret = run_clustered_refs(trans, root, &cluster);
		BUG_ON(ret < 0);

		count -= min_t(unsigned long, ret, count);

		if (count == 0)
			break;
1063
	}
1064

1065 1066
	if (run_all) {
		node = rb_first(&delayed_refs->root);
1067
		if (!node)
1068
			goto out;
1069
		count = (unsigned long)-1;
1070

1071 1072 1073 1074 1075
		while (node) {
			ref = rb_entry(node, struct btrfs_delayed_ref_node,
				       rb_node);
			if (btrfs_delayed_ref_is_head(ref)) {
				struct btrfs_delayed_ref_head *head;
1076

1077 1078 1079 1080 1081 1082 1083 1084
				head = btrfs_delayed_node_to_head(ref);
				atomic_inc(&ref->refs);

				spin_unlock(&delayed_refs->lock);
				mutex_lock(&head->mutex);
				mutex_unlock(&head->mutex);

				btrfs_put_delayed_ref(ref);
1085
				cond_resched();
1086 1087 1088 1089 1090 1091 1092
				goto again;
			}
			node = rb_next(node);
		}
		spin_unlock(&delayed_refs->lock);
		schedule_timeout(1);
		goto again;
1093
	}
1094
out:
1095
	spin_unlock(&delayed_refs->lock);
1096 1097 1098
	return 0;
}

Y
Yan Zheng 已提交
1099
int btrfs_cross_ref_exist(struct btrfs_trans_handle *trans,
1100
			  struct btrfs_root *root, u64 objectid, u64 bytenr)
1101 1102 1103
{
	struct btrfs_root *extent_root = root->fs_info->extent_root;
	struct btrfs_path *path;
1104 1105 1106 1107
	struct extent_buffer *leaf;
	struct btrfs_extent_ref *ref_item;
	struct btrfs_key key;
	struct btrfs_key found_key;
Y
Yan Zheng 已提交
1108 1109
	u64 ref_root;
	u64 last_snapshot;
1110 1111
	u32 nritems;
	int ret;
1112

1113
	key.objectid = bytenr;
Z
Zheng Yan 已提交
1114
	key.offset = (u64)-1;
1115
	key.type = BTRFS_EXTENT_ITEM_KEY;
1116

1117
	path = btrfs_alloc_path();
1118 1119 1120 1121
	ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
	if (ret < 0)
		goto out;
	BUG_ON(ret == 0);
Y
Yan Zheng 已提交
1122 1123 1124

	ret = -ENOENT;
	if (path->slots[0] == 0)
Z
Zheng Yan 已提交
1125
		goto out;
1126

Z
Zheng Yan 已提交
1127
	path->slots[0]--;
1128 1129
	leaf = path->nodes[0];
	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1130 1131

	if (found_key.objectid != bytenr ||
Y
Yan Zheng 已提交
1132
	    found_key.type != BTRFS_EXTENT_ITEM_KEY)
1133
		goto out;
1134

Y
Yan Zheng 已提交
1135
	last_snapshot = btrfs_root_last_snapshot(&root->root_item);
1136
	while (1) {
1137 1138
		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
1139 1140
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(extent_root, path);
1141 1142
			if (ret < 0)
				goto out;
1143 1144 1145 1146
			if (ret == 0)
				continue;
			break;
		}
1147
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1148 1149
		if (found_key.objectid != bytenr)
			break;
1150

1151 1152 1153 1154 1155
		if (found_key.type != BTRFS_EXTENT_REF_KEY) {
			path->slots[0]++;
			continue;
		}

1156
		ref_item = btrfs_item_ptr(leaf, path->slots[0],
1157
					  struct btrfs_extent_ref);
Y
Yan Zheng 已提交
1158
		ref_root = btrfs_ref_root(leaf, ref_item);
1159 1160 1161
		if ((ref_root != root->root_key.objectid &&
		     ref_root != BTRFS_TREE_LOG_OBJECTID) ||
		     objectid != btrfs_ref_objectid(leaf, ref_item)) {
Y
Yan Zheng 已提交
1162
			ret = 1;
1163
			goto out;
Y
Yan Zheng 已提交
1164 1165
		}
		if (btrfs_ref_generation(leaf, ref_item) <= last_snapshot) {
1166 1167 1168
			ret = 1;
			goto out;
		}
Y
Yan Zheng 已提交
1169 1170

		path->slots[0]++;
1171 1172
	}
	ret = 0;
1173
out:
Y
Yan Zheng 已提交
1174
	btrfs_free_path(path);
1175
	return ret;
1176
}
C
Chris Mason 已提交
1177

Z
Zheng Yan 已提交
1178 1179
int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		    struct extent_buffer *buf, u32 nr_extents)
C
Chris Mason 已提交
1180
{
1181
	struct btrfs_key key;
1182
	struct btrfs_file_extent_item *fi;
Z
Zheng Yan 已提交
1183 1184
	u64 root_gen;
	u32 nritems;
C
Chris Mason 已提交
1185
	int i;
1186
	int level;
Z
Zheng Yan 已提交
1187
	int ret = 0;
Z
Zheng Yan 已提交
1188
	int shared = 0;
1189

1190
	if (!root->ref_cows)
1191
		return 0;
1192

Z
Zheng Yan 已提交
1193 1194 1195 1196 1197 1198 1199 1200
	if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
		shared = 0;
		root_gen = root->root_key.offset;
	} else {
		shared = 1;
		root_gen = trans->transid - 1;
	}

1201
	level = btrfs_header_level(buf);
1202
	nritems = btrfs_header_nritems(buf);
C
Chris Mason 已提交
1203

Z
Zheng Yan 已提交
1204
	if (level == 0) {
Y
Yan Zheng 已提交
1205 1206 1207
		struct btrfs_leaf_ref *ref;
		struct btrfs_extent_info *info;

Z
Zheng Yan 已提交
1208
		ref = btrfs_alloc_leaf_ref(root, nr_extents);
Y
Yan Zheng 已提交
1209
		if (!ref) {
Z
Zheng Yan 已提交
1210
			ret = -ENOMEM;
Y
Yan Zheng 已提交
1211 1212 1213
			goto out;
		}

Z
Zheng Yan 已提交
1214
		ref->root_gen = root_gen;
Y
Yan Zheng 已提交
1215 1216 1217
		ref->bytenr = buf->start;
		ref->owner = btrfs_header_owner(buf);
		ref->generation = btrfs_header_generation(buf);
Z
Zheng Yan 已提交
1218
		ref->nritems = nr_extents;
Y
Yan Zheng 已提交
1219
		info = ref->extents;
1220

Z
Zheng Yan 已提交
1221
		for (i = 0; nr_extents > 0 && i < nritems; i++) {
Y
Yan Zheng 已提交
1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242
			u64 disk_bytenr;
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
				continue;
			fi = btrfs_item_ptr(buf, i,
					    struct btrfs_file_extent_item);
			if (btrfs_file_extent_type(buf, fi) ==
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
				continue;

			info->bytenr = disk_bytenr;
			info->num_bytes =
				btrfs_file_extent_disk_num_bytes(buf, fi);
			info->objectid = key.objectid;
			info->offset = key.offset;
			info++;
		}

Z
Zheng Yan 已提交
1243
		ret = btrfs_add_leaf_ref(root, ref, shared);
Y
Yan Zheng 已提交
1244 1245 1246 1247 1248 1249 1250 1251
		if (ret == -EEXIST && shared) {
			struct btrfs_leaf_ref *old;
			old = btrfs_lookup_leaf_ref(root, ref->bytenr);
			BUG_ON(!old);
			btrfs_remove_leaf_ref(root, old);
			btrfs_free_leaf_ref(root, old);
			ret = btrfs_add_leaf_ref(root, ref, shared);
		}
Y
Yan Zheng 已提交
1252
		WARN_ON(ret);
1253
		btrfs_free_leaf_ref(root, ref);
Y
Yan Zheng 已提交
1254 1255
	}
out:
Z
Zheng Yan 已提交
1256 1257 1258
	return ret;
}

1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269
/* when a block goes through cow, we update the reference counts of
 * everything that block points to.  The internal pointers of the block
 * can be in just about any order, and it is likely to have clusters of
 * things that are close together and clusters of things that are not.
 *
 * To help reduce the seeks that come with updating all of these reference
 * counts, sort them by byte number before actual updates are done.
 *
 * struct refsort is used to match byte number to slot in the btree block.
 * we sort based on the byte number and then use the slot to actually
 * find the item.
1270 1271 1272 1273 1274
 *
 * struct refsort is smaller than strcut btrfs_item and smaller than
 * struct btrfs_key_ptr.  Since we're currently limited to the page size
 * for a btree block, there's no way for a kmalloc of refsorts for a
 * single node to be bigger than a page.
1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300
 */
struct refsort {
	u64 bytenr;
	u32 slot;
};

/*
 * for passing into sort()
 */
static int refsort_cmp(const void *a_void, const void *b_void)
{
	const struct refsort *a = a_void;
	const struct refsort *b = b_void;

	if (a->bytenr < b->bytenr)
		return -1;
	if (a->bytenr > b->bytenr)
		return 1;
	return 0;
}


noinline int btrfs_inc_ref(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root,
			   struct extent_buffer *orig_buf,
			   struct extent_buffer *buf, u32 *nr_extents)
Z
Zheng Yan 已提交
1301 1302 1303 1304 1305 1306
{
	u64 bytenr;
	u64 ref_root;
	u64 orig_root;
	u64 ref_generation;
	u64 orig_generation;
1307
	struct refsort *sorted;
Z
Zheng Yan 已提交
1308 1309 1310 1311 1312 1313 1314 1315
	u32 nritems;
	u32 nr_file_extents = 0;
	struct btrfs_key key;
	struct btrfs_file_extent_item *fi;
	int i;
	int level;
	int ret = 0;
	int faili = 0;
1316 1317
	int refi = 0;
	int slot;
Z
Zheng Yan 已提交
1318
	int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
1319
			    u64, u64, u64, u64, u64, u64, u64, u64, u64);
Z
Zheng Yan 已提交
1320 1321 1322 1323 1324 1325 1326 1327 1328

	ref_root = btrfs_header_owner(buf);
	ref_generation = btrfs_header_generation(buf);
	orig_root = btrfs_header_owner(orig_buf);
	orig_generation = btrfs_header_generation(orig_buf);

	nritems = btrfs_header_nritems(buf);
	level = btrfs_header_level(buf);

1329 1330 1331
	sorted = kmalloc(sizeof(struct refsort) * nritems, GFP_NOFS);
	BUG_ON(!sorted);

Z
Zheng Yan 已提交
1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343
	if (root->ref_cows) {
		process_func = __btrfs_inc_extent_ref;
	} else {
		if (level == 0 &&
		    root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
			goto out;
		if (level != 0 &&
		    root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
			goto out;
		process_func = __btrfs_update_extent_ref;
	}

1344 1345 1346 1347 1348
	/*
	 * we make two passes through the items.  In the first pass we
	 * only record the byte number and slot.  Then we sort based on
	 * byte number and do the actual work based on the sorted results
	 */
Z
Zheng Yan 已提交
1349 1350
	for (i = 0; i < nritems; i++) {
		cond_resched();
1351
		if (level == 0) {
1352 1353
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1354
				continue;
1355
			fi = btrfs_item_ptr(buf, i,
1356
					    struct btrfs_file_extent_item);
1357
			if (btrfs_file_extent_type(buf, fi) ==
1358 1359
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
Z
Zheng Yan 已提交
1360 1361
			bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (bytenr == 0)
1362
				continue;
Z
Zheng Yan 已提交
1363 1364

			nr_file_extents++;
1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390
			sorted[refi].bytenr = bytenr;
			sorted[refi].slot = i;
			refi++;
		} else {
			bytenr = btrfs_node_blockptr(buf, i);
			sorted[refi].bytenr = bytenr;
			sorted[refi].slot = i;
			refi++;
		}
	}
	/*
	 * if refi == 0, we didn't actually put anything into the sorted
	 * array and we're done
	 */
	if (refi == 0)
		goto out;

	sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);

	for (i = 0; i < refi; i++) {
		cond_resched();
		slot = sorted[i].slot;
		bytenr = sorted[i].bytenr;

		if (level == 0) {
			btrfs_item_key_to_cpu(buf, &key, slot);
1391 1392 1393 1394 1395 1396
			fi = btrfs_item_ptr(buf, slot,
					    struct btrfs_file_extent_item);

			bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (bytenr == 0)
				continue;
Z
Zheng Yan 已提交
1397 1398

			ret = process_func(trans, root, bytenr,
1399 1400 1401 1402 1403
				   btrfs_file_extent_disk_num_bytes(buf, fi),
				   orig_buf->start, buf->start,
				   orig_root, ref_root,
				   orig_generation, ref_generation,
				   key.objectid);
Z
Zheng Yan 已提交
1404 1405

			if (ret) {
1406
				faili = slot;
Z
Zheng Yan 已提交
1407 1408 1409
				WARN_ON(1);
				goto fail;
			}
1410
		} else {
1411
			ret = process_func(trans, root, bytenr, buf->len,
Z
Zheng Yan 已提交
1412 1413 1414
					   orig_buf->start, buf->start,
					   orig_root, ref_root,
					   orig_generation, ref_generation,
1415
					   level - 1);
Z
Zheng Yan 已提交
1416
			if (ret) {
1417
				faili = slot;
Z
Zheng Yan 已提交
1418 1419 1420
				WARN_ON(1);
				goto fail;
			}
1421 1422
		}
	}
Z
Zheng Yan 已提交
1423
out:
1424
	kfree(sorted);
Z
Zheng Yan 已提交
1425 1426 1427 1428 1429 1430 1431 1432
	if (nr_extents) {
		if (level == 0)
			*nr_extents = nr_file_extents;
		else
			*nr_extents = nritems;
	}
	return 0;
fail:
1433
	kfree(sorted);
Z
Zheng Yan 已提交
1434
	WARN_ON(1);
1435
	return ret;
C
Chris Mason 已提交
1436 1437
}

Z
Zheng Yan 已提交
1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487
int btrfs_update_ref(struct btrfs_trans_handle *trans,
		     struct btrfs_root *root, struct extent_buffer *orig_buf,
		     struct extent_buffer *buf, int start_slot, int nr)

{
	u64 bytenr;
	u64 ref_root;
	u64 orig_root;
	u64 ref_generation;
	u64 orig_generation;
	struct btrfs_key key;
	struct btrfs_file_extent_item *fi;
	int i;
	int ret;
	int slot;
	int level;

	BUG_ON(start_slot < 0);
	BUG_ON(start_slot + nr > btrfs_header_nritems(buf));

	ref_root = btrfs_header_owner(buf);
	ref_generation = btrfs_header_generation(buf);
	orig_root = btrfs_header_owner(orig_buf);
	orig_generation = btrfs_header_generation(orig_buf);
	level = btrfs_header_level(buf);

	if (!root->ref_cows) {
		if (level == 0 &&
		    root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
			return 0;
		if (level != 0 &&
		    root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
			return 0;
	}

	for (i = 0, slot = start_slot; i < nr; i++, slot++) {
		cond_resched();
		if (level == 0) {
			btrfs_item_key_to_cpu(buf, &key, slot);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
				continue;
			fi = btrfs_item_ptr(buf, slot,
					    struct btrfs_file_extent_item);
			if (btrfs_file_extent_type(buf, fi) ==
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
			bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (bytenr == 0)
				continue;
			ret = __btrfs_update_extent_ref(trans, root, bytenr,
1488 1489 1490 1491
				    btrfs_file_extent_disk_num_bytes(buf, fi),
				    orig_buf->start, buf->start,
				    orig_root, ref_root, orig_generation,
				    ref_generation, key.objectid);
Z
Zheng Yan 已提交
1492 1493 1494 1495 1496
			if (ret)
				goto fail;
		} else {
			bytenr = btrfs_node_blockptr(buf, slot);
			ret = __btrfs_update_extent_ref(trans, root, bytenr,
1497 1498
					    buf->len, orig_buf->start,
					    buf->start, orig_root, ref_root,
Z
Zheng Yan 已提交
1499
					    orig_generation, ref_generation,
1500
					    level - 1);
Z
Zheng Yan 已提交
1501 1502 1503 1504 1505 1506 1507 1508 1509 1510
			if (ret)
				goto fail;
		}
	}
	return 0;
fail:
	WARN_ON(1);
	return -1;
}

C
Chris Mason 已提交
1511 1512 1513 1514 1515 1516 1517
static int write_one_cache_group(struct btrfs_trans_handle *trans,
				 struct btrfs_root *root,
				 struct btrfs_path *path,
				 struct btrfs_block_group_cache *cache)
{
	int ret;
	struct btrfs_root *extent_root = root->fs_info->extent_root;
1518 1519
	unsigned long bi;
	struct extent_buffer *leaf;
C
Chris Mason 已提交
1520 1521

	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1522 1523
	if (ret < 0)
		goto fail;
C
Chris Mason 已提交
1524
	BUG_ON(ret);
1525 1526 1527 1528 1529

	leaf = path->nodes[0];
	bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
	write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
	btrfs_mark_buffer_dirty(leaf);
C
Chris Mason 已提交
1530
	btrfs_release_path(extent_root, path);
1531
fail:
C
Chris Mason 已提交
1532 1533 1534 1535 1536 1537
	if (ret)
		return ret;
	return 0;

}

1538 1539
int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root)
C
Chris Mason 已提交
1540
{
J
Josef Bacik 已提交
1541 1542
	struct btrfs_block_group_cache *cache, *entry;
	struct rb_node *n;
C
Chris Mason 已提交
1543 1544 1545
	int err = 0;
	int werr = 0;
	struct btrfs_path *path;
1546
	u64 last = 0;
C
Chris Mason 已提交
1547 1548 1549 1550 1551

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

C
Chris Mason 已提交
1552
	while (1) {
J
Josef Bacik 已提交
1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564
		cache = NULL;
		spin_lock(&root->fs_info->block_group_cache_lock);
		for (n = rb_first(&root->fs_info->block_group_cache_tree);
		     n; n = rb_next(n)) {
			entry = rb_entry(n, struct btrfs_block_group_cache,
					 cache_node);
			if (entry->dirty) {
				cache = entry;
				break;
			}
		}
		spin_unlock(&root->fs_info->block_group_cache_lock);
1565

J
Josef Bacik 已提交
1566
		if (!cache)
1567
			break;
J
Josef Bacik 已提交
1568

1569
		cache->dirty = 0;
J
Josef Bacik 已提交
1570 1571
		last += cache->key.offset;

1572 1573 1574 1575 1576 1577 1578 1579 1580 1581
		err = write_one_cache_group(trans, root,
					    path, cache);
		/*
		 * if we fail to write the cache group, we want
		 * to keep it marked dirty in hopes that a later
		 * write will work
		 */
		if (err) {
			werr = err;
			continue;
C
Chris Mason 已提交
1582 1583 1584 1585 1586 1587
		}
	}
	btrfs_free_path(path);
	return werr;
}

1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600
int btrfs_extent_readonly(struct btrfs_root *root, u64 bytenr)
{
	struct btrfs_block_group_cache *block_group;
	int readonly = 0;

	block_group = btrfs_lookup_block_group(root->fs_info, bytenr);
	if (!block_group || block_group->ro)
		readonly = 1;
	if (block_group)
		put_block_group(block_group);
	return readonly;
}

1601 1602 1603 1604 1605 1606 1607 1608
static int update_space_info(struct btrfs_fs_info *info, u64 flags,
			     u64 total_bytes, u64 bytes_used,
			     struct btrfs_space_info **space_info)
{
	struct btrfs_space_info *found;

	found = __find_space_info(info, flags);
	if (found) {
1609
		spin_lock(&found->lock);
1610 1611
		found->total_bytes += total_bytes;
		found->bytes_used += bytes_used;
1612
		found->full = 0;
1613
		spin_unlock(&found->lock);
1614 1615 1616
		*space_info = found;
		return 0;
	}
Y
Yan Zheng 已提交
1617
	found = kzalloc(sizeof(*found), GFP_NOFS);
1618 1619 1620
	if (!found)
		return -ENOMEM;

J
Josef Bacik 已提交
1621
	INIT_LIST_HEAD(&found->block_groups);
1622
	init_rwsem(&found->groups_sem);
J
Josef Bacik 已提交
1623
	spin_lock_init(&found->lock);
1624 1625 1626 1627
	found->flags = flags;
	found->total_bytes = total_bytes;
	found->bytes_used = bytes_used;
	found->bytes_pinned = 0;
1628
	found->bytes_reserved = 0;
Y
Yan Zheng 已提交
1629
	found->bytes_readonly = 0;
J
Josef Bacik 已提交
1630
	found->bytes_delalloc = 0;
1631
	found->full = 0;
C
Chris Mason 已提交
1632
	found->force_alloc = 0;
1633
	*space_info = found;
1634
	list_add_rcu(&found->list, &info->space_info);
1635 1636 1637
	return 0;
}

1638 1639 1640
static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
{
	u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1641
				   BTRFS_BLOCK_GROUP_RAID1 |
C
Chris Mason 已提交
1642
				   BTRFS_BLOCK_GROUP_RAID10 |
1643
				   BTRFS_BLOCK_GROUP_DUP);
1644 1645 1646 1647 1648 1649 1650 1651 1652
	if (extra_flags) {
		if (flags & BTRFS_BLOCK_GROUP_DATA)
			fs_info->avail_data_alloc_bits |= extra_flags;
		if (flags & BTRFS_BLOCK_GROUP_METADATA)
			fs_info->avail_metadata_alloc_bits |= extra_flags;
		if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
			fs_info->avail_system_alloc_bits |= extra_flags;
	}
}
1653

Y
Yan Zheng 已提交
1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666
static void set_block_group_readonly(struct btrfs_block_group_cache *cache)
{
	spin_lock(&cache->space_info->lock);
	spin_lock(&cache->lock);
	if (!cache->ro) {
		cache->space_info->bytes_readonly += cache->key.offset -
					btrfs_block_group_used(&cache->item);
		cache->ro = 1;
	}
	spin_unlock(&cache->lock);
	spin_unlock(&cache->space_info->lock);
}

Y
Yan Zheng 已提交
1667
u64 btrfs_reduce_alloc_profile(struct btrfs_root *root, u64 flags)
1668
{
Y
Yan Zheng 已提交
1669
	u64 num_devices = root->fs_info->fs_devices->rw_devices;
1670 1671 1672 1673 1674 1675

	if (num_devices == 1)
		flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
	if (num_devices < 4)
		flags &= ~BTRFS_BLOCK_GROUP_RAID10;

1676 1677
	if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
	    (flags & (BTRFS_BLOCK_GROUP_RAID1 |
1678
		      BTRFS_BLOCK_GROUP_RAID10))) {
1679
		flags &= ~BTRFS_BLOCK_GROUP_DUP;
1680
	}
1681 1682

	if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
1683
	    (flags & BTRFS_BLOCK_GROUP_RAID10)) {
1684
		flags &= ~BTRFS_BLOCK_GROUP_RAID1;
1685
	}
1686 1687 1688 1689 1690 1691 1692 1693 1694

	if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
	    ((flags & BTRFS_BLOCK_GROUP_RAID1) |
	     (flags & BTRFS_BLOCK_GROUP_RAID10) |
	     (flags & BTRFS_BLOCK_GROUP_DUP)))
		flags &= ~BTRFS_BLOCK_GROUP_RAID0;
	return flags;
}

J
Josef Bacik 已提交
1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734
static u64 btrfs_get_alloc_profile(struct btrfs_root *root, u64 data)
{
	struct btrfs_fs_info *info = root->fs_info;
	u64 alloc_profile;

	if (data) {
		alloc_profile = info->avail_data_alloc_bits &
			info->data_alloc_profile;
		data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
	} else if (root == root->fs_info->chunk_root) {
		alloc_profile = info->avail_system_alloc_bits &
			info->system_alloc_profile;
		data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
	} else {
		alloc_profile = info->avail_metadata_alloc_bits &
			info->metadata_alloc_profile;
		data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
	}

	return btrfs_reduce_alloc_profile(root, data);
}

void btrfs_set_inode_space_info(struct btrfs_root *root, struct inode *inode)
{
	u64 alloc_target;

	alloc_target = btrfs_get_alloc_profile(root, 1);
	BTRFS_I(inode)->space_info = __find_space_info(root->fs_info,
						       alloc_target);
}

/*
 * for now this just makes sure we have at least 5% of our metadata space free
 * for use.
 */
int btrfs_check_metadata_free_space(struct btrfs_root *root)
{
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_space_info *meta_sinfo;
	u64 alloc_target, thresh;
1735
	int committed = 0, ret;
J
Josef Bacik 已提交
1736 1737 1738 1739 1740

	/* get the space info for where the metadata will live */
	alloc_target = btrfs_get_alloc_profile(root, 0);
	meta_sinfo = __find_space_info(info, alloc_target);

1741
again:
J
Josef Bacik 已提交
1742
	spin_lock(&meta_sinfo->lock);
1743 1744 1745 1746
	if (!meta_sinfo->full)
		thresh = meta_sinfo->total_bytes * 80;
	else
		thresh = meta_sinfo->total_bytes * 95;
J
Josef Bacik 已提交
1747 1748 1749 1750 1751

	do_div(thresh, 100);

	if (meta_sinfo->bytes_used + meta_sinfo->bytes_reserved +
	    meta_sinfo->bytes_pinned + meta_sinfo->bytes_readonly > thresh) {
1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765
		struct btrfs_trans_handle *trans;
		if (!meta_sinfo->full) {
			meta_sinfo->force_alloc = 1;
			spin_unlock(&meta_sinfo->lock);

			trans = btrfs_start_transaction(root, 1);
			if (!trans)
				return -ENOMEM;

			ret = do_chunk_alloc(trans, root->fs_info->extent_root,
					     2 * 1024 * 1024, alloc_target, 0);
			btrfs_end_transaction(trans, root);
			goto again;
		}
J
Josef Bacik 已提交
1766
		spin_unlock(&meta_sinfo->lock);
1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777

		if (!committed) {
			committed = 1;
			trans = btrfs_join_transaction(root, 1);
			if (!trans)
				return -ENOMEM;
			ret = btrfs_commit_transaction(trans, root);
			if (ret)
				return ret;
			goto again;
		}
J
Josef Bacik 已提交
1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792
		return -ENOSPC;
	}
	spin_unlock(&meta_sinfo->lock);

	return 0;
}

/*
 * This will check the space that the inode allocates from to make sure we have
 * enough space for bytes.
 */
int btrfs_check_data_free_space(struct btrfs_root *root, struct inode *inode,
				u64 bytes)
{
	struct btrfs_space_info *data_sinfo;
1793
	int ret = 0, committed = 0;
J
Josef Bacik 已提交
1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805

	/* make sure bytes are sectorsize aligned */
	bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);

	data_sinfo = BTRFS_I(inode)->space_info;
again:
	/* make sure we have enough space to handle the data first */
	spin_lock(&data_sinfo->lock);
	if (data_sinfo->total_bytes - data_sinfo->bytes_used -
	    data_sinfo->bytes_delalloc - data_sinfo->bytes_reserved -
	    data_sinfo->bytes_pinned - data_sinfo->bytes_readonly -
	    data_sinfo->bytes_may_use < bytes) {
1806 1807
		struct btrfs_trans_handle *trans;

J
Josef Bacik 已提交
1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831
		/*
		 * if we don't have enough free bytes in this space then we need
		 * to alloc a new chunk.
		 */
		if (!data_sinfo->full) {
			u64 alloc_target;

			data_sinfo->force_alloc = 1;
			spin_unlock(&data_sinfo->lock);

			alloc_target = btrfs_get_alloc_profile(root, 1);
			trans = btrfs_start_transaction(root, 1);
			if (!trans)
				return -ENOMEM;

			ret = do_chunk_alloc(trans, root->fs_info->extent_root,
					     bytes + 2 * 1024 * 1024,
					     alloc_target, 0);
			btrfs_end_transaction(trans, root);
			if (ret)
				return ret;
			goto again;
		}
		spin_unlock(&data_sinfo->lock);
1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844

		/* commit the current transaction and try again */
		if (!committed) {
			committed = 1;
			trans = btrfs_join_transaction(root, 1);
			if (!trans)
				return -ENOMEM;
			ret = btrfs_commit_transaction(trans, root);
			if (ret)
				return ret;
			goto again;
		}

J
Josef Bacik 已提交
1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921
		printk(KERN_ERR "no space left, need %llu, %llu delalloc bytes"
		       ", %llu bytes_used, %llu bytes_reserved, "
		       "%llu bytes_pinned, %llu bytes_readonly, %llu may use"
		       "%llu total\n", bytes, data_sinfo->bytes_delalloc,
		       data_sinfo->bytes_used, data_sinfo->bytes_reserved,
		       data_sinfo->bytes_pinned, data_sinfo->bytes_readonly,
		       data_sinfo->bytes_may_use, data_sinfo->total_bytes);
		return -ENOSPC;
	}
	data_sinfo->bytes_may_use += bytes;
	BTRFS_I(inode)->reserved_bytes += bytes;
	spin_unlock(&data_sinfo->lock);

	return btrfs_check_metadata_free_space(root);
}

/*
 * if there was an error for whatever reason after calling
 * btrfs_check_data_free_space, call this so we can cleanup the counters.
 */
void btrfs_free_reserved_data_space(struct btrfs_root *root,
				    struct inode *inode, u64 bytes)
{
	struct btrfs_space_info *data_sinfo;

	/* make sure bytes are sectorsize aligned */
	bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);

	data_sinfo = BTRFS_I(inode)->space_info;
	spin_lock(&data_sinfo->lock);
	data_sinfo->bytes_may_use -= bytes;
	BTRFS_I(inode)->reserved_bytes -= bytes;
	spin_unlock(&data_sinfo->lock);
}

/* called when we are adding a delalloc extent to the inode's io_tree */
void btrfs_delalloc_reserve_space(struct btrfs_root *root, struct inode *inode,
				  u64 bytes)
{
	struct btrfs_space_info *data_sinfo;

	/* get the space info for where this inode will be storing its data */
	data_sinfo = BTRFS_I(inode)->space_info;

	/* make sure we have enough space to handle the data first */
	spin_lock(&data_sinfo->lock);
	data_sinfo->bytes_delalloc += bytes;

	/*
	 * we are adding a delalloc extent without calling
	 * btrfs_check_data_free_space first.  This happens on a weird
	 * writepage condition, but shouldn't hurt our accounting
	 */
	if (unlikely(bytes > BTRFS_I(inode)->reserved_bytes)) {
		data_sinfo->bytes_may_use -= BTRFS_I(inode)->reserved_bytes;
		BTRFS_I(inode)->reserved_bytes = 0;
	} else {
		data_sinfo->bytes_may_use -= bytes;
		BTRFS_I(inode)->reserved_bytes -= bytes;
	}

	spin_unlock(&data_sinfo->lock);
}

/* called when we are clearing an delalloc extent from the inode's io_tree */
void btrfs_delalloc_free_space(struct btrfs_root *root, struct inode *inode,
			      u64 bytes)
{
	struct btrfs_space_info *info;

	info = BTRFS_I(inode)->space_info;

	spin_lock(&info->lock);
	info->bytes_delalloc -= bytes;
	spin_unlock(&info->lock);
}

1922 1923
static int do_chunk_alloc(struct btrfs_trans_handle *trans,
			  struct btrfs_root *extent_root, u64 alloc_bytes,
C
Chris Mason 已提交
1924
			  u64 flags, int force)
1925 1926 1927
{
	struct btrfs_space_info *space_info;
	u64 thresh;
Y
Yan Zheng 已提交
1928 1929 1930
	int ret = 0;

	mutex_lock(&extent_root->fs_info->chunk_mutex);
1931

Y
Yan Zheng 已提交
1932
	flags = btrfs_reduce_alloc_profile(extent_root, flags);
1933

1934
	space_info = __find_space_info(extent_root->fs_info, flags);
1935 1936 1937 1938 1939
	if (!space_info) {
		ret = update_space_info(extent_root->fs_info, flags,
					0, 0, &space_info);
		BUG_ON(ret);
	}
1940 1941
	BUG_ON(!space_info);

1942
	spin_lock(&space_info->lock);
C
Chris Mason 已提交
1943 1944 1945 1946
	if (space_info->force_alloc) {
		force = 1;
		space_info->force_alloc = 0;
	}
1947 1948
	if (space_info->full) {
		spin_unlock(&space_info->lock);
1949
		goto out;
1950
	}
1951

Y
Yan Zheng 已提交
1952 1953
	thresh = space_info->total_bytes - space_info->bytes_readonly;
	thresh = div_factor(thresh, 6);
C
Chris Mason 已提交
1954
	if (!force &&
1955
	   (space_info->bytes_used + space_info->bytes_pinned +
1956 1957
	    space_info->bytes_reserved + alloc_bytes) < thresh) {
		spin_unlock(&space_info->lock);
1958
		goto out;
1959 1960 1961
	}
	spin_unlock(&space_info->lock);

Y
Yan Zheng 已提交
1962
	ret = btrfs_alloc_chunk(trans, extent_root, flags);
C
Chris Mason 已提交
1963
	if (ret)
1964
		space_info->full = 1;
1965
out:
Y
Yan Zheng 已提交
1966
	mutex_unlock(&extent_root->fs_info->chunk_mutex);
J
Josef Bacik 已提交
1967
	return ret;
1968 1969
}

C
Chris Mason 已提交
1970 1971
static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
1972
			      u64 bytenr, u64 num_bytes, int alloc,
1973
			      int mark_free)
C
Chris Mason 已提交
1974 1975 1976
{
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *info = root->fs_info;
1977
	u64 total = num_bytes;
C
Chris Mason 已提交
1978
	u64 old_val;
1979
	u64 byte_in_group;
C
Chris Mason 已提交
1980

C
Chris Mason 已提交
1981
	while (total) {
1982
		cache = btrfs_lookup_block_group(info, bytenr);
1983
		if (!cache)
C
Chris Mason 已提交
1984
			return -1;
1985 1986
		byte_in_group = bytenr - cache->key.objectid;
		WARN_ON(byte_in_group > cache->key.offset);
C
Chris Mason 已提交
1987

1988
		spin_lock(&cache->space_info->lock);
1989
		spin_lock(&cache->lock);
J
Josef Bacik 已提交
1990
		cache->dirty = 1;
C
Chris Mason 已提交
1991
		old_val = btrfs_block_group_used(&cache->item);
1992
		num_bytes = min(total, cache->key.offset - byte_in_group);
C
Chris Mason 已提交
1993
		if (alloc) {
1994
			old_val += num_bytes;
1995
			cache->space_info->bytes_used += num_bytes;
Y
Yan Zheng 已提交
1996
			if (cache->ro)
Y
Yan Zheng 已提交
1997
				cache->space_info->bytes_readonly -= num_bytes;
1998 1999
			btrfs_set_block_group_used(&cache->item, old_val);
			spin_unlock(&cache->lock);
2000
			spin_unlock(&cache->space_info->lock);
C
Chris Mason 已提交
2001
		} else {
2002
			old_val -= num_bytes;
2003
			cache->space_info->bytes_used -= num_bytes;
Y
Yan Zheng 已提交
2004 2005
			if (cache->ro)
				cache->space_info->bytes_readonly += num_bytes;
2006 2007
			btrfs_set_block_group_used(&cache->item, old_val);
			spin_unlock(&cache->lock);
2008
			spin_unlock(&cache->space_info->lock);
2009
			if (mark_free) {
J
Josef Bacik 已提交
2010
				int ret;
2011 2012 2013 2014 2015

				ret = btrfs_discard_extent(root, bytenr,
							   num_bytes);
				WARN_ON(ret);

J
Josef Bacik 已提交
2016 2017
				ret = btrfs_add_free_space(cache, bytenr,
							   num_bytes);
2018
				WARN_ON(ret);
2019
			}
C
Chris Mason 已提交
2020
		}
2021
		put_block_group(cache);
2022 2023
		total -= num_bytes;
		bytenr += num_bytes;
C
Chris Mason 已提交
2024 2025 2026
	}
	return 0;
}
2027

2028 2029
static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
{
J
Josef Bacik 已提交
2030
	struct btrfs_block_group_cache *cache;
2031
	u64 bytenr;
J
Josef Bacik 已提交
2032 2033 2034

	cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
	if (!cache)
2035
		return 0;
J
Josef Bacik 已提交
2036

2037 2038 2039 2040
	bytenr = cache->key.objectid;
	put_block_group(cache);

	return bytenr;
2041 2042
}

2043
int btrfs_update_pinned_extents(struct btrfs_root *root,
2044 2045 2046 2047 2048 2049
				u64 bytenr, u64 num, int pin)
{
	u64 len;
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *fs_info = root->fs_info;

2050
	WARN_ON(!mutex_is_locked(&root->fs_info->pinned_mutex));
2051 2052 2053 2054 2055 2056 2057
	if (pin) {
		set_extent_dirty(&fs_info->pinned_extents,
				bytenr, bytenr + num - 1, GFP_NOFS);
	} else {
		clear_extent_dirty(&fs_info->pinned_extents,
				bytenr, bytenr + num - 1, GFP_NOFS);
	}
2058 2059
	mutex_unlock(&root->fs_info->pinned_mutex);

2060 2061
	while (num > 0) {
		cache = btrfs_lookup_block_group(fs_info, bytenr);
2062 2063 2064
		BUG_ON(!cache);
		len = min(num, cache->key.offset -
			  (bytenr - cache->key.objectid));
2065
		if (pin) {
2066
			spin_lock(&cache->space_info->lock);
2067 2068 2069 2070
			spin_lock(&cache->lock);
			cache->pinned += len;
			cache->space_info->bytes_pinned += len;
			spin_unlock(&cache->lock);
2071
			spin_unlock(&cache->space_info->lock);
2072 2073
			fs_info->total_pinned += len;
		} else {
2074
			spin_lock(&cache->space_info->lock);
2075 2076 2077 2078
			spin_lock(&cache->lock);
			cache->pinned -= len;
			cache->space_info->bytes_pinned -= len;
			spin_unlock(&cache->lock);
2079
			spin_unlock(&cache->space_info->lock);
2080
			fs_info->total_pinned -= len;
2081 2082
			if (cache->cached)
				btrfs_add_free_space(cache, bytenr, len);
2083
		}
2084
		put_block_group(cache);
2085 2086 2087 2088 2089
		bytenr += len;
		num -= len;
	}
	return 0;
}
C
Chris Mason 已提交
2090

2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102
static int update_reserved_extents(struct btrfs_root *root,
				   u64 bytenr, u64 num, int reserve)
{
	u64 len;
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *fs_info = root->fs_info;

	while (num > 0) {
		cache = btrfs_lookup_block_group(fs_info, bytenr);
		BUG_ON(!cache);
		len = min(num, cache->key.offset -
			  (bytenr - cache->key.objectid));
2103 2104 2105

		spin_lock(&cache->space_info->lock);
		spin_lock(&cache->lock);
2106 2107 2108 2109 2110 2111 2112
		if (reserve) {
			cache->reserved += len;
			cache->space_info->bytes_reserved += len;
		} else {
			cache->reserved -= len;
			cache->space_info->bytes_reserved -= len;
		}
2113 2114
		spin_unlock(&cache->lock);
		spin_unlock(&cache->space_info->lock);
2115
		put_block_group(cache);
2116 2117 2118 2119 2120 2121
		bytenr += len;
		num -= len;
	}
	return 0;
}

2122
int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
C
Chris Mason 已提交
2123 2124
{
	u64 last = 0;
2125 2126
	u64 start;
	u64 end;
2127
	struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
C
Chris Mason 已提交
2128 2129
	int ret;

2130
	mutex_lock(&root->fs_info->pinned_mutex);
C
Chris Mason 已提交
2131
	while (1) {
2132 2133 2134
		ret = find_first_extent_bit(pinned_extents, last,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
C
Chris Mason 已提交
2135
			break;
2136 2137
		set_extent_dirty(copy, start, end, GFP_NOFS);
		last = end + 1;
C
Chris Mason 已提交
2138
	}
2139
	mutex_unlock(&root->fs_info->pinned_mutex);
C
Chris Mason 已提交
2140 2141 2142 2143 2144
	return 0;
}

int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
2145
			       struct extent_io_tree *unpin)
2146
{
2147 2148
	u64 start;
	u64 end;
2149 2150
	int ret;

C
Chris Mason 已提交
2151
	while (1) {
2152
		mutex_lock(&root->fs_info->pinned_mutex);
2153 2154 2155
		ret = find_first_extent_bit(unpin, 0, &start, &end,
					    EXTENT_DIRTY);
		if (ret)
2156
			break;
2157 2158 2159

		ret = btrfs_discard_extent(root, start, end + 1 - start);

2160
		/* unlocks the pinned mutex */
2161
		btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
2162
		clear_extent_dirty(unpin, start, end, GFP_NOFS);
2163

2164
		cond_resched();
2165
	}
2166
	mutex_unlock(&root->fs_info->pinned_mutex);
2167
	return ret;
2168 2169
}

Z
Zheng Yan 已提交
2170 2171
static int pin_down_bytes(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root,
2172 2173 2174
			  struct btrfs_path *path,
			  u64 bytenr, u64 num_bytes, int is_data,
			  struct extent_buffer **must_clean)
C
Chris Mason 已提交
2175
{
2176
	int err = 0;
Z
Zheng Yan 已提交
2177
	struct extent_buffer *buf;
C
Chris Mason 已提交
2178

Z
Zheng Yan 已提交
2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195
	if (is_data)
		goto pinit;

	buf = btrfs_find_tree_block(root, bytenr, num_bytes);
	if (!buf)
		goto pinit;

	/* we can reuse a block if it hasn't been written
	 * and it is from this transaction.  We can't
	 * reuse anything from the tree log root because
	 * it has tiny sub-transactions.
	 */
	if (btrfs_buffer_uptodate(buf, 0) &&
	    btrfs_try_tree_lock(buf)) {
		u64 header_owner = btrfs_header_owner(buf);
		u64 header_transid = btrfs_header_generation(buf);
		if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
Z
Zheng Yan 已提交
2196
		    header_owner != BTRFS_TREE_RELOC_OBJECTID &&
2197
		    header_owner != BTRFS_DATA_RELOC_TREE_OBJECTID &&
Z
Zheng Yan 已提交
2198 2199
		    header_transid == trans->transid &&
		    !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
2200
			*must_clean = buf;
Z
Zheng Yan 已提交
2201
			return 1;
C
Chris Mason 已提交
2202
		}
Z
Zheng Yan 已提交
2203
		btrfs_tree_unlock(buf);
C
Chris Mason 已提交
2204
	}
Z
Zheng Yan 已提交
2205 2206
	free_extent_buffer(buf);
pinit:
2207 2208 2209
	btrfs_set_path_blocking(path);
	mutex_lock(&root->fs_info->pinned_mutex);
	/* unlocks the pinned mutex */
Z
Zheng Yan 已提交
2210 2211
	btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);

C
Chris Mason 已提交
2212
	BUG_ON(err < 0);
C
Chris Mason 已提交
2213 2214 2215
	return 0;
}

2216
/*
2217
 * remove an extent from the root, returns 0 on success
2218
 */
Z
Zheng Yan 已提交
2219 2220 2221
static int __free_extent(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root,
			 u64 bytenr, u64 num_bytes, u64 parent,
2222
			 u64 root_objectid, u64 ref_generation,
2223 2224
			 u64 owner_objectid, int pin, int mark_free,
			 int refs_to_drop)
2225
{
2226
	struct btrfs_path *path;
C
Chris Mason 已提交
2227
	struct btrfs_key key;
2228 2229
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
2230
	struct extent_buffer *leaf;
2231
	int ret;
2232 2233 2234
	int extent_slot = 0;
	int found_extent = 0;
	int num_to_del = 1;
C
Chris Mason 已提交
2235
	struct btrfs_extent_item *ei;
C
Chris Mason 已提交
2236
	u32 refs;
C
Chris Mason 已提交
2237

2238
	key.objectid = bytenr;
2239
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
2240
	key.offset = num_bytes;
2241
	path = btrfs_alloc_path();
2242 2243
	if (!path)
		return -ENOMEM;
2244

2245
	path->reada = 1;
2246
	path->leave_spinning = 1;
2247 2248 2249
	ret = lookup_extent_backref(trans, extent_root, path,
				    bytenr, parent, root_objectid,
				    ref_generation, owner_objectid, 1);
2250
	if (ret == 0) {
2251 2252
		struct btrfs_key found_key;
		extent_slot = path->slots[0];
C
Chris Mason 已提交
2253
		while (extent_slot > 0) {
2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266
			extent_slot--;
			btrfs_item_key_to_cpu(path->nodes[0], &found_key,
					      extent_slot);
			if (found_key.objectid != bytenr)
				break;
			if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
			    found_key.offset == num_bytes) {
				found_extent = 1;
				break;
			}
			if (path->slots[0] - extent_slot > 5)
				break;
		}
Z
Zheng Yan 已提交
2267
		if (!found_extent) {
2268 2269
			ret = remove_extent_backref(trans, extent_root, path,
						    refs_to_drop);
Z
Zheng Yan 已提交
2270 2271
			BUG_ON(ret);
			btrfs_release_path(extent_root, path);
2272
			path->leave_spinning = 1;
Z
Zheng Yan 已提交
2273 2274
			ret = btrfs_search_slot(trans, extent_root,
						&key, path, -1, 1);
2275 2276
			if (ret) {
				printk(KERN_ERR "umm, got %d back from search"
C
Chris Mason 已提交
2277 2278
				       ", was looking for %llu\n", ret,
				       (unsigned long long)bytenr);
2279 2280
				btrfs_print_leaf(extent_root, path->nodes[0]);
			}
Z
Zheng Yan 已提交
2281 2282 2283
			BUG_ON(ret);
			extent_slot = path->slots[0];
		}
2284 2285 2286
	} else {
		btrfs_print_leaf(extent_root, path->nodes[0]);
		WARN_ON(1);
C
Chris Mason 已提交
2287
		printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
2288
		       "parent %llu root %llu gen %llu owner %llu\n",
C
Chris Mason 已提交
2289
		       (unsigned long long)bytenr,
2290
		       (unsigned long long)parent,
C
Chris Mason 已提交
2291 2292 2293
		       (unsigned long long)root_objectid,
		       (unsigned long long)ref_generation,
		       (unsigned long long)owner_objectid);
2294
	}
2295 2296

	leaf = path->nodes[0];
2297
	ei = btrfs_item_ptr(leaf, extent_slot,
C
Chris Mason 已提交
2298
			    struct btrfs_extent_item);
2299
	refs = btrfs_extent_refs(leaf, ei);
2300

2301 2302 2303 2304 2305 2306 2307 2308
	/*
	 * we're not allowed to delete the extent item if there
	 * are other delayed ref updates pending
	 */

	BUG_ON(refs < refs_to_drop);
	refs -= refs_to_drop;
	btrfs_set_extent_refs(leaf, ei, refs);
2309 2310
	btrfs_mark_buffer_dirty(leaf);

2311 2312
	if (refs == 0 && found_extent &&
	    path->slots[0] == extent_slot + 1) {
Z
Zheng Yan 已提交
2313 2314 2315
		struct btrfs_extent_ref *ref;
		ref = btrfs_item_ptr(leaf, path->slots[0],
				     struct btrfs_extent_ref);
2316
		BUG_ON(btrfs_ref_num_refs(leaf, ref) != refs_to_drop);
2317 2318 2319 2320 2321 2322 2323
		/* if the back ref and the extent are next to each other
		 * they get deleted below in one shot
		 */
		path->slots[0] = extent_slot;
		num_to_del = 2;
	} else if (found_extent) {
		/* otherwise delete the extent back ref */
2324 2325
		ret = remove_extent_backref(trans, extent_root, path,
					    refs_to_drop);
2326 2327 2328 2329
		BUG_ON(ret);
		/* if refs are 0, we need to setup the path for deletion */
		if (refs == 0) {
			btrfs_release_path(extent_root, path);
2330
			path->leave_spinning = 1;
2331 2332 2333 2334 2335 2336
			ret = btrfs_search_slot(trans, extent_root, &key, path,
						-1, 1);
			BUG_ON(ret);
		}
	}

C
Chris Mason 已提交
2337
	if (refs == 0) {
2338 2339
		u64 super_used;
		u64 root_used;
2340
		struct extent_buffer *must_clean = NULL;
C
Chris Mason 已提交
2341 2342

		if (pin) {
2343 2344 2345 2346
			ret = pin_down_bytes(trans, root, path,
				bytenr, num_bytes,
				owner_objectid >= BTRFS_FIRST_FREE_OBJECTID,
				&must_clean);
2347 2348 2349
			if (ret > 0)
				mark_free = 1;
			BUG_ON(ret < 0);
C
Chris Mason 已提交
2350
		}
2351

2352
		/* block accounting for super block */
2353
		spin_lock(&info->delalloc_lock);
2354 2355 2356
		super_used = btrfs_super_bytes_used(&info->super_copy);
		btrfs_set_super_bytes_used(&info->super_copy,
					   super_used - num_bytes);
2357 2358

		/* block accounting for root item */
2359
		root_used = btrfs_root_used(&root->root_item);
2360
		btrfs_set_root_used(&root->root_item,
2361
					   root_used - num_bytes);
2362
		spin_unlock(&info->delalloc_lock);
2363 2364 2365 2366 2367 2368 2369 2370 2371 2372

		/*
		 * it is going to be very rare for someone to be waiting
		 * on the block we're freeing.  del_items might need to
		 * schedule, so rather than get fancy, just force it
		 * to blocking here
		 */
		if (must_clean)
			btrfs_set_lock_blocking(must_clean);

2373 2374
		ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
				      num_to_del);
Z
Zheng Yan 已提交
2375
		BUG_ON(ret);
2376
		btrfs_release_path(extent_root, path);
2377

2378 2379 2380 2381 2382 2383
		if (must_clean) {
			clean_tree_block(NULL, root, must_clean);
			btrfs_tree_unlock(must_clean);
			free_extent_buffer(must_clean);
		}

2384 2385 2386 2387 2388
		if (owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
			ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
			BUG_ON(ret);
		}

2389 2390 2391
		ret = update_block_group(trans, root, bytenr, num_bytes, 0,
					 mark_free);
		BUG_ON(ret);
2392
	}
2393
	btrfs_free_path(path);
2394 2395 2396
	return ret;
}

2397 2398 2399
/*
 * remove an extent from the root, returns 0 on success
 */
2400
static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
2401 2402 2403 2404 2405
					struct btrfs_root *root,
					u64 bytenr, u64 num_bytes, u64 parent,
					u64 root_objectid, u64 ref_generation,
					u64 owner_objectid, int pin,
					int refs_to_drop)
2406
{
2407
	WARN_ON(num_bytes < root->sectorsize);
Z
Zheng Yan 已提交
2408

2409 2410 2411 2412 2413 2414
	/*
	 * if metadata always pin
	 * if data pin when any transaction has committed this
	 */
	if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID ||
	    ref_generation != trans->transid)
C
Chris Mason 已提交
2415 2416 2417 2418 2419
		pin = 1;

	if (ref_generation != trans->transid)
		pin = 1;

2420
	return __free_extent(trans, root, bytenr, num_bytes, parent,
2421
			    root_objectid, ref_generation,
2422
			    owner_objectid, pin, pin == 0, refs_to_drop);
2423 2424
}

2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468
/*
 * when we free an extent, it is possible (and likely) that we free the last
 * delayed ref for that extent as well.  This searches the delayed ref tree for
 * a given extent, and if there are no other delayed refs to be processed, it
 * removes it from the tree.
 */
static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
				      struct btrfs_root *root, u64 bytenr)
{
	struct btrfs_delayed_ref_head *head;
	struct btrfs_delayed_ref_root *delayed_refs;
	struct btrfs_delayed_ref_node *ref;
	struct rb_node *node;
	int ret;

	delayed_refs = &trans->transaction->delayed_refs;
	spin_lock(&delayed_refs->lock);
	head = btrfs_find_delayed_ref_head(trans, bytenr);
	if (!head)
		goto out;

	node = rb_prev(&head->node.rb_node);
	if (!node)
		goto out;

	ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);

	/* there are still entries for this ref, we can't drop it */
	if (ref->bytenr == bytenr)
		goto out;

	/*
	 * waiting for the lock here would deadlock.  If someone else has it
	 * locked they are already in the process of dropping it anyway
	 */
	if (!mutex_trylock(&head->mutex))
		goto out;

	/*
	 * at this point we have a head with no other entries.  Go
	 * ahead and process it.
	 */
	head->node.in_tree = 0;
	rb_erase(&head->node.rb_node, &delayed_refs->root);
2469

2470 2471 2472 2473 2474 2475
	delayed_refs->num_entries--;

	/*
	 * we don't take a ref on the node because we're removing it from the
	 * tree, so we just steal the ref the tree was holding.
	 */
2476 2477 2478 2479 2480
	delayed_refs->num_heads--;
	if (list_empty(&head->cluster))
		delayed_refs->num_heads_ready--;

	list_del_init(&head->cluster);
2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492
	spin_unlock(&delayed_refs->lock);

	ret = run_one_delayed_ref(trans, root->fs_info->tree_root,
				  &head->node, head->must_insert_reserved);
	BUG_ON(ret);
	btrfs_put_delayed_ref(&head->node);
	return 0;
out:
	spin_unlock(&delayed_refs->lock);
	return 0;
}

2493
int btrfs_free_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
2494 2495 2496
		      struct btrfs_root *root,
		      u64 bytenr, u64 num_bytes, u64 parent,
		      u64 root_objectid, u64 ref_generation,
2497
		      u64 owner_objectid, int pin)
2498 2499 2500
{
	int ret;

2501 2502 2503 2504 2505 2506 2507 2508 2509 2510
	/*
	 * tree log blocks never actually go into the extent allocation
	 * tree, just update pinning info and exit early.
	 *
	 * data extents referenced by the tree log do need to have
	 * their reference counts bumped.
	 */
	if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID &&
	    owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
		mutex_lock(&root->fs_info->pinned_mutex);
2511 2512

		/* unlocks the pinned mutex */
2513 2514 2515 2516 2517 2518 2519 2520
		btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
		update_reserved_extents(root, bytenr, num_bytes, 0);
		ret = 0;
	} else {
		ret = btrfs_add_delayed_ref(trans, bytenr, num_bytes, parent,
				       root_objectid, ref_generation,
				       owner_objectid,
				       BTRFS_DROP_DELAYED_REF, 1);
2521 2522 2523
		BUG_ON(ret);
		ret = check_ref_cleanup(trans, root, bytenr);
		BUG_ON(ret);
2524
	}
2525 2526 2527
	return ret;
}

2528 2529 2530 2531 2532 2533 2534
static u64 stripe_align(struct btrfs_root *root, u64 val)
{
	u64 mask = ((u64)root->stripesize - 1);
	u64 ret = (val + mask) & ~mask;
	return ret;
}

2535 2536 2537 2538
/*
 * walks the btree of allocated extents and find a hole of a given size.
 * The key ins is changed to record the hole:
 * ins->objectid == block start
2539
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
2540 2541 2542
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
C
Chris Mason 已提交
2543
static noinline int find_free_extent(struct btrfs_trans_handle *trans,
2544 2545 2546 2547 2548 2549
				     struct btrfs_root *orig_root,
				     u64 num_bytes, u64 empty_size,
				     u64 search_start, u64 search_end,
				     u64 hint_byte, struct btrfs_key *ins,
				     u64 exclude_start, u64 exclude_nr,
				     int data)
2550
{
2551
	int ret = 0;
C
Chris Mason 已提交
2552
	struct btrfs_root *root = orig_root->fs_info->extent_root;
2553
	u64 total_needed = num_bytes;
2554
	u64 *last_ptr = NULL;
2555
	u64 last_wanted = 0;
2556
	struct btrfs_block_group_cache *block_group = NULL;
C
Chris Mason 已提交
2557
	int chunk_alloc_done = 0;
2558
	int empty_cluster = 2 * 1024 * 1024;
C
Chris Mason 已提交
2559
	int allowed_chunk_alloc = 0;
2560 2561
	struct list_head *head = NULL, *cur = NULL;
	int loop = 0;
2562
	int extra_loop = 0;
2563
	struct btrfs_space_info *space_info;
2564

2565
	WARN_ON(num_bytes < root->sectorsize);
2566
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
2567 2568
	ins->objectid = 0;
	ins->offset = 0;
2569

C
Chris Mason 已提交
2570 2571 2572
	if (orig_root->ref_cows || empty_size)
		allowed_chunk_alloc = 1;

2573 2574
	if (data & BTRFS_BLOCK_GROUP_METADATA) {
		last_ptr = &root->fs_info->last_alloc;
2575 2576
		if (!btrfs_test_opt(root, SSD))
			empty_cluster = 64 * 1024;
2577 2578
	}

J
Josef Bacik 已提交
2579
	if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD))
2580
		last_ptr = &root->fs_info->last_data_alloc;
J
Josef Bacik 已提交
2581

2582
	if (last_ptr) {
2583
		if (*last_ptr) {
2584
			hint_byte = *last_ptr;
2585 2586
			last_wanted = *last_ptr;
		} else
2587
			empty_size += empty_cluster;
2588 2589
	} else {
		empty_cluster = 0;
2590
	}
2591
	search_start = max(search_start, first_logical_byte(root, 0));
2592
	search_start = max(search_start, hint_byte);
2593

2594
	if (last_wanted && search_start != last_wanted) {
2595
		last_wanted = 0;
2596 2597
		empty_size += empty_cluster;
	}
2598

2599
	total_needed += empty_size;
2600
	block_group = btrfs_lookup_block_group(root->fs_info, search_start);
Y
Yan Zheng 已提交
2601 2602 2603
	if (!block_group)
		block_group = btrfs_lookup_first_block_group(root->fs_info,
							     search_start);
2604
	space_info = __find_space_info(root->fs_info, data);
J
Josef Bacik 已提交
2605

2606 2607 2608
	down_read(&space_info->groups_sem);
	while (1) {
		struct btrfs_free_space *free_space;
J
Josef Bacik 已提交
2609
		/*
2610 2611 2612
		 * the only way this happens if our hint points to a block
		 * group thats not of the proper type, while looping this
		 * should never happen
J
Josef Bacik 已提交
2613
		 */
2614 2615 2616
		if (empty_size)
			extra_loop = 1;

2617 2618 2619
		if (!block_group)
			goto new_group_no_lock;

2620 2621 2622 2623 2624 2625 2626 2627
		if (unlikely(!block_group->cached)) {
			mutex_lock(&block_group->cache_mutex);
			ret = cache_block_group(root, block_group);
			mutex_unlock(&block_group->cache_mutex);
			if (ret)
				break;
		}

2628
		mutex_lock(&block_group->alloc_mutex);
2629
		if (unlikely(!block_group_bits(block_group, data)))
J
Josef Bacik 已提交
2630 2631
			goto new_group;

2632
		if (unlikely(block_group->ro))
2633
			goto new_group;
J
Josef Bacik 已提交
2634

2635 2636 2637 2638 2639
		free_space = btrfs_find_free_space(block_group, search_start,
						   total_needed);
		if (free_space) {
			u64 start = block_group->key.objectid;
			u64 end = block_group->key.objectid +
J
Josef Bacik 已提交
2640
				block_group->key.offset;
2641

2642
			search_start = stripe_align(root, free_space->offset);
J
Josef Bacik 已提交
2643

2644 2645 2646
			/* move on to the next group */
			if (search_start + num_bytes >= search_end)
				goto new_group;
2647

2648 2649 2650 2651
			/* move on to the next group */
			if (search_start + num_bytes > end)
				goto new_group;

2652
			if (last_wanted && search_start != last_wanted) {
2653
				total_needed += empty_cluster;
2654
				empty_size += empty_cluster;
2655
				last_wanted = 0;
2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669
				/*
				 * if search_start is still in this block group
				 * then we just re-search this block group
				 */
				if (search_start >= start &&
				    search_start < end) {
					mutex_unlock(&block_group->alloc_mutex);
					continue;
				}

				/* else we go to the next block group */
				goto new_group;
			}

2670 2671 2672 2673 2674 2675 2676 2677 2678
			if (exclude_nr > 0 &&
			    (search_start + num_bytes > exclude_start &&
			     search_start < exclude_start + exclude_nr)) {
				search_start = exclude_start + exclude_nr;
				/*
				 * if search_start is still in this block group
				 * then we just re-search this block group
				 */
				if (search_start >= start &&
2679 2680
				    search_start < end) {
					mutex_unlock(&block_group->alloc_mutex);
2681
					last_wanted = 0;
2682
					continue;
2683
				}
2684 2685 2686 2687 2688 2689 2690

				/* else we go to the next block group */
				goto new_group;
			}

			ins->objectid = search_start;
			ins->offset = num_bytes;
2691 2692 2693

			btrfs_remove_free_space_lock(block_group, search_start,
						     num_bytes);
2694
			/* we are all good, lets return */
2695
			mutex_unlock(&block_group->alloc_mutex);
2696
			break;
J
Josef Bacik 已提交
2697
		}
2698
new_group:
2699
		mutex_unlock(&block_group->alloc_mutex);
2700 2701
		put_block_group(block_group);
		block_group = NULL;
2702
new_group_no_lock:
2703 2704 2705
		/* don't try to compare new allocations against the
		 * last allocation any more
		 */
2706
		last_wanted = 0;
2707

2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724
		/*
		 * Here's how this works.
		 * loop == 0: we were searching a block group via a hint
		 *		and didn't find anything, so we start at
		 *		the head of the block groups and keep searching
		 * loop == 1: we're searching through all of the block groups
		 *		if we hit the head again we have searched
		 *		all of the block groups for this space and we
		 *		need to try and allocate, if we cant error out.
		 * loop == 2: we allocated more space and are looping through
		 *		all of the block groups again.
		 */
		if (loop == 0) {
			head = &space_info->block_groups;
			cur = head->next;
			loop++;
		} else if (loop == 1 && cur == head) {
2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735
			int keep_going;

			/* at this point we give up on the empty_size
			 * allocations and just try to allocate the min
			 * space.
			 *
			 * The extra_loop field was set if an empty_size
			 * allocation was attempted above, and if this
			 * is try we need to try the loop again without
			 * the additional empty_size.
			 */
2736 2737
			total_needed -= empty_size;
			empty_size = 0;
2738 2739
			keep_going = extra_loop;
			loop++;
2740

2741 2742 2743 2744 2745
			if (allowed_chunk_alloc && !chunk_alloc_done) {
				up_read(&space_info->groups_sem);
				ret = do_chunk_alloc(trans, root, num_bytes +
						     2 * 1024 * 1024, data, 1);
				down_read(&space_info->groups_sem);
2746 2747
				if (ret < 0)
					goto loop_check;
2748
				head = &space_info->block_groups;
2749 2750 2751 2752 2753
				/*
				 * we've allocated a new chunk, keep
				 * trying
				 */
				keep_going = 1;
2754 2755 2756
				chunk_alloc_done = 1;
			} else if (!allowed_chunk_alloc) {
				space_info->force_alloc = 1;
2757
			}
2758
loop_check:
2759 2760 2761
			if (keep_going) {
				cur = head->next;
				extra_loop = 0;
2762 2763 2764 2765 2766
			} else {
				break;
			}
		} else if (cur == head) {
			break;
J
Josef Bacik 已提交
2767
		}
2768

2769 2770
		block_group = list_entry(cur, struct btrfs_block_group_cache,
					 list);
2771 2772
		atomic_inc(&block_group->count);

2773 2774
		search_start = block_group->key.objectid;
		cur = cur->next;
2775
	}
2776

2777 2778 2779
	/* we found what we needed */
	if (ins->objectid) {
		if (!(data & BTRFS_BLOCK_GROUP_DATA))
2780
			trans->block_group = block_group->key.objectid;
J
Josef Bacik 已提交
2781

2782 2783 2784 2785
		if (last_ptr)
			*last_ptr = ins->objectid + ins->offset;
		ret = 0;
	} else if (!ret) {
C
Chris Mason 已提交
2786 2787 2788 2789
		printk(KERN_ERR "btrfs searching for %llu bytes, "
		       "num_bytes %llu, loop %d, allowed_alloc %d\n",
		       (unsigned long long)total_needed,
		       (unsigned long long)num_bytes,
2790
		       loop, allowed_chunk_alloc);
2791
		ret = -ENOSPC;
C
Chris Mason 已提交
2792
	}
2793 2794
	if (block_group)
		put_block_group(block_group);
C
Chris Mason 已提交
2795

2796
	up_read(&space_info->groups_sem);
C
Chris Mason 已提交
2797
	return ret;
2798
}
2799

J
Josef Bacik 已提交
2800 2801 2802 2803
static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
{
	struct btrfs_block_group_cache *cache;

C
Chris Mason 已提交
2804 2805 2806 2807
	printk(KERN_INFO "space_info has %llu free, is %sfull\n",
	       (unsigned long long)(info->total_bytes - info->bytes_used -
				    info->bytes_pinned - info->bytes_reserved),
	       (info->full) ? "" : "not ");
J
Josef Bacik 已提交
2808 2809 2810 2811
	printk(KERN_INFO "space_info total=%llu, pinned=%llu, delalloc=%llu,"
	       " may_use=%llu, used=%llu\n", info->total_bytes,
	       info->bytes_pinned, info->bytes_delalloc, info->bytes_may_use,
	       info->bytes_used);
J
Josef Bacik 已提交
2812

2813
	down_read(&info->groups_sem);
Q
Qinghuang Feng 已提交
2814
	list_for_each_entry(cache, &info->block_groups, list) {
J
Josef Bacik 已提交
2815
		spin_lock(&cache->lock);
C
Chris Mason 已提交
2816 2817 2818 2819 2820 2821 2822
		printk(KERN_INFO "block group %llu has %llu bytes, %llu used "
		       "%llu pinned %llu reserved\n",
		       (unsigned long long)cache->key.objectid,
		       (unsigned long long)cache->key.offset,
		       (unsigned long long)btrfs_block_group_used(&cache->item),
		       (unsigned long long)cache->pinned,
		       (unsigned long long)cache->reserved);
J
Josef Bacik 已提交
2823 2824 2825
		btrfs_dump_free_space(cache, bytes);
		spin_unlock(&cache->lock);
	}
2826
	up_read(&info->groups_sem);
J
Josef Bacik 已提交
2827
}
2828

2829 2830 2831 2832 2833 2834
static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
				  struct btrfs_root *root,
				  u64 num_bytes, u64 min_alloc_size,
				  u64 empty_size, u64 hint_byte,
				  u64 search_end, struct btrfs_key *ins,
				  u64 data)
2835 2836
{
	int ret;
2837
	u64 search_start = 0;
2838
	struct btrfs_fs_info *info = root->fs_info;
2839

J
Josef Bacik 已提交
2840
	data = btrfs_get_alloc_profile(root, data);
2841
again:
C
Chris Mason 已提交
2842 2843 2844 2845 2846
	/*
	 * the only place that sets empty_size is btrfs_realloc_node, which
	 * is not called recursively on allocations
	 */
	if (empty_size || root->ref_cows) {
2847
		if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2848
			ret = do_chunk_alloc(trans, root->fs_info->extent_root,
C
Chris Mason 已提交
2849 2850 2851 2852
				     2 * 1024 * 1024,
				     BTRFS_BLOCK_GROUP_METADATA |
				     (info->metadata_alloc_profile &
				      info->avail_metadata_alloc_bits), 0);
2853 2854
		}
		ret = do_chunk_alloc(trans, root->fs_info->extent_root,
C
Chris Mason 已提交
2855
				     num_bytes + 2 * 1024 * 1024, data, 0);
2856
	}
2857

2858 2859 2860
	WARN_ON(num_bytes < root->sectorsize);
	ret = find_free_extent(trans, root, num_bytes, empty_size,
			       search_start, search_end, hint_byte, ins,
2861 2862
			       trans->alloc_exclude_start,
			       trans->alloc_exclude_nr, data);
2863

2864 2865
	if (ret == -ENOSPC && num_bytes > min_alloc_size) {
		num_bytes = num_bytes >> 1;
J
Josef Bacik 已提交
2866
		num_bytes = num_bytes & ~(root->sectorsize - 1);
2867
		num_bytes = max(num_bytes, min_alloc_size);
C
Chris Mason 已提交
2868 2869
		do_chunk_alloc(trans, root->fs_info->extent_root,
			       num_bytes, data, 1);
2870 2871
		goto again;
	}
2872
	if (ret) {
J
Josef Bacik 已提交
2873 2874 2875
		struct btrfs_space_info *sinfo;

		sinfo = __find_space_info(root->fs_info, data);
C
Chris Mason 已提交
2876 2877 2878
		printk(KERN_ERR "btrfs allocation failed flags %llu, "
		       "wanted %llu\n", (unsigned long long)data,
		       (unsigned long long)num_bytes);
J
Josef Bacik 已提交
2879
		dump_space_info(sinfo, num_bytes);
2880 2881
		BUG();
	}
J
Josef Bacik 已提交
2882 2883

	return ret;
2884 2885
}

2886 2887
int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
{
J
Josef Bacik 已提交
2888
	struct btrfs_block_group_cache *cache;
2889
	int ret = 0;
J
Josef Bacik 已提交
2890 2891 2892

	cache = btrfs_lookup_block_group(root->fs_info, start);
	if (!cache) {
C
Chris Mason 已提交
2893 2894
		printk(KERN_ERR "Unable to find block group for %llu\n",
		       (unsigned long long)start);
J
Josef Bacik 已提交
2895 2896
		return -ENOSPC;
	}
2897 2898 2899

	ret = btrfs_discard_extent(root, start, len);

J
Josef Bacik 已提交
2900
	btrfs_add_free_space(cache, start, len);
2901
	put_block_group(cache);
Z
Zheng Yan 已提交
2902
	update_reserved_extents(root, start, len, 0);
2903 2904

	return ret;
2905 2906
}

2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917
int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
				  struct btrfs_root *root,
				  u64 num_bytes, u64 min_alloc_size,
				  u64 empty_size, u64 hint_byte,
				  u64 search_end, struct btrfs_key *ins,
				  u64 data)
{
	int ret;
	ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
				     empty_size, hint_byte, search_end, ins,
				     data);
2918
	update_reserved_extents(root, ins->objectid, ins->offset, 1);
2919 2920 2921 2922
	return ret;
}

static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
2923
					 struct btrfs_root *root, u64 parent,
2924
					 u64 root_objectid, u64 ref_generation,
2925 2926
					 u64 owner, struct btrfs_key *ins,
					 int ref_mod)
2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938
{
	int ret;
	u64 super_used;
	u64 root_used;
	u64 num_bytes = ins->offset;
	u32 sizes[2];
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
	struct btrfs_extent_item *extent_item;
	struct btrfs_extent_ref *ref;
	struct btrfs_path *path;
	struct btrfs_key keys[2];
2939

Z
Zheng Yan 已提交
2940 2941 2942
	if (parent == 0)
		parent = ins->objectid;

2943
	/* block accounting for super block */
2944
	spin_lock(&info->delalloc_lock);
2945 2946
	super_used = btrfs_super_bytes_used(&info->super_copy);
	btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
2947

2948
	/* block accounting for root item */
2949 2950
	root_used = btrfs_root_used(&root->root_item);
	btrfs_set_root_used(&root->root_item, root_used + num_bytes);
2951
	spin_unlock(&info->delalloc_lock);
2952

2953 2954 2955
	memcpy(&keys[0], ins, sizeof(*ins));
	keys[1].objectid = ins->objectid;
	keys[1].type = BTRFS_EXTENT_REF_KEY;
Z
Zheng Yan 已提交
2956
	keys[1].offset = parent;
2957 2958
	sizes[0] = sizeof(*extent_item);
	sizes[1] = sizeof(*ref);
2959 2960 2961

	path = btrfs_alloc_path();
	BUG_ON(!path);
2962

2963
	path->leave_spinning = 1;
2964 2965
	ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
				       sizes, 2);
C
Chris Mason 已提交
2966
	BUG_ON(ret);
J
Josef Bacik 已提交
2967

2968 2969
	extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
				     struct btrfs_extent_item);
2970
	btrfs_set_extent_refs(path->nodes[0], extent_item, ref_mod);
2971 2972 2973 2974 2975 2976
	ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
			     struct btrfs_extent_ref);

	btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
	btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
	btrfs_set_ref_objectid(path->nodes[0], ref, owner);
2977
	btrfs_set_ref_num_refs(path->nodes[0], ref, ref_mod);
2978 2979 2980 2981 2982

	btrfs_mark_buffer_dirty(path->nodes[0]);

	trans->alloc_exclude_start = 0;
	trans->alloc_exclude_nr = 0;
2983
	btrfs_free_path(path);
2984

2985 2986
	if (ret)
		goto out;
2987

C
Chris Mason 已提交
2988 2989
	ret = update_block_group(trans, root, ins->objectid,
				 ins->offset, 1, 0);
2990
	if (ret) {
C
Chris Mason 已提交
2991 2992 2993
		printk(KERN_ERR "btrfs update block group failed for %llu "
		       "%llu\n", (unsigned long long)ins->objectid,
		       (unsigned long long)ins->offset);
2994 2995
		BUG();
	}
2996
out:
2997 2998 2999 3000
	return ret;
}

int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
3001
				struct btrfs_root *root, u64 parent,
3002
				u64 root_objectid, u64 ref_generation,
3003
				u64 owner, struct btrfs_key *ins)
3004 3005
{
	int ret;
3006 3007 3008

	if (root_objectid == BTRFS_TREE_LOG_OBJECTID)
		return 0;
3009 3010 3011 3012 3013 3014

	ret = btrfs_add_delayed_ref(trans, ins->objectid,
				    ins->offset, parent, root_objectid,
				    ref_generation, owner,
				    BTRFS_ADD_DELAYED_EXTENT, 0);
	BUG_ON(ret);
3015 3016
	return ret;
}
3017 3018 3019 3020 3021 3022 3023

/*
 * this is used by the tree logging recovery code.  It records that
 * an extent has been allocated and makes sure to clear the free
 * space cache bits as well
 */
int btrfs_alloc_logged_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
3024
				struct btrfs_root *root, u64 parent,
3025
				u64 root_objectid, u64 ref_generation,
3026
				u64 owner, struct btrfs_key *ins)
3027 3028 3029 3030 3031
{
	int ret;
	struct btrfs_block_group_cache *block_group;

	block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
3032
	mutex_lock(&block_group->cache_mutex);
3033
	cache_block_group(root, block_group);
3034
	mutex_unlock(&block_group->cache_mutex);
3035

3036 3037
	ret = btrfs_remove_free_space(block_group, ins->objectid,
				      ins->offset);
J
Josef Bacik 已提交
3038
	BUG_ON(ret);
3039
	put_block_group(block_group);
3040
	ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
3041
					    ref_generation, owner, ins, 1);
3042 3043 3044
	return ret;
}

3045 3046 3047 3048 3049 3050 3051 3052 3053
/*
 * finds a free extent and does all the dirty work required for allocation
 * returns the key for the extent through ins, and a tree buffer for
 * the first block of the extent through buf.
 *
 * returns 0 if everything worked, non-zero otherwise.
 */
int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root,
Z
Zheng Yan 已提交
3054
		       u64 num_bytes, u64 parent, u64 min_alloc_size,
3055
		       u64 root_objectid, u64 ref_generation,
3056
		       u64 owner_objectid, u64 empty_size, u64 hint_byte,
3057 3058 3059 3060 3061 3062 3063
		       u64 search_end, struct btrfs_key *ins, u64 data)
{
	int ret;
	ret = __btrfs_reserve_extent(trans, root, num_bytes,
				     min_alloc_size, empty_size, hint_byte,
				     search_end, ins, data);
	BUG_ON(ret);
3064
	if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
3065 3066 3067 3068
		ret = btrfs_add_delayed_ref(trans, ins->objectid,
					    ins->offset, parent, root_objectid,
					    ref_generation, owner_objectid,
					    BTRFS_ADD_DELAYED_EXTENT, 0);
3069 3070
		BUG_ON(ret);
	}
3071
	update_reserved_extents(root, ins->objectid, ins->offset, 1);
3072
	return ret;
3073
}
3074 3075 3076

struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
					    struct btrfs_root *root,
3077 3078
					    u64 bytenr, u32 blocksize,
					    int level)
3079 3080 3081 3082 3083 3084 3085
{
	struct extent_buffer *buf;

	buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
	if (!buf)
		return ERR_PTR(-ENOMEM);
	btrfs_set_header_generation(buf, trans->transid);
3086
	btrfs_set_buffer_lockdep_class(buf, level);
3087 3088
	btrfs_tree_lock(buf);
	clean_tree_block(trans, root, buf);
3089 3090

	btrfs_set_lock_blocking(buf);
3091
	btrfs_set_buffer_uptodate(buf);
3092

3093 3094 3095 3096 3097
	if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
		set_extent_dirty(&root->dirty_log_pages, buf->start,
			 buf->start + buf->len - 1, GFP_NOFS);
	} else {
		set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
3098
			 buf->start + buf->len - 1, GFP_NOFS);
3099
	}
3100
	trans->blocks_used++;
3101
	/* this returns a buffer locked for blocking */
3102 3103 3104
	return buf;
}

3105 3106 3107 3108
/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
3109
struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
3110
					     struct btrfs_root *root,
Z
Zheng Yan 已提交
3111
					     u32 blocksize, u64 parent,
3112 3113 3114 3115
					     u64 root_objectid,
					     u64 ref_generation,
					     int level,
					     u64 hint,
3116
					     u64 empty_size)
3117
{
C
Chris Mason 已提交
3118
	struct btrfs_key ins;
3119
	int ret;
3120
	struct extent_buffer *buf;
3121

Z
Zheng Yan 已提交
3122
	ret = btrfs_alloc_extent(trans, root, blocksize, parent, blocksize,
3123
				 root_objectid, ref_generation, level,
Z
Zheng Yan 已提交
3124
				 empty_size, hint, (u64)-1, &ins, 0);
3125
	if (ret) {
3126 3127
		BUG_ON(ret > 0);
		return ERR_PTR(ret);
3128
	}
3129

3130 3131
	buf = btrfs_init_new_buffer(trans, root, ins.objectid,
				    blocksize, level);
3132 3133
	return buf;
}
3134

3135 3136
int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
			struct btrfs_root *root, struct extent_buffer *leaf)
3137
{
3138 3139
	u64 leaf_owner;
	u64 leaf_generation;
3140
	struct refsort *sorted;
3141
	struct btrfs_key key;
3142 3143 3144 3145
	struct btrfs_file_extent_item *fi;
	int i;
	int nritems;
	int ret;
3146 3147
	int refi = 0;
	int slot;
3148

3149 3150
	BUG_ON(!btrfs_is_leaf(leaf));
	nritems = btrfs_header_nritems(leaf);
3151 3152 3153
	leaf_owner = btrfs_header_owner(leaf);
	leaf_generation = btrfs_header_generation(leaf);

3154 3155 3156 3157 3158 3159
	sorted = kmalloc(sizeof(*sorted) * nritems, GFP_NOFS);
	/* we do this loop twice.  The first time we build a list
	 * of the extents we have a reference on, then we sort the list
	 * by bytenr.  The second time around we actually do the
	 * extent freeing.
	 */
3160
	for (i = 0; i < nritems; i++) {
3161
		u64 disk_bytenr;
3162
		cond_resched();
3163 3164

		btrfs_item_key_to_cpu(leaf, &key, i);
3165 3166

		/* only extents have references, skip everything else */
3167
		if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
3168
			continue;
3169

3170
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
3171 3172

		/* inline extents live in the btree, they don't have refs */
3173 3174
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
3175
			continue;
3176

3177
		disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
3178 3179

		/* holes don't have refs */
3180
		if (disk_bytenr == 0)
C
Chris Mason 已提交
3181
			continue;
C
Chris Mason 已提交
3182

3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206
		sorted[refi].bytenr = disk_bytenr;
		sorted[refi].slot = i;
		refi++;
	}

	if (refi == 0)
		goto out;

	sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);

	for (i = 0; i < refi; i++) {
		u64 disk_bytenr;

		disk_bytenr = sorted[i].bytenr;
		slot = sorted[i].slot;

		cond_resched();

		btrfs_item_key_to_cpu(leaf, &key, slot);
		if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
			continue;

		fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);

3207
		ret = btrfs_free_extent(trans, root, disk_bytenr,
3208
				btrfs_file_extent_disk_num_bytes(leaf, fi),
Z
Zheng Yan 已提交
3209
				leaf->start, leaf_owner, leaf_generation,
3210
				key.objectid, 0);
Z
Zheng Yan 已提交
3211
		BUG_ON(ret);
C
Chris Mason 已提交
3212 3213 3214 3215

		atomic_inc(&root->fs_info->throttle_gen);
		wake_up(&root->fs_info->transaction_throttle);
		cond_resched();
3216
	}
3217 3218
out:
	kfree(sorted);
3219 3220 3221
	return 0;
}

C
Chris Mason 已提交
3222
static noinline int cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
3223 3224
					struct btrfs_root *root,
					struct btrfs_leaf_ref *ref)
Y
Yan Zheng 已提交
3225 3226 3227
{
	int i;
	int ret;
3228 3229 3230 3231 3232
	struct btrfs_extent_info *info;
	struct refsort *sorted;

	if (ref->nritems == 0)
		return 0;
Y
Yan Zheng 已提交
3233

3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244
	sorted = kmalloc(sizeof(*sorted) * ref->nritems, GFP_NOFS);
	for (i = 0; i < ref->nritems; i++) {
		sorted[i].bytenr = ref->extents[i].bytenr;
		sorted[i].slot = i;
	}
	sort(sorted, ref->nritems, sizeof(struct refsort), refsort_cmp, NULL);

	/*
	 * the items in the ref were sorted when the ref was inserted
	 * into the ref cache, so this is already in order
	 */
Y
Yan Zheng 已提交
3245
	for (i = 0; i < ref->nritems; i++) {
3246
		info = ref->extents + sorted[i].slot;
3247
		ret = btrfs_free_extent(trans, root, info->bytenr,
Z
Zheng Yan 已提交
3248 3249
					  info->num_bytes, ref->bytenr,
					  ref->owner, ref->generation,
3250
					  info->objectid, 0);
C
Chris Mason 已提交
3251 3252 3253 3254 3255

		atomic_inc(&root->fs_info->throttle_gen);
		wake_up(&root->fs_info->transaction_throttle);
		cond_resched();

Y
Yan Zheng 已提交
3256 3257 3258 3259
		BUG_ON(ret);
		info++;
	}

3260
	kfree(sorted);
Y
Yan Zheng 已提交
3261 3262 3263
	return 0;
}

3264 3265
static int drop_snap_lookup_refcount(struct btrfs_trans_handle *trans,
				     struct btrfs_root *root, u64 start,
C
Chris Mason 已提交
3266
				     u64 len, u32 *refs)
3267
{
C
Chris Mason 已提交
3268
	int ret;
3269

3270
	ret = btrfs_lookup_extent_ref(trans, root, start, len, refs);
3271 3272
	BUG_ON(ret);

C
Chris Mason 已提交
3273
#if 0 /* some debugging code in case we see problems here */
3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293
	/* if the refs count is one, it won't get increased again.  But
	 * if the ref count is > 1, someone may be decreasing it at
	 * the same time we are.
	 */
	if (*refs != 1) {
		struct extent_buffer *eb = NULL;
		eb = btrfs_find_create_tree_block(root, start, len);
		if (eb)
			btrfs_tree_lock(eb);

		mutex_lock(&root->fs_info->alloc_mutex);
		ret = lookup_extent_ref(NULL, root, start, len, refs);
		BUG_ON(ret);
		mutex_unlock(&root->fs_info->alloc_mutex);

		if (eb) {
			btrfs_tree_unlock(eb);
			free_extent_buffer(eb);
		}
		if (*refs == 1) {
C
Chris Mason 已提交
3294 3295
			printk(KERN_ERR "btrfs block %llu went down to one "
			       "during drop_snap\n", (unsigned long long)start);
3296 3297 3298 3299 3300
		}

	}
#endif

3301
	cond_resched();
C
Chris Mason 已提交
3302
	return ret;
3303 3304
}

3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377
/*
 * this is used while deleting old snapshots, and it drops the refs
 * on a whole subtree starting from a level 1 node.
 *
 * The idea is to sort all the leaf pointers, and then drop the
 * ref on all the leaves in order.  Most of the time the leaves
 * will have ref cache entries, so no leaf IOs will be required to
 * find the extents they have references on.
 *
 * For each leaf, any references it has are also dropped in order
 *
 * This ends up dropping the references in something close to optimal
 * order for reading and modifying the extent allocation tree.
 */
static noinline int drop_level_one_refs(struct btrfs_trans_handle *trans,
					struct btrfs_root *root,
					struct btrfs_path *path)
{
	u64 bytenr;
	u64 root_owner;
	u64 root_gen;
	struct extent_buffer *eb = path->nodes[1];
	struct extent_buffer *leaf;
	struct btrfs_leaf_ref *ref;
	struct refsort *sorted = NULL;
	int nritems = btrfs_header_nritems(eb);
	int ret;
	int i;
	int refi = 0;
	int slot = path->slots[1];
	u32 blocksize = btrfs_level_size(root, 0);
	u32 refs;

	if (nritems == 0)
		goto out;

	root_owner = btrfs_header_owner(eb);
	root_gen = btrfs_header_generation(eb);
	sorted = kmalloc(sizeof(*sorted) * nritems, GFP_NOFS);

	/*
	 * step one, sort all the leaf pointers so we don't scribble
	 * randomly into the extent allocation tree
	 */
	for (i = slot; i < nritems; i++) {
		sorted[refi].bytenr = btrfs_node_blockptr(eb, i);
		sorted[refi].slot = i;
		refi++;
	}

	/*
	 * nritems won't be zero, but if we're picking up drop_snapshot
	 * after a crash, slot might be > 0, so double check things
	 * just in case.
	 */
	if (refi == 0)
		goto out;

	sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);

	/*
	 * the first loop frees everything the leaves point to
	 */
	for (i = 0; i < refi; i++) {
		u64 ptr_gen;

		bytenr = sorted[i].bytenr;

		/*
		 * check the reference count on this leaf.  If it is > 1
		 * we just decrement it below and don't update any
		 * of the refs the leaf points to.
		 */
3378 3379
		ret = drop_snap_lookup_refcount(trans, root, bytenr,
						blocksize, &refs);
3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429
		BUG_ON(ret);
		if (refs != 1)
			continue;

		ptr_gen = btrfs_node_ptr_generation(eb, sorted[i].slot);

		/*
		 * the leaf only had one reference, which means the
		 * only thing pointing to this leaf is the snapshot
		 * we're deleting.  It isn't possible for the reference
		 * count to increase again later
		 *
		 * The reference cache is checked for the leaf,
		 * and if found we'll be able to drop any refs held by
		 * the leaf without needing to read it in.
		 */
		ref = btrfs_lookup_leaf_ref(root, bytenr);
		if (ref && ref->generation != ptr_gen) {
			btrfs_free_leaf_ref(root, ref);
			ref = NULL;
		}
		if (ref) {
			ret = cache_drop_leaf_ref(trans, root, ref);
			BUG_ON(ret);
			btrfs_remove_leaf_ref(root, ref);
			btrfs_free_leaf_ref(root, ref);
		} else {
			/*
			 * the leaf wasn't in the reference cache, so
			 * we have to read it.
			 */
			leaf = read_tree_block(root, bytenr, blocksize,
					       ptr_gen);
			ret = btrfs_drop_leaf_ref(trans, root, leaf);
			BUG_ON(ret);
			free_extent_buffer(leaf);
		}
		atomic_inc(&root->fs_info->throttle_gen);
		wake_up(&root->fs_info->transaction_throttle);
		cond_resched();
	}

	/*
	 * run through the loop again to free the refs on the leaves.
	 * This is faster than doing it in the loop above because
	 * the leaves are likely to be clustered together.  We end up
	 * working in nice chunks on the extent allocation tree.
	 */
	for (i = 0; i < refi; i++) {
		bytenr = sorted[i].bytenr;
3430
		ret = btrfs_free_extent(trans, root, bytenr,
3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451
					blocksize, eb->start,
					root_owner, root_gen, 0, 1);
		BUG_ON(ret);

		atomic_inc(&root->fs_info->throttle_gen);
		wake_up(&root->fs_info->transaction_throttle);
		cond_resched();
	}
out:
	kfree(sorted);

	/*
	 * update the path to show we've processed the entire level 1
	 * node.  This will get saved into the root's drop_snapshot_progress
	 * field so these drops are not repeated again if this transaction
	 * commits.
	 */
	path->slots[1] = nritems;
	return 0;
}

C
Chris Mason 已提交
3452 3453 3454 3455
/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
C
Chris Mason 已提交
3456
static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
3457 3458
				   struct btrfs_root *root,
				   struct btrfs_path *path, int *level)
C
Chris Mason 已提交
3459
{
3460 3461 3462
	u64 root_owner;
	u64 root_gen;
	u64 bytenr;
3463
	u64 ptr_gen;
3464 3465
	struct extent_buffer *next;
	struct extent_buffer *cur;
3466
	struct extent_buffer *parent;
3467
	u32 blocksize;
C
Chris Mason 已提交
3468 3469 3470
	int ret;
	u32 refs;

3471 3472
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
3473
	ret = drop_snap_lookup_refcount(trans, root, path->nodes[*level]->start,
3474
				path->nodes[*level]->len, &refs);
C
Chris Mason 已提交
3475 3476 3477
	BUG_ON(ret);
	if (refs > 1)
		goto out;
3478

C
Chris Mason 已提交
3479 3480 3481
	/*
	 * walk down to the last node level and free all the leaves
	 */
C
Chris Mason 已提交
3482
	while (*level >= 0) {
3483 3484
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
3485
		cur = path->nodes[*level];
3486

3487
		if (btrfs_header_level(cur) != *level)
C
Chris Mason 已提交
3488
			WARN_ON(1);
3489

3490
		if (path->slots[*level] >=
3491
		    btrfs_header_nritems(cur))
C
Chris Mason 已提交
3492
			break;
3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503

		/* the new code goes down to level 1 and does all the
		 * leaves pointed to that node in bulk.  So, this check
		 * for level 0 will always be false.
		 *
		 * But, the disk format allows the drop_snapshot_progress
		 * field in the root to leave things in a state where
		 * a leaf will need cleaning up here.  If someone crashes
		 * with the old code and then boots with the new code,
		 * we might find a leaf here.
		 */
3504
		if (*level == 0) {
3505
			ret = btrfs_drop_leaf_ref(trans, root, cur);
3506 3507 3508
			BUG_ON(ret);
			break;
		}
3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519

		/*
		 * once we get to level one, process the whole node
		 * at once, including everything below it.
		 */
		if (*level == 1) {
			ret = drop_level_one_refs(trans, root, path);
			BUG_ON(ret);
			break;
		}

3520
		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
3521
		ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
3522
		blocksize = btrfs_level_size(root, *level - 1);
3523

3524 3525
		ret = drop_snap_lookup_refcount(trans, root, bytenr,
						blocksize, &refs);
3526
		BUG_ON(ret);
3527 3528 3529 3530 3531 3532 3533

		/*
		 * if there is more than one reference, we don't need
		 * to read that node to drop any references it has.  We
		 * just drop the ref we hold on that node and move on to the
		 * next slot in this level.
		 */
3534
		if (refs != 1) {
3535 3536 3537
			parent = path->nodes[*level];
			root_owner = btrfs_header_owner(parent);
			root_gen = btrfs_header_generation(parent);
C
Chris Mason 已提交
3538
			path->slots[*level]++;
3539

3540
			ret = btrfs_free_extent(trans, root, bytenr,
Z
Zheng Yan 已提交
3541
						blocksize, parent->start,
3542 3543
						root_owner, root_gen,
						*level - 1, 1);
C
Chris Mason 已提交
3544
			BUG_ON(ret);
3545 3546 3547

			atomic_inc(&root->fs_info->throttle_gen);
			wake_up(&root->fs_info->transaction_throttle);
C
Chris Mason 已提交
3548
			cond_resched();
3549

C
Chris Mason 已提交
3550 3551
			continue;
		}
3552

3553
		/*
3554 3555
		 * we need to keep freeing things in the next level down.
		 * read the block and loop around to process it
3556
		 */
3557
		next = read_tree_block(root, bytenr, blocksize, ptr_gen);
3558
		WARN_ON(*level <= 0);
C
Chris Mason 已提交
3559
		if (path->nodes[*level-1])
3560
			free_extent_buffer(path->nodes[*level-1]);
C
Chris Mason 已提交
3561
		path->nodes[*level-1] = next;
3562
		*level = btrfs_header_level(next);
C
Chris Mason 已提交
3563
		path->slots[*level] = 0;
C
Chris Mason 已提交
3564
		cond_resched();
C
Chris Mason 已提交
3565 3566
	}
out:
3567 3568
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
3569 3570 3571

	if (path->nodes[*level] == root->node) {
		parent = path->nodes[*level];
Y
Yan Zheng 已提交
3572
		bytenr = path->nodes[*level]->start;
3573 3574
	} else {
		parent = path->nodes[*level + 1];
Y
Yan Zheng 已提交
3575
		bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
3576 3577
	}

Y
Yan Zheng 已提交
3578 3579
	blocksize = btrfs_level_size(root, *level);
	root_owner = btrfs_header_owner(parent);
3580
	root_gen = btrfs_header_generation(parent);
Y
Yan Zheng 已提交
3581

3582 3583 3584 3585
	/*
	 * cleanup and free the reference on the last node
	 * we processed
	 */
3586
	ret = btrfs_free_extent(trans, root, bytenr, blocksize,
Z
Zheng Yan 已提交
3587
				  parent->start, root_owner, root_gen,
3588
				  *level, 1);
3589
	free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
3590
	path->nodes[*level] = NULL;
3591

C
Chris Mason 已提交
3592 3593
	*level += 1;
	BUG_ON(ret);
3594

3595
	cond_resched();
C
Chris Mason 已提交
3596 3597 3598
	return 0;
}

Y
Yan Zheng 已提交
3599 3600 3601 3602 3603
/*
 * helper function for drop_subtree, this function is similar to
 * walk_down_tree. The main difference is that it checks reference
 * counts while tree blocks are locked.
 */
C
Chris Mason 已提交
3604
static noinline int walk_down_subtree(struct btrfs_trans_handle *trans,
Y
Yan Zheng 已提交
3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642
				      struct btrfs_root *root,
				      struct btrfs_path *path, int *level)
{
	struct extent_buffer *next;
	struct extent_buffer *cur;
	struct extent_buffer *parent;
	u64 bytenr;
	u64 ptr_gen;
	u32 blocksize;
	u32 refs;
	int ret;

	cur = path->nodes[*level];
	ret = btrfs_lookup_extent_ref(trans, root, cur->start, cur->len,
				      &refs);
	BUG_ON(ret);
	if (refs > 1)
		goto out;

	while (*level >= 0) {
		cur = path->nodes[*level];
		if (*level == 0) {
			ret = btrfs_drop_leaf_ref(trans, root, cur);
			BUG_ON(ret);
			clean_tree_block(trans, root, cur);
			break;
		}
		if (path->slots[*level] >= btrfs_header_nritems(cur)) {
			clean_tree_block(trans, root, cur);
			break;
		}

		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
		blocksize = btrfs_level_size(root, *level - 1);
		ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);

		next = read_tree_block(root, bytenr, blocksize, ptr_gen);
		btrfs_tree_lock(next);
3643
		btrfs_set_lock_blocking(next);
Y
Yan Zheng 已提交
3644 3645 3646 3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 3688

		ret = btrfs_lookup_extent_ref(trans, root, bytenr, blocksize,
					      &refs);
		BUG_ON(ret);
		if (refs > 1) {
			parent = path->nodes[*level];
			ret = btrfs_free_extent(trans, root, bytenr,
					blocksize, parent->start,
					btrfs_header_owner(parent),
					btrfs_header_generation(parent),
					*level - 1, 1);
			BUG_ON(ret);
			path->slots[*level]++;
			btrfs_tree_unlock(next);
			free_extent_buffer(next);
			continue;
		}

		*level = btrfs_header_level(next);
		path->nodes[*level] = next;
		path->slots[*level] = 0;
		path->locks[*level] = 1;
		cond_resched();
	}
out:
	parent = path->nodes[*level + 1];
	bytenr = path->nodes[*level]->start;
	blocksize = path->nodes[*level]->len;

	ret = btrfs_free_extent(trans, root, bytenr, blocksize,
			parent->start, btrfs_header_owner(parent),
			btrfs_header_generation(parent), *level, 1);
	BUG_ON(ret);

	if (path->locks[*level]) {
		btrfs_tree_unlock(path->nodes[*level]);
		path->locks[*level] = 0;
	}
	free_extent_buffer(path->nodes[*level]);
	path->nodes[*level] = NULL;
	*level += 1;
	cond_resched();
	return 0;
}

C
Chris Mason 已提交
3689 3690 3691 3692 3693
/*
 * helper for dropping snapshots.  This walks back up the tree in the path
 * to find the first node higher up where we haven't yet gone through
 * all the slots
 */
C
Chris Mason 已提交
3694
static noinline int walk_up_tree(struct btrfs_trans_handle *trans,
3695
				 struct btrfs_root *root,
Y
Yan Zheng 已提交
3696 3697
				 struct btrfs_path *path,
				 int *level, int max_level)
C
Chris Mason 已提交
3698
{
3699 3700 3701
	u64 root_owner;
	u64 root_gen;
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
3702 3703 3704
	int i;
	int slot;
	int ret;
3705

Y
Yan Zheng 已提交
3706
	for (i = *level; i < max_level && path->nodes[i]; i++) {
C
Chris Mason 已提交
3707
		slot = path->slots[i];
3708 3709 3710
		if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
			struct extent_buffer *node;
			struct btrfs_disk_key disk_key;
3711 3712 3713 3714 3715 3716 3717

			/*
			 * there is more work to do in this level.
			 * Update the drop_progress marker to reflect
			 * the work we've done so far, and then bump
			 * the slot number
			 */
3718
			node = path->nodes[i];
C
Chris Mason 已提交
3719 3720
			path->slots[i]++;
			*level = i;
3721
			WARN_ON(*level == 0);
3722
			btrfs_node_key(node, &disk_key, path->slots[i]);
3723
			memcpy(&root_item->drop_progress,
3724
			       &disk_key, sizeof(disk_key));
3725
			root_item->drop_level = i;
C
Chris Mason 已提交
3726 3727
			return 0;
		} else {
Z
Zheng Yan 已提交
3728
			struct extent_buffer *parent;
3729 3730 3731 3732 3733

			/*
			 * this whole node is done, free our reference
			 * on it and go up one level
			 */
Z
Zheng Yan 已提交
3734 3735 3736 3737 3738 3739 3740
			if (path->nodes[*level] == root->node)
				parent = path->nodes[*level];
			else
				parent = path->nodes[*level + 1];

			root_owner = btrfs_header_owner(parent);
			root_gen = btrfs_header_generation(parent);
Y
Yan Zheng 已提交
3741 3742

			clean_tree_block(trans, root, path->nodes[*level]);
3743
			ret = btrfs_free_extent(trans, root,
3744
						path->nodes[*level]->start,
3745
						path->nodes[*level]->len,
3746 3747
						parent->start, root_owner,
						root_gen, *level, 1);
3748
			BUG_ON(ret);
Y
Yan Zheng 已提交
3749 3750 3751 3752
			if (path->locks[*level]) {
				btrfs_tree_unlock(path->nodes[*level]);
				path->locks[*level] = 0;
			}
3753
			free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
3754
			path->nodes[*level] = NULL;
C
Chris Mason 已提交
3755 3756 3757 3758 3759 3760
			*level = i + 1;
		}
	}
	return 1;
}

C
Chris Mason 已提交
3761 3762 3763 3764 3765
/*
 * drop the reference count on the tree rooted at 'snap'.  This traverses
 * the tree freeing any blocks that have a ref count of zero after being
 * decremented.
 */
3766
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
3767
			*root)
C
Chris Mason 已提交
3768
{
3769
	int ret = 0;
C
Chris Mason 已提交
3770
	int wret;
C
Chris Mason 已提交
3771
	int level;
3772
	struct btrfs_path *path;
C
Chris Mason 已提交
3773 3774
	int i;
	int orig_level;
3775
	int update_count;
3776
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
3777

3778
	WARN_ON(!mutex_is_locked(&root->fs_info->drop_mutex));
3779 3780
	path = btrfs_alloc_path();
	BUG_ON(!path);
C
Chris Mason 已提交
3781

3782
	level = btrfs_header_level(root->node);
C
Chris Mason 已提交
3783
	orig_level = level;
3784 3785
	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
		path->nodes[level] = root->node;
3786
		extent_buffer_get(root->node);
3787 3788 3789
		path->slots[level] = 0;
	} else {
		struct btrfs_key key;
3790 3791
		struct btrfs_disk_key found_key;
		struct extent_buffer *node;
3792

3793
		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
3794 3795
		level = root_item->drop_level;
		path->lowest_level = level;
3796
		wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3797
		if (wret < 0) {
3798 3799 3800
			ret = wret;
			goto out;
		}
3801 3802 3803 3804
		node = path->nodes[level];
		btrfs_node_key(node, &found_key, path->slots[level]);
		WARN_ON(memcmp(&found_key, &root_item->drop_progress,
			       sizeof(found_key)));
3805 3806 3807 3808
		/*
		 * unlock our path, this is safe because only this
		 * function is allowed to delete this snapshot
		 */
3809 3810 3811 3812 3813 3814
		for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
			if (path->nodes[i] && path->locks[i]) {
				path->locks[i] = 0;
				btrfs_tree_unlock(path->nodes[i]);
			}
		}
3815
	}
C
Chris Mason 已提交
3816
	while (1) {
3817
		unsigned long update;
3818
		wret = walk_down_tree(trans, root, path, &level);
C
Chris Mason 已提交
3819
		if (wret > 0)
C
Chris Mason 已提交
3820
			break;
C
Chris Mason 已提交
3821 3822 3823
		if (wret < 0)
			ret = wret;

Y
Yan Zheng 已提交
3824 3825
		wret = walk_up_tree(trans, root, path, &level,
				    BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
3826
		if (wret > 0)
C
Chris Mason 已提交
3827
			break;
C
Chris Mason 已提交
3828 3829
		if (wret < 0)
			ret = wret;
3830 3831
		if (trans->transaction->in_commit ||
		    trans->transaction->delayed_refs.flushing) {
3832 3833 3834
			ret = -EAGAIN;
			break;
		}
3835
		atomic_inc(&root->fs_info->throttle_gen);
C
Chris Mason 已提交
3836
		wake_up(&root->fs_info->transaction_throttle);
3837 3838 3839 3840 3841 3842 3843 3844
		for (update_count = 0; update_count < 16; update_count++) {
			update = trans->delayed_ref_updates;
			trans->delayed_ref_updates = 0;
			if (update)
				btrfs_run_delayed_refs(trans, root, update);
			else
				break;
		}
C
Chris Mason 已提交
3845
	}
C
Chris Mason 已提交
3846
	for (i = 0; i <= orig_level; i++) {
3847
		if (path->nodes[i]) {
3848
			free_extent_buffer(path->nodes[i]);
3849
			path->nodes[i] = NULL;
C
Chris Mason 已提交
3850
		}
C
Chris Mason 已提交
3851
	}
3852
out:
3853
	btrfs_free_path(path);
C
Chris Mason 已提交
3854
	return ret;
C
Chris Mason 已提交
3855
}
C
Chris Mason 已提交
3856

Y
Yan Zheng 已提交
3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 3870
int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
			struct btrfs_root *root,
			struct extent_buffer *node,
			struct extent_buffer *parent)
{
	struct btrfs_path *path;
	int level;
	int parent_level;
	int ret = 0;
	int wret;

	path = btrfs_alloc_path();
	BUG_ON(!path);

3871
	btrfs_assert_tree_locked(parent);
Y
Yan Zheng 已提交
3872 3873 3874 3875 3876
	parent_level = btrfs_header_level(parent);
	extent_buffer_get(parent);
	path->nodes[parent_level] = parent;
	path->slots[parent_level] = btrfs_header_nritems(parent);

3877
	btrfs_assert_tree_locked(node);
Y
Yan Zheng 已提交
3878 3879 3880 3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900
	level = btrfs_header_level(node);
	extent_buffer_get(node);
	path->nodes[level] = node;
	path->slots[level] = 0;

	while (1) {
		wret = walk_down_subtree(trans, root, path, &level);
		if (wret < 0)
			ret = wret;
		if (wret != 0)
			break;

		wret = walk_up_tree(trans, root, path, &level, parent_level);
		if (wret < 0)
			ret = wret;
		if (wret != 0)
			break;
	}

	btrfs_free_path(path);
	return ret;
}

3901 3902 3903 3904 3905 3906
static unsigned long calc_ra(unsigned long start, unsigned long last,
			     unsigned long nr)
{
	return min(last, start + nr - 1);
}

C
Chris Mason 已提交
3907
static noinline int relocate_inode_pages(struct inode *inode, u64 start,
3908
					 u64 len)
3909 3910 3911
{
	u64 page_start;
	u64 page_end;
Z
Zheng Yan 已提交
3912
	unsigned long first_index;
3913 3914 3915
	unsigned long last_index;
	unsigned long i;
	struct page *page;
3916
	struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
3917
	struct file_ra_state *ra;
3918
	struct btrfs_ordered_extent *ordered;
Z
Zheng Yan 已提交
3919 3920 3921
	unsigned int total_read = 0;
	unsigned int total_dirty = 0;
	int ret = 0;
3922 3923

	ra = kzalloc(sizeof(*ra), GFP_NOFS);
3924 3925

	mutex_lock(&inode->i_mutex);
Z
Zheng Yan 已提交
3926
	first_index = start >> PAGE_CACHE_SHIFT;
3927 3928
	last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;

Z
Zheng Yan 已提交
3929 3930 3931 3932 3933
	/* make sure the dirty trick played by the caller work */
	ret = invalidate_inode_pages2_range(inode->i_mapping,
					    first_index, last_index);
	if (ret)
		goto out_unlock;
3934

3935
	file_ra_state_init(ra, inode->i_mapping);
3936

Z
Zheng Yan 已提交
3937 3938
	for (i = first_index ; i <= last_index; i++) {
		if (total_read % ra->ra_pages == 0) {
3939
			btrfs_force_ra(inode->i_mapping, ra, NULL, i,
Z
Zheng Yan 已提交
3940
				       calc_ra(i, last_index, ra->ra_pages));
3941 3942
		}
		total_read++;
3943 3944
again:
		if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
Z
Zheng Yan 已提交
3945
			BUG_ON(1);
3946
		page = grab_cache_page(inode->i_mapping, i);
3947
		if (!page) {
Z
Zheng Yan 已提交
3948
			ret = -ENOMEM;
3949
			goto out_unlock;
3950
		}
3951 3952 3953 3954 3955 3956
		if (!PageUptodate(page)) {
			btrfs_readpage(NULL, page);
			lock_page(page);
			if (!PageUptodate(page)) {
				unlock_page(page);
				page_cache_release(page);
Z
Zheng Yan 已提交
3957
				ret = -EIO;
3958 3959 3960
				goto out_unlock;
			}
		}
3961
		wait_on_page_writeback(page);
3962

3963 3964
		page_start = (u64)page->index << PAGE_CACHE_SHIFT;
		page_end = page_start + PAGE_CACHE_SIZE - 1;
3965
		lock_extent(io_tree, page_start, page_end, GFP_NOFS);
3966

3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977
		ordered = btrfs_lookup_ordered_extent(inode, page_start);
		if (ordered) {
			unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
			unlock_page(page);
			page_cache_release(page);
			btrfs_start_ordered_extent(inode, ordered, 1);
			btrfs_put_ordered_extent(ordered);
			goto again;
		}
		set_page_extent_mapped(page);

Z
Zheng Yan 已提交
3978 3979 3980
		if (i == first_index)
			set_extent_bits(io_tree, page_start, page_end,
					EXTENT_BOUNDARY, GFP_NOFS);
3981
		btrfs_set_extent_delalloc(inode, page_start, page_end);
Z
Zheng Yan 已提交
3982

3983
		set_page_dirty(page);
Z
Zheng Yan 已提交
3984
		total_dirty++;
3985

3986
		unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
3987 3988 3989 3990 3991
		unlock_page(page);
		page_cache_release(page);
	}

out_unlock:
3992
	kfree(ra);
3993
	mutex_unlock(&inode->i_mutex);
Z
Zheng Yan 已提交
3994 3995
	balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
	return ret;
3996 3997
}

C
Chris Mason 已提交
3998
static noinline int relocate_data_extent(struct inode *reloc_inode,
Z
Zheng Yan 已提交
3999 4000 4001 4002 4003 4004
					 struct btrfs_key *extent_key,
					 u64 offset)
{
	struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
	struct extent_map_tree *em_tree = &BTRFS_I(reloc_inode)->extent_tree;
	struct extent_map *em;
Y
Yan Zheng 已提交
4005 4006
	u64 start = extent_key->objectid - offset;
	u64 end = start + extent_key->offset - 1;
4007

Z
Zheng Yan 已提交
4008 4009
	em = alloc_extent_map(GFP_NOFS);
	BUG_ON(!em || IS_ERR(em));
4010

Y
Yan Zheng 已提交
4011
	em->start = start;
Z
Zheng Yan 已提交
4012
	em->len = extent_key->offset;
C
Chris Mason 已提交
4013
	em->block_len = extent_key->offset;
Z
Zheng Yan 已提交
4014 4015 4016 4017 4018
	em->block_start = extent_key->objectid;
	em->bdev = root->fs_info->fs_devices->latest_bdev;
	set_bit(EXTENT_FLAG_PINNED, &em->flags);

	/* setup extent map to cheat btrfs_readpage */
Y
Yan Zheng 已提交
4019
	lock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
Z
Zheng Yan 已提交
4020 4021 4022 4023 4024 4025 4026
	while (1) {
		int ret;
		spin_lock(&em_tree->lock);
		ret = add_extent_mapping(em_tree, em);
		spin_unlock(&em_tree->lock);
		if (ret != -EEXIST) {
			free_extent_map(em);
4027 4028
			break;
		}
Y
Yan Zheng 已提交
4029
		btrfs_drop_extent_cache(reloc_inode, start, end, 0);
4030
	}
Y
Yan Zheng 已提交
4031
	unlock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4032

Y
Yan Zheng 已提交
4033
	return relocate_inode_pages(reloc_inode, start, extent_key->offset);
Z
Zheng Yan 已提交
4034
}
4035

Z
Zheng Yan 已提交
4036 4037 4038 4039 4040 4041 4042 4043 4044
struct btrfs_ref_path {
	u64 extent_start;
	u64 nodes[BTRFS_MAX_LEVEL];
	u64 root_objectid;
	u64 root_generation;
	u64 owner_objectid;
	u32 num_refs;
	int lowest_level;
	int current_level;
Y
Yan Zheng 已提交
4045 4046 4047 4048
	int shared_level;

	struct btrfs_key node_keys[BTRFS_MAX_LEVEL];
	u64 new_nodes[BTRFS_MAX_LEVEL];
Z
Zheng Yan 已提交
4049
};
4050

Z
Zheng Yan 已提交
4051
struct disk_extent {
C
Chris Mason 已提交
4052
	u64 ram_bytes;
Z
Zheng Yan 已提交
4053 4054 4055 4056
	u64 disk_bytenr;
	u64 disk_num_bytes;
	u64 offset;
	u64 num_bytes;
C
Chris Mason 已提交
4057 4058 4059
	u8 compression;
	u8 encryption;
	u16 other_encoding;
Z
Zheng Yan 已提交
4060
};
4061

Z
Zheng Yan 已提交
4062 4063 4064 4065 4066 4067
static int is_cowonly_root(u64 root_objectid)
{
	if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
	    root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
	    root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
	    root_objectid == BTRFS_DEV_TREE_OBJECTID ||
4068 4069
	    root_objectid == BTRFS_TREE_LOG_OBJECTID ||
	    root_objectid == BTRFS_CSUM_TREE_OBJECTID)
Z
Zheng Yan 已提交
4070 4071 4072
		return 1;
	return 0;
}
4073

C
Chris Mason 已提交
4074
static noinline int __next_ref_path(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087
				    struct btrfs_root *extent_root,
				    struct btrfs_ref_path *ref_path,
				    int first_time)
{
	struct extent_buffer *leaf;
	struct btrfs_path *path;
	struct btrfs_extent_ref *ref;
	struct btrfs_key key;
	struct btrfs_key found_key;
	u64 bytenr;
	u32 nritems;
	int level;
	int ret = 1;
4088

Z
Zheng Yan 已提交
4089 4090 4091
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
4092

Z
Zheng Yan 已提交
4093 4094 4095
	if (first_time) {
		ref_path->lowest_level = -1;
		ref_path->current_level = -1;
Y
Yan Zheng 已提交
4096
		ref_path->shared_level = -1;
Z
Zheng Yan 已提交
4097 4098 4099 4100 4101 4102 4103 4104
		goto walk_up;
	}
walk_down:
	level = ref_path->current_level - 1;
	while (level >= -1) {
		u64 parent;
		if (level < ref_path->lowest_level)
			break;
4105

C
Chris Mason 已提交
4106
		if (level >= 0)
Z
Zheng Yan 已提交
4107
			bytenr = ref_path->nodes[level];
C
Chris Mason 已提交
4108
		else
Z
Zheng Yan 已提交
4109 4110
			bytenr = ref_path->extent_start;
		BUG_ON(bytenr == 0);
4111

Z
Zheng Yan 已提交
4112 4113 4114 4115
		parent = ref_path->nodes[level + 1];
		ref_path->nodes[level + 1] = 0;
		ref_path->current_level = level;
		BUG_ON(parent == 0);
C
Chris Mason 已提交
4116

Z
Zheng Yan 已提交
4117 4118 4119
		key.objectid = bytenr;
		key.offset = parent + 1;
		key.type = BTRFS_EXTENT_REF_KEY;
4120

Z
Zheng Yan 已提交
4121 4122
		ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
		if (ret < 0)
4123
			goto out;
Z
Zheng Yan 已提交
4124
		BUG_ON(ret == 0);
4125

Z
Zheng Yan 已提交
4126 4127 4128 4129 4130 4131 4132 4133 4134 4135
		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(extent_root, path);
			if (ret < 0)
				goto out;
			if (ret > 0)
				goto next;
			leaf = path->nodes[0];
		}
C
Chris Mason 已提交
4136

Z
Zheng Yan 已提交
4137 4138
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.objectid == bytenr &&
Y
Yan Zheng 已提交
4139 4140 4141
		    found_key.type == BTRFS_EXTENT_REF_KEY) {
			if (level < ref_path->shared_level)
				ref_path->shared_level = level;
Z
Zheng Yan 已提交
4142
			goto found;
Y
Yan Zheng 已提交
4143
		}
Z
Zheng Yan 已提交
4144 4145 4146
next:
		level--;
		btrfs_release_path(extent_root, path);
Y
Yan Zheng 已提交
4147
		cond_resched();
Z
Zheng Yan 已提交
4148 4149 4150 4151 4152 4153 4154 4155
	}
	/* reached lowest level */
	ret = 1;
	goto out;
walk_up:
	level = ref_path->current_level;
	while (level < BTRFS_MAX_LEVEL - 1) {
		u64 ref_objectid;
C
Chris Mason 已提交
4156 4157

		if (level >= 0)
Z
Zheng Yan 已提交
4158
			bytenr = ref_path->nodes[level];
C
Chris Mason 已提交
4159
		else
Z
Zheng Yan 已提交
4160
			bytenr = ref_path->extent_start;
C
Chris Mason 已提交
4161

Z
Zheng Yan 已提交
4162
		BUG_ON(bytenr == 0);
4163

Z
Zheng Yan 已提交
4164 4165 4166
		key.objectid = bytenr;
		key.offset = 0;
		key.type = BTRFS_EXTENT_REF_KEY;
4167

Z
Zheng Yan 已提交
4168 4169 4170
		ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
		if (ret < 0)
			goto out;
4171

Z
Zheng Yan 已提交
4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186
		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(extent_root, path);
			if (ret < 0)
				goto out;
			if (ret > 0) {
				/* the extent was freed by someone */
				if (ref_path->lowest_level == level)
					goto out;
				btrfs_release_path(extent_root, path);
				goto walk_down;
			}
			leaf = path->nodes[0];
		}
4187

Z
Zheng Yan 已提交
4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.objectid != bytenr ||
				found_key.type != BTRFS_EXTENT_REF_KEY) {
			/* the extent was freed by someone */
			if (ref_path->lowest_level == level) {
				ret = 1;
				goto out;
			}
			btrfs_release_path(extent_root, path);
			goto walk_down;
		}
found:
		ref = btrfs_item_ptr(leaf, path->slots[0],
				struct btrfs_extent_ref);
		ref_objectid = btrfs_ref_objectid(leaf, ref);
		if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
			if (first_time) {
				level = (int)ref_objectid;
				BUG_ON(level >= BTRFS_MAX_LEVEL);
				ref_path->lowest_level = level;
				ref_path->current_level = level;
				ref_path->nodes[level] = bytenr;
			} else {
				WARN_ON(ref_objectid != level);
			}
		} else {
			WARN_ON(level != -1);
		}
		first_time = 0;
4217

Z
Zheng Yan 已提交
4218 4219 4220 4221
		if (ref_path->lowest_level == level) {
			ref_path->owner_objectid = ref_objectid;
			ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
		}
4222

4223
		/*
Z
Zheng Yan 已提交
4224 4225
		 * the block is tree root or the block isn't in reference
		 * counted tree.
4226
		 */
Z
Zheng Yan 已提交
4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239
		if (found_key.objectid == found_key.offset ||
		    is_cowonly_root(btrfs_ref_root(leaf, ref))) {
			ref_path->root_objectid = btrfs_ref_root(leaf, ref);
			ref_path->root_generation =
				btrfs_ref_generation(leaf, ref);
			if (level < 0) {
				/* special reference from the tree log */
				ref_path->nodes[0] = found_key.offset;
				ref_path->current_level = 0;
			}
			ret = 0;
			goto out;
		}
4240

Z
Zheng Yan 已提交
4241 4242 4243 4244
		level++;
		BUG_ON(ref_path->nodes[level] != 0);
		ref_path->nodes[level] = found_key.offset;
		ref_path->current_level = level;
4245

Z
Zheng Yan 已提交
4246 4247 4248 4249 4250 4251 4252 4253 4254 4255
		/*
		 * the reference was created in the running transaction,
		 * no need to continue walking up.
		 */
		if (btrfs_ref_generation(leaf, ref) == trans->transid) {
			ref_path->root_objectid = btrfs_ref_root(leaf, ref);
			ref_path->root_generation =
				btrfs_ref_generation(leaf, ref);
			ret = 0;
			goto out;
4256 4257
		}

Z
Zheng Yan 已提交
4258
		btrfs_release_path(extent_root, path);
Y
Yan Zheng 已提交
4259
		cond_resched();
4260
	}
Z
Zheng Yan 已提交
4261 4262
	/* reached max tree level, but no tree root found. */
	BUG();
4263
out:
Z
Zheng Yan 已提交
4264 4265
	btrfs_free_path(path);
	return ret;
4266 4267
}

Z
Zheng Yan 已提交
4268 4269 4270 4271
static int btrfs_first_ref_path(struct btrfs_trans_handle *trans,
				struct btrfs_root *extent_root,
				struct btrfs_ref_path *ref_path,
				u64 extent_start)
4272
{
Z
Zheng Yan 已提交
4273 4274
	memset(ref_path, 0, sizeof(*ref_path));
	ref_path->extent_start = extent_start;
4275

Z
Zheng Yan 已提交
4276
	return __next_ref_path(trans, extent_root, ref_path, 1);
4277 4278
}

Z
Zheng Yan 已提交
4279 4280 4281
static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
			       struct btrfs_root *extent_root,
			       struct btrfs_ref_path *ref_path)
4282
{
Z
Zheng Yan 已提交
4283 4284 4285
	return __next_ref_path(trans, extent_root, ref_path, 0);
}

C
Chris Mason 已提交
4286
static noinline int get_new_locations(struct inode *reloc_inode,
Z
Zheng Yan 已提交
4287 4288 4289 4290 4291 4292 4293 4294
				      struct btrfs_key *extent_key,
				      u64 offset, int no_fragment,
				      struct disk_extent **extents,
				      int *nr_extents)
{
	struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
	struct btrfs_path *path;
	struct btrfs_file_extent_item *fi;
4295
	struct extent_buffer *leaf;
Z
Zheng Yan 已提交
4296 4297 4298 4299
	struct disk_extent *exts = *extents;
	struct btrfs_key found_key;
	u64 cur_pos;
	u64 last_byte;
4300
	u32 nritems;
Z
Zheng Yan 已提交
4301 4302 4303
	int nr = 0;
	int max = *nr_extents;
	int ret;
4304

Z
Zheng Yan 已提交
4305 4306 4307 4308 4309 4310
	WARN_ON(!no_fragment && *extents);
	if (!exts) {
		max = 1;
		exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
		if (!exts)
			return -ENOMEM;
4311
	}
4312

Z
Zheng Yan 已提交
4313 4314
	path = btrfs_alloc_path();
	BUG_ON(!path);
4315

Z
Zheng Yan 已提交
4316 4317 4318 4319 4320 4321 4322 4323 4324 4325
	cur_pos = extent_key->objectid - offset;
	last_byte = extent_key->objectid + extent_key->offset;
	ret = btrfs_lookup_file_extent(NULL, root, path, reloc_inode->i_ino,
				       cur_pos, 0);
	if (ret < 0)
		goto out;
	if (ret > 0) {
		ret = -ENOENT;
		goto out;
	}
4326

Z
Zheng Yan 已提交
4327
	while (1) {
4328 4329
		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
Z
Zheng Yan 已提交
4330 4331
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(root, path);
4332 4333
			if (ret < 0)
				goto out;
Z
Zheng Yan 已提交
4334 4335
			if (ret > 0)
				break;
4336
			leaf = path->nodes[0];
4337
		}
4338 4339

		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
Z
Zheng Yan 已提交
4340 4341 4342
		if (found_key.offset != cur_pos ||
		    found_key.type != BTRFS_EXTENT_DATA_KEY ||
		    found_key.objectid != reloc_inode->i_ino)
4343 4344
			break;

Z
Zheng Yan 已提交
4345 4346 4347 4348 4349
		fi = btrfs_item_ptr(leaf, path->slots[0],
				    struct btrfs_file_extent_item);
		if (btrfs_file_extent_type(leaf, fi) !=
		    BTRFS_FILE_EXTENT_REG ||
		    btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
4350
			break;
Z
Zheng Yan 已提交
4351 4352 4353 4354 4355 4356 4357 4358

		if (nr == max) {
			struct disk_extent *old = exts;
			max *= 2;
			exts = kzalloc(sizeof(*exts) * max, GFP_NOFS);
			memcpy(exts, old, sizeof(*exts) * nr);
			if (old != *extents)
				kfree(old);
4359
		}
4360

Z
Zheng Yan 已提交
4361 4362 4363 4364 4365 4366
		exts[nr].disk_bytenr =
			btrfs_file_extent_disk_bytenr(leaf, fi);
		exts[nr].disk_num_bytes =
			btrfs_file_extent_disk_num_bytes(leaf, fi);
		exts[nr].offset = btrfs_file_extent_offset(leaf, fi);
		exts[nr].num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
C
Chris Mason 已提交
4367 4368 4369 4370 4371
		exts[nr].ram_bytes = btrfs_file_extent_ram_bytes(leaf, fi);
		exts[nr].compression = btrfs_file_extent_compression(leaf, fi);
		exts[nr].encryption = btrfs_file_extent_encryption(leaf, fi);
		exts[nr].other_encoding = btrfs_file_extent_other_encoding(leaf,
									   fi);
Y
Yan Zheng 已提交
4372 4373 4374
		BUG_ON(exts[nr].offset > 0);
		BUG_ON(exts[nr].compression || exts[nr].encryption);
		BUG_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
4375

Z
Zheng Yan 已提交
4376 4377 4378 4379 4380 4381 4382 4383
		cur_pos += exts[nr].num_bytes;
		nr++;

		if (cur_pos + offset >= last_byte)
			break;

		if (no_fragment) {
			ret = 1;
4384
			goto out;
Z
Zheng Yan 已提交
4385 4386 4387 4388
		}
		path->slots[0]++;
	}

4389
	BUG_ON(cur_pos + offset > last_byte);
Z
Zheng Yan 已提交
4390 4391 4392
	if (cur_pos + offset < last_byte) {
		ret = -ENOENT;
		goto out;
4393 4394 4395
	}
	ret = 0;
out:
Z
Zheng Yan 已提交
4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406
	btrfs_free_path(path);
	if (ret) {
		if (exts != *extents)
			kfree(exts);
	} else {
		*extents = exts;
		*nr_extents = nr;
	}
	return ret;
}

C
Chris Mason 已提交
4407
static noinline int replace_one_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
4408 4409 4410 4411 4412 4413 4414 4415 4416 4417 4418 4419 4420 4421 4422 4423
					struct btrfs_root *root,
					struct btrfs_path *path,
					struct btrfs_key *extent_key,
					struct btrfs_key *leaf_key,
					struct btrfs_ref_path *ref_path,
					struct disk_extent *new_extents,
					int nr_extents)
{
	struct extent_buffer *leaf;
	struct btrfs_file_extent_item *fi;
	struct inode *inode = NULL;
	struct btrfs_key key;
	u64 lock_start = 0;
	u64 lock_end = 0;
	u64 num_bytes;
	u64 ext_offset;
4424
	u64 search_end = (u64)-1;
Z
Zheng Yan 已提交
4425
	u32 nritems;
4426
	int nr_scaned = 0;
Z
Zheng Yan 已提交
4427
	int extent_locked = 0;
Y
Yan Zheng 已提交
4428
	int extent_type;
Z
Zheng Yan 已提交
4429 4430
	int ret;

4431
	memcpy(&key, leaf_key, sizeof(key));
Z
Zheng Yan 已提交
4432
	if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
4433 4434 4435 4436 4437 4438 4439
		if (key.objectid < ref_path->owner_objectid ||
		    (key.objectid == ref_path->owner_objectid &&
		     key.type < BTRFS_EXTENT_DATA_KEY)) {
			key.objectid = ref_path->owner_objectid;
			key.type = BTRFS_EXTENT_DATA_KEY;
			key.offset = 0;
		}
Z
Zheng Yan 已提交
4440 4441 4442 4443 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460
	}

	while (1) {
		ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
		if (ret < 0)
			goto out;

		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
next:
		if (extent_locked && ret > 0) {
			/*
			 * the file extent item was modified by someone
			 * before the extent got locked.
			 */
			unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
				      lock_end, GFP_NOFS);
			extent_locked = 0;
		}

		if (path->slots[0] >= nritems) {
4461
			if (++nr_scaned > 2)
Z
Zheng Yan 已提交
4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479
				break;

			BUG_ON(extent_locked);
			ret = btrfs_next_leaf(root, path);
			if (ret < 0)
				goto out;
			if (ret > 0)
				break;
			leaf = path->nodes[0];
			nritems = btrfs_header_nritems(leaf);
		}

		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);

		if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
			if ((key.objectid > ref_path->owner_objectid) ||
			    (key.objectid == ref_path->owner_objectid &&
			     key.type > BTRFS_EXTENT_DATA_KEY) ||
4480
			    key.offset >= search_end)
Z
Zheng Yan 已提交
4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499
				break;
		}

		if (inode && key.objectid != inode->i_ino) {
			BUG_ON(extent_locked);
			btrfs_release_path(root, path);
			mutex_unlock(&inode->i_mutex);
			iput(inode);
			inode = NULL;
			continue;
		}

		if (key.type != BTRFS_EXTENT_DATA_KEY) {
			path->slots[0]++;
			ret = 1;
			goto next;
		}
		fi = btrfs_item_ptr(leaf, path->slots[0],
				    struct btrfs_file_extent_item);
Y
Yan Zheng 已提交
4500 4501 4502
		extent_type = btrfs_file_extent_type(leaf, fi);
		if ((extent_type != BTRFS_FILE_EXTENT_REG &&
		     extent_type != BTRFS_FILE_EXTENT_PREALLOC) ||
Z
Zheng Yan 已提交
4503 4504 4505 4506 4507 4508 4509 4510 4511 4512
		    (btrfs_file_extent_disk_bytenr(leaf, fi) !=
		     extent_key->objectid)) {
			path->slots[0]++;
			ret = 1;
			goto next;
		}

		num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
		ext_offset = btrfs_file_extent_offset(leaf, fi);

4513 4514 4515 4516
		if (search_end == (u64)-1) {
			search_end = key.offset - ext_offset +
				btrfs_file_extent_ram_bytes(leaf, fi);
		}
Z
Zheng Yan 已提交
4517 4518 4519 4520 4521

		if (!extent_locked) {
			lock_start = key.offset;
			lock_end = lock_start + num_bytes - 1;
		} else {
Y
Yan Zheng 已提交
4522 4523 4524 4525 4526 4527
			if (lock_start > key.offset ||
			    lock_end + 1 < key.offset + num_bytes) {
				unlock_extent(&BTRFS_I(inode)->io_tree,
					      lock_start, lock_end, GFP_NOFS);
				extent_locked = 0;
			}
Z
Zheng Yan 已提交
4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601
		}

		if (!inode) {
			btrfs_release_path(root, path);

			inode = btrfs_iget_locked(root->fs_info->sb,
						  key.objectid, root);
			if (inode->i_state & I_NEW) {
				BTRFS_I(inode)->root = root;
				BTRFS_I(inode)->location.objectid =
					key.objectid;
				BTRFS_I(inode)->location.type =
					BTRFS_INODE_ITEM_KEY;
				BTRFS_I(inode)->location.offset = 0;
				btrfs_read_locked_inode(inode);
				unlock_new_inode(inode);
			}
			/*
			 * some code call btrfs_commit_transaction while
			 * holding the i_mutex, so we can't use mutex_lock
			 * here.
			 */
			if (is_bad_inode(inode) ||
			    !mutex_trylock(&inode->i_mutex)) {
				iput(inode);
				inode = NULL;
				key.offset = (u64)-1;
				goto skip;
			}
		}

		if (!extent_locked) {
			struct btrfs_ordered_extent *ordered;

			btrfs_release_path(root, path);

			lock_extent(&BTRFS_I(inode)->io_tree, lock_start,
				    lock_end, GFP_NOFS);
			ordered = btrfs_lookup_first_ordered_extent(inode,
								    lock_end);
			if (ordered &&
			    ordered->file_offset <= lock_end &&
			    ordered->file_offset + ordered->len > lock_start) {
				unlock_extent(&BTRFS_I(inode)->io_tree,
					      lock_start, lock_end, GFP_NOFS);
				btrfs_start_ordered_extent(inode, ordered, 1);
				btrfs_put_ordered_extent(ordered);
				key.offset += num_bytes;
				goto skip;
			}
			if (ordered)
				btrfs_put_ordered_extent(ordered);

			extent_locked = 1;
			continue;
		}

		if (nr_extents == 1) {
			/* update extent pointer in place */
			btrfs_set_file_extent_disk_bytenr(leaf, fi,
						new_extents[0].disk_bytenr);
			btrfs_set_file_extent_disk_num_bytes(leaf, fi,
						new_extents[0].disk_num_bytes);
			btrfs_mark_buffer_dirty(leaf);

			btrfs_drop_extent_cache(inode, key.offset,
						key.offset + num_bytes - 1, 0);

			ret = btrfs_inc_extent_ref(trans, root,
						new_extents[0].disk_bytenr,
						new_extents[0].disk_num_bytes,
						leaf->start,
						root->root_key.objectid,
						trans->transid,
4602
						key.objectid);
Z
Zheng Yan 已提交
4603 4604 4605 4606 4607 4608 4609 4610
			BUG_ON(ret);

			ret = btrfs_free_extent(trans, root,
						extent_key->objectid,
						extent_key->offset,
						leaf->start,
						btrfs_header_owner(leaf),
						btrfs_header_generation(leaf),
4611
						key.objectid, 0);
Z
Zheng Yan 已提交
4612 4613 4614 4615 4616
			BUG_ON(ret);

			btrfs_release_path(root, path);
			key.offset += num_bytes;
		} else {
Y
Yan Zheng 已提交
4617 4618
			BUG_ON(1);
#if 0
Z
Zheng Yan 已提交
4619 4620 4621 4622 4623 4624 4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654 4655
			u64 alloc_hint;
			u64 extent_len;
			int i;
			/*
			 * drop old extent pointer at first, then insert the
			 * new pointers one bye one
			 */
			btrfs_release_path(root, path);
			ret = btrfs_drop_extents(trans, root, inode, key.offset,
						 key.offset + num_bytes,
						 key.offset, &alloc_hint);
			BUG_ON(ret);

			for (i = 0; i < nr_extents; i++) {
				if (ext_offset >= new_extents[i].num_bytes) {
					ext_offset -= new_extents[i].num_bytes;
					continue;
				}
				extent_len = min(new_extents[i].num_bytes -
						 ext_offset, num_bytes);

				ret = btrfs_insert_empty_item(trans, root,
							      path, &key,
							      sizeof(*fi));
				BUG_ON(ret);

				leaf = path->nodes[0];
				fi = btrfs_item_ptr(leaf, path->slots[0],
						struct btrfs_file_extent_item);
				btrfs_set_file_extent_generation(leaf, fi,
							trans->transid);
				btrfs_set_file_extent_type(leaf, fi,
							BTRFS_FILE_EXTENT_REG);
				btrfs_set_file_extent_disk_bytenr(leaf, fi,
						new_extents[i].disk_bytenr);
				btrfs_set_file_extent_disk_num_bytes(leaf, fi,
						new_extents[i].disk_num_bytes);
C
Chris Mason 已提交
4656 4657 4658 4659 4660 4661 4662 4663 4664 4665
				btrfs_set_file_extent_ram_bytes(leaf, fi,
						new_extents[i].ram_bytes);

				btrfs_set_file_extent_compression(leaf, fi,
						new_extents[i].compression);
				btrfs_set_file_extent_encryption(leaf, fi,
						new_extents[i].encryption);
				btrfs_set_file_extent_other_encoding(leaf, fi,
						new_extents[i].other_encoding);

Z
Zheng Yan 已提交
4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678 4679 4680
				btrfs_set_file_extent_num_bytes(leaf, fi,
							extent_len);
				ext_offset += new_extents[i].offset;
				btrfs_set_file_extent_offset(leaf, fi,
							ext_offset);
				btrfs_mark_buffer_dirty(leaf);

				btrfs_drop_extent_cache(inode, key.offset,
						key.offset + extent_len - 1, 0);

				ret = btrfs_inc_extent_ref(trans, root,
						new_extents[i].disk_bytenr,
						new_extents[i].disk_num_bytes,
						leaf->start,
						root->root_key.objectid,
4681
						trans->transid, key.objectid);
Z
Zheng Yan 已提交
4682 4683 4684
				BUG_ON(ret);
				btrfs_release_path(root, path);

4685
				inode_add_bytes(inode, extent_len);
Z
Zheng Yan 已提交
4686 4687 4688 4689 4690 4691 4692 4693 4694

				ext_offset = 0;
				num_bytes -= extent_len;
				key.offset += extent_len;

				if (num_bytes == 0)
					break;
			}
			BUG_ON(i >= nr_extents);
Y
Yan Zheng 已提交
4695
#endif
Z
Zheng Yan 已提交
4696 4697 4698 4699 4700 4701 4702 4703 4704
		}

		if (extent_locked) {
			unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
				      lock_end, GFP_NOFS);
			extent_locked = 0;
		}
skip:
		if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS &&
4705
		    key.offset >= search_end)
Z
Zheng Yan 已提交
4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 4744 4745 4746 4747 4748 4749 4750 4751 4752 4753 4754 4755 4756 4757 4758
			break;

		cond_resched();
	}
	ret = 0;
out:
	btrfs_release_path(root, path);
	if (inode) {
		mutex_unlock(&inode->i_mutex);
		if (extent_locked) {
			unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
				      lock_end, GFP_NOFS);
		}
		iput(inode);
	}
	return ret;
}

int btrfs_reloc_tree_cache_ref(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
			       struct extent_buffer *buf, u64 orig_start)
{
	int level;
	int ret;

	BUG_ON(btrfs_header_generation(buf) != trans->transid);
	BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);

	level = btrfs_header_level(buf);
	if (level == 0) {
		struct btrfs_leaf_ref *ref;
		struct btrfs_leaf_ref *orig_ref;

		orig_ref = btrfs_lookup_leaf_ref(root, orig_start);
		if (!orig_ref)
			return -ENOENT;

		ref = btrfs_alloc_leaf_ref(root, orig_ref->nritems);
		if (!ref) {
			btrfs_free_leaf_ref(root, orig_ref);
			return -ENOMEM;
		}

		ref->nritems = orig_ref->nritems;
		memcpy(ref->extents, orig_ref->extents,
			sizeof(ref->extents[0]) * ref->nritems);

		btrfs_free_leaf_ref(root, orig_ref);

		ref->root_gen = trans->transid;
		ref->bytenr = buf->start;
		ref->owner = btrfs_header_owner(buf);
		ref->generation = btrfs_header_generation(buf);
4759

Z
Zheng Yan 已提交
4760 4761 4762 4763 4764 4765 4766
		ret = btrfs_add_leaf_ref(root, ref, 0);
		WARN_ON(ret);
		btrfs_free_leaf_ref(root, ref);
	}
	return 0;
}

C
Chris Mason 已提交
4767
static noinline int invalidate_extent_cache(struct btrfs_root *root,
Z
Zheng Yan 已提交
4768 4769 4770 4771 4772 4773 4774 4775 4776 4777 4778 4779 4780 4781 4782 4783 4784 4785 4786 4787 4788 4789 4790 4791 4792 4793 4794 4795 4796 4797 4798 4799 4800 4801 4802 4803 4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814
					struct extent_buffer *leaf,
					struct btrfs_block_group_cache *group,
					struct btrfs_root *target_root)
{
	struct btrfs_key key;
	struct inode *inode = NULL;
	struct btrfs_file_extent_item *fi;
	u64 num_bytes;
	u64 skip_objectid = 0;
	u32 nritems;
	u32 i;

	nritems = btrfs_header_nritems(leaf);
	for (i = 0; i < nritems; i++) {
		btrfs_item_key_to_cpu(leaf, &key, i);
		if (key.objectid == skip_objectid ||
		    key.type != BTRFS_EXTENT_DATA_KEY)
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
			continue;
		if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
			continue;
		if (!inode || inode->i_ino != key.objectid) {
			iput(inode);
			inode = btrfs_ilookup(target_root->fs_info->sb,
					      key.objectid, target_root, 1);
		}
		if (!inode) {
			skip_objectid = key.objectid;
			continue;
		}
		num_bytes = btrfs_file_extent_num_bytes(leaf, fi);

		lock_extent(&BTRFS_I(inode)->io_tree, key.offset,
			    key.offset + num_bytes - 1, GFP_NOFS);
		btrfs_drop_extent_cache(inode, key.offset,
					key.offset + num_bytes - 1, 1);
		unlock_extent(&BTRFS_I(inode)->io_tree, key.offset,
			      key.offset + num_bytes - 1, GFP_NOFS);
		cond_resched();
	}
	iput(inode);
	return 0;
}

C
Chris Mason 已提交
4815
static noinline int replace_extents_in_leaf(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886
					struct btrfs_root *root,
					struct extent_buffer *leaf,
					struct btrfs_block_group_cache *group,
					struct inode *reloc_inode)
{
	struct btrfs_key key;
	struct btrfs_key extent_key;
	struct btrfs_file_extent_item *fi;
	struct btrfs_leaf_ref *ref;
	struct disk_extent *new_extent;
	u64 bytenr;
	u64 num_bytes;
	u32 nritems;
	u32 i;
	int ext_index;
	int nr_extent;
	int ret;

	new_extent = kmalloc(sizeof(*new_extent), GFP_NOFS);
	BUG_ON(!new_extent);

	ref = btrfs_lookup_leaf_ref(root, leaf->start);
	BUG_ON(!ref);

	ext_index = -1;
	nritems = btrfs_header_nritems(leaf);
	for (i = 0; i < nritems; i++) {
		btrfs_item_key_to_cpu(leaf, &key, i);
		if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
			continue;
		bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
		num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
		if (bytenr == 0)
			continue;

		ext_index++;
		if (bytenr >= group->key.objectid + group->key.offset ||
		    bytenr + num_bytes <= group->key.objectid)
			continue;

		extent_key.objectid = bytenr;
		extent_key.offset = num_bytes;
		extent_key.type = BTRFS_EXTENT_ITEM_KEY;
		nr_extent = 1;
		ret = get_new_locations(reloc_inode, &extent_key,
					group->key.objectid, 1,
					&new_extent, &nr_extent);
		if (ret > 0)
			continue;
		BUG_ON(ret < 0);

		BUG_ON(ref->extents[ext_index].bytenr != bytenr);
		BUG_ON(ref->extents[ext_index].num_bytes != num_bytes);
		ref->extents[ext_index].bytenr = new_extent->disk_bytenr;
		ref->extents[ext_index].num_bytes = new_extent->disk_num_bytes;

		btrfs_set_file_extent_disk_bytenr(leaf, fi,
						new_extent->disk_bytenr);
		btrfs_set_file_extent_disk_num_bytes(leaf, fi,
						new_extent->disk_num_bytes);
		btrfs_mark_buffer_dirty(leaf);

		ret = btrfs_inc_extent_ref(trans, root,
					new_extent->disk_bytenr,
					new_extent->disk_num_bytes,
					leaf->start,
					root->root_key.objectid,
4887
					trans->transid, key.objectid);
Z
Zheng Yan 已提交
4888
		BUG_ON(ret);
4889

Z
Zheng Yan 已提交
4890 4891 4892 4893
		ret = btrfs_free_extent(trans, root,
					bytenr, num_bytes, leaf->start,
					btrfs_header_owner(leaf),
					btrfs_header_generation(leaf),
4894
					key.objectid, 0);
Z
Zheng Yan 已提交
4895 4896 4897 4898 4899 4900 4901 4902 4903
		BUG_ON(ret);
		cond_resched();
	}
	kfree(new_extent);
	BUG_ON(ext_index + 1 != ref->nritems);
	btrfs_free_leaf_ref(root, ref);
	return 0;
}

Y
Yan Zheng 已提交
4904 4905
int btrfs_free_reloc_root(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root)
Z
Zheng Yan 已提交
4906 4907
{
	struct btrfs_root *reloc_root;
Y
Yan Zheng 已提交
4908
	int ret;
Z
Zheng Yan 已提交
4909 4910 4911 4912 4913 4914

	if (root->reloc_root) {
		reloc_root = root->reloc_root;
		root->reloc_root = NULL;
		list_add(&reloc_root->dead_list,
			 &root->fs_info->dead_reloc_roots);
Y
Yan Zheng 已提交
4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927

		btrfs_set_root_bytenr(&reloc_root->root_item,
				      reloc_root->node->start);
		btrfs_set_root_level(&root->root_item,
				     btrfs_header_level(reloc_root->node));
		memset(&reloc_root->root_item.drop_progress, 0,
			sizeof(struct btrfs_disk_key));
		reloc_root->root_item.drop_level = 0;

		ret = btrfs_update_root(trans, root->fs_info->tree_root,
					&reloc_root->root_key,
					&reloc_root->root_item);
		BUG_ON(ret);
Z
Zheng Yan 已提交
4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024
	}
	return 0;
}

int btrfs_drop_dead_reloc_roots(struct btrfs_root *root)
{
	struct btrfs_trans_handle *trans;
	struct btrfs_root *reloc_root;
	struct btrfs_root *prev_root = NULL;
	struct list_head dead_roots;
	int ret;
	unsigned long nr;

	INIT_LIST_HEAD(&dead_roots);
	list_splice_init(&root->fs_info->dead_reloc_roots, &dead_roots);

	while (!list_empty(&dead_roots)) {
		reloc_root = list_entry(dead_roots.prev,
					struct btrfs_root, dead_list);
		list_del_init(&reloc_root->dead_list);

		BUG_ON(reloc_root->commit_root != NULL);
		while (1) {
			trans = btrfs_join_transaction(root, 1);
			BUG_ON(!trans);

			mutex_lock(&root->fs_info->drop_mutex);
			ret = btrfs_drop_snapshot(trans, reloc_root);
			if (ret != -EAGAIN)
				break;
			mutex_unlock(&root->fs_info->drop_mutex);

			nr = trans->blocks_used;
			ret = btrfs_end_transaction(trans, root);
			BUG_ON(ret);
			btrfs_btree_balance_dirty(root, nr);
		}

		free_extent_buffer(reloc_root->node);

		ret = btrfs_del_root(trans, root->fs_info->tree_root,
				     &reloc_root->root_key);
		BUG_ON(ret);
		mutex_unlock(&root->fs_info->drop_mutex);

		nr = trans->blocks_used;
		ret = btrfs_end_transaction(trans, root);
		BUG_ON(ret);
		btrfs_btree_balance_dirty(root, nr);

		kfree(prev_root);
		prev_root = reloc_root;
	}
	if (prev_root) {
		btrfs_remove_leaf_refs(prev_root, (u64)-1, 0);
		kfree(prev_root);
	}
	return 0;
}

int btrfs_add_dead_reloc_root(struct btrfs_root *root)
{
	list_add(&root->dead_list, &root->fs_info->dead_reloc_roots);
	return 0;
}

int btrfs_cleanup_reloc_trees(struct btrfs_root *root)
{
	struct btrfs_root *reloc_root;
	struct btrfs_trans_handle *trans;
	struct btrfs_key location;
	int found;
	int ret;

	mutex_lock(&root->fs_info->tree_reloc_mutex);
	ret = btrfs_find_dead_roots(root, BTRFS_TREE_RELOC_OBJECTID, NULL);
	BUG_ON(ret);
	found = !list_empty(&root->fs_info->dead_reloc_roots);
	mutex_unlock(&root->fs_info->tree_reloc_mutex);

	if (found) {
		trans = btrfs_start_transaction(root, 1);
		BUG_ON(!trans);
		ret = btrfs_commit_transaction(trans, root);
		BUG_ON(ret);
	}

	location.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
	location.offset = (u64)-1;
	location.type = BTRFS_ROOT_ITEM_KEY;

	reloc_root = btrfs_read_fs_root_no_name(root->fs_info, &location);
	BUG_ON(!reloc_root);
	btrfs_orphan_cleanup(reloc_root);
	return 0;
}

C
Chris Mason 已提交
5025
static noinline int init_reloc_tree(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052
				    struct btrfs_root *root)
{
	struct btrfs_root *reloc_root;
	struct extent_buffer *eb;
	struct btrfs_root_item *root_item;
	struct btrfs_key root_key;
	int ret;

	BUG_ON(!root->ref_cows);
	if (root->reloc_root)
		return 0;

	root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
	BUG_ON(!root_item);

	ret = btrfs_copy_root(trans, root, root->commit_root,
			      &eb, BTRFS_TREE_RELOC_OBJECTID);
	BUG_ON(ret);

	root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
	root_key.offset = root->root_key.objectid;
	root_key.type = BTRFS_ROOT_ITEM_KEY;

	memcpy(root_item, &root->root_item, sizeof(root_item));
	btrfs_set_root_refs(root_item, 0);
	btrfs_set_root_bytenr(root_item, eb->start);
	btrfs_set_root_level(root_item, btrfs_header_level(eb));
5053
	btrfs_set_root_generation(root_item, trans->transid);
Z
Zheng Yan 已提交
5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077

	btrfs_tree_unlock(eb);
	free_extent_buffer(eb);

	ret = btrfs_insert_root(trans, root->fs_info->tree_root,
				&root_key, root_item);
	BUG_ON(ret);
	kfree(root_item);

	reloc_root = btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
						 &root_key);
	BUG_ON(!reloc_root);
	reloc_root->last_trans = trans->transid;
	reloc_root->commit_root = NULL;
	reloc_root->ref_tree = &root->fs_info->reloc_ref_tree;

	root->reloc_root = reloc_root;
	return 0;
}

/*
 * Core function of space balance.
 *
 * The idea is using reloc trees to relocate tree blocks in reference
Y
Yan Zheng 已提交
5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090
 * counted roots. There is one reloc tree for each subvol, and all
 * reloc trees share same root key objectid. Reloc trees are snapshots
 * of the latest committed roots of subvols (root->commit_root).
 *
 * To relocate a tree block referenced by a subvol, there are two steps.
 * COW the block through subvol's reloc tree, then update block pointer
 * in the subvol to point to the new block. Since all reloc trees share
 * same root key objectid, doing special handing for tree blocks owned
 * by them is easy. Once a tree block has been COWed in one reloc tree,
 * we can use the resulting new block directly when the same block is
 * required to COW again through other reloc trees. By this way, relocated
 * tree blocks are shared between reloc trees, so they are also shared
 * between subvols.
Z
Zheng Yan 已提交
5091
 */
C
Chris Mason 已提交
5092
static noinline int relocate_one_path(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104
				      struct btrfs_root *root,
				      struct btrfs_path *path,
				      struct btrfs_key *first_key,
				      struct btrfs_ref_path *ref_path,
				      struct btrfs_block_group_cache *group,
				      struct inode *reloc_inode)
{
	struct btrfs_root *reloc_root;
	struct extent_buffer *eb = NULL;
	struct btrfs_key *keys;
	u64 *nodes;
	int level;
Y
Yan Zheng 已提交
5105
	int shared_level;
Z
Zheng Yan 已提交
5106 5107 5108 5109 5110 5111
	int lowest_level = 0;
	int ret;

	if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
		lowest_level = ref_path->owner_objectid;

Y
Yan Zheng 已提交
5112
	if (!root->ref_cows) {
Z
Zheng Yan 已提交
5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125
		path->lowest_level = lowest_level;
		ret = btrfs_search_slot(trans, root, first_key, path, 0, 1);
		BUG_ON(ret < 0);
		path->lowest_level = 0;
		btrfs_release_path(root, path);
		return 0;
	}

	mutex_lock(&root->fs_info->tree_reloc_mutex);
	ret = init_reloc_tree(trans, root);
	BUG_ON(ret);
	reloc_root = root->reloc_root;

Y
Yan Zheng 已提交
5126 5127
	shared_level = ref_path->shared_level;
	ref_path->shared_level = BTRFS_MAX_LEVEL - 1;
Z
Zheng Yan 已提交
5128

Y
Yan Zheng 已提交
5129 5130 5131 5132 5133 5134
	keys = ref_path->node_keys;
	nodes = ref_path->new_nodes;
	memset(&keys[shared_level + 1], 0,
	       sizeof(*keys) * (BTRFS_MAX_LEVEL - shared_level - 1));
	memset(&nodes[shared_level + 1], 0,
	       sizeof(*nodes) * (BTRFS_MAX_LEVEL - shared_level - 1));
Z
Zheng Yan 已提交
5135

Y
Yan Zheng 已提交
5136 5137 5138 5139 5140 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150
	if (nodes[lowest_level] == 0) {
		path->lowest_level = lowest_level;
		ret = btrfs_search_slot(trans, reloc_root, first_key, path,
					0, 1);
		BUG_ON(ret);
		for (level = lowest_level; level < BTRFS_MAX_LEVEL; level++) {
			eb = path->nodes[level];
			if (!eb || eb == reloc_root->node)
				break;
			nodes[level] = eb->start;
			if (level == 0)
				btrfs_item_key_to_cpu(eb, &keys[level], 0);
			else
				btrfs_node_key_to_cpu(eb, &keys[level], 0);
		}
Y
Yan Zheng 已提交
5151 5152
		if (nodes[0] &&
		    ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
Y
Yan Zheng 已提交
5153 5154 5155 5156 5157 5158 5159
			eb = path->nodes[0];
			ret = replace_extents_in_leaf(trans, reloc_root, eb,
						      group, reloc_inode);
			BUG_ON(ret);
		}
		btrfs_release_path(reloc_root, path);
	} else {
Z
Zheng Yan 已提交
5160
		ret = btrfs_merge_path(trans, reloc_root, keys, nodes,
Y
Yan Zheng 已提交
5161
				       lowest_level);
Z
Zheng Yan 已提交
5162 5163 5164 5165 5166 5167 5168 5169 5170 5171 5172
		BUG_ON(ret);
	}

	/*
	 * replace tree blocks in the fs tree with tree blocks in
	 * the reloc tree.
	 */
	ret = btrfs_merge_path(trans, root, keys, nodes, lowest_level);
	BUG_ON(ret < 0);

	if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
Y
Yan Zheng 已提交
5173 5174 5175 5176 5177 5178
		ret = btrfs_search_slot(trans, reloc_root, first_key, path,
					0, 0);
		BUG_ON(ret);
		extent_buffer_get(path->nodes[0]);
		eb = path->nodes[0];
		btrfs_release_path(reloc_root, path);
Z
Zheng Yan 已提交
5179 5180 5181 5182 5183
		ret = invalidate_extent_cache(reloc_root, eb, group, root);
		BUG_ON(ret);
		free_extent_buffer(eb);
	}

Y
Yan Zheng 已提交
5184
	mutex_unlock(&root->fs_info->tree_reloc_mutex);
Z
Zheng Yan 已提交
5185 5186 5187 5188
	path->lowest_level = 0;
	return 0;
}

C
Chris Mason 已提交
5189
static noinline int relocate_tree_block(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
5190 5191 5192 5193 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203
					struct btrfs_root *root,
					struct btrfs_path *path,
					struct btrfs_key *first_key,
					struct btrfs_ref_path *ref_path)
{
	int ret;

	ret = relocate_one_path(trans, root, path, first_key,
				ref_path, NULL, NULL);
	BUG_ON(ret);

	return 0;
}

C
Chris Mason 已提交
5204
static noinline int del_extent_zero(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
5205 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 5218 5219
				    struct btrfs_root *extent_root,
				    struct btrfs_path *path,
				    struct btrfs_key *extent_key)
{
	int ret;

	ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
	if (ret)
		goto out;
	ret = btrfs_del_item(trans, extent_root, path);
out:
	btrfs_release_path(extent_root, path);
	return ret;
}

C
Chris Mason 已提交
5220
static noinline struct btrfs_root *read_ref_root(struct btrfs_fs_info *fs_info,
Z
Zheng Yan 已提交
5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234
						struct btrfs_ref_path *ref_path)
{
	struct btrfs_key root_key;

	root_key.objectid = ref_path->root_objectid;
	root_key.type = BTRFS_ROOT_ITEM_KEY;
	if (is_cowonly_root(ref_path->root_objectid))
		root_key.offset = 0;
	else
		root_key.offset = (u64)-1;

	return btrfs_read_fs_root_no_name(fs_info, &root_key);
}

C
Chris Mason 已提交
5235
static noinline int relocate_one_extent(struct btrfs_root *extent_root,
Z
Zheng Yan 已提交
5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262
					struct btrfs_path *path,
					struct btrfs_key *extent_key,
					struct btrfs_block_group_cache *group,
					struct inode *reloc_inode, int pass)
{
	struct btrfs_trans_handle *trans;
	struct btrfs_root *found_root;
	struct btrfs_ref_path *ref_path = NULL;
	struct disk_extent *new_extents = NULL;
	int nr_extents = 0;
	int loops;
	int ret;
	int level;
	struct btrfs_key first_key;
	u64 prev_block = 0;


	trans = btrfs_start_transaction(extent_root, 1);
	BUG_ON(!trans);

	if (extent_key->objectid == 0) {
		ret = del_extent_zero(trans, extent_root, path, extent_key);
		goto out;
	}

	ref_path = kmalloc(sizeof(*ref_path), GFP_NOFS);
	if (!ref_path) {
C
Chris Mason 已提交
5263 5264
		ret = -ENOMEM;
		goto out;
Z
Zheng Yan 已提交
5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307 5308 5309 5310 5311 5312 5313 5314 5315 5316 5317 5318 5319 5320 5321 5322 5323 5324 5325 5326 5327 5328 5329 5330
	}

	for (loops = 0; ; loops++) {
		if (loops == 0) {
			ret = btrfs_first_ref_path(trans, extent_root, ref_path,
						   extent_key->objectid);
		} else {
			ret = btrfs_next_ref_path(trans, extent_root, ref_path);
		}
		if (ret < 0)
			goto out;
		if (ret > 0)
			break;

		if (ref_path->root_objectid == BTRFS_TREE_LOG_OBJECTID ||
		    ref_path->root_objectid == BTRFS_TREE_RELOC_OBJECTID)
			continue;

		found_root = read_ref_root(extent_root->fs_info, ref_path);
		BUG_ON(!found_root);
		/*
		 * for reference counted tree, only process reference paths
		 * rooted at the latest committed root.
		 */
		if (found_root->ref_cows &&
		    ref_path->root_generation != found_root->root_key.offset)
			continue;

		if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
			if (pass == 0) {
				/*
				 * copy data extents to new locations
				 */
				u64 group_start = group->key.objectid;
				ret = relocate_data_extent(reloc_inode,
							   extent_key,
							   group_start);
				if (ret < 0)
					goto out;
				break;
			}
			level = 0;
		} else {
			level = ref_path->owner_objectid;
		}

		if (prev_block != ref_path->nodes[level]) {
			struct extent_buffer *eb;
			u64 block_start = ref_path->nodes[level];
			u64 block_size = btrfs_level_size(found_root, level);

			eb = read_tree_block(found_root, block_start,
					     block_size, 0);
			btrfs_tree_lock(eb);
			BUG_ON(level != btrfs_header_level(eb));

			if (level == 0)
				btrfs_item_key_to_cpu(eb, &first_key, 0);
			else
				btrfs_node_key_to_cpu(eb, &first_key, 0);

			btrfs_tree_unlock(eb);
			free_extent_buffer(eb);
			prev_block = block_start;
		}

5331
		mutex_lock(&extent_root->fs_info->trans_mutex);
Y
Yan Zheng 已提交
5332
		btrfs_record_root_in_trans(found_root);
5333
		mutex_unlock(&extent_root->fs_info->trans_mutex);
Y
Yan Zheng 已提交
5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 5346
		if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
			/*
			 * try to update data extent references while
			 * keeping metadata shared between snapshots.
			 */
			if (pass == 1) {
				ret = relocate_one_path(trans, found_root,
						path, &first_key, ref_path,
						group, reloc_inode);
				if (ret < 0)
					goto out;
				continue;
			}
Z
Zheng Yan 已提交
5347 5348 5349 5350 5351 5352
			/*
			 * use fallback method to process the remaining
			 * references.
			 */
			if (!new_extents) {
				u64 group_start = group->key.objectid;
Y
Yan Zheng 已提交
5353 5354 5355
				new_extents = kmalloc(sizeof(*new_extents),
						      GFP_NOFS);
				nr_extents = 1;
Z
Zheng Yan 已提交
5356 5357
				ret = get_new_locations(reloc_inode,
							extent_key,
Y
Yan Zheng 已提交
5358
							group_start, 1,
Z
Zheng Yan 已提交
5359 5360
							&new_extents,
							&nr_extents);
Y
Yan Zheng 已提交
5361
				if (ret)
Z
Zheng Yan 已提交
5362 5363 5364 5365 5366 5367
					goto out;
			}
			ret = replace_one_extent(trans, found_root,
						path, extent_key,
						&first_key, ref_path,
						new_extents, nr_extents);
Y
Yan Zheng 已提交
5368
		} else {
Z
Zheng Yan 已提交
5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382
			ret = relocate_tree_block(trans, found_root, path,
						  &first_key, ref_path);
		}
		if (ret < 0)
			goto out;
	}
	ret = 0;
out:
	btrfs_end_transaction(trans, extent_root);
	kfree(new_extents);
	kfree(ref_path);
	return ret;
}

5383 5384 5385 5386 5387 5388
static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
{
	u64 num_devices;
	u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
		BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;

Y
Yan Zheng 已提交
5389
	num_devices = root->fs_info->fs_devices->rw_devices;
5390 5391 5392 5393 5394 5395 5396 5397 5398 5399 5400 5401 5402 5403 5404 5405 5406 5407 5408 5409 5410 5411 5412 5413 5414 5415 5416 5417 5418 5419 5420
	if (num_devices == 1) {
		stripped |= BTRFS_BLOCK_GROUP_DUP;
		stripped = flags & ~stripped;

		/* turn raid0 into single device chunks */
		if (flags & BTRFS_BLOCK_GROUP_RAID0)
			return stripped;

		/* turn mirroring into duplication */
		if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
			     BTRFS_BLOCK_GROUP_RAID10))
			return stripped | BTRFS_BLOCK_GROUP_DUP;
		return flags;
	} else {
		/* they already had raid on here, just return */
		if (flags & stripped)
			return flags;

		stripped |= BTRFS_BLOCK_GROUP_DUP;
		stripped = flags & ~stripped;

		/* switch duplicated blocks with raid1 */
		if (flags & BTRFS_BLOCK_GROUP_DUP)
			return stripped | BTRFS_BLOCK_GROUP_RAID1;

		/* turn single device chunks into raid0 */
		return stripped | BTRFS_BLOCK_GROUP_RAID0;
	}
	return flags;
}

5421
static int __alloc_chunk_for_shrink(struct btrfs_root *root,
C
Chris Mason 已提交
5422 5423 5424 5425 5426 5427 5428
		     struct btrfs_block_group_cache *shrink_block_group,
		     int force)
{
	struct btrfs_trans_handle *trans;
	u64 new_alloc_flags;
	u64 calc;

5429
	spin_lock(&shrink_block_group->lock);
C
Chris Mason 已提交
5430
	if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
5431 5432
		spin_unlock(&shrink_block_group->lock);

C
Chris Mason 已提交
5433
		trans = btrfs_start_transaction(root, 1);
5434
		spin_lock(&shrink_block_group->lock);
5435

C
Chris Mason 已提交
5436 5437 5438 5439 5440 5441 5442 5443
		new_alloc_flags = update_block_group_flags(root,
						   shrink_block_group->flags);
		if (new_alloc_flags != shrink_block_group->flags) {
			calc =
			     btrfs_block_group_used(&shrink_block_group->item);
		} else {
			calc = shrink_block_group->key.offset;
		}
5444 5445
		spin_unlock(&shrink_block_group->lock);

C
Chris Mason 已提交
5446 5447
		do_chunk_alloc(trans, root->fs_info->extent_root,
			       calc + 2 * 1024 * 1024, new_alloc_flags, force);
5448

C
Chris Mason 已提交
5449
		btrfs_end_transaction(trans, root);
5450 5451
	} else
		spin_unlock(&shrink_block_group->lock);
C
Chris Mason 已提交
5452 5453 5454
	return 0;
}

Z
Zheng Yan 已提交
5455 5456 5457 5458 5459 5460 5461 5462 5463 5464 5465 5466 5467
static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
				 struct btrfs_root *root,
				 u64 objectid, u64 size)
{
	struct btrfs_path *path;
	struct btrfs_inode_item *item;
	struct extent_buffer *leaf;
	int ret;

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

5468
	path->leave_spinning = 1;
Z
Zheng Yan 已提交
5469 5470 5471 5472 5473 5474 5475 5476 5477 5478
	ret = btrfs_insert_empty_inode(trans, root, path, objectid);
	if (ret)
		goto out;

	leaf = path->nodes[0];
	item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
	memset_extent_buffer(leaf, 0, (unsigned long)item, sizeof(*item));
	btrfs_set_inode_generation(leaf, item, 1);
	btrfs_set_inode_size(leaf, item, size);
	btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
5479
	btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NOCOMPRESS);
Z
Zheng Yan 已提交
5480 5481 5482 5483 5484 5485 5486
	btrfs_mark_buffer_dirty(leaf);
	btrfs_release_path(root, path);
out:
	btrfs_free_path(path);
	return ret;
}

C
Chris Mason 已提交
5487
static noinline struct inode *create_reloc_inode(struct btrfs_fs_info *fs_info,
Z
Zheng Yan 已提交
5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498 5499 5500 5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514
					struct btrfs_block_group_cache *group)
{
	struct inode *inode = NULL;
	struct btrfs_trans_handle *trans;
	struct btrfs_root *root;
	struct btrfs_key root_key;
	u64 objectid = BTRFS_FIRST_FREE_OBJECTID;
	int err = 0;

	root_key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
	root_key.type = BTRFS_ROOT_ITEM_KEY;
	root_key.offset = (u64)-1;
	root = btrfs_read_fs_root_no_name(fs_info, &root_key);
	if (IS_ERR(root))
		return ERR_CAST(root);

	trans = btrfs_start_transaction(root, 1);
	BUG_ON(!trans);

	err = btrfs_find_free_objectid(trans, root, objectid, &objectid);
	if (err)
		goto out;

	err = __insert_orphan_inode(trans, root, objectid, group->key.offset);
	BUG_ON(err);

	err = btrfs_insert_file_extent(trans, root, objectid, 0, 0, 0,
C
Chris Mason 已提交
5515 5516
				       group->key.offset, 0, group->key.offset,
				       0, 0, 0);
Z
Zheng Yan 已提交
5517 5518 5519 5520 5521 5522 5523 5524 5525 5526 5527 5528 5529 5530
	BUG_ON(err);

	inode = btrfs_iget_locked(root->fs_info->sb, objectid, root);
	if (inode->i_state & I_NEW) {
		BTRFS_I(inode)->root = root;
		BTRFS_I(inode)->location.objectid = objectid;
		BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
		BTRFS_I(inode)->location.offset = 0;
		btrfs_read_locked_inode(inode);
		unlock_new_inode(inode);
		BUG_ON(is_bad_inode(inode));
	} else {
		BUG_ON(1);
	}
5531
	BTRFS_I(inode)->index_cnt = group->key.objectid;
Z
Zheng Yan 已提交
5532 5533 5534 5535 5536 5537 5538 5539 5540 5541 5542 5543

	err = btrfs_orphan_add(trans, inode);
out:
	btrfs_end_transaction(trans, root);
	if (err) {
		if (inode)
			iput(inode);
		inode = ERR_PTR(err);
	}
	return inode;
}

5544 5545 5546 5547 5548 5549 5550 5551 5552 5553 5554 5555 5556 5557 5558 5559 5560 5561
int btrfs_reloc_clone_csums(struct inode *inode, u64 file_pos, u64 len)
{

	struct btrfs_ordered_sum *sums;
	struct btrfs_sector_sum *sector_sum;
	struct btrfs_ordered_extent *ordered;
	struct btrfs_root *root = BTRFS_I(inode)->root;
	struct list_head list;
	size_t offset;
	int ret;
	u64 disk_bytenr;

	INIT_LIST_HEAD(&list);

	ordered = btrfs_lookup_ordered_extent(inode, file_pos);
	BUG_ON(ordered->file_offset != file_pos || ordered->len != len);

	disk_bytenr = file_pos + BTRFS_I(inode)->index_cnt;
Y
Yan Zheng 已提交
5562
	ret = btrfs_lookup_csums_range(root->fs_info->csum_root, disk_bytenr,
5563 5564 5565 5566 5567 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584
				       disk_bytenr + len - 1, &list);

	while (!list_empty(&list)) {
		sums = list_entry(list.next, struct btrfs_ordered_sum, list);
		list_del_init(&sums->list);

		sector_sum = sums->sums;
		sums->bytenr = ordered->start;

		offset = 0;
		while (offset < sums->len) {
			sector_sum->bytenr += ordered->start - disk_bytenr;
			sector_sum++;
			offset += root->sectorsize;
		}

		btrfs_add_ordered_sum(inode, ordered, sums);
	}
	btrfs_put_ordered_extent(ordered);
	return 0;
}

Z
Zheng Yan 已提交
5585
int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start)
5586 5587 5588
{
	struct btrfs_trans_handle *trans;
	struct btrfs_path *path;
Z
Zheng Yan 已提交
5589 5590 5591 5592 5593
	struct btrfs_fs_info *info = root->fs_info;
	struct extent_buffer *leaf;
	struct inode *reloc_inode;
	struct btrfs_block_group_cache *block_group;
	struct btrfs_key key;
Y
Yan Zheng 已提交
5594
	u64 skipped;
5595 5596 5597 5598
	u64 cur_byte;
	u64 total_found;
	u32 nritems;
	int ret;
5599
	int progress;
Z
Zheng Yan 已提交
5600
	int pass = 0;
5601

Z
Zheng Yan 已提交
5602 5603 5604 5605
	root = root->fs_info->extent_root;

	block_group = btrfs_lookup_block_group(info, group_start);
	BUG_ON(!block_group);
5606

C
Chris Mason 已提交
5607
	printk(KERN_INFO "btrfs relocating block group %llu flags %llu\n",
Z
Zheng Yan 已提交
5608 5609
	       (unsigned long long)block_group->key.objectid,
	       (unsigned long long)block_group->flags);
5610

5611
	path = btrfs_alloc_path();
Z
Zheng Yan 已提交
5612
	BUG_ON(!path);
5613

Z
Zheng Yan 已提交
5614 5615
	reloc_inode = create_reloc_inode(info, block_group);
	BUG_ON(IS_ERR(reloc_inode));
5616

Z
Zheng Yan 已提交
5617
	__alloc_chunk_for_shrink(root, block_group, 1);
Y
Yan Zheng 已提交
5618
	set_block_group_readonly(block_group);
5619

Z
Zheng Yan 已提交
5620 5621 5622
	btrfs_start_delalloc_inodes(info->tree_root);
	btrfs_wait_ordered_extents(info->tree_root, 0);
again:
Y
Yan Zheng 已提交
5623
	skipped = 0;
5624
	total_found = 0;
5625
	progress = 0;
Z
Zheng Yan 已提交
5626
	key.objectid = block_group->key.objectid;
5627 5628
	key.offset = 0;
	key.type = 0;
5629
	cur_byte = key.objectid;
5630

Z
Zheng Yan 已提交
5631 5632
	trans = btrfs_start_transaction(info->tree_root, 1);
	btrfs_commit_transaction(trans, info->tree_root);
5633

Z
Zheng Yan 已提交
5634 5635 5636 5637
	mutex_lock(&root->fs_info->cleaner_mutex);
	btrfs_clean_old_snapshots(info->tree_root);
	btrfs_remove_leaf_refs(info->tree_root, (u64)-1, 1);
	mutex_unlock(&root->fs_info->cleaner_mutex);
5638

5639 5640 5641
	trans = btrfs_start_transaction(info->tree_root, 1);
	btrfs_commit_transaction(trans, info->tree_root);

C
Chris Mason 已提交
5642
	while (1) {
5643 5644 5645
		ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
		if (ret < 0)
			goto out;
5646
next:
5647
		leaf = path->nodes[0];
5648 5649 5650 5651 5652 5653 5654 5655
		nritems = btrfs_header_nritems(leaf);
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(root, path);
			if (ret < 0)
				goto out;
			if (ret == 1) {
				ret = 0;
				break;
5656
			}
5657 5658
			leaf = path->nodes[0];
			nritems = btrfs_header_nritems(leaf);
5659
		}
5660

Z
Zheng Yan 已提交
5661
		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5662

Z
Zheng Yan 已提交
5663 5664
		if (key.objectid >= block_group->key.objectid +
		    block_group->key.offset)
5665 5666
			break;

5667 5668
		if (progress && need_resched()) {
			btrfs_release_path(root, path);
Z
Zheng Yan 已提交
5669
			cond_resched();
5670
			progress = 0;
Z
Zheng Yan 已提交
5671
			continue;
5672 5673 5674
		}
		progress = 1;

Z
Zheng Yan 已提交
5675 5676
		if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY ||
		    key.objectid + key.offset <= cur_byte) {
5677 5678 5679
			path->slots[0]++;
			goto next;
		}
5680

5681
		total_found++;
Z
Zheng Yan 已提交
5682
		cur_byte = key.objectid + key.offset;
5683 5684
		btrfs_release_path(root, path);

Z
Zheng Yan 已提交
5685 5686 5687 5688
		__alloc_chunk_for_shrink(root, block_group, 0);
		ret = relocate_one_extent(root, path, &key, block_group,
					  reloc_inode, pass);
		BUG_ON(ret < 0);
Y
Yan Zheng 已提交
5689 5690
		if (ret > 0)
			skipped++;
5691

Z
Zheng Yan 已提交
5692 5693 5694
		key.objectid = cur_byte;
		key.type = 0;
		key.offset = 0;
5695 5696
	}

Z
Zheng Yan 已提交
5697
	btrfs_release_path(root, path);
5698

Z
Zheng Yan 已提交
5699 5700 5701
	if (pass == 0) {
		btrfs_wait_ordered_range(reloc_inode, 0, (u64)-1);
		invalidate_mapping_pages(reloc_inode->i_mapping, 0, -1);
5702
	}
5703

Z
Zheng Yan 已提交
5704
	if (total_found > 0) {
C
Chris Mason 已提交
5705
		printk(KERN_INFO "btrfs found %llu extents in pass %d\n",
Z
Zheng Yan 已提交
5706 5707
		       (unsigned long long)total_found, pass);
		pass++;
Y
Yan Zheng 已提交
5708 5709 5710 5711 5712
		if (total_found == skipped && pass > 2) {
			iput(reloc_inode);
			reloc_inode = create_reloc_inode(info, block_group);
			pass = 0;
		}
Z
Zheng Yan 已提交
5713
		goto again;
J
Josef Bacik 已提交
5714
	}
C
Chris Mason 已提交
5715

Z
Zheng Yan 已提交
5716 5717 5718 5719 5720 5721
	/* delete reloc_inode */
	iput(reloc_inode);

	/* unpin extents in this range */
	trans = btrfs_start_transaction(info->tree_root, 1);
	btrfs_commit_transaction(trans, info->tree_root);
C
Chris Mason 已提交
5722

Z
Zheng Yan 已提交
5723 5724 5725 5726 5727
	spin_lock(&block_group->lock);
	WARN_ON(block_group->pinned > 0);
	WARN_ON(block_group->reserved > 0);
	WARN_ON(btrfs_block_group_used(&block_group->item) > 0);
	spin_unlock(&block_group->lock);
5728
	put_block_group(block_group);
Z
Zheng Yan 已提交
5729
	ret = 0;
5730
out:
Z
Zheng Yan 已提交
5731
	btrfs_free_path(path);
5732 5733 5734
	return ret;
}

5735 5736
static int find_first_block_group(struct btrfs_root *root,
		struct btrfs_path *path, struct btrfs_key *key)
5737
{
5738
	int ret = 0;
5739 5740 5741
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
	int slot;
5742

5743 5744
	ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
	if (ret < 0)
5745 5746
		goto out;

C
Chris Mason 已提交
5747
	while (1) {
5748
		slot = path->slots[0];
5749
		leaf = path->nodes[0];
5750 5751 5752 5753 5754
		if (slot >= btrfs_header_nritems(leaf)) {
			ret = btrfs_next_leaf(root, path);
			if (ret == 0)
				continue;
			if (ret < 0)
5755
				goto out;
5756
			break;
5757
		}
5758
		btrfs_item_key_to_cpu(leaf, &found_key, slot);
5759

5760
		if (found_key.objectid >= key->objectid &&
5761 5762 5763 5764
		    found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
			ret = 0;
			goto out;
		}
5765
		path->slots[0]++;
5766
	}
5767
	ret = -ENOENT;
5768
out:
5769
	return ret;
5770 5771
}

Z
Zheng Yan 已提交
5772 5773 5774
int btrfs_free_block_groups(struct btrfs_fs_info *info)
{
	struct btrfs_block_group_cache *block_group;
5775
	struct btrfs_space_info *space_info;
Z
Zheng Yan 已提交
5776 5777 5778 5779 5780 5781 5782 5783
	struct rb_node *n;

	spin_lock(&info->block_group_cache_lock);
	while ((n = rb_last(&info->block_group_cache_tree)) != NULL) {
		block_group = rb_entry(n, struct btrfs_block_group_cache,
				       cache_node);
		rb_erase(&block_group->cache_node,
			 &info->block_group_cache_tree);
Y
Yan Zheng 已提交
5784 5785 5786
		spin_unlock(&info->block_group_cache_lock);

		btrfs_remove_free_space_cache(block_group);
5787
		down_write(&block_group->space_info->groups_sem);
Z
Zheng Yan 已提交
5788
		list_del(&block_group->list);
5789
		up_write(&block_group->space_info->groups_sem);
5790 5791

		WARN_ON(atomic_read(&block_group->count) != 1);
Z
Zheng Yan 已提交
5792
		kfree(block_group);
Y
Yan Zheng 已提交
5793 5794

		spin_lock(&info->block_group_cache_lock);
Z
Zheng Yan 已提交
5795 5796
	}
	spin_unlock(&info->block_group_cache_lock);
5797 5798 5799 5800 5801 5802 5803 5804 5805 5806 5807 5808 5809 5810 5811 5812 5813

	/* now that all the block groups are freed, go through and
	 * free all the space_info structs.  This is only called during
	 * the final stages of unmount, and so we know nobody is
	 * using them.  We call synchronize_rcu() once before we start,
	 * just to be on the safe side.
	 */
	synchronize_rcu();

	while(!list_empty(&info->space_info)) {
		space_info = list_entry(info->space_info.next,
					struct btrfs_space_info,
					list);

		list_del(&space_info->list);
		kfree(space_info);
	}
Z
Zheng Yan 已提交
5814 5815 5816
	return 0;
}

C
Chris Mason 已提交
5817 5818 5819 5820 5821
int btrfs_read_block_groups(struct btrfs_root *root)
{
	struct btrfs_path *path;
	int ret;
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
5822
	struct btrfs_fs_info *info = root->fs_info;
5823
	struct btrfs_space_info *space_info;
C
Chris Mason 已提交
5824 5825
	struct btrfs_key key;
	struct btrfs_key found_key;
5826
	struct extent_buffer *leaf;
5827

C
Chris Mason 已提交
5828
	root = info->extent_root;
C
Chris Mason 已提交
5829
	key.objectid = 0;
5830
	key.offset = 0;
C
Chris Mason 已提交
5831 5832 5833 5834 5835
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

C
Chris Mason 已提交
5836
	while (1) {
5837 5838 5839 5840
		ret = find_first_block_group(root, path, &key);
		if (ret > 0) {
			ret = 0;
			goto error;
C
Chris Mason 已提交
5841
		}
5842 5843 5844
		if (ret != 0)
			goto error;

5845 5846
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5847
		cache = kzalloc(sizeof(*cache), GFP_NOFS);
C
Chris Mason 已提交
5848
		if (!cache) {
5849
			ret = -ENOMEM;
C
Chris Mason 已提交
5850 5851
			break;
		}
C
Chris Mason 已提交
5852

5853
		atomic_set(&cache->count, 1);
5854
		spin_lock_init(&cache->lock);
5855
		mutex_init(&cache->alloc_mutex);
5856
		mutex_init(&cache->cache_mutex);
J
Josef Bacik 已提交
5857
		INIT_LIST_HEAD(&cache->list);
5858 5859 5860
		read_extent_buffer(leaf, &cache->item,
				   btrfs_item_ptr_offset(leaf, path->slots[0]),
				   sizeof(cache->item));
C
Chris Mason 已提交
5861
		memcpy(&cache->key, &found_key, sizeof(found_key));
5862

C
Chris Mason 已提交
5863 5864
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
5865
		cache->flags = btrfs_block_group_flags(&cache->item);
5866

5867 5868 5869 5870 5871
		ret = update_space_info(info, cache->flags, found_key.offset,
					btrfs_block_group_used(&cache->item),
					&space_info);
		BUG_ON(ret);
		cache->space_info = space_info;
5872 5873 5874
		down_write(&space_info->groups_sem);
		list_add_tail(&cache->list, &space_info->block_groups);
		up_write(&space_info->groups_sem);
J
Josef Bacik 已提交
5875 5876 5877

		ret = btrfs_add_block_group_cache(root->fs_info, cache);
		BUG_ON(ret);
5878 5879

		set_avail_alloc_bits(root->fs_info, cache->flags);
Y
Yan Zheng 已提交
5880 5881
		if (btrfs_chunk_readonly(root, cache->key.objectid))
			set_block_group_readonly(cache);
C
Chris Mason 已提交
5882
	}
5883 5884
	ret = 0;
error:
C
Chris Mason 已提交
5885
	btrfs_free_path(path);
5886
	return ret;
C
Chris Mason 已提交
5887
}
5888 5889 5890

int btrfs_make_block_group(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root, u64 bytes_used,
5891
			   u64 type, u64 chunk_objectid, u64 chunk_offset,
5892 5893 5894 5895 5896 5897 5898 5899
			   u64 size)
{
	int ret;
	struct btrfs_root *extent_root;
	struct btrfs_block_group_cache *cache;

	extent_root = root->fs_info->extent_root;

5900
	root->fs_info->last_trans_log_full_commit = trans->transid;
5901

5902
	cache = kzalloc(sizeof(*cache), GFP_NOFS);
J
Josef Bacik 已提交
5903 5904 5905
	if (!cache)
		return -ENOMEM;

5906
	cache->key.objectid = chunk_offset;
5907
	cache->key.offset = size;
5908 5909
	cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
	atomic_set(&cache->count, 1);
5910
	spin_lock_init(&cache->lock);
5911
	mutex_init(&cache->alloc_mutex);
5912
	mutex_init(&cache->cache_mutex);
J
Josef Bacik 已提交
5913
	INIT_LIST_HEAD(&cache->list);
C
Chris Mason 已提交
5914

5915 5916 5917 5918 5919 5920 5921 5922
	btrfs_set_block_group_used(&cache->item, bytes_used);
	btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
	cache->flags = type;
	btrfs_set_block_group_flags(&cache->item, type);

	ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
				&cache->space_info);
	BUG_ON(ret);
5923 5924 5925
	down_write(&cache->space_info->groups_sem);
	list_add_tail(&cache->list, &cache->space_info->block_groups);
	up_write(&cache->space_info->groups_sem);
5926

J
Josef Bacik 已提交
5927 5928
	ret = btrfs_add_block_group_cache(root->fs_info, cache);
	BUG_ON(ret);
5929

5930 5931 5932 5933
	ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
				sizeof(cache->item));
	BUG_ON(ret);

C
Chris Mason 已提交
5934
	set_avail_alloc_bits(extent_root->fs_info, type);
5935

5936 5937
	return 0;
}
Z
Zheng Yan 已提交
5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950

int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
			     struct btrfs_root *root, u64 group_start)
{
	struct btrfs_path *path;
	struct btrfs_block_group_cache *block_group;
	struct btrfs_key key;
	int ret;

	root = root->fs_info->extent_root;

	block_group = btrfs_lookup_block_group(root->fs_info, group_start);
	BUG_ON(!block_group);
Y
Yan Zheng 已提交
5951
	BUG_ON(!block_group->ro);
Z
Zheng Yan 已提交
5952 5953 5954 5955 5956 5957

	memcpy(&key, &block_group->key, sizeof(key));

	path = btrfs_alloc_path();
	BUG_ON(!path);

5958
	spin_lock(&root->fs_info->block_group_cache_lock);
Z
Zheng Yan 已提交
5959 5960
	rb_erase(&block_group->cache_node,
		 &root->fs_info->block_group_cache_tree);
5961 5962
	spin_unlock(&root->fs_info->block_group_cache_lock);
	btrfs_remove_free_space_cache(block_group);
5963
	down_write(&block_group->space_info->groups_sem);
Z
Zheng Yan 已提交
5964
	list_del(&block_group->list);
5965
	up_write(&block_group->space_info->groups_sem);
Z
Zheng Yan 已提交
5966

Y
Yan Zheng 已提交
5967 5968 5969 5970
	spin_lock(&block_group->space_info->lock);
	block_group->space_info->total_bytes -= block_group->key.offset;
	block_group->space_info->bytes_readonly -= block_group->key.offset;
	spin_unlock(&block_group->space_info->lock);
Y
Yan Zheng 已提交
5971
	block_group->space_info->full = 0;
Y
Yan Zheng 已提交
5972

5973 5974
	put_block_group(block_group);
	put_block_group(block_group);
Z
Zheng Yan 已提交
5975 5976 5977 5978 5979 5980 5981 5982 5983 5984 5985 5986

	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
	if (ret > 0)
		ret = -EIO;
	if (ret < 0)
		goto out;

	ret = btrfs_del_item(trans, root, path);
out:
	btrfs_free_path(path);
	return ret;
}