内存池解析

内存池

---

内存池(Memory Pool)是一种内存分配方式，又被称为固定大小区块规划（fixed-size-blocks allocation）。通常我们习惯直接使用new、malloc等API申请分配内存，这样做的缺点在于：由于所申请内存块的大小不定，当频繁使用时会造成大量的内存碎片并进而降低性能。与此同时，频繁的进行malloc和free操作很容易造成内存碎片。且因为malloc支持多线程同时操作，所以会使用进程同步锁。根据malloc的实现原理，线程在进行malloc操作时，如果无法获得同步锁，会在另外的heap区开辟子区域进行内存申请，有效避免等待，但是频繁获得锁会造成开销。

malloc底层原理

---

1. malloc开始搜索空闲内存块，如果能找到一块大小合适的就分配出去
2. malloc无法找到一块合适的内存，调用brk等系统调用扩大堆区进而获得更多空闲内存
3. malloc开始调用brk后开始转为内核态，此时操作系统中的虚拟地址系统开始工作，扩大进程的堆区，操作系统并没有为此分配真正的物理内存
4. brk执行结束后返回到malloc，从内核态切换到用户态，malloc找到一块合适的空闲内存后返回进程拿到内存，继续干活。
5. 当有代码读写新申请的内存时系统内部出现缺页中断，此时再由用户态切换到内存态，操作系统分配物理内存，切换位用户态继续运行。

实现一个固定大小的内存池

---

固定大小的内存池的优点，只需要支持固定大小的内存块的申请和释放，性能可以达到极致。且不需要进行内存碎片的问题

原理：在使用之前，先分配一定数量，大小的块。当需要内存时，向内存池申请。如果内存全部分配，则内存池继续申请一大块内存进行分配

• 初始化一个头节点作为寻址的头节点（MemoryPool）
• 通过MemoryPool进行内存分配，如果发现MemoryPool所指向的第一块MemoryBlock或者现有MemoryPool没有空闲内存块，则创建一个新的MemoryBlock初始化之后将其插入MemoryPool的头
• 在内存分配的时候，遍历MemoryPool中的单链表MemoryBlock，根据地址判断所要释放的内存属于哪个MemoryBlock，然后根据偏移设置MemoryBlock的第一块空闲块索引，同时将空闲块个数+1

• 在每个MemoryBlock中使用头来存储使用情况

  struct MemoryBlock {
  	unsigned int size;
  	unsigned int free_size;
  	unsigned int first_free;
  
  	struct MemoryBlock *next;
  	char a_data[0];	//柔性数组，C语言结构体中的最后一个元素可以是大小未知的数组
  };
  1
  2
  3
  4
  5
  6
  7
  8

• 内存池头MemoryPool，内存池头定义了内存池的信息

  struct MemoryPool {
  	unsigned int obj_size; // 固定内存块大小
  	unsigned int init_size;  // 初始化内存池中内存块数量
  	unsigned int grow_size;  // 使用完当前内存块，再次申请个数
  	MemoryBlock *first_block;  // 指向第一个Block
  };
  1
  2
  3
  4
  5
  6

线程池对外接口

接口函数实现

---

memory_pool_create

MemoryPool *memory_pool_create(unsigned int init_size, unsigned int grow_size, unsigned int size)
    MemoryPool *mp;
	mp = (MemoryPool*)malloc(sizeof(MemoryPool));
	mp->first_block = NULL;
	mp->init_size = init_size;
	mp->grow_size = grow_size;

	if(size < sizeof(unsigned int))
		mp->obj_size = sizeof(unsigned int);
	mp->obj_size = (size + (MEMPOOL_ALIGNMENT-1)) & ~(MEMPOOL_ALIGNMENT-1);

	return mp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

memory_alloc：内存分配

