伙伴系统

2015-7-30 chenhui 内存管理

页框是最基本的内存管理单位,每次分配内存时最少需要分配一个页框。页框当然不能随便分配,我们需要有一种分配策略来进行分配页框,这就是本文要讲的伙伴系统。

 

伙伴系统是一种页框分配策略。网络上详细描述其基本原理的文章有很多,所以本文就不再累述其基本原理了,这里只讲解内核中的伙伴系统是如何实现分配和释放的。

 

我们可以调用 alloc_page() 来从分配一个页框。




alloc_page() 实际上调用了 alloc_pages() 来执行真正的操作。alloc_pages() 因 NUMA UMA 的区别有两个版本,这两个版本的 alloc_pages 最后实际上都调用 __alloc_pages() 来执行真正的操作。ARM 一般都是 UMA 的架构,所以下面讲解 UMA 版本的。




alloc_pages() 又转到 alloc_pages_node() 来执行真正的操作。





alloc_pages_node() 接收一个内存节点的节点号,并从那个节点号对应的内存节点中分配页框。

nid :目标内存节点。

dfp_mask :分配选项。

order :欲分配页框数的对数。对于 alloc_page() 来说,他是 0,即分配一个页框(1<<0=1)。


132~133 行,分配页框数不能超过最大数。


135~136 行,如果 nid 小于 0,就说明调用者需要内核来为我们选择一个内存节点,那么这里会调用 numa_node_id() 来得到当前 CPU 使用的节点。对于 UMA 来说,节点只有 个,一般来说节点号也就是 


138~139 行,根据 gfp_mask 来选择一个内存管理区并调用 __alloc_pages() 来从内存管理区中分配页框。这里要注意,并非只能在这个内存管理区中分配,而是先从这个管理区分配,如果没有再从其他管理区找。




228~229 行,参数检查。

232 行,取出目标内存管理区。

239~242 行,从目标内存管理区中分配一个页框。

 

get_page_from_freelist() 是分配页框的核心函数,下面我们来看看他是如何分配的。



147 行,节点描述符有个 node_zones[] 字段,他保存了节点下所有内存管理区的描述符。这里就是算出目标内存管理区在其所属节点的 node_zones[] 字段的下标。



162 行,取出当前循环到的内存管理区描述符。


166~168 行,如果分配标志里规定了不允许在当前内存管理区里分配页框,那么跳过本次循环。


170 行,如果分配时需要检查页框分配后是否达到某个阀值,那么就在 172~177 行从分配标志中取出需要检查的阀值并在 178 行检查确认,如果会,那么跳过本次循环(对于 UMA 而言,zone_reclaim_mode 为 0)。


186~188 行,开始从内存管理区分配页框。


199 行,到了这里,就说明分配页框失败或者不允许在这个内存管理区分配页框,那么指向下一个内存管理区,然后回到循环开头从这个内存管理区取页框。

 

get_page_from_freelist() 这个函数看起来很复杂,但实际上他的逻辑非常简单:给我一个 zonelist,我从第一个内存管理区开始尝试分配页框,如果分配成功则退出,分配失败则尝试分配下一个。


下面我们再来看一下 buffered_rmqueue() 是怎么从内存管理区中分配页框的。





zonelist :内存管理区所属的 zonelist

zone :目标内存管理区。

order :欲分配页框数的对数。

gfp_flags :分配标志。

 

852 行,取出当前 CPU 号。


853 行,如果我们只需要分配一个页框,那么内核会使用每 CPU 页框高速缓存来分配页框。所谓的每 CPU 页框高速缓存,其实就是一种页框缓存机制,用于快速分配页框。


856 行,取出当前 CPU 的页框高速缓存描述符。


858~863 行,如果每 CPU 页框高速缓存上已经没有页框了(count字段为0),那么就调用 rmqueue_bulk() 来为每 CPU 页框高速缓存补充页框,如果分配失败,则退出。


864~866 行,到了这里就说明每 CPU 页框高速缓存上有页框存在,那么把页框取出并递减页框数。


867~873 行,如果我们我们不止分配一个页框,那么直接调用 __rmqueue() 来从伙伴系统分配页框。


883 行,返回分配出来的页框。

 

