EXT4源码分析之“块分配算法分析”（1）主体流程，系列的第一篇文章，主要介绍块分配算法的主要流程以及一些细节点，如快速提交重放、简单分配器、配额文件、延迟分配、分配上下文。

文章目录

写在前面

最近阅读了很多内核文件系统相关的源码，一直想写一篇文章将自己的收获表达出来，这篇文章写了四天，发现内容太多了，如果压缩会影响文章的质量，如果不压缩，应该没人愿意读完它，所以再三纠结下，决定将EXT”文件系统源码中与文件和块分配相关内容写成一个系列的文章，希望能通过这个系列让从未接触过这个领域的朋友们能有一点收获。

最近在做存储相关的工作，所以从内核的文件系统开始讲起。文件系统最核心的就是块分配算法，可以做为一个不错的切入点。希望未来如果没做相关工作，也能利用空余时间去更新由此展开的内容。

在写这篇文章之前，看了非常多网上的文章和源码，总结出一个经验：对于内核的设计，得先自己花时间去琢磨了，再去网上看看不同人的理解和分析，直接看文章，收获会少很多。

相关说明

做为系列的第一篇，将这个系列的相关说明全写在此处，后续篇章不再重复这些。

  • 本系列主要参考Linux内核版本为v5.19。
  • 本系列尽可能深的解析源码，但有些源码实在是看了没意义就没给出了。
  • 所有参考的源码、文章等会在最后给出。
  • 关于文章有任何问题欢迎私信我，或通过主页的联系方式联系我。

0.前置知识-EXT4块结构

一张图就可以大致了解EXT的块结构，即整体结构为：

  • 头部为1KB大小的引导块，后续依据存储空间的大小分为N个块组，每个块组的头部有数据块位图、inode位图、inode表等结构，数据块位于最后。
  • 默认一个块的大小为4KB，每个块组有32768个块，每个组的大小是128MB。
  • 块分配算法即为一个文件分配数据块的过程。
    在这里插入图片描述
    其余细节暂时不需要深入理解。

1.入口点流程

EXT4文件系统的块分配算法叫做mballoc多块分配器，其源码位于内核fs/ext4/mballoc.c中：

在这里插入图片描述

其主要的入口点为ext4_mb_new_blocks函数，其大致的函数关系图如下：

函数关系图如下（仅深入三层）：

注：图片可高清放大

在这里插入图片描述

ext4_mb_new_blocks
│
├── kmem_cache_zalloc
├── ext4_mb_initialize_context
│   ├── ext4_mb_group_or_file
│   │   └── ext4_mb_normalize_group_request
│   └── ext4_mb_new_preallocation
│       └── ext4_mb_new_group_pa
│         ext4_mb_new_inode_pa
│           └── ext4_get_group_no_and_offset
│
├── ext4_mb_use_preallocated
│   ├── ext4_mb_use_inode_pa
│   │   └── ext4_get_group_no_and_offset
│   └── ext4_mb_use_group_pa
│       └── ext4_grp_offs_to_block
│
├── ext4_mb_regular_allocator
│   └── (内部调用其他分配函数，如查找空闲块、分配块等)
│
├── ext4_mb_mark_diskspace_used
│   ├── ext4_read_block_bitmap
│   ├── ext4_journal_get_write_access
│   ├── ext4_get_group_desc
│   ├── ext4_grp_offs_to_block
│   ├── ext4_inode_block_valid
│   ├── ext4_lock_group
│   ├── ext4_handle_dirty_metadata
│   └── ext4_unlock_group
│
├── ext4_mb_discard_preallocations
│   ├── ext4_mb_discard_group_preallocations
│   │   ├── ext4_mb_load_buddy
│   │   ├── ext4_read_block_bitmap
│   │   ├── ext4_lock_group
│   │   ├── ext4_mb_release_group_pa
│   └── ext4_mb_trim_inode_pa
│       ├── ext4_discard_preallocations
│       └── ext4_mb_trim_inode_pa
│
├── ext4_mb_release_context
│   ├── ext4_mb_add_n_trim
│   ├── ext4_mb_pa_free
│   └── ext4_mb_trim_inode_pa
│
└── kmem_cache_free

其核心代码为：

/*
 * 主入口点，负责分配新的数据块
 * handle: 事务句柄
 * ar: 分配请求结构体，包含分配的目标等信息
 * errp: 用于返回错误码
 */
ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
                                struct ext4_allocation_request *ar, int *errp)
{
    struct ext4_allocation_context *ac = NULL; // 分配上下文
    struct ext4_sb_info *sbi;
    struct super_block *sb;
    ext4_fsblk_t block = 0; // 分配到的块号
    unsigned int inquota = 0; // 配额相关
    unsigned int reserv_clstrs = 0; // 保留的集群数
    u64 seq;

    might_sleep(); // 表示此函数可能会睡眠

    sb = ar->inode->i_sb; // 获取超级块
    sbi = EXT4_SB(sb); // 获取 EXT4 特定的超级块信息

    trace_ext4_request_blocks(ar); // 追踪分配请求

    // 如果文件系统处于快速提交重放状态，使用简单分配器
    if (sbi->s_mount_state & EXT4_FC_REPLAY)
        return ext4_mb_new_blocks_simple(handle, ar, errp);

    /* 允许配额文件使用超级用户保留 */
    if (ext4_is_quota_file(ar->inode))
        ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;

    /*
	* 如果不是延迟分配保留的块，则进行配额和空闲块检查
	*/
	if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0) {
		/* 检查并预留足够的空闲集群 */
		while (ar->len &&
			ext4_claim_free_clusters(sbi, ar->len, ar->flags)) {

			/* 让其他进程有机会释放空间 */
			cond_resched();
			/* 如果没有足够的空闲集群，则减半请求的集群数 */
			ar->len = ar->len >> 1;
		}
		/* 如果无法预留任何集群，则返回没有空间的错误 */
		if (!ar->len) {
			ext4_mb_show_pa(sb);
			*errp = -ENOSPC;
			return 0;
		}
		/* 记录成功预留的集群数 */
		reserv_clstrs = ar->len;
		
		/* 检查是否允许使用超级用户保留的块 */
		if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {
			/* 为超级用户保留块，使用不失败的配额分配函数 */
			dquot_alloc_block_nofail(ar->inode,
									EXT4_C2B(sbi, ar->len));
		} else {
			/* 为普通用户分配配额块，若超出配额则减小请求 */
			while (ar->len &&
				dquot_alloc_block(ar->inode,
									EXT4_C2B(sbi, ar->len))) {

				/* 设置标志，指示后续分配不使用预分配块 */
				ar->flags |= EXT4_MB_HINT_NOPREALLOC;
				/* 减小请求的集群数 */
				ar->len--;
			}
		}
		/* 记录成功分配的配额集群数 */
		inquota = ar->len;
		/* 如果配额分配失败，则返回配额超限的错误 */
		if (ar->len == 0) {
			*errp = -EDQUOT;
			goto out;
		}
	}

    // 分配分配上下文
    ac = kmem_cache_zalloc(ext4_ac_cachep, GFP_NOFS);
    if (!ac) {
        ar->len = 0;
        *errp = -ENOMEM; // 内存不足
        goto out;
    }

    // 初始化分配上下文
    *errp = ext4_mb_initialize_context(ac, ar);
    if (*errp) {
        ar->len = 0;
        goto out;
    }

    ac->ac_op = EXT4_MB_HISTORY_PREALLOC; // 设置操作历史为预分配

    seq = this_cpu_read(discard_pa_seq); // 读取当前CPU的丢弃序列

    // 尝试使用预分配的块
    if (!ext4_mb_use_preallocated(ac)) {
        ac->ac_op = EXT4_MB_HISTORY_ALLOC; // 设置操作历史为分配

        // 规范化分配请求
        ext4_mb_normalize_request(ac, ar);

        // 分配预分配空间
        *errp = ext4_mb_pa_alloc(ac);
        if (*errp)
            goto errout;

    repeat:
        // 使用常规分配器分配块
        *errp = ext4_mb_regular_allocator(ac);
        /*
         * 如果分配失败，则释放预分配块
         */
        if (*errp) {
            ext4_mb_pa_free(ac);
            ext4_discard_allocated_blocks(ac);
            goto errout;
        }
        // 如果分配成功且满足条件，释放预分配块
        if (ac->ac_status == AC_STATUS_FOUND &&
            ac->ac_o_ex.fe_len >= ac->ac_f_ex.fe_len)
            ext4_mb_pa_free(ac);
    }

    if (likely(ac->ac_status == AC_STATUS_FOUND)) {
        // 标记磁盘空间已使用
        *errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_clstrs);
        if (*errp) {
            ext4_discard_allocated_blocks(ac);
            goto errout;
        } else {
            block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex); // 获取块号
            ar->len = ac->ac_b_ex.fe_len; // 更新分配长度
        }
    } else {
        // 如果分配失败，尝试丢弃预分配块并重试
        if (ext4_mb_discard_preallocations_should_retry(sb, ac, &seq))
            goto repeat;
        /*
         * 如果分配失败，则释放预分配块
         */
        ext4_mb_pa_free(ac);
        *errp = -ENOSPC; // 没有足够的空间
    }

errout:
    if (*errp) {
        ac->ac_b_ex.fe_len = 0;
        ar->len = 0;
        ext4_mb_show_ac(ac); // 显示分配上下文信息
    }
    // 释放分配上下文
    ext4_mb_release_context(ac);
out:
    if (ac)
        kmem_cache_free(ext4_ac_cachep, ac);
    if (inquota && ar->len < inquota)
        dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len));
    if (!ar->len) {
        if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0)
            /* 释放保留的集群 */
            percpu_counter_sub(&sbi->s_dirtyclusters_counter,
                               reserv_clstrs);
    }

    trace_ext4_allocate_blocks(ar, (unsigned long long)block); // 追踪分配的块

    return block; // 返回分配的块号
}

它首先尝试使用预分配的块（preallocated blocks），如果预分配块不足或不可用，则回退到常规的块分配器进行分配。在分配过程中，还会处理配额检查、块位图更新以及事务日志的处理。

2.快速提交重放状态

对于上述入口函数中的快速提交重放状态，这里做一个解释。

快速提交（Fast Commit）是 EXT4 文件系统中的一个优化机制，旨在加快文件系统的挂载和恢复过程，特别是在系统崩溃或异常关机后。快速提交通过记录关键的元数据快照，减少需要重放的日志条目数量，从而加速恢复过程。

快速提交重放状态（Fast Commit Replay State）指的是文件系统在启动过程中，正在重放快速提交日志以恢复文件系统到一致状态的阶段。在此期间，文件系统会优先使用预先记录的快照信息进行恢复，而不是逐一重放所有的日志操作。

在快速提交重放状态下，文件系统的元数据可能尚未完全恢复或处于一种临时一致状态。此时，使用复杂的分配算法可能会受到限制，因为文件系统需要依赖快速提交日志中的信息来完成恢复。

使用简单分配器的原因如下：

  • 加速恢复：简单分配器可以在快速提交恢复过程中迅速分配块，加快恢复速度。
  • 避免冲突：在重放日志期间，复杂的分配算法可能会与正在恢复的元数据产生冲突，导致不一致或错误。简单分配器通过简化分配逻辑，减少潜在的冲突风险。
  • 确保一致性：快速提交的目标是快速恢复到一致状态。使用简单的分配策略有助于确保恢复过程的可靠性和一致性，而不必担心复杂分配逻辑引入的不确定性。

3.简单分配器

对于上述入口函数中的快速提交重放状态用到的简单分配器，这里做一个解释。

简单分配器主要用于 Ext4 快速提交（fast commit）重放路径。在这种情况下，分配块的过程简化为从目标块（goal block）线性搜索空闲块，同时排除那些在快速提交重放后将被使用的块。这种方法避免了复杂的预分配和上下文管理，适用于特定的高性能场景。

核心函数ext4_mb_new_blocks_simple的注释如下：

/**
 * ext4_mb_new_blocks_simple -- 简单分配器，用于快速提交重放路径
 * @handle:		事务句柄
 * @ar:			分配请求结构体
 * @errp:		错误码指针
 *
 * 返回值:
 * 成功时返回分配的起始块号，失败时返回0并设置errp为错误码。
 */
static ext4_fsblk_t ext4_mb_new_blocks_simple(handle_t *handle,
					struct ext4_allocation_request *ar, int *errp)
{
	struct buffer_head *bitmap_bh;
	struct super_block *sb = ar->inode->i_sb;
	ext4_group_t group;
	ext4_grpblk_t blkoff;
	ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);
	ext4_grpblk_t i = 0;
	ext4_fsblk_t goal, block;
	struct ext4_super_block *es = EXT4_SB(sb)->s_es;

	// 获取分配目标块，如果目标块无效，则使用第一个数据块
	goal = ar->goal;
	if (goal < le32_to_cpu(es->s_first_data_block) ||
			goal >= ext4_blocks_count(es))
		goal = le32_to_cpu(es->s_first_data_block);

	// 初始化分配长度为0
	ar->len = 0;

	// 获取目标块所属的组号和组内偏移
	ext4_get_group_no_and_offset(sb, goal, &group, &blkoff);

	// 从目标组开始，遍历所有组
	for (; group < ext4_get_groups_count(sb); group++) {
		// 读取块位图
		bitmap_bh = ext4_read_block_bitmap(sb, group);
		if (IS_ERR(bitmap_bh)) {
			*errp = PTR_ERR(bitmap_bh);
			pr_warn("Failed to read block bitmap\n");
			return 0;
		}

		// 获取组内第一个可分配的块
		ext4_get_group_no_and_offset(sb,
			max(ext4_group_first_block_no(sb, group), goal),
			NULL, &blkoff);

		// 在位图中查找下一个空闲块
		while (1) {
			i = mb_find_next_zero_bit(bitmap_bh->b_data, max, blkoff);
			if (i >= max)
				break;
			// 检查该块是否在快速提交重放后被排除
			if (ext4_fc_replay_check_excluded(sb,
				ext4_group_first_block_no(sb, group) + i)) {
				blkoff = i + 1;
			} else
				break;
		}
		// 释放位图缓冲区
		brelse(bitmap_bh);

		// 如果找到空闲块，则退出循环
		if (i < max)
			break;
	}

	// 检查是否找到空闲块
	if (group >= ext4_get_groups_count(sb) || i >= max) {
		*errp = -ENOSPC; // 没有可用空间
		return 0;
	}

	// 计算物理块号
	block = ext4_group_first_block_no(sb, group) + i;

	// 标记该块为已使用
	ext4_mb_mark_bb(sb, block, 1, 1);

	// 设置分配长度为1块
	ar->len = 1;

	return block; // 返回分配的块号
}

4.配额文件

对于上述入口函数中的配额检查，这里做一个解释。

配额（Quota）系统用于限制用户或用户组在文件系统中的资源使用量，如磁盘空间和文件数。配额文件是用于跟踪和管理这些限制的文件，通常包括以下几种：

  • 用户配额文件（User Quota File）：记录每个用户的磁盘使用情况和限制。
  • 组配额文件（Group Quota File）：记录每个用户组的磁盘使用情况和限制。

配额文件通常存储在文件系统的特定位置，如 aquota.user 和 aquota.group，并由配额管理工具（如 quota, edquota）进行操作。

root 用户在系统中具有最高权限，能够绕过常规的配额限制。为root用户保留磁盘空间有以下几个原因：

  • 系统维护和紧急情况：在系统出现问题或需要进行维护时，root用户可能需要创建或修改文件，而不受配额限制的约束，以确保系统的稳定性和可恢复性。
  • 防止配额耗尽导致系统锁死：如果所有用户（包括超级用户）都受到配额限制，可能会导致root用户无法执行关键的系统管理任务，甚至导致系统无法正常运行。
  • 灵活性：为root用户保留空间可以提供更大的灵活性，允许在必要时进行大规模的数据操作，而不必担心配额限制阻碍操作。

5.延迟分配

对于上述入口函数中的延迟分配，这里做一个解释。

延迟分配（Delayed Allocation，简称 delalloc）是一种优化技术，主要用于减少磁盘碎片和提升写入性能。在使用延迟分配的文件系统（如 EXT4、XFS 等）中，文件的写入操作不会立即分配磁盘块，而是将写入的数据保存在内存的缓冲区（page cache）中，直到数据需要被刷新到磁盘时再进行实际的块分配。

优点：通过延迟分配、提升性能、优化空间。
缺点：内存占用、复杂性。

(ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0：这意味着，如果当前的分配请求 不是 由延迟分配机制保留的（即，常规的分配请求），则需要进行配额和空闲块检查。

为什么这样判断：

  • 延迟分配保留的块已处理：对于由延迟分配机制预先保留的块，相关的配额和空闲块检查已经在预分配阶段完成。因此，在实际的块分配过程中，无需再次进行这些检查。

延迟分配的实际块分配发生在以下情况下：
• 事务提交时： 当数据页被写入磁盘或事务被提交时，系统会触发块的实际分配。
• 同步操作时： 当执行文件系统的同步操作（如 fsync）时，未分配的块会被分配并写入磁盘。
这些操作会调用 ext4_mb_new_blocks 来完成块的分配和标记。

6.分配上下文

对于上述入口函数中的分配上下文，这里做一个解释。

分配上下文（Allocation Context）是 EXT4 文件系统中用于管理和跟踪块分配过程的一个关键数据结构。它包含了分配请求的所有相关信息，并在块分配的不同阶段传递和更新这些信息，以确保分配过程的正确性和高效性。

具体来说，struct ext4_allocation_context 包含以下主要内容：

  • 超级块指针（ac_sb）：指向文件系统的超级块，包含文件系统的全局信息。
  • inode 指针（ac_inode）：指向发起分配请求的 inode，表示哪个文件需要分配块。
  • 分配请求结构体（ac_o_ex 和 ac_g_ex）：包含分配的目标群组、起始块、长度等信息。ac_o_ex 表示原始分配请求，ac_g_ex 表示规范化后的分配请求。
  • 操作历史（ac_op）：记录当前的分配操作类型，例如预分配（prealloc）或常规分配（alloc）。
  • 标志（ac_flags）：存储分配请求的各种标志，如是否使用预分配块、是否允许超级用户保留等。
  • 本地性群组指针（ac_lg）：指向本地性群组，优化块分配的局部性。
  • 预分配空间指针（ac_pa）：指向预分配的块空间，用于快速分配。
  • 分配状态（ac_status）：表示当前分配的状态，例如是否找到合适的块。
  • 其他辅助字段：用于管理分配过程中的各种状态和条件。

分配上下文的作用：集中管理分配信息、支持复杂的分配逻辑、提高代码可维护性和可扩展性。

代码中的具体解析：

ac = kmem_cache_zalloc(ext4_ac_cachep, GFP_NOFS);
if (!ac) {
    ar->len = 0;
    *errp = -ENOMEM;
    goto out;
}
  • ext4_ac_cachep：这是一个内存缓存，专门用于分配 struct ext4_allocation_context 对象。通过预先创建一个内存缓存，EXT4 能够高效地分配和回收分配上下文对象。
  • GFP_NOFS：分配标志，表示在文件系统内部调用，不能睡眠或进行阻塞操作，避免死锁。

ext4_mb_initialize_context函数具体解析：

static noinline_for_stack int
ext4_mb_initialize_context(struct ext4_allocation_context *ac,
                           struct ext4_allocation_request *ar)
{
    struct super_block *sb = ar->inode->i_sb;
    struct ext4_sb_info *sbi = EXT4_SB(sb);
    struct ext4_super_block *es = sbi->s_es;
    ext4_group_t group;
    unsigned int len;
    ext4_fsblk_t goal, block;
    
    // 限制分配长度不超过每组集群数
    len = ar->len;
    if (len >= EXT4_CLUSTERS_PER_GROUP(sb))
        len = EXT4_CLUSTERS_PER_GROUP(sb);

    // 从目标块开始搜索
    goal = ar->goal;
    if (goal < le32_to_cpu(es->s_first_data_block) ||
        goal >= ext4_blocks_count(es))
        goal = le32_to_cpu(es->s_first_data_block);
    ext4_get_group_no_and_offset(sb, goal, &group, &block);

    // 设置分配目标
    ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);
    ac->ac_status = AC_STATUS_CONTINUE;
    ac->ac_sb = sb;
    ac->ac_inode = ar->inode;
    ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;
    ac->ac_o_ex.fe_group = group;
    ac->ac_o_ex.fe_start = block;
    ac->ac_o_ex.fe_len = len;
    ac->ac_g_ex = ac->ac_o_ex;
    ac->ac_flags = ar->flags;

    // 根据上下文选择使用文件级预分配或群组级预分配
    ext4_mb_group_or_file(ac);

    mb_debug(sb, "init ac: %u blocks @ %u, goal %u, flags 0x%x, 2^%d, "
            "left: %u/%u, right %u/%u to %swritable\n",
            (unsigned) ar->len, (unsigned) ar->logical,
            (unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
            (unsigned) ar->lleft, (unsigned) ar->pleft,
            (unsigned) ar->lright, (unsigned) ar->pright,
            inode_is_open_for_write(ar->inode) ? "" : "non-");
    return 0;
}

参考

  • https://www.kernel.org/doc/html/v5.19/filesystems/ext4/index.html（linux内核官方文档）
  • https://github.com/torvalds/linux/blob/v5.19/fs/ext4/mballoc.c（内核源代码）
  • https://opensource.com/article/17/5/introduction-ext4-filesystem

ATFWUS 2024-12-25

# 文件系统
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

avatar 魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

avatar 魔乐社区

如何快速上手 hvac：HashiCorp Vault Python 客户端零基础入门指南

**hvac** 是 HashiCorp Vault 的 Python 3.X 客户端库，专为开发者提供简单高效的 Vault 交互方式。无论你是需要管理密钥、配置身份验证，还是实现安全的秘密数据存储，hvac 都能帮助你轻松搞定 Vault 的各项操作。本文将带你零基础快速入门，从安装到基础操作，让你在几分钟内即可上手使用这个强大的工具。[![hvac 客户端 Logo](https://r

avatar 魔乐社区