extent-tree.c 135.2 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 "hash.h"
23
#include "crc32c.h"
24 25 26
#include "ctree.h"
#include "disk-io.h"
#include "print-tree.h"
27
#include "transaction.h"
28
#include "volumes.h"
29
#include "locking.h"
Y
Yan Zheng 已提交
30
#include "ref-cache.h"
31

Z
Zheng Yan 已提交
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
#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;
};

47 48
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root);
C
Chris Mason 已提交
49 50
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root);
51 52 53 54
static struct btrfs_block_group_cache *
__btrfs_find_block_group(struct btrfs_root *root,
			 struct btrfs_block_group_cache *hint,
			 u64 search_start, int data, int owner);
55

56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
void maybe_lock_mutex(struct btrfs_root *root)
{
	if (root != root->fs_info->extent_root &&
	    root != root->fs_info->chunk_root &&
	    root != root->fs_info->dev_root) {
		mutex_lock(&root->fs_info->alloc_mutex);
	}
}

void maybe_unlock_mutex(struct btrfs_root *root)
{
	if (root != root->fs_info->extent_root &&
	    root != root->fs_info->chunk_root &&
	    root != root->fs_info->dev_root) {
		mutex_unlock(&root->fs_info->alloc_mutex);
	}
}
73

J
Josef Bacik 已提交
74 75 76 77 78 79 80 81 82 83 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 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
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
 */
int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
				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;
		}
	}
	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;

	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;
			ret = btrfs_add_free_space(block_group, start, size);
			BUG_ON(ret);
			start = extent_end + 1;
		} else {
			break;
		}
	}

	if (start < end) {
		size = end - start;
		ret = btrfs_add_free_space(block_group, start, size);
		BUG_ON(ret);
	}

	return 0;
}

195 196 197 198
static int cache_block_group(struct btrfs_root *root,
			     struct btrfs_block_group_cache *block_group)
{
	struct btrfs_path *path;
199
	int ret = 0;
200
	struct btrfs_key key;
201
	struct extent_buffer *leaf;
202 203
	int slot;
	u64 last = 0;
204
	u64 first_free;
205 206
	int found = 0;

207 208 209
	if (!block_group)
		return 0;

210 211 212 213
	root = root->fs_info->extent_root;

	if (block_group->cached)
		return 0;
214

215 216 217
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
218

219
	path->reada = 2;
220 221 222 223 224 225
	/*
	 * 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;
J
Josef Bacik 已提交
226 227
	first_free = max_t(u64, block_group->key.objectid,
			   BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
228 229 230 231 232
	key.objectid = block_group->key.objectid;
	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)
233
		goto err;
234
	ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
235
	if (ret < 0)
236
		goto err;
237 238 239 240 241 242
	if (ret == 0) {
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
		if (key.objectid + key.offset > first_free)
			first_free = key.objectid + key.offset;
	}
243
	while(1) {
244
		leaf = path->nodes[0];
245
		slot = path->slots[0];
246
		if (slot >= btrfs_header_nritems(leaf)) {
247
			ret = btrfs_next_leaf(root, path);
248 249
			if (ret < 0)
				goto err;
J
Josef Bacik 已提交
250
			if (ret == 0)
251
				continue;
J
Josef Bacik 已提交
252
			else
253 254
				break;
		}
255
		btrfs_item_key_to_cpu(leaf, &key, slot);
J
Josef Bacik 已提交
256
		if (key.objectid < block_group->key.objectid)
257
			goto next;
J
Josef Bacik 已提交
258

259
		if (key.objectid >= block_group->key.objectid +
J
Josef Bacik 已提交
260
		    block_group->key.offset)
261
			break;
262

263 264
		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
			if (!found) {
265
				last = first_free;
266 267
				found = 1;
			}
J
Josef Bacik 已提交
268 269 270 271

			add_new_free_space(block_group, root->fs_info, last,
					   key.objectid);

272
			last = key.objectid + key.offset;
273
		}
274
next:
275 276 277
		path->slots[0]++;
	}

278 279
	if (!found)
		last = first_free;
J
Josef Bacik 已提交
280 281 282 283 284

	add_new_free_space(block_group, root->fs_info, last,
			   block_group->key.objectid +
			   block_group->key.offset);

285
	block_group->cached = 1;
286
	ret = 0;
287
err:
288
	btrfs_free_path(path);
289
	return ret;
290 291
}

J
Josef Bacik 已提交
292 293 294
/*
 * return the block group that starts at or after bytenr
 */
C
Chris Mason 已提交
295 296 297 298
struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
						       btrfs_fs_info *info,
							 u64 bytenr)
{
J
Josef Bacik 已提交
299
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
300

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

J
Josef Bacik 已提交
303
	return cache;
C
Chris Mason 已提交
304 305
}

J
Josef Bacik 已提交
306 307 308
/*
 * return the block group that contains teh given bytenr
 */
309 310
struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
							 btrfs_fs_info *info,
311
							 u64 bytenr)
C
Chris Mason 已提交
312
{
J
Josef Bacik 已提交
313
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
314

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

J
Josef Bacik 已提交
317
	return cache;
C
Chris Mason 已提交
318
}
319

J
Josef Bacik 已提交
320 321 322
static int noinline find_free_space(struct btrfs_root *root,
				    struct btrfs_block_group_cache **cache_ret,
				    u64 *start_ret, u64 num, int data)
323 324 325
{
	int ret;
	struct btrfs_block_group_cache *cache = *cache_ret;
J
Josef Bacik 已提交
326
	struct btrfs_free_space *info = NULL;
327
	u64 last;
328
	u64 search_start = *start_ret;
329

330
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
C
Chris Mason 已提交
331 332 333
	if (!cache)
		goto out;

J
Josef Bacik 已提交
334 335
	last = max(search_start, cache->key.objectid);

336
again:
337
	ret = cache_block_group(root, cache);
J
Josef Bacik 已提交
338
	if (ret)
339
		goto out;
340

J
Josef Bacik 已提交
341
	if (cache->ro || !block_group_bits(cache, data))
342
		goto new_group;
343

J
Josef Bacik 已提交
344 345 346
	info = btrfs_find_free_space(cache, last, num);
	if (info) {
		*start_ret = info->offset;
347
		return 0;
348
	}
349 350

new_group:
351
	last = cache->key.objectid + cache->key.offset;
J
Josef Bacik 已提交
352

C
Chris Mason 已提交
353
	cache = btrfs_lookup_first_block_group(root->fs_info, last);
354
	if (!cache)
355
		goto out;
J
Josef Bacik 已提交
356

357 358
	*cache_ret = cache;
	goto again;
J
Josef Bacik 已提交
359 360 361

out:
	return -ENOSPC;
362 363
}

C
Chris Mason 已提交
364 365
static u64 div_factor(u64 num, int factor)
{
366 367
	if (factor == 10)
		return num;
C
Chris Mason 已提交
368 369 370 371 372
	num *= factor;
	do_div(num, 10);
	return num;
}

J
Josef Bacik 已提交
373 374
static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
						  u64 flags)
375
{
J
Josef Bacik 已提交
376 377 378 379 380 381 382 383 384
	struct list_head *head = &info->space_info;
	struct list_head *cur;
	struct btrfs_space_info *found;
	list_for_each(cur, head) {
		found = list_entry(cur, struct btrfs_space_info, list);
		if (found->flags == flags)
			return found;
	}
	return NULL;
385 386
}

387 388 389 390
static struct btrfs_block_group_cache *
__btrfs_find_block_group(struct btrfs_root *root,
			 struct btrfs_block_group_cache *hint,
			 u64 search_start, int data, int owner)
C
Chris Mason 已提交
391
{
392
	struct btrfs_block_group_cache *cache;
393
	struct btrfs_block_group_cache *found_group = NULL;
C
Chris Mason 已提交
394 395
	struct btrfs_fs_info *info = root->fs_info;
	u64 used;
396
	u64 last = 0;
397
	u64 free_check;
398
	int full_search = 0;
399
	int factor = 10;
C
Chris Mason 已提交
400
	int wrapped = 0;
401

402 403
	if (data & BTRFS_BLOCK_GROUP_METADATA)
		factor = 9;
C
Chris Mason 已提交
404

C
Chris Mason 已提交
405
	if (search_start) {
C
Chris Mason 已提交
406
		struct btrfs_block_group_cache *shint;
C
Chris Mason 已提交
407
		shint = btrfs_lookup_first_block_group(info, search_start);
408
		if (shint && block_group_bits(shint, data) && !shint->ro) {
409
			spin_lock(&shint->lock);
C
Chris Mason 已提交
410
			used = btrfs_block_group_used(&shint->item);
411
			if (used + shint->pinned + shint->reserved <
412
			    div_factor(shint->key.offset, factor)) {
413
				spin_unlock(&shint->lock);
C
Chris Mason 已提交
414 415
				return shint;
			}
416
			spin_unlock(&shint->lock);
C
Chris Mason 已提交
417 418
		}
	}
C
Chris Mason 已提交
419
	if (hint && !hint->ro && block_group_bits(hint, data)) {
420
		spin_lock(&hint->lock);
421
		used = btrfs_block_group_used(&hint->item);
422
		if (used + hint->pinned + hint->reserved <
423
		    div_factor(hint->key.offset, factor)) {
424
			spin_unlock(&hint->lock);
425 426
			return hint;
		}
427
		spin_unlock(&hint->lock);
428
		last = hint->key.objectid + hint->key.offset;
429
	} else {
430
		if (hint)
C
Chris Mason 已提交
431
			last = max(hint->key.objectid, search_start);
432
		else
C
Chris Mason 已提交
433
			last = search_start;
434 435
	}
again:
436 437
	while (1) {
		cache = btrfs_lookup_first_block_group(root->fs_info, last);
J
Josef Bacik 已提交
438 439
		if (!cache)
			break;
440

441
		spin_lock(&cache->lock);
442 443 444
		last = cache->key.objectid + cache->key.offset;
		used = btrfs_block_group_used(&cache->item);

445
		if (!cache->ro && block_group_bits(cache, data)) {
C
Chris Mason 已提交
446
			free_check = div_factor(cache->key.offset, factor);
447 448
			if (used + cache->pinned + cache->reserved <
			    free_check) {
449
				found_group = cache;
450
				spin_unlock(&cache->lock);
451 452
				goto found;
			}
453
		}
454
		spin_unlock(&cache->lock);
455
		cond_resched();
C
Chris Mason 已提交
456
	}
C
Chris Mason 已提交
457 458 459 460 461 462
	if (!wrapped) {
		last = search_start;
		wrapped = 1;
		goto again;
	}
	if (!full_search && factor < 10) {
C
Chris Mason 已提交
463
		last = search_start;
464
		full_search = 1;
C
Chris Mason 已提交
465
		factor = 10;
466 467
		goto again;
	}
C
Chris Mason 已提交
468
found:
469
	return found_group;
C
Chris Mason 已提交
470 471
}

472 473 474 475 476 477 478 479 480 481
struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
						 struct btrfs_block_group_cache
						 *hint, u64 search_start,
						 int data, int owner)
{

	struct btrfs_block_group_cache *ret;
	ret = __btrfs_find_block_group(root, hint, search_start, data, owner);
	return ret;
}
J
Josef Bacik 已提交
482

483
/* simple helper to search for an existing extent at a given offset */
Z
Zheng Yan 已提交
484
int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
485 486 487
{
	int ret;
	struct btrfs_key key;
Z
Zheng Yan 已提交
488
	struct btrfs_path *path;
489

Z
Zheng Yan 已提交
490 491
	path = btrfs_alloc_path();
	BUG_ON(!path);
492 493 494 495 496 497 498
	maybe_lock_mutex(root);
	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);
	maybe_unlock_mutex(root);
Z
Zheng Yan 已提交
499
	btrfs_free_path(path);
500 501 502
	return ret;
}

503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519
/*
 * 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 已提交
520
 * - different files inside a single subvolume
521 522 523 524 525 526 527
 * - 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 已提交
528 529 530 531
 * - 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
532
 * the file are close together.
533 534
 *
 * When a file extent is allocated the fields are filled in:
535
 *     (root_key.objectid, trans->transid, inode objectid, 1)
536 537
 *
 * When a leaf is cow'd new references are added for every file extent found
Z
Zheng Yan 已提交
538 539
 * in the leaf.  It looks similar to the create case, but trans->transid will
 * be different when the block is cow'd.
540
 *
541
 *     (root_key.objectid, trans->transid, inode objectid,
Z
Zheng Yan 已提交
542
 *      number of references in the leaf)
543
 *
544 545 546
 * When a file extent is removed either during snapshot deletion or
 * file truncation, we find the corresponding back reference and check
 * the following fields:
547
 *
548 549
 *     (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
 *      inode objectid)
550 551 552 553 554 555 556 557
 *
 * Btree extents can be referenced by:
 *
 * - Different subvolumes
 * - Different generations of the same subvolume
 *
 * When a tree block is created, back references are inserted:
 *
558
 * (root->root_key.objectid, trans->transid, level, 1)
559
 *
Z
Zheng Yan 已提交
560 561 562 563
 * 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):
564
 *
565
 * (root->root_key.objectid, trans->transid, level, 1)
566
 *
Z
Zheng Yan 已提交
567
 * When a backref is in deleting, the following fields are checked:
568 569
 *
 * if backref was for a tree root:
570
 *     (btrfs_header_owner(itself), btrfs_header_generation(itself), level)
571
 * else
572
 *     (btrfs_header_owner(parent), btrfs_header_generation(parent), level)
573
 *
Z
Zheng Yan 已提交
574
 * Back Reference Key composing:
575
 *
Z
Zheng Yan 已提交
576 577 578 579
 * 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.
580
 */
Z
Zheng Yan 已提交
581 582 583

static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
					  struct btrfs_root *root,
584 585 586 587
					  struct btrfs_path *path,
					  u64 bytenr, u64 parent,
					  u64 ref_root, u64 ref_generation,
					  u64 owner_objectid, int del)
588 589
{
	struct btrfs_key key;
Z
Zheng Yan 已提交
590 591
	struct btrfs_extent_ref *ref;
	struct extent_buffer *leaf;
592
	u64 ref_objectid;
593 594
	int ret;

Z
Zheng Yan 已提交
595 596 597 598 599 600 601 602 603 604 605 606 607 608
	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);
609
	ref_objectid = btrfs_ref_objectid(leaf, ref);
Z
Zheng Yan 已提交
610
	if (btrfs_ref_root(leaf, ref) != ref_root ||
611 612 613
	    btrfs_ref_generation(leaf, ref) != ref_generation ||
	    (ref_objectid != owner_objectid &&
	     ref_objectid != BTRFS_MULTIPLE_OBJECTIDS)) {
Z
Zheng Yan 已提交
614 615 616 617 618 619 620 621 622 623 624 625 626 627
		ret = -EIO;
		WARN_ON(1);
		goto out;
	}
	ret = 0;
out:
	return ret;
}

static int noinline insert_extent_backref(struct btrfs_trans_handle *trans,
					  struct btrfs_root *root,
					  struct btrfs_path *path,
					  u64 bytenr, u64 parent,
					  u64 ref_root, u64 ref_generation,
628
					  u64 owner_objectid)
Z
Zheng Yan 已提交
629 630 631 632 633 634
{
	struct btrfs_key key;
	struct extent_buffer *leaf;
	struct btrfs_extent_ref *ref;
	u32 num_refs;
	int ret;
635 636 637

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

Z
Zheng Yan 已提交
640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658
	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);
		btrfs_set_ref_num_refs(leaf, ref, 1);
	} else if (ret == -EEXIST) {
		u64 existing_owner;
		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);
659
			goto out;
Z
Zheng Yan 已提交
660 661 662 663 664 665 666
		}

		num_refs = btrfs_ref_num_refs(leaf, ref);
		BUG_ON(num_refs == 0);
		btrfs_set_ref_num_refs(leaf, ref, num_refs + 1);

		existing_owner = btrfs_ref_objectid(leaf, ref);
667 668
		if (existing_owner != owner_objectid &&
		    existing_owner != BTRFS_MULTIPLE_OBJECTIDS) {
Z
Zheng Yan 已提交
669 670 671 672 673
			btrfs_set_ref_objectid(leaf, ref,
					BTRFS_MULTIPLE_OBJECTIDS);
		}
		ret = 0;
	} else {
674
		goto out;
Z
Zheng Yan 已提交
675
	}
676 677 678 679
	btrfs_mark_buffer_dirty(path->nodes[0]);
out:
	btrfs_release_path(root, path);
	return ret;
680 681
}

Z
Zheng Yan 已提交
682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710
static int noinline remove_extent_backref(struct btrfs_trans_handle *trans,
					  struct btrfs_root *root,
					  struct btrfs_path *path)
{
	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);
	BUG_ON(num_refs == 0);
	num_refs -= 1;
	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;
}

static int __btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
				     struct btrfs_root *root, u64 bytenr,
				     u64 orig_parent, u64 parent,
				     u64 orig_root, u64 ref_root,
				     u64 orig_generation, u64 ref_generation,
711
				     u64 owner_objectid)