下面我们再来看看 __rmqueue() 是如何从伙伴系统获取页框的。




zone :目标内存管理区。

order :分配页框数的对数。

 

642 行,从分配页框数的对数开始一直循环到最大对数(一般是11)。为什么要这样?伙伴系统有一个特点:当有两个相邻且相同大小的内存块空闲时(这里的内存块是指一个或多个页框组成的内存块,内存块中的第一个页框代表整个内存块),他们会被合并为一个内存块,然后他们的大小就倍增了,也就是说他们的对数递增了1(比如说两个页框的对数都是0,然后他们合并后对数就成了1)。由于这个特性的存在,我们不可能总是找到我们需要的那个大小的内存块(比如说我们需要1个页框,但是单独页框都已经相互合并了,所以找不到),当没找到时,我们就需要找比他更大的内存块,而伙伴系统的特性就是块大小是倍增的,所以比他更大的内存块就是对数比他大1的内存块。就是因为这样,我们才要从需要分配的页框数对数一直循环到最大对数。


643 行,在讲这句代码前,我们先来看一下 struct free_area 结构的定义。





在内核中,每一个内存管理区都单独使用一个伙伴系统。我们知道,伙伴系统根据内存块大小的对数把内存块分成多个级别,那么这些内存块就必然要被分类存放在某些队列里,这些队列就是内存管理区描述符的 free_area[] 字段。





看到这个 MAX_ORDER 是不是很熟悉?没错,内存块就被分类存放在这个数组里。比如说对数为 的内存块(一个页框),那么那些内存块就全部存放在 free_area[0] 这个对象里,而对数为 的内存块则存放在 free_area[5] 里。

内存块当然不可能只有一个,所以 struct free_area 结构里有一个链表,他把相同大小但不相邻的内存块连成一个链表来进行管理(若相同大小还相邻,那就直接合并了),而 nr_free 字段则记录了链表上的内存块个数。

 

然后我们再来看 643 行,他就是取出当前对数的内存块队列(这个当前对数,有可能就是我们需要的那个页框数的对数,也有可能是因为其对应的内存块不足而递增后的对数)。那么把这个队列取出来干嘛呢?这不是废话吗?当然是要从队列中拿内存块了(别忘了,内存块由一个或多个页框组成)!

 

644~645 行,如果当前对数对应的内存块队列没有内存块了,那么就跳过当前对数。


646 行,到了这里就说明,当前对数对应的内存块是足够分配的(为什么足够分配?别忘了,他是从需要分配的页框数开始循环的,所以只要有内存块存在,就必然满足需求)!


647~651 行,取出内存块并取消相关标志表示他已经不再被伙伴系统管理,当然最后还要更新相关计数。


652 行,到了这里肯定就是分配成功了,但分配成功还没结束。假设我们只需要一个页框(即对数为0),但这里为我们分配的内存块是两个页框组成的(对数为1),那么这个时候我们需要把另外一个页框放到对数0的那个队列里,即把合并起来的内存块重新分散,这样才能高效地利用页框。

 

下面我们来看一下 expand() 是如何拆分内存块的。





zone :页框所属的内存管理区。

page :内存块的第一个页框。

low :需要的页框数的对数(比如说我们要分配一个页,那么他就是0)。

high :内存块大小的对数(我们要分配一个页,但最后得到的内存块是两个页框组成的,那么他就是两个页框的对数,即1)。

area :内存块所属的队列。

 

