笑天's profile笑天的共享空间BlogLists Tools Help

笑天的共享空间

April 14

高斯白噪声

白噪声是指它的功率谱密度函数在整个频域内是常数,即服从均匀分布。之所以称它为“白”噪声,是因为它类似于光学中包括全部可见光频率在内的白光

所谓高斯噪声是指它的概率密度函数服从高斯分布(即正态分布)的一类噪声。其一维概率密度函数可用数学表达式表示为



为噪声的数学期望值,也就是均值;为噪声的方差

  

January 02

文件访问原语

文件访问原语
POSIX API 最重要的一个抽象概念就是文件。尽管几乎所有的操作系统都将文件用于永久性存储器,但所有 Unix 版本通过文件抽象概念提供对大多数系统资源的访问。

更具体地说,这意味着 Linux 使用相同的一组系统调用来提供对设备(例如软盘和磁带设备)、网络资源(最常见的是 TCP/IP 连接)、系统终端,甚至内核状态信息的访问。感谢无所不在的系统调用,娴熟地使用与文件相关的调用对于每个 Linux 程序员来说都很重要。让我们仔细查看一下文件 API 背后的一些基本概念,并描述最重要的文件相关系统调用。

Linux 提供许多不同种类的文件。最常见的类型就简称为常规文件,它存储大量用于以后访问的信息。您所使用的绝大部分文件 -- 例如可执行文件(如 /bin/vi)、数据文件(如 /etc/passwd)和系统二进制文件(如 /lib/libc.so.6)-- 都是常规文件。它们通常驻留在磁盘上的某处,但我们稍后会发现,并不一定都是这种情况。

另一种文件类型是目录,它包含了一个其它文件及其位置的列表。使用 ls 命令列出目录中的文件时,它打开该目录的文件,并打印出它所包含的所有文件的信息。

其它文件类型包括块设备(表示文件系统高速缓存的设备,例如硬盘驱动器)、字符设备(表示非高速缓存的设备,例如磁带驱动器、鼠标和系统终端)、管道和套接字(允许进程相互之间对话),以及符号链接(允许文件在目录层次结构中有多个名称)。

大多数文件都有一个或多个引用它们的符号名。这些符号名是一组由 / 字符定界的字符串,并向内核标识文件。它们是 Linux 用户所熟悉的路径名;例如,路径名 /home/ewt/article 引用的是我手提电脑中包含这篇文章文本的文件。没有两个文件可以共享相同的名称(但单一文件可以有多个名称),因此路径名唯一地标识单一文件。

进程可以访问的每个文件都由一个小的非负整数标识,称为“文件描述符”。文件描述符由打开文件的系统调用创建,并由从当前进程创建的新子进程继承。就是说,当进程启动了一个新程序时,原始进程的打开文件通常是由新程序继承的

按照约定,大多数程序保留前三个文件描述符(0、1 和 2)用于特殊目的 -- 访问所谓的标准输出、标准输出和标准错误流。文件描述符 0 是标准输入,这里许多程序都将从外部世界接收输入。文件描述符 1 是标准输出。大多数程序在这里显示正常的输出。对于与错误情况相关的输出,使用文件描述符 2(标准错误)。

任何习惯使用 Linux shell 的人都曾看到过标准输入、输出和错误文件描述符的使用。通常,shell 运行命令时带文件描述符 0、1 和 2,都是指 shell 的终端。当使用 > 字符指示 shell 将一个程序的输出发送给另一个程序时,shell 在调用新程序之前打开该文件作为文件描述符 1。这将导致程序将它的输出发送给指定的文件而不是用户终端;其妙处是,对于程序本身,这是透明的!

与之类似,"<" 字符指示 shell 使用特定的文件作为文件描述符 0。这样就强迫程序从该文件中读取它的输入;这两种情况下,任何来自程序的错误仍将出现在终端上,如同它们在文件描述符 2 的情况下发送给标准错误一样。(在 "bash" shell 中,可以使用 2> 而不是 > 将标准错误重定向)。这种类型的文件重定向是 Linux 命令行最强大的特性之一。

使用任何与文件相关的系统调用之前,程序应该包括 <fcntl.h> 和 <unistd.h>;它们为最普遍的文件例程提供了函数原型和常数。在下面的示例代码中,我们假设每个程序开始处都有

#include <fcntl.h>
#include <unistd.h>

首先,让我们了解如何读写文件。凭直觉就可以知道,read() 和 write() 系统调用是执行这些操作的最常用方法。这两种系统调用将有三个自变量:要访问的文件描述符、指向要读写的信息的指针以及应该读写的字符数。返回成功读写的 字符数。清单 1 说明了一个简单的程序,它从标准输入(文件描述符 0)中读取一行,并将它写入标准输出(文件描述符 1):

清单 1:

void main(void) {
char buf[100];
int num;

num = read(0, buf, sizeof(buf));
write(1, "I got: ", 7); /* Length of "I got: " is 7! */
write(1, buf, num);
}

关于这个处理有两个值得注意的问题。首先,我们要求 read() 返回 100 个字符,但如果我们运行这个程序,只有在用户按下了 "enter" 键以后才能获得输入。许多文件操作都根据最佳效果工作:它们尝试返回程序要求的所有信息,但只有部分能够成功。缺省情况下,终端配置成一旦存在 "\n" 或新行符(通过按 "enter" 键产生)时,就从 read() 调用返回。这实际上非常方便,因为大多数用户都希望程序无论如何都是面向行的。但常规数据文件并非如此,如果依靠它就可能产生不可预料的结果。

另一个要注意的问题是我们不必在显示输出后写一个 \n。read() 调用给了我们来自用户的 \n,只将那个 \n 通过 write() 写回标准输出。如果您希望在没有新行符的情况下看到发生的事件,尝试将最后一行改为

write(1, buf, num - 1);

有关这个简单示例的最后一点:buf 绝对不包含实际的 C 字符串。C 字符串由标记字符串结束的单一 \0 字符终止。因为 read() 不将 \0 添加到缓冲区的结尾,在 read() 上使用 strlen()(或任何其它 C 字符串函数)将可能铸成大错!这种行为可以让 read() 和 write() 对包括 \0 字符的数据处理,而这对于一般字符串函数来说是不可能的。

read() 和 write() 系统调用可以对绝大多数文件起作用。但它们不对目录起作用,目录应该通过特殊函数(例如 readdir())来访问。另外,read() 和 write() 对于某些类型的套接字也不起作用。

某些文件,例如常规文件和块设备文件,使用文件指针的概念。它指定在文件中,下一个 read() 调用从哪里读取,下一个 write() 调用从哪里写入。read() 或 write() 后,文件指针随着已处理的字符数(在内部,通过内核)增加。这样,使用单一循环就可以方便地读取文件中的所有数据。清单 2 就是示例:

清单 2:

char buffer[1024];
while ((num = read(0, buffer, 1024))) {
printf("got some data\n");
}


这个循环将读取标准输入上的所有数据,自动在每次读取后增加内核的内部文件指针。当文件指针处于文件结尾时,read() 将返回 0 并退出循环。某些文件(例如字符设备 -- 终端就是很好的一例)本身没有文件指针,所以对于这一点,该程序将继续运行,直到用户提供文件结束标记(通过按 "Ctrl-D")为止。

到现在为止,我们已经知道如何读写文件了,下一步要学习如何打开一个新文件。打开不同类型的文件有不同方法;我们将在这里讨论的方法是通过路径名打开在文 件系统中表示的文件;包括常规文件、目录、设备文件和指定的管道。某些套接字文件有路径名,那些必须通过替代方法打开

撇开放弃权利的,open() 系统调用可以让程序访问大多数系统文件。open() 是个不寻常的系统调用,因为它获取两个或者三个自变量:

int open(const char *
pathname,
int flags);

或者,
int open(const char *
pathname,
int flags,
int perm);

第一种形式更普遍一些;它打开一个已存在的文件。第二种格式应该在需要创建文件时使用。第三个自变量指定应该给予新文件的访问权限

open() 的第一个参数是以正常 C 字符串表示的全路径名(即以 \0 终止)。第二个参数指定文件应该如何打开,并包括逻辑“与”操作的一个或多个以下标志:

O_RDONLY:文件可以只读
O_RDWR:文件可以读写
O_APPEND:文件可以读或附加
O_CREAT:如果文件还不存在则应该创建
O_EXCL:如果文件已存在,失败而不是创建它(只应该使用 O_CREAT)
O_TRUNC:如果文件已存在,从中除去所有数据(与创建新文件类似)

open() 的第三个参数只在使用 O_CREAT 时需要;它指定了以数字表示的文件许可权(格式与 chown 命令的数值许可权自变量的格式相同。为 open() 指定的许可权受用户的 umask 影响,后者允许用户指定一系列新文件应该获得的缺省许可权。大多数创建文件的程序都使用第三个自变量 0666 调用 open(),可以让用户通过 umask 来控制程序的缺省许可权。(大多数 shell 的 umask 命令都可以更改它。)

例如,清单 3 显示了如何为进行读写打开文件、如果它不存在则创建,以及废弃其中的数据:

清单 3:

int fd;
fd = open("myfile", O_RDWR | O_CREAT | O_TRUNC, 0666)
if (fd < 0) {
/* Some error occurred */
/* ... */
}

open() 返回引用文件的文件描述符。回忆一下,文件描述符总是 >= 0。如果 open() 返回了一个负值,就表示发生了错误,全局变量错误号包含了描述问题的 Unix 错误代码。open() 总尽量返回最小数,如果没有使用文件描述符 0,open() 将总返回 0。

进程带文件结束时,它应该通过 close() 系统调用关闭它,该系统调用的格式为:

int close(int fd);

close 的文件描述符是传递给 close() 的唯一自变量,在成功情况下返回 0。尽管 close() 失败的情况比较少见,但如果文件描述符引用的是远程服务器上的文件,系统无法正确清空它的高速缓存,close() 就可能真的失败。进程终止时,内核自动关闭所有还在打开的文件。

最后的一个常见文件操作是移动文件指针。这(自然)只对带文件指针的文件有意义,如果尝试在不恰当的文件上尝试该操作就会返回错误。lseek() 系统调用用于以下目的:

off_t lseek(int fd, off_t pos, int whence);

off_t 类型是表达 longint (long 就是 lseek 中 "l" 的来历)的一种别致方法。lseek() 返回相对于文件开始处文件指针的最终位置,如果有错误,则返回 -1。这个系统调用希望被移动的文件指针所属的文件描述符作为第一个自变量,将它移动到文件中的位置作为第二个自变量。最后一个自变量描述文件指针的移动 方式。

SEEK_SET 将它移动到从文件开始算起的 pos 字节。
SEEK_END 将它移动到从文件结尾算起的 pos 字节。
SEEK_CUR 从它当前位置开始向文件结尾移动 pos 字节。

open()、close()、write()、read() 和 lseek() 的组合为 Linux 提供了基本的文件访问 API。虽然还有许多其它操纵文件的函数,但这里描述的是最常用的。

大多数程序员都使用熟悉的 ANSI C 库文件函数,例如 fopen() 和 fread(),而不是在此描述的低级系统调用。可以预见到,fopen() 和 fread() 是在用户级别库中这些系统调用的基础上实现的。仍然会经常看到低级系统调用的使用,特别是在更复杂的程序中。通过熟悉这些例程和接口,您就可以成为一个真 正的 Unix 黑客了。

关于作者
Erik Troan 是 Red Hat Software 的开发者,Linux Application Development 一书的作者之一。可以通过 ewt@redhat.com 与他联系。

linux tr命令

1      tr -d  ''\r''<oldfile> newfile    **删掉回车**

应用-s参数:-s 删除所有重复出现字符序列,只保留第一个;

              即将重复出现字符串压缩为一个字符串。例如:

  tr  -s "\n"<oldfile> newfile    **删掉空行**

3      tr  "[a-z]" "[A-Z]"<oldfile> newfile   **小写到大写**

    或 tr  "[:lower:]" "[:upper:]"<oldfile> newfile



有问题的两点:

1 $ echo "this is a test " | tr -s "this" "that"

    that at a tet #不能够根据整个词进行替换


2 $ echo "this is a test " | tr -d "is"

    th  a tet  #把每一个字符都删除,不能当做整个字符串来处理

December 28

Linux 指令:文件系统--mkfs-sync-swapon

  指令:mkfs

  使用权限: 超级使用者

  使用方式: mkfs [-V] [-t fstype] [fs-options] filesys [blocks]

  说明:建立 linux 档案系统在特定的 partition 上

  参数:

device :预备检查的硬盘 partition,例如:/dev/sda1
-V : 详细显示模式
-t : 给定档案系统的型式,Linux 的预设值为 ext2
-c : 在制做档案系统前,检查该partition 是否有坏轨
-l bad_blocks_file : 将有坏轨的block资料加到 bad_blocks_file 里面
block : 给定 block 的大小

  例子:

  在 /dev/hda5 上建一个 msdos 的档案系统,同时检查是否有坏轨存在,并且将过程详细列出来:

  mkfs -V -t msdos -c /dev/hda5



Linux 指令:文件系统--sync

  名称 : sync

  使用权限 : 系统管理者

  使用方式 : sync

  说明 : Linux 系统中欲写入硬盘的资料有的时候会了效率起见,会写到 filesystem buffer 中,这个 buffer 是一块记忆体空间,如果欲写入硬盘的资料存于此 buffer 中,而系统又突然断电的话,那么资料就会流失了,sync 指令会将存于 buffer 中的资料强制写入硬盘中。



名称: swapon

  使用者权限: 超级使用者(super-user)

  使用方式:

/sbin/swapon -a [-v]
/sbin/swapon [-v] [-p priority] specialfile ...
/sbin/swapon [-s]

  参数:

-h 请帮帮我
-V 显示版本讯息
-s 显示简短的装置讯息
-a 自动启动所有SWAP装置
-p 设定优先权,你可以在0到32767中间选一个数字给他。或是在 /etc/fstab 里面加上 pri=[value] ([value]就是0~32767中间一个数字),然后你就可以很方便的直接使用 swapon -a 来启动他们,而且有优先权设定。

  swapon 是开启swap。

  相对的,便有一个关闭swap的指令,swapoff。

December 26

linux网络相关

一 TCP/IP中的两个命令
/sbin/ifconfig-查看,配置图修改网络
/sbin/setup命令
二 在局域网用的都是IP地址,而对于本地网络通信来说,则是使用“媒体访问控制”或者“MAC地址”
IPv4中两者是通过arp协议转换
MAC (Media Access Control) address,由48bit(8B)来编码,
arp运行方式:
1本地网络主机mac地址解析
(1)检查A缓存,有B则完成
(2)arp向局域网的所有主机广播arp请求数据包,内含A的mac和IP地址以及目的主机IP地址请求
(3)符合条件的B主机将原主机A的MAC,IPtianjia到本机的ARP缓存中。
(4)B将ARP响应信息给A,内包含B的MAC
(5)A接到B响应后,将B的MAC IP存入缓存,然后A将ICMP发给B

2远程网络主机mac地址解析
(1)检查A缓存,有B则完成
(2)ARP向局域网的所有主机广播arp请求数据包,内含A的mac和IP地址以及目的主机IP地址。因为是广播数据包,局域网所有主机都接收该ARP请求,然后自检
(3)当本地网络主机都拒绝这个ARP请求,路由器在接收该广播数据包后,检查本身的路由表决定是否可以
访问这个远程的子网。
如果可以访问这个远程网络,它会将A的MAC IP添加到本机ARP缓存中
(4)路由器直接将ARP消息响应送回主机A,该消息内含路由器的MAC地址
(5)A接到路由器响应后,将路由器的MAC IP存入ARP缓存。在成功解析出路由器MAC地址后,A可将该
ICMP数据包(或IP数据包)传送到路由器,然后路由器使用与A的MAC地址解析相同的ARP处理程序,来将
消息传给B

/////////////////////////////////////////////////////////////
ARP,全称Address Resolution Protocol,中文名为地址解析协议,它工作在数据链路层,在本层和硬件接口联系,同时对上层提供服务。

  IP数据包常通过以太网发送,以太网设备并不识别32位IP地址,它们是以48位以太网地址传输以太网数据包。因此,必须把IP目的地址转换 成以太网目的地址。在以太网中,一个主机要和另一个主机进行直接通信,必须要知道目标主机的MAC地址。但这个目标MAC地址是如何获得的呢?它就是通过 地址解析协议获得的。ARP协议用于将网络中的IP地址解析为的硬件地址(MAC地址),以保证通信的顺利进行。

ARP的工作原理如下: ──找寻要通信的机器的MAC(已知IP)

  1. 首先,每台主机都会在自己的ARP缓冲区 (ARP Cache)中建立一个 ARP列表,以表示IP地址和MAC地址的对应关系。

  2. 当源主机需要将一个数据包要发送到目的主机时,会首先检查自己 ARP列表中是否存在该 IP地址对应的MAC地址,如果有﹐就直接将数据包发送到这个MAC地址;如果没有,就向本地网段发起一个ARP请求的广播包,查询此目的主机对应的 MAC地址。此ARP请求数据包里包括源主机的IP地址、硬件地址、以及目的主机的IP地址。

  3. 网络中所有的主机收到这个ARP请求后,会检查数据包中的目的IP是否和自己的IP地址一致。如果不相同就忽略此数据包;如果相同,该主机首先将发送端的 MAC地址和IP地址添加到自己的ARP列表中,如果ARP表中已经存在该IP的信息,则将其覆盖,然后给源主机发送一个 ARP响应数据包,告诉对方自己是它需要查找的MAC地址;

  4. 源主机收到这个ARP响应数据包后,将得到的目的主机的IP地址和MAC地址添加到自己的ARP列表中,并利用此信息开始数据的传输。如果源主机一直没有收到ARP响应数据包,表示ARP查询失败。
///////////////////////////////////////////////////////////////
三 IP和大多数网络服务一样,是个数据传送系统,也就是说信息在TCP/IP网络中用IP传送前,必须将它分成大小相同的单位──数据报(Datagram)
IP运行路由(routing)的功能,选择一条最佳路径来传送数据
IP数据包有两部分组成,表头和数据。数据包括数据报表头和数据报数据部分。



般来说,ICMP报文提供针对网络层的错误诊断、拥塞控制、路径控制和查询服务四项大的功能。如,当一个分组无法到达目的站点或TTL超时后,路由器就会丢弃此分组,并向源站点返回一个目的站点不可到达的ICMP报文。
ICMP报文大体可以分为两种类型,即ICMP差错报文和ICMP询问报文

四、修改Linux内核默认文件描述符最大同时打开数量

修改内核参数 /proc/sys/fs/file-max

源代码文件为
file-max <kernel-path>;/fs/file.c
inode-nr <kernel-path>;/fs/innode.c

如果系统不是精简的内核可以用:以下方法修改
ulimit -n  <可以同时打开的文件数>;  设置用户可以同时打开的最大文件数(max open files)

     # echo "65536"  >; /proc/sys/fs/file-max  # 适用于 2.2 和 2.4 版内核
     # echo "131072" >; /proc/sys/fs/inode-max # 仅适用于 2.2 版内核
或将下列内容放入 /etc/sysctl.conf,做永久性的更改:

Securing and Optimizing Linux: RedHat Edition -A Hands on Guide
Prev Chapter 6. Linux General Optimization Next

--------------------------------------------------------------------------------

6.9. The file-max parameter
The file-max file /proc/sys/fs/file-max sets the maximum number of file-handles that the Linux kernel will allocate. We generally tune this file to improve the number of open files by increasing the value of /proc/sys/fs/file-max to something reasonable like 256 for every 4M of RAM we have: i.e. for a machine with 128 MB of RAM, set it to 8192 - 128/4=32 32*256=8192.

The default setup for the file-max parameter under Red Hat Linux is: "4096" To adjust the value of file-max to 128 MB of RAM, type the following on your terminal:



          [root@deep] /# echo "8192" >;/proc/sys/fs/file-max
         

Add the above commands to the /etc/rc.d/rc.local script file and you'll not have to type it again the next time your server reboots.




Edit the /etc/sysctl.conf file and add the following line:           # Improve the number of open files
          fs.file-max = 8192
         

You must restart your network for the change to take effect. The command to manually restart the network is the following:           [root@deep] /# /etc/rc.d/init.d/network restart
         


Setting network parameters [ OK ] Bringing up interface lo [ OK ] Bringing up interface eth0 [ OK ] Bringing up interface eth1 [ OK ]


: When you regularly receive from your server a lot of messages with errors about running out of open files, you might want to raise this limit. The default value is 4096. A file server or web server needs a lot of open files.


--------------------------------------------------------------------------------
Prev Home Next
The /etc/nsswitch.conf file Up The ulimit parameter


看这里:

[url]http://www.faqs.org/docs/securing/chap6sec72.html[/url]

fcitx和lumqq安装时遇到的小问题

1. RedHat9添加Fcitx输入法

版本:fcitx-3.0.2-1.i386.rpm
 
rpm -ivh fcitx-3.0.2-1.i386.rpm,OK安装完毕
 
fcitx缺省注册的XIM名为fcitx,但如果fcitx启动时XMODIFIERS已经设置好,fcitx会自动以系统的设置来注册合适的名字。因此,对于新安装的Mandrake和RedHat,最简单的方法是执行以下命令:
cd /usr/bin
ln -sf fcitx chinput

出现问题:can't open chinese punc file:/usr/share/fcitx/data/punc.mb
please set xmodifiers..

解决:
目录/usr/share/fcitx 的权限有问题,执行以下命令即可解决问题
su - root
chmod 755 /usr/share/fcitx
2 安装lumqq时,不能登录,
原因 :防火墙 默认等级过高
解决: gnome-lokkit来调用防火墙配置

补充:
火墙规则写入 /etc/sysconfig/iptables 文件,并通过启动 iptables 服务来启动防火墙。

警告:如果你配置了防火墙,或在 /etc/sysconfig/iptables 文件中配置了防火墙规则,你若选择了 「Disable Firewall」 并点击 「结束」 来保存所做改变,这些防火墙规则就会被删除。

我们强烈建议你从机器而不是远程 X 会话中运行 GNOME Lokkit 。如果你禁用了到你的机器的远程访问,你将无法再进入系统来禁用防火墙规则。

如果你不想写入防火墙规则,点击 「取消」

邮件转发

邮件转发(mail relay)是允许其它系统通过它来发寄电子邮件的系统。如果你的系统是一个邮件转发站,某些人便可能用它来通过你的机器散发垃圾邮件。

如果你选定要启用邮件服务,在 「Activate Firewall」 页上点击 「结束」 后,你会被提示是否检查邮件转发。如果你回答了 「Yes」 来检查邮件转发, GNOME Lokkit 就会试图连接 Mail Abuse Prevention System 网站( http://www.mail-abuse.org/ ),并运行邮件转发测试程序。测试结果会在结束后显示。如果你的系统向邮件转发开放,强烈推荐你配置 Sendmail 来避免它的发生。 

激活 iptables 服务

防火墙规则只有在 iptables 服务运行的时候才能被激活。要手工启动服务,使用以下命令:

/sbin/service iptables restart

要确保它在系统引导时启动,使用以下命令:

/sbin/chkconfig --level 345 iptables on

ipchains 服务不能和 iptables 服务同时运行。要确定 ipchains 服务被禁用,执行以下命令:

/sbin/chkconfig --level 345 ipchains off

你还可以使用 服务配置工具 来激活 iptables 和 ipchains 服务,详情请参阅 第 14.3 节


December 25

Linux inode cache机制分析(2)

1.4 icache中的inode对象存取接口——iget/iput

1.4.1 iget()——引用一个inode对象
其他内核模块要想访问一个inode对象,必须通过iget()访问接口。该函数会首先在icache的哈希链表中查找相应的inode对象,如果找到,则将该对象的引用计数加1,然后返回该inode对象的指针。如果没有找到,则通过调用get_new_inode()函数分配一个新的inode对象。该函数的源代码如下所示(include/linux/fs.h):
static inline struct inode *iget(struct super_block *sb, unsigned long ino)
{
return iget4(sb, ino, NULL, NULL);
}
可以看出,实际的工作是由iget4()函数(带有4个参数的iget函数,所以叫iget4)来完成的,其源码如下(inode.c):
struct inode *iget4(struct super_block *sb, unsigned long ino, find_inode_t find_actor, void *opaque)
{
struct list_head * head = inode_hashtable + hash(sb,ino);
struct inode * inode;

spin_lock(&inode_lock);
inode = find_inode(sb, ino, head, find_actor, opaque);
if (inode) {
__iget(inode);
spin_unlock(&inode_lock);
wait_on_inode(inode);
return inode;
}
spin_unlock(&inode_lock);

/*
* get_new_inode() will do the right thing, re-trying the search
* in case it had to block at any point.
*/
return get_new_inode(sb, ino, head, find_actor, opaque);
}
NOTE:
(1)首先,通过散列函数hash找到该inode对象应该在那个哈希链表中,然后调用find_inode()函数在该哈希链表中查找是否存在该inode对象。。
(2)如果在哈希链表中找到了相应的inode对象(由超级块对象指针sb和索引节点号ino唯一确定),则先调用__iget()函数增加该inode对象的引用计数。然后调用wait_on_inode()函数等待该inode对象被其他内核模块解锁。最后,直接返回这个inode对象的指针。
(3)如果没有找到,则调用get_new_inode()函数分配一个新的inode对象。
内联函数__iget()用来增加一个inode对象的引用计数。该函数首先判断inode对象的I_count的当前值。如果它非0,则将I_count加1后就直接返回。如果它为0,则先将I_count加1,然后就看看这个inode对象当前是否为脏,如果为脏(I_state&I_DIRTY非0),那就什么也不做,让该inode对象继续待在超级块对象的s_dirty链表中。如果不为脏,则将该inode对象从原来的“类型”链表(应该在inode_unused链表中)中删除,并将其连入到inode_in_use链表中。最后将icache统计信息中的未使用inode个数减1。
static inline void __iget(struct inode * inode)
{
if (atomic_read(&inode->i_count)) {
atomic_inc(&inode->i_count);
return;
}
atomic_inc(&inode->i_count);
if (!(inode->i_state & I_DIRTY)) {
list_del(&inode->i_list);
list_add(&inode->i_list, &inode_in_use);
}
inodes_stat.nr_unused--;
}
wait_on_inode()函数测试一个inode对象是否已经被加锁,如果是,则调用__wait_on_inode()函数等待该inode被解锁。否则就直接返回:
static inline void wait_on_inode(struct inode *inode)
{
if (inode->i_state & I_LOCK)
__wait_on_inode(inode);
}
get_new_inode()函数用于得到一个新的inode对象。该函数首先调用alloc_inode宏从inode_cachep这个slab分配器缓存中分配一个新的inode对象。如下所示:
static struct inode * get_new_inode(struct super_block *sb, unsigned long ino, struct list_head *head, find_inode_t find_actor, void *opaque)
{
struct inode * inode;

inode = alloc_inode();
if (inode) {
struct inode * old;

spin_lock(&inode_lock);
/* We released the lock, so.. */
old = find_inode(sb, ino, head, find_actor, opaque);
if (!old) {
inodes_stat.nr_inodes++;
list_add(&inode->i_list, &inode_in_use);
list_add(&inode->i_hash, head);
inode->i_sb = sb;
inode->i_dev = sb->s_dev;
inode->i_ino = ino;
inode->i_flags = 0;
atomic_set(&inode->i_count, 1);
inode->i_state = I_LOCK;
spin_unlock(&inode_lock);

clean_inode(inode);
sb->s_op->read_inode(inode);

/*
* This is special! We do not need the spinlock
* when clearing I_LOCK, because we're guaranteed
* that nobody else tries to do anything about the
* state of the inode when it is locked, as we
* just created it (so there can be no old holders
* that haven't tested I_LOCK).
*/
inode->i_state &= ~I_LOCK;
wake_up(&inode->i_wait);

return inode;
}

/*
* Uhhuh, somebody else created the same inode under
* us. Use the old inode instead of the one we just
* allocated.
*/
__iget(old);
spin_unlock(&inode_lock);
destroy_inode(inode);
inode = old;
wait_on_inode(inode);
}
return inode;
}

(1)由于在调用get_new_inode函数时,调用者已经释放了inode_lock锁,因此在inode_lock被释放到调用get_new_inode函数期间,其他内核模块有可能已经创建了(sb,ino)所确定的索引节点。所以,get_new_inode函数必须重新调用find_inode函数,以再一次在哈希链表中查找是否已存在相应的inode对象。
(2)如果find_inode()返回一个有效的指针,则说明其它模块已经创建了(sb,ino)这个inode对象,因此就要调用destroy_inode()函数来销毁一开始创建的inode对象,然后调用__iget()函数增加所找到的inode对象的引用计数,然后用wait_on_inode()函数等待他被解锁。
(3)如果find_inode()返回NULL,则对先前所分配的inode对象进行初始化。其中,要调用clean_inode()函数和超级块的s_op->read_inode()方法,以从块设备上读取磁盘索引节点的内容。最后,返回所分配的inode对象的指针。

1.4.2 iput()函数——释放对一个inode对象的引用
当其他内核对象或模块不再需要一个inode对象时,必须通过iput()函数,来解除对该inode对象的引用。
iput()函数将inode对象的引用计数减1。如果减到了0,则将该inode释放。否则就直接返回。
/**
* iput - put an inode
* @inode: inode to put
*
* Puts an inode, dropping its usage count. If the inode use count hits
* zero the inode is also then freed and may be destroyed.
*/

void iput(struct inode *inode)
{
if (inode) {
struct super_operations *op = NULL;

if (inode->i_sb && inode->i_sb->s_op)
op = inode->i_sb->s_op;
if (op && op->put_inode)
op->put_inode(inode);

if (!atomic_dec_and_lock(&inode->i_count, &inode_lock))
return;

if (!inode->i_nlink) {
list_del(&inode->i_hash);
INIT_LIST_HEAD(&inode->i_hash);
list_del(&inode->i_list);
INIT_LIST_HEAD(&inode->i_list);
inode->i_state|=I_FREEING;
inodes_stat.nr_inodes--;
spin_unlock(&inode_lock);

if (inode->i_data.nrpages)
truncate_inode_pages(&inode->i_data, 0);

if (op && op->delete_inode) {
void (*delete)(struct inode *) = op->delete_inode;
/* s_op->delete_inode internally recalls clear_inode() */
delete(inode);
} else
clear_inode(inode);
if (inode->i_state != I_CLEAR)
BUG();
} else {
if (!list_empty(&inode->i_hash)) {
if (!(inode->i_state & I_DIRTY)) {
list_del(&inode->i_list);
list_add(&inode->i_list,
&inode_unused);
}
inodes_stat.nr_unused++;
spin_unlock(&inode_lock);
return;
} else {
/* magic nfs path */
list_del(&inode->i_list);
INIT_LIST_HEAD(&inode->i_list);
inode->i_state|=I_FREEING;
inodes_stat.nr_inodes--;
spin_unlock(&inode_lock);
clear_inode(inode);
}
}
destroy_inode(inode);
}
}
对该函数的注释如下:
(1)函数首先调用超级块对象中的s_op->put_inode()方法(如果有的话)来释放这个inode对象。
(2)通过atomic_dec_and_lock原子操作将I_count减1,并同时对inode_lock进行加锁。如果I_count在减1后还为非0值,则直接返回。否则就进行下面的处理。
(3)如果该inode的i_nlink值为0,则说明文件系统中已经没有任何文件链接到这个inode对象上。对于这种情况,iput()先将这个inode从其所属的哈希链表和“类型”链表中摘除。然后在其i_count中设置I_FREEING标志,表示正在释放这个inode对象。最后,看看是否定义了超级块对象方法s_op->delete_inode(),如果有则调用该方法删除相应的磁盘索引节点,如果未定义该方法,则调用clear_inode()函数来清除这个inode对象。最后,用destroy_inode()将这个内存索引节点释放给inode_cachep slab分配器缓存。
(4)如果该inode的i_nlink不为0,则说明虽然没有人引用这个inode对象,但fs中还有文件链接与这个inode对象相关联,因此这个inode对象有可能再次被引用。对于这种情况,iput()函数首先判断这个inode对象是否正连接在哈希链表中。如果是,则将这个inode对象放到inode_unused链表中(当然,前提是这个inode对象不在s_dirty链表中,如果他在s_dirty链表中,则让他继续待在s_dirty链表中),然后直接返回就可以了。如果不是,则这个inode对象已经不用继续留在icache中了(反正通过哈希链表也找不到他),因此将这个inode对象从其所属的“类型”链表中摘除,然后调用clear_inode()方法清除这个inode对象,最后调用destroy_indoe()将这个内存索引节点释放回inode_cachep slab分配器缓存。注意!这里不能调用超级块对象的delete_inode()方法来删除对应的磁盘索引节点,因为fs中还有文件链接与这个inode相关联。



Linux inode cache机制分析(1)

Linux inode cache机制实现在fs/inode.c文件中。

1.1.Inode的slab分配器缓存
索引节点缓存(inode cache,简称icache)机制的实现是以inode对象的slab分配器缓存为基础的,因此要从物理内存中申请或释放一个inode对象,都必须通过kmem_cache_alloc()函数和kmem_cache_free()函数来进行。
Inode对象的slab分配缓存由一个kmem_cache_t类型的指针变量inode_cachep来定义。这个slab分配器缓存是在inode cache的初始化函数inode_init()中通过kmem_cache_create()函数来创建的。
Linux在inode.c文件中又定义了两个封装函数,来实现从inode_cachep slab分配器缓存中分配一个inode对象或将一个不再使用的inode对象释放给slab分配器,如下所示:
#define alloc_inode() \
((struct inode *) kmem_cache_alloc(inode_cachep, SLAB_KERNEL))
static void destroy_inode(struct inode *inode)
{
if (!list_empty(&inode->i_dirty_buffers))
BUG();
kmem_cache_free(inode_cachep, (inode));
}

1.2 和inode对象相关的一些底层操作
源文件inode.c中实现了一些对inode对象的底层基本操作,如下:
(1)clean_inode()——初始化部分inode对象成员域
该函数用来将一个刚从inode_cachep slab分配器中分配得到的inode对象中的某些成员初始化为已知的值(通常为0),但是有一个例外,既链接数i_nlink被初始化为1。这是一个静态的静态内部函数,因此它只能被inode.c中的其他函数所调用,如:get_empty_inode()和get_new_inode()。
/*
* This just initializes the inode fields
* to known values before returning the inode..
*
* i_sb, i_ino, i_count, i_state and the lists have
* been initialized elsewhere..
*/
static void clean_inode(struct inode *inode)
{
static struct address_space_operations empty_aops;
static struct inode_operations empty_iops;
static struct file_operations empty_fops;
memset(&inode->u, 0, sizeof(inode->u));
inode->i_sock = 0;
inode->i_op = &empty_iops;
inode->i_fop = &empty_fops;
inode->i_nlink = 1; /* NOTE!i_nlink被初始化为1 */
atomic_set(&inode->i_writecount, 0);
inode->i_size = 0;
inode->i_generation = 0;
memset(&inode->i_dquot, 0, sizeof(inode->i_dquot));
inode->i_pipe = NULL;
inode->i_bdev = NULL;
inode->i_data.a_ops = &empty_aops;
inode->i_data.host = inode;
inode->i_mapping = &inode->i_data;
}
(2)get_empty_inode()——从slab分配器中分配一个空的inode对象
该函数通过调用alloc_inode宏从slab分配器中分配一个inode对象,然后把除了I_count引用计数和链接计数I_nlink之外的所有域都初始化为NULL(部分域的初始化通过调用clean_inode函数来完成),并将这个inode对象链入inode_in_use链表中。最后返回这个inode对象的指针,如下所示:
struct inode * get_empty_inode(void)
{
static unsigned long last_ino;
struct inode * inode;

inode = alloc_inode();
if (inode)
{
spin_lock(&inode_lock);
inodes_stat.nr_inodes++;
list_add(&inode->i_list, &inode_in_use);
inode->i_sb = NULL;
inode->i_dev = 0;
inode->i_ino = ++last_ino;
inode->i_flags = 0;
atomic_set(&inode->i_count, 1);
inode->i_state = 0;
spin_unlock(&inode_lock);
clean_inode(inode);
}
return inode;
}

Linux内核模块通常并不会调用这个函数来分配一个inode对象。那些想获取一个没有索引节点号的inode对象的内核模块(如网络层等),以及那些没有任何已知信息的fs,通常会用这个函数来获取一个新的inode对象。
(3) clear_inode()——清除一个inode对象中的内容
在调用destroy_inode()函数释放一个inode对象之前,通常调用该函数来清除该inode对象中内容,如:使inode引用的缓冲区无效、解除对其它对象的引用等。
/**
* clear_inode - clear an inode
* @inode: inode to clear
*
* This is called by the filesystem to tell us
* that the inode is no longer useful. We just
* terminate it with extreme prejudice.
*/
void clear_inode(struct inode *inode)
{
if (!list_empty(&inode->i_dirty_buffers))
invalidate_inode_buffers(inode);

if (inode->i_data.nrpages)
BUG();
if (!(inode->i_state & I_FREEING))
BUG();
if (inode->i_state & I_CLEAR)
BUG();
wait_on_inode(inode);
if (IS_QUOTAINIT(inode))
DQUOT_DROP(inode);
if (inode->i_sb && inode->i_sb->s_op && inode->i_sb->s_op->clear_inode)
inode->i_sb->s_op->clear_inode(inode);
if (inode->i_bdev) {
bdput(inode->i_bdev);
inode->i_bdev = NULL;
}
inode->i_state = I_CLEAR;
}

1.3 icache数据结构
Linux通过在inode_cachep slab分配器缓存之上定义各种双向链表来实现inode缓存机制,以便有效地管理内存inode对象。这些链表包括:正在使用的inode链表、未使用的inode链表、inode哈希链表和匿名inode的哈希链表,他们的定义如下:
static LIST_HEAD(inode_in_use);
static LIST_HEAD(inode_unused);
static struct list_head *inode_hashtable;
static LIST_HEAD(anon_hash_chain); /* for inodes with NULL i_sb */
此外,每个超级块对象super_block中还有一条被修改过的、且正在使用的inode双向链表s_dirty。
每一个inode对象都会存在于两个分离的双向链表中:
(1)一个就是inode哈希链表inode_hashtable,用来加快inode查找,每个inode对象都通过I_hash指针链入哈希链表中。
(2)另一个就是inode的“类型”链表:
l 如果I_count>0、I_nlink>0且该inode不脏,则这个inode就通过其I_list指针链入系统全局的inode_in_use双向链表。
l 如果I_count和I_nlink都大于0,但是这个inode为脏(既I_state域中设置了I_DIRTY标志),则这个inode通过I_list指针链入他所属的super_block对象的s_dirty链表。
l 如果I_count=0,则通过其I_list链入inode_unused链表。
对于那些不属于任何超级块对象(即I_sb=NULL)的匿名inode对象,则通过I_hash指针链入系统全局的匿名inode哈希链表anon_hash_chain。


1.3.1 对inode缓存链表的锁保护
Linux在inode.c中定义了自旋锁inode_lock,来实现对所有inode缓存链表的互斥访问。也即,任何访问任意一条inode缓存链表的代码段,都必须通过调用spin_lock()函数持有该自旋锁,并在结束访问后通过spin_unlock()释放该自旋锁。Inode_lock的定义如下:
Spinlock_t inode_lock=SPIN_LOCK_UNLOCKED;
NOTE!如果要改变一个正在使用的inode对象的I_state域,也必须先持有该自旋锁。

1.3.2 inode缓存的统计信息
全局变量inodes_stat定义了inode cache的统计信息,主要包括cache中的inode对象总数和其中未使用的inode个数,其定义如下:
struct {
int nr_inodes;
int nr_unused;
int dummy[5];
} inodes_stat;

1.3.3 inode哈希链表
inode哈希链表的主要用途是加快在icache中查找一个特定的inode对象。指针inode_hashtable指向一组哈希链表表头,所有哈希函数值(记为h)相同的inode对象都通过I_hash指针作为接口组成双向链表,并挂在inode_hashtable[h]这个哈希链表表头之后。所有哈希链表表头都放在一起组成一个数组,该数组的首地址由指针inode_hashtable所指向。
在Linux中,inode哈希链表表头数组是存放在2order个连续的物理页帧中的,其中,order≥1,且它的值与系统总的物理页帧数num_physpages的值相关。因此,哈希链表表头的个数为:2order*PAGE_SIZE/sizeof(struct list_head)。由于list_head结构类型的大小是8个字节(2个32位指针),因此:inode哈希链表表头的个数可以表示为:2(order+12-3)。
l 哈希链表的初始化
inode cache的初始化工作是由inode_init()函数来完成的,它主要完成两项工作:(1)inode哈希链表的初始化,包括为inode哈希链表表头数组分配物理内存等;(2)创建inode slab分配器缓存。该函数的源代码如下:
/*
* Initialize the hash tables.
*/
void __init inode_init(unsigned long mempages)
{
struct list_head *head;
unsigned long order;
unsigned int nr_hash;
int i;

/*计算order的值,但是我不知道为什么要这样计算?:) */
mempages >>= (14 - PAGE_SHIFT);
mempages *= sizeof(struct list_head);
for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
;

do {
unsigned long tmp;

nr_hash = (1UL << order) * PAGE_SIZE /
sizeof(struct list_head);
i_hash_mask = (nr_hash - 1);

tmp = nr_hash;
i_hash_shift = 0;
while ((tmp >>= 1UL) != 0UL)
i_hash_shift++;

inode_hashtable = (struct list_head *)
__get_free_pages(GFP_ATOMIC, order);
} while (inode_hashtable == NULL && --order >= 0);

printk("Inode-cache hash table entries: %d (order: %ld, %ld bytes)\n",
nr_hash, order, (PAGE_SIZE << order));

if (!inode_hashtable)
panic("Failed to allocate inode hash table\n");

head = inode_hashtable;
i = nr_hash;
do {
INIT_LIST_HEAD(head);
head++;
i--;
} while (i);

/* inode slab cache */
inode_cachep = kmem_cache_create("inode_cache", sizeof(struct inode),
0, SLAB_HWCACHE_ALIGN, init_once,
NULL);
if (!inode_cachep)
panic("cannot create inode slab cache");
}
 
函数注释如下:
(1)函数首先计算inode哈希链表表头数组所需的连续物理页帧数(最大可能的order值)。
(2)然后在do…while循环中,尝试分配2order个连续的物理页帧。如果分配失败,则将order减1,然后在重新开始分配。如果直到order=0(既1页)时还是分配失败(inode_hashtable=NULL),则退出do…while循环,并通过panic()函数终止内核初始化过程。
(3)上述每次do…while循环中,在分配物理内存之前,函数都会首先计算哈希链表表头数组的位掩码(I_hash_mask)和位数(I_hash_shift)。其中,位掩码I_hash_mask=nr_hash-1,nr_hash是inode哈西链表表头的个数。而I_hash_shift实际上就等于(order+12-3)。
I_hash_mask和I_hash_shift的定义如下:
#define I_HASHBITS i_hash_shift
#define I_HASHMASK i_hash_mask

static unsigned int i_hash_mask;
static unsigned int i_hash_shift;
(4)在成功分配物理内存之后,函数开始对inode哈希链表表头数组中的表头进行初始化,也即通过INIT_LIST_HEAD宏将每一个表头中的prev、next指针初始化为指向自己。
(5)最后,函数通过调用kmem_cache_create()函数创建inode对象的slab分配器缓存inode_cachep。
l 计算一个inode对象的哈希散列值
Linux唯一确定一个inode对象的值是二元组(设备号,索引节点号),而设备号与超级块对象是一一对应的,因此,哈希散列值计算函数hash以super_block对象和索引节点号I_ino为参数。如下:
static inline unsigned long hash(struct super_block *sb, unsigned long i_ino)
{
unsigned long tmp = i_ino | ((unsigned long) sb / L1_CACHE_BYTES);
tmp = tmp + (tmp >> I_HASHBITS) + (tmp >> I_HASHBITS*2);
return tmp & I_HASHMASK;
}
l 对inode哈希链表的操作函数
与inode哈希链表相关的操作函数有:insert_inode_hash()和remove_inode_hash(),以及find_inode()。
Insert_inode_hash()函数用于将一个未散列的inode对象插入到相应的索引节点哈希链表中:
void insert_inode_hash(struct inode *inode)
{
struct list_head *head = &anon_hash_chain;
if (inode->i_sb)
head = inode_hashtable + hash(inode->i_sb, inode->i_ino);
spin_lock(&inode_lock);
list_add(&inode->i_hash, head);
spin_unlock(&inode_lock);
}
remove_inode_hash()函数用于将一个inode对象从他所属的哈希链表中摘除:
void remove_inode_hash(struct inode *inode)
{
spin_lock(&inode_lock);
list_del(&inode->i_hash);
INIT_LIST_HEAD(&inode->i_hash);
spin_unlock(&inode_lock);
}
而find_inode()函数则用于在某个链表中查找由(sb,ino)唯一标识的inode对象,如下所示:
/*
* Called with the inode lock held.
* NOTE: we are not increasing the inode-refcount, you must call __iget()
* by hand after calling find_inode now! This simplifies iunique and won't
* add any additional branch in the common code.
*/
static struct inode * find_inode(struct super_block * sb, unsigned long ino, struct list_head *head, find_inode_t find_actor, void *opaque)
{
struct list_head *tmp;
struct inode * inode;

tmp = head;
for (;;) {
tmp = tmp->next;
inode = NULL;
if (tmp == head)
break;
inode = list_entry(tmp, struct inode, i_hash);
if (inode->i_ino != ino)
continue;
if (inode->i_sb != sb)
continue;
if (find_actor && !find_actor(inode, ino, opaque))
continue;
break;
}
return inode;
}
NOTE! 调用find_inode()函数时一定要持有inode_lock锁。


Ext2 文件系统的硬盘布局

本文主要讲述 Linux 上比较流行的 ext2 文件系统在硬盘分区上的详细布局情况。Ext2 文件系统加上日志支持的下一个版本是 ext3 文件系统,它和 ext2 文件系统在硬盘布局上是一样的,其差别仅仅是 ext3 文件系统在硬盘上多出了一个特殊的 inode(可以理解为一个特殊文件),用来记录文件系统的日志,也即所谓的 journal。由于本文并不讨论日志文件,所以本文的内容对于 ext2 和 ext3 都是适用的。
1 前言
本文的资料来源是 Linux 内核中 ext3 文件系统的源代码。为了便于读者查阅源代码,本文中一些关键的技术词汇都使用了内核源代码中所使用的英语单词,而没有使用相应的中文翻译。(这种方法是否恰当,还请读者朋友们指教。)
2 粗略的描述
对于 ext2 文件系统来说,硬盘分区首先被划分为一个个的 block,一个 ext2 文件系统上的每个 block 都是一样大小的,但是对于不同的 ext2 文件系统,block 的大小可以有区别。典型的 block 大小是 1024 bytes 或者 4096 bytes。这个大小在创建 ext2 文件系统的时候被决定,它可以由系统管理员指定,也可以由文件系统的创建程序根据硬盘分区的大小,自动选择一个较合理的值。这些 blocks 被聚在一起分成几个大的 block group。每个 block group 中有多少个 block 是固定的。
每个 block group 都相对应一个 group descriptor,这些 group descriptor 被聚在一起放在硬盘分区的开头部分,跟在 super block 的后面。所谓 super block,我们下面还要讲到。在这个 descriptor 当中有几个重要的 block 指针。我们这里所说的 block 指针,就是指硬盘分区上的 block 号数,比如,指针的值为 0,我们就说它是指向硬盘分区上的 block 0;指针的值为 1023,我们就说它是指向硬盘分区上的 block 1023。我们注意到,一个硬盘分区上的 block 计数是从 0 开始的,并且这个计数对于这个硬盘分区来说是全局性质的

在 block group 的 group descriptor 中,其中有一个 block 指针指向这个 block group 的 block bitmap,block bitmap 中的每个 bit 表示一个 block,如果该 bit 为 0,表示该 block 中有数据,如果 bit 为 1,则表示该 block 是空闲的。注意,这个 block bitmap 本身也正好只有一个 block 那么大小。假设 block 大小为 S bytes,那么 block bitmap 当中只能记载 8*S 个 block 的情况(因为一个 byte 等于 8 个 bits,而一个 bit 对应一个 block)。这也就是说,一个 block group 最多只能有 8*S*S bytes 这么大。
在 block group 的 group descriptor 中另有一个 block 指针指向 inode bitmap,这个 bitmap 同样也是正好有一个 block 那么大,里面的每一个 bit 相对应一个 inode。硬盘上的一个 inode 大体上相对应于文件系统上的一个文件或者目录。关于 inode,我们下面还要进一步讲到。
在 block group 的 descriptor 中另一个重要的 block 指针,是指向所谓的 inode table。这个 inode table 就不止一个 block 那么大了。这个 inode table 就是这个 block group 中所聚集到的全部 inode 放在一起形成的。
一个 inode 当中记载的最关键的信息,是这个 inode 中的用户数据存放在什么地方。我们在前面提到,一个 inode 大体上相对应于文件系统中的一个文件,那么用户文件的内容存放在什么地方,这就是一个 inode 要回答的问题。一个 inode 通过提供一系列的 block 指针,来回答这个问题。这些 block 指针指向的 block,里面就存放了用户文件的内容。
2.1 回顾
现在我们回顾一下。硬盘分区首先被分为好多个 block。这些 block 聚在一起,被分成几组,也就是 block group。每个 block group 都有一个 group descriptor。所有这些 descriptor 被聚在一起,放在硬盘分区的开头部分,跟在 super block 的后面。从 group descriptor 我们可以通过 block 指针,找到这个 block group 的 inode table 和 block bitmap 等等。从 inode table 里面,我们就可以看到一个个的 inode 了。从一个 inode,我们通过它里面的 block 指针,就可以进而找到存放用户数据的那些 block。我们还要提一下,block 指针不是可以到处乱指的。一个 block group 的 block bitmap 和 inode bitmap 以及 inode table,都依次存放在这个 block group 的开头部分,而那些存放用户数据的 block 就紧跟在它们的后面。一个 block group 结束后,另一个 block group 又跟着开始。
3 详细的布局情况
3.1 Super Block
所谓 ext2 文件系统的 super block,就是硬盘分区开头(开头的第一个 byte 是 byte 0)从 byte 1024 开始往后的一部分数据。由于 block size 最小是 1024 bytes,所以 super block 可能是在 block 1 中(此时 block 的大小正好是 1024 bytes),也可能是在 block 0 中。
硬盘分区上 ext3 文件系统的 super block 的详细情况如下。其中 __u32 是表示 unsigned 不带符号的 32 bits 的数据类型,其余类推。这是 Linux 内核中所用到的数据类型,如果是开发用户空间(user-space)的程序,可以根据具体计算机平台的情况,用 unsigned long 等等来代替。下面列表中关于 fragments 的部分可以忽略,Linux 上的 ext3 文件系统并没有实现 fragments 这个特性。另外要注意,ext3 文件系统在硬盘分区上的数据是按照 Intel 的 Little-endian 格式存放的(低地址存放低字节数据),如果是在 PC 以外的平台上开发 ext3 相关的程序,要特别注意这一点。如果只是在 PC 上做开发,倒不用特别注意。
struct ext3_super_block {
/*00*/ __u32 s_inodes_count;      /* inodes 计数 */
       __u32 s_blocks_count;      /* blocks 计数 */
       __u32 s_r_blocks_count;    /* 保留的 blocks 计数 */
       __u32 s_free_blocks_count; /* 空闲的 blocks 计数 */
/*10*/ __u32 s_free_inodes_count; /* 空闲的 inodes 计数 */
       __u32 s_first_data_block;  /* 第一个数据 block */
       __u32 s_log_block_size;    /* block 的大小 */
       __s32 s_log_frag_size;     /* 可以忽略 */
/*20*/ __u32 s_blocks_per_group;  /* 每 block group 的 block 数量 */
       __u32 s_frags_per_group;   /* 可以忽略 */
       __u32 s_inodes_per_group;  /* 每 block group 的 inode 数量 */
       __u32 s_mtime;             /* Mount time */
/*30*/ __u32 s_wtime;             /* Write time */
       __u16 s_mnt_count;         /* Mount count */
       __s16 s_max_mnt_count;     /* Maximal mount count */
       __u16 s_magic;             /* Magic 签名 */
       __u16 s_state;             /* File system state */
       __u16 s_errors;            /* Behaviour when detecting errors */
       __u16 s_minor_rev_level;   /* minor revision level */
/*40*/ __u32 s_lastcheck;         /* time of last check */
       __u32 s_checkinterval;     /* max. time between checks */
       __u32 s_creator_os;        /* 可以忽略 */
       __u32 s_rev_level;         /* Revision level */
/*50*/ __u16 s_def_resuid;        /* Default uid for reserved blocks */
       __u16 s_def_resgid;        /* Default gid for reserved blocks */
       __u32 s_first_ino;         /* First non-reserved inode */
       __u16 s_inode_size;        /* size of inode structure */
       __u16 s_block_group_nr;    /* block group # of this superblock */
       __u32 s_feature_compat;    /* compatible feature set */
/*60*/ __u32 s_feature_incompat;  /* incompatible feature set */
       __u32 s_feature_ro_compat; /* readonly-compatible feature set */
/*68*/ __u8  s_uuid[16];          /* 128-bit uuid for volume */
/*78*/ char  s_volume_name[16];   /* volume name */
/*88*/ char  s_last_mounted[64];  /* directory where last mounted */
/*C8*/ __u32 s_algorithm_usage_bitmap; /* 可以忽略 */
       __u8  s_prealloc_blocks;        /* 可以忽略 */
       __u8  s_prealloc_dir_blocks;    /* 可以忽略 */
       __u16 s_padding1;               /* 可以忽略 */
/*D0*/ __u8  s_journal_uuid[16]; /* uuid of journal superblock */
/*E0*/ __u32 s_journal_inum;     /* 日志文件的 inode 号数 */
       __u32 s_journal_dev;      /* 日志文件的设备号 */
       __u32 s_last_orphan;      /* start of list of inodes to delete */
/*EC*/ __u32 s_reserved[197];    /* 可以忽略 */
};
我们可以看到,super block 一共有 1024 bytes 那么大。在 super block 中,我们第一个要关心的字段是 magic 签名,对于 ext2 和 ext3 文件系统来说,这个字段的值应该正好等于 0xEF53。如果不等的话,那么这个硬盘分区上肯定不是一个正常的 ext2 或 ext3 文件系统。从这里,我们也可以估计到,ext2 和 ext3 的兼容性一定是很强的,不然的话,Linux 内核的开发者应该会为 ext3 文件系统另选一个 magic 签名才对。
在 super block 中另一个重要的字段是 s_log_block_size。从这个字段,我们可以得出真正的 block 的大小。我们把真正 block 的大小记作 B,B = 1 << (s_log_block_size + 10),单位是 bytes。举例来说,如果这个字段是 0,那么 block 的大小就是 1024 bytes,这正好就是最小的 block 大小;如果这个字段是 2,那么 block 大小就是 4096 bytes。从这里我们就得到了 block 的大小这一非常重要的数据。
3.2 Group Descriptors
我们继续往下,看跟在 super block 后面的一堆 group descriptors。首先注意到 super block 是从 byte 1024 开始,一共有 1024 bytes 那么大。而 group descriptors 是从 super block 后面的第一个 block 开始。也就是说,如果 super block 是在 block 0,那么 group descriptors 就是从 block 1 开始;如果 super block 是在 block 1,那么 group descriptors 就是从 block 2 开始。因为 super block 一共只有 1024 bytes 那么大,所以不会超出一个 block 的边界。如果一个 block 正好是 1024 bytes 那么大的话,我们看到 group descriptors 就是紧跟在 super block 后面的了,没有留一点空隙。而如果一个 block 是 4096 bytes 那么大的话,那么在 group descriptors(从 byte 4096 开始)和 super block 的结尾之间,就有一定的空隙(4096 - 2048 bytes)。
那么硬盘分区上一共有多少个 block group,或者说一共有多少个 group descriptors,这我们要在 super block 中找答案。super block 中的 s_blocks_count 记录了硬盘分区上的 block 的总数,而 s_blocks_per_group 记录了每个 group 中有多少个 block。显然,文件系统上的 block groups 数量,我们把它记作 G,G = (s_blocks_count - s_first_data_block - 1) / s_blocks_per_group + 1。为什么要减去 s_first_data_block,因为 s_blocks_count 是硬盘分区上全部的 block 的数量,而在 s_first_data_block 之前的 block 是不归 block group 管的,所以当然要减去。最后为什么又要加一,这是因为尾巴上可能多出来一些 block,这些 block 我们要把它划在一个相对较小的 group 里面。
注意,硬盘分区上的所有这些 group descriptors 要能塞在一个 block 里面。也就是说 groups_count * descriptor_size 必须小于等于 block_size。
知道了硬盘分区上一共有多少个 block group,我们就可以把这么多个 group descriptors 读出来了。先来看看 group descriptor 是什么样子的。
struct ext3_group_desc
{
__u32 bg_block_bitmap;      /* block 指针指向 block bitmap */
__u32 bg_inode_bitmap;      /* block 指针指向 inode bitmap */
__u32 bg_inode_table;       /* block 指针指向 inodes table */
__u16 bg_free_blocks_count; /* 空闲的 blocks 计数 */
__u16 bg_free_inodes_count; /* 空闲的 inodes 计数 */
__u16 bg_used_dirs_count;   /* 目录计数 */
__u16 bg_pad;               /* 可以忽略 */
__u32 bg_reserved[3];       /* 可以忽略 */
};
每个 group descriptor 是 32 bytes 那么大。从上面,我们看到了三个关键的 block 指针,这三个关键的 block 指针,我们已经在前面都提到过了。
3.3 Inode
前面都准备好了以后,我们现在终于可以开始读取文件了。首先要读的,当然是文件系统的根目录。注意,这里所谓的根目录是相对于这一个文件系统或者说硬盘分区而言的,它并不一定是整个 Linux 操作系统上的根目录。这里的这个 root 目录存放在一个固定的 inode 中,这就是文件系统上的 inode 2。需要提到 inode 计数同 block 计数一样,也是全局性质的。这里需要特别注意的是,inode 计数是从 1 开始的,而前面我们提到过 block 计数是从 0 开始,这个不同在开发程序的时候要特别留心。(这一奇怪的 inode 计数方法,曾经让本文作者大伤脑筋。)
那么,我们先来看一下得到一个 inode 号数以后,怎样读取这个 inode 中的用户数据。在 super block 中有一个字段 s_inodes_per_group 记载了每个 block group 中有多少个 inode。用我们得到的 inode 号数除以 s_inodes_per_group,我们就知道了我们要的这个 inode 是在哪一个 block group 里面,这个除法的余数也告诉我们,我们要的这个 inode 是这个 block group 里面的第几个 inode;然后,我们可以先找到这个 block group 的 group descriptor,从这个 descriptor,我们找到这个 group 的 inode table,再从 inode table 找到我们要的第几个 inode,再以后,我们就可以开始读取 inode 中的用户数据了。(//没有必要这样,根据余数就读取其中数据不就行了吗??//)
个公式是这样的:block_group = (ino - 1) / s_inodes_per_group。这里 ino 就是我们的 inode 号数。而 offset = (ino - 1) % s_inodes_per_group,这个 offset 就指出了我们要的 inode 是这个 block group 里面的第几个 inode。

找到这个 inode 之后,我们来具体的看看 inode 是什么样的。
struct ext3_inode {
__u16 i_mode;    /* File mode */
__u16 i_uid;     /* Low 16 bits of Owner Uid */
__u32 i_size;    /* 文件大小,单位是 byte */
__u32 i_atime;   /* Access time */
__u32 i_ctime;   /* Creation time */
__u32 i_mtime;   /* Modification time */
__u32 i_dtime;   /* Deletion Time */
__u16 i_gid;     /* Low 16 bits of Group Id */
__u16 i_links_count;          /* Links count */
__u32 i_blocks;               /* blocks 计数 */
__u32 i_flags;                /* File flags */
__u32 l_i_reserved1;          /* 可以忽略 */
__u32 i_block[EXT3_N_BLOCKS]; /* 一组 block 指针 */
__u32 i_generation;           /* 可以忽略 */
__u32 i_file_acl;             /* 可以忽略 */
__u32 i_dir_acl;              /* 可以忽略 */
__u32 i_faddr;                /* 可以忽略 */
__u8  l_i_frag;               /* 可以忽略 */
__u8  l_i_fsize;              /* 可以忽略 */
__u16 i_pad1;                 /* 可以忽略 */
__u16 l_i_uid_high;           /* 可以忽略 */
__u16 l_i_gid_high;           /* 可以忽略 */
__u32 l_i_reserved2;          /* 可以忽略 */
};
我们看到在 inode 里面可以存放 EXT3_N_BLOCKS(= 15)这么多个 block 指针。用户数据就从这些 block 里面获得。15 个 blocks 不一定放得下全部的用户数据,在这里 ext3 文件系统采取了一种分层的结构。这组 15 个 block 指针的前 12 个是所谓的 direct blocks,里面直接存放的就是用户数据。第 13 个 block,也就是所谓的 indirect block,里面存放的全部是 block 指针,这些 block 指针指向的 block 才被用来存放用户数据。第 14 个 block 是所谓的 double indirect block,里面存放的全是 block 指针,这些 block 指针指向的 block 也被全部用来存放 block 指针,而这些 block 指针指向的 block,才被用来存放用户数据。15 个 block 是所谓的 triple indirect block,比上面说的 double indirect block 有多了一层 block 指针。作为练习,读者可以计算一下,这样的分层结构可以使一个 inode 中最多存放多少字节的用户数据。(计算所需的信息是否已经足够?还缺少哪一个关键数据?)
一个 inode 里面实际有多少个 block,这是由 inode 字段 i_size 再通过计算得到的。i_size 记录的是文件或者目录的实际大小,用它的值除以 block 的大小,就可以得出这个 inode 一共占有几个 block。注意上面的 i_blocks 字段,粗心的读者可能会以为是这一字段记录了一个 inode 中实际用到多少个 block,其实不是的。那么这一字段是干什么用的呢,读者朋友们可以借这个机会,体验一下阅读 Linux 内核源代码的乐趣。
3.4 文件系统的目录结构
现在我们已经可以读取 inode 的内容了,再往后,我们将要读取文件系统上文件和目录的内容。读取文件的内容,只要把相应的 inode 的内容全部读出来就行了;而目录只是一种固定格式的文件,这个文件按照固定的格式记录了目录中有哪些文件,以及它们的文件名,和 inode 号数等等。
struct ext3_dir_entry_2 {
__u32 inode;    /* Inode 号数 */
__u16 rec_len;  /* Directory entry length */
__u8  name_len; /* Name length */
__u8  file_type;
char  name[EXT3_NAME_LEN]; /* File name */
};
上面用到的 EXT3_NAME_LEN 是 255。注意,在硬盘分区上的 dir entry 不是固定长度的,每个 dir entry 的长度由上面的 rec_len 字段记录。
4 小结
有了以上的这些信息,我们就可以读取一个 ext3 文件系统的全部内容了。如果读者有 Windows 驱动程序开发的经验,从本文的信息,开发一个 Windows 下只读的 ext3 文件系统是可能的。但是要想又读又写,那还需要了解 Ext3 的日志文件的结构,而本文限于篇幅,并没有包括这方面的内容。