Use uintptr_t, not intptr_t, for memory addresses!

[marionette.git] / kernel / mm / allocation.c

/*
 *    Copyright (c) 2008 Joshua Phillips. All rights reserved.
 *  
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are
 *  met:
 *  
 *    1. Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *    2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *  
 *  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
 *  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 *  DISCLAIMED. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
 *  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 *  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 *  GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 *  IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 *  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 *  IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "mm/allocation.h"
#include "mm/buddy.h"
#include "mm/paging.h" // for PAGE_TAB
#include "stdlib.h" // for malloc!
#include "trace.h"
#include "extlib.h"

// Boundaries of contiguous free memory.
// This is far from ideal.
static uintptr_t freemem_low_bound;
static uintptr_t freemem_high_bound;

// Physical buddy allocator
static struct buddy *physical_buddy = NULL;

// Kernel virtual page allocator + buddy
struct vpallocator kvpa;

// Base of physical memory that we're allocating
static uintptr_t phys_base;

void pmem_init_set_freemem_base(uintptr_t freemem_base)
{
    freemem_low_bound = alignup(freemem_base, PAGE_SIZE);
}

void pmem_init_mark_free(uintptr_t region_start, uintptr_t region_end)
{
    // Don't use non-contiguous parts of memory. This might throw away
    // large chunks of physical memory that we'll never use!
    // It's easier this way for now. At least print a warning if any
    // gets wasted.
    if (region_start <= freemem_low_bound){
        freemem_high_bound = region_end;
    } else {
        TRACE("Throwing away %d MiB of memory!",
          uldivru(region_end - region_start, 1024 * 1024));
    }
}

size_t pmem_get_size(void)
{
    return freemem_high_bound - freemem_low_bound;
}

void mm_allocation_init(void)
{
    size_t n_chunks;
    int height;
    size_t struct_size, old_struct_size;
    uintptr_t new_freemem_low_bound;

    // create the virtual buddy allocator (for kernel address space)

    n_chunks = (0 - KERNEL_VIRT_BASE) / PAGE_SIZE;
    
    // calculate the size the buddy structures will take
    get_buddy_size(n_chunks, &height, &struct_size);
    TRACE("Buddy data for kernel's virtual addr space: %u kiB",
      uldivru(struct_size, 1024));
    // TODO: make sure struct_size doesn't exceed the amount of memory mapped
    // after the kernel image at 0xC0000000

    // Here, we can convert a physical address to a virtual address just by
    // adding. This only works during bootstrapping, due to the simple page
    // mapping!
    kvpa.buddy = (struct buddy *) ((freemem_low_bound - KERNEL_PHYS_BASE) + KERNEL_VIRT_BASE);

    // initialize the buddy structure
    buddy_init(kvpa.buddy, n_chunks, height, struct_size);
    kvpa.base = KERNEL_VIRT_BASE;

    // Now that we've set up the virtual buddy structure, there's
    // even less free memory.
    struct_size = alignup(struct_size, PAGE_SIZE);
    new_freemem_low_bound = freemem_low_bound + struct_size;

    // Create the physical buddy, to manage all normal physical memory,
    // with a granularity of one page.

    old_struct_size = 0;
    for (;;){
        // how many pages (allocator 'chunks') do we need to manage?
        n_chunks = ((freemem_high_bound - new_freemem_low_bound) 
          - alignup(old_struct_size, PAGE_SIZE)) / PAGE_SIZE;
        // calculate amount of data needed for buddy allocator
        get_buddy_size(n_chunks, &height, &struct_size);
        if (struct_size != old_struct_size){
            // We don't need to manage the memory management data,
            // so we'll calculate the size again, and again, until
            // we settle on an optimum size. This only actually takes
            // about two iterations. There could also be a more
            // linear calculation? :)
            old_struct_size = struct_size;
        } else {
            // the struct_size hasn't changed. Stop iterating.
            break;
        }
    }

    TRACE("Buddy data for %u MiB physical addr space: %u kiB",
      uldivru(freemem_high_bound - freemem_low_bound, 1024 * 1024),
      uldivru(struct_size, 1024));
    // TODO: make sure struct_size doesn't exceed the amount of memory mapped
    // after the kernel image at 0xC0000000
    physical_buddy = (struct buddy *) ((new_freemem_low_bound - KERNEL_PHYS_BASE) 
      + KERNEL_VIRT_BASE);
    phys_base = new_freemem_low_bound + alignup(struct_size, PAGE_SIZE);
    buddy_init(physical_buddy, n_chunks, height, struct_size);
    TRACE("Buddy allocators initialized.");

    // Mark the kernel as used kernel virtual address space (because it is)
    buddy_mark_used(kvpa.buddy, 0, uldivru(phys_base - KERNEL_PHYS_BASE, PAGE_SIZE));
}

size_t ppalloc(size_t min_pages, size_t max_pages, uintptr_t *start_addr)
{
    unsigned int result;
    size_t allocated_pages;
    result = buddy_alloc(physical_buddy, min_pages, max_pages, &allocated_pages);
    if (result == -1){
        return 0;
    } else {
        *start_addr = phys_base + (result * PAGE_SIZE);
        return allocated_pages;
    }
}

void ppfree(uintptr_t start_addr, size_t n_pages)
{
    buddy_free(physical_buddy, (start_addr - phys_base) / PAGE_SIZE, n_pages);
}

int vpcreate(struct vpallocator *restrict vp, uintptr_t base, size_t extent)
{
    int height;
    size_t struct_size;
    size_t n_chunks;

    vp->base = base & ~(PAGE_SIZE - 1);
    
    // calculate the size the buddy structure will take
    get_buddy_size(extent, &height, &struct_size);

    // allocate the buddy structure, using malloc
    // since we're using malloc, we can't use vpcreate
    // for the kernel virtual address space ^_^
    vp->buddy = malloc(struct_size);
    if (!vp->buddy){
        TRACE("memory full (struct_size = %d)", struct_size);
        return 1;
    }

    // initialize the buddy structure
    buddy_init(vp->buddy, n_chunks, height, struct_size);

    // thank you, caller. Enjoy your allocator!
    return 0;
}

size_t vpalloc(struct vpallocator *restrict vp, size_t min_pages, size_t max_pages, uintptr_t *start_addr)
{
    unsigned int result;
    size_t allocated_pages;
    result = buddy_alloc(vp->buddy, min_pages, max_pages, &allocated_pages);
    if (result == -1){
        return 0;
    } else {
        *start_addr = vp->base + (result * PAGE_SIZE);
        return allocated_pages;
    }
}

void vpfree(struct vpallocator *restrict vp, uintptr_t start_addr, size_t n_pages)
{
    buddy_free(vp->buddy, (start_addr - vp->base) / PAGE_SIZE, n_pages);
}