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 <kern/backtrace.h> |
30 | #include <vm/vm_map_store_rb.h> |
31 | |
32 | RB_GENERATE(rb_head, vm_map_store, entry, rb_node_compare); |
33 | |
34 | #define VME_FOR_STORE( store) \ |
35 | (vm_map_entry_t)(((unsigned long)store) - ((unsigned long)sizeof(struct vm_map_links))) |
36 | |
37 | void |
38 | vm_map_store_init_rb( struct vm_map_header* hdr ) |
39 | { |
40 | RB_INIT(&(hdr->rb_head_store)); |
41 | } |
42 | |
43 | int rb_node_compare(struct vm_map_store *node, struct vm_map_store *parent) |
44 | { |
45 | vm_map_entry_t vme_c; |
46 | vm_map_entry_t vme_p; |
47 | |
48 | vme_c = VME_FOR_STORE(node); |
49 | vme_p = VME_FOR_STORE(parent); |
50 | if (vme_c->vme_start < vme_p->vme_start) |
51 | return -1; |
52 | if (vme_c->vme_start >= vme_p->vme_end) |
53 | return 1; |
54 | return 0; |
55 | } |
56 | |
57 | void vm_map_store_walk_rb( vm_map_t map, vm_map_entry_t *wrong_vme, vm_map_entry_t *vm_entry) |
58 | { |
59 | struct vm_map_header hdr = map->hdr; |
60 | struct vm_map_store *rb_entry = RB_ROOT(&(hdr.rb_head_store)); |
61 | vm_map_entry_t cur = *vm_entry; |
62 | |
63 | rb_entry = RB_FIND( rb_head, &(hdr.rb_head_store), &(cur->store)); |
64 | if(rb_entry == NULL) |
65 | panic("NO SUCH ENTRY %p. Gave back %p" , *vm_entry, *wrong_vme); |
66 | else |
67 | 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))); |
68 | } |
69 | |
70 | |
71 | boolean_t vm_map_store_lookup_entry_rb( vm_map_t map, vm_map_offset_t address, vm_map_entry_t *vm_entry) |
72 | { |
73 | struct vm_map_header hdr = map->hdr; |
74 | struct vm_map_store *rb_entry = RB_ROOT(&(hdr.rb_head_store)); |
75 | vm_map_entry_t cur = vm_map_to_entry(map); |
76 | vm_map_entry_t prev = VM_MAP_ENTRY_NULL; |
77 | |
78 | while (rb_entry != (struct vm_map_store*)NULL) { |
79 | cur = VME_FOR_STORE(rb_entry); |
80 | if(cur == VM_MAP_ENTRY_NULL) |
81 | panic("no entry" ); |
82 | if (address >= cur->vme_start) { |
83 | if (address < cur->vme_end) { |
84 | *vm_entry = cur; |
85 | return TRUE; |
86 | } |
87 | rb_entry = RB_RIGHT(rb_entry, entry); |
88 | prev = cur; |
89 | } else { |
90 | rb_entry = RB_LEFT(rb_entry, entry); |
91 | } |
92 | } |
93 | if( prev == VM_MAP_ENTRY_NULL){ |
94 | prev = vm_map_to_entry(map); |
95 | } |
96 | *vm_entry = prev; |
97 | return FALSE; |
98 | } |
99 | |
100 | void vm_map_store_entry_link_rb( struct vm_map_header *mapHdr, __unused vm_map_entry_t after_where, vm_map_entry_t entry) |
101 | { |
102 | struct rb_head *rbh = &(mapHdr->rb_head_store); |
103 | struct vm_map_store *store = &(entry->store); |
104 | struct vm_map_store *tmp_store; |
105 | if((tmp_store = RB_INSERT( rb_head, rbh, store )) != NULL) { |
106 | panic("VMSEL: INSERT FAILED: 0x%lx, 0x%lx, 0x%lx, 0x%lx" , (uintptr_t)entry->vme_start, (uintptr_t)entry->vme_end, |
107 | (uintptr_t)(VME_FOR_STORE(tmp_store))->vme_start, (uintptr_t)(VME_FOR_STORE(tmp_store))->vme_end); |
108 | } |
109 | } |
110 | |
111 | void vm_map_store_entry_unlink_rb( struct vm_map_header *mapHdr, vm_map_entry_t entry) |
112 | { |
113 | struct rb_head *rbh = &(mapHdr->rb_head_store); |
114 | struct vm_map_store *rb_entry; |
115 | struct vm_map_store *store = &(entry->store); |
116 | |
117 | rb_entry = RB_FIND( rb_head, rbh, store); |
118 | if(rb_entry == NULL) |
119 | panic("NO ENTRY TO DELETE" ); |
120 | RB_REMOVE( rb_head, rbh, store ); |
121 | } |
122 | |
123 | void |
124 | vm_map_store_copy_reset_rb( vm_map_copy_t copy, vm_map_entry_t entry, int nentries ) |
125 | { |
126 | struct vm_map_header *mapHdr = &(copy->cpy_hdr); |
127 | struct rb_head *rbh = &(mapHdr->rb_head_store); |
128 | struct vm_map_store *store; |
129 | int deleted=0; |
130 | |
131 | while (entry != vm_map_copy_to_entry(copy) && nentries > 0) { |
132 | store = &(entry->store); |
133 | RB_REMOVE( rb_head, rbh, store ); |
134 | entry = entry->vme_next; |
135 | deleted++; |
136 | nentries--; |
137 | } |
138 | } |
139 | |
140 | extern zone_t vm_map_holes_zone; /* zone for vm map holes (vm_map_links) structures */ |
141 | |
142 | void |
143 | vm_map_combine_hole(vm_map_t map, vm_map_entry_t hole_entry); |
144 | void |
145 | vm_map_combine_hole(__unused vm_map_t map, vm_map_entry_t hole_entry) |
146 | { |
147 | |
148 | vm_map_entry_t middle_hole_entry, last_hole_entry; |
149 | |
150 | hole_entry->vme_end = hole_entry->vme_next->vme_end; |
151 | |
152 | middle_hole_entry = hole_entry->vme_next; |
153 | last_hole_entry = middle_hole_entry->vme_next; |
154 | |
155 | assert(last_hole_entry->vme_prev == middle_hole_entry); |
156 | assert(middle_hole_entry->vme_end != last_hole_entry->vme_start); |
157 | |
158 | last_hole_entry->vme_prev = hole_entry; |
159 | hole_entry->vme_next = last_hole_entry; |
160 | |
161 | middle_hole_entry->vme_prev = NULL; |
162 | middle_hole_entry->vme_next = NULL; |
163 | |
164 | zfree(vm_map_holes_zone, middle_hole_entry); |
165 | |
166 | assert(hole_entry->vme_start < hole_entry->vme_end); |
167 | assert(last_hole_entry->vme_start < last_hole_entry->vme_end); |
168 | } |
169 | |
170 | |
171 | void |
172 | vm_map_delete_hole(vm_map_t map, vm_map_entry_t hole_entry); |
173 | void |
174 | vm_map_delete_hole(vm_map_t map, vm_map_entry_t hole_entry) |
175 | { |
176 | if (hole_entry == CAST_TO_VM_MAP_ENTRY(map->holes_list)) { |
177 | |
178 | if (hole_entry->vme_next == CAST_TO_VM_MAP_ENTRY(map->holes_list)) { |
179 | |
180 | map->holes_list = NULL; |
181 | SAVE_HINT_HOLE_WRITE(map, NULL); |
182 | } else { |
183 | |
184 | vm_map_entry_t l_next, l_prev; |
185 | |
186 | l_next = (vm_map_entry_t) map->holes_list->next; |
187 | l_prev = (vm_map_entry_t) map->holes_list->prev; |
188 | map->holes_list = (struct vm_map_links*) l_next; |
189 | |
190 | l_next->vme_prev = l_prev; |
191 | l_prev->vme_next = l_next; |
192 | |
193 | SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) l_next); |
194 | } |
195 | } else { |
196 | |
197 | SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry->vme_prev); |
198 | |
199 | hole_entry->vme_prev->vme_next = hole_entry->vme_next; |
200 | hole_entry->vme_next->vme_prev = hole_entry->vme_prev; |
201 | } |
202 | |
203 | hole_entry->vme_next = NULL; |
204 | hole_entry->vme_prev = NULL; |
205 | zfree(vm_map_holes_zone, hole_entry); |
206 | } |
207 | |
208 | |
209 | /* |
210 | * For Debugging. |
211 | */ |
212 | |
213 | #if DEBUG |
214 | static void |
215 | check_map_sanity(vm_map_t map, vm_map_entry_t old_hole_entry) |
216 | { |
217 | vm_map_entry_t hole_entry, next_hole_entry; |
218 | vm_map_entry_t map_entry, next_map_entry; |
219 | |
220 | if (map->holes_list == NULL) { |
221 | |
222 | return; |
223 | } |
224 | |
225 | hole_entry = (vm_map_entry_t) map->holes_list; |
226 | next_hole_entry = hole_entry->vme_next; |
227 | |
228 | map_entry = vm_map_first_entry(map); |
229 | next_map_entry = map_entry->vme_next; |
230 | |
231 | while(map_entry->vme_start > hole_entry->vme_start) { |
232 | hole_entry = next_hole_entry; |
233 | next_hole_entry = hole_entry->vme_next; |
234 | |
235 | if (hole_entry == (vm_map_entry_t)map->holes_list) |
236 | break; |
237 | } |
238 | |
239 | while (map_entry != vm_map_to_entry(map)) { |
240 | |
241 | if (map_entry->vme_start >= map->max_offset) |
242 | break; |
243 | |
244 | if (map_entry->vme_end != map_entry->vme_next->vme_start) { |
245 | |
246 | if (map_entry->vme_next == vm_map_to_entry(map)) |
247 | break; |
248 | |
249 | if (hole_entry->vme_start != map_entry->vme_end) { |
250 | panic("hole_entry not aligned %p(0x%llx), %p (0x%llx), %p" , hole_entry, (unsigned long long)hole_entry->vme_start, map_entry->vme_next, (unsigned long long)map_entry->vme_end, old_hole_entry); |
251 | assert(hole_entry->vme_start == map_entry->vme_end); |
252 | } |
253 | |
254 | if (hole_entry->vme_end != map_entry->vme_next->vme_start) { |
255 | panic("hole_entry not next aligned %p(0x%llx), %p (0x%llx), %p" , hole_entry, (unsigned long long)hole_entry->vme_end, map_entry->vme_next, (unsigned long long)map_entry->vme_next->vme_start, old_hole_entry); |
256 | assert(hole_entry->vme_end == map_entry->vme_next->vme_start); |
257 | } |
258 | |
259 | hole_entry = next_hole_entry; |
260 | next_hole_entry = hole_entry->vme_next; |
261 | |
262 | if (hole_entry == (vm_map_entry_t)map->holes_list) |
263 | break; |
264 | } |
265 | |
266 | map_entry = map_entry->vme_next; |
267 | } |
268 | } |
269 | |
270 | /* |
271 | * For debugging. |
272 | */ |
273 | static void |
274 | copy_hole_info(vm_map_entry_t hole_entry, vm_map_entry_t old_hole_entry) |
275 | { |
276 | old_hole_entry->vme_prev = hole_entry->vme_prev; |
277 | old_hole_entry->vme_next = hole_entry->vme_next; |
278 | old_hole_entry->vme_start = hole_entry->vme_start; |
279 | old_hole_entry->vme_end = hole_entry->vme_end; |
280 | } |
281 | #endif /* DEBUG */ |
282 | |
283 | void |
284 | update_holes_on_entry_deletion(vm_map_t map, vm_map_entry_t old_entry); |
285 | void |
286 | update_holes_on_entry_deletion(vm_map_t map, vm_map_entry_t old_entry) |
287 | { |
288 | /* |
289 | * Dealing with the deletion of an older entry. |
290 | */ |
291 | |
292 | vm_map_entry_t hole_entry, next_hole_entry; |
293 | #if DEBUG |
294 | struct vm_map_entry old_hole_entry; |
295 | #endif /* DEBUG */ |
296 | boolean_t create_new_hole = TRUE; |
297 | |
298 | hole_entry = CAST_TO_VM_MAP_ENTRY(map->hole_hint); |
299 | |
300 | if (hole_entry) { |
301 | |
302 | if (hole_entry->vme_end == old_entry->vme_start) { |
303 | /* |
304 | * Found a hole right after above our entry. |
305 | * Hit. |
306 | */ |
307 | |
308 | } else if (hole_entry->vme_start == old_entry->vme_end) { |
309 | |
310 | if (hole_entry != CAST_TO_VM_MAP_ENTRY(map->holes_list)) { |
311 | |
312 | /* |
313 | * Found a hole right after below our entry but |
314 | * make sure we don't erroneously extend backwards. |
315 | * |
316 | * Hit. |
317 | */ |
318 | |
319 | hole_entry = hole_entry->vme_prev; |
320 | } |
321 | |
322 | } else if (hole_entry->vme_start > old_entry->vme_end) { |
323 | |
324 | /* |
325 | * Useless hint. Start from the top. |
326 | */ |
327 | |
328 | hole_entry = CAST_TO_VM_MAP_ENTRY(map->holes_list); |
329 | } |
330 | |
331 | if (hole_entry != CAST_TO_VM_MAP_ENTRY(map->holes_list)) { |
332 | if (hole_entry->vme_start > old_entry->vme_start) { |
333 | panic("Hole hint failed: Hole entry start: 0x%llx, entry start: 0x%llx, map hole start: 0x%llx, map hint start: 0x%llx\n" , |
334 | (unsigned long long)hole_entry->vme_start, |
335 | (unsigned long long)old_entry->vme_start, |
336 | (unsigned long long)map->holes_list->start, |
337 | (unsigned long long)map->hole_hint->start); |
338 | } |
339 | if (hole_entry->vme_end > old_entry->vme_start) { |
340 | panic("Hole hint failed: Hole entry end: 0x%llx, entry start: 0x%llx, map hole start: 0x%llx, map hint start: 0x%llx\n" , |
341 | (unsigned long long)hole_entry->vme_end, |
342 | (unsigned long long)old_entry->vme_start, |
343 | (unsigned long long)map->holes_list->start, |
344 | (unsigned long long)map->hole_hint->start); |
345 | } |
346 | } |
347 | |
348 | while (1) { |
349 | |
350 | next_hole_entry = hole_entry->vme_next; |
351 | |
352 | /* |
353 | * Hole is right above the entry. |
354 | */ |
355 | if (hole_entry->vme_end == old_entry->vme_start) { |
356 | |
357 | #if DEBUG |
358 | copy_hole_info(hole_entry, &old_hole_entry); |
359 | #endif /* DEBUG */ |
360 | |
361 | /* |
362 | * Is there another hole right below the entry? |
363 | * Can we combine holes? |
364 | */ |
365 | |
366 | if (old_entry->vme_end == hole_entry->vme_next->vme_start) { |
367 | |
368 | vm_map_combine_hole(map, hole_entry); |
369 | } else { |
370 | |
371 | hole_entry->vme_end = old_entry->vme_end; |
372 | } |
373 | create_new_hole = FALSE; |
374 | #if DEBUG |
375 | check_map_sanity(map, &old_hole_entry); |
376 | #endif /* DEBUG */ |
377 | break; |
378 | } |
379 | |
380 | /* |
381 | * Hole is right below the entry. |
382 | */ |
383 | if (hole_entry->vme_start == old_entry->vme_end) { |
384 | |
385 | #if DEBUG |
386 | copy_hole_info(hole_entry, &old_hole_entry); |
387 | #endif /* DEBUG */ |
388 | |
389 | hole_entry->vme_start = old_entry->vme_start; |
390 | create_new_hole = FALSE; |
391 | |
392 | #if DEBUG |
393 | check_map_sanity(map, &old_hole_entry); |
394 | #endif /* DEBUG */ |
395 | break; |
396 | } |
397 | |
398 | /* |
399 | * Hole is beyond our entry. Let's go back to the last hole |
400 | * before our entry so we have the right place to link up the |
401 | * new hole that will be needed. |
402 | */ |
403 | if (hole_entry->vme_start > old_entry->vme_end) { |
404 | |
405 | #if DEBUG |
406 | copy_hole_info(hole_entry, &old_hole_entry); |
407 | #endif /* DEBUG */ |
408 | |
409 | if (hole_entry != CAST_TO_VM_MAP_ENTRY(map->holes_list)) { |
410 | assert(hole_entry->vme_start != old_entry->vme_start); |
411 | hole_entry = hole_entry->vme_prev; |
412 | } |
413 | break; |
414 | } |
415 | |
416 | hole_entry = next_hole_entry; |
417 | |
418 | if (hole_entry == CAST_TO_VM_MAP_ENTRY(map->holes_list)) { |
419 | hole_entry = hole_entry->vme_prev; |
420 | break; |
421 | } |
422 | } |
423 | } |
424 | |
425 | if (create_new_hole) { |
426 | struct vm_map_links *new_hole_entry = NULL; |
427 | vm_map_entry_t l_next, l_prev; |
428 | |
429 | new_hole_entry = zalloc(vm_map_holes_zone); |
430 | |
431 | /* |
432 | * First hole in the map? |
433 | * OR |
434 | * A hole that is located above the current first hole in the map? |
435 | */ |
436 | if (map->holes_list == NULL || (hole_entry == CAST_TO_VM_MAP_ENTRY(map->holes_list) && hole_entry->vme_start > old_entry->vme_start)) { |
437 | |
438 | if (map->holes_list == NULL) { |
439 | |
440 | map->holes_list = new_hole_entry; |
441 | new_hole_entry->prev = new_hole_entry->next = CAST_TO_VM_MAP_ENTRY(map->holes_list); |
442 | } else { |
443 | |
444 | l_next = CAST_TO_VM_MAP_ENTRY(map->holes_list); |
445 | l_prev = map->holes_list->prev; |
446 | map->holes_list = new_hole_entry; |
447 | new_hole_entry->next = l_next; |
448 | new_hole_entry->prev = l_prev; |
449 | |
450 | l_prev->vme_next = l_next->vme_prev = CAST_TO_VM_MAP_ENTRY(new_hole_entry); |
451 | } |
452 | } else { |
453 | |
454 | l_next = hole_entry->vme_next; |
455 | l_prev = hole_entry->vme_next->vme_prev; |
456 | |
457 | new_hole_entry->prev = hole_entry; |
458 | new_hole_entry->next = l_next; |
459 | |
460 | hole_entry->vme_next = CAST_TO_VM_MAP_ENTRY(new_hole_entry); |
461 | l_next->vme_prev = CAST_TO_VM_MAP_ENTRY(new_hole_entry); |
462 | } |
463 | |
464 | new_hole_entry->start = old_entry->vme_start; |
465 | new_hole_entry->end = old_entry->vme_end; |
466 | |
467 | hole_entry = CAST_TO_VM_MAP_ENTRY(new_hole_entry); |
468 | |
469 | assert(new_hole_entry->start < new_hole_entry->end); |
470 | } |
471 | |
472 | #if DEBUG |
473 | check_map_sanity(map, &old_hole_entry); |
474 | #endif /* DEBUG */ |
475 | |
476 | SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry); |
477 | return; |
478 | } |
479 | |
480 | |
481 | void |
482 | update_holes_on_entry_creation(vm_map_t map, vm_map_entry_t new_entry); |
483 | void |
484 | update_holes_on_entry_creation(vm_map_t map, vm_map_entry_t new_entry) |
485 | { |
486 | |
487 | vm_map_entry_t hole_entry, next_hole_entry; |
488 | #if DEBUG |
489 | struct vm_map_entry old_hole_entry; |
490 | vm_map_entry_t tmp_entry; |
491 | boolean_t check_map_with_hole_sanity = TRUE; |
492 | #endif /* DEBUG */ |
493 | |
494 | /* |
495 | * Case A: The entry is aligned exactly with the start and end of the hole. |
496 | * This will delete the hole. |
497 | * |
498 | * Case B: The entry is completely within a hole but NOT aligned with the start/end of the hole. |
499 | * This will split a hole. |
500 | * |
501 | * Case C: The entry overlaps with the hole. The entry could be extending upwards (C1) or downwards (C2). |
502 | * This will reduce the size of the hole or delete the hole completely if it is smaller than the entry. |
503 | */ |
504 | |
505 | hole_entry = CAST_TO_VM_MAP_ENTRY(map->holes_list); |
506 | assert(hole_entry); |
507 | next_hole_entry = hole_entry->vme_next; |
508 | |
509 | while (1) { |
510 | |
511 | #if DEBUG |
512 | /* |
513 | * If the entry doesn't exist in the RB tree, we are likely dealing with copy maps where |
514 | * the entries belonging to the copy map are linked into the list of entries silently and |
515 | * then added to the RB-tree later on. |
516 | * So sanity checks are useless in that case. |
517 | */ |
518 | check_map_with_hole_sanity = vm_map_lookup_entry(map, new_entry->vme_start, &tmp_entry); |
519 | #endif /* DEBUG */ |
520 | |
521 | if (hole_entry->vme_start == new_entry->vme_start && |
522 | hole_entry->vme_end == new_entry->vme_end) { |
523 | |
524 | /* Case A */ |
525 | #if DEBUG |
526 | copy_hole_info(hole_entry, &old_hole_entry); |
527 | #endif /* DEBUG */ |
528 | |
529 | /* |
530 | * This check makes sense only for regular maps, not copy maps. |
531 | * With a regular map, the VM entry is first linked and then |
532 | * the hole is deleted. So the check below, which makes sure that |
533 | * the map's bounds are being respected, is valid. |
534 | * But for copy maps, the hole is deleted before the VM entry is |
535 | * linked (vm_map_store_copy_insert) and so this check is invalid. |
536 | * |
537 | if (hole_entry == (vm_map_entry_t) map->holes_list) { |
538 | |
539 | if (hole_entry->vme_next == (vm_map_entry_t) map->holes_list) { |
540 | |
541 | next_hole_entry = vm_map_last_entry(map); |
542 | assert(next_hole_entry->vme_end >= map->max_offset); |
543 | } |
544 | } |
545 | */ |
546 | |
547 | vm_map_delete_hole(map, hole_entry); |
548 | |
549 | #if DEBUG |
550 | if (check_map_with_hole_sanity) |
551 | check_map_sanity(map, &old_hole_entry); |
552 | #endif /* DEBUG */ |
553 | return; |
554 | |
555 | } else if (hole_entry->vme_start < new_entry->vme_start && |
556 | hole_entry->vme_end > new_entry->vme_end) { |
557 | |
558 | /* Case B */ |
559 | struct vm_map_links *new_hole_entry = NULL; |
560 | |
561 | new_hole_entry = zalloc(vm_map_holes_zone); |
562 | |
563 | #if DEBUG |
564 | copy_hole_info(hole_entry, &old_hole_entry); |
565 | #endif /* DEBUG */ |
566 | |
567 | new_hole_entry->prev = hole_entry; |
568 | new_hole_entry->next = hole_entry->vme_next; |
569 | hole_entry->vme_next->vme_prev = CAST_TO_VM_MAP_ENTRY(new_hole_entry); |
570 | hole_entry->vme_next = CAST_TO_VM_MAP_ENTRY(new_hole_entry); |
571 | |
572 | new_hole_entry->start = new_entry->vme_end; |
573 | new_hole_entry->end = hole_entry->vme_end; |
574 | hole_entry->vme_end = new_entry->vme_start; |
575 | |
576 | assert(hole_entry->vme_start < hole_entry->vme_end); |
577 | assert(new_hole_entry->start < new_hole_entry->end); |
578 | |
579 | #if DEBUG |
580 | if (check_map_with_hole_sanity) |
581 | check_map_sanity(map, &old_hole_entry); |
582 | #endif /* DEBUG */ |
583 | |
584 | SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry); |
585 | return; |
586 | |
587 | } else if ((new_entry->vme_start <= hole_entry->vme_start) && (hole_entry->vme_start < new_entry->vme_end)) { |
588 | |
589 | /* |
590 | * Case C1: Entry moving upwards and a part/full hole lies within the bounds of the entry. |
591 | */ |
592 | |
593 | #if DEBUG |
594 | copy_hole_info(hole_entry, &old_hole_entry); |
595 | #endif /* DEBUG */ |
596 | |
597 | if (hole_entry->vme_end <= new_entry->vme_end) { |
598 | |
599 | vm_map_delete_hole(map, hole_entry); |
600 | } else { |
601 | hole_entry->vme_start = new_entry->vme_end; |
602 | SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry); |
603 | } |
604 | |
605 | #if DEBUG |
606 | if (check_map_with_hole_sanity) |
607 | check_map_sanity(map, &old_hole_entry); |
608 | #endif /* DEBUG */ |
609 | |
610 | return; |
611 | |
612 | } else if ((new_entry->vme_start < hole_entry->vme_end) && (hole_entry->vme_end <= new_entry->vme_end)) { |
613 | |
614 | /* |
615 | * Case C2: Entry moving downwards and a part/full hole lies within the bounds of the entry. |
616 | */ |
617 | |
618 | #if DEBUG |
619 | copy_hole_info(hole_entry, &old_hole_entry); |
620 | #endif /* DEBUG */ |
621 | |
622 | if (hole_entry->vme_start >= new_entry->vme_start) { |
623 | vm_map_delete_hole(map, hole_entry); |
624 | } else { |
625 | hole_entry->vme_end = new_entry->vme_start; |
626 | SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry); |
627 | } |
628 | |
629 | #if DEBUG |
630 | if (check_map_with_hole_sanity) |
631 | check_map_sanity(map, &old_hole_entry); |
632 | #endif /* DEBUG */ |
633 | |
634 | return; |
635 | } |
636 | |
637 | hole_entry = next_hole_entry; |
638 | next_hole_entry = hole_entry->vme_next; |
639 | |
640 | if (hole_entry == CAST_TO_VM_MAP_ENTRY(map->holes_list)) |
641 | break; |
642 | } |
643 | |
644 | panic("Illegal action: h1: %p, s:0x%llx, e:0x%llx...h2:%p, s:0x%llx, e:0x%llx...h3:0x%p, s:0x%llx, e:0x%llx\n" , |
645 | hole_entry->vme_prev, |
646 | (unsigned long long)hole_entry->vme_prev->vme_start, |
647 | (unsigned long long)hole_entry->vme_prev->vme_end, |
648 | hole_entry, |
649 | (unsigned long long)hole_entry->vme_start, |
650 | (unsigned long long)hole_entry->vme_end, |
651 | hole_entry->vme_next, |
652 | (unsigned long long)hole_entry->vme_next->vme_start, |
653 | (unsigned long long)hole_entry->vme_next->vme_end); |
654 | |
655 | } |
656 | |
657 | void |
658 | update_first_free_rb(vm_map_t map, vm_map_entry_t entry, boolean_t new_entry_creation) |
659 | { |
660 | |
661 | if (map->holelistenabled) { |
662 | |
663 | /* |
664 | * Holes can be used to track ranges all the way up to MACH_VM_MAX_ADDRESS or more (e.g. kernel map). |
665 | */ |
666 | vm_map_offset_t max_valid_offset = (map->max_offset > MACH_VM_MAX_ADDRESS) ? map->max_offset : MACH_VM_MAX_ADDRESS; |
667 | |
668 | /* |
669 | * Clipping an entry will not result in the creation/deletion/modification of |
670 | * a hole. Those calls pass NULL for their target entry. |
671 | */ |
672 | if (entry == NULL) { |
673 | return; |
674 | } |
675 | |
676 | /* |
677 | * Commpage is pinned beyond the map's max offset. That shouldn't affect the |
678 | * holes within the bounds of the map. |
679 | */ |
680 | if (vm_map_trunc_page(entry->vme_start, VM_MAP_PAGE_MASK(map)) >= max_valid_offset) { |
681 | return; |
682 | } |
683 | |
684 | /* |
685 | * |
686 | * Note: |
687 | * |
688 | * - A new entry has already been added to the map |
689 | * OR |
690 | * - An older entry has already been deleted from the map |
691 | * |
692 | * We are updating the hole list after the fact (except in one special case involving copy maps). |
693 | * |
694 | */ |
695 | |
696 | if (new_entry_creation) { |
697 | |
698 | update_holes_on_entry_creation(map, entry); |
699 | } else { |
700 | |
701 | update_holes_on_entry_deletion(map, entry); |
702 | } |
703 | } |
704 | } |
705 | |