C语言动态内存分配：（一）malloc/free的实现及malloc实际分配/释放的内存_c语言 malloc free

一、malloc/free概述

malloc是在C语言中用于在程序运行时在堆中进行动态内存分配的库函数。free是进行内存释放的库函数。

1、函数原型

#include <stdlib.h>



 



void *malloc( 



   size_t size 



);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void free( 



   void* memblock 



);
1
2
3
4
5
6
7
8
9

2、返回值

成功时，返回所分配存储空间的起始地址；返回值类型为void*,在C语言中可以把void*直接付给具体的类型，但是在C++中必须进行强制类型转换

失败时(内存不足时)返回NULL

size为0时，返回的指针不是NULL；但是除了free，别的地方不要使用这个指针。

3、使用示例

#include <stdlib.h>         /* For _MAX_PATH definition */



#include <stdio.h>



#include <malloc.h>



 



void main( void )



{



   char *string;



 



   /* Allocate space for a path name */



   string = malloc( _MAX_PATH );



 



   // In a C++ file, explicitly cast malloc's return.  For example, 



   // string = (char *)malloc( _MAX_PATH );



 



   if( string == NULL )



      printf( "Insufficient memory available\n" );



   else



   {



      printf( "Memory space allocated for path name\n" );



      free( string );



      printf( "Memory freed\n" );



   }



}
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

*二、malloc实际分配的内存大小*

malloc实际分配的内存会大于我们需要的size。主要由两方面因素决定：

1、字节对齐。会对齐到机器最受限的类型（具体的实现因机器而异）。

2、“块头部信息”。每个空闲块都有“头部”控制信息，其中包含一个指向链表中下一个块的指针、当前块的大小和一个指向本身的指针。为了简化块对齐，所有块的大小都必须是头部大小的整数倍，且头部已正确对齐。

在VC平台下由_CrtMemBlockHeader结构体实现。

以下为《C程序设计语言》中给出的通过union进行的头部实现，其中假定机器的受限类型为long。

typedef long Align;/*按照long类型的边界对齐*/



union header/*块的头部*/



{



	struct



	{



		union header *ptr;/*空闲块链表中的下一块*/



		unsigned size;/*本块的大小*/



	}s;



	Align x;/*强制块对齐*/



};
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

说明：
（1）实际分配的内存块将多一个单元，用于头部本身。实际分配的块的大小被记录在头部的size字段中。

（2）size字段是必须的，因为malloc函数控制的块不一定是连续的，这样就不能通过指针算术运算计算其大小。

（3）malloc返回的是空闲块的首地址，而不是首地址。

三、malloc/free实现过程

1、空闲存储空间以空闲链表的方式组织（地址递增），每个块包含一个长度、一个指向下一块的指针以及一个指向自身存储空间的指针。（ 因为程序中的某些地方可能不通过malloc调用申请，因此malloc管理的空间不一定连续。）

