home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / sys / vm / vm_map.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-21  |  57.5 KB  |  2,473 lines
  1. /* 
  2.  * Copyright (c) 1991 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * The Mach Operating System project at Carnegie-Mellon University.
  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 the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  *
  36.  *    @(#)vm_map.c    7.3 (Berkeley) 4/21/91
  37.  *
  38.  *
  39.  * Copyright (c) 1987, 1990 Carnegie-Mellon University.
  40.  * All rights reserved.
  41.  *
  42.  * Authors: Avadis Tevanian, Jr., Michael Wayne Young
  43.  * 
  44.  * Permission to use, copy, modify and distribute this software and
  45.  * its documentation is hereby granted, provided that both the copyright
  46.  * notice and this permission notice appear in all copies of the
  47.  * software, derivative works or modified versions, and any portions
  48.  * thereof, and that both notices appear in supporting documentation.
  49.  * 
  50.  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 
  51.  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 
  52.  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  53.  * 
  54.  * Carnegie Mellon requests users of this software to return to
  55.  *
  56.  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  57.  *  School of Computer Science
  58.  *  Carnegie Mellon University
  59.  *  Pittsburgh PA 15213-3890
  60.  *
  61.  * any improvements or extensions that they make and grant Carnegie the
  62.  * rights to redistribute these changes.
  63.  */
  64.  
  65. /*
  66.  *    Virtual memory mapping module.
  67.  */
  68.  
  69. #include "param.h"
  70. #include "malloc.h"
  71. #include "vm.h"
  72. #include "vm_page.h"
  73. #include "vm_object.h"
  74.  
  75. /*
  76.  *    Virtual memory maps provide for the mapping, protection,
  77.  *    and sharing of virtual memory objects.  In addition,
  78.  *    this module provides for an efficient virtual copy of
  79.  *    memory from one map to another.
  80.  *
  81.  *    Synchronization is required prior to most operations.
  82.  *
  83.  *    Maps consist of an ordered doubly-linked list of simple
  84.  *    entries; a single hint is used to speed up lookups.
  85.  *
  86.  *    In order to properly represent the sharing of virtual
  87.  *    memory regions among maps, the map structure is bi-level.
  88.  *    Top-level ("address") maps refer to regions of sharable
  89.  *    virtual memory.  These regions are implemented as
  90.  *    ("sharing") maps, which then refer to the actual virtual
  91.  *    memory objects.  When two address maps "share" memory,
  92.  *    their top-level maps both have references to the same
  93.  *    sharing map.  When memory is virtual-copied from one
  94.  *    address map to another, the references in the sharing
  95.  *    maps are actually copied -- no copying occurs at the
  96.  *    virtual memory object level.
  97.  *
  98.  *    Since portions of maps are specified by start/end addreses,
  99.  *    which may not align with existing map entries, all
  100.  *    routines merely "clip" entries to these start/end values.
  101.  *    [That is, an entry is split into two, bordering at a
  102.  *    start or end value.]  Note that these clippings may not
  103.  *    always be necessary (as the two resulting entries are then
  104.  *    not changed); however, the clipping is done for convenience.
  105.  *    No attempt is currently made to "glue back together" two
  106.  *    abutting entries.
  107.  *
  108.  *    As mentioned above, virtual copy operations are performed
  109.  *    by copying VM object references from one sharing map to
  110.  *    another, and then marking both regions as copy-on-write.
  111.  *    It is important to note that only one writeable reference
  112.  *    to a VM object region exists in any map -- this means that
  113.  *    shadow object creation can be delayed until a write operation
  114.  *    occurs.
  115.  */
  116.  
  117. /*
  118.  *    vm_map_startup:
  119.  *
  120.  *    Initialize the vm_map module.  Must be called before
  121.  *    any other vm_map routines.
  122.  *
  123.  *    Map and entry structures are allocated from the general
  124.  *    purpose memory pool with some exceptions:
  125.  *
  126.  *    - The kernel map and kmem submap are allocated statically.
  127.  *    - Kernel map entries are allocated out of a static pool.
  128.  *
  129.  *    These restrictions are necessary since malloc() uses the
  130.  *    maps and requires map entries.
  131.  */
  132.  
  133. vm_offset_t    kentry_data;
  134. vm_size_t    kentry_data_size;
  135. vm_map_entry_t    kentry_free;
  136. vm_map_t    kmap_free;
  137.  
  138. void vm_map_startup()
  139. {
  140.     register int i;
  141.     register vm_map_entry_t mep;
  142.     vm_map_t mp;
  143.  
  144.     /*
  145.      * Static map structures for allocation before initialization of
  146.      * kernel map or kmem map.  vm_map_create knows how to deal with them.
  147.      */
  148.     kmap_free = mp = (vm_map_t) kentry_data;
  149.     i = MAX_KMAP;
  150.     while (--i > 0) {
  151.         mp->header.next = (vm_map_entry_t) (mp + 1);
  152.         mp++;
  153.     }
  154.     mp++->header.next = NULL;
  155.  
  156.     /*
  157.      * Form a free list of statically allocated kernel map entries
  158.      * with the rest.
  159.      */
  160.     kentry_free = mep = (vm_map_entry_t) mp;
  161.     i = (kentry_data_size - MAX_KMAP * sizeof *mp) / sizeof *mep;
  162.     while (--i > 0) {
  163.         mep->next = mep + 1;
  164.         mep++;
  165.     }
  166.     mep->next = NULL;
  167. }
  168.  
  169. /*
  170.  * Allocate a vmspace structure, including a vm_map and pmap,
  171.  * and initialize those structures.  The refcnt is set to 1.
  172.  * The remaining fields must be initialized by the caller.
  173.  */
  174. struct vmspace *
  175. vmspace_alloc(min, max, pageable)
  176.     vm_offset_t min, max;
  177.     int pageable;
  178. {
  179.     register struct vmspace *vm;
  180.  
  181.     MALLOC(vm, struct vmspace *, sizeof(struct vmspace), M_VMMAP, M_WAITOK);
  182.     bzero(vm, (caddr_t) &vm->vm_startcopy - (caddr_t) vm);
  183.     vm_map_init(&vm->vm_map, min, max, pageable);
  184.     pmap_pinit(&vm->vm_pmap);
  185.     vm->vm_map.pmap = &vm->vm_pmap;        /* XXX */
  186.     vm->vm_refcnt = 1;
  187.     return (vm);
  188. }
  189.  
  190. void
  191. vmspace_free(vm)
  192.     register struct vmspace *vm;
  193. {
  194.  
  195.     if (--vm->vm_refcnt == 0) {
  196.         /*
  197.          * Lock the map, to wait out all other references to it.
  198.          * Delete all of the mappings and pages they hold,
  199.          * then call the pmap module to reclaim anything left.
  200.          */
  201.         vm_map_lock(&vm->vm_map);
  202.         (void) vm_map_delete(&vm->vm_map, vm->vm_map.min_offset,
  203.             vm->vm_map.max_offset);
  204.         pmap_release(&vm->vm_pmap);
  205.         FREE(vm, M_VMMAP);
  206.     }
  207. }
  208.  
  209. /*
  210.  *    vm_map_create:
  211.  *
  212.  *    Creates and returns a new empty VM map with
  213.  *    the given physical map structure, and having
  214.  *    the given lower and upper address bounds.
  215.  */
  216. vm_map_t vm_map_create(pmap, min, max, pageable)
  217.     pmap_t        pmap;
  218.     vm_offset_t    min, max;
  219.     boolean_t    pageable;
  220. {
  221.     register vm_map_t    result;
  222.     extern vm_map_t        kernel_map, kmem_map;
  223.  
  224.     if (kmem_map == NULL) {
  225.         result = kmap_free;
  226.         kmap_free = (vm_map_t) result->header.next;
  227.         if (result == NULL)
  228.             panic("vm_map_create: out of maps");
  229.     } else
  230.         MALLOC(result, vm_map_t, sizeof(struct vm_map),
  231.                M_VMMAP, M_WAITOK);
  232.  
  233.     vm_map_init(result, min, max, pageable);
  234.     result->pmap = pmap;
  235.     return(result);
  236. }
  237.  
  238. /*
  239.  * Initialize an existing vm_map structure
  240.  * such as that in the vmspace structure.
  241.  * The pmap is set elsewhere.
  242.  */
  243. void
  244. vm_map_init(map, min, max, pageable)
  245.     register struct vm_map *map;
  246.     vm_offset_t    min, max;
  247.     boolean_t    pageable;
  248. {
  249.     map->header.next = map->header.prev = &map->header;
  250.     map->nentries = 0;
  251.     map->size = 0;
  252.     map->ref_count = 1;
  253.     map->is_main_map = TRUE;
  254.     map->min_offset = min;
  255.     map->max_offset = max;
  256.     map->entries_pageable = pageable;
  257.     map->first_free = &map->header;
  258.     map->hint = &map->header;
  259.     map->timestamp = 0;
  260.     lock_init(&map->lock, TRUE);
  261.     simple_lock_init(&map->ref_lock);
  262.     simple_lock_init(&map->hint_lock);
  263. }
  264.  
  265. /*
  266.  *    vm_map_entry_create:    [ internal use only ]
  267.  *
  268.  *    Allocates a VM map entry for insertion.
  269.  *    No entry fields are filled in.  This routine is
  270.  */
  271. vm_map_entry_t vm_map_entry_create(map)
  272.     vm_map_t    map;
  273. {
  274.     vm_map_entry_t    entry;
  275.     extern vm_map_t        kernel_map, kmem_map, mb_map;
  276.  
  277.     if (map == kernel_map || map == kmem_map || map == mb_map) {
  278.         if (entry = kentry_free)
  279.             kentry_free = kentry_free->next;
  280.     } else
  281.         MALLOC(entry, vm_map_entry_t, sizeof(struct vm_map_entry),
  282.                M_VMMAPENT, M_WAITOK);
  283.     if (entry == NULL)
  284.         panic("vm_map_entry_create: out of map entries");
  285.  
  286.     return(entry);
  287. }
  288.  
  289. /*
  290.  *    vm_map_entry_dispose:    [ internal use only ]
  291.  *
  292.  *    Inverse of vm_map_entry_create.
  293.  */
  294. void vm_map_entry_dispose(map, entry)
  295.     vm_map_t    map;
  296.     vm_map_entry_t    entry;
  297. {
  298.     extern vm_map_t        kernel_map, kmem_map, mb_map;
  299.  
  300.     if (map == kernel_map || map == kmem_map || map == mb_map) {
  301.         entry->next = kentry_free;
  302.         kentry_free = entry;
  303.     } else
  304.         FREE(entry, M_VMMAPENT);
  305. }
  306.  
  307. /*
  308.  *    vm_map_entry_{un,}link:
  309.  *
  310.  *    Insert/remove entries from maps.
  311.  */
  312. #define    vm_map_entry_link(map, after_where, entry) \
  313.         { \
  314.         (map)->nentries++; \
  315.         (entry)->prev = (after_where); \
  316.         (entry)->next = (after_where)->next; \
  317.         (entry)->prev->next = (entry); \
  318.         (entry)->next->prev = (entry); \
  319.         }
  320. #define    vm_map_entry_unlink(map, entry) \
  321.         { \
  322.         (map)->nentries--; \
  323.         (entry)->next->prev = (entry)->prev; \
  324.         (entry)->prev->next = (entry)->next; \
  325.         }
  326.  
  327. /*
  328.  *    vm_map_reference:
  329.  *
  330.  *    Creates another valid reference to the given map.
  331.  *
  332.  */
  333. void vm_map_reference(map)
  334.     register vm_map_t    map;
  335. {
  336.     if (map == NULL)
  337.         return;
  338.  
  339.     simple_lock(&map->ref_lock);
  340.     map->ref_count++;
  341.     simple_unlock(&map->ref_lock);
  342. }
  343.  
  344. /*
  345.  *    vm_map_deallocate:
  346.  *
  347.  *    Removes a reference from the specified map,
  348.  *    destroying it if no references remain.
  349.  *    The map should not be locked.
  350.  */
  351. void vm_map_deallocate(map)
  352.     register vm_map_t    map;
  353. {
  354.     register int        c;
  355.  
  356.     if (map == NULL)
  357.         return;
  358.  
  359.     simple_lock(&map->ref_lock);
  360.     c = --map->ref_count;
  361.     simple_unlock(&map->ref_lock);
  362.  
  363.     if (c > 0) {
  364.         return;
  365.     }
  366.  
  367.     /*
  368.      *    Lock the map, to wait out all other references
  369.      *    to it.
  370.      */
  371.  
  372.     vm_map_lock(map);
  373.  
  374.     (void) vm_map_delete(map, map->min_offset, map->max_offset);
  375.  
  376.     pmap_destroy(map->pmap);
  377.  
  378.     FREE(map, M_VMMAP);
  379. }
  380.  
  381. /*
  382.  *    vm_map_insert:    [ internal use only ]
  383.  *
  384.  *    Inserts the given whole VM object into the target
  385.  *    map at the specified address range.  The object's
  386.  *    size should match that of the address range.
  387.  *
  388.  *    Requires that the map be locked, and leaves it so.
  389.  */
  390. vm_map_insert(map, object, offset, start, end)
  391.     vm_map_t    map;
  392.     vm_object_t    object;
  393.     vm_offset_t    offset;
  394.     vm_offset_t    start;
  395.     vm_offset_t    end;
  396. {
  397.     register vm_map_entry_t        new_entry;
  398.     register vm_map_entry_t        prev_entry;
  399.     vm_map_entry_t            temp_entry;
  400.  
  401.     /*
  402.      *    Check that the start and end points are not bogus.
  403.      */
  404.  
  405.     if ((start < map->min_offset) || (end > map->max_offset) ||
  406.             (start >= end))
  407.         return(KERN_INVALID_ADDRESS);
  408.  
  409.     /*
  410.      *    Find the entry prior to the proposed
  411.      *    starting address; if it's part of an
  412.      *    existing entry, this range is bogus.
  413.      */
  414.  
  415.     if (vm_map_lookup_entry(map, start, &temp_entry))
  416.         return(KERN_NO_SPACE);
  417.  
  418.     prev_entry = temp_entry;
  419.  
  420.     /*
  421.      *    Assert that the next entry doesn't overlap the
  422.      *    end point.
  423.      */
  424.  
  425.     if ((prev_entry->next != &map->header) &&
  426.             (prev_entry->next->start < end))
  427.         return(KERN_NO_SPACE);
  428.  
  429.     /*
  430.      *    See if we can avoid creating a new entry by
  431.      *    extending one of our neighbors.
  432.      */
  433.  
  434.     if (object == NULL) {
  435.         if ((prev_entry != &map->header) &&
  436.             (prev_entry->end == start) &&
  437.             (map->is_main_map) &&
  438.             (prev_entry->is_a_map == FALSE) &&
  439.             (prev_entry->is_sub_map == FALSE) &&
  440.             (prev_entry->inheritance == VM_INHERIT_DEFAULT) &&
  441.             (prev_entry->protection == VM_PROT_DEFAULT) &&
  442.             (prev_entry->max_protection == VM_PROT_DEFAULT) &&
  443.             (prev_entry->wired_count == 0)) {
  444.  
  445.             if (vm_object_coalesce(prev_entry->object.vm_object,
  446.                     NULL,
  447.                     prev_entry->offset,
  448.                     (vm_offset_t) 0,
  449.                     (vm_size_t)(prev_entry->end
  450.                              - prev_entry->start),
  451.                     (vm_size_t)(end - prev_entry->end))) {
  452.                 /*
  453.                  *    Coalesced the two objects - can extend
  454.                  *    the previous map entry to include the
  455.                  *    new range.
  456.                  */
  457.                 map->size += (end - prev_entry->end);
  458.                 prev_entry->end = end;
  459.                 return(KERN_SUCCESS);
  460.             }
  461.         }
  462.     }
  463.  
  464.     /*
  465.      *    Create a new entry
  466.      */
  467.  
  468.     new_entry = vm_map_entry_create(map);
  469.     new_entry->start = start;
  470.     new_entry->end = end;
  471.  
  472.     new_entry->is_a_map = FALSE;
  473.     new_entry->is_sub_map = FALSE;
  474.     new_entry->object.vm_object = object;
  475.     new_entry->offset = offset;
  476.  
  477.     new_entry->copy_on_write = FALSE;
  478.     new_entry->needs_copy = FALSE;
  479.  
  480.     if (map->is_main_map) {
  481.         new_entry->inheritance = VM_INHERIT_DEFAULT;
  482.         new_entry->protection = VM_PROT_DEFAULT;
  483.         new_entry->max_protection = VM_PROT_DEFAULT;
  484.         new_entry->wired_count = 0;
  485.     }
  486.  
  487.     /*
  488.      *    Insert the new entry into the list
  489.      */
  490.  
  491.     vm_map_entry_link(map, prev_entry, new_entry);
  492.     map->size += new_entry->end - new_entry->start;
  493.  
  494.     /*
  495.      *    Update the free space hint
  496.      */
  497.  
  498.     if ((map->first_free == prev_entry) && (prev_entry->end >= new_entry->start))
  499.         map->first_free = new_entry;
  500.  
  501.     return(KERN_SUCCESS);
  502. }
  503.  
  504. /*
  505.  *    SAVE_HINT:
  506.  *
  507.  *    Saves the specified entry as the hint for
  508.  *    future lookups.  Performs necessary interlocks.
  509.  */
  510. #define    SAVE_HINT(map,value) \
  511.         simple_lock(&(map)->hint_lock); \
  512.         (map)->hint = (value); \
  513.         simple_unlock(&(map)->hint_lock);
  514.  
  515. /*
  516.  *    vm_map_lookup_entry:    [ internal use only ]
  517.  *
  518.  *    Finds the map entry containing (or
  519.  *    immediately preceding) the specified address
  520.  *    in the given map; the entry is returned
  521.  *    in the "entry" parameter.  The boolean
  522.  *    result indicates whether the address is
  523.  *    actually contained in the map.
  524.  */
  525. boolean_t vm_map_lookup_entry(map, address, entry)
  526.     register vm_map_t    map;
  527.     register vm_offset_t    address;
  528.     vm_map_entry_t        *entry;        /* OUT */
  529. {
  530.     register vm_map_entry_t        cur;
  531.     register vm_map_entry_t        last;
  532.  
  533.     /*
  534.      *    Start looking either from the head of the
  535.      *    list, or from the hint.
  536.      */
  537.  
  538.     simple_lock(&map->hint_lock);
  539.     cur = map->hint;
  540.     simple_unlock(&map->hint_lock);
  541.  
  542.     if (cur == &map->header)
  543.         cur = cur->next;
  544.  
  545.     if (address >= cur->start) {
  546.             /*
  547.          *    Go from hint to end of list.
  548.          *
  549.          *    But first, make a quick check to see if
  550.          *    we are already looking at the entry we
  551.          *    want (which is usually the case).
  552.          *    Note also that we don't need to save the hint
  553.          *    here... it is the same hint (unless we are
  554.          *    at the header, in which case the hint didn't
  555.          *    buy us anything anyway).
  556.          */
  557.         last = &map->header;
  558.         if ((cur != last) && (cur->end > address)) {
  559.             *entry = cur;
  560.             return(TRUE);
  561.         }
  562.     }
  563.     else {
  564.             /*
  565.          *    Go from start to hint, *inclusively*
  566.          */
  567.         last = cur->next;
  568.         cur = map->header.next;
  569.     }
  570.  
  571.     /*
  572.      *    Search linearly
  573.      */
  574.  
  575.     while (cur != last) {
  576.         if (cur->end > address) {
  577.             if (address >= cur->start) {
  578.                     /*
  579.                  *    Save this lookup for future
  580.                  *    hints, and return
  581.                  */
  582.  
  583.                 *entry = cur;
  584.                 SAVE_HINT(map, cur);
  585.                 return(TRUE);
  586.             }
  587.             break;
  588.         }
  589.         cur = cur->next;
  590.     }
  591.     *entry = cur->prev;
  592.     SAVE_HINT(map, *entry);
  593.     return(FALSE);
  594. }
  595.  
  596. /*
  597.  *    vm_map_find finds an unallocated region in the target address
  598.  *    map with the given length.  The search is defined to be
  599.  *    first-fit from the specified address; the region found is
  600.  *    returned in the same parameter.
  601.  *
  602.  */
  603. vm_map_find(map, object, offset, addr, length, find_space)
  604.     vm_map_t    map;
  605.     vm_object_t    object;
  606.     vm_offset_t    offset;
  607.     vm_offset_t    *addr;        /* IN/OUT */
  608.     vm_size_t    length;
  609.     boolean_t    find_space;
  610. {
  611.     register vm_map_entry_t    entry;
  612.     register vm_offset_t    start;
  613.     register vm_offset_t    end;
  614.     int            result;
  615.  
  616.     start = *addr;
  617.  
  618.     vm_map_lock(map);
  619.  
  620.     if (find_space) {
  621.         /*
  622.          *    Calculate the first possible address.
  623.          */
  624.  
  625.         if (start < map->min_offset)
  626.             start = map->min_offset;
  627.         if (start > map->max_offset) {
  628.             vm_map_unlock(map);
  629.             return (KERN_NO_SPACE);
  630.         }
  631.  
  632.         /*
  633.          *    Look for the first possible address;
  634.          *    if there's already something at this
  635.          *    address, we have to start after it.
  636.          */
  637.  
  638.         if (start == map->min_offset) {
  639.             if ((entry = map->first_free) != &map->header)
  640.                 start = entry->end;
  641.         } else {
  642.             vm_map_entry_t    tmp_entry;
  643.             if (vm_map_lookup_entry(map, start, &tmp_entry))
  644.                 start = tmp_entry->end;
  645.             entry = tmp_entry;
  646.         }
  647.  
  648.         /*
  649.          *    In any case, the "entry" always precedes
  650.          *    the proposed new region throughout the
  651.          *    loop:
  652.          */
  653.  
  654.         while (TRUE) {
  655.             register vm_map_entry_t    next;
  656.  
  657.                 /*
  658.              *    Find the end of the proposed new region.
  659.              *    Be sure we didn't go beyond the end, or
  660.              *    wrap around the address.
  661.              */
  662.  
  663.             end = start + length;
  664.  
  665.             if ((end > map->max_offset) || (end < start)) {
  666.                 vm_map_unlock(map);
  667.                 return (KERN_NO_SPACE);
  668.             }
  669.  
  670.             /*
  671.              *    If there are no more entries, we must win.
  672.              */
  673.  
  674.             next = entry->next;
  675.             if (next == &map->header)
  676.                 break;
  677.  
  678.             /*
  679.              *    If there is another entry, it must be
  680.              *    after the end of the potential new region.
  681.              */
  682.  
  683.             if (next->start >= end)
  684.                 break;
  685.  
  686.             /*
  687.              *    Didn't fit -- move to the next entry.
  688.              */
  689.  
  690.             entry = next;
  691.             start = entry->end;
  692.         }
  693.         *addr = start;
  694.         
  695.         SAVE_HINT(map, entry);
  696.     }
  697.  
  698.     result = vm_map_insert(map, object, offset, start, start + length);
  699.  
  700.     vm_map_unlock(map);
  701.     return(result);
  702. }
  703.  
  704. /*
  705.  *    vm_map_simplify_entry:    [ internal use only ]
  706.  *
  707.  *    Simplify the given map entry by:
  708.  *        removing extra sharing maps
  709.  *        [XXX maybe later] merging with a neighbor
  710.  */
  711. void vm_map_simplify_entry(map, entry)
  712.     vm_map_t    map;
  713.     vm_map_entry_t    entry;
  714. {
  715. #ifdef    lint
  716.     map++;
  717. #endif    lint
  718.  
  719.     /*
  720.      *    If this entry corresponds to a sharing map, then
  721.      *    see if we can remove the level of indirection.
  722.      *    If it's not a sharing map, then it points to
  723.      *    a VM object, so see if we can merge with either
  724.      *    of our neighbors.
  725.      */
  726.  
  727.     if (entry->is_sub_map)
  728.         return;
  729.     if (entry->is_a_map) {
  730. #if    0
  731.         vm_map_t    my_share_map;
  732.         int        count;
  733.  
  734.         my_share_map = entry->object.share_map;    
  735.         simple_lock(&my_share_map->ref_lock);
  736.         count = my_share_map->ref_count;
  737.         simple_unlock(&my_share_map->ref_lock);
  738.         
  739.         if (count == 1) {
  740.             /* Can move the region from
  741.              * entry->start to entry->end (+ entry->offset)
  742.              * in my_share_map into place of entry.
  743.              * Later.
  744.              */
  745.         }
  746. #endif    0
  747.     }
  748.     else {
  749.         /*
  750.          *    Try to merge with our neighbors.
  751.          *
  752.          *    Conditions for merge are:
  753.          *
  754.          *    1.  entries are adjacent.
  755.          *    2.  both entries point to objects
  756.          *        with null pagers.
  757.          *
  758.          *     If a merge is possible, we replace the two
  759.          *    entries with a single entry, then merge
  760.          *    the two objects into a single object.
  761.          *
  762.          *    Now, all that is left to do is write the
  763.          *    code!
  764.          */
  765.     }
  766. }
  767.  
  768. /*
  769.  *    vm_map_clip_start:    [ internal use only ]
  770.  *
  771.  *    Asserts that the given entry begins at or after
  772.  *    the specified address; if necessary,
  773.  *    it splits the entry into two.
  774.  */
  775. #define vm_map_clip_start(map, entry, startaddr) \
  776. { \
  777.     if (startaddr > entry->start) \
  778.         _vm_map_clip_start(map, entry, startaddr); \
  779. }
  780.  
  781. /*
  782.  *    This routine is called only when it is known that
  783.  *    the entry must be split.
  784.  */
  785. void _vm_map_clip_start(map, entry, start)
  786.     register vm_map_t    map;
  787.     register vm_map_entry_t    entry;
  788.     register vm_offset_t    start;
  789. {
  790.     register vm_map_entry_t    new_entry;
  791.  
  792.     /*
  793.      *    See if we can simplify this entry first
  794.      */
  795.          
  796.     vm_map_simplify_entry(map, entry);
  797.  
  798.     /*
  799.      *    Split off the front portion --
  800.      *    note that we must insert the new
  801.      *    entry BEFORE this one, so that
  802.      *    this entry has the specified starting
  803.      *    address.
  804.      */
  805.  
  806.     new_entry = vm_map_entry_create(map);
  807.     *new_entry = *entry;
  808.  
  809.     new_entry->end = start;
  810.     entry->offset += (start - entry->start);
  811.     entry->start = start;
  812.  
  813.     vm_map_entry_link(map, entry->prev, new_entry);
  814.  
  815.     if (entry->is_a_map || entry->is_sub_map)
  816.          vm_map_reference(new_entry->object.share_map);
  817.     else
  818.         vm_object_reference(new_entry->object.vm_object);
  819. }
  820.  
  821. /*
  822.  *    vm_map_clip_end:    [ internal use only ]
  823.  *
  824.  *    Asserts that the given entry ends at or before
  825.  *    the specified address; if necessary,
  826.  *    it splits the entry into two.
  827.  */
  828.  
  829. void _vm_map_clip_end();
  830. #define vm_map_clip_end(map, entry, endaddr) \
  831. { \
  832.     if (endaddr < entry->end) \
  833.         _vm_map_clip_end(map, entry, endaddr); \
  834. }
  835.  
  836. /*
  837.  *    This routine is called only when it is known that
  838.  *    the entry must be split.
  839.  */
  840. void _vm_map_clip_end(map, entry, end)
  841.     register vm_map_t    map;
  842.     register vm_map_entry_t    entry;
  843.     register vm_offset_t    end;
  844. {
  845.     register vm_map_entry_t    new_entry;
  846.  
  847.     /*
  848.      *    Create a new entry and insert it
  849.      *    AFTER the specified entry
  850.      */
  851.  
  852.     new_entry = vm_map_entry_create(map);
  853.     *new_entry = *entry;
  854.  
  855.     new_entry->start = entry->end = end;
  856.     new_entry->offset += (end - entry->start);
  857.  
  858.     vm_map_entry_link(map, entry, new_entry);
  859.  
  860.     if (entry->is_a_map || entry->is_sub_map)
  861.          vm_map_reference(new_entry->object.share_map);
  862.     else
  863.         vm_object_reference(new_entry->object.vm_object);
  864. }
  865.  
  866. /*
  867.  *    VM_MAP_RANGE_CHECK:    [ internal use only ]
  868.  *
  869.  *    Asserts that the starting and ending region
  870.  *    addresses fall within the valid range of the map.
  871.  */
  872. #define    VM_MAP_RANGE_CHECK(map, start, end)        \
  873.         {                    \
  874.         if (start < vm_map_min(map))        \
  875.             start = vm_map_min(map);    \
  876.         if (end > vm_map_max(map))        \
  877.             end = vm_map_max(map);        \
  878.         if (start > end)            \
  879.             start = end;            \
  880.         }
  881.  
  882. /*
  883.  *    vm_map_submap:        [ kernel use only ]
  884.  *
  885.  *    Mark the given range as handled by a subordinate map.
  886.  *
  887.  *    This range must have been created with vm_map_find,
  888.  *    and no other operations may have been performed on this
  889.  *    range prior to calling vm_map_submap.
  890.  *
  891.  *    Only a limited number of operations can be performed
  892.  *    within this rage after calling vm_map_submap:
  893.  *        vm_fault
  894.  *    [Don't try vm_map_copy!]
  895.  *
  896.  *    To remove a submapping, one must first remove the
  897.  *    range from the superior map, and then destroy the
  898.  *    submap (if desired).  [Better yet, don't try it.]
  899.  */
  900. vm_map_submap(map, start, end, submap)
  901.     register vm_map_t    map;
  902.     register vm_offset_t    start;
  903.     register vm_offset_t    end;
  904.     vm_map_t        submap;
  905. {
  906.     vm_map_entry_t        entry;
  907.     register int        result = KERN_INVALID_ARGUMENT;
  908.  
  909.     vm_map_lock(map);
  910.  
  911.     VM_MAP_RANGE_CHECK(map, start, end);
  912.  
  913.     if (vm_map_lookup_entry(map, start, &entry)) {
  914.         vm_map_clip_start(map, entry, start);
  915.     }
  916.      else
  917.         entry = entry->next;
  918.  
  919.     vm_map_clip_end(map, entry, end);
  920.  
  921.     if ((entry->start == start) && (entry->end == end) &&
  922.         (!entry->is_a_map) &&
  923.         (entry->object.vm_object == NULL) &&
  924.         (!entry->copy_on_write)) {
  925.         entry->is_a_map = FALSE;
  926.         entry->is_sub_map = TRUE;
  927.         vm_map_reference(entry->object.sub_map = submap);
  928.         result = KERN_SUCCESS;
  929.     }
  930.     vm_map_unlock(map);
  931.  
  932.     return(result);
  933. }
  934.  
  935. /*
  936.  *    vm_map_protect:
  937.  *
  938.  *    Sets the protection of the specified address
  939.  *    region in the target map.  If "set_max" is
  940.  *    specified, the maximum protection is to be set;
  941.  *    otherwise, only the current protection is affected.
  942.  */
  943. vm_map_protect(map, start, end, new_prot, set_max)
  944.     register vm_map_t    map;
  945.     register vm_offset_t    start;
  946.     register vm_offset_t    end;
  947.     register vm_prot_t    new_prot;
  948.     register boolean_t    set_max;
  949. {
  950.     register vm_map_entry_t        current;
  951.     vm_map_entry_t            entry;
  952.  
  953.     vm_map_lock(map);
  954.  
  955.     VM_MAP_RANGE_CHECK(map, start, end);
  956.  
  957.     if (vm_map_lookup_entry(map, start, &entry)) {
  958.         vm_map_clip_start(map, entry, start);
  959.     }
  960.      else
  961.         entry = entry->next;
  962.  
  963.     /*
  964.      *    Make a first pass to check for protection
  965.      *    violations.
  966.      */
  967.  
  968.     current = entry;
  969.     while ((current != &map->header) && (current->start < end)) {
  970.         if (current->is_sub_map)
  971.             return(KERN_INVALID_ARGUMENT);
  972.         if ((new_prot & current->max_protection) != new_prot) {
  973.             vm_map_unlock(map);
  974.             return(KERN_PROTECTION_FAILURE);
  975.         }
  976.  
  977.         current = current->next;
  978.     }
  979.  
  980.     /*
  981.      *    Go back and fix up protections.
  982.      *    [Note that clipping is not necessary the second time.]
  983.      */
  984.  
  985.     current = entry;
  986.  
  987.     while ((current != &map->header) && (current->start < end)) {
  988.         vm_prot_t    old_prot;
  989.  
  990.         vm_map_clip_end(map, current, end);
  991.  
  992.         old_prot = current->protection;
  993.         if (set_max)
  994.             current->protection =
  995.                 (current->max_protection = new_prot) &
  996.                     old_prot;
  997.         else
  998.             current->protection = new_prot;
  999.  
  1000.         /*
  1001.          *    Update physical map if necessary.
  1002.          *    Worry about copy-on-write here -- CHECK THIS XXX
  1003.          */
  1004.  
  1005.         if (current->protection != old_prot) {
  1006.  
  1007. #define MASK(entry)    ((entry)->copy_on_write ? ~VM_PROT_WRITE : \
  1008.                             VM_PROT_ALL)
  1009. #define    max(a,b)    ((a) > (b) ? (a) : (b))
  1010.  
  1011.             if (current->is_a_map) {
  1012.                 vm_map_entry_t    share_entry;
  1013.                 vm_offset_t    share_end;
  1014.  
  1015.                 vm_map_lock(current->object.share_map);
  1016.                 (void) vm_map_lookup_entry(
  1017.                         current->object.share_map,
  1018.                         current->offset,
  1019.                         &share_entry);
  1020.                 share_end = current->offset +
  1021.                     (current->end - current->start);
  1022.                 while ((share_entry !=
  1023.                     ¤t->object.share_map->header) &&
  1024.                     (share_entry->start < share_end)) {
  1025.  
  1026.                     pmap_protect(map->pmap,
  1027.                         (max(share_entry->start,
  1028.                             current->offset) -
  1029.                             current->offset +
  1030.                             current->start),
  1031.                         min(share_entry->end,
  1032.                             share_end) -
  1033.                         current->offset +
  1034.                         current->start,
  1035.                         current->protection &
  1036.                             MASK(share_entry));
  1037.  
  1038.                     share_entry = share_entry->next;
  1039.                 }
  1040.                 vm_map_unlock(current->object.share_map);
  1041.             }
  1042.             else
  1043.                  pmap_protect(map->pmap, current->start,
  1044.                     current->end,
  1045.                     current->protection & MASK(entry));
  1046. #undef    max
  1047. #undef    MASK
  1048.         }
  1049.         current = current->next;
  1050.     }
  1051.  
  1052.     vm_map_unlock(map);
  1053.     return(KERN_SUCCESS);
  1054. }
  1055.  
  1056. /*
  1057.  *    vm_map_inherit:
  1058.  *
  1059.  *    Sets the inheritance of the specified address
  1060.  *    range in the target map.  Inheritance
  1061.  *    affects how the map will be shared with
  1062.  *    child maps at the time of vm_map_fork.
  1063.  */
  1064. vm_map_inherit(map, start, end, new_inheritance)
  1065.     register vm_map_t    map;
  1066.     register vm_offset_t    start;
  1067.     register vm_offset_t    end;
  1068.     register vm_inherit_t    new_inheritance;
  1069. {
  1070.     register vm_map_entry_t    entry;
  1071.     vm_map_entry_t    temp_entry;
  1072.  
  1073.     switch (new_inheritance) {
  1074.     case VM_INHERIT_NONE:
  1075.     case VM_INHERIT_COPY:
  1076.     case VM_INHERIT_SHARE:
  1077.         break;
  1078.     default:
  1079.         return(KERN_INVALID_ARGUMENT);
  1080.     }
  1081.  
  1082.     vm_map_lock(map);
  1083.  
  1084.     VM_MAP_RANGE_CHECK(map, start, end);
  1085.  
  1086.     if (vm_map_lookup_entry(map, start, &temp_entry)) {
  1087.         entry = temp_entry;
  1088.         vm_map_clip_start(map, entry, start);
  1089.     }
  1090.     else
  1091.         entry = temp_entry->next;
  1092.  
  1093.     while ((entry != &map->header) && (entry->start < end)) {
  1094.         vm_map_clip_end(map, entry, end);
  1095.  
  1096.         entry->inheritance = new_inheritance;
  1097.  
  1098.         entry = entry->next;
  1099.     }
  1100.  
  1101.     vm_map_unlock(map);
  1102.     return(KERN_SUCCESS);
  1103. }
  1104.  
  1105. /*
  1106.  *    vm_map_pageable:
  1107.  *
  1108.  *    Sets the pageability of the specified address
  1109.  *    range in the target map.  Regions specified
  1110.  *    as not pageable require locked-down physical
  1111.  *    memory and physical page maps.
  1112.  *
  1113.  *    The map must not be locked, but a reference
  1114.  *    must remain to the map throughout the call.
  1115.  */
  1116. vm_map_pageable(map, start, end, new_pageable)
  1117.     register vm_map_t    map;
  1118.     register vm_offset_t    start;
  1119.     register vm_offset_t    end;
  1120.     register boolean_t    new_pageable;
  1121. {
  1122.     register vm_map_entry_t    entry;
  1123.     vm_map_entry_t        temp_entry;
  1124.  
  1125.     vm_map_lock(map);
  1126.  
  1127.     VM_MAP_RANGE_CHECK(map, start, end);
  1128.  
  1129.     /*
  1130.      *    Only one pageability change may take place at one
  1131.      *    time, since vm_fault assumes it will be called
  1132.      *    only once for each wiring/unwiring.  Therefore, we
  1133.      *    have to make sure we're actually changing the pageability
  1134.      *    for the entire region.  We do so before making any changes.
  1135.      */
  1136.  
  1137.     if (vm_map_lookup_entry(map, start, &temp_entry)) {
  1138.         entry = temp_entry;
  1139.         vm_map_clip_start(map, entry, start);
  1140.     }
  1141.     else
  1142.         entry = temp_entry->next;
  1143.     temp_entry = entry;
  1144.  
  1145.     /*
  1146.      *    Actions are rather different for wiring and unwiring,
  1147.      *    so we have two separate cases.
  1148.      */
  1149.  
  1150.     if (new_pageable) {
  1151.  
  1152.         /*
  1153.          *    Unwiring.  First ensure that the range to be
  1154.          *    unwired is really wired down.
  1155.          */
  1156.         while ((entry != &map->header) && (entry->start < end)) {
  1157.  
  1158.             if (entry->wired_count == 0) {
  1159.             vm_map_unlock(map);
  1160.             return(KERN_INVALID_ARGUMENT);
  1161.             }
  1162.             entry = entry->next;
  1163.         }
  1164.  
  1165.         /*
  1166.          *    Now decrement the wiring count for each region.
  1167.          *    If a region becomes completely unwired,
  1168.          *    unwire its physical pages and mappings.
  1169.          */
  1170.         lock_set_recursive(&map->lock);
  1171.  
  1172.         entry = temp_entry;
  1173.         while ((entry != &map->header) && (entry->start < end)) {
  1174.             vm_map_clip_end(map, entry, end);
  1175.  
  1176.             entry->wired_count--;
  1177.             if (entry->wired_count == 0)
  1178.             vm_fault_unwire(map, entry->start, entry->end);
  1179.  
  1180.             entry = entry->next;
  1181.         }
  1182.         lock_clear_recursive(&map->lock);
  1183.     }
  1184.  
  1185.     else {
  1186.         /*
  1187.          *    Wiring.  We must do this in two passes:
  1188.          *
  1189.          *    1.  Holding the write lock, we increment the
  1190.          *        wiring count.  For any area that is not already
  1191.          *        wired, we create any shadow objects that need
  1192.          *        to be created.
  1193.          *
  1194.          *    2.  We downgrade to a read lock, and call
  1195.          *        vm_fault_wire to fault in the pages for any
  1196.          *        newly wired area (wired_count is 1).
  1197.          *
  1198.          *    Downgrading to a read lock for vm_fault_wire avoids
  1199.          *    a possible deadlock with another thread that may have
  1200.          *    faulted on one of the pages to be wired (it would mark
  1201.          *    the page busy, blocking us, then in turn block on the
  1202.          *    map lock that we hold).  Because of problems in the
  1203.          *    recursive lock package, we cannot upgrade to a write
  1204.          *    lock in vm_map_lookup.  Thus, any actions that require
  1205.          *    the write lock must be done beforehand.  Because we
  1206.          *    keep the read lock on the map, the copy-on-write status
  1207.          *    of the entries we modify here cannot change.
  1208.          */
  1209.  
  1210.         /*
  1211.          *    Pass 1.
  1212.          */
  1213.         entry = temp_entry;
  1214.         while ((entry != &map->header) && (entry->start < end)) {
  1215.             vm_map_clip_end(map, entry, end);
  1216.  
  1217.             entry->wired_count++;
  1218.             if (entry->wired_count == 1) {
  1219.  
  1220.             /*
  1221.              *    Perform actions of vm_map_lookup that need
  1222.              *    the write lock on the map: create a shadow
  1223.              *    object for a copy-on-write region, or an
  1224.              *    object for a zero-fill region.
  1225.              *
  1226.              *    We don't have to do this for entries that
  1227.              *    point to sharing maps, because we won't hold
  1228.              *    the lock on the sharing map.
  1229.              */
  1230.             if (!entry->is_a_map) {
  1231.                 if (entry->needs_copy &&
  1232.                 ((entry->protection & VM_PROT_WRITE) != 0)) {
  1233.  
  1234.                 vm_object_shadow(&entry->object.vm_object,
  1235.                         &entry->offset,
  1236.                         (vm_size_t)(entry->end
  1237.                             - entry->start));
  1238.                 entry->needs_copy = FALSE;
  1239.                 }
  1240.                 else if (entry->object.vm_object == NULL) {
  1241.                 entry->object.vm_object =
  1242.                     vm_object_allocate((vm_size_t)(entry->end
  1243.                                 - entry->start));
  1244.                 entry->offset = (vm_offset_t)0;
  1245.                 }
  1246.             }
  1247.             }
  1248.  
  1249.             entry = entry->next;
  1250.         }
  1251.  
  1252.         /*
  1253.          *    Pass 2.
  1254.          */
  1255.  
  1256.         /*
  1257.          * HACK HACK HACK HACK
  1258.          *
  1259.          * If we are wiring in the kernel map or a submap of it,
  1260.          * unlock the map to avoid deadlocks.  We trust that the
  1261.          * kernel threads are well-behaved, and therefore will
  1262.          * not do anything destructive to this region of the map
  1263.          * while we have it unlocked.  We cannot trust user threads
  1264.          * to do the same.
  1265.          *
  1266.          * HACK HACK HACK HACK
  1267.          */
  1268.         if (vm_map_pmap(map) == kernel_pmap) {
  1269.             vm_map_unlock(map);        /* trust me ... */
  1270.         }
  1271.         else {
  1272.             lock_set_recursive(&map->lock);
  1273.             lock_write_to_read(&map->lock);
  1274.         }
  1275.  
  1276.         entry = temp_entry;
  1277.         while (entry != &map->header && entry->start < end) {
  1278.             if (entry->wired_count == 1) {
  1279.             vm_fault_wire(map, entry->start, entry->end);
  1280.             }
  1281.             entry = entry->next;
  1282.         }
  1283.  
  1284.         if (vm_map_pmap(map) == kernel_pmap) {
  1285.             vm_map_lock(map);
  1286.         }
  1287.         else {
  1288.             lock_clear_recursive(&map->lock);
  1289.         }
  1290.     }
  1291.  
  1292.     vm_map_unlock(map);
  1293.  
  1294.     return(KERN_SUCCESS);
  1295. }
  1296.  
  1297. /*
  1298.  *    vm_map_entry_unwire:    [ internal use only ]
  1299.  *
  1300.  *    Make the region specified by this entry pageable.
  1301.  *
  1302.  *    The map in question should be locked.
  1303.  *    [This is the reason for this routine's existence.]
  1304.  */
  1305. void vm_map_entry_unwire(map, entry)
  1306.     vm_map_t        map;
  1307.     register vm_map_entry_t    entry;
  1308. {
  1309.     vm_fault_unwire(map, entry->start, entry->end);
  1310.     entry->wired_count = 0;
  1311. }
  1312.  
  1313. /*
  1314.  *    vm_map_entry_delete:    [ internal use only ]
  1315.  *
  1316.  *    Deallocate the given entry from the target map.
  1317.  */        
  1318. void vm_map_entry_delete(map, entry)
  1319.     register vm_map_t    map;
  1320.     register vm_map_entry_t    entry;
  1321. {
  1322.     if (entry->wired_count != 0)
  1323.         vm_map_entry_unwire(map, entry);
  1324.         
  1325.     vm_map_entry_unlink(map, entry);
  1326.     map->size -= entry->end - entry->start;
  1327.  
  1328.     if (entry->is_a_map || entry->is_sub_map)
  1329.         vm_map_deallocate(entry->object.share_map);
  1330.     else
  1331.          vm_object_deallocate(entry->object.vm_object);
  1332.  
  1333.     vm_map_entry_dispose(map, entry);
  1334. }
  1335.  
  1336. /*
  1337.  *    vm_map_delete:    [ internal use only ]
  1338.  *
  1339.  *    Deallocates the given address range from the target
  1340.  *    map.
  1341.  *
  1342.  *    When called with a sharing map, removes pages from
  1343.  *    that region from all physical maps.
  1344.  */
  1345. vm_map_delete(map, start, end)
  1346.     register vm_map_t    map;
  1347.     vm_offset_t        start;
  1348.     register vm_offset_t    end;
  1349. {
  1350.     register vm_map_entry_t    entry;
  1351.     vm_map_entry_t        first_entry;
  1352.  
  1353.     /*
  1354.      *    Find the start of the region, and clip it
  1355.      */
  1356.  
  1357.     if (!vm_map_lookup_entry(map, start, &first_entry))
  1358.         entry = first_entry->next;
  1359.     else {
  1360.         entry = first_entry;
  1361.         vm_map_clip_start(map, entry, start);
  1362.  
  1363.         /*
  1364.          *    Fix the lookup hint now, rather than each
  1365.          *    time though the loop.
  1366.          */
  1367.  
  1368.         SAVE_HINT(map, entry->prev);
  1369.     }
  1370.  
  1371.     /*
  1372.      *    Save the free space hint
  1373.      */
  1374.  
  1375.     if (map->first_free->start >= start)
  1376.         map->first_free = entry->prev;
  1377.  
  1378.     /*
  1379.      *    Step through all entries in this region
  1380.      */
  1381.  
  1382.     while ((entry != &map->header) && (entry->start < end)) {
  1383.         vm_map_entry_t        next;
  1384.         register vm_offset_t    s, e;
  1385.         register vm_object_t    object;
  1386.  
  1387.         vm_map_clip_end(map, entry, end);
  1388.  
  1389.         next = entry->next;
  1390.         s = entry->start;
  1391.         e = entry->end;
  1392.  
  1393.         /*
  1394.          *    Unwire before removing addresses from the pmap;
  1395.          *    otherwise, unwiring will put the entries back in
  1396.          *    the pmap.
  1397.          */
  1398.  
  1399.         object = entry->object.vm_object;
  1400.         if (entry->wired_count != 0)
  1401.             vm_map_entry_unwire(map, entry);
  1402.  
  1403.         /*
  1404.          *    If this is a sharing map, we must remove
  1405.          *    *all* references to this data, since we can't
  1406.          *    find all of the physical maps which are sharing
  1407.          *    it.
  1408.          */
  1409.  
  1410.         if (object == kernel_object || object == kmem_object)
  1411.             vm_object_page_remove(object, entry->offset,
  1412.                     entry->offset + (e - s));
  1413.         else if (!map->is_main_map)
  1414.             vm_object_pmap_remove(object,
  1415.                      entry->offset,
  1416.                      entry->offset + (e - s));
  1417.         else
  1418.             pmap_remove(map->pmap, s, e);
  1419.  
  1420.         /*
  1421.          *    Delete the entry (which may delete the object)
  1422.          *    only after removing all pmap entries pointing
  1423.          *    to its pages.  (Otherwise, its page frames may
  1424.          *    be reallocated, and any modify bits will be
  1425.          *    set in the wrong object!)
  1426.          */
  1427.  
  1428.         vm_map_entry_delete(map, entry);
  1429.         entry = next;
  1430.     }
  1431.     return(KERN_SUCCESS);
  1432. }
  1433.  
  1434. /*
  1435.  *    vm_map_remove:
  1436.  *
  1437.  *    Remove the given address range from the target map.
  1438.  *    This is the exported form of vm_map_delete.
  1439.  */
  1440. vm_map_remove(map, start, end)
  1441.     register vm_map_t    map;
  1442.     register vm_offset_t    start;
  1443.     register vm_offset_t    end;
  1444. {
  1445.     register int        result;
  1446.  
  1447.     vm_map_lock(map);
  1448.     VM_MAP_RANGE_CHECK(map, start, end);
  1449.     result = vm_map_delete(map, start, end);
  1450.     vm_map_unlock(map);
  1451.  
  1452.     return(result);
  1453. }
  1454.  
  1455. /*
  1456.  *    vm_map_check_protection:
  1457.  *
  1458.  *    Assert that the target map allows the specified
  1459.  *    privilege on the entire address region given.
  1460.  *    The entire region must be allocated.
  1461.  */
  1462. boolean_t vm_map_check_protection(map, start, end, protection)
  1463.     register vm_map_t    map;
  1464.     register vm_offset_t    start;
  1465.     register vm_offset_t    end;
  1466.     register vm_prot_t    protection;
  1467. {
  1468.     register vm_map_entry_t    entry;
  1469.     vm_map_entry_t        tmp_entry;
  1470.  
  1471.     if (!vm_map_lookup_entry(map, start, &tmp_entry)) {
  1472.         return(FALSE);
  1473.     }
  1474.  
  1475.     entry = tmp_entry;
  1476.  
  1477.     while (start < end) {
  1478.         if (entry == &map->header) {
  1479.             return(FALSE);
  1480.         }
  1481.  
  1482.         /*
  1483.          *    No holes allowed!
  1484.          */
  1485.  
  1486.         if (start < entry->start) {
  1487.             return(FALSE);
  1488.         }
  1489.  
  1490.         /*
  1491.          * Check protection associated with entry.
  1492.          */
  1493.  
  1494.         if ((entry->protection & protection) != protection) {
  1495.             return(FALSE);
  1496.         }
  1497.  
  1498.         /* go to next entry */
  1499.  
  1500.         start = entry->end;
  1501.         entry = entry->next;
  1502.     }
  1503.     return(TRUE);
  1504. }
  1505.  
  1506. /*
  1507.  *    vm_map_copy_entry:
  1508.  *
  1509.  *    Copies the contents of the source entry to the destination
  1510.  *    entry.  The entries *must* be aligned properly.
  1511.  */
  1512. void vm_map_copy_entry(src_map, dst_map, src_entry, dst_entry)
  1513.     vm_map_t        src_map, dst_map;
  1514.     register vm_map_entry_t    src_entry, dst_entry;
  1515. {
  1516.     vm_object_t    temp_object;
  1517.  
  1518.     if (src_entry->is_sub_map || dst_entry->is_sub_map)
  1519.         return;
  1520.  
  1521.     if (dst_entry->object.vm_object != NULL &&
  1522.         !dst_entry->object.vm_object->internal)
  1523.         printf("vm_map_copy_entry: copying over permanent data!\n");
  1524.  
  1525.     /*
  1526.      *    If our destination map was wired down,
  1527.      *    unwire it now.
  1528.      */
  1529.  
  1530.     if (dst_entry->wired_count != 0)
  1531.         vm_map_entry_unwire(dst_map, dst_entry);
  1532.  
  1533.     /*
  1534.      *    If we're dealing with a sharing map, we
  1535.      *    must remove the destination pages from
  1536.      *    all maps (since we cannot know which maps
  1537.      *    this sharing map belongs in).
  1538.      */
  1539.  
  1540.     if (dst_map->is_main_map)
  1541.         pmap_remove(dst_map->pmap, dst_entry->start, dst_entry->end);
  1542.     else
  1543.         vm_object_pmap_remove(dst_entry->object.vm_object,
  1544.             dst_entry->offset,
  1545.             dst_entry->offset +
  1546.                 (dst_entry->end - dst_entry->start));
  1547.  
  1548.     if (src_entry->wired_count == 0) {
  1549.  
  1550.         boolean_t    src_needs_copy;
  1551.  
  1552.         /*
  1553.          *    If the source entry is marked needs_copy,
  1554.          *    it is already write-protected.
  1555.          */
  1556.         if (!src_entry->needs_copy) {
  1557.  
  1558.             boolean_t    su;
  1559.  
  1560.             /*
  1561.              *    If the source entry has only one mapping,
  1562.              *    we can just protect the virtual address
  1563.              *    range.
  1564.              */
  1565.             if (!(su = src_map->is_main_map)) {
  1566.                 simple_lock(&src_map->ref_lock);
  1567.                 su = (src_map->ref_count == 1);
  1568.                 simple_unlock(&src_map->ref_lock);
  1569.             }
  1570.  
  1571.             if (su) {
  1572.                 pmap_protect(src_map->pmap,
  1573.                     src_entry->start,
  1574.                     src_entry->end,
  1575.                     src_entry->protection & ~VM_PROT_WRITE);
  1576.             }
  1577.             else {
  1578.                 vm_object_pmap_copy(src_entry->object.vm_object,
  1579.                     src_entry->offset,
  1580.                     src_entry->offset + (src_entry->end
  1581.                                 -src_entry->start));
  1582.             }
  1583.         }
  1584.  
  1585.         /*
  1586.          *    Make a copy of the object.
  1587.          */
  1588.         temp_object = dst_entry->object.vm_object;
  1589.         vm_object_copy(src_entry->object.vm_object,
  1590.                 src_entry->offset,
  1591.                 (vm_size_t)(src_entry->end -
  1592.                         src_entry->start),
  1593.                 &dst_entry->object.vm_object,
  1594.                 &dst_entry->offset,
  1595.                 &src_needs_copy);
  1596.         /*
  1597.          *    If we didn't get a copy-object now, mark the
  1598.          *    source map entry so that a shadow will be created
  1599.          *    to hold its changed pages.
  1600.          */
  1601.         if (src_needs_copy)
  1602.             src_entry->needs_copy = TRUE;
  1603.  
  1604.         /*
  1605.          *    The destination always needs to have a shadow
  1606.          *    created.
  1607.          */
  1608.         dst_entry->needs_copy = TRUE;
  1609.  
  1610.         /*
  1611.          *    Mark the entries copy-on-write, so that write-enabling
  1612.          *    the entry won't make copy-on-write pages writable.
  1613.          */
  1614.         src_entry->copy_on_write = TRUE;
  1615.         dst_entry->copy_on_write = TRUE;
  1616.         /*
  1617.          *    Get rid of the old object.
  1618.          */
  1619.         vm_object_deallocate(temp_object);
  1620.  
  1621.         pmap_copy(dst_map->pmap, src_map->pmap, dst_entry->start,
  1622.             dst_entry->end - dst_entry->start, src_entry->start);
  1623.     }
  1624.     else {
  1625.         /*
  1626.          *    Of course, wired down pages can't be set copy-on-write.
  1627.          *    Cause wired pages to be copied into the new
  1628.          *    map by simulating faults (the new pages are
  1629.          *    pageable)
  1630.          */
  1631.         vm_fault_copy_entry(dst_map, src_map, dst_entry, src_entry);
  1632.     }
  1633. }
  1634.  
  1635. /*
  1636.  *    vm_map_copy:
  1637.  *
  1638.  *    Perform a virtual memory copy from the source
  1639.  *    address map/range to the destination map/range.
  1640.  *
  1641.  *    If src_destroy or dst_alloc is requested,
  1642.  *    the source and destination regions should be
  1643.  *    disjoint, not only in the top-level map, but
  1644.  *    in the sharing maps as well.  [The best way
  1645.  *    to guarantee this is to use a new intermediate
  1646.  *    map to make copies.  This also reduces map
  1647.  *    fragmentation.]
  1648.  */
  1649. vm_map_copy(dst_map, src_map,
  1650.               dst_addr, len, src_addr,
  1651.               dst_alloc, src_destroy)
  1652.     vm_map_t    dst_map;
  1653.     vm_map_t    src_map;
  1654.     vm_offset_t    dst_addr;
  1655.     vm_size_t    len;
  1656.     vm_offset_t    src_addr;
  1657.     boolean_t    dst_alloc;
  1658.     boolean_t    src_destroy;
  1659. {
  1660.     register
  1661.     vm_map_entry_t    src_entry;
  1662.     register
  1663.     vm_map_entry_t    dst_entry;
  1664.     vm_map_entry_t    tmp_entry;
  1665.     vm_offset_t    src_start;
  1666.     vm_offset_t    src_end;
  1667.     vm_offset_t    dst_start;
  1668.     vm_offset_t    dst_end;
  1669.     vm_offset_t    src_clip;
  1670.     vm_offset_t    dst_clip;
  1671.     int        result;
  1672.     boolean_t    old_src_destroy;
  1673.  
  1674.     /*
  1675.      *    XXX While we figure out why src_destroy screws up,
  1676.      *    we'll do it by explicitly vm_map_delete'ing at the end.
  1677.      */
  1678.  
  1679.     old_src_destroy = src_destroy;
  1680.     src_destroy = FALSE;
  1681.  
  1682.     /*
  1683.      *    Compute start and end of region in both maps
  1684.      */
  1685.  
  1686.     src_start = src_addr;
  1687.     src_end = src_start + len;
  1688.     dst_start = dst_addr;
  1689.     dst_end = dst_start + len;
  1690.  
  1691.     /*
  1692.      *    Check that the region can exist in both source
  1693.      *    and destination.
  1694.      */
  1695.  
  1696.     if ((dst_end < dst_start) || (src_end < src_start))
  1697.         return(KERN_NO_SPACE);
  1698.  
  1699.     /*
  1700.      *    Lock the maps in question -- we avoid deadlock
  1701.      *    by ordering lock acquisition by map value
  1702.      */
  1703.  
  1704.     if (src_map == dst_map) {
  1705.         vm_map_lock(src_map);
  1706.     }
  1707.     else if ((int) src_map < (int) dst_map) {
  1708.          vm_map_lock(src_map);
  1709.         vm_map_lock(dst_map);
  1710.     } else {
  1711.         vm_map_lock(dst_map);
  1712.          vm_map_lock(src_map);
  1713.     }
  1714.  
  1715.     result = KERN_SUCCESS;
  1716.  
  1717.     /*
  1718.      *    Check protections... source must be completely readable and
  1719.      *    destination must be completely writable.  [Note that if we're
  1720.      *    allocating the destination region, we don't have to worry
  1721.      *    about protection, but instead about whether the region
  1722.      *    exists.]
  1723.      */
  1724.  
  1725.     if (src_map->is_main_map && dst_map->is_main_map) {
  1726.         if (!vm_map_check_protection(src_map, src_start, src_end,
  1727.                     VM_PROT_READ)) {
  1728.             result = KERN_PROTECTION_FAILURE;
  1729.             goto Return;
  1730.         }
  1731.  
  1732.         if (dst_alloc) {
  1733.             /* XXX Consider making this a vm_map_find instead */
  1734.             if ((result = vm_map_insert(dst_map, NULL,
  1735.                     (vm_offset_t) 0, dst_start, dst_end)) != KERN_SUCCESS)
  1736.                 goto Return;
  1737.         }
  1738.         else if (!vm_map_check_protection(dst_map, dst_start, dst_end,
  1739.                     VM_PROT_WRITE)) {
  1740.             result = KERN_PROTECTION_FAILURE;
  1741.             goto Return;
  1742.         }
  1743.     }
  1744.  
  1745.     /*
  1746.      *    Find the start entries and clip.
  1747.      *
  1748.      *    Note that checking protection asserts that the
  1749.      *    lookup cannot fail.
  1750.      *
  1751.      *    Also note that we wait to do the second lookup
  1752.      *    until we have done the first clip, as the clip
  1753.      *    may affect which entry we get!
  1754.      */
  1755.  
  1756.     (void) vm_map_lookup_entry(src_map, src_addr, &tmp_entry);
  1757.     src_entry = tmp_entry;
  1758.     vm_map_clip_start(src_map, src_entry, src_start);
  1759.  
  1760.     (void) vm_map_lookup_entry(dst_map, dst_addr, &tmp_entry);
  1761.     dst_entry = tmp_entry;
  1762.     vm_map_clip_start(dst_map, dst_entry, dst_start);
  1763.  
  1764.     /*
  1765.      *    If both source and destination entries are the same,
  1766.      *    retry the first lookup, as it may have changed.
  1767.      */
  1768.  
  1769.     if (src_entry == dst_entry) {
  1770.         (void) vm_map_lookup_entry(src_map, src_addr, &tmp_entry);
  1771.         src_entry = tmp_entry;
  1772.     }
  1773.  
  1774.     /*
  1775.      *    If source and destination entries are still the same,
  1776.      *    a null copy is being performed.
  1777.      */
  1778.  
  1779.     if (src_entry == dst_entry)
  1780.         goto Return;
  1781.  
  1782.     /*
  1783.      *    Go through entries until we get to the end of the
  1784.      *    region.
  1785.      */
  1786.  
  1787.     while (src_start < src_end) {
  1788.         /*
  1789.          *    Clip the entries to the endpoint of the entire region.
  1790.          */
  1791.  
  1792.         vm_map_clip_end(src_map, src_entry, src_end);
  1793.         vm_map_clip_end(dst_map, dst_entry, dst_end);
  1794.  
  1795.         /*
  1796.          *    Clip each entry to the endpoint of the other entry.
  1797.          */
  1798.  
  1799.         src_clip = src_entry->start + (dst_entry->end - dst_entry->start);
  1800.         vm_map_clip_end(src_map, src_entry, src_clip);
  1801.  
  1802.         dst_clip = dst_entry->start + (src_entry->end - src_entry->start);
  1803.         vm_map_clip_end(dst_map, dst_entry, dst_clip);
  1804.  
  1805.         /*
  1806.          *    Both entries now match in size and relative endpoints.
  1807.          *
  1808.          *    If both entries refer to a VM object, we can
  1809.          *    deal with them now.
  1810.          */
  1811.  
  1812.         if (!src_entry->is_a_map && !dst_entry->is_a_map) {
  1813.             vm_map_copy_entry(src_map, dst_map, src_entry,
  1814.                         dst_entry);
  1815.         }
  1816.         else {
  1817.             register vm_map_t    new_dst_map;
  1818.             vm_offset_t        new_dst_start;
  1819.             vm_size_t        new_size;
  1820.             vm_map_t        new_src_map;
  1821.             vm_offset_t        new_src_start;
  1822.  
  1823.             /*
  1824.              *    We have to follow at least one sharing map.
  1825.              */
  1826.  
  1827.             new_size = (dst_entry->end - dst_entry->start);
  1828.  
  1829.             if (src_entry->is_a_map) {
  1830.                 new_src_map = src_entry->object.share_map;
  1831.                 new_src_start = src_entry->offset;
  1832.             }
  1833.             else {
  1834.                  new_src_map = src_map;
  1835.                 new_src_start = src_entry->start;
  1836.                 lock_set_recursive(&src_map->lock);
  1837.             }
  1838.  
  1839.             if (dst_entry->is_a_map) {
  1840.                     vm_offset_t    new_dst_end;
  1841.  
  1842.                 new_dst_map = dst_entry->object.share_map;
  1843.                 new_dst_start = dst_entry->offset;
  1844.  
  1845.                 /*
  1846.                  *    Since the destination sharing entries
  1847.                  *    will be merely deallocated, we can
  1848.                  *    do that now, and replace the region
  1849.                  *    with a null object.  [This prevents
  1850.                  *    splitting the source map to match
  1851.                  *    the form of the destination map.]
  1852.                  *    Note that we can only do so if the
  1853.                  *    source and destination do not overlap.
  1854.                  */
  1855.  
  1856.                 new_dst_end = new_dst_start + new_size;
  1857.  
  1858.                 if (new_dst_map != new_src_map) {
  1859.                     vm_map_lock(new_dst_map);
  1860.                     (void) vm_map_delete(new_dst_map,
  1861.                             new_dst_start,
  1862.                             new_dst_end);
  1863.                     (void) vm_map_insert(new_dst_map,
  1864.                             NULL,
  1865.                             (vm_offset_t) 0,
  1866.                             new_dst_start,
  1867.                             new_dst_end);
  1868.                     vm_map_unlock(new_dst_map);
  1869.                 }
  1870.             }
  1871.             else {
  1872.                  new_dst_map = dst_map;
  1873.                 new_dst_start = dst_entry->start;
  1874.                 lock_set_recursive(&dst_map->lock);
  1875.             }
  1876.  
  1877.             /*
  1878.              *    Recursively copy the sharing map.
  1879.              */
  1880.  
  1881.             (void) vm_map_copy(new_dst_map, new_src_map,
  1882.                 new_dst_start, new_size, new_src_start,
  1883.                 FALSE, FALSE);
  1884.  
  1885.             if (dst_map == new_dst_map)
  1886.                 lock_clear_recursive(&dst_map->lock);
  1887.             if (src_map == new_src_map)
  1888.                 lock_clear_recursive(&src_map->lock);
  1889.         }
  1890.  
  1891.         /*
  1892.          *    Update variables for next pass through the loop.
  1893.          */
  1894.  
  1895.         src_start = src_entry->end;
  1896.         src_entry = src_entry->next;
  1897.         dst_start = dst_entry->end;
  1898.         dst_entry = dst_entry->next;
  1899.  
  1900.         /*
  1901.          *    If the source is to be destroyed, here is the
  1902.          *    place to do it.
  1903.          */
  1904.  
  1905.         if (src_destroy && src_map->is_main_map &&
  1906.                         dst_map->is_main_map)
  1907.             vm_map_entry_delete(src_map, src_entry->prev);
  1908.     }
  1909.  
  1910.     /*
  1911.      *    Update the physical maps as appropriate
  1912.      */
  1913.  
  1914.     if (src_map->is_main_map && dst_map->is_main_map) {
  1915.         if (src_destroy)
  1916.             pmap_remove(src_map->pmap, src_addr, src_addr + len);
  1917.     }
  1918.  
  1919.     /*
  1920.      *    Unlock the maps
  1921.      */
  1922.  
  1923.     Return: ;
  1924.  
  1925.     if (old_src_destroy)
  1926.         vm_map_delete(src_map, src_addr, src_addr + len);
  1927.  
  1928.     vm_map_unlock(src_map);
  1929.     if (src_map != dst_map)
  1930.         vm_map_unlock(dst_map);
  1931.  
  1932.     return(result);
  1933. }
  1934.  
  1935. /*
  1936.  * vmspace_fork:
  1937.  * Create a new process vmspace structure and vm_map
  1938.  * based on those of an existing process.  The new map
  1939.  * is based on the old map, according to the inheritance
  1940.  * values on the regions in that map.
  1941.  *
  1942.  * The source map must not be locked.
  1943.  */
  1944. struct vmspace *
  1945. vmspace_fork(vm1)
  1946.     register struct vmspace *vm1;
  1947. {
  1948.     register struct vmspace *vm2;
  1949.     vm_map_t    old_map = &vm1->vm_map;
  1950.     vm_map_t    new_map;
  1951.     vm_map_entry_t    old_entry;
  1952.     vm_map_entry_t    new_entry;
  1953.     pmap_t        new_pmap;
  1954.  
  1955.     vm_map_lock(old_map);
  1956.  
  1957.     vm2 = vmspace_alloc(old_map->min_offset, old_map->max_offset,
  1958.         old_map->entries_pageable);
  1959.     bcopy(&vm1->vm_startcopy, &vm2->vm_startcopy,
  1960.         (caddr_t) (vm1 + 1) - (caddr_t) &vm1->vm_startcopy);
  1961.     new_pmap = &vm2->vm_pmap;        /* XXX */
  1962.     new_map = &vm2->vm_map;            /* XXX */
  1963.  
  1964.     old_entry = old_map->header.next;
  1965.  
  1966.     while (old_entry != &old_map->header) {
  1967.         if (old_entry->is_sub_map)
  1968.             panic("vm_map_fork: encountered a submap");
  1969.  
  1970.         switch (old_entry->inheritance) {
  1971.         case VM_INHERIT_NONE:
  1972.             break;
  1973.  
  1974.         case VM_INHERIT_SHARE:
  1975.             /*
  1976.              *    If we don't already have a sharing map:
  1977.              */
  1978.  
  1979.             if (!old_entry->is_a_map) {
  1980.                  vm_map_t    new_share_map;
  1981.                 vm_map_entry_t    new_share_entry;
  1982.                 
  1983.                 /*
  1984.                  *    Create a new sharing map
  1985.                  */
  1986.                  
  1987.                 new_share_map = vm_map_create(NULL,
  1988.                             old_entry->start,
  1989.                             old_entry->end,
  1990.                             TRUE);
  1991.                 new_share_map->is_main_map = FALSE;
  1992.  
  1993.                 /*
  1994.                  *    Create the only sharing entry from the
  1995.                  *    old task map entry.
  1996.                  */
  1997.  
  1998.                 new_share_entry =
  1999.                     vm_map_entry_create(new_share_map);
  2000.                 *new_share_entry = *old_entry;
  2001.  
  2002.                 /*
  2003.                  *    Insert the entry into the new sharing
  2004.                  *    map
  2005.                  */
  2006.  
  2007.                 vm_map_entry_link(new_share_map,
  2008.                         new_share_map->header.prev,
  2009.                         new_share_entry);
  2010.  
  2011.                 /*
  2012.                  *    Fix up the task map entry to refer
  2013.                  *    to the sharing map now.
  2014.                  */
  2015.  
  2016.                 old_entry->is_a_map = TRUE;
  2017.                 old_entry->object.share_map = new_share_map;
  2018.                 old_entry->offset = old_entry->start;
  2019.             }
  2020.  
  2021.             /*
  2022.              *    Clone the entry, referencing the sharing map.
  2023.              */
  2024.  
  2025.             new_entry = vm_map_entry_create(new_map);
  2026.             *new_entry = *old_entry;
  2027.             vm_map_reference(new_entry->object.share_map);
  2028.  
  2029.             /*
  2030.              *    Insert the entry into the new map -- we
  2031.              *    know we're inserting at the end of the new
  2032.              *    map.
  2033.              */
  2034.  
  2035.             vm_map_entry_link(new_map, new_map->header.prev,
  2036.                         new_entry);
  2037.  
  2038.             /*
  2039.              *    Update the physical map
  2040.              */
  2041.  
  2042.             pmap_copy(new_map->pmap, old_map->pmap,
  2043.                 new_entry->start,
  2044.                 (old_entry->end - old_entry->start),
  2045.                 old_entry->start);
  2046.             break;
  2047.  
  2048.         case VM_INHERIT_COPY:
  2049.             /*
  2050.              *    Clone the entry and link into the map.
  2051.              */
  2052.  
  2053.             new_entry = vm_map_entry_create(new_map);
  2054.             *new_entry = *old_entry;
  2055.             new_entry->wired_count = 0;
  2056.             new_entry->object.vm_object = NULL;
  2057.             new_entry->is_a_map = FALSE;
  2058.             vm_map_entry_link(new_map, new_map->header.prev,
  2059.                             new_entry);
  2060.             if (old_entry->is_a_map) {
  2061.                 int    check;
  2062.  
  2063.                 check = vm_map_copy(new_map,
  2064.                         old_entry->object.share_map,
  2065.                         new_entry->start,
  2066.                         (vm_size_t)(new_entry->end -
  2067.                             new_entry->start),
  2068.                         old_entry->offset,
  2069.                         FALSE, FALSE);
  2070.                 if (check != KERN_SUCCESS)
  2071.                     printf("vm_map_fork: copy in share_map region failed\n");
  2072.             }
  2073.             else {
  2074.                 vm_map_copy_entry(old_map, new_map, old_entry,
  2075.                         new_entry);
  2076.             }
  2077.             break;
  2078.         }
  2079.         old_entry = old_entry->next;
  2080.     }
  2081.  
  2082.     new_map->size = old_map->size;
  2083.     vm_map_unlock(old_map);
  2084.  
  2085.     return(vm2);
  2086. }
  2087.  
  2088. /*
  2089.  *    vm_map_lookup:
  2090.  *
  2091.  *    Finds the VM object, offset, and
  2092.  *    protection for a given virtual address in the
  2093.  *    specified map, assuming a page fault of the
  2094.  *    type specified.
  2095.  *
  2096.  *    Leaves the map in question locked for read; return
  2097.  *    values are guaranteed until a vm_map_lookup_done
  2098.  *    call is performed.  Note that the map argument
  2099.  *    is in/out; the returned map must be used in
  2100.  *    the call to vm_map_lookup_done.
  2101.  *
  2102.  *    A handle (out_entry) is returned for use in
  2103.  *    vm_map_lookup_done, to make that fast.
  2104.  *
  2105.  *    If a lookup is requested with "write protection"
  2106.  *    specified, the map may be changed to perform virtual
  2107.  *    copying operations, although the data referenced will
  2108.  *    remain the same.
  2109.  */
  2110. vm_map_lookup(var_map, vaddr, fault_type, out_entry,
  2111.                 object, offset, out_prot, wired, single_use)
  2112.     vm_map_t        *var_map;    /* IN/OUT */
  2113.     register vm_offset_t    vaddr;
  2114.     register vm_prot_t    fault_type;
  2115.  
  2116.     vm_map_entry_t        *out_entry;    /* OUT */
  2117.     vm_object_t        *object;    /* OUT */
  2118.     vm_offset_t        *offset;    /* OUT */
  2119.     vm_prot_t        *out_prot;    /* OUT */
  2120.     boolean_t        *wired;        /* OUT */
  2121.     boolean_t        *single_use;    /* OUT */
  2122. {
  2123.     vm_map_t            share_map;
  2124.     vm_offset_t            share_offset;
  2125.     register vm_map_entry_t        entry;
  2126.     register vm_map_t        map = *var_map;
  2127.     register vm_prot_t        prot;
  2128.     register boolean_t        su;
  2129.  
  2130.     RetryLookup: ;
  2131.  
  2132.     /*
  2133.      *    Lookup the faulting address.
  2134.      */
  2135.  
  2136.     vm_map_lock_read(map);
  2137.  
  2138. #define    RETURN(why) \
  2139.         { \
  2140.         vm_map_unlock_read(map); \
  2141.         return(why); \
  2142.         }
  2143.  
  2144.     /*
  2145.      *    If the map has an interesting hint, try it before calling
  2146.      *    full blown lookup routine.
  2147.      */
  2148.  
  2149.     simple_lock(&map->hint_lock);
  2150.     entry = map->hint;
  2151.     simple_unlock(&map->hint_lock);
  2152.  
  2153.     *out_entry = entry;
  2154.  
  2155.     if ((entry == &map->header) ||
  2156.         (vaddr < entry->start) || (vaddr >= entry->end)) {
  2157.         vm_map_entry_t    tmp_entry;
  2158.  
  2159.         /*
  2160.          *    Entry was either not a valid hint, or the vaddr
  2161.          *    was not contained in the entry, so do a full lookup.
  2162.          */
  2163.         if (!vm_map_lookup_entry(map, vaddr, &tmp_entry))
  2164.             RETURN(KERN_INVALID_ADDRESS);
  2165.  
  2166.         entry = tmp_entry;
  2167.         *out_entry = entry;
  2168.     }
  2169.  
  2170.     /*
  2171.      *    Handle submaps.
  2172.      */
  2173.  
  2174.     if (entry->is_sub_map) {
  2175.         vm_map_t    old_map = map;
  2176.  
  2177.         *var_map = map = entry->object.sub_map;
  2178.         vm_map_unlock_read(old_map);
  2179.         goto RetryLookup;
  2180.     }
  2181.         
  2182.     /*
  2183.      *    Check whether this task is allowed to have
  2184.      *    this page.
  2185.      */
  2186.  
  2187.     prot = entry->protection;
  2188.     if ((fault_type & (prot)) != fault_type)
  2189.         RETURN(KERN_PROTECTION_FAILURE);
  2190.  
  2191.     /*
  2192.      *    If this page is not pageable, we have to get
  2193.      *    it for all possible accesses.
  2194.      */
  2195.  
  2196.     if (*wired = (entry->wired_count != 0))
  2197.         prot = fault_type = entry->protection;
  2198.  
  2199.     /*
  2200.      *    If we don't already have a VM object, track
  2201.      *    it down.
  2202.      */
  2203.  
  2204.     if (su = !entry->is_a_map) {
  2205.          share_map = map;
  2206.         share_offset = vaddr;
  2207.     }
  2208.     else {
  2209.         vm_map_entry_t    share_entry;
  2210.  
  2211.         /*
  2212.          *    Compute the sharing map, and offset into it.
  2213.          */
  2214.  
  2215.         share_map = entry->object.share_map;
  2216.         share_offset = (vaddr - entry->start) + entry->offset;
  2217.  
  2218.         /*
  2219.          *    Look for the backing store object and offset
  2220.          */
  2221.  
  2222.         vm_map_lock_read(share_map);
  2223.  
  2224.         if (!vm_map_lookup_entry(share_map, share_offset,
  2225.                     &share_entry)) {
  2226.             vm_map_unlock_read(share_map);
  2227.             RETURN(KERN_INVALID_ADDRESS);
  2228.         }
  2229.         entry = share_entry;
  2230.     }
  2231.  
  2232.     /*
  2233.      *    If the entry was copy-on-write, we either ...
  2234.      */
  2235.  
  2236.     if (entry->needs_copy) {
  2237.             /*
  2238.          *    If we want to write the page, we may as well
  2239.          *    handle that now since we've got the sharing
  2240.          *    map locked.
  2241.          *
  2242.          *    If we don't need to write the page, we just
  2243.          *    demote the permissions allowed.
  2244.          */
  2245.  
  2246.         if (fault_type & VM_PROT_WRITE) {
  2247.             /*
  2248.              *    Make a new object, and place it in the
  2249.              *    object chain.  Note that no new references
  2250.              *    have appeared -- one just moved from the
  2251.              *    share map to the new object.
  2252.              */
  2253.  
  2254.             if (lock_read_to_write(&share_map->lock)) {
  2255.                 if (share_map != map)
  2256.                     vm_map_unlock_read(map);
  2257.                 goto RetryLookup;
  2258.             }
  2259.  
  2260.             vm_object_shadow(
  2261.                 &entry->object.vm_object,
  2262.                 &entry->offset,
  2263.                 (vm_size_t) (entry->end - entry->start));
  2264.                 
  2265.             entry->needs_copy = FALSE;
  2266.             
  2267.             lock_write_to_read(&share_map->lock);
  2268.         }
  2269.         else {
  2270.             /*
  2271.              *    We're attempting to read a copy-on-write
  2272.              *    page -- don't allow writes.
  2273.              */
  2274.  
  2275.             prot &= (~VM_PROT_WRITE);
  2276.         }
  2277.     }
  2278.  
  2279.     /*
  2280.      *    Create an object if necessary.
  2281.      */
  2282.     if (entry->object.vm_object == NULL) {
  2283.  
  2284.         if (lock_read_to_write(&share_map->lock)) {
  2285.             if (share_map != map)
  2286.                 vm_map_unlock_read(map);
  2287.             goto RetryLookup;
  2288.         }
  2289.  
  2290.         entry->object.vm_object = vm_object_allocate(
  2291.                     (vm_size_t)(entry->end - entry->start));
  2292.         entry->offset = 0;
  2293.         lock_write_to_read(&share_map->lock);
  2294.     }
  2295.  
  2296.     /*
  2297.      *    Return the object/offset from this entry.  If the entry
  2298.      *    was copy-on-write or empty, it has been fixed up.
  2299.      */
  2300.  
  2301.     *offset = (share_offset - entry->start) + entry->offset;
  2302.     *object = entry->object.vm_object;
  2303.  
  2304.     /*
  2305.      *    Return whether this is the only map sharing this data.
  2306.      */
  2307.  
  2308.     if (!su) {
  2309.         simple_lock(&share_map->ref_lock);
  2310.         su = (share_map->ref_count == 1);
  2311.         simple_unlock(&share_map->ref_lock);
  2312.     }
  2313.  
  2314.     *out_prot = prot;
  2315.     *single_use = su;
  2316.  
  2317.     return(KERN_SUCCESS);
  2318.     
  2319. #undef    RETURN
  2320. }
  2321.  
  2322. /*
  2323.  *    vm_map_lookup_done:
  2324.  *
  2325.  *    Releases locks acquired by a vm_map_lookup
  2326.  *    (according to the handle returned by that lookup).
  2327.  */
  2328.  
  2329. void vm_map_lookup_done(map, entry)
  2330.     register vm_map_t    map;
  2331.     vm_map_entry_t        entry;
  2332. {
  2333.     /*
  2334.      *    If this entry references a map, unlock it first.
  2335.      */
  2336.  
  2337.     if (entry->is_a_map)
  2338.         vm_map_unlock_read(entry->object.share_map);
  2339.  
  2340.     /*
  2341.      *    Unlock the main-level map
  2342.      */
  2343.  
  2344.     vm_map_unlock_read(map);
  2345. }
  2346.  
  2347. /*
  2348.  *    Routine:    vm_map_simplify
  2349.  *    Purpose:
  2350.  *        Attempt to simplify the map representation in
  2351.  *        the vicinity of the given starting address.
  2352.  *    Note:
  2353.  *        This routine is intended primarily to keep the
  2354.  *        kernel maps more compact -- they generally don't
  2355.  *        benefit from the "expand a map entry" technology
  2356.  *        at allocation time because the adjacent entry
  2357.  *        is often wired down.
  2358.  */
  2359. void vm_map_simplify(map, start)
  2360.     vm_map_t    map;
  2361.     vm_offset_t    start;
  2362. {
  2363.     vm_map_entry_t    this_entry;
  2364.     vm_map_entry_t    prev_entry;
  2365.  
  2366.     vm_map_lock(map);
  2367.     if (
  2368.         (vm_map_lookup_entry(map, start, &this_entry)) &&
  2369.         ((prev_entry = this_entry->prev) != &map->header) &&
  2370.  
  2371.         (prev_entry->end == start) &&
  2372.         (map->is_main_map) &&
  2373.  
  2374.         (prev_entry->is_a_map == FALSE) &&
  2375.         (prev_entry->is_sub_map == FALSE) &&
  2376.  
  2377.         (this_entry->is_a_map == FALSE) &&
  2378.         (this_entry->is_sub_map == FALSE) &&
  2379.  
  2380.         (prev_entry->inheritance == this_entry->inheritance) &&
  2381.         (prev_entry->protection == this_entry->protection) &&
  2382.         (prev_entry->max_protection == this_entry->max_protection) &&
  2383.         (prev_entry->wired_count == this_entry->wired_count) &&
  2384.         
  2385.         (prev_entry->copy_on_write == this_entry->copy_on_write) &&
  2386.         (prev_entry->needs_copy == this_entry->needs_copy) &&
  2387.         
  2388.         (prev_entry->object.vm_object == this_entry->object.vm_object) &&
  2389.         ((prev_entry->offset + (prev_entry->end - prev_entry->start))
  2390.              == this_entry->offset)
  2391.     ) {
  2392.         if (map->first_free == this_entry)
  2393.             map->first_free = prev_entry;
  2394.  
  2395.         SAVE_HINT(map, prev_entry);
  2396.         vm_map_entry_unlink(map, this_entry);
  2397.         prev_entry->end = this_entry->end;
  2398.          vm_object_deallocate(this_entry->object.vm_object);
  2399.         vm_map_entry_dispose(map, this_entry);
  2400.     }
  2401.     vm_map_unlock(map);
  2402. }
  2403.  
  2404. /*
  2405.  *    vm_map_print:    [ debug ]
  2406.  */
  2407. void vm_map_print(map, full)
  2408.     register vm_map_t    map;
  2409.     boolean_t        full;
  2410. {
  2411.     register vm_map_entry_t    entry;
  2412.     extern int indent;
  2413.  
  2414.     iprintf("%s map 0x%x: pmap=0x%x,ref=%d,nentries=%d,version=%d\n",
  2415.         (map->is_main_map ? "Task" : "Share"),
  2416.          (int) map, (int) (map->pmap), map->ref_count, map->nentries,
  2417.         map->timestamp);
  2418.  
  2419.     if (!full && indent)
  2420.         return;
  2421.  
  2422.     indent += 2;
  2423.     for (entry = map->header.next; entry != &map->header;
  2424.                 entry = entry->next) {
  2425.         iprintf("map entry 0x%x: start=0x%x, end=0x%x, ",
  2426.             (int) entry, (int) entry->start, (int) entry->end);
  2427.         if (map->is_main_map) {
  2428.                  static char *inheritance_name[4] =
  2429.                 { "share", "copy", "none", "donate_copy"};
  2430.             printf("prot=%x/%x/%s, ",
  2431.                 entry->protection,
  2432.                 entry->max_protection,
  2433.                 inheritance_name[entry->inheritance]);
  2434.             if (entry->wired_count != 0)
  2435.                 printf("wired, ");
  2436.         }
  2437.  
  2438.         if (entry->is_a_map || entry->is_sub_map) {
  2439.              printf("share=0x%x, offset=0x%x\n",
  2440.                 (int) entry->object.share_map,
  2441.                 (int) entry->offset);
  2442.             if ((entry->prev == &map->header) ||
  2443.                 (!entry->prev->is_a_map) ||
  2444.                 (entry->prev->object.share_map !=
  2445.                  entry->object.share_map)) {
  2446.                 indent += 2;
  2447.                 vm_map_print(entry->object.share_map, full);
  2448.                 indent -= 2;
  2449.             }
  2450.                 
  2451.         }
  2452.         else {
  2453.             printf("object=0x%x, offset=0x%x",
  2454.                 (int) entry->object.vm_object,
  2455.                 (int) entry->offset);
  2456.             if (entry->copy_on_write)
  2457.                 printf(", copy (%s)",
  2458.                        entry->needs_copy ? "needed" : "done");
  2459.             printf("\n");
  2460.  
  2461.             if ((entry->prev == &map->header) ||
  2462.                 (entry->prev->is_a_map) ||
  2463.                 (entry->prev->object.vm_object !=
  2464.                  entry->object.vm_object)) {
  2465.                 indent += 2;
  2466.                 vm_object_print(entry->object.vm_object, full);
  2467.                 indent -= 2;
  2468.             }
  2469.         }
  2470.     }
  2471.     indent -= 2;
  2472. }
  2473.