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:
#include <oskit/amm.h>
#include <fluke/mapping.h>
struct as {
amm_t map;
...
}
struct as_entry {
amm_entry_t entry;
fluke_mapping_t mapping;
};
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:
amm_entry_t *as_entry_alloc(amm_t *amm, oskit_addr_t addr, oskit_size_t size, int flags)
{
struct as_entry *aentry;
if (flags == AMM_FREE)
return malloc(sizeof(amm_entry_t));
if ((aentry = malloc(sizeof *aentry)) == 0)
return 0;
if (fluke_mapping_create(&aentry->mapping)) {
free(aentry);
return 0;
}
return &aentry->entry;
}
void as_entry_free(amm_t *amm, amm_entry_t *entry)
{
struct as_entry *aentry;
if (amm_entry_flags(entry) == AMM_FREE)
free(sizeof *entry);
else {
aentry = (struct as_entry *)entry;
fluke_mapping_destroy(&aentry->mapping);
free(sizeof *aentry);
}
}
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:
int as_allocate(struct as *map, oskit_addr_t addr, oskit_size_t size, int prot)
{
struct as_entry *aentry;
int rc;
/* check range to ensure it is available, etc. */
...
aentry = (struct as_entry *)as_entry_alloc(&map->amm, addr, size, prot|AMM_ALLOCATED);
/* setup Fluke mapping state */
...
fluke_mapping_set_state(&aentry->mapping, ...);
rc = amm_modify(&map->amm, addr, size, prot|AMM_ALLOCATED, &aentry->entry);
...
}
int as_deallocate(struct as *map, oskit_addr_t addr, oskit_size_t size)
{
int rc;
/* as_entry_free will destroy all Fluke mappings */
rc = amm_modify(&map->amm, addr, size, AMM_FREE, 0);
...
}
int as_protect(struct as *map, oskit_addr_t addr, oskit_size_t size, int prot)
{
struct as_entry *aentry;
int rc;
/* check range to ensure it is allocated, etc. */
...
aentry = (struct as_entry *)as_entry_alloc(&map->amm, addr, size, prot|AMM_ALLOCATED);
/* setup Fluke mapping state */
...
fluke_mapping_set_state(&aentry->mapping, ...);
rc = amm_modify(&map->amm, addr, size, prot|AMM_ALLOCATED, &aentry->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:
int as_entry_split(amm_t *amm, amm_entry_t *entry, oskit_addr_t addr,
amm_entry_t **head, amm_entry_t **tail)
{
amm_entry_t *nentry;
struct as_entry *aentry;
int flags = amm_entry_flags(entry);
nentry = as_entry_alloc(amm, addr, amm_entry_end(entry) - addr, flags);
if (nentry == 0)
return ENOMEM;
*head = entry;
*tail = nentry;
if (flags == AMM_FREE)
return 0;
/* Modify existing Fluke mapping for first half of range */
aentry = (struct as_entry *)entry;
...
fluke_mapping_set_state(&aentry->mapping, ...);
/* Setup new Fluke mapping for last half of range */
aentry = (struct as_entry *)nentry;
...
fluke_mapping_set_state(&aentry->mapping, ...);
return 0;
}
int as_entry_join(amm_t *amm, amm_entry_t *head, amm_entry_t *tail, amm_entry_t **new)
{
struct as_entry *aentryh, *aentryt;
int flags = amm_entry_flags(head);
*new = head;
/* Basic entries are always joined */
if (flags == AMM_FREE)
return 0;
/* Sources of mappings must be adjacent to join */
aentryh = (struct as_entry *)head;
aentryt = (struct as_entry *)tail;
if (mapping_source(&aentryh->mapping) + amm_entry_size(entry) !=
mapping_source(&aentryt->mapping))
return 1;
/* Collapse range of two Fluke mappings into head mapping */
...
fluke_mapping_set_state(&aentryh->mapping, ...);
/* Caller will deallocate tail mapping via as_entry_free */
return 0;
}
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:
int as_write_protect(struct as *map, oskit_addr_t addr, oskit_size_t size)
{
return amm_iterate_gen(&map->amm, as_wp_func, 0, addr, size,
AMM_ALLOCATED|FLUKE_PROT_WRITE,
AMM_ALLOCATED|FLUKE_PROT_WRITE);
}
int as_wp_func(amm_t *amm, amm_entry_t *entry, void *arg)
{
struct as_entry *aentry = (struct as_entry *)entry;
/* Tweak permission of Fluke mapping to remove write permission */
...
fluke_mapping_set_state(&aentry->mapping, ...);
/* Modify the existing AMM entry, removing write permission */
rc = amm_modify(&map->amm, amm_entry_start(entry), amm_entry_size(entry),
amm_entry_flags(entry) & ~FLUKE_PROT_WRITE, entry);
...
return 0;
}