动态内存分配器的一个简易实现

发表于 | | 阅读次数: |

堆是进程空间里很重要的一部分，有效的使用堆可以很大程度上提高程序的性能，本文参考《深入理解计算机系统》简要的实现了一个内存分配器。

介绍

这是用C语言实现的一个简易的动态内存分配器，模拟动态内存的分配与回收，是本学期CSAPP课程的第五个实验。它是基于mmlib包所提供的一个存储器系统模型，在对此进行的扩充。实现了用于堆Heap内存管理的动态分配功能。

内存管理与动态分配

内存管理

是在系统层面对计算机内存的一种操作，它的基本要求是：在程序需要内存的时候，能够提供一种方式动态的分配给它；并且当应用程序不再使用时，要能回收。而操作系统动态分配的内存区域称作为堆(Heap)。

动态内存分配

动态内存分配器维护着一个进程的虚拟存储区域，称为堆(Heap)，对于每个进程，内核维护着一个变量brk，它指向堆区域的顶部。栈是向下增长，而堆是向上增长的。而对于brk的改变需要系统调用，因为系统调用有很大的开销，如果让用户每次需要堆的时候都自己调用系统调用是很浪费时间的，所以需要对这堆Heap的分配进行封装。

一般做法是先分一大块堆空间，然后对分配的堆空间管理起来，提供接口，以后每次用户需要申请堆的时候，调用这些封装后的函数就行了，它们是用户层的函数，开销不大，这种封装也叫做动态内存分配器。

分配器有两种类型，一种是隐式分配，一种是显示分配。本次实现是基于显示分配的。

  • 显示分配：要求应用程序显示的释放任何已分配的块，如C、C++语言
  • 隐式分配：也称作垃圾回收器GC(garbage collector)，是由分配器检测一个已分配块何时不再被程序所使用，并主动释放这个块，如Java、C#语言。

显示分配

本次实验是采用显示分配策略，通过一种隐式链表的形式，来链接每个空闲块以及已分配块。因为在内存分配中，不能使用复合数据类型，如队列、链表来组织这些内存块，本实验是通过对一些位进行标记，每个空闲块都有一个头部和脚部，大小为机器字长。如下图所示：
带边界标记的块

为什么要用低三位来标记一个块呢？

内部碎片与外部碎片的折中考虑,会造成不同空余位的选择， 空3位表明最小块是8个字节。余下的位可用于其他方面的标记，比如合并后的脚部，该位用于表明前一块是否是空闲的。

这样就可以定义一些宏操作用于操纵这些空闲块，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 根据块的大小和是否被标记，计算出头部和尾部的值 */
#define PACK(size,alloc) ((size)|(alloc))   

#define GET(p)  (*(unsigned int *)(p))   // 得到这块地址的值
#define PUT(p, val) (*(unsigned int *)(p) = (val))   // 把值放到指定地址去

#define GET_SIZE(p) (GET(p) & ~0x7)    // 因为低3位用于标记该块是否被使用
#define GET_ALLOC(p) (GET(p) & 0x1)   // 取得该块的标记位

#define HDRP(bp) ((char *)(bp) - WSIZE)  // 取得该块的头部
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)  // 取得该块的尾部

/* 得到前一个块和后一个块 */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

参考：动态内存分配

Heap的初始化

这个简易的分配器是基于mmlib提供的存储器模型，它提供了以下2个Heap管理接口：

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
#define MAX_HEAP (1<<20)
...
static char * mem_heap;         // 指向堆的第一个字节
static char * mem_brk;          // 指向堆的最后一个字节，当需要重新扩充堆时，需要调整这个指针。
static char * mem_max_addr;     // 堆的最大地址加1
...
/*
 * 这里是利用malloc分配一个大的堆空间，在此基础上，
 * 进行的动态内存分配器的模拟。在Linux中，sbrk系统调用，
 * 可以直接操作堆空间，改变brk指针的位置。
 */
void mem_init(void) {
  mem_heap = (char *)malloc(MAX_HEAP);   // 先开辟一个大的堆空间
  mem_brk = (char *)mem_heap;
  mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}

void * mem_sbrk(int incr) {
  char * old_brk = mem_brk;

  if( ( incr < 0 ) || ( (mem_brk + incr) > mem_max_addr ) )
  {
    errno = ENOMEM;
    fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memeory..\n");
    return (void *)-1;
  }
  mem_brk += incr;
  return (void *)old_brk;
}

分配器的简易实现

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4             // word length
#define DSIZE 8            // double word length
#define CHUNKSIZE (1<<12)        // 4 K

#define MAX(x, y) ( (x)>(y) ? (x):(y) )
/* caculate the header and footer by the size and allocated bit */
#define PACK(size,alloc) ((size)|(alloc))   

#define GET(p)  (*(unsigned int *)(p))   // get a value of a address
#define PUT(p, val) (*(unsigned int *)(p) = (val))

#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)   // get the allocated bit

#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* get the next block and prev block */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

static char * heap_listp;
/* when allocated space again, we should search from this address */
static char * first_search;  

