Confusion with implementation of malloc from K&R

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?

While the semantics are the same, the use of a union as the header does make the logic a bit trickier to follow, it is basically the same approach described in this [awkwardly written, but good basic malloc introduction](http://www.inf.udec.cl/~leo/Malloc_tutorial.pdf). There a struct is used in lieu of the union, and at least for me, the logic was easier to follow as far as what points where, etc.. — David C. Rankin, Mar 14 '18 at 02:25
@Lundin: Instead of just asserting that this code is bad, it would be more constructive to describe *why* it's bad. I'll grant that it's written in a terse style that some might nowadays find hard to read, or even prone to bugs if carelessly messed with (but then, *any* code is prone to bugs if you mess with it without understanding it). But when you describe it as "naively written", that sounds like you're implying that it fails to consider all relevant cases and may fail to work as written. I rather doubt that is actually the case. — Ilmari Karonen, Mar 15 '18 at 14:03
@Lundin: Fair enough. IMO, while waiting for the mods to decide what to do, including that link in your first comment above would've made it a lot more helpful. — Ilmari Karonen, Mar 15 '18 at 14:12
I wrote the comment before I realized I couldn't dupe hammer the question. But now the bounty is posted so I can do so. I have withdrawn the flag. — Lundin, Mar 15 '18 at 14:19

score 4 · Accepted Answer · answered Mar 14 '18 at 20:08

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.

The only bit I'm unclear on still is how we can assign a size value despite that block being claimed from sbrk at some point, which will just initialize everything to zero - shouldn't we have to cast the block to Header and then assign a size? Or is block already of type Header? — screeb, Mar 14 '18 at 20:21
@bag The pointer to the block returned from `sbrk` is cast to `Header *`, so the whole block can be considered an array of `Header`. Anytime a portion of that memory is accessed from `malloc` or `free` it is done through a variable of type `Header *`, so the fields can be written in that way. — dbush, Mar 14 '18 at 20:25
Ah, I had been thinking that the cast only applied to the first unit in the block - that makes sense. — screeb, Mar 14 '18 at 20:27

Ingo Leonhardt · Answer 2 · 2018-03-14T18:53:16.130

1

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.

edited Mar 14 '18 at 18:53

answered Mar 14 '18 at 18:44

Ingo Leonhardt

9,435
2
24
33

I'm still unclear as to how the new header is created. When we increment `p` (with `p += p->s.size`), would `p` not now be `NULL`, or does the entire block consist of uninitialized Header units already? If it does, when does that happen? Doesn't sbrk just give us memory initialized to zero? – screeb Mar 14 '18 at 19:18
1

When you increment a pointer it will never be NULL (you just add a positive value to an address, so the result will be another addres). What's true is that the address p points to is uninitalized. But size is set in the next line und ptr doesn't matter – Ingo Leonhardt Mar 15 '18 at 09:04
And yes, the entire block has always a size which is a multiple of the header size so you can create a new header within that block at every position you set a pointer to. – Ingo Leonhardt Mar 15 '18 at 09:06

Confusion with implementation of malloc from K&R

2 Answers2