1 // SPDX-License-Identifier: GPL-2.0
7  * Laboratoire MASI - Institut Blaise Pascal
10  *  Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
11  *  Big-endian to little-endian byte-swapping/bitmaps by
34  * Calculate block group number for a given block number
37 				   ext4_fsblk_t block)  in ext4_get_group_number()  argument
42 		group = (block -  in ext4_get_group_number()
43 			 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block)) >>  in ext4_get_group_number()
46 		ext4_get_group_no_and_offset(sb, block, &group, NULL);  in ext4_get_group_number()
51  * Calculate the block group number and offset into the block/cluster
52  * allocation bitmap, given a block number
57 	struct ext4_super_block *es = EXT4_SB(sb)->s_es;  in ext4_get_group_no_and_offset()
58 	ext4_grpblk_t offset;  in ext4_get_group_no_and_offset()  local
60 	blocknr = blocknr - le32_to_cpu(es->s_first_data_block);  in ext4_get_group_no_and_offset()
61 	offset = do_div(blocknr, EXT4_BLOCKS_PER_GROUP(sb)) >>  in ext4_get_group_no_and_offset()
62 		EXT4_SB(sb)->s_cluster_bits;  in ext4_get_group_no_and_offset()
64 		*offsetp = offset;  in ext4_get_group_no_and_offset()
71  * Check whether the 'block' lives within the 'block_group'. Returns 1 if so
75 				      ext4_fsblk_t block,  in ext4_block_in_group()  argument
80 	actual_group = ext4_get_group_number(sb, block);  in ext4_block_in_group()
93 	int block_cluster = -1, inode_cluster;  in ext4_num_overhead_clusters()
94 	int itbl_cluster_start = -1, itbl_cluster_end = -1;  in ext4_num_overhead_clusters()
96 	ext4_fsblk_t end = start + EXT4_BLOCKS_PER_GROUP(sb) - 1;  in ext4_num_overhead_clusters()
101 	 * block group descriptors, and reserved block group  in ext4_num_overhead_clusters()
108 	 * is in the block group, or inode table cluster range is  in ext4_num_overhead_clusters()
109 	 * [-1, -1] and won't overlap with block/inode bitmap cluster  in ext4_num_overhead_clusters()
113 	itbl_blk_end = itbl_blk_start + sbi->s_itb_per_group - 1;  in ext4_num_overhead_clusters()
118 		itbl_cluster_start = EXT4_B2C(sbi, itbl_blk_start - start);  in ext4_num_overhead_clusters()
119 		itbl_cluster_end = EXT4_B2C(sbi, itbl_blk_end - start);  in ext4_num_overhead_clusters()
121 		num_clusters += itbl_cluster_end - itbl_cluster_start + 1;  in ext4_num_overhead_clusters()
123 		if (itbl_cluster_start == base_clusters - 1)  in ext4_num_overhead_clusters()
124 			num_clusters--;  in ext4_num_overhead_clusters()
129 	 * if the block is in the block group.  If it is, then check  in ext4_num_overhead_clusters()
138 					 ext4_block_bitmap(sb, gdp) - start);  in ext4_num_overhead_clusters()
147 					 ext4_inode_bitmap(sb, gdp) - start);  in ext4_num_overhead_clusters()
167 	if (block_group == ext4_get_groups_count(sb) - 1) {  in num_clusters_in_group()
174 		blocks = ext4_blocks_count(EXT4_SB(sb)->s_es) -  in num_clusters_in_group()
181 /* Initializes an uninitialized block bitmap */
197 		return -EFSBADCRC;  in ext4_init_block_bitmap()
199 	memset(bh->b_data, 0, sb->s_blocksize);  in ext4_init_block_bitmap()
202 	if ((bit_max >> 3) >= bh->b_size)  in ext4_init_block_bitmap()
203 		return -EFSCORRUPTED;  in ext4_init_block_bitmap()
206 		ext4_set_bit(bit, bh->b_data);  in ext4_init_block_bitmap()
210 	/* Set bits for block and inode bitmaps, and inode table */  in ext4_init_block_bitmap()
213 		ext4_set_bit(EXT4_B2C(sbi, tmp - start), bh->b_data);  in ext4_init_block_bitmap()
217 		ext4_set_bit(EXT4_B2C(sbi, tmp - start), bh->b_data);  in ext4_init_block_bitmap()
221 		     sbi->s_itb_per_group; tmp++) {  in ext4_init_block_bitmap()
223 			ext4_set_bit(EXT4_B2C(sbi, tmp - start), bh->b_data);  in ext4_init_block_bitmap()
229 	 * of the block bitmap to 1  in ext4_init_block_bitmap()
232 			     sb->s_blocksize * 8, bh->b_data);  in ext4_init_block_bitmap()
236 /* Return the number of free blocks in a block group.  It is used when
237  * the block bitmap is uninitialized, so we can't just count the bits
243 	return num_clusters_in_group(sb, block_group) -  in ext4_free_clusters_after_init()
249  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
250  * block for inodes, N blocks for the inode table and data blocks.
253  * super block.  Each descriptor contains the number of the bitmap block and
254  * the free blocks count in the block.  The descriptors are loaded in memory
259  * ext4_get_group_desc() -- load group descriptor from disk
260  * @sb:			super block
261  * @block_group:	given block group
262  * @bh:			pointer to the buffer head to store the block
270 	unsigned int offset;  in ext4_get_group_desc()  local
280 		ext4_error(sb, "block_group >= groups_count - block_group = %u,"  in ext4_get_group_desc()
287 	offset = block_group & (EXT4_DESC_PER_BLOCK(sb) - 1);  in ext4_get_group_desc()
296 		ext4_error(sb, "Group descriptor not loaded - "  in ext4_get_group_desc()
298 			   block_group, group_desc, offset);  in ext4_get_group_desc()
303 		(__u8 *)bh_p->b_data +  in ext4_get_group_desc()
304 		offset * EXT4_DESC_SIZE(sb));  in ext4_get_group_desc()
315 	unsigned long bitmap_size = sb->s_blocksize * 8;  in ext4_valid_block_bitmap_padding()
316 	unsigned int offset = num_clusters_in_group(sb, block_group);  in ext4_valid_block_bitmap_padding()  local
318 	if (bitmap_size <= offset)  in ext4_valid_block_bitmap_padding()
321 	next_zero_bit = ext4_find_next_zero_bit(bh->b_data, bitmap_size, offset);  in ext4_valid_block_bitmap_padding()
332 	if (unlikely(group >= EXT4_SB(sb)->s_groups_count))  in ext4_get_group_info()
335 	indexh = group & ((EXT4_DESC_PER_BLOCK(sb)) - 1);  in ext4_get_group_info()
341  * Return the block number which was discovered to be invalid, or 0 if
342  * the block bitmap is valid.
350 	ext4_grpblk_t offset;  in ext4_valid_block_bitmap()  local
357 		/* with FLEX_BG, the inode/block bitmaps and itable  in ext4_valid_block_bitmap()
360 		 * or it has to also read the block group where the bitmaps  in ext4_valid_block_bitmap()
367 	/* check whether block bitmap block number is set */  in ext4_valid_block_bitmap()
369 	offset = blk - group_first_block;  in ext4_valid_block_bitmap()
370 	if (offset < 0 || EXT4_B2C(sbi, offset) >= max_bit ||  in ext4_valid_block_bitmap()
371 	    !ext4_test_bit(EXT4_B2C(sbi, offset), bh->b_data))  in ext4_valid_block_bitmap()
372 		/* bad block bitmap */  in ext4_valid_block_bitmap()
375 	/* check whether the inode bitmap block number is set */  in ext4_valid_block_bitmap()
377 	offset = blk - group_first_block;  in ext4_valid_block_bitmap()
378 	if (offset < 0 || EXT4_B2C(sbi, offset) >= max_bit ||  in ext4_valid_block_bitmap()
379 	    !ext4_test_bit(EXT4_B2C(sbi, offset), bh->b_data))  in ext4_valid_block_bitmap()
380 		/* bad block bitmap */  in ext4_valid_block_bitmap()
383 	/* check whether the inode table block number is set */  in ext4_valid_block_bitmap()
385 	offset = blk - group_first_block;  in ext4_valid_block_bitmap()
386 	if (offset < 0 || EXT4_B2C(sbi, offset) >= max_bit ||  in ext4_valid_block_bitmap()
387 	    EXT4_B2C(sbi, offset + sbi->s_itb_per_group - 1) >= max_bit)  in ext4_valid_block_bitmap()
389 	next_zero_bit = ext4_find_next_zero_bit(bh->b_data,  in ext4_valid_block_bitmap()
390 			EXT4_B2C(sbi, offset + sbi->s_itb_per_group - 1) + 1,  in ext4_valid_block_bitmap()
391 			EXT4_B2C(sbi, offset));  in ext4_valid_block_bitmap()
393 	    EXT4_B2C(sbi, offset + sbi->s_itb_per_group - 1) + 1)  in ext4_valid_block_bitmap()
407 	if (EXT4_SB(sb)->s_mount_state & EXT4_FC_REPLAY)  in ext4_validate_block_bitmap()
415 		return -EFSCORRUPTED;  in ext4_validate_block_bitmap()
423 		ext4_error(sb, "bg %u: bad block bitmap checksum", block_group);  in ext4_validate_block_bitmap()
426 		return -EFSBADCRC;  in ext4_validate_block_bitmap()
431 		ext4_error(sb, "bg %u: block %llu: invalid block bitmap",  in ext4_validate_block_bitmap()
435 		return -EFSCORRUPTED;  in ext4_validate_block_bitmap()
440 		ext4_error(sb, "bg %u: block %llu: padding at end of block bitmap is not set",  in ext4_validate_block_bitmap()
444 		return -EFSCORRUPTED;  in ext4_validate_block_bitmap()
454  * @sb:			super block
455  * @block_group:	given block group
459  * bits for block/inode/inode tables are set in the bitmaps
478 		return ERR_PTR(-EFSCORRUPTED);  in ext4_read_block_bitmap_nowait()
480 	if ((bitmap_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) ||  in ext4_read_block_bitmap_nowait()
481 	    (bitmap_blk >= ext4_blocks_count(sbi->s_es))) {  in ext4_read_block_bitmap_nowait()
482 		ext4_error(sb, "Invalid block bitmap block %llu in "  in ext4_read_block_bitmap_nowait()
486 		return ERR_PTR(-EFSCORRUPTED);  in ext4_read_block_bitmap_nowait()
490 		ext4_warning(sb, "Cannot get buffer for block bitmap - "  in ext4_read_block_bitmap_nowait()
493 		return ERR_PTR(-ENOMEM);  in ext4_read_block_bitmap_nowait()
512 	    (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {  in ext4_read_block_bitmap_nowait()
516 			ext4_error(sb, "Block bitmap for bg 0 marked "  in ext4_read_block_bitmap_nowait()
518 			err = -EFSCORRUPTED;  in ext4_read_block_bitmap_nowait()
525 			ext4_error(sb, "Failed to init block bitmap for group "  in ext4_read_block_bitmap_nowait()
566 /* Returns 0 on success, -errno on error */
579 		return -EFSCORRUPTED;  in ext4_wait_block_bitmap()
582 		ext4_error_err(sb, EIO, "Cannot read block bitmap - "  in ext4_wait_block_bitmap()
584 			       block_group, (unsigned long long) bh->b_blocknr);  in ext4_wait_block_bitmap()
587 		return -EIO;  in ext4_wait_block_bitmap()
590 	/* Panic or remount fs read-only if block bitmap is invalid */  in ext4_wait_block_bitmap()
613  * @sbi:	in-core super block structure.
624 	struct percpu_counter *fcc = &sbi->s_freeclusters_counter;  in ext4_has_free_clusters()
625 	struct percpu_counter *dcc = &sbi->s_dirtyclusters_counter;  in ext4_has_free_clusters()
629 	resv_clusters = atomic64_read(&sbi->s_resv_clusters);  in ext4_has_free_clusters()
635 	rsv = (ext4_r_blocks_count(sbi->s_es) >> sbi->s_cluster_bits) +  in ext4_has_free_clusters()
638 	if (free_clusters - (nclusters + rsv + dirty_clusters) <  in ext4_has_free_clusters()
650 	if (uid_eq(sbi->s_resuid, current_fsuid()) ||  in ext4_has_free_clusters()
651 	    (!gid_eq(sbi->s_resgid, GLOBAL_ROOT_GID) && in_group_p(sbi->s_resgid)) ||  in ext4_has_free_clusters()
672 		percpu_counter_add(&sbi->s_dirtyclusters_counter, nclusters);  in ext4_claim_free_clusters()
675 		return -ENOSPC;  in ext4_claim_free_clusters()
679  * ext4_should_retry_alloc() - check if a block allocation should be retried
693 	if (!sbi->s_journal)  in ext4_should_retry_alloc()
697 		percpu_counter_inc(&sbi->s_sra_exceeded_retry_limit);  in ext4_should_retry_alloc()
706 	if (sbi->s_mb_free_pending == 0) {  in ext4_should_retry_alloc()
708 			atomic_inc(&sbi->s_retry_alloc_pending);  in ext4_should_retry_alloc()
709 			flush_work(&sbi->s_discard_work);  in ext4_should_retry_alloc()
710 			atomic_dec(&sbi->s_retry_alloc_pending);  in ext4_should_retry_alloc()
719 	ext4_debug("%s: retrying operation after ENOSPC\n", sb->s_id);  in ext4_should_retry_alloc()
720 	(void) jbd2_journal_force_commit_nested(sbi->s_journal);  in ext4_should_retry_alloc()
725  * ext4_new_meta_blocks() -- allocate block for meta data (indexing) blocks
729  * @goal:               given target block(filesystem wide)
733  * Return 1st allocated block number on success, *count stores total account
759 				EXT4_C2B(EXT4_SB(inode->i_sb), ar.len));  in ext4_new_meta_blocks()
765  * ext4_count_free_clusters() -- count filesystem free clusters
768  * Adds up the number of free clusters from each block group.
783 	es = EXT4_SB(sb)->s_es;  in ext4_count_free_clusters()
793 		if (EXT4_SB(sb)->s_group_info)  in ext4_count_free_clusters()
804 		x = ext4_count_free(bitmap_bh->b_data,  in ext4_count_free_clusters()
823 		if (EXT4_SB(sb)->s_group_info)  in ext4_count_free_clusters()
847  *	ext4_bg_has_super - number of blocks used by the superblock in group
856 	struct ext4_super_block *es = EXT4_SB(sb)->s_es;  in ext4_bg_has_super()
861 		if (group == le32_to_cpu(es->s_backup_bgs[0]) ||  in ext4_bg_has_super()
862 		    group == le32_to_cpu(es->s_backup_bgs[1]))  in ext4_bg_has_super()
882 	ext4_group_t last = first + EXT4_DESC_PER_BLOCK(sb) - 1;  in ext4_bg_num_gdb_meta()
896 		return le32_to_cpu(EXT4_SB(sb)->s_es->s_first_meta_bg);  in ext4_bg_num_gdb_nometa()
898 		return EXT4_SB(sb)->s_gdb_count;  in ext4_bg_num_gdb_nometa()
902  *	ext4_bg_num_gdb - number of blocks used by the group table in group
913 			le32_to_cpu(EXT4_SB(sb)->s_es->s_first_meta_bg);  in ext4_bg_num_gdb()
925  * the beginning of a block group, including the reserved gdt blocks.
937 	    block_group < le32_to_cpu(sbi->s_es->s_first_meta_bg) *  in ext4_num_base_meta_blocks()
938 			  sbi->s_desc_per_block) {  in ext4_num_base_meta_blocks()
941 			num += le16_to_cpu(sbi->s_es->s_reserved_gdt_blocks);  in ext4_num_base_meta_blocks()
956  *	ext4_inode_to_goal_block - return a hint for block allocation
957  *	@inode: inode for block allocation
967 	int flex_size = ext4_flex_bg_size(EXT4_SB(inode->i_sb));  in ext4_inode_to_goal_block()
971 	block_group = ei->i_block_group;  in ext4_inode_to_goal_block()
975 		 * block groups per flexgroup, reserve the first block  in ext4_inode_to_goal_block()
977 		 * files will start at the second block group.  This  in ext4_inode_to_goal_block()
981 		block_group &= ~(flex_size-1);  in ext4_inode_to_goal_block()
982 		if (S_ISREG(inode->i_mode))  in ext4_inode_to_goal_block()
985 	bg_start = ext4_group_first_block_no(inode->i_sb, block_group);  in ext4_inode_to_goal_block()
986 	last_block = ext4_blocks_count(EXT4_SB(inode->i_sb)->s_es) - 1;  in ext4_inode_to_goal_block()
992 	if (test_opt(inode->i_sb, DELALLOC))  in ext4_inode_to_goal_block()
995 	if (bg_start + EXT4_BLOCKS_PER_GROUP(inode->i_sb) <= last_block)  in ext4_inode_to_goal_block()
997 			(EXT4_BLOCKS_PER_GROUP(inode->i_sb) / 16);  in ext4_inode_to_goal_block()
1000 			((last_block - bg_start) / 16);  in ext4_inode_to_goal_block()