free-space-cache.c 72.9 KB
Newer Older
J
Josef Bacik 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * Copyright (C) 2008 Red Hat.  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.
 */

19
#include <linux/pagemap.h>
J
Josef Bacik 已提交
20
#include <linux/sched.h>
21
#include <linux/slab.h>
22
#include <linux/math64.h>
23
#include <linux/ratelimit.h>
J
Josef Bacik 已提交
24
#include "ctree.h"
25 26
#include "free-space-cache.h"
#include "transaction.h"
27
#include "disk-io.h"
28
#include "extent_io.h"
29
#include "inode-map.h"
30

31 32
#define BITS_PER_BITMAP		(PAGE_CACHE_SIZE * 8)
#define MAX_CACHE_BYTES_PER_GIG	(32 * 1024)
J
Josef Bacik 已提交
33

34
static int link_free_space(struct btrfs_free_space_ctl *ctl,
J
Josef Bacik 已提交
35
			   struct btrfs_free_space *info);
36 37
static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
			      struct btrfs_free_space *info);
J
Josef Bacik 已提交
38

39 40 41
static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
					       struct btrfs_path *path,
					       u64 offset)
42 43 44 45 46 47 48 49 50 51
{
	struct btrfs_key key;
	struct btrfs_key location;
	struct btrfs_disk_key disk_key;
	struct btrfs_free_space_header *header;
	struct extent_buffer *leaf;
	struct inode *inode = NULL;
	int ret;

	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
52
	key.offset = offset;
53 54 55 56 57 58
	key.type = 0;

	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		return ERR_PTR(ret);
	if (ret > 0) {
59
		btrfs_release_path(path);
60 61 62 63 64 65 66 67
		return ERR_PTR(-ENOENT);
	}

	leaf = path->nodes[0];
	header = btrfs_item_ptr(leaf, path->slots[0],
				struct btrfs_free_space_header);
	btrfs_free_space_key(leaf, header, &disk_key);
	btrfs_disk_key_to_cpu(&location, &disk_key);
68
	btrfs_release_path(path);
69 70 71 72 73 74 75 76 77 78 79

	inode = btrfs_iget(root->fs_info->sb, &location, root, NULL);
	if (!inode)
		return ERR_PTR(-ENOENT);
	if (IS_ERR(inode))
		return inode;
	if (is_bad_inode(inode)) {
		iput(inode);
		return ERR_PTR(-ENOENT);
	}

A
Al Viro 已提交
80 81
	mapping_set_gfp_mask(inode->i_mapping,
			mapping_gfp_mask(inode->i_mapping) & ~__GFP_FS);
82

83 84 85 86 87 88 89 90
	return inode;
}

struct inode *lookup_free_space_inode(struct btrfs_root *root,
				      struct btrfs_block_group_cache
				      *block_group, struct btrfs_path *path)
{
	struct inode *inode = NULL;
91
	u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
92 93 94 95 96 97 98 99 100 101 102 103 104

	spin_lock(&block_group->lock);
	if (block_group->inode)
		inode = igrab(block_group->inode);
	spin_unlock(&block_group->lock);
	if (inode)
		return inode;

	inode = __lookup_free_space_inode(root, path,
					  block_group->key.objectid);
	if (IS_ERR(inode))
		return inode;

105
	spin_lock(&block_group->lock);
106
	if (!((BTRFS_I(inode)->flags & flags) == flags)) {
107
		printk(KERN_INFO "Old style space inode found, converting.\n");
108 109
		BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM |
			BTRFS_INODE_NODATACOW;
110 111 112
		block_group->disk_cache_state = BTRFS_DC_CLEAR;
	}

113
	if (!block_group->iref) {
114 115 116 117 118 119 120 121
		block_group->inode = igrab(inode);
		block_group->iref = 1;
	}
	spin_unlock(&block_group->lock);

	return inode;
}

122 123 124
int __create_free_space_inode(struct btrfs_root *root,
			      struct btrfs_trans_handle *trans,
			      struct btrfs_path *path, u64 ino, u64 offset)
125 126 127 128 129 130
{
	struct btrfs_key key;
	struct btrfs_disk_key disk_key;
	struct btrfs_free_space_header *header;
	struct btrfs_inode_item *inode_item;
	struct extent_buffer *leaf;
131
	u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC;
132 133
	int ret;

134
	ret = btrfs_insert_empty_inode(trans, root, path, ino);
135 136 137
	if (ret)
		return ret;

138 139 140 141
	/* We inline crc's for the free disk space cache */
	if (ino != BTRFS_FREE_INO_OBJECTID)
		flags |= BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;

142 143 144 145 146 147 148 149 150 151 152 153
	leaf = path->nodes[0];
	inode_item = btrfs_item_ptr(leaf, path->slots[0],
				    struct btrfs_inode_item);
	btrfs_item_key(leaf, &disk_key, path->slots[0]);
	memset_extent_buffer(leaf, 0, (unsigned long)inode_item,
			     sizeof(*inode_item));
	btrfs_set_inode_generation(leaf, inode_item, trans->transid);
	btrfs_set_inode_size(leaf, inode_item, 0);
	btrfs_set_inode_nbytes(leaf, inode_item, 0);
	btrfs_set_inode_uid(leaf, inode_item, 0);
	btrfs_set_inode_gid(leaf, inode_item, 0);
	btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);
154
	btrfs_set_inode_flags(leaf, inode_item, flags);
155 156
	btrfs_set_inode_nlink(leaf, inode_item, 1);
	btrfs_set_inode_transid(leaf, inode_item, trans->transid);
157
	btrfs_set_inode_block_group(leaf, inode_item, offset);
158
	btrfs_mark_buffer_dirty(leaf);
159
	btrfs_release_path(path);
160 161

	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
162
	key.offset = offset;
163 164 165 166 167
	key.type = 0;

	ret = btrfs_insert_empty_item(trans, root, path, &key,
				      sizeof(struct btrfs_free_space_header));
	if (ret < 0) {
168
		btrfs_release_path(path);
169 170 171 172 173 174 175 176
		return ret;
	}
	leaf = path->nodes[0];
	header = btrfs_item_ptr(leaf, path->slots[0],
				struct btrfs_free_space_header);
	memset_extent_buffer(leaf, 0, (unsigned long)header, sizeof(*header));
	btrfs_set_free_space_key(leaf, header, &disk_key);
	btrfs_mark_buffer_dirty(leaf);
177
	btrfs_release_path(path);
178 179 180 181

	return 0;
}

182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
int create_free_space_inode(struct btrfs_root *root,
			    struct btrfs_trans_handle *trans,
			    struct btrfs_block_group_cache *block_group,
			    struct btrfs_path *path)
{
	int ret;
	u64 ino;

	ret = btrfs_find_free_objectid(root, &ino);
	if (ret < 0)
		return ret;

	return __create_free_space_inode(root, trans, path, ino,
					 block_group->key.objectid);
}

198 199 200 201 202
int btrfs_truncate_free_space_cache(struct btrfs_root *root,
				    struct btrfs_trans_handle *trans,
				    struct btrfs_path *path,
				    struct inode *inode)
{
203
	struct btrfs_block_rsv *rsv;
204
	u64 needed_bytes;
205 206 207
	loff_t oldsize;
	int ret = 0;

208
	rsv = trans->block_rsv;
209 210 211 212 213 214 215 216 217 218 219 220 221
	trans->block_rsv = &root->fs_info->global_block_rsv;

	/* 1 for slack space, 1 for updating the inode */
	needed_bytes = btrfs_calc_trunc_metadata_size(root, 1) +
		btrfs_calc_trans_metadata_size(root, 1);

	spin_lock(&trans->block_rsv->lock);
	if (trans->block_rsv->reserved < needed_bytes) {
		spin_unlock(&trans->block_rsv->lock);
		trans->block_rsv = rsv;
		return -ENOSPC;
	}
	spin_unlock(&trans->block_rsv->lock);
222 223 224 225 226 227 228 229 230 231 232

	oldsize = i_size_read(inode);
	btrfs_i_size_write(inode, 0);
	truncate_pagecache(inode, oldsize, 0);

	/*
	 * We don't need an orphan item because truncating the free space cache
	 * will never be split across transactions.
	 */
	ret = btrfs_truncate_inode_items(trans, root, inode,
					 0, BTRFS_EXTENT_DATA_KEY);
233

234
	if (ret) {
235
		trans->block_rsv = rsv;
236
		btrfs_abort_transaction(trans, root, ret);
237 238 239
		return ret;
	}

240
	ret = btrfs_update_inode(trans, root, inode);
241 242
	if (ret)
		btrfs_abort_transaction(trans, root, ret);
243 244
	trans->block_rsv = rsv;

245
	return ret;
246 247
}

248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266
static int readahead_cache(struct inode *inode)
{
	struct file_ra_state *ra;
	unsigned long last_index;

	ra = kzalloc(sizeof(*ra), GFP_NOFS);
	if (!ra)
		return -ENOMEM;

	file_ra_state_init(ra, inode->i_mapping);
	last_index = (i_size_read(inode) - 1) >> PAGE_CACHE_SHIFT;

	page_cache_sync_readahead(inode->i_mapping, ra, NULL, 0, last_index);

	kfree(ra);

	return 0;
}

267 268 269 270 271 272 273 274
struct io_ctl {
	void *cur, *orig;
	struct page *page;
	struct page **pages;
	struct btrfs_root *root;
	unsigned long size;
	int index;
	int num_pages;
275
	unsigned check_crcs:1;
276 277 278 279 280 281 282 283 284 285 286 287 288
};

static int io_ctl_init(struct io_ctl *io_ctl, struct inode *inode,
		       struct btrfs_root *root)
{
	memset(io_ctl, 0, sizeof(struct io_ctl));
	io_ctl->num_pages = (i_size_read(inode) + PAGE_CACHE_SIZE - 1) >>
		PAGE_CACHE_SHIFT;
	io_ctl->pages = kzalloc(sizeof(struct page *) * io_ctl->num_pages,
				GFP_NOFS);
	if (!io_ctl->pages)
		return -ENOMEM;
	io_ctl->root = root;
289 290
	if (btrfs_ino(inode) != BTRFS_FREE_INO_OBJECTID)
		io_ctl->check_crcs = 1;
291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
	return 0;
}

static void io_ctl_free(struct io_ctl *io_ctl)
{
	kfree(io_ctl->pages);
}

static void io_ctl_unmap_page(struct io_ctl *io_ctl)
{
	if (io_ctl->cur) {
		kunmap(io_ctl->page);
		io_ctl->cur = NULL;
		io_ctl->orig = NULL;
	}
}

static void io_ctl_map_page(struct io_ctl *io_ctl, int clear)
{
	BUG_ON(io_ctl->index >= io_ctl->num_pages);
	io_ctl->page = io_ctl->pages[io_ctl->index++];
	io_ctl->cur = kmap(io_ctl->page);
	io_ctl->orig = io_ctl->cur;
	io_ctl->size = PAGE_CACHE_SIZE;
	if (clear)
		memset(io_ctl->cur, 0, PAGE_CACHE_SIZE);
}

static void io_ctl_drop_pages(struct io_ctl *io_ctl)
{
	int i;

	io_ctl_unmap_page(io_ctl);

	for (i = 0; i < io_ctl->num_pages; i++) {
326 327 328 329 330
		if (io_ctl->pages[i]) {
			ClearPageChecked(io_ctl->pages[i]);
			unlock_page(io_ctl->pages[i]);
			page_cache_release(io_ctl->pages[i]);
		}
331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359
	}
}

static int io_ctl_prepare_pages(struct io_ctl *io_ctl, struct inode *inode,
				int uptodate)
{
	struct page *page;
	gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
	int i;

	for (i = 0; i < io_ctl->num_pages; i++) {
		page = find_or_create_page(inode->i_mapping, i, mask);
		if (!page) {
			io_ctl_drop_pages(io_ctl);
			return -ENOMEM;
		}
		io_ctl->pages[i] = page;
		if (uptodate && !PageUptodate(page)) {
			btrfs_readpage(NULL, page);
			lock_page(page);
			if (!PageUptodate(page)) {
				printk(KERN_ERR "btrfs: error reading free "
				       "space cache\n");
				io_ctl_drop_pages(io_ctl);
				return -EIO;
			}
		}
	}

360 361 362 363 364
	for (i = 0; i < io_ctl->num_pages; i++) {
		clear_page_dirty_for_io(io_ctl->pages[i]);
		set_page_extent_mapped(io_ctl->pages[i]);
	}

365 366 367 368 369
	return 0;
}

