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

31
#define BLOCK_GROUP_DATA     EXTENT_WRITEBACK
32
#define BLOCK_GROUP_METADATA EXTENT_UPTODATE
33 34
#define BLOCK_GROUP_SYSTEM   EXTENT_NEW

35 36
#define BLOCK_GROUP_DIRTY EXTENT_DIRTY

37 38
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root);
C
Chris Mason 已提交
39 40
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root);
41 42 43 44
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);
45

46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
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);
	}
}
63

64 65 66 67 68 69
static int cache_block_group(struct btrfs_root *root,
			     struct btrfs_block_group_cache *block_group)
{
	struct btrfs_path *path;
	int ret;
	struct btrfs_key key;
70
	struct extent_buffer *leaf;
71
	struct extent_io_tree *free_space_cache;
72 73 74
	int slot;
	u64 last = 0;
	u64 hole_size;
75
	u64 first_free;
76 77
	int found = 0;

78 79 80
	if (!block_group)
		return 0;

81
	root = root->fs_info->extent_root;
82
	free_space_cache = &root->fs_info->free_space_cache;
83 84 85

	if (block_group->cached)
		return 0;
86

87 88 89
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
90

91
	path->reada = 2;
92 93 94 95 96 97
	/*
	 * 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;
98
	first_free = block_group->key.objectid;
99 100 101 102 103 104
	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)
		return ret;
105
	ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
106 107 108 109 110 111 112 113
	if (ret < 0)
		return ret;
	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;
	}
114
	while(1) {
115
		leaf = path->nodes[0];
116
		slot = path->slots[0];
117
		if (slot >= btrfs_header_nritems(leaf)) {
118
			ret = btrfs_next_leaf(root, path);
119 120
			if (ret < 0)
				goto err;
121
			if (ret == 0) {
122
				continue;
123
			} else {
124 125 126
				break;
			}
		}
127
		btrfs_item_key_to_cpu(leaf, &key, slot);
128 129 130
		if (key.objectid < block_group->key.objectid) {
			goto next;
		}
131 132 133 134
		if (key.objectid >= block_group->key.objectid +
		    block_group->key.offset) {
			break;
		}
135

136 137
		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
			if (!found) {
138
				last = first_free;
139 140
				found = 1;
			}
141 142 143 144 145
			if (key.objectid > last) {
				hole_size = key.objectid - last;
				set_extent_dirty(free_space_cache, last,
						 last + hole_size - 1,
						 GFP_NOFS);
146 147
			}
			last = key.objectid + key.offset;
148
		}
149
next:
150 151 152
		path->slots[0]++;
	}

153 154 155 156 157 158
	if (!found)
		last = first_free;
	if (block_group->key.objectid +
	    block_group->key.offset > last) {
		hole_size = block_group->key.objectid +
			block_group->key.offset - last;
159 160
		set_extent_dirty(free_space_cache, last,
				 last + hole_size - 1, GFP_NOFS);
161
	}
162
	block_group->cached = 1;
163
err:
164 165 166 167
	btrfs_free_path(path);
	return 0;
}

C
Chris Mason 已提交
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 195 196
struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
						       btrfs_fs_info *info,
							 u64 bytenr)
{
	struct extent_io_tree *block_group_cache;
	struct btrfs_block_group_cache *block_group = NULL;
	u64 ptr;
	u64 start;
	u64 end;
	int ret;

	bytenr = max_t(u64, bytenr,
		       BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
	block_group_cache = &info->block_group_cache;
	ret = find_first_extent_bit(block_group_cache,
				    bytenr, &start, &end,
				    BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
				    BLOCK_GROUP_SYSTEM);
	if (ret) {
		return NULL;
	}
	ret = get_state_private(block_group_cache, start, &ptr);
	if (ret)
		return NULL;

	block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
	return block_group;
}

197 198
struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
							 btrfs_fs_info *info,
199
							 u64 bytenr)
C
Chris Mason 已提交
200
{
201
	struct extent_io_tree *block_group_cache;
202 203 204 205
	struct btrfs_block_group_cache *block_group = NULL;
	u64 ptr;
	u64 start;
	u64 end;
C
Chris Mason 已提交
206 207
	int ret;

208 209
	bytenr = max_t(u64, bytenr,
		       BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
210 211
	block_group_cache = &info->block_group_cache;
	ret = find_first_extent_bit(block_group_cache,
212
				    bytenr, &start, &end,
213 214
				    BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
				    BLOCK_GROUP_SYSTEM);
C
Chris Mason 已提交
215
	if (ret) {
216
		return NULL;
C
Chris Mason 已提交
217
	}
218 219 220 221
	ret = get_state_private(block_group_cache, start, &ptr);
	if (ret)
		return NULL;

J
Jens Axboe 已提交
222
	block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
Y
Yan 已提交
223
	if (block_group->key.objectid <= bytenr && bytenr <
224 225
	    block_group->key.objectid + block_group->key.offset)
		return block_group;
C
Chris Mason 已提交
226 227
	return NULL;
}
228 229 230

static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
{
231
	return (cache->flags & bits) == bits;
232 233 234
}

static int noinline find_search_start(struct btrfs_root *root,
235
			      struct btrfs_block_group_cache **cache_ret,
C
Chris Mason 已提交
236
			      u64 *start_ret, u64 num, int data)
237 238 239
{
	int ret;
	struct btrfs_block_group_cache *cache = *cache_ret;
C
Chris Mason 已提交
240
	struct extent_io_tree *free_space_cache;
241
	struct extent_state *state;
242
	u64 last;
243
	u64 start = 0;
244
	u64 cache_miss = 0;
C
Chris Mason 已提交
245
	u64 total_fs_bytes;
246
	u64 search_start = *start_ret;
247
	int wrapped = 0;
248

249
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
C
Chris Mason 已提交
250
	total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
C
Chris Mason 已提交
251 252
	free_space_cache = &root->fs_info->free_space_cache;

C
Chris Mason 已提交
253 254 255
	if (!cache)
		goto out;

256
again:
257
	ret = cache_block_group(root, cache);
C
Chris Mason 已提交
258
	if (ret) {
259
		goto out;
C
Chris Mason 已提交
260
	}
261

262
	last = max(search_start, cache->key.objectid);
C
Chris Mason 已提交
263
	if (!block_group_bits(cache, data) || cache->ro)
264
		goto new_group;
265

266 267
	spin_lock_irq(&free_space_cache->lock);
	state = find_first_extent_bit_state(free_space_cache, last, EXTENT_DIRTY);
268
	while(1) {
269
		if (!state) {
270 271
			if (!cache_miss)
				cache_miss = last;
272
			spin_unlock_irq(&free_space_cache->lock);
273 274
			goto new_group;
		}
275

276 277
		start = max(last, state->start);
		last = state->end + 1;
278
		if (last - start < num) {
279 280 281
			do {
				state = extent_state_next(state);
			} while(state && !(state->state & EXTENT_DIRTY));
282
			continue;
283
		}
284
		spin_unlock_irq(&free_space_cache->lock);
C
Chris Mason 已提交
285
		if (cache->ro) {
286
			goto new_group;
C
Chris Mason 已提交
287
		}
288
		if (start + num > cache->key.objectid + cache->key.offset)
289
			goto new_group;
290
		if (!block_group_bits(cache, data)) {
291
			printk("block group bits don't match %Lu %d\n", cache->flags, data);
292
		}
293 294
		*start_ret = start;
		return 0;
295 296
	}
out:
297 298
	cache = btrfs_lookup_block_group(root->fs_info, search_start);
	if (!cache) {
299
		printk("Unable to find block group for %Lu\n", search_start);
300 301
		WARN_ON(1);
	}
302
	return -ENOSPC;
303 304

new_group:
305
	last = cache->key.objectid + cache->key.offset;
306
wrapped:
C
Chris Mason 已提交
307
	cache = btrfs_lookup_first_block_group(root->fs_info, last);
C
Chris Mason 已提交
308
	if (!cache || cache->key.objectid >= total_fs_bytes) {
309
no_cache:
310 311 312 313 314
		if (!wrapped) {
			wrapped = 1;
			last = search_start;
			goto wrapped;
		}
315
		goto out;
316
	}
317 318 319
	if (cache_miss && !cache->cached) {
		cache_block_group(root, cache);
		last = cache_miss;
C
Chris Mason 已提交
320
		cache = btrfs_lookup_first_block_group(root->fs_info, last);
321
	}
C
Chris Mason 已提交
322
	cache_miss = 0;
323
	cache = btrfs_find_block_group(root, cache, last, data, 0);
324 325
	if (!cache)
		goto no_cache;
326 327 328 329
	*cache_ret = cache;
	goto again;
}

C
Chris Mason 已提交
330 331
static u64 div_factor(u64 num, int factor)
{
332 333
	if (factor == 10)
		return num;
C
Chris Mason 已提交
334 335 336 337 338
	num *= factor;
	do_div(num, 10);
	return num;
}

339 340 341 342 343 344 345 346 347 348 349 350
static int block_group_state_bits(u64 flags)
{
	int bits = 0;
	if (flags & BTRFS_BLOCK_GROUP_DATA)
		bits |= BLOCK_GROUP_DATA;
	if (flags & BTRFS_BLOCK_GROUP_METADATA)
		bits |= BLOCK_GROUP_METADATA;
	if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
		bits |= BLOCK_GROUP_SYSTEM;
	return bits;
}

351 352 353 354
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 已提交
355
{
356
	struct btrfs_block_group_cache *cache;
357
	struct extent_io_tree *block_group_cache;
358
	struct btrfs_block_group_cache *found_group = NULL;
C
Chris Mason 已提交
359 360
	struct btrfs_fs_info *info = root->fs_info;
	u64 used;
361
	u64 last = 0;
362 363 364 365 366
	u64 start;
	u64 end;
	u64 free_check;
	u64 ptr;
	int bit;
C
Chris Mason 已提交
367
	int ret;
368
	int full_search = 0;
369
	int factor = 10;
C
Chris Mason 已提交
370
	int wrapped = 0;
371

372 373
	block_group_cache = &info->block_group_cache;

374 375
	if (data & BTRFS_BLOCK_GROUP_METADATA)
		factor = 9;
C
Chris Mason 已提交
376

377
	bit = block_group_state_bits(data);
C
Chris Mason 已提交
378

C
Chris Mason 已提交
379
	if (search_start) {
C
Chris Mason 已提交
380
		struct btrfs_block_group_cache *shint;
C
Chris Mason 已提交
381
		shint = btrfs_lookup_first_block_group(info, search_start);
382
		if (shint && block_group_bits(shint, data) && !shint->ro) {
383
			spin_lock(&shint->lock);
C
Chris Mason 已提交
384
			used = btrfs_block_group_used(&shint->item);
385 386
			if (used + shint->pinned <
			    div_factor(shint->key.offset, factor)) {
387
				spin_unlock(&shint->lock);
C
Chris Mason 已提交
388 389
				return shint;
			}
390
			spin_unlock(&shint->lock);
C
Chris Mason 已提交
391 392
		}
	}
C
Chris Mason 已提交
393
	if (hint && !hint->ro && block_group_bits(hint, data)) {
394
		spin_lock(&hint->lock);
395
		used = btrfs_block_group_used(&hint->item);
396 397
		if (used + hint->pinned <
		    div_factor(hint->key.offset, factor)) {
398
			spin_unlock(&hint->lock);
399 400
			return hint;
		}
401
		spin_unlock(&hint->lock);
402
		last = hint->key.objectid + hint->key.offset;
403
	} else {
404
		if (hint)
C
Chris Mason 已提交
405
			last = max(hint->key.objectid, search_start);
406
		else
C
Chris Mason 已提交
407
			last = search_start;
408 409
	}
again:
C
Chris Mason 已提交
410
	while(1) {
411 412 413
		ret = find_first_extent_bit(block_group_cache, last,
					    &start, &end, bit);
		if (ret)
C
Chris Mason 已提交
414
			break;
415 416

		ret = get_state_private(block_group_cache, start, &ptr);
C
Chris Mason 已提交
417 418 419 420
		if (ret) {
			last = end + 1;
			continue;
		}
421

J
Jens Axboe 已提交
422
		cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
423
		spin_lock(&cache->lock);
424 425 426
		last = cache->key.objectid + cache->key.offset;
		used = btrfs_block_group_used(&cache->item);

427
		if (!cache->ro && block_group_bits(cache, data)) {
C
Chris Mason 已提交
428
			free_check = div_factor(cache->key.offset, factor);
429 430
			if (used + cache->pinned < free_check) {
				found_group = cache;
431
				spin_unlock(&cache->lock);
432 433
				goto found;
			}
434
		}
435
		spin_unlock(&cache->lock);
436
		cond_resched();
C
Chris Mason 已提交
437
	}
C
Chris Mason 已提交
438 439 440 441 442 443
	if (!wrapped) {
		last = search_start;
		wrapped = 1;
		goto again;
	}
	if (!full_search && factor < 10) {
C
Chris Mason 已提交
444
		last = search_start;
445
		full_search = 1;
C
Chris Mason 已提交
446
		factor = 10;
447 448
		goto again;
	}
C
Chris Mason 已提交
449
found:
450
	return found_group;
C
Chris Mason 已提交
451 452
}

453 454 455 456 457 458 459 460 461 462
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;
}
463
static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
464 465 466 467 468 469
			   u64 owner, u64 owner_offset)
{
	u32 high_crc = ~(u32)0;
	u32 low_crc = ~(u32)0;
	__le64 lenum;
	lenum = cpu_to_le64(root_objectid);
470
	high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
471
	lenum = cpu_to_le64(ref_generation);
472
	low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
473 474
	if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
		lenum = cpu_to_le64(owner);
475
		low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
476
		lenum = cpu_to_le64(owner_offset);
477
		low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
478
	}
479 480 481
	return ((u64)high_crc << 32) | (u64)low_crc;
}

482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
static int match_extent_ref(struct extent_buffer *leaf,
			    struct btrfs_extent_ref *disk_ref,
			    struct btrfs_extent_ref *cpu_ref)
{
	int ret;
	int len;

	if (cpu_ref->objectid)
		len = sizeof(*cpu_ref);
	else
		len = 2 * sizeof(u64);
	ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
				   len);
	return ret == 0;
}

498 499 500 501 502 503
static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
					  struct btrfs_root *root,
					  struct btrfs_path *path, u64 bytenr,
					  u64 root_objectid,
					  u64 ref_generation, u64 owner,
					  u64 owner_offset, int del)
504 505 506
{
	u64 hash;
	struct btrfs_key key;
507
	struct btrfs_key found_key;
508
	struct btrfs_extent_ref ref;
509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563
	struct extent_buffer *leaf;
	struct btrfs_extent_ref *disk_ref;
	int ret;
	int ret2;

	btrfs_set_stack_ref_root(&ref, root_objectid);
	btrfs_set_stack_ref_generation(&ref, ref_generation);
	btrfs_set_stack_ref_objectid(&ref, owner);
	btrfs_set_stack_ref_offset(&ref, owner_offset);

	hash = hash_extent_ref(root_objectid, ref_generation, owner,
			       owner_offset);
	key.offset = hash;
	key.objectid = bytenr;
	key.type = BTRFS_EXTENT_REF_KEY;

	while (1) {
		ret = btrfs_search_slot(trans, root, &key, path,
					del ? -1 : 0, del);
		if (ret < 0)
			goto out;
		leaf = path->nodes[0];
		if (ret != 0) {
			u32 nritems = btrfs_header_nritems(leaf);
			if (path->slots[0] >= nritems) {
				ret2 = btrfs_next_leaf(root, path);
				if (ret2)
					goto out;
				leaf = path->nodes[0];
			}
			btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
			if (found_key.objectid != bytenr ||
			    found_key.type != BTRFS_EXTENT_REF_KEY)
				goto out;
			key.offset = found_key.offset;
			if (del) {
				btrfs_release_path(root, path);
				continue;
			}
		}
		disk_ref = btrfs_item_ptr(path->nodes[0],
					  path->slots[0],
					  struct btrfs_extent_ref);
		if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
			ret = 0;
			goto out;
		}
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		key.offset = found_key.offset + 1;
		btrfs_release_path(root, path);
	}
out:
	return ret;
}

564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626
/*
 * 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
 * - different files inside a single subvolume (in theory, not implemented yet)
 * - 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
 * - offset in the file corresponding to the key holding the reference
 *
 * When a file extent is allocated the fields are filled in:
 *     (root_key.objectid, trans->transid, inode objectid, offset in file)
 *
 * When a leaf is cow'd new references are added for every file extent found
 * in the leaf.  It looks the same as the create case, but trans->transid
 * will be different when the block is cow'd.
 *
 *     (root_key.objectid, trans->transid, inode objectid, offset in file)
 *
 * When a file extent is removed either during snapshot deletion or file
 * truncation, the corresponding back reference is found
 * by searching for:
 *
 *     (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
 *      inode objectid, offset in file)
 *
 * Btree extents can be referenced by:
 *
 * - Different subvolumes
 * - Different generations of the same subvolume
 *
 * Storing sufficient information for a full reverse mapping of a btree
 * block would require storing the lowest key of the block in the backref,
 * and it would require updating that lowest key either before write out or
 * every time it changed.  Instead, the objectid of the lowest key is stored
 * along with the level of the tree block.  This provides a hint
 * about where in the btree the block can be found.  Searches through the
 * btree only need to look for a pointer to that block, so they stop one
 * level higher than the level recorded in the backref.
 *
 * Some btrees do not do reference counting on their extents.  These
 * include the extent tree and the tree of tree roots.  Backrefs for these
 * trees always have a generation of zero.
 *
 * When a tree block is created, back references are inserted:
 *
627
 * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
628 629 630 631 632
 *
 * When a tree block is cow'd in a reference counted root,
 * new back references are added for all the blocks it points to.
 * These are of the form (trans->transid will have increased since creation):
 *
633
 * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651
 *
 * Because the lowest_key_objectid and the level are just hints
 * they are not used when backrefs are deleted.  When a backref is deleted:
 *
 * if backref was for a tree root:
 *     root_objectid = root->root_key.objectid
 * else
 *     root_objectid = btrfs_header_owner(parent)
 *
 * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
 *
 * Back Reference Key hashing:
 *
 * Back references have four fields, each 64 bits long.  Unfortunately,
 * This is hashed into a single 64 bit number and placed into the key offset.
 * The key objectid corresponds to the first byte in the extent, and the
 * key type is set to BTRFS_EXTENT_REF_KEY
 */
652 653 654 655 656 657 658 659 660 661
int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
				 struct btrfs_root *root,
				 struct btrfs_path *path, u64 bytenr,
				 u64 root_objectid, u64 ref_generation,
				 u64 owner, u64 owner_offset)
{
	u64 hash;
	struct btrfs_key key;
	struct btrfs_extent_ref ref;
	struct btrfs_extent_ref *disk_ref;
662 663 664
	int ret;

	btrfs_set_stack_ref_root(&ref, root_objectid);
665
	btrfs_set_stack_ref_generation(&ref, ref_generation);
666 667 668
	btrfs_set_stack_ref_objectid(&ref, owner);
	btrfs_set_stack_ref_offset(&ref, owner_offset);

669 670
	hash = hash_extent_ref(root_objectid, ref_generation, owner,
			       owner_offset);
671 672 673 674 675 676
	key.offset = hash;
	key.objectid = bytenr;
	key.type = BTRFS_EXTENT_REF_KEY;

	ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
	while (ret == -EEXIST) {
677 678 679 680 681 682 683 684
		disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
					  struct btrfs_extent_ref);
		if (match_extent_ref(path->nodes[0], disk_ref, &ref))
			goto out;
		key.offset++;
		btrfs_release_path(root, path);
		ret = btrfs_insert_empty_item(trans, root, path, &key,
					      sizeof(ref));
685
	}
