本文重点在实现(x86gccunixunix)like环境下
优采云 发布时间: 2021-08-08 07:32本文重点在实现(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() == '*') { //eat self
Game_Over();
}
if((char)inch() == 'o') { //eat food
move(head->y, head->x);
addch('*');
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()) == '*');
move(food.y, food.x);
addch('o');
refresh();
}
move(head->y, head->x);
addch('*');
refresh();
move(tail->y, tail->x);
addch(' ');
refresh();
}
void key_ctl()
{
int ch = getch();
switch(ch) {
case 'W':
case 'w':
if(dir_x == 0)
break;
dir_x = 0;
dir_y = -1;
break;
case 'S':
case 's':
if(dir_x == 0)
break;
dir_x = 0;
dir_y = 1;
break;
case 'A':
case 'a':
if(dir_y == 0)
break;
dir_y = 0;
dir_x = -1;
break;
case 'D':
case 'd':
if(dir_y == 0)
break;
dir_y = 0;
dir_x = 1;
break;
case ' ':
set_ticker(0);
do {
ch = getch();
}while(ch != ' ');
set_ticker(500);
break;
case 'Q':
case 'q':
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() == '*');
move(head->y, head->x);
addch('*');
move(food.y, food.x);
addch('o');
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;
}