many changes

- boot time memory allocation has changed. the fractal page map has been
  replaced by a single self-mapped page giving 2MiB of ready virtual
  space to play with without needing a fully-initialized memory manager. this
  scheme may be repeated for other purposes
- the page stack has now been totally overhauled to make use of sparse
  allocation and all of the ugly init_*() procedures are gone. long live
  the new interface. also reference counting is a thing now. sort of.
- found a bug in vmt_init_node where insertion did not use the root node as
  the parent in the case of no predecessor node. whoops.

5 files changed, 964 insertions, 0 deletions

diff --git a/kc/core/memory/memory.c b/kc/core/memory/memory.c
new file mode 100644
index 0000000..1a33629
--- /dev/null
+++ b/kc/core/memory/memory.c
@@ -0,0 +1,628 @@
+/* kernel virtual space guarantees
+ * the loader must set up the address space as follows
+ * 1. kernel virtual space is 2GiB in size on 2GiB alignment.
+ * 2. the very top of address space must have a single self-mapped
+ *    that manages the top 2MiB of space.
+ * 3. that top 2MiB of space contains a bump-allocated buffer of some size
+ *    recorded in the boot data structures
+ */
+
+#include "page_early.h"
+#include "page_stack.h"
+
+#include "memory.h"
+#include "kprint.h"
+#include "panic.h"
+#include "vm_object.h"
+#include "cpu/mmu.h"
+
+#include <stdint.h>
+
+#include <kc.h>
+#include <core/memory.h>
+
+#define align_next(x, a) (x + a - 1) & ~(a - 1)
+
+static void *temp_page_map(kc_phys_addr paddr, enum page_map_flags flags);
+static void temp_page_unmap(void *address);
+
+static void *page_map_at(
+        void *vaddr,
+        phys_addr_t paddr,
+        enum page_map_flags flags);
+
+enum vm_core_state_items
+{
+    KERNEL_VM_STATE,
+    HEAP_VM_STATE,
+    STACK_VM_STATE,
+    TEMPS_VM_STATE
+};
+
+struct vm_core_static_state
+{
+    struct vm_tree_node node;
+    struct vm_object *object;
+};
+
+static struct vm_core_state
+{
+    struct vm_tree tree;
+    struct vm_object global_null;
+    struct vm_object global_anonymous;
+    struct vm_object global_direct;
+    struct vm_object global_translate;
+    struct vm_core_static_state statics[4];
+    kc_phys_addr zero_page;
+    void *first_free;
+} vm_state = {
+    {0},
+    {NULL_VM_OBJECT, NULL},
+    {ANONYMOUS_VM_OBJECT, anonymous_page_handler},
+    {DIRECT_VM_OBJECT, NULL},
+    {TRANSLATION_VM_OBJECT, NULL},
+    {
+        {{0}, &vm_state.global_null},
+        {{0}, &vm_state.global_anonymous},
+        {{0}, &vm_state.global_anonymous},
+        {{0}, &vm_state.global_null},
+    },
+    0,
+    NULL
+};
+
+static struct vm_temp_state
+{
+    uint64_t *table;
+    int first_free;
+}
+temp_state;
+
+struct vm_tree *vm_get_tree(void)
+{
+    return &vm_state.tree;
+}
+
+void page_init(void)
+{
+    kprintf("initializing page frame allocator\n");
+    page_early_init();
+    page_stack_init();
+}
+
+void page_init_final(void)
+{
+    kprintf("finishing page frame allocator initialization\n");
+    page_early_final();
+}
+
+
+void page_set_present(kc_phys_addr page)
+{
+    page_stack_set_present(page);
+}
+
+int page_get_present(kc_phys_addr page)
+{
+    return page_stack_get_present(page);
+}
+
+void page_set_allocated(kc_phys_addr page)
+{
+    page_stack_set_allocated(page);
+}
+
+void page_set_free(kc_phys_addr page)
+{
+    page_stack_set_free(page);
+}
+
+kc_phys_addr page_alloc(enum page_alloc_flags type)
+{
+    kc_phys_addr paddr = 0;
+    if ((paddr = page_stack_alloc(type)) > 0)
+    {
+        return paddr;
+    }
+    else
+    {
+        return page_early_alloc(type);
+    }
+}
+
+void page_free(kc_phys_addr page)
+{
+    page_stack_free(page);
+}
+
+static void *map_tableset(void *vaddr, uint64_t *tables[4])
+{
+    uint64_t current_phys;
+    uint64_t *current_pte;
+    // pml4 is guaranteed to be present. no checks necessary.
+    //
+
+    current_phys = page_address(mmu_get_map(), 1);
+    tables[3] = temp_page_map(current_phys, CONTENT_RWDATA);
+    int n = 3;
+
+    while (n)
+    {
+        if (tables[n])
+        {
+            current_pte = &tables[n][pte_index(vaddr, n+1)];
+
+            if (!page_address(*current_pte, 1))
+            {
+                current_phys = page_alloc(PAGE_ALLOC_CONV);
+                if (current_phys)
+                {
+                    tables[n-1] = temp_page_map(current_phys, CONTENT_RWDATA);
+                    memset(tables[n-1], 0, page_size(1));
+                    *current_pte = current_phys |= PAGE_NX|PAGE_WR|PAGE_PR;
+                }
+                else
+                {
+                    kprintf("error: failed allocating memory for page table\n");
+                    PANIC(OUT_OF_MEMORY);
+                }
+            }
+            else
+            {
+                current_phys = page_address(*current_pte, 1);
+                tables[n-1] = temp_page_map(current_phys, CONTENT_RWDATA);
+            }
+        }
+        n--;
+    }
+
+    if (tables[0])
+    {
+        current_pte = &tables[0][pte_index(vaddr, 1)];
+    }
+
+    return vaddr;
+}
+
+static void *page_map_at(
+        void *vaddr,
+        phys_addr_t paddr,
+        enum page_map_flags flags)
+{
+    // TODO: add checks to prevent attempts to map reserved addreses
+    //
+    uint64_t *mapset[4] = {NULL};
+
+    if (vaddr != map_tableset(vaddr, mapset))
+    {
+        PANIC(GENERAL_PANIC);
+    }
+
+    uint64_t entry = PAGE_PR;
+
+    switch (flags & CONTENT_MASK)
+    {
+        case CONTENT_RODATA:
+            entry |= PAGE_NX;
+            break;
+        case CONTENT_RWDATA:
+            entry |= PAGE_NX|PAGE_WR;
+            break;
+        default:
+            break;
+    }
+
+    size_t offset;
+
+    switch (flags & SIZE_MASK)
+    {
+        case SIZE_1G:
+            offset = page_offset(paddr, 3);
+            break;
+        case SIZE_2M:
+            offset = page_offset(paddr, 2);
+            break;
+        case 0:
+        case SIZE_4K:
+            offset = page_offset(paddr, 1);
+            break;
+        default:
+            vaddr = NULL;
+    }
+    if (vaddr)
+    {
+        mapset[0][pte_index(vaddr, 1)] = page_address(paddr, 1) | entry;
+    }
+
+    for (int i = 0; i < 4; i++)
+    {
+        if (mapset[i])
+        {
+            temp_page_unmap(mapset[i]);
+        }
+    }
+
+    return (char *)vaddr + offset;
+}
+
+#define VM_HEAP_SIZE 16 * page_size(2)
+
+static void *temp_page_alloc(void)
+{
+    int index = temp_state.first_free;
+
+    // do not allocate the 511th index!!
+    if (index > -1 && index < 511)
+    {
+        temp_state.first_free = temp_state.table[index] >> 1;
+        temp_state.table[index] = 0;
+    }
+    else
+    {
+        return NULL;
+    }
+
+    return (void *)-((512ULL - index) << 12);
+}
+
+static void temp_page_free(void *address)
+{
+    int index = pte_index(address, 1);
+
+    if (index > -1 && index < 511)
+    {
+        temp_state.table[index] = temp_state.first_free << 1;
+        temp_state.first_free = index;
+    }
+}
+
+static void *temp_page_map(kc_phys_addr paddr, enum page_map_flags flags)
+{
+    uint64_t entry = PAGE_PR;
+    size_t offset = 0;
+
+    switch (flags & SIZE_MASK)
+    {
+        case 0:
+        case SIZE_4K:
+            offset = page_offset(paddr, 1);
+            break;
+        default:
+            return NULL;
+    }
+
+    switch (flags & CONTENT_MASK)
+    {
+        case CONTENT_RODATA:
+            entry |= PAGE_NX;
+            break;
+        case CONTENT_RWDATA:
+            entry |= PAGE_NX|PAGE_WR;
+            break;
+        default:
+            break;
+    }
+
+    unsigned char *vaddr = temp_page_alloc();
+
+    if (vaddr)
+    {
+        vaddr += offset;
+        temp_state.table[pte_index(vaddr, 1)] = page_address(paddr, 1) | entry;
+    }
+
+    return vaddr;
+}
+
+static void temp_page_unmap(void *vaddr)
+{
+    temp_page_free(vaddr);
+    mmu_invalidate(vaddr);
+}
+
+static void vm_init(void)
+{
+    kprintf("initializing vm state\n");
+    struct kc_boot_data *boot_data = get_boot_data();
+    struct vm_core_static_state *states = &vm_state.statics[0];
+
+    // initialize the static vm node entries
+    struct
+    {
+        unsigned char *base;
+        unsigned char *head;
+    } vm_ranges[] = {
+        {&kc_image_base, &kc_image_end},
+        {&kc_image_end, &kc_image_end + VM_HEAP_SIZE},
+        {
+            boot_data->buffer.base - page_size(1) * 2,
+            boot_data->buffer.base - page_size(1)
+        },
+        {
+            boot_data->buffer.current,
+            boot_data->buffer.current + boot_data->buffer.max_size,
+        }
+    };
+
+    vm_state.first_free = &kc_image_end;
+
+    for (int i = 0; i <= TEMPS_VM_STATE; i++)
+    {
+        vmt_init_node
+            (
+             vm_get_tree(),
+             &states[i].node,
+             states[i].object,
+             (void *)vm_ranges[i].base,
+             (void *)vm_ranges[i].head
+            );
+    }
+
+    // init the temporary mappings table state
+    temp_state.table = (uint64_t *)-page_size(1);
+    temp_state.first_free = -1;
+    for (int index = 0; index < 512; index++)
+    {
+        // i love these array-based linked list stacks
+        if (!(temp_state.table[index] & PAGE_PR))
+        {
+            temp_page_free((void *)-((512ULL - index) << 12));
+        }
+    }
+
+    page_init();
+
+    vm_state.zero_page = page_alloc(PAGE_ALLOC_CONV);
+    if (!vm_state.zero_page)
+    {
+        kprintf("failed allocating for zero page\n");
+        PANIC(GENERAL_PANIC);
+    }
+
+    void *zero_temp = temp_page_map(vm_state.zero_page, CONTENT_RWDATA);
+
+    if (!zero_temp)
+    {
+        kprintf("failed mapping zero page for initialization\n");
+        PANIC(GENERAL_PANIC);
+    }
+
+    // make the zero page live up to its name;
+    memset(zero_temp, 0, page_size(1));
+    temp_page_unmap(zero_temp);
+
+    page_init_final();
+}
+
+void memory_init(void)
+{
+    vm_init();
+}
+
+void *page_map(phys_addr_t page, enum page_map_flags flags)
+{
+    void *vm_page = vm_alloc(4096, VM_ALLOC_TRANSLATE);
+    if (vm_page)
+    {
+        page_map_at(vm_page, page, flags);
+    }
+    return NULL;
+}
+
+void page_unmap(void *vaddr)
+{
+    (void)vaddr;
+}
+
+struct heap_header
+{
+    size_t size;
+    struct heap_header *next;
+};
+
+static struct heap_header *heap_root = (void *)-1ULL;
+
+void *heap_alloc(size_t size)
+{
+    // simple first-fit allocator, allocates downward from the head
+    // of the first block of sufficient size
+    // TODO: join heap blocks if there is not one of sufficient size
+    void *block = NULL;
+    struct heap_header *header;
+
+    // first attempt at allocation
+    if ((void *)-1ULL == heap_root)
+    {
+        struct vm_tree_node *heap_node = &vm_state.statics[HEAP_VM_STATE].node;
+        kprintf("initializing heap at %#lx of %zu bytes\n",
+                heap_node->key.address, heap_node->key.size);
+        heap_root = NULL;
+        header = (struct heap_header *)heap_node->key.address;
+        header->size = heap_node->key.size - sizeof(header->size);
+        heap_free((char *)header + sizeof(*header));
+    }
+    else
+    {
+        header = heap_root;
+    }
+    size = align_next(size, sizeof(*header));
+
+    while (header)
+    {
+        if (header->size > size)
+        {
+            break;
+        }
+        header = header->next;
+    }
+
+    if (header)
+    {
+        header->size -= size + sizeof(*header);
+        header = (struct heap_header *)((char *)header + header->size);
+        header->size = size;
+        header->next = NULL;
+        block = (char *)header + sizeof(*header);
+    }
+
+    return block;
+}
+
+void heap_free(void *block)
+{
+    struct heap_header *header = (void *)
+        ((char *)block - sizeof(*header));
+
+    header->next = heap_root;
+    heap_root = header;
+}
+
+void *memory_alloc(size_t size)
+{
+    // allocations larger than page-size should just get an anonymous vm_object
+    if (size < 4096)
+    {
+        return heap_alloc(size);
+    }
+    else
+    {
+        return vm_alloc(size, VM_ALLOC_ANY|VM_ALLOC_ANONYMOUS);
+    }
+}
+
+void memory_free(void *block)
+{
+    // a little complicated to implement
+    //
+    // 1. find the vm_object that owns the block
+    //   a. if the vm_object is a heap, call heap_free()
+    //   b. if the vm_object is an anonymous vm_area, call vm_free().
+    //   c. if the object is any other kind issue a bug warning and do nothing
+    (void)block;
+}
+
+void *vm_alloc_at(void *address, size_t size, enum vm_alloc_flags flags)
+{
+    struct vm_tree_key key = {(uintptr_t)address, size};
+    struct vm_tree_node *node;
+    struct vm_object *object;
+
+    switch (flags & VM_ALLOC_MECHANISM_MASK)
+    {
+        case VM_ALLOC_ANONYMOUS:
+            object = &vm_state.global_anonymous;
+            break;
+        case VM_ALLOC_DIRECT:
+            object = &vm_state.global_direct;
+            break;
+        case VM_ALLOC_TRANSLATE:
+            object = &vm_state.global_translate;
+            break;
+        default:
+            return NULL;
+    }
+
+    if (!vmt_search_key(vm_get_tree(), &key) &&
+            (node = heap_alloc(sizeof(*node))))
+    {
+        vmt_init_node(
+                vm_get_tree(),
+                node,
+                object,
+                address,
+                (void *)((char *)address + size));
+    }
+    
+    return address;
+}
+
+void *vm_alloc(size_t size, enum vm_alloc_flags flags)
+{
+    (void)flags;
+    // TODO implement a proper allocator here rather than this bump allocator.
+    char *address = vm_state.first_free;
+
+    if (address == vm_alloc_at(address, size, flags))
+    {
+        vm_state.first_free = address + size;
+        return address;
+    }
+
+    return NULL;
+}
+
+int anonymous_page_handler(
+        struct vm_tree_node *node,
+        uint32_t code,
+        void *address)
+{
+    (void)node;
+
+    if (!(code & 1))
+    {
+        // map the zero page read-only to the address
+        page_map_at(
+                address,
+                vm_state.zero_page,
+                CONTENT_RODATA|SIZE_4K);
+    }
+
+    if ((code & 1) && (code & 2)) // page fault write violation on present page
+    {
+        mmu_invalidate(address);
+        kc_phys_addr paddr = page_alloc(PAGE_ALLOC_CONV);
+
+        if (!paddr)
+        {
+            kprintf("got zero from page_alloc :|\n");
+            PANIC(OUT_OF_MEMORY);
+        }
+        page_map_at(
+                address,
+                page_alloc(PAGE_ALLOC_CONV),
+                CONTENT_RWDATA|SIZE_4K);
+        // NULL out the whole page
+        // TODO: thread to clean dirty pages.
+        memset((void *)page_address(address, 1), 0, page_size(1));
+    }
+
+    return 0;
+}
+
+int page_fault_handler(uint8_t vector, uint32_t code)
+{
+    (void)vector;
+
+    void *address;
+    __asm__ volatile ("movq %%cr2, %0" : "=r"(address));
+
+    struct vm_tree_key key = {(uintptr_t)address, sizeof(uint64_t)};
+    struct vm_tree_node *node = vmt_search_key(vm_get_tree(), &key);
+
+    if (!node)
+    {
+        kprintf("error: page fault in unmanaged address %#lx\n",
+                address);
+        PANIC(UNHANDLED_FAULT);
+    }
+
+    if (!node->object->handler)
+    {
+        kprintf("error: vm object at %p has no fault handler\n");
+        PANIC(UNHANDLED_FAULT);
+    }
+
+    return node->object->handler(node, code, address);
+}
+
+int general_protection_handler(uint8_t vector, uint32_t code)
+{
+    //TODO: implement #gp handler
+    (void)vector;
+    (void)code;
+
+    kputs("general protection violation\n");
+    PANIC(UNHANDLED_FAULT);
+    return 0;
+}
+
diff --git a/kc/core/memory/page_early.c b/kc/core/memory/page_early.c
new file mode 100644
index 0000000..7f1d0eb
--- /dev/null
+++ b/kc/core/memory/page_early.c
@@ -0,0 +1,95 @@
+#include "page_early.h"
+#include "kprint.h"
+#include "panic.h"
+
+static struct page_early_state
+{
+    struct memory_range *first;
+    struct memory_range *current;
+    struct memory_range *last;
+}
+early_state;
+
+void page_early_init(void)
+{
+    kprintf("initializing early page frame allocator\n");
+    struct kc_boot_data *boot_data = get_boot_data();
+
+    early_state.first = &boot_data->memory.entries[0];
+    early_state.last = &boot_data->memory.entries[boot_data->memory.count];
+    early_state.current = early_state.first;
+}
+
+void page_early_final(void)
+{
+    if (early_state.first)
+    {
+        kprintf("finalizing early page allocator\n");
+        for (struct memory_range *current = early_state.first; 
+                current < early_state.last;
+                current++)
+        {
+            while (current->size >= page_size(1))
+            {
+                current->size -= page_size(1);
+
+                enum memory_range_type type = current->type;
+                kc_phys_addr page = current->base + current->size;
+                // all pages are gonna be set allocated first
+                // to initialize the tracking structure at the other side
+                // and make setting the page free as simple as 
+                // calling page_free();
+                page_set_allocated(page);
+
+                switch (type)
+                {
+                    case RESERVED_MEMORY:
+                    case SYSTEM_MEMORY:
+                        page_set_present(page);
+                        break;
+                    case AVAILABLE_MEMORY:
+                        page_set_present(page);
+                        page_free(page);
+                        break;
+                    case FIRMWARE_MEMORY:
+                    case MMIO_MEMORY:
+                        break;
+                    default:
+                        break;
+                }
+            }
+        }
+
+        early_state = (struct page_early_state){NULL, NULL, NULL};
+    }
+}
+
+kc_phys_addr page_early_alloc(enum page_alloc_flags type)
+{
+    // TODO: support low/conv/high allocations in early_alloc.
+    // currently we only have conventional allocations enforced
+    // by the conditions of the scanning loop
+    (void)type;
+
+    while(early_state.current)
+    {
+        if ((early_state.current->type == AVAILABLE_MEMORY) &&
+                (early_state.current->base > 0x10000) &&
+            (early_state.current->size > page_size(1)))
+        {
+            early_state.current->size -= page_size(1);
+            return early_state.current->base + early_state.current->size;
+        }
+
+        if (early_state.current == early_state.last)
+        {
+            early_state.current = NULL;
+            break;
+        }
+        early_state.current++;
+    }
+
+    kprintf("error: early allocator has run out of memory\n");
+    PANIC(OUT_OF_MEMORY);
+}
+
diff --git a/kc/core/memory/page_early.h b/kc/core/memory/page_early.h
new file mode 100644
index 0000000..3cd5b4e
--- /dev/null
+++ b/kc/core/memory/page_early.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include "memory.h"
+
+void page_early_init(void);
+void page_early_final(void);
+kc_phys_addr page_early_alloc(enum page_alloc_flags type);
+
diff --git a/kc/core/memory/page_stack.c b/kc/core/memory/page_stack.c
new file mode 100644
index 0000000..92c5cff
--- /dev/null
+++ b/kc/core/memory/page_stack.c
@@ -0,0 +1,215 @@
+#include "page_stack.h"
+#include "vm_tree.h"
+#include "vm_object.h"
+
+#include <kc.h>
+
+#define PAGE_STACK_CACHE_SIZE (1ULL << 32)
+#define page_stack_index(x) (x / page_size(1))
+#define page_stack_address(x) (x * page_size(1))
+
+struct page
+{
+    uint32_t present: 1; // a physical page is at this location
+    uint32_t allocated: 1; // this physical page has been taken
+    int32_t next_refs; // allocated = 0: the index of the next page in the list
+                       // allocated = 1: the number of references this page has
+};
+
+static struct page_stack_state
+{
+    struct vm_tree_node node;
+    struct vm_object object;
+    struct page *stack;
+    int32_t free_count[3];
+    int32_t total_count[3];
+    int32_t first_free[3];
+}
+stack_state = {
+    {0},
+    {ANONYMOUS_VM_OBJECT, anonymous_page_handler},
+    NULL,
+    {0,0,0},
+    {0,0,0},
+    {-1,-1,-1}
+};
+
+static enum page_alloc_flags stack_type(kc_phys_addr page);
+static void stack_push(kc_phys_addr page);
+static kc_phys_addr stack_pop(enum page_alloc_flags type);
+
+void page_stack_init(void)
+{   
+    vmt_init_node(
+            vm_get_tree(),
+            &stack_state.node,
+            &stack_state.object,
+            &kc_image_base - PAGE_STACK_CACHE_SIZE,
+            &kc_image_base);
+
+    stack_state.stack = (struct page *)stack_state.node.key.address;
+}
+
+kc_phys_addr page_stack_alloc(enum page_alloc_flags type)
+{
+    kc_phys_addr page = stack_pop(type);
+    if (page)
+    {
+        page_stack_inc_ref(page);
+    }
+    return page;
+}
+
+void page_stack_free(kc_phys_addr page)
+{
+    // immediately release a reference
+    int referents = page_stack_dec_ref(page);
+
+    // freeing a page only makes sense for present physical pages
+    if (!page_stack_get_present(page))
+    {
+        return;
+    }
+
+    // only actually free the page if it has no more references
+    if (referents == 0)
+    {
+        page_stack_set_free(page);
+        stack_push(page);
+    }
+}
+
+int page_stack_get_present(kc_phys_addr page)
+{
+    unsigned index = page_stack_index(page);
+    return stack_state.stack[index].present;
+}
+
+void page_stack_set_present(kc_phys_addr page)
+{
+    unsigned index = page_stack_index(page);
+    stack_state.stack[index].present = 1;
+}
+
+void page_stack_set_allocated(kc_phys_addr page)
+{
+    unsigned index = page_stack_index(page);
+    stack_state.stack[index].allocated = 1;
+    stack_state.stack[index].next_refs = 1;
+}
+
+void page_stack_set_free(kc_phys_addr page)
+{
+    unsigned index = page_stack_index(page);
+    stack_state.stack[index].allocated = 0;
+    stack_state.stack[index].next_refs = -1;
+}
+
+int page_stack_inc_ref(kc_phys_addr page)
+{
+    unsigned index = page_stack_index(page);
+    // taking a reference only makes sense for an allocated page
+    if (stack_state.stack[index].allocated)
+    {
+        return ++stack_state.stack[index].next_refs;
+    }
+
+    return -1;
+}
+
+int page_stack_dec_ref(kc_phys_addr page)
+{   
+    unsigned index = page_stack_index(page);
+    // releasing a reference only makes sense for an allocated page
+    if (stack_state.stack[index].allocated)
+    {
+        // releasing a reference only makes sense if the refcount is > 0
+        if (stack_state.stack[index].next_refs > 0)
+        {
+            stack_state.stack[index].next_refs--;
+        }
+        return stack_state.stack[index].next_refs;
+    }
+
+    return -1;
+}
+
+static enum page_alloc_flags stack_type(kc_phys_addr page)
+{
+    // the page stack type only makes sense for physical pages
+    if (!page_stack_get_present(page))
+    {
+        return PAGE_ALLOC_NONE;
+    }
+
+    // pages above 4GiB physical are high memory
+    if (page > -1U)
+    {
+        return PAGE_ALLOC_HIGH;
+    }
+
+    // pages below 1MiB are low memory
+    else if (page < 0x100000)
+    {
+        return PAGE_ALLOC_LOW;
+    }
+    
+    // all other pages are conventional memory
+    return PAGE_ALLOC_CONV;
+}
+
+static void stack_push(kc_phys_addr page)
+{
+    enum page_alloc_flags type = stack_type(page);
+
+    // stack push only makes sense for pages in a physical stack
+    if ((type < PAGE_ALLOC_LOW) || type > PAGE_ALLOC_HIGH)
+    {
+        return;
+    }
+
+    unsigned index = page_stack_index(page);
+    stack_state.stack[index].next_refs = stack_state.first_free[type - 1];
+    stack_state.first_free[type - 1] = index;
+    stack_state.free_count[type - 1]++;
+}
+
+static kc_phys_addr stack_pop(enum page_alloc_flags type)
+{   
+    int pop_stack_index = -1;
+    int pop_stack_last = -1;
+
+    // pops only make sense for pages with a stack type
+    if ((type < PAGE_ALLOC_LOW) || (type > PAGE_ALLOC_HIGH))
+    {
+        return 0;
+    }
+
+    // do allocations in a high-to-low order if we're allocating any
+    if (type == PAGE_ALLOC_ANY)
+    {
+        pop_stack_index = PAGE_ALLOC_HIGH;
+        pop_stack_last = PAGE_ALLOC_LOW;
+    }
+    else
+    {
+        pop_stack_index = type;
+        pop_stack_last = type;
+    }
+
+    for (; pop_stack_last <= pop_stack_index; --pop_stack_index)
+    {
+        if (stack_state.first_free[pop_stack_index - 1] > 0)
+        {
+            unsigned index = stack_state.first_free[pop_stack_index-1];
+            stack_state.first_free[pop_stack_index-1] = 
+                stack_state.stack[index].next_refs;
+            page_stack_set_allocated(page_stack_address(index));
+            stack_state.free_count[pop_stack_index - 1]--;
+            return page_stack_address(index);
+        }
+    }
+
+    return 0;
+}
+
diff --git a/kc/core/memory/page_stack.h b/kc/core/memory/page_stack.h
new file mode 100644
index 0000000..92d7222
--- /dev/null
+++ b/kc/core/memory/page_stack.h
@@ -0,0 +1,18 @@
+#pragma once
+
+#include "memory.h"
+
+void page_stack_init(void);
+
+kc_phys_addr page_stack_alloc(enum page_alloc_flags type);
+void page_stack_free(kc_phys_addr page);
+
+int page_stack_get_present(kc_phys_addr page);
+void page_stack_set_present(kc_phys_addr page);
+
+void page_stack_set_allocated(kc_phys_addr page);
+void page_stack_set_free(kc_phys_addr page);
+
+int page_stack_inc_ref(kc_phys_addr page);
+int page_stack_dec_ref(kc_phys_addr page);
+