//
// This software is copyright (c) 2006 Scott Wood <scott@buserror.net>.
//
-// Permission is hereby granted, free of charge, to any person obtaining a copy of
-// this software and associated documentation files (the "Software"), to deal with
-// the Software without restriction, including without limitation the rights to
-// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
-// of the Software, and to permit persons to whom the Software is furnished to do
-// so, subject to the following condition:
+// This software is provided 'as-is', without any express or implied warranty.
+// In no event will the authors or contributors be held liable for any damages
+// arising from the use of this software.
//
-// The above copyright notice and this permission notice shall be
-// included in all copies or substantial portions of the Software.
-//
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
-// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-// CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
-// SOFTWARE.
+// Permission is hereby granted to everyone, free of charge, to use, copy,
+// modify, prepare derivative works of, publish, distribute, perform,
+// sublicense, and/or sell copies of the Software, provided that the above
+// copyright notice and disclaimer of warranty be included in all copies or
+// substantial portions of this software.
#include <kern/mem.h>
#include <kern/pagealloc.h>
-#include <util/misc.h>
+#include <kern/rmap.h>
+#include <kern/pagetable.h>
namespace Mem {
- using Util::round_up;
- // static uint rmaps_per_page = Arch::page_size / sizeof(RMapNode);
-
- // If RMapNode's length becomes something other than 8 longs,
- // change "3" to the base-2 log of the number of longs.
-
- static int rmap_shift = Arch::page_shift - _LL_LONG_LOGBYTES - 3;
-
- // static int rmap_dirs_per_page = Arch::page_size / sizeof(RMapNode *);
- static int rmap_dir_shift = Arch::page_shift - _LL_LONG_LOGBYTES;
- static int rmap_lastlevel_shift = rmap_shift + Arch::page_shift;
+ static const ulong rmap_node_len =
+ 1 << ll_get_order_round_up(sizeof(RMapNode));
- static int rmap_dir_levels = (64 - rmap_lastlevel_shift - 1)
- / rmap_dir_shift;
-
- static int rmap_toplevel_shift = rmap_dir_shift * rmap_dir_levels
- + rmap_lastlevel_shift;
-
- static inline u64 addr_to_dir_offset(u64 addr, int shift)
- {
- return (addr >> shift) & ((1ULL << rmap_dir_shift) - 1);
- }
-
- static inline u64 addr_to_offset(u64 addr)
- {
- return (addr >> Arch::page_shift) & ((1ULL << rmap_shift) - 1);
- }
-
- RMapTable::RMapTable()
- {
- // All RMap tables must have at least one dir level, in order to
- // simplify the code. If it turns out that a lot of memory is
- // wasted due to this, the code could be made more complex in order
- // to allow one-level rmap tables. Currently, on 4KiB-page systems,
- // a page is wasted per under-512KiB aspace (32-bit) or under-256KiB
- // aspace (64-bit).
- //
- // Dynamic levels would have to be implemented in generic-pte for
- // the wastage here to be meaningful.
-
- toplevel_shift = rmap_lastlevel_shift;
- toplevel = Mem::alloc_pages(1);
- bzero(toplevel, Arch::page_size);
- }
-
- RMapNode *RMapTable::get_rmap(u64 virtaddr, bool add)
- {
- assert(rmap_lock.held_by_curthread());
- int shift = toplevel_shift;
- void *table = toplevel;
-
- while (toplevel_shift < rmap_toplevel_shift &&
- (virtaddr >> (toplevel_shift + rmap_dir_shift)))
- {
- if (!add)
- return NULL;
-
- shift += rmap_dir_shift;
- toplevel_shift += rmap_dir_shift;
-
- toplevel = Mem::alloc_pages(1);
- bzero(toplevel, Arch::page_size);
-
- static_cast<void **>(toplevel)[0] = table;
- table = toplevel;
- }
-
- while (shift >= rmap_lastlevel_shift) {
- int off = addr_to_dir_offset(virtaddr, shift);
- void *new_table = static_cast<void **>(table)[off];
-
- if (!new_table) {
- new_table = Mem::alloc_pages(1);
- bzero(new_table, Arch::page_size);
- static_cast<void **>(table)[off] = new_table;
- }
-
- table = new_table;
- shift -= rmap_dir_shift;
- }
-
- assert(shift + rmap_dir_shift - rmap_shift == Arch::page_shift);
-
- int off = addr_to_offset(virtaddr);
- return &static_cast<RMapNode *>(table)[off];
- }
-
void RMapTable::map(VirtualArea *dsva, PageTable *usptbl,
u64 dsvaddr, u64 usvaddr)
{
RMapNode *dsrmap = dsva->aspace->page_table->
- rmap_table.get_rmap(dsvaddr, true);
+ rmap_table.tree.lookup(dsvaddr, true);
assert(!dsrmap->va);
dsrmap->va = dsva;
dsrmap->tail.init();
if (usptbl) {
- RMapNode *usrmap = usptbl->rmap_table.get_rmap(usvaddr);
+ RMapNode *usrmap = usptbl->rmap_table.tree.lookup(usvaddr);
assert(usrmap);
assert(usrmap->va->aspace->page_table == usptbl);
void RMapTable::unmap(u64 virtaddr)
{
Lock::AutoLock autolock(rmap_lock);
- RMapNode *head = get_rmap(virtaddr);
+ RMapNode *head = tree.lookup(virtaddr);
if (!head || !head->va)
return;
Util::ListNoAutoInit *node = &head->head, *oldnode;
do {
- ulong off = reinterpret_cast<ulong>(node) & (sizeof(RMapNode) - 1);
- if (off == RMapNode::head_offset) {
+ ulong off = reinterpret_cast<ulong>(node) & (rmap_node_len - 1);
+ if (off == RMap::head_offset) {
RMapNode *rmap = node->listentry(RMapNode, head);
Region region = { rmap->vaddr,
rmap->va->aspace->page_table->unmap(region);
rmap->va = NULL;
} else {
- assert(off == RMapNode::tail_offset);
+ assert(off == RMap::tail_offset);
}
oldnode = node;
void RMapTable::break_copy_on_write(u64 virtaddr, Page *new_page)
{
assert(rmap_lock.held_by_curthread());
- RMapNode *head = get_rmap(virtaddr);
+ RMapNode *head = tree.lookup(virtaddr);
RMapNode *still_cow = NULL;
assert(head && head->va);
Util::ListNoAutoInit *node = &head->head;
do {
- ulong off = reinterpret_cast<ulong>(node) & (sizeof(RMapNode) - 1);
- if (off == RMapNode::head_offset) {
+ ulong off = reinterpret_cast<ulong>(node) & (rmap_node_len - 1);
+ if (off == RMap::head_offset) {
RMapNode *rmap = node->listentry(RMapNode, head);
RegionWithOffset region;
rmap->va->aspace->page_table->map(region, flags);
} else {
- assert(off == RMapNode::tail_offset);
+ assert(off == RMap::tail_offset);
if (still_cow) {
RMapNode *rmap = node->listentry(RMapNode, tail);