extent-tree.c 79.5 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

29
#define BLOCK_GROUP_DATA     EXTENT_WRITEBACK
30
#define BLOCK_GROUP_METADATA EXTENT_UPTODATE
31 32
#define BLOCK_GROUP_SYSTEM   EXTENT_NEW

33 34
#define BLOCK_GROUP_DIRTY EXTENT_DIRTY

35 36
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root);
C
Chris Mason 已提交
37 38
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root);
39

40

41 42 43 44 45 46
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;
47
	struct extent_buffer *leaf;
48
	struct extent_io_tree *free_space_cache;
49 50 51
	int slot;
	u64 last = 0;
	u64 hole_size;
52
	u64 first_free;
53 54
	int found = 0;

55 56 57
	if (!block_group)
		return 0;

58
	root = root->fs_info->extent_root;
59
	free_space_cache = &root->fs_info->free_space_cache;
60 61 62

	if (block_group->cached)
		return 0;
63

64 65 66
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
67

68
	path->reada = 2;
69
	first_free = block_group->key.objectid;
70 71 72 73 74 75
	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;
76
	ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
77 78 79 80 81 82 83 84
	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;
	}
85
	while(1) {
86
		leaf = path->nodes[0];
87
		slot = path->slots[0];
88
		if (slot >= btrfs_header_nritems(leaf)) {
89
			ret = btrfs_next_leaf(root, path);
90 91
			if (ret < 0)
				goto err;
92
			if (ret == 0) {
93
				continue;
94
			} else {
95 96 97
				break;
			}
		}
98
		btrfs_item_key_to_cpu(leaf, &key, slot);
99 100 101
		if (key.objectid < block_group->key.objectid) {
			goto next;
		}
102 103 104 105
		if (key.objectid >= block_group->key.objectid +
		    block_group->key.offset) {
			break;
		}
106

107 108
		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
			if (!found) {
109
				last = first_free;
110 111
				found = 1;
			}
112 113 114 115 116
			if (key.objectid > last) {
				hole_size = key.objectid - last;
				set_extent_dirty(free_space_cache, last,
						 last + hole_size - 1,
						 GFP_NOFS);
117 118
			}
			last = key.objectid + key.offset;
119
		}
120
next:
121 122 123
		path->slots[0]++;
	}

124 125 126 127 128 129
	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;
130 131
		set_extent_dirty(free_space_cache, last,
				 last + hole_size - 1, GFP_NOFS);
132
	}
133
	block_group->cached = 1;
134
err:
135 136 137 138
	btrfs_free_path(path);
	return 0;
}

139 140
struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
							 btrfs_fs_info *info,
141
							 u64 bytenr)
C
Chris Mason 已提交
142
{
143
	struct extent_io_tree *block_group_cache;
144 145 146 147
	struct btrfs_block_group_cache *block_group = NULL;
	u64 ptr;
	u64 start;
	u64 end;
C
Chris Mason 已提交
148 149
	int ret;

150 151
	bytenr = max_t(u64, bytenr,
		       BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
152 153
	block_group_cache = &info->block_group_cache;
	ret = find_first_extent_bit(block_group_cache,
154
				    bytenr, &start, &end,
155 156
				    BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
				    BLOCK_GROUP_SYSTEM);
C
Chris Mason 已提交
157
	if (ret) {
158
		return NULL;
C
Chris Mason 已提交
159
	}
160 161 162 163
	ret = get_state_private(block_group_cache, start, &ptr);
	if (ret)
		return NULL;

J
Jens Axboe 已提交
164
	block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
Y
Yan 已提交
165
	if (block_group->key.objectid <= bytenr && bytenr <
166 167
	    block_group->key.objectid + block_group->key.offset)
		return block_group;
C
Chris Mason 已提交
168 169
	return NULL;
}
170 171 172

static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
{
173
	return (cache->flags & bits) == bits;
174 175 176
}

static int noinline find_search_start(struct btrfs_root *root,
177
			      struct btrfs_block_group_cache **cache_ret,
178
			      u64 *start_ret, int num, int data)
179 180 181
{
	int ret;
	struct btrfs_block_group_cache *cache = *cache_ret;
C
Chris Mason 已提交
182
	struct extent_io_tree *free_space_cache;
183
	struct extent_state *state;
184
	u64 last;
185
	u64 start = 0;
186
	u64 cache_miss = 0;
C
Chris Mason 已提交
187
	u64 total_fs_bytes;
188
	u64 search_start = *start_ret;
189
	int wrapped = 0;
190

191
	if (!cache)
192
		goto out;
193

C
Chris Mason 已提交
194
	total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
C
Chris Mason 已提交
195 196
	free_space_cache = &root->fs_info->free_space_cache;

197
again:
198 199 200
	ret = cache_block_group(root, cache);
	if (ret)
		goto out;
201

202
	last = max(search_start, cache->key.objectid);
203
	if (!block_group_bits(cache, data) || cache->ro) {
204 205
		goto new_group;
	}
206

207 208
	spin_lock_irq(&free_space_cache->lock);
	state = find_first_extent_bit_state(free_space_cache, last, EXTENT_DIRTY);
209
	while(1) {
210
		if (!state) {
211 212
			if (!cache_miss)
				cache_miss = last;
213
			spin_unlock_irq(&free_space_cache->lock);
214 215
			goto new_group;
		}
216

217 218
		start = max(last, state->start);
		last = state->end + 1;
219 220 221
		if (last - start < num) {
			if (last == cache->key.objectid + cache->key.offset)
				cache_miss = start;
222 223 224
			do {
				state = extent_state_next(state);
			} while(state && !(state->state & EXTENT_DIRTY));
225
			continue;
226
		}
227
		spin_unlock_irq(&free_space_cache->lock);
228 229
		if (cache->ro)
			goto new_group;
230
		if (start + num > cache->key.objectid + cache->key.offset)
231
			goto new_group;
C
Chris Mason 已提交
232 233
		if (start + num  > total_fs_bytes)
			goto new_group;
234
		if (!block_group_bits(cache, data)) {
235
			printk("block group bits don't match %Lu %d\n", cache->flags, data);
236
		}
237 238
		*start_ret = start;
		return 0;
239 240
	}
out:
241 242
	cache = btrfs_lookup_block_group(root->fs_info, search_start);
	if (!cache) {
243
		printk("Unable to find block group for %Lu\n", search_start);
244 245
		WARN_ON(1);
	}
246
	return -ENOSPC;
247 248

new_group:
249
	last = cache->key.objectid + cache->key.offset;
250
wrapped:
251
	cache = btrfs_lookup_block_group(root->fs_info, last);
C
Chris Mason 已提交
252
	if (!cache || cache->key.objectid >= total_fs_bytes) {
253
no_cache:
254 255 256 257 258
		if (!wrapped) {
			wrapped = 1;
			last = search_start;
			goto wrapped;
		}
259
		goto out;
260
	}
261 262 263 264 265
	if (cache_miss && !cache->cached) {
		cache_block_group(root, cache);
		last = cache_miss;
		cache = btrfs_lookup_block_group(root->fs_info, last);
	}
266
	cache = btrfs_find_block_group(root, cache, last, data, 0);
267 268
	if (!cache)
		goto no_cache;
269
	*cache_ret = cache;
270
	cache_miss = 0;
271 272 273
	goto again;
}

C
Chris Mason 已提交
274 275
static u64 div_factor(u64 num, int factor)
{
276 277
	if (factor == 10)
		return num;
C
Chris Mason 已提交
278 279 280 281 282
	num *= factor;
	do_div(num, 10);
	return num;
}

283 284 285 286 287 288 289 290 291 292 293 294
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;
}

295 296
struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
						 struct btrfs_block_group_cache
C
Chris Mason 已提交
297
						 *hint, u64 search_start,
298
						 int data, int owner)
C
Chris Mason 已提交
299
{
300
	struct btrfs_block_group_cache *cache;
301
	struct extent_io_tree *block_group_cache;
302
	struct btrfs_block_group_cache *found_group = NULL;
C
Chris Mason 已提交
303 304
	struct btrfs_fs_info *info = root->fs_info;
	u64 used;
305 306
	u64 last = 0;
	u64 hint_last;
307 308 309 310
	u64 start;
	u64 end;
	u64 free_check;
	u64 ptr;
C
Chris Mason 已提交
311
	u64 total_fs_bytes;
312
	int bit;
C
Chris Mason 已提交
313
	int ret;
314
	int full_search = 0;
315
	int factor = 10;
316

317
	block_group_cache = &info->block_group_cache;
C
Chris Mason 已提交
318
	total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
319

320 321
	if (data & BTRFS_BLOCK_GROUP_METADATA)
		factor = 9;
C
Chris Mason 已提交
322

323
	bit = block_group_state_bits(data);
C
Chris Mason 已提交
324

C
Chris Mason 已提交
325
	if (search_start && search_start < total_fs_bytes) {
C
Chris Mason 已提交
326
		struct btrfs_block_group_cache *shint;
327
		shint = btrfs_lookup_block_group(info, search_start);
328
		if (shint && block_group_bits(shint, data) && !shint->ro) {
C
Chris Mason 已提交
329
			used = btrfs_block_group_used(&shint->item);
330 331
			if (used + shint->pinned <
			    div_factor(shint->key.offset, factor)) {
C
Chris Mason 已提交
332 333 334 335
				return shint;
			}
		}
	}
336
	if (hint && !hint->ro && block_group_bits(hint, data) &&
337
	    hint->key.objectid < total_fs_bytes) {
338
		used = btrfs_block_group_used(&hint->item);
339 340
		if (used + hint->pinned <
		    div_factor(hint->key.offset, factor)) {
341 342
			return hint;
		}
343
		last = hint->key.objectid + hint->key.offset;
344 345
		hint_last = last;
	} else {
346 347 348 349 350
		if (hint)
			hint_last = max(hint->key.objectid, search_start);
		else
			hint_last = search_start;

C
Chris Mason 已提交
351 352
		if (hint_last >= total_fs_bytes)
			hint_last = search_start;
353
		last = hint_last;
354 355
	}
again:
C
Chris Mason 已提交
356
	while(1) {
357 358 359
		ret = find_first_extent_bit(block_group_cache, last,
					    &start, &end, bit);
		if (ret)
C
Chris Mason 已提交
360
			break;
361 362 363 364 365

		ret = get_state_private(block_group_cache, start, &ptr);
		if (ret)
			break;

J
Jens Axboe 已提交
366
		cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
367 368 369
		last = cache->key.objectid + cache->key.offset;
		used = btrfs_block_group_used(&cache->item);

C
Chris Mason 已提交
370 371 372
		if (cache->key.objectid > total_fs_bytes)
			break;

373
		if (!cache->ro && block_group_bits(cache, data)) {
374 375 376 377 378
			if (full_search)
				free_check = cache->key.offset;
			else
				free_check = div_factor(cache->key.offset,
							factor);
379

380 381 382 383
			if (used + cache->pinned < free_check) {
				found_group = cache;
				goto found;
			}
384
		}
385
		cond_resched();
C
Chris Mason 已提交
386
	}
387
	if (!full_search) {
C
Chris Mason 已提交
388
		last = search_start;
389 390 391
		full_search = 1;
		goto again;
	}
C
Chris Mason 已提交
392
found:
393
	return found_group;
C
Chris Mason 已提交
394 395
}

