osfmk/vm/vm_map_store.c

   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 <mach/sdt.h>
  30 #include <vm/vm_map_store.h>
  31 #include <vm/vm_pageout.h> /* for vm_debug_events */
  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
  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
  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
  55         if (vm_map_store_has_RB_support( hdr )) {
  56                 vm_map_store_init_rb( hdr );
  57         }
  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
  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         }
  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:
  86                         if((map->holelistenabled == FALSE) && ((entry) == (map)->first_free)) {
  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 {
 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
 117         vm_map_store_copy_insert_ll(map, after_where, copy);
 118 #ifdef VM_MAP_STORE_USE_RB
 119         if (vm_map_store_has_RB_support( &map->hdr )) {
 120                 vm_map_store_copy_insert_rb(map, after_where, copy);
 121         }
 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 {
 141         assert(entry->vme_start < entry->vme_end);
 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
 145         vm_map_store_entry_link_ll(mapHdr, after_where, entry);
 146 #ifdef VM_MAP_STORE_USE_RB
 147         if (vm_map_store_has_RB_support( mapHdr )) {
 148                 vm_map_store_entry_link_rb(mapHdr, after_where, entry);
 149         }
 150 #endif
 151 #if MAP_ENTRY_INSERTION_DEBUG
 152         fastbacktrace(&entry->vme_insertion_bt[0],
 153                       (sizeof (entry->vme_insertion_bt) / sizeof (uintptr_t)));
 154 #endif
 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
 171                 if (vm_map_store_has_RB_support( &VMEL_map->hdr )) {
 172                         update_first_free_rb(VMEL_map, entry, TRUE);
 173                 }
 174 #endif
 175         }
 176 }
 177
 178 void
 179 _vm_map_store_entry_unlink( struct vm_map_header * mapHdr, vm_map_entry_t entry)
 180 {
 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
 184         vm_map_store_entry_unlink_ll(mapHdr, entry);
 185 #ifdef VM_MAP_STORE_USE_RB
 186         if (vm_map_store_has_RB_support( mapHdr )) {
 187                 vm_map_store_entry_unlink_rb(mapHdr, entry);
 188         }
 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;
 196         vm_map_entry_t VMEU_entry = NULL;
 197         vm_map_entry_t VMEU_first_free = NULL;
 198         VMEU_map = (map);
 199         VMEU_entry = (entry);
 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                 }
 207         }
 208         _vm_map_store_entry_unlink(&VMEU_map->hdr, VMEU_entry);
 209         vm_map_store_update( map, entry, VM_MAP_ENTRY_DELETE);
 210         update_first_free_ll(VMEU_map, VMEU_first_free);
 211 #ifdef VM_MAP_STORE_USE_RB
 212         if (vm_map_store_has_RB_support( &VMEU_map->hdr )) {
 213                 update_first_free_rb(VMEU_map, entry, FALSE);
 214         }
 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
 224         if (vm_map_store_has_RB_support( &copy->c_u.hdr )) {
 225                 vm_map_store_copy_reset_rb(copy, entry, nentries);
 226         }
 227 #endif
 228 }
 229
 230 void
 231 vm_map_store_update_first_free( vm_map_t map, vm_map_entry_t first_free_entry, boolean_t new_entry_creation)
 232 {
 233         update_first_free_ll(map, first_free_entry);
 234 #ifdef VM_MAP_STORE_USE_RB
 235         if (vm_map_store_has_RB_support( &map->hdr )) {
 236                 update_first_free_rb(map, first_free_entry, new_entry_creation);
 237         }
 238 #endif
 239 }