osfmk/vm/vm_external.c

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