K & R malloc code does not make sense?

Question

This code is from books K and R - Chapter 8 Section 7: Example - Storage Assistant. This code, at least for me, makes no sense. A “header” is a combination of structure and “the most restrictive type of alignment,” which is a long type. Malloc will then find a sufficiently large free space with a size that is a multiple of the size of the header.

static Header base; /* empty list to get started */ static Header *freep = NULL; /* start of free list */ /* malloc: general-purpose storage allocator */ 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 = 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; } freep = prevp; return (void *)(p+1); } if (p == freep) /* wrapped around free list */ if ((p = morecore(nunits)) == NULL) return NULL; /* none left */ } } 

The odd part of this code is the operator nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1; , which is then used when comparing if (p->s.size >= nunits) to find a sufficiently large space with units in terms of the size of the header. Should the first be only nunits = (nbytes+sizeof(Header)) / sizeof(Header) ? The source code will evaluate a value less than it should be. What is + -1? Why allocate less space than required.

Answer 1

-1 and +1 should take into account values ​​that are not multiplied by the block size.

For example, suppose the block size is 10. If you try to use the n / 10 formula to get the number of blocks you need, you get 1 block for n = 15. This is wrong, you need 2.

If you change the formula to n / 10 + 1 , this will also be a mistake. With n = 20, you only need 2 blocks, but this formula will return 3.

The correct formula is (n - 1) / 10 + 1 . This is how you combined with the whole division. The only difference between this and the formula you asked for is the extra sizeof(Header) , which is just the extra space needed for the header itself.

Answer 2

(nbytes+sizeof(Header)-1)/sizeof(Header) + 1 is a pretty standard idiom in the code to get the number of units of something with the correct rounding. You will try this with some values, you will see that it works correctly.

The actual idiom is better expressed as (nbytes - 1)/unitSizeInBytes + 1 .

To clarify, based on the last paragraph of the accepted answer, the use of sizeof(Header) is different on both sides of the division. It is used in a dividend because it needs to allocate bytes for the header and nbytes. It is used in the divider because the size of the selected blocks. In this case, it happens that they have the same value, sizeof(Header) .