看了《程序员自我修养》这本书后，对目标文件、可执行文件的结构有了比较清晰的了解，对目标文件链接成可执行文件的过程和程序运行库有了大致的认识。不过正如“纸上得来终觉浅，绝知此事需恭行”，很多东西看似容易，但实践的时候却往往不是这样，在实践中往往能发现很多的问题。《程序员自我修养》这本书我觉得是理论与实践很好的结合了，它在最后一章给出了一个c和c++运行库的简单版的实现，通过实现这个可以更为深刻地理解可执行文件的结构、程序的执行、运行库的实现。参考这边书，我在linux下实现的一个简单的c运行库，这个运行库主要实现了文件操作、字符串操作、动态内存分配三个方面。

程序的入口函数实现

　　当被问到程序的入口函数是什么的时候，很多人都会回答是main函数。其实这是不准确的，因为如果main是第一个开始执行的函数，那么对于在main函数外面定义的变量，特别是c++中的对象，由谁来初始化它们呢？还有就是我们用atexit函数注册的清理函数在main函数结束之后才被调用。种种都说明在main函数之外还有函数，它负责建立程序执行所需的环境，包括变量的初始化和堆的初始化，清理函数的调用，构造函数和析构函数调用（如果是c++的话）。这个函数在为程序准备好了运行环境之后才开始调用main函数。我实现的入口函数很简单，它主要负责对堆进行初始化、调用main函数和退出程序。

/*初始化堆*/
if (CrtInitHeap() == -1)
    CrtFataError("init heap error\n");
/*获取argc和argv*/
__asm__ volatile(
    "movl 0x4(%%ebp), %0\n\t"
    "lea 0x8(%%ebp), %1"    
     :"=r"(argc),"=r"(argv)
     );
environ = &argv[argc + 1];
ret = main(argc, argv);
exit(ret);

　　当程序被加载到内存中，在运行上面的入口函数前，操作系统就将程序的命令行参数和环境变量放到了该程序的栈中，这时候栈的分布为：

此时，栈顶指针指向ebp，正如在程序的栈结构中说的那样，当进入函数时，通常做的第一件事就是把ebp保存到栈中。从上图可以知道argc在esp+4中，argv在esp+8中，程序中用了嵌入汇编来获得它们的值，程序中第10行获得环境变量，然后就是调用main函数了，向main中传递了argc和argv（现在可以明白为什么我们可以再main中直接用argc和argv了吧！！），最后根据main的返回值调用exit结束程序。

　　这里最主要的还是初始化堆和管理堆比较麻烦些，为什么要初始化堆呢？因为我们程序经常要用到malloc函数来动态申请内存，而malloc函数是从堆中获取内存的。你可能会说堆不是在程序开始运行前就由操作系统分配好了给程序吗？其实我们这个初始化堆的意思是说把分配给堆的地址空间变大，并不是真正的申请内存，只有当程序用malloc申请并用到时才真正分配内存（用时才分配，这个是内存管理的时，我们就不深究了）。因为程序运行时给堆的地址空间是比较小的，所以需要初始化堆。管理堆的工作主要是负责堆的分配和回收。

堆的初始化

　　正如上面讲的，我们的堆初始化就是扩充堆的地址空间。我们可以用系统调用brk来完成这个，不过现在我们不能用glibc的库，所以只能用汇编来调用了brk系统调用了。

int brk(void *addr)
{
    int ret;

    __asm__ volatile(
        "movl %1, %%ebx\n\t"    
        "movl $45, %%eax\n\t"
        "int $0x80 \n\t"
        :"=a"(ret)
        :"m"(addr)
    );
    return ret;
}

　　brk的系统调用号时45，当传递的参数是NULL时，brk会返当前堆的起始地址，brk的参数是堆的结束地址，所以要扩充堆地址空间，必须先获取堆的起始地址，然后根据起始地址来扩充堆地址空间。　

void *heapBase, *heapEnd;
int heapSize = 1024 * 1024 * 32;

/*扩展堆的大小到32MB*/
heapBase = (void *)brk((void *)0);
heapEnd = (void *)brk(ADDR_ADD(heapBase, heapSize));
if (heapEnd == heapBase)
    return -1;

堆的管理

　　堆的工作主要是管理用brk申请来的空间，负责空间的分配和回收。我用的是双向链表实现的，链表的节点结构为heap_header结构体，当用malloc函数申请堆空间时，采用最先适应算法，只要找到一个满足申请空间大小的空闲节点，就将该节点所在的空间分配给它，如果该节点的空间比较大，则拆分这个节点为两个节点，前一个节点分配申请空间的大小，并标记为占用，后一个为空闲节点。在用free函数释放堆空间时，确定该空间所在的节点，并将该节点标记为空闲，查找该节点的相邻节点是否是空闲节点，如果是则合并。

　　堆空间中节点的数据结构为：　

typedef struct _heap_header
{
    enum heap_state state;/*是否空闲*/
    int size;/*本节点空间大小*/
    struct _heap_header *next;/*下一个节点*/
    struct _heap_header *pre;/*上一个节点*/
}heap_header;

entry.c参考代码

#include "minicrt.h"

char **environ;
extern int main(int argc, char *argv[]);
void exit(int exitCode);

void CrtFataError(char *fmt, ...)
{
	va_list ap;

	va_start(ap, fmt);
	vfprintf(stdout, fmt, ap);

	va_end(ap);
	exit(-1);
}

void MiniCrtEntry(void)
{
	int ret, argc;
	char **argv;

	/*初始化堆*/
	if (CrtInitHeap() == -1)
		CrtFataError("init heap error\n");
	/*初始化IO*/
	if (!CrtInitIo() == -1)
		CrtFataError("init io error\n");
//	do_global_ctors();
	/*获取argc和argv*/
	__asm__ volatile(
		"movl 0x4(%%ebp), %0\n\t"
		"lea 0x8(%%ebp), %1"	
		 :"=r"(argc),"=r"(argv)
		 );
	environ = &argv[argc + 1];
	ret = main(argc, argv);
	exit(ret);
}

void exit(int exitCode)
{
//	mini_crt_all_exit_routine();
	__asm__ volatile(
		"movl %0, %%ebx\n\t"	
		"movl $1, %%eax\n\t"
		"int $0x80\n\t"
		"hlt"
		::"m"(exitCode)
		);
}

malloc.c参考代码

#include "minicrt.h"
/*
 * 为每个程序初始化32MB的堆空间，对于堆空间的管理采用链表法，分配采用最先适应算法
 * */
enum heap_state
{
	HEAP_USED = 0xabababab,
	HEAP_FREE = 0xcdcdcdcd
};

typedef struct _heap_header
{
	enum heap_state state;/*是否空闲*/
	int size;/*本节点空间大小*/
	struct _heap_header *next;/*下一个节点*/
	struct _heap_header *pre;/*上一个节点*/
}heap_header;

static heap_header *heapList = NULL;

#define ADDR_ADD(a, o) (((char *)a) + o)
#define HEADER_SIZE (sizeof(heap_header))

int CrtInitHeap()
{
	void *heapBase, *heapEnd;
	int heapSize = 1024 * 1024 * 32;

	/*扩展堆的大小到32MB*/
	heapBase = (void *)brk((void *)0);
	heapEnd = (void *)brk(ADDR_ADD(heapBase, heapSize)); 
	if (heapEnd == heapBase)
		return -1;
	heapList = (heap_header *)heapBase;
	heapList->state = HEAP_FREE;
	heapList->size = heapSize;
	heapList->next = NULL;
	heapList->pre = NULL;
	return 0;
}

int brk(void *addr)
{
	int ret;

	__asm__ volatile(
		"movl %1, %%ebx\n\t"	
		"movl $45, %%eax\n\t"
		"int $0x80 \n\t"
		:"=a"(ret)
		:"m"(addr)
	);
	return ret;
}

void *malloc(int size)
{
	heap_header *heapHeader = heapList;
	if (size == 0)	
		return NULL; 
	while (heapHeader)	
	{
		if (heapHeader->state == HEAP_FREE)	
		{
			if (heapHeader->size >= size + HEADER_SIZE && heapHeader->size <= size + 2 * HEADER_SIZE)	
			{
				/*如果节点的size不超过size + 2 * HEADER_SIZE，是不需要拆分节点的*/	
				heapHeader->state = HEAP_USED;
				return ADDR_ADD(heapHeader, HEADER_SIZE);
			}
			else if (heapHeader->size > size + 2 * HEADER_SIZE)
			{
				heap_header *temp = (heap_header *)ADDR_ADD(heapHeader, size + HEADER_SIZE);	
				temp->state = HEAP_FREE;
				temp->size = heapHeader->size - (size + HEADER_SIZE);
				temp->pre = heapHeader;
				temp->next = heapHeader->next;
				heapHeader->state = HEAP_USED;
				heapHeader->size = size + HEADER_SIZE;
				heapHeader->next = temp;
				return ADDR_ADD(heapHeader, HEADER_SIZE);
			}
		}
		heapHeader = heapHeader->next;
	}
	return NULL;
}

void free(void *ptr)
{
	heap_header *heapHeader; 
	if (!ptr)
		return;
	heapHeader = (heap_header *)ADDR_ADD(ptr, -HEADER_SIZE);	
	if (heapHeader->state == HEAP_FREE)
		CrtFataError("free(%x) has already been called before\n", ptr);		
	if (heapHeader->state == HEAP_USED)
	{
		heapHeader->state = HEAP_FREE;	
		if (heapHeader->pre && heapHeader->pre->state == HEAP_FREE)
		{
			heapHeader = heapHeader->pre;
			heapHeader->size += heapHeader->next->size;
			heapHeader->next = heapHeader->next->next;
			if (heapHeader->next)
				heapHeader->next->pre = heapHeader;
		}
		if (heapHeader->next && heapHeader->next->state == HEAP_FREE)
		{
			heapHeader->size += heapHeader->next->size;
			heapHeader->next = heapHeader->next->next;
			if (heapHeader->next)
				heapHeader->next->pre = heapHeader;
		}
	}
	else
		CrtFataError("free error\n");
}