static void io_ctl_set_generation(struct io_ctl *io_ctl, u64 generation)
{
A
Al Viro 已提交
370
	__le64 *val;
371 372 373 374

	io_ctl_map_page(io_ctl, 1);

	/*
375 376
	 * Skip the csum areas.  If we don't check crcs then we just have a
	 * 64bit chunk at the front of the first page.
377
	 */
378 379 380 381 382 383 384
	if (io_ctl->check_crcs) {
		io_ctl->cur += (sizeof(u32) * io_ctl->num_pages);
		io_ctl->size -= sizeof(u64) + (sizeof(u32) * io_ctl->num_pages);
	} else {
		io_ctl->cur += sizeof(u64);
		io_ctl->size -= sizeof(u64) * 2;
	}
385 386 387 388 389 390 391 392

	val = io_ctl->cur;
	*val = cpu_to_le64(generation);
	io_ctl->cur += sizeof(u64);
}

static int io_ctl_check_generation(struct io_ctl *io_ctl, u64 generation)
{
A
Al Viro 已提交
393
	__le64 *gen;
394

395 396 397 398 399 400 401 402 403 404 405 406
	/*
	 * Skip the crc area.  If we don't check crcs then we just have a 64bit
	 * chunk at the front of the first page.
	 */
	if (io_ctl->check_crcs) {
		io_ctl->cur += sizeof(u32) * io_ctl->num_pages;
		io_ctl->size -= sizeof(u64) +
			(sizeof(u32) * io_ctl->num_pages);
	} else {
		io_ctl->cur += sizeof(u64);
		io_ctl->size -= sizeof(u64) * 2;
	}
407 408 409 410 411 412 413 414 415 416

	gen = io_ctl->cur;
	if (le64_to_cpu(*gen) != generation) {
		printk_ratelimited(KERN_ERR "btrfs: space cache generation "
				   "(%Lu) does not match inode (%Lu)\n", *gen,
				   generation);
		io_ctl_unmap_page(io_ctl);
		return -EIO;
	}
	io_ctl->cur += sizeof(u64);
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431
	return 0;
}

static void io_ctl_set_crc(struct io_ctl *io_ctl, int index)
{
	u32 *tmp;
	u32 crc = ~(u32)0;
	unsigned offset = 0;

	if (!io_ctl->check_crcs) {
		io_ctl_unmap_page(io_ctl);
		return;
	}

	if (index == 0)
432
		offset = sizeof(u32) * io_ctl->num_pages;
433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473

	crc = btrfs_csum_data(io_ctl->root, io_ctl->orig + offset, crc,
			      PAGE_CACHE_SIZE - offset);
	btrfs_csum_final(crc, (char *)&crc);
	io_ctl_unmap_page(io_ctl);
	tmp = kmap(io_ctl->pages[0]);
	tmp += index;
	*tmp = crc;
	kunmap(io_ctl->pages[0]);
}

static int io_ctl_check_crc(struct io_ctl *io_ctl, int index)
{
	u32 *tmp, val;
	u32 crc = ~(u32)0;
	unsigned offset = 0;

	if (!io_ctl->check_crcs) {
		io_ctl_map_page(io_ctl, 0);
		return 0;
	}

	if (index == 0)
		offset = sizeof(u32) * io_ctl->num_pages;

	tmp = kmap(io_ctl->pages[0]);
	tmp += index;
	val = *tmp;
	kunmap(io_ctl->pages[0]);

	io_ctl_map_page(io_ctl, 0);
	crc = btrfs_csum_data(io_ctl->root, io_ctl->orig + offset, crc,
			      PAGE_CACHE_SIZE - offset);
	btrfs_csum_final(crc, (char *)&crc);
	if (val != crc) {
		printk_ratelimited(KERN_ERR "btrfs: csum mismatch on free "
				   "space cache\n");
		io_ctl_unmap_page(io_ctl);
		return -EIO;
	}

474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495
	return 0;
}

static int io_ctl_add_entry(struct io_ctl *io_ctl, u64 offset, u64 bytes,
			    void *bitmap)
{
	struct btrfs_free_space_entry *entry;

	if (!io_ctl->cur)
		return -ENOSPC;

	entry = io_ctl->cur;
	entry->offset = cpu_to_le64(offset);
	entry->bytes = cpu_to_le64(bytes);
	entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP :
		BTRFS_FREE_SPACE_EXTENT;
	io_ctl->cur += sizeof(struct btrfs_free_space_entry);
	io_ctl->size -= sizeof(struct btrfs_free_space_entry);

	if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
		return 0;

496
	io_ctl_set_crc(io_ctl, io_ctl->index - 1);
497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516

	/* No more pages to map */
	if (io_ctl->index >= io_ctl->num_pages)
		return 0;

	/* map the next page */
	io_ctl_map_page(io_ctl, 1);
	return 0;
}

static int io_ctl_add_bitmap(struct io_ctl *io_ctl, void *bitmap)
{
	if (!io_ctl->cur)
		return -ENOSPC;

	/*
	 * If we aren't at the start of the current page, unmap this one and
	 * map the next one if there is any left.
	 */
	if (io_ctl->cur != io_ctl->orig) {
517
		io_ctl_set_crc(io_ctl, io_ctl->index - 1);
518 519 520 521 522 523
		if (io_ctl->index >= io_ctl->num_pages)
			return -ENOSPC;
		io_ctl_map_page(io_ctl, 0);
	}

	memcpy(io_ctl->cur, bitmap, PAGE_CACHE_SIZE);
524
	io_ctl_set_crc(io_ctl, io_ctl->index - 1);
525 526 527 528 529 530 531
	if (io_ctl->index < io_ctl->num_pages)
		io_ctl_map_page(io_ctl, 0);
	return 0;
}

static void io_ctl_zero_remaining_pages(struct io_ctl *io_ctl)
{
532 533 534 535 536 537 538 539
	/*
	 * If we're not on the boundary we know we've modified the page and we
	 * need to crc the page.
	 */
	if (io_ctl->cur != io_ctl->orig)
		io_ctl_set_crc(io_ctl, io_ctl->index - 1);
	else
		io_ctl_unmap_page(io_ctl);
540 541 542

	while (io_ctl->index < io_ctl->num_pages) {
		io_ctl_map_page(io_ctl, 1);
543
		io_ctl_set_crc(io_ctl, io_ctl->index - 1);
544 545 546
	}
}

547 548
static int io_ctl_read_entry(struct io_ctl *io_ctl,
			    struct btrfs_free_space *entry, u8 *type)
549 550
{
	struct btrfs_free_space_entry *e;
551 552 553 554 555 556 557
	int ret;

	if (!io_ctl->cur) {
		ret = io_ctl_check_crc(io_ctl, io_ctl->index);
		if (ret)
			return ret;
	}
558 559 560 561

	e = io_ctl->cur;
	entry->offset = le64_to_cpu(e->offset);
	entry->bytes = le64_to_cpu(e->bytes);
562
	*type = e->type;
563 564 565 566
	io_ctl->cur += sizeof(struct btrfs_free_space_entry);
	io_ctl->size -= sizeof(struct btrfs_free_space_entry);

	if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
567
		return 0;
568 569 570

	io_ctl_unmap_page(io_ctl);

571
	return 0;
572 573
}

574 575
static int io_ctl_read_bitmap(struct io_ctl *io_ctl,
			      struct btrfs_free_space *entry)
576
{
577 578 579 580 581 582
	int ret;

	ret = io_ctl_check_crc(io_ctl, io_ctl->index);
	if (ret)
		return ret;

583 584
	memcpy(entry->bitmap, io_ctl->cur, PAGE_CACHE_SIZE);
	io_ctl_unmap_page(io_ctl);
585 586

	return 0;
587 588
}

589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626
/*
 * Since we attach pinned extents after the fact we can have contiguous sections
 * of free space that are split up in entries.  This poses a problem with the
 * tree logging stuff since it could have allocated across what appears to be 2
 * entries since we would have merged the entries when adding the pinned extents
 * back to the free space cache.  So run through the space cache that we just
 * loaded and merge contiguous entries.  This will make the log replay stuff not
 * blow up and it will make for nicer allocator behavior.
 */
static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
{
	struct btrfs_free_space *e, *prev = NULL;
	struct rb_node *n;

again:
	spin_lock(&ctl->tree_lock);
	for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
		e = rb_entry(n, struct btrfs_free_space, offset_index);
		if (!prev)
			goto next;
		if (e->bitmap || prev->bitmap)
			goto next;
		if (prev->offset + prev->bytes == e->offset) {
			unlink_free_space(ctl, prev);
			unlink_free_space(ctl, e);
			prev->bytes += e->bytes;
			kmem_cache_free(btrfs_free_space_cachep, e);
			link_free_space(ctl, prev);
			prev = NULL;
			spin_unlock(&ctl->tree_lock);
			goto again;
		}
next:
		prev = e;
	}
	spin_unlock(&ctl->tree_lock);
}

627 628 629
int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
			    struct btrfs_free_space_ctl *ctl,
			    struct btrfs_path *path, u64 offset)
630 631 632
{
	struct btrfs_free_space_header *header;
	struct extent_buffer *leaf;
633
	struct io_ctl io_ctl;
634
	struct btrfs_key key;
635
	struct btrfs_free_space *e, *n;
636 637 638 639
	struct list_head bitmaps;
	u64 num_entries;
	u64 num_bitmaps;
	u64 generation;
640
	u8 type;
641
	int ret = 0;
642 643 644 645

	INIT_LIST_HEAD(&bitmaps);

	/* Nothing in the space cache, goodbye */
646
	if (!i_size_read(inode))
647
		return 0;
648 649

	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
650
	key.offset = offset;
651 652 653
	key.type = 0;

	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
654
	if (ret < 0)
655
		return 0;
656
	else if (ret > 0) {
657
		btrfs_release_path(path);
658
		return 0;
659 660
	}

661 662
	ret = -1;

663 664 665 666 667 668
	leaf = path->nodes[0];
	header = btrfs_item_ptr(leaf, path->slots[0],
				struct btrfs_free_space_header);
	num_entries = btrfs_free_space_entries(leaf, header);
	num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
	generation = btrfs_free_space_generation(leaf, header);
669
	btrfs_release_path(path);
670 671 672

	if (BTRFS_I(inode)->generation != generation) {
		printk(KERN_ERR "btrfs: free space inode generation (%llu) did"
673
		       " not match free space cache generation (%llu)\n",
674
		       (unsigned long long)BTRFS_I(inode)->generation,
675
		       (unsigned long long)generation);
676
		return 0;
677 678 679
	}

	if (!num_entries)
680
		return 0;
681

682 683 684 685
	ret = io_ctl_init(&io_ctl, inode, root);
	if (ret)
		return ret;

686
	ret = readahead_cache(inode);
687
	if (ret)
688 689
		goto out;

690 691 692
	ret = io_ctl_prepare_pages(&io_ctl, inode, 1);
	if (ret)
		goto out;
693

694 695 696 697
	ret = io_ctl_check_crc(&io_ctl, 0);
	if (ret)
		goto free_cache;

698 699 700
	ret = io_ctl_check_generation(&io_ctl, generation);
	if (ret)
		goto free_cache;
701

702 703 704 705
	while (num_entries) {
		e = kmem_cache_zalloc(btrfs_free_space_cachep,
				      GFP_NOFS);
		if (!e)
706 707
			goto free_cache;

708 709 710 711 712 713
		ret = io_ctl_read_entry(&io_ctl, e, &type);
		if (ret) {
			kmem_cache_free(btrfs_free_space_cachep, e);
			goto free_cache;
		}

714 715 716
		if (!e->bytes) {
			kmem_cache_free(btrfs_free_space_cachep, e);
			goto free_cache;
717
		}
718 719 720 721 722 723 724 725 726

		if (type == BTRFS_FREE_SPACE_EXTENT) {
			spin_lock(&ctl->tree_lock);
			ret = link_free_space(ctl, e);
			spin_unlock(&ctl->tree_lock);
			if (ret) {
				printk(KERN_ERR "Duplicate entries in "
				       "free space cache, dumping\n");
				kmem_cache_free(btrfs_free_space_cachep, e);
727 728
				goto free_cache;
			}
729 730 731 732 733 734 735
		} else {
			BUG_ON(!num_bitmaps);
			num_bitmaps--;
			e->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
			if (!e->bitmap) {
				kmem_cache_free(
					btrfs_free_space_cachep, e);
736 737
				goto free_cache;
			}
738 739 740 741 742 743 744 745
			spin_lock(&ctl->tree_lock);
			ret = link_free_space(ctl, e);
			ctl->total_bitmaps++;
			ctl->op->recalc_thresholds(ctl);
			spin_unlock(&ctl->tree_lock);
			if (ret) {
				printk(KERN_ERR "Duplicate entries in "
				       "free space cache, dumping\n");
746
				kmem_cache_free(btrfs_free_space_cachep, e);
747 748
				goto free_cache;
			}
749
			list_add_tail(&e->list, &bitmaps);
750 751
		}

752 753
		num_entries--;
	}
754

755 756
	io_ctl_unmap_page(&io_ctl);

757 758 759 760 761
	/*
	 * We add the bitmaps at the end of the entries in order that
	 * the bitmap entries are added to the cache.
	 */
	list_for_each_entry_safe(e, n, &bitmaps, list) {
762
		list_del_init(&e->list);
763 764 765
		ret = io_ctl_read_bitmap(&io_ctl, e);
		if (ret)
			goto free_cache;
766 767
	}

768
	io_ctl_drop_pages(&io_ctl);
769
	merge_space_tree(ctl);
770 771
	ret = 1;
out:
772
	io_ctl_free(&io_ctl);
773 774
	return ret;
free_cache:
775
	io_ctl_drop_pages(&io_ctl);
776
	__btrfs_remove_free_space_cache(ctl);
777 778 779
	goto out;
}

