<commit_before>/*
** Copyright 2001-2004, <NAME>. All rights reserved.
** Distributed under the terms of the NewOS License.
*/
#include <kernel/kernel.h>
#include <kernel/vm.h>
#include <kernel/vm_priv.h>
#include <kernel/vm_page.h>
#include <kernel/vm_cache.h>
#include <kernel/vm_store_anonymous_noswap.h>
#include <kernel/vm_store_device.h>
#include <kernel/vm_store_null.h>
#include <kernel/vm_store_vnode.h>
#include <kernel/heap.h>
#include <kernel/debug.h>
#include <kernel/console.h>
#include <kernel/int.h>
#include <kernel/smp.h>
#include <kernel/sem.h>
#include <kernel/lock.h>
#include <kernel/khash.h>
#include <kernel/time.h>
#include <newos/errors.h>

#include <boot/stage2.h>

#include <kernel/arch/cpu.h>
#include <kernel/arch/vm.h>

#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>


/* global data about the vm */
vm_info_t vm_info;

static vm_address_space *kernel_aspace;

#define REGION_HASH_TABLE_SIZE 1024
static region_id next_region_id;
static void *region_table;
static sem_id region_hash_sem;

#define ASPACE_HASH_TABLE_SIZE 1024
static aspace_id next_aspace_id;
static void *aspace_table;
static sem_id aspace_hash_sem;

static spinlock_t max_commit_lock;

// function declarations
static vm_region *_vm_create_region_struct(vm_address_space *aspace, const char *name, int wiring, int lock);
static int map_backing_store(vm_address_space *aspace, vm_store *store, void **vaddr,
	off_t offset, addr_t size, int addr_type, int wiring, int lock, int mapping, vm_region **_region, const char *region_name);
static int vm_soft_fault(addr_t address, bool is_write, bool is_user);
static vm_region *vm_virtual_map_lookup(vm_virtual_map *map, addr_t address);

static int region_compare(void *_r, const void *key)
{
	vm_region *r = _r;
	const region_id *id = key;

#if DEBUG > 1
	VERIFY_VM_REGION(r);
#endif

	if(r->id == *id)
		return 0;
	else
		return -1;
}

static unsigned int region_hash(void *_r, const void *key, unsigned int range)
{
	vm_region *r = _r;
	const region_id *id = key;

#if DEBUG > 1
	if(r != NULL)
		VERIFY_VM_REGION(r);
#endif

	if(r != NULL)
		return (r->id % range);
	else
		return (*id % range);
}

static int aspace_compare(void *_a, const void *key)
{
	vm_address_space *aspace = _a;
	const aspace_id *id = key;

#if DEBUG > 1
	VERIFY_VM_ASPACE(aspace);
#endif

	if(aspace->id == *id)
		return 0;
	else
		return -1;
}

static unsigned int aspace_hash(void *_a, const void *key, unsigned int range)
{
	vm_address_space *aspace = _a;
	const aspace_id *id = key;

#if DEBUG > 1
	if(aspace != NULL)
		VERIFY_VM_ASPACE(aspace);
#endif

	if(aspace != NULL)
		return (aspace->id % range);
	else
		return (*id % range);
}

vm_address_space *vm_get_aspace_by_id(aspace_id aid)
{
	vm_address_space *aspace;

	sem_acquire(aspace_hash_sem, READ_COUNT);
	aspace = hash_lookup(aspace_table, &aid);
	if(aspace) {
		VERIFY_VM_ASPACE(aspace);
		atomic_add(&aspace->ref_count, 1);
	}
	sem_release(aspace_hash_sem, READ_COUNT);

	return aspace;
}

vm_region *vm_get_region_by_id(region_id rid)
{
	vm_region *region;

	sem_acquire(region_hash_sem, READ_COUNT);
	region = hash_lookup(region_table, &rid);
	if(region) {
		VERIFY_VM_REGION(region);
		atomic_add(&region->ref_count, 1);
	}
	sem_release(region_hash_sem, READ_COUNT);

	return region;
}

region_id vm_find_region_by_name(aspace_id aid, const char *name)
{
	vm_region *region = NULL;
	vm_address_space *aspace;
	region_id id = ERR_NOT_FOUND;

	ASSERT(name != NULL);

	aspace = vm_get_aspace_by_id(aid);
	if(aspace == NULL)
		return ERR_VM_INVALID_ASPACE;

	sem_acquire(aspace->virtual_map.sem, READ_COUNT);

	region = aspace->virtual_map.region_list;
	while(region != NULL) {
		VERIFY_VM_REGION(region);
		ASSERT(region->name != NULL);
		if(strcmp(region->name, name) == 0) {
			id = region->id;
			break;
		}
		region = region->aspace_next;
	}

	sem_release(aspace->virtual_map.sem, READ_COUNT);
	vm_put_aspace(aspace);
	return id;
}

static vm_region *_vm_create_region_struct(vm_address_space *aspace, const char *name, int wiring, int lock)
{
	vm_region *region = NULL;

	VERIFY_VM_ASPACE(aspace);
	ASSERT(name != NULL);

	region = (vm_region *)kmalloc(sizeof(vm_region));
	if(region == NULL)
		return NULL;
	region->name = (char *)kmalloc(strlen(name) + 1);
	if(region->name == NULL) {
		kfree(region);
		return NULL;
	}
	strcpy(region->name, name);
	region->magic = VM_REGION_MAGIC;
	region->id = atomic_add(&next_region_id, 1);
	region->base = 0;
	region->size = 0;
	region->lock = lock;
	region->wiring = wiring;
	region->ref_count = 1;

	region->cache_ref = NULL;
	region->cache_offset = 0;

	region->aspace = aspace;
	region->aspace_next = NULL;
	region->map = &aspace->virtual_map;
	list_clear_node(&region->cache_node);
	region->hash_next = NULL;

	return region;
}

// must be called with this address space's virtual_map.sem held
static int find_and_insert_region_slot(vm_virtual_map *map, addr_t start, addr_t size, addr_t end, int addr_type, vm_region *region)
{
	vm_region *last_r = NULL;
	vm_region *next_r;
	bool foundspot = false;

//	dprintf("find_and_insert_region_slot: map %p, start 0x%lx, size %ld, end 0x%lx, addr_type %d, region %p\n",
//		map, start, size, end, addr_type, region);
//	dprintf("map->base 0x%x, map->size 0x%x\n", map->base, map->size);

	// do some sanity checking
	if(start < map->base || size == 0 || (end - 1) > (map->base + (map->size - 1)) || start + size > end)
		return ERR_VM_BAD_ADDRESS;

	// walk up to the spot where we should start searching
	next_r = map->region_list;
	while(next_r) {
		if(next_r->base >= start + size) {
			// we have a winner
			break;
		}
		last_r = next_r;
		next_r = next_r->aspace_next;
	}

#if 0
	dprintf("last_r 0x%x, next_r 0x%x\n", last_r, next_r);
	if(last_r) dprintf("last_r->base 0x%x, last_r->size 0x%x\n", last_r->base, last_r->size);
	if(next_r) dprintf("next_r->base 0x%x, next_r->size 0x%x\n", next_r->base, next_r->size);
#endif

	switch(addr_type) {
		case REGION_ADDR_ANY_ADDRESS:
			// find a hole big enough for a new region
			if(!last_r) {
				// see if we can build it at the beginning of the virtual map
				if(!next_r || (next_r->base >= map->base + size)) {
					foundspot = true;
					region->base = map->base;
					break;
				}
				last_r = next_r;
				next_r = next_r->aspace_next;
			}
			// keep walking
			while(next_r) {
				if(next_r->base >= last_r->base + last_r->size + size) {
					// we found a spot
					foundspot = true;
					region->base = last_r->base + last_r->size;
					break;
				}
				last_r = next_r;
				next_r = next_r->aspace_next;
			}
			if((map->base + (map->size - 1)) >= (last_r->base + last_r->size + (size - 1))) {
				// found a spot
				foundspot = true;
				region->base = last_r->base + last_r->size;
				break;
			}
			break;
		case REGION_ADDR_EXACT_ADDRESS:
			// see if we can create it exactly here
			if(!last_r) {
				if(!next_r || (next_r->base >= start + size)) {
					foundspot = true;
					region->base = start;
					break;
				}
			} else {
				if(next_r) {
					if(last_r->base + last_r->size <= start && next_r->base >= start + size) {
						foundspot = true;
						region->base = start;
						break;
					}
				} else {
					if((last_r->base + (last_r->size - 1)) <= start - 1) {
						foundspot = true;
						region->base = start;
					}
				}
			}
			break;
		default:
			return ERR_INVALID_ARGS;
	}

	if(foundspot) {
		region->size = size;
		if(last_r) {
			region->aspace_next = last_r->aspace_next;
			last_r->aspace_next = region;
		} else {
			region->aspace_next = map->region_list;
			map->region_list = region;
		}
		map->change_count++;
		return NO_ERROR;
	} else {
		return ERR_VM_NO_REGION_SLOT;
	}
}

// a ref to the cache holding this store must be held before entering here
static int map_backing_store(vm_address_space *aspace, vm_store *store, void **vaddr,
	off_t offset, addr_t size, int addr_type, int wiring, int lock, int mapping, vm_region **_region, const char *region_name)
{
	vm_cache *cache;
	vm_cache_ref *cache_ref;
	vm_region *region;
	vm_cache *nu_cache;
	vm_cache_ref *nu_cache_ref = NULL;
	vm_store *nu_store;

	int err;

	VERIFY_VM_ASPACE(aspace);
	VERIFY_VM_STORE(store);

//	dprintf("map_backing_store: aspace %p, store %p, *vaddr %p, offset 0x%Lx, size 0x%lx, addr_type %d, wiring %d, lock %d, _region %p, region_name '%s'\n",
//		aspace, store, *vaddr, offset, size, addr_type, wiring, lock, _region, region_name);

	region = _vm_create_region_struct(aspace, region_name, wiring, lock);
	if(!region)
		return ERR_NO_MEMORY;

	cache = store->cache;
	VERIFY_VM_CACHE(cache);
	cache_ref = cache->ref;
	VERIFY_VM_CACHE_REF(cache_ref);

	// if this is a private map, we need to create a new cache & store object
	// pair to handle the private copies of pages as they are written to
	if(mapping == REGION_PRIVATE_MAP) {
		// create an anonymous store object
		nu_store = vm_store_create_anonymous_noswap();
		if(nu_store == NULL)
			panic("map_backing_store: vm_create_store_anonymous_noswap returned NULL");
		nu_cache = vm_cache_create(nu_store);
		if(nu_cache == NULL)
			panic("map_backing_store: vm_cache_create returned NULL");
		nu_cache_ref = vm_cache_ref_create(nu_cache);
		if(nu_cache_ref == NULL)
			panic("map_backing_store: vm_cache_ref_create returned NULL");
		nu_cache->temporary = 1;
		nu_cache->scan_skip = cache->scan_skip;

		nu_cache->source = cache;

		// grab a ref to the cache object we're now linked to as a source
		vm_cache_acquire_ref(cache_ref, true);

		cache = nu_cache;
		cache_ref = cache->ref;
		store = nu_store;
	}

	mutex_lock(&cache_ref->lock);
	if(store->committed_size < offset + size) {
		// try to commit more memory
		off_t old_store_commitment = store->committed_size;
		off_t commitment = (store->ops->commit)(store, offset + size);
		if(commitment < offset + size) {
			if(cache->temporary) {
				int_disable_interrupts();
				acquire_spinlock(&max_commit_lock);

				if(vm_info.max_commit - old_store_commitment + commitment < offset + size) {
					release_spinlock(&max_commit_lock);
					int_restore_interrupts();
					mutex_unlock(&cache_ref->lock);
					err = ERR_VM_WOULD_OVERCOMMIT;
					goto err1a;
				}

//				dprintf("map_backing_store: adding %d to max_commit\n",
//					(commitment - old_store_commitment) - (offset + size - cache->committed_size));

				vm_info.max_commit += (commitment - old_store_commitment) - (offset + size - cache->virtual_size);
				cache->virtual_size = offset + size;
				release_spinlock(&max_commit_lock);
				int_restore_interrupts();
			} else {
				mutex_unlock(&cache_ref->lock);
				err = ERR_NO_MEMORY;
				goto err1a;
			}
		}
	}

	mutex_unlock(&cache_ref->lock);

	vm_cache_acquire_ref(cache_ref, true);

	sem_acquire(aspace->virtual_map.sem, WRITE_COUNT);

	// check to see if this aspace has entered DELETE state
	if(aspace->state == VM_ASPACE_STATE_DELETION) {
		// okay, someone is trying to delete this aspace now, so we can't
		// insert the region, so back out
		err = ERR_VM_INVALID_ASPACE;
		goto err1b;
	}

	{
		addr_t search_addr, search_end;

		if(addr_type == REGION_ADDR_EXACT_ADDRESS) {
			search_addr = (addr_t)*vaddr;
			search_end = (addr_t)*vaddr + size;
		} else if(addr_type == REGION_ADDR_ANY_ADDRESS) {
			search_addr = aspace->virtual_map.base;
			search_end = aspace->virtual_map.base + (aspace->virtual_map.size - 1);
		} else {
			err = ERR_INVALID_ARGS;
			goto err1b;
		}

		err = find_and_insert_region_slot(&aspace->virtual_map, search_addr, size, search_end, addr_type, region);
		if(err < 0)
			goto err1b;
		*vaddr = (addr_t *)region->base;
	}

	// attach the cache to the region
	region->cache_ref = cache_ref;
	region->cache_offset = offset;
	// point the cache back to the region
	vm_cache_insert_region(cache_ref, region);

	// insert the region in the global region hash table
	sem_acquire(region_hash_sem, WRITE_COUNT);
	hash_insert(region_table, region);
	sem_release(region_hash_sem, WRITE_COUNT);

	// grab a ref to the aspace (the region holds this)
	atomic_add(&aspace->ref_count, 1);

	sem_release(aspace->virtual_map.sem, WRITE_COUNT);

	*_region = region;

	return NO_ERROR;

err1b:
	sem_release(aspace->virtual_map.sem, WRITE_COUNT);
	vm_cache_release_ref(cache_ref);
	goto err;
err1a:
	if(nu_cache_ref) {
		// had never acquired it's initial ref, so acquire and then release it
		// this should clean up all the objects it references
		vm_cache_acquire_ref(cache_ref, true);
		vm_cache_release_ref(cache_ref);
	}
err:
	kfree(region->name);
	kfree(region);
	return err;
}

