path: root/fs/ext4/balloc.c

// SPDX-License-Identifier: GPL-2.0
/*
 *  linux/fs/ext4/balloc.c
 *
 * Copyright (C) 1992, 1993, 1994, 1995
 * Remy Card (card@masi.ibp.fr)
 * Laboratoire MASI - Institut Blaise Pascal
 * Universite Pierre et Marie Curie (Paris VI)
 *
 *  Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
 *  Big-endian to little-endian byte-swapping/bitmaps by
 *        David S. Miller (davem@caip.rutgers.edu), 1995
 */

#include <linux/time.h>
#include <linux/capability.h>
#include <linux/fs.h>
#include <linux/quotaops.h>
#include <linux/buffer_head.h>
#include "ext4.h"
#include "ext4_jbd2.h"
#include "mballoc.h"

#include <trace/events/ext4.h>
#include <kunit/static_stub.h>

static unsigned ext4_num_base_meta_clusters(struct super_block *sb,
					    ext4_group_t block_group);
/*
 * balloc.c contains the blocks allocation and deallocation routines
 */

/*
 * Calculate block group number for a given block number
 */
ext4_group_t ext4_get_group_number(struct super_block *sb,
				   ext4_fsblk_t block)
{
	ext4_group_t group;

	if (test_opt2(sb, STD_GROUP_SIZE))
		group = (block -
			 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block)) >>
			(EXT4_BLOCK_SIZE_BITS(sb) + EXT4_CLUSTER_BITS(sb) + 3);
	else
		ext4_get_group_no_and_offset(sb, block, &group, NULL);
	return group;
}

/*
 * Calculate the block group number and offset into the block/cluster
 * allocation bitmap, given a block number
 */
void ext4_get_group_no_and_offset(struct super_block *sb, ext4_fsblk_t blocknr,
		ext4_group_t *blockgrpp, ext4_grpblk_t *offsetp)
{
	struct ext4_super_block *es = EXT4_SB(sb)->s_es;
	ext4_grpblk_t offset;

	blocknr = blocknr - le32_to_cpu(es->s_first_data_block);
	offset = do_div(blocknr, EXT4_BLOCKS_PER_GROUP(sb)) >>
		EXT4_SB(sb)->s_cluster_bits;
	if (offsetp)
		*offsetp = offset;
	if (blockgrpp)
		*blockgrpp = blocknr;

}

/*
 * Check whether the 'block' lives within the 'block_group'. Returns 1 if so
 * and 0 otherwise.
 */
static inline int ext4_block_in_group(struct super_block *sb,
				      ext4_fsblk_t block,
				      ext4_group_t block_group)
{
	ext4_group_t actual_group;

	actual_group = ext4_get_group_number(sb, block);
	return (actual_group == block_group) ? 1 : 0;
}

/*
 * Return the number of clusters used for file system metadata; this
 * represents the overhead needed by the file system.
 */
static unsigned ext4_num_overhead_clusters(struct super_block *sb,
					   ext4_group_t block_group,
					   struct ext4_group_desc *gdp)
{
	unsigned base_clusters, num_clusters;
	int block_cluster = -1, inode_cluster;
	int itbl_cluster_start = -1, itbl_cluster_end = -1;
	ext4_fsblk_t start = ext4_group_first_block_no(sb, block_group);
	ext4_fsblk_t end = start + EXT4_BLOCKS_PER_GROUP(sb) - 1;
	ext4_fsblk_t itbl_blk_start, itbl_blk_end;
	struct ext4_sb_info *sbi = EXT4_SB(sb);

	/* This is the number of clusters used by the superblock,
	 * block group descriptors, and reserved block group
	 * descriptor blocks */
	base_clusters = ext4_num_base_meta_clusters(sb, block_group);
	num_clusters = base_clusters;

	/*
	 * Account and record inode table clusters if any cluster
	 * is in the block group, or inode table cluster range is
	 * [-1, -1] and won't overlap with block/inode bitmap cluster
	 * accounted below.
	 */
	itbl_blk_start = ext4_inode_table(sb, gdp);
	itbl_blk_end = itbl_blk_start + sbi->s_itb_per_group - 1;
	if (itbl_blk_start <= end && itbl_blk_end >= start) {
		itbl_blk_start = max(itbl_blk_start, start);
		itbl_blk_end = min(itbl_blk_end, end);

		itbl_cluster_start = EXT4_B2C(sbi, itbl_blk_start - start);
		itbl_cluster_end = EXT4_B2C(sbi, itbl_blk_end - start);

		num_clusters += itbl_cluster_end - itbl_cluster_start + 1;
		/* check if border cluster is overlapped */
		if (itbl_cluster_start == base_clusters - 1)
			num_clusters--;
	}

	/*
	 * For the allocation bitmaps, we first need to check to see
	 * if the block is in the block group.  If it is, then check
	 * to see if the cluster is already accounted for in the clusters
	 * used for the base metadata cluster and inode tables cluster.
	 * Normally all of these blocks are contiguous, so the special
	 * case handling shouldn't be necessary except for *very*
	 * unusual file system layouts.
	 */
	if (ext4_block_in_group(sb, ext4_block_bitmap(sb, gdp), block_group)) {
		block_cluster = EXT4_B2C(sbi,
					 ext4_block_bitmap(sb, gdp) - start);
		if (block_cluster >= base_clusters &&
		    (block_cluster < itbl_cluster_start ||
		    block_cluster > itbl_cluster_end))
			num_clusters++;
	}

	if (ext4_block_in_group(sb, ext4_inode_bitmap(sb, gdp), block_group)) {
		inode_cluster = EXT4_B2C