780 781
int load_free_space_cache(struct btrfs_fs_info *fs_info,
			  struct btrfs_block_group_cache *block_group)
J
Josef Bacik 已提交
782
{
783
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
784 785 786
	struct btrfs_root *root = fs_info->tree_root;
	struct inode *inode;
	struct btrfs_path *path;
787
	int ret = 0;
788 789 790 791 792 793 794
	bool matched;
	u64 used = btrfs_block_group_used(&block_group->item);

	/*
	 * If this block group has been marked to be cleared for one reason or
	 * another then we can't trust the on disk cache, so just return.
	 */
795
	spin_lock(&block_group->lock);
796 797 798 799
	if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
		spin_unlock(&block_group->lock);
		return 0;
	}
800
	spin_unlock(&block_group->lock);
801 802 803 804

	path = btrfs_alloc_path();
	if (!path)
		return 0;
805 806
	path->search_commit_root = 1;
	path->skip_locking = 1;
807 808 809 810 811 812 813

	inode = lookup_free_space_inode(root, block_group, path);
	if (IS_ERR(inode)) {
		btrfs_free_path(path);
		return 0;
	}

814 815 816 817
	/* We may have converted the inode and made the cache invalid. */
	spin_lock(&block_group->lock);
	if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
		spin_unlock(&block_group->lock);
818
		btrfs_free_path(path);
819 820 821 822
		goto out;
	}
	spin_unlock(&block_group->lock);

823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845
	ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,
				      path, block_group->key.objectid);
	btrfs_free_path(path);
	if (ret <= 0)
		goto out;

	spin_lock(&ctl->tree_lock);
	matched = (ctl->free_space == (block_group->key.offset - used -
				       block_group->bytes_super));
	spin_unlock(&ctl->tree_lock);

	if (!matched) {
		__btrfs_remove_free_space_cache(ctl);
		printk(KERN_ERR "block group %llu has an wrong amount of free "
		       "space\n", block_group->key.objectid);
		ret = -1;
	}
out:
	if (ret < 0) {
		/* This cache is bogus, make sure it gets cleared */
		spin_lock(&block_group->lock);
		block_group->disk_cache_state = BTRFS_DC_CLEAR;
		spin_unlock(&block_group->lock);
846
		ret = 0;
847 848 849 850 851 852 853

		printk(KERN_ERR "btrfs: failed to load free space cache "
		       "for block group %llu\n", block_group->key.objectid);
	}

	iput(inode);
	return ret;
854 855
}

856 857 858 859 860 861 862 863 864 865 866 867 868
/**
 * __btrfs_write_out_cache - write out cached info to an inode
 * @root - the root the inode belongs to
 * @ctl - the free space cache we are going to write out
 * @block_group - the block_group for this cache if it belongs to a block_group
 * @trans - the trans handle
 * @path - the path to use
 * @offset - the offset for the key we'll insert
 *
 * This function writes out a free space cache struct to disk for quick recovery
 * on mount.  This will return 0 if it was successfull in writing the cache out,
 * and -1 if it was not.
 */
869 870 871 872 873
int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
			    struct btrfs_free_space_ctl *ctl,
			    struct btrfs_block_group_cache *block_group,
			    struct btrfs_trans_handle *trans,
			    struct btrfs_path *path, u64 offset)
J
Josef Bacik 已提交
874 875 876 877 878 879
{
	struct btrfs_free_space_header *header;
	struct extent_buffer *leaf;
	struct rb_node *node;
	struct list_head *pos, *n;
	struct extent_state *cached_state = NULL;
880 881
	struct btrfs_free_cluster *cluster = NULL;
	struct extent_io_tree *unpin = NULL;
882
	struct io_ctl io_ctl;
J
Josef Bacik 已提交
883 884
	struct list_head bitmap_list;
	struct btrfs_key key;
885
	u64 start, extent_start, extent_end, len;
J
Josef Bacik 已提交
886 887
	int entries = 0;
	int bitmaps = 0;
888 889
	int ret;
	int err = -1;
J
Josef Bacik 已提交
890 891 892

	INIT_LIST_HEAD(&bitmap_list);

893 894
	if (!i_size_read(inode))
		return -1;
895

896 897 898
	ret = io_ctl_init(&io_ctl, inode, root);
	if (ret)
		return -1;
899

900
	/* Get the cluster for this block_group if it exists */
901
	if (block_group && !list_empty(&block_group->cluster_list))
902 903 904 905
		cluster = list_entry(block_group->cluster_list.next,
				     struct btrfs_free_cluster,
				     block_group_list);

906 907
	/* Lock all pages first so we can lock the extent safely. */
	io_ctl_prepare_pages(&io_ctl, inode, 0);
J
Josef Bacik 已提交
908 909

	lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,
910
			 0, &cached_state);
J
Josef Bacik 已提交
911

912 913 914 915 916 917
	node = rb_first(&ctl->free_space_offset);
	if (!node && cluster) {
		node = rb_first(&cluster->root);
		cluster = NULL;
	}

918 919 920 921 922 923 924
	/* Make sure we can fit our crcs into the first page */
	if (io_ctl.check_crcs &&
	    (io_ctl.num_pages * sizeof(u32)) >= PAGE_CACHE_SIZE) {
		WARN_ON(1);
		goto out_nospc;
	}

925
	io_ctl_set_generation(&io_ctl, trans->transid);
926

927 928 929
	/* Write out the extent entries */
	while (node) {
		struct btrfs_free_space *e;
J
Josef Bacik 已提交
930

931 932
		e = rb_entry(node, struct btrfs_free_space, offset_index);
		entries++;
J
Josef Bacik 已提交
933

934 935 936 937
		ret = io_ctl_add_entry(&io_ctl, e->offset, e->bytes,
				       e->bitmap);
		if (ret)
			goto out_nospc;
938

939 940 941
		if (e->bitmap) {
			list_add_tail(&e->list, &bitmap_list);
			bitmaps++;
942
		}
943 944 945 946
		node = rb_next(node);
		if (!node && cluster) {
			node = rb_first(&cluster->root);
			cluster = NULL;
947
		}
948
	}
949

950 951 952 953
	/*
	 * We want to add any pinned extents to our free space cache
	 * so we don't leak the space
	 */
954 955 956 957 958 959 960 961 962 963

	/*
	 * We shouldn't have switched the pinned extents yet so this is the
	 * right one
	 */
	unpin = root->fs_info->pinned_extents;

	if (block_group)
		start = block_group->key.objectid;

964 965
	while (block_group && (start < block_group->key.objectid +
			       block_group->key.offset)) {
966 967
		ret = find_first_extent_bit(unpin, start,
					    &extent_start, &extent_end,
968
					    EXTENT_DIRTY, NULL);
969 970 971
		if (ret) {
			ret = 0;
			break;
J
Josef Bacik 已提交
972 973
		}

974
		/* This pinned extent is out of our range */
975
		if (extent_start >= block_group->key.objectid +
976 977
		    block_group->key.offset)
			break;
978

979 980 981 982
		extent_start = max(extent_start, start);
		extent_end = min(block_group->key.objectid +
				 block_group->key.offset, extent_end + 1);
		len = extent_end - extent_start;
J
Josef Bacik 已提交
983

984
		entries++;
985
		ret = io_ctl_add_entry(&io_ctl, extent_start, len, NULL);
986 987
		if (ret)
			goto out_nospc;
J
Josef Bacik 已提交
988

989
		start = extent_end;
990
	}
J
Josef Bacik 已提交
991 992 993 994 995 996

	/* Write out the bitmaps */
	list_for_each_safe(pos, n, &bitmap_list) {
		struct btrfs_free_space *entry =
			list_entry(pos, struct btrfs_free_space, list);

997 998 999
		ret = io_ctl_add_bitmap(&io_ctl, entry->bitmap);
		if (ret)
			goto out_nospc;
J
Josef Bacik 已提交
1000
		list_del_init(&entry->list);
1001 1002
	}

J
Josef Bacik 已提交
1003
	/* Zero out the rest of the pages just to make sure */
1004
	io_ctl_zero_remaining_pages(&io_ctl);
J
Josef Bacik 已提交
1005

1006 1007 1008
	ret = btrfs_dirty_pages(root, inode, io_ctl.pages, io_ctl.num_pages,
				0, i_size_read(inode), &cached_state);
	io_ctl_drop_pages(&io_ctl);
J
Josef Bacik 已提交
1009 1010 1011
	unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
			     i_size_read(inode) - 1, &cached_state, GFP_NOFS);

1012
	if (ret)
1013
		goto out;
1014 1015


1016
	btrfs_wait_ordered_range(inode, 0, (u64)-1);
J
Josef Bacik 已提交
1017 1018

	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
1019
	key.offset = offset;
J
Josef Bacik 已提交
1020 1021
	key.type = 0;

1022
	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
J
Josef Bacik 已提交
1023
	if (ret < 0) {
1024
		clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
1025 1026
				 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL,
				 GFP_NOFS);
1027
		goto out;
J
Josef Bacik 已提交
1028 1029 1030 1031 1032 1033 1034 1035
	}
	leaf = path->nodes[0];
	if (ret > 0) {
		struct btrfs_key found_key;
		BUG_ON(!path->slots[0]);
		path->slots[0]--;
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||
1036
		    found_key.offset != offset) {
1037 1038
			clear_extent_bit(&BTRFS_I(inode)->io_tree, 0,
					 inode->i_size - 1,
1039 1040
					 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0,
					 NULL, GFP_NOFS);
1041
			btrfs_release_path(path);
1042
			goto out;
J
Josef Bacik 已提交
1043 1044
		}
	}
1045 1046

	BTRFS_I(inode)->generation = trans->transid;
J
Josef Bacik 已提交
1047 1048 1049 1050 1051 1052
	header = btrfs_item_ptr(leaf, path->slots[0],
				struct btrfs_free_space_header);
	btrfs_set_free_space_entries(leaf, header, entries);
	btrfs_set_free_space_bitmaps(leaf, header, bitmaps);
	btrfs_set_free_space_generation(leaf, header, trans->transid);
	btrfs_mark_buffer_dirty(leaf);
1053
	btrfs_release_path(path);
J
Josef Bacik 已提交
1054

1055
	err = 0;
1056
out:
1057
	io_ctl_free(&io_ctl);
1058
	if (err) {
1059
		invalidate_inode_pages2(inode->i_mapping);
J
Josef Bacik 已提交
1060 1061 1062
		BTRFS_I(inode)->generation = 0;
	}
	btrfs_update_inode(trans, root, inode);
1063
	return err;
1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074

out_nospc:
	list_for_each_safe(pos, n, &bitmap_list) {
		struct btrfs_free_space *entry =
			list_entry(pos, struct btrfs_free_space, list);
		list_del_init(&entry->list);
	}
	io_ctl_drop_pages(&io_ctl);
	unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
			     i_size_read(inode) - 1, &cached_state, GFP_NOFS);
	goto out;
1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100
}

int btrfs_write_out_cache(struct btrfs_root *root,
			  struct btrfs_trans_handle *trans,
			  struct btrfs_block_group_cache *block_group,
			  struct btrfs_path *path)
{
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
	struct inode *inode;
	int ret = 0;

	root = root->fs_info->tree_root;

	spin_lock(&block_group->lock);
	if (block_group->disk_cache_state < BTRFS_DC_SETUP) {
		spin_unlock(&block_group->lock);
		return 0;
	}
	spin_unlock(&block_group->lock);

	inode = lookup_free_space_inode(root, block_group, path);
	if (IS_ERR(inode))
		return 0;

