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
31boolean_t
32first_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;
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)) &&
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 */
66#define UPDATE_FIRST_FREE_LL(map, new_first_free) \
67 MACRO_BEGIN \
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 } \
92 MACRO_END
93
94#define _vm_map_entry_link_ll(hdr, after_where, entry) \
95 MACRO_BEGIN \
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 } \
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) \
126MACRO_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); \
139MACRO_END
140
141
142
143void
144vm_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 */
158boolean_t
159vm_map_store_lookup_entry_ll(
160 vm_map_t map,
161 vm_map_offset_t address,
162 vm_map_entry_t *entry) /* OUT */
163{
164 vm_map_entry_t cur;
165 vm_map_entry_t last;
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
229void
230vm_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
235void
236vm_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
241void
242vm_map_store_copy_reset_ll( vm_map_copy_t copy, __unused vm_map_entry_t entry, __unused int nentries)
243{
244 copy->cpy_hdr.nentries = 0;
245 vm_map_copy_first_entry(copy) =
246 vm_map_copy_last_entry(copy) =
247 vm_map_copy_to_entry(copy);
248
249}
250
251void
252update_first_free_ll( vm_map_t map, vm_map_entry_t new_first_free)
253{
254 if (map->holelistenabled)
255 return;
256
257 UPDATE_FIRST_FREE_LL( map, new_first_free);
258}
259
260