内存管理：堆

2025-11-21 3566 words 8 minutes

Contents

本文参考OSDev Wiki上关于“堆”的介绍及实现，原文地址：https://wiki.osdev.org/Heap

堆内存

Heap（堆）

堆是应用程序和内核都离不开的重要组成部分。通常，它位于更高层次的内存管理机制之下，而高层机制负责处理更大粒度的内存块。在大多数操作系统中，内存是按页（page）或其他较大的块进行分配的。在 X86 和 X64 架构中，一页通常是 4KB，但也可能更大。然而，对于较小的分配需求，如果直接占用整页会造成大量浪费。例如，只需要 24 字节却分配整整 4KB 页，将导致严重的内存浪费。因此，大多数应用程序和内核都会实现第二层内存管理：在以 4KB（或更大）为单位分配得到的内存块基础上，根据需求将这些一组页面或单独页面拆分成更小的部分进行分配。

标准库、应用程序与内核

在大多数操作系统中，应用程序的堆由标准库实现，而不会使用内核采用的堆实现。因此，内核的堆不仅与每个应用程序的堆相互独立，而且它们可能使用完全不同的堆实现。此外，这也使得每个应用程序可以根据其使用或构建所依赖的标准库选择自身的堆实现。不过，内核也完全可以直接向应用程序提供堆服务。需要注意的是，无法强制某个应用程序必须使用某种特定的堆或堆实现，因为只要程序员足够聪明，就可以利用已分配的内存自行实现一套堆管理机制。

教程 / 实现方案 / 文章

页面名称	简要说明
简易堆内存实现	一种简洁、可移植且内存利用率较高的实现方案。
编写堆内存实现方案	实现一个基础的首次适配（First Fit）内存管理（MM）机制其实并不难……（下文续）

简易堆内存实现

原文链接：https://wiki.osdev.org/User:Pancakes/SimpleHeapImplementation

Simple Heap Implementation

这里有几个简单的堆实现供你参考。“我”打算之后在每个页面上写一些教程，带读者逐步理解它们的工作原理。

如果你想直接将它们复制到你的内核中使用，也完全没问题。“我”把这些实现放在这里，是为了让那些对实现堆并不感兴趣的人也能快速完成这件事，然后继续做更重要的事情。

位图（bitmap）实现已经进行了相当充分的优化。“我”找不到可以带来显著性能提升的地方了。但它在处理多个块时仍需要一些优化，例如把已满的块移动到链表末尾。此外，entry 也许可以使用双链结构：一条链连接空闲项，另一条链连接使用中的项，这样可以加快分配速度。目前的方式是逐一遍历所有 entry。并且，在 entry 实现中，释放操作也可以更快一些。

“我”已经对这两个实现进行了充分的内部破坏性测试，在块的起始和结尾处检查 32 位字段以检测越界读写。即使长时间运行，目前仍未发现任何损坏。

如果你发现任何 bug、问题，或在使用中取得了好的效果，请告诉“我”：kmcg3413@gmail.com。

Simulation

“我”写了一个页面，可以模拟位图堆，并可视化内存和内存访问回放。它直接对应位图算法，但只使用 16 位字段。你可以在这里找到它： **http://kmcg3413.net/jsbmheap.htm**。其中还包含一个指向位图实现页面的链接，方便你参考实际代码和结构。（好像已经不能访问了

Implementations

以下是这些实现。“我”推荐位图版本，因为它可靠、性能不错、简单且代码量小，是初学者实现堆的非常有吸引力的选择。

页面	简要说明
Bitmap Based	一个非常简单且性能尚可的实现。
Entry Based	性能不佳，但展示了另一种思路。
Stack Based	非常快，但只支持一种块大小；如果数据更小，会根据栈条目大小造成浪费。可以通过链式方式支持多种大小，类似 SLAB 分配器。
Bitmap Based With Enhanced Functionality	位图实现的增强版本，支持管理物理内存，并能按任意边界对齐数据。
Linked List Bucket Heap	一个非常快的通用分配器，适用于大小不同的分配请求。

Performance

增强位图实现（标记为 bm，绿色）初始化时使用 16 字节块。链表桶堆（Linked List Bucket Heap）标记为 mrvn，浅红色。从图中可以看到，位图实现的性能会随着分配大小的增加而下降。深紫色为 entry 实现。