Z
Zheng Yan 已提交
712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761
{
	int ret;
	struct btrfs_root *extent_root = root->fs_info->extent_root;
	struct btrfs_path *path;

	if (root == root->fs_info->extent_root) {
		struct pending_extent_op *extent_op;
		u64 num_bytes;

		BUG_ON(owner_objectid >= BTRFS_MAX_LEVEL);
		num_bytes = btrfs_level_size(root, (int)owner_objectid);
		if (test_range_bit(&root->fs_info->extent_ins, bytenr,
				bytenr + num_bytes - 1, EXTENT_LOCKED, 0)) {
			u64 priv;
			ret = get_state_private(&root->fs_info->extent_ins,
						bytenr, &priv);
			BUG_ON(ret);
			extent_op = (struct pending_extent_op *)
							(unsigned long)priv;
			BUG_ON(extent_op->parent != orig_parent);
			BUG_ON(extent_op->generation != orig_generation);
			extent_op->parent = parent;
			extent_op->generation = ref_generation;
		} else {
			extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
			BUG_ON(!extent_op);

			extent_op->type = PENDING_BACKREF_UPDATE;
			extent_op->bytenr = bytenr;
			extent_op->num_bytes = num_bytes;
			extent_op->parent = parent;
			extent_op->orig_parent = orig_parent;
			extent_op->generation = ref_generation;
			extent_op->orig_generation = orig_generation;
			extent_op->level = (int)owner_objectid;

			set_extent_bits(&root->fs_info->extent_ins,
					bytenr, bytenr + num_bytes - 1,
					EXTENT_LOCKED, GFP_NOFS);
			set_state_private(&root->fs_info->extent_ins,
					  bytenr, (unsigned long)extent_op);
		}
		return 0;
	}

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
	ret = lookup_extent_backref(trans, extent_root, path,
				    bytenr, orig_parent, orig_root,
762
				    orig_generation, owner_objectid, 1);
Z
Zheng Yan 已提交
763 764 765 766 767 768 769
	if (ret)
		goto out;
	ret = remove_extent_backref(trans, extent_root, path);
	if (ret)
		goto out;
	ret = insert_extent_backref(trans, extent_root, path, bytenr,
				    parent, ref_root, ref_generation,
770
				    owner_objectid);
Z
Zheng Yan 已提交
771 772 773 774 775 776 777 778 779 780 781 782
	BUG_ON(ret);
	finish_current_insert(trans, extent_root);
	del_pending_extents(trans, extent_root);
out:
	btrfs_free_path(path);
	return ret;
}

int btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
			    struct btrfs_root *root, u64 bytenr,
			    u64 orig_parent, u64 parent,
			    u64 ref_root, u64 ref_generation,
783
			    u64 owner_objectid)
Z
Zheng Yan 已提交
784 785 786 787 788 789 790 791 792
{
	int ret;
	if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
	    owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
		return 0;
	maybe_lock_mutex(root);
	ret = __btrfs_update_extent_ref(trans, root, bytenr, orig_parent,
					parent, ref_root, ref_root,
					ref_generation, ref_generation,
793
					owner_objectid);
Z
Zheng Yan 已提交
794 795 796 797
	maybe_unlock_mutex(root);
	return ret;
}

798
static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
799 800 801 802
				  struct btrfs_root *root, u64 bytenr,
				  u64 orig_parent, u64 parent,
				  u64 orig_root, u64 ref_root,
				  u64 orig_generation, u64 ref_generation,
803
				  u64 owner_objectid)
C
Chris Mason 已提交
804
{
805
	struct btrfs_path *path;
C
Chris Mason 已提交
806
	int ret;
C
Chris Mason 已提交
807
	struct btrfs_key key;
808
	struct extent_buffer *l;
C
Chris Mason 已提交
809
	struct btrfs_extent_item *item;
C
Chris Mason 已提交
810
	u32 refs;
C
Chris Mason 已提交
811

812
	path = btrfs_alloc_path();
813 814
	if (!path)
		return -ENOMEM;
815

816
	path->reada = 1;
817
	key.objectid = bytenr;
Z
Zheng Yan 已提交
818 819 820
	key.type = BTRFS_EXTENT_ITEM_KEY;
	key.offset = (u64)-1;

821
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
822
				0, 1);
823 824
	if (ret < 0)
		return ret;
Z
Zheng Yan 已提交
825 826 827
	BUG_ON(ret == 0 || path->slots[0] == 0);

	path->slots[0]--;
828
	l = path->nodes[0];
Z
Zheng Yan 已提交
829 830 831 832 833

	btrfs_item_key_to_cpu(l, &key, path->slots[0]);
	BUG_ON(key.objectid != bytenr);
	BUG_ON(key.type != BTRFS_EXTENT_ITEM_KEY);

834
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
835 836
	refs = btrfs_extent_refs(l, item);
	btrfs_set_extent_refs(l, item, refs + 1);
837
	btrfs_mark_buffer_dirty(path->nodes[0]);
838

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

841
	path->reada = 1;
Z
Zheng Yan 已提交
842 843 844
	ret = insert_extent_backref(trans, root->fs_info->extent_root,
				    path, bytenr, parent,
				    ref_root, ref_generation,
845
				    owner_objectid);
846
	BUG_ON(ret);
847
	finish_current_insert(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
848
	del_pending_extents(trans, root->fs_info->extent_root);
849 850

	btrfs_free_path(path);
C
Chris Mason 已提交
851 852 853
	return 0;
}

854
int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
855 856 857
			 struct btrfs_root *root,
			 u64 bytenr, u64 num_bytes, u64 parent,
			 u64 ref_root, u64 ref_generation,
858
			 u64 owner_objectid)
859 860
{
	int ret;
Z
Zheng Yan 已提交
861 862 863 864 865 866
	if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
	    owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
		return 0;
	maybe_lock_mutex(root);
	ret = __btrfs_inc_extent_ref(trans, root, bytenr, 0, parent,
				     0, ref_root, 0, ref_generation,
867
				     owner_objectid);
Z
Zheng Yan 已提交
868
	maybe_unlock_mutex(root);
869 870 871
	return ret;
}

872 873 874 875 876 877 878 879
int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root)
{
	finish_current_insert(trans, root->fs_info->extent_root);
	del_pending_extents(trans, root->fs_info->extent_root);
	return 0;
}

Z
Zheng Yan 已提交
880 881 882
int btrfs_lookup_extent_ref(struct btrfs_trans_handle *trans,
			    struct btrfs_root *root, u64 bytenr,
			    u64 num_bytes, u32 *refs)
883
{
884
	struct btrfs_path *path;
885
	int ret;
C
Chris Mason 已提交
886
	struct btrfs_key key;
887
	struct extent_buffer *l;
C
Chris Mason 已提交
888
	struct btrfs_extent_item *item;
889

890
	WARN_ON(num_bytes < root->sectorsize);
891
	path = btrfs_alloc_path();
892
	path->reada = 1;
893 894
	key.objectid = bytenr;
	key.offset = num_bytes;
895
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
896
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
897
				0, 0);
898 899
	if (ret < 0)
		goto out;
900 901
	if (ret != 0) {
		btrfs_print_leaf(root, path->nodes[0]);
902
		printk("failed to find block number %Lu\n", bytenr);
903
		BUG();
904 905
	}
	l = path->nodes[0];
906
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
907
	*refs = btrfs_extent_refs(l, item);
908
out:
909
	btrfs_free_path(path);
910 911 912
	return 0;
}

913 914 915
static int get_reference_status(struct btrfs_root *root, u64 bytenr,
				u64 parent_gen, u64 ref_objectid,
			        u64 *min_generation, u32 *ref_count)
916 917 918
{
	struct btrfs_root *extent_root = root->fs_info->extent_root;
	struct btrfs_path *path;
919 920 921 922
	struct extent_buffer *leaf;
	struct btrfs_extent_ref *ref_item;
	struct btrfs_key key;
	struct btrfs_key found_key;
923
	u64 root_objectid = root->root_key.objectid;
924
	u64 ref_generation;
925 926
	u32 nritems;
	int ret;
927

928
	key.objectid = bytenr;
Z
Zheng Yan 已提交
929
	key.offset = (u64)-1;
930
	key.type = BTRFS_EXTENT_ITEM_KEY;
931

932 933
	path = btrfs_alloc_path();
	mutex_lock(&root->fs_info->alloc_mutex);
934 935 936 937
	ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
	if (ret < 0)
		goto out;
	BUG_ON(ret == 0);
Z
Zheng Yan 已提交
938 939
	if (ret < 0 || path->slots[0] == 0)
		goto out;
940

Z
Zheng Yan 已提交
941
	path->slots[0]--;
942 943
	leaf = path->nodes[0];
	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
944 945 946

	if (found_key.objectid != bytenr ||
	    found_key.type != BTRFS_EXTENT_ITEM_KEY) {
947
		ret = 1;
948 949 950
		goto out;
	}

951 952 953
	*ref_count = 0;
	*min_generation = (u64)-1;

954
	while (1) {
955 956
		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
957 958
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(extent_root, path);
959 960
			if (ret < 0)
				goto out;
961 962 963 964
			if (ret == 0)
				continue;
			break;
		}
965
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
966 967
		if (found_key.objectid != bytenr)
			break;
968

969 970 971 972 973
		if (found_key.type != BTRFS_EXTENT_REF_KEY) {
			path->slots[0]++;
			continue;
		}

974
		ref_item = btrfs_item_ptr(leaf, path->slots[0],
975
					  struct btrfs_extent_ref);
976 977
		ref_generation = btrfs_ref_generation(leaf, ref_item);
		/*
Z
Zheng Yan 已提交
978
		 * For (parent_gen > 0 && parent_gen > ref_generation):
979
		 *
980 981
		 * we reach here through the oldest root, therefore
		 * all other reference from same snapshot should have
982 983 984 985 986 987
		 * a larger generation.
		 */
		if ((root_objectid != btrfs_ref_root(leaf, ref_item)) ||
		    (parent_gen > 0 && parent_gen > ref_generation) ||
		    (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
		     ref_objectid != btrfs_ref_objectid(leaf, ref_item))) {
Z
Zheng Yan 已提交
988
			*ref_count = 2;
989
			break;
990
		}
991 992 993 994 995

		*ref_count = 1;
		if (*min_generation > ref_generation)
			*min_generation = ref_generation;

996 997
		path->slots[0]++;
	}
998 999 1000 1001 1002 1003 1004
	ret = 0;
out:
	mutex_unlock(&root->fs_info->alloc_mutex);
	btrfs_free_path(path);
	return ret;
}

1005 1006
int btrfs_cross_ref_exists(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root,
1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019
			   struct btrfs_key *key, u64 bytenr)
{
	struct btrfs_root *old_root;
	struct btrfs_path *path = NULL;
	struct extent_buffer *eb;
	struct btrfs_file_extent_item *item;
	u64 ref_generation;
	u64 min_generation;
	u64 extent_start;
	u32 ref_count;
	int level;
	int ret;

1020
	BUG_ON(trans == NULL);
1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035
	BUG_ON(key->type != BTRFS_EXTENT_DATA_KEY);
	ret = get_reference_status(root, bytenr, 0, key->objectid,
				   &min_generation, &ref_count);
	if (ret)
		return ret;

	if (ref_count != 1)
		return 1;

	old_root = root->dirty_root->root;
	ref_generation = old_root->root_key.offset;

	/* all references are created in running transaction */
	if (min_generation > ref_generation) {
		ret = 0;
C
Chris Mason 已提交
1036 1037
		goto out;
	}
1038 1039 1040 1041

	path = btrfs_alloc_path();
	if (!path) {
		ret = -ENOMEM;
1042 1043
		goto out;
	}
1044 1045 1046 1047 1048

	path->skip_locking = 1;
	/* if no item found, the extent is referenced by other snapshot */
	ret = btrfs_search_slot(NULL, old_root, key, path, 0, 0);
	if (ret)
1049 1050
		goto out;

1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065
	eb = path->nodes[0];
	item = btrfs_item_ptr(eb, path->slots[0],
			      struct btrfs_file_extent_item);
	if (btrfs_file_extent_type(eb, item) != BTRFS_FILE_EXTENT_REG ||
	    btrfs_file_extent_disk_bytenr(eb, item) != bytenr) {
		ret = 1;
		goto out;
	}

	for (level = BTRFS_MAX_LEVEL - 1; level >= -1; level--) {
		if (level >= 0) {
			eb = path->nodes[level];
			if (!eb)
				continue;
			extent_start = eb->start;
1066
		} else
1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081
			extent_start = bytenr;

		ret = get_reference_status(root, extent_start, ref_generation,
					   0, &min_generation, &ref_count);
		if (ret)
			goto out;

		if (ref_count != 1) {
			ret = 1;
			goto out;
		}
		if (level >= 0)
			ref_generation = btrfs_header_generation(eb);
	}
	ret = 0;
1082
out:
1083 1084 1085
	if (path)
		btrfs_free_path(path);
	return ret;
1086
}
C
Chris Mason 已提交
1087

Z
Zheng Yan 已提交
1088 1089
int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		    struct extent_buffer *buf, u32 nr_extents)
C
Chris Mason 已提交
1090
{
1091
	struct btrfs_key key;
1092
	struct btrfs_file_extent_item *fi;
Z
Zheng Yan 已提交
1093 1094
	u64 root_gen;
	u32 nritems;
C
Chris Mason 已提交
1095
	int i;
1096
	int level;
Z
Zheng Yan 已提交
1097
	int ret = 0;
Z
Zheng Yan 已提交
1098
	int shared = 0;
1099

1100
	if (!root->ref_cows)
1101
		return 0;
1102

Z
Zheng Yan 已提交
1103 1104 1105 1106 1107 1108 1109 1110
	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;
	}

1111
	level = btrfs_header_level(buf);
1112
	nritems = btrfs_header_nritems(buf);
C
Chris Mason 已提交
1113

Z
Zheng Yan 已提交
1114
	if (level == 0) {
Y
Yan Zheng 已提交
1115 1116 1117
		struct btrfs_leaf_ref *ref;
		struct btrfs_extent_info *info;

Z
Zheng Yan 已提交
1118
		ref = btrfs_alloc_leaf_ref(root, nr_extents);
Y
Yan Zheng 已提交
1119
		if (!ref) {
Z
Zheng Yan 已提交
1120
			ret = -ENOMEM;
Y
Yan Zheng 已提交
1121 1122 1123
			goto out;
		}

Z
Zheng Yan 已提交
1124
		ref->root_gen = root_gen;
Y
Yan Zheng 已提交
1125 1126 1127
		ref->bytenr = buf->start;
		ref->owner = btrfs_header_owner(buf);
		ref->generation = btrfs_header_generation(buf);
Z
Zheng Yan 已提交
1128
		ref->nritems = nr_extents;
Y
Yan Zheng 已提交
1129
		info = ref->extents;
1130

Z
Zheng Yan 已提交
1131
		for (i = 0; nr_extents > 0 && i < nritems; i++) {
Y
Yan Zheng 已提交
1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152
			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 已提交
1153
		ret = btrfs_add_leaf_ref(root, ref, shared);
Y
Yan Zheng 已提交
1154 1155 1156 1157 1158 1159 1160 1161
		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 已提交
1162
		WARN_ON(ret);
1163
		btrfs_free_leaf_ref(root, ref);
Y
Yan Zheng 已提交
1164 1165
	}
out:
Z
Zheng Yan 已提交
1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186
	return ret;
}

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)
{
	u64 bytenr;
	u64 ref_root;
	u64 orig_root;
	u64 ref_generation;
	u64 orig_generation;
	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;
	int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
1187
			    u64, u64, u64, u64, u64, u64, u64, u64);
Z
Zheng Yan 已提交
1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210

	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);

	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;
	}

	for (i = 0; i < nritems; i++) {
		cond_resched();
1211
		if (level == 0) {
1212 1213
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1214
				continue;
1215
			fi = btrfs_item_ptr(buf, i,
1216
					    struct btrfs_file_extent_item);
1217
			if (btrfs_file_extent_type(buf, fi) ==
1218 1219
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
Z
Zheng Yan 已提交
1220 1221
			bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (bytenr == 0)
1222
				continue;
Z
Zheng Yan 已提交
1223 1224 1225 1226 1227 1228 1229 1230

			nr_file_extents++;

			maybe_lock_mutex(root);
			ret = process_func(trans, root, bytenr,
					   orig_buf->start, buf->start,
					   orig_root, ref_root,
					   orig_generation, ref_generation,
1231
					   key.objectid);
Z
Zheng Yan 已提交
1232 1233 1234 1235 1236 1237 1238
			maybe_unlock_mutex(root);

			if (ret) {
				faili = i;
				WARN_ON(1);
				goto fail;
			}
1239
		} else {
1240
			bytenr = btrfs_node_blockptr(buf, i);
Z
Zheng Yan 已提交
1241 1242 1243 1244 1245
			maybe_lock_mutex(root);
			ret = process_func(trans, root, bytenr,
					   orig_buf->start, buf->start,
					   orig_root, ref_root,
					   orig_generation, ref_generation,
1246
					   level - 1);
Z
Zheng Yan 已提交
1247 1248 1249 1250 1251 1252
			maybe_unlock_mutex(root);
			if (ret) {
				faili = i;
				WARN_ON(1);
				goto fail;
			}
1253 1254
		}
	}
Z
Zheng Yan 已提交
1255 1256 1257 1258 1259 1260 1261 1262 1263 1264
out:
	if (nr_extents) {
		if (level == 0)
			*nr_extents = nr_file_extents;
		else
			*nr_extents = nritems;
	}
	return 0;
fail:
	WARN_ON(1);
1265
	return ret;
C
Chris Mason 已提交
1266 1267
}

Z
Zheng Yan 已提交
1268 1269 1270 1271 1272 1273 1274 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 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321
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;
			maybe_lock_mutex(root);
			ret = __btrfs_update_extent_ref(trans, root, bytenr,
					    orig_buf->start, buf->start,
					    orig_root, ref_root,
					    orig_generation, ref_generation,
1322
					    key.objectid);
Z
Zheng Yan 已提交
1323 1324 1325 1326 1327 1328 1329 1330 1331 1332
			maybe_unlock_mutex(root);
			if (ret)
				goto fail;
		} else {
			bytenr = btrfs_node_blockptr(buf, slot);
			maybe_lock_mutex(root);
			ret = __btrfs_update_extent_ref(trans, root, bytenr,
					    orig_buf->start, buf->start,
					    orig_root, ref_root,
					    orig_generation, ref_generation,
1333
					    level - 1);
Z
Zheng Yan 已提交
1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344
			maybe_unlock_mutex(root);
			if (ret)
				goto fail;
		}
	}
	return 0;
fail:
	WARN_ON(1);
	return -1;
}

C
Chris Mason 已提交
1345 1346 1347 1348 1349 1350 1351 1352
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;
	int pending_ret;
	struct btrfs_root *extent_root = root->fs_info->extent_root;
1353 1354
	unsigned long bi;
	struct extent_buffer *leaf;
C
Chris Mason 已提交
1355 1356

	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1357 1358
	if (ret < 0)
		goto fail;
C
Chris Mason 已提交
1359
	BUG_ON(ret);
1360 1361 1362 1363 1364

	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 已提交
1365
	btrfs_release_path(extent_root, path);
1366
fail:
C
Chris Mason 已提交
1367 1368 1369 1370 1371 1372 1373 1374 1375 1376
	finish_current_insert(trans, extent_root);
	pending_ret = del_pending_extents(trans, extent_root);
	if (ret)
		return ret;
	if (pending_ret)
		return pending_ret;
	return 0;

}

1377 1378
int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root)
C
Chris Mason 已提交
1379
{
J
Josef Bacik 已提交
1380 1381
	struct btrfs_block_group_cache *cache, *entry;
	struct rb_node *n;
C
Chris Mason 已提交
1382 1383 1384
	int err = 0;
	int werr = 0;
	struct btrfs_path *path;
1385
	u64 last = 0;
C
Chris Mason 已提交
1386 1387 1388 1389 1390

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

1391
	mutex_lock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
1392
	while(1) {
J
Josef Bacik 已提交
1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404
		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);
1405

J
Josef Bacik 已提交
1406
		if (!cache)
1407
			break;
J
Josef Bacik 已提交
1408

1409
		cache->dirty = 0;
J
Josef Bacik 已提交
1410 1411
		last += cache->key.offset;

1412 1413 1414 1415 1416 1417 1418 1419 1420 1421
		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 已提交
1422 1423 1424
		}
	}
	btrfs_free_path(path);
1425
	mutex_unlock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
1426 1427 1428
	return werr;
}

1429 1430 1431 1432 1433 1434 1435 1436 1437 1438
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) {
		found->total_bytes += total_bytes;
		found->bytes_used += bytes_used;
1439
		found->full = 0;
1440 1441 1442 1443 1444 1445 1446 1447
		*space_info = found;
		return 0;
	}
	found = kmalloc(sizeof(*found), GFP_NOFS);
	if (!found)
		return -ENOMEM;

	list_add(&found->list, &info->space_info);
J
Josef Bacik 已提交
1448 1449
	INIT_LIST_HEAD(&found->block_groups);
	spin_lock_init(&found->lock);
1450 1451 1452 1453
	found->flags = flags;
	found->total_bytes = total_bytes;
	found->bytes_used = bytes_used;
	found->bytes_pinned = 0;
1454
	found->bytes_reserved = 0;
1455
	found->full = 0;
C
Chris Mason 已提交
1456
	found->force_alloc = 0;
1457 1458 1459 1460
	*space_info = found;
	return 0;
}

1461 1462 1463
static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
{
	u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1464
				   BTRFS_BLOCK_GROUP_RAID1 |
C
Chris Mason 已提交
1465
				   BTRFS_BLOCK_GROUP_RAID10 |
1466
				   BTRFS_BLOCK_GROUP_DUP);
1467 1468 1469 1470 1471 1472 1473 1474 1475
	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;
	}
}
1476

1477
static u64 reduce_alloc_profile(struct btrfs_root *root, u64 flags)
1478
{
1479 1480 1481 1482 1483 1484 1485
	u64 num_devices = root->fs_info->fs_devices->num_devices;

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

1486 1487
	if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
	    (flags & (BTRFS_BLOCK_GROUP_RAID1 |
1488
		      BTRFS_BLOCK_GROUP_RAID10))) {
1489
		flags &= ~BTRFS_BLOCK_GROUP_DUP;
1490
	}
1491 1492

	if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
1493
	    (flags & BTRFS_BLOCK_GROUP_RAID10)) {
1494
		flags &= ~BTRFS_BLOCK_GROUP_RAID1;
1495
	}
1496 1497 1498 1499 1500 1501 1502 1503 1504

	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;
}

1505 1506
static int do_chunk_alloc(struct btrfs_trans_handle *trans,
			  struct btrfs_root *extent_root, u64 alloc_bytes,
C
Chris Mason 已提交
1507
			  u64 flags, int force)
1508 1509 1510 1511 1512
{
	struct btrfs_space_info *space_info;
	u64 thresh;
	u64 start;
	u64 num_bytes;
1513
	int ret = 0, waited = 0;
1514

1515
	flags = reduce_alloc_profile(extent_root, flags);
1516

1517
	space_info = __find_space_info(extent_root->fs_info, flags);
1518 1519 1520 1521 1522
	if (!space_info) {
		ret = update_space_info(extent_root->fs_info, flags,
					0, 0, &space_info);
		BUG_ON(ret);
	}
1523 1524
	BUG_ON(!space_info);

C
Chris Mason 已提交
1525 1526 1527 1528
	if (space_info->force_alloc) {
		force = 1;
		space_info->force_alloc = 0;
	}
1529
	if (space_info->full)
1530
		goto out;
1531

1532
	thresh = div_factor(space_info->total_bytes, 6);
C
Chris Mason 已提交
1533
	if (!force &&
1534 1535
	   (space_info->bytes_used + space_info->bytes_pinned +
	    space_info->bytes_reserved + alloc_bytes) < thresh)
1536
		goto out;
1537

1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549
	while (!mutex_trylock(&extent_root->fs_info->chunk_mutex)) {
		if (!force)
			goto out;
		mutex_unlock(&extent_root->fs_info->alloc_mutex);
		cond_resched();
		mutex_lock(&extent_root->fs_info->alloc_mutex);
		waited = 1;
	}

	if (waited && space_info->full)
		goto out_unlock;

1550 1551 1552 1553
	ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
	if (ret == -ENOSPC) {
printk("space info full %Lu\n", flags);
		space_info->full = 1;
1554
		goto out_unlock;
1555 1556 1557 1558
	}
	BUG_ON(ret);

	ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1559
		     BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1560
	BUG_ON(ret);
J
Josef Bacik 已提交
1561

1562
out_unlock:
1563
	mutex_unlock(&extent_root->fs_info->chunk_mutex);
1564
out:
J
Josef Bacik 已提交
1565
	return ret;
1566 1567
}

C
Chris Mason 已提交
1568 1569
static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
1570
			      u64 bytenr, u64 num_bytes, int alloc,
1571
			      int mark_free)
C
Chris Mason 已提交
1572 1573 1574
{
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *info = root->fs_info;
1575
	u64 total = num_bytes;
C
Chris Mason 已提交
1576
	u64 old_val;
1577
	u64 byte_in_group;
C
Chris Mason 已提交
1578

1579
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
C
Chris Mason 已提交
1580
	while(total) {
1581
		cache = btrfs_lookup_block_group(info, bytenr);
C
Chris Mason 已提交
1582
		if (!cache) {
C
Chris Mason 已提交
1583
			return -1;
C
Chris Mason 已提交
1584
		}
1585 1586
		byte_in_group = bytenr - cache->key.objectid;
		WARN_ON(byte_in_group > cache->key.offset);
C
Chris Mason 已提交
1587

1588
		spin_lock(&cache->lock);
J
Josef Bacik 已提交
1589
		cache->dirty = 1;
C
Chris Mason 已提交
1590
		old_val = btrfs_block_group_used(&cache->item);
1591
		num_bytes = min(total, cache->key.offset - byte_in_group);
C
Chris Mason 已提交
1592
		if (alloc) {
1593
			old_val += num_bytes;
1594
			cache->space_info->bytes_used += num_bytes;
1595 1596
			btrfs_set_block_group_used(&cache->item, old_val);
			spin_unlock(&cache->lock);
C
Chris Mason 已提交
1597
		} else {
1598
			old_val -= num_bytes;
1599
			cache->space_info->bytes_used -= num_bytes;
1600 1601
			btrfs_set_block_group_used(&cache->item, old_val);
			spin_unlock(&cache->lock);
1602
			if (mark_free) {
J
Josef Bacik 已提交
1603 1604 1605 1606 1607
				int ret;
				ret = btrfs_add_free_space(cache, bytenr,
							   num_bytes);
				if (ret)
					return -1;
1608
			}
C
Chris Mason 已提交
1609
		}
1610 1611
		total -= num_bytes;
		bytenr += num_bytes;
C
Chris Mason 已提交
1612 1613 1614
	}
	return 0;
}
1615

1616 1617
static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
{
J
Josef Bacik 已提交
1618 1619 1620 1621
	struct btrfs_block_group_cache *cache;

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

	return cache->key.objectid;
1625 1626
}

1627
int btrfs_update_pinned_extents(struct btrfs_root *root,
1628 1629 1630 1631 1632 1633
				u64 bytenr, u64 num, int pin)
{
	u64 len;
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *fs_info = root->fs_info;

1634
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1635 1636 1637 1638 1639 1640 1641 1642 1643
	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);
	}
	while (num > 0) {
		cache = btrfs_lookup_block_group(fs_info, bytenr);
1644 1645 1646
		BUG_ON(!cache);
		len = min(num, cache->key.offset -
			  (bytenr - cache->key.objectid));
1647
		if (pin) {
1648 1649 1650 1651
			spin_lock(&cache->lock);
			cache->pinned += len;
			cache->space_info->bytes_pinned += len;
			spin_unlock(&cache->lock);
1652 1653
			fs_info->total_pinned += len;
		} else {
1654 1655 1656 1657
			spin_lock(&cache->lock);
			cache->pinned -= len;
			cache->space_info->bytes_pinned -= len;
			spin_unlock(&cache->lock);
1658 1659 1660 1661 1662 1663 1664
			fs_info->total_pinned -= len;
		}
		bytenr += len;
		num -= len;
	}
	return 0;
}
C
Chris Mason 已提交
1665

1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695
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;

	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
	while (num > 0) {
		cache = btrfs_lookup_block_group(fs_info, bytenr);
		BUG_ON(!cache);
		len = min(num, cache->key.offset -
			  (bytenr - cache->key.objectid));
		if (reserve) {
			spin_lock(&cache->lock);
			cache->reserved += len;
			cache->space_info->bytes_reserved += len;
			spin_unlock(&cache->lock);
		} else {
			spin_lock(&cache->lock);
			cache->reserved -= len;
			cache->space_info->bytes_reserved -= len;
			spin_unlock(&cache->lock);
		}
		bytenr += len;
		num -= len;
	}
	return 0;
}

1696
int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
C
Chris Mason 已提交
1697 1698
{
	u64 last = 0;
1699 1700
	u64 start;
	u64 end;
1701
	struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
C
Chris Mason 已提交
1702 1703 1704
	int ret;

	while(1) {
1705 1706 1707
		ret = find_first_extent_bit(pinned_extents, last,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
C
Chris Mason 已提交
1708
			break;
1709 1710
		set_extent_dirty(copy, start, end, GFP_NOFS);
		last = end + 1;
C
Chris Mason 已提交
1711 1712 1713 1714 1715 1716
	}
	return 0;
}

int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
1717
			       struct extent_io_tree *unpin)
1718
{
1719 1720
	u64 start;
	u64 end;
1721
	int ret;
J
Josef Bacik 已提交
1722
	struct btrfs_block_group_cache *cache;
1723

1724
	mutex_lock(&root->fs_info->alloc_mutex);
1725
	while(1) {
1726 1727 1728
		ret = find_first_extent_bit(unpin, 0, &start, &end,
					    EXTENT_DIRTY);
		if (ret)
1729
			break;
1730
		btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
1731
		clear_extent_dirty(unpin, start, end, GFP_NOFS);
J
Josef Bacik 已提交
1732 1733 1734
		cache = btrfs_lookup_block_group(root->fs_info, start);
		if (cache->cached)
			btrfs_add_free_space(cache, start, end - start + 1);
1735 1736 1737 1738 1739
		if (need_resched()) {
			mutex_unlock(&root->fs_info->alloc_mutex);
			cond_resched();
			mutex_lock(&root->fs_info->alloc_mutex);
		}
1740
	}
1741
	mutex_unlock(&root->fs_info->alloc_mutex);
1742 1743 1744
	return 0;
}

1745 1746
static int finish_current_insert(struct btrfs_trans_handle *trans,
				 struct btrfs_root *extent_root)
C
Chris Mason 已提交
1747
{
1748 1749
	u64 start;
	u64 end;
Z
Zheng Yan 已提交
1750
	u64 priv;
1751 1752
	struct btrfs_fs_info *info = extent_root->fs_info;
	struct btrfs_path *path;
Z
Zheng Yan 已提交
1753 1754 1755
	struct btrfs_extent_ref *ref;
	struct pending_extent_op *extent_op;
	struct btrfs_key key;
C
Chris Mason 已提交
1756
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
1757
	int ret;
1758
	int err = 0;
C
Chris Mason 已提交
1759

1760
	WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
1761
	btrfs_set_stack_extent_refs(&extent_item, 1);
1762
	path = btrfs_alloc_path();
C
Chris Mason 已提交
1763

1764
	while(1) {
1765 1766 1767
		ret = find_first_extent_bit(&info->extent_ins, 0, &start,
					    &end, EXTENT_LOCKED);
		if (ret)
1768 1769
			break;

Z
Zheng Yan 已提交
1770 1771 1772 1773 1774 1775 1776 1777 1778
		ret = get_state_private(&info->extent_ins, start, &priv);
		BUG_ON(ret);
		extent_op = (struct pending_extent_op *)(unsigned long)priv;

		if (extent_op->type == PENDING_EXTENT_INSERT) {
			key.objectid = start;
			key.offset = end + 1 - start;
			key.type = BTRFS_EXTENT_ITEM_KEY;
			err = btrfs_insert_item(trans, extent_root, &key,
1779
					&extent_item, sizeof(extent_item));
Z
Zheng Yan 已提交
1780
			BUG_ON(err);
1781

Z
Zheng Yan 已提交
1782 1783
			clear_extent_bits(&info->extent_ins, start, end,
					  EXTENT_LOCKED, GFP_NOFS);
1784

Z
Zheng Yan 已提交
1785 1786 1787 1788
			err = insert_extent_backref(trans, extent_root, path,
						start, extent_op->parent,
						extent_root->root_key.objectid,
						extent_op->generation,
1789
						extent_op->level);
Z
Zheng Yan 已提交
1790 1791 1792 1793 1794
			BUG_ON(err);
		} else if (extent_op->type == PENDING_BACKREF_UPDATE) {
			err = lookup_extent_backref(trans, extent_root, path,
						start, extent_op->orig_parent,
						extent_root->root_key.objectid,
1795 1796
						extent_op->orig_generation,
						extent_op->level, 0);
Z
Zheng Yan 已提交
1797
			BUG_ON(err);
1798

Z
Zheng Yan 已提交
1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813
			clear_extent_bits(&info->extent_ins, start, end,
					  EXTENT_LOCKED, GFP_NOFS);

			key.objectid = start;
			key.offset = extent_op->parent;
			key.type = BTRFS_EXTENT_REF_KEY;
			err = btrfs_set_item_key_safe(trans, extent_root, path,
						      &key);
			BUG_ON(err);
			ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
					     struct btrfs_extent_ref);
			btrfs_set_ref_generation(path->nodes[0], ref,
						 extent_op->generation);
			btrfs_mark_buffer_dirty(path->nodes[0]);
			btrfs_release_path(extent_root, path);
1814
		} else {
Z
Zheng Yan 已提交
1815
			BUG_ON(1);
1816
		}
Z
Zheng Yan 已提交
1817 1818
		kfree(extent_op);

1819 1820 1821 1822 1823
		if (need_resched()) {
			mutex_unlock(&extent_root->fs_info->alloc_mutex);
			cond_resched();
			mutex_lock(&extent_root->fs_info->alloc_mutex);
		}
C
Chris Mason 已提交
1824
	}
1825
	btrfs_free_path(path);
C
Chris Mason 已提交
1826 1827 1828
	return 0;
}

Z
Zheng Yan 已提交
1829 1830 1831
static int pin_down_bytes(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root,
			  u64 bytenr, u64 num_bytes, int is_data)
C
Chris Mason 已提交
1832
{
1833
	int err = 0;
Z
Zheng Yan 已提交
1834
	struct extent_buffer *buf;
C
Chris Mason 已提交
1835

1836
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
Z
Zheng Yan 已提交
1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853
	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 已提交
1854
		    header_owner != BTRFS_TREE_RELOC_OBJECTID &&
Z
Zheng Yan 已提交
1855 1856 1857 1858
		    header_transid == trans->transid &&
		    !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
			clean_tree_block(NULL, root, buf);
			btrfs_tree_unlock(buf);
1859
			free_extent_buffer(buf);
Z
Zheng Yan 已提交
1860
			return 1;
C
Chris Mason 已提交
1861
		}
