我想制作自己的Malloc

我想制作自己的malloc/free,这样我就可以制作精确的复制分配器.

任何大师都有任何提示和建议吗？

我现在有几个问题:

我应该只是malloc大块的内存,然后从那里分发,所以我不必调用系统调用？

复制收藏家通常如何完成？我想这个部分有效地做起来有点复杂.我天真的实现只是将一个块大小地移动到剩余对象的大小,这需要2倍的空间.

Charlie Mart.. 20

关于实现malloc和类似的东西,有很多很好的文献.但我注意到,你包括C++在这里-你知道,你可以写自己的实现new,并delete在C++？这可能很有用,可以轻松实现.

在任何情况下,您想要的特性将在很大程度上取决于您的工作负载,即随着时间的推移而使用的模式.如果你只有mallocs和new frees,很明显很简单.如果你只有一个或几个不同的块大小的malloc,那也很简单.

在其他语言中,您可以通过将内存链接在一起来获得一些优势,但C并不那么聪明.

malloc的基本实现只是分配一个包含数据长度的头,一个"使用中的标志"和一个malloced内存.然后,Malloc在其空间的末尾构造一个新的头,分配内存,并返回一个指针.当你空闲时,它只会重置使用中的标志.

诀窍在于,当你做了大量的mallooc和free时,你可以快速获得许多未使用的小blob,但很难分配.所以你需要某种bumpo gc来合并内存块.

你可以做一个更复杂的gc,但要记住这需要时间; 你不想自由地占用很多时间.

有一篇关于Solaris malloc实现的文章,你可能会感兴趣.这是另一个关于构建替代malloc的问题,同样在Solaris中,但基础是相同的.你应该阅读关于垃圾收集的维基百科文章,并将其关注到一些更正式的论文.

更新

你知道,你真的应该看看世代垃圾收集器.其基本思路是,较长的东西保持分配,越有可能是它保持分配.这是你提到的"复制"GC的扩展.基本上,你在内存池的一个部分分配新东西,称之为g0.当你达到高水位标记时,你会查看已分配的块并将仍在使用的块复制到另一段内存中,将其称为g1,然后你可以清除g0空间并开始在那里分配.最终g1达到高水位,你通过清除g0来修复它,并清理g1移动到g0的东西,当你完成后,你将旧的g1重命名为g0,反之亦然并继续.

诀窍在于,特别是在C语言中,你传递给malloc内存的句柄是直接的原始指针; 如果没有一些大药,你就无法真正改变现状.

第二次更新

在评论中,@ badn提出"不会移动的东西只是一个memcpy()".事实上它会.但请考虑此时间表:

警告:这是不完整的,未经测试,仅用于说明,仅用于娱乐,不保证明示或暗示

/* basic environment for illustration*/
void * myMemoryHdl ;
unsigned char lotsOfMemory[LOTS]; /* this will be your memory pool*/ 

你想要一些记忆

/* if we get past this, it succeded */
if((myMemoryHdl = newMalloc(SIZE)) == NULL)
    exit(-1);

在malloc的实现中,创建内存并返回指向缓冲区的指针.

unsigned char * nextUnusued = &lotsOfMemory[0];
int partitionSize = (int)(LOTS/2);
int hwm = (int) (partition/2);
/* So g0 will be the bottom half and g1 the top half to start */
unsigned char * g0 = &lotsOfMemory[0];
unsigned char * g1 = &lotsOfMemory[partitionSize];


void * newMalloc(size_t size){
   void * rtn ;
   if( /* memory COMPLETELY exhausted */)
      return NULL;
   /* otherwise */
   /* add header at nextUnused */
   newHeader(nextUnused);     /* includes some pointers for chaining
                               * and a field with values USED or FREE, 
                               * set to USED */
   nextUnused += HEADERLEN ;  /* this could be niftier */
   rtn = nextUnused ;
   nextUnused += size ;
}

有些东西被释放了

  newFree(void * aHandle){
     *(aHandle-offset) = FREE ; /* set the flag in the header, 
                                 * using an offset. */
  }

所以现在你做了所有的事情,你就达到了高水位.

 for( /* each block in your memory pool */ )
    if( /* block header is still marked USED */ ) {
        memcpy(/* block into other partition */);
    }
 /* clear the partition */
 bzero(g0, partitionSize);

现在,返回到myMemHdl中保存的原始句柄.它指向什么？(答案,你只需用bzero(3)将其设置为0x00.)

这就是魔法的来源.至少在C中,你从malloc返回的指针不再受你的控制 - 你不能在事后移动它.在C++中,使用用户定义的类指针类型,您可以解决这个问题.

关于实现malloc和类似的东西,有很多很好的文献.但我注意到,你包括C++在这里-你知道,你可以写自己的实现new,并delete在C++？这可能很有用,可以轻松实现.

在任何情况下,您想要的特性将在很大程度上取决于您的工作负载,即随着时间的推移而使用的模式.如果你只有mallocs和new frees,很明显很简单.如果你只有一个或几个不同的块大小的malloc,那也很简单.

在其他语言中,您可以通过将内存链接在一起来获得一些优势,但C并不那么聪明.

malloc的基本实现只是分配一个包含数据长度的头,一个"使用中的标志"和一个malloced内存.然后,Malloc在其空间的末尾构造一个新的头,分配内存,并返回一个指针.当你空闲时,它只会重置使用中的标志.

诀窍在于,当你做了大量的mallooc和free时,你可以快速获得许多未使用的小blob,但很难分配.所以你需要某种bumpo gc来合并内存块.

你可以做一个更复杂的gc,但要记住这需要时间; 你不想自由地占用很多时间.

有一篇关于Solaris malloc实现的文章,你可能会感兴趣.这是另一个关于构建替代malloc的问题,同样在Solaris中,但基础是相同的.你应该阅读关于垃圾收集的维基百科文章,并将其关注到一些更正式的论文.

更新

你知道,你真的应该看看世代垃圾收集器.其基本思路是,较长的东西保持分配,越有可能是它保持分配.这是你提到的"复制"GC的扩展.基本上,你在内存池的一个部分分配新东西,称之为g0.当你达到高水位标记时,你会查看已分配的块并将仍在使用的块复制到另一段内存中,将其称为g1,然后你可以清除g0空间并开始在那里分配.最终g1达到高水位,你通过清除g0来修复它,并清理g1移动到g0的东西,当你完成后,你将旧的g1重命名为g0,反之亦然并继续.

诀窍在于,特别是在C语言中,你传递给malloc内存的句柄是直接的原始指针; 如果没有一些大药,你就无法真正改变现状.

第二次更新

在评论中,@ badn提出"不会移动的东西只是一个memcpy()".事实上它会.但请考虑此时间表:

警告:这是不完整的,未经测试,仅用于说明,仅用于娱乐,不保证明示或暗示

/* basic environment for illustration*/
void * myMemoryHdl ;
unsigned char lotsOfMemory[LOTS]; /* this will be your memory pool*/ 

你想要一些记忆

/* if we get past this, it succeded */
if((myMemoryHdl = newMalloc(SIZE)) == NULL)
    exit(-1);

在malloc的实现中,创建内存并返回指向缓冲区的指针.

unsigned char * nextUnusued = &lotsOfMemory[0];
int partitionSize = (int)(LOTS/2);
int hwm = (int) (partition/2);
/* So g0 will be the bottom half and g1 the top half to start */
unsigned char * g0 = &lotsOfMemory[0];
unsigned char * g1 = &lotsOfMemory[partitionSize];


void * newMalloc(size_t size){
   void * rtn ;
   if( /* memory COMPLETELY exhausted */)
      return NULL;
   /* otherwise */
   /* add header at nextUnused */
   newHeader(nextUnused);     /* includes some pointers for chaining
                               * and a field with values USED or FREE, 
                               * set to USED */
   nextUnused += HEADERLEN ;  /* this could be niftier */
   rtn = nextUnused ;
   nextUnused += size ;
}

有些东西被释放了

  newFree(void * aHandle){
     *(aHandle-offset) = FREE ; /* set the flag in the header, 
                                 * using an offset. */
  }

所以现在你做了所有的事情,你就达到了高水位.

 for( /* each block in your memory pool */ )
    if( /* block header is still marked USED */ ) {
        memcpy(/* block into other partition */);
    }
 /* clear the partition */
 bzero(g0, partitionSize);

现在,返回到myMemHdl中保存的原始句柄.它指向什么？(答案,你只需用bzero(3)将其设置为0x00.)

这就是魔法的来源.至少在C中,你从malloc返回的指针不再受你的控制 - 你不能在事后移动它.在C++中,使用用户定义的类指针类型,您可以解决这个问题.