void *memory_alloc(MemoryPool *mp) {
    	unsigned int i;
	unsigned int length;

	if(mp->first_block == NULL) {
		MemoryBlock *mb;
		length = (mp->init_size)*(mp->obj_size) + sizeof(MemoryBlock);
		mb = malloc(length);
		if(mb == NULL) {
			perror("memory allocate failed!\n");
			return NULL;
		}
        mb->next = NULL;
		mb->free_size = mp->init_size - 1;
		mb->first_free = 1;
		mb->size = mp->init_size*mp->obj_size;
        
        mp->first_block = mb;
        char *data = mb->a_data;
        
        for(i=1;i<mp->init_size;++i) {
            *(unsigned long *)data= i;
            data += mp->obj_size;
        }
        return (void *)mb->a_data;
    }
    MemoryBlock *pm_block = mp->first_block;
    
    while((pm_block != NULL) && (pm_block->free_size == 0)) {
		pm_block = pm_block->next;
	}
    
    if(pm_block != NULL) {
        		char *pfree = pm_block->a_data + pm_block->first_free * mp->obj_size;

		pm_block->first_free = *((unsigned long *)pfree);
		pm_block->free_size--;

		return (void *)pfree;
    } else {
        if(mp->grow_size == 0)
			return NULL;
		
    MemoryBlock *new_block = (MemoryBlock *)malloc((mp->grow_size)*(mp->obj_size) + sizeof(MemoryBlock));

		if(new_block == NULL)
			return NULL;

		char *data = new_block->a_data;

		for(i=1; i<mp->grow_size; ++i) {
			*(unsigned long *)data = i;
			data += mp->obj_size;
		}		

		new_block->size = mp->grow_size*mp->obj_size;
		new_block->free_size = mp->grow_size-1;
		new_block->first_free = 1;
		new_block->next = mp->first_block;
		mp->first_block = new_block;
		
		return (void *)new_block->a_data;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

内存释放：

void* memory_free(MemoryPool *mp, void *pfree) {
    	if(mp->first_block == NULL) {
    return;
  }
    
    MemoryBlock *pm_block = mp->first_block;
    MemoryBlock *pm_pre_block = mp->first_block;
    
    while(pm_block && ((unsigned long)pfree < (unsigned long)pm_block->a_data || 
		(unsigned long)pfree>((unsigned long)pm_block->a_data+pm_block->size))) {
		//pm_pre_block = pm_block;
		pm_block = pm_block->next;

		if(pm_block == NULL) {
      return pfree;
    }
    }
    
    unsigned int offset = pfree -(void*) pm_block->a_data;

	if((offset&(mp->obj_size -1)) > 0) {
    return pfree;
  }
    pm_block->free_size++;
	*((unsigned int *)pfree) = pm_block->first_free;

	pm_block->first_free=(unsigned int)(offset/mp->obj_size);

	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

释放内存池：

void free_memory_pool(MemoryPool *mp) {
	MemoryBlock *mb = mp->first_block;

	if(mb != NULL) {
		while(mb->next != NULL) {
			s_memory_block *delete_block = mb;
			mb = mb->next;

			free(delete_block);
		}

		free(mb);
	}
  
	free(mp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

tcmalloc内存池

---

在实现了一个单线程固定大小线程池后，可以看一下tcmalloc的内存池，这是谷歌的开源项目，实现了高效的多线程内存管理，用于替代系统的内存分配相关的函数（malloc、free，new，new[]等），在线程级实现了缓存，在申请的大多数情况下无锁内存分配

小内存的分配和释放（小于等于256K）

• ThreadCache：线程级缓存 ：用于小于256k的内存分配，线程从这里申请内存不需要加锁，每个线程独享一个cache
• Central Cache：中央缓存 ：线程共享，让内存在多个线程中按需调度，有竞争，使用桶锁，竞争不激烈
• PageHeap：页缓存 ：存储的内存是以页为单位存储及分配的，自动合并相连的页，组成更大的页，缓解内存碎片

tcmalloc的初始化

tcmalloc的初始化在TCMallocGuard的构造函数中完成，TCMallocGuard的构造函数如下所示

static int tcmallocguard_refcount = 0;  // no lock needed: runs before main()
TCMallocGuard::TCMallocGuard() {
  if (tcmallocguard_refcount++ == 0) {
    ReplaceSystemAlloc();    // defined in libc_override_*.h
    tc_free(tc_malloc(1));
    ThreadCache::InitTSD();    // Thread Specific Data
    tc_free(tc_malloc(1));
    // Either we, or debugallocation.cc, or valgrind will control memory
    // management.  We register our extension if we're the winner.
#ifdef TCMALLOC_USING_DEBUGALLOCATION
    // Let debugallocation register its extension.
#else
    if (RunningOnValgrind()) {
      // Let Valgrind uses its own malloc (so don't register our extension).
    } else {
      MallocExtension::Register(new TCMallocImplementation);
    }
#endif
  }
}
    // 初始化方式是调用tcmalloc申请一个字节之后调用tc_free释放
    // 初始化时会初始 1.初始化SizeMap  2.初始化各种Allocator  3.初始化CentralCache  4.创建PageHeap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

tcmalloc的内存分配算法概览

按照所分配的内存大小，tcmalloc分为三类

1. 小对象分配 (0,255]
2. 中对象分配 (225kb,1mb]
3. 大对象分配 (1mb,无穷大)

几个概念

• Page

  tcmalloc将整个虚拟空间划分为n个大小相同的Page，每个page默认为8kb

• Span

  将连续的n个Page称为一个Span

• PageHeap

  TCMalloc定义了PageHeap类来处理向OS申请内存相关的操作，并提供了一层缓存。可以认为，PageHeap就是整个可供应用程序动态分配的内存的抽象。

  PageHeap以span为单位向系统申请内存，申请到的span可能只有一个page，也可能包含n个page。可能会被划分为一系列的小对象，供小对象分配使用，也可能当做一整块当做中对象或大对象分配

小对象分配

• size Class

  对于256kb以内的小对象分配，tcmalloc分配了88个类别，称为size Class，每个size Class对应一个大小。在申请时会向上取整到size Class大小，保证内部碎片不会过多

• ThreadCache

  tcmalloc为每个线程分配单独缓存空间（ThreadCache），每个ThreadCache中对于每个sizeClass都有一个单独的FreeList，缓存n个未被应用程序使用的空闲对象

• 小对象直接从ThreadCache的Freelist中返回一个空闲对象，对象的回收也是直接放回到Freelist中

• 每个对象都有一个ThreadCache，因此取用或者回收内存不需要加锁

• 将线程的ThreadCache连接成一个双向链表，结构大致如下
  

• CentralCache

  ThreadCache中的空闲对象由CentralCache（公用缓存）

  与Thread的FreeList相似，CentralCache也拥有一个单独链表处理缓存空闲对象（CentralFreeList），供线程取用空闲对象

  CentralCache为线程共用，从CentralCache取用或者回收对象，需要加锁。为了平摊锁操作的开销，ThreadCache会一次性申请多个对象

• PageHeap

  CentralCache中空闲对象的来源，PageHeap是tcmalloc对可动态分配的内存的抽象

  当CentralCache中的空闲对象不够用时，CentralCache会向PageHeap申请一块内存（可能来自PageHeap的缓存，也可能向系统申请新的内存），并将其拆分成一系列空闲对象，添加到对应size class的CentralFreeList中。

  PageHeap内部根据内存块（span）的大小采取了两种不同的缓存策略。128个page以内的span，每个大小都用一个链表来缓存，超过128个page的span，存储于一个有序set（std::set）。讨论TCMalloc的实现细节时再具体分析，现在可以认为PageHeap的简化结构如下

• 小对象的内存回收

  当调用free或者delete一个对象时，将其插回ThreadCache的FreeList

中对象分配

---

超过256KB但不超过1MB（128个page）的内存分配被认为是中对象分配，采取了与小对象不同的分配策略。

中对象也会向上取整（单位page），然后向PageHeap申请一定数量page的span然后返回起始地址

TCMalloc对于span的管理（小于128page，1MB）

• PageHeap中有128个小span的链表，分别对应1~128个page的span

• 需要分配一个内存，向上取整k个page，从PageHeap取一个大小为k个page的span

  从k个page的span链表到128个page的span链表，按序找到一个非空链表

  取出非空链表的span，拆分这个span

  拆分后一个为k个page的span作为结果返回，另一个span插入到大小为n-k个page的链表中

  如果无非空链表，按最大对象分配

大对象分配

---

超过1MB（128个page）的内存分配被认为是大对象分配，与中对象分配类似，也是先将所要分配的内存大小向上取整到整数个page，假设是k个page，然后向PageHeap申请一个k个page大小的span。

• 大对象分配用到的都是超过128个page的span，缓存方式为按span大小排列的有序set

实现细节

---

Page

page是tcmalloc管理内存的基本单位（不等于操作系统内存管理的page），page增大速度变快，但是会带来内存碎片

PageID

从内存空间0x0开始，每个page对应一个递增的PageID，可以通过移位计算id，8kb13位

Span

• 一个span记录了起始page的PageID（start），以及所包含page的数量（length）
• 一个span要么被拆分成多个相同size class的小对象用于小对象分配，要么作为一个整体用于中对象或大对象分配。当作用作小对象分配时，span的sizeclass成员变量记录了其对应的size class。
• span中还包含两个Span类型的指针（prev, next），用于将多个span以链表的形式存储。

span的三种状态

1. IN_USE

   span为PageHeap管理的，就是已经分配了，不在PageHeap

2. ON_NORMAL_FREELIST

3. ON_RETURNED_FREELIST

   ON_NORMAL_FREELIST和ON_RETURNED_FREELIST都可以认为是空闲状态。ON_RETURNED_FREELIST已经释放给系统了，（调用使用madvise实现），即使归还依然可用，只丢失修改。

空闲对象链表

被拆分的span还包含了一个记录空闲对象的链表objects，由CentralFreeList维护

对于新创建的span，将对应的内存按size class的大小均分，每一个小对象均含有下一个小对象的地址

在一系列申请和回收顺序不定

PageMap

用于解决问题：给定一个page，确定这个page所属的span

在root_数组中包含512个指向Leaf的指针，每个Leaf又是1024个void*的数组，数组索引为PageID，数组元素为page所属Span的指针。一共219个数组元素，对应32位系统的219个page。
使用两级map可以减少TCMalloc元数据的内存占用，因为初始只会给第一层（即root_数组）分配内存（2KB），第二层只有在实际用到时才会实际分配内存。而如果初始就给219个page都分配内存的话，则会占用219 * 4 bytes = 2MB的内存，底层使用基数树

基数树(radix tree)

---

• 基数树基础知识

  压缩前缀树，是一种更节省空间的Trie（前缀树）。对于基数树的每个结点，如果该结点是确定的子树的话，就和父节点合并

  基数树将长整数与指针键值相关联，解决Hash冲突和Hash表大小的设计问题

  利用基数树可以根据一个长整型（比如一个长ID，或一串地址）快速查找到其对应的对象指针（在redis中用来存储stream消息队列，tcmalloc中用来建立page id和span*的映射）

  基数树的空间使用更加灵活，只有当需要用到某节点时才会去创建它(pageMap)

Size Class

---

• 合并操作

  TCMalloc会将相同page数量，相同对象数量的相邻的size class合并为一个size class。

  合入后对象大小取两者之中大的那个

• 记录映射关系

  一个size class对应着（一个对象大小，一个申请page的数量，一个批量移动对象的数量）

  tcmalloc将信息的映射关系记录在三个以class的编号为索引的数组中（class_to_size, num_objects_to_move, class_to_pages_）

  由于size class之间有间隔（1024字节以内间隔8字节，1024以上间隔128字节）计算索引方式如下

  // s <= 1024
  static inline size_t SmallSizeClass(size_t s) {
   return (static_cast<uint32_t>(s) + 7) >> 3;
  }
  
  // s > 1024
  static inline size_t LargeSizeClass(size_t s) {
   return (static_cast<uint32_t>(s) + 127 + (120 << 7)) >> 7;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 计算任意内存地址对应的对象大小

  当应用程序调用free()或delete释放内存时，需要有一种方式获取所要释放的内存地址对应的内存大小。结合前文所述的各种映射关系，在TCMalloc中按照以下顺序计算任意内存地址对应的对象大小：

  计算给定地址计所在的PageID（ptr >> 13）
  从PageMap中查询该page所在的span
  span中记录了size class编号
  据size class编号从class_to_size_数组中查询对应的对象大小
  这样做的好处是：不需要在内存块的头部记录内存大小，减少内存的浪费。

PageHeap

---

tcmalloc管理划分后的内存，由PageHeap负责

1. 空闲Span管理器

   分为两个部分，小于128page–小Page，大于128page–大Page。PageHeap对小的使用链表，大的使用std::set进行管理

   PageHeap分开管理ON_NORMAL_FREELIST和ON_RETURNED_FREELIST状态的span的。所有小span对应两个链表，大span对应两个set

Nginx的线程池

---

Nginx使用内存池对内存进行管理，把内存分配分为大内存分配和小内存分配。申请内存大小超过同页内存池最大值还大，为大内存分配，否则小内存分配

大块内存直接向系统申请一块内存，将这块内存挂到内存池头部的large字段下

小块内存直接从内存池中进行分配

ngx内存池的缺点

---

Nginx有效降低了内存分片，减少了内存泄露的可能性。在使用小内存时只是通过分割来分配内存，这一方面简化了操作效率，但是小块内存因为没有管理信息的维护而不能及时释放和重用。只能在内存池释放时才能作为整体释放，但是Nginx本身运行就是阶段化的，特定内存池只在特定阶段存在，使得内存不能及时释放问题不大。

数据结构

数据块

typedef struct {
    u_char               *last;  // 未使用开始地址
    u_char               *end;   // 内存池结束地址
    ngx_pool_t           *next;   // 指向下一个内存池
    ngx_uint_t            failed;  // 失败次数
} ngx_pool_data_t;  // 数据区
1
2
3
4
5
6

池结构

struct ngx_pool_s {
    ngx_pool_data_t       d;  // 数据区域
    size_t                max;  // max size every time
    ngx_pool_t           *current;  //own * which is last pool 
    ngx_chain_t          *chain;  // 缓冲区链表
    ngx_pool_large_t     *large;  // big message chain
    ngx_pool_cleanup_t   *cleanup;  // 清理回调函数
    ngx_log_t            *log;  
};
1
2
3
4
5
6
7
8
9

大内存块

struct ngx_pool_large_s {
    ngx_pool_large_t     *next;     // 指向下一个large类型内存的指针
    void                 *alloc;    // 所分配的内存指针
};
1
2
3
4

回收结构

struct ngx_pool_cleanup_s {
    ngx_pool_cleanup_pt   handler;  // 清理的回调函数
    void                 *data;  // 指向存储的数据地址
    ngx_pool_cleanup_t   *next;  //  指向下一个ngx_pool_cleanup_t*
};  // 清理回调的数据结构
1
2
3
4
5

源码分析

内存池的创建

// 简单的封装了malloc
void *
ngx_alloc(size_t size, ngx_log_t *log)
{
    void  *p;

    p = malloc(size);  // 返回函数起始地址
    if (p == NULL) {  // 判空
        ngx_log_error(NGX_LOG_EMERG, log, ngx_errno,
                      "malloc(%uz) failed", size);
    }

    ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, log, 0, "malloc: %p:%uz", p, size);

    return p;
}
// 创建内存池
ngx_pool_t *
ngx_create_pool(size_t size, ngx_log_t *log) {
    ngx_pool_t *p;

    p = ngx_alloc(size, log);
    if (p == NULL) {
        return NULL;
    }
	// 可以看到last指向pool数据区的开始，即下一个可分配块地址
    p->d.last = (u_char *) p + sizeof(ngx_pool_t);
    // end 指向pool的size的最后，即当前pool可容纳的最大尺寸的结束位置
    p->d.end = (u_char *)p + size;
    p->d.next = NULL;
    p->d.failed = 0;
	// 将size去掉ngx_pool_t的数据头
    size = size - sizeof(ngx_pool_t);

    p->max = (size < NGX_MAX_ALLOC_FROM_POOL) ? size : NGX_MAX_ALLOC_FROM_POOL;
	/*
	nginx对内存的管理分为大内存与小内存，
	当某一个申请的内存大于某一个值时，就需要从大内存中分配空间，否则从小内存中分配空间。
	nginx中的内存池是在创建的时候就设定好了大小，
	在以后分配小块内存的时候，如果内存不够，则是重新创建一块内存串到内存池中，而不是将原有的内存池进行扩张。
	当要分配大块内存时，则是在内存池外面再分配空间进行管理的，称为大块内存池。
	*/
    p->current = p;
    p->chain = NULL;
    p->large = NULL;
    p->cleanup = NULL;
    p->log = log;

    return p;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

摧毁内存池

#define ngx_free          free

void 
ngx_destroy_pool(ngx_pool_t *pool)
{
    ngx_pool_t          *p, *n;
    ngx_pool_large_t    *l;
    ngx_pool_cleanup_t  *c;


    for (c = pool->cleanup; c; c->next) {
        if (c->handler) {
            ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, pool->log, 0,
                "run cleanup: %p", c);
            c->handler(c->data);
        }
    }
    for (l = pool->large; l; l = l->next) {
        if (l->alloc) {
            ngx_free(l->alloc);
        }
    }

    for (p = pool, n = pool->d.next; /* void */; p = n, n = n->d.next) {
        ngx_free(p);

        if (n == NULL) {
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

重置内存池

void
ngx_reset_pool(ngx_pool_t *pool)
{
    ngx_pool_t *p;
    ngx_pool_large_t *l;
	// 先遍历large链表，释放large内存  
    for (l = pool->large; l; l->next) {
        if (l->alloc) {
            ngx_free(l->alloc);
        }
    }
    
    // 重置小块内存区
    for (p = pool; p; p = pool->d.next) {
        p->d.last = (u_char *)p + sizeof(ngx_pool_t);
        p->d.failed = 0;
    }

    pool->current = pool;
    pool->chain = NULL;
    pool->large = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

分配内存

// ngx_align_ptr :一个地址取整的宏，提高性能
#define ngx_align_ptr(p, a)                                                   \
       (u_char *) (((uintptr_t) (p) + ((uintptr_t) a - 1)) & ~((uintptr_t) a - 1))
/*
首先当a为2,4,8,16等2的幂时，假设为2^n，a-1的后n位为1。所以按位与之后，后n位为0。
总体上按最大基本类型进行对齐：其首地址能被其类型的自身对齐值整除，不能整除时，移到下一个开始处
取整可以降低CPU读取内存的次数，提高性能。
*/

static ngx_inline void *
ngx_palloc_small(ngx_pool_t *pool, size_t size, ngx_uint_t align)
{
    u_char *m;
    ngx_pool_t *p;

    p = pool->current;  // 小于max，从current开始遍历pool链表

    do {
        // 每次从last处分配内存
        m = p->d.last;

        if (align) {
            m = ngx_align_ptr(m, NGX_ALIGNMENT);
        }

        if ((size_t)(p->d.end - m) >= size) {
            // 内存够用，直接分配，并且移动last指针
            p->d.last = m + size;

            return m;
        }

        p = p->d.next;
    } while (p);
    // 如果没有能够分配的size大小的节点，生成新的节点，并分配内存
    return ngx_palloc_block(pool, size);
}


void *
ngx_palloc(ngx_pool_t *pool, size_t size)
{
#if !(NGX_DEBUG_PALLOC)
    if (size <= pool->max) {  // 分配内存小于max使用小内存分配
        return ngx_palloc_small(pool, size, 1);
    }
#endif
  // 大于max使用palloc_large来分配内存
    return ngx_palloc_large(pool, size);
}

static void *
ngx_palloc_block(ngx_pool_t *pool, size_t size)
{
    u_char      *m;
    size_t       psize;
    ngx_pool_t  *p, *new;
    
    // 计算内存池第一个内存块的大小
    psize = (size_t) (pool->d.end - (u_char *) pool);
    // 分配一个和第一块内存一样大小的内存块
    m = ngx_memalign(NGX_POOL_ALIGNMENT, psize, pool->log);
    if (m == NULL) {
        return NULL;
    }

    new = (ngx_pool_t *) m;

    new->d.end = m + psize;  // 设置内存块的新end
    new->d.next = NULL;
    new->d.failed = 0;

    m += sizeof(ngx_pool_data_t);  // 指针移到d后面第一个位置，作为起始位置
    m = ngx_align_ptr(m, NGX_ALIGNMENT);  // 对m指针按4字节对齐处理
    new->d.last = m + size;  // 设置新块的last，即申请使用size大小的内存

    for (p = pool->current; p->d.next; p = p->d.next) {
        if (p->d.failed++ > 4) {
            pool->current = p->d.next;
        }
    }

    p->d.next = new;

    return m;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

大内存分配

/*
ngx_palloc_large :开辟一个大内存并交给大内存链表进行管理。所开辟的内存必定存在大内存链表上
*/

static void *
ngx_palloc_large(ngx_pool_t *pool, size_t size)
{
    void              *p;
    ngx_uint_t         n;
    ngx_pool_large_t  *large;

    p = ngx_alloc(size, pool->log);  // 直接调用malloc，与内存池链表无关
    if (p == NULL) {
        return NULL;
    }

    n = 0;
	// 遍历large链表，判断有没有被释放的大数据块，有就赋值，没有跳出
    for (large = pool->large; large; large = large->next) {
        if (large->alloc == NULL) {
            large->alloc = p;
            return p;
        }

        if (n++ > 3) {
            break;
        }
    }
	// 新建large结构用于管理新内存
    large = ngx_palloc_small(pool, sizeof(ngx_pool_large_t), 1);
    if (large == NULL) {
        ngx_free(p);
        return NULL;
    }

    large->alloc = p;  // 将新开辟内存交给large链表进行管理
    large->next = pool->large;  // 插入紧邻large
    pool->large = large;

    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

内存清理

/*
指定释放大内存链表的一块大内存
因为大内存的管理是支持释放某一块大内存的，所以上面的ngx_palloc_large函数每一次都检查前三个是否为空，确保前三个有内存空间可用，至于后面是否为空就只能不怎么关心了。
*/

#define ngx_free          free

ngx_int_t
ngx_pfree(ngx_pool_t *pool, void *p)
{
    ngx_pool_large_t  *l;
	// 遍历大内存链表，若找到想要释放的大内存则释放，否则返回错误NGX_DECLINED
    for (l = pool->large; l; l = l->next) {
        if (p == l->alloc) {
            ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, pool->log, 0,
                           "free: %p", l->alloc);
            ngx_free(l->alloc);
            l->alloc = NULL;

            return NGX_OK;
        }
    }

    return NGX_DECLINED;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

cleanup机制

/*
pool->cleanup本身是一个链表，每个ngx_pool_cleanup_t的数据结构上，保存着内存数据的本身cleanup->data和回调清理函数cleanup->handler
ngx_pool_cleanup_add 分配一个可以用于回调清理内存块的内存。内存块仍旧留在p->d或者p->large上
*/

ngx_pool_cleanup_t *
ngx_pool_cleanup_add(ngx_pool_t *p, size_t size)
{
    // 创建一个新的ngx_pool_cleanup_t结构体并给内部成员开辟内存空间
    ngx_pool_cleanup_t  *c;

    c = ngx_palloc(p, sizeof(ngx_pool_cleanup_t));
    if (c == NULL) {
        return NULL;
    }

    if (size) {
        c->data = ngx_palloc(p, size);
        if (c->data == NULL) {
            return NULL;
        }

    } else {
        c->data = NULL;
    }
	// 使用头插法，并回到设为NULL等待设置
    
    c->handler = NULL;
    c->next = p->cleanup;

    p->cleanup = c;

    ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, p->log, 0, "add cleanup: %p", c);

    return c;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

清除指定的文件描述符

void ngx_pool_run_cleanup_file(ngx_pool_t *p, ngx_fd_t fd) {
	ngx_pool_cleanup_t *c;
	ngx_pool_cleanup_file_t *cf;
 
 	// 遍历清理链表
	for (c = p->cleanup; c; c = c->next) {
		if (c->handler == ngx_pool_cleanup_file) {
 
			cf = c->data;//因为为清理文件描述符，此时的c->data应为ngx_pool_cleanup_file_t的结构体类型
 			
 			// 判断是否是指定要删除的fd
			if (cf->fd == fd) {
				c->handler(cf); /* 调用ngx_pool_cleanup_file回调函数清理指定内存cf */
				c->handler = NULL;
				return;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

slab内存池的实现

---

内核将相同尺寸的内存块用一个内核数据结构struct free_area中的双向链表free_list串联组织起来

struct free_area {
 struct list_head free_list[MIGRATE_TYPES];
 unsigned long  nr_free;
};
1
2
3
4

free_list串联起来的相同尺寸的内存块根据物理内存页的迁移类型【MIGRATE_TYPES】进行归类

• MIGRATE_UNMOVABLE （不可移动的页面类型）
• MIGRATE_MOVABLE （可以移动的内存页类型）
• MIGRATE_RECLAIMABLE （不能移动，但是可以直接回收的页面类型）

• slab，slub，slob的区分：

  slab：初号机，实现复杂，拥有多种存储对象队列，管理开销大

  slub：提高slab性能，吞吐量，降低内存浪费，成为常见实现

  slob：为嵌入式小型机器设计的

• 内存对齐的作用

  在工业级的设计中，我们需要考虑内存对齐，CPU访问一块没有对齐的内存比访问内存对齐的速度要慢一倍(CPU向内存读取数据的单位是根据word size来的，在64位处理器中word size = 8字节)，CPU一次访问按照8字节进行对齐的地址，如果没有对齐，就要访问两次

• slab的初始填充 当 slab 刚刚从伙伴系统中申请出来，并初始化划分物理内存页中的对象内存空间时，内核会将对象的 object size 内存区域用特殊字节 0x6b 填充，并用 0xa5 填充对象 object size 内存区域的最后一个字节表示填充完毕。

  或者当对象被释放回 slab 对象池中的时候，也会用这些字节填充对象的内存区域。

• slab中毒

  通过在对象内存区域填充特定字节表示对象的特殊状态的行为

      struct page {      
            // 首页 page 中的 flags 会被设置为 PG_head 表示复合页的第一页
            unsigned long flags;	
            // 其余尾页会通过该字段指向首页
            unsigned long compound_head;   
            // 用于释放复合页的析构函数，保存在首页中
            unsigned char compound_dtor;
            // 该复合页有多少个 page 组成，order 还是分配阶的概念，在首页中保存
            // 本例中的 order = 2 表示由 4 个普通页组成
            unsigned char compound_order;
            // 该复合页被多少个进程使用，内存页反向映射的概念，首页中保存
            atomic_t compound_mapcount;
            // 复合页使用计数，首页中保存
            atomic_t compound_pincount;
      }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

slab 的具体信息也是在 struct page 中存储，下面提取了 struct page 结构中和 slab 相关的字段：

struct page {

        struct {    /*  slub 相关字段 */
            union {
                // slab 所在的管理链表
                struct list_head slab_list;
                struct {    /* Partial pages */
                    // 用 next 指针在相应管理链表中串联起 slab
                    struct page *next;
#ifdef CONFIG_64BIT
                    // slab 所在管理链表中的包含的 slab 总数
                    int pages;  
                    // slab 所在管理链表中包含的对象总数
                    int pobjects; 
#else
                    short int pages;
                    short int pobjects;
#endif
                };
            };
            // 指向 slab cache，slab cache 就是真正的对象池结构，里边管理了多个 slab
            // 这多个 slab 被 slab cache 管理在了不同的链表上
            struct kmem_cache *slab_cache;
            // 指向 slab 中第一个空闲对象
            void *freelist;     /* first free object */
            union {
                struct {            /* SLUB */
                    // slab 中已经分配出去的独享
                    unsigned inuse:16;
                    // slab 中包含的对象总数
                    unsigned objects:15;
                    // 该 slab 是否在对应 slab cache 的本地 CPU 缓存中
                    // frozen = 1 表示缓存再本地 cpu 缓存中
                    unsigned frozen:1;
                };
            };
        };

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

参考：性能优化-高效内存池的设计与实现

参考：高并发内存池—tcmalloc核心框架学习