Z
Zheng Yan 已提交
1862
		btrfs_tree_unlock(buf);
C
Chris Mason 已提交
1863
	}
Z
Zheng Yan 已提交
1864 1865 1866 1867
	free_extent_buffer(buf);
pinit:
	btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);

C
Chris Mason 已提交
1868
	BUG_ON(err < 0);
C
Chris Mason 已提交
1869 1870 1871
	return 0;
}

1872
/*
1873
 * remove an extent from the root, returns 0 on success
1874
 */
Z
Zheng Yan 已提交
1875 1876 1877
static int __free_extent(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root,
			 u64 bytenr, u64 num_bytes, u64 parent,
1878
			 u64 root_objectid, u64 ref_generation,
1879
			 u64 owner_objectid, int pin, int mark_free)
1880
{
1881
	struct btrfs_path *path;
C
Chris Mason 已提交
1882
	struct btrfs_key key;
1883 1884
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
1885
	struct extent_buffer *leaf;
1886
	int ret;
1887 1888 1889
	int extent_slot = 0;
	int found_extent = 0;
	int num_to_del = 1;
C
Chris Mason 已提交
1890
	struct btrfs_extent_item *ei;
C
Chris Mason 已提交
1891
	u32 refs;
C
Chris Mason 已提交
1892

1893
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1894
	key.objectid = bytenr;
1895
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1896
	key.offset = num_bytes;
1897
	path = btrfs_alloc_path();
1898 1899
	if (!path)
		return -ENOMEM;
1900

1901
	path->reada = 1;
1902 1903 1904
	ret = lookup_extent_backref(trans, extent_root, path,
				    bytenr, parent, root_objectid,
				    ref_generation, owner_objectid, 1);
1905
	if (ret == 0) {
1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921
		struct btrfs_key found_key;
		extent_slot = path->slots[0];
		while(extent_slot > 0) {
			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 已提交
1922 1923 1924 1925 1926 1927 1928 1929 1930
		if (!found_extent) {
			ret = remove_extent_backref(trans, extent_root, path);
			BUG_ON(ret);
			btrfs_release_path(extent_root, path);
			ret = btrfs_search_slot(trans, extent_root,
						&key, path, -1, 1);
			BUG_ON(ret);
			extent_slot = path->slots[0];
		}
1931 1932 1933 1934
	} else {
		btrfs_print_leaf(extent_root, path->nodes[0]);
		WARN_ON(1);
		printk("Unable to find ref byte nr %Lu root %Lu "
1935 1936
		       "gen %Lu owner %Lu\n", bytenr,
		       root_objectid, ref_generation, owner_objectid);
1937
	}
1938 1939

	leaf = path->nodes[0];
1940
	ei = btrfs_item_ptr(leaf, extent_slot,
C
Chris Mason 已提交
1941
			    struct btrfs_extent_item);
1942 1943 1944 1945
	refs = btrfs_extent_refs(leaf, ei);
	BUG_ON(refs == 0);
	refs -= 1;
	btrfs_set_extent_refs(leaf, ei, refs);
1946

1947 1948
	btrfs_mark_buffer_dirty(leaf);

1949
	if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
Z
Zheng Yan 已提交
1950 1951 1952 1953
		struct btrfs_extent_ref *ref;
		ref = btrfs_item_ptr(leaf, path->slots[0],
				     struct btrfs_extent_ref);
		BUG_ON(btrfs_ref_num_refs(leaf, ref) != 1);
1954 1955 1956 1957 1958 1959 1960
		/* 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 */
Z
Zheng Yan 已提交
1961
		ret = remove_extent_backref(trans, extent_root, path);
1962 1963 1964 1965 1966 1967 1968 1969 1970 1971
		BUG_ON(ret);
		/* if refs are 0, we need to setup the path for deletion */
		if (refs == 0) {
			btrfs_release_path(extent_root, path);
			ret = btrfs_search_slot(trans, extent_root, &key, path,
						-1, 1);
			BUG_ON(ret);
		}
	}

C
Chris Mason 已提交
1972
	if (refs == 0) {
1973 1974
		u64 super_used;
		u64 root_used;
1975 1976 1977 1978
#ifdef BIO_RW_DISCARD
		u64 map_length = num_bytes;
		struct btrfs_multi_bio *multi = NULL;
#endif
C
Chris Mason 已提交
1979 1980

		if (pin) {
Z
Zheng Yan 已提交
1981 1982
			ret = pin_down_bytes(trans, root, bytenr, num_bytes,
				owner_objectid >= BTRFS_FIRST_FREE_OBJECTID);
1983 1984 1985
			if (ret > 0)
				mark_free = 1;
			BUG_ON(ret < 0);
C
Chris Mason 已提交
1986 1987
		}

1988
		/* block accounting for super block */
1989
		spin_lock_irq(&info->delalloc_lock);
1990 1991 1992
		super_used = btrfs_super_bytes_used(&info->super_copy);
		btrfs_set_super_bytes_used(&info->super_copy,
					   super_used - num_bytes);
1993
		spin_unlock_irq(&info->delalloc_lock);
1994 1995

		/* block accounting for root item */
1996
		root_used = btrfs_root_used(&root->root_item);
1997
		btrfs_set_root_used(&root->root_item,
1998
					   root_used - num_bytes);
1999 2000
		ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
				      num_to_del);
Z
Zheng Yan 已提交
2001
		BUG_ON(ret);
2002
		ret = update_block_group(trans, root, bytenr, num_bytes, 0,
2003
					 mark_free);
C
Chris Mason 已提交
2004
		BUG_ON(ret);
2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024

#ifdef BIO_RW_DISCARD
		/* 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++) {
				blkdev_issue_discard(stripe->dev->bdev,
						     stripe->physical >> 9,
						     map_length >> 9);
			}
			kfree(multi);
		}
#endif
2025
	}
2026
	btrfs_free_path(path);
2027
	finish_current_insert(trans, extent_root);
2028 2029 2030 2031 2032 2033 2034
	return ret;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
2035 2036
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root)
2037 2038
{
	int ret;
C
Chris Mason 已提交
2039
	int err = 0;
Z
Zheng Yan 已提交
2040
	int mark_free = 0;
2041 2042
	u64 start;
	u64 end;
Z
Zheng Yan 已提交
2043
	u64 priv;
2044
	struct extent_io_tree *pending_del;
Z
Zheng Yan 已提交
2045 2046
	struct extent_io_tree *extent_ins;
	struct pending_extent_op *extent_op;
C
Chris Mason 已提交
2047

2048
	WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
Z
Zheng Yan 已提交
2049
	extent_ins = &extent_root->fs_info->extent_ins;
2050
	pending_del = &extent_root->fs_info->pending_del;
2051 2052

	while(1) {
2053 2054 2055
		ret = find_first_extent_bit(pending_del, 0, &start, &end,
					    EXTENT_LOCKED);
		if (ret)
2056
			break;
Z
Zheng Yan 已提交
2057 2058 2059 2060 2061

		ret = get_state_private(pending_del, start, &priv);
		BUG_ON(ret);
		extent_op = (struct pending_extent_op *)(unsigned long)priv;

2062 2063
		clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
				  GFP_NOFS);
Z
Zheng Yan 已提交
2064 2065 2066 2067 2068 2069 2070

		ret = pin_down_bytes(trans, extent_root, start,
				     end + 1 - start, 0);
		mark_free = ret > 0;
		if (!test_range_bit(extent_ins, start, end,
				    EXTENT_LOCKED, 0)) {
free_extent:
2071
			ret = __free_extent(trans, extent_root,
Z
Zheng Yan 已提交
2072 2073 2074 2075
					    start, end + 1 - start,
					    extent_op->orig_parent,
					    extent_root->root_key.objectid,
					    extent_op->orig_generation,
2076
					    extent_op->level, 0, mark_free);
Z
Zheng Yan 已提交
2077
			kfree(extent_op);
2078
		} else {
Z
Zheng Yan 已提交
2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094
			kfree(extent_op);
			ret = get_state_private(extent_ins, start, &priv);
			BUG_ON(ret);
			extent_op = (struct pending_extent_op *)
							(unsigned long)priv;

			clear_extent_bits(extent_ins, start, end,
					  EXTENT_LOCKED, GFP_NOFS);

			if (extent_op->type == PENDING_BACKREF_UPDATE)
				goto free_extent;

			ret = update_block_group(trans, extent_root, start,
						end + 1 - start, 0, mark_free);
			BUG_ON(ret);
			kfree(extent_op);
2095
		}
2096 2097
		if (ret)
			err = ret;
2098 2099 2100 2101 2102 2103

		if (need_resched()) {
			mutex_unlock(&extent_root->fs_info->alloc_mutex);
			cond_resched();
			mutex_lock(&extent_root->fs_info->alloc_mutex);
		}
2104
	}
C
Chris Mason 已提交
2105
	return err;
2106 2107 2108 2109 2110
}

/*
 * remove an extent from the root, returns 0 on success
 */
2111
static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
2112 2113 2114
			       struct btrfs_root *root,
			       u64 bytenr, u64 num_bytes, u64 parent,
			       u64 root_objectid, u64 ref_generation,
2115
			       u64 owner_objectid, int pin)
2116
{
2117
	struct btrfs_root *extent_root = root->fs_info->extent_root;
2118 2119
	int pending_ret;
	int ret;
2120

2121
	WARN_ON(num_bytes < root->sectorsize);
2122
	if (root == extent_root) {
Z
Zheng Yan 已提交
2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141
		struct pending_extent_op *extent_op;

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

		extent_op->type = PENDING_EXTENT_DELETE;
		extent_op->bytenr = bytenr;
		extent_op->num_bytes = num_bytes;
		extent_op->parent = parent;
		extent_op->orig_parent = parent;
		extent_op->generation = ref_generation;
		extent_op->orig_generation = ref_generation;
		extent_op->level = (int)owner_objectid;

		set_extent_bits(&root->fs_info->pending_del,
				bytenr, bytenr + num_bytes - 1,
				EXTENT_LOCKED, GFP_NOFS);
		set_state_private(&root->fs_info->pending_del,
				  bytenr, (unsigned long)extent_op);
2142 2143
		return 0;
	}
C
Chris Mason 已提交
2144
	/* if metadata always pin */
2145 2146
	if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
		if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
J
Josef Bacik 已提交
2147 2148
			struct btrfs_block_group_cache *cache;

2149
			/* btrfs_free_reserved_extent */
J
Josef Bacik 已提交
2150 2151 2152
			cache = btrfs_lookup_block_group(root->fs_info, bytenr);
			BUG_ON(!cache);
			btrfs_add_free_space(cache, bytenr, num_bytes);
2153
			update_reserved_extents(root, bytenr, num_bytes, 0);
2154 2155
			return 0;
		}
C
Chris Mason 已提交
2156
		pin = 1;
2157
	}
C
Chris Mason 已提交
2158 2159 2160 2161 2162

	/* if data pin when any transaction has committed this */
	if (ref_generation != trans->transid)
		pin = 1;

Z
Zheng Yan 已提交
2163
	ret = __free_extent(trans, root, bytenr, num_bytes, parent,
2164 2165
			    root_objectid, ref_generation,
			    owner_objectid, pin, pin == 0);
2166 2167

	finish_current_insert(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
2168
	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
2169 2170 2171
	return ret ? ret : pending_ret;
}

2172
int btrfs_free_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
2173 2174 2175
		      struct btrfs_root *root,
		      u64 bytenr, u64 num_bytes, u64 parent,
		      u64 root_objectid, u64 ref_generation,
2176
		      u64 owner_objectid, int pin)
2177 2178 2179 2180
{
	int ret;

	maybe_lock_mutex(root);
Z
Zheng Yan 已提交
2181
	ret = __btrfs_free_extent(trans, root, bytenr, num_bytes, parent,
2182
				  root_objectid, ref_generation,
2183
				  owner_objectid, pin);
2184 2185 2186 2187
	maybe_unlock_mutex(root);
	return ret;
}

2188 2189 2190 2191 2192 2193 2194
static u64 stripe_align(struct btrfs_root *root, u64 val)
{
	u64 mask = ((u64)root->stripesize - 1);
	u64 ret = (val + mask) & ~mask;
	return ret;
}

2195 2196 2197 2198
/*
 * 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
2199
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
2200 2201 2202
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
2203 2204 2205 2206 2207 2208 2209
static int noinline find_free_extent(struct btrfs_trans_handle *trans,
				     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)
2210
{
2211
	int ret;
2212
	u64 orig_search_start;
2213
	struct btrfs_root * root = orig_root->fs_info->extent_root;
2214
	struct btrfs_fs_info *info = root->fs_info;
2215
	u64 total_needed = num_bytes;
2216
	u64 *last_ptr = NULL;
C
Chris Mason 已提交
2217
	struct btrfs_block_group_cache *block_group;
C
Chris Mason 已提交
2218
	int chunk_alloc_done = 0;
2219
	int empty_cluster = 2 * 1024 * 1024;
C
Chris Mason 已提交
2220
	int allowed_chunk_alloc = 0;
2221

2222
	WARN_ON(num_bytes < root->sectorsize);
2223 2224
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);

C
Chris Mason 已提交
2225 2226 2227
	if (orig_root->ref_cows || empty_size)
		allowed_chunk_alloc = 1;

2228 2229
	if (data & BTRFS_BLOCK_GROUP_METADATA) {
		last_ptr = &root->fs_info->last_alloc;
2230
		empty_cluster = 256 * 1024;
2231 2232
	}

J
Josef Bacik 已提交
2233
	if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD))
2234
		last_ptr = &root->fs_info->last_data_alloc;
J
Josef Bacik 已提交
2235

2236 2237 2238
	if (last_ptr) {
		if (*last_ptr)
			hint_byte = *last_ptr;
J
Josef Bacik 已提交
2239
		else
2240 2241 2242
			empty_size += empty_cluster;
	}

2243 2244 2245
	search_start = max(search_start, first_logical_byte(root, 0));
	orig_search_start = search_start;

2246
	search_start = max(search_start, hint_byte);
2247
	total_needed += empty_size;
2248

J
Josef Bacik 已提交
2249
new_group:
2250 2251 2252 2253
	block_group = btrfs_lookup_block_group(info, search_start);
	if (!block_group)
		block_group = btrfs_lookup_first_block_group(info,
							     search_start);
J
Josef Bacik 已提交
2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269

	/*
	 * Ok this looks a little tricky, buts its really simple.  First if we
	 * didn't find a block group obviously we want to start over.
	 * Secondly, if the block group we found does not match the type we
	 * need, and we have a last_ptr and its not 0, chances are the last
	 * allocation we made was at the end of the block group, so lets go
	 * ahead and skip the looking through the rest of the block groups and
	 * start at the beginning.  This helps with metadata allocations,
	 * since you are likely to have a bunch of data block groups to search
	 * through first before you realize that you need to start over, so go
	 * ahead and start over and save the time.
	 */
	if (!block_group || (!block_group_bits(block_group, data) &&
			     last_ptr && *last_ptr)) {
		if (search_start != orig_search_start) {
2270 2271
			if (last_ptr && *last_ptr) {
				total_needed += empty_cluster;
J
Josef Bacik 已提交
2272
				*last_ptr = 0;
2273
			}
J
Josef Bacik 已提交
2274 2275 2276 2277 2278 2279
			search_start = orig_search_start;
			goto new_group;
		} else if (!chunk_alloc_done && allowed_chunk_alloc) {
			ret = do_chunk_alloc(trans, root,
					     num_bytes + 2 * 1024 * 1024,
					     data, 1);
2280
			if (ret < 0)
J
Josef Bacik 已提交
2281 2282 2283 2284 2285 2286 2287 2288
				goto error;
			BUG_ON(ret);
			chunk_alloc_done = 1;
			search_start = orig_search_start;
			goto new_group;
		} else {
			ret = -ENOSPC;
			goto error;
C
Chris Mason 已提交
2289
		}
2290
	}
2291

J
Josef Bacik 已提交
2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311
	/*
	 * this is going to seach through all of the existing block groups it
	 * can find, so if we don't find something we need to see if we can
	 * allocate what we need.
	 */
	ret = find_free_space(root, &block_group, &search_start,
			      total_needed, data);
	if (ret == -ENOSPC) {
		/*
		 * instead of allocating, start at the original search start
		 * and see if there is something to be found, if not then we
		 * allocate
		 */
		if (search_start != orig_search_start) {
			if (last_ptr && *last_ptr) {
				*last_ptr = 0;
				total_needed += empty_cluster;
			}
			search_start = orig_search_start;
			goto new_group;
2312
		}
J
Josef Bacik 已提交
2313 2314 2315 2316 2317

		/*
		 * we've already allocated, we're pretty screwed
		 */
		if (chunk_alloc_done) {
2318
			goto error;
J
Josef Bacik 已提交
2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339
		} else if (!allowed_chunk_alloc && block_group &&
			   block_group_bits(block_group, data)) {
			block_group->space_info->force_alloc = 1;
			goto error;
		} else if (!allowed_chunk_alloc) {
			goto error;
		}

		ret = do_chunk_alloc(trans, root, num_bytes + 2 * 1024 * 1024,
				     data, 1);
		if (ret < 0)
			goto error;

		BUG_ON(ret);
		chunk_alloc_done = 1;
		if (block_group)
			search_start = block_group->key.objectid +
				block_group->key.offset;
		else
			search_start = orig_search_start;
		goto new_group;
2340 2341
	}

J
Josef Bacik 已提交
2342 2343 2344
	if (ret)
		goto error;

2345 2346 2347
	search_start = stripe_align(root, search_start);
	ins->objectid = search_start;
	ins->offset = num_bytes;
2348

J
Josef Bacik 已提交
2349 2350 2351 2352 2353 2354 2355 2356
	if (ins->objectid + num_bytes >= search_end) {
		search_start = orig_search_start;
		if (chunk_alloc_done) {
			ret = -ENOSPC;
			goto error;
		}
		goto new_group;
	}
2357 2358 2359

	if (ins->objectid + num_bytes >
	    block_group->key.objectid + block_group->key.offset) {
J
Josef Bacik 已提交
2360 2361 2362 2363
		if (search_start == orig_search_start && chunk_alloc_done) {
			ret = -ENOSPC;
			goto error;
		}
2364 2365 2366 2367
		search_start = block_group->key.objectid +
			block_group->key.offset;
		goto new_group;
	}
2368

2369
	if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
2370 2371 2372 2373
	    ins->objectid < exclude_start + exclude_nr)) {
		search_start = exclude_start + exclude_nr;
		goto new_group;
	}
2374

J
Josef Bacik 已提交
2375 2376 2377
	if (!(data & BTRFS_BLOCK_GROUP_DATA))
		trans->block_group = block_group;

2378
	ins->offset = num_bytes;
2379 2380 2381
	if (last_ptr) {
		*last_ptr = ins->objectid + ins->offset;
		if (*last_ptr ==
J
Josef Bacik 已提交
2382
		    btrfs_super_total_bytes(&root->fs_info->super_copy))
2383
			*last_ptr = 0;
C
Chris Mason 已提交
2384 2385
	}

J
Josef Bacik 已提交
2386
	ret = 0;
C
Chris Mason 已提交
2387 2388
error:
	return ret;
2389
}
2390

J
Josef Bacik 已提交
2391 2392 2393 2394 2395 2396
static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
{
	struct btrfs_block_group_cache *cache;
	struct list_head *l;

	printk(KERN_INFO "space_info has %Lu free, is %sfull\n",
2397 2398
	       info->total_bytes - info->bytes_used - info->bytes_pinned -
	       info->bytes_reserved, (info->full) ? "" : "not ");
J
Josef Bacik 已提交
2399 2400 2401 2402 2403 2404

	spin_lock(&info->lock);
	list_for_each(l, &info->block_groups) {
		cache = list_entry(l, struct btrfs_block_group_cache, list);
		spin_lock(&cache->lock);
		printk(KERN_INFO "block group %Lu has %Lu bytes, %Lu used "
2405
		       "%Lu pinned %Lu reserved\n",
J
Josef Bacik 已提交
2406
		       cache->key.objectid, cache->key.offset,
2407 2408
		       btrfs_block_group_used(&cache->item),
		       cache->pinned, cache->reserved);
J
Josef Bacik 已提交
2409 2410 2411 2412 2413
		btrfs_dump_free_space(cache, bytes);
		spin_unlock(&cache->lock);
	}
	spin_unlock(&info->lock);
}
2414

2415 2416 2417 2418 2419 2420
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)
2421 2422
{
	int ret;
2423
	u64 search_start = 0;
2424
	u64 alloc_profile;
2425
	struct btrfs_fs_info *info = root->fs_info;
J
Josef Bacik 已提交
2426
	struct btrfs_block_group_cache *cache;
2427

2428
	if (data) {
2429 2430 2431
		alloc_profile = info->avail_data_alloc_bits &
			        info->data_alloc_profile;
		data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2432
	} else if (root == root->fs_info->chunk_root) {
2433 2434 2435
		alloc_profile = info->avail_system_alloc_bits &
			        info->system_alloc_profile;
		data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2436
	} else {
2437 2438 2439
		alloc_profile = info->avail_metadata_alloc_bits &
			        info->metadata_alloc_profile;
		data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2440
	}
2441
again:
2442
	data = reduce_alloc_profile(root, data);
C
Chris Mason 已提交
2443 2444 2445 2446 2447
	/*
	 * the only place that sets empty_size is btrfs_realloc_node, which
	 * is not called recursively on allocations
	 */
	if (empty_size || root->ref_cows) {
2448
		if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2449
			ret = do_chunk_alloc(trans, root->fs_info->extent_root,
C
Chris Mason 已提交
2450 2451 2452 2453
				     2 * 1024 * 1024,
				     BTRFS_BLOCK_GROUP_METADATA |
				     (info->metadata_alloc_profile &
				      info->avail_metadata_alloc_bits), 0);
2454 2455
		}
		ret = do_chunk_alloc(trans, root->fs_info->extent_root,
C
Chris Mason 已提交
2456
				     num_bytes + 2 * 1024 * 1024, data, 0);
2457
	}
2458

2459 2460 2461
	WARN_ON(num_bytes < root->sectorsize);
	ret = find_free_extent(trans, root, num_bytes, empty_size,
			       search_start, search_end, hint_byte, ins,
2462 2463
			       trans->alloc_exclude_start,
			       trans->alloc_exclude_nr, data);
2464

2465 2466
	if (ret == -ENOSPC && num_bytes > min_alloc_size) {
		num_bytes = num_bytes >> 1;
J
Josef Bacik 已提交
2467
		num_bytes = num_bytes & ~(root->sectorsize - 1);
2468
		num_bytes = max(num_bytes, min_alloc_size);
C
Chris Mason 已提交
2469 2470
		do_chunk_alloc(trans, root->fs_info->extent_root,
			       num_bytes, data, 1);
2471 2472
		goto again;
	}
2473
	if (ret) {
J
Josef Bacik 已提交
2474 2475 2476 2477 2478 2479
		struct btrfs_space_info *sinfo;

		sinfo = __find_space_info(root->fs_info, data);
		printk("allocation failed flags %Lu, wanted %Lu\n",
		       data, num_bytes);
		dump_space_info(sinfo, num_bytes);
2480 2481
		BUG();
	}
J
Josef Bacik 已提交
2482 2483 2484 2485 2486 2487 2488 2489 2490
	cache = btrfs_lookup_block_group(root->fs_info, ins->objectid);
	if (!cache) {
		printk(KERN_ERR "Unable to find block group for %Lu\n", ins->objectid);
		return -ENOSPC;
	}

	ret = btrfs_remove_free_space(cache, ins->objectid, ins->offset);

	return ret;
2491 2492
}

2493 2494
int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
{
J
Josef Bacik 已提交
2495 2496
	struct btrfs_block_group_cache *cache;

2497
	maybe_lock_mutex(root);
J
Josef Bacik 已提交
2498 2499 2500 2501 2502 2503 2504
	cache = btrfs_lookup_block_group(root->fs_info, start);
	if (!cache) {
		printk(KERN_ERR "Unable to find block group for %Lu\n", start);
		maybe_unlock_mutex(root);
		return -ENOSPC;
	}
	btrfs_add_free_space(cache, start, len);
Z
Zheng Yan 已提交
2505
	update_reserved_extents(root, start, len, 0);
2506 2507 2508 2509
	maybe_unlock_mutex(root);
	return 0;
}

2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521
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;
	maybe_lock_mutex(root);
	ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
				     empty_size, hint_byte, search_end, ins,
				     data);
2522
	update_reserved_extents(root, ins->objectid, ins->offset, 1);
2523 2524 2525 2526 2527
	maybe_unlock_mutex(root);
	return ret;
}

static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
2528
					 struct btrfs_root *root, u64 parent,
2529
					 u64 root_objectid, u64 ref_generation,
2530
					 u64 owner, struct btrfs_key *ins)
2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543
{
	int ret;
	int pending_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];
2544

Z
Zheng Yan 已提交
2545 2546 2547
	if (parent == 0)
		parent = ins->objectid;

2548
	/* block accounting for super block */
2549
	spin_lock_irq(&info->delalloc_lock);
2550 2551
	super_used = btrfs_super_bytes_used(&info->super_copy);
	btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
2552
	spin_unlock_irq(&info->delalloc_lock);
2553

2554
	/* block accounting for root item */
2555 2556
	root_used = btrfs_root_used(&root->root_item);
	btrfs_set_root_used(&root->root_item, root_used + num_bytes);
2557

2558
	if (root == extent_root) {
Z
Zheng Yan 已提交
2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572
		struct pending_extent_op *extent_op;

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

		extent_op->type = PENDING_EXTENT_INSERT;
		extent_op->bytenr = ins->objectid;
		extent_op->num_bytes = ins->offset;
		extent_op->parent = parent;
		extent_op->orig_parent = 0;
		extent_op->generation = ref_generation;
		extent_op->orig_generation = 0;
		extent_op->level = (int)owner;

2573 2574 2575
		set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
				ins->objectid + ins->offset - 1,
				EXTENT_LOCKED, GFP_NOFS);
Z
Zheng Yan 已提交
2576 2577
		set_state_private(&root->fs_info->extent_ins,
				  ins->objectid, (unsigned long)extent_op);
2578 2579 2580
		goto update_block;
	}

2581 2582 2583
	memcpy(&keys[0], ins, sizeof(*ins));
	keys[1].objectid = ins->objectid;
	keys[1].type = BTRFS_EXTENT_REF_KEY;
Z
Zheng Yan 已提交
2584
	keys[1].offset = parent;
2585 2586
	sizes[0] = sizeof(*extent_item);
	sizes[1] = sizeof(*ref);
2587 2588 2589

	path = btrfs_alloc_path();
	BUG_ON(!path);
2590 2591 2592

	ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
				       sizes, 2);
C
Chris Mason 已提交
2593
	BUG_ON(ret);
J
Josef Bacik 已提交
2594

2595 2596 2597 2598 2599 2600 2601 2602 2603
	extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
				     struct btrfs_extent_item);
	btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
	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);
Z
Zheng Yan 已提交
2604
	btrfs_set_ref_num_refs(path->nodes[0], ref, 1);
2605 2606 2607 2608 2609

	btrfs_mark_buffer_dirty(path->nodes[0]);

	trans->alloc_exclude_start = 0;
	trans->alloc_exclude_nr = 0;
2610
	btrfs_free_path(path);
2611
	finish_current_insert(trans, extent_root);
C
Chris Mason 已提交
2612
	pending_ret = del_pending_extents(trans, extent_root);
2613

2614 2615
	if (ret)
		goto out;
2616
	if (pending_ret) {
2617 2618
		ret = pending_ret;
		goto out;
2619
	}
2620 2621

update_block:
2622
	ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
2623 2624 2625 2626 2627
	if (ret) {
		printk("update block group failed for %Lu %Lu\n",
		       ins->objectid, ins->offset);
		BUG();
	}
2628
out:
2629 2630 2631 2632
	return ret;
}

int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
Z
Zheng Yan 已提交
2633
				struct btrfs_root *root, u64 parent,
2634
				u64 root_objectid, u64 ref_generation,
2635
				u64 owner, struct btrfs_key *ins)
2636 2637
{
	int ret;
2638 2639 2640

	if (root_objectid == BTRFS_TREE_LOG_OBJECTID)
		return 0;
2641
	maybe_lock_mutex(root);
2642 2643
	ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
					    ref_generation, owner, ins);
2644
	update_reserved_extents(root, ins->objectid, ins->offset, 0);
2645 2646 2647
	maybe_unlock_mutex(root);
	return ret;
}
2648 2649 2650 2651 2652 2653 2654

/*
 * 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 已提交
2655
				struct btrfs_root *root, u64 parent,
2656
				u64 root_objectid, u64 ref_generation,
2657
				u64 owner, struct btrfs_key *ins)
2658 2659 2660 2661 2662 2663 2664 2665
{
	int ret;
	struct btrfs_block_group_cache *block_group;

	maybe_lock_mutex(root);
	block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
	cache_block_group(root, block_group);

J
Josef Bacik 已提交
2666 2667
	ret = btrfs_remove_free_space(block_group, ins->objectid, ins->offset);
	BUG_ON(ret);
2668 2669
	ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
					    ref_generation, owner, ins);
2670 2671 2672 2673
	maybe_unlock_mutex(root);
	return ret;
}

2674 2675 2676 2677 2678 2679 2680 2681 2682
/*
 * 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 已提交
2683
		       u64 num_bytes, u64 parent, u64 min_alloc_size,
2684
		       u64 root_objectid, u64 ref_generation,
2685
		       u64 owner_objectid, u64 empty_size, u64 hint_byte,
2686 2687 2688 2689 2690 2691 2692 2693 2694 2695
		       u64 search_end, struct btrfs_key *ins, u64 data)
{
	int ret;

	maybe_lock_mutex(root);

	ret = __btrfs_reserve_extent(trans, root, num_bytes,
				     min_alloc_size, empty_size, hint_byte,
				     search_end, ins, data);
	BUG_ON(ret);
2696
	if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
Z
Zheng Yan 已提交
2697 2698
		ret = __btrfs_alloc_reserved_extent(trans, root, parent,
					root_objectid, ref_generation,
2699
					owner_objectid, ins);
2700
		BUG_ON(ret);
2701

2702 2703
	} else {
		update_reserved_extents(root, ins->objectid, ins->offset, 1);
2704
	}
2705 2706
	maybe_unlock_mutex(root);
	return ret;
2707
}
2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721

struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
					    struct btrfs_root *root,
					    u64 bytenr, u32 blocksize)
{
	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);
	btrfs_tree_lock(buf);
	clean_tree_block(trans, root, buf);
	btrfs_set_buffer_uptodate(buf);
2722 2723 2724 2725 2726
	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,
2727
			 buf->start + buf->len - 1, GFP_NOFS);
2728
	}
2729 2730 2731 2732
	trans->blocks_used++;
	return buf;
}

2733 2734 2735 2736
/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
2737
struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2738
					     struct btrfs_root *root,
Z
Zheng Yan 已提交
2739
					     u32 blocksize, u64 parent,
2740 2741 2742 2743
					     u64 root_objectid,
					     u64 ref_generation,
					     int level,
					     u64 hint,
2744
					     u64 empty_size)
2745
{
C
Chris Mason 已提交
2746
	struct btrfs_key ins;
2747
	int ret;
2748
	struct extent_buffer *buf;
2749

Z
Zheng Yan 已提交
2750
	ret = btrfs_alloc_extent(trans, root, blocksize, parent, blocksize,
2751
				 root_objectid, ref_generation, level,
Z
Zheng Yan 已提交
2752
				 empty_size, hint, (u64)-1, &ins, 0);
2753
	if (ret) {
2754 2755
		BUG_ON(ret > 0);
		return ERR_PTR(ret);
2756
	}
2757

2758
	buf = btrfs_init_new_buffer(trans, root, ins.objectid, blocksize);
2759 2760
	return buf;
}
2761

2762 2763
int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
			struct btrfs_root *root, struct extent_buffer *leaf)
2764
{
2765 2766
	u64 leaf_owner;
	u64 leaf_generation;
2767
	struct btrfs_key key;
2768 2769 2770 2771 2772
	struct btrfs_file_extent_item *fi;
	int i;
	int nritems;
	int ret;

2773 2774
	BUG_ON(!btrfs_is_leaf(leaf));
	nritems = btrfs_header_nritems(leaf);
2775 2776 2777
	leaf_owner = btrfs_header_owner(leaf);
	leaf_generation = btrfs_header_generation(leaf);

2778
	for (i = 0; i < nritems; i++) {
2779
		u64 disk_bytenr;
2780
		cond_resched();
2781 2782 2783

		btrfs_item_key_to_cpu(leaf, &key, i);
		if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2784 2785
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2786 2787
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
2788
			continue;
2789 2790 2791 2792
		/*
		 * FIXME make sure to insert a trans record that
		 * repeats the snapshot del on crash
		 */
2793 2794
		disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
		if (disk_bytenr == 0)
C
Chris Mason 已提交
2795
			continue;
C
Chris Mason 已提交
2796 2797

		mutex_lock(&root->fs_info->alloc_mutex);
2798
		ret = __btrfs_free_extent(trans, root, disk_bytenr,
2799
				btrfs_file_extent_disk_num_bytes(leaf, fi),
Z
Zheng Yan 已提交
2800
				leaf->start, leaf_owner, leaf_generation,
2801
				key.objectid, 0);
C
Chris Mason 已提交
2802
		mutex_unlock(&root->fs_info->alloc_mutex);
Z
Zheng Yan 已提交
2803
		BUG_ON(ret);
C
Chris Mason 已提交
2804 2805 2806 2807

		atomic_inc(&root->fs_info->throttle_gen);
		wake_up(&root->fs_info->transaction_throttle);
		cond_resched();
2808 2809 2810 2811
	}
	return 0;
}

2812 2813 2814
static int noinline cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
					struct btrfs_root *root,
					struct btrfs_leaf_ref *ref)
Y
Yan Zheng 已提交
2815 2816 2817 2818 2819 2820 2821
{
	int i;
	int ret;
	struct btrfs_extent_info *info = ref->extents;

	for (i = 0; i < ref->nritems; i++) {
		mutex_lock(&root->fs_info->alloc_mutex);
Z
Zheng Yan 已提交
2822 2823 2824
		ret = __btrfs_free_extent(trans, root, info->bytenr,
					  info->num_bytes, ref->bytenr,
					  ref->owner, ref->generation,
2825
					  info->objectid, 0);
Y
Yan Zheng 已提交
2826
		mutex_unlock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
2827 2828 2829 2830 2831

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

Y
Yan Zheng 已提交
2832 2833 2834 2835 2836 2837 2838
		BUG_ON(ret);
		info++;
	}

	return 0;
}