396
static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
397 398 399 400 401 402
			   u64 owner, u64 owner_offset)
{
	u32 high_crc = ~(u32)0;
	u32 low_crc = ~(u32)0;
	__le64 lenum;
	lenum = cpu_to_le64(root_objectid);
403
	high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
404
	lenum = cpu_to_le64(ref_generation);
405
	low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
406 407
	if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
		lenum = cpu_to_le64(owner);
408
		low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
409
		lenum = cpu_to_le64(owner_offset);
410
		low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
411
	}
412 413 414
	return ((u64)high_crc << 32) | (u64)low_crc;
}

415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430
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;
}

431 432 433 434 435 436
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)
437 438 439
{
	u64 hash;
	struct btrfs_key key;
440
	struct btrfs_key found_key;
441
	struct btrfs_extent_ref ref;
442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496
	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;
}

497 498 499 500 501 502 503 504 505 506 507 508 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
/*
 * 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:
 *
560
 * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
561 562 563 564 565
 *
 * 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):
 *
566
 * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584
 *
 * 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
 */
585 586 587 588 589 590 591 592 593 594
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;
595 596 597
	int ret;

	btrfs_set_stack_ref_root(&ref, root_objectid);
598
	btrfs_set_stack_ref_generation(&ref, ref_generation);
599 600 601
	btrfs_set_stack_ref_objectid(&ref, owner);
	btrfs_set_stack_ref_offset(&ref, owner_offset);

602 603
	hash = hash_extent_ref(root_objectid, ref_generation, owner,
			       owner_offset);
604 605 606 607 608 609
	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) {
610 611 612 613 614 615 616 617
		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));
618
	}
619 620 621 622 623 624 625 626 627 628
	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;
629 630
}

C
Chris Mason 已提交
631 632
int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
				struct btrfs_root *root,
633
				u64 bytenr, u64 num_bytes,
634
				u64 root_objectid, u64 ref_generation,
635
				u64 owner, u64 owner_offset)
C
Chris Mason 已提交
636
{
637
	struct btrfs_path *path;
C
Chris Mason 已提交
638
	int ret;
C
Chris Mason 已提交
639
	struct btrfs_key key;
640
	struct extent_buffer *l;
C
Chris Mason 已提交
641
	struct btrfs_extent_item *item;
C
Chris Mason 已提交
642
	u32 refs;
C
Chris Mason 已提交
643

644
	WARN_ON(num_bytes < root->sectorsize);
645
	path = btrfs_alloc_path();
646 647
	if (!path)
		return -ENOMEM;
648

649
	path->reada = 1;
650
	key.objectid = bytenr;
651
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
652
	key.offset = num_bytes;
653
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
654
				0, 1);
655 656
	if (ret < 0)
		return ret;
657
	if (ret != 0) {
658
		BUG();
659
	}
C
Chris Mason 已提交
660
	BUG_ON(ret != 0);
661
	l = path->nodes[0];
662
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
663 664
	refs = btrfs_extent_refs(l, item);
	btrfs_set_extent_refs(l, item, refs + 1);
665
	btrfs_mark_buffer_dirty(path->nodes[0]);
666

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

669
	path->reada = 1;
670 671 672 673
	ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
					  path, bytenr, root_objectid,
					  ref_generation, owner, owner_offset);
	BUG_ON(ret);
674
	finish_current_insert(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
675
	del_pending_extents(trans, root->fs_info->extent_root);
676 677

	btrfs_free_path(path);
C
Chris Mason 已提交
678 679 680
	return 0;
}

681 682 683 684 685 686 687 688
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 已提交
689
static int lookup_extent_ref(struct btrfs_trans_handle *trans,
690 691
			     struct btrfs_root *root, u64 bytenr,
			     u64 num_bytes, u32 *refs)
692
{
693
	struct btrfs_path *path;
694
	int ret;
C
Chris Mason 已提交
695
	struct btrfs_key key;
696
	struct extent_buffer *l;
C
Chris Mason 已提交
697
	struct btrfs_extent_item *item;
698

699
	WARN_ON(num_bytes < root->sectorsize);
700
	path = btrfs_alloc_path();
701
	path->reada = 1;
702 703
	key.objectid = bytenr;
	key.offset = num_bytes;
704
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
705
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
706
				0, 0);
707 708
	if (ret < 0)
		goto out;
709 710
	if (ret != 0) {
		btrfs_print_leaf(root, path->nodes[0]);
711
		printk("failed to find block number %Lu\n", bytenr);
712
		BUG();
713 714
	}
	l = path->nodes[0];
715
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
716
	*refs = btrfs_extent_refs(l, item);
717
out:
718
	btrfs_free_path(path);
719 720 721
	return 0;
}

722 723
u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
				  struct btrfs_path *count_path,
724
				  u64 expected_owner,
