笑天 的个人资料笑天的共享空间日志列表 工具 帮助

日志


4月14日

高斯白噪声

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

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



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

  

1月2日

文件访问原语

文件访问原语
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  #把每一个字符都删除,不能当做整个字符串来处理

12月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。

12月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 节


12月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 的日志文件的结构,而本文限于篇幅,并没有包括这方面的内容。

12月24日

标准库 STL :Allocator能做什么?

Allocator是C++语言标准库中最神秘的部分之一。它们很少被显式使用,标准也没有明确出它们应该在什么时候被使用。今天的allocator与 最初的STL建议非常不同,在此过程中还存在着另外两个设计--这两个都依赖于语言的一些特性,而直到最近才在很少的几个编译器上可用。对 allocator的功能,标准似乎在一些方面追加了承诺,而在另外一些方面撤销了承诺。

这篇专栏文章将讨论你能用allocator来做什么以及如何定义一个自己的版本。我只会讨论C++标准所定义的allocator:引入准标准时代的设计,或试图绕过有缺陷的编译器,只会增加混乱。

1 什么时候不使用Allocator


C++标准中的Allocator分成两块:一个通用需求集(描述于§ 20.1.5(表 32)),和叫std::allocator的class(描述于§20.4.1)。如果一个class满足表32的需求,我们就称它为一个 allocator。std::allocator类满足那些需求,因此它是一个allocator。它是标准程序库中的唯一一个预先定义 allocator类。

每个 C++程序员都已经知道动态内存分配:写下new X来分配内存和创建一个X类型的新对象,写下delete p来销毁p所指的对象并归还其内存。你有理由认为allocator会使用new和delete--但它们没有。(C++标准将::operator new()描述为“allocation function”,但很奇怪,allocator并不是这样的。)

有关allocator的最重要的事实是它们只是为了一个目的:封装STL容器在内存管理上的低层细节。你不应该在自己的代码中直接调用 allocator 的成员函数,除非正在写一个自己的STL容器。你不应该试图使用allocator来实现operator new[];这不是allocator该做的。 如果你不确定是否需要使用allocator,那就不要用。

allocator 是一个类,有着叫allocate()和deallocate()成员函数(相当于malloc和free)。它还有用于维护所分配的内存的辅助函数和指 示如何使用这些内存的typedef(指针或引用类型的名字)。如果一个STL容器使用用户提供的allocator来分配它所需的所有内存(预定义的 STL容器全都能这么做;他们都有一个模板参数,其默认值是std::allocator),你就能通过提供自己的allocator来控制它的内存管 理。

这种柔性是有限制的:仍然由容器自己决定它将要申请多少内存以及如何使用它们。在容器申请更多的内存时,你能控制它调用那个低层函数,但是你不能通过使用 allocator来让一个vector行动起来像一个deque一样。虽然如此,有时候,这个受限的柔性也很有用。比如,假设你有一个特殊的 fast_allocator,能快速分配和释放内存(也许通过放弃线程安全性,或使用一个小的局部堆),你能通过写下std::list<T, fast_allocator<T> >而不是简单的std::list<T>来让标准的list使用它。

如果这看起来对你很陌生,那就对了。没有理由在常规代码中使用allocator的。

2 定义一个Allocator


关于allocator的这一点你已经看到了:它们是模板。Allocator,和容器一样,有value_type,而且allocator的 value_type必须要匹配于使用它的容器的value_type。这有时会比较丑陋:map的value_type相当复杂,所以显式调用 allocator的map看起来象这样的,std::map<K,V, fast_allocator<std::pair<const K, V> > >。(像往常一样,typedef会对此有帮助。)

以一个简单的例子开始。根据C++标准,std::allocator构建在::operator new()上。如果你正在使用一个自动化内存使用跟踪工具,让std::allocator更简单些会更方便。我们可以用malloc()代替:: operator new(),而且我们也不考虑(在好的std::allocator实作中可以找到的)复杂的性能优化措施。我们将这个简单的allocator叫作 malloc_allocator 。

既然malloc_allocator的内存管理很简单,我们就能将重点集中在所有STL的allocator所共有的样板上。首先,一些类型: allocator是一个类模板,它的实例专为某个类型T分配内存。我们提供了一序列的typedef,以描述该如何使用此类型的对象: value_type指T本身,其它的则是有各种修饰字的指针和引用。

    template <class T> class malloc_allocator

{

public:

typedef T value_type;

typedef value_type* pointer;

typedef const value_type* const_pointer;

typedef value_type& reference;

typedef const value_type& const_reference;

typedef std::size_t size_type;

typedef std::ptrdiff_t difference_type;

...

};
这些类型与STL容器中的很相似,这不是巧合:容器类常常直接从它的allocator提取这些类型。

为什么有这么多的typedef?你可能认为pointer是多余的:它就是value_type *。绝大部份时候这是对的,但你可能有时候想定义非传统的allocator,它的pointer是一个pointer-like的class,或非标的 厂商特定类型value_type __far *;allocator是为非标扩展提供的标准hook。不寻常的pointer类型也是存在address()成员函数的理由,它在 malloc_allocator中只是operator &()的另外一种写法:

    template <class T> class malloc_allocator
{
public:
pointer address(reference x) const { return &x; }
const_pointer address(const_reference x) const {
return &x;
}
...

};
现在我们能开始真正的工作:allocate()和deallocate()。它们很简单,但并不十分象malloc()和free()。我们传给 allocate()两个参数:我们正在为其分派空间的对象的数目(max_size返回可能成功的最大请求值),以及可选的一个地址值(可以被用作一个 位置提示)。象malloc_allocator这样的简单的allocator没有利用那个提示,但为高性能而设计的allocator可能会利用它。 返回值是一个指向内存块的指针,它足以容纳n个value_type类型的对象并有正确的对齐。

我们也传给deallocate()两个参数:当然一个是指针,但同样还有一个元素计数值。容器必须自己掌握大小信息;传给allocate和 deallocate的大小参数必须匹配。同样,这个额外的参数是为效率而存在的,而同样,malloc_allocator不使用它。

    template <class T> class malloc_allocator
{
public:
pointer allocate(size_type n, const_pointer = 0) {
void* p = std::malloc(n * sizeof(T));
if (!p)
throw std::bad_alloc();
return static_cast<pointer>(p);
}
void deallocate(pointer p, size_type) {
std::free(p);
}
size_type max_size() const {
return static_cast<size_type>(-1) / sizeof(value_type);
}
...
};
allocate ()和deallocate()成员函数处理的是未初始化的内存,它们不构造和销毁对象。语句a.allocate(1)更象malloc(sizeof (int))而不是new int。在使用从allocate()获得的内存前,你必须在这块内存上创建对象;在通过deallocate()归还内存前,你需要销毁那些对象。

C+ +语言提供一个机制以在特定的内存位置创建对象:placement new。如果你写下new(p) T(a, b),那么你正在调用T的构造函数产生一个新的对象,一如你写的new T(a, b)或 T t(a, b)。区别是当你写new(p) T(a, b),你指定了对象被创建的位置:p所指向的地址。(自然,p必须指向一块足够大的内存,而且必须是未被使用的内存;你不能在相同的地址构建两个不同的对 象。)。你也可以调用对象的析构函数,而不释放内存,只要写p->~T()。

这些特性很少被使用,因为通常内存的分配和初始化是一起进行的:使用未初始化的内存是不方便的和危险的。你需要如此低层的技巧的很少几处之一就是你在写一 个容器类,于是allocator将内存的分配与初始化解耦。成员函数construct()调用placement new,而且成员函数destory()调用析构函数。

    template <class T> class malloc_allocator
{
public:
void construct(pointer p, const value_type& x) {
new(p) value_type(x);
}
void destroy(pointer p) { p->~value_type(); }
...
};
(为什么allocator有那些成员函数,什么时候容器可以直接使用placement new?一个理由是要隐藏笨拙的语法,而另一个是如果写一个更复杂的allocator时你可能想在构造和销毁对象时construct()和 destroy()还有其它一些副作用。比如,allocator可能维护一个所有当前活动对象的日志。)

这些成员函数没有一个是static的,因此,容器在使用allocator前做的第一件事就是创建一个allocator对象--也就是说我们应该定义 一些构造函数。但是,我们不需要赋值运算:一旦容器创建了它的allocator,这个allocator就从没想过会被改变。表32中的对 allocator的需求没有包括赋值。只是基于安全,为了确保没人偶然使用了赋值运算,我们将禁止掉这个可能自动生成的函数。

    template <class T> class malloc_allocator
{
public:
malloc_allocator() {}
malloc_allocator(const malloc_allocator&) {}
~malloc_allocator() {}
private:
void operator=(const malloc_allocator&);
...
};
这些构造函数实际上没有做任何事,因为这个allocator不需要初始化任何成员变量。基于同样的理由,任意两个malloc_allocator都是 可互换的;如果a1和a2的类型都是malloc_allocator<int>,我们可以自由地通过a1来allocate()内存然后通 过 a2来deallocate()它。我们因此定义一个比较操作以表明所有的malloc_allocator对象是等价的:
    template <class T>
inline bool operator==(const malloc_allocator<T>&,
const malloc_allocator<T>&) {
return true;
}
tmplate <class T>
inline bool operator!=(const malloc_allocator<T>&,
const malloc_allocator<T>&) {
return false;
}
你会期望一个allocator,它的不同对象是不可替换的吗?当然--但很难提供一个简单而有用的例子。一种明显的可能性是内存池。它对大型的C程序很 常见,从几个不同的位置(“池”)分配内存,而不是什么东西都直接使用malloc()。这样做有几个好处,其一是it only takes a single function call to reclaim all of the memory associated with a particular phase of the program。使用内存池的程序可能定义诸如mempool_Alloc和mempool_Free这样的工具函数,mempol_Alloc(n, p)从池p中分配n个字节。很容易写出一个mmepool_alocator以匹配这样的架构:每个mempool_allocator对象有一个成员变 量以指明它绑定在哪个池上,而mempool_allocator::allocate()将调用mempool_Alloc()从相应的池中获取内存。 [注1]

最后,我们到了allocator的定义体中一个微妙的部份:在不同的类型之间映射。问题是,一个allocator类,比如 malloc_allocator<int>,全部是围绕着单个value_type构建的:malloc_allocator< int>::pointer是int*,malloc_allocator<int>().allocate(1)返回足够容纳一个 int对象的内存,等等。然而,通常,容器类使用malloc_allocator可能必须处理超过一个类型。比如,一个list类,不分配int对象; 实际上,它分配list node对象。(我们将在下一段落研究细节。)于是,当你创建一个std::list<int, malloc_allocator<int> >时,list必须将malloc_allocator<int>转变成为处理list_node类型的 malloc_allocator。

这个机制称为重绑定,它有二个部份。首先,对于给定的一个value_type是X1的allocator类型A1,你必须能够写出一个 allocator 类型A2,它与A1完全相同,除了value_type是X2。其次,对于给定的A1类型的对象a1,你必须能够创建一个等价的A2类型对象a2。这两部 分都使用了成员模板,这也就是allocator不能被老的编译器支持,或支持得很差的原因。

    template <class T> class malloc_allocator
{
public:
template <class X>
malloc_allocator(const malloc_allocator<X>&) {}
template <class X>
struct rebind { typedef malloc_allocator<X> other; };
...
};
这其实意味着一个allocator类不能仅仅是单个类;它必须是一族相关类,每个都有它自己的value_type。一个allocator类必须要有一个rebind成员,因为它使得从一个类变成同族的另外一个类成为可能。

如果有一个allocator类型A1,对应于另外一个value_type的类型是typename A1::template rebind<X2>::othere[注2]。正如你能将一个类型转换为另外一个,模板的转换用构造函数让你转换值:你可以写 malloc_allocator<int>(a),无论a的类型是malloc_allocator<int>,或 malloc_allocator<double>,或malloc_allocator<string>。象往常一样, malloc_allocator的转换用构造函数用不着做任何事,因为malloc_allocator没有成员变量。

附带一提,虽然绝大多数的allocator有一个模板参数(allocator的value_type),但这不是需求中的规定,只不过常常正巧如此。重绑定机制在多模板参数的allocator上也工作良好:

    template <class T, int flags> class my_allocator
{
public:
template <class U>
struct rebind { typedef my_allocator<U, flags> other; };
...
};
最后,最后一个细节:对于void我们该怎么做?有时一个容器必须涉及void的指针(再一次,我们将会在下一段落研究细节),而重绑定机制几乎给了我们 所需要的东西,但并不完全。它不能工作,因为我们会写出类似malloc_allocator<void>::pointer的代码,而我们 定义的malloc_allocator用void实例化时是非法的。它使用了sizeof(T),和涉及了T &;当T是void时,这两个都是非法的。解决的方法如同问题本身一样简单:为void特化malloc_allocator,扔掉其它一切,只 留下我们需要的void的指针。
    template<> class malloc_allocator<void>
{
typedef void value_type;
typedef void* pointer;
typedef const void* const_pointer;
template <class U>
struct rebind { typedef malloc_allocator<U> other; };
};

就是它了!malloc_allocator的完备源码见Listing 1。

3 使用Allocator


使用allocator的最简单方法,当然是将它们作为参数传给容器类;用

std::vector<char, malloc_allocator<char> > V;

取代简单的std::vector<char>,或用

typedef std::list<int, mempool_allocator<int> > List;

List L(mempool_allocator<int>(p));

取代简单的std::list<int>。

但是你能做得更多。STL的卖点是它是可扩展性:正如你能写自己的allocator,你也能写你自己的容器类。如果你很小心, 并且你写的容器类使用它的allocator来处理所有的内存相关操作,那么别人将能够加入他们自己的用户自定义allocator。

