nuclear@17: #include <stdio.h>
nuclear@17: #include <string.h>
nuclear@17: #include <inttypes.h>
nuclear@52: #include <assert.h>
nuclear@52: #include "config.h"
nuclear@17: #include "vm.h"
nuclear@17: #include "intr.h"
nuclear@17: #include "mem.h"
nuclear@17: #include "panic.h"
nuclear@52: #include "proc.h"
nuclear@17: 
nuclear@17: #define IDMAP_START		0xa0000
nuclear@17: 
nuclear@24: #define PGDIR_ADDR		0xfffff000
nuclear@24: #define PGTBL_BASE		(0xffffffff - 4096 * 1024 + 1)
nuclear@24: #define PGTBL(x)		((uint32_t*)(PGTBL_BASE + PGSIZE * (x)))
nuclear@24: 
nuclear@17: #define ATTR_PGDIR_MASK	0x3f
nuclear@17: #define ATTR_PGTBL_MASK	0x1ff
nuclear@17: 
nuclear@17: #define PAGEFAULT		14
nuclear@17: 
nuclear@22: 
nuclear@22: struct page_range {
nuclear@22: 	int start, end;
nuclear@22: 	struct page_range *next;
nuclear@22: };
nuclear@22: 
nuclear@22: /* defined in vm-asm.S */
nuclear@22: void enable_paging(void);
nuclear@23: void disable_paging(void);
nuclear@23: int get_paging_status(void);
nuclear@22: void set_pgdir_addr(uint32_t addr);
nuclear@23: void flush_tlb(void);
nuclear@23: void flush_tlb_addr(uint32_t addr);
nuclear@23: #define flush_tlb_page(p)	flush_tlb_addr(PAGE_TO_ADDR(p))
nuclear@22: uint32_t get_fault_addr(void);
nuclear@22: 
nuclear@23: static void coalesce(struct page_range *low, struct page_range *mid, struct page_range *high);
nuclear@52: static void pgfault(int inum);
nuclear@69: static int copy_on_write(struct vm_page *page);
nuclear@22: static struct page_range *alloc_node(void);
nuclear@22: static void free_node(struct page_range *node);
nuclear@22: 
nuclear@22: /* page directory */
nuclear@22: static uint32_t *pgdir;
nuclear@22: 
nuclear@22: /* 2 lists of free ranges, for kernel memory and user memory */
nuclear@22: static struct page_range *pglist[2];
nuclear@22: /* list of free page_range structures to be used in the lists */
nuclear@22: static struct page_range *node_pool;
nuclear@23: /* the first page range for the whole kernel address space, to get things started */
nuclear@23: static struct page_range first_node;
nuclear@22: 
nuclear@22: 
nuclear@26: void init_vm(void)
nuclear@17: {
nuclear@19: 	uint32_t idmap_end;
nuclear@47: 	int i, kmem_start_pg, pgtbl_base_pg;
nuclear@19: 
nuclear@23: 	/* setup the page tables */
nuclear@18: 	pgdir = (uint32_t*)alloc_phys_page();
nuclear@23: 	memset(pgdir, 0, PGSIZE);
nuclear@24: 	set_pgdir_addr((uint32_t)pgdir);
nuclear@17: 
nuclear@17: 	/* map the video memory and kernel code 1-1 */
nuclear@19: 	get_kernel_mem_range(0, &idmap_end);
nuclear@19: 	map_mem_range(IDMAP_START, idmap_end - IDMAP_START, IDMAP_START, 0);
nuclear@17: 
nuclear@24: 	/* make the last page directory entry point to the page directory */
nuclear@68: 	pgdir[1023] = ((uint32_t)pgdir & PGENT_ADDR_MASK) | PG_PRESENT;
nuclear@24: 	pgdir = (uint32_t*)PGDIR_ADDR;
nuclear@24: 
nuclear@23: 	/* set the page fault handler */
nuclear@17: 	interrupt(PAGEFAULT, pgfault);
nuclear@17: 
nuclear@23: 	/* we can enable paging now */
nuclear@17: 	enable_paging();
nuclear@23: 
nuclear@23: 	/* initialize the virtual page allocator */
nuclear@23: 	node_pool = 0;
nuclear@23: 
nuclear@47: 	kmem_start_pg = ADDR_TO_PAGE(KMEM_START);
nuclear@47: 	pgtbl_base_pg = ADDR_TO_PAGE(PGTBL_BASE);
nuclear@47: 
nuclear@47: 	first_node.start = kmem_start_pg;
nuclear@47: 	first_node.end = pgtbl_base_pg;
nuclear@23: 	first_node.next = 0;
nuclear@23: 	pglist[MEM_KERNEL] = &first_node;
nuclear@23: 
nuclear@23: 	pglist[MEM_USER] = alloc_node();
nuclear@26: 	pglist[MEM_USER]->start = ADDR_TO_PAGE(idmap_end);
nuclear@47: 	pglist[MEM_USER]->end = kmem_start_pg;
nuclear@23: 	pglist[MEM_USER]->next = 0;
nuclear@47: 
nuclear@47: 	/* temporaroly map something into every 1024th page of the kernel address
nuclear@47: 	 * space to force pre-allocation of all the kernel page-tables
nuclear@47: 	 */
nuclear@47: 	for(i=kmem_start_pg; i<pgtbl_base_pg; i+=1024) {
nuclear@47: 		/* if there's already something mapped here, leave it alone */
nuclear@47: 		if(virt_to_phys_page(i) == -1) {
nuclear@47: 			map_page(i, 0, 0);
nuclear@47: 			unmap_page(i);
nuclear@47: 		}
nuclear@47: 	}
nuclear@17: }
nuclear@17: 
nuclear@23: /* if ppage == -1 we allocate a physical page by calling alloc_phys_page */
nuclear@23: int map_page(int vpage, int ppage, unsigned int attr)
nuclear@17: {
nuclear@17: 	uint32_t *pgtbl;
nuclear@25: 	int diridx, pgidx, pgon, intr_state;
nuclear@69: 	struct process *p;
nuclear@25: 
nuclear@25: 	intr_state = get_intr_state();
nuclear@25: 	disable_intr();
nuclear@23: 
nuclear@23: 	pgon = get_paging_status();
nuclear@23: 
nuclear@23: 	if(ppage < 0) {
nuclear@23: 		uint32_t addr = alloc_phys_page();
nuclear@23: 		if(!addr) {
nuclear@25: 			set_intr_state(intr_state);
nuclear@23: 			return -1;
nuclear@23: 		}
nuclear@23: 		ppage = ADDR_TO_PAGE(addr);
nuclear@23: 	}
nuclear@23: 
nuclear@23: 	diridx = PAGE_TO_PGTBL(vpage);
nuclear@23: 	pgidx = PAGE_TO_PGTBL_PG(vpage);
nuclear@17: 
nuclear@17: 	if(!(pgdir[diridx] & PG_PRESENT)) {
nuclear@55: 		/* no page table present, we must allocate one */
nuclear@17: 		uint32_t addr = alloc_phys_page();
nuclear@55: 
nuclear@55: 		/* make sure all page directory entries in the below the kernel vm
nuclear@55: 		 * split have the user and writable bits set, otherwise further user
nuclear@55: 		 * mappings on the same 4mb block will be unusable in user space.
nuclear@55: 		 */
nuclear@55: 		unsigned int pgdir_attr = attr;
nuclear@55: 		if(vpage < ADDR_TO_PAGE(KMEM_START)) {
nuclear@55: 			pgdir_attr |= PG_USER | PG_WRITABLE;
nuclear@55: 		}
nuclear@55: 
nuclear@55: 		pgdir[diridx] = addr | (pgdir_attr & ATTR_PGDIR_MASK) | PG_PRESENT;
nuclear@24: 
nuclear@24: 		pgtbl = pgon ? PGTBL(diridx) : (uint32_t*)addr;
nuclear@18: 		memset(pgtbl, 0, PGSIZE);
nuclear@17: 	} else {
nuclear@24: 		if(pgon) {
nuclear@24: 			pgtbl = PGTBL(diridx);
nuclear@24: 		} else {
nuclear@68: 			pgtbl = (uint32_t*)(pgdir[diridx] & PGENT_ADDR_MASK);
nuclear@24: 		}
nuclear@17: 	}
nuclear@17: 
nuclear@17: 	pgtbl[pgidx] = PAGE_TO_ADDR(ppage) | (attr & ATTR_PGTBL_MASK) | PG_PRESENT;
nuclear@23: 	flush_tlb_page(vpage);
nuclear@23: 
nuclear@69: 	/* if it's a new *user* mapping, and there is a current process, update the vmmap */
nuclear@69: 	if((attr & PG_USER) && (p = get_current_proc())) {
nuclear@69: 		struct vm_page *page;
nuclear@69: 
nuclear@69: 		if(!(page = get_vm_page_proc(p, vpage))) {
nuclear@69: 			if(!(page = malloc(sizeof *page))) {
nuclear@69: 				panic("map_page: failed to allocate new vm_page structure");
nuclear@69: 			}
nuclear@69: 			page->vpage = vpage;
nuclear@69: 			page->ppage = ppage;
nuclear@69: 			page->flags = (attr & ATTR_PGTBL_MASK) | PG_PRESENT;
nuclear@69: 			page->nref = 1;
nuclear@69: 
nuclear@69: 			rb_inserti(&p->vmmap, vpage, page);
nuclear@69: 		} else {
nuclear@69: 			/* otherwise just update the mapping */
nuclear@69: 			page->ppage = ppage;
nuclear@69: 
nuclear@69: 			/* XXX don't touch the flags, as that's how we implement CoW
nuclear@69: 			 * by changing the mapping without affecting the vm_page
nuclear@69: 			 */
nuclear@69: 		}
nuclear@69: 	}
nuclear@69: 
nuclear@25: 	set_intr_state(intr_state);
nuclear@23: 	return 0;
nuclear@17: }
nuclear@17: 
nuclear@43: int unmap_page(int vpage)
nuclear@17: {
nuclear@17: 	uint32_t *pgtbl;
nuclear@43: 	int res = 0;
nuclear@17: 	int diridx = PAGE_TO_PGTBL(vpage);
nuclear@17: 	int pgidx = PAGE_TO_PGTBL_PG(vpage);
nuclear@17: 
nuclear@25: 	int intr_state = get_intr_state();
nuclear@25: 	disable_intr();
nuclear@25: 
nuclear@17: 	if(!(pgdir[diridx] & PG_PRESENT)) {
nuclear@17: 		goto err;
nuclear@17: 	}
nuclear@26: 	pgtbl = PGTBL(diridx);
nuclear@17: 
nuclear@17: 	if(!(pgtbl[pgidx] & PG_PRESENT)) {
nuclear@17: 		goto err;
nuclear@17: 	}
nuclear@17: 	pgtbl[pgidx] = 0;
nuclear@23: 	flush_tlb_page(vpage);
nuclear@17: 
nuclear@25: 	if(0) {
nuclear@17: err:
nuclear@25: 		printf("unmap_page(%d): page already not mapped\n", vpage);
nuclear@43: 		res = -1;
nuclear@25: 	}
nuclear@25: 	set_intr_state(intr_state);
nuclear@43: 	return res;
nuclear@17: }
nuclear@17: 
nuclear@22: /* if ppg_start is -1, we allocate physical pages to map with alloc_phys_page() */
nuclear@23: int map_page_range(int vpg_start, int pgcount, int ppg_start, unsigned int attr)
nuclear@17: {
nuclear@23: 	int i, phys_pg;
nuclear@17: 
nuclear@17: 	for(i=0; i<pgcount; i++) {
nuclear@26: 		phys_pg = ppg_start < 0 ? -1 : ppg_start + i;
nuclear@23: 		map_page(vpg_start + i, phys_pg, attr);
nuclear@17: 	}
nuclear@23: 	return 0;
nuclear@17: }
nuclear@17: 
nuclear@43: int unmap_page_range(int vpg_start, int pgcount)
nuclear@43: {
nuclear@43: 	int i, res = 0;
nuclear@43: 
nuclear@43: 	for(i=0; i<pgcount; i++) {
nuclear@43: 		if(unmap_page(vpg_start + i) == -1) {
nuclear@43: 			res = -1;
nuclear@43: 		}
nuclear@43: 	}
nuclear@43: 	return res;
nuclear@43: }
nuclear@43: 
nuclear@23: /* if paddr is 0, we allocate physical pages with alloc_phys_page() */
nuclear@23: int map_mem_range(uint32_t vaddr, size_t sz, uint32_t paddr, unsigned int attr)
nuclear@17: {
nuclear@17: 	int vpg_start, ppg_start, num_pages;
nuclear@17: 
nuclear@23: 	if(!sz) return -1;
nuclear@17: 
nuclear@17: 	if(ADDR_TO_PGOFFS(paddr)) {
nuclear@17: 		panic("map_mem_range called with unaligned physical address: %x\n", paddr);
nuclear@17: 	}
nuclear@17: 
nuclear@17: 	vpg_start = ADDR_TO_PAGE(vaddr);
nuclear@23: 	ppg_start = paddr > 0 ? ADDR_TO_PAGE(paddr) : -1;
nuclear@17: 	num_pages = ADDR_TO_PAGE(sz) + 1;
nuclear@17: 
nuclear@23: 	return map_page_range(vpg_start, num_pages, ppg_start, attr);
nuclear@17: }
nuclear@17: 
nuclear@69: /* translate a virtual address to a physical address using the current page table */
nuclear@18: uint32_t virt_to_phys(uint32_t vaddr)
nuclear@18: {
nuclear@43: 	int pg;
nuclear@43: 	uint32_t pgaddr;
nuclear@43: 
nuclear@43: 	if((pg = virt_to_phys_page(ADDR_TO_PAGE(vaddr))) == -1) {
nuclear@43: 		return 0;
nuclear@43: 	}
nuclear@43: 	pgaddr = PAGE_TO_ADDR(pg);
nuclear@43: 
nuclear@43: 	return pgaddr | ADDR_TO_PGOFFS(vaddr);
nuclear@43: }
nuclear@43: 
nuclear@69: /* translate a virtual page number to a physical page number using the current page table */
nuclear@43: int virt_to_phys_page(int vpg)
nuclear@43: {
nuclear@18: 	uint32_t pgaddr, *pgtbl;
nuclear@43: 	int diridx, pgidx;
nuclear@43: 
nuclear@43: 	if(vpg < 0 || vpg >= PAGE_COUNT) {
nuclear@43: 		return -1;
nuclear@43: 	}
nuclear@43: 
nuclear@43: 	diridx = PAGE_TO_PGTBL(vpg);
nuclear@43: 	pgidx = PAGE_TO_PGTBL_PG(vpg);
nuclear@18: 
nuclear@18: 	if(!(pgdir[diridx] & PG_PRESENT)) {
nuclear@43: 		return -1;
nuclear@18: 	}
nuclear@26: 	pgtbl = PGTBL(diridx);
nuclear@18: 
nuclear@18: 	if(!(pgtbl[pgidx] & PG_PRESENT)) {
nuclear@43: 		return -1;
nuclear@18: 	}
nuclear@18: 	pgaddr = pgtbl[pgidx] & PGENT_ADDR_MASK;
nuclear@43: 	return ADDR_TO_PAGE(pgaddr);
nuclear@18: }
nuclear@18: 
nuclear@69: /* same as virt_to_phys, but uses the vm_page tree instead of the actual page table */
nuclear@69: uint32_t virt_to_phys_proc(struct process *p, uint32_t vaddr)
nuclear@69: {
nuclear@69: 	int pg;
nuclear@69: 	uint32_t pgaddr;
nuclear@69: 
nuclear@69: 	if((pg = virt_to_phys_page_proc(p, ADDR_TO_PAGE(vaddr))) == -1) {
nuclear@69: 		return 0;
nuclear@69: 	}
nuclear@69: 	pgaddr = PAGE_TO_ADDR(pg);
nuclear@69: 
nuclear@69: 	return pgaddr | ADDR_TO_PGOFFS(vaddr);
nuclear@69: }
nuclear@69: 
nuclear@69: /* same virt_to_phys_page, but uses the vm_page tree instead of the actual page table */
nuclear@69: int virt_to_phys_page_proc(struct process *p, int vpg)
nuclear@69: {
nuclear@69: 	struct rbnode *node;
nuclear@69: 	assert(p);
nuclear@69: 
nuclear@69: 	if(!(node = rb_findi(&p->vmmap, vpg))) {
nuclear@69: 		return -1;
nuclear@69: 	}
nuclear@69: 	return ((struct vm_page*)node->data)->ppage;
nuclear@69: }
nuclear@69: 
nuclear@22: /* allocate a contiguous block of virtual memory pages along with
nuclear@22:  * backing physical memory for them, and update the page table.
nuclear@22:  */
nuclear@22: int pgalloc(int num, int area)
nuclear@22: {
nuclear@25: 	int intr_state, ret = -1;
nuclear@22: 	struct page_range *node, *prev, dummy;
nuclear@22: 
nuclear@25: 	intr_state = get_intr_state();
nuclear@25: 	disable_intr();
nuclear@25: 
nuclear@22: 	dummy.next = pglist[area];
nuclear@22: 	node = pglist[area];
nuclear@22: 	prev = &dummy;
nuclear@22: 
nuclear@22: 	while(node) {
nuclear@22: 		if(node->end - node->start >= num) {
nuclear@22: 			ret = node->start;
nuclear@22: 			node->start += num;
nuclear@22: 
nuclear@22: 			if(node->start == node->end) {
nuclear@22: 				prev->next = node->next;
nuclear@22: 				node->next = 0;
nuclear@22: 
nuclear@22: 				if(node == pglist[area]) {
nuclear@22: 					pglist[area] = 0;
nuclear@22: 				}
nuclear@22: 				free_node(node);
nuclear@22: 			}
nuclear@22: 			break;
nuclear@22: 		}
nuclear@22: 
nuclear@22: 		prev = node;
nuclear@22: 		node = node->next;
nuclear@22: 	}
nuclear@22: 
nuclear@22: 	if(ret >= 0) {
nuclear@55: 		/*unsigned int attr = (area == MEM_USER) ? (PG_USER | PG_WRITABLE) : PG_GLOBAL;*/
nuclear@55: 		unsigned int attr = (area == MEM_USER) ? (PG_USER | PG_WRITABLE) : 0;
nuclear@55: 
nuclear@23: 		/* allocate physical storage and map */
nuclear@45: 		if(map_page_range(ret, num, -1, attr) == -1) {
nuclear@45: 			ret = -1;
nuclear@45: 		}
nuclear@45: 	}
nuclear@45: 
nuclear@45: 	set_intr_state(intr_state);
nuclear@45: 	return ret;
nuclear@45: }
nuclear@45: 
nuclear@45: int pgalloc_vrange(int start, int num)
nuclear@45: {
nuclear@45: 	struct page_range *node, *prev, dummy;
nuclear@45: 	int area, intr_state, ret = -1;
nuclear@45: 
nuclear@45: 	area = (start >= ADDR_TO_PAGE(KMEM_START)) ? MEM_KERNEL : MEM_USER;
nuclear@47: 	if(area == MEM_USER && start + num > ADDR_TO_PAGE(KMEM_START)) {
nuclear@45: 		printf("pgalloc_vrange: invalid range request crossing user/kernel split\n");
nuclear@45: 		return -1;
nuclear@45: 	}
nuclear@45: 
nuclear@45: 	intr_state = get_intr_state();
nuclear@45: 	disable_intr();
nuclear@45: 
nuclear@45: 	dummy.next = pglist[area];
nuclear@45: 	node = pglist[area];
nuclear@45: 	prev = &dummy;
nuclear@45: 
nuclear@45: 	/* check to see if the requested VM range is available */
nuclear@45: 	node = pglist[area];
nuclear@45: 	while(node) {
nuclear@45: 		if(start >= node->start && start + num <= node->end) {
nuclear@49: 			ret = start;	/* can do .. */
nuclear@49: 
nuclear@49: 			if(start == node->start) {
nuclear@49: 				/* adjacent to the start of the range */
nuclear@49: 				node->start += num;
nuclear@49: 			} else if(start + num == node->end) {
nuclear@49: 				/* adjacent to the end of the range */
nuclear@49: 				node->end = start;
nuclear@49: 			} else {
nuclear@49: 				/* somewhere in the middle, which means we need
nuclear@49: 				 * to allocate a new page_range
nuclear@49: 				 */
nuclear@49: 				struct page_range *newnode;
nuclear@49: 
nuclear@49: 				if(!(newnode = alloc_node())) {
nuclear@49: 					panic("pgalloc_vrange failed to allocate new page_range while splitting a range in half... bummer\n");
nuclear@49: 				}
nuclear@49: 				newnode->start = start + num;
nuclear@49: 				newnode->end = node->end;
nuclear@49: 				newnode->next = node->next;
nuclear@49: 
nuclear@49: 				node->end = start;
nuclear@49: 				node->next = newnode;
nuclear@49: 				/* no need to check for null nodes at this point, there's
nuclear@49: 				 * certainly stuff at the begining and the end, otherwise we
nuclear@49: 				 * wouldn't be here. so break out of it.
nuclear@49: 				 */
nuclear@49: 				break;
nuclear@49: 			}
nuclear@45: 
nuclear@45: 			if(node->start == node->end) {
nuclear@45: 				prev->next = node->next;
nuclear@45: 				node->next = 0;
nuclear@45: 
nuclear@45: 				if(node == pglist[area]) {
nuclear@45: 					pglist[area] = 0;
nuclear@45: 				}
nuclear@45: 				free_node(node);
nuclear@45: 			}
nuclear@45: 			break;
nuclear@45: 		}
nuclear@45: 
nuclear@45: 		prev = node;
nuclear@45: 		node = node->next;
nuclear@45: 	}
nuclear@45: 
nuclear@45: 	if(ret >= 0) {
nuclear@55: 		/*unsigned int attr = (area == MEM_USER) ? (PG_USER | PG_WRITABLE) : PG_GLOBAL;*/
nuclear@55: 		unsigned int attr = (area == MEM_USER) ? (PG_USER | PG_WRITABLE) : 0;
nuclear@55: 
nuclear@45: 		/* allocate physical storage and map */
nuclear@45: 		if(map_page_range(ret, num, -1, attr) == -1) {
nuclear@23: 			ret = -1;
nuclear@23: 		}
nuclear@22: 	}
nuclear@22: 
nuclear@25: 	set_intr_state(intr_state);
nuclear@22: 	return ret;
nuclear@22: }
nuclear@22: 
nuclear@22: void pgfree(int start, int num)
nuclear@22: {
nuclear@33: 	int i, area, intr_state;
nuclear@23: 	struct page_range *node, *new, *prev, *next;
nuclear@23: 
nuclear@25: 	intr_state = get_intr_state();
nuclear@25: 	disable_intr();
nuclear@25: 
nuclear@26: 	for(i=0; i<num; i++) {
nuclear@43: 		int phys_pg = virt_to_phys_page(start + i);
nuclear@43: 		if(phys_pg != -1) {
nuclear@43: 			free_phys_page(phys_pg);
nuclear@26: 		}
nuclear@26: 	}
nuclear@26: 
nuclear@23: 	if(!(new = alloc_node())) {
nuclear@23: 		panic("pgfree: can't allocate new page_range node to add the freed pages\n");
nuclear@23: 	}
nuclear@23: 	new->start = start;
nuclear@33: 	new->end = start + num;
nuclear@23: 
nuclear@23: 	area = PAGE_TO_ADDR(start) >= KMEM_START ? MEM_KERNEL : MEM_USER;
nuclear@23: 
nuclear@23: 	if(!pglist[area] || pglist[area]->start > start) {
nuclear@23: 		next = new->next = pglist[area];
nuclear@23: 		pglist[area] = new;
nuclear@23: 		prev = 0;
nuclear@23: 
nuclear@23: 	} else {
nuclear@23: 
nuclear@23: 		prev = 0;
nuclear@23: 		node = pglist[area];
nuclear@23: 		next = node ? node->next : 0;
nuclear@23: 
nuclear@23: 		while(node) {
nuclear@23: 			if(!next || next->start > start) {
nuclear@23: 				/* place here, after node */
nuclear@23: 				new->next = next;
nuclear@23: 				node->next = new;
nuclear@23: 				prev = node;	/* needed by coalesce after the loop */
nuclear@23: 				break;
nuclear@23: 			}
nuclear@23: 
nuclear@23: 			prev = node;
nuclear@23: 			node = next;
nuclear@23: 			next = node ? node->next : 0;
nuclear@23: 		}
nuclear@23: 	}
nuclear@23: 
nuclear@23: 	coalesce(prev, new, next);
nuclear@25: 	set_intr_state(intr_state);
nuclear@23: }
nuclear@23: 
nuclear@23: static void coalesce(struct page_range *low, struct page_range *mid, struct page_range *high)
nuclear@23: {
nuclear@23: 	if(high) {
nuclear@23: 		if(mid->end == high->start) {
nuclear@23: 			mid->end = high->end;
nuclear@23: 			mid->next = high->next;
nuclear@23: 			free_node(high);
nuclear@23: 		}
nuclear@23: 	}
nuclear@23: 
nuclear@23: 	if(low) {
nuclear@23: 		if(low->end == mid->start) {
nuclear@23: 			low->end += mid->end;
nuclear@23: 			low->next = mid->next;
nuclear@23: 			free_node(mid);
nuclear@23: 		}
nuclear@23: 	}
nuclear@22: }
nuclear@22: 
nuclear@52: static void pgfault(int inum)
nuclear@17: {
nuclear@52: 	struct intr_frame *frm = get_intr_frame();
nuclear@52: 	uint32_t fault_addr = get_fault_addr();
nuclear@52: 
nuclear@52: 	/* the fault occured in user space */
nuclear@55: 	if(frm->err & PG_USER) {
nuclear@52: 		int fault_page = ADDR_TO_PAGE(fault_addr);
nuclear@52: 		struct process *proc = get_current_proc();
nuclear@69: 		printf("DBG: page fault in user space (pid: %d)\n", proc->id);
nuclear@52: 		assert(proc);
nuclear@52: 
nuclear@52: 		if(frm->err & PG_PRESENT) {
nuclear@69: 			/* it's not due to a missing page fetch the attributes */
nuclear@69: 			int pgnum = ADDR_TO_PAGE(fault_addr);
nuclear@69: 
nuclear@69: 			if((frm->err & PG_WRITABLE) && (get_page_bit(pgnum, PG_WRITABLE, 0) == 0)) {
nuclear@69: 				/* write permission fault might be a CoW fault or just an error
nuclear@69: 				 * fetch the vm_page permissions to check if this is suppoosed to be
nuclear@69: 				 * a writable page (which means we should CoW).
nuclear@69: 				 */
nuclear@69: 				struct vm_page *page = get_vm_page_proc(proc, pgnum);
nuclear@69: 
nuclear@69: 				if(page->flags & PG_WRITABLE) {
nuclear@69: 					/* ok this is a CoW fault */
nuclear@69: 					if(copy_on_write(page) == -1) {
nuclear@69: 						panic("copy on write failed!");
nuclear@69: 					}
nuclear@69: 					return;	/* done, allow the process to restart the instruction and continue */
nuclear@69: 				} else {
nuclear@69: 					/* TODO eventually we'll SIGSEGV the process, for now just panic.
nuclear@69: 					 */
nuclear@69: 					goto unhandled;
nuclear@69: 				}
nuclear@69: 			}
nuclear@52: 			goto unhandled;
nuclear@52: 		}
nuclear@52: 
nuclear@69: 		/* so it's a missing page... ok */
nuclear@69: 
nuclear@52: 		/* detect if it's an automatic stack growth deal */
nuclear@55: 		if(fault_page < proc->user_stack_pg && proc->user_stack_pg - fault_page < USTACK_MAXGROW) {
nuclear@55: 			int num_pages = proc->user_stack_pg - fault_page;
nuclear@52: 			printf("growing user (%d) stack by %d pages\n", proc->id, num_pages);
nuclear@52: 
nuclear@52: 			if(pgalloc_vrange(fault_page, num_pages) != fault_page) {
nuclear@52: 				printf("failed to allocate VM for stack growth\n");
nuclear@52: 				/* TODO: in the future we'd SIGSEGV the process here, for now just panic */
nuclear@52: 				goto unhandled;
nuclear@52: 			}
nuclear@55: 			proc->user_stack_pg = fault_page;
nuclear@52: 			return;
nuclear@52: 		}
nuclear@69: 
nuclear@69: 		/* it's not a stack growth fault. since we don't do swapping yet, just
nuclear@69: 		 * fall to unhandled and panic
nuclear@69: 		 */
nuclear@52: 	}
nuclear@52: 
nuclear@52: unhandled:
nuclear@17: 	printf("~~~~ PAGE FAULT ~~~~\n");
nuclear@52: 	printf("fault address: %x\n", fault_addr);
nuclear@69: 	printf("error code: %x\n", frm->err);
nuclear@17: 
nuclear@51: 	if(frm->err & PG_PRESENT) {
nuclear@51: 		if(frm->err & 8) {
nuclear@17: 			printf("reserved bit set in some paging structure\n");
nuclear@17: 		} else {
nuclear@55: 			printf("%s protection violation ", (frm->err & PG_WRITABLE) ? "WRITE" : "READ");
nuclear@55: 			printf("in %s mode\n", (frm->err & PG_USER) ? "user" : "kernel");
nuclear@17: 		}
nuclear@17: 	} else {
nuclear@17: 		printf("page not present\n");
nuclear@17: 	}
nuclear@19: 
nuclear@19: 	panic("unhandled page fault\n");
nuclear@17: }
nuclear@22: 
nuclear@69: /* copy-on-write handler, called from pgfault above */
nuclear@69: static int copy_on_write(struct vm_page *page)
nuclear@69: {
nuclear@69: 	uint32_t newphys;
nuclear@69: 	struct vm_page *newpage;
nuclear@69: 	struct rbnode *vmnode;
nuclear@69: 	struct process *p = get_current_proc();
nuclear@69: 
nuclear@69: 	assert(page->nref > 0);
nuclear@69: 
nuclear@69: 	/* first of all check the refcount. If it's 1 then we don't need to copy
nuclear@69: 	 * anything. This will happen when all forked processes except one have
nuclear@69: 	 * marked this read-write again after faulting.
nuclear@69: 	 */
nuclear@69: 	if(page->nref == 1) {
nuclear@69: 		set_page_bit(page->vpage, PG_WRITABLE, PAGE_ONLY);
nuclear@69: 		return 0;
nuclear@69: 	}
nuclear@69: 
nuclear@69: 	/* ok let's make a copy and mark it read-write */
nuclear@69: 	if(!(newpage = malloc(sizeof *newpage))) {
nuclear@69: 		printf("copy_on_write: failed to allocate new vm_page\n");
nuclear@69: 		return -1;
nuclear@69: 	}
nuclear@69: 	newpage->vpage = page->vpage;
nuclear@69: 	newpage->flags = page->flags;
nuclear@69: 
nuclear@69: 	if(!(newphys = alloc_phys_page())) {
nuclear@69: 		printf("copy_on_write: failed to allocate physical page\n");
nuclear@69: 		/* XXX proper action: SIGSEGV */
nuclear@69: 		return -1;
nuclear@69: 	}
nuclear@69: 	newpage->ppage = ADDR_TO_PAGE(newphys);
nuclear@69: 	newpage->nref = 1;
nuclear@69: 
nuclear@69: 	/* set the new vm_page in the process vmmap */
nuclear@69: 	vmnode = rb_findi(&p->vmmap, newpage->vpage);
nuclear@69: 	assert(vmnode && vmnode->data == page);	/* shouldn't be able to fail */
nuclear@69: 	vmnode->data = newpage;
nuclear@69: 
nuclear@69: 	/* also update tha page table */
nuclear@69: 	map_page(newpage->vpage, newpage->ppage, newpage->flags);
nuclear@69: 
nuclear@69: 	/* finally decrease the refcount at the original vm_page struct */
nuclear@69: 	page->nref--;
nuclear@69: 	return 0;
nuclear@69: }
nuclear@69: 
nuclear@22: /* --- page range list node management --- */
nuclear@23: #define NODES_IN_PAGE	(PGSIZE / sizeof(struct page_range))
nuclear@23: 
nuclear@22: static struct page_range *alloc_node(void)
nuclear@22: {
nuclear@22: 	struct page_range *node;
nuclear@23: 	int pg, i;
nuclear@22: 
nuclear@22: 	if(node_pool) {
nuclear@22: 		node = node_pool;
nuclear@22: 		node_pool = node_pool->next;
nuclear@47: 		/*printf("alloc_node -> %x\n", (unsigned int)node);*/
nuclear@22: 		return node;
nuclear@22: 	}
nuclear@22: 
nuclear@23: 	/* no node structures in the pool, we need to allocate a new page,
nuclear@23: 	 * split it up into node structures, add them in the pool, and
nuclear@23: 	 * allocate one of them.
nuclear@22: 	 */
nuclear@23: 	if(!(pg = pgalloc(1, MEM_KERNEL))) {
nuclear@22: 		panic("ran out of physical memory while allocating VM range structures\n");
nuclear@22: 	}
nuclear@23: 	node_pool = (struct page_range*)PAGE_TO_ADDR(pg);
nuclear@22: 
nuclear@23: 	/* link them up, skip the first as we'll just allocate it anyway */
nuclear@23: 	for(i=2; i<NODES_IN_PAGE; i++) {
nuclear@23: 		node_pool[i - 1].next = node_pool + i;
nuclear@23: 	}
nuclear@23: 	node_pool[NODES_IN_PAGE - 1].next = 0;
nuclear@23: 
nuclear@23: 	/* grab the first and return it */
nuclear@23: 	node = node_pool++;
nuclear@47: 	/*printf("alloc_node -> %x\n", (unsigned int)node);*/
nuclear@23: 	return node;
nuclear@22: }
nuclear@22: 
nuclear@22: static void free_node(struct page_range *node)
nuclear@22: {
nuclear@22: 	node->next = node_pool;
nuclear@22: 	node_pool = node;
nuclear@47: 	/*printf("free_node\n");*/
nuclear@22: }
nuclear@23: 
nuclear@47: /* clone_vm makes a copy of the current page tables, thus duplicating the
nuclear@47:  * virtual address space.
nuclear@47:  *
nuclear@47:  * For the kernel part of the address space (last 256 page directory entries)
nuclear@47:  * we don't want to diplicate the page tables, just point all page directory
nuclear@47:  * entries to the same set of page tables.
nuclear@43:  *
nuclear@57:  * If "cow" is non-zero it also marks the shared user-space pages as
nuclear@57:  * read-only, to implement copy-on-write.
nuclear@43:  */
nuclear@69: void clone_vm(struct process *pdest, struct process *psrc, int cow)
nuclear@43: {
nuclear@57: 	int i, j, dirpg, tblpg, kstart_dirent;
nuclear@43: 	uint32_t paddr;
nuclear@43: 	uint32_t *ndir, *ntbl;
nuclear@69: 	struct rbnode *vmnode;
nuclear@43: 
nuclear@47: 	/* allocate the new page directory */
nuclear@43: 	if((dirpg = pgalloc(1, MEM_KERNEL)) == -1) {
nuclear@43: 		panic("clone_vmem: failed to allocate page directory page\n");
nuclear@43: 	}
nuclear@43: 	ndir = (uint32_t*)PAGE_TO_ADDR(dirpg);
nuclear@43: 
nuclear@47: 	/* allocate a virtual page for temporarily mapping all new
nuclear@47: 	 * page tables while we populate them.
nuclear@47: 	 */
nuclear@43: 	if((tblpg = pgalloc(1, MEM_KERNEL)) == -1) {
nuclear@43: 		panic("clone_vmem: failed to allocate page table page\n");
nuclear@43: 	}
nuclear@43: 	ntbl = (uint32_t*)PAGE_TO_ADDR(tblpg);
nuclear@43: 
nuclear@43: 	/* we will allocate physical pages and map them to this virtual page
nuclear@57: 	 * as needed in the loop below. we don't need the physical page allocated
nuclear@57: 	 * by pgalloc.
nuclear@43: 	 */
nuclear@49: 	free_phys_page(virt_to_phys((uint32_t)ntbl));
nuclear@43: 
nuclear@48: 	kstart_dirent = ADDR_TO_PAGE(KMEM_START) / 1024;
nuclear@47: 
nuclear@47: 	/* user space */
nuclear@48: 	for(i=0; i<kstart_dirent; i++) {
nuclear@43: 		if(pgdir[i] & PG_PRESENT) {
nuclear@64: 			if(cow) {
nuclear@64: 				/* first go through all the entries of the existing
nuclear@64: 				 * page table and unset the writable bits.
nuclear@64: 				 */
nuclear@64: 				for(j=0; j<1024; j++) {
nuclear@69: 					if(PGTBL(i)[j] & PG_PRESENT) {
nuclear@69: 						clear_page_bit(i * 1024 + j, PG_WRITABLE, PAGE_ONLY);
nuclear@69: 						/*PGTBL(i)[j] &= ~(uint32_t)PG_WRITABLE;*/
nuclear@69: 					}
nuclear@64: 				}
nuclear@57: 			}
nuclear@57: 
nuclear@57: 			/* allocate a page table for the clone */
nuclear@43: 			paddr = alloc_phys_page();
nuclear@43: 
nuclear@43: 			/* copy the page table */
nuclear@57: 			map_page(tblpg, ADDR_TO_PAGE(paddr), 0);
nuclear@43: 			memcpy(ntbl, PGTBL(i), PGSIZE);
nuclear@43: 
nuclear@43: 			/* set the new page directory entry */
nuclear@43: 			ndir[i] = paddr | (pgdir[i] & PGOFFS_MASK);
nuclear@43: 		} else {
nuclear@43: 			ndir[i] = 0;
nuclear@43: 		}
nuclear@43: 	}
nuclear@43: 
nuclear@69: 	/* make a copy of the parent's vmmap tree pointing to the same vm_pages
nuclear@69: 	 * and increase the reference counters for all vm_pages.
nuclear@69: 	 */
nuclear@69: 	rb_init(&pdest->vmmap, RB_KEY_INT);
nuclear@69: 	rb_begin(&psrc->vmmap);
nuclear@69: 	while((vmnode = rb_next(&psrc->vmmap))) {
nuclear@69: 		struct vm_page *pg = vmnode->data;
nuclear@69: 		pg->nref++;
nuclear@69: 
nuclear@69: 		/* insert the same vm_page to the new tree */
nuclear@69: 		rb_inserti(&pdest->vmmap, pg->vpage, pg);
nuclear@69: 	}
nuclear@69: 
nuclear@55: 	/* for the kernel space we'll just use the same page tables */
nuclear@70: 	for(i=kstart_dirent; i<1023; i++) {
nuclear@49: 		ndir[i] = pgdir[i];
nuclear@47: 	}
nuclear@70: 
nuclear@70: 	/* also point the last page directory entry to the page directory address
nuclear@70: 	 * since we're relying on recursive page tables
nuclear@70: 	 */
nuclear@69: 	paddr = virt_to_phys((uint32_t)ndir);
nuclear@69: 	ndir[1023] = paddr | PG_PRESENT;
nuclear@47: 
nuclear@64: 	if(cow) {
nuclear@64: 		/* we just changed all the page protection bits, so we need to flush the TLB */
nuclear@64: 		flush_tlb();
nuclear@64: 	}
nuclear@57: 
nuclear@57: 	/* unmap before freeing the virtual pages, to avoid deallocating the physical pages */
nuclear@43: 	unmap_page(dirpg);
nuclear@43: 	unmap_page(tblpg);
nuclear@43: 
nuclear@43: 	pgfree(dirpg, 1);
nuclear@43: 	pgfree(tblpg, 1);
nuclear@43: 
nuclear@69: 	/* set the new page directory pointer */
nuclear@69: 	pdest->ctx.pgtbl_paddr = paddr;
nuclear@43: }
nuclear@57: 
nuclear@57: int get_page_bit(int pgnum, uint32_t bit, int wholepath)
nuclear@57: {
nuclear@57: 	int tidx = PAGE_TO_PGTBL(pgnum);
nuclear@57: 	int tent = PAGE_TO_PGTBL_PG(pgnum);
nuclear@57: 	uint32_t *pgtbl = PGTBL(tidx);
nuclear@57: 
nuclear@57: 	if(wholepath) {
nuclear@57: 		if((pgdir[tidx] & bit) == 0) {
nuclear@57: 			return 0;
nuclear@57: 		}
nuclear@57: 	}
nuclear@57: 
nuclear@57: 	return pgtbl[tent] & bit;
nuclear@57: }
nuclear@57: 
nuclear@57: void set_page_bit(int pgnum, uint32_t bit, int wholepath)
nuclear@57: {
nuclear@57: 	int tidx = PAGE_TO_PGTBL(pgnum);
nuclear@57: 	int tent = PAGE_TO_PGTBL_PG(pgnum);
nuclear@57: 	uint32_t *pgtbl = PGTBL(tidx);
nuclear@57: 
nuclear@57: 	if(wholepath) {
nuclear@57: 		pgdir[tidx] |= bit;
nuclear@57: 	}
nuclear@57: 	pgtbl[tent] |= bit;
nuclear@57: 
nuclear@57: 	flush_tlb_page(pgnum);
nuclear@57: }
nuclear@57: 
nuclear@57: void clear_page_bit(int pgnum, uint32_t bit, int wholepath)
nuclear@57: {
nuclear@57: 	int tidx = PAGE_TO_PGTBL(pgnum);
nuclear@57: 	int tent = PAGE_TO_PGTBL_PG(pgnum);
nuclear@57: 	uint32_t *pgtbl = PGTBL(tidx);
nuclear@57: 
nuclear@57: 	if(wholepath) {
nuclear@57: 		pgdir[tidx] &= ~bit;
nuclear@57: 	}
nuclear@57: 
nuclear@57: 	pgtbl[tent] &= ~bit;
nuclear@57: 
nuclear@57: 	flush_tlb_page(pgnum);
nuclear@57: }
nuclear@43: 
nuclear@43: 
nuclear@68: #define USER_PGDIR_ENTRIES	PAGE_TO_PGTBL(KMEM_START_PAGE)
nuclear@68: int cons_vmmap(struct rbtree *vmmap)
nuclear@68: {
nuclear@68: 	int i, j;
nuclear@68: 
nuclear@68: 	rb_init(vmmap, RB_KEY_INT);
nuclear@68: 
nuclear@68: 	for(i=0; i<USER_PGDIR_ENTRIES; i++) {
nuclear@68: 		if(pgdir[i] & PG_PRESENT) {
nuclear@68: 			/* page table is present, iterate through its 1024 pages */
nuclear@68: 			uint32_t *pgtbl = PGTBL(i);
nuclear@68: 
nuclear@68: 			for(j=0; j<1024; j++) {
nuclear@68: 				if(pgtbl[j] & PG_PRESENT) {
nuclear@68: 					struct vm_page *vmp;
nuclear@68: 
nuclear@68: 					if(!(vmp = malloc(sizeof *vmp))) {
nuclear@68: 						panic("cons_vmap failed to allocate memory");
nuclear@68: 					}
nuclear@68: 					vmp->vpage = i * 1024 + j;
nuclear@68: 					vmp->ppage = ADDR_TO_PAGE(pgtbl[j] & PGENT_ADDR_MASK);
nuclear@68: 					vmp->flags = pgtbl[j] & ATTR_PGTBL_MASK;
nuclear@68: 					vmp->nref = 1;	/* when first created assume no sharing */
nuclear@68: 
nuclear@69: 					rb_inserti(vmmap, vmp->vpage, vmp);
nuclear@68: 				}
nuclear@68: 			}
nuclear@68: 		}
nuclear@68: 	}
nuclear@68: 
nuclear@68: 	return 0;
nuclear@68: }
nuclear@68: 
nuclear@69: struct vm_page *get_vm_page(int vpg)
nuclear@69: {
nuclear@69: 	return get_vm_page_proc(get_current_proc(), vpg);
nuclear@69: }
nuclear@69: 
nuclear@69: struct vm_page *get_vm_page_proc(struct process *p, int vpg)
nuclear@69: {
nuclear@69: 	struct rbnode *node;
nuclear@69: 
nuclear@69: 	if(!p || !(node = rb_findi(&p->vmmap, vpg))) {
nuclear@69: 		return 0;
nuclear@69: 	}
nuclear@69: 	return node->data;
nuclear@69: }
nuclear@69: 
nuclear@68: 
nuclear@23: void dbg_print_vm(int area)
nuclear@23: {
nuclear@25: 	struct page_range *node;
nuclear@25: 	int last, intr_state;
nuclear@25: 
nuclear@25: 	intr_state = get_intr_state();
nuclear@25: 	disable_intr();
nuclear@25: 
nuclear@25: 	node = pglist[area];
nuclear@25: 	last = area == MEM_USER ? 0 : ADDR_TO_PAGE(KMEM_START);
nuclear@23: 
nuclear@23: 	printf("%s vm space\n", area == MEM_USER ? "user" : "kernel");
nuclear@23: 
nuclear@23: 	while(node) {
nuclear@23: 		if(node->start > last) {
nuclear@23: 			printf("  vm-used: %x -> %x\n", PAGE_TO_ADDR(last), PAGE_TO_ADDR(node->start));
nuclear@23: 		}
nuclear@23: 
nuclear@23: 		printf("  vm-free: %x -> ", PAGE_TO_ADDR(node->start));
nuclear@23: 		if(node->end >= PAGE_COUNT) {
nuclear@23: 			printf("END\n");
nuclear@23: 		} else {
nuclear@23: 			printf("%x\n", PAGE_TO_ADDR(node->end));
nuclear@23: 		}
nuclear@23: 
nuclear@23: 		last = node->end;
nuclear@23: 		node = node->next;
nuclear@23: 	}
nuclear@25: 
nuclear@25: 	set_intr_state(intr_state);
nuclear@23: }