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