随笔 - 119  文章 - 290  trackbacks - 0

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

常用链接

留言簿(12)

随笔分类

我的博客

搜索

  •  

积分与排名

  • 积分 - 280140
  • 排名 - 78

最新评论

阅读排行榜

先说下背景,有同学看了我写的yfgc库的分析,留言问我能不能用c实现一个教学用gc库,力求简单,无需优化。这个月实在写不出blog,正好充数一篇。
相关连接: http://www.cppblog.com/darkdestiny/archive/2008/09.html

真正能用的gc库我不会写,简单表达问题本质的东西倒还能应付,就写了一下。不过只用c没有容器是不行的,用了stl,相信同学能看明白。
首先还是先说一下基本概念,gc本质就是把你分配出去的内存都记好了,俩俩内存之间的依赖关系都记好了。回收的时候查找依赖关系,将被根节点依赖的内存都标记为不可删除,删除没有被标记的内存即可。
说实话,gc对于c/cpp这种中级语言意义不大,因为你不得不手动修改两块内存之间的依赖关系,这和手动管理内存是没有差别的。你忘了解除依赖关系,等价于忘了释放内存。
gc这种东西,只对于能把指针变量进行特殊编译的编译器,或者基于虚拟机的语言有价值。我用c/cpp的话还是倾向于手动管理内存,不管依赖关系如何复杂,只要所有权内保证唯一就可单点手动释放;对于所有权不唯一的依赖关系,则采用引用计数机制。

话说太多了,贴点代码吧,也许改改就能编译过去。
#define ROOT (void*)NULL

void* gc_malloc(size_t s);
void gc_link(void* parent, void* child);
void gc_unlink(void* parent, void* child);
void gc_collect();


#include 
<map>
static std::multimap<void*,void*> s_links, s_linkClean;
static std::map<void*,int> s_allPtrs;
static int s_color = 0;


void* gc_malloc(size_t s)
{
    
void* ptr = ::malloc(s);
    s_allPtrs[ptr] 
= s_color;
    
return ptr;
}

void gc_link(void* parent, void* child)
{
    s_links.insert(std::make_pair(parent,child));
}

void gc_unlink(void* parent, void* child)
{
    s_links.erase(std::make_pair(parent, child));
}

void gc_collect()
{
    s_color 
= (s_color+1% 2;
    gc_mark_r(ROOT);
    s_links 
= s_linkClean;
    s_linkClean.clear();

    auto iter 
= s_allPtrs.begin();
    
while(iter!=s_allPtrs.end())
    {
        auto cur 
= iter++;
        
if(cur->second != s_color)
        {
            ::free(cur
->first);
            s_allPtrs.erase(cur);
        }
    }
}

void gc_mark_r(void* parent)
{
    
if(parent!=ROOT && s_allPtrs[parent]==s_color)
    {
        
return;
    }
    s_allPtrs[parent] 
= s_color;

    auto iter 
= s_links.lower_bound(parent);
    auto end 
= s_links.upper_bound(parent);
    
for(; iter!=end; ++iter)
    {
        s_linkClean.insert(iter);
        
void* child = iter->second;
        gc_mark_r(child);
    }
}

int main()
{
    
void* p1 = gc_malloc(10);
    gc_link(ROOT, p1);
    
void* p2 = gc_malloc(20);
    gc_link(p1, p2);
    gc_collect();
    
return 0;
}

yfgc库里的gc_enter/gc_leave是实现在gc_link/gc_unlink上的,算拓展api吧。同学完全可以自己实现的,hint是,为每个函数调用分配一点内存,建立父子函数内存上的依赖关系,函数里分配的临时内存和函数对应的内存也建立依赖关系,函数退出时解除相关的依赖关系。

云风不久前又给出一个基于继承的gc解决方案,很简单,可以看看:
http://blog.codingnow.com/2010/02/cpp_gc.html
posted on 2010-04-29 21:13 LOGOS 阅读(2599) 评论(6)  编辑 收藏 引用 所属分类: 垃圾收集

FeedBack:
# re: gc库概念简化版 2010-04-30 09:42 Kevin Lynx
- - 果然需要自己“改改才能编译过去”。。  回复  更多评论
  
# re: gc库概念简化版 2010-04-30 10:23 Kevin Lynx
每一次调用gc_collect的时候,s_color变为对立值(0->1, 1->0),然后gc_mark_r将位于s_links中的指针全部标记为当前的s_color值,那么在gc_collect之前gc_unlink的指针依然为原来的s_color,即未被标记,然后gc_collect回收这些未被标记的指针(指向的内存)。

不是很明白,s_linkClean在这里的作用。  回复  更多评论
  
# re: gc库概念简化版 2010-04-30 10:35 LOGOS
@Kevin Lynx
假设links中有这些值
root->a,a->b,b->c
当root->a被删除后,links的值为
a->b,b->c
结果a,b,c都被回收了,而这些链接关系都是无效的关系,需要清理
s_linkClean用于记录有效的链接关系  回复  更多评论
  
# re: gc库概念简化版[未登录] 2010-04-30 11:03 houapple
先谢谢LOGOS的回复,早上起来就看自己想看到的,心情那个愉悦啊!呵呵!
恩,刚刚把程序仔细看完,大概明白了程序的思想。
有两个问题:
1、如果我们不显式调用 gc_link 去维护依赖关系,如何去知道哪些内存需要回收?
2、因为大部分内存泄露都在被调用的函数中发生。如果我希望如下使用:
main()
{
gc_init();
foo();
gc_collect();
}
当然foo()中内存分配函数使用gc_malloc()。应该用什么机制去实现?  回复  更多评论
  
# re: gc库概念简化版 2010-04-30 11:56 LOGOS
@houapple
1.不调用gc_link,所有内存都会被回收
2.
foo()
{
gc_enter();
...
gc_leave();
}
gc_enter分配一个表示函数调用的内存p,修改gc_malloc,分配出c时默认和函数调用栈顶的内存建立依赖关系即可:gc_link(p,c)
gc_leave删除当前函数和上一个函数的依赖关系:gc_unlink(p-1, p)  回复  更多评论
  
# re: gc库概念简化版[未登录] 2010-04-30 14:22 houapple
第一点明白了,第二点考虑中!
谢谢 LOGOS  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理