1/* 2 * Copyright (c) 2000-2004 Apple Computer, 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 * @OSF_COPYRIGHT@ 30 */ 31/* 32 * Mach Operating System 33 * Copyright (c) 1991,1990,1989 Carnegie Mellon University 34 * All Rights Reserved. 35 * 36 * Permission to use, copy, modify and distribute this software and its 37 * documentation is hereby granted, provided that both the copyright 38 * notice and this permission notice appear in all copies of the 39 * software, derivative works or modified versions, and any portions 40 * thereof, and that both notices appear in supporting documentation. 41 * 42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR 44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 45 * 46 * Carnegie Mellon requests users of this software to return to 47 * 48 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 49 * School of Computer Science 50 * Carnegie Mellon University 51 * Pittsburgh PA 15213-3890 52 * 53 * any improvements or extensions that they make and grant Carnegie Mellon 54 * the rights to redistribute these changes. 55 */ 56/* 57 */ 58 59/* 60 * This module maintains information about the presence of 61 * pages not in memory. Since an external memory object 62 * must maintain a complete knowledge of its contents, this 63 * information takes the form of hints. 64 */ 65#include <string.h> /* for memcpy()/memset() */ 66 67#include <mach/boolean.h> 68#include <vm/vm_external.h> 69#include <kern/kalloc.h> 70#include <mach/vm_param.h> 71#include <kern/assert.h> 72 73/* 74 * The implementation uses bit arrays to record whether 75 * a page has been written to external storage. For 76 * convenience, these bit arrays come in various sizes. 77 * For example, a map N bytes long can record: 78 * 79 * 16 bytes = 128 pages = (@ 4KB/page) 512KB 80 * 1024 bytes = 8192 pages = (@ 4KB/page) 32MB 81 * 4096 bytes = 32768 pages = (@ 4KB/page) 128MB 82 * 83 * For a 32-bit machine with 4KB pages, the largest size 84 * would be 128KB = 32 pages. Machines with a larger page 85 * size are more efficient. 86 * 87 * This subsystem must be very careful about memory allocation, 88 * since vm_external_create() is almost always called with 89 * vm_privilege set. The largest map to be allocated must be less 90 * than or equal to a single page, and the kalloc subsystem must 91 * never allocate more than a single page in response to a kalloc() 92 * request. Also, vm_external_destroy() must not take any blocking 93 * locks, since it is called with a vm_object lock held. This 94 * implies that kfree() MUST be implemented in terms of zfree() 95 * NOT kmem_free() for all request sizes that this subsystem uses. 96 * 97 * For efficiency, this subsystem knows that the kalloc() subsystem 98 * is implemented in terms of power-of-2 allocation, and that the 99 * minimum allocation unit is KALLOC_MINSIZE 100 * 101 * XXXO 102 * Should consider using existence_map to hold bits directly 103 * when existence_size <= 4 bytes (i.e., 32 pages). 104 */ 105 106#define SMALL_SIZE KALLOC_MINSIZE 107#define LARGE_SIZE PAGE_SIZE 108 109static vm_object_size_t power_of_2(vm_object_size_t size); 110 111static vm_object_size_t 112power_of_2(vm_object_size_t size) 113{ 114 vm_object_size_t power; 115 116 power = 2 * SMALL_SIZE; 117 while (power < size) { 118 power <<= 1; 119 } 120 return(power); 121} 122 123vm_external_map_t 124vm_external_create( 125 vm_object_offset_t size) 126{ 127 vm_object_size_t bytes; 128 vm_external_map_t result = VM_EXTERNAL_NULL; 129 130 bytes = stob(size); 131 if (bytes <= SMALL_SIZE) { 132 result = (vm_external_map_t)kalloc(SMALL_SIZE); 133 if (result != NULL) { 134 memset(result, 0, SMALL_SIZE); 135 } 136 } else if (bytes <= LARGE_SIZE) { 137 bytes = power_of_2(bytes); 138 139 assert((vm_size_t) bytes == bytes); 140 result = (vm_external_map_t)kalloc((vm_size_t)bytes); 141 if (result != NULL) { 142 assert((size_t) bytes == bytes); 143 memset(result, 0, (size_t) bytes); 144 } 145 } 146 return(result); 147} 148 149void 150vm_external_destroy( 151 vm_external_map_t map, 152 vm_object_size_t size) 153{ 154 vm_object_size_t bytes; 155 156 if (map == VM_EXTERNAL_NULL) 157 return; 158 159 bytes = stob(size); 160 if (bytes <= SMALL_SIZE) { 161 bytes = SMALL_SIZE; 162 } else { 163 bytes = power_of_2(bytes); 164 } 165 assert((vm_size_t) bytes == bytes); 166 kfree(map, (vm_size_t) bytes); 167} 168 169/* 170 * Return the number of bytes needed for a vm_external_map given the 171 * size of the object to be mapped, i.e. the size of the map that was 172 * created by vm_external_create. 173 */ 174vm_object_size_t 175vm_external_map_size( 176 vm_object_size_t size) 177{ 178 vm_object_size_t bytes; 179 180 bytes = stob(size); 181 if (bytes != 0) { 182 if (bytes <= SMALL_SIZE) { 183 bytes = SMALL_SIZE; 184 } else { 185 bytes = power_of_2(bytes); 186 } 187 } 188 return bytes; 189} 190 191void 192vm_external_copy( 193 vm_external_map_t old_map, 194 vm_object_size_t old_size, 195 vm_external_map_t new_map) 196{ 197 vm_object_size_t bytes; 198 199 /* 200 * Cannot copy non-existent maps 201 */ 202 if ((old_map == VM_EXTERNAL_NULL) || (new_map == VM_EXTERNAL_NULL)) 203 return; 204 205 /* 206 * Copy old map to new 207 */ 208 bytes = stob(old_size); 209 assert((size_t) bytes == bytes); 210 memcpy(new_map, old_map, (size_t) bytes); 211} 212 213boolean_t 214vm_external_within( 215 vm_object_size_t new_size, 216 vm_object_size_t old_size) 217{ 218 vm_object_size_t new_bytes; 219 vm_object_size_t old_bytes; 220 221 assert(new_size >= old_size); 222 223 /* 224 * "old_bytes" is calculated to be the actual amount of space 225 * allocated for a map of size "old_size". 226 */ 227 old_bytes = stob(old_size); 228 if (old_bytes <= SMALL_SIZE) old_bytes = SMALL_SIZE; 229 else if (old_bytes <= LARGE_SIZE) old_bytes = power_of_2(old_bytes); 230 231 /* 232 * "new_bytes" is the map size required to map the "new_size" object. 233 * Since the rounding algorithms are the same, we needn't actually 234 * round up new_bytes to get the correct answer 235 */ 236 new_bytes = stob(new_size); 237 238 return(new_bytes <= old_bytes); 239} 240 241vm_external_state_t 242_vm_external_state_get( 243 vm_external_map_t map, 244 vm_object_offset_t offset) 245{ 246 uint64_t bit, byte; 247 248 assert (map != VM_EXTERNAL_NULL); 249 250 bit = atop_64(offset); 251 byte = bit >> 3; 252 if (map[byte] & (1 << (bit & 07))) { 253 return VM_EXTERNAL_STATE_EXISTS; 254 } else { 255 return VM_EXTERNAL_STATE_ABSENT; 256 } 257} 258 259void 260vm_external_state_set( 261 vm_external_map_t map, 262 vm_object_offset_t offset) 263{ 264 uint64_t bit, byte; 265 266 if (map == VM_EXTERNAL_NULL) 267 return; 268 269 bit = atop_64(offset); 270 byte = bit >> 3; 271 map[byte] |= (1 << (bit & 07)); 272} 273 274void 275vm_external_state_clr( 276 vm_external_map_t map, 277 vm_object_offset_t offset) 278{ 279 uint64_t bit, byte; 280 281 if (map == VM_EXTERNAL_NULL) 282 return; 283 284 bit = atop_64(offset); 285 byte = bit >> 3; 286 map[byte] &= ~(1 << (bit & 07)); 287} 288 289void 290vm_external_module_initialize(void) 291{ 292} 293