// SPDX-License-Identifier: GPL-2.0 /* * linux/fs/ext2/balloc.c * * Copyright (C) 1992, 1993, 1994, 1995 * Remy Card ([email protected]) * Laboratoire MASI - Institut Blaise Pascal * Universite Pierre et Marie Curie (Paris VI) * * Enhanced block allocation by Stephen Tweedie ([email protected]), 1993 * Big-endian to little-endian byte-swapping/bitmaps by * David S. Miller ([email protected]), 1995 */ #include "ext2.h" #include <linux/quotaops.h> #include <linux/slab.h> #include <linux/sched.h> #include <linux/cred.h> #include <linux/buffer_head.h> #include <linux/capability.h> /* * balloc.c contains the blocks allocation and deallocation routines */ /* * The free blocks are managed by bitmaps. A file system contains several * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap * block for inodes, N blocks for the inode table and data blocks. * * The file system contains group descriptors which are located after the * super block. Each descriptor contains the number of the bitmap block and * the free blocks count in the block. The descriptors are loaded in memory * when a file system is mounted (see ext2_fill_super). */ struct ext2_group_desc * ext2_get_group_desc(struct super_block * sb, unsigned int block_group, struct buffer_head ** bh) { … } static int ext2_valid_block_bitmap(struct super_block *sb, struct ext2_group_desc *desc, unsigned int block_group, struct buffer_head *bh) { … } /* * Read the bitmap for a given block_group,and validate the * bits for block/inode/inode tables are set in the bitmaps * * Return buffer_head on success or NULL in case of failure. */ static struct buffer_head * read_block_bitmap(struct super_block *sb, unsigned int block_group) { … } static void group_adjust_blocks(struct super_block *sb, int group_no, struct ext2_group_desc *desc, struct buffer_head *bh, int count) { … } /* * The reservation window structure operations * -------------------------------------------- * Operations include: * dump, find, add, remove, is_empty, find_next_reservable_window, etc. * * We use a red-black tree to represent per-filesystem reservation * windows. * */ /** * __rsv_window_dump() -- Dump the filesystem block allocation reservation map * @root: root of per-filesystem reservation rb tree * @verbose: verbose mode * @fn: function which wishes to dump the reservation map * * If verbose is turned on, it will print the whole block reservation * windows(start, end). Otherwise, it will only print out the "bad" windows, * those windows that overlap with their immediate neighbors. */ #if 1 static void __rsv_window_dump(struct rb_root *root, int verbose, const char *fn) { … } #define rsv_window_dump(root, verbose) … #else #define rsv_window_dump … #endif /** * goal_in_my_reservation() * @rsv: inode's reservation window * @grp_goal: given goal block relative to the allocation block group * @group: the current allocation block group * @sb: filesystem super block * * Test if the given goal block (group relative) is within the file's * own block reservation window range. * * If the reservation window is outside the goal allocation group, return 0; * grp_goal (given goal block) could be -1, which means no specific * goal block. In this case, always return 1. * If the goal block is within the reservation window, return 1; * otherwise, return 0; */ static int goal_in_my_reservation(struct ext2_reserve_window *rsv, ext2_grpblk_t grp_goal, unsigned int group, struct super_block * sb) { … } /** * search_reserve_window() * @root: root of reservation tree * @goal: target allocation block * * Find the reserved window which includes the goal, or the previous one * if the goal is not in any window. * Returns NULL if there are no windows or if all windows start after the goal. */ static struct ext2_reserve_window_node * search_reserve_window(struct rb_root *root, ext2_fsblk_t goal) { … } /* * ext2_rsv_window_add() -- Insert a window to the block reservation rb tree. * @sb: super block * @rsv: reservation window to add * * Must be called with rsv_lock held. */ void ext2_rsv_window_add(struct super_block *sb, struct ext2_reserve_window_node *rsv) { … } /** * rsv_window_remove() -- unlink a window from the reservation rb tree * @sb: super block * @rsv: reservation window to remove * * Mark the block reservation window as not allocated, and unlink it * from the filesystem reservation window rb tree. Must be called with * rsv_lock held. */ static void rsv_window_remove(struct super_block *sb, struct ext2_reserve_window_node *rsv) { … } /* * rsv_is_empty() -- Check if the reservation window is allocated. * @rsv: given reservation window to check * * returns 1 if the end block is EXT2_RESERVE_WINDOW_NOT_ALLOCATED. */ static inline int rsv_is_empty(struct ext2_reserve_window *rsv) { … } /** * ext2_init_block_alloc_info() * @inode: file inode structure * * Allocate and initialize the reservation window structure, and * link the window to the ext2 inode structure at last * * The reservation window structure is only dynamically allocated * and linked to ext2 inode the first time the open file * needs a new block. So, before every ext2_new_block(s) call, for * regular files, we should check whether the reservation window * structure exists or not. In the latter case, this function is called. * Fail to do so will result in block reservation being turned off for that * open file. * * This function is called from ext2_get_blocks_handle(), also called * when setting the reservation window size through ioctl before the file * is open for write (needs block allocation). * * Needs truncate_mutex protection prior to calling this function. */ void ext2_init_block_alloc_info(struct inode *inode) { … } /** * ext2_discard_reservation() * @inode: inode * * Discard(free) block reservation window on last file close, or truncate * or at last iput(). * * It is being called in three cases: * ext2_release_file(): last writer closes the file * ext2_clear_inode(): last iput(), when nobody links to this file. * ext2_truncate(): when the block indirect map is about to change. */ void ext2_discard_reservation(struct inode *inode) { … } /** * ext2_free_blocks() -- Free given blocks and update quota and i_blocks * @inode: inode * @block: start physical block to free * @count: number of blocks to free */ void ext2_free_blocks(struct inode * inode, ext2_fsblk_t block, unsigned long count) { … } /** * bitmap_search_next_usable_block() * @start: the starting block (group relative) of the search * @bh: bufferhead contains the block group bitmap * @maxblocks: the ending block (group relative) of the reservation * * The bitmap search --- search forward through the actual bitmap on disk until * we find a bit free. */ static ext2_grpblk_t bitmap_search_next_usable_block(ext2_grpblk_t start, struct buffer_head *bh, ext2_grpblk_t maxblocks) { … } /** * find_next_usable_block() * @start: the starting block (group relative) to find next * allocatable block in bitmap. * @bh: bufferhead contains the block group bitmap * @maxblocks: the ending block (group relative) for the search * * Find an allocatable block in a bitmap. We perform the "most * appropriate allocation" algorithm of looking for a free block near * the initial goal; then for a free byte somewhere in the bitmap; * then for any free bit in the bitmap. */ static ext2_grpblk_t find_next_usable_block(int start, struct buffer_head *bh, int maxblocks) { … } /** * ext2_try_to_allocate() * @sb: superblock * @group: given allocation block group * @bitmap_bh: bufferhead holds the block bitmap * @grp_goal: given target block within the group * @count: target number of blocks to allocate * @my_rsv: reservation window * * Attempt to allocate blocks within a give range. Set the range of allocation * first, then find the first free bit(s) from the bitmap (within the range), * and at last, allocate the blocks by claiming the found free bit as allocated. * * To set the range of this allocation: * if there is a reservation window, only try to allocate block(s) * from the file's own reservation window; * Otherwise, the allocation range starts from the give goal block, * ends at the block group's last block. * * If we failed to allocate the desired block then we may end up crossing to a * new bitmap. */ static int ext2_try_to_allocate(struct super_block *sb, int group, struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal, unsigned long *count, struct ext2_reserve_window *my_rsv) { … } /** * find_next_reservable_window - Find a reservable space within the given range. * @search_head: The list to search. * @my_rsv: The reservation we're currently using. * @sb: The super block. * @start_block: The first block we consider to start the real search from * @last_block: The maximum block number that our goal reservable space * could start from. * * It does not allocate the reservation window: alloc_new_reservation() * will do the work later. * * We search the given range, rather than the whole reservation double * linked list, (start_block, last_block) to find a free region that is * of my size and has not been reserved. * * @search_head is not necessarily the list head of the whole filesystem. * We have both head and @start_block to assist the search for the * reservable space. The list starts from head, but we will shift to * the place where start_block is, then start from there, when looking * for a reservable space. * * @last_block is normally the last block in this group. The search will end * when we found the start of next possible reservable space is out * of this boundary. This could handle the cross boundary reservation * window request. * * Return: -1 if we could not find a range of sufficient size. If we could, * return 0 and fill in @my_rsv with the range information. */ static int find_next_reservable_window( struct ext2_reserve_window_node *search_head, struct ext2_reserve_window_node *my_rsv, struct super_block * sb, ext2_fsblk_t start_block, ext2_fsblk_t last_block) { … } /** * alloc_new_reservation - Allocate a new reservation window. * @my_rsv: The reservation we're currently using. * @grp_goal: The goal block relative to the start of the group. * @sb: The super block. * @group: The group we are trying to allocate in. * @bitmap_bh: The block group block bitmap. * * To make a new reservation, we search part of the filesystem reservation * list (the list inside the group). We try to allocate a new * reservation window near @grp_goal, or the beginning of the * group, if @grp_goal is negative. * * We first find a reservable space after the goal, then from there, * we check the bitmap for the first free block after it. If there is * no free block until the end of group, then the whole group is full, * we failed. Otherwise, check if the free block is inside the expected * reservable space, if so, we succeed. * * If the first free block is outside the reservable space, then start * from the first free block, we search for next available space, and * go on. * * on succeed, a new reservation will be found and inserted into the * list. It contains at least one free block, and it does not overlap * with other reservation windows. * * Return: 0 on success, -1 if we failed to find a reservation window * in this group */ static int alloc_new_reservation(struct ext2_reserve_window_node *my_rsv, ext2_grpblk_t grp_goal, struct super_block *sb, unsigned int group, struct buffer_head *bitmap_bh) { … } /** * try_to_extend_reservation() * @my_rsv: given reservation window * @sb: super block * @size: the delta to extend * * Attempt to expand the reservation window large enough to have * required number of free blocks * * Since ext2_try_to_allocate() will always allocate blocks within * the reservation window range, if the window size is too small, * multiple blocks allocation has to stop at the end of the reservation * window. To make this more efficient, given the total number of * blocks needed and the current size of the window, we try to * expand the reservation window size if necessary on a best-effort * basis before ext2_new_blocks() tries to allocate blocks. */ static void try_to_extend_reservation(struct ext2_reserve_window_node *my_rsv, struct super_block *sb, int size) { … } /** * ext2_try_to_allocate_with_rsv() * @sb: superblock * @group: given allocation block group * @bitmap_bh: bufferhead holds the block bitmap * @grp_goal: given target block within the group * @count: target number of blocks to allocate * @my_rsv: reservation window * * This is the main function used to allocate a new block and its reservation * window. * * Each time when a new block allocation is need, first try to allocate from * its own reservation. If it does not have a reservation window, instead of * looking for a free bit on bitmap first, then look up the reservation list to * see if it is inside somebody else's reservation window, we try to allocate a * reservation window for it starting from the goal first. Then do the block * allocation within the reservation window. * * This will avoid keeping on searching the reservation list again and * again when somebody is looking for a free block (without * reservation), and there are lots of free blocks, but they are all * being reserved. * * We use a red-black tree for the per-filesystem reservation list. */ static ext2_grpblk_t ext2_try_to_allocate_with_rsv(struct super_block *sb, unsigned int group, struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal, struct ext2_reserve_window_node * my_rsv, unsigned long *count) { … } /** * ext2_has_free_blocks() * @sbi: in-core super block structure. * * Check if filesystem has at least 1 free block available for allocation. */ static int ext2_has_free_blocks(struct ext2_sb_info *sbi) { … } /* * Returns 1 if the passed-in block region is valid; 0 if some part overlaps * with filesystem metadata blocks. */ int ext2_data_block_valid(struct ext2_sb_info *sbi, ext2_fsblk_t start_blk, unsigned int count) { … } /* * ext2_new_blocks() -- core block(s) allocation function * @inode: file inode * @goal: given target block(filesystem wide) * @count: target number of blocks to allocate * @errp: error code * @flags: allocate flags * * ext2_new_blocks uses a goal block to assist allocation. If the goal is * free, or there is a free block within 32 blocks of the goal, that block * is allocated. Otherwise a forward search is made for a free block; within * each block group the search first looks for an entire free byte in the block * bitmap, and then for any free bit if that fails. * This function also updates quota and i_blocks field. */ ext2_fsblk_t ext2_new_blocks(struct inode *inode, ext2_fsblk_t goal, unsigned long *count, int *errp, unsigned int flags) { … } #ifdef EXT2FS_DEBUG unsigned long ext2_count_free(struct buffer_head *map, unsigned int numchars) { return numchars * BITS_PER_BYTE - memweight(map->b_data, numchars); } #endif /* EXT2FS_DEBUG */ unsigned long ext2_count_free_blocks (struct super_block * sb) { … } static inline int test_root(int a, int b) { … } static int ext2_group_sparse(int group) { … } /** * ext2_bg_has_super - number of blocks used by the superblock in group * @sb: superblock for filesystem * @group: group number to check * * Return the number of blocks used by the superblock (primary or backup) * in this group. Currently this will be only 0 or 1. */ int ext2_bg_has_super(struct super_block *sb, int group) { … } /** * ext2_bg_num_gdb - number of blocks used by the group table in group * @sb: superblock for filesystem * @group: group number to check * * Return the number of blocks used by the group descriptor table * (primary or backup) in this group. In the future there may be a * different number of descriptor blocks in each group. */ unsigned long ext2_bg_num_gdb(struct super_block *sb, int group) { … }
Codebase Browser
linux