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_rb.h>
30
31RB_GENERATE(rb_head, vm_map_store, entry, rb_node_compare);
32
33#define VME_FOR_STORE( store)	\
34	(vm_map_entry_t)(((unsigned long)store) - ((unsigned long)sizeof(struct vm_map_links)))
35
36void
37vm_map_store_init_rb( struct vm_map_header* hdr )
38{
39	RB_INIT(&(hdr->rb_head_store));
40}
41
42int rb_node_compare(struct vm_map_store *node, struct vm_map_store *parent)
43{
44	vm_map_entry_t vme_c;
45	vm_map_entry_t vme_p;
46
47	vme_c = VME_FOR_STORE(node);
48	vme_p =  VME_FOR_STORE(parent);
49	if (vme_c->vme_start < vme_p->vme_start)
50		return -1;
51	if (vme_c->vme_start >= vme_p->vme_end)
52		return 1;
53	return 0;
54}
55
56void vm_map_store_walk_rb( vm_map_t map, vm_map_entry_t *wrong_vme, vm_map_entry_t *vm_entry)
57{
58	struct vm_map_header hdr = map->hdr;
59	struct vm_map_store *rb_entry = RB_ROOT(&(hdr.rb_head_store));
60	vm_map_entry_t cur = *vm_entry;
61
62	rb_entry = RB_FIND( rb_head, &(hdr.rb_head_store), &(cur->store));
63	if(rb_entry == NULL)
64		panic("NO SUCH ENTRY %p. Gave back %p", *vm_entry, *wrong_vme);
65	else
66		panic("Cur: %p, L: %p, R: %p",  VME_FOR_STORE(rb_entry),  VME_FOR_STORE(RB_LEFT(rb_entry,entry)),  VME_FOR_STORE(RB_RIGHT(rb_entry,entry)));
67}
68
69
70boolean_t vm_map_store_lookup_entry_rb( vm_map_t map, vm_map_offset_t address, vm_map_entry_t *vm_entry)
71{
72	struct vm_map_header hdr = map->hdr;
73	struct vm_map_store *rb_entry = RB_ROOT(&(hdr.rb_head_store));
74	vm_map_entry_t cur = vm_map_to_entry(map);
75	vm_map_entry_t prev = VM_MAP_ENTRY_NULL;
76
77	while (rb_entry != (struct vm_map_store*)NULL) {
78       		cur =  VME_FOR_STORE(rb_entry);
79		if(cur == VM_MAP_ENTRY_NULL)
80			panic("no entry");
81		if (address >= cur->vme_start) {
82			if (address < cur->vme_end) {
83				*vm_entry = cur;
84				return TRUE;
85			}
86			rb_entry = RB_RIGHT(rb_entry, entry);
87			prev = cur;
88		} else {
89			rb_entry = RB_LEFT(rb_entry, entry);
90		}
91	}
92	if( prev == VM_MAP_ENTRY_NULL){
93		prev = vm_map_to_entry(map);
94	}
95	*vm_entry = prev;
96	return FALSE;
97}
98
99void 	vm_map_store_entry_link_rb( struct vm_map_header *mapHdr, __unused vm_map_entry_t after_where, vm_map_entry_t entry)
100{
101	struct rb_head *rbh = &(mapHdr->rb_head_store);
102	struct vm_map_store *store = &(entry->store);
103	struct vm_map_store *tmp_store;
104	if((tmp_store = RB_INSERT( rb_head, rbh, store )) != NULL) {
105		panic("VMSEL: INSERT FAILED: 0x%lx, 0x%lx, 0x%lx, 0x%lx", (uintptr_t)entry->vme_start, (uintptr_t)entry->vme_end,
106				(uintptr_t)(VME_FOR_STORE(tmp_store))->vme_start,  (uintptr_t)(VME_FOR_STORE(tmp_store))->vme_end);
107	}
108}
109
110void	vm_map_store_entry_unlink_rb( struct vm_map_header *mapHdr, vm_map_entry_t entry)
111{
112	struct rb_head *rbh = &(mapHdr->rb_head_store);
113	struct vm_map_store *rb_entry;
114	struct vm_map_store *store = &(entry->store);
115
116	rb_entry = RB_FIND( rb_head, rbh, store);
117	if(rb_entry == NULL)
118		panic("NO ENTRY TO DELETE");
119	RB_REMOVE( rb_head, rbh, store );
120}
121
122void	vm_map_store_copy_insert_rb( vm_map_t map, __unused vm_map_entry_t after_where, vm_map_copy_t copy)
123{
124	struct vm_map_header *mapHdr = &(map->hdr);
125	struct rb_head *rbh = &(mapHdr->rb_head_store);
126	struct vm_map_store *store;
127	vm_map_entry_t entry = vm_map_copy_first_entry(copy);
128	int inserted=0, nentries = copy->cpy_hdr.nentries;
129
130	while (entry != vm_map_copy_to_entry(copy) && nentries > 0) {
131		vm_map_entry_t prev = entry;
132		store = &(entry->store);
133		if( RB_INSERT( rb_head, rbh, store ) != NULL){
134			panic("VMSCIR1: INSERT FAILED: %d: %p, %p, %p, 0x%lx, 0x%lx, 0x%lx, 0x%lx, 0x%lx, 0x%lx",inserted, prev, entry, vm_map_copy_to_entry(copy),
135					(uintptr_t)prev->vme_start,  (uintptr_t)prev->vme_end,  (uintptr_t)entry->vme_start,  (uintptr_t)entry->vme_end,
136					 (uintptr_t)(VME_FOR_STORE(rbh->rbh_root))->vme_start,  (uintptr_t)(VME_FOR_STORE(rbh->rbh_root))->vme_end);
137		} else {
138			entry = entry->vme_next;
139			inserted++;
140			nentries--;
141		}
142	}
143}
144
145void
146vm_map_store_copy_reset_rb( vm_map_copy_t copy, vm_map_entry_t entry, int nentries )
147{
148	struct vm_map_header *mapHdr = &(copy->cpy_hdr);
149	struct rb_head *rbh = &(mapHdr->rb_head_store);
150	struct vm_map_store *store;
151	int deleted=0;
152
153	while (entry != vm_map_copy_to_entry(copy) && nentries > 0) {
154		store = &(entry->store);
155		RB_REMOVE( rb_head, rbh, store );
156		entry = entry->vme_next;
157		deleted++;
158		nentries--;
159	}
160}
161
162void	update_first_free_rb( __unused vm_map_t map, __unused vm_map_entry_t entry)
163{
164	return ;
165}
166
167