1. zengl开源网
  2. zenglOX
  3. zenglOX v0.0.6 使用Heap(堆)动态分配和释放内存

zenglOX v0.0.6 使用Heap(堆)动态分配和释放内存

zenglong  2014-04-01 10:45:32

之前的v0.0.5版本里的堆，直接是从内核结束位置开始，不断向高地址方向分配内存，因此还不具备释放内存的能力，要让堆具备动态分配和动态释放内存的能力，就需要建立一套相关的堆算法...

    v0.0.6的项目地址：

    github.com地址：https://github.com/zenglong/zenglOX (只包含git提交上来的源代码)
   
    Dropbox地址：点此进入Dropbox网盘  (该版本位于zenglOX_v0.0.6的文件夹，该文件夹里的zip压缩包为源代码)

    sourceforge地址：https://sourceforge.net/projects/zenglox/files  (该版本位于zenglOX_v0.0.6的文件夹，该文件夹里的zip压缩包为源代码)

    有关zenglOX的编译及gdb调试的方法，请参考zenglOX v0.0.1里的文章。

    之前的v0.0.5版本里的堆，直接是从内核结束位置开始，不断向高地址方向分配内存，因此还不具备释放内存的能力，要让堆具备动态分配和动态释放内存的能力，就需要建立一套相关的堆算法。在当前的v0.0.6的版本里就建立了这么一套算法，这些算法主要集中在zlox_kheap.c和zlox_ordered_array.c文件里，算法相关的结构体则对应定义在zlox_kheap.h和zlox_ordered_array.h的头文件里。

    在zlox_kheap.h里有如下三个和堆相关的结构体定义：

typedef struct _ZLOX_KHP_HEADER
{
	ZLOX_UINT32 magic; // Magic number,用于判断是否是有效的ZLOX_KHP_HEADER
	ZLOX_UINT8 is_hole; // 如果是1则说明是未分配的hole，如果是0则说明是已分配的block
	ZLOX_UINT32 size; // hole或block的总大小的字节数(包括头，数据部分及底部)
}ZLOX_KHP_HEADER; // 堆里的hole或block的头部结构

typedef struct _ZLOX_KHP_FOOTER
{
	ZLOX_UINT32 magic; // 和ZLOX_KHP_HEADER里的magic作用一样
	ZLOX_KHP_HEADER * header; // 通过header指针，方便从FOOTER底部结构直接访问HEADER头部信息
}ZLOX_KHP_FOOTER; // 堆里的hole或block的底部结构

typedef struct _ZLOX_HEAP
{
	ZLOX_ORDERED_ARRAY index;
	ZLOX_UINT32 start_address;	// The start of our allocated space.
	ZLOX_UINT32 end_address;	// The end of our allocated space. May be expanded up to max_address.
	ZLOX_UINT32 max_address;	// The maximum address the heap can be expanded to.
	ZLOX_UINT8 supervisor;		// Should extra pages requested by us be mapped as supervisor-only?
	ZLOX_UINT8 readonly;		// Should extra pages requested by us be mapped as read-only?
} ZLOX_HEAP;

    这三个结构体的关系图如下：


图1

    上图只是一个简单的示意图，图中的ZLOX_HEAP表示一个堆管理器，它的第一个成员index是一个ZLOX_ORDERED_ARRAY的结构体，该结构体定义在zlox_ordered_array.h的头文件里：

typedef struct _ZLOX_ORDERED_ARRAY
{
	ZLOX_VPTR * array; // 指针数组的起始线性地址
	ZLOX_UINT32 size; // 指针数组里当前已存储的hole指针数目
	ZLOX_UINT32 max_size; // 指针数组最多能容纳的指针数目
	ZLOX_LESSTHEN_FUNC less_than; // 指针数组用于进行排序比较的函数
} ZLOX_ORDERED_ARRAY;

    ZLOX_ORDERED_ARRAY里的第一个成员array是一个指针，它指向了上面图1里的hole ptr数组的起始位置，该数组里存储了所有hole的指针值，hole是指堆管理器里所有未分配出去的内存块，当一个hole被分配给程序使用后，该hole就会变为block(表示已分配的内存块)，hole变为block后，就会将hole的ptr指针值从hole ptr数组里移除，反过来，当某个block被释放后，该block就又会变为hole，并且将hole的指针值重新加入hole ptr数组，以便于下一次的分配。

    从图1可以看到，不论是未分配的hole，还是已分配的block，都是由三个部分组成：
  • ZLOX_KHP_HEADER头部结构
  • 中间的Unuse或using部分
  • ZLOX_KHP_FOOTER底部结构
    ZLOX_KHP_HEADER和ZLOX_KHP_FOOTER里的第一个成员都是magic，用于判断某个hole或block是否有效，当ZLOX_KHP_HEADER结构里的第二个成员is_hole为1时表示该内存块是一个hole，当is_hole为0时，表示该内存块是一个block。ZLOX_KHP_HEADER结构里的第三个成员size用于表示hole或block的总字节数(包括头部和底部结构在内)。

    在block里实际分配给用户的是图1里中间的using部分，返回给用户的指针也是using部分的起始线性地址。

    内核的堆管理器的初始化创建工作是在zlox_paging.c文件里的zlox_init_paging函数里完成的(也就是和分页初始化一起完成)：

ZLOX_VOID zlox_init_paging()
{
.............................
.............................

	// 先为堆(当前起始线性地址为0xc0000000)分配页表项,但是暂时先不设置具体的物理内存,
	//	因为必须确保堆之前的线性地址能够先从frames位图里分配到物理内存,否则内核代码部分的
	//	线性地址就会找不到正确的物理地址(内核代码的线性地址等于物理地址),堆必须等内核部分的映射完,
	//	然后才能用它们后面的物理地址进行映射 
	i = 0;
	for (i = ZLOX_KHEAP_START; i < ZLOX_KHEAP_START+ZLOX_KHEAP_INITIAL_SIZE; i += 0x1000)
		zlox_get_page(i, 1, kernel_directory);

.............................
.............................

	// 为之前给堆(0xc0000000起始的线性地址)准备的页表设置具体的物理地址
	for (i = ZLOX_KHEAP_START; i < ZLOX_KHEAP_START+ZLOX_KHEAP_INITIAL_SIZE; i += 0x1000)
		zlox_alloc_frame(zlox_get_page(i, 1, kernel_directory), 0, 0);

.............................
.............................

	// 在0xc0000000线性地址处创建一个新的堆,用于后面的zlox_kmalloc,zlox_kfree之类的分配及释放操作
	kheap = zlox_create_heap(ZLOX_KHEAP_START,ZLOX_KHEAP_START+ZLOX_KHEAP_INITIAL_SIZE,0xCFFFF000, 0, 0);
}

    上面代码里的注释已经详细的解释了这些代码的含义，首先是为堆的初始线性地址范围0xc0000000到0xc0100000分配页表和设置页表项里的物理内存地址，然后使用zlox_create_heap函数(该函数位于zlox_kheap.c文件里)在刚才设置好的线性地址空间里，创建堆结构，也就是设置图1里的hole ptr数组部分，以及设置该数组后面的hole内存块部分，0xc0000000的线性地址对应的物理内存地址是紧挨着内核页表和堆管理器后面的：


图2

     上图里，0x00000000到0x001xxxxx的内核代码，内核页表及堆管理器部分被映射为了相同的物理内存地址(这样内核里的代码在开启分页后才能正常执行)，而堆相关的0xc0000000到0xc0100000的线性地址在frames位图的分配下，映射到了0x001xxxxx到0x002xxxxx的物理地址范围，这也就是前面提到的4G线性地址空间可以映射到十几M物理内存里的原因。

    zlox_create_heap函数的代码如下：

// 创建堆的函数,start为堆的起始线性地址,end_addr为堆的当前结束地址,max为堆可以expand(扩展)的最大尺寸,
//	supervisor表示该堆是否只允许内核代码访问(0表示用户程序可以访问,1表示用户程序不可访问),
//	readonly表示该堆是否是只读的(0表示可读写,1表示只读),在expand扩展堆空间时,supervisor和readonly
//	可以用来设置页表里的属性
// 另外,start开始的第一个部分是heap堆的index部分,index部分是一个数组,该数组存储了该堆里所有可供分配的hole的指针值,
//	并且index里的hole的指针是根据hole的尺寸由小到大排列的,尺寸小的hole的指针值排在前面,较大的排在后面
ZLOX_HEAP * zlox_create_heap(ZLOX_UINT32 start, ZLOX_UINT32 end_addr, 
							ZLOX_UINT32 max, ZLOX_UINT8 supervisor, ZLOX_UINT8 readonly)
{
	ZLOX_HEAP *heap = (ZLOX_HEAP *)zlox_kmalloc(sizeof(ZLOX_HEAP));

	// All our assumptions are made on startAddress and endAddress being page-aligned.
	ZLOX_ASSERT(start%0x1000 == 0);
	ZLOX_ASSERT(end_addr%0x1000 == 0);
	
	// Initialise the index.
	// 创建堆的index部分,index的含义在函数开头的注释里做了说明
	heap->index = zlox_place_ordered_array((ZLOX_VOID *)start, ZLOX_HEAP_INDEX_SIZE, &zlox_header_less_than);
	
	// Shift the start address forward to resemble where we can start putting data.
	// index后面就是实际的未分配的hole和已分配的block部分
	start += sizeof(ZLOX_VPTR) * ZLOX_HEAP_INDEX_SIZE;

	// Make sure the start address is page-aligned.
	if ((start & 0x00000FFF) != 0)
	{
		start &= 0xFFFFF000;
		start += 0x1000;
	}
	// Write the start, end and max addresses into the heap structure.
	heap->start_address = start;
	heap->end_address = end_addr;
	heap->max_address = max;
	heap->supervisor = supervisor;
	heap->readonly = readonly;

	// We start off with one large hole in the index.
	// 刚开始创建的堆,除了堆头部的index指针数组外,其余部分是一个大的hole,这样zlox_kmalloc函数就可以从该hole里分配到内存
	ZLOX_KHP_HEADER *hole = (ZLOX_KHP_HEADER *)start;
	hole->size = end_addr-start;
	hole->magic = ZLOX_HEAP_MAGIC;
	hole->is_hole = 1;
	ZLOX_KHP_FOOTER *hole_footer = (ZLOX_KHP_FOOTER *)((ZLOX_UINT32)hole + hole->size - sizeof(ZLOX_KHP_FOOTER));
	hole_footer->magic = ZLOX_HEAP_MAGIC;
	hole_footer->header = hole;
	zlox_insert_ordered_array((ZLOX_VPTR)hole, &heap->index);	 

	return heap;
}

    上面代码里先通过zlox_place_ordered_array函数(位于zlox_ordered_array.c文件里)设置前面图1里的hole ptr数组(该数组的起始线性地址为0xc0000000)，返回的ZLOX_ORDERED_ARRAY结构体则设置到heap的index成员里，hole ptr数组后面一直到0xc0100000为止的部分在创建堆时被分配为一个大的hole 。

    初始化完内核的kheap堆后，在zlox_kmalloc函数里就可以使用kheap来动态分配内存了(该函数位于zlox_kheap.c文件里)：

ZLOX_HEAP * kheap = 0;

ZLOX_UINT32 zlox_kmalloc_int(ZLOX_UINT32 sz, ZLOX_SINT32 align, ZLOX_UINT32 *phys)
{
	ZLOX_UINT32 tmp;
	// 是否初始化了堆,如果初始化了,则使用堆来分配内存
	if (kheap != 0)
	{
		ZLOX_VOID *addr = zlox_alloc(sz, (ZLOX_UINT8)align, kheap);
		if (phys != 0)
		{
			// 从分页表里获取addr线性地址对应的实际的物理内存地址
			ZLOX_PAGE *page = zlox_get_page((ZLOX_UINT32)addr, 0, kernel_directory);
			*phys = (page->frame * 0x1000) + ((ZLOX_UINT32)addr & 0xFFF);
		}
		// 返回线性地址
		return (ZLOX_UINT32)addr;
	}
	else
	{
		// This will eventually call malloc() on the kernel heap.
		// For now, though, we just assign memory at placement_address
		// and increment it by sz. Even when we've coded our kernel
		// heap, this will be useful for use before the heap is initialised.
		if (align == 1 && (placement_address & 0x00000FFF) )
		{
			// Align the placement address;
			placement_address &= 0xFFFFF000;
			placement_address += 0x1000;
		}
		if (phys)
		{
			*phys = placement_address;
		}
		tmp = placement_address;
		placement_address += sz;
		return tmp;
	}
}

........................................
........................................

ZLOX_UINT32 zlox_kmalloc(ZLOX_UINT32 sz)
{
	return zlox_kmalloc_int(sz, 0, 0);
}

    在kheap没有被初始化时，采用的是原来的方式，直接在内核结束位置开始向高地址方向分配内存，在kheap使用zlox_create_heap函数初始化后，就可以用zlox_alloc函数从kheap里动态分配内存(该函数也位于zlox_kheap.c文件里)：

// 从heap堆里查找能够容纳size尺寸的hole,如果找到该hole,则将该hole变为block,如果hole分离出block后,
//	还有多余的空间,则多余的部分形成新的hole,如果找不到满足size要求的hole,则对heap进行expand(扩展物理内存)
ZLOX_VOID * zlox_alloc(ZLOX_UINT32 size, ZLOX_UINT8 page_align, ZLOX_HEAP * heap)
{
	//	Make sure we take the size of header/footer into account.
	//	计算new_size时,除了要考虑size所需的内存尺寸外,还必须把头部,底部结构的尺寸也考虑进去
	ZLOX_UINT32 new_size = size + sizeof(ZLOX_KHP_HEADER) + sizeof(ZLOX_KHP_FOOTER);
	// Find the smallest hole that will fit.
	ZLOX_SINT32 iterator = zlox_find_smallest_hole(new_size, page_align, heap);
	
	if (iterator == -1) // If we didn't find a suitable hole
	{
		// Save some previous data.
		ZLOX_UINT32 old_length = heap->end_address - heap->start_address;
		ZLOX_UINT32 old_end_address = heap->end_address;

		// We need to allocate some more space.
		zlox_expand(old_length+new_size, heap);
		ZLOX_UINT32 new_length = heap->end_address - heap->start_address;
		ZLOX_KHP_FOOTER * old_end_footer = (ZLOX_KHP_FOOTER *)(old_end_address - sizeof(ZLOX_KHP_FOOTER));
		ZLOX_ASSERT(old_end_footer->magic == ZLOX_HEAP_MAGIC);
		// 在zlox_expand扩容了heap的堆空间后,新增空间的前面如果本身是一个hole的话,就将新增的空间合并到前面的hole里
		if(old_end_footer->header->magic == ZLOX_HEAP_MAGIC &&
			old_end_footer->header->is_hole == 1)
		{
			// The last header needs adjusting.
			ZLOX_KHP_HEADER *header = old_end_footer->header;
			header->size += new_length - old_length;
			// Rewrite the footer.
			ZLOX_KHP_FOOTER *footer = (ZLOX_KHP_FOOTER *) ( (ZLOX_UINT32)header + header->size - sizeof(ZLOX_KHP_FOOTER) );
			footer->header = header;
			footer->magic = ZLOX_HEAP_MAGIC;
		}
		// 如果前面不是一个hole,则将新增的空间变为一个单独的hole
		else
		{
			ZLOX_KHP_HEADER *header = (ZLOX_KHP_HEADER *)old_end_address;
			header->magic = ZLOX_HEAP_MAGIC;
			header->size = new_length - old_length;
			header->is_hole = 1;
			ZLOX_KHP_FOOTER *footer = (ZLOX_KHP_FOOTER *) (old_end_address + header->size - sizeof(ZLOX_KHP_FOOTER));
			footer->magic = ZLOX_HEAP_MAGIC;
			footer->header = header;
			zlox_insert_ordered_array((ZLOX_VPTR)header, &heap->index);
		}
		// We now have enough space. Recurse, and call the function again.
		return zlox_alloc(size, page_align, heap);
	}

	ZLOX_KHP_HEADER *orig_hole_header = (ZLOX_KHP_HEADER *)zlox_lookup_ordered_array(iterator, &heap->index);
	ZLOX_UINT32 orig_hole_pos = (ZLOX_UINT32)orig_hole_header;
	ZLOX_UINT32 orig_hole_size = orig_hole_header->size;
	// Here we work out if we should split the hole we found into two parts.
	// Is the original hole size - requested hole size less than the overhead for adding a new hole?
	// 判断找到的hole尺寸除了可以满足基本的new_size需求外,是否可以再分出一个hole,这里只有差值大于头与底部的大小,
	//	才能形成一个新的hole,所以这里差值做了小于等于的判断,当小于等于时,说明不能形成一个新的hole,
	//	则将hole整个分配出去
	if (orig_hole_size-new_size <= sizeof(ZLOX_KHP_HEADER)+sizeof(ZLOX_KHP_FOOTER))
	{
		// Then just increase the requested size to the size of the hole we found.
		// 如果hole满足new_size后,不能再分出一个hole了,则将整个hole都分配出去
		size += orig_hole_size-new_size;
		new_size = orig_hole_size;
	}

	// If we need to page-align the data, do it now and make a new hole in front of our block.
	// 如果需要对齐,而hole的头部下面的指针没有页对齐,则进行页对齐操作,
	//	且将页对齐后剩余出来的offset偏移值作为新hole的大小
	if (page_align && 
		((orig_hole_pos + sizeof(ZLOX_KHP_HEADER)) & 0x00000FFF)
		)
	{
		ZLOX_UINT32 new_location   = orig_hole_pos + 0x1000 /* page size */ - (orig_hole_pos & 0xFFF) - sizeof(ZLOX_KHP_HEADER);
		ZLOX_KHP_HEADER *hole_header = (ZLOX_KHP_HEADER *)orig_hole_pos;
		hole_header->size	= 0x1000 /* page size */ - (orig_hole_pos & 0xFFF) - sizeof(ZLOX_KHP_HEADER);
		hole_header->magic	= ZLOX_HEAP_MAGIC;
		hole_header->is_hole = 1;
		ZLOX_KHP_FOOTER *hole_footer = (ZLOX_KHP_FOOTER *) ( (ZLOX_UINT32)new_location - sizeof(ZLOX_KHP_FOOTER) );
		hole_footer->magic	= ZLOX_HEAP_MAGIC;
		hole_footer->header	= hole_header;
		orig_hole_pos		= new_location;
		orig_hole_size		= orig_hole_size - hole_header->size;
	}
	else
	{
		// Else we don't need this hole any more, delete it from the index.
		// hole变为block后,需要将hole从index指针数组里移除
		zlox_remove_ordered_array(iterator, &heap->index);
	}

	// Overwrite the original header...
	ZLOX_KHP_HEADER *block_header  = (ZLOX_KHP_HEADER *)orig_hole_pos;
	block_header->magic		= ZLOX_HEAP_MAGIC;
	block_header->is_hole	= 0;
	// 如果找到的hole减去所需的new_size后,剩余尺寸可以容纳一个有效的hole的话,就将剩余的部分变为一个新的hole
	if (orig_hole_size - new_size > sizeof(ZLOX_KHP_HEADER)+sizeof(ZLOX_KHP_FOOTER))
	{
		block_header->size = new_size;
		// ...And the footer
		ZLOX_KHP_FOOTER *block_footer = (ZLOX_KHP_FOOTER *) (orig_hole_pos + sizeof(ZLOX_KHP_HEADER) + size);
		block_footer->magic = ZLOX_HEAP_MAGIC;
		block_footer->header = block_header;
		ZLOX_KHP_HEADER *hole_header = (ZLOX_KHP_HEADER *) (orig_hole_pos + sizeof(ZLOX_KHP_HEADER) + size + sizeof(ZLOX_KHP_FOOTER));
		hole_header->magic = ZLOX_HEAP_MAGIC;
		hole_header->is_hole = 1;
		hole_header->size = orig_hole_size - new_size;
		ZLOX_KHP_FOOTER *hole_footer = (ZLOX_KHP_FOOTER *) ( (ZLOX_UINT32)hole_header + hole_header->size - sizeof(ZLOX_KHP_FOOTER) );
		hole_footer->magic = ZLOX_HEAP_MAGIC;
		hole_footer->header = hole_header;
		// Put the new hole in the index;
		zlox_insert_ordered_array((ZLOX_VPTR)hole_header, &heap->index);
	}
	// 剩余部分不足以形成新的hole,则将找到的hole整个分配出去
	else
	{
		block_header->size	  = orig_hole_size;
		ZLOX_KHP_FOOTER *block_footer  = (ZLOX_KHP_FOOTER *)(orig_hole_pos + block_header->size - sizeof(ZLOX_KHP_FOOTER));
		block_footer->magic	 = ZLOX_HEAP_MAGIC;
		block_footer->header	= block_header;
	}

	// ...And we're done!
	return (ZLOX_VOID *)((ZLOX_UINT32)block_header+sizeof(ZLOX_KHP_HEADER));
}

    上面代码里的注释已经详细的讲解了如何查找hole，以及hole变为block的过程，这里主要看下zlox_expand函数，该函数是当堆管理的内存空间里没有符合size尺寸条件的hole时，用于扩容堆的物理内存的(该函数也位于zlox_kheap.c文件里)：

// 当堆空间不足时,扩展堆的物理内存 
static ZLOX_VOID zlox_expand(ZLOX_UINT32 new_size, ZLOX_HEAP * heap)
{
	// Sanity check.
	ZLOX_ASSERT(new_size > heap->end_address - heap->start_address);

	// Get the nearest following page boundary.
	// 扩展的尺寸必须是页对齐的
	if ((new_size & 0x00000FFF) != 0)
	{
		new_size &= 0xFFFFF000;
		new_size += 0x1000;
	}

	// Make sure we are not overreaching ourselves.
	ZLOX_ASSERT(heap->start_address + new_size <= heap->max_address);

	// This should always be on a page boundary.
	ZLOX_UINT32 old_size = heap->end_address-heap->start_address;

	ZLOX_UINT32 i = old_size;
	while (i < new_size)
	{
		// 从frames位图里为扩展的线性地址分配物理内存
		zlox_alloc_frame( zlox_get_page(heap->start_address+i, 1, kernel_directory),
					 (heap->supervisor)?1:0, (heap->readonly)?0:1);
		i += 0x1000 /* page size */;
	}
	heap->end_address = heap->start_address+new_size;
}

    上面代码里使用zlox_get_page和zlox_alloc_frame函数为扩充的线性地址设置对应的页表项，以及从frames位图里分配物理内存地址，在扩容后，设置heap新的end_address(结束线性地址)。

    hole可以通过zlox_alloc函数变为block，反过来，block也可以通过zlox_free函数变回hole(zlox_free函数也位于zlox_kheap.c文件里)：

// 将p指针所在的block(已分配的堆内存)变为hole(未分配的堆内存),同时在变为hole之后,
//	如果该hole的左右相邻位置存在hole的话,则将这些hole合并为一个大的hole,
//	另外,如果free释放生成的hole刚好又位于堆的底部时,则将堆空间进行contract收缩操作
ZLOX_VOID zlox_free(ZLOX_VOID *p, ZLOX_HEAP *heap)
{
	// Exit gracefully for null pointers.
	if (p == 0)
		return;

	// Get the header and footer associated with this pointer.
	ZLOX_KHP_HEADER *header = (ZLOX_KHP_HEADER *)((ZLOX_UINT32)p - sizeof(ZLOX_KHP_HEADER));
	ZLOX_KHP_FOOTER *footer = (ZLOX_KHP_FOOTER *)((ZLOX_UINT32)header + header->size - sizeof(ZLOX_KHP_FOOTER));

	// Sanity checks.
	ZLOX_ASSERT(header->magic == ZLOX_HEAP_MAGIC);
	ZLOX_ASSERT(footer->magic == ZLOX_HEAP_MAGIC);

	// 如果本身就是一个hole,则直接返回
	if(header->is_hole == 1)
		return;

	// Make us a hole.
	header->is_hole = 1;

	// Do we want to add this header into the 'free holes' index?
	ZLOX_CHAR do_add = 1;

	// Unify left
	// If the thing immediately to the left of us is a footer...
	// 合并左侧低地址方向的hole,如果左侧刚好有一个hole,则将当前释放的hole直接合并到左侧的hole里
	ZLOX_KHP_FOOTER *test_footer = (ZLOX_KHP_FOOTER *)((ZLOX_UINT32)header - sizeof(ZLOX_KHP_FOOTER));
	if (test_footer->magic == ZLOX_HEAP_MAGIC &&
		test_footer->header->is_hole == 1)
	{
		ZLOX_UINT32 cache_size = header->size; // Cache our current size.
		header = test_footer->header; // Rewrite our header with the new one.
		footer->header = header; // Rewrite our footer to point to the new header.
		header->size += cache_size; // Change the size.
		do_add = 0; // Since this header is already in the index, we don't want to add it again.
	}

	// Unify right
	// If the thing immediately to the right of us is a header...
	// 合并右侧高地址方向的hole,如果右侧刚好有一个hole,则将右侧的hole合并到当前释放的hole里
	ZLOX_KHP_HEADER *test_header = (ZLOX_KHP_HEADER*)((ZLOX_UINT32)footer + sizeof(ZLOX_KHP_FOOTER));
	if (test_header->magic == ZLOX_HEAP_MAGIC &&
		test_header->is_hole == 1)
	{
		header->size += test_header->size; // Increase our size.
		test_footer = (ZLOX_KHP_FOOTER *) ( (ZLOX_UINT32)test_header + // Rewrite it's footer to point to our header.
									test_header->size - sizeof(ZLOX_KHP_FOOTER) );
		footer = test_footer;
		footer->header = header;
		// Find and remove this header from the index.
		ZLOX_UINT32 iterator = 0;
		while ((iterator < heap->index.size) &&
			   (zlox_lookup_ordered_array(iterator, &heap->index) != (ZLOX_VPTR)test_header))
			iterator++;

		// Make sure we actually found the item.
		ZLOX_ASSERT(iterator < heap->index.size);
		// Remove it.
		zlox_remove_ordered_array(iterator, &heap->index);
	}

	// If the footer location is the end address, we can contract.
	// 如果hole位于堆的底部,则对堆进行contract收缩操作,以回收一部分物理内存资源
	if ( (ZLOX_UINT32)footer+sizeof(ZLOX_KHP_FOOTER) == heap->end_address)
	{
		ZLOX_UINT32 old_length = heap->end_address-heap->start_address;
		ZLOX_UINT32 new_length = zlox_contract( (ZLOX_UINT32)header - heap->start_address, heap);
		// Check how big we will be after resizing.
		if (header->size - (old_length-new_length) > 0)
		{
			// We will still exist, so resize us.
			header->size -= old_length-new_length;
			footer = (ZLOX_KHP_FOOTER *)((ZLOX_UINT32)header + header->size - sizeof(ZLOX_KHP_FOOTER));
			footer->magic = ZLOX_HEAP_MAGIC;
			footer->header = header;
		}
		else
		{
			// We will no longer exist :(. Remove us from the index.
			ZLOX_UINT32 iterator = 0;
			while ( (iterator < heap->index.size) &&
					(zlox_lookup_ordered_array(iterator, &heap->index) != (ZLOX_VPTR)header))
				iterator++;
			// If we didn't find ourselves, we have nothing to remove.
			if (iterator < heap->index.size)
				zlox_remove_ordered_array(iterator, &heap->index);
			do_add = 0;
		}
	}

	// If required, add us to the index.
	// 由于生成了新的hole,所以根据需要将该hole的头部的指针值设置到index对应的数组里
	if (do_add == 1)
		zlox_insert_ordered_array((ZLOX_VPTR)header, &heap->index);

}

    上面代码就是block变为hole的过程，在变为hole的过程里，还可以合并低地址与高地址方向相邻的hole，从而形成一个大的hole，另外当释放的hole位于底部时，还可以通过zlox_contract函数来收缩堆的空间，以释放一部分物理内存(zlox_contract函数同样位于zlox_kheap.c文件里)：

// 根据需要回收一部分堆的物理内存,将回收的部分从页表和frames位图里去除
static ZLOX_UINT32 zlox_contract(ZLOX_UINT32 new_size, ZLOX_HEAP * heap)
{
	// Sanity check.
	ZLOX_ASSERT(new_size < heap->end_address-heap->start_address);

	// Get the nearest following page boundary.
	if (new_size & 0x00000FFF)
	{
		new_size &= 0xFFFFF000;
		new_size += 0x1000;
	}

	// Don't contract too far!
	// 回收的尺寸受到ZLOX_HEAP_MIN_SIZE的限制,防止回收过多的内存资源
	if (new_size < ZLOX_HEAP_MIN_SIZE)
	{
		if(ZLOX_HEAP_MIN_SIZE - new_size > 
			sizeof(ZLOX_KHP_HEADER) + sizeof(ZLOX_KHP_FOOTER))
			new_size = ZLOX_HEAP_MIN_SIZE;
		// 如果收缩堆空间后,剩余尺寸不能形成一个有效的hole,则放弃收缩,返回原来的尺寸
		else
			return (heap->end_address-heap->start_address);
	}

	ZLOX_UINT32 old_size = heap->end_address-heap->start_address;
	ZLOX_UINT32 i = old_size - 0x1000;
	while (new_size <= i)
	{
		// 通过zlox_free_frame将需要回收的页面从页表和frames位图里去除
		zlox_free_frame(zlox_get_page(heap->start_address+i, 0, kernel_directory));
		i -= 0x1000;
	}

	heap->end_address = heap->start_address + new_size;
	return new_size;
}

    有了动态分配内存和动态释放内存的机制，就可以在zlox_kernel_main即内核的主入口函数里进行测试：

