extent-tree.c 41.3 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
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root);
C
Chris Mason 已提交
27 28
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root);
29

30 31 32 33 34 35 36 37 38 39 40 41
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;
	struct btrfs_leaf *leaf;
	struct radix_tree_root *extent_radix;
	int slot;
	u64 i;
	u64 last = 0;
	u64 hole_size;
42
	u64 first_free;
43 44 45 46 47 48 49 50 51 52 53 54
	int found = 0;

	root = root->fs_info->extent_root;
	extent_radix = &root->fs_info->extent_map_radix;

	if (block_group->cached)
		return 0;
	if (block_group->data)
		return 0;
	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
55

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

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

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

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

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

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

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

97 98
		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
			if (!found) {
99
				last = first_free;
100 101
				found = 1;
			}
102 103 104 105 106
			hole_size = key.objectid - last;
			for (i = 0; i < hole_size; i++) {
				set_radix_bit(extent_radix, last + i);
			}
			last = key.objectid + key.offset;
107
		}
108
next:
109 110 111
		path->slots[0]++;
	}

112 113 114 115 116 117 118 119 120 121 122
	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;
		for (i = 0; i < hole_size; i++) {
			set_radix_bit(extent_radix,
					last + i);
		}
	}
123
	block_group->cached = 1;
124
err:
125 126 127 128
	btrfs_free_path(path);
	return 0;
}

129 130 131
struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
							 btrfs_fs_info *info,
							 u64 blocknr)
C
Chris Mason 已提交
132 133 134 135 136 137 138 139
{
	struct btrfs_block_group_cache *block_group;
	int ret;

	ret = radix_tree_gang_lookup(&info->block_group_radix,
				     (void **)&block_group,
				     blocknr, 1);
	if (ret) {
C
Chris Mason 已提交
140
		if (block_group->key.objectid <= blocknr && blocknr <=
C
Chris Mason 已提交
141 142 143 144 145 146 147
		    block_group->key.objectid + block_group->key.offset)
			return block_group;
	}
	ret = radix_tree_gang_lookup(&info->block_group_data_radix,
				     (void **)&block_group,
				     blocknr, 1);
	if (ret) {
C
Chris Mason 已提交
148
		if (block_group->key.objectid <= blocknr && blocknr <=
C
Chris Mason 已提交
149 150 151 152 153 154
		    block_group->key.objectid + block_group->key.offset)
			return block_group;
	}
	return NULL;
}

155 156 157
static u64 leaf_range(struct btrfs_root *root)
{
	u64 size = BTRFS_LEAF_DATA_SIZE(root);
C
Chris Mason 已提交
158 159
	do_div(size, sizeof(struct btrfs_extent_item) +
		sizeof(struct btrfs_item));
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
	return size;
}

static u64 find_search_start(struct btrfs_root *root,
			     struct btrfs_block_group_cache **cache_ret,
			     u64 search_start, int num)
{
	unsigned long gang[8];
	int ret;
	struct btrfs_block_group_cache *cache = *cache_ret;
	u64 last = max(search_start, cache->key.objectid);

	if (cache->data)
		goto out;
again:
175 176 177
	ret = cache_block_group(root, cache);
	if (ret)
		goto out;
178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
	while(1) {
		ret = find_first_radix_bit(&root->fs_info->extent_map_radix,
					   gang, last, ARRAY_SIZE(gang));
		if (!ret)
			goto out;
		last = gang[ret-1] + 1;
		if (num > 1) {
			if (ret != ARRAY_SIZE(gang)) {
				goto new_group;
			}
			if (gang[ret-1] - gang[0] > leaf_range(root)) {
				continue;
			}
		}
		if (gang[0] >= cache->key.objectid + cache->key.offset) {
			goto new_group;
		}
		return gang[0];
	}
out:
	return max(cache->last_alloc, search_start);

new_group:
201 202
	cache = btrfs_lookup_block_group(root->fs_info,
					 last + cache->key.offset - 1);
203 204 205 206
	if (!cache) {
		return max((*cache_ret)->last_alloc, search_start);
	}
	cache = btrfs_find_block_group(root, cache,
207
				       last + cache->key.offset - 1, 0, 0);
208 209 210 211
	*cache_ret = cache;
	goto again;
}

C
Chris Mason 已提交
212 213 214 215 216 217 218
static u64 div_factor(u64 num, int factor)
{
	num *= factor;
	do_div(num, 10);
	return num;
}

219 220
struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
						 struct btrfs_block_group_cache
C
Chris Mason 已提交
221
						 *hint, u64 search_start,
222
						 int data, int owner)
C
Chris Mason 已提交
223 224
{
	struct btrfs_block_group_cache *cache[8];
225
	struct btrfs_block_group_cache *found_group = NULL;
C
Chris Mason 已提交
226
	struct btrfs_fs_info *info = root->fs_info;
C
Chris Mason 已提交
227
	struct radix_tree_root *radix;
C
Chris Mason 已提交
228
	struct radix_tree_root *swap_radix;
C
Chris Mason 已提交
229
	u64 used;
230 231
	u64 last = 0;
	u64 hint_last;
C
Chris Mason 已提交
232 233
	int i;
	int ret;
234
	int full_search = 0;
235
	int factor = 8;
C
Chris Mason 已提交
236
	int data_swap = 0;
237 238 239

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

C
Chris Mason 已提交
241
	if (data) {
C
Chris Mason 已提交
242
		radix = &info->block_group_data_radix;
C
Chris Mason 已提交
243 244
		swap_radix = &info->block_group_radix;
	} else {
C
Chris Mason 已提交
245
		radix = &info->block_group_radix;
C
Chris Mason 已提交
246 247
		swap_radix = &info->block_group_data_radix;
	}
C
Chris Mason 已提交
248 249 250

	if (search_start) {
		struct btrfs_block_group_cache *shint;
251
		shint = btrfs_lookup_block_group(info, search_start);
252
		if (shint && shint->data == data) {
C
Chris Mason 已提交
253 254
			used = btrfs_block_group_used(&shint->item);
			if (used + shint->pinned <
C
Chris Mason 已提交
255
			    div_factor(shint->key.offset, factor)) {
C
Chris Mason 已提交
256 257 258 259 260
				return shint;
			}
		}
	}
	if (hint && hint->data == data) {
261
		used = btrfs_block_group_used(&hint->item);
C
Chris Mason 已提交
262 263
		if (used + hint->pinned <
		    div_factor(hint->key.offset, factor)) {
264 265
			return hint;
		}
C
Chris Mason 已提交
266
		if (used >= div_factor(hint->key.offset, 8)) {
C
Chris Mason 已提交
267 268 269 270 271
			radix_tree_tag_clear(radix,
					     hint->key.objectid +
					     hint->key.offset - 1,
					     BTRFS_BLOCK_GROUP_AVAIL);
		}
272
		last = hint->key.offset * 3;
C
Chris Mason 已提交
273
		if (hint->key.objectid >= last)
274 275
			last = max(search_start + hint->key.offset - 1,
				   hint->key.objectid - last);
C
Chris Mason 已提交
276 277
		else
			last = hint->key.objectid + hint->key.offset;
278 279
		hint_last = last;
	} else {
280 281 282 283 284 285
		if (hint)
			hint_last = max(hint->key.objectid, search_start);
		else
			hint_last = search_start;

		last = hint_last;
286
	}
C
Chris Mason 已提交
287
	while(1) {
C
Chris Mason 已提交
288
		ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
C
Chris Mason 已提交
289
						 last, ARRAY_SIZE(cache),
290
						 BTRFS_BLOCK_GROUP_AVAIL);
C
Chris Mason 已提交
291 292 293
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
294 295
			last = cache[i]->key.objectid +
				cache[i]->key.offset;
C
Chris Mason 已提交
296
			used = btrfs_block_group_used(&cache[i]->item);
C
Chris Mason 已提交
297
			if (used + cache[i]->pinned <
C
Chris Mason 已提交
298
			    div_factor(cache[i]->key.offset, factor)) {
299 300
				found_group = cache[i];
				goto found;
C
Chris Mason 已提交
301
			}
C
Chris Mason 已提交
302
			if (used >= div_factor(cache[i]->key.offset, 8)) {
C
Chris Mason 已提交
303 304 305 306 307
				radix_tree_tag_clear(radix,
						     cache[i]->key.objectid +
						     cache[i]->key.offset - 1,
						     BTRFS_BLOCK_GROUP_AVAIL);
			}
C
Chris Mason 已提交
308
		}
309
		cond_resched();
C
Chris Mason 已提交
310
	}
311 312
	last = hint_last;
again:
C
Chris Mason 已提交
313
	while(1) {
C
Chris Mason 已提交
314 315
		ret = radix_tree_gang_lookup(radix, (void **)cache,
					     last, ARRAY_SIZE(cache));
C
Chris Mason 已提交
316 317 318
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
319 320
			last = cache[i]->key.objectid +
				cache[i]->key.offset;
C
Chris Mason 已提交
321
			used = btrfs_block_group_used(&cache[i]->item);
C
Chris Mason 已提交
322
			if (used + cache[i]->pinned < cache[i]->key.offset) {
323 324
				found_group = cache[i];
				goto found;
C
Chris Mason 已提交
325
			}
C
Chris Mason 已提交
326 327 328 329 330 331
			if (used >= cache[i]->key.offset) {
				radix_tree_tag_clear(radix,
						     cache[i]->key.objectid +
						     cache[i]->key.offset - 1,
						     BTRFS_BLOCK_GROUP_AVAIL);
			}
C
Chris Mason 已提交
332
		}
333
		cond_resched();
C
Chris Mason 已提交
334
	}
335
	if (!full_search) {
C
Chris Mason 已提交
336
		last = search_start;
337 338 339
		full_search = 1;
		goto again;
	}
C
Chris Mason 已提交
340 341 342 343 344 345 346 347
	if (!data_swap) {
		struct radix_tree_root *tmp = radix;
		data_swap = 1;
		radix = swap_radix;
		swap_radix = tmp;
		last = search_start;
		goto again;
	}
348
	if (!found_group) {
C
Chris Mason 已提交
349
		ret = radix_tree_gang_lookup(radix,
350
					     (void **)&found_group, 0, 1);
C
Chris Mason 已提交
351 352 353 354 355
		if (ret == 0) {
			ret = radix_tree_gang_lookup(swap_radix,
						     (void **)&found_group,
						     0, 1);
		}
356 357
		BUG_ON(ret != 1);
	}
C
Chris Mason 已提交
358
found:
359
	return found_group;
C
Chris Mason 已提交
360 361
}

C
Chris Mason 已提交
362 363 364
int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
				struct btrfs_root *root,
				u64 blocknr, u64 num_blocks)
C
Chris Mason 已提交
365
{
366
	struct btrfs_path *path;
C
Chris Mason 已提交
367
	int ret;
C
Chris Mason 已提交
368
	struct btrfs_key key;
C
Chris Mason 已提交
369 370
	struct btrfs_leaf *l;
	struct btrfs_extent_item *item;
C
Chris Mason 已提交
371
	u32 refs;
C
Chris Mason 已提交
372

373
	path = btrfs_alloc_path();
374 375
	if (!path)
		return -ENOMEM;
376

C
Chris Mason 已提交
377 378
	key.objectid = blocknr;
	key.flags = 0;
379
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
380
	key.offset = num_blocks;
381
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
382
				0, 1);
383 384
	if (ret < 0)
		return ret;
385
	if (ret != 0) {
386
		BUG();
387
	}
C
Chris Mason 已提交
388
	BUG_ON(ret != 0);
389 390
	l = btrfs_buffer_leaf(path->nodes[0]);
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
C
Chris Mason 已提交
391 392
	refs = btrfs_extent_refs(item);
	btrfs_set_extent_refs(item, refs + 1);
393
	btrfs_mark_buffer_dirty(path->nodes[0]);
394

395 396
	btrfs_release_path(root->fs_info->extent_root, path);
	btrfs_free_path(path);
397
	finish_current_insert(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
398
	del_pending_extents(trans, root->fs_info->extent_root);
C
Chris Mason 已提交
399 400 401
	return 0;
}

402 403 404 405 406 407 408 409
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 已提交
410 411 412
static int lookup_extent_ref(struct btrfs_trans_handle *trans,
			     struct btrfs_root *root, u64 blocknr,
			     u64 num_blocks, u32 *refs)
413
{
414
	struct btrfs_path *path;
415
	int ret;
C
Chris Mason 已提交
416
	struct btrfs_key key;
C
Chris Mason 已提交
417 418
	struct btrfs_leaf *l;
	struct btrfs_extent_item *item;
419 420

	path = btrfs_alloc_path();
421
	key.objectid = blocknr;
422
	key.offset = num_blocks;
423 424
	key.flags = 0;
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
425
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
426
				0, 0);
427 428
	if (ret < 0)
		goto out;
429 430
	if (ret != 0)
		BUG();
431 432
	l = btrfs_buffer_leaf(path->nodes[0]);
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
C
Chris Mason 已提交
433
	*refs = btrfs_extent_refs(item);
434
out:
435
	btrfs_free_path(path);
436 437 438
	return 0;
}

C
Chris Mason 已提交
439 440 441
int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root)
{
C
Chris Mason 已提交
442
	return btrfs_inc_extent_ref(trans, root, bh_blocknr(root->node), 1);
C
Chris Mason 已提交
443 444
}

445
int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
C
Chris Mason 已提交
446
		  struct buffer_head *buf)
