10

我想制作自己的 malloc/free，这样我就可以制作一个精确的复制分配器。

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

我现在有几个问题：

  1. 我应该只 malloc 大块内存，然后从中分发，这样我就不必调用系统调用了吗？
  2. 抄袭收藏家通常是怎么做的？我想这部分要有效地完成有点复杂。我幼稚的实现只会 malloc 一个块，剩余对象的大小需要 2 倍的空间。
4

3 回答 3

20

关于实现 malloc 和类似的东西有很多很好的文献。但我注意到你在这里包含了 C++——你知道你可以编写自己的 C++ 实现new吗delete？作为一种轻松完成它的方法，这可能很有用。

在任何情况下，您想要的特征将在很大程度上取决于您的工作量，即随着时间的推移使用模式。如果你只有 mallocs 和 new frees，显然很容易。如果您只有一种或几种不同块大小的 malloc，那也很简单。

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

malloc 的基本实现只是分配一个包含数据长度、“使用中标志”和 malloc 内存的标头。Malloc 然后在其空间的末尾构造一个新的标头，分配内存，并返回一个指针。当您释放时，它只会重置正在使用的标志。

诀窍是，当您执行大量 mallooc 和 free 操作时，您可以快速获得大量未使用但难以分配的小 blob。所以你需要某种凹凸 gc 来合并内存块。

您可以进行更复杂的 gc，但请记住这需要时间；你不想一个空闲占用很多时间。

有一篇关于 Solaris malloc 实现的好论文，您可能会觉得有趣。这是另一个关于在 Solaris 中构建替代 malloc的内容，但基本内容是相同的。你应该阅读关于垃圾收集的维基百科文章，并按照它来阅读一些更正式的论文。

更新

你知道，你真的应该看看分代垃圾收集器。基本思想是，分配的时间越长，分配的可能性就越大。这是您提到的“复制”GC的扩展。基本上，你在内存池的一部分中分配新的东西，称之为 g0。当你达到高水位线时，你查看分配的块并将仍在使用的块复制到内存的另一部分，称为 g1，然后你可以清除 g0 空间并开始在那里分配。最终 g1 达到了它的高水位线，你通过清除 g0 来修复它，并清理 g1 将东西移动到 g0，当你完成后，你将旧的 g1 重命名为 g0，反之亦然并继续。

诀窍在于，尤其是在 C 语言中，您分配给 malloc 内存的句柄是直接的原始指针；如果没有一些大药，你就无法真正移动东西。

第二次更新

在评论中，@unknown 询问“移动的东西不会只是一个 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++ 中，使用用户定义的类指针类型，您可以解决这个问题。

于 2009-04-09T03:11:15.400 回答
1

了解更多关于您正在尝试做的事情会很有帮助。这是针对单一类型的吗？还是一组相对统一的类型？

  • 如果您需要加速给定类型的分配，内存池是一种久经考验的技术（一个可能的缺点是您可能会在内存中跳跃，影响缓存性能）
  • 应用程序范围的分配技术通常包括将所有分配四舍五入到配置文件驱动的存储桶大小，以便减少碎片。
  • 多线程应用程序通常具有可以分配的每个线程池，而不会冒与其他线程争用的风险

tcmalloc 的文档非常擅长描述这些技术的当前状态。

这里没有太多复杂的东西，但你可能正在重新发明轮子。有一些开源库可以做到这一点。

于 2009-04-09T03:54:13.317 回答
0

不要使用想法 #1，您将浪费大量资源，这些资源可能在应用程序的整个执行过程中可能仍未使用，同时阻止其他进程使用它（取决于您计划占用多少）。

于 2009-04-09T03:13:48.873 回答