2839 2840 2841
int drop_snap_lookup_refcount(struct btrfs_root *root, u64 start, u64 len,
			      u32 *refs)
{
C
Chris Mason 已提交
2842
	int ret;
2843

Z
Zheng Yan 已提交
2844
	ret = btrfs_lookup_extent_ref(NULL, root, start, len, refs);
2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874
	BUG_ON(ret);

#if 0 // some debugging code in case we see problems here
	/* 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) {
			printk("block %llu went down to one during drop_snap\n",
			       (unsigned long long)start);
		}

	}
#endif

2875
	cond_resched();
C
Chris Mason 已提交
2876
	return ret;
2877 2878
}

C
Chris Mason 已提交
2879 2880 2881 2882
/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
2883 2884 2885
static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct btrfs_path *path, int *level)
C
Chris Mason 已提交
2886
{
2887 2888 2889
	u64 root_owner;
	u64 root_gen;
	u64 bytenr;
2890
	u64 ptr_gen;
2891 2892
	struct extent_buffer *next;
	struct extent_buffer *cur;
2893
	struct extent_buffer *parent;
Y
Yan Zheng 已提交
2894
	struct btrfs_leaf_ref *ref;
2895
	u32 blocksize;
C
Chris Mason 已提交
2896 2897 2898
	int ret;
	u32 refs;

2899 2900
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
2901
	ret = drop_snap_lookup_refcount(root, path->nodes[*level]->start,
2902
				path->nodes[*level]->len, &refs);
C
Chris Mason 已提交
2903 2904 2905
	BUG_ON(ret);
	if (refs > 1)
		goto out;
2906

C
Chris Mason 已提交
2907 2908 2909
	/*
	 * walk down to the last node level and free all the leaves
	 */
2910
	while(*level >= 0) {
2911 2912
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
2913
		cur = path->nodes[*level];
2914

2915
		if (btrfs_header_level(cur) != *level)
C
Chris Mason 已提交
2916
			WARN_ON(1);
2917

2918
		if (path->slots[*level] >=
2919
		    btrfs_header_nritems(cur))
C
Chris Mason 已提交
2920
			break;
2921
		if (*level == 0) {
2922
			ret = btrfs_drop_leaf_ref(trans, root, cur);
2923 2924 2925
			BUG_ON(ret);
			break;
		}
2926
		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2927
		ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2928
		blocksize = btrfs_level_size(root, *level - 1);
2929

2930
		ret = drop_snap_lookup_refcount(root, bytenr, blocksize, &refs);
2931 2932
		BUG_ON(ret);
		if (refs != 1) {
2933 2934 2935
			parent = path->nodes[*level];
			root_owner = btrfs_header_owner(parent);
			root_gen = btrfs_header_generation(parent);
C
Chris Mason 已提交
2936
			path->slots[*level]++;
2937 2938

			mutex_lock(&root->fs_info->alloc_mutex);
2939
			ret = __btrfs_free_extent(trans, root, bytenr,
Z
Zheng Yan 已提交
2940
						blocksize, parent->start,
2941 2942
						root_owner, root_gen,
						*level - 1, 1);
C
Chris Mason 已提交
2943
			BUG_ON(ret);
2944
			mutex_unlock(&root->fs_info->alloc_mutex);
2945 2946 2947

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

C
Chris Mason 已提交
2950 2951
			continue;
		}
2952 2953 2954 2955 2956 2957
		/*
		 * at this point, we have a single ref, and since the
		 * only place referencing this extent is a dead root
		 * the reference count should never go higher.
		 * So, we don't need to check it again
		 */
Y
Yan Zheng 已提交
2958
		if (*level == 1) {
C
Chris Mason 已提交
2959
			ref = btrfs_lookup_leaf_ref(root, bytenr);
Z
Zheng Yan 已提交
2960 2961 2962 2963
			if (ref && ref->generation != ptr_gen) {
				btrfs_free_leaf_ref(root, ref);
				ref = NULL;
			}
Y
Yan Zheng 已提交
2964
			if (ref) {
2965
				ret = cache_drop_leaf_ref(trans, root, ref);
Y
Yan Zheng 已提交
2966 2967
				BUG_ON(ret);
				btrfs_remove_leaf_ref(root, ref);
2968
				btrfs_free_leaf_ref(root, ref);
Y
Yan Zheng 已提交
2969 2970 2971
				*level = 0;
				break;
			}
2972
			if (printk_ratelimit()) {
C
Chris Mason 已提交
2973 2974
				printk("leaf ref miss for bytenr %llu\n",
				       (unsigned long long)bytenr);
2975
			}
Y
Yan Zheng 已提交
2976
		}
2977
		next = btrfs_find_tree_block(root, bytenr, blocksize);
2978
		if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
2979
			free_extent_buffer(next);
2980

2981 2982
			next = read_tree_block(root, bytenr, blocksize,
					       ptr_gen);
2983
			cond_resched();
2984 2985 2986 2987 2988 2989
#if 0
			/*
			 * this is a debugging check and can go away
			 * the ref should never go all the way down to 1
			 * at this point
			 */
2990 2991
			ret = lookup_extent_ref(NULL, root, bytenr, blocksize,
						&refs);
2992
			BUG_ON(ret);
2993 2994
			WARN_ON(refs != 1);
#endif
2995
		}
2996
		WARN_ON(*level <= 0);
C
Chris Mason 已提交
2997
		if (path->nodes[*level-1])
2998
			free_extent_buffer(path->nodes[*level-1]);
C
Chris Mason 已提交
2999
		path->nodes[*level-1] = next;
3000
		*level = btrfs_header_level(next);
C
Chris Mason 已提交
3001
		path->slots[*level] = 0;
C
Chris Mason 已提交
3002
		cond_resched();
C
Chris Mason 已提交
3003 3004
	}
out:
3005 3006
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
3007 3008 3009

	if (path->nodes[*level] == root->node) {
		parent = path->nodes[*level];
Y
Yan Zheng 已提交
3010
		bytenr = path->nodes[*level]->start;
3011 3012
	} else {
		parent = path->nodes[*level + 1];
Y
Yan Zheng 已提交
3013
		bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
3014 3015
	}

Y
Yan Zheng 已提交
3016 3017
	blocksize = btrfs_level_size(root, *level);
	root_owner = btrfs_header_owner(parent);
3018
	root_gen = btrfs_header_generation(parent);
Y
Yan Zheng 已提交
3019

3020
	mutex_lock(&root->fs_info->alloc_mutex);
Y
Yan Zheng 已提交
3021
	ret = __btrfs_free_extent(trans, root, bytenr, blocksize,
Z
Zheng Yan 已提交
3022
				  parent->start, root_owner, root_gen,
3023
				  *level, 1);
Z
Zheng Yan 已提交
3024
	mutex_unlock(&root->fs_info->alloc_mutex);
3025
	free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
3026 3027 3028
	path->nodes[*level] = NULL;
	*level += 1;
	BUG_ON(ret);
3029

3030
	cond_resched();
C
Chris Mason 已提交
3031 3032 3033
	return 0;
}

C
Chris Mason 已提交
3034 3035 3036 3037 3038
/*
 * 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
 */
3039 3040 3041
static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
				 struct btrfs_root *root,
				 struct btrfs_path *path, int *level)
C
Chris Mason 已提交
3042
{
3043 3044 3045
	u64 root_owner;
	u64 root_gen;
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
3046 3047 3048
	int i;
	int slot;
	int ret;
3049

C
Chris Mason 已提交
3050
	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
C
Chris Mason 已提交
3051
		slot = path->slots[i];
3052 3053 3054 3055
		if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
			struct extent_buffer *node;
			struct btrfs_disk_key disk_key;
			node = path->nodes[i];
C
Chris Mason 已提交
3056 3057
			path->slots[i]++;
			*level = i;
3058
			WARN_ON(*level == 0);
3059
			btrfs_node_key(node, &disk_key, path->slots[i]);
3060
			memcpy(&root_item->drop_progress,
3061
			       &disk_key, sizeof(disk_key));
3062
			root_item->drop_level = i;
C
Chris Mason 已提交
3063 3064
			return 0;
		} else {
Z
Zheng Yan 已提交
3065 3066 3067 3068 3069 3070 3071 3072
			struct extent_buffer *parent;
			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);
3073
			ret = btrfs_free_extent(trans, root,
3074
						path->nodes[*level]->start,
3075
						path->nodes[*level]->len,
3076 3077
						parent->start, root_owner,
						root_gen, *level, 1);
3078
			BUG_ON(ret);
3079
			free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
3080
			path->nodes[*level] = NULL;
C
Chris Mason 已提交
3081 3082 3083 3084 3085 3086
			*level = i + 1;
		}
	}
	return 1;
}

C
Chris Mason 已提交
3087 3088 3089 3090 3091
/*
 * 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.
 */
3092
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
3093
			*root)
C
Chris Mason 已提交
3094
{
3095
	int ret = 0;
C
Chris Mason 已提交
3096
	int wret;
C
Chris Mason 已提交
3097
	int level;
3098
	struct btrfs_path *path;
C
Chris Mason 已提交
3099 3100
	int i;
	int orig_level;
3101
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
3102

3103
	WARN_ON(!mutex_is_locked(&root->fs_info->drop_mutex));
3104 3105
	path = btrfs_alloc_path();
	BUG_ON(!path);
C
Chris Mason 已提交
3106

3107
	level = btrfs_header_level(root->node);
C
Chris Mason 已提交
3108
	orig_level = level;
3109 3110
	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
		path->nodes[level] = root->node;
3111
		extent_buffer_get(root->node);
3112 3113 3114
		path->slots[level] = 0;
	} else {
		struct btrfs_key key;
3115 3116
		struct btrfs_disk_key found_key;
		struct extent_buffer *node;
3117

3118
		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
3119 3120
		level = root_item->drop_level;
		path->lowest_level = level;
3121
		wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3122
		if (wret < 0) {
3123 3124 3125
			ret = wret;
			goto out;
		}
3126 3127 3128 3129
		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)));
3130 3131 3132 3133
		/*
		 * unlock our path, this is safe because only this
		 * function is allowed to delete this snapshot
		 */
3134 3135 3136 3137 3138 3139
		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]);
			}
		}
3140
	}
C
Chris Mason 已提交
3141
	while(1) {
3142
		wret = walk_down_tree(trans, root, path, &level);
C
Chris Mason 已提交
3143
		if (wret > 0)
C
Chris Mason 已提交
3144
			break;
C
Chris Mason 已提交
3145 3146 3147
		if (wret < 0)
			ret = wret;

3148
		wret = walk_up_tree(trans, root, path, &level);
C
Chris Mason 已提交
3149
		if (wret > 0)
C
Chris Mason 已提交
3150
			break;
C
Chris Mason 已提交
3151 3152
		if (wret < 0)
			ret = wret;
3153 3154 3155 3156
		if (trans->transaction->in_commit) {
			ret = -EAGAIN;
			break;
		}
3157
		atomic_inc(&root->fs_info->throttle_gen);
C
Chris Mason 已提交
3158
		wake_up(&root->fs_info->transaction_throttle);
C
Chris Mason 已提交
3159
	}
C
Chris Mason 已提交
3160
	for (i = 0; i <= orig_level; i++) {
3161
		if (path->nodes[i]) {
3162
			free_extent_buffer(path->nodes[i]);
3163
			path->nodes[i] = NULL;
C
Chris Mason 已提交
3164
		}
C
Chris Mason 已提交
3165
	}
3166
out:
3167
	btrfs_free_path(path);
C
Chris Mason 已提交
3168
	return ret;
C
Chris Mason 已提交
3169
}
C
Chris Mason 已提交
3170

3171 3172 3173 3174 3175 3176
static unsigned long calc_ra(unsigned long start, unsigned long last,
			     unsigned long nr)
{
	return min(last, start + nr - 1);
}

3177 3178
static int noinline relocate_inode_pages(struct inode *inode, u64 start,
					 u64 len)
3179 3180 3181
{
	u64 page_start;
	u64 page_end;
Z
Zheng Yan 已提交
3182
	unsigned long first_index;
3183 3184 3185
	unsigned long last_index;
	unsigned long i;
	struct page *page;
3186
	struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
3187
	struct file_ra_state *ra;
3188
	struct btrfs_ordered_extent *ordered;
Z
Zheng Yan 已提交
3189 3190 3191
	unsigned int total_read = 0;
	unsigned int total_dirty = 0;
	int ret = 0;
3192 3193

	ra = kzalloc(sizeof(*ra), GFP_NOFS);
3194 3195

	mutex_lock(&inode->i_mutex);
Z
Zheng Yan 已提交
3196
	first_index = start >> PAGE_CACHE_SHIFT;
3197 3198
	last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;

Z
Zheng Yan 已提交
3199 3200 3201 3202 3203
	/* 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;
3204

3205
	file_ra_state_init(ra, inode->i_mapping);
3206

Z
Zheng Yan 已提交
3207 3208
	for (i = first_index ; i <= last_index; i++) {
		if (total_read % ra->ra_pages == 0) {
3209
			btrfs_force_ra(inode->i_mapping, ra, NULL, i,
Z
Zheng Yan 已提交
3210
				       calc_ra(i, last_index, ra->ra_pages));
3211 3212
		}
		total_read++;
3213 3214
again:
		if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
Z
Zheng Yan 已提交
3215
			BUG_ON(1);
3216
		page = grab_cache_page(inode->i_mapping, i);
3217
		if (!page) {
Z
Zheng Yan 已提交
3218
			ret = -ENOMEM;
3219
			goto out_unlock;
3220
		}
3221 3222 3223 3224 3225 3226
		if (!PageUptodate(page)) {
			btrfs_readpage(NULL, page);
			lock_page(page);
			if (!PageUptodate(page)) {
				unlock_page(page);
				page_cache_release(page);
Z
Zheng Yan 已提交
3227
				ret = -EIO;
3228 3229 3230
				goto out_unlock;
			}
		}
3231
		wait_on_page_writeback(page);
3232

3233 3234
		page_start = (u64)page->index << PAGE_CACHE_SHIFT;
		page_end = page_start + PAGE_CACHE_SIZE - 1;
3235
		lock_extent(io_tree, page_start, page_end, GFP_NOFS);
3236

3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247
		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);

3248
		btrfs_set_extent_delalloc(inode, page_start, page_end);
Z
Zheng Yan 已提交
3249 3250 3251 3252
		if (i == first_index)
			set_extent_bits(io_tree, page_start, page_end,
					EXTENT_BOUNDARY, GFP_NOFS);

3253
		set_page_dirty(page);
Z
Zheng Yan 已提交
3254
		total_dirty++;
3255

3256
		unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
3257 3258 3259 3260 3261
		unlock_page(page);
		page_cache_release(page);
	}

out_unlock:
3262
	kfree(ra);
3263
	mutex_unlock(&inode->i_mutex);
Z
Zheng Yan 已提交
3264 3265
	balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
	return ret;
3266 3267
}

Z
Zheng Yan 已提交
3268 3269 3270 3271 3272 3273 3274
static int noinline relocate_data_extent(struct inode *reloc_inode,
					 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;
3275

Z
Zheng Yan 已提交
3276 3277
	em = alloc_extent_map(GFP_NOFS);
	BUG_ON(!em || IS_ERR(em));
3278

Z
Zheng Yan 已提交
3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293
	em->start = extent_key->objectid - offset;
	em->len = extent_key->offset;
	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 */
	mutex_lock(&BTRFS_I(reloc_inode)->extent_mutex);
	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);
3294 3295
			break;
		}
Z
Zheng Yan 已提交
3296 3297
		btrfs_drop_extent_cache(reloc_inode, em->start,
					em->start + em->len - 1, 0);
3298
	}
Z
Zheng Yan 已提交
3299
	mutex_unlock(&BTRFS_I(reloc_inode)->extent_mutex);
3300

Z
Zheng Yan 已提交
3301 3302 3303
	return relocate_inode_pages(reloc_inode, extent_key->objectid - offset,
				    extent_key->offset);
}
3304

Z
Zheng Yan 已提交
3305 3306 3307 3308 3309 3310 3311 3312 3313 3314
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;
};
3315

Z
Zheng Yan 已提交
3316 3317 3318 3319 3320 3321
struct disk_extent {
	u64 disk_bytenr;
	u64 disk_num_bytes;
	u64 offset;
	u64 num_bytes;
};
3322

Z
Zheng Yan 已提交
3323 3324 3325 3326 3327 3328 3329 3330 3331 3332
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 ||
	    root_objectid == BTRFS_TREE_LOG_OBJECTID)
		return 1;
	return 0;
}
3333

Z
Zheng Yan 已提交
3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347
static int noinline __next_ref_path(struct btrfs_trans_handle *trans,
				    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;
3348

Z
Zheng Yan 已提交
3349 3350 3351
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
3352

Z
Zheng Yan 已提交
3353
	mutex_lock(&extent_root->fs_info->alloc_mutex);
C
Chris Mason 已提交
3354

Z
Zheng Yan 已提交
3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365
	if (first_time) {
		ref_path->lowest_level = -1;
		ref_path->current_level = -1;
		goto walk_up;
	}
walk_down:
	level = ref_path->current_level - 1;
	while (level >= -1) {
		u64 parent;
		if (level < ref_path->lowest_level)
			break;
3366

Z
Zheng Yan 已提交
3367 3368 3369 3370 3371 3372
		if (level >= 0) {
			bytenr = ref_path->nodes[level];
		} else {
			bytenr = ref_path->extent_start;
		}
		BUG_ON(bytenr == 0);
3373

Z
Zheng Yan 已提交
3374 3375 3376 3377
		parent = ref_path->nodes[level + 1];
		ref_path->nodes[level + 1] = 0;
		ref_path->current_level = level;
		BUG_ON(parent == 0);
C
Chris Mason 已提交
3378

Z
Zheng Yan 已提交
3379 3380 3381
		key.objectid = bytenr;
		key.offset = parent + 1;
		key.type = BTRFS_EXTENT_REF_KEY;
3382

Z
Zheng Yan 已提交
3383 3384
		ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
		if (ret < 0)
3385
			goto out;
Z
Zheng Yan 已提交
3386
		BUG_ON(ret == 0);
3387

Z
Zheng Yan 已提交
3388 3389 3390 3391 3392 3393 3394 3395 3396 3397
		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 已提交
3398

Z
Zheng Yan 已提交
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
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.objectid == bytenr &&
				found_key.type == BTRFS_EXTENT_REF_KEY)
			goto found;
next:
		level--;
		btrfs_release_path(extent_root, path);
		if (need_resched()) {
			mutex_unlock(&extent_root->fs_info->alloc_mutex);
			cond_resched();
			mutex_lock(&extent_root->fs_info->alloc_mutex);
		}
	}
	/* reached lowest level */
	ret = 1;
	goto out;
walk_up:
	level = ref_path->current_level;
	while (level < BTRFS_MAX_LEVEL - 1) {
		u64 ref_objectid;
		if (level >= 0) {
			bytenr = ref_path->nodes[level];
		} else {
			bytenr = ref_path->extent_start;
		}
		BUG_ON(bytenr == 0);
3425

Z
Zheng Yan 已提交
3426 3427 3428
		key.objectid = bytenr;
		key.offset = 0;
		key.type = BTRFS_EXTENT_REF_KEY;
3429

Z
Zheng Yan 已提交
3430 3431 3432
		ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
		if (ret < 0)
			goto out;
3433

Z
Zheng Yan 已提交
3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448
		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];
		}
3449

Z
Zheng Yan 已提交
3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478
		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;
3479

Z
Zheng Yan 已提交
3480 3481 3482 3483
		if (ref_path->lowest_level == level) {
			ref_path->owner_objectid = ref_objectid;
			ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
		}
3484

3485
		/*
Z
Zheng Yan 已提交
3486 3487
		 * the block is tree root or the block isn't in reference
		 * counted tree.
3488
		 */
Z
Zheng Yan 已提交
3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501
		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;
		}
3502

Z
Zheng Yan 已提交
3503 3504 3505 3506
		level++;
		BUG_ON(ref_path->nodes[level] != 0);
		ref_path->nodes[level] = found_key.offset;
		ref_path->current_level = level;
3507

Z
Zheng Yan 已提交
3508 3509 3510 3511 3512 3513 3514 3515 3516 3517
		/*
		 * 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;
3518 3519
		}

Z
Zheng Yan 已提交
3520 3521
		btrfs_release_path(extent_root, path);
		if (need_resched()) {
3522
			mutex_unlock(&extent_root->fs_info->alloc_mutex);
Z
Zheng Yan 已提交
3523 3524 3525
			cond_resched();
			mutex_lock(&extent_root->fs_info->alloc_mutex);
		}
3526
	}
Z
Zheng Yan 已提交
3527 3528
	/* reached max tree level, but no tree root found. */
	BUG();
3529
out:
Z
Zheng Yan 已提交
3530 3531 3532
	mutex_unlock(&extent_root->fs_info->alloc_mutex);
	btrfs_free_path(path);
	return ret;
3533 3534
}

Z
Zheng Yan 已提交
3535 3536 3537 3538
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)
3539
{
Z
Zheng Yan 已提交
3540 3541
	memset(ref_path, 0, sizeof(*ref_path));
	ref_path->extent_start = extent_start;
3542

Z
Zheng Yan 已提交
3543
	return __next_ref_path(trans, extent_root, ref_path, 1);
3544 3545
}

Z
Zheng Yan 已提交
3546 3547 3548
static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
			       struct btrfs_root *extent_root,
			       struct btrfs_ref_path *ref_path)
3549
{
Z
Zheng Yan 已提交
3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561
	return __next_ref_path(trans, extent_root, ref_path, 0);
}

static int noinline get_new_locations(struct inode *reloc_inode,
				      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;
3562
	struct extent_buffer *leaf;
Z
Zheng Yan 已提交
3563 3564 3565 3566
	struct disk_extent *exts = *extents;
	struct btrfs_key found_key;
	u64 cur_pos;
	u64 last_byte;
3567
	u32 nritems;
Z
Zheng Yan 已提交
3568 3569 3570
	int nr = 0;
	int max = *nr_extents;
	int ret;
3571

Z
Zheng Yan 已提交
3572 3573 3574 3575 3576 3577
	WARN_ON(!no_fragment && *extents);
	if (!exts) {
		max = 1;
		exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
		if (!exts)
			return -ENOMEM;
3578
	}
3579

Z
Zheng Yan 已提交
3580 3581
	path = btrfs_alloc_path();
	BUG_ON(!path);
3582

Z
Zheng Yan 已提交
3583 3584 3585 3586 3587 3588 3589 3590 3591 3592
	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;
	}
3593

Z
Zheng Yan 已提交
3594
	while (1) {
3595 3596
		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
Z
Zheng Yan 已提交
3597 3598
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(root, path);
3599 3600
			if (ret < 0)
				goto out;
Z
Zheng Yan 已提交
3601 3602
			if (ret > 0)
				break;
3603
			leaf = path->nodes[0];
3604
		}
3605 3606

		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
Z
Zheng Yan 已提交
3607 3608 3609
		if (found_key.offset != cur_pos ||
		    found_key.type != BTRFS_EXTENT_DATA_KEY ||
		    found_key.objectid != reloc_inode->i_ino)
3610 3611
			break;

Z
Zheng Yan 已提交
3612 3613 3614 3615 3616
		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)
3617
			break;
Z
Zheng Yan 已提交
3618 3619 3620 3621 3622 3623 3624 3625

		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);
3626
		}
3627

Z
Zheng Yan 已提交
3628 3629 3630 3631 3632 3633 3634 3635
		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);
		WARN_ON(exts[nr].offset > 0);
		WARN_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
3636

Z
Zheng Yan 已提交
3637 3638 3639 3640 3641 3642 3643 3644
		cur_pos += exts[nr].num_bytes;
		nr++;

		if (cur_pos + offset >= last_byte)
			break;

		if (no_fragment) {
			ret = 1;
3645
			goto out;
Z
Zheng Yan 已提交
3646 3647 3648 3649 3650 3651 3652 3653
		}
		path->slots[0]++;
	}

	WARN_ON(cur_pos + offset > last_byte);
	if (cur_pos + offset < last_byte) {
		ret = -ENOENT;
		goto out;
3654 3655 3656
	}
	ret = 0;
out:
Z
Zheng Yan 已提交
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
	btrfs_free_path(path);
	if (ret) {
		if (exts != *extents)
			kfree(exts);
	} else {
		*extents = exts;
		*nr_extents = nr;
	}
	return ret;
}

static int noinline replace_one_extent(struct btrfs_trans_handle *trans,
					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;
	u64 first_pos;
	u32 nritems;
3687
	int nr_scaned = 0;
Z
Zheng Yan 已提交
3688 3689 3690
	int extent_locked = 0;
	int ret;

3691 3692
	memcpy(&key, leaf_key, sizeof(key));
	first_pos = INT_LIMIT(loff_t) - extent_key->offset;
Z
Zheng Yan 已提交
3693
	if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
3694 3695 3696 3697 3698 3699 3700
		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 已提交
3701 3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722
	}

	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.
			 */
			mutex_unlock(&BTRFS_I(inode)->extent_mutex);
			unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
				      lock_end, GFP_NOFS);
			extent_locked = 0;
		}

		if (path->slots[0] >= nritems) {
3723
			if (++nr_scaned > 2)
Z
Zheng Yan 已提交
3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 3742 3743 3744 3745 3746 3747 3748 3749 3750 3751 3752 3753 3754 3755 3756 3757 3758 3759 3760 3761 3762 3763 3764 3765 3766 3767 3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861
				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) ||
			    (key.offset >= first_pos + extent_key->offset))
				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);
		if ((btrfs_file_extent_type(leaf, fi) !=
		     BTRFS_FILE_EXTENT_REG) ||
		    (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);

		if (first_pos > key.offset - ext_offset)
			first_pos = key.offset - ext_offset;

		if (!extent_locked) {
			lock_start = key.offset;
			lock_end = lock_start + num_bytes - 1;
		} else {
			BUG_ON(lock_start != key.offset);
			BUG_ON(lock_end - lock_start + 1 < num_bytes);
		}

		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);

			mutex_lock(&BTRFS_I(inode)->extent_mutex);
			extent_locked = 1;
			continue;
		}

		if (nr_extents == 1) {
			/* update extent pointer in place */
			btrfs_set_file_extent_generation(leaf, fi,
						trans->transid);
			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);
			ext_offset += new_extents[0].offset;
			btrfs_set_file_extent_offset(leaf, fi, ext_offset);
			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,
3862
						key.objectid);
Z
Zheng Yan 已提交
3863 3864 3865 3866 3867 3868 3869 3870
			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),
3871
						key.objectid, 0);
Z
Zheng Yan 已提交
3872 3873 3874 3875 3876 3877 3878 3879 3880 3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 3924 3925 3926 3927 3928
			BUG_ON(ret);

			btrfs_release_path(root, path);
			key.offset += num_bytes;
		} else {
			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);
				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,
3929
						trans->transid, key.objectid);
Z
Zheng Yan 已提交
3930 3931 3932
				BUG_ON(ret);
				btrfs_release_path(root, path);

3933
				inode_add_bytes(inode, extent_len);
Z
Zheng Yan 已提交
3934 3935 3936 3937 3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955 3956 3957 3958 3959 3960 3961 3962 3963 3964 3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995 3996 3997 3998 3999 4000 4001 4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184

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

				if (num_bytes == 0)
					break;
			}
			BUG_ON(i >= nr_extents);
		}

		if (extent_locked) {
			mutex_unlock(&BTRFS_I(inode)->extent_mutex);
			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 &&
		    key.offset >= first_pos + extent_key->offset)
			break;

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

int btrfs_add_reloc_mapping(struct btrfs_root *root, u64 orig_bytenr,
			    u64 num_bytes, u64 new_bytenr)
{
	set_extent_bits(&root->fs_info->reloc_mapping_tree,
			orig_bytenr, orig_bytenr + num_bytes - 1,
			EXTENT_LOCKED, GFP_NOFS);
	set_state_private(&root->fs_info->reloc_mapping_tree,
			  orig_bytenr, new_bytenr);
	return 0;
}

int btrfs_get_reloc_mapping(struct btrfs_root *root, u64 orig_bytenr,
			    u64 num_bytes, u64 *new_bytenr)
{
	u64 bytenr;
	u64 cur_bytenr = orig_bytenr;
	u64 prev_bytenr = orig_bytenr;
	int ret;

	while (1) {
		ret = get_state_private(&root->fs_info->reloc_mapping_tree,
					cur_bytenr, &bytenr);
		if (ret)
			break;
		prev_bytenr = cur_bytenr;
		cur_bytenr = bytenr;
	}

	if (orig_bytenr == cur_bytenr)
		return -ENOENT;

	if (prev_bytenr != orig_bytenr) {
		set_state_private(&root->fs_info->reloc_mapping_tree,
				  orig_bytenr, cur_bytenr);
	}
	*new_bytenr = cur_bytenr;
	return 0;
}

void btrfs_free_reloc_mappings(struct btrfs_root *root)
{
	clear_extent_bits(&root->fs_info->reloc_mapping_tree,
			  0, (u64)-1, -1, GFP_NOFS);
}

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);
		ret = btrfs_add_leaf_ref(root, ref, 0);
		WARN_ON(ret);
		btrfs_free_leaf_ref(root, ref);
	}
	return 0;
}

static int noinline invalidate_extent_cache(struct btrfs_root *root,
					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);
		mutex_lock(&BTRFS_I(inode)->extent_mutex);
		btrfs_drop_extent_cache(inode, key.offset,
					key.offset + num_bytes - 1, 1);
		mutex_unlock(&BTRFS_I(inode)->extent_mutex);
		unlock_extent(&BTRFS_I(inode)->io_tree, key.offset,
			      key.offset + num_bytes - 1, GFP_NOFS);
		cond_resched();
	}
	iput(inode);
	return 0;
}

static int noinline replace_extents_in_leaf(struct btrfs_trans_handle *trans,
					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_generation(leaf, fi, trans->transid);
		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);
		new_extent->offset += btrfs_file_extent_offset(leaf, fi);
		btrfs_set_file_extent_offset(leaf, fi, new_extent->offset);
		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,
4185
					trans->transid, key.objectid);
Z
Zheng Yan 已提交
4186 4187 4188 4189 4190
		BUG_ON(ret);
		ret = btrfs_free_extent(trans, root,
					bytenr, num_bytes, leaf->start,
					btrfs_header_owner(leaf),
					btrfs_header_generation(leaf),
4191
					key.objectid, 0);
Z
Zheng Yan 已提交
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 4217 4218 4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261 4262 4263 4264 4265 4266 4267 4268 4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 4376 4377 4378 4379 4380 4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 4417 4418 4419 4420 4421 4422 4423 4424 4425 4426 4427 4428 4429 4430 4431 4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 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 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 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 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714
		BUG_ON(ret);
		cond_resched();
	}
	kfree(new_extent);
	BUG_ON(ext_index + 1 != ref->nritems);
	btrfs_free_leaf_ref(root, ref);
	return 0;
}

int btrfs_free_reloc_root(struct btrfs_root *root)
{
	struct btrfs_root *reloc_root;

	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);
	}
	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;
}

static int noinline init_reloc_tree(struct btrfs_trans_handle *trans,
				    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));
	memset(&root_item->drop_progress, 0, sizeof(root_item->drop_progress));
	root_item->drop_level = 0;

	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
 * counted roots. There is one reloc tree for each subvol, all reloc
 * trees share same key objectid. Reloc trees are snapshots of the
 * latest committed roots (subvol root->commit_root). To relocate a tree
 * block referenced by a subvol, the code COW the block through the reloc
 * tree, then update pointer in the subvol to point to the new block.
 * Since all reloc trees share same key objectid, we can easily do special
 * handing to share tree blocks between reloc trees. Once a tree block has
 * been COWed in one reloc tree, we can use the result when the same block
 * is COWed again through other reloc trees.
 */
static int noinline relocate_one_path(struct btrfs_trans_handle *trans,
				      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;
	int lowest_merge;
	int lowest_level = 0;
	int update_refs;
	int ret;

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

	if (is_cowonly_root(ref_path->root_objectid)) {
		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;
	}

	keys = kzalloc(sizeof(*keys) * BTRFS_MAX_LEVEL, GFP_NOFS);
	BUG_ON(!keys);
	nodes = kzalloc(sizeof(*nodes) * BTRFS_MAX_LEVEL, GFP_NOFS);
	BUG_ON(!nodes);

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

	path->lowest_level = lowest_level;
	ret = btrfs_search_slot(trans, reloc_root, first_key, path, 0, 0);
	BUG_ON(ret);
	/*
	 * get relocation mapping for tree blocks in the path
	 */
	lowest_merge = BTRFS_MAX_LEVEL;
	for (level = BTRFS_MAX_LEVEL - 1; level >= lowest_level; level--) {
		u64 new_bytenr;
		eb = path->nodes[level];
		if (!eb || eb == reloc_root->node)
			continue;
		ret = btrfs_get_reloc_mapping(reloc_root, eb->start, eb->len,
					      &new_bytenr);
		if (ret)
			continue;
		if (level == 0)
			btrfs_item_key_to_cpu(eb, &keys[level], 0);
		else
			btrfs_node_key_to_cpu(eb, &keys[level], 0);
		nodes[level] = new_bytenr;
		lowest_merge = level;
	}

	update_refs = 0;
	if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
		eb = path->nodes[0];
		if (btrfs_header_generation(eb) < trans->transid)
			update_refs = 1;
	}

	btrfs_release_path(reloc_root, path);
	/*
	 * merge tree blocks that already relocated in other reloc trees
	 */
	if (lowest_merge != BTRFS_MAX_LEVEL) {
		ret = btrfs_merge_path(trans, reloc_root, keys, nodes,
				       lowest_merge);
		BUG_ON(ret < 0);
	}
	/*
	 * cow any tree blocks that still haven't been relocated
	 */
	ret = btrfs_search_slot(trans, reloc_root, first_key, path, 0, 1);
	BUG_ON(ret);
	/*
	 * if we are relocating data block group, update extent pointers
	 * in the newly created tree leaf.
	 */
	eb = path->nodes[0];
	if (update_refs && nodes[0] != eb->start) {
		ret = replace_extents_in_leaf(trans, reloc_root, eb, group,
					      reloc_inode);
		BUG_ON(ret);
	}

	memset(keys, 0, sizeof(*keys) * BTRFS_MAX_LEVEL);
	memset(nodes, 0, sizeof(*nodes) * BTRFS_MAX_LEVEL);
	for (level = BTRFS_MAX_LEVEL - 1; level >= lowest_level; level--) {
		eb = path->nodes[level];
		if (!eb || eb == reloc_root->node)
			continue;
		BUG_ON(btrfs_header_owner(eb) != BTRFS_TREE_RELOC_OBJECTID);
		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);
	}

	if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
		eb = path->nodes[0];
		extent_buffer_get(eb);
	}
	btrfs_release_path(reloc_root, path);
	/*
	 * 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) {
		ret = invalidate_extent_cache(reloc_root, eb, group, root);
		BUG_ON(ret);
		free_extent_buffer(eb);
	}
	mutex_unlock(&root->fs_info->tree_reloc_mutex);

	path->lowest_level = 0;
	kfree(nodes);
	kfree(keys);
	return 0;
}

static int noinline relocate_tree_block(struct btrfs_trans_handle *trans,
					struct btrfs_root *root,
					struct btrfs_path *path,
					struct btrfs_key *first_key,
					struct btrfs_ref_path *ref_path)
{
	int ret;
	int needs_lock = 0;

	if (root == root->fs_info->extent_root ||
	    root == root->fs_info->chunk_root ||
	    root == root->fs_info->dev_root) {
		needs_lock = 1;
		mutex_lock(&root->fs_info->alloc_mutex);
	}

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

	if (root == root->fs_info->extent_root)
		btrfs_extent_post_op(trans, root);
	if (needs_lock)
		mutex_unlock(&root->fs_info->alloc_mutex);

	return 0;
}

static int noinline del_extent_zero(struct btrfs_trans_handle *trans,
				    struct btrfs_root *extent_root,
				    struct btrfs_path *path,
				    struct btrfs_key *extent_key)
{
	int ret;

	mutex_lock(&extent_root->fs_info->alloc_mutex);
	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);
	mutex_unlock(&extent_root->fs_info->alloc_mutex);
	return ret;
}

static struct btrfs_root noinline *read_ref_root(struct btrfs_fs_info *fs_info,
						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);
}

static int noinline relocate_one_extent(struct btrfs_root *extent_root,
					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;

	mutex_unlock(&extent_root->fs_info->alloc_mutex);

	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) {
	       ret = -ENOMEM;
	       goto out;
	}

	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;
		}

		if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
		    pass >= 2) {
			/*
			 * use fallback method to process the remaining
			 * references.
			 */
			if (!new_extents) {
				u64 group_start = group->key.objectid;
				ret = get_new_locations(reloc_inode,
							extent_key,
							group_start, 0,
							&new_extents,
							&nr_extents);
				if (ret < 0)
					goto out;
			}
			btrfs_record_root_in_trans(found_root);
			ret = replace_one_extent(trans, found_root,
						path, extent_key,
						&first_key, ref_path,
						new_extents, nr_extents);
			if (ret < 0)
				goto out;
			continue;
		}

		btrfs_record_root_in_trans(found_root);
		if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
			ret = relocate_tree_block(trans, found_root, path,
						  &first_key, ref_path);
		} else {
			/*
			 * try to update data extent references while
			 * keeping metadata shared between snapshots.
			 */
			ret = relocate_one_path(trans, found_root, path,
						&first_key, ref_path,
						group, reloc_inode);
		}
		if (ret < 0)
			goto out;
	}
	ret = 0;
out:
	btrfs_end_transaction(trans, extent_root);
	kfree(new_extents);
	kfree(ref_path);
	mutex_lock(&extent_root->fs_info->alloc_mutex);
	return ret;
}

4715 4716 4717 4718 4719 4720
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;

4721
	num_devices = root->fs_info->fs_devices->num_devices;
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
	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;
}

C
Chris Mason 已提交
4753 4754 4755 4756 4757 4758 4759 4760
int __alloc_chunk_for_shrink(struct btrfs_root *root,
		     struct btrfs_block_group_cache *shrink_block_group,
		     int force)
{
	struct btrfs_trans_handle *trans;
	u64 new_alloc_flags;
	u64 calc;

4761
	spin_lock(&shrink_block_group->lock);
C
Chris Mason 已提交
4762
	if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
4763
		spin_unlock(&shrink_block_group->lock);
4764
		mutex_unlock(&root->fs_info->alloc_mutex);
4765

C
Chris Mason 已提交
4766
		trans = btrfs_start_transaction(root, 1);
4767
		mutex_lock(&root->fs_info->alloc_mutex);
4768
		spin_lock(&shrink_block_group->lock);
4769

C
Chris Mason 已提交
4770 4771 4772 4773 4774 4775 4776 4777
		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;
		}
4778 4779
		spin_unlock(&shrink_block_group->lock);

C
Chris Mason 已提交
4780 4781
		do_chunk_alloc(trans, root->fs_info->extent_root,
			       calc + 2 * 1024 * 1024, new_alloc_flags, force);
4782 4783

		mutex_unlock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
4784
		btrfs_end_transaction(trans, root);
4785
		mutex_lock(&root->fs_info->alloc_mutex);
4786 4787
	} else
		spin_unlock(&shrink_block_group->lock);
C
Chris Mason 已提交
4788 4789 4790
	return 0;
}

Z
Zheng Yan 已提交
4791 4792 4793 4794 4795 4796 4797 4798 4799 4800 4801 4802 4803 4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 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
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;

	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);
	btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NODATASUM);
	btrfs_mark_buffer_dirty(leaf);
	btrfs_release_path(root, path);
out:
	btrfs_free_path(path);
	return ret;
}

static struct inode noinline *create_reloc_inode(struct btrfs_fs_info *fs_info,
					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,
				       group->key.offset, 0);
	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);
	}

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

int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start)
4878 4879 4880
{
	struct btrfs_trans_handle *trans;
	struct btrfs_path *path;
Z
Zheng Yan 已提交
4881 4882 4883 4884 4885
	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;
4886 4887 4888 4889
	u64 cur_byte;
	u64 total_found;
	u32 nritems;
	int ret;
4890
	int progress;
Z
Zheng Yan 已提交
4891
	int pass = 0;
4892

Z
Zheng Yan 已提交
4893 4894 4895 4896
	root = root->fs_info->extent_root;

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

Z
Zheng Yan 已提交
4898 4899 4900
	printk("btrfs relocating block group %llu flags %llu\n",
	       (unsigned long long)block_group->key.objectid,
	       (unsigned long long)block_group->flags);
4901

4902
	path = btrfs_alloc_path();
Z
Zheng Yan 已提交
4903
	BUG_ON(!path);
4904

Z
Zheng Yan 已提交
4905 4906
	reloc_inode = create_reloc_inode(info, block_group);
	BUG_ON(IS_ERR(reloc_inode));
4907

Z
Zheng Yan 已提交
4908
	mutex_lock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
4909

Z
Zheng Yan 已提交
4910 4911 4912
	__alloc_chunk_for_shrink(root, block_group, 1);
	block_group->ro = 1;
	block_group->space_info->total_bytes -= block_group->key.offset;
4913

Z
Zheng Yan 已提交
4914
	mutex_unlock(&root->fs_info->alloc_mutex);
4915

Z
Zheng Yan 已提交
4916 4917 4918
	btrfs_start_delalloc_inodes(info->tree_root);
	btrfs_wait_ordered_extents(info->tree_root, 0);
again:
4919
	total_found = 0;
4920
	progress = 0;
Z
Zheng Yan 已提交
4921
	key.objectid = block_group->key.objectid;
4922 4923
	key.offset = 0;
	key.type = 0;
4924
	cur_byte = key.objectid;
4925

Z
Zheng Yan 已提交
4926 4927
	trans = btrfs_start_transaction(info->tree_root, 1);
	btrfs_commit_transaction(trans, info->tree_root);
4928

Z
Zheng Yan 已提交
4929 4930 4931 4932
	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);
4933 4934 4935

	mutex_lock(&root->fs_info->alloc_mutex);

4936
	while(1) {
4937 4938 4939
		ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
		if (ret < 0)
			goto out;
4940
next:
4941
		leaf = path->nodes[0];
4942 4943 4944 4945 4946 4947 4948 4949
		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;
4950
			}
4951 4952
			leaf = path->nodes[0];
			nritems = btrfs_header_nritems(leaf);
4953
		}
4954

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

Z
Zheng Yan 已提交
4957 4958
		if (key.objectid >= block_group->key.objectid +
		    block_group->key.offset)
4959 4960
			break;

4961 4962
		if (progress && need_resched()) {
			btrfs_release_path(root, path);
Z
Zheng Yan 已提交
4963 4964 4965
			mutex_unlock(&root->fs_info->alloc_mutex);
			cond_resched();
			mutex_lock(&root->fs_info->alloc_mutex);
4966
			progress = 0;
Z
Zheng Yan 已提交
4967
			continue;
4968 4969 4970
		}
		progress = 1;

Z
Zheng Yan 已提交
4971 4972
		if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY ||
		    key.objectid + key.offset <= cur_byte) {
4973 4974 4975
			path->slots[0]++;
			goto next;
		}
4976

4977
		total_found++;
Z
Zheng Yan 已提交
4978
		cur_byte = key.objectid + key.offset;
4979 4980
		btrfs_release_path(root, path);

Z
Zheng Yan 已提交
4981 4982 4983 4984
		__alloc_chunk_for_shrink(root, block_group, 0);
		ret = relocate_one_extent(root, path, &key, block_group,
					  reloc_inode, pass);
		BUG_ON(ret < 0);
4985

Z
Zheng Yan 已提交
4986 4987 4988
		key.objectid = cur_byte;
		key.type = 0;
		key.offset = 0;
4989 4990
	}

Z
Zheng Yan 已提交
4991
	btrfs_release_path(root, path);
4992 4993
	mutex_unlock(&root->fs_info->alloc_mutex);

Z
Zheng Yan 已提交
4994 4995 4996 4997
	if (pass == 0) {
		btrfs_wait_ordered_range(reloc_inode, 0, (u64)-1);
		invalidate_mapping_pages(reloc_inode->i_mapping, 0, -1);
		WARN_ON(reloc_inode->i_mapping->nrpages);
4998
	}
4999

Z
Zheng Yan 已提交
5000 5001 5002 5003 5004
	if (total_found > 0) {
		printk("btrfs found %llu extents in pass %d\n",
		       (unsigned long long)total_found, pass);
		pass++;
		goto again;
J
Josef Bacik 已提交
5005
	}
C
Chris Mason 已提交
5006

Z
Zheng Yan 已提交
5007 5008 5009 5010 5011 5012
	/* 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 已提交
5013

5014 5015
	mutex_lock(&root->fs_info->alloc_mutex);

Z
Zheng Yan 已提交
5016 5017 5018 5019 5020 5021
	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);
	ret = 0;
5022
out:
5023
	mutex_unlock(&root->fs_info->alloc_mutex);
Z
Zheng Yan 已提交
5024
	btrfs_free_path(path);
5025 5026 5027
	return ret;
}

5028 5029 5030
int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
			   struct btrfs_key *key)
{
5031
	int ret = 0;
5032 5033 5034
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
	int slot;
5035

5036 5037
	ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
	if (ret < 0)
5038 5039
		goto out;

5040 5041
	while(1) {
		slot = path->slots[0];
5042
		leaf = path->nodes[0];
5043 5044 5045 5046 5047
		if (slot >= btrfs_header_nritems(leaf)) {
			ret = btrfs_next_leaf(root, path);
			if (ret == 0)
				continue;
			if (ret < 0)
5048
				goto out;
5049
			break;
5050
		}
5051
		btrfs_item_key_to_cpu(leaf, &found_key, slot);
5052

5053
		if (found_key.objectid >= key->objectid &&
5054 5055 5056 5057
		    found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
			ret = 0;
			goto out;
		}
5058
		path->slots[0]++;
5059
	}
5060
	ret = -ENOENT;
5061
out:
5062
	return ret;
5063 5064
}

Z
Zheng Yan 已提交
5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091
int btrfs_free_block_groups(struct btrfs_fs_info *info)
{
	struct btrfs_block_group_cache *block_group;
	struct rb_node *n;

	mutex_lock(&info->alloc_mutex);
	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);

		spin_unlock(&info->block_group_cache_lock);
		btrfs_remove_free_space_cache(block_group);
		spin_lock(&info->block_group_cache_lock);

		rb_erase(&block_group->cache_node,
			 &info->block_group_cache_tree);
		spin_lock(&block_group->space_info->lock);
		list_del(&block_group->list);
		spin_unlock(&block_group->space_info->lock);
		kfree(block_group);
	}
	spin_unlock(&info->block_group_cache_lock);
	mutex_unlock(&info->alloc_mutex);
	return 0;
}

C
Chris Mason 已提交
5092 5093 5094 5095 5096
int btrfs_read_block_groups(struct btrfs_root *root)
{
	struct btrfs_path *path;
	int ret;
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
5097
	struct btrfs_fs_info *info = root->fs_info;
5098
	struct btrfs_space_info *space_info;
C
Chris Mason 已提交
5099 5100
	struct btrfs_key key;
	struct btrfs_key found_key;
5101
	struct extent_buffer *leaf;
5102

C
Chris Mason 已提交
5103
	root = info->extent_root;
C
Chris Mason 已提交
5104
	key.objectid = 0;
5105
	key.offset = 0;
C
Chris Mason 已提交
5106 5107 5108 5109 5110
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

5111
	mutex_lock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
5112
	while(1) {
5113 5114 5115 5116
		ret = find_first_block_group(root, path, &key);
		if (ret > 0) {
			ret = 0;
			goto error;
C
Chris Mason 已提交
5117
		}
5118 5119 5120
		if (ret != 0)
			goto error;

5121 5122
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5123
		cache = kzalloc(sizeof(*cache), GFP_NOFS);
C
Chris Mason 已提交
5124
		if (!cache) {
5125
			ret = -ENOMEM;
C
Chris Mason 已提交
5126 5127
			break;
		}
C
Chris Mason 已提交
5128

5129
		spin_lock_init(&cache->lock);
J
Josef Bacik 已提交
5130
		INIT_LIST_HEAD(&cache->list);
5131 5132 5133
		read_extent_buffer(leaf, &cache->item,
				   btrfs_item_ptr_offset(leaf, path->slots[0]),
				   sizeof(cache->item));
C
Chris Mason 已提交
5134
		memcpy(&cache->key, &found_key, sizeof(found_key));
5135

C
Chris Mason 已提交
5136 5137
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
5138
		cache->flags = btrfs_block_group_flags(&cache->item);
5139

5140 5141 5142 5143 5144
		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;
J
Josef Bacik 已提交
5145 5146 5147 5148 5149 5150
		spin_lock(&space_info->lock);
		list_add(&cache->list, &space_info->block_groups);
		spin_unlock(&space_info->lock);

		ret = btrfs_add_block_group_cache(root->fs_info, cache);
		BUG_ON(ret);
5151 5152

		set_avail_alloc_bits(root->fs_info, cache->flags);
C
Chris Mason 已提交
5153
	}
5154 5155
	ret = 0;
error:
C
Chris Mason 已提交
5156
	btrfs_free_path(path);
5157
	mutex_unlock(&root->fs_info->alloc_mutex);
5158
	return ret;
C
Chris Mason 已提交
5159
}
5160 5161 5162

int btrfs_make_block_group(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root, u64 bytes_used,
5163
			   u64 type, u64 chunk_objectid, u64 chunk_offset,
5164 5165 5166 5167 5168 5169
			   u64 size)
{
	int ret;
	struct btrfs_root *extent_root;
	struct btrfs_block_group_cache *cache;

5170
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
5171 5172
	extent_root = root->fs_info->extent_root;

5173 5174
	root->fs_info->last_trans_new_blockgroup = trans->transid;

5175
	cache = kzalloc(sizeof(*cache), GFP_NOFS);
J
Josef Bacik 已提交
5176 5177 5178
	if (!cache)
		return -ENOMEM;

5179
	cache->key.objectid = chunk_offset;
5180
	cache->key.offset = size;
5181
	spin_lock_init(&cache->lock);
J
Josef Bacik 已提交
5182
	INIT_LIST_HEAD(&cache->list);
5183
	btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
C
Chris Mason 已提交
5184

5185 5186 5187 5188 5189 5190 5191 5192
	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);
J
Josef Bacik 已提交
5193 5194 5195
	spin_lock(&cache->space_info->lock);
	list_add(&cache->list, &cache->space_info->block_groups);
	spin_unlock(&cache->space_info->lock);
5196

J
Josef Bacik 已提交
5197 5198
	ret = btrfs_add_block_group_cache(root->fs_info, cache);
	BUG_ON(ret);
5199

5200 5201 5202 5203 5204 5205 5206
	ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
				sizeof(cache->item));
	BUG_ON(ret);

	finish_current_insert(trans, extent_root);
	ret = del_pending_extents(trans, extent_root);
	BUG_ON(ret);
C
Chris Mason 已提交
5207
	set_avail_alloc_bits(extent_root->fs_info, type);
5208

5209 5210
	return 0;
}
Z
Zheng Yan 已提交
5211 5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253

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;

	BUG_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
	root = root->fs_info->extent_root;

	block_group = btrfs_lookup_block_group(root->fs_info, group_start);
	BUG_ON(!block_group);

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

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

	btrfs_remove_free_space_cache(block_group);
	rb_erase(&block_group->cache_node,
		 &root->fs_info->block_group_cache_tree);
	spin_lock(&block_group->space_info->lock);
	list_del(&block_group->list);
	spin_unlock(&block_group->space_info->lock);

	/*
	memset(shrink_block_group, 0, sizeof(*shrink_block_group));
	kfree(shrink_block_group);
	*/

	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;
}