C
Chris Mason 已提交
447 448
{
	u64 blocknr;
C
Chris Mason 已提交
449
	struct btrfs_node *buf_node;
450 451 452
	struct btrfs_leaf *buf_leaf;
	struct btrfs_disk_key *key;
	struct btrfs_file_extent_item *fi;
C
Chris Mason 已提交
453
	int i;
454 455
	int leaf;
	int ret;
456 457
	int faili;
	int err;
458

459
	if (!root->ref_cows)
460
		return 0;
C
Chris Mason 已提交
461
	buf_node = btrfs_buffer_node(buf);
462 463
	leaf = btrfs_is_leaf(buf_node);
	buf_leaf = btrfs_buffer_leaf(buf);
C
Chris Mason 已提交
464
	for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
465
		if (leaf) {
C
Chris Mason 已提交
466
			u64 disk_blocknr;
467 468 469 470 471
			key = &buf_leaf->items[i].key;
			if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
				continue;
			fi = btrfs_item_ptr(buf_leaf, i,
					    struct btrfs_file_extent_item);
472 473 474
			if (btrfs_file_extent_type(fi) ==
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
C
Chris Mason 已提交
475 476 477 478
			disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
			if (disk_blocknr == 0)
				continue;
			ret = btrfs_inc_extent_ref(trans, root, disk_blocknr,
479
				    btrfs_file_extent_disk_num_blocks(fi));
480 481 482 483
			if (ret) {
				faili = i;
				goto fail;
			}
484 485
		} else {
			blocknr = btrfs_node_blockptr(buf_node, i);
C
Chris Mason 已提交
486
			ret = btrfs_inc_extent_ref(trans, root, blocknr, 1);
487 488 489 490
			if (ret) {
				faili = i;
				goto fail;
			}
491
		}
C
Chris Mason 已提交
492 493
	}
	return 0;
494
fail:
C
Chris Mason 已提交
495
	WARN_ON(1);
496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519
	for (i =0; i < faili; i++) {
		if (leaf) {
			u64 disk_blocknr;
			key = &buf_leaf->items[i].key;
			if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
				continue;
			fi = btrfs_item_ptr(buf_leaf, i,
					    struct btrfs_file_extent_item);
			if (btrfs_file_extent_type(fi) ==
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
			disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
			if (disk_blocknr == 0)
				continue;
			err = btrfs_free_extent(trans, root, disk_blocknr,
				    btrfs_file_extent_disk_num_blocks(fi), 0);
			BUG_ON(err);
		} else {
			blocknr = btrfs_node_blockptr(buf_node, i);
			err = btrfs_free_extent(trans, root, blocknr, 1, 0);
			BUG_ON(err);
		}
	}
	return ret;
C
Chris Mason 已提交
520 521
}

C
Chris Mason 已提交
522 523 524 525 526 527 528 529 530 531 532
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;
	struct btrfs_block_group_item *bi;

	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
533 534
	if (ret < 0)
		goto fail;
C
Chris Mason 已提交
535 536 537 538
	BUG_ON(ret);
	bi = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
			    struct btrfs_block_group_item);
	memcpy(bi, &cache->item, sizeof(*bi));
C
Chris Mason 已提交
539
	btrfs_mark_buffer_dirty(path->nodes[0]);
C
Chris Mason 已提交
540
	btrfs_release_path(extent_root, path);
541
fail:
C
Chris Mason 已提交
542 543 544 545 546 547
	finish_current_insert(trans, extent_root);
	pending_ret = del_pending_extents(trans, extent_root);
	if (ret)
		return ret;
	if (pending_ret)
		return pending_ret;
C
Chris Mason 已提交
548 549
	if (cache->data)
		cache->last_alloc = cache->first_free;
C
Chris Mason 已提交
550 551 552 553
	return 0;

}

C
Chris Mason 已提交
554 555 556
static int write_dirty_block_radix(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct radix_tree_root *radix)
C
Chris Mason 已提交
557 558 559 560 561 562 563
{
	struct btrfs_block_group_cache *cache[8];
	int ret;
	int err = 0;
	int werr = 0;
	int i;
	struct btrfs_path *path;
564
	unsigned long off = 0;
C
Chris Mason 已提交
565 566 567 568 569 570 571

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

	while(1) {
		ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
572
						 off, ARRAY_SIZE(cache),
C
Chris Mason 已提交
573 574 575 576 577 578
						 BTRFS_BLOCK_GROUP_DIRTY);
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
			err = write_one_cache_group(trans, root,
						    path, cache[i]);
579 580 581 582 583 584
			/*
			 * 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) {
C
Chris Mason 已提交
585
				werr = err;
586 587 588 589 590 591 592 593
				off = cache[i]->key.objectid +
					cache[i]->key.offset;
				continue;
			}

			radix_tree_tag_clear(radix, cache[i]->key.objectid +
					     cache[i]->key.offset - 1,
					     BTRFS_BLOCK_GROUP_DIRTY);
C
Chris Mason 已提交
594 595 596 597 598 599
		}
	}
	btrfs_free_path(path);
	return werr;
}

C
Chris Mason 已提交
600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615
int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root)
{
	int ret;
	int ret2;
	ret = write_dirty_block_radix(trans, root,
				      &root->fs_info->block_group_radix);
	ret2 = write_dirty_block_radix(trans, root,
				      &root->fs_info->block_group_data_radix);
	if (ret)
		return ret;
	if (ret2)
		return ret2;
	return 0;
}

C
Chris Mason 已提交
616 617
static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
C
Chris Mason 已提交
618 619
			      u64 blocknr, u64 num, int alloc, int mark_free,
			      int data)
C
Chris Mason 已提交
620 621 622 623 624 625
{
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *info = root->fs_info;
	u64 total = num;
	u64 old_val;
	u64 block_in_group;
626
	u64 i;
C
Chris Mason 已提交
627
	int ret;
C
Chris Mason 已提交
628

C
Chris Mason 已提交
629
	while(total) {
630
		cache = btrfs_lookup_block_group(info, blocknr);
C
Chris Mason 已提交
631
		if (!cache) {
C
Chris Mason 已提交
632
			return -1;
C
Chris Mason 已提交
633
		}
C
Chris Mason 已提交
634 635
		block_in_group = blocknr - cache->key.objectid;
		WARN_ON(block_in_group > cache->key.offset);
C
Chris Mason 已提交
636
		radix_tree_tag_set(cache->radix, cache->key.objectid +
C
Chris Mason 已提交
637
				   cache->key.offset - 1,
C
Chris Mason 已提交
638 639 640 641
				   BTRFS_BLOCK_GROUP_DIRTY);

		old_val = btrfs_block_group_used(&cache->item);
		num = min(total, cache->key.offset - block_in_group);
C
Chris Mason 已提交
642 643 644
		if (alloc) {
			if (blocknr > cache->last_alloc)
				cache->last_alloc = blocknr;
645 646 647 648 649 650
			if (!cache->data) {
				for (i = 0; i < num; i++) {
					clear_radix_bit(&info->extent_map_radix,
						        blocknr + i);
				}
			}
C
Chris Mason 已提交
651
			if (cache->data != data &&
C
Chris Mason 已提交
652
			    old_val < (cache->key.offset >> 1)) {
C
Chris Mason 已提交
653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673
				cache->data = data;
				radix_tree_delete(cache->radix,
						  cache->key.objectid +
						  cache->key.offset - 1);

				if (data) {
					cache->radix =
						&info->block_group_data_radix;
					cache->item.flags |=
						BTRFS_BLOCK_GROUP_DATA;
				} else {
					cache->radix = &info->block_group_radix;
					cache->item.flags &=
						~BTRFS_BLOCK_GROUP_DATA;
				}
				ret = radix_tree_insert(cache->radix,
							cache->key.objectid +
							cache->key.offset - 1,
							(void *)cache);
			}
			old_val += num;
C
Chris Mason 已提交
674
		} else {
C
Chris Mason 已提交
675
			old_val -= num;
C
Chris Mason 已提交
676 677
			if (blocknr < cache->first_free)
				cache->first_free = blocknr;
678 679 680 681 682 683
			if (!cache->data && mark_free) {
				for (i = 0; i < num; i++) {
					set_radix_bit(&info->extent_map_radix,
						      blocknr + i);
				}
			}
C
Chris Mason 已提交
684 685
			if (old_val < (cache->key.offset >> 1) &&
			    old_val + num >= (cache->key.offset >> 1)) {
686 687 688 689 690
				radix_tree_tag_set(cache->radix,
						   cache->key.objectid +
						   cache->key.offset - 1,
						   BTRFS_BLOCK_GROUP_AVAIL);
			}
C
Chris Mason 已提交
691
		}
C
Chris Mason 已提交
692
		btrfs_set_block_group_used(&cache->item, old_val);
693 694
		total -= num;
		blocknr += num;
C
Chris Mason 已提交
695 696 697 698
	}
	return 0;
}

C
Chris Mason 已提交
699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716
int btrfs_copy_pinned(struct btrfs_root *root, struct radix_tree_root *copy)
{
	unsigned long gang[8];
	u64 last = 0;
	struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
	int ret;
	int i;

	while(1) {
		ret = find_first_radix_bit(pinned_radix, gang, last,
					   ARRAY_SIZE(gang));
		if (!ret)
			break;
		for (i = 0 ; i < ret; i++) {
			set_radix_bit(copy, gang[i]);
			last = gang[i] + 1;
		}
	}
717 718 719
	ret = find_first_radix_bit(&root->fs_info->extent_ins_radix, gang, 0,
				   ARRAY_SIZE(gang));
	WARN_ON(ret);
C
Chris Mason 已提交
720 721 722 723 724 725
	return 0;
}

int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
			       struct radix_tree_root *unpin_radix)
726
{
C
Chris Mason 已提交
727
	unsigned long gang[8];
C
Chris Mason 已提交
728
	struct btrfs_block_group_cache *block_group;
729
	u64 first = 0;
730 731
	int ret;
	int i;
C
Chris Mason 已提交
732
	struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
733
	struct radix_tree_root *extent_radix = &root->fs_info->extent_map_radix;
734 735

	while(1) {
C
Chris Mason 已提交
736
		ret = find_first_radix_bit(unpin_radix, gang, 0,
C
Chris Mason 已提交
737
					   ARRAY_SIZE(gang));
738 739
		if (!ret)
			break;
740
		if (!first)
C
Chris Mason 已提交
741
			first = gang[0];
742
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
743
			clear_radix_bit(pinned_radix, gang[i]);
C
Chris Mason 已提交
744
			clear_radix_bit(unpin_radix, gang[i]);
745 746
			block_group = btrfs_lookup_block_group(root->fs_info,
							       gang[i]);
C
Chris Mason 已提交
747 748 749 750 751
			if (block_group) {
				WARN_ON(block_group->pinned == 0);
				block_group->pinned--;
				if (gang[i] < block_group->last_alloc)
					block_group->last_alloc = gang[i];
752 753
				if (!block_group->data)
					set_radix_bit(extent_radix, gang[i]);
C
Chris Mason 已提交
754
			}
755
		}
756 757 758 759
	}
	return 0;
}

760 761
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root)
C
Chris Mason 已提交
762
{
C
Chris Mason 已提交
763
	struct btrfs_key ins;
C
Chris Mason 已提交
764
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
765 766
	int i;
	int ret;
767 768
	int err;
	unsigned long gang[8];
769
	struct btrfs_fs_info *info = extent_root->fs_info;
C
Chris Mason 已提交
770

C
Chris Mason 已提交
771
	btrfs_set_extent_refs(&extent_item, 1);
C
Chris Mason 已提交
772 773
	ins.offset = 1;
	ins.flags = 0;
774
	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
775
	btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid);
C
Chris Mason 已提交
776

777 778 779 780 781 782 783 784 785 786 787 788 789 790
	while(1) {
		ret = find_first_radix_bit(&info->extent_ins_radix, gang, 0,
					   ARRAY_SIZE(gang));
		if (!ret)
			break;

		for (i = 0; i < ret; i++) {
			ins.objectid = gang[i];
			err = btrfs_insert_item(trans, extent_root, &ins,
						&extent_item,
						sizeof(extent_item));
			clear_radix_bit(&info->extent_ins_radix, gang[i]);
			WARN_ON(err);
		}
C
Chris Mason 已提交
791 792 793 794
	}
	return 0;
}

C
Chris Mason 已提交
795
static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
C
Chris Mason 已提交
796 797
{
	int err;
C
Chris Mason 已提交
798
	struct btrfs_header *header;
C
Chris Mason 已提交
799 800
	struct buffer_head *bh;

C
Chris Mason 已提交
801
	if (!pending) {
802
		bh = btrfs_find_tree_block(root, blocknr);
C
Chris Mason 已提交
803 804 805 806 807 808 809 810 811 812
		if (bh) {
			if (buffer_uptodate(bh)) {
				u64 transid =
				    root->fs_info->running_transaction->transid;
				header = btrfs_buffer_header(bh);
				if (btrfs_header_generation(header) ==
				    transid) {
					btrfs_block_release(root, bh);
					return 0;
				}
C
Chris Mason 已提交
813
			}
C
Chris Mason 已提交
814
			btrfs_block_release(root, bh);
C
Chris Mason 已提交
815 816
		}
		err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
C
Chris Mason 已提交
817 818
		if (!err) {
			struct btrfs_block_group_cache *cache;
819 820
			cache = btrfs_lookup_block_group(root->fs_info,
							 blocknr);
C
Chris Mason 已提交
821 822 823
			if (cache)
				cache->pinned++;
		}
C
Chris Mason 已提交
824 825 826
	} else {
		err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
	}
C
Chris Mason 已提交
827
	BUG_ON(err < 0);
C
Chris Mason 已提交
828 829 830
	return 0;
}

831
/*
832
 * remove an extent from the root, returns 0 on success
833
 */
834
static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
835 836
			 *root, u64 blocknr, u64 num_blocks, int pin,
			 int mark_free)
837
{
838
	struct btrfs_path *path;
C
Chris Mason 已提交
839
	struct btrfs_key key;
840 841
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
842
	int ret;
C
Chris Mason 已提交
843
	struct btrfs_extent_item *ei;
C
Chris Mason 已提交
844
	u32 refs;
C
Chris Mason 已提交
845

846 847
	key.objectid = blocknr;
	key.flags = 0;
848
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
849 850
	key.offset = num_blocks;

851
	path = btrfs_alloc_path();
852 853
	if (!path)
		return -ENOMEM;
854

855 856 857 858
	ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
	if (ret < 0)
		return ret;
	BUG_ON(ret);
859
	ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
C
Chris Mason 已提交
860
			    struct btrfs_extent_item);
861
	BUG_ON(ei->refs == 0);
C
Chris Mason 已提交
862 863
	refs = btrfs_extent_refs(ei) - 1;
	btrfs_set_extent_refs(ei, refs);
864
	btrfs_mark_buffer_dirty(path->nodes[0]);
C
Chris Mason 已提交
865
	if (refs == 0) {
866
		u64 super_blocks_used, root_blocks_used;
C
Chris Mason 已提交
867 868

		if (pin) {
C
Chris Mason 已提交
869
			ret = pin_down_block(root, blocknr, 0);
C
Chris Mason 已提交
870 871 872
			BUG_ON(ret);
		}

873
		/* block accounting for super block */
874 875
		super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
		btrfs_set_super_blocks_used(&info->super_copy,
876
					    super_blocks_used - num_blocks);
877 878 879 880 881 882

		/* block accounting for root item */
		root_blocks_used = btrfs_root_blocks_used(&root->root_item);
		btrfs_set_root_blocks_used(&root->root_item,
					   root_blocks_used - num_blocks);

883
		ret = btrfs_del_item(trans, extent_root, path);
884 885 886
		if (ret) {
			return ret;
		}
887
		ret = update_block_group(trans, root, blocknr, num_blocks, 0,
C
Chris Mason 已提交
888
					 mark_free, 0);
C
Chris Mason 已提交
889
		BUG_ON(ret);
890
	}
