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
int btrfs_write_out_cache(struct btrfs_fs_info *fs_info,
1354 1355 1356 1357
			  struct btrfs_trans_handle *trans,
			  struct btrfs_block_group_cache *block_group,
			  struct btrfs_path *path)
{
1358
	struct btrfs_root *root = fs_info->tree_root;
1359 1360 1361 1362 1363 1364 1365
	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
	struct inode *inode;
	int ret = 0;

	spin_lock(&block_group->lock);
	if (block_group->disk_cache_state < BTRFS_DC_SETUP) {
		spin_unlock(&block_group->lock);
1366 1367
		return 0;
	}
1368 1369 1370 1371 1372 1373
	spin_unlock(&block_group->lock);

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

1374 1375
	ret = __btrfs_write_out_cache(root, inode, ctl, block_group,
				      &block_group->io_ctl, trans,
1376
				      path, block_group->key.objectid);
1377 1378
	if (ret) {
#ifdef DEBUG
1379 1380 1381
		btrfs_err(root->fs_info,
			"failed to write free space cache for block group %llu",
			block_group->key.objectid);
1382
#endif
1383 1384 1385 1386 1387 1388
		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);
1389 1390
	}

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

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

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

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

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

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

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

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

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

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

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

	return 0;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	return 0;
}

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

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

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

}

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

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

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

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

	return true;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	return ret;
}

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

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

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

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

2174 2175 2176
	return merged;
}

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

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

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

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

2314
	spin_lock(&ctl->tree_lock);
2315

2316
	if (try_merge_free_space(ctl, info, true))
2317 2318 2319 2320 2321 2322 2323
		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
	 */
2324
	ret = insert_into_bitmap(ctl, info);
2325 2326 2327 2328 2329 2330 2331
	if (ret < 0) {
		goto out;
	} else if (ret) {
		ret = 0;
		goto out;
	}
link:
2332 2333 2334 2335 2336 2337 2338 2339
	/*
	 * 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);

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

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

	return ret;
}

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

2362
	spin_lock(&ctl->tree_lock);
2363

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

J
Josef Bacik 已提交
2581 2582
}

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

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

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

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

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

2659 2660
	ctl = block_group->free_space_ctl;

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

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

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

	search_start = min_start;
	search_bytes = bytes;

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

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

	return ret;
}

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

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

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

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

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

2767 2768 2769
	if (!ret)
		return 0;

2770
	spin_lock(&ctl->tree_lock);
2771

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

2783
	spin_unlock(&ctl->tree_lock);
2784

2785 2786 2787
	return ret;
}

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

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

2810 2811 2812 2813 2814 2815 2816
	/*
	 * 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;
2817 2818
again:
	found_bits = 0;
2819
	for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {
2820 2821
		next_zero = find_next_zero_bit(entry->bitmap,
					       BITS_PER_BITMAP, i);
2822
		if (next_zero - i >= min_bits) {
2823
			found_bits = next_zero - i;
2824 2825
			if (found_bits > max_bits)
				max_bits = found_bits;
2826 2827
			break;
		}
2828 2829
		if (next_zero - i > max_bits)
			max_bits = next_zero - i;
2830 2831 2832
		i = next_zero;
	}

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

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

	total_found += found_bits;

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

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

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

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

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

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

	/*
	 * We don't want bitmaps, so just move along until we find a normal
	 * extent entry.
	 */
2892 2893
	while (entry->bitmap || entry->bytes < min_bytes) {
		if (entry->bitmap && list_empty(&entry->list))
2894
			list_add_tail(&entry->list, bitmaps);
2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905
		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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3209
		spin_unlock(&ctl->tree_lock);
3210 3211 3212 3213
		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);
3214

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

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

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

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

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

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

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

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

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

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

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

		cond_resched();
	}

	return ret;
}
3313

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

3319 3320 3321 3322 3323
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;
3324

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

3330
	if (cleanup) {
3331
		lock_chunks(block_group->fs_info->chunk_root);
3332 3333 3334 3335 3336
		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 */
3337 3338 3339 3340
		/*
		 * remove_extent_mapping() will delete us from the pinned_chunks
		 * list, which is protected by the chunk mutex.
		 */
3341 3342 3343 3344 3345 3346 3347
		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);
3348 3349 3350 3351 3352 3353

		/*
		 * 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);
3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365
	}
}

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) {
3366
		spin_unlock(&block_group->lock);
3367
		return 0;
3368
	}
3369 3370 3371 3372 3373 3374
	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;
3375

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

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

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

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

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

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

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

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

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

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

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

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

C
Chris Mason 已提交
3520
	memset(&io_ctl, 0, sizeof(io_ctl));
3521
	ret = __btrfs_write_out_cache(root, inode, ctl, NULL, &io_ctl,
C
Chris Mason 已提交
3522
				      trans, path, 0);
3523 3524 3525 3526 3527 3528 3529 3530
	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 已提交
3531
		ret = btrfs_wait_cache_io(root, trans, NULL, &io_ctl, path, 0);
3532
	}
C
Chris Mason 已提交
3533

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

	return ret;
}
3546 3547

#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
3548 3549 3550 3551 3552 3553 3554 3555
/*
 * 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)
3556
{
3557 3558 3559 3560 3561
	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;
3562

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

3570 3571 3572 3573
	if (!bitmap) {
		spin_lock(&ctl->tree_lock);
		info->offset = offset;
		info->bytes = bytes;
3574
		info->max_extent_size = 0;
3575 3576 3577 3578 3579 3580 3581 3582
		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) {
3583
		map = kzalloc(PAGE_SIZE, GFP_NOFS);
3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597
		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;
3598
		info = NULL;
3599
	}
3600

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

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

3607 3608
	if (bytes)
		goto again;
3609

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

/*
 * 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.
 */
3622 3623
int test_check_exists(struct btrfs_block_group_cache *cache,
		      u64 offset, u64 bytes)
3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645
{
	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;
3646
		ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false);
3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664
		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) {
3665
				n = rb_prev(&tmp->offset_index);
3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678
				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) {
3679
				n = rb_next(&tmp->offset_index);
3680 3681 3682 3683 3684 3685
				continue;
			}
			info = tmp;
			goto have_info;
		}

3686
		ret = 0;
3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700
		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;
}
3701
#endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */