存档在 2011年12月

物理内存管理中的基本数据结构

2011年12月29日

Linux内核在管理内存时将物理内存从逻辑上划分为节点(node),内存管理区(zone),页框(frame page)三级结构。物理内存先被划分为内存节点,每个节点关联一个CPU,各个节点又被划分几个内存管理区,在一个内存管理区中则是页框。页框是内存管理的基本单位,它可以存放任何种类的数据。不过,由于实际中计算机硬件的制约,部分页框的使用受到了限制,内核将具有相同性质的页框进行分类组织,即形成内存管理区。为了兼容NUMA架构的计算机,内核又引入了节点这个概念,每个CPU对应一个节点。

1.page结构

内核使用page结构体描述一个物理页框,该结构也称为页描述符,每个物理页框都关联一个这样的结构体。值得注意的是,page结构仅用来描述一个页框的属性,它不包含该页框中的任何数据。此外,还应该区分页框大小和page结构的大小,页框大小通常为4KB,而page结构的大小即为sizeof(struct page)。

内核在定义page结构时使用了许多联合体,这样做的目的是保证page结构尽可能的小。虽然每个page结构体占很少内存,但是由于实际系统中页框总数量巨大,因此所有页框对应的page结构所占用的内存量也很庞大。下面仅对该结构中的部分字段进行介绍。

flags:它是用来描述页框状态的标志位,更重要的是该字段的高位存放着该页框所关联的页框号、节点内管理区号以及节点号。

__count:表示该页的引用计数,如果该页为-1,表示页框空闲;如果该字段的值为N(N>=0),则说明有N+1个进程正在使用该页。
系统中所有的页描述符都放在mem_map数组中,每个页描述符在数组中的下标即为该描述符对应物理页的页框号。

2.zone结构

内核将整个页框按照不同的访问特性划分为几个区,每个区内的页框都是连续的,这样的区称为内存管理区并使用zone结构来描述。内核中使用了一个枚举类型对内存管理区的类型进行定义:

enum zone_type {
#ifdef CONFIG_ZONE_DMA
	ZONE_DMA,
#endif
#ifdef CONFIG_ZONE_DMA32
	ZONE_DMA32,
#endif
	ZONE_NORMAL,
#ifdef CONFIG_HIGHMEM
	ZONE_HIGHMEM,
#endif
	ZONE_MOVABLE,
	__MAX_NR_ZONES
};

内存管理区是一个逻辑上的概念,它的存在是因为计算机中硬件访问物理内存时有一些限制。因此,每个内存管理区的实际分布是与体系结构相关的,具体分布如下:

ZONE_DMA:某些设备通过DMA方式访问内存时,不能访问到所有的物理内存,此时只能为它们单独划分一块内存管理区。ZONE_DMA的范围根据体系结构而改变,比如X86架构下,ISA总线为16位,因此该区的范围为物理内存的前16M。但是,如果某些架构在内存的任何地址上都可以执行DMA,那么该区域就为空,即长度为0。

ZONE_DMA32:该区的作用与ZONE_DMA相同,只不过它代表的是32位可寻址并适合DMA的物理内存区域。32位的系统中该区域的长度为0,这种区域只会出现在64位的系统中。在某些64位的系统中,该区域的大小可达到4GB。

ZONE_NORMAL:这个区域包含的都是能够正常映射的页框。通过源码中的定义可以发现,所有的体系架构都包含这个区域。但是并不是每个架构下该区都能对应到实际的物理内存,根据上面所述,某些架构下ZONE_DMA32会占据整个4G的物理内存,因此该区域为空。在IA32架构下该内存管理区的范围为16MB到896MB。

ZONE_HIGHMEM:这个区域代表超出内核空间大小的物理内存,这部分内存也被成为高端内存(与之对应ZONE_DMA和ZONE_NORMAL成为低端内存)。在32位的x86系统中,高端内存即为大于896MB的物理内存。而在64位的系统中,高端内存总为空。

ZONE_MOVABLE:这个区域是一个伪内存管理区,它只在防止物理内存碎片机制中使用。

__MAX_NR_ZONES:它用来标记内存管理区的数量。

内存管理区描述符中有许多字段,有些字段理解起来并不简单,因此只介绍部分字段。

watermark:即所谓的水印值数组,它为每个内存区设置合适的内存消耗基准,该水印值随着系统中的空闲内存量而变化。该数组包含三个元素:

1).watermark[WMARK_HIGH]:当系统中空闲页框数大于其值时,表示当前内存使用情况理想。

2).watermark[WMARK_LOW]:如果空闲页框小于其值,表示空闲页量较少,应当换出内存中部分页到磁盘上。

3).watermark[WMARK_MIN]:当空闲页框数小于其值时,表示系统急需空闲页框。

free_area:它表示当前内存管理区中空闲页框。该数组中的每个元素都是一条双链表,链表中的每个元素都是固定大小的连续内存块。

lock:保护当前内存管理区的自旋锁。由于在多处理器的系统中,会出现多个CPU同时访问一个内存管理区的情形,因此需要锁来保护避免数据不一致的现象。

3.pg_data_t结构

节点这个概念是由于NUMA(非一致内存访问)模型而诞生的,该模型只存在于多处理器计算机中。NUMA根据CPU数量将整个物理内存分为几个大块,每块内存即为每个CPU的的本地内存。这样的划分使每个CPU都能以较快的速度访问本地内存,当然每个CPU也可以访问其他CPU的内存只不过速度比较慢而已。上述的每块物理内存对应一个pg_data_t数据结构,每块物理内存即为一个节点,所以的结点形成一个双链表。

与NUMA模型对应的是UMA(一致内存访问)模型,这种模型并不需要将物理内存划分为块,因此也就不存在节点这样的概念。但是为了兼容NUMA模式,UMA模型下的物理内存还是对应一个节点,也就是说整个物理内存形成一个节点,因此上述的节点链表中也就只有一个元素。

struct bootmem_data;
typedef struct pglist_data {
        struct zone node_zones[MAX_NR_ZONES];
        struct zonelist node_zonelists[MAX_ZONELISTS];
        int nr_zones;
#ifdef CONFIG_FLAT_NODE_MEM_MAP /* means !SPARSEMEM */
        struct page *node_mem_map;
#ifdef CONFIG_CGROUP_MEM_RES_CTLR
        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
        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;
} pg_data_t;

node_zones:当前节点中内存管理区描述符数组。这个数组的大小使用__MAX_NR_ZONES来定义。

node_zonelists:它是zonelist结构的数组,长度为MAX_ZONELISTS。如果内核未配置NUMA,则长度为1,否则,长度为2。该数组中0号元素指定了备用的内存管理区链表,也就是当前系统中所有的zone。1号元素指定了当前节点中的管理区链表。除非分配内存时指定了GFP_THISNODE标志而采用本地内存节点上的zonelist,一般均采用备用zonelist。

struct zonelist {
        struct zonelist_cache *zlcache_ptr;                  // NULL or &zlcache
        struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
#ifdef CONFIG_NUMA
        struct zonelist_cache zlcache;                       // optional ...
#endif
};

zonelist结构中管理区链表主要由_zonerefs数组来描述。
nr_zones:当前节点中内存管理区的数量。

node_mem_map:页框描述符数组,该数组中的页框即为当前节点中包含的物理页。

node_id:当前节点的索引,系统中节点从0开始编号。

kswapd:指向负责该节点页交换的守护进程的进程描述符。

这里只是简单的介绍了节点,内存管理区,页框所代表的数据结构,这三个结构贯穿整个内存管理系统中,许多字段的含义以及作用随着对内存管理部分的深入学习才能逐渐加深理解。

与虚拟内存区域有关的操作(2)-合并内存区域

2011年12月16日

合并内存区域

Linux的内存管理模块以虚拟内存区域为单位管理进程的虚拟内存,一个进程的所有内存区域分别以链表和树形结构进行组织。当一个新建的区域加入进程时,内核会试图将这个新区域与已存在的区域进行合并。区域合并的首要条件就是检查新区域之前的prve区域终止地址是否与新区域起始地址重合,或新区域的结束地址是否与其之后的next区域起始地址重合;接着再检查将要合并的区域是否有相同的标志。如果合并区域均映射了磁盘文件,则还要检查其映射文件是否相同,以及文件内的偏移量是否连续。

上述提及的一系列条件检查是在vma_merge()中完成的,根据新区域和它前后两个内存区域之间的位置关系,区域合并分为8种情况。由于合并条件的复杂性,该函数包含好几个参数,分别对上述说明的合并条件进行检测。

mm描述要添加新区域进程的内存空间,prev指向当前区域之前的一个内存区域,addr表示新区域的起始地址,end为新区域的结束地址,vm_flags表示该区域的标志。如果该新区域映射了一个磁盘文件,则file结构表示该文件,pgoff表示该文件映射的偏移量。

struct vm_area_struct *vma_merge(struct mm_struct *mm,
                        struct vm_area_struct *prev, unsigned long addr,
                        unsigned long end, unsigned long vm_flags,
                        struct anon_vma *anon_vma, struct file *file,
                        pgoff_t pgoff, struct mempolicy *policy)

合并函数首先通过起始地址和终止地址计算新区域的长度,接下来判断新区域是否设置了VM_SPECIAL,这个标志指定了该区域不能和其他区域合并,因此立即返回NULL。

        pgoff_t pglen = (end - addr) >> PAGE_SHIFT;
        struct vm_area_struct *area, *next;
        int err;

        if (vm_flags & VM_SPECIAL)
                return NULL;

        if (prev)
                next = prev->vm_next;
        else
                next = mm->mmap;
        area = next;
        if (next && next->vm_end == end)                /* cases 6, 7, 8 */
                next = next->vm_next;

接着,通过prev获得下一个内存区域的描述符next,如图1。如果新区域的终止地址与next区域的终止地址重合,则next再向前移动一个区域,如图2。为了便于说明,在图2所示的情况下,next‘表示紧邻prev的那个区域,而next表示紧邻next‘的区域。图中每个不同的内存区域都使用不同的颜色标示。

接下来开始真正的合并工作,合并分为两大类,第一大类为新区域的起始地址和prev区域的终止地址重合,第二种情况为新区域的终止地址和next区域的起始地址重合。

我们首先分析第一种情况,即便addr和prev的终止地址重合还不足以将其合并,还应通过can_vma_merge_after()判断两者的标志和映射文件等是否相同。如果都满足条件,那么合并此时就应该可以开始了。不过合并函数力求每次合并程度达到最大化,它再继续检查end是否恰好与next区域的起始地址重合。

在这样的判断条件下,会出现5种不同的合并情况(分别为case1,6,2,5,7)。每种合并情况最终都会调用vma_adjust(),它通过修改vma结构中的字段对区域进行适当调整,也就是说真正的合并是在这个函数中完成的。可以看出vma_merge()本质上是一个“分流”函数,它将区域合并细化,根据不同的合并情况向vma_adjust()传递不同的参数。

        if (prev && prev->vm_end == addr &&
                        mpol_equal(vma_policy(prev), policy) &&
                        can_vma_merge_after(prev, vm_flags,
                                                anon_vma, file, pgoff)) {
                if (next && end == next->vm_start &&
                                mpol_equal(policy, vma_policy(next)) &&
                                can_vma_merge_before(next, vm_flags,
                                        anon_vma, file, pgoff+pglen) &&
                                is_mergeable_anon_vma(prev->anon_vma,
                                                      next->anon_vma)) {
                                                        /* cases 1, 6 */
                        err = vma_adjust(prev, prev->vm_start,
                                next->vm_end, prev->vm_pgoff, NULL);
                } else                                  /* cases 2, 5, 7 */
                        err = vma_adjust(prev, prev->vm_start,
                                end, prev->vm_pgoff, NULL);
                if (err)
                        return NULL;
                return prev;
        }

从上面的分析以及源码可以看出,case1和case6既满足addr与prev终止地址重合,又满足end与next起始地址重合,但是他们的next(如图1,2)却指向不同的区域。case1可参考下图,它实际上是填充了prev和next之间的“空洞”,也就是说三个区域合为一个区域,vma_adjust()会删除next区域同时扩大prev区域。

case6也可以看作是填充prev和next区域之间的空洞,不过它会将next‘区域进行“覆盖”。通过代码可以发现,next‘和next区域事实上是连续的,不过由于其他原因,比如标志不同,造成它们是两个不同的区域。尽管地址连续,但是组织的时候仍然通过链表链接。这里为了定量的表示区域之间的关系,省去了next‘和next之间的链接箭头。

如果end与next的起始地址不重合,那么会出现case2,case5,case7三种情况。这三种情况的差异会在vma_adjust()中被进一步区分,而在当前函数中,它们被看作是一种情况,即addr与prev终止地址重合而end与next起始地址不重合。

如果end小于next区域的起始地址,则为case2。

 

如果end大于next区域的起始地址,则为case5。在这种情况下,next会被一分为二,一部分加入prev,而另一部分则继续保留在原始区域中。

case7也是一种扩大prev的情况,它会将next‘覆盖,而next则保持不变。

当上述情况都不符合时,进入第二大类合并,即end与next的起始地址重合。在这种情形下涉及三种合并模型,它们的图示分别如下所示。

        if (next && end == next->vm_start &&
                        mpol_equal(policy, vma_policy(next)) &&
                        can_vma_merge_before(next, vm_flags,
                                        anon_vma, file, pgoff+pglen)) {
                if (prev && addr < prev->vm_end)        /* case 4 */
                        err = vma_adjust(prev, prev->vm_start,
                                addr, prev->vm_pgoff, NULL);
                else                                    /* cases 3, 8 */
                        err = vma_adjust(area, addr, next->vm_end,
                                next->vm_pgoff - pglen, NULL);
                if (err)
                        return NULL;
                return area;
        }

        return NULL;

如果addr大于prev的终止地址,则属于case4。这种情况下缩小prev,扩充next。

如果addr小于prev区域的终止地址,则属于case3。这种情况下prev不做改变,扩充next。

case8与case3比较类似,不过它会覆盖已存在的next‘。

从源码的条件判断语句可以看出,上述8种合并情况可以规划为四类,通过向vma_adjust()传递不同的参数可以为每种情况调节内存区域。

与虚拟内存区域有关的操作

2011年12月12日

每个进程都拥有一段连续的虚拟地址空间,内核实际的使用情况并不是以整个地址空间为单位,而是将整个连续的空间划分为若干个内存区域,内核中使用vm_area_struct数据结构来表示,简称vma。当进程需要使用内存时,内核先为该进程分配一个合适大小的虚拟内存区域,此时并不立刻为此内存区域映射物理页框,而是一直延迟到进程不得不访问物理内存为止。

使用虚拟内存区域的另外一个好处便是可以将进程的所有信息按照类型进行区域划分。比如,进程二进制形式的代码对应一个内存区域,这个内存区域被特定的称为text段。进程包含的数据划分的更为细致,全局变量存储在被称为数据段的内存区域中,局部变量存储在栈所对应的内存区域,动态申请的数据存放在堆所对应的内存区域。另外,进程所需的库以及映射到进程地址空间中的文件也都对应着一个内存区域。

可以看出进程对内存区域的操作是十分频繁的,据此内核提供了各种对内存区域操作的函数,比如在一个进程的地址空间中删除一个区域或创建一个区域等。本文将分析几个常见的对虚拟内存区域操作的函数。

1.通过线性地址查找最临近的区域

内核中通常会有这样的操作需求:给定一个虚拟地址,查找该地址最临近的内存区域,find_vma()用来完成这样的操作。通常情况下,我们希望恰好找到该线性地址所属的内存区域。但是这种结果不会每次都发生,该线性地址有可能不属于当前已存在的任何内存区域,此时只需返回第一个终止地址大于该虚拟地址的内存区。如果没有符合上述要求的内存区,则直接返回空。因此,find_vma()找到的区域和线性地址addr的关系如下图:

一个进程的所有内存区域通过两种方式进行组织:双联表和红黑树。双联表易于遍历每个区域,红黑树则易于查找所需区域。find_vma()就是基于红黑树进行查找的,它传入两个参数,mm为进程的内存描述符,addr即为所查找的线性地址。该函数首先检查addr是否就在mmap_cache所指向的那个内存区域中,mmap_cache保存了进程最后一次所使用的虚拟内存区域描述符地址。根据程序的局部性原理,当前所查找的线性地址很可能就在刚刚所使用的那个内存区中,这样做可以避免由于查找而带来的系统开销。

如果addr没有在mmap_cache所指的内存区域中,接下来就开始从红黑树的根节点进行查找。内存区所对应的红黑树是以线性地址为键值的,既一个节点左孩子的线性地址均比该节点的线性地址小,而右节点都比该节点大。整体的查找过程是通过一个循环完成的,rb_node保存了每个内存区在红黑树中对应的节点,而vma_tmp则暂存当前红黑树节点对应的内存区描述符。红黑树的根节点通过内存描述符中rb_root字段获得,在接下来的查找过程中,如何根据红黑树节点得到对应的内存区描述符?这里通过rb_entry()获得。该函数类似list_entry(),既利用vm_area_struct结构中vm_rb字段的指针获取整个结构体的指针。

根据红黑树的特点,如果当前的vma的终止地址大于addr,再进一步检查vma的起始地址是否小于addr。如果起始地址小于addr则说明查找成功,退出循环,否则继续向左查找。如果vma的终止地址小于addr,则向右搜索。最后,将找到的vma再次保存到mmap_cache中。

struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
        struct vm_area_struct *vma = NULL;

        if (mm) {
                vma = mm->mmap_cache;
                if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
                        struct rb_node * rb_node;

                        rb_node = mm->mm_rb.rb_node;
                        vma = NULL;

                        while (rb_node) {
                                struct vm_area_struct * vma_tmp;

                                vma_tmp = rb_entry(rb_node,
                                                struct vm_area_struct, vm_rb);

                                if (vma_tmp->vm_end > addr) {
                                        vma = vma_tmp;
                                        if (vma_tmp->vm_start <= addr)
                                                break;
                                        rb_node = rb_node->rb_left;
                                } else
                                        rb_node = rb_node->rb_right;
                        }
                        if (vma)
                                mm->mmap_cache = vma;
                }
        }
        return vma;
}

2.获取一个空闲的内存区域

每个进程都将已使用的内存区域通过双联表链接在一起,该链表的头指针为mmap。如果进程要申请一个新的内存区域,则必须先查找一个空闲的内存区间,此时就会用到get_unmapped_area()函数。该函数实现的思想很简单,通过遍历内存区域双联表查找一个符合指定大小的空闲区间,如果指定了起始地址,则从该起始地址开始查找。

该函数首先要检查len的合法性,如果它超过了TASK_SIZE的大小,则直接返回内存不足的错误信息。如果flags设置了MAP_FIXED标志,则表示以固定的地址开始创建线性区,因此立即返回该线性地址。

上述两种情况都不满足时,该函数对addr再做进一步判断。它先将addr调整成页大小的倍数,再通过addr查找临近的内存区vma。如果addr是空闲区首地址并且返回给调用函数,那么它首先必须满足addr+len不会超过进程用户空间的上限TASK_SIZE(其值为3GB)。在此条件成立的基础上有两种情况,第一,如果通过addr查找临近的vma为空,则查找成功。也就是说addr之后并不存在任何的内存区域,则addr到addr+len之间的地址空间都是空闲可用的。第二,当addr+len并没有超过vma的起始地址时,也是指定起始地址查找成功的一种情况。这种情况表示所查找到的内存区间位于vma之前的空洞中。

unsigned long
arch_get_unmapped_area(struct file *filp, unsigned long addr,
                unsigned long len, unsigned long pgoff, unsigned long flags)
{
        struct mm_struct *mm = current->mm;
        struct vm_area_struct *vma;
        unsigned long start_addr;

        if (len > TASK_SIZE)
                return -ENOMEM;

        if (flags & MAP_FIXED)
                return addr;

        if (addr) {
                addr = PAGE_ALIGN(addr);
                vma = find_vma(mm, addr);
                if (TASK_SIZE - len >= addr &&
                    (!vma || addr + len <= vm_start))
                        return addr;
        }

上述两种情况的实例图如下:

如果没有指定起始地址,则接下来通过链表查找空闲区间。虽然我们上面说过通过遍历内存区域双联表可以查找一个指定大小的空闲区间,但实际的操作并不是每次都从头遍历到尾,该函数采用缓存机制节约搜索时间。这里首先要介绍一下进程地址空间中的空洞,mmap链表中相邻两个内存区之间的空闲区域就形成一个空洞。free_area_cache和cached_hole_size都是内存描述符中的字段,它们共同描述进程地址空间中的一个空洞,该空洞比较特殊,它位于最近刚分配的内存区之后,以free_area_cache为起始地址,以cached_hole_size为长度。

如果len大于当前空洞大小,也就是说free_area_cache所缓存的空洞太小,那么就从当前这个空洞开始继续查找更大范围的空洞;反之,当len大于当前空洞大小时,并不是立刻就从此空洞中分配所需大小的空闲区,而是从TASK_UNMAPPED_BASE开始重新查找。这种机制是为了防止产生越来越多更小范围的空洞,这种小空洞很难被再次利用。

        if (len > mm->cached_hole_size) {
                start_addr = addr = mm->free_area_cache;
        } else {
                start_addr = addr = TASK_UNMAPPED_BASE;
                mm->cached_hole_size = 0;
        }

下面开始进行完全搜索,如果addr+len已经超出进程用户空间的上限并且此次搜索并不是从TASK_UNMAPPED_BASE开始的,那么从TASK_UNMAPPED_BASE处重新进行新一轮的搜索,并且相应的更新start_addr和cached_hole_size的值。如果此次搜索的确是从TASK_UNMAPPED_BASE开始的,那么说明搜索失败,没有指定大小的空闲区间。

full_search:
        for (vma = find_vma(mm, addr); ; vma = vma->vm_next) {
                if (TASK_SIZE - len < addr) {
                        if (start_addr != TASK_UNMAPPED_BASE) {
                                addr = TASK_UNMAPPED_BASE;
                                start_addr = addr;
                                mm->cached_hole_size = 0;
                                goto full_search;
                        }
                        return -ENOMEM;
                }

如果addr+len在进程的用户空间范围内,那么有两种情况是可以成功搜索到空闲区间的。第一,当vma为空时,则搜索成功;第二,vma之前的空洞可以满足len大小,则搜索成功。不管那种情况,此时都要更新free_area_cache以便后续查找操作的使用,即下一次的查找就是从addr+len之后的空洞开始。最后返回空闲区的起始地址addr。

                if (!vma || addr + len vm_start) {
                        mm->free_area_cache = addr + len;
                        return addr;
                }

上述情况不满足时,也就是当前vma前的空洞太小时,就从当前vma的终止地址开始继续查找。不错在这之前,还要更新cached_hole_size。

                if (addr + mm->cached_hole_size < vma->vm_start)
                        mm->cached_hole_size = vma->vm_start - addr;
                addr = vma->vm_end;
        }
}

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