WebSVN – HelenOS – Blame – /trunk/kernel/generic/src/mm/as.c

Rev	Author	Line No.	Line
703	jermar	1	/*
		2	* Copyright (C) 2001-2006 Jakub Jermar
		3	* All rights reserved.
		4	*
		5	* Redistribution and use in source and binary forms, with or without
		6	* modification, are permitted provided that the following conditions
		7	* are met:
		8	*
		9	* - Redistributions of source code must retain the above copyright
		10	* notice, this list of conditions and the following disclaimer.
		11	* - Redistributions in binary form must reproduce the above copyright
		12	* notice, this list of conditions and the following disclaimer in the
		13	* documentation and/or other materials provided with the distribution.
		14	* - The name of the author may not be used to endorse or promote products
		15	* derived from this software without specific prior written permission.
		16	*
		17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
		18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
		19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
		20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
		21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
		22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
		23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
		24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
		25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
		26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		27	*/
		28
1757	jermar	29	/** @addtogroup genericmm
1702	cejka	30	* @{
		31	*/
		32
1248	jermar	33	/**
1702	cejka	34	* @file
1248	jermar	35	* @brief Address space related functions.
		36	*
703	jermar	37	* This file contains address space manipulation functions.
		38	* Roughly speaking, this is a higher-level client of
		39	* Virtual Address Translation (VAT) subsystem.
1248	jermar	40	*
		41	* Functionality provided by this file allows one to
1757	jermar	42	* create address spaces and create, resize and share
1248	jermar	43	* address space areas.
		44	*
		45	* @see page.c
		46	*
703	jermar	47	*/
		48
		49	#include <mm/as.h>
756	jermar	50	#include <arch/mm/as.h>
703	jermar	51	#include <mm/page.h>
		52	#include <mm/frame.h>
814	palkovsky	53	#include <mm/slab.h>
703	jermar	54	#include <mm/tlb.h>
		55	#include <arch/mm/page.h>
		56	#include <genarch/mm/page_pt.h>
1108	jermar	57	#include <genarch/mm/page_ht.h>
727	jermar	58	#include <mm/asid.h>
703	jermar	59	#include <arch/mm/asid.h>
		60	#include <synch/spinlock.h>
1380	jermar	61	#include <synch/mutex.h>
788	jermar	62	#include <adt/list.h>
1147	jermar	63	#include <adt/btree.h>
1235	jermar	64	#include <proc/task.h>
1288	jermar	65	#include <proc/thread.h>
1235	jermar	66	#include <arch/asm.h>
703	jermar	67	#include <panic.h>
		68	#include <debug.h>
1235	jermar	69	#include <print.h>
703	jermar	70	#include <memstr.h>
1070	jermar	71	#include <macros.h>
703	jermar	72	#include <arch.h>
1235	jermar	73	#include <errno.h>
		74	#include <config.h>
1387	jermar	75	#include <align.h>
1235	jermar	76	#include <arch/types.h>
		77	#include <typedefs.h>
1288	jermar	78	#include <syscall/copy.h>
		79	#include <arch/interrupt.h>
703	jermar	80
1757	jermar	81	/**
		82	* Each architecture decides what functions will be used to carry out
		83	* address space operations such as creating or locking page tables.
		84	*/
756	jermar	85	as_operations_t *as_operations = NULL;
703	jermar	86
1890	jermar	87	/**
		88	* Slab for as_t objects.
		89	*/
		90	static slab_cache_t *as_slab;
		91
1415	jermar	92	/** This lock protects inactive_as_with_asid_head list. It must be acquired before as_t mutex. */
		93	SPINLOCK_INITIALIZE(inactive_as_with_asid_lock);
823	jermar	94
		95	/**
		96	* This list contains address spaces that are not active on any
		97	* processor and that have valid ASID.
		98	*/
		99	LIST_INITIALIZE(inactive_as_with_asid_head);
		100
757	jermar	101	/** Kernel address space. */
		102	as_t *AS_KERNEL = NULL;
		103
1235	jermar	104	static int area_flags_to_page_flags(int aflags);
1780	jermar	105	static as_area_t find_area_and_lock(as_t as, uintptr_t va);
		106	static bool check_area_conflicts(as_t as, uintptr_t va, size_t size, as_area_t avoid_area);
1409	jermar	107	static void sh_info_remove_reference(share_info_t *sh_info);
703	jermar	108
1891	jermar	109	static int as_constructor(void *obj, int flags)
		110	{
		111	as_t as = (as_t ) obj;
		112	int rc;
		113
		114	link_initialize(&as->inactive_as_with_asid_link);
		115	mutex_initialize(&as->lock);
		116
		117	rc = as_constructor_arch(as, flags);
		118
		119	return rc;
		120	}
		121
		122	static int as_destructor(void *obj)
		123	{
		124	as_t as = (as_t ) obj;
		125
		126	return as_destructor_arch(as);
		127	}
		128
756	jermar	129	/** Initialize address space subsystem. */
		130	void as_init(void)
		131	{
		132	as_arch_init();
1890	jermar	133
1891	jermar	134	as_slab = slab_cache_create("as_slab", sizeof(as_t), 0,
		135	as_constructor, as_destructor, SLAB_CACHE_MAGDEFERRED);
1890	jermar	136
789	palkovsky	137	AS_KERNEL = as_create(FLAG_AS_KERNEL);
1383	decky	138	if (!AS_KERNEL)
		139	panic("can't create kernel address space\n");
		140
756	jermar	141	}
		142
757	jermar	143	/** Create address space.
		144	*
		145	* @param flags Flags that influence way in wich the address space is created.
		146	*/
756	jermar	147	as_t *as_create(int flags)
703	jermar	148	{
		149	as_t *as;
		150
1890	jermar	151	as = (as_t *) slab_alloc(as_slab, 0);
1891	jermar	152	(void) as_create_arch(as, 0);
		153
1147	jermar	154	btree_create(&as->as_area_btree);
822	palkovsky	155
		156	if (flags & FLAG_AS_KERNEL)
		157	as->asid = ASID_KERNEL;
		158	else
		159	as->asid = ASID_INVALID;
		160
1468	jermar	161	as->refcount = 0;
1415	jermar	162	as->cpu_refcount = 0;
822	palkovsky	163	as->page_table = page_table_create(flags);
703	jermar	164
		165	return as;
		166	}
		167
1468	jermar	168	/** Destroy adress space.
		169	*
		170	* When there are no tasks referencing this address space (i.e. its refcount is zero),
		171	* the address space can be destroyed.
		172	*/
		173	void as_destroy(as_t *as)
973	palkovsky	174	{
1468	jermar	175	ipl_t ipl;
1594	jermar	176	bool cond;
973	palkovsky	177
1468	jermar	178	ASSERT(as->refcount == 0);
		179
		180	/*
		181	* Since there is no reference to this area,
		182	* it is safe not to lock its mutex.
		183	*/
		184	ipl = interrupts_disable();
		185	spinlock_lock(&inactive_as_with_asid_lock);
1587	jermar	186	if (as->asid != ASID_INVALID && as != AS_KERNEL) {
1594	jermar	187	if (as != AS && as->cpu_refcount == 0)
1587	jermar	188	list_remove(&as->inactive_as_with_asid_link);
1468	jermar	189	asid_put(as->asid);
		190	}
		191	spinlock_unlock(&inactive_as_with_asid_lock);
		192
		193	/*
		194	* Destroy address space areas of the address space.
1954	jermar	195	* The B+tree must be walked carefully because it is
1594	jermar	196	* also being destroyed.
1468	jermar	197	*/
1594	jermar	198	for (cond = true; cond; ) {
1468	jermar	199	btree_node_t *node;
1594	jermar	200
		201	ASSERT(!list_empty(&as->as_area_btree.leaf_head));
		202	node = list_get_instance(as->as_area_btree.leaf_head.next, btree_node_t, leaf_link);
		203
		204	if ((cond = node->keys)) {
		205	as_area_destroy(as, node->key[0]);
		206	}
1468	jermar	207	}
1495	jermar	208
1483	jermar	209	btree_destroy(&as->as_area_btree);
1468	jermar	210	page_table_destroy(as->page_table);
		211
		212	interrupts_restore(ipl);
		213
1890	jermar	214	slab_free(as_slab, as);
973	palkovsky	215	}
		216
703	jermar	217	/** Create address space area of common attributes.
		218	*
		219	* The created address space area is added to the target address space.
		220	*
		221	* @param as Target address space.
1239	jermar	222	* @param flags Flags of the area memory.
1048	jermar	223	* @param size Size of area.
703	jermar	224	* @param base Base address of area.
1239	jermar	225	* @param attrs Attributes of the area.
1409	jermar	226	* @param backend Address space area backend. NULL if no backend is used.
		227	* @param backend_data NULL or a pointer to an array holding two void *.
703	jermar	228	*
		229	* @return Address space area on success or NULL on failure.
		230	*/
1780	jermar	231	as_area_t as_area_create(as_t as, int flags, size_t size, uintptr_t base, int attrs,
1424	jermar	232	mem_backend_t backend, mem_backend_data_t backend_data)
703	jermar	233	{
		234	ipl_t ipl;
		235	as_area_t *a;
		236
		237	if (base % PAGE_SIZE)
1048	jermar	238	return NULL;
		239
1233	jermar	240	if (!size)
		241	return NULL;
		242
1048	jermar	243	/* Writeable executable areas are not supported. */
		244	if ((flags & AS_AREA_EXEC) && (flags & AS_AREA_WRITE))
		245	return NULL;
703	jermar	246
		247	ipl = interrupts_disable();
1380	jermar	248	mutex_lock(&as->lock);
703	jermar	249
1048	jermar	250	if (!check_area_conflicts(as, base, size, NULL)) {
1380	jermar	251	mutex_unlock(&as->lock);
1048	jermar	252	interrupts_restore(ipl);
		253	return NULL;
		254	}
703	jermar	255
822	palkovsky	256	a = (as_area_t *) malloc(sizeof(as_area_t), 0);
703	jermar	257
1380	jermar	258	mutex_initialize(&a->lock);
822	palkovsky	259
1424	jermar	260	a->as = as;
1026	jermar	261	a->flags = flags;
1239	jermar	262	a->attributes = attrs;
1048	jermar	263	a->pages = SIZE2FRAMES(size);
822	palkovsky	264	a->base = base;
1409	jermar	265	a->sh_info = NULL;
		266	a->backend = backend;
1424	jermar	267	if (backend_data)
		268	a->backend_data = *backend_data;
		269	else
1780	jermar	270	memsetb((uintptr_t) &a->backend_data, sizeof(a->backend_data), 0);
1424	jermar	271
1387	jermar	272	btree_create(&a->used_space);
822	palkovsky	273
1147	jermar	274	btree_insert(&as->as_area_btree, base, (void *) a, NULL);
822	palkovsky	275
1380	jermar	276	mutex_unlock(&as->lock);
703	jermar	277	interrupts_restore(ipl);
704	jermar	278
703	jermar	279	return a;
		280	}
		281
1235	jermar	282	/** Find address space area and change it.
		283	*
		284	* @param as Address space.
		285	* @param address Virtual address belonging to the area to be changed. Must be page-aligned.
		286	* @param size New size of the virtual memory block starting at address.
		287	* @param flags Flags influencing the remap operation. Currently unused.
		288	*
1306	jermar	289	* @return Zero on success or a value from @ref errno.h otherwise.
1235	jermar	290	*/
1780	jermar	291	int as_area_resize(as_t *as, uintptr_t address, size_t size, int flags)
1235	jermar	292	{
1306	jermar	293	as_area_t *area;
1235	jermar	294	ipl_t ipl;
		295	size_t pages;
		296
		297	ipl = interrupts_disable();
1380	jermar	298	mutex_lock(&as->lock);
1235	jermar	299
		300	/*
		301	* Locate the area.
		302	*/
		303	area = find_area_and_lock(as, address);
		304	if (!area) {
1380	jermar	305	mutex_unlock(&as->lock);
1235	jermar	306	interrupts_restore(ipl);
1306	jermar	307	return ENOENT;
1235	jermar	308	}
		309
1424	jermar	310	if (area->backend == &phys_backend) {
1235	jermar	311	/*
		312	* Remapping of address space areas associated
		313	* with memory mapped devices is not supported.
		314	*/
1380	jermar	315	mutex_unlock(&area->lock);
		316	mutex_unlock(&as->lock);
1235	jermar	317	interrupts_restore(ipl);
1306	jermar	318	return ENOTSUP;
1235	jermar	319	}
1409	jermar	320	if (area->sh_info) {
		321	/*
		322	* Remapping of shared address space areas
		323	* is not supported.
		324	*/
		325	mutex_unlock(&area->lock);
		326	mutex_unlock(&as->lock);
		327	interrupts_restore(ipl);
		328	return ENOTSUP;
		329	}
1235	jermar	330
		331	pages = SIZE2FRAMES((address - area->base) + size);
		332	if (!pages) {
		333	/*
		334	* Zero size address space areas are not allowed.
		335	*/
1380	jermar	336	mutex_unlock(&area->lock);
		337	mutex_unlock(&as->lock);
1235	jermar	338	interrupts_restore(ipl);
1306	jermar	339	return EPERM;
1235	jermar	340	}
		341
		342	if (pages < area->pages) {
1403	jermar	343	bool cond;
1780	jermar	344	uintptr_t start_free = area->base + pages*PAGE_SIZE;
1235	jermar	345
		346	/*
		347	* Shrinking the area.
		348	* No need to check for overlaps.
		349	*/
1403	jermar	350
		351	/*
1436	jermar	352	* Start TLB shootdown sequence.
		353	*/
		354	tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
		355
		356	/*
1403	jermar	357	* Remove frames belonging to used space starting from
		358	* the highest addresses downwards until an overlap with
		359	* the resized address space area is found. Note that this
		360	* is also the right way to remove part of the used_space
		361	* B+tree leaf list.
		362	*/
		363	for (cond = true; cond;) {
		364	btree_node_t *node;
		365
		366	ASSERT(!list_empty(&area->used_space.leaf_head));
		367	node = list_get_instance(area->used_space.leaf_head.prev, btree_node_t, leaf_link);
		368	if ((cond = (bool) node->keys)) {
1780	jermar	369	uintptr_t b = node->key[node->keys - 1];
1403	jermar	370	count_t c = (count_t) node->value[node->keys - 1];
		371	int i = 0;
1235	jermar	372
1403	jermar	373	if (overlaps(b, cPAGE_SIZE, area->base, pagesPAGE_SIZE)) {
		374
		375	if (b + c*PAGE_SIZE <= start_free) {
		376	/*
		377	* The whole interval fits completely
		378	* in the resized address space area.
		379	*/
		380	break;
		381	}
		382
		383	/*
		384	* Part of the interval corresponding to b and c
		385	* overlaps with the resized address space area.
		386	*/
		387
		388	cond = false; /* we are almost done */
		389	i = (start_free - b) >> PAGE_WIDTH;
		390	if (!used_space_remove(area, start_free, c - i))
1889	jermar	391	panic("Could not remove used space.\n");
1403	jermar	392	} else {
		393	/*
		394	* The interval of used space can be completely removed.
		395	*/
		396	if (!used_space_remove(area, b, c))
		397	panic("Could not remove used space.\n");
		398	}
		399
		400	for (; i < c; i++) {
		401	pte_t *pte;
		402
		403	page_table_lock(as, false);
		404	pte = page_mapping_find(as, b + i*PAGE_SIZE);
		405	ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
1424	jermar	406	if (area->backend && area->backend->frame_free) {
		407	area->backend->frame_free(area,
1409	jermar	408	b + i*PAGE_SIZE, PTE_GET_FRAME(pte));
		409	}
1403	jermar	410	page_mapping_remove(as, b + i*PAGE_SIZE);
		411	page_table_unlock(as, false);
		412	}
1235	jermar	413	}
		414	}
1436	jermar	415
1235	jermar	416	/*
1436	jermar	417	* Finish TLB shootdown sequence.
1235	jermar	418	*/
1954	jermar	419	tlb_invalidate_pages(as->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
1235	jermar	420	tlb_shootdown_finalize();
1889	jermar	421
		422	/*
		423	* Invalidate software translation caches (e.g. TSB on sparc64).
		424	*/
		425	as_invalidate_translation_cache(as, area->base + pages*PAGE_SIZE, area->pages - pages);
1235	jermar	426	} else {
		427	/*
		428	* Growing the area.
		429	* Check for overlaps with other address space areas.
		430	*/
		431	if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
1380	jermar	432	mutex_unlock(&area->lock);
		433	mutex_unlock(&as->lock);
1235	jermar	434	interrupts_restore(ipl);
1306	jermar	435	return EADDRNOTAVAIL;
1235	jermar	436	}
		437	}
		438
		439	area->pages = pages;
		440
1380	jermar	441	mutex_unlock(&area->lock);
		442	mutex_unlock(&as->lock);
1235	jermar	443	interrupts_restore(ipl);
		444
1306	jermar	445	return 0;
1235	jermar	446	}
		447