686 687 688 689 690 691 692 693 694 695
	if (ret)
		goto out;
	disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
				  struct btrfs_extent_ref);
	write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
			    sizeof(ref));
	btrfs_mark_buffer_dirty(path->nodes[0]);
out:
	btrfs_release_path(root, path);
	return ret;
696 697
}

698
static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
C
Chris Mason 已提交
699
				struct btrfs_root *root,
700
				u64 bytenr, u64 num_bytes,
701
				u64 root_objectid, u64 ref_generation,
702
				u64 owner, u64 owner_offset)
C
Chris Mason 已提交
703
{
704
	struct btrfs_path *path;
C
Chris Mason 已提交
705
	int ret;
C
Chris Mason 已提交
706
	struct btrfs_key key;
707
	struct extent_buffer *l;
C
Chris Mason 已提交
708
	struct btrfs_extent_item *item;
C
Chris Mason 已提交
709
	u32 refs;
C
Chris Mason 已提交
710

711
	WARN_ON(num_bytes < root->sectorsize);
712
	path = btrfs_alloc_path();
713 714
	if (!path)
		return -ENOMEM;
715

716
	path->reada = 1;
717
	key.objectid = bytenr;
718
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
719
	key.offset = num_bytes;
720
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
721
				0, 1);
722 723
	if (ret < 0)
		return ret;
724
	if (ret != 0) {
725
		BUG();
726
	}
C
Chris Mason 已提交
727
	BUG_ON(ret != 0);
728
	l = path->nodes[0];
729
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
730 731
	refs = btrfs_extent_refs(l, item);
	btrfs_set_extent_refs(l, item, refs + 1);
732
	btrfs_mark_buffer_dirty(path->nodes[0]);
733

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

736
	path->reada = 1;
737 738 739 740
	ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
					  path, bytenr, root_objectid,
					  ref_generation, owner, owner_offset);
	BUG_ON(ret);
741
	finish_current_insert(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
742
	del_pending_extents(trans, root->fs_info->extent_root);
743 744

	btrfs_free_path(path);
C
Chris Mason 已提交
745 746 747
	return 0;
}

748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763
int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
				struct btrfs_root *root,
				u64 bytenr, u64 num_bytes,
				u64 root_objectid, u64 ref_generation,
				u64 owner, u64 owner_offset)
{
	int ret;

	mutex_lock(&root->fs_info->alloc_mutex);
	ret = __btrfs_inc_extent_ref(trans, root, bytenr, num_bytes,
				     root_objectid, ref_generation,
				     owner, owner_offset);
	mutex_unlock(&root->fs_info->alloc_mutex);
	return ret;
}

764 765 766 767 768 769 770 771
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;
}

C
Chris Mason 已提交
772
static int lookup_extent_ref(struct btrfs_trans_handle *trans,
773 774
			     struct btrfs_root *root, u64 bytenr,
			     u64 num_bytes, u32 *refs)
775
{
776
	struct btrfs_path *path;
777
	int ret;
C
Chris Mason 已提交
778
	struct btrfs_key key;
779
	struct extent_buffer *l;
C
Chris Mason 已提交
780
	struct btrfs_extent_item *item;
781

782
	WARN_ON(num_bytes < root->sectorsize);
783
	path = btrfs_alloc_path();
784
	path->reada = 1;
785 786
	key.objectid = bytenr;
	key.offset = num_bytes;
787
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
788
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
789
				0, 0);
790 791
	if (ret < 0)
		goto out;
792 793
	if (ret != 0) {
		btrfs_print_leaf(root, path->nodes[0]);
794
		printk("failed to find block number %Lu\n", bytenr);
795
		BUG();
796 797
	}
	l = path->nodes[0];
798
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
799
	*refs = btrfs_extent_refs(l, item);
800
out:
801
	btrfs_free_path(path);
802 803 804
	return 0;
}

805 806
u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
				  struct btrfs_path *count_path,
807
				  u64 expected_owner,
808 809 810 811 812 813
				  u64 first_extent)
{
	struct btrfs_root *extent_root = root->fs_info->extent_root;
	struct btrfs_path *path;
	u64 bytenr;
	u64 found_objectid;
814
	u64 found_owner;
815
	u64 root_objectid = root->root_key.objectid;
816
	u32 total_count = 0;
C
Chris Mason 已提交
817
	u32 extent_refs;
818 819 820 821 822 823 824 825 826 827
	u32 cur_count;
	u32 nritems;
	int ret;
	struct btrfs_key key;
	struct btrfs_key found_key;
	struct extent_buffer *l;
	struct btrfs_extent_item *item;
	struct btrfs_extent_ref *ref_item;
	int level = -1;

828 829 830 831
	/* FIXME, needs locking */
	BUG();

	mutex_lock(&root->fs_info->alloc_mutex);
832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857
	path = btrfs_alloc_path();
again:
	if (level == -1)
		bytenr = first_extent;
	else
		bytenr = count_path->nodes[level]->start;

	cur_count = 0;
	key.objectid = bytenr;
	key.offset = 0;

	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
	if (ret < 0)
		goto out;
	BUG_ON(ret == 0);

	l = path->nodes[0];
	btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);

	if (found_key.objectid != bytenr ||
	    found_key.type != BTRFS_EXTENT_ITEM_KEY) {
		goto out;
	}

	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
C
Chris Mason 已提交
858
	extent_refs = btrfs_extent_refs(l, item);
859
	while (1) {
860
		l = path->nodes[0];
861 862 863 864 865 866 867 868 869 870
		nritems = btrfs_header_nritems(l);
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(extent_root, path);
			if (ret == 0)
				continue;
			break;
		}
		btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
		if (found_key.objectid != bytenr)
			break;
871

872 873 874 875 876 877 878 879 880 881
		if (found_key.type != BTRFS_EXTENT_REF_KEY) {
			path->slots[0]++;
			continue;
		}

		cur_count++;
		ref_item = btrfs_item_ptr(l, path->slots[0],
					  struct btrfs_extent_ref);
		found_objectid = btrfs_ref_root(l, ref_item);

882 883
		if (found_objectid != root_objectid) {
			total_count = 2;
884
			goto out;
885
		}
886 887 888 889 890 891
		if (level == -1) {
			found_owner = btrfs_ref_objectid(l, ref_item);
			if (found_owner != expected_owner) {
				total_count = 2;
				goto out;
			}
C
Chris Mason 已提交
892 893 894 895 896 897 898 899 900 901
			/*
			 * nasty.  we don't count a reference held by
			 * the running transaction.  This allows nodatacow
			 * to avoid cow most of the time
			 */
			if (found_owner >= BTRFS_FIRST_FREE_OBJECTID &&
			    btrfs_ref_generation(l, ref_item) ==
			    root->fs_info->generation) {
				extent_refs--;
			}
902
		}
903
		total_count = 1;
904 905
		path->slots[0]++;
	}
C
Chris Mason 已提交
906 907 908 909 910 911 912 913
	/*
	 * if there is more than one reference against a data extent,
	 * we have to assume the other ref is another snapshot
	 */
	if (level == -1 && extent_refs > 1) {
		total_count = 2;
		goto out;
	}
914 915 916 917 918 919 920 921 922 923 924 925
	if (cur_count == 0) {
		total_count = 0;
		goto out;
	}
	if (level >= 0 && root->node == count_path->nodes[level])
		goto out;
	level++;
	btrfs_release_path(root, path);
	goto again;

out:
	btrfs_free_path(path);
926
	mutex_unlock(&root->fs_info->alloc_mutex);
927 928
	return total_count;
}
C
Chris Mason 已提交
929

930
int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
Y
Yan Zheng 已提交
931
		  struct extent_buffer *buf, int cache_ref)
