Confusion with the implementation of malloc from K & R

Question

I read K & R and ran into confusion in the implementation of malloc() .

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

I'm having trouble understanding how the tail stands out.

• Will prevp->s.ptr point to the beginning of the block (but now with sizes-nunits) after the block is split, so that the rest of the block is still available?
• When adding ( p += p->size ) to where the new block to be returned starts, how can we refer to p->s.size and assign it nunits . Should p be NULL since the block is never initialized to save the header?

Answer 1

The first time malloc called, the memory block is physically allocated by calling sbrk and added to the free list. At this point, the memory looks like this:

  1 (base) freep ----------- ------- | 10 / 0 | | 1 | ----------- ------- 10 11 12 13 14 15 ------------------------------------------------------------- | 1 / 6 | | | | | | ------------------------------------------------------------- 

For simplicity, I numbered blocks of memory in terms of "units" rather than actual bytes. Here we assume that the global base variable lives at address 1 and that there is a block of 6 units assigned starting at address 10. In each module, the first number is the ptr value, and the second is the size value. In addition, freep contains the start address of the free block.

Thus, a free list starts with an empty base block, which then points to a block at address 10. This block contains 5 free units and points to a base block.

Suppose the current call to malloc requests 2 units. When we first introduce 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 added to the tail, the first statement p->s.size -= nunits; . This reduces the 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 with address 10 has a size of 4 units instead of 6. Next 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 not NULL. It points somewhere, but this memory has no meaningful data.

Now we run p->s.size = nunits; , which sets the size field in the module, which 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 a free pointer to the current prev value. There are no changes at this time. Then we return p+1 , which is equal to 15, the caller.

The end result is that the block pointed to by prev has not changed, but the one pointed to by prev->s.ptr is now less than the requested number of units, and address 14 is now the beginning of the allocated 2-unit memory block.

When address 15 is then passed to free , he looks at address 14 to see how big the allocated block is so that it can return these units to the free list.

Answer 2

If malloc() will use part of the free segment, it splits into two parts. The first remains free, the second will be returned. I think you already have it.

So what are the consequences:

• prev->s.ptr still points to the same address (original p ), which is fine, since there is still free memory here, only nunits smaller than before.
• In the 'original p' s.ptr address 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 incremented to indicate the beginning of the block of memory that we want to return ( p += p->s.size ). Of course, this memory block should also start with a header that has not yet been initialized, so we set p->s.size = nunits ; p->s.ptr may still contain the garbage value, but this is normal because it is not a free block (which should answer the second question). Coming back
• finally p + 1 , which is the "payload" of the memory block behind the new header.