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_object_size_t power_of_2(vm_object_size_t size);
 110
 111 static vm_object_size_t
 112 power_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
 123 vm_external_map_t
 124 vm_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
 149 void
 150 vm_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  */
 174 vm_object_size_t
 175 vm_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
 191 void
 192 vm_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
 213 boolean_t
 214 vm_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
 241 vm_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
 259 void
 260 vm_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
 274 void
 275 vm_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
 289 void
 290 vm_external_module_initialize(void)
 291 {
 292 }