	ret = __btrfs_write_out_cache(root, inode, ctl, block_group, trans,
				      path, block_group->key.objectid);
1101
	if (ret) {
1102 1103 1104
		spin_lock(&block_group->lock);
		block_group->disk_cache_state = BTRFS_DC_ERROR;
		spin_unlock(&block_group->lock);
1105
		ret = 0;
1106
#ifdef DEBUG
1107
		printk(KERN_ERR "btrfs: failed to write free space cache "
1108
		       "for block group %llu\n", block_group->key.objectid);
1109
#endif
1110 1111
	}

J
Josef Bacik 已提交
1112 1113 1114 1115
	iput(inode);
	return ret;
}

1116
static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
1117
					  u64 offset)
J
Josef Bacik 已提交
1118
{
1119 1120
	BUG_ON(offset < bitmap_start);
	offset -= bitmap_start;
1121
	return (unsigned long)(div_u64(offset, unit));
1122
}
J
Josef Bacik 已提交
1123

1124
static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
1125
{
1126
	return (unsigned long)(div_u64(bytes, unit));
1127
}
J
Josef Bacik 已提交
1128

1129
static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
1130 1131 1132 1133
				   u64 offset)
{
	u64 bitmap_start;
	u64 bytes_per_bitmap;
J
Josef Bacik 已提交
1134

1135 1136
	bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
	bitmap_start = offset - ctl->start;
1137 1138
	bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
	bitmap_start *= bytes_per_bitmap;
1139
	bitmap_start += ctl->start;
J
Josef Bacik 已提交
1140

1141
	return bitmap_start;
J
Josef Bacik 已提交
1142 1143
}

1144 1145
static int tree_insert_offset(struct rb_root *root, u64 offset,
			      struct rb_node *node, int bitmap)
J
Josef Bacik 已提交
1146 1147 1148 1149 1150 1151 1152
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct btrfs_free_space *info;

	while (*p) {
		parent = *p;
1153
		info = rb_entry(parent, struct btrfs_free_space, offset_index);
J
Josef Bacik 已提交
1154

1155
		if (offset < info->offset) {
J
Josef Bacik 已提交
1156
			p = &(*p)->rb_left;
1157
		} else if (offset > info->offset) {
J
Josef Bacik 已提交
1158
			p = &(*p)->rb_right;
1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173
		} else {
			/*
			 * we could have a bitmap entry and an extent entry
			 * share the same offset.  If this is the case, we want
			 * the extent entry to always be found first if we do a
			 * linear search through the tree, since we want to have
			 * the quickest allocation time, and allocating from an
			 * extent is faster than allocating from a bitmap.  So
			 * if we're inserting a bitmap and we find an entry at
			 * this offset, we want to go right, or after this entry
			 * logically.  If we are inserting an extent and we've
			 * found a bitmap, we want to go left, or before
			 * logically.
			 */
			if (bitmap) {
1174 1175 1176 1177
				if (info->bitmap) {
					WARN_ON_ONCE(1);
					return -EEXIST;
				}
1178 1179
				p = &(*p)->rb_right;
			} else {
1180 1181 1182 1183
				if (!info->bitmap) {
					WARN_ON_ONCE(1);
					return -EEXIST;
				}
1184 1185 1186
				p = &(*p)->rb_left;
			}
		}
J
Josef Bacik 已提交
1187 1188 1189 1190 1191 1192 1193 1194 1195
	}

	rb_link_node(node, parent, p);
	rb_insert_color(node, root);

	return 0;
}

/*
J
Josef Bacik 已提交
1196 1197
 * searches the tree for the given offset.
 *
1198 1199 1200
 * fuzzy - If this is set, then we are trying to make an allocation, and we just
 * want a section that has at least bytes size and comes at or after the given
 * offset.
J
Josef Bacik 已提交
1201
 */
1202
static struct btrfs_free_space *
1203
tree_search_offset(struct btrfs_free_space_ctl *ctl,
1204
		   u64 offset, int bitmap_only, int fuzzy)
J
Josef Bacik 已提交
1205
{
1206
	struct rb_node *n = ctl->free_space_offset.rb_node;
1207 1208 1209 1210 1211 1212 1213 1214
	struct btrfs_free_space *entry, *prev = NULL;

	/* find entry that is closest to the 'offset' */
	while (1) {
		if (!n) {
			entry = NULL;
			break;
		}
J
Josef Bacik 已提交
1215 1216

		entry = rb_entry(n, struct btrfs_free_space, offset_index);
1217
		prev = entry;
J
Josef Bacik 已提交
1218

1219
		if (offset < entry->offset)
J
Josef Bacik 已提交
1220
			n = n->rb_left;
1221
		else if (offset > entry->offset)
J
Josef Bacik 已提交
1222
			n = n->rb_right;
1223
		else
J
Josef Bacik 已提交
1224 1225 1226
			break;
	}

1227 1228 1229 1230 1231
	if (bitmap_only) {
		if (!entry)
			return NULL;
		if (entry->bitmap)
			return entry;
J
Josef Bacik 已提交
1232

1233 1234 1235 1236 1237 1238 1239 1240 1241 1242
		/*
		 * bitmap entry and extent entry may share same offset,
		 * in that case, bitmap entry comes after extent entry.
		 */
		n = rb_next(n);
		if (!n)
			return NULL;
		entry = rb_entry(n, struct btrfs_free_space, offset_index);
		if (entry->offset != offset)
			return NULL;
J
Josef Bacik 已提交
1243

1244 1245 1246 1247
		WARN_ON(!entry->bitmap);
		return entry;
	} else if (entry) {
		if (entry->bitmap) {
J
Josef Bacik 已提交
1248
			/*
1249 1250
			 * if previous extent entry covers the offset,
			 * we should return it instead of the bitmap entry
J
Josef Bacik 已提交
1251
			 */
1252 1253
			n = rb_prev(&entry->offset_index);
			if (n) {
1254 1255
				prev = rb_entry(n, struct btrfs_free_space,
						offset_index);
1256 1257 1258
				if (!prev->bitmap &&
				    prev->offset + prev->bytes > offset)
					entry = prev;
J
Josef Bacik 已提交
1259
			}
1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274
		}
		return entry;
	}

	if (!prev)
		return NULL;

	/* find last entry before the 'offset' */
	entry = prev;
	if (entry->offset > offset) {
		n = rb_prev(&entry->offset_index);
		if (n) {
			entry = rb_entry(n, struct btrfs_free_space,
					offset_index);
			BUG_ON(entry->offset > offset);
J
Josef Bacik 已提交
1275
		} else {
1276 1277 1278 1279
			if (fuzzy)
				return entry;
			else
				return NULL;
J
Josef Bacik 已提交
1280 1281 1282
		}
	}

1283
	if (entry->bitmap) {
1284 1285
		n = rb_prev(&entry->offset_index);
		if (n) {
1286 1287
			prev = rb_entry(n, struct btrfs_free_space,
					offset_index);
1288 1289 1290
			if (!prev->bitmap &&
			    prev->offset + prev->bytes > offset)
				return prev;
1291
		}
1292
		if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
1293 1294 1295 1296 1297 1298 1299 1300 1301 1302
			return entry;
	} else if (entry->offset + entry->bytes > offset)
		return entry;

	if (!fuzzy)
		return NULL;

	while (1) {
		if (entry->bitmap) {
			if (entry->offset + BITS_PER_BITMAP *
1303
			    ctl->unit > offset)
1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315
				break;
		} else {
			if (entry->offset + entry->bytes > offset)
				break;
		}

		n = rb_next(&entry->offset_index);
		if (!n)
			return NULL;
		entry = rb_entry(n, struct btrfs_free_space, offset_index);
	}
	return entry;
J
Josef Bacik 已提交
1316 1317
}

1318
static inline void
1319
__unlink_free_space(struct btrfs_free_space_ctl *ctl,
1320
		    struct btrfs_free_space *info)
J
Josef Bacik 已提交
1321
{
1322 1323
	rb_erase(&info->offset_index, &ctl->free_space_offset);
	ctl->free_extents--;
1324 1325
}

1326
static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
1327 1328
			      struct btrfs_free_space *info)
{
1329 1330
	__unlink_free_space(ctl, info);
	ctl->free_space -= info->bytes;
J
Josef Bacik 已提交
1331 1332
}

1333
static int link_free_space(struct btrfs_free_space_ctl *ctl,
J
Josef Bacik 已提交
1334 1335 1336 1337
			   struct btrfs_free_space *info)
{
	int ret = 0;

1338
	BUG_ON(!info->bitmap && !info->bytes);
1339
	ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
1340
				 &info->offset_index, (info->bitmap != NULL));
J
Josef Bacik 已提交
1341 1342 1343
	if (ret)
		return ret;

1344 1345
	ctl->free_space += info->bytes;
	ctl->free_extents++;
1346 1347 1348
	return ret;
}

1349
static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
1350
{
1351
	struct btrfs_block_group_cache *block_group = ctl->private;
1352 1353 1354
	u64 max_bytes;
	u64 bitmap_bytes;
	u64 extent_bytes;
1355
	u64 size = block_group->key.offset;
1356
	u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;
1357 1358
	int max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);

1359 1360
	max_bitmaps = max(max_bitmaps, 1);

1361
	BUG_ON(ctl->total_bitmaps > max_bitmaps);
1362 1363 1364 1365 1366 1367

	/*
	 * The goal is to keep the total amount of memory used per 1gb of space
	 * at or below 32k, so we need to adjust how much memory we allow to be
	 * used by extent based free space tracking
	 */
1368 1369 1370 1371 1372
	if (size < 1024 * 1024 * 1024)
		max_bytes = MAX_CACHE_BYTES_PER_GIG;
	else
		max_bytes = MAX_CACHE_BYTES_PER_GIG *
			div64_u64(size, 1024 * 1024 * 1024);
1373

1374 1375 1376 1377 1378
	/*
	 * we want to account for 1 more bitmap than what we have so we can make
	 * sure we don't go over our overall goal of MAX_CACHE_BYTES_PER_GIG as
	 * we add more bitmaps.
	 */
1379
	bitmap_bytes = (ctl->total_bitmaps + 1) * PAGE_CACHE_SIZE;
1380

1381
	if (bitmap_bytes >= max_bytes) {
1382
		ctl->extents_thresh = 0;
1383 1384
		return;
	}
1385

1386 1387 1388 1389 1390 1391
	/*
	 * we want the extent entry threshold to always be at most 1/2 the maxw
	 * bytes we can have, or whatever is less than that.
	 */
	extent_bytes = max_bytes - bitmap_bytes;
	extent_bytes = min_t(u64, extent_bytes, div64_u64(max_bytes, 2));
1392

1393
	ctl->extents_thresh =
1394
		div64_u64(extent_bytes, (sizeof(struct btrfs_free_space)));
1395 1396
}

1397 1398 1399
static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
				       struct btrfs_free_space *info,
				       u64 offset, u64 bytes)
1400
{
L
Li Zefan 已提交
1401
	unsigned long start, count;
1402

1403 1404
	start = offset_to_bit(info->offset, ctl->unit, offset);
	count = bytes_to_bits(bytes, ctl->unit);
L
Li Zefan 已提交
1405
	BUG_ON(start + count > BITS_PER_BITMAP);
1406

L
Li Zefan 已提交
1407
	bitmap_clear(info->bitmap, start, count);
1408 1409

	info->bytes -= bytes;
1410 1411 1412 1413 1414 1415 1416
}

static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
			      struct btrfs_free_space *info, u64 offset,
			      u64 bytes)
{
	__bitmap_clear_bits(ctl, info, offset, bytes);
1417
	ctl->free_space -= bytes;
1418 1419
}

1420
static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
J
Josef Bacik 已提交
1421 1422
			    struct btrfs_free_space *info, u64 offset,
			    u64 bytes)
1423
{
L
Li Zefan 已提交
1424
	unsigned long start, count;
1425

1426 1427
	start = offset_to_bit(info->offset, ctl->unit, offset);
	count = bytes_to_bits(bytes, ctl->unit);
L
Li Zefan 已提交
1428
	BUG_ON(start + count > BITS_PER_BITMAP);
1429

L
Li Zefan 已提交
1430
	bitmap_set(info->bitmap, start, count);
1431 1432

	info->bytes += bytes;
1433
	ctl->free_space += bytes;
1434 1435
}

1436
static int search_bitmap(struct btrfs_free_space_ctl *ctl,
1437 1438 1439 1440 1441 1442 1443
			 struct btrfs_free_space *bitmap_info, u64 *offset,
			 u64 *bytes)
{
	unsigned long found_bits = 0;
	unsigned long bits, i;
	unsigned long next_zero;

1444
	i = offset_to_bit(bitmap_info->offset, ctl->unit,
1445
			  max_t(u64, *offset, bitmap_info->offset));
1446
	bits = bytes_to_bits(*bytes, ctl->unit);
1447

1448
	for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
1449 1450 1451 1452 1453 1454 1455 1456 1457 1458
		next_zero = find_next_zero_bit(bitmap_info->bitmap,
					       BITS_PER_BITMAP, i);
		if ((next_zero - i) >= bits) {
			found_bits = next_zero - i;
			break;
		}
		i = next_zero;
	}

	if (found_bits) {
1459 1460
		*offset = (u64)(i * ctl->unit) + bitmap_info->offset;
		*bytes = (u64)(found_bits) * ctl->unit;
1461 1462 1463 1464 1465 1466
		return 0;
	}

	return -1;
}

