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

mingyanguo

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


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

这种处理方式不是程序员预期的。之所以要用a记下A，那么很可能以后会用到。
可能接下来

1. 
   
2. int *bp
   
3. bp = (int *)a;
   
4. ....
   

复制代码

zx_wing

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


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

>>通过a你是无法访问A的
为什么不行？

ypxing想法很好，但这里有两个地方实现不了。
1.malloc失败的时候垃圾处理器工作。 在malloc失败之前，你的应用程序很可能就被内黑的oom killer杀掉了。
2.扫描内存，发现没有指针指向它。这个是无法做到的，给定一块内存，你是无法找到谁指向它的。

c是可以做垃圾处理器，但不是这么简单。CSAPP上给出了一个c实现垃圾处理器的例子——mark & sweep垃圾处理器。
小弟对这个没什么深入研究，不敢多说，有兴趣的朋友可以看。

ypxing

一个赖皮的办法就是，凡是类似于a = (long int)ap;中的这种a都先记录下来
准备回收内存的时候，除了看指针，还要查看这样先前
记录下来的a的值如果等于堆中已分配内存的地址，则不予释放

也就是说，被指针赋值的非指针变量也给他记录下来

谁也无法预知你以后怎么使用a
非得用一个整型去保存一个指针，而不用指针去保存指针
这就是问题的所在
这可能就是java不显示的使用指针重要原因之一

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

这种处理方式不是程序员预期的。之所以要用a记下A，那么很可能以后会用到。
可能接下来

1. 
   
2. int *bp
   
3. bp = (int *)a;
   
4. ....
   

复制代码

flw2

malloc怎么跟垃圾回收放在一起呢?
我不了解垃圾回收，但是大概方式是编译器确认你不会用到某个对象的时候它就知道可以回收了。内存不能让malloc控制，而是让编译器。否则感觉方向就错了，大家说呢
C改了就不C了，C相信程序员能做对。比如不会忘记必要的时候free malloc得到的内存。如果不放心，不是有有很多这方面的工具吗？

而且实现这个东东感觉比一个能跑的编译器还难吧。

ypxing

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

1.malloc失败的时候垃圾处理器工作。 在malloc失败之前，你的应用程序很可能就被内黑的oom killer杀掉了。
2.扫描内存，发现没有指针指向它。这个是无法做到的，给定一块内存，你是无法找到谁指向它的。

只是很从书上看来的想法而已，呵呵

你说的1。我不是很明白
2。的话，我的意思是说假定程序中有a1,....an共n个指针，然后堆中分配了m块内存
只查看这n个指针的值，看他们指向了哪些m中的块，m中没有被指向的则释放掉

ypxing

是的，大部分工作要在编译器上做
跟malloc没有直接的关系

原帖由 flw2 于 2007-6-24 20:11 发表
malloc怎么跟垃圾回收放在一起呢?
我不了解垃圾回收，但是大概方式是编译器确认你不会用到某个对象的时候它就知道可以回收了。内存不能让malloc控制，而是让编译器。否则感觉方向就错了，大家说呢
C改了就不C了 ...

mingyanguo

原帖由 ypxing 于 2007-6-24 20:09 发表
一个赖皮的办法就是，凡是类似于a = (long int)ap;中的这种a都先记录下来
准备回收内存的时候，除了看指针，还要查看这样先前
记录下来的a的值如果等于堆中已分配内存的地址，则不予释放

也就是说，被指针赋 ...

普通的赋值你可能还能跟踪，如果经过运算呢，这个跟踪就很复杂。
用int或者long来保存一个指针的一个很自然的想法是，这个指针是有一定的对齐要求的，
那么我可以用这个int的低几个bit来做其他的事情，当我需要这个指针的时候，我只需要
这个int的高几位就能还原这个指针。而且只要是c跟asm混用，那么指针与整数的转换几乎
不可避免，而且，现在不跟asm混用的c似乎非常的少见。

ypxing

有道理。

其实我提到的这个方法还是很简单粗浅
好的方法，大家还是去google一下吧

举个例子
如果用一个long某些位来保存一个地址的话，
比如偶数位来保存
然后在用一个方法读出来，再继续使用，
再或者对一个地址进行加密，使用的时候再解密
实在是不知道怎么判断那个地址

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

普通的赋值你可能还能跟踪，如果经过运算呢，这个跟踪就很复杂。
用int或者long来保存一个指针的一个很自然的想法是，这个指针是有一定的对齐要求的，
那么我可以用这个int的低几个bit来做其他的事情，当我需 ...

koolcoy

找到一个实现, 呵呵

我还没看它的代码, 估计是依靠大量的宏来实现的. 不过比起java的自动回收还是差远了.
http://www.hpl.hp.com/personal/Hans_Boehm/gc/

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

ypxing

去学习一下

原帖由 koolcoy 于 2007-6-24 23:05 发表
找到一个实现, 呵呵

我还没看它的代码, 估计是依靠大量的宏来实现的. 不过比起java的自动回收还是差远了.
http://www.hpl.hp.com/personal/Hans_Boehm/gc/