free-space-cache.c 91.8 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
#include "volumes.h"
31

32
#define BITS_PER_BITMAP		(PAGE_SIZE * 8UL)
33
#define MAX_CACHE_BYTES_PER_GIG	SZ_32K
J
Josef Bacik 已提交
34

35 36 37 38 39 40
struct btrfs_trim_range {
	u64 start;
	u64 bytes;
	struct list_head list;
};

41
static int link_free_space(struct btrfs_free_space_ctl *ctl,
J
Josef Bacik 已提交
42
			   struct btrfs_free_space *info);
43 44
static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
			      struct btrfs_free_space *info);
J
Josef Bacik 已提交
45

46 47 48
static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
					       struct btrfs_path *path,
					       u64 offset)
49 50 51 52 53 54 55 56 57 58
{
	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;
59
	key.offset = offset;
60 61 62 63 64 65
	key.type = 0;

	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		return ERR_PTR(ret);
	if (ret > 0) {
66
		btrfs_release_path(path);
67 68 69 70 71 72 73 74
		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);
75
	btrfs_release_path(path);
76 77 78 79 80 81 82 83 84

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

A
Al Viro 已提交
85
	mapping_set_gfp_mask(inode->i_mapping,
86 87
			mapping_gfp_constraint(inode->i_mapping,
			~(__GFP_FS | __GFP_HIGHMEM)));
88

89 90 91 92 93 94 95 96
	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;
97
	u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
98 99 100 101 102 103 104 105 106 107 108 109 110

	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;

111
	spin_lock(&block_group->lock);
112
	if (!((BTRFS_I(inode)->flags & flags) == flags)) {
113 114
		btrfs_info(root->fs_info,
			"Old style space inode found, converting.");
115 116
		BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM |
			BTRFS_INODE_NODATACOW;
117 118 119
		block_group->disk_cache_state = BTRFS_DC_CLEAR;
	}

120
	if (!block_group->iref) {
121 122 123 124 125 126 127 128
		block_group->inode = igrab(inode);
		block_group->iref = 1;
	}
	spin_unlock(&block_group->lock);

	return inode;
}

129 130 131 132
static int __create_free_space_inode(struct btrfs_root *root,
				     struct btrfs_trans_handle *trans,
				     struct btrfs_path *path,
				     u64 ino, u64 offset)
133 134 135 136 137 138
{
	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;
139
	u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC;
140 141
	int ret;

142
	ret = btrfs_insert_empty_inode(trans, root, path, ino);
143 144 145
	if (ret)
		return ret;

146 147 148 149
	/* We inline crc's for the free disk space cache */
	if (ino != BTRFS_FREE_INO_OBJECTID)
		flags |= BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;

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]);
154
	memzero_extent_buffer(leaf, (unsigned long)inode_item,
155 156 157 158 159 160 161
			     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);
162
	btrfs_set_inode_flags(leaf, inode_item, flags);
163 164
	btrfs_set_inode_nlink(leaf, inode_item, 1);
	btrfs_set_inode_transid(leaf, inode_item, trans->transid);
165
	btrfs_set_inode_block_group(leaf, inode_item, offset);
166
	btrfs_mark_buffer_dirty(leaf);
167
	btrfs_release_path(path);
168 169

	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
170
	key.offset = offset;
171 172 173 174
	key.type = 0;
	ret = btrfs_insert_empty_item(trans, root, path, &key,
				      sizeof(struct btrfs_free_space_header));
	if (ret < 0) {
175
		btrfs_release_path(path);
176 177
		return ret;
	}
178

179 180 181
	leaf = path->nodes[0];
	header = btrfs_item_ptr(leaf, path->slots[0],
				struct btrfs_free_space_header);
182
	memzero_extent_buffer(leaf, (unsigned long)header, sizeof(*header));
183 184
	btrfs_set_free_space_key(leaf, header, &disk_key);
	btrfs_mark_buffer_dirty(leaf);
185
	btrfs_release_path(path);
186 187 188 189

	return 0;
}

190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205
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);
}

206 207
int btrfs_check_trunc_cache_free_space(struct btrfs_root *root,
				       struct btrfs_block_rsv *rsv)
208
{
209
	u64 needed_bytes;
210
	int ret;
211 212 213 214 215

	/* 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);

216 217 218 219 220 221
	spin_lock(&rsv->lock);
	if (rsv->reserved < needed_bytes)
		ret = -ENOSPC;
	else
		ret = 0;
	spin_unlock(&rsv->lock);
222
	return ret;
223 224 225 226
}

int btrfs_truncate_free_space_cache(struct btrfs_root *root,
				    struct btrfs_trans_handle *trans,
227
				    struct btrfs_block_group_cache *block_group,
228 229 230
				    struct inode *inode)
{
	int ret = 0;
231
	struct btrfs_path *path = btrfs_alloc_path();
232
	bool locked = false;
233 234 235 236 237 238 239

	if (!path) {
		ret = -ENOMEM;
		goto fail;
	}

	if (block_group) {
240
		locked = true;
241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
		mutex_lock(&trans->transaction->cache_write_mutex);
		if (!list_empty(&block_group->io_list)) {
			list_del_init(&block_group->io_list);

			btrfs_wait_cache_io(root, trans, block_group,
					    &block_group->io_ctl, path,
					    block_group->key.objectid);
			btrfs_put_block_group(block_group);
		}

		/*
		 * now that we've truncated the cache away, its no longer
		 * setup or written
		 */
		spin_lock(&block_group->lock);
		block_group->disk_cache_state = BTRFS_DC_CLEAR;
		spin_unlock(&block_group->lock);
	}
	btrfs_free_path(path);
260 261

	btrfs_i_size_write(inode, 0);
262
	truncate_pagecache(inode, 0);
263 264 265 266

	/*
	 * We don't need an orphan item because truncating the free space cache
	 * will never be split across transactions.
267 268
	 * We don't need to check for -EAGAIN because we're a free space
	 * cache inode
269 270 271
	 */
	ret = btrfs_truncate_inode_items(trans, root, inode,
					 0, BTRFS_EXTENT_DATA_KEY);
272 273
	if (ret)
		goto fail;
274

275
	ret = btrfs_update_inode(trans, root, inode);
276 277

fail:
278 279
	if (locked)
		mutex_unlock(&trans->transaction->cache_write_mutex);
280
	if (ret)
281
		btrfs_abort_transaction(trans, ret);
282

283
	return ret;
284 285
}

286 287 288 289 290 291 292 293 294 295
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);
296
	last_index = (i_size_read(inode) - 1) >> PAGE_SHIFT;
297 298 299 300 301 302 303 304

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

	kfree(ra);

	return 0;
}

305
static int io_ctl_init(struct btrfs_io_ctl *io_ctl, struct inode *inode,
306
		       struct btrfs_root *root, int write)
307
{
308 309 310
	int num_pages;
	int check_crcs = 0;

311
	num_pages = DIV_ROUND_UP(i_size_read(inode), PAGE_SIZE);
312 313 314 315 316 317

	if (btrfs_ino(inode) != BTRFS_FREE_INO_OBJECTID)
		check_crcs = 1;

	/* Make sure we can fit our crcs into the first page */
	if (write && check_crcs &&
318
	    (num_pages * sizeof(u32)) >= PAGE_SIZE)
319 320
		return -ENOSPC;

321
	memset(io_ctl, 0, sizeof(struct btrfs_io_ctl));
322

323
	io_ctl->pages = kcalloc(num_pages, sizeof(struct page *), GFP_NOFS);
324 325
	if (!io_ctl->pages)
		return -ENOMEM;
326 327

	io_ctl->num_pages = num_pages;
328
	io_ctl->root = root;
329
	io_ctl->check_crcs = check_crcs;
330
	io_ctl->inode = inode;
331

332 333 334
	return 0;
}

335
static void io_ctl_free(struct btrfs_io_ctl *io_ctl)
336 337
{
	kfree(io_ctl->pages);
338
	io_ctl->pages = NULL;
339 340
}

341
static void io_ctl_unmap_page(struct btrfs_io_ctl *io_ctl)
342 343 344 345 346 347 348
{
	if (io_ctl->cur) {
		io_ctl->cur = NULL;
		io_ctl->orig = NULL;
	}
}

349
static void io_ctl_map_page(struct btrfs_io_ctl *io_ctl, int clear)
350
{
351
	ASSERT(io_ctl->index < io_ctl->num_pages);
352
	io_ctl->page = io_ctl->pages[io_ctl->index++];
353
	io_ctl->cur = page_address(io_ctl->page);
354
	io_ctl->orig = io_ctl->cur;
355
	io_ctl->size = PAGE_SIZE;
356
	if (clear)
357
		memset(io_ctl->cur, 0, PAGE_SIZE);
358 359
}

360
static void io_ctl_drop_pages(struct btrfs_io_ctl *io_ctl)
361 362 363 364 365 366
{
	int i;

	io_ctl_unmap_page(io_ctl);

	for (i = 0; i < io_ctl->num_pages; i++) {
367 368 369
		if (io_ctl->pages[i]) {
			ClearPageChecked(io_ctl->pages[i]);
			unlock_page(io_ctl->pages[i]);
370
			put_page(io_ctl->pages[i]);
371
		}
372 373 374
	}
}

375
static int io_ctl_prepare_pages(struct btrfs_io_ctl *io_ctl, struct inode *inode,
376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
				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)) {
393 394
				btrfs_err(BTRFS_I(inode)->root->fs_info,
					   "error reading free space cache");
395 396 397 398 399 400
				io_ctl_drop_pages(io_ctl);
				return -EIO;
			}
		}
	}

401 402 403 404 405
	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]);
	}

406 407 408
	return 0;
}

409
static void io_ctl_set_generation(struct btrfs_io_ctl *io_ctl, u64 generation)
410
{
A
Al Viro 已提交
411
	__le64 *val;
412 413 414 415

	io_ctl_map_page(io_ctl, 1);

	/*
416 417
	 * Skip the csum areas.  If we don't check crcs then we just have a
	 * 64bit chunk at the front of the first page.
418
	 */
419 420 421 422 423 424 425
	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;
	}
426 427 428 429 430 431

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