725 726 727 728 729 730
				  u64 first_extent)
{
	struct btrfs_root *extent_root = root->fs_info->extent_root;
	struct btrfs_path *path;
	u64 bytenr;
	u64 found_objectid;
731
	u64 found_owner;
732
	u64 root_objectid = root->root_key.objectid;
733
	u32 total_count = 0;
C
Chris Mason 已提交
734
	u32 extent_refs;
735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770
	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;

	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 已提交
771
	extent_refs = btrfs_extent_refs(l, item);
772
	while (1) {
773
		l = path->nodes[0];
774 775 776 777 778 779 780 781 782 783
		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;
784

785 786 787 788 789 790 791 792 793 794
		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);

795 796
		if (found_objectid != root_objectid) {
			total_count = 2;
797
			goto out;
798
		}
799 800 801 802 803 804
		if (level == -1) {
			found_owner = btrfs_ref_objectid(l, ref_item);
			if (found_owner != expected_owner) {
				total_count = 2;
				goto out;
			}
C
Chris Mason 已提交
805 806 807 808 809 810 811 812 813 814
			/*
			 * 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--;
			}
815
		}
816
		total_count = 1;
817 818
		path->slots[0]++;
	}
C
Chris Mason 已提交
819 820 821 822 823 824 825 826
	/*
	 * 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;
	}
827 828 829 830 831 832 833 834 835 836 837 838 839 840
	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);
	return total_count;
}
C
Chris Mason 已提交
841
int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
842
		       struct btrfs_root *root, u64 owner_objectid)
C
Chris Mason 已提交
843
{
844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861
	u64 generation;
	u64 key_objectid;
	u64 level;
	u32 nritems;
	struct btrfs_disk_key disk_key;

	level = btrfs_header_level(root->node);
	generation = trans->transid;
	nritems = btrfs_header_nritems(root->node);
	if (nritems > 0) {
		if (level == 0)
			btrfs_item_key(root->node, &disk_key, 0);
		else
			btrfs_node_key(root->node, &disk_key, 0);
		key_objectid = btrfs_disk_key_objectid(&disk_key);
	} else {
		key_objectid = 0;
	}
862
	return btrfs_inc_extent_ref(trans, root, root->node->start,
863
				    root->node->len, owner_objectid,
864
				    generation, level, key_objectid);
C
Chris Mason 已提交
865 866
}

867
int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
868
		  struct extent_buffer *buf)
C
Chris Mason 已提交
869
{
870
	u64 bytenr;
871 872
	u32 nritems;
	struct btrfs_key key;
873
	struct btrfs_file_extent_item *fi;
C
Chris Mason 已提交
874
	int i;
875
	int level;
876
	int ret;
877
	int faili;
878

879
	if (!root->ref_cows)
880
		return 0;
881

882
	level = btrfs_header_level(buf);
883 884
	nritems = btrfs_header_nritems(buf);
	for (i = 0; i < nritems; i++) {
885 886
		if (level == 0) {
			u64 disk_bytenr;
887 888
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
889
				continue;
890
			fi = btrfs_item_ptr(buf, i,
891
					    struct btrfs_file_extent_item);
892
			if (btrfs_file_extent_type(buf, fi) ==
893 894
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
895 896
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
C
Chris Mason 已提交
897
				continue;
898
			ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
899 900 901
				    btrfs_file_extent_disk_num_bytes(buf, fi),
				    root->root_key.objectid, trans->transid,
				    key.objectid, key.offset);
902 903 904 905
			if (ret) {
				faili = i;
				goto fail;
			}
906
		} else {
907
			bytenr = btrfs_node_blockptr(buf, i);
908
			btrfs_node_key_to_cpu(buf, &key, i);
909
			ret = btrfs_inc_extent_ref(trans, root, bytenr,
910 911
					   btrfs_level_size(root, level - 1),
					   root->root_key.objectid,
912 913
					   trans->transid,
					   level - 1, key.objectid);
914 915 916 917
			if (ret) {
				faili = i;
				goto fail;
			}
918
		}
C
Chris Mason 已提交
919 920
	}
	return 0;
921
fail:
C
Chris Mason 已提交
922
	WARN_ON(1);
923
#if 0
924
	for (i =0; i < faili; i++) {
925 926
		if (level == 0) {
			u64 disk_bytenr;
927 928
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
929
				continue;
930
			fi = btrfs_item_ptr(buf, i,
931
					    struct btrfs_file_extent_item);
932
			if (btrfs_file_extent_type(buf, fi) ==
933 934
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
935 936
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
937
				continue;
938 939
			err = btrfs_free_extent(trans, root, disk_bytenr,
				    btrfs_file_extent_disk_num_bytes(buf,
940
								      fi), 0);
941 942
			BUG_ON(err);
		} else {
943 944 945
			bytenr = btrfs_node_blockptr(buf, i);
			err = btrfs_free_extent(trans, root, bytenr,
					btrfs_level_size(root, level - 1), 0);
946 947 948
			BUG_ON(err);
		}
	}
949
#endif
950
	return ret;
C
Chris Mason 已提交
951 952
}

C
Chris Mason 已提交
953 954 955 956 957 958 959 960
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;
961 962
	unsigned long bi;
	struct extent_buffer *leaf;
C
Chris Mason 已提交
963 964

	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
965 966
	if (ret < 0)
		goto fail;
C
Chris Mason 已提交
967
	BUG_ON(ret);
968 969 970 971 972

	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 已提交
973
	btrfs_release_path(extent_root, path);
974
fail:
C
Chris Mason 已提交
975 976 977 978 979 980 981 982 983 984
	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;

}

985 986
int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root)
C
Chris Mason 已提交
987
{
988
	struct extent_io_tree *block_group_cache;
989
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
990 991 992 993
	int ret;
	int err = 0;
	int werr = 0;
	struct btrfs_path *path;
994 995 996 997
	u64 last = 0;
	u64 start;
	u64 end;
	u64 ptr;
C
Chris Mason 已提交
998

999
	block_group_cache = &root->fs_info->block_group_cache;
C
Chris Mason 已提交
1000 1001 1002 1003 1004
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

	while(1) {
1005 1006 1007
		ret = find_first_extent_bit(block_group_cache, last,
					    &start, &end, BLOCK_GROUP_DIRTY);
		if (ret)
C
Chris Mason 已提交
1008
			break;
1009

1010 1011 1012 1013
		last = end + 1;
		ret = get_state_private(block_group_cache, start, &ptr);
		if (ret)
			break;
J
Jens Axboe 已提交
1014
		cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
1015 1016 1017 1018 1019 1020 1021 1022 1023 1024
		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 已提交
1025
		}
1026 1027
		clear_extent_bits(block_group_cache, start, end,
				  BLOCK_GROUP_DIRTY, GFP_NOFS);
C
Chris Mason 已提交
1028 1029 1030 1031 1032
	}
	btrfs_free_path(path);
	return werr;
}

1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047
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;

}

1048 1049 1050 1051 1052 1053 1054 1055 1056 1057
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;
1058
		found->full = 0;
1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076
		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;
	*space_info = found;
	return 0;
}

1077 1078 1079
static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
{
	u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1080
				   BTRFS_BLOCK_GROUP_RAID1 |
C
Chris Mason 已提交
1081
				   BTRFS_BLOCK_GROUP_RAID10 |
1082
				   BTRFS_BLOCK_GROUP_DUP);
1083 1084 1085 1086 1087 1088 1089 1090 1091
	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;
	}
}
1092

1093
static u64 reduce_alloc_profile(struct btrfs_root *root, u64 flags)
1094
{
1095 1096 1097 1098 1099 1100 1101
	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;

1102 1103
	if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
	    (flags & (BTRFS_BLOCK_GROUP_RAID1 |
1104
		      BTRFS_BLOCK_GROUP_RAID10))) {
1105
		flags &= ~BTRFS_BLOCK_GROUP_DUP;
1106
	}
1107 1108

	if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
1109
	    (flags & BTRFS_BLOCK_GROUP_RAID10)) {
1110
		flags &= ~BTRFS_BLOCK_GROUP_RAID1;
1111
	}
1112 1113 1114 1115 1116 1117 1118 1119 1120

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

1121 1122 1123 1124 1125 1126 1127 1128 1129 1130
static int do_chunk_alloc(struct btrfs_trans_handle *trans,
			  struct btrfs_root *extent_root, u64 alloc_bytes,
			  u64 flags)
{
	struct btrfs_space_info *space_info;
	u64 thresh;
	u64 start;
	u64 num_bytes;
	int ret;

1131
	flags = reduce_alloc_profile(extent_root, flags);
1132

1133
	space_info = __find_space_info(extent_root->fs_info, flags);
1134 1135 1136 1137 1138
	if (!space_info) {
		ret = update_space_info(extent_root->fs_info, flags,
					0, 0, &space_info);
		BUG_ON(ret);
	}
1139 1140 1141 1142 1143
	BUG_ON(!space_info);

	if (space_info->full)
		return 0;

1144
	thresh = div_factor(space_info->total_bytes, 6);
1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158
	if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
	    thresh)
		return 0;

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

	BUG_ON(ret);

	ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1159
		     BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1160
	BUG_ON(ret);
1161

1162 1163 1164
	return 0;
}

C
Chris Mason 已提交
1165 1166
static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
1167
			      u64 bytenr, u64 num_bytes, int alloc,
1168
			      int mark_free)
C
Chris Mason 已提交
1169 1170 1171
{
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *info = root->fs_info;
1172
	u64 total = num_bytes;
C
Chris Mason 已提交
1173
	u64 old_val;
1174
	u64 byte_in_group;
1175 1176
	u64 start;
	u64 end;
C
Chris Mason 已提交
1177

C
Chris Mason 已提交
1178
	while(total) {
1179
		cache = btrfs_lookup_block_group(info, bytenr);
C
Chris Mason 已提交
1180
		if (!cache) {
C
Chris Mason 已提交
1181
			return -1;
C
Chris Mason 已提交
1182
		}
1183 1184
		byte_in_group = bytenr - cache->key.objectid;
		WARN_ON(byte_in_group > cache->key.offset);
1185 1186 1187 1188
		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 已提交
1189 1190

		old_val = btrfs_block_group_used(&cache->item);
1191
		num_bytes = min(total, cache->key.offset - byte_in_group);
C
Chris Mason 已提交
1192
		if (alloc) {
1193
			old_val += num_bytes;
1194
			cache->space_info->bytes_used += num_bytes;
C
Chris Mason 已提交
1195
		} else {
1196
			old_val -= num_bytes;
1197
			cache->space_info->bytes_used -= num_bytes;
1198 1199
			if (mark_free) {
				set_extent_dirty(&info->free_space_cache,
1200
						 bytenr, bytenr + num_bytes - 1,
1201
						 GFP_NOFS);
1202
			}
C
Chris Mason 已提交
1203
		}
C
Chris Mason 已提交
1204
		btrfs_set_block_group_used(&cache->item, old_val);
1205 1206
		total -= num_bytes;
		bytenr += num_bytes;
C
Chris Mason 已提交
1207 1208 1209
	}
	return 0;
}
1210

1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225
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;
}


1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241
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;

	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);
1242 1243 1244 1245 1246 1247 1248 1249
		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));
		}
1250
		if (pin) {
1251 1252 1253 1254
			if (cache) {
				cache->pinned += len;
				cache->space_info->bytes_pinned += len;
			}
1255 1256
			fs_info->total_pinned += len;
		} else {
1257 1258 1259 1260
			if (cache) {
				cache->pinned -= len;
				cache->space_info->bytes_pinned -= len;
			}
1261 1262 1263 1264 1265 1266 1267
			fs_info->total_pinned -= len;
		}
		bytenr += len;
		num -= len;
	}
	return 0;
}
C
Chris Mason 已提交
1268

1269
int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
C
Chris Mason 已提交
1270 1271
{
	u64 last = 0;
1272 1273
	u64 start;
	u64 end;
1274
	struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
C
Chris Mason 已提交
1275 1276 1277
	int ret;

	while(1) {
1278 1279 1280
		ret = find_first_extent_bit(pinned_extents, last,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
C
Chris Mason 已提交
1281
			break;
1282 1283
		set_extent_dirty(copy, start, end, GFP_NOFS);
		last = end + 1;
C
Chris Mason 已提交
1284 1285 1286 1287 1288 1289
	}
	return 0;
}

int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
1290
			       struct extent_io_tree *unpin)
1291
{
1292 1293
	u64 start;
	u64 end;
1294
	int ret;
1295
	struct extent_io_tree *free_space_cache;
1296
	free_space_cache = &root->fs_info->free_space_cache;
1297 1298

	while(1) {
1299 1300 1301
		ret = find_first_extent_bit(unpin, 0, &start, &end,
					    EXTENT_DIRTY);
		if (ret)
1302
			break;
1303
		update_pinned_extents(root, start, end + 1 - start, 0);
1304 1305
		clear_extent_dirty(unpin, start, end, GFP_NOFS);
		set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1306 1307 1308 1309
	}
	return 0;
}

1310 1311
static int finish_current_insert(struct btrfs_trans_handle *trans,
				 struct btrfs_root *extent_root)
C
Chris Mason 已提交
1312
{
1313 1314 1315
	u64 start;
	u64 end;
	struct btrfs_fs_info *info = extent_root->fs_info;
1316
	struct extent_buffer *eb;
1317
	struct btrfs_path *path;
C
Chris Mason 已提交
1318
	struct btrfs_key ins;
1319
	struct btrfs_disk_key first;
C
Chris Mason 已提交
1320
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
1321
	int ret;
1322
	int level;
1323
	int err = 0;
C
Chris Mason 已提交
1324

1325
	btrfs_set_stack_extent_refs(&extent_item, 1);
1326
	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1327
	path = btrfs_alloc_path();
C
Chris Mason 已提交
1328

1329
	while(1) {
1330 1331 1332
		ret = find_first_extent_bit(&info->extent_ins, 0, &start,
					    &end, EXTENT_LOCKED);
		if (ret)
1333 1334
			break;

1335 1336 1337 1338 1339 1340
		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);
1341 1342 1343 1344 1345 1346 1347
		eb = read_tree_block(extent_root, ins.objectid, ins.offset);
		level = btrfs_header_level(eb);
		if (level == 0) {
			btrfs_item_key(eb, &first, 0);
		} else {
			btrfs_node_key(eb, &first, 0);
		}
1348 1349
		err = btrfs_insert_extent_backref(trans, extent_root, path,
					  start, extent_root->root_key.objectid,
1350 1351
					  0, level,
					  btrfs_disk_key_objectid(&first));
1352
		BUG_ON(err);
1353
		free_extent_buffer(eb);
C
Chris Mason 已提交
1354
	}
1355
	btrfs_free_path(path);
C
Chris Mason 已提交
1356 1357 1358
	return 0;
}

1359 1360
static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
			  int pending)
C
Chris Mason 已提交
1361
{
1362
	int err = 0;
1363
	struct extent_buffer *buf;
C
Chris Mason 已提交
1364

C
Chris Mason 已提交
1365
	if (!pending) {
1366
		buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1367 1368
		if (buf) {
			if (btrfs_buffer_uptodate(buf)) {
C
Chris Mason 已提交
1369 1370
				u64 transid =
				    root->fs_info->running_transaction->transid;
C
Chris Mason 已提交
1371 1372
				u64 header_transid =
					btrfs_header_generation(buf);
1373 1374 1375
				if (header_transid == transid &&
				    !btrfs_header_flag(buf,
					       BTRFS_HEADER_FLAG_WRITTEN)) {
1376
					clean_tree_block(NULL, root, buf);
1377
					free_extent_buffer(buf);
1378
					return 1;
C
Chris Mason 已提交
1379
				}
C
Chris Mason 已提交
1380
			}
1381
			free_extent_buffer(buf);
C
Chris Mason 已提交
1382
		}
1383
		update_pinned_extents(root, bytenr, num_bytes, 1);
C
Chris Mason 已提交
1384
	} else {
1385
		set_extent_bits(&root->fs_info->pending_del,
1386 1387
				bytenr, bytenr + num_bytes - 1,
				EXTENT_LOCKED, GFP_NOFS);
C
Chris Mason 已提交
1388
	}
C
Chris Mason 已提交
1389
	BUG_ON(err < 0);
C
Chris Mason 已提交
1390 1391 1392
	return 0;
}

1393
/*
1394
 * remove an extent from the root, returns 0 on success
1395
 */
1396
static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1397 1398 1399
			 *root, u64 bytenr, u64 num_bytes,
			 u64 root_objectid, u64 ref_generation,
			 u64 owner_objectid, u64 owner_offset, int pin,
1400
			 int mark_free)
1401
{
1402
	struct btrfs_path *path;
C
Chris Mason 已提交
1403
	struct btrfs_key key;
1404 1405
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
1406
	struct extent_buffer *leaf;
1407
	int ret;
1408 1409 1410
	int extent_slot = 0;
	int found_extent = 0;
	int num_to_del = 1;
C
Chris Mason 已提交
1411
	struct btrfs_extent_item *ei;
C
Chris Mason 已提交
1412
	u32 refs;
C
Chris Mason 已提交
1413

1414
	key.objectid = bytenr;
1415
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1416
	key.offset = num_bytes;
1417
	path = btrfs_alloc_path();
1418 1419
	if (!path)
		return -ENOMEM;
1420

1421
	path->reada = 1;
1422 1423 1424 1425 1426
	ret = lookup_extent_backref(trans, extent_root, path,
				    bytenr, root_objectid,
				    ref_generation,
				    owner_objectid, owner_offset, 1);
	if (ret == 0) {
1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444
		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);
1445 1446 1447 1448 1449 1450 1451 1452
	} 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);
	}
