15.1 Introduction

The list-based memory manager is a component that provides simple but extremely generic and flexible memory management services. It provides functionality at a lower level than typical ANSI C malloc-style memory allocation mechanisms. For example, the LMM does not keep track of the sizes of allocated memory blocks; that job is left to the client of the LMM library or other high-level memory allocation mechanisms. (For example, the default version of malloc() provided by the minimal C library, described in Section 9.5.2, is implemented on top of the LMM.)

The LMM attempts to make as few assumptions as possible about the environment in which it runs and the use to which it is put. For example, it does not assume that all allocatable ``heap'' memory is contained in one large continuous range of virtual addresses, as is the case in typical Unix process environments. Similarly, it does not assume that the heap can be expanded on demand (although the LMM can certainly be used in situations in which the heap is expandable). It does not assume that it is OK to ``waste'' pages on the assumption that they will never be assigned ``real'' physical memory unless they are actually touched. It does not assume that there is only one ``type'' of memory, or that all allocatable memory in the program should be managed as a single heap. Thus, the LMM is suited for use in a wide variety of environments, and can be used for both physical and virtual memory management.

The LMM has the following main features:

• Very efficient use of memory. At most fourteen bytes are wasted in a given allocation (because of alignment restrictions); there is no memory overhead for properly-aligned allocations.
• Support for allocating memory with specific alignment properties. Memory can be allocated at any given power-of-two boundary, or at an arbitrary offset beyond a specified power-of-two boundary. Allocation requests can also be constrained to specific address ranges or even exact addresses.
• Support for allocations of memory of a specific ``type.'' For example, on the PC architecture, sometimes memory needs to be allocated specifically from the first 16MB of physical memory, or from the first 1MB of memory.
• Support for a concept of allocation priority, which allows certain memory regions to be preferred over others for allocation purposes.
• The LMM is pure and does not use any global variables; thus, different LMM pools are completely independent of each other and can be accessed concurrently without synchronization. Section 2.2 describes the pure execution environment supported by the LMM in more detail.
• Extremely flexible management of the memory pool. LMM pools can be grown or shrunk at any time, under the complete control of the caller. The client can also ``map'' the free memory pool, locating free memory blocks without allocating them.

Some of the LMM's (potential) disadvantages with respect to more conventional memory allocators are:

• It requires the caller to remember the size of each allocated block, and pass its size back as a parameter to lmm_free. Thus, a malloc implemented on top of this memory manager would have to remember the size of each block somewhere.
• Since the LMM uses sequential searches through linked lists, allocations are not as blazingly fast as in packages that maintain separate free lists for different sizes of memory blocks. However, performance is still generally acceptable for many purposes, and higher-level code is always free to cache allocated blocks of commonly used sizes if extremely high-performance memory allocation is needed. (For example, a malloc package built on top of the LMM could do this.)
• The LMM does not know how to ``grow'' the free list automatically (e.g. by calling sbrk() or some equivalent); if it runs out of memory, the allocation simply fails. If the LMM is to be used in the context of a growable heap, an appropriate grow-and-retry mechanism must be provided at a higher level.
• In order to avoid making the LMM dependent on threading mechanisms, it does not contain any internal synchronization code. The LMM can be used in multithreaded environments, but the calling code must explicitly serialize execution while invoking LMM operations on a particular LMM heap. However, LMM operations on different heaps are fully independent and do not need to be synchronized with each other.