加入星计划,您可以享受以下权益:

  • 创作内容快速变现
  • 行业影响力扩散
  • 作品版权保护
  • 300W+ 专业用户
  • 1.5W+ 优质创作者
  • 5000+ 长期合作伙伴
立即加入
  • 正文
    • 伙伴算法
    • 伙伴系统在内核中的实现
    • 迁移类型
    • 内存碎片化的产生
    • 页面分配和释放常用的函数
    • per-cpu页面分配
  • 推荐器件
  • 相关推荐
  • 电子产业图谱
申请入驻 产业图谱

【内存管理】页面分配机制

07/22 18:00
1263
阅读需 22 分钟
加入交流群
扫码加入
获取工程师必备礼包
参与热点资讯讨论

Linux内核中是如何分配出页面的,如果我们站在CPU的角度去看这个问题,CPU能分配出来的页面是以物理页面为单位的。也就是我们计算机中常讲的分页机制。本文就看下Linux内核是如何管理,释放和分配这些物理页面的。

伙伴算法

伙伴系统的定义

大家都知道,Linux内核的页面分配器的基本算法是基于伙伴系统的,伙伴系统通俗的讲就是以2^order 分配内存的。这些内存块我们就称为伙伴。

何为伙伴

两个块大小相同

两个块地址连续

两个块必须是同一个大块分离出来的

下面我们举个例子理解伙伴分配算法。假设我们要管理一大块连续的内存,有64个页面,假设现在来了一个请求,要分配8个页面。总不能把64个页面全部给他使用吧。

首先把64个页面一切为二,每部分32个页面。

把32个页面给请求者还是很大,这个时候会继续拆分为16个。

最后会将16个页面继续拆分为8个,将其返回给请求者,这就完成了第一个请求。

这个时候,第二个请求者也来了,同样的请求8个页面,这个时候系统就会把另外8个页面返回给请求者。

假设现在有第三个请求者过来了,它请求4个页面。这个时候之前的8个页面都被分配走了,这个时候就要从16个页面的内存块切割了,切割后变为每份8个页面。最后将8个页面的内存块一分为二后返回给调用者。

假设前面分配的8个页面都已经用完了,这个时候可以把两个8个页面合并为16个页面。

以上例子就是伙伴系统的简单的例子,大家可以通过这个例子通俗易懂的理解伙伴系统。

另外一个例子将要去说明三个条件中的第三个条件:两个块必须要是从同一个大块中分离出来的,这两个块才能称之为伙伴,才能去合并为一个大块。

我们以8个页面的一个大块为例子来说明,如图A0所示。将A0一分为二分,分别为 B0,B1。

B0:4页

B1:4页

再将B0,B1继续切分:

C0:2页

C1:2页

C2:2页

C3:2页

最后可以将C0,C1,C2,C3切分为1个页面大小的内存块。

我们从C列来看,C0,C1称之为伙伴关系,C2,C3为伙伴关系。

同理,page0 和 page1也为伙伴关系,因为他们都是从C0分割出来的。

假设,page0正在使用,page1 和 page2都是空闲的。那page1 和 page 2 可以合并成一个大的内存块吗?

我们从上下级的关系来看,page 1,page 2 并不属于一个大内存块切割而来的,不属于伙伴关系。

如果我们把page 1 page 2,page4 page 5 合并了,看下结果会是什么样子。

page0和page3 就会变成大内存块中孤零零的空洞了。page 0 和 page3 就无法再和其他块合并了。这样就形成了外碎片化。因此,内核的伙伴系统是极力避免这种清空发生的。

伙伴系统在内核中的实现

下面我们看下内核中是怎么实现伙伴系统的。

上面这张图是内核中早期伙伴系统的实现

内核中把内存以2^order 为单位分为多个链表。order范围为[0,MAX_ORDER-1],MAX_ORDER一般为11。因此,Linux内核中可以分配的最大的内存块为2^10= 4M,术语叫做page block。