1467
static struct btrfs_free_space *
D
David Woodhouse 已提交
1468 1469
find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
		unsigned long align)
1470 1471 1472
{
	struct btrfs_free_space *entry;
	struct rb_node *node;
D
David Woodhouse 已提交
1473 1474 1475
	u64 ctl_off;
	u64 tmp;
	u64 align_off;
1476 1477
	int ret;

1478
	if (!ctl->free_space_offset.rb_node)
1479 1480
		return NULL;

1481
	entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
1482 1483 1484 1485 1486 1487 1488 1489
	if (!entry)
		return NULL;

	for (node = &entry->offset_index; node; node = rb_next(node)) {
		entry = rb_entry(node, struct btrfs_free_space, offset_index);
		if (entry->bytes < *bytes)
			continue;

D
David Woodhouse 已提交
1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506
		/* make sure the space returned is big enough
		 * to match our requested alignment
		 */
		if (*bytes >= align) {
			ctl_off = entry->offset - ctl->start;
			tmp = ctl_off + align - 1;;
			do_div(tmp, align);
			tmp = tmp * align + ctl->start;
			align_off = tmp - entry->offset;
		} else {
			align_off = 0;
			tmp = entry->offset;
		}

		if (entry->bytes < *bytes + align_off)
			continue;

1507
		if (entry->bitmap) {
D
David Woodhouse 已提交
1508 1509 1510
			ret = search_bitmap(ctl, entry, &tmp, bytes);
			if (!ret) {
				*offset = tmp;
1511
				return entry;
D
David Woodhouse 已提交
1512
			}
1513 1514 1515
			continue;
		}

D
David Woodhouse 已提交
1516 1517
		*offset = tmp;
		*bytes = entry->bytes - align_off;
1518 1519 1520 1521 1522 1523
		return entry;
	}

	return NULL;
}

1524
static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
1525 1526
			   struct btrfs_free_space *info, u64 offset)
{
1527
	info->offset = offset_to_bitmap(ctl, offset);
J
Josef Bacik 已提交
1528
	info->bytes = 0;
1529
	INIT_LIST_HEAD(&info->list);
1530 1531
	link_free_space(ctl, info);
	ctl->total_bitmaps++;
1532

1533
	ctl->op->recalc_thresholds(ctl);
1534 1535
}

1536
static void free_bitmap(struct btrfs_free_space_ctl *ctl,
1537 1538
			struct btrfs_free_space *bitmap_info)
{
1539
	unlink_free_space(ctl, bitmap_info);
1540
	kfree(bitmap_info->bitmap);
1541
	kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
1542 1543
	ctl->total_bitmaps--;
	ctl->op->recalc_thresholds(ctl);
1544 1545
}

1546
static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
1547 1548 1549 1550
			      struct btrfs_free_space *bitmap_info,
			      u64 *offset, u64 *bytes)
{
	u64 end;
1551 1552
	u64 search_start, search_bytes;
	int ret;
1553 1554

again:
1555
	end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;
1556

1557
	/*
1558 1559 1560 1561
	 * We need to search for bits in this bitmap.  We could only cover some
	 * of the extent in this bitmap thanks to how we add space, so we need
	 * to search for as much as it as we can and clear that amount, and then
	 * go searching for the next bit.
1562 1563
	 */
	search_start = *offset;
1564
	search_bytes = ctl->unit;
1565
	search_bytes = min(search_bytes, end - search_start + 1);
1566
	ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes);
1567 1568
	BUG_ON(ret < 0 || search_start != *offset);

1569 1570 1571 1572 1573 1574 1575 1576 1577
	/* We may have found more bits than what we need */
	search_bytes = min(search_bytes, *bytes);

	/* Cannot clear past the end of the bitmap */
	search_bytes = min(search_bytes, end - search_start + 1);

	bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes);
	*offset += search_bytes;
	*bytes -= search_bytes;
1578 1579

	if (*bytes) {
1580
		struct rb_node *next = rb_next(&bitmap_info->offset_index);
1581
		if (!bitmap_info->bytes)
1582
			free_bitmap(ctl, bitmap_info);
1583

1584 1585 1586 1587 1588
		/*
		 * no entry after this bitmap, but we still have bytes to
		 * remove, so something has gone wrong.
		 */
		if (!next)
1589 1590
			return -EINVAL;

1591 1592 1593 1594 1595 1596 1597
		bitmap_info = rb_entry(next, struct btrfs_free_space,
				       offset_index);

		/*
		 * if the next entry isn't a bitmap we need to return to let the
		 * extent stuff do its work.
		 */
1598 1599 1600
		if (!bitmap_info->bitmap)
			return -EAGAIN;

1601 1602 1603 1604 1605 1606 1607
		/*
		 * Ok the next item is a bitmap, but it may not actually hold
		 * the information for the rest of this free space stuff, so
		 * look for it, and if we don't find it return so we can try
		 * everything over again.
		 */
		search_start = *offset;
1608
		search_bytes = ctl->unit;
1609
		ret = search_bitmap(ctl, bitmap_info, &search_start,
1610 1611 1612 1613
				    &search_bytes);
		if (ret < 0 || search_start != *offset)
			return -EAGAIN;

1614
		goto again;
1615
	} else if (!bitmap_info->bytes)
1616
		free_bitmap(ctl, bitmap_info);
1617 1618 1619 1620

	return 0;
}

J
Josef Bacik 已提交
1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637
static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
			       struct btrfs_free_space *info, u64 offset,
			       u64 bytes)
{
	u64 bytes_to_set = 0;
	u64 end;

	end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);

	bytes_to_set = min(end - offset, bytes);

	bitmap_set_bits(ctl, info, offset, bytes_to_set);

	return bytes_to_set;

}

1638 1639
static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
		      struct btrfs_free_space *info)
1640
{
1641
	struct btrfs_block_group_cache *block_group = ctl->private;
1642 1643 1644 1645 1646

	/*
	 * If we are below the extents threshold then we can add this as an
	 * extent, and don't have to deal with the bitmap
	 */
1647
	if (ctl->free_extents < ctl->extents_thresh) {
1648 1649 1650 1651 1652 1653 1654 1655
		/*
		 * If this block group has some small extents we don't want to
		 * use up all of our free slots in the cache with them, we want
		 * to reserve them to larger extents, however if we have plent
		 * of cache left then go ahead an dadd them, no sense in adding
		 * the overhead of a bitmap if we don't have to.
		 */
		if (info->bytes <= block_group->sectorsize * 4) {
1656 1657
			if (ctl->free_extents * 2 <= ctl->extents_thresh)
				return false;
1658
		} else {
1659
			return false;
1660 1661
		}
	}
1662 1663

	/*
1664 1665 1666 1667 1668 1669
	 * The original block groups from mkfs can be really small, like 8
	 * megabytes, so don't bother with a bitmap for those entries.  However
	 * some block groups can be smaller than what a bitmap would cover but
	 * are still large enough that they could overflow the 32k memory limit,
	 * so allow those block groups to still be allowed to have a bitmap
	 * entry.
1670
	 */
1671
	if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->key.offset)
1672 1673 1674 1675 1676
		return false;

	return true;
}

J
Josef Bacik 已提交
1677 1678 1679 1680 1681
static struct btrfs_free_space_op free_space_op = {
	.recalc_thresholds	= recalculate_thresholds,
	.use_bitmap		= use_bitmap,
};

1682 1683 1684 1685
static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
			      struct btrfs_free_space *info)
{
	struct btrfs_free_space *bitmap_info;
J
Josef Bacik 已提交
1686
	struct btrfs_block_group_cache *block_group = NULL;
1687
	int added = 0;
J
Josef Bacik 已提交
1688
	u64 bytes, offset, bytes_added;
1689
	int ret;
1690 1691 1692 1693

	bytes = info->bytes;
	offset = info->offset;

1694 1695 1696
	if (!ctl->op->use_bitmap(ctl, info))
		return 0;

J
Josef Bacik 已提交
1697 1698
	if (ctl->op == &free_space_op)
		block_group = ctl->private;
1699
again:
J
Josef Bacik 已提交
1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716
	/*
	 * Since we link bitmaps right into the cluster we need to see if we
	 * have a cluster here, and if so and it has our bitmap we need to add
	 * the free space to that bitmap.
	 */
	if (block_group && !list_empty(&block_group->cluster_list)) {
		struct btrfs_free_cluster *cluster;
		struct rb_node *node;
		struct btrfs_free_space *entry;

		cluster = list_entry(block_group->cluster_list.next,
				     struct btrfs_free_cluster,
				     block_group_list);
		spin_lock(&cluster->lock);
		node = rb_first(&cluster->root);
		if (!node) {
			spin_unlock(&cluster->lock);
1717
			goto no_cluster_bitmap;
J
Josef Bacik 已提交
1718 1719 1720 1721 1722
		}

		entry = rb_entry(node, struct btrfs_free_space, offset_index);
		if (!entry->bitmap) {
			spin_unlock(&cluster->lock);
1723
			goto no_cluster_bitmap;
J
Josef Bacik 已提交
1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737
		}

		if (entry->offset == offset_to_bitmap(ctl, offset)) {
			bytes_added = add_bytes_to_bitmap(ctl, entry,
							  offset, bytes);
			bytes -= bytes_added;
			offset += bytes_added;
		}
		spin_unlock(&cluster->lock);
		if (!bytes) {
			ret = 1;
			goto out;
		}
	}
1738 1739

no_cluster_bitmap:
1740
	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1741 1742 1743 1744 1745 1746
					 1, 0);
	if (!bitmap_info) {
		BUG_ON(added);
		goto new_bitmap;
	}

J
Josef Bacik 已提交
1747 1748 1749 1750
	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
	bytes -= bytes_added;
	offset += bytes_added;
	added = 0;
1751 1752 1753 1754 1755 1756 1757 1758 1759

	if (!bytes) {
		ret = 1;
		goto out;
	} else
		goto again;

new_bitmap:
	if (info && info->bitmap) {
1760
		add_new_bitmap(ctl, info, offset);
1761 1762 1763 1764
		added = 1;
		info = NULL;
		goto again;
	} else {
1765
		spin_unlock(&ctl->tree_lock);
1766 1767 1768

		/* no pre-allocated info, allocate a new one */
		if (!info) {
1769 1770
			info = kmem_cache_zalloc(btrfs_free_space_cachep,
						 GFP_NOFS);
1771
			if (!info) {
1772
				spin_lock(&ctl->tree_lock);
1773 1774 1775 1776 1777 1778 1779
				ret = -ENOMEM;
				goto out;
			}
		}

		/* allocate the bitmap */
		info->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
1780
		spin_lock(&ctl->tree_lock);
1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791
		if (!info->bitmap) {
			ret = -ENOMEM;
			goto out;
		}
		goto again;
	}

out:
	if (info) {
		if (info->bitmap)
			kfree(info->bitmap);
1792
		kmem_cache_free(btrfs_free_space_cachep, info);
1793
	}
J
Josef Bacik 已提交
1794 1795 1796 1797

	return ret;
}

1798
static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
1799
			  struct btrfs_free_space *info, bool update_stat)
J
Josef Bacik 已提交
1800
{
1801 1802 1803 1804 1805
	struct btrfs_free_space *left_info;
	struct btrfs_free_space *right_info;
	bool merged = false;
	u64 offset = info->offset;
	u64 bytes = info->bytes;
1806

J
Josef Bacik 已提交
1807 1808 1809 1810 1811
	/*
	 * first we want to see if there is free space adjacent to the range we
	 * are adding, if there is remove that struct and add a new one to
	 * cover the entire range
	 */
1812
	right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
1813 1814 1815 1816
	if (right_info && rb_prev(&right_info->offset_index))
		left_info = rb_entry(rb_prev(&right_info->offset_index),
				     struct btrfs_free_space, offset_index);
	else
1817
		left_info = tree_search_offset(ctl, offset - 1, 0, 0);
J
Josef Bacik 已提交
1818

1819
	if (right_info && !right_info->bitmap) {
1820
		if (update_stat)
1821
			unlink_free_space(ctl, right_info);
1822
		else
1823
			__unlink_free_space(ctl, right_info);
1824
		info->bytes += right_info->bytes;
1825
		kmem_cache_free(btrfs_free_space_cachep, right_info);
1826
		merged = true;
J
Josef Bacik 已提交
1827 1828
	}

1829 1830
	if (left_info && !left_info->bitmap &&
	    left_info->offset + left_info->bytes == offset) {
1831
		if (update_stat)
1832
			unlink_free_space(ctl, left_info);
1833
		else
1834
			__unlink_free_space(ctl, left_info);
1835 1836
		info->offset = left_info->offset;
		info->bytes += left_info->bytes;
1837
		kmem_cache_free(btrfs_free_space_cachep, left_info);
1838
		merged = true;
J
Josef Bacik 已提交
1839 1840
	}

1841 1842 1843
	return merged;
}

