The Origins of Malloc

The 1973 Fourth Edition Unix kernel source code contains two routines, malloc and mfree, that manage the dynamic allocation and release of main memory blocks for in-memory processes and of continuous disk swap area blocks for swapped-out processes. Their implementation and history can teach us many things regarding modern computing.

Amazingly, these routines are used to allocate two very different types of resources: main memory areas and disk blocks. Both allocations use the same underlying data structure, a map. Each of the two maps (coremap and swapmap) is an array of structures containing the position and size of each allocated block. Consequently, one can surmise that the name malloc did not initially stand for “memory allocate”, but for “map allocate”.

The definition of the map structure is also interesting.

struct map {
        char *m_size;
        char *m_addr;
};

The structure is defined to contain two pointers to characters. However, m_size is actually used as an integer and m_addr can be either a memory address or a disk block offset. Playing fast and loose with pointers and integers was common at the time. It took developers more than a decade to shake off the habit with the introduction of more stringent type checking in C and its successort languages. In fact, when John Lions describes the map data structure in the 6th Edition Unix, he writes that character pointers are the same as unsigned integers. (The C programming language did not at the time have an unsigned data type.)

Both data structures survived until the 1979 7th Edition Unix, and swapmap could still be found in the 1980s Berkeley Unix distributions. By that time the swapmap array was being allocated dynamically. Also, through the introduction of memory management hardware, swapping out entire processes to disk was giving way to paging out smaller (virtual) memory pages. The name malloc survives to this day as the function used in the C programming language to dynamically allocate a memory block.

Comments   Toot! Tweet Share