osfmk/vm/vm_external.c

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