随笔 - 119  文章 - 290  trackbacks - 0

博客搬家了哦,请移步
叫我abc

常用链接

留言簿(12)

随笔分类

我的博客

搜索

  •  

积分与排名

  • 积分 - 301935
  • 排名 - 84

最新评论

阅读排行榜

终于可以看看这个gc库是如何收集垃圾内存的了。还是老方法,先贴代码,来一个直观上的认识

 1void
 2gc_collect()
 3{
 4    int i;
 5    stack_pack();
 6    cache_flush();
 7    gc_mark(0);
 8    for (i=0;i<E.size;i++{}
 9    E.mark+=2;
10}
首先是stack_pack,这将是要研究的第一个子函数。根据其名字,可以推测会操作前面看过的管理自由内存的堆栈,事实上也是如此。该函数将清理堆栈,将暂时不能释放的自由内存用一种自动化的方式标记出来,这种方式就是为他们建立依赖关系。建立依赖关系也是内存不能被当作垃圾的唯一理由。
下一步是cache_flush,这个以前已经看过,将cache的依赖关系写入到实际管理的容器上。
第三步是gc_mark,用来给所有有依赖关系的内存做一下标记,证明他们不是垃圾。
第四步是一个for循环,循环体太长暂时先不贴出来,不过其工作就是将标记不合格的内存释放,因为他们是垃圾内存。
最后更新标记,标记是一个递增的整数。

垃圾收集的过程直观上就是这样,现在就来逐步细看,先看看stack_pack。声明一点,通过这个函数,可以解开之前在gc_leave中为何会有E.bottom大于 E.current的缘故(除了初始化)。
1static void
2stack_pack()
3{
4    int bottom=stack_pack_internal(E.stack.bottom,E.stack.current,E.stack.top);
5    E.stack.top=E.stack.bottom=bottom;
6    E.stack.current=bottom-1;
7}
stack_pack的代码很少,因此可以断定关键的地方都在stack_pack_internal上了,其返回值bottom也有重要意义。
第5、6行,直接将top,bottom,current指针重置到一个类似于初始化的状态,不过此时的bottom通常都已经往上移动了,而current小于bottom。
也就是说,每次调用gc_collect后,总会造成current小于bottom的结果,那么gc_leave的实现里有对这种判断的处理也就不奇怪了,不过具体这种处理是何用意,看了stack_pack_internal之后再说。

 1static int
 2stack_pack_internal(int from,int to,int top)
 3{
 4    if (to < from) {
 5        int parent = E.stack.data[to].stack;
 6        while (from < top) {
 7            node_add(parent,E.stack.data[from].handle);
 8            ++from;
 9        }

10        return to+1;
11    }

12    else {
13        int bottom=stack_pack_internal(from,to-E.stack.data[to].number,to);
14        int node=node_alloc(0);
15        ++to;
16        while (to<top) {
17            node_add(node,E.stack.data[to].handle);
18            ++to;
19        }

20        node_add(E.stack.data[bottom-1].stack,node);
21        E.stack.data[bottom].stack=node;
22        return bottom+1;
23    }

24}

快速扫一眼stack_pack_internal,发现他是一个递归函数,其次确认一下三个参数,分别对应bottom,current,top,也就是当前函数下的堆栈指针位置。
第4行的代码可以看成 if ( current < bottom ),通过以前看过的代码,可以了解到以下3点:
1.初始化之后,current < bottom
2.调用gc_collect之后,current < bottom
3.调用了gc_enter后,current 绝对不会小于bottom
因此else部分的代码才是要先考虑的代码,也就是递归的部分。

第13行的代码可以写成
bottom = stack_pack_internal( bottom , current - E.stack.data[ current ].number , current )
有看出什么来吗?比如说从number,或者是从这个减法。没错哟,这三个用于递归的参数,其实是在父函数环境下的堆栈指针位置。也就是说,stack_pack_internal递归的调用,由于执行常规的else部分的代码,因此不断的传递父函数的堆栈指针位置,不断的寻根,不断的追宗认祖,最终就会回到stack刚初始化的状态,此时 current < bottom。很酷的,现在不得不暂时放下else部分,来看看if部分,这if部分可就只是为了这么一下而准备的。
第5行,取的是current节点处的值。刚初始化的stack,这里存放着全局内存之根,最大的所有者。
接下来,由于此时bottom 等于 top,所以while循环暂不执行,直接返回bottom。现在可以回到else部分了。

第14行,从 E.pool中分配了一个节点,当然该节点实际没有维护任何内存,不过这个节点可有大用处。
第16到第19行,这个while循环内,将某一级函数(递归太多,是哪一级已经不重要了)中分配出来的自由内存和刚申请的node建立依赖关系,这级函数的自由内存id可都记录在current+1到top之间的handler中呢(current记录父函数分配的自由内存数量)。
第20行,将刚申请node和 E.stack.data[ bottom -1 ].stack建立以来关系,不过这到底是什么呢?如果bottom-1等于0的话,那就是node和全局建立依赖关系,否则,看起来就像是和父函数建立了依赖关系。第21行验证了这个想法,这一赋值,将node记录到了堆栈中。就此也知道了stack成员变量的作用,表示某个函数的节点。
最后返回bottom+1,即bottom指针移动了,而bottom-1必然指向了代表父函数的node。

以上的分析看其来都比较混乱,不过从整体想像的话:
假设函数其实是一种对象,他引用着那些在他函数体内分配出来的自由内存,因此他和那些内存就有依赖关系。从最上层的函数开始,建立表示该函数对象的节点,和所有在这一级函数中分配的自由内存建立依赖关系。然后到下一级子函数,也建立一个表示该函数对象的节点,和所有在这一级函数中分配的自由内存建立依赖关系。如此递归,直到调用了gc_collect的这一级函数为止。
管理自由内存的堆栈,经过这样处理后,里面就剩下了每一级函数对象的节点id,一个个的紧挨着。而作为到调用gc_collect为止,这一路下来分配的自由内存,都是暂时不能释放的,已经建立依赖关系放进了 E.cache。

根据stack_pack后两行的代码,就可以判断出if代码中while循环是用来干什么吃的了:同一级函数中,在gc_collect后,继续分配自由内存,然后再gc_collect的话,就会执行到该while循环,本质也是用来建立依赖关系的。


最后说说看gc_leave时无法理解的代码吧,现在已是真相大白了
 1    else {
 2        int parent,child;
 3        --E.stack.bottom;
 4        parent=E.stack.data[E.stack.bottom-1].stack;
 5        child=E.stack.data[E.stack.bottom].stack;
 6        node_add(parent, child | UNSET_MASK);
 7        node_free(child);
 8        E.stack.current=E.stack.bottom-1;
 9        E.stack.top = E.stack.current + 1;
10    }
这是current小于bottom的情形,已经被gc_collect了,此时 E.stack.data[0]到 bottom指针之间应该都是每一级函数的象征节点。
第4、5行,就是一个父函数和子函数的关系,现在既然已经从子函数中退出了,那么也是时候解放子函数中分配的自由内存的时候了,因此第6行解开了父子函数的依赖关系,那子函数中分配的自由内存也相应的变成垃圾了。
最后两行恢复父函数的堆栈,我想堆栈的形状也差不多了,E.stack.data[0]到 bottom指针之间应该都是每一级函数的象征节点。
posted on 2008-09-21 23:17 LOGOS 阅读(1673) 评论(3)  编辑 收藏 引用

FeedBack:
# re: 垃圾收集的那点事(I) 2008-09-22 11:38 来支持
天天来支持下。
博主有没有看过一个autofreealloc的玩意?  回复  更多评论
  
# re: 垃圾收集的那点事(I) 2008-09-22 14:11 LOGOS
@来支持
没听说过,搜索了一下,不知道你说的是不是这个
http://blog.csdn.net/xushiweizh/archive/2006/11/19/1396573.aspx

这个autofreealloc的责任很明确-----理解该垃圾回收器的关键点在于,是在于理解它的目标:为一个复杂的局部过程(算法)提供自动内存回收的能力。
所以从各种意义上他都比yfgc简单得多  回复  更多评论
  
# re: 垃圾收集的那点事(I) 2008-09-22 22:40 来支持
是的。
许这个所谓半自动GC花了一些时间研究过他的实现,感觉应用面比较小,而且只适合单线程环境。争议也比较大

个人对C/C++下轻量GC实现非常敢兴趣,云风这个还没时间深入去看,现在甚至还不知道它能做什么,不能做什么,在什么环境下适用,什么环境下不适用。

提个建议,博主你能不能对云风这个GC写一个综述性和应用实例的文章,然后再去探讨内部的实现机理。单纯的代码分析好像C++博客的弟兄们都不怎么感冒,这么好的东西都没人关注。呵呵。



  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理