C
Chris Mason 已提交
932
{
933
	u64 bytenr;
934 935
	u32 nritems;
	struct btrfs_key key;
936
	struct btrfs_file_extent_item *fi;
C
Chris Mason 已提交
937
	int i;
938
	int level;
939
	int ret;
940
	int faili;
Y
Yan Zheng 已提交
941
	int nr_file_extents = 0;
942

943
	if (!root->ref_cows)
944
		return 0;
945

946
	level = btrfs_header_level(buf);
947 948
	nritems = btrfs_header_nritems(buf);
	for (i = 0; i < nritems; i++) {
949
		cond_resched();
950 951
		if (level == 0) {
			u64 disk_bytenr;
952 953
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
954
				continue;
955
			fi = btrfs_item_ptr(buf, i,
956
					    struct btrfs_file_extent_item);
957
			if (btrfs_file_extent_type(buf, fi) ==
958 959
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
960 961
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
C
Chris Mason 已提交
962
				continue;
C
Chris Mason 已提交
963

Y
Yan Zheng 已提交
964 965 966
			if (buf != root->commit_root)
				nr_file_extents++;

C
Chris Mason 已提交
967
			mutex_lock(&root->fs_info->alloc_mutex);
968
			ret = __btrfs_inc_extent_ref(trans, root, disk_bytenr,
969 970 971
				    btrfs_file_extent_disk_num_bytes(buf, fi),
				    root->root_key.objectid, trans->transid,
				    key.objectid, key.offset);
C
Chris Mason 已提交
972
			mutex_unlock(&root->fs_info->alloc_mutex);
973 974
			if (ret) {
				faili = i;
C
Chris Mason 已提交
975
				WARN_ON(1);
976 977
				goto fail;
			}
978
		} else {
979
			bytenr = btrfs_node_blockptr(buf, i);
980
			btrfs_node_key_to_cpu(buf, &key, i);
C
Chris Mason 已提交
981 982

			mutex_lock(&root->fs_info->alloc_mutex);
983
			ret = __btrfs_inc_extent_ref(trans, root, bytenr,
984 985
					   btrfs_level_size(root, level - 1),
					   root->root_key.objectid,
986 987
					   trans->transid,
					   level - 1, key.objectid);
C
Chris Mason 已提交
988
			mutex_unlock(&root->fs_info->alloc_mutex);
989 990
			if (ret) {
				faili = i;
C
Chris Mason 已提交
991
				WARN_ON(1);
992 993
				goto fail;
			}
994
		}
C
Chris Mason 已提交
995
	}
Y
Yan Zheng 已提交
996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042
	/* cache orignal leaf block's references */
	if (level == 0 && cache_ref && buf != root->commit_root) {
		struct btrfs_leaf_ref *ref;
		struct btrfs_extent_info *info;

		ref = btrfs_alloc_leaf_ref(nr_file_extents);
		if (!ref) {
			WARN_ON(1);
			goto out;
		}

		btrfs_item_key_to_cpu(buf, &ref->key, 0);

		ref->bytenr = buf->start;
		ref->owner = btrfs_header_owner(buf);
		ref->generation = btrfs_header_generation(buf);
		ref->nritems = nr_file_extents;
		info = ref->extents;
		
		for (i = 0; nr_file_extents > 0 && i < nritems; i++) {
			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++;
		}

		BUG_ON(!root->ref_tree);
		ret = btrfs_add_leaf_ref(root, ref);
		WARN_ON(ret);
		btrfs_free_leaf_ref(ref);
	}
out:
C
Chris Mason 已提交
1043
	return 0;
1044
fail:
C
Chris Mason 已提交
1045
	WARN_ON(1);
1046
#if 0
1047
	for (i =0; i < faili; i++) {
1048 1049
		if (level == 0) {
			u64 disk_bytenr;
1050 1051
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1052
				continue;
1053
			fi = btrfs_item_ptr(buf, i,
1054
					    struct btrfs_file_extent_item);
1055
			if (btrfs_file_extent_type(buf, fi) ==
1056 1057
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
1058 1059
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
1060
				continue;
1061 1062
			err = btrfs_free_extent(trans, root, disk_bytenr,
				    btrfs_file_extent_disk_num_bytes(buf,
1063
								      fi), 0);
1064 1065
			BUG_ON(err);
		} else {
1066 1067 1068
			bytenr = btrfs_node_blockptr(buf, i);
			err = btrfs_free_extent(trans, root, bytenr,
					btrfs_level_size(root, level - 1), 0);
1069 1070 1071
			BUG_ON(err);
		}
	}
1072
#endif
1073
	return ret;
C
Chris Mason 已提交
1074 1075
}

C
Chris Mason 已提交
1076 1077 1078 1079 1080 1081 1082 1083
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;
1084 1085
	unsigned long bi;
	struct extent_buffer *leaf;
C
Chris Mason 已提交
1086 1087

	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1088 1089
	if (ret < 0)
		goto fail;
C
Chris Mason 已提交
1090
	BUG_ON(ret);
1091 1092 1093 1094 1095

	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 已提交
1096
	btrfs_release_path(extent_root, path);
1097
fail:
C
Chris Mason 已提交
1098 1099 1100 1101 1102 1103 1104 1105 1106 1107
	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;

}

1108 1109
int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root)
C
Chris Mason 已提交
1110
{
1111
	struct extent_io_tree *block_group_cache;
1112
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
1113 1114 1115 1116
	int ret;
	int err = 0;
	int werr = 0;
	struct btrfs_path *path;
1117 1118 1119 1120
	u64 last = 0;
	u64 start;
	u64 end;
	u64 ptr;
C
Chris Mason 已提交
1121

1122
	block_group_cache = &root->fs_info->block_group_cache;
C
Chris Mason 已提交
1123 1124 1125 1126
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

1127
	mutex_lock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
1128
	while(1) {
1129 1130 1131
		ret = find_first_extent_bit(block_group_cache, last,
					    &start, &end, BLOCK_GROUP_DIRTY);
		if (ret)
C
Chris Mason 已提交
1132
			break;
1133

1134 1135 1136 1137
		last = end + 1;
		ret = get_state_private(block_group_cache, start, &ptr);
		if (ret)
			break;
J
Jens Axboe 已提交
1138
		cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
1139 1140 1141 1142 1143 1144 1145 1146 1147 1148
		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 已提交
1149
		}
1150 1151
		clear_extent_bits(block_group_cache, start, end,
				  BLOCK_GROUP_DIRTY, GFP_NOFS);
C
Chris Mason 已提交
1152 1153
	}
	btrfs_free_path(path);
1154
	mutex_unlock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
1155 1156 1157
	return werr;
}

1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172
static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
						  u64 flags)
{
	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;

}

1173 1174 1175 1176 1177 1178 1179 1180 1181 1182
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;
1183
		found->full = 0;
1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197
		WARN_ON(found->total_bytes < found->bytes_used);
		*space_info = found;
		return 0;
	}
	found = kmalloc(sizeof(*found), GFP_NOFS);
	if (!found)
		return -ENOMEM;

	list_add(&found->list, &info->space_info);
	found->flags = flags;
	found->total_bytes = total_bytes;
	found->bytes_used = bytes_used;
	found->bytes_pinned = 0;
	found->full = 0;
C
Chris Mason 已提交
1198
	found->force_alloc = 0;
1199 1200 1201 1202
	*space_info = found;
	return 0;
}

1203 1204 1205
static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
{
	u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1206
				   BTRFS_BLOCK_GROUP_RAID1 |
C
Chris Mason 已提交
1207
				   BTRFS_BLOCK_GROUP_RAID10 |
1208
				   BTRFS_BLOCK_GROUP_DUP);
1209 1210 1211 1212 1213 1214 1215 1216 1217
	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;
	}
}
1218

1219
static u64 reduce_alloc_profile(struct btrfs_root *root, u64 flags)
1220
{
1221 1222 1223 1224 1225 1226 1227
	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;

1228 1229
	if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
	    (flags & (BTRFS_BLOCK_GROUP_RAID1 |
1230
		      BTRFS_BLOCK_GROUP_RAID10))) {
1231
		flags &= ~BTRFS_BLOCK_GROUP_DUP;
1232
	}
1233 1234

	if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
1235
	    (flags & BTRFS_BLOCK_GROUP_RAID10)) {
1236
		flags &= ~BTRFS_BLOCK_GROUP_RAID1;
1237
	}
1238 1239 1240 1241 1242 1243 1244 1245 1246

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

1247 1248
static int do_chunk_alloc(struct btrfs_trans_handle *trans,
			  struct btrfs_root *extent_root, u64 alloc_bytes,
C
Chris Mason 已提交
1249
			  u64 flags, int force)
1250 1251 1252 1253 1254 1255 1256
{
	struct btrfs_space_info *space_info;
	u64 thresh;
	u64 start;
	u64 num_bytes;
	int ret;

1257
	flags = reduce_alloc_profile(extent_root, flags);
1258

1259
	space_info = __find_space_info(extent_root->fs_info, flags);
1260 1261 1262 1263 1264
	if (!space_info) {
		ret = update_space_info(extent_root->fs_info, flags,
					0, 0, &space_info);
		BUG_ON(ret);
	}
1265 1266
	BUG_ON(!space_info);

C
Chris Mason 已提交
1267 1268 1269 1270
	if (space_info->force_alloc) {
		force = 1;
		space_info->force_alloc = 0;
	}
1271
	if (space_info->full)
1272
		goto out;
1273

1274
	thresh = div_factor(space_info->total_bytes, 6);
C
Chris Mason 已提交
1275 1276
	if (!force &&
	   (space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
1277
	    thresh)
1278
		goto out;
1279

1280
	mutex_lock(&extent_root->fs_info->chunk_mutex);
1281 1282 1283 1284
	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;
1285
		goto out_unlock;
1286 1287 1288 1289
	}
	BUG_ON(ret);

	ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1290
		     BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1291
	BUG_ON(ret);
1292
out_unlock:
1293
	mutex_unlock(&extent_root->fs_info->chunk_mutex);
1294
out:
1295 1296 1297
	return 0;
}

C
Chris Mason 已提交
1298 1299
static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
1300
			      u64 bytenr, u64 num_bytes, int alloc,
1301
			      int mark_free)
C
Chris Mason 已提交
1302 1303 1304
{
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *info = root->fs_info;
1305
	u64 total = num_bytes;
C
Chris Mason 已提交
1306
	u64 old_val;
1307
	u64 byte_in_group;
1308 1309
	u64 start;
	u64 end;
C
Chris Mason 已提交
1310

1311
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
C
Chris Mason 已提交
1312
	while(total) {
1313
		cache = btrfs_lookup_block_group(info, bytenr);
C
Chris Mason 已提交
1314
		if (!cache) {
C
Chris Mason 已提交
1315
			return -1;
C
Chris Mason 已提交
1316
		}
1317 1318
		byte_in_group = bytenr - cache->key.objectid;
		WARN_ON(byte_in_group > cache->key.offset);
1319 1320 1321 1322
		start = cache->key.objectid;
		end = start + cache->key.offset - 1;
		set_extent_bits(&info->block_group_cache, start, end,
				BLOCK_GROUP_DIRTY, GFP_NOFS);
C
Chris Mason 已提交
1323

1324
		spin_lock(&cache->lock);
C
Chris Mason 已提交
1325
		old_val = btrfs_block_group_used(&cache->item);
1326
		num_bytes = min(total, cache->key.offset - byte_in_group);
C
Chris Mason 已提交
1327
		if (alloc) {
1328
			old_val += num_bytes;
1329
			cache->space_info->bytes_used += num_bytes;
1330 1331
			btrfs_set_block_group_used(&cache->item, old_val);
			spin_unlock(&cache->lock);
C
Chris Mason 已提交
1332
		} else {
1333
			old_val -= num_bytes;
1334
			cache->space_info->bytes_used -= num_bytes;
1335 1336
			btrfs_set_block_group_used(&cache->item, old_val);
			spin_unlock(&cache->lock);
1337 1338
			if (mark_free) {
				set_extent_dirty(&info->free_space_cache,
1339
						 bytenr, bytenr + num_bytes - 1,
1340
						 GFP_NOFS);
1341
			}
C
Chris Mason 已提交
1342
		}
1343 1344
		total -= num_bytes;
		bytenr += num_bytes;
C
Chris Mason 已提交
1345 1346 1347
	}
	return 0;
}
1348

1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363
static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
{
	u64 start;
	u64 end;
	int ret;
	ret = find_first_extent_bit(&root->fs_info->block_group_cache,
				    search_start, &start, &end,
				    BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
				    BLOCK_GROUP_SYSTEM);
	if (ret)
		return 0;
	return start;
}


1364 1365 1366 1367 1368 1369 1370
static int update_pinned_extents(struct btrfs_root *root,
				u64 bytenr, u64 num, int pin)
{
	u64 len;
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *fs_info = root->fs_info;

1371
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1372 1373 1374 1375 1376 1377 1378 1379 1380
	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);
1381 1382 1383 1384 1385 1386 1387 1388
		if (!cache) {
			u64 first = first_logical_byte(root, bytenr);
			WARN_ON(first < bytenr);
			len = min(first - bytenr, num);
		} else {
			len = min(num, cache->key.offset -
				  (bytenr - cache->key.objectid));
		}
1389
		if (pin) {
1390
			if (cache) {
1391
				spin_lock(&cache->lock);
1392 1393
				cache->pinned += len;
				cache->space_info->bytes_pinned += len;
1394
				spin_unlock(&cache->lock);
1395
			}
1396 1397
			fs_info->total_pinned += len;
		} else {
1398
			if (cache) {
1399
				spin_lock(&cache->lock);
1400 1401
				cache->pinned -= len;
				cache->space_info->bytes_pinned -= len;
1402
				spin_unlock(&cache->lock);
1403
			}
1404 1405 1406 1407 1408 1409 1410
			fs_info->total_pinned -= len;
		}
		bytenr += len;
		num -= len;
	}
	return 0;
}
C
Chris Mason 已提交
1411

1412
int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
C
Chris Mason 已提交
1413 1414
{
	u64 last = 0;
1415 1416
	u64 start;
	u64 end;
1417
	struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
C
Chris Mason 已提交
1418 1419 1420
	int ret;

	while(1) {
1421 1422 1423
		ret = find_first_extent_bit(pinned_extents, last,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
C
Chris Mason 已提交
1424
			break;
1425 1426
		set_extent_dirty(copy, start, end, GFP_NOFS);
		last = end + 1;
C
Chris Mason 已提交
1427 1428 1429 1430 1431 1432
	}
	return 0;
}

int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
1433
			       struct extent_io_tree *unpin)
1434
{
1435 1436
	u64 start;
	u64 end;
1437
	int ret;
1438
	struct extent_io_tree *free_space_cache;
1439
	free_space_cache = &root->fs_info->free_space_cache;
1440

1441
	mutex_lock(&root->fs_info->alloc_mutex);
1442
	while(1) {
1443 1444 1445
		ret = find_first_extent_bit(unpin, 0, &start, &end,
					    EXTENT_DIRTY);
		if (ret)
1446
			break;
1447
		update_pinned_extents(root, start, end + 1 - start, 0);
1448 1449
		clear_extent_dirty(unpin, start, end, GFP_NOFS);
		set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1450 1451 1452 1453 1454
		if (need_resched()) {
			mutex_unlock(&root->fs_info->alloc_mutex);
			cond_resched();
			mutex_lock(&root->fs_info->alloc_mutex);
		}
1455
	}
1456
	mutex_unlock(&root->fs_info->alloc_mutex);
1457 1458 1459
	return 0;
}

