648 lines
18 KiB
C++
648 lines
18 KiB
C++
// AUTOMATICALLY GENERATED -- DO NOT EDIT! -*- c++ -*-
|
|
|
|
#include "mapping_inline.h"
|
|
#include "mapping_inline_i.h"
|
|
|
|
#line 48 "mapping.cpp"
|
|
|
|
// The mapping database.
|
|
|
|
// This implementation encodes mapping trees in very compact arrays of
|
|
// fixed sizes, prefixed by a tree header (mapping_tree_t). Array
|
|
// sizes can vary from 4 mappings to 4<<15 mappings. For each size,
|
|
// we set up a slab allocator. To grow or shrink the size of an
|
|
// array, we have to allocate a larger or smaller tree from the
|
|
// corresponding allocator and then copy the array elements.
|
|
//
|
|
// The array elements (mapping_t) contain a tree depth element. This
|
|
// depth and the relative position in the array is all information we
|
|
// need to derive tree structure information. Here is an example:
|
|
//
|
|
// array
|
|
// element depth
|
|
// number value comment
|
|
// --------------------------
|
|
// 0 0 Sigma0 mapping
|
|
// 1 1 child of element #0 with depth 0
|
|
// 2 2 child of element #1 with depth 1
|
|
// 3 2 child of element #1 with depth 1
|
|
// 4 3 child of element #3 with depth 2
|
|
// 5 2 child of element #1 with depth 1
|
|
// 6 3 child of element #5 with depth 2
|
|
// 7 1 child of element #0 with depth 0
|
|
//
|
|
// This array is a pre-order encoding of the following tree:
|
|
//
|
|
// 0
|
|
// / \
|
|
// 1 7
|
|
// / | \
|
|
// 2 3 5
|
|
// | |
|
|
// 4 6
|
|
|
|
// IDEAS for enhancing this implementation:
|
|
|
|
// We often have to find a tree header corresponding to a mapping.
|
|
// Currently, we do this by iterating backwards over the array
|
|
// containing the mappings until we find the Sigma0 mapping, from
|
|
// whose address we can compute the address of the tree header. If
|
|
// this becomes a problem, we could add one more byte to the mappings
|
|
// with a hint (negative array offset) where to find the sigma0
|
|
// mapping. (If the hint value overflows, just iterate using the hint
|
|
// value of the mapping we find with the first hint value.) Another
|
|
// idea (from Adam) would be to just look up the tree header by using
|
|
// the physical address from the page-table lookup, but we would need
|
|
// to change the interface of the mapping database for that (pass in
|
|
// the physical address at all times), or we would have to include the
|
|
// physical address (or just the address of the tree header) in the
|
|
// mapdb_t-user-visible mapping_t (which could be different from the
|
|
// internal tree representation). (XXX: Implementing one of these
|
|
// ideas is probably worthwile doing!)
|
|
|
|
// Instead of copying whole trees around when they grow or shrink a
|
|
// lot, or copying parts of trees when inserting an element, we could
|
|
// give up the array representation and add a "next" pointer to the
|
|
// elements -- that is, keep the tree of mappings in a
|
|
// pre-order-encoded singly-linked list (credits to: Christan Szmajda
|
|
// and Adam Wiggins). 24 bits would probably be enough to encode that
|
|
// pointer. Disadvantages: Mapping entries would be larger, and the
|
|
// cache-friendly space-locality of tree entries would be lost.
|
|
|
|
// The current handling of superpages sucks rocks both in this module
|
|
// and in our user, ipc_map.cc. We could support multiple page sizes
|
|
// by not using a physframe[] array only for the largest page size.
|
|
// (Entries of that array point to the top-level mappings -- sigma0
|
|
// mappings.) Mapping-tree entries would then either be regular
|
|
// mappings or pointers to an array of mappings of the next-smaller
|
|
// size. (credits: Christan Szmajda)
|
|
//
|
|
// physframe[]
|
|
// -------------------------------
|
|
// | | | | | | | | | | | | | | | | array of ptr to 4M mapping_tree_t's
|
|
// ---|---------------------------
|
|
// |
|
|
// v a mapping_tree_t
|
|
// ---------------
|
|
// | | tree header
|
|
// |-------------|
|
|
// | | mapping_t *or* ptr to array of ptr to 4K trees
|
|
// | | e.g.
|
|
// | ----------------|
|
|
// | | v array of ptr to 4M mapping_tree_t's
|
|
// --------------- -------------------------------
|
|
// | | | | | | | | | | | | | | | |
|
|
// ---|---------------------------
|
|
// |
|
|
// v a mapping_tree_t
|
|
// ---------------
|
|
// | | tree header
|
|
// |-------------|
|
|
// | | mapping_t
|
|
// | |
|
|
// | |
|
|
// | |
|
|
// ---------------
|
|
//-
|
|
#line 151 "mapping.cpp"
|
|
|
|
#ifndef offsetof // should be defined in stddef.h, but isn't
|
|
#line 153 "mapping.cpp"
|
|
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
|
|
#line 154 "mapping.cpp"
|
|
#endif
|
|
|
|
#line 261 "mapping.cpp"
|
|
|
|
mapping_tree_t *
|
|
mapping_t::tree()
|
|
{
|
|
mapping_t *m = this;
|
|
|
|
while (m->data()->depth > Depth_sigma0_mapping)
|
|
{
|
|
// jump in bigger steps if this is not a free mapping
|
|
if (! m->unused())
|
|
{
|
|
m -= m->data()->depth;
|
|
continue;
|
|
}
|
|
|
|
m--;
|
|
}
|
|
|
|
return reinterpret_cast<mapping_tree_t *>
|
|
(reinterpret_cast<char *>(m) - offsetof(mapping_tree_t, _mappings));
|
|
}
|
|
|
|
#line 282 "mapping.cpp"
|
|
|
|
//
|
|
// more of class mapping_t
|
|
//
|
|
|
|
mapping_t *
|
|
mapping_t::parent()
|
|
{
|
|
if (data()->depth <= Depth_sigma0_mapping)
|
|
{
|
|
// Sigma0 mappings don't have a parent.
|
|
return 0;
|
|
}
|
|
|
|
// Iterate over mapping entries of this tree backwards until we find
|
|
// an entry with a depth smaller than ours. (We assume here that
|
|
// "special" depths (empty, end) are larger than Depth_max.)
|
|
mapping_t *m = this - 1;
|
|
|
|
while (m->data()->depth >= data()->depth)
|
|
m--;
|
|
|
|
return m;
|
|
}
|
|
|
|
#line 306 "mapping.cpp"
|
|
|
|
mapping_t *
|
|
mapping_t::next_iter()
|
|
{
|
|
mapping_tree_t *t = tree();
|
|
mapping_t *last_in_tree = t->mappings() + t->number_of_entries() - 1;
|
|
|
|
mapping_t *m = this;
|
|
|
|
// Look for a valid element in the tree structure.
|
|
while (m != last_in_tree)
|
|
{
|
|
m++;
|
|
if (! m->unused())
|
|
return m; // Found a valid entry!
|
|
|
|
// Don't iterate to end of tree if this is the last tree entry.
|
|
if (m->data()->depth == Depth_end)
|
|
return 0;
|
|
}
|
|
|
|
// Couldn't find a non-empty element behind ourselves in the tree
|
|
// structure.
|
|
return 0;
|
|
}
|
|
|
|
#line 331 "mapping.cpp"
|
|
|
|
mapping_t *
|
|
mapping_t::next_child(mapping_t *parent)
|
|
{
|
|
// Find the next valid entry in the tree structure.
|
|
mapping_t *m = next_iter();
|
|
|
|
// If we didn't find an entry, or if the entry cannot be a child of
|
|
// "parent", return 0
|
|
if (m == 0
|
|
|| m->data()->depth <= parent->data()->depth)
|
|
return 0;
|
|
|
|
return m; // Found!
|
|
}
|
|
|
|
#line 346 "mapping.cpp"
|
|
|
|
// helpers
|
|
|
|
//
|
|
// class mapping_tree_t
|
|
//
|
|
|
|
// This function copies the elements of mapping tree src to mapping
|
|
// tree dst, ignoring empty elements (that is, compressing the
|
|
// source tree. In-place compression is supported.
|
|
void
|
|
mapping_tree_t::copy_compact_tree(mapping_tree_t *dst, mapping_tree_t *src)
|
|
{
|
|
dst->_count = 0;
|
|
dst->_empty_count = 0;
|
|
|
|
mapping_t *d = dst->mappings();
|
|
|
|
for (mapping_t *s = src->mappings();
|
|
s < src->mappings() + src->number_of_entries();
|
|
s++)
|
|
{
|
|
if (s->unused()) // entry free
|
|
{
|
|
if (s->data()->depth == Depth_end)
|
|
break;
|
|
continue;
|
|
}
|
|
|
|
*d++ = *s;
|
|
dst->_count += 1;
|
|
}
|
|
|
|
assert (dst->_count == src->_count);
|
|
assert (d < dst->mappings() + dst->number_of_entries());
|
|
|
|
d->data()->depth = Depth_end;
|
|
dst->mappings()[dst->number_of_entries() - 1].data()->depth = Depth_end;
|
|
} // copy_compact_tree()
|
|
|
|
#line 397 "mapping.cpp"
|
|
|
|
|
|
mapdb_t::mapdb_t()
|
|
{
|
|
vm_offset_t page_number = kmem::info()->main_memory.high / PAGE_SIZE + 1;
|
|
|
|
// allocate physframe array
|
|
check ( physframe = reinterpret_cast<physframe_data *>
|
|
(kmem::alloc(page_number * sizeof(physframe_data))) );
|
|
|
|
memset(physframe, 0, page_number * sizeof(physframe_data));
|
|
|
|
// create a slab for each mapping tree size
|
|
for (int slab_number = 0;
|
|
slab_number <= Size_id_max;
|
|
slab_number++ )
|
|
{
|
|
unsigned elem_size =
|
|
(Size_factor << slab_number) * sizeof(mapping_t)
|
|
+ sizeof(mapping_tree_t);
|
|
|
|
allocator_for_treesize[slab_number] =
|
|
new kmem_slab_t(((PAGE_SIZE / elem_size) < 40
|
|
? 8*PAGE_SIZE : PAGE_SIZE),
|
|
elem_size, 1);
|
|
}
|
|
|
|
// create a sigma0 mapping for all physical pages
|
|
for (unsigned page_id = 0; page_id < page_number; page_id++)
|
|
{
|
|
mapping_tree_t *t;
|
|
check( (t = physframe[page_id].tree
|
|
= reinterpret_cast<mapping_tree_t*>
|
|
(allocator_for_treesize[0]->alloc())) );
|
|
|
|
t->_count = 1; // 1 valid mapping
|
|
t->_size_id = 0; // size is equal to Size_factor << 0
|
|
t->_empty_count = 0; // no gaps in tree representation
|
|
|
|
t->mappings()[0].data()->depth = Depth_sigma0_mapping;
|
|
t->mappings()[0].data()->address = page_id;
|
|
t->mappings()[0].data()->space = config::sigma0_taskno;
|
|
t->mappings()[0].data()->size = 0;
|
|
|
|
t->mappings()[1].data()->depth = Depth_end;
|
|
|
|
// We also always set the end tag on last entry so that we can
|
|
// check whether it has been overwritten.
|
|
t->mappings()[t->number_of_entries() - 1].data()->depth = Depth_end;
|
|
}
|
|
} // mapdb_t()
|
|
|
|
#line 448 "mapping.cpp"
|
|
|
|
|
|
// insert a new mapping entry with the given values as child of
|
|
// "parent" After locating the right place for the new entry, it will
|
|
// be stored there (if this place is empty) or the following entries
|
|
// moved by one entry.
|
|
|
|
// We assume that there is at least one free entry at the end of the
|
|
// array so that at least one insert() operation can succeed between a
|
|
// lock()/free() pair of calls. This is guaranteed by the free()
|
|
// operation which allocates a larger tree if the current one becomes
|
|
// to small.
|
|
mapping_t *
|
|
mapdb_t::insert(mapping_t *parent,
|
|
space_t *space,
|
|
vm_offset_t va,
|
|
vm_size_t size,
|
|
mapping_type_t type)
|
|
{
|
|
assert(type == Map_mem); // we don't yet support Map_io
|
|
|
|
mapping_tree_t *t = parent->tree();
|
|
|
|
// We cannot continue if the last array entry is not free. This
|
|
// only happens if an earlier call to free() with this mapping tree
|
|
// couldn't allocate a bigger array. In this case, signal an
|
|
// out-of-memory condition.
|
|
if (! t->mappings()[t->number_of_entries() - 1].unused())
|
|
return 0;
|
|
|
|
// If the parent mapping already has the maximum depth, we cannot
|
|
// insert a child.
|
|
if (parent->data()->depth == Depth_max)
|
|
return 0;
|
|
|
|
mapping_t *insert = 0;
|
|
|
|
bool
|
|
found_free_entry = false,
|
|
need_to_move = false;
|
|
|
|
mapping_t temp;
|
|
|
|
// Find a free entry in the array encoding the tree, and find the
|
|
// insertion point for the new entry. These two entries might not
|
|
// be equivalent, so we may need to move entries backwards in the
|
|
// array. In this implementation, we move entries as we traverse
|
|
// the array, instead of doing one big memmove
|
|
for (mapping_t *m = parent + 1;
|
|
m < t->mappings() + t->number_of_entries();
|
|
m++)
|
|
{
|
|
if (m->unused())
|
|
{
|
|
// We found a free entry in the tree -- allocate it.
|
|
found_free_entry = true;
|
|
t->_count += 1;
|
|
|
|
// Did we find an empty element != the end tag?
|
|
if (m->data()->depth == Depth_empty)
|
|
{
|
|
t->_empty_count -= 1;
|
|
}
|
|
// Else we have found the end tag. If there is another
|
|
// array entry left, apply a new end tag to the array
|
|
else if (m + 1 < t->mappings() + t->number_of_entries())
|
|
{
|
|
(m + 1)->data()->depth = Depth_end;
|
|
}
|
|
|
|
// if we haven't identified a place for inserting the new
|
|
// element, this is it.
|
|
if (! need_to_move)
|
|
insert = m;
|
|
}
|
|
else if (! need_to_move
|
|
&& m->data()->depth <= parent->data()->depth)
|
|
{
|
|
// we found a non-descendant of ourselves -- need to make
|
|
// space for new child
|
|
need_to_move = true;
|
|
insert = m;
|
|
temp = *insert;
|
|
|
|
continue;
|
|
}
|
|
|
|
if (need_to_move)
|
|
{
|
|
// replace *m with temp (which used to be *(m - 1); but
|
|
// *(m - 1) has since been overwritten), and load temp with
|
|
// the old value of *m
|
|
mapping_t temp2;
|
|
|
|
temp2 = *m;
|
|
*m = temp;
|
|
temp = temp2;
|
|
}
|
|
|
|
if (found_free_entry)
|
|
break;
|
|
}
|
|
|
|
assert(insert && found_free_entry);
|
|
|
|
// found a place to insert new child.
|
|
insert->data()->depth = mapping_depth_t(parent->data()->depth + 1);
|
|
insert->data()->address = va >> PAGE_SHIFT;
|
|
insert->data()->space = space->space();
|
|
insert->data()->size = (size == SUPERPAGE_SIZE);
|
|
|
|
return insert;
|
|
} // insert()
|
|
|
|
#line 561 "mapping.cpp"
|
|
|
|
mapping_t *
|
|
mapdb_t::lookup(space_t *space,
|
|
vm_offset_t va,
|
|
mapping_type_t type)
|
|
{
|
|
vm_offset_t phys = space->virt_to_phys(va);
|
|
|
|
if (phys == 0xffffffff)
|
|
return 0;
|
|
|
|
mapping_tree_t *t;
|
|
|
|
// get and lock the tree.
|
|
// XXX For now, use a simple lock with helping. Later
|
|
// unify locking with our request scheme.
|
|
physframe[phys >> PAGE_SHIFT].lock.lock();
|
|
|
|
t = physframe[phys >> PAGE_SHIFT].tree;
|
|
assert(t);
|
|
|
|
mapping_t *m;
|
|
|
|
for (m = t->mappings();
|
|
m->data()->depth != Depth_end
|
|
&& m < t->mappings() + t->number_of_entries();
|
|
m++)
|
|
{
|
|
if (m->data()->space == space->space()
|
|
&& m->data()->address == va >> PAGE_SHIFT)
|
|
{
|
|
// found!
|
|
return m;
|
|
}
|
|
}
|
|
|
|
// not found -- unlock tree
|
|
physframe[phys >> PAGE_SHIFT].lock.clear();
|
|
|
|
return 0;
|
|
} // lookup()
|
|
|
|
#line 602 "mapping.cpp"
|
|
|
|
void
|
|
mapdb_t::free(mapping_t* mapping_of_tree)
|
|
{
|
|
mapping_tree_t *t = mapping_of_tree->tree();
|
|
|
|
// We assume that the zeroth mapping of the tree is a sigma0
|
|
// mapping, that is, its virtual address == the page's physical
|
|
// address.
|
|
vm_offset_t phys_pno = t->mappings()[0].data()->address;
|
|
|
|
// We are the owner of the tree lock.
|
|
assert(physframe[phys_pno].lock.lock_owner() == current());
|
|
|
|
// Before we unlock the tree, we need to make sure that there is
|
|
// room for at least one new mapping. In particular, this means
|
|
// that the last entry of the array encoding the tree must be free.
|
|
|
|
// (1) When we use up less than a quarter of all entries of the
|
|
// array encoding the tree, copy to a smaller tree. Otherwise, (2)
|
|
// if the last entry is free, do nothing. Otherwise, (3) if less
|
|
// than 3/4 of the entries are used, compress the tree. Otherwise,
|
|
// (4) copy to a larger tree.
|
|
|
|
bool maybe_out_of_memory = false;
|
|
|
|
do // (this is not actually a loop, just a block we can "break" out of)
|
|
{
|
|
// (1) Do we need to allocate a smaller tree?
|
|
if (t->_size_id > 0 // must not be smallest size
|
|
&& (t->_count << 2) < t->number_of_entries())
|
|
{
|
|
mapping_tree_t *new_t =
|
|
reinterpret_cast<mapping_tree_t *>
|
|
(allocator_for_treesize[t->_size_id - 1]->alloc());
|
|
|
|
if (new_t)
|
|
{
|
|
// XXX should be asserted by allocator:
|
|
new_t->_size_id = t->_size_id - 1;
|
|
new_t->mappings()[new_t->number_of_entries() - 1].data()->depth
|
|
= Depth_end;
|
|
|
|
mapping_tree_t::copy_compact_tree(new_t, t);
|
|
|
|
// Register new tree.
|
|
physframe[phys_pno].tree = new_t;
|
|
|
|
allocator_for_treesize[t->_size_id]->free(t);
|
|
t = new_t;
|
|
|
|
break;
|
|
}
|
|
}
|
|
|
|
// (2) Is last entry is free?
|
|
if (t->mappings()[t->number_of_entries() - 1].unused())
|
|
break; // OK, last entry is free.
|
|
|
|
// Last entry is not free -- either compress current array
|
|
// (i.e., move free entries to end of array), or allocate bigger
|
|
// array.
|
|
|
|
// (3) Should we compress the tree?
|
|
// We also try to compress if we cannot allocate a bigger
|
|
// tree because there is no bigger tree size.
|
|
if (t->_count < (t->number_of_entries() >> 2)
|
|
+ (t->number_of_entries() >> 1)
|
|
|| t->_size_id == Size_id_max) // cannot enlarge?
|
|
{
|
|
if (t->_size_id == Size_id_max)
|
|
maybe_out_of_memory = true;
|
|
|
|
mapping_tree_t::copy_compact_tree(t, t); // in-place compression
|
|
|
|
break;
|
|
}
|
|
|
|
// (4) OK, allocate a bigger array.
|
|
|
|
mapping_tree_t *new_t =
|
|
reinterpret_cast<mapping_tree_t*>
|
|
(allocator_for_treesize[t->_size_id + 1]->alloc());
|
|
|
|
if (new_t)
|
|
{
|
|
// XXX should be asserted by allocator:
|
|
new_t->_size_id = t->_size_id + 1;
|
|
new_t->mappings()[new_t->number_of_entries() - 1].data()->depth
|
|
= Depth_end;
|
|
|
|
mapping_tree_t::copy_compact_tree(new_t, t);
|
|
|
|
// Register new tree.
|
|
physframe[phys_pno].tree = new_t;
|
|
|
|
allocator_for_treesize[t->_size_id]->free(t);
|
|
t = new_t;
|
|
}
|
|
else
|
|
{
|
|
// out of memory -- just do tree compression and hope that helps.
|
|
maybe_out_of_memory = true;
|
|
|
|
mapping_tree_t::copy_compact_tree(t, t); // in-place compression
|
|
}
|
|
}
|
|
while (false);
|
|
|
|
// The last entry of the tree should now be free -- exept if we're
|
|
// out of memory.
|
|
assert(t->mappings()[t->number_of_entries() - 1].unused()
|
|
|| maybe_out_of_memory);
|
|
|
|
// Unlock tree.
|
|
physframe[phys_pno].lock.clear();
|
|
} // free()
|
|
|
|
#line 719 "mapping.cpp"
|
|
|
|
// Delete mappings from a tree. This is easy to do: We just have to
|
|
// iterate over the array encoding the tree.
|
|
bool
|
|
mapdb_t::flush(mapping_t *m, bool me_too)
|
|
{
|
|
mapping_tree_t *t = m->tree();
|
|
mapping_t *start_of_deletions = m;
|
|
unsigned m_depth = m->data()->depth;
|
|
unsigned deleted = 0, empty_elems_passed = 0;
|
|
|
|
if (me_too)
|
|
{
|
|
m->data()->depth = Depth_empty;
|
|
t->_count -= 1;
|
|
deleted++;
|
|
}
|
|
else
|
|
start_of_deletions++;
|
|
|
|
m++;
|
|
|
|
for (;
|
|
m < t->mappings() + t->number_of_entries()
|
|
&& m->data()->depth != Depth_end;
|
|
m++)
|
|
{
|
|
if (unsigned (m->data()->depth) <= m_depth)
|
|
{
|
|
// Found another data element -- stop deleting. Since we
|
|
// created holes in the tree representation, account for it.
|
|
t->_empty_count += deleted;
|
|
|
|
return true;
|
|
}
|
|
|
|
if (m->data()->depth == Depth_empty)
|
|
{
|
|
empty_elems_passed++;
|
|
continue;
|
|
}
|
|
|
|
// Delete the element.
|
|
m->data()->depth = Depth_empty;
|
|
t->_count -= 1;
|
|
deleted++;
|
|
}
|
|
|
|
// We deleted stuff at the end of the array -- move end tag
|
|
if (start_of_deletions < t->mappings() + t->number_of_entries())
|
|
{
|
|
start_of_deletions->data()->depth = Depth_end;
|
|
|
|
// also, reduce number of free entries
|
|
t->_empty_count -= empty_elems_passed;
|
|
}
|
|
|
|
return true;
|
|
} // flush()
|
|
|
|
#line 778 "mapping.cpp"
|
|
|
|
void
|
|
mapdb_t::grant(mapping_t *m, space_t *new_space, vm_offset_t va)
|
|
{
|
|
m->data()->space = new_space->space();
|
|
m->data()->address = va >> PAGE_SHIFT;
|
|
} // grant()
|