2、当有申请请求时，malloc会扫描空闲链表，直到找到一个足够大的块为止（首次适应）(因此每次调用malloc时并不是花费了完全相同的时间）。

3、如果该块恰好与请求的大小相符，则将其从链表中移走并返回给用户。如果该块太大，则将其分为两部分，尾部的部分分给用户，剩下的部分留在空闲链表中（更改头部信息）。因此malloc分配的是一块连续的内存。

4、释放时，首先搜索空闲链表，找到可以插入被释放块的合适位置。如果与被释放块相邻的任一边是一个空闲块，则将这两个块合为一个更大的块，以减少内存碎片。

四、实现

以下为《C语言程序设计语言》中给出的一种实现方法

1、malloc的实现

typedef union header Header;



static Header base;/*从空链表开始*/



static Header *freep = NULL;/*空闲链表的初始指针*/



 



void *malloc(unsigned nbytes)



{



	Header *p, *prevp;



	Header *morecore(unsigned);



	unsigned nunits;



 



	nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;



	if((prevp = freep) == NULL) /* 没有空闲链表 */



	{ 



		base.s.ptr = freep = prevp = &base;



		base.s.size = 0;



	}



	for(p = prevp->s.ptr; ;prevp = p, p= p->s.ptr) 



	{



		if(p->s.size >= nunits) /* 足够大 */



		{ 



			if (p->s.size == nunits)  /* 正好 */



				prevp->s.ptr = p->s.ptr;



			else  /*分配末尾部分*/



			{                 



				p->s.size -= nunits;



				p += p->s.size;



				p->s.size = nunits;



			}



			freep = prevp;



			return (void*)(p+1);



		}



		if (p== freep) /* 闭环的空闲链表*/



			if ((p = morecore(nunits)) == NULL)



				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
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

说明：

（1）malloc实际分配的空间是Header大小的整数倍，并且多出一个Header空间用于放置Header

（2）式nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1中的减1是为了防止(nbytes+sizeof(Header))%sizeof(Header) == 0时，多分配了一个Header大小的空间

（3）第一次调用malloc函数时，freep为NULL，系统将创建一个退化的空闲链表，它只包含一个大小为0的块，且该块指向自己。任何时候，当请求空闲空间时，都将搜索空闲块链表。搜索从上一次找到空闲块的地方（freep）开始。该策略可以保证链表是均匀的。如果找到的块太大，则将其尾部返回给用户，这样，初始块的头部只需要修改size字段即可。

（4）任何时候，返回给用户的指针都指向块内的空闲存储空间，即比指向头部的指针大一个单元。

（5）sbrk不是系统调用，是C库函数。sbrk/brk是从堆中分配空间，本质是移动一个位置，向后移就是分配空间，向前移就是释放空间，sbrk用相对的整数值确定位置，如果这个整数是正数，会从当前位置向后移若干字节，如果为负数就向前若干字节。在任何情况下，返回值永远是移动之前的位置。在LINUX中sbrk(0)能返回比较精确的虚拟内存使用情况。链接：sbrk()/brk()–改变数据长度

（6）链接:brk()分配过程

2、morecore的实现

函数morecore用来向操作系统请求存储空间，其实现细节因系统的不同而不同。因为向系统请求存储空间是一个开销很大的操作，因此我们不希望每次调用malloc时都执行该操作，基于这个考虑，morecore函数请求至少NALLOC个单元。这个较大的块将根据需要分成较小的块。在设置完size字段后，morecore函数调用free函数把多余的存储空间插入到空闲区域中。

#define NALLOC 1024    /* 最小申请单元数 */



static Header *morecore(unsigned nu)



{



    char *cp;



    Header *up;



    if(nu < NALLOC)



        nu = NALLOC;



    cp = sbrk(nu * sizeof(Header));



    if(cp == (char *)-1)    /* 没有空间*/



        return NULL;



    up = (Header *)cp;



    up->s.size = nu;



    free((void *)(up+1));



    return freep;



}
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

说明：

（1）没有存储空间时sbrk调用返回-1.因此需要将-1强制类型转换为char*类型，以便 与返回值进行比较。而且，强制类型转换使得函数不会受不同机器中指针表示的不同的影响。

3、free的实现

free函数从freep指向的地址开始，逐个扫描空闲链表，寻找可以插入空闲块的地方。该位置可能在链表的末尾或者两个空闲块之间。在任何一种情况下，如果被释放的块与另一空闲块相邻，则将这两个块合并。

void free(void *ap)



{



	Header *bp,*p;



	bp = (Header *)ap -1; /* 指向块头 */



	for(p=freep;!(bp>p && bp< p->s.ptr);p=p->s.ptr)



		if(p>=p->s.ptr && (bp>p || bp<p->s.ptr))



			break;    /* 被释放的块在链表的开头或结尾*/



	if (bp+bp->s.size==p->s.ptr) /*与上一相邻块合并 */



	{    



		bp->s.size += p->s.ptr->s.size;



		bp->s.ptr = p->s.ptr->s.ptr;



	} 



	else



		bp->s.ptr = p->s.ptr;



	if (p+p->s.size == bp)/* 与下一相邻块合并 */ 



	{     



		p->s.size += bp->s.size;



		p->s.ptr = bp->s.ptr;



	} 



	else



		p->s.ptr = bp;



	freep = 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
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

五、注意事项

链接：malloc/free使用注意事项

参考文献：

1、《C程序设计语言》

2、《C和指针》

3、《C和C++安全编码》

4、链接：如何实现一个malloc