572 行,算出内存块大小(单位为页框,一般是4K


574~574 行,遍历伙伴系统,因为我们取了一个内存块,需要把其他用不到的内存分配到比他小的几个队列里。


575 行,area 是内存块所属的队列,但别忘了这个队列是存放在数组里的。所以这里递减 area 实际上是让 area 指向当前对数减一的那个内存块队列,这样下面才能把内存块释放到他里面。


576 行,当前对数递减。


577 行,跟随当前对数,内存块大小也是减半。这个内存块大小减半后,实际上他就成了需要被回收到下一级队列的那部分内存块的第一个页框的编号(内存块内的编号)。


579~581 行,把那部分内存块放到下一级队列里(看清楚了 page[size]),就这么完了。

 

如果读者理解不了 expand() 这个函数,那我也没办法,自己多画下图就能理解了。

 

另外我忽然发现,__alloc_pages() 这个函数还有很大一部分没有讲,但实际上如果我们在 239 行分配页框成功,那么这个函数就这么结束了。当然如果失败了还会有一大堆代码等着你,但不是很难,而且伙伴系统的分配我也讲完了,__alloc_pages() 余下的函数我也懒得讲了,愿意的就自己去看吧。

 

和 alloc_page() 对应的是 free_page()free_page() 接收一个页框的虚拟地址来释放页框。






free_pages() 释放一组连续的页框。

addr :第一个页框的虚拟地址。

order :页框数的对数。

 

free_pages() 非常简单,他根据第一个页框的虚拟地址得到第一个页框的页框描述符,然后把他和 order 传递给 __free_pages() 来执行真正的操作。





404 行,递减页框的引用计数。如果递减后页框的引用计数为 了,那么这个页框就可以被回收。

405~409行,如果我们只需要释放一个页框,那么使用 free_hot_page() 来释放,否则使用 __free_pages_ok() 来释放。

 

我们下面来看free_hot_page() 是如何释放一个页框的。






792 行,取出页框所属的内存管理区。

796 行,如果这是一个匿名页,那么就把 mapping 置空(请看 进程地址空间 那一章)。

798 行,页框检查。

806 行,取出当前 CPU 的页框高速缓存。

809~810 行,把页框插入当前 CPU 的页框高速缓存并递增缓存内的页框数。

811~814 行,如果当前 CPU 页框高速缓存内的页框数达到了最高阀值,那么我们就需要调用 free_pages_bulk() 把缓存内的页框回收到伙伴系统内(patch 字段是回收页框数)。





481 行,内存管理区的all_unreclaimable 字段为 时,说明内存管理区内没有空闲页框,而现在我们把页框回收到内存管理区了(准确地说,是内存管理区的伙伴系统),他肯定为 0,,因为肯定有页框可以回收。


483行,循环所有页框。


487~488 行,取出当前页框。我们一定要弄清楚,这个页框并不一定是一个单独页框,他也有可能是一个内存块里的第一个页框。


489 行,把当前页框(页框所属的内存块)回收到伙伴系统。





398 行,在讲这段代码之前,一定要弄清楚一个地方,那就是:参数里的 page 是一个页框,更准确的说是一个内存块的第一个页框;而参数里的 order 则是这个内存块大小的对数。


403 行,得到页框的页号。其实就是他在 mem_map[] 数组内的下标。


405 行,如果页框不是内存块的第一个页框,那报错。


406 行,如果页框不属于 zone 这个内存管理区,那报错。


409 行,我们之前讲解分配页框时说过:一个内存块被拆分后,剩下的部分要降级存放。在这里则是要释放页框到伙伴系统,而页框释放到伙伴系统后,可能存在和他相邻且相同大小的内存块,这个时候我们要把这两个内存块合并再让他升级;当然他升级后可能又有一个和他相邻且相同大小的内存块(下面称他为「伙伴」),这个时候他又要合并升级,直到最高级别。这里的循环,就是干这个事情的。


414~416 行,调用 __page_find_buddy() 尝试找到当前内存块的伙伴,并调用 page_is_buddy() 进行确认。如果查找失败,那就说明不需要再合并了,自然也不需要再升级,所以退出循环。


417 行,到了这里就说明找到伙伴,可以进行合并。


418 行,伙伴已经在伙伴系统相应的队列里了(zone->free_area [order].free_list 这个队列),这里要把他从这个队列摘出来。


419~420 行,取出伙伴所属的那个队列对象,并递减队列上的内存块数。


421 行,清除伙伴标志,因为他要被合并了。


422 行,取出合并后,伙伴所在的索引(mem_map[] 的索引)。


423~行,指向合并后的内存块的第一个页框。


424~425 行,下次循环用。


我们可以发现的是,在循环中并没有真正地合并,这是因为下次循环可能还能继续合并,所以合并操作实际上是在循环过后才开始的。

 

427 行,设置伙伴标记。


428 行,把内存块插入队列。


429 行,递增队列中的内存块数。





发表评论:

Copyright ©2015-2016 freehui All rights reserved