Confusion with implementation of malloc from K&R [duplicate]

Question

I've been reading through K&R and encountered a point of confusion in the implementation of malloc() included.

typedef long Align; /* for alignment to long boundary */

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 */

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 = freep = prevp = &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 */
    }
}

#define NALLOC 1024 /* minimum #units to request */
/* morecore: ask system for more memory */

static Header *morecore(unsigned nu)
{

  char *cp, *sbrk(int);
  Header *up;

  if (nu < NALLOC)
    nu = NALLOC;

  cp = sbrk(nu * sizeof(Header));

  if (cp == (char *) -1) /* no space at all */
    return NULL;

  up = (Header *) cp;
  up->s.size = nu;
  free((void *)(up+1));

  return freep;
}

/* free: put block ap in free list */
void free(void *ap) {
  Header *bp, *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 */

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

  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;
}

What I'm having trouble understanding is how the tail end is allocated.

• Will prevp->s.ptr still point to the beginning of the block (but now with size - nunits) after partitioning the block, so the remaining portion of the block is still available?
• When incrementing (p += p->size) to where the new, to-be-returned block begins how are we able to reference p->s.size and assign it nunits. Shouldn't p be NULL, as the block isn't ever initialized save for the header?

Answer 1

On the first call to malloc, a memory block is physically allocated by via a call to sbrk and added to the free list. At this point memory looks like this:

 1 (base)              freep
 -----------           -------
 | 10 / 0  |           |  1  |
 -----------           -------

 10        11        12        13        14        15
 -------------------------------------------------------------
 |  1 / 6  |         |         |         |         |         |
 -------------------------------------------------------------

For the sake of simplicity, I've numbered the memory blocks in terms of "units" as opposed to actual bytes. Here we assume the global variable base lives at address 1 and that there are a block of 6 units allocated starting at address 10. In each unit, the first number is the value of ptr and the second is the value of size. Also, freep contains the address of the start of the free block.

So the free list starts with the empty base block which then points to the block at address 10. That block contains 5 free units and points back to the base block.

Let's assume the current call to malloc is requesting 2 units. When we first enter the for loop, prev == 1 and p == 10:

 1 (base)              freep       prev       p
 -----------           -------     ------     ------
 | 10 / 0  |           |  1  |     | 1  |     | 10 |
 -----------           -------     ------     ------

 10        11        12        13        14        15
 -------------------------------------------------------------
 |  1 / 6  |         |         |         |         |         |
 -------------------------------------------------------------

When adding at the tail, the first statement is p->s.size -= nunits;. This decrements size in p by nunits:

 1 (base)              freep       prev       p
 -----------           -------     ------     ------
 | 10 / 0  |           |  1  |     | 1  |     | 10 |
 -----------           -------     ------     ------

 10        11        12        13        14        15
 -------------------------------------------------------------
 |  1 / 4  |         |         |         |         |         |
 -------------------------------------------------------------

So now the block at address 10 is 4 units in size instead of 6. Next is p += p->s.size; which adds the value of size to p:

 1 (base)              freep       prev       p
 -----------           -------     ------     ------
 | 10 / 0  |           |  1  |     | 1  |     | 14 |
 -----------           -------     ------     ------

 10        11        12        13        14        15
 -------------------------------------------------------------
 |  1 / 4  |         |         |         | xx / xx |         |
 -------------------------------------------------------------

Now p points to address 14. Currently the ptr and size fields contain garbage, denoted here as "xx". Note that p is not NULL. It points someplace, but that memory has no meaningful data.

Now we run p->s.size = nunits; which sets the size field in the unit that p points to:

 1 (base)              freep       prev       p
 -----------           -------     ------     ------
 | 10 / 0  |           |  1  |     | 1  |     | 14 |
 -----------           -------     ------     ------

 10        11        12        13        14        15
 -------------------------------------------------------------
 |  1 / 4  |         |         |         | xx / 2  |         |
 -------------------------------------------------------------

Then we have freep = prevp; which sets the free pointer to the current value of prev. At this point, there's no change. Then we return p+1, which is 15, to the caller.

The end result is that the block pointed to by prev hasn't changed, but the one pointed to by prev->s.ptr is now smaller by the requested number of units, and address 14 is now the start of an allocated block of memory 2 units in size.

When address 15 is later passed to free, it looks at address 14 to see how big the allocated block is so it can put those units back on the free list.

Answer 2

If malloc() will use a part of a free segement, this is split into two parts. The first remains free, the second will be the one returned. I think you've got that already.

So, what are the consequences:

• prev->s.ptr still points to the same address (the original p) which is OK as there is still free memory here, only nunits less then before.
• In the header 'original p', the address s.ptr remains unchanged, so prev->s.ptr->s.ptr still points to the same address as before, the chain remains valid (the first two bullets should answer the first question).
• now p is incremented to point to the beginning of the memory block we want to return (p += p->s.size). Of course that memory block shall also begin with a header which is not yet initialized, so we set p->s.size = nunits; p->s.ptr may still contain garbage value, but that's ok because it's not a free block (that should answer the second question).
• finally p + 1 is returned, which is the "payload" of the memory block behind the new header.