extent-tree.c 38.1 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 21 22
#include "ctree.h"
#include "disk-io.h"
#include "print-tree.h"
23
#include "transaction.h"
24

25 26 27 28
#define BLOCK_GROUP_DATA EXTENT_WRITEBACK
#define BLOCK_GROUP_METADATA EXTENT_UPTODATE
#define BLOCK_GROUP_DIRTY EXTENT_DIRTY

29 30
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root);
C
Chris Mason 已提交
31 32
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root);
33

34 35 36 37 38 39
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;
40
	struct extent_buffer *leaf;
41
	struct extent_map_tree *free_space_cache;
42 43 44
	int slot;
	u64 last = 0;
	u64 hole_size;
45
	u64 first_free;
46 47 48
	int found = 0;

	root = root->fs_info->extent_root;
49
	free_space_cache = &root->fs_info->free_space_cache;
50 51 52

	if (block_group->cached)
		return 0;
53

54 55 56
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
57

58
	path->reada = 2;
59
	first_free = block_group->key.objectid;
60 61
	key.objectid = block_group->key.objectid;
	key.offset = 0;
62

63 64
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
65

66 67
	if (ret < 0)
		return ret;
68

69 70
	if (ret && path->slots[0] > 0)
		path->slots[0]--;
71

72
	while(1) {
73
		leaf = path->nodes[0];
74
		slot = path->slots[0];
75
		if (slot >= btrfs_header_nritems(leaf)) {
76
			ret = btrfs_next_leaf(root, path);
77 78
			if (ret < 0)
				goto err;
79
			if (ret == 0) {
80
				continue;
81
			} else {
82 83 84
				break;
			}
		}
85

86
		btrfs_item_key_to_cpu(leaf, &key, slot);
87 88 89 90 91 92
		if (key.objectid < block_group->key.objectid) {
			if (key.objectid + key.offset > first_free)
				first_free = key.objectid + key.offset;
			goto next;
		}

93 94 95 96
		if (key.objectid >= block_group->key.objectid +
		    block_group->key.offset) {
			break;
		}
97

98 99
		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
			if (!found) {
100
				last = first_free;
101 102
				found = 1;
			}
103 104 105 106 107
			if (key.objectid > last) {
				hole_size = key.objectid - last;
				set_extent_dirty(free_space_cache, last,
						 last + hole_size - 1,
						 GFP_NOFS);
108 109
			}
			last = key.objectid + key.offset;
110
		}
111
next:
112 113 114
		path->slots[0]++;
	}

115 116 117 118 119 120
	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;
121 122
		set_extent_dirty(free_space_cache, last,
				 last + hole_size - 1, GFP_NOFS);
123
	}
124
	block_group->cached = 1;
125
err:
126 127 128 129
	btrfs_free_path(path);
	return 0;
}

130 131
struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
							 btrfs_fs_info *info,
132
							 u64 bytenr)
C
Chris Mason 已提交
133
{
134 135 136 137 138
	struct extent_map_tree *block_group_cache;
	struct btrfs_block_group_cache *block_group = NULL;
	u64 ptr;
	u64 start;
	u64 end;
C
Chris Mason 已提交
139 140
	int ret;

141 142
	block_group_cache = &info->block_group_cache;
	ret = find_first_extent_bit(block_group_cache,
143
				    bytenr, &start, &end,
144
				    BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA);
C
Chris Mason 已提交
145
	if (ret) {
146
		return NULL;
C
Chris Mason 已提交
147
	}
148 149 150 151
	ret = get_state_private(block_group_cache, start, &ptr);
	if (ret)
		return NULL;

J
Jens Axboe 已提交
152
	block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
153 154


155
	if (block_group->key.objectid <= bytenr && bytenr <=
156 157 158
	    block_group->key.objectid + block_group->key.offset)
		return block_group;

C
Chris Mason 已提交
159 160 161
	return NULL;
}

162 163
static u64 find_search_start(struct btrfs_root *root,
			     struct btrfs_block_group_cache **cache_ret,
164
			     u64 search_start, int num, int data)
165 166 167
{
	int ret;
	struct btrfs_block_group_cache *cache = *cache_ret;
168
	u64 last;
169 170
	u64 start = 0;
	u64 end = 0;
171 172

again:
173 174 175
	ret = cache_block_group(root, cache);
	if (ret)
		goto out;
176 177
	last = max(search_start, cache->key.objectid);

178
	while(1) {
179 180
		ret = find_first_extent_bit(&root->fs_info->free_space_cache,
					    last, &start, &end, EXTENT_DIRTY);
181 182 183
		if (ret) {
			goto new_group;
		}
184 185 186 187 188

		start = max(last, start);
		last = end + 1;
		if (end + 1 - start < num)
			continue;
189
		if (start + num >= cache->key.objectid + cache->key.offset)
190
			goto new_group;
191
		return start;
192 193
	}
out:
194
	return search_start;
195 196

new_group:
197 198
	last = cache->key.objectid + cache->key.offset;
	cache = btrfs_lookup_block_group(root->fs_info, last);
199
	if (!cache) {
200
		return search_start;
201
	}
202
	cache = btrfs_find_block_group(root, cache, last, data, 0);
203 204 205 206
	*cache_ret = cache;
	goto again;
}

C
Chris Mason 已提交
207 208 209 210 211 212 213
static u64 div_factor(u64 num, int factor)
{
	num *= factor;
	do_div(num, 10);
	return num;
}

214 215
struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
						 struct btrfs_block_group_cache
C
Chris Mason 已提交
216
						 *hint, u64 search_start,
217
						 int data, int owner)
C
Chris Mason 已提交
218
{
219 220
	struct btrfs_block_group_cache *cache;
	struct extent_map_tree *block_group_cache;
221
	struct btrfs_block_group_cache *found_group = NULL;
C
Chris Mason 已提交
222 223
	struct btrfs_fs_info *info = root->fs_info;
	u64 used;
224 225
	u64 last = 0;
	u64 hint_last;
226 227 228 229 230
	u64 start;
	u64 end;
	u64 free_check;
	u64 ptr;
	int bit;
C
Chris Mason 已提交
231
	int ret;
232
	int full_search = 0;
233
	int factor = 8;
C
Chris Mason 已提交
234
	int data_swap = 0;
235

236 237
	block_group_cache = &info->block_group_cache;

238 239
	if (!owner)
		factor = 5;
C
Chris Mason 已提交
240

241 242 243 244
	if (data)
		bit = BLOCK_GROUP_DATA;
	else
		bit = BLOCK_GROUP_METADATA;
C
Chris Mason 已提交
245 246 247

	if (search_start) {
		struct btrfs_block_group_cache *shint;
248
		shint = btrfs_lookup_block_group(info, search_start);
249
		if (shint && shint->data == data) {
C
Chris Mason 已提交
250
			used = btrfs_block_group_used(&shint->item);
251
			if (used < div_factor(shint->key.offset, factor)) {
C
Chris Mason 已提交
252 253 254 255 256
				return shint;
			}
		}
	}
	if (hint && hint->data == data) {
257
		used = btrfs_block_group_used(&hint->item);
258
		if (used < div_factor(hint->key.offset, factor)) {
259 260
			return hint;
		}
261
		last = hint->key.objectid + hint->key.offset;
262 263
		hint_last = last;
	} else {
264 265 266 267 268 269
		if (hint)
			hint_last = max(hint->key.objectid, search_start);
		else
			hint_last = search_start;

		last = hint_last;
270 271
	}
again:
C
Chris Mason 已提交
272
	while(1) {
273 274 275
		ret = find_first_extent_bit(block_group_cache, last,
					    &start, &end, bit);
		if (ret)
C
Chris Mason 已提交
276
			break;
277 278 279 280 281

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

J
Jens Axboe 已提交
282
		cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
283 284 285 286 287 288 289 290
		last = cache->key.objectid + cache->key.offset;
		used = btrfs_block_group_used(&cache->item);

		if (full_search)
			free_check = cache->key.offset;
		else
			free_check = div_factor(cache->key.offset, factor);

291
		if (used < free_check) {
292 293
			found_group = cache;
			goto found;
C
Chris Mason 已提交
294
		}
295
		cond_resched();
C
Chris Mason 已提交
296
	}
297
	if (!full_search) {
C
Chris Mason 已提交
298
		last = search_start;
299 300 301
		full_search = 1;
		goto again;
	}
C
Chris Mason 已提交
302 303
	if (!data_swap) {
		data_swap = 1;
304
		bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
C
Chris Mason 已提交
305 306 307
		last = search_start;
		goto again;
	}
C
Chris Mason 已提交
308
found:
309
	return found_group;
C
Chris Mason 已提交
310 311
}

C
Chris Mason 已提交
312 313
int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
				struct btrfs_root *root,
314
				u64 bytenr, u64 num_bytes)
C
Chris Mason 已提交
315
{
316
	struct btrfs_path *path;
C
Chris Mason 已提交
317
	int ret;
C
Chris Mason 已提交
318
	struct btrfs_key key;
319
	struct extent_buffer *l;
C
Chris Mason 已提交
320
	struct btrfs_extent_item *item;
C
Chris Mason 已提交
321
	u32 refs;
C
Chris Mason 已提交
322

323
	WARN_ON(num_bytes < root->sectorsize);
324
	path = btrfs_alloc_path();
325 326
	if (!path)
		return -ENOMEM;
327

328
	key.objectid = bytenr;
329
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
330
	key.offset = num_bytes;
331
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
332
				0, 1);
333 334
	if (ret < 0)
		return ret;
335
	if (ret != 0) {
336
		BUG();
337
	}
C
Chris Mason 已提交
338
	BUG_ON(ret != 0);
339
	l = path->nodes[0];
340
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
341 342
	refs = btrfs_extent_refs(l, item);
	btrfs_set_extent_refs(l, item, refs + 1);
343
	btrfs_mark_buffer_dirty(path->nodes[0]);
344

345 346
	btrfs_release_path(root->fs_info->extent_root, path);
	btrfs_free_path(path);
347
	finish_current_insert(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
348
	del_pending_extents(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
349 350 351
	return 0;
}

352 353 354 355 356 357 358 359
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 已提交
360
static int lookup_extent_ref(struct btrfs_trans_handle *trans,
361 362
			     struct btrfs_root *root, u64 bytenr,
			     u64 num_bytes, u32 *refs)
363
{
364
	struct btrfs_path *path;
365
	int ret;
C
Chris Mason 已提交
366
	struct btrfs_key key;
367
	struct extent_buffer *l;
C
Chris Mason 已提交
368
	struct btrfs_extent_item *item;
369

370
	WARN_ON(num_bytes < root->sectorsize);
371
	path = btrfs_alloc_path();
372 373
	key.objectid = bytenr;
	key.offset = num_bytes;
374
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
375
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
376
				0, 0);
377 378
	if (ret < 0)
		goto out;
379 380
	if (ret != 0) {
		btrfs_print_leaf(root, path->nodes[0]);
381
		printk("failed to find block number %Lu\n", bytenr);
382
		BUG();
383 384
	}
	l = path->nodes[0];
385
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
386
	*refs = btrfs_extent_refs(l, item);
387
out:
388
	btrfs_free_path(path);
389 390 391
	return 0;
}

C
Chris Mason 已提交
392 393 394
int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root)
{
395 396
	return btrfs_inc_extent_ref(trans, root, root->node->start,
				    root->node->len);
C
Chris Mason 已提交
397 398
}

399
int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
400
		  struct extent_buffer *buf)
C
Chris Mason 已提交
401
{
402
	u64 bytenr;
403 404
	u32 nritems;
	struct btrfs_key key;
405
	struct btrfs_file_extent_item *fi;
C
Chris Mason 已提交
406
	int i;
407
	int level;
408
	int ret;
409 410
	int faili;
	int err;
411

412
	if (!root->ref_cows)
413
		return 0;
414

415
	level = btrfs_header_level(buf);
416 417
	nritems = btrfs_header_nritems(buf);
	for (i = 0; i < nritems; i++) {
418 419
		if (level == 0) {
			u64 disk_bytenr;
420 421
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
422
				continue;
423
			fi = btrfs_item_ptr(buf, i,
424
					    struct btrfs_file_extent_item);
425
			if (btrfs_file_extent_type(buf, fi) ==
426 427
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
428 429
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
C
Chris Mason 已提交
430
				continue;
431 432
			ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
				    btrfs_file_extent_disk_num_bytes(buf, fi));
433 434 435 436
			if (ret) {
				faili = i;
				goto fail;
			}
437
		} else {
438 439 440
			bytenr = btrfs_node_blockptr(buf, i);
			ret = btrfs_inc_extent_ref(trans, root, bytenr,
					   btrfs_level_size(root, level - 1));
441 442 443 444
			if (ret) {
				faili = i;
				goto fail;
			}
445
		}
C
Chris Mason 已提交
446 447
	}
	return 0;
448
fail:
C
Chris Mason 已提交
449
	WARN_ON(1);
450
	for (i =0; i < faili; i++) {
451 452
		if (level == 0) {
			u64 disk_bytenr;
453 454
			btrfs_item_key_to_cpu(buf, &key, i);
			if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
455
				continue;
456
			fi = btrfs_item_ptr(buf, i,
457
					    struct btrfs_file_extent_item);
458
			if (btrfs_file_extent_type(buf, fi) ==
459 460
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
461 462
			disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
			if (disk_bytenr == 0)
463
				continue;
464 465
			err = btrfs_free_extent(trans, root, disk_bytenr,
				    btrfs_file_extent_disk_num_bytes(buf,
466
								      fi), 0);
467 468
			BUG_ON(err);
		} else {
469 470 471
			bytenr = btrfs_node_blockptr(buf, i);
			err = btrfs_free_extent(trans, root, bytenr,
					btrfs_level_size(root, level - 1), 0);
472 473 474 475
			BUG_ON(err);
		}
	}
	return ret;
C
Chris Mason 已提交
476 477
}

C
Chris Mason 已提交
478 479 480 481 482 483 484 485
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;
486 487
	unsigned long bi;
	struct extent_buffer *leaf;
C
Chris Mason 已提交
488 489

	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
490 491
	if (ret < 0)
		goto fail;
C
Chris Mason 已提交
492
	BUG_ON(ret);
493 494 495 496 497

	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 已提交
498
	btrfs_release_path(extent_root, path);
499
fail:
C
Chris Mason 已提交
500 501 502 503 504 505 506 507 508 509
	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;

}

510 511
int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root)
C
Chris Mason 已提交
512
{
513 514
	struct extent_map_tree *block_group_cache;
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
515 516 517 518
	int ret;
	int err = 0;
	int werr = 0;
	struct btrfs_path *path;
519 520 521 522
	u64 last = 0;
	u64 start;
	u64 end;
	u64 ptr;
C
Chris Mason 已提交
523

524
	block_group_cache = &root->fs_info->block_group_cache;
C
Chris Mason 已提交
525 526 527 528 529
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

	while(1) {
530 531 532
		ret = find_first_extent_bit(block_group_cache, last,
					    &start, &end, BLOCK_GROUP_DIRTY);
		if (ret)
C
Chris Mason 已提交
533
			break;
534

535 536 537 538 539
		last = end + 1;
		ret = get_state_private(block_group_cache, start, &ptr);
		if (ret)
			break;

J
Jens Axboe 已提交
540
		cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
541 542 543 544 545 546 547 548 549 550
		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 已提交
551
		}
552 553
		clear_extent_bits(block_group_cache, start, end,
				  BLOCK_GROUP_DIRTY, GFP_NOFS);
C
Chris Mason 已提交
554 555 556 557 558 559 560
	}
	btrfs_free_path(path);
	return werr;
}

static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
561 562
			      u64 bytenr, u64 num_bytes, int alloc,
			      int mark_free, int data)
C
Chris Mason 已提交
563 564 565
{
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *info = root->fs_info;
566
	u64 total = num_bytes;
C
Chris Mason 已提交
567
	u64 old_val;
568
	u64 byte_in_group;
569 570
	u64 start;
	u64 end;
C
Chris Mason 已提交
571

C
Chris Mason 已提交
572
	while(total) {
573
		cache = btrfs_lookup_block_group(info, bytenr);
C
Chris Mason 已提交
574
		if (!cache) {
C
Chris Mason 已提交
575
			return -1;
C
Chris Mason 已提交
576
		}
577 578
		byte_in_group = bytenr - cache->key.objectid;
		WARN_ON(byte_in_group > cache->key.offset);
579 580 581 582
		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 已提交
583 584

		old_val = btrfs_block_group_used(&cache->item);
585
		num_bytes = min(total, cache->key.offset - byte_in_group);
C
Chris Mason 已提交
586
		if (alloc) {
C
Chris Mason 已提交
587
			if (cache->data != data &&
C
Chris Mason 已提交
588
			    old_val < (cache->key.offset >> 1)) {
589 590 591
				int bit_to_clear;
				int bit_to_set;
				cache->data = data;
C
Chris Mason 已提交
592
				if (data) {
593 594
					bit_to_clear = BLOCK_GROUP_METADATA;
					bit_to_set = BLOCK_GROUP_DATA;
C
Chris Mason 已提交
595 596 597
					cache->item.flags |=
						BTRFS_BLOCK_GROUP_DATA;
				} else {
598 599
					bit_to_clear = BLOCK_GROUP_DATA;
					bit_to_set = BLOCK_GROUP_METADATA;
C
Chris Mason 已提交
600 601 602
					cache->item.flags &=
						~BTRFS_BLOCK_GROUP_DATA;
				}
603 604 605 606 607 608
				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);
C
Chris Mason 已提交
609
			}
610
			old_val += num_bytes;
C
Chris Mason 已提交
611
		} else {
612
			old_val -= num_bytes;
613 614
			if (mark_free) {
				set_extent_dirty(&info->free_space_cache,
615
						 bytenr, bytenr + num_bytes - 1,
616
						 GFP_NOFS);
617
			}
C
Chris Mason 已提交
618
		}
C
Chris Mason 已提交
619
		btrfs_set_block_group_used(&cache->item, old_val);
620 621
		total -= num_bytes;
		bytenr += num_bytes;
C
Chris Mason 已提交
622 623 624 625
	}
	return 0;
}

626
int btrfs_copy_pinned(struct btrfs_root *root, struct extent_map_tree *copy)
C
Chris Mason 已提交
627 628
{
	u64 last = 0;
629 630 631
	u64 start;
	u64 end;
	struct extent_map_tree *pinned_extents = &root->fs_info->pinned_extents;
C
Chris Mason 已提交
632 633 634
	int ret;

	while(1) {
635 636 637
		ret = find_first_extent_bit(pinned_extents, last,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
C
Chris Mason 已提交
638
			break;
639 640
		set_extent_dirty(copy, start, end, GFP_NOFS);
		last = end + 1;
C
Chris Mason 已提交
641 642 643 644 645 646
	}
	return 0;
}

int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
647
			       struct extent_map_tree *unpin)
648
{
649 650
	u64 start;
	u64 end;
651
	int ret;
652
	struct extent_map_tree *pinned_extents = &root->fs_info->pinned_extents;
653 654 655
	struct extent_map_tree *free_space_cache;

	free_space_cache = &root->fs_info->free_space_cache;
656 657

	while(1) {
658 659 660
		ret = find_first_extent_bit(unpin, 0, &start, &end,
					    EXTENT_DIRTY);
		if (ret)
661
			break;
662 663 664 665 666

		clear_extent_dirty(pinned_extents, start, end,
				   GFP_NOFS);
		clear_extent_dirty(unpin, start, end, GFP_NOFS);
		set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
667 668 669 670
	}
	return 0;
}

671 672
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root)
C
Chris Mason 已提交
673
{
C
Chris Mason 已提交
674
	struct btrfs_key ins;
C
Chris Mason 已提交
675
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
676
	int ret;
677 678 679
	int err = 0;
	u64 start;
	u64 end;
680
	struct btrfs_fs_info *info = extent_root->fs_info;
C
Chris Mason 已提交
681

682
	btrfs_set_stack_extent_refs(&extent_item, 1);
683
	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
684 685
	btrfs_set_stack_extent_owner(&extent_item,
				     extent_root->root_key.objectid);
C
Chris Mason 已提交
686

687
	while(1) {
688 689 690
		ret = find_first_extent_bit(&info->extent_ins, 0, &start,
					    &end, EXTENT_LOCKED);
		if (ret)
691 692
			break;

693 694 695 696 697 698
		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);
C
Chris Mason 已提交
699 700 701 702
	}
	return 0;
}

703 704
static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
			  int pending)
C
Chris Mason 已提交
705
{
706
	int err = 0;
707
	struct extent_buffer *buf;
C
Chris Mason 已提交
708

C
Chris Mason 已提交
709
	if (!pending) {
710
		buf = btrfs_find_tree_block(root, bytenr, num_bytes);
711 712
		if (buf) {
			if (btrfs_buffer_uptodate(buf)) {
C
Chris Mason 已提交
713 714
				u64 transid =
				    root->fs_info->running_transaction->transid;
715 716
				if (btrfs_header_generation(buf) == transid) {
					free_extent_buffer(buf);
717
					return 1;
C
Chris Mason 已提交
718
				}
C
Chris Mason 已提交
719
			}
720
			free_extent_buffer(buf);
C
Chris Mason 已提交
721
		}
722
		set_extent_dirty(&root->fs_info->pinned_extents,
723
				 bytenr, bytenr + num_bytes - 1, GFP_NOFS);
C
Chris Mason 已提交
724
	} else {
725
		set_extent_bits(&root->fs_info->pending_del,
726 727
				bytenr, bytenr + num_bytes - 1,
				EXTENT_LOCKED, GFP_NOFS);
C
Chris Mason 已提交
728
	}
C
Chris Mason 已提交
729
	BUG_ON(err < 0);
C
Chris Mason 已提交
730 731 732
	return 0;
}

733
/*
734
 * remove an extent from the root, returns 0 on success
735
 */
736
static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
737
			 *root, u64 bytenr, u64 num_bytes, int pin,
738
			 int mark_free)
739
{
740
	struct btrfs_path *path;
C
Chris Mason 已提交
741
	struct btrfs_key key;
742 743
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
744
	struct extent_buffer *leaf;
745
	int ret;
C
Chris Mason 已提交
746
	struct btrfs_extent_item *ei;
C
Chris Mason 已提交
747
	u32 refs;
C
Chris Mason 已提交
748

749
	key.objectid = bytenr;
750
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
751
	key.offset = num_bytes;
752

753
	path = btrfs_alloc_path();
754 755
	if (!path)
		return -ENOMEM;
756

757 758 759 760
	ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
	if (ret < 0)
		return ret;
	BUG_ON(ret);
761 762 763

	leaf = path->nodes[0];
	ei = btrfs_item_ptr(leaf, path->slots[0],
C
Chris Mason 已提交
764
			    struct btrfs_extent_item);
765 766 767 768 769 770
	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 已提交
771
	if (refs == 0) {
772 773
		u64 super_used;
		u64 root_used;
C
Chris Mason 已提交
774 775

		if (pin) {
776
			ret = pin_down_bytes(root, bytenr, num_bytes, 0);
777 778 779
			if (ret > 0)
				mark_free = 1;
			BUG_ON(ret < 0);
C
Chris Mason 已提交
780 781
		}

782
		/* block accounting for super block */
783 784 785
		super_used = btrfs_super_bytes_used(&info->super_copy);
		btrfs_set_super_bytes_used(&info->super_copy,
					   super_used - num_bytes);
786 787

		/* block accounting for root item */
788
		root_used = btrfs_root_used(&root->root_item);
789
		btrfs_set_root_used(&root->root_item,
790
					   root_used - num_bytes);
791

792
		ret = btrfs_del_item(trans, extent_root, path);
793 794 795
		if (ret) {
			return ret;
		}
796
		ret = update_block_group(trans, root, bytenr, num_bytes, 0,
C
Chris Mason 已提交
797
					 mark_free, 0);
C
Chris Mason 已提交
798
		BUG_ON(ret);
799
	}
800
	btrfs_free_path(path);
801
	finish_current_insert(trans, extent_root);
802 803 804 805 806 807 808
	return ret;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
809 810
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root)
811 812
{
	int ret;
C
Chris Mason 已提交
813
	int err = 0;
814 815 816 817
	u64 start;
	u64 end;
	struct extent_map_tree *pending_del;
	struct extent_map_tree *pinned_extents;
C
Chris Mason 已提交
818

819 820
	pending_del = &extent_root->fs_info->pending_del;
	pinned_extents = &extent_root->fs_info->pinned_extents;
821 822

	while(1) {
823 824 825
		ret = find_first_extent_bit(pending_del, 0, &start, &end,
					    EXTENT_LOCKED);
		if (ret)
826
			break;
827 828 829 830 831 832 833 834

		set_extent_dirty(pinned_extents, start, end, GFP_NOFS);
		clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
				  GFP_NOFS);
		ret = __free_extent(trans, extent_root,
				     start, end + 1 - start, 0, 0);
		if (ret)
			err = ret;
835
	}
C
Chris Mason 已提交
836
	return err;
837 838 839 840 841
}

/*
 * remove an extent from the root, returns 0 on success
 */
842
int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
843
		      *root, u64 bytenr, u64 num_bytes, int pin)
844
{
845
	struct btrfs_root *extent_root = root->fs_info->extent_root;
846 847
	int pending_ret;
	int ret;
848

849
	WARN_ON(num_bytes < root->sectorsize);
850
	if (root == extent_root) {
851
		pin_down_bytes(root, bytenr, num_bytes, 1);
852 853
		return 0;
	}
854
	ret = __free_extent(trans, root, bytenr, num_bytes, pin, pin == 0);
C
Chris Mason 已提交
855
	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
856 857 858 859 860 861 862
	return ret ? ret : pending_ret;
}

/*
 * 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
863
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
864 865 866
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
867
static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
868 869
			    *orig_root, u64 num_bytes, u64 empty_size,
			    u64 search_start, u64 search_end, u64 hint_byte,
870 871
			    struct btrfs_key *ins, u64 exclude_start,
			    u64 exclude_nr, int data)
872
{
873
	struct btrfs_path *path;
C
Chris Mason 已提交
874
	struct btrfs_key key;
875 876 877
	int ret;
	u64 hole_size = 0;
	int slot = 0;
878
	u64 last_byte = 0;
C
Chris Mason 已提交
879
	u64 orig_search_start = search_start;
880
	int start_found;
881
	struct extent_buffer *l;
882
	struct btrfs_root * root = orig_root->fs_info->extent_root;
883
	struct btrfs_fs_info *info = root->fs_info;
884
	u64 total_needed = num_bytes;
C
Chris Mason 已提交
885
	int level;
C
Chris Mason 已提交
886
	struct btrfs_block_group_cache *block_group;
C
Chris Mason 已提交
887
	int full_scan = 0;
888
	int wrapped = 0;
889

890
	WARN_ON(num_bytes < root->sectorsize);
891 892
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);

893 894
	level = btrfs_header_level(root->node);

C
Chris Mason 已提交
895
	if (search_end == (u64)-1)
896 897 898
		search_end = btrfs_super_total_bytes(&info->super_copy);
	if (hint_byte) {
		block_group = btrfs_lookup_block_group(info, hint_byte);
C
Chris Mason 已提交
899
		block_group = btrfs_find_block_group(root, block_group,
900
						     hint_byte, data, 1);
C
Chris Mason 已提交
901 902 903
	} else {
		block_group = btrfs_find_block_group(root,
						     trans->block_group, 0,
904
						     data, 1);
C
Chris Mason 已提交
905 906
	}

907
	total_needed += empty_size;
908 909
	path = btrfs_alloc_path();

C
Chris Mason 已提交
910
check_failed:
911 912
	search_start = find_search_start(root, &block_group,
					 search_start, total_needed, data);
913
	btrfs_init_path(path);
914 915 916
	ins->objectid = search_start;
	ins->offset = 0;
	start_found = 0;
917
	path->reada = 2;
918

919
	ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
C
Chris Mason 已提交
920 921
	if (ret < 0)
		goto error;
C
Chris Mason 已提交
922

923
	if (path->slots[0] > 0) {
924
		path->slots[0]--;
925 926
	}

927 928 929
	l = path->nodes[0];
	btrfs_item_key_to_cpu(l, &key, path->slots[0]);

930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946
	/*
	 * a rare case, go back one key if we hit a block group item
	 * instead of an extent item
	 */
	if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
	    key.objectid + key.offset >= search_start) {
		ins->objectid = key.objectid;
		ins->offset = key.offset - 1;
		btrfs_release_path(root, path);
		ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
		if (ret < 0)
			goto error;

		if (path->slots[0] > 0) {
			path->slots[0]--;
		}
	}
947

948
	while (1) {
949
		l = path->nodes[0];
950
		slot = path->slots[0];
951
		if (slot >= btrfs_header_nritems(l)) {
952
			ret = btrfs_next_leaf(root, path);
953 954
			if (ret == 0)
				continue;
C
Chris Mason 已提交
955 956
			if (ret < 0)
				goto error;
957 958 959

			search_start = max(search_start,
					   block_group->key.objectid);
960 961
			if (!start_found) {
				ins->objectid = search_start;
C
Chris Mason 已提交
962
				ins->offset = search_end - search_start;
963 964 965
				start_found = 1;
				goto check_pending;
			}
966 967
			ins->objectid = last_byte > search_start ?
					last_byte : search_start;
C
Chris Mason 已提交
968
			ins->offset = search_end - ins->objectid;
969
			BUG_ON(ins->objectid >= search_end);
970 971
			goto check_pending;
		}
972
		btrfs_item_key_to_cpu(l, &key, slot);
973

974
		if (key.objectid >= search_start && key.objectid > last_byte &&
975
		    start_found) {
976 977 978 979 980
			if (last_byte < search_start)
				last_byte = search_start;
			hole_size = key.objectid - last_byte;
			if (hole_size >= num_bytes) {
				ins->objectid = last_byte;
981 982
				ins->offset = hole_size;
				goto check_pending;
983
			}
984
		}
985 986
		if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
			if (!start_found) {
987
				last_byte = key.objectid;
988 989
				start_found = 1;
			}
990
			goto next;
991 992
		}

993

994
		start_found = 1;
995
		last_byte = key.objectid + key.offset;
996

997
		if (!full_scan && last_byte >= block_group->key.objectid +
C
Chris Mason 已提交
998 999 1000
		    block_group->key.offset) {
			btrfs_release_path(root, path);
			search_start = block_group->key.objectid +
1001
				block_group->key.offset;
C
Chris Mason 已提交
1002 1003
			goto new_group;
		}
C
Chris Mason 已提交
1004
next:
1005
		path->slots[0]++;
1006
		cond_resched();
1007 1008 1009 1010 1011
	}
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
	 */
1012
	btrfs_release_path(root, path);
1013
	BUG_ON(ins->objectid < search_start);
1014

1015
	if (ins->objectid + num_bytes >= search_end)
1016 1017
		goto enospc;

1018 1019 1020 1021 1022 1023
	if (!full_scan && ins->objectid + num_bytes >= block_group->
	    key.objectid + block_group->key.offset) {
		search_start = block_group->key.objectid +
			block_group->key.offset;
		goto new_group;
	}
1024
	if (test_range_bit(&info->extent_ins, ins->objectid,
1025 1026
			   ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
		search_start = ins->objectid + num_bytes;
1027 1028 1029
		goto new_group;
	}
	if (test_range_bit(&info->pinned_extents, ins->objectid,
1030 1031
			   ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
		search_start = ins->objectid + num_bytes;
1032
		goto new_group;
1033
	}
1034
	if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1035 1036 1037 1038
	    ins->objectid < exclude_start + exclude_nr)) {
		search_start = exclude_start + exclude_nr;
		goto new_group;
	}
1039
	if (!data) {
1040
		block_group = btrfs_lookup_block_group(info, ins->objectid);
1041 1042
		if (block_group)
			trans->block_group = block_group;
1043
	}
1044
	ins->offset = num_bytes;
1045
	btrfs_free_path(path);
1046
	return 0;
C
Chris Mason 已提交
1047 1048

new_group:
1049
	if (search_start + num_bytes >= search_end) {
1050
enospc:
C
Chris Mason 已提交
1051
		search_start = orig_search_start;
1052 1053 1054 1055
		if (full_scan) {
			ret = -ENOSPC;
			goto error;
		}
1056 1057 1058
		if (wrapped) {
			if (!full_scan)
				total_needed -= empty_size;
1059
			full_scan = 1;
1060
		} else
1061
			wrapped = 1;
C
Chris Mason 已提交
1062
	}
1063
	block_group = btrfs_lookup_block_group(info, search_start);
1064
	cond_resched();
C
Chris Mason 已提交
1065 1066
	if (!full_scan)
		block_group = btrfs_find_block_group(root, block_group,
1067
						     search_start, data, 0);
C
Chris Mason 已提交
1068 1069
	goto check_failed;

C
Chris Mason 已提交
1070
error:
1071 1072
	btrfs_release_path(root, path);
	btrfs_free_path(path);
C
Chris Mason 已提交
1073
	return ret;
1074 1075 1076 1077 1078 1079 1080 1081
}
/*
 * 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.
 */
1082 1083
int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root, u64 owner,
1084
		       u64 num_bytes, u64 empty_size, u64 hint_byte,
C
Chris Mason 已提交
1085
		       u64 search_end, struct btrfs_key *ins, int data)
1086 1087 1088
{
	int ret;
	int pending_ret;
1089
	u64 super_used, root_used;
1090
	u64 search_start = 0;
1091 1092
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
C
Chris Mason 已提交
1093
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
1094

1095 1096
	btrfs_set_stack_extent_refs(&extent_item, 1);
	btrfs_set_stack_extent_owner(&extent_item, owner);
1097

1098 1099 1100
	WARN_ON(num_bytes < root->sectorsize);
	ret = find_free_extent(trans, root, num_bytes, empty_size,
			       search_start, search_end, hint_byte, ins,
1101 1102
			       trans->alloc_exclude_start,
			       trans->alloc_exclude_nr, data);
C
Chris Mason 已提交
1103
	BUG_ON(ret);
1104 1105
	if (ret)
		return ret;
1106

1107
	/* block accounting for super block */
1108 1109
	super_used = btrfs_super_bytes_used(&info->super_copy);
	btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1110

1111
	/* block accounting for root item */
1112 1113
	root_used = btrfs_root_used(&root->root_item);
	btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1114

1115 1116 1117 1118
	clear_extent_dirty(&root->fs_info->free_space_cache,
			   ins->objectid, ins->objectid + ins->offset - 1,
			   GFP_NOFS);

1119
	if (root == extent_root) {
1120 1121 1122
		set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
				ins->objectid + ins->offset - 1,
				EXTENT_LOCKED, GFP_NOFS);
1123
		WARN_ON(data == 1);
1124 1125 1126 1127 1128 1129
		goto update_block;
	}

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

1133 1134 1135
	trans->alloc_exclude_start = 0;
	trans->alloc_exclude_nr = 0;

C
Chris Mason 已提交
1136
	BUG_ON(ret);
1137
	finish_current_insert(trans, extent_root);
C
Chris Mason 已提交
1138
	pending_ret = del_pending_extents(trans, extent_root);
1139

1140
	if (ret) {
C
Chris Mason 已提交
1141
		return ret;
1142 1143
	}
	if (pending_ret) {
C
Chris Mason 已提交
1144
		return pending_ret;
1145
	}
1146 1147

update_block:
C
Chris Mason 已提交
1148 1149
	ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
				 data);
C
Chris Mason 已提交
1150
	BUG_ON(ret);
C
Chris Mason 已提交
1151
	return 0;
1152 1153 1154 1155 1156 1157
}

/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
1158
struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1159 1160
					     struct btrfs_root *root,
					     u32 blocksize, u64 hint,
1161
					     u64 empty_size)
1162
{
C
Chris Mason 已提交
1163
	struct btrfs_key ins;
1164
	int ret;
1165
	struct extent_buffer *buf;
1166

1167
	ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1168 1169
				 blocksize, empty_size, hint,
				 (u64)-1, &ins, 0);
1170
	if (ret) {
1171 1172
		BUG_ON(ret > 0);
		return ERR_PTR(ret);
1173
	}
1174
	buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1175
	if (!buf) {
1176
		btrfs_free_extent(trans, root, ins.objectid, blocksize, 0);
1177 1178
		return ERR_PTR(-ENOMEM);
	}
1179 1180 1181
	btrfs_set_buffer_uptodate(buf);
	set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
			 buf->start + buf->len - 1, GFP_NOFS);
1182 1183 1184 1185
	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;
1186
	btrfs_set_buffer_defrag(buf);
1187
	trans->blocks_used++;
1188 1189
	return buf;
}
1190

1191
static int drop_leaf_ref(struct btrfs_trans_handle *trans,
1192
			 struct btrfs_root *root, struct extent_buffer *leaf)
1193
{
1194
	struct btrfs_key key;
1195 1196 1197 1198 1199
	struct btrfs_file_extent_item *fi;
	int i;
	int nritems;
	int ret;

1200 1201
	BUG_ON(!btrfs_is_leaf(leaf));
	nritems = btrfs_header_nritems(leaf);
1202
	for (i = 0; i < nritems; i++) {
1203
		u64 disk_bytenr;
1204 1205 1206

		btrfs_item_key_to_cpu(leaf, &key, i);
		if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1207 1208
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1209 1210
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
1211
			continue;
1212 1213 1214 1215
		/*
		 * FIXME make sure to insert a trans record that
		 * repeats the snapshot del on crash
		 */
1216 1217
		disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
		if (disk_bytenr == 0)
C
Chris Mason 已提交
1218
			continue;
1219 1220
		ret = btrfs_free_extent(trans, root, disk_bytenr,
				btrfs_file_extent_disk_num_bytes(leaf, fi), 0);
1221 1222 1223 1224 1225
		BUG_ON(ret);
	}
	return 0;
}

1226
static void reada_walk_down(struct btrfs_root *root,
1227
			    struct extent_buffer *node)
1228 1229 1230
{
	int i;
	u32 nritems;
1231
	u64 bytenr;
1232 1233
	int ret;
	u32 refs;
1234 1235
	int level;
	u32 blocksize;
1236

1237
	nritems = btrfs_header_nritems(node);
1238
	level = btrfs_header_level(node);
1239
	for (i = 0; i < nritems; i++) {
1240 1241 1242
		bytenr = btrfs_node_blockptr(node, i);
		blocksize = btrfs_level_size(root, level - 1);
		ret = lookup_extent_ref(NULL, root, bytenr, blocksize, &refs);
1243 1244 1245
		BUG_ON(ret);
		if (refs != 1)
			continue;
1246
		mutex_unlock(&root->fs_info->fs_mutex);
1247
		ret = readahead_tree_block(root, bytenr, blocksize);
1248 1249
		cond_resched();
		mutex_lock(&root->fs_info->fs_mutex);
1250 1251 1252 1253 1254
		if (ret)
			break;
	}
}

C
Chris Mason 已提交
1255 1256 1257 1258
/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
1259 1260
static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
			  *root, struct btrfs_path *path, int *level)
C
Chris Mason 已提交
1261
{
1262 1263
	struct extent_buffer *next;
	struct extent_buffer *cur;
1264 1265
	u64 bytenr;
	u32 blocksize;
C
Chris Mason 已提交
1266 1267 1268
	int ret;
	u32 refs;

1269 1270
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
1271
	ret = lookup_extent_ref(trans, root,
1272 1273
				path->nodes[*level]->start,
				path->nodes[*level]->len, &refs);
C
Chris Mason 已提交
1274 1275 1276
	BUG_ON(ret);
	if (refs > 1)
		goto out;
1277

C
Chris Mason 已提交
1278 1279 1280
	/*
	 * walk down to the last node level and free all the leaves
	 */
1281
	while(*level >= 0) {
1282 1283
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
1284
		cur = path->nodes[*level];
1285 1286

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

1289
		if (btrfs_header_level(cur) != *level)
C
Chris Mason 已提交
1290
			WARN_ON(1);
1291

1292
		if (path->slots[*level] >=
1293
		    btrfs_header_nritems(cur))
C
Chris Mason 已提交
1294
			break;
1295 1296 1297 1298 1299
		if (*level == 0) {
			ret = drop_leaf_ref(trans, root, cur);
			BUG_ON(ret);
			break;
		}
1300 1301 1302
		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
		blocksize = btrfs_level_size(root, *level - 1);
		ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1303 1304
		BUG_ON(ret);
		if (refs != 1) {
C
Chris Mason 已提交
1305
			path->slots[*level]++;
1306 1307
			ret = btrfs_free_extent(trans, root, bytenr,
						blocksize, 1);
C
Chris Mason 已提交
1308 1309 1310
			BUG_ON(ret);
			continue;
		}
1311
		next = btrfs_find_tree_block(root, bytenr, blocksize);
1312 1313
		if (!next || !btrfs_buffer_uptodate(next)) {
			free_extent_buffer(next);
1314
			mutex_unlock(&root->fs_info->fs_mutex);
1315
			next = read_tree_block(root, bytenr, blocksize);
1316 1317 1318
			mutex_lock(&root->fs_info->fs_mutex);

			/* we dropped the lock, check one more time */
1319 1320
			ret = lookup_extent_ref(trans, root, bytenr,
						blocksize, &refs);
1321 1322 1323
			BUG_ON(ret);
			if (refs != 1) {
				path->slots[*level]++;
1324
				free_extent_buffer(next);
1325
				ret = btrfs_free_extent(trans, root,
1326
							bytenr, blocksize, 1);
1327 1328 1329 1330
				BUG_ON(ret);
				continue;
			}
		}
1331
		WARN_ON(*level <= 0);
C
Chris Mason 已提交
1332
		if (path->nodes[*level-1])
1333
			free_extent_buffer(path->nodes[*level-1]);
C
Chris Mason 已提交
1334
		path->nodes[*level-1] = next;
1335
		*level = btrfs_header_level(next);
C
Chris Mason 已提交
1336 1337 1338
		path->slots[*level] = 0;
	}
out:
1339 1340
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
1341 1342
	ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
				path->nodes[*level]->len, 1);
1343
	free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
1344 1345 1346 1347 1348 1349
	path->nodes[*level] = NULL;
	*level += 1;
	BUG_ON(ret);
	return 0;
}

C
Chris Mason 已提交
1350 1351 1352 1353 1354
/*
 * 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
 */
1355 1356
static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
			*root, struct btrfs_path *path, int *level)
C
Chris Mason 已提交
1357 1358 1359 1360
{
	int i;
	int slot;
	int ret;
1361 1362
	struct btrfs_root_item *root_item = &root->root_item;

C
Chris Mason 已提交
1363
	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
C
Chris Mason 已提交
1364
		slot = path->slots[i];
1365 1366 1367 1368
		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 已提交
1369 1370
			path->slots[i]++;
			*level = i;
1371
			WARN_ON(*level == 0);
1372
			btrfs_node_key(node, &disk_key, path->slots[i]);
1373
			memcpy(&root_item->drop_progress,
1374
			       &disk_key, sizeof(disk_key));
1375
			root_item->drop_level = i;
C
Chris Mason 已提交
1376 1377
			return 0;
		} else {
1378
			ret = btrfs_free_extent(trans, root,
1379 1380
						path->nodes[*level]->start,
						path->nodes[*level]->len, 1);
1381
			BUG_ON(ret);
1382
			free_extent_buffer(path->nodes[*level]);
C
Chris Mason 已提交
1383
			path->nodes[*level] = NULL;
C
Chris Mason 已提交
1384 1385 1386 1387 1388 1389
			*level = i + 1;
		}
	}
	return 1;
}

C
Chris Mason 已提交
1390 1391 1392 1393 1394
/*
 * 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.
 */
1395
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
1396
			*root)
C
Chris Mason 已提交
1397
{
1398
	int ret = 0;
C
Chris Mason 已提交
1399
	int wret;
C
Chris Mason 已提交
1400
	int level;
1401
	struct btrfs_path *path;
C
Chris Mason 已提交
1402 1403
	int i;
	int orig_level;
1404
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
1405

1406 1407
	path = btrfs_alloc_path();
	BUG_ON(!path);
C
Chris Mason 已提交
1408

1409
	level = btrfs_header_level(root->node);
C
Chris Mason 已提交
1410
	orig_level = level;
1411 1412
	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
		path->nodes[level] = root->node;
1413
		extent_buffer_get(root->node);
1414 1415 1416
		path->slots[level] = 0;
	} else {
		struct btrfs_key key;
1417 1418
		struct btrfs_disk_key found_key;
		struct extent_buffer *node;
1419

1420
		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1421 1422
		level = root_item->drop_level;
		path->lowest_level = level;
1423
		wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1424
		if (wret < 0) {
1425 1426 1427
			ret = wret;
			goto out;
		}
1428 1429 1430 1431
		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)));
1432
	}
C
Chris Mason 已提交
1433
	while(1) {
1434
		wret = walk_down_tree(trans, root, path, &level);
C
Chris Mason 已提交
1435
		if (wret > 0)
C
Chris Mason 已提交
1436
			break;
C
Chris Mason 已提交
1437 1438 1439
		if (wret < 0)
			ret = wret;

1440
		wret = walk_up_tree(trans, root, path, &level);
C
Chris Mason 已提交
1441
		if (wret > 0)
C
Chris Mason 已提交
1442
			break;
C
Chris Mason 已提交
1443 1444
		if (wret < 0)
			ret = wret;
1445 1446
		ret = -EAGAIN;
		break;
C
Chris Mason 已提交
1447
	}
C
Chris Mason 已提交
1448
	for (i = 0; i <= orig_level; i++) {
1449
		if (path->nodes[i]) {
1450
			free_extent_buffer(path->nodes[i]);
1451
			path->nodes[i] = NULL;
C
Chris Mason 已提交
1452
		}
C
Chris Mason 已提交
1453
	}
1454
out:
1455
	btrfs_free_path(path);
C
Chris Mason 已提交
1456
	return ret;
C
Chris Mason 已提交
1457
}
C
Chris Mason 已提交
1458

1459
int btrfs_free_block_groups(struct btrfs_fs_info *info)
C
Chris Mason 已提交
1460
{
1461 1462
	u64 start;
	u64 end;
1463
	u64 ptr;
C
Chris Mason 已提交
1464 1465
	int ret;
	while(1) {
1466 1467 1468
		ret = find_first_extent_bit(&info->block_group_cache, 0,
					    &start, &end, (unsigned int)-1);
		if (ret)
C
Chris Mason 已提交
1469
			break;
1470 1471 1472
		ret = get_state_private(&info->block_group_cache, start, &ptr);
		if (!ret)
			kfree((void *)(unsigned long)ptr);
1473 1474
		clear_extent_bits(&info->block_group_cache, start,
				  end, (unsigned int)-1, GFP_NOFS);
C
Chris Mason 已提交
1475
	}
1476
	while(1) {
1477 1478 1479
		ret = find_first_extent_bit(&info->free_space_cache, 0,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
1480
			break;
1481 1482
		clear_extent_dirty(&info->free_space_cache, start,
				   end, GFP_NOFS);
1483
	}
C
Chris Mason 已提交
1484 1485 1486
	return 0;
}

C
Chris Mason 已提交
1487 1488 1489 1490 1491
int btrfs_read_block_groups(struct btrfs_root *root)
{
	struct btrfs_path *path;
	int ret;
	int err = 0;
1492
	int bit;
C
Chris Mason 已提交
1493
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
1494
	struct btrfs_fs_info *info = root->fs_info;
1495
	struct extent_map_tree *block_group_cache;
C
Chris Mason 已提交
1496 1497
	struct btrfs_key key;
	struct btrfs_key found_key;
1498
	struct extent_buffer *leaf;
1499 1500

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

C
Chris Mason 已提交
1502
	root = info->extent_root;
C
Chris Mason 已提交
1503
	key.objectid = 0;
1504
	key.offset = BTRFS_BLOCK_GROUP_SIZE;
C
Chris Mason 已提交
1505 1506 1507 1508 1509 1510 1511
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);

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

	while(1) {
C
Chris Mason 已提交
1512
		ret = btrfs_search_slot(NULL, info->extent_root,
C
Chris Mason 已提交
1513 1514 1515 1516 1517
					&key, path, 0, 0);
		if (ret != 0) {
			err = ret;
			break;
		}
1518 1519
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
C
Chris Mason 已提交
1520 1521 1522 1523 1524
		cache = kmalloc(sizeof(*cache), GFP_NOFS);
		if (!cache) {
			err = -1;
			break;
		}
C
Chris Mason 已提交
1525

1526 1527 1528
		read_extent_buffer(leaf, &cache->item,
				   btrfs_item_ptr_offset(leaf, path->slots[0]),
				   sizeof(cache->item));
C
Chris Mason 已提交
1529
		memcpy(&cache->key, &found_key, sizeof(found_key));
1530 1531
		cache->cached = 0;

C
Chris Mason 已提交
1532 1533
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
1534

1535 1536 1537 1538 1539 1540
		if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
			bit = BLOCK_GROUP_DATA;
			cache->data = 1;
		} else {
			bit = BLOCK_GROUP_METADATA;
			cache->data = 0;
1541
		}
1542 1543 1544 1545 1546 1547

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

C
Chris Mason 已提交
1550
		if (key.objectid >=
1551
		    btrfs_super_total_bytes(&info->super_copy))
C
Chris Mason 已提交
1552 1553 1554 1555 1556 1557
			break;
	}

	btrfs_free_path(path);
	return 0;
}