1844 1845
int __btrfs_add_free_space(struct btrfs_free_space_ctl *ctl,
			   u64 offset, u64 bytes)
1846 1847 1848 1849
{
	struct btrfs_free_space *info;
	int ret = 0;

1850
	info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
1851 1852 1853 1854 1855 1856
	if (!info)
		return -ENOMEM;

	info->offset = offset;
	info->bytes = bytes;

1857
	spin_lock(&ctl->tree_lock);
1858

1859
	if (try_merge_free_space(ctl, info, true))
1860 1861 1862 1863 1864 1865 1866
		goto link;

	/*
	 * There was no extent directly to the left or right of this new
	 * extent then we know we're going to have to allocate a new extent, so
	 * before we do that see if we need to drop this into a bitmap
	 */
1867
	ret = insert_into_bitmap(ctl, info);
1868 1869 1870 1871 1872 1873 1874
	if (ret < 0) {
		goto out;
	} else if (ret) {
		ret = 0;
		goto out;
	}
link:
1875
	ret = link_free_space(ctl, info);
J
Josef Bacik 已提交
1876
	if (ret)
1877
		kmem_cache_free(btrfs_free_space_cachep, info);
1878
out:
1879
	spin_unlock(&ctl->tree_lock);
1880

J
Josef Bacik 已提交
1881
	if (ret) {
1882
		printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
S
Stoyan Gaydarov 已提交
1883
		BUG_ON(ret == -EEXIST);
J
Josef Bacik 已提交
1884 1885 1886 1887 1888
	}

	return ret;
}

1889 1890
int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
			    u64 offset, u64 bytes)
J
Josef Bacik 已提交
1891
{
1892
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
J
Josef Bacik 已提交
1893
	struct btrfs_free_space *info;
1894 1895
	int ret;
	bool re_search = false;
J
Josef Bacik 已提交
1896

1897
	spin_lock(&ctl->tree_lock);
1898

1899
again:
1900
	ret = 0;
1901 1902 1903
	if (!bytes)
		goto out_lock;

1904
	info = tree_search_offset(ctl, offset, 0, 0);
1905
	if (!info) {
1906 1907 1908 1909
		/*
		 * oops didn't find an extent that matched the space we wanted
		 * to remove, look for a bitmap instead
		 */
1910
		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1911 1912
					  1, 0);
		if (!info) {
1913 1914 1915 1916
			/*
			 * If we found a partial bit of our free space in a
			 * bitmap but then couldn't find the other part this may
			 * be a problem, so WARN about it.
1917
			 */
1918
			WARN_ON(re_search);
1919 1920
			goto out_lock;
		}
1921 1922
	}

1923
	re_search = false;
1924
	if (!info->bitmap) {
1925
		unlink_free_space(ctl, info);
1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936
		if (offset == info->offset) {
			u64 to_free = min(bytes, info->bytes);

			info->bytes -= to_free;
			info->offset += to_free;
			if (info->bytes) {
				ret = link_free_space(ctl, info);
				WARN_ON(ret);
			} else {
				kmem_cache_free(btrfs_free_space_cachep, info);
			}
J
Josef Bacik 已提交
1937

1938 1939 1940 1941 1942
			offset += to_free;
			bytes -= to_free;
			goto again;
		} else {
			u64 old_end = info->bytes + info->offset;
1943

1944
			info->bytes = offset - info->offset;
1945
			ret = link_free_space(ctl, info);
1946 1947 1948 1949
			WARN_ON(ret);
			if (ret)
				goto out_lock;

1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965
			/* Not enough bytes in this entry to satisfy us */
			if (old_end < offset + bytes) {
				bytes -= old_end - offset;
				offset = old_end;
				goto again;
			} else if (old_end == offset + bytes) {
				/* all done */
				goto out_lock;
			}
			spin_unlock(&ctl->tree_lock);

			ret = btrfs_add_free_space(block_group, offset + bytes,
						   old_end - (offset + bytes));
			WARN_ON(ret);
			goto out;
		}
J
Josef Bacik 已提交
1966
	}
1967

1968
	ret = remove_from_bitmap(ctl, info, &offset, &bytes);
1969 1970
	if (ret == -EAGAIN) {
		re_search = true;
1971
		goto again;
1972
	}
1973
	BUG_ON(ret); /* logic error */
1974
out_lock:
1975
	spin_unlock(&ctl->tree_lock);
J
Josef Bacik 已提交
1976
out:
1977 1978 1979
	return ret;
}

J
Josef Bacik 已提交
1980 1981 1982
void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
			   u64 bytes)
{
1983
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
J
Josef Bacik 已提交
1984 1985 1986 1987
	struct btrfs_free_space *info;
	struct rb_node *n;
	int count = 0;

1988
	for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
J
Josef Bacik 已提交
1989
		info = rb_entry(n, struct btrfs_free_space, offset_index);
L
Liu Bo 已提交
1990
		if (info->bytes >= bytes && !block_group->ro)
J
Josef Bacik 已提交
1991
			count++;
1992
		printk(KERN_CRIT "entry offset %llu, bytes %llu, bitmap %s\n",
1993
		       (unsigned long long)info->offset,
1994 1995
		       (unsigned long long)info->bytes,
		       (info->bitmap) ? "yes" : "no");
J
Josef Bacik 已提交
1996
	}
1997 1998
	printk(KERN_INFO "block group has cluster?: %s\n",
	       list_empty(&block_group->cluster_list) ? "no" : "yes");
J
Josef Bacik 已提交
1999 2000 2001 2002
	printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
	       "\n", count);
}

2003
void btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group)
J
Josef Bacik 已提交
2004
{
2005
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
J
Josef Bacik 已提交
2006

2007 2008 2009 2010 2011
	spin_lock_init(&ctl->tree_lock);
	ctl->unit = block_group->sectorsize;
	ctl->start = block_group->key.objectid;
	ctl->private = block_group;
	ctl->op = &free_space_op;
J
Josef Bacik 已提交
2012

2013 2014 2015 2016 2017 2018 2019
	/*
	 * we only want to have 32k of ram per block group for keeping
	 * track of free space, and if we pass 1/2 of that we want to
	 * start converting things over to using bitmaps
	 */
	ctl->extents_thresh = ((1024 * 32) / 2) /
				sizeof(struct btrfs_free_space);
J
Josef Bacik 已提交
2020 2021
}

2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032
/*
 * for a given cluster, put all of its extents back into the free
 * space cache.  If the block group passed doesn't match the block group
 * pointed to by the cluster, someone else raced in and freed the
 * cluster already.  In that case, we just return without changing anything
 */
static int
__btrfs_return_cluster_to_free_space(
			     struct btrfs_block_group_cache *block_group,
			     struct btrfs_free_cluster *cluster)
{
2033
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2034 2035 2036 2037 2038 2039 2040
	struct btrfs_free_space *entry;
	struct rb_node *node;

	spin_lock(&cluster->lock);
	if (cluster->block_group != block_group)
		goto out;

2041
	cluster->block_group = NULL;
2042
	cluster->window_start = 0;
2043 2044
	list_del_init(&cluster->block_group_list);

2045
	node = rb_first(&cluster->root);
2046
	while (node) {
2047 2048
		bool bitmap;

2049 2050 2051
		entry = rb_entry(node, struct btrfs_free_space, offset_index);
		node = rb_next(&entry->offset_index);
		rb_erase(&entry->offset_index, &cluster->root);
2052 2053 2054

		bitmap = (entry->bitmap != NULL);
		if (!bitmap)
2055 2056
			try_merge_free_space(ctl, entry, false);
		tree_insert_offset(&ctl->free_space_offset,
2057
				   entry->offset, &entry->offset_index, bitmap);
2058
	}
2059
	cluster->root = RB_ROOT;
2060

2061 2062
out:
	spin_unlock(&cluster->lock);
2063
	btrfs_put_block_group(block_group);
2064 2065 2066
	return 0;
}

2067
void __btrfs_remove_free_space_cache_locked(struct btrfs_free_space_ctl *ctl)
J
Josef Bacik 已提交
2068 2069 2070
{
	struct btrfs_free_space *info;
	struct rb_node *node;
2071 2072 2073

	while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
		info = rb_entry(node, struct btrfs_free_space, offset_index);
2074 2075 2076 2077 2078 2079
		if (!info->bitmap) {
			unlink_free_space(ctl, info);
			kmem_cache_free(btrfs_free_space_cachep, info);
		} else {
			free_bitmap(ctl, info);
		}
2080 2081 2082 2083 2084 2085
		if (need_resched()) {
			spin_unlock(&ctl->tree_lock);
			cond_resched();
			spin_lock(&ctl->tree_lock);
		}
	}
2086 2087 2088 2089 2090 2091
}

void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
{
	spin_lock(&ctl->tree_lock);
	__btrfs_remove_free_space_cache_locked(ctl);
2092 2093 2094 2095 2096 2097
	spin_unlock(&ctl->tree_lock);
}

void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
{
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2098
	struct btrfs_free_cluster *cluster;
2099
	struct list_head *head;
J
Josef Bacik 已提交
2100

2101
	spin_lock(&ctl->tree_lock);
2102 2103 2104 2105
	while ((head = block_group->cluster_list.next) !=
	       &block_group->cluster_list) {
		cluster = list_entry(head, struct btrfs_free_cluster,
				     block_group_list);
2106 2107 2108

		WARN_ON(cluster->block_group != block_group);
		__btrfs_return_cluster_to_free_space(block_group, cluster);
2109
		if (need_resched()) {
2110
			spin_unlock(&ctl->tree_lock);
2111
			cond_resched();
2112
			spin_lock(&ctl->tree_lock);
2113
		}
2114
	}
2115
	__btrfs_remove_free_space_cache_locked(ctl);
2116
	spin_unlock(&ctl->tree_lock);
2117

J
Josef Bacik 已提交
2118 2119
}

2120 2121
u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
			       u64 offset, u64 bytes, u64 empty_size)
J
Josef Bacik 已提交
2122
{
2123
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2124
	struct btrfs_free_space *entry = NULL;
2125
	u64 bytes_search = bytes + empty_size;
2126
	u64 ret = 0;
D
David Woodhouse 已提交
2127 2128
	u64 align_gap = 0;
	u64 align_gap_len = 0;
J
Josef Bacik 已提交
2129

2130
	spin_lock(&ctl->tree_lock);
D
David Woodhouse 已提交
2131 2132
	entry = find_free_space(ctl, &offset, &bytes_search,
				block_group->full_stripe_len);
2133
	if (!entry)
2134 2135 2136 2137
		goto out;

	ret = offset;
	if (entry->bitmap) {
2138
		bitmap_clear_bits(ctl, entry, offset, bytes);
2139
		if (!entry->bytes)
2140
			free_bitmap(ctl, entry);
2141
	} else {
D
David Woodhouse 已提交
2142

2143
		unlink_free_space(ctl, entry);
D
David Woodhouse 已提交
2144 2145 2146 2147 2148 2149 2150
		align_gap_len = offset - entry->offset;
		align_gap = entry->offset;

		entry->offset = offset + bytes;
		WARN_ON(entry->bytes < bytes + align_gap_len);

		entry->bytes -= bytes + align_gap_len;
2151
		if (!entry->bytes)
2152
			kmem_cache_free(btrfs_free_space_cachep, entry);
2153
		else
2154
			link_free_space(ctl, entry);
2155
	}
J
Josef Bacik 已提交
2156

2157
out:
2158
	spin_unlock(&ctl->tree_lock);
J
Josef Bacik 已提交
2159

D
David Woodhouse 已提交
2160 2161
	if (align_gap_len)
		__btrfs_add_free_space(ctl, align_gap, align_gap_len);
J
Josef Bacik 已提交
2162 2163
	return ret;
}
2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176

/*
 * given a cluster, put all of its extents back into the free space
 * cache.  If a block group is passed, this function will only free
 * a cluster that belongs to the passed block group.
 *
 * Otherwise, it'll get a reference on the block group pointed to by the
 * cluster and remove the cluster from it.
 */
