给c实现一个垃圾回收器有多大难度?

koolcoy

大家说说看, 我对计算机组成原理了解不多, c是编译运行的, 我想这个难度应该相当大吧.

我不懂, 大家说说看.

当然我不是指能自动回收malloc分配出去的内存, 对于编译执行的语言这个几乎无法实现. 能不能定义自己的malloc, 使得内存在不被使用时能够自动回收.

ypxing

当然不是了，编译执行的也可以实现的
一个最简单的办法就是
当malloc不能再分配的时候,执行下面两遍扫描：
第一遍扫描程序中所有的指针，看看他们指向堆中的那些部分，并记录下来
第二遍扫描堆，将那些没有被指针指向的内存释放掉

原帖由 koolcoy 于 2007-6-24 00:06 发表
大家说说看, 我对计算机组成原理了解不多, c是编译运行的, 我想这个难度应该相当大吧.

我不懂, 大家说说看.

当然我不是指能自动回收malloc分配出去的内存, 对于编译执行的语言这个几乎无法实现. 能不能定义 ...

MMMIX

原帖由 koolcoy 于 2007-6-24 00:06 发表
大家说说看, 我对计算机组成原理了解不多, c是编译运行的, 我想这个难度应该相当大吧.

我不懂, 大家说说看.

当然我不是指能自动回收malloc分配出去的内存, 对于编译执行的语言这个几乎无法实现. 能不能定义 ...

建议楼主搜些垃圾回收方面的资料先看看。

koolcoy

原帖由 ypxing 于 2007-6-24 00:18 发表
当然不是了，编译执行的也可以实现的
一个最简单的办法就是
当malloc不能再分配的时候,执行下面两遍扫描：
第一遍扫描程序中所有的指针，看看他们指向堆中的那些部分，并记录下来
第二遍扫描堆，将那些没有被 ...

我看事情远不是这么简单的, 在c中你可以把整数转换成指针, 指针也就是整数, 也就是说你根本就不知道哪些是指针哪些是整数. 所以你不可能把所有的指针都扫描一遍.

我认为这个问题才是c中垃圾回收最大的问题, 除非你自己定义一种新的指针的表示方式, 至于回收算法什么的一搜一大把.

[ 本帖最后由 koolcoy 于 2007-6-24 08:33 编辑 ]

ypxing

你可以对所有的指针变量进行追踪

“把整数转换成指针, 指针也就是整数”

即使允许你“整数转换成指针",这种不是malloc生成的地址，你还要管吗？

原帖由 koolcoy 于 2007-6-24 08:22 发表

我看事情远不是这么简单的, 在c中你可以把整数转换成指针, 指针也就是整数, 也就是说你根本就不知道哪些是指针哪些是整数. 所以你不可能把所有的指针都扫描一遍.

我认为这个问题才是c中垃圾回收最大的问题,  ...

[ 本帖最后由 ypxing 于 2007-6-24 21:03 编辑 ]

koolcoy

原帖由 ypxing 于 2007-6-24 08:50 发表
建议你好好想想
你可以对所有的指针变量进行追踪

“把整数转换成指针, 指针也就是整数”

即使允许你“整数转换成指针",这种不是malloc生成的地址，你还要管吗？

当然要管了:

1. 
   
2. char* p;
   
3. p = malloc(1);
   
4. int i = (int)p;
   
5. int b = i;
   
6. int* c = (int*)b;
   

复制代码

上面代码中的c你管还是不管? 如果要管的话你怎么去追踪它? b该不该管呢? 如果后面还有一个return b; 又该怎么管呢?

[ 本帖最后由 koolcoy 于 2007-6-24 16:20 编辑 ]

ypxing

原帖由 koolcoy 于 2007-6-24 16:12 发表

当然要管了:

1. 
   
2. char* p;
   
3. p = malloc(1);
   
4. int i = (int)p;
   
5. int b = i;
   
6. int* c = (int*)b;
   

复制代码

上面代码中的c你管还是不管? 如果要管的话你怎么去追踪它?

”第一遍扫描程序中所有的指针，看看他们指向堆中的那些部分，并记录下来“
这样c就会被记录下来，发现它是指向堆中的一块内存的，那么这块内存不能释放

并不需要追踪这些指针的传递过程
哪些是指针类型(比如你说的c)的你总知道吧，呵呵

[ 本帖最后由 ypxing 于 2007-6-24 21:03 编辑 ]

cobras

给点提示，实现很简单

#include <stdlib.h>

#ifndef NDEBUG
#define malloc  f_automem_malloc
#define free     f_automem_free
#endif

struct s_memblock {
    struct s_memblock *prev, *next;
};

struct s_memblock *v_memblocks;

static int v_initial = 0;

static void f_automem_exit(void) {
    /* check v_memblocks for leak memblock */
    /* free them and send warning message */
}

static void f_automem_init(void) {
    if (!v_initial) {
         atexit(f_automem_exit);
         v_initial = 1;
    }
}

void *f_automem_malloc(size_t size) {
     f_automem_init();
    /* allocate a new memblock */
   /* and link it to the link table */
}

void f_automem_free(void *memblock) {
    /* unlink the memblock from link table */
    /* free the memblock */
}

mingyanguo

原帖由 ypxing 于 2007-6-24 16:21 发表


都给你说了
”第一遍扫描程序中所有的指针，看看他们指向堆中的那些部分，并记录下来“
这样c就会被记录下来，发现它是指向堆中的一块内存的，那么这块内存不能释放

并不需要追踪这些指针的传递过程
哪 ...

还有个疑问

1. 
   
2. long int a;
   
3. void* ap;
   
4. 
   
5. ap = malloc(1);
   
6. a = (long int)ap;
   
7. ap = malloc(1);
   

复制代码

这种情况怎么处理？

ypxing

原帖由 mingyanguo 于 2007-6-24 19:24 发表

还有个疑问

1. 
   
2. long int a;
   
3. void* ap;
   
4. 
   
5. ap = malloc(1);
   
6. a = (long int)ap;
   
7. ap = malloc(1);
   

复制代码

这种情况怎么处理？

假设第一次malloc的内存为A，第二次malloc的内存为B
经过第一遍扫描，发现有一个指针ap指向内存B，但是没有指针指向内存A(通过a你是无法访问A的)
第二遍扫描堆的时候，将A释放，B保留