extent-tree.c 38.3 KB
Newer Older
1
#include <linux/module.h>
2 3 4
#include "ctree.h"
#include "disk-io.h"
#include "print-tree.h"
5
#include "transaction.h"
6

7 8
static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
			    *orig_root, u64 num_blocks, u64 search_start, u64
C
Chris Mason 已提交
9
			    search_end, struct btrfs_key *ins, int data);
10 11
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root);
C
Chris Mason 已提交
12 13
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root);
14

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
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;
	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;
printk("cache block group %Lu\n", block_group->key.objectid);
	key.objectid = block_group->key.objectid;
	key.flags = 0;
	key.offset = 0;
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		return ret;
	if (ret && path->slots[0] > 0)
		path->slots[0]--;
	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);
			if (ret == 0)
				continue;
			else {
				if (found) {
					hole_size = block_group->key.objectid +
						block_group->key.offset - last;
				} else {
					last = block_group->key.objectid;
					hole_size = block_group->key.offset;
				}
				for (i = 0; i < hole_size; i++) {
					set_radix_bit(extent_radix,
						      last + i);
				}
				break;
			}
		}
		btrfs_disk_key_to_cpu(&key, &leaf->items[slot].key);
		if (key.objectid >= block_group->key.objectid +
		    block_group->key.offset) {
			if (found) {
				hole_size = block_group->key.objectid +
					block_group->key.offset - last;
			} else {
				last = block_group->key.objectid;
				hole_size = block_group->key.offset;
			}
			for (i = 0; i < hole_size; i++) {
				set_radix_bit(extent_radix, last + i);
			}
			break;
		}
		if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
			if (!found) {
				last = key.objectid + key.offset;
				found = 1;
			} else {
				hole_size = key.objectid - last;
				for (i = 0; i < hole_size; i++) {
					set_radix_bit(extent_radix, last + i);
				}
				last = key.objectid + key.offset;
			}
		}
		path->slots[0]++;
	}

	block_group->cached = 1;
	btrfs_free_path(path);
	return 0;
}

C
Chris Mason 已提交
106 107 108 109 110 111 112 113 114 115 116
static struct btrfs_block_group_cache *lookup_block_group(struct
							  btrfs_fs_info *info,
							  u64 blocknr)
{
	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 已提交
117
		if (block_group->key.objectid <= blocknr && blocknr <=
C
Chris Mason 已提交
118 119 120 121 122 123 124
		    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 已提交
125
		if (block_group->key.objectid <= blocknr && blocknr <=
C
Chris Mason 已提交
126 127 128
		    block_group->key.objectid + block_group->key.offset)
			return block_group;
	}
C
Chris Mason 已提交
129 130 131 132 133 134
	WARN_ON(1);
	printk("lookup_block_group fails for blocknr %Lu\n", blocknr);
	printk("last ret was %d\n", ret);
	if (ret) {
		printk("last block group was %Lu %Lu\n", block_group->key.objectid, block_group->key.offset);
	}
C
Chris Mason 已提交
135 136 137
	return NULL;
}

138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
static u64 leaf_range(struct btrfs_root *root)
{
	u64 size = BTRFS_LEAF_DATA_SIZE(root);
	size = size / (sizeof(struct btrfs_extent_item) +
		       sizeof(struct btrfs_item));
	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;
	if (num > 1) {
		last = max(last, cache->last_prealloc);
	}
again:
	cache_block_group(root, cache);
	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:
	cache = lookup_block_group(root->fs_info, last + cache->key.offset - 1);
	if (!cache) {
		return max((*cache_ret)->last_alloc, search_start);
	}
	cache = btrfs_find_block_group(root, cache,
				       last + cache->key.offset - 1, 0);
	*cache_ret = cache;
	goto again;
}

195 196
struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
						 struct btrfs_block_group_cache
C
Chris Mason 已提交
197 198
						 *hint, u64 search_start,
						 int data)
C
Chris Mason 已提交
199 200
{
	struct btrfs_block_group_cache *cache[8];
201
	struct btrfs_block_group_cache *found_group = NULL;
C
Chris Mason 已提交
202
	struct btrfs_fs_info *info = root->fs_info;
C
Chris Mason 已提交
203
	struct radix_tree_root *radix;
C
Chris Mason 已提交
204
	u64 used;
205 206
	u64 last = 0;
	u64 hint_last;
C
Chris Mason 已提交
207 208
	int i;
	int ret;
209
	int full_search = 0;
C
Chris Mason 已提交
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227

	if (data)
		radix = &info->block_group_data_radix;
	else
		radix = &info->block_group_radix;

	if (search_start) {
		struct btrfs_block_group_cache *shint;
		shint = lookup_block_group(info, search_start);
		if (shint->data == data) {
			used = btrfs_block_group_used(&shint->item);
			if (used + shint->pinned <
			    (shint->key.offset * 8) / 10) {
				return shint;
			}
		}
	}
	if (hint && hint->data == data) {
228
		used = btrfs_block_group_used(&hint->item);
C
Chris Mason 已提交
229
		if (used + hint->pinned < (hint->key.offset * 8) / 10) {
230 231
			return hint;
		}
C
Chris Mason 已提交
232 233 234 235 236 237 238 239
		if (used >= (hint->key.offset * 8) / 10) {
			radix_tree_tag_clear(radix,
					     hint->key.objectid +
					     hint->key.offset - 1,
					     BTRFS_BLOCK_GROUP_AVAIL);
		}
		last = hint->key.offset * 2;
		if (hint->key.objectid >= last)
240 241
			last = max(search_start + hint->key.offset - 1,
				   hint->key.objectid - last);
C
Chris Mason 已提交
242 243
		else
			last = hint->key.objectid + hint->key.offset;
244 245
		hint_last = last;
	} else {
246 247 248 249 250 251
		if (hint)
			hint_last = max(hint->key.objectid, search_start);
		else
			hint_last = search_start;

		last = hint_last;
252
	}
C
Chris Mason 已提交
253
	while(1) {
C
Chris Mason 已提交
254
		ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
C
Chris Mason 已提交
255
						 last, ARRAY_SIZE(cache),
256
						 BTRFS_BLOCK_GROUP_AVAIL);
C
Chris Mason 已提交
257 258 259
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
260 261
			last = cache[i]->key.objectid +
				cache[i]->key.offset;
C
Chris Mason 已提交
262
			used = btrfs_block_group_used(&cache[i]->item);
C
Chris Mason 已提交
263 264
			if (used + cache[i]->pinned <
			    (cache[i]->key.offset * 8) / 10) {
265 266
				found_group = cache[i];
				goto found;
C
Chris Mason 已提交
267
			}
C
Chris Mason 已提交
268 269 270 271 272 273
			if (used >= (cache[i]->key.offset * 8) / 10) {
				radix_tree_tag_clear(radix,
						     cache[i]->key.objectid +
						     cache[i]->key.offset - 1,
						     BTRFS_BLOCK_GROUP_AVAIL);
			}
C
Chris Mason 已提交
274 275
		}
	}