1460 1461
static int finish_current_insert(struct btrfs_trans_handle *trans,
				 struct btrfs_root *extent_root)
C
Chris Mason 已提交
1462
{
1463 1464 1465
	u64 start;
	u64 end;
	struct btrfs_fs_info *info = extent_root->fs_info;
1466
	struct extent_buffer *eb;
1467
	struct btrfs_path *path;
C
Chris Mason 已提交
1468
	struct btrfs_key ins;
1469
	struct btrfs_disk_key first;
C
Chris Mason 已提交
1470
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
1471
	int ret;
1472
	int level;
1473
	int err = 0;
C
Chris Mason 已提交
1474

1475
	WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
1476
	btrfs_set_stack_extent_refs(&extent_item, 1);
1477
	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1478
	path = btrfs_alloc_path();
C
Chris Mason 已提交
1479

1480
	while(1) {
1481 1482 1483
		ret = find_first_extent_bit(&info->extent_ins, 0, &start,
					    &end, EXTENT_LOCKED);
		if (ret)
1484 1485
			break;

1486 1487 1488 1489 1490 1491
		ins.objectid = start;
		ins.offset = end + 1 - start;
		err = btrfs_insert_item(trans, extent_root, &ins,
					&extent_item, sizeof(extent_item));
		clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
				  GFP_NOFS);
1492 1493 1494 1495 1496 1497 1498 1499 1500 1501

		eb = btrfs_find_tree_block(extent_root, ins.objectid,
					   ins.offset);

		if (!btrfs_buffer_uptodate(eb, trans->transid)) {
			mutex_unlock(&extent_root->fs_info->alloc_mutex);
			btrfs_read_buffer(eb, trans->transid);
			mutex_lock(&extent_root->fs_info->alloc_mutex);
		}

1502
		btrfs_tree_lock(eb);
1503 1504 1505 1506 1507 1508
		level = btrfs_header_level(eb);
		if (level == 0) {
			btrfs_item_key(eb, &first, 0);
		} else {
			btrfs_node_key(eb, &first, 0);
		}
1509 1510 1511 1512 1513 1514
		btrfs_tree_unlock(eb);
		free_extent_buffer(eb);
		/*
		 * the first key is just a hint, so the race we've created
		 * against reading it is fine
		 */
1515 1516
		err = btrfs_insert_extent_backref(trans, extent_root, path,
					  start, extent_root->root_key.objectid,
1517 1518
					  0, level,
					  btrfs_disk_key_objectid(&first));
1519
		BUG_ON(err);
1520 1521 1522 1523 1524
		if (need_resched()) {
			mutex_unlock(&extent_root->fs_info->alloc_mutex);
			cond_resched();
			mutex_lock(&extent_root->fs_info->alloc_mutex);
		}
C
Chris Mason 已提交
1525
	}
1526
	btrfs_free_path(path);
C
Chris Mason 已提交
1527 1528 1529
	return 0;
}

1530 1531
static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
			  int pending)
C
Chris Mason 已提交
1532
{
1533
	int err = 0;
C
Chris Mason 已提交
1534

1535
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
C
Chris Mason 已提交
1536
	if (!pending) {
1537
		struct extent_buffer *buf;
1538
		buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1539
		if (buf) {
1540 1541
			if (btrfs_buffer_uptodate(buf, 0) &&
			    btrfs_try_tree_lock(buf)) {
C
Chris Mason 已提交
1542 1543
				u64 transid =
				    root->fs_info->running_transaction->transid;
C
Chris Mason 已提交
1544 1545
				u64 header_transid =
					btrfs_header_generation(buf);
1546 1547 1548
				if (header_transid == transid &&
				    !btrfs_header_flag(buf,
					       BTRFS_HEADER_FLAG_WRITTEN)) {
1549
					clean_tree_block(NULL, root, buf);
1550
					btrfs_tree_unlock(buf);
1551
					free_extent_buffer(buf);
1552
					return 1;
C
Chris Mason 已提交
1553
				}
1554
				btrfs_tree_unlock(buf);
C
Chris Mason 已提交
1555
			}
1556
			free_extent_buffer(buf);
C
Chris Mason 已提交
1557
		}
1558
		update_pinned_extents(root, bytenr, num_bytes, 1);
C
Chris Mason 已提交
1559
	} else {
1560
		set_extent_bits(&root->fs_info->pending_del,
1561 1562
				bytenr, bytenr + num_bytes - 1,
				EXTENT_LOCKED, GFP_NOFS);
C
Chris Mason 已提交
1563
	}
C
Chris Mason 已提交
1564
	BUG_ON(err < 0);
C
Chris Mason 已提交
1565 1566 1567
	return 0;
}

1568
/*
1569
 * remove an extent from the root, returns 0 on success
1570
 */
1571
static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1572 1573 1574
			 *root, u64 bytenr, u64 num_bytes,
			 u64 root_objectid, u64 ref_generation,
			 u64 owner_objectid, u64 owner_offset, int pin,
1575
			 int mark_free)
1576
{
1577
	struct btrfs_path *path;
C
Chris Mason 已提交
1578
	struct btrfs_key key;
1579 1580
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
1581
	struct extent_buffer *leaf;
1582
	int ret;
1583 1584 1585
	int extent_slot = 0;
	int found_extent = 0;
	int num_to_del = 1;
C
Chris Mason 已提交
1586
	struct btrfs_extent_item *ei;
C
Chris Mason 已提交
1587
	u32 refs;
C
Chris Mason 已提交
1588

1589
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1590
	key.objectid = bytenr;
1591
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1592
	key.offset = num_bytes;
1593
	path = btrfs_alloc_path();
1594 1595
	if (!path)
		return -ENOMEM;
1596

1597
	path->reada = 1;
1598 1599 1600 1601 1602
	ret = lookup_extent_backref(trans, extent_root, path,
				    bytenr, root_objectid,
				    ref_generation,
				    owner_objectid, owner_offset, 1);
	if (ret == 0) {
1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620
		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;
		}
		if (!found_extent)
			ret = btrfs_del_item(trans, extent_root, path);
1621 1622 1623 1624 1625 1626 1627 1628
	} else {
		btrfs_print_leaf(extent_root, path->nodes[0]);
		WARN_ON(1);
		printk("Unable to find ref byte nr %Lu root %Lu "
		       " gen %Lu owner %Lu offset %Lu\n", bytenr,
		       root_objectid, ref_generation, owner_objectid,
		       owner_offset);
	}
1629 1630 1631 1632 1633 1634 1635 1636
	if (!found_extent) {
		btrfs_release_path(extent_root, path);
		ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
		if (ret < 0)
			return ret;
		BUG_ON(ret);
		extent_slot = path->slots[0];
	}
1637 1638

	leaf = path->nodes[0];
1639
	ei = btrfs_item_ptr(leaf, extent_slot,
C
Chris Mason 已提交
1640
			    struct btrfs_extent_item);
1641 1642 1643 1644
	refs = btrfs_extent_refs(leaf, ei);
	BUG_ON(refs == 0);
	refs -= 1;
	btrfs_set_extent_refs(leaf, ei, refs);
1645

1646 1647
	btrfs_mark_buffer_dirty(leaf);

1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668
	if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
		/* 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 */
		ret = btrfs_del_item(trans, extent_root, path);
		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);
			if (ret < 0)
				return ret;
			BUG_ON(ret);
		}
	}

C
Chris Mason 已提交
1669
	if (refs == 0) {
1670 1671
		u64 super_used;
		u64 root_used;
C
Chris Mason 已提交
1672 1673

		if (pin) {
1674
			ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1675 1676 1677
			if (ret > 0)
				mark_free = 1;
			BUG_ON(ret < 0);
C
Chris Mason 已提交
1678 1679
		}

1680
		/* block accounting for super block */
1681
		spin_lock_irq(&info->delalloc_lock);
1682 1683 1684
		super_used = btrfs_super_bytes_used(&info->super_copy);
		btrfs_set_super_bytes_used(&info->super_copy,
					   super_used - num_bytes);
1685
		spin_unlock_irq(&info->delalloc_lock);
1686 1687

		/* block accounting for root item */
1688
		root_used = btrfs_root_used(&root->root_item);
1689
		btrfs_set_root_used(&root->root_item,
1690
					   root_used - num_bytes);
1691 1692
		ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
				      num_to_del);
1693 1694 1695
		if (ret) {
			return ret;
		}
1696
		ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1697
					 mark_free);
C
Chris Mason 已提交
1698
		BUG_ON(ret);
1699
	}
1700
	btrfs_free_path(path);
1701
	finish_current_insert(trans, extent_root);
1702 1703 1704 1705 1706 1707 1708
	return ret;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
1709 1710
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root)
1711 1712
{
	int ret;
C
Chris Mason 已提交
1713
	int err = 0;
1714 1715
	u64 start;
	u64 end;
1716 1717
	struct extent_io_tree *pending_del;
	struct extent_io_tree *pinned_extents;
C
Chris Mason 已提交
1718

1719
	WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
1720 1721
	pending_del = &extent_root->fs_info->pending_del;
	pinned_extents = &extent_root->fs_info->pinned_extents;
1722 1723

	while(1) {
1724 1725 1726
		ret = find_first_extent_bit(pending_del, 0, &start, &end,
					    EXTENT_LOCKED);
		if (ret)
1727
			break;
1728 1729
		clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
				  GFP_NOFS);
1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741
		if (!test_range_bit(&extent_root->fs_info->extent_ins,
				    start, end, EXTENT_LOCKED, 0)) {
			update_pinned_extents(extent_root, start,
					      end + 1 - start, 1);
			ret = __free_extent(trans, extent_root,
					     start, end + 1 - start,
					     extent_root->root_key.objectid,
					     0, 0, 0, 0, 0);
		} else {
			clear_extent_bits(&extent_root->fs_info->extent_ins,
					  start, end, EXTENT_LOCKED, GFP_NOFS);
		}
1742 1743
		if (ret)
			err = ret;
1744 1745 1746 1747 1748 1749

		if (need_resched()) {
			mutex_unlock(&extent_root->fs_info->alloc_mutex);
			cond_resched();
			mutex_lock(&extent_root->fs_info->alloc_mutex);
		}
1750
	}
C
Chris Mason 已提交
1751
	return err;
1752 1753 1754 1755 1756
}

/*
 * remove an extent from the root, returns 0 on success
 */
1757 1758 1759 1760 1761
static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root, u64 bytenr,
			       u64 num_bytes, u64 root_objectid,
			       u64 ref_generation, u64 owner_objectid,
			       u64 owner_offset, int pin)
1762
{
1763
	struct btrfs_root *extent_root = root->fs_info->extent_root;
1764 1765
	int pending_ret;
	int ret;
1766

1767
	WARN_ON(num_bytes < root->sectorsize);
1768 1769 1770
	if (!root->ref_cows)
		ref_generation = 0;

1771
	if (root == extent_root) {
1772
		pin_down_bytes(root, bytenr, num_bytes, 1);
1773 1774
		return 0;
	}
1775 1776 1777
	ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
			    ref_generation, owner_objectid, owner_offset,
			    pin, pin == 0);
1778 1779

	finish_current_insert(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
1780
	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1781 1782 1783
	return ret ? ret : pending_ret;
}

1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799
int btrfs_free_extent(struct btrfs_trans_handle *trans,
		      struct btrfs_root *root, u64 bytenr,
		      u64 num_bytes, u64 root_objectid,
		      u64 ref_generation, u64 owner_objectid,
		      u64 owner_offset, int pin)
{
	int ret;

	maybe_lock_mutex(root);
	ret = __btrfs_free_extent(trans, root, bytenr, num_bytes,
				  root_objectid, ref_generation,
				  owner_objectid, owner_offset, pin);
	maybe_unlock_mutex(root);
	return ret;
}

1800 1801 1802 1803 1804 1805 1806
static u64 stripe_align(struct btrfs_root *root, u64 val)
{
	u64 mask = ((u64)root->stripesize - 1);
	u64 ret = (val + mask) & ~mask;
	return ret;
}