432
static int io_ctl_check_generation(struct btrfs_io_ctl *io_ctl, u64 generation)
433
{
A
Al Viro 已提交
434
	__le64 *gen;
435

436 437 438 439 440 441 442 443 444 445 446 447
	/*
	 * 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;
	}
448 449 450

	gen = io_ctl->cur;
	if (le64_to_cpu(*gen) != generation) {
451 452 453
		btrfs_err_rl(io_ctl->root->fs_info,
			"space cache generation (%llu) does not match inode (%llu)",
				*gen, generation);
454 455 456 457
		io_ctl_unmap_page(io_ctl);
		return -EIO;
	}
	io_ctl->cur += sizeof(u64);
458 459 460
	return 0;
}

461
static void io_ctl_set_crc(struct btrfs_io_ctl *io_ctl, int index)
462 463 464 465 466 467 468 469 470 471 472
{
	u32 *tmp;
	u32 crc = ~(u32)0;
	unsigned offset = 0;

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

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

475
	crc = btrfs_csum_data(io_ctl->orig + offset, crc,
476
			      PAGE_SIZE - offset);
477
	btrfs_csum_final(crc, (u8 *)&crc);
478
	io_ctl_unmap_page(io_ctl);
479
	tmp = page_address(io_ctl->pages[0]);
480 481 482 483
	tmp += index;
	*tmp = crc;
}

484
static int io_ctl_check_crc(struct btrfs_io_ctl *io_ctl, int index)
485 486 487 488 489 490 491 492 493 494 495 496 497
{
	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;

498
	tmp = page_address(io_ctl->pages[0]);
499 500 501 502
	tmp += index;
	val = *tmp;

	io_ctl_map_page(io_ctl, 0);
503
	crc = btrfs_csum_data(io_ctl->orig + offset, crc,
504
			      PAGE_SIZE - offset);
505
	btrfs_csum_final(crc, (u8 *)&crc);
506
	if (val != crc) {
507 508
		btrfs_err_rl(io_ctl->root->fs_info,
			"csum mismatch on free space cache");
509 510 511 512
		io_ctl_unmap_page(io_ctl);
		return -EIO;
	}

513 514 515
	return 0;
}

516
static int io_ctl_add_entry(struct btrfs_io_ctl *io_ctl, u64 offset, u64 bytes,
517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534
			    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;

535
	io_ctl_set_crc(io_ctl, io_ctl->index - 1);
536 537 538 539 540 541 542 543 544 545

	/* 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;
}

546
static int io_ctl_add_bitmap(struct btrfs_io_ctl *io_ctl, void *bitmap)
547 548 549 550 551 552 553 554 555
{
	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) {
556
		io_ctl_set_crc(io_ctl, io_ctl->index - 1);
557 558 559 560 561
		if (io_ctl->index >= io_ctl->num_pages)
			return -ENOSPC;
		io_ctl_map_page(io_ctl, 0);
	}

562
	memcpy(io_ctl->cur, bitmap, PAGE_SIZE);
563
	io_ctl_set_crc(io_ctl, io_ctl->index - 1);
564 565 566 567 568
	if (io_ctl->index < io_ctl->num_pages)
		io_ctl_map_page(io_ctl, 0);
	return 0;
}

569
static void io_ctl_zero_remaining_pages(struct btrfs_io_ctl *io_ctl)
570
{
571 572 573 574 575 576 577 578
	/*
	 * 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);
579 580 581

	while (io_ctl->index < io_ctl->num_pages) {
		io_ctl_map_page(io_ctl, 1);
582
		io_ctl_set_crc(io_ctl, io_ctl->index - 1);
583 584 585
	}
}

586
static int io_ctl_read_entry(struct btrfs_io_ctl *io_ctl,
587
			    struct btrfs_free_space *entry, u8 *type)
588 589
{
	struct btrfs_free_space_entry *e;
590 591 592 593 594 595 596
	int ret;

	if (!io_ctl->cur) {
		ret = io_ctl_check_crc(io_ctl, io_ctl->index);
		if (ret)
			return ret;
	}
597 598 599 600

	e = io_ctl->cur;
	entry->offset = le64_to_cpu(e->offset);
	entry->bytes = le64_to_cpu(e->bytes);
601
	*type = e->type;
602 603 604 605
	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))
606
		return 0;
607 608 609

	io_ctl_unmap_page(io_ctl);

610
	return 0;
611 612
}

613
static int io_ctl_read_bitmap(struct btrfs_io_ctl *io_ctl,
614
			      struct btrfs_free_space *entry)
615
{
616 617 618 619 620 621
	int ret;

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

622
	memcpy(entry->bitmap, io_ctl->cur, PAGE_SIZE);
623
	io_ctl_unmap_page(io_ctl);
624 625

	return 0;
626 627
}

628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665
/*
 * 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);
}

666 667 668
static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
				   struct btrfs_free_space_ctl *ctl,
				   struct btrfs_path *path, u64 offset)
669 670 671
{
	struct btrfs_free_space_header *header;
	struct extent_buffer *leaf;
672
	struct btrfs_io_ctl io_ctl;
673
	struct btrfs_key key;
674
	struct btrfs_free_space *e, *n;
675
	LIST_HEAD(bitmaps);
676 677 678
	u64 num_entries;
	u64 num_bitmaps;
	u64 generation;
679
	u8 type;
680
	int ret = 0;
681 682

	/* Nothing in the space cache, goodbye */
683
	if (!i_size_read(inode))
684
		return 0;
685 686

	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
687
	key.offset = offset;
688 689 690
	key.type = 0;

	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
691
	if (ret < 0)
692
		return 0;
693
	else if (ret > 0) {
694
		btrfs_release_path(path);
695
		return 0;
696 697
	}

698 699
	ret = -1;

700 701 702 703 704 705
	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);
706
	btrfs_release_path(path);
707

708 709 710 711 712 713 714
	if (!BTRFS_I(inode)->generation) {
		btrfs_info(root->fs_info,
			   "The free space cache file (%llu) is invalid. skip it\n",
			   offset);
		return 0;
	}

715
	if (BTRFS_I(inode)->generation != generation) {
716
		btrfs_err(root->fs_info,
J
Jeff Mahoney 已提交
717
			"free space inode generation (%llu) did not match free space cache generation (%llu)",
718
			BTRFS_I(inode)->generation, generation);
719
		return 0;
720 721 722
	}

	if (!num_entries)
723
		return 0;
724

725
	ret = io_ctl_init(&io_ctl, inode, root, 0);
726 727 728
	if (ret)
		return ret;

729
	ret = readahead_cache(inode);
730
	if (ret)
731 732
		goto out;

733 734 735
	ret = io_ctl_prepare_pages(&io_ctl, inode, 1);
	if (ret)
		goto out;
736

737 738 739 740
	ret = io_ctl_check_crc(&io_ctl, 0);
	if (ret)
		goto free_cache;

741 742 743
	ret = io_ctl_check_generation(&io_ctl, generation);
	if (ret)
		goto free_cache;
744

745 746 747 748
	while (num_entries) {
		e = kmem_cache_zalloc(btrfs_free_space_cachep,
				      GFP_NOFS);
		if (!e)
749 750
			goto free_cache;

751 752 753 754 755 756
		ret = io_ctl_read_entry(&io_ctl, e, &type);
		if (ret) {
			kmem_cache_free(btrfs_free_space_cachep, e);
			goto free_cache;
		}

757 758 759
		if (!e->bytes) {
			kmem_cache_free(btrfs_free_space_cachep, e);
			goto free_cache;
760
		}
761 762 763 764 765 766

		if (type == BTRFS_FREE_SPACE_EXTENT) {
			spin_lock(&ctl->tree_lock);
			ret = link_free_space(ctl, e);
			spin_unlock(&ctl->tree_lock);
			if (ret) {
767 768
				btrfs_err(root->fs_info,
					"Duplicate entries in free space cache, dumping");
769
				kmem_cache_free(btrfs_free_space_cachep, e);
770 771
				goto free_cache;
			}
772
		} else {
773
			ASSERT(num_bitmaps);
774
			num_bitmaps--;
775
			e->bitmap = kzalloc(PAGE_SIZE, GFP_NOFS);
776 777 778
			if (!e->bitmap) {
				kmem_cache_free(
					btrfs_free_space_cachep, e);
779 780
				goto free_cache;
			}
781 782 783 784 785 786
			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) {
787 788
				btrfs_err(root->fs_info,
					"Duplicate entries in free space cache, dumping");
789
				kmem_cache_free(btrfs_free_space_cachep, e);
790 791
				goto free_cache;
			}
792
			list_add_tail(&e->list, &bitmaps);
793 794
		}

795 796
		num_entries--;
	}
797

798 799
	io_ctl_unmap_page(&io_ctl);

800 801 802 803 804
	/*
	 * 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) {
805
		list_del_init(&e->list);
806 807 808
		ret = io_ctl_read_bitmap(&io_ctl, e);
		if (ret)
			goto free_cache;
809 810
	}

811
	io_ctl_drop_pages(&io_ctl);
812
	merge_space_tree(ctl);
813 814
	ret = 1;
out:
815
	io_ctl_free(&io_ctl);
816 817
	return ret;
free_cache:
818
	io_ctl_drop_pages(&io_ctl);
819
	__btrfs_remove_free_space_cache(ctl);
820 821 822
	goto out;
}

823 824
int load_free_space_cache(struct btrfs_fs_info *fs_info,
			  struct btrfs_block_group_cache *block_group)
J
Josef Bacik 已提交
825
{
826
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
827 828 829
	struct btrfs_root *root = fs_info->tree_root;
	struct inode *inode;
	struct btrfs_path *path;
830
	int ret = 0;
831 832 833 834 835 836 837
	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.
	 */
838
	spin_lock(&block_group->lock);
839 840 841 842
	if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
		spin_unlock(&block_group->lock);
		return 0;
	}
843
	spin_unlock(&block_group->lock);
844 845 846 847

	path = btrfs_alloc_path();
	if (!path)
		return 0;
848 849
	path->search_commit_root = 1;
	path->skip_locking = 1;
850 851 852 853 854 855 856

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

857 858 859 860
	/* 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);
861
		btrfs_free_path(path);
862 863 864 865
		goto out;
	}
	spin_unlock(&block_group->lock);

866 867 868 869 870 871 872 873 874 875 876 877 878
	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);
J
Jeff Mahoney 已提交
879 880 881
		btrfs_warn(fs_info,
			   "block group %llu has wrong amount of free space",
			   block_group->key.objectid);
882 883 884 885 886 887 888 889
		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);
890
		ret = 0;
891

J
Jeff Mahoney 已提交
892 893 894
		btrfs_warn(fs_info,
			   "failed to load free space cache for block group %llu, rebuilding it now",
			   block_group->key.objectid);
895 896 897 898
	}

	iput(inode);
	return ret;
899 900
}

901
static noinline_for_stack
902
int write_cache_extent_entries(struct btrfs_io_ctl *io_ctl,
903 904 905 906
			      struct btrfs_free_space_ctl *ctl,
			      struct btrfs_block_group_cache *block_group,
			      int *entries, int *bitmaps,
			      struct list_head *bitmap_list)
J
Josef Bacik 已提交
907
{
908
	int ret;
909
	struct btrfs_free_cluster *cluster = NULL;
910
	struct btrfs_free_cluster *cluster_locked = NULL;
911
	struct rb_node *node = rb_first(&ctl->free_space_offset);
912
	struct btrfs_trim_range *trim_entry;
913

914
	/* Get the cluster for this block_group if it exists */
915
	if (block_group && !list_empty(&block_group->cluster_list)) {
916 917 918
		cluster = list_entry(block_group->cluster_list.next,
				     struct btrfs_free_cluster,
				     block_group_list);
919
	}
920

921
	if (!node && cluster) {
922 923
		cluster_locked = cluster;
		spin_lock(&cluster_locked->lock);
924 925 926 927
		node = rb_first(&cluster->root);
		cluster = NULL;
	}

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

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

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

940
		if (e->bitmap) {
941 942
			list_add_tail(&e->list, bitmap_list);
			*bitmaps += 1;
943
		}
944 945 946
		node = rb_next(node);
		if (!node && cluster) {
			node = rb_first(&cluster->root);
947 948
			cluster_locked = cluster;
			spin_lock(&cluster_locked->lock);
949
			cluster = NULL;
950
		}
951
	}
952 953 954 955
	if (cluster_locked) {
		spin_unlock(&cluster_locked->lock);
		cluster_locked = NULL;
	}
956 957 958 959 960 961 962 963 964 965 966 967 968 969 970

	/*
	 * Make sure we don't miss any range that was removed from our rbtree
	 * because trimming is running. Otherwise after a umount+mount (or crash
	 * after committing the transaction) we would leak free space and get
	 * an inconsistent free space cache report from fsck.
	 */
	list_for_each_entry(trim_entry, &ctl->trimming_ranges, list) {
		ret = io_ctl_add_entry(io_ctl, trim_entry->start,
				       trim_entry->bytes, NULL);
		if (ret)
			goto fail;
		*entries += 1;
	}

971 972
	return 0;
fail:
973 974
	if (cluster_locked)
		spin_unlock(&cluster_locked->lock);
975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033
	return -ENOSPC;
}

static noinline_for_stack int
update_cache_item(struct btrfs_trans_handle *trans,
		  struct btrfs_root *root,
		  struct inode *inode,
		  struct btrfs_path *path, u64 offset,
		  int entries, int bitmaps)
{
	struct btrfs_key key;
	struct btrfs_free_space_header *header;
	struct extent_buffer *leaf;
	int ret;

	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
	key.offset = offset;
	key.type = 0;

	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
	if (ret < 0) {
		clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
				 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL,
				 GFP_NOFS);
		goto fail;
	}
	leaf = path->nodes[0];
	if (ret > 0) {
		struct btrfs_key found_key;
		ASSERT(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 ||
		    found_key.offset != offset) {
			clear_extent_bit(&BTRFS_I(inode)->io_tree, 0,
					 inode->i_size - 1,
					 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0,
					 NULL, GFP_NOFS);
			btrfs_release_path(path);
			goto fail;
		}
	}

	BTRFS_I(inode)->generation = trans->transid;
	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);
	btrfs_release_path(path);

	return 0;

fail:
	return -1;
}

static noinline_for_stack int
1034 1035
write_pinned_extent_entries(struct btrfs_root *root,
			    struct btrfs_block_group_cache *block_group,
1036
			    struct btrfs_io_ctl *io_ctl,
1037
			    int *entries)
