Maybe that's what was being used in the common versions of C. If so, then for whatever reason I missed out on that. I kept seeing in the book where they kept saying that malloc() allocated storage in the 'heap' without being clear on what they meant by a 'heap' although in this thread is an explanation that 'heap' was also used in Algol 68. Whatever, when they said 'heap' with no explanation, they blew me away.

Once I was one of a team of three researchers that did a new language. Eventually it shipped commercially. We needed a lot in dynamic storage allocation. Our approach was to start with an array of pointers, say, for i = 1, 2, ..., 32 or some such, s(i) was a pointer to the start of storage for chunks of size 2^(i-1) + 1 to 2^i. So, allocate 10 bytes of storage from 16 bytes where 16 = 2^i for i = 4. That is, i = 4 handles requests of size 9 through 16. Etc.

So, right away at the start of execution for relatively large j, have the operating system allocate a block of storage of size 2^j. Then for i < j, if need a block of storage for allocations handled by i, get that from storage handled by i + 1, etc. up to j where actually get some storage. That is, if i = 4 needs storage, get that from i = 5 that handles requests up to size 32 = 2^5.

For each i, the allocated blocks are chained together in a linked list and so are the free blocks. So, for an allocation, look first at the end of the linked list of free blocks.

In principle, after enough uses of, call it, free(), could return some storage for i to the storage for i + 1 but we didn't bother doing that.

It always seemed to me that on a virtual memory system where the page size was a power of 2 (aren't they all?), this approach to dynamic memory allocation would be quite good.

Later I was using an old version of Fortran, got a big block of storage from the operating system as just an array (right, as a common block known to the linkage editor), and wrote code such as above to have versions of malloc() and free().

If what is there in K&R in 8.7 is what was actually being used in the versions of C I used, then I blew it by not writing some code at least to report on storage allocated, freed, 'fragmentation', when allocated, etc. Basically I was highly concerned that in a relatively complicated program with just malloc() and free() I would make some mistakes in storage allocation and get some bugs that gave symptoms only occasionally and that would be a total pain to diagnose. "Last Tuesday after running for four hours we got some strange data in the file and then it blew up." Great! It reminds me of one of those arrangements of a few thousand dominoes on edge where when one tips over they all go, a house of cards, an electric power system with no circuit breakers, a dense city built with no fire safety codes, etc.