CoderZQYのBlog

个人不定期更新的学习周报

0%

CMU15-213

发表于 分类于

CMU 15-213 Malloc Lab

1. Introduction

  1. 用 malloc 申请一块内存空间作为自己的空闲内存；
  2. 实现自己的 void *myalloc(int size) 和 int myfree(void *ptr) 函数，用于分配和回收内存，替代 malloc 和 free 函数；
  3. 采用最先适应、最优适应或最差适应分配算法对空闲内存进行管理。

2. Implementation

2.1 BlockNode

​ 定义BlockNode存储内存块信息，先通过 _aligned_malloc 申请一块 8 字节对齐的内存（也可以采用 VirtualAlloc 分配），然后实现 malloc 和 free 函数对这块内存进行管理。这里将内存以块 (Block) 的方式进行管理，每块内存分为标记区 (Header) 和数据区 (Data)，块的定义如下：

1
2
3
4
5
6
7
/*
 * 内存块分为标记区(Header)和数据区(Data)
 */
struct BlockNode{
	BlockNode* m_next;
	size_t m_size;
};

​ Header 中记录了指向下一块内存的指针和一个 size_t 类型的 m_size 记录这块内存数据的大小。

2.2 MemAllocator

​ 构造一个 MemAllocator 类对内存进行管理，类中维持一个指向所有空闲内存块的 m_freeList。在类的构造函数中通过_ aligned_malloc 申请一块8字节对齐的内存，除了申请内存外，构造构造函数还负责初始化 m_freeList（直接在申请的内存上构建一个空闲块并将其添加到 freelist 中），并在析构函数中释放了这块内存。

​ m_numAllocations 记录了申请和释放内存的次数（每次申请内存时加一，释放时减一），m_remainSize 记录了空闲块数据区的总大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class MemAllocator
{
public:
	MemAllocator(size_t pSize, SEARCH_MODE pMode) {
		m_size = pSize * 8;
		m_data = _aligned_malloc(m_size, 8);//申请一块8字节对齐的内存
		m_mode = pMode;
		memset(m_data, 0, m_size);
		InitFreeList(m_data, m_size);
		cout << "申请内存空间大小为：" << m_size << "B" << endl;
		cout << "内存空间实际剩余为：" << m_remainSize << "B" << endl;
		cout << "内存空间首地址为：0x" << m_data << endl;
	}
    //初始化m_freeList
	void InitFreeList(void* pStart, size_t pSize){
		assert(pStart != nullptr);
		m_numAllocations = 0;
		m_remainSize = pSize - sizeof(BlockNode);
		m_freeList = static_cast<BlockNode*>(pStart);
		m_freeList->m_next = nullptr;
		m_freeList->m_size = m_remainSize;
	}
	~MemAllocator() {
		if (m_data != nullptr) {
			_aligned_free(m_data);
		}
	}
private:
	BlockNode* m_freeList;		//指向所有空闲内存块
	void* m_data;
	size_t m_size;
	size_t m_numAllocations; 	//记录申请和释放内存的次数
	size_t m_remainSize; 		//记录空闲块数据区的总大小
	SEARCH_MODE m_mode;
};

2.3 GetProperBlock()

​ 每次申请内存时需要在 FreeList 中找到合适大小的空闲内存块，这里实现了两种不同的分配算法：

  • First fit，返回第一个数据区大小大于等于所申请内存的空闲块。
  • Best fit，检查所有块，返回数据区和所申请内存大小差距最小且大于等于所需内存的空闲块。
  • Worst fit，和 Best 类似，返回数据区和所申请内存大小差距最大且大于等于所需内存的空闲块（代码略）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
enum class SEARCH_MODE{	//定义三种内存分配算法
	FIRST_FIT,
	BEST_FIT,
    WORST_FIT
};
bool GetProperBlock(size_t pSize, SEARCH_MODE pMode, BlockNode** pPrevNode, BlockNode** pFoundNode) {
	if (pMode == SEARCH_MODE::FIRST_FIT) {
		return GetFirstFitBlock(pSize, pPrevNode, pFoundNode);
	}else if(pMode == SEARCH_MODE::BEST_FIT){
        return GetBestFitBlock(pSize, pPrevNode, pFoundNode);
    }else if(pMode == SEARCH_MODE::WORST_FIT){
        return GetWorstFitBlock(pSize, pPrevNode, pFoundNode);
    }else{
        cout<<"Not implemented yet ...";
        return false;
    }
}

​ First fit 的查找实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool GetFirstFitBlock(size_t pSize, BlockNode** pPrevNode, BlockNode** pFoundNode) {
	BlockNode* prev = nullptr;
	BlockNode* curr = m_freeList;
	bool success = false;

	while (curr != nullptr){
		if (curr->m_size >= pSize){
			success = true;
			break;
		}
		prev = curr;
		curr = curr->m_next;
	}
	*pPrevNode = prev;
	*pFoundNode = curr;
	return success;
}

​ Best fit 的查找实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool GetBestFitBlock(size_t pSize, BlockNode** pPrevNode, BlockNode** pFoundNode){
	BlockNode* prev = nullptr;
	BlockNode* curr = m_freeList;
	bool success = false;

	BlockNode* best = nullptr;
	BlockNode* bestPrev = nullptr;
	size_t bestSize = m_size;
	while (curr != nullptr){
		size_t currSize = curr->m_size;
		if (currSize >= pSize){
			success = true;
			if (currSize < bestSize){
				bestSize = currSize;
				best = curr;
				bestPrev = prev;
			}
		}

		prev = curr;
		curr = curr->m_next;
	}

	*pPrevNode = bestPrev;
	*pFoundNode = best;
	return success;
}

2.4 SplitBlock()

​ 若找到的空闲内存块的大小 size > 所需内存大小 + sizeof(BlockNode)，则可以将该空闲块分裂为两个新的块，并将新分出的块插入到 m_freeList 中：

1
2
3
4
5
6
7
8
9
10
void SplitBlock(BlockNode* pOld, size_t pSize){
	assert(pOld != nullptr);
	size_t oldBlockSize = pOld->m_size;
	assert(oldBlockSize > pSize);
	BlockNode* newBlock = pOld + (pSize + sizeof(BlockNode)) / 8;
	newBlock->m_size = oldBlockSize - pSize - sizeof(BlockNode);
	pOld->m_size = pSize;
	InsertNode(pOld, newBlock);
	cout << "Split block" << endl;
}

​ m_freeList 的插入和删除操作定义如下（均需要插入或删除节点的前驱结点，若前驱结点为空则需要操作的节点为 m_freeList 的头节点）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void RemoveNode(BlockNode* pPrev, const BlockNode* pDelete){
	assert(pDelete != nullptr);
	if (pPrev != nullptr){
		pPrev->m_next = pDelete->m_next;
	}
	else{
		m_freeList = pDelete->m_next;
	}
}

void InsertNode(BlockNode* pPrev, BlockNode* pNew){
	assert(pNew != nullptr);
	if (pPrev != nullptr){
		pNew->m_next = pPrev->m_next;
		pPrev->m_next = pNew;
	}
	else{
		pNew->m_next = m_freeList;
		m_freeList = pNew;
	}
}

2.5 myalloc()

​ myalloc 的实现如下（myalloc 每次申请的内存大小会被缩放为 8 的倍数）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void* myalloc(size_t pSize){
	size_t dataSize = pSize * 8;
	if (dataSize <= m_remainSize){
		BlockNode* prev = nullptr;
		BlockNode* found = nullptr;
		if (GetProperBlock(dataSize, m_mode, &prev, &found)){
			assert(found != nullptr);
			size_t founBlockSize = found->m_size;
			size_t allocateSize = founBlockSize + sizeof(BlockNode);
			if (founBlockSize > (dataSize + sizeof(BlockNode))){
					SplitBlock(found, dataSize);
					allocateSize = dataSize + sizeof(BlockNode);
			}
			RemoveNode(prev, found);
			m_remainSize -= allocateSize;
			++m_numAllocations;
			cout << "Malloc success, num allocations: " << m_numAllocations << endl;
			cout << "Remain size: " << m_remainSize << "B" << endl;
			return found + 1;
		}
	}
	cout << "Malloc failed!" << endl;
	cout << "Remain size: " << m_remainSize << endl;
	return nullptr;
}

​ 若所需内存为 0 或者所需内存大于剩余总空闲内存则直接返回空指针（myalloc(0) 是未定义型为也可以返回一个无法使用但可以被释放的内存块，即只有Header的块），分配成功后将符合要求的空闲内存块移出 m_freeList，并返回指向该块数据区的指针。

2.6 myfree()

​ 释放由 myalloc 所申请的内存时，通过指针比较，找到该内存块在 m_freeList 中的前驱节点（m_freeList中的节点以地址从小到大的顺序排列），查找前驱节点的函数定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool GetPrevNode(BlockNode** pPrev, BlockNode* pNode){
	assert(pNode != nullptr);
	bool success = false;
    BlockNode* prev = nullptr;
	BlockNode* curr = m_freeList;
	while (curr != nullptr){
		if (pNode <= curr){
			success = true;
			break;
		}

		prev = curr;
		curr = curr->m_next;
	}
	*pPrev = prev;
	return success;
}

​ 有了前驱节点和需要释放的内存块后，可以将需要释放的内存块插入到 m_freeList 中，这时可以判断所需释放的内存块的前部和后部的内存块（不是m_freeList中的前驱或后驱节点，而是和需要释放的内存块地址连续邻接的内存块）是否处于空闲状态（可以通过指针的地址进行检查所后驱节点和前驱节点与该节点的内存地址连续则为邻接块），若是则进行合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void MergeBlock(BlockNode* pPrev, BlockNode* pMerge){
	assert(pMerge != nullptr);
	size_t mergeNodeSize = pMerge->m_size;
	m_remainSize += mergeNodeSize;

	if (pMerge->m_next != nullptr){
		size_t nextNodeSize = pMerge->m_next->m_size;
		if ((pMerge + (mergeNodeSize + sizeof(BlockNode)) / 8) == pMerge->m_next) {
			RemoveNode(pMerge, pMerge->m_next);
			cout << "Merge block with next block, size after merge :" << nextNodeSize << endl;
			mergeNodeSize += sizeof(BlockNode) + nextNodeSize;//更新mergeNodeSize
			pMerge->m_size = mergeNodeSize;
			m_remainSize += sizeof(BlockNode);
		}
	}

	if (pPrev != nullptr){
		size_t prevNodeSize = pPrev->m_size;
		if ((pPrev + (prevNodeSize + sizeof(BlockNode)) / 8) == pMerge) {
			cout << "Merge block with prev block, size before merge :" << prevNodeSize << endl;
			RemoveNode(pPrev, pMerge);
			prevNodeSize += mergeNodeSize + sizeof(BlockNode);
			pPrev->m_size = prevNodeSize;
			m_remainSize += sizeof(BlockNode);
		}
	}
}

​ 最后 myfree 函数的具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
void myfree(void* pPtr){
	if (pPtr != nullptr){
		BlockNode* freeBlock = (BlockNode*)pPtr - 1;
		BlockNode* prev = nullptr;
		GetPrevNode(&prev, freeBlock);
		InsertNode(prev, freeBlock);
		MergeBlock(prev, freeBlock);
		--m_numAllocations;
		cout << "Free success, num allocations: " << m_numAllocations << endl;
		cout << "Remain size: " << m_remainSize << endl;
	}
}

​ 由于初始申请的一大块内存为 8 字节对齐，Header的大小为 8，每次申请的内存大小也为 8 的倍数，所以 myalloc 所返回的指针均为 8 字节对齐，这种实现的优点是比较简单，而且对任何对齐大小（1, 2, 4, 8 字节对齐）都可以实现对齐，缺点是若所需的内存大小不是 8 的倍数则会浪费一部分的内存。若想要实现更节省内存一点的分配方式则可以每次分配时计算内存对齐地址，然后再进行分配可以节省一些内存。

更多参考：浅谈C++内存管理

-------------本文结束感谢您的阅读-------------