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.1 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 14.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:
Some of the LMM’s (potential) disadvantages with respect to more conventional memory allocators are:
The LMM maintains a concept of a memory region, represented by the data type lmm_region_t, which represents a range of memory addresses within which free memory blocks may be located. Multiple memory regions can be attached to a single LMM pool, with different attributes attached to each region.
The attributes attached to memory regions include a set of caller-defined flags, which typically represent fundamental properties of the memory described by the region (i.e., the ways in which the region can be used), and a caller-specified allocation priority, which allows the caller to specify that some regions are to be preferred over others for satisfying allocation requests.
It is not necessary for all the memory addresses covered by a region to actually refer to valid memory locations; the LMM will only ever attempt to access subsections of a region that are explicitly added to the free memory pool using lmm_add_free. Thus, for example, it is perfectly acceptable to create a single region covering all virtual addresses from 0 to (oskit_addr_t)-1, as long as only the memory areas that are actually valid and usable are added to the free pool with lmm_add_free.
The LMM assumes that if more than one region is attached to an LMM pool, the address ranges of those regions do not overlap each other. Furthermore, the end address of each region must be larger than the start address, using unsigned arithmetic: a region must not “wrap around” the top of the address space to the bottom. These restrictions are not generally an issue, but can be of importance in some situations such as when running on the x86 with funny segment layouts.
The region flags, of type lmm_flags_t, generally indicate certain features or capabilities of a particular range of memory. Allocation requests can specify a mask of flag bits that indicate which region(s) the allocation may be made from. For each flag bit set in the allocation request, the corresponding bit must be set in the region in order for the region to be considered for satisfying the allocation.
For example, on PCs, the lowest 1MB of physical memory is “special” in that only it can be accessed from real mode, and the lowest 16MB of physical memory is special in that only it can be accessed by the built-in DMA controller. Thus, typical behavior on a PC would be to create three LMM regions: one covering the lowest 1MB of physical memory, one covering the next 15MB, and one covering all other physical memory. The first region would have the “1MB memory” and “16MB memory” bits set in its associated flags word, the second region would have only the “16MB memory” bit set, and the third region would have neither. Normal allocations would be done with a flags word of zero, which allows the allocation to be satisfied from any region, but, for example, allocations of DMA buffers would be done with the “16MB memory” flag set, which will force the LMM to allocate from either the first or second region. (In fact, this is the default arrangement used by the libkern library when setting up physical memory for an OS running on a PC; see Section 15.11 for more details.)
The second attribute associated with each region, the allocation priority, indicates in what order the regions should be searched for free memory to satisfy memory allocation requests. Regions with a higher allocation priority value are preferred over regions with a lower priority.
Allocation priorities are typically useful in two situations. First, one section of a machine’s physical memory may provide faster access than other regions for some reason, for example because it is directly connected to the processor rather than connected over a slower bus of some kind. (For example, the Amiga has what is known as “fast” memory, which typically supports faster access because it does not contend with ongoing DMA activity in the system.) In this case, if it is not likely that all available memory will be needed, the memory region describing the faster memory might be given higher priority so that the LMM will allocate from it whenever possible.
Alternatively, it can be useful to give a region a lower priority because it is in some way more “precious” than other memory, and should be conserved by satisfying normal allocation requests from other regions whenever possible. For example, on the PC, it makes sense to give 16MB memory a lower priority than “high” memory, and 1MB memory a still lower priority; this will decrease the likelihood of using up precious “special” memory for normal allocation requests which just need any type of memory, and causing memory shortages when special memory really is needed.
To make an LMM pool ready for use, a client generally proceeds in three stages:
Here is an example initialization sequence that sets up an LMM pool for use in a Unix-like environment, using an (initially) 1MB memory pool to service allocations. It uses only one region, which covers all possible memory addresses; this allows additional free memory areas to be added to the pool later regardless of where they happen to be located.
#include <oskit/lmm.h>
lmm_t lmm;
lmm_region_t region;
int setup_lmm()
{
unsigned mem_size = 1024*1024;
char *mem = sbrk(mem_size);
if (mem == (char*)-1)
return -1;
lmm_init(&lmm);
lmm_add_region(&lmm, ®ion, (void*)0, (oskit_size_t)-1, 0, 0);
lmm_add_free(&lmm, mem, mem_size);
return 0;
}
|
After the LMM pool is set up properly, memory blocks can be allocated from it using any of the lmm_alloc functions described in the reference section below, and returned to the memory pool using the lmm_free function.
This section describes some of the important restrictions the LMM places on its use. Many of these are restrictions one would expect to be present; however, they are listed here anyway in order to make them explicit and to make it more clear in what situations the LMM can and can’t be used.
As mentioned previously, the LMM implements no internal synchronization mechanisms, so if it is used in a multithreaded environment, the caller must explicitly serialize execution when performing operations on a particular LMM pool.
If a client uses multiple LMM memory pools, then each pool must manage disjoint blocks of memory. In other words, a particular chunk of memory must never be present on two or more LMM pools at once. However, as long as the actual memory blocks in different pools are disjoint, the overall memory regions managed by the pools can overlap. For example, it is OK if pages 1 and 3 are managed by one LMM pool and page 2 is managed by another, as long as none of those pages are managed by two LMM pools at once.
The LMM uses the memory it manages as storage space for free list information. This means that the LMM is not suitable for managing memory that cannot be accessed directly using normal C pointer arithmetic in the local address space, or memory with special access semantics, such as flash memory. In such a situation, you must use a memory management system that stores free memory metadata separately from the free memory itself.
The LMM guarantees that it will not use any memory other than the memory explicitly given to it for its use through the lmm_init, lmm_add_region, and lmm_add_free calls. This implies that no “destructor” functions need to be provided by the library in order to destroy LMM pools, regions, or free lists: an LMM pool can be “destroyed” by the caller simply by overwriting or reinitializing the memory with something else. Of course, it is up to the caller to ensure that no attempts are made to use an LMM pool that has been destroyed.
When the OSKit is compiled with debugging enabled (--enable-debug), a fairly large number of sanity checks are compiled into the LMM library to help detect memory list corruption bugs and such. Assertion failures in the LMM library can indicate bugs either in the LMM itself or in the application using it (e.g., freeing blocks twice, overwriting allocated buffers, etc.). In practice such assertion failures usually tend to be caused by the application, since the LMM library itself is quite well-tested and stable. For additional help in debugging memory management errors in applications that use the C-standard malloc/free interfaces, the OSKit’s memdebug library can be used as well (see Section 31).
Note that the sanity checks in the LMM library are likely to slow down the library considerably under normal use, so it may be a good idea to turn off this debugging support when linking the LMM into “stable” versions of a program.
The following sections describe the functions exported by the LMM in detail. All of these functions, as well as the types necessary to use them, are defined in the header file <oskit/lmm.h>.
This function initializes an LMM pool. The caller must provide a pointer to an lmm_t structure, which is typically (but doesn’t have to be) statically allocated; the LMM system uses this structure to keep track of the state of the LMM pool. In subsequent LMM operations, the caller must pass back a pointer to the same lmm structure, which acts as a handle for the LMM pool.
Note that the LMM pool initially contains no regions or free memory; thus, immediate attempts to allocate memory from it will fail. The caller must register one or more memory regions using lmm_add_region, and then add some free memory to the pool using lmm_add_free, before the LMM pool will become useful for servicing allocations.
#include <oskit/lmm.h>
void lmm_add_region(lmm_t *lmm, lmm_region_t *region, void *addr, oskit_size_t size, lmm_flags_t flags, lmm_pri_t pri);
This function attaches a new memory region to an LMM pool. The region describes a contiguous range of addresses with specific attributes, in which free memory management may need to be done.
The caller must supply a structure of type lmm_region_t in which the LMM can store critical state for the region. This structure must remain available for the exclusive use of the LMM for the entire remaining lifetime of the LMM pool to which it is attached. However, the contents of the structure is opaque; client code should not examine or modify its contents directly.
The caller must only ensure that if multiple regions are attached to a single LMM pool, they refer to disjoint address ranges.
Note that this routine does not actually make any free memory available; it merely registers a range of addresses in which free memory might be made available later. Typically this call is followed by one or more calls to lmm_add_free, which actually adds memory blocks to the pool’s free memory list.
The act of registering a new region does not cause any of the memory described by that region to be accessed or modified in any way by the LMM; only the lmm_region_t structure itself is modified at this point. The LMM will only access and modify memory that is explicitly added to the free list using lmm_add_free. This means, for example, that it is safe to create a single region with a base of 0 and a size of (oskit_size_t)-1, regardless of what parts of that address range actually contain valid memory.
See Section 25.2 for general information on memory regions.
This routine declares a range of memory to be available for allocation, and attaches that memory to the specified LMM pool. The memory block will be made available to satisfy subsequent allocation requests.
The caller can specify a block of any size and alignment, as long as the block does not wrap around the end of the address space. The LMM may discard a few bytes at the beginning and end of the block in order to enforce internal alignment constraints; however, the LMM will never touch memory outside the specified block (unless, of course, that memory is part of another free block).
If the block’s beginning or end happens to coincide exactly with the beginning or end of a block already on the free list, then the LMM will merge the new block with the existing one. Of course, the block may be further subdivided or merged later as memory is allocated from the pool and returned to it.
The new free block will automatically be associated with whatever region it happens to fall in. If the block crosses the boundary between two regions, then it is automatically split between the regions. If part of the block does not fall within any region, then that part of the block is simply ignored and forgotten about. (By extension, if the entire block does not overlap any region, the entire block is dropped on the floor.)
This routine is complementary to lmm_add_free: it removes all free memory blocks in a specified address range from an LMM memory pool. After this call completes, unless the caller subsequently adds memory in this range back onto the LMM pool using lmm_add_free or lmm_free it is guaranteed that no subsequent memory allocation will return a memory block that overlaps the specified range.
The address range specified to this routine does not actually all have to be on the free list. If the address range contains several smaller free memory blocks, then all of those free blocks are removed from the pool without touching or affecting any memory parts of the address range that weren’t in the free memory list. Similarly, if a free block crosses the beginning or end of the range, then the free block is “clipped” so that the part previously extending into the address range is removed and thrown away.
One use for this routine is to reserve a specific piece of memory for some special purpose, and ensure that no subsequent allocations use that region. For example, the example MultiBoot boot loaders in the OSKit use this routine to reserve the address range that will eventually be occupied by the OS executable being loaded, ensuring that none of the information structures to be passed to the OS will overlap with the final position of its executable image.
This routine works by finding all the free memory in the given range and allocating it. This means that if blocks were allocated in that range before the lmm_remove_free call and then freed afterwords, then they will be candidates for future allocations.
This is the primary routine used to allocate memory from an LMM pool. It searches for a free memory block of the specified size and with the specified memory type requirements (indicated by the flags argument), and returns a pointer to the allocated memory block. If no memory block of sufficient size and proper type can be found, then this function returns NULL instead.
Note that unlike with malloc, the caller must keep track of the size of allocated blocks in order to allow them to be freed properly later.
Returns a pointer to the memory block allocated, or NULL if no sufficiently large block of the correct type is available. The returned memory block will be at least doubleword aligned, but no other alignment properties are guaranteed by this routine.
#include <oskit/lmm.h>
void *lmm_alloc_aligned(lmm_t *lmm, oskit_size_t size, lmm_flags_t flags, int align_bits, oskit_addr_t align_ofs);
This routine allocates a memory block with specific alignment constraints. It works like lmm_alloc, except that it enforces the rule that the lowest align_bits bits of the address of the returned block must match the lowest align_bits of align_ofs. In other words, align_bits specifies an alignment boundary as a power of two, and align_ofs specifies an offset from “natural” alignment. If no memory block with the proper requirements can be found, then this function returns NULL instead.
Returns a pointer to the memory block allocated, or NULL if no memory block satisfying the specified requirements can be found.
#include <oskit/lmm.h>
void *lmm_alloc_gen(lmm_t *lmm, oskit_size_t size, lmm_flags_t flags, int align_bits, oskit_addr_t align_ofs, oskit_addr_t in_min, oskit_size_t in_size);
This routine allocates a memory block meeting various alignment and address constraints. It works like lmm_alloc_aligned, except that as an additional constraint, the returned memory block must fit entirely in the address range specified by the in_min and in_size parameters.
If in_size is equal to size, then memory will only be allocated if a block can be found at exactly the address specified by in_min; i.e., the returned pointer will either be in_min or NULL.
Returns a pointer to the memory block allocated, or NULL if no memory block satisfying all of the specified requirements can be found.
This routine allocates a memory block that is exactly one minimum-size hardware page in size, and is naturally aligned to a page boundary. The same effect can be achieved by calling lmm_alloc_aligned with appropriate parameters; this routine merely provides a simpler interface for this extremely common action.
Returns a pointer to the memory page allocated, or NULL if no naturally-aligned page can be found.
This routine is used to return a memory block allocated with one of the above lmm_alloc functions to the LMM pool from which it was allocated.
This routine simply calls lmm_free with PAGE_SIZE as the size argument, providing a companion to lmm_alloc_page.
This routine returns the number of bytes of free memory currently exist in the specified LMM memory pool of a certain memory type, specified by the flags argument.
Note that the returned value does not imply that a block of that size can be allocated; due to fragmentation it may only be possible to allocate memory in significantly smaller chunks.
Returns the number of bytes of free memory available of the requested memory type.
#include <oskit/lmm.h>
void lmm_find_free(lmm_t *lmm, [in/out] oskit_addr_t *inout_addr, [out] oskit_size_t *out_size, [out] lmm_flags_t *out_flags);
This routine can be used to locate free memory blocks in an LMM pool. It searches the pool for free memory starting at the address specified in *inout_addr, and returns a description of the lowest block of available memory starting at at least this address. The address and size of the next block found are returned in *inout_addr and *out_size, respectively, and the memory type flags associated with the region in which the block was found are returned in *out_flags. If no further free memory can be found above the specified address, then this routine returns with *out_size set to zero.
If the specified *inout_addr points into the middle of a free block, then a description of the remainder of the block is returned, i.e., the part of the block starting at *inout_addr and extending to the end of the free block.
This routine does not actually cause any memory to be allocated; it merely reports on available memory blocks. The caller must not actually attempt to use or modify any reported blocks without allocating them first. The caller can allocate a block reported by this routine using lmm_alloc_gen, using its in_min and in_size parameters to constrain the address of the allocated block to exactly the address reported by lmm_find_free. If this allocation is done immediately after the call to lmm_find_free, without any intervening memory allocations, then the allocation is guaranteed to succeed. However, any intervening memory allocation operations will effectively invalidate the information returned by this routine, and a subsequent attempt to allocate the reported block may fail.
This routine is primarily used for debugging the LMM and the code that uses it. It scans through the LMM pool and calls printf to display each attached memory region and all the blocks of free memory currently contained in each.
Uses printf to display a one-line summary of an LMM in the form:
|
which lists the address of the LMM pool, the total number of bytes contained in it, the number of regions attached via lmm_add_region, and the number of nodes used to describe the memory. This routine is primarily used for tracking down memory leaks and list fragmentation problems.