Where is the "space itself" in the storage allocator described at the end of K&R's book?

Question

At the very end of Kernighan & Ritchie's book the The C Programming Language, a storage allocator is described. It says

Each block contains a size, a pointer to the next block, and the space itself.

But I don't see that in the code:

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;

The pointer to the next block is *ptr and the size is unsigned size but which variable is the space itself? Is the space itself the variable x?

It's likely that the space follows immediately after the header itself. — sashoalm, Sep 15 '15 at 13:08
Are you sure that's not just the *header* for the block? I.e., when space is allocated, you'd allocate size+sizeof(header) bytes, put the header in the first sizeof(header) bytes, and then have size bytes remaining in the allocated memory? — Joshua Taylor, Sep 15 '15 at 13:09
K&R is quite ancient and does not account for C99 features like _flexible struct members_ — too honest for this site, Sep 15 '15 at 13:25
Assuming you computer is not from the 80s, the size of `ptr` plus size of `size` will be larger than `x`. There's no alignment fix present and the whole segment will most likely have padding bytes. All this code does is to pointlessly obfuscate things. Just don't read this crap, 30 years later it is nonsense code. — Lundin, Sep 15 '15 at 13:32
[Post about this very example](http://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book). In case it wasn't already obvious to you how bad the code is. — Lundin, Sep 15 '15 at 13:37

score 3 · Accepted Answer · edited May 23 '17 at 11:44

That's just the header for the block. That is, when space is allocated, you'd allocate some amount of space, in multiples of sizeof(header), put the header in the first sizeof(header) bytes, and then have size bytes remaining in the allocated memory. From the text (I think; this is what I was led to when I Googled some of the text you quoted, and comes unexpectedly from a Java tutorials site), emphasis added:

A free block contains a pointer to the next block in the chain, a record of the size of the block, and then the free space itself; the control information at the beginning is called the "header." To simplify alignment, all blocks are multiples of the header size, and the header is aligned properly. This is achieved by a union that contains the desired header structure and an instance of the most restrictive alignment type, which we have arbitrarily made a long[.]

page 186, Chapter 8, The C Programming Language, Second Edition

Later, on p. 187, the sample implementation of malloc() shows that memory is always allocated in multiples of headers, with an addition header at the beginning for the control information:

void *malloc(unsigned nbytes)
{
    /* ... */
    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
page 187, Chapter 8, The C Programming Language, Second Edition

Possibly Useful References

Not quite the same question, but includes discussion of the same, another Stack Overflow question, What am I missing from this K&R sample?
Explain this implementation of malloc from the K&R book

score 1 · Answer 2 · edited Jun 20 '20 at 09:12

The book is talking about a storage allocator. Excerpt (emphasis mine):

8.7 Example - A Storage Allocator

[…]

Rather than allocating from a compiled-in fixed-size array, malloc will request space from the operating system as needed. Since other activities in the program may also request space without calling this allocator, the space that malloc manages may not be contiguous. Thus its free storage is kept as a list of free blocks. Each block contains a size, a pointer to the next block, and the space itself.

The author is simply referring to the space allocated for a request. Say a request for 20 KiB comes for allocation, a block is created for this request. It would contain the request size as an int which would've the value 20 * 1024 * 1024, followed by a pointer to the next such allocated block and then 20 KiB of free space (this is what the term refers too) whose first byte address is handed back to the caller.

In the page that follows the code shown is

void *malloc(unsigned nbytes)
{
    …
    nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;

This shows that the union only covers space for the control information (Header) and not the free space itself, which is later added to the count of allocated units.

I think OP's confusion in "Each block contains a size, a pointer to the next block, and the space itself." is that the header struct mentioned in the question *isn't the entire block*, but just a *header* for the block. — Joshua Taylor, Sep 15 '15 at 13:44

Where is the "space itself" in the storage allocator described at the end of K&R's book?

2 Answers2

Possibly Useful References