诸如std::vector和std::list这样的容器类是很复杂的,而且大部分复杂性与内存管理无关。让我们以一个简单的例子开始,这样我们可以只 关注于allocator。考虑一个固定大小数组的类,Array,元素的个数是在构造函数中设定的,并且在此之后不会改变。(这有点像std:: valarray的一个简化版本。)它有二个模板参数,元素类型和allocator类型。

容器,和allocator一样,以巢式类型申明开始:value_type, reference,const_reference,size_type,difference_type,iterator,和 const_iterator。通常,这些类型中的绝大部分都可以直接从它的allocator中获得--这也解释了为什么容器的value_type必 须和allocator中的相匹配。

当然,iterator类型通常不来自于allocator;通常iterator是一个类,完全取决于容器的内在表示。Array类比通常见到的容器简 单,因为它实际上将所有元素存储在单块连续内存中;我们只要维护指向内存块开始和结束处的两个指针。iterator就是指针。

在更进一步之前,我们必须决定:我们将怎样储存allocator?构造函数将接受一个allocator对象作为参数。我们必须在容器的整个生命期内保存它的一个拷贝,因为在析构函数中还需要它。

依感觉,这儿没什么问题:我们只要申明一个Allocator类型的成员变量,然后使用它。方法是正确的,但不爽。毕竟,在99%的时间里,用户都不想考 虑有关allocator的事;他们只会写Array<int>并使用默认值--而默认的allocator可能是一个没有任何非 static 成员变量的空类。问题是即使Allocator是一个空类,这样的成员变量也会有开销。(这是C++标准所要求的。) 我们的Array类将会有三个word的开销,而不是两个。也许一个word的额外开销不是大问题,但总是不爽,它迫使所有用户为一个几乎从不使用的功能 承担了开销。

都很多方法来解决这个问题,其中一些使用了traits类和偏特化。或许最简单的解决方法就是使用(私有)继承而不是成员变量。编译器被允许优化掉空基类,而且时下绝大多数的编译器都这么做了。

我们最终能写下定义的骨架了:

    template <class T, class Allocator = std::allocator<T> >

class Array : private Allocator

{

public:

typedef T value_type;



typedef typename Allocator::reference reference;

typedef typename Allocator::const_reference

const_reference;

typedef typename Allocator::size_type size_type;

typedef typename Allocator::difference_type

difference_type;

typedef typename Allocator::pointer iterator;

typedef typename Allocator::const_pointer const_iterator;

typedef Allocator allocator_type;

allocator_type get_allocator() const {

return static_cast<const Allocator&>(*this);

}

iterator begin() { return first; }

iterator end() { return last; }

const_iterator begin() const { return first; }

const_iterator end() const { return last; }

Array(size_type n = 0,

const T& x = T(),

const Allocator& a = Allocator());

Array(const Array&);

~Array();

Array& operator=(const Array&);

private:

typename Allocator::pointer first;

typename Allocator::pointer last;

};
如果要满足对容器的需求的话(需求全集见于C++标准§23.1,Table 65),这还不是我们所要的全部样板,但是绝大部分都和allocator完全无关。对于我们的目的而言,最感兴趣的成员函数是构造函数(它分配内存和创 建对象),和析构函数(它销毁内存并释放内存)。

构造函数初始化allocator基类,获得足够容纳n个元素的一块内存(如果我们正在写类似于vector的东西,我们可能申请更大些的内存以供增长 用),然后遍历内存以创建初始化值的拷贝。唯一的问题是异常安全:如果某一个元素的构造函数抛出了一个异常,我们必须撤销我们所做的一切。

    template <class T, class Allocator>

Array<T, Allocator>::Array(size_type n,

const T& x,

const Allocator& a)

: Allocator(a), first(0), last(0)

{

if (n != 0) {

first = Allocator::allocate(n);

size_type i;

try {

for (i = 0; i < n; ++i) {

Allocator::construct(first + i, x);

}

}

catch(...) {

for(size_type j = 0; j < i; ++j) {

Allocator::destroy(first + j);

}

Allocator::deallocate(first, n);

throw;

}

}

}
(你可能会问为什么我们手写了这个循环;std::uninitialized_fill()不是已经做我们所需要的东西?几乎,但不完全相同。我们必须 调用 allocator的构造成员函数而不是简单的pacement new。也许未来的C++标准将会包含一个接受allocator为参数的uninitialized_fill()函数,从而使得不再需要这个显式循 环。

析构函数比较简单,因为我们不需要担心异常安全:T的析构函数被假设为从不抛出异常。

    template <class T, class Allocator>

Array<T, Allocator>::~Array()

{

if (first != last) {

for (iterator i = first; i < last; ++i)

Allocator::destroy(i);

Allocator::deallocate(first, last - first);

}

}
我们这个简单的array类不需要使用重绑定或转换,但这只是因为Array<T, Allocator>绝不产生T类型以外的对象。当你定义更复杂的数据结构时,其它类型就出现了。比如,考虑一下value_type是T的链表类 list。链表通常是由节点组成的,每个节点含有一个T类型的对象和一个指向下个节点的指针。于是,作为最初的尝试,我们可能定义链表的节点为:
    template <class T>

struct List_node

{

T val;

List_node* next;

};
把一个新的值加入list的过程看起来可能是这样的:

l 使用一个value_type是List_node<T>的allocator,为一个新节点分配内存。 l 使用一个value_type是T的allocator,在节点的val位置上构建新的元素。 l 将这个节点连接到适当的位置。

这个过程需要处理两个不同的allocator,其中一个是通过对另一个的重绑定而获得的。它对几乎所有程序都工作得很好,即使是将allocator用 于相当复杂的目的的程序。它所不能完成的是向allocator提供一些不寻常的指针类型。它明显依赖于能使用List_node<T> *类型的普通指针。

如果你极端野心勃勃,想将其它可能的指针类型传给allocator,一切都突然变得复杂多了--从一个节点指向另一个节点的指针不再是 List_node<T> *或void *了,但它必须是能够从allocator获取的某个类型。直接实现是不太可能的:用一个不完全的类型实例化allocator是非法的,因此,除非 List_node已经被完整定义,否则无法谈论指向List_node的指针。我们需要一个精巧的申明顺序。

    template <class T, class Pointer>

struct List_node

{

T val;

Pointer next;

};

template <class T, class Alloc>

class List : private Alloc

{

private:

typedef typename Alloc::template rebind<void>::other

Void_alloc;

typedef typename Void_alloc::pointer Voidptr;

typedef typename List_node<T, Voidptr> Node;

typedef typename Alloc::template rebind<Node>::other

Node_alloc;

typedef typename Node_alloc::pointer Nodeptr;

typedef typename Alloc::template rebind<Voidptr>::other

Voidptr_alloc;

Nodeptr new_node(const T& x, Nodeptr next) {

Alloc a = get_allocator();

Nodeptr p = Node_alloc(a).allocate(1);

try {

a.construct(p->val, x);

}

catch(...) {

Node_alloc(a).deallocate(p, 1);

throw;

}

Voidptr_alloc(a).construct(p->next, Voidptr(next));

return p;

}

...

};
最后,以防你认为这么费劲才获得这么小的好处太不值了,提醒一下:仅仅因为你能写一个使用allocator的容器,并不意谓你必须,或你应该。有时你可 能写一个依赖于特殊的内存分配策略的容器类,比如复杂到基于磁盘的B树容器或简单到我的书中所描述的block类。即使你确实想写一个使用 allocator的容器类,你也不是必须支持可能的指针类型。你可以写一个容器,而要求所有用户自定义的allocator使用普通指针,并在文档中明 确说明这个限制。不是每件事都要完全通用。 展望未来

如果你想写一个如同malloc_allocator这样简单的allocator,应该没有困难。(前提是你正在使用一个比较现代的编译器)。然而,如果你的心比较大,--基于内存池的或支持非标指针类型的allocator--情况就比较不令人满意了。

如果你想使用可能的类指针(pointer-like)类型,它必须支持哪些操作?它必须有一个null值吗?如果是的话,那个值应该如何书写?你能使用 类型转换吗?你如何在类指针对象与普通指针间进行转换?你必须要考虑操作指针时抛的异常吗?我在这最后一节提出了一些假设;C++标准没有指明这些假设的 对错。这些细节都留给了具体的标准库的实现,即使某个实现完全忽略可选指针类型也是合法的。C++标准还遗留了一些没有答案的问题,比如当一个 allocator的不同实例不可互换时,将发生什么。

幸运的是,情形并不象标准(§ 20.1.5,第4-5段)中的词汇所描述得那么可怕。标准留下没有答案的问题,是因为在制订标准时,C++标准化委员会对答案达不成共识;对 allocator的必要的经验还不存在。每个参与制订的人都认为这是一个临时的补丁,其中的含糊肯定将在将来的修订中被去除。

等一下,如果你关心可移植性,最好还是远离可选的指针类型,而,如果你乐意接受一些限制,就能安全地使用诸如mempool_allocator这样不同 对象实体间差别很大的allocator。所有主流标准库的实现现在都在某个方面不支持这样的allocator,而且不同实现间的差别不大。

正如容器接受一个allocator作为模板参数,容器的构造函数也接受一个allocator作为参数。容器保留这个参数的一份拷贝,并使用这个拷贝来处理所有的内存管理;容器的allocator一旦在构造函数中初始化完成,就终生不变。

唯一的问题是当你运行一个需要两个容器在内存管理上进行协同的操作时,会发生什么。在标准库中确实存在两个这样的操作:swap()(所有容器)和std::list::splice()。原理上,可以以这样几个不同的方式处理他们:

l 禁止在两个allocator不等价的容器间进行swap()和splice()。 l 在swap()和splice()中放入一个allocator等价性的测试。如果不等价,降格调用copy()和赋值运算。 l 只提供swap():如同对容器中的数据一样,交换它们的allocator。(很难找出如何将它推广到splice上.它同样也带来一个问题:如何swap没有定义赋值运算符的东西?)

如果你能避免对可能具有不同allocator的容器使用swap()和splice(),一切都很安全。在实践中,我没有发现这会造成严重束缚:你需要严格练习安全使用诸如内存池这类特性,而你或许并不想不加选择地混用使用不同allocator的容器。

部分因为不熟悉,部分因为C++标准的要求并不令人满意,目前对allocator的绝大多数的使用都很简单。由于C++社群对allocator变得越来越熟悉,并且标准已被阐明,我们能期待更复杂的使用将会浮现。 Listing 1: A sample allocator based on malloc

template <class T> class malloc_allocator

{

public:

typedef T value_type;

typedef value_type* pointer;

typedef const value_type* const_pointer;

typedef value_type& reference;

typedef const value_type& const_reference;

typedef std::size_t size_type;

typedef std::ptrdiff_t difference_type;



template <class U>

struct rebind { typedef malloc_allocator<U> other; };



malloc_allocator() {}

malloc_allocator(const malloc_allocator&) {}

template <class U>

malloc_allocator(const malloc_allocator<U>&) {}

~malloc_allocator() {}



pointer address(reference x) const { return &x; }

const_pointer address(const_reference x) const {

return x;

}



pointer allocate(size_type n, const_pointer = 0) {

void* p = std::malloc(n * sizeof(T));

if (!p)

throw std::bad_alloc();

return static_cast<pointer>(p);

}



void deallocate(pointer p, size_type) { std::free(p); }



size_type max_size() const {

return static_cast<size_type>(-1) / sizeof(T);

}



void construct(pointer p, const value_type& x) {

new(p) value_type(x);

}

void destroy(pointer p) { p->~value_type(); }



private:

void operator=(const malloc_allocator&);

};



template<> class malloc_allocator<void>

{

typedef void value_type;

typedef void* pointer;

typedef const void* const_pointer;



template <class U>

struct rebind { typedef malloc_allocator<U> other; };

};





template <class T>

inline bool operator==(const malloc_allocator<T>&,

const malloc_allocator<T>&) {

return true;

}



template <class T>

inline bool operator!=(const malloc_allocator<T>&,

const malloc_allocator<T>&) {

return false;

}
12月23日

Linux操作系统的内核编译内幕详解

内核,是一个操作系统的核心。它负责管理系统的进程、内存、设备驱动程序、文件和网络系统,决定着系统的性能和稳定性。

  Linux的一个重要的特点就是其源代码的公开性,所有的内核源程序都可以在/usr/src/linux下找到,大部分应用软件也都是遵循GPL而设计的,你都可以获取相应的源程序代码。

  全世界任何一个软件工程师都可以将自己认为优秀的代码加入到其中,由此引发的一个明显的好处就是Linux修补漏洞的快速以及对最新软件技术的利用。而Linux的内核则是这些特点的最直接的代表。

  想象一下,拥有了内核的源程序对你来说意味着什么?首先,我们可以了解系统是如何工作的。通过通读源代码,我们就可以了解系统的工作原理,这在Windows下简直是天方夜谭。其次,我们可以针对自己的情况,量体裁衣,定制适合自己的系统,这样就需要重新编译内核。

  在Windows下是什么情况呢?相信很多人都被越来越庞大的Windows整得莫名其妙过。再次,我们可以对内核进行修改,以符合自己的需要。这意味着什么?没错,相当于自己开发了一个操作系统,但是大部分的工作已经做好了,你所要做的就是要增加并实现自己需要的功能。在Windows下,除非你是微软的核心技术人员,否则就不用痴心妄想了。

  内核版本号

  由于Linux的源程序是完全公开的,任何人只要遵循GPL,就可以对内核加以修改并发布给他人使用。Linux的开发采用的是集市模型(bazaar,与cathedral--教堂模型--对应),为了确保这些无序的开发过程能够有序地进行,Linux采用了双树系统。

  一个树是稳定树(stable tree),另一个树是非稳定树(unstable tree)或者开发树(development tree)。一些新特性、实验性改进等都将首先在开发树中进行。如果在开发树中所做的改进也可以应用于稳定树,那么在开发树中经过测试以后,在稳定树中将进行相同的改进。一旦开发树经过了足够的发展,开发树就会成为新的稳定树。

  开发数就体现在源程序的版本号中;源程序版本号的形式为x.y.z:对于稳定树来说,y是偶数;对于开发树来说,y比相应的稳定树大一(因此,是奇数)。到目前为止,稳定树的最高版本是2.2.16,最新发布的Redhat7.0所采用的就是2.2.16的内核;开发树的最新版本是2.3.99。也许你已经发现和多网站上都有2.4.0-test9-pre7之类的内核,但是这并不是正式版本。内核版本的更新可以访问http://www.kernel.org。

  为什么重新编译内核

  Linux作为一个自由软件,在广大爱好者的支持下,内核版本不断更新。新的内核修订了旧内核的bug,并增加了许多新的特性。如果用户想要使用这些新特性,或想根据自己的系统度身定制一个更高效,更稳定的内核,就需要重新编译内核。

  通常,更新的内核会支持更多的硬件,具备更好的进程管理能力,运行速度更快、 更稳定,并且一般会修复老版本中发现的许多漏洞等,经常性地选择升级更新的系统内核是Linux使用者的必要操作内容。

  为了正确的合理地设置内核编译配置选项,从而只编译系统需要的功能的代码,一般主要有下面四个考虑:

  自己定制编译的内核运行更快(具有更少的代码)

  系统将拥有更多的内存(内核部分将不会被交换到虚拟内存中)

  不需要的功能编译进入内核可能会增加被系统攻击者利用的漏洞

  将某种功能编译为模块方式会比编译到内核内的方式速度要慢一些


内核编译模式

  要增加对某部分功能的支持,比如网络之类,可以把相应部分编译到内核中(build-in),也可以把该部分编译成模块(module),动态调用。

  如果编译到内核中,在内核启动时就可以自动支持相应部分的功能,这样的优点是方便、速度快,机器一启动,你就可以使用这部分功能了;缺点是会使内核变得庞大起来,不管你是否需要这部分功能,它都会存在,这就是Windows惯用的招数,建议经常使用的部分直接编译到内核中,比如网卡。

  如果编译成模块,就会生成对应的.o文件,在使用的时候可以动态加载,优点是不会使内核过分庞大,缺点是你得自己来调用这些模块。

  内核编译详解

  新版本内核的获取和更新

  Linux内核版本发布的官方网站是http://www.kernel.org,国内各大ftp上一般都可以找到某些版本的内核。新版本的内核的发布有两种形式,一种是完整的内核版本,另外一种是patch文件,即补丁。

  完整的内核版本比较大,比如linux-2.4.0-test8.tar.bz2就有18M之多,网速快的用户可以下载使用。完整内核版本一般是.tar.gz(.tgz)文件或者是.bz2文件,二者分别是使用gzip或者bzip2进行压缩的文件,使用时需要解压缩。

  patch文件则比较小,一般只有几十K到几百K,极少的会超过1M,网速慢的用户可以使用patch文件来升级内核。但是patch文件是针对于特定的版本的,你需要找到自己对应的版本才能使用。

  编译内核需要root权限,以下操作都假定你是root用户。请把你需要升级的内核拷贝到/usr/src/下(下文中以2.4.0test8的内核的linux-2.4.0test8.tar.gz为例),命令为

#cp linux-2.4.0test8.tar.gz /usr/src

  让我们先来查看一下当前/usr/src的内容,注意到有一个linux的符号链接,它指向一个类似于linux-2.2.14(对应于你现在使用的内核版本号)的目录。首先删除这个链接:

#cd /usr/src
#rm -f linux

  现在解压我们下载的源程序文件。如果所下载的是.tar.gz(.tgz)文件,请使用下面的命令:

#tar -xzvf linux-2.4.0test8.tar.gz

  如果你所下载的是.bz2文件,例如linux-2.4.0test8.tar.bz2,请使用下面的命令

#bzip2 -d linux-2.4.0test8.tar.bz2
#tar -xvf linux.2.4.0.test8.tar

  现在让我们再来看一下/usr/src下的内容,你会发现现在有了一个名为linux的目录,里面就是我们需要升级到的版本的内核的源程序。还记得那个名为linux的链接么?之所以使用那个链接就是防止在升级内核的时候会不慎把原来版本内核的源程序给覆盖掉了。我们也需要同样处理:

#mv linux linux-2.4.0test8
#ln -s linux-2.4.0test8 linux

  这样我们也有了一个名为linux的符号链接,就不用担心以后会把它覆盖掉了(也许你会觉得重新建立linux的符号链接没有必要,但实际上这是必不可少的,下文中会有介绍)。如果你还下载了patch文件,比如patch-2.4.0test8,你就可以进行patch操作(下面假设patch-2.4.0test8已经位于/usr/src目录下了,否则你需要先把该文件拷贝到/usr/src下):

#patch -p0 < patch-2.4.0test8

  现在,我们已经把内核源程序升级到最新版本了,下面就让我们开始内核编译的旅程吧。


准备工作

  通常要运行的第一个命令是:

#cd /usr/src/linux;make mrproper

  该命令确保源代码目录下没有不正确的.o文件以及文件的互相依赖。由于我们使用刚下载的完整的源程序包进行编译,所以本步可以省略。而如果你多次使用了这些源程序编译内核,那么最好要先运行一下这个命令。

  确保/usr/include/目录下的asm、linux和scsi等链接是指向要升级的内核源代码的。它们分别链向源代码目录下的真正的、该计算机体系结构(对于PC机来说,使用的体系结构是i386)所需要的真正的include子目录。

  如:asm指向/usr/src/linux/include/asm-i386等。若没有这些链接,就需要手工创建,按照下面的步骤进行:

# cd /usr/include/
# rm -r asm linux scsi
# ln -s /usr/src/linux/include/asm-i386 asm
# ln -s /usr/src/linux/include/linux linux
# ln -s /usr/src/linux/include/scsi scsi

  这是配置非常重要的一部分。删除掉/usr/include下的asm、linux和scsi链接后,再创建新的链接指向新内核源代码目录下的同名的目录。这些头文件目录包含着保证内核在系统上正确编译所需要的重要的头文件。现在你应该明白为什么我们上面又在/usr/src下"多余"地创建了个名为linux的链接了吧?

  配置

  接下来的内核配置过程比较烦琐,但是配置的适当与否与日后Linux的运行直接相关,有必要了解一下一些主要的且经常用到的选项的设置。

  配置内核可以根据需要与爱好使用下面命令中的一个:

#make config(基于文本的最为传统的配置界面,不推荐使用)
#make menuconfig(基于文本选单的配置界面,字符终端下推荐使用)
#make xconfig(基于图形窗口模式的配置界面,Xwindow下推荐使用)
#make oldconfig(如果只想在原来内核配置的基础上修改一些小地方,会省去不少麻烦)

  这三个命令中,make xconfig的界面最为友好,如果你可以使用Xwindow,那么就推荐你使用这个命令。

  如果你不能使用Xwindow,那么就使用make menuconfig好了。界面虽然比上面一个差点,总比make config的要好多了。

  选择相应的配置时,有三种选择,它们分别代表的含义如下:

Y--将该功能编译进内核
N--不将该功能编译进内核
M--将该功能编译成可以在需要时动态插入到内核中的模块

  如果使用的是make xconfig,使用鼠标就可以选择对应的选项。如果使用的是make menuconfig,则需要使用空格键进行选取。你会发现在每一个选项前都有个括号, 但有的是中括号有的是尖括号,还有一种圆括号。

  用空格键选择时可以发现,中括号里要么是空,要么是"*",而尖括号里可以是空,"*"和"M"这表示前者对应的项要么不要,要么编译到内核里;后者则多一样选择,可以编译成模块。而圆括号的内容是要你在所提供的几个选项中选择一项。

  在编译内核的过程中,最烦杂的事情就是这步配置工作了,很多新手都不清楚到底该如何选取这些选项。实际上在配置时,大部分选项可以使用其缺省值,只有小部分需要根据用户不同的需要选择。

  选择的原则是将与内核其它部分关系较远且不经常使用的部分功能代码编译成为可加载模块,有利于减小内核的长度,减小内核消耗的内存,简化该功能相应的环境改变时对内核的影响;不需要的功能就不要选;与内核关心紧密而且经常使用的部分功能代码直接编译到内核中。下面就让我们对常用的选项分别加以介绍。

  1. Code maturity level options

  代码成熟等级。此处只有一项:prompt for development and/or incomplete code/drivers,如果你要试验现在仍处于实验阶段的功能,比如khttpd、IPv6等,就必须把该项选择为Y了;否则可以把它选择为N。

  2. Loadable module support

  对模块的支持。这里面有三项:

  Enable loadable module support:除非你准备把所有需要的内容都编译到内核里面,否则该项应该是必选的。

  Set version information on all module symbols:可以不选它。

  Kernel module loader:让内核在启动时有自己装入必需模块的能力,建议选上。


3. Processor type and features

  CPU类型。内容蛮多的,不一一介绍了,有关的几个如下:

  Processor family:根据你自己的情况选择CPU类型。

  High Memory Support:大容量内存的支持。可以支持到4G、64G,一般可以不选。

  Math emulation:协处理器仿真。协处理器是在386时代的宠儿,现在早已不用了。

  MTTR support:MTTR支持。可不选。

  Symmetric multi-processing support:对称多处理支持。除非你富到有多个CPU,否则就不用选了。

  4. General setup 这里是对最普通的一些属性进行设置。这部分内容非常多,一般使用缺省设置就可以了。下面介绍一下经常使用的一些选项:

  Networking support:网络支持。必须,没有网卡也建议你选上。 PCI support:PCI支持。如果使用了PCI的卡,当然必选。

  PCI access mode:PCI存取模式。可供选择的有BIOS、Direct和Any,选Any吧。

  Support for hot-pluggabel devices:热插拔设备支持。支持的不是太好,可不选。

  PCMCIA/CardBus support:PCMCIA/CardBus支持。有PCMCIA就必选了。

  System V IPC

  BSD Process Accounting

  Sysctl support:以上三项是有关进程处理/IPC调用的,主要就是System V和BSD两种风格。如果你不是使用BSD,就按照缺省吧。

  Power Management support:电源管理支持。 Advanced Power Management BIOS support:高级电源管理BIOD支持。


  5. Memory Technology Device(MTD)

  MTD设备支持。可不选。

  6. Parallel port support

  串口支持。如果不打算使用串口,就别选了。

  7. Plug and Play configuration

  即插即用支持。虽然Linux对即插即用目前支持的不如Windows好,但是还是选上吧,这样你可以拔下鼠标之类的体验一下Linux下即插即用的感觉。

  8. Block devices

  块设备支持。这个就得针对自己的情况来选了,简单说明一下吧:

 

Normal PC floppy disk support:普通PC软盘支持。这个应该必选。
XT hard disk support:
Compaq SMART2 support:
Mulex DAC960/DAC1100 PCI RAID Controller support:RAID镜像用的。
Loopback device support:
Network block device support:网络块设备支持。如果想访问网上邻居的东西,就选上。
Logical volume manager(LVM)support:逻辑卷管理支持。
Multiple devices driver support:多设备驱动支持。
RAM disk support:RAM盘支持。

  9. Networking options

  网络选项。这里配置的是网络协议。内容太多了,不一一介绍了,自己看吧,如果你对网络协议有所了解的话,应该可以看懂的。如果懒得看,使用缺省选项(肯定要选中TCP/IP networking哦)就可以了。

  让我们看看,TCP/IP、ATM、IPX、DECnet、Appletalk……支持的协议好多哦,IPv6也支持了,Qos and/or fair queueing(服务质量公平调度)也支持了,还有kHTTPd,不过这些都还在实验阶段。

  10. Telephony Support

  电话支持。这个是什么东东?让我查查帮助,原来是Linux下可以支持电话卡,这样你就可以在IP上使用普通的电话提供语音服务了。记住,电话卡可和modem没有任何关系哦。

  11. ATA/IDE/MFM/RLL support

  这个是有关各种接口的硬盘/光驱/磁带/软盘支持的,内容太多了,使用缺省的选项吧,如果你使用了比较特殊的设备,比如PCMCIA等,就到里面自己找相应的选项吧。

12. SCSI support

  SCSI设备的支持。我没有SCSI的设备,所以根本就不用选,如果你用了SCSI的硬盘/光驱/磁带等设备,自己找好了。

  13. IEEE 1394(FireWire)support 这个是什么?低版本的没有见过,看看帮助再说。原来是要Fireware硬件来提高串行总线的性能,我没有,不选了。

  14. I2O device support

  这个也不清楚,帮助里说是这个需要I2O接口适配器才能支持的,在智能Input/Output(I2O)体系接口中使用,又是要硬件,不选了。

  15. Network device support

  网络设备支持。上面选好协议了,现在该选设备了,可想而知,内容肯定多得很。还好还好,里面大概分类了,有ARCnet设备、Ethernet(10 or 100 Mbit)、Ethernet(1000Mbit)、Wireless LAN(non-hamradio)、Token Ring device、Wan interfaces、PCMCIA network device support几大类。

  我用的是10/100M的以太网,看来只需要选则这个了。还是10/100M的以太网设备熟悉,内容虽然多,一眼就可以看到我所用的RealTeck RTL-8139 PCI Fast Ethernet Adapter support,为了免得麻烦,编译到内核里面好了,不选M了,选Y。耐心点,一般说来你都能找到自己用的网卡。如果没有,你只好自己到厂商那里去要驱动了。

  16. Amateur Radio support

  又一个不懂的,应该是配置业余无线广播的吧,没有,不要了。

  17. IrDA(infrared)support

  这个要红外支持,免了。

  18. ISDN subsystem

  如果你使用ISDN上网,这个就必不可少了。自己看着办好了。

  19. Old CD-ROM drivers(not SCSI、not IDE) 做的可真周到,原来那些非SCSI/IDE口的光驱谁还在用啊,自己选吧,反正我是用的IDE的CD-ROM,不选这个。

  20. Character devices

  字符设备。这个内容又太多了,先使用缺省设置,需要的话自己就修改。把大类介绍一下吧:

  I2C support:I2C是Philips极力推动的微控制应用中使用的低速串行总线协议。如果你要选择下面的Video For Linux,该项必选。

  Mice:鼠标。现在可以支持总线、串口、PS/2、C&T 82C710 mouse port、PC110 digitizer pad,自己根据需要选择。

  Joysticks:手柄。即使在Linux下把手柄驱动起来意义也不是太大,游戏太少了。

  Watchdog Cards:虽然称为Cards,这个可以用纯软件来实现,当然也有硬件的。如果你把这个选中,那么就会在你的/dev下创建一个名为watchdog的文件,它可以记录你的系统的运行情况,一直到系统重新启动的1分钟左右。有了这个文件,你就可以恢复系统到重启前的状态了。

  Video For Linux:支持有关的音频/视频卡。

  Ftape, the floppy tape device driver:

  PCMCIA character device support:

  21. File systems

  文件系统。内容又太多了,老法子,在缺省选项的基础上进行修改。介绍以下几项:

  Quota support:Quota可以限制每个用户可以使用的硬盘空间的上限,在多用户共同使用一台主机的情况中十分有效。

  DOS FAT fs support:DOS FAT文件格式的支持,可以支持FAT16、FAT32。

  ISO 9660 CD-ROM file system support:光盘使用的就是ISO 9660的文件格式。

  NTFS file system support:ntfs是NT使用的文件格式。

  /proc file system support:/proc文件系统是Linux提供给用户和系统进行交互的通道,建议选上,否则有些功能没法正确执行。

  还有另外三个大类都规到这儿了:Network File Systems(网络文件系统)、Partition Types(分区类型)、Native Language Support(本地语言支持)。值得一提的是Network File Systems里面的两种:NFS和SMB分别是Linux和Windows相互以网络邻居的形式访问对方所使用的文件系统,根据需要加以选择。

  22. Console drivers

  控制台驱动。一般使用VGA text console就可以了,标准的80*25的文本控制台。

  23. Sound

  声卡驱动。如果你能在列表中找到声卡驱动那自然最好,否则就试试OSS了。

  24. USB supprot

  USB支持。很多USB设备,比如鼠标、调制解调器、打印机、扫描仪等,在Linux都可以得到支持,根据需要自行选择。

  25. Kernel hacking

  配置了这个,即使在系统崩溃时,你也可以进行一定的工作了。普通用户是用不着这个功能的。

  总算配置完了,现在存盘退出,当然你也可以把现在的配置文件保存起来,这样下次再配置的时候就省力气了。


编译

  在繁杂的配置工作完成以后,下面你就可以自己到杯茶耐心等候了。与编译有关的命令有如下几个:

#make dep
#make clean
#make zImage
#make bzImage
#make modules
#make modules_install
#depmod -a

  第一个命令make dep实际上读取配置过程生成的配置文件,来创建对应于配置的依赖关系树,从而决定哪些需要编译而那些不需要;第二命令make clean完成删除前面步骤留下的文件,以避免出现一些错误;第三个命令make zImage和第四个命令make bzImage实现完全编译内核,二者生成的内核都是使用gzip压缩的,只要使用一个就够了,它们的区别在于使用make bzImage可以生成大一点的内核,比如在编译2.4.0版本的内核时如果使用make zImage命令,那么就会出现system too big的错误提示。建议大家使用make bzImage命令。

  后面三个命令只有在你进行配置的过程中,在回答Enable loadable module support (CONFIG_MODULES)时选了"Yes"才是必要的,make modules和make modules_install分别生成相应的模块和把模块拷贝到需要的目录中。

  严格说来,第七个命令和编译过程并没有关系,它是生成模块间的依赖关系,这样你启动新内核之后,使用modprobe命令加载模块时就能正确地定位模块。

  更新

  经过以上的步骤,我们终于得到了新版本的内核。为了能够使用新版本的内核,我们还需要做一些改动:

#cp /usr/src/linux/System.map /boot/System.map-2.4.0test8
#cp /usr/src/linux/arch/i386/bzImage /boot/vmlinuz-2.4.0test8

  以上这两个文件是我们刚才编译时新生成的。下面修改/boot下的两个链接System.map和vmlinuz,使其指向新内核的文件

#cd /boot;rm -f System.map vmlinuz
#ln -s vmlinuz-2.4.0test8 vmlinuz
#ln -s System.map-2.4.0test8 System.map

  然后修改/etc/lilo.conf:

#vi /etc/lilo.conf

  增加如下一段:

image=/boot/vmlinuz-2.4.0test8
label=linux240
read-only
root=/dev/hda2

  其中root=/dev/hda2一行要根据需要自行加以修改。运行:

#/sbin/lilo -v

  确认对/etc/lilo.conf的编辑无误,现在重新启动系统:

#shutdown -r now

  在机器重启后出现LILO时按TAB键,输入linux240,我们的新内核发挥作用了,好好享受吧

mmap函数

内存映射使一个磁盘文件与存储空间中的一个缓存相映射。
对缓存存取数据,就相当对磁盘文件读写操作
mmap      ummmap
 
具体看下面摘录的这篇文章
 
 共享内存可以说是最有用的进程间通信方式,也是最快的IPC形式。两个不同进程A、B共享内存的意思是,同一块物理内存被映射到进程A、B各自的进程地址空间。进程A可以即时看到进程B对共享内存中数据的更新,反之亦然。由于多个进程共享同一块内存区域,必然需要某种同步机制,互斥锁和信号量都可以。  
   
  采用共享内存通信的一个显而易见的好处是效率高,因为进程可以直接读写内存,而不需要任何数据的拷贝。对于像管道和消息队列等通信方式,则需要在内核和用户空间进行四次的数据拷贝,而共享内存则只拷贝两次数据[1]:一次从输入文件到共享内存区,另一次从共享内存区到输出文件。实际上,进程之间在共享内存时,并不总是读写少量数据后就解除映射,有新的通信时,再重新建立共享内存区域。而是保持共享区域,直到通信完毕为止,这样,数据内容一直保存在共享内存中,并没有写回文件。共享内存中的内容往往是在解除映射时才写回文件的。因此,采用共享内存的通信方式效率是非常高的。  
   
  Linux的2.2.x内核支持多种共享内存方式,如mmap()系统调用,Posix共享内存,以及系统V共享内存。linux发行版本如Redhat   8.0支持mmap()系统调用及系统V共享内存,但还没实现Posix共享内存,本文将主要介绍mmap()系统调用及系统V共享内存API的原理及应用。  
   
  一、内核怎样保证各个进程寻址到同一个共享内存区域的内存页面  
   
  1、page   cache及swap   cache中页面的区分:一个被访问文件物理页面都驻留在page   cache或swap   cache中,一个页面的所有信息由struct   page来描述。struct   page中有一个域为指针mapping   ,它指向一个struct   address_space类型结构。page   cache或swap   cache中的所有页面就是根据address_space结构以及一个偏移量来区分的。  
   
  2、文件与address_space结构的对应:一个具体的文件在打开后,内核会在内存中为之建立一个struct   inode结构,其中的i_mapping域指向一个address_space结构。这样,一个文件就对应一个address_space结构,一个address_space与一个偏移量能够确定一个page   cache   或swap   cache中的一个页面。因此,当要寻址某个数据时,很容易根据给定的文件及数据在文件内的偏移量而找到相应的页面。  
   
  3、进程调用mmap()时,只是在进程空间内新增了一块相应大小的缓冲区,并设置了相应的访问标识,但并没有建立进程空间到物理页面的映射。因此,第一次访问该空间时,会引发一个缺页异常。  
   
  4、对于共享内存映射情况,缺页异常处理程序首先在swap   cache中寻找目标页(符合address_space以及偏移量的物理页),如果找到,则直接返回地址;如果没有找到,则判断该页是否在交换区(swap   area),如果在,则执行一个换入操作;如果上述两种情况都不满足,处理程序将分配新的物理页面,并把它插入到page   cache中。进程最终将更新进程页表。  
  注:对于映射普通文件情况(非共享映射),缺页异常处理程序首先会在page   cache中根据address_space以及数据偏移量寻找相应的页面。如果没有找到,则说明文件数据还没有读入内存,处理程序会从磁盘读入相应的页面,并返回相应地址,同时,进程页表也会更新。  
   
  5、所有进程在映射同一个共享内存区域时,情况都一样,在建立线性地址与物理地址之间的映射之后,不论进程各自的返回地址如何,实际访问的必然是同一个共享内存区域对应的物理页面。  
  注:一个共享内存区域可以看作是特殊文件系统shm中的一个文件,shm的安装点在交换区上。  
   
  上面涉及到了一些数据结构,围绕数据结构理解问题会容易一些。  
   
  二、mmap()及其相关系统调用  
   
  mmap()系统调用使得进程之间通过映射同一个普通文件实现共享内存。普通文件被映射到进程地址空间后,进程可以向访问普通内存一样对文件进行访问,不必再调用read(),write()等操作。  
   
  注:实际上,mmap()系统调用并不是完全为了用于共享内存而设计的。它本身提供了不同于一般对普通文件的访问方式,进程可以像读写内存一样对普通文件的操作。而Posix或系统V的共享内存IPC则纯粹用于共享目的,当然mmap()实现共享内存也是其主要应用之一。  
   
  1、mmap()系统调用形式如下:  
   
  void*   mmap   (   void   *   addr   ,   size_t   len   ,   int   prot   ,   int   flags   ,   int   fd   ,   off_t   offset   )  
  参数fd为即将映射到进程空间的文件描述字,一般由open()返回,同时,fd可以指定为-1,此时须指定flags参数中的MAP_ANON,表明进行的是匿名映射(不涉及具体的文件名,避免了文件的创建及打开,很显然只能用于具有亲缘关系的进程间通信)。len是映射到调用进程地址空间的字节数,它从被映射文件开头offset个字节开始算起。prot   参数指定共享内存的访问权限。可取如下几个值的或:PROT_READ(可读)   ,   PROT_WRITE   (可写),   PROT_EXEC   (可执行),   PROT_NONE(不可访问)。flags由以下几个常值指定:MAP_SHARED   ,   MAP_PRIVATE   ,   MAP_FIXED,其中,MAP_SHARED   ,   MAP_PRIVATE必选其一,而MAP_FIXED则不推荐使用。offset参数一般设为0,表示从文件头开始映射。参数addr指定文件应被映射到进程空间的起始地址,一般被指定一个空指针,此时选择起始地址的任务留给内核来完成。函数的返回值为最后文件映射到进程空间的地址,进程可直接操作起始地址为该值的有效地址。这里不再详细介绍mmap()的参数,读者可参考mmap()手册页获得进一步的信息。  
   
  2、系统调用mmap()用于共享内存的两种方式:  
   
  (1)使用普通文件提供的内存映射:适用于任何进程之间;此时,需要打开或创建一个文件,然后再调用mmap();典型调用代码如下:    
   
  fd=open(name,   flag,   mode);  
  if(fd<0)  
  ...  
   
  ptr=mmap(NULL,   len   ,   PROT_READ|PROT_WRITE,   MAP_SHARED   ,   fd   ,   0);   通过mmap()实现共享内存的通信方式有许多特点和要注意的地方,我们将在范例中进行具体说明。    
   
  (2)使用特殊文件提供匿名内存映射:适用于具有亲缘关系的进程之间;由于父子进程特殊的亲缘关系,在父进程中先调用mmap(),然后调用fork()。那么在调用fork()之后,子进程继承父进程匿名映射后的地址空间,同样也继承mmap()返回的地址,这样,父子进程就可以通过映射区域进行通信了。注意,这里不是一般的继承关系。一般来说,子进程单独维护从父进程继承下来的一些变量。而mmap()返回的地址,却由父子进程共同维护。  
  对于具有亲缘关系的进程实现共享内存最好的方式应该是采用匿名内存映射的方式。此时,不必指定具体的文件,只要设置相应的标志即可,参见范例2。  
   
  3、系统调用munmap()  
   
  int   munmap(   void   *   addr,   size_t   len   )  
  该调用在进程地址空间中解除一个映射关系,addr是调用mmap()时返回的地址,len是映射区的大小。当映射关系解除后,对原来映射地址的访问将导致段错误发生。  
   
  4、系统调用msync()  
   
  int   msync   (   void   *   addr   ,   size_t   len,   int   flags)  
  一般说来,进程在映射空间的对共享内容的改变并不直接写回到磁盘文件中,往往在调用munmap()后才执行该操作。可以通过调用msync()实现磁盘上文件内容与共享内存区的内容一致。  //应该不太常用
   
  三、mmap()范例  
   
  下面将给出使用mmap()的两个范例:范例1给出两个进程通过映射普通文件实现共享内存通信;范例2给出父子进程通过匿名映射实现共享内存。系统调用mmap()有许多有趣的地方,下面是通过mmap()映射普通文件实现进程间的通信的范例,我们通过该范例来说明mmap()实现共享内存的特点及注意事项。  
   
  范例1:两个进程通过映射普通文件实现共享内存通信  
   
  范例1包含两个子程序:map_normalfile1.c及map_normalfile2.c。编译两个程序,可执行文件分别为map_normalfile1及map_normalfile2。两个程序通过命令行参数指定同一个文件来实现共享内存方式的进程间通信。map_normalfile2试图打开命令行参数指定的一个普通文件,把该文件映射到进程的地址空间,并对映射后的地址空间进行写操作。map_normalfile1把命令行参数指定的文件映射到进程地址空间,然后对映射后的地址空间执行读操作。这样,两个进程通过命令行参数指定同一个文件来实现共享内存方式的进程间通信。  
 
下面是两个程序代码:  
   
  /*-------------map_normalfile1.c-----------*/  
  #include   <sys/mman.h>  
  #include   <sys/types.h>  
  #include   <fcntl.h>  
  #include   <unistd.h>  
  typedef   struct{  
  char   name[4];  
  int     age;  
  }people;  
   
  main(int   argc,   char**   argv)   //   map   a   normal   file   as   shared   mem:  
  {  
  int   fd,i;  
  people   *p_map;  
  char   temp;  
   
  fd=open(argv[1],O_CREAT|O_RDWR|O_TRUNC,00777);  
  lseek(fd,sizeof(people)*5-1,SEEK_SET);  
  write(fd,"",1);  
   
  p_map   =   (people*)   mmap(   NULL,sizeof(people)*10,PROT_READ|PROT_WRITE,MAP_SHARED,fd,0   );  
  close(   fd   );  
  temp   =   'a';  
  for(i=0;   i<10;   i++)  
  {  
  temp   +=   1;  
  memcpy(   (   *(p_map+i)   ).name,   &temp,2   );  
  (   *(p_map+i)   ).age   =   20+i;  
  }  
  printf("   initialize   over   \n   ");  
  sleep(10);  
   
  munmap(   p_map,   sizeof(people)*10   );  
  printf(   "umap   ok   \n"   );  
  }  
   
  /*-------------map_normalfile2.c-----------*/  
  #include   <sys/mman.h>  
  #include   <sys/types.h>  
  #include   <fcntl.h>  
  #include   <unistd.h>  
  typedef   struct{  
  char   name[4];  
  int     age;  
  }people;  
   
  main(int   argc,   char**   argv)   //   map   a   normal   file   as   shared   mem:  
  {  
  int   fd,i;  
  people   *p_map;  
  fd=open(   argv[1],O_CREAT|O_RDWR,00777   );  
  p_map   =   (people*)mmap(NULL,sizeof(people)*10,PROT_READ|PROT_WRITE,MAP_SHARED,fd,0);  
  for(i   =   0;i<10;i++)  
  {  
  printf(   "name:   %s   age   %d;\n",(*(p_map+i)).name,   (*(p_map+i)).age   );  
   
  }  
  munmap(   p_map,sizeof(people)*10   );  
  }  
   
  map_normalfile1.c首先定义了一个people数据结构,(在这里采用数据结构的方式是因为,共享内存区的数据往往是有固定格式的,这由通信的各个进程决定,采用结构的方式有普遍代表性)。map_normfile1首先打开或创建一个文件,并把文件的长度设置为5个people结构大小。然后从mmap()的返回地址开始,设置了10个people结构。然后,进程睡眠10秒钟,等待其他进程映射同一个文件,最后解除映射。  
   
  map_normfile2.c只是简单的映射一个文件,并以people数据结构的格式从mmap()返回的地址处读取10个people结构,并输出读取的值,然后解除映射。  
   
  分别把两个程序编译成可执行文件map_normalfile1和map_normalfile2后,在一个终端上先运行./map_normalfile2   /tmp/test_shm,程序输出结果如下:  
   
  initialize   over  
  umap   ok  
   
  在map_normalfile1输出initialize   over   之后,输出umap   ok之前,在另一个终端上运行map_normalfile2   /tmp/test_shm,将会产生如下输出(为了节省空间,输出结果为稍作整理后的结果):  
   
  name:   b   age   20;   name:   c   age   21;   name:   d   age   22;   name:   e   age   23;   name:   f   age   24;  
  name:   g   age   25;   name:   h   age   26;   name:   I   age   27;   name:   j   age   28;   name:   k   age   29;  
   
  在map_normalfile1   输出umap   ok后,运行map_normalfile2则输出如下结果:  
   
  name:   b   age   20;   name:   c   age   21;   name:   d   age   22;   name:   e   age   23;   name:   f   age   24;  
  name:   age   0;   name:   age   0;   name:   age   0;   name:   age   0;   name:   age   0;  
   
  从程序的运行结果中可以得出的结论  
   
  1、   最终被映射文件的内容的长度不会超过文件本身的初始大小,即映射不能改变文件的大小;  
   
  2、   可以用于进程通信的有效地址空间大小大体上受限于被映射文件的大小,但不完全受限于文件大小。打开文件被截短为5个people结构大小,而在map_normalfile1中初始化了10个people数据结构,在恰当时候(map_normalfile1输出initialize   over   之后,输出umap   ok之前)调用map_normalfile2会发现map_normalfile2将输出全部10个people结构的值,后面将给出详细讨论。  
  注:在linux中,内存的保护是以页为基本单位的,即使被映射文件只有一个字节大小,内核也会为映射分配一个页面大小的内存。当被映射文件小于一个页面大小时,进程可以对从mmap()返回地址开始的一个页面大小进行访问,而不会出错;但是,如果对一个页面以外的地址空间进行访问,则导致错误发生,后面将进一步描述。因此,可用于进程间通信的有效地址空间大小不会超过文件大小及一个页面大小的和。  
   
  3、   文件一旦被映射后,调用mmap()的进程对返回地址的访问是对某一内存区域的访问,暂时脱离了磁盘上文件的影响。所有对mmap()返回地址空间的操作只在内存中有意义,只有在调用了munmap()后或者msync()时,才把内存中的相应内容写回磁盘文件,所写内容仍然不能超过文件的大小。  
   
  范例2:父子进程通过匿名映射实现共享内存  
   
  #include   <sys/mman.h>  
  #include   <sys/types.h>  
  #include   <fcntl.h>  
  #include   <unistd.h>  
  typedef   struct{  
  char   name[4];  
  int     age;  
  }people;  
  main(int   argc,   char**   argv)  
  {  
  int   i;  
  people   *p_map;  
  char   temp;  
  p_map=(people*)mmap(NULL,sizeof(people)*10,PROT_READ|PROT_WRITE,MAP_SHARED|MAP_ANONYMOUS,-1,0);  
  if(fork()   ==   0)  
  {  
  sleep(2);  
  for(i   =   0;i<5;i++)  
  printf("child   read:   the   %d   people's   age   is   %d\n",i+1,(*(p_map+i)).age);  
  (*p_map).age   =   100;  
  munmap(p_map,sizeof(people)*10);   //实际上,进程终止时,会自动解除映射。  
  exit();  
  }  
  temp   =   'a';  
  for(i   =   0;i<5;i++)  
  {  
  temp   +=   1;  
  memcpy((*(p_map+i)).name,   &temp,2);  
  (*(p_map+i)).age=20+i;  
  }  
   
  sleep(5);  
  printf(   "parent   read:   the   first   people,s   age   is   %d\n",(*p_map).age   );  
  printf("umap\n");  
  munmap(   p_map,sizeof(people)*10   );  
  printf(   "umap   ok\n"   );  
  }  
   
  考察程序的输出结果,体会父子进程匿名共享内存:  
   
  child   read:   the   1   people's   age   is   20  
  child   read:   the   2   people's   age   is   21  
  child   read:   the   3   people's   age   is   22  
  child   read:   the   4   people's   age   is   23  
  child   read:   the   5   people's   age   is   24  
   
  parent   read:   the   first   people,s   age   is   100  
  umap  
  umap   ok  
   
  四、对mmap()返回地址的访问  
   
  前面对范例运行结构的讨论中已经提到,linux采用的是页式管理机制。对于用mmap()映射普通文件来说,进程会在自己的地址空间新增一块空间,空间大小由mmap()的len参数指定,注意,进程并不一定能够对全部新增空间都能进行有效访问。进程能够访问的有效地址大小取决于文件被映射部分的大小。简单的说,能够容纳文件被映射部分大小的最少页面个数决定了进程从mmap()返回的地址开始,能够有效访问的地址空间大小。超过这个空间大小,内核会根据超过的严重程度返回发送不同的信号给进程。可用如下图示说明:  
   
   
     
   
   
  注意:文件被映射部分而不是整个文件决定了进程能够访问的空间大小,另外,如果指定文件的偏移部分,一定要注意为页面大小的整数倍。下面是对进程映射地址空间的访问范例:  
   
  #include   <sys/mman.h>  
  #include   <sys/types.h>  
  #include   <fcntl.h>  
  #include   <unistd.h>  
  typedef   struct{  
  char   name[4];  
  int     age;  
  }people;  
   
  main(int   argc,   char**   argv)  
  {  
  int   fd,i;  
  int   pagesize,offset;  
  people   *p_map;  
   
  pagesize   =   sysconf(_SC_PAGESIZE);  
  printf("pagesize   is   %d\n",pagesize);  
  fd   =   open(argv[1],O_CREAT|O_RDWR|O_TRUNC,00777);  
  lseek(fd,pagesize*2-100,SEEK_SET);  
  write(fd,"",1);  
  offset   =   0;   //此处offset   =   0编译成版本1;offset   =   pagesize编译成版本2  
  p_map   =   (people*)mmap(NULL,pagesize*3,PROT_READ|PROT_WRITE,MAP_SHARED,fd,offset);  
  close(fd);  
   
  for(i   =   1;   i<10;   i++)  
  {  
  (*(p_map+pagesize/sizeof(people)*i-2)).age   =   100;  
  printf("access   page   %d   over\n",i);  
  (*(p_map+pagesize/sizeof(people)*i-1)).age   =   100;  
  printf("access   page   %d   edge   over,   now   begin   to   access   page   %d\n",i,   i+1);  
  (*(p_map+pagesize/sizeof(people)*i)).age   =   100;  
  printf("access   page   %d   over\n",i+1);  
  }  
  munmap(p_map,sizeof(people)*10);  
  }  
   
  如程序中所注释的那样,把程序编译成两个版本,两个版本主要体现在文件被映射部分的大小不同。文件的大小介于一个页面与两个页面之间(大小为:pagesize*2-99),版本1的被映射部分是整个文件,版本2的文件被映射部分是文件大小减去一个页面后的剩余部分,不到一个页面大小(大小为:pagesize-99)。程序中试图访问每一个页面边界,两个版本都试图在进程空间中映射pagesize*3的字节数。  
   
  版本1的输出结果如下:  
   
  pagesize   is   4096  
  access   page   1   over  
  access   page   1   edge   over,   now   begin   to   access   page   2  
  access   page   2   over  
  access   page   2   over  
  access   page   2   edge   over,   now   begin   to   access   page   3  
  Bus   error   //被映射文件在进程空间中覆盖了两个页面,此时,进程试图访问第三个页面  
   
  版本2的输出结果如下:  
   
  pagesize   is   4096  
  access   page   1   over  
  access   page   1   edge   over,   now   begin   to   access   page   2  
  Bus   error   //被映射文件在进程空间中覆盖了一个页面,此时,进程试图访问第二个页面  
   
  结论:采用系统调用mmap()实现进程间通信是很方便的,在应用层上接口非常简洁。内部实现机制区涉及到了linux存储管理以及文件系统等方面的内容,可以参考一下相关重要数据结构来加深理解。在本专题的后面部分,将介绍系统v共享内存的实现。  
   
  参考文献:  
   
  [1]   Understanding   the   Linux   Kernel,   2nd   Edition,   By   Daniel   P.   Bovet,   Marco   Cesati   ,   对各主题阐述得重点突出,脉络清晰。  
   
  [2]   UNIX网络编程第二卷:进程间通信,作者:W.Richard   Stevens,译者:杨继张,清华大学出版社。对mmap()有详细阐述。  
   
  [3]   Linux内核源代码情景分析(上),毛德操、胡希明著,浙江大学出版社,给出了mmap()相关的源代码分析。  
   
  [4]mmap()手册  
   
   
   
     
    文章作者:郑彦兴    
  文章来源:网络文摘      

12月22日

linux下访问Window分区(NTFS)以及Mount闪存

本文所讲例子均基于内核为2.4.20-8的RedHat 9 Linux操作系统.如果使用的是其他linux系统或是redhat其他版本,或其他内核,本文仅作参考--Jiarry(Jarry).

加载USB移动盘符以及软驱/光驱 首先打开终端并输入 # fdisk -l 通过查询盘符(用fdisk)列表来查看支持的分驱格式以及相关信息.Redhat9 默认自带的支持fat32,fat等. 输入 # cat /proc/filesystems 查看系统支持的格式,有vfat的话支持FAT/FAT32,有ntfs的话支持NTFS,有iso9660的话支持iso标准CD,有smbfs的话支持samba/Microsoft Windows Network;没有需要的文件系统的话,需要重编内核加以支持; 在mnt下建立一个文件夹 # mkdir /mnt/usb1 这个文件夹用来转载usb的数据.redhat中,mnt用来加载各种盘符.usb,floppy,cdrom都可以. 输入 mount -t vfat /dev/sda1 /mnt/usb1 这时输入mount挂载刚用fidsk查看到usb所在的位置,并装载入到刚建好的文件夹中. 输入 #cd /mnt/usb1 进入usb1文件夹,用# ls或dir查看一下列表吧,是否看见了usb里的文件了呢. cd是进入文件的明令于DOS下相同,ls与dir都能查看文件列表. 输入 #umount /mnt/usb1 卸载USB Linux下,退出光盘或软盘必须卸载才能拔出.USB使用完后最好也卸载再拔出. 显示中文 #mount -t vfat -o iocharset=gb2312,codepage=936 /dev/sda1 /mnt/usb1 前面加载后的文件无法正常显示中文名,加上 -o iocharset=gb2312或者utf8就可以显示中文名称了. 加载光驱 [root@localhost root]# mount -t vfat /dev/scd0 /mnt/cdrom 或者 #mount /mnt/cdrom 加载软驱 [root@localhost root]# mount -t vfat -o iocharset=gb2312 /dev/fd0 /mnt/floppy 或者 #mount /mnt/floppy 访问windows NTFS盘符 访问fat或者fat32格式,与访问USB移动驱动器几乎差不多,如. #mount -t vfat -o iocharset=gb2312,codepage=936 /dev/hda6 /mnt/winD 即将/dev/hda6也就是windows D加载至mnt/winD文件夹下. 访问NTFS格式 #mount -t ntfs -o iocharset=gb2312 /dev/hda8 /mnt/winH 前面通过 #cat /proc/filesystems 可以查看到redha默认不支持NTFS格式,使用过红旗的可能知道红旗是可以访问NTFS的.这样我们需要下载一个与此相应的版本.安装软件包 #rpm -ivh kernel-ntfs-2.4.20-8.i686.rpm (下载地址:根据系统内核找到不同的rpm安装包 http://linux-ntfs.sourceforge.net/rpm/redhat9.html ) 也可用双击的方式安装(redhat9的安装最好是将开发工具以及编辑工具全选上),安装后用 #cat /proc/filesystems 看下,就能发现ntfs了. 最后再用mount命令 #mount -t ntfs -o iocharset=gb2312 /dev/hda7 /mnt/winG 这样就可以装载各个NTFS的盘符.别忘了先在mnt下建立相应的文件夹. 自动加载windows盘符 可以在启动文件里加如mount命令,那样也可以.但我的做法是,在桌面建立一个可执行autoRun.sh文件,将mount命令写进该文件里,需要用到时双击该sh文件运行即可.如下 #[root@localhost root]# sh /root/.gnome-desktop/autoRun.sh #装载windows盘符 mount -t ntfs -o iocharset=gb2312 /dev/hda5 /mnt/winE mount -t ntfs -o iocharset=gb2312 /dev/hda6 /mnt/winF mount -t ntfs -o iocharset=gb2312 /dev/hda7 /mnt/winG mount -t ntfs -o iocharset=gb2312 /dev/hda8 /mnt/winH 只要将以上文件存成一个.sh文件,且给该文件可执行权限就行了.这样很方便吧,想用时执行该文件就可以了,卸载也可以按这样的方式. 说明:本例所讲对windows NTFS是只读模式,要写入要另外下载相应的包,但不建议写入.从windows下访问Linux也很简单,去google搜索一下,或是下载一个 (windows下看linux分区的软件 Paragon.Ext2FS.Anywhere.2.5.rar和explore2fs-1.00-pre4.zip)软件,那样就可以读写了.但最好只是导出一些文件,不要写入. 为了让更多处于初学阶段的朋友能更快的适应并熟练使用Linux,也为了让自己加深记忆.特将自己在使用Linux过程中的遇到问题以及解决方案整理出来,以供大家参考.同时也备日后查阅.我知道大部分朋友与我一样都是从Windows下转入Linux的,而且仍然继续在使用Windows,都装了双系统.那我希望自己以及与我同样喜欢学习新知识的朋友在掌握Windows的情况下,能尽快掌握Linux.

12月21日

几个linux的bsah命令 2

find
[语法]: find 路径名... 表达式
[说明]: find 命令递归地遍历指定路径下的每个文件和子目录,看该文件是否能使表达式值为真,以下 n 代表一个十进制整数,+n 代表打印 n , -n 代表小于 n ,下面是合法表达式说明:
-name 模式 文件名与模式匹配则为真,(\ 为转意符)
-perm [-]八进制数 文件存取模式与八进制数相同则为真若有- 选项,则文件存取模式含有八进制数规定模式即为真
-size n[c] 文件块长度为 n 则真(一块为512字节),若有c 选项,则文件字节长度为 n 则真
-atime n 若文件的最近访问时间为 n 天前则为真,find 命令将改变其访问的目录的访问时间
-mtime n 若文件的最近修改时间为 n 天前则为真
-ctime n 若文件状态为 n 天前改变则为真
-exec 命令 { }\; 若命令返回值为0则真,{ }内为命令参数,此命令必须以 \; 为结束
-ok 命令 { }\; 与 exec 相同,只是在命令执行前先提示,若回答 y 则执行命令
-print 显示输出使表达式为真的文件名
-newer 文件 若文件的访问时间比newer 指定的文件新则真
-depth 先下降到搜索目录的子目录,然后才至其自身
-mount 仅查找包含指定目录的文件系统
-local 文件在当前文件系统时为真
-type c 文件类型为 c 则真,c 取值可为 b(块文件) c (字符文件) d(目录) l (符号链接) p (命名管道) f (普通文件)
\( 表达式 \) 表达式为真则真
-links n 文件链接数为 n 时为真
-user 用户 当文件属于用户时为真,用户可用数字表示UID
-nouser 当文件不属于 /etc/passwd 中的一个用户时为真
-group 文件组 当文件属于文件组时为真,文件组可用数字表示GID
-nogroup 当文件不属于 /etc/group 中的一个组时为真
-fstype 类型 当文件所属文件系统类型为指定类型时真
-inum n 当文件 i 节点号为 n 时为真
-prune 当目录名与模式匹配时,不再搜索其子目录
可以用逻辑操作符将简单表达式连接成复杂表达式
逻辑操作符有 ! 表示非操作, -o 表示或操作,两个表达式并列则表示与操作
[例子]:
find / -name find* -print
从根目录开始搜索文件名如 find* 的文件并显示之
find ./ -exec sleep{1}\; -print
每秒显示一个当前目录下的文件
find $HOME \(-name a.out -o -name '*.o' \) -atime +7 -exec rm {} \;
从$HOME目录开始搜索,删除所有文件名为a.out 或 *.o 且访问时间在7天前的文件


finger - 显示用户信息
finger命令比who命令显示的信息量大,功能强。基本使用方法如下
显示登录信息: finger
显示smith用户详细信息: finger smith

tar
[语法]: tar -c[vwfbL] [设备] [块] 文件...
tar -r[vwfbL] [设备] [块] 文件...
tar -t[vfL] [设备] [文件...]
tar -u[vwfbL] [设备] [块] 文件...
tar -x[lmovwfL] [设备] [文件...]
[说明]: 将多个文件归档,命令中各参数的意义为:
r 附加方式归档
x 抽取文件
t 显示文件
u 附加方式归档,同时删除旧版文件
c 建立新档案文件
v 显示所处理的文件名
w 处理文件前,要求用户确认
f 文件名 使用指定文件名作为档案文件
bn 每次读写 n 块,缺省值为1,最大值为20
m 将新的文件修改时间设为获取时的时间
o 获取出来的文件以下达tar指令的UID和GID存储
[例子]:
tar cvf file.tar *
tar tvf file.tar

 
tar xzvf  *.tar.gz
tar xjvf   *.tar.bz2

几个linux指令

at

[语法]: at [-f 命令文件] [-m] [-q 队列] -t 时间
[说明]: at命令由cron管理,在未来一个指定的时间内执行一组命令,命令可以从指定文件读入,也可从键盘读入,从键盘读入时以EOF结束,(通常为CTRL D)
-f 从指定命令文件中读入命令
-m 命令执行完后给用户发邮件
-q 将命令放入指定队列
-t 指定时间 指定的时间格式为 [[CC]YY]MMDDhhmm[.ss],CC表示年的前两位,YY表示年的后两位,MM表示月,DD表示日,hh表示时,mm表示分,ss表示秒

basename

basename 全路径名
basename 用来从全路径名中得到文件名。
例如:
basename /home/winter/first.txt 你会得到first.txt

bc

[语法]: bc [-c] [-l] [文件...]
[说明]: bc是一个交互式的高精度计算工具,采用类似于C语言的语法,能够从指定文件指定文件中读出命令执行,然后再进入交互式执行,事实上,bc是dc的预编译器,它自动激活dc,将语句经预编译后传递给dc,退出bc的命令是quit,bc中的ibase,obase,scale分别表示输入基数,输出基数,小数点右边的位数。
-c bc 只编译,而不将编译结果送dc,将其送到标准输出上
-l 预定义一个数学函数库,可在bc中使用以下函数
s(x) sine
c(x) cosine
e(x) exponential
l(x) log
a(x) arctangent
j(n,x) Bessel
[例子]:
bc -l 进入bc
scale=10 将小数位定为10位
e(1) 计算e的小数点后10位
quit 退出bc

cat

cat 用于显示文本,使用方法 cat [-benstuv] [file ...]
别看这么多参数,最常用的还是什么参数都没有,直接使用cat. cat 可以用来合并多个文本文件。其格式为
cat file1 file2 file3 > file4
这就把file1 file2 file3的内容都放入 file4中。当然,你可以合并更多的文件 
cat *.txt > file4
相当于把 所有以 ".txt"结尾的文件的内容都输出到file4 中。其中 " > " 表示定向符,如果没有 "> file4" 则会直接输出到终端
[语法]: cat [-u] [-s] [-v[-t] [-e]] 文件...
[说明]: 显示和连接一个或多个文件至标准输出
-u 无缓冲的输出(缺省为有缓冲输出)
-s 对不存在的文件不作提示
-v 显示出文件中的非打印字符,控制字符显示成^n ,n为八进制数字,其他非打印字符显示成M-x , x 为该字符低7位的8进制数值
-t 在使用-v 选项时,将制表符(tab) 显示成 ^I,将换页符(formfeed)显示成 ^ L
-e 在使用-v 选项时,在每一行的行尾显示 $
[例子]:
cat file 显示文件
cat -s -v -e file1 file2 file3 逐个显示文件 file1 file2 file3
 

cmp

[语法]: cmp [-l] [-s] 文件1 文件2
[说明]: 比较两个文件,若文件1 为 - ,则使用标准输入, 两个文件相同则无提示,不同则显示出现第一个不同时的字符数和行号
-l 显示每个不同处的字节数(10进制)和不同的字节(8进制)
-s 不作任何提示,只返回码
[例子]:
cmp file1 file2 比较文件 file1 和 file2
cmp -l file1 file2 比较文件file1 和 file2 的每处不同
 

date

[语法]: date
date mmddhhmm[yy]
[说明]: date 无参数时用于显示系统时间,修改时间时参数形式为 月日时分[年]

df

[语法]: df [-t] [文件系统]
[说明]: 显示剩余 i 节点和块数,使用 -t 选项,还显示总块数和 i 节点数
[例子]: df -t

diff

[语法]: diff [-be] 文件1 文件2
[说明]: 本命令逐行比较两个文本文件,将不同的行列出来
-b 将一串空格或TAB转换成一个空格或TAB
-e 生成一个编辑角本,作为ex或ed的输入可将文件1转换成文件2
[例子]:
diff file1 file2
diff -b file1 file2
diff -e file1 file2 >edscript

du

[语法]: du [-ars] [目录]
[说明]: 显示磁盘空间专用情况
-r 提供无法打开的文件信息
-s 仅显示指定目录所占空间的总和
-a 显示文件大小及目录总空间,其后可根文件名作参数
 

file

[语法]: file [-f 文件名文件] 文件...
[说明]: file 对指定文件进行测试,尽量猜测出文件类型并显示出来
-f 文件名文件 文件名文件是一个包含了文件名的文本文件, -f 选项测试文件名文件中所列出的文件
[例子]:
file * 显示当前目录下所有文件的类型

head

[语法]: head [-n] [文件 ...]
[说明]: 将文件的头n 行显示输出,缺省值为 10 行,显示多个文件时,在每个文件的前面加上 ==> 文件名 <==
[例子]:
head -9999 file1 file2 显示文件 file1 和 file2 的头 9999 行

logname

[语法]: logname
[说明]: 取得当前用户注册名

pack

[语法]: pack 文件...
[说明]: pack 将指定文件转储为压缩格式,文件名后加 .z , 文件存取模式,访问时间,修改时间等均不变
[例子]:
pack largefile 将largefile 压缩后转储为largefile.z

pcat 显示压缩文件

[语法]: pcat 文件...
[说明]: pcat 显示输出压缩文件
[例子]:
pcat largefile.z 显示压缩前的largefile
pcat largefile.z > oldfile 显示压缩前的laregfile,并将其重定向到文件oldfile中

split

[语法]: split [-n] [ 文件 [名字]]
[说明]: split 将指定大文件分解为若干个小文件,每个文件长度为n行(n 缺省时为1000),第一个小文件名为指定的名字后跟aa,直至zz,名字缺省值为x,若未指定大文件名,则使用标准输入
[例子]:
split -500 largefile little
将文件largefile 每500行写入一个文件,第一个文件名为littleaa
 

time

[语法]: time 命令
[说明]: 执行命令,并在执行完后显示其运行的时间
 

touch

[语法]: touch [-amc] [mmddhhmm[yy]] 文件...
[说明]: 将指定文件的访问时间和修改时间改变,若指定文件不存在则创建之,若无指定时间,则使用当前时间,返回值是未成功改变时间的文件个数,包括不存在而又未能创建的文件。
-a 只改变访问时间
-m 只改变修改时间
-c 若文件不存在,不创建它且不作提示
mmddhhmm[yy] 两位表示 月日时分[年]
[例子]:
touch file
更新文件file的时间
touch 0701000097 HongKong?
将文件HongKong的时间改为97年7月1日0时0分

wc

[语法]: wc [-lwc] 文件...
[说明]: 统计文件的行、字、字符数,若无指定文件,则统计标准输入
-l 只统计行数
-w 只统计字数
-c 只统计字符数
[例子]:
wc -l file1 file2 统计文件file1和file2 的行数

unpack

[语法]: unpack 文件...
[说明]: 将压缩后的文件解压后转储为压缩前的格式
[例子]:
unpack largefile.z 将压缩文件largefile.z解压后转储为largefile

uptime

用途:uptime报告系统到现在为止运行了多长时间。
举例:uptime。以下是该命令执行后输出的实例:
9:31pm up 4 day(s),20:36,14 users,load average:0.00,0.01,0.02

12月20日

一份linux相关东西——Bai

Linux系统中“/proc”是虚拟文件系统,其中许多文件都保存系统运行状态和相关信息
对于“/proc”中文件可使用文件查看命令浏览其内容,文件中包含系统特定信息:

cat /proc/cpuinfo - CPU (i.e. vendor, Mhz, flags like mmx)
cat /proc/interrupts - 中断
cat /proc/ioports - 设备IO端口
cat /proc/meminfo - 内存信息(i.e. mem used, free, swap size)
cat /proc/partitions - 所有设备的所有分区
cat /proc/pci - PCI设备的信息
cat /proc/swaps - 所有Swap分区的信息
cat /proc/version - Linux的版本号 相当于 uname -r
uname -a - 看系统内核等信息
/*******************
/proc是个伪文件目录,不占用系统空间,及时的反应出内存现在使用的进程情况......应该是比较专业的查看系统情况的命令,或者是最佳之选
********************/
 
 
1.  linux下查看cpu信息
     #cat proc/cpuinfo
 
因为linux 下
/proc/cpuinfo
文件会显示cpu的信息

processor 会从0开始记数 继续下去多个cpu
flags 如果有 ht 说明支持超线程技术

判断物理CPU的个数可以查看
physical id 的值
相同则为同一个物理 CPU

2
linux 查看cpu 命令
 
使用权限:所有使用者    
   
  使用方式:top   [-]   [d   delay]   [q]   [c]   [S]   [s]   [i]   [n]   [b]    
   
  说明:即时显示   process   的动态    
   
  把计    
   
  d   :   改变显示的更新速度,或是在交谈式指令列(   interactive   command)按   s    
  q   :   没有任何延迟的显示速度,如果使用者是有   superuser   的权限,则   top   将会以最高的优先序执行    
  c   :   切换显示模式,共有两种模式,一是只显示执行档的名称,另一种是显示完整的路径与名称S   :   累积模式,会将己完成或消失的子行程   (   dead   child   process   )   的   CPU   time   累积起来    
  s   :   安全模式,将交谈式指令取消,   避免潜在的危机    
  i   :   不显示任何闲置   (idle)   或无用   (zombie)   的行程    
  n   :   更新的次数,完成后将会退出   top    
  b   :   批次档模式,搭配   "n"   参数一起使用,可以用来将   top   的结果输出到档案内    
   
  范例:    
  显示更新十次后退出   ;    
  top   -n   10    
   
  使用者将不能利用交谈式指令来对行程下命令   :    
  top   -s    
   
  将更新显示二次的结果输入到名称为   top.log   的档案里   :    
  top   -n   2   -b   <   top.log    
 
 3 读取文件方式 read vs mmap
一种是read()直接读取;另外一种mmap()内存映射
Read()通过内核缓冲区来读取数据;而mmap()通过把设备文件映射到内存中,绕过了内核缓冲区,最快的磁盘访问往往还是慢于最慢的内存访问,所以mmap()方式加速了I/O访问。
另外,mmap()系统调用使得进程之间通过映射同一文件实现共享内存,各进程可以像访问普通内存一样对文件进行访问,访问时只需要使用指针而不用调用文件操作函数。
 
 
对于大范围IO 读取操作,使用mmap 调用
对于庞大的日记分析操作,可以考虑用mmap优化之.
使用mmap 操作比传统的read 操作好处是减少了一次内核态到用户态的拷贝。但并不适用于有写入的情况,因为mmap 写盘的时候是以页为单位进行操作,页中只要有一个字节被改写,就要往磁盘上面写整个页面的数据
12月19日

仔细选择你的容器

 

条款1:仔细选择你的容器

你知道C++中有很多你可以支配的容器,但是你意识到有多少吗?要确定你没有忽略你的选项,这里有一个快速回顾。

  • 标准STL序列容器:vector、string、deque和list。
  • 标准STL关联容器:set、multiset、map和multimap。
  • 非标准序列容器slist和rope。slist是一个单向链表,rope本质上是一个重型字符串。(“rope”是一个重型“string”。明白了吗?)你可以找到一个关于这些非标准(但常见的)容器的概览在条款50
  • 非标准关联容器hash_set、hash_multiset、hash_map和hash_multimap。我在条款25检验了这些可以广泛获得的基于hash表的容器和标准关联容器的不同点。
  • vector<char>可以作为string的替代品。条款13描述了这个替代品可能会有意义的情况。
  • vector作为标准关联容器的替代品。就像条款23所说的,有时候vector可以在时间和空间上都表现得比标准关联容器好。
  • 几种标准非STL容器,包括数组、bitset、valarray、stack、queue和priority_queue。因为它们是非STL容器,所以在本书中关于它们我说得很少,虽然条款16提到了数组比STL容器更有优势的一种情况,而条款18揭示了为什么bitset可能比vector<bool>要好。值得注意的是,数组可以和STL算法配合,因为指针可以当作数组的迭代器使用。

这是所有的选项,而且可以考虑的范围和可以在它们之间的选择一样丰富。不走运的是,STL的大多数讨论只限于容器世界的一个很窄的视野,忽略了很多关于选择适当容器的问题。就连标准都介入了这个行动,提供了以下的在vector、deque和list之间作选择的指导方案:

vector、list和deque提供给程序员不同的复杂度,因此应该这么用:vector是一种可以默认使用的序列类型,当很频繁地对序列中部进行插入和删除时应该用list,当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构。

如果你主要关心的是算法复杂度,我想这个方案是有理由的建议,但需要关心更多东西。

现在,我们要检查一些可以补充算法复杂度的重要的容器相关问题,但首先我需要介绍一种STL容器的分类方法,它被讨论的次数并不像它应该的那样多。那是连续内存容器和基于节点的容器的区别。

连续内存容器(也叫做基于数组的容器)在一个或多个(动态分配)的内存块中保存它们的元素。如果一个新元素被查入或者已存元素被删除,其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。这种移动影响了效率(参见条款514)和异常安全(就像我们将会看到的)。标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。

基于节点的容器在每个内存块(动态分配)中只保存一个元素。容器元素的插入或删除只影响指向节点的指针,而不是节点自己的内容。所以当有东西插入或删除时,元素值不需要移动。表现为链表的容器——比如list和slist——是基于节点的,所有的标准关联容器也是(它们的典型实现是平衡树)。非标准的hash容器使用不同的基于节点的实现,就像我们将会在条款25中看到的。

利用这个不恰当的术语,我们已经准备好描述一些大多数关于在容器间选择的问题。在这个讨论中,我略过考虑非STL类容器(比如,数组、bitset等),因为毕竟这是本关于STL的书。

  • 你需要“可以在容器的任意位置插入一个新元素”的能力吗?如果是,你需要序列容器,关联容器做不到。
  • 你关心元素在容器中的顺序吗?如果不,hash容器就是可行的选择。否则,你要避免使用hash容器。
  • 必须使用标准C++中的容器吗?如果是,就可以除去hash容器、slist和rope。
  • 你需要哪一类迭代器?如果必须是随机访问迭代器,在技术上你就只能限于vector、deque和string,但你也可能会考虑rope(关于rope的更多信息在条款50)。如果需要双向迭代器,你就用不了slist(参见条款50)和hash容器的一般实现(参见条款25)。
  • 当插入或者删除数据时,是否非常在意容器内现有元素的移动?如果是,你就必须放弃连续内存容器(参见条款5)。
  • 容器中的数据的内存布局需要兼容C吗?如果是,你就只能用vector(参见条款16)。
  • 查找速度很重要吗?如果是,你就应该看看hash容器(参见条款25),排序的vector(参见条款23)和标准的关联容器——大概是这个顺序。
  • 你介意如果容器的底层使用了引用计数吗?如果是,你就得避开string,因为很多string的实现是用引用计数(参见条款13)。你也不能用rope,因为权威的rope实现是基于引用计数的(参见条款50)。于是你得重新审核你的string,你可以考虑使用vector<char>。
  • 你需要插入和删除的事务性(transactional)语义吗?也就是说,你需要有可靠地回退(roll back)插入和删除的能力吗?如果是,你就需要使用基于节点的容器。如果你需要多元素插入(比如,以范围的方式——参见条款5)的事务性语义,你就应该选择list,因为list是唯一提供多元素插入事务性语义的标准容器。事务性语义对于有兴趣写异常安全代码的程序员来说非常重要。(事务性语义也可以在连续内存容器上实现,但会有一个性能开销,而且代码不那么直观。要了解这方面的知识,请参考Sutter的《Exceptional C++》的条款17 [8]。)
  • 你要把迭代器、指针和引用的失效次数减到最少吗?如果是,你就应该使用基于节点的容器,因为在这些容器上进行插入和删除不会使迭代器、指针和引用失效(除非它们指向你删除的元素)。一般来说,在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。
  • 你需要具有有以下特性的序列容器吗:1)可以使用随机访问迭代器;2)只要没有删除而且插入只发生在容器结尾,指针和引用的数据就不会失效?这个一个非常特殊的情况,但如果你遇到这种情况,deque就是你梦想的容器。(有趣的是,当插入只在容器结尾时,deque的迭代器也可能会失效,deque是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。)

这些问题几乎不是事情的完结。比如,它们没有关注不同的容器类型使用不同的内存配置策略(条款1014讨论了这些策略的一些方面)。但是,它们已经足够是你信服了,除非你对元素顺序、标准的一致性、迭代器能力、内存布局和C的兼容性、查找速度、因为引用计数造成的行为不规则、事务性语义的轻松实现和迭代器失效的条件没兴趣,你得在容器操作的算法复杂度上花更多的考虑时间。当然这样的复杂度是重要的,但这离整个故事很远。

当面对容器时,STL给了你很多选项。如果你的视线超越了STL的范围,那就会有更多的选项。在选择一个容器前,要保证考虑了所有你的选项。一个“默认容器”?我不这么认为。


深入研究 C++中的 STL Deque 容器

本文档深入分析了std::deque,并提供了一个指导思想:当考虑到内存分配和执行性能的时候,使用std::deque要比std::vector好。

  介绍

  本文深入地研究了std::deque 容器。本文将讨论在一些情况下使用deque> 比vector更好。读完这篇文章后读者应该能够理解在容量增长的过程中deque 与vector在内存分配和性能的不同表现。由于deque> 和vector的用法很相似,读者可以参考vector 文档中介绍如何使用STL容器。

  Deque总览

  deque和vector一样都是标准模板库中的内容,deque是双端队列,在接口上和vector非常相似,在许多操作的地方可以直接替换。假如读者已经能够有效地使用vector容器,下面提供deque的成员函数和操作,进行对比参考。

  Deque成员函数

函数
描述
c.assign(beg,end)
c.assign(n,elem)
将[beg; end)区间中的数据赋值给c。
将n个elem的拷贝赋值给c。
c.at(idx)
传回索引idx所指的数据,如果idx越界,抛出out_of_range。
c.back()
传回最后一个数据,不检查这个数据是否存在。
c.begin()
传回迭代器重的可一个数据。
c.clear()
移除容器中所有数据。
deque<Elem> c
deque<Elem> c1(c2)
Deque<Elem> c(n)
Deque<Elem> c(n, elem)
Deque<Elem> c(beg,end)
c.~deque<Elem>()
创建一个空的deque。
复制一个deque。
创建一个deque,含有n个数据,数据均已缺省构造产生。
创建一个含有n个elem拷贝的deque。
创建一个以[beg;end)区间的deque。
销毁所有数据,释放内存。
c.empty()
判断容器是否为空。
c.end()
指向迭代器中的最后一个数据地址。
c.erase(pos)
c.erase(beg,end)
删除pos位置的数据,传回下一个数据的位置。
删除[beg,end)区间的数据,传回下一个数据的位置。
c.front()
传回地一个数据。
get_allocator
使用构造函数返回一个拷贝。
c.insert(pos,elem)
c.insert(pos,n,elem)
c.insert(pos,beg,end)
在pos位置插入一个elem拷贝,传回新数据位置。
在pos位置插入>n个elem数据。无返回值。
在pos位置插入在[beg,end)区间的数据。无返回值。
c.max_size()
返回容器中最大数据的数量。
c.pop_back()
删除最后一个数据。
c.pop_front()
删除头部数据。
c.push_back(elem)
在尾部加入一个数据。
c.push_front(elem)
在头部插入一个数据。
c.rbegin()
传回一个逆向队列的第一个数据。
c.rend()
传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num)
重新指定队列的长度。
c.size()
返回容器中实际数据的个数。
C1.swap(c2)
Swap(c1,c2)
将c1和c2元素互换。
同上操作。

  Deque操作

函数
描述
operator[]
返回容器中指定位置的一个引用。


  上面这些特征和vector明显相似,所以我们会提出下面的疑问。

  问题:如果deque和vector可以提供相同功能的时候,我们使用哪一个更好呢?

  回答:如果你要问的话,就使用vector吧。

  或者你给个解释?

  非常高兴你这样问,的确,这并不是无中生有的,事实上,在C++标准里解释了这个问题,下面有一个片断:

  vector在默认情况下是典型的使用序列的方法,对于deque,当使用插入删除操作的时候是一个更好的选择。

  有趣的是,本文就是要非常彻底地理解这句话。

  什么是新的?

  细读上面两张表格,你会发现和vector比较这里增加了两个函数。

  1、c.push_front(elem) —— 在头部插入一个数据。

  2、c.pop_front() —— 删除头部数据。

  调用方法和c.push_back(elem)和c.pop_back()相同,这些将来会告诉我们对于deque> 会非常有用,deque可以在前后加入数据。>

  缺少了什么?

  同时你也会发现相对于vector> 缺少了两个函数,你将了解到deque> 不需要它们。

  1、capacity()—— 返回vector当前的容量。

  2、reserve() —— 给指定大小的vector> 分配空间。

  这里是我们真正研究的开始,这里说明deque> 和vector它们在管理内部存储的时候是完全不同的。deque是大块大块地分配内存,每次插入固定数量的数据。vector是就近分配内存(这可能不是一个坏的事情)。但我们应该关注是,vector每次增加的内存足够大的时候,在当前的内存不够的情况。下面的实验来验证deque不需要capacity()和reserve()> 是非常有道理的。

  实验一 —— 增长的容器

  目的

  目的是通过实验来观察deque和vector在容量增长的时候有什么不同。用图形来说明它们在分配内存和执行效率上的不同。

  描述

  这个实验的测试程序是从一个文件中读取文本内容,每行作为一个数据使用push_back插入到deque> 和vector中,通过多次读取文件来实现插入大量的数据,下面这个类就是为了测试这个内容:


#include <deque>
#include <fstream>
#include <string>
#include <vector>

static enum modes
{
 FM_INVALID = 0,
 FM_VECTOR,
 FM_DEQUE
};

class CVectorDequeTest
{
 public:
  CVectorDequeTest();
  void ReadTestFile(const char* szFile, int iMode)
  {
   char buff[0xFFFF] = {0};
   std::ifstream inFile;
   inFile.open(szFile);
   while(!inFile.eof())
   {
    inFile.getline(buff, sizeof(buff));
    if(iMode == FM_VECTOR)
     m_vData.push_back(buff);
    else if(iMode == FM_DEQUE)
     m_dData.push_back(buff);
   }
   inFile.close();
  }
  virtual ~CVectorDequeTest();
 protected:
  std::vector<std::string> m_vData;
  std::deque<std::string> m_dData;
};


  结果

  测试程序运行的平台和一些条件:

CPU 1.8 GHz Pentium 4
内存 1.50 GB
操作系统 W2K-SP4
文件中的行数 9874
平均每行字母个数
1755.85
读文件的次数
45
总共插入的数据个数 444330



  使用Windows任务管理器来记录执行效率,本程序中使用了Laurent Guinnard 的CDuration类。消耗系统资源如下图:


  注意在vector分配内存的最高峰,vector在分配内存的时候是怎样达到最高值,deque就是这样的,它在插入数据的同时,内存直线增长,首先deque的这种内存分配单元进行回收的话,存在意想不到的后果,我们希望它的分配内存看上去和vector一样,通过上面的测试我们需要进一步的测试,现提出一个假设:假设deque分配的内存不是连续的,一定需要释放和收回内存,我们将这些假设加入后面的测试中,但是首先让我们从执行的性能外表分析一下这个实验。

  究竟分配内存需要消耗多久?

  注意看下面这张图片,vector在不插入数据的时候在进行寻求分配更多内存。


  同时我们也注意到使用push_back插入一组数据消耗的时间,注意,在这里每插入一组数据代表着9874个串,平均每个串的长度是1755.85。


 实验二—— vector::reserve()的资源

  目的

  这个实验的目的是vector在加入大量数据之前调用reserve(),和deque进行比较,看它们的内存分配和执行效率怎么样?

  描述

  本实验中的测试基本上和实验一相同,除了在测试类的构造函数中加入下面这行代码:

m_vData.reserve(1000000);

  结果

  测试程序运行的平台和一些条件:

CPU
1.8 GHz Pentium 4
内存
1.50 GB
操作系统
W2K-SP4
文件中的行数
9874
平均每行字母个数
1755.85
读文件的次数
70
总共插入的数据个数
691180


  使用Windows任务管理器来记录执行效率,本程序中使用了>Laurent Guinnard 的CDuration类。消耗系统资源如下图:


  我们注意到vector不在需要分配花费多余的时间分配内存了,这是由于我们使用了reserve()对于所测试的>691180个数据为我们每一次插入大量数据的时候保留了足够的内存空间,对于deque存储分配的假设,观察这个测试中的内存分配图形和上一个图形,我们需要进一步量化这个测试。

  怎样改良内存分配的性能呢?

  下面这个图例说明随着数据的增加,容量在增加:


  当增加数据的时候对容量的增加在vector和deque执行效率基本一样,然而,vector在插入数据的时候有一些零星的时间消耗,看下面的图例:


  通过统计分析vector和deque在插入平均为>1755.85长度的>9874个数据所花费的时间,下面是总结的表格:


Vector

Deque

Mean

0.603724814 sec

Maximum

0.738313000 sec

Minimum

0.559959000 sec


Std. Dev

0.037795736 sec

6-Sigma

0.226774416 sec

Mean

0.588021114 sec

Maximum

0.615617000 sec

Minimum

0.567503000 sec

Std. Dev

0.009907800 sec

6-Sigma

0.059446800 sec



  实验三——内存回收

  目的

  本实验是对假设deque分配的内存不是临近的,而且很难回收进行量化测试分析。

  描述

  在本实验中再次用到了实验一中的代码,在调用函数中加入记录增加数据执行的效率具体入下面操作:

for(xRun=0; xRun<NUMBER_OF_XRUNS; xRun++)
{
 df = new CVectorDequeTest;
 elapsed_time = 0;

 for(i=0; i<NUMBER_OF_RUNS*xRun; i++)
 {
  cout << "Deque - Run " << i << " of " <<
  NUMBER_OF_RUNS*xRun << "... ";
  df->ReadTestFile("F:\\huge.csv",DF_DEQUE);
  deque_data.push_back(datapoint());
  deque_data.back().time_to_read = df->GetProcessTime();
  elapsed_time += deque_data.back().time_to_read;
  deque_data.back().elapsed_time = elapsed_time;
  cout << deque_data.back().time_to_read << " seconds\n";
 }
 vnElements.push_back(df->GetDequeSize());
 cout << "\n\nDeleting... ";
 del_deque.Start();
 delete df;
 del_deque.Stop();
 cout << del_deque.GetDuration()/1000000.0 << " seconds.\n\n";
 vTimeToDelete.push_back(del_deque.GetDuration()/1000000.0);
}
 

  结果

  本测试和上面两个实验在相同的平台上运行,除了插入的数据由>9874到>691180,需要插入>70次,下面图例显示了>deque在插入数据的时候分配内存的情况,在deque里插入了平均每个长度为>1755.85的字符串。>


  尽管从几个曲线图中看到的实际消耗时间不同,但些曲线图都精确到了>R2=95.15%。所给的数据点都实际背离了下表中统计的曲线图数据:


deque Results

Mean

0.007089269 sec

Maximum

11.02838496 sec

Minimum

-15.25901667 sec

Std. Dev

3.3803636 sec

6-Sigma

20.2821816 sec


  在相同的情况下比较vector的结果是非常有意义的。下面图就是将vector和deque在相同的情况下分配内存消耗的时间比较图:


  这些数据在这个测试中是>R2=82.12%。这或许可以经过每个点反复运行得到更加优化,在这个问题中这些数据适当地标注了这些点,所给的数据点都实际背离了下表中统计的曲线图数据:


vector Results

Mean

-0.007122715sec

Maximum

0.283452127 sec

Minimum

-0.26724459sec

Std. Dev

0.144572356sec

6-Sigma

0.867434136sec

  实验四—— vector::insert() 和 deque::insert() 执行特点比较

  目的

  deque主张使用参数为常量的insert()。但怎么样能和vector::insert()比较一下呢?本实验的目的就是比较一下vector::insert()> 和 deque::insert()的工作特点。

  描述

  在容器的容器多次插入数据,在这里可能不符合你的需求,既然这样你可以使用insert(),试验代码也和实验一基本一样,使用insert()代替push_back(),使用insert(>)来测试。

  结果

  当插入常量给deque的时候,从下图可以看出和vector的对比来。


  注意两张图片中时间轴的不同,这是将>61810个数据插入到容器中。


  实验五——读取容器的性能

  目的

  这个实验将测试vector::at(),vector::operator[],deque::at()和deque::operator[]的性能。首先应该是operator[]比at()效率要高,因为它不进行边界检查,同时也比较vector和deque。

  描述

  这个实验将测试中的容器有1000000个类型为std::string,每个字符串长度为1024的数据,分别使用at()和operator[]这两个操作来访问容器容器的数据,测试它们运行的时间,这个测试执行50次,统计每次执行的结果。

  结果

  我们看到使用vector和deque访问容器中的数据,他们执行的性能差别很小,使用operator[]和at()访问数据的性能差别几乎可以忽略不计,下面是统计的结果:


vector::at()

Mean

1.177088125sec

Maximum

1.189580000sec

Minimum

1.168340000sec

Std. Dev

0.006495193sec

6-Sigma

0.038971158sec

deque::at()

Mean

1.182364375sec

Maximum

1.226860000sec

Minimum

1.161270000sec

Std. Dev

0.016362148sec

6-Sigma

0.098172888sec

vector::operator[]

Mean

1.164221042sec

Maximum

1.192550000sec

Minimum

1.155690000sec

Std. Dev

0.007698520sec

6-Sigma

0.046191120sec

deque::operator[]

Mean

1.181507292sec

Maximum

1.218540000 sec

Minimum

1.162710000sec

Std. Dev

0.010275712sec

6-Sigma

0.061654272sec

  结论

  在这篇文章中我们覆盖了多种不同的情况来选择我们到底是该使用vector还是deque。让我们总结一下测试的结果看下面几个结论。

  当执行大数据量的调用push_back()的时候,记住要调用vector::reserve()。

  在实验一中我们研究了vector和deque在插入数据的情况。通过这些假设,我们可以看出deque分配的空间是预先分配好的,deque维持一个固定增长率,在vector实验中我们考虑到应该调用vecor::reserve()>.然后在下面这个例子验证了我们的假设,在使用vector的时候调用reserve()能够膀子我们预先分配空间,这将是vector一个默认选择的操作。

  当你分配很多内存单元的时候,记住使用deque回收内存要比vector消耗时间多。

  在实验三中我们探讨了vector和deque在回收非邻接内存块上的不同,分别证明了vector在分配内存的时候是线性增长,而deque是指数增长,同样,vector要回收的内存比deque多的多,如果你循环调用了push_back(),那么deque将获取大量的内存,而且是临近的。我们通过测试发现在分配内存单元消耗的时间和vector的时间接近。

  如果你计划使用insert(),或者需要pop_front(),那就使用deque。

  由于vector没有提供pop_front()函数,但在实验四的结果中可以看出没有insert()是非常好的,同时也告诉我们为什么deque在STL类中要作为单独的一个类划分出来。

  对于访问数据,vector::at()效率最高。

  在实验五中统计的数据表示,所有访问数据方法的效率是非常接近的,但是vector::at()效率最高。这是因为最优的平衡图访问时间为最低的六个西格玛值。

  最后

  我希望本文能够带你认识deque,而且对它感兴趣或者一个启发,欢迎继续讨论关于vector和deque任何问题和内容。


vector,list

1 由于不支持随机存储,list既不提供subscript操作符, 也未提供at()函数。
2 lists并未提供存储容量、空间的重新分配等操作函数,因为完全无必要。每个元素都有自己的内存,在删除之前一直有效。
3 lists提供了不少特殊的成员函数。专门用于移动元素。较之同名的STL通用算法,这些函数执行起来更快,因为他们无需拷贝过移动,只要调整若干指针即可。
 
vector基于数组,利于随机访问;list基于链表,插入删除等内存操作方便。
 
  如果我们需要随机访问一个容器则vector   要比list   好得多  
  如果我们已知要存储元素的个数则vector   又是一个比list   好的选择  
  如果我们需要的不只是在容器两端插入和删除元素则list   显然要比vector好  
  除非我们需要在容器首部插入和删除元素否则vector   要比deque好
 
///////////////////////////////////////////////////////
一个很好的vector的例子
  《More Exceptional C++》条款7之学习
        vector和deque的使用
对vector应该当作一个通用的数组 
o下面例子的输出是什么?
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int> &sentence)
{
 vector<int>::iterator i;
 for(i = sentence.begin(); i < sentence.end(); i++)
 {
  cout<<*i<<endl;
 }
 cout<<"print finish"<<endl;
}

int main(int argc, char* argv[])
{
 vector<int> s(999);//1
 s.push_back(1);
 s.erase(s.begin()+10, s.end());
 s.reserve(10);
 //vector<int> (s).swap(s);
 print(s);
 cout<<s.size()<<endl;
 cout<<s.capacity()<<endl;
 return 0;
}
代码通读:
第一句的功能是构造一个数组,数组以默认构造函数填充,int值默认为0,s.size()=999,s.capacity()>=999
第二句的功能在最后插入一个元素, 最后的一个元素值为1,s.size()=1000, 
s.capacity()>=1000,如果容量不够时,则增加一个元素,容量一般为扩大为两倍。
第三句的功能:删除除前10个外的其他元素。
第四句的功能:在这不起任何作用。
reserve()的功能是预留一定的容量,如果容量已足够,则什么也不做。
o 那如何才能缩小容量呢?这正是第五句的功能
vector<int>(s).swap(s);
首先以s为参数构造一个临时未命名对象,拥有s元素的拷贝。
然后与s交换,
s拥有新的内部缓冲区,临时未命名对象拥有较大的缓冲区.
现s的容量已经足够小。
o 那如何完全清除s呢?
vector<int>().swap(s);//只要将临时vector初始化为空即可
难点:临时对象的理解。