int btrfs_return_cluster_to_free_space(
			       struct btrfs_block_group_cache *block_group,
			       struct btrfs_free_cluster *cluster)
{
2177
	struct btrfs_free_space_ctl *ctl;
2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195
	int ret;

	/* first, get a safe pointer to the block group */
	spin_lock(&cluster->lock);
	if (!block_group) {
		block_group = cluster->block_group;
		if (!block_group) {
			spin_unlock(&cluster->lock);
			return 0;
		}
	} else if (cluster->block_group != block_group) {
		/* someone else has already freed it don't redo their work */
		spin_unlock(&cluster->lock);
		return 0;
	}
	atomic_inc(&block_group->count);
	spin_unlock(&cluster->lock);

2196 2197
	ctl = block_group->free_space_ctl;

2198
	/* now return any extents the cluster had on it */
2199
	spin_lock(&ctl->tree_lock);
2200
	ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
2201
	spin_unlock(&ctl->tree_lock);
2202 2203 2204 2205 2206 2207

	/* finally drop our ref */
	btrfs_put_block_group(block_group);
	return ret;
}

2208 2209
static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
				   struct btrfs_free_cluster *cluster,
2210
				   struct btrfs_free_space *entry,
2211 2212
				   u64 bytes, u64 min_start)
{
2213
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2214 2215 2216 2217 2218 2219 2220 2221
	int err;
	u64 search_start = cluster->window_start;
	u64 search_bytes = bytes;
	u64 ret = 0;

	search_start = min_start;
	search_bytes = bytes;

2222
	err = search_bitmap(ctl, entry, &search_start, &search_bytes);
2223
	if (err)
2224
		return 0;
2225 2226

	ret = search_start;
2227
	__bitmap_clear_bits(ctl, entry, ret, bytes);
2228 2229 2230 2231

	return ret;
}

2232 2233 2234 2235 2236 2237 2238 2239 2240
/*
 * given a cluster, try to allocate 'bytes' from it, returns 0
 * if it couldn't find anything suitably large, or a logical disk offset
 * if things worked out
 */
u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
			     struct btrfs_free_cluster *cluster, u64 bytes,
			     u64 min_start)
{
2241
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258
	struct btrfs_free_space *entry = NULL;
	struct rb_node *node;
	u64 ret = 0;

	spin_lock(&cluster->lock);
	if (bytes > cluster->max_size)
		goto out;

	if (cluster->block_group != block_group)
		goto out;

	node = rb_first(&cluster->root);
	if (!node)
		goto out;

	entry = rb_entry(node, struct btrfs_free_space, offset_index);
	while(1) {
2259 2260
		if (entry->bytes < bytes ||
		    (!entry->bitmap && entry->offset < min_start)) {
2261 2262 2263 2264 2265 2266 2267 2268
			node = rb_next(&entry->offset_index);
			if (!node)
				break;
			entry = rb_entry(node, struct btrfs_free_space,
					 offset_index);
			continue;
		}

2269 2270 2271
		if (entry->bitmap) {
			ret = btrfs_alloc_from_bitmap(block_group,
						      cluster, entry, bytes,
2272
						      cluster->window_start);
2273 2274 2275 2276 2277 2278 2279 2280
			if (ret == 0) {
				node = rb_next(&entry->offset_index);
				if (!node)
					break;
				entry = rb_entry(node, struct btrfs_free_space,
						 offset_index);
				continue;
			}
2281
			cluster->window_start += bytes;
2282 2283 2284 2285 2286 2287
		} else {
			ret = entry->offset;

			entry->offset += bytes;
			entry->bytes -= bytes;
		}
2288

2289
		if (entry->bytes == 0)
2290 2291 2292 2293 2294
			rb_erase(&entry->offset_index, &cluster->root);
		break;
	}
out:
	spin_unlock(&cluster->lock);
2295

2296 2297 2298
	if (!ret)
		return 0;

2299
	spin_lock(&ctl->tree_lock);
2300

2301
	ctl->free_space -= bytes;
2302
	if (entry->bytes == 0) {
2303
		ctl->free_extents--;
2304 2305
		if (entry->bitmap) {
			kfree(entry->bitmap);
2306 2307
			ctl->total_bitmaps--;
			ctl->op->recalc_thresholds(ctl);
2308
		}
2309
		kmem_cache_free(btrfs_free_space_cachep, entry);
2310 2311
	}

2312
	spin_unlock(&ctl->tree_lock);
2313

2314 2315 2316
	return ret;
}

2317 2318 2319
static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group,
				struct btrfs_free_space *entry,
				struct btrfs_free_cluster *cluster,
2320 2321
				u64 offset, u64 bytes,
				u64 cont1_bytes, u64 min_bytes)
2322
{
2323
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2324 2325
	unsigned long next_zero;
	unsigned long i;
2326 2327
	unsigned long want_bits;
	unsigned long min_bits;
2328 2329 2330
	unsigned long found_bits;
	unsigned long start = 0;
	unsigned long total_found = 0;
2331
	int ret;
2332

2333
	i = offset_to_bit(entry->offset, ctl->unit,
2334
			  max_t(u64, offset, entry->offset));
2335 2336
	want_bits = bytes_to_bits(bytes, ctl->unit);
	min_bits = bytes_to_bits(min_bytes, ctl->unit);
2337 2338 2339

again:
	found_bits = 0;
2340
	for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {
2341 2342
		next_zero = find_next_zero_bit(entry->bitmap,
					       BITS_PER_BITMAP, i);
2343
		if (next_zero - i >= min_bits) {
2344 2345 2346 2347 2348 2349 2350
			found_bits = next_zero - i;
			break;
		}
		i = next_zero;
	}

	if (!found_bits)
2351
		return -ENOSPC;
2352

2353
	if (!total_found) {
2354
		start = i;
2355
		cluster->max_size = 0;
2356 2357 2358 2359
	}

	total_found += found_bits;

2360 2361
	if (cluster->max_size < found_bits * ctl->unit)
		cluster->max_size = found_bits * ctl->unit;
2362

2363 2364
	if (total_found < want_bits || cluster->max_size < cont1_bytes) {
		i = next_zero + 1;
2365 2366 2367
		goto again;
	}

2368
	cluster->window_start = start * ctl->unit + entry->offset;
2369
	rb_erase(&entry->offset_index, &ctl->free_space_offset);
2370 2371
	ret = tree_insert_offset(&cluster->root, entry->offset,
				 &entry->offset_index, 1);
2372
	BUG_ON(ret); /* -EEXIST; Logic error */
2373

J
Josef Bacik 已提交
2374
	trace_btrfs_setup_cluster(block_group, cluster,
2375
				  total_found * ctl->unit, 1);
2376 2377 2378
	return 0;
}

2379 2380
/*
 * This searches the block group for just extents to fill the cluster with.
2381 2382
 * Try to find a cluster with at least bytes total bytes, at least one
 * extent of cont1_bytes, and other clusters of at least min_bytes.
2383
 */
2384 2385 2386 2387
static noinline int
setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group,
			struct btrfs_free_cluster *cluster,
			struct list_head *bitmaps, u64 offset, u64 bytes,
2388
			u64 cont1_bytes, u64 min_bytes)
2389
{
2390
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2391 2392 2393 2394 2395 2396 2397
	struct btrfs_free_space *first = NULL;
	struct btrfs_free_space *entry = NULL;
	struct btrfs_free_space *last;
	struct rb_node *node;
	u64 window_start;
	u64 window_free;
	u64 max_extent;
J
Josef Bacik 已提交
2398
	u64 total_size = 0;
2399

2400
	entry = tree_search_offset(ctl, offset, 0, 1);
2401 2402 2403 2404 2405 2406 2407
	if (!entry)
		return -ENOSPC;

	/*
	 * We don't want bitmaps, so just move along until we find a normal
	 * extent entry.
	 */
2408 2409
	while (entry->bitmap || entry->bytes < min_bytes) {
		if (entry->bitmap && list_empty(&entry->list))
2410
			list_add_tail(&entry->list, bitmaps);
2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422
		node = rb_next(&entry->offset_index);
		if (!node)
			return -ENOSPC;
		entry = rb_entry(node, struct btrfs_free_space, offset_index);
	}

	window_start = entry->offset;
	window_free = entry->bytes;
	max_extent = entry->bytes;
	first = entry;
	last = entry;

2423 2424
	for (node = rb_next(&entry->offset_index); node;
	     node = rb_next(&entry->offset_index)) {
2425 2426
		entry = rb_entry(node, struct btrfs_free_space, offset_index);

2427 2428 2429
		if (entry->bitmap) {
			if (list_empty(&entry->list))
				list_add_tail(&entry->list, bitmaps);
2430
			continue;
2431 2432
		}

2433 2434 2435 2436 2437 2438
		if (entry->bytes < min_bytes)
			continue;

		last = entry;
		window_free += entry->bytes;
		if (entry->bytes > max_extent)
2439 2440 2441
			max_extent = entry->bytes;
	}

2442 2443 2444
	if (window_free < bytes || max_extent < cont1_bytes)
		return -ENOSPC;

2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457
	cluster->window_start = first->offset;

	node = &first->offset_index;

	/*
	 * now we've found our entries, pull them out of the free space
	 * cache and put them into the cluster rbtree
	 */
	do {
		int ret;

		entry = rb_entry(node, struct btrfs_free_space, offset_index);
		node = rb_next(&entry->offset_index);
2458
		if (entry->bitmap || entry->bytes < min_bytes)
2459 2460
			continue;

2461
		rb_erase(&entry->offset_index, &ctl->free_space_offset);
2462 2463
		ret = tree_insert_offset(&cluster->root, entry->offset,
					 &entry->offset_index, 0);
J
Josef Bacik 已提交
2464
		total_size += entry->bytes;
2465
		BUG_ON(ret); /* -EEXIST; Logic error */
2466 2467 2468
	} while (node && entry != last);

	cluster->max_size = max_extent;
J
Josef Bacik 已提交
2469
	trace_btrfs_setup_cluster(block_group, cluster, total_size, 0);
2470 2471 2472 2473 2474 2475 2476
	return 0;
}

/*
 * This specifically looks for bitmaps that may work in the cluster, we assume
 * that we have already failed to find extents that will work.
 */
2477 2478 2479 2480
static noinline int
setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,
		     struct btrfs_free_cluster *cluster,
		     struct list_head *bitmaps, u64 offset, u64 bytes,
2481
		     u64 cont1_bytes, u64 min_bytes)
2482
{
2483
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2484 2485
	struct btrfs_free_space *entry;
	int ret = -ENOSPC;
2486
	u64 bitmap_offset = offset_to_bitmap(ctl, offset);
2487

2488
	if (ctl->total_bitmaps == 0)
2489 2490
		return -ENOSPC;

2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501
	/*
	 * The bitmap that covers offset won't be in the list unless offset
	 * is just its start offset.
	 */
	entry = list_first_entry(bitmaps, struct btrfs_free_space, list);
	if (entry->offset != bitmap_offset) {
		entry = tree_search_offset(ctl, bitmap_offset, 1, 0);
		if (entry && list_empty(&entry->list))
			list_add(&entry->list, bitmaps);
	}

2502
	list_for_each_entry(entry, bitmaps, list) {
2503
		if (entry->bytes < bytes)
2504 2505
			continue;
		ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
2506
					   bytes, cont1_bytes, min_bytes);
2507 2508 2509 2510 2511
		if (!ret)
			return 0;
	}

	/*
2512 2513
	 * The bitmaps list has all the bitmaps that record free space
	 * starting after offset, so no more search is required.
2514
	 */
2515
	return -ENOSPC;
2516 2517
}

2518 2519
/*
 * here we try to find a cluster of blocks in a block group.  The goal
2520
 * is to find at least bytes+empty_size.
2521 2522 2523 2524 2525 2526
 * We might not find them all in one contiguous area.
 *
 * returns zero and sets up cluster if things worked out, otherwise
 * it returns -enospc
 */
int btrfs_find_space_cluster(struct btrfs_trans_handle *trans,
2527
			     struct btrfs_root *root,
2528 2529 2530 2531
			     struct btrfs_block_group_cache *block_group,
			     struct btrfs_free_cluster *cluster,
			     u64 offset, u64 bytes, u64 empty_size)
{
2532
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2533
	struct btrfs_free_space *entry, *tmp;
2534
	LIST_HEAD(bitmaps);
2535
	u64 min_bytes;
2536
	u64 cont1_bytes;
2537 2538
	int ret;

2539 2540 2541 2542 2543 2544
	/*
	 * Choose the minimum extent size we'll require for this
	 * cluster.  For SSD_SPREAD, don't allow any fragmentation.
	 * For metadata, allow allocates with smaller extents.  For
	 * data, keep it dense.
	 */
2545
	if (btrfs_test_opt(root, SSD_SPREAD)) {
2546
		cont1_bytes = min_bytes = bytes + empty_size;
2547
	} else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
2548 2549 2550 2551 2552 2553
		cont1_bytes = bytes;
		min_bytes = block_group->sectorsize;
	} else {
		cont1_bytes = max(bytes, (bytes + empty_size) >> 2);
		min_bytes = block_group->sectorsize;
	}
