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