c - Kernighan和Ritchie malloc自由逻辑

Question

我花了几个小时在free()实现中的一个特定条件上。我已经搜索了网络和stackoverflow以查看是否还有其他人对此进行了讨论，但没有发现任何问题。我了解第二版(ANSI)第187和188页中介绍的3个功能背后的总体思路。我是专业人士，大多数代码对我来说都是有意义的，但是当我确定所有3个函数在第一次调用时如何工作(换句话说，将* freep初始化为某种东西)时，我感到很沮丧。

这是我从代码中得出的步骤:
步骤1.定义了两个全局变量，如下所示

typedef long Align;
union header { /* block header */
      struct {
      union header *ptr; /* next block if on free list */
      unsigned size; /* size of this block */
      } s;
      Align x; /* force alignment of blocks */
};
typedef union header Header;

   static Header base; /* empty list to get started */
   static Header *freep = NULL; /* start of free list */

步骤2:首先通过malloc()函数，因为第一次，当用户调用malloc()时，上面给出的2个全局变量将不包含任何可用数据。我已经在本节的下面附了本书中malloc()的代码。我了解“nunits”的计算方式。如果freep == NULL，则freep和prevp指向＆base。因此，使用p == prevp-> s.ptr == base.s.ptr == freep == prevp ==＆base(sic)，第一次进入for循环。下一个if条件为false，因为在第一次调用期间base.s.size已设置为零。现在，下一个if条件(p == freep)为true，因为两者都仍指向“base”的地址。因此，在这一点上，我们调用了morecore()，这将在下面的步骤3中进行描述。

/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned nunits;
    nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
    if ((prevp = freep) == NULL) { /* no free list yet */
          base.s.ptr = freeptr = prevptr = &base;
          base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
         if (p->s.size >= nunits) { /* big enough */
               if (p->s.size == nunits) /* exactly */
                     prevp->s.ptr = p->s.ptr;
               else { /* allocate tail end */
                     p->s.size -= nunits;
                     p += p->s.size;
                     p->s.size = nunits
               }
               freep = prevp;
               return (void *)(p+1);
          }
          if (p == freep) /* wrapped around free list */
               if ((p = morecore(nunits)) == NULL)
                      return NULL; /* none left */
    } // end of for loop
}

步骤3:morecore()

到目前为止，所有指针都指向＆base(全局)，并且我们输入morecore()来调用操作系统以获取可用的内存空间。然后，morecore()将此内存的开头初始化为Header结构，如下所示:

   Header *up;
   up = the memory from OS
   up->s.size =  nu; (number of units, each of size = sizeof(Header))
   free( (void*) (up+1) );
   return freep;

初始化之后，morecore()调用带有指向下一个地址的参数的free()(在初始Header结构之后)。 morecore()不会更改freep全局，它仍然指向＆base。

步骤4:输入free()。

我的问题是自由功能，所以我只在下面提供相关内容。

    void free( void* ap)
    {
         Header *bp, *p; // a pointer to base (ie. Header) and a temporary pointer p.
         bp = (Header *)ap - 1;  // point to block header
         for (p = freep;  !(bp > p && bp < p->s.ptr) ;  p = p->s.ptr)

              if ( p >= p->s.ptr && (bp > p || bp < p->s.ptr) )
                   break; // freed block at start or end of arena.

使用p == freep ==＆base still进入for循环。在这之后，我有条件的麻烦。将首先执行for循环条件-将基本(全局)地址(p == freep ==＆base still)与从OS新获得的空间的地址进行比较(注意-此地址来自free参数)。在malloc中，我们将freep == p-> s.ptr初始化为＆base。因此，此时p和p-> s.ptr都指向相同的地址。因此，for条件将为TRUE，因为bp不能同时是>和<同一地址。注意取反，它使循环条件为TRUE，然后输入if条件。

步骤5:

if条件的第一部分是p> = p-> s.ptr。这是正确的，因为p == freep ==＆base == p-> s.ptr(在malloc中设置)。 if条件的第二部分为TRUE，因为bp必须>或<相同地址(p == p-> s.ptr)。因此，我们退出for循环，因为释放的块位于竞技场的开始(或竞技场的结束，如果我们通过malloc维护的空闲内存的循环链接列表到达此点)。

步骤6:我的问题在这里

if(bp + bp->s.size == p->s.ptr) {          // join to upper nbr
     bp->s.size  += p->s.ptr->s.size;
     bp->s.ptr  =   p->s.ptr->s.ptr;  
}
else  bp->s.ptr = p->s.ptr;

继续... for循环后的第一个if条件为false，因为新分配的存储空间将不等于p-> s.ptr，即'base'的地址。因此，执行else并将新分配的 header 设置为p-> s.ptr == freep-> s.ptr == freep ==＆base !!!为什么要将此新指针设置为“基本”全局地址？

我的第二个问题是，如果满足条件，为什么要使用2级间接寻址(上面代码的第三行)来设置bp-> s.ptr？ (我知道这是要加入连续的块。)

第7步:加入下层nbr(是书中的注释)

 if (p + p->s.size == bp) {
     p->s.size  += bp->s.size;
     p->s.ptr  =  bp->s.ptr;
 }
 else   p->s.ptr = bp;
 freep = p;

由于相同的原因，在第一遍过程中，下一个if条件也将为false，并且else子句将p-> s.ptr == base.s.ptr == freep-> s.ptr设置为新分配的内存。因此，下一条语句freep = p在我们第一次遍历malloc / morecore / free的序列时是多余的？在所有这些步骤的最后，freep仍指向“base”的地址？没有变化 ？感觉像我在逻辑上犯了一些错误。

关于ANSI标准C关于联合的说明，有一点需要澄清。这可以追溯到我上面带有“typedef”的第一个代码片段。我认为静态联合(例如静态Header base)内的所有成员都由编译器初始化为零？如果我没有将它们声明为静态的怎么办？在这种情况下，结构s.header ptr是否为NULL？

请指出，如果我在7个步骤的逻辑中犯了任何错误，请进行第一次尝试。如果有人花时间清楚地写下(我做过的事情)free()的工作方式以及free()中各种条件的伪代码，我也将不胜感激。这样，该线程将对学生/新手非常有用。

感谢您的时间和解释。

Answer 1

为什么要将此新指针设置为“基本”全局地址？

在malloc实现的描述中，据说最后一个块具有指向第一个块的指针。而且由于第一次调用函数，您没有任何块，因此该块指向自身。

因此，下一条语句freep = p在我们第一次遍历malloc / morecore / free的序列时是多余的？在所有这些步骤的最后，freep仍指向“base”的地址？没有变化 ？感觉像我在逻辑上犯了一些错误。

我相信，在第一次调用malloc时，您对 freep = p = &base 的推理没有错误。
我认为，一般而言，这段代码非常棘手。在这个问题(Explain this implementation of malloc from the K&R book)中，您可以找到更多关于k＆r malloc()实现的评论
但是对于您的情况，我认为free()名称使您有些困惑。因为函数free()实际上具有两个目的:初始化全新的空闲列表，以及显然释放先前分配的内存。 S.Macconnell的“代码完成”也说，具有多种用途的功能不是一个好主意。
因此，在第一遍中，是的，实际上，您不需要其他分配(初始化free()的机制)。但是在下一次调用free(真正释放先前分配的内存的方式)时，使用指向空闲列表内存的最后一块的指针来合并内存很有用。

关于ANSI标准C关于联合的说明，有一点需要澄清。这可以追溯到我上面带有“typedef”的第一个代码片段。我认为静态联合(例如静态Header base)内的所有成员都由编译器初始化为零？

是的，引用c89 draft(3.5.7。初始化):

如果具有静态存储持续时间的对象未初始化
显式地，它隐式地初始化，就像每个具有
算术类型分配了0，每个成员都具有指针类型
被分配了一个空指针常量。如果对象具有自动
存储持续时间未明确初始化，其值为
不定。

如果我没有将它们声明为静态的怎么办？在这种情况下，结构s.header ptr是否为NULL？

我相信这将是垃圾。