vm tree bb

4 files changed, 595 insertions, 199 deletions

diff --git a/kc/core/Makefile b/kc/core/Makefile
index 85cdb53..53f1cea 100644
--- a/kc/core/Makefile
+++ b/kc/core/Makefile
@@ -12,7 +12,7 @@ CFLAGS += -Wno-unused-const-variable -Wno-unused-function -fvisibility=hidden -g
 SOBJS := 
 GOBJS := entry_x86_64.o reloc_x86_64.o kprint.o serial.o port.o \
 	 kc_main.o main.o memory.o memset.o memcpy.o memmove.o memcmp.o cpu.o \
-	 exceptions.o panic.o
+	 vm_tree.o exceptions.o panic.o
 IOBJS :=
 
 # __attribute__((interrupt)) requires -mgeneral-regs-only
diff --git a/kc/core/memory.c b/kc/core/memory.c
index 87395ba..0efdf81 100644
--- a/kc/core/memory.c
+++ b/kc/core/memory.c
@@ -1,6 +1,7 @@
 #include "memory.h"
 #include "kprint.h"
 #include "panic.h"
+#include "vm_tree.h"
 
 #include <stdint.h>
 
@@ -30,7 +31,7 @@ enum memory_space_flags
     OBJECT_MEMORY_SPACE = 0x03, // a mapping managed by an underlying object
 
     MEMORY_SPACE_TYPE_MASK = 0x0f, //
-    
+
     NOFAULT_MEMORY_FLAG = 0x10, // a mapping that cannot be resolved during a page fault
     NOSWAP_MEMORY_FLAG = 0x20, // a mapping that cannot be swapped out
     COW_MEMORY_FLAG = 0x40, // a mapping that is copy-on-write
@@ -40,16 +41,6 @@ enum memory_space_flags
     INVALID_MEMORY_SPACE = 0xff
 };
 
-struct memory_space
-{
-    enum memory_space_flags flags;
-    page_fault_handler_func handler;
-    void *base;
-    void *head;
-    struct memory_space *next;
-    struct memory_space *prev;
-};
-
 struct page
 {
     uint32_t next: 31;
@@ -64,38 +55,32 @@ static size_t page_array_entries = 0;
 static size_t free_pages = 0;
 
 // the temporary mapping place. never use this permanently.
-static void *const temp = (void *)0xffffffffffa00000;
+static void *const vm_temp = (void *)0xffffffffffa00000;
 static uint64_t *const kernel_pm1 = (uint64_t *)0xffffffffffc00000;
 static uint64_t *const kernel_pm2 = (uint64_t *)0xffffffffffffe000;
 
 static uint64_t *get_kernel_pm1e(void *vaddr);
 static uint64_t *get_kernel_pm2e(void *vaddr);
-static void *get_virtual_page(enum page_map_flags flags);
 static void *page_map_at(void *vaddr, phys_addr_t paddr, enum page_map_flags flags);
 
-// handlers for memory space types
-int anonymous_page_handler(uint32_t code, void *address);
-
-// the system memory_space's that are always present
-
-// NULL if the system address spaces are not set up
-static struct memory_space *root_memory_space;
-static struct memory_space core_code_space; // kernel core code
-static struct memory_space core_static_space; // kernel core static data/bss
-static struct memory_space core_object_space; // kernel core dynamic space
+struct vm_tree core_vm_tree;
+struct vm_tree_node core_pagestack_node;
+struct vm_tree_node core_image_node;
+struct vm_tree_node core_object_node;
+struct vm_tree_node core_pagemaps_node;
 
 static struct memory_range init_grab_pages(struct memory_range *ranges,
-                                           int count,
-                                           size_t size)
+        int count,
+        size_t size)
 {
     struct memory_range request = {SYSTEM_MEMORY,
-                                   0,
-                                   align_next(size, page_size(1))};
-    
+        0,
+        align_next(size, page_size(1))};
+
     for (int i = 0; i < count; i++)
     {
         if (ranges[i].type != AVAILABLE_MEMORY ||
-            ranges[i].base < (1 << 20)) // leave pages below 1MiB alone.
+                ranges[i].base < (1 << 20)) // leave pages below 1MiB alone.
         {
             continue;
         }
@@ -107,7 +92,7 @@ static struct memory_range init_grab_pages(struct memory_range *ranges,
             return request;
         }
     }
-    
+
     request.type = INVALID_MEMORY;
     return request;
 }
