extent-tree.c 69.6 KB
Newer Older
C
Chris Mason 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * 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 已提交
19
#include <linux/sched.h>
20
#include <linux/crc32c.h>
21
#include <linux/pagemap.h>
22
#include "hash.h"
23 24 25
#include "ctree.h"
#include "disk-io.h"
#include "print-tree.h"
26
#include "transaction.h"
27

28 29 30 31
#define BLOCK_GROUP_DATA EXTENT_WRITEBACK
#define BLOCK_GROUP_METADATA EXTENT_UPTODATE
#define BLOCK_GROUP_DIRTY EXTENT_DIRTY

32 33
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root);
C
Chris Mason 已提交
34 35
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root);
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
static int find_previous_extent(struct btrfs_root *root,
				struct btrfs_path *path)
{
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
	int ret;

	while(1) {
		if (path->slots[0] == 0) {
			ret = btrfs_prev_leaf(root, path);
			if (ret != 0)
				return ret;
		} else {
			path->slots[0]--;
		}
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.type == BTRFS_EXTENT_ITEM_KEY)
			return 0;
	}
	return 1;
}
58

59 60 61 62 63 64
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;
65
	struct extent_buffer *leaf;
66
	struct extent_map_tree *free_space_cache;
67 68 69
	int slot;
	u64 last = 0;
	u64 hole_size;
70
	u64 first_free;
71 72
	int found = 0;

73 74 75
	if (!block_group)
		return 0;

76
	root = root->fs_info->extent_root;
77
	free_space_cache = &root->fs_info->free_space_cache;
78 79 80

	if (block_group->cached)
		return 0;
81

82 83 84
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
85

86
	path->reada = 2;
87
	first_free = block_group->key.objectid;
88 89 90 91 92 93
	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;
94 95 96 97 98 99 100 101 102
	ret = find_previous_extent(root, path);
	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;
	}
103
	while(1) {
104
		leaf = path->nodes[0];
105
		slot = path->slots[0];
106
		if (slot >= btrfs_header_nritems(leaf)) {
107
			ret = btrfs_next_leaf(root, path);
108 109
			if (ret < 0)
				goto err;
110
			if (ret == 0) {
111
				continue;
112
			} else {
113 114 115
				break;
			}
		}
116
		btrfs_item_key_to_cpu(leaf, &key, slot);
117 118 119
		if (key.objectid < block_group->key.objectid) {
			goto next;
		}
120 121 122 123
		if (key.objectid >= block_group->key.objectid +
		    block_group->key.offset) {
			break;
		}
124

125 126
		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
			if (!found) {
127
				last = first_free;
128 129
				found = 1;
			}
130 131 132 133 134
			if (key.objectid > last) {
				hole_size = key.objectid - last;
				set_extent_dirty(free_space_cache, last,
						 last + hole_size - 1,
						 GFP_NOFS);
135 136
			}
			last = key.objectid + key.offset;
137
		}
138
next:
139 140 141
		path->slots[0]++;
	}

142 143 144 145 146 147
	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;
148 149
		set_extent_dirty(free_space_cache, last,
				 last + hole_size - 1, GFP_NOFS);
150
	}
151
	block_group->cached = 1;
152
err:
153 154 155 156
	btrfs_free_path(path);
	return 0;
}

157 158
struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
							 btrfs_fs_info *info,
159
							 u64 bytenr)
C
Chris Mason 已提交
160
{
161 162 163 164 165
	struct extent_map_tree *block_group_cache;
	struct btrfs_block_group_cache *block_group = NULL;
	u64 ptr;
	u64 start;
	u64 end;
C
Chris Mason 已提交
166 167
	int ret;

168 169
	block_group_cache = &info->block_group_cache;
	ret = find_first_extent_bit(block_group_cache,
170
				    bytenr, &start, &end,
171
				    BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA);
C
Chris Mason 已提交
172
	if (ret) {
173
		return NULL;
C
Chris Mason 已提交
174
	}
175 176 177 178
	ret = get_state_private(block_group_cache, start, &ptr);
	if (ret)
		return NULL;

J
Jens Axboe 已提交
179
	block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
Y
Yan 已提交
180
	if (block_group->key.objectid <= bytenr && bytenr <
181 182
	    block_group->key.objectid + block_group->key.offset)
		return block_group;
C
Chris Mason 已提交
183 184
	return NULL;
}
185 186
static u64 noinline find_search_start(struct btrfs_root *root,
			      struct btrfs_block_group_cache **cache_ret,
187
			      u64 search_start, int num, int data)
188 189 190
{
	int ret;
	struct btrfs_block_group_cache *cache = *cache_ret;
191
	u64 last;
192 193
	u64 start = 0;
	u64 end = 0;
194
	u64 cache_miss = 0;
C
Chris Mason 已提交
195
	u64 total_fs_bytes;
196
	int wrapped = 0;
197

198
	if (!cache) {
199
		goto out;
200
	}
C
Chris Mason 已提交
201
	total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
202
again:
203 204 205
	ret = cache_block_group(root, cache);
	if (ret)
		goto out;
206

207 208
	last = max(search_start, cache->key.objectid);

209
	while(1) {
210 211
		ret = find_first_extent_bit(&root->fs_info->free_space_cache,
					    last, &start, &end, EXTENT_DIRTY);
212
		if (ret) {
213 214
			if (!cache_miss)
				cache_miss = last;
215 216
			goto new_group;
		}
217 218 219

		start = max(last, start);
		last = end + 1;
220 221 222
		if (last - start < num) {
			if (last == cache->key.objectid + cache->key.offset)
				cache_miss = start;
223
			continue;
224 225
		}
		if (data != BTRFS_BLOCK_GROUP_MIXED &&
Y
Yan 已提交
226
		    start + num > cache->key.objectid + cache->key.offset)
227
			goto new_group;
C
Chris Mason 已提交
228 229
		if (start + num  > total_fs_bytes)
			goto new_group;
230
		return start;
231 232
	}
out:
233 234 235 236 237 238 239
	cache = btrfs_lookup_block_group(root->fs_info, search_start);
	if (!cache) {
		printk("Unable to find block group for %Lu\n",
		       search_start);
		WARN_ON(1);
		return search_start;
	}
240
	return search_start;
241 242

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

C
Chris Mason 已提交
269 270
static u64 div_factor(u64 num, int factor)
{
271 272
	if (factor == 10)
		return num;
C
Chris Mason 已提交
273 274 275 276 277
	num *= factor;
	do_div(num, 10);
	return num;
}

278 279
struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
						 struct btrfs_block_group_cache
C
Chris Mason 已提交
280
						 *hint, u64 search_start,
281
						 int data, int owner)
C
Chris Mason 已提交
282
{
283 284
	struct btrfs_block_group_cache *cache;
	struct extent_map_tree *block_group_cache;
285
	struct btrfs_block_group_cache *found_group = NULL;
C
Chris Mason 已提交
286 287
	struct btrfs_fs_info *info = root->fs_info;
	u64 used;
288 289
	u64 last = 0;
	u64 hint_last;
290 291 292 293
	u64 start;
	u64 end;
	u64 free_check;
	u64 ptr;
C
Chris Mason 已提交
294
	u64 total_fs_bytes;
295
	int bit;
C
Chris Mason 已提交
296
	int ret;
297
	int full_search = 0;
298
	int factor = 8;
C
Chris Mason 已提交
299
	int data_swap = 0;
300

301
	block_group_cache = &info->block_group_cache;
C
Chris Mason 已提交
302
	total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
303

304
	if (!owner)
305
		factor = 8;
C
Chris Mason 已提交
306

307
	if (data == BTRFS_BLOCK_GROUP_MIXED) {
308
		bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
309 310
		factor = 10;
	} else if (data)
311 312 313
		bit = BLOCK_GROUP_DATA;
	else
		bit = BLOCK_GROUP_METADATA;
C
Chris Mason 已提交
314

C
Chris Mason 已提交
315
	if (search_start && search_start < total_fs_bytes) {
C
Chris Mason 已提交
316
		struct btrfs_block_group_cache *shint;
317
		shint = btrfs_lookup_block_group(info, search_start);
318 319
		if (shint && (shint->data == data ||
			      shint->data == BTRFS_BLOCK_GROUP_MIXED)) {
C
Chris Mason 已提交
320
			used = btrfs_block_group_used(&shint->item);
321 322
			if (used + shint->pinned <
			    div_factor(shint->key.offset, factor)) {
C
Chris Mason 已提交
323 324 325 326
				return shint;
			}
		}
	}
C
Chris Mason 已提交
327 328
	if (hint && hint->key.objectid < total_fs_bytes &&
	    (hint->data == data || hint->data == BTRFS_BLOCK_GROUP_MIXED)) {
329
		used = btrfs_block_group_used(&hint->item);
330 331
		if (used + hint->pinned <
		    div_factor(hint->key.offset, factor)) {
332 333
			return hint;
		}
334
		last = hint->key.objectid + hint->key.offset;
335 336
		hint_last = last;
	} else {
337 338 339 340 341
		if (hint)
			hint_last = max(hint->key.objectid, search_start);
		else
			hint_last = search_start;

C
Chris Mason 已提交
342 343
		if (hint_last >= total_fs_bytes)
			hint_last = search_start;
344
		last = hint_last;
345 346
	}
again:
C
Chris Mason 已提交
347
	while(1) {
348 349 350
		ret = find_first_extent_bit(block_group_cache, last,
					    &start, &end, bit);
		if (ret)
C
Chris Mason 已提交
351
			break;
352 353 354 355 356

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

J
Jens Axboe 已提交
357
		cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
358 359 360
		last = cache->key.objectid + cache->key.offset;
		used = btrfs_block_group_used(&cache->item);

C
Chris Mason 已提交
361 362 363
		if (cache->key.objectid > total_fs_bytes)
			break;

364 365 366 367
		if (full_search)
			free_check = cache->key.offset;
		else
			free_check = div_factor(cache->key.offset, factor);
368
		if (used + cache->pinned < free_check) {
369 370
			found_group = cache;
			goto found;
C
Chris Mason 已提交
371
		}
372
		cond_resched();
C
Chris Mason 已提交
373
	}
374
	if (!full_search) {
C
Chris Mason 已提交
375
		last = search_start;
376 377 378
		full_search = 1;
		goto again;
	}
C
Chris Mason 已提交
379 380
	if (!data_swap) {
		data_swap = 1;
381
		bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
C
Chris Mason 已提交
382 383 384
		last = search_start;
		goto again;
	}
C
Chris Mason 已提交
385
found:
386
	return found_group;
C
Chris Mason 已提交
387 388
}

389
static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
390 391 392 393 394 395 396 397
			   u64 owner, u64 owner_offset)
{
	u32 high_crc = ~(u32)0;
	u32 low_crc = ~(u32)0;
	__le64 lenum;

	lenum = cpu_to_le64(root_objectid);
	high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
398 399
	lenum = cpu_to_le64(ref_generation);
	low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
400

401
#if 0
402 403 404 405
	lenum = cpu_to_le64(owner);
	low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
	lenum = cpu_to_le64(owner_offset);
	low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
406
#endif
407 408 409
	return ((u64)high_crc << 32) | (u64)low_crc;
}

410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425
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;
}

426 427 428 429 430 431
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)
432 433 434
{
	u64 hash;
	struct btrfs_key key;
435
	struct btrfs_key found_key;
436
	struct btrfs_extent_ref ref;
437 438 439 440 441 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
	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;
}

492 493 494 495 496 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
/*
 * 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:
 *
555
 * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
556 557 558 559 560
 *
 * 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):
 *
561
 * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579
 *
 * 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
 */
580 581 582 583 584 585 586 587 588 589
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;
590 591 592
	int ret;

	btrfs_set_stack_ref_root(&ref, root_objectid);
593
	btrfs_set_stack_ref_generation(&ref, ref_generation);
594 595 596
	btrfs_set_stack_ref_objectid(&ref, owner);
	btrfs_set_stack_ref_offset(&ref, owner_offset);

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

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

639
	WARN_ON(num_bytes < root->sectorsize);
640
	path = btrfs_alloc_path();
641 642
	if (!path)
		return -ENOMEM;
643

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

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

664
	path->reada = 0;
665 666 667 668
	ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
					  path, bytenr, root_objectid,
					  ref_generation, owner, owner_offset);
	BUG_ON(ret);
669
	finish_current_insert(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
670
	del_pending_extents(trans, root->fs_info->extent_root);
671 672

	btrfs_free_path(path);
C
Chris Mason 已提交
673 674 675
	return 0;
}

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

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

717 718 719 720 721 722 723 724
u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
				  struct btrfs_path *count_path,
				  u64 first_extent)
{
	struct btrfs_root *extent_root = root->fs_info->extent_root;
	struct btrfs_path *path;
	u64 bytenr;
	u64 found_objectid;
725
	u64 root_objectid = root->root_key.objectid;
726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763
	u32 total_count = 0;
	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);
	while (1) {
764
		l = path->nodes[0];
765 766 767 768 769 770 771 772 773 774
		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;
775

776 777 778 779 780 781 782 783 784 785
		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);

786 787
		if (found_objectid != root_objectid) {
			total_count = 2;
788
			goto out;
789 790
		}
		total_count = 1;
791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806
		path->slots[0]++;
	}
	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 已提交
807
int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
808
		       struct btrfs_root *root, u64 owner_objectid)
C
Chris Mason 已提交
809
{
810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827
	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;
	}
828
	return btrfs_inc_extent_ref(trans, root, root->node->start,
829
				    root->node->len, owner_objectid,
830
				    generation, level, key_objectid);
C
Chris Mason 已提交
831 832
}

833
int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
834
		  struct extent_buffer *buf)
C
Chris Mason 已提交
835
{
836
	u64 bytenr;
837 838
	u32 nritems;
	struct btrfs_key key;
839
	struct btrfs_file_extent_item *fi;
C
Chris Mason 已提交
840
	int i;
841
	int level;
842
	int ret;
843
	int faili;
844

845
	if (!root->ref_cows)
846
		return 0;
847

848
	level = btrfs_header_level(buf);
849 850
	nritems = btrfs_header_nritems(buf);
	for (i = 0; i < nritems; i++) {
851 852
		if (level == 0) {
			u64 disk_bytenr;
853 854
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
855
				continue;
856
			fi = btrfs_item_ptr(buf, i,
857
					    struct btrfs_file_extent_item);
858
			if (btrfs_file_extent_type(buf, fi) ==
859 860
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
861 862
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
C
Chris Mason 已提交
863
				continue;
864
			ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
865 866 867
				    btrfs_file_extent_disk_num_bytes(buf, fi),
				    root->root_key.objectid, trans->transid,
				    key.objectid, key.offset);
868 869 870 871
			if (ret) {
				faili = i;
				goto fail;
			}
872
		} else {
873
			bytenr = btrfs_node_blockptr(buf, i);
874
			btrfs_node_key_to_cpu(buf, &key, i);
875
			ret = btrfs_inc_extent_ref(trans, root, bytenr,
876 877
					   btrfs_level_size(root, level - 1),
					   root->root_key.objectid,
878 879
					   trans->transid,
					   level - 1, key.objectid);
880 881 882 883
			if (ret) {
				faili = i;
				goto fail;
			}
884
		}
C
Chris Mason 已提交
885 886
	}
	return 0;
887
fail:
C
Chris Mason 已提交
888
	WARN_ON(1);
889
#if 0
890
	for (i =0; i < faili; i++) {
891 892
		if (level == 0) {
			u64 disk_bytenr;
893 894
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
895
				continue;
896
			fi = btrfs_item_ptr(buf, i,
897
					    struct btrfs_file_extent_item);
898
			if (btrfs_file_extent_type(buf, fi) ==
899 900
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
901 902
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
903
				continue;
904 905
			err = btrfs_free_extent(trans, root, disk_bytenr,
				    btrfs_file_extent_disk_num_bytes(buf,
906
								      fi), 0);
907 908
			BUG_ON(err);
		} else {
909 910 911
			bytenr = btrfs_node_blockptr(buf, i);
			err = btrfs_free_extent(trans, root, bytenr,
					btrfs_level_size(root, level - 1), 0);
912 913 914
			BUG_ON(err);
		}
	}
915
#endif
916
	return ret;
C
Chris Mason 已提交
917 918
}

C
Chris Mason 已提交
919 920 921 922 923 924 925 926
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;
927 928
	unsigned long bi;
	struct extent_buffer *leaf;
C
Chris Mason 已提交
929 930

	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
931 932
	if (ret < 0)
		goto fail;
C
Chris Mason 已提交
933
	BUG_ON(ret);
934 935 936 937 938

	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 已提交
939
	btrfs_release_path(extent_root, path);
940
fail:
C
Chris Mason 已提交
941 942 943 944 945 946 947 948 949 950
	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;

}

951 952
int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root)
C
Chris Mason 已提交
953
{
954 955
	struct extent_map_tree *block_group_cache;
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
956 957 958 959
	int ret;
	int err = 0;
	int werr = 0;
	struct btrfs_path *path;
960 961 962 963
	u64 last = 0;
	u64 start;
	u64 end;
	u64 ptr;
C
Chris Mason 已提交
964

965
	block_group_cache = &root->fs_info->block_group_cache;
C
Chris Mason 已提交
966 967 968 969 970
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

	while(1) {
971 972 973
		ret = find_first_extent_bit(block_group_cache, last,
					    &start, &end, BLOCK_GROUP_DIRTY);
		if (ret)
C
Chris Mason 已提交
974
			break;
975

976 977 978 979 980
		last = end + 1;
		ret = get_state_private(block_group_cache, start, &ptr);
		if (ret)
			break;

J
Jens Axboe 已提交
981
		cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
982 983 984 985 986 987 988 989 990 991
		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 已提交
992
		}
993 994
		clear_extent_bits(block_group_cache, start, end,
				  BLOCK_GROUP_DIRTY, GFP_NOFS);
C
Chris Mason 已提交
995 996 997 998 999 1000 1001
	}
	btrfs_free_path(path);
	return werr;
}

static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
1002 1003
			      u64 bytenr, u64 num_bytes, int alloc,
			      int mark_free, int data)
C
Chris Mason 已提交
1004 1005 1006
{
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *info = root->fs_info;
1007
	u64 total = num_bytes;
C
Chris Mason 已提交
1008
	u64 old_val;
1009
	u64 byte_in_group;
1010 1011
	u64 start;
	u64 end;
C
Chris Mason 已提交
1012

C
Chris Mason 已提交
1013
	while(total) {
1014
		cache = btrfs_lookup_block_group(info, bytenr);
C
Chris Mason 已提交
1015
		if (!cache) {
C
Chris Mason 已提交
1016
			return -1;
C
Chris Mason 已提交
1017
		}
1018 1019
		byte_in_group = bytenr - cache->key.objectid;
		WARN_ON(byte_in_group > cache->key.offset);
1020 1021 1022 1023
		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 已提交
1024 1025

		old_val = btrfs_block_group_used(&cache->item);
1026
		num_bytes = min(total, cache->key.offset - byte_in_group);
C
Chris Mason 已提交
1027
		if (alloc) {
C
Chris Mason 已提交
1028
			if (cache->data != data &&
C
Chris Mason 已提交
1029
			    old_val < (cache->key.offset >> 1)) {
1030 1031 1032
				int bit_to_clear;
				int bit_to_set;
				cache->data = data;
C
Chris Mason 已提交
1033
				if (data) {
1034 1035
					bit_to_clear = BLOCK_GROUP_METADATA;
					bit_to_set = BLOCK_GROUP_DATA;
1036 1037
					cache->item.flags &=
						~BTRFS_BLOCK_GROUP_MIXED;
C
Chris Mason 已提交
1038 1039 1040
					cache->item.flags |=
						BTRFS_BLOCK_GROUP_DATA;
				} else {
1041 1042
					bit_to_clear = BLOCK_GROUP_DATA;
					bit_to_set = BLOCK_GROUP_METADATA;
1043 1044
					cache->item.flags &=
						~BTRFS_BLOCK_GROUP_MIXED;
C
Chris Mason 已提交
1045 1046 1047
					cache->item.flags &=
						~BTRFS_BLOCK_GROUP_DATA;
				}
1048 1049 1050 1051 1052 1053
				clear_extent_bits(&info->block_group_cache,
						  start, end, bit_to_clear,
						  GFP_NOFS);
				set_extent_bits(&info->block_group_cache,
						start, end, bit_to_set,
						GFP_NOFS);
1054 1055 1056 1057 1058 1059 1060 1061
			} else if (cache->data != data &&
				   cache->data != BTRFS_BLOCK_GROUP_MIXED) {
				cache->data = BTRFS_BLOCK_GROUP_MIXED;
				set_extent_bits(&info->block_group_cache,
						start, end,
						BLOCK_GROUP_DATA |
						BLOCK_GROUP_METADATA,
						GFP_NOFS);
C
Chris Mason 已提交
1062
			}
1063
			old_val += num_bytes;
C
Chris Mason 已提交
1064
		} else {
1065
			old_val -= num_bytes;
1066 1067
			if (mark_free) {
				set_extent_dirty(&info->free_space_cache,
1068
						 bytenr, bytenr + num_bytes - 1,
1069
						 GFP_NOFS);
1070
			}
C
Chris Mason 已提交
1071
		}
C
Chris Mason 已提交
1072
		btrfs_set_block_group_used(&cache->item, old_val);
1073 1074
		total -= num_bytes;
		bytenr += num_bytes;
C
Chris Mason 已提交
1075 1076 1077
	}
	return 0;
}
1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108
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);
		WARN_ON(!cache);
		len = min(num, cache->key.offset -
			  (bytenr - cache->key.objectid));
		if (pin) {
			cache->pinned += len;
			fs_info->total_pinned += len;
		} else {
			cache->pinned -= len;
			fs_info->total_pinned -= len;
		}
		bytenr += len;
		num -= len;
	}
	return 0;
}
C
Chris Mason 已提交
1109

1110
int btrfs_copy_pinned(struct btrfs_root *root, struct extent_map_tree *copy)
C
Chris Mason 已提交
1111 1112
{
	u64 last = 0;
1113 1114 1115
	u64 start;
	u64 end;
	struct extent_map_tree *pinned_extents = &root->fs_info->pinned_extents;
C
Chris Mason 已提交
1116 1117 1118
	int ret;

	while(1) {
1119 1120 1121
		ret = find_first_extent_bit(pinned_extents, last,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
C
Chris Mason 已提交
1122
			break;
1123 1124
		set_extent_dirty(copy, start, end, GFP_NOFS);
		last = end + 1;
C
Chris Mason 已提交
1125 1126 1127 1128 1129 1130
	}
	return 0;
}

int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
1131
			       struct extent_map_tree *unpin)
1132
{
1133 1134
	u64 start;
	u64 end;
1135
	int ret;
1136 1137
	struct extent_map_tree *free_space_cache;
	free_space_cache = &root->fs_info->free_space_cache;
1138 1139

	while(1) {
1140 1141 1142
		ret = find_first_extent_bit(unpin, 0, &start, &end,
					    EXTENT_DIRTY);
		if (ret)
1143
			break;
1144
		update_pinned_extents(root, start, end + 1 - start, 0);
1145 1146
		clear_extent_dirty(unpin, start, end, GFP_NOFS);
		set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1147 1148 1149 1150
	}
	return 0;
}

1151 1152
static int finish_current_insert(struct btrfs_trans_handle *trans,
				 struct btrfs_root *extent_root)
C
Chris Mason 已提交
1153
{
1154 1155 1156
	u64 start;
	u64 end;
	struct btrfs_fs_info *info = extent_root->fs_info;
1157
	struct extent_buffer *eb;
1158
	struct btrfs_path *path;
C
Chris Mason 已提交
1159
	struct btrfs_key ins;
1160
	struct btrfs_disk_key first;
C
Chris Mason 已提交
1161
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
1162
	int ret;
1163
	int level;
1164
	int err = 0;
C
Chris Mason 已提交
1165

1166
	btrfs_set_stack_extent_refs(&extent_item, 1);
1167
	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1168
	path = btrfs_alloc_path();
C
Chris Mason 已提交
1169

1170
	while(1) {
1171 1172 1173
		ret = find_first_extent_bit(&info->extent_ins, 0, &start,
					    &end, EXTENT_LOCKED);
		if (ret)
1174 1175
			break;

1176 1177 1178 1179 1180 1181
		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);
1182 1183 1184 1185 1186 1187 1188
		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);
		}
1189 1190
		err = btrfs_insert_extent_backref(trans, extent_root, path,
					  start, extent_root->root_key.objectid,
1191 1192
					  0, level,
					  btrfs_disk_key_objectid(&first));
1193
		BUG_ON(err);
1194
		free_extent_buffer(eb);
C
Chris Mason 已提交
1195
	}
1196
	btrfs_free_path(path);
C
Chris Mason 已提交
1197 1198 1199
	return 0;
}

1200 1201
static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
			  int pending)
C
Chris Mason 已提交
1202
{
1203
	int err = 0;
1204
	struct extent_buffer *buf;
C
Chris Mason 已提交
1205

C
Chris Mason 已提交
1206
	if (!pending) {
1207
		buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1208 1209
		if (buf) {
			if (btrfs_buffer_uptodate(buf)) {
C
Chris Mason 已提交
1210 1211
				u64 transid =
				    root->fs_info->running_transaction->transid;
C
Chris Mason 已提交
1212 1213 1214
				u64 header_transid =
					btrfs_header_generation(buf);
				if (header_transid == transid) {
1215
					clean_tree_block(NULL, root, buf);
1216
					free_extent_buffer(buf);
1217
					return 1;
C
Chris Mason 已提交
1218
				}
C
Chris Mason 已提交
1219
			}
1220
			free_extent_buffer(buf);
C
Chris Mason 已提交
1221
		}
1222
		update_pinned_extents(root, bytenr, num_bytes, 1);
C
Chris Mason 已提交
1223
	} else {
1224
		set_extent_bits(&root->fs_info->pending_del,
1225 1226
				bytenr, bytenr + num_bytes - 1,
				EXTENT_LOCKED, GFP_NOFS);
C
Chris Mason 已提交
1227
	}
C
Chris Mason 已提交
1228
	BUG_ON(err < 0);
C
Chris Mason 已提交
1229 1230 1231
	return 0;
}

1232
/*
1233
 * remove an extent from the root, returns 0 on success
1234
 */
1235
static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1236 1237 1238
			 *root, u64 bytenr, u64 num_bytes,
			 u64 root_objectid, u64 ref_generation,
			 u64 owner_objectid, u64 owner_offset, int pin,
1239
			 int mark_free)
1240
{
1241
	struct btrfs_path *path;
C
Chris Mason 已提交
1242
	struct btrfs_key key;
1243 1244
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
1245
	struct extent_buffer *leaf;
1246
	int ret;
C
Chris Mason 已提交
1247
	struct btrfs_extent_item *ei;
C
Chris Mason 已提交
1248
	u32 refs;
C
Chris Mason 已提交
1249

1250
	key.objectid = bytenr;
1251
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1252
	key.offset = num_bytes;
1253
	path = btrfs_alloc_path();
1254 1255
	if (!path)
		return -ENOMEM;
1256

1257
	path->reada = 0;
1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272
	ret = lookup_extent_backref(trans, extent_root, path,
				    bytenr, root_objectid,
				    ref_generation,
				    owner_objectid, owner_offset, 1);
	if (ret == 0) {
		ret = btrfs_del_item(trans, extent_root, path);
	} 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);
	}
	btrfs_release_path(extent_root, path);
1273 1274 1275 1276
	ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
	if (ret < 0)
		return ret;
	BUG_ON(ret);
1277 1278 1279

	leaf = path->nodes[0];
	ei = btrfs_item_ptr(leaf, path->slots[0],
C
Chris Mason 已提交
1280
			    struct btrfs_extent_item);
1281 1282 1283 1284 1285 1286
	refs = btrfs_extent_refs(leaf, ei);
	BUG_ON(refs == 0);
	refs -= 1;
	btrfs_set_extent_refs(leaf, ei, refs);
	btrfs_mark_buffer_dirty(leaf);

C
Chris Mason 已提交
1287
	if (refs == 0) {
1288 1289
		u64 super_used;
		u64 root_used;
C
Chris Mason 已提交
1290 1291

		if (pin) {
1292
			ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1293 1294 1295
			if (ret > 0)
				mark_free = 1;
			BUG_ON(ret < 0);
C
Chris Mason 已提交
1296 1297
		}

1298
		/* block accounting for super block */
1299 1300 1301
		super_used = btrfs_super_bytes_used(&info->super_copy);
		btrfs_set_super_bytes_used(&info->super_copy,
					   super_used - num_bytes);
1302 1303

		/* block accounting for root item */
1304
		root_used = btrfs_root_used(&root->root_item);
1305
		btrfs_set_root_used(&root->root_item,
1306
					   root_used - num_bytes);
1307

1308
		ret = btrfs_del_item(trans, extent_root, path);
1309 1310 1311
		if (ret) {
			return ret;
		}
1312
		ret = update_block_group(trans, root, bytenr, num_bytes, 0,
C
Chris Mason 已提交
1313
					 mark_free, 0);
C
Chris Mason 已提交
1314
		BUG_ON(ret);
1315
	}
1316
	btrfs_free_path(path);
1317
	finish_current_insert(trans, extent_root);
1318 1319 1320 1321 1322 1323 1324
	return ret;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
1325 1326
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root)
1327 1328
{
	int ret;
C
Chris Mason 已提交
1329
	int err = 0;
1330 1331 1332 1333
	u64 start;
	u64 end;
	struct extent_map_tree *pending_del;
	struct extent_map_tree *pinned_extents;
C
Chris Mason 已提交
1334

1335 1336
	pending_del = &extent_root->fs_info->pending_del;
	pinned_extents = &extent_root->fs_info->pinned_extents;
1337 1338

	while(1) {
1339 1340 1341
		ret = find_first_extent_bit(pending_del, 0, &start, &end,
					    EXTENT_LOCKED);
		if (ret)
1342
			break;
1343
		update_pinned_extents(extent_root, start, end + 1 - start, 1);
1344 1345 1346
		clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
				  GFP_NOFS);
		ret = __free_extent(trans, extent_root,
1347 1348 1349
				     start, end + 1 - start,
				     extent_root->root_key.objectid,
				     0, 0, 0, 0, 0);
1350 1351
		if (ret)
			err = ret;
1352
	}
C
Chris Mason 已提交
1353
	return err;
1354 1355 1356 1357 1358
}

/*
 * remove an extent from the root, returns 0 on success
 */
1359
int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1360 1361 1362
		      *root, u64 bytenr, u64 num_bytes,
		      u64 root_objectid, u64 ref_generation,
		      u64 owner_objectid, u64 owner_offset, int pin)
1363
{
1364
	struct btrfs_root *extent_root = root->fs_info->extent_root;
1365 1366
	int pending_ret;
	int ret;
1367

1368
	WARN_ON(num_bytes < root->sectorsize);
1369 1370 1371
	if (!root->ref_cows)
		ref_generation = 0;

1372
	if (root == extent_root) {
1373
		pin_down_bytes(root, bytenr, num_bytes, 1);
1374 1375
		return 0;
	}
1376 1377 1378
	ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
			    ref_generation, owner_objectid, owner_offset,
			    pin, pin == 0);
C
Chris Mason 已提交
1379
	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1380 1381 1382
	return ret ? ret : pending_ret;
}

1383 1384 1385 1386 1387 1388 1389
static u64 stripe_align(struct btrfs_root *root, u64 val)
{
	u64 mask = ((u64)root->stripesize - 1);
	u64 ret = (val + mask) & ~mask;
	return ret;
}

1390 1391 1392 1393
/*
 * 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
1394
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
1395 1396 1397
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
1398 1399 1400 1401 1402 1403 1404
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)
1405
{
1406
	struct btrfs_path *path;
C
Chris Mason 已提交
1407
	struct btrfs_key key;
1408
	u64 hole_size = 0;
1409 1410
	u64 aligned;
	int ret;
1411
	int slot = 0;
1412
	u64 last_byte = 0;
C
Chris Mason 已提交
1413
	u64 orig_search_start = search_start;
1414
	int start_found;
1415
	struct extent_buffer *l;
1416
	struct btrfs_root * root = orig_root->fs_info->extent_root;
1417
	struct btrfs_fs_info *info = root->fs_info;
1418
	u64 total_needed = num_bytes;
C
Chris Mason 已提交
1419
	int level;
C
Chris Mason 已提交
1420
	struct btrfs_block_group_cache *block_group;
C
Chris Mason 已提交
1421
	int full_scan = 0;
1422
	int wrapped = 0;
1423
	u64 cached_start;
1424

1425
	WARN_ON(num_bytes < root->sectorsize);
1426 1427
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);

1428 1429
	level = btrfs_header_level(root->node);

1430
	if (num_bytes >= 32 * 1024 * 1024 && hint_byte) {
1431 1432 1433
		data = BTRFS_BLOCK_GROUP_MIXED;
	}

1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446
	/* for SSD, cluster allocations together as much as possible */
	if (btrfs_test_opt(root, SSD)) {
		if (!data) {
			if (root->fs_info->last_alloc)
				hint_byte = root->fs_info->last_alloc;
			else {
				hint_byte = hint_byte &
					~((u64)BTRFS_BLOCK_GROUP_SIZE - 1);
				empty_size += 16 * 1024 * 1024;
			}
		}
	}

C
Chris Mason 已提交
1447 1448
	search_end = min(search_end,
			 btrfs_super_total_bytes(&info->super_copy));
1449 1450
	if (hint_byte) {
		block_group = btrfs_lookup_block_group(info, hint_byte);
1451 1452
		if (!block_group)
			hint_byte = search_start;
C
Chris Mason 已提交
1453
		block_group = btrfs_find_block_group(root, block_group,
1454
						     hint_byte, data, 1);
C
Chris Mason 已提交
1455 1456
	} else {
		block_group = btrfs_find_block_group(root,
1457 1458
						     trans->block_group,
						     search_start, data, 1);
C
Chris Mason 已提交
1459 1460
	}

1461
	total_needed += empty_size;
1462
	path = btrfs_alloc_path();
C
Chris Mason 已提交
1463
check_failed:
1464 1465 1466 1467 1468 1469
	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);
	}
1470
	search_start = find_search_start(root, &block_group, search_start,
1471
					 total_needed, data);
1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484

	if (!data && btrfs_test_opt(root, SSD) && info->last_alloc &&
	    search_start != info->last_alloc) {
		info->last_alloc = 0;
		if (!empty_size) {
			empty_size += 16 * 1024 * 1024;
			total_needed += empty_size;
		}
		search_start = find_search_start(root, &block_group,
						 search_start, total_needed,
						 data);
	}

1485
	search_start = stripe_align(root, search_start);
1486
	cached_start = search_start;
1487
	btrfs_init_path(path);
1488 1489 1490
	ins->objectid = search_start;
	ins->offset = 0;
	start_found = 0;
1491
	path->reada = 2;
1492

1493
	ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
C
Chris Mason 已提交
1494 1495
	if (ret < 0)
		goto error;
1496 1497 1498
	ret = find_previous_extent(root, path);
	if (ret < 0)
		goto error;
1499 1500
	l = path->nodes[0];
	btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1501
	while (1) {
1502
		l = path->nodes[0];
1503
		slot = path->slots[0];
1504
		if (slot >= btrfs_header_nritems(l)) {
1505
			ret = btrfs_next_leaf(root, path);
1506 1507
			if (ret == 0)
				continue;
C
Chris Mason 已提交
1508 1509
			if (ret < 0)
				goto error;
1510 1511 1512

			search_start = max(search_start,
					   block_group->key.objectid);
1513
			if (!start_found) {
1514 1515 1516 1517 1518 1519 1520
				aligned = stripe_align(root, search_start);
				ins->objectid = aligned;
				if (aligned >= search_end) {
					ret = -ENOSPC;
					goto error;
				}
				ins->offset = search_end - aligned;
1521 1522 1523
				start_found = 1;
				goto check_pending;
			}
1524 1525 1526 1527 1528 1529 1530
			ins->objectid = stripe_align(root,
						     last_byte > search_start ?
						     last_byte : search_start);
			if (search_end <= ins->objectid) {
				ret = -ENOSPC;
				goto error;
			}
C
Chris Mason 已提交
1531
			ins->offset = search_end - ins->objectid;
1532
			BUG_ON(ins->objectid >= search_end);
1533 1534
			goto check_pending;
		}
1535
		btrfs_item_key_to_cpu(l, &key, slot);
1536

1537
		if (key.objectid >= search_start && key.objectid > last_byte &&
1538
		    start_found) {
1539 1540
			if (last_byte < search_start)
				last_byte = search_start;
1541 1542 1543 1544
			aligned = stripe_align(root, last_byte);
			hole_size = key.objectid - aligned;
			if (key.objectid > aligned && hole_size >= num_bytes) {
				ins->objectid = aligned;
1545 1546
				ins->offset = hole_size;
				goto check_pending;
1547
			}
1548
		}
1549
		if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
1550 1551
			if (!start_found && btrfs_key_type(&key) ==
			    BTRFS_BLOCK_GROUP_ITEM_KEY) {
1552
				last_byte = key.objectid;
1553 1554
				start_found = 1;
			}
1555
			goto next;
1556 1557
		}

1558

1559
		start_found = 1;
1560
		last_byte = key.objectid + key.offset;
1561

1562 1563
		if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
		    last_byte >= block_group->key.objectid +
C
Chris Mason 已提交
1564 1565 1566
		    block_group->key.offset) {
			btrfs_release_path(root, path);
			search_start = block_group->key.objectid +
1567
				block_group->key.offset;
C
Chris Mason 已提交
1568 1569
			goto new_group;
		}
C
Chris Mason 已提交
1570
next:
1571
		path->slots[0]++;
1572
		cond_resched();
1573 1574 1575 1576 1577
	}
check_pending:
	/* we have to make sure we didn't find an extent that has already
	 * been allocated by the map tree or the original allocation
	 */
1578
	btrfs_release_path(root, path);
1579
	BUG_ON(ins->objectid < search_start);
1580

1581
	if (ins->objectid + num_bytes >= search_end)
1582
		goto enospc;
1583
	if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
Y
Yan 已提交
1584
	    ins->objectid + num_bytes > block_group->
1585 1586 1587 1588 1589
	    key.objectid + block_group->key.offset) {
		search_start = block_group->key.objectid +
			block_group->key.offset;
		goto new_group;
	}
1590
	if (test_range_bit(&info->extent_ins, ins->objectid,
1591 1592
			   ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
		search_start = ins->objectid + num_bytes;
1593 1594 1595
		goto new_group;
	}
	if (test_range_bit(&info->pinned_extents, ins->objectid,
1596 1597
			   ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
		search_start = ins->objectid + num_bytes;
1598
		goto new_group;
1599
	}
1600
	if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1601 1602 1603 1604
	    ins->objectid < exclude_start + exclude_nr)) {
		search_start = exclude_start + exclude_nr;
		goto new_group;
	}
1605
	if (!data) {
1606
		block_group = btrfs_lookup_block_group(info, ins->objectid);
1607 1608
		if (block_group)
			trans->block_group = block_group;
1609
	}
1610
	ins->offset = num_bytes;
1611
	btrfs_free_path(path);
1612
	return 0;
C
Chris Mason 已提交
1613 1614

new_group:
1615
	if (search_start + num_bytes >= search_end) {
1616
enospc:
C
Chris Mason 已提交
1617
		search_start = orig_search_start;
1618 1619 1620 1621
		if (full_scan) {
			ret = -ENOSPC;
			goto error;
		}
1622 1623 1624
		if (wrapped) {
			if (!full_scan)
				total_needed -= empty_size;
1625
			full_scan = 1;
1626
			data = BTRFS_BLOCK_GROUP_MIXED;
1627
		} else
1628
			wrapped = 1;
C
Chris Mason 已提交
1629
	}
1630
	block_group = btrfs_lookup_block_group(info, search_start);
1631
	cond_resched();
1632 1633
	block_group = btrfs_find_block_group(root, block_group,
					     search_start, data, 0);
C
Chris Mason 已提交
1634 1635
	goto check_failed;

C
Chris Mason 已提交
1636
error:
1637 1638
	btrfs_release_path(root, path);
	btrfs_free_path(path);
1639 1640
	if (btrfs_test_opt(root, SSD) && !ret && !data)
		info->last_alloc = ins->objectid + ins->offset;
C
Chris Mason 已提交
1641
	return ret;
1642 1643 1644 1645 1646 1647 1648 1649
}
/*
 * 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.
 */
1650
int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1651 1652 1653 1654
		       struct btrfs_root *root,
		       u64 num_bytes, u64 root_objectid, u64 ref_generation,
		       u64 owner, u64 owner_offset,
		       u64 empty_size, u64 hint_byte,
C
Chris Mason 已提交
1655
		       u64 search_end, struct btrfs_key *ins, int data)
1656 1657 1658
{
	int ret;
	int pending_ret;
C
Chris Mason 已提交
1659 1660
	u64 super_used;
	u64 root_used;
1661
	u64 search_start = 0;
1662
	u64 new_hint;
1663 1664
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
C
Chris Mason 已提交
1665
	struct btrfs_extent_item extent_item;
1666
	struct btrfs_path *path;
C
Chris Mason 已提交
1667

1668
	btrfs_set_stack_extent_refs(&extent_item, 1);
1669 1670

	new_hint = max(hint_byte, root->fs_info->alloc_start);
1671 1672
	if (new_hint < btrfs_super_total_bytes(&info->super_copy))
		hint_byte = new_hint;
1673

1674 1675 1676
	WARN_ON(num_bytes < root->sectorsize);
	ret = find_free_extent(trans, root, num_bytes, empty_size,
			       search_start, search_end, hint_byte, ins,
1677 1678
			       trans->alloc_exclude_start,
			       trans->alloc_exclude_nr, data);
C
Chris Mason 已提交
1679
	BUG_ON(ret);
1680 1681
	if (ret)
		return ret;
1682

1683
	/* block accounting for super block */
1684 1685
	super_used = btrfs_super_bytes_used(&info->super_copy);
	btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1686

1687
	/* block accounting for root item */
1688 1689
	root_used = btrfs_root_used(&root->root_item);
	btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1690

1691 1692 1693 1694
	clear_extent_dirty(&root->fs_info->free_space_cache,
			   ins->objectid, ins->objectid + ins->offset - 1,
			   GFP_NOFS);

1695
	if (root == extent_root) {
1696 1697 1698
		set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
				ins->objectid + ins->offset - 1,
				EXTENT_LOCKED, GFP_NOFS);
1699
		WARN_ON(data == 1);
1700 1701 1702 1703 1704 1705
		goto update_block;
	}

	WARN_ON(trans->alloc_exclude_nr);
	trans->alloc_exclude_start = ins->objectid;
	trans->alloc_exclude_nr = ins->offset;
1706 1707
	ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
				sizeof(extent_item));
C
Chris Mason 已提交
1708

1709 1710
	trans->alloc_exclude_start = 0;
	trans->alloc_exclude_nr = 0;
1711 1712 1713 1714 1715 1716 1717
	BUG_ON(ret);

	path = btrfs_alloc_path();
	BUG_ON(!path);
	ret = btrfs_insert_extent_backref(trans, extent_root, path,
					  ins->objectid, root_objectid,
					  ref_generation, owner, owner_offset);
1718

C
Chris Mason 已提交
1719
	BUG_ON(ret);
1720
	btrfs_free_path(path);
1721
	finish_current_insert(trans, extent_root);
C
Chris Mason 已提交
1722
	pending_ret = del_pending_extents(trans, extent_root);
1723

1724
	if (ret) {
C
Chris Mason 已提交
1725
		return ret;
1726 1727
	}
	if (pending_ret) {
C
Chris Mason 已提交
1728
		return pending_ret;
1729
	}
1730 1731

update_block:
C
Chris Mason 已提交
1732 1733
	ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
				 data);
C
Chris Mason 已提交
1734
	BUG_ON(ret);
C
Chris Mason 已提交
1735
	return 0;
1736 1737 1738 1739 1740 1741
}

/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
1742
struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1743
					     struct btrfs_root *root,
1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771
					     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,
1772
					     u64 empty_size)
1773
{
C
Chris Mason 已提交
1774
	struct btrfs_key ins;
1775
	int ret;
1776
	struct extent_buffer *buf;
1777

1778 1779
	ret = btrfs_alloc_extent(trans, root, blocksize,
				 root_objectid, ref_generation,
1780
				 level, first_objectid, empty_size, hint,
1781
				 (u64)-1, &ins, 0);
1782
	if (ret) {
1783 1784
		BUG_ON(ret > 0);
		return ERR_PTR(ret);
1785
	}
1786
	buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1787
	if (!buf) {
1788 1789 1790
		btrfs_free_extent(trans, root, ins.objectid, blocksize,
				  root->root_key.objectid, ref_generation,
				  0, 0, 0);
1791 1792
		return ERR_PTR(-ENOMEM);
	}
1793 1794 1795
	btrfs_set_header_generation(buf, trans->transid);
	clean_tree_block(trans, root, buf);
	wait_on_tree_block_writeback(root, buf);
1796
	btrfs_set_buffer_uptodate(buf);
1797 1798 1799 1800 1801 1802

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

1803 1804
	set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
			 buf->start + buf->len - 1, GFP_NOFS);
1805 1806 1807 1808
	set_extent_bits(&BTRFS_I(root->fs_info->btree_inode)->extent_tree,
			buf->start, buf->start + buf->len - 1,
			EXTENT_CSUM, GFP_NOFS);
	buf->flags |= EXTENT_CSUM;
1809 1810
	if (!btrfs_test_opt(root, SSD))
		btrfs_set_buffer_defrag(buf);
1811
	trans->blocks_used++;
1812 1813
	return buf;
}
1814

1815 1816 1817
static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
				  struct btrfs_root *root,
				  struct extent_buffer *leaf)
1818
{
1819 1820
	u64 leaf_owner;
	u64 leaf_generation;
1821
	struct btrfs_key key;
1822 1823 1824 1825 1826
	struct btrfs_file_extent_item *fi;
	int i;
	int nritems;
	int ret;

1827 1828
	BUG_ON(!btrfs_is_leaf(leaf));
	nritems = btrfs_header_nritems(leaf);
1829 1830 1831
	leaf_owner = btrfs_header_owner(leaf);
	leaf_generation = btrfs_header_generation(leaf);

1832
	for (i = 0; i < nritems; i++) {
1833
		u64 disk_bytenr;
1834 1835 1836

		btrfs_item_key_to_cpu(leaf, &key, i);
		if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1837 1838
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1839 1840
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
1841
			continue;
1842 1843 1844 1845
		/*
		 * FIXME make sure to insert a trans record that
		 * repeats the snapshot del on crash
		 */
1846 1847
		disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
		if (disk_bytenr == 0)
C
Chris Mason 已提交
1848
			continue;
1849
		ret = btrfs_free_extent(trans, root, disk_bytenr,
1850 1851 1852
				btrfs_file_extent_disk_num_bytes(leaf, fi),
				leaf_owner, leaf_generation,
				key.objectid, key.offset, 0);
1853 1854 1855 1856 1857
		BUG_ON(ret);
	}
	return 0;
}

1858 1859
static void noinline reada_walk_down(struct btrfs_root *root,
				     struct extent_buffer *node)
1860 1861 1862
{
	int i;
	u32 nritems;
1863
	u64 bytenr;
1864 1865
	int ret;
	u32 refs;
1866 1867
	int level;
	u32 blocksize;
1868

1869
	nritems = btrfs_header_nritems(node);
1870
	level = btrfs_header_level(node);
1871
	for (i = 0; i < nritems; i++) {
1872 1873 1874
		bytenr = btrfs_node_blockptr(node, i);
		blocksize = btrfs_level_size(root, level - 1);
		ret = lookup_extent_ref(NULL, root, bytenr, blocksize, &refs);
1875 1876 1877
		BUG_ON(ret);
		if (refs != 1)
			continue;
1878
		mutex_unlock(&root->fs_info->fs_mutex);
1879
		ret = readahead_tree_block(root, bytenr, blocksize);
1880 1881
		cond_resched();
		mutex_lock(&root->fs_info->fs_mutex);
1882 1883 1884 1885 1886
		if (ret)
			break;
	}
}

C
Chris Mason 已提交
1887 1888 1889 1890
/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
1891 1892 1893
static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct btrfs_path *path, int *level)
C
Chris Mason 已提交
1894
{
1895 1896 1897
	u64 root_owner;
	u64 root_gen;
	u64 bytenr;
1898 1899
	struct extent_buffer *next;
	struct extent_buffer *cur;
1900
	struct extent_buffer *parent;
1901
	u32 blocksize;
C
Chris Mason 已提交
1902 1903 1904
	int ret;
	u32 refs;

1905 1906
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
1907
	ret = lookup_extent_ref(trans, root,
1908 1909
				path->nodes[*level]->start,
				path->nodes[*level]->len, &refs);
C
Chris Mason 已提交
1910 1911 1912
	BUG_ON(ret);
	if (refs > 1)
		goto out;
1913

C
Chris Mason 已提交
1914 1915 1916
	/*
	 * walk down to the last node level and free all the leaves
	 */
1917
	while(*level >= 0) {
1918 1919
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
1920
		cur = path->nodes[*level];
1921 1922

		if (*level > 0 && path->slots[*level] == 0)
1923
			reada_walk_down(root, cur);
1924

1925
		if (btrfs_header_level(cur) != *level)
C
Chris Mason 已提交
1926
			WARN_ON(1);
1927

1928
		if (path->slots[*level] >=
1929
		    btrfs_header_nritems(cur))
C
Chris Mason 已提交
1930
			break;
1931 1932 1933 1934 1935
		if (*level == 0) {
			ret = drop_leaf_ref(trans, root, cur);
			BUG_ON(ret);
			break;
		}
1936 1937 1938
		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
		blocksize = btrfs_level_size(root, *level - 1);
		ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1939 1940
		BUG_ON(ret);
		if (refs != 1) {
1941 1942 1943
			parent = path->nodes[*level];
			root_owner = btrfs_header_owner(parent);
			root_gen = btrfs_header_generation(parent);
C
Chris Mason 已提交
1944
			path->slots[*level]++;
1945
			ret = btrfs_free_extent(trans, root, bytenr,
1946 1947
						blocksize, root_owner,
						root_gen, 0, 0, 1);
C
Chris Mason 已提交
1948 1949 1950
			BUG_ON(ret);
			continue;
		}
1951
		next = btrfs_find_tree_block(root, bytenr, blocksize);
1952 1953
		if (!next || !btrfs_buffer_uptodate(next)) {
			free_extent_buffer(next);
1954
			mutex_unlock(&root->fs_info->fs_mutex);
1955
			next = read_tree_block(root, bytenr, blocksize);
1956 1957 1958
			mutex_lock(&root->fs_info->fs_mutex);

			/* we dropped the lock, check one more time */
1959 1960
			ret = lookup_extent_ref(trans, root, bytenr,
						blocksize, &refs);
1961 1962
			BUG_ON(ret);
			if (refs != 1) {
1963 1964 1965 1966
				parent = path->nodes[*level];
				root_owner = btrfs_header_owner(parent);
				root_gen = btrfs_header_generation(parent);

1967
				path->slots[*level]++;
1968
				free_extent_buffer(next);
1969 1970 1971 1972
				ret = btrfs_free_extent(trans, root, bytenr,
							blocksize,
							root_owner,
							root_gen, 0, 0, 1);
1973 1974 1975 1976
				BUG_ON(ret);
				continue;
			}
		}
1977
		WARN_ON(*level <= 0);
C
Chris Mason 已提交
1978
		if (path->nodes[*level-1])
1979
			free_extent_buffer(path->nodes[*level-1]);
C
Chris Mason 已提交
1980
		path->nodes[*level-1] = next;
1981
		*level = btrfs_header_level(next);
C
Chris Mason 已提交
1982 1983 1984
		path->slots[*level] = 0;
	}
out:
1985 1986
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
1987 1988 1989 1990 1991 1992 1993 1994 1995 1996

	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);
1997
	ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
1998 1999
				path->nodes[*level]->len,
				root_owner, root_gen, 0, 0, 1);
2000
	free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
2001 2002 2003 2004 2005 2006
	path->nodes[*level] = NULL;
	*level += 1;
	BUG_ON(ret);
	return 0;
}

C
Chris Mason 已提交
2007 2008 2009 2010 2011
/*
 * 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
 */
2012 2013 2014
static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
				 struct btrfs_root *root,
				 struct btrfs_path *path, int *level)
C
Chris Mason 已提交
2015
{
2016 2017 2018
	u64 root_owner;
	u64 root_gen;
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
2019 2020 2021
	int i;
	int slot;
	int ret;
2022

C
Chris Mason 已提交
2023
	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
C
Chris Mason 已提交
2024
		slot = path->slots[i];
2025 2026 2027 2028
		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 已提交
2029 2030
			path->slots[i]++;
			*level = i;
2031
			WARN_ON(*level == 0);
2032
			btrfs_node_key(node, &disk_key, path->slots[i]);
2033
			memcpy(&root_item->drop_progress,
2034
			       &disk_key, sizeof(disk_key));
2035
			root_item->drop_level = i;
C
Chris Mason 已提交
2036 2037
			return 0;
		} else {
2038 2039 2040 2041 2042 2043 2044 2045 2046 2047
			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);
			}
2048
			ret = btrfs_free_extent(trans, root,
2049
						path->nodes[*level]->start,
2050 2051
						path->nodes[*level]->len,
						root_owner, root_gen, 0, 0, 1);
2052
			BUG_ON(ret);
2053
			free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
2054
			path->nodes[*level] = NULL;
C
Chris Mason 已提交
2055 2056 2057 2058 2059 2060
			*level = i + 1;
		}
	}
	return 1;
}

C
Chris Mason 已提交
2061 2062 2063 2064 2065
/*
 * 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.
 */
2066
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2067
			*root)
C
Chris Mason 已提交
2068
{
2069
	int ret = 0;
C
Chris Mason 已提交
2070
	int wret;
C
Chris Mason 已提交
2071
	int level;
2072
	struct btrfs_path *path;
C
Chris Mason 已提交
2073 2074
	int i;
	int orig_level;
2075
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
2076

2077 2078
	path = btrfs_alloc_path();
	BUG_ON(!path);
C
Chris Mason 已提交
2079

2080
	level = btrfs_header_level(root->node);
C
Chris Mason 已提交
2081
	orig_level = level;
2082 2083
	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
		path->nodes[level] = root->node;
2084
		extent_buffer_get(root->node);
2085 2086 2087
		path->slots[level] = 0;
	} else {
		struct btrfs_key key;
2088 2089
		struct btrfs_disk_key found_key;
		struct extent_buffer *node;
2090

2091
		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2092 2093
		level = root_item->drop_level;
		path->lowest_level = level;
2094
		wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2095
		if (wret < 0) {
2096 2097 2098
			ret = wret;
			goto out;
		}
2099 2100 2101 2102
		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)));
2103
	}
C
Chris Mason 已提交
2104
	while(1) {
2105
		wret = walk_down_tree(trans, root, path, &level);
C
Chris Mason 已提交
2106
		if (wret > 0)
C
Chris Mason 已提交
2107
			break;
C
Chris Mason 已提交
2108 2109 2110
		if (wret < 0)
			ret = wret;

2111
		wret = walk_up_tree(trans, root, path, &level);
C
Chris Mason 已提交
2112
		if (wret > 0)
C
Chris Mason 已提交
2113
			break;
C
Chris Mason 已提交
2114 2115
		if (wret < 0)
			ret = wret;
2116 2117
		ret = -EAGAIN;
		break;
C
Chris Mason 已提交
2118
	}
C
Chris Mason 已提交
2119
	for (i = 0; i <= orig_level; i++) {
2120
		if (path->nodes[i]) {
2121
			free_extent_buffer(path->nodes[i]);
2122
			path->nodes[i] = NULL;
C
Chris Mason 已提交
2123
		}
C
Chris Mason 已提交
2124
	}
2125
out:
2126
	btrfs_free_path(path);
C
Chris Mason 已提交
2127
	return ret;
C
Chris Mason 已提交
2128
}
C
Chris Mason 已提交
2129

2130
int btrfs_free_block_groups(struct btrfs_fs_info *info)
C
Chris Mason 已提交
2131
{
2132 2133
	u64 start;
	u64 end;
2134
	u64 ptr;
C
Chris Mason 已提交
2135 2136
	int ret;
	while(1) {
2137 2138 2139
		ret = find_first_extent_bit(&info->block_group_cache, 0,
					    &start, &end, (unsigned int)-1);
		if (ret)
C
Chris Mason 已提交
2140
			break;
2141 2142 2143
		ret = get_state_private(&info->block_group_cache, start, &ptr);
		if (!ret)
			kfree((void *)(unsigned long)ptr);
2144 2145
		clear_extent_bits(&info->block_group_cache, start,
				  end, (unsigned int)-1, GFP_NOFS);
C
Chris Mason 已提交
2146
	}
2147
	while(1) {
2148 2149 2150
		ret = find_first_extent_bit(&info->free_space_cache, 0,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
2151
			break;
2152 2153
		clear_extent_dirty(&info->free_space_cache, start,
				   end, GFP_NOFS);
2154
	}
C
Chris Mason 已提交
2155 2156 2157
	return 0;
}

2158 2159
static int noinline relocate_inode_pages(struct inode *inode, u64 start,
					 u64 len)
2160 2161 2162 2163 2164 2165 2166 2167 2168 2169
{
	u64 page_start;
	u64 page_end;
	u64 delalloc_start;
	u64 existing_delalloc;
	unsigned long last_index;
	unsigned long i;
	struct page *page;
	struct btrfs_root *root = BTRFS_I(inode)->root;
	struct extent_map_tree *em_tree = &BTRFS_I(inode)->extent_tree;
2170 2171 2172
	struct file_ra_state *ra;

	ra = kzalloc(sizeof(*ra), GFP_NOFS);
2173 2174

	mutex_lock(&inode->i_mutex);
2175
	i = start >> PAGE_CACHE_SHIFT;
2176 2177
	last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;

2178 2179 2180
	file_ra_state_init(ra, inode->i_mapping);
	btrfs_force_ra(inode->i_mapping, ra, NULL, i, last_index);
	kfree(ra);
2181

2182
	for (; i <= last_index; i++) {
2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224
		page = grab_cache_page(inode->i_mapping, i);
		if (!page)
			goto out_unlock;
		if (!PageUptodate(page)) {
			btrfs_readpage(NULL, page);
			lock_page(page);
			if (!PageUptodate(page)) {
				unlock_page(page);
				page_cache_release(page);
				goto out_unlock;
			}
		}
		page_start = (u64)page->index << PAGE_CACHE_SHIFT;
		page_end = page_start + PAGE_CACHE_SIZE - 1;

		lock_extent(em_tree, page_start, page_end, GFP_NOFS);

		delalloc_start = page_start;
		existing_delalloc =
			count_range_bits(&BTRFS_I(inode)->extent_tree,
					 &delalloc_start, page_end,
					 PAGE_CACHE_SIZE, EXTENT_DELALLOC);

		set_extent_delalloc(em_tree, page_start,
				    page_end, GFP_NOFS);

		spin_lock(&root->fs_info->delalloc_lock);
		root->fs_info->delalloc_bytes += PAGE_CACHE_SIZE -
						 existing_delalloc;
		spin_unlock(&root->fs_info->delalloc_lock);

		unlock_extent(em_tree, page_start, page_end, GFP_NOFS);
		set_page_dirty(page);
		unlock_page(page);
		page_cache_release(page);
	}

out_unlock:
	mutex_unlock(&inode->i_mutex);
	return 0;
}

2225 2226 2227
/*
 * note, this releases the path
 */
2228
static int noinline relocate_one_reference(struct btrfs_root *extent_root,
2229
				  struct btrfs_path *path,
2230
				  struct btrfs_key *extent_key)
2231 2232 2233
{
	struct inode *inode;
	struct btrfs_root *found_root;
2234 2235 2236 2237 2238 2239
	struct btrfs_key *root_location;
	struct btrfs_extent_ref *ref;
	u64 ref_root;
	u64 ref_gen;
	u64 ref_objectid;
	u64 ref_offset;
2240 2241
	int ret;

2242 2243 2244 2245 2246 2247 2248 2249 2250 2251
	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);

	root_location = kmalloc(sizeof(*root_location), GFP_NOFS);
	root_location->objectid = ref_root;
2252
	if (ref_gen == 0)
2253
		root_location->offset = 0;
2254
	else
2255 2256
		root_location->offset = (u64)-1;
	root_location->type = BTRFS_ROOT_ITEM_KEY;
2257 2258

	found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
2259
						root_location);
2260
	BUG_ON(!found_root);
2261
	kfree(root_location);
2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308

	if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
		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);
		/* FIXME, data=ordered will help get rid of this */
		filemap_fdatawrite(inode->i_mapping);
		iput(inode);
		mutex_lock(&extent_root->fs_info->fs_mutex);
	} else {
		struct btrfs_trans_handle *trans;
		struct btrfs_key found_key;
		struct extent_buffer *eb;
		int level;
		int i;

		trans = btrfs_start_transaction(found_root, 1);
		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);

		path->lowest_level = level;
2309
		path->reada = 2;
2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326
		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;
}

2327 2328 2329
static int noinline relocate_one_extent(struct btrfs_root *extent_root,
					struct btrfs_path *path,
					struct btrfs_key *extent_key)
2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363
{
	struct btrfs_key key;
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
	u32 nritems;
	u32 item_size;
	int ret = 0;

	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);
		if (path->slots[0] == nritems)
			goto out;

		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.objectid != extent_key->objectid)
			break;

		if (found_key.type != BTRFS_EXTENT_REF_KEY)
			break;

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

2364
		ret = relocate_one_reference(extent_root, path, extent_key);
2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383
		if (ret)
			goto out;
	}
	ret = 0;
out:
	btrfs_release_path(extent_root, path);
	return ret;
}

int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 new_size)
{
	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;
	struct btrfs_fs_info *info = root->fs_info;
	struct extent_map_tree *block_group_cache;
	struct btrfs_key key;
2384
	struct btrfs_key found_key;
2385 2386 2387
	struct extent_buffer *leaf;
	u32 nritems;
	int ret;
2388
	int progress = 0;
2389 2390

	btrfs_set_super_total_bytes(&info->super_copy, new_size);
C
Chris Mason 已提交
2391 2392
	clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
			   GFP_NOFS);
2393 2394 2395
	block_group_cache = &info->block_group_cache;
	path = btrfs_alloc_path();
	root = root->fs_info->extent_root;
2396
	path->reada = 2;
2397 2398 2399 2400 2401 2402

again:
	total_found = 0;
	key.objectid = new_size;
	key.offset = 0;
	key.type = 0;
2403
	cur_byte = key.objectid;
2404

2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		goto out;

	ret = find_previous_extent(root, path);
	if (ret < 0)
		goto out;
	if (ret == 0) {
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.objectid + found_key.offset > new_size) {
			cur_byte = found_key.objectid;
			key.objectid = cur_byte;
		}
	}
	btrfs_release_path(root, path);

	while(1) {
2423 2424 2425
		ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
		if (ret < 0)
			goto out;
2426

2427
		leaf = path->nodes[0];
2428 2429 2430 2431 2432 2433 2434 2435 2436
		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;
2437
			}
2438 2439
			leaf = path->nodes[0];
			nritems = btrfs_header_nritems(leaf);
2440
		}
2441 2442

		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455

		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;

2456 2457
		if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
		    found_key.objectid + found_key.offset <= cur_byte) {
2458 2459 2460
			path->slots[0]++;
			goto next;
		}
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
		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;
	}

	trans = btrfs_start_transaction(root, 1);
	key.objectid = new_size;
	key.offset = 0;
	key.type = 0;
	while(1) {
2489 2490
		u64 ptr;

2491 2492 2493
		ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
		if (ret < 0)
			goto out;
2494

2495 2496
		leaf = path->nodes[0];
		nritems = btrfs_header_nritems(leaf);
2497 2498 2499 2500 2501 2502 2503 2504
bg_next:
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(root, path);
			if (ret < 0)
				break;
			if (ret == 1) {
				ret = 0;
				break;
2505
			}
2506
			leaf = path->nodes[0];
2507 2508 2509 2510 2511 2512 2513 2514
			btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);

			/*
			 * btrfs_next_leaf doesn't cow buffers, we have to
			 * do the search again
			 */
			memcpy(&key, &found_key, sizeof(key));
			btrfs_release_path(root, path);
2515
			goto resched_check;
2516 2517 2518 2519 2520 2521 2522 2523
		}

		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (btrfs_key_type(&found_key) != BTRFS_BLOCK_GROUP_ITEM_KEY) {
			printk("shrinker found key %Lu %u %Lu\n",
				found_key.objectid, found_key.type,
				found_key.offset);
			path->slots[0]++;
2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537
			goto bg_next;
		}
		ret = get_state_private(&info->block_group_cache,
					found_key.objectid, &ptr);
		if (!ret)
			kfree((void *)(unsigned long)ptr);

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

		key.objectid = found_key.objectid + 1;
		btrfs_del_item(trans, root, path);
		btrfs_release_path(root, path);
2538 2539 2540 2541 2542 2543
resched_check:
		if (need_resched()) {
			mutex_unlock(&root->fs_info->fs_mutex);
			cond_resched();
			mutex_lock(&root->fs_info->fs_mutex);
		}
2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559
	}
	clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
			   GFP_NOFS);
	btrfs_commit_transaction(trans, root);
out:
	btrfs_free_path(path);
	return ret;
}

int btrfs_grow_extent_tree(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root, u64 new_size)
{
	struct btrfs_path *path;
	u64 nr = 0;
	u64 cur_byte;
	u64 old_size;
2560
	unsigned long rem;
2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597
	struct btrfs_block_group_cache *cache;
	struct btrfs_block_group_item *item;
	struct btrfs_fs_info *info = root->fs_info;
	struct extent_map_tree *block_group_cache;
	struct btrfs_key key;
	struct extent_buffer *leaf;
	int ret;
	int bit;

	old_size = btrfs_super_total_bytes(&info->super_copy);
	block_group_cache = &info->block_group_cache;

	root = info->extent_root;

	cache = btrfs_lookup_block_group(root->fs_info, old_size - 1);

	cur_byte = cache->key.objectid + cache->key.offset;
	if (cur_byte >= new_size)
		goto set_size;

	key.offset = BTRFS_BLOCK_GROUP_SIZE;
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);

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

	while(cur_byte < new_size) {
		key.objectid = cur_byte;
		ret = btrfs_insert_empty_item(trans, root, path, &key,
				        sizeof(struct btrfs_block_group_item));
		BUG_ON(ret);
		leaf = path->nodes[0];
		item = btrfs_item_ptr(leaf, path->slots[0],
				      struct btrfs_block_group_item);

		btrfs_set_disk_block_group_used(leaf, item, 0);
2598 2599
		div_long_long_rem(nr, 3, &rem);
		if (rem) {
2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639
			btrfs_set_disk_block_group_flags(leaf, item,
						 BTRFS_BLOCK_GROUP_DATA);
		} else {
			btrfs_set_disk_block_group_flags(leaf, item, 0);
		}
		nr++;

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

		read_extent_buffer(leaf, &cache->item, (unsigned long)item,
				   sizeof(cache->item));

		memcpy(&cache->key, &key, sizeof(key));
		cache->cached = 0;
		cache->pinned = 0;
		cur_byte = key.objectid + key.offset;
		btrfs_release_path(root, path);

		if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
			bit = BLOCK_GROUP_DATA;
			cache->data = BTRFS_BLOCK_GROUP_DATA;
		} else {
			bit = BLOCK_GROUP_METADATA;
			cache->data = 0;
		}

		/* use EXTENT_LOCKED to prevent merging */
		set_extent_bits(block_group_cache, key.objectid,
				key.objectid + key.offset - 1,
				bit | EXTENT_LOCKED, GFP_NOFS);
		set_state_private(block_group_cache, key.objectid,
				  (unsigned long)cache);
	}
	btrfs_free_path(path);
set_size:
	btrfs_set_super_total_bytes(&info->super_copy, new_size);
	return 0;
}

C
Chris Mason 已提交
2640 2641 2642 2643 2644
int btrfs_read_block_groups(struct btrfs_root *root)
{
	struct btrfs_path *path;
	int ret;
	int err = 0;
2645
	int bit;
C
Chris Mason 已提交
2646
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
2647
	struct btrfs_fs_info *info = root->fs_info;
2648
	struct extent_map_tree *block_group_cache;
C
Chris Mason 已提交
2649 2650
	struct btrfs_key key;
	struct btrfs_key found_key;
2651
	struct extent_buffer *leaf;
2652 2653

	block_group_cache = &info->block_group_cache;
C
Chris Mason 已提交
2654

C
Chris Mason 已提交
2655
	root = info->extent_root;
C
Chris Mason 已提交
2656
	key.objectid = 0;
2657
	key.offset = BTRFS_BLOCK_GROUP_SIZE;
C
Chris Mason 已提交
2658 2659 2660 2661 2662 2663 2664
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);

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

	while(1) {
C
Chris Mason 已提交
2665
		ret = btrfs_search_slot(NULL, info->extent_root,
C
Chris Mason 已提交
2666 2667 2668 2669 2670
					&key, path, 0, 0);
		if (ret != 0) {
			err = ret;
			break;
		}
2671 2672
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
C
Chris Mason 已提交
2673 2674 2675 2676 2677
		cache = kmalloc(sizeof(*cache), GFP_NOFS);
		if (!cache) {
			err = -1;
			break;
		}
C
Chris Mason 已提交
2678

2679 2680 2681
		read_extent_buffer(leaf, &cache->item,
				   btrfs_item_ptr_offset(leaf, path->slots[0]),
				   sizeof(cache->item));
C
Chris Mason 已提交
2682
		memcpy(&cache->key, &found_key, sizeof(found_key));
2683
		cache->cached = 0;
2684
		cache->pinned = 0;
C
Chris Mason 已提交
2685 2686
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
2687

2688 2689 2690 2691
		if (cache->item.flags & BTRFS_BLOCK_GROUP_MIXED) {
			bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
			cache->data = BTRFS_BLOCK_GROUP_MIXED;
		} else if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
2692
			bit = BLOCK_GROUP_DATA;
2693
			cache->data = BTRFS_BLOCK_GROUP_DATA;
2694 2695 2696
		} else {
			bit = BLOCK_GROUP_METADATA;
			cache->data = 0;
2697
		}
2698 2699 2700 2701 2702 2703

		/* 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 已提交
2704
				  (unsigned long)cache);
2705

C
Chris Mason 已提交
2706
		if (key.objectid >=
2707
		    btrfs_super_total_bytes(&info->super_copy))
C
Chris Mason 已提交
2708 2709 2710 2711 2712 2713
			break;
	}

	btrfs_free_path(path);
	return 0;
}