本文重点在实现(x86gccunixunix)like环境下

　　本文重点在实现(x86gccunixunix)like环境下

　　注：本文重点是实现（在x86 gcc unix like环境下），而不是算法（否则最简单的回收算法就不用了），纯粹用于教学（娱乐）目的。它不注重效率，但可以使用。 ，并且没有继续支持多线程。

　　具体代码在github上：[]

　　目录：

　　实现中的重点难点介绍：原理图代码的外部接口部分：

　　#include "interface3.h"

#include // 必要头文件

int main()

{

__gc_init(); /* to init gc */

/*add some code you like*/

...

/* need some memory in heap */

void *forgetToFree = (void *)gc_calloc(sizeof(struct XXX));

/*add some code you like*/

...

__gc_exit(); /* to destroy gc */

return 0;

}

　　如何找到mark&sweep的根节点：

　　i) 对于自动变量的标记，可以从当前栈顶一直向上找到environ的正确位置。当然也可以通过读取程序中的/proc/pid/maps来查看栈底地址。然后，只需标记这些区域。

　　ii) 对于全局变量的标签，使用链接器变量 _etext, _end 标签。 （注意gcc工具是支持的，其他编译链接工具完全不能保证）

　　iii) 对于临时变量，标记当前寄存器。

　　具体代码片段：

　　在marksweep.c文件中：

　　static unsigned int stack_bottom = 0;

extern char _end[];

extern char _etext[];

extern char** environ;

void gc_collect()

{

unsigned int stack_top;

unsigned int _eax_,_ebx_,_ecx_,_edx_,_esi_,_edi_;

asm volatile ("movl %%ebp, %0" : "=r" (stack_top));

asm volatile ("movl %%eax, %0" : "=r" (_eax_));

asm volatile ("movl %%ebx, %0" : "=r" (_ebx_));

asm volatile ("movl %%ecx, %0" : "=r" (_ecx_));

asm volatile ("movl %%edx, %0" : "=r" (_edx_));

asm volatile ("movl %%esi, %0" : "=r" (_esi_));

asm volatile ("movl %%edi, %0" : "=r" (_edi_));

/* 我们标记一些寄存器里头的临时变量 */

mark(_eax_);

mark(_ebx_);

mark(_ecx_);

mark(_edx_);

mark(_esi_);

mark(_edi_);

mark_from_region((ptr *)((char *)stack_top + 4),(ptr *)(stack_bottom)); //我们标记自动变量

mark_from_region((ptr *)((char *)_etext + 6),(ptr *)(_end)); //我们标记全局变量

sweep();

}

int __gc_init()

{

unsigned int stack_top;

unsigned int curr;

asm volatile ("movl %%ebp, %0" : "=r" (stack_top));

curr = stack_top;

/* 用简单的循环检查出栈底地址（有逻辑漏洞） */

while(*(unsigned int *)curr != (unsigned int)environ)

{

curr++;

}

stack_bottom = curr;

return __rb_init();

}

　　实现中用到的一些设计和具体方法：

　　代码中会有一些令人费解的宏定义，例如：

　　在 unordered_list.h 文件中：

　　...

#define CHUNKSIZE (1node;

while(curr)

{

__rb_free((RBTree)(curr->data));

curr = curr->next;

}

link_destroy(root->node);

int i = 0;

__free(root);

root = NULL;

}

　　使用mark和sweep函数实现自己的__gc_calloc函数：

　　测试：

　　测试代码：

　　#include

#include

#include

#include "interface3.h"

#define NUM 10000

#define TEST 100

#define RANGE 100

int *a[NUM];

size_t size[NUM];

void leak(int i)

{

int* leak = (int *)__gc_calloc(size[i]);

return;

}

int main(int argc, char *argv[])

{

clock_t start, finish, end;

double duration1, duration2;

int j;

int i;

for (i = 0; i < NUM; ++i)

{

size[i] = 1 + (size_t)(1.0*RANGE*rand()/(RAND_MAX+1.0));

}

__gc_init();

start = clock();

for (j = 0; j < TEST; ++j)

{

for(i = 0; i prev->x;

p->y = p->prev->y;

}

p->x += dir_x;

p->y += dir_y;

if(head->x > 79)

head->x = 0;

if(head->x < 0)

head->x = 79;

if(head->y > 23)

head->y = 0;

if(head->y < 0)

head->y = 23;

move(head->y, head->x);

if((char)inch() == &#39;*&#39;) { //eat self

Game_Over();

}

if((char)inch() == &#39;o&#39;) { //eat food

move(head->y, head->x);

addch(&#39;*&#39;);

refresh();

tmp = (Snake)__gc_calloc(sizeof(SNAKE));

tmp->x = head->x + dir_x;

tmp->y = head->y + dir_y;

tmp->next = head;

head->prev = tmp;

head = tmp;

do {

food.x = rand() % 80;

food.y = rand() % 24;

move(food.y, food.x);

}while(((char)inch()) == &#39;*&#39;);

move(food.y, food.x);

addch(&#39;o&#39;);

refresh();

}

move(head->y, head->x);

addch(&#39;*&#39;);

refresh();

move(tail->y, tail->x);

addch(&#39; &#39;);

refresh();

}

void key_ctl()

{

int ch = getch();

switch(ch) {

case &#39;W&#39;:

case &#39;w&#39;:

if(dir_x == 0)

break;

dir_x = 0;

dir_y = -1;

break;

case &#39;S&#39;:

case &#39;s&#39;:

if(dir_x == 0)

break;

dir_x = 0;

dir_y = 1;

break;

case &#39;A&#39;:

case &#39;a&#39;:

if(dir_y == 0)

break;

dir_y = 0;

dir_x = -1;

break;

case &#39;D&#39;:

case &#39;d&#39;:

if(dir_y == 0)

break;

dir_y = 0;

dir_x = 1;

break;

case &#39; &#39;:

set_ticker(0);

do {

ch = getch();

}while(ch != &#39; &#39;);

set_ticker(500);

break;

case &#39;Q&#39;:

case &#39;q&#39;:

Game_Over();

break;

default:break;

}

}

void Init()

{

initscr();

cbreak();

noecho();

curs_set(0);

srand(time(0));

dir_x = 1;

dir_y = 0;

head = (Snake)__gc_calloc(sizeof(SNAKE));

head->x = rand() % 80;

head->y = rand() % 24;

head->next = (Snake)__gc_calloc(sizeof(SNAKE));

tail = head->next;

tail->prev = head;

tail->x = head->x - dir_x;

tail->y = head->y - dir_y;

do {

food.x = rand() % 80;

food.y = rand() % 24;

move(food.y, food.x);

}while((char)inch() == &#39;*&#39;);

move(head->y, head->x);

addch(&#39;*&#39;);

move(food.y, food.x);

addch(&#39;o&#39;);

refresh();

}

void sig_alrm(int singo)

{

set_ticker(500);

Snake_Move();

}

int main()

{

__gc_init();

char ch;

Init();

signal(SIGALRM, sig_alrm);

set_ticker(500);

while(1) {

key_ctl();

}

endwin();

return 0;

}