1038 1039 1040 1041
{
	u64 start, extent_start, extent_end, len;
	struct extent_io_tree *unpin = NULL;
	int ret;
1042

1043 1044 1045
	if (!block_group)
		return 0;

1046 1047 1048
	/*
	 * We want to add any pinned extents to our free space cache
	 * so we don't leak the space
1049
	 *
1050 1051 1052 1053 1054
	 * We shouldn't have switched the pinned extents yet so this is the
	 * right one
	 */
	unpin = root->fs_info->pinned_extents;

1055
	start = block_group->key.objectid;
1056

1057
	while (start < block_group->key.objectid + block_group->key.offset) {
1058 1059
		ret = find_first_extent_bit(unpin, start,
					    &extent_start, &extent_end,
1060
					    EXTENT_DIRTY, NULL);
1061 1062
		if (ret)
			return 0;
J
Josef Bacik 已提交
1063

1064
		/* This pinned extent is out of our range */
1065
		if (extent_start >= block_group->key.objectid +
1066
		    block_group->key.offset)
1067
			return 0;
1068

1069 1070 1071 1072
		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 已提交
1073

1074 1075
		*entries += 1;
		ret = io_ctl_add_entry(io_ctl, extent_start, len, NULL);
1076
		if (ret)
1077
			return -ENOSPC;
J
Josef Bacik 已提交
1078

1079
		start = extent_end;
1080
	}
J
Josef Bacik 已提交
1081

1082 1083 1084 1085
	return 0;
}

static noinline_for_stack int
1086
write_bitmap_entries(struct btrfs_io_ctl *io_ctl, struct list_head *bitmap_list)
1087
{
1088
	struct btrfs_free_space *entry, *next;
1089 1090
	int ret;

J
Josef Bacik 已提交
1091
	/* Write out the bitmaps */
1092
	list_for_each_entry_safe(entry, next, bitmap_list, list) {
1093
		ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);
1094
		if (ret)
1095
			return -ENOSPC;
J
Josef Bacik 已提交
1096
		list_del_init(&entry->list);
1097 1098
	}

1099 1100
	return 0;
}
J
Josef Bacik 已提交
1101

1102 1103 1104
static int flush_dirty_cache(struct inode *inode)
{
	int ret;
1105

1106
	ret = btrfs_wait_ordered_range(inode, 0, (u64)-1);
1107
	if (ret)
1108 1109 1110
		clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
				 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL,
				 GFP_NOFS);
J
Josef Bacik 已提交
1111

1112
	return ret;
1113 1114 1115
}

static void noinline_for_stack
1116
cleanup_bitmap_list(struct list_head *bitmap_list)
1117
{
1118
	struct btrfs_free_space *entry, *next;
1119

1120
	list_for_each_entry_safe(entry, next, bitmap_list, list)
1121
		list_del_init(&entry->list);
1122 1123 1124 1125 1126 1127 1128 1129
}

static void noinline_for_stack
cleanup_write_cache_enospc(struct inode *inode,
			   struct btrfs_io_ctl *io_ctl,
			   struct extent_state **cached_state,
			   struct list_head *bitmap_list)
{
1130 1131 1132 1133 1134
	io_ctl_drop_pages(io_ctl);
	unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
			     i_size_read(inode) - 1, cached_state,
			     GFP_NOFS);
}
1135

1136 1137 1138 1139 1140 1141 1142 1143 1144
int btrfs_wait_cache_io(struct btrfs_root *root,
			struct btrfs_trans_handle *trans,
			struct btrfs_block_group_cache *block_group,
			struct btrfs_io_ctl *io_ctl,
			struct btrfs_path *path, u64 offset)
{
	int ret;
	struct inode *inode = io_ctl->inode;

1145 1146 1147
	if (!inode)
		return 0;

C
Chris Mason 已提交
1148 1149
	if (block_group)
		root = root->fs_info->tree_root;
1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174

	/* Flush the dirty pages in the cache file. */
	ret = flush_dirty_cache(inode);
	if (ret)
		goto out;

	/* Update the cache item to tell everyone this cache file is valid. */
	ret = update_cache_item(trans, root, inode, path, offset,
				io_ctl->entries, io_ctl->bitmaps);
out:
	io_ctl_free(io_ctl);
	if (ret) {
		invalidate_inode_pages2(inode->i_mapping);
		BTRFS_I(inode)->generation = 0;
		if (block_group) {
#ifdef DEBUG
			btrfs_err(root->fs_info,
				"failed to write free space cache for block group %llu",
				block_group->key.objectid);
#endif
		}
	}
	btrfs_update_inode(trans, root, inode);

	if (block_group) {
1175 1176 1177 1178
		/* the dirty list is protected by the dirty_bgs_lock */
		spin_lock(&trans->transaction->dirty_bgs_lock);

		/* the disk_cache_state is protected by the block group lock */
1179 1180 1181 1182
		spin_lock(&block_group->lock);

		/*
		 * only mark this as written if we didn't get put back on
1183 1184
		 * the dirty list while waiting for IO.   Otherwise our
		 * cache state won't be right, and we won't get written again
1185 1186 1187 1188 1189 1190 1191
		 */
		if (!ret && list_empty(&block_group->dirty_list))
			block_group->disk_cache_state = BTRFS_DC_WRITTEN;
		else if (ret)
			block_group->disk_cache_state = BTRFS_DC_ERROR;

		spin_unlock(&block_group->lock);
1192
		spin_unlock(&trans->transaction->dirty_bgs_lock);
1193 1194 1195 1196 1197 1198 1199 1200
		io_ctl->inode = NULL;
		iput(inode);
	}

	return ret;

}

1201 1202 1203 1204 1205 1206 1207 1208 1209 1210
/**
 * __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
G
Geliang Tang 已提交
1211
 * on mount.  This will return 0 if it was successful in writing the cache out,
1212
 * or an errno if it was not.
1213 1214 1215 1216
 */
static 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,
1217
				   struct btrfs_io_ctl *io_ctl,
1218 1219 1220 1221
				   struct btrfs_trans_handle *trans,
				   struct btrfs_path *path, u64 offset)
{
	struct extent_state *cached_state = NULL;
1222
	LIST_HEAD(bitmap_list);
1223 1224 1225
	int entries = 0;
	int bitmaps = 0;
	int ret;
1226
	int must_iput = 0;
1227 1228

	if (!i_size_read(inode))
1229
		return -EIO;
1230

1231 1232
	WARN_ON(io_ctl->pages);
	ret = io_ctl_init(io_ctl, inode, root, 1);
1233
	if (ret)
1234
		return ret;
1235

1236 1237 1238 1239 1240 1241 1242 1243 1244
	if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) {
		down_write(&block_group->data_rwsem);
		spin_lock(&block_group->lock);
		if (block_group->delalloc_bytes) {
			block_group->disk_cache_state = BTRFS_DC_WRITTEN;
			spin_unlock(&block_group->lock);
			up_write(&block_group->data_rwsem);
			BTRFS_I(inode)->generation = 0;
			ret = 0;
1245
			must_iput = 1;
1246 1247 1248 1249 1250
			goto out;
		}
		spin_unlock(&block_group->lock);
	}

1251
	/* Lock all pages first so we can lock the extent safely. */
1252 1253 1254
	ret = io_ctl_prepare_pages(io_ctl, inode, 0);
	if (ret)
		goto out;
1255 1256

	lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,
1257
			 &cached_state);
1258

1259
	io_ctl_set_generation(io_ctl, trans->transid);
1260

1261
	mutex_lock(&ctl->cache_writeout_mutex);
1262
	/* Write out the extent entries in the free space cache */
1263
	spin_lock(&ctl->tree_lock);
1264
	ret = write_cache_extent_entries(io_ctl, ctl,
1265 1266
					 block_group, &entries, &bitmaps,
					 &bitmap_list);
1267 1268
	if (ret)
		goto out_nospc_locked;
1269

1270 1271 1272 1273
	/*
	 * Some spaces that are freed in the current transaction are pinned,
	 * they will be added into free space cache after the transaction is
	 * committed, we shouldn't lose them.
1274 1275 1276
	 *
	 * If this changes while we are working we'll get added back to
	 * the dirty list and redo it.  No locking needed
1277
	 */
1278
	ret = write_pinned_extent_entries(root, block_group, io_ctl, &entries);
1279 1280
	if (ret)
		goto out_nospc_locked;
1281

1282 1283 1284 1285 1286
	/*
	 * At last, we write out all the bitmaps and keep cache_writeout_mutex
	 * locked while doing it because a concurrent trim can be manipulating
	 * or freeing the bitmap.
	 */
1287
	ret = write_bitmap_entries(io_ctl, &bitmap_list);
1288
	spin_unlock(&ctl->tree_lock);
1289
	mutex_unlock(&ctl->cache_writeout_mutex);
1290 1291 1292 1293
	if (ret)
		goto out_nospc;

	/* Zero out the rest of the pages just to make sure */
1294
	io_ctl_zero_remaining_pages(io_ctl);
1295

1296
	/* Everything is written out, now we dirty the pages in the file. */
1297
	ret = btrfs_dirty_pages(root, inode, io_ctl->pages, io_ctl->num_pages,
1298 1299
				0, i_size_read(inode), &cached_state);
	if (ret)
1300
		goto out_nospc;
1301

1302 1303
	if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
		up_write(&block_group->data_rwsem);
1304 1305 1306 1307
	/*
	 * Release the pages and unlock the extent, we will flush
	 * them out later
	 */
1308
	io_ctl_drop_pages(io_ctl);
1309 1310 1311 1312

	unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
			     i_size_read(inode) - 1, &cached_state, GFP_NOFS);

1313 1314 1315 1316 1317 1318 1319 1320 1321
	/*
	 * at this point the pages are under IO and we're happy,
	 * The caller is responsible for waiting on them and updating the
	 * the cache and the inode
	 */
	io_ctl->entries = entries;
	io_ctl->bitmaps = bitmaps;

	ret = btrfs_fdatawrite_range(inode, 0, (u64)-1);
1322
	if (ret)
1323 1324
		goto out;

1325 1326
	return 0;

1327
out:
1328 1329
	io_ctl->inode = NULL;
	io_ctl_free(io_ctl);
1330
	if (ret) {
1331
		invalidate_inode_pages2(inode->i_mapping);
J
Josef Bacik 已提交
1332 1333 1334
		BTRFS_I(inode)->generation = 0;
	}
	btrfs_update_inode(trans, root, inode);
1335 1336
	if (must_iput)
		iput(inode);
1337
	return ret;
1338

1339 1340 1341 1342 1343
out_nospc_locked:
	cleanup_bitmap_list(&bitmap_list);
	spin_unlock(&ctl->tree_lock);
	mutex_unlock(&ctl->cache_writeout_mutex);

1344
out_nospc:
1345
	cleanup_write_cache_enospc(inode, io_ctl, &cached_state, &bitmap_list);
1346 1347 1348 1349

	if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
		up_write(&block_group->data_rwsem);

1350
	goto out;
1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366
}

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);
1367 1368
		return 0;
	}
1369 1370 1371 1372 1373 1374
	spin_unlock(&block_group->lock);

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

1375 1376
	ret = __btrfs_write_out_cache(root, inode, ctl, block_group,
				      &block_group->io_ctl, trans,
1377
				      path, block_group->key.objectid);
1378 1379
	if (ret) {
#ifdef DEBUG
1380 1381 1382
		btrfs_err(root->fs_info,
			"failed to write free space cache for block group %llu",
			block_group->key.objectid);
1383
#endif
1384 1385 1386 1387 1388 1389
		spin_lock(&block_group->lock);
		block_group->disk_cache_state = BTRFS_DC_ERROR;
		spin_unlock(&block_group->lock);

		block_group->io_ctl.inode = NULL;
		iput(inode);
1390 1391
	}

1392 1393 1394 1395 1396
	/*
	 * if ret == 0 the caller is expected to call btrfs_wait_cache_io
	 * to wait for IO and put the inode
	 */

J
Josef Bacik 已提交
1397 1398 1399
	return ret;
}

1400
static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
1401
					  u64 offset)
J
Josef Bacik 已提交
1402
{
1403
	ASSERT(offset >= bitmap_start);
1404
	offset -= bitmap_start;
1405
	return (unsigned long)(div_u64(offset, unit));
1406
}
J
Josef Bacik 已提交
1407

1408
static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
1409
{
1410
	return (unsigned long)(div_u64(bytes, unit));
1411
}
J
Josef Bacik 已提交
1412

1413
static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
1414 1415 1416
				   u64 offset)
{
	u64 bitmap_start;
1417
	u64 bytes_per_bitmap;
J
Josef Bacik 已提交
1418

1419 1420
	bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
	bitmap_start = offset - ctl->start;
1421
	bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
1422
	bitmap_start *= bytes_per_bitmap;
1423
	bitmap_start += ctl->start;
J
Josef Bacik 已提交
1424

1425
	return bitmap_start;
J
Josef Bacik 已提交
1426 1427
}

1428 1429
static int tree_insert_offset(struct rb_root *root, u64 offset,
			      struct rb_node *node, int bitmap)
J
Josef Bacik 已提交
1430 1431 1432 1433 1434 1435 1436
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct btrfs_free_space *info;

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

1439
		if (offset < info->offset) {
J
Josef Bacik 已提交
1440
			p = &(*p)->rb_left;
1441
		} else if (offset > info->offset) {
J
Josef Bacik 已提交
1442
			p = &(*p)->rb_right;
1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457
		} 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) {
1458 1459 1460 1461
				if (info->bitmap) {
					WARN_ON_ONCE(1);
					return -EEXIST;
				}
1462 1463
				p = &(*p)->rb_right;
			} else {
1464 1465 1466 1467
				if (!info->bitmap) {
					WARN_ON_ONCE(1);
					return -EEXIST;
				}
1468 1469 1470
				p = &(*p)->rb_left;
			}
		}
J
Josef Bacik 已提交
1471 1472 1473 1474 1475 1476 1477 1478 1479
	}

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

	return 0;
}

/*
J
Josef Bacik 已提交
1480 1481
 * searches the tree for the given offset.
 *
1482 1483 1484
 * 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 已提交
1485
 */
1486
static struct btrfs_free_space *
1487
tree_search_offset(struct btrfs_free_space_ctl *ctl,
1488
		   u64 offset, int bitmap_only, int fuzzy)
J
Josef Bacik 已提交
1489
{
1490
	struct rb_node *n = ctl->free_space_offset.rb_node;
1491 1492 1493 1494 1495 1496 1497 1498
	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 已提交
1499 1500

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

1503
		if (offset < entry->offset)
J
Josef Bacik 已提交
1504
			n = n->rb_left;
1505
		else if (offset > entry->offset)
J
Josef Bacik 已提交
1506
			n = n->rb_right;
1507
		else
J
Josef Bacik 已提交
1508 1509 1510
			break;
	}

1511 1512 1513 1514 1515
	if (bitmap_only) {
		if (!entry)
			return NULL;
		if (entry->bitmap)
			return entry;
J
Josef Bacik 已提交
1516

1517 1518 1519 1520 1521 1522 1523 1524 1525 1526
		/*
		 * 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 已提交
1527

1528 1529 1530 1531
		WARN_ON(!entry->bitmap);
		return entry;
	} else if (entry) {
		if (entry->bitmap) {
J
Josef Bacik 已提交
1532
			/*
1533 1534
			 * if previous extent entry covers the offset,
			 * we should return it instead of the bitmap entry
J
Josef Bacik 已提交
1535
			 */
1536 1537
			n = rb_prev(&entry->offset_index);
			if (n) {
1538 1539
				prev = rb_entry(n, struct btrfs_free_space,
						offset_index);
1540 1541 1542
				if (!prev->bitmap &&
				    prev->offset + prev->bytes > offset)
					entry = prev;
J
Josef Bacik 已提交
1543
			}
1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557
		}
		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);
1558
			ASSERT(entry->offset <= offset);
J
Josef Bacik 已提交
1559
		} else {
1560 1561 1562 1563
			if (fuzzy)
				return entry;
			else
				return NULL;
J
Josef Bacik 已提交
1564 1565 1566
		}
	}

1567
	if (entry->bitmap) {
1568 1569
		n = rb_prev(&entry->offset_index);
		if (n) {
1570 1571
			prev = rb_entry(n, struct btrfs_free_space,
					offset_index);
1572 1573 1574
			if (!prev->bitmap &&
			    prev->offset + prev->bytes > offset)
				return prev;
1575
		}
1576
		if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
1577 1578 1579 1580 1581 1582 1583 1584 1585 1586
			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 *
1587
			    ctl->unit > offset)
1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599
				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 已提交
1600 1601
}

1602
static inline void
1603
__unlink_free_space(struct btrfs_free_space_ctl *ctl,
1604
		    struct btrfs_free_space *info)
J
Josef Bacik 已提交
1605
{
1606 1607
	rb_erase(&info->offset_index, &ctl->free_space_offset);
	ctl->free_extents--;
1608 1609
}

1610
static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
1611 1612
			      struct btrfs_free_space *info)
{
1613 1614
	__unlink_free_space(ctl, info);
	ctl->free_space -= info->bytes;
J
Josef Bacik 已提交
1615 1616
}

1617
static int link_free_space(struct btrfs_free_space_ctl *ctl,
J
Josef Bacik 已提交
1618 1619 1620 1621
			   struct btrfs_free_space *info)
{
	int ret = 0;

1622
	ASSERT(info->bytes || info->bitmap);
1623
	ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
1624
				 &info->offset_index, (info->bitmap != NULL));
J
Josef Bacik 已提交
1625 1626 1627
	if (ret)
		return ret;

1628 1629
	ctl->free_space += info->bytes;
	ctl->free_extents++;
1630 1631 1632
	return ret;
}

1633
static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
1634
{
1635
	struct btrfs_block_group_cache *block_group = ctl->private;
1636 1637 1638
	u64 max_bytes;
	u64 bitmap_bytes;
	u64 extent_bytes;
1639
	u64 size = block_group->key.offset;
1640 1641
	u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;
	u64 max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);
1642

1643
	max_bitmaps = max_t(u64, max_bitmaps, 1);
1644

1645
	ASSERT(ctl->total_bitmaps <= max_bitmaps);
1646 1647 1648 1649 1650 1651

	/*
	 * 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
	 */
1652
	if (size < SZ_1G)
1653 1654
		max_bytes = MAX_CACHE_BYTES_PER_GIG;
	else
1655
		max_bytes = MAX_CACHE_BYTES_PER_GIG * div_u64(size, SZ_1G);
1656

1657 1658 1659 1660 1661
	/*
	 * 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.
	 */
1662
	bitmap_bytes = (ctl->total_bitmaps + 1) * ctl->unit;
1663

1664
	if (bitmap_bytes >= max_bytes) {
1665
		ctl->extents_thresh = 0;
1666 1667
		return;
	}
1668

1669
	/*
1670
	 * we want the extent entry threshold to always be at most 1/2 the max
1671 1672 1673
	 * bytes we can have, or whatever is less than that.
	 */
	extent_bytes = max_bytes - bitmap_bytes;
1674
	extent_bytes = min_t(u64, extent_bytes, max_bytes >> 1);
1675

1676
	ctl->extents_thresh =
1677
		div_u64(extent_bytes, sizeof(struct btrfs_free_space));
1678 1679
}

1680 1681 1682
static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
				       struct btrfs_free_space *info,
				       u64 offset, u64 bytes)
1683
{
L
Li Zefan 已提交
1684
	unsigned long start, count;
1685

1686 1687
	start = offset_to_bit(info->offset, ctl->unit, offset);
	count = bytes_to_bits(bytes, ctl->unit);
1688
	ASSERT(start + count <= BITS_PER_BITMAP);
1689

L
Li Zefan 已提交
1690
	bitmap_clear(info->bitmap, start, count);
1691 1692

	info->bytes -= bytes;
1693 1694 1695 1696 1697 1698 1699
}

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);
1700
	ctl->free_space -= bytes;
1701 1702
}

1703
static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
J
Josef Bacik 已提交
1704 1705
			    struct btrfs_free_space *info, u64 offset,
			    u64 bytes)
1706
{
L
Li Zefan 已提交
1707
	unsigned long start, count;
1708

1709 1710
	start = offset_to_bit(info->offset, ctl->unit, offset);
	count = bytes_to_bits(bytes, ctl->unit);
1711
	ASSERT(start + count <= BITS_PER_BITMAP);
1712

L
Li Zefan 已提交
1713
	bitmap_set(info->bitmap, start, count);
1714 1715

	info->bytes += bytes;
1716
	ctl->free_space += bytes;
1717 1718
}

1719 1720 1721 1722
/*
 * If we can not find suitable extent, we will use bytes to record
 * the size of the max extent.
 */
1723
static int search_bitmap(struct btrfs_free_space_ctl *ctl,
1724
			 struct btrfs_free_space *bitmap_info, u64 *offset,
1725
			 u64 *bytes, bool for_alloc)
1726 1727
{
	unsigned long found_bits = 0;
1728
	unsigned long max_bits = 0;
1729 1730
	unsigned long bits, i;
	unsigned long next_zero;
1731
	unsigned long extent_bits;
1732

1733 1734 1735 1736
	/*
	 * Skip searching the bitmap if we don't have a contiguous section that
	 * is large enough for this allocation.
	 */
1737 1738
	if (for_alloc &&
	    bitmap_info->max_extent_size &&
1739 1740 1741 1742 1743
	    bitmap_info->max_extent_size < *bytes) {
		*bytes = bitmap_info->max_extent_size;
		return -1;
	}

1744
	i = offset_to_bit(bitmap_info->offset, ctl->unit,
1745
			  max_t(u64, *offset, bitmap_info->offset));
1746
	bits = bytes_to_bits(*bytes, ctl->unit);
1747

1748
	for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
1749 1750 1751 1752
		if (for_alloc && bits == 1) {
			found_bits = 1;
			break;
		}
1753 1754
		next_zero = find_next_zero_bit(bitmap_info->bitmap,
					       BITS_PER_BITMAP, i);
1755 1756 1757
		extent_bits = next_zero - i;
		if (extent_bits >= bits) {
			found_bits = extent_bits;
1758
			break;
1759 1760
		} else if (extent_bits > max_bits) {
			max_bits = extent_bits;
1761 1762 1763 1764 1765
		}
		i = next_zero;
	}

	if (found_bits) {
1766 1767
		*offset = (u64)(i * ctl->unit) + bitmap_info->offset;
		*bytes = (u64)(found_bits) * ctl->unit;
1768 1769 1770
		return 0;
	}

1771
	*bytes = (u64)(max_bits) * ctl->unit;
1772
	bitmap_info->max_extent_size = *bytes;
1773 1774 1775
	return -1;
}

1776
/* Cache the size of the max extent in bytes */
1777
static struct btrfs_free_space *
D
David Woodhouse 已提交
1778
find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
1779
		unsigned long align, u64 *max_extent_size)
1780 1781 1782
{
	struct btrfs_free_space *entry;
	struct rb_node *node;
D
David Woodhouse 已提交
1783 1784
	u64 tmp;
	u64 align_off;
1785 1786
	int ret;

1787
	if (!ctl->free_space_offset.rb_node)
1788
		goto out;
1789

1790
	entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
1791
	if (!entry)
1792
		goto out;
1793 1794 1795

	for (node = &entry->offset_index; node; node = rb_next(node)) {
		entry = rb_entry(node, struct btrfs_free_space, offset_index);
1796 1797 1798
		if (entry->bytes < *bytes) {
			if (entry->bytes > *max_extent_size)
				*max_extent_size = entry->bytes;
1799
			continue;
1800
		}
1801

D
David Woodhouse 已提交
1802 1803 1804 1805
		/* make sure the space returned is big enough
		 * to match our requested alignment
		 */
		if (*bytes >= align) {
1806
			tmp = entry->offset - ctl->start + align - 1;
1807
			tmp = div64_u64(tmp, align);
D
David Woodhouse 已提交
1808 1809 1810 1811 1812 1813 1814
			tmp = tmp * align + ctl->start;
			align_off = tmp - entry->offset;
		} else {
			align_off = 0;
			tmp = entry->offset;
		}

1815 1816 1817
		if (entry->bytes < *bytes + align_off) {
			if (entry->bytes > *max_extent_size)
				*max_extent_size = entry->bytes;
D
David Woodhouse 已提交
1818
			continue;
1819
		}
D
David Woodhouse 已提交
1820

1821
		if (entry->bitmap) {
1822 1823
			u64 size = *bytes;

1824
			ret = search_bitmap(ctl, entry, &tmp, &size, true);
D
David Woodhouse 已提交
1825 1826
			if (!ret) {
				*offset = tmp;
1827
				*bytes = size;
1828
				return entry;
1829 1830
			} else if (size > *max_extent_size) {
				*max_extent_size = size;
D
David Woodhouse 已提交
1831
			}
1832 1833 1834
			continue;
		}

D
David Woodhouse 已提交
1835 1836
		*offset = tmp;
		*bytes = entry->bytes - align_off;
1837 1838
		return entry;
	}
1839
out:
1840 1841 1842
	return NULL;
}