1453 1454 1455 1456 1457 1458 1459 1460
	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];
	}
1461 1462

	leaf = path->nodes[0];
1463
	ei = btrfs_item_ptr(leaf, extent_slot,
C
Chris Mason 已提交
1464
			    struct btrfs_extent_item);
1465 1466 1467 1468
	refs = btrfs_extent_refs(leaf, ei);
	BUG_ON(refs == 0);
	refs -= 1;
	btrfs_set_extent_refs(leaf, ei, refs);
1469

1470 1471
	btrfs_mark_buffer_dirty(leaf);

1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492
	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 已提交
1493
	if (refs == 0) {
1494 1495
		u64 super_used;
		u64 root_used;
C
Chris Mason 已提交
1496 1497

		if (pin) {
1498
			ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1499 1500 1501
			if (ret > 0)
				mark_free = 1;
			BUG_ON(ret < 0);
C
Chris Mason 已提交
1502 1503
		}

1504
		/* block accounting for super block */
1505 1506 1507
		super_used = btrfs_super_bytes_used(&info->super_copy);
		btrfs_set_super_bytes_used(&info->super_copy,
					   super_used - num_bytes);
1508 1509

		/* block accounting for root item */
1510
		root_used = btrfs_root_used(&root->root_item);
1511
		btrfs_set_root_used(&root->root_item,
1512
					   root_used - num_bytes);
1513 1514
		ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
				      num_to_del);
1515 1516 1517
		if (ret) {
			return ret;
		}
1518
		ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1519
					 mark_free);
C
Chris Mason 已提交
1520
		BUG_ON(ret);
1521
	}
1522
	btrfs_free_path(path);
1523
	finish_current_insert(trans, extent_root);
1524 1525 1526 1527 1528 1529 1530
	return ret;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
1531 1532
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root)
1533 1534
{
	int ret;
C
Chris Mason 已提交
1535
	int err = 0;
1536 1537
	u64 start;
	u64 end;
1538 1539
	struct extent_io_tree *pending_del;
	struct extent_io_tree *pinned_extents;
C
Chris Mason 已提交
1540

1541 1542
	pending_del = &extent_root->fs_info->pending_del;
	pinned_extents = &extent_root->fs_info->pinned_extents;
1543 1544

	while(1) {
1545 1546 1547
		ret = find_first_extent_bit(pending_del, 0, &start, &end,
					    EXTENT_LOCKED);
		if (ret)
1548
			break;
1549
		update_pinned_extents(extent_root, start, end + 1 - start, 1);
1550 1551 1552
		clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
				  GFP_NOFS);
		ret = __free_extent(trans, extent_root,
1553 1554 1555
				     start, end + 1 - start,
				     extent_root->root_key.objectid,
				     0, 0, 0, 0, 0);
1556 1557
		if (ret)
			err = ret;
1558
	}
C
Chris Mason 已提交
1559
	return err;
1560 1561 1562 1563 1564
}

/*
 * remove an extent from the root, returns 0 on success
 */
1565
int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1566 1567 1568
		      *root, u64 bytenr, u64 num_bytes,
		      u64 root_objectid, u64 ref_generation,
		      u64 owner_objectid, u64 owner_offset, int pin)
1569
{
1570
	struct btrfs_root *extent_root = root->fs_info->extent_root;
1571 1572
	int pending_ret;
	int ret;
1573

1574
	WARN_ON(num_bytes < root->sectorsize);
1575 1576 1577
	if (!root->ref_cows)
		ref_generation = 0;

1578
	if (root == extent_root) {
1579
		pin_down_bytes(root, bytenr, num_bytes, 1);
1580 1581
		return 0;
	}
1582 1583 1584
	ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
			    ref_generation, owner_objectid, owner_offset,
			    pin, pin == 0);
C
Chris Mason 已提交
1585
	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1586 1587 1588
	return ret ? ret : pending_ret;
}

1589 1590 1591 1592 1593 1594 1595
static u64 stripe_align(struct btrfs_root *root, u64 val)
{
	u64 mask = ((u64)root->stripesize - 1);
	u64 ret = (val + mask) & ~mask;
	return ret;
}

1596 1597 1598 1599
/*
 * 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
1600
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
1601 1602 1603
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
1604 1605 1606 1607 1608 1609 1610
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)
1611
{
1612
	int ret;
1613
	u64 orig_search_start;
1614
	struct btrfs_root * root = orig_root->fs_info->extent_root;
1615
	struct btrfs_fs_info *info = root->fs_info;
1616
	u64 total_needed = num_bytes;
1617
	u64 *last_ptr = NULL;
C
Chris Mason 已提交
1618
	struct btrfs_block_group_cache *block_group;
C
Chris Mason 已提交
1619
	int full_scan = 0;
1620
	int wrapped = 0;
1621
	int empty_cluster = 2 * 1024 * 1024;
1622

1623
	WARN_ON(num_bytes < root->sectorsize);
1624 1625
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);

1626 1627
	if (data & BTRFS_BLOCK_GROUP_METADATA) {
		last_ptr = &root->fs_info->last_alloc;
1628
		empty_cluster = 256 * 1024;
1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642
	}

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

1643 1644 1645
	search_start = max(search_start, first_logical_byte(root, 0));
	orig_search_start = search_start;

1646 1647
	if (search_end == (u64)-1)
		search_end = btrfs_super_total_bytes(&info->super_copy);
1648

1649 1650
	if (hint_byte) {
		block_group = btrfs_lookup_block_group(info, hint_byte);
1651 1652
		if (!block_group)
			hint_byte = search_start;
C
Chris Mason 已提交
1653
		block_group = btrfs_find_block_group(root, block_group,
1654
						     hint_byte, data, 1);
1655 1656
		if (last_ptr && *last_ptr == 0 && block_group)
			hint_byte = block_group->key.objectid;
C
Chris Mason 已提交
1657 1658
	} else {
		block_group = btrfs_find_block_group(root,
1659 1660
						     trans->block_group,
						     search_start, data, 1);
C
Chris Mason 已提交
1661
	}
1662
	search_start = max(search_start, hint_byte);
C
Chris Mason 已提交
1663

1664
	total_needed += empty_size;
1665

C
Chris Mason 已提交
1666
check_failed:
1667 1668 1669 1670 1671 1672
	if (!block_group) {
		block_group = btrfs_lookup_block_group(info, search_start);
		if (!block_group)
			block_group = btrfs_lookup_block_group(info,
						       orig_search_start);
	}
1673 1674
	ret = find_search_start(root, &block_group, &search_start,
				total_needed, data);
1675 1676 1677 1678 1679 1680 1681 1682 1683 1684
	if (ret == -ENOSPC && last_ptr && *last_ptr) {
		*last_ptr = 0;
		block_group = btrfs_lookup_block_group(info,
						       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;
1685
	if (ret)
1686
		goto error;
1687

1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704
	if (last_ptr && *last_ptr && search_start != *last_ptr) {
		*last_ptr = 0;
		if (!empty_size) {
			empty_size += empty_cluster;
			total_needed += empty_size;
		}
		block_group = btrfs_lookup_block_group(info,
						       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;
	}

1705 1706 1707
	search_start = stripe_align(root, search_start);
	ins->objectid = search_start;
	ins->offset = num_bytes;
1708

1709
	if (ins->objectid + num_bytes >= search_end)
1710
		goto enospc;
1711 1712 1713

	if (ins->objectid + num_bytes >
	    block_group->key.objectid + block_group->key.offset) {
1714 1715 1716 1717
		search_start = block_group->key.objectid +
			block_group->key.offset;
		goto new_group;
	}
1718

1719
	if (test_range_bit(&info->extent_ins, ins->objectid,
1720 1721
			   ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
		search_start = ins->objectid + num_bytes;
1722 1723
		goto new_group;
	}
1724

1725
	if (test_range_bit(&info->pinned_extents, ins->objectid,
1726 1727
			   ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
		search_start = ins->objectid + num_bytes;
1728
		goto new_group;
1729
	}
1730

1731
	if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1732 1733 1734 1735
	    ins->objectid < exclude_start + exclude_nr)) {
		search_start = exclude_start + exclude_nr;
		goto new_group;
	}
1736

1737
	if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
1738
		block_group = btrfs_lookup_block_group(info, ins->objectid);
1739 1740
		if (block_group)
			trans->block_group = block_group;
1741
	}
1742
	ins->offset = num_bytes;
1743 1744 1745 1746 1747 1748 1749
	if (last_ptr) {
		*last_ptr = ins->objectid + ins->offset;
		if (*last_ptr ==
		    btrfs_super_total_bytes(&root->fs_info->super_copy)) {
			*last_ptr = 0;
		}
	}
1750
	return 0;
C
Chris Mason 已提交
1751 1752

new_group:
1753
	if (search_start + num_bytes >= search_end) {
1754
enospc:
C
Chris Mason 已提交
1755
		search_start = orig_search_start;
1756 1757 1758 1759
		if (full_scan) {
			ret = -ENOSPC;
			goto error;
		}
1760 1761 1762
		if (wrapped) {
			if (!full_scan)
				total_needed -= empty_size;
1763
			full_scan = 1;
1764
		} else
1765
			wrapped = 1;
C
Chris Mason 已提交
1766
	}
1767
	block_group = btrfs_lookup_block_group(info, search_start);
1768
	cond_resched();
1769 1770
	block_group = btrfs_find_block_group(root, block_group,
					     search_start, data, 0);
C
Chris Mason 已提交
1771 1772
	goto check_failed;

C
Chris Mason 已提交
1773 1774
error:
	return ret;
1775
}
1776

1777 1778 1779 1780 1781 1782 1783
/*
 * 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.
 */
1784
int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1785
		       struct btrfs_root *root,
1786 1787
		       u64 num_bytes, u64 min_alloc_size,
		       u64 root_objectid, u64 ref_generation,
1788 1789
		       u64 owner, u64 owner_offset,
		       u64 empty_size, u64 hint_byte,
1790
		       u64 search_end, struct btrfs_key *ins, u64 data)
1791 1792 1793
{
	int ret;
	int pending_ret;
C
Chris Mason 已提交
1794 1795
	u64 super_used;
	u64 root_used;
1796
	u64 search_start = 0;
1797
	u64 alloc_profile;
1798
	u32 sizes[2];
1799 1800
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
1801 1802
	struct btrfs_extent_item *extent_item;
	struct btrfs_extent_ref *ref;
1803
	struct btrfs_path *path;
1804
	struct btrfs_key keys[2];
1805

1806
	if (data) {
1807 1808 1809
		alloc_profile = info->avail_data_alloc_bits &
			        info->data_alloc_profile;
		data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
1810
	} else if (root == root->fs_info->chunk_root) {
1811 1812 1813
		alloc_profile = info->avail_system_alloc_bits &
			        info->system_alloc_profile;
		data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
1814
	} else {
1815 1816 1817
		alloc_profile = info->avail_metadata_alloc_bits &
			        info->metadata_alloc_profile;
		data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
1818
	}
1819
again:
1820
	data = reduce_alloc_profile(root, data);
1821
	if (root->ref_cows) {
1822
		if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
1823
			ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1824
					     2 * 1024 * 1024,
1825
					     BTRFS_BLOCK_GROUP_METADATA |
1826 1827
					     (info->metadata_alloc_profile &
					      info->avail_metadata_alloc_bits));
1828 1829 1830
			BUG_ON(ret);
		}
		ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1831
				     num_bytes + 2 * 1024 * 1024, data);
1832 1833
		BUG_ON(ret);
	}
1834

1835 1836 1837
	WARN_ON(num_bytes < root->sectorsize);
	ret = find_free_extent(trans, root, num_bytes, empty_size,
			       search_start, search_end, hint_byte, ins,
1838 1839
			       trans->alloc_exclude_start,
			       trans->alloc_exclude_nr, data);
1840

1841 1842 1843 1844 1845
	if (ret == -ENOSPC && num_bytes > min_alloc_size) {
		num_bytes = num_bytes >> 1;
		num_bytes = max(num_bytes, min_alloc_size);
		goto again;
	}
1846 1847 1848
	if (ret) {
		printk("allocation failed flags %Lu\n", data);
	}
C
Chris Mason 已提交
1849
	BUG_ON(ret);
1850 1851
	if (ret)
		return ret;
1852

1853
	/* block accounting for super block */
1854 1855
	super_used = btrfs_super_bytes_used(&info->super_copy);
	btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1856

1857
	/* block accounting for root item */
1858 1859
	root_used = btrfs_root_used(&root->root_item);
	btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1860

1861 1862 1863 1864
	clear_extent_dirty(&root->fs_info->free_space_cache,
			   ins->objectid, ins->objectid + ins->offset - 1,
			   GFP_NOFS);

1865
	if (root == extent_root) {
1866 1867 1868
		set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
				ins->objectid + ins->offset - 1,
				EXTENT_LOCKED, GFP_NOFS);
1869 1870 1871 1872 1873 1874
		goto update_block;
	}

	WARN_ON(trans->alloc_exclude_nr);
	trans->alloc_exclude_start = ins->objectid;
	trans->alloc_exclude_nr = ins->offset;
C
Chris Mason 已提交
1875

1876 1877 1878 1879 1880 1881 1882
	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);
1883 1884 1885

	path = btrfs_alloc_path();
	BUG_ON(!path);
1886 1887 1888

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

C
Chris Mason 已提交
1890
	BUG_ON(ret);
1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905
	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;
1906
	btrfs_free_path(path);
1907
	finish_current_insert(trans, extent_root);
C
Chris Mason 已提交
1908
	pending_ret = del_pending_extents(trans, extent_root);
1909

1910
	if (ret) {
C
Chris Mason 已提交
1911
		return ret;
1912 1913
	}
	if (pending_ret) {
C
Chris Mason 已提交
1914
		return pending_ret;
1915
	}
1916 1917

update_block:
1918
	ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
1919 1920 1921 1922 1923
	if (ret) {
		printk("update block group failed for %Lu %Lu\n",
		       ins->objectid, ins->offset);
		BUG();
	}
C
Chris Mason 已提交
1924
	return 0;
1925 1926 1927 1928 1929 1930
}

/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
1931
struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1932
					     struct btrfs_root *root,
1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960
					     u32 blocksize,
					     u64 root_objectid, u64 hint,
					     u64 empty_size)
{
	u64 ref_generation;

	if (root->ref_cows)
		ref_generation = trans->transid;
	else
		ref_generation = 0;


	return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
					ref_generation, 0, 0, hint, empty_size);
}

/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
					     struct btrfs_root *root,
					     u32 blocksize,
					     u64 root_objectid,
					     u64 ref_generation,
					     u64 first_objectid,
					     int level,
					     u64 hint,
1961
					     u64 empty_size)
1962
{
C
Chris Mason 已提交
1963
	struct btrfs_key ins;
1964
	int ret;
1965
	struct extent_buffer *buf;
1966

1967
	ret = btrfs_alloc_extent(trans, root, blocksize, blocksize,
1968
				 root_objectid, ref_generation,
1969
				 level, first_objectid, empty_size, hint,
1970
				 (u64)-1, &ins, 0);
1971
	if (ret) {
1972 1973
		BUG_ON(ret > 0);
		return ERR_PTR(ret);
1974
	}
1975
	buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1976
	if (!buf) {
1977 1978 1979
		btrfs_free_extent(trans, root, ins.objectid, blocksize,
				  root->root_key.objectid, ref_generation,
				  0, 0, 0);
1980 1981
		return ERR_PTR(-ENOMEM);
	}
1982 1983
	btrfs_set_header_generation(buf, trans->transid);
	clean_tree_block(trans, root, buf);
1984
	btrfs_set_buffer_uptodate(buf);
1985 1986 1987 1988 1989 1990

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

1991 1992
	set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
			 buf->start + buf->len - 1, GFP_NOFS);
1993 1994
	if (!btrfs_test_opt(root, SSD))
		btrfs_set_buffer_defrag(buf);
1995
	trans->blocks_used++;
1996 1997
	return buf;
}
1998

1999 2000 2001
static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
				  struct btrfs_root *root,
				  struct extent_buffer *leaf)
2002
{
2003 2004
	u64 leaf_owner;
	u64 leaf_generation;
2005
	struct btrfs_key key;
2006 2007 2008 2009 2010
	struct btrfs_file_extent_item *fi;
	int i;
	int nritems;
	int ret;

2011 2012
	BUG_ON(!btrfs_is_leaf(leaf));
	nritems = btrfs_header_nritems(leaf);
2013 2014 2015
	leaf_owner = btrfs_header_owner(leaf);
	leaf_generation = btrfs_header_generation(leaf);

2016
	for (i = 0; i < nritems; i++) {
2017
		u64 disk_bytenr;
2018 2019 2020

		btrfs_item_key_to_cpu(leaf, &key, i);
		if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2021 2022
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2023 2024
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
2025
			continue;
2026 2027 2028 2029
		/*
		 * FIXME make sure to insert a trans record that
		 * repeats the snapshot del on crash
		 */
2030 2031
		disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
		if (disk_bytenr == 0)
C
Chris Mason 已提交
2032
			continue;
2033
		ret = btrfs_free_extent(trans, root, disk_bytenr,
2034 2035 2036
				btrfs_file_extent_disk_num_bytes(leaf, fi),
				leaf_owner, leaf_generation,
				key.objectid, key.offset, 0);
2037 2038 2039 2040 2041
		BUG_ON(ret);
	}
	return 0;
}

2042
static void noinline reada_walk_down(struct btrfs_root *root,
2043 2044
				     struct extent_buffer *node,
				     int slot)
2045
{
2046
	u64 bytenr;
2047 2048
	u64 last = 0;
	u32 nritems;
2049
	u32 refs;
2050
	u32 blocksize;
2051 2052 2053 2054
	int ret;
	int i;
	int level;
	int skipped = 0;
2055

2056
	nritems = btrfs_header_nritems(node);
2057
	level = btrfs_header_level(node);
2058 2059 2060 2061
	if (level)
		return;

	for (i = slot; i < nritems && skipped < 32; i++) {
2062
		bytenr = btrfs_node_blockptr(node, i);
2063 2064 2065
		if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
			     (last > bytenr && last - bytenr > 32 * 1024))) {
			skipped++;
2066
			continue;
2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077
		}
		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;
			}
		}
2078
		mutex_unlock(&root->fs_info->fs_mutex);
2079
		ret = readahead_tree_block(root, bytenr, blocksize);
2080
		last = bytenr + blocksize;
2081 2082
		cond_resched();
		mutex_lock(&root->fs_info->fs_mutex);
2083 2084 2085 2086 2087
		if (ret)
			break;
	}
}

C
Chris Mason 已提交
2088 2089 2090 2091
/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
2092 2093 2094
static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct btrfs_path *path, int *level)
C
Chris Mason 已提交
2095
{
2096 2097 2098
	u64 root_owner;
	u64 root_gen;
	u64 bytenr;
2099 2100
	struct extent_buffer *next;
	struct extent_buffer *cur;
2101
	struct extent_buffer *parent;
2102
	u32 blocksize;
C
Chris Mason 已提交
2103 2104 2105
	int ret;
	u32 refs;

2106 2107
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
2108
	ret = lookup_extent_ref(trans, root,
2109 2110
				path->nodes[*level]->start,
				path->nodes[*level]->len, &refs);
C
Chris Mason 已提交
2111 2112 2113
	BUG_ON(ret);
	if (refs > 1)
		goto out;
2114

C
Chris Mason 已提交
2115 2116 2117
	/*
	 * walk down to the last node level and free all the leaves
	 */
2118
	while(*level >= 0) {
2119 2120
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
2121
		cur = path->nodes[*level];
2122

2123
		if (btrfs_header_level(cur) != *level)
C
Chris Mason 已提交
2124
			WARN_ON(1);
2125

2126
		if (path->slots[*level] >=
2127
		    btrfs_header_nritems(cur))
C
Chris Mason 已提交
2128
			break;
2129 2130 2131 2132 2133
		if (*level == 0) {
			ret = drop_leaf_ref(trans, root, cur);
			BUG_ON(ret);
			break;
		}
2134 2135 2136
		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
		blocksize = btrfs_level_size(root, *level - 1);
		ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
2137 2138
		BUG_ON(ret);
		if (refs != 1) {
2139 2140 2141
			parent = path->nodes[*level];
			root_owner = btrfs_header_owner(parent);
			root_gen = btrfs_header_generation(parent);
C
Chris Mason 已提交
2142
			path->slots[*level]++;
2143
			ret = btrfs_free_extent(trans, root, bytenr,
2144 2145
						blocksize, root_owner,
						root_gen, 0, 0, 1);
C
Chris Mason 已提交
2146 2147 2148
			BUG_ON(ret);
			continue;
		}
2149
		next = btrfs_find_tree_block(root, bytenr, blocksize);
2150 2151
		if (!next || !btrfs_buffer_uptodate(next)) {
			free_extent_buffer(next);
2152
			reada_walk_down(root, cur, path->slots[*level]);
2153 2154

			mutex_unlock(&root->fs_info->fs_mutex);
2155
			next = read_tree_block(root, bytenr, blocksize);
2156
			mutex_lock(&root->fs_info->fs_mutex);
2157

2158
			/* we've dropped the lock, double check */
2159 2160
			ret = lookup_extent_ref(trans, root, bytenr,
						blocksize, &refs);
2161 2162
			BUG_ON(ret);
			if (refs != 1) {
2163 2164 2165 2166
				parent = path->nodes[*level];
				root_owner = btrfs_header_owner(parent);
				root_gen = btrfs_header_generation(parent);

2167
				path->slots[*level]++;
2168
				free_extent_buffer(next);
2169 2170 2171 2172
				ret = btrfs_free_extent(trans, root, bytenr,
							blocksize,
							root_owner,
							root_gen, 0, 0, 1);
2173 2174 2175
				BUG_ON(ret);
				continue;
			}
2176 2177
		} else if (next) {
			btrfs_verify_block_csum(root, next);
2178
		}
2179
		WARN_ON(*level <= 0);
C
Chris Mason 已提交
2180
		if (path->nodes[*level-1])
2181
			free_extent_buffer(path->nodes[*level-1]);
C
Chris Mason 已提交
2182
		path->nodes[*level-1] = next;
2183
		*level = btrfs_header_level(next);
C
Chris Mason 已提交
2184 2185 2186
		path->slots[*level] = 0;
	}
out:
2187 2188
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
2189 2190 2191 2192 2193 2194 2195 2196 2197 2198

	if (path->nodes[*level] == root->node) {
		root_owner = root->root_key.objectid;
		parent = path->nodes[*level];
	} else {
		parent = path->nodes[*level + 1];
		root_owner = btrfs_header_owner(parent);
	}

	root_gen = btrfs_header_generation(parent);
2199
	ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
2200 2201
				path->nodes[*level]->len,
				root_owner, root_gen, 0, 0, 1);
2202
	free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
2203 2204 2205 2206 2207 2208
	path->nodes[*level] = NULL;
	*level += 1;
	BUG_ON(ret);
	return 0;
}

C
Chris Mason 已提交
2209 2210 2211 2212 2213
/*
 * 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
 */
2214 2215 2216
static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
				 struct btrfs_root *root,
				 struct btrfs_path *path, int *level)
C
Chris Mason 已提交
2217
{
2218 2219 2220
	u64 root_owner;
	u64 root_gen;
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
2221 2222 2223
	int i;
	int slot;
	int ret;
2224

C
Chris Mason 已提交
2225
	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
C
Chris Mason 已提交
2226
		slot = path->slots[i];
2227 2228 2229 2230
		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 已提交
2231 2232
			path->slots[i]++;
			*level = i;
2233
			WARN_ON(*level == 0);
2234
			btrfs_node_key(node, &disk_key, path->slots[i]);
2235
			memcpy(&root_item->drop_progress,
2236
			       &disk_key, sizeof(disk_key));
2237
			root_item->drop_level = i;
C
Chris Mason 已提交
2238 2239
			return 0;
		} else {
2240 2241 2242 2243 2244 2245 2246 2247 2248 2249
			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);
			}
2250
			ret = btrfs_free_extent(trans, root,
2251
						path->nodes[*level]->start,
2252 2253
						path->nodes[*level]->len,
						root_owner, root_gen, 0, 0, 1);
2254
			BUG_ON(ret);
2255
			free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
2256
			path->nodes[*level] = NULL;
C
Chris Mason 已提交
2257 2258 2259 2260 2261 2262
			*level = i + 1;
		}
	}
	return 1;
}

C
Chris Mason 已提交
2263 2264 2265 2266 2267
/*
 * 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.
 */
2268
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2269
			*root)
C
Chris Mason 已提交
2270
{
2271
	int ret = 0;
C
Chris Mason 已提交
2272
	int wret;
C
Chris Mason 已提交
2273
	int level;
2274
	struct btrfs_path *path;
C
Chris Mason 已提交
2275 2276
	int i;
	int orig_level;
2277
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
2278

2279 2280
	path = btrfs_alloc_path();
	BUG_ON(!path);
C
Chris Mason 已提交
2281

2282
	level = btrfs_header_level(root->node);
C
Chris Mason 已提交
2283
	orig_level = level;
2284 2285
	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
		path->nodes[level] = root->node;
2286
		extent_buffer_get(root->node);
2287 2288 2289
		path->slots[level] = 0;
	} else {
		struct btrfs_key key;
2290 2291
		struct btrfs_disk_key found_key;
		struct extent_buffer *node;
2292

2293
		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2294 2295
		level = root_item->drop_level;
		path->lowest_level = level;
2296
		wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2297
		if (wret < 0) {
2298 2299 2300
			ret = wret;
			goto out;
		}
2301 2302 2303 2304
		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)));
2305
	}
C
Chris Mason 已提交
2306
	while(1) {
2307
		wret = walk_down_tree(trans, root, path, &level);
C
Chris Mason 已提交
2308
		if (wret > 0)
C
Chris Mason 已提交
2309
			break;
C
Chris Mason 已提交
2310 2311 2312
		if (wret < 0)
			ret = wret;

2313
		wret = walk_up_tree(trans, root, path, &level);
C
Chris Mason 已提交
2314
		if (wret > 0)
C
Chris Mason 已提交
2315
			break;
C
Chris Mason 已提交
2316 2317
		if (wret < 0)
			ret = wret;
2318 2319
		ret = -EAGAIN;
		break;
C
Chris Mason 已提交
2320
	}
C
Chris Mason 已提交
2321
	for (i = 0; i <= orig_level; i++) {
2322
		if (path->nodes[i]) {
2323
			free_extent_buffer(path->nodes[i]);
2324
			path->nodes[i] = NULL;
C
Chris Mason 已提交
2325
		}
C
Chris Mason 已提交
2326
	}
2327
out:
2328
	btrfs_free_path(path);
C
Chris Mason 已提交
2329
	return ret;
C
Chris Mason 已提交
2330
}
C
Chris Mason 已提交
2331

2332
int btrfs_free_block_groups(struct btrfs_fs_info *info)
C
Chris Mason 已提交
2333
{
2334 2335
	u64 start;
	u64 end;
2336
	u64 ptr;
C
Chris Mason 已提交
2337 2338
	int ret;
	while(1) {
2339 2340 2341
		ret = find_first_extent_bit(&info->block_group_cache, 0,
					    &start, &end, (unsigned int)-1);
		if (ret)
C
Chris Mason 已提交
2342
			break;
2343 2344 2345
		ret = get_state_private(&info->block_group_cache, start, &ptr);
		if (!ret)
			kfree((void *)(unsigned long)ptr);
2346 2347
		clear_extent_bits(&info->block_group_cache, start,
				  end, (unsigned int)-1, GFP_NOFS);
C
Chris Mason 已提交
2348
	}
2349
	while(1) {
2350 2351 2352
		ret = find_first_extent_bit(&info->free_space_cache, 0,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
2353
			break;
2354 2355
		clear_extent_dirty(&info->free_space_cache, start,
				   end, GFP_NOFS);
2356
	}
C
Chris Mason 已提交
2357 2358 2359
	return 0;
}

2360 2361 2362 2363 2364 2365
static unsigned long calc_ra(unsigned long start, unsigned long last,
			     unsigned long nr)
{
	return min(last, start + nr - 1);
}

2366 2367
static int noinline relocate_inode_pages(struct inode *inode, u64 start,
					 u64 len)
2368 2369 2370 2371 2372 2373
{
	u64 page_start;
	u64 page_end;
	unsigned long last_index;
	unsigned long i;
	struct page *page;
2374
	struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
2375
	struct file_ra_state *ra;
2376 2377
	unsigned long total_read = 0;
	unsigned long ra_pages;
2378
	struct btrfs_trans_handle *trans;
2379 2380

	ra = kzalloc(sizeof(*ra), GFP_NOFS);
2381 2382

	mutex_lock(&inode->i_mutex);
2383
	i = start >> PAGE_CACHE_SHIFT;
2384 2385
	last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;

2386 2387
	ra_pages = BTRFS_I(inode)->root->fs_info->bdi.ra_pages;

2388
	file_ra_state_init(ra, inode->i_mapping);
2389

2390
	for (; i <= last_index; i++) {
2391 2392 2393 2394 2395
		if (total_read % ra_pages == 0) {
			btrfs_force_ra(inode->i_mapping, ra, NULL, i,
				       calc_ra(i, last_index, ra_pages));
		}
		total_read++;
2396 2397 2398
		if (((u64)i << PAGE_CACHE_SHIFT) > inode->i_size)
			goto truncate_racing;

2399
		page = grab_cache_page(inode->i_mapping, i);
2400
		if (!page) {
2401
			goto out_unlock;
2402
		}
2403 2404 2405 2406 2407 2408 2409 2410 2411
		if (!PageUptodate(page)) {
			btrfs_readpage(NULL, page);
			lock_page(page);
			if (!PageUptodate(page)) {
				unlock_page(page);
				page_cache_release(page);
				goto out_unlock;
			}
		}
2412 2413 2414 2415 2416 2417 2418
#if LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,18)
		ClearPageDirty(page);
#else
		cancel_dirty_page(page, PAGE_CACHE_SIZE);
#endif
		wait_on_page_writeback(page);
		set_page_extent_mapped(page);
2419 2420 2421
		page_start = (u64)page->index << PAGE_CACHE_SHIFT;
		page_end = page_start + PAGE_CACHE_SIZE - 1;

2422
		lock_extent(io_tree, page_start, page_end, GFP_NOFS);
2423

2424
		set_extent_delalloc(io_tree, page_start,
2425
				    page_end, GFP_NOFS);
2426
		set_page_dirty(page);
2427

2428
		unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
2429 2430 2431
		unlock_page(page);
		page_cache_release(page);
	}
2432 2433
	balance_dirty_pages_ratelimited_nr(inode->i_mapping,
					   total_read);
2434 2435

out_unlock:
2436
	kfree(ra);
2437 2438 2439 2440 2441 2442
	trans = btrfs_start_transaction(BTRFS_I(inode)->root, 1);
	if (trans) {
		btrfs_add_ordered_inode(inode);
		btrfs_end_transaction(trans, BTRFS_I(inode)->root);
		mark_inode_dirty(inode);
	}
2443 2444
	mutex_unlock(&inode->i_mutex);
	return 0;
2445 2446 2447 2448 2449 2450

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

2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531
/*
 * 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;
	int i;

	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);
		       }
		} else if (ret == 0) {
			if (path->nodes[level])
				found_bytenr = path->nodes[level]->start;
		}

		for (i = level; i < BTRFS_MAX_LEVEL; i++) {
			if (!path->nodes[i])
				break;
			free_extent_buffer(path->nodes[i]);
			path->nodes[i] = NULL;
		}
		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;
}

2532 2533 2534
/*
 * note, this releases the path
 */
2535
static int noinline relocate_one_reference(struct btrfs_root *extent_root,
2536
				  struct btrfs_path *path,
2537
				  struct btrfs_key *extent_key)
2538 2539 2540
{
	struct inode *inode;
	struct btrfs_root *found_root;
2541 2542
	struct btrfs_key root_location;
	struct btrfs_key found_key;
2543 2544 2545 2546 2547
	struct btrfs_extent_ref *ref;
	u64 ref_root;
	u64 ref_gen;
	u64 ref_objectid;
	u64 ref_offset;
2548
	int ret;
2549
	int level;
2550

2551 2552 2553 2554 2555 2556 2557 2558
	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);

2559
	root_location.objectid = ref_root;
2560
	if (ref_gen == 0)
2561
		root_location.offset = 0;
2562
	else
2563 2564
		root_location.offset = (u64)-1;
	root_location.type = BTRFS_ROOT_ITEM_KEY;
2565 2566

	found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
2567
						&root_location);
2568 2569 2570
	BUG_ON(!found_root);

	if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582
		found_key.objectid = ref_objectid;
		found_key.type = BTRFS_EXTENT_DATA_KEY;
		found_key.offset = ref_offset;
		level = 0;

		ret = find_root_for_ref(extent_root, path, &found_key,
					level, 1, &found_root,
					extent_key->objectid);

		if (ret)
			goto out;

2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621
		mutex_unlock(&extent_root->fs_info->fs_mutex);
		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
		 */
		if (is_bad_inode(inode)) {
			mutex_lock(&extent_root->fs_info->fs_mutex);
			goto out;
		}
		relocate_inode_pages(inode, ref_offset, extent_key->offset);
		iput(inode);
		mutex_lock(&extent_root->fs_info->fs_mutex);
	} else {
		struct btrfs_trans_handle *trans;
		struct extent_buffer *eb;
		int i;

		eb = read_tree_block(found_root, extent_key->objectid,
				     extent_key->offset);
		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);

		free_extent_buffer(eb);

2622 2623 2624 2625 2626 2627 2628 2629 2630
		ret = find_root_for_ref(extent_root, path, &found_key,
					level, 0, &found_root,
					extent_key->objectid);

		if (ret)
			goto out;

		trans = btrfs_start_transaction(found_root, 1);

2631
		path->lowest_level = level;
2632
		path->reada = 2;
2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649
		ret = btrfs_search_slot(trans, found_root, &found_key, path,
					0, 1);
		path->lowest_level = 0;
		for (i = level; i < BTRFS_MAX_LEVEL; i++) {
			if (!path->nodes[i])
				break;
			free_extent_buffer(path->nodes[i]);
			path->nodes[i] = NULL;
		}
		btrfs_release_path(found_root, path);
		btrfs_end_transaction(trans, found_root);
	}

out:
	return 0;
}

2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670
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;
}

2671 2672 2673
static int noinline relocate_one_extent(struct btrfs_root *extent_root,
					struct btrfs_path *path,
					struct btrfs_key *extent_key)
2674 2675 2676 2677 2678 2679 2680 2681
{
	struct btrfs_key key;
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
	u32 nritems;
	u32 item_size;
	int ret = 0;

2682 2683 2684 2685
	if (extent_key->objectid == 0) {
		ret = del_extent_zero(extent_root, path, extent_key);
		goto out;
	}
2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698
	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);
2699 2700 2701 2702 2703 2704 2705 2706
		if (path->slots[0] == nritems) {
			ret = btrfs_next_leaf(extent_root, path);
			if (ret > 0) {
				ret = 0;
				goto out;
			}
			if (ret < 0)
				goto out;
2707
			leaf = path->nodes[0];
2708
		}
2709 2710

		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2711
		if (found_key.objectid != extent_key->objectid) {
2712
			break;
2713
		}
2714

2715
		if (found_key.type != BTRFS_EXTENT_REF_KEY) {
2716
			break;
2717
		}
2718 2719 2720 2721

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

2722
		ret = relocate_one_reference(extent_root, path, extent_key);
2723 2724 2725 2726 2727 2728 2729 2730 2731
		if (ret)
			goto out;
	}
	ret = 0;
out:
	btrfs_release_path(extent_root, path);
	return ret;
}

2732 2733 2734 2735 2736 2737
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;

2738
	num_devices = root->fs_info->fs_devices->num_devices;
2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769
	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;
}

2770
int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 shrink_start)
2771 2772 2773 2774 2775 2776
{
	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;
2777
	u64 shrink_last_byte;
2778
	u64 new_alloc_flags;
2779
	struct btrfs_block_group_cache *shrink_block_group;
2780 2781
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_key key;
2782
	struct btrfs_key found_key;
2783 2784 2785
	struct extent_buffer *leaf;
	u32 nritems;
	int ret;
2786
	int progress;
2787

2788 2789 2790 2791 2792 2793 2794 2795
	shrink_block_group = btrfs_lookup_block_group(root->fs_info,
						      shrink_start);
	BUG_ON(!shrink_block_group);

	shrink_last_byte = shrink_start + shrink_block_group->key.offset;

	shrink_block_group->space_info->total_bytes -=
		shrink_block_group->key.offset;
2796 2797
	path = btrfs_alloc_path();
	root = root->fs_info->extent_root;
2798
	path->reada = 2;
2799 2800

again:
2801 2802 2803 2804 2805
	if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
		trans = btrfs_start_transaction(root, 1);
		new_alloc_flags = update_block_group_flags(root,
						   shrink_block_group->flags);
		do_chunk_alloc(trans, root->fs_info->extent_root,
2806
			btrfs_block_group_used(&shrink_block_group->item) +
2807 2808 2809
			2 * 1024 * 1024, new_alloc_flags);
		btrfs_end_transaction(trans, root);
	}
2810 2811
	shrink_block_group->ro = 1;

2812
	total_found = 0;
2813
	progress = 0;
2814
	key.objectid = shrink_start;
2815 2816
	key.offset = 0;
	key.type = 0;
2817
	cur_byte = key.objectid;
2818

2819 2820 2821 2822
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		goto out;

2823
	ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
2824 2825
	if (ret < 0)
		goto out;
2826

2827 2828 2829
	if (ret == 0) {
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2830 2831
		if (found_key.objectid + found_key.offset > shrink_start &&
		    found_key.objectid < shrink_last_byte) {
2832 2833 2834 2835 2836 2837 2838
			cur_byte = found_key.objectid;
			key.objectid = cur_byte;
		}
	}
	btrfs_release_path(root, path);

	while(1) {
2839 2840 2841
		ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
		if (ret < 0)
			goto out;
2842

2843
		leaf = path->nodes[0];
2844 2845 2846 2847 2848 2849 2850 2851 2852
		nritems = btrfs_header_nritems(leaf);
next:
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(root, path);
			if (ret < 0)
				goto out;
			if (ret == 1) {
				ret = 0;
				break;
2853
			}
2854 2855
			leaf = path->nodes[0];
			nritems = btrfs_header_nritems(leaf);
2856
		}
2857 2858

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

2860 2861 2862
		if (found_key.objectid >= shrink_last_byte)
			break;

2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874
		if (progress && need_resched()) {
			memcpy(&key, &found_key, sizeof(key));
			mutex_unlock(&root->fs_info->fs_mutex);
			cond_resched();
			mutex_lock(&root->fs_info->fs_mutex);
			btrfs_release_path(root, path);
			btrfs_search_slot(NULL, root, &key, path, 0, 0);
			progress = 0;
			goto next;
		}
		progress = 1;

2875 2876
		if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
		    found_key.objectid + found_key.offset <= cur_byte) {
2877 2878 2879
			path->slots[0]++;
			goto next;
		}
2880

2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902
		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);
	}

	btrfs_release_path(root, path);

	if (total_found > 0) {
		trans = btrfs_start_transaction(tree_root, 1);
		btrfs_commit_transaction(trans, tree_root);

		mutex_unlock(&root->fs_info->fs_mutex);
		btrfs_clean_old_snapshots(tree_root);
		mutex_lock(&root->fs_info->fs_mutex);

		trans = btrfs_start_transaction(tree_root, 1);
		btrfs_commit_transaction(trans, tree_root);
		goto again;
	}

2903 2904 2905 2906
	/*
	 * we've freed all the extents, now remove the block
	 * group item from the tree
	 */
2907
	trans = btrfs_start_transaction(root, 1);
2908
	memcpy(&key, &shrink_block_group->key, sizeof(key));
2909

2910 2911 2912 2913 2914
	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
	if (ret > 0)
		ret = -EIO;
	if (ret < 0)
		goto out;
2915

2916 2917 2918 2919
	leaf = path->nodes[0];
	nritems = btrfs_header_nritems(leaf);
	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
	kfree(shrink_block_group);
2920

2921 2922 2923
	clear_extent_bits(&info->block_group_cache, found_key.objectid,
			  found_key.objectid + found_key.offset - 1,
			  (unsigned int)-1, GFP_NOFS);
2924

2925 2926 2927
	btrfs_del_item(trans, root, path);
	clear_extent_dirty(&info->free_space_cache,
			   shrink_start, shrink_last_byte - 1,
2928 2929 2930 2931 2932 2933 2934
			   GFP_NOFS);
	btrfs_commit_transaction(trans, root);
out:
	btrfs_free_path(path);
	return ret;
}

2935 2936 2937 2938 2939 2940 2941
int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
			   struct btrfs_key *key)
{
	int ret;
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
	int slot;
2942

2943 2944 2945 2946 2947
	ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
	if (ret < 0)
		return ret;
	while(1) {
		slot = path->slots[0];
2948
		leaf = path->nodes[0];
2949 2950 2951 2952 2953 2954 2955
		if (slot >= btrfs_header_nritems(leaf)) {
			ret = btrfs_next_leaf(root, path);
			if (ret == 0)
				continue;
			if (ret < 0)
				goto error;
			break;
2956
		}
2957
		btrfs_item_key_to_cpu(leaf, &found_key, slot);
2958

2959 2960 2961 2962
		if (found_key.objectid >= key->objectid &&
		    found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
			return 0;
		path->slots[0]++;
2963
	}
2964 2965 2966
	ret = -ENOENT;
error:
	return ret;
2967 2968
}

C
Chris Mason 已提交
2969 2970 2971 2972
int btrfs_read_block_groups(struct btrfs_root *root)
{
	struct btrfs_path *path;
	int ret;
2973
	int bit;
C
Chris Mason 已提交
2974
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
2975
	struct btrfs_fs_info *info = root->fs_info;
2976
	struct btrfs_space_info *space_info;
2977
	struct extent_io_tree *block_group_cache;
C
Chris Mason 已提交
2978 2979
	struct btrfs_key key;
	struct btrfs_key found_key;
2980
	struct extent_buffer *leaf;
2981 2982

	block_group_cache = &info->block_group_cache;
C
Chris Mason 已提交
2983
	root = info->extent_root;
C
Chris Mason 已提交
2984
	key.objectid = 0;
2985
	key.offset = 0;
C
Chris Mason 已提交
2986 2987 2988 2989 2990 2991
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

	while(1) {
2992 2993 2994 2995
		ret = find_first_block_group(root, path, &key);
		if (ret > 0) {
			ret = 0;
			goto error;
C
Chris Mason 已提交
2996
		}
2997 2998 2999
		if (ret != 0)
			goto error;

3000 3001
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3002
		cache = kzalloc(sizeof(*cache), GFP_NOFS);
C
Chris Mason 已提交
3003
		if (!cache) {
3004
			ret = -ENOMEM;
C
Chris Mason 已提交
3005 3006
			break;
		}
C
Chris Mason 已提交
3007

3008 3009 3010
		read_extent_buffer(leaf, &cache->item,
				   btrfs_item_ptr_offset(leaf, path->slots[0]),
				   sizeof(cache->item));
C
Chris Mason 已提交
3011
		memcpy(&cache->key, &found_key, sizeof(found_key));
3012

C
Chris Mason 已提交
3013 3014
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
3015 3016 3017
		cache->flags = btrfs_block_group_flags(&cache->item);
		bit = 0;
		if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
3018
			bit = BLOCK_GROUP_DATA;
3019 3020 3021
		} else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
			bit = BLOCK_GROUP_SYSTEM;
		} else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
3022
			bit = BLOCK_GROUP_METADATA;
3023
		}
3024
		set_avail_alloc_bits(info, cache->flags);
3025

3026 3027 3028 3029 3030 3031
		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;

3032 3033 3034 3035 3036
		/* use EXTENT_LOCKED to prevent merging */
		set_extent_bits(block_group_cache, found_key.objectid,
				found_key.objectid + found_key.offset - 1,
				bit | EXTENT_LOCKED, GFP_NOFS);
		set_state_private(block_group_cache, found_key.objectid,
J
Jens Axboe 已提交
3037
				  (unsigned long)cache);
3038

C
Chris Mason 已提交
3039
		if (key.objectid >=
3040
		    btrfs_super_total_bytes(&info->super_copy))
C
Chris Mason 已提交
3041 3042
			break;
	}
3043 3044
	ret = 0;
error:
C
Chris Mason 已提交
3045
	btrfs_free_path(path);
3046
	return ret;
C
Chris Mason 已提交
3047
}
3048 3049 3050

int btrfs_make_block_group(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root, u64 bytes_used,
3051
			   u64 type, u64 chunk_objectid, u64 chunk_offset,
3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062
			   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;

	extent_root = root->fs_info->extent_root;
	block_group_cache = &root->fs_info->block_group_cache;

3063
	cache = kzalloc(sizeof(*cache), GFP_NOFS);
3064
	BUG_ON(!cache);
3065
	cache->key.objectid = chunk_offset;
3066
	cache->key.offset = size;
3067

3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078
	btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
	memset(&cache->item, 0, sizeof(cache->item));
	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 已提交
3079
	bit = block_group_state_bits(type);
3080 3081
	set_extent_bits(block_group_cache, chunk_offset,
			chunk_offset + size - 1,
3082 3083
			bit | EXTENT_LOCKED, GFP_NOFS);

3084 3085
	set_state_private(block_group_cache, chunk_offset,
			  (unsigned long)cache);
3086 3087 3088 3089 3090 3091 3092
	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 已提交
3093
	set_avail_alloc_bits(extent_root->fs_info, type);
3094 3095
	return 0;
}