//zenglOX kernel main entry
ZLOX_SINT32 zlox_kernel_main(ZLOX_VOID * mboot_ptr)
{
	// init gdt and idt
	zlox_init_descriptor_tables();	

	// Initialise the screen (by clearing it)
	zlox_monitor_clear();

	// 未初始化堆时,为a分配内存
	ZLOX_UINT32 a = zlox_kmalloc(8);

	zlox_init_paging();

	// Write out a sample string
	zlox_monitor_write("hello world!\nwelcome to zenglOX v0.0.6!\n");

	// 在zlox_init_paging函数里初始化堆后,为b,c,d分配和释放内存
	ZLOX_UINT32 b = zlox_kmalloc(8);
	ZLOX_UINT32 c = zlox_kmalloc(8);
	zlox_monitor_write("a: ");
	zlox_monitor_write_hex(a);
	zlox_monitor_write(", b: ");
	zlox_monitor_write_hex(b);
	zlox_monitor_write("\nc: ");
	zlox_monitor_write_hex(c);

	zlox_kfree((ZLOX_VOID *)c);
	zlox_kfree((ZLOX_VOID *)b);
	ZLOX_UINT32 d = zlox_kmalloc(12);
	zlox_monitor_write(", d: ");
	zlox_monitor_write_hex(d);

	/*asm volatile("int $0x3");
	asm volatile("int $0x4");
	
	asm volatile("sti");
	zlox_init_timer(50);*/

	return (ZLOX_SINT32)mboot_ptr;
}

    上面使用zlox_kmalloc函数依次为几个变量分配内存，并且使用zlox_kfree函数来释放内存(zlox_kfree函数里会间接调用zlox_free函数)，bochs里的运行结果如下：


图3

    在给a变量分配内存时，kheap对应的堆还没有被初始化，所以a得到的内存地址就是0x105c9c的地址。

    最后，该版本的堆算法有个BUG，就是在一开始只为0xc0000000开始的线性地址分配了一个页表，而一个页表只能表示4M的物理内存，当zlox_expand函数扩容超过4M时，就无法分配了，因为zlox_expand里会调用zlox_get_page来设置页表，而zlox_get_page里会通过zlox_kmalloc_ap函数间接调用zlox_alloc函数，zlox_alloc又再调用zlox_expand，zlox_expand又调用zlox_get_page，等等，这样就会死循环了。要解决这个问题，可以在一开始根据实际可用的物理内存大小为0xc0000000开始的线性地址设置尽可能多的页表，这个问题会在以后的版本里进行处理。

    OK，就到这里，休息，休息一下 o(∩_∩)o~~
 
上下篇

下一篇： zenglOX v0.0.7 VFS(虚拟文件系统)与initrd(初始化ram disk)

上一篇： zenglOX v0.0.5 分页

相关文章

zenglOX v2.4.0 DMA(Direct Memory Access)

zenglOX v3.1.0 Sound Blaster 16

zenglOX v0.0.11 ELF format(ELF可执行文件格式)与execve系统调用

zenglOX v0.0.4 IRQ(中断请求)与PIT(可编程间隔定时器)

zenglOX v1.6.0 保护模式下, VGA图形模式驱动程式

zenglOX v1.1.0 通过ATAPI读取光盘里的数据