diff options
| -rw-r--r-- | Makefrag.am | 1 | ||||
| -rw-r--r-- | i386/i386at/biosmem.c | 831 | ||||
| -rw-r--r-- | i386/i386at/biosmem.h | 84 | ||||
| -rw-r--r-- | vm/vm_page.c | 735 | ||||
| -rw-r--r-- | vm/vm_page.h | 442 |
5 files changed, 1812 insertions, 281 deletions
diff --git a/Makefrag.am b/Makefrag.am index b9d96c5..35a4884 100644 --- a/Makefrag.am +++ b/Makefrag.am @@ -259,6 +259,7 @@ libkernel_a_SOURCES += \ vm/vm_map.h \ vm/vm_object.c \ vm/vm_object.h \ + vm/vm_page.c \ vm/vm_page.h \ vm/vm_pageout.c \ vm/vm_pageout.h \ diff --git a/i386/i386at/biosmem.c b/i386/i386at/biosmem.c new file mode 100644 index 0000000..d666f1b --- /dev/null +++ b/i386/i386at/biosmem.c @@ -0,0 +1,831 @@ +/* + * Copyright (c) 2010-2014 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <kern/assert.h> +#include <kern/init.h> +#include <kern/macros.h> +#include <kern/panic.h> +#include <kern/param.h> +#include <kern/printk.h> +#include <kern/stddef.h> +#include <kern/stdint.h> +#include <kern/string.h> +#include <kern/types.h> +#include <machine/biosmem.h> +#include <machine/boot.h> +#include <machine/cpu.h> +#include <machine/elf.h> +#include <machine/multiboot.h> +#include <vm/vm_kmem.h> +#include <vm/vm_page.h> + +/* + * Maximum number of entries in the BIOS memory map. + * + * Because of adjustments of overlapping ranges, the memory map can grow + * to twice this size. + */ +#define BIOSMEM_MAX_MAP_SIZE 128 + +/* + * Memory range types. + */ +#define BIOSMEM_TYPE_AVAILABLE 1 +#define BIOSMEM_TYPE_RESERVED 2 +#define BIOSMEM_TYPE_ACPI 3 +#define BIOSMEM_TYPE_NVS 4 +#define BIOSMEM_TYPE_UNUSABLE 5 +#define BIOSMEM_TYPE_DISABLED 6 + +/* + * Memory map entry. + */ +struct biosmem_map_entry { + uint64_t base_addr; + uint64_t length; + unsigned int type; +}; + +/* + * Contiguous block of physical memory. + * + * Tha "available" range records what has been passed to the VM system as + * available inside the segment. + */ +struct biosmem_segment { + phys_addr_t start; + phys_addr_t end; + phys_addr_t avail_start; + phys_addr_t avail_end; +}; + +/* + * Memory map built from the information passed by the boot loader. + * + * If the boot loader didn't pass a valid memory map, a simple map is built + * based on the mem_lower and mem_upper multiboot fields. + */ +static struct biosmem_map_entry biosmem_map[BIOSMEM_MAX_MAP_SIZE * 2] + __bootdata; +static unsigned int biosmem_map_size __bootdata; + +/* + * Physical segment boundaries. + */ +static struct biosmem_segment biosmem_segments[VM_PAGE_MAX_SEGS] __bootdata; + +/* + * Boundaries of the simple bootstrap heap. + * + * This heap is located above BIOS memory. + */ +static uint32_t biosmem_heap_start __bootdata; +static uint32_t biosmem_heap_cur __bootdata; +static uint32_t biosmem_heap_end __bootdata; + +static char biosmem_panic_toobig_msg[] __bootdata + = "biosmem: too many memory map entries"; +static char biosmem_panic_setup_msg[] __bootdata + = "biosmem: unable to set up the early memory allocator"; +static char biosmem_panic_noseg_msg[] __bootdata + = "biosmem: unable to find any memory segment"; +static char biosmem_panic_inval_msg[] __bootdata + = "biosmem: attempt to allocate 0 page"; +static char biosmem_panic_nomem_msg[] __bootdata + = "biosmem: unable to allocate memory"; + +static void __boot +biosmem_map_build(const struct multiboot_raw_info *mbi) +{ + struct multiboot_raw_mmap_entry *mb_entry, *mb_end; + struct biosmem_map_entry *start, *entry, *end; + unsigned long addr; + + addr = mbi->mmap_addr; + mb_entry = (struct multiboot_raw_mmap_entry *)addr; + mb_end = (struct multiboot_raw_mmap_entry *)(addr + mbi->mmap_length); + start = biosmem_map; + entry = start; + end = entry + BIOSMEM_MAX_MAP_SIZE; + + while ((mb_entry < mb_end) && (entry < end)) { + entry->base_addr = mb_entry->base_addr; + entry->length = mb_entry->length; + entry->type = mb_entry->type; + + mb_entry = (void *)mb_entry + sizeof(mb_entry->size) + mb_entry->size; + entry++; + } + + biosmem_map_size = entry - start; +} + +static void __boot +biosmem_map_build_simple(const struct multiboot_raw_info *mbi) +{ + struct biosmem_map_entry *entry; + + entry = biosmem_map; + entry->base_addr = 0; + entry->length = mbi->mem_lower << 10; + entry->type = BIOSMEM_TYPE_AVAILABLE; + + entry++; + entry->base_addr = BIOSMEM_END; + entry->length = mbi->mem_upper << 10; + entry->type = BIOSMEM_TYPE_AVAILABLE; + + biosmem_map_size = 2; +} + +static int __boot +biosmem_map_entry_is_invalid(const struct biosmem_map_entry *entry) +{ + return (entry->base_addr + entry->length) <= entry->base_addr; +} + +static void __boot +biosmem_map_filter(void) +{ + struct biosmem_map_entry *entry; + unsigned int i; + + i = 0; + + while (i < biosmem_map_size) { + entry = &biosmem_map[i]; + + if (biosmem_map_entry_is_invalid(entry)) { + biosmem_map_size--; + boot_memmove(entry, entry + 1, + (biosmem_map_size - i) * sizeof(*entry)); + continue; + } + + i++; + } +} + +static void __boot +biosmem_map_sort(void) +{ + struct biosmem_map_entry tmp; + unsigned int i, j; + + /* + * Simple insertion sort. + */ + for (i = 1; i < biosmem_map_size; i++) { + tmp = biosmem_map[i]; + + for (j = i - 1; j < i; j--) { + if (biosmem_map[j].base_addr < tmp.base_addr) + break; + + biosmem_map[j + 1] = biosmem_map[j]; + } + + biosmem_map[j + 1] = tmp; + } +} + +static void __boot +biosmem_map_adjust(void) +{ + struct biosmem_map_entry tmp, *a, *b, *first, *second; + uint64_t a_end, b_end, last_end; + unsigned int i, j, last_type; + + biosmem_map_filter(); + + /* + * Resolve overlapping areas, giving priority to most restrictive + * (i.e. numerically higher) types. + */ + for (i = 0; i < biosmem_map_size; i++) { + a = &biosmem_map[i]; + a_end = a->base_addr + a->length; + + j = i + 1; + + while (j < biosmem_map_size) { + b = &biosmem_map[j]; + b_end = b->base_addr + b->length; + + if ((a->base_addr >= b_end) || (a_end <= b->base_addr)) { + j++; + continue; + } + + if (a->base_addr < b->base_addr) { + first = a; + second = b; + } else { + first = b; + second = a; + } + + if (a_end > b_end) { + last_end = a_end; + last_type = a->type; + } else { + last_end = b_end; + last_type = b->type; + } + + tmp.base_addr = second->base_addr; + tmp.length = MIN(a_end, b_end) - tmp.base_addr; + tmp.type = MAX(a->type, b->type); + first->length = tmp.base_addr - first->base_addr; + second->base_addr += tmp.length; + second->length = last_end - second->base_addr; + second->type = last_type; + + /* + * Filter out invalid entries. + */ + if (biosmem_map_entry_is_invalid(a) + && biosmem_map_entry_is_invalid(b)) { + *a = tmp; + biosmem_map_size--; + memmove(b, b + 1, (biosmem_map_size - j) * sizeof(*b)); + continue; + } else if (biosmem_map_entry_is_invalid(a)) { + *a = tmp; + j++; + continue; + } else if (biosmem_map_entry_is_invalid(b)) { + *b = tmp; + j++; + continue; + } + + if (tmp.type == a->type) + first = a; + else if (tmp.type == b->type) + first = b; + else { + + /* + * If the overlapping area can't be merged with one of its + * neighbors, it must be added as a new entry. + */ + + if (biosmem_map_size >= ARRAY_SIZE(biosmem_map)) + boot_panic(biosmem_panic_toobig_msg); + + biosmem_map[biosmem_map_size] = tmp; + biosmem_map_size++; + j++; + continue; + } + + if (first->base_addr > tmp.base_addr) + first->base_addr = tmp.base_addr; + + first->length += tmp.length; + j++; + } + } + + biosmem_map_sort(); +} + +static int __boot +biosmem_map_find_avail(phys_addr_t *phys_start, phys_addr_t *phys_end) +{ + const struct biosmem_map_entry *entry, *map_end; + phys_addr_t seg_start, seg_end; + uint64_t start, end; + + seg_start = (phys_addr_t)-1; + seg_end = (phys_addr_t)-1; + map_end = biosmem_map + biosmem_map_size; + + for (entry = biosmem_map; entry < map_end; entry++) { + if (entry->type != BIOSMEM_TYPE_AVAILABLE) + continue; + + start = vm_page_round(entry->base_addr); + + if (start >= *phys_end) + break; + + end = vm_page_trunc(entry->base_addr + entry->length); + + if ((start < end) && (start < *phys_end) && (end > *phys_start)) { + if (seg_start == (phys_addr_t)-1) + seg_start = start; + + seg_end = end; + } + } + + if ((seg_start == (phys_addr_t)-1) || (seg_end == (phys_addr_t)-1)) + return -1; + + if (seg_start > *phys_start) + *phys_start = seg_start; + + if (seg_end < *phys_end) + *phys_end = seg_end; + + return 0; +} + +static void __boot +biosmem_set_segment(unsigned int seg_index, phys_addr_t start, phys_addr_t end) +{ + biosmem_segments[seg_index].start = start; + biosmem_segments[seg_index].end = end; +} + +static phys_addr_t __boot +biosmem_segment_end(unsigned int seg_index) +{ + return biosmem_segments[seg_index].end; +} + +static phys_addr_t __boot +biosmem_segment_size(unsigned int seg_index) +{ + return biosmem_segments[seg_index].end - biosmem_segments[seg_index].start; +} + +static void __boot +biosmem_save_cmdline_sizes(struct multiboot_raw_info *mbi) +{ + struct multiboot_raw_module *mod; + uint32_t i; + + if (mbi->flags & MULTIBOOT_LOADER_CMDLINE) + mbi->unused0 = boot_strlen((char *)(unsigned long)mbi->cmdline) + 1; + + if (mbi->flags & MULTIBOOT_LOADER_MODULES) { + unsigned long addr; + + addr = mbi->mods_addr; + + for (i = 0; i < mbi->mods_count; i++) { + mod = (struct multiboot_raw_module *)addr + i; + mod->reserved = boot_strlen((char *)(unsigned long)mod->string) + 1; + } + } +} + +static void __boot +biosmem_find_boot_data_update(uint32_t min, uint32_t *start, uint32_t *end, + uint32_t data_start, uint32_t data_end) +{ + if ((min <= data_start) && (data_start < *start)) { + *start = data_start; + *end = data_end; + } +} + +/* + * Find the first boot data in the given range, and return their containing + * area (start address is returned directly, end address is returned in end). + * The following are considered boot data : + * - the kernel + * - the kernel command line + * - the module table + * - the modules + * - the modules command lines + * - the ELF section header table + * - the ELF .shstrtab, .symtab and .strtab sections + * + * If no boot data was found, 0 is returned, and the end address isn't set. + */ +static uint32_t __boot +biosmem_find_boot_data(const struct multiboot_raw_info *mbi, uint32_t min, + uint32_t max, uint32_t *endp) +{ + struct multiboot_raw_module *mod; + struct elf_shdr *shdr; + uint32_t i, start, end = end; + unsigned long tmp; + + start = max; + + biosmem_find_boot_data_update(min, &start, &end, (unsigned long)&_boot, + BOOT_VTOP((unsigned long)&_end)); + + if ((mbi->flags & MULTIBOOT_LOADER_CMDLINE) && (mbi->cmdline != 0)) + biosmem_find_boot_data_update(min, &start, &end, mbi->cmdline, + mbi->cmdline + mbi->unused0); + + if (mbi->flags & MULTIBOOT_LOADER_MODULES) { + i = mbi->mods_count * sizeof(struct multiboot_raw_module); + biosmem_find_boot_data_update(min, &start, &end, mbi->mods_addr, + mbi->mods_addr + i); + tmp = mbi->mods_addr; + + for (i = 0; i < mbi->mods_count; i++) { + mod = (struct multiboot_raw_module *)tmp + i; + biosmem_find_boot_data_update(min, &start, &end, mod->mod_start, + mod->mod_end); + + if (mod->string != 0) + biosmem_find_boot_data_update(min, &start, &end, mod->string, + mod->string + mod->reserved); + } + } + + if (mbi->flags & MULTIBOOT_LOADER_SHDR) { + tmp = mbi->shdr_num * mbi->shdr_size; + biosmem_find_boot_data_update(min, &start, &end, mbi->shdr_addr, + mbi->shdr_addr + tmp); + tmp = mbi->shdr_addr; + + for (i = 0; i < mbi->shdr_num; i++) { + shdr = (struct elf_shdr *)(tmp + (i * mbi->shdr_size)); + + if ((shdr->type != ELF_SHT_SYMTAB) + && (shdr->type != ELF_SHT_STRTAB)) + continue; + + biosmem_find_boot_data_update(min, &start, &end, shdr->addr, + shdr->addr + shdr->size); + } + } + + if (start == max) + return 0; + + *endp = end; + return start; +} + +static void __boot +biosmem_setup_allocator(struct multiboot_raw_info *mbi) +{ + uint32_t heap_start, heap_end, max_heap_start, max_heap_end; + uint32_t mem_end, next; + + /* + * Find some memory for the heap. Look for the largest unused area in + * upper memory, carefully avoiding all boot data. + */ + mem_end = vm_page_trunc((mbi->mem_upper + 1024) << 10); + +#ifndef __LP64__ + if (mem_end > VM_PAGE_DIRECTMAP_LIMIT) + mem_end = VM_PAGE_DIRECTMAP_LIMIT; +#endif /* __LP64__ */ + + max_heap_start = 0; + max_heap_end = 0; + next = BIOSMEM_END; + + do { + heap_start = next; + heap_end = biosmem_find_boot_data(mbi, heap_start, mem_end, &next); + + if (heap_end == 0) { + heap_end = mem_end; + next = 0; + } + + if ((heap_end - heap_start) > (max_heap_end - max_heap_start)) { + max_heap_start = heap_start; + max_heap_end = heap_end; + } + } while (next != 0); + + max_heap_start = vm_page_round(max_heap_start); + max_heap_end = vm_page_trunc(max_heap_end); + + if (max_heap_start >= max_heap_end) + boot_panic(biosmem_panic_setup_msg); + + biosmem_heap_start = max_heap_start; + biosmem_heap_end = max_heap_end; + biosmem_heap_cur = biosmem_heap_end; +} + +void __boot +biosmem_bootstrap(struct multiboot_raw_info *mbi) +{ + phys_addr_t phys_start, phys_end; + int error; + + if (mbi->flags & MULTIBOOT_LOADER_MMAP) + biosmem_map_build(mbi); + else + biosmem_map_build_simple(mbi); + + biosmem_map_adjust(); + + phys_start = BIOSMEM_BASE; + phys_end = VM_PAGE_DMA_LIMIT; + error = biosmem_map_find_avail(&phys_start, &phys_end); + + if (error) + boot_panic(biosmem_panic_noseg_msg); + + biosmem_set_segment(VM_PAGE_SEG_DMA, phys_start, phys_end); + + phys_start = VM_PAGE_DMA_LIMIT; +#ifdef VM_PAGE_DMA32_LIMIT + phys_end = VM_PAGE_DMA32_LIMIT; + error = biosmem_map_find_avail(&phys_start, &phys_end); + + if (error) + goto out; + + biosmem_set_segment(VM_PAGE_SEG_DMA32, phys_start, phys_end); + + phys_start = VM_PAGE_DMA32_LIMIT; +#endif /* VM_PAGE_DMA32_LIMIT */ + phys_end = VM_PAGE_DIRECTMAP_LIMIT; + error = biosmem_map_find_avail(&phys_start, &phys_end); + + if (error) + goto out; + + biosmem_set_segment(VM_PAGE_SEG_DIRECTMAP, phys_start, phys_end); + + phys_start = VM_PAGE_DIRECTMAP_LIMIT; + phys_end = VM_PAGE_HIGHMEM_LIMIT; + error = biosmem_map_find_avail(&phys_start, &phys_end); + + if (error) + goto out; + + biosmem_set_segment(VM_PAGE_SEG_HIGHMEM, phys_start, phys_end); + +out: + + /* + * The kernel and modules command lines will be memory mapped later + * during initialization. Their respective sizes must be saved. + */ + biosmem_save_cmdline_sizes(mbi); + biosmem_setup_allocator(mbi); +} + +void * __boot +biosmem_bootalloc(unsigned int nr_pages) +{ + unsigned long addr, size; + + size = vm_page_ptoa(nr_pages); + + if (size == 0) + boot_panic(biosmem_panic_inval_msg); + + /* Top-down allocation to avoid unnecessarily filling DMA segments */ + addr = biosmem_heap_cur - size; + + if ((addr < biosmem_heap_start) || (addr > biosmem_heap_cur)) + boot_panic(biosmem_panic_nomem_msg); + + biosmem_heap_cur = addr; + return boot_memset((void *)addr, 0, size); +} + +phys_addr_t __boot +biosmem_directmap_size(void) +{ + if (biosmem_segment_size(VM_PAGE_SEG_DIRECTMAP) != 0) + return biosmem_segment_end(VM_PAGE_SEG_DIRECTMAP); + else if (biosmem_segment_size(VM_PAGE_SEG_DMA32) != 0) + return biosmem_segment_end(VM_PAGE_SEG_DMA32); + else + return biosmem_segment_end(VM_PAGE_SEG_DMA); +} + +static const char * __init +biosmem_type_desc(unsigned int type) +{ + switch (type) { + case BIOSMEM_TYPE_AVAILABLE: + return "available"; + case BIOSMEM_TYPE_RESERVED: + return "reserved"; + case BIOSMEM_TYPE_ACPI: + return "ACPI"; + case BIOSMEM_TYPE_NVS: + return "ACPI NVS"; + case BIOSMEM_TYPE_UNUSABLE: + return "unusable"; + default: + return "unknown (reserved)"; + } +} + +static void __init +biosmem_map_show(void) +{ + const struct biosmem_map_entry *entry, *end; + + printk("biosmem: physical memory map:\n"); + + for (entry = biosmem_map, end = entry + biosmem_map_size; + entry < end; + entry++) + printk("biosmem: %018llx:%018llx, %s\n", entry->base_addr, + entry->base_addr + entry->length, + biosmem_type_desc(entry->type)); + + printk("biosmem: heap: %x-%x\n", biosmem_heap_start, biosmem_heap_end); +} + +static void __init +biosmem_load_segment(struct biosmem_segment *seg, uint64_t max_phys_end, + phys_addr_t phys_start, phys_addr_t phys_end, + phys_addr_t avail_start, phys_addr_t avail_end) +{ + unsigned int seg_index; + + seg_index = seg - biosmem_segments; + + if (phys_end > max_phys_end) { + if (max_phys_end <= phys_start) { + printk("biosmem: warning: segment %s physically unreachable, " + "not loaded\n", vm_page_seg_name(seg_index)); + return; + } + + printk("biosmem: warning: segment %s truncated to %#llx\n", + vm_page_seg_name(seg_index), max_phys_end); + phys_end = max_phys_end; + } + + if ((avail_start < phys_start) || (avail_start >= phys_end)) + avail_start = phys_start; + + if ((avail_end <= phys_start) || (avail_end > phys_end)) + avail_end = phys_end; + + seg->avail_start = avail_start; + seg->avail_end = avail_end; + vm_page_load(seg_index, phys_start, phys_end, avail_start, avail_end); +} + +void __init +biosmem_setup(void) +{ + uint64_t max_phys_end; + struct biosmem_segment *seg; + struct cpu *cpu; + unsigned int i; + + biosmem_map_show(); + + cpu = cpu_current(); + max_phys_end = (cpu->phys_addr_width == 0) + ? (uint64_t)-1 + : (uint64_t)1 << cpu->phys_addr_width; + + for (i = 0; i < ARRAY_SIZE(biosmem_segments); i++) { + if (biosmem_segment_size(i) == 0) + break; + + seg = &biosmem_segments[i]; + biosmem_load_segment(seg, max_phys_end, seg->start, seg->end, + biosmem_heap_start, biosmem_heap_cur); + } +} + +static void __init +biosmem_free_usable_range(phys_addr_t start, phys_addr_t end) +{ + struct vm_page *page; + + printk("biosmem: release to vm_page: %llx-%llx (%lluk)\n", + (unsigned long long)start, (unsigned long long)end, + (unsigned long long)((end - start) >> 10)); + + while (start < end) { + page = vm_page_lookup(start); + assert(page != NULL); + vm_page_manage(page); + start += PAGE_SIZE; + } +} + +static void __init +biosmem_free_usable_update_start(phys_addr_t *start, phys_addr_t res_start, + phys_addr_t res_end) +{ + if ((*start >= res_start) && (*start < res_end)) + *start = res_end; +} + +static phys_addr_t __init +biosmem_free_usable_start(phys_addr_t start) +{ + const struct biosmem_segment *seg; + unsigned int i; + + biosmem_free_usable_update_start(&start, (unsigned long)&_boot, + BOOT_VTOP((unsigned long)&_end)); + biosmem_free_usable_update_start(&start, biosmem_heap_start, + biosmem_heap_end); + + for (i = 0; i < ARRAY_SIZE(biosmem_segments); i++) { + seg = &biosmem_segments[i]; + biosmem_free_usable_update_start(&start, seg->avail_start, + seg->avail_end); + } + + return start; +} + +static int __init +biosmem_free_usable_reserved(phys_addr_t addr) +{ + const struct biosmem_segment *seg; + unsigned int i; + + if ((addr >= (unsigned long)&_boot) + && (addr < BOOT_VTOP((unsigned long)&_end))) + return 1; + + if ((addr >= biosmem_heap_start) && (addr < biosmem_heap_end)) + return 1; + + for (i = 0; i < ARRAY_SIZE(biosmem_segments); i++) { + seg = &biosmem_segments[i]; + + if ((addr >= seg->avail_start) && (addr < seg->avail_end)) + return 1; + } + + return 0; +} + +static phys_addr_t __init +biosmem_free_usable_end(phys_addr_t start, phys_addr_t entry_end) +{ + while (start < entry_end) { + if (biosmem_free_usable_reserved(start)) + break; + + start += PAGE_SIZE; + } + + return start; +} + +static void __init +biosmem_free_usable_entry(phys_addr_t start, phys_addr_t end) +{ + phys_addr_t entry_end; + + entry_end = end; + + for (;;) { + start = biosmem_free_usable_start(start); + + if (start >= entry_end) + return; + + end = biosmem_free_usable_end(start, entry_end); + biosmem_free_usable_range(start, end); + start = end; + } +} + +void __init +biosmem_free_usable(void) +{ + struct biosmem_map_entry *entry; + uint64_t start, end; + unsigned int i; + + for (i = 0; i < biosmem_map_size; i++) { + entry = &biosmem_map[i]; + + if (entry->type != BIOSMEM_TYPE_AVAILABLE) + continue; + + start = vm_page_round(entry->base_addr); + + if (start >= VM_PAGE_HIGHMEM_LIMIT) + break; + + end = vm_page_trunc(entry->base_addr + entry->length); + + if (start < BIOSMEM_BASE) + start = BIOSMEM_BASE; + + biosmem_free_usable_entry(start, end); + } +} diff --git a/i386/i386at/biosmem.h b/i386/i386at/biosmem.h new file mode 100644 index 0000000..b32e027 --- /dev/null +++ b/i386/i386at/biosmem.h @@ -0,0 +1,84 @@ +/* + * Copyright (c) 2010-2014 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef _X86_BIOSMEM_H +#define _X86_BIOSMEM_H + +#include <kern/types.h> +#include <machine/multiboot.h> + +/* + * Address where the address of the Extended BIOS Data Area segment can be + * found. + */ +#define BIOSMEM_EBDA_PTR 0x40e + +/* + * Significant low memory addresses. + * + * The first 64 KiB are reserved for various reasons (e.g. to preserve BIOS + * data and to work around data corruption on some hardware). + */ +#define BIOSMEM_BASE 0x010000 +#define BIOSMEM_BASE_END 0x0a0000 +#define BIOSMEM_EXT_ROM 0x0e0000 +#define BIOSMEM_ROM 0x0f0000 +#define BIOSMEM_END 0x100000 + +/* + * Early initialization of the biosmem module. + * + * This function processes the given multiboot data for BIOS-provided + * memory information, and sets up a bootstrap physical page allocator. + * + * It is called before paging is enabled. + */ +void biosmem_bootstrap(struct multiboot_raw_info *mbi); + +/* + * Allocate contiguous physical pages during bootstrap. + * + * This function is called before paging is enabled. It should only be used + * to allocate initial page table pages. Those pages are later loaded into + * the VM system (as reserved pages) which means they can be freed like other + * regular pages. Users should fix up the type of those pages once the VM + * system is initialized. + */ +void * biosmem_bootalloc(unsigned int nr_pages); + +/* + * Return the amount of physical memory that can be directly mapped. + * + * This includes the size of both the DMA/DMA32 and DIRECTMAP segments. + */ +phys_addr_t biosmem_directmap_size(void); + +/* + * Set up physical memory based on the information obtained during bootstrap + * and load it in the VM system. + */ +void biosmem_setup(void); + +/* + * Free all usable memory. + * + * This includes ranges that weren't part of the bootstrap allocator initial + * heap, e.g. because they contained boot data. + */ +void biosmem_free_usable(void); + +#endif /* _X86_BIOSMEM_H */ diff --git a/vm/vm_page.c b/vm/vm_page.c new file mode 100644 index 0000000..cc184ca --- /dev/null +++ b/vm/vm_page.c @@ -0,0 +1,735 @@ +/* + * Copyright (c) 2010-2014 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + * + * This implementation uses the binary buddy system to manage its heap. + * Descriptions of the buddy system can be found in the following works : + * - "UNIX Internals: The New Frontiers", by Uresh Vahalia. + * - "Dynamic Storage Allocation: A Survey and Critical Review", + * by Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. + * + * In addition, this allocator uses per-CPU pools of pages for order 0 + * (i.e. single page) allocations. These pools act as caches (but are named + * differently to avoid confusion with CPU caches) that reduce contention on + * multiprocessor systems. When a pool is empty and cannot provide a page, + * it is filled by transferring multiple pages from the backend buddy system. + * The symmetric case is handled likewise. + */ + +#include <kern/assert.h> +#include <kern/init.h> +#include <kern/list.h> +#include <kern/macros.h> +#include <kern/mutex.h> +#include <kern/panic.h> +#include <kern/param.h> +#include <kern/printk.h> +#include <kern/sprintf.h> +#include <kern/stddef.h> +#include <kern/string.h> +#include <kern/thread.h> +#include <kern/types.h> +#include <machine/cpu.h> +#include <machine/pmap.h> +#include <vm/vm_kmem.h> +#include <vm/vm_page.h> + +/* + * Number of free block lists per segment. + */ +#define VM_PAGE_NR_FREE_LISTS 11 + +/* + * The size of a CPU pool is computed by dividing the number of pages in its + * containing segment by this value. + */ +#define VM_PAGE_CPU_POOL_RATIO 1024 + +/* + * Maximum number of pages in a CPU pool. + */ +#define VM_PAGE_CPU_POOL_MAX_SIZE 128 + +/* + * The transfer size of a CPU pool is computed by dividing the pool size by + * this value. + */ +#define VM_PAGE_CPU_POOL_TRANSFER_RATIO 2 + +/* + * Per-processor cache of pages. + */ +struct vm_page_cpu_pool { + struct mutex lock; + int size; + int transfer_size; + int nr_pages; + struct list pages; +} __aligned(CPU_L1_SIZE); + +/* + * Special order value for pages that aren't in a free list. Such pages are + * either allocated, or part of a free block of pages but not the head page. + */ +#define VM_PAGE_ORDER_UNLISTED ((unsigned short)-1) + +/* + * Doubly-linked list of free blocks. + */ +struct vm_page_free_list { + unsigned long size; + struct list blocks; +}; + +/* + * Segment name buffer size. + */ +#define VM_PAGE_NAME_SIZE 16 + +/* + * Segment of contiguous memory. + */ +struct vm_page_seg { + struct vm_page_cpu_pool cpu_pools[MAX_CPUS]; + + phys_addr_t start; + phys_addr_t end; + struct vm_page *pages; + struct vm_page *pages_end; + struct mutex lock; + struct vm_page_free_list free_lists[VM_PAGE_NR_FREE_LISTS]; + unsigned long nr_free_pages; +}; + +/* + * Bootstrap information about a segment. + */ +struct vm_page_boot_seg { + phys_addr_t start; + phys_addr_t end; + phys_addr_t avail_start; + phys_addr_t avail_end; +}; + +static int vm_page_is_ready __read_mostly; + +/* + * Segment table. + * + * The system supports a maximum of 4 segments : + * - DMA: suitable for DMA + * - DMA32: suitable for DMA when devices support 32-bits addressing + * - DIRECTMAP: direct physical mapping, allows direct access from + * the kernel with a simple offset translation + * - HIGHMEM: must be mapped before it can be accessed + * + * Segments are ordered by priority, 0 being the lowest priority. Their + * relative priorities are DMA < DMA32 < DIRECTMAP < HIGHMEM. Some segments + * may actually be aliases for others, e.g. if DMA is always possible from + * the direct physical mapping, DMA and DMA32 are aliases for DIRECTMAP, + * in which case the segment table contains DIRECTMAP and HIGHMEM only. + */ +static struct vm_page_seg vm_page_segs[VM_PAGE_MAX_SEGS]; + +/* + * Bootstrap segment table. + */ +static struct vm_page_boot_seg vm_page_boot_segs[VM_PAGE_MAX_SEGS] __initdata; + +/* + * Number of loaded segments. + */ +static unsigned int vm_page_segs_size __read_mostly; + +static void __init +vm_page_init(struct vm_page *page, unsigned short seg_index, phys_addr_t pa) +{ + memset(page, 0, sizeof(*page)); + page->type = VM_PAGE_RESERVED; + page->seg_index = seg_index; + page->order = VM_PAGE_ORDER_UNLISTED; + page->phys_addr = pa; +} + +void +vm_page_set_type(struct vm_page *page, unsigned int order, unsigned short type) +{ + unsigned int i, nr_pages; + + nr_pages = 1 << order; + + for (i = 0; i < nr_pages; i++) + page[i].type = type; +} + +static void __init +vm_page_free_list_init(struct vm_page_free_list *free_list) +{ + free_list->size = 0; + list_init(&free_list->blocks); +} + +static inline void +vm_page_free_list_insert(struct vm_page_free_list *free_list, + struct vm_page *page) +{ + assert(page->order == VM_PAGE_ORDER_UNLISTED); + + free_list->size++; + list_insert_head(&free_list->blocks, &page->node); +} + +static inline void +vm_page_free_list_remove(struct vm_page_free_list *free_list, + struct vm_page *page) +{ + assert(page->order != VM_PAGE_ORDER_UNLISTED); + + free_list->size--; + list_remove(&page->node); +} + +static struct vm_page * +vm_page_seg_alloc_from_buddy(struct vm_page_seg *seg, unsigned int order) +{ + struct vm_page_free_list *free_list = free_list; + struct vm_page *page, *buddy; + unsigned int i; + + assert(order < VM_PAGE_NR_FREE_LISTS); + + for (i = order; i < VM_PAGE_NR_FREE_LISTS; i++) { + free_list = &seg->free_lists[i]; + + if (free_list->size != 0) + break; + } + + if (i == VM_PAGE_NR_FREE_LISTS) + return NULL; + + page = list_first_entry(&free_list->blocks, struct vm_page, node); + vm_page_free_list_remove(free_list, page); + page->order = VM_PAGE_ORDER_UNLISTED; + + while (i > order) { + i--; + buddy = &page[1 << i]; + vm_page_free_list_insert(&seg->free_lists[i], buddy); + buddy->order = i; + } + + seg->nr_free_pages -= (1 << order); + return page; +} + +static void +vm_page_seg_free_to_buddy(struct vm_page_seg *seg, struct vm_page *page, + unsigned int order) +{ + struct vm_page *buddy; + phys_addr_t pa, buddy_pa; + unsigned int nr_pages; + + assert(page >= seg->pages); + assert(page < seg->pages_end); + assert(page->order == VM_PAGE_ORDER_UNLISTED); + assert(order < VM_PAGE_NR_FREE_LISTS); + + nr_pages = (1 << order); + pa = page->phys_addr; + + while (order < (VM_PAGE_NR_FREE_LISTS - 1)) { + buddy_pa = pa ^ vm_page_ptoa(1 << order); + + if ((buddy_pa < seg->start) || (buddy_pa >= seg->end)) + break; + + buddy = &seg->pages[vm_page_atop(buddy_pa - seg->start)]; + + if (buddy->order != order) + break; + + vm_page_free_list_remove(&seg->free_lists[order], buddy); + buddy->order = VM_PAGE_ORDER_UNLISTED; + order++; + pa &= -vm_page_ptoa(1 << order); + page = &seg->pages[vm_page_atop(pa - seg->start)]; + } + + vm_page_free_list_insert(&seg->free_lists[order], page); + page->order = order; + seg->nr_free_pages += nr_pages; +} + +static void __init +vm_page_cpu_pool_init(struct vm_page_cpu_pool *cpu_pool, int size) +{ + mutex_init(&cpu_pool->lock); + cpu_pool->size = size; + cpu_pool->transfer_size = (size + VM_PAGE_CPU_POOL_TRANSFER_RATIO - 1) + / VM_PAGE_CPU_POOL_TRANSFER_RATIO; + cpu_pool->nr_pages = 0; + list_init(&cpu_pool->pages); +} + +static inline struct vm_page_cpu_pool * +vm_page_cpu_pool_get(struct vm_page_seg *seg) +{ + return &seg->cpu_pools[cpu_id()]; +} + +static inline struct vm_page * +vm_page_cpu_pool_pop(struct vm_page_cpu_pool *cpu_pool) +{ + struct vm_page *page; + + assert(cpu_pool->nr_pages != 0); + cpu_pool->nr_pages--; + page = list_first_entry(&cpu_pool->pages, struct vm_page, node); + list_remove(&page->node); + return page; +} + +static inline void +vm_page_cpu_pool_push(struct vm_page_cpu_pool *cpu_pool, struct vm_page *page) +{ + assert(cpu_pool->nr_pages < cpu_pool->size); + cpu_pool->nr_pages++; + list_insert_head(&cpu_pool->pages, &page->node); +} + +static int +vm_page_cpu_pool_fill(struct vm_page_cpu_pool *cpu_pool, + struct vm_page_seg *seg) +{ + struct vm_page *page; + int i; + + assert(cpu_pool->nr_pages == 0); + + mutex_lock(&seg->lock); + + for (i = 0; i < cpu_pool->transfer_size; i++) { + page = vm_page_seg_alloc_from_buddy(seg, 0); + + if (page == NULL) + break; + + vm_page_cpu_pool_push(cpu_pool, page); + } + + mutex_unlock(&seg->lock); + + return i; +} + +static void +vm_page_cpu_pool_drain(struct vm_page_cpu_pool *cpu_pool, + struct vm_page_seg *seg) +{ + struct vm_page *page; + int i; + + assert(cpu_pool->nr_pages == cpu_pool->size); + + mutex_lock(&seg->lock); + + for (i = cpu_pool->transfer_size; i > 0; i--) { + page = vm_page_cpu_pool_pop(cpu_pool); + vm_page_seg_free_to_buddy(seg, page, 0); + } + + mutex_unlock(&seg->lock); +} + +static phys_addr_t __init +vm_page_seg_size(struct vm_page_seg *seg) +{ + return seg->end - seg->start; +} + +static int __init +vm_page_seg_compute_pool_size(struct vm_page_seg *seg) +{ + phys_addr_t size; + + size = vm_page_atop(vm_page_seg_size(seg)) / VM_PAGE_CPU_POOL_RATIO; + + if (size == 0) + size = 1; + else if (size > VM_PAGE_CPU_POOL_MAX_SIZE) + size = VM_PAGE_CPU_POOL_MAX_SIZE; + + return size; +} + +static void __init +vm_page_seg_init(struct vm_page_seg *seg, phys_addr_t start, phys_addr_t end, + struct vm_page *pages) +{ + phys_addr_t pa; + int pool_size; + unsigned int i; + + seg->start = start; + seg->end = end; + pool_size = vm_page_seg_compute_pool_size(seg); + + for (i = 0; i < ARRAY_SIZE(seg->cpu_pools); i++) + vm_page_cpu_pool_init(&seg->cpu_pools[i], pool_size); + + seg->pages = pages; + seg->pages_end = pages + vm_page_atop(vm_page_seg_size(seg)); + mutex_init(&seg->lock); + + for (i = 0; i < ARRAY_SIZE(seg->free_lists); i++) + vm_page_free_list_init(&seg->free_lists[i]); + + seg->nr_free_pages = 0; + i = seg - vm_page_segs; + + for (pa = seg->start; pa < seg->end; pa += PAGE_SIZE) + vm_page_init(&pages[vm_page_atop(pa - seg->start)], i, pa); +} + +static struct vm_page * +vm_page_seg_alloc(struct vm_page_seg *seg, unsigned int order, + unsigned short type) +{ + struct vm_page_cpu_pool *cpu_pool; + struct vm_page *page; + int filled; + + assert(order < VM_PAGE_NR_FREE_LISTS); + + if (order == 0) { + thread_pin(); + cpu_pool = vm_page_cpu_pool_get(seg); + mutex_lock(&cpu_pool->lock); + + if (cpu_pool->nr_pages == 0) { + filled = vm_page_cpu_pool_fill(cpu_pool, seg); + + if (!filled) { + mutex_unlock(&cpu_pool->lock); + thread_unpin(); + return NULL; + } + } + + page = vm_page_cpu_pool_pop(cpu_pool); + mutex_unlock(&cpu_pool->lock); + thread_unpin(); + } else { + mutex_lock(&seg->lock); + page = vm_page_seg_alloc_from_buddy(seg, order); + mutex_unlock(&seg->lock); + } + + assert(page->type == VM_PAGE_FREE); + vm_page_set_type(page, order, type); + return page; +} + +static void +vm_page_seg_free(struct vm_page_seg *seg, struct vm_page *page, + unsigned int order) +{ + struct vm_page_cpu_pool *cpu_pool; + + assert(page->type != VM_PAGE_FREE); + assert(order < VM_PAGE_NR_FREE_LISTS); + + vm_page_set_type(page, order, VM_PAGE_FREE); + + if (order == 0) { + thread_pin(); + cpu_pool = vm_page_cpu_pool_get(seg); + mutex_lock(&cpu_pool->lock); + + if (cpu_pool->nr_pages == cpu_pool->size) + vm_page_cpu_pool_drain(cpu_pool, seg); + + vm_page_cpu_pool_push(cpu_pool, page); + mutex_unlock(&cpu_pool->lock); + thread_unpin(); + } else { + mutex_lock(&seg->lock); + vm_page_seg_free_to_buddy(seg, page, order); + mutex_unlock(&seg->lock); + } +} + +void __init +vm_page_load(unsigned int seg_index, phys_addr_t start, phys_addr_t end, + phys_addr_t avail_start, phys_addr_t avail_end) +{ + struct vm_page_boot_seg *seg; + + assert(seg_index < ARRAY_SIZE(vm_page_boot_segs)); + assert(vm_page_aligned(start)); + assert(vm_page_aligned(end)); + assert(vm_page_aligned(avail_start)); + assert(vm_page_aligned(avail_end)); + assert(start < end); + assert(start <= avail_start); + assert(avail_end <= end); + assert(vm_page_segs_size < ARRAY_SIZE(vm_page_boot_segs)); + + seg = &vm_page_boot_segs[seg_index]; + seg->start = start; + seg->end = end; + seg->avail_start = avail_start; + seg->avail_end = avail_end; + vm_page_segs_size++; +} + +int +vm_page_ready(void) +{ + return vm_page_is_ready; +} + +static unsigned int +vm_page_select_alloc_seg(unsigned int selector) +{ + unsigned int seg_index; + + switch (selector) { + case VM_PAGE_SEL_DMA: + seg_index = VM_PAGE_SEG_DMA; + break; + case VM_PAGE_SEL_DMA32: + seg_index = VM_PAGE_SEG_DMA32; + break; + case VM_PAGE_SEL_DIRECTMAP: + seg_index = VM_PAGE_SEG_DIRECTMAP; + break; + case VM_PAGE_SEL_HIGHMEM: + seg_index = VM_PAGE_SEG_HIGHMEM; + break; + default: + panic("vm_page: invalid selector"); + } + + return MIN(vm_page_segs_size - 1, seg_index); +} + +static int __init +vm_page_boot_seg_loaded(const struct vm_page_boot_seg *seg) +{ + return (seg->end != 0); +} + +static void __init +vm_page_check_boot_segs(void) +{ + unsigned int i; + int expect_loaded; + + if (vm_page_segs_size == 0) + panic("vm_page: no physical memory loaded"); + + for (i = 0; i < ARRAY_SIZE(vm_page_boot_segs); i++) { + expect_loaded = (i < vm_page_segs_size); + + if (vm_page_boot_seg_loaded(&vm_page_boot_segs[i]) == expect_loaded) + continue; + + panic("vm_page: invalid boot segment table"); + } +} + +static phys_addr_t __init +vm_page_boot_seg_size(struct vm_page_boot_seg *seg) +{ + return seg->end - seg->start; +} + +static phys_addr_t __init +vm_page_boot_seg_avail_size(struct vm_page_boot_seg *seg) +{ + return seg->avail_end - seg->avail_start; +} + +static void * __init +vm_page_bootalloc(size_t size) +{ + struct vm_page_boot_seg *seg; + phys_addr_t pa; + unsigned int i; + + for (i = vm_page_select_alloc_seg(VM_PAGE_SEL_DIRECTMAP); + i < vm_page_segs_size; + i--) { + seg = &vm_page_boot_segs[i]; + + if (size <= vm_page_boot_seg_avail_size(seg)) { + pa = seg->avail_start; + seg->avail_start += vm_page_round(size); + return (void *)vm_page_direct_va(pa); + } + } + + panic("vm_page: no physical memory available"); +} + +void __init +vm_page_setup(void) +{ + struct vm_page_boot_seg *boot_seg; + struct vm_page_seg *seg; + struct vm_page *table, *page, *end; + size_t nr_pages, table_size; + unsigned long va; + unsigned int i; + phys_addr_t pa; + + vm_page_check_boot_segs(); + + /* + * Compute the page table size. + */ + nr_pages = 0; + + for (i = 0; i < vm_page_segs_size; i++) + nr_pages += vm_page_atop(vm_page_boot_seg_size(&vm_page_boot_segs[i])); + + table_size = vm_page_round(nr_pages * sizeof(struct vm_page)); + printk("vm_page: page table size: %zu entries (%zuk)\n", nr_pages, + table_size >> 10); + table = vm_page_bootalloc(table_size); + va = (unsigned long)table; + + /* + * Initialize the segments, associating them to the page table. When + * the segments are initialized, all their pages are set allocated. + * Pages are then released, which populates the free lists. + */ + for (i = 0; i < vm_page_segs_size; i++) { + seg = &vm_page_segs[i]; + boot_seg = &vm_page_boot_segs[i]; + vm_page_seg_init(seg, boot_seg->start, boot_seg->end, table); + page = seg->pages + vm_page_atop(boot_seg->avail_start + - boot_seg->start); + end = seg->pages + vm_page_atop(boot_seg->avail_end + - boot_seg->start); + + while (page < end) { + page->type = VM_PAGE_FREE; + vm_page_seg_free_to_buddy(seg, page, 0); + page++; + } + + table += vm_page_atop(vm_page_seg_size(seg)); + } + + while (va < (unsigned long)table) { + pa = vm_page_direct_pa(va); + page = vm_page_lookup(pa); + assert((page != NULL) && (page->type == VM_PAGE_RESERVED)); + page->type = VM_PAGE_TABLE; + va += PAGE_SIZE; + } + + vm_page_is_ready = 1; +} + +void __init +vm_page_manage(struct vm_page *page) +{ + assert(page->seg_index < ARRAY_SIZE(vm_page_segs)); + assert(page->type == VM_PAGE_RESERVED); + + vm_page_set_type(page, 0, VM_PAGE_FREE); + vm_page_seg_free_to_buddy(&vm_page_segs[page->seg_index], page, 0); +} + +struct vm_page * +vm_page_lookup(phys_addr_t pa) +{ + struct vm_page_seg *seg; + unsigned int i; + + for (i = 0; i < vm_page_segs_size; i++) { + seg = &vm_page_segs[i]; + + if ((pa >= seg->start) && (pa < seg->end)) + return &seg->pages[vm_page_atop(pa - seg->start)]; + } + + return NULL; +} + +struct vm_page * +vm_page_alloc(unsigned int order, unsigned int selector, unsigned short type) +{ + struct vm_page *page; + unsigned int i; + + for (i = vm_page_select_alloc_seg(selector); i < vm_page_segs_size; i--) { + page = vm_page_seg_alloc(&vm_page_segs[i], order, type); + + if (page != NULL) + return page; + } + + if (type == VM_PAGE_PMAP) + panic("vm_page: unable to allocate pmap page"); + + return NULL; +} + +void +vm_page_free(struct vm_page *page, unsigned int order) +{ + assert(page->seg_index < ARRAY_SIZE(vm_page_segs)); + + vm_page_seg_free(&vm_page_segs[page->seg_index], page, order); +} + +const char * +vm_page_seg_name(unsigned int seg_index) +{ + /* Don't use a switch statement since segments can be aliased */ + if (seg_index == VM_PAGE_SEG_HIGHMEM) + return "HIGHMEM"; + else if (seg_index == VM_PAGE_SEG_DIRECTMAP) + return "DIRECTMAP"; + else if (seg_index == VM_PAGE_SEG_DMA32) + return "DMA32"; + else if (seg_index == VM_PAGE_SEG_DMA) + return "DMA"; + else + panic("vm_page: invalid segment index"); +} + +void +vm_page_info(void) +{ + struct vm_page_seg *seg; + unsigned long pages; + unsigned int i; + + for (i = 0; i < vm_page_segs_size; i++) { + seg = &vm_page_segs[i]; + pages = (unsigned long)(seg->pages_end - seg->pages); + printk("vm_page: %s: pages: %lu (%luM), free: %lu (%luM)\n", + vm_page_seg_name(i), pages, pages >> (20 - PAGE_SHIFT), + seg->nr_free_pages, seg->nr_free_pages >> (20 - PAGE_SHIFT)); + } +} diff --git a/vm/vm_page.h b/vm/vm_page.h index dd571e2..23c8c47 100644 --- a/vm/vm_page.h +++ b/vm/vm_page.h @@ -1,315 +1,195 @@ -/* - * Mach Operating System - * Copyright (c) 1993-1988 Carnegie Mellon University - * All Rights Reserved. - * - * Permission to use, copy, modify and distribute this software and its - * documentation is hereby granted, provided that both the copyright - * notice and this permission notice appear in all copies of the - * software, derivative works or modified versions, and any portions - * thereof, and that both notices appear in supporting documentation. - * - * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" - * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR - * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. - * - * Carnegie Mellon requests users of this software to return to - * - * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU - * School of Computer Science - * Carnegie Mellon University - * Pittsburgh PA 15213-3890 - * - * any improvements or extensions that they make and grant Carnegie Mellon - * the rights to redistribute these changes. - */ /* - * File: vm/vm_page.h - * Author: Avadis Tevanian, Jr., Michael Wayne Young - * Date: 1985 + * Copyright (c) 2010-2014 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. * - * Resident memory system definitions. + * + * Physical page management. */ -#ifndef _VM_VM_PAGE_H_ -#define _VM_VM_PAGE_H_ - -#include <mach/boolean.h> -#include <mach/vm_prot.h> -#include <mach/vm_param.h> -#include <vm/vm_object.h> -#include <vm/vm_types.h> -#include <kern/queue.h> -#include <kern/lock.h> +#ifndef _VM_VM_PAGE_H +#define _VM_VM_PAGE_H +#include <kern/assert.h> +#include <kern/list.h> +#include <kern/log2.h> #include <kern/macros.h> -#include <kern/sched_prim.h> /* definitions of wait/wakeup */ +//#include <kern/param.h> +//#include <kern/stddef.h> +//#include <kern/types.h> +#include <machine/pmap.h> -#if MACH_VM_DEBUG -#include <mach_debug/hash_info.h> -#endif +/* + * Address/page conversion and rounding macros (not inline functions to + * be easily usable on both virtual and physical addresses, which may not + * have the same type size). + */ +#define vm_page_atop(addr) ((addr) >> PAGE_SHIFT) +#define vm_page_ptoa(page) ((page) << PAGE_SHIFT) +#define vm_page_trunc(addr) P2ALIGN(addr, PAGE_SIZE) +#define vm_page_round(addr) P2ROUND(addr, PAGE_SIZE) +#define vm_page_aligned(addr) P2ALIGNED(addr, PAGE_SIZE) /* - * Management of resident (logical) pages. - * - * A small structure is kept for each resident - * page, indexed by page number. Each structure - * is an element of several lists: - * - * A hash table bucket used to quickly - * perform object/offset lookups - * - * A list of all pages for a given object, - * so they can be quickly deactivated at - * time of deallocation. + * Segment selectors. * - * An ordered list of pages due for pageout. - * - * In addition, the structure contains the object - * and offset to which this page belongs (for pageout), - * and sundry status bits. + * Selector-to-segment-list translation table : + * DMA DMA + * DMA32 DMA32 DMA + * DIRECTMAP DIRECTMAP DMA32 DMA + * HIGHMEM HIGHMEM DIRECTMAP DMA32 DMA + */ +#define VM_PAGE_SEL_DMA 0 +#define VM_PAGE_SEL_DMA32 1 +#define VM_PAGE_SEL_DIRECTMAP 2 +#define VM_PAGE_SEL_HIGHMEM 3 + +/* + * Page usage types. * - * Fields in this structure are locked either by the lock on the - * object that the page belongs to (O) or by the lock on the page - * queues (P). [Some fields require that both locks be held to - * change that field; holding either lock is sufficient to read.] + * Failing to allocate pmap pages will cause a kernel panic. + * TODO Obviously, this needs to be addressed, e.g. with a reserved pool of + * pages. */ +#define VM_PAGE_FREE 0 /* Page unused */ +#define VM_PAGE_RESERVED 1 /* Page reserved at boot time */ +#define VM_PAGE_TABLE 2 /* Page is part of the page table */ +#define VM_PAGE_PMAP 3 /* Page stores pmap-specific data */ +#define VM_PAGE_KMEM 4 /* Page is part of a kmem slab */ +#define VM_PAGE_OBJECT 5 /* Page is part of a VM object */ +#define VM_PAGE_KERNEL 6 /* Type for generic kernel allocations */ +/* + * Physical page descriptor. + */ struct vm_page { - queue_chain_t pageq; /* queue info for FIFO - * queue or free list (P) */ - queue_chain_t listq; /* all pages in same object (O) */ - struct vm_page *next; /* VP bucket link (O) */ - - vm_object_t object; /* which object am I in (O,P) */ - vm_offset_t offset; /* offset into that object (O,P) */ - - unsigned int wire_count:15, /* how many wired down maps use me? - (O&P) */ - /* boolean_t */ inactive:1, /* page is in inactive list (P) */ - active:1, /* page is in active list (P) */ - laundry:1, /* page is being cleaned now (P)*/ - free:1, /* page is on free list (P) */ - reference:1, /* page has been used (P) */ - external:1, /* page considered external (P) */ - extcounted:1, /* page counted in ext counts (P) */ - busy:1, /* page is in transit (O) */ - wanted:1, /* someone is waiting for page (O) */ - tabled:1, /* page is in VP table (O) */ - fictitious:1, /* Physical page doesn't exist (O) */ - private:1, /* Page should not be returned to - * the free list (O) */ - absent:1, /* Data has been requested, but is - * not yet available (O) */ - error:1, /* Data manager was unable to provide - * data due to error (O) */ - dirty:1, /* Page must be cleaned (O) */ - precious:1, /* Page is precious; data must be - * returned even if clean (O) */ - overwriting:1; /* Request to unlock has been made - * without having data. (O) - * [See vm_object_overwrite] */ - - vm_offset_t phys_addr; /* Physical address of page, passed - * to pmap_enter (read-only) */ - vm_prot_t page_lock; /* Uses prohibited by data manager (O) */ - vm_prot_t unlock_request; /* Outstanding unlock request (O) */ + struct list node; + unsigned short type; + unsigned short seg_index; + unsigned short order; + phys_addr_t phys_addr; + void *slab_priv; }; +static inline unsigned short +vm_page_type(const struct vm_page *page) +{ + return page->type; +} + +void vm_page_set_type(struct vm_page *page, unsigned int order, + unsigned short type); + +static inline unsigned int +vm_page_order(size_t size) +{ + return iorder2(vm_page_atop(vm_page_round(size))); +} + +static inline phys_addr_t +vm_page_to_pa(const struct vm_page *page) +{ + return page->phys_addr; +} + +static inline unsigned long +vm_page_direct_va(phys_addr_t pa) +{ + assert(pa < VM_PAGE_DIRECTMAP_LIMIT); + return ((unsigned long)pa + VM_MIN_DIRECTMAP_ADDRESS); +} + +static inline phys_addr_t +vm_page_direct_pa(unsigned long va) +{ + assert(va >= VM_MIN_DIRECTMAP_ADDRESS); + assert(va < VM_MAX_DIRECTMAP_ADDRESS); + return (va - VM_MIN_DIRECTMAP_ADDRESS); +} + +static inline void * +vm_page_direct_ptr(const struct vm_page *page) +{ + return (void *)vm_page_direct_va(vm_page_to_pa(page)); +} + /* - * For debugging, this macro can be defined to perform - * some useful check on a page structure. + * Load physical memory into the vm_page module at boot time. + * + * The avail_start and avail_end parameters are used to maintain a simple + * heap for bootstrap allocations. + * + * All addresses must be page-aligned. Segments can be loaded in any order. */ +void vm_page_load(unsigned int seg_index, phys_addr_t start, phys_addr_t end, + phys_addr_t avail_start, phys_addr_t avail_end); -#define VM_PAGE_CHECK(mem) +/* + * Return true if the vm_page module is completely initialized, false + * otherwise, in which case only vm_page_bootalloc() can be used for + * allocations. + */ +int vm_page_ready(void); /* - * Each pageable resident page falls into one of three lists: + * Set up the vm_page module. + * + * Architecture-specific code must have loaded segments before calling this + * function. Segments must comply with the selector-to-segment-list table, + * e.g. HIGHMEM is loaded if and only if DIRECTMAP, DMA32 and DMA are loaded, + * notwithstanding segment aliasing. * - * free - * Available for allocation now. - * inactive - * Not referenced in any map, but still has an - * object/offset-page mapping, and may be dirty. - * This is the list of pages that should be - * paged out next. - * active - * A list of pages which have been placed in - * at least one physical map. This list is - * ordered, in LRU-like fashion. + * Once this function returns, the vm_page module is ready, and normal + * allocation functions can be used. */ - -extern -vm_page_t vm_page_queue_free; /* memory free queue */ -extern -vm_page_t vm_page_queue_fictitious; /* fictitious free queue */ -extern -queue_head_t vm_page_queue_active; /* active memory queue */ -extern -queue_head_t vm_page_queue_inactive; /* inactive memory queue */ - -extern -int vm_page_free_count; /* How many pages are free? */ -extern -int vm_page_fictitious_count;/* How many fictitious pages are free? */ -extern -int vm_page_active_count; /* How many pages are active? */ -extern -int vm_page_inactive_count; /* How many pages are inactive? */ -extern -int vm_page_wire_count; /* How many pages are wired? */ -extern -int vm_page_free_target; /* How many do we want free? */ -extern -int vm_page_free_min; /* When to wakeup pageout */ -extern -int vm_page_inactive_target;/* How many do we want inactive? */ -extern -int vm_page_free_reserved; /* How many pages reserved to do pageout */ -extern -int vm_page_laundry_count; /* How many pages being laundered? */ -extern -int vm_page_external_limit; /* Max number of pages for external objects */ - -/* Only objects marked with the extcounted bit are included in this total. - Pages which we scan for possible pageout, but which are not actually - dirty, don't get considered against the external page limits any more - in this way. */ -extern -int vm_page_external_count; /* How many pages for external objects? */ - - - -struct lock vm_page_queue_lock; /* lock on active and inactive page queues */ -decl_simple_lock_data(extern,vm_page_queue_free_lock) - /* lock on free page queue */ - -extern unsigned int vm_page_free_wanted; - /* how many threads are waiting for memory */ - -extern vm_offset_t vm_page_fictitious_addr; - /* (fake) phys_addr of fictitious pages */ - -extern void vm_page_bootstrap( - vm_offset_t *startp, - vm_offset_t *endp); -extern void vm_page_module_init(void); - -extern void vm_page_create( - vm_offset_t start, - vm_offset_t end); -extern vm_page_t vm_page_lookup( - vm_object_t object, - vm_offset_t offset); -extern vm_page_t vm_page_grab_fictitious(void); -extern void vm_page_release_fictitious(vm_page_t); -extern boolean_t vm_page_convert(vm_page_t, boolean_t); -extern void vm_page_more_fictitious(void); -extern vm_page_t vm_page_grab(boolean_t); -extern void vm_page_release(vm_page_t, boolean_t); -extern void vm_page_wait(void (*)(void)); -extern vm_page_t vm_page_alloc( - vm_object_t object, - vm_offset_t offset); -extern void vm_page_init( - vm_page_t mem, - vm_offset_t phys_addr); -extern void vm_page_free(vm_page_t); -extern void vm_page_activate(vm_page_t); -extern void vm_page_deactivate(vm_page_t); -extern void vm_page_rename( - vm_page_t mem, - vm_object_t new_object, - vm_offset_t new_offset); -extern void vm_page_insert( - vm_page_t mem, - vm_object_t object, - vm_offset_t offset); -extern void vm_page_remove( - vm_page_t mem); - -extern void vm_page_zero_fill(vm_page_t); -extern void vm_page_copy(vm_page_t src_m, vm_page_t dest_m); - -extern void vm_page_wire(vm_page_t); -extern void vm_page_unwire(vm_page_t); - -#if MACH_VM_DEBUG -extern unsigned int vm_page_info( - hash_info_bucket_t *info, - unsigned int count); -#endif +void vm_page_setup(void); /* - * Functions implemented as macros + * Make the given page managed by the vm_page module. + * + * If additional memory can be made usable after the VM system is initialized, + * it should be reported through this function. */ - -#define PAGE_ASSERT_WAIT(m, interruptible) \ - MACRO_BEGIN \ - (m)->wanted = TRUE; \ - assert_wait((event_t) (m), (interruptible)); \ - MACRO_END - -#define PAGE_WAKEUP_DONE(m) \ - MACRO_BEGIN \ - (m)->busy = FALSE; \ - if ((m)->wanted) { \ - (m)->wanted = FALSE; \ - thread_wakeup(((event_t) m)); \ - } \ - MACRO_END - -#define PAGE_WAKEUP(m) \ - MACRO_BEGIN \ - if ((m)->wanted) { \ - (m)->wanted = FALSE; \ - thread_wakeup((event_t) (m)); \ - } \ - MACRO_END - -#define VM_PAGE_FREE(p) \ - MACRO_BEGIN \ - vm_page_lock_queues(); \ - vm_page_free(p); \ - vm_page_unlock_queues(); \ - MACRO_END +void vm_page_manage(struct vm_page *page); /* - * Macro to be used in place of pmap_enter() + * Return the page descriptor for the given physical address. */ +struct vm_page * vm_page_lookup(phys_addr_t pa); -#define PMAP_ENTER(pmap, virtual_address, page, protection, wired) \ - MACRO_BEGIN \ - pmap_enter( \ - (pmap), \ - (virtual_address), \ - (page)->phys_addr, \ - (protection) & ~(page)->page_lock, \ - (wired) \ - ); \ - MACRO_END +/* + * Allocate a block of 2^order physical pages. + * + * The selector is used to determine the segments from which allocation can + * be attempted. + */ +struct vm_page * vm_page_alloc(unsigned int order, unsigned int selector, + unsigned short type); -#define VM_PAGE_WAIT(continuation) vm_page_wait(continuation) +/* + * Release a block of 2^order physical pages. + */ +void vm_page_free(struct vm_page *page, unsigned int order); -#define vm_page_lock_queues() lock_write(&vm_page_queue_lock) -#define vm_page_unlock_queues() lock_write_done(&vm_page_queue_lock) -#define have_vm_page_queue_lock() have_write_lock(&vm_page_queue_lock) +/* + * Return the name of the given segment. + */ +const char * vm_page_seg_name(unsigned int seg_index); -#define VM_PAGE_QUEUES_REMOVE(mem) \ - MACRO_BEGIN \ - if (mem->active) { \ - queue_remove(&vm_page_queue_active, \ - mem, vm_page_t, pageq); \ - mem->active = FALSE; \ - vm_page_active_count--; \ - } \ - \ - if (mem->inactive) { \ - queue_remove(&vm_page_queue_inactive, \ - mem, vm_page_t, pageq); \ - mem->inactive = FALSE; \ - vm_page_inactive_count--; \ - } \ - MACRO_END +/* + * Display internal information about the module. + */ +void vm_page_info(void); -#endif /* _VM_VM_PAGE_H_ */ +#endif /* _VM_VM_PAGE_H */ |