模拟实现c语言中的动态内存分配malloc函数 - 推酷
模拟实现c语言中的动态内存分配malloc函数
动态存储器分配器维护着一个进程的虚拟的存储器区域，称为堆（heap）。分配器将堆视为一组不同大小的块的集合来维护。每个块就是一个连续的虚拟存储器片（chunk），要么是已经分配的，要么是空闲的。
我们这里把内存堆空间模拟为一个字节数组buf［1000］，块的数据结构为：
typedef struct HeadStruct{
&&&& size_
&&&& void *
&&&& struct HeadStruct *pre,*
堆的组织方式为双向链表。要实现malloc函数，就必须考虑几个问题：
1 空闲块的组织：我们如何记录空闲块
2 放置：我们如何选择一个合适的空闲块来放置一个新分配的块
3 分割：在我们将一个新分配的块放置在某一个空闲块之后，如何处理这个空闲块的剩余部分
4 合并：我们如何处理一个刚刚被释放的块
程序实现如下：
#include &stdio.h&
#include &stdlib.h&
#define HeadSize (sizeof(HeadStruct))
char buf[1000];//模拟内存堆
typedef struct HeadStruct{
size_//块的大小
void *//有效的载荷
struct HeadStruct *pre,*//前驱和后继，用双向链表实现堆
//表明此块空闲与否
}HeadS//堆中块的结构体
void Init_heap()
HeadStruct *p=(HeadStruct *)
p-&size=sizeof(buf)-HeadS
p-&buf=(char *)p + HeadS//p should be cast to char*
p-&pre=p-&next=NULL;
p-&used=0;
void list_blocks()
HeadStruct *p=(HeadStruct *)
printf(&addr:%d,size:%d,used:%d\n&,(char *)(p-&buf)-buf,p-&size,p-&used);
void *myalloc(size_t size)
HeadStruct *p=(HeadStruct *)
while(!((p!=NULL)&&(p-&size-size&HeadSize)&&(p-&used==0)))
if(p==NULL)
printf(&ERROR!&);
return NULL;
HeadStruct *rest=(HeadStruct *)((char *)(p-&buf)+size);
rest-&buf=(char *)rest+HeadS
rest-&size=p-&size-size-HeadS
rest-&next=p-&
if(p-&next)
p-&next-&pre=
rest-&pre=p;
rest-&used=0;
p-&used=1;
return p-&
void myFree(void *mem)
HeadStruct *actual=(HeadStruct *)((char *)mem-HeadSize);
//堆增长的方式是向高地址增长，要找到块的首地址就的减去块头的大小
if(!mem || 0==actual-&used)
printf(&FREE ERROR!&);
actual-&used=0;
HeadStruct *
if(actual-&next && actual-&next-&used==0)
actual-&size+=actual-&next-&size+HeadS
tmp=actual-&next-&
actual-&next=
if(actual-&pre && actual-&pre-&used==0)
actual-&pre-&size+=actual-&size+HeadS
actual-&pre-&next=actual-&
if(actual-&next)
actual-&next-&pre=actual-&
int main()
Init_heap();
list_blocks();
int *a=(int *)myalloc(sizeof(int)*100);
list_blocks();
char *b=(char *)myalloc(sizeof(char)*100);
list_blocks();
myFree(a);
myFree(b);
list_blocks();
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致使用一个快速固定块的内存分配器来替换 malloc/free - 开源中国社区
使用一个快速固定块的内存分配器来替换 malloc/free
英文原文：
IntroductionCustom fixed block allocators are specialized memory managers used to solve performance problems with the global heap. In the article "", I implemented an allocator class&to improve speed and eliminate the possibility of a fragmented heap memory fault. In this latest article, the Allocator class is used as a basis for the xallocator implementation to replace malloc() and free().Unlike most fixed block allocators, the xallocator implementation is capable of running in a completely dynamic fashion without advance knowledge of block sizes or block quantity. The allocator takes care of all the fixed block management for you. It is completely portable to any PC-based or embedded system. In addition, it offers insight into your dynamic usage with memory statistics.&
自定义的固定区域（块）分配器是一个特别的内存管理策略专门用来解决全局堆栈的性能问题。 在 ""这篇文章中, 我实现了一个可以减少碎片堆栈错误可能性的快速分配器类。那篇文章中的分配器类将会作为今天的主角——X-分配器的基石，替换系统的malloc()和free()函数。
和大部分固定块分配器不同的是，X-分配器可以在预先不知道块大小和数量的前提下，以完全动态的方式运行。X-分配器也会为你提供所有的固定块管理方式。完美运行在任何PC或嵌入式设备上。此外，它还提供了内存的动态使用图可用于内存使用情况的统计。
In this article, I replace the C library malloc/free with alternative fixed memory block versions xmalloc() and xfree(). First, I'll briefly explain the underlying Allocator storage recycling method, then present how xallocator works.&Storage RecyclingThe basic philosophy of the memory management scheme is to recycle memory obtained during object allocations. Once storage for an object has been created, it's never returned to the heap. Instead, the memory is recycled, allowing another object of the same type to reuse the space. I've implemented a class called Allocator that expresses the technique. &
在这边文章中，我使用可选择的固定内存块版本的xmalloc()和xfree来代替对应的C标准库mallc和free函数。首先，我简要解释下面的Allocator存储回收方法，接着介绍xallocator是如何工作的。
基本的内存管理方案是回收在对象被分配期间获得地内存。一旦对象存储创建完成，它永远不会返回推中。相反，内存被回收，允许其他相同类型的对象重用此空间。我已经实现了一个叫做Allocator的类来解释这个技术。
When the application deletes using Allocator, the memory block for a single object is freed for use again but is not actually released back to the memory manager. Freed blocks are retained in a linked list, called the free-list, to be doled out again for another object of the same type. On every allocation request, Allocator first checks the free-list for an existing memory block. Only if none are available is a new one created. Depending on the desired behavior of Allocator, storage comes from either the global heap or a static memory pool with one of three operating modes.&Heap blocksHeap poolStatic poolHeap vs. PoolThe Allocator class is capable of creating new blocks from the heap or a memory pool whenever the free-list cannot provide an existing one. If the pool is used, you must specify the number of objects up front. Using the total objects, a pool large enough to handle the maximum number of instances is created. Obtaining block memory from the heap, on the other hand, has no such quantity limitations – construct as many new objects as storage permits.&
当应用程序使用Allocator删除块之后，此对象的内存块被释放以便重用，但并不是直接释放到内存管理器。返回的内存块被保存至一个链表，我们叫它可用链表。此表可继续提供给其他相同类型对象使用。收到分配请求时，Allocator 先检查此可用链表中是否存在可用块。只有当链表中没有可用的块才创建新的块。取决于的Allocator期望的行为，存储可来自全局堆，也可来自于具有以下三种操作模式的静态内存池。
& & & & 1.堆块
& & & & 2.堆池
&&&&& & 3.静态池堆VS 池
当可用链表不能提供相应块时，Allocator类可以从堆或者内存池创建一个新块。如果使用池，你必须预先指定创建对象的数目。 然后使用这些对象，一个足够大的可以处理最大数目实例的池即可创建。另一方面，从堆创建内存块并没有这方面的数量限制，只要存储允许，我们可创建尽可能多的对象。
The heap blocks mode allocates from the global heap a new memory block for a single object as necessary to fulfill memory requests. A deallocation puts the block into a free-list for later reuse. Creating fresh new blocks off the heap when the free-list is empty frees you from having to set an object limit. This approach offers dynamic-like operation since the number of blocks can expand at run-time. The disadvantage is a loss of deterministic execution during block creation.&The heap pool mode creates a single pool from the global heap to hold all blocks. The pool is created using operator new when the Allocator object is constructed. Allocator then provides blocks of memory from the pool during allocations.&
堆块模式尽可能的从全局堆中分配一个新内存块给对象，来实现内存分配请求。而释放的时候，内存块被放置在一个可用链表以便后续重用。如果可用链表为空，则创建从堆产生的新内存块，使你摆脱对象数的限制。这个方法提供了动态的操作方式，因为内存块数可以在运行时扩展。其缺点是在内存块创建期带来的确定性执行损失。
堆池模式从全局堆创建一个单一的池来持有所有的块。 Allocator对象被创建之后，使用操作符new来创建这个池。从此，Alloctor可以从此池中提供内存块来完成分配。
The static pool mode uses a single memory pool, typically located in static memory, to hold all blocks. The static memory pool is not created by Allocator but instead is provided by the user of the class.&The heap pool and static pool modes offers consistent allocation execution times because the memory manager is never involved with obtaining individual blocks. This makes a new operation very fast and deterministic.The Allocator constructor controls the mode of operation.&class&Allocator
&&&&Allocator(size_t&size,&UINT&objects=0,&CHAR*&memory=NULL,&const&CHAR*&name=NULL);
...Refer to ""&for more information on Allocator.
静态池模式使用单个内存池来持有所有块。这个内存池基本上在静态内存池中。这个池不是由Allocator创建的，而是由类的使用者提供的。
堆池和静态池模式都提供一致的分配执行时间，因为内存管理器从不涉及到对单个内存块的获取。这使得新的操作快速而具有确定性。
Allocator构造函数控制者操作模式。class&Allocator
&&&&Allocator(size_t&size,&UINT&objects=0,&CHAR*&memory=NULL,&const&CHAR*&name=NULL);
参考""获取更多关于Allocator信息。
xallocatorThe xallocator module has six main APIs.xmallocxfreexreallocxalloc_statsxalloc_initxalloc_destroyxmalloc() is equivalent to malloc() and used in exactly the same way. Given a number of bytes, the function returns a pointer to a block of memory the size requested.void*&memory1&=&xmalloc(100);The memory block is at least as large as the user request, but could actually be more due to the fixed block allocator implementation. The additional over allocated memory is called slack but with fine-tuning block size, the waste is minimized, as I'll explain later in the article.&
xallocator模块有6个主要的API.
xalloc_stats
xalloc_init
xalloc_destroy
xmalloc等同于malloc，使用方法也与malloc相同。给定byte数，函数返回一个指向我们所请求的内存块大小的指针。void*&memory1=xmalloc(100);
这个内存块至少和用户请求的一样大，但是因为固定内存块分配实现的原因，实际上会大一些。这个额外分配内存被称为“宽松”，此“宽松”经过了微调块大小，以便浪费最小化。稍后文中我会解释。
xfree() is the CRT equivalent of free(). Just pass xfree() a pointer to a previously allocated xmalloc() block to free the memory for reuse.&xfree(memory1);xrealloc() behaves the same as realloc() in that it expands or contracts the memory block while preserving the memory block contents.&char*&memory2&=&(char*)xmalloc(24);&&&&
strcpy(memory2,&"TEST&STRING");
memory2&=&(char*)xrealloc(memory2,&124);
xfree(memory2);xalloc_stats() outputs allocator usage statistics to the standard output stream. The output provides insight into how many Allocator&instances are being used, blocks in use, block sizes, and more.&xalloc_init() must be called one time before any worker threads start, or in the case of an embedded system, before the OS starts. On a C++ application, this function is called automatically for you. However, it is desirable to call xalloc_init() manually is some cases, typically on an embedded system to avoid the small memory overhead involved with the automatic xalloc_init()/xalloc_destroy() call mechanism.&
&xfree()等同于free()函数，只需给xfree传入之前通过xmalloc分配得到的指针来释放此内存。
xfree(memory1)；
xrealloc()和realloc操作类似，用于扩展或者收缩内存块的同时保留内存块的内容。char*&memory2&=&(char*)xmalloc(24);&&&&
strcpy(memory2,&"TEST&STRING");
memory2&=&(char*)xrealloc(memory2,&124);
xfree(memory2);
xalloc_stats 把分配器使用情况统计输出到标准输出流，通过它可以窥探到内部有多少实例/块在使用，块大小，甚至更多。
在任何工作线程开始或嵌入式系统开始之前，xalloc_init必须被调用一次。在C++程序中，此函数会被自动调用。然而，某些情况下，特别是在嵌入式系统中，手动调用此函数更可取，从而避开此小内存开销涉及到自动调用xalloc_init()/xalloc_destory()机制。
xalloc_destroy() is called when the application exits to clean up any dynamically allocated resources. On a C++ application, this function is called automatically when the application terminates. You must never call xalloc_destroy() manually except in programs that use xallocator only within C files.Now, when to call&xalloc_init() and xalloc_destroy()&within a C++ application is not so easy. The problem arises with static objects. If xalloc_destroy() is called too early, xallocator may still be needed when a static object destructor get called at program exit. Take for instance this class:class&MyClassStatic
&&&&MyClassStatic()&
&&&&&&&&memory&=&xmalloc(100);&
&&&&~MyClassStatic()&
&&&&&&&&xfree(memory);&
&&&&void*&
};Now create a static instance of this class at file scope.static&MyClassStatic&myClassSSince the object is static, the MyClassStatic constructor will be called before main(), which is okay as I’ll explain in the “Porting issues” section below. However, the destructor is called after main() exits which is not okay if not handled correctly. The problem becomes how to determine when to destroy the xallocator dynamically allocated resources. If xalloc_destroy() is called before main() exits, xallocator will already be destroyed when ~MyClassStatic() tries to call xfree() causing a bug.&
当应用程序退出，任何动态分配的资源都将被通过xalloc_destroy()调用来清理。这个函数在C++程序终止时被自动调用。你千万别手动调用它，除非在C文件中使用了xallocator函数。
现在在C++程序中，几时调用xalloc_init()和xalloc_destroy()可不是见容易的事。这里引入了静态对象问题。如果xalloc_destory函数过早被调用，而当程序退出时静态对象析构函数被调用到，此时可能还需要xallocator.如下例子：class&MyClassStatic
&&&&MyClassStatic()&
&&&&&&&&memory&=&xmalloc(100);&
&&&&~MyClassStatic()&
&&&&&&&&xfree(memory);&
&&&&void*&
};文件范围内创建此类的一个静态实例。static&MyClassStatic&myClassS既然这个对象是静态的，MyClassStatic 构造函数会在main函数之前被调用。这是没有问题的，在下文的“移植问题”中将作解释。但是，析构函数在main退出之后被调用，如果处理不当，就产生问题。问题在于如何确定何时销毁xallocator动态分配的资源。如果在main函数退出之前调用xalloc_destroy ,则xallocator已经被销毁，而当&~MyClassStatic()尝试调用xfree函数时就会带来bug.
The key to the solution&comes from a guarantee in the C++ Standard:Quote:“Objects with static storage duration defined in namespace scope in the same translation unit and dynamically initialized shall be initialized in the order in which their definition appears in the translation unit.”In other words, static object constructors are called in the same order as defined within the file (translation unit). The destruction will reverse that order. Therefore, xallocator.h defines a XallocInitDestroy class and creates a static instance of it.&class&XallocInitDestroy
&&&&XallocInitDestroy();
&&&&~XallocInitDestroy();
&&&&static&INT&refC
static&XallocInitDestroy&xallocInitD
这个解决方案的关键在于C++标准的保障：
“在同一个翻译单元内，定义于命名空间范围并具有静态存储期的动态初始化对象应该按照他们在翻译单元中的定义顺序去完成初始化。””
也就是说，静态对象构造函数调用顺序和他们在文件中的定义顺序一致（翻译单元）。析构函数则以相反的顺序调用。因此，xallocator.h定义了XallocInitDestory类并创建一个静态实例。class&XallocInitDestroy
&&&&XallocInitDestroy();
&&&&~XallocInitDestroy();
&&&&static&INT&refC
static&XallocInitDestroy&xallocInitD
The constructor keeps track of the total number of static instances created and calls xalloc_init() on the first construction.&INT&XallocInitDestroy::refCount&=&0;
XallocInitDestroy::XallocInitDestroy()&
&&&&//&Track&how&many&static&instances&of&XallocInitDestroy&are&created
&&&&if&(refCount++&==&0)
&&&&&&&&xalloc_init();
}The destructor calls xalloc_destroy() automatically when the last instance is destroyed.&XallocDestroy::~XallocDestroy()
&&&&//&Last&static&instance&to&have&destructor&called?
&&&&if&(--refCount&==&0)
&&&&&&&&xalloc_destroy();
}When including xallocator.h in a translation unit, xallocInitDestroy will be declared first since the #include comes before user code. Meaning any other static user classes relying on xallocator will be declared after #include “xallocator.h”. This guarantees that ~XallocInitDestroy() is called after all user static classes destructors are executed. Using this technique, xalloc_destroy() is safely called when the program exits without danger of having xallocator destroyed prematurely.&
构造函数记录了创建的静态实例对象数，并在首次构造时调用xalloc_init。
INT&XallocInitDestroy::refCount&=&0;
XallocInitDestroy::XallocInitDestroy()&
&&&&//&Track&how&many&static&instances&of&XallocInitDestroy&are&created
&&&&if&(refCount++&==&0)
&&&&&&&&xalloc_init();
} 在销毁最后一个实例时，析构函数自动调用xalloc_destroy()。
XallocDestroy::~XallocDestroy()
&&&&//&Last&static&instance&to&have&destructor&called?
&&&&if&(--refCount&==&0)
&&&&&&&&xalloc_destroy();
当翻译单元中包含xallocator.h时，先声明xallocInitDestroy，因为#include在用户代码之前。也就意味着，任何依赖xallocator的静态用户类声明在在#include“xallocator.h”之后。这样保证了所有用户静态类析构函数执行之后才去调用XallocInitDestroy函数。运用此技术，xalloc_destroy可在程序退出时被安全调用，而不至于带来过早销毁xallocator的风险。在内存充足时malloc函数分配内存失败的原因及解决
昨天在修改自己的代码的时候，碰到了malloc函数内存分配失败，上网翻了翻，一个很可能的原因是之前的代码出现了越界操作，导致malloc分配函数所涉及的一些信息被破坏。在这个思想的指导下，今天又是郁闷了一整天，来来回回看自己的代码。又加不断的调试，终于发现自己的代码中有一个malloc分配的内存大小为0，不是自己预想的大小，而之后的代码又按预想的大小对内存进行了操作，导致了下一个malloc无法分配内存。
总结自己的问题，如果下一次再碰到这样的问题，就要查从不能分配的那个malloc函数开始往回找最近的那个能分配的malloc，出问题的代码应该就在这部分，很可能的原因就是指针越界，对未知的内存进行了操作，导致了malloc不能继续分配内存。
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。关注51Testing
C语言动态内存分配之malloc与realloc区别
发表于： 10:10 &作者：Linux公社 & 来源：51Testing软件测试网采编
推荐标签：
　　在程序的执行期间分配内存时，内存区域中的这个空间称为堆(heap)。还有另一个内存区域，称为栈(stack)，其中的空间分配给函数的参数和本地变量。在执行完该函数后，存储参数和本地变量的内存空间就会释放。堆中的内存是由程序员控制的。在分配堆上的内存时，由程序员跟踪所分配的内存何时不再需要，并释放这些空间，以便于以后重用它们。　　使用动态内存很明显的好处就是：不需要预先分配存储空间且分配的空间可以根据程序的需要扩大或缩小，这样可以有效的使用内存空间。　　malloc和free　　C函数库中的malloc和free分别用于执行动态内存分配和释放。这两个函数的原型如下所示，他们都在头文件stdlib.h中声明。　　void *malloc ( size_t size );　　void free ( void *pointer );　　malloc的作用是在内存的动态存储区中分配一个长度为size的连续空间。其参数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。还有一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。所以在调用该函数时应该检测返回值是否为NULL，确保非空之后再使用非常重要。malloc所分配的内存是一块连续的空间。同时，malloc实际分配的内存空间可能会比你请求的多一点，但是这个行为只是由编译器定义的。malloc不知道用户所请求的内存需要存储的数据类型，所以malloc返回一个void *的指针，它可以转换为其它任何类型的指针。　　由于内存区域总是有限的，不能不限制地分配下去，而且一个程序要尽量节省资源，所以当所分配的内存区域不用时，就要释放它，以便其它的变量或者程序使用。这时我们就要用到free函数。free的参数必须要么是NULL，要么是从malloc、relloc、calloc返回的值。作用是释放之前返回的指针指向的内存空间，向free传递一个NULL参数不会产生任何效果。　　calloc和realloc与malloc的区别　　calloc和realloc的原型如下：　　void *calloc ( size_t num_elements, size_t element_size );　　void *realloc (void *ptr, size_t new_size );　　calloc和malloc 主要的区别在于前者在返回内存的指针之前将它初始化为0，另外它们请求数量的方式不同。calloc的参数包括所需元素的数量和每个元素的字节，根据这些值可以计算出总共需要分配的内存空间。　　realloc函数用于修改一个原先已经分配的内存块的大小，可以使一块内存的扩大或缩小。当起始空间的地址为空，即*ptr = NULL,则同malloc。当*ptr非空：若nuw_size & size,即缩小*ptr所指向的内存空间，该内存块尾部的部分内存被拿掉，剩余部分内存的原先内容依然保留；若nuw_size & size,即扩大*ptr所指向的内存空间，如果原先的内存尾部有足够的扩大空间，则直接在原先的内存块尾部新增内存，如果原先的内存尾部空间不足，或原先的内存块无法改变大小，realloc将重新分配另一块nuw_size大小的内存，并把原先那块内存的内容复制到新的内存块上。因此，使用realloc后就应该改用realloc返回的新指针。　　使用方法程序示例　　int *ptr =NULL;　　ptr = (int*)malloc(sizeof(int)*size);　　if (*ptr == NULL)　　{　　strerror(error);　　　　}　　上例中动态分配了size个整型存储区域。动态分配内存的步骤可细分为：分配size个整型的连续存储空间，并返回一个指向其起始地址的整型指针把此整型指针地址赋给ptr, 检测返回值是否为NULL。注意，类型转换(int*)将函数返回的地址转换成int类型的指针。这么做是因为malloc()是一般用途的函数，可为任何类型的数据分配内存。sizeof是一个运算符，它返回一个size_t类型的无符号整数，该整数是存储它的参数需要的字节数。它把关键字如int或float等作为参数，返回存储该类型的数据项所需的字节数。它的参数也可以是变量或数组名。把数组名作为参数时，sizeof返回存储整个数组所需的字节数。前一个例子请求分配足以存储size个int数据项的内存。以这种方式使用sizeof，可以根据不同的C编译器为int类型的值自动调整所需的内存空间。　　1 int *p1,*p2;　　2 &p1 = (int*)malloc(size * sizeof(int));　　3 &p2=p1;　　4 ……　　5 free(p1); &/*或者free(p2)*/　　给free函数传递其它的值很可能造成死机或其它灾难性的后果。注意：这里重要的是指针的值，而不是用来申请动态内存的指针本身。　　malloc返回值赋给p1，又把p1的值赋给p2，所以此时p1，p2都可作为free函数的参数。malloc函数是对存储区域进行分配的。 free函数是释放已经不用的内存区域的。 所以由这两个函数就可以实现对内存区域进行动态分配并进行简单的管理了。　　下面是使用动态分配的内存的基本规则：　　· 避免分配大量的小内存块。分配堆上的内存有一些系统开销，所以分配许多小的内存块比分配几个大内存块的系统开销大。　　·&仅在需要时分配内存。只要使用完堆上的内存块，就释放它。　　·&总是确保释放已分配的内存。在编写分配内存的代码时，就要确定在代码的什么地方释放内存。　　·&在释放内存之前，确保不会无意中覆盖堆上分配的内存的地址，否则程序就会出现内存泄漏。在循环中分配内存时，要特别小心。
搜索风云榜
51Testing官方微信
51Testing官方微博
测试知识全知道}