sys/uvm/uvm_amap.h

   1 /*      $NetBSD: uvm_amap.h,v 1.33 2007/07/21 19:21:53 ad Exp $ */
   2
   3 /*
   4  *
   5  * Copyright (c) 1997 Charles D. Cranor and Washington University.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by Charles D. Cranor and
  19  *      Washington University.
  20  * 4. The name of the author may not be used to endorse or promote products
  21  *    derived from this software without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  24  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  25  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  26  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  28  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  29  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  30  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  32  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 #ifndef _UVM_UVM_AMAP_H_
  36 #define _UVM_UVM_AMAP_H_
  37
  38 /*
  39  * uvm_amap.h: general amap interface and amap implementation-specific info
  40  */
  41
  42 /*
  43  * an amap structure contains pointers to a set of anons that are
  44  * mapped together in virtual memory (an anon is a single page of
  45  * anonymous virtual memory -- see uvm_anon.h).  in uvm we hide the
  46  * details of the implementation of amaps behind a general amap
  47  * interface.  this allows us to change the amap implementation
  48  * without having to touch the rest of the code.  this file is divided
  49  * into two parts: the definition of the uvm amap interface and the
  50  * amap implementation-specific definitions.
  51  */
  52
  53 #ifdef _KERNEL
  54
  55 /*
  56  * part 1: amap interface
  57  */
  58
  59 void    uvm_amap_init(void);
  60
  61 /*
  62  * forward definition of vm_amap structure.  only amap
  63  * implementation-specific code should directly access the fields of
  64  * this structure.
  65  */
  66
  67 struct vm_amap;
  68
  69
  70 /*
  71  * prototypes for the amap interface
  72  */
  73
  74 void            amap_add        /* add an anon to an amap */
  75                         (struct vm_aref *, vaddr_t,
  76                          struct vm_anon *, bool);
  77 struct vm_amap  *amap_alloc     /* allocate a new amap */
  78                         (vaddr_t, vaddr_t, int);
  79 void            amap_copy       /* clear amap needs-copy flag */
  80                         (struct vm_map *, struct vm_map_entry *, int,
  81                          vaddr_t, vaddr_t);
  82 void            amap_cow_now    /* resolve all COW faults now */
  83                         (struct vm_map *, struct vm_map_entry *);
  84 int             amap_extend     /* make amap larger */
  85                         (struct vm_map_entry *, vsize_t, int);
  86 int             amap_flags      /* get amap's flags */
  87                         (struct vm_amap *);
  88 void            amap_free       /* free amap */
  89                         (struct vm_amap *);
  90 void            amap_lock       /* lock amap */
  91                         (struct vm_amap *);
  92 struct vm_anon  *amap_lookup    /* lookup an anon @ offset in amap */
  93                         (struct vm_aref *, vaddr_t);
  94 void            amap_lookups    /* lookup multiple anons */
  95                         (struct vm_aref *, vaddr_t,
  96                          struct vm_anon **, int);
  97 void            amap_ref        /* add a reference to an amap */
  98                         (struct vm_amap *, vaddr_t, vsize_t, int);
  99 int             amap_refs       /* get number of references of amap */
 100                         (struct vm_amap *);
 101 void            amap_share_protect /* protect pages in a shared amap */
 102                         (struct vm_map_entry *, vm_prot_t);
 103 void            amap_splitref   /* split reference to amap into two */
 104                         (struct vm_aref *, struct vm_aref *, vaddr_t);
 105 void            amap_unadd      /* remove an anon from an amap */
 106                         (struct vm_aref *, vaddr_t);
 107 void            amap_unlock     /* unlock amap */
 108                         (struct vm_amap *);
 109 void            amap_unref      /* drop reference to an amap */
 110                         (struct vm_amap *, vaddr_t, vsize_t, bool);
 111 void            amap_wipeout    /* remove all anons from amap */
 112                         (struct vm_amap *);
 113 bool            amap_swap_off
 114                         (int, int);
 115
 116 /*
 117  * amap flag values
 118  */
 119
 120 #define AMAP_SHARED     0x1     /* amap is shared */
 121 #define AMAP_REFALL     0x2     /* amap_ref: reference entire amap */
 122 #define AMAP_SWAPOFF    0x4     /* amap_swap_off() is in progress */
 123
 124 /*
 125  * amap_copy flags
 126  */
 127
 128 #define AMAP_COPY_NOWAIT        0x02    /* not allowed to sleep */
 129 #define AMAP_COPY_NOCHUNK       0x04    /* not allowed to chunk */
 130 #define AMAP_COPY_NOMERGE       0x08    /* not allowed to merge */
 131
 132 /*
 133  * amap_extend flags
 134  */
 135 #define AMAP_EXTEND_BACKWARDS   0x00    /* add "size" to start of map */
 136 #define AMAP_EXTEND_FORWARDS    0x01    /* add "size" to end of map */
 137 #define AMAP_EXTEND_NOWAIT      0x02    /* not allowed to sleep */
 138
 139 #endif /* _KERNEL */
 140
 141 /**********************************************************************/
 142
 143 /*
 144  * part 2: amap implementation-specific info
 145  */
 146
 147 /*
 148  * we currently provide an array-based amap implementation.  in this
 149  * implementation we provide the option of tracking split references
 150  * so that we don't lose track of references during partial unmaps
 151  * ... this is enabled with the "UVM_AMAP_PPREF" define.
 152  */
 153
 154 #define UVM_AMAP_PPREF          /* track partial references */
 155
 156 /*
 157  * here is the definition of the vm_amap structure for this implementation.
 158  */
 159
 160 struct vm_amap {
 161         kmutex_t am_l;          /* lock [locks all vm_amap fields] */
 162         int am_ref;             /* reference count */
 163         int am_flags;           /* flags */
 164         int am_maxslot;         /* max # of slots allocated */
 165         int am_nslot;           /* # of slots currently in map ( <= maxslot) */
 166         int am_nused;           /* # of slots currently in use */
 167         int *am_slots;          /* contig array of active slots */
 168         int *am_bckptr;         /* back pointer array to am_slots */
 169         struct vm_anon **am_anon; /* array of anonymous pages */
 170 #ifdef UVM_AMAP_PPREF
 171         int *am_ppref;          /* per page reference count (if !NULL) */
 172 #endif
 173         LIST_ENTRY(vm_amap) am_list;
 174 };
 175
 176 /*
 177  * note that am_slots, am_bckptr, and am_anon are arrays.   this allows
 178  * fast lookup of pages based on their virual address at the expense of
 179  * some extra memory.   in the future we should be smarter about memory
 180  * usage and fall back to a non-array based implementation on systems
 181  * that are short of memory (XXXCDC).
 182  *
 183  * the entries in the array are called slots... for example an amap that
 184  * covers four pages of virtual memory is said to have four slots.   here
 185  * is an example of the array usage for a four slot amap.   note that only
 186  * slots one and three have anons assigned to them.  "D/C" means that we
 187  * "don't care" about the value.
 188  *
 189  *            0     1      2     3
 190  * am_anon:   NULL, anon0, NULL, anon1          (actual pointers to anons)
 191  * am_bckptr: D/C,  1,     D/C,  0              (points to am_slots entry)
 192  *
 193  * am_slots:  3, 1, D/C, D/C                    (says slots 3 and 1 are in use)
 194  *
 195  * note that am_bckptr is D/C if the slot in am_anon is set to NULL.
 196  * to find the entry in am_slots for an anon, look at am_bckptr[slot],
 197  * thus the entry for slot 3 in am_slots[] is at am_slots[am_bckptr[3]].
 198  * in general, if am_anon[X] is non-NULL, then the following must be
 199  * true: am_slots[am_bckptr[X]] == X
 200  *
 201  * note that am_slots is always contig-packed.
 202  */
 203
 204 /*
 205  * defines for handling of large, sparse amaps:
 206  *
 207  * one of the problems of array-based amaps is that if you allocate a
 208  * large, sparsely-used area of virtual memory you end up allocating
 209  * large arrays that, for the most part, don't get used.  this is a
 210  * problem for BSD in that the kernel likes to make these types of
 211  * allocations to "reserve" memory for possible future use.
 212  *
 213  * for example, the kernel allocates (reserves) a large chunk of user
 214  * VM for possible stack growth.  most of the time only a page or two
 215  * of this VM is actually used.  since the stack is anonymous memory
 216  * it makes sense for it to live in an amap, but if we allocated an
 217  * amap for the entire stack range we could end up wasting a large
 218  * amount of malloc'd KVM.
 219  *
 220  * for example, on the i386 at boot time we allocate two amaps for the stack
 221  * of /sbin/init:
 222  *  1. a 7680 slot amap at protection 0 (reserve space for stack)
 223  *  2. a 512 slot amap at protection 7 (top of stack)
 224  *
 225  * most of the array allocated for the amaps for this is never used.
 226  * the amap interface provides a way for us to avoid this problem by
 227  * allowing amap_copy() to break larger amaps up into smaller sized
 228  * chunks (controlled by the "canchunk" option).   we use this feature
 229  * to reduce our memory usage with the BSD stack management.  if we
 230  * are asked to create an amap with more than UVM_AMAP_LARGE slots in it,
 231  * we attempt to break it up into a UVM_AMAP_CHUNK sized amap if the
 232  * "canchunk" flag is set.
 233  *
 234  * so, in the i386 example, the 7680 slot area is never referenced so
 235  * nothing gets allocated (amap_copy is never called because the protection
 236  * is zero).   the 512 slot area for the top of the stack is referenced.
 237  * the chunking code breaks it up into 16 slot chunks (hopefully a single
 238  * 16 slot chunk is enough to handle the whole stack).
 239  */
 240
 241 #define UVM_AMAP_LARGE  256     /* # of slots in "large" amap */
 242 #define UVM_AMAP_CHUNK  16      /* # of slots to chunk large amaps in */
 243
 244 #ifdef _KERNEL
 245
 246 /*
 247  * macros
 248  */
 249
 250 /* AMAP_B2SLOT: convert byte offset to slot */
 251 #define AMAP_B2SLOT(S,B) {                                              \
 252         KASSERT(((B) & (PAGE_SIZE - 1)) == 0);                          \
 253         (S) = (B) >> PAGE_SHIFT;                                        \
 254 }
 255
 256 /*
 257  * lock/unlock/refs/flags macros
 258  */
 259
 260 #define amap_flags(AMAP)        ((AMAP)->am_flags)
 261 #define amap_lock(AMAP)         mutex_enter(&(AMAP)->am_l)
 262 #define amap_lock_try(AMAP)     mutex_tryenter(&(AMAP)->am_l)
 263 #define amap_refs(AMAP)         ((AMAP)->am_ref)
 264 #define amap_unlock(AMAP)       mutex_exit(&(AMAP)->am_l)
 265
 266 /*
 267  * if we enable PPREF, then we have a couple of extra functions that
 268  * we need to prototype here...
 269  */
 270
 271 #ifdef UVM_AMAP_PPREF
 272
 273 #define PPREF_NONE ((int *) -1) /* not using ppref */
 274
 275 void            amap_pp_adjref          /* adjust references */
 276                         (struct vm_amap *, int, vsize_t, int);
 277 void            amap_pp_establish       /* establish ppref */
 278                         (struct vm_amap *, vaddr_t);
 279 void            amap_wiperange          /* wipe part of an amap */
 280                         (struct vm_amap *, int, int);
 281 #endif  /* UVM_AMAP_PPREF */
 282
 283 #endif /* _KERNEL */
 284
 285 #endif /* _UVM_UVM_AMAP_H_ */