276 277
	last = hint_last;
again:
C
Chris Mason 已提交
278
	while(1) {
C
Chris Mason 已提交
279 280
		ret = radix_tree_gang_lookup(radix, (void **)cache,
					     last, ARRAY_SIZE(cache));
C
Chris Mason 已提交
281 282 283
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
284 285
			last = cache[i]->key.objectid +
				cache[i]->key.offset;
C
Chris Mason 已提交
286
			used = btrfs_block_group_used(&cache[i]->item);
C
Chris Mason 已提交
287
			if (used + cache[i]->pinned < cache[i]->key.offset) {
288 289
				found_group = cache[i];
				goto found;
C
Chris Mason 已提交
290
			}
C
Chris Mason 已提交
291 292 293 294 295 296
			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 已提交
297 298
		}
	}
299
	if (!full_search) {
C
Chris Mason 已提交
300
		last = search_start;
301 302 303 304
		full_search = 1;
		goto again;
	}
	if (!found_group) {
C
Chris Mason 已提交
305
		ret = radix_tree_gang_lookup(radix,
306 307 308
					     (void **)&found_group, 0, 1);
		BUG_ON(ret != 1);
	}
C
Chris Mason 已提交
309
found:
310
	return found_group;
C
Chris Mason 已提交
311 312
}

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

325
	find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
C
Chris Mason 已提交
326
			 &ins, 0);
327 328 329
	path = btrfs_alloc_path();
	BUG_ON(!path);
	btrfs_init_path(path);
C
Chris Mason 已提交
330 331
	key.objectid = blocknr;
	key.flags = 0;
332
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
333
	key.offset = num_blocks;
334
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
335
				0, 1);
336 337
	if (ret != 0) {
printk("can't find block %Lu %Lu\n", blocknr, num_blocks);
338
		BUG();
339
	}
C
Chris Mason 已提交
340
	BUG_ON(ret != 0);
341 342
	l = btrfs_buffer_leaf(path->nodes[0]);
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
C
Chris Mason 已提交
343 344
	refs = btrfs_extent_refs(item);
	btrfs_set_extent_refs(item, refs + 1);
345
	btrfs_mark_buffer_dirty(path->nodes[0]);
346

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

C
Chris Mason 已提交
354 355 356
static int lookup_extent_ref(struct btrfs_trans_handle *trans,
			     struct btrfs_root *root, u64 blocknr,
			     u64 num_blocks, u32 *refs)
357
{
358
	struct btrfs_path *path;
359
	int ret;
C
Chris Mason 已提交
360
	struct btrfs_key key;
C
Chris Mason 已提交
361 362
	struct btrfs_leaf *l;
	struct btrfs_extent_item *item;
363 364 365

	path = btrfs_alloc_path();
	btrfs_init_path(path);
366
	key.objectid = blocknr;
367
	key.offset = num_blocks;
368 369
	key.flags = 0;
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
370
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
371
				0, 0);
372 373
	if (ret != 0)
		BUG();
374 375
	l = btrfs_buffer_leaf(path->nodes[0]);
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
C
Chris Mason 已提交
376
	*refs = btrfs_extent_refs(item);
377 378
	btrfs_release_path(root->fs_info->extent_root, path);
	btrfs_free_path(path);
379 380 381
	return 0;
}

C
Chris Mason 已提交
382 383 384
int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root)
{
C
Chris Mason 已提交
385
	return btrfs_inc_extent_ref(trans, root, bh_blocknr(root->node), 1);
C
Chris Mason 已提交
386 387
}

388
int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
C
Chris Mason 已提交
389
		  struct buffer_head *buf)
C
Chris Mason 已提交
390 391
{
	u64 blocknr;
C
Chris Mason 已提交
392
	struct btrfs_node *buf_node;
393 394 395
	struct btrfs_leaf *buf_leaf;
	struct btrfs_disk_key *key;
	struct btrfs_file_extent_item *fi;
C
Chris Mason 已提交
396
	int i;
397 398
	int leaf;
	int ret;
399

400
	if (!root->ref_cows)
401
		return 0;
C
Chris Mason 已提交
402
	buf_node = btrfs_buffer_node(buf);
403 404
	leaf = btrfs_is_leaf(buf_node);
	buf_leaf = btrfs_buffer_leaf(buf);
C
Chris Mason 已提交
405
	for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
406 407 408 409 410 411
		if (leaf) {
			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);
412 413 414
			if (btrfs_file_extent_type(fi) ==
			    BTRFS_FILE_EXTENT_INLINE)
				continue;
C
Chris Mason 已提交
415
			ret = btrfs_inc_extent_ref(trans, root,
416 417 418 419 420
				    btrfs_file_extent_disk_blocknr(fi),
				    btrfs_file_extent_disk_num_blocks(fi));
			BUG_ON(ret);
		} else {
			blocknr = btrfs_node_blockptr(buf_node, i);
C
Chris Mason 已提交
421
			ret = btrfs_inc_extent_ref(trans, root, blocknr, 1);
422 423
			BUG_ON(ret);
		}
C
Chris Mason 已提交
424 425 426 427
	}
	return 0;
}

C
Chris Mason 已提交
428 429 430 431 432 433 434 435 436 437 438
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;
	struct btrfs_key ins;

C
Chris Mason 已提交
439
	find_free_extent(trans, extent_root, 0, 0, (u64)-1, &ins, 0);
C
Chris Mason 已提交
440 441 442 443 444 445 446 447 448 449 450 451 452 453
	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
	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));
	mark_buffer_dirty(path->nodes[0]);
	btrfs_release_path(extent_root, path);

	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 已提交
454 455
	if (cache->data)
		cache->last_alloc = cache->first_free;
C
Chris Mason 已提交
456 457 458 459
	return 0;

}

C
Chris Mason 已提交
460 461 462
static int write_dirty_block_radix(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct radix_tree_root *radix)
C
Chris Mason 已提交
463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494
{
	struct btrfs_block_group_cache *cache[8];
	int ret;
	int err = 0;
	int werr = 0;
	int i;
	struct btrfs_path *path;

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

	while(1) {
		ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
						 0, ARRAY_SIZE(cache),
						 BTRFS_BLOCK_GROUP_DIRTY);
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
			radix_tree_tag_clear(radix, cache[i]->key.objectid +
					     cache[i]->key.offset - 1,
					     BTRFS_BLOCK_GROUP_DIRTY);
			err = write_one_cache_group(trans, root,
						    path, cache[i]);
			if (err)
				werr = err;
		}
	}
	btrfs_free_path(path);
	return werr;
}

C
Chris Mason 已提交
495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
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 已提交
511 512
static int update_block_group(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
513
			      u64 blocknr, u64 num, int alloc, int mark_free)
C
Chris Mason 已提交
514 515 516 517 518 519
{
	struct btrfs_block_group_cache *cache;
	struct btrfs_fs_info *info = root->fs_info;
	u64 total = num;
	u64 old_val;
	u64 block_in_group;
520
	u64 i;
C
Chris Mason 已提交
521

C
Chris Mason 已提交
522
	while(total) {
C
Chris Mason 已提交
523 524
		cache = lookup_block_group(info, blocknr);
		if (!cache) {
C
Chris Mason 已提交
525 526
			printk(KERN_CRIT "blocknr %Lu lookup failed\n",
			       blocknr);
C
Chris Mason 已提交
527
			return -1;
C
Chris Mason 已提交
528
		}
C
Chris Mason 已提交
529 530
		block_in_group = blocknr - cache->key.objectid;
		WARN_ON(block_in_group > cache->key.offset);
C
Chris Mason 已提交
531
		radix_tree_tag_set(cache->radix, cache->key.objectid +
C
Chris Mason 已提交
532
				   cache->key.offset - 1,
C
Chris Mason 已提交
533 534 535 536
				   BTRFS_BLOCK_GROUP_DIRTY);

		old_val = btrfs_block_group_used(&cache->item);
		num = min(total, cache->key.offset - block_in_group);
C
Chris Mason 已提交
537
		if (alloc) {
C
Chris Mason 已提交
538
			old_val += num;
C
Chris Mason 已提交
539 540
			if (blocknr > cache->last_alloc)
				cache->last_alloc = blocknr;
541 542 543 544 545 546
			if (!cache->data) {
				for (i = 0; i < num; i++) {
					clear_radix_bit(&info->extent_map_radix,
						        blocknr + i);
				}
			}
C
Chris Mason 已提交
547
		} else {
C
Chris Mason 已提交
548
			old_val -= num;
C
Chris Mason 已提交
549 550
			if (blocknr < cache->first_free)
				cache->first_free = blocknr;
551 552 553 554 555 556 557 558 559 560 561 562 563 564
			if (!cache->data && mark_free) {
				for (i = 0; i < num; i++) {
					set_radix_bit(&info->extent_map_radix,
						      blocknr + i);
				}
			}
			if (old_val < (cache->key.offset * 8) / 10 &&
			    old_val + num >= (cache->key.offset * 8) / 10) {
printk("group %Lu now available\n", cache->key.objectid);
				radix_tree_tag_set(cache->radix,
						   cache->key.objectid +
						   cache->key.offset - 1,
						   BTRFS_BLOCK_GROUP_AVAIL);
			}
C
Chris Mason 已提交
565
		}
C
Chris Mason 已提交
566
		btrfs_set_block_group_used(&cache->item, old_val);
567 568
		total -= num;
		blocknr += num;
C
Chris Mason 已提交
569 570 571 572
	}
	return 0;
}

C
Chris Mason 已提交
573 574 575 576 577 578 579
static int try_remove_page(struct address_space *mapping, unsigned long index)
{
	int ret;
	ret = invalidate_mapping_pages(mapping, index, index);
	return ret;
}

580 581
int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
			       btrfs_root *root)
582
{
C
Chris Mason 已提交
583
	unsigned long gang[8];
C
Chris Mason 已提交
584
	struct inode *btree_inode = root->fs_info->btree_inode;
C
Chris Mason 已提交
585
	struct btrfs_block_group_cache *block_group;
586
	u64 first = 0;
587 588
	int ret;
	int i;
C
Chris Mason 已提交
589
	struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
590
	struct radix_tree_root *extent_radix = &root->fs_info->extent_map_radix;
591 592

	while(1) {
593
		ret = find_first_radix_bit(pinned_radix, gang, 0,
C
Chris Mason 已提交
594
					   ARRAY_SIZE(gang));
595 596
		if (!ret)
			break;
597
		if (!first)
C
Chris Mason 已提交
598
			first = gang[0];
599
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
600
			clear_radix_bit(pinned_radix, gang[i]);
C
Chris Mason 已提交
601 602 603 604 605 606 607
			block_group = lookup_block_group(root->fs_info,
							 gang[i]);
			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];
608 609 610 611
				if (gang[i] < block_group->last_prealloc)
					block_group->last_prealloc = gang[i];
				if (!block_group->data)
					set_radix_bit(extent_radix, gang[i]);
C
Chris Mason 已提交
612
			}
C
Chris Mason 已提交
613 614 615
			try_remove_page(btree_inode->i_mapping,
					gang[i] << (PAGE_CACHE_SHIFT -
						    btree_inode->i_blkbits));
616
		}
617 618 619 620
	}
	return 0;
}

