// 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 "fs.h" #include "messages.h" #include "misc.h" #include "free-space-cache.h" #include "transaction.h" #include "disk-io.h" #include "extent_io.h" #include "space-info.h" #include "block-group.h" #include "discard.h" #include "subpage.h" #include "inode-item.h" #include "accessors.h" #include "file-item.h" #include "file.h" #include "super.h" #define BITS_PER_BITMAP … #define MAX_CACHE_BYTES_PER_GIG … #define FORCE_EXTENT_THRESHOLD … static struct kmem_cache *btrfs_free_space_cachep; static struct kmem_cache *btrfs_free_space_bitmap_cachep; struct btrfs_trim_range { … }; 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, bool update_stat); static int search_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *bitmap_info, u64 *offset, u64 *bytes, bool for_alloc); static void free_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *bitmap_info); static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, u64 offset, u64 bytes, bool update_stats); static void btrfs_crc32c_final(u32 crc, u8 *result) { … } static void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl) { … } static struct inode *__lookup_free_space_inode(struct btrfs_root *root, struct btrfs_path *path, u64 offset) { … } struct inode *lookup_free_space_inode(struct btrfs_block_group *block_group, struct btrfs_path *path) { … } static int __create_free_space_inode(struct btrfs_root *root, struct btrfs_trans_handle *trans, struct btrfs_path *path, u64 ino, u64 offset) { … } int create_free_space_inode(struct btrfs_trans_handle *trans, struct btrfs_block_group *block_group, struct btrfs_path *path) { … } /* * inode is an optional sink: if it is NULL, btrfs_remove_free_space_inode * handles lookup, otherwise it takes ownership and iputs the inode. * Don't reuse an inode pointer after passing it into this function. */ int btrfs_remove_free_space_inode(struct btrfs_trans_handle *trans, struct inode *inode, struct btrfs_block_group *block_group) { … } int btrfs_truncate_free_space_cache(struct btrfs_trans_handle *trans, struct btrfs_block_group *block_group, struct inode *vfs_inode) { … } static void readahead_cache(struct inode *inode) { … } static int io_ctl_init(struct btrfs_io_ctl *io_ctl, struct inode *inode, int write) { … } ALLOW_ERROR_INJECTION(…); static void io_ctl_free(struct btrfs_io_ctl *io_ctl) { … } static void io_ctl_unmap_page(struct btrfs_io_ctl *io_ctl) { … } static void io_ctl_map_page(struct btrfs_io_ctl *io_ctl, int clear) { … } static void io_ctl_drop_pages(struct btrfs_io_ctl *io_ctl) { … } static int io_ctl_prepare_pages(struct btrfs_io_ctl *io_ctl, bool uptodate) { … } static void io_ctl_set_generation(struct btrfs_io_ctl *io_ctl, u64 generation) { … } static int io_ctl_check_generation(struct btrfs_io_ctl *io_ctl, u64 generation) { … } static void io_ctl_set_crc(struct btrfs_io_ctl *io_ctl, int index) { … } static int io_ctl_check_crc(struct btrfs_io_ctl *io_ctl, int index) { … } static int io_ctl_add_entry(struct btrfs_io_ctl *io_ctl, u64 offset, u64 bytes, void *bitmap) { … } static int io_ctl_add_bitmap(struct btrfs_io_ctl *io_ctl, void *bitmap) { … } static void io_ctl_zero_remaining_pages(struct btrfs_io_ctl *io_ctl) { … } static int io_ctl_read_entry(struct btrfs_io_ctl *io_ctl, struct btrfs_free_space *entry, u8 *type) { … } static int io_ctl_read_bitmap(struct btrfs_io_ctl *io_ctl, struct btrfs_free_space *entry) { … } static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl) { … } 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) { … } static int copy_free_space_cache(struct btrfs_block_group *block_group, struct btrfs_free_space_ctl *ctl) { … } static struct lock_class_key btrfs_free_space_inode_key; int load_free_space_cache(struct btrfs_block_group *block_group) { … } 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) { … } 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) { … } 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) { … } static noinline_for_stack int write_bitmap_entries(struct btrfs_io_ctl *io_ctl, struct list_head *bitmap_list) { … } static int flush_dirty_cache(struct inode *inode) { … } static void noinline_for_stack cleanup_bitmap_list(struct list_head *bitmap_list) { … } static void noinline_for_stack cleanup_write_cache_enospc(struct inode *inode, struct btrfs_io_ctl *io_ctl, struct extent_state **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 btrfs_wait_cache_io(struct btrfs_trans_handle *trans, struct btrfs_block_group *block_group, struct btrfs_path *path) { … } /* * Write out cached info to an inode. * * @inode: freespace inode we are writing out * @ctl: free space cache we are going to write out * @block_group: block_group for this cache if it belongs to a block_group * @io_ctl: holds context for the io * @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 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) { … } int btrfs_write_out_cache(struct btrfs_trans_handle *trans, struct btrfs_block_group *block_group, struct btrfs_path *path) { … } static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit, u64 offset) { … } static inline unsigned long bytes_to_bits(u64 bytes, u32 unit) { … } static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl, u64 offset) { … } static int tree_insert_offset(struct btrfs_free_space_ctl *ctl, struct btrfs_free_cluster *cluster, struct btrfs_free_space *new_entry) { … } /* * This is a little subtle. We *only* have ->max_extent_size set if we actually * searched through the bitmap and figured out the largest ->max_extent_size, * otherwise it's 0. In the case that it's 0 we don't want to tell the * allocator the wrong thing, we want to use the actual real max_extent_size * we've found already if it's larger, or we want to use ->bytes. * * This matters because find_free_space() will skip entries who's ->bytes is * less than the required bytes. So if we didn't search down this bitmap, we * may pick some previous entry that has a smaller ->max_extent_size than we * have. For example, assume we have two entries, one that has * ->max_extent_size set to 4K and ->bytes set to 1M. A second entry hasn't set * ->max_extent_size yet, has ->bytes set to 8K and it's contiguous. We will * call into find_free_space(), and return with max_extent_size == 4K, because * that first bitmap entry had ->max_extent_size set, but the second one did * not. If instead we returned 8K we'd come in searching for 8K, and find the * 8K contiguous range. * * Consider the other case, we have 2 8K chunks in that second entry and still * don't have ->max_extent_size set. We'll return 16K, and the next time the * allocator comes in it'll fully search our second bitmap, and this time it'll * get an uptodate value of 8K as the maximum chunk size. Then we'll get the * right allocation the next loop through. */ static inline u64 get_max_extent_size(const struct btrfs_free_space *entry) { … } /* * We want the largest entry to be leftmost, so this is inverted from what you'd * normally expect. */ static bool entry_less(struct rb_node *node, const struct rb_node *parent) { … } /* * searches the tree for the given offset. * * 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. */ static struct btrfs_free_space * tree_search_offset(struct btrfs_free_space_ctl *ctl, u64 offset, int bitmap_only, int fuzzy) { … } static inline void unlink_free_space(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, bool update_stat) { … } static int link_free_space(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info) { … } static void relink_bitmap_entry(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info) { … } static inline void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, u64 offset, u64 bytes, bool update_stat) { … } static void btrfs_bitmap_set_bits(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, u64 offset, u64 bytes) { … } /* * If we can not find suitable extent, we will use bytes to record * the size of the max extent. */ static int search_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *bitmap_info, u64 *offset, u64 *bytes, bool for_alloc) { … } /* Cache the size of the max extent in bytes */ static struct btrfs_free_space * find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, unsigned long align, u64 *max_extent_size, bool use_bytes_index) { … } static void add_new_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, u64 offset) { … } static void free_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *bitmap_info) { … } static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *bitmap_info, u64 *offset, u64 *bytes) { … } static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, u64 offset, u64 bytes, enum btrfs_trim_state trim_state) { … } static bool use_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info) { … } static const struct btrfs_free_space_op free_space_op = …; static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info) { … } /* * Free space merging rules: * 1) Merge trimmed areas together * 2) Let untrimmed areas coalesce with trimmed areas * 3) Always pull neighboring regions from bitmaps * * The above rules are for when we merge free space based on btrfs_trim_state. * Rules 2 and 3 are subtle because they are suboptimal, but are done for the * same reason: to promote larger extent regions which makes life easier for * find_free_extent(). Rule 2 enables coalescing based on the common path * being returning free space from btrfs_finish_extent_commit(). So when free * space is trimmed, it will prevent aggregating trimmed new region and * untrimmed regions in the rb_tree. Rule 3 is purely to obtain larger extents * and provide find_free_extent() with the largest extents possible hoping for * the reuse path. */ static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, bool update_stat) { … } static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, bool update_stat) { … } static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info, bool update_stat) { … } /* * 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) { … } static int __btrfs_add_free_space(struct btrfs_block_group *block_group, u64 offset, u64 bytes, enum btrfs_trim_state trim_state) { … } static int __btrfs_add_free_space_zoned(struct btrfs_block_group *block_group, u64 bytenr, u64 size, bool used) { … } int btrfs_add_free_space(struct btrfs_block_group *block_group, u64 bytenr, u64 size) { … } int btrfs_add_free_space_unused(struct btrfs_block_group *block_group, u64 bytenr, u64 size) { … } /* * This is a subtle distinction because when adding free space back in general, * we want it to be added as untrimmed for async. But in the case where we add * it on loading of a block group, we want to consider it trimmed. */ int btrfs_add_free_space_async_trimmed(struct btrfs_block_group *block_group, u64 bytenr, u64 size) { … } int btrfs_remove_free_space(struct btrfs_block_group *block_group, u64 offset, u64 bytes) { … } void btrfs_dump_free_space(struct btrfs_block_group *block_group, u64 bytes) { … } void btrfs_init_free_space_ctl(struct btrfs_block_group *block_group, struct btrfs_free_space_ctl *ctl) { … } /* * 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 void __btrfs_return_cluster_to_free_space( struct btrfs_block_group *block_group, struct btrfs_free_cluster *cluster) { … } void btrfs_remove_free_space_cache(struct btrfs_block_group *block_group) { … } /* * Walk @block_group's free space rb_tree to determine if everything is trimmed. */ bool btrfs_is_free_space_trimmed(struct btrfs_block_group *block_group) { … } u64 btrfs_find_space_for_alloc(struct btrfs_block_group *block_group, u64 offset, u64 bytes, u64 empty_size, u64 *max_extent_size) { … } /* * 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. */ void btrfs_return_cluster_to_free_space( struct btrfs_block_group *block_group, struct btrfs_free_cluster *cluster) { … } static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group *block_group, struct btrfs_free_cluster *cluster, struct btrfs_free_space *entry, u64 bytes, u64 min_start, u64 *max_extent_size) { … } /* * 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 *block_group, struct btrfs_free_cluster *cluster, u64 bytes, u64 min_start, u64 *max_extent_size) { … } static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group, struct btrfs_free_space *entry, struct btrfs_free_cluster *cluster, u64 offset, u64 bytes, u64 cont1_bytes, u64 min_bytes) { … } /* * This searches the block group for just extents to fill the cluster with. * 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. */ static noinline int setup_cluster_no_bitmap(struct btrfs_block_group *block_group, struct btrfs_free_cluster *cluster, struct list_head *bitmaps, u64 offset, u64 bytes, u64 cont1_bytes, u64 min_bytes) { … } /* * This specifically looks for bitmaps that may work in the cluster, we assume * that we have already failed to find extents that will work. */ static noinline int setup_cluster_bitmap(struct btrfs_block_group *block_group, struct btrfs_free_cluster *cluster, struct list_head *bitmaps, u64 offset, u64 bytes, u64 cont1_bytes, u64 min_bytes) { … } /* * here we try to find a cluster of blocks in a block group. The goal * is to find at least bytes+empty_size. * We might not find them all in one contiguous area. * * returns zero and sets up cluster if things worked out, otherwise * it returns -enospc */ int btrfs_find_space_cluster(struct btrfs_block_group *block_group, struct btrfs_free_cluster *cluster, u64 offset, u64 bytes, u64 empty_size) { … } /* * simple code to zero out a cluster */ void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster) { … } static int do_trimming(struct btrfs_block_group *block_group, u64 *total_trimmed, u64 start, u64 bytes, u64 reserved_start, u64 reserved_bytes, enum btrfs_trim_state reserved_trim_state, struct btrfs_trim_range *trim_entry) { … } /* * If @async is set, then we will trim 1 region and return. */ static int trim_no_bitmap(struct btrfs_block_group *block_group, u64 *total_trimmed, u64 start, u64 end, u64 minlen, bool async) { … } /* * If we break out of trimming a bitmap prematurely, we should reset the * trimming bit. In a rather contrieved case, it's possible to race here so * reset the state to BTRFS_TRIM_STATE_UNTRIMMED. * * start = start of bitmap * end = near end of bitmap * * Thread 1: Thread 2: * trim_bitmaps(start) * trim_bitmaps(end) * end_trimming_bitmap() * reset_trimming_bitmap() */ static void reset_trimming_bitmap(struct btrfs_free_space_ctl *ctl, u64 offset) { … } static void end_trimming_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *entry) { … } /* * If @async is set, then we will trim 1 region and return. */ static int trim_bitmaps(struct btrfs_block_group *block_group, u64 *total_trimmed, u64 start, u64 end, u64 minlen, u64 maxlen, bool async) { … } int btrfs_trim_block_group(struct btrfs_block_group *block_group, u64 *trimmed, u64 start, u64 end, u64 minlen) { … } int btrfs_trim_block_group_extents(struct btrfs_block_group *block_group, u64 *trimmed, u64 start, u64 end, u64 minlen, bool async) { … } int btrfs_trim_block_group_bitmaps(struct btrfs_block_group *block_group, u64 *trimmed, u64 start, u64 end, u64 minlen, u64 maxlen, bool async) { … } bool btrfs_free_space_cache_v1_active(struct btrfs_fs_info *fs_info) { … } static int cleanup_free_space_cache_v1(struct btrfs_fs_info *fs_info, struct btrfs_trans_handle *trans) { … } int btrfs_set_free_space_cache_v1_active(struct btrfs_fs_info *fs_info, bool active) { … } int __init btrfs_free_space_init(void) { … } void __cold btrfs_free_space_exit(void) { … } #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS /* * 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, u64 offset, u64 bytes, bool bitmap) { … } /* * 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. */ int test_check_exists(struct btrfs_block_group *cache, u64 offset, u64 bytes) { … } #endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */
Codebase Browser
linux