@@ -123,13 +108,13 @@ static size_t init_get_max_paddr(struct memory_range *ranges, int count)
         {
             continue;
         }
-        
+
         if ((ranges[i].base + ranges[i].size - 1) > max_paddr)
         {
             max_paddr = ranges[i].base + ranges[i].size - 1;
         }
     }
-    
+
     return max_paddr;
 }
 
@@ -137,10 +122,10 @@ static phys_addr_t get_kernel_pm4_phys(void)
 {
     phys_addr_t pm4_phys;
     __asm__ (
-             "mov %%cr3, %0\n\t"
-             : "=r"(pm4_phys)
-    );
-    
+            "mov %%cr3, %0\n\t"
+            : "=r"(pm4_phys)
+            );
+
     return page_address(pm4_phys, 1);
 }
 
@@ -148,15 +133,15 @@ static phys_addr_t get_kernel_pm3_phys(void)
 {
     phys_addr_t pm3_phys;
     // make a temporary mapping to read pm4
-    uint64_t *pm4 = page_map_at(temp,
-                                get_kernel_pm4_phys(),
-                                CONTENT_RODATA|SIZE_2M);
-    
+    uint64_t *pm4 = page_map_at(vm_temp,
+            get_kernel_pm4_phys(),
+            CONTENT_RODATA|SIZE_2M);
+
     // pm3_phys is in pm4.
     pm3_phys = page_address(pm4[pte_index(&kc_image_base, 4)], 1);
     // never leave a temporary mapping
     page_unmap(pm4);
-    
+
     return pm3_phys;
 }
 
@@ -164,41 +149,43 @@ static void init_map_page_array_pm2(struct memory_range *pm2_pages)
 {
     // now we need to write the physical address of each pm2 page for the
     // page_array in the kernel's pm3.
-    uint64_t *pm3 = page_map_at(temp,
-                                get_kernel_pm3_phys(),
-                                CONTENT_RWDATA|SIZE_2M);
-    
+    uint64_t *pm3 = page_map_at(vm_temp,
+            get_kernel_pm3_phys(),
+            CONTENT_RWDATA|SIZE_2M);
+
     // the first index is NOT zero!
     for (size_t i = 0; i < (pm2_pages->size / PAGE_SIZE); i++)
     {
-        pm3[pte_index(page_array, 3) + i] = (pm2_pages->base + i *
-                                             PAGE_SIZE)|PAGE_NX|PAGE_WR|PAGE_PR;
+        pm3[pte_index(page_array, 3) + i] = (
+                pm2_pages->base + i *
+                PAGE_SIZE)|PAGE_NX|PAGE_WR|PAGE_PR;
     }
     // never forget to unmap temporary mappings.
     page_unmap(pm3);
 }
 
 static void init_create_page_array_map(struct memory_range *pages,
-                                       struct memory_range *maps)
+        struct memory_range *maps)
 {
     // indices for page_array always start at 0
     size_t entry_count = pages->size / PAGE_SIZE;
-    
+
     // every 512 entries we need to re-map and clean.
     for (size_t i = 0; i < entry_count; i += PAGE_TABLE_INDEX_MASK)
     {
-        uint64_t *pm1 = page_map_at(temp,
-                                           maps->base + i * PAGE_SIZE,
-                                           CONTENT_RWDATA|SIZE_2M);
+        uint64_t *pm1 = page_map_at(
+                vm_temp,
+                maps->base + i * PAGE_SIZE,
+                CONTENT_RWDATA|SIZE_2M);
         memset(pm1, 0, PAGE_SIZE);
         for (size_t j = 0;
-             (j < PAGE_TABLE_INDEX_MASK) && ((j + i) < entry_count);
-             j++)
+                (j < PAGE_TABLE_INDEX_MASK) && ((j + i) < entry_count);
+                j++)
         {
             pm1[j] = (pages->base + (i + j) * PAGE_SIZE)|
-                     PAGE_NX|PAGE_WR|PAGE_PR; 
+                PAGE_NX|PAGE_WR|PAGE_PR; 
         }
-        
+
         page_unmap(pm1);
     }
 }
@@ -211,7 +198,7 @@ static void init_set_memory_range(struct memory_range *range)
         {
             return;
         }