1843
static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
1844 1845
			   struct btrfs_free_space *info, u64 offset)
{
1846
	info->offset = offset_to_bitmap(ctl, offset);
J
Josef Bacik 已提交
1847
	info->bytes = 0;
1848
	INIT_LIST_HEAD(&info->list);
1849 1850
	link_free_space(ctl, info);
	ctl->total_bitmaps++;
1851

1852
	ctl->op->recalc_thresholds(ctl);
1853 1854
}

1855
static void free_bitmap(struct btrfs_free_space_ctl *ctl,
1856 1857
			struct btrfs_free_space *bitmap_info)
{
1858
	unlink_free_space(ctl, bitmap_info);
1859
	kfree(bitmap_info->bitmap);
1860
	kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
1861 1862
	ctl->total_bitmaps--;
	ctl->op->recalc_thresholds(ctl);
1863 1864
}

1865
static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
1866 1867 1868 1869
			      struct btrfs_free_space *bitmap_info,
			      u64 *offset, u64 *bytes)
{
	u64 end;
1870 1871
	u64 search_start, search_bytes;
	int ret;
1872 1873

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

1876
	/*
1877 1878 1879 1880
	 * 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.
1881 1882
	 */
	search_start = *offset;
1883
	search_bytes = ctl->unit;
1884
	search_bytes = min(search_bytes, end - search_start + 1);
1885 1886
	ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes,
			    false);
1887 1888
	if (ret < 0 || search_start != *offset)
		return -EINVAL;
1889

1890 1891 1892 1893 1894 1895 1896 1897 1898
	/* 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;
1899 1900

	if (*bytes) {
1901
		struct rb_node *next = rb_next(&bitmap_info->offset_index);
1902
		if (!bitmap_info->bytes)
1903
			free_bitmap(ctl, bitmap_info);
1904

1905 1906 1907 1908 1909
		/*
		 * no entry after this bitmap, but we still have bytes to
		 * remove, so something has gone wrong.
		 */
		if (!next)
1910 1911
			return -EINVAL;

1912 1913 1914 1915 1916 1917 1918
		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.
		 */
1919 1920 1921
		if (!bitmap_info->bitmap)
			return -EAGAIN;

1922 1923 1924 1925 1926 1927 1928
		/*
		 * 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;
1929
		search_bytes = ctl->unit;
1930
		ret = search_bitmap(ctl, bitmap_info, &search_start,
1931
				    &search_bytes, false);
1932 1933 1934
		if (ret < 0 || search_start != *offset)
			return -EAGAIN;

1935
		goto again;
1936
	} else if (!bitmap_info->bytes)
1937
		free_bitmap(ctl, bitmap_info);
1938 1939 1940 1941

	return 0;
}

J
Josef Bacik 已提交
1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954
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);

1955 1956 1957 1958 1959 1960
	/*
	 * We set some bytes, we have no idea what the max extent size is
	 * anymore.
	 */
	info->max_extent_size = 0;

J
Josef Bacik 已提交
1961 1962 1963 1964
	return bytes_to_set;

}

1965 1966
static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
		      struct btrfs_free_space *info)
1967
{
1968
	struct btrfs_block_group_cache *block_group = ctl->private;
1969 1970 1971 1972 1973 1974 1975
	bool forced = false;

#ifdef CONFIG_BTRFS_DEBUG
	if (btrfs_should_fragment_free_space(block_group->fs_info->extent_root,
					     block_group))
		forced = true;
#endif
1976 1977 1978 1979 1980

	/*
	 * If we are below the extents threshold then we can add this as an
	 * extent, and don't have to deal with the bitmap
	 */
1981
	if (!forced && ctl->free_extents < ctl->extents_thresh) {
1982 1983 1984
		/*
		 * 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
1985
		 * to reserve them to larger extents, however if we have plenty
1986 1987 1988 1989
		 * 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) {
1990 1991
			if (ctl->free_extents * 2 <= ctl->extents_thresh)
				return false;
1992
		} else {
1993
			return false;
1994 1995
		}
	}
1996 1997

	/*
1998 1999 2000 2001 2002 2003
	 * 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.
2004
	 */
2005
	if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->key.offset)
2006 2007 2008 2009 2010
		return false;

	return true;
}

2011
static const struct btrfs_free_space_op free_space_op = {
J
Josef Bacik 已提交
2012 2013 2014 2015
	.recalc_thresholds	= recalculate_thresholds,
	.use_bitmap		= use_bitmap,
};

2016 2017 2018 2019
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 已提交
2020
	struct btrfs_block_group_cache *block_group = NULL;
2021
	int added = 0;
J
Josef Bacik 已提交
2022
	u64 bytes, offset, bytes_added;
2023
	int ret;
2024 2025 2026 2027

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

2028 2029 2030
	if (!ctl->op->use_bitmap(ctl, info))
		return 0;

J
Josef Bacik 已提交
2031 2032
	if (ctl->op == &free_space_op)
		block_group = ctl->private;
2033
again:
J
Josef Bacik 已提交
2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050
	/*
	 * 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);
2051
			goto no_cluster_bitmap;
J
Josef Bacik 已提交
2052 2053 2054 2055 2056
		}

		entry = rb_entry(node, struct btrfs_free_space, offset_index);
		if (!entry->bitmap) {
			spin_unlock(&cluster->lock);
2057
			goto no_cluster_bitmap;
J
Josef Bacik 已提交
2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071
		}

		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;
		}
	}
2072 2073

no_cluster_bitmap:
2074
	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
2075 2076
					 1, 0);
	if (!bitmap_info) {
2077
		ASSERT(added == 0);
2078 2079 2080
		goto new_bitmap;
	}

J
Josef Bacik 已提交
2081 2082 2083 2084
	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
	bytes -= bytes_added;
	offset += bytes_added;
	added = 0;
2085 2086 2087 2088 2089 2090 2091 2092 2093

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

new_bitmap:
	if (info && info->bitmap) {
2094
		add_new_bitmap(ctl, info, offset);
2095 2096 2097 2098
		added = 1;
		info = NULL;
		goto again;
	} else {
2099
		spin_unlock(&ctl->tree_lock);
2100 2101 2102

		/* no pre-allocated info, allocate a new one */
		if (!info) {
2103 2104
			info = kmem_cache_zalloc(btrfs_free_space_cachep,
						 GFP_NOFS);
2105
			if (!info) {
2106
				spin_lock(&ctl->tree_lock);
2107 2108 2109 2110 2111 2112
				ret = -ENOMEM;
				goto out;
			}
		}

		/* allocate the bitmap */
2113
		info->bitmap = kzalloc(PAGE_SIZE, GFP_NOFS);
2114
		spin_lock(&ctl->tree_lock);
2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125
		if (!info->bitmap) {
			ret = -ENOMEM;
			goto out;
		}
		goto again;
	}

out:
	if (info) {
		if (info->bitmap)
			kfree(info->bitmap);
2126
		kmem_cache_free(btrfs_free_space_cachep, info);
2127
	}
J
Josef Bacik 已提交
2128 2129 2130 2131

	return ret;
}

2132
static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
2133
			  struct btrfs_free_space *info, bool update_stat)
J
Josef Bacik 已提交
2134
{
2135 2136 2137 2138 2139
	struct btrfs_free_space *left_info;
	struct btrfs_free_space *right_info;
	bool merged = false;
	u64 offset = info->offset;
	u64 bytes = info->bytes;
2140

J
Josef Bacik 已提交
2141 2142 2143 2144 2145
	/*
	 * 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
	 */
2146
	right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
2147 2148 2149 2150
	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
2151
		left_info = tree_search_offset(ctl, offset - 1, 0, 0);
J
Josef Bacik 已提交
2152

2153
	if (right_info && !right_info->bitmap) {
2154
		if (update_stat)
2155
			unlink_free_space(ctl, right_info);
2156
		else
2157
			__unlink_free_space(ctl, right_info);
2158
		info->bytes += right_info->bytes;
2159
		kmem_cache_free(btrfs_free_space_cachep, right_info);
2160
		merged = true;
J
Josef Bacik 已提交
2161 2162
	}

2163 2164
	if (left_info && !left_info->bitmap &&
	    left_info->offset + left_info->bytes == offset) {
2165
		if (update_stat)
2166
			unlink_free_space(ctl, left_info);
2167
		else
2168
			__unlink_free_space(ctl, left_info);
2169 2170
		info->offset = left_info->offset;
		info->bytes += left_info->bytes;
2171
		kmem_cache_free(btrfs_free_space_cachep, left_info);
2172
		merged = true;
J
Josef Bacik 已提交
2173 2174
	}

2175 2176 2177
	return merged;
}

2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299
static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
				     struct btrfs_free_space *info,
				     bool update_stat)
{
	struct btrfs_free_space *bitmap;
	unsigned long i;
	unsigned long j;
	const u64 end = info->offset + info->bytes;
	const u64 bitmap_offset = offset_to_bitmap(ctl, end);
	u64 bytes;

	bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
	if (!bitmap)
		return false;

	i = offset_to_bit(bitmap->offset, ctl->unit, end);
	j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i);
	if (j == i)
		return false;
	bytes = (j - i) * ctl->unit;
	info->bytes += bytes;

	if (update_stat)
		bitmap_clear_bits(ctl, bitmap, end, bytes);
	else
		__bitmap_clear_bits(ctl, bitmap, end, bytes);

	if (!bitmap->bytes)
		free_bitmap(ctl, bitmap);

	return true;
}

static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
				       struct btrfs_free_space *info,
				       bool update_stat)
{
	struct btrfs_free_space *bitmap;
	u64 bitmap_offset;
	unsigned long i;
	unsigned long j;
	unsigned long prev_j;
	u64 bytes;

	bitmap_offset = offset_to_bitmap(ctl, info->offset);
	/* If we're on a boundary, try the previous logical bitmap. */
	if (bitmap_offset == info->offset) {
		if (info->offset == 0)
			return false;
		bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);
	}

	bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
	if (!bitmap)
		return false;

	i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;
	j = 0;
	prev_j = (unsigned long)-1;
	for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
		if (j > i)
			break;
		prev_j = j;
	}
	if (prev_j == i)
		return false;

	if (prev_j == (unsigned long)-1)
		bytes = (i + 1) * ctl->unit;
	else
		bytes = (i - prev_j) * ctl->unit;

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

	if (update_stat)
		bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
	else
		__bitmap_clear_bits(ctl, bitmap, info->offset, bytes);

	if (!bitmap->bytes)
		free_bitmap(ctl, bitmap);

	return true;
}

/*
 * We prefer always to allocate from extent entries, both for clustered and
 * non-clustered allocation requests. So when attempting to add a new extent
 * entry, try to see if there's adjacent free space in bitmap entries, and if
 * there is, migrate that space from the bitmaps to the extent.
 * Like this we get better chances of satisfying space allocation requests
 * because we attempt to satisfy them based on a single cache entry, and never
 * on 2 or more entries - even if the entries represent a contiguous free space
 * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry
 * ends).
 */
static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,
			      struct btrfs_free_space *info,
			      bool update_stat)
{
	/*
	 * Only work with disconnected entries, as we can change their offset,
	 * and must be extent entries.
	 */
	ASSERT(!info->bitmap);
	ASSERT(RB_EMPTY_NODE(&info->offset_index));

	if (ctl->total_bitmaps > 0) {
		bool stole_end;
		bool stole_front = false;

		stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);
		if (ctl->total_bitmaps > 0)
			stole_front = steal_from_bitmap_to_front(ctl, info,
								 update_stat);

		if (stole_end || stole_front)
			try_merge_free_space(ctl, info, update_stat);
	}
}

2300 2301
int __btrfs_add_free_space(struct btrfs_fs_info *fs_info,
			   struct btrfs_free_space_ctl *ctl,
2302
			   u64 offset, u64 bytes)
