FreeBSD/Linux Kernel Cross Reference
sys/uvm/uvm_amap.c

     /*      $OpenBSD: uvm_amap.c,v 1.91 2022/08/01 14:15:46 mpi Exp $       */
     /*      $NetBSD: uvm_amap.c,v 1.27 2000/11/25 06:27:59 chs Exp $        */
     
     /*
      * Copyright (c) 1997 Charles D. Cranor and Washington University.
      * All rights reserved.
      *
      * Redistribution and use in source and binary forms, with or without
      * modification, are permitted provided that the following conditions
     * are met:
     * 1. Redistributions of source code must retain the above copyright
     *    notice, this list of conditions and the following disclaimer.
     * 2. Redistributions in binary form must reproduce the above copyright
     *    notice, this list of conditions and the following disclaimer in the
     *    documentation and/or other materials provided with the distribution.
     *
     * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     */
    
    /*
     * uvm_amap.c: amap operations
     *
     * this file contains functions that perform operations on amaps.  see
     * uvm_amap.h for a brief explanation of the role of amaps in uvm.
     */
    
    #include <sys/param.h>
    #include <sys/systm.h>
    #include <sys/malloc.h>
    #include <sys/kernel.h>
    #include <sys/pool.h>
    #include <sys/atomic.h>
    
    #include <uvm/uvm.h>
    #include <uvm/uvm_swap.h>
    
    /*
     * pools for allocation of vm_amap structures.  note that in order to
     * avoid an endless loop, the amap pool's allocator cannot allocate
     * memory from an amap (it currently goes through the kernel uobj, so
     * we are ok).
     */
    
    struct pool uvm_amap_pool;
    struct pool uvm_small_amap_pool[UVM_AMAP_CHUNK];
    struct pool uvm_amap_chunk_pool;
    
    LIST_HEAD(, vm_amap) amap_list;
    struct rwlock amap_list_lock = RWLOCK_INITIALIZER("amaplstlk");
    #define amap_lock_list()        rw_enter_write(&amap_list_lock)
    #define amap_unlock_list()      rw_exit_write(&amap_list_lock)
    
    static char amap_small_pool_names[UVM_AMAP_CHUNK][9];
    
    /*
     * local functions
     */
    
    static struct vm_amap *amap_alloc1(int, int, int);
    static inline void amap_list_insert(struct vm_amap *);
    static inline void amap_list_remove(struct vm_amap *);   
    
    struct vm_amap_chunk *amap_chunk_get(struct vm_amap *, int, int, int);
    void amap_chunk_free(struct vm_amap *, struct vm_amap_chunk *);
    
    /*
     * if we enable PPREF, then we have a couple of extra functions that
     * we need to prototype here...
     */
    
    #ifdef UVM_AMAP_PPREF
    
    #define PPREF_NONE ((int *) -1) /* not using ppref */
    
    void    amap_pp_adjref(struct vm_amap *, int, vsize_t, int);
    void    amap_pp_establish(struct vm_amap *);
    void    amap_wiperange_chunk(struct vm_amap *, struct vm_amap_chunk *, int,
                int);
    void    amap_wiperange(struct vm_amap *, int, int);
    
    #endif  /* UVM_AMAP_PPREF */
    
    static inline void
    amap_list_insert(struct vm_amap *amap)
    {
            amap_lock_list();
            LIST_INSERT_HEAD(&amap_list, amap, am_list);
            amap_unlock_list();
    }
    
   static inline void
   amap_list_remove(struct vm_amap *amap)
   {
           amap_lock_list();
           LIST_REMOVE(amap, am_list);
           amap_unlock_list();
   }
   
   /*
    * amap_chunk_get: lookup a chunk for slot. if create is non-zero,
    * the chunk is created if it does not yet exist.
    *
    * => returns the chunk on success or NULL on error
    */
   struct vm_amap_chunk *
   amap_chunk_get(struct vm_amap *amap, int slot, int create, int waitf)
   {
           int bucket = UVM_AMAP_BUCKET(amap, slot);
           int baseslot = AMAP_BASE_SLOT(slot);
           int n;
           struct vm_amap_chunk *chunk, *newchunk, *pchunk = NULL;
   
           if (UVM_AMAP_SMALL(amap))
                   return &amap->am_small;
   
           for (chunk = amap->am_buckets[bucket]; chunk != NULL;
               chunk = TAILQ_NEXT(chunk, ac_list)) {
                   if (UVM_AMAP_BUCKET(amap, chunk->ac_baseslot) != bucket)
                           break;
                   if (chunk->ac_baseslot == baseslot)
                           return chunk;
                   pchunk = chunk;
           }
           if (!create)
                   return NULL;
   
           if (amap->am_nslot - baseslot >= UVM_AMAP_CHUNK)
                   n = UVM_AMAP_CHUNK;
           else
                   n = amap->am_nslot - baseslot;
   
           newchunk = pool_get(&uvm_amap_chunk_pool, waitf | PR_ZERO);
           if (newchunk == NULL)
                   return NULL;
   
           if (pchunk == NULL) {
                   TAILQ_INSERT_TAIL(&amap->am_chunks, newchunk, ac_list);
                   KASSERT(amap->am_buckets[bucket] == NULL);
                   amap->am_buckets[bucket] = newchunk;
           } else
                   TAILQ_INSERT_AFTER(&amap->am_chunks, pchunk, newchunk,
                       ac_list);
   
           amap->am_ncused++;
           newchunk->ac_baseslot = baseslot;
           newchunk->ac_nslot = n;
           return newchunk;
   }
   
   void
   amap_chunk_free(struct vm_amap *amap, struct vm_amap_chunk *chunk)
   {
           int bucket = UVM_AMAP_BUCKET(amap, chunk->ac_baseslot);
           struct vm_amap_chunk *nchunk;
   
           if (UVM_AMAP_SMALL(amap))
                   return;
   
           nchunk = TAILQ_NEXT(chunk, ac_list);
           TAILQ_REMOVE(&amap->am_chunks, chunk, ac_list);
           if (amap->am_buckets[bucket] == chunk) {
                   if (nchunk != NULL &&
                       UVM_AMAP_BUCKET(amap, nchunk->ac_baseslot) == bucket)
                           amap->am_buckets[bucket] = nchunk;
                   else
                           amap->am_buckets[bucket] = NULL;
   
           }
           pool_put(&uvm_amap_chunk_pool, chunk);
           amap->am_ncused--;
   }
   
   #ifdef UVM_AMAP_PPREF
   /*
    * what is ppref?   ppref is an _optional_ amap feature which is used
    * to keep track of reference counts on a per-page basis.  it is enabled
    * when UVM_AMAP_PPREF is defined.
    *
    * when enabled, an array of ints is allocated for the pprefs.  this
    * array is allocated only when a partial reference is added to the
    * map (either by unmapping part of the amap, or gaining a reference
    * to only a part of an amap).  if the allocation of the array fails
    * (M_NOWAIT), then we set the array pointer to PPREF_NONE to indicate
    * that we tried to do ppref's but couldn't alloc the array so just
    * give up (after all, this is an optional feature!).
    *
    * the array is divided into page sized "chunks."   for chunks of length 1,
    * the chunk reference count plus one is stored in that chunk's slot.
    * for chunks of length > 1 the first slot contains (the reference count
    * plus one) * -1.    [the negative value indicates that the length is
    * greater than one.]   the second slot of the chunk contains the length
    * of the chunk.   here is an example:
    *
    * actual REFS:  2  2  2  2  3  1  1  0  0  0  4  4  0  1  1  1
    *       ppref: -3  4  x  x  4 -2  2 -1  3  x -5  2  1 -2  3  x
    *              <----------><-><----><-------><----><-><------->
    * (x = don't care)
    *
    * this allows us to allow one int to contain the ref count for the whole
    * chunk.    note that the "plus one" part is needed because a reference
    * count of zero is neither positive or negative (need a way to tell
    * if we've got one zero or a bunch of them).
    *
    * here are some in-line functions to help us.
    */
   
   /*
    * pp_getreflen: get the reference and length for a specific offset
    *
    * => ppref's amap must be locked
    */
   static inline void
   pp_getreflen(int *ppref, int offset, int *refp, int *lenp)
   {
   
           if (ppref[offset] > 0) {                /* chunk size must be 1 */
                   *refp = ppref[offset] - 1;      /* don't forget to adjust */
                   *lenp = 1;
           } else {
                   *refp = (ppref[offset] * -1) - 1;
                   *lenp = ppref[offset+1];
           }
   }
   
   /*
    * pp_setreflen: set the reference and length for a specific offset
    *
    * => ppref's amap must be locked
    */
   static inline void
   pp_setreflen(int *ppref, int offset, int ref, int len)
   {
           if (len == 1) {
                   ppref[offset] = ref + 1;
           } else {
                   ppref[offset] = (ref + 1) * -1;
                   ppref[offset+1] = len;
           }
   }
   #endif /* UVM_AMAP_PPREF */
   
   /*
    * amap_init: called at boot time to init global amap data structures
    */
   
   void
   amap_init(void)
   {
           int i;
           size_t size;
   
           /* Initialize the vm_amap pool. */
           pool_init(&uvm_amap_pool, sizeof(struct vm_amap),
               0, IPL_MPFLOOR, PR_WAITOK, "amappl", NULL);
           pool_sethiwat(&uvm_amap_pool, 4096);
   
           /* initialize small amap pools */
           for (i = 0; i < nitems(uvm_small_amap_pool); i++) {
                   snprintf(amap_small_pool_names[i],
                       sizeof(amap_small_pool_names[0]), "amappl%d", i + 1);
                   size = offsetof(struct vm_amap, am_small.ac_anon) +
                       (i + 1) * sizeof(struct vm_anon *);
                   pool_init(&uvm_small_amap_pool[i], size, 0, IPL_MPFLOOR,
                       PR_WAITOK, amap_small_pool_names[i], NULL);
           }
   
           pool_init(&uvm_amap_chunk_pool, sizeof(struct vm_amap_chunk) +
               UVM_AMAP_CHUNK * sizeof(struct vm_anon *),
               0, IPL_MPFLOOR, PR_WAITOK, "amapchunkpl", NULL);
           pool_sethiwat(&uvm_amap_chunk_pool, 4096);
   }
   
   /*
    * amap_alloc1: allocate an amap, but do not initialise the overlay.
    *
    * => Note: lock is not set.
    */
   static inline struct vm_amap *
   amap_alloc1(int slots, int waitf, int lazyalloc)
   {
           struct vm_amap *amap;
           struct vm_amap_chunk *chunk, *tmp;
           int chunks, log_chunks, chunkperbucket = 1, hashshift = 0;
           int buckets, i, n;
           int pwaitf = (waitf & M_WAITOK) ? PR_WAITOK : PR_NOWAIT;
   
           KASSERT(slots > 0);
   
           /*
            * Cast to unsigned so that rounding up cannot cause integer overflow
            * if slots is large.
            */
           chunks = roundup((unsigned int)slots, UVM_AMAP_CHUNK) / UVM_AMAP_CHUNK;
   
           if (lazyalloc) {
                   /*
                    * Basically, the amap is a hash map where the number of
                    * buckets is fixed. We select the number of buckets using the
                    * following strategy:
                    *
                    * 1. The maximal number of entries to search in a bucket upon
                    * a collision should be less than or equal to
                    * log2(slots / UVM_AMAP_CHUNK). This is the worst-case number
                    * of lookups we would have if we could chunk the amap. The
                    * log2(n) comes from the fact that amaps are chunked by
                    * splitting up their vm_map_entries and organizing those
                    * in a binary search tree.
                    *
                    * 2. The maximal number of entries in a bucket must be a
                    * power of two.
                    *
                    * The maximal number of entries per bucket is used to hash
                    * a slot to a bucket.
                    *
                    * In the future, this strategy could be refined to make it
                    * even harder/impossible that the total amount of KVA needed
                    * for the hash buckets of all amaps to exceed the maximal
                    * amount of KVA memory reserved for amaps.
                    */
                   for (log_chunks = 1; (chunks >> log_chunks) > 0; log_chunks++)
                           continue;
   
                   chunkperbucket = 1 << hashshift;
                   while (chunkperbucket + 1 < log_chunks) {
                           hashshift++;
                           chunkperbucket = 1 << hashshift;
                   }
           }
   
           if (slots > UVM_AMAP_CHUNK)
                   amap = pool_get(&uvm_amap_pool, pwaitf);
           else
                   amap = pool_get(&uvm_small_amap_pool[slots - 1],
                       pwaitf | PR_ZERO);
           if (amap == NULL)
                   return NULL;
   
           amap->am_lock = NULL;
           amap->am_ref = 1;
           amap->am_flags = 0;
   #ifdef UVM_AMAP_PPREF
           amap->am_ppref = NULL;
   #endif
           amap->am_nslot = slots;
           amap->am_nused = 0;
   
           if (UVM_AMAP_SMALL(amap)) {
                   amap->am_small.ac_nslot = slots;
                   return amap;
           }
   
           amap->am_ncused = 0;
           TAILQ_INIT(&amap->am_chunks);
           amap->am_hashshift = hashshift;
           amap->am_buckets = NULL;
   
           buckets = howmany(chunks, chunkperbucket);
           amap->am_buckets = mallocarray(buckets, sizeof(*amap->am_buckets),
               M_UVMAMAP, waitf | (lazyalloc ? M_ZERO : 0));
           if (amap->am_buckets == NULL)
                   goto fail1;
           amap->am_nbuckets = buckets;
   
           if (!lazyalloc) {
                   for (i = 0; i < buckets; i++) {
                           if (i == buckets - 1) {
                                   n = slots % UVM_AMAP_CHUNK;
                                   if (n == 0)
                                           n = UVM_AMAP_CHUNK;
                           } else
                                   n = UVM_AMAP_CHUNK;
   
                           chunk = pool_get(&uvm_amap_chunk_pool,
                               PR_ZERO | pwaitf);
                           if (chunk == NULL)
                                   goto fail1;
   
                           amap->am_buckets[i] = chunk;
                           amap->am_ncused++;
                           chunk->ac_baseslot = i * UVM_AMAP_CHUNK;
                           chunk->ac_nslot = n;
                           TAILQ_INSERT_TAIL(&amap->am_chunks, chunk, ac_list);
                   }
           }
   
           return amap;
   
   fail1:
           free(amap->am_buckets, M_UVMAMAP, buckets * sizeof(*amap->am_buckets));
           TAILQ_FOREACH_SAFE(chunk, &amap->am_chunks, ac_list, tmp)
                   pool_put(&uvm_amap_chunk_pool, chunk);
           pool_put(&uvm_amap_pool, amap);
           return NULL;
   }
   
   static void
   amap_lock_alloc(struct vm_amap *amap)
   {
           rw_obj_alloc(&amap->am_lock, "amaplk");
   }
   
   /*
    * amap_alloc: allocate an amap to manage "sz" bytes of anonymous VM
    *
    * => caller should ensure sz is a multiple of PAGE_SIZE
    * => reference count to new amap is set to one
    * => new amap is returned unlocked
    */
   struct vm_amap *
   amap_alloc(vaddr_t sz, int waitf, int lazyalloc)
   {
           struct vm_amap *amap;
           size_t slots;
   
           AMAP_B2SLOT(slots, sz);         /* load slots */
           if (slots > INT_MAX)
                   return NULL;
   
           amap = amap_alloc1(slots, waitf, lazyalloc);
           if (amap != NULL) {
                   amap_lock_alloc(amap);
                   amap_list_insert(amap);
           }
   
           return amap;
   }
   
   
   /*
    * amap_free: free an amap
    *
    * => the amap must be unlocked
    * => the amap should have a zero reference count and be empty
    */
   void
   amap_free(struct vm_amap *amap)
   {
           struct vm_amap_chunk *chunk, *tmp;
   
           KASSERT(amap->am_ref == 0 && amap->am_nused == 0);
           KASSERT((amap->am_flags & AMAP_SWAPOFF) == 0);
   
           if (amap->am_lock != NULL) {
                   KASSERT(amap->am_lock == NULL || !rw_write_held(amap->am_lock));
                   rw_obj_free(amap->am_lock);
           }
   
   #ifdef UVM_AMAP_PPREF
           if (amap->am_ppref && amap->am_ppref != PPREF_NONE)
                   free(amap->am_ppref, M_UVMAMAP, amap->am_nslot * sizeof(int));
   #endif
   
           if (UVM_AMAP_SMALL(amap))
                   pool_put(&uvm_small_amap_pool[amap->am_nslot - 1], amap);
           else {
                   TAILQ_FOREACH_SAFE(chunk, &amap->am_chunks, ac_list, tmp)
                       pool_put(&uvm_amap_chunk_pool, chunk);
                   free(amap->am_buckets, M_UVMAMAP,
                       amap->am_nbuckets * sizeof(*amap->am_buckets));
                   pool_put(&uvm_amap_pool, amap);
           }
   }
   
   /*
    * amap_wipeout: wipeout all anon's in an amap; then free the amap!
    *
    * => Called from amap_unref(), when reference count drops to zero.
    * => amap must be locked.
    */
   void
   amap_wipeout(struct vm_amap *amap)
   {
           int slot;
           struct vm_anon *anon;
           struct vm_amap_chunk *chunk;
           struct pglist pgl;
   
           KASSERT(rw_write_held(amap->am_lock));
           KASSERT(amap->am_ref == 0);
   
           if (__predict_false((amap->am_flags & AMAP_SWAPOFF) != 0)) {
                   /*
                    * Note: amap_swap_off() will call us again.
                    */
                   amap_unlock(amap);
                   return;
           }
   
           TAILQ_INIT(&pgl);
           amap_list_remove(amap);
   
           AMAP_CHUNK_FOREACH(chunk, amap) {
                   int i, refs, map = chunk->ac_usedmap;
   
                   for (i = ffs(map); i != 0; i = ffs(map)) {
                           slot = i - 1;
                           map ^= 1 << slot;
                           anon = chunk->ac_anon[slot];
   
                           if (anon == NULL || anon->an_ref == 0)
                                   panic("amap_wipeout: corrupt amap");
                           KASSERT(anon->an_lock == amap->am_lock);
   
                           /*
                            * Drop the reference.
                            */
                           refs = --anon->an_ref;
                           if (refs == 0) {
                                   uvm_anfree_list(anon, &pgl);
                           }
                   }
           }
           /* free the pages */
           uvm_pglistfree(&pgl);
   
           /*
            * Finally, destroy the amap.
            */
           amap->am_ref = 0;       /* ... was one */
           amap->am_nused = 0;
           amap_unlock(amap);
           amap_free(amap);
   }
   
   /*
    * amap_copy: ensure that a map entry's "needs_copy" flag is false
    *      by copying the amap if necessary.
    *
    * => an entry with a null amap pointer will get a new (blank) one.
    * => the map that the map entry belongs to must be locked by caller.
    * => the amap currently attached to "entry" (if any) must be unlocked.
    * => if canchunk is true, then we may clip the entry into a chunk
    * => "startva" and "endva" are used only if canchunk is true.  they are
    *     used to limit chunking (e.g. if you have a large space that you
    *     know you are going to need to allocate amaps for, there is no point
    *     in allowing that to be chunked)
    */
   
   void
   amap_copy(struct vm_map *map, struct vm_map_entry *entry, int waitf,
       boolean_t canchunk, vaddr_t startva, vaddr_t endva)
   {
           struct vm_amap *amap, *srcamap;
           int slots, lcv, lazyalloc = 0;
           vaddr_t chunksize;
           int i, j, k, n, srcslot;
           struct vm_amap_chunk *chunk = NULL, *srcchunk = NULL;
           struct vm_anon *anon;
   
           KASSERT(map != kernel_map);             /* we use sleeping locks */
   
           /*
            * Is there an amap to copy?  If not, create one.
            */
           if (entry->aref.ar_amap == NULL) {
                   /*
                    * Check to see if we have a large amap that we can
                    * chunk.  We align startva/endva to chunk-sized
                    * boundaries and then clip to them.
                    *
                    * If we cannot chunk the amap, allocate it in a way
                    * that makes it grow or shrink dynamically with
                    * the number of slots.
                    */
                   if (atop(entry->end - entry->start) >= UVM_AMAP_LARGE) {
                           if (canchunk) {
                                   /* convert slots to bytes */
                                   chunksize = UVM_AMAP_CHUNK << PAGE_SHIFT;
                                   startva = (startva / chunksize) * chunksize;
                                   endva = roundup(endva, chunksize);
                                   UVM_MAP_CLIP_START(map, entry, startva);
                                   /* watch out for endva wrap-around! */
                                   if (endva >= startva)
                                           UVM_MAP_CLIP_END(map, entry, endva);
                           } else
                                   lazyalloc = 1;
                   }
   
                   entry->aref.ar_pageoff = 0;
                   entry->aref.ar_amap = amap_alloc(entry->end - entry->start,
                       waitf, lazyalloc);
                   if (entry->aref.ar_amap != NULL)
                           entry->etype &= ~UVM_ET_NEEDSCOPY;
                   return;
           }
   
           /*
            * First check and see if we are the only map entry referencing
            * he amap we currently have.  If so, then just take it over instead
            * of copying it.  Note that we are reading am_ref without lock held
            * as the value value can only be one if we have the only reference
            * to the amap (via our locked map).  If the value is greater than
            * one, then allocate amap and re-check the value.
            */
           if (entry->aref.ar_amap->am_ref == 1) {
                   entry->etype &= ~UVM_ET_NEEDSCOPY;
                   return;
           }
   
           /*
            * Allocate a new amap (note: not initialised, etc).
            */
           AMAP_B2SLOT(slots, entry->end - entry->start);
           if (!UVM_AMAP_SMALL(entry->aref.ar_amap) &&
               entry->aref.ar_amap->am_hashshift != 0)
                   lazyalloc = 1;
           amap = amap_alloc1(slots, waitf, lazyalloc);
           if (amap == NULL)
                   return;
           srcamap = entry->aref.ar_amap;
   
           /*
            * Make the new amap share the source amap's lock, and then lock
            * both.
            */
           amap->am_lock = srcamap->am_lock;
           rw_obj_hold(amap->am_lock);
   
           amap_lock(srcamap);
   
           /*
            * Re-check the reference count with the lock held.  If it has
            * dropped to one - we can take over the existing map.
            */
           if (srcamap->am_ref == 1) {
                   /* Just take over the existing amap. */
                   entry->etype &= ~UVM_ET_NEEDSCOPY;
                   amap_unlock(srcamap);
                   /* Destroy the new (unused) amap. */
                   amap->am_ref--;
                   amap_free(amap);
                   return;
           }
   
           /*
            * Copy the slots.
            */
           for (lcv = 0; lcv < slots; lcv += n) {
                   srcslot = entry->aref.ar_pageoff + lcv;
                   i = UVM_AMAP_SLOTIDX(lcv);
                   j = UVM_AMAP_SLOTIDX(srcslot);
                   n = UVM_AMAP_CHUNK;
                   if (i > j)
                           n -= i;
                   else
                           n -= j;
                   if (lcv + n > slots)
                           n = slots - lcv;
   
                   srcchunk = amap_chunk_get(srcamap, srcslot, 0, PR_NOWAIT);
                   if (srcchunk == NULL)
                           continue;
   
                   chunk = amap_chunk_get(amap, lcv, 1, PR_NOWAIT);
                   if (chunk == NULL) {
                           /* amap_wipeout() releases the lock. */
                           amap->am_ref = 0;
                           amap_wipeout(amap);
                           return;
                   }
   
                   for (k = 0; k < n; i++, j++, k++) {
                           chunk->ac_anon[i] = anon = srcchunk->ac_anon[j];
                           if (anon == NULL)
                                   continue;
   
                           KASSERT(anon->an_lock == srcamap->am_lock);
                           KASSERT(anon->an_ref > 0);
                           chunk->ac_usedmap |= (1 << i);
                           anon->an_ref++;
                           amap->am_nused++;
                   }
           }
   
           /*
            * Drop our reference to the old amap (srcamap) and unlock.
            * Since the reference count on srcamap is greater than one,
            * (we checked above), it cannot drop to zero while it is locked.
            */
           srcamap->am_ref--;
           KASSERT(srcamap->am_ref > 0);
   
           if (srcamap->am_ref == 1 && (srcamap->am_flags & AMAP_SHARED) != 0)
                   srcamap->am_flags &= ~AMAP_SHARED;   /* clear shared flag */
   #ifdef UVM_AMAP_PPREF
           if (srcamap->am_ppref && srcamap->am_ppref != PPREF_NONE) {
                   amap_pp_adjref(srcamap, entry->aref.ar_pageoff, 
                       (entry->end - entry->start) >> PAGE_SHIFT, -1);
           }
   #endif
   
           /*
            * If we referenced any anons, then share the source amap's lock.
            * Otherwise, we have nothing in common, so allocate a new one.
            */
           KASSERT(amap->am_lock == srcamap->am_lock);
           if (amap->am_nused == 0) {
                   rw_obj_free(amap->am_lock);
                   amap->am_lock = NULL;
           }
           amap_unlock(srcamap);
   
           if (amap->am_lock == NULL)
                   amap_lock_alloc(amap);
   
           /*
            * Install new amap.
            */
           entry->aref.ar_pageoff = 0;
           entry->aref.ar_amap = amap;
           entry->etype &= ~UVM_ET_NEEDSCOPY;
   
           amap_list_insert(amap);
   }
   
   /*
    * amap_cow_now: resolve all copy-on-write faults in an amap now for fork(2)
    *
    *      called during fork(2) when the parent process has a wired map
    *      entry.   in that case we want to avoid write-protecting pages
    *      in the parent's map (e.g. like what you'd do for a COW page)
    *      so we resolve the COW here.
    *
    * => assume parent's entry was wired, thus all pages are resident.
    * => the parent and child vm_map must both be locked.
    * => caller passes child's map/entry in to us
    * => XXXCDC: out of memory should cause fork to fail, but there is
    *      currently no easy way to do this (needs fix)
    */
   
   void
   amap_cow_now(struct vm_map *map, struct vm_map_entry *entry)
   {
           struct vm_amap *amap = entry->aref.ar_amap;
           int slot;
           struct vm_anon *anon, *nanon;
           struct vm_page *pg, *npg;
           struct vm_amap_chunk *chunk;
   
           /*
            * note that if we unlock the amap then we must ReStart the "lcv" for
            * loop because some other process could reorder the anon's in the
            * am_anon[] array on us while the lock is dropped.
            */
   ReStart:
           amap_lock(amap);
           AMAP_CHUNK_FOREACH(chunk, amap) {
                   int i, map = chunk->ac_usedmap;
   
                   for (i = ffs(map); i != 0; i = ffs(map)) {
                           slot = i - 1;
                           map ^= 1 << slot;
                           anon = chunk->ac_anon[slot];
                           pg = anon->an_page;
                           KASSERT(anon->an_lock == amap->am_lock);
   
                           /*
                            * The old page must be resident since the parent is
                            * wired.
                            */
                           KASSERT(pg != NULL);
   
                           /*
                            * if the anon ref count is one, we are safe (the child
                            * has exclusive access to the page).
                            */
                           if (anon->an_ref <= 1)
                                   continue;
   
                           /*
                            * If the page is busy, then we have to unlock, wait for
                            * it and then restart.
                            */
                           if (pg->pg_flags & PG_BUSY) {
                                   uvm_pagewait(pg, amap->am_lock, "cownow");
                                   goto ReStart;
                           }
   
                           /*
                            * Perform a copy-on-write.
                            * First - get a new anon and a page.
                            */
                           nanon = uvm_analloc();
                           if (nanon != NULL) {
                                   /* the new anon will share the amap's lock */
                                   nanon->an_lock = amap->am_lock;
                                   npg = uvm_pagealloc(NULL, 0, nanon, 0);
                           } else
                                   npg = NULL;     /* XXX: quiet gcc warning */
   
                           if (nanon == NULL || npg == NULL) {
                                   /* out of memory */
                                   amap_unlock(amap);
                                   if (nanon != NULL) {
                                           nanon->an_lock = NULL;
                                           nanon->an_ref--;
                                           KASSERT(nanon->an_ref == 0);
                                           uvm_anfree(nanon);
                                   }
                                   uvm_wait("cownowpage");
                                   goto ReStart;
                           }
   
                           /*
                            * Copy the data and replace anon with the new one.
                            * Also, setup its lock (share the with amap's lock).
                            */
                           uvm_pagecopy(pg, npg);
                           anon->an_ref--;
                           KASSERT(anon->an_ref > 0);
                           chunk->ac_anon[slot] = nanon;
   
                           /*
                            * Drop PG_BUSY on new page.  Since its owner was write
                            * locked all this time - it cannot be PG_RELEASED or
                            * PG_WANTED.
                            */
                           atomic_clearbits_int(&npg->pg_flags, PG_BUSY|PG_FAKE);
                           UVM_PAGE_OWN(npg, NULL);
                           uvm_lock_pageq();
                           uvm_pageactivate(npg);
                           uvm_unlock_pageq();
                   }
           }
           amap_unlock(amap);
   }
   
   /*
    * amap_splitref: split a single reference into two separate references
    *
    * => called from uvm_map's clip routines
    * => origref's map should be locked
    * => origref->ar_amap should be unlocked (we will lock)
    */
   void
   amap_splitref(struct vm_aref *origref, struct vm_aref *splitref, vaddr_t offset)
   {
           struct vm_amap *amap = origref->ar_amap;
           int leftslots;
   
           KASSERT(splitref->ar_amap == amap);
           AMAP_B2SLOT(leftslots, offset);
           if (leftslots == 0)
                   panic("amap_splitref: split at zero offset");
   
           amap_lock(amap);
   
           if (amap->am_nslot - origref->ar_pageoff - leftslots <= 0)
                   panic("amap_splitref: map size check failed");
   
   #ifdef UVM_AMAP_PPREF
           /* Establish ppref before we add a duplicate reference to the amap. */
           if (amap->am_ppref == NULL)
                   amap_pp_establish(amap);
   #endif
   
           /* Note: not a share reference. */
           amap->am_ref++;
           splitref->ar_amap = amap;
           splitref->ar_pageoff = origref->ar_pageoff + leftslots;
           amap_unlock(amap);
   }
   
   #ifdef UVM_AMAP_PPREF
   
   /*
    * amap_pp_establish: add a ppref array to an amap, if possible.
    *
    * => amap should be locked by caller* => amap should be locked by caller
    */
   void
   amap_pp_establish(struct vm_amap *amap)
   {
   
           KASSERT(rw_write_held(amap->am_lock));
           amap->am_ppref = mallocarray(amap->am_nslot, sizeof(int),
               M_UVMAMAP, M_NOWAIT|M_ZERO);
   
           if (amap->am_ppref == NULL) {
                   /* Failure - just do not use ppref. */
                   amap->am_ppref = PPREF_NONE;
                   return;
           }
   
           pp_setreflen(amap->am_ppref, 0, amap->am_ref, amap->am_nslot);
   }
   
   /*
    * amap_pp_adjref: adjust reference count to a part of an amap using the
    * per-page reference count array.
    *
    * => caller must check that ppref != PPREF_NONE before calling.
    * => map and amap must be locked.
    */
   void
   amap_pp_adjref(struct vm_amap *amap, int curslot, vsize_t slotlen, int adjval)
   {
           int stopslot, *ppref, lcv, prevlcv;
           int ref, len, prevref, prevlen;
   
           KASSERT(rw_write_held(amap->am_lock));
   
           stopslot = curslot + slotlen;
           ppref = amap->am_ppref;
           prevlcv = 0;
   
           /*
            * Advance to the correct place in the array, fragment if needed.
            */
           for (lcv = 0 ; lcv < curslot ; lcv += len) {
                   pp_getreflen(ppref, lcv, &ref, &len);
                   if (lcv + len > curslot) {     /* goes past start? */
                           pp_setreflen(ppref, lcv, ref, curslot - lcv);
                           pp_setreflen(ppref, curslot, ref, len - (curslot -lcv));
                           len = curslot - lcv;   /* new length of entry @ lcv */
                   }
                   prevlcv = lcv;
           }
           if (lcv != 0)
                   pp_getreflen(ppref, prevlcv, &prevref, &prevlen);
           else {
                   /*
                    * Ensure that the "prevref == ref" test below always
                    * fails, since we are starting from the beginning of
                    * the ppref array; that is, there is no previous chunk.
                    */
                   prevref = -1;
                   prevlen = 0;
           }
   
           /*
            * Now adjust reference counts in range.  Merge the first
            * changed entry with the last unchanged entry if possible.
            */
           if (lcv != curslot)
                   panic("amap_pp_adjref: overshot target");
   
           for (/* lcv already set */; lcv < stopslot ; lcv += len) {
                   pp_getreflen(ppref, lcv, &ref, &len);
                   if (lcv + len > stopslot) {     /* goes past end? */
                           pp_setreflen(ppref, lcv, ref, stopslot - lcv);
                           pp_setreflen(ppref, stopslot, ref,
                               len - (stopslot - lcv));
                           len = stopslot - lcv;
                   }
                   ref += adjval;
                   if (ref < 0)
                           panic("amap_pp_adjref: negative reference count");
                   if (lcv == prevlcv + prevlen && ref == prevref) {
                           pp_setreflen(ppref, prevlcv, ref, prevlen + len);
                   } else {
                           pp_setreflen(ppref, lcv, ref, len);
                   }
                   if (ref == 0)
                           amap_wiperange(amap, lcv, len);
           }
   
   }
   
   void
   amap_wiperange_chunk(struct vm_amap *amap, struct vm_amap_chunk *chunk,
       int slotoff, int slots)
   {
           int curslot, i, map;
           int startbase, endbase;
           struct vm_anon *anon;
   
           startbase = AMAP_BASE_SLOT(slotoff);
           endbase = AMAP_BASE_SLOT(slotoff + slots - 1);
   
           map = chunk->ac_usedmap;
           if (startbase == chunk->ac_baseslot)
                   map &= ~((1 << (slotoff - startbase)) - 1);
           if (endbase == chunk->ac_baseslot)
                   map &= (1 << (slotoff + slots - endbase)) - 1;
   
           for (i = ffs(map); i != 0; i = ffs(map)) {
                   int refs;
   
                   curslot = i - 1;
                   map ^= 1 << curslot;
                   chunk->ac_usedmap ^= 1 << curslot;
                   anon = chunk->ac_anon[curslot];
                   KASSERT(anon->an_lock == amap->am_lock);
   
                   /* remove it from the amap */
                   chunk->ac_anon[curslot] = NULL;
   
                   amap->am_nused--;
   
                  /* drop anon reference count */
                  refs = --anon->an_ref;
                  if (refs == 0) {
                          uvm_anfree(anon);
                  }
  
                  /*
                   * done with this anon, next ...!
                   */
  
          }       /* end of 'for' loop */
  }
  
  /*
   * amap_wiperange: wipe out a range of an amap.
   * Note: different from amap_wipeout because the amap is kept intact.
   *
   * => Both map and amap must be locked by caller.
   */
  void
  amap_wiperange(struct vm_amap *amap, int slotoff, int slots)
  {
          int bucket, startbucket, endbucket;
          struct vm_amap_chunk *chunk, *nchunk;
  
          KASSERT(rw_write_held(amap->am_lock));
  
          startbucket = UVM_AMAP_BUCKET(amap, slotoff);
          endbucket = UVM_AMAP_BUCKET(amap, slotoff + slots - 1);
  
          /*
           * We can either traverse the amap by am_chunks or by am_buckets.
           * Determine which way is less expensive.
           */
          if (UVM_AMAP_SMALL(amap))
                  amap_wiperange_chunk(amap, &amap->am_small, slotoff, slots);
          else if (endbucket + 1 - startbucket >= amap->am_ncused) {
                  TAILQ_FOREACH_SAFE(chunk, &amap->am_chunks, ac_list, nchunk) {
                          if (chunk->ac_baseslot + chunk->ac_nslot <= slotoff)
                                  continue;
                          if (chunk->ac_baseslot >= slotoff + slots)
                                  continue;
  
                          amap_wiperange_chunk(amap, chunk, slotoff, slots);
                          if (chunk->ac_usedmap == 0)
                                  amap_chunk_free(amap, chunk);
                  }
          } else {
                  for (bucket = startbucket; bucket <= endbucket; bucket++) {
                          for (chunk = amap->am_buckets[bucket]; chunk != NULL;
                              chunk = nchunk) {
                                  nchunk = TAILQ_NEXT(chunk, ac_list);
  
                                  if (UVM_AMAP_BUCKET(amap, chunk->ac_baseslot) !=
                                      bucket)
                                          break;
                                  if (chunk->ac_baseslot + chunk->ac_nslot <=
                                      slotoff)
                                          continue;
                                  if (chunk->ac_baseslot >= slotoff + slots)
                                          continue;
  
                                  amap_wiperange_chunk(amap, chunk, slotoff,
                                      slots);
                                  if (chunk->ac_usedmap == 0)
                                          amap_chunk_free(amap, chunk);
                          }
                  }
          }
  }
  
  #endif
  
  /*
   * amap_swap_off: pagein anonymous pages in amaps and drop swap slots.
   *
   * => note that we don't always traverse all anons.
   *    eg. amaps being wiped out, released anons.
   * => return TRUE if failed.
   */
  
  boolean_t
  amap_swap_off(int startslot, int endslot)
  {
          struct vm_amap *am;
          struct vm_amap *am_next;
          struct vm_amap marker;
          boolean_t rv = FALSE;
  
          amap_lock_list();
          for (am = LIST_FIRST(&amap_list); am != NULL && !rv; am = am_next) {
                  int i, map;
                  struct vm_amap_chunk *chunk;
  
                  amap_lock(am);
                  if (am->am_nused == 0) {
                          amap_unlock(am);
                          am_next = LIST_NEXT(am, am_list);
                          continue;
                  }
  
                  LIST_INSERT_AFTER(am, &marker, am_list);
                  amap_unlock_list();
  
  again:
                  AMAP_CHUNK_FOREACH(chunk, am) {
                          map = chunk->ac_usedmap;
  
                          for (i = ffs(map); i != 0; i = ffs(map)) {
                                  int swslot;
                                  int slot = i - 1;
                                  struct vm_anon *anon;
  
                                  map ^= 1 << slot;
                                  anon = chunk->ac_anon[slot];
  
                                  swslot = anon->an_swslot;
                                  if (swslot < startslot || endslot <= swslot) {
                                          continue;
                                  }
  
                                  am->am_flags |= AMAP_SWAPOFF;
  
                                  rv = uvm_anon_pagein(am, anon);
                                  amap_lock(am);
  
                                  am->am_flags &= ~AMAP_SWAPOFF;
                                  if (amap_refs(am) == 0) {
                                          amap_wipeout(am);
                                          am = NULL;
                                          goto nextamap;
                                  }
                                  if (rv)
                                          goto nextamap;
                                  goto again;
                          }
                  }
  nextamap:
                  if (am != NULL)
                          amap_unlock(am);
                  amap_lock_list();
                  am_next = LIST_NEXT(&marker, am_list);
                  LIST_REMOVE(&marker, am_list);
          }
          amap_unlock_list();
  
          return rv;
  }
  
  /*
   * amap_lookup: look up a page in an amap.
   *
   * => amap should be locked by caller.
   */
  struct vm_anon *
  amap_lookup(struct vm_aref *aref, vaddr_t offset)
  {
          int slot;
          struct vm_amap *amap = aref->ar_amap;
          struct vm_amap_chunk *chunk;
  
          AMAP_B2SLOT(slot, offset);
          slot += aref->ar_pageoff;
          KASSERT(slot < amap->am_nslot);
  
          chunk = amap_chunk_get(amap, slot, 0, PR_NOWAIT);
          if (chunk == NULL)
                  return NULL;
  
          return chunk->ac_anon[UVM_AMAP_SLOTIDX(slot)];
  }
  
  /*
   * amap_lookups: look up a range of pages in an amap.
   *
   * => amap should be locked by caller.
   * => XXXCDC: this interface is biased toward array-based amaps.  fix.
   */
  void
  amap_lookups(struct vm_aref *aref, vaddr_t offset,
      struct vm_anon **anons, int npages)
  {
          int i, lcv, n, slot;
          struct vm_amap *amap = aref->ar_amap;
          struct vm_amap_chunk *chunk = NULL;
  
          AMAP_B2SLOT(slot, offset);
          slot += aref->ar_pageoff;
  
          KASSERT((slot + (npages - 1)) < amap->am_nslot);
  
          for (i = 0, lcv = slot; lcv < slot + npages; i += n, lcv += n) {
                  n = UVM_AMAP_CHUNK - UVM_AMAP_SLOTIDX(lcv);
                  if (lcv + n > slot + npages)
                          n = slot + npages - lcv;
  
                  chunk = amap_chunk_get(amap, lcv, 0, PR_NOWAIT);
                  if (chunk == NULL)
                          memset(&anons[i], 0, n * sizeof(*anons));
                  else
                          memcpy(&anons[i],
                              &chunk->ac_anon[UVM_AMAP_SLOTIDX(lcv)],
                              n * sizeof(*anons));
          }
  }
  
  /*
   * amap_populate: ensure that the amap can store an anon for the page at
   * offset. This function can sleep until memory to store the anon is
   * available.
   */
  void
  amap_populate(struct vm_aref *aref, vaddr_t offset)
  {
          int slot;
          struct vm_amap *amap = aref->ar_amap;
          struct vm_amap_chunk *chunk;
  
          AMAP_B2SLOT(slot, offset);
          slot += aref->ar_pageoff;
          KASSERT(slot < amap->am_nslot);
  
          chunk = amap_chunk_get(amap, slot, 1, PR_WAITOK);
          KASSERT(chunk != NULL);
  }
  
  /*
   * amap_add: add (or replace) a page to an amap.
   *
   * => amap should be locked by caller.
   * => anon must have the lock associated with this amap.
   */
  int
  amap_add(struct vm_aref *aref, vaddr_t offset, struct vm_anon *anon,
      boolean_t replace)
  {
          int slot;
          struct vm_amap *amap = aref->ar_amap;
          struct vm_amap_chunk *chunk;
  
          AMAP_B2SLOT(slot, offset);
          slot += aref->ar_pageoff;
          KASSERT(slot < amap->am_nslot);
  
          chunk = amap_chunk_get(amap, slot, 1, PR_NOWAIT);
          if (chunk == NULL)
                  return 1;
  
          slot = UVM_AMAP_SLOTIDX(slot);
          if (replace) {
                  struct vm_anon *oanon  = chunk->ac_anon[slot];
  
                  KASSERT(oanon != NULL);
                  if (oanon->an_page && (amap->am_flags & AMAP_SHARED) != 0) {
                          pmap_page_protect(oanon->an_page, PROT_NONE);
                          /*
                           * XXX: suppose page is supposed to be wired somewhere?
                           */
                  }
          } else {   /* !replace */
                  if (chunk->ac_anon[slot] != NULL)
                          panic("amap_add: slot in use");
  
                  chunk->ac_usedmap |= 1 << slot;
                  amap->am_nused++;
          }
          chunk->ac_anon[slot] = anon;
  
          return 0;
  }
  
  /*
   * amap_unadd: remove a page from an amap.
   *
   * => amap should be locked by caller.
   */
  void
  amap_unadd(struct vm_aref *aref, vaddr_t offset)
  {
          struct vm_amap *amap = aref->ar_amap;
          struct vm_amap_chunk *chunk;
          int slot;
  
          KASSERT(rw_write_held(amap->am_lock));
  
          AMAP_B2SLOT(slot, offset);
          slot += aref->ar_pageoff;
          KASSERT(slot < amap->am_nslot);
          chunk = amap_chunk_get(amap, slot, 0, PR_NOWAIT);
          KASSERT(chunk != NULL);
  
          slot = UVM_AMAP_SLOTIDX(slot);
          KASSERT(chunk->ac_anon[slot] != NULL);
  
          chunk->ac_anon[slot] = NULL;
          chunk->ac_usedmap &= ~(1 << slot);
          amap->am_nused--;
  
          if (chunk->ac_usedmap == 0)
                  amap_chunk_free(amap, chunk);
  }
  
  /*
   * amap_adjref_anons: adjust the reference count(s) on amap and its anons.
   */
  static void
  amap_adjref_anons(struct vm_amap *amap, vaddr_t offset, vsize_t len,
      int refv, boolean_t all)
  {
  #ifdef UVM_AMAP_PPREF
          KASSERT(rw_write_held(amap->am_lock));
  
          /*
           * We must establish the ppref array before changing am_ref
           * so that the ppref values match the current amap refcount.
           */
          if (amap->am_ppref == NULL && !all && len != amap->am_nslot) {
                  amap_pp_establish(amap);
          }
  #endif
  
          amap->am_ref += refv;
  
  #ifdef UVM_AMAP_PPREF
          if (amap->am_ppref && amap->am_ppref != PPREF_NONE) {
                  if (all) {
                          amap_pp_adjref(amap, 0, amap->am_nslot, refv);
                  } else {
                          amap_pp_adjref(amap, offset, len, refv);
                  }
          }
  #endif
          amap_unlock(amap);
  }
  
  /*
   * amap_ref: gain a reference to an amap.
   *
   * => amap must not be locked (we will lock).
   * => "offset" and "len" are in units of pages.
   * => Called at fork time to gain the child's reference.
   */
  void
  amap_ref(struct vm_amap *amap, vaddr_t offset, vsize_t len, int flags)
  {
          amap_lock(amap);
          if (flags & AMAP_SHARED)
                  amap->am_flags |= AMAP_SHARED;
          amap_adjref_anons(amap, offset, len, 1, (flags & AMAP_REFALL) != 0);
  }
  
  /*
   * amap_unref: remove a reference to an amap.
   *
   * => All pmap-level references to this amap must be already removed.
   * => Called from uvm_unmap_detach(); entry is already removed from the map.
   * => We will lock amap, so it must be unlocked.
   */
  void
  amap_unref(struct vm_amap *amap, vaddr_t offset, vsize_t len, boolean_t all)
  {
          amap_lock(amap);
  
          KASSERT(amap->am_ref > 0);
  
          if (amap->am_ref == 1) {
                  /*
                   * If the last reference - wipeout and destroy the amap.
                   */
                  amap->am_ref--;
                  amap_wipeout(amap);
                  return;
          }
  
          /*
           * Otherwise, drop the reference count(s) on anons.
           */
          if (amap->am_ref == 2 && (amap->am_flags & AMAP_SHARED) != 0) {
                  amap->am_flags &= ~AMAP_SHARED;
          }
          amap_adjref_anons(amap, offset, len, -1, all);
  }

Cache object: 5fae8415b92f12af57467b30fac74f64