kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

Linux的inode的理解

http://www.cnblogs.com/itech/archive/2012/05/15/2502284.html

一、inode是什么?

理解inode,要从文件储存说起。

文件储存在硬盘上,硬盘的最小存储单位叫做"扇区"(Sector)。每个扇区储存512字节(相当于0.5KB)。

操作系统读取硬盘的时候,不会一个个扇区地读取,这样效率太低,而是一次性连续读取多个扇区,即一次性读取一个"块"(block)。这种由多个扇区组成的"块",是文件存取的最小单位。"块"的大小,最常见的是4KB,即连续八个 sector组成一个 block。

文件数据都储存在"块"中,那么很显然,我们还必须找到一个地方储存文件的元信息,比如文件的创建者、文件的创建日期、文件的大小等等。这种储存文件元信息的区域就叫做inode,中文译名为"索引节点"。

二、inode的内容

inode包含文件的元信息,具体来说有以下内容: * 文件的字节数
* 文件拥有者的User ID
* 文件的Group ID
* 文件的读、写、执行权限
* 文件的时间戳,共有三个:ctime指inode上一次变动的时间,mtime指文件内容上一次变动的时间,atime指文件上一次打开的时间。
* 链接数,即有多少文件名指向这个inode
* 文件数据block的位置

可以用stat命令,查看某个文件的inode信息:

1
stat example.txt

总之,除了文件名以外的所有文件信息,都存在inode之中。至于为什么没有文件名,下文会有详细解释。

三、inode的大小

inode也会消耗硬盘空间,所以硬盘格式化的时候,操作系统自动将硬盘分成两个区域。一个是数据区,存放文件数据;另一个是inode区(inode table),存放inode所包含的信息。 每个inode节点的大小,一般是128字节或256字节。inode节点的总数,在格式化时就给定,一般是每1KB或每2KB就设置一个inode。假定在一块1GB的硬盘中,每个inode节点的大小为128字节,每1KB就设置一个inode,那么inode table的大小就会达到128MB,占整块硬盘的12.8%。

查看每个硬盘分区的inode总数和已经使用的数量,可以使用df命令。

1
df -i

查看每个inode节点的大小,可以用如下命令:

1
sudo dumpe2fs -h /dev/hda | grep "Inode size"

由于每个文件都必须有一个inode,因此有可能发生inode已经用光,但是硬盘还未存满的情况。这时,就无法在硬盘上创建新文件。

四、inode号码

每个inode都有一个号码,操作系统用inode号码来识别不同的文件。

这里值得重复一遍,Unix/Linux系统内部不使用文件名,而使用inode号码来识别文件。对于系统来说,文件名只是inode号码便于识别的别称或者绰号。表面上,用户通过文件名,打开文件。实际上,系统内部这个过程分成三步:首先,系统找到这个文件名对应的inode号码;其次,通过inode号码,获取inode信息;最后,根据inode信息,找到文件数据所在的block,读出数据。

使用ls -i命令,可以看到文件名对应的inode号码:

1
ls -i example.txt

五、目录文件

Unix/Linux系统中,目录(directory)也是一种文件。打开目录,实际上就是打开目录文件。

目录文件的结构非常简单,就是一系列目录项(dirent)的列表。每个目录项,由两部分组成:所包含文件的文件名,以及该文件名对应的inode号码。

ls命令只列出目录文件中的所有文件名:

1
ls /etc

ls -i命令列出整个目录文件,即文件名和inode号码:

1
ls -i /etc

如果要查看文件的详细信息,就必须根据inode号码,访问inode节点,读取信息。ls -l命令列出文件的详细信息。

1
ls -l /etc

六、硬链接

一般情况下,文件名和inode号码是"一一对应"关系,每个inode号码对应一个文件名。但是,Unix/Linux系统允许,多个文件名指向同一个inode号码。这意味着,可以用不同的文件名访问同样的内容;对文件内容进行修改,会影响到所有文件名;但是,删除一个文件名,不影响另一个文件名的访问。这种情况就被称为"硬链接"(hard link)。

ln命令可以创建硬链接:

1
ln 源文件 目标文件

运行上面这条命令以后,源文件与目标文件的inode号码相同,都指向同一个inode。inode信息中有一项叫做"链接数",记录指向该inode的文件名总数,这时就会增加1。反过来,删除一个文件名,就会使得inode节点中的"链接数"减1。当这个值减到0,表明没有文件名指向这个inode,系统就会回收这个inode号码,以及其所对应block区域。

这里顺便说一下目录文件的"链接数"。创建目录时,默认会生成两个目录项:".“和”..“。前者的inode号码就是当前目录的inode号码,等同于当前目录的"硬链接";后者的inode号码就是当前目录的父目录的inode号码,等同于父目录的"硬链接"。所以,任何一个目录的"硬链接"总数,总是等于2加上它的子目录总数(含隐藏目录),这里的2是父目录对其的“硬链接”和当前目录下的”.硬链接“。

七、软链接

除了硬链接以外,还有一种特殊情况。文件A和文件B的inode号码虽然不一样,但是文件A的内容是文件B的路径。读取文件A时,系统会自动将访问者导向文件B。因此,无论打开哪一个文件,最终读取的都是文件B。这时,文件A就称为文件B的"软链接"(soft link)或者"符号链接(symbolic link)。

这意味着,文件A依赖于文件B而存在,如果删除了文件B,打开文件A就会报错:"No such file or directory"。这是软链接与硬链接最大的不同:文件A指向文件B的文件名,而不是文件B的inode号码,文件B的inode"链接数"不会因此发生变化。

ln -s命令可以创建软链接。

1
ln -s 源文文件或目录 目标文件或目录

八、inode的特殊作用

由于inode号码与文件名分离,这种机制导致了一些Unix/Linux系统特有的现象。

  1. 有时,文件名包含特殊字符,无法正常删除。这时,直接删除inode节点,就能起到删除文件的作用。

  2. 移动文件或重命名文件,只是改变文件名,不影响inode号码。

  3. 打开一个文件以后,系统就以inode号码来识别这个文件,不再考虑文件名。因此,通常来说,系统无法从inode号码得知文件名。

第3点使得软件更新变得简单,可以在不关闭软件的情况下进行更新,不需要重启。因为系统通过inode号码,识别运行中的文件,不通过文件名。更新的时候,新版文件以同样的文件名,生成一个新的inode,不会影响到运行中的文件。等到下一次运行这个软件的时候,文件名就自动指向新版文件,旧版文件的inode则被回收。

Linux中Buffer cache

http://www.linuxidc.com/Linux/2013-01/78140.htm

buffer cache和page cache的区别

Page cache和buffer cache到底有什么区别呢?很多时候我们不知道系统在做IO操作的时候到底是走了page cache还是buffer cache?其实,buffer cache和page cache是Linux中两个比较简单的概念,在此对其总结说明。

Page cache是vfs文件系统层的cache,例如 对于一个ext3文件系统而言,每个文件都会有一棵radix树管理文件的缓存页,这些被管理的缓存页被称之为page cache。所以,page cache是针对文件系统而言的。例如,ext3文件系统的页缓存就是page cache。Buffer cache是针对设备的,每个设备都会有一棵radix树管理数据缓存块,这些缓存块被称之为buffer cache。通常对于ext3文件系统而言,page cache的大小为4KB,所以ext3每次操作的数据块大小都是4KB的整数倍。Buffer cache的缓存块大小通常由块设备的大小来决定,取值范围在512B~4KB之间,取块设备大小的最大公约数。


http://alanwu.blog.51cto.com/3652632/1112079

Linux中Buffer cache性能问题一探究竟

1, Buffer cache的作用

为了提高磁盘设备的IO性能,我们采用内存作为磁盘设备的cache。用户操作磁盘设备的时候,首先将数据写入内存,然后再将内存中的脏数据定时刷新到磁盘。这个用作磁盘数据缓存的内存就是所谓的buffer cache。在以前的Linux系统中,有很完善的buffer cache软件层,专门负责磁盘数据的缓存。在磁盘设备的上层往往会架构文件系统,为了提高文件系统的性能,VFS层同样会提供文件系统级别的page cache。这样就导致系统中存在两个cache,并且重叠在一起,显得没有必要和冗余。为了解决这个问题,在现有的Linux系统中对buffer cache软件层进行了弱化,并且和page cache进行了整合。Buffer cache和page cache都采用radix tree进行维护,只有当访问裸设备的时候才会使用buffer cache,正常走文件系统的IO不会使用buffer cache。

我们知道ext3文件系统的page cache都是以page页大小为单位的,那么buffer cache中缓存块大小究竟是多大呢?其对性能影响如何呢?这两天我在Linux-2.6.23平台上针对这个问题做了很多实验,得到了一些数据结果,并从源代码分析中得到设置缓存块大小的方法。在此对这个buffer cache的性能问题进行分析说明,供大家讨论。

2, Buffer cache的性能问题

2.1 测试实验

首先让我们来做一个实验,在Linux-2.6.23平台上,采用dd工具对一个块设备进行顺序写操作,可以采用如下的命令格式:

1
dd if=/dev/zero of=/dev/sda2 bs=<request_size> count=100

采用该命令在不同buffer cache块(blk_size)大小配置的情况下测试不同请求大小(req_size)的IO性能,可以得到如下表所示的测试数据:

表:不同buffer cache块大小配置下的吞吐量

将表中的数据做成性能对比图,如下图所示:

从图中可以看出,在请求大小小于Cache块大小的时候,Cache块越大,IO性能越高;但是,请求大小大于Cache块大小之后,性能都有明显的飞跃。

例如,当buffer cache块大小被配置成2KB时,小于2KB的块性能基本都在19MB/s左右;当buffer cache块大小被配置成512B时,小于512B的写性能都保持在5MB/s;当buffer cache块大小被配置成1024B时,小于1KB的写性能基本都保持在9.5MB/s上下。这就说明对于小于cache块大小的small_write,buffer cache越大,其性能会越好,反之,性能越差,这就是buffer cache的作用。

观察发现一旦请求大小大于等于cache块大小之后,性能急剧提升,由于测试工具的IO压力足够大,能够一下子将磁盘性能耗尽。这是为什么呢?其实,当请求块比较小时,对于cache块而言是“局部操作”,这种“局部操作”会引入buffer cache的数据读操作,并且数据读操作和用户写操作存在顺序关系,这就极大的影响了IO的写性能。因此,当请求大小大于cache块时,并且能够和Cache块对齐时,就能够充分利用磁盘的IO带宽,所以就产生了上图中所示的性能飞跃。

看到上图中的测试结果之后,我们就会想在实际应用中,我们该如何选择buffer cache的块大小?如果请求大小是512B时,显然将buffer cache块设置成512比较合适;如果请求大小是256B时,显然将buffer cache块设置成2KB比较合适。所以,个人认为块大小的设置还需要根据实际的应用来决定,不同的应用需要设置不同的块大小,这样才能使整体性能达到最佳。

2.2 Buffer cache块大小

Linux系统在创建块设备的时候是如何设置块大小的呢?这里面涉及到Linux针对块大小设置的一个小小算法。在此结合源码对Linux的这个方法加以说明。

总体来说,Linux决定buffer cache块大小采用的是“最大块大小”的设计思想。Linux根据块设备容量决定buffer cache的块大小,并且将值域限定在512B和4KB之间。当然,这个值域内的元素不是连续的,并且都是2的幂。在这个值域的基础上取块设备大小的最大公约数,这个值就是buffer cache的块大小。这种算法的指导思想就是buffer cache的块越大越好,因此,能够取2KB就不会选择512B。Linux中算法实现代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bd_set_size(struct block_device *bdev, loff_t size)
{
	unsigned bsize = bdev_logical_block_size(bdev);

	bdev->bd_inode->i_size = size;      //size为块设备大小
	while (bsize < PAGE_CACHE_SIZE) {   //bsize不能大于Page size
		if (size & bsize)
			break;
		bsize <<= 1;    //bsize只能取2的幂
	}
	bdev->bd_block_size = bsize;
	/* 设置buffer cache块大小 */
	bdev->bd_inode->i_blkbits = blksize_bits(bsize);
}

3, 小结

本文对buffer cache的性能问题进行了分析,通过实验发现当请求块比较小时,buffer cache块大小对IO性能有很大的影响。Linux根据块设备的容量采用“最大cache块”的思想决定buffer cache的块大小。在实际应用中,我们应该根据应用特征,通过实际测试来决定buffer cache块大小。


通常Linux的“block size”指的是1024 bytes,Linux用1024-byte blocks 作为buffer cache的基本单位。但linux的文件系统的block确不一样。例如ext3系统,block size是4096。使用tune2fs可以查看带文件系统的磁盘分区的相关信息,包括block size。

例如:

1
2
tune2fs -l /dev/sda2 |grep "Block size"
Block size:               4096

另一个工具dumpe2fs也可以。 dumpe2fs /dev/sda2 | grep “Block size”

其实本来这几个概念不是很难,主要是NND他们的名字都一样,都叫“Block Size”。

1.硬件上的 block size, 应该是"sector size",linux的扇区大小是512byte

2.有文件系统的分区的block size, 是"block size",大小不一,可以用工具查看

3.没有文件系统的分区的block size,也叫“block size”,大小指的是1024 byte

4.Kernel buffer cache 的block size, 就是"block size",大部分PC是1024

5.磁盘分区的"cylinder size",用fdisk -l可以查看。

我们来看看fdisk显示的不同的信息,理解一下这几个概念:

1
2
3
4
5
6
7
Disk /dev/hda: 250.0 GB, 250059350016 bytes
255 heads, 63 sectors/track, 30401 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes
   Device Boot    Start       End    Blocks   Id  System
/dev/hda1   *         1      1305  10482381   83  Linux
/dev/hda2          1306      1566   2096482+  82  Linux swap
/dev/hda3          1567     30401 231617137+  83  Linux

8225280就是cylinder size。一共有30401个cylinder。Start和End分别标记的是各个分区的起始cylinder。第4列显示的就是以1024为单位的block(这一列最容易把人搞晕)。为什么“2096482+”有个“+”号呢?因为啊,总size除1024除不尽,是个约数。

Linux内核页回收 swappiness参数

http://www.douban.com/note/349467816/

本文主要尝试解释两个问题:
1. swappiness的确切含义是什么,它对内核进行页回收机制的影响。
2. swappiness设置成0,为什么系统仍然可能会有swap发生。

一. 关于内存分配与页回收(page reclaim)

page reclaim发生的场景主要有两类,一个是kswapd后台线程进行的活动,另一个是direct reclaim,即分配页时没有空闲内存满足,需要立即直接进行的页回收。大体上内存分配的流程会分为两部分,一部分是fast path,另一部分是slow path,通常内存使用非紧张情况下,都会在fast path就可以满足要求。并且fast path下的内存分配不会出现dirty writeback及swap等页回收引起的IO阻塞情况。

fast path大体流程如下:

1.如果系统挂载使用了memory cgroup,则首先检查是否超过cgroup限额,如果超过则进行direct reclaim,通过do_try_to_free_pages完成。如果没超过则进行cgroup的charge工作(charge是通过两阶段提交完成的,这里不展开了)。

2.从本地prefered zone内存节点查找空闲页,需要判断是否满足系统watermark及dirty ratio的要求,如果满足则从buddy system上摘取相应page,否则尝试对本地prefered zone进行页回收,本次fast path下页回收只会回收clean page,即不会考虑dirty page以及mapped page,这样就不会产生任何swap及writeback,即不会引起任何blocking的IO操作,如果这次回收仍然无法满足请求的内存页数目则进入slow path

slow path大体流程如下:

  1. 首先唤醒kswapd进行page reclaim后台操作。

  2. 重新尝试本地prefered zone进行分配内存,如果失败会根据请求的GFP相关参数决定是否尝试忽略watermark, dirty ratio以及本地节点分配等要求进行再次重试,这一步中如果分配页时有指定__GFP_NOFAIL标记,则分配失败会一直等待重试。

  3. 如果没有__GFP_NOFAIL标记,则会需开始进行page compact及page direct reclaim操作,之后如果仍然没有可用内存,则进入OOM流程。

相关内容可以参阅内核代码__alloc_pages函数的逻辑,另外无论page reclaim是由谁发起的,最终都会统一入口到shrink_zone,即针对每个zone独立进行reclaim操作,最终会进入shrink_lruvec函数,进行每个zone相应page lru链表的扫描与回收操作。

二. 关于页回收的一些背景知识

页回收大体流程会先在每个zone上扫描相应的page链表,主要包括inactive anon/active anon(匿名页链表)以及inactive file/active file链表(file cache/映射页链表),一共四条链表,我们所有使用过的page在被回收前基本是保存在这四条链表中的某一条中的(还有一部分在unevictable链表中,忽略),根据其被引用的次数会决定其处于active还是inactive链表中,根据其类型决定处于anon还是file链表中。

页回收总体会扫描逐个内存节点的所有zone,然后先扫描active,将不频繁访问的页挪到inactive链表中,随后扫描inactive链表,会将其中被频繁引用的页重新挪回到active中,确认不频繁的页则最终被回收,如果是file based的页则根据是否clean进行释放或回写(writeback,filecache则直接释放),如果是anon则进行swap,所以本文实际关心的是swappiness参数对anon链表扫描的影响。

另外还需要了解前面描述的四个链表原来是放在zone数据结构上的,后来引入了mem_cgroup则,重新定义了一组mem_cgroup_per_zone/mem_cgroup_per_node的数据结构,这四个链表同时定义在这组数据结构上,如果系统开启了mem cgroup则使用后者,否则用前者。

另外再重点说下swap只是page reclaim的一种处理措施,主要针对anon page,我们最终来看下swappiness的确切含义

三. swappiness对page reclaim的确切影响

page reclaim逻辑中对前面所述四个链表进行扫描的逻辑在vmscan.c中的get_scan_count函数内,该函数大部分逻辑注释写得非常清楚,我们简单梳理下,主要关注scan_balance变量的取值:

  1. 首先如果系统禁用了swap或者没有swap空间,则只扫描file based的链表,即不进行匿名页链表扫描 代码:
1
2
3
4
if (!sc->may_swap || (get_nr_swap_pages() <= 0)) {
	scan_balance = SCAN_FILE;
	goto out;
}
  1. 如果当前进行的不是全局页回收(cgroup资源限额引起的页回收),并且swappiness设为0,则不进行匿名页链表扫描,这个是没得商量,这里swappiness值直接决定了是否有swap发生,设成0则肯定不会发生,另外需要注意,这种情况下需要设置的是cgroup配置文件memory.swappiness,而不是全局的sysctl vm.swappiness 代码:
1
2
3
4
if (!global_reclaim(sc) && !vmscan_swappiness(sc)) {
	scan_balance = SCAN_FILE;
	goto out;
}
  1. 如果进行链表扫描前设置的priority(这个值决定扫描多少分之一的链表元素)为0,且swappiness非0,则可能会进行swap 代码:
1
2
3
4
if (!sc->priority && vmscan_swappiness(sc)) {
	scan_balance = SCAN_EQUAL;
	goto out;
}
  1. 如果是全局页回收,并且当前空闲内存和所有file based链表page数目的加和都小于系统的high watermark,则必须进行匿名页回收,则必然会发生swap,可以看到这里swappiness的值如何设置是完全无关的,这也解释了为什么其为0,系统也会进行swap的原因,另外最后我们会详细解释系统page watermark是如何计算的。 代码:
1
2
3
4
5
6
7
8
9
10
11
12
anon = get_lru_size(lruvec, LRU_ACTIVE_ANON) +
		get_lru_size(lruvec, LRU_INACTIVE_ANON);
file = get_lru_size(lruvec, LRU_ACTIVE_FILE) +
		get_lru_size(lruvec, LRU_INACTIVE_FILE);

if (global_reclaim(sc)) {
	free = zone_page_state(zone, NR_FREE_PAGES);
	if (unlikely(file + free <= high_wmark_pages(zone))) {
		scan_balance = SCAN_ANON;
		goto out;
	}
}
  1. 如果系统inactive file链表比较充足,则不考虑进行匿名页的回收,即不进行swap 代码:
1
2
3
4
if (!inactive_file_is_low(lruvec)) {
	scan_balance = SCAN_FILE;
	goto out;
}
  1. 最后一种情况则要根据swappiness值与之前统计的file与anon哪个更有价值来综合决定file和anon链表扫描的比例,这时如果swappiness设置成0,则也不会扫描anon链表,即不进行swap,代码比较多,不再贴出。

四. 系统内存watermark的计算

前面看到系统内存watermark对页回收机制是有决定影响的,其实在内存分配中也会频繁用到这个值,确切的说它有三个值,分别是low,min和high,根据分配页时来指定用哪个,如果系统空闲内存低于相应watermark则分配会失败,这也是进入slow path或者wakeup kswapd的依据。

实际这个值的计算是通过sysctl里的vm.min_free_kbytes来决定的,大体的计算公式如下:

1
2
3
4
5
6
pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
tmp = (u64)pages_min * zone->managed_pages;
do_div(tmp, lowmem_pages);
zone->watermark[WMARK_MIN] = tmp;
zone->watermark[WMARK_LOW] = min_wmark_pages(zone) + (tmp >> 2);
zone->watermark[WMARK_HIGH] = min_wmark_pages(zone) + (tmp >> 1);

即根据min_free_kbytes的值按照每个zone管理页面的比例算出zone的min_watermark,然后再加min的1/4就是low,加1/2就是high了

总结:

swappiness的值是个参考值,是否会发生swap跟当前是哪种page reclaim及系统当前状态都有关系,所以设置了swappiness=0并不代表一定没有swap发生,同时设为0也确实会可能发生OOM。

个人仍然认为线上环境设置swappiness=0是没有任何问题的。

Linux swap实现

http://blog.csdn.net/freas_1990/article/details/9090601

swap是现代Unix操作系统一个非常重要的特性。尤其在大型数据库服务器上,swap往往是性能首要查看指标。

通俗的说法,在Unix里,将开辟一个磁盘分区,用作swap,这块磁盘将作为内存的的替代品,在内存不够用的时候,把一部分内存空间交换到磁盘上去。

而Unix的swap功能也成为了Unixer们认为Unix由于windows的一个论据(?)。在Unix里,swap一般被认为设置为内存的2倍大小。这个2倍大小的指标出自哪里,到目前为止我也没有找到(?如果你找到了可以留言或发私信)。

不过,在内存不断掉价的今天,swap的功效已经越来越弱化了——在2013年6月13日23:01,如果一个OLTP系统的swap使用超过了2G以上,基本上可以对这个系统的性能产生怀疑了。swap并不是一种优化机制,而是一种不得已而为之的手段,防止在内存紧张的时刻,操作系统性能骤降以至瞬间崩溃。swap的价值主要体现在可以把这个崩溃的时间提升至几小时到几十个小时不等。

本文主要关注CPU访问一个内存page时,发现该page不在内存中的情况。废话不多说了,先把swap的核心函数调用栈贴一下。

当CPU检查一个页目录项/页表项的Present标志位时,如果发现该标志位为0,则表示相应的物理页面不在内存。此时,CPU会被激发“页面异常”(中断中的fault),而去执行一段代码。

至于到底是这个内存页面需要重新构建、还是页面的内容是存储到磁盘上去了,CPU本身是不关心的,CPU只知道中断条件发生了,要根据中断描述符跳转到另外一段代码去执行,而真正的swap或者是真的缺页的智能判断是在这段中断服务程序里做的——真正的技术是在这段中断服务程序里。(所以我在《中断——一鞭一条痕(下)》里说,作为一个初学者,不必深究中断(interrupt)、异常(exception)、陷阱(trap)这三个概念)

pte_present()函数会检查当前页面的描述entry的present标志位,查看该page是否在内存中。如果不在内存中,调用pte_none()判断是否建立了页目录、页表映射。如果连映射都没建立,说明是“真没在内存中”,需要从头建立映射关系。如果建立了映射关系,说明此时,该页面被暂时存储到磁盘上去了,应该到磁盘上去把该page取回来放到内存里。

如何去取呢?

如何到磁盘取一个page的数据到内存中去,这是一个多么熟悉的概念!思考一下Oracle的内存管理,一个block如何读入到SGA的buffer cache里去吧。其实这几十年来,核心的本源技术无论是在操作系统内核还是在数据库内核里,都是通用的,都是用来极大限度提升CPU任务管理能力、内存管理效率的,所有的理念、技术都是通用的——如果你站在一个系统程序猿的角度来思考,一定能明白的——不要把自己局限在一个产品里,无论这个产品是数据库、CPU、还是操作系统,这些看似绚烂神秘的技术在30年以前,已经被人反复的讨论和意淫过了。

接下来就到了核心部分了——do_swap_page()函数。

源代码如下(linux/mm/memory.c line 2022~1060):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static int do_swap_page(struct mm_struct * mm,
	struct vm_area_struct * vma, unsigned long address,
	pte_t * page_table, swp_entry_t entry, int write_access)
{ 
	struct page *page = lookup_swap_cache(entry);
	pte_t pte;

	if (!page) {
		lock_kernel();
		swapin_readahead(entry);
		page = read_swap_cache(entry);
		unlock_kernel();
		if (!page)
			return -1;

		flush_page_to_ram(page);
		flush_icache_page(vma, page);
	}

	mm->rss++;

	pte = mk_pte(page, vma->vm_page_prot);

	/*
	 * Freeze the "shared"ness of the page, ie page_count + swap_count.
	 * Must lock page before transferring our swap count to already
	 * obtained page count.
	 */
	lock_page(page);
	swap_free(entry);
	if (write_access && !is_page_shared(page))
		pte = pte_mkwrite(pte_mkdirty(pte));
	UnlockPage(page);

	set_pte(page_table, pte);
	/* No need to invalidate - it was non-present before */
	update_mmu_cache(vma, address, pte);
	return 1;   /* Minor fault */
}

这里有2个参数需要重点关注,一个是(pte_t *)page_table,另外一个是(swp_entry_t*)entry

当一个page在内存中,不需要swap in时,描述该page的entry是pte_t类型的;反之,是swp_entry_t类型。

swap_entry_t(include/linux/shmem_fs.h)定义如下:

1
2
3
typedef struct {
	unsigned long val;
} swp_entry_t;

问题出来了,既然都进入do_swap_page()函数了,说明是需要swap in了,为什么还会传入一个pte_t类型的变量呢?

答案是,当在do_swap_page()之前,page是在磁盘上的,描述类型是swp_entry_t,而do_swap_page()之后,页面已经从磁盘交换到内存了,这个时候描述类型就是pte_t了。

至于lookup_swap_cache、swapin_readahead(预读——read ahead)等函数就不一一分析了,从名字就可以看出其技巧了。都是些在数据库server上的常用技巧。如果你是行家,一眼就能看出来。

Linux Cache 机制探究

http://www.penglixun.com/tech/system/linux_cache_discovery.html

相关源码主要在:
./fs/fscache/cache.c Cache实现的代码
./mm/slab.c SLAB管理器代码
./mm/swap.c 缓存替换算法代码
./mm/mmap.c 内存管理器代码
./mm/mempool.c 内存池实现代码

0. 预备:Linux内存管理基础

创建进程fork()、程序载入execve()、映射文件mmap()、动态内存分配malloc()/brk()等进程相关操作都需要分配内存给进程。不过这时进程申请和获得的还不是实际内存,而是虚拟内存,准确的说是“内存区域”。Linux除了内核以外,App都不能直接使用内存,因为Linux采用Memory Map的管理方式,App拿到的全部是内核映射自物理内存的一块虚拟内存。malloc分配很少会失败,因为malloc只是通知内存App需要内存,在没有正式使用之前,这段内存其实只在真正开始使用的时候才分配,所以malloc成功了并不代表使用的时候就真的可以拿到这么多内存。据说Google的tcmalloc改进了这一点。

进程对内存区域的分配最终多会归结到do_mmap()函数上来(brk调用被单独以系统调用实现,不用do_mmap())。内核使用do_mmap()函数创建一个新的线性地址区间,如果创建的地址区间和一个已经存在的地址区间相邻,并且它们具有相同的访问权限的话,那么两个区间将合并为一个。如果不能合并,那么就确实需要创建一个新的VMA了。但无论哪种情况, do_mmap()函数都会将一个地址区间加入到进程的地址空间中,无论是扩展已存在的内存区域还是创建一个新的区域。同样释放一个内存区域使用函数do_ummap(),它会销毁对应的内存区域。

另一个重要的部分是SLAB分配器。在Linux中以页为最小单位分配内存对于内核管理系统物理内存来说是比较方便的,但内核自身最常使用的内存却往往是很小(远远小于一页)的内存块,因为大都是一些描述符。一个整页中可以聚集多个这种这些小块内存,如果一样按页分配,那么会被频繁的创建/销毁,开始是非常大的。

为了满足内核对这种小内存块的需要,Linux系统采用了SLAB分配器。Slab分配器的实现相当复杂,但原理不难,其核心思想就是Memory Pool。内存片段(小块内存)被看作对象,当被使用完后,并不直接释放而是被缓存到Memory Pool里,留做下次使用,这就避免了频繁创建与销毁对象所带来的额外负载。

Slab技术不但避免了内存内部分片带来的不便,而且可以很好利用硬件缓存提高访问速度。但Slab仍然是建立在页面基础之上,Slab将页面分成众多小内存块以供分配,Slab中的对象分配和销毁使用kmem_cache_alloc与kmem_cache_free。

关于SALB分配器有一份资料:http://lsec.cc.ac.cn/~tengfei/doc/ldd3/ch08s02.html

关于内存管理的两份资料:http://lsec.cc.ac.cn/~tengfei/doc/ldd3/ch15.html

http://memorymyann.javaeye.com/blog/193061

1. Linux Cache的体系

在 Linux 中,当App需要读取Disk文件中的数据时,Linux先分配一些内存,将数据从Disk读入到这些内存中,然后再将数据传给App。当需要往文件中写数据时,Linux先分配内存接收用户数据,然后再将数据从内存写到Disk上。Linux Cache 管理指的就是对这些由Linux分配,并用来存储文件数据的内存的管理。

下图描述了 Linux 中文件 Cache 管理与内存管理以及文件系统的关系。从图中可以看到,在 Linux 中,具体的文件系统,如 ext2/ext3/ext4 等,负责在文件 Cache和存储设备之间交换数据,位于具体文件系统之上的虚拟文件系统VFS负责在应用程序和文件 Cache 之间通过 read/write 等接口交换数据,而内存管理系统负责文件 Cache 的分配和回收,同时虚拟内存管理系统(VMM)则允许应用程序和文件 Cache 之间通过 memory map的方式交换数据,FS Cache底层通过SLAB管理器来管理内存。

下图则非常清晰的描述了Cache所在的位置,磁盘与VFS之间的纽带。

2. Linux Cache的结构

在 Linux 中,文件 Cache 分为两层,一是 Page Cache,另一个 Buffer Cache,每一个 Page Cache 包含若干 Buffer Cache。内存管理系统和 VFS 只与 Page Cache 交互,内存管理系统负责维护每项 Page Cache 的分配和回收,同时在使用 memory map 方式访问时负责建立映射;VFS 负责 Page Cache 与用户空间的数据交换。而具体文件系统则一般只与 Buffer Cache 交互,它们负责在外围存储设备和 Buffer Cache 之间交换数据。读缓存以Page Cache为单位,每次读取若干个Page Cache,回写磁盘以Buffer Cache为单位,每次回写若干个Buffer Cache。 Page Cache、Buffer Cache、文件以及磁盘之间的关系如下图所示。

Page 结构和 buffer_head 数据结构的关系如下图所示。Page指向一组Buffer的头指针,Buffer的头指针指向磁盘块。在这两个图中,假定了 Page 的大小是 4K,磁盘块的大小是 1K。

在 Linux 内核中,文件的每个数据块最多只能对应一个 Page Cache 项,它通过两个数据结构来管理这些 Cache 项,一个是 Radix Tree,另一个是双向链表。Radix Tree 是一种搜索树,Linux 内核利用这个数据结构来通过文件内偏移快速定位 Cache 项,图 4 是 radix tree的一个示意图,该 radix tree 的分叉为4(22),树高为4,用来快速定位8位文件内偏移。Linux(2.6.7) 内核中的分叉为 64(26),树高为 6(64位系统)或者 11(32位系统),用来快速定位 32 位或者 64 位偏移,Radix tree 中的每一个到叶子节点的路径上的Key所拼接起来的字串都是一个地址,指向文件内相应偏移所对应的Cache项。

查看Page Cache的核心数据结构struct address_space就可以看到上述结构(略去了无关结构):

1
2
3
4
5
6
7
struct address_space  {
	struct inode             *host;              /* owner: inode, block_device */
	struct radix_tree_root      page_tree;         /* radix tree of all pages */
	unsigned long           nrpages;  /* number of total pages */
	struct address_space       *assoc_mapping;      /* ditto */
	......
} __attribute__((aligned(sizeof(long))));

下面是一个Radix Tree实例:

另一个数据结构是双向链表,Linux内核为每一片物理内存区域(zone) 维护active_list和inactive_list两个双向链表,这两个list主要用来实现物理内存的回收。这两个链表上除了文件Cache之 外,还包括其它匿名(Anonymous)内存,如进程堆栈等。

相关数据结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
truct page{
	struct list_head list;   //通过使用它进入下面的数据结构free_area_struct结构中的双向链队列
	struct address_space * mapping;   //用于内存交换的数据结构
	unsigned long index;//当页面进入交换文件后
	struct page *next_hash; //自身的指针,这样就可以链接成一个链表
	atomic t count; //用于页面交换的计数,若页面为空闲则为0,分配就赋值1,没建立或恢复一次映射就加1,断开映射就减一
	unsigned long flags;//反应页面各种状态,例如活跃,不活跃脏,不活跃干净,空闲
	struct list_head lru;
	unsigned long age; //表示页面寿命
	wait_queue_head_t wait;
	struct page ** pprev_hash;
	struct buffer_head * buffers;
	void * virtual
	struct zone_struct * zone; //指向所属的管理区
}
typedef struct free_area_struct {
	struct list_head free_list;   //linux 中通用的双向链队列
	unsigned int * map;
} free_area_t;
typedef struct zone_struct{
	spinlock_t        lock;
	unsigned long offset;  //表示该管理区在mem-map数组中,起始的页号
	unsigned long free pages;
	unsigned long inactive_clean_pages;
	unsigned long inactive_dirty_pages;
	unsigned pages_min, pages_low, pages_high;
	struct list_head inactive_clean_list;   //用于页面交换的队列,基于linux页面交换的机制。这里存贮的是不活动“干净”页面
	free_area_t free_area[MAX_ORDER]; //一组“空闲区间”队列,free_area_t定义在上面,其中空闲下标表示的是页面大小,例如:数组第一个元素0号,表示所有区间大小为2的 0次方的页面链接成的双向队列,1号表示所有2的1次方页面链接链接成的双向队列,2号表示所有2的2次方页面链接成的队列,其中要求是这些页面地址连续
	char * name;
	unsigned long size;
	struct pglist_data * zone_pgdat;   //用于指向它所属的存贮节点,及下面的数据结构
	unsigned  long  zone_start_paddr;
	unsigned  long    zone_start_mapnr;
	struct page * zone_mem_map;
} zone_t;

3. Cache预读与换出

Linux 内核中文件预读算法的具体过程是这样的: 对于每个文件的第一个读请求,系统读入所请求的页面并读入紧随其后的少数几个页面(不少于一个页面,通常是三个页 面),这时的预读称为同步预读。对于第二次读请求,如果所读页面不在Cache中,即不在前次预读的group中,则表明文件访问不是顺序访问,系统继续 采用同步预读;如果所读页面在Cache中,则表明前次预读命中,操作系统把预读group扩大一倍,并让底层文件系统读入group中剩下尚不在 Cache中的文件数据块,这时的预读称为异步预读。无论第二次读请求是否命中,系统都要更新当前预读group的大小。

此外,系统中定义了一个 window,它包括前一次预读的group和本次预读的group。任何接下来的读请求都会处于两种情况之一:

第一种情况是所请求的页面处于预读 window中,这时继续进行异步预读并更新相应的window和group;

第二种情况是所请求的页面处于预读window之外,这时系统就要进行同步 预读并重置相应的window和group。

下图是Linux内核预读机制的一个示意图,其中a是某次读操作之前的情况,b是读操作所请求页面不在 window中的情况,而c是读操作所请求页面在window中的情况。

Linux内核中文件Cache替换的具体过程是这样的:刚刚分配的Cache项链入到inactive_list头部,并将其状态设置为active,当内存不够需要回收Cache时,系统首先从尾部开始反向扫描 active_list并将状态不是referenced的项链入到inactive_list的头部,然后系统反向扫描inactive_list,如果所扫描的项的处于合适的状态就回收该项,直到回收了足够数目的Cache项。其中Active_list的含义是热访问数据,及多次被访问的,inactive_list是冷访问数据,表示尚未被访问的。如果数据被访问了,Page会被打上一个Refrence标记,如果Page没有被访问过,则打上Unrefrence标记。这些处理在swap.c中可以找到。 下图也描述了这个过程。

下面的代码描述了一个Page被访问它的标记为变化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * Mark a page as having seen activity.
 *
 * inactive,unreferenced        ->      inactive,referenced
 * inactive,referenced          ->      active,unreferenced
 * active,unreferenced          ->      active,referenced
 */
void mark_page_accessed(struct page *page)
{
	if (!PageActive(page) && !PageUnevictable(page) &&
			PageReferenced(page) && PageLRU(page)) {
		activate_page(page);
		ClearPageReferenced(page);
	} else if (!PageReferenced(page)) {
		SetPageReferenced(page);
	}
}

参考文章:

http://lsec.cc.ac.cn/~tengfei/doc/ldd3/

http://memorymyann.javaeye.com/blog/193061

http://www.cublog.cn/u/20047/showart.php?id=121850

http://blog.chinaunix.net/u2/74194/showart_1089736.html

关于内存管理,Linux有一个网页:http://linux-mm.org/