2303 2304 2305 2306
{
	struct btrfs_free_space *info;
	int ret = 0;

2307
	info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
2308 2309 2310 2311 2312
	if (!info)
		return -ENOMEM;

	info->offset = offset;
	info->bytes = bytes;
2313
	RB_CLEAR_NODE(&info->offset_index);
2314

2315
	spin_lock(&ctl->tree_lock);
2316

2317
	if (try_merge_free_space(ctl, info, true))
2318 2319 2320 2321 2322 2323 2324
		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
	 */
2325
	ret = insert_into_bitmap(ctl, info);
2326 2327 2328 2329 2330 2331 2332
	if (ret < 0) {
		goto out;
	} else if (ret) {
		ret = 0;
		goto out;
	}
link:
2333 2334 2335 2336 2337 2338 2339 2340
	/*
	 * Only steal free space from adjacent bitmaps if we're sure we're not
	 * going to add the new free space to existing bitmap entries - because
	 * that would mean unnecessary work that would be reverted. Therefore
	 * attempt to steal space from bitmaps if we're adding an extent entry.
	 */
	steal_from_bitmap(ctl, info, true);

2341
	ret = link_free_space(ctl, info);
J
Josef Bacik 已提交
2342
	if (ret)
2343
		kmem_cache_free(btrfs_free_space_cachep, info);
2344
out:
2345
	spin_unlock(&ctl->tree_lock);
2346

J
Josef Bacik 已提交
2347
	if (ret) {
2348
		btrfs_crit(fs_info, "unable to add free space :%d", ret);
2349
		ASSERT(ret != -EEXIST);
J
Josef Bacik 已提交
2350 2351 2352 2353 2354
	}

	return ret;
}

2355 2356
int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
			    u64 offset, u64 bytes)
J
Josef Bacik 已提交
2357
{
2358
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
J
Josef Bacik 已提交
2359
	struct btrfs_free_space *info;
2360 2361
	int ret;
	bool re_search = false;
J
Josef Bacik 已提交
2362

2363
	spin_lock(&ctl->tree_lock);
2364

2365
again:
2366
	ret = 0;
2367 2368 2369
	if (!bytes)
		goto out_lock;

2370
	info = tree_search_offset(ctl, offset, 0, 0);
2371
	if (!info) {
2372 2373 2374 2375
		/*
		 * oops didn't find an extent that matched the space we wanted
		 * to remove, look for a bitmap instead
		 */
2376
		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
2377 2378
					  1, 0);
		if (!info) {
2379 2380 2381 2382
			/*
			 * 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.
2383
			 */
2384
			WARN_ON(re_search);
2385 2386
			goto out_lock;
		}
2387 2388
	}

2389
	re_search = false;
2390
	if (!info->bitmap) {
2391
		unlink_free_space(ctl, info);
2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402
		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 已提交
2403

2404 2405 2406 2407 2408
			offset += to_free;
			bytes -= to_free;
			goto again;
		} else {
			u64 old_end = info->bytes + info->offset;
2409

2410
			info->bytes = offset - info->offset;
2411
			ret = link_free_space(ctl, info);
2412 2413 2414 2415
			WARN_ON(ret);
			if (ret)
				goto out_lock;

2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431
			/* 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 已提交
2432
	}
2433

2434
	ret = remove_from_bitmap(ctl, info, &offset, &bytes);
2435 2436
	if (ret == -EAGAIN) {
		re_search = true;
2437
		goto again;
2438
	}
2439
out_lock:
2440
	spin_unlock(&ctl->tree_lock);
J
Josef Bacik 已提交
2441
out:
2442 2443 2444
	return ret;
}

J
Josef Bacik 已提交
2445 2446 2447
void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
			   u64 bytes)
{
2448
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
J
Josef Bacik 已提交
2449 2450 2451 2452
	struct btrfs_free_space *info;
	struct rb_node *n;
	int count = 0;

2453
	for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
J
Josef Bacik 已提交
2454
		info = rb_entry(n, struct btrfs_free_space, offset_index);
L
Liu Bo 已提交
2455
		if (info->bytes >= bytes && !block_group->ro)
J
Josef Bacik 已提交
2456
			count++;
2457 2458 2459
		btrfs_crit(block_group->fs_info,
			   "entry offset %llu, bytes %llu, bitmap %s",
			   info->offset, info->bytes,
2460
		       (info->bitmap) ? "yes" : "no");
J
Josef Bacik 已提交
2461
	}
2462
	btrfs_info(block_group->fs_info, "block group has cluster?: %s",
2463
	       list_empty(&block_group->cluster_list) ? "no" : "yes");
2464 2465
	btrfs_info(block_group->fs_info,
		   "%d blocks of free space at or bigger than bytes is", count);
J
Josef Bacik 已提交
2466 2467
}

2468
void btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group)
J
Josef Bacik 已提交
2469
{
2470
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
J
Josef Bacik 已提交
2471

2472 2473 2474 2475 2476
	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;
2477 2478
	INIT_LIST_HEAD(&ctl->trimming_ranges);
	mutex_init(&ctl->cache_writeout_mutex);
J
Josef Bacik 已提交
2479

2480 2481 2482 2483 2484
	/*
	 * 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
	 */
2485
	ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space);
J
Josef Bacik 已提交
2486 2487
}

2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498
/*
 * 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)
{
2499
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2500 2501 2502 2503 2504 2505 2506
	struct btrfs_free_space *entry;
	struct rb_node *node;

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

2507
	cluster->block_group = NULL;
2508
	cluster->window_start = 0;
2509 2510
	list_del_init(&cluster->block_group_list);

2511
	node = rb_first(&cluster->root);
2512
	while (node) {
2513 2514
		bool bitmap;

2515 2516 2517
		entry = rb_entry(node, struct btrfs_free_space, offset_index);
		node = rb_next(&entry->offset_index);
		rb_erase(&entry->offset_index, &cluster->root);
2518
		RB_CLEAR_NODE(&entry->offset_index);
2519 2520

		bitmap = (entry->bitmap != NULL);
2521
		if (!bitmap) {
2522
			try_merge_free_space(ctl, entry, false);
2523 2524
			steal_from_bitmap(ctl, entry, false);
		}
2525
		tree_insert_offset(&ctl->free_space_offset,
2526
				   entry->offset, &entry->offset_index, bitmap);
2527
	}
2528
	cluster->root = RB_ROOT;
2529

2530 2531
out:
	spin_unlock(&cluster->lock);
2532
	btrfs_put_block_group(block_group);
2533 2534 2535
	return 0;
}

2536 2537
static void __btrfs_remove_free_space_cache_locked(
				struct btrfs_free_space_ctl *ctl)
J
Josef Bacik 已提交
2538 2539 2540
{
	struct btrfs_free_space *info;
	struct rb_node *node;
2541 2542 2543

	while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
		info = rb_entry(node, struct btrfs_free_space, offset_index);
2544 2545 2546 2547 2548 2549
		if (!info->bitmap) {
			unlink_free_space(ctl, info);
			kmem_cache_free(btrfs_free_space_cachep, info);
		} else {
			free_bitmap(ctl, info);
		}
2550 2551

		cond_resched_lock(&ctl->tree_lock);
2552
	}
2553 2554 2555 2556 2557 2558
}

void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
{
	spin_lock(&ctl->tree_lock);
	__btrfs_remove_free_space_cache_locked(ctl);
2559 2560 2561 2562 2563 2564
	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;
2565
	struct btrfs_free_cluster *cluster;
2566
	struct list_head *head;
J
Josef Bacik 已提交
2567

2568
	spin_lock(&ctl->tree_lock);
2569 2570 2571 2572
	while ((head = block_group->cluster_list.next) !=
	       &block_group->cluster_list) {
		cluster = list_entry(head, struct btrfs_free_cluster,
				     block_group_list);
2573 2574 2575

		WARN_ON(cluster->block_group != block_group);
		__btrfs_return_cluster_to_free_space(block_group, cluster);
2576 2577

		cond_resched_lock(&ctl->tree_lock);
2578
	}
2579
	__btrfs_remove_free_space_cache_locked(ctl);
2580
	spin_unlock(&ctl->tree_lock);
2581

J
Josef Bacik 已提交
2582 2583
}

2584
u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
2585 2586
			       u64 offset, u64 bytes, u64 empty_size,
			       u64 *max_extent_size)
J
Josef Bacik 已提交
2587
{
2588
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2589
	struct btrfs_free_space *entry = NULL;
2590
	u64 bytes_search = bytes + empty_size;
2591
	u64 ret = 0;
D
David Woodhouse 已提交
2592 2593
	u64 align_gap = 0;
	u64 align_gap_len = 0;
J
Josef Bacik 已提交
2594

2595
	spin_lock(&ctl->tree_lock);
D
David Woodhouse 已提交
2596
	entry = find_free_space(ctl, &offset, &bytes_search,
2597
				block_group->full_stripe_len, max_extent_size);
2598
	if (!entry)
2599 2600 2601 2602
		goto out;

	ret = offset;
	if (entry->bitmap) {
2603
		bitmap_clear_bits(ctl, entry, offset, bytes);
2604
		if (!entry->bytes)
2605
			free_bitmap(ctl, entry);
2606
	} else {
2607
		unlink_free_space(ctl, entry);
D
David Woodhouse 已提交
2608 2609 2610 2611 2612 2613 2614
		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;
2615
		if (!entry->bytes)
2616
			kmem_cache_free(btrfs_free_space_cachep, entry);
2617
		else
2618
			link_free_space(ctl, entry);
2619
	}
2620
out:
2621
	spin_unlock(&ctl->tree_lock);
J
Josef Bacik 已提交
2622

D
David Woodhouse 已提交
2623
	if (align_gap_len)
2624 2625
		__btrfs_add_free_space(block_group->fs_info, ctl,
				       align_gap, align_gap_len);
J
Josef Bacik 已提交
2626 2627
	return ret;
}
2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640

/*
 * 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)
{
2641
	struct btrfs_free_space_ctl *ctl;
2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659
	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);

2660 2661
	ctl = block_group->free_space_ctl;

2662
	/* now return any extents the cluster had on it */
2663
	spin_lock(&ctl->tree_lock);
2664
	ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
2665
	spin_unlock(&ctl->tree_lock);
2666 2667 2668 2669 2670 2671

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

2672 2673
static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
				   struct btrfs_free_cluster *cluster,
2674
				   struct btrfs_free_space *entry,
2675 2676
				   u64 bytes, u64 min_start,
				   u64 *max_extent_size)
2677
{
2678
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2679 2680 2681 2682 2683 2684 2685 2686
	int err;
	u64 search_start = cluster->window_start;
	u64 search_bytes = bytes;
	u64 ret = 0;

	search_start = min_start;
	search_bytes = bytes;

2687
	err = search_bitmap(ctl, entry, &search_start, &search_bytes, true);
2688 2689 2690
	if (err) {
		if (search_bytes > *max_extent_size)
			*max_extent_size = search_bytes;
2691
		return 0;
2692
	}
2693 2694

	ret = search_start;
2695
	__bitmap_clear_bits(ctl, entry, ret, bytes);
2696 2697 2698 2699

	return ret;
}

2700 2701 2702 2703 2704 2705 2706
/*
 * 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,
2707
			     u64 min_start, u64 *max_extent_size)
2708
{
2709
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725
	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);
2726
	while (1) {
2727 2728 2729
		if (entry->bytes < bytes && entry->bytes > *max_extent_size)
			*max_extent_size = entry->bytes;

2730 2731
		if (entry->bytes < bytes ||
		    (!entry->bitmap && entry->offset < min_start)) {
2732 2733 2734 2735 2736 2737 2738 2739
			node = rb_next(&entry->offset_index);
			if (!node)
				break;
			entry = rb_entry(node, struct btrfs_free_space,
					 offset_index);
			continue;
		}

2740 2741 2742
		if (entry->bitmap) {
			ret = btrfs_alloc_from_bitmap(block_group,
						      cluster, entry, bytes,
2743 2744
						      cluster->window_start,
						      max_extent_size);
2745 2746 2747 2748 2749 2750 2751 2752
			if (ret == 0) {
				node = rb_next(&entry->offset_index);
				if (!node)
					break;
				entry = rb_entry(node, struct btrfs_free_space,
						 offset_index);
				continue;
			}
2753
			cluster->window_start += bytes;
2754 2755 2756 2757 2758 2759
		} else {
			ret = entry->offset;

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

2761
		if (entry->bytes == 0)
2762 2763 2764 2765 2766
			rb_erase(&entry->offset_index, &cluster->root);
		break;
	}
out:
	spin_unlock(&cluster->lock);
2767

2768 2769 2770
	if (!ret)
		return 0;

2771
	spin_lock(&ctl->tree_lock);
2772

2773
	ctl->free_space -= bytes;
2774
	if (entry->bytes == 0) {
2775
		ctl->free_extents--;
2776 2777
		if (entry->bitmap) {
			kfree(entry->bitmap);
2778 2779
			ctl->total_bitmaps--;
			ctl->op->recalc_thresholds(ctl);
2780
		}
2781
		kmem_cache_free(btrfs_free_space_cachep, entry);
2782 2783
	}

2784
	spin_unlock(&ctl->tree_lock);
2785

2786 2787 2788
	return ret;
}

2789 2790 2791
static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group,
				struct btrfs_free_space *entry,
				struct btrfs_free_cluster *cluster,
2792 2793
				u64 offset, u64 bytes,
				u64 cont1_bytes, u64 min_bytes)
2794
{
2795
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2796 2797
	unsigned long next_zero;
	unsigned long i;
2798 2799
	unsigned long want_bits;
	unsigned long min_bits;
2800
	unsigned long found_bits;
2801
	unsigned long max_bits = 0;
2802 2803
	unsigned long start = 0;
	unsigned long total_found = 0;
2804
	int ret;
2805

2806
	i = offset_to_bit(entry->offset, ctl->unit,
2807
			  max_t(u64, offset, entry->offset));
2808 2809
	want_bits = bytes_to_bits(bytes, ctl->unit);
	min_bits = bytes_to_bits(min_bytes, ctl->unit);
2810

2811 2812 2813 2814 2815 2816 2817
	/*
	 * Don't bother looking for a cluster in this bitmap if it's heavily
	 * fragmented.
	 */
	if (entry->max_extent_size &&
	    entry->max_extent_size < cont1_bytes)
		return -ENOSPC;
