diff options
Diffstat (limited to 'libhurd-mm/as.c')
| -rw-r--r-- | libhurd-mm/as.c | 979 |
1 files changed, 929 insertions, 50 deletions
diff --git a/libhurd-mm/as.c b/libhurd-mm/as.c index 01cd130..62430ef 100644 --- a/libhurd-mm/as.c +++ b/libhurd-mm/as.c @@ -1,66 +1,945 @@ -/* as.c - Address space management. - Copyright (C) 2004, 2005 Free Software Foundation, Inc. +/* as.c - Address space construction utility functions. + Copyright (C) 2007 Free Software Foundation, Inc. Written by Neal H. Walfield <neal@gnu.org>. This file is part of the GNU Hurd. The GNU Hurd is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License as - published by the Free Software Foundation; either version 2, or (at - your option) any later version. - - The GNU Hurd is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU Hurd is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received a copy of the GNU General Public License - along with the GNU Hurd; see the file COPYING. If not, write to - the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, - USA. */ - -#if HAVE_CONFIG_H -#include <config.h> + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ + +#include "as.h" +#include "storage.h" + +#include <hurd/folio.h> +#include <hurd/cap.h> +#include <hurd/btree.h> +#include <hurd/slab.h> +#include <l4/types.h> + +#include <string.h> + +/* The top of the data address space. */ +#if L4_WORDSIZE == 32 +#define DATA_ADDR_MAX (0xC0000000ULL) +#else +#error define DATA_ADDR_MAX #endif -#include "priv.h" +/* Set to true before as_init returns. Indicates that the shadow page + table structures may be used, etc. */ +bool as_init_done; + +#if 0 +/* We keep track of cappages that have slots appropriate for storing + regions with depth < /20, < /28 and < /36. This allows for fast + allocation of subtrees. */ +struct cappage +{ + btree_node_t node; + + struct cappage *next; + struct cappage **prevp; + + union + { + struct cap *cap; + struct cappage *parent; + }; + /* If this cappage describes an unallocated cappage, then this + cappage is a place holder. That is, the cappage is elidged via + the use of a guard. In this case, PARENT points to the parent + cappage. Be careful: this may also be a placeholder. SLOT + describes which slot in PARENT this page is a place for. */ + unsigned char is_placeholder: 1; + unsigned char slot; -struct as as; + /* Number of free caps. */ + short free; + /* Which caps are allocated. */ + unsigned char alloced[CAPPAGE_SLOTS / 8]; +}; + +/* List of cappages with free slots that dominate subtrees with height + less than PAGESIZE + (i + 1) * CAPPAGE_SLOTS_LOG2. */ +#define DEPTHS \ + ((ADDR_BITS - PAGESIZE_LOG2 + CAPPAGE_SLOTS_LOG2 - 1) / CAPPAGE_SLOTS_LOG2) +static struct cappage *depth[DEPTHS]; +#define DEPTH(width) \ + ({ \ + int d_; \ + if ((width) <= PAGESIZE_LOG2) \ + d_ = 0; \ + else \ + d_ = ((width) - PAGESIZE_LOG2) / CAPPAGE_SLOTS_LOG2; \ + d_; \ + }) + +static void +link (struct cappage **list, struct cappage *e) +{ + e->next = *list; + if (e->next) + e->next->prevp = &e->next; + e->prevp = list; + *list = e; +} + +static void +unlink (struct cappage *e) +{ + assert (e->next); + assert (e->prevp); -/* Find a free region of the virtual address space for a region of - size SIZE with alignment ALIGN. Must be called with the map lock. - The lock msut not be dropped until the virtual address is entered - into the mapping database (and this function should not be called - again until that has happened). */ -uintptr_t -as_find_free (size_t size, size_t align) + *e->prevp = e->next; + if (e->next) + e->next->prevp = e->prevp; +} + +addr_t +as_alloc (int width, l4_uint64_t count, bool data_mappable) { - /* Start the probe at the lowest address aligned address after - VIRTUAL_MEMORY_START. FIXME: We should use a hint. But then, we - shouldn't use linked lists either. */ - l4_word_t start = (VIRTUAL_MEMORY_START + align - 1) & ~(align - 1); - bool ok; - struct map *map; + int d = DEPTH (width); + + /* Grab is the number of levels above D to which we have to go to + get a slot. */ + int grab = 0; + for (grab = 0; d + grab < sizeof (depth) / sizeof (depth[0]); grab ++) + if (depth[d + grab]) + break; + + struct cappage *cappage = depth[d + grab]; + + int slot = bit_alloc (cappage->alloced, sizeof (cappage->alloced), 0); + assert (slot != -1); + cappage->free --; - do + int i; + for (i = 0; i < grab; i ++) { - /* The proposed start is free unless proven not to be. */ - ok = true; - - /* Iterate over all of the maps and see if any intersect. If - none do, then we have a good address. */ - for (map = hurd_btree_map_first (&as.mappings); map; - map = hurd_btree_map_next (map)) - if (overlap (start, size, map->vm.start, map->vm.size)) - { - ok = false; - /* Use the next aligned virtual address after MAP. */ - /* FIXME: We need to check that we don't overflow. */ - start = (map->vm.start + map->vm.size + align - 1) & ~(align - 1); - break; - } + struct cappage *placeholder = cappage_alloc (); + + placeholder->parent = cappage; + placeholder->is_placeholder = true; + placeholder->slot = slot; + placeholder->free = CAPPAGE_SLOTS - 1; + + link (&depth[d + i], placeholder); + = cappage + } - while (! ok); - return start; + addr_t addr = addr_extend (cappage->cap->self, slot, CAPPAGE_SLOTS_LOG2); + addr = addr_extend (addr, 0, grab * CAPPAGE_SLOTS_LOG2); + + int guard_depth = ADDR_BITS - addr_depth (cappage->cap->self) + - CAPPAGE_SLOTS_LOG2 - width; + + + /* When we grab, we don't want to actually allocate the slot as it + would be possible to insert a cappage in place of the extra + guard. What to do... If we grab, should we always just insert a + cappage? */ + + struct object *object = cap_to_object (cappage->cap); + assert (object); + + CAP_SET_GUARD (object->caps[i], 0, guard_depth); + + return addr_extend (addr, 0, guard_depth); +} + +#endif + +/* We keep track of the regions which are unallocated. These regions + are kept in a btree allowing for fast allocation, fast searching + and fast insertion and deletion. + + The maximum number of free regions is the number of allocated + regions plus one. As each free region requires a constant amount + of memory, the memory required to maintain the free regions is + O(number of allocated regions). */ +struct region +{ + l4_uint64_t start; + l4_uint64_t end; +}; + +struct free_space +{ + hurd_btree_node_t node; + struct region region; +}; + +/* Compare two regions. Two regions are considered equal if there is + any overlap at all. */ +static int +region_compare (const struct region *a, const struct region *b) +{ + if (a->end < b->start) + return -1; + if (a->start > b->end) + return 1; + /* Overlap. */ + return 0; +} + +BTREE_CLASS (free_space, struct free_space, struct region, region, node, + region_compare) + +/* The list of free regions. */ +hurd_btree_free_space_t free_spaces; + +static struct hurd_slab_space free_space_desc_slab; + +static error_t +free_space_desc_slab_alloc (void *hook, size_t size, void **ptr) +{ + assert (size == PAGESIZE); + + addr_t storage = storage_alloc (meta_data_activity, + cap_page, STORAGE_LONG_LIVED, ADDR_VOID); + *ptr = ADDR_TO_PTR (storage); + + return 0; +} + +static error_t +free_space_desc_slab_dealloc (void *hook, void *buffer, size_t size) +{ + assert (size == PAGESIZE); + + addr_t addr = PTR_TO_ADDR (buffer); + storage_free (addr, false); + + return 0; +} + +static struct free_space * +free_space_desc_alloc (void) +{ + void *buffer; + error_t err = hurd_slab_alloc (&free_space_desc_slab, &buffer); + if (err) + panic ("Out of memory!"); + return buffer; +} + +static void +free_space_desc_free (struct free_space *free_space) +{ + hurd_slab_dealloc (&free_space_desc_slab, free_space); +} + +/* The sub-region starting at start byte START and endinging at byte + END is completely covered by the free region F. Carve it out of + F. */ +static void +free_space_split (struct free_space *f, l4_uint64_t start, l4_uint64_t end) +{ + /* START and END must be inside F. */ + assert (f->region.start <= start); + assert (end <= f->region.end); + + if (start == f->region.start && end == f->region.end) + /* We completely consume the free region. Remove it. */ + { + hurd_btree_free_space_detach (&free_spaces, f); + free_space_desc_free (f); + } + else if (start == f->region.start) + /* We overlap with the start of the region, just shrink it. */ + f->region.start = end + 1; + else if (end == f->region.end) + /* We overlap with the end of the region, just shrink it. */ + f->region.end = start - 1; + else + /* We split the region. */ + { + struct free_space *new = free_space_desc_alloc (); + new->region.start = end + 1; + new->region.end = f->region.end; + f->region.end = start - 1; + + struct free_space *f = hurd_btree_free_space_insert (&free_spaces, new); + if (f) + debug (1, "%llx-%llx overlaps with %llx-%llx", + start, end, f->region.start, f->region.end); + assert (! f); + } +} + +addr_t +as_alloc (int width, l4_uint64_t count, bool data_mappable) +{ + assert (count); + int shift = l4_lsb64 (count) - 1; + int w = width + shift; + count >>= shift; + if (! data_mappable) + /* We have some latitude regarding where we can place the mapping. + Use it to ease page table construction. */ + { + if (w <= 4) + w = 4; + else if (w <= PAGESIZE_LOG2) + w = PAGESIZE_LOG2; + else + /* Make W - PAGESIZE_LOG2 a multiple of CAPPAGE_SLOTS_LOG2; + this greatly simplifies page table construction. */ + w += (CAPPAGE_SLOTS_LOG2 + - ((w - PAGESIZE_LOG2) % CAPPAGE_SLOTS_LOG2)); + } + + l4_uint64_t align = 1ULL << w; + l4_uint64_t length = align * count; + + struct free_space *free_space; + for (free_space = hurd_btree_free_space_first (&free_spaces); + free_space; + free_space = hurd_btree_free_space_next (free_space)) + { + l4_uint64_t start; + start = (free_space->region.start + align - 1) & ~(align - 1); + + if (start < free_space->region.end + && length <= (free_space->region.end - start) + 1) + /* We found a fit! */ + { + if (data_mappable && start + length - 1 >= DATA_ADDR_MAX) + /* But it must be mappable and it extends beyond the end + of the address space! */ + return ADDR_VOID; + + free_space_split (free_space, start, start + length - 1); + return ADDR (start, ADDR_BITS - (w - shift)); + } + } + + return ADDR_VOID; +} + +bool +as_alloc_at (addr_t addr, l4_uint64_t count) +{ + l4_uint64_t start = addr_prefix (addr); + l4_uint64_t length = (1ULL << (ADDR_BITS - addr_depth (addr))) * count; + l4_uint64_t end = start + length - 1; + + struct region region = { start, end }; + struct free_space *f; + f = hurd_btree_free_space_find (&free_spaces, ®ion); + if (! f) + return false; + + if (! (f->region.start <= start && end <= f->region.end)) + return false; + + free_space_split (f, start, end); + return true; +} + +void +as_free (addr_t addr, l4_uint64_t count) +{ + l4_uint64_t start = addr_prefix (addr); + l4_uint64_t length = (1ULL << (ADDR_BITS - addr_depth (addr))) * count; + l4_uint64_t end = start + length - 1; + + struct free_space *space = free_space_desc_alloc (); + /* We prefer to coalesce regions where possible. This ensures that + if there is overlap, we bail. */ + space->region.start = start == 0 ? 0 : start - 1; + space->region.end = end == -1ULL ? -1ULL : end + 1; + + struct free_space *f = hurd_btree_free_space_insert (&free_spaces, space); + if (f) + /* We failed to insert. This mean that we can coalesce. */ + { + free_space_desc_free (space); + + assert (f->region.end + 1 == start || end + 1 == f->region.start); + + struct free_space *prev; + struct free_space *next; + + if (f->region.end + 1 == start) + { + prev = f; + next = hurd_btree_free_space_next (f); + } + else + { + prev = hurd_btree_free_space_prev (f); + next = f; + } + + if (prev && next + && prev->region.end + 1 == start && end + 1 == next->region.start) + /* We exactly fill a hole and have to free one. */ + { + prev->region.end = next->region.end; + hurd_btree_free_space_detach (&free_spaces, next); + free_space_desc_free (next); + } + else if (prev && prev->region.end + 1 == start) + prev->region.end = end; + else + { + assert (next); + assert (end + 1 == next->region.start); + next->region.start = start; + } + } + else + /* We cannot coalesce. Just fix the region descriptor. */ + { + space->region.start = start; + space->region.end = end; + } +} + +static struct as_insert_rt +allocate_object (enum cap_type type, addr_t addr) +{ + struct as_insert_rt rt; + + assert (type == cap_page || type == cap_rpage + || type == cap_cappage || type == cap_rcappage); + + memset (&rt, 0, sizeof (rt)); + rt.cap.type = cap_void; + + /* First allocate the real object. */ + addr_t storage = storage_alloc (meta_data_activity, type, + STORAGE_LONG_LIVED, ADDR_VOID); + if (ADDR_IS_VOID (storage)) + return rt; + + debug (4, "%llx/%d %s -> %llx/%d", + addr_prefix (addr), addr_depth (addr), + cap_type_string (type), + addr_prefix (storage), addr_depth (storage)); + + if (type == cap_cappage || type == cap_rcappage) + { + /* Then, allocate the shadow object. */ + addr_t shadow = storage_alloc (meta_data_activity, cap_page, + STORAGE_LONG_LIVED, ADDR_VOID); + if (ADDR_IS_VOID (shadow)) + { + storage_free (storage, false); + return rt; + } + cap_set_shadow (&rt.cap, ADDR_TO_PTR (shadow)); + } + + rt.storage = storage; + rt.cap.type = type; + + return rt; +} + +struct cap * +as_slot_ensure (addr_t addr) +{ + /* The implementation is provided by viengoos. */ + extern struct cap * as_slot_ensure_full (activity_t activity, + struct cap *root, addr_t a, + struct as_insert_rt + (*allocate_object) + (enum cap_type type, + addr_t addr)); + + return as_slot_ensure_full (meta_data_activity, + &shadow_root, addr, + allocate_object); +} + +#define DESC_ADDITIONAL ((PAGESIZE + sizeof (struct hurd_object_desc) - 1) \ + / sizeof (struct hurd_object_desc)) +static struct hurd_object_desc __attribute__((aligned(PAGESIZE))) + desc_additional[DESC_ADDITIONAL]; +static int desc_additional_count; + +/* Find an appropriate slot for an object. */ +addr_t +as_alloc_slow (int width, bool data_mappable, bool may_alloc) +{ + if (as_init_done) + { + addr_t addr = as_alloc (width, 1, true); + as_slot_ensure (addr); + return addr; + } + + error_t err; + + static addr_t cappage; + static int index; + + addr_t alloc_area (l4_word_t width) + { + addr_t slot; + + int find_free_slot (addr_t cap, + l4_word_t type, struct cap_addr_trans cap_addr_trans, + bool writable, + void *cookie) + { + if (! writable) + return 0; + + if (ADDR_BITS - addr_depth (cap) < width) + /* Not enough depth to map a cappage and then a page. */ + return 0; + + l4_uint64_t start = addr_prefix (cap); + l4_uint64_t end = start + (1 << width) - 1; + + if (data_mappable && end >= DATA_ADDR_MAX) + return 0; + + if (! (end < (uintptr_t) l4_kip () + || (uintptr_t) l4_kip () + l4_kip_area_size () <= start)) + /* Overlaps the KIP. */ + return 0; + + if (! (end < (uintptr_t) _L4_utcb () + || ((uintptr_t) _L4_utcb () + l4_utcb_size () <= start))) + /* Overlaps the UTCB. */ + return 0; + + addr_t *addrp = cookie; + *addrp = cap; + return 1; + } + + if (! as_walk (find_free_slot, 1 << cap_void, (void *) &slot)) + panic ("Failed to find a free slot!"); + + debug (3, "Using slot %llx/%d", addr_prefix (slot), addr_depth (slot)); + + /* Set the guard on the slot. */ + int gbits = ADDR_BITS - addr_depth (slot) - width; + assert (gbits >= 0); + + struct cap_addr_trans cap_addr_trans = CAP_ADDR_TRANS_VOID; + CAP_ADDR_TRANS_SET_GUARD (&cap_addr_trans, 0, gbits); + err = rm_cap_copy (meta_data_activity, slot, slot, + CAP_COPY_COPY_GUARD, cap_addr_trans); + if (err) + panic ("failed to copy capability: %d", err); + + return addr_extend (slot, 0, gbits); + } + + if (! data_mappable && width < PAGESIZE_LOG2) + width = PAGESIZE_LOG2; + + if (width == PAGESIZE_LOG2) + { + if ((ADDR_IS_VOID (cappage) || index == CAPPAGE_SLOTS) && may_alloc) + /* Need a new area. */ + { + cappage = alloc_area (CAPPAGE_SLOTS_LOG2 + PAGESIZE_LOG2); + addr_t storage = storage_alloc (meta_data_activity, + cap_cappage, STORAGE_LONG_LIVED, + cappage); + + if (ADDR_IS_VOID (storage)) + cappage = ADDR_VOID; + else + { + /* Reset the index. */ + index = 0; + + /* Fill in a descriptor. */ + struct hurd_object_desc *desc + = &desc_additional[desc_additional_count ++]; + if (desc_additional_count == DESC_ADDITIONAL) + panic ("Out of object descriptors!"); + desc->object = cappage; + desc->storage = storage; + desc->type = cap_cappage; + } + } + + if (! ADDR_IS_VOID (cappage)) + return addr_extend (cappage, index ++, CAPPAGE_SLOTS_LOG2); + } + + return alloc_area (width); +} + +struct cap shadow_root; + +void +as_init (void) +{ + /* First, we initialize the free region data structure. */ + error_t err = hurd_slab_init (&free_space_desc_slab, + sizeof (struct free_space), 0, + free_space_desc_slab_alloc, + free_space_desc_slab_dealloc, + NULL, NULL, NULL); + assert (! err); + + hurd_btree_free_space_tree_init (&free_spaces); + + /* We start with a tabula rasa and then remove the regions that are + actually in use. */ + as_free (ADDR (0, 0), 1); + + /* Then, we create the shadow page tables and mark the allocation + regions appropriately. */ + + void add (struct hurd_object_desc *desc) + { + error_t err; + int i; + addr_t shadow_addr; + struct object *shadow; + + debug (5, "Adding object %llx/%d", + addr_prefix (desc->object), addr_depth (desc->object)); + + /* We know that the slot that contains the capability that + designates this object is already shadowed as we shadow depth + first. */ + struct cap *cap = slot_lookup_rel (meta_data_activity, + &shadow_root, desc->object, + desc->type, NULL); + assert (cap->type == desc->type); + + switch (desc->type) + { + case cap_page: + case cap_rpage: + as_alloc_at (desc->object, 1); + return; + + case cap_cappage: + case cap_rcappage:; + /* We shadow the content of cappages. */ + + if (ADDR_BITS - addr_depth (desc->object) + < CAP_SUBPAGE_SIZE_LOG2 (cap)) + /* The cappage is unusable for addressing. */ + return; + else + /* We release the addresses used by ADDR and will fill it + in appropriately. */ + as_free (desc->object, 1); + + shadow_addr = storage_alloc (meta_data_activity, + cap_page, STORAGE_LONG_LIVED, + ADDR_VOID); + shadow = ADDR_TO_PTR (shadow_addr); + cap_set_shadow (cap, shadow); + + /* We expect at least one non-void capability per + cappage. */ + bool have_one = false; + + /* XXX: Would be nice have syscall bundling here. */ + for (i = 0; i < CAP_SUBPAGE_SIZE (cap); i ++) + { + struct cap *slot = &shadow->caps[i]; + + addr_t slot_addr = addr_extend (desc->object, + i, CAP_SUBPAGE_SIZE_LOG2 (cap)); + l4_word_t type; + err = rm_cap_read (meta_data_activity, slot_addr, + &type, &slot->addr_trans); + if (err) + panic ("Error reading cap %d: %d", i, err); + slot->type = type; + + if (type != cap_void) + { + have_one = true; + + addr_t object = addr_extend (slot_addr, CAP_GUARD (slot), + CAP_GUARD_BITS (slot)); + as_alloc_at (object, 1); + } + } + + assert (have_one); + + return; + + case cap_folio: + if (ADDR_BITS - addr_depth (desc->object) < FOLIO_OBJECTS_LOG2) + /* The folio is unusable for addressing. */ + return; + + storage_shadow_setup (cap, desc->object); + shadow = cap_get_shadow (cap); + + for (i = 0; i < FOLIO_OBJECTS_LOG2; i ++) + { + l4_word_t type; + struct cap_addr_trans addr_trans; + err = rm_cap_read (meta_data_activity, + addr_extend (desc->object, + i, FOLIO_OBJECTS_LOG2), + &type, &addr_trans); + if (err) + panic ("Error reading cap %d: %d", i, err); + + /* This is an object in a folio: it can't have a guard + or anything other than a single subpage. */ + assert (CAP_ADDR_TRANS_GUARD_BITS (addr_trans) == 0); + assert (CAP_ADDR_TRANS_SUBPAGES (addr_trans) == 1); + + shadow->caps[i].type = type; + shadow->caps[i].addr_trans = CAP_ADDR_TRANS_VOID; + + /* We do not mark folio objects as free: the address + allocator should not allocate addresses out of + them. */ + } + + return; + + case cap_void: + assert (! "void descriptor?"); + return; + + default:; + /* This object's address was already reserved when its + parent cap page was added. */ + return; + } + } + + /* Shadow the root capability. */ + l4_word_t type; + err = rm_cap_read (meta_data_activity, ADDR (0, 0), + &type, &shadow_root.addr_trans); + assert (err == 0); + shadow_root.type = type; + + if (type != cap_void) + as_alloc_at (ADDR (CAP_GUARD (&shadow_root), + CAP_GUARD_BITS (&shadow_root)), + 1); + + /* We assume that the address space is well-formed and that all + objects in the address space are described by hurd object + descriptors. + + We shadow each object depth first. This ensures that all + dependencies are available when we add a shadow object to the + shadowed AS. */ + + /* Which depths have objects. */ + l4_uint64_t depths = 0; + + struct hurd_object_desc *desc; + int i; + for (i = 0, desc = &__hurd_startup_data->descs[0]; + i < __hurd_startup_data->desc_count; + i ++, desc ++) + depths |= 1ULL << addr_depth (desc->object); + + while (depths) + { + int depth = l4_lsb64 (depths) - 1; + depths &= ~(1ULL << depth); + + for (i = 0, desc = &__hurd_startup_data->descs[0]; + i < __hurd_startup_data->desc_count; + i ++, desc ++) + if (addr_depth (desc->object) == depth) + add (desc); + } + + /* Now we add any additional descriptors that describe memory that + we have allocated in the mean time. */ + for (i = 0; i < desc_additional_count; i ++) + add (&desc_additional[i]); + + /* Reserve the kip and the utcb. */ + as_alloc_at (ADDR ((uintptr_t) l4_kip (), ADDR_BITS), l4_kip_area_size ()); + as_alloc_at (ADDR ((uintptr_t) _L4_utcb (), ADDR_BITS), l4_utcb_size ()); + + /* And the page at 0. */ + as_alloc_at (PTR_TO_ADDR (0), 1); + + /* Free DESC_ADDITIONAL. */ + for (i = 0, desc = &__hurd_startup_data->descs[0]; + i < __hurd_startup_data->desc_count; + i ++, desc ++) + if (ADDR_EQ (desc->object, PTR_TO_ADDR (desc_additional))) + { + storage_free (desc->storage, false); + as_free (PTR_TO_ADDR (desc_additional), 1); + break; + } + assert (i != __hurd_startup_data->desc_count); + +#ifndef NDEBUG + /* Walk the address space the hard way and make sure that we've got + everything. */ + int visit (addr_t addr, + l4_word_t type, struct cap_addr_trans addr_trans, + bool writable, void *cookie) + { + struct cap *cap = slot_lookup_rel (meta_data_activity, + &shadow_root, addr, -1, NULL); + assert (cap); + + assert (cap->type == type); + assert (cap->addr_trans.raw == addr_trans.raw); + + return 0; + } + + as_walk (visit, -1, NULL); +#endif + + as_init_done = true; + + as_alloced_dump (""); +} + +void +as_alloced_dump (const char *prefix) +{ + struct free_space *free_space; + for (free_space = hurd_btree_free_space_first (&free_spaces); + free_space; + free_space = hurd_btree_free_space_next (free_space)) + printf ("%s%s%llx-%llx\n", + prefix ?: "", prefix ? ": " : "", + free_space->region.start, free_space->region.end); +} + +struct cap +cap_lookup (activity_t activity, + addr_t address, enum cap_type type, bool *writable) +{ + return cap_lookup_rel (activity, &shadow_root, address, type, writable); +} + +struct cap +object_lookup (activity_t activity, + addr_t address, enum cap_type type, bool *writable) +{ + return object_lookup_rel (activity, &shadow_root, address, type, writable); +} + +struct cap * +slot_lookup (activity_t activity, + addr_t address, enum cap_type type, bool *writable) +{ + return slot_lookup_rel (activity, &shadow_root, address, type, writable); +} + +/* Walk the address space, depth first. VISIT is called for each slot + for which (1 << reported capability type) & TYPES is non-zero. + TYPE is the reported type of the capability and CAP_ADDR_TRANS the + value of its address translation fields. WRITABLE is whether the + slot is writable. If VISIT returns a non-zero value, the walk is + aborted and that value is returned. If the walk is not aborted, 0 + is returned. */ +int +as_walk (int (*visit) (addr_t cap, + l4_word_t type, struct cap_addr_trans cap_addr_trans, + bool writable, + void *cookie), + int types, + void *cookie) +{ + int do_walk (struct cap *cap, addr_t addr, bool writable) + { + l4_word_t type; + struct cap_addr_trans cap_addr_trans; + + if (as_init_done) + { + type = cap->type; + cap_addr_trans = cap->addr_trans; + } + else + { + error_t err = rm_cap_read (meta_data_activity, + addr, &type, &cap_addr_trans); + if (err) + panic ("Failed to cap_read 0x%llx/%d", + addr_prefix (addr), addr_depth (addr)); + } + + int r; + if (((1 << type) & types)) + { + r = visit (addr, type, cap_addr_trans, writable, cookie); + if (r) + return r; + } + + if (type != cap_cappage && type != cap_cappage) + return 0; + + if (type == cap_rcappage) + writable = false; + + if (addr_depth (addr) + CAP_ADDR_TRANS_GUARD_BITS (cap_addr_trans) + > ADDR_BITS) + return 0; + + addr = addr_extend (addr, CAP_ADDR_TRANS_GUARD (cap_addr_trans), + CAP_ADDR_TRANS_GUARD_BITS (cap_addr_trans)); + + if (addr_depth (addr) + CAP_ADDR_TRANS_SUBPAGE_SIZE_LOG2 (cap_addr_trans) + > ADDR_BITS) + return 0; + + struct object *shadow = NULL; + if (as_init_done) + shadow = cap_to_object (meta_data_activity, cap); + + int i; + for (i = 0; i < CAP_ADDR_TRANS_SUBPAGE_SIZE (cap_addr_trans); i ++) + { + struct cap *object = NULL; + if (as_init_done) + object = &shadow->caps[i]; + + r = do_walk (object, + addr_extend (addr, i, + CAP_ADDR_TRANS_SUBPAGE_SIZE_LOG2 + (cap_addr_trans)), + writable); + if (r) + return r; + } + + return 0; + } + + return do_walk (&shadow_root, ADDR (0, 0), true); +} + +void +as_dump (const char *prefix) +{ + extern void as_dump_from (activity_t activity, + struct cap *root, const char *prefix); + + as_dump_from (meta_data_activity, &shadow_root, prefix); } |