The Address Map Manager (AMM) library manages collections of resources where each element of a collection has a name (address) and some set of attributes. These collections are described by address maps. Examples of resources which might be managed by address maps include:
Logically, an address map is an array of attribute values indexed by address. However, such an implementation would be impractical for all but the smallest address ranges so the AMM coalesces ranges of contiguous addresses with identical attributes and describes each such range with an address map entry. Hence address maps are collections of map entries with every possible address contained in exactly one entry.
The AMM library includes routines to create and destroy address maps, lookup addresses within a map, modify the attributes of addresses within a map, and iterate over all entries in a map. The library is responsible for maintaining a consistent and efficient representation of the map. The complete set of routines is described in Section 26.8.
The AMM is a pure component: it uses no static or global variables, so clients can freely make concurrent AMM calls on different address maps without synchronization. However, in interruptible or multithreaded environments, the client is responsible for synchronizing calls that manipulate a single AMM pool. Section 2.2 describes the pure execution environment supported by the AMM in more detail.
The AMM attempts to be general by making very few assumptions about addresses or attributes. An address is defined as an arbitrary unsigned integer of some reasonable size (typically 32 or 64 bits). The value of the integer is not interpreted by AMM in any way. The only assumption that the AMM makes about addresses is that two addresses are considered contiguous (i.e., represent adjacent pieces of a resource) if their integer values are consecutive. This is an intuitive assumption and not likely to be a restriction for many (any?) uses.
Attributes are represented using an opaque flag word (again, an integer of reasonable size). The only assumption that AMM makes about attributes is that the attributes of two addresses are identical if their flag words have the same integer value. This again is a fairly obvious assumption. Note that though the flag word appears to limit the number of possible attributes to 32 or 64 single-bit values, the user can actually define arbitrary attributes for an address by associating additional state with the address. Section 26.5 explains how this is done.
Each address map is represented by an amm_t structure. This structure is allocated by the user and initialized once at startup via a library routine. After initialization, a pointer to the structure is used as an opaque handle for all subsequent AMM calls.
Many of the library routines take map entries as parameters or pass them back as return values. Thus the AMM defines an opaque amm_entry_t type and includes routines to obtain the starting and ending addresses, size and attributes associated with the entry.
Implementing an address map as a collection of map entries requires that the AMM be able to split and join map entries as the attributes of addresses change. An entry is split into two entries when some sub-range of the entry changes attributes. Analogously, two entries which are adjacent may be joined when the attributes of one change to be identical to those of the other.
The AMM library provides hooks to allow the user to associate additional state with map entries. These hooks include explicit map entry parameters to some routines as well as callback interfaces to handle allocation, deallocation, splitting and joining map entries. Section 26.5 contains complete details.
Though the AMM is general enough to allow the user to associate arbitrary attributes with address map entries, one of the most common uses of address maps involves keeping track of which elements of a resource are free and which are available.
The AMM library provides an interface to make this “simple” use more convenient and, to some extent, more efficient. It is important to note that the simple interfaces are just wrappers for the generic interfaces described in Section 26.5. They are not a separate implementation. Thus, simple and generic routines can be called for the same map.
In the simple interface, the AMM pre-defines three attribute values: AMM_ALLOCATED, AMM_FREE, and AMM_RESERVED, and provides a set of routines that knows their semantics. Addresses that are AMM_ALLOCATED represent resources that are in use and unavailable until freed. Addresses that are AMM_FREE represent resources that are available for allocation. AMM_RESERVED addresses represent “out of range” resources that can not be allocated or freed.
amm_init performs the one-time initialization of an address map including restricting the “valid” range of addresses. Addresses within the specified range are marked as free and all others marked as reserved. amm_reserve allows additional areas of the address map to be reserved. This can be used to represent “holes” within an otherwise contiguous address map. amm_allocate allocates a range of a given size from the valid portion of the address map. This routine includes a “hint” address indicating where to start searching for free space in which to locate the range. Finally, amm_deallocate can be used to free a range of allocated space.
This set of routines is sufficient to implement basic resource management similar to that provided by UNIX resource maps. For example:
|
Three additional routines enable the simple interface to be used for another common OS usage: managing process/task address spaces. amm_protect changes the attributes associated with a range of the map. Attributes are restricted to whatever can be described in the flag word and should not clash with the AMM_ALLOCATED, AMM_FREE, and AMM_RESERVED bits, but there are typically only a small number of address space protection bits anyway so this isn’t likely to be a problem. amm_find_addr looks up an address, returning a pointer to the entry containing the address. A final function, amm_iterate takes a function pointer and calls that function for every entry in the map, passing the map and map entry pointers as arguments. This allows the user to traverse the map, examining each entry in turn.
When using the simple AMM interface, map entries are allocated with malloc, deallocated with free, and the default library routines are used to split and join entries based on the attributes in the flag word.
The more general AMM interface routines provide the same basic capability as the simple interface. amm_init_gen provides the one-time initialization of a map, amm_find_gen locates an address range in a map, amm_modify changes the attributes of an address range, and amm_iterate_gen allows a user-provided function to be called for selected entries in a map.
The primary differences between the two interfaces are that the generic interface allows fine-grained control over the selection of addresses and attributes within a map and it permits user-directed allocation and management of address map entries.
Fine-grained control of address selection enables the user to specify exact alignment and offset criteria when attempting to find a range of addresses in a map using amm_find_gen. For example, an address space manager can allocate arbitrary-sized, page-aligned address ranges using this technique.
Similarly, fine-grained control of attribute selection enables inexact attribute matches when locating an address range using amm_find_gen. In the address space manager example, this would allow an address space deallocation routine to match any allocated map entry regardless of its additional protection bits. These mask and match parameters are also used in amm_iterate_gen to selectively iterate over entries in a map.
User-directed allocation and management of entries allows the user to embed the standard amm_entry_t structure in a larger application specific structure thus associating additional state with each entry. Allocation control is addressed in two ways. First, is by providing explicit map entry parameters to amm_init_gen and amm_modify, the two routines that result in an entry being added to a map. In this way, the caller can pass in the wrapped amm_entry_t structure to use. Second, as part of the amm_init_gen call, the user can register a routine to be called when a map entry is to be split. Since entry splitting results in one or two new entries being created, this routine allows the user to provide the wrapped entries to use.
User-directed management is attained through the above allocation hooks as well as additional initialization-time registered callback routines for joining and deallocation of map entries. The join routine permits the user to determine if two entries which are adjacent in address and have equivalent attributes flags can be coalesced into a single entry. If they can be joined, this routine is responsible for merging the extended attribute information and returning a new entry with this state. The deallocation routine enables user control over situations where the AMM library destroys map entries, either left over entries from a join operation or entries that are completely replaced by a single entry in amm_modify. This routine is responsible for freeing the extended attribute information.
As an example of a non-trivial use of AMM, consider a Fluke address space manager which maintains a map to describe the address space in which threads run. In Fluke, an address space is populated with memory by mapping memory from other address spaces into the space using kernel-managed mapping objects. Hence each allocated area of the address space would be described by a composite entry consisting of an amm_entry_t structure and a Fluke mapping object:
|
Note that unallocated (AMM_FREE) entries don’t need to have mapping objects associated with them and could just be standard amm_entry_t structures. Thus, a user-provided entry allocation routine can create and return the appropriate structure depending on whether it is for an allocated or free entry. In the case of allocated map entries, the Fluke mapping object can be created at this time. Similarly, a user-provided deallocation routine can free an entry appropriately, destroying mapping objects as necessary:
|
Address space is allocated, freed, or the protections changed, using amm_modify. Here the address space manager first creates an entry of the correct type, creating and initializing the mapping object as necessary. It then calls amm_modify with that entry:
|
Note that since AMM_FREE entries are just standard amm_entry_t structures, it is not necessary to pass amm_modify an explicit entry parameter when freeing address space. In this situation, amm_modify will call the user-provided allocation routine which will allocate a basic map entry structure based on the fact that the flag parameter is AMM_FREE. This works since no user initialization of the amm_entry_t is required. In general, the parameters passed to the allocation routine do not provide sufficient information to initialize user-extended attributes and thus these entries must be initialized and passed to amm_modify.
In amm_modify, if the modification results in an entry being split, the user-provided split routine is called with the entry and an address at which the entry is to be broken. The split routine will create a new entry of the appropriate type, creating and initializing a Fluke mapping object if necessary. It then adjusts any Fluke mapping object associated with the existing entry to reflect the split and returns both objects.
After isolating the range identified by the address and size parameters, amm_modify discards it by calling the user-provided deallocation routine for every entry within the range. The deallocation routine will destroy any Fluke mapping object associated with an entry.
Once the address range has been cleared, amm_modify inserts the user-provided entry in the map. The newly inserted entry may now be compatible with one or both of its neighbors in which case the user-provided join routine is called (possibly twice) with the entries to join as parameters. If the entries can be merged, the join routine modifies one of the existing entries to cover the joined range and returns a pointer to that entry. Note that, even though the map entry addresses and attributes are compatible to join, the user-provided join routine may choose not to join them. In this example, it is possible that the source addresses of the two mapping objects are not adjacent and hence the two mappings cannot be combined into one. Thus, the join function will fail and the two entries will remain separate.
The following code illustrates the split and join functions described:
|
Finally, the address space manager may want to perform some operation on only selected parts of the address space. For example, assume it wants to write-protect some arbitrary subset of the address space. Write protecting should only be done to the parts of the address space which are actually allocated (i.e., not free or reserved) and, for efficiency, only on those parts which currently allow write access (i.e., include FLUKE_PROT_WRITE in their attributes). Here it could use amm_iterate_gen to process the map matching only those entries which are allocated and have write permission. Amm_modify can then be used on those entries to write-protect them as follows:
|
The AMM library requires only four external routines. AMM uses smalloc and sfree (Section 14.5) to allocate and free entries for maps which don’t specify an allocator (see amm_init_gen). The amm_dump routine uses printf (Section 14.6) to generate output. Various routines use panic (Section 14.8.3) when an internal consistency check fails.
The following sections describe the functions exported by the AMM in detail. All of these functions, as well as the types necessary to use them, are defined in the header file <oskit/amm.h>.
#include <oskit/amm.h>
amm_entry_t *amm_alloc_func(amm_t *amm, oskit_addr_t addr, oskit_size_t size, int flags);
User-provided function called whenever an AMM entry needs to be allocated in the given map amm. The allocation function for an AMM is set at initialization time by passing a pointer to it as a parameter to amm_init_gen.
The parameters to amm_alloc_func provide information about the entry being created; i.e., the entry will cover the range [addr - addr+size-1] and have the attributes specified in flags.
If the map is using extended map entries, this routine should initialize the extended portion of the entry. No initialization of the AMM-private portion is necessary.
Returns a pointer to the uninitialized, AMM-private part of the allocated entry, or zero if no memory can be allocated.
amm_init_gen
#include <oskit/amm.h>
int amm_allocate(amm_t *amm, [in/out] oskit_addr_t *addrp, oskit_size_t size, int prot);
Looks for a range of the indicated size with flags AMM_FREE and modifies it to have the attributes AMM_ALLOCATED|prot.
On call, *addrp specifies a hint address at which to start searching for a range of the desired size. The search will progress toward higher addresses from that point. If no range is found before the maximum possible address the search “wraps around,” starting from the lowest address and searching forward until it reaches the original hint address. If no free range of sufficient size is found, ENOMEM is returned.
Amm_allocate is a simplified interface to amm_modify intended to be used with amm_init, amm_deallocate, amm_protect, and amm_reserve.
Returns zero if successful, an error code otherwise.
amm_deallocate, amm_init, amm_modify, amm_protect, amm_reserve
Marks a range of address space as AMM_FREE. Only pieces of the range marked as AMM_ALLOCATED (e.g., allocated with amm_allocate) are “freed,” all other regions are ignored.
Amm_Deallocate is a simplified interface to amm_modify intended to be used with amm_init, amm_allocate, amm_protect, and amm_reserve.
Returns zero if successful, an error code otherwise.
amm_allocate, amm_init, amm_modify, amm_protect, amm_reserve
Free all the address map entries associated with the map amm. The user-provided free function is called for every entry in the map. If no free function is associated with the map, the standard libc free function is used.
amm_free_func
This routine is primarily used for debugging the AMM and the code that uses it. It scans through the AMM and calls printf to display the AMM-private data for each entry in it.
#include <oskit/amm.h>
oskit_addr_t amm_entry_start(amm_entry_t *entry);
oskit_addr_t amm_entry_end(amm_entry_t *entry);
Macros provided to access AMM-private data members. Currently defined are macros to return the starting and ending virtual addresses of the entry as well as the size and attributes of the range covered by the entry.
Returns a data member of the appropriate type.
Locates the map entry describing the given address in the map amm and returns a pointer to it. Since AMM maps contain every possible address in some entry, this routine will always succeed; i.e., it will always return a valid amm_entry_t pointer.
AMM-private fields of the returned entry can be queried with the amm_entry_field macros.
Returns a pointer to the entry containing the desired address.
#include <oskit/amm.h>
amm_entry_t *amm_find_gen(amm_t *amm, [in/out] oskit_addr_t *addrp, oskit_size_t size, int flags, int flagmask, int align_bits, oskit_addr_t align_off, int find_flags);
Returns a pointer to a map entry in the map amm with the indicated attributes which contains an address range of the given size and alignment. If no range can be found, amm_find_gen returns zero.
On call, *addrp contains a “hint” at which to start searching for the range. On a successful return, *addrp contains the address chosen; i.e., [*addrp - *addrp+size-1] is the desired range. This address may not be the same as the start address of the chosen map entry.
Flags and flagmask specify the attributes that the returned range must match. Only entries which satisfy ((entry->flags & flagmask) == flags) are considered when looking for a range.
Align_bits and align_off specify the alignment of the returned range. Align_bits specifies an alignment boundary as a power of two, and align_ofs specifies an offset from “natural” alignment; i.e., the lowest align_bits bits of the returned address must match the lowest align_bits of align_ofs. For example, align_bits == 12 and align_ofs == 8 would return a range starting 8 bytes past a 4096 byte boundary.
Find_flags can be used to modify the behavior of the lookup:
AMM_EXACT_ADDR. Range must start at the specified address. If that address is unsuitable, amm_find_gen returns zero.
AMM_FORWARD. Search forward from the hint address looking for a match. This is the default behavior.
AMM_BACKWARD. Search backward from the hint address looking for a match. Not implemented.
AMM_FIRSTFIT. Return the first entry found that contains a suitable range. This is the default behavior.
AMM_BESTFIT. Of all entries containing a suitable range, return the entry which is the closest fit. Not implemented.
Returns a pointer to the entry containing the desired range, or zero if no suitable range could be found.
User-provided function called whenever an AMM entry needs to be deallocated from the given map amm. The free function for an AMM is set at initialization time by passing a pointer to it as a parameter to amm_init_gen.
The range and attributes of the entry can be obtained using the amm_entry_field macros.
If the map is using extended map entries, this routine should clean up any map-private data before deallocating the entry.
amm_entry_field , amm_init_gen
This function initializes an address map as it would be used in most “simple” applications. The caller must provide a pointer to an amm_t structure; the AMM system uses this structure to keep track of the state of the address map. In subsequent AMM operations, the caller must pass a pointer to the same amm_t structure, which acts as a handle for the address map.
The address range [lo - hi-1] forms the valid area of the map. A single map entry is created for that range with attribute AMM_FREE so that all addresses within the range are eligible for allocation with amm_allocate. If necessary, entries are created for the ranges [AMM_MINADDR - lo-1] and [hi - AMM_MAXADDR] with attribute AMM_RESERVED so that addresses within those ranges are ignored by other simple interface routines.
Amm_Init is a simplified interface to amm_init_gen intended to be used with amm_allocate, amm_deallocate, amm_protect and amm_reserve.
amm_allocate, amm_deallocate, amm_modify, amm_protect, amm_reserve
#include <oskit/amm.h>
void amm_init_gen(amm_t *amm, int flags, amm_entry_t *entry, amm_entry_t *(*amm_alloc_func)(), void (*amm_free_func)(), int (*amm_split_func)(), int (*amm_join_func)());
This function initializes an address map. The caller must provide a pointer to an amm_t structure; the AMM system uses this structure to keep track of the state of the address map. In subsequent AMM operations, the caller must pass a pointer to the same amm_t structure, which acts as a handle for the address map.
The map is initialized to contain a single entry describing the maximum possible address range [AMM_MINADDR - AMM_MAXADDR] and have the attributes specified in flags. If the entry parameter is non-zero, it is used as the initial entry. This allows the caller to allocate a structure larger than the basic amm_entry_t and store additional attribute data in the extended structure. If the caller supplies such an entry they must have initialized any caller-private data in that entry, but amm_init_gen will initialize the AMM-private part (the actual amm_entry_t). If entry is zero, a standard entry will be allocated using the default or caller-provided entry allocation routine (described below).
The four function pointer parameters permit the caller to customize AMM entry management on a per-AMM basis. If non-zero, amm_alloc_func and amm_free_func specify routines that the AMM library will callout to whenever an AMM entry is to be created or destroyed. If zero, malloc and free are used to manage basic amm_entry_t structures.
If non-zero, amm_split_func and amm_join_func specify routines that the AMM library will callout to whenever an AMM entry needs to be split or two entries need to be joined. If zero, default split and join calls are used. Split and join calls only occur as a side-effect of an amm_modify call.
When using extended AMM structures, the caller needs to provide free, split and join functions. The alloc function is not strictly necessary since the two AMM functions which create entries, amm_init_gen and amm_modify, have explicit entry parameters, and the third function which can create an entry, amm_split_func, will be caller-provided. The allocation hook is primarily provided to allow the caller control over the placement of AMM entry storage.
amm_alloc_func, amm_free_func, amm_join_func, amm_split_func
Calls a user-provided function amm_iterate_func for every entry of amm.
Arg is an opaque value which is passed to every instance of amm_iterate_func along with amm and the entry itself.
amm_iterate continues until the function has been called for all entries in the AMM or until one instance of the function returns non-zero. In the latter case, that non-zero value will be returned from amm_iterate.
Since the iteration function may modify or even destroy the entry passed in, amm_iterate uses the following technique for locating the “next” entry. At the beginning of each iteration, amm_iterate records the last address covered by the current entry. After the specified iteration function returns, amm_find_addr is called with this address to “relocate” the current entry. From this entry, amm_iterate derives the next entry.
Returns zero if amm_iterate_func returned zero for all entries. Returns the first non-zero value returned from any amm_iterate_func call.
amm_iterate_func
Function called successively by amm_iterate and amm_iterate_gen with each selected entry from the map amm. The iteration function may modify or destroy the entry passed in.
If this function returns non-zero, the iterator will stop and amm_iterate or amm_iterate_gen will return that non-zero value. Returning zero will continue the iteration.
Should return zero if the iteration is to continue, non-zero otherwise.
amm_iterate, amm_iterate_gen
#include <oskit/amm.h>
int amm_iterate_gen(amm_t *amm, int (*amm_iterate_func)(), void *arg, oskit_addr_t addr, oskit_size_t size, int flags, int flagmask);
Calls a user-provided function amm_iterate_func for every entry of amm which falls partially or completely in the range [addr - addr+size-1] and matches the given attribute criteria.
Arg is an opaque value which is passed to every instance of amm_iterate_func (along with amm and the entry itself).
Flags and flagmask specify the attributes that an entry in the range must match for amm_iterate_func to be invoked. Only entries with ((entry->flags & flagmask) == flags) are considered.
amm_iterate_gen continues until the function has been called for all appropriate entries in the range or until one instance of the function returns non-zero. In the latter case, that non-zero value will be returned from amm_iterate_gen.
Since the iteration function may modify or even destroy the entry passed in, amm_iterate_gen uses the following technique for locating the “next” entry. At the beginning of each iteration, amm_iterate_gen records the last address covered by the current entry. After the specified iteration function returns, amm_find_addr is called with this address to “relocate” the current entry. From this entry, amm_iterate_gen derives the next entry.
Returns zero if amm_iterate_func returned zero for all entries. Returns the first non-zero value returned from any amm_iterate_func call.
amm_iterate_func
#include <oskit/amm.h>
int amm_join_func(amm_t *amm, amm_entry_t *head, amm_entry_t *tail, [out] amm_entry_t **new);
User-provided function called whenever the AMM thinks that two map entries for the map amm can be joined, based on comparison of the their flag words. The join function for an AMM is set at initialization time by passing a pointer to it as a parameter to amm_init_gen.
Head and tail are the two entries to join. If the join is successful, a pointer to the joined entry is returned in new. The returned entry may be one of the two entries passed in or it may be an entirely new entry. The AMM will call the entry free function for any “left-over” entries on return from a successful join call.
This routine is responsible for merging the map-private attributes of the two entries if they can be joined.
If the map-private attributes of the two entries are incompatible, the call should return non-zero to prevent the caller from reflecting the join in the map. Failure to join two entries is not an error, and the return code will not be propagated up through the call chain.
amm_join_func is only called by amm_modify.
Returns zero if the join was successful, non-zero if not.
amm_init_gen, amm_modify
#include <oskit/amm.h>
int amm_modify(amm_t *amm, oskit_addr_t addr, oskit_size_t size, int flags, amm_entry_t *entry);
Creates a new map entry in amm describing the range [addr - addr+size-1] with the attributes indicated in flags.
Any existing map entries wholly within the range are deleted, any that partly overlap the range are split as necessary. After adding the new entry, the AMM may attempt to join it with adjacent already-existing entries if the flag words are compatible.
If entry is zero, a standard amm_entry_t structure is allocated for the new range. If entry is non-zero, the caller must have already allocated and initialized any extra attribute data in the extended entry. In either case, the AMM will initialize the private part of the new entry, including setting its attribute flags to flags.
Returns zero if the modification was successful, non-zero if an entry split failed.
amm_alloc_func, amm_free_func, amm_join_func, amm_split_func
Modifies the attribute flags associated with with all AMM_ALLOCATED entries within the specified address range. The resulting attributes are AMM_ALLOCATED|prot. AMM_RESERVED and AMM_FREE areas within the range are ignored.
Amm_Protect is a simplified interface to amm_modify intended to be used with amm_init, amm_allocate, amm_deallocate, and amm_reserve.
Returns zero if successful, an error code otherwise.
amm_allocate, amm_deallocate, amm_init, amm_modify, amm_reserve
Mark the specified address range as AMM_RESERVED. All entries within the range are effected regardless of existing attributes.
Amm_Reserve is a simplified interface to amm_modify intended to be used with amm_init, amm_allocate, amm_deallocate, and amm_protect.
Returns zero if successful, an error code otherwise.
amm_allocate, amm_deallocate, amm_init, amm_modify, amm_protect
Return a map entry in amm describing the range [addr - addr+size-1]. If either the start or end address is contained within an entry, the entry is split to create one starting or ending at the desired address.
Note that the desired range may still be described by multiple entries. Amm_select only guarantees that there is an entry starting at addr and an entry ending at addr+size-1.
This function returns a pointer to the selected entry. In the event that the desired range is described by multiple entries, amm_select returns the first entry. Successive entries may be obtained using amm_find_addr using the end address of the current entry (amm_entry_end).
Returns a pointer to the first entry describing the range.
amm_split_func, amm_find_addr, amm_entry_field
#include <oskit/amm.h>
int amm_split_func(amm_t *amm, amm_entry_t *entry, oskit_addr_t split_addr, [out] amm_entry_t **head, [out] amm_entry_t **tail);
User-provided function called whenever the AMM needs to split an entry in map amm due to conflicting flags. The split function for an AMM is set at initialization time by passing a pointer to it as a parameter to amm_init_gen.
Entry is the entry to be split and split_addr is the address at which to split it. If the split is successful, head and tail are pointers to the resulting entries describing the ranges [amm_entry_start(entry) - split_addr-1] and [split_addr - amm_entry_end(entry)-1] respectively. Both may be entirely new entries allocated in this routine, or one may point to the modified original entry. The AMM will call the entry free function for the original entry if it is not one of the returned values.
This routine is responsible for initializing the map-private attributes of the resulting new entries.
If the split cannot be done, e.g., due to lack of resources, a non-zero value indicating the error should be returned. A non-zero return value is propagated on to whoever performed the action which triggered the split request.
amm_split_func is only called by amm_modify.
Returns zero if the split was successful, non-zero if not.
amm_init_gen