2818 2819
again:
	found_bits = 0;
2820
	for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {
2821 2822
		next_zero = find_next_zero_bit(entry->bitmap,
					       BITS_PER_BITMAP, i);
2823
		if (next_zero - i >= min_bits) {
2824
			found_bits = next_zero - i;
2825 2826
			if (found_bits > max_bits)
				max_bits = found_bits;
2827 2828
			break;
		}
2829 2830
		if (next_zero - i > max_bits)
			max_bits = next_zero - i;
2831 2832 2833
		i = next_zero;
	}

2834 2835
	if (!found_bits) {
		entry->max_extent_size = (u64)max_bits * ctl->unit;
2836
		return -ENOSPC;
2837
	}
2838

2839
	if (!total_found) {
2840
		start = i;
2841
		cluster->max_size = 0;
2842 2843 2844 2845
	}

	total_found += found_bits;

2846 2847
	if (cluster->max_size < found_bits * ctl->unit)
		cluster->max_size = found_bits * ctl->unit;
2848

2849 2850
	if (total_found < want_bits || cluster->max_size < cont1_bytes) {
		i = next_zero + 1;
2851 2852 2853
		goto again;
	}

2854
	cluster->window_start = start * ctl->unit + entry->offset;
2855
	rb_erase(&entry->offset_index, &ctl->free_space_offset);
2856 2857
	ret = tree_insert_offset(&cluster->root, entry->offset,
				 &entry->offset_index, 1);
2858
	ASSERT(!ret); /* -EEXIST; Logic error */
2859

J
Josef Bacik 已提交
2860
	trace_btrfs_setup_cluster(block_group, cluster,
2861
				  total_found * ctl->unit, 1);
2862 2863 2864
	return 0;
}

2865 2866
/*
 * This searches the block group for just extents to fill the cluster with.
2867 2868
 * 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.
2869
 */
2870 2871 2872 2873
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,
2874
			u64 cont1_bytes, u64 min_bytes)
2875
{
2876
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2877 2878 2879 2880 2881 2882
	struct btrfs_free_space *first = NULL;
	struct btrfs_free_space *entry = NULL;
	struct btrfs_free_space *last;
	struct rb_node *node;
	u64 window_free;
	u64 max_extent;
J
Josef Bacik 已提交
2883
	u64 total_size = 0;
2884

2885
	entry = tree_search_offset(ctl, offset, 0, 1);
2886 2887 2888 2889 2890 2891 2892
	if (!entry)
		return -ENOSPC;

	/*
	 * We don't want bitmaps, so just move along until we find a normal
	 * extent entry.
	 */
2893 2894
	while (entry->bitmap || entry->bytes < min_bytes) {
		if (entry->bitmap && list_empty(&entry->list))
2895
			list_add_tail(&entry->list, bitmaps);
2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906
		node = rb_next(&entry->offset_index);
		if (!node)
			return -ENOSPC;
		entry = rb_entry(node, struct btrfs_free_space, offset_index);
	}

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

2907 2908
	for (node = rb_next(&entry->offset_index); node;
	     node = rb_next(&entry->offset_index)) {
2909 2910
		entry = rb_entry(node, struct btrfs_free_space, offset_index);

2911 2912 2913
		if (entry->bitmap) {
			if (list_empty(&entry->list))
				list_add_tail(&entry->list, bitmaps);
2914
			continue;
2915 2916
		}

2917 2918 2919 2920 2921 2922
		if (entry->bytes < min_bytes)
			continue;

		last = entry;
		window_free += entry->bytes;
		if (entry->bytes > max_extent)
2923 2924 2925
			max_extent = entry->bytes;
	}

2926 2927 2928
	if (window_free < bytes || max_extent < cont1_bytes)
		return -ENOSPC;

2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941
	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);
2942
		if (entry->bitmap || entry->bytes < min_bytes)
2943 2944
			continue;

2945
		rb_erase(&entry->offset_index, &ctl->free_space_offset);
2946 2947
		ret = tree_insert_offset(&cluster->root, entry->offset,
					 &entry->offset_index, 0);
J
Josef Bacik 已提交
2948
		total_size += entry->bytes;
2949
		ASSERT(!ret); /* -EEXIST; Logic error */
2950 2951 2952
	} while (node && entry != last);

	cluster->max_size = max_extent;
J
Josef Bacik 已提交
2953
	trace_btrfs_setup_cluster(block_group, cluster, total_size, 0);
2954 2955 2956 2957 2958 2959 2960
	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.
 */
2961 2962 2963 2964
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,
2965
		     u64 cont1_bytes, u64 min_bytes)
2966
{
2967
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2968
	struct btrfs_free_space *entry = NULL;
2969
	int ret = -ENOSPC;
2970
	u64 bitmap_offset = offset_to_bitmap(ctl, offset);
2971

2972
	if (ctl->total_bitmaps == 0)
2973 2974
		return -ENOSPC;

2975 2976 2977 2978
	/*
	 * The bitmap that covers offset won't be in the list unless offset
	 * is just its start offset.
	 */
2979 2980 2981 2982
	if (!list_empty(bitmaps))
		entry = list_first_entry(bitmaps, struct btrfs_free_space, list);

	if (!entry || entry->offset != bitmap_offset) {
2983 2984 2985 2986 2987
		entry = tree_search_offset(ctl, bitmap_offset, 1, 0);
		if (entry && list_empty(&entry->list))
			list_add(&entry->list, bitmaps);
	}

2988
	list_for_each_entry(entry, bitmaps, list) {
2989
		if (entry->bytes < bytes)
2990 2991
			continue;
		ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
2992
					   bytes, cont1_bytes, min_bytes);
2993 2994 2995 2996 2997
		if (!ret)
			return 0;
	}

	/*
2998 2999
	 * The bitmaps list has all the bitmaps that record free space
	 * starting after offset, so no more search is required.
3000
	 */
3001
	return -ENOSPC;
3002 3003
}

3004 3005
/*
 * here we try to find a cluster of blocks in a block group.  The goal
3006
 * is to find at least bytes+empty_size.
3007 3008 3009 3010 3011
 * We might not find them all in one contiguous area.
 *
 * returns zero and sets up cluster if things worked out, otherwise
 * it returns -enospc
 */
3012
int btrfs_find_space_cluster(struct btrfs_root *root,
3013 3014 3015 3016
			     struct btrfs_block_group_cache *block_group,
			     struct btrfs_free_cluster *cluster,
			     u64 offset, u64 bytes, u64 empty_size)
{
3017
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3018
	struct btrfs_free_space *entry, *tmp;
3019
	LIST_HEAD(bitmaps);
3020
	u64 min_bytes;
3021
	u64 cont1_bytes;
3022 3023
	int ret;

3024 3025 3026 3027 3028 3029
	/*
	 * 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.
	 */
3030
	if (btrfs_test_opt(root->fs_info, SSD_SPREAD)) {
3031
		cont1_bytes = min_bytes = bytes + empty_size;
3032
	} else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
3033 3034 3035 3036 3037 3038
		cont1_bytes = bytes;
		min_bytes = block_group->sectorsize;
	} else {
		cont1_bytes = max(bytes, (bytes + empty_size) >> 2);
		min_bytes = block_group->sectorsize;
	}
3039

3040
	spin_lock(&ctl->tree_lock);
3041 3042 3043 3044 3045

	/*
	 * 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.
	 */
3046
	if (ctl->free_space < bytes) {
3047
		spin_unlock(&ctl->tree_lock);
3048 3049 3050
		return -ENOSPC;
	}

3051 3052 3053 3054 3055 3056 3057 3058
	spin_lock(&cluster->lock);

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

J
Josef Bacik 已提交
3059 3060 3061
	trace_btrfs_find_cluster(block_group, offset, bytes, empty_size,
				 min_bytes);

3062
	ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
3063 3064
				      bytes + empty_size,
				      cont1_bytes, min_bytes);
3065
	if (ret)
3066
		ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
3067 3068
					   offset, bytes + empty_size,
					   cont1_bytes, min_bytes);
3069 3070 3071 3072

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

3074 3075 3076 3077 3078
	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 已提交
3079 3080
	} else {
		trace_btrfs_failed_cluster_setup(block_group);
3081 3082 3083
	}
out:
	spin_unlock(&cluster->lock);
3084
	spin_unlock(&ctl->tree_lock);
3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095

	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);
3096
	cluster->root = RB_ROOT;
3097
	cluster->max_size = 0;
3098
	cluster->fragmented = false;
3099 3100 3101 3102
	INIT_LIST_HEAD(&cluster->block_group_list);
	cluster->block_group = NULL;
}

3103 3104
static int do_trimming(struct btrfs_block_group_cache *block_group,
		       u64 *total_trimmed, u64 start, u64 bytes,
3105 3106
		       u64 reserved_start, u64 reserved_bytes,
		       struct btrfs_trim_range *trim_entry)
3107
{
3108
	struct btrfs_space_info *space_info = block_group->space_info;
3109
	struct btrfs_fs_info *fs_info = block_group->fs_info;
3110
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3111 3112 3113
	int ret;
	int update = 0;
	u64 trimmed = 0;
3114

3115 3116 3117 3118 3119 3120 3121 3122 3123 3124
	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);

3125 3126
	ret = btrfs_discard_extent(fs_info->extent_root,
				   start, bytes, &trimmed);
3127 3128 3129
	if (!ret)
		*total_trimmed += trimmed;

3130
	mutex_lock(&ctl->cache_writeout_mutex);
3131
	btrfs_add_free_space(block_group, reserved_start, reserved_bytes);
3132 3133
	list_del(&trim_entry->list);
	mutex_unlock(&ctl->cache_writeout_mutex);
3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158

	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;
3159 3160

	while (start < end) {
3161 3162 3163
		struct btrfs_trim_range trim_entry;

		mutex_lock(&ctl->cache_writeout_mutex);
3164
		spin_lock(&ctl->tree_lock);
3165

3166 3167
		if (ctl->free_space < minlen) {
			spin_unlock(&ctl->tree_lock);
3168
			mutex_unlock(&ctl->cache_writeout_mutex);
3169 3170 3171
			break;
		}

3172
		entry = tree_search_offset(ctl, start, 0, 1);
3173
		if (!entry) {
3174
			spin_unlock(&ctl->tree_lock);
3175
			mutex_unlock(&ctl->cache_writeout_mutex);
3176 3177 3178
			break;
		}

3179 3180 3181 3182
		/* skip bitmaps */
		while (entry->bitmap) {
			node = rb_next(&entry->offset_index);
			if (!node) {
3183
				spin_unlock(&ctl->tree_lock);
3184
				mutex_unlock(&ctl->cache_writeout_mutex);
3185
				goto out;
3186
			}
3187 3188
			entry = rb_entry(node, struct btrfs_free_space,
					 offset_index);
3189 3190
		}

3191 3192
		if (entry->offset >= end) {
			spin_unlock(&ctl->tree_lock);
3193
			mutex_unlock(&ctl->cache_writeout_mutex);
3194
			break;
3195 3196
		}

3197 3198 3199 3200 3201 3202
		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);
