#include "globals.h" #include "kernel.h" #include #include "vm/anon.h" #include "vm/shadow.h" #include "util/debug.h" #include "util/printf.h" #include "util/string.h" #include "fs/file.h" #include "fs/vfs_syscall.h" #include "fs/vnode.h" #include "mm/mm.h" #include "mm/mman.h" #include "mm/slab.h" #include "mm/tlb.h" static slab_allocator_t *vmmap_allocator; static slab_allocator_t *vmarea_allocator; void vmmap_init(void) { vmmap_allocator = slab_allocator_create("vmmap", sizeof(vmmap_t)); vmarea_allocator = slab_allocator_create("vmarea", sizeof(vmarea_t)); KASSERT(vmmap_allocator && vmarea_allocator); } /* * Allocate and initialize a new vmarea using vmarea_allocator. */ vmarea_t *vmarea_alloc(void) { // Allocate a new vmarea vmarea_t *new_vmarea = (vmarea_t *)slab_obj_alloc(vmarea_allocator); if (new_vmarea == NULL) { return NULL; } // Initialize the fields of the vmarea new_vmarea->vma_start = 0; new_vmarea->vma_end = 0; new_vmarea->vma_off = 0; new_vmarea->vma_prot = 0; new_vmarea->vma_flags = 0; new_vmarea->vma_obj = NULL; new_vmarea->vma_vmmap = NULL; list_link_init(&new_vmarea->vma_plink); // Return the new vmarea return new_vmarea; } /* * Free the vmarea by removing it from any lists it may be on, putting its * vma_obj if it exists, and freeing the vmarea_t. */ void vmarea_free(vmarea_t *vma) { // Remove the vmarea from any lists it may be on if (list_link_is_linked(&vma->vma_plink)) { list_remove(&vma->vma_plink); } // Put the vma_obj if it exists if (vma->vma_obj != NULL) { mobj_put(&vma->vma_obj); } // Free the vmarea slab_obj_free(vmarea_allocator, vma); } /* * Create and initialize a new vmmap. Initialize all the fields of vmmap_t. */ vmmap_t *vmmap_create(void) { // Allocate a new vmmap vmmap_t *new_vmmap = (vmmap_t *)slab_obj_alloc(vmmap_allocator); if (new_vmmap == NULL) { return NULL; } // Initialize the fields of the vmmap list_init(&new_vmmap->vmm_list); new_vmmap->vmm_proc = curproc; return new_vmmap; } /* * Destroy the map pointed to by mapp and set *mapp = NULL. * Remember to free each vma in the maps list. */ void vmmap_destroy(vmmap_t **mapp) { vmmap_t *map = *mapp; // Iterate through the list of vmareas and free each one list_iterate(&(map)->vmm_list, vma, vmarea_t, vma_plink) { list_remove(&vma->vma_plink); vmarea_free(vma); } // Free the map slab_obj_free(vmmap_allocator, map); // Set the map to NULL *mapp = NULL; } /* * Add a vmarea to an address space. Assumes (i.e. asserts to some extent) the * vmarea is valid. Iterate through the list of vmareas, and add it * accordingly. */ void vmmap_insert(vmmap_t *map, vmarea_t *new_vma) { new_vma->vma_vmmap = map; // iterate over the list of vmareas list_iterate(&map->vmm_list, vma, vmarea_t, vma_plink) { // if the new vmarea is after the current vmarea if (vma->vma_start > new_vma->vma_end) { // insert the new vmarea before the current vmarea list_insert_before(&vma->vma_plink, &new_vma->vma_plink); return; } } // insert this map to the tail list_insert_tail(&map->vmm_list, &new_vma->vma_plink); } /* * Find a contiguous range of free virtual pages of length npages in the given * address space. Returns starting page number for the range, without altering the map. * Return -1 if no such range exists. * * Your algorithm should be first fit. * You should assert that dir is VMMAP_DIR_LOHI OR VMMAP_DIR_HILO. * If dir is: * - VMMAP_DIR_HILO: find a gap as high in the address space as possible, * starting from USER_MEM_HIGH. * - VMMAP_DIR_LOHI: find a gap as low in the address space as possible, * starting from USER_MEM_LOW. * * Make sure you are converting between page numbers and addresses correctly! */ ssize_t vmmap_find_range(vmmap_t *map, size_t npages, int dir) { // : vmmap_find_range"); // case 1: dir is VMMAP_DIR_LOHI if (dir == VMMAP_DIR_LOHI) { // iterate over the page numbers, going from low to high // determine the continguous range of free virtual pages size_t start_page, contig_page = 0; size_t vfn = ADDR_TO_PN(USER_MEM_LOW); while (vfn++ < ADDR_TO_PN(USER_MEM_HIGH)) { // Lookup the vmarea for this page number vmarea_t *vma = vmmap_lookup(map, vfn); if (vma == NULL) { // if unmapped, document this if (contig_page == 0) { start_page = 0; } contig_page++; } else { // if mapped, start over start_page = contig_page = 0; } // if the range exists, return the start if (contig_page == npages) { return start_page; } } } // case 2: dir is VMMAP_DIR_HILO if (dir == VMMAP_DIR_HILO) { // iterate over the page numbers size_t contig = 0; size_t vfn = ADDR_TO_PN(USER_MEM_HIGH); while (--vfn >= ADDR_TO_PN(USER_MEM_LOW)) { // Lookup the vmarea for this page number vmarea_t *vma = vmmap_lookup(map, vfn); if (vma == NULL) { // if unmapped, increment the contig contig++; } else { // if mapped, reset the contig contig = 0; } // if there are n contiguous pages, return the current vfn if (contig == npages) { return vfn; } } } // if no range exists, return -1 return -1; } /* * Return the vm_area that vfn (a page number) lies in. Scan the address space looking * for a vma whose range covers vfn. If the page is unmapped, return NULL. */ vmarea_t *vmmap_lookup(vmmap_t *map, size_t vfn) { // iterate over the list of vmareas list_iterate(&map->vmm_list, vma, vmarea_t, vma_plink) { // if the vfn lies within the range of the current vmarea if (vfn >= vma->vma_start && vfn < vma->vma_end) { return vma; } } // if the page is unmapped, return NULL return NULL; } /* * For each vmarea in the map, if it is a shadow object, call shadow_collapse. */ void vmmap_collapse(vmmap_t *map) { list_iterate(&map->vmm_list, vma, vmarea_t, vma_plink) { if (vma->vma_obj->mo_type == MOBJ_SHADOW) { // mobj_lock(vma->vma_obj); shadow_collapse(vma->vma_obj); // mobj_unlock(vma->vma_obj); } } } /* * This is where the magic of fork's copy-on-write gets set up. * * Upon successful return, the new vmmap should be a clone of map with all * shadow objects properly set up. * * For each vmarea, clone it's members. * 1) vmarea is share-mapped, you don't need to do anything special. * 2) vmarea is not share-mapped, time for shadow objects: * a) Create two shadow objects, one for map and one for the new vmmap you * are constructing, both of which shadow the current vma_obj the vmarea * being cloned. * b) After creating the shadow objects, put the original vma_obj * c) and insert the shadow objects into their respective vma's. * * Be sure to clean up in any error case, manage the reference counts correctly, * and to lock/unlock properly. */ vmmap_t *vmmap_clone(vmmap_t *map) { vmmap_collapse(map); // Create a new vmmap vmmap_t *new_vmmap = vmmap_create(); if (new_vmmap == NULL) { return NULL; } // Iterate over the list of vmareas list_iterate(&map->vmm_list, vma, vmarea_t, vma_plink) { // Create a new vmarea vmarea_t *new_vmarea = vmarea_alloc(); if (new_vmarea == NULL) { vmmap_destroy(&new_vmmap); return NULL; } // Clone the fields of the vmarea new_vmarea->vma_start = vma->vma_start; new_vmarea->vma_end = vma->vma_end; new_vmarea->vma_off = vma->vma_off; new_vmarea->vma_prot = vma->vma_prot; new_vmarea->vma_flags = vma->vma_flags; // If the vmarea is share-mapped if (vma->vma_flags & MAP_SHARED) { mobj_lock(vma->vma_obj); new_vmarea->vma_obj = vma->vma_obj; mobj_ref(new_vmarea->vma_obj); mobj_unlock(vma->vma_obj); } // If the vmarea is not share-mapped else { // Create two shadow objects mobj_lock(vma->vma_obj); mobj_t *shadow_obj_map = shadow_create(vma->vma_obj); mobj_unlock(vma->vma_obj); mobj_unlock(shadow_obj_map); // unlock the map before use if (shadow_obj_map == NULL) { vmarea_free(new_vmarea); vmmap_destroy(&new_vmmap); return NULL; } mobj_lock(vma->vma_obj); mobj_t *shadow_obj_new = shadow_create(vma->vma_obj); mobj_unlock(vma->vma_obj); mobj_unlock(shadow_obj_new); // unlock the new before use if (shadow_obj_new == NULL) { mobj_put(&shadow_obj_map); vmarea_free(new_vmarea); vmmap_destroy(&new_vmmap); return NULL; } // Put the original vma_obj mobj_put(&vma->vma_obj); // Insert the shadow objects into their respective vmareas new_vmarea->vma_obj = shadow_obj_new; vma->vma_obj = shadow_obj_map; } // Insert the new vmarea into the new vmmap vmmap_insert(new_vmmap, new_vmarea); } // Return the new vmmap return new_vmmap; } /* * * Insert a mapping into the map starting at lopage for npages pages. * * file - If provided, the vnode of the file to be mapped in * lopage - If provided, the desired start range of the mapping * prot - See mman.h for possible values * flags - See do_mmap()'s comments for possible values * off - Offset in the file to start mapping at, in bytes * dir - VMMAP_DIR_LOHI or VMMAP_DIR_HILO * new_vma - If provided, on success, must point to the new vmarea_t * * Return 0 on success, or: * - ENOMEM: On vmarea_alloc, anon_create, shadow_create or * vmmap_find_range failure * - Propagate errors from file->vn_ops->mmap and vmmap_remove * * Hints: * - You can assume/assert that all input is valid. It may help to write * this function and do_mmap() somewhat in tandem. * - If file is NULL, create an anon object. * - If file is non-NULL, use the vnode's mmap operation to get the mobj. * Do not assume it is file->vn_obj (mostly relevant for special devices). * - If lopage is 0, use vmmap_find_range() to get a valid range * - If lopage is not 0, the direction flag (dir) is ignored. * - If lopage is nonzero and MAP_FIXED is specified and * the given range overlaps with any preexisting mappings, * remove the preexisting mappings. * - If MAP_PRIVATE is specified, set up a shadow object. Be careful with * refcounts! * - Be careful: off is in bytes (albeit should be page-aligned), but * vma->vma_off is in pages. * - Be careful with the order of operations. Hold off on any irreversible * work until there is no more chance of failure. */ long vmmap_map(vmmap_t *map, vnode_t *file, size_t lopage, size_t npages, int prot, int flags, off_t off, int dir, vmarea_t **new_vma) { if (lopage == 0) { KASSERT(dir == VMMAP_DIR_LOHI || dir == VMMAP_DIR_HILO); ssize_t res = vmmap_find_range(map, npages, dir); if (res == -1) { return -ENOMEM; } lopage = res; } if (lopage != 0 && (flags & MAP_FIXED)) { long ret = vmmap_remove(map, lopage, npages); if (ret < 0) { return ret; } } // alloc the new vma vmarea_t *vma = vmarea_alloc(); if (!vma) { return -ENOMEM; } // fill in fields, except for mobj and vma vma->vma_start = lopage; vma->vma_end = lopage + npages; vma->vma_off = ADDR_TO_PN(off); vma->vma_prot = prot; vma->vma_flags = flags; // make the mobj, depending on the case (anon or mmap) mobj_t *obj = NULL; if (file == NULL) { obj = anon_create(); if (obj == NULL) { vmarea_free(vma); return -ENOMEM; } mobj_unlock(obj); } else { long ret = file->vn_ops->mmap(file, &obj); if (ret < 0) { vmarea_free(vma); return ret; } } vma->vma_obj = obj; // if the flag is private, upgrade the obj to a shadow obj if (flags & MAP_PRIVATE) { mobj_t *shadow_obj = shadow_create(obj); if (shadow_obj == NULL) { vmarea_free(vma); mobj_put(&obj); return -ENOMEM; } // unlock from creation mobj_unlock(shadow_obj); vma->vma_obj = shadow_obj; // put the og obj mobj_put(&obj); } // now that vma is ready, set it vmmap_insert(map, vma); if (new_vma != NULL) { *new_vma = vma; } return 0; } /* * Iterate over the mapping's vmm_list and make sure that the specified range * is completely empty. You will have to handle the following cases: * * Key: [ ] = existing vmarea_t * ******* = region to be unmapped * * Case 1: [ ******* ] * The region to be unmapped lies completely inside the vmarea. We need to * split the old vmarea into two vmareas. Be sure to increment the refcount of * the object associated with the vmarea. * * Case 2: [ *******]** * The region overlaps the end of the vmarea. Just shorten the length of * the mapping. * * Case 3: *[***** ] * The region overlaps the beginning of the vmarea. Move the beginning of * the mapping (remember to update vma_off), and shorten its length. * * Case 4: *[*************]** * The region completely contains the vmarea. Remove the vmarea from the * list. * * Return 0 on success, or: * - ENOMEM: Failed to allocate a new vmarea when splitting a vmarea (case 1). * * Hints: * - Whenever you shorten/remove any mappings, be sure to call pt_unmap_range() * tlb_flush_range() to clean your pagetables and TLB. */ long vmmap_remove(vmmap_t *map, size_t lopage, size_t npages) { // Iterate over the list of vmareas list_iterate(&map->vmm_list, vma, vmarea_t, vma_plink) { // if the vmarea is completely inside the region to be unmapped if (vma->vma_start < lopage && vma->vma_end > lopage + npages) { // split the old vmarea into two vmareas vmarea_t *new_vmarea = vmarea_alloc(); if (new_vmarea == NULL) { return -ENOMEM; } // Set the fields of the new vmarea new_vmarea->vma_start = lopage + npages; new_vmarea->vma_end = vma->vma_end; new_vmarea->vma_off += lopage + npages - vma->vma_start; new_vmarea->vma_prot = vma->vma_prot; new_vmarea->vma_flags = vma->vma_flags; // new_vmarea->vma_vmmap = map; mobj_lock(vma->vma_obj); new_vmarea->vma_obj = vma->vma_obj; // increment the refcount of the object associated with the vmarea mobj_ref(new_vmarea->vma_obj); mobj_unlock(vma->vma_obj); // Shorten the length of the old vmarea vma->vma_end = lopage; // Insert the new vmarea into the map vmmap_insert(map, new_vmarea); // call pt_unmap_range() and tlb_flush_range() to clean the pagetables and TLB pt_unmap_range( curproc->p_pml4, PN_TO_ADDR(lopage), PN_TO_ADDR(lopage + npages)); tlb_flush_range( PN_TO_ADDR(lopage), npages ); } // if the region overlaps the end of the vmarea else if (vma->vma_start < lopage && vma->vma_end > lopage && vma->vma_end <= lopage + npages) { // shorten the length of the mapping vma->vma_end = lopage; // call pt_unmap_range() and tlb_flush_range() to clean the pagetables and TLB pt_unmap_range( curproc->p_pml4, PN_TO_ADDR(lopage), PN_TO_ADDR(lopage + npages)); tlb_flush_range( PN_TO_ADDR(lopage), npages ); } // if the region overlaps the beginning of the vmarea else if (vma->vma_start >= lopage && vma->vma_end > lopage + npages && vma->vma_start < lopage + npages) { // move the beginning of the mapping and shorten its length vma->vma_off += lopage + npages - vma->vma_start; vma->vma_start = lopage + npages; // call pt_unmap_range() and tlb_flush_range() to clean the pagetables and TLB pt_unmap_range( curproc->p_pml4, PN_TO_ADDR(lopage), PN_TO_ADDR(lopage + npages)); tlb_flush_range( PN_TO_ADDR(lopage), npages ); } // if the region completely contains the vmarea else if (vma->vma_start >= lopage && vma->vma_end <= lopage + npages) { // remove the vmarea from the list list_remove(&vma->vma_plink); vmarea_free(vma); // call pt_unmap_range() and tlb_flush_range() to clean the pagetables and TLB pt_unmap_range( curproc->p_pml4, PN_TO_ADDR(lopage), PN_TO_ADDR(lopage + npages)); tlb_flush_range( PN_TO_ADDR(lopage), npages ); } } return 0; } /* * Returns 1 if the given address space has no mappings for the given range, * 0 otherwise. */ long vmmap_is_range_empty(vmmap_t *map, size_t startvfn, size_t npages) { // Iterate over the list of vmareas list_iterate(&map->vmm_list, vma, vmarea_t, vma_plink) { // if the range completely contains the vmarea if (vma->vma_start <= startvfn && vma->vma_end >= startvfn + npages) { return 0; } // if the start of the vmarea is greater than or equal to the start of the range if (vma->vma_start < startvfn + npages && vma->vma_start >= startvfn) { return 0; } // check if the end of the vmarea is greater than the start of the range if (vma->vma_end > startvfn && vma->vma_end <= startvfn + npages) { return 0; } } return 1; } /* * Read into 'buf' from the virtual address space of 'map'. Start at 'vaddr' * for size 'count'. 'vaddr' is not necessarily page-aligned. count is in bytes. * * Hints: * 1) Find the vmareas that correspond to the region to read from. * 2) Find the pframes within those vmareas corresponding to the virtual * addresses you want to read. * 3) Read from those page frames and copy it into `buf`. * 4) You will not need to check the permissisons of the area. * 5) You may assume/assert that all areas exist. * * Return 0 on success, -errno on error (propagate from the routines called). * This routine will be used within copy_from_user(). */ long vmmap_read(vmmap_t *map, const void *vaddr, void *buf, size_t count) { // Iterate over the page numbers size_t vfn = ADDR_TO_PN(vaddr); size_t end_vfn = ADDR_TO_PN(vaddr + count); size_t bytes_read = 0; while (vfn <= end_vfn) { // Lookup the vmarea for this page number vmarea_t *vma = vmmap_lookup(map, vfn); if (vma == NULL) { return -EFAULT; } // Find the pframe for this page number pframe_t *pf; mobj_lock(vma->vma_obj); long ret = mobj_get_pframe(vma->vma_obj, vfn - vma->vma_start + vma->vma_off, 0, &pf); mobj_unlock(vma->vma_obj); if (ret < 0) { return ret; } // Read from the pframe and copy it into buf void *cursor = bytes_read + vaddr; size_t bytes_this_iteration = MIN(PAGE_SIZE - PAGE_OFFSET(cursor), count - bytes_read); memcpy( (void *) buf + bytes_read, (void *) pf->pf_addr + PAGE_OFFSET(cursor), bytes_this_iteration ); // Unlock the pframe pframe_release(&pf); // Increment the bytes read bytes_read += bytes_this_iteration; // check if we have read enough if (bytes_read >= count) { return 0; } // Increment the page number vfn++; } return 0; } /* * Write from 'buf' into the virtual address space of 'map' starting at * 'vaddr' for size 'count'. * * Hints: * 1) Find the vmareas to write to. * 2) Find the correct pframes within those areas that contain the virtual addresses * that you want to write data to. * 3) Write to the pframes, copying data from buf. * 4) You do not need check permissions of the areas you use. * 5) Assume/assert that all areas exist. * 6) Remember to dirty the pages that you write to. * * Returns 0 on success, -errno on error (propagate from the routines called). * This routine will be used within copy_to_user(). */ long vmmap_write(vmmap_t *map, void *vaddr, const void *buf, size_t count) { // Iterate over the page numbers size_t vfn = ADDR_TO_PN(vaddr); size_t end_vfn = ADDR_TO_PN(vaddr + count); size_t bytes_written = 0; while(vfn <= end_vfn) { // Lookup the vmarea for this page number vmarea_t *vma = vmmap_lookup(map, vfn); if (vma == NULL) { return -EFAULT; } // Find the pframe for this page number pframe_t *pf; mobj_lock(vma->vma_obj); long ret = mobj_get_pframe(vma->vma_obj, vfn - vma->vma_start + vma->vma_off, 1, &pf); mobj_unlock(vma->vma_obj); if (ret < 0) { return ret; } // Write to the pframe, copying data from buf void *cursor = bytes_written + vaddr; size_t bytes_this_iteration = MIN(PAGE_SIZE - PAGE_OFFSET(cursor), count - bytes_written); memcpy( (void *)pf->pf_addr + PAGE_OFFSET(cursor), (void *)buf + bytes_written, bytes_this_iteration ); // Dirty the pframe pf->pf_dirty = 1; // Unlock the pframe pframe_release(&pf); // Increment the bytes written bytes_written += bytes_this_iteration; // check if we have written enough if (bytes_written >= count) { return 0; } // Increment the page number vfn++; } return 0; } size_t vmmap_mapping_info(const void *vmmap, char *buf, size_t osize) { return vmmap_mapping_info_helper(vmmap, buf, osize, ""); } size_t vmmap_mapping_info_helper(const void *vmmap, char *buf, size_t osize, char *prompt) { KASSERT(0 < osize); KASSERT(NULL != buf); KASSERT(NULL != vmmap); vmmap_t *map = (vmmap_t *)vmmap; ssize_t size = (ssize_t)osize; int len = snprintf(buf, (size_t)size, "%s%37s %5s %7s %18s %11s %23s\n", prompt, "VADDR RANGE", "PROT", "FLAGS", "MOBJ", "OFFSET", "VFN RANGE"); list_iterate(&map->vmm_list, vma, vmarea_t, vma_plink) { size -= len; buf += len; if (0 >= size) { goto end; } len = snprintf(buf, (size_t)size, "%s0x%p-0x%p %c%c%c %7s 0x%p %#.9lx %#.9lx-%#.9lx\n", prompt, (void *)(vma->vma_start << PAGE_SHIFT), (void *)(vma->vma_end << PAGE_SHIFT), (vma->vma_prot & PROT_READ ? 'r' : '-'), (vma->vma_prot & PROT_WRITE ? 'w' : '-'), (vma->vma_prot & PROT_EXEC ? 'x' : '-'), (vma->vma_flags & MAP_SHARED ? " SHARED" : "PRIVATE"), vma->vma_obj, vma->vma_off, vma->vma_start, vma->vma_end); } end: if (size <= 0) { size = osize; buf[osize - 1] = '\0'; } return osize - size; }