1306	jermar	448	/** Destroy address space area.
		449	*
		450	* @param as Address space.
		451	* @param address Address withing the area to be deleted.
		452	*
		453	* @return Zero on success or a value from @ref errno.h on failure.
		454	*/
1780	jermar	455	int as_area_destroy(as_t *as, uintptr_t address)
1306	jermar	456	{
		457	as_area_t *area;
1780	jermar	458	uintptr_t base;
1495	jermar	459	link_t *cur;
1306	jermar	460	ipl_t ipl;
		461
		462	ipl = interrupts_disable();
1380	jermar	463	mutex_lock(&as->lock);
1306	jermar	464
		465	area = find_area_and_lock(as, address);
		466	if (!area) {
1380	jermar	467	mutex_unlock(&as->lock);
1306	jermar	468	interrupts_restore(ipl);
		469	return ENOENT;
		470	}
		471
1403	jermar	472	base = area->base;
		473
1411	jermar	474	/*
1436	jermar	475	* Start TLB shootdown sequence.
		476	*/
1889	jermar	477	tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base, area->pages);
1436	jermar	478
		479	/*
1411	jermar	480	* Visit only the pages mapped by used_space B+tree.
		481	*/
1495	jermar	482	for (cur = area->used_space.leaf_head.next; cur != &area->used_space.leaf_head; cur = cur->next) {
1411	jermar	483	btree_node_t *node;
1495	jermar	484	int i;
1403	jermar	485
1495	jermar	486	node = list_get_instance(cur, btree_node_t, leaf_link);
		487	for (i = 0; i < node->keys; i++) {
1780	jermar	488	uintptr_t b = node->key[i];
1495	jermar	489	count_t j;
1411	jermar	490	pte_t *pte;
1403	jermar	491
1495	jermar	492	for (j = 0; j < (count_t) node->value[i]; j++) {
1411	jermar	493	page_table_lock(as, false);
1495	jermar	494	pte = page_mapping_find(as, b + j*PAGE_SIZE);
1411	jermar	495	ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
1424	jermar	496	if (area->backend && area->backend->frame_free) {
		497	area->backend->frame_free(area,
1495	jermar	498	b + j*PAGE_SIZE, PTE_GET_FRAME(pte));
1403	jermar	499	}
1889	jermar	500	page_mapping_remove(as, b + j*PAGE_SIZE);
1411	jermar	501	page_table_unlock(as, false);
1306	jermar	502	}
		503	}
		504	}
1403	jermar	505
1306	jermar	506	/*
1436	jermar	507	* Finish TLB shootdown sequence.
1306	jermar	508	*/
1889	jermar	509	tlb_invalidate_pages(as->asid, area->base, area->pages);
1306	jermar	510	tlb_shootdown_finalize();
1436	jermar	511
1889	jermar	512	/*
		513	* Invalidate potential software translation caches (e.g. TSB on sparc64).
		514	*/
		515	as_invalidate_translation_cache(as, area->base, area->pages);
		516
1436	jermar	517	btree_destroy(&area->used_space);
1306	jermar	518
1309	jermar	519	area->attributes \|= AS_AREA_ATTR_PARTIAL;
1409	jermar	520
		521	if (area->sh_info)
		522	sh_info_remove_reference(area->sh_info);
		523
1380	jermar	524	mutex_unlock(&area->lock);
1306	jermar	525
		526	/*
		527	* Remove the empty area from address space.
		528	*/
1889	jermar	529	btree_remove(&as->as_area_btree, base, NULL);
1306	jermar	530
1309	jermar	531	free(area);
		532
1889	jermar	533	mutex_unlock(&as->lock);
1306	jermar	534	interrupts_restore(ipl);
		535	return 0;
		536	}
		537
1413	jermar	538	/** Share address space area with another or the same address space.
1235	jermar	539	*
1424	jermar	540	* Address space area mapping is shared with a new address space area.
		541	* If the source address space area has not been shared so far,
		542	* a new sh_info is created. The new address space area simply gets the
		543	* sh_info of the source area. The process of duplicating the
		544	* mapping is done through the backend share function.
1413	jermar	545	*
1417	jermar	546	* @param src_as Pointer to source address space.
1239	jermar	547	* @param src_base Base address of the source address space area.
1417	jermar	548	* @param acc_size Expected size of the source area.
1428	palkovsky	549	* @param dst_as Pointer to destination address space.
1417	jermar	550	* @param dst_base Target base address.
		551	* @param dst_flags_mask Destination address space area flags mask.
1235	jermar	552	*
2007	jermar	553	* @return Zero on success or ENOENT if there is no such task or if there is no
		554	* such address space area, EPERM if there was a problem in accepting the area
		555	* or ENOMEM if there was a problem in allocating destination address space
		556	* area. ENOTSUP is returned if the address space area backend does not support
		557	* sharing. It can be also returned if the architecture uses virtually indexed
		558	* caches and the source and destination areas start at pages with different
		559	* page colors.
1235	jermar	560	*/
1780	jermar	561	int as_area_share(as_t *src_as, uintptr_t src_base, size_t acc_size,
		562	as_t *dst_as, uintptr_t dst_base, int dst_flags_mask)
1235	jermar	563	{
		564	ipl_t ipl;
1239	jermar	565	int src_flags;
		566	size_t src_size;
		567	as_area_t src_area, dst_area;
1413	jermar	568	share_info_t *sh_info;
1424	jermar	569	mem_backend_t *src_backend;
		570	mem_backend_data_t src_backend_data;
1434	palkovsky	571
1235	jermar	572	ipl = interrupts_disable();
1380	jermar	573	mutex_lock(&src_as->lock);
1329	palkovsky	574	src_area = find_area_and_lock(src_as, src_base);
1239	jermar	575	if (!src_area) {
1238	jermar	576	/*
		577	* Could not find the source address space area.
		578	*/
1380	jermar	579	mutex_unlock(&src_as->lock);
1238	jermar	580	interrupts_restore(ipl);
		581	return ENOENT;
		582	}
1413	jermar	583
2007	jermar	584	#if 0 /* disable the check for now */
		585	#ifdef CONFIG_VIRT_IDX_CACHE
		586	if (PAGE_COLOR(src_area->base) != PAGE_COLOR(dst_base)) {
		587	/*
		588	* Refuse to create illegal address alias.
		589	*/
		590	mutex_unlock(&src_area->lock);
		591	mutex_unlock(&src_as->lock);
		592	interrupts_restore(ipl);
		593	return ENOTSUP;
		594	}
		595	#endif /* CONFIG_VIRT_IDX_CACHE */
		596	#endif
		597
1424	jermar	598	if (!src_area->backend \|\| !src_area->backend->share) {
1413	jermar	599	/*
1851	jermar	600	* There is no backend or the backend does not
1424	jermar	601	* know how to share the area.
1413	jermar	602	*/
		603	mutex_unlock(&src_area->lock);
		604	mutex_unlock(&src_as->lock);
		605	interrupts_restore(ipl);
		606	return ENOTSUP;
		607	}
		608
1239	jermar	609	src_size = src_area->pages * PAGE_SIZE;
		610	src_flags = src_area->flags;
1424	jermar	611	src_backend = src_area->backend;
		612	src_backend_data = src_area->backend_data;
1544	palkovsky	613
		614	/* Share the cacheable flag from the original mapping */
		615	if (src_flags & AS_AREA_CACHEABLE)
		616	dst_flags_mask \|= AS_AREA_CACHEABLE;
		617
1461	palkovsky	618	if (src_size != acc_size \|\| (src_flags & dst_flags_mask) != dst_flags_mask) {
1413	jermar	619	mutex_unlock(&src_area->lock);
		620	mutex_unlock(&src_as->lock);
1235	jermar	621	interrupts_restore(ipl);
		622	return EPERM;
		623	}
1413	jermar	624
1235	jermar	625	/*
1413	jermar	626	* Now we are committed to sharing the area.
1954	jermar	627	* First, prepare the area for sharing.
1413	jermar	628	* Then it will be safe to unlock it.
		629	*/
		630	sh_info = src_area->sh_info;
		631	if (!sh_info) {
		632	sh_info = (share_info_t *) malloc(sizeof(share_info_t), 0);
		633	mutex_initialize(&sh_info->lock);
		634	sh_info->refcount = 2;
		635	btree_create(&sh_info->pagemap);
		636	src_area->sh_info = sh_info;
		637	} else {
		638	mutex_lock(&sh_info->lock);
		639	sh_info->refcount++;
		640	mutex_unlock(&sh_info->lock);
		641	}
		642
1424	jermar	643	src_area->backend->share(src_area);
1413	jermar	644
		645	mutex_unlock(&src_area->lock);
		646	mutex_unlock(&src_as->lock);
		647
		648	/*
1239	jermar	649	* Create copy of the source address space area.
		650	* The destination area is created with AS_AREA_ATTR_PARTIAL
		651	* attribute set which prevents race condition with
		652	* preliminary as_page_fault() calls.
1417	jermar	653	* The flags of the source area are masked against dst_flags_mask
		654	* to support sharing in less privileged mode.
1235	jermar	655	*/
1461	palkovsky	656	dst_area = as_area_create(dst_as, dst_flags_mask, src_size, dst_base,
1424	jermar	657	AS_AREA_ATTR_PARTIAL, src_backend, &src_backend_data);
1239	jermar	658	if (!dst_area) {
1235	jermar	659	/*
		660	* Destination address space area could not be created.
		661	*/
1413	jermar	662	sh_info_remove_reference(sh_info);
		663
1235	jermar	664	interrupts_restore(ipl);
		665	return ENOMEM;
		666	}
		667
		668	/*
1239	jermar	669	* Now the destination address space area has been
		670	* fully initialized. Clear the AS_AREA_ATTR_PARTIAL
1413	jermar	671	* attribute and set the sh_info.
1239	jermar	672	*/
1380	jermar	673	mutex_lock(&dst_area->lock);
1239	jermar	674	dst_area->attributes &= ~AS_AREA_ATTR_PARTIAL;
1413	jermar	675	dst_area->sh_info = sh_info;
1380	jermar	676	mutex_unlock(&dst_area->lock);
1235	jermar	677
		678	interrupts_restore(ipl);
		679
		680	return 0;
		681	}
		682