-        
+
         if (range->type == AVAILABLE_MEMORY)
         {
             page_free(range->base + PAGE_SIZE * i);
@@ -238,72 +225,46 @@ static void init_create_page_array(struct memory_range *ranges, int count)
     size_t max_paddr = init_get_max_paddr(ranges, count);
     page_array_entries = max_paddr / page_size(1);
     size_t page_array_size = page_array_entries * sizeof(struct page);
-    
+
     // the physical pages that will contain page_array
     struct memory_range pa_pages = init_grab_pages(ranges, count, page_array_size);
-    
+
     // the number of page tables needed to map pa_pages
     // this will be 1 on systems with less than 2GB of memory.
     size_t pm1_count = page_count(pa_pages.size, 2);
     struct memory_range pm1_pages = init_grab_pages(ranges,
-                                                    count,
-                                                    pm1_count * page_size(1));
-    
+            count,
+            pm1_count * page_size(1));
+
     init_create_page_array_map(&pa_pages, &pm1_pages);
-    
+
     // the number of page directories needed to map pa_pages
     // this will be 1 on systems with less than 1TB of memory.
     // who the fuck has 1TB of memory lol
     size_t pm2_count = page_count(pa_pages.size, 3);
     struct memory_range pm2_pages = init_grab_pages(ranges,
-                                                    count,
-                                                    pm2_count * page_size(1));
-    
+            count,
+            pm2_count * page_size(1));
+
     init_create_page_array_map(&pm1_pages, &pm2_pages);
-    
+
     // ok here goes
     init_map_page_array_pm2(&pm2_pages);
-    
+
     memset(page_array, 0, page_array_size);
-    
+
     init_populate_page_array(ranges, count);
     init_populate_page_array(&pa_pages, 1);
     init_populate_page_array(&pm1_pages, 1);
     init_populate_page_array(&pm2_pages, 1);
 }
 
