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 #ifndef _VM_VM_MAP_STORE_H 30 #define _VM_VM_MAP_STORE_H 31 32 #ifndef VM_MAP_STORE_USE_RB 33 #define VM_MAP_STORE_USE_RB 34 #endif 35 36 #include <libkern/tree.h> 37 #include <mach/shared_region.h> 38 39 struct _vm_map; 40 struct vm_map_entry; 41 struct vm_map_copy; 42 struct vm_map_header; 43 44 struct vm_map_store { 45 #ifdef VM_MAP_STORE_USE_RB 46 RB_ENTRY(vm_map_store) entry; 47 #endif 48 }; 49 50 #ifdef VM_MAP_STORE_USE_RB 51 RB_HEAD(rb_head, vm_map_store); 52 #endif 53 54 #define VM_ENTRY_PACKED_PTR_BITS 48 55 #define VM_ENTRY_PACKED_PTR_SHIFT 0 56 #define VM_ENTRY_PACKED_PTR_BASE ((uintptr_t)0) 57 58 #define VM_PREV_PACK(prev) (uintptr_t) (VM_PACK_POINTER((uintptr_t)(prev), VM_ENTRY_PACKED_PTR)) 59 #define VM_PREV_UNPACK(p) ((vm_map_entry_t) VM_UNPACK_POINTER((vm_offset_t)p, VM_ENTRY_PACKED_PTR)) 60 static_assert(VM_KERNEL_POINTER_SIGNIFICANT_BITS <= VM_ENTRY_PACKED_PTR_BITS); 61 62 /* 63 * Type: vm_map_entry_t [internal use only] 64 * 65 * Description: 66 * A single mapping within an address map. 67 * 68 * Implementation: 69 * Address map entries consist of start and end addresses, 70 * a VM object (or sub map) and offset into that object, 71 * and user-exported inheritance and protection information. 72 * Control information for virtual copy operations is also 73 * stored in the address map entry. 74 * 75 * Note: 76 * vm_map_relocate_early_elem() knows about this layout, 77 * and needs to be kept in sync. 78 */ 79 struct vm_map_links { 80 uintptr_t prev : VM_ENTRY_PACKED_PTR_BITS; 81 uint8_t vme_zero_wire_count_waiters :1; 82 struct vm_map_entry *next; /* next entry */ 83 vm_map_offset_t start; /* start address */ 84 vm_map_offset_t end; /* end address */ 85 }; 86 87 88 /* 89 * Type: struct vm_map_header 90 * 91 * Description: 92 * Header for a vm_map and a vm_map_copy. 93 * 94 * Note: 95 * vm_map_relocate_early_elem() knows about this layout, 96 * and needs to be kept in sync. 97 */ 98 struct vm_map_header { 99 struct vm_map_links links; /* first, last, min, max */ 100 int nentries; /* Number of entries */ 101 uint16_t page_shift; /* page shift */ 102 uint16_t entries_pageable : 1; /* are map entries pageable? */ 103 uint16_t __padding : 15; 104 #ifdef VM_MAP_STORE_USE_RB 105 struct rb_head rb_head_store; 106 #endif /* VM_MAP_STORE_USE_RB */ 107 }; 108 109 #define VM_MAP_HDR_PAGE_SHIFT(hdr) ((hdr)->page_shift) 110 #define VM_MAP_HDR_PAGE_SIZE(hdr) (1 << VM_MAP_HDR_PAGE_SHIFT((hdr))) 111 #define VM_MAP_HDR_PAGE_MASK(hdr) (VM_MAP_HDR_PAGE_SIZE((hdr)) - 1) 112 113 114 #include <vm/vm_map_store_ll_internal.h> 115 #include <vm/vm_map_store_rb_internal.h> 116 117 /* 118 * SAVE_HINT_MAP_WRITE: 119 * 120 * Saves the specified entry as the hint for 121 * future lookups. write lock held on map, 122 * so no one else can be writing or looking 123 * until the lock is dropped. 124 */ 125 #define SAVE_HINT_MAP_WRITE(map, value) \ 126 MACRO_BEGIN \ 127 (map)->hint = (value); \ 128 MACRO_END 129 130 #define SAVE_HINT_HOLE_WRITE(map, value) \ 131 MACRO_BEGIN \ 132 (map)->hole_hint = (value); \ 133 MACRO_END 134 135 #define SKIP_RB_TREE 0xBAADC0D1 136 137 extern void vm_map_store_init( 138 struct vm_map_header *header); 139 140 extern bool vm_map_store_lookup_entry( 141 struct _vm_map *map, 142 vm_map_offset_t address, 143 struct vm_map_entry **entryp); 144 145 extern void _vm_map_store_entry_link( 146 struct vm_map_header *header, 147 struct vm_map_entry *after_where, 148 struct vm_map_entry *entry); 149 150 extern void vm_map_store_entry_link( 151 struct _vm_map *map, 152 struct vm_map_entry *after_where, 153 struct vm_map_entry *entry, 154 vm_map_kernel_flags_t vmk_flags); 155 156 extern void _vm_map_store_entry_unlink( 157 struct vm_map_header *header, 158 struct vm_map_entry *entry, 159 bool check_permanent); 160 161 extern void vm_map_store_entry_unlink( 162 struct _vm_map *map, 163 struct vm_map_entry *entry, 164 bool check_permanent); 165 166 extern void vm_map_store_update_first_free( 167 struct _vm_map *map, 168 struct vm_map_entry *entry, 169 bool new_entry_creation); 170 171 extern void vm_map_store_copy_reset( 172 struct vm_map_copy *copy_map, 173 struct vm_map_entry *entry); 174 175 #if MACH_ASSERT 176 extern bool first_free_is_valid_store( 177 struct _vm_map *map); 178 #endif 179 180 extern bool vm_map_store_has_RB_support( 181 struct vm_map_header *header); 182 183 extern struct vm_map_entry *vm_map_store_find_space( 184 vm_map_t map, 185 vm_map_offset_t hint, 186 vm_map_offset_t limit, 187 bool backwards, 188 vm_map_offset_t guard_offset, 189 vm_map_size_t size, 190 vm_map_offset_t mask, 191 vm_map_offset_t *addr_out); 192 193 #endif /* _VM_VM_MAP_STORE_H */ 194