diff options
Diffstat (limited to 'kernel/kmem.c')
| -rw-r--r-- | kernel/kmem.c | 691 |
1 files changed, 0 insertions, 691 deletions
diff --git a/kernel/kmem.c b/kernel/kmem.c deleted file mode 100644 index fe0c7de..0000000 --- a/kernel/kmem.c +++ /dev/null @@ -1,691 +0,0 @@ -/** -** @file kmem.c -** -** @author Warren R. Carithers -** @author Kenneth Reek -** @author 4003-506 class of 20013 -** -** @brief Functions to perform dynamic memory allocation in the OS. -** -** NOTE: these should NOT be called by user processes! -** -** This allocator functions as a simple "slab" allocator; it allows -** allocation of either 4096-byte ("page") or 1024-byte ("slice") -** chunks of memory from the free pool. The free pool is initialized -** using the memory map provided by the BIOS during the boot sequence, -** and contains a series of blocks which are each one page of memory -** (4KB, and aligned at 4KB boundaries); they are held in the free list -** in LIFO order, as all pages are created equal. -** -** By default, the addresses used are virtual addresses rather than -** physical addresses. Define the symbol USE_PADDRS when compiling to -** change this. -** -** Each allocator ("page" and "slice") allocates the first block from -** the appropriate free list. On deallocation, the block is added back -** to the free list. -** -** The "slice" allocator operates by taking blocks from the "page" -** allocator and splitting them into four 1K slices, which it then -** manages. Requests are made for slices one at a time. If the free -** list contains an available slice, it is unlinked and returned; -** otherwise, a page is requested from the page allocator, split into -** slices, and the slices are added to the free list, after which the -** first one is returned. The slice free list is a simple linked list -** of these 1K blocks; because they are all the same size, no ordering -** is done on the free list, and no coalescing is performed. -** -** This could be converted into a bitmap-based allocator pretty easily. -** A 4GB address space contains 2^20 (1,048,576) pages; at one bit per -** page frame, that's 131,072 (2^17) bytes to cover all of the address -** space, and that could be reduced by restricting allocatable space -** to a subset of the 4GB space. -** -** Compilation options: -** -** ALLOC_FAIL_PANIC if an internal slice allocation fails, panic -** USE_PADDRS build the free list using physical, not -** virtual, addresses -*/ - -#define KERNEL_SRC - -#include <common.h> - -// all other framework includes are next -#include <lib.h> - -#include <kmem.h> - -#include <list.h> -#include <x86/arch.h> -#include <x86/bios.h> -#include <bootstrap.h> -#include <cio.h> -#include <vm.h> - -/* -** PRIVATE DEFINITIONS -*/ - -// combination tracing tests -#define ANY_KMEM (TRACING_KMEM | TRACING_KMEM_INIT | TRACING_KMEM_FREELIST) -#define KMEM_OR_INIT (TRACING_KMEM | TRACING_KMEM_INIT) - -// parameters related to word and block sizes - -#define WORD_SIZE sizeof(int) -#define LOG2_OF_WORD_SIZE 2 - -#define LOG2_OF_PAGE_SIZE 12 - -#define LOG2_OF_SLICE_SIZE 10 - -// converters: pages to bytes, bytes to pages - -#define P2B(x) ((x) << LOG2_OF_PAGE_SIZE) -#define B2P(x) ((x) >> LOG2_OF_PAGE_SIZE) - -/* -** Name: adjacent -** -** Arguments: addresses of two blocks -** -** Description: Determines whether the second block immediately -** follows the first one. -*/ -#define adjacent(first, second) \ - ((void *)(first) + P2B((first)->pages) == (void *)(second)) - -/* -** PRIVATE DATA TYPES -*/ - -/* -** Memory region information returned by the BIOS -** -** This data consists of a 32-bit integer followed -** by an array of region descriptor structures. -*/ - -// a handy union for playing with 64-bit addresses -typedef union b64_u { - uint32_t part[2]; - uint64_t all; -} b64_t; - -// the halves of a 64-bit address -#define LOW part[0] -#define HIGH part[1] - -// memory region descriptor -typedef struct memregion_s { - b64_t base; // base address - b64_t length; // region length - uint32_t type; // type of region - uint32_t acpi; // ACPI 3.0 info -} ATTR_PACKED region_t; - -/* -** Region types -*/ - -#define REGION_USABLE 1 -#define REGION_RESERVED 2 -#define REGION_ACPI_RECL 3 -#define REGION_ACPI_NVS 4 -#define REGION_BAD 5 - -/* -** ACPI 3.0 bit fields -*/ - -#define REGION_IGNORE 0x01 -#define REGION_NONVOL 0x02 - -/* -** 32-bit and 64-bit address values as 64-bit literals -*/ - -#define ADDR_BIT_32 0x0000000100000000LL -#define ADDR_LOW_HALF 0x00000000ffffffffLL -#define ADDR_HIGH_HALR 0xffffffff00000000LL - -#define ADDR_32_MAX ADDR_LOW_HALF -#define ADDR_64_FIRST ADDR_BIT_32 - -/* -** PRIVATE GLOBAL VARIABLES -*/ - -// freespace pools -static list_t free_pages; -static list_t free_slices; - -// block counts -static uint32_t n_pages; -static uint32_t n_slices; - -// initialization status -static int km_initialized; - -/* -** IMPORTED GLOBAL VARIABLES -*/ - -// this is no longer used; for simple situations, it can be used as -// the KM_LOW_CUTOFF value -// -// extern int _end; // end of the BSS section - provided by the linker - -/* -** FUNCTIONS -*/ - -/* -** FREE LIST MANAGEMENT -*/ - -/** -** Name: add_block -** -** Add a block to the free list. The block will be split into separate -** page-sized fragments which will each be added to the free_pages -** list; each of these will also be modified. -** -** @param[in] base Base physical address of the block -** @param[in] length Block length, in bytes -*/ -static void add_block(uint32_t base, uint32_t length) -{ - // don't add it if it isn't at least 4K - if (length < SZ_PAGE) { - return; - } - -#if ANY_KMEM - cio_printf(" add(%08x,%08x): ", base, length); -#endif - - // verify that the base address is a 4K boundary - if ((base & MOD4K_BITS) != 0) { - // nope - how many bytes will we lose from the beginning - uint_t loss = base & MOD4K_BITS; - // adjust the starting address: (n + 4K - 1) / 4K - base = (base + MOD4K_BITS) & MOD4K_MASK; - // adjust the length - length -= loss; - } - - // only want to add multiples of 4K; check the lower bits - if ((length & MOD4K_BITS) != 0) { - // round it down to 4K - length &= MOD4K_MASK; - } - - // determine the starting and ending addresses for the block -#ifndef USE_PADDRS - // starting and ending addresses as virtual addresses - base = P2V(base); -#endif - // endpoint of the block - uint32_t blend = base + length; - - // page count for this block - int npages = 0; - -#if ANY_KMEM - cio_printf("-> base %08x len %08x: ", base, length); -#endif - - // iterate through the block page by page - while (base < blend) { - list_add(&free_pages, (void *)base); - ++npages; - base += SZ_PAGE; - } - - // add the count to our running total - n_pages += npages; - -#if ANY_KMEM - cio_printf(" -> %d pages\n", npages); -#endif -} - -/** -** Name: km_init -** -** Find what memory is present on the system and -** construct the list of free memory blocks. -** -** Dependencies: -** Must be called before any other init routine that uses -** dynamic storage is called. -*/ -void km_init(void) -{ - int32_t entries; - region_t *region; - -#if TRACING_INIT - // announce that we're starting initialization - cio_puts(" Kmem"); -#endif - - // initially, nothing in the free lists - free_slices.next = NULL; - free_pages.next = NULL; - n_pages = n_slices = 0; - km_initialized = 0; - - // get the list length - entries = *((int32_t *)MMAP_ADDR); - -#if KMEM_OR_INIT - cio_printf("\nKmem: %d regions\n", entries); -#endif - - // if there are no entries, we have nothing to do! - if (entries < 1) { // note: entries == -1 could occur! - return; - } - - // iterate through the entries, adding things to the freelist - - region = ((region_t *)(MMAP_ADDR + 4)); - - for (int i = 0; i < entries; ++i, ++region) { -#if KMEM_OR_INIT - // report this region - cio_printf("%3d: ", i); - cio_printf(" B %08x%08x", region->base.HIGH, region->base.LOW); - cio_printf(" L %08x%08x", region->length.HIGH, region->length.LOW); - cio_printf(" T %08x A %08x", region->type, region->acpi); -#endif - - /* - ** Determine whether or not we should ignore this region. - ** - ** We ignore regions for several reasons: - ** - ** ACPI indicates it should be ignored - ** ACPI indicates it's non-volatile memory - ** Region type isn't "usable" - ** Region is above our address limit - ** - ** Currently, only "normal" (type 1) regions are considered - ** "usable" for our purposes. We could potentially expand - ** this to include ACPI "reclaimable" memory. - */ - - // first, check the ACPI one-bit flags - - if (((region->acpi) & REGION_IGNORE) == 0) { -#if KMEM_OR_INIT - cio_puts(" IGN\n"); -#endif - continue; - } - - if (((region->acpi) & REGION_NONVOL) != 0) { -#if KMEM_OR_INIT - cio_puts(" NVOL\n"); -#endif - continue; // we'll ignore this, too - } - - // next, the region type - - if ((region->type) != REGION_USABLE) { -#if KMEM_OR_INIT - cio_puts(" RCLM\n"); -#endif - continue; // we won't attempt to reclaim ACPI memory (yet) - } - - /* - ** We have a "normal" memory region. We need to verify - ** that it's within our constraints. - ** - ** We ignore anything below our KM_LOW_CUTOFF address. (In theory, - ** we should be able to re-use much of that space; in practice, - ** this is safer.) We won't add anything to the free list if it is: - ** - ** * below our KM_LOW_CUTOFF value - ** * above out KM_HIGH_CUTOFF value. - ** - ** For blocks which straddle one of those limits, we will - ** split it, and only use the portion that's within those - ** bounds. - */ - - // grab the two 64-bit values to simplify things - uint64_t base = region->base.all; - uint64_t length = region->length.all; - uint64_t endpt = base + length; - - // ignore it if it's above our high cutoff point - if (base >= KM_HIGH_CUTOFF || endpt >= KM_HIGH_CUTOFF) { - // is the whole thing too high, or just part? - if (base >= KM_HIGH_CUTOFF) { - // it's all too high! -#if KMEM_OR_INIT - cio_puts(" HIGH\n"); -#endif - continue; - } - - // some of it is usable - fix the end point - endpt = KM_HIGH_CUTOFF; - } - - // see if it's below our low cutoff point - if (base < KM_LOW_CUTOFF || endpt < KM_LOW_CUTOFF) { - // is the whole thing too low, or just part? - if (endpt < KM_LOW_CUTOFF) { - // it's all below the cutoff! -#if KMEM_OR_INIT - cio_puts(" LOW\n"); -#endif - continue; - } - - // some of it is usable - reset the base address - base = KM_LOW_CUTOFF; - - // recalculate the length - length = endpt - base; - } - - // we survived the gauntlet - add the new block - // - // we may have changed the base or endpoint, so - // we should recalculate the length - length = endpt - base; - -#if KMEM_OR_INIT - cio_puts(" OK\n"); -#endif - - uint32_t b32 = base & ADDR_LOW_HALF; - uint32_t l32 = length & ADDR_LOW_HALF; - - add_block(b32, l32); - } - - // record the initialization - km_initialized = 1; - -#if KMEM_OR_INIT - delay(DELAY_3_SEC); -#endif -} - -/** -** Name: km_dump -** -** Dump information about the free lists to the console. By default, -** prints only the list sizes; if 'addrs' is true, also dumps the list -** of page addresses; if 'all' is also true, dumps page addresses and -** slice addresses. -** -** @param addrs Also dump page addresses -** @param both Also dump slice addresses -*/ -void km_dump(bool_t addrs, bool_t both) -{ - // report the sizes - cio_printf("&free_pages %08x, &free_slices %08x, %u pages, %u slices\n", - (uint32_t)&free_pages, (uint32_t)&free_slices, n_pages, - n_slices); - - // was that all? - if (!addrs) { - return; - } - - // dump the addresses of the pages in the free list - uint32_t n = 0; - list_t *block = free_pages.next; - while (block != NULL) { - if (n && !(n & MOD4_BITS)) { - // four per line - cio_putchar('\n'); - } - cio_printf(" page @ 0x%08x", (uint32_t)block); - block = block->next; - ++n; - } - - // sanity check - verify that the counts match - if (n != n_pages) { - sprint(b256, "km_dump: n_pages %u, counted %u!!!\n", n_pages, n); - WARNING(b256); - } - - if (!both) { - return; - } - - // but wait - there's more! - - // also dump the addresses of slices in the slice free list - n = 0; - block = free_slices.next; - while (block != NULL) { - if (n && !(n & MOD4_BITS)) { - // four per line - cio_putchar('\n'); - } - cio_printf(" slc @ 0x%08x", (uint32_t)block); - block = block->next; - ++n; - } - - // sanity check - verify that the counts match - if (n != n_slices) { - sprint(b256, "km_dump: n_slices %u, counted %u!!!\n", n_slices, n); - WARNING(b256); - } -} - -/* -** PAGE MANAGEMENT -*/ - -/** -** Name: km_page_alloc -** -** Allocate a page of memory from the free list. -** -** @return a pointer to the beginning of the allocated page, -** or NULL if no memory is available -*/ -void *km_page_alloc(void) -{ - // if km_init() wasn't called first, stop us in our tracks - assert(km_initialized); - -#if TRACING_KMEM_FREELIST - cio_puts("KM: pg_alloc()"); -#endif - - // pointer to the first block - void *page = list_remove(&free_pages); - - // was a page available? - if (page == NULL) { - // nope! -#if TRACING_KMEM_FREELIST - cio_puts(" FAIL\n"); -#endif -#if ALLOC_FAIL_PANIC - PANIC(0, "page alloc failed"); -#else - return NULL; -#endif - } - - // fix the count of available pages - --n_pages; - -#if TRACING_KMEM_FREELIST - cio_printf(" -> %08x\n", (uint32_t)page); -#endif - - return (page); -} - -/** -** Name: km_page_free -** -** Returns a page to the list of available pages. -** -** @param[in] page Pointer to the page to be returned to the free list -*/ -void km_page_free(void *page) -{ - // verify that km_init() was called first - assert(km_initialized); - -#if TRACING_KMEM_FREELIST - cio_printf("KM: pg_free(%08x)\n", (uint32_t)page); -#endif - - /* - ** Don't do anything if the address is NULL. - */ - if (page == NULL) { - return; - } - - /* - ** CRITICAL ASSUMPTION - ** - ** We assume that the block pointer given to us points to a single - ** page-sized block of memory. We make this assumption because we - ** don't track allocation sizes. We can't use the simple "allocate - ** four extra bytes before the returned pointer" scheme to do this - ** because we're managing pages, and the pointers we return must point - ** to page boundaries, so we would wind up allocating an extra page - ** for each allocation. - ** - ** Alternatively, we could keep an array of addresses and block - ** sizes ourselves, but that feels clunky, and would risk running out - ** of table entries if there are lots of allocations (assuming we use - ** a 4KB page to hold the table, at eight bytes per entry we would have - ** 512 entries per page). - ** - ** IF THIS ASSUMPTION CHANGES, THIS CODE MUST BE FIXED!!! - */ - - // link this into the free list - list_add(&free_pages, page); - - // one more in the pool - ++n_pages; -} - -/* -** SLICE MANAGEMENT -*/ - -/* -** Slices are 1024-byte fragments from pages. We maintain a free list of -** slices for those parts of the OS which don't need full 4096-byte chunks -** of space. -*/ - -/** -** Name: carve_slices -** -** Split an allocated page into four slices and add -** them to the "free slices" list. -** -** @param page Pointer to the page to be carved up -*/ -static void carve_slices(void *page) -{ - // sanity check - assert1(page != NULL); - -#if TRACING_KMEM_FREELIST - cio_printf("KM: carve_slices(%08x)\n", (uint32_t)page); -#endif - - // create the four slices from it - uint8_t *ptr = (uint8_t *)page; - for (int i = 0; i < 4; ++i) { - km_slice_free((void *)ptr); - ptr += SZ_SLICE; - ++n_slices; - } -} - -/** -** Name: km_slice_alloc -** -** Dynamically allocates a slice (1/4 of a page). If no -** memory is available, we return NULL (unless ALLOC_FAIL_PANIC -** was defined, in which case we panic). -** -** @return a pointer to the allocated slice -*/ -void *km_slice_alloc(void) -{ - // verify that km_init() was called first - assert(km_initialized); - -#if TRACING_KMEM_FREELIST - cio_printf("KM: sl_alloc()\n"); -#endif - - // if we are out of slices, create a few more - if (free_slices.next == NULL) { - void *new = km_page_alloc(); - if (new == NULL) { - // can't get any more space -#if ALLOC_FAIL_PANIC - PANIC(0, "slice new alloc failed"); -#else - return NULL; -#endif - } - carve_slices(new); - } - - // take the first one from the free list - void *slice = list_remove(&free_slices); - assert(slice != NULL); - --n_slices; - - // make it nice and shiny for the caller - memclr((void *)slice, SZ_SLICE); - - return (slice); -} - -/** -** Name: km_slice_free -** -** Returns a slice to the list of available slices. -** -** We make no attempt to merge slices, as we treat them as -** independent blocks of memory (like pages). -** -** @param[in] block Pointer to the slice (1/4 page) to be freed -*/ -void km_slice_free(void *block) -{ - // verify that km_init() was called first - assert(km_initialized); - -#if TRACING_KMEM_FREELIST - cio_printf("KM: sl_free(%08x)\n", (uint32_t)block); -#endif - - // just add it to the front of the free list - list_add(&free_slices, block); - --n_slices; -} |