libc 中提供非常好用的 malloc free 功能，如果自己实现一个，应该怎么做。
要实现 malloc free 需要有 可以分配内存使用的堆，和记录内存使用情况的链表。
如下图所示，堆从高向低分配，链表从低向高分配，图是 ps 画的。
1 /* 管理堆的链表 */
2 typedef struct A_BLOCK_LINK
3 {
4 char *pV; /* 内存实际物理地址 */
5 int index; /* 内存编号 */
6 char empty; /* 1 空 0 非空 */
7 int heapLen; /* 分配长度 */
8 struct A_BLOCK_LINK *pxNextFreeBlock; /* 上个节点 */
9 struct A_BLOCK_LINK *pxPrevFreeBlock; /* 下个节点 */
10 } BlockLink_t;
这里的对应关系是，链表 1 对应 最后一个堆，链表 2对应 最后2个堆。
如何初始化？
1,先计算出来，共能分配多少块内存
2,分配管理链表
如何找到合适的可以分配的内存？
这里从链表1 开始向后查找，当未使用的内存长度满足要求时，将最后找到的链表的，堆地址返回给 申请者。
如何free 内存？
因为 free 只传过来一个 ，最初申请的内存地址，没有传入长度，这里也需要在 链表结构体中进行记录
详细的代码，可以去置顶的 github 项目。
经过测试在， ubuntu16.4 gcc 5.4 中运行正常，free 后的内存，可以被重新 malloc 。
目前还没有实现，内存碎片整理功能。仅有一个空实现。 后期在更新。
实现代码：
1 #include <string.h>
2 #include <stdio.h>
3 #include "sram.h"
4
5 //以下定义大小是为了直观的看到程序运行分配结果，取10进制数
6 //整个SRAM大小
7 #define SRAM_SIZE (1000)
8
9 //堆分块大小
10 #define HeapBlockSIZE (100)
11
12 //以下代码在 GCC 中演示使用编译器分一个大的SRAM 在实际硬件中，直接写内存开始地址就可以
13 //#define SRAM_BASE_ADDR 0
14 static char SRAM_BASE_ADDR[SRAM_SIZE] = {0};
15
16 /* 管理堆的链表 */
17 typedef struct A_BLOCK_LINK
18 {
19 char *pV; /* 内存实际物理地址 */
20 int index; /* 内存编号 */
21 char empty; /* 1 空 0 非空 */
22 int heapLen; /* 分配长度 */
23 struct A_BLOCK_LINK *pxNextFreeBlock; /* 上个节点 */
24 struct A_BLOCK_LINK *pxPrevFreeBlock; /* 下个节点 */
25 } BlockLink_t;
26
27 //头节点
28 static char *HeapHead = NULL;
29 //块数量
30 static int BlockTotal = 0;
31
32 void TraceHeap(void)
33 {
34 BlockLink_t *pTempBlockLink = (BlockLink_t *)HeapHead;
35 printf("\r\n##########TraceHeap#############\r\n");
36 while(pTempBlockLink)
37 {
38 printf("index: %d empty:%d addr:%d \r\n", pTempBlockLink->index, pTempBlockLink->empty, pTempBlockLink->pV - SRAM_BASE_ADDR);
39 pTempBlockLink = pTempBlockLink->pxNextFreeBlock;
40 }
41 printf("\r\n##########TraceHeap#############\r\n");
42 }
43
44 //堆 Heap 分配初始化
45 void InitHeap(void)
46 {
47 BlockLink_t *pBlockLink, *pTempBlockLink = NULL;
48 int i = 0;
49 char *pHeapStart = (char *)SRAM_BASE_ADDR;
50 char *pHeapEnd = (char *)(SRAM_BASE_ADDR + SRAM_SIZE);
51 pHeapEnd -= HeapBlockSIZE;
52 BlockTotal = SRAM_SIZE / (HeapBlockSIZE + sizeof(BlockLink_t));
53 while(i < BlockTotal)
54 {
55 pBlockLink = (BlockLink_t *)pHeapStart;
56 pBlockLink->pxPrevFreeBlock = pTempBlockLink;
57 pBlockLink->pV = pHeapEnd;
58 pBlockLink->index = i;
59 pBlockLink->empty = 1;
60 pBlockLink->heapLen = 0;
61 //指针重定位
62 pHeapEnd -= HeapBlockSIZE;
63 pHeapStart += sizeof(BlockLink_t);
64 //双向链表的上一个
65 pTempBlockLink = pBlockLink;
66 pBlockLink->pxNextFreeBlock = (BlockLink_t *)pHeapStart;
67 i++;
68 }
69 pBlockLink->pxNextFreeBlock = NULL;
70 HeapHead = (char *)SRAM_BASE_ADDR;
71 }
72
73 static BlockLink_t *FindHeap(char *addr)
74 {
75 BlockLink_t *pTempBlockLink = (BlockLink_t *)HeapHead;
76 //从低向高查找可用的内存
77 while(pTempBlockLink)
78 {
79 if(pTempBlockLink->pV == addr)
80 {
81 return pTempBlockLink;
82 }
83 //切换下一节点
84 pTempBlockLink = pTempBlockLink->pxNextFreeBlock;
85 }
86 return NULL;
87 }
88
89 //查找可用的连续内存
90 static void *SramFindHeap(int size)
91 {
92 char *mem;
93 int seriesSize = 0; //已查找到连续用的内存
94 BlockLink_t *pTempBlockLink; //头节点
95 pTempBlockLink = (BlockLink_t *)HeapHead;
96 //从低向高查找可用的内存
97 while(pTempBlockLink)
98 {
99 //如果是未使用的内存
100 if(pTempBlockLink->empty)
101 {
102 seriesSize += HeapBlockSIZE;
103 }
104 else
105 {
106 seriesSize = 0;
107 }
108 //如果查找到连续未使用的内存
109 if(seriesSize >= size)
110 {
111 //返回内存堆开始地址
112 pTempBlockLink->heapLen = seriesSize; //设置分配堆长度
113 mem = pTempBlockLink->pV;
114
115 //将内存标记为 已使用
116 while(seriesSize && pTempBlockLink)
117 {
118 seriesSize -= HeapBlockSIZE;
119 pTempBlockLink->empty = 0;
120 pTempBlockLink = pTempBlockLink->pxPrevFreeBlock;
121 }
122 return mem;
123 }
124 //切换下一节点
125 pTempBlockLink = pTempBlockLink->pxNextFreeBlock;
126 }
127 return NULL;
128 }
129
130 //内存碎片整理
131 static void SramMerge(void)
132 {
133
134 }
135
136 void *SramMalloc(size_t xWantedSize)
137 {
138 char *mem;
139
140 if(! HeapHead)
141 {
142 InitHeap();
143 }
144 //地址对齐
145
146 mem = SramFindHeap(xWantedSize);
147 if(mem)
148 {
149 return mem;
150 }
151 //如果没有查找到 整理内存碎片
152 SramMerge();
153
154 //仍然分配不成功 返回错误
155 mem = SramFindHeap(xWantedSize);
156 if(mem)
157 {
158 return mem;
159 }
160 return NULL;
161 }
162
163 void SramFree( void *pv )
164 {
165 int heapLen = 0;
166 //释放内存 从堆的高位开始向低位查找
167 BlockLink_t *pTempHeap = FindHeap(pv);
168 heapLen = pTempHeap->heapLen;
169 while(heapLen && pTempHeap)
170 {
171 //设为空闲状态
172 pTempHeap->empty = 1;
173 pTempHeap->heapLen = 0;
174 //查找上个节点
175 pTempHeap = pTempHeap->pxPrevFreeBlock;
176 heapLen -= HeapBlockSIZE;
177 }
178 }