【C】简单的malloc和free的实现

usr

这里简单实现了cstdlib的动态内存管理函数malloc、calloc、realloc和free
大致原理是先申请一个数组作为内存空间，然后使用链表连接每个申请的内存块。如果要释放内存，就从链表中移除相应的内存块。
在没有动态内存管理的环境中，以下代码能派上用场替代malloc函数等。
使用前需要先调用mpkInitMemory函数。
这是头文件：

1. 
   
2. #ifndef _MEMPKG_H_
   
3. #define _MEMPKG_H_
   
4. 
   
5. #include <stddef.h> /* Using type size_t. */
   
6. 
   
7. typedef unsigned char UCHART, * PUCHAR;
   
8. 
   
9. typedef struct st_BLOCK_HEADER
   
10. {
    
11.         struct st_BLOCK_HEADER * pnext;
    
12.         PUCHAR pblock;
    
13.         size_t size;
    
14. } BLOCK_HEADER, * P_BLOCK_HEADER;
    
15. 
    
16. #define MEM_SIZ (8192) /* Alter this macro to control the size of a heap. */
    
17. 
    
18. void   mpkInitMemory(void);
    
19. void * memcpy       (void *       dst, void *       src, size_t size);
    
20. void * memset       (void *       s,   int          c,   size_t n);
    
21. void * malloc       (size_t       size);
    
22. void   free         (void *       ptr);
    
23. void * realloc      (void *       ptr, size_t       size);
    
24. void * calloc       (size_t       n,   size_t       size);
    
25. int    memcmp       (const void * s1,  const void * s2,  size_t n);
    
26. 
    
27. #define memmove(dst, src, size) memcpy(dst, src, size)
    
28. 
    
29. #endif
    

复制代码

源文件：

1. 
   
2. #include "mempkg.h"
   
3. 
   
4. UCHART volatile array[MEM_SIZ]; /* Create a linear address space. */
   
5. 
   
6. const PUCHAR volatile pmem = array;
   
7. 
   
8. volatile P_BLOCK_HEADER phead = NULL; /* This is the header pointer of block chain. */
   
9. 
   
10. /* Invoke this function before you use any function of this package.
    
11. */
    
12. void mpkInitMemory(void)
    
13. {
    
14.         phead = (P_BLOCK_HEADER)pmem;
    
15.         phead->pblock = pmem + sizeof(BLOCK_HEADER);
    
16.         phead->pnext = (P_BLOCK_HEADER)(pmem + MEM_SIZ - sizeof(BLOCK_HEADER));
    
17.         phead->size = 0;
    
18.         phead->pnext->pblock = pmem + MEM_SIZ;
    
19.         phead->pnext->pnext = NULL;
    
20.         phead->pnext->size = 0;
    
21. }
    
22. 
    
23. void * memcpy(void * dst, void * src, size_t size)
    
24. {
    
25.         char * sc1;
    
26.         const char * sc2;
    
27.         sc1 = dst;
    
28.         sc2 = src;
    
29.         if (sc2 < sc1 && sc1 < sc2 + size)
    
30.                 for (sc1 += size, sc2 += size; 0 < size; --size)
    
31.                         *--sc1 = *--sc2;
    
32.         else
    
33.                 for (; 0 < size; --size)
    
34.                         *sc1++ = *sc2++;
    
35.         return dst;
    
36. }
    
37. 
    
38. void * memset(void * s, int c, size_t n)
    
39. {
    
40.         const UCHART uc = c;
    
41.         unsigned char * su;
    
42.         for (su = s; 0 < n; ++su, --n)
    
43.                 *su = uc;
    
44.         return s;
    
45. }
    
46. 
    
47. void * malloc(size_t size)
    
48. {
    
49.         if (size > 0)
    
50.         {
    
51.                 P_BLOCK_HEADER pnode, pnew;
    
52.                 for (pnode = phead; NULL != pnode; pnode = pnode->pnext)
    
53.                 {
    
54.                         if (pnode->pnext != NULL)
    
55.                         {        /* Test available space for the new block. */
    
56.                                 if (pnode->pnext->pblock - sizeof(BLOCK_HEADER) - pnode->pblock - pnode->size >=
    
57.                                         size + sizeof(BLOCK_HEADER))
    
58.                                 {
    
59.                                         pnew = (P_BLOCK_HEADER)(pnode->pblock + pnode->size);
    
60.                                         /* Initialize the new block header and assign new block. */
    
61.                                         pnew->pblock = pnode->pblock + pnode->size + sizeof(BLOCK_HEADER);
    
62.                                         pnew->size = size;
    
63.                                         pnew->pnext = pnode->pnext;
    
64.                                         pnode->pnext = pnew;
    
65.                                         return pnew->pblock;
    
66.                                 }
    
67.                         }
    
68.                         else
    
69.                                 break;
    
70.                 }
    
71.         }
    
72.         return NULL;
    
73. }
    
74. 
    
75. void free(void * ptr)
    
76. {        /* Preserve the tail and header block structure. */
    
77.         if (pmem == ptr || pmem + MEM_SIZ == ptr)
    
78.                 return;
    
79.         if (NULL != ptr)
    
80.         {
    
81.                 P_BLOCK_HEADER pnode;
    
82.                 for (pnode = phead; NULL != pnode; pnode = pnode->pnext)
    
83.                 {
    
84.                         if (NULL != pnode->pnext && ptr == pnode->pnext->pblock)
    
85.                         {
    
86.                                 pnode->pnext = pnode->pnext->pnext;
    
87.                                 return;
    
88.                         }
    
89.                 }
    
90.         }
    
91.         return;
    
92. }
    
93. 
    
94. void * realloc(void * ptr, size_t size)
    
95. {        /* Preserve the tail and header block structure. */
    
96.         if (pmem == ptr || pmem + MEM_SIZ == ptr)
    
97.                 return NULL;
    
98.         if (NULL == ptr && size > 0)
    
99.                 return malloc(size);
    
100.         else if (size > 0)
     
101.         {
     
102.                 P_BLOCK_HEADER pnode;
     
103.                 for (pnode = phead; NULL != pnode; pnode = pnode->pnext)
     
104.                 {
     
105.                         if (NULL != pnode->pnext && ptr == pnode->pnext->pblock)
     
106.                         {
     
107.                                 if (size == pnode->pnext->size)
     
108.                                         return ptr;
     
109.                                 else if (pnode->pnext->pnext->pblock - sizeof(BLOCK_HEADER) - pnode->pblock - pnode->size >=
     
110.                                         size + sizeof(BLOCK_HEADER))
     
111.                                 {
     
112.                                         pnode->pnext->size = size;
     
113.                                         return ptr;
     
114.                                 }
     
115.                                 else
     
116.                                 {
     
117.                                         void * newptr = malloc(size);
     
118.                                         if (NULL != newptr)
     
119.                                         {
     
120.                                                 memcpy(newptr, ptr, pnode->pnext->size);
     
121.                                                 free(ptr);
     
122.                                         }
     
123.                                         return newptr;
     
124.                                 }
     
125.                         }
     
126.                 }
     
127.         }
     
128.         return NULL;
     
129. }
     
130. 
     
131. void * calloc(size_t n, size_t size)
     
132. {
     
133.         void * rtn = malloc(size * n);
     
134.         memset(rtn, 0, size * n);
     
135.         return rtn;
     
136. }
     
137. 
     
138. int memcmp(const void * s1, const void * s2, size_t n)
     
139. {
     
140.         PUCHAR su1, su2;
     
141.         for (su1 = s1, su2 = s2; 0 < n; ++su1, ++su2, --n)
     
142.                 if (*su1 != *su2)
     
143.                         return *su1 < *su2 ? -1 : 1;
     
144.         return 0;
     
145. }
     

复制代码

0xAA55

一种裸机上管理内存的感觉，让我想到了在DOS年代，捅穿A20地址线，然后写16 MB内存的一些DOS游戏。

但，像STM32这样的单片机上，然后像STM32CubeIDE这样的开发环境提供的malloc其实是静态分配地址，就像一个宏，它给你局部起了一个static char mem[size];然后这块内存妥妥地进入了链接器脚本的.bss段。对应的，单片机上的free是没有任何行为的。

另外，现在的桌面机或者服务器环境，我为了实现高频的内存分配释放的效果，写过内存池，然后感觉一个比较大的难点是如何实现多线程环境下，能尽可能不锁住线程，实现高效的内存分配释放。

usr

这段代码还有个缺点就是容易形成内存碎片，本来想实现一个伙伴系统的无奈功夫不到家没有实现成功。
在多线程环境下这段代码必须加锁，不然内存会被写乱。
另外，楼上可以参考一下glibc的malloc来获得灵感。