当前位置: 主页 > Linux安装教程 > 环境部署 >

Linux系统下内存分配与释放算法

时间:2018-01-06 13:41来源:未知 作者:Linux先生 举报 点击:
内存分配与释放算法kmalloc()和kfree()分配和释放内存是以块(block)为单位进行的。

  内存分配与释放算法kmalloc()和kfree()分配和释放内存是以块(block)为单位进行的。
 


 

  (1)内存分配与释放的数据结构

  可以分配的空闲块的大小记录在blocksize表中,它是一个静态数组,定义在/mm/kmalloc.c中:

  #if PAGE_SIZE == 4096

  static const unsigned int blocksize[] = {

  32,64,128,252,508,1020,2040,

  4096-16,8192-16,16384-16,

  32768-16,65536-16,131072-16,

  0

  };

  在使用kmalloc()分配空闲块时仍以Buddy算法为基础,即以free_area[]管理的空闲页面块作为分配对象。重新制定了分配的单位,blocksize[]数组中的块长度。它可以分配比1个页面更小的内存空间。blocksize[]中的前7个是在1个空闲页面内进行分配,其后的6种分别对应free_area[]的1至32空闲页面块,当申请分配的空间小于或等于1个页面时,从free_area[]管理的1页面块中查找空闲页面进行分配。若申请的空间大于1个页面时,按照blocksize[]后六个块单位进行申请,从free_area[]中与该块长度对应的空闲页块组中查找空闲页面块。

  对kmalloc()分配的内存页面块中加上一个信息头,它处于该页面块的前部。页面块中信息头后的空间是可以分配的内存空间。加在页面块前部的信息头称为页描述符,定义在/mm/kmalloc.c中:

  struct page_descriptor {

  struct page_descriptor *next;  /* 指向下一个页面块的指针 */

  struct block_header *firstfree; /* 本页中空闲块链表的头 */

  int order;            /* 本页中块长度的级别 */

  int nfree;            /* 本页中空闲的数目 */

  };

  具有相同块单位和使用特性的页面块组成若干个链表。

  Linux设置了sizes[]数组,对页面块进行描述。数组元素是size_descriptor结构体,定义在/mm/kmalloc.c中:

  struct size_descriptor {

  struct page_descriptor *firstfree; /* 一般页块链表的头指针 */

  struct page_descriptor *dmafree; /* DMA页块链表的头指针 */

  int nblocks;      /* 页块中划分的块数目 */

  int nmallocs;      /* 链表中各页块中已分配的块总数 */

  int nfrees;       /* 链表中各页块中尚空闲的块总数 */

  int nbytesmalloced;  /* 链表中各页块中已分配的字节总数 */

  int npages;      /* 链表中页块数目 */

  unsigned long gfporder; /* 页块的页面数目 */

  };

  static struct size_descriptor sizes[] ={

  {NULL, NULL, 127, 0, 0, 0, 0, 0},

  {NULL, NULL, 63, 0, 0, 0, 0, 0},

  {NULL, NULL, 31, 0, 0, 0, 0, 0},

  {NULL, NULL, 16, 0, 0, 0, 0, 0},

  {NULL, NULL, 8, 0, 0, 0, 0, 0},

  {NULL, NULL, 4, 0, 0, 0, 0, 0},

  {NULL, NULL, 2, 0, 0, 0, 0, 0},

  {NULL, NULL, 1, 0, 0, 0, 0, 0},

  {NULL, NULL, 1, 0, 0, 0, 0, 1},

  {NULL, NULL, 1, 0, 0, 0, 0, 2},

  {NULL, NULL, 1, 0, 0, 0, 0, 3},

  {NULL, NULL, 1, 0, 0, 0, 0, 4},

  {NULL, NULL, 1, 0, 0, 0, 0, 5},

  {NULL, NULL, 0, 0, 0, 0, 0, 0}

  };

  blocksize[]与sizes[]元素数目相同,它们一一对应。由kmalloc()分配的每种块长度的页面块链接成两个链表,一个是DMA可以访问的页面块链表,dmafree指向这个链表。一个是一般的链表,firstfree指向这个链表。成员项gfporder是0~5,它作为2的幂数表示所含的页面数。

  由sizes[]管理的各个页面块中每个块(空闲块和占用块)的头部还有一个对该块进行描述的块头block_header:

  struct block_header {

  unsigned long bh_flags; /* 块的分配标志 */

  union {

  unsigned long ubh_length;   /* 块长度 */

  struct block_header *fbh_next; /*指向下一空闲块的指针 */

  } vp;

  };

  bh_flages是块的标志,有三种:

  MF_FREE指明该块是空闲块;

  MF_USED表示该块已占用;

  MF_DMA 表示该块是DMA可访问。

  ubh_length和fbh_next是联合体成员项,当块占用时使用ubh_length表示该块的长度;

  当块空闲时使用fbh_next链接下一个空闲块。

  在一个页块中的空闲块组成一个链表,表头由页块的page_descriptor中firstfree指出。

  (2)内存分配函数kmalloc()和释放函数kfree()

  void *kmalloc(size_t size, int priority)

  参数size是申请分配内存的大小,priority是申请优先级。

  priority常用的值为GFP_KERNEL、GFP_ATOMIC和GPF_DMA。

  priority取值GPF_DMA,表示申请的内存用于DMA传送。当内存不够时,priority取值GFP_KERNEL表示当前申请进程暂时被挂起而等待换页;取值GPF_ATOMIC时,表示该函数不允许推迟,而立即返回0值。

  kfree()用于释放由kmalloc()分配的内存空间:

  void kfree(void *__ptr)

  ptr是kmalloc()分配的内存空间的首地址。

  img22

  图4-8 sizes[]、kmalloc_cache[]和free_area[]的关系

  当kmalloc管理的一个页面块中的占用块全部被释放后,它就成为一个空闲页面块。系统把这个空闲页面块从sizes[]管理的相应链表中删除,把它交给free_area[]数组按照buddy算法管理。kmalloc()和kfree()还共同维护一个kmalloc缓冲区,由kmalloc_cache的数组进行管理,定义如下:

  #define MAX_CACHE_ORDER 3

  struct page_descriptor * kmalloc_cache[MAX_CACHE_ORDER];

  kmalloc_cache[]有3个元素,分别指向一个空闲的1、2、4页面块。由sizes[]管理的内存中有1页块、2页块或4页块被释放时,它们不立即交还free_area[]管理,先交给kmalloc_cache[]管理。sizes[]中有新的1页块、2页块或4页块被释放时,把kmalloc_cache[]当前指向的空闲页块交给free_area[]管理,然后指向新释放的空闲页块。三者的关系见图4-8。

  (3)虚拟内存的申请和释放

  在申请和释放较小且连续的内存空间时,使用kmalloc()和kfree()在物理内存中进行分配。申请较大的内存空间时,使用vmalloc()。由vmalloc()申请的内存空间在虚拟内存中是连续的,它们映射到在物理内存时,可以使用不连续的物理页面,而且仅把当前访问的部分放在物理页面中。由vmalloc()分配的虚存空间称为虚拟内存块(虚存块)。由vmalloc()分配的虚存块用一个链表来管理,系统定义的指针变量vmlist指向链表的表头,在mm/vmalloc.c中定义如下:

  static struct vm_struct * vmlist = NULL;

  结构vm_struct描述由vmalloc()分配虚存块:

  struct vm_struct {

  unsigned long flags;  /* 虚存块的标志 */

  void * addr;      /* 虚存块起始地址 */

  unsigned long size;   /*虚存块大小 */

  struct vm_struct * next; /* 指向下一个虚存块的指针 */

  };

  vmalloc()和vfree()定义在mm/vmalloc.c中:

  void * vmalloc(unsigned long size)

  void vfree(void * addr)

  可以看到vmalloc()参数size指出申请内存的大小。分配成功后,返回值为在虚存空间分配的虚存块首地址,失败返回值为0。vfree()用来释放由vmalloc()分配的虚存块,参数addr是要释放的虚存块首址。

 

------分隔线----------------------------
推荐内容