It seems an unnecessary line in the K & RC example for malloc?

Question

You can find this code in the K & R 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 )

Basically there is a linked list, and each node in the list starts with a heading indicating the next node, and the amount of memory that the node allocated after the heading (in multiples of the size of the heading). This linked list keeps track of where there is free memory.

What I don't understand is why the line in STRANGE LINE ????? necessary. I understand the first two. We want to give the user node the end, so we reduce the size and push p with the new size and give it to the user (+1). But then the third line wants to set the space size p points to the number of units. What for? After the second line of p points to a spot in free memory that does not seem to make any difference. Is this some kind of dodgy optimization that I don’t know about, or is it really necessary?

Thanks for any help!

Answer 1

The reason you did not understand this line is because it cannot be understood in isolation: from the point of view of malloc it is useless. This assignment is performed to support the functionality of the corresponding free function, which must know the allocated size in order to add a block of memory 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 flies in bytes immediately before it is returned to the caller. This is the part of the header that malloc and free use for their “accounting”.