osfmk/vm/vm_external.c

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