论文-linux 文件系统分析及其系统调用发言报告.pdf

linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 1 页 linux 文件系统分析及其系统调用发言报告文件系统分析及其系统调用发言报告 作者 黄苟作者 黄苟 第一部分第一部分 一 文件系统上层结构整体介绍一 文件系统上层结构整体介绍 图一 linux 文件系统分层示意图 Linux 文件系统的最优秀的地方是对多种文件系统的支持 这里的 上层结构是指 VFS 系统和具体的文件系统 即除 buffer 管理系统以外的部 分 为了实现这种特色 就必须有一个抽象的层次来统一描述各种文件系 统 Linux 中就用 VFS 来实现了这个抽象层 同时 各种具体的文件系统 又必须有一个和 VFS 交互的手段 在 Linux 系统中 这种交互的手段是通 过 n 个数据结构中的 union 结构和函数指针来实现的 这些数据结构如下 一 一 VFS 和具体的文件系统的连接途径和具体的文件系统的连接途径 File system type中中 struct super block read super struct super block void int 在mount一个文件卷时 VFS的do mount函数会调用read super函数 EXT2 VFS Buffers Cache Inode Cache Directory Cache 抽象层 具体文件系统层 缓冲管理层 linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 2 页 而 read super 将找到一个未被使用的 read blocks 数组项 并调用相应 file system type 的 read super 函数 以上均在 fs super c 文件中 就 ext2 文件系统的 read super 函数名为 ext2 read super 在 fs ext2 super c 文件中 而言 它做了如下一些工作 首先它读入该文件卷 的第一个逻辑块 该块含有相应文件卷的 superblock 结构 在相应 VFS superblock 项的 u ext2 sb 结构中的 s sbh 和 s es 分别指向该缓冲区的头部 和数据区 接下来 该函数将该缓冲区中的一些数据复制或经计算复制到 VFS superblock 的 u ext2 sb 结构中 在做完一些检验工作以后 该函数读 入文件卷组描述符所在的块并将这些缓冲区头部的指针赋值给 VFS superblock 的 u ext2 sb s group desc 结构 并在最后读入该文件卷的根结 点 Super block 中 Super block 中 Union u 该结构定义了对应各文件卷的结构 如上所述 它的 很多数据均在具体类型文件系统的 read super 函数中被赋值 同时 do mount 函数在 read super 函数返回后 会记录该文件卷安装到的结点 即对 VFS 中 superblock 的 s covered 赋值 Super operations结构 该结构中定义了对 inode 和 superblock 的各种相应操作函数的指针 ext2 中其实例为 ext2 sops ext2 super c 中定义 并在其 ext2 read super 函数中对其赋值 sb s op 6 返回 5 ext2 updata inode ext2 inode c 功能 将 VFS inode 的改动信息写回 VFS 中 inode 参数 inode VFS 中 inode do sync 写同步标志 调用的主要函数 无 linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 8 页 过程 1 根据 inode i ino 读入该 inode 在 ext2 中相应的块 并进而得 到具体 inode 记录项 所用的方法即上一部分 p5 上面 叙述的过 程 2 将 inode 的信息写到缓冲区中相应记录里 3 置缓冲区脏标志 如果有同步写标志 则等待缓冲区写回 否 则 释放缓冲区 返回 6 dir namei fs namei c 功能 在指定目录中按给定的带目录文件名查找其 inode 参数 pathname 带路径的文件名 namelen 用于返回 放最后一段文件名长度 name 用返回 放最一段文件名 base 指定目录对应的 VFS inode res inode 用于返回 放最后一段文件名所在父目录对应的 VFS inode 主要调用函数 lookup follow link iput 例示 要从根目录开始查找 调用 dir namei usr src linux namelen 若成功返回 则说明 dir 目录文件中已存在名为 name 的目录 返回错误标志 关于此 函数见前 2 调用 ext2 new inode dir S IFDIR 5 在父目录 dir 的目录文件中增加 1 项 引用 inode 6 把 inode 加入 directory cache 7 成功返回 0 3 ext2 new inode ext2 ialloc c 功能 在 ext2 文件系统中找一个未用的 inode 结点 参数 dir VFS 的 inode 结点 一般调用该函数 dir 为父目录 VFS inode mode 待生成的 ext2 inode 的类型 err 返回错误信息 调用的主要函数 get empty inode get group desc load inode bitmap 过程 linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 12 页 1 调用 get empty inode 得到一个新的 VFS inode 该 inode 用于 返回 2 if mode 为 dir 类型 then 遍历所有的组描述符 找出 free ext2 inodes 数 量 最 多 的 一 个 组 组 描 述 符 的 得 到 期 是 通 过 get group desc 函数调用 它的过程即为 上一部分 p5 上面 所述过程的 1 3 步 的组描述符 else a 若 dir 所属的组还有 free ext2 inode 则取其组描述符 b if dir 所属的组无 free ext2 inode then 从该组开始 以 2 的 次幂为跨度 搜寻第一个有 free ext2 inode 的组描述符 c if 还未找到 then 遍历所有组描述 找到含 free ext2 inodes 数量最多的组描述符 3 调入选中的组记为 i 的 inode 位图 4 找到该组内第一个 free ext2 inode 的组内编号 记为 j 将位 图的相应位置改为占用 并根据 superblock 同步标志是否可延时 写该位图缓冲区 5 j 改为此新 ext2 inode 的实际编号 相应组描述符的 free inodes 数量 1 若为目录 则已用目录数 1 延时写回该描述符所在的 缓冲区 修改 superblock 中的相关信息 对 VFS inode 进行相应初始化 并加入 hash 表 做相应配额控制 返回 VFS inode 二 二 sys rmdir 系统调用系统调用 1 概况概况 A 功能功能 该系统调用将删除一个目录结点 同 sys mkdir 类似 也将结合 ext2 文件系统来分析它的工作过程 B 输入参数输入参数 pathname 带路径的文件名 C 工作过程工作过程 1 调用 getname 函数 同 sys mkdir 系统调用 2 若第 1 步成功 则做如下工作 a 调用 remove trailing slashes 函数 同 sys mkdir 系统调用 b 调用 do mkdir 函数 做实际的删除目录的工作 c 调用 putname 函数 同 sys mkdir 系统调用 3 同 sys mkdir 系统调用 2 主要调用例程主要调用例程 1 do rmdir 该函数流程基本同 do mkdir 其调用的具体文件系统的函数为 linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 13 页 rmdir 2 ext2 rmdir 功能 删除指定目录下目录名为 name 的目录 参数 dir 要删除的目录名所在的目录 name 带删除的目录名 len 目录名长度 过程 调用 ext2 find entry 函数在 dir 的目录文件中找到相应目录名 对应的 ext2 inode 编号 并用 iget 函数得到其 VFS inode 记为 inode 做权限检查 判断是否为删除自己 rmdir 的情形 是则返回出错代码 调用 empty dir 判断该目录是否为空 若有别的进程引用 则 把其目录文件长度置为 删除其在父目录文件中相应的项并写回父目录文件 标记此 inode 的 i nlink 0 写回 inode 标记其 i dirt 1 释放 inode 和 dir 在释放 inode 时 ext2 put inode 函数会调用 ext2 free inode 该函数发现 inode 的 nlink 0 会将相应的 inode bitmap 位清掉 最终 完成 ext2 inode 的释放 3 empty dir 功能 检查指定目录是否为空 参数 inode 指定的目录对应的 VFS inode 过程 读入该目录的目录文件 将第一项 引用自身 赋给 de 第二项 引用父目录 赋给 de1 判断此两项是否有错 偏移量为 de1 和 de 的长度之和 if 偏移量 文件长度 then 做如下工作 a 如果当前缓冲块遍历完 读入下一块 b 遍历当前缓冲块 判断有无目录或文件 并调整偏移 量 一旦发现有内容 则返回 若执行至此 则成功返回 linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 14 页 第二部分第二部分 三 缓冲块的管理三 缓冲块的管理 lru list DIRTY free list 512 1024 2048 4096 8192 unused listreuse list 新分配的一个页面 的缓冲区 IO操作后一个页面 的缓冲区 buffer head bufferbuffer buffer head Memory LOCKEDLOCKED1 CLEAN 1 1 8 8 1010 7 7 9 9 1212 1212 1212 1212 3 3 5 5 4 4 6 6 2 2 4 4 1111 图三 buffer head 在各个链的转换 在图三中 各转换函数如下 1 getblk 2 refill freelist 3 grow buffers 4 try to free buffer 5 get free page 6 get unused buffer head 7 recover reusable buffer heads 8 get more buffer heads 调用了 kmalloc 9 bdflush 10 free async buffers linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 15 页 11 free page 12 refile buffer 下面说明这些函数的功能及流程 1 struct buffer head getblk kdev t dev int block int size getblk 函数获取一个缓冲块用于读写操作 它先在 buffer head 的 hash 表中寻找对应给定设备和块号的缓冲块 找到说明已分配 则返回 hash 表中的缓冲块对应的 buffer head 找不到则检查块大小为 size 的空闲链 表 若链表不为空 则取表头的 buffer head 作为返回值 否则调用函数 refill freelist 填充空闲链表 再取出表头作为返回值 2 static void refill freelist int size refill freelist 函数一次试图分配一定数量内存用作缓冲块 这个数值保存 在一个参数表中 bdf prm b un nrefill size 为欲分配内存的大小 它主要 分三步来满足需求 1 调用 grow buffers 从未用内存中来进行分配 成功则返回 否则执行 2 2 尝试从 BUF CLEAN BUF LOCKED BUF LOCKED 三个链表中取 出一个合适的缓冲块移入 free list 链 对于这个缓冲块的要求是不 脏 没被加锁 没有保护标志及引用数为 0 等 然后在这个缓冲块所 在链表重复找这样的块移入 free list 若找完这个链还不能分配所需 的缓冲块 就重新在三个链表中找并移入 free list 如果满足了要求 则返回 否则进行下面的处理 由于在找可移入 free list 的缓冲块时 找的都是与所需得到缓冲块大小一样的缓冲块 对于大小不一样的缓 冲块 refill freelist 则尝试回收这些缓冲 它调用 try to free buffer 来完成这一工作 这一函数检查这一缓冲块所在页面的所有缓冲块 如果它们不脏 没被加锁 没有置保护位 没有进程等它 则用 free page 释放这些缓冲块 并把它们的 buffer head 放入 unused list 中 这样 当处理完这三个链表后 系统的内存可能会增加而大于一 个限制值 这时可以再次调用 grow buffers 从内存分配缓冲块 若需 求满足 则返回 否则执行 3 3 如果当前进程不是 bdflush 进程且满足唤醒 bdflush 的条件 脏块到一 定数目 则唤醒 bdflush 进程并等它做完 再进入这一进程时 如果 空闲链表不为空 则返回 如果仍为空 再次尝试 grow buffers 分配 因为在该进程睡眠时 可能有些进程会释放内存 如果不成功 而 DIRTY 链存在脏块 唤醒 bdflush 写回脏块 若连脏块都没有了 就 以优先级 GFP IO 调用 grow buffers 进行尝试 所有这些努力都试过后 我们降低要求 少分配一个页面大小的缓冲 块 重复上述 2 3 步来填充 free list 表直到要求能得到满足 3 static int grow buffers int pri int size 这个函数试图从内存中分配一个页面 再分为所需大小的缓冲块链 linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 16 页 入 free list 中 它首先从内存中申请一个页面 get free page 再调用 create buffers 将一个页面分成所需大小的缓冲块 并把 buffer head 和这 些 buffer 相对应 最后把这些缓冲链入相应的 free list 链表 static struct buffer head create buffers unsigned long page unsigned long size 这个函数调用 get unused buffer head 得到一个空表头 将页面分成所需 大小 将不同 buffer head 的 b data 指向页面的不同区 所有这些 buffer head 用 b this page 链连在一起便于检索 static struct buffer head get unused buffer head void 这 个 函 数 先 调 用 recover reusable buffer head 从 reused list 回 收 buffer head到unused list 若unused list还 为 空 它 调 用 get more buffer heads 从内存中分配一个 buffer head kmalloc 函数 当 然 如果内存太小不能分配一个buffer head并且reused list和unused list 为空时 它要进行进程调度 get unused buffer head 最终把 unused list 的表头返回 4 int bdflush void unused bdflush 是一个守护进程 它发觉脏块超过一定的限额后 就启动写 操作 将脏块写入磁盘 在上述的某些 buffer 缓冲块的函数中 也会唤 醒 bdflush 进程 把脏块写出 在完成 IO 操作后 原先分配的组成一个 页面大小的缓冲块可能被释放 free page 它们的表头就可以用 free async buffers 挂到 reused list 链表中 5 void refile buffer struct buffer head buf 在 lru list 的四个链表中 有可能出现状态转换 这个函数就是用于 调整缓冲块在四个链表中的位置的 并且在脏块数目大于一定限额时 唤醒 bdflush linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 17 页 四 系统调用四 系统调用 sys open 的分析的分析 sys open 系统调用的功能是在进程的打开文件表中添加一文件名为给 定参数的一项并填充其中的内容 它的主要流程如下 1 sys open 调用 get unused fd 分配一个空闲的文件描述符 current files fd 把文件名以从用户空间拷贝至核心空间 调用 do open 填写 文件描述符 释放刚分配的核心空间 返回文件描述符在进程打开文件 表中的下标 2 do open 从系统文件中得一个空项 struct file f 调用 open namei 找 出文件名对应的 inode 填写 f 中数据 把 f 放入 current 的文件描述符 表的指定位置 3 open namei 调用 dir namei 查找文件所在目录的 inode 并得到不带路 径的文件名及其长度 若是要新创建文件 则调用具体文件系统的create 操作并返回 对于 ext2 文件系统而言 就是 ext2 create 否则调用 lookup 和 follow link 找到文件的 inode 节点 接着检查 inode 权限 对于不同 文件类型调整 flag 如果要截断文件 则在获取写权限后 做 do truncate 截断文件 最终获得文件 inode 节点及不带路径的文件名及其长度 4 dir namei 主要是调用 lookup 和 follow link 沿着路径名向下找文件所 在目录的 inode 结点并获得不带路径的文件名及其长度 5 lookup 调用具体文件系统的 lookup ext2 lookup 它先在目录项的 hash 表中找 若找到则可知到 inode 节点号 通过 iget 则可以得到 inode 节点 如没找着 调用 ext2 find entry 找到目录项 进而可知 inode 节 点号 同时将这一目录项添到 hash 表中 6 follow link 调用具体文件系统的 follow link ext2 follow link 用于处 理符号链接文件 符号链接文件指向的原文件名存在 inode 的 idata 区 中 或是存在一个专门分配的 bock 中 ext2 follow link 读出原文件名 调用 open namei 找到相应的 inode 节点 7 ext2 create 调用 ext2 new inode 新建一个 inode 节点 在文件所在目 录的目录文件中添上一项 并将其添入目录缓存中 8 do truncate 改变文件对应 inode 属性 主要是文件长 截断文件所占 页面 截断文件的虚存块 释放文件多余的 block 并将未占满块的多 余部分清空 linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 18 页 第三部分第三部分 五 五 Sys close 的工作流程 的工作流程 参数参数 进程打开文件号 fd 过程 过程 1 首先判断 fd 是否有效 fd f inode 为 NULL 10 如果该系统文件指针的打开方式为写方式 调用 put write access 将 inode 的写引用计数减 1 11 如果该 inode 的引用计数大于 1 则说明还有其他系统文件指针在引 用该 inode 节点 结束 12 唤醒在该 inode 上等待的进程 13 关闭该 inode 节点 将 inode 节点信息所在的数据缓冲区内容写回到 设备中 由具体文件系统的 put inode 函数进行处理 如果该文件以写方 式打开 则还要将文件数据缓冲区的内容写回到设备 这个过程是一个持 续时间相对较长 而且可能由于阻塞而睡眠的过程 其间可能有其他进程 打开了这个文件 又要引用这个 inode 节点 14 如果 inode 节点被修改 则返回第 11 步 15 如果该 inode 是可写的 还要检查该 inode 对应的磁盘配额是否被修 改 若修改则要将新的磁盘配额写回到该文件系统的配额文件中 16 Inode 的引用计数减 1 若非 0 说明该 inode 还不能释放 结束 17 将该 inode 放入空闲 inode 队列 全局变量 nr free inodes 加 1 inode linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 19 页 被正确释放 结束 在分析过程中遇到了许多数据结构和相应的算法 我着重研究了有关 的系统文件锁 磁盘配额和读写请求队列机制 一 文件锁一 文件锁有共享锁 读锁 和独占锁 写锁 两种 是进程在读写文 件时加在相应的文件 inode 节点上的 文件锁的数据结构如下 struct file lock struct file lock fl next singly linked list for this inode struct file lock fl nextlink doubly linked list of all locks struct file lock fl prevlink used to simplify lock removal struct file lock fl nextblock circular list of blocked processes struct file lock fl prevblock struct task struct fl owner struct wait queue fl wait struct file fl file unsigned char fl flags unsigned char fl type off t fl start off t fl end fl next 指针链接了一条单向的不循环文件锁链表 此链表上是加在同一个 inode 节点上的互不冲突的文件锁 fl nextlink fl prevlink 形成了一个双向的不循环文件锁链表 此表连结 的是所有的 包括不同 inode 上的文件锁 fl nextblock fl prevblock 形成了一个双向的循环链表 此表连接的是阻 塞在 inode 上的文件锁 这些文件锁互相冲突 只能依次等待前一个文件 锁完成并解除 struct task struct fl owner 是拥有该文件锁的进程指针 struct wait queue fl wait 是在该文件锁上等待的队列 struct file fl file 是该文件锁的加锁对象 unsigned char fl type 标识了该文件锁的类型 共享 独占 归根结底 文件锁是作用在 inode 上的 每个 inode 有一个指针指向 它的一个文件锁 并通过这个文件锁可以遍历所有文件锁 在关闭文件时执行删除 inode 文件锁的操作 是为了确保没有进程阻 塞在该文件上 否则一旦删除该 inode 这些进程将会丢失 二 磁盘配额 二 磁盘配额 由于外部存储设备是一种系统资源 所以 Linux 用磁盘配额的方法有 效地加强了资源的管理 磁盘配额分为两种 组配额和用户配额 规定了 组和用户的文件和所占用设备数据块数量 这两种配额以文件的形式保存 linux 文 件 系 统 分 析 及 其 系 统 调 用 发 言 报 告 第5组 第 20 页 在设备上 由文件系统装入时在 vfsmount 中指定访问配额文件的系统文件 指针 在内存中有对应的磁盘配额结构 struct dquot unsigned int dq id id this applies to uid gid short dq type type of quota kdev t dq dev Device this applies to short dq flags see DQ short dq count reference count struct vf