[apple/xnu.git] / osfmk / vm / vm_map_store.c

/*
 * Copyright (c) 2009 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#include <mach/sdt.h>
#include <vm/vm_map_store.h>
#include <vm/vm_pageout.h> /* for vm_debug_events */

#if MACH_ASSERT
boolean_t
first_free_is_valid_store( vm_map_t map )
{
	return(first_free_is_valid_ll( map ));
}
#endif

boolean_t
vm_map_store_has_RB_support( struct vm_map_header *hdr )
{
	if ((void*)hdr->rb_head_store.rbh_root == (void*)(int)SKIP_RB_TREE) {
		return FALSE;
	}
	return TRUE;
}

void
vm_map_store_init( struct vm_map_header *hdr )
{
	vm_map_store_init_ll( hdr );
#ifdef VM_MAP_STORE_USE_RB
	if (vm_map_store_has_RB_support( hdr )) {
		vm_map_store_init_rb( hdr );
	}
#endif
}

boolean_t
vm_map_store_lookup_entry(
	register vm_map_t		map,
	register vm_map_offset_t	address,
	vm_map_entry_t		*entry)		/* OUT */
{
#ifdef VM_MAP_STORE_USE_LL
	return (vm_map_store_lookup_entry_ll( map, address, entry ));
#elif defined VM_MAP_STORE_USE_RB
	if (vm_map_store_has_RB_support( &map->hdr )) {
		return (vm_map_store_lookup_entry_rb( map, address, entry ));
	} else {
		panic("VM map lookups need RB tree support.\n");
		return FALSE; /* For compiler warning.*/
	}
#endif
}

void
vm_map_store_update( vm_map_t map, vm_map_entry_t entry, int update_type )
{
	switch (update_type) {
		case VM_MAP_ENTRY_CREATE:
			break;
		case VM_MAP_ENTRY_DELETE:
			if((map->holelistenabled == FALSE) && ((entry) == (map)->first_free)) {
				(map)->first_free = vm_map_to_entry(map);
			}
			if((entry) == (map)->hint) {
				(map)->hint = vm_map_to_entry(map);
			}
			break;
		default:
			break;
	}
}

void	vm_map_store_copy_insert( vm_map_t map, vm_map_entry_t after_where, vm_map_copy_t copy)
{
	if (__improbable(vm_debug_events)) {
		vm_map_entry_t entry;
		for (entry = vm_map_copy_first_entry(copy); entry != vm_map_copy_to_entry(copy); entry = entry->vme_next) {
			DTRACE_VM4(map_entry_link_copy, vm_map_t, map, vm_map_entry_t, entry, vm_address_t, entry->links.start, vm_address_t, entry->links.end);
		}
	}

	if (map->holelistenabled) {
		vm_map_entry_t entry = NULL;

		entry = vm_map_copy_first_entry(copy);
		while (entry != vm_map_copy_to_entry(copy)) {
			vm_map_store_update_first_free(map, entry, TRUE);
			entry = entry->vme_next;
		}
	}

	vm_map_store_copy_insert_ll(map, after_where, copy);
#ifdef VM_MAP_STORE_USE_RB
	if (vm_map_store_has_RB_support( &map->hdr )) {
		vm_map_store_copy_insert_rb(map, after_where, copy);
	}
#endif
}

/*
 *	vm_map_entry_{un,}link:
 *
 *	Insert/remove entries from maps (or map copies).
 *	The _vm_map_store_entry_{un,}link variants are used at
 *	some places where updating first_free is not needed &
 *	copy maps are being modified. Also note the first argument
 *	is the map header.
 *	Modifying the vm_map_store_entry_{un,}link functions to 
 *	deal with these call sites made the interface confusing
 *	and clunky.
 */

void
_vm_map_store_entry_link( struct vm_map_header * mapHdr, vm_map_entry_t after_where, vm_map_entry_t entry)
{
	assert(entry->vme_start < entry->vme_end);
	if (__improbable(vm_debug_events))
		DTRACE_VM4(map_entry_link, vm_map_t, (char *)mapHdr - sizeof (lck_rw_t), vm_map_entry_t, entry, vm_address_t, entry->links.start, vm_address_t, entry->links.end);

	vm_map_store_entry_link_ll(mapHdr, after_where, entry);
#ifdef VM_MAP_STORE_USE_RB
	if (vm_map_store_has_RB_support( mapHdr )) {
		vm_map_store_entry_link_rb(mapHdr, after_where, entry);
	}
#endif
#if MAP_ENTRY_INSERTION_DEBUG
	fastbacktrace(&entry->vme_insertion_bt[0],
		      (sizeof (entry->vme_insertion_bt) / sizeof (uintptr_t)));
#endif
}

void
vm_map_store_entry_link( vm_map_t map, vm_map_entry_t after_where, vm_map_entry_t entry)
{
	vm_map_t VMEL_map;
	vm_map_entry_t VMEL_entry;
	VMEL_map = (map);
	VMEL_entry = (entry);
	
	_vm_map_store_entry_link(&VMEL_map->hdr, after_where, VMEL_entry);
	if( VMEL_map->disable_vmentry_reuse == TRUE ) {
		UPDATE_HIGHEST_ENTRY_END( VMEL_map, VMEL_entry);
	} else {
		update_first_free_ll(VMEL_map, VMEL_map->first_free);
#ifdef VM_MAP_STORE_USE_RB
		if (vm_map_store_has_RB_support( &VMEL_map->hdr )) {
			update_first_free_rb(VMEL_map, entry, TRUE);
		}
#endif
	}
}

void
_vm_map_store_entry_unlink( struct vm_map_header * mapHdr, vm_map_entry_t entry)
{
	if (__improbable(vm_debug_events))
		DTRACE_VM4(map_entry_unlink, vm_map_t, (char *)mapHdr - sizeof (lck_rw_t), vm_map_entry_t, entry, vm_address_t, entry->links.start, vm_address_t, entry->links.end);

	vm_map_store_entry_unlink_ll(mapHdr, entry);
#ifdef VM_MAP_STORE_USE_RB
	if (vm_map_store_has_RB_support( mapHdr )) {
		vm_map_store_entry_unlink_rb(mapHdr, entry);
	}
#endif
}

void
vm_map_store_entry_unlink( vm_map_t map, vm_map_entry_t entry)
{
	vm_map_t VMEU_map;
	vm_map_entry_t VMEU_entry = NULL;
	vm_map_entry_t VMEU_first_free = NULL;
	VMEU_map = (map);
	VMEU_entry = (entry);

	if (map->holelistenabled == FALSE) {
		if (VMEU_entry->vme_start <= VMEU_map->first_free->vme_start){
			VMEU_first_free = VMEU_entry->vme_prev;
		} else	{
			VMEU_first_free = VMEU_map->first_free;
		}
	}
	_vm_map_store_entry_unlink(&VMEU_map->hdr, VMEU_entry);
	vm_map_store_update( map, entry, VM_MAP_ENTRY_DELETE);
	update_first_free_ll(VMEU_map, VMEU_first_free);
#ifdef VM_MAP_STORE_USE_RB
	if (vm_map_store_has_RB_support( &VMEU_map->hdr )) {
		update_first_free_rb(VMEU_map, entry, FALSE);
	}
#endif
}

void
vm_map_store_copy_reset( vm_map_copy_t copy,vm_map_entry_t entry)
{
	int nentries = copy->cpy_hdr.nentries;
	vm_map_store_copy_reset_ll(copy, entry, nentries);
#ifdef VM_MAP_STORE_USE_RB
	if (vm_map_store_has_RB_support( &copy->c_u.hdr )) {
		vm_map_store_copy_reset_rb(copy, entry, nentries);
	}
#endif
}

void
vm_map_store_update_first_free( vm_map_t map, vm_map_entry_t first_free_entry, boolean_t new_entry_creation)
{
	update_first_free_ll(map, first_free_entry);
#ifdef VM_MAP_STORE_USE_RB
	if (vm_map_store_has_RB_support( &map->hdr )) {
		update_first_free_rb(map, first_free_entry, new_entry_creation);
	}
#endif
}
Commit	Line	Data
6d2010ae A	1	/*
	2	* Copyright (c) 2009 Apple Inc. All rights reserved.
	3	*
	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
	25	*
	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
	27	*/
	28
3e170ce0	29	#include <mach/sdt.h>
6d2010ae	30	#include <vm/vm_map_store.h>
3e170ce0	31	#include <vm/vm_pageout.h> /* for vm_debug_events */
6d2010ae A	32
	33	#if MACH_ASSERT
	34	boolean_t
	35	first_free_is_valid_store( vm_map_t map )
	36	{
	37	return(first_free_is_valid_ll( map ));
	38	}
	39	#endif
	40
04b8595b A	41	boolean_t
	42	vm_map_store_has_RB_support( struct vm_map_header *hdr )
	43	{
	44	if ((void)hdr->rb_head_store.rbh_root == (void)(int)SKIP_RB_TREE) {
	45	return FALSE;
	46	}
	47	return TRUE;
	48	}
	49
6d2010ae A	50	void
	51	vm_map_store_init( struct vm_map_header *hdr )
	52	{
	53	vm_map_store_init_ll( hdr );
	54	#ifdef VM_MAP_STORE_USE_RB
04b8595b A	55	if (vm_map_store_has_RB_support( hdr )) {
	56	vm_map_store_init_rb( hdr );
	57	}
6d2010ae A	58	#endif
	59	}
	60
	61	boolean_t
	62	vm_map_store_lookup_entry(
	63	register vm_map_t map,
	64	register vm_map_offset_t address,
	65	vm_map_entry_t entry) / OUT */
	66	{
	67	#ifdef VM_MAP_STORE_USE_LL
	68	return (vm_map_store_lookup_entry_ll( map, address, entry ));
	69	#elif defined VM_MAP_STORE_USE_RB
04b8595b A	70	if (vm_map_store_has_RB_support( &map->hdr )) {
	71	return (vm_map_store_lookup_entry_rb( map, address, entry ));
	72	} else {
	73	panic("VM map lookups need RB tree support.\n");
	74	return FALSE; /* For compiler warning.*/
	75	}
6d2010ae A	76	#endif
	77	}
	78
	79	void
	80	vm_map_store_update( vm_map_t map, vm_map_entry_t entry, int update_type )
	81	{
	82	switch (update_type) {
	83	case VM_MAP_ENTRY_CREATE:
	84	break;
	85	case VM_MAP_ENTRY_DELETE:
3e170ce0	86	if((map->holelistenabled == FALSE) && ((entry) == (map)->first_free)) {
6d2010ae A	87	(map)->first_free = vm_map_to_entry(map);
	88	}
	89	if((entry) == (map)->hint) {
	90	(map)->hint = vm_map_to_entry(map);
	91	}
	92	break;
	93	default:
	94	break;
	95	}
	96	}
	97
	98	void vm_map_store_copy_insert( vm_map_t map, vm_map_entry_t after_where, vm_map_copy_t copy)
	99	{
3e170ce0 A	100	if (__improbable(vm_debug_events)) {
	101	vm_map_entry_t entry;
	102	for (entry = vm_map_copy_first_entry(copy); entry != vm_map_copy_to_entry(copy); entry = entry->vme_next) {
	103	DTRACE_VM4(map_entry_link_copy, vm_map_t, map, vm_map_entry_t, entry, vm_address_t, entry->links.start, vm_address_t, entry->links.end);
	104	}
	105	}
	106
	107	if (map->holelistenabled) {
	108	vm_map_entry_t entry = NULL;
	109
	110	entry = vm_map_copy_first_entry(copy);
	111	while (entry != vm_map_copy_to_entry(copy)) {
	112	vm_map_store_update_first_free(map, entry, TRUE);
	113	entry = entry->vme_next;
	114	}
	115	}
	116
6d2010ae A	117	vm_map_store_copy_insert_ll(map, after_where, copy);
6d2010ae A	118	#ifdef VM_MAP_STORE_USE_RB
04b8595b A	119	if (vm_map_store_has_RB_support( &map->hdr )) {
	120	vm_map_store_copy_insert_rb(map, after_where, copy);
	121	}
6d2010ae A	122	#endif
	123	}
	124
	125	/*
	126	* vm_map_entry_{un,}link:
	127	*
	128	* Insert/remove entries from maps (or map copies).
	129	* The _vm_map_store_entry_{un,}link variants are used at
	130	* some places where updating first_free is not needed &
	131	* copy maps are being modified. Also note the first argument
	132	* is the map header.
	133	* Modifying the vm_map_store_entry_{un,}link functions to
	134	* deal with these call sites made the interface confusing
	135	* and clunky.
	136	*/
	137
	138	void
	139	_vm_map_store_entry_link( struct vm_map_header * mapHdr, vm_map_entry_t after_where, vm_map_entry_t entry)
	140	{
e2d2fc5c	141	assert(entry->vme_start < entry->vme_end);
3e170ce0 A	142	if (__improbable(vm_debug_events))
	143	DTRACE_VM4(map_entry_link, vm_map_t, (char *)mapHdr - sizeof (lck_rw_t), vm_map_entry_t, entry, vm_address_t, entry->links.start, vm_address_t, entry->links.end);
	144
6d2010ae A	145	vm_map_store_entry_link_ll(mapHdr, after_where, entry);
6d2010ae A	146	#ifdef VM_MAP_STORE_USE_RB
04b8595b A	147	if (vm_map_store_has_RB_support( mapHdr )) {
	148	vm_map_store_entry_link_rb(mapHdr, after_where, entry);
	149	}
6d2010ae	150	#endif
39236c6e A	151	#if MAP_ENTRY_INSERTION_DEBUG
	152	fastbacktrace(&entry->vme_insertion_bt[0],
	153	(sizeof (entry->vme_insertion_bt) / sizeof (uintptr_t)));
	154	#endif
6d2010ae A	155	}
	156
	157	void
	158	vm_map_store_entry_link( vm_map_t map, vm_map_entry_t after_where, vm_map_entry_t entry)
	159	{
	160	vm_map_t VMEL_map;
	161	vm_map_entry_t VMEL_entry;
	162	VMEL_map = (map);
	163	VMEL_entry = (entry);
	164
	165	_vm_map_store_entry_link(&VMEL_map->hdr, after_where, VMEL_entry);
	166	if( VMEL_map->disable_vmentry_reuse == TRUE ) {
	167	UPDATE_HIGHEST_ENTRY_END( VMEL_map, VMEL_entry);
	168	} else {
	169	update_first_free_ll(VMEL_map, VMEL_map->first_free);
	170	#ifdef VM_MAP_STORE_USE_RB
04b8595b	171	if (vm_map_store_has_RB_support( &VMEL_map->hdr )) {
3e170ce0	172	update_first_free_rb(VMEL_map, entry, TRUE);
04b8595b	173	}
6d2010ae A	174	#endif
	175	}
	176	}
	177
	178	void
	179	_vm_map_store_entry_unlink( struct vm_map_header * mapHdr, vm_map_entry_t entry)
	180	{
3e170ce0 A	181	if (__improbable(vm_debug_events))
	182	DTRACE_VM4(map_entry_unlink, vm_map_t, (char *)mapHdr - sizeof (lck_rw_t), vm_map_entry_t, entry, vm_address_t, entry->links.start, vm_address_t, entry->links.end);
	183
6d2010ae A	184	vm_map_store_entry_unlink_ll(mapHdr, entry);
6d2010ae A	185	#ifdef VM_MAP_STORE_USE_RB
04b8595b A	186	if (vm_map_store_has_RB_support( mapHdr )) {
	187	vm_map_store_entry_unlink_rb(mapHdr, entry);
	188	}
6d2010ae A	189	#endif
	190	}
	191
	192	void
	193	vm_map_store_entry_unlink( vm_map_t map, vm_map_entry_t entry)
	194	{
	195	vm_map_t VMEU_map;
3e170ce0 A	196	vm_map_entry_t VMEU_entry = NULL;
3e170ce0 A	197	vm_map_entry_t VMEU_first_free = NULL;
6d2010ae A	198	VMEU_map = (map);
6d2010ae A	199	VMEU_entry = (entry);
3e170ce0 A	200
	201	if (map->holelistenabled == FALSE) {
	202	if (VMEU_entry->vme_start <= VMEU_map->first_free->vme_start){
	203	VMEU_first_free = VMEU_entry->vme_prev;
	204	} else {
	205	VMEU_first_free = VMEU_map->first_free;
	206	}
6d2010ae	207	}
6d2010ae	208	_vm_map_store_entry_unlink(&VMEU_map->hdr, VMEU_entry);
316670eb	209	vm_map_store_update( map, entry, VM_MAP_ENTRY_DELETE);
6d2010ae A	210	update_first_free_ll(VMEU_map, VMEU_first_free);
6d2010ae A	211	#ifdef VM_MAP_STORE_USE_RB
04b8595b	212	if (vm_map_store_has_RB_support( &VMEU_map->hdr )) {
3e170ce0	213	update_first_free_rb(VMEU_map, entry, FALSE);
04b8595b	214	}
6d2010ae A	215	#endif
	216	}
	217
	218	void
	219	vm_map_store_copy_reset( vm_map_copy_t copy,vm_map_entry_t entry)
	220	{
	221	int nentries = copy->cpy_hdr.nentries;
	222	vm_map_store_copy_reset_ll(copy, entry, nentries);
	223	#ifdef VM_MAP_STORE_USE_RB
04b8595b A	224	if (vm_map_store_has_RB_support( &copy->c_u.hdr )) {
	225	vm_map_store_copy_reset_rb(copy, entry, nentries);
	226	}
6d2010ae A	227	#endif
	228	}
	229
	230	void
3e170ce0	231	vm_map_store_update_first_free( vm_map_t map, vm_map_entry_t first_free_entry, boolean_t new_entry_creation)
6d2010ae	232	{
3e170ce0	233	update_first_free_ll(map, first_free_entry);
6d2010ae	234	#ifdef VM_MAP_STORE_USE_RB
04b8595b	235	if (vm_map_store_has_RB_support( &map->hdr )) {
3e170ce0	236	update_first_free_rb(map, first_free_entry, new_entry_creation);
04b8595b	237	}
6d2010ae A	238	#endif
6d2010ae A	239	}