[apple/xnu.git] / osfmk / vm / vm_map_store_ll.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 <vm/vm_map_store_ll.h>

boolean_t
first_free_is_valid_ll( vm_map_t map )
{
	vm_map_entry_t	entry, next;
	entry = vm_map_to_entry(map);
	next = entry->vme_next;
	while (vm_map_trunc_page(next->vme_start,
				 VM_MAP_PAGE_MASK(map)) ==
	       vm_map_trunc_page(entry->vme_end,
				 VM_MAP_PAGE_MASK(map)) ||
	       (vm_map_trunc_page(next->vme_start,
				  VM_MAP_PAGE_MASK(map)) ==
		vm_map_trunc_page(entry->vme_start,
				  VM_MAP_PAGE_MASK(map)) &&
		next != vm_map_to_entry(map))) {
		entry = next;
		next = entry->vme_next;
		if (entry == vm_map_to_entry(map))
			break;
	}
	if (map->first_free != entry) {
		printf("Bad first_free for map %p: %p should be %p\n",
		       map, map->first_free, entry);
		return FALSE;
	}
	return TRUE;
}

/*
 *	UPDATE_FIRST_FREE:
 *
 *	Updates the map->first_free pointer to the
 *	entry immediately before the first hole in the map.
 * 	The map should be locked.
 */
#define UPDATE_FIRST_FREE_LL(map, new_first_free)			\
	MACRO_BEGIN							\
	if( map->disable_vmentry_reuse == FALSE){			\
		vm_map_t	UFF_map;				\
		vm_map_entry_t	UFF_first_free;				\
		vm_map_entry_t	UFF_next_entry;				\
		UFF_map = (map);					\
		UFF_first_free = (new_first_free);			\
		UFF_next_entry = UFF_first_free->vme_next;		\
		while (vm_map_trunc_page(UFF_next_entry->vme_start,	\
					 VM_MAP_PAGE_MASK(UFF_map)) ==	\
		       vm_map_trunc_page(UFF_first_free->vme_end,	\
					 VM_MAP_PAGE_MASK(UFF_map)) ||	\
		       (vm_map_trunc_page(UFF_next_entry->vme_start,	\
					  VM_MAP_PAGE_MASK(UFF_map)) ==	\
			vm_map_trunc_page(UFF_first_free->vme_start,	\
					  VM_MAP_PAGE_MASK(UFF_map)) &&	\
			UFF_next_entry != vm_map_to_entry(UFF_map))) {	\
			UFF_first_free = UFF_next_entry;		\
			UFF_next_entry = UFF_first_free->vme_next;	\
			if (UFF_first_free == vm_map_to_entry(UFF_map))	\
				break;					\
		}							\
		UFF_map->first_free = UFF_first_free;			\
		assert(first_free_is_valid(UFF_map));			\
	}								\
	MACRO_END

#define _vm_map_entry_link_ll(hdr, after_where, entry)			\
	MACRO_BEGIN							\
	if (entry->map_aligned) {					\
		assert(VM_MAP_PAGE_ALIGNED((entry->vme_start),		\
					   VM_MAP_HDR_PAGE_MASK((hdr))));\
		assert(VM_MAP_PAGE_ALIGNED((entry->vme_end),		\
					   VM_MAP_HDR_PAGE_MASK((hdr))));\
	}								\
	(hdr)->nentries++;						\
	(entry)->vme_prev = (after_where);				\
	(entry)->vme_next = (after_where)->vme_next;			\
	(entry)->vme_prev->vme_next = (entry)->vme_next->vme_prev = (entry); \
	MACRO_END

#define _vm_map_entry_unlink_ll(hdr, entry)				\
	MACRO_BEGIN							\
	(hdr)->nentries--;						\
	(entry)->vme_next->vme_prev = (entry)->vme_prev; 		\
	(entry)->vme_prev->vme_next = (entry)->vme_next; 		\
	MACRO_END
/*
 *	Macro:		vm_map_copy_insert
 *	
 *	Description:
 *		Link a copy chain ("copy") into a map at the
 *		specified location (after "where").
 *	Side effects:
 *		The copy chain is destroyed.
 *	Warning:
 *		The arguments are evaluated multiple times.
 */
#define	_vm_map_copy_insert_ll(map, where, copy)				\
MACRO_BEGIN								\
	vm_map_t VMCI_map;						\
	vm_map_entry_t VMCI_where;					\
	vm_map_copy_t VMCI_copy;					\
	VMCI_map = (map);						\
	VMCI_where = (where);						\
	VMCI_copy = (copy);						\
	((VMCI_where->vme_next)->vme_prev = vm_map_copy_last_entry(VMCI_copy))\
		->vme_next = (VMCI_where->vme_next);			\
	((VMCI_where)->vme_next = vm_map_copy_first_entry(VMCI_copy))	\
		->vme_prev = VMCI_where;				\
	VMCI_map->hdr.nentries += VMCI_copy->cpy_hdr.nentries;		\
	update_first_free_ll(VMCI_map, VMCI_map->first_free);		\
MACRO_END


void
vm_map_store_init_ll( __unused struct vm_map_header *hdr)
{
	return;
}

/*
 *	vm_map_lookup_entry_ll:	[ internal use only ]
 *	Use the linked list to find the map entry containing (or
 *	immediately preceding) the specified address
 *	in the given map; the entry is returned
 *	in the "entry" parameter.  The boolean
 *	result indicates whether the address is
 *	actually contained in the map.
 */
boolean_t
vm_map_store_lookup_entry_ll(
	vm_map_t		map,
	vm_map_offset_t		address,
	vm_map_entry_t		*entry)		/* OUT */
{
	vm_map_entry_t		cur;
	vm_map_entry_t		last;

	/*
	 *	Start looking either from the head of the
	 *	list, or from the hint.
	 */
	cur = map->hint;

	if (cur == vm_map_to_entry(map))
		cur = cur->vme_next;

	if (address >= cur->vme_start) {
		/*
		 *	Go from hint to end of list.
		 *
		 *	But first, make a quick check to see if
		 *	we are already looking at the entry we
		 *	want (which is usually the case).
		 *	Note also that we don't need to save the hint
		 *	here... it is the same hint (unless we are
		 *	at the header, in which case the hint didn't
		 *	buy us anything anyway).
		 */
		last = vm_map_to_entry(map);
		if ((cur != last) && (cur->vme_end > address)) {
			*entry = cur;
			return(TRUE);
		}
	}
	else {
		/*
		 *	Go from start to hint, *inclusively*
		 */
		last = cur->vme_next;
		cur = vm_map_first_entry(map);
	}

	/*
	 *	Search linearly
	 */

	while (cur != last) {
		if (cur->vme_end > address) {
			if (address >= cur->vme_start) {
				/*
				 *	Save this lookup for future
				 *	hints, and return
				 */

				*entry = cur;
				SAVE_HINT_MAP_READ(map, cur);

				return(TRUE);
			}
			break;
		}
		cur = cur->vme_next;
	}
	*entry = cur->vme_prev;
	SAVE_HINT_MAP_READ(map, *entry);

	return(FALSE);
}

void
vm_map_store_entry_link_ll( struct vm_map_header *mapHdr, vm_map_entry_t after_where, vm_map_entry_t entry)
{
	_vm_map_entry_link_ll( mapHdr, after_where, entry);
}

void
vm_map_store_entry_unlink_ll( struct vm_map_header *mapHdr, vm_map_entry_t entry)
{
	_vm_map_entry_unlink_ll( mapHdr, entry);
}

void
vm_map_store_copy_insert_ll( vm_map_t map, vm_map_entry_t after_where, vm_map_copy_t copy)
{
	_vm_map_copy_insert_ll( map, after_where, copy);
}

void
vm_map_store_copy_reset_ll( vm_map_copy_t copy, __unused vm_map_entry_t entry, __unused int nentries)
{
	copy->cpy_hdr.nentries = 0;
	vm_map_copy_first_entry(copy) =
		vm_map_copy_last_entry(copy) =
			vm_map_copy_to_entry(copy);

}

void
update_first_free_ll( vm_map_t map, vm_map_entry_t new_first_free)
{
	if (map->holelistenabled)
		return;

	UPDATE_FIRST_FREE_LL( map, new_first_free);
}
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
	29	#include <vm/vm_map_store_ll.h>
	30
	31	boolean_t
	32	first_free_is_valid_ll( vm_map_t map )
	33	{
	34	vm_map_entry_t entry, next;
	35	entry = vm_map_to_entry(map);
	36	next = entry->vme_next;
39236c6e A	37	while (vm_map_trunc_page(next->vme_start,
	38	VM_MAP_PAGE_MASK(map)) ==
	39	vm_map_trunc_page(entry->vme_end,
	40	VM_MAP_PAGE_MASK(map)) \|\|
	41	(vm_map_trunc_page(next->vme_start,
	42	VM_MAP_PAGE_MASK(map)) ==
	43	vm_map_trunc_page(entry->vme_start,
	44	VM_MAP_PAGE_MASK(map)) &&
6d2010ae A	45	next != vm_map_to_entry(map))) {
	46	entry = next;
	47	next = entry->vme_next;
	48	if (entry == vm_map_to_entry(map))
	49	break;
	50	}
	51	if (map->first_free != entry) {
	52	printf("Bad first_free for map %p: %p should be %p\n",
	53	map, map->first_free, entry);
	54	return FALSE;
	55	}
	56	return TRUE;
	57	}
	58
	59	/*
	60	* UPDATE_FIRST_FREE:
	61	*
	62	* Updates the map->first_free pointer to the
	63	* entry immediately before the first hole in the map.
	64	* The map should be locked.
	65	*/
39236c6e	66	#define UPDATE_FIRST_FREE_LL(map, new_first_free) \
6d2010ae	67	MACRO_BEGIN \
39236c6e A	68	if( map->disable_vmentry_reuse == FALSE){ \
	69	vm_map_t UFF_map; \
	70	vm_map_entry_t UFF_first_free; \
	71	vm_map_entry_t UFF_next_entry; \
	72	UFF_map = (map); \
	73	UFF_first_free = (new_first_free); \
	74	UFF_next_entry = UFF_first_free->vme_next; \
	75	while (vm_map_trunc_page(UFF_next_entry->vme_start, \
	76	VM_MAP_PAGE_MASK(UFF_map)) == \
	77	vm_map_trunc_page(UFF_first_free->vme_end, \
	78	VM_MAP_PAGE_MASK(UFF_map)) \|\| \
	79	(vm_map_trunc_page(UFF_next_entry->vme_start, \
	80	VM_MAP_PAGE_MASK(UFF_map)) == \
	81	vm_map_trunc_page(UFF_first_free->vme_start, \
	82	VM_MAP_PAGE_MASK(UFF_map)) && \
	83	UFF_next_entry != vm_map_to_entry(UFF_map))) { \
	84	UFF_first_free = UFF_next_entry; \
	85	UFF_next_entry = UFF_first_free->vme_next; \
	86	if (UFF_first_free == vm_map_to_entry(UFF_map)) \
	87	break; \
	88	} \
	89	UFF_map->first_free = UFF_first_free; \
	90	assert(first_free_is_valid(UFF_map)); \
	91	} \
6d2010ae A	92	MACRO_END
	93
	94	#define _vm_map_entry_link_ll(hdr, after_where, entry) \
	95	MACRO_BEGIN \
39236c6e A	96	if (entry->map_aligned) { \
	97	assert(VM_MAP_PAGE_ALIGNED((entry->vme_start), \
	98	VM_MAP_HDR_PAGE_MASK((hdr))));\
	99	assert(VM_MAP_PAGE_ALIGNED((entry->vme_end), \
	100	VM_MAP_HDR_PAGE_MASK((hdr))));\
	101	} \
6d2010ae A	102	(hdr)->nentries++; \
	103	(entry)->vme_prev = (after_where); \
	104	(entry)->vme_next = (after_where)->vme_next; \
	105	(entry)->vme_prev->vme_next = (entry)->vme_next->vme_prev = (entry); \
	106	MACRO_END
	107
	108	#define _vm_map_entry_unlink_ll(hdr, entry) \
	109	MACRO_BEGIN \
	110	(hdr)->nentries--; \
	111	(entry)->vme_next->vme_prev = (entry)->vme_prev; \
	112	(entry)->vme_prev->vme_next = (entry)->vme_next; \
	113	MACRO_END
	114	/*
	115	* Macro: vm_map_copy_insert
	116	*
	117	* Description:
	118	* Link a copy chain ("copy") into a map at the
	119	* specified location (after "where").
	120	* Side effects:
	121	* The copy chain is destroyed.
	122	* Warning:
	123	* The arguments are evaluated multiple times.
	124	*/
	125	#define _vm_map_copy_insert_ll(map, where, copy) \
	126	MACRO_BEGIN \
	127	vm_map_t VMCI_map; \
	128	vm_map_entry_t VMCI_where; \
	129	vm_map_copy_t VMCI_copy; \
	130	VMCI_map = (map); \
	131	VMCI_where = (where); \
	132	VMCI_copy = (copy); \
	133	((VMCI_where->vme_next)->vme_prev = vm_map_copy_last_entry(VMCI_copy))\
	134	->vme_next = (VMCI_where->vme_next); \
	135	((VMCI_where)->vme_next = vm_map_copy_first_entry(VMCI_copy)) \
	136	->vme_prev = VMCI_where; \
	137	VMCI_map->hdr.nentries += VMCI_copy->cpy_hdr.nentries; \
	138	update_first_free_ll(VMCI_map, VMCI_map->first_free); \
	139	MACRO_END
	140
	141
	142
	143	void
	144	vm_map_store_init_ll( __unused struct vm_map_header *hdr)
	145	{
	146	return;
	147	}
	148
	149	/*
	150	* vm_map_lookup_entry_ll: [ internal use only ]
	151	* Use the linked list to find the map entry containing (or
	152	* immediately preceding) the specified address
	153	* in the given map; the entry is returned
	154	* in the "entry" parameter. The boolean
	155	* result indicates whether the address is
	156	* actually contained in the map.
	157	*/
	158	boolean_t
	159	vm_map_store_lookup_entry_ll(
39037602 A	160	vm_map_t map,
39037602 A	161	vm_map_offset_t address,
6d2010ae A	162	vm_map_entry_t entry) / OUT */
6d2010ae A	163	{
39037602 A	164	vm_map_entry_t cur;
39037602 A	165	vm_map_entry_t last;
6d2010ae A	166
	167	/*
	168	* Start looking either from the head of the
	169	* list, or from the hint.
	170	*/
	171	cur = map->hint;
	172
	173	if (cur == vm_map_to_entry(map))
	174	cur = cur->vme_next;
	175
	176	if (address >= cur->vme_start) {
	177	/*
	178	* Go from hint to end of list.
	179	*
	180	* But first, make a quick check to see if
	181	* we are already looking at the entry we
	182	* want (which is usually the case).
	183	* Note also that we don't need to save the hint
	184	* here... it is the same hint (unless we are
	185	* at the header, in which case the hint didn't
	186	* buy us anything anyway).
	187	*/
	188	last = vm_map_to_entry(map);
	189	if ((cur != last) && (cur->vme_end > address)) {
	190	*entry = cur;
	191	return(TRUE);
	192	}
	193	}
	194	else {
	195	/*
	196	* Go from start to hint, inclusively
	197	*/
	198	last = cur->vme_next;
	199	cur = vm_map_first_entry(map);
	200	}
	201
	202	/*
	203	* Search linearly
	204	*/
	205
	206	while (cur != last) {
	207	if (cur->vme_end > address) {
	208	if (address >= cur->vme_start) {
	209	/*
	210	* Save this lookup for future
	211	* hints, and return
	212	*/
	213
	214	*entry = cur;
	215	SAVE_HINT_MAP_READ(map, cur);
	216
	217	return(TRUE);
	218	}
	219	break;
	220	}
	221	cur = cur->vme_next;
	222	}
	223	*entry = cur->vme_prev;
	224	SAVE_HINT_MAP_READ(map, *entry);
	225
	226	return(FALSE);
	227	}
	228
	229	void
230	vm_map_store_entry_link_ll( struct vm_map_header *mapHdr, vm_map_entry_t after_where, vm_map_entry_t entry)
231	{
232	_vm_map_entry_link_ll( mapHdr, after_where, entry);
233	}
234
235	void
236	vm_map_store_entry_unlink_ll( struct vm_map_header *mapHdr, vm_map_entry_t entry)
237	{
238	_vm_map_entry_unlink_ll( mapHdr, entry);
239	}
240
241	void
242	vm_map_store_copy_insert_ll( vm_map_t map, vm_map_entry_t after_where, vm_map_copy_t copy)
243	{
244	_vm_map_copy_insert_ll( map, after_where, copy);
245	}
246
247	void
248	vm_map_store_copy_reset_ll( vm_map_copy_t copy, __unused vm_map_entry_t entry, __unused int nentries)
249	{
250	copy->cpy_hdr.nentries = 0;
251	vm_map_copy_first_entry(copy) =
252	vm_map_copy_last_entry(copy) =
253	vm_map_copy_to_entry(copy);
254
255	}
256
257	void
258	update_first_free_ll( vm_map_t map, vm_map_entry_t new_first_free)
259	{
3e170ce0 A	260	if (map->holelistenabled)
	261	return;
	262
6d2010ae A	263	UPDATE_FIRST_FREE_LL( map, new_first_free);
	264	}
	265