Seemingly unneeded line in K&R C example for malloc?

Question

You can find this code in K&R's The C Programming Language:

void *malloc(unsigned nbytes) {
    Header *p, *prevp;
    Header *moreroce(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; /* STRANGE LINE???????? */
            }
            freep = prevp;
            return (void *)(p+1);
        }
        if (p == freep) /* wrapped around free list */
            if ((p = morecore(nunits)) == NULL)
                return NULL; /* none left */
    }
}

(from http://pelusa.fis.cinvestav.mx/tmatos/LaSumA/LaSumA2_archivos/Supercomputo/The_C_Programming_Language.pdf)

There's basically a linked list, and each node in the list begins with a header indicating the next node and the amount of memory the node has allocated after the header (in multiples of the header size). This linked list tracks where there is free memory.

What I don't understand is why the line at "STRANGE LINE?????" is needed. I understand the first two. We want to give the end of the node to the user, so we shrink the size, and advance p with the new size and give that to the user (+1). But then the third line wants to set the size of the place p points at to the number of units. Why? After the second line p points at a spot in the free memory which doesn't seem to have any meaning. Is this some sort of tricksy optimization I'm unaware of, or is it actually necessary?

Thanks for any help!

Answer 1

The reason you did not understand this line is that it cannot be understood in isolation: from the point of view of malloc, it is useless. This assignment is done in order to support functionality of the corresponding free function, which needs to know the allocated size to add the memory chunk to the 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 */
     /* Here is where the saved size comes into play */
     if (bp + bp->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;
     if (p + p->size == bp) { /* join to lower nbr */
         p->s.size += bp->s.size;
         p->s.ptr = bp->s.ptr;
     } else
         p->s.ptr = bp;
    freep = p;
}

As you can see, the size is squirreled away in the bytes just prior to what's returned to the caller. This is the header portion that malloc and free use for their "bookkeeping".