1423	jermar	683	/** Check access mode for address space area.
		684	*
		685	* The address space area must be locked prior to this call.
		686	*
		687	* @param area Address space area.
		688	* @param access Access mode.
		689	*
		690	* @return False if access violates area's permissions, true otherwise.
		691	*/
		692	bool as_area_check_access(as_area_t *area, pf_access_t access)
		693	{
		694	int flagmap[] = {
		695	[PF_ACCESS_READ] = AS_AREA_READ,
		696	[PF_ACCESS_WRITE] = AS_AREA_WRITE,
		697	[PF_ACCESS_EXEC] = AS_AREA_EXEC
		698	};
		699
		700	if (!(area->flags & flagmap[access]))
		701	return false;
		702
		703	return true;
		704	}
		705
703	jermar	706	/** Handle page fault within the current address space.
		707	*
1409	jermar	708	* This is the high-level page fault handler. It decides
		709	* whether the page fault can be resolved by any backend
		710	* and if so, it invokes the backend to resolve the page
		711	* fault.
		712	*
703	jermar	713	* Interrupts are assumed disabled.
		714	*
		715	* @param page Faulting page.
1411	jermar	716	* @param access Access mode that caused the fault (i.e. read/write/exec).
1288	jermar	717	* @param istate Pointer to interrupted state.
703	jermar	718	*
1409	jermar	719	* @return AS_PF_FAULT on page fault, AS_PF_OK on success or AS_PF_DEFER if the
		720	* fault was caused by copy_to_uspace() or copy_from_uspace().
703	jermar	721	*/
1780	jermar	722	int as_page_fault(uintptr_t page, pf_access_t access, istate_t *istate)
703	jermar	723	{
1044	jermar	724	pte_t *pte;
977	jermar	725	as_area_t *area;
703	jermar	726
1380	jermar	727	if (!THREAD)
1409	jermar	728	return AS_PF_FAULT;
1380	jermar	729
703	jermar	730	ASSERT(AS);
1044	jermar	731
1380	jermar	732	mutex_lock(&AS->lock);
977	jermar	733	area = find_area_and_lock(AS, page);
703	jermar	734	if (!area) {
		735	/*
		736	* No area contained mapping for 'page'.
		737	* Signal page fault to low-level handler.
		738	*/
1380	jermar	739	mutex_unlock(&AS->lock);
1288	jermar	740	goto page_fault;
703	jermar	741	}
		742
1239	jermar	743	if (area->attributes & AS_AREA_ATTR_PARTIAL) {
		744	/*
		745	* The address space area is not fully initialized.
		746	* Avoid possible race by returning error.
		747	*/
1380	jermar	748	mutex_unlock(&area->lock);
		749	mutex_unlock(&AS->lock);
1288	jermar	750	goto page_fault;
1239	jermar	751	}
		752
1424	jermar	753	if (!area->backend \|\| !area->backend->page_fault) {
1409	jermar	754	/*
		755	* The address space area is not backed by any backend
		756	* or the backend cannot handle page faults.
		757	*/
		758	mutex_unlock(&area->lock);
		759	mutex_unlock(&AS->lock);
		760	goto page_fault;
		761	}
1179	jermar	762
1044	jermar	763	page_table_lock(AS, false);
		764
703	jermar	765	/*
1044	jermar	766	* To avoid race condition between two page faults
		767	* on the same address, we need to make sure
		768	* the mapping has not been already inserted.
		769	*/
		770	if ((pte = page_mapping_find(AS, page))) {
		771	if (PTE_PRESENT(pte)) {
1423	jermar	772	if (((access == PF_ACCESS_READ) && PTE_READABLE(pte)) \|\|
		773	(access == PF_ACCESS_WRITE && PTE_WRITABLE(pte)) \|\|
		774	(access == PF_ACCESS_EXEC && PTE_EXECUTABLE(pte))) {
		775	page_table_unlock(AS, false);
		776	mutex_unlock(&area->lock);
		777	mutex_unlock(&AS->lock);
		778	return AS_PF_OK;
		779	}
1044	jermar	780	}
		781	}
1409	jermar	782
1044	jermar	783	/*
1409	jermar	784	* Resort to the backend page fault handler.
703	jermar	785	*/
1424	jermar	786	if (area->backend->page_fault(area, page, access) != AS_PF_OK) {
1409	jermar	787	page_table_unlock(AS, false);
		788	mutex_unlock(&area->lock);
		789	mutex_unlock(&AS->lock);
		790	goto page_fault;
		791	}
703	jermar	792
1044	jermar	793	page_table_unlock(AS, false);
1380	jermar	794	mutex_unlock(&area->lock);
		795	mutex_unlock(&AS->lock);
1288	jermar	796	return AS_PF_OK;
		797
		798	page_fault:
		799	if (THREAD->in_copy_from_uspace) {
		800	THREAD->in_copy_from_uspace = false;
1780	jermar	801	istate_set_retaddr(istate, (uintptr_t) &memcpy_from_uspace_failover_address);
1288	jermar	802	} else if (THREAD->in_copy_to_uspace) {
		803	THREAD->in_copy_to_uspace = false;
1780	jermar	804	istate_set_retaddr(istate, (uintptr_t) &memcpy_to_uspace_failover_address);
1288	jermar	805	} else {
		806	return AS_PF_FAULT;
		807	}
		808
		809	return AS_PF_DEFER;
703	jermar	810	}
		811
823	jermar	812	/** Switch address spaces.
703	jermar	813	*
1380	jermar	814	* Note that this function cannot sleep as it is essentially a part of
1415	jermar	815	* scheduling. Sleeping here would lead to deadlock on wakeup.
1380	jermar	816	*
823	jermar	817	* @param old Old address space or NULL.
		818	* @param new New address space.
703	jermar	819	*/
823	jermar	820	void as_switch(as_t old, as_t new)
703	jermar	821	{
		822	ipl_t ipl;
823	jermar	823	bool needs_asid = false;
703	jermar	824
		825	ipl = interrupts_disable();
1415	jermar	826	spinlock_lock(&inactive_as_with_asid_lock);
703	jermar	827
		828	/*
823	jermar	829	* First, take care of the old address space.
		830	*/
		831	if (old) {
1380	jermar	832	mutex_lock_active(&old->lock);
1415	jermar	833	ASSERT(old->cpu_refcount);
		834	if((--old->cpu_refcount == 0) && (old != AS_KERNEL)) {
823	jermar	835	/*
		836	* The old address space is no longer active on
		837	* any processor. It can be appended to the
		838	* list of inactive address spaces with assigned
		839	* ASID.
		840	*/
		841	ASSERT(old->asid != ASID_INVALID);
		842	list_append(&old->inactive_as_with_asid_link, &inactive_as_with_asid_head);
		843	}
1380	jermar	844	mutex_unlock(&old->lock);
1890	jermar	845
		846	/*
		847	* Perform architecture-specific tasks when the address space
		848	* is being removed from the CPU.
		849	*/
		850	as_deinstall_arch(old);
823	jermar	851	}
		852
		853	/*
		854	* Second, prepare the new address space.
		855	*/
1380	jermar	856	mutex_lock_active(&new->lock);
1415	jermar	857	if ((new->cpu_refcount++ == 0) && (new != AS_KERNEL)) {
823	jermar	858	if (new->asid != ASID_INVALID)
		859	list_remove(&new->inactive_as_with_asid_link);
		860	else
		861	needs_asid = true; /* defer call to asid_get() until new->lock is released */
		862	}
		863	SET_PTL0_ADDRESS(new->page_table);
1380	jermar	864	mutex_unlock(&new->lock);
823	jermar	865
		866	if (needs_asid) {
		867	/*
		868	* Allocation of new ASID was deferred
		869	* until now in order to avoid deadlock.
		870	*/
		871	asid_t asid;
		872
		873	asid = asid_get();
1380	jermar	874	mutex_lock_active(&new->lock);
823	jermar	875	new->asid = asid;
1380	jermar	876	mutex_unlock(&new->lock);
823	jermar	877	}
1415	jermar	878	spinlock_unlock(&inactive_as_with_asid_lock);
823	jermar	879	interrupts_restore(ipl);
		880
		881	/*
703	jermar	882	* Perform architecture-specific steps.
727	jermar	883	* (e.g. write ASID to hardware register etc.)
703	jermar	884	*/
823	jermar	885	as_install_arch(new);
703	jermar	886
823	jermar	887	AS = new;
703	jermar	888	}
754	jermar	889
1235	jermar	890	/** Convert address space area flags to page flags.
754	jermar	891	*
1235	jermar	892	* @param aflags Flags of some address space area.
754	jermar	893	*
1235	jermar	894	* @return Flags to be passed to page_mapping_insert().
754	jermar	895	*/
1235	jermar	896	int area_flags_to_page_flags(int aflags)
754	jermar	897	{
		898	int flags;
		899
1178	jermar	900	flags = PAGE_USER \| PAGE_PRESENT;
754	jermar	901
1235	jermar	902	if (aflags & AS_AREA_READ)
1026	jermar	903	flags \|= PAGE_READ;
		904
1235	jermar	905	if (aflags & AS_AREA_WRITE)
1026	jermar	906	flags \|= PAGE_WRITE;
		907
1235	jermar	908	if (aflags & AS_AREA_EXEC)
1026	jermar	909	flags \|= PAGE_EXEC;
		910
1424	jermar	911	if (aflags & AS_AREA_CACHEABLE)
1178	jermar	912	flags \|= PAGE_CACHEABLE;
		913
754	jermar	914	return flags;
		915	}
756	jermar	916
1235	jermar	917	/** Compute flags for virtual address translation subsytem.
		918	*
		919	* The address space area must be locked.
		920	* Interrupts must be disabled.
		921	*
		922	* @param a Address space area.
		923	*
		924	* @return Flags to be used in page_mapping_insert().
		925	*/
1409	jermar	926	int as_area_get_flags(as_area_t *a)
1235	jermar	927	{
		928	return area_flags_to_page_flags(a->flags);
		929	}
		930
756	jermar	931	/** Create page table.
		932	*
		933	* Depending on architecture, create either address space
		934	* private or global page table.
		935	*
		936	* @param flags Flags saying whether the page table is for kernel address space.
		937	*
		938	* @return First entry of the page table.
		939	*/
		940	pte_t *page_table_create(int flags)
		941	{
		942	ASSERT(as_operations);
		943	ASSERT(as_operations->page_table_create);
		944
		945	return as_operations->page_table_create(flags);
		946	}
977	jermar	947
1468	jermar	948	/** Destroy page table.
		949	*
		950	* Destroy page table in architecture specific way.
		951	*
		952	* @param page_table Physical address of PTL0.
		953	*/
		954	void page_table_destroy(pte_t *page_table)
		955	{
		956	ASSERT(as_operations);
		957	ASSERT(as_operations->page_table_destroy);
		958
		959	as_operations->page_table_destroy(page_table);
		960	}
		961
1044	jermar	962	/** Lock page table.
		963	*
		964	* This function should be called before any page_mapping_insert(),
		965	* page_mapping_remove() and page_mapping_find().
		966	*
		967	* Locking order is such that address space areas must be locked
		968	* prior to this call. Address space can be locked prior to this
		969	* call in which case the lock argument is false.
		970	*
		971	* @param as Address space.
1248	jermar	972	* @param lock If false, do not attempt to lock as->lock.
1044	jermar	973	*/
		974	void page_table_lock(as_t *as, bool lock)
		975	{
		976	ASSERT(as_operations);
		977	ASSERT(as_operations->page_table_lock);
		978
		979	as_operations->page_table_lock(as, lock);
		980	}
		981
		982	/** Unlock page table.
		983	*
		984	* @param as Address space.
1248	jermar	985	* @param unlock If false, do not attempt to unlock as->lock.
1044	jermar	986	*/
		987	void page_table_unlock(as_t *as, bool unlock)
		988	{
		989	ASSERT(as_operations);
		990	ASSERT(as_operations->page_table_unlock);
		991
		992	as_operations->page_table_unlock(as, unlock);
		993	}
		994
977	jermar	995
		996	/** Find address space area and lock it.
		997	*
		998	* The address space must be locked and interrupts must be disabled.
		999	*
		1000	* @param as Address space.
		1001	* @param va Virtual address.
		1002	*
		1003	* @return Locked address space area containing va on success or NULL on failure.
		1004	*/
1780	jermar	1005	as_area_t find_area_and_lock(as_t as, uintptr_t va)
977	jermar	1006	{
		1007	as_area_t *a;
1147	jermar	1008	btree_node_t leaf, lnode;
		1009	int i;
977	jermar	1010
1147	jermar	1011	a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
		1012	if (a) {
		1013	/* va is the base address of an address space area */
1380	jermar	1014	mutex_lock(&a->lock);
1147	jermar	1015	return a;
		1016	}
		1017
		1018	/*
1150	jermar	1019	* Search the leaf node and the righmost record of its left neighbour
1147	jermar	1020	* to find out whether this is a miss or va belongs to an address
		1021	* space area found there.
		1022	*/
		1023
		1024	/* First, search the leaf node itself. */
		1025	for (i = 0; i < leaf->keys; i++) {
		1026	a = (as_area_t *) leaf->value[i];
1380	jermar	1027	mutex_lock(&a->lock);
1147	jermar	1028	if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
		1029	return a;
		1030	}
1380	jermar	1031	mutex_unlock(&a->lock);
1147	jermar	1032	}
977	jermar	1033
1147	jermar	1034	/*
1150	jermar	1035	* Second, locate the left neighbour and test its last record.
1148	jermar	1036	* Because of its position in the B+tree, it must have base < va.
1147	jermar	1037	*/
1150	jermar	1038	if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
1147	jermar	1039	a = (as_area_t *) lnode->value[lnode->keys - 1];
1380	jermar	1040	mutex_lock(&a->lock);
1147	jermar	1041	if (va < a->base + a->pages * PAGE_SIZE) {
1048	jermar	1042	return a;
1147	jermar	1043	}
1380	jermar	1044	mutex_unlock(&a->lock);
977	jermar	1045	}
		1046
		1047	return NULL;
		1048	}
1048	jermar	1049
		1050	/** Check area conflicts with other areas.
		1051	*
		1052	* The address space must be locked and interrupts must be disabled.
		1053	*
		1054	* @param as Address space.
		1055	* @param va Starting virtual address of the area being tested.
		1056	* @param size Size of the area being tested.
		1057	* @param avoid_area Do not touch this area.
		1058	*
		1059	* @return True if there is no conflict, false otherwise.
		1060	*/
1780	jermar	1061	bool check_area_conflicts(as_t as, uintptr_t va, size_t size, as_area_t avoid_area)
1048	jermar	1062	{
		1063	as_area_t *a;
1147	jermar	1064	btree_node_t leaf, node;
		1065	int i;
1048	jermar	1066
1070	jermar	1067	/*
		1068	* We don't want any area to have conflicts with NULL page.
		1069	*/
		1070	if (overlaps(va, size, NULL, PAGE_SIZE))
		1071	return false;
		1072
1147	jermar	1073	/*
		1074	* The leaf node is found in O(log n), where n is proportional to
		1075	* the number of address space areas belonging to as.
		1076	* The check for conflicts is then attempted on the rightmost
1150	jermar	1077	* record in the left neighbour, the leftmost record in the right
		1078	* neighbour and all records in the leaf node itself.
1147	jermar	1079	*/
1048	jermar	1080
1147	jermar	1081	if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
		1082	if (a != avoid_area)
		1083	return false;
		1084	}
		1085
		1086	/* First, check the two border cases. */
1150	jermar	1087	if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
1147	jermar	1088	a = (as_area_t *) node->value[node->keys - 1];
1380	jermar	1089	mutex_lock(&a->lock);
1147	jermar	1090	if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380	jermar	1091	mutex_unlock(&a->lock);
1147	jermar	1092	return false;
		1093	}
1380	jermar	1094	mutex_unlock(&a->lock);
1147	jermar	1095	}
1150	jermar	1096	if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) {
1147	jermar	1097	a = (as_area_t *) node->value[0];
1380	jermar	1098	mutex_lock(&a->lock);
1147	jermar	1099	if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380	jermar	1100	mutex_unlock(&a->lock);
1147	jermar	1101	return false;
		1102	}
1380	jermar	1103	mutex_unlock(&a->lock);
1147	jermar	1104	}
		1105
		1106	/* Second, check the leaf node. */
		1107	for (i = 0; i < leaf->keys; i++) {
		1108	a = (as_area_t *) leaf->value[i];
		1109
1048	jermar	1110	if (a == avoid_area)
		1111	continue;
1147	jermar	1112
1380	jermar	1113	mutex_lock(&a->lock);
1147	jermar	1114	if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380	jermar	1115	mutex_unlock(&a->lock);
1147	jermar	1116	return false;
		1117	}
1380	jermar	1118	mutex_unlock(&a->lock);
1048	jermar	1119	}
		1120
1070	jermar	1121	/*
		1122	* So far, the area does not conflict with other areas.
		1123	* Check if it doesn't conflict with kernel address space.
		1124	*/
		1125	if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
		1126	return !overlaps(va, size,
		1127	KERNEL_ADDRESS_SPACE_START, KERNEL_ADDRESS_SPACE_END-KERNEL_ADDRESS_SPACE_START);
		1128	}
		1129
1048	jermar	1130	return true;
		1131	}
1235	jermar	1132
1380	jermar	1133	/** Return size of the address space area with given base. */
1780	jermar	1134	size_t as_get_size(uintptr_t base)
1329	palkovsky	1135	{
		1136	ipl_t ipl;
		1137	as_area_t *src_area;
		1138	size_t size;
		1139
		1140	ipl = interrupts_disable();
		1141	src_area = find_area_and_lock(AS, base);
		1142	if (src_area){
		1143	size = src_area->pages * PAGE_SIZE;
1380	jermar	1144	mutex_unlock(&src_area->lock);
1329	palkovsky	1145	} else {
		1146	size = 0;
		1147	}
		1148	interrupts_restore(ipl);
		1149	return size;
		1150	}
		1151
1387	jermar	1152	/** Mark portion of address space area as used.
		1153	*
		1154	* The address space area must be already locked.
		1155	*
		1156	* @param a Address space area.
		1157	* @param page First page to be marked.
		1158	* @param count Number of page to be marked.
		1159	*
		1160	* @return 0 on failure and 1 on success.
		1161	*/