内核中有一个叫free_area的数据结构,这个数据结构为链表的数组。数组的大小为MAX_ORDER。数组的每个成员为一个链表。分别表示对应order的空闲链表。以上就是早期的伙伴系统的页面分配器的实现。

现在的伙伴系统中的页面分配器的实现,为了解决内存碎片化的问题,在Linux内核2.6.4中引入了迁移类型的 算法缓解内存碎片化的问题。

我们看这张图,现在的页面分配器中,每个free_area数组成员中都增加了一个迁移类型。也就是说在每个order链表中多增加了一个链表。例如,order = 0 的链表中,新增了MOVABLE 链表,UNMOVABLE 链表,RECLAIMABLE链表。随着内核的发展,迁移类型越来越多,但常用的就那三个。

迁移类型

在Linux内核2.6.4内核中引入了反碎片化的概念,反碎片化就是根据迁移类型来实现的。我们知道迁移类型 是根据page block来划分的。我们看下常用的迁移类型。

MIGRATE_UNMOVABLE:在内存中有固定位置,不能随意移动,比如内核分配的内存。那为什么内核分配的不能迁移呢?因此要迁移页面,首先要把物理页面的映射关系断开,在新的地方分配物理页面,重新建立映射关系。在断开映射关系的途中,如果内核继续访问这个页面,会导致oop错误或者系统crash。因为内核是敏感区,内核必须保证它使用的内存是安全的。这一点和用户进程不一样。如果是用户进程使用的内存,我们将其断开后,用户进程再去访问,就会产生缺页中断,重新去寻找可用物理内存然后建立映射关系。

MIGRATE_MOVABLE:可以随意移动,用户态app分配的内存,mlock,mmap分配的 匿名页面。

MIGRATE_RECLAIMABLE:不能移动可以删除回收,比如文件映射。

内存碎片化的产生

伙伴系统的迁移算法可以解决一些碎片化的问题,但在内存管理的方面,长期存在一个问题。从系统启动,长期运行之后,经过大量的分配-释放过程,还是会产生很多碎片,下面我们看下,这些碎片是怎么产生的。

我们以8个page的内存块为例,假设page3是被内核使用的,比如alloc_page(GFP_KERNRL),所以它属于不可移动的页面,它就像一个桩一样,插入在一大块内存的中间。

尽管其他的页面都是空闲页面,导致page0 ~ page 7 不能合并为一个大块的内存。

下面我们看下,迁移类型是怎么解决这类问题的。我们知道,迁移算法是以page block为单位工作的,一个page block大小就是页面分配器能分配的最大内存块。也就是说,一个page block 中的页面都是属于一个迁移类型的。所以,就不会存在上面说的多个page中夹着一个不可迁移的类型的情况。

页面分配和释放常用的函数

页面分配函数

alloc_pages是内核中常用的分配物理内存页面的函数,  用于分配2^order个连续的物理页。

static inline struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)

gfp_mask:gfp的全称是get free page , 因此gfp_mask表示页面分配的方法。

gfp_mask

    • 的具体分类后面我们会详细介绍。order:页面分配器使用伙伴系统按照顺序请求页面分配。所以只能以2的幂内存分配。例如,请求order=3的页面分配,最终会分配2 ^ 3 = 8页。arm64当前默认

MAX_ORDER为11, 即最多一次性分配2 ^(MAX_ORDER-1)个页。返回值:返回指向第一个page的struct page

    指针

__get_free_page() 是页面分配器提供给调用者的最底层的内存分配函数。它分配连续的物理内存。__get_free_page() 函数本身是基于 buddy 实现的。在使用 buddy 实现的物理内存管理中最小分配粒度是以页为单位的。

unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
    返回值:返回第一个page映射后的虚拟地址。
#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

alloc_page 是宏定义,逻辑是调用 alloc_pages,传递给 order 参数的值为 0,表示需要分配的物理页个数为 2 的 0 次方,即 1 个物理页,需要用户传递参数 GFP flags。

释放函数

void free_pages(unsigned long addr, unsigned int order)

释放2^order大小的页块,传入参数是页框首地址的虚拟地址

#define __free_page(page) __free_pages((page), 0)

释放一个页,传入参数是指向该页对应的虚拟地址

#define free_page(addr) free_pages((addr), 0)

释放一个页,传入参数是页框首地址的虚拟地址

gfp_mask标志位

行为修饰符
标志 描述
GFP_WAIT 分配器可以睡眠
GFP_HIGH 分配器可以访问紧急的内存池
GFP_IO 不能直接移动,但可以删除
GFP_FS 分配器可以启动文件系统IO
GFP_REPEAT 在分配失败的时候重复尝试
GFP_NOFAIL 分配失败的时候重复进行分配,直到分配成功位置
GFP_NORETRY 分配失败时不允许再尝试
zone 修饰符
标志 描述
GFP_DMA 从ZONE_DMA中分配内存(只存在与X86)
GFP_HIGHMEM 可以从ZONE_HIGHMEM或者ZONE_NOMAL中分配
水位修饰符
标志 描述
GFP_ATOMIC 分配过程中不允许睡眠,通常用作中断处理程序、下半部、持有自旋锁等不能睡眠的地方
GFP_KERNEL 常规的内存分配方式,可以睡眠
GFP_USER 常用于用户进程分配内存
GFP_HIGHUSER 需要从ZONE_HIGHMEM开始进行分配,也是常用于用户进程分配内存
GFP_NOIO 分配可以阻塞,但不会启动磁盘IO
GFP_NOFS 可以阻塞,可以启动磁盘,但不会启动文件系统操作

GFP_MASK和zone 以及迁移类型的关系

GFP_MASK除了表示分配行为之外,还可以表示从那些ZONE来分配内存。还可以确定从那些迁移类型的page block 分配内存。

我们以ARM为例,由于ARM架构没有ZONE_DMA的内存,因此只能从ZONE_HIGHMEM或者ZONE_NOMAL中分配.

在内核中有两个数据结构来表示从那些地方开始分配内存。

struct zonelist {
 struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
};struct zonelist

zonelist是一个zone的链表。一次分配的请求是在zonelist上执行的。开始在链表的第一个zone上分配,如果失败,则根据优先级降序访问其他zone。zlcache_ptr 指向zonelist的缓存。为了加速对zonelist的读取操作 ,用_zonerefs 保存zonelist中每个zone的index。

struct zoneref {
 struct zone *zone; /* Pointer to actual zone */
 int zone_idx;  /* zone_idx(zoneref->zone) */
};

页面分配器是基于ZONE来设计的,因此页面的分配有必要确定那些zone可以用于本次页面分配。系统会优先使用ZONE_HIGHMEM,然后才是ZONE_NORMAL 。

基于zone 的设计思想,在分配物理页面的时候理应以zone_hignmem优先,因为hign_memzone_ref中排在zone_normal的前面。而且,ZONE_NORMAL是线性映射的,线性映射的内存会优先给内核态使用。

页面分配的时候从那个迁移类型中分配出内存呢?

函数static inline int gfp_migratetype(const gfp_t gfp_flags)可以根据掩码类型转换出迁移类型,从那个迁移类型分配页面。比如GFP_KERNEL是从UNMOVABLE类型分配页面的。

ZONE水位

页面分配器是基于ZONE的机制来实现的,怎么去管理这些空闲页面呢?Linux内核中定义了三个警戒线,WATERMARK_MINWATERMARK_LOWWATERMARK_HIGH。大家可以看下面这张图,就是分配水位和警戒线的关系。

    • 最低水线(WMARK_MIN):当剩余内存在min以下时,则系统内存压力非常大。一般情况下min以下的内存是不会被分配的,min以下的内存默认是保留给特殊用途使用,属于保留的页框,用于原子的内存请求操作。比如:当我们在中断上下文申请或者在不允许睡眠的地方申请内存时,可以采用标志

GFP_ATOMIC来分配内存,此时才会允许我们使用保留在min水位以下的内存。低水线(WMARK_LOW):空闲页数小数低水线,说明该内存区域的内存轻微不足。默认情况下,该值为

WMARK_MIN的125%高水线(WMARK_HIGH):如果内存区域的空闲页数大于高水线,说明该内存区域水线充足。默认情况下,该值为

WMARK_MAX的150%

在进行内存分配的时候,如果分配器(比如buddy allocator)发现当前空余内存的值低于”low”但高于”min”,说明现在内存面临一定的压力,那么在此次内存分配完成后,kswapd将被唤醒,以执行内存回收操作。在这种情况下,内存分配虽然会触发内存回收,但不存在被内存回收所阻塞的问题,两者的执行关系是异步的

对于kswapd来说,要回收多少内存才算完成任务呢?只要把空余内存的大小恢复到”high”对应的watermark值就可以了,当然,这取决于当前空余内存和”high”值之间的差距,差距越大,需要回收的内存也就越多。”low”可以被认为是一个警戒水位线,而”high”则是一个安全的水位线。

如果内存分配器发现空余内存的值低于了”min”,说明现在内存严重不足。这里要分两种情况来讨论,一种是默认的操作,此时分配器将同步等待内存回收完成,再进行内存分配,也就是direct reclaim。还有一种特殊情况,如果内存分配的请求是带了PF_MEMALLOC标志位的,并且现在空余内存的大小可以满足本次内存分配的需求,那么也将是先分配,再回收。

per-cpu页面分配

内核会经常请求和释放单个页框,比如网卡驱动。

页面分配器分配和释放页面的时候需要申请一把锁:zone->lock

      • 为了提高单个页框的申请和释放效率,内核建立了per-cpu页面告诉缓存池其中存放了若干预先分配好的页框

当请求单个页框时,直接从本地cpu的页框告诉缓存池中获取页框

体现了预先建立缓存池的优势,而且是每个CPU有一个独立的缓存池

    • 不必申请锁不必进行复杂的页框分配操作
per-cpu数据结构

由于页框频繁的分配和释放,内核在每个zone中放置了一些事先保留的页框。这些页框只能由来自本地CPU的请求使用。zone中有一个成员pageset字段指向per-cpu的高速缓存,高速缓存由struct per_cpu_pages数据结构来描述。

struct per_cpu_pages {
 int count;  /* number of pages in the list */
 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];
};
    count:表示高速缓存中的页框数量。high :缓存中页框数量的最大值batch :buddy allocator增加或删除的页框数lists:页框链表。

本文参考

https://www.cnblogs.com/dennis-wong/p/14729453.html

https://blog.csdn.net/yhb1047818384/article/details/112298996

https://blog.csdn.net/u010923083/article/details/115916169

https://blog.csdn.net/farmwang/article/details/66975128

推荐器件

更多器件
器件型号 数量 器件厂商 器件描述 数据手册 ECAD模型 风险等级 参考价格 更多信息
LTC6994IS6-1#TRPBF 1 Analog Devices Inc LTC6994IS6-1#TRPBF
$3.41 查看
SN74LVC125APWR 1 Texas Instruments 4-ch, 1.65-V to 3.6-V buffers with 3-state outputs 14-TSSOP -40 to 125

ECAD模型

下载ECAD模型
$0.51 查看
SFH756V 1 Avago Technologies FIBER OPTIC TRANSMITTER, 10Mbps, THROUGH HOLE MOUNT, PLASTIC PACKAGE-4
$13.92 查看

相关推荐

电子产业图谱

作者就职于某500强公司,担任BSP工程师。具有丰富的嵌入式开发经验。专栏主要分享计算机基础,操作系统,Linux驱动开发,Arm体系与架构,C/C++,数据结构与算法等相关文章。欢迎关注我的公众号【嵌入式与Linux那些事】,一起学习交流。