// SPDX-License-Identifier: GPL-2.0

  /*
   * Copyright (C) 2008 Red Hat.  All rights reserved.

   */

  #include <linux/pagemap.h>

  #include <linux/sched.h>

  #include <linux/sched/signal.h>

  #include <linux/slab.h>

  #include <linux/math64.h>

  #include <linux/ratelimit.h>

  #include <linux/error-injection.h>

  #include <linux/sched/mm.h>

  #include "ctree.h"

  #include "free-space-cache.h"
  #include "transaction.h"

  #include "disk-io.h"

  #include "extent_io.h"

  #include "inode-map.h"

  #include "volumes.h"

  #include "space-info.h"

  #include "delalloc-space.h"

  #include "block-group.h"

  #include "discard.h"

  #define BITS_PER_BITMAP		(PAGE_SIZE * 8UL)

  #define MAX_CACHE_BYTES_PER_GIG	SZ_64K
  #define FORCE_EXTENT_THRESHOLD	SZ_1M

  struct btrfs_trim_range {
  	u64 start;
  	u64 bytes;
  	struct list_head list;
  };

  static int count_bitmap_extents(struct btrfs_free_space_ctl *ctl,
  				struct btrfs_free_space *bitmap_info);

  static int link_free_space(struct btrfs_free_space_ctl *ctl,

  			   struct btrfs_free_space *info);

  static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
  			      struct btrfs_free_space *info);

  static int btrfs_wait_cache_io_root(struct btrfs_root *root,
  			     struct btrfs_trans_handle *trans,
  			     struct btrfs_io_ctl *io_ctl,
  			     struct btrfs_path *path);

  static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
  					       struct btrfs_path *path,
  					       u64 offset)

  {

  	struct btrfs_fs_info *fs_info = root->fs_info;

  	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;

  	unsigned nofs_flag;

  	int ret;

  	key.objectid = BTRFS_FREE_SPACE_OBJECTID;

  	key.offset = offset;

  	key.type = 0;
  
  	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  	if (ret < 0)
  		return ERR_PTR(ret);
  	if (ret > 0) {

  		btrfs_release_path(path);

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

  	btrfs_release_path(path);

  	/*
  	 * We are often under a trans handle at this point, so we need to make
  	 * sure NOFS is set to keep us from deadlocking.
  	 */
  	nofs_flag = memalloc_nofs_save();

  	inode = btrfs_iget_path(fs_info->sb, location.objectid, root, path);

  	btrfs_release_path(path);

  	memalloc_nofs_restore(nofs_flag);

  	if (IS_ERR(inode))
  		return inode;

  	mapping_set_gfp_mask(inode->i_mapping,

  			mapping_gfp_constraint(inode->i_mapping,
  			~(__GFP_FS | __GFP_HIGHMEM)));

  	return inode;
  }

  struct inode *lookup_free_space_inode(struct btrfs_block_group *block_group,

  		struct btrfs_path *path)

  {

  	struct btrfs_fs_info *fs_info = block_group->fs_info;

  	struct inode *inode = NULL;

  	u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;

  
  	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(fs_info->tree_root, path,

  					  block_group->start);

  	if (IS_ERR(inode))
  		return inode;

  	spin_lock(&block_group->lock);

  	if (!((BTRFS_I(inode)->flags & flags) == flags)) {

  		btrfs_info(fs_info, "Old style space inode found, converting.");

  		BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM |
  			BTRFS_INODE_NODATACOW;

  		block_group->disk_cache_state = BTRFS_DC_CLEAR;
  	}

  	if (!block_group->iref) {

  		block_group->inode = igrab(inode);
  		block_group->iref = 1;
  	}
  	spin_unlock(&block_group->lock);
  
  	return inode;
  }

  static int __create_free_space_inode(struct btrfs_root *root,
  				     struct btrfs_trans_handle *trans,
  				     struct btrfs_path *path,
  				     u64 ino, u64 offset)

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

  	u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC;

  	int ret;

  	ret = btrfs_insert_empty_inode(trans, root, path, ino);

  	if (ret)
  		return ret;

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

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

  	memzero_extent_buffer(leaf, (unsigned long)inode_item,

  			     sizeof(*inode_item));
  	btrfs_set_inode_generation(leaf, inode_item, trans->transid);
  	btrfs_set_inode_size(leaf, inode_item, 0);
  	btrfs_set_inode_nbytes(leaf, inode_item, 0);
  	btrfs_set_inode_uid(leaf, inode_item, 0);
  	btrfs_set_inode_gid(leaf, inode_item, 0);
  	btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);

  	btrfs_set_inode_flags(leaf, inode_item, flags);

  	btrfs_set_inode_nlink(leaf, inode_item, 1);
  	btrfs_set_inode_transid(leaf, inode_item, trans->transid);

  	btrfs_set_inode_block_group(leaf, inode_item, offset);

  	btrfs_mark_buffer_dirty(leaf);

  	btrfs_release_path(path);

  
  	key.objectid = BTRFS_FREE_SPACE_OBJECTID;

  	key.offset = offset;

  	key.type = 0;

  	ret = btrfs_insert_empty_item(trans, root, path, &key,
  				      sizeof(struct btrfs_free_space_header));
  	if (ret < 0) {

  		btrfs_release_path(path);

  		return ret;
  	}

  	leaf = path->nodes[0];
  	header = btrfs_item_ptr(leaf, path->slots[0],
  				struct btrfs_free_space_header);

  	memzero_extent_buffer(leaf, (unsigned long)header, sizeof(*header));

  	btrfs_set_free_space_key(leaf, header, &disk_key);
  	btrfs_mark_buffer_dirty(leaf);

  	btrfs_release_path(path);

  
  	return 0;
  }

  int create_free_space_inode(struct btrfs_trans_handle *trans,

  			    struct btrfs_block_group *block_group,

  			    struct btrfs_path *path)
  {
  	int ret;
  	u64 ino;

  	ret = btrfs_find_free_objectid(trans->fs_info->tree_root, &ino);

  	if (ret < 0)
  		return ret;

  	return __create_free_space_inode(trans->fs_info->tree_root, trans, path,

  					 ino, block_group->start);

  }

  int btrfs_check_trunc_cache_free_space(struct btrfs_fs_info *fs_info,

  				       struct btrfs_block_rsv *rsv)

  {

  	u64 needed_bytes;

  	int ret;

  
  	/* 1 for slack space, 1 for updating the inode */

  	needed_bytes = btrfs_calc_insert_metadata_size(fs_info, 1) +
  		btrfs_calc_metadata_size(fs_info, 1);

  	spin_lock(&rsv->lock);
  	if (rsv->reserved < needed_bytes)
  		ret = -ENOSPC;
  	else
  		ret = 0;
  	spin_unlock(&rsv->lock);

  	return ret;

  }

  int btrfs_truncate_free_space_cache(struct btrfs_trans_handle *trans,

  				    struct btrfs_block_group *block_group,

  				    struct inode *inode)
  {

  	struct btrfs_root *root = BTRFS_I(inode)->root;

  	int ret = 0;

  	bool locked = false;

  	if (block_group) {

  		struct btrfs_path *path = btrfs_alloc_path();
  
  		if (!path) {
  			ret = -ENOMEM;
  			goto fail;
  		}

  		locked = true;

  		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(trans, block_group, path);

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

  	}

  	btrfs_i_size_write(BTRFS_I(inode), 0);

  	truncate_pagecache(inode, 0);

  
  	/*

  	 * We skip the throttling logic for free space cache inodes, so we don't
  	 * need to check for -EAGAIN.

  	 */
  	ret = btrfs_truncate_inode_items(trans, root, inode,
  					 0, BTRFS_EXTENT_DATA_KEY);

  	if (ret)
  		goto fail;

  	ret = btrfs_update_inode(trans, root, inode);

  fail:

  	if (locked)
  		mutex_unlock(&trans->transaction->cache_write_mutex);

  	if (ret)

  		btrfs_abort_transaction(trans, ret);

  	return ret;

  }

  static void readahead_cache(struct inode *inode)

  {
  	struct file_ra_state *ra;
  	unsigned long last_index;
  
  	ra = kzalloc(sizeof(*ra), GFP_NOFS);
  	if (!ra)

  		return;

  
  	file_ra_state_init(ra, inode->i_mapping);

  	last_index = (i_size_read(inode) - 1) >> PAGE_SHIFT;

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

  }

  static int io_ctl_init(struct btrfs_io_ctl *io_ctl, struct inode *inode,

  		       int write)

  {

  	int num_pages;
  	int check_crcs = 0;

  	num_pages = DIV_ROUND_UP(i_size_read(inode), PAGE_SIZE);

  	if (btrfs_ino(BTRFS_I(inode)) != BTRFS_FREE_INO_OBJECTID)

  		check_crcs = 1;

  	/* Make sure we can fit our crcs and generation into the first page */

  	if (write && check_crcs &&

  	    (num_pages * sizeof(u32) + sizeof(u64)) > PAGE_SIZE)

  		return -ENOSPC;

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

  	io_ctl->pages = kcalloc(num_pages, sizeof(struct page *), GFP_NOFS);

  	if (!io_ctl->pages)
  		return -ENOMEM;

  
  	io_ctl->num_pages = num_pages;

  	io_ctl->fs_info = btrfs_sb(inode->i_sb);

  	io_ctl->check_crcs = check_crcs;

  	io_ctl->inode = inode;

  	return 0;
  }

  ALLOW_ERROR_INJECTION(io_ctl_init, ERRNO);

  static void io_ctl_free(struct btrfs_io_ctl *io_ctl)

  {
  	kfree(io_ctl->pages);

  	io_ctl->pages = NULL;

  }

  static void io_ctl_unmap_page(struct btrfs_io_ctl *io_ctl)

  {
  	if (io_ctl->cur) {

  		io_ctl->cur = NULL;
  		io_ctl->orig = NULL;
  	}
  }

  static void io_ctl_map_page(struct btrfs_io_ctl *io_ctl, int clear)

  {

  	ASSERT(io_ctl->index < io_ctl->num_pages);

  	io_ctl->page = io_ctl->pages[io_ctl->index++];

  	io_ctl->cur = page_address(io_ctl->page);

  	io_ctl->orig = io_ctl->cur;

  	io_ctl->size = PAGE_SIZE;

  	if (clear)

  		clear_page(io_ctl->cur);

  }

  static void io_ctl_drop_pages(struct btrfs_io_ctl *io_ctl)

  {
  	int i;
  
  	io_ctl_unmap_page(io_ctl);
  
  	for (i = 0; i < io_ctl->num_pages; i++) {

  		if (io_ctl->pages[i]) {
  			ClearPageChecked(io_ctl->pages[i]);
  			unlock_page(io_ctl->pages[i]);

  			put_page(io_ctl->pages[i]);

  		}

  	}
  }

  static int io_ctl_prepare_pages(struct btrfs_io_ctl *io_ctl, bool uptodate)

  {
  	struct page *page;

  	struct inode *inode = io_ctl->inode;

  	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 (page->mapping != inode->i_mapping) {
  				btrfs_err(BTRFS_I(inode)->root->fs_info,
  					  "free space cache page truncated");
  				io_ctl_drop_pages(io_ctl);
  				return -EIO;
  			}

  			if (!PageUptodate(page)) {

  				btrfs_err(BTRFS_I(inode)->root->fs_info,
  					   "error reading free space cache");

  				io_ctl_drop_pages(io_ctl);
  				return -EIO;
  			}
  		}
  	}

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

  	return 0;
  }

  static void io_ctl_set_generation(struct btrfs_io_ctl *io_ctl, u64 generation)

  {

  	io_ctl_map_page(io_ctl, 1);
  
  	/*

  	 * Skip the csum areas.  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;
  	}

  	put_unaligned_le64(generation, io_ctl->cur);

  	io_ctl->cur += sizeof(u64);

  }

  static int io_ctl_check_generation(struct btrfs_io_ctl *io_ctl, u64 generation)

  {

  	u64 cache_gen;

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

  	cache_gen = get_unaligned_le64(io_ctl->cur);
  	if (cache_gen != generation) {

  		btrfs_err_rl(io_ctl->fs_info,

  			"space cache generation (%llu) does not match inode (%llu)",

  				cache_gen, generation);

  		io_ctl_unmap_page(io_ctl);
  		return -EIO;
  	}
  	io_ctl->cur += sizeof(u64);

  	return 0;
  }

  static void io_ctl_set_crc(struct btrfs_io_ctl *io_ctl, int index)

  {
  	u32 *tmp;
  	u32 crc = ~(u32)0;
  	unsigned offset = 0;
  
  	if (!io_ctl->check_crcs) {
  		io_ctl_unmap_page(io_ctl);
  		return;
  	}
  
  	if (index == 0)

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

  	crc = btrfs_crc32c(crc, io_ctl->orig + offset, PAGE_SIZE - offset);
  	btrfs_crc32c_final(crc, (u8 *)&crc);

  	io_ctl_unmap_page(io_ctl);

  	tmp = page_address(io_ctl->pages[0]);

  	tmp += index;
  	*tmp = crc;

  }

  static int io_ctl_check_crc(struct btrfs_io_ctl *io_ctl, int index)

  {
  	u32 *tmp, val;
  	u32 crc = ~(u32)0;
  	unsigned offset = 0;
  
  	if (!io_ctl->check_crcs) {
  		io_ctl_map_page(io_ctl, 0);
  		return 0;
  	}
  
  	if (index == 0)
  		offset = sizeof(u32) * io_ctl->num_pages;

  	tmp = page_address(io_ctl->pages[0]);

  	tmp += index;
  	val = *tmp;

  
  	io_ctl_map_page(io_ctl, 0);

  	crc = btrfs_crc32c(crc, io_ctl->orig + offset, PAGE_SIZE - offset);
  	btrfs_crc32c_final(crc, (u8 *)&crc);

  	if (val != crc) {

  		btrfs_err_rl(io_ctl->fs_info,

  			"csum mismatch on free space cache");

  		io_ctl_unmap_page(io_ctl);
  		return -EIO;
  	}

  	return 0;
  }

  static int io_ctl_add_entry(struct btrfs_io_ctl *io_ctl, u64 offset, u64 bytes,

  			    void *bitmap)
  {
  	struct btrfs_free_space_entry *entry;
  
  	if (!io_ctl->cur)
  		return -ENOSPC;
  
  	entry = io_ctl->cur;

  	put_unaligned_le64(offset, &entry->offset);
  	put_unaligned_le64(bytes, &entry->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;

  	io_ctl_set_crc(io_ctl, io_ctl->index - 1);

  
  	/* No more pages to map */
  	if (io_ctl->index >= io_ctl->num_pages)
  		return 0;
  
  	/* map the next page */
  	io_ctl_map_page(io_ctl, 1);
  	return 0;
  }

  static int io_ctl_add_bitmap(struct btrfs_io_ctl *io_ctl, void *bitmap)

  {
  	if (!io_ctl->cur)
  		return -ENOSPC;
  
  	/*
  	 * If we aren't at the start of the current page, unmap this one and
  	 * map the next one if there is any left.
  	 */
  	if (io_ctl->cur != io_ctl->orig) {

  		io_ctl_set_crc(io_ctl, io_ctl->index - 1);

  		if (io_ctl->index >= io_ctl->num_pages)
  			return -ENOSPC;
  		io_ctl_map_page(io_ctl, 0);
  	}

  	copy_page(io_ctl->cur, bitmap);

  	io_ctl_set_crc(io_ctl, io_ctl->index - 1);

  	if (io_ctl->index < io_ctl->num_pages)
  		io_ctl_map_page(io_ctl, 0);
  	return 0;
  }

  static void io_ctl_zero_remaining_pages(struct btrfs_io_ctl *io_ctl)

  {

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

  
  	while (io_ctl->index < io_ctl->num_pages) {
  		io_ctl_map_page(io_ctl, 1);

  		io_ctl_set_crc(io_ctl, io_ctl->index - 1);

  	}
  }

  static int io_ctl_read_entry(struct btrfs_io_ctl *io_ctl,

  			    struct btrfs_free_space *entry, u8 *type)

  {
  	struct btrfs_free_space_entry *e;

  	int ret;
  
  	if (!io_ctl->cur) {
  		ret = io_ctl_check_crc(io_ctl, io_ctl->index);
  		if (ret)
  			return ret;
  	}

  
  	e = io_ctl->cur;

  	entry->offset = get_unaligned_le64(&e->offset);
  	entry->bytes = get_unaligned_le64(&e->bytes);

  	*type = e->type;

  	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;

  
  	io_ctl_unmap_page(io_ctl);

  	return 0;

  }

  static int io_ctl_read_bitmap(struct btrfs_io_ctl *io_ctl,

  			      struct btrfs_free_space *entry)

  {

  	int ret;

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

  	copy_page(entry->bitmap, io_ctl->cur);

  	io_ctl_unmap_page(io_ctl);

  
  	return 0;

  }

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

  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)

  {

  	struct btrfs_fs_info *fs_info = root->fs_info;

  	struct btrfs_free_space_header *header;
  	struct extent_buffer *leaf;

  	struct btrfs_io_ctl io_ctl;

  	struct btrfs_key key;

  	struct btrfs_free_space *e, *n;

  	LIST_HEAD(bitmaps);

  	u64 num_entries;
  	u64 num_bitmaps;
  	u64 generation;

  	u8 type;

  	int ret = 0;

  	/* Nothing in the space cache, goodbye */

  	if (!i_size_read(inode))

  		return 0;

  
  	key.objectid = BTRFS_FREE_SPACE_OBJECTID;

  	key.offset = offset;

  	key.type = 0;
  
  	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);

  	if (ret < 0)

  		return 0;

  	else if (ret > 0) {

  		btrfs_release_path(path);

  		return 0;

  	}

  	ret = -1;

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

  	btrfs_release_path(path);

  	if (!BTRFS_I(inode)->generation) {

  		btrfs_info(fs_info,

  			   "the free space cache file (%llu) is invalid, skip it",

  			   offset);
  		return 0;
  	}

  	if (BTRFS_I(inode)->generation != generation) {

  		btrfs_err(fs_info,
  			  "free space inode generation (%llu) did not match free space cache generation (%llu)",
  			  BTRFS_I(inode)->generation, generation);

  		return 0;

  	}
  
  	if (!num_entries)

  		return 0;

  	ret = io_ctl_init(&io_ctl, inode, 0);

  	if (ret)
  		return ret;

  	readahead_cache(inode);

  	ret = io_ctl_prepare_pages(&io_ctl, true);

  	if (ret)
  		goto out;

  	ret = io_ctl_check_crc(&io_ctl, 0);
  	if (ret)
  		goto free_cache;

  	ret = io_ctl_check_generation(&io_ctl, generation);
  	if (ret)
  		goto free_cache;

  	while (num_entries) {
  		e = kmem_cache_zalloc(btrfs_free_space_cachep,
  				      GFP_NOFS);
  		if (!e)

  			goto free_cache;

  		ret = io_ctl_read_entry(&io_ctl, e, &type);
  		if (ret) {
  			kmem_cache_free(btrfs_free_space_cachep, e);
  			goto free_cache;
  		}

  		/*
  		 * Sync discard ensures that the free space cache is always
  		 * trimmed.  So when reading this in, the state should reflect

  		 * that.  We also do this for async as a stop gap for lack of
  		 * persistence.

  		 */

  		if (btrfs_test_opt(fs_info, DISCARD_SYNC) ||
  		    btrfs_test_opt(fs_info, DISCARD_ASYNC))

  			e->trim_state = BTRFS_TRIM_STATE_TRIMMED;

  		if (!e->bytes) {
  			kmem_cache_free(btrfs_free_space_cachep, e);
  			goto free_cache;

  		}

  
  		if (type == BTRFS_FREE_SPACE_EXTENT) {
  			spin_lock(&ctl->tree_lock);
  			ret = link_free_space(ctl, e);
  			spin_unlock(&ctl->tree_lock);
  			if (ret) {

  				btrfs_err(fs_info,

  					"Duplicate entries in free space cache, dumping");

  				kmem_cache_free(btrfs_free_space_cachep, e);

  				goto free_cache;
  			}

  		} else {

  			ASSERT(num_bitmaps);

  			num_bitmaps--;

  			e->bitmap = kmem_cache_zalloc(
  					btrfs_free_space_bitmap_cachep, GFP_NOFS);

  			if (!e->bitmap) {
  				kmem_cache_free(
  					btrfs_free_space_cachep, e);

  				goto free_cache;
  			}

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

  				btrfs_err(fs_info,

  					"Duplicate entries in free space cache, dumping");

  				kmem_cache_free(btrfs_free_space_cachep, e);

  				goto free_cache;
  			}

  			list_add_tail(&e->list, &bitmaps);

  		}

  		num_entries--;
  	}

  	io_ctl_unmap_page(&io_ctl);

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

  		list_del_init(&e->list);

  		ret = io_ctl_read_bitmap(&io_ctl, e);
  		if (ret)
  			goto free_cache;

  		e->bitmap_extents = count_bitmap_extents(ctl, e);

  		if (!btrfs_free_space_trimmed(e)) {

  			ctl->discardable_extents[BTRFS_STAT_CURR] +=
  				e->bitmap_extents;

  			ctl->discardable_bytes[BTRFS_STAT_CURR] += e->bytes;
  		}

  	}

  	io_ctl_drop_pages(&io_ctl);

  	merge_space_tree(ctl);

  	ret = 1;
  out:

  	btrfs_discard_update_discardable(ctl->private, ctl);

  	io_ctl_free(&io_ctl);

  	return ret;

  free_cache:

  	io_ctl_drop_pages(&io_ctl);

  	__btrfs_remove_free_space_cache(ctl);

  	goto out;
  }

  int load_free_space_cache(struct btrfs_block_group *block_group)

  {

  	struct btrfs_fs_info *fs_info = block_group->fs_info;

  	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;

  	struct inode *inode;
  	struct btrfs_path *path;

  	int ret = 0;

  	bool matched;

  	u64 used = block_group->used;

  
  	/*

  	 * 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.
  	 */

  	spin_lock(&block_group->lock);

  	if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
  		spin_unlock(&block_group->lock);
  		return 0;
  	}

  	spin_unlock(&block_group->lock);

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

  	path->search_commit_root = 1;
  	path->skip_locking = 1;

  	/*
  	 * We must pass a path with search_commit_root set to btrfs_iget in
  	 * order to avoid a deadlock when allocating extents for the tree root.
  	 *
  	 * When we are COWing an extent buffer from the tree root, when looking
  	 * for a free extent, at extent-tree.c:find_free_extent(), we can find
  	 * block group without its free space cache loaded. When we find one
  	 * we must load its space cache which requires reading its free space
  	 * cache's inode item from the root tree. If this inode item is located
  	 * in the same leaf that we started COWing before, then we end up in
  	 * deadlock on the extent buffer (trying to read lock it when we
  	 * previously write locked it).
  	 *
  	 * It's safe to read the inode item using the commit root because
  	 * block groups, once loaded, stay in memory forever (until they are
  	 * removed) as well as their space caches once loaded. New block groups
  	 * once created get their ->cached field set to BTRFS_CACHE_FINISHED so
  	 * we will never try to read their inode item while the fs is mounted.
  	 */

  	inode = lookup_free_space_inode(block_group, path);

  	if (IS_ERR(inode)) {
  		btrfs_free_path(path);
  		return 0;
  	}

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

  		btrfs_free_path(path);

  		goto out;
  	}
  	spin_unlock(&block_group->lock);

  	ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,

  				      path, block_group->start);

  	btrfs_free_path(path);
  	if (ret <= 0)
  		goto out;
  
  	spin_lock(&ctl->tree_lock);

  	matched = (ctl->free_space == (block_group->length - used -

  				       block_group->bytes_super));
  	spin_unlock(&ctl->tree_lock);
  
  	if (!matched) {
  		__btrfs_remove_free_space_cache(ctl);

  		btrfs_warn(fs_info,
  			   "block group %llu has wrong amount of free space",

  			   block_group->start);

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

  		ret = 0;

  		btrfs_warn(fs_info,
  			   "failed to load free space cache for block group %llu, rebuilding it now",

  			   block_group->start);

  	}
  
  	iput(inode);
  	return ret;

  }

  static noinline_for_stack

  int write_cache_extent_entries(struct btrfs_io_ctl *io_ctl,

  			      struct btrfs_free_space_ctl *ctl,

  			      struct btrfs_block_group *block_group,

  			      int *entries, int *bitmaps,
  			      struct list_head *bitmap_list)

  {

  	int ret;

  	struct btrfs_free_cluster *cluster = NULL;

  	struct btrfs_free_cluster *cluster_locked = NULL;

  	struct rb_node *node = rb_first(&ctl->free_space_offset);

  	struct btrfs_trim_range *trim_entry;

  	/* Get the cluster for this block_group if it exists */

  	if (block_group && !list_empty(&block_group->cluster_list)) {

  		cluster = list_entry(block_group->cluster_list.next,
  				     struct btrfs_free_cluster,
  				     block_group_list);

  	}

  	if (!node && cluster) {

  		cluster_locked = cluster;
  		spin_lock(&cluster_locked->lock);

  		node = rb_first(&cluster->root);
  		cluster = NULL;
  	}

  	/* Write out the extent entries */
  	while (node) {
  		struct btrfs_free_space *e;

  		e = rb_entry(node, struct btrfs_free_space, offset_index);

  		*entries += 1;

  		ret = io_ctl_add_entry(io_ctl, e->offset, e->bytes,

  				       e->bitmap);
  		if (ret)

  			goto fail;

  		if (e->bitmap) {

  			list_add_tail(&e->list, bitmap_list);
  			*bitmaps += 1;

  		}

  		node = rb_next(node);
  		if (!node && cluster) {
  			node = rb_first(&cluster->root);

  			cluster_locked = cluster;
  			spin_lock(&cluster_locked->lock);

  			cluster = NULL;

  		}

  	}

  	if (cluster_locked) {
  		spin_unlock(&cluster_locked->lock);
  		cluster_locked = NULL;
  	}

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

  	return 0;
  fail:

  	if (cluster_locked)
  		spin_unlock(&cluster_locked->lock);

  	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_DELALLOC, 0, 0, NULL);

  		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_DELALLOC, 0,
  					 0, NULL);

  			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 write_pinned_extent_entries(

  			    struct btrfs_trans_handle *trans,

  			    struct btrfs_block_group *block_group,

  			    struct btrfs_io_ctl *io_ctl,

  			    int *entries)

  {
  	u64 start, extent_start, extent_end, len;

  	struct extent_io_tree *unpin = NULL;
  	int ret;

  	if (!block_group)
  		return 0;

  	/*
  	 * We want to add any pinned extents to our free space cache
  	 * so we don't leak the space

  	 *

  	 * We shouldn't have switched the pinned extents yet so this is the
  	 * right one
  	 */

  	unpin = &trans->transaction->pinned_extents;

  	start = block_group->start;

  	while (start < block_group->start + block_group->length) {

  		ret = find_first_extent_bit(unpin, start,
  					    &extent_start, &extent_end,

  					    EXTENT_DIRTY, NULL);

  		if (ret)
  			return 0;

  		/* This pinned extent is out of our range */

  		if (extent_start >= block_group->start + block_group->length)

  			return 0;

  		extent_start = max(extent_start, start);

  		extent_end = min(block_group->start + block_group->length,
  				 extent_end + 1);

  		len = extent_end - extent_start;

  		*entries += 1;
  		ret = io_ctl_add_entry(io_ctl, extent_start, len, NULL);

  		if (ret)

  			return -ENOSPC;

  		start = extent_end;

  	}

  	return 0;
  }
  
  static noinline_for_stack int

  write_bitmap_entries(struct btrfs_io_ctl *io_ctl, struct list_head *bitmap_list)

  {

  	struct btrfs_free_space *entry, *next;

  	int ret;

  	/* Write out the bitmaps */

  	list_for_each_entry_safe(entry, next, bitmap_list, list) {

  		ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);

  		if (ret)

  			return -ENOSPC;

  		list_del_init(&entry->list);

  	}

  	return 0;
  }

  static int flush_dirty_cache(struct inode *inode)
  {
  	int ret;

  	ret = btrfs_wait_ordered_range(inode, 0, (u64)-1);

  	if (ret)

  		clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,

  				 EXTENT_DELALLOC, 0, 0, NULL);

  	return ret;

  }
  
  static void noinline_for_stack

  cleanup_bitmap_list(struct list_head *bitmap_list)

  {

  	struct btrfs_free_space *entry, *next;

  	list_for_each_entry_safe(entry, next, bitmap_list, list)

  		list_del_init(&entry->list);

  }
  
  static void noinline_for_stack
  cleanup_write_cache_enospc(struct inode *inode,
  			   struct btrfs_io_ctl *io_ctl,

  			   struct extent_state **cached_state)

  {

  	io_ctl_drop_pages(io_ctl);
  	unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,

  			     i_size_read(inode) - 1, cached_state);

  }

  static int __btrfs_wait_cache_io(struct btrfs_root *root,
  				 struct btrfs_trans_handle *trans,

  				 struct btrfs_block_group *block_group,

  				 struct btrfs_io_ctl *io_ctl,
  				 struct btrfs_path *path, u64 offset)

  {
  	int ret;
  	struct inode *inode = io_ctl->inode;

  	if (!inode)
  		return 0;

  	/* 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:

  	if (ret) {
  		invalidate_inode_pages2(inode->i_mapping);
  		BTRFS_I(inode)->generation = 0;

  		if (block_group)
  			btrfs_debug(root->fs_info,

  	  "failed to write free space cache for block group %llu error %d",
  				  block_group->start, ret);

  	}
  	btrfs_update_inode(trans, root, inode);
  
  	if (block_group) {

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

  		spin_lock(&block_group->lock);
  
  		/*
  		 * only mark this as written if we didn't get put back on

  		 * the dirty list while waiting for IO.   Otherwise our
  		 * cache state won't be right, and we won't get written again

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

  		spin_unlock(&trans->transaction->dirty_bgs_lock);

  		io_ctl->inode = NULL;
  		iput(inode);
  	}
  
  	return ret;
  
  }

  static int btrfs_wait_cache_io_root(struct btrfs_root *root,
  				    struct btrfs_trans_handle *trans,
  				    struct btrfs_io_ctl *io_ctl,
  				    struct btrfs_path *path)
  {
  	return __btrfs_wait_cache_io(root, trans, NULL, io_ctl, path, 0);
  }
  
  int btrfs_wait_cache_io(struct btrfs_trans_handle *trans,

  			struct btrfs_block_group *block_group,

  			struct btrfs_path *path)
  {
  	return __btrfs_wait_cache_io(block_group->fs_info->tree_root, trans,
  				     block_group, &block_group->io_ctl,

  				     path, block_group->start);

  }

  /**
   * __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

   *
   * This function writes out a free space cache struct to disk for quick recovery

   * on mount.  This will return 0 if it was successful in writing the cache out,

   * or an errno if it was not.

   */
  static int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
  				   struct btrfs_free_space_ctl *ctl,

  				   struct btrfs_block_group *block_group,

  				   struct btrfs_io_ctl *io_ctl,

  				   struct btrfs_trans_handle *trans)

  {
  	struct extent_state *cached_state = NULL;

  	LIST_HEAD(bitmap_list);

  	int entries = 0;
  	int bitmaps = 0;
  	int ret;

  	int must_iput = 0;

  
  	if (!i_size_read(inode))

  		return -EIO;

  	WARN_ON(io_ctl->pages);

  	ret = io_ctl_init(io_ctl, inode, 1);

  	if (ret)

  		return ret;

  	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;

  			must_iput = 1;

  			goto out;
  		}
  		spin_unlock(&block_group->lock);
  	}

  	/* Lock all pages first so we can lock the extent safely. */

  	ret = io_ctl_prepare_pages(io_ctl, false);

  	if (ret)

  		goto out_unlock;

  
  	lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,

  			 &cached_state);

  	io_ctl_set_generation(io_ctl, trans->transid);

  	mutex_lock(&ctl->cache_writeout_mutex);

  	/* Write out the extent entries in the free space cache */

  	spin_lock(&ctl->tree_lock);

  	ret = write_cache_extent_entries(io_ctl, ctl,

  					 block_group, &entries, &bitmaps,
  					 &bitmap_list);

  	if (ret)
  		goto out_nospc_locked;

  	/*
  	 * 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.

  	 *
  	 * If this changes while we are working we'll get added back to
  	 * the dirty list and redo it.  No locking needed

  	 */

  	ret = write_pinned_extent_entries(trans, block_group, io_ctl, &entries);

  	if (ret)
  		goto out_nospc_locked;

  	/*
  	 * 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.
  	 */

  	ret = write_bitmap_entries(io_ctl, &bitmap_list);

  	spin_unlock(&ctl->tree_lock);

  	mutex_unlock(&ctl->cache_writeout_mutex);

  	if (ret)
  		goto out_nospc;
  
  	/* Zero out the rest of the pages just to make sure */

  	io_ctl_zero_remaining_pages(io_ctl);

  	/* Everything is written out, now we dirty the pages in the file. */

  	ret = btrfs_dirty_pages(BTRFS_I(inode), io_ctl->pages,
  				io_ctl->num_pages, 0, i_size_read(inode),
  				&cached_state);

  	if (ret)

  		goto out_nospc;

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

  	/*
  	 * Release the pages and unlock the extent, we will flush
  	 * them out later
  	 */

  	io_ctl_drop_pages(io_ctl);

  	io_ctl_free(io_ctl);

  
  	unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,

  			     i_size_read(inode) - 1, &cached_state);

  	/*
  	 * at this point the pages are under IO and we're happy,

  	 * The caller is responsible for waiting on them and updating

  	 * the cache and the inode
  	 */
  	io_ctl->entries = entries;
  	io_ctl->bitmaps = bitmaps;
  
  	ret = btrfs_fdatawrite_range(inode, 0, (u64)-1);

  	if (ret)

  		goto out;

  	return 0;

  out_nospc_locked:
  	cleanup_bitmap_list(&bitmap_list);
  	spin_unlock(&ctl->tree_lock);
  	mutex_unlock(&ctl->cache_writeout_mutex);

  out_nospc:

  	cleanup_write_cache_enospc(inode, io_ctl, &cached_state);

  out_unlock:

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

  out:
  	io_ctl->inode = NULL;
  	io_ctl_free(io_ctl);
  	if (ret) {
  		invalidate_inode_pages2(inode->i_mapping);
  		BTRFS_I(inode)->generation = 0;
  	}
  	btrfs_update_inode(trans, root, inode);
  	if (must_iput)
  		iput(inode);
  	return ret;

  }

  int btrfs_write_out_cache(struct btrfs_trans_handle *trans,

  			  struct btrfs_block_group *block_group,

  			  struct btrfs_path *path)
  {

  	struct btrfs_fs_info *fs_info = trans->fs_info;

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

  		return 0;
  	}

  	spin_unlock(&block_group->lock);

  	inode = lookup_free_space_inode(block_group, path);

  	if (IS_ERR(inode))
  		return 0;

  	ret = __btrfs_write_out_cache(fs_info->tree_root, inode, ctl,
  				block_group, &block_group->io_ctl, trans);

  	if (ret) {

  		btrfs_debug(fs_info,

  	  "failed to write free space cache for block group %llu error %d",
  			  block_group->start, ret);

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