extent-tree.c 37.9 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 152 153 154
	ret = get_state_private(block_group_cache, start, &ptr);
	if (ret)
		return NULL;

	block_group = (struct btrfs_block_group_cache *)ptr;


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 282 283 284 285 286 287 288 289 290

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

		cache = (struct btrfs_block_group_cache *)ptr;
		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 540 541 542 543 544 545 546 547 548 549 550
		last = end + 1;
		ret = get_state_private(block_group_cache, start, &ptr);
		if (ret)
			break;

		cache = (struct btrfs_block_group_cache *)ptr;
		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
				int bit_to_clear;
				int bit_to_set;
C
Chris Mason 已提交
591

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

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

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

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

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

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

		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);
668 669 670 671
	}
	return 0;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

		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;
834
	}
C
Chris Mason 已提交
835
	return err;
836 837 838 839 840
}

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

848
	WARN_ON(num_bytes < root->sectorsize);
849
	if (root == extent_root) {
850
		pin_down_bytes(root, bytenr, num_bytes, 1);
851 852
		return 0;
	}
853
	ret = __free_extent(trans, root, bytenr, num_bytes, pin, pin == 0);
C
Chris Mason 已提交
854
	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
855 856 857 858 859 860 861
	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
862
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
863 864 865
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
866
static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
867 868
			    *orig_root, u64 num_bytes, u64 empty_size,
			    u64 search_start, u64 search_end, u64 hint_byte,
869 870
			    struct btrfs_key *ins, u64 exclude_start,
			    u64 exclude_nr, int data)
871
{
872
	struct btrfs_path *path;
C
Chris Mason 已提交
873
	struct btrfs_key key;
874 875 876
	int ret;
	u64 hole_size = 0;
	int slot = 0;
877
	u64 last_byte = 0;
C
Chris Mason 已提交
878
	u64 orig_search_start = search_start;
879
	int start_found;
880
	struct extent_buffer *l;
881
	struct btrfs_root * root = orig_root->fs_info->extent_root;
882
	struct btrfs_fs_info *info = root->fs_info;
883
	u64 total_needed = num_bytes;
C
Chris Mason 已提交
884
	int level;
C
Chris Mason 已提交
885
	struct btrfs_block_group_cache *block_group;
C
Chris Mason 已提交
886
	int full_scan = 0;
887
	int wrapped = 0;
888

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

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

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

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

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

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

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

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

929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945
	/*
	 * 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]--;
		}
	}
946

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

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

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

992

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1458
int btrfs_free_block_groups(struct btrfs_fs_info *info)
C
Chris Mason 已提交
1459
{
1460 1461
	u64 start;
	u64 end;
C
Chris Mason 已提交
1462 1463 1464
	int ret;

	while(1) {
1465 1466 1467
		ret = find_first_extent_bit(&info->block_group_cache, 0,
					    &start, &end, (unsigned int)-1);
		if (ret)
C
Chris Mason 已提交
1468
			break;
1469 1470
		clear_extent_bits(&info->block_group_cache, start,
				  end, (unsigned int)-1, GFP_NOFS);
C
Chris Mason 已提交
1471
	}
1472
	while(1) {
1473 1474 1475
		ret = find_first_extent_bit(&info->free_space_cache, 0,
					    &start, &end, EXTENT_DIRTY);
		if (ret)
1476
			break;
1477 1478
		clear_extent_dirty(&info->free_space_cache, start,
				   end, GFP_NOFS);
1479
	}
C
Chris Mason 已提交
1480 1481 1482
	return 0;
}

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

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

C
Chris Mason 已提交
1498
	root = info->extent_root;
C
Chris Mason 已提交
1499
	key.objectid = 0;
1500
	key.offset = BTRFS_BLOCK_GROUP_SIZE;
C
Chris Mason 已提交
1501 1502 1503 1504 1505 1506 1507
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);

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

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

1522 1523 1524
		read_extent_buffer(leaf, &cache->item,
				   btrfs_item_ptr_offset(leaf, path->slots[0]),
				   sizeof(cache->item));
C
Chris Mason 已提交
1525
		memcpy(&cache->key, &found_key, sizeof(found_key));
1526 1527
		cache->cached = 0;

C
Chris Mason 已提交
1528 1529
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
1530

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

		/* 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,
				  (u64)cache);

C
Chris Mason 已提交
1546
		if (key.objectid >=
1547
		    btrfs_super_total_bytes(&info->super_copy))
C
Chris Mason 已提交
1548 1549 1550 1551 1552 1553
			break;
	}

	btrfs_free_path(path);
	return 0;
}