1780	jermar	1162	int used_space_insert(as_area_t *a, uintptr_t page, count_t count)
1387	jermar	1163	{
		1164	btree_node_t leaf, node;
		1165	count_t pages;
		1166	int i;
		1167
		1168	ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
		1169	ASSERT(count);
		1170
		1171	pages = (count_t) btree_search(&a->used_space, page, &leaf);
		1172	if (pages) {
		1173	/*
		1174	* We hit the beginning of some used space.
		1175	*/
		1176	return 0;
		1177	}
		1178
1437	jermar	1179	if (!leaf->keys) {
		1180	btree_insert(&a->used_space, page, (void *) count, leaf);
		1181	return 1;
		1182	}
		1183
1387	jermar	1184	node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
		1185	if (node) {
1780	jermar	1186	uintptr_t left_pg = node->key[node->keys - 1], right_pg = leaf->key[0];
1387	jermar	1187	count_t left_cnt = (count_t) node->value[node->keys - 1], right_cnt = (count_t) leaf->value[0];
		1188
		1189	/*
		1190	* Examine the possibility that the interval fits
		1191	* somewhere between the rightmost interval of
		1192	* the left neigbour and the first interval of the leaf.
		1193	*/
		1194
		1195	if (page >= right_pg) {
		1196	/* Do nothing. */
		1197	} else if (overlaps(page, countPAGE_SIZE, left_pg, left_cntPAGE_SIZE)) {
		1198	/* The interval intersects with the left interval. */
		1199	return 0;
		1200	} else if (overlaps(page, countPAGE_SIZE, right_pg, right_cntPAGE_SIZE)) {
		1201	/* The interval intersects with the right interval. */
		1202	return 0;
		1203	} else if ((page == left_pg + left_cntPAGE_SIZE) && (page + countPAGE_SIZE == right_pg)) {
		1204	/* The interval can be added by merging the two already present intervals. */
1403	jermar	1205	node->value[node->keys - 1] += count + right_cnt;
1387	jermar	1206	btree_remove(&a->used_space, right_pg, leaf);
		1207	return 1;
		1208	} else if (page == left_pg + left_cnt*PAGE_SIZE) {
		1209	/* The interval can be added by simply growing the left interval. */
1403	jermar	1210	node->value[node->keys - 1] += count;
1387	jermar	1211	return 1;
		1212	} else if (page + count*PAGE_SIZE == right_pg) {
		1213	/*
		1214	* The interval can be addded by simply moving base of the right
		1215	* interval down and increasing its size accordingly.
		1216	*/
1403	jermar	1217	leaf->value[0] += count;
1387	jermar	1218	leaf->key[0] = page;
		1219	return 1;
		1220	} else {
		1221	/*
		1222	* The interval is between both neigbouring intervals,
		1223	* but cannot be merged with any of them.
		1224	*/
		1225	btree_insert(&a->used_space, page, (void *) count, leaf);
		1226	return 1;
		1227	}
		1228	} else if (page < leaf->key[0]) {
1780	jermar	1229	uintptr_t right_pg = leaf->key[0];
1387	jermar	1230	count_t right_cnt = (count_t) leaf->value[0];
		1231
		1232	/*
		1233	* Investigate the border case in which the left neighbour does not
		1234	* exist but the interval fits from the left.
		1235	*/
		1236
		1237	if (overlaps(page, countPAGE_SIZE, right_pg, right_cntPAGE_SIZE)) {
		1238	/* The interval intersects with the right interval. */
		1239	return 0;
		1240	} else if (page + count*PAGE_SIZE == right_pg) {
		1241	/*
		1242	* The interval can be added by moving the base of the right interval down
		1243	* and increasing its size accordingly.
		1244	*/
		1245	leaf->key[0] = page;
1403	jermar	1246	leaf->value[0] += count;
1387	jermar	1247	return 1;
		1248	} else {
		1249	/*
		1250	* The interval doesn't adjoin with the right interval.
		1251	* It must be added individually.
		1252	*/
		1253	btree_insert(&a->used_space, page, (void *) count, leaf);
		1254	return 1;
		1255	}
		1256	}
		1257
		1258	node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
		1259	if (node) {
1780	jermar	1260	uintptr_t left_pg = leaf->key[leaf->keys - 1], right_pg = node->key[0];
1387	jermar	1261	count_t left_cnt = (count_t) leaf->value[leaf->keys - 1], right_cnt = (count_t) node->value[0];
		1262
		1263	/*
		1264	* Examine the possibility that the interval fits
		1265	* somewhere between the leftmost interval of
		1266	* the right neigbour and the last interval of the leaf.
		1267	*/
		1268
		1269	if (page < left_pg) {
		1270	/* Do nothing. */
		1271	} else if (overlaps(page, countPAGE_SIZE, left_pg, left_cntPAGE_SIZE)) {
		1272	/* The interval intersects with the left interval. */
		1273	return 0;
		1274	} else if (overlaps(page, countPAGE_SIZE, right_pg, right_cntPAGE_SIZE)) {
		1275	/* The interval intersects with the right interval. */
		1276	return 0;
		1277	} else if ((page == left_pg + left_cntPAGE_SIZE) && (page + countPAGE_SIZE == right_pg)) {
		1278	/* The interval can be added by merging the two already present intervals. */
1403	jermar	1279	leaf->value[leaf->keys - 1] += count + right_cnt;
1387	jermar	1280	btree_remove(&a->used_space, right_pg, node);
		1281	return 1;
		1282	} else if (page == left_pg + left_cnt*PAGE_SIZE) {
		1283	/* The interval can be added by simply growing the left interval. */
1403	jermar	1284	leaf->value[leaf->keys - 1] += count;
1387	jermar	1285	return 1;
		1286	} else if (page + count*PAGE_SIZE == right_pg) {
		1287	/*
		1288	* The interval can be addded by simply moving base of the right
		1289	* interval down and increasing its size accordingly.
		1290	*/
1403	jermar	1291	node->value[0] += count;
1387	jermar	1292	node->key[0] = page;
		1293	return 1;
		1294	} else {
		1295	/*
		1296	* The interval is between both neigbouring intervals,
		1297	* but cannot be merged with any of them.
		1298	*/
		1299	btree_insert(&a->used_space, page, (void *) count, leaf);
		1300	return 1;
		1301	}
		1302	} else if (page >= leaf->key[leaf->keys - 1]) {
1780	jermar	1303	uintptr_t left_pg = leaf->key[leaf->keys - 1];
1387	jermar	1304	count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
		1305
		1306	/*
		1307	* Investigate the border case in which the right neighbour does not
		1308	* exist but the interval fits from the right.
		1309	*/
		1310
		1311	if (overlaps(page, countPAGE_SIZE, left_pg, left_cntPAGE_SIZE)) {
1403	jermar	1312	/* The interval intersects with the left interval. */
1387	jermar	1313	return 0;
		1314	} else if (left_pg + left_cnt*PAGE_SIZE == page) {
		1315	/* The interval can be added by growing the left interval. */
1403	jermar	1316	leaf->value[leaf->keys - 1] += count;
1387	jermar	1317	return 1;
		1318	} else {
		1319	/*
		1320	* The interval doesn't adjoin with the left interval.
		1321	* It must be added individually.
		1322	*/
		1323	btree_insert(&a->used_space, page, (void *) count, leaf);
		1324	return 1;
		1325	}
		1326	}
		1327
		1328	/*
		1329	* Note that if the algorithm made it thus far, the interval can fit only
		1330	* between two other intervals of the leaf. The two border cases were already
		1331	* resolved.
		1332	*/
		1333	for (i = 1; i < leaf->keys; i++) {
		1334	if (page < leaf->key[i]) {
1780	jermar	1335	uintptr_t left_pg = leaf->key[i - 1], right_pg = leaf->key[i];
1387	jermar	1336	count_t left_cnt = (count_t) leaf->value[i - 1], right_cnt = (count_t) leaf->value[i];
		1337
		1338	/*
		1339	* The interval fits between left_pg and right_pg.
		1340	*/
		1341
		1342	if (overlaps(page, countPAGE_SIZE, left_pg, left_cntPAGE_SIZE)) {
		1343	/* The interval intersects with the left interval. */
		1344	return 0;
		1345	} else if (overlaps(page, countPAGE_SIZE, right_pg, right_cntPAGE_SIZE)) {
		1346	/* The interval intersects with the right interval. */
		1347	return 0;
		1348	} else if ((page == left_pg + left_cntPAGE_SIZE) && (page + countPAGE_SIZE == right_pg)) {
		1349	/* The interval can be added by merging the two already present intervals. */
1403	jermar	1350	leaf->value[i - 1] += count + right_cnt;
1387	jermar	1351	btree_remove(&a->used_space, right_pg, leaf);
		1352	return 1;
		1353	} else if (page == left_pg + left_cnt*PAGE_SIZE) {
		1354	/* The interval can be added by simply growing the left interval. */
1403	jermar	1355	leaf->value[i - 1] += count;
1387	jermar	1356	return 1;
		1357	} else if (page + count*PAGE_SIZE == right_pg) {
		1358	/*
		1359	* The interval can be addded by simply moving base of the right
		1360	* interval down and increasing its size accordingly.
		1361	*/
1403	jermar	1362	leaf->value[i] += count;
1387	jermar	1363	leaf->key[i] = page;
		1364	return 1;
		1365	} else {
		1366	/*
		1367	* The interval is between both neigbouring intervals,
		1368	* but cannot be merged with any of them.
		1369	*/
		1370	btree_insert(&a->used_space, page, (void *) count, leaf);
		1371	return 1;
		1372	}
		1373	}
		1374	}
		1375
1735	decky	1376	panic("Inconsistency detected while adding %d pages of used space at %p.\n", count, page);
1387	jermar	1377	}
		1378
		1379	/** Mark portion of address space area as unused.
		1380	*
		1381	* The address space area must be already locked.
		1382	*
		1383	* @param a Address space area.
		1384	* @param page First page to be marked.
		1385	* @param count Number of page to be marked.
		1386	*
		1387	* @return 0 on failure and 1 on success.
		1388	*/
1780	jermar	1389	int used_space_remove(as_area_t *a, uintptr_t page, count_t count)
1387	jermar	1390	{
		1391	btree_node_t leaf, node;
		1392	count_t pages;
		1393	int i;
		1394
		1395	ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
		1396	ASSERT(count);
		1397
		1398	pages = (count_t) btree_search(&a->used_space, page, &leaf);
		1399	if (pages) {
		1400	/*
		1401	* We are lucky, page is the beginning of some interval.
		1402	*/
		1403	if (count > pages) {
		1404	return 0;
		1405	} else if (count == pages) {
		1406	btree_remove(&a->used_space, page, leaf);
1403	jermar	1407	return 1;
1387	jermar	1408	} else {
		1409	/*
		1410	* Find the respective interval.
		1411	* Decrease its size and relocate its start address.
		1412	*/
		1413	for (i = 0; i < leaf->keys; i++) {
		1414	if (leaf->key[i] == page) {
		1415	leaf->key[i] += count*PAGE_SIZE;
1403	jermar	1416	leaf->value[i] -= count;
1387	jermar	1417	return 1;
		1418	}
		1419	}
		1420	goto error;
		1421	}
		1422	}
		1423
		1424	node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
		1425	if (node && page < leaf->key[0]) {
1780	jermar	1426	uintptr_t left_pg = node->key[node->keys - 1];
1387	jermar	1427	count_t left_cnt = (count_t) node->value[node->keys - 1];
		1428
		1429	if (overlaps(left_pg, left_cntPAGE_SIZE, page, countPAGE_SIZE)) {
		1430	if (page + countPAGE_SIZE == left_pg + left_cntPAGE_SIZE) {
		1431	/*
		1432	* The interval is contained in the rightmost interval
		1433	* of the left neighbour and can be removed by
		1434	* updating the size of the bigger interval.
		1435	*/
1403	jermar	1436	node->value[node->keys - 1] -= count;
1387	jermar	1437	return 1;
		1438	} else if (page + countPAGE_SIZE < left_pg + left_cntPAGE_SIZE) {
1403	jermar	1439	count_t new_cnt;
1387	jermar	1440
		1441	/*
		1442	* The interval is contained in the rightmost interval
		1443	* of the left neighbour but its removal requires
		1444	* both updating the size of the original interval and
		1445	* also inserting a new interval.
		1446	*/
1403	jermar	1447	new_cnt = ((left_pg + left_cntPAGE_SIZE) - (page + countPAGE_SIZE)) >> PAGE_WIDTH;
		1448	node->value[node->keys - 1] -= count + new_cnt;
1387	jermar	1449	btree_insert(&a->used_space, page + countPAGE_SIZE, (void ) new_cnt, leaf);
		1450	return 1;
		1451	}
		1452	}
		1453	return 0;
		1454	} else if (page < leaf->key[0]) {
		1455	return 0;
		1456	}
		1457
		1458	if (page > leaf->key[leaf->keys - 1]) {
1780	jermar	1459	uintptr_t left_pg = leaf->key[leaf->keys - 1];
1387	jermar	1460	count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
		1461
		1462	if (overlaps(left_pg, left_cntPAGE_SIZE, page, countPAGE_SIZE)) {
		1463	if (page + countPAGE_SIZE == left_pg + left_cntPAGE_SIZE) {
		1464	/*
		1465	* The interval is contained in the rightmost interval
		1466	* of the leaf and can be removed by updating the size
		1467	* of the bigger interval.
		1468	*/
1403	jermar	1469	leaf->value[leaf->keys - 1] -= count;
1387	jermar	1470	return 1;
		1471	} else if (page + countPAGE_SIZE < left_pg + left_cntPAGE_SIZE) {
1403	jermar	1472	count_t new_cnt;
1387	jermar	1473
		1474	/*
		1475	* The interval is contained in the rightmost interval
		1476	* of the leaf but its removal requires both updating
		1477	* the size of the original interval and
		1478	* also inserting a new interval.
		1479	*/
1403	jermar	1480	new_cnt = ((left_pg + left_cntPAGE_SIZE) - (page + countPAGE_SIZE)) >> PAGE_WIDTH;
		1481	leaf->value[leaf->keys - 1] -= count + new_cnt;
1387	jermar	1482	btree_insert(&a->used_space, page + countPAGE_SIZE, (void ) new_cnt, leaf);
		1483	return 1;
		1484	}
		1485	}
		1486	return 0;
		1487	}
		1488
		1489	/*
		1490	* The border cases have been already resolved.
		1491	* Now the interval can be only between intervals of the leaf.
		1492	*/
		1493	for (i = 1; i < leaf->keys - 1; i++) {
		1494	if (page < leaf->key[i]) {
1780	jermar	1495	uintptr_t left_pg = leaf->key[i - 1];
1387	jermar	1496	count_t left_cnt = (count_t) leaf->value[i - 1];
		1497
		1498	/*
		1499	* Now the interval is between intervals corresponding to (i - 1) and i.
		1500	*/
		1501	if (overlaps(left_pg, left_cntPAGE_SIZE, page, countPAGE_SIZE)) {
		1502	if (page + countPAGE_SIZE == left_pg + left_cntPAGE_SIZE) {
		1503	/*
		1504	* The interval is contained in the interval (i - 1)
		1505	* of the leaf and can be removed by updating the size
		1506	* of the bigger interval.
		1507	*/
1403	jermar	1508	leaf->value[i - 1] -= count;
1387	jermar	1509	return 1;
		1510	} else if (page + countPAGE_SIZE < left_pg + left_cntPAGE_SIZE) {
1403	jermar	1511	count_t new_cnt;
1387	jermar	1512
		1513	/*
		1514	* The interval is contained in the interval (i - 1)
		1515	* of the leaf but its removal requires both updating
		1516	* the size of the original interval and
		1517	* also inserting a new interval.
		1518	*/
1403	jermar	1519	new_cnt = ((left_pg + left_cntPAGE_SIZE) - (page + countPAGE_SIZE)) >> PAGE_WIDTH;
		1520	leaf->value[i - 1] -= count + new_cnt;
1387	jermar	1521	btree_insert(&a->used_space, page + countPAGE_SIZE, (void ) new_cnt, leaf);
		1522	return 1;
		1523	}
		1524	}
		1525	return 0;
		1526	}
		1527	}
		1528
		1529	error:
1735	decky	1530	panic("Inconsistency detected while removing %d pages of used space from %p.\n", count, page);
1387	jermar	1531	}
		1532
1409	jermar	1533	/** Remove reference to address space area share info.
		1534	*
		1535	* If the reference count drops to 0, the sh_info is deallocated.
		1536	*
		1537	* @param sh_info Pointer to address space area share info.
		1538	*/
		1539	void sh_info_remove_reference(share_info_t *sh_info)
		1540	{
		1541	bool dealloc = false;
		1542
		1543	mutex_lock(&sh_info->lock);
		1544	ASSERT(sh_info->refcount);
		1545	if (--sh_info->refcount == 0) {
		1546	dealloc = true;
1495	jermar	1547	link_t *cur;
1409	jermar	1548
		1549	/*
		1550	* Now walk carefully the pagemap B+tree and free/remove
		1551	* reference from all frames found there.
		1552	*/
1495	jermar	1553	for (cur = sh_info->pagemap.leaf_head.next; cur != &sh_info->pagemap.leaf_head; cur = cur->next) {
1409	jermar	1554	btree_node_t *node;
1495	jermar	1555	int i;
1409	jermar	1556
1495	jermar	1557	node = list_get_instance(cur, btree_node_t, leaf_link);
		1558	for (i = 0; i < node->keys; i++)
1780	jermar	1559	frame_free((uintptr_t) node->value[i]);
1409	jermar	1560	}
		1561
		1562	}
		1563	mutex_unlock(&sh_info->lock);
		1564
		1565	if (dealloc) {
		1566	btree_destroy(&sh_info->pagemap);
		1567	free(sh_info);
		1568	}
		1569	}
		1570
1235	jermar	1571	/*
		1572	* Address space related syscalls.
		1573	*/
		1574
		1575	/** Wrapper for as_area_create(). */
1780	jermar	1576	unative_t sys_as_area_create(uintptr_t address, size_t size, int flags)
1235	jermar	1577	{
1424	jermar	1578	if (as_area_create(AS, flags \| AS_AREA_CACHEABLE, size, address, AS_AREA_ATTR_NONE, &anon_backend, NULL))
1780	jermar	1579	return (unative_t) address;
1235	jermar	1580	else
1780	jermar	1581	return (unative_t) -1;
1235	jermar	1582	}
		1583
1793	jermar	1584	/** Wrapper for as_area_resize(). */
1780	jermar	1585	unative_t sys_as_area_resize(uintptr_t address, size_t size, int flags)
1235	jermar	1586	{
1780	jermar	1587	return (unative_t) as_area_resize(AS, address, size, 0);
1235	jermar	1588	}
		1589
1793	jermar	1590	/** Wrapper for as_area_destroy(). */
1780	jermar	1591	unative_t sys_as_area_destroy(uintptr_t address)
1306	jermar	1592	{
1780	jermar	1593	return (unative_t) as_area_destroy(AS, address);
1306	jermar	1594	}
1702	cejka	1595
1914	jermar	1596	/** Print out information about address space.
		1597	*
		1598	* @param as Address space.
		1599	*/
		1600	void as_print(as_t *as)
		1601	{
		1602	ipl_t ipl;
		1603
		1604	ipl = interrupts_disable();
		1605	mutex_lock(&as->lock);
		1606
		1607	/* print out info about address space areas */
		1608	link_t *cur;
		1609	for (cur = as->as_area_btree.leaf_head.next; cur != &as->as_area_btree.leaf_head; cur = cur->next) {
1915	jermar	1610	btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link);
1914	jermar	1611
		1612	int i;
		1613	for (i = 0; i < node->keys; i++) {
1915	jermar	1614	as_area_t *area = node->value[i];
1914	jermar	1615
		1616	mutex_lock(&area->lock);
		1617	printf("as_area: %p, base=%p, pages=%d (%p - %p)\n",
		1618	area, area->base, area->pages, area->base, area->base + area->pages*PAGE_SIZE);
		1619	mutex_unlock(&area->lock);
		1620	}
		1621	}
		1622
		1623	mutex_unlock(&as->lock);
		1624	interrupts_restore(ipl);
		1625	}
		1626
1757	jermar	1627	/** @}
1702	cejka	1628	*/

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/mm/as.c @ 4093 – Rev 2007