osfmk/vm/vm_external.c

   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
 109 static vm_size_t power_of_2(vm_size_t size);
 110
 111 static vm_size_t
 112 power_of_2(vm_size_t size)
 113 {
 114         vm_size_t power;
 115
 116         power = 2 * SMALL_SIZE;
 117         while (power < size) {
 118                 power <<= 1;
 119         }
 120         return(power);
 121 }
 122
 123 vm_external_map_t
 124 vm_external_create(
 125         vm_offset_t     size)
 126 {
 127         vm_size_t               bytes;
 128         vm_external_map_t       result = VM_EXTERNAL_NULL;
 129
 130         bytes = stob(size);
 131         if (bytes <= SMALL_SIZE) {
 132                 if ((result = (vm_external_map_t)kalloc(SMALL_SIZE)) != NULL) {
 133                         memset(result, 0, SMALL_SIZE);
 134                 }
 135         } else if (bytes <= LARGE_SIZE) {
 136                 bytes = power_of_2(bytes);
 137
 138                 if ((result = (vm_external_map_t)kalloc(bytes)) != NULL) {
 139                         memset(result, 0, bytes);
 140                 }
 141         }
 142         return(result);
 143 }
 144
 145 void
 146 vm_external_destroy(
 147         vm_external_map_t       map,
 148         vm_size_t               size)
 149 {
 150         vm_size_t bytes;
 151
 152         if (map == VM_EXTERNAL_NULL)
 153                 return;
 154
 155         bytes = stob(size);
 156         if (bytes <= SMALL_SIZE) {
 157                 bytes = SMALL_SIZE;
 158         } else {
 159                 bytes = power_of_2(bytes);
 160         }
 161         kfree(map, bytes);
 162 }
 163
 164 /*
 165  * Return the number of bytes needed for a vm_external_map given the
 166  * size of the object to be mapped, i.e. the size of the map that was
 167  * created by vm_external_create.
 168  */
 169 vm_size_t
 170 vm_external_map_size(
 171         vm_offset_t     size)
 172 {
 173         vm_size_t       bytes;
 174
 175         bytes = stob(size);
 176         if (bytes != 0) {
 177                 if (bytes <= SMALL_SIZE) {
 178                         bytes = SMALL_SIZE;
 179                 } else {
 180                         bytes = power_of_2(bytes);
 181                 }
 182         }
 183         return bytes;
 184 }
 185
 186 void
 187 vm_external_copy(
 188         vm_external_map_t       old_map,
 189         vm_size_t               old_size,
 190         vm_external_map_t       new_map)
 191 {
 192         /*
 193          * Cannot copy non-existent maps
 194          */
 195         if ((old_map == VM_EXTERNAL_NULL) || (new_map == VM_EXTERNAL_NULL))
 196                 return;
 197
 198         /*
 199          * Copy old map to new
 200          */
 201         memcpy(new_map, old_map, stob(old_size));
 202 }
 203
 204 boolean_t
 205 vm_external_within(
 206         vm_size_t       new_size,
 207         vm_size_t       old_size)
 208 {
 209         vm_size_t       new_bytes;
 210         vm_size_t       old_bytes;
 211
 212         assert(new_size >= old_size);
 213
 214         /*
 215          * "old_bytes" is calculated to be the actual amount of space
 216          * allocated for a map of size "old_size".
 217          */
 218         old_bytes = stob(old_size);
 219         if (old_bytes <= SMALL_SIZE) old_bytes = SMALL_SIZE;
 220         else if (old_bytes <= LARGE_SIZE) old_bytes = power_of_2(old_bytes);
 221
 222         /*
 223          * "new_bytes" is the map size required to map the "new_size" object.
 224          * Since the rounding algorithms are the same, we needn't actually
 225          * round up new_bytes to get the correct answer
 226          */
 227         new_bytes = stob(new_size);
 228
 229         return(new_bytes <= old_bytes);
 230 }
 231
 232 vm_external_state_t
 233 _vm_external_state_get(
 234         vm_external_map_t       map,
 235         vm_offset_t             offset)
 236 {
 237         unsigned
 238         int             bit, byte;
 239
 240         assert (map != VM_EXTERNAL_NULL);
 241
 242         bit = atop_32(offset);
 243         byte = bit >> 3;
 244         if (map[byte] & (1 << (bit & 07))) {
 245                 return VM_EXTERNAL_STATE_EXISTS;
 246         } else {
 247                 return VM_EXTERNAL_STATE_ABSENT;
 248         }
 249 }
 250
 251 void
 252 vm_external_state_set(
 253         vm_external_map_t       map,
 254         vm_offset_t             offset)
 255 {
 256         unsigned
 257         int             bit, byte;
 258
 259         if (map == VM_EXTERNAL_NULL)
 260                 return;
 261
 262         bit = atop_32(offset);
 263         byte = bit >> 3;
 264         map[byte] |= (1 << (bit & 07));
 265 }
 266
 267 void
 268 vm_external_state_clr(
 269         vm_external_map_t       map,
 270         vm_offset_t             offset)
 271 {
 272         unsigned
 273         int             bit, byte;
 274
 275         if (map == VM_EXTERNAL_NULL)
 276                 return;
 277
 278         bit = atop_32(offset);
 279         byte = bit >> 3;
 280         map[byte] &= ~(1 << (bit & 07));
 281 }
 282
 283 void
 284 vm_external_module_initialize(void)
 285 {
 286 }