1807 1808 1809 1810
/*
 * 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
1811
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
1812 1813 1814
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
1815 1816 1817 1818 1819 1820 1821
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)
1822
{
1823
	int ret;
1824
	u64 orig_search_start;
1825
	struct btrfs_root * root = orig_root->fs_info->extent_root;
1826
	struct btrfs_fs_info *info = root->fs_info;
1827
	u64 total_needed = num_bytes;
1828
	u64 *last_ptr = NULL;
C
Chris Mason 已提交
1829
	struct btrfs_block_group_cache *block_group;
C
Chris Mason 已提交
1830
	int full_scan = 0;
1831
	int wrapped = 0;
C
Chris Mason 已提交
1832
	int chunk_alloc_done = 0;
1833
	int empty_cluster = 2 * 1024 * 1024;
C
Chris Mason 已提交
1834
	int allowed_chunk_alloc = 0;
1835

1836
	WARN_ON(num_bytes < root->sectorsize);
1837 1838
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);

C
Chris Mason 已提交
1839 1840 1841
	if (orig_root->ref_cows || empty_size)
		allowed_chunk_alloc = 1;

1842 1843
	if (data & BTRFS_BLOCK_GROUP_METADATA) {
		last_ptr = &root->fs_info->last_alloc;
1844
		empty_cluster = 256 * 1024;
1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858
	}

	if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
		last_ptr = &root->fs_info->last_data_alloc;
	}

	if (last_ptr) {
		if (*last_ptr)
			hint_byte = *last_ptr;
		else {
			empty_size += empty_cluster;
		}
	}

1859 1860 1861
	search_start = max(search_start, first_logical_byte(root, 0));
	orig_search_start = search_start;

1862 1863
	if (search_end == (u64)-1)
		search_end = btrfs_super_total_bytes(&info->super_copy);
1864

1865
	if (hint_byte) {
C
Chris Mason 已提交
1866
		block_group = btrfs_lookup_first_block_group(info, hint_byte);
1867 1868
		if (!block_group)
			hint_byte = search_start;
1869
		block_group = btrfs_find_block_group(root, block_group,
1870
						     hint_byte, data, 1);
1871 1872
		if (last_ptr && *last_ptr == 0 && block_group)
			hint_byte = block_group->key.objectid;
C
Chris Mason 已提交
1873
	} else {
1874
		block_group = btrfs_find_block_group(root,
1875 1876
						     trans->block_group,
						     search_start, data, 1);
C
Chris Mason 已提交
1877
	}
1878
	search_start = max(search_start, hint_byte);
C
Chris Mason 已提交
1879

1880
	total_needed += empty_size;
1881

C
Chris Mason 已提交
1882
check_failed:
1883
	if (!block_group) {
C
Chris Mason 已提交
1884 1885
		block_group = btrfs_lookup_first_block_group(info,
							     search_start);
1886
		if (!block_group)
C
Chris Mason 已提交
1887
			block_group = btrfs_lookup_first_block_group(info,
1888 1889
						       orig_search_start);
	}
C
Chris Mason 已提交
1890 1891 1892 1893 1894 1895 1896 1897 1898 1899
	if (full_scan && !chunk_alloc_done) {
		if (allowed_chunk_alloc) {
			do_chunk_alloc(trans, root,
				     num_bytes + 2 * 1024 * 1024, data, 1);
			allowed_chunk_alloc = 0;
		} else if (block_group && block_group_bits(block_group, data)) {
			block_group->space_info->force_alloc = 1;
		}
		chunk_alloc_done = 1;
	}
1900 1901
	ret = find_search_start(root, &block_group, &search_start,
				total_needed, data);
1902 1903
	if (ret == -ENOSPC && last_ptr && *last_ptr) {
		*last_ptr = 0;
C
Chris Mason 已提交
1904 1905
		block_group = btrfs_lookup_first_block_group(info,
							     orig_search_start);
1906 1907 1908 1909 1910 1911
		search_start = orig_search_start;
		ret = find_search_start(root, &block_group, &search_start,
					total_needed, data);
	}
	if (ret == -ENOSPC)
		goto enospc;
1912
	if (ret)
1913
		goto error;
1914

1915 1916 1917 1918 1919 1920
	if (last_ptr && *last_ptr && search_start != *last_ptr) {
		*last_ptr = 0;
		if (!empty_size) {
			empty_size += empty_cluster;
			total_needed += empty_size;
		}
C
Chris Mason 已提交
1921
		block_group = btrfs_lookup_first_block_group(info,
1922 1923 1924 1925 1926 1927 1928 1929 1930 1931
						       orig_search_start);
		search_start = orig_search_start;
		ret = find_search_start(root, &block_group,
					&search_start, total_needed, data);
		if (ret == -ENOSPC)
			goto enospc;
		if (ret)
			goto error;
	}

1932 1933 1934
	search_start = stripe_align(root, search_start);
	ins->objectid = search_start;
	ins->offset = num_bytes;
1935

1936
	if (ins->objectid + num_bytes >= search_end)
1937
		goto enospc;
1938 1939 1940

	if (ins->objectid + num_bytes >
	    block_group->key.objectid + block_group->key.offset) {
1941 1942 1943 1944
		search_start = block_group->key.objectid +
			block_group->key.offset;
		goto new_group;
	}
1945

1946
	if (test_range_bit(&info->extent_ins, ins->objectid,
1947 1948
			   ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
		search_start = ins->objectid + num_bytes;
1949 1950
		goto new_group;
	}
1951

1952
	if (test_range_bit(&info->pinned_extents, ins->objectid,
1953 1954
			   ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
		search_start = ins->objectid + num_bytes;
1955
		goto new_group;
1956
	}
1957

1958
	if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1959 1960 1961 1962
	    ins->objectid < exclude_start + exclude_nr)) {
		search_start = exclude_start + exclude_nr;
		goto new_group;
	}
1963

1964
	if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
1965
		block_group = btrfs_lookup_block_group(info, ins->objectid);
1966 1967
		if (block_group)
			trans->block_group = block_group;
1968
	}
1969
	ins->offset = num_bytes;
1970 1971 1972 1973 1974 1975 1976
	if (last_ptr) {
		*last_ptr = ins->objectid + ins->offset;
		if (*last_ptr ==
		    btrfs_super_total_bytes(&root->fs_info->super_copy)) {
			*last_ptr = 0;
		}
	}
1977
	return 0;
C
Chris Mason 已提交
1978 1979

new_group:
1980
	if (search_start + num_bytes >= search_end) {
1981
enospc:
C
Chris Mason 已提交
1982
		search_start = orig_search_start;
1983 1984 1985 1986
		if (full_scan) {
			ret = -ENOSPC;
			goto error;
		}
1987 1988 1989
		if (wrapped) {
			if (!full_scan)
				total_needed -= empty_size;
1990
			full_scan = 1;
1991
		} else
1992
			wrapped = 1;
C
Chris Mason 已提交
1993
	}
C
Chris Mason 已提交
1994
	block_group = btrfs_lookup_first_block_group(info, search_start);
1995
	cond_resched();
1996
	block_group = btrfs_find_block_group(root, block_group,
1997
					     search_start, data, 0);
C
Chris Mason 已提交
1998 1999
	goto check_failed;

C
Chris Mason 已提交
2000 2001
error:
	return ret;
2002
}
2003

2004 2005 2006 2007 2008 2009
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)
2010 2011
{
	int ret;
2012
	u64 search_start = 0;
2013
	u64 alloc_profile;
2014
	struct btrfs_fs_info *info = root->fs_info;
2015

2016
	if (data) {
2017 2018 2019
		alloc_profile = info->avail_data_alloc_bits &
			        info->data_alloc_profile;
		data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2020
	} else if (root == root->fs_info->chunk_root) {
2021 2022 2023
		alloc_profile = info->avail_system_alloc_bits &
			        info->system_alloc_profile;
		data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2024
	} else {
2025 2026 2027
		alloc_profile = info->avail_metadata_alloc_bits &
			        info->metadata_alloc_profile;
		data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2028
	}
2029
again:
2030
	data = reduce_alloc_profile(root, data);
C
Chris Mason 已提交
2031 2032 2033 2034 2035
	/*
	 * the only place that sets empty_size is btrfs_realloc_node, which
	 * is not called recursively on allocations
	 */
	if (empty_size || root->ref_cows) {
2036
		if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2037
			ret = do_chunk_alloc(trans, root->fs_info->extent_root,
C
Chris Mason 已提交
2038 2039 2040 2041
				     2 * 1024 * 1024,
				     BTRFS_BLOCK_GROUP_METADATA |
				     (info->metadata_alloc_profile &
				      info->avail_metadata_alloc_bits), 0);
2042 2043 2044
			BUG_ON(ret);
		}
		ret = do_chunk_alloc(trans, root->fs_info->extent_root,
C
Chris Mason 已提交
2045
				     num_bytes + 2 * 1024 * 1024, data, 0);
2046 2047
		BUG_ON(ret);
	}
2048

2049 2050 2051
	WARN_ON(num_bytes < root->sectorsize);
	ret = find_free_extent(trans, root, num_bytes, empty_size,
			       search_start, search_end, hint_byte, ins,
2052 2053
			       trans->alloc_exclude_start,
			       trans->alloc_exclude_nr, data);
2054

2055 2056 2057
	if (ret == -ENOSPC && num_bytes > min_alloc_size) {
		num_bytes = num_bytes >> 1;
		num_bytes = max(num_bytes, min_alloc_size);
C
Chris Mason 已提交
2058 2059
		do_chunk_alloc(trans, root->fs_info->extent_root,
			       num_bytes, data, 1);
2060 2061
		goto again;
	}
2062 2063
	if (ret) {
		printk("allocation failed flags %Lu\n", data);
2064 2065
		BUG();
	}
2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105
	clear_extent_dirty(&root->fs_info->free_space_cache,
			   ins->objectid, ins->objectid + ins->offset - 1,
			   GFP_NOFS);
	return 0;
}

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);
	maybe_unlock_mutex(root);
	return ret;
}

static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
					 struct btrfs_root *root,
					 u64 root_objectid, u64 ref_generation,
					 u64 owner, u64 owner_offset,
					 struct btrfs_key *ins)
{
	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];
2106

2107
	/* block accounting for super block */
2108
	spin_lock_irq(&info->delalloc_lock);
2109 2110
	super_used = btrfs_super_bytes_used(&info->super_copy);
	btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
2111
	spin_unlock_irq(&info->delalloc_lock);
2112

2113
	/* block accounting for root item */
2114 2115
	root_used = btrfs_root_used(&root->root_item);
	btrfs_set_root_used(&root->root_item, root_used + num_bytes);
2116

2117
	if (root == extent_root) {
2118 2119 2120
		set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
				ins->objectid + ins->offset - 1,
				EXTENT_LOCKED, GFP_NOFS);
2121 2122 2123
		goto update_block;
	}

2124 2125 2126 2127 2128 2129 2130
	memcpy(&keys[0], ins, sizeof(*ins));
	keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
					 owner, owner_offset);
	keys[1].objectid = ins->objectid;
	keys[1].type = BTRFS_EXTENT_REF_KEY;
	sizes[0] = sizeof(*extent_item);
	sizes[1] = sizeof(*ref);
2131 2132 2133

	path = btrfs_alloc_path();
	BUG_ON(!path);
2134 2135 2136

	ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
				       sizes, 2);
2137

C
Chris Mason 已提交
2138
	BUG_ON(ret);
2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153
	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);
	btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);

	btrfs_mark_buffer_dirty(path->nodes[0]);

	trans->alloc_exclude_start = 0;
	trans->alloc_exclude_nr = 0;
2154
	btrfs_free_path(path);
2155
	finish_current_insert(trans, extent_root);
C
Chris Mason 已提交
2156
	pending_ret = del_pending_extents(trans, extent_root);
2157

2158 2159
	if (ret)
		goto out;
2160
	if (pending_ret) {
2161 2162
		ret = pending_ret;
		goto out;
2163
	}
2164 2165

update_block:
2166
	ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
2167 2168 2169 2170 2171
	if (ret) {
		printk("update block group failed for %Lu %Lu\n",
		       ins->objectid, ins->offset);
		BUG();
	}
2172
out:
2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217
	return ret;
}

int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
				struct btrfs_root *root,
				u64 root_objectid, u64 ref_generation,
				u64 owner, u64 owner_offset,
				struct btrfs_key *ins)
{
	int ret;
	maybe_lock_mutex(root);
	ret = __btrfs_alloc_reserved_extent(trans, root, root_objectid,
					    ref_generation, owner,
					    owner_offset, ins);
	maybe_unlock_mutex(root);
	return ret;
}
/*
 * 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,
		       u64 num_bytes, u64 min_alloc_size,
		       u64 root_objectid, u64 ref_generation,
		       u64 owner, u64 owner_offset,
		       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);
	BUG_ON(ret);
	ret = __btrfs_alloc_reserved_extent(trans, root, root_objectid,
					    ref_generation, owner,
					    owner_offset, ins);
	BUG_ON(ret);

2218 2219
	maybe_unlock_mutex(root);
	return ret;
2220 2221 2222 2223 2224
}
/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
2225
struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2226 2227 2228 2229 2230 2231 2232
					     struct btrfs_root *root,
					     u32 blocksize,
					     u64 root_objectid,
					     u64 ref_generation,
					     u64 first_objectid,
					     int level,
					     u64 hint,
2233
					     u64 empty_size)
2234
{
C
Chris Mason 已提交
2235
	struct btrfs_key ins;
2236
	int ret;
2237
	struct extent_buffer *buf;
2238

2239
	ret = btrfs_alloc_extent(trans, root, blocksize, blocksize,
2240
				 root_objectid, ref_generation,
2241
				 level, first_objectid, empty_size, hint,
2242
				 (u64)-1, &ins, 0);
2243
	if (ret) {
2244 2245
		BUG_ON(ret > 0);
		return ERR_PTR(ret);
2246
	}
2247
	buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
2248
	if (!buf) {
2249 2250 2251
		btrfs_free_extent(trans, root, ins.objectid, blocksize,
				  root->root_key.objectid, ref_generation,
				  0, 0, 0);
2252 2253
		return ERR_PTR(-ENOMEM);
	}
2254
	btrfs_set_header_generation(buf, trans->transid);
2255
	btrfs_tree_lock(buf);
2256
	clean_tree_block(trans, root, buf);
2257
	btrfs_set_buffer_uptodate(buf);
2258 2259 2260 2261 2262 2263

	if (PageDirty(buf->first_page)) {
		printk("page %lu dirty\n", buf->first_page->index);
		WARN_ON(1);
	}

2264 2265
	set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
			 buf->start + buf->len - 1, GFP_NOFS);
2266
	trans->blocks_used++;
2267 2268
	return buf;
}
2269

Y
Yan Zheng 已提交
2270 2271 2272
static int noinline drop_leaf_ref_no_cache(struct btrfs_trans_handle *trans,
				  	   struct btrfs_root *root,
					   struct extent_buffer *leaf)
2273
{
2274 2275
	u64 leaf_owner;
	u64 leaf_generation;
2276
	struct btrfs_key key;
2277 2278 2279 2280 2281
	struct btrfs_file_extent_item *fi;
	int i;
	int nritems;
	int ret;

2282 2283
	BUG_ON(!btrfs_is_leaf(leaf));
	nritems = btrfs_header_nritems(leaf);
2284 2285 2286
	leaf_owner = btrfs_header_owner(leaf);
	leaf_generation = btrfs_header_generation(leaf);

C
Chris Mason 已提交
2287 2288
	mutex_unlock(&root->fs_info->alloc_mutex);

2289
	for (i = 0; i < nritems; i++) {
2290
		u64 disk_bytenr;
2291
		cond_resched();
2292 2293 2294

		btrfs_item_key_to_cpu(leaf, &key, i);
		if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2295 2296
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2297 2298
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
2299
			continue;
2300 2301 2302 2303
		/*
		 * FIXME make sure to insert a trans record that
		 * repeats the snapshot del on crash
		 */
2304 2305
		disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
		if (disk_bytenr == 0)
C
Chris Mason 已提交
2306
			continue;
C
Chris Mason 已提交
2307 2308

		mutex_lock(&root->fs_info->alloc_mutex);
