osfmk/vm/vm_external.c

   1 /*
   2  * Copyright (c) 2000 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((vm_offset_t)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         return bytes;
 177 }
 178
 179 void
 180 vm_external_copy(
 181         vm_external_map_t       old_map,
 182         vm_size_t               old_size,
 183         vm_external_map_t       new_map)
 184 {
 185         /*
 186          * Cannot copy non-existent maps
 187          */
 188         if ((old_map == VM_EXTERNAL_NULL) || (new_map == VM_EXTERNAL_NULL))
 189                 return;
 190
 191         /*
 192          * Copy old map to new
 193          */
 194         memcpy(new_map, old_map, stob(old_size));
 195 }
 196
 197 boolean_t
 198 vm_external_within(
 199         vm_size_t       new_size,
 200         vm_size_t       old_size)
 201 {
 202         vm_size_t       new_bytes;
 203         vm_size_t       old_bytes;
 204
 205         assert(new_size >= old_size);
 206
 207         /*
 208          * "old_bytes" is calculated to be the actual amount of space
 209          * allocated for a map of size "old_size".
 210          */
 211         old_bytes = stob(old_size);
 212         if (old_bytes <= SMALL_SIZE) old_bytes = SMALL_SIZE;
 213         else if (old_bytes <= LARGE_SIZE) old_bytes = power_of_2(old_bytes);
 214
 215         /*
 216          * "new_bytes" is the map size required to map the "new_size" object.
 217          * Since the rounding algorithms are the same, we needn't actually
 218          * round up new_bytes to get the correct answer
 219          */
 220         new_bytes = stob(new_size);
 221
 222         return(new_bytes <= old_bytes);
 223 }
 224
 225 vm_external_state_t
 226 _vm_external_state_get(
 227         vm_external_map_t       map,
 228         vm_offset_t             offset)
 229 {
 230         unsigned
 231         int             bit, byte;
 232
 233         assert (map != VM_EXTERNAL_NULL);
 234
 235         bit = atop(offset);
 236         byte = bit >> 3;
 237         if (map[byte] & (1 << (bit & 07))) {
 238                 return VM_EXTERNAL_STATE_EXISTS;
 239         } else {
 240                 return VM_EXTERNAL_STATE_ABSENT;
 241         }
 242 }
 243
 244 void
 245 vm_external_state_set(
 246         vm_external_map_t       map,
 247         vm_offset_t             offset)
 248 {
 249         unsigned
 250         int             bit, byte;
 251
 252         if (map == VM_EXTERNAL_NULL)
 253                 return;
 254
 255         bit = atop(offset);
 256         byte = bit >> 3;
 257         map[byte] |= (1 << (bit & 07));
 258 }
 259
 260 void
 261 vm_external_state_clr(
 262         vm_external_map_t       map,
 263         vm_offset_t             offset)
 264 {
 265         unsigned
 266         int             bit, byte;
 267
 268         if (map == VM_EXTERNAL_NULL)
 269                 return;
 270
 271         bit = atop(offset);
 272         byte = bit >> 3;
 273         map[byte] &= ~(1 << (bit & 07));
 274 }
 275
 276 void
 277 vm_external_module_initialize(void)
 278 {
 279 }