《深入理解LINUX内存管理》学习笔记（一）

2009-12-20 13:16| 发布者: admin| 查看: 105| 评论: 0|原作者: 仙剑

引子
为什么要写这个笔记：
1，这本书的中文版翻译了太垃圾，没法阅读。阅读英文原版，可以很好的理解作者的思路。作此笔记备忘
2，一直以来学习LINUX kernel的知识缺乏系统化，借对这本书的学习，系统化的学习一下LINUX kernel。
3，自己一直在做一个too small，too simple的单进程，特权模式，64bit保护模式的称不上OS的ＯＳ，已经做完了bootloader, 构思kernel的实现的时候，困惑在内存管理的实现上，阅读这本书，希望能有利于自己的OS的编写。
4，克服惰性，多读书，希望一天能阅读5页，争取半年内阅读完这本原版700多页的巨著。
不足：
我不可能完全理解LINUX 内存管理的精髓，肯定有很多地方理解错误。希望大家能够指正，以便提高，谢谢。
学习方法：
可能您第一次阅读的时候很多地方都不理解，不用担心。那您可能需要阅读一些文件系统的知识。
或者阅读全部笔记后，再回头阅读，有些地方您就理解了。
言归正传：
一、概要
可用工具CodeViz: 生成代码调用关系图的工具，这个工具我现在还没有去使用，有兴趣的可以自己试试去建立调用关系图。
http://www.csn.ul.ie/~mel/projects/codeviz/
Linux cross reference (LXR): 以web的方式阅读和查找LINUX内核源代码的工具。这个工具安装相当麻烦，我建议直接到它的官方网站直接读代码。
http://lxr.linux.no/linux v2.6.24/
模块LINUX内存管理代码模块主要分为4个部分：

Out of memory 代码在mm/oom_kill.c 貌似用于杀进程的时候对内存的操作

虚拟内存的分配代码在mm/vmalloc.c

物理内存页面分配代码在mm/page_alloc.cVMA（virtual memory addresses)的创建和进程内的内存区域的管理

这些模块，贯穿与其他kernel代码之中，形成更复杂的系统模块，如页面替换策略，buffer的输入输出等

继续
二、物理内存从硬件角度看内存系统，有2种主流的体系结构，不一致的内存访问系统（NUMA），我不知道什么系统在用这样模式，这种系统将内存系统分割成2块区域（BANK），一块是专门给CPU去访问，一块是给外围设备板卡的DMA去访问。另外一种体系结构，是一致的内存访问系统（UMA），PC都是用的这种结构，这种结构的对于CPU和其他外围设备访问的内存在一块内存条上，没有任何不同。
LINUX内核需要支持这2种体系结构。它引入了一个概念称为node，一个node对应一个bank，对于UMA体系的，系统中只有一个node。在LINUX中引入一个数据结构“struct pglist_data”,来描述一个node，定义在
include/linux/mmzone.h
文件中。（这个结构被typedef pg_data_t）
对于NUMA系统来讲，整个系统的内存由一个
node_data
的pg_data_t指针数组来管理。（因为可能有多个node）对于PC这样的UMA系统，使用struct
pglist_data

contig_page_data
，作为系统唯一的node管理所有的内存区域。（UMA系统中中只有一个node）
每个node又被分成多个zone，它们各自描述在内存中的范围。zone由struct zone_struct 数据结构来描述。zone的类型由zone_t表示，有ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM这三种类型。它们之间的用途是不一样的，ZONE_DMA类型的内存区域在物理内存的低端，主要是ISA设备只能用低端的地址做DMA操作。ZONE_NORMAL类型的内存区域直接被内核映射到线性地址空间上面的区域（line address space），以后的章节将详细描述。ZONE_HIGHMEM将保留给系统使用。
在PC系统中，内存区域类型如下分布：
ZONE_DMA 0-16MB
ZONE_NORMAL 16MB-896MB
ZONE_HIGHMEM 896MB-物理内存结束
大多数kernel的操作只使用ZONE_NORMAL区域，
系统内存由很多固定大小的内存块组成的，这样的内存块称作为“页”（PAGE），x86体系结构中，page的大小为4096个字节。每个物理的页由一个struct page的数据结构对象来描述。页的数据结构对象都保存在mem_map全局数组中。从载入内核的低地址内存区域的后面内存区域，也就是ZONE_NORMAL开始的地方的内存的页的数据结构对象，都保存在这个全局数组中。
screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://p.blog.csdn.net/images/p_blog_csdn_net/yrj/图4.14.bmp');}" onmousewheel="return imgzoom(this);" alt="" />

因为ZONE_NORMAL区域的内存空间也是有限的，所以LINUX也支持High memory的访问，这个下面章节会描述，这个章节，将主要描述node，zone，page及它们之间的关联。
Nodes表示node的数据结构为pg_data_t, 也就是struct pglist_data, 这个结构定义在中：
typedef struct
pglist_data
{

struct
zone

node_zones
[
MAX_NR_ZONES
];

struct
zonelist

node_zonelists
[
MAX_ZONELISTS
];

int
nr_zones
;

struct
page
*
node_mem_map
;

struct
bootmem_data
*
bdata
;

unsigned long
node_start_pfn
;

unsigned long
node_present_pages
; /* total number of physical pages */

unsigned long
node_spanned_pages
; /* total size of physical page

range, including holes */

int
node_id
;

wait_queue_head_t

kswapd_wait
;

struct
task_struct
*
kswapd
;

int
kswapd_max_order
;

}
any holes that may exist.可能是包括hold的node可以访问的区域的数量吧。
node_id: node的NODE ID，从0开始
kswapd_wait: node的等待队列
对于单一node的系统，
contig_page_data
是系统唯一的node数据结构对象。
Zone每个zone都由一个struct zone数据结构对象描述。zone对象里面保存着内存使用状态信息，如page使用统计，未使用的内存区域，互斥访问的锁（LOCKS）等。struct zone在中定义（把不关心的NUMA和memory hotplug相关的成员给省略掉了）：
struct zone {
unsigned long free_pages;
unsigned long pages_min, pages_low, pages_high;
unsigned long lowmem_reserve[MAX_NR_ZONES];
struct per_cpu_pageset pageset[NR_CPUS];
spinlock_t lock;
struct free_area free_area[MAX_ORDER];

ZONE_PADDING(_pad1_) //用于字节对齐

spinlock_t lru_lock;
struct list_head active_list;
struct list_head inactive_list;
unsigned long nr_scan_active;
unsigned long nr_scan_inactive;
unsigned long nr_active;
unsigned long nr_inactive;
unsigned long pages_scanned;
int all_unreclaimable;

atomic_t reclaim_in_progress;

atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS];

int prev_priority;

ZONE_PADDING(_pad2_) //用于字节对齐
wait_queue_head_t * wait_table;
unsigned long wait_table_hash_nr_entries;
unsigned long wait_table_bits;

struct pglist_data *zone_pgdat;
unsigned long zone_start_pfn;

unsigned long spanned_pages;
unsigned long present_pages;

const char *name;
} ____cacheline_internodealigned_in_smp;
free_pages：未分配使用的page的数量。
pages_min, pages_low and pages_high： zone对page管理调度的一些参数，下面章节将讲到。
lowmem_reserve[MAX_NR_ZONES]：为了防止一些代码必须运行在低地址区域，所以事先保留一些低地址区域的内存。
pageset[NR_CPUS]： page管理的数据结构对象，内部有一个page的列表(list)来管理。每个CPU维护一个page list，避免自旋锁的冲突。这个数组的大小和NR_CPUS(CPU的数量）有关，这个值是编译的时候确定的。
lock: 对zone并发访问的保护的自旋锁
free_area：页面使用状态的信息，以每个bit标识对应的page是否可以分配
lru_lock: LRU（最近最少使用算法)的自旋锁
reclaim_in_progress: 回收操作的原子锁
active_list: 活跃的page的list
inactive_list: 不活跃的page的list
refill_counter:从活跃的page list中移除的page的数量
nr_active: 活跃的page的数量
nr_inactive: 不活跃的page的数量
pressure：检查回收page的指标
all_unreclaimable: 如果检测2次还是不能回收zone的page的话，则设置为1
pages_scanned: 上次回收page后，扫描过的page的数量。
wait_table：等待一个page释放的等待队列哈希表。它会被wait_on_page(),unlock_page()函数使用. 用哈希表，而不用一个等待队列的原因，防止进程长期等待资源。
wait_table_hash_nr_entries: 哈希表中的等待队列的数量
zone_pgdat: 指向这个zone所在的pglist_data对象。
zone_start_pfn：和node_start_pfn的含义一样。这个成员是用于表示zone中的开始那个page在物理内存中的位置的
present_pages, spanned_pages: 和node中的类似的成员含义一样。
zone: zone的名字，字符串表示： "DMA","Normal" 和"HighMem"
ZONE_PADDING：由于自旋锁频繁的被使用，因此为了性能上的考虑，将某些成员对齐到cache line中，有助于提高执行的性能。使用这个宏，可以确定zone->lock,zone->lru_lock,zone->pageset这些成员使用不同的cache line.
Zone的管理调度的一些参数：（Zone watermarks),
英文直译为zone的水平，打个比喻，就像一个水库，水存量很小的时候加大进水量，水存量达到一个标准的时候，减小进水量，当快要满的时候，可能就关闭了进水口。pages_min, pages_low and pages_high就类似与这个标准。
当系统中可用内存很少的时候，系统代码kswapd被唤醒，开始回收释放page。pages_min, pages_low and pages_high这些参数影响着这个代码的行为。
每个zone有三个水平标准：pages_min, pages_low and pages_high，帮助确定zone中内存分配使用的压力状态。kswapd和这3个参数的互动关系如下图：
screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://p.blog.csdn.net/images/p_blog_csdn_net/yrj/a.jpg');}" onmousewheel="return imgzoom(this);" alt="" />

page_min中所表示的page的数量值，是在内存初始化的过程中调用free_area_init_core()中计算的。这个数值是根据zone中的page的数量除以一个>1的系数来确定的。通常是这样初始化的ZoneSizeInPages/128。
page_low: 当空闲页面的数量达到page_low所标定的数量的时候，kswapd线程将被唤醒，并开始释放回收页面。这个值默认是page_min的2倍。
page_min: 当空闲页面的数量达到page_min所标定的数量的时候, 分配页面的动作和kswapd线程同步运行
page_high: 当空闲页面的数量达到page_high所标定的数量的时候, kswapd线程将重新休眠，通常这个数值是page_min的3倍。
zone的大小的计算
setup_memory()函数计算每个zone的大小：
screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://p.blog.csdn.net/images/p_blog_csdn_net/yrj/c.jpg');}" onmousewheel="return imgzoom(this);" alt="" />

PFN是物理内存以Page为单位的偏移量。系统可用的第一个PFN是min_low_pfn变量，开始与_end标号的后面，也就是kernel结束的地方。在文件mm/bootmem.c中对这个变量作初始化。系统可用的最后一个PFN是max_pfn变量，这个变量的初始化完全依赖与硬件的体系结构。x86的系统中，find_max_pfn()函数通过读取e820表获得最高的page frame的数值。同样在文件mm/bootmem.c中对这个变量作初始化。e820表是由BIOS创建的。
x86中，max_low_pfn变量是由find_max_low_pfn()函数计算并且初始化的，它被初始化成ZONE_NORMAL的最后一个page的位置。这个位置是kernel直接访问的物理内存，也是关系到kernel/userspace通过“PAGE_OFFSET宏”把线性地址内存空间分开的内存地址位置。（原文：This is the physical memory directly accessible
by the kernel and is related to the kernel/userspace split in the linear address space
marked by PAGE OFFSET.）我理解为这段地址kernel可以直接访问，可以通过PAGE_OFFSET宏直接将kernel所用的虚拟地址转换成物理地址的区段。在文件mm/bootmem.c中对这个变量作初始化。在内存比较小的系统中max_pfn和max_low_pfn的值相同。
min_low_pfn, max_pfn和max_low_pfn这3个值，也要用于对高端内存（high memory)的起止位置的计算。在arch/i386/mm/init.c文件中会对类似的highstart_pfn和highend_pfn变量作初始化。这些变量用于对高端内存页面的分配。后面将描述。
Zone等待队列表（zone wait queue table)
当对一个page做I/O操作的时候，I/O操作需要被锁住，防止不正确的数据被访问。进程在访问page前，调用wait_on_page()函数，使进程加入一个等待队列。访问完成后，UnlockPage()函数解锁其他进程对page的访问。其他正在等待队列中的进程被唤醒。每个page都可以有一个等待队列，但是太多的分离的等待队列使得花费太多的内存访问周期。替代的解决方法，就是将所有的队列放在struct zone数据结构中。
也可以有一种可能，就是struct zone中只有一个队列，但是这就意味着，当一个page unlock的时候，访问这个zone里内存page的所有休眠的进程将都被唤醒，这样就会出现拥堵（thundering herd）的问题。建立一个哈希表管理多个等待队列，能解决这个问题，zone->wait_table就是这个哈希表。哈希表的方法可能还是会造成一些进程不必要的唤醒。但是这种事情发生的机率不是很频繁的。下面这个图就是进程及等待队列的运行关系：
screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://p.blog.csdn.net/images/p_blog_csdn_net/yrj/d.JPG');}" onmousewheel="return imgzoom(this);" alt="" />

等待队列的哈希表的分配和建立在free_area_init_core()函数中进行。哈希表的表项的数量在wait_table_size()函数中计算，并且保持在zone->wait_table_size成员中。最大4096个等待队列。最小是NoPages / PAGES_PER_WAITQUEUE的2次方，NoPages是zone管理的page的数量，PAGES_PER_WAITQUEUE被定义256。（原文：For smaller tables, the size of the table
is the minimum power of 2 required to store NoPages / PAGES PER WAITQUEUE
number of queues, where NoPages is the number of pages in the zone and
PAGE PER WAITQUEUE is defined to be 256.）
下面这个公式可以用于计算这个值：

screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://p.blog.csdn.net/images/p_blog_csdn_net/yrj/c.JPG');}" onmousewheel="return imgzoom(this);" alt="" />

zone->wait_table_bits用于计算：根据page 地址得到需要使用的等待队列在哈希表中的索引的算法因子。page_waitqueue()函数负责返回zone中page所对应等待队列。它用一个基于struct page虚拟地址的简单的乘法哈希算法来确定等待队列的。
page_waitqueue()函数用GOLDEN_RATIO_PRIME的地址和“右移zone→wait_table_bits一个索引值”的一个乘积来确定等待队列在哈希表中的索引的。
Zone的初始化
在kernel page table通过paging_init()函数完全建立起z来以后，zone被初始化。下面章节将描述这个。当然不同的体系结构这个过程肯定也是不一样的，但它们的目的却是相同的：确定什么参数需要传递给free_area_init()函数（对于UMA体系结构）或者free_area_init_node()函数（对于NUMA体系结构）。这里省略掉NUMA体系结构的说明。
free_area_init()函数的参数：
unsigned long *zones_sizes: 系统中每个zone所管理的page的数量的数组。这个时候，还没能确定zone中那些page是可以分配使用的（free）。这个信息知道boot memory allocator完成之前还无法知道。

收藏分享邀请

		自动登录	找回密码
密码			注册

《深入理解LINUX内存管理》学习笔记（一）

最新评论

相关分类