Malloc in C

原文地址: http://web.eecs.utk.edu/~plank/plank/classes/cs360/360/notes/Malloc1/lecture.html

原文作者: Jim Plank

译文作者: 顾伟刚

译者注:一直想找时间好好理一下C语言中malloc的使用方法及其原理,它是如此的重要以至于影响到程序的方方面面。现在终于有机会了,我将借助这个讲义来记录和分享 malloc()

在尝试使用本文提到的代码之前请先看讲义。不幸的是,实验室机器上的 malloc()free() 的实现百分之百和本讲义中的不一样。因为这些讲义是在20世纪90年代中期编写的,而 malloc 的实现几乎每几年都要变化一次。

而我坚持使用本讲义来教学是因为它足够清晰。如果想知道它和现在机器实现的联系和区别,请猛击 http://web.eecs.utk.edu/~plank/plank/classes/cs360/360/notes/Malloc1/diff.html


这是一篇关于 sbrk()malloc() 的讲义。

上一节课我们学习了操作系统内存的通用知识 -- 我们了解到代码段的尾地址是 &etext ,全局段的尾地址是 &edata 。随着程序的运行,堆内存会不断地增长,因为代码使用 malloc() 从堆中分配内存。为了解决堆内存局限的问题,我们必须使用 brk()sbrk() 。它们都是系统调用,我们可以通过UNIX的man手册了解它们。这里我们仅讨论 sbrk() ,因为你只需要跟它打交道就行了。

caddr_t sbrk(int incr);

caddr_t 是一个“C地址指针”。它等同于 (char *) 或者 (void *)

这个操作指定操作系统给当前堆多分配 incr 字节内存。它返回调用 sbrk() 之前的堆内存尾地址。因此,调用 sbrk() 之后堆内存新的尾地址是:

sbrk(incr) + incr;

如果你调用 sbrk(0) ,它会返回当前堆内存的尾地址给你。

现在, malloc() ( 包括相应的 realloc()calloc() )都是通过调用 sbrk() 获取堆内存空间的。它们只是 sbrk() 的习惯用法。因此,可以说,获取堆内存的唯一方法是通过调用 malloc()sbrk() 。但是你始终应该使用 malloc() ,因为它更高效。


让我们来试试,请看fb2.c:

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>

main()
{
  int *i1, *i2;

  printf("sbrk(0) before malloc(4): 0x%x\n", sbrk(0));
  i1 = (int *) malloc(4);
  printf("sbrk(0) after 'i1 = (int *) malloc(4)': 0x%x\n", sbrk(0));
  i2 = (int *) malloc(4);
  printf("sbrk(0) after 'i2 = (int *) malloc(4)': 0x%x\n", sbrk(0));
  printf("i1 = 0x%x, i2 = 0x%x\n", i1, i2);
}

这个示例打印出调用 malloc() 前后 sbrk(0) 的结果。下面是运行在 hydra3a 的结果:

UNIX> fb2
sbrk(0) before malloc(4): 0x21ab0
sbrk(0) after `i1 = (int *) malloc(4)': 0x23ab0
sbrk(0) after `i2 = (int *) malloc(4)': 0x23ab0
i1 = 0x21ac0, i2 = 0x21ad0
UNIX>

注意到, sbrk() 返回值在调用 malloc() 之后并没有发生变化。为什么会这样?因为 malloc() 会缓冲内存。当它调用 sbrk() 申请内存时,它会申请一块大内存 -- 如12K或8K,之后的 malloc() 会从缓冲区里面获取内存。换句话说,在分配完内存i1和i2之后,缓冲区中还剩一整块内存(从 0x0x21ad0 至 0x0x23ab0)供 malloc() 使用,在这之前它都无需再次调用 sbrk() ,在这个示例中缓冲区内大概还剩8160字节内存。因此,在示例 fb2a.c 中,当我们分配完i1和i2后,再申请大于8160字节( malloc(8164) )的内存时,我们期待看到发生 sbrk() 的调用以获取更多内存。事实的确如此:

UNIX> fb2a
sbrk(0) before malloc(4): 0x21b68
sbrk(0) after `i1 = (int *) malloc(4)': 0x23b68
sbrk(0) after `i2 = (int *) malloc(4)': 0x23b68
i1 = 0x21b78, i2 = 0x21b88, sbrk(0)-i2 = 8160
sbrk(0) after `i3 = (int *) malloc(8164)': 0x25b68
i3 = 0x21f78
UNIX>

现在来看fb3.c, 调用 malloc(4) 10次,并且打印出分配的内存地址:

#include <stdio.h>
#include <stdlib.h>

main()
{
  int j, *buf;

  for (j = 0; j < 10; j++) {
    buf = (int *) malloc(4);
    printf("malloc(4) returned 0x%x\n", buf);
  }
}

结果如下:

UNIX> fb3
malloc(4) returned 0x219d0
malloc(4) returned 0x219e0
malloc(4) returned 0x219f0
malloc(4) returned 0x21a00
malloc(4) returned 0x21a10
malloc(4) returned 0x21a20
malloc(4) returned 0x21a30
malloc(4) returned 0x21a40
malloc(4) returned 0x21a50
malloc(4) returned 0x21a60
UNIX>

观察上面的打印结果,你将会发现每次 malloc() 返回的地址相比之前一次调用都是是以 16 字节递增的。你可能会想为什么不是4字节呢,因为你只请求了4字节内存?这里发生了一些事情, malloc() 每次都会额外分配一些字节以帮助保存申请记录。这些额外的字节在你调用 free() 的时候将发挥重要的作用。这些额外的字节通常是在内存申请前分配的。这也是我们之后讨论 free() 的原因。

再看fb4.c,这个文件做的事情是:使用 malloc() 分配一整块内存,然后打印出他们的起始地址,以及这个起始地址之前的1个字和2个字(这里我使用“字”来代表4字节大小)。这是大部分程序员认为的“不安全”的代码,可是要弄清楚这些事情我们只能做了。你可以看到, malloc() 返回地址之前的2个字的空间存领了本次实际分配的内存大小。好像有点混乱了,我们来仔细看看 fb4 的输出:(不同的操作系统上, malloc 的工作方式不一样。如果你的输出跟我的不一样,请猛击 这里)。

#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>

main()
{
  int *buf;
  int i, sz;

  i = 1000;
  printf("sbrk(0) = 0x%x\n", sbrk(0));
  for (sz = 4; sz < 32; sz += 4) {
    buf = (int *) malloc(sz);
    buf[0] = i;
    i++;
  printf("Allocated %d bytes.  buf = 0x%x, buf[-1] = %d, buf[-2] = %d, buf[0] = %d\n", 
            sz, (unsigned int) buf, buf[-1], buf[-2], buf[0]);
  }

  sz = 100;
  buf = (int *) malloc(sz);
  buf[0] = i;
  i++;
  printf("Allocated %d bytes.  buf = 0x%x, buf[-1] = %d, buf[-2] = %d, buf[0] = %d\n", 
            sz, (unsigned int) buf, buf[-1], buf[-2], buf[0]);
  printf("sbrk(0) = 0x%x\n", sbrk(0));
}

其输出结果如下:

UNIX> fb4
sbrk(0) = 0x70f8
Allocated 4 bytes.  buf = 0x61a8, buf[-1] = 0, buf[-2] = 16, buf[0] = 1000
Allocated 8 bytes.  buf = 0x61b8, buf[-1] = 0, buf[-2] = 16, buf[0] = 1001
Allocated 12 bytes.  buf = 0x61c8, buf[-1] = 0, buf[-2] = 24, buf[0] = 1002
Allocated 16 bytes.  buf = 0x61e0, buf[-1] = 0, buf[-2] = 24, buf[0] = 1003
Allocated 20 bytes.  buf = 0x61f8, buf[-1] = 0, buf[-2] = 32, buf[0] = 1004
Allocated 24 bytes.  buf = 0x6218, buf[-1] = 0, buf[-2] = 32, buf[0] = 1005
Allocated 28 bytes.  buf = 0x6238, buf[-1] = 0, buf[-2] = 40, buf[0] = 1006
Allocated 100 bytes.  buf = 0x6260, buf[-1] = 0, buf[-2] = 112, buf[0] = 1007
sbrk(0) = 0x70f8
UNIX>

现在我们看一下调用 malloc() 之后堆的状况,注意,这里 buf**[0**] 的内容被设置为 i = 1000:

|---------------|  
|      ...      | 
|               |      
|      16       | 0x61a0
|               | 0x61a4     
|     1000      | 0x61a8  <--------- return value
|               | 0x61ac
|               | 0x61b0
|               | 0x61b4
|      ...      |      
|               |      
|               |      
|               |      
|---------------| 0x70f8 (sbrk(0));

在第二次调用 malloc() 时( buf = malloc(8) ), malloc() 返回 0x61b8buf**[0**] 的内容被设置为 i = 1001,这时候堆的状况如下:

|---------------|  
|      ...      | 
|               |      
|      16       | 0x61a0

|               | 0x61a4     
|     1000      | 0x61a8  
|               | 0x61ac
|      16       | 0x61b0
|               | 0x61b4
|     1001      | 0x61b8  <--------- return value
|               | 0x61bc
|               | 0x61c0
|               | 0x61c4
|      ...      |      
|               |      
|               |      
|---------------| 0x70f8 (sbrk(0));

如此往复 -- 当最后调用 sbrk(0) 的时候,堆的状况如下:

|---------------| 

|      ...      |
|               | 
|      16       | 0x61a0
|               | 0x61a4
|     1000      | 0x61a8
|               | 0x61ac
|      16       | 0x61b0
|               | 0x61b4
|     1001      | 0x61b8 
|               | 0x61bc
|      24       | 0x61c0
|               | 0x61c4
|     1002      | 0x61c8 
|               | 0x61cc
|               | 0x61d0
|               | 0x61d4
|      24       | 0x61d8 
|               | 0x61dc
|     1003      | 0x61e0
|               | 0x61e4
|               | 0x61e8 
|               | 0x61ec
|      32       | 0x61f0
|               | 0x61f4
|     1004      | 0x61f8 
|               | 0x61fc
|               | 0x6200
|               | 0x6204
|               | 0x6208 
|               | 0x620c
|      32       | 0x6210
|               | 0x6214
|     1005      | 0x6218 
|               | 0x621c
|               | 0x6220
|               | 0x6224
|               | 0x6228 
|               | 0x622c
|      40       | 0x6230
|               | 0x6234
|     1006      | 0x6238 
|               | 0x623c
|               | 0x6240
|               | 0x6244
|               | 0x6248 
|               | 0x624c
|               | 0x6250
|               | 0x6254
|     112       | 0x6258 
|               | 0x625c
|     1007      | 0x6260
|               | 0x6264
|      ...      |
|               |
|               |
|---------------| 0x70f8 (sbrk(0));

可以看出, malloc() 通过调用 sbrk() 从操作系统获取内存到缓冲区,当 malloc() 再次被调用时从缓冲区中获取。当缓冲区的内存用尽之后,它再次调用 sbrk() 从操作系统获取更多内存。

那为什么 malloc(4)malloc(8) 分配16字节空间,而 malloc(12)malloc(16) 分配24字节呢?这是因为 malloc() 会扩展分配的内存大小为8的整数倍。因此 malloc(4)malloc(8) 会为你分配8字节内存,另外再申请额外的8字节用以记录。 malloc(12)malloc(16) 会分配16字节空间,加上额外的8字节用以记录。 malloc(100) 会为你分配104字节内存,加上额外的8字节用以记录。

为什么 malloc() 为执行内存扩展呢?这么做之后, malloc() 返回的地址一定会是8的整数倍,因此对于任何类型的指针来说都是合法的。假如 malloc() 不这么做,而是可以返回任何地址的指针,下面的代码就会出现问题:

int *i;

i = (int *) malloc(4);
*i = 4;

这可能会产生一个总线错误,因为 malloc() 可以返回任何非4的整数倍地址给你。而事实是 malloc() 返回的地址是8的整数倍,因此对于浮点和长整型(8字节长度)来说也不会有总线问题。

malloc() 如何知道从哪里获取内存呢?它使用一个或两个全局变量来标识。例如:它可能会有如下两个全局变量:

char *malloc_begin = NULL;
char *malloc_end = NULL;

malloc() 被调用时,它首先检验 malloc_begin == NULL 是否成立?如果成立,它会调用 sbrk() 获取一个内存缓冲区。并且使用 malloc_beginmalloc_end 标明这个缓冲区的开始和结尾。当 malloc() 被调用时,它会从缓冲区的开始分配内存,并且更新 malloc_begin 的值。如果缓冲区中内存不足,那么它会转而调用 sbrk() 向系统申请更多内存,并且会更新 malloc_end 的值以扩展缓冲区。

到目前为止,我们描述了如何编写无需内存回收( free() )的 malloc() 函数。当 free() 被调用时,你必须保证它释放的内存能被 malloc 再次使用。也就是说你要在 malloc() 中做一些更复杂的事情,我们会在接下来继续讨论,大家先自己思考一下吧!


重申一下,如果你还没有阅读对比 malloc() 不同实现的 这篇文章 ,你应该现在就读一下。