动态内存管理
通常在一块较大且连续的内存空间上根据需要分配内存和回收内存
计算机早期内存资源稀缺，多任务并发执行不可能将多个任务都加载到内存当中，可以通过内存复用增加任务的并发性，某一时间仅有一个任务在内存当中
因此动态内存管理的本质是时间换空间，通过动态分配和回收 “扩大” 物理内存
动态内存管理的关键
从发出内存申请到获得内存的时间越短越好
为了管理内存（记录内存信息等）而占用的内存越少越好
最大可分配内存占空闲内存总和的比例越大越好，即尽量避免外部碎片
动态内存管理的分类
- 定长内存管理：将内存分为大小相同的单元， 每次申请一单元的内存（实时性高，效率高）
- 变长内存管理：每次申请需要的内存（大小不固定， 以字节为单位)
定长内存管理的设计与实现
将内存分为两部分：管理单元（4bytes）&分配单元（32bytes），每次分配仅仅分配32bytes
管理单元应该与分配单元一一对应，n = lengthof(管理单元+分配单元)/36
申请内存：
从链表头（全局变量gFMemList的node成员）获取一个管理单元并且计算下标，根据下标计算分配单元的内存起始地址
归还内存：
计算分配单元的下标，并且将对应下标的管理单元插入链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| typedef byte(FMemUnit)[FM_ALLOC_SIZE];
typedef union _FMemNode FMemNode;
union _FMemNode //管理单元4bytes 注意是union
{
FMemNode* next;
FMemUnit* ptr;
};
typedef struct
{
FMemNode* node;
FMemNode* nbase;
FMemUnit* ubase;
uint max;
} FMemList;
static FMemList gFMemList = {0};
|
定长内存的管理单元与分配单元初始化
对定长内存的管理单元和分配单元一起初始化，每个管理单元(4 bytes)的next指针指向下一个相邻的管理单元(4 bytes)
并且初始化一个全局变量gFMemList用于定位当前的内存管理单元，
gFMemList记录内存管理单元的起始地址和内存分配单元的起始地址（这两个起始地址主要是为了确定一个已经分配出去的内存块是此段定长内存的第几个管理单元或分配单元）以及内存管理链表的头节点等
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
|
static void FMemInit(byte* mem, uint size)
{
FMemNode* p = NULL;
int i = 0;
uint max = 0;
max = size / (FM_NODE_SIZE + FM_ALLOC_SIZE);
gFMemList.max = max;
gFMemList.nbase = (FMemNode*)mem;
gFMemList.ubase = (FMemUnit*)((uint)mem + max * FM_NODE_SIZE);
gFMemList.node = (FMemNode*)mem;
p = gFMemList.node;
for(i=0; i<max-1; i++)
{
FMemNode* current = (FMemNode*)AddrOff(p, i);
FMemNode* next = (FMemNode*)AddrOff(p, i+1);
current->next = next;
}
((FMemNode*)AddrOff(p, i))->next = NULL;
}
|
内存分配与释放
分配：将全局变量gFMemList记录的内存管理链表的头节点分配出去，更新链表的头节点为下一个相邻节点，返回值为分配单元地址
释放：传入参数为分配单元地址，根据gFMemList记录内存管理单元的起始地址和内存分配单元的起始地址可以知道当前分配单元是第几个分配单元，利用头插法将此node插入到内存管理链表头部
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
36
37
38
39
40
41
42
43
| static void* FMemAlloc()
{
void* ret = NULL;
if( gFMemList.node )
{
FMemNode* alloc = gFMemList.node;
int index = AddrIndex(alloc, gFMemList.nbase);
ret = AddrOff(gFMemList.ubase, index);
gFMemList.node = alloc->next;
alloc->ptr = ret;
}
return ret;
}
static int FMemFree(void* ptr)
{
int ret = 0;
if( ptr )
{
uint index = AddrIndex((FMemUnit*)ptr, gFMemList.ubase);
FMemNode* node = AddrOff(gFMemList.nbase, index);
if( (index < gFMemList.max) && IsEqual(node->ptr, ptr) )
{
node->next = gFMemList.node;
gFMemList.node = node;
ret = 1;
}
}
return ret;
}
|
变长内存管理设计与实现
将内存分为三部分： 管理头 & 已用区域 & 空闲区域（此三者统称为一个管理节点）
- 管理头： 记录已用区域和空闲区域的位置
- 已用区域： 已分配的内存区域 （使用中)
- 空闲区域： 可分配的内存区域（空闲)
因此管理节点可以构成一个链表，
申请内存
- 初始时只有一个管理结点 (used == 0,free == all)
- 每次申请时从链表头的管理结点一直遍历直到某个管理节点可用内存满足（free >= alloc )，在此处插入一个新管理节点
- 划分可用内存成为新的管理结点(used == size已用区域，free == 0空闲区域)
- 将管理节点组织成管理链表
归还内存
- 遍历管理链表， 找到对应的目标结点
- 将目标结点从管理链表中删除
- 目标结点所占用的内存归入前一个管理结点的空闲区域中
管理链表初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| typedef struct //管理头
{
ListNode head;
uint used;
uint free;
byte* ptr;
} VMemHead;
static List gVMemList = {0};
static void VMemInit(byte* mem, uint size)
{
List_Init((List*)&gVMemList);
VMemHead* head = (VMemHead*)mem;
head->used = 0;
head->free = size - VM_HEAD_SIZE;
head->ptr = AddrOff(head, 1);
List_AddTail(&gVMemList, (ListNode*)head);
}
|
变长内存分配与释放
提升效率，每次遍历其实都是从开头开始申请
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| static void* VMemAlloc(uint size)
{
ListNode* pos = NULL;
VMemHead* ret = NULL;
uint alloc = size + VM_HEAD_SIZE;
List_ForEach(&gVMemList, pos)
{
VMemHead* current = (VMemHead*)pos;
if( current->free >= alloc )
{
byte* mem = (byte*)((uint)current->ptr + (current->used + current->free) - alloc);
ret = (VMemHead*)mem;
ret->used = size;
ret->free = 0;
ret->ptr = AddrOff(ret, 1);
current->free -= alloc;
List_AddAfter((ListNode*)current, (ListNode*)ret);
break;
}
}
return ret ? ret->ptr : NULL;
}
static int VMemFree(void* ptr)
{
int ret = 0;
if( ptr )
{
ListNode* pos = NULL;
List_ForEach(&gVMemList, pos)
{
VMemHead* current = (VMemHead*)pos;
if( IsEqual(current->ptr, ptr) )
{
VMemHead* prev = (VMemHead*)(current->head.prev);
prev->free += current->used + current->free + VM_HEAD_SIZE;
List_DelNode((ListNode*)current);
ret = 1;
break;
}
}
}
return ret;
}
|
Malloc(uint size)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void* Malloc(uint size)
{
void* ret = NULL;
if( size <= FM_ALLOC_SIZE )
{
ret = FMemAlloc();
}
if( !ret )
{
ret = VMemAlloc(size);
}
return ret;
}
|
Free(void* ptr)
1
2
3
4
5
6
7
8
9
10
| void Free(void* ptr)
{
if( ptr )
{
if( !FMemFree(ptr) )
{
VMemFree(ptr);
}
}
}
|
内存布局图
1
2
3
4
5
6
7
| ; Base Address
HeapBase equ 0x70000
HeapSize equ 0x20000
KernelHeapBase equ HeapBase
AppHeapBase equ HeapBase - HeapSize
PageDirBase equ HeapBase + HeapSize
PageTblBase equ PageDirBase + 0x1000
|
0x50000-0x90000作为堆空间，前半部分给应用程序使用，后半部分给内核使用
针对应用程序堆空间和内核的堆空间分别调用MemModInit(0x50000,0x20000)和MemModInit(0x70000,0x20000)
1
2
3
4
5
6
7
8
9
10
11
|
void MemModInit(byte* mem, uint size)
{
byte* fmem = mem;
uint fsize = size / 2;
byte* vmem = AddrOff(fmem, fsize);
uint vsize = size - fsize;
FMemInit(fmem, fsize);
VMemInit(vmem, vsize);
}
|
此系统最小分配32bytes，即使是malloc(0)也是返回32bytes，free