-static struct memory_space init_system_space(void *base, void *head)
-{
-    struct memory_space space = {TRANSLATION_MEMORY_SPACE|
-            NOFAULT_MEMORY_FLAG|
-            NOSWAP_MEMORY_FLAG,
-        NULL,
-        base,
-        head,
-        NULL,
-        NULL};
-    return space;
-}
-
-static struct memory_space init_anonymous_space(void *base, void *head)
-{
-    struct memory_space space = {ANONYMOUS_MEMORY_SPACE|
-            NOSWAP_MEMORY_FLAG,
-        &anonymous_page_handler,
-        base,
-        head,
-        NULL,
-        NULL};
-
-    return space;
-}
-
 static void *page_map_at(void *vaddr,
-                         phys_addr_t paddr,
-                         enum page_map_flags flags)
+        phys_addr_t paddr,
+        enum page_map_flags flags)
 {
     uint64_t entry = PAGE_PR;
-    
+
     switch (flags & CONTENT_MASK)
     {
         case CONTENT_RODATA:
@@ -315,10 +276,10 @@ static void *page_map_at(void *vaddr,
         default:
             break;
     }
-    
+
     size_t offset;
     uint64_t *pte;
-    
+
     switch (flags & SIZE_MASK)
     {
         case SIZE_2M:
@@ -335,52 +296,85 @@ static void *page_map_at(void *vaddr,
             offset = 0;
             pte = NULL;
     }
-    
+
     if (!pte)
     {
         return NULL;
     }
-    
+
     *pte = entry;
     return (char *)vaddr + offset;
 }
 
 #define KERNEL_OBJECT_SPACE_EXTENT 0x1000000 // 16MiB for kernel object space?
 
+static void init_vm_node(struct vm_tree_node *node, void *base, void *head)
+{
+    node->key =
+        (struct vm_tree_key)
+        {
+            (uintptr_t)base,
+            (size_t)head - (size_t)base
+        };
+
+    if (!vmt_search_key(&core_vm_tree, &node->key))
+    {
+        kputs("inserting node\n");
+        struct vm_tree_node *p = vmn_predecessor_key(
+                core_vm_tree.root,
+                &node->key);
+        vmt_insert(
+                &core_vm_tree,
+                node,
+                p,
+                vmn_child_direction(node, p));
+    }
+    else
+    {
+        kputs("fatal: overlap on static vm node\n");
+    }
+}
+
 void memory_init(struct kc_boot_data *boot_data)
 {
-    init_create_page_array(boot_data->phys_memory_map.base,
+    init_create_page_array(
+            boot_data->phys_memory_map.base,
             boot_data->phys_memory_map.entries);
 
-    core_code_space = init_system_space(&kc_text_begin, &kc_text_end);
-    core_static_space = init_system_space(&kc_data_begin, &kc_data_end);
-    core_object_space = init_anonymous_space(boot_data->object_space.base,
-            (void *)page_align(&kc_data_end + KERNEL_OBJECT_SPACE_EXTENT, 2));
-
-    root_memory_space = &core_code_space;
+    void * object_space_head = (void *)page_align(
+            boot_data->object_space.size +
+            (uintptr_t)boot_data->object_space.base, 1);
 
-    core_code_space.prev = NULL;
-    core_code_space.next = &core_static_space;
-    core_static_space.prev = &core_code_space;
-    core_static_space.next = &core_object_space;
-    core_object_space.prev = &core_static_space;
-    core_object_space.next = NULL;
+    kputs("vm node 1\n");
+    init_vm_node(
+            &core_image_node,
+            &kc_image_base,
+            (void *)page_align(&kc_data_end, 1));
+    kputs("vm node 2\n");
+    init_vm_node(
+            &core_object_node,
+            (void *)page_align(&kc_data_end, 1),
+            object_space_head);
+    kputs("vm node 3\n");
+    init_vm_node(&core_pagemaps_node, vm_temp, (void *)-1);
 }
 
 void *page_map(phys_addr_t paddr, enum page_map_flags flags)
 {
-    return page_map_at(get_virtual_page(flags), paddr, flags);
+    (void)paddr;
+    (void)flags;
+    return NULL;
 }
 
 void page_unmap(void *vaddr)
 {
     uint64_t *pte = get_kernel_pm2e(vaddr);
-    
+
     if (pte && !(*pte & PAGE_LG))
     {
         pte = get_kernel_pm1e(vaddr);
     }
-    
+
     if (pte)
     {
         *pte = 0;
@@ -391,26 +385,26 @@ void page_unmap(void *vaddr)
 phys_addr_t page_alloc(void)
 {
     int index = first_free_page_index;
-    
+
     if (index > 0)
     {
         page_array[index].used = 1;
         first_free_page_index = page_array[index].next;
         free_pages--;
     }
-    
+
     return (phys_addr_t)index * page_size(1);
 }
 
 void page_free(phys_addr_t paddr)
 {
     int index = paddr / page_size(1);
-    
+
     if ((size_t)index > page_array_entries)
     {
         return;
     }
-    
+
     page_array[index].used = 0;
     page_array[index].next = first_free_page_index;
     first_free_page_index = index;
@@ -449,91 +443,69 @@ static uint64_t *get_kernel_pm2e(void *vaddr)
     return &kernel_pm2[kpm2_index(vaddr)];
 }
 
-static void *get_virtual_page(enum page_map_flags flags)
-{
-    (void)flags;
-    return NULL;
+/*
+   int anonymous_page_handler(uint32_t code, void *address)
+   {
+   kputs("anonymous space fault\n");
+   if (code & PAGE_PR)
+   {
+// there's no reason a protection violation should happen
+// in anonymous space
+panic(UNHANDLED_FAULT);
 }
+// kernel page mappings are built different
+if (address >= (void *)&kc_image_base)
+{
+uint64_t *pm2e = get_kernel_pm2e(address);
 
-static struct memory_space *get_memory_space(void *address)
+if (!page_address(*pm2e, 1))
 {
-    // walk the memory space list
-    struct memory_space *space = root_memory_space;
-    
-    while (space)
-    {
-        kputs("checking a space\n");
-        if ((space->base <= address) && (address < space->head))
-        {
-            kputs("space matched\n");
-            return space;
-        }
-        space = space->next;
-    }
+// create a page table and install it
+phys_addr_t pm1_phys = page_alloc();
+if (pm1_phys)
+{
+uint64_t *pm1;
+pm1 = page_map_at(temp, pm1_phys, CONTENT_RWDATA|SIZE_2M);
+// zero the page
+memset(pm1, 0, PAGE_SIZE);
+// put the table where it goes
+ *pm2e = page_address(pm1_phys, 1)|PAGE_WR|PAGE_PR;
+ page_unmap(pm1);
+ }
+ else
+ {
+ panic(OUT_OF_MEMORY);
+ }
+ }
 
-    return NULL;
+ uint64_t *pm1e = get_kernel_pm1e(address);
+
+ if (pm1e)
+ {
+ phys_addr_t page_phys = page_alloc();
+ if (page_phys)
+ {
+ *pm1e = page_address(page_phys, 1)|PAGE_WR|PAGE_PR;
+// clear a potentially dirty page.
+memset((void *)page_address(address, 1), 0, page_size(1));
+}
+}
 }
 
-int anonymous_page_handler(uint32_t code, void *address)
-{
-    kputs("anonymous space fault\n");
-    if (code & PAGE_PR)
-    {
-        // there's no reason a protection violation should happen
-        // in anonymous space
-        panic(UNHANDLED_FAULT);
-    }
-    // kernel page mappings are built different
-    if (address >= (void *)&kc_image_base)
-    {
-        uint64_t *pm2e = get_kernel_pm2e(address);
-        
-        if (!page_address(*pm2e, 1))
-        {
-            // create a page table and install it
-            phys_addr_t pm1_phys = page_alloc();
-            if (pm1_phys)
-            {
-                uint64_t *pm1;
-                pm1 = page_map_at(temp, pm1_phys, CONTENT_RWDATA|SIZE_2M);
-                // zero the page
-                memset(pm1, 0, PAGE_SIZE);
-                // put the table where it goes
-                *pm2e = page_address(pm1_phys, 1)|PAGE_WR|PAGE_PR;
-                page_unmap(pm1);
-            }
-            else
-            {
-                panic(OUT_OF_MEMORY);
-            }
-        }
-        
-        uint64_t *pm1e = get_kernel_pm1e(address);
-        
-        if (pm1e)
-        {
-            phys_addr_t page_phys = page_alloc();
-            if (page_phys)
-            {
-                *pm1e = page_address(page_phys, 1)|PAGE_WR|PAGE_PR;
-                // clear a potentially dirty page.
-                memset((void *)page_address(address, 1), 0, page_size(1));
-            }
-        }
-    }
-    
-    return 0;
+return 0;
 }
+*/
 
 int page_fault_handler(uint32_t code, void *address)
 {
-    kputs("page faulmt\n");
-    struct memory_space *space = get_memory_space(address);
-    if (space && space->handler)
+    (void)code;
+    kputs("page fault\n");
+    struct vm_tree_key key = {(uintptr_t)address, 1};
+    struct vm_tree_node *node = vmt_search_key(&core_vm_tree, &key);
+    if (node)
     {
-        kputs("found memory space\n");
-        int result = space->handler(code, address);
-        
+        kputs("found memory object\n");
+        int result = 1;
         if (result)
         {
             panic(UNHANDLED_FAULT);
@@ -541,10 +513,9 @@ int page_fault_handler(uint32_t code, void *address)
     }
     else
     {
-        kputs("didn't found memory space\n");
+        kputs("didn't find memory object\n");
         panic(UNHANDLED_FAULT);
     }
-    
     return 0;
 }
 
diff --git a/kc/core/vm_tree.c b/kc/core/vm_tree.c
new file mode 100644
index 0000000..bfb0c8f
--- /dev/null
+++ b/kc/core/vm_tree.c
@@ -0,0 +1,332 @@
+// vm_tree.c
+//
+// AUTHOR NOTE:
+//
+// a great deal of this code is lifted and adapted straight from wikipedia at
+// https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
+//
+// i reserve no rights under copyright law to this material, but i agree to be
+// bound by the terms of the Creative Commons Share-Alike by Attribution license
+//
+// if any of the following is found to be in violation please contact the author
+// at ada.christine.18+sophia _at_ gmail _dot_ com
+//
+// -Ada Christine Fontaine, 1/1/2022
+//
+// LICENSE NOTIFICATION
+//
+// THE WORK (AS DEFINED BELOW) IS PROVIDED UNDER THE TERMS OF THIS CREATIVE
+// COMMONS PUBLIC LICENSE ("CCPL" OR "LICENSE"). THE WORK IS PROTECTED BY
+// COPYRIGHT AND/OR OTHER APPLICABLE LAW. ANY USE OF THE WORK OTHER THAN AS
+// AUTHORIZED UNDER THIS LICENSE OR COPYRIGHT LAW IS PROHIBITED.
+
+// BY EXERCISING ANY RIGHTS TO THE WORK PROVIDED HERE, YOU ACCEPT AND AGREE TO
+// BE BOUND BY THE TERMS OF THIS LICENSE. TO THE EXTENT THIS LICENSE MAY BE
+// CONSIDERED TO BE A CONTRACT, THE LICENSOR GRANTS YOU THE RIGHTS CONTAINED
+// HERE IN CONSIDERATION OF YOUR ACCEPTANCE OF SUCH TERMS AND CONDITIONS. 
+//
+// The full text of the CC-BY-SA 3.0 license can be found here:
+// https://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include "vm_tree.h"
+
+#define assert(expr)
+
+#define NIL NULL
+#define left child[LEFT]
+#define right child[RIGHT]
+// the direction of the child node
+#define childDir(vmn) (vmn == (vmn->parent)->right ? RIGHT : LEFT)
+
+static int compare(uintptr_t a1, size_t s1, uintptr_t a2, size_t s2)
+{
+    // case 1: a1:a1+s1 occupies a region entirely below a2
+    // and is therefore less than.
+    if ((a1 + s1) <= a2)
+    {
+        return -1;
+    }
+    // case 2: a1:a1+s1 occupies a region entirely above (a2+s2)
+    // and is therefore greater than.
+    else if (a1 >= (a2 + s2))
+    {
+        return 1;
+    }
+    // case 3: the above conditions are not satisfied and therefore
+    // the regions overlap and are considered equivalent.
+    return 0;
+}
+
+static int compare_key(struct vm_tree_key const * const k1,
+        struct vm_tree_key const * const k2)
+{
+    return compare(k1->address, k1->size, k2->address, k2->size);
+}
+
+static struct vm_tree_node* RotateDirRoot(
+        struct vm_tree* T,   // red–black tree
+        struct vm_tree_node* P,   // root of subtree (may be the root of T)
+        enum vm_tree_direction dir) {   // dir ∈ { LEFT, RIGHT }
+    struct vm_tree_node* G = P->parent;
+    struct vm_tree_node* S = P->child[1-dir];
+    struct vm_tree_node* C;
+    assert(S != NIL); // pointer to true node required
+    C = S->child[dir];
+    P->child[1-dir] = C; if (C != NIL) C->parent = P;
+    S->child[  dir] = P; P->parent = S;
+    S->parent = G;
+    if (G != NULL)
+        G->child[ P == G->right ? RIGHT : LEFT ] = S;
+    else
+        T->root = S;
+    return S; // new root of subtree
+}
+
+#define RotateDir(N,dir) RotateDirRoot(T,N,dir)
+#define RotateLeft(N)    RotateDirRoot(T,N,LEFT)
+#define RotateRight(N)   RotateDirRoot(T,N,RIGHT)
+
+void vmt_insert(
+        struct vm_tree* T,         // -> red–black tree
+        struct vm_tree_node* N,  // -> node to be inserted
+        struct vm_tree_node* P,  // -> parent node of N ( may be NULL )
+        enum vm_tree_direction dir) // side ( LEFT or RIGHT ) of P where to insert N
+{
+    struct vm_tree_node* G;  // -> parent node of P
+    struct vm_tree_node* U;  // -> uncle of N
+
+    N->color = RED;
+    N->left  = NIL;
+    N->right = NIL;
+    N->parent = P;
+    if (P == NULL) {   // There is no parent
+        T->root = N;     // N is the new root of the tree T.
+        return; // insertion complete
+    }
+    P->child[dir] = N; // insert N as dir-child of P
+    // start of the (do while)-loop:
+    do {
+        if (P->color == BLACK) {
+            // Case_I1 (P black):
+            return; // insertion complete
+        }
+        // From now on P is red.
+        if ((G = P->parent) == NULL) 
+            goto Case_I4; // P red and root
+        // else: P red and G!=NULL.
+        dir = childDir(P); // the side of parent G on which node P is located
+        U = G->child[1-dir]; // uncle
+        if (U == NIL || U->color == BLACK) // considered black
+            goto Case_I56; // P red && U black
+        // Case_I2 (P+U red):
+        P->color = BLACK;
+        U->color = BLACK;
+        G->color = RED;
+        N = G; // new current node
+        // iterate 1 black level higher
+        //   (= 2 tree levels)
+    } while ((P = N->parent) != NULL);
+    // end of the (do while)-loop
+    // Leaving the (do while)-loop (after having fallen through from Case_I2).
+    // Case_I3: N is the root and red.
+    return; // insertion complete
+Case_I4: // P is the root and red:
+    P->color = BLACK;
+    return; // insertion complete
+Case_I56: // P red && U black:
+    if (N == P->child[1-dir])
+    { // Case_I5 (P red && U black && N inner grandchild of G):
+        RotateDir(P,dir); // P is never the root
+        N = P; // new current node
+        P = G->child[dir]; // new parent of N
+        // fall through to Case_I6
+    }
+    // Case_I6 (P red && U black && N outer grandchild of G):
+    RotateDirRoot(T,G,1-dir); // G may be the root
+    P->color = BLACK;
+    G->color = RED;
+    return; // insertion complete
+} // end of RBinsert1
+
+void vmt_delete(
+        struct vm_tree* T, // -> red–black tree
+        struct vm_tree_node* N)  // -> node to be deleted
+{
+    struct vm_tree_node* P = N->parent;  // -> parent node of N
+    enum vm_tree_direction dir; // side of P on which N is located (∈ { LEFT, RIGHT })
+    struct vm_tree_node* S;  // -> sibling of N
+    struct vm_tree_node* C;  // -> close   nephew
+    struct vm_tree_node* D;  // -> distant nephew
+
+    // P != NULL, since N is not the root.
+    dir = childDir(N); // side of parent P on which the node N is located
+    // Replace N at its parent P by NIL:
+    P->child[dir] = NIL;
+    goto Start_D;      // jump into the loop
+
+    // start of the (do while)-loop:
+    do {
+        dir = childDir(N);   // side of parent P on which node N is located
+Start_D:
+        S = P->child[1-dir]; // sibling of N (has black height >= 1)
+        D = S->child[1-dir]; // distant nephew
+        C = S->child[  dir]; // close   nephew
+        if (S->color == RED)
+            goto Case_D3;                  // S red ===> P+C+D black
+        // S is black:
+        if (D != NIL && D->color == RED) // not considered black
+            goto Case_D6;                  // D red && S black
+        if (C != NIL && C->color == RED) // not considered black
+            goto Case_D5;                  // C red && S+D black
+        // Here both nephews are == NIL (first iteration) or black (later).
+        if (P->color == RED)
+            goto Case_D4;                  // P red && C+S+D black
+        // Case_D1 (P+C+S+D black):
+        S->color = RED;
+        N = P; // new current node (maybe the root)
+        // iterate 1 black level
+        //   (= 1 tree level) higher
+    } while ((P = N->parent) != NULL);
+    // end of the (do while)-loop
+    // Case_D2 (P == NULL):
+    return; // deletion complete
+Case_D3: // S red && P+C+D black:
+    RotateDirRoot(T,P,dir); // P may be the root
+    P->color = RED;
+    S->color = BLACK;
+    S = C; // != NIL
+    // now: P red && S black
+    D = S->child[1-dir]; // distant nephew
+    if (D != NIL && D->color == RED)
+        goto Case_D6;      // D red && S black
+    C = S->child[  dir]; // close   nephew
+    if (C != NIL && C->color == RED)
+        goto Case_D5;      // C red && S+D black
+    // Otherwise C+D considered black.
+    // fall through to Case_D4
+    // Case_D4: // P red && S+C+D black:
+    S->color = RED;
+    P->color = BLACK;
+    return; // deletion complete
+Case_D4: // P red && S+C+D black:
+  S->color = RED;
+  P->color = BLACK;
+  return; // deletion complete
+Case_D5: // C red && S+D black:
+    RotateDir(S,1-dir); // S is never the root
+    S->color = RED;
+    C->color = BLACK;
+    D = S;
+    S = C;
+    // now: D red && S black
+    // fall through to Case_D6
+Case_D6: // D red && S black:
+    RotateDirRoot(T,P,dir); // P may be the root
+    S->color = P->color;
+    P->color = BLACK;
+    D->color = BLACK;
+    return; // deletion complete
+} // end of RBdelete2
+
+enum vm_tree_direction vmn_child_direction(
+        struct vm_tree_node *n,
+        struct vm_tree_node *p
+)
+{
+    if (p && compare_key(&p->key, &n->key) > 0)
+    {
+        return LEFT;
+    }
+    return RIGHT;
+}
+
+struct vm_tree_node *vmt_search_key(
+        struct vm_tree *tree,
+        struct vm_tree_key *key)
+{
+    struct vm_tree_node *N = tree->root;
+    
+    while (N && (compare_key(&N->key, key) != 0))
+    {
+        if (compare_key(&N->key, key) > 0)
+        {
+            N = N->left;
+        }
+        else
+        {
+            N = N->right;
+        }
+    }
+
+    return N;
+}
+
+// search for the predecessor node for a given key
+struct vm_tree_node *vmn_predecessor_key(
+        struct vm_tree_node *N,
+        struct vm_tree_key *key)
+{
+    struct vm_tree_node *P = NULL;
+
+    while (N && (compare_key(&N->key, key) != 0))
+    {
+        if (compare_key(&N->key, key) > 0)
+        {
+            N = N->left;
+        }
+        else
+        {
+            P = N;
+            N = N->right;
+        }
+    }
+
+    return P;
+}
+
+// search for the successor node for a given key
+struct vm_tree_node *vmn_successor_key(
+        struct vm_tree_node *N,
+        struct vm_tree_key *key)
+{
+    (void)N;
+    (void)key;
+    //TODO: write
+    return NULL;
+}
+
+struct vm_tree_node *vmn_min(struct vm_tree_node *node)
+{
+    while (node && node->left)
+    {
+        node = node->left;
+    }
+
+    return node;
+}
+
+struct vm_tree_node *vmn_max(struct vm_tree_node *node)
+{
+    while (node && node->right)
+    {
+        node = node->right;
+    }
+
+    return node;
+}
+
+void *vmt_get_object(struct vm_tree *tree, void *address)
+{
+    // find the object for a page.
+    struct vm_tree_key key = {(uintptr_t)address, 1};
+    struct vm_tree_node *node = vmt_search_key(tree, &key);
+    if (node)
+    {
+        return node->object;
+    }
+    return NULL;
+}
+
diff --git a/kc/core/vm_tree.h b/kc/core/vm_tree.h
new file mode 100644
index 0000000..dfceebf
--- /dev/null
+++ b/kc/core/vm_tree.h
@@ -0,0 +1,93 @@
+#pragma once
+
+// vm_tree.c
+//
+// AUTHOR NOTE:
+//
+// a great deal of this code is lifted and adapted straight from wikipedia at
+// https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
+//
+// i reserve no rights under copyright law to this material, but i agree to be
+// bound by the terms of the Creative Commons Share-Alike by Attribution license
+//
+// if any of the following is found to be in violation please contact the author
+// at ada.christine.18+sophia _at_ gmail _dot_ com
+//
+// -Ada Christine Fontaine, 1/1/2022
+//
+// LICENSE NOTIFICATION
+//
+// THE WORK (AS DEFINED BELOW) IS PROVIDED UNDER THE TERMS OF THIS CREATIVE
+// COMMONS PUBLIC LICENSE ("CCPL" OR "LICENSE"). THE WORK IS PROTECTED BY
+// COPYRIGHT AND/OR OTHER APPLICABLE LAW. ANY USE OF THE WORK OTHER THAN AS
+// AUTHORIZED UNDER THIS LICENSE OR COPYRIGHT LAW IS PROHIBITED.
+
+// BY EXERCISING ANY RIGHTS TO THE WORK PROVIDED HERE, YOU ACCEPT AND AGREE TO
+// BE BOUND BY THE TERMS OF THIS LICENSE. TO THE EXTENT THIS LICENSE MAY BE
+// CONSIDERED TO BE A CONTRACT, THE LICENSOR GRANTS YOU THE RIGHTS CONTAINED
+// HERE IN CONSIDERATION OF YOUR ACCEPTANCE OF SUCH TERMS AND CONDITIONS. 
+//
+// The full text of the CC-BY-SA 3.0 license can be found here:
+// https://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License
+
+enum vm_tree_direction
+{
+    LEFT,
+    RIGHT
+};
+
+enum vm_tree_color
+{
+    RED,
+    BLACK
+};
+
+
+struct vm_tree_key
+{
+    uintptr_t address;
+    size_t size;
+};
+
+struct vm_tree_node
+{
+    // red-black binary tree data
+    struct vm_tree_node *parent;
+    struct vm_tree_node *child[2];
+    enum vm_tree_color color;
+    struct vm_tree_key key;
+    // object that owns this node
+    void *object;
+};
+
+struct vm_tree
+{
+    struct vm_tree_node *root;
+};
+
+void vmt_insert(
+        struct vm_tree *,
+        struct vm_tree_node *,
+        struct vm_tree_node *,
+        enum vm_tree_direction);
+
+enum vm_tree_direction vmn_child_direction(
+        struct vm_tree_node *n,
+        struct vm_tree_node *p);
+
+void vmt_delete(struct vm_tree*, struct vm_tree_node*);
+
+struct vm_tree_node *vmt_search_key(struct vm_tree *, struct vm_tree_key *);
+
+struct vm_tree_node *vmn_predecessor_key(
+        struct vm_tree_node *,
+        struct vm_tree_key *);
+struct vm_tree_node *vmn_successor_key(
+        struct vm_tree_node *,
+        struct vm_tree_key *);
+
+struct vm_tree_node *vmn_min(struct vm_tree_node *node);
+struct vm_tree_node *vmn_max(struct vm_tree_node *node);
+
+void *vmt_get_object(struct vm_tree *, void *address);
+