2309
		ret = __btrfs_free_extent(trans, root, disk_bytenr,
2310 2311 2312
				btrfs_file_extent_disk_num_bytes(leaf, fi),
				leaf_owner, leaf_generation,
				key.objectid, key.offset, 0);
C
Chris Mason 已提交
2313
		mutex_unlock(&root->fs_info->alloc_mutex);
2314 2315
		BUG_ON(ret);
	}
C
Chris Mason 已提交
2316 2317

	mutex_lock(&root->fs_info->alloc_mutex);
2318 2319 2320
	return 0;
}

Y
Yan Zheng 已提交
2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344
static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
				  	 struct btrfs_root *root,
					 struct btrfs_leaf_ref *ref)
{
	int i;
	int ret;
	struct btrfs_extent_info *info = ref->extents;

	mutex_unlock(&root->fs_info->alloc_mutex);
	for (i = 0; i < ref->nritems; i++) {
		mutex_lock(&root->fs_info->alloc_mutex);
		ret = __btrfs_free_extent(trans, root,
					info->bytenr, info->num_bytes,
					ref->owner, ref->generation,
					info->objectid, info->offset, 0);
		mutex_unlock(&root->fs_info->alloc_mutex);
		BUG_ON(ret);
		info++;
	}
	mutex_lock(&root->fs_info->alloc_mutex);

	return 0;
}

2345
static void noinline reada_walk_down(struct btrfs_root *root,
2346 2347
				     struct extent_buffer *node,
				     int slot)
2348
{
2349
	u64 bytenr;
2350 2351
	u64 last = 0;
	u32 nritems;
2352
	u32 refs;
2353
	u32 blocksize;
2354 2355 2356 2357
	int ret;
	int i;
	int level;
	int skipped = 0;
2358

2359
	nritems = btrfs_header_nritems(node);
2360
	level = btrfs_header_level(node);
2361 2362 2363 2364
	if (level)
		return;

	for (i = slot; i < nritems && skipped < 32; i++) {
2365
		bytenr = btrfs_node_blockptr(node, i);
2366 2367 2368
		if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
			     (last > bytenr && last - bytenr > 32 * 1024))) {
			skipped++;
2369
			continue;
2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380
		}
		blocksize = btrfs_level_size(root, level - 1);
		if (i != slot) {
			ret = lookup_extent_ref(NULL, root, bytenr,
						blocksize, &refs);
			BUG_ON(ret);
			if (refs != 1) {
				skipped++;
				continue;
			}
		}
2381 2382
		ret = readahead_tree_block(root, bytenr, blocksize,
					   btrfs_node_ptr_generation(node, i));
2383
		last = bytenr + blocksize;
2384
		cond_resched();
2385 2386 2387 2388 2389
		if (ret)
			break;
	}
}

2390 2391 2392 2393 2394 2395 2396 2397 2398 2399
/*
 * we want to avoid as much random IO as we can with the alloc mutex
 * held, so drop the lock and do the lookup, then do it again with the
 * lock held.
 */
int drop_snap_lookup_refcount(struct btrfs_root *root, u64 start, u64 len,
			      u32 *refs)
{
	mutex_unlock(&root->fs_info->alloc_mutex);
	lookup_extent_ref(NULL, root, start, len, refs);
2400
	cond_resched();
2401 2402 2403 2404
	mutex_lock(&root->fs_info->alloc_mutex);
	return lookup_extent_ref(NULL, root, start, len, refs);
}

C
Chris Mason 已提交
2405 2406 2407 2408
/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
2409 2410 2411
static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct btrfs_path *path, int *level)
C
Chris Mason 已提交
2412
{
2413 2414 2415
	u64 root_owner;
	u64 root_gen;
	u64 bytenr;
2416
	u64 ptr_gen;
2417 2418
	struct extent_buffer *next;
	struct extent_buffer *cur;
2419
	struct extent_buffer *parent;
Y
Yan Zheng 已提交
2420
	struct btrfs_leaf_ref *ref;
2421
	u32 blocksize;
C
Chris Mason 已提交
2422 2423 2424
	int ret;
	u32 refs;

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

2427 2428
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
2429
	ret = drop_snap_lookup_refcount(root, path->nodes[*level]->start,
2430
				path->nodes[*level]->len, &refs);
C
Chris Mason 已提交
2431 2432 2433
	BUG_ON(ret);
	if (refs > 1)
		goto out;
2434

C
Chris Mason 已提交
2435 2436 2437
	/*
	 * walk down to the last node level and free all the leaves
	 */
2438
	while(*level >= 0) {
2439 2440
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
2441
		cur = path->nodes[*level];
2442

2443
		if (btrfs_header_level(cur) != *level)
C
Chris Mason 已提交
2444
			WARN_ON(1);
2445

2446
		if (path->slots[*level] >=
2447
		    btrfs_header_nritems(cur))
C
Chris Mason 已提交
2448
			break;
2449
		if (*level == 0) {
Y
Yan Zheng 已提交
2450
			ret = drop_leaf_ref_no_cache(trans, root, cur);
2451 2452 2453
			BUG_ON(ret);
			break;
		}
2454
		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2455
		ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2456
		blocksize = btrfs_level_size(root, *level - 1);
2457

2458
		ret = drop_snap_lookup_refcount(root, bytenr, blocksize, &refs);
2459 2460
		BUG_ON(ret);
		if (refs != 1) {
2461 2462 2463
			parent = path->nodes[*level];
			root_owner = btrfs_header_owner(parent);
			root_gen = btrfs_header_generation(parent);
C
Chris Mason 已提交
2464
			path->slots[*level]++;
2465
			ret = __btrfs_free_extent(trans, root, bytenr,
2466 2467
						blocksize, root_owner,
						root_gen, 0, 0, 1);
C
Chris Mason 已提交
2468 2469 2470
			BUG_ON(ret);
			continue;
		}
Y
Yan Zheng 已提交
2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485
		
		if (*level == 1) {
			struct btrfs_key key;
			btrfs_node_key_to_cpu(cur, &key, path->slots[*level]);
			ref = btrfs_lookup_leaf_ref(root, &key);
			if (ref) {
				ret = drop_leaf_ref(trans, root, ref);
				BUG_ON(ret);
				btrfs_remove_leaf_ref(root, ref);
				btrfs_free_leaf_ref(ref);
				*level = 0;
				break;
			}
		}

2486
		next = btrfs_find_tree_block(root, bytenr, blocksize);
2487
		if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
2488
			free_extent_buffer(next);
2489 2490
			mutex_unlock(&root->fs_info->alloc_mutex);

2491 2492
			if (path->slots[*level] == 0)
				reada_walk_down(root, cur, path->slots[*level]);
2493 2494
			next = read_tree_block(root, bytenr, blocksize,
					       ptr_gen);
2495
			cond_resched();
2496
			mutex_lock(&root->fs_info->alloc_mutex);
2497

2498
			/* we've dropped the lock, double check */
2499 2500
			ret = lookup_extent_ref(NULL, root, bytenr, blocksize,
						&refs);
2501 2502
			BUG_ON(ret);
			if (refs != 1) {
2503 2504 2505 2506
				parent = path->nodes[*level];
				root_owner = btrfs_header_owner(parent);
				root_gen = btrfs_header_generation(parent);

2507
				path->slots[*level]++;
2508
				free_extent_buffer(next);
2509
				ret = __btrfs_free_extent(trans, root, bytenr,
2510 2511 2512
							blocksize,
							root_owner,
							root_gen, 0, 0, 1);
2513 2514 2515 2516
				BUG_ON(ret);
				continue;
			}
		}
2517
		WARN_ON(*level <= 0);
C
Chris Mason 已提交
2518
		if (path->nodes[*level-1])
2519
			free_extent_buffer(path->nodes[*level-1]);
C
Chris Mason 已提交
2520
		path->nodes[*level-1] = next;
2521
		*level = btrfs_header_level(next);
C
Chris Mason 已提交
2522 2523 2524
		path->slots[*level] = 0;
	}
out:
2525 2526
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
2527 2528 2529

	if (path->nodes[*level] == root->node) {
		parent = path->nodes[*level];
Y
Yan Zheng 已提交
2530
		bytenr = path->nodes[*level]->start;
2531 2532
	} else {
		parent = path->nodes[*level + 1];
Y
Yan Zheng 已提交
2533
		bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
2534 2535
	}

Y
Yan Zheng 已提交
2536 2537
	blocksize = btrfs_level_size(root, *level);
	root_owner = btrfs_header_owner(parent);
2538
	root_gen = btrfs_header_generation(parent);
Y
Yan Zheng 已提交
2539 2540 2541

	ret = __btrfs_free_extent(trans, root, bytenr, blocksize,
				  root_owner, root_gen, 0, 0, 1);
2542
	free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
2543 2544 2545
	path->nodes[*level] = NULL;
	*level += 1;
	BUG_ON(ret);
2546
	mutex_unlock(&root->fs_info->alloc_mutex);
2547
	cond_resched();
C
Chris Mason 已提交
2548 2549 2550
	return 0;
}

C
Chris Mason 已提交
2551 2552 2553 2554 2555
/*
 * 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
 */
2556 2557 2558
static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
				 struct btrfs_root *root,
				 struct btrfs_path *path, int *level)
C
Chris Mason 已提交
2559
{
2560 2561 2562
	u64 root_owner;
	u64 root_gen;
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
2563 2564 2565
	int i;
	int slot;
	int ret;
2566

C
Chris Mason 已提交
2567
	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
C
Chris Mason 已提交
2568
		slot = path->slots[i];
2569 2570 2571 2572
		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 已提交
2573 2574
			path->slots[i]++;
			*level = i;
2575
			WARN_ON(*level == 0);
2576
			btrfs_node_key(node, &disk_key, path->slots[i]);
2577
			memcpy(&root_item->drop_progress,
2578
			       &disk_key, sizeof(disk_key));
2579
			root_item->drop_level = i;
C
Chris Mason 已提交
2580 2581
			return 0;
		} else {
2582 2583 2584 2585 2586 2587 2588 2589 2590 2591
			if (path->nodes[*level] == root->node) {
				root_owner = root->root_key.objectid;
				root_gen =
				   btrfs_header_generation(path->nodes[*level]);
			} else {
				struct extent_buffer *node;
				node = path->nodes[*level + 1];
				root_owner = btrfs_header_owner(node);
				root_gen = btrfs_header_generation(node);
			}
2592
			ret = btrfs_free_extent(trans, root,
2593
						path->nodes[*level]->start,
2594 2595
						path->nodes[*level]->len,
						root_owner, root_gen, 0, 0, 1);
2596
			BUG_ON(ret);
2597
			free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
2598
			path->nodes[*level] = NULL;
C
Chris Mason 已提交
2599 2600 2601 2602 2603 2604
			*level = i + 1;
		}
	}
	return 1;
}

C
Chris Mason 已提交
2605 2606 2607 2608 2609
/*
 * 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.
 */
2610
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2611
			*root)
C
Chris Mason 已提交
2612
{
2613
	int ret = 0;
C
Chris Mason 已提交
2614
	int wret;
C
Chris Mason 已提交
2615
	int level;
2616
	struct btrfs_path *path;
C
Chris Mason 已提交
2617 2618
	int i;
	int orig_level;
2619
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
2620

2621
	WARN_ON(!mutex_is_locked(&root->fs_info->drop_mutex));
2622 2623
	path = btrfs_alloc_path();
	BUG_ON(!path);
C
Chris Mason 已提交
2624

2625
	level = btrfs_header_level(root->node);
C
Chris Mason 已提交
2626
	orig_level = level;
2627 2628
	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
		path->nodes[level] = root->node;
2629
		extent_buffer_get(root->node);
2630 2631 2632
		path->slots[level] = 0;
	} else {
		struct btrfs_key key;
2633 2634
		struct btrfs_disk_key found_key;
		struct extent_buffer *node;
2635

2636
		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2637 2638
		level = root_item->drop_level;
		path->lowest_level = level;
2639
		wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2640
		if (wret < 0) {
2641 2642 2643
			ret = wret;
			goto out;
		}
2644 2645 2646 2647
		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)));
2648 2649 2650 2651
		/*
		 * unlock our path, this is safe because only this
		 * function is allowed to delete this snapshot
		 */
2652 2653 2654 2655 2656 2657
		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]);
			}
		}
2658
	}
C
Chris Mason 已提交
2659
	while(1) {
2660
		wret = walk_down_tree(trans, root, path, &level);
C
Chris Mason 已提交
2661
		if (wret > 0)
C
Chris Mason 已提交
2662
			break;
C
Chris Mason 已提交
2663 2664 2665
		if (wret < 0)
			ret = wret;

2666
		wret = walk_up_tree(trans, root, path, &level);
C
Chris Mason 已提交
2667
		if (wret > 0)
C
Chris Mason 已提交
2668
			break;
C
Chris Mason 已提交
2669 2670
		if (wret < 0)
			ret = wret;
2671 2672 2673 2674
		if (trans->transaction->in_commit) {
			ret = -EAGAIN;
			break;
		}
C
Chris Mason 已提交
2675
	}
C
Chris Mason 已提交
2676
	for (i = 0; i <= orig_level; i++) {
2677
		if (path->nodes[i]) {
2678
			free_extent_buffer(path->nodes[i]);
2679
			path->nodes[i] = NULL;
C
Chris Mason 已提交
2680
		}
C
Chris Mason 已提交
2681
	}
2682
out:
2683
	btrfs_free_path(path);
C
Chris Mason 已提交
2684
	return ret;
C
Chris Mason 已提交
2685
}
C
Chris Mason 已提交
2686

