现在的位置: 首页 > 综合 > 正文

简易的c垃圾收集器 一个简易的c垃圾收集器

2017年09月30日 ⁄ 综合 ⁄ 共 11357字 ⁄ 字号 小 中 大 ⁄ 评论关闭

一个简易的c垃圾收集器

2010-05-09 21:47 262人阅读 评论(9) 收藏 举报

      这段时间试着实现了一个简易的C语言垃圾收集器，代码不多，但对我的经验而言，确实费了不少心思。
      这里感谢云风兄的开源：云风：blog.codingnow.com/2008/06/gc_for_c.html
      以及LOGOS兄的对yfgc的解析和实现的一个概念版本：LOGOS：www.cppblog.com/darkdestiny
      话说我知道自己的实现里面，有很多考虑不足的地方。但还是决定贴出来，讲述的我实现的思想，有不足的地方大家指出来也好纠正。
       大家知道垃圾收集技术主要分为以下几种，他们有各自的优点与缺点:
       1、引用技术（Reference Counting）
       2、标记清除（Mark-Sweep）
       3、标记整理/紧缩（Mark-Compact）
       4、结点复制（Copying）
       5、分代收集（Generational Collecting）
       这里我就不详述各种思想了，google上有。我的需求是：要求垃圾收集能自然的解决循环引用的问题，占用的空间不要太多，轻量级的实现，解决内存碎片的问题。
       这里我选用的是标记清除算法，内存分配使用内存池。
       首先还是给出内存池的接口，实现在我之前的文章中有讲，就不贴出来了。内存池的实现借鉴了sgi stl的实现思路。

Code:
  1. #ifndef _MEM_POOL_H   
  2. #define _MEM_POOL_H   
  3.   
  4. #include <stddef.h>   
  5.   
  6. void *mem_malloc(size_t n);
      
  7. void mem_free(void *p, size_t n);
      
  8. void *mem_realloc(void* ptr, size_t new_sz, size_t old_sz);
      
  9.   
  10. #endif   

    然后看gc的接口：

Code:
  1. #ifndef GARBAGE_COLLECTOR_H   
  2. #define GARBAGE_COLLECTOR_H   
  3.   
  4. #include <stddef.h>   
  5.   
  6. #define my_malloc mem_malloc   
  7. #define my_free mem_free   
  8. #define my_realloc mem_realloc   
  9.   
  10. /* define the level of node */  
  11. #define NODE_ROOT_LEVEL 0 /* the node is global
    variable or in main() */       
  12. #define NODE_NOW_LEVEL 1  /* the node is just use in  present fucntion */   
  13. #define NODE_PRE_LEVEL 2  /* the node is be referenced by call function */   
  14.   
  15.   
  16. void gc_init();
      
  17. void gc_exit();
      
  18.   
  19. void func_end(void *p, ...);
      
  20. void gc_link(void *p, int level);
      
  21.   
  22. /* gc will mark the memory in gc_enter/gc_leave for collect later */  
  23. void gc_enter();
      
  24. void gc_leave();
      
  25.   
  26. void gc_collect();
      
  27.   
  28. void *gc_malloc(size_t sz, void (*finalizer)(void *));
      
  29. void *gc_realloc(void *p, size_t sz);
      
  30.   
  31. #endif   

  用到的数据结构：

Code:
  1. struct node {
      
  2.     int mark;          /* mark for gc collect */  
  3.     int level;         /* the node leavel */  
  4.     struct {
      
  5.         void *mem;     /* the pointer point to memory*/  
  6.         int size;      /* the size of memrory */  
  7.         void (*finalizer)(void *); /* destruction when the mem be free */  
  8.     }n;
      
  9. };
      
  10.   
  11. static struct {
      
  12.     struct node *pool;   /* an array for store
    nodes */      
  13.     int size;            /* the size of pool */  
  14.     int free;            /* the next free node in pool */  
  15.     struct stack *stack; /* the stack used for store
    pointer in fuction */      
  16. } E;  

      这里 level 取值为：NODE_ROOT_LEVEL、NODE_NOW_LEVEL、NODE_PRE_LEVEL。 基于这样的考虑：我们知道动态分配一块内存，如果要延长其生命期，要么通过函数返回值传回，要么通过多级指针，或者直接挂到全局变量上。所以这个gc基于这样的策略：首先用户分配的内存块所在的结点 level 值初始化为NODE_NOW_LEVEL，如果用户需要延长其生命期到上一级函数或全局变量，那么调用 gc_link 并传入相应的 level 值。仅在其生命期需要延长至上一级函数时需要在函数结尾处（通过返回值传递动态内存时需要在
return 前）调用 func_end。func_end的作用是将该内存块的 level 值设置为NODE_NOW_LEVEL。
      知道了结点的生命期，标记就简单了。gc_leave负责将当前函数栈中的evel为NODE_NOW_LEVEL的结点标记为MARK_COLLECT，从而在 gc_collect 中回收。这里需要说的是main()函数中分配的内存和挂到全局变量的内存会在gc_exit中释放。
      大致过程知道了，下面就是具体实现了：

Code:
  1. #include <stdio.h>   
  2. #include <stdlib.h>   
  3. #include <stdarg.h>   
  4. #include <assert.h>   
  5. #include "stack.h"   
  6. #include "mem_pool.h"   
  7. #include "gc.h"   
  8.   
  9.   
  10.   
  11. #define POOL_INITIAL_NUMBER 1024 /* the initial number of nodes
    in pool */       
  12. #define POOL_MAX_NUMBER 4096     /* the
    max number of nodes in pool */       
  13.   
  14. #define STACK_SECTION_TAG NULL /* the tag to section the stack */   
  15.   
  16. #define MARK_INITIAL -1     /* the node initialed */   
  17. #define MARK_RESERVE 0      /* the node marked for reserve */   
  18. #define MARK_COLLECT 1      /* the node marked for collect */   
  19.   
  20. struct node {
      
  21.     int mark;          /* mark for gc collect */  
  22.     int level;         /* the node leavel */  
  23.     struct {
      
  24.         void *mem;     /* the pointer point to memory*/  
  25.         int size;      /* the size of memrory */  
  26.         void (*finalizer)(void *); /* destruction when the mem be free */  
  27.     }n;
      
  28. };
      
  29.   
  30. static struct {
      
  31.     struct node *pool;   /* an array for store the pointer of node */  
  32.     int size;            /* the size of pool */  
  33.     int free;            /* the next free node in pool */  
  34.     struct stack *stack; /* the stack used for store
    pointer in fuction */      
  35. } E;
      
  36.   
  37. static bool pool_compact()
      
  38. {
      
  39.     int i, j;
      
  40.     struct node temp;
      
  41.     
      
  42.     for (i = 0; i < E.free; i++) {
      
  43.         if (E.pool[i].mark == MARK_INITIAL) {
      
  44.             temp = E.pool[i];
  45.             for (j =
    E.free; j > i; j--) {   
  46.                 if (E.pool[j].mark != MARK_INITIAL) {
      
  47.                     E.pool[i] = E.pool[j];
      
  48.                     E.pool[j] = temp;
      
  49.                     break;
      
  50.                 }
      
  51.             }
      
  52.         }
      
  53.     }
      
  54.     
      
  55.     for (i = 0; i < E.size; i++) {
      
  56.         if (E.pool[i].mark == MARK_INITIAL) {
      
  57.             E.free = i;
      
  58.             break;
      
  59.         }
      
  60.     }
      
  61.     
      
  62.     return E.free >= E.size ? true : false;
      
  63. }
      
  64.   
  65. static void node_init()
      
  66. {
      
  67.     int i;
      
  68.     
      
  69.     for (i = E.free; i < E.size; i++) {
      
  70.         E.pool[i].mark = MARK_INITIAL;
      
  71.         E.pool[i].level = NODE_NOW_LEVEL;
      
  72.         E.pool[i].n.mem = NULL;
      
  73.         E.pool[i].n.finalizer = NULL;
      
  74.     }
      
  75. }
      
  76.   
  77. static void pool_expand()
      
  78. {
      
  79.     int expand_size;
      
  80.     bool expand = false;
      
  81.     
      
  82.     expand_size = E.size * 2;
      
  83.     if (expand_size >= POOL_MAX_NUMBER * sizeof(struct node)) {
      
  84.          expand = pool_compact();
      
  85.     } 
      
  86.     
      
  87.     if (expand) {
      
  88.         E.pool = (struct node *)my_realloc(E.pool, expand_size * sizeof(struct node),
      
  89.              E.size * sizeof(struct node));
      
  90.         E.free = E.size;
      
  91.         E.size = expand_size;
      
  92.         
      
  93.         /* init the node */  
  94.         node_init();
      
  95.     }   
      
  96. }
      
  97.   
  98. static void node_alloc(void *p, size_t sz, void (*finalizer)(void *))
      
  99. {
      
  100.     if (E.free >= E.size) {
      
  101.         pool_expand();
      
  102.     }
  104.   
     E.pool[E.free].mark = MARK_RESERVE;   
  105.   
     E.pool[E.free].level = NODE_NOW_LEVEL;   
  106.   
     E.pool[E.free].n.mem = p;   
  107.   
     E.pool[E.free].n.size = sz;     // for mem_free   
  108.   
     E.pool[E.free].n.finalizer = finalizer;   
  109.         
      
  110.   
     E.free++;         
       
  111. }
      
  112.   
  113.   
  114.   
  115. static void pool_init()
      
  116. {
      
  117.     E.pool = (struct node *)my_malloc(POOL_INITIAL_NUMBER * sizeof(struct node));
      
  118.     E.free = 0;
      
  119.     E.size = POOL_INITIAL_NUMBER;
      
  120.     
      
  121.     /* init the node */  
  122.     node_init();
      
  123. }
      
  124.   
  125.   
  126.   
  127. void gc_init()
      
  128. {
      
  129.     E.pool = NULL;
      
  130.     E.size = 0;
      
  131.     E.free = -1;
      
  132.     E.stack = init_stack();
      
  133.     
      
  134.     pool_init();
      
  135. }
      
  136.   
  137. void gc_link(void *p, int level)
      
  138. {
      
  139.     int i;
      
  140.     
      
  141.     for (i = 0; i < E.free; i++) {
      
  142.         if (E.pool[i].n.mem == p) {
      
  143.             E.pool[i].level = level;
      
  144.             break;
      
  145.         }
      
  146.     }
      
  147. }
      
  148.   
  149. void gc_enter()
      
  150. {
      
  151.     push(E.stack, STACK_SECTION_TAG);
      
  152. }
      
  153.   
  154. /* accordind to the level of nodes, mark nodes. if in present stack section   
  155.  * of function, there are some nodes' life extend father function's life   
  156.  * which callthe present function, then push these nodes in stack section  
  157.  * of father's function.  
  158.  */  
  159.   
  160. void gc_leave()
      
  161. {
      
  162.     void *p;
      
  163.     struct stack *stack_temp;
      
  164.     
      
  165.     stack_temp = init_stack();
      
  166.     while ((p = top(E.stack)) != STACK_SECTION_TAG) {
      
  167.         int i;
      
  168.         
      
  169.         /* whether mark for gc collect or not by searching for the node   
  170.             whose mem element equals p. */  
  171.         for (i = 0; i < E.free; i++) {
      
  172.             if (E.pool[i].n.mem == p ) {
      
  173.                 if (E.pool[i].level == NODE_NOW_LEVEL) {
      
  174.                     E.pool[i].mark =  MARK_COLLECT;
      
  175.                 } else if (E.pool[i].level == NODE_PRE_LEVEL) {
      
  176.                     push(stack_temp, p);
      
  177.                 }
      
  178.                 break;
      
  179.             }
      
  180.         }
      
  181.         
      
  182.         pop(E.stack);
      
  183.     }
      
  184.     
      
  185.     pop(E.stack); /* pop the STACK_SECTION_TAG */  
  186.     
      
  187.     while (! stack_empty(stack_temp)) {
      
  188.         p = top(stack_temp);
      
  189.         push(E.stack, p);
      
  190.         pop(stack_temp);
      
  191.     }
      
  192.     
      
  193.     destory_stack(stack_temp);
      
  194. }
      
  195.   
  196. void gc_collect()
      
  197. {
      
  198.     int i;
      
  199.     
      
  200.     for (i = 0; i < E.free; i++) {
      
  201.         if (E.pool[i].mark == MARK_COLLECT) {
      
  202.             void *p = E.pool[i].n.mem;
      
  203.             int sz = E.pool[i].n.size;
      
  204.             if (E.pool[i].n.finalizer != NULL) {
      
  205.                 E.pool[i].n.finalizer(p);
      
  206.             }
      
  207.             my_free(p, sz); // for mem_free(p, size);   
  208.             
      
  209.             E.pool[i].mark = MARK_INITIAL;
      
  210.         }
      
  211.     }
      
  212. }
      
  213.   
  214. void *gc_malloc(size_t sz, void (* finalizer)(void *))
      
  215. {
      
  216.     void *result = my_malloc(sz);
      
  217.     node_alloc(result, sz, finalizer);
      
  218.     push(E.stack, result);
      
  219.     return result;
      
  220. }
      
  221.   
  222. void *gc_realloc(void *p, size_t sz)
      
  223. {
      
  224.     void *result;
      
  225.     assert(sz > 0);
      
  226.     
      
  227.     if (p == NULL) {
      
  228.         return gc_malloc(sz, NULL);
      
  229.     }
      
  230.     
      
  231.     /* find the node contain p */  
  232.     int i;
      
  233.     int old_sz;
      
  234.                 
      
  235.     for (i = 0; i < E.free; i++) {
      
  236.         if (E.pool[i].n.mem == p) {
      
  237.             old_sz = E.pool[i].n.size;
      
  238.             break;
      
  239.         }
      
  240.     }
      
  241.   
  242.     result = my_realloc(p, sz, old_sz);
      
  243.     /* if new memory address is not change, just update size and return */  
  244.     if (result == p) {  
      
  245.         E.pool[i].n.size = sz;
      
  246.         return result;
      
  247.     } else {
      
  248.         /* update size and mem */  
  249.         E.pool[i].n.size = sz;
      
  250.         E.pool[i].n.mem = result;
      
  251.         
      
  252.         /* update the stack infomation */  
  253.         
      
  254.         void *temp;
      
  255.         struct stack *stack_temp = init_stack();
      
  256.         
      
  257.         while ((! stack_empty(E.stack)) && ((temp = top(E.stack)) != p)) {
      
  258.             push(stack_temp, temp);
      
  259.             pop(E.stack);
      
  260.         }
      
  261.         
      
  262.         /* if the stack is not empty, pop the old address p and push   
  263.             the new address result */  
  264.         
      
  265.         if (! stack_empty(E.stack)) {
      
  266.             pop(E.stack);
      
  267.             push(E.stack, result);
      
  268.         }
      
  269.         
      
  270.         /* push the former data */  
  271.         while (! stack_empty(stack_temp)) {
      
  272.             temp = top(stack_temp);
      
  273.             push(E.stack, temp);
      
  274.             pop(stack_temp);
      
  275.         }
      
  276.         
      
  277.         destory_stack(stack_temp);
      
  278.     }
      
  279.     return result;
      
  280. }
      
  281.   
  282. void gc_exit()
      
  283. {
      
  284.     /* the rest nodes (normally are root nodes) will free in this function */  
  285.     int i;
      
  286.     
      
  287.     for (i = 0; i < E.free; i++) {
      
  288.         if (E.pool[i].mark != MARK_INITIAL) {
      
  289.             E.pool[i].mark = MARK_COLLECT;
      
  290.         }
      
  291.     }
      
  292.     
      
  293.     gc_collect();
      
  294.     
      
  295.     my_free(E.pool, E.size * sizeof(struct node));
      
  296.     
      
  297.     destory_stack(E.stack);
      
  298. }
      
  299.   
  300. /* this remand the last paramater must be NULL */  
  301. void func_end(void *p, ...)
      
  302. {
      
  303.     va_list ap;
      
  304.     void *temp = p;
      
  305.     va_start(ap, p);
      
  306.     
      
  307.     int i;
      
  308.     while (temp != NULL) {
      
  309.         for (i = 0; i < E.free; i++) {
      
  310.             if (E.pool[i].n.mem == temp) {
      
  311.                 E.pool[i].level = NODE_NOW_LEVEL;
      
  312.                 break;
      
  313.             }
      
  314.         }
      
  315.         
      
  316.         temp = va_arg(ap, void *);
      
  317.     }
      
  318.     
      
  319.     va_end(ap);
      
  320. }
      

这里给出测试代码：

Code:
  1. #include <stdio.h>   
  2. #include "gc.h"   
  3.   
  4. static void log_ptr(void *p)
      
  5. {
      
  6.     printf("free %p/n",p);
      
  7. }
      
  8.   
  9. int *foo1()
      
  10. {
      
  11.     printf("in function foo1:/n");
      
  12.     int *p3 = gc_malloc(3, log_ptr);
      
  13.     int *p4 = gc_malloc(6, log_ptr);
      
  14.     int *p5 = gc_realloc(p4, 1024);
      
  15.     
      
  16.     gc_link(p3, NODE_PRE_LEVEL);
      
  17.     func_end(p3, NULL);
      
  18.     return p3;
      
  19. }
      
  20.   
  21.   
  22. void foo()
      
  23. {
      
  24.     gc_enter();
      
  25.     int *p1 = foo1();
      
  26.     int *p2 = gc_malloc(4, log_ptr);
      
  27.     
      
  28.     gc_link(p2, NODE_ROOT_LEVEL);
      
  29.     
      
  30.     gc_leave();
      
  31.     
      
  32.     printf("in foo:/n");
      
  33.     gc_collect();
      
  34. }
      
  35.   
  36.   
  37. int main()
      
  38. {
      
  39.     gc_init();
      
  40.     
      
  41.     gc_enter();
      
  42.     
      
  43.     void *p = gc_malloc(5, log_ptr);
      
  44.     foo();
      
  45.     
      
  46.     gc_leave();
      
  47.     
      
  48.     printf("in fuction main:/n");
      
  49.     gc_collect();
      
  50.     gc_exit();
      
  51.     
      
  52.     return 0;
      
  53. }
      

运行结果：

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