百科问答小站 logo
百科问答小站 font logo



从操作系统内存管理来说,malloc申请一块内存的背后原理是什么? 第1页

  

user avatar   qing-yu-bai-lu 网友的相关建议: 
      

这个问题我当时在学习操作系统的时候也疑惑过,后来在《手写操作系统》的时候,渐渐地对内存的这一块有比较清晰的认知:对于程序申请的内存来说,一般都是虚拟内存,操作系统只需要负责给其分配足够的虚拟空间就好了,让程序以为自己具有这些内存空间,而实际意义上的物理内存,是等到非用不可的时候,才会使用的。下文比较长,可以根据目录选择阅读:


前言

这一章将深入了解内存有关知识,第一步是学习划分物理内存与表示内存的方法,而后研究内存分配释放算法;第二步是学习如何表示虚拟内存,而后研究分配释放虚拟内存。

物理内存相关

内存的表示与组织

有关究竟内存是采用分段还是分页的讨论,在第五章CPU工作模式中已经讨论过了。

简而言之,内存采取分段的方式,一是不利于对内存状态进行表示,二是分段会产生较大的内存碎片,三是内存与硬盘的交换效率较低。

我们之后对内存相关的代码和研究都是基于4KB分页的内存模型(CPU长模式下,64位)

内存页的表示

逻辑上内存结构如下:



不过要注意,真实的地址空间是有空洞的,不是连续的,在第五章已经通过INT 15H中断获取了计算机的内存视图(e820map_t 结构数组已转换到phymmarge_t 结构数组),其中内存每一页都是4K对齐的,现在考虑第一个问题——如何表示一个内存页

如果用类似位图的方式来表示一个内存页已经被使用或者未被使用,比如标为1表示未被使用,为0表示已被使用。那么后续有关内存的分配算法等只能够采用最简单的遍历方式,但是效率却并不符合实际使用。

在实际的内存管理方式设计中,一个内存页的表示不仅要考虑它的状态(是否被分配),还要考虑到页的地址、分配次数、页的类型等,以结构的方式表示如下:

       //内存空间地址描述符标志 typedef struct s_MSADFLGS {     u32_t mf_olkty:2;    //挂入链表的类型     u32_t mf_lstty:1;    //是否挂入链表     u32_t mf_mocty:2;    //分配类型,被谁占用了,内核还是应用或者空闲     u32_t mf_marty:3;    //属于哪个区     u32_t mf_uindx:24;   //分配计数 }__attribute__((packed)) msadflgs_t;  ​ //物理地址和标志   typedef struct s_PHYADRFLGS {     u64_t paf_alloc:1;     //分配位     u64_t paf_shared:1;    //共享位     u64_t paf_swap:1;      //交换位     u64_t paf_cache:1;     //缓存位     u64_t paf_kmap:1;      //映射位     u64_t paf_lock:1;      //锁定位     u64_t paf_dirty:1;     //脏位     u64_t paf_busy:1;      //忙位     u64_t paf_rv2:4;       //保留位     u64_t paf_padrs:52;    //页物理地址位 }__attribute__((packed)) phyadrflgs_t; ​ //内存空间地址描述符 typedef struct s_MSADSC {     list_h_t md_list;           //链表     spinlock_t md_lock;         //保护自身的自旋锁     msadflgs_t md_indxflgs;     //内存空间地址描述符标志     phyadrflgs_t md_phyadrs;    //物理地址和标志     void* md_odlink;            //相邻且相同大小msadsc的指针 }__attribute__((packed)) msadsc_t;     

注意到上述masdsc_t结构占用的内存很小,这是因为每一个内存页就有一个这样的结构,它必须得小。另外,在物理地址和标志中,低12位被用作它用这是由于内存页4K对齐

内存分区

为了便于对内存的管理,以及不同内存区域功能的区分,我们通常会在逻辑上对内存进行分区,如下:



其中,硬件区位于低32MB空间,这个地址空间是给硬件使用的,它主要是提供给一些能够直接和内存交换数据的硬件,这些硬件不通过MMU进行虚拟地址到物理地址的转换,而是直接与物理地址打交道。

比较常见的是就是DMA访问内存,它只能访问低于24MB的物理内存,还有一些其他硬件也是如此,那么我们在分配内存的时候,就不应该将一部分低位内存分配出去。

之后的内存区,主要是考虑到内核也是运行在虚拟地址空间,将内核所使用的地址空间与物理地址空间一一对应,可以提高内存的运行效率。另外,有时需要在内核中分配连续、大块的内存,比如内核栈、显卡驱动等。总之,给内核单独分配一块区域具有很大的作用。

应用区,就是留给用户态程序所使用的内存区域了,这部分内存根据应用程序的需要,按需分配,如果访问到一个还没有与物理地址建立映射关系的虚拟地址时,会产生缺页异常,操作系统响应这个异常为其分配对应的物理内存页,从而达到“按需分配”。

那么如何表示一个内存区呢?其实无外乎内存页的状态,内存区的开始与结束物理地址等属性,用一个结构体来表示:

       typedef struct s_MEMAREA {     list_h_t ma_list;             //内存区自身的链表     spinlock_t ma_lock;           //保护内存区的自旋锁     uint_t ma_stus;               //内存区的状态     uint_t ma_flgs;               //内存区的标志      uint_t ma_type;               //内存区的类型     sem_t ma_sem;                 //内存区的信号量     wait_l_head_t ma_waitlst;     //内存区的等待队列     uint_t ma_maxpages;           //内存区总的页面数     uint_t ma_allocpages;         //内存区分配的页面数     uint_t ma_freepages;          //内存区空闲的页面数     uint_t ma_resvpages;          //内存区保留的页面数     uint_t ma_horizline;          //内存区分配时的水位线     adr_t ma_logicstart;          //内存区开始地址     adr_t ma_logicend;            //内存区结束地址     uint_t ma_logicsz;            //内存区大小     //还有一些结构我们这里不关心。后面才会用到 }memarea_t;     

这些标志现在不会讲,继续往后看就懂了,现在只需要了解有这些属性就够了。

现在思考一个问题——如何将内存区域内存页相关联起来

组织内存页

由于内存页是用msadsc_t结构体来表示的,组织内存页,即是找到一个合理、高效地方式来组织msadsc_t结构体。

注意到msadsc_t结构体中有链表,那么用链表串起来?——遍历链表跟遍历位图没有多大区别

在讲解代码的时候,先以一副图来表示如何在内存区memarea_t中组织内存页msadsc_t



我们在内存区中新建一个新的结构体——memdivmer_t,意指内存的分割与合并,分割即是将内存分配出去,合并即是内存被释放之后的回收。

memdivmer_t结构体中有一个dm_mdmlielst指针指向bafhlst_t结构体数组

而bafhlst_t链表将内存页msadsc_t用链表串联起来,并且每一个bafhlst_链表所拥有的内存页msadsc_t数量是不一样的,分别是0,2,4,6,……2^(n-1),其中n是该bafhlst结构体在dm_mdmlielst数组中的下标


为什么要用这样的方式来组织内存页呢?


需要注意的是,对于每一个bafhlst_t链表中的msadsc_t我们并不在意其中第一个 msadsc_t 结构对应的内存物理地址从哪里开始,但是第一个 msadsc_t 结构与最后一个 msadsc_t 结构,它们之间的内存物理地址是连续的


举个例子,对于dm_mdmlielst数组第0个bafhlst,它挂载一个msadsc_t结构体,其内存地址可以是0x4000~0x5FFF;

对于dm_mdmlielst数组第1个bafhlst,它挂载2个msadsc_t结构体,其内存地址可以是0x101000~0x102FFF, 0x103000~0x104FFF,即是0x101000~0x4FFF的连续区域

……

对于dm_mdmlielst数组第n个bafhlst,它挂载2^(n-1)个msadsc_t结构体,其内存地址也是一段连续区域

通过这种方式,我们可以对内存中较大/较小的连续区域分别进行组织,减小了内存碎片出现的可能


其中上述两个结构体的实现代码分别如下:

       typedef struct s_BAFHLST {     spinlock_t af_lock;    //保护自身结构的自旋锁     u32_t af_stus;         //状态      uint_t af_oder;        //页面数的位移量     uint_t af_oderpnr;     //oder对应的页面数比如 oder为2那就是1<<2=4     uint_t af_fobjnr;      //多少个空闲msadsc_t结构,即空闲页面     uint_t af_mobjnr;      //此结构的msadsc_t结构总数,即此结构总页面     uint_t af_alcindx;     //此结构的分配计数     uint_t af_freindx;     //此结构的释放计数     list_h_t af_frelst;    //挂载此结构的空闲msadsc_t结构     list_h_t af_alclst;    //挂载此结构已经分配的msadsc_t结构 }bafhlst_t; …… ​ #define MDIVMER_ARR_LMAX 52 typedef struct s_MEMDIVMER {     spinlock_t dm_lock;      //保护自身结构的自旋锁     u32_t dm_stus;           //状态     uint_t dm_divnr;         //内存分配次数     uint_t dm_mernr;         //内存合并次数     bafhlst_t dm_mdmlielst[MDIVMER_ARR_LMAX];//bafhlst_t结构数组     bafhlst_t dm_onemsalst;  //单个的bafhlst_t结构 }memdivmer_t;     

在下一节的分配、释放内存中,我们将会研究为什么这样的组织内存页。

内存的初始化

其实在内核启动最开始的阶段,我们需要先进行内存初始化才能够为后续的工作进行内存的分配和释放,虽然我们建立了内存页和内存区相关的结构体,但是还远远不够。

因为我们还没有在内存中建立对应的实例变量。我们都知道,在代码中实际操作的数据结构必须在内存中有相应的变量,而所谓对内存的初始化就是建立相应的数据结构对应的实例

内存的初始化主要有以下几个部分

       void init_memmgr() {     //初始化内存页结构     init_msadsc();     //初始化内存区结构     init_memarea();     //处理内存占用     init_search_krloccupymm(&kmachbsp);     //合并内存页到内存区中     init_merlove_mem();     init_memmgrob();     return; }     

由于这部分的知识主要是代码层面上的理解,因此建议直接阅读彭老师的原文

内存的分配与释放

内存分配

也许你会想象内存分配是这么进行的:在一段循环代码中,遍历所有的内存页,而后将一个空闲的内存页返回即可。

但是现实是,内存管理器需要为内核、驱动、应用程序提供复杂的内存服务——需要多少内存页?内存页需不需要连续?物理地址是否有要求?……

由于这些现实问题的存在,关于内存的分配和释放不能采取上述简单遍历的方式。

有关这部分的代码详见代码仓库,下面是我梳理出的一个函数调用逻辑图:



其实整个内存分配阶段最重要的部分就是如何从dm_mdmlielst数组中找到合适的bafhlst_t结构体,因为如果找到的bafhlst_t结构体中内存页msadsc_t过大,就会产生内存碎片,不利于下次内存的分配;如果找到的bafhlst_t结构体中内存页msadsc_t过小,就需要多个bafhlst_t结构体组合完成这次分配,效率又不高

这部分的逻辑在两个函数里,一个是对dm_mdmlielst数组中根据下标遍历找到合适的bafhlst_t

       //找到合适的bafhlst_t bool_t onmpgs_retn_bafhlst(memarea_t *malckp, uint_t pages , bafhlst_t **retrelbafh, bafhlst_t **retdivbafh) {     //获取bafhlst_t结构数组的开始地址     bafhlst_t *bafhstat = malckp->ma_mdmdata.dm_mdmlielst;            //根据分配页面数计算出分配页面在dm_mdmlielst数组中下标     sint_t dividx = retn_divoder(pages);     //从第dividx个数组元素开始搜索     for (sint_t idx = dividx; idx < MDIVMER_ARR_LMAX; idx++)     {     //如果第idx个数组元素对应的一次可分配连续的页面数大于等于请求的页面数         //,且其中的可分配对象大于0则返回          if (bafhstat[idx].af_oderpnr >= pages &&              0 < bafhstat[idx].af_fobjnr)         {             //返回请求分配的bafhlst_t结构指针             *retrelbafh = &bafhstat[dividx];             //返回实际分配的bafhlst_t结构指针             *retdivbafh = &bafhstat[idx];             return TRUE;         }     }     *retrelbafh = NULL;     *retdivbafh = NULL;     return FALSE; }     

二是,处理获取到的bafhlst_t结构体,根据实际需要的内存大小,有可能需要对其进行拆分,将其剩下的部分挂载其他的bafhlst_t上

       msadsc_t *mm_reldpgsdivmsa_bafhl(memarea_t *malckp, uint_t pages, uint_t *retrelpnr, bafhlst_t *relbfl, bafhlst_t *divbfl) {     msadsc_t *retmsa = NULL;     bool_t rets = FALSE;     msadsc_t *retmstat = NULL, *retmend = NULL;     //处理相等的情况     if (relbfl == divbfl)     {     //从bafhlst_t结构中获取msadsc_t结构的开始与结束地址         rets = mm_retnmsaob_onbafhlst(relbfl, &retmstat, &retmend);         //设置msadsc_t结构的相关信息表示已经删除         retmsa = mm_divpages_opmsadsc(retmstat, relbfl->af_oderpnr);         //返回实际的分配页数         *retrelpnr = relbfl->af_oderpnr;         return retmsa;     }     //处理不等的情况     //从bafhlst_t结构中获取msadsc_t结构的开始与结束地址     rets = mm_retnmsaob_onbafhlst(divbfl, &retmstat, &retmend);      uint_t divnr = divbfl->af_oderpnr;      //从高bafhlst_t数组元素中向下遍历     for (bafhlst_t *tmpbfl = divbfl - 1; tmpbfl >= relbfl; tmpbfl--)     {         //开始分割连续的msadsc_t结构,把剩下的一段连续的msadsc_t结构加入到对应该bafhlst_t结构中         if (mrdmb_add_msa_bafh(tmpbfl, &retmstat[tmpbfl->af_oderpnr], (msadsc_t *)retmstat->md_odlink) == FALSE)         {             system_error("mrdmb_add_msa_bafh fail
");         }         retmstat->md_odlink = &retmstat[tmpbfl->af_oderpnr - 1];         divnr -= tmpbfl->af_oderpnr;     } ​     retmsa = mm_divpages_opmsadsc(retmstat, divnr);     if (NULL == retmsa)     {         *retrelpnr = 0;         return NULL;     }     *retrelpnr = relbfl->af_oderpnr;     return retmsa; }     

彭老师所举的例子来解释一下这个过程:比如现在我们需要分配一个页面,这个算法将执行如下步骤:

1. 根据一个页面的请求,会返回 m_mdmlielst 数组中的第 0 个 bafhlst_t 结构(第0个bafhlst_t结构中挂载了一个内存页)。

2. 如果第 0 个 bafhlst_t 结构中有 msadsc_t 结构就直接返回,若没有 msadsc_t 结构(即这个bafhlst_t中的msadsc_t结构已经被用完了),就会继续查找 m_mdmlielst 数组中的第 1 个 bafhlst_t 结构。

3. 如果第 1 个 bafhlst_t 结构中也没有 msadsc_t 结构,就会继续查找 m_mdmlielst 数组中的第 2 个 bafhlst_t 结构。

4. 如果第 2 个 bafhlst_t 结构中有 msadsc_t 结构,记住第 2 个 bafhlst_t 结构中对应是 4 个连续的 msadsc_t 结构。这时让这 4 个连续的 msadsc_t 结构从第 2 个 bafhlst_t 结构中脱离。

5. 把这 4 个连续的 msadsc_t 结构,对半分割成 2 个双 msadsc_t 结构,把其中一个双 msadsc_t 结构挂载到第 1 个 bafhlst_t 结构中。

6. 把剩下一个双 msadsc_t 结构,继续对半分割成两个单 msadsc_t 结构,把其中一个单 msadsc_t 结构挂载到第 0 个 bafhlst_t 结构中,剩下一个单 msadsc_t 结构返回给请求者,完成内存分配

整个过程如下图所示



结合上面的代码、过程解释、流程图,现在我们对内存分配的具体过程有了较为详细的理解:如果当前下标的bafhlst_t中的msadsc结构不够,那就继续往后查,如果用不完当前bafhlst结构体中的msadsc还有剩余,就挂载到其之前的bafhlst_t结构体中

内存释放

内存的释放过程,其实是内存分配的逆过程。因为代码量太多,这里同样不放出具体的代码,详情可见cosmos/hal/x86/memdivmer.c,我梳理出的函数调用逻辑如下:



而在这个调用逻辑中,重点则是理解最后一个函数——如何将释放的内存页放到合适的bafhlst_t上呢?

先来看看代码:

       bool_t mm_merpages_onbafhlst(msadsc_t *freemsa, uint_t freepgs, bafhlst_t *relbf, bafhlst_t *merbf) {     sint_t rets = 0;     msadsc_t *mnxs = freemsa, *mnxe = &freemsa[freepgs - 1];     bafhlst_t *tmpbf = relbf;     //从实际要开始遍历,直到最高的那个bafhlst_t结构     for (; tmpbf < merbf; tmpbf++)     {         //查看最大地址连续、且空闲msadsc_t结构         //如释放的是第0个msadsc_t结构我们就去查找第1个msadsc_t结构是否空闲         //,且与第0个msadsc_t结构的地址是不是连续的         rets = mm_find_cmsa2blk(tmpbf, &mnxs, &mnxe);         if (1 == rets)         {             break;         }     }     //把合并的msadsc_t结构(从mnxs到mnxe)加入到对应的bafhlst_t结构中     if (mpobf_add_msadsc(tmpbf, mnxs, mnxe) == FALSE)     {         return FALSE;     }     return TRUE; } ​ bool_t mpobf_add_msadsc(bafhlst_t *bafhp, msadsc_t *freemstat, msadsc_t *freemend) {     freemstat->md_indxflgs.mf_olkty = MF_OLKTY_ODER;     //设置起始页面指向结束页     freemstat->md_odlink = freemend;     freemend->md_indxflgs.mf_olkty = MF_OLKTY_BAFH;     //结束页面指向所属的bafhlst_t结构     freemend->md_odlink = bafhp;     //把起始页面挂载到所属的bafhlst_t结构中     list_add(&freemstat->md_list, &bafhp->af_frelst);     //增加bafhlst_t结构的空闲页面对象和总的页面对象的计数     bafhp->af_fobjnr++;     bafhp->af_mobjnr++;     return TRUE; }     

参考彭老师的例子来解释这个过程:比如,现在我们要释放一个页面,这个算法将执行如下步骤。

  1. 释放一个页面,会返回 m_mdmlielst 数组中的第 0 个 bafhlst_t 结构
  2. 设置这个页面对应的 msadsc_t 结构的相关信息,表示已经执行了释放操作
  3. 开始查看第 0 个 bafhlst_t 结构中有没有空闲的 msadsc_t,并且它和要释放的 msadsc_t 对应的物理地址是连续的。没有则把这个释放的 msadsc_t 挂载第 0 个 bafhlst_t 结构中,算法结束,否则进入下一步(即有空闲的msadsc并且地址连续)。
  4. 把第 0 个 bafhlst_t 结构中的 msadsc_t 结构拿出来与释放的 msadsc_t 结构,合并成 2 个连续且更大的 msadsc_t
  5. 继续查看第 1 个 bafhlst_t 结构中有没有空闲的 msadsc_t,而且这个空闲 msadsc_t 要和上一步合并的 2 个 msadsc_t 对应的物理地址是连续的。没有则把这个合并的 2 个 msadsc_t 挂载第 1 个 bafhlst_t 结构中,算法结束,否则进入下一步。
  6. 把第 1 个 bafhlst_t 结构中的 2 个连续的 msadsc_t 结构,还有合并的 2 个地址连续的 msadsc_t 结构拿出来,合并成 4 个连续且更大的 msadsc_t 结构
  7. 继续查看第 2 个 bafhlst_t 结构,有没有空闲的 msadsc_t 结构,并且它要和上一步合并的 4 个 msadsc_t 结构对应的物理地址是连续的。没有则把这个合并的 4 个 msadsc_t 挂载第 2 个 bafhlst_t 结构中,算法结束
  8. ……

将上述过程,以流程图的方式表现如下:



小结

通过之前的学习,我们设计了一个较为优秀的内存页面管理器。其实这种管理内存页的方式,在Linux中也存在,并且称其为buddy内存分配算法(伙伴系统)。

有关buddy内存分配与释放算法的详细知识可以参考这两篇博客:

blog.csdn.net/btchengzi

blog.csdn.net/orange_os

内存页的细分

在之前的学习中,我们将内存页的大小定为4KB(也可以是2MB等等)。

试想,在我们写代码的时候,经常会出现动态分配数组的情况:

        char *str;           //内存分配 存放15个char字符类型        str = (char *) malloc(15);     if (str == NULL) {             printf("mem alloc err
");     return -1; }     

如上例,需要分配15个字节大小的内存空间。如果说这15个字节的内存空间,就单独分配一页4KB,内存使用率岂不是极低?

如果为了解决这种方式就将页的大小降低,那么势必会增加在页管理方面的性能损耗。

那么可不可以逻辑上再将页进行细分呢?——比如单独拿出一些内存页,将其划分为32 字节、64 字节、128 字节、256 字节、512 字节等大小的内存小块,如下图所示。



当需要分配较小的内存空间时,就从这些内存小块中选出合适的空间分配出去。

内存对象

将内存页中逻辑上划分的内存小块称为内存对象。用下面这个结构体来表示内存对象:

       typedef struct s_FREOBJH {     list_h_t oh_list;     //链表,将内存对象挂载在其他的结构上,常规操作     uint_t oh_stus;       //对象状态     void* oh_stat;        //对象的开始地址,即该对象的开头地址 }freobjh_t;     

同时,为了方便放置内存对象,设置一个内存对象容器来保存内存对象,结构体如下:

       //内存对象容器 typedef struct s_KMSOB {     list_h_t so_list;        //链表     spinlock_t so_lock;      //保护结构自身的自旋锁     uint_t so_stus;          //状态与标志     uint_t so_flgs;     adr_t so_vstat;          //内存对象容器的开始地址     adr_t so_vend;           //内存对象容器的结束地址     size_t so_objsz;         //内存对象大小     size_t so_objrelsz;      //内存对象实际大小     uint_t so_mobjnr;        //内存对象容器中总共的对象个数     uint_t so_fobjnr;        //内存对象容器中空闲的对象个数     list_h_t so_frelst;      //内存对象容器中空闲的对象链表头     list_h_t so_alclst;      //内存对象容器中分配的对象链表头     list_h_t so_mextlst;     //内存对象容器扩展kmbext_t结构链表头     uint_t so_mextnr;        //内存对象容器扩展kmbext_t结构个数     msomdc_t so_mc;          //内存对象容器占用内存页面管理结构     void* so_privp;          //本结构私有数据指针     void* so_extdp;          //本结构扩展数据指针 }kmsob_t; //管理内存对象容器扩展容量 typedef struct s_KMBEXT {     list_h_t mt_list;        //链表     adr_t mt_vstat;          //内存对象容器扩展容量开始地址     adr_t mt_vend;           //内存对象容器扩展容量结束地址     kmsob_t* mt_kmsb;        //指向内存对象容器结构     uint_t mt_mobjnr;        //内存对象容器扩展容量的内存中有多少对象 }kmbext_t; //管理内存对象容器占用的内存页面所对应的msadsc_t结构 typedef struct s_MSCLST {     uint_t ml_msanr;  //多少个msadsc_t     uint_t ml_ompnr;  //一个msadsc_t对应的连续的物理内存页面数     list_h_t ml_list; //挂载msadsc_t的链表 }msclst_t; //管理内存对象容器占用的内存 typedef struct s_MSOMDC {     //msclst_t结构数组mc_lst[0]=1个连续页面的msadsc_t     //               mc_lst[1]=2个连续页面的msadsc_t     //               mc_lst[2]=4个连续页面的msadsc_t     //               mc_lst[3]=8个连续页面的msadsc_t     //               mc_lst[4]=16个连续页面的msadsc_t     msclst_t mc_lst[MSCLST_MAX];     uint_t mc_msanr;   //总共多个msadsc_t结构     list_h_t mc_list;     //内存对象容器第一个占用msadsc_t     list_h_t mc_kmobinlst;     //内存对象容器第一个占用msadsc_t对应的连续的物理内存页面数     uint_t mc_kmobinpnr; }msomdc_t;     

上述代码一共有四个结构体,分别是内存对象容器kmsob_t,容器的扩展容量kmbext_t,用于管理内存对象占用的内存msclst_t与msomdc_t。它们之间的关系如下:



其中内存对象容器是用来挂载不同大小的内存对象,当当前内存页空间分配完毕之后,就需要再次向物理内存页面管理器请求分配一个内存页,而后在新的内存页上进行内存对象的划分,这个新的内存页就是所谓的扩展容量

内存对象分配

那么如何分配内存对象呢?

在我们的设计中,内存对象分配的核心函数是kmsob new opkmsob。它的功能很简单的,就是负责从空闲内存对象链表中取出第一个内存对象,返回它的首地址

       //判断内存对象容器中有没有内存对象 uint_t scan_kmob_objnr(kmsob_t *kmsp) {     if (0 < kmsp->so_fobjnr)     {         return kmsp->so_fobjnr;     }     return 0; } //实际分配内存对象 void *kmsob_new_opkmsob(kmsob_t *kmsp, size_t msz) {     //获取kmsob_t中的so_frelst链表头的第一个空闲内存对象     freobjh_t *fobh = list_entry(kmsp->so_frelst.next, freobjh_t, oh_list);     //从链表中脱链     list_del(&fobh->oh_list);     //kmsob_t中的空闲对象计数减一     kmsp->so_fobjnr--;     //返回内存对象首地址     return (void *)(fobh); } ​ void *kmsob_new_onkmsob(kmsob_t *kmsp, size_t msz) {     void *retptr = NULL;     cpuflg_t cpuflg;     knl_spinlock_cli(&kmsp->so_lock, &cpuflg);     //如果内存对象容器中没有空闲的内存对象了就需要扩展内存对象容器的内存了     if (scan_kmsob_objnr(kmsp) < 1)     {//扩展内存对象容器的内存         if (kmsob_extn_pages(kmsp) == FALSE)         {             retptr = NULL;             goto ret_step;         }     }     //实际分配内存对象     retptr = kmsob_new_opkmsob(kmsp, msz); ret_step:     knl_spinunlock_sti(&kmsp->so_lock, &cpuflg);     return retptr; }     

内存对象释放

内存对象释放的过程其实就是内存对象分配的逆过程:先根据释放内存对象的地址和大小,找到对应的内存对象容器,然后把该内存对象加入到对应内存对象容器的空闲链表上,最后查看是否需要释放内存对象容器占用的物理内存页面,代码如下:

       bool_t kmsob_delete_core(void *fadrs, size_t fsz) {     kmsobmgrhed_t *kmobmgrp = &memmgrob.mo_kmsobmgr;     bool_t rets = FALSE;     koblst_t *koblp = NULL;     kmsob_t *kmsp = NULL;     cpuflg_t cpuflg;     knl_spinlock_cli(&kmobmgrp->ks_lock, &cpuflg);     //根据释放内存对象的大小在kmsobmgrhed_t中查找并返回koblst_t,在其中挂载着对应的kmsob_t,这个在前面已经写好了     koblp = onmsz_retn_koblst(kmobmgrp, fsz);     if (NULL == koblp)     {         rets = FALSE;         goto ret_step;     }     kmsp = onkoblst_retn_delkmsob(koblp, fadrs, fsz);     if (NULL == kmsp)     {         rets = FALSE;         goto ret_step;     }     rets = kmsob_delete_onkmsob(kmsp, fadrs, fsz);     if (FALSE == rets)     {         rets = FALSE;         goto ret_step;     }     if (_destroy_kmsob(kmobmgrp, koblp, kmsp) == FALSE)     {         rets = FALSE;         goto ret_step;     }     rets = TRUE; ret_step:     knl_spinunlock_sti(&kmobmgrp->ks_lock, &cpuflg);     return rets; } //释放内存对象接口 bool_t kmsob_delete(void *fadrs, size_t fsz) {     //对参数进行检查,但是多了对内存对象地址的检查      if (NULL == fadrs || 1 > fsz || 2048 < fsz)     {         return FALSE;     }     //调用释放内存对象的核心函数     return kmsob_delete_core(fadrs, fsz); }     

值得注意的是,当频繁请求不同大小的内存对象并再释放时,就会留下大量的空闲内存对象,这对于内存也是一种浪费。因此我们需要一种策略来将空闲内存对象容器回收,先看看代码:

       uint_t scan_freekmsob_isok(kmsob_t *kmsp) {     //当内存对象容器的总对象个数等于空闲对象个数时,说明这内存对象容器空闲     if (kmsp->so_mobjnr == kmsp->so_fobjnr)     {         return 2;     }     return 1; } ​ bool_t _destroy_kmsob_core(kmsobmgrhed_t *kmobmgrp, koblst_t *koblp, kmsob_t *kmsp) {     list_h_t *tmplst = NULL;     msadsc_t *msa = NULL;     msclst_t *mscp = kmsp->so_mc.mc_lst;     list_del(&kmsp->so_list);     koblp->ol_emnr--;     kmobmgrp->ks_msobnr--;     //释放内存对象容器扩展空间的物理内存页面     //遍历kmsob_t结构中的so_mc.mc_lst数组     for (uint_t j = 0; j < MSCLST_MAX; j++)     {         if (0 < mscp[j].ml_msanr)         {//遍历每个so_mc.mc_lst数组中的msadsc_t结构             list_for_each_head_dell(tmplst, &mscp[j].ml_list)             {                 msa = list_entry(tmplst, msadsc_t, md_list);                 list_del(&msa->md_list);                 //msadsc_t脱链                 //释放msadsc_t对应的物理内存页面                 if (mm_merge_pages(&memmgrob, msa, (uint_t)mscp[j].ml_ompnr) == FALSE)                 {                     system_error("_destroy_kmsob_core mm_merge_pages FALSE2
");                 }             }         }     }     //释放内存对象容器本身占用的物理内存页面     //遍历每个so_mc.mc_kmobinlst中的msadsc_t结构。它只会遍历一次     list_for_each_head_dell(tmplst, &kmsp->so_mc.mc_kmobinlst)     {         msa = list_entry(tmplst, msadsc_t, md_list);         list_del(&msa->md_list);         //msadsc_t脱链         //释放msadsc_t对应的物理内存页面         if (mm_merge_pages(&memmgrob, msa, (uint_t)kmsp->so_mc.mc_kmobinpnr) == FALSE)         {             system_error("_destroy_kmsob_core mm_merge_pages FALSE2
");         }     }     return TRUE; } //销毁内存对象容器 bool_t _destroy_kmsob(kmsobmgrhed_t *kmobmgrp, koblst_t *koblp, kmsob_t *kmsp) {     //看看能不能销毁     uint_t screts = scan_freekmsob_isok(kmsp);     if (2 == screts)     {//调用销毁内存对象容器的核心函数         return _destroy_kmsob_core(kmobmgrp, koblp, kmsp);     }     return FALSE; }     

上述代码的主要逻辑就是,查看内存对象容器是否空闲(即该内存对象容器中全部都是空闲的内存对象),如果是空闲的,就对其进行销毁。

虚拟内存相关

大家需要明白,之前我们所有对内存的管理,是针对物理内存的。但是对于运行的进程来说,它们的地址空间应该都是虚拟内存地址,因此,接下来我们就需要学习如何表示虚拟内存页,并且如何将虚拟内存页和物理内存页相关联最后我们研究如何分配和释放虚拟内存。

虚拟内存的表示

首先,虚拟地址空间有多大取决于处理器的位数——32位的处理器的虚拟地址空间为0~0xFFFFFFFF;64位的虚拟机地址空间为0xFFFFFFFFFFFFFFFF。但我们应该明白,虚拟地址空间只是一个逻辑上的概念,既然是逻辑上的概念,那么我们就可以对这个虚拟地址空间进行相关的安排和设计。

虚拟内存分区

同物理内存划分段一样,我们也对虚拟地址空间进行分段将一部分地址用来放内核,另一部分地址用来放应用。对于x86 CPU,根据CPU所处的工作模式不同,我们可以将虚拟地址空间划分如下:




值得注意的是,长模式下的内存空间实在是太大,现在CPU其实只实现了48位的地址寻址,然而寄存器确实是64位的,因此高16位的数值其实是第47位的扩展。由于长模式下“天然”将内存空间分为了上下两个部分(排除保留空间),那就一部分给内核,另一部分给应用结合各个部分的堆、栈、指令区、数据区、MMU页表等概念,我们将整个虚拟地址空间划分如下:



线性映射区使得内核能通过加减一个固定值的方式,方便的完成虚拟地址与物理地址的转换

虚拟内存的表示

那么我们用什么样的数据结构来表示虚拟内存页以及相应的内存区呢?——在物理内存设计时,我们采用了一个内存页来表示一个内存,一个内存区间就是一系列内存页

但是在虚拟内存空间,这个方法行不通——因为虚拟地址空间太大了!常见物理内存大小也就8G、16G等等,但是对于64位机,虚拟地址可达2^64次方,这是一个天文数字,单单是保存这些数据结构就足以将物理内存给用关,所以只能另寻它路

由于虚拟地址空间往往是以区为单位的,比如栈区、堆区,指令区、数据区这些区内部往往是连续的,区与区之间却间隔了很大空间,而且每个区的空间扩大时我们不会建立新的虚拟地址区间数据结构而是改变其中的指针,这就节约了内存空间

基于这个现象,我们将虚拟内存区的数据结构设计如下:

       typedef struct KMVARSDSC {     spinlock_t kva_lock;        //保护自身自旋锁     u32_t  kva_maptype;         //映射类型     list_h_t kva_list;          //链表     u64_t  kva_flgs;            //相关标志     u64_t  kva_limits;     void*  kva_mcstruct;        //指向它的上层结构     adr_t  kva_start;           //虚拟地址的开始     adr_t  kva_end;             //虚拟地址的结束     kvmemcbox_t* kva_kvmbox;    //管理这个结构映射的物理页面     void*  kva_kvmcobj; }kmvarsdsc_t;     

将所有的虚拟内存区顺序串联起来,就是整个虚拟内存地址空间

       typedef struct s_VIRMEMADRS {     spinlock_t vs_lock;            //保护自身的自旋锁     u32_t  vs_resalin;     list_h_t vs_list;              //链表,链接虚拟地址区间     uint_t vs_flgs;                //标志     uint_t vs_kmvdscnr;            //多少个虚拟地址区间     mmadrsdsc_t* vs_mm;            //指向它的上层的数据结构     kmvarsdsc_t* vs_startkmvdsc;   //开始的虚拟地址区间     kmvarsdsc_t* vs_endkmvdsc;     //结束的虚拟地址区间     kmvarsdsc_t* vs_currkmvdsc;    //当前的虚拟地址区间     adr_t vs_isalcstart;           //能分配的开始虚拟地址     adr_t vs_isalcend;             //能分配的结束虚拟地址     void* vs_privte;               //私有数据指针     void* vs_ext;                  //扩展数据指针 }virmemadrs_t;     

虚拟地址是针对应用程序也就是进程而言的,那么它应该是进程的一个属性。对于一个进程来说,单单了解自身的虚拟地址空间还不够,还需要知道其他的信息,比如虚拟地址到物理内存地址的映射关系、各个区的开始和结束地址等,我们将这些信息组织起来共同表示一个进程的地址空间,结构体如下

       typedef struct s_MMADRSDSC {     spinlock_t msd_lock;               //保护自身的自旋锁     list_h_t msd_list;                 //链表     uint_t msd_flag;                   //状态和标志     uint_t msd_stus;     uint_t msd_scount;                 //计数,该结构可能被共享     sem_t  msd_sem;                    //信号量     mmudsc_t msd_mmu;                  //MMU相关的信息     virmemadrs_t msd_virmemadrs;       //虚拟地址空间     adr_t msd_stext;                   //应用的指令区的开始、结束地址     adr_t msd_etext;     adr_t msd_sdata;                   //应用的数据区的开始、结束地址     adr_t msd_edata;     adr_t msd_sbss;                     //栈区的开始、结束地址     adr_t msd_ebss;     adr_t msd_sbrk;                    //应用的堆区的开始、结束地址     adr_t msd_ebrk; }mmadrsdsc_t;     

每段虚拟地址区间,在用到的时候都会映射对应的物理页面。前面我们物理内存管理器的设计,每分配一个或者一组内存页面,都会返回一个 msadsc_t 结构,所以我们还需要一个数据结构来挂载 msadsc_t 结构

考虑到把一个文件映射到进程的虚拟地址空间中,只需要在内存页面中保留一份共享文件多个程序就都可以共享它。我们用一个结构体来管理它:

       typedef struct KVMEMCBOX  {     list_h_t kmb_list;        //链表     spinlock_t kmb_lock;      //保护自身的自旋锁     refcount_t kmb_cont;      //共享的计数器     u64_t kmb_flgs;           //状态和标志     u64_t kmb_stus;     u64_t kmb_type;           //类型     uint_t kmb_msanr;         //多少个msadsc_t     list_h_t kmb_msalist;     //挂载msadsc_t结构的链表     kvmemcboxmgr_t* kmb_mgr;  //指向上层结构     void* kmb_filenode;       //指向文件节点描述符     void* kmb_pager;          //指向分页器 暂时不使用     void* kmb_ext;            //自身扩展数据指针 }kvmemcbox_t;     

另外,再设计一个数据结构,用来挂载所有的kvmemcbox_t结构体,:

       typedef struct KVMEMCBOXMGR  {     list_h_t kbm_list;        //链表     spinlock_t kbm_lock;      //保护自身的自旋锁     u64_t kbm_flgs;           //标志与状态     u64_t kbm_stus;      uint_t kbm_kmbnr;         //kvmemcbox_t结构个数     list_h_t kbm_kmbhead;     //挂载kvmemcbox_t结构的链表     uint_t kbm_cachenr;       //缓存空闲kvmemcbox_t结构的个数     uint_t kbm_cachemax;      //最大缓存个数,超过了就要释放     uint_t kbm_cachemin;      //最小缓存个数     list_h_t kbm_cachehead;   //缓存kvmemcbox_t结构的链表     void* kbm_ext;            //扩展数据指针 }kvmemcboxmgr_t;     

我们对上面所有的数据结构做一个梳理:



从上倒下,从左到右来理解这个图。一个进程的虚拟地址空间由virmemadrs_t 结构管理,图上每一个 kmvarsdsc_t 结构就表示一个已经分配出去的虚拟地址空间。由于虚拟地址空间需要映射到实际物理内存页面,统一用kvmemcbox_t来管理,而所有的kvmemcbox_t都被kvmemcboxmgr来管理。

虚拟内存的分配与释放

从前面的学习中我们了解到,整个虚拟地址空间就是由一个个虚拟地址区间组成的。那么不难猜到,分配一个虚拟地址空间就是在整个虚拟地址空间分割出一个区域,而释放一块虚拟地址空间,就是把这个区域合并到整个虚拟地址空间中去

这节课重点是理解概念,具体的代码请参考代码仓库或者彭老师的课程。

虚拟内存的分配

在我们的设计中,进程可以指定虚拟内存的开始地址(可能失败,因为被用了),也可以由系统分配,但是一定会指定分配内存的大小

那么如何从地址空间中找到一个合适的虚拟地址分配出去?其实重点是遍历,是的,遍历

参考neohope的留言——虚拟地址空间分配函数调用过程如下: vma_new_vadrs -> vma_new_vadrs_core ->-> vma_find_kmvarsdsc 1、查找合适的 kmvarsdsc_t结构 2、如果可以复用找到的kmvarsdsc_t结构,扩容 3、如果无法复用,创建新的kmvarsdsc_t结构,加入到 virmemadrs_t【按地址有序】

其中,vma_find_kmvarsdsc->vma_find_kmvarsdsc_is_ok的查找过程为 依次检查virmemadrs_t中全部 kmvarsdsc_t结构: 1、如果没有指定起始地址,则判断当前kmvarsdsc_t与下一个kmvarsdsc_t之间,是否有未分配的虚拟地址,长度满足要求,否则就查询下一个结构; 2、如果制定了起始地址,则判断当前kmvarsdsc_t与 下一个kmvarsdsc_t之间,,是否有未分配的虚拟地址,起始地址和长度都满足要求,否则就查询下一个结构;


这个部分的核心代码如下:

       //检查kmvarsdsc_t结构 kmvarsdsc_t *vma_find_kmvarsdsc_is_ok(virmemadrs_t *vmalocked, kmvarsdsc_t *curr, adr_t start, size_t vassize) {     kmvarsdsc_t *nextkmvd = NULL;     adr_t newend = start + (adr_t)vassize;     //如果curr不是最后一个先检查当前kmvarsdsc_t结构     if (list_is_last(&curr->kva_list, &vmalocked->vs_list) == FALSE)     {//就获取curr的下一个kmvarsdsc_t结构         nextkmvd = list_next_entry(curr, kmvarsdsc_t, kva_list);         //由系统动态决定分配虚拟空间的开始地址         if (NULL == start)         {//如果curr的结束地址加上分配的大小小于等于下一个kmvarsdsc_t结构的开始地址就返回curr             if ((curr->kva_end + (adr_t)vassize) <= nextkmvd->kva_start)             {                 return curr;             }         }         else         {//否则比较应用指定分配的开始、结束地址是不是在curr和下一个kmvarsdsc_t结构之间             if ((curr->kva_end <= start) && (newend <= nextkmvd->kva_start))             {                 return curr;             }         }     }     else     {//否则curr为最后一个kmvarsdsc_t结构         if (NULL == start)         {//curr的结束地址加上分配空间的大小是不是小于整个虚拟地址空间             if ((curr->kva_end + (adr_t)vassize) < vmalocked->vs_isalcend)             {                 return curr;             }         }         else         {//否则比较应用指定分配的开始、结束地址是不是在curr的结束地址和整个虚拟地址空间的结束地址之间             if ((curr->kva_end <= start) && (newend < vmalocked->vs_isalcend))             {                 return curr;             }         }     }     return NULL; } //查找kmvarsdsc_t结构 kmvarsdsc_t *vma_find_kmvarsdsc(virmemadrs_t *vmalocked, adr_t start, size_t vassize) {     kmvarsdsc_t *kmvdcurrent = NULL, *curr = vmalocked->vs_currkmvdsc;     adr_t newend = start + vassize;     list_h_t *listpos = NULL;     //分配的虚拟空间大小小于4KB不行     if (0x1000 > vassize)     {         return NULL;     }     //将要分配虚拟地址空间的结束地址大于整个虚拟地址空间 不行     if (newend > vmalocked->vs_isalcend)     {         return NULL;     } ​     if (NULL != curr)     {//先检查当前kmvarsdsc_t结构行不行         kmvdcurrent = vma_find_kmvarsdsc_is_ok(vmalocked, curr, start, vassize);         if (NULL != kmvdcurrent)         {             return kmvdcurrent;         }     }     //遍历virmemadrs_t中的所有的kmvarsdsc_t结构     list_for_each(listpos, &vmalocked->vs_list)     {         curr = list_entry(listpos, kmvarsdsc_t, kva_list);         //检查每个kmvarsdsc_t结构         kmvdcurrent = vma_find_kmvarsdsc_is_ok(vmalocked, curr, start, vassize);         if (NULL != kmvdcurrent)         {//如果符合要求就返回             return kmvdcurrent;         }     }     return NULL; }     

虚拟内存的释放

这个部分的重点是找到合适的kmvarsdsc_t的结构体,而后将释放的虚拟内存地址放进去。

同样借用neohope的留言来解释这个过程:虚拟地址空间释放 vma_del_vadrs ->vma_del_vadrs_core ->->vma_del_find_kmvarsdsc 根据起始地址,查找要释放虚拟地址空间的kmvarsdsc_t结构; 根据要释放的空间与kmvarsdsc_t结构起始地址有四种情况: A、首位都相等,砍掉kmvarsdsc_t结构 B、开始相等,砍掉kmvarsdsc_t开始 C、结尾相等,砍掉kmvarsdsc_t结尾 D、首尾都不相等,砍掉中间部分,两边拆分为两个kmvarsdsc_t结构

代码就不放了,就是根据释放的空间与kmvarsdsc_t结构体空间的关系来决定释放的方式。

虚拟内存的虚与实——缺页异常

其实当我们完成虚拟地址分配之后,这个虚拟地址是不能用的!

如果我们对这个虚拟地址进行访问,那么它会产生一个缺页异常——因为我们仅仅是分配了一个虚拟地址空间,就对它进行访问,所以才会缺页。我们并没有为这个虚拟地址空间分配任何物理内存页面建立对应的 MMU 页。

那么我们在分配虚拟地址的时候就分配相应的物理地址,而后建立MMU页面?

但是为了节约物理内存,实际操作系统设计的时候是采用延迟分配的方式。

何为延迟分配?——就是先将虚拟地址分配出去,但是不分配相对应的物理内存页面,等到程序运行到这个虚拟地址时,才会去分配物理内存

这个过程的核心代码如下:

       sint_t vma_map_fairvadrs_core(mmadrsdsc_t *mm, adr_t vadrs) {     sint_t rets = FALSE;     adr_t phyadrs = NULL;     virmemadrs_t *vma = &mm->msd_virmemadrs;     kmvarsdsc_t *kmvd = NULL;     kvmemcbox_t *kmbox = NULL;     knl_spinlock(&vma->vs_lock);     //查找对应的kmvarsdsc_t结构     kmvd = vma_map_find_kmvarsdsc(vma, vadrs);     if (NULL == kmvd)     {         rets = -EFAULT;         goto out;     }     //返回kmvarsdsc_t结构下对应kvmemcbox_t结构     kmbox = vma_map_retn_kvmemcbox(kmvd);     if (NULL == kmbox)     {         rets = -ENOMEM;         goto out;     }     //分配物理内存页面并建立MMU页表     phyadrs = vma_map_phyadrs(mm, kmvd, vadrs, (0 | PML4E_US | PML4E_RW | PML4E_P));     if (NULL == phyadrs)     {         rets = -ENOMEM;         goto out;     }     rets = EOK; out:     knl_spinunlock(&vma->vs_lock);     return rets; }     

对上述代码总结一下,主要是三件事: 查看这个kmvarsdsc_t 虚拟地址是否合法;建立一个kvmemcbox结构体,挂载到kmvarsdsc_t 上;为kmvarsdsc_t 的kvmemcbox结构体分配一个物理内存页面,并加入MMU页表数据

致谢

代码仓库

16 | 划分土地(上):如何划分与组织内存?

17 | 划分土地(中):如何实现内存页面初始化?

18 | 划分土地(下):如何实现内存页的分配与释放?

19 | 土地不能浪费:如何管理内存对象?

20 | 土地需求扩大与保障:如何表示虚拟内存?

21 | 土地需求扩大与保障:如何分配和释放虚拟内存?


user avatar   jun-jun-42-59 网友的相关建议: 
      

1116回答下

5年前,在上家公司,因为malloc/free导致OOM,损失了上千万

1、先是分析代码,查找内存泄漏,内部全部是智能指针,且不存在循环引用,最终怀疑gblic释放时候存在问题。

2、开始分析glibc源码,大概用了1个月时间吃透了整个malloc/free源码,最终结论是free的时候,glibc并不会将内存归还给os,而是在合适的时候,进行trim

3、下面是application申请内存时候的宏观图

4、glibc的分配和释放远比我想象复杂的多,里面涉及到bin概念

fast bins,small bins,largebins,top chunk,mmaped chunk以及lastremainder chunk

内存的释放和分配都是在上面这些里面操作的

5、下面是malloc流程图

6、free流程如下图

7、用了一个月分析代码,然后用了三周时间来写对gblic内存管理进行整理

由于篇幅有限,相关文章链接如下




  

相关话题

  为什么 Windows 比 Linux 的文件搜索慢很多? 
  为什么一个字节定义成8位? 
  为什么win7,win10很多人用,win8,win8.1却无人问津? 
  为什么win7,win10很多人用,win8,win8.1却无人问津? 
  计算机底层是如何访问显卡的? 
  我听说以前的系统没有图形界面,那他们是用 C# 等语言直接敲代码吗? 
  为什么atomic比mutex性能更高? 
  学习 Linux 有哪些好处? 
  Mac上的gcc和Linux上的不一样吗,为啥这段代码运行结果不同? 
  计算机windows7操作系统到底是属于多用户还是单用户? 

前一个讨论
为什么中国小学数学教育要揪“除”和“除以”的区别?
下一个讨论
当有些事无处倾诉又很想倾诉,怎么办?





© 2024-05-17 - tinynew.org. All Rights Reserved.
© 2024-05-17 - tinynew.org. 保留所有权利