4.5.2 内存分配与释放算法
内存分配与释放算法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()分配的内存空间的首地址。
图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是要释放的虚存块首址。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