2554

2555
	spin_lock(&ctl->tree_lock);
2556 2557 2558 2559 2560

	/*
	 * If we know we don't have enough space to make a cluster don't even
	 * bother doing all the work to try and find one.
	 */
2561
	if (ctl->free_space < bytes) {
2562
		spin_unlock(&ctl->tree_lock);
2563 2564 2565
		return -ENOSPC;
	}

2566 2567 2568 2569 2570 2571 2572 2573
	spin_lock(&cluster->lock);

	/* someone already found a cluster, hooray */
	if (cluster->block_group) {
		ret = 0;
		goto out;
	}

J
Josef Bacik 已提交
2574 2575 2576 2577
	trace_btrfs_find_cluster(block_group, offset, bytes, empty_size,
				 min_bytes);

	INIT_LIST_HEAD(&bitmaps);
2578
	ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
2579 2580
				      bytes + empty_size,
				      cont1_bytes, min_bytes);
2581
	if (ret)
2582
		ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
2583 2584
					   offset, bytes + empty_size,
					   cont1_bytes, min_bytes);
2585 2586 2587 2588

	/* Clear our temporary list */
	list_for_each_entry_safe(entry, tmp, &bitmaps, list)
		list_del_init(&entry->list);
2589

2590 2591 2592 2593 2594
	if (!ret) {
		atomic_inc(&block_group->count);
		list_add_tail(&cluster->block_group_list,
			      &block_group->cluster_list);
		cluster->block_group = block_group;
J
Josef Bacik 已提交
2595 2596
	} else {
		trace_btrfs_failed_cluster_setup(block_group);
2597 2598 2599
	}
out:
	spin_unlock(&cluster->lock);
2600
	spin_unlock(&ctl->tree_lock);
2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611

	return ret;
}

/*
 * simple code to zero out a cluster
 */
void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
{
	spin_lock_init(&cluster->lock);
	spin_lock_init(&cluster->refill_lock);
2612
	cluster->root = RB_ROOT;
2613 2614 2615 2616 2617
	cluster->max_size = 0;
	INIT_LIST_HEAD(&cluster->block_group_list);
	cluster->block_group = NULL;
}

2618 2619 2620
static int do_trimming(struct btrfs_block_group_cache *block_group,
		       u64 *total_trimmed, u64 start, u64 bytes,
		       u64 reserved_start, u64 reserved_bytes)
2621
{
2622
	struct btrfs_space_info *space_info = block_group->space_info;
2623
	struct btrfs_fs_info *fs_info = block_group->fs_info;
2624 2625 2626
	int ret;
	int update = 0;
	u64 trimmed = 0;
2627

2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668
	spin_lock(&space_info->lock);
	spin_lock(&block_group->lock);
	if (!block_group->ro) {
		block_group->reserved += reserved_bytes;
		space_info->bytes_reserved += reserved_bytes;
		update = 1;
	}
	spin_unlock(&block_group->lock);
	spin_unlock(&space_info->lock);

	ret = btrfs_error_discard_extent(fs_info->extent_root,
					 start, bytes, &trimmed);
	if (!ret)
		*total_trimmed += trimmed;

	btrfs_add_free_space(block_group, reserved_start, reserved_bytes);

	if (update) {
		spin_lock(&space_info->lock);
		spin_lock(&block_group->lock);
		if (block_group->ro)
			space_info->bytes_readonly += reserved_bytes;
		block_group->reserved -= reserved_bytes;
		space_info->bytes_reserved -= reserved_bytes;
		spin_unlock(&space_info->lock);
		spin_unlock(&block_group->lock);
	}

	return ret;
}

static int trim_no_bitmap(struct btrfs_block_group_cache *block_group,
			  u64 *total_trimmed, u64 start, u64 end, u64 minlen)
{
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
	struct btrfs_free_space *entry;
	struct rb_node *node;
	int ret = 0;
	u64 extent_start;
	u64 extent_bytes;
	u64 bytes;
2669 2670

	while (start < end) {
2671
		spin_lock(&ctl->tree_lock);
2672

2673 2674
		if (ctl->free_space < minlen) {
			spin_unlock(&ctl->tree_lock);
2675 2676 2677
			break;
		}

2678
		entry = tree_search_offset(ctl, start, 0, 1);
2679
		if (!entry) {
2680
			spin_unlock(&ctl->tree_lock);
2681 2682 2683
			break;
		}

2684 2685 2686 2687
		/* skip bitmaps */
		while (entry->bitmap) {
			node = rb_next(&entry->offset_index);
			if (!node) {
2688
				spin_unlock(&ctl->tree_lock);
2689
				goto out;
2690
			}
2691 2692
			entry = rb_entry(node, struct btrfs_free_space,
					 offset_index);
2693 2694
		}

2695 2696 2697
		if (entry->offset >= end) {
			spin_unlock(&ctl->tree_lock);
			break;
2698 2699
		}

2700 2701 2702 2703 2704 2705 2706
		extent_start = entry->offset;
		extent_bytes = entry->bytes;
		start = max(start, extent_start);
		bytes = min(extent_start + extent_bytes, end) - start;
		if (bytes < minlen) {
			spin_unlock(&ctl->tree_lock);
			goto next;
2707 2708
		}

2709 2710 2711
		unlink_free_space(ctl, entry);
		kmem_cache_free(btrfs_free_space_cachep, entry);

2712
		spin_unlock(&ctl->tree_lock);
2713

2714 2715 2716 2717 2718 2719
		ret = do_trimming(block_group, total_trimmed, start, bytes,
				  extent_start, extent_bytes);
		if (ret)
			break;
next:
		start += bytes;
2720

2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789
		if (fatal_signal_pending(current)) {
			ret = -ERESTARTSYS;
			break;
		}

		cond_resched();
	}
out:
	return ret;
}

static int trim_bitmaps(struct btrfs_block_group_cache *block_group,
			u64 *total_trimmed, u64 start, u64 end, u64 minlen)
{
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
	struct btrfs_free_space *entry;
	int ret = 0;
	int ret2;
	u64 bytes;
	u64 offset = offset_to_bitmap(ctl, start);

	while (offset < end) {
		bool next_bitmap = false;

		spin_lock(&ctl->tree_lock);

		if (ctl->free_space < minlen) {
			spin_unlock(&ctl->tree_lock);
			break;
		}

		entry = tree_search_offset(ctl, offset, 1, 0);
		if (!entry) {
			spin_unlock(&ctl->tree_lock);
			next_bitmap = true;
			goto next;
		}

		bytes = minlen;
		ret2 = search_bitmap(ctl, entry, &start, &bytes);
		if (ret2 || start >= end) {
			spin_unlock(&ctl->tree_lock);
			next_bitmap = true;
			goto next;
		}

		bytes = min(bytes, end - start);
		if (bytes < minlen) {
			spin_unlock(&ctl->tree_lock);
			goto next;
		}

		bitmap_clear_bits(ctl, entry, start, bytes);
		if (entry->bytes == 0)
			free_bitmap(ctl, entry);

		spin_unlock(&ctl->tree_lock);

		ret = do_trimming(block_group, total_trimmed, start, bytes,
				  start, bytes);
		if (ret)
			break;
next:
		if (next_bitmap) {
			offset += BITS_PER_BITMAP * ctl->unit;
		} else {
			start += bytes;
			if (start >= offset + BITS_PER_BITMAP * ctl->unit)
				offset += BITS_PER_BITMAP * ctl->unit;
2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801
		}

		if (fatal_signal_pending(current)) {
			ret = -ERESTARTSYS;
			break;
		}

		cond_resched();
	}

	return ret;
}
2802

2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818
int btrfs_trim_block_group(struct btrfs_block_group_cache *block_group,
			   u64 *trimmed, u64 start, u64 end, u64 minlen)
{
	int ret;

	*trimmed = 0;

	ret = trim_no_bitmap(block_group, trimmed, start, end, minlen);
	if (ret)
		return ret;

	ret = trim_bitmaps(block_group, trimmed, start, end, minlen);

	return ret;
}

2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855
/*
 * Find the left-most item in the cache tree, and then return the
 * smallest inode number in the item.
 *
 * Note: the returned inode number may not be the smallest one in
 * the tree, if the left-most item is a bitmap.
 */
u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root)
{
	struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl;
	struct btrfs_free_space *entry = NULL;
	u64 ino = 0;

	spin_lock(&ctl->tree_lock);

	if (RB_EMPTY_ROOT(&ctl->free_space_offset))
		goto out;

	entry = rb_entry(rb_first(&ctl->free_space_offset),
			 struct btrfs_free_space, offset_index);

	if (!entry->bitmap) {
		ino = entry->offset;

		unlink_free_space(ctl, entry);
		entry->offset++;
		entry->bytes--;
		if (!entry->bytes)
			kmem_cache_free(btrfs_free_space_cachep, entry);
		else
			link_free_space(ctl, entry);
	} else {
		u64 offset = 0;
		u64 count = 1;
		int ret;

		ret = search_bitmap(ctl, entry, &offset, &count);
2856
		/* Logic error; Should be empty if it can't find anything */
2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868
		BUG_ON(ret);

		ino = offset;
		bitmap_clear_bits(ctl, entry, offset, 1);
		if (entry->bytes == 0)
			free_bitmap(ctl, entry);
	}
out:
	spin_unlock(&ctl->tree_lock);

	return ino;
}
2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886

struct inode *lookup_free_ino_inode(struct btrfs_root *root,
				    struct btrfs_path *path)
{
	struct inode *inode = NULL;

	spin_lock(&root->cache_lock);
	if (root->cache_inode)
		inode = igrab(root->cache_inode);
	spin_unlock(&root->cache_lock);
	if (inode)
		return inode;

	inode = __lookup_free_space_inode(root, path, 0);
	if (IS_ERR(inode))
		return inode;

	spin_lock(&root->cache_lock);
2887
	if (!btrfs_fs_closing(root->fs_info))
2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909
		root->cache_inode = igrab(inode);
	spin_unlock(&root->cache_lock);

	return inode;
}

int create_free_ino_inode(struct btrfs_root *root,
			  struct btrfs_trans_handle *trans,
			  struct btrfs_path *path)
{
	return __create_free_space_inode(root, trans, path,
					 BTRFS_FREE_INO_OBJECTID, 0);
}

int load_free_ino_cache(struct btrfs_fs_info *fs_info, struct btrfs_root *root)
{
	struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
	struct btrfs_path *path;
	struct inode *inode;
	int ret = 0;
	u64 root_gen = btrfs_root_generation(&root->root_item);

C
Chris Mason 已提交
2910 2911 2912
	if (!btrfs_test_opt(root, INODE_MAP_CACHE))
		return 0;

2913 2914 2915 2916
	/*
	 * If we're unmounting then just return, since this does a search on the
	 * normal root and not the commit root and we could deadlock.
	 */
2917
	if (btrfs_fs_closing(fs_info))
2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950
		return 0;

	path = btrfs_alloc_path();
	if (!path)
		return 0;

	inode = lookup_free_ino_inode(root, path);
	if (IS_ERR(inode))
		goto out;

	if (root_gen != BTRFS_I(inode)->generation)
		goto out_put;

	ret = __load_free_space_cache(root, inode, ctl, path, 0);

	if (ret < 0)
		printk(KERN_ERR "btrfs: failed to load free ino cache for "
		       "root %llu\n", root->root_key.objectid);
out_put:
	iput(inode);
out:
	btrfs_free_path(path);
	return ret;
}

int btrfs_write_out_ino_cache(struct btrfs_root *root,
			      struct btrfs_trans_handle *trans,
			      struct btrfs_path *path)
{
	struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
	struct inode *inode;
	int ret;

C
Chris Mason 已提交
2951 2952 2953
	if (!btrfs_test_opt(root, INODE_MAP_CACHE))
		return 0;

2954 2955 2956 2957 2958
	inode = lookup_free_ino_inode(root, path);
	if (IS_ERR(inode))
		return 0;

	ret = __btrfs_write_out_cache(root, inode, ctl, NULL, trans, path, 0);
2959 2960 2961
	if (ret) {
		btrfs_delalloc_release_metadata(inode, inode->i_size);
#ifdef DEBUG
2962 2963
		printk(KERN_ERR "btrfs: failed to write free ino cache "
		       "for root %llu\n", root->root_key.objectid);
2964 2965
#endif
	}
2966 2967 2968 2969

	iput(inode);
	return ret;
}