2687
int btrfs_free_block_groups(struct btrfs_fs_info *info)
C
Chris Mason 已提交
2688
{
2689 2690
	u64 start;
	u64 end;
2691
	u64 ptr;
C
Chris Mason 已提交
2692
	int ret;
2693 2694

	mutex_lock(&info->alloc_mutex);
C
Chris Mason 已提交
2695
	while(1) {
2696 2697 2698
		ret = find_first_extent_bit(&info->block_group_cache, 0,
					    &start, &end, (unsigned int)-1);
		if (ret)
C
Chris Mason 已提交
2699
			break;
2700 2701 2702
		ret = get_state_private(&info->block_group_cache, start, &ptr);
		if (!ret)
			kfree((void *)(unsigned long)ptr);
2703 2704
		clear_extent_bits(&info->block_group_cache, start,
				  end, (unsigned int)-1, GFP_NOFS);
C
Chris Mason 已提交
2705
	}
2706
	while(1) {
2707 2708 2709
		ret = find_first_extent_bit(&info->free_space_cache, 0,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
2710
			break;
2711 2712
		clear_extent_dirty(&info->free_space_cache, start,
				   end, GFP_NOFS);
2713
	}
2714
	mutex_unlock(&info->alloc_mutex);
C
Chris Mason 已提交
2715 2716 2717
	return 0;
}

2718 2719 2720 2721 2722 2723
static unsigned long calc_ra(unsigned long start, unsigned long last,
			     unsigned long nr)
{
	return min(last, start + nr - 1);
}

2724 2725
static int noinline relocate_inode_pages(struct inode *inode, u64 start,
					 u64 len)
2726 2727 2728 2729 2730 2731
{
	u64 page_start;
	u64 page_end;
	unsigned long last_index;
	unsigned long i;
	struct page *page;
2732
	struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
2733
	struct file_ra_state *ra;
2734 2735
	unsigned long total_read = 0;
	unsigned long ra_pages;
2736
	struct btrfs_ordered_extent *ordered;
2737
	struct btrfs_trans_handle *trans;
2738 2739

	ra = kzalloc(sizeof(*ra), GFP_NOFS);
2740 2741

	mutex_lock(&inode->i_mutex);
2742
	i = start >> PAGE_CACHE_SHIFT;
2743 2744
	last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;

2745 2746
	ra_pages = BTRFS_I(inode)->root->fs_info->bdi.ra_pages;

2747
	file_ra_state_init(ra, inode->i_mapping);
2748

2749
	for (; i <= last_index; i++) {
2750 2751 2752 2753 2754
		if (total_read % ra_pages == 0) {
			btrfs_force_ra(inode->i_mapping, ra, NULL, i,
				       calc_ra(i, last_index, ra_pages));
		}
		total_read++;
2755 2756
again:
		if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
2757
			goto truncate_racing;
2758
		page = grab_cache_page(inode->i_mapping, i);
2759
		if (!page) {
2760
			goto out_unlock;
2761
		}
2762 2763 2764 2765 2766 2767 2768 2769 2770
		if (!PageUptodate(page)) {
			btrfs_readpage(NULL, page);
			lock_page(page);
			if (!PageUptodate(page)) {
				unlock_page(page);
				page_cache_release(page);
				goto out_unlock;
			}
		}
2771
		wait_on_page_writeback(page);
2772

2773 2774
		page_start = (u64)page->index << PAGE_CACHE_SHIFT;
		page_end = page_start + PAGE_CACHE_SIZE - 1;
2775
		lock_extent(io_tree, page_start, page_end, GFP_NOFS);
2776

2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788
		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);


2789
		set_extent_delalloc(io_tree, page_start,
2790
				    page_end, GFP_NOFS);
2791
		set_page_dirty(page);
2792

2793
		unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
2794 2795 2796 2797 2798
		unlock_page(page);
		page_cache_release(page);
	}

out_unlock:
2799 2800 2801 2802 2803 2804 2805 2806 2807 2808
	/* we have to start the IO in order to get the ordered extents
	 * instantiated.  This allows the relocation to code to wait
	 * for all the ordered extents to hit the disk.
	 *
	 * Otherwise, it would constantly loop over the same extents
	 * because the old ones don't get deleted  until the IO is
	 * started
	 */
	btrfs_fdatawrite_range(inode->i_mapping, start, start + len - 1,
			       WB_SYNC_NONE);
2809
	kfree(ra);
2810 2811 2812 2813 2814
	trans = btrfs_start_transaction(BTRFS_I(inode)->root, 1);
	if (trans) {
		btrfs_end_transaction(trans, BTRFS_I(inode)->root);
		mark_inode_dirty(inode);
	}
2815 2816
	mutex_unlock(&inode->i_mutex);
	return 0;
2817 2818 2819 2820 2821 2822

truncate_racing:
	vmtruncate(inode, inode->i_size);
	balance_dirty_pages_ratelimited_nr(inode->i_mapping,
					   total_read);
	goto out_unlock;
2823 2824
}

2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866
/*
 * The back references tell us which tree holds a ref on a block,
 * but it is possible for the tree root field in the reference to
 * reflect the original root before a snapshot was made.  In this
 * case we should search through all the children of a given root
 * to find potential holders of references on a block.
 *
 * Instead, we do something a little less fancy and just search
 * all the roots for a given key/block combination.
 */
static int find_root_for_ref(struct btrfs_root *root,
			     struct btrfs_path *path,
			     struct btrfs_key *key0,
			     int level,
			     int file_key,
			     struct btrfs_root **found_root,
			     u64 bytenr)
{
	struct btrfs_key root_location;
	struct btrfs_root *cur_root = *found_root;
	struct btrfs_file_extent_item *file_extent;
	u64 root_search_start = BTRFS_FS_TREE_OBJECTID;
	u64 found_bytenr;
	int ret;

	root_location.offset = (u64)-1;
	root_location.type = BTRFS_ROOT_ITEM_KEY;
	path->lowest_level = level;
	path->reada = 0;
	while(1) {
		ret = btrfs_search_slot(NULL, cur_root, key0, path, 0, 0);
		found_bytenr = 0;
		if (ret == 0 && file_key) {
			struct extent_buffer *leaf = path->nodes[0];
			file_extent = btrfs_item_ptr(leaf, path->slots[0],
					     struct btrfs_file_extent_item);
			if (btrfs_file_extent_type(leaf, file_extent) ==
			    BTRFS_FILE_EXTENT_REG) {
				found_bytenr =
					btrfs_file_extent_disk_bytenr(leaf,
							       file_extent);
		       }
2867
		} else if (!file_key) {
2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896
			if (path->nodes[level])
				found_bytenr = path->nodes[level]->start;
		}

		btrfs_release_path(cur_root, path);

		if (found_bytenr == bytenr) {
			*found_root = cur_root;
			ret = 0;
			goto out;
		}
		ret = btrfs_search_root(root->fs_info->tree_root,
					root_search_start, &root_search_start);
		if (ret)
			break;

		root_location.objectid = root_search_start;
		cur_root = btrfs_read_fs_root_no_name(root->fs_info,
						      &root_location);
		if (!cur_root) {
			ret = 1;
			break;
		}
	}
out:
	path->lowest_level = 0;
	return ret;
}

2897 2898 2899
/*
 * note, this releases the path
 */
2900
static int noinline relocate_one_reference(struct btrfs_root *extent_root,
2901
				  struct btrfs_path *path,
C
Chris Mason 已提交
2902 2903 2904 2905 2906
				  struct btrfs_key *extent_key,
				  u64 *last_file_objectid,
				  u64 *last_file_offset,
				  u64 *last_file_root,
				  u64 last_extent)
2907 2908 2909
{
	struct inode *inode;
	struct btrfs_root *found_root;
2910 2911
	struct btrfs_key root_location;
	struct btrfs_key found_key;
2912 2913 2914 2915 2916
	struct btrfs_extent_ref *ref;
	u64 ref_root;
	u64 ref_gen;
	u64 ref_objectid;
	u64 ref_offset;
2917
	int ret;
2918
	int level;
2919

2920 2921
	WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));

2922 2923 2924 2925 2926 2927 2928 2929
	ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
			     struct btrfs_extent_ref);
	ref_root = btrfs_ref_root(path->nodes[0], ref);
	ref_gen = btrfs_ref_generation(path->nodes[0], ref);
	ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
	ref_offset = btrfs_ref_offset(path->nodes[0], ref);
	btrfs_release_path(extent_root, path);

2930
	root_location.objectid = ref_root;
2931
	if (ref_gen == 0)
2932
		root_location.offset = 0;
2933
	else
2934 2935
		root_location.offset = (u64)-1;
	root_location.type = BTRFS_ROOT_ITEM_KEY;
2936 2937

	found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
2938
						&root_location);
2939
	BUG_ON(!found_root);
2940
	mutex_unlock(&extent_root->fs_info->alloc_mutex);
2941 2942

	if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
2943 2944 2945 2946 2947
		found_key.objectid = ref_objectid;
		found_key.type = BTRFS_EXTENT_DATA_KEY;
		found_key.offset = ref_offset;
		level = 0;

C
Chris Mason 已提交
2948 2949 2950 2951 2952 2953
		if (last_extent == extent_key->objectid &&
		    *last_file_objectid == ref_objectid &&
		    *last_file_offset == ref_offset &&
		    *last_file_root == ref_root)
			goto out;

2954 2955 2956 2957 2958 2959 2960
		ret = find_root_for_ref(extent_root, path, &found_key,
					level, 1, &found_root,
					extent_key->objectid);

		if (ret)
			goto out;

C
Chris Mason 已提交
2961 2962 2963 2964 2965 2966
		if (last_extent == extent_key->objectid &&
		    *last_file_objectid == ref_objectid &&
		    *last_file_offset == ref_offset &&
		    *last_file_root == ref_root)
			goto out;

2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981
		inode = btrfs_iget_locked(extent_root->fs_info->sb,
					  ref_objectid, found_root);
		if (inode->i_state & I_NEW) {
			/* the inode and parent dir are two different roots */
			BTRFS_I(inode)->root = found_root;
			BTRFS_I(inode)->location.objectid = ref_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);

		}
		/* this can happen if the reference is not against
		 * the latest version of the tree root
		 */
2982
		if (is_bad_inode(inode))
2983
			goto out;
2984

C
Chris Mason 已提交
2985 2986 2987 2988
		*last_file_objectid = inode->i_ino;
		*last_file_root = found_root->root_key.objectid;
		*last_file_offset = ref_offset;

2989 2990 2991 2992 2993
		relocate_inode_pages(inode, ref_offset, extent_key->offset);
		iput(inode);
	} else {
		struct btrfs_trans_handle *trans;
		struct extent_buffer *eb;
2994
		int needs_lock = 0;
2995 2996

		eb = read_tree_block(found_root, extent_key->objectid,
2997
				     extent_key->offset, 0);
2998
		btrfs_tree_lock(eb);
2999 3000 3001 3002 3003 3004 3005
		level = btrfs_header_level(eb);

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

3006
		btrfs_tree_unlock(eb);
3007 3008
		free_extent_buffer(eb);

3009 3010 3011 3012 3013 3014 3015
		ret = find_root_for_ref(extent_root, path, &found_key,
					level, 0, &found_root,
					extent_key->objectid);

		if (ret)
			goto out;

3016 3017 3018 3019 3020 3021 3022 3023
		/*
		 * right here almost anything could happen to our key,
		 * but that's ok.  The cow below will either relocate it
		 * or someone else will have relocated it.  Either way,
		 * it is in a different spot than it was before and
		 * we're happy.
		 */

3024 3025
		trans = btrfs_start_transaction(found_root, 1);

3026 3027 3028 3029 3030 3031 3032
		if (found_root == extent_root->fs_info->extent_root ||
		    found_root == extent_root->fs_info->chunk_root ||
		    found_root == extent_root->fs_info->dev_root) {
			needs_lock = 1;
			mutex_lock(&extent_root->fs_info->alloc_mutex);
		}

3033
		path->lowest_level = level;
3034
		path->reada = 2;
3035 3036 3037 3038
		ret = btrfs_search_slot(trans, found_root, &found_key, path,
					0, 1);
		path->lowest_level = 0;
		btrfs_release_path(found_root, path);
3039

C
Chris Mason 已提交
3040 3041
		if (found_root == found_root->fs_info->extent_root)
			btrfs_extent_post_op(trans, found_root);
3042 3043 3044
		if (needs_lock)
			mutex_unlock(&extent_root->fs_info->alloc_mutex);

3045 3046
		btrfs_end_transaction(trans, found_root);

3047
	}
3048
out:
3049
	mutex_lock(&extent_root->fs_info->alloc_mutex);
3050 3051 3052
	return 0;
}

3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073
static int noinline del_extent_zero(struct btrfs_root *extent_root,
				    struct btrfs_path *path,
				    struct btrfs_key *extent_key)
{
	int ret;
	struct btrfs_trans_handle *trans;

	trans = btrfs_start_transaction(extent_root, 1);
	ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
	if (ret > 0) {
		ret = -EIO;
		goto out;
	}
	if (ret < 0)
		goto out;
	ret = btrfs_del_item(trans, extent_root, path);
out:
	btrfs_end_transaction(trans, extent_root);
	return ret;
}

3074 3075 3076
static int noinline relocate_one_extent(struct btrfs_root *extent_root,
					struct btrfs_path *path,
					struct btrfs_key *extent_key)
3077 3078 3079 3080
{
	struct btrfs_key key;
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
C
Chris Mason 已提交
3081 3082 3083 3084
	u64 last_file_objectid = 0;
	u64 last_file_root = 0;
	u64 last_file_offset = (u64)-1;
	u64 last_extent = 0;
3085 3086 3087 3088
	u32 nritems;
	u32 item_size;
	int ret = 0;

3089 3090 3091 3092
	if (extent_key->objectid == 0) {
		ret = del_extent_zero(extent_root, path, extent_key);
		goto out;
	}
3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105
	key.objectid = extent_key->objectid;
	key.type = BTRFS_EXTENT_REF_KEY;
	key.offset = 0;

	while(1) {
		ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);

		if (ret < 0)
			goto out;

		ret = 0;
		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
3106 3107 3108 3109 3110 3111 3112 3113
		if (path->slots[0] == nritems) {
			ret = btrfs_next_leaf(extent_root, path);
			if (ret > 0) {
				ret = 0;
				goto out;
			}
			if (ret < 0)
				goto out;
3114
			leaf = path->nodes[0];
3115
		}
3116 3117

		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3118
		if (found_key.objectid != extent_key->objectid) {
3119
			break;
3120
		}
3121

3122
		if (found_key.type != BTRFS_EXTENT_REF_KEY) {
3123
			break;
3124
		}
3125 3126 3127 3128

		key.offset = found_key.offset + 1;
		item_size = btrfs_item_size_nr(leaf, path->slots[0]);

C
Chris Mason 已提交
3129 3130 3131 3132
		ret = relocate_one_reference(extent_root, path, extent_key,
					     &last_file_objectid,
					     &last_file_offset,
					     &last_file_root, last_extent);
3133 3134
		if (ret)
			goto out;
C
Chris Mason 已提交
3135
		last_extent = extent_key->objectid;
3136 3137 3138 3139 3140 3141 3142
	}
	ret = 0;
