kern

annotate src/mem.c @ 30:a2c6110bd24b

find changesets by author, revision, files, or words in the commit message
refactored the code a bit, and merged with the malloc implementation branch
author John Tsiombikas <nuclear@siggraph.org>
date Fri, 27 May 2011 22:09:10 +0300
parents 5454cee245a3
children b793b8fcba7d
rev   line source
nuclear@17 1 #include <stdio.h>
nuclear@19 2 #include <string.h>
nuclear@17 3 #include "mem.h"
nuclear@17 4 #include "panic.h"
nuclear@17 5 #include "vm.h"
nuclear@25 6 #include "intr.h"
nuclear@17 7
nuclear@19 8 #define FREE 0
nuclear@19 9 #define USED 1
nuclear@19 10
nuclear@19 11 #define BM_IDX(pg) ((pg) / 32)
nuclear@19 12 #define BM_BIT(pg) ((pg) & 0x1f)
nuclear@19 13
nuclear@19 14 #define IS_FREE(pg) ((bitmap[BM_IDX(pg)] & (1 << BM_BIT(pg))) == 0)
nuclear@19 15
nuclear@19 16 static void mark_page(int pg, int free);
nuclear@19 17 static void add_memory(uint32_t start, size_t size);
nuclear@19 18
nuclear@17 19 /* end of kernel image */
nuclear@17 20 extern int _end;
nuclear@17 21
nuclear@20 22 /* A bitmap is used to track which physical memory pages are used or available
nuclear@20 23 * for allocation by alloc_phys_page.
nuclear@20 24 *
nuclear@20 25 * last_alloc_idx keeps track of the last 32bit element in the bitmap array
nuclear@20 26 * where a free page was found. It's guaranteed that all the elements before
nuclear@20 27 * this have no free pages, but it doesn't imply that there will be another
nuclear@20 28 * free page there. So it's used as a starting point for the search.
nuclear@20 29 */
nuclear@19 30 static uint32_t *bitmap;
nuclear@19 31 static int bmsize, last_alloc_idx;
nuclear@17 32
nuclear@20 33
nuclear@17 34 void init_mem(struct mboot_info *mb)
nuclear@17 35 {
nuclear@19 36 int i, num_pages, max_pg = 0;
nuclear@19 37 uint32_t used_end;
nuclear@19 38
nuclear@19 39 num_pages = 0;
nuclear@19 40 last_alloc_idx = 0;
nuclear@19 41
nuclear@20 42 /* the allocation bitmap starts right at the end of the ELF image */
nuclear@19 43 bitmap = (uint32_t*)&_end;
nuclear@19 44
nuclear@20 45 /* start by marking all posible pages (2**20) as used. We do not "reserve"
nuclear@20 46 * all this space. Pages beyond the end of the useful bitmap area
nuclear@20 47 * ((char*)bitmap + bmsize), which will be determined after we traverse the
nuclear@20 48 * memory map, are going to be marked as available for allocation.
nuclear@20 49 */
nuclear@19 50 memset(bitmap, 0xff, 1024 * 1024 / 8);
nuclear@19 51
nuclear@20 52 /* if the bootloader gave us an available memory map, traverse it and mark
nuclear@20 53 * all the corresponding pages as free.
nuclear@20 54 */
nuclear@19 55 if(mb->flags & MB_MMAP) {
nuclear@19 56 struct mboot_mmap *mem, *mmap_end;
nuclear@19 57
nuclear@19 58 mem = mb->mmap;
nuclear@19 59 mmap_end = (struct mboot_mmap*)((char*)mb->mmap + mb->mmap_len);
nuclear@19 60
nuclear@19 61 printf("memory map:\n");
nuclear@19 62 while(mem < mmap_end) {
nuclear@21 63 /* ignore memory ranges that start beyond the 4gb mark */
nuclear@21 64 if(mem->base_high == 0 && mem->base_low != 0xffffffff) {
nuclear@21 65 char *type;
nuclear@21 66 unsigned int end, rest = 0xffffffff - mem->base_low;
nuclear@19 67
nuclear@21 68 /* make sure the length does not extend beyond 4gb */
nuclear@21 69 if(mem->length_high || mem->length_low > rest) {
nuclear@21 70 mem->length_low = rest;
nuclear@21 71 }
nuclear@21 72 end = mem->base_low + mem->length_low;
nuclear@19 73
nuclear@21 74 if(mem->type == MB_MEM_VALID) {
nuclear@21 75 type = "free:";
nuclear@21 76 add_memory(mem->base_low, mem->length_low);
nuclear@21 77
nuclear@21 78 num_pages = ADDR_TO_PAGE(mem->base_low + mem->length_low);
nuclear@21 79 if(max_pg < num_pages) {
nuclear@21 80 max_pg = num_pages;
nuclear@21 81 }
nuclear@21 82 } else {
nuclear@21 83 type = "hole:";
nuclear@19 84 }
nuclear@21 85
nuclear@21 86 printf(" %s %x - %x (%u bytes)\n", type, mem->base_low, end, mem->length_low);
nuclear@19 87 }
nuclear@19 88 mem = (struct mboot_mmap*)((char*)mem + mem->skip + sizeof mem->skip);
nuclear@19 89 }
nuclear@19 90 } else if(mb->flags & MB_MEM) {
nuclear@20 91 /* if we don't have a detailed memory map, just use the lower and upper
nuclear@20 92 * memory block sizes to determine which pages should be available.
nuclear@20 93 */
nuclear@19 94 add_memory(0, mb->mem_lower);
nuclear@19 95 add_memory(0x100000, mb->mem_upper * 1024);
nuclear@19 96 max_pg = mb->mem_upper / 4;
nuclear@19 97
nuclear@19 98 printf("lower memory: %ukb, upper mem: %ukb\n", mb->mem_lower, mb->mem_upper);
nuclear@19 99 } else {
nuclear@20 100 /* I don't think this should ever happen with a multiboot-compliant boot loader */
nuclear@19 101 panic("didn't get any memory info from the boot loader, I give up\n");
nuclear@19 102 }
nuclear@19 103
nuclear@20 104 bmsize = max_pg / 8; /* size of the useful bitmap in bytes */
nuclear@19 105
nuclear@19 106 /* mark all the used pages as ... well ... used */
nuclear@19 107 used_end = ((uint32_t)bitmap + bmsize - 1);
nuclear@19 108
nuclear@19 109 printf("marking pages up to %x ", used_end);
nuclear@19 110 used_end = ADDR_TO_PAGE(used_end);
nuclear@19 111 printf("(page: %d) inclusive as used\n", used_end);
nuclear@19 112
nuclear@19 113 for(i=0; i<=used_end; i++) {
nuclear@19 114 mark_page(i, USED);
nuclear@19 115 }
nuclear@17 116 }
nuclear@17 117
nuclear@20 118 /* alloc_phys_page finds the first available page of physical memory,
nuclear@20 119 * marks it as used in the bitmap, and returns its address. If there's
nuclear@20 120 * no unused physical page, 0 is returned.
nuclear@20 121 */
nuclear@17 122 uint32_t alloc_phys_page(void)
nuclear@17 123 {
nuclear@25 124 int i, idx, max, intr_state;
nuclear@25 125
nuclear@25 126 intr_state = get_intr_state();
nuclear@25 127 disable_intr();
nuclear@17 128
nuclear@19 129 idx = last_alloc_idx;
nuclear@19 130 max = bmsize / 4;
nuclear@19 131
nuclear@19 132 while(idx <= max) {
nuclear@19 133 /* if at least one bit is 0 then we have at least
nuclear@19 134 * one free page. find it and allocate it.
nuclear@19 135 */
nuclear@19 136 if(bitmap[idx] != 0xffffffff) {
nuclear@19 137 for(i=0; i<32; i++) {
nuclear@19 138 int pg = idx * 32 + i;
nuclear@19 139
nuclear@19 140 if(IS_FREE(pg)) {
nuclear@19 141 mark_page(pg, USED);
nuclear@19 142
nuclear@19 143 last_alloc_idx = idx;
nuclear@19 144
nuclear@19 145 printf("alloc_phys_page() -> %x (page: %d)\n", PAGE_TO_ADDR(pg), pg);
nuclear@25 146
nuclear@25 147 set_intr_state(intr_state);
nuclear@19 148 return PAGE_TO_ADDR(pg);
nuclear@19 149 }
nuclear@19 150 }
nuclear@19 151 panic("can't happen: alloc_phys_page (mem.c)\n");
nuclear@19 152 }
nuclear@19 153 idx++;
nuclear@17 154 }
nuclear@17 155
nuclear@25 156 set_intr_state(intr_state);
nuclear@19 157 return 0;
nuclear@19 158 }
nuclear@19 159
nuclear@20 160 /* free_phys_page marks the physical page which corresponds to the specified
nuclear@20 161 * address as free in the allocation bitmap.
nuclear@20 162 *
nuclear@20 163 * CAUTION: no checks are done that this page should actually be freed or not.
nuclear@20 164 * If you call free_phys_page with the address of some part of memory that was
nuclear@20 165 * originally reserved due to it being in a memory hole or part of the kernel
nuclear@20 166 * image or whatever, it will be subsequently allocatable by alloc_phys_page.
nuclear@20 167 */
nuclear@19 168 void free_phys_page(uint32_t addr)
nuclear@19 169 {
nuclear@19 170 int pg = ADDR_TO_PAGE(addr);
nuclear@19 171 int bmidx = BM_IDX(pg);
nuclear@19 172
nuclear@25 173 int intr_state = get_intr_state();
nuclear@25 174 disable_intr();
nuclear@25 175
nuclear@19 176 if(!IS_FREE(pg)) {
nuclear@19 177 panic("free_phys_page(%d): I thought that was already free!\n", pg);
nuclear@17 178 }
nuclear@17 179
nuclear@19 180 mark_page(pg, FREE);
nuclear@19 181 if(bmidx < last_alloc_idx) {
nuclear@19 182 last_alloc_idx = bmidx;
nuclear@19 183 }
nuclear@25 184
nuclear@25 185 set_intr_state(intr_state);
nuclear@19 186 }
nuclear@17 187
nuclear@20 188 /* this is only ever used by the VM init code to find out what the extends of
nuclear@20 189 * the kernel image are, in order to map them 1-1 before enabling paging.
nuclear@20 190 */
nuclear@19 191 void get_kernel_mem_range(uint32_t *start, uint32_t *end)
nuclear@19 192 {
nuclear@19 193 if(start) {
nuclear@19 194 *start = 0x100000;
nuclear@19 195 }
nuclear@19 196 if(end) {
nuclear@19 197 uint32_t e = (uint32_t)bitmap + bmsize;
nuclear@19 198
nuclear@19 199 if(e & PGOFFS_MASK) {
nuclear@23 200 *end = (e + 4096) & ~PGOFFS_MASK;
nuclear@19 201 } else {
nuclear@19 202 *end = e;
nuclear@19 203 }
nuclear@19 204 }
nuclear@17 205 }
nuclear@19 206
nuclear@20 207 /* adds a range of physical memory to the available pool. used during init_mem
nuclear@20 208 * when traversing the memory map.
nuclear@20 209 */
nuclear@19 210 static void add_memory(uint32_t start, size_t sz)
nuclear@19 211 {
nuclear@19 212 int i, szpg, pg;
nuclear@19 213
nuclear@19 214 szpg = ADDR_TO_PAGE(sz);
nuclear@19 215 pg = ADDR_TO_PAGE(start);
nuclear@19 216
nuclear@19 217 for(i=0; i<szpg; i++) {
nuclear@19 218 mark_page(pg++, FREE);
nuclear@19 219 }
nuclear@19 220 }
nuclear@19 221
nuclear@20 222 /* maps a page as used or free in the allocation bitmap */
nuclear@19 223 static void mark_page(int pg, int used)
nuclear@19 224 {
nuclear@19 225 int idx = BM_IDX(pg);
nuclear@19 226 int bit = BM_BIT(pg);
nuclear@19 227
nuclear@19 228 if(used) {
nuclear@19 229 bitmap[idx] |= 1 << bit;
nuclear@19 230 } else {
nuclear@19 231 bitmap[idx] &= ~(1 << bit);
nuclear@19 232 }
nuclear@19 233 }
nuclear@19 234