横轴数字表示最大分配大小。例如，256 表示分配大小在 1 到 256 字节之间；4096 表示 1 到 4096 字节之间。每个实现都运行了较长时间，并进行了随机分配和释放。如果某个实现的内存用完，会允许其使用更多内存。

链表桶堆（Linked List Bucket Heap）是一个非常优秀的通用堆实现，但它稍微复杂一些，从代码层面来看也更难理解。位图堆虽然由于位图表的元数据消耗了大量内存，但在代码结构上相对简单、直观。

文中的数字表示相对于“我“所使用机器上 C 库提供的标准 malloc 和 free 的速度提升倍率。它表示该实现的整体速度快了多少倍，并将 malloc 和 free 的速度综合考虑为一个总体性能。一些实现（如 entry-based 和 bitmap）拥有极快的释放速度，能够超过所有其他实现，但它们的初次分配速度太慢，导致整体性能无法保持领先。

简易堆实现（位图实现）

原文链接：https://wiki.osdev.org/User:Pancakes/BitmapHeapImplementation

Bitmap Heap Implementation

这种堆实现为每个块（block）使用一张位图（bitmap），而不是为每次分配（以及未分配的空间）在块内使用一个独立的头部（header）。

它能提供按块内指定的“块大小（block size）”对齐的数据。因此，如果你使用多种块大小，那么最终数据可能按不同的边界对齐。如果你打算在这个堆的基础上进一步改进，这可能是你需要优化的特性。

另外，不要混淆“块（block）”和“块大小（block size）”。你向堆中添加块（这些块中会发生实际的分配），而在每个块内部，你需要指定一个参数用于将该块切分成更小的单元。例如，你可以指定 16，表示在块内部以 16 字节为单位进行切分。这个 16 既是对齐单位，也是位图中每一位所代表的子块大小。

该实现还使用了 KHEAPBLOCKBM 结构中的 lfb 字段做了轻微优化。它基本上指向最近一次分配之后的位置，希望在后续分配中能够更接近空闲区域。在某些情况下，这种技巧可能效果不佳，但在早期开发阶段，它能提供相当可观的性能。随着你的内核或用户程序逐渐成熟，你可能需要寻找更好的实现方式。

Simulation

我写了一个页面，可以模拟该位图堆并可视化内存及内存访问回放。它直接对应本算法，但只使用 16 位字段。你可以在 [1]（原链接已失效）找到它。

Example Usage

使用 #define 指令使函数名更简短可能更容易，例如将 k_heapBMAlloc 重命名为 kmalloc，或将 k_heapBMFree 重命名为 kfree。例如：

#define kmalloc k_heapBMAlloc

或者，你也可以直接修改函数名。

传给 add block 函数的数字 16 指定了默认的块大小（有点像硬盘的扇区大小）。因此，一个 9 字节的数据实际会占用 16 字节，而一个 17 字节的数据会占用 32 字节。

示例代码：

KHEAPBM     kheap;
char        *ptr;

k_heapBMInit(&kheap);                              /* 初始化堆 */
k_heapBMAddBlock(&kheap, 0x100000, 0x100000, 16);  /* 添加一个块
                                                     （从 1MB 开始，长度为 1MB）
                                                     默认子块大小为 16 字节
                                                   */
ptr = (char*)k_heapBMAlloc(&kheap, 256);           /* 分配 256 字节（类似 malloc） */
k_heapBMFree(&kheap, ptr);                         /* 释放指针（类似 free） */

现在，使用这个实现你会遇到一个问题：当没有剩余内存时，它会返回空指针（null pointer），这可能令人头疼。为了解决这个问题，你可以编写一个包装函数（比如叫 kmalloc），让它检查返回值是否为空。如果为空，则从更高层的内存管理器申请新内存，用 k_heapBMAddBlock 添加一个新的块，然后重新尝试分配。

你还需要检查你添加的块是否足够大。例如，如果你向堆中添加的块大小是 4KB，而某次分配需要 16KB，那么你就需要添加一个至少大于 16KB 的块，以便容纳位图和头部。我稍后会尝试添加一个函数，用来告诉你实现特定大小的分配所需的最小块大小，不过现在这大概算是留给你的一个练习！

Code

/*
    2014 Leonard Kevin McGuire Jr (www.kmcg3413.net) (kmcg3413@gmail.com)
    2016 Clément Gallet (provided bug fixes)
*/
typedef struct _KHEAPBLOCKBM {
	struct _KHEAPBLOCKBM	                *next;
	uint32					size;
	uint32					used;
	uint32					bsize;
        uint32                                  lfb;
} KHEAPBLOCKBM;

typedef struct _KHEAPBM {
	KHEAPBLOCKBM			*fblock;
} KHEAPBM;

void k_heapBMInit(KHEAPBM *heap) {
	heap->fblock = 0;
}

int k_heapBMAddBlock(KHEAPBM *heap, uintptr addr, uint32 size, uint32 bsize) {
	KHEAPBLOCKBM		*b;
	uint32				bcnt;
	uint32				x;
	uint8				*bm;
	
	b = (KHEAPBLOCKBM*)addr;
	b->size = size - sizeof(KHEAPBLOCKBM);
	b->bsize = bsize;
	
	b->next = heap->fblock;
	heap->fblock = b;

	bcnt = b->size / b->bsize;
	bm = (uint8*)&b[1];
	
	/* clear bitmap */
	for (x = 0; x < bcnt; ++x) {
			bm[x] = 0;
	}

	/* reserve room for bitmap */
	bcnt = (bcnt / bsize) * bsize < bcnt ? bcnt / bsize + 1 : bcnt / bsize;
	for (x = 0; x < bcnt; ++x) {
			bm[x] = 5;
	}
	
	b->lfb = bcnt - 1;
	
	b->used = bcnt;
	
	return 1;
}

static uint8 k_heapBMGetNID(uint8 a, uint8 b) {
	uint8		c;	
	for (c = a + 1; c == b || c == 0; ++c);
	return c;
}

void *k_heapBMAlloc(KHEAPBM *heap, uint32 size) {
	KHEAPBLOCKBM		*b;
	uint8				*bm;
	uint32				bcnt;
	uint32				x, y, z;
	uint32				bneed;
	uint8				nid;

	/* iterate blocks */
	for (b = heap->fblock; b; b = b->next) {
		/* check if block has enough room */
		if (b->size - (b->used * b->bsize) >= size) {
			
			bcnt = b->size / b->bsize;		
			bneed = (size / b->bsize) * b->bsize < size ? size / b->bsize + 1 : size / b->bsize;
			bm = (uint8*)&b[1];
			
			for (x = (b->lfb + 1 >= bcnt ? 0 : b->lfb + 1); x < b->lfb; ++x) {
				/* just wrap around */
				if (x >= bcnt) {
					x = 0;
				}		

				if (bm[x] == 0) {	
					/* count free blocks */
					for (y = 0; bm[x + y] == 0 && y < bneed && (x + y) < bcnt; ++y);
					
					/* we have enough, now allocate them */
					if (y == bneed) {
						/* find ID that does not match left or right */
						nid = k_heapBMGetNID(bm[x - 1], bm[x + y]);
						
						/* allocate by setting id */
						for (z = 0; z < y; ++z) {
							bm[x + z] = nid;
						}
						
						/* optimization */
						b->lfb = (x + bneed) - 2;
						
						/* count used blocks NOT bytes */
						b->used += y;
						
						return (void*)(x * b->bsize + (uintptr)&b[1]);
					}
					
					/* x will be incremented by one ONCE more in our FOR loop */
					x += (y - 1);
					continue;
				}
			}
		}
	}
	
	return 0;
}

void k_heapBMFree(KHEAPBM *heap, void *ptr) {
	KHEAPBLOCKBM		*b;	
	uintptr				ptroff;
	uint32				bi, x;
	uint8				*bm;
	uint8				id;
	uint32				max;
	
	for (b = heap->fblock; b; b = b->next) {
		if ((uintptr)ptr > (uintptr)b && (uintptr)ptr < (uintptr)b + sizeof(KHEAPBLOCKBM) + b->size) {
			/* found block */
			ptroff = (uintptr)ptr - (uintptr)&b[1];  /* get offset to get block */
			/* block offset in BM */
			bi = ptroff / b->bsize;
			/* .. */
			bm = (uint8*)&b[1];
			/* clear allocation */
			id = bm[bi];
			/* oddly.. GCC did not optimize this */
			max = b->size / b->bsize;
			for (x = bi; bm[x] == id && x < max; ++x) {
				bm[x] = 0;
			}
			/* update free block count */
			b->used -= x - bi;
			return;
		}
	}
	
	/* this error needs to be raised or reported somehow */
	return;
}