^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * linux/fs/ext2/balloc.c
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Copyright (C) 1992, 1993, 1994, 1995
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Remy Card (card@masi.ibp.fr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * Laboratoire MASI - Institut Blaise Pascal
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * Universite Pierre et Marie Curie (Paris VI)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * Big-endian to little-endian byte-swapping/bitmaps by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * David S. Miller (davem@caip.rutgers.edu), 1995
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) #include "ext2.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #include <linux/quotaops.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) #include <linux/sched.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) #include <linux/cred.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) #include <linux/buffer_head.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #include <linux/capability.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * balloc.c contains the blocks allocation and deallocation routines
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * The free blocks are managed by bitmaps. A file system contains several
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * block for inodes, N blocks for the inode table and data blocks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) * The file system contains group descriptors which are located after the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) * super block. Each descriptor contains the number of the bitmap block and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * the free blocks count in the block. The descriptors are loaded in memory
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) * when a file system is mounted (see ext2_fill_super).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) #define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) struct ext2_group_desc * ext2_get_group_desc(struct super_block * sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) unsigned int block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) struct buffer_head ** bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) unsigned long group_desc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) unsigned long offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) struct ext2_group_desc * desc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) struct ext2_sb_info *sbi = EXT2_SB(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) if (block_group >= sbi->s_groups_count) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) WARN(1, "block_group >= groups_count - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) "block_group = %d, groups_count = %lu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) block_group, sbi->s_groups_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) group_desc = block_group >> EXT2_DESC_PER_BLOCK_BITS(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) offset = block_group & (EXT2_DESC_PER_BLOCK(sb) - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) if (!sbi->s_group_desc[group_desc]) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) WARN(1, "Group descriptor not loaded - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) "block_group = %d, group_desc = %lu, desc = %lu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) block_group, group_desc, offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) desc = (struct ext2_group_desc *) sbi->s_group_desc[group_desc]->b_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) if (bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) *bh = sbi->s_group_desc[group_desc];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) return desc + offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) static int ext2_valid_block_bitmap(struct super_block *sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) struct ext2_group_desc *desc,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) unsigned int block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) struct buffer_head *bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) ext2_grpblk_t offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) ext2_grpblk_t next_zero_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) ext2_fsblk_t bitmap_blk;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) ext2_fsblk_t group_first_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) group_first_block = ext2_group_first_block_no(sb, block_group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) /* check whether block bitmap block number is set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) bitmap_blk = le32_to_cpu(desc->bg_block_bitmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) offset = bitmap_blk - group_first_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) if (!ext2_test_bit(offset, bh->b_data))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) /* bad block bitmap */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) /* check whether the inode bitmap block number is set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) bitmap_blk = le32_to_cpu(desc->bg_inode_bitmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) offset = bitmap_blk - group_first_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) if (!ext2_test_bit(offset, bh->b_data))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) /* bad block bitmap */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) /* check whether the inode table block number is set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) bitmap_blk = le32_to_cpu(desc->bg_inode_table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) offset = bitmap_blk - group_first_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) next_zero_bit = ext2_find_next_zero_bit(bh->b_data,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) offset + EXT2_SB(sb)->s_itb_per_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) if (next_zero_bit >= offset + EXT2_SB(sb)->s_itb_per_group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) /* good bitmap for inode tables */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) err_out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) ext2_error(sb, __func__,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) "Invalid block bitmap - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) "block_group = %d, block = %lu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) block_group, bitmap_blk);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) * Read the bitmap for a given block_group,and validate the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) * bits for block/inode/inode tables are set in the bitmaps
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) * Return buffer_head on success or NULL in case of failure.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) static struct buffer_head *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) read_block_bitmap(struct super_block *sb, unsigned int block_group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) struct ext2_group_desc * desc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) struct buffer_head * bh = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) ext2_fsblk_t bitmap_blk;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) desc = ext2_get_group_desc(sb, block_group, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) if (!desc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) bitmap_blk = le32_to_cpu(desc->bg_block_bitmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) bh = sb_getblk(sb, bitmap_blk);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) if (unlikely(!bh)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) ext2_error(sb, __func__,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) "Cannot read block bitmap - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) "block_group = %d, block_bitmap = %u",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) block_group, le32_to_cpu(desc->bg_block_bitmap));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) if (likely(bh_uptodate_or_lock(bh)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) return bh;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) if (bh_submit_read(bh) < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) brelse(bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) ext2_error(sb, __func__,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) "Cannot read block bitmap - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) "block_group = %d, block_bitmap = %u",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) block_group, le32_to_cpu(desc->bg_block_bitmap));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) ext2_valid_block_bitmap(sb, desc, block_group, bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) * file system mounted not to panic on error, continue with corrupt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) * bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) return bh;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) static void group_adjust_blocks(struct super_block *sb, int group_no,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) struct ext2_group_desc *desc, struct buffer_head *bh, int count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) if (count) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) struct ext2_sb_info *sbi = EXT2_SB(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) unsigned free_blocks;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) spin_lock(sb_bgl_lock(sbi, group_no));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) free_blocks = le16_to_cpu(desc->bg_free_blocks_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) desc->bg_free_blocks_count = cpu_to_le16(free_blocks + count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) spin_unlock(sb_bgl_lock(sbi, group_no));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) mark_buffer_dirty(bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) * The reservation window structure operations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) * --------------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) * Operations include:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) * dump, find, add, remove, is_empty, find_next_reservable_window, etc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) * We use a red-black tree to represent per-filesystem reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) * windows.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) * @root: root of per-filesystem reservation rb tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) * @verbose: verbose mode
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) * @fn: function which wishes to dump the reservation map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) * If verbose is turned on, it will print the whole block reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) * windows(start, end). Otherwise, it will only print out the "bad" windows,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) * those windows that overlap with their immediate neighbors.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) #if 1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) static void __rsv_window_dump(struct rb_root *root, int verbose,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) const char *fn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) struct rb_node *n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) struct ext2_reserve_window_node *rsv, *prev;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) int bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) restart:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) n = rb_first(root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) bad = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) prev = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) printk("Block Allocation Reservation Windows Map (%s):\n", fn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) while (n) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) if (verbose)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) printk("reservation window 0x%p "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) "start: %lu, end: %lu\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) rsv, rsv->rsv_start, rsv->rsv_end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) printk("Bad reservation %p (start >= end)\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) rsv);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) bad = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) if (prev && prev->rsv_end >= rsv->rsv_start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) printk("Bad reservation %p (prev->end >= start)\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) rsv);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) bad = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) if (bad) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) if (!verbose) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) printk("Restarting reservation walk in verbose mode\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) verbose = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) goto restart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) n = rb_next(n);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) prev = rsv;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) printk("Window map complete.\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) BUG_ON(bad);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) #define rsv_window_dump(root, verbose) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) __rsv_window_dump((root), (verbose), __func__)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) #else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) #define rsv_window_dump(root, verbose) do {} while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) * goal_in_my_reservation()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) * @rsv: inode's reservation window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) * @grp_goal: given goal block relative to the allocation block group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) * @group: the current allocation block group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) * @sb: filesystem super block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) * Test if the given goal block (group relative) is within the file's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) * own block reservation window range.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) * If the reservation window is outside the goal allocation group, return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) * grp_goal (given goal block) could be -1, which means no specific
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) * goal block. In this case, always return 1.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) * If the goal block is within the reservation window, return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) * otherwise, return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) goal_in_my_reservation(struct ext2_reserve_window *rsv, ext2_grpblk_t grp_goal,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) unsigned int group, struct super_block * sb)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) ext2_fsblk_t group_first_block, group_last_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) group_first_block = ext2_group_first_block_no(sb, group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) group_last_block = ext2_group_last_block_no(sb, group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) if ((rsv->_rsv_start > group_last_block) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) (rsv->_rsv_end < group_first_block))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) || (grp_goal + group_first_block > rsv->_rsv_end)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) * search_reserve_window()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) * @root: root of reservation tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) * @goal: target allocation block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) * Find the reserved window which includes the goal, or the previous one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) * if the goal is not in any window.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) * Returns NULL if there are no windows or if all windows start after the goal.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) static struct ext2_reserve_window_node *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) search_reserve_window(struct rb_root *root, ext2_fsblk_t goal)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) struct rb_node *n = root->rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) struct ext2_reserve_window_node *rsv;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) if (!n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) if (goal < rsv->rsv_start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) n = n->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) else if (goal > rsv->rsv_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) n = n->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) return rsv;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) } while (n);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) * We've fallen off the end of the tree: the goal wasn't inside
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) * any particular node. OK, the previous node must be to one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) * side of the interval containing the goal. If it's the RHS,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) * we need to back up one.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) if (rsv->rsv_start > goal) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) n = rb_prev(&rsv->rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) return rsv;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) * ext2_rsv_window_add() -- Insert a window to the block reservation rb tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) * @sb: super block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) * @rsv: reservation window to add
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) * Must be called with rsv_lock held.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) void ext2_rsv_window_add(struct super_block *sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) struct ext2_reserve_window_node *rsv)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) struct rb_root *root = &EXT2_SB(sb)->s_rsv_window_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) struct rb_node *node = &rsv->rsv_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) ext2_fsblk_t start = rsv->rsv_start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) struct rb_node ** p = &root->rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) struct rb_node * parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) struct ext2_reserve_window_node *this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) while (*p)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) parent = *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) this = rb_entry(parent, struct ext2_reserve_window_node, rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) if (start < this->rsv_start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) p = &(*p)->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) else if (start > this->rsv_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) p = &(*p)->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) rsv_window_dump(root, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) BUG();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) rb_link_node(node, parent, p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) rb_insert_color(node, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) * rsv_window_remove() -- unlink a window from the reservation rb tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) * @sb: super block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) * @rsv: reservation window to remove
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) * Mark the block reservation window as not allocated, and unlink it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) * from the filesystem reservation window rb tree. Must be called with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) * rsv_lock held.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) static void rsv_window_remove(struct super_block *sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) struct ext2_reserve_window_node *rsv)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) rsv->rsv_alloc_hit = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) rb_erase(&rsv->rsv_node, &EXT2_SB(sb)->s_rsv_window_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) * rsv_is_empty() -- Check if the reservation window is allocated.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) * @rsv: given reservation window to check
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) * returns 1 if the end block is EXT2_RESERVE_WINDOW_NOT_ALLOCATED.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) static inline int rsv_is_empty(struct ext2_reserve_window *rsv)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) /* a valid reservation end block could not be 0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) return (rsv->_rsv_end == EXT2_RESERVE_WINDOW_NOT_ALLOCATED);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) * ext2_init_block_alloc_info()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) * @inode: file inode structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) * Allocate and initialize the reservation window structure, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) * link the window to the ext2 inode structure at last
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) * The reservation window structure is only dynamically allocated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) * and linked to ext2 inode the first time the open file
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) * needs a new block. So, before every ext2_new_block(s) call, for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) * regular files, we should check whether the reservation window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) * structure exists or not. In the latter case, this function is called.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) * Fail to do so will result in block reservation being turned off for that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) * open file.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) * This function is called from ext2_get_blocks_handle(), also called
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) * when setting the reservation window size through ioctl before the file
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) * is open for write (needs block allocation).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) * Needs truncate_mutex protection prior to calling this function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) void ext2_init_block_alloc_info(struct inode *inode)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) struct ext2_inode_info *ei = EXT2_I(inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) struct ext2_block_alloc_info *block_i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) struct super_block *sb = inode->i_sb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) if (block_i) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) struct ext2_reserve_window_node *rsv = &block_i->rsv_window_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) * if filesystem is mounted with NORESERVATION, the goal
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) * reservation window size is set to zero to indicate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) * block reservation is off
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) if (!test_opt(sb, RESERVATION))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) rsv->rsv_goal_size = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) rsv->rsv_goal_size = EXT2_DEFAULT_RESERVE_BLOCKS;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) rsv->rsv_alloc_hit = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) block_i->last_alloc_logical_block = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) block_i->last_alloc_physical_block = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) ei->i_block_alloc_info = block_i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) * ext2_discard_reservation()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) * @inode: inode
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) * Discard(free) block reservation window on last file close, or truncate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) * or at last iput().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) * It is being called in three cases:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) * ext2_release_file(): last writer closes the file
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) * ext2_clear_inode(): last iput(), when nobody links to this file.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) * ext2_truncate(): when the block indirect map is about to change.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) void ext2_discard_reservation(struct inode *inode)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) struct ext2_inode_info *ei = EXT2_I(inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) struct ext2_block_alloc_info *block_i = ei->i_block_alloc_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) struct ext2_reserve_window_node *rsv;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) spinlock_t *rsv_lock = &EXT2_SB(inode->i_sb)->s_rsv_window_lock;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) if (!block_i)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) rsv = &block_i->rsv_window_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) if (!rsv_is_empty(&rsv->rsv_window)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) spin_lock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) if (!rsv_is_empty(&rsv->rsv_window))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) rsv_window_remove(inode->i_sb, rsv);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) spin_unlock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) * ext2_free_blocks() -- Free given blocks and update quota and i_blocks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) * @inode: inode
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) * @block: start physical block to free
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) * @count: number of blocks to free
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) void ext2_free_blocks (struct inode * inode, unsigned long block,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) unsigned long count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) struct buffer_head *bitmap_bh = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) struct buffer_head * bh2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) unsigned long block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) unsigned long bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) unsigned long i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) unsigned long overflow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) struct super_block * sb = inode->i_sb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) struct ext2_sb_info * sbi = EXT2_SB(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) struct ext2_group_desc * desc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) struct ext2_super_block * es = sbi->s_es;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) unsigned freed = 0, group_freed;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) if (!ext2_data_block_valid(sbi, block, count)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) ext2_error (sb, "ext2_free_blocks",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) "Freeing blocks not in datazone - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) "block = %lu, count = %lu", block, count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) goto error_return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) ext2_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) do_more:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) overflow = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) block_group = (block - le32_to_cpu(es->s_first_data_block)) /
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) EXT2_BLOCKS_PER_GROUP(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) bit = (block - le32_to_cpu(es->s_first_data_block)) %
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) EXT2_BLOCKS_PER_GROUP(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) * Check to see if we are freeing blocks across a group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) * boundary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) if (bit + count > EXT2_BLOCKS_PER_GROUP(sb)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) overflow = bit + count - EXT2_BLOCKS_PER_GROUP(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) count -= overflow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) brelse(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) bitmap_bh = read_block_bitmap(sb, block_group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) if (!bitmap_bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) goto error_return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) desc = ext2_get_group_desc (sb, block_group, &bh2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) if (!desc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) goto error_return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) in_range (block, le32_to_cpu(desc->bg_inode_table),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) sbi->s_itb_per_group) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) sbi->s_itb_per_group)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) ext2_error (sb, "ext2_free_blocks",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) "Freeing blocks in system zones - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) "Block = %lu, count = %lu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) block, count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) goto error_return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) for (i = 0, group_freed = 0; i < count; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) if (!ext2_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) bit + i, bitmap_bh->b_data)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) ext2_error(sb, __func__,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) "bit already cleared for block %lu", block + i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) group_freed++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) mark_buffer_dirty(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) if (sb->s_flags & SB_SYNCHRONOUS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) sync_dirty_buffer(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) group_adjust_blocks(sb, block_group, desc, bh2, group_freed);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) freed += group_freed;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) if (overflow) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) block += count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) count = overflow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) goto do_more;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) error_return:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) brelse(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) if (freed) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) percpu_counter_add(&sbi->s_freeblocks_counter, freed);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) dquot_free_block_nodirty(inode, freed);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) mark_inode_dirty(inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) * bitmap_search_next_usable_block()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) * @start: the starting block (group relative) of the search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) * @bh: bufferhead contains the block group bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) * @maxblocks: the ending block (group relative) of the reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) * The bitmap search --- search forward through the actual bitmap on disk until
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) * we find a bit free.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) static ext2_grpblk_t
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) bitmap_search_next_usable_block(ext2_grpblk_t start, struct buffer_head *bh,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) ext2_grpblk_t maxblocks)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) ext2_grpblk_t next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) next = ext2_find_next_zero_bit(bh->b_data, maxblocks, start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) if (next >= maxblocks)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) return next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) * find_next_usable_block()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) * @start: the starting block (group relative) to find next
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) * allocatable block in bitmap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) * @bh: bufferhead contains the block group bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) * @maxblocks: the ending block (group relative) for the search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) * Find an allocatable block in a bitmap. We perform the "most
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) * appropriate allocation" algorithm of looking for a free block near
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) * the initial goal; then for a free byte somewhere in the bitmap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) * then for any free bit in the bitmap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) static ext2_grpblk_t
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) find_next_usable_block(int start, struct buffer_head *bh, int maxblocks)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) ext2_grpblk_t here, next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) char *p, *r;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) if (start > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) * The goal was occupied; search forward for a free
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) * block within the next XX blocks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) * end_goal is more or less random, but it has to be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) * less than EXT2_BLOCKS_PER_GROUP. Aligning up to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) * next 64-bit boundary is simple..
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) ext2_grpblk_t end_goal = (start + 63) & ~63;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) if (end_goal > maxblocks)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) end_goal = maxblocks;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) here = ext2_find_next_zero_bit(bh->b_data, end_goal, start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) if (here < end_goal)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) return here;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) ext2_debug("Bit not found near goal\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) here = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) if (here < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) here = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) p = ((char *)bh->b_data) + (here >> 3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) next = (r - ((char *)bh->b_data)) << 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) if (next < maxblocks && next >= here)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) return next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) here = bitmap_search_next_usable_block(here, bh, maxblocks);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) return here;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) * ext2_try_to_allocate()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) * @sb: superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) * @group: given allocation block group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) * @bitmap_bh: bufferhead holds the block bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) * @grp_goal: given target block within the group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) * @count: target number of blocks to allocate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) * @my_rsv: reservation window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) * Attempt to allocate blocks within a give range. Set the range of allocation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) * first, then find the first free bit(s) from the bitmap (within the range),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) * and at last, allocate the blocks by claiming the found free bit as allocated.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) * To set the range of this allocation:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) * if there is a reservation window, only try to allocate block(s)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) * from the file's own reservation window;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) * Otherwise, the allocation range starts from the give goal block,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) * ends at the block group's last block.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) * If we failed to allocate the desired block then we may end up crossing to a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) * new bitmap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) static int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) ext2_try_to_allocate(struct super_block *sb, int group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) unsigned long *count,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) struct ext2_reserve_window *my_rsv)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) ext2_fsblk_t group_first_block = ext2_group_first_block_no(sb, group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) ext2_fsblk_t group_last_block = ext2_group_last_block_no(sb, group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) ext2_grpblk_t start, end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) unsigned long num = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) start = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) end = group_last_block - group_first_block + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) /* we do allocation within the reservation window if we have a window */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) if (my_rsv) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) if (my_rsv->_rsv_start >= group_first_block)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) start = my_rsv->_rsv_start - group_first_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) if (my_rsv->_rsv_end < group_last_block)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) end = my_rsv->_rsv_end - group_first_block + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) if (grp_goal < start || grp_goal >= end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) grp_goal = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) BUG_ON(start > EXT2_BLOCKS_PER_GROUP(sb));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) if (grp_goal < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) grp_goal = find_next_usable_block(start, bitmap_bh, end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) if (grp_goal < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) goto fail_access;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) if (!my_rsv) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) for (i = 0; i < 7 && grp_goal > start &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) !ext2_test_bit(grp_goal - 1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) bitmap_bh->b_data);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) i++, grp_goal--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) for (; num < *count && grp_goal < end; grp_goal++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) if (ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) grp_goal, bitmap_bh->b_data)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) if (num == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) num++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) if (num == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) goto fail_access;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) *count = num;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) return grp_goal - num;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) fail_access:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) * find_next_reservable_window():
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) * find a reservable space within the given range.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) * It does not allocate the reservation window for now:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) * alloc_new_reservation() will do the work later.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) * @search_head: the head of the searching list;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) * This is not necessarily the list head of the whole filesystem
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) * We have both head and start_block to assist the search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) * for the reservable space. The list starts from head,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) * but we will shift to the place where start_block is,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) * then start from there, when looking for a reservable space.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) * @sb: the super block.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) * @start_block: the first block we consider to start the real search from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) * @last_block:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) * the maximum block number that our goal reservable space
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) * could start from. This is normally the last block in this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) * group. The search will end when we found the start of next
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) * possible reservable space is out of this boundary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) * This could handle the cross boundary reservation window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) * request.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) * basically we search from the given range, rather than the whole
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) * reservation double linked list, (start_block, last_block)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) * to find a free region that is of my size and has not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) * been reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) static int find_next_reservable_window(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) struct ext2_reserve_window_node *search_head,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) struct ext2_reserve_window_node *my_rsv,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) struct super_block * sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) ext2_fsblk_t start_block,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) ext2_fsblk_t last_block)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) struct rb_node *next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) struct ext2_reserve_window_node *rsv, *prev;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) ext2_fsblk_t cur;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) int size = my_rsv->rsv_goal_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763) /* TODO: make the start of the reservation window byte-aligned */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) /* cur = *start_block & ~7;*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) cur = start_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) rsv = search_head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) if (!rsv)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) if (cur <= rsv->rsv_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) cur = rsv->rsv_end + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) /* TODO?
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) * in the case we could not find a reservable space
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) * that is what is expected, during the re-search, we could
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) * remember what's the largest reservable space we could have
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) * and return that one.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) * For now it will fail if we could not find the reservable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) * space with expected-size (or more)...
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) if (cur > last_block)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) return -1; /* fail */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) prev = rsv;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787) next = rb_next(&rsv->rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) rsv = rb_entry(next,struct ext2_reserve_window_node,rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) * Reached the last reservation, we can just append to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) * previous one.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) if (!next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) if (cur + size <= rsv->rsv_start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) * Found a reserveable space big enough. We could
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) * have a reservation across the group boundary here
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806) * we come here either :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) * when we reach the end of the whole list,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808) * and there is empty reservable space after last entry in the list.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) * append it to the end of the list.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811) * or we found one reservable space in the middle of the list,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) * return the reservation window that we could append to.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813) * succeed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816) if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817) rsv_window_remove(sb, my_rsv);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820) * Let's book the whole available window for now. We will check the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821) * disk bitmap later and then, if there are free blocks then we adjust
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) * the window size if it's larger than requested.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823) * Otherwise, we will remove this node from the tree next time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824) * call find_next_reservable_window.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) my_rsv->rsv_start = cur;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827) my_rsv->rsv_end = cur + size - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828) my_rsv->rsv_alloc_hit = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 829)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 830) if (prev != my_rsv)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 831) ext2_rsv_window_add(sb, my_rsv);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 832)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 833) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 834) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 835)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 836) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 837) * alloc_new_reservation()--allocate a new reservation window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 838) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 839) * To make a new reservation, we search part of the filesystem
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 840) * reservation list (the list that inside the group). We try to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 841) * allocate a new reservation window near the allocation goal,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 842) * or the beginning of the group, if there is no goal.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 843) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 844) * We first find a reservable space after the goal, then from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 845) * there, we check the bitmap for the first free block after
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 846) * it. If there is no free block until the end of group, then the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 847) * whole group is full, we failed. Otherwise, check if the free
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 848) * block is inside the expected reservable space, if so, we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 849) * succeed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 850) * If the first free block is outside the reservable space, then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 851) * start from the first free block, we search for next available
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 852) * space, and go on.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 853) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 854) * on succeed, a new reservation will be found and inserted into the list
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 855) * It contains at least one free block, and it does not overlap with other
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 856) * reservation windows.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 857) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 858) * failed: we failed to find a reservation window in this group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 859) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 860) * @my_rsv: the reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 861) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 862) * @grp_goal: The goal (group-relative). It is where the search for a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 863) * free reservable space should start from.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 864) * if we have a goal(goal >0 ), then start from there,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 865) * no goal(goal = -1), we start from the first block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 866) * of the group.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 867) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 868) * @sb: the super block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 869) * @group: the group we are trying to allocate in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 870) * @bitmap_bh: the block group block bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 871) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 872) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 873) static int alloc_new_reservation(struct ext2_reserve_window_node *my_rsv,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 874) ext2_grpblk_t grp_goal, struct super_block *sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 875) unsigned int group, struct buffer_head *bitmap_bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 876) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 877) struct ext2_reserve_window_node *search_head;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 878) ext2_fsblk_t group_first_block, group_end_block, start_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 879) ext2_grpblk_t first_free_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 880) struct rb_root *fs_rsv_root = &EXT2_SB(sb)->s_rsv_window_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 881) unsigned long size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 882) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 883) spinlock_t *rsv_lock = &EXT2_SB(sb)->s_rsv_window_lock;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 884)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 885) group_first_block = ext2_group_first_block_no(sb, group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 886) group_end_block = ext2_group_last_block_no(sb, group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 887)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 888) if (grp_goal < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 889) start_block = group_first_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 890) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 891) start_block = grp_goal + group_first_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 892)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 893) size = my_rsv->rsv_goal_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 894)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 895) if (!rsv_is_empty(&my_rsv->rsv_window)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 896) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 897) * if the old reservation is cross group boundary
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 898) * and if the goal is inside the old reservation window,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 899) * we will come here when we just failed to allocate from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 900) * the first part of the window. We still have another part
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 901) * that belongs to the next group. In this case, there is no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 902) * point to discard our window and try to allocate a new one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 903) * in this group(which will fail). we should
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 904) * keep the reservation window, just simply move on.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 905) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 906) * Maybe we could shift the start block of the reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 907) * window to the first block of next group.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 908) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 909)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 910) if ((my_rsv->rsv_start <= group_end_block) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 911) (my_rsv->rsv_end > group_end_block) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 912) (start_block >= my_rsv->rsv_start))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 913) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 914)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 915) if ((my_rsv->rsv_alloc_hit >
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 916) (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 917) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 918) * if the previously allocation hit ratio is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 919) * greater than 1/2, then we double the size of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 920) * the reservation window the next time,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 921) * otherwise we keep the same size window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 922) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 923) size = size * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 924) if (size > EXT2_MAX_RESERVE_BLOCKS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 925) size = EXT2_MAX_RESERVE_BLOCKS;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 926) my_rsv->rsv_goal_size= size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 927) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 928) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 929)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 930) spin_lock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 931) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 932) * shift the search start to the window near the goal block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 933) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 934) search_head = search_reserve_window(fs_rsv_root, start_block);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 935)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 936) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 937) * find_next_reservable_window() simply finds a reservable window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 938) * inside the given range(start_block, group_end_block).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 939) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 940) * To make sure the reservation window has a free bit inside it, we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 941) * need to check the bitmap after we found a reservable window.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 942) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 943) retry:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 944) ret = find_next_reservable_window(search_head, my_rsv, sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 945) start_block, group_end_block);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 946)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 947) if (ret == -1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 948) if (!rsv_is_empty(&my_rsv->rsv_window))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 949) rsv_window_remove(sb, my_rsv);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 950) spin_unlock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 951) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 952) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 953)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 954) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 955) * On success, find_next_reservable_window() returns the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 956) * reservation window where there is a reservable space after it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 957) * Before we reserve this reservable space, we need
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 958) * to make sure there is at least a free block inside this region.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 959) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 960) * Search the first free bit on the block bitmap. Search starts from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 961) * the start block of the reservable space we just found.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 962) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 963) spin_unlock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 964) first_free_block = bitmap_search_next_usable_block(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 965) my_rsv->rsv_start - group_first_block,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 966) bitmap_bh, group_end_block - group_first_block + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 967)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 968) if (first_free_block < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 969) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 970) * no free block left on the bitmap, no point
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 971) * to reserve the space. return failed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 972) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 973) spin_lock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 974) if (!rsv_is_empty(&my_rsv->rsv_window))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 975) rsv_window_remove(sb, my_rsv);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 976) spin_unlock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 977) return -1; /* failed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 978) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 979)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 980) start_block = first_free_block + group_first_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 981) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 982) * check if the first free block is within the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 983) * free space we just reserved
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 984) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 985) if (start_block >= my_rsv->rsv_start && start_block <= my_rsv->rsv_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 986) return 0; /* success */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 987) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 988) * if the first free bit we found is out of the reservable space
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 989) * continue search for next reservable space,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 990) * start from where the free block is,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 991) * we also shift the list head to where we stopped last time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 992) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 993) search_head = my_rsv;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 994) spin_lock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 995) goto retry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 996) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 997)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 998) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 999) * try_to_extend_reservation()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1000) * @my_rsv: given reservation window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1001) * @sb: super block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1002) * @size: the delta to extend
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1003) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1004) * Attempt to expand the reservation window large enough to have
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1005) * required number of free blocks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1006) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1007) * Since ext2_try_to_allocate() will always allocate blocks within
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1008) * the reservation window range, if the window size is too small,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1009) * multiple blocks allocation has to stop at the end of the reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1010) * window. To make this more efficient, given the total number of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1011) * blocks needed and the current size of the window, we try to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1012) * expand the reservation window size if necessary on a best-effort
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1013) * basis before ext2_new_blocks() tries to allocate blocks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1014) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1015) static void try_to_extend_reservation(struct ext2_reserve_window_node *my_rsv,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1016) struct super_block *sb, int size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1017) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1018) struct ext2_reserve_window_node *next_rsv;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1019) struct rb_node *next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1020) spinlock_t *rsv_lock = &EXT2_SB(sb)->s_rsv_window_lock;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1021)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1022) if (!spin_trylock(rsv_lock))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1023) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1024)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1025) next = rb_next(&my_rsv->rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1026)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1027) if (!next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1028) my_rsv->rsv_end += size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1029) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1030) next_rsv = rb_entry(next, struct ext2_reserve_window_node, rsv_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1031)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1032) if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1033) my_rsv->rsv_end += size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1034) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1035) my_rsv->rsv_end = next_rsv->rsv_start - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1036) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1037) spin_unlock(rsv_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1038) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1039)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1040) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1041) * ext2_try_to_allocate_with_rsv()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1042) * @sb: superblock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1043) * @group: given allocation block group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1044) * @bitmap_bh: bufferhead holds the block bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1045) * @grp_goal: given target block within the group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1046) * @count: target number of blocks to allocate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1047) * @my_rsv: reservation window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1048) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1049) * This is the main function used to allocate a new block and its reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1050) * window.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1051) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1052) * Each time when a new block allocation is need, first try to allocate from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1053) * its own reservation. If it does not have a reservation window, instead of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1054) * looking for a free bit on bitmap first, then look up the reservation list to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1055) * see if it is inside somebody else's reservation window, we try to allocate a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1056) * reservation window for it starting from the goal first. Then do the block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1057) * allocation within the reservation window.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1058) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1059) * This will avoid keeping on searching the reservation list again and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1060) * again when somebody is looking for a free block (without
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1061) * reservation), and there are lots of free blocks, but they are all
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1062) * being reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1063) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1064) * We use a red-black tree for the per-filesystem reservation list.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1065) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1066) static ext2_grpblk_t
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1067) ext2_try_to_allocate_with_rsv(struct super_block *sb, unsigned int group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1068) struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1069) struct ext2_reserve_window_node * my_rsv,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1070) unsigned long *count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1071) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1072) ext2_fsblk_t group_first_block, group_last_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1073) ext2_grpblk_t ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1074) unsigned long num = *count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1075)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1076) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1077) * we don't deal with reservation when
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1078) * filesystem is mounted without reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1079) * or the file is not a regular file
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1080) * or last attempt to allocate a block with reservation turned on failed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1081) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1082) if (my_rsv == NULL) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1083) return ext2_try_to_allocate(sb, group, bitmap_bh,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1084) grp_goal, count, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1085) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1086) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1087) * grp_goal is a group relative block number (if there is a goal)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1088) * 0 <= grp_goal < EXT2_BLOCKS_PER_GROUP(sb)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1089) * first block is a filesystem wide block number
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1090) * first block is the block number of the first block in this group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1091) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1092) group_first_block = ext2_group_first_block_no(sb, group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1093) group_last_block = ext2_group_last_block_no(sb, group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1094)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1095) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1096) * Basically we will allocate a new block from inode's reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1097) * window.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1098) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1099) * We need to allocate a new reservation window, if:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1100) * a) inode does not have a reservation window; or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1101) * b) last attempt to allocate a block from existing reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1102) * failed; or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1103) * c) we come here with a goal and with a reservation window
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1104) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1105) * We do not need to allocate a new reservation window if we come here
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1106) * at the beginning with a goal and the goal is inside the window, or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1107) * we don't have a goal but already have a reservation window.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1108) * then we could go to allocate from the reservation window directly.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1109) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1110) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1111) if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1112) !goal_in_my_reservation(&my_rsv->rsv_window,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1113) grp_goal, group, sb)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1114) if (my_rsv->rsv_goal_size < *count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1115) my_rsv->rsv_goal_size = *count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1116) ret = alloc_new_reservation(my_rsv, grp_goal, sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1117) group, bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1118) if (ret < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1119) break; /* failed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1121) if (!goal_in_my_reservation(&my_rsv->rsv_window,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1122) grp_goal, group, sb))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1123) grp_goal = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1124) } else if (grp_goal >= 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1125) int curr = my_rsv->rsv_end -
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1126) (grp_goal + group_first_block) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1128) if (curr < *count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1129) try_to_extend_reservation(my_rsv, sb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1130) *count - curr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1131) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1132)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1133) if ((my_rsv->rsv_start > group_last_block) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1134) (my_rsv->rsv_end < group_first_block)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1135) rsv_window_dump(&EXT2_SB(sb)->s_rsv_window_root, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1136) BUG();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1137) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1138) ret = ext2_try_to_allocate(sb, group, bitmap_bh, grp_goal,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1139) &num, &my_rsv->rsv_window);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1140) if (ret >= 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1141) my_rsv->rsv_alloc_hit += num;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1142) *count = num;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1143) break; /* succeed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1144) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1145) num = *count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1146) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1147) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1148) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1149)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1150) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1151) * ext2_has_free_blocks()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1152) * @sbi: in-core super block structure.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1153) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1154) * Check if filesystem has at least 1 free block available for allocation.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1155) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1156) static int ext2_has_free_blocks(struct ext2_sb_info *sbi)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1157) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1158) ext2_fsblk_t free_blocks, root_blocks;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1159)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1160) free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1161) root_blocks = le32_to_cpu(sbi->s_es->s_r_blocks_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1162) if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1163) !uid_eq(sbi->s_resuid, current_fsuid()) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1164) (gid_eq(sbi->s_resgid, GLOBAL_ROOT_GID) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1165) !in_group_p (sbi->s_resgid))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1166) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1167) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1168) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1169) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1171) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1172) * Returns 1 if the passed-in block region is valid; 0 if some part overlaps
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1173) * with filesystem metadata blocks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1174) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1175) int ext2_data_block_valid(struct ext2_sb_info *sbi, ext2_fsblk_t start_blk,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1176) unsigned int count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1177) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1178) if ((start_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1179) (start_blk + count - 1 < start_blk) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1180) (start_blk + count - 1 >= le32_to_cpu(sbi->s_es->s_blocks_count)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1181) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1182)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1183) /* Ensure we do not step over superblock */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1184) if ((start_blk <= sbi->s_sb_block) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1185) (start_blk + count - 1 >= sbi->s_sb_block))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1186) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1187)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1188) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1189) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1190)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1191) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1192) * ext2_new_blocks() -- core block(s) allocation function
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1193) * @inode: file inode
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1194) * @goal: given target block(filesystem wide)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1195) * @count: target number of blocks to allocate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1196) * @errp: error code
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1197) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1198) * ext2_new_blocks uses a goal block to assist allocation. If the goal is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1199) * free, or there is a free block within 32 blocks of the goal, that block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1200) * is allocated. Otherwise a forward search is made for a free block; within
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1201) * each block group the search first looks for an entire free byte in the block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1202) * bitmap, and then for any free bit if that fails.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1203) * This function also updates quota and i_blocks field.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1204) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1205) ext2_fsblk_t ext2_new_blocks(struct inode *inode, ext2_fsblk_t goal,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1206) unsigned long *count, int *errp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1207) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1208) struct buffer_head *bitmap_bh = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1209) struct buffer_head *gdp_bh;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1210) int group_no;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1211) int goal_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1212) ext2_grpblk_t grp_target_blk; /* blockgroup relative goal block */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1213) ext2_grpblk_t grp_alloc_blk; /* blockgroup-relative allocated block*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1214) ext2_fsblk_t ret_block; /* filesyetem-wide allocated block */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1215) int bgi; /* blockgroup iteration index */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1216) int performed_allocation = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1217) ext2_grpblk_t free_blocks; /* number of free blocks in a group */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1218) struct super_block *sb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1219) struct ext2_group_desc *gdp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1220) struct ext2_super_block *es;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1221) struct ext2_sb_info *sbi;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1222) struct ext2_reserve_window_node *my_rsv = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1223) struct ext2_block_alloc_info *block_i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1224) unsigned short windowsz = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1225) unsigned long ngroups;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1226) unsigned long num = *count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1227) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1228)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1229) *errp = -ENOSPC;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1230) sb = inode->i_sb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1231)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1232) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1233) * Check quota for allocation of this block.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1234) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1235) ret = dquot_alloc_block(inode, num);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1236) if (ret) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1237) *errp = ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1238) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1239) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1240)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1241) sbi = EXT2_SB(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1242) es = EXT2_SB(sb)->s_es;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1243) ext2_debug("goal=%lu.\n", goal);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1244) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1245) * Allocate a block from reservation only when
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1246) * filesystem is mounted with reservation(default,-o reservation), and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1247) * it's a regular file, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1248) * the desired window size is greater than 0 (One could use ioctl
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1249) * command EXT2_IOC_SETRSVSZ to set the window size to 0 to turn off
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1250) * reservation on that particular file)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1251) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1252) block_i = EXT2_I(inode)->i_block_alloc_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1253) if (block_i) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1254) windowsz = block_i->rsv_window_node.rsv_goal_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1255) if (windowsz > 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1256) my_rsv = &block_i->rsv_window_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1257) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1258)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1259) if (!ext2_has_free_blocks(sbi)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1260) *errp = -ENOSPC;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1261) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1262) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1263)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1264) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1265) * First, test whether the goal block is free.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1266) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1267) if (goal < le32_to_cpu(es->s_first_data_block) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1268) goal >= le32_to_cpu(es->s_blocks_count))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1269) goal = le32_to_cpu(es->s_first_data_block);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1270) group_no = (goal - le32_to_cpu(es->s_first_data_block)) /
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1271) EXT2_BLOCKS_PER_GROUP(sb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1272) goal_group = group_no;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1273) retry_alloc:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1274) gdp = ext2_get_group_desc(sb, group_no, &gdp_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1275) if (!gdp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1276) goto io_error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1277)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1278) free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1279) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1280) * if there is not enough free blocks to make a new resevation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1281) * turn off reservation for this allocation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1282) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1283) if (my_rsv && (free_blocks < windowsz)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1284) && (free_blocks > 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1285) && (rsv_is_empty(&my_rsv->rsv_window)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1286) my_rsv = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1287)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1288) if (free_blocks > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1289) grp_target_blk = ((goal - le32_to_cpu(es->s_first_data_block)) %
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1290) EXT2_BLOCKS_PER_GROUP(sb));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1291) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1292) * In case we retry allocation (due to fs reservation not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1293) * working out or fs corruption), the bitmap_bh is non-null
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1294) * pointer and we have to release it before calling
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1295) * read_block_bitmap().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1296) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1297) brelse(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1298) bitmap_bh = read_block_bitmap(sb, group_no);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1299) if (!bitmap_bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1300) goto io_error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1301) grp_alloc_blk = ext2_try_to_allocate_with_rsv(sb, group_no,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1302) bitmap_bh, grp_target_blk,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1303) my_rsv, &num);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1304) if (grp_alloc_blk >= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1305) goto allocated;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1306) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1307)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1308) ngroups = EXT2_SB(sb)->s_groups_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1309) smp_rmb();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1310)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1311) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1312) * Now search the rest of the groups. We assume that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1313) * group_no and gdp correctly point to the last group visited.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1314) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1315) for (bgi = 0; bgi < ngroups; bgi++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1316) group_no++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1317) if (group_no >= ngroups)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1318) group_no = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1319) gdp = ext2_get_group_desc(sb, group_no, &gdp_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1320) if (!gdp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1321) goto io_error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1322)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1323) free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1324) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1325) * skip this group (and avoid loading bitmap) if there
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1326) * are no free blocks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1327) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1328) if (!free_blocks)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1329) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1330) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1331) * skip this group if the number of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1332) * free blocks is less than half of the reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1333) * window size.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1334) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1335) if (my_rsv && (free_blocks <= (windowsz/2)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1336) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1337)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1338) brelse(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1339) bitmap_bh = read_block_bitmap(sb, group_no);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1340) if (!bitmap_bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1341) goto io_error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1342) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1343) * try to allocate block(s) from this group, without a goal(-1).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1344) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1345) grp_alloc_blk = ext2_try_to_allocate_with_rsv(sb, group_no,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1346) bitmap_bh, -1, my_rsv, &num);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1347) if (grp_alloc_blk >= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1348) goto allocated;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1349) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1350) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1351) * We may end up a bogus earlier ENOSPC error due to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1352) * filesystem is "full" of reservations, but
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1353) * there maybe indeed free blocks available on disk
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1354) * In this case, we just forget about the reservations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1355) * just do block allocation as without reservations.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1356) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1357) if (my_rsv) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1358) my_rsv = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1359) windowsz = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1360) group_no = goal_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1361) goto retry_alloc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1362) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1363) /* No space left on the device */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1364) *errp = -ENOSPC;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1365) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1366)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1367) allocated:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1368)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1369) ext2_debug("using block group %d(%d)\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1370) group_no, gdp->bg_free_blocks_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1371)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1372) ret_block = grp_alloc_blk + ext2_group_first_block_no(sb, group_no);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1373)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1374) if (in_range(le32_to_cpu(gdp->bg_block_bitmap), ret_block, num) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1375) in_range(le32_to_cpu(gdp->bg_inode_bitmap), ret_block, num) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1376) in_range(ret_block, le32_to_cpu(gdp->bg_inode_table),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1377) EXT2_SB(sb)->s_itb_per_group) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1378) in_range(ret_block + num - 1, le32_to_cpu(gdp->bg_inode_table),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1379) EXT2_SB(sb)->s_itb_per_group)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1380) ext2_error(sb, "ext2_new_blocks",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1381) "Allocating block in system zone - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1382) "blocks from "E2FSBLK", length %lu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1383) ret_block, num);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1384) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1385) * ext2_try_to_allocate marked the blocks we allocated as in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1386) * use. So we may want to selectively mark some of the blocks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1387) * as free
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1388) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1389) num = *count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1390) goto retry_alloc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1391) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1393) performed_allocation = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1394)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1395) if (ret_block + num - 1 >= le32_to_cpu(es->s_blocks_count)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1396) ext2_error(sb, "ext2_new_blocks",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1397) "block("E2FSBLK") >= blocks count(%d) - "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1398) "block_group = %d, es == %p ", ret_block,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1399) le32_to_cpu(es->s_blocks_count), group_no, es);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1400) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1401) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1402)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1403) group_adjust_blocks(sb, group_no, gdp, gdp_bh, -num);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1404) percpu_counter_sub(&sbi->s_freeblocks_counter, num);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1405)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1406) mark_buffer_dirty(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1407) if (sb->s_flags & SB_SYNCHRONOUS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1408) sync_dirty_buffer(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1409)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1410) *errp = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1411) brelse(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1412) if (num < *count) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1413) dquot_free_block_nodirty(inode, *count-num);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1414) mark_inode_dirty(inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1415) *count = num;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1416) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1417) return ret_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1418)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1419) io_error:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1420) *errp = -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1421) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1422) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1423) * Undo the block allocation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1424) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1425) if (!performed_allocation) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1426) dquot_free_block_nodirty(inode, *count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1427) mark_inode_dirty(inode);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1428) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1429) brelse(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1430) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1431) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1432)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1433) ext2_fsblk_t ext2_new_block(struct inode *inode, unsigned long goal, int *errp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1434) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1435) unsigned long count = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1436)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1437) return ext2_new_blocks(inode, goal, &count, errp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1438) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1439)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1440) #ifdef EXT2FS_DEBUG
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1441)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1442) unsigned long ext2_count_free(struct buffer_head *map, unsigned int numchars)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1443) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1444) return numchars * BITS_PER_BYTE - memweight(map->b_data, numchars);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1445) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1446)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1447) #endif /* EXT2FS_DEBUG */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1448)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1449) unsigned long ext2_count_free_blocks (struct super_block * sb)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1450) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1451) struct ext2_group_desc * desc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1452) unsigned long desc_count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1453) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1454) #ifdef EXT2FS_DEBUG
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1455) unsigned long bitmap_count, x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1456) struct ext2_super_block *es;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1457)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1458) es = EXT2_SB(sb)->s_es;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1459) desc_count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1460) bitmap_count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1461) desc = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1462) for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1463) struct buffer_head *bitmap_bh;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1464) desc = ext2_get_group_desc (sb, i, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1465) if (!desc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1466) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1467) desc_count += le16_to_cpu(desc->bg_free_blocks_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1468) bitmap_bh = read_block_bitmap(sb, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1469) if (!bitmap_bh)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1470) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1471)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1472) x = ext2_count_free(bitmap_bh, sb->s_blocksize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1473) printk ("group %d: stored = %d, counted = %lu\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1474) i, le16_to_cpu(desc->bg_free_blocks_count), x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1475) bitmap_count += x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1476) brelse(bitmap_bh);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1477) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1478) printk("ext2_count_free_blocks: stored = %lu, computed = %lu, %lu\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1479) (long)le32_to_cpu(es->s_free_blocks_count),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1480) desc_count, bitmap_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1481) return bitmap_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1482) #else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1483) for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1484) desc = ext2_get_group_desc (sb, i, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1485) if (!desc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1486) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1487) desc_count += le16_to_cpu(desc->bg_free_blocks_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1488) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1489) return desc_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1490) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1491) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1492)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1493) static inline int test_root(int a, int b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1494) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1495) int num = b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1496)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1497) while (a > num)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1498) num *= b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1499) return num == a;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1500) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1501)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1502) static int ext2_group_sparse(int group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1503) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1504) if (group <= 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1505) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1506) return (test_root(group, 3) || test_root(group, 5) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1507) test_root(group, 7));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1508) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1509)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1510) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1511) * ext2_bg_has_super - number of blocks used by the superblock in group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1512) * @sb: superblock for filesystem
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1513) * @group: group number to check
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1514) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1515) * Return the number of blocks used by the superblock (primary or backup)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1516) * in this group. Currently this will be only 0 or 1.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1517) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1518) int ext2_bg_has_super(struct super_block *sb, int group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1519) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1520) if (EXT2_HAS_RO_COMPAT_FEATURE(sb,EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER)&&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1521) !ext2_group_sparse(group))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1522) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1523) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1524) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1525)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1526) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1527) * ext2_bg_num_gdb - number of blocks used by the group table in group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1528) * @sb: superblock for filesystem
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1529) * @group: group number to check
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1530) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1531) * Return the number of blocks used by the group descriptor table
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1532) * (primary or backup) in this group. In the future there may be a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1533) * different number of descriptor blocks in each group.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1534) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1535) unsigned long ext2_bg_num_gdb(struct super_block *sb, int group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1536) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1537) return ext2_bg_has_super(sb, group) ? EXT2_SB(sb)->s_gdb_count : 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1538) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1539)
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags