diff options
Diffstat (limited to 'libhurd-mm')
| -rw-r--r-- | libhurd-mm/ChangeLog | 28 | ||||
| -rw-r--r-- | libhurd-mm/Makefile.am | 23 | ||||
| -rw-r--r-- | libhurd-mm/as.c | 979 | ||||
| -rw-r--r-- | libhurd-mm/as.h | 150 | ||||
| -rw-r--r-- | libhurd-mm/capalloc.c | 192 | ||||
| -rw-r--r-- | libhurd-mm/capalloc.h | 33 | ||||
| -rw-r--r-- | libhurd-mm/headers.m4 | 7 | ||||
| -rw-r--r-- | libhurd-mm/mm-init.c | 71 | ||||
| -rw-r--r-- | libhurd-mm/mm.h | 141 | ||||
| -rw-r--r-- | libhurd-mm/mmap.c | 105 | ||||
| -rw-r--r-- | libhurd-mm/physmem-user.c | 210 | ||||
| -rw-r--r-- | libhurd-mm/physmem-user.h | 116 | ||||
| -rw-r--r-- | libhurd-mm/storage.c | 547 | ||||
| -rw-r--r-- | libhurd-mm/storage.h | 64 |
14 files changed, 2079 insertions, 587 deletions
diff --git a/libhurd-mm/ChangeLog b/libhurd-mm/ChangeLog index 60173eb..94125e1 100644 --- a/libhurd-mm/ChangeLog +++ b/libhurd-mm/ChangeLog @@ -1,3 +1,31 @@ +2007-11-16 Neal H. Walfield <neal@gnu.org> + + * Makefile.am (includehurd_HEADERS): Remove vm.h. Add storage.h + and as.h. + (AM_CPPFLAGS): Rename from this... + (COMMON_CPPFLAGS): ... to this. + (libhurd_mm_a_SOURCES): Remove vm.h, vm.c, priv.h, store.c, map.c, + memory.c, pager.c, core.c, anonymous.c, anonymous.h, + physmem-user.h and physmem-user.c. Add capalloc.h, capalloc.c, + storage.h, storage.c, as.h and mmap.c. + * headers.m4: Don't link $(BUILDDIR)/include/hurd/vm.h to vm.h or + $(BUILDDIR)/include/hurd/anonymous.h to anonymous.h. Link + $(BUILDDIR)/include/hurd/as.h to as.h, + $(BUILDDIR)/include/hurd/storage.h to storage.h, and + $(BUILDDIR)/include/hurd/capalloc.h to libhurd-mm/capalloc.h. + * mm-init.c: Rewrite. + * mm.h: Likewise. + * as.c: Likewise. + * as.h: New file. + * capalloc.h: Likewise. + * capalloc.c: Likewise. + * mmap.c: Likewise. + * storage.h: Likewise. + * storage.c: Likewise. + + * physmem-user.h: Remove file. + * physmem-user.c: Remove file. + 2005-04-06 Neal H. Walfield <neal@gnu.org> * vm.h (hurd_vm_allocate): Remove declaration. diff --git a/libhurd-mm/Makefile.am b/libhurd-mm/Makefile.am index 303bd58..1a50277 100644 --- a/libhurd-mm/Makefile.am +++ b/libhurd-mm/Makefile.am @@ -1,5 +1,5 @@ # Makefile.am - Makefile template for libhurd-mm. -# Copyright (C) 2004, 2005 Free Software Foundation, Inc. +# Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc. # Written by Neal H. Walfield # # This file is part of the GNU Hurd. @@ -22,16 +22,13 @@ lib_LIBRARIES = libhurd-mm.a includehurddir = $(includedir)/hurd -includehurd_HEADERS = mm.h vm.h +includehurd_HEADERS = mm.h storage.h as.h -AM_CPPFLAGS = -I$(top_builddir)/include -I$(top_srcdir)/libc-parts -AM_CFLAGS = -libhurd_mm_a_SOURCES = mm.h mm-init.c \ - as.c \ - vm.h vm.c \ - priv.h \ - store.c map.c memory.c \ - pager.c \ - core.c \ - anonymous.c anonymous.h \ - physmem-user.h physmem-user.c +COMMON_CPPFLAGS = -I$(top_builddir)/include -I$(top_srcdir)/libc-parts + -D_GNU_SOURCE -Wall -std=gnu99 -g -O3 +libhurd_mm_a_SOURCES = mm.h \ + capalloc.h capalloc.c \ + storage.h storage.c \ + as.h as.c \ + mmap.c \ + mm-init.c 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); } diff --git a/libhurd-mm/as.h b/libhurd-mm/as.h new file mode 100644 index 0000000..cca8b35 --- /dev/null +++ b/libhurd-mm/as.h @@ -0,0 +1,150 @@ +/* as.h - Address space interface. + 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 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 + 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. */ + +#ifndef _HURD_AS_H +#define _HURD_AS_H + +#include <hurd/addr.h> +#include <hurd/cap.h> +#include <stdbool.h> + +/* The address space allocator keeps track of which addresses are + allocated and which are available. The allocator supports the + efficient allocation of both arbitrary and specific addresses. + When an address is allocated, all address under that address are + allocated as well. */ + +/* Allocate COUNT contiguous subtree such that the root's depth of + each is at least ADDR_BITS - WIDTH. If DATA_MAPPABLE is true, then + ensures that the leaves of each subtree are mappable in the region + accessible to data instructions. On success returns the address of + the first subtree. Otherwise, returns ADDR_VOID. */ +extern addr_t as_alloc (int width, l4_uint64_t count, + bool data_mappable); + +/* Like as_alloc but may be called before as_init is called. If + MAY_ALLOC is false, may be called before storage_init is done. */ +extern addr_t as_alloc_slow (int width, bool data_mappable, + bool may_alloc); + +/* Allocate the COUNT contiguous addresses strating at address ADDR. + Returns true on success, false otherwise. */ +extern bool as_alloc_at (addr_t addr, l4_uint64_t count); + +/* Free the COUNT contiguous addresses starting at ADDR. Each ADDR + must have been previously returned by a call to as_chunk_alloc or + as_region_alloc. All address returned by a call to as_chunk_alloc + or as_region_alloc need not be freed by a single call to + as_free. */ +extern void as_free (addr_t addr, l4_uint64_t count); + +/* Whether as_init has completed. */ +extern bool as_init_done; + +/* Initialize the address space manager. */ +extern void as_init (void); + +/* Allocate an area covering of width WIDTH. */ +extern addr_t as_alloc_slow (int width, bool data_mappable, bool may_alloc); + +/* Print the allocated areas. */ +extern void as_alloced_dump (const char *prefix); + +/* Root of the shadow page tables. */ +extern struct cap shadow_root; + +/* Because metadata is often a resource shared among the activities + running in a particular address space, all metadata is built from a + single activity. This should dominate all activities running in + this address space to avoid priority inversion. */ +extern addr_t meta_data_activity; + +/* Ensure that the slot designated by ADDR is accessible. Return that + capability. */ +extern struct cap *as_slot_ensure (addr_t addr); + +struct as_insert_rt +{ + struct cap cap; + addr_t storage; +}; + +/* Insert the object described by the capability ENTRY into the + address space at address ADDR. Creates any required page + tables. */ +extern void as_insert (activity_t activity, + struct cap *root, addr_t addr, + struct cap entry, addr_t entry_addr, + struct as_insert_rt (*allocate_object) + (enum cap_type type, addr_t addr)); + +/* Return the value of the capability at ADDR or, if an object, the + value of the capability designating the object. + + TYPE is the required type. If the type is incompatible + (cap_rcappage => cap_cappage and cap_rpage => cap_page), bails. If + TYPE is -1, then any type is acceptable. May cause paging. If + non-NULL, returns whether the slot is writable in *WRITABLE. */ +extern struct cap cap_lookup (activity_t activity, + addr_t addr, enum cap_type type, + bool *writable); + +/* Return the capability slot at ADDR or, if an object, the slot + referencing the object. + + TYPE is the required type. If the type is incompatible + (cap_rcappage => cap_cappage and cap_rpage => cap_page), bails. If + TYPE is -1, then any type is acceptable. May cause paging. If + non-NULL, returns whether the slot is writable in *WRITABLE. */ +extern struct cap *slot_lookup (activity_t activity, + addr_t addr, enum cap_type type, + bool *writable); + +/* Return the value of the capability designating the object at ADDR. + + TYPE is the required type. If the type is incompatible + (cap_rcappage => cap_cappage and cap_rpage => cap_page), bails. If + TYPE is -1, then any type is acceptable. May cause paging. If + non-NULL, returns whether the slot is writable in *WRITABLE. */ +extern struct cap object_lookup (activity_t activity, + addr_t addr, enum cap_type type, + bool *writable); + +/* Walk the address space (without using the shadow page tables), + 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. */ +extern 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); + +/* Dump the address space structures. */ +extern void as_dump (const char *prefix); + +#endif /* _HURD_AS_H */ diff --git a/libhurd-mm/capalloc.c b/libhurd-mm/capalloc.c new file mode 100644 index 0000000..f565201 --- /dev/null +++ b/libhurd-mm/capalloc.c @@ -0,0 +1,192 @@ +/* capalloc.c - Capability allocation 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 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 + 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 "capalloc.h" + +#include "storage.h" +#include "as.h" + +#include <hurd/addr.h> +#include <hurd/btree.h> +#include <hurd/slab.h> +#include <hurd/stddef.h> + +#include <bit-array.h> + +#include <string.h> + +struct cappage_desc +{ + hurd_btree_node_t node; + + addr_t cappage; + unsigned char alloced[CAPPAGE_SLOTS / 8]; + unsigned short free; + + struct cappage_desc *next; + struct cappage_desc **prevp; +}; + +static void +link (struct cappage_desc **list, struct cappage_desc *e) +{ + e->next = *list; + if (e->next) + e->next->prevp = &e->next; + e->prevp = list; + *list = e; +} + +static void +unlink (struct cappage_desc *e) +{ + assert (e->next); + assert (e->prevp); + + *e->prevp = e->next; + if (e->next) + e->next->prevp = e->prevp; +} + +static int +addr_compare (const addr_t *a, const addr_t *b) +{ + if (addr_prefix (*a) < addr_prefix (*b)) + return -1; + return addr_prefix (*a) != addr_prefix (*b); +} + +BTREE_CLASS (cappage_desc, struct cappage_desc, + addr_t, cappage, node, addr_compare) + +static hurd_btree_cappage_desc_t cappage_descs; + +/* Storage descriptors are alloced from a slab. */ +static error_t +cappage_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); + if (ADDR_IS_VOID (storage)) + panic ("Out of storage"); + *ptr = ADDR_TO_PTR (storage); + + return 0; +} + +static error_t +cappage_desc_slab_dealloc (void *hook, void *buffer, size_t size) +{ + assert (size == PAGESIZE); + + addr_t addr = ADDR ((uintptr_t) buffer, ADDR_BITS - PAGESIZE_LOG2); + storage_free (addr, false); + + return 0; +} + +static struct hurd_slab_space cappage_desc_slab + = HURD_SLAB_SPACE_INITIALIZER (struct cappage_desc, + cappage_desc_slab_alloc, + cappage_desc_slab_dealloc, + NULL, NULL, NULL); + +static struct cappage_desc * +cappage_desc_alloc (void) +{ + void *buffer; + error_t err = hurd_slab_alloc (&cappage_desc_slab, &buffer); + if (err) + panic ("Out of memory!"); + return buffer; +} + +static void +cappage_desc_free (struct cappage_desc *storage) +{ + hurd_slab_dealloc (&cappage_desc_slab, storage); +} + +struct cappage_desc *nonempty; + +addr_t +capalloc (void) +{ + if (! nonempty) + { + nonempty = cappage_desc_alloc (); + + /* As there is such a large number of objects, we expect that + the page will be long lived. */ + nonempty->cappage = storage_alloc (meta_data_activity, + cap_cappage, STORAGE_LONG_LIVED, + ADDR_VOID); + + memset (&nonempty->alloced, 0, sizeof (nonempty->alloced)); + nonempty->free = CAPPAGE_SLOTS; + + nonempty->next = NULL; + nonempty->prevp = &nonempty; + + hurd_btree_cappage_desc_insert (&cappage_descs, nonempty); + } + + int idx = bit_alloc (nonempty->alloced, sizeof (nonempty->alloced), 0); + assert (idx != -1); + + nonempty->free --; + + if (nonempty->free == 0) + unlink (nonempty); + + return addr_extend (nonempty->cappage, idx, CAPPAGE_SLOTS_LOG2); +} + +void +capfree (addr_t cap) +{ + addr_t cappage = addr_chop (cap, CAPPAGE_SLOTS_LOG2); + + struct cappage_desc *desc; + desc = hurd_btree_cappage_desc_find (&cappage_descs, &cappage); + assert (desc); + + bit_dealloc (desc->alloced, addr_extract (cap, CAPPAGE_SLOTS_LOG2)); + desc->free ++; + + if (desc->free == 1) + /* The cappage is no longer full. Add it back to the list of + nonempty cappages. */ + link (&nonempty, desc); + else if (desc->free == CAPPAGE_SLOTS) + /* No slots in the cappage are allocated. Free it if there is at + least one cappage on NONEMPTY. */ + { + if (nonempty) + { + hurd_btree_cappage_desc_detach (&cappage_descs, desc); + cappage_desc_free (desc); + } + } +} + diff --git a/libhurd-mm/capalloc.h b/libhurd-mm/capalloc.h new file mode 100644 index 0000000..77d6359 --- /dev/null +++ b/libhurd-mm/capalloc.h @@ -0,0 +1,33 @@ +/* capalloc.h - Capability allocation 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 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 + 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. */ + +#ifndef _HURD_CAP_ALLOC_H +#define _HURD_CAP_ALLOC_H + +#include <hurd/addr.h> + +/* Allocate a capability slot. */ +extern addr_t capalloc (void); + +/* Free a capability previously allocated by capalloc. */ +extern void capfree (addr_t cap); + +#endif /* _HURD_CAP_ALLOC_H */ diff --git a/libhurd-mm/headers.m4 b/libhurd-mm/headers.m4 index 4d9202e..5fc6736 100644 --- a/libhurd-mm/headers.m4 +++ b/libhurd-mm/headers.m4 @@ -1,5 +1,5 @@ # headers.m4 - Autoconf snippets to install links for header files. -# Copyright 2004, 2005 Free Software Foundation, Inc. +# Copyright 2004, 2005, 2007 Free Software Foundation, Inc. # Written by Neal H. Walfield <neal@gnu.org>. # # This file is free software; as a special exception the author gives @@ -12,6 +12,7 @@ AC_CONFIG_LINKS([ include/hurd/mm.h:libhurd-mm/mm.h - include/hurd/vm.h:libhurd-mm/vm.h - include/hurd/anonymous.h:libhurd-mm/anonymous.h + include/hurd/as.h:libhurd-mm/as.h + include/hurd/storage.h:libhurd-mm/storage.h + include/hurd/capalloc.h:libhurd-mm/capalloc.h ]) diff --git a/libhurd-mm/mm-init.c b/libhurd-mm/mm-init.c index 927cc6b..b23ccb7 100644 --- a/libhurd-mm/mm-init.c +++ b/libhurd-mm/mm-init.c @@ -23,72 +23,27 @@ #include <config.h> #endif -#include <assert.h> -#include <errno.h> -#include <stdbool.h> -#include <l4.h> #include <hurd/startup.h> -#include "anonymous.h" -#include "vm.h" -#include "priv.h" +#include "storage.h" +#include "as.h" -/* Physmem's server thread. */ -l4_thread_id_t physmem; - -/* True once the MM is up and running. */ -int mm_init_done; - -/* Initialized by the machine-specific startup-code. */ extern struct hurd_startup_data *__hurd_startup_data; -/* Initialize the memory management subsystem. */ +addr_t meta_data_activity; + void -hurd_mm_init (l4_thread_id_t pager_tid) +mm_init (addr_t activity) { - error_t err; - uintptr_t stack; - - /* FIXME: The image server may not be (and will likely not be) - physmem. */ - physmem = __hurd_startup_data->image.server; - -#define INIT(service) \ - do \ - { \ - void service##_system_init (void); \ - service##_system_init (); \ - } \ - while (0) - - /* Initialize the core. */ - INIT (memory); - - /* Initialize the system pagers. */ - INIT (core); - INIT (hurd_anonymous); - - /* Initialize the mapping database. */ - INIT (map); - - /* The mapping database is now bootstrapped. */ - mm_init_done = 1; - - /* Allocate a stack for the pager thread. */ - err = core_allocate (&stack, getpagesize (), 0, 1); - if (err) - panic ("Unable to allocate a stack for the pager thread.\n"); + extern int output_debug; - /* Start it up. */ - l4_start_sp_ip (pager_tid, stack + getpagesize (), (l4_word_t) pager); + output_debug = 4; - /* XXX: EVIL. If a thread causes a page fault before its pager is - waiting for faults, the pager will not get the correct message - contents. This is an evil work around to make sure that the - pager is up before we return. */ - int i; - for (i = 0; i < 100; i ++) - l4_yield (); + if (ADDR_IS_VOID (activity)) + meta_data_activity = __hurd_startup_data->activity; + else + meta_data_activity = activity; - l4_set_pager (pager_tid); + storage_init (); + as_init (); } diff --git a/libhurd-mm/mm.h b/libhurd-mm/mm.h index e18201e..ffa3daa 100644 --- a/libhurd-mm/mm.h +++ b/libhurd-mm/mm.h @@ -22,143 +22,10 @@ #ifndef HURD_MM_MM_H #define HURD_MM_MM_H -#include <stdint.h> -#include <sys/types.h> -#include <l4/types.h> -#include <hurd/physmem.h> +#include <hurd/addr.h> -/* Start the memory manager including starting the user pager and the - virtual memory management subsystem on thread PAGER_TID. */ -extern void hurd_mm_init (l4_thread_id_t pager_tid); - -/* A region of memory. */ -struct region -{ - /* Start of the region. */ - uintptr_t start; - /* And its extent. */ - size_t size; -}; - -/* Backing store abstraction. */ -struct hurd_store; -typedef struct hurd_store hurd_store_t; - -/* Physical memory abstraction. */ -struct hurd_memory; -typedef struct hurd_memory hurd_memory_t; - -/* Allocate a new memory structure referring to size bytes of physical - memory. Return NULL on failure. The returned memory needs to be - integrated into the appropriate store's cache (using - hurd_memory_insert). */ -extern hurd_memory_t *hurd_memory_alloc (size_t size); - -/* Allocate a new memory structure referring to the physical memory on - container CONTAINER starting at CONT_START and continuing for SIZE - bytes. The physical memory becomes fully managed by the memory - manager and must only be deallocated via the hurd_memory_dealloc - interface. (Hence, CONTAINER must not be deallocated until the - memory manager no longer references it.) */ -extern hurd_memory_t *hurd_memory_use (hurd_pm_container_t container, - uintptr_t cont_start, - size_t size); - -/* Allocate a new memory structure referring to the physical memory on - container CONTAINER starting at CONT_START and continuing for SIZE - bytes. The physical memory is logically copied (and deallocated - from CONTAINER if MOVE is true) to an internal container. Hence, - unlike hurd_memory_use, hurd_memory_transfer obtains its own - reference to the physical memory. NB: if MOVE is false the memory - is referenced by two containers and those count doubly against the - task's physical memory allocation. */ -extern hurd_memory_t *hurd_memory_transfer (hurd_pm_container_t container, - uintptr_t cont_start, - size_t size, - bool move); - -/* Deallocate the physical memory MEMORY associated with store STORE - starting at START (relative to the base of MEMORY) and continuing - for LENGHT bytes. If START is 0 and LENGTH is the length of - MEMORY, MEMORY is deallocated (and detached from STORE). If START - is greater than zero and START + LENGTH is less than the size of - MEMORY then MEMORY is adjusted to refer to the first portion of - memory, a new MEMORY structure is allocated to refer the end and - physical memory referred to by the middle part is freed. - Otherwise, MEMORY is adjusted to refer to the physical memory which - will not be deallocated and the rest of the physical memory is - deallocated. */ -extern void hurd_memory_dealloc (hurd_store_t *store, hurd_memory_t *memory, - uintptr_t start, size_t length); - -/* Install a map of memory MEMORY starting at offset MEMORY_OFFSET - (relative to the base of MEMORY) extending LENGTH bytes in the - address space at virtual memory address VADDR. (To map an entire - memory block, pass OFFSET equal to 0 and LENGTH equal to - MEMORY->STORE.SIZE.) OFFSET must be aligned on a multiple of the - base page size and LENGTH must be a multiple of the base page - size. */ -extern error_t hurd_memory_map (hurd_memory_t *memory, size_t memory_offset, - size_t length, uintptr_t vaddr); - -/* Thread THREAD faulted at address ADDR which is contained in the - registered region REGION. */ -typedef void (*hurd_store_fault_t) (hurd_store_t *store, void *hook, - l4_thread_id_t thread, - struct region vm_region, - off64_t store_offset, - uintptr_t addr, l4_word_t access); - -/* Initialize a store. STORE points to allocated memory. */ -extern void hurd_store_init (hurd_store_t *store, - void *hook, hurd_store_fault_t fault); - -/* The number of bytes required for a store. */ -extern size_t hurd_store_size (void) __attribute__ ((const)); - -extern void hurd_store_destroy (hurd_store_t *store); - -/* Either allocate a region exactly at the specified address or - fail. */ -#define HURD_VM_HERE (1 << 0) - -/* A store manager may call this to indicate that STORE will manage - faults for the addresses starting at ADDRESS and extending for SIZE - bytes. If ADDRESS is 0, the memory manager selects a free virtual - memory region. If ADDRESS is non-zero and HURD_VM_HERE is not set - in FLAGS, then ADDRESS is used as a hint. If HURD_VM_HERE is set - in the flags, ADDRESS is used if possible otherwise, EEXIST is - returned. The function returns the start of the virtual memory - address actually used on success in *USED_ADDRESS if USED_ADDRESS - is not-NULL. On success, 0 is returned. An error code - otherwise. */ -extern error_t hurd_store_bind_to_vm (hurd_store_t *store, - off64_t store_offset, - uintptr_t address, size_t size, - uintptr_t flags, int map_now, - uintptr_t *used_address); - -/* Record that memory MEMORY caches backing store STORE starting at - byte STORE_START. */ -extern void hurd_store_cache (hurd_store_t *store, uintptr_t store_start, - hurd_memory_t *memory); - -/* Find the first memory region (i.e. the one with the lowest starting - address) which intersects with regions covering STORE starting at - STORE_START and spanning LENGTH bytes. If none is found, return - NULL. - - NB: The intersection of any two memory regions will always be NULL, - however, it is possible that the region one is looking up on the - store is covered by multiple memory regions. This function returns - the first of those. */ -extern hurd_memory_t *hurd_store_find_cached (hurd_store_t *store, - uintptr_t store_start, - size_t length); - -/* Flush any memory mapping the backing store starting at STORE_START - and continuing for LENGTH bytes to backing store. */ -extern void hurd_store_flush (hurd_store_t *store, - uintptr_t store_start, size_t length); +/* Initialize the memory management sub-system. ACTIVITY is the + activity to use to account meta-data resources. */ +extern void mm_init (addr_t activity); #endif /* HURD_MM_MM_H */ diff --git a/libhurd-mm/mmap.c b/libhurd-mm/mmap.c new file mode 100644 index 0000000..eb37e8c --- /dev/null +++ b/libhurd-mm/mmap.c @@ -0,0 +1,105 @@ +/* mmap.c - mmap implementation. + 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 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 + 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 <hurd/stddef.h> +#include <hurd/addr.h> +#include <hurd/as.h> +#include <hurd/storage.h> + +#include <sys/mman.h> +#include <stdint.h> + +void * +mmap (void *addr, size_t length, int protect, int flags, + int filedes, off_t offset) +{ + if (length == 0) + return MAP_FAILED; + + if ((flags & ~(MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED))) + panic ("mmap called with invalid flags"); + if (protect != (PROT_READ | PROT_WRITE)) + panic ("mmap called with unsupported protection"); + + if ((flags & MAP_FIXED)) + /* Interpret ADDR exactly. */ + { + if (((uintptr_t) addr & (PAGESIZE - 1))) + return MAP_FAILED; + } + else + { + /* Round the address down to a multiple of the pagesize. */ + addr = (void *) ((uintptr_t) addr & ~(PAGESIZE - 1)); + } + + /* Round length up. */ + length = (length + PAGESIZE - 1) & ~(PAGESIZE - 1); + + bool alloced = false; + if (addr) + /* Caller wants a specific address range. */ + { + bool r = as_alloc_at (PTR_TO_ADDR (addr), length); + if (r) + alloced = true; + else + /* No room for this region. */ + { + if (flags & MAP_FIXED) + return MAP_FAILED; + } + } + + if (! alloced) + { + addr_t region = as_alloc (PAGESIZE_LOG2, length / PAGESIZE, true); + if (ADDR_IS_VOID (region)) + return MAP_FAILED; + + addr = ADDR_TO_PTR (region); + } + + /* Right now we allocate each page and its supporting data + structures immediately. It may make more sense to setup a + pager. */ + /* XXX: Save the association between the storage that we allocate + and the addresses; we need to deallocate it on unmap! */ + uintptr_t page; + for (page = (uintptr_t) addr; page < (uintptr_t) addr + length; + page += PAGESIZE) + { + addr_t page_addr = PTR_TO_ADDR (page); + bool r = as_slot_ensure (page_addr); + if (! r) + panic ("Failed to ensure slot at 0x%x/%d", + addr_prefix (page_addr), addr_depth (page_addr)); + + addr_t storage + = storage_alloc (ADDR_VOID, + protect & PROT_WRITE ? cap_page : cap_rpage, + STORAGE_UNKNOWN, page_addr); + if (ADDR_IS_VOID (storage)) + panic ("Out of memory."); + } + + return addr; +} diff --git a/libhurd-mm/physmem-user.c b/libhurd-mm/physmem-user.c deleted file mode 100644 index 0ee13c9..0000000 --- a/libhurd-mm/physmem-user.c +++ /dev/null @@ -1,210 +0,0 @@ -/* physmem-user.c - physmem client stubs. - Copyright (C) 2004, 2005 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 - 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> -#endif - -#include <stdint.h> -#include <l4.h> - -#include <compiler.h> -#include <hurd/startup.h> - -#include "physmem-user.h" - -/* Initialized by the machine-specific startup-code. */ -extern struct hurd_startup_data *__hurd_startup_data; - -#define physmem (__hurd_startup_data->image.server) - -/* Create a container managed by the physical memory server. On - success, returned in *CONTAINER. */ -error_t -hurd_pm_container_create (hurd_pm_container_t control, - hurd_pm_container_t *container) - -{ - l4_msg_t msg; - l4_msg_tag_t tag; - - l4_msg_clear (msg); - l4_set_msg_label (msg, hurd_pm_container_create_id); - l4_msg_append_word (msg, control); - l4_msg_load (msg); - - tag = l4_call (physmem); - l4_msg_store (tag, msg); - - *container = l4_msg_word (msg, 0); - - return l4_msg_label (msg); -} - -/* Create a limited access capability for container CONTAINER, return - in *ACCESS. */ -error_t -hurd_pm_container_share (hurd_pm_control_t container, - hurd_pm_container_t *access) -{ - l4_msg_t msg; - l4_msg_tag_t tag; - - l4_msg_clear (msg); - l4_set_msg_label (msg, hurd_pm_container_share_id); - l4_msg_append_word (msg, container); - l4_msg_load (msg); - - tag = l4_call (physmem); - l4_msg_store (tag, msg); - - *access = l4_msg_word (msg, 0); - - return l4_msg_label (msg); -} - -/* Allocate SIZE bytes according to FLAGS into container CONTAINER - starting with index START. *AMOUNT contains the number of bytes - successfully allocated. */ -error_t -hurd_pm_container_allocate (hurd_pm_container_t container, - l4_word_t start, l4_word_t size, - l4_word_t flags, l4_word_t *amount) -{ - l4_msg_t msg; - l4_msg_tag_t tag; - - l4_msg_clear (msg); - l4_set_msg_label (msg, hurd_pm_container_allocate_id); - l4_msg_append_word (msg, container); - l4_msg_append_word (msg, flags); - l4_msg_append_word (msg, start); - l4_msg_append_word (msg, size); - - l4_msg_load (msg); - - tag = l4_call (physmem); - l4_msg_store (tag, msg); - - *amount = l4_msg_word (msg, 0); - - return l4_msg_label (msg); -} - -error_t -hurd_pm_container_deallocate (hurd_pm_container_t container, - uintptr_t start, uintptr_t size) -{ - l4_msg_t msg; - l4_msg_tag_t tag; - - l4_msg_clear (msg); - l4_set_msg_label (msg, hurd_pm_container_deallocate_id); - l4_msg_append_word (msg, container); - l4_msg_append_word (msg, start); - l4_msg_append_word (msg, size); - - l4_msg_load (msg); - - tag = l4_call (physmem); - l4_msg_store (tag, msg); - - return l4_msg_label (msg); -} - - -/* Map the COUNT bytes of physical memory in container CONTAINER - starting at byte INDEX at virtual memory address VADDR of the - calling task according to the flags FLAGS. */ -error_t -hurd_pm_container_map (hurd_pm_container_t container, - l4_word_t index, size_t count, - uintptr_t vaddr, l4_word_t flags, - size_t *amountp) -{ - l4_msg_t msg; - l4_msg_tag_t tag; - int i; - size_t amount; - - /* Let physmem take over the address space completely. */ - l4_accept (l4_map_grant_items (L4_COMPLETE_ADDRESS_SPACE)); - - l4_msg_clear (msg); - l4_set_msg_label (msg, hurd_pm_container_map_id); - l4_msg_append_word (msg, container); - l4_msg_append_word (msg, flags); - l4_msg_append_word (msg, vaddr); - l4_msg_append_word (msg, index); - l4_msg_append_word (msg, count); - l4_msg_load (msg); - - tag = l4_call (physmem); - l4_msg_store (tag, msg); - - if (amountp) - { - for (i = 0, amount = 0; - i < l4_typed_words (tag); - i += sizeof (l4_map_item_t) / sizeof (l4_word_t)) - { - l4_map_item_t mi; - l4_msg_get_map_item (msg, i, &mi); - assert (l4_is_map_item (mi)); - amount += l4_size (l4_map_item_snd_fpage (mi)); - } - - *amountp = amount; - } - - return l4_msg_label (msg); -} - -error_t -hurd_pm_container_copy (hurd_pm_container_t src_container, - uintptr_t src_start, - hurd_pm_container_t dest_container, - uintptr_t dest_start, - size_t count, - uintptr_t flags, - size_t *amount) -{ - l4_msg_t msg; - l4_msg_tag_t tag; - - l4_msg_clear (msg); - l4_set_msg_label (msg, hurd_pm_container_copy_id); - l4_msg_append_word (msg, src_container); - l4_msg_append_word (msg, src_start); - l4_msg_append_word (msg, dest_container); - l4_msg_append_word (msg, dest_start); - l4_msg_append_word (msg, count); - l4_msg_append_word (msg, flags); - - l4_msg_load (msg); - - tag = l4_call (physmem); - l4_msg_store (tag, msg); - - *amount = l4_msg_word (msg, 0); - - return l4_msg_label (msg); -} diff --git a/libhurd-mm/physmem-user.h b/libhurd-mm/physmem-user.h deleted file mode 100644 index 266bfc5..0000000 --- a/libhurd-mm/physmem-user.h +++ /dev/null @@ -1,116 +0,0 @@ -/* physmem-user.h - physmem client stubs. - Copyright (C) 2004, 2005 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 - 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. */ - -#ifndef HURD_PHYSMEM_USER_H -#define HURD_PHYSMEM_USER_H 1 - -#include <stdint.h> -#include <sys/types.h> -#include <l4.h> -#include <hurd/types.h> -#include <hurd/physmem.h> - -/* Create a container in *CONTAINER managed by the physical memory - server from the contol memory capability CONTROL. */ -extern error_t hurd_pm_container_create (hurd_pm_control_t control, - hurd_pm_container_t *container); - -/* Create a limited access capability for container CONTAINER, return - in *ACCESS. */ -extern error_t hurd_pm_container_share (hurd_pm_container_t container, - hurd_pm_container_t *access); - -/* Allocate SIZE bytes of physical memory (which must be a multiple of - the page size) according to the flags FLAGS into container - CONTAINER and associate the first byte with index START (and byte X - with START+X where X < SIZE). On return *AMOUNT will contain the - number of bytes successfully allocated. The returned error code - will indicate the error trying to allocate byte *AMOUNT. - - physmem will use the least number of frames possible to cover the - region (recall: a frame is any power of 2 greater than the minimum - page size) without allocating too much memory. That is, if you - allocate 12k and the page size is 4k, physmem will allocate two - frames, an 8k frame and a 4k frame. If for some reason you need - only 4k frames, then you must call this function multiple - times. */ -extern error_t hurd_pm_container_allocate (hurd_pm_container_t container, - l4_word_t start, l4_word_t size, - l4_word_t flags, l4_word_t *amount); - -/* Deallocate SIZE bytes of physical memory starting at offset START - in container CONTAINER. This implicitly unmaps any extant mappings - of the physical memory. If is not START page aligned, EINVAL is - returned. If SIZE is not a multiple of the page size, EINVAL is - returned. - - Multiple allocations may be deallocated in a single RPC. Parts of - an allocation may also be deallocated. Any part of the region - without a valid mapping will be ignored (and no error - returned). */ -extern error_t hurd_pm_container_deallocate (hurd_pm_container_t container, - uintptr_t start, uintptr_t size); - -/* Map the COUNT bytes of physical memory in container CONTAINER - starting at byte INDEX at virtual memory address VADDR of the - calling task according to the flags FLAGS. - - If INDEX does not refer to the start of base page aligned memory in - CONTAINER, EINVAL is returned. If SIZE is not a multiple of the - base page size, EINVAL is returned. If VADDR is not aligned on a - multiple of the base page size, EINVAL is returned. - - If an address to map has no memory associated with it, ENOENT is - returned. - - If AMOUNT is not-NULL, *AMOUNT is set to the number of bytes - actually mapped. */ -extern error_t hurd_pm_container_map (hurd_pm_container_t container, - l4_word_t index, size_t size, - uintptr_t vaddr, l4_word_t flags, - size_t *amount); - -/* Logically copy COUNT bytes from container SRC_CONTAINER starting at - byte SRC_START to container DEST_CONTAINER starting at byte - DEST_START. On return, *AMOUNT contains the number of bytes - successfully copied. - - If copying would overwrite frames in DEST_CONTAINER and FLAGS - contains HURD_PM_CONT_ALLOC_SQUASH, the frames are implicitly - deallocated, otherwise EEXIST is returned. - - If an address to copy has no memory associated with it, ENOENT is - returned. - - SRC_START and DEST_START must correspond to the start of a base - page. COUNT must be a multiple of the base page. Failing this, - EINVAL is returned. - - *AMOUNT will always contain a number of bytes which is a multiple - of the base page size. */ -extern error_t hurd_pm_container_copy (hurd_pm_container_t src_container, - uintptr_t src_start, - hurd_pm_container_t dest_container, - uintptr_t dest_start, - size_t count, - uintptr_t flags, - size_t *amount); -#endif /* HURD_PHYSMEM_USER_H */ diff --git a/libhurd-mm/storage.c b/libhurd-mm/storage.c new file mode 100644 index 0000000..4e0f407 --- /dev/null +++ b/libhurd-mm/storage.c @@ -0,0 +1,547 @@ +/* storage.c - Storage allocation 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 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 + 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 "storage.h" + +#include <hurd/stddef.h> +#include <hurd/btree.h> +#include <hurd/slab.h> +#include <hurd/addr.h> +#include <hurd/folio.h> +#include <hurd/startup.h> +#include <hurd/rm.h> + +#include <bit-array.h> + +#include <stddef.h> +#include <string.h> + +#include "as.h" + +/* Objects are allocated from folios. As a folio is the unit of + storage allocation, we can only free a folio when it is completely + empty. For this reason, we try to group long lived objects + together and short lived objects together. */ + +/* Total number of free objects across all folios. */ +static int free_count; + +struct storage_desc +{ + /* Each storage area is stored in a btree keyed by the address of + the folio. */ + hurd_btree_node_t node; + + /* The address of the folio. */ + addr_t folio; + /* The location of the folio's shadow object. */ + struct object *shadow; + + /* Which objects are allocated. */ + unsigned char alloced[FOLIO_OBJECTS / 8]; + /* The number of free objects. */ + unsigned char free; + + /* The storage object's mode of allocation. */ + char mode; + + struct storage_desc *next; + struct storage_desc **prevp; +}; + +static void +link (struct storage_desc **list, struct storage_desc *e) +{ + e->next = *list; + if (e->next) + e->next->prevp = &e->next; + e->prevp = list; + *list = e; +} + +static void +unlink (struct storage_desc *e) +{ + assert (e->next); + assert (e->prevp); + + *e->prevp = e->next; + if (e->next) + e->next->prevp = e->prevp; +} + +static int +addr_compare (const addr_t *a, const addr_t *b) +{ + if (a->raw < b->raw) + return -1; + return a->raw != b->raw; +} + +BTREE_CLASS (storage_desc, struct storage_desc, + addr_t, folio, node, addr_compare) + +static hurd_btree_storage_desc_t storage_descs; + +/* Storage descriptors are alloced from a slab. */ +static struct hurd_slab_space storage_desc_slab; + +/* Before we are initialized, allocating data instruction addressable + storage is at best awkward primarily because we may also need to + create page tables. We avoid this by preallocating some slab + space. */ +static char slab_space[PAGESIZE] __attribute__ ((aligned(PAGESIZE))); +static void *slab_space_reserve = slab_space; + +/* After allocating a descriptor, we check to see whether there is + still a reserve page. By keeping a page of storage available, we + avoid the problematic situation of trying to allocate storage and + insert it into the addresss space but requiring storage and a + storage descriptor (of which there are none!) to do so. */ +static void +check_slab_space_reserve (void) +{ + if (likely (!!slab_space_reserve)) + return; + + addr_t addr = storage_alloc (meta_data_activity, cap_page, + STORAGE_LONG_LIVED, ADDR_VOID); + slab_space_reserve = ADDR_TO_PTR (addr); +} + +static error_t +storage_desc_slab_alloc (void *hook, size_t size, void **ptr) +{ + assert (size == PAGESIZE); + + assert (slab_space_reserve); + *ptr = slab_space_reserve; + slab_space_reserve = NULL; + + return 0; +} + +static error_t +storage_desc_slab_dealloc (void *hook, void *buffer, size_t size) +{ + /* There is no need to special case SLAB_SPACE; we can free it in + the normal way and the right thing will happen. */ + + assert (size == PAGESIZE); + + addr_t addr = PTR_TO_ADDR (buffer); + storage_free (addr, false); + + return 0; +} + +static struct storage_desc * +storage_desc_alloc (void) +{ + void *buffer; + error_t err = hurd_slab_alloc (&storage_desc_slab, &buffer); + if (err) + panic ("Out of memory!"); + + return buffer; +} + +static void +storage_desc_free (struct storage_desc *storage) +{ + hurd_slab_dealloc (&storage_desc_slab, storage); +} + +/* Each storage block with at least one unallocated object lives on + one of three lists. Where a storage area lives is determined by + the type of storage: whether a storage block has mostly long-lived + objects and it is being used as a source for allocations, mostly + long-lived but we are trying to free it; or, mostly ephemeral + objects. */ +static struct storage_desc *long_lived_allocing; +static struct storage_desc *long_lived_freeing; +static struct storage_desc *short_lived; + +/* The storage area is a source of allocations. */ +#define LONG_LIVED_ALLOCING 1 +/* The storage area has been full. */ +#define LONG_LIVED_STABLE 2 +/* The storage area is trying to be freed. */ +#define LONG_LIVED_FREEING 3 + +/* The storage area is dedicated to short lived objects. */ +#define SHORT_LIVED 4 + +/* Once there are more free objects in a LONG_LIVED_STABLE folio than + FREEING_THRESHOLD, we change the folios state from stable to + freeing. */ +#define FREEING_THRESHOLD (FOLIO_OBJECTS / 2) + +/* The minimum number of pages that should be available. */ +#define MIN_FREE_PAGES 16 + +static void +shadow_setup (struct cap *cap, struct storage_desc *storage) +{ + /* XXX: We need to remember that we freed the shadow page from + ourself so that we can deteck when this storage area is + actually free. */ + int idx = bit_alloc (storage->alloced, sizeof (storage->alloced), 0); + if (idx == -1) + panic ("Folio full! No space for a shadow object."); + + storage->free --; + free_count --; + + error_t err = rm_folio_object_alloc (meta_data_activity, + storage->folio, idx, cap_page, + ADDR_VOID); + assert (err == 0); + storage->shadow = ADDR_TO_PTR (addr_extend (storage->folio, idx, + FOLIO_OBJECTS_LOG2)); + cap_set_shadow (cap, storage->shadow); + cap->type = cap_folio; + + storage->shadow->caps[idx].type = cap_page; + storage->shadow->caps[idx].addr_trans = CAP_ADDR_TRANS_VOID; +} + +void +storage_shadow_setup (struct cap *cap, addr_t folio) +{ + struct storage_desc *sdesc; + sdesc = hurd_btree_storage_desc_find (&storage_descs, &folio); + assert (sdesc); + + shadow_setup (cap, sdesc); +} + +/* Allocate an object of type TYPE. If ADDR is not ADDR_VOID, inserts + a capability to it the slot at address ADDR. Returns the address + of the object in the folio (which must be passed to storage_free to + free the storage). */ +addr_t +storage_alloc (addr_t activity, + enum cap_type type, enum storage_expectancy expectancy, + addr_t addr) +{ + struct storage_desc *storage; + + restart: + if (expectancy == STORAGE_EPHEMERAL) + { + storage = short_lived; + if (! storage) + storage = long_lived_allocing; + if (! storage) + storage = long_lived_freeing; + } + else + { + storage = long_lived_allocing; + if (! storage) + { + storage = long_lived_freeing; + if (! storage) + storage = short_lived; + + if (storage) + { + unlink (storage); + link (&long_lived_allocing, storage); + } + } + } + + if (! storage || free_count <= MIN_FREE_PAGES) + /* Insufficient free storage. Allocate a new storage area. */ + { + /* Although we have not yet allocated the objects, allocating + structures may require memory causing us to recurse. Thus, + we add them first. */ + free_count += FOLIO_OBJECTS; + + /* Here is the big recursive dependency! Using the address that + as_alloc returns might require allocating one (or more) page + tables to make a slot available. Moreover, each of those + page tables requires not only a cappage but also a shadow + page table. */ + addr_t addr = as_alloc (FOLIO_OBJECTS_LOG2 + PAGESIZE_LOG2, + 1, true); + if (ADDR_IS_VOID (addr)) + panic ("Failed to allocate address space!"); + + struct cap *cap = as_slot_ensure (addr); + assert (cap); + + /* And then the folio. */ + error_t err = rm_folio_alloc (activity, addr); + assert (! err); + + /* Allocate and fill a descriptor. */ + struct storage_desc *s = storage_desc_alloc (); + + s->folio = addr; + memset (&s->alloced, 0, sizeof (s->alloced)); + s->free = FOLIO_OBJECTS; + + if (! storage && expectancy == STORAGE_EPHEMERAL) + { + s->mode = SHORT_LIVED; + link (&short_lived, s); + } + else + { + s->mode = LONG_LIVED_ALLOCING; + link (&long_lived_allocing, s); + } + + shadow_setup (cap, s); + + /* And finally, insert the new storage descriptor. */ + hurd_btree_storage_desc_insert (&storage_descs, s); + + /* Having added the storage, we now check if we need to allocate + a new reserve slab buffer. */ + check_slab_space_reserve (); + + if (! storage) + storage = s; + + if (storage->free == 0) + /* Some allocations (by as_slot_ensure) appear to have caused + us to empty this folio. Restart. */ + goto restart; + } + + int idx = bit_alloc (storage->alloced, sizeof (storage->alloced), 0); + assert (idx != -1); + + addr_t folio = storage->folio; + addr_t object = addr_extend (folio, idx, FOLIO_OBJECTS_LOG2); + + debug (5, "Allocating object %d from " ADDR_FMT " (" ADDR_FMT ") " + "(%d left), copying to " ADDR_FMT, + idx, ADDR_PRINTF (folio), ADDR_PRINTF (object), + storage->free, ADDR_PRINTF (addr)); + + storage->free --; + free_count --; + + if (storage->free == 0) + /* The folio is now full. */ + { + unlink (storage); +#ifndef NDEBUG + storage->next = NULL; + storage->prevp = NULL; +#endif + if (storage->mode == LONG_LIVED_ALLOCING) + /* Change the folio from the allocating state to the stable + state. */ + storage->mode = LONG_LIVED_STABLE; + } + + if (likely (!! storage->shadow)) + { + storage->shadow->caps[idx].addr_trans = CAP_ADDR_TRANS_VOID; + storage->shadow->caps[idx].type = type; + } + else + assert (! as_init_done); + + error_t err = rm_folio_object_alloc (meta_data_activity, + folio, idx, type, addr); + assert (! err); + + if (! ADDR_IS_VOID (addr)) + /* We also have to update the shadow for ADDR. Unfortunately, we + don't have the cap although the caller might. */ + { + struct cap *cap = slot_lookup (meta_data_activity, addr, -1, NULL); + + cap->type = type; + } + + return object; +} + +void +storage_free (addr_t object, bool unmap_now) +{ + bool freeing_shadow = false; + + restart:; + addr_t folio = addr_chop (object, FOLIO_OBJECTS_LOG2); + + struct storage_desc *storage; + storage = hurd_btree_storage_desc_find (&storage_descs, &folio); + assert (storage); + + int idx = addr_extract (object, FOLIO_OBJECTS_LOG2); + bit_dealloc (storage->alloced, idx); + storage->free ++; + free_count ++; + + error_t err = rm_folio_object_alloc (meta_data_activity, + folio, idx, cap_void, ADDR_VOID); + assert (err == 0); + + /* Update the shadow object. */ + if (likely (!! storage->shadow)) + { + storage->shadow->caps[idx].type = cap_void; + storage->shadow->caps[idx].addr_trans = CAP_ADDR_TRANS_VOID; + } + else + assert (! storage->shadow); + + + if (storage->free == FOLIO_OBJECTS - 1) + { + if (ADDR_EQ (addr_chop (PTR_TO_ADDR (storage->shadow), + FOLIO_OBJECTS_LOG2), + storage->folio)) + /* The last allocated page is our shadow page. Free this + folio. */ + { + object = PTR_TO_ADDR (storage->shadow); + storage->shadow = NULL; + freeing_shadow = true; + goto restart; + } + } + + else if (storage->free == 1 && storage->mode == LONG_LIVED_STABLE) + /* The folio is no longer completely full. Return it to the long + lived allocating list. */ + link (&long_lived_allocing, storage); + + else if (storage->mode == LONG_LIVED_STABLE + && storage->free > FREEING_THRESHOLD) + /* The folio is stable and is now less than half allocated. + Change the folio's state to freeing. */ + { + unlink (storage); + storage->mode = LONG_LIVED_FREEING; + link (&long_lived_freeing, storage); + } + + else if (storage->free == FOLIO_OBJECTS) + /* The folio is now empty. */ + { + if (free_count - FOLIO_OBJECTS > MIN_FREE_PAGES) + /* There are sufficient reserve pages not including this + folio. Thus, we free STORAGE. */ + { + void *shadow = storage->shadow; + + free_count -= FOLIO_OBJECTS; + + unlink (storage); + hurd_btree_storage_desc_detach (&storage_descs, storage); + storage_desc_free (storage); + + error_t err = rm_folio_free (meta_data_activity, folio); + assert (err == 0); + + if (shadow) + { + assert (! freeing_shadow); + storage_free (PTR_TO_ADDR (shadow), false); + } + else + assert (freeing_shadow); + } + } +} + +void +storage_init (void) +{ + /* Initialize the slab. */ + error_t err = hurd_slab_init (&storage_desc_slab, + sizeof (struct storage_desc), 0, + storage_desc_slab_alloc, + storage_desc_slab_dealloc, + NULL, NULL, NULL); + assert (! err); + + /* Identify the existing objects and folios. */ + struct hurd_object_desc *odesc; + int i; + + for (i = 0, odesc = &__hurd_startup_data->descs[0]; + i < __hurd_startup_data->desc_count; + i ++, odesc ++) + { + addr_t folio; + if (odesc->type == cap_folio) + folio = odesc->object; + else + folio = addr_chop (odesc->storage, FOLIO_OBJECTS_LOG2); + + struct storage_desc *sdesc; + sdesc = hurd_btree_storage_desc_find (&storage_descs, &folio); + if (! sdesc) + /* Haven't seen this folio yet. */ + { + sdesc = storage_desc_alloc (); + sdesc->folio = folio; + sdesc->free = FOLIO_OBJECTS; + sdesc->mode = LONG_LIVED_ALLOCING; + + link (&long_lived_allocing, sdesc); + + hurd_btree_storage_desc_insert (&storage_descs, sdesc); + + /* Assume that the folio is free. As we encounter objects, + we will mark them as allocated. */ + free_count += FOLIO_OBJECTS; + } + + if (odesc->type != cap_folio) + { + int idx = addr_extract (odesc->storage, FOLIO_OBJECTS_LOG2); + + debug (5, "%llx/%d, %d -> %llx/%d (%s)", + addr_prefix (folio), + addr_depth (folio), + idx, + addr_prefix (odesc->storage), + addr_depth (odesc->storage), + cap_type_string (odesc->type)); + + bit_set (sdesc->alloced, sizeof (sdesc->alloced), idx); + + sdesc->free --; + free_count --; + } + + } + + debug (1, "Have %d initial free objects", free_count); + /* XXX: We can only call this after initialization is complete. + This presents a problem: we might require additional storage + descriptors than a single pre-allocated page provides. This is + quite unlikely but something we really need to deal with. */ + check_slab_space_reserve (); +} diff --git a/libhurd-mm/storage.h b/libhurd-mm/storage.h new file mode 100644 index 0000000..f4d27a1 --- /dev/null +++ b/libhurd-mm/storage.h @@ -0,0 +1,64 @@ +/* storage.h - Storage allocation 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 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 + 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. */ + +#ifndef _HURD_STORAGE_H +#define _HURD_STORAGE_H + +#include <hurd/addr.h> +#include <hurd/cap.h> + +enum storage_expectancy + { + /* Storage with an unknown life expectancy. */ + STORAGE_UNKNOWN = 0, + /* Storage that is likely to be deallocated quickly (seconds to a + couple of minutes). */ + STORAGE_EPHEMERAL, + /* Storage that is likely to be deallocated at some time, but + program will continue running much longer. */ + STORAGE_MEDIUM_LIVED, + /* Storage with an expected long-life (storage will most likely + not be deallocated). */ + STORAGE_LONG_LIVED, + }; + +/* Allocate an object of type TYPE. The object has a life expectancy + of EXPECTANCY. If ADDR is not ADDR_VOID, a capability to the + storage will be saved at ADDR. On success, the address of the + storage object is returned. Otherwise, ADDR_VOID. ACTIVITY is the + activity to use to account the memory. */ +extern addr_t storage_alloc (addr_t activity, + enum cap_type type, + enum storage_expectancy expectancy, + addr_t addr); + +/* Frees the storage at STORAGE. STORAGE must be the address returned + by storage_alloc (NOT the address provided to storage_alloc). If + UNMAP_NOW is not true, revoking the storage may be delayed. */ +extern void storage_free (addr_t storage, bool unmap_now); + +/* Initialize the storage sub-system. */ +extern void storage_init (void); + +/* Used by as_init to initialize a folio's shadow object. */ +extern void storage_shadow_setup (struct cap *cap, addr_t folio); + +#endif /* _HURD_STORAGE_H */ |