region_id user_vm_create_anonymous_region(char *uname, void **uaddress, int addr_type,
	addr_t size, int wiring, int lock)
{
	char name[SYS_MAX_OS_NAME_LEN];
	void *address;
	int rc, rc2;

	if(is_kernel_address(uname))
		return ERR_VM_BAD_USER_MEMORY;

	rc = user_strncpy(name, uname, SYS_MAX_OS_NAME_LEN-1);
	if(rc < 0)
		return rc;
	name[SYS_MAX_OS_NAME_LEN-1] = 0;

	rc = user_memcpy(&address, uaddress, sizeof(address));
	if(rc < 0)
		return rc;

	rc = vm_create_anonymous_region(vm_get_current_user_aspace_id(), name, &address, addr_type, size, wiring, lock);
	if(rc < 0)
		return rc;

	rc2 = user_memcpy(uaddress, &address, sizeof(address));
	if(rc2 < 0)
		return rc2;

	return rc;
}

region_id vm_create_anonymous_region(aspace_id aid, char *name, void **address, int addr_type,
	addr_t size, int wiring, int lock)
{
	int err;
	vm_region *region;
	vm_cache *cache;
	vm_store *store;
	vm_address_space *aspace;
	vm_cache_ref *cache_ref;

//	dprintf("create_anonymous_region: name '%s', type %d, size 0x%lx, wiring %d, lock %d\n",
//		name, addr_type, size, wiring, lock);

	if(addr_type != REGION_ADDR_ANY_ADDRESS && addr_type != REGION_ADDR_EXACT_ADDRESS)
		return ERR_INVALID_ARGS;
	switch(wiring) {
		case REGION_WIRING_WIRED:
		case REGION_WIRING_WIRED_ALREADY:
		case REGION_WIRING_WIRED_CONTIG:
		case REGION_WIRING_LAZY:
			break;
		default:
			return ERR_INVALID_ARGS;
	}
	aspace = vm_get_aspace_by_id(aid);
	if(aspace == NULL)
		return ERR_VM_INVALID_ASPACE;

	size = PAGE_ALIGN(size);

	// create an anonymous store object
	store = vm_store_create_anonymous_noswap();
	if(store == NULL)
		panic("vm_create_anonymous_region: vm_create_store_anonymous_noswap returned NULL");
	cache = vm_cache_create(store);
	if(cache == NULL)
		panic("vm_create_anonymous_region: vm_cache_create returned NULL");
	cache_ref = vm_cache_ref_create(cache);
	if(cache_ref == NULL)
		panic("vm_create_anonymous_region: vm_cache_ref_create returned NULL");
	cache->temporary = 1;

	switch(wiring) {
		case REGION_WIRING_WIRED:
		case REGION_WIRING_WIRED_ALREADY:
		case REGION_WIRING_WIRED_CONTIG:
			cache->scan_skip = 1;
			break;
		case REGION_WIRING_LAZY:
			cache->scan_skip = 0;
			break;
	}

//	dprintf("create_anonymous_region: calling map_backing store\n");

	vm_cache_acquire_ref(cache_ref, true);
	err = map_backing_store(aspace, store, address, 0, size, addr_type, wiring, lock, REGION_NO_PRIVATE_MAP, &region, name);
	vm_cache_release_ref(cache_ref);
	if(err < 0) {
		vm_put_aspace(aspace);
		return err;
	}

//	dprintf("create_anonymous_region: done calling map_backing store\n");

	cache_ref = store->cache->ref;
	switch(wiring) {
		case REGION_WIRING_LAZY:
			break; // do nothing
		case REGION_WIRING_WIRED: {
			// pages aren't mapped at this point, but we just simulate a fault on
			// every page, which should allocate them
			addr_t va;
			// XXX remove
			for(va = region->base; va < region->base + region->size; va += PAGE_SIZE) {
//				dprintf("mapping wired pages: region %p, cache_ref %p %p, address 0x%lx\n", region, cache_ref, region->cache_ref, va);
				vm_soft_fault(va, false, false);
			}
			break;
		}
		case REGION_WIRING_WIRED_ALREADY: {
			// the pages should already be mapped. This is only really useful during
			// boot time. Find the appropriate vm_page objects and stick them in
			// the cache object.
			addr_t va;
			addr_t pa;
			unsigned int flags;
			int err;
			vm_page *page;
			off_t offset = 0;

			mutex_lock(&cache_ref->lock);
			(*aspace->translation_map.ops->lock)(&aspace->translation_map);
			for(va = region->base; va < region->base + region->size; va += PAGE_SIZE, offset += PAGE_SIZE) {
				err = (*aspace->translation_map.ops->query)(&aspace->translation_map,
					va, &pa, &flags);
				if(err < 0) {
//					dprintf("vm_create_anonymous_region: error looking up mapping for va 0x%x\n", va);
					continue;
				}
//				dprintf("vm_create_anonymous_region: looked up page at va 0x%lx. pa 0x%lx\n", va, pa);
				page = vm_lookup_page(pa / PAGE_SIZE);
				if(page == NULL) {
//					dprintf("vm_create_anonymous_region: error looking up vm_page structure for pa 0x%x\n", pa);
					continue;
				}
				atomic_add(&page->ref_count, 1);
				vm_page_set_state(page, PAGE_STATE_WIRED);
				vm_cache_insert_page(cache_ref, page, offset);
			}
			(*aspace->translation_map.ops->unlock)(&aspace->translation_map);
			mutex_unlock(&cache_ref->lock);
			break;
		}
		case REGION_WIRING_WIRED_CONTIG: {
			addr_t va;
			addr_t phys_addr;
			int err;
			vm_page *page;
			off_t offset = 0;

			page = vm_page_allocate_page_run(PAGE_STATE_CLEAR, ROUNDUP(region->size, PAGE_SIZE) / PAGE_SIZE);
			if(page == NULL) {
				// XXX back out of this
				panic("couldn't allocate page run of size %ld\n", region->size);
			}
			phys_addr = page->ppn * PAGE_SIZE;

			mutex_lock(&cache_ref->lock);
			(*aspace->translation_map.ops->lock)(&aspace->translation_map);
			for(va = region->base; va < region->base + region->size; va += PAGE_SIZE, offset += PAGE_SIZE, phys_addr += PAGE_SIZE) {
				page = vm_lookup_page(phys_addr / PAGE_SIZE);
				if(page == NULL) {
					panic("couldn't lookup physical page just allocated\n");
				}
				atomic_add(&page->ref_count, 1);
				err = (*aspace->translation_map.ops->map)(&aspace->translation_map, va, phys_addr, lock);
				if(err < 0) {
					panic("couldn't map physical page in page run\n");
				}
				vm_page_set_state(page, PAGE_STATE_WIRED);
				vm_cache_insert_page(cache_ref, page, offset);
			}
			(*aspace->translation_map.ops->unlock)(&aspace->translation_map);
			mutex_unlock(&cache_ref->lock);

			break;
		}
		default:
			;
	}
	vm_put_aspace(aspace);
//	dprintf("create_anonymous_region: done\n");
	if(region)
		return region->id;
	else
		return ERR_NO_MEMORY;
}

region_id vm_map_physical_memory(aspace_id aid, char *name, void **address, int addr_type,
	addr_t size, int lock, addr_t phys_addr)
{
	vm_region *region;
	vm_cache *cache;
	vm_cache_ref *cache_ref;
	vm_store *store;
	addr_t map_offset;
	int err;

	vm_address_space *aspace = vm_get_aspace_by_id(aid);
	if(aspace == NULL)
		return ERR_VM_INVALID_ASPACE;

	// if the physical address is somewhat inside a page,
	// move the actual region down to align on a page boundary
	map_offset = phys_addr % PAGE_SIZE;
	size += map_offset;
	phys_addr -= map_offset;

	size = PAGE_ALIGN(size);

	// create an device store object
	store = vm_store_create_device(phys_addr);
	if(store == NULL)
		panic("vm_map_physical_memory: vm_store_create_device returned NULL");
	cache = vm_cache_create(store);
	if(cache == NULL)
		panic("vm_map_physical_memory: vm_cache_create returned NULL");
	cache_ref = vm_cache_ref_create(cache);
	if(cache_ref == NULL)
		panic("vm_map_physical_memory: vm_cache_ref_create returned NULL");

	// tell the page scanner to skip over this region, it's pages are special
	cache->scan_skip = 1;

	vm_cache_acquire_ref(cache_ref, true);
	err = map_backing_store(aspace, store, address, 0, size, addr_type, 0, lock, REGION_NO_PRIVATE_MAP, &region, name);
	vm_cache_release_ref(cache_ref);
	vm_put_aspace(aspace);
	if(err < 0) {
		return err;
	}

	// modify the pointer returned to be offset back into the new region
	// the same way the physical address in was offset
	((addr_t)(*address)) += map_offset;
	return region->id;
}

region_id vm_create_null_region(aspace_id aid, char *name, void **address, int addr_type, addr_t size)
{
	vm_region *region;
	vm_cache *cache;
	vm_cache_ref *cache_ref;
	vm_store *store;
	int err;

	vm_address_space *aspace = vm_get_aspace_by_id(aid);
	if(aspace == NULL)
		return ERR_VM_INVALID_ASPACE;

	size = PAGE_ALIGN(size);

	// create an null store object
	store = vm_store_create_null();
	if(store == NULL)
		panic("vm_create_null_region: vm_store_create_null returned NULL");
	cache = vm_cache_create(store);<commit_msg>Make this file compile with gcc4<commit_after>/*
** Copyright 2001-2004, <NAME>. All rights reserved.
** Distributed under the terms of the NewOS License.
*/
#include <kernel/kernel.h>
#include <kernel/vm.h>
#include <kernel/vm_priv.h>
#include <kernel/vm_page.h>
#include <kernel/vm_cache.h>
#include <kernel/vm_store_anonymous_noswap.h>
#include <kernel/vm_store_device.h>
#include <kernel/vm_store_null.h>
#include <kernel/vm_store_vnode.h>
#include <kernel/heap.h>
#include <kernel/debug.h>
#include <kernel/console.h>
#include <kernel/int.h>
#include <kernel/smp.h>
#include <kernel/sem.h>
#include <kernel/lock.h>
#include <kernel/khash.h>
#include <kernel/time.h>
#include <newos/errors.h>

#include <boot/stage2.h>

#include <kernel/arch/cpu.h>
#include <kernel/arch/vm.h>

#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>


/* global data about the vm */
vm_info_t vm_info;

static vm_address_space *kernel_aspace;

#define REGION_HASH_TABLE_SIZE 1024
static region_id next_region_id;
static void *region_table;
static sem_id region_hash_sem;

#define ASPACE_HASH_TABLE_SIZE 1024
static aspace_id next_aspace_id;
static void *aspace_table;
static sem_id aspace_hash_sem;

static spinlock_t max_commit_lock;

// function declarations
static vm_region *_vm_create_region_struct(vm_address_space *aspace, const char *name, int wiring, int lock);
static int map_backing_store(vm_address_space *aspace, vm_store *store, void **vaddr,
	off_t offset, addr_t size, int addr_type, int wiring, int lock, int mapping, vm_region **_region, const char *region_name);
static int vm_soft_fault(addr_t address, bool is_write, bool is_user);
static vm_region *vm_virtual_map_lookup(vm_virtual_map *map, addr_t address);

static int region_compare(void *_r, const void *key)
{
	vm_region *r = _r;
	const region_id *id = key;

#if DEBUG > 1
	VERIFY_VM_REGION(r);
#endif

	if(r->id == *id)
		return 0;
	else
		return -1;
}

static unsigned int region_hash(void *_r, const void *key, unsigned int range)
{
	vm_region *r = _r;
	const region_id *id = key;

#if DEBUG > 1
	if(r != NULL)
		VERIFY_VM_REGION(r);
#endif

	if(r != NULL)
		return (r->id % range);
	else
		return (*id % range);
}

static int aspace_compare(void *_a, const void *key)
{
	vm_address_space *aspace = _a;
	const aspace_id *id = key;

#if DEBUG > 1
	VERIFY_VM_ASPACE(aspace);
#endif

	if(aspace->id == *id)
		return 0;
	else
		return -1;
}

static unsigned int aspace_hash(void *_a, const void *key, unsigned int range)
{
	vm_address_space *aspace = _a;
	const aspace_id *id = key;

#if DEBUG > 1
	if(aspace != NULL)
		VERIFY_VM_ASPACE(aspace);
#endif

	if(aspace != NULL)
		return (aspace->id % range);
	else
		return (*id % range);
}

vm_address_space *vm_get_aspace_by_id(aspace_id aid)
{
	vm_address_space *aspace;

	sem_acquire(aspace_hash_sem, READ_COUNT);
	aspace = hash_lookup(aspace_table, &aid);
	if(aspace) {
		VERIFY_VM_ASPACE(aspace);
		atomic_add(&aspace->ref_count, 1);
	}
	sem_release(aspace_hash_sem, READ_COUNT);

	return aspace;
}

vm_region *vm_get_region_by_id(region_id rid)
{
	vm_region *region;

	sem_acquire(region_hash_sem, READ_COUNT);
	region = hash_lookup(region_table, &rid);
	if(region) {
		VERIFY_VM_REGION(region);
		atomic_add(&region->ref_count, 1);
	}
	sem_release(region_hash_sem, READ_COUNT);

	return region;
}

region_id vm_find_region_by_name(aspace_id aid, const char *name)
{
	vm_region *region = NULL;
	vm_address_space *aspace;
	region_id id = ERR_NOT_FOUND;

	ASSERT(name != NULL);

	aspace = vm_get_aspace_by_id(aid);
	if(aspace == NULL)
		return ERR_VM_INVALID_ASPACE;

	sem_acquire(aspace->virtual_map.sem, READ_COUNT);

	region = aspace->virtual_map.region_list;
	while(region != NULL) {
		VERIFY_VM_REGION(region);
		ASSERT(region->name != NULL);
		if(strcmp(region->name, name) == 0) {
			id = region->id;
			break;
		}
		region = region->aspace_next;
	}

	sem_release(aspace->virtual_map.sem, READ_COUNT);
	vm_put_aspace(aspace);
	return id;
}

static vm_region *_vm_create_region_struct(vm_address_space *aspace, const char *name, int wiring, int lock)
{
	vm_region *region = NULL;

	VERIFY_VM_ASPACE(aspace);
	ASSERT(name != NULL);

	region = (vm_region *)kmalloc(sizeof(vm_region));
	if(region == NULL)
		return NULL;
	region->name = (char *)kmalloc(strlen(name) + 1);
	if(region->name == NULL) {
		kfree(region);
		return NULL;
	}
	strcpy(region->name, name);
	region->magic = VM_REGION_MAGIC;
	region->id = atomic_add(&next_region_id, 1);
	region->base = 0;
	region->size = 0;
	region->lock = lock;
	region->wiring = wiring;
	region->ref_count = 1;

	region->cache_ref = NULL;
	region->cache_offset = 0;

	region->aspace = aspace;
	region->aspace_next = NULL;
	region->map = &aspace->virtual_map;
	list_clear_node(&region->cache_node);
	region->hash_next = NULL;

	return region;
}

// must be called with this address space's virtual_map.sem held
static int find_and_insert_region_slot(vm_virtual_map *map, addr_t start, addr_t size, addr_t end, int addr_type, vm_region *region)
{
	vm_region *last_r = NULL;
	vm_region *next_r;
	bool foundspot = false;

//	dprintf("find_and_insert_region_slot: map %p, start 0x%lx, size %ld, end 0x%lx, addr_type %d, region %p\n",
//		map, start, size, end, addr_type, region);
//	dprintf("map->base 0x%x, map->size 0x%x\n", map->base, map->size);

	// do some sanity checking
	if(start < map->base || size == 0 || (end - 1) > (map->base + (map->size - 1)) || start + size > end)
		return ERR_VM_BAD_ADDRESS;

	// walk up to the spot where we should start searching
	next_r = map->region_list;
	while(next_r) {
		if(next_r->base >= start + size) {
			// we have a winner
			break;
		}
		last_r = next_r;
		next_r = next_r->aspace_next;
	}

#if 0
	dprintf("last_r 0x%x, next_r 0x%x\n", last_r, next_r);
	if(last_r) dprintf("last_r->base 0x%x, last_r->size 0x%x\n", last_r->base, last_r->size);
	if(next_r) dprintf("next_r->base 0x%x, next_r->size 0x%x\n", next_r->base, next_r->size);
#endif

	switch(addr_type) {
		case REGION_ADDR_ANY_ADDRESS:
			// find a hole big enough for a new region
			if(!last_r) {
				// see if we can build it at the beginning of the virtual map
				if(!next_r || (next_r->base >= map->base + size)) {
					foundspot = true;
					region->base = map->base;
					break;
				}
				last_r = next_r;
				next_r = next_r->aspace_next;
			}
			// keep walking
			while(next_r) {
				if(next_r->base >= last_r->base + last_r->size + size) {
					// we found a spot
					foundspot = true;
					region->base = last_r->base + last_r->size;
					break;
				}
				last_r = next_r;
				next_r = next_r->aspace_next;
			}
			if((map->base + (map->size - 1)) >= (last_r->base + last_r->size + (size - 1))) {
				// found a spot
				foundspot = true;
				region->base = last_r->base + last_r->size;
				break;
			}
			break;
		case REGION_ADDR_EXACT_ADDRESS:
			// see if we can create it exactly here
			if(!last_r) {
				if(!next_r || (next_r->base >= start + size)) {
					foundspot = true;
					region->base = start;
					break;
				}
			} else {
				if(next_r) {
					if(last_r->base + last_r->size <= start && next_r->base >= start + size) {
						foundspot = true;
						region->base = start;
						break;
					}
				} else {
					if((last_r->base + (last_r->size - 1)) <= start - 1) {
						foundspot = true;
						region->base = start;
					}
				}
			}
			break;
		default:
			return ERR_INVALID_ARGS;
	}

	if(foundspot) {
		region->size = size;
		if(last_r) {
			region->aspace_next = last_r->aspace_next;
			last_r->aspace_next = region;
		} else {
			region->aspace_next = map->region_list;
			map->region_list = region;
		}
		map->change_count++;
		return NO_ERROR;
	} else {
		return ERR_VM_NO_REGION_SLOT;
	}
}

// a ref to the cache holding this store must be held before entering here
static int map_backing_store(vm_address_space *aspace, vm_store *store, void **vaddr,
	off_t offset, addr_t size, int addr_type, int wiring, int lock, int mapping, vm_region **_region, const char *region_name)
{
	vm_cache *cache;
	vm_cache_ref *cache_ref;
	vm_region *region;
	vm_cache *nu_cache;
	vm_cache_ref *nu_cache_ref = NULL;
	vm_store *nu_store;

	int err;

	VERIFY_VM_ASPACE(aspace);
	VERIFY_VM_STORE(store);

//	dprintf("map_backing_store: aspace %p, store %p, *vaddr %p, offset 0x%Lx, size 0x%lx, addr_type %d, wiring %d, lock %d, _region %p, region_name '%s'\n",
//		aspace, store, *vaddr, offset, size, addr_type, wiring, lock, _region, region_name);

	region = _vm_create_region_struct(aspace, region_name, wiring, lock);
	if(!region)
		return ERR_NO_MEMORY;

	cache = store->cache;
	VERIFY_VM_CACHE(cache);
	cache_ref = cache->ref;
	VERIFY_VM_CACHE_REF(cache_ref);

	// if this is a private map, we need to create a new cache & store object
	// pair to handle the private copies of pages as they are written to
	if(mapping == REGION_PRIVATE_MAP) {
		// create an anonymous store object
		nu_store = vm_store_create_anonymous_noswap();
		if(nu_store == NULL)
			panic("map_backing_store: vm_create_store_anonymous_noswap returned NULL");
		nu_cache = vm_cache_create(nu_store);
		if(nu_cache == NULL)
			panic("map_backing_store: vm_cache_create returned NULL");
		nu_cache_ref = vm_cache_ref_create(nu_cache);
		if(nu_cache_ref == NULL)
			panic("map_backing_store: vm_cache_ref_create returned NULL");
		nu_cache->temporary = 1;
		nu_cache->scan_skip = cache->scan_skip;

		nu_cache->source = cache;

		// grab a ref to the cache object we're now linked to as a source
		vm_cache_acquire_ref(cache_ref, true);

		cache = nu_cache;
		cache_ref = cache->ref;
		store = nu_store;
	}

	mutex_lock(&cache_ref->lock);
	if(store->committed_size < offset + size) {
		// try to commit more memory
		off_t old_store_commitment = store->committed_size;
		off_t commitment = (store->ops->commit)(store, offset + size);
		if(commitment < offset + size) {
			if(cache->temporary) {
				int_disable_interrupts();
				acquire_spinlock(&max_commit_lock);

				if(vm_info.max_commit - old_store_commitment + commitment < offset + size) {
					release_spinlock(&max_commit_lock);
					int_restore_interrupts();
					mutex_unlock(&cache_ref->lock);
					err = ERR_VM_WOULD_OVERCOMMIT;
					goto err1a;
				}

//				dprintf("map_backing_store: adding %d to max_commit\n",
//					(commitment - old_store_commitment) - (offset + size - cache->committed_size));

				vm_info.max_commit += (commitment - old_store_commitment) - (offset + size - cache->virtual_size);
				cache->virtual_size = offset + size;
				release_spinlock(&max_commit_lock);
				int_restore_interrupts();
			} else {
				mutex_unlock(&cache_ref->lock);
				err = ERR_NO_MEMORY;
				goto err1a;
			}
		}
	}

	mutex_unlock(&cache_ref->lock);

	vm_cache_acquire_ref(cache_ref, true);

	sem_acquire(aspace->virtual_map.sem, WRITE_COUNT);

	// check to see if this aspace has entered DELETE state
	if(aspace->state == VM_ASPACE_STATE_DELETION) {
		// okay, someone is trying to delete this aspace now, so we can't
		// insert the region, so back out
		err = ERR_VM_INVALID_ASPACE;
		goto err1b;
	}

	{
		addr_t search_addr, search_end;

		if(addr_type == REGION_ADDR_EXACT_ADDRESS) {
			search_addr = (addr_t)*vaddr;
			search_end = (addr_t)*vaddr + size;
		} else if(addr_type == REGION_ADDR_ANY_ADDRESS) {
			search_addr = aspace->virtual_map.base;
			search_end = aspace->virtual_map.base + (aspace->virtual_map.size - 1);
		} else {
			err = ERR_INVALID_ARGS;
			goto err1b;
		}

		err = find_and_insert_region_slot(&aspace->virtual_map, search_addr, size, search_end, addr_type, region);
		if(err < 0)
			goto err1b;
		*vaddr = (addr_t *)region->base;
	}

	// attach the cache to the region
	region->cache_ref = cache_ref;
	region->cache_offset = offset;
	// point the cache back to the region
	vm_cache_insert_region(cache_ref, region);

	// insert the region in the global region hash table
	sem_acquire(region_hash_sem, WRITE_COUNT);
	hash_insert(region_table, region);
	sem_release(region_hash_sem, WRITE_COUNT);

	// grab a ref to the aspace (the region holds this)
	atomic_add(&aspace->ref_count, 1);

	sem_release(aspace->virtual_map.sem, WRITE_COUNT);

	*_region = region;

	return NO_ERROR;

err1b:
	sem_release(aspace->virtual_map.sem, WRITE_COUNT);
	vm_cache_release_ref(cache_ref);
	goto err;
err1a:
	if(nu_cache_ref) {
		// had never acquired it's initial ref, so acquire and then release it
		// this should clean up all the objects it references
		vm_cache_acquire_ref(cache_ref, true);
		vm_cache_release_ref(cache_ref);
	}
err:
	kfree(region->name);
	kfree(region);
	return err;
}

region_id user_vm_create_anonymous_region(char *uname, void **uaddress, int addr_type,
	addr_t size, int wiring, int lock)
{
	char name[SYS_MAX_OS_NAME_LEN];
	void *address;
	int rc, rc2;

	if(is_kernel_address(uname))
		return ERR_VM_BAD_USER_MEMORY;

	rc = user_strncpy(name, uname, SYS_MAX_OS_NAME_LEN-1);
	if(rc < 0)
		return rc;
	name[SYS_MAX_OS_NAME_LEN-1] = 0;

	rc = user_memcpy(&address, uaddress, sizeof(address));
	if(rc < 0)
		return rc;

	rc = vm_create_anonymous_region(vm_get_current_user_aspace_id(), name, &address, addr_type, size, wiring, lock);
	if(rc < 0)
		return rc;

	rc2 = user_memcpy(uaddress, &address, sizeof(address));
	if(rc2 < 0)
		return rc2;

	return rc;
}

region_id vm_create_anonymous_region(aspace_id aid, char *name, void **address, int addr_type,
	addr_t size, int wiring, int lock)
{
	int err;
	vm_region *region;
	vm_cache *cache;
	vm_store *store;
	vm_address_space *aspace;
	vm_cache_ref *cache_ref;

//	dprintf("create_anonymous_region: name '%s', type %d, size 0x%lx, wiring %d, lock %d\n",
//		name, addr_type, size, wiring, lock);

	if(addr_type != REGION_ADDR_ANY_ADDRESS && addr_type != REGION_ADDR_EXACT_ADDRESS)
		return ERR_INVALID_ARGS;
	switch(wiring) {
		case REGION_WIRING_WIRED:
		case REGION_WIRING_WIRED_ALREADY:
		case REGION_WIRING_WIRED_CONTIG:
		case REGION_WIRING_LAZY:
			break;
		default:
			return ERR_INVALID_ARGS;
	}
	aspace = vm_get_aspace_by_id(aid);
	if(aspace == NULL)
		return ERR_VM_INVALID_ASPACE;

	size = PAGE_ALIGN(size);

	// create an anonymous store object
	store = vm_store_create_anonymous_noswap();
	if(store == NULL)
		panic("vm_create_anonymous_region: vm_create_store_anonymous_noswap returned NULL");
	cache = vm_cache_create(store);
	if(cache == NULL)
		panic("vm_create_anonymous_region: vm_cache_create returned NULL");
	cache_ref = vm_cache_ref_create(cache);
	if(cache_ref == NULL)
		panic("vm_create_anonymous_region: vm_cache_ref_create returned NULL");
	cache->temporary = 1;

	switch(wiring) {
		case REGION_WIRING_WIRED:
		case REGION_WIRING_WIRED_ALREADY:
		case REGION_WIRING_WIRED_CONTIG:
			cache->scan_skip = 1;
			break;
		case REGION_WIRING_LAZY:
			cache->scan_skip = 0;
			break;
	}

//	dprintf("create_anonymous_region: calling map_backing store\n");

	vm_cache_acquire_ref(cache_ref, true);
	err = map_backing_store(aspace, store, address, 0, size, addr_type, wiring, lock, REGION_NO_PRIVATE_MAP, &region, name);
	vm_cache_release_ref(cache_ref);
	if(err < 0) {
		vm_put_aspace(aspace);
		return err;
	}

//	dprintf("create_anonymous_region: done calling map_backing store\n");

	cache_ref = store->cache->ref;
	switch(wiring) {
		case REGION_WIRING_LAZY:
			break; // do nothing
		case REGION_WIRING_WIRED: {
			// pages aren't mapped at this point, but we just simulate a fault on
			// every page, which should allocate them
			addr_t va;
			// XXX remove
			for(va = region->base; va < region->base + region->size; va += PAGE_SIZE) {
//				dprintf("mapping wired pages: region %p, cache_ref %p %p, address 0x%lx\n", region, cache_ref, region->cache_ref, va);
				vm_soft_fault(va, false, false);
			}
			break;
		}
		case REGION_WIRING_WIRED_ALREADY: {
			// the pages should already be mapped. This is only really useful during
			// boot time. Find the appropriate vm_page objects and stick them in
			// the cache object.
			addr_t va;
			addr_t pa;
			unsigned int flags;
			int err;
			vm_page *page;
			off_t offset = 0;

			mutex_lock(&cache_ref->lock);
			(*aspace->translation_map.ops->lock)(&aspace->translation_map);
			for(va = region->base; va < region->base + region->size; va += PAGE_SIZE, offset += PAGE_SIZE) {
				err = (*aspace->translation_map.ops->query)(&aspace->translation_map,
					va, &pa, &flags);
				if(err < 0) {
//					dprintf("vm_create_anonymous_region: error looking up mapping for va 0x%x\n", va);
					continue;
				}
//				dprintf("vm_create_anonymous_region: looked up page at va 0x%lx. pa 0x%lx\n", va, pa);
				page = vm_lookup_page(pa / PAGE_SIZE);
				if(page == NULL) {
//					dprintf("vm_create_anonymous_region: error looking up vm_page structure for pa 0x%x\n", pa);
					continue;
				}
				atomic_add(&page->ref_count, 1);
				vm_page_set_state(page, PAGE_STATE_WIRED);
				vm_cache_insert_page(cache_ref, page, offset);
			}
			(*aspace->translation_map.ops->unlock)(&aspace->translation_map);
			mutex_unlock(&cache_ref->lock);
			break;
		}
		case REGION_WIRING_WIRED_CONTIG: {
			addr_t va;
			addr_t phys_addr;
			int err;
			vm_page *page;
			off_t offset = 0;

			page = vm_page_allocate_page_run(PAGE_STATE_CLEAR, ROUNDUP(region->size, PAGE_SIZE) / PAGE_SIZE);
			if(page == NULL) {
				// XXX back out of this
				panic("couldn't allocate page run of size %ld\n", region->size);
			}
			phys_addr = page->ppn * PAGE_SIZE;

			mutex_lock(&cache_ref->lock);
			(*aspace->translation_map.ops->lock)(&aspace->translation_map);
			for(va = region->base; va < region->base + region->size; va += PAGE_SIZE, offset += PAGE_SIZE, phys_addr += PAGE_SIZE) {
				page = vm_lookup_page(phys_addr / PAGE_SIZE);
				if(page == NULL) {
					panic("couldn't lookup physical page just allocated\n");
				}
				atomic_add(&page->ref_count, 1);
				err = (*aspace->translation_map.ops->map)(&aspace->translation_map, va, phys_addr, lock);
				if(err < 0) {
					panic("couldn't map physical page in page run\n");
				}
				vm_page_set_state(page, PAGE_STATE_WIRED);
				vm_cache_insert_page(cache_ref, page, offset);
			}
			(*aspace->translation_map.ops->unlock)(&aspace->translation_map);
			mutex_unlock(&cache_ref->lock);

			break;
		}
		default:
			;
	}
	vm_put_aspace(aspace);
//	dprintf("create_anonymous_region: done\n");
	if(region)
		return region->id;
	else
		return ERR_NO_MEMORY;
}

region_id vm_map_physical_memory(aspace_id aid, char *name, void **address, int addr_type,
	addr_t size, int lock, addr_t phys_addr)
{
	vm_region *region;
	vm_cache *cache;
	vm_cache_ref *cache_ref;
	vm_store *store;
	addr_t map_offset;
	int err;

	vm_address_space *aspace = vm_get_aspace_by_id(aid);
	if(aspace == NULL)
		return ERR_VM_INVALID_ASPACE;

	// if the physical address is somewhat inside a page,
	// move the actual region down to align on a page boundary
	map_offset = phys_addr % PAGE_SIZE;
	size += map_offset;
	phys_addr -= map_offset;

	size = PAGE_ALIGN(size);

	// create an device store object
	store = vm_store_create_device(phys_addr);
	if(store == NULL)
		panic("vm_map_physical_memory: vm_store_create_device returned NULL");
	cache = vm_cache_create(store);
	if(cache == NULL)
		panic("vm_map_physical_memory: vm_cache_create returned NULL");
	cache_ref = vm_cache_ref_create(cache);
	if(cache_ref == NULL)
		panic("vm_map_physical_memory: vm_cache_ref_create returned NULL");

	// tell the page scanner to skip over this region, it's pages are special
	cache->scan_skip = 1;

	vm_cache_acquire_ref(cache_ref, true);
	err = map_backing_store(aspace, store, address, 0, size, addr_type, 0, lock, REGION_NO_PRIVATE_MAP, &region, name);
	vm_cache_release_ref(cache_ref);
	vm_put_aspace(aspace);
	if(err < 0) {
		return err;
	}

	// modify the pointer returned to be offset back into the new region
	// the same way the physical address in was offset
	(*address) = (void *)(((addr_t)*address) + map_offset);
	return region->id;
}

region_id vm_create_null_region(aspace_id aid, char *name, void **address, int addr_type, addr_t size)
{
	vm_region *region;
	vm_cache *cache;
	vm_cache_ref *cache_ref;
	vm_store *store;
	int err;

	vm_address_space *aspace = vm_get_aspace_by_id(aid);
	if(aspace == NULL)
		return ERR_VM_INVALID_ASPACE;

	size = PAGE_ALIGN(size);

	// create an null store object
	store = vm_store_create_null();
	if(store == NULL)
		panic("vm_create_null_region: vm_store_create_null returned NULL");
	cache = vm_cache_create(store);
{'fraction_non_alphanumeric': 0.12456713412088317, 'fraction_numerical': 0.004789154407250043, 'mean_word_length': 4.331674741390598, 'pattern_counts': {'":': 0, '<': 93, '<?xml version=': 0, '>': 405, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1249345', 'n_tokens_mistral': 16836, 'n_tokens_neox': 15295, 'n_words': 3538}