3203
			mutex_unlock(&ctl->cache_writeout_mutex);
3204
			goto next;
3205 3206
		}

3207 3208 3209
		unlink_free_space(ctl, entry);
		kmem_cache_free(btrfs_free_space_cachep, entry);

3210
		spin_unlock(&ctl->tree_lock);
3211 3212 3213 3214
		trim_entry.start = extent_start;
		trim_entry.bytes = extent_bytes;
		list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
		mutex_unlock(&ctl->cache_writeout_mutex);
3215

3216
		ret = do_trimming(block_group, total_trimmed, start, bytes,
3217
				  extent_start, extent_bytes, &trim_entry);
3218 3219 3220 3221
		if (ret)
			break;
next:
		start += bytes;
3222

3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245
		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;
3246
		struct btrfs_trim_range trim_entry;
3247

3248
		mutex_lock(&ctl->cache_writeout_mutex);
3249 3250 3251 3252
		spin_lock(&ctl->tree_lock);

		if (ctl->free_space < minlen) {
			spin_unlock(&ctl->tree_lock);
3253
			mutex_unlock(&ctl->cache_writeout_mutex);
3254 3255 3256 3257 3258 3259
			break;
		}

		entry = tree_search_offset(ctl, offset, 1, 0);
		if (!entry) {
			spin_unlock(&ctl->tree_lock);
3260
			mutex_unlock(&ctl->cache_writeout_mutex);
3261 3262 3263 3264 3265
			next_bitmap = true;
			goto next;
		}

		bytes = minlen;
3266
		ret2 = search_bitmap(ctl, entry, &start, &bytes, false);
3267 3268
		if (ret2 || start >= end) {
			spin_unlock(&ctl->tree_lock);
3269
			mutex_unlock(&ctl->cache_writeout_mutex);
3270 3271 3272 3273 3274 3275 3276
			next_bitmap = true;
			goto next;
		}

		bytes = min(bytes, end - start);
		if (bytes < minlen) {
			spin_unlock(&ctl->tree_lock);
3277
			mutex_unlock(&ctl->cache_writeout_mutex);
3278 3279 3280 3281 3282 3283 3284 3285
			goto next;
		}

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

		spin_unlock(&ctl->tree_lock);
3286 3287 3288 3289
		trim_entry.start = start;
		trim_entry.bytes = bytes;
		list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
		mutex_unlock(&ctl->cache_writeout_mutex);
3290 3291

		ret = do_trimming(block_group, total_trimmed, start, bytes,
3292
				  start, bytes, &trim_entry);
3293 3294 3295 3296 3297 3298 3299 3300 3301
		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;
3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313
		}

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

		cond_resched();
	}

	return ret;
}
3314

3315
void btrfs_get_block_group_trimming(struct btrfs_block_group_cache *cache)
3316
{
3317 3318
	atomic_inc(&cache->trimming);
}
3319

3320 3321 3322 3323 3324
void btrfs_put_block_group_trimming(struct btrfs_block_group_cache *block_group)
{
	struct extent_map_tree *em_tree;
	struct extent_map *em;
	bool cleanup;
3325

3326
	spin_lock(&block_group->lock);
3327 3328
	cleanup = (atomic_dec_and_test(&block_group->trimming) &&
		   block_group->removed);
3329 3330
	spin_unlock(&block_group->lock);

3331
	if (cleanup) {
3332
		lock_chunks(block_group->fs_info->chunk_root);
3333 3334 3335 3336 3337
		em_tree = &block_group->fs_info->mapping_tree.map_tree;
		write_lock(&em_tree->lock);
		em = lookup_extent_mapping(em_tree, block_group->key.objectid,
					   1);
		BUG_ON(!em); /* logic error, can't happen */
3338 3339 3340 3341
		/*
		 * remove_extent_mapping() will delete us from the pinned_chunks
		 * list, which is protected by the chunk mutex.
		 */
3342 3343 3344 3345 3346 3347 3348
		remove_extent_mapping(em_tree, em);
		write_unlock(&em_tree->lock);
		unlock_chunks(block_group->fs_info->chunk_root);

		/* once for us and once for the tree */
		free_extent_map(em);
		free_extent_map(em);
3349 3350 3351 3352 3353 3354

		/*
		 * We've left one free space entry and other tasks trimming
		 * this block group have left 1 entry each one. Free them.
		 */
		__btrfs_remove_free_space_cache(block_group->free_space_ctl);
3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366
	}
}

int btrfs_trim_block_group(struct btrfs_block_group_cache *block_group,
			   u64 *trimmed, u64 start, u64 end, u64 minlen)
{
	int ret;

	*trimmed = 0;

	spin_lock(&block_group->lock);
	if (block_group->removed) {
3367
		spin_unlock(&block_group->lock);
3368
		return 0;
3369
	}
3370 3371 3372 3373 3374 3375
	btrfs_get_block_group_trimming(block_group);
	spin_unlock(&block_group->lock);

	ret = trim_no_bitmap(block_group, trimmed, start, end, minlen);
	if (ret)
		goto out;
3376

3377 3378 3379
	ret = trim_bitmaps(block_group, trimmed, start, end, minlen);
out:
	btrfs_put_block_group_trimming(block_group);
3380 3381 3382
	return ret;
}

3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418
/*
 * 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;

3419
		ret = search_bitmap(ctl, entry, &offset, &count, true);
3420
		/* Logic error; Should be empty if it can't find anything */
3421
		ASSERT(!ret);
3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432

		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;
}
3433 3434 3435 3436 3437 3438

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

3439 3440 3441 3442
	spin_lock(&root->ino_cache_lock);
	if (root->ino_cache_inode)
		inode = igrab(root->ino_cache_inode);
	spin_unlock(&root->ino_cache_lock);
3443 3444 3445 3446 3447 3448 3449
	if (inode)
		return inode;

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

3450
	spin_lock(&root->ino_cache_lock);
3451
	if (!btrfs_fs_closing(root->fs_info))
3452 3453
		root->ino_cache_inode = igrab(inode);
	spin_unlock(&root->ino_cache_lock);
3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473

	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);

3474
	if (!btrfs_test_opt(root->fs_info, INODE_MAP_CACHE))
C
Chris Mason 已提交
3475 3476
		return 0;

3477 3478 3479 3480
	/*
	 * 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.
	 */
3481
	if (btrfs_fs_closing(fs_info))
3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497
		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)
3498 3499 3500
		btrfs_err(fs_info,
			"failed to load free ino cache for root %llu",
			root->root_key.objectid);
3501 3502 3503 3504 3505 3506 3507 3508 3509
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,
3510 3511
			      struct btrfs_path *path,
			      struct inode *inode)
3512 3513 3514
{
	struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
	int ret;
3515
	struct btrfs_io_ctl io_ctl;
3516
	bool release_metadata = true;
3517

3518
	if (!btrfs_test_opt(root->fs_info, INODE_MAP_CACHE))
C
Chris Mason 已提交
3519 3520
		return 0;

C
Chris Mason 已提交
3521
	memset(&io_ctl, 0, sizeof(io_ctl));
3522
	ret = __btrfs_write_out_cache(root, inode, ctl, NULL, &io_ctl,
C
Chris Mason 已提交
3523
				      trans, path, 0);
3524 3525 3526 3527 3528 3529 3530 3531
	if (!ret) {
		/*
		 * At this point writepages() didn't error out, so our metadata
		 * reservation is released when the writeback finishes, at
		 * inode.c:btrfs_finish_ordered_io(), regardless of it finishing
		 * with or without an error.
		 */
		release_metadata = false;
C
Chris Mason 已提交
3532
		ret = btrfs_wait_cache_io(root, trans, NULL, &io_ctl, path, 0);
3533
	}
C
Chris Mason 已提交
3534

3535
	if (ret) {
3536 3537
		if (release_metadata)
			btrfs_delalloc_release_metadata(inode, inode->i_size);
3538
#ifdef DEBUG
3539 3540 3541
		btrfs_err(root->fs_info,
			"failed to write free ino cache for root %llu",
			root->root_key.objectid);
3542 3543
#endif
	}
3544 3545 3546

	return ret;
}
3547 3548

#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
3549 3550 3551 3552 3553 3554 3555 3556
/*
 * Use this if you need to make a bitmap or extent entry specifically, it
 * doesn't do any of the merging that add_free_space does, this acts a lot like
 * how the free space cache loading stuff works, so you can get really weird
 * configurations.
 */
int test_add_free_space_entry(struct btrfs_block_group_cache *cache,
			      u64 offset, u64 bytes, bool bitmap)
3557
{
3558 3559 3560 3561 3562
	struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
	struct btrfs_free_space *info = NULL, *bitmap_info;
	void *map = NULL;
	u64 bytes_added;
	int ret;
3563

3564 3565 3566 3567 3568
again:
	if (!info) {
		info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
		if (!info)
			return -ENOMEM;
3569 3570
	}

3571 3572 3573 3574
	if (!bitmap) {
		spin_lock(&ctl->tree_lock);
		info->offset = offset;
		info->bytes = bytes;
3575
		info->max_extent_size = 0;
3576 3577 3578 3579 3580 3581 3582 3583
		ret = link_free_space(ctl, info);
		spin_unlock(&ctl->tree_lock);
		if (ret)
			kmem_cache_free(btrfs_free_space_cachep, info);
		return ret;
	}

	if (!map) {
3584
		map = kzalloc(PAGE_SIZE, GFP_NOFS);
3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598
		if (!map) {
			kmem_cache_free(btrfs_free_space_cachep, info);
			return -ENOMEM;
		}
	}

	spin_lock(&ctl->tree_lock);
	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
					 1, 0);
	if (!bitmap_info) {
		info->bitmap = map;
		map = NULL;
		add_new_bitmap(ctl, info, offset);
		bitmap_info = info;
3599
		info = NULL;
3600
	}
3601

3602
	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
3603

3604 3605 3606
	bytes -= bytes_added;
	offset += bytes_added;
	spin_unlock(&ctl->tree_lock);
3607

3608 3609
	if (bytes)
		goto again;
3610

3611 3612
	if (info)
		kmem_cache_free(btrfs_free_space_cachep, info);
3613 3614 3615
	if (map)
		kfree(map);
	return 0;
3616 3617 3618 3619 3620 3621 3622
}

/*
 * Checks to see if the given range is in the free space cache.  This is really
 * just used to check the absence of space, so if there is free space in the
 * range at all we will return 1.
 */
3623 3624
int test_check_exists(struct btrfs_block_group_cache *cache,
		      u64 offset, u64 bytes)
3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646
{
	struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
	struct btrfs_free_space *info;
	int ret = 0;

	spin_lock(&ctl->tree_lock);
	info = tree_search_offset(ctl, offset, 0, 0);
	if (!info) {
		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
					  1, 0);
		if (!info)
			goto out;
	}

have_info:
	if (info->bitmap) {
		u64 bit_off, bit_bytes;
		struct rb_node *n;
		struct btrfs_free_space *tmp;

		bit_off = offset;
		bit_bytes = ctl->unit;
3647
		ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false);
3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665
		if (!ret) {
			if (bit_off == offset) {
				ret = 1;
				goto out;
			} else if (bit_off > offset &&
				   offset + bytes > bit_off) {
				ret = 1;
				goto out;
			}
		}

		n = rb_prev(&info->offset_index);
		while (n) {
			tmp = rb_entry(n, struct btrfs_free_space,
				       offset_index);
			if (tmp->offset + tmp->bytes < offset)
				break;
			if (offset + bytes < tmp->offset) {
3666
				n = rb_prev(&tmp->offset_index);
3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679
				continue;
			}
			info = tmp;
			goto have_info;
		}

		n = rb_next(&info->offset_index);
		while (n) {
			tmp = rb_entry(n, struct btrfs_free_space,
				       offset_index);
			if (offset + bytes < tmp->offset)
				break;
			if (tmp->offset + tmp->bytes < offset) {
3680
				n = rb_next(&tmp->offset_index);
3681 3682 3683 3684 3685 3686
				continue;
			}
			info = tmp;
			goto have_info;
		}

3687
		ret = 0;
3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701
		goto out;
	}

	if (info->offset == offset) {
		ret = 1;
		goto out;
	}

	if (offset > info->offset && offset < info->offset + info->bytes)
		ret = 1;
out:
	spin_unlock(&ctl->tree_lock);
	return ret;
}
3702
#endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */