日志标签 ‘物理内存’

Linux物理内存管理概述

2012年4月10日

在内核态申请内存比在用户态申请内存要更为直接,它没有采用用户态那种延迟分配内存技术。内核认为一旦有内核函数申请内存,那么就必须立刻满足该申请内存的请求,并且这个请求一定是正确合理的。相反,对于用户态申请内存的请求,内核总是尽量延后分配物理内存,用户进程总是先获得一个虚拟内存区的使用权,最终通过缺页异常获得一块真正的物理内存。

1.物理内存的内核映射

IA32架构中内核虚拟地址空间只有1GB大小(从3GB到4GB),因此可以直接将1GB大小的物理内存(即常规内存)映射到内核地址空间,但超出1GB大小的物理内存(即高端内存)就不能映射到内核空间。为此,内核采取了下面的方法使得内核可以使用所有的物理内存。

1.高端内存不能全部映射到内核空间,也就是说这些物理内存没有对应的线性地址。不过,内核为每个物理页框都分配了对应的页框描述符,所有的页框描述符都保存在mem_map数组中,因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用alloc_pages()和alloc_page()来分配高端内存,因为这些函数返回页框描述符的线性地址。

2.内核地址空间的后128MB专门用于映射高端内存,否则,没有线性地址的高端内存不能被内核所访问。这些高端内存的内核映射显然是暂时映射的,否则也只能映射128MB的高端内存。当内核需要访问高端内存时就临时在这个区域进行地址映射,使用完毕之后再用来进行其他高端内存的映射。

由于要进行高端内存的内核映射,因此直接能够映射的物理内存大小只有896MB,该值保存在high_memory中。内核地址空间的线性地址区间如下图所示:

从图中可以看出,内核采用了三种机制将高端内存映射到内核空间:永久内核映射,固定映射和vmalloc机制。

2.物理内存管理机制

基于物理内存在内核空间中的映射原理,物理内存的管理方式也有所不同。内核中物理内存的管理机制主要有伙伴算法,slab高速缓存和vmalloc机制。其中伙伴算法和slab高速缓存都在物理内存映射区分配物理内存,而vmalloc机制则在高端内存映射区分配物理内存。

伙伴算法

伙伴算法负责大块连续物理内存的分配和释放,以页框为基本单位。该机制可以避免外部碎片。

per-CPU页框高速缓存

内核经常请求和释放单个页框,该缓存包含预先分配的页框,用于满足本地CPU发出的单一页框请求。

slab缓存

slab缓存负责小块物理内存的分配,并且它也作为高速缓存,主要针对内核中经常分配并释放的对象。

vmalloc机制

vmalloc机制使得内核通过连续的线性地址来访问非连续的物理页框,这样可以最大限度的使用高端物理内存。

3.物理内存的分配

内核发出内存申请的请求时,根据内核函数调用接口将启用不同的内存分配器。

3.1 分区页框分配器

分区页框分配器 (zoned page frame allocator) ,处理对连续页框的内存分配请求。分区页框管理器分为两大部分:前端的管理区分配器和伙伴系统,如下图:

管理区分配器负责搜索一个能满足请求页框块大小的管理区。在每个管理区中,具体的页框分配工作由伙伴系统负责。为了达到更好的系统性能,单个页框的申请工作直接通过per-CPU页框高速缓存完成。

该分配器通过几个函数和宏来请求页框,它们之间的封装关系如下图所示。

这些函数和宏将核心的分配函数__alloc_pages_nodemask()封装,形成满足不同分配需求的分配函数。其中,alloc_pages()系列函数返回物理内存首页框描述符,__get_free_pages()系列函数返回内存的线性地址。

3.2 slab分配器

slab 分配器最初是为了解决物理内存的内部碎片而提出的,它将内核中常用的数据结构看做对象。slab分配器为每一种对象建立高速缓存。内核对该对象的分配和释放均是在这块高速缓存中操作。一种对象的slab分配器结构图如下:

可以看到每种对象的高速缓存是由若干个slab组成,每个slab是由若干个页框组成的。虽然slab分配器可以分配比单个页框更小的内存块,但它所需的所有内存都是通过伙伴算法分配的。

slab高速缓存分专用缓存和通用缓存。专用缓存是对特定的对象,比如为内存描述符创建高速缓存。通用缓存则是针对一般情况,适合分配任意大小的物理内存,其接口即为kmalloc()。

3.3 非连续内存区内存的分配

内核通过vmalloc()来申请非连续的物理内存,若申请成功,该函数返回连续内存区的起始地址,否则,返回NULL。vmalloc()和kmalloc()申请的内存有所不同,kmalloc()所申请内存的线性地址与物理地址都是连续的,而vmalloc()所申请的内存线性地址连续而物理地址则是离散的,两个地址之间通过内核页表进行映射。

vmalloc()的工作方式理解起来很简单:

1.寻找一个新的连续线性地址空间;

2.依次分配一组非连续的页框;

3.为线性地址空间和非连续页框建立映射关系,即修改内核页表;

vmalloc()的内存分配原理与用户态的内存分配相似,都是通过连续的虚拟内存来访问离散的物理内存,并且虚拟地址和物理地址之间是通过页表进行连接的,通过这种方式可以有效的使用物理内存。但是应该注意的是,vmalloc()申请物理内存时是立即分配的,因为内核认为这种内存分配请求是正当而且紧急的;相反,用户态有内存请求时,内核总是尽可能的延后,毕竟用户态跟内核态不在一个特权级。

后记:本文将Linux内核中物理内存管理这部分内容进行框架性总结,对内存管理感兴趣的同学可以从伙伴算法,slab和vmalloc()三个角度去了解和学习物理内存管理。

伙伴算法的数据结构

2012年3月6日

伙伴算法(buddy system)在物理内存管理中占据十分重要的位置,这种算法可以有效的避免内存中的外部碎片。所谓外部碎片(external fragmentation),就是指内存频繁请求和释放大小不同的连续页框后,导致在已分配页框块周围分散了许多小块空闲的页框,尽管这些空闲页框的总数可以满足接下来的请求,但却无法满足一个大块的连续页框。本文接下来详细说明伙伴算法在内核中的结构描述,其基本原理本文不再赘述。

在每个内存管理区中都有一个free_area数组,该数组的长度为MAX_ORDER,默认值为11。free_area数组描述的就是伙伴算法中每个分配阶(从0到11)所对应的页框块链表。比如free_area[2]所对应的页框块链表中,每个节点对应4个连续的页框(2的2次方)。

struct zone {
……
struct free_area        free_area[MAX_ORDER];
……
}

#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif

可以看到,free_area数组的元素类型是struct free_area,该结构的描述如下:

struct free_area {
        struct list_head        free_list[MIGRATE_TYPES];
        unsigned long           nr_free;
};

在这个结构中的确有一个表示当前分配阶所对应的页框块链表free_list,不过这里稍显复杂一下,因free_list是一个链表数组,这个数组也称为迁移数组。我们可以将这个数组看作是对页框块链表的进一步细分,每个数组元素对应一种迁移类型的页框块链表。迁移列表是在内核2.6.24中引入的,它更加的避免了由于系统长期运行而产生的外部碎片。除了链表结构以外,该结构使用nr_free表示当前链表中空闲页框块的数目,比如free_area[2]中nr_free的值为5,表示有5个大小为4的页框块,那么总的页框数目为20。

根据上面对伙伴算法数据结构的描述,可以得到下面的关系图:

上图表示的是某个内存节点中的某个内存管理区中的伙伴算法示意图。需要注意的是,页框描述符page中有一个lru字段,该字段即为链接每个页框块的链表节点。

struct page {
……
        struct list_head lru;
……
};

从图中也可以看出,链表中负责连接前后页框块的是该页框块首页框中的链表节点。

Linux页框分配函数的实现(2)-慢速内存分配

2012年2月28日

2. 慢速分配函数

进入慢速分配函数后,先检查所请求的分配阶是否超过了MAX_ORDER。如果指定了GFP_THISNODE标志后,则不能继续进行慢速内存分配,因为该标志指明了内存不能进行回收,因此直接跳到nopage处的代码。

在经历一系列的参数检查之后,该函数通过调用wake_all_kswapd()唤醒每个zone所属node中的kswapd守护进程。这个守护进程负责换出很少使用的页,以提高目前系统可以用的空闲页框。

在kswapd交换进程被唤醒之后,该函数开始尝试新一轮的分配。它首先通过gfp_to_alloc_flags()对分配标志进行调整,稍微降低分配标准以便这次调用get_page_from_freelist()有可能分配到内存。

static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
        struct zonelist *zonelist, enum zone_type high_zoneidx,
        nodemask_t *nodemask, struct zone *preferred_zone,
        int migratetype)
{
        const gfp_t wait = gfp_mask & __GFP_WAIT;
        struct page *page = NULL;
        int alloc_flags;
        unsigned long pages_reclaimed = 0;
        unsigned long did_some_progress;
        struct task_struct *p = current;

        if (order >= MAX_ORDER) {
                WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
                return NULL;
        }

        if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
                goto nopage;

restart:
        wake_all_kswapd(order, zonelist, high_zoneidx);
        alloc_flags = gfp_to_alloc_flags(gfp_mask);
        page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
                        high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
                        preferred_zone, migratetype);
        if (page)
                goto got_pg;

如果page不为空,则说明内存申请成功,否则继续进行慢速内存分配。如果设置了ALLOC_NO_WATERMARKS标志,那么此时会忽略水印,并此时进入__alloc_pages_high_priority()。该函数内部会至少会再调用一次get_page_from_freelist(),如果设置了__GFP_NOFAIL标志,则不断的循环等待并尝试进行内存分配。

rebalance:
        if (alloc_flags & ALLOC_NO_WATERMARKS) {
                page = __alloc_pages_high_priority(gfp_mask, order,
                                zonelist, high_zoneidx, nodemask,
                                preferred_zone, migratetype);
                if (page)
                        goto got_pg;
        }

如果没有设置__GFP_WAIT,即wait为0,则不继续进行内存分配,直接跳到nopage处。如果PF_MEMALLOC被设置,也就是说调用内存分配函数着本身就是内存回收进程,则直接跳到nopage处。

        if (!wait)
                goto nopage;

        if (p->flags & PF_MEMALLOC)
                goto nopage;

        if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
                goto nopage;

到目前为止,分配函数已经尝试好几次页框分配。如果现在仍未分配到请求的内存,那么接下来将进入一个比较耗时的阶段。内核通过将很少使用的页换出到磁盘上,以便在物理内存中有更多的空闲页框。这个过程可能会产生阻塞,也就是说会产生睡眠,因此它比较耗时。

__alloc_pages_direct_reclaim()的作用就是先通过try_to_free_pages()回收一些最近很少用的页,将其写回磁盘上的交换区,以便在物理内存中腾出更多的空间。接着,内核会再次调用get_page_from_freelist()尝试分配内存。

        page = __alloc_pages_direct_reclaim(gfp_mask, order,
                                        zonelist, high_zoneidx,
                                        nodemask,
                                        alloc_flags, preferred_zone,
                                        migratetype, &did_some_progress);
        if (page)
                goto got_pg;

如果内核进行了上述的回收和重新分配的过程后,仍未分配成功,既did_some_progress为0,那么此时内核不的不考虑是否发生了OOM(out of memory)。如果当前请求内存的进程发生了OOM,也就是说该进程试图拥有过多的内存,那么此时内核会调用OOM killer杀死它。并且跳转到restart处,重新进行内存分配。

        if (!did_some_progress) {
                if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
                        if (oom_killer_disabled)
                                goto nopage;
                        page = __alloc_pages_may_oom(gfp_mask, order,
                                        zonelist, high_zoneidx,
                                        nodemask, preferred_zone,
                                        migratetype);
                        if (page)
                                goto got_pg;

                        if (order > PAGE_ALLOC_COSTLY_ORDER &&
                                                !(gfp_mask & __GFP_NOFAIL))
                                goto nopage;

                        goto restart;
                }
        }

此时再次判断是否要重新进行一次内存申请。如果有这个必要,那么等待写操作完成后再次跳到rebalance处重试。

        pages_reclaimed += did_some_progress;
        if (should_alloc_retry(gfp_mask, order, pages_reclaimed)) {
                congestion_wait(BLK_RW_ASYNC, HZ/50);
                goto rebalance;
        }

页框分配函数结束时候一般有两种情况,其中之一即为分配失败,并没有得到所需页框,因此打印一些内存分配失败的信息。

nopage:
        if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
                printk(KERN_WARNING "%s: page allocation failure."
                        " order:%d, mode:0x%x\n",
                        p->comm, order, gfp_mask);
                dump_stack();
                show_mem();
        }
        return page;

另一种情况,也就是得到了所需页框,那么直接返回这组页框的首页框描述符。

got_pg:
        if (kmemcheck_enabled)
                kmemcheck_pagealloc_alloc(page, order, gfp_mask);
        return page;

}

通过上述的过程可以看到,页框分配函数__alloc_pages()会多次尝试进行分配内存。而具体的页框分配操作是在get_page_from_freelist()中完成的,它根据伙伴算法分配所需大小的页框。

Linux页框分配函数的实现(1)-主体分配函数

2012年1月11日

内核中有六个基本的页框分配函数,它们内部经过封装,最终都会调用alloc_pages_node()。这个函数的参数比alloc_pages()多了一个nid,它用来指定节点id,如果nid小于0,则说明在当前节点上分配页框。正确获取到节点id后,接下来调用__alloc_pages()。

static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask, unsigned int order)
{
        if (nid < 0)
                nid = numa_node_id();

        return __alloc_pages(gfp_mask, order, node_zonelist(nid, gfp_mask));
}

__alloc_pages()第三个参数根据nid和gfp_mask得到适当的zonelist链表,该过程通过node_zonelist()完成。该函数的实现比较简单,其中NODE_DATA()根据nid返回对应的内存节点描述符,而gfp_zonelist()根据flags标志选取对应的内存管理区链表。其实node_zonelist()就是根据flags在相应内存节点的node_zonelists数组中选择一个何时的内存管理区链表zonelist。

static inline int gfp_zonelist(gfp_t flags)
{
        if (NUMA_BUILD && unlikely(flags & __GFP_THISNODE))
                return 1;

        return 0;
}

由于node_zonelists数组的元素个数最大为2,因此gfp_zonelist()返回0或者1。如果flags中设置了__GFP_THISNODE并且NUMA被设置,则表明使用当前节点对应的zonelist,返回1。否则使用备用zonelist,也就是说当本地节点中zone不足时,在其他节点中申请页框。

static inline int gfp_zonelist(gfp_t flags)
{
        if (NUMA_BUILD && unlikely(flags & __GFP_THISNODE))
                return 1;

        return 0;
}

__alloc_pages()内部再次封装__alloc_pages_nodemask()。

static inline struct page *
__alloc_pages(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist)
{
        return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);
}

1. 主体分配函数

现在进入__alloc_pages_nodemask(),它作为页框分配函数的核心部分。该函数可以通过get_page_from_freelist()快速分配所请求的内存,但是大多数情况下调用该函数都会失败,因为通常物理内存的使用情况都比较紧张,这一点从其后if语句中的unlikely就可以看出。

struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,struct zonelist *zonelist, nodemask_t *nodemask)
{
        enum zone_type high_zoneidx = gfp_zone(gfp_mask);
        struct zone *preferred_zone;
        struct page *page;
        int migratetype = allocflags_to_migratetype(gfp_mask);

        gfp_mask &= gfp_allowed_mask;

        lockdep_trace_alloc(gfp_mask);

        might_sleep_if(gfp_mask & __GFP_WAIT);

        if (should_fail_alloc_page(gfp_mask, order))
                return NULL; 

        if (unlikely(!zonelist->_zonerefs->zone))
                return NULL;            

        first_zones_zonelist(zonelist, high_zoneidx, nodemask, &preferred_zone);
        if (!preferred_zone)
                return NULL;

        page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
                        zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,
                        preferred_zone, migratetype);
        if (unlikely(!page))
                page = __alloc_pages_slowpath(gfp_mask, order,
                                zonelist, high_zoneidx, nodemask,
                                preferred_zone, migratetype);

        trace_mm_page_alloc(page, order, gfp_mask, migratetype);
        return page;
}

首先,gfp_zone()根据gfp_mask选取适当类型的zone。在经过几项参数检查后,该函数通过zonelist->_zonerefs->zone判断zonelist是否为空,既至少需要一个zone可用。接着根据一开始选取的zone类型high_zoneidx,通过first_zones_zonelist()确定优先分配内存的内存管理区。

如果一切顺利,将会进入get_page_from_freelist(),这个函数可以看作是伙伴算法的前置函数,它通过分配标志和分配阶判断是否能进行此次内存分配。如果可以分配,则它进行实际的内存分配工作,既利用伙伴算法进行分配内存。否则,进入__alloc_pages_slowpath(),此时内核需要放宽一些分配条件,或回收一些系统的内存,然后再调用几次get_page_from_freelist()以申请所需内存。

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key