diff options
Diffstat (limited to 'kc')
| -rw-r--r-- | kc/core/Makefile | 2 | ||||
| -rw-r--r-- | kc/core/memory.c | 367 | ||||
| -rw-r--r-- | kc/core/vm_tree.c | 332 | ||||
| -rw-r--r-- | kc/core/vm_tree.h | 93 |
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); + |