本文为原创,转载请注明:http://blog.chinaunix.net/uid/26772321.html
分页和分段
先看一幅图
也就是我们实际中编码时遇到的内存地址并不是对应于实际内存上的地址,我们编码中使用的地址是一个逻辑地址,会通过分段和分页这两个机制把它转为物理地址。而由于linux使用的分段机制有限,可以认为,linux下的逻辑地址=线性地址。也就是,我们编码使用的是线性地址,之后只需要经过一个分页机制就可以把这个地址转为物理地址了。所以我们更重要的可能是去说明一下linux的分页模型。
系统会将整个物理内存分为多个页框,每个页框大小一般是4K(硬件允许情况下也可设置为4M),也就是如果我们有1GB的物理内存,系统就会将这个物理内存分为262144个页框。当我们提供一个线性地址时,系统就会通过分页机制将这个线性地址转换为对应于某个物理页中的某个内存地址。下图是linux的分页模型
linux采用四级分页模型,这四种页表是:页全局目录(PGD)、页上级目录(PUD)、页中间目录(PMD)、页表(PTE)。这里的所有页全局目录、页上级目录、页中间目录、页表,它们的大小都是一个页。linux下各个硬件上并不一定都是使用四级目录的,当使用于没有启动物理地址扩展的32位系统上时,只使用二级页表,linux会把页上级目录和页中间目录置空。而在启用了物理地址扩展的32位系统上时,linux使用的是三级页表,页上级目录被置空。而在64位系统上,linux根据硬件的情况会选择三级页表或者四级页表。这个整个由线性地址转换到物理地址的过程,是由CPU自动进行的。
每个进程都有它自己的页全局目录,当进程运行时,系统会将该进程的页全局目录基地址保存到cr3寄存器中;而当进程被换出时,会将这个cr3保存的页全局目录地址保存到进程描述符中。之后我们还会介绍一个cr2寄存器,用于缺页异常处理的。当进程运行时,它使用的是它自己的一套页表,当它通过系统调用或陷入内核态时,使用的是内核页表,实际上,对于所有的进程页表来说,它们的线性地址0xC0000000以上所涉及到的页表都是主内核页全局目录(保存在init_mm.pgd),它们的内容等于主内核页全局目录的相应表项,这样就实现了所有进程的进程空间相互隔离,但是内核空间相互共享的情况。当某个进程修改了内核页表的一些映射情况后,系统只会相应的修改主内核页全局目录中的表项(只能修改高端内存中非连续内存区的映射),当其他进程访问这些线性地址时,会出现缺页异常,然后修改该进程的页表项重新映射该地址。
因为说到每个进程都有它自己的页全局目录,如果有100个进程,内存中就要保存100个进程的整个页表集,看起来会耗费相当多的内存。实际上,只有进程使用到的情况下系统才会分配给进程一条路径,比如我们要求访问一个线性地址,但是这个地址可能对应的页上级目录、页中间目录、页表和页都不存在的,这时系统会产生一个缺页异常,在缺页异常处理中再给进程的这个线性地址分配页上级目录、页中间目录、页表和页所需的物理页框。
地址空间
一个线性地址经过分页机制转为一个对应的物理地址,我们称之为映射,比如我们的一个线性地址0x00000001经过分页机制处理后,对应的物理地址可能是0xffffff01。
在linux系统中分两个地址空间,一个是进程地址空间,一个是内核地址空间。对于每个进程来说,他们都有自己的大小为3G的进程地址空间,这些进程地址空间是相互隔离的,也就是进程A的0x00000001线性地址和进程B的0x00000001线性地址并不是同一个地址,进程A也不能通过自己的进程空间直接访问进程B的进程地址空间。而当线性地址大于3G时(也就是0xC0000000),这里的线性地址属于内核空间,内核地址空间的大小为1G,地址从0xC0000000到0xFFFFFFFF。在内核地址空间中,内核会把前896MB的线性地址直接与物理地址的前896MB进行映射,也就是说,内核地址空间的线性地址0xC0000001所对应的物理地址为0x00000001,它们之间相差一个0xC0000000。
linux内核会将物理内存分为3个管理区,分别是:
-
ZONE_DMA:包含0MB~16MB之间的内存页框,可以由老式基于ISA的设备通过DMA使用,直接映射到内核的地址空间。
-
ZONE_NORMAL:包含16MB~896MB之间的内存页框,常规页框,直接映射到内核的地址空间。
-
ZONE_HIGHMEM:包含896MB以上的内存页框,不进行直接映射,可以通过永久映射和临时映射进行这部分内存页框的访问。
整个结构如下图
对于ZONE_DMA和ZONE_NORMAL这两个管理区,内核地址都是进行直接映射,只有ZONE_HIGHMEM管理区系统在默认情况下是不进行直接映射的,只有在需要使用的时候进行映射(临时映射或者永久映射)。
结点和管理区描述符
为了用于NUMA架构,使用了node用来描述一个地方的内存。NUMA大致就是使众多服务器像单一系统一样地运行,这样每台服务器都有自己的内存,每台服务器的内存就是一个node。对于我们PC来说,一台PC就是一个node。node用struct pglist_data结构表示:
-
/* 内存结点描述符,所有的结点描述符保存在 struct pglist_data *node_data[MAX_NUMNODES] 中 */
-
typedef struct pglist_data {
-
/* 管理区描述符的数组 */
-
struct zone node_zones[MAX_NR_ZONES];
-
/* 页分配器使用的zonelist数据结构的数组,将所有结点的管理区按一定的关联链接成一个链表,分配内存时会按照此链表的顺序进行分配 */
-
struct zonelist node_zonelists[MAX_ZONELISTS];
-
/* 结点中管理区的个数 */
-
int nr_zones;
-
#ifdef CONFIG_FLAT_NODE_MEM_MAP /* means !SPARSEMEM */
-
/* 结点中页描述符的数组,包含了此结点中所有页框描述符,实际分配是是一个指针数组 */
-
struct page *node_mem_map;
-
#ifdef CONFIG_MEMCG
-
/* 用于资源限制机制 */
-
struct page_cgroup *node_page_cgroup;
-
#endif
-
#endif
-
#ifndef CONFIG_NO_BOOTMEM
-
/* 用在内核初始化阶段 */
-
struct bootmem_data *bdata;
-
#endif
-
#ifdef CONFIG_MEMORY_HOTPLUG
-
/* 自旋锁 */
-
spinlock_t node_size_lock;
-
#endif
-
/* 结点中第一个页框的下标,在numa系统中,页框会有两个序号,所有页框的一个序号,还有就是在此结点中的一个序号
-
* 比如结点2中的页框1,它在结点2中的序号是1,但是在所有页框中的序号是1001,这个变量就是保存这个结点首页框的序号1000,用于方便转换
-
*/
-
unsigned long node_start_pfn;
-
/* 内存结点的大小,不包括洞(以页框为单位) */
-
unsigned long node_present_pages;
-
/* 结点的大小,包括洞(以页框为单位) */
-
unsigned long node_spanned_pages;
-
-
/* 结点标识符 */
-
int node_id;
-
/* kswaped页换出守护进程使用的等待队列 */
-
wait_queue_head_t kswapd_wait;
-
wait_queue_head_t pfmemalloc_wait;
-
/* 指针指向kswapd内核线程的进程描述符 */
-
struct task_struct *kswapd; /* Protected by
-
mem_hotplug_begin/end() */
-
/* kswapd将要创建的空闲块大小取对数的值 */
-
int kswapd_max_order;
-
enum zone_type classzone_idx;
-
#ifdef CONFIG_NUMA_BALANCING
-
/* 以下用于NUMA的负载均衡 */
-
/* Lock serializing the migrate rate limiting window */
-
spinlock_t numabalancing_migrate_lock;
-
-
/* Rate limiting time interval */
-
unsigned long numabalancing_migrate_next_window;
-
-
/* Number of pages migrated during the rate limiting time interval */
-
unsigned long numabalancing_migrate_nr_pages;
-
#endif
-
} pg_data_t;
系统中所有的结点描述符都保存在node_data这个数组中。在pg_data_t这个结点描述符中,node_zones数组中保存了这个结点中所有的管理区描述符,虽然系统将物理内存分为三个区,但是在逻辑上,系统分为了四个管理区,多出的一个是ZONE_MOVABLE,这个区是一个虚拟的管理区,它并没有对应于内存的某个区域,它的主要目的就是为了避免内存碎片化,它的内存要么全部来自ZONE_HIGHMEM区,要么全部来自ZONE_NORMAL区。这些我们在后面的初始化函数中将会看到。
每个结点都有一个内核线程kswapd,它的作用就是将进程或内核持有的,但是不常用的页交换到磁盘上,以腾出更多可用内存。
我们再看看管理区描述符:
-
/* 内存管理区描述符 */
-
struct zone {
-
/* Read-mostly fields */
-
-
/* zone watermarks, access with *_wmark_pages(zone) macros */
-
/* 包括pages_min,pages_low,pages_high
-
* pages_min: 管理区中保留页的数目
-
* pages_low: 回收页框使用的下界,同时也被管理区分配器作为阀值使用,一般这个数字是pages_min的5/4
-
* pages_high: 回收页框使用的上界,同时也被管理区分配器作为阀值使用,一般这个数字是pages_min的3/2
-
*/
-
unsigned long watermark[NR_WMARK];
-
-
/* 指明在处理内存不足的临界情况下管理区必须保留的页框数目,同时也用于在中断或临界区发出的原子内存分配请求(就是禁止阻塞的内存分配请求) */
-
long lowmem_reserve[MAX_NR_ZONES];
-
-
#ifdef CONFIG_NUMA
-
int node;
-
#endif
-
-
/*
-
* The target ratio of ACTIVE_ANON to INACTIVE_ANON pages on
-
* this zone's LRU. Maintained by the pageout code.
-
*/
-
unsigned int inactive_ratio;
-
-
/* 指向此管理区属于的结点 */
-
struct pglist_data *zone_pgdat;
-
/* 实现每CPU页框高速缓存,里面包含每个CPU的单页框的链表 */
-
struct per_cpu_pageset __percpu *pageset;
-
-
/*
-
* This is a per-zone reserve of pages that should not be
-
* considered dirtyable memory.
-
*/
-
unsigned long dirty_balance_reserve;
-
-
#ifndef CONFIG_SPARSEMEM
-
/*
-
* Flags for a pageblock_nr_pages block. See pageblock-flags.h.
-
* In SPARSEMEM, this map is stored in struct mem_section
-
*/
-
unsigned long *pageblock_flags;
-
#endif /* CONFIG_SPARSEMEM */
-
-
#ifdef CONFIG_NUMA
-
/*
-
* zone reclaim becomes active if more unmapped pages exist.
-
*/
-
unsigned long min_unmapped_pages;
-
unsigned long min_slab_pages;
-
#endif /* CONFIG_NUMA */
-
-
/* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT */
-
/* 管理区第一个页框下标 */
-
unsigned long zone_start_pfn;
-
-
/* 所有正常情况下可用的页,总页数(不包括洞)减去保留的页数 */
-
unsigned long managed_pages;
-
/* 管理区总大小(页为单位),包括洞 */
-
unsigned long spanned_pages;
-
/* 管理区总大小(页为单位),不包括洞 */
-
unsigned long present_pages;
-
/* 指向管理区的传统名称,"DMA" "NORMAL" "HighMem" */
-
const char *name;
-
-
/* 对应于伙伴系统中MIGRATE_RESEVE链的页块的数量 */
-
int nr_migrate_reserve_block;
-
-
#ifdef CONFIG_MEMORY_ISOLATION
-
/*
-
* Number of isolated pageblock. It is used to solve incorrect
-
* freepage counting problem due to racy retrieving migratetype
-
* of pageblock. Protected by zone->lock.
-
*/
-
/* 在内存隔离中表示隔离的页框块数量 */
-
unsigned long nr_isolate_pageblock;
-
#endif
-
-
#ifdef CONFIG_MEMORY_HOTPLUG
-
/* see spanned/present_pages for more description */
-
seqlock_t span_seqlock;
-
#endif
-
-
/* 进程等待队列的hash表,这些进程在等待管理区中的某页 */
-
wait_queue_head_t *wait_table;
-
/* 等待队列散列表的大小 */
-
unsigned long wait_table_hash_nr_entries;
-
/* 等待队列散列表数组大小 */
-
unsigned long wait_table_bits;
-
-
ZONE_PADDING(_pad1_)
-
-
/* Write-intensive fields used from the page allocator */
-
/* 保护该描述符的自旋锁 */
-
spinlock_t lock;
-
-
/* free areas of different sizes */
-
/* 标识出管理区中的空闲页框块,用于伙伴系统 */
-
/* MAX_ORDER为11,分别代表包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续页框的链表 */
-
struct free_area free_area[MAX_ORDER];
-
-
/* zone flags, see below */
-
/* 管理区标识 */
-
unsigned long flags;
-
-
ZONE_PADDING(_pad2_)
-
-
/* Fields commonly accessed by the page reclaim scanner */
-
/* 活动及非活动链表使用的自旋锁 */
-
spinlock_t lru_lock;
-
struct lruvec lruvec;
-
-
/* Evictions & activations on the inactive file list */
-
atomic_long_t inactive_age;
-
-
/*
-
* When free pages are below this point, additional steps are taken
-
* when reading the number of free pages to avoid per-cpu counter
-
* drift allowing watermarks to be breached
-
*/
-
unsigned long percpu_drift_mark;
-
-
#if defined CONFIG_COMPACTION || defined CONFIG_CMA
-
/* pfn where compaction free scanner should start */
-
unsigned long compact_cached_free_pfn;
-
/* pfn where async and sync compaction migration scanner should start */
-
unsigned long compact_cached_migrate_pfn[2];
-
#endif
-
-
#ifdef CONFIG_COMPACTION
-
/*
-
* On compaction failure, 1<<compact_defer_shift compactions
-
* are skipped before trying again. The number attempted since
-
* last failure is tracked with compact_considered.
-
*/
-
unsigned int compact_considered;
-
unsigned int compact_defer_shift;
-
int compact_order_failed;
-
#endif
-
-
#if defined CONFIG_COMPACTION || defined CONFIG_CMA
-
/* Set to true when the PG_migrate_skip bits should be cleared */
-
bool compact_blockskip_flush;
-
#endif
-
-
ZONE_PADDING(_pad3_)
-
/* 管理区的一些统计数据 */
-
atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS];
-
} ____cacheline_internodealigned_in_smp;
此管理区描述符中的实际把所有属于该管理区的页框保存在两个地方:struct free_area free_area[MAX_ORDER]和struct per_cpu_pageset __percpu * pageset。free_area是这个管理区的伙伴系统,而pageset是这个区的每CPU页框高速缓存。对管理区的理解需要结合伙伴系统和每CPU页框高速缓存
管理区页框分配器(管理所有物理内存页框)
ZONE_NORMAL和ZONE_DMA的地址直接映射到了内核地址空间,但是也不代表内核的代码可以随心所欲的通过线性地址直接访问物理地址。内核通过一个管理区页框分配器管理着物理内存上所有的页框,在管理区分配器里的核心系统就是伙伴系统和每CPU页框高速缓存(不是硬件上的高速缓存,只是名称一样)。在linux系统中,管理区页框分配器管理着所有物理内存,无论你是内核还是进程,需要将一些内存占为己有时,都需要请求管理区页框分配器,这时才会分配给你应该获得的物理内存页框。当你所拥有的页框不再使用时,你必须释放这些页框,让这些页框回到管理区页框分配器当中。特别的,对于高端内存,即使从管理区页框分配器中获得了相应的页框,我们还需要进行映射才能够使用。
有时候目标管理区不一定有足够的页框去满足分配,这时候系统会从另外两个管理区中获取要求的页框,但这是按照一定规则去执行的,如下:
-
如果要求从DMA区中获取,就只能从ZONE_DMA区中获取。
-
如果没有规定从哪个区获取,就按照顺序从 ZONE_NORMAL -> ZONE_DMA 获取。
-
如果规定从HIGHMEM区获取,就按照顺序从 ZONE_HIGHMEM -> ZONE_NORMAL -> ZONE_DMA 获取。
注意系统是不允许在一次分配中从不同的两个管理区获取页框的,并且当请求多个页框时,从伙伴系统中分配给目标的页框是连续的,并且请求的页数必须是2的次方个数。
管理区分配器主要做的事情就是将页框通过伙伴系统或者每CPU页框高速缓存分配出去,这里涉及到三个结构,页描述符,伙伴系统,每CPU高速缓存。
我们先说说页描述符,页描述符实际上并不专属于描述页框,它还用于描述一个SLAB分配器和SLUB分配器,这个之后再说,我们先说关于页的:
在struct page描述一个页框时,我们比较关注的成员变量有unsigned long flags、struct list_head lru和atomic_t _count。
-
flags:包含有很多信息,包括此页框属于的node结点号,此页框属于的zone号和此页框的属性。
-
lru:用于将此页描述符放入相应的链表,比如伙伴系统或者每CPU页框高速缓存。
-
_count:代表页框的引用计数,-1代表此页框空闲,大于0代表此页框分配给了多少个进程使用(共享)。
linux为了防止内存中产生过多的碎片,一般把页的类型分为三种:
-
不可移动页:在内存中有固定位置,不能移动到其他地方。内核中使用的页大部分是属于这种类型。
-
可回收页:不能直接移动,但可以删除,页中的内容可以从某些源中重新生成。例如,页内容是映射到文件数据的页就属于这种类型。对于这种类型,kswapd内核线程会根据可回收页的访问频率,周期性地释放这些页。在内存短缺(分配失败)时,也会发起页面回收,释放这些页。
-
可移动页:可随意移动,用户空间的进程使用的页就属于这种类型,它们是通过进程页表映射的,把这些页复制到新位置时,只要更新进程页表就可以了。一般这些页是从高端内存管理区获取。
伙伴系统
伙伴系统实际上是一个struct free_area的数组,数组长度是MAX_ORDER,也就是11,代表着每个数组元素中链表上保存的连续页框长度是2的order次方。free_area[0]中链表保存的是长度为1的页框,free_area[1]中链表上保存的是物理上连续的两个页框的首页框链表,free_area[2]中链表上保存的是物理上连续4个页框的首页框链表,free_area[10]中链表上保存的是物理上连续1024个页框的首页框链表,所以整个伙伴系统中将管理区中的页框分为连续的1,2,4,8,16,32,64,128,256,512,1024页框放入不同链表中保存起来。而因为伙伴系统中每个链表保存的页框都是连续的,所以只有第一个页框会加入到链表中,因为有order,也可以知道此页框之后的多少个页框是属于这一小块连续页框的。当需要在普通内存区申请4个页框大小的内存时,系统会到普通内存管理区的伙伴系统中的free_area[2]中的第一个链表结点,这个结点的页框及其之后3个页框都是空闲的,然后把首页框返回给申请者。
-
/* 伙伴系统的一个块,描述1,2,4,8,16,32,64,128,256,512或1024个连续页框的块 */
-
struct free_area {
-
/* 指向这个块中所有空闲小块的第一个页描述符,这些小块会按照MIGRATE_TYPES类型存放在不同指针里 */
-
struct list_head free_list[MIGRATE_TYPES];
-
/* 空闲小块的个数 */
-
unsigned long nr_free;
-
};
在伙伴系统中,因为页的分类关系,在每种长度相同的连续页框中又会分出多个不同类型的链表,如下:
-
enum {
-
MIGRATE_UNMOVABLE, /* 不可移动页 */
-
MIGRATE_RECLAIMABLE, /* 可回收页 */
-
MIGRATE_MOVABLE, /* 可移动页 */
-
MIGRATE_PCPTYPES, /* 用来表示每CPU页框高速缓存的数据结构中的链表的可移动类型数目 */
-
MIGRATE_RESERVE = MIGRATE_PCPTYPES,
-
#ifdef CONFIG_CMA
-
MIGRATE_CMA,
-
#endif
-
#ifdef CONFIG_MEMORY_ISOLATION
-
MIGRATE_ISOLATE, /* 不能从这个链表分配页框,因为这个链表专门用于NUMA结点移动物理内存页,将物理内存页移动到使用这个页最频繁的CPU */
-
#endif
-
MIGRATE_TYPES
-
};
保存连续2个页框的free_area[2]的结构如下:
在从伙伴系统中申请页框时,有可能会遇到一种情况,就是当前需求的连续页框链表上没有可用的空闲页框,这时后,伙伴系统会从下一级获取一个连续长度的页框块,将其拆分放入这级列表;当然在拥有者释放连续页框时伙伴系统也会适当地进行连续页框的合并,并放入下一级中。比如:我需要申请4个页框,但是长度为4个连续页框块链表没有空闲的页框块,伙伴系统会从连续8个页框块的链表获取一个,并将其拆分为两个连续4个页框块,放入连续4个页框块的链表中。释放时道理也一样,会检查释放的这几个页框的之前和之后的物理页框是否空闲,并且能否组成下一级长度的块。
每CPU页框高速缓存
每CPU页框高速缓存也是一个分配器,配合着伙伴系统进行使用,这个分配器是专门用于分配单个页框的,它维护一个单页框的双向链表,为什么需要这个分配器,因为每个CPU都有自己的硬件高速缓存,当对一个页进行读取写入时,首先会把这个页装入硬件高速缓存,而如果进程对这个处于硬件高速缓存的页进行操作后立即释放掉,这个页有可能还保存在硬件高速缓存中,这样我另一个进程需要请求一个页并立即写入数据的话,分配器将这个处于硬件高速缓存中的页分配给它,系统效率会大大增加。
在每CPU页框高速缓存中用一个链表来维护一个单页框的双向链表,每个CPU都有自己的链表(因为每个CPU有自己的硬件高速缓存),那些比较可能处于硬件高速缓存中的页被称为“热页”,比较不可能处于硬件高速缓存中的页称为“冷页”。其实系统判断是否为热页还是冷页很简单,越最近释放的页就比较可能是热页,所以在双向链表中,从链表头插入可能是热页的单页框,在链表尾插入可能是冷页的单页框。分配时热页就从链表头获取,冷页就从链表尾获取。
在每CPU页框高速缓存中也可能会遇到没有空闲的页框(被分配完了),这时候每CPU页框高速缓存会从伙伴系统中拿出页框放入每CPU页框高速缓存中,相反,如果每CPU页框高速缓存中页框过多,也会将一些页框放回伙伴系统。
在内核中使用struct per_cpu_pageset结构描述一个每CPU页框高速缓存,其中的struct per_cpu_pages是核心结构体,如下:
-
/* 描述一个CPU页框高速缓存 */
-
struct per_cpu_pageset {
-
/* 高速缓存页框结构 */
-
struct per_cpu_pages pcp;
-
#ifdef CONFIG_NUMA
-
s8 expire;
-
#endif
-
#ifdef CONFIG_SMP
-
s8 stat_threshold;
-
s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];
-
#endif
-
};
-
-
struct per_cpu_pages {
-
/* 当前CPU高速缓存中页框个数 */
-
int count; /* number of pages in the list */
-
/* 上界,当此CPU高速缓存中页框个数大于high,则会将batch个页框放回伙伴系统 */
-
int high; /* high watermark, emptying needed */
-
/* 在高速缓存中将要添加或被删去的页框个数 */
-
int batch; /* chunk size for buddy add/remove */
-
-
/* Lists of pages, one per migrate type stored on the pcp-lists */
-
/* 页框的链表,如果需要冷高速缓存,从链表尾开始获取页框,如果需要热高速缓存,从链表头开始获取页框 */
-
struct list_head lists[MIGRATE_PCPTYPES];
-
};
结尾
下篇再说slab了,内容太多。到这里,记住对于物理内存来说,系统都是以页框作为最小的分配单位,而分配时必定是要通过管理区分配器进行分配的,在管理区分配器中又必定是通过伙伴系统或每CPU页框分配器进行分配的,而我们编程使用到的malloc或者内核中使用的分配小额内存的情况,是使用slab实现的,slab的作用就是将一个页框细分为多个小块内存。
阅读(4329) | 评论(0) | 转发(1) |