621 622
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root)
C
Chris Mason 已提交
623
{
C
Chris Mason 已提交
624
	struct btrfs_key ins;
C
Chris Mason 已提交
625
	struct btrfs_extent_item extent_item;
C
Chris Mason 已提交
626 627
	int i;
	int ret;
628 629
	u64 super_blocks_used;
	struct btrfs_fs_info *info = extent_root->fs_info;
C
Chris Mason 已提交
630

C
Chris Mason 已提交
631
	btrfs_set_extent_refs(&extent_item, 1);
C
Chris Mason 已提交
632 633
	ins.offset = 1;
	ins.flags = 0;
634
	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
635
	btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid);
C
Chris Mason 已提交
636

637 638
	for (i = 0; i < extent_root->fs_info->extent_tree_insert_nr; i++) {
		ins.objectid = extent_root->fs_info->extent_tree_insert[i];
639 640 641
		super_blocks_used = btrfs_super_blocks_used(info->disk_super);
		btrfs_set_super_blocks_used(info->disk_super,
					    super_blocks_used + 1);
642 643
		ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
					sizeof(extent_item));
C
Chris Mason 已提交
644 645
		BUG_ON(ret);
	}
646 647
	extent_root->fs_info->extent_tree_insert_nr = 0;
	extent_root->fs_info->extent_tree_prealloc_nr = 0;
C
Chris Mason 已提交
648 649 650
	return 0;
}

C
Chris Mason 已提交
651
static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
C
Chris Mason 已提交
652 653
{
	int err;
C
Chris Mason 已提交
654
	struct btrfs_header *header;
C
Chris Mason 已提交
655 656
	struct buffer_head *bh;

C
Chris Mason 已提交
657
	if (!pending) {
658
		bh = btrfs_find_tree_block(root, blocknr);
C
Chris Mason 已提交
659 660 661 662 663 664 665 666 667 668
		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 已提交
669
			}
C
Chris Mason 已提交
670
			btrfs_block_release(root, bh);
C
Chris Mason 已提交
671 672
		}
		err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
C
Chris Mason 已提交
673 674 675 676 677 678
		if (!err) {
			struct btrfs_block_group_cache *cache;
			cache = lookup_block_group(root->fs_info, blocknr);
			if (cache)
				cache->pinned++;
		}
C
Chris Mason 已提交
679 680 681
	} else {
		err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
	}
C
Chris Mason 已提交
682
	BUG_ON(err < 0);
C
Chris Mason 已提交
683 684 685
	return 0;
}

686
/*
687
 * remove an extent from the root, returns 0 on success
688
 */
689
static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
690 691
			 *root, u64 blocknr, u64 num_blocks, int pin,
			 int mark_free)
692
{
693
	struct btrfs_path *path;
C
Chris Mason 已提交
694
	struct btrfs_key key;
695 696
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
697
	int ret;
C
Chris Mason 已提交
698
	struct btrfs_extent_item *ei;
C
Chris Mason 已提交
699
	struct btrfs_key ins;
C
Chris Mason 已提交
700
	u32 refs;
C
Chris Mason 已提交
701

702 703
	key.objectid = blocknr;
	key.flags = 0;
704
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
705 706
	key.offset = num_blocks;

C
Chris Mason 已提交
707
	find_free_extent(trans, root, 0, 0, (u64)-1, &ins, 0);
708 709 710
	path = btrfs_alloc_path();
	BUG_ON(!path);
	btrfs_init_path(path);
711

712
	ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
713
	if (ret) {
714
		printk("failed to find %Lu\n", key.objectid);
C
Chris Mason 已提交
715
		btrfs_print_tree(extent_root, extent_root->node);
716
		printk("failed to find %Lu\n", key.objectid);
717 718
		BUG();
	}
719
	ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
C
Chris Mason 已提交
720
			    struct btrfs_extent_item);
721
	BUG_ON(ei->refs == 0);
C
Chris Mason 已提交
722 723
	refs = btrfs_extent_refs(ei) - 1;
	btrfs_set_extent_refs(ei, refs);
724
	btrfs_mark_buffer_dirty(path->nodes[0]);
C
Chris Mason 已提交
725
	if (refs == 0) {
726
		u64 super_blocks_used;
C
Chris Mason 已提交
727 728

		if (pin) {
C
Chris Mason 已提交
729
			ret = pin_down_block(root, blocknr, 0);
C
Chris Mason 已提交
730 731 732
			BUG_ON(ret);
		}

733 734 735
		super_blocks_used = btrfs_super_blocks_used(info->disk_super);
		btrfs_set_super_blocks_used(info->disk_super,
					    super_blocks_used - num_blocks);
736
		ret = btrfs_del_item(trans, extent_root, path);
737 738
		if (ret)
			BUG();
739 740
		ret = update_block_group(trans, root, blocknr, num_blocks, 0,
					 mark_free);
C
Chris Mason 已提交
741
		BUG_ON(ret);
742
	}
743
	btrfs_free_path(path);
744
	finish_current_insert(trans, extent_root);
745 746 747 748 749 750 751
	return ret;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
752 753
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root)
754 755
{
	int ret;
C
Chris Mason 已提交
756 757
	int wret;
	int err = 0;
C
Chris Mason 已提交
758
	unsigned long gang[4];
759
	int i;
C
Chris Mason 已提交
760 761
	struct radix_tree_root *pending_radix;
	struct radix_tree_root *pinned_radix;
C
Chris Mason 已提交
762
	struct btrfs_block_group_cache *cache;
C
Chris Mason 已提交
763 764 765

	pending_radix = &extent_root->fs_info->pending_del_radix;
	pinned_radix = &extent_root->fs_info->pinned_radix;
766 767

	while(1) {
768
		ret = find_first_radix_bit(pending_radix, gang, 0,
C
Chris Mason 已提交
769
					   ARRAY_SIZE(gang));
770 771 772
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
773
			wret = set_radix_bit(pinned_radix, gang[i]);
C
Chris Mason 已提交
774 775 776 777 778 779 780 781 782 783 784
			if (wret == 0) {
				cache = lookup_block_group(extent_root->fs_info,
							   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 已提交
785 786
			wret = clear_radix_bit(pending_radix, gang[i]);
			BUG_ON(wret);
787
			wret = __free_extent(trans, extent_root,
788
					     gang[i], 1, 0, 0);
C
Chris Mason 已提交
789 790
			if (wret)
				err = wret;
791 792
		}
	}
C
Chris Mason 已提交
793
	return err;
794 795 796 797 798
}

/*
 * remove an extent from the root, returns 0 on success
 */
799 800
int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, u64 blocknr, u64 num_blocks, int pin)
801
{
802
	struct btrfs_root *extent_root = root->fs_info->extent_root;
803 804
	int pending_ret;
	int ret;
805

806
	if (root == extent_root) {
C
Chris Mason 已提交
807
		pin_down_block(root, blocknr, 1);
808 809
		return 0;
	}
810
	ret = __free_extent(trans, root, blocknr, num_blocks, pin, pin == 0);
C
Chris Mason 已提交
811
	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
812 813 814 815 816 817 818
	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
819
 * ins->flags = BTRFS_EXTENT_ITEM_KEY
820 821 822
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
823 824
static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
			    *orig_root, u64 num_blocks, u64 search_start, u64
C
Chris Mason 已提交
825
			    search_end, struct btrfs_key *ins, int data)
826
{
827
	struct btrfs_path *path;
C
Chris Mason 已提交
828
	struct btrfs_key key;
829 830 831
	int ret;
	u64 hole_size = 0;
	int slot = 0;
C
Chris Mason 已提交
832
	u64 last_block = 0;
C
Chris Mason 已提交
833
	u64 test_block;
C
Chris Mason 已提交
834
	u64 orig_search_start = search_start;
835
	int start_found;
C
Chris Mason 已提交
836
	struct btrfs_leaf *l;
837
	struct btrfs_root * root = orig_root->fs_info->extent_root;
838
	struct btrfs_fs_info *info = root->fs_info;
839
	int total_needed = num_blocks;
840 841
	int total_found = 0;
	int fill_prealloc = 0;
C
Chris Mason 已提交
842
	int level;
C
Chris Mason 已提交
843
	struct btrfs_block_group_cache *block_group;
C
Chris Mason 已提交
844
	int full_scan = 0;
845

846 847 848 849
	path = btrfs_alloc_path();
	ins->flags = 0;
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);

C
Chris Mason 已提交
850
	level = btrfs_header_level(btrfs_buffer_header(root->node));
851 852 853
	if (num_blocks == 0) {
		fill_prealloc = 1;
		num_blocks = 1;
854
		total_needed = (min(level + 1, BTRFS_MAX_LEVEL) + 2) * 3;
855
	}
C
Chris Mason 已提交
856 857
	if (search_end == (u64)-1)
		search_end = btrfs_super_total_blocks(info->disk_super);
C
Chris Mason 已提交
858 859 860 861 862 863 864 865 866 867 868
	if (search_start) {
		block_group = lookup_block_group(info, search_start);
		block_group = btrfs_find_block_group(root, block_group,
						     search_start, data);
	} else {
		block_group = btrfs_find_block_group(root,
						     trans->block_group, 0,
						     data);
	}

check_failed:
C
Chris Mason 已提交
869
	if (!full_scan && block_group->data != data)
C
Chris Mason 已提交
870
		WARN_ON(1);
871 872 873 874 875 876 877

	if (!data)
		search_start = find_search_start(root, &block_group,
						 search_start, total_needed);
	else
		search_start = max(block_group->last_alloc, search_start);

878
	btrfs_init_path(path);
879 880 881
	ins->objectid = search_start;
	ins->offset = 0;
	start_found = 0;
882

883
	ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
C
Chris Mason 已提交
884 885
	if (ret < 0)
		goto error;
C
Chris Mason 已提交
886

887
	if (path->slots[0] > 0) {
888
		path->slots[0]--;
889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909
	}

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

911
	while (1) {
912 913
		l = btrfs_buffer_leaf(path->nodes[0]);
		slot = path->slots[0];
914
		if (slot >= btrfs_header_nritems(&l->header)) {
915 916 917 918
			if (fill_prealloc) {
				info->extent_tree_prealloc_nr = 0;
				total_found = 0;
			}
919
			ret = btrfs_next_leaf(root, path);
920 921
			if (ret == 0)
				continue;
C
Chris Mason 已提交
922 923
			if (ret < 0)
				goto error;
924 925
			if (!start_found) {
				ins->objectid = search_start;
C
Chris Mason 已提交
926
				ins->offset = search_end - search_start;
927 928 929 930 931
				start_found = 1;
				goto check_pending;
			}
			ins->objectid = last_block > search_start ?
					last_block : search_start;
C
Chris Mason 已提交
932
			ins->offset = search_end - ins->objectid;
933 934
			goto check_pending;
		}
935

C
Chris Mason 已提交
936
		btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
937 938 939 940 941 942 943 944 945
		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;
946
			}
947
		}
948 949 950 951

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

952
		start_found = 1;
C
Chris Mason 已提交
953
		last_block = key.objectid + key.offset;
C
Chris Mason 已提交
954 955 956 957 958 959 960
		if (last_block >= block_group->key.objectid +
		    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 已提交
961
next:
962
		path->slots[0]++;
963 964 965 966 967 968
	}
	// FIXME -ENOSPC
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
	 */
969
	btrfs_release_path(root, path);
970
	BUG_ON(ins->objectid < search_start);
971

C
Chris Mason 已提交
972
	if (ins->objectid + num_blocks >= search_end) {
C
Chris Mason 已提交
973
		if (full_scan)
974
			return -ENOSPC;
C
Chris Mason 已提交
975 976 977
		search_start = orig_search_start;
		full_scan = 1;
		goto new_group;
978
	}
C
Chris Mason 已提交
979
	for (test_block = ins->objectid;
980 981
	     test_block < ins->objectid + num_blocks; test_block++) {
		if (test_radix_bit(&info->pinned_radix, test_block)) {
C
Chris Mason 已提交
982
			search_start = test_block + 1;
C
Chris Mason 已提交
983
			goto new_group;
984 985
		}
	}
986 987 988 989 990 991 992
	if (!fill_prealloc && info->extent_tree_insert_nr) {
		u64 last =
		  info->extent_tree_insert[info->extent_tree_insert_nr - 1];
		if (ins->objectid + num_blocks >
		    info->extent_tree_insert[0] &&
		    ins->objectid <= last) {
			search_start = last + 1;
993
			WARN_ON(!full_scan);
C
Chris Mason 已提交
994
			goto new_group;
995 996 997 998 999 1000 1001 1002
		}
	}
	if (!fill_prealloc && info->extent_tree_prealloc_nr) {
		u64 first =
		  info->extent_tree_prealloc[info->extent_tree_prealloc_nr - 1];
		if (ins->objectid + num_blocks > first &&
		    ins->objectid <= info->extent_tree_prealloc[0]) {
			search_start = info->extent_tree_prealloc[0] + 1;
1003
			WARN_ON(!full_scan);
C
Chris Mason 已提交
1004
			goto new_group;
1005 1006 1007 1008 1009
		}
	}
	if (fill_prealloc) {
		int nr;
		test_block = ins->objectid;
1010 1011 1012 1013 1014
		if (test_block - info->extent_tree_prealloc[total_needed - 1] >=
		    leaf_range(root)) {
			total_found = 0;
			info->extent_tree_prealloc_nr = total_found;
		}
1015 1016 1017 1018
		while(test_block < ins->objectid + ins->offset &&
		      total_found < total_needed) {
			nr = total_needed - total_found - 1;
			BUG_ON(nr < 0);
C
Chris Mason 已提交
1019
			info->extent_tree_prealloc[nr] = test_block;
1020 1021 1022 1023 1024
			total_found++;
			test_block++;
		}
		if (total_found < total_needed) {
			search_start = test_block;
C
Chris Mason 已提交
1025
			goto new_group;
1026
		}
C
Chris Mason 已提交
1027 1028
		info->extent_tree_prealloc_nr = total_found;
	}
1029 1030 1031 1032 1033 1034 1035 1036 1037
	if (!data) {
		block_group = lookup_block_group(info, ins->objectid);
		if (block_group) {
			if (fill_prealloc)
				block_group->last_prealloc =
				     info->extent_tree_prealloc[total_needed-1];
			else
				trans->block_group = block_group;
		}
1038
	}
C
Chris Mason 已提交
1039
	ins->offset = num_blocks;
1040
	btrfs_free_path(path);
1041
	return 0;
C
Chris Mason 已提交
1042 1043

new_group:
C
Chris Mason 已提交
1044
	if (search_start + num_blocks >= search_end) {
C
Chris Mason 已提交
1045
		search_start = orig_search_start;
1046
printk("doing full scan!\n");
C
Chris Mason 已提交
1047 1048 1049 1050 1051 1052 1053 1054
		full_scan = 1;
	}
	block_group = lookup_block_group(info, search_start);
	if (!full_scan)
		block_group = btrfs_find_block_group(root, block_group,
						     search_start, data);
	goto check_failed;

C
Chris Mason 已提交
1055
error:
1056 1057
	btrfs_release_path(root, path);
	btrfs_free_path(path);
C
Chris Mason 已提交
1058
	return ret;
1059 1060 1061 1062 1063 1064 1065 1066
}
/*
 * 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.
 */
1067 1068
int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root, u64 owner,
1069
		       u64 num_blocks, u64 search_start,
C
Chris Mason 已提交
1070
		       u64 search_end, struct btrfs_key *ins, int data)
1071 1072 1073
{
	int ret;
	int pending_ret;
1074 1075 1076
	u64 super_blocks_used;
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
C
Chris Mason 已提交
1077
	struct btrfs_extent_item extent_item;
1078
	struct btrfs_key prealloc_key;
C
Chris Mason 已提交
1079

C
Chris Mason 已提交
1080
	btrfs_set_extent_refs(&extent_item, 1);
1081
	btrfs_set_extent_owner(&extent_item, owner);
1082

C
Chris Mason 已提交
1083
	if (root == extent_root) {
1084 1085
		int nr;
		BUG_ON(info->extent_tree_prealloc_nr == 0);
C
Chris Mason 已提交
1086 1087
		BUG_ON(num_blocks != 1);
		ins->offset = 1;
1088 1089 1090 1091 1092
		info->extent_tree_prealloc_nr--;
		nr = info->extent_tree_prealloc_nr;
		ins->objectid = info->extent_tree_prealloc[nr];
		info->extent_tree_insert[info->extent_tree_insert_nr++] =
			ins->objectid;
C
Chris Mason 已提交
1093
		ret = update_block_group(trans, root,
1094
					 ins->objectid, ins->offset, 1, 0);
C
Chris Mason 已提交
1095
		BUG_ON(ret);
1096 1097
		return 0;
	}
1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116

	/*
	 * if we're doing a data allocation, preallocate room in the
	 * extent tree first.  This way the extent tree blocks end up
	 * in the correct block group.
	 */
	if (data) {
		ret = find_free_extent(trans, root, 0, search_start,
				       search_end, &prealloc_key, 0);
		if (ret) {
			return ret;
		}
		if (prealloc_key.objectid + prealloc_key.offset >= search_end) {
			int nr = info->extent_tree_prealloc_nr;
			search_end = info->extent_tree_prealloc[nr - 1] - 1;
		} else {
			search_start = info->extent_tree_prealloc[0] + 1;
		}
	}
1117
	/* do the real allocation */
1118
	ret = find_free_extent(trans, root, num_blocks, search_start,
C
Chris Mason 已提交
1119
			       search_end, ins, data);
1120
	if (ret) {
C
Chris Mason 已提交
1121
		return ret;
1122
	}
1123

1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137
	/*
	 * if we're doing a metadata allocation, preallocate space in the
	 * extent tree second.  This way, we don't create a tiny hole
	 * in the allocation map between any unused preallocation blocks
	 * and the metadata block we're actually allocating.  On disk,
	 * it'll go:
	 * [block we've allocated], [used prealloc 1], [ unused prealloc ]
	 * The unused prealloc will get reused the next time around.
	 */
	if (!data) {
		if (ins->objectid + ins->offset >= search_end)
			search_end = ins->objectid - 1;
		else
			search_start = ins->objectid + ins->offset;
C
Chris Mason 已提交
1138

1139 1140 1141 1142 1143 1144
		ret = find_free_extent(trans, root, 0, search_start,
				       search_end, &prealloc_key, 0);
		if (ret) {
			return ret;
		}
	}
1145

1146 1147 1148
	super_blocks_used = btrfs_super_blocks_used(info->disk_super);
	btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
				    num_blocks);
1149 1150
	ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
				sizeof(extent_item));
C
Chris Mason 已提交
1151

1152
	finish_current_insert(trans, extent_root);
C
Chris Mason 已提交
1153
	pending_ret = del_pending_extents(trans, extent_root);
1154
	if (ret) {
C
Chris Mason 已提交
1155
		return ret;
1156 1157
	}
	if (pending_ret) {
C
Chris Mason 已提交
1158
		return pending_ret;
1159 1160
	}
	ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
C
Chris Mason 已提交
1161
	return 0;
1162 1163 1164 1165 1166 1167
}

/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
C
Chris Mason 已提交
1168
struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1169
					   struct btrfs_root *root, u64 hint)
1170
{
C
Chris Mason 已提交
1171
	struct btrfs_key ins;
1172
	int ret;
C
Chris Mason 已提交
1173
	struct buffer_head *buf;
1174

1175
	ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1176
				 1, 0, (unsigned long)-1, &ins, 0);
1177 1178 1179 1180
	if (ret) {
		BUG();
		return NULL;
	}
C
Chris Mason 已提交
1181
	BUG_ON(ret);
1182
	buf = btrfs_find_create_tree_block(root, ins.objectid);
1183
	set_buffer_uptodate(buf);
C
Chris Mason 已提交
1184
	set_buffer_checked(buf);
1185
	set_radix_bit(&trans->transaction->dirty_pages, buf->b_page->index);
1186 1187
	return buf;
}
1188

1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206
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++) {
		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);
1207 1208
		if (btrfs_file_extent_type(fi) == BTRFS_FILE_EXTENT_INLINE)
			continue;
1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221
		/*
		 * FIXME make sure to insert a trans record that
		 * repeats the snapshot del on crash
		 */
		ret = btrfs_free_extent(trans, root,
					btrfs_file_extent_disk_blocknr(fi),
					btrfs_file_extent_disk_num_blocks(fi),
					0);
		BUG_ON(ret);
	}
	return 0;
}

C
Chris Mason 已提交
1222 1223 1224 1225
/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
1226 1227
static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
			  *root, struct btrfs_path *path, int *level)
C
Chris Mason 已提交
1228
{
C
Chris Mason 已提交
1229 1230
	struct buffer_head *next;
	struct buffer_head *cur;
C
Chris Mason 已提交
1231 1232 1233 1234
	u64 blocknr;
	int ret;
	u32 refs;

1235 1236
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
1237
	ret = lookup_extent_ref(trans, root, bh_blocknr(path->nodes[*level]),
1238
			       1, &refs);
C
Chris Mason 已提交
1239 1240 1241
	BUG_ON(ret);
	if (refs > 1)
		goto out;
C
Chris Mason 已提交
1242 1243 1244
	/*
	 * walk down to the last node level and free all the leaves
	 */
1245
	while(*level >= 0) {
1246 1247
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
C
Chris Mason 已提交
1248
		cur = path->nodes[*level];
C
Chris Mason 已提交
1249 1250
		if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
			WARN_ON(1);
1251
		if (path->slots[*level] >=
C
Chris Mason 已提交
1252
		    btrfs_header_nritems(btrfs_buffer_header(cur)))
C
Chris Mason 已提交
1253
			break;
1254 1255 1256 1257 1258
		if (*level == 0) {
			ret = drop_leaf_ref(trans, root, cur);
			BUG_ON(ret);
			break;
		}
C
Chris Mason 已提交
1259 1260
		blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
					      path->slots[*level]);
C
Chris Mason 已提交
1261
		ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1262 1263
		BUG_ON(ret);
		if (refs != 1) {
C
Chris Mason 已提交
1264
			path->slots[*level]++;
1265
			ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
C
Chris Mason 已提交
1266 1267 1268 1269
			BUG_ON(ret);
			continue;
		}
		next = read_tree_block(root, blocknr);
1270
		WARN_ON(*level <= 0);
C
Chris Mason 已提交
1271
		if (path->nodes[*level-1])
C
Chris Mason 已提交
1272
			btrfs_block_release(root, path->nodes[*level-1]);
C
Chris Mason 已提交
1273
		path->nodes[*level-1] = next;
C
Chris Mason 已提交
1274
		*level = btrfs_header_level(btrfs_buffer_header(next));
C
Chris Mason 已提交
1275 1276 1277
		path->slots[*level] = 0;
	}
out:
1278 1279
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
1280
	ret = btrfs_free_extent(trans, root,
1281
				bh_blocknr(path->nodes[*level]), 1, 1);
C
Chris Mason 已提交
1282
	btrfs_block_release(root, path->nodes[*level]);
C
Chris Mason 已提交
1283 1284 1285 1286 1287 1288
	path->nodes[*level] = NULL;
	*level += 1;
	BUG_ON(ret);
	return 0;
}

C
Chris Mason 已提交
1289 1290 1291 1292 1293
/*
 * 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
 */
1294 1295
static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
			*root, struct btrfs_path *path, int *level)
C
Chris Mason 已提交
1296 1297 1298 1299
{
	int i;
	int slot;
	int ret;
C
Chris Mason 已提交
1300
	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
C
Chris Mason 已提交
1301
		slot = path->slots[i];
C
Chris Mason 已提交
1302 1303
		if (slot < btrfs_header_nritems(
		    btrfs_buffer_header(path->nodes[i])) - 1) {
C
Chris Mason 已提交
1304 1305 1306 1307
			path->slots[i]++;
			*level = i;
			return 0;
		} else {
1308
			ret = btrfs_free_extent(trans, root,
1309
						bh_blocknr(path->nodes[*level]),
1310
						1, 1);
1311
			BUG_ON(ret);
C
Chris Mason 已提交
1312
			btrfs_block_release(root, path->nodes[*level]);
C
Chris Mason 已提交
1313
			path->nodes[*level] = NULL;
C
Chris Mason 已提交
1314 1315 1316 1317 1318 1319
			*level = i + 1;
		}
	}
	return 1;
}

C
Chris Mason 已提交
1320 1321 1322 1323 1324
/*
 * 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.
 */