out:
	btrfs_release_path(extent_root, path);
	return ret;
}

3143 3144 3145 3146 3147 3148
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;

3149
	num_devices = root->fs_info->fs_devices->num_devices;
3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180
	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 已提交
3181 3182 3183 3184 3185 3186 3187 3188
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;

3189
	spin_lock(&shrink_block_group->lock);
C
Chris Mason 已提交
3190
	if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
3191
		spin_unlock(&shrink_block_group->lock);
3192
		mutex_unlock(&root->fs_info->alloc_mutex);
3193

C
Chris Mason 已提交
3194
		trans = btrfs_start_transaction(root, 1);
3195
		mutex_lock(&root->fs_info->alloc_mutex);
3196
		spin_lock(&shrink_block_group->lock);
3197

C
Chris Mason 已提交
3198 3199 3200 3201 3202 3203 3204 3205
		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;
		}
3206 3207
		spin_unlock(&shrink_block_group->lock);

C
Chris Mason 已提交
3208 3209
		do_chunk_alloc(trans, root->fs_info->extent_root,
			       calc + 2 * 1024 * 1024, new_alloc_flags, force);
3210 3211

		mutex_unlock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
3212
		btrfs_end_transaction(trans, root);
3213
		mutex_lock(&root->fs_info->alloc_mutex);
3214 3215
	} else
		spin_unlock(&shrink_block_group->lock);
C
Chris Mason 已提交
3216 3217 3218
	return 0;
}

3219
int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 shrink_start)
3220 3221 3222 3223 3224 3225
{
	struct btrfs_trans_handle *trans;
	struct btrfs_root *tree_root = root->fs_info->tree_root;
	struct btrfs_path *path;
	u64 cur_byte;
	u64 total_found;
3226 3227
	u64 shrink_last_byte;
	struct btrfs_block_group_cache *shrink_block_group;
3228 3229
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_key key;
3230
	struct btrfs_key found_key;
3231 3232 3233
	struct extent_buffer *leaf;
	u32 nritems;
	int ret;
3234
	int progress;
3235

3236
	mutex_lock(&root->fs_info->alloc_mutex);
3237 3238 3239 3240
	shrink_block_group = btrfs_lookup_block_group(root->fs_info,
						      shrink_start);
	BUG_ON(!shrink_block_group);

C
Chris Mason 已提交
3241 3242
	shrink_last_byte = shrink_block_group->key.objectid +
		shrink_block_group->key.offset;
3243 3244 3245

	shrink_block_group->space_info->total_bytes -=
		shrink_block_group->key.offset;
3246 3247
	path = btrfs_alloc_path();
	root = root->fs_info->extent_root;
3248
	path->reada = 2;
3249

3250 3251 3252 3253
	printk("btrfs relocating block group %llu flags %llu\n",
	       (unsigned long long)shrink_start,
	       (unsigned long long)shrink_block_group->flags);

C
Chris Mason 已提交
3254 3255
	__alloc_chunk_for_shrink(root, shrink_block_group, 1);

3256
again:
3257

3258 3259
	shrink_block_group->ro = 1;

3260
	total_found = 0;
3261
	progress = 0;
3262
	key.objectid = shrink_start;
3263 3264
	key.offset = 0;
	key.type = 0;
3265
	cur_byte = key.objectid;
3266

3267 3268 3269 3270
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		goto out;

3271
	ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
3272 3273
	if (ret < 0)
		goto out;
3274

3275 3276 3277
	if (ret == 0) {
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3278 3279
		if (found_key.objectid + found_key.offset > shrink_start &&
		    found_key.objectid < shrink_last_byte) {
3280 3281 3282 3283 3284 3285 3286
			cur_byte = found_key.objectid;
			key.objectid = cur_byte;
		}
	}
	btrfs_release_path(root, path);

	while(1) {
3287 3288 3289
		ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
		if (ret < 0)
			goto out;
3290

3291
next:
3292
		leaf = path->nodes[0];
3293 3294 3295 3296 3297 3298 3299 3300
		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;
3301
			}
3302 3303
			leaf = path->nodes[0];
			nritems = btrfs_header_nritems(leaf);
3304
		}
3305 3306

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

3308 3309 3310
		if (found_key.objectid >= shrink_last_byte)
			break;

3311 3312 3313 3314 3315 3316 3317 3318 3319 3320
		if (progress && need_resched()) {
			memcpy(&key, &found_key, sizeof(key));
			cond_resched();
			btrfs_release_path(root, path);
			btrfs_search_slot(NULL, root, &key, path, 0, 0);
			progress = 0;
			goto next;
		}
		progress = 1;

3321 3322
		if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
		    found_key.objectid + found_key.offset <= cur_byte) {
C
Chris Mason 已提交
3323 3324
			memcpy(&key, &found_key, sizeof(key));
			key.offset++;
3325 3326 3327
			path->slots[0]++;
			goto next;
		}
3328

3329 3330 3331 3332 3333
		total_found++;
		cur_byte = found_key.objectid + found_key.offset;
		key.objectid = cur_byte;
		btrfs_release_path(root, path);
		ret = relocate_one_extent(root, path, &found_key);
C
Chris Mason 已提交
3334
		__alloc_chunk_for_shrink(root, shrink_block_group, 0);
3335 3336 3337 3338 3339
	}

	btrfs_release_path(root, path);

	if (total_found > 0) {
3340 3341 3342
		printk("btrfs relocate found %llu last extent was %llu\n",
		       (unsigned long long)total_found,
		       (unsigned long long)found_key.objectid);
3343
		mutex_unlock(&root->fs_info->alloc_mutex);
3344 3345 3346 3347 3348
		trans = btrfs_start_transaction(tree_root, 1);
		btrfs_commit_transaction(trans, tree_root);

		btrfs_clean_old_snapshots(tree_root);

3349 3350
		btrfs_wait_ordered_extents(tree_root);

3351 3352
		trans = btrfs_start_transaction(tree_root, 1);
		btrfs_commit_transaction(trans, tree_root);
3353
		mutex_lock(&root->fs_info->alloc_mutex);
3354 3355 3356
		goto again;
	}

3357 3358 3359 3360
	/*
	 * we've freed all the extents, now remove the block
	 * group item from the tree
	 */
3361 3362
	mutex_unlock(&root->fs_info->alloc_mutex);

3363
	trans = btrfs_start_transaction(root, 1);
3364

3365
	mutex_lock(&root->fs_info->alloc_mutex);
3366
	memcpy(&key, &shrink_block_group->key, sizeof(key));
3367

3368 3369 3370
	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
	if (ret > 0)
		ret = -EIO;
3371 3372
	if (ret < 0) {
		btrfs_end_transaction(trans, root);
3373
		goto out;
3374
	}
3375

C
Chris Mason 已提交
3376 3377
	clear_extent_bits(&info->block_group_cache, key.objectid,
			  key.objectid + key.offset - 1,
3378
			  (unsigned int)-1, GFP_NOFS);
3379

C
Chris Mason 已提交
3380 3381 3382 3383 3384 3385 3386 3387

	clear_extent_bits(&info->free_space_cache,
			   key.objectid, key.objectid + key.offset - 1,
			   (unsigned int)-1, GFP_NOFS);

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

3388
	btrfs_del_item(trans, root, path);
3389 3390
	btrfs_release_path(root, path);
	mutex_unlock(&root->fs_info->alloc_mutex);
3391
	btrfs_commit_transaction(trans, root);
C
Chris Mason 已提交
3392

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

C
Chris Mason 已提交
3395 3396 3397 3398 3399 3400
	/* the code to unpin extents might set a few bits in the free
	 * space cache for this range again
	 */
	clear_extent_bits(&info->free_space_cache,
			   key.objectid, key.objectid + key.offset - 1,
			   (unsigned int)-1, GFP_NOFS);
3401 3402
out:
	btrfs_free_path(path);
3403
	mutex_unlock(&root->fs_info->alloc_mutex);
3404 3405 3406
	return ret;
}

3407 3408 3409
int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
			   struct btrfs_key *key)
{
3410
	int ret = 0;
3411 3412 3413
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
	int slot;
3414

3415 3416
	ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
	if (ret < 0)
3417 3418
		goto out;

3419 3420
	while(1) {
		slot = path->slots[0];
3421
		leaf = path->nodes[0];
3422 3423 3424 3425 3426
		if (slot >= btrfs_header_nritems(leaf)) {
			ret = btrfs_next_leaf(root, path);
			if (ret == 0)
				continue;
			if (ret < 0)
3427
				goto out;
3428
			break;
3429
		}
3430
		btrfs_item_key_to_cpu(leaf, &found_key, slot);
3431

3432
		if (found_key.objectid >= key->objectid &&
3433 3434 3435 3436
		    found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
			ret = 0;
			goto out;
		}
3437
		path->slots[0]++;
3438
	}
3439
	ret = -ENOENT;
3440
out:
3441
	return ret;
3442 3443
}

C
Chris Mason 已提交
3444 3445 3446 3447
int btrfs_read_block_groups(struct btrfs_root *root)
{
	struct btrfs_path *path;
	int ret;
3448
	int bit;
C
Chris Mason 已提交
3449
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
3450
	struct btrfs_fs_info *info = root->fs_info;
3451
	struct btrfs_space_info *space_info;
3452
	struct extent_io_tree *block_group_cache;
C
Chris Mason 已提交
3453 3454
	struct btrfs_key key;
	struct btrfs_key found_key;
3455
	struct extent_buffer *leaf;
3456 3457

	block_group_cache = &info->block_group_cache;
C
Chris Mason 已提交
3458
	root = info->extent_root;
C
Chris Mason 已提交
3459
	key.objectid = 0;
3460
	key.offset = 0;
C
Chris Mason 已提交
3461 3462 3463 3464 3465
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

3466
	mutex_lock(&root->fs_info->alloc_mutex);
C
Chris Mason 已提交
3467
	while(1) {
3468 3469 3470 3471
		ret = find_first_block_group(root, path, &key);
		if (ret > 0) {
			ret = 0;
			goto error;
C
Chris Mason 已提交
3472
		}
3473 3474 3475
		if (ret != 0)
			goto error;

3476 3477
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3478
		cache = kzalloc(sizeof(*cache), GFP_NOFS);
C
Chris Mason 已提交
3479
		if (!cache) {
3480
			ret = -ENOMEM;
C
Chris Mason 已提交
3481 3482
			break;
		}
C
Chris Mason 已提交
3483

3484
		spin_lock_init(&cache->lock);
3485 3486 3487
		read_extent_buffer(leaf, &cache->item,
				   btrfs_item_ptr_offset(leaf, path->slots[0]),
				   sizeof(cache->item));
C
Chris Mason 已提交
3488
		memcpy(&cache->key, &found_key, sizeof(found_key));
3489

C
Chris Mason 已提交
3490 3491
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
3492 3493 3494
		cache->flags = btrfs_block_group_flags(&cache->item);
		bit = 0;
		if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
3495
			bit = BLOCK_GROUP_DATA;
3496 3497 3498
		} else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
			bit = BLOCK_GROUP_SYSTEM;
		} else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
3499
			bit = BLOCK_GROUP_METADATA;
3500
		}
3501
		set_avail_alloc_bits(info, cache->flags);
3502

3503 3504 3505 3506 3507 3508
		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;

3509 3510 3511
		/* use EXTENT_LOCKED to prevent merging */
		set_extent_bits(block_group_cache, found_key.objectid,
				found_key.objectid + found_key.offset - 1,
3512
				EXTENT_LOCKED, GFP_NOFS);
3513
		set_state_private(block_group_cache, found_key.objectid,
J
Jens Axboe 已提交
3514
				  (unsigned long)cache);
3515 3516 3517
		set_extent_bits(block_group_cache, found_key.objectid,
				found_key.objectid + found_key.offset - 1,
				bit | EXTENT_LOCKED, GFP_NOFS);
C
Chris Mason 已提交
3518
		if (key.objectid >=
3519
		    btrfs_super_total_bytes(&info->super_copy))
C
Chris Mason 已提交
3520 3521
			break;
	}
3522 3523
	ret = 0;
error:
C
Chris Mason 已提交
3524
	btrfs_free_path(path);
3525
	mutex_unlock(&root->fs_info->alloc_mutex);
3526
	return ret;
C
Chris Mason 已提交
3527
}
3528 3529 3530

int btrfs_make_block_group(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root, u64 bytes_used,
3531
			   u64 type, u64 chunk_objectid, u64 chunk_offset,
3532 3533 3534 3535 3536 3537 3538 3539
			   u64 size)
{
	int ret;
	int bit = 0;
	struct btrfs_root *extent_root;
	struct btrfs_block_group_cache *cache;
	struct extent_io_tree *block_group_cache;

3540
	WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
3541 3542 3543
	extent_root = root->fs_info->extent_root;
	block_group_cache = &root->fs_info->block_group_cache;

3544
	cache = kzalloc(sizeof(*cache), GFP_NOFS);
3545
	BUG_ON(!cache);
3546
	cache->key.objectid = chunk_offset;
3547
	cache->key.offset = size;
3548
	spin_lock_init(&cache->lock);
3549
	btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
C
Chris Mason 已提交
3550

3551 3552 3553 3554 3555 3556 3557 3558 3559
	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);

C
Chris Mason 已提交
3560
	bit = block_group_state_bits(type);
3561 3562
	set_extent_bits(block_group_cache, chunk_offset,
			chunk_offset + size - 1,
3563
			EXTENT_LOCKED, GFP_NOFS);
3564 3565
	set_state_private(block_group_cache, chunk_offset,
			  (unsigned long)cache);
3566 3567 3568 3569
	set_extent_bits(block_group_cache, chunk_offset,
			chunk_offset + size - 1,
			bit | EXTENT_LOCKED, GFP_NOFS);

3570 3571 3572 3573 3574 3575 3576
	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 已提交
3577
	set_avail_alloc_bits(extent_root->fs_info, type);
3578

3579 3580
	return 0;
}