/* we should merge these idle blocks */
static void *coalesce( void * bp )
{
	size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
	size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
	size_t size = GET_SIZE(HDRP(bp));

	if( prev_alloc && next_alloc ) return bp;

	else if( prev_alloc && ! next_alloc )  // merge with next block
	{
		size += GET_SIZE(HDRP(NEXT_BLKP(bp)));

		PUT(HDRP(bp), PACK(size, 0));
		PUT(FTRP(bp), PACK(size, 0));
	}
	else if( ! prev_alloc && next_alloc ) // merge with prev block
	{
		size += GET_SIZE(HDRP(PREV_BLKP(bp)));

		PUT(FTRP(bp), PACK(size, 0));
		PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));

		bp = PREV_BLKP(bp);
	}
	else  // merge with prev block and next block
	{
		size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
			GET_SIZE(FTRP(NEXT_BLKP(bp)));

		PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
		PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));

		return PREV_BLKP(bp);
	}

	return bp;
}

static void *extend_heap(size_t words)
{
	char * bp;
	size_t size;

	size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;

	if( (long)(bp = mem_sbrk(size)) == -1 ) return NULL;

	PUT( HDRP(bp), PACK(size, 0) );
	PUT( FTRP(bp), PACK(size, 0) );
	PUT( HDRP(NEXT_BLKP(bp)), PACK(0, 1) );

	return coalesce(bp);   // merge these spared block
}

int mm_init(void)
{
	mem_init();

	if(( heap_listp = mem_sbrk(4 * WSIZE) ) == (void *)-1 )
	{
		return -1;
	}

	PUT( heap_listp, 0 );
	PUT( heap_listp + (1*WSIZE), PACK(DSIZE, 1));  
	PUT( heap_listp + (2*WSIZE), PACK(DSIZE, 1));
	PUT( heap_listp + (3*WSIZE), PACK(0, 1));

	heap_listp += (2 * WSIZE);

	if( extend_heap(CHUNKSIZE/WSIZE) == NULL ) return -1;

	first_search = heap_listp;

	return 0;
}

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 * Always allocate a block whose size is a multiple of the alignment.
 */
static void *find_fit( size_t size )
{
	void *bp;

	for( bp = first_search; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp) )
	{
		if( ! GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp))))
		{
			first_search = bp;
			return bp;
		}
	}
	/* if not find, we need search from the head... */
	for( bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp) )
	{
		if( ! GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp))))
		{
			first_search = bp;
			return bp;
		}
	}

	return NULL;
}

static void place( void *bp, size_t asize )
{
	size_t csize = GET_SIZE(HDRP(bp));

	if( (csize - asize) >= (2*DSIZE) )
	{
		PUT(HDRP(bp), PACK(asize, 1));
		PUT(FTRP(bp), PACK(asize, 1));
		bp = NEXT_BLKP(bp);
		PUT(HDRP(bp), PACK(csize-asize, 0));
		PUT(FTRP(bp), PACK(csize-asize, 0));
	}
	else
	{
		PUT(HDRP(bp), PACK(csize, 1));
		PUT(FTRP(bp), PACK(csize, 1));
	}
}

void *mm_malloc(size_t size)
{
	size_t asize;
	size_t extendsize;
	char *bp;

	if( size == 0 ) return NULL;

	if( size <= DSIZE ) asize = 2*DSIZE;
	else asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);

	if( (bp = find_fit(asize)) != NULL )
	{
		place(bp, asize);
		return bp;
	}
	/* not find, Get more memory */
	extendsize = MAX(asize, CHUNKSIZE);

	if( (bp = extend_heap(extendsize/WSIZE)) == NULL ) return NULL;

	place(bp, asize);

	return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
	size_t size = GET_SIZE(HDRP(ptr));

	PUT(HDRP(ptr), PACK(size, 0));
	PUT(FTRP(ptr), PACK(size, 0));

	coalesce(ptr);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
	if( ptr == NULL ) return mm_malloc( size );

	if( size == 0 )
	{
		mm_free( ptr );
		return NULL;
	}

	void * old_ptr = ptr;
	void * new_ptr;

	new_ptr = mm_malloc( size );
	memcpy( new_ptr, old_ptr, size );
	mm_free( old_ptr );

	return new_ptr;

}

性能测试

这个分配策略是根据<<深入理解计算机系统>>这本书写的，主要的不同点在于，我把书上的首次适配策略，换成了下一次适配策略。通过老师给的测试程序，结果显示下一次适配策略在本次实验中会取得更好的空间利用率和吞吐率的性能。

性能测试

总结

以前学习操作系统的时候，只从概念上了解了栈的分配与回收，如今自己动手写了一下，对堆的结构有了更深刻的认识.总体来说:受益匪浅。

在实现堆空间块的标记和合并时，我懂得了学会使用某些标记位来代替一些复合数据结构如链表，达到像链表那样的功能。这样不仅节约了空间，而且非常高效。在这里向提出这种标记方法的大牛致敬_。