1325
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
C
Chris Mason 已提交
1326
			*root, struct buffer_head *snap)
C
Chris Mason 已提交
1327
{
1328
	int ret = 0;
C
Chris Mason 已提交
1329
	int wret;
C
Chris Mason 已提交
1330
	int level;
1331
	struct btrfs_path *path;
C
Chris Mason 已提交
1332 1333 1334
	int i;
	int orig_level;

1335 1336 1337
	path = btrfs_alloc_path();
	BUG_ON(!path);
	btrfs_init_path(path);
C
Chris Mason 已提交
1338

C
Chris Mason 已提交
1339
	level = btrfs_header_level(btrfs_buffer_header(snap));
C
Chris Mason 已提交
1340
	orig_level = level;
1341 1342
	path->nodes[level] = snap;
	path->slots[level] = 0;
C
Chris Mason 已提交
1343
	while(1) {
1344
		wret = walk_down_tree(trans, root, path, &level);
C
Chris Mason 已提交
1345
		if (wret > 0)
C
Chris Mason 已提交
1346
			break;
C
Chris Mason 已提交
1347 1348 1349
		if (wret < 0)
			ret = wret;

1350
		wret = walk_up_tree(trans, root, path, &level);
C
Chris Mason 已提交
1351
		if (wret > 0)
C
Chris Mason 已提交
1352
			break;
C
Chris Mason 已提交
1353 1354
		if (wret < 0)
			ret = wret;
C
Chris Mason 已提交
1355
		btrfs_btree_balance_dirty(root);
C
Chris Mason 已提交
1356
	}
C
Chris Mason 已提交
1357
	for (i = 0; i <= orig_level; i++) {
1358 1359
		if (path->nodes[i]) {
			btrfs_block_release(root, path->nodes[i]);
C
Chris Mason 已提交
1360
		}
C
Chris Mason 已提交
1361
	}
1362
	btrfs_free_path(path);
C
Chris Mason 已提交
1363
	return ret;
C
Chris Mason 已提交
1364
}
C
Chris Mason 已提交
1365

C
Chris Mason 已提交
1366
static int free_block_group_radix(struct radix_tree_root *radix)
C
Chris Mason 已提交
1367 1368 1369 1370 1371 1372
{
	int ret;
	struct btrfs_block_group_cache *cache[8];
	int i;

	while(1) {
C
Chris Mason 已提交
1373
		ret = radix_tree_gang_lookup(radix, (void **)cache, 0,
C
Chris Mason 已提交
1374 1375 1376 1377
					     ARRAY_SIZE(cache));
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
C
Chris Mason 已提交
1378
			radix_tree_delete(radix, cache[i]->key.objectid +
C
Chris Mason 已提交
1379 1380 1381 1382 1383 1384 1385
					  cache[i]->key.offset - 1);
			kfree(cache[i]);
		}
	}
	return 0;
}

C
Chris Mason 已提交
1386 1387 1388 1389
int btrfs_free_block_groups(struct btrfs_fs_info *info)
{
	int ret;
	int ret2;
1390 1391
	unsigned long gang[16];
	int i;
C
Chris Mason 已提交
1392 1393 1394 1395 1396 1397 1398

	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;
1399 1400 1401 1402 1403 1404 1405 1406 1407 1408

	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 已提交
1409 1410 1411
	return 0;
}

C
Chris Mason 已提交
1412 1413 1414 1415 1416 1417 1418
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 已提交
1419 1420
	struct btrfs_fs_info *info = root->fs_info;
	struct radix_tree_root *radix;
C
Chris Mason 已提交
1421 1422 1423 1424
	struct btrfs_key key;
	struct btrfs_key found_key;
	struct btrfs_leaf *leaf;
	u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;
1425
	u64 used;
C
Chris Mason 已提交
1426
	u64 nr = 0;
C
Chris Mason 已提交
1427

C
Chris Mason 已提交
1428
	root = info->extent_root;
C
Chris Mason 已提交
1429 1430 1431 1432 1433 1434 1435 1436 1437 1438
	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 已提交
1439
		ret = btrfs_search_slot(NULL, info->extent_root,
C
Chris Mason 已提交
1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452
					&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 已提交
1453

1454
		if (nr % 3)
C
Chris Mason 已提交
1455 1456 1457 1458
			radix = &info->block_group_data_radix;
		else
			radix = &info->block_group_radix;

C
Chris Mason 已提交
1459 1460 1461 1462
		bi = btrfs_item_ptr(leaf, path->slots[0],
				    struct btrfs_block_group_item);
		memcpy(&cache->item, bi, sizeof(*bi));
		memcpy(&cache->key, &found_key, sizeof(found_key));
1463 1464
		cache->last_alloc = cache->key.objectid;
		cache->first_free = cache->key.objectid;
1465
		cache->last_prealloc = cache->key.objectid;
C
Chris Mason 已提交
1466
		cache->pinned = 0;
1467 1468 1469 1470 1471 1472
		cache->cached = 0;

		if (nr % 3)
			cache->data = 1;
		else
			cache->data = 0;
C
Chris Mason 已提交
1473 1474
		cache->radix = radix;

C
Chris Mason 已提交
1475 1476
		key.objectid = found_key.objectid + found_key.offset;
		btrfs_release_path(root, path);
C
Chris Mason 已提交
1477
		ret = radix_tree_insert(radix, found_key.objectid +
C
Chris Mason 已提交
1478 1479 1480
					found_key.offset - 1,
					(void *)cache);
		BUG_ON(ret);
1481
		used = btrfs_block_group_used(bi);
C
Chris Mason 已提交
1482 1483
		if (used < (key.offset * 8) / 10) {
			radix_tree_tag_set(radix, found_key.objectid +
1484 1485 1486
					   found_key.offset - 1,
					   BTRFS_BLOCK_GROUP_AVAIL);
		}
C
Chris Mason 已提交
1487
		if (key.objectid >=
C
Chris Mason 已提交
1488
		    btrfs_super_total_blocks(info->disk_super))
C
Chris Mason 已提交
1489
			break;
C
Chris Mason 已提交
1490
		nr++;
C
Chris Mason 已提交
1491 1492 1493 1494 1495
	}

	btrfs_free_path(path);
	return 0;
}