891
	btrfs_free_path(path);
892
	finish_current_insert(trans, extent_root);
893 894 895 896 897 898 899
	return ret;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
900 901
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root)
902 903
{
	int ret;
C
Chris Mason 已提交
904 905
	int wret;
	int err = 0;
C
Chris Mason 已提交
906
	unsigned long gang[4];
907
	int i;
C
Chris Mason 已提交
908 909
	struct radix_tree_root *pending_radix;
	struct radix_tree_root *pinned_radix;
C
Chris Mason 已提交
910
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
911 912 913

	pending_radix = &extent_root->fs_info->pending_del_radix;
	pinned_radix = &extent_root->fs_info->pinned_radix;
914 915

	while(1) {
916
		ret = find_first_radix_bit(pending_radix, gang, 0,
C
Chris Mason 已提交
917
					   ARRAY_SIZE(gang));
918 919 920
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
921
			wret = set_radix_bit(pinned_radix, gang[i]);
C
Chris Mason 已提交
922
			if (wret == 0) {
923 924
				cache =
				  btrfs_lookup_block_group(extent_root->fs_info,
C
Chris Mason 已提交
925 926 927 928 929 930 931 932 933
							   gang[i]);
				if (cache)
					cache->pinned++;
			}
			if (wret < 0) {
				printk(KERN_CRIT "set_radix_bit, err %d\n",
				       wret);
				BUG_ON(wret < 0);
			}
C
Chris Mason 已提交
934 935
			wret = clear_radix_bit(pending_radix, gang[i]);
			BUG_ON(wret);
936
			wret = __free_extent(trans, extent_root,
937
					     gang[i], 1, 0, 0);
C
Chris Mason 已提交
938 939
			if (wret)
				err = wret;
940 941
		}
	}
C
Chris Mason 已提交
942
	return err;
943 944 945 946 947
}

/*
 * remove an extent from the root, returns 0 on success
 */
948 949
int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, u64 blocknr, u64 num_blocks, int pin)
950
{
951
	struct btrfs_root *extent_root = root->fs_info->extent_root;
952 953
	int pending_ret;
	int ret;
954

955
	if (root == extent_root) {
C
Chris Mason 已提交
956
		pin_down_block(root, blocknr, 1);
957 958
		return 0;
	}
959
	ret = __free_extent(trans, root, blocknr, num_blocks, pin, pin == 0);
C
Chris Mason 已提交
960
	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
961 962 963 964 965 966 967
	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
968
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
969 970 971
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
972
static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
973 974
			    *orig_root, u64 num_blocks, u64 empty_size,
			    u64 search_start, u64 search_end, u64 hint_block,
975 976
			    struct btrfs_key *ins, u64 exclude_start,
			    u64 exclude_nr, int data)
977
{
978
	struct btrfs_path *path;
C
Chris Mason 已提交
979
	struct btrfs_key key;
980 981 982
	int ret;
	u64 hole_size = 0;
	int slot = 0;
C
Chris Mason 已提交
983
	u64 last_block = 0;
C
Chris Mason 已提交
984
	u64 test_block;
C
Chris Mason 已提交
985
	u64 orig_search_start = search_start;
986
	int start_found;
C
Chris Mason 已提交
987
	struct btrfs_leaf *l;
988
	struct btrfs_root * root = orig_root->fs_info->extent_root;
989
	struct btrfs_fs_info *info = root->fs_info;
990
	int total_needed = num_blocks;
C
Chris Mason 已提交
991
	int level;
C
Chris Mason 已提交
992
	struct btrfs_block_group_cache *block_group;
C
Chris Mason 已提交
993
	int full_scan = 0;
994
	int wrapped = 0;
995

996
	WARN_ON(num_blocks < 1);
997 998 999
	ins->flags = 0;
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);

C
Chris Mason 已提交
1000
	level = btrfs_header_level(btrfs_buffer_header(root->node));
C
Chris Mason 已提交
1001
	if (search_end == (u64)-1)
1002
		search_end = btrfs_super_total_blocks(&info->super_copy);
1003
	if (hint_block) {
1004
		block_group = btrfs_lookup_block_group(info, hint_block);
C
Chris Mason 已提交
1005
		block_group = btrfs_find_block_group(root, block_group,
1006
						     hint_block, data, 1);
C
Chris Mason 已提交
1007 1008 1009
	} else {
		block_group = btrfs_find_block_group(root,
						     trans->block_group, 0,
1010
						     data, 1);
C
Chris Mason 已提交
1011 1012
	}

1013
	total_needed += empty_size;
1014 1015
	path = btrfs_alloc_path();

C
Chris Mason 已提交
1016
check_failed:
C
Chris Mason 已提交
1017
	if (!block_group->data)
1018 1019
		search_start = find_search_start(root, &block_group,
						 search_start, total_needed);
1020
	else if (!full_scan)
1021 1022
		search_start = max(block_group->last_alloc, search_start);

1023
	btrfs_init_path(path);
1024 1025 1026
	ins->objectid = search_start;
	ins->offset = 0;
	start_found = 0;
1027
	path->reada = 2;
1028

1029
	ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
C
Chris Mason 已提交
1030 1031
	if (ret < 0)
		goto error;
C
Chris Mason 已提交
1032

1033
	if (path->slots[0] > 0) {
1034
		path->slots[0]--;
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055
	}

	l = btrfs_buffer_leaf(path->nodes[0]);
	btrfs_disk_key_to_cpu(&key, &l->items[path->slots[0]].key);
	/*
	 * 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]--;
		}
	}
1056

1057
	while (1) {
1058 1059
		l = btrfs_buffer_leaf(path->nodes[0]);
		slot = path->slots[0];
1060
		if (slot >= btrfs_header_nritems(&l->header)) {
1061
			ret = btrfs_next_leaf(root, path);
1062 1063
			if (ret == 0)
				continue;
C
Chris Mason 已提交
1064 1065
			if (ret < 0)
				goto error;
1066 1067
			if (!start_found) {
				ins->objectid = search_start;
C
Chris Mason 已提交
1068
				ins->offset = search_end - search_start;
1069 1070 1071 1072 1073
				start_found = 1;
				goto check_pending;
			}
			ins->objectid = last_block > search_start ?
					last_block : search_start;
C
Chris Mason 已提交
1074
			ins->offset = search_end - ins->objectid;
1075 1076
			goto check_pending;
		}
1077

C
Chris Mason 已提交
1078
		btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
1079 1080 1081 1082 1083 1084 1085 1086 1087
		if (key.objectid >= search_start && key.objectid > last_block &&
		    start_found) {
			if (last_block < search_start)
				last_block = search_start;
			hole_size = key.objectid - last_block;
			if (hole_size >= num_blocks) {
				ins->objectid = last_block;
				ins->offset = hole_size;
				goto check_pending;
1088
			}
1089
		}
1090 1091 1092 1093

		if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
			goto next;

1094
		start_found = 1;
C
Chris Mason 已提交
1095
		last_block = key.objectid + key.offset;
1096
		if (!full_scan && last_block >= block_group->key.objectid +
C
Chris Mason 已提交
1097 1098 1099 1100 1101 1102
		    block_group->key.offset) {
			btrfs_release_path(root, path);
			search_start = block_group->key.objectid +
				block_group->key.offset * 2;
			goto new_group;
		}
C
Chris Mason 已提交
1103
next:
1104
		path->slots[0]++;
1105
		cond_resched();
1106 1107 1108 1109 1110
	}
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
	 */
1111
	btrfs_release_path(root, path);
1112
	BUG_ON(ins->objectid < search_start);
1113

C
Chris Mason 已提交
1114
	if (ins->objectid + num_blocks >= search_end) {
1115 1116 1117 1118
		if (full_scan) {
			ret = -ENOSPC;
			goto error;
		}
C
Chris Mason 已提交
1119
		search_start = orig_search_start;
1120 1121 1122
		if (wrapped) {
			if (!full_scan)
				total_needed -= empty_size;
1123
			full_scan = 1;
1124
		} else
1125
			wrapped = 1;
C
Chris Mason 已提交
1126
		goto new_group;
1127
	}
C
Chris Mason 已提交
1128
	for (test_block = ins->objectid;
1129
	     test_block < ins->objectid + num_blocks; test_block++) {
1130 1131
		if (test_radix_bit(&info->pinned_radix, test_block) ||
		    test_radix_bit(&info->extent_ins_radix, test_block)) {
C
Chris Mason 已提交
1132
			search_start = test_block + 1;
C
Chris Mason 已提交
1133
			goto new_group;
1134 1135
		}
	}
1136 1137 1138 1139 1140
	if (exclude_nr > 0 && (ins->objectid + num_blocks > exclude_start &&
	    ins->objectid < exclude_start + exclude_nr)) {
		search_start = exclude_start + exclude_nr;
		goto new_group;
	}
1141
	if (!data) {
1142
		block_group = btrfs_lookup_block_group(info, ins->objectid);
1143 1144
		if (block_group)
			trans->block_group = block_group;
1145
	}
C
Chris Mason 已提交
1146
	ins->offset = num_blocks;
1147
	btrfs_free_path(path);
1148
	return 0;
C
Chris Mason 已提交
1149 1150

new_group:
C
Chris Mason 已提交
1151
	if (search_start + num_blocks >= search_end) {
C
Chris Mason 已提交
1152
		search_start = orig_search_start;
1153 1154 1155 1156
		if (full_scan) {
			ret = -ENOSPC;
			goto error;
		}
1157 1158 1159
		if (wrapped) {
			if (!full_scan)
				total_needed -= empty_size;
1160
			full_scan = 1;
1161
		} else
1162
			wrapped = 1;
C
Chris Mason 已提交
1163
	}
1164
	block_group = btrfs_lookup_block_group(info, search_start);
1165
	cond_resched();
C
Chris Mason 已提交
1166 1167
	if (!full_scan)
		block_group = btrfs_find_block_group(root, block_group,
1168
						     search_start, data, 0);
C
Chris Mason 已提交
1169 1170
	goto check_failed;

C
Chris Mason 已提交
1171
error:
1172 1173
	btrfs_release_path(root, path);
	btrfs_free_path(path);
C
Chris Mason 已提交
1174
	return ret;
1175 1176 1177 1178 1179 1180 1181 1182
}
/*
 * 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.
 */
1183 1184
int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root, u64 owner,
1185
		       u64 num_blocks, u64 empty_size, u64 hint_block,
C
Chris Mason 已提交
1186
		       u64 search_end, struct btrfs_key *ins, int data)
1187 1188 1189
{
	int ret;
	int pending_ret;
1190
	u64 super_blocks_used, root_blocks_used;
1191
	u64 search_start = 0;
1192 1193
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
C
Chris Mason 已提交
1194
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
1195

C
Chris Mason 已提交
1196
	btrfs_set_extent_refs(&extent_item, 1);
1197
	btrfs_set_extent_owner(&extent_item, owner);
1198

1199
	WARN_ON(num_blocks < 1);
1200 1201
	ret = find_free_extent(trans, root, num_blocks, empty_size,
			       search_start, search_end, hint_block, ins,
1202 1203
			       trans->alloc_exclude_start,
			       trans->alloc_exclude_nr, data);
C
Chris Mason 已提交
1204
	BUG_ON(ret);
1205 1206
	if (ret)
		return ret;
1207

1208
	/* block accounting for super block */
1209 1210
	super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
	btrfs_set_super_blocks_used(&info->super_copy, super_blocks_used +
1211
				    num_blocks);
1212

1213 1214 1215 1216 1217
	/* block accounting for root item */
	root_blocks_used = btrfs_root_blocks_used(&root->root_item);
	btrfs_set_root_blocks_used(&root->root_item, root_blocks_used +
				   num_blocks);

1218 1219 1220 1221 1222 1223 1224 1225 1226
	if (root == extent_root) {
		BUG_ON(num_blocks != 1);
		set_radix_bit(&root->fs_info->extent_ins_radix, ins->objectid);
		goto update_block;
	}

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

1230 1231 1232
	trans->alloc_exclude_start = 0;
	trans->alloc_exclude_nr = 0;

C
Chris Mason 已提交
1233
	BUG_ON(ret);
1234
	finish_current_insert(trans, extent_root);
C
Chris Mason 已提交
1235
	pending_ret = del_pending_extents(trans, extent_root);
1236
	if (ret) {
C
Chris Mason 已提交
1237
		return ret;
1238 1239
	}
	if (pending_ret) {
C
Chris Mason 已提交
1240
		return pending_ret;
1241
	}
1242 1243

update_block:
C
Chris Mason 已提交
1244 1245
	ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
				 data);
C
Chris Mason 已提交
1246
	BUG_ON(ret);
C
Chris Mason 已提交
1247
	return 0;
1248 1249 1250 1251 1252 1253
}

/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
C
Chris Mason 已提交
1254
struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1255 1256
					   struct btrfs_root *root, u64 hint,
					   u64 empty_size)
1257
{
C
Chris Mason 已提交
1258
	struct btrfs_key ins;
1259
	int ret;
C
Chris Mason 已提交
1260
	struct buffer_head *buf;
1261

1262
	ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1263
				 1, empty_size, hint, (u64)-1, &ins, 0);
1264
	if (ret) {
1265 1266
		BUG_ON(ret > 0);
		return ERR_PTR(ret);
1267
	}
1268
	buf = btrfs_find_create_tree_block(root, ins.objectid);
1269 1270 1271 1272
	if (!buf) {
		btrfs_free_extent(trans, root, ins.objectid, 1, 0);
		return ERR_PTR(-ENOMEM);
	}
1273
	WARN_ON(buffer_dirty(buf));
1274
	set_buffer_uptodate(buf);
C
Chris Mason 已提交
1275
	set_buffer_checked(buf);
1276
	set_buffer_defrag(buf);
1277
	set_radix_bit(&trans->transaction->dirty_pages, buf->b_page->index);
1278 1279
	return buf;
}
1280

1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294
static int drop_leaf_ref(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root, struct buffer_head *cur)
{
	struct btrfs_disk_key *key;
	struct btrfs_leaf *leaf;
	struct btrfs_file_extent_item *fi;
	int i;
	int nritems;
	int ret;

	BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
	leaf = btrfs_buffer_leaf(cur);
	nritems = btrfs_header_nritems(&leaf->header);
	for (i = 0; i < nritems; i++) {
C
Chris Mason 已提交
1295
		u64 disk_blocknr;
1296 1297 1298 1299
		key = &leaf->items[i].key;
		if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1300 1301
		if (btrfs_file_extent_type(fi) == BTRFS_FILE_EXTENT_INLINE)
			continue;
1302 1303 1304 1305
		/*
		 * FIXME make sure to insert a trans record that
		 * repeats the snapshot del on crash
		 */
C
Chris Mason 已提交
1306 1307 1308 1309
		disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
		if (disk_blocknr == 0)
			continue;
		ret = btrfs_free_extent(trans, root, disk_blocknr,
1310 1311 1312 1313 1314 1315 1316
					btrfs_file_extent_disk_num_blocks(fi),
					0);
		BUG_ON(ret);
	}
	return 0;
}

1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332
static void reada_walk_down(struct btrfs_root *root,
			    struct btrfs_node *node)
{
	int i;
	u32 nritems;
	u64 blocknr;
	int ret;
	u32 refs;

	nritems = btrfs_header_nritems(&node->header);
	for (i = 0; i < nritems; i++) {
		blocknr = btrfs_node_blockptr(node, i);
		ret = lookup_extent_ref(NULL, root, blocknr, 1, &refs);
		BUG_ON(ret);
		if (refs != 1)
			continue;
1333
		mutex_unlock(&root->fs_info->fs_mutex);
1334
		ret = readahead_tree_block(root, blocknr);
1335 1336
		cond_resched();
		mutex_lock(&root->fs_info->fs_mutex);
1337 1338 1339 1340 1341
		if (ret)
			break;
	}
}

C
Chris Mason 已提交
1342 1343 1344 1345
/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
1346 1347
static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
			  *root, struct btrfs_path *path, int *level)
C
Chris Mason 已提交
1348
{
C
Chris Mason 已提交
1349 1350
	struct buffer_head *next;
	struct buffer_head *cur;
C
Chris Mason 已提交
1351 1352 1353 1354
	u64 blocknr;
	int ret;
	u32 refs;

1355 1356
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
1357
	ret = lookup_extent_ref(trans, root, bh_blocknr(path->nodes[*level]),
1358
			       1, &refs);
C
Chris Mason 已提交
1359 1360 1361
	BUG_ON(ret);
	if (refs > 1)
		goto out;
1362

C
Chris Mason 已提交
1363 1364 1365
	/*
	 * walk down to the last node level and free all the leaves
	 */
1366
	while(*level >= 0) {
1367 1368
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
1369
		cur = path->nodes[*level];
1370 1371 1372 1373

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

C
Chris Mason 已提交
1374 1375
		if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
			WARN_ON(1);
1376

1377
		if (path->slots[*level] >=
C
Chris Mason 已提交
1378
		    btrfs_header_nritems(btrfs_buffer_header(cur)))
C
Chris Mason 已提交
1379
			break;
1380 1381 1382 1383 1384
		if (*level == 0) {
			ret = drop_leaf_ref(trans, root, cur);
			BUG_ON(ret);
			break;
		}
C
Chris Mason 已提交
1385 1386
		blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
					      path->slots[*level]);
C
Chris Mason 已提交
1387
		ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1388 1389
		BUG_ON(ret);
		if (refs != 1) {
C
Chris Mason 已提交
1390
			path->slots[*level]++;
1391
			ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
C
Chris Mason 已提交
1392 1393 1394
			BUG_ON(ret);
			continue;
		}
1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413
		next = btrfs_find_tree_block(root, blocknr);
		if (!next || !buffer_uptodate(next)) {
			brelse(next);
			mutex_unlock(&root->fs_info->fs_mutex);
			next = read_tree_block(root, blocknr);
			mutex_lock(&root->fs_info->fs_mutex);

			/* we dropped the lock, check one more time */
			ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
			BUG_ON(ret);
			if (refs != 1) {
				path->slots[*level]++;
				brelse(next);
				ret = btrfs_free_extent(trans, root,
							blocknr, 1, 1);
				BUG_ON(ret);
				continue;
			}
		}
1414
		WARN_ON(*level <= 0);
C
Chris Mason 已提交
1415
		if (path->nodes[*level-1])
C
Chris Mason 已提交
1416
			btrfs_block_release(root, path->nodes[*level-1]);
C
Chris Mason 已提交
1417
		path->nodes[*level-1] = next;
C
Chris Mason 已提交
1418
		*level = btrfs_header_level(btrfs_buffer_header(next));
C
Chris Mason 已提交
1419 1420 1421
		path->slots[*level] = 0;
	}
out:
1422 1423
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
1424
	ret = btrfs_free_extent(trans, root,
1425
				bh_blocknr(path->nodes[*level]), 1, 1);
C
Chris Mason 已提交
1426
	btrfs_block_release(root, path->nodes[*level]);
C
Chris Mason 已提交
1427 1428 1429 1430 1431 1432
	path->nodes[*level] = NULL;
	*level += 1;
	BUG_ON(ret);
	return 0;
}

C
Chris Mason 已提交
1433 1434 1435 1436 1437
/*
 * 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
 */
1438 1439
static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
			*root, struct btrfs_path *path, int *level)
C
Chris Mason 已提交
1440 1441 1442 1443
{
	int i;
	int slot;
	int ret;
1444 1445
	struct btrfs_root_item *root_item = &root->root_item;

C
Chris Mason 已提交
1446
	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
C
Chris Mason 已提交
1447
		slot = path->slots[i];
C
Chris Mason 已提交
1448 1449
		if (slot < btrfs_header_nritems(
		    btrfs_buffer_header(path->nodes[i])) - 1) {
1450 1451
			struct btrfs_node *node;
			node = btrfs_buffer_node(path->nodes[i]);
C
Chris Mason 已提交
1452 1453
			path->slots[i]++;
			*level = i;
1454 1455 1456 1457 1458
			WARN_ON(*level == 0);
			memcpy(&root_item->drop_progress,
			       &node->ptrs[path->slots[i]].key,
			       sizeof(root_item->drop_progress));
			root_item->drop_level = i;
C
Chris Mason 已提交
1459 1460
			return 0;
		} else {
1461
			ret = btrfs_free_extent(trans, root,
1462
						bh_blocknr(path->nodes[*level]),
1463
						1, 1);
1464
			BUG_ON(ret);
C
Chris Mason 已提交
1465
			btrfs_block_release(root, path->nodes[*level]);
C
Chris Mason 已提交
1466
			path->nodes[*level] = NULL;
C
Chris Mason 已提交
1467 1468 1469 1470 1471 1472
			*level = i + 1;
		}
	}
	return 1;
}

C
Chris Mason 已提交
1473 1474 1475 1476 1477
/*
 * 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.
 */
1478
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
1479
			*root)
C
Chris Mason 已提交
1480
{
1481
	int ret = 0;
C
Chris Mason 已提交
1482
	int wret;
C
Chris Mason 已提交
1483
	int level;
1484
	struct btrfs_path *path;
C
Chris Mason 已提交
1485 1486
	int i;
	int orig_level;
1487
	struct btrfs_root_item *root_item = &root->root_item;
C
Chris Mason 已提交
1488

1489 1490
	path = btrfs_alloc_path();
	BUG_ON(!path);
C
Chris Mason 已提交
1491

1492
	level = btrfs_header_level(btrfs_buffer_header(root->node));
C
Chris Mason 已提交
1493
	orig_level = level;
1494 1495 1496 1497 1498 1499 1500
	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
		path->nodes[level] = root->node;
		path->slots[level] = 0;
	} else {
		struct btrfs_key key;
		struct btrfs_disk_key *found_key;
		struct btrfs_node *node;
1501

1502
		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1503 1504
		level = root_item->drop_level;
		path->lowest_level = level;
1505
		wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1506
		if (wret < 0) {
1507 1508 1509 1510 1511 1512 1513 1514
			ret = wret;
			goto out;
		}
		node = btrfs_buffer_node(path->nodes[level]);
		found_key = &node->ptrs[path->slots[level]].key;
		WARN_ON(memcmp(found_key, &root_item->drop_progress,
			       sizeof(*found_key)));
	}
C
Chris Mason 已提交
1515
	while(1) {
1516
		wret = walk_down_tree(trans, root, path, &level);
C
Chris Mason 已提交
1517
		if (wret > 0)
C
Chris Mason 已提交
1518
			break;
C
Chris Mason 已提交
1519 1520 1521
		if (wret < 0)
			ret = wret;

1522
		wret = walk_up_tree(trans, root, path, &level);
C
Chris Mason 已提交
1523
		if (wret > 0)
C
Chris Mason 已提交
1524
			break;
C
Chris Mason 已提交
1525 1526
		if (wret < 0)
			ret = wret;
1527 1528 1529
		ret = -EAGAIN;
		get_bh(root->node);
		break;
C
Chris Mason 已提交
1530
	}
C
Chris Mason 已提交
1531
	for (i = 0; i <= orig_level; i++) {
1532 1533
		if (path->nodes[i]) {
			btrfs_block_release(root, path->nodes[i]);
1534
			path->nodes[i] = 0;
C
Chris Mason 已提交
1535
		}
C
Chris Mason 已提交
1536
	}
1537
out:
1538
	btrfs_free_path(path);
C
Chris Mason 已提交
1539
	return ret;
C
Chris Mason 已提交
1540
}
C
Chris Mason 已提交
1541

C
Chris Mason 已提交
1542
static int free_block_group_radix(struct radix_tree_root *radix)
C
Chris Mason 已提交
1543 1544 1545 1546 1547 1548
{
	int ret;
	struct btrfs_block_group_cache *cache[8];
	int i;

	while(1) {
C
Chris Mason 已提交
1549
		ret = radix_tree_gang_lookup(radix, (void **)cache, 0,
C
Chris Mason 已提交
1550 1551 1552 1553
					     ARRAY_SIZE(cache));
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
1554
			radix_tree_delete(radix, cache[i]->key.objectid +
C
Chris Mason 已提交
1555 1556 1557 1558 1559 1560 1561
					  cache[i]->key.offset - 1);
			kfree(cache[i]);
		}
	}
	return 0;
}

C
Chris Mason 已提交
1562 1563 1564 1565
int btrfs_free_block_groups(struct btrfs_fs_info *info)
{
	int ret;
	int ret2;
1566 1567
	unsigned long gang[16];
	int i;
C
Chris Mason 已提交
1568 1569 1570 1571 1572 1573 1574

	ret = free_block_group_radix(&info->block_group_radix);
	ret2 = free_block_group_radix(&info->block_group_data_radix);
	if (ret)
		return ret;
	if (ret2)
		return ret2;
1575 1576 1577 1578 1579 1580 1581 1582 1583 1584

	while(1) {
		ret = find_first_radix_bit(&info->extent_map_radix,
					   gang, 0, ARRAY_SIZE(gang));
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
			clear_radix_bit(&info->extent_map_radix, gang[i]);
		}
	}
C
Chris Mason 已提交
1585 1586 1587
	return 0;
}

C
Chris Mason 已提交
1588 1589 1590 1591 1592 1593 1594
int btrfs_read_block_groups(struct btrfs_root *root)
{
	struct btrfs_path *path;
	int ret;
	int err = 0;
	struct btrfs_block_group_item *bi;
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
1595 1596
	struct btrfs_fs_info *info = root->fs_info;
	struct radix_tree_root *radix;
C
Chris Mason 已提交
1597 1598 1599
	struct btrfs_key key;
	struct btrfs_key found_key;
	struct btrfs_leaf *leaf;
C
Chris Mason 已提交
1600
	u64 group_size_blocks;
1601
	u64 used;
C
Chris Mason 已提交
1602

C
Chris Mason 已提交
1603 1604
	group_size_blocks = BTRFS_BLOCK_GROUP_SIZE >>
		root->fs_info->sb->s_blocksize_bits;
C
Chris Mason 已提交
1605
	root = info->extent_root;
C
Chris Mason 已提交
1606 1607 1608 1609 1610 1611 1612 1613 1614 1615
	key.objectid = 0;
	key.offset = group_size_blocks;
	key.flags = 0;
	btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);

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

	while(1) {
C
Chris Mason 已提交
1616
		ret = btrfs_search_slot(NULL, info->extent_root,
C
Chris Mason 已提交
1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629
					&key, path, 0, 0);
		if (ret != 0) {
			err = ret;
			break;
		}
		leaf = btrfs_buffer_leaf(path->nodes[0]);
		btrfs_disk_key_to_cpu(&found_key,
				      &leaf->items[path->slots[0]].key);
		cache = kmalloc(sizeof(*cache), GFP_NOFS);
		if (!cache) {
			err = -1;
			break;
		}
C
Chris Mason 已提交
1630

C
Chris Mason 已提交
1631 1632 1633
		bi = btrfs_item_ptr(leaf, path->slots[0],
				    struct btrfs_block_group_item);
		if (bi->flags & BTRFS_BLOCK_GROUP_DATA) {
C
Chris Mason 已提交
1634
			radix = &info->block_group_data_radix;
C
Chris Mason 已提交
1635 1636
			cache->data = 1;
		} else {
C
Chris Mason 已提交
1637
			radix = &info->block_group_radix;
C
Chris Mason 已提交
1638 1639
			cache->data = 0;
		}
C
Chris Mason 已提交
1640

C
Chris Mason 已提交
1641 1642
		memcpy(&cache->item, bi, sizeof(*bi));
		memcpy(&cache->key, &found_key, sizeof(found_key));
1643 1644
		cache->last_alloc = cache->key.objectid;
		cache->first_free = cache->key.objectid;
C
Chris Mason 已提交
1645
		cache->pinned = 0;
1646 1647
		cache->cached = 0;

C
Chris Mason 已提交
1648 1649
		cache->radix = radix;

C
Chris Mason 已提交
1650 1651
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
C
Chris Mason 已提交
1652
		ret = radix_tree_insert(radix, found_key.objectid +
C
Chris Mason 已提交
1653 1654 1655
					found_key.offset - 1,
					(void *)cache);
		BUG_ON(ret);
1656
		used = btrfs_block_group_used(bi);
C
Chris Mason 已提交
1657
		if (used < div_factor(key.offset, 8)) {
C
Chris Mason 已提交
1658
			radix_tree_tag_set(radix, found_key.objectid +
1659 1660 1661
					   found_key.offset - 1,
					   BTRFS_BLOCK_GROUP_AVAIL);
		}
C
Chris Mason 已提交
1662
		if (key.objectid >=
1663
		    btrfs_super_total_blocks(&info->super_copy))
C
Chris Mason 已提交
1664 1665 1666 1667 1668 1669
			break;
	}

	btrfs_free_path(path);
	return 0;
}