762c7744f07b7d561e2f7ec3fc634b36f945e0c1
[dragonfly.git] / sys / vm / vm_map.c
1 /*
2  * Copyright (c) 1991, 1993
3  *      The Regents of the University of California.  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  *      from: @(#)vm_map.c      8.3 (Berkeley) 1/12/94
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  * $FreeBSD: src/sys/vm/vm_map.c,v 1.187.2.19 2003/05/27 00:47:02 alc Exp $
65  * $DragonFly: src/sys/vm/vm_map.c,v 1.56 2007/04/29 18:25:41 dillon Exp $
66  */
67
68 /*
69  *      Virtual memory mapping module.
70  */
71
72 #include <sys/param.h>
73 #include <sys/systm.h>
74 #include <sys/kernel.h>
75 #include <sys/proc.h>
76 #include <sys/lock.h>
77 #include <sys/vmmeter.h>
78 #include <sys/mman.h>
79 #include <sys/vnode.h>
80 #include <sys/resourcevar.h>
81 #include <sys/shm.h>
82 #include <sys/tree.h>
83 #include <sys/malloc.h>
84
85 #include <vm/vm.h>
86 #include <vm/vm_param.h>
87 #include <vm/pmap.h>
88 #include <vm/vm_map.h>
89 #include <vm/vm_page.h>
90 #include <vm/vm_object.h>
91 #include <vm/vm_pager.h>
92 #include <vm/vm_kern.h>
93 #include <vm/vm_extern.h>
94 #include <vm/swap_pager.h>
95 #include <vm/vm_zone.h>
96
97 #include <sys/thread2.h>
98 #include <sys/sysref2.h>
99
100 /*
101  *      Virtual memory maps provide for the mapping, protection,
102  *      and sharing of virtual memory objects.  In addition,
103  *      this module provides for an efficient virtual copy of
104  *      memory from one map to another.
105  *
106  *      Synchronization is required prior to most operations.
107  *
108  *      Maps consist of an ordered doubly-linked list of simple
109  *      entries; a single hint is used to speed up lookups.
110  *
111  *      Since portions of maps are specified by start/end addresses,
112  *      which may not align with existing map entries, all
113  *      routines merely "clip" entries to these start/end values.
114  *      [That is, an entry is split into two, bordering at a
115  *      start or end value.]  Note that these clippings may not
116  *      always be necessary (as the two resulting entries are then
117  *      not changed); however, the clipping is done for convenience.
118  *
119  *      As mentioned above, virtual copy operations are performed
120  *      by copying VM object references from one map to
121  *      another, and then marking both regions as copy-on-write.
122  */
123
124 static void vmspace_terminate(struct vmspace *vm);
125 static void vmspace_dtor(void *obj, void *private);
126
127 MALLOC_DEFINE(M_VMSPACE, "vmspace", "vmspace objcache backingstore");
128
129 struct sysref_class vmspace_sysref_class = {
130         .name =         "vmspace",
131         .mtype =        M_VMSPACE,
132         .proto =        SYSREF_PROTO_VMSPACE,
133         .offset =       offsetof(struct vmspace, vm_sysref),
134         .objsize =      sizeof(struct vmspace),
135         .mag_capacity = 32,
136         .flags = SRC_MANAGEDINIT,
137         .dtor = vmspace_dtor,
138         .ops = {
139                 .terminate = (sysref_terminate_func_t)vmspace_terminate
140         }
141 };
142
143 #define VMEPERCPU       2
144
145 static struct vm_zone mapentzone_store, mapzone_store;
146 static vm_zone_t mapentzone, mapzone;
147 static struct vm_object mapentobj, mapobj;
148
149 static struct vm_map_entry map_entry_init[MAX_MAPENT];
150 static struct vm_map_entry cpu_map_entry_init[MAXCPU][VMEPERCPU];
151 static struct vm_map map_init[MAX_KMAP];
152
153 static void vm_map_entry_shadow(vm_map_entry_t entry);
154 static vm_map_entry_t vm_map_entry_create(vm_map_t map, int *);
155 static void vm_map_entry_dispose (vm_map_t map, vm_map_entry_t entry, int *);
156 static void _vm_map_clip_end (vm_map_t, vm_map_entry_t, vm_offset_t, int *);
157 static void _vm_map_clip_start (vm_map_t, vm_map_entry_t, vm_offset_t, int *);
158 static void vm_map_entry_delete (vm_map_t, vm_map_entry_t, int *);
159 static void vm_map_entry_unwire (vm_map_t, vm_map_entry_t);
160 static void vm_map_copy_entry (vm_map_t, vm_map_t, vm_map_entry_t,
161                 vm_map_entry_t);
162 static void vm_map_split (vm_map_entry_t);
163 static void vm_map_unclip_range (vm_map_t map, vm_map_entry_t start_entry, vm_offset_t start, vm_offset_t end, int *count, int flags);
164
165 /*
166  *      vm_map_startup:
167  *
168  *      Initialize the vm_map module.  Must be called before
169  *      any other vm_map routines.
170  *
171  *      Map and entry structures are allocated from the general
172  *      purpose memory pool with some exceptions:
173  *
174  *      - The kernel map and kmem submap are allocated statically.
175  *      - Kernel map entries are allocated out of a static pool.
176  *
177  *      These restrictions are necessary since malloc() uses the
178  *      maps and requires map entries.
179  */
180 void
181 vm_map_startup(void)
182 {
183         mapzone = &mapzone_store;
184         zbootinit(mapzone, "MAP", sizeof (struct vm_map),
185                 map_init, MAX_KMAP);
186         mapentzone = &mapentzone_store;
187         zbootinit(mapentzone, "MAP ENTRY", sizeof (struct vm_map_entry),
188                 map_entry_init, MAX_MAPENT);
189 }
190
191 /*
192  *      vm_init2 - called prior to any vmspace allocations
193  */
194 void
195 vm_init2(void) 
196 {
197         zinitna(mapentzone, &mapentobj, NULL, 0, 0, 
198                 ZONE_USE_RESERVE | ZONE_SPECIAL, 1);
199         zinitna(mapzone, &mapobj, NULL, 0, 0, 0, 1);
200         pmap_init2();
201         vm_object_init2();
202 }
203
204
205 /*
206  * Red black tree functions
207  */
208 static int rb_vm_map_compare(vm_map_entry_t a, vm_map_entry_t b);
209 RB_GENERATE(vm_map_rb_tree, vm_map_entry, rb_entry, rb_vm_map_compare);
210
211 /* a->start is address, and the only field has to be initialized */
212 static int
213 rb_vm_map_compare(vm_map_entry_t a, vm_map_entry_t b)
214 {
215         if (a->start < b->start)
216                 return(-1);
217         else if (a->start > b->start)
218                 return(1);
219         return(0);
220 }
221
222 /*
223  * Allocate a vmspace structure, including a vm_map and pmap.
224  * Initialize numerous fields.  While the initial allocation is zerod,
225  * subsequence reuse from the objcache leaves elements of the structure
226  * intact (particularly the pmap), so portions must be zerod.
227  *
228  * The structure is not considered activated until we call sysref_activate().
229  */
230 struct vmspace *
231 vmspace_alloc(vm_offset_t min, vm_offset_t max)
232 {
233         struct vmspace *vm;
234
235         vm = sysref_alloc(&vmspace_sysref_class);
236         bzero(&vm->vm_startcopy,
237               (char *)&vm->vm_endcopy - (char *)&vm->vm_startcopy);
238         vm_map_init(&vm->vm_map, min, max, NULL);
239         pmap_pinit(vmspace_pmap(vm));           /* (some fields reused) */
240         vm->vm_map.pmap = vmspace_pmap(vm);             /* XXX */
241         vm->vm_shm = NULL;
242         vm->vm_exitingcnt = 0;
243         cpu_vmspace_alloc(vm);
244         sysref_activate(&vm->vm_sysref);
245         return (vm);
246 }
247
248 /*
249  * dtor function - Some elements of the pmap are retained in the
250  * free-cached vmspaces to improve performance.  We have to clean them up
251  * here before returning the vmspace to the memory pool.
252  */
253 static void
254 vmspace_dtor(void *obj, void *private)
255 {
256         struct vmspace *vm = obj;
257
258         pmap_puninit(vmspace_pmap(vm));
259 }
260
261 /*
262  * Called in two cases: 
263  *
264  * (1) When the last sysref is dropped, but exitingcnt might still be
265  *     non-zero.
266  *
267  * (2) When there are no sysrefs (i.e. refcnt is negative) left and the
268  *     exitingcnt becomes zero
269  *
270  * sysref will not scrap the object until we call sysref_put() once more
271  * after the last ref has been dropped.
272  */
273 static void
274 vmspace_terminate(struct vmspace *vm)
275 {
276         int count;
277
278         /*
279          * If exitingcnt is non-zero we can't get rid of the entire vmspace
280          * yet, but we can scrap user memory.
281          */
282         if (vm->vm_exitingcnt) {
283                 shmexit(vm);
284                 pmap_remove_pages(vmspace_pmap(vm), VM_MIN_USER_ADDRESS,
285                                   VM_MAX_USER_ADDRESS);
286                 vm_map_remove(&vm->vm_map, VM_MIN_USER_ADDRESS,
287                               VM_MAX_USER_ADDRESS);
288
289                 return;
290         }
291         cpu_vmspace_free(vm);
292
293         /*
294          * Make sure any SysV shm is freed, it might not have in
295          * exit1()
296          */
297         shmexit(vm);
298
299         KKASSERT(vm->vm_upcalls == NULL);
300
301         /*
302          * Lock the map, to wait out all other references to it.
303          * Delete all of the mappings and pages they hold, then call
304          * the pmap module to reclaim anything left.
305          */
306         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
307         vm_map_lock(&vm->vm_map);
308         vm_map_delete(&vm->vm_map, vm->vm_map.min_offset,
309                 vm->vm_map.max_offset, &count);
310         vm_map_unlock(&vm->vm_map);
311         vm_map_entry_release(count);
312
313         pmap_release(vmspace_pmap(vm));
314         sysref_put(&vm->vm_sysref);
315 }
316
317 /*
318  * This is called in the wait*() handling code.  The vmspace can be terminated
319  * after the last wait is finished using it.
320  */
321 void
322 vmspace_exitfree(struct proc *p)
323 {
324         struct vmspace *vm;
325
326         vm = p->p_vmspace;
327         p->p_vmspace = NULL;
328
329         if (--vm->vm_exitingcnt == 0 && sysref_isinactive(&vm->vm_sysref))
330                 vmspace_terminate(vm);
331 }
332
333 /*
334  * vmspace_swap_count() - count the approximate swap useage in pages for a
335  *                        vmspace.
336  *
337  *      Swap useage is determined by taking the proportional swap used by
338  *      VM objects backing the VM map.  To make up for fractional losses,
339  *      if the VM object has any swap use at all the associated map entries
340  *      count for at least 1 swap page.
341  */
342 int
343 vmspace_swap_count(struct vmspace *vmspace)
344 {
345         vm_map_t map = &vmspace->vm_map;
346         vm_map_entry_t cur;
347         vm_object_t object;
348         int count = 0;
349         int n;
350
351         for (cur = map->header.next; cur != &map->header; cur = cur->next) {
352                 switch(cur->maptype) {
353                 case VM_MAPTYPE_NORMAL:
354                 case VM_MAPTYPE_VPAGETABLE:
355                         if ((object = cur->object.vm_object) == NULL)
356                                 break;
357                         if (object->type != OBJT_SWAP)
358                                 break;
359                         n = (cur->end - cur->start) / PAGE_SIZE;
360                         if (object->un_pager.swp.swp_bcount) {
361                                 count += object->un_pager.swp.swp_bcount *
362                                     SWAP_META_PAGES * n / object->size + 1;
363                         }
364                         break;
365                 default:
366                         break;
367                 }
368         }
369         return(count);
370 }
371
372
373 /*
374  *      vm_map_create:
375  *
376  *      Creates and returns a new empty VM map with
377  *      the given physical map structure, and having
378  *      the given lower and upper address bounds.
379  */
380 vm_map_t
381 vm_map_create(vm_map_t result, pmap_t pmap, vm_offset_t min, vm_offset_t max)
382 {
383         if (result == NULL)
384                 result = zalloc(mapzone);
385         vm_map_init(result, min, max, pmap);
386         return (result);
387 }
388
389 /*
390  * Initialize an existing vm_map structure
391  * such as that in the vmspace structure.
392  * The pmap is set elsewhere.
393  */
394 void
395 vm_map_init(struct vm_map *map, vm_offset_t min, vm_offset_t max, pmap_t pmap)
396 {
397         map->header.next = map->header.prev = &map->header;
398         RB_INIT(&map->rb_root);
399         map->nentries = 0;
400         map->size = 0;
401         map->system_map = 0;
402         map->infork = 0;
403         map->min_offset = min;
404         map->max_offset = max;
405         map->pmap = pmap;
406         map->first_free = &map->header;
407         map->hint = &map->header;
408         map->timestamp = 0;
409         lockinit(&map->lock, "thrd_sleep", 0, 0);
410 }
411
412 /*
413  * Shadow the vm_map_entry's object.  This typically needs to be done when
414  * a write fault is taken on an entry which had previously been cloned by
415  * fork().  The shared object (which might be NULL) must become private so
416  * we add a shadow layer above it.
417  *
418  * Object allocation for anonymous mappings is defered as long as possible.
419  * When creating a shadow, however, the underlying object must be instantiated
420  * so it can be shared.
421  *
422  * If the map segment is governed by a virtual page table then it is
423  * possible to address offsets beyond the mapped area.  Just allocate
424  * a maximally sized object for this case.
425  */
426 static
427 void
428 vm_map_entry_shadow(vm_map_entry_t entry)
429 {
430         if (entry->maptype == VM_MAPTYPE_VPAGETABLE) {
431                 vm_object_shadow(&entry->object.vm_object, &entry->offset,
432                                  0x7FFFFFFF);   /* XXX */
433         } else {
434                 vm_object_shadow(&entry->object.vm_object, &entry->offset,
435                                  atop(entry->end - entry->start));
436         }
437         entry->eflags &= ~MAP_ENTRY_NEEDS_COPY;
438 }
439
440 /*
441  * Allocate an object for a vm_map_entry.
442  *
443  * Object allocation for anonymous mappings is defered as long as possible.
444  * This function is called when we can defer no longer, generally when a map
445  * entry might be split or forked or takes a page fault.
446  *
447  * If the map segment is governed by a virtual page table then it is
448  * possible to address offsets beyond the mapped area.  Just allocate
449  * a maximally sized object for this case.
450  */
451 void 
452 vm_map_entry_allocate_object(vm_map_entry_t entry)
453 {
454         vm_object_t obj;
455
456         if (entry->maptype == VM_MAPTYPE_VPAGETABLE) {
457                 obj = vm_object_allocate(OBJT_DEFAULT, 0x7FFFFFFF); /* XXX */
458         } else {
459                 obj = vm_object_allocate(OBJT_DEFAULT,
460                                          atop(entry->end - entry->start));
461         }
462         entry->object.vm_object = obj;
463         entry->offset = 0;
464 }
465
466 /*
467  *      vm_map_entry_reserve_cpu_init:
468  *
469  *      Set an initial negative count so the first attempt to reserve
470  *      space preloads a bunch of vm_map_entry's for this cpu.  Also
471  *      pre-allocate 2 vm_map_entries which will be needed by zalloc() to
472  *      map a new page for vm_map_entry structures.  SMP systems are
473  *      particularly sensitive.
474  *
475  *      This routine is called in early boot so we cannot just call
476  *      vm_map_entry_reserve().
477  *
478  *      May be called for a gd other then mycpu, but may only be called
479  *      during early boot.
480  */
481 void
482 vm_map_entry_reserve_cpu_init(globaldata_t gd)
483 {
484         vm_map_entry_t entry;
485         int i;
486
487         gd->gd_vme_avail -= MAP_RESERVE_COUNT * 2;
488         entry = &cpu_map_entry_init[gd->gd_cpuid][0];
489         for (i = 0; i < VMEPERCPU; ++i, ++entry) {
490                 entry->next = gd->gd_vme_base;
491                 gd->gd_vme_base = entry;
492         }
493 }
494
495 /*
496  *      vm_map_entry_reserve:
497  *
498  *      Reserves vm_map_entry structures so code later on can manipulate
499  *      map_entry structures within a locked map without blocking trying
500  *      to allocate a new vm_map_entry.
501  */
502 int
503 vm_map_entry_reserve(int count)
504 {
505         struct globaldata *gd = mycpu;
506         vm_map_entry_t entry;
507
508         crit_enter();
509
510         /*
511          * Make sure we have enough structures in gd_vme_base to handle
512          * the reservation request.
513          */
514         while (gd->gd_vme_avail < count) {
515                 entry = zalloc(mapentzone);
516                 entry->next = gd->gd_vme_base;
517                 gd->gd_vme_base = entry;
518                 ++gd->gd_vme_avail;
519         }
520         gd->gd_vme_avail -= count;
521         crit_exit();
522         return(count);
523 }
524
525 /*
526  *      vm_map_entry_release:
527  *
528  *      Releases previously reserved vm_map_entry structures that were not
529  *      used.  If we have too much junk in our per-cpu cache clean some of
530  *      it out.
531  */
532 void
533 vm_map_entry_release(int count)
534 {
535         struct globaldata *gd = mycpu;
536         vm_map_entry_t entry;
537
538         crit_enter();
539         gd->gd_vme_avail += count;
540         while (gd->gd_vme_avail > MAP_RESERVE_SLOP) {
541                 entry = gd->gd_vme_base;
542                 KKASSERT(entry != NULL);
543                 gd->gd_vme_base = entry->next;
544                 --gd->gd_vme_avail;
545                 crit_exit();
546                 zfree(mapentzone, entry);
547                 crit_enter();
548         }
549         crit_exit();
550 }
551
552 /*
553  *      vm_map_entry_kreserve:
554  *
555  *      Reserve map entry structures for use in kernel_map itself.  These
556  *      entries have *ALREADY* been reserved on a per-cpu basis when the map
557  *      was inited.  This function is used by zalloc() to avoid a recursion
558  *      when zalloc() itself needs to allocate additional kernel memory.
559  *
560  *      This function works like the normal reserve but does not load the
561  *      vm_map_entry cache (because that would result in an infinite
562  *      recursion).  Note that gd_vme_avail may go negative.  This is expected.
563  *
564  *      Any caller of this function must be sure to renormalize after 
565  *      potentially eating entries to ensure that the reserve supply
566  *      remains intact.
567  */
568 int
569 vm_map_entry_kreserve(int count)
570 {
571         struct globaldata *gd = mycpu;
572
573         crit_enter();
574         gd->gd_vme_avail -= count;
575         crit_exit();
576         KASSERT(gd->gd_vme_base != NULL, ("no reserved entries left, gd_vme_avail = %d\n", gd->gd_vme_avail));
577         return(count);
578 }
579
580 /*
581  *      vm_map_entry_krelease:
582  *
583  *      Release previously reserved map entries for kernel_map.  We do not
584  *      attempt to clean up like the normal release function as this would
585  *      cause an unnecessary (but probably not fatal) deep procedure call.
586  */
587 void
588 vm_map_entry_krelease(int count)
589 {
590         struct globaldata *gd = mycpu;
591
592         crit_enter();
593         gd->gd_vme_avail += count;
594         crit_exit();
595 }
596
597 /*
598  *      vm_map_entry_create:    [ internal use only ]
599  *
600  *      Allocates a VM map entry for insertion.  No entry fields are filled 
601  *      in.
602  *
603  *      This routine may be called from an interrupt thread but not a FAST
604  *      interrupt.  This routine may recurse the map lock.
605  */
606 static vm_map_entry_t
607 vm_map_entry_create(vm_map_t map, int *countp)
608 {
609         struct globaldata *gd = mycpu;
610         vm_map_entry_t entry;
611
612         KKASSERT(*countp > 0);
613         --*countp;
614         crit_enter();
615         entry = gd->gd_vme_base;
616         KASSERT(entry != NULL, ("gd_vme_base NULL! count %d", *countp));
617         gd->gd_vme_base = entry->next;
618         crit_exit();
619         return(entry);
620 }
621
622 /*
623  *      vm_map_entry_dispose:   [ internal use only ]
624  *
625  *      Dispose of a vm_map_entry that is no longer being referenced.  This
626  *      function may be called from an interrupt.
627  */
628 static void
629 vm_map_entry_dispose(vm_map_t map, vm_map_entry_t entry, int *countp)
630 {
631         struct globaldata *gd = mycpu;
632
633         KKASSERT(map->hint != entry);
634         KKASSERT(map->first_free != entry);
635
636         ++*countp;
637         crit_enter();
638         entry->next = gd->gd_vme_base;
639         gd->gd_vme_base = entry;
640         crit_exit();
641 }
642
643
644 /*
645  *      vm_map_entry_{un,}link:
646  *
647  *      Insert/remove entries from maps.
648  */
649 static __inline void
650 vm_map_entry_link(vm_map_t map,
651                   vm_map_entry_t after_where,
652                   vm_map_entry_t entry)
653 {
654         map->nentries++;
655         entry->prev = after_where;
656         entry->next = after_where->next;
657         entry->next->prev = entry;
658         after_where->next = entry;
659         if (vm_map_rb_tree_RB_INSERT(&map->rb_root, entry))
660                 panic("vm_map_entry_link: dup addr map %p ent %p", map, entry);
661 }
662
663 static __inline void
664 vm_map_entry_unlink(vm_map_t map,
665                     vm_map_entry_t entry)
666 {
667         vm_map_entry_t prev;
668         vm_map_entry_t next;
669
670         if (entry->eflags & MAP_ENTRY_IN_TRANSITION)
671                 panic("vm_map_entry_unlink: attempt to mess with locked entry! %p", entry);
672         prev = entry->prev;
673         next = entry->next;
674         next->prev = prev;
675         prev->next = next;
676         vm_map_rb_tree_RB_REMOVE(&map->rb_root, entry);
677         map->nentries--;
678 }
679
680 /*
681  *      vm_map_lookup_entry:    [ internal use only ]
682  *
683  *      Finds the map entry containing (or
684  *      immediately preceding) the specified address
685  *      in the given map; the entry is returned
686  *      in the "entry" parameter.  The boolean
687  *      result indicates whether the address is
688  *      actually contained in the map.
689  */
690 boolean_t
691 vm_map_lookup_entry(vm_map_t map, vm_offset_t address,
692     vm_map_entry_t *entry /* OUT */)
693 {
694         vm_map_entry_t tmp;
695         vm_map_entry_t last;
696
697 #if 0
698         /*
699          * XXX TEMPORARILY DISABLED.  For some reason our attempt to revive
700          * the hint code with the red-black lookup meets with system crashes
701          * and lockups.  We do not yet know why.
702          *
703          * It is possible that the problem is related to the setting
704          * of the hint during map_entry deletion, in the code specified
705          * at the GGG comment later on in this file.
706          */
707         /*
708          * Quickly check the cached hint, there's a good chance of a match.
709          */
710         if (map->hint != &map->header) {
711                 tmp = map->hint;
712                 if (address >= tmp->start && address < tmp->end) {
713                         *entry = tmp;
714                         return(TRUE);
715                 }
716         }
717 #endif
718
719         /*
720          * Locate the record from the top of the tree.  'last' tracks the
721          * closest prior record and is returned if no match is found, which
722          * in binary tree terms means tracking the most recent right-branch
723          * taken.  If there is no prior record, &map->header is returned.
724          */
725         last = &map->header;
726         tmp = RB_ROOT(&map->rb_root);
727
728         while (tmp) {
729                 if (address >= tmp->start) {
730                         if (address < tmp->end) {
731                                 *entry = tmp;
732                                 map->hint = tmp;
733                                 return(TRUE);
734                         }
735                         last = tmp;
736                         tmp = RB_RIGHT(tmp, rb_entry);
737                 } else {
738                         tmp = RB_LEFT(tmp, rb_entry);
739                 }
740         }
741         *entry = last;
742         return (FALSE);
743 }
744
745 /*
746  *      vm_map_insert:
747  *
748  *      Inserts the given whole VM object into the target
749  *      map at the specified address range.  The object's
750  *      size should match that of the address range.
751  *
752  *      Requires that the map be locked, and leaves it so.  Requires that
753  *      sufficient vm_map_entry structures have been reserved and tracks
754  *      the use via countp.
755  *
756  *      If object is non-NULL, ref count must be bumped by caller
757  *      prior to making call to account for the new entry.
758  */
759 int
760 vm_map_insert(vm_map_t map, int *countp,
761               vm_object_t object, vm_ooffset_t offset,
762               vm_offset_t start, vm_offset_t end,
763               vm_maptype_t maptype,
764               vm_prot_t prot, vm_prot_t max,
765               int cow)
766 {
767         vm_map_entry_t new_entry;
768         vm_map_entry_t prev_entry;
769         vm_map_entry_t temp_entry;
770         vm_eflags_t protoeflags;
771
772         /*
773          * Check that the start and end points are not bogus.
774          */
775
776         if ((start < map->min_offset) || (end > map->max_offset) ||
777             (start >= end))
778                 return (KERN_INVALID_ADDRESS);
779
780         /*
781          * Find the entry prior to the proposed starting address; if it's part
782          * of an existing entry, this range is bogus.
783          */
784
785         if (vm_map_lookup_entry(map, start, &temp_entry))
786                 return (KERN_NO_SPACE);
787
788         prev_entry = temp_entry;
789
790         /*
791          * Assert that the next entry doesn't overlap the end point.
792          */
793
794         if ((prev_entry->next != &map->header) &&
795             (prev_entry->next->start < end))
796                 return (KERN_NO_SPACE);
797
798         protoeflags = 0;
799
800         if (cow & MAP_COPY_ON_WRITE)
801                 protoeflags |= MAP_ENTRY_COW|MAP_ENTRY_NEEDS_COPY;
802
803         if (cow & MAP_NOFAULT) {
804                 protoeflags |= MAP_ENTRY_NOFAULT;
805
806                 KASSERT(object == NULL,
807                         ("vm_map_insert: paradoxical MAP_NOFAULT request"));
808         }
809         if (cow & MAP_DISABLE_SYNCER)
810                 protoeflags |= MAP_ENTRY_NOSYNC;
811         if (cow & MAP_DISABLE_COREDUMP)
812                 protoeflags |= MAP_ENTRY_NOCOREDUMP;
813
814         if (object) {
815                 /*
816                  * When object is non-NULL, it could be shared with another
817                  * process.  We have to set or clear OBJ_ONEMAPPING 
818                  * appropriately.
819                  */
820                 if ((object->ref_count > 1) || (object->shadow_count != 0)) {
821                         vm_object_clear_flag(object, OBJ_ONEMAPPING);
822                 }
823         }
824         else if ((prev_entry != &map->header) &&
825                  (prev_entry->eflags == protoeflags) &&
826                  (prev_entry->end == start) &&
827                  (prev_entry->wired_count == 0) &&
828                  prev_entry->maptype == maptype &&
829                  ((prev_entry->object.vm_object == NULL) ||
830                   vm_object_coalesce(prev_entry->object.vm_object,
831                                      OFF_TO_IDX(prev_entry->offset),
832                                      (vm_size_t)(prev_entry->end - prev_entry->start),
833                                      (vm_size_t)(end - prev_entry->end)))) {
834                 /*
835                  * We were able to extend the object.  Determine if we
836                  * can extend the previous map entry to include the 
837                  * new range as well.
838                  */
839                 if ((prev_entry->inheritance == VM_INHERIT_DEFAULT) &&
840                     (prev_entry->protection == prot) &&
841                     (prev_entry->max_protection == max)) {
842                         map->size += (end - prev_entry->end);
843                         prev_entry->end = end;
844                         vm_map_simplify_entry(map, prev_entry, countp);
845                         return (KERN_SUCCESS);
846                 }
847
848                 /*
849                  * If we can extend the object but cannot extend the
850                  * map entry, we have to create a new map entry.  We
851                  * must bump the ref count on the extended object to
852                  * account for it.  object may be NULL.
853                  */
854                 object = prev_entry->object.vm_object;
855                 offset = prev_entry->offset +
856                         (prev_entry->end - prev_entry->start);
857                 vm_object_reference(object);
858         }
859
860         /*
861          * NOTE: if conditionals fail, object can be NULL here.  This occurs
862          * in things like the buffer map where we manage kva but do not manage
863          * backing objects.
864          */
865
866         /*
867          * Create a new entry
868          */
869
870         new_entry = vm_map_entry_create(map, countp);
871         new_entry->start = start;
872         new_entry->end = end;
873
874         new_entry->maptype = maptype;
875         new_entry->eflags = protoeflags;
876         new_entry->object.vm_object = object;
877         new_entry->offset = offset;
878         new_entry->aux.master_pde = 0;
879
880         new_entry->inheritance = VM_INHERIT_DEFAULT;
881         new_entry->protection = prot;
882         new_entry->max_protection = max;
883         new_entry->wired_count = 0;
884
885         /*
886          * Insert the new entry into the list
887          */
888
889         vm_map_entry_link(map, prev_entry, new_entry);
890         map->size += new_entry->end - new_entry->start;
891
892         /*
893          * Update the free space hint
894          */
895         if ((map->first_free == prev_entry) &&
896             (prev_entry->end >= new_entry->start)) {
897                 map->first_free = new_entry;
898         }
899
900 #if 0
901         /*
902          * Temporarily removed to avoid MAP_STACK panic, due to
903          * MAP_STACK being a huge hack.  Will be added back in
904          * when MAP_STACK (and the user stack mapping) is fixed.
905          */
906         /*
907          * It may be possible to simplify the entry
908          */
909         vm_map_simplify_entry(map, new_entry, countp);
910 #endif
911
912         /*
913          * Try to pre-populate the page table.  Mappings governed by virtual
914          * page tables cannot be prepopulated without a lot of work, so
915          * don't try.
916          */
917         if ((cow & (MAP_PREFAULT|MAP_PREFAULT_PARTIAL)) &&
918             maptype != VM_MAPTYPE_VPAGETABLE) {
919                 pmap_object_init_pt(map->pmap, start, prot,
920                                     object, OFF_TO_IDX(offset), end - start,
921                                     cow & MAP_PREFAULT_PARTIAL);
922         }
923
924         return (KERN_SUCCESS);
925 }
926
927 /*
928  * Find sufficient space for `length' bytes in the given map, starting at
929  * `start'.  The map must be locked.  Returns 0 on success, 1 on no space.
930  *
931  * This function will returned an arbitrarily aligned pointer.  If no
932  * particular alignment is required you should pass align as 1.  Note that
933  * the map may return PAGE_SIZE aligned pointers if all the lengths used in
934  * the map are a multiple of PAGE_SIZE, even if you pass a smaller align
935  * argument.
936  *
937  * 'align' should be a power of 2 but is not required to be.
938  */
939 int
940 vm_map_findspace(
941         vm_map_t map,
942         vm_offset_t start,
943         vm_size_t length,
944         vm_offset_t align,
945         vm_offset_t *addr)
946 {
947         vm_map_entry_t entry, next;
948         vm_offset_t end;
949         vm_offset_t align_mask;
950
951         if (start < map->min_offset)
952                 start = map->min_offset;
953         if (start > map->max_offset)
954                 return (1);
955
956         /*
957          * If the alignment is not a power of 2 we will have to use
958          * a mod/division, set align_mask to a special value.
959          */
960         if ((align | (align - 1)) + 1 != (align << 1))
961                 align_mask = (vm_offset_t)-1;
962         else
963                 align_mask = align - 1;
964
965 retry:
966         /*
967          * Look for the first possible address; if there's already something
968          * at this address, we have to start after it.
969          */
970         if (start == map->min_offset) {
971                 if ((entry = map->first_free) != &map->header)
972                         start = entry->end;
973         } else {
974                 vm_map_entry_t tmp;
975
976                 if (vm_map_lookup_entry(map, start, &tmp))
977                         start = tmp->end;
978                 entry = tmp;
979         }
980
981         /*
982          * Look through the rest of the map, trying to fit a new region in the
983          * gap between existing regions, or after the very last region.
984          */
985         for (;; start = (entry = next)->end) {
986                 /*
987                  * Adjust the proposed start by the requested alignment,
988                  * be sure that we didn't wrap the address.
989                  */
990                 if (align_mask == (vm_offset_t)-1)
991                         end = ((start + align - 1) / align) * align;
992                 else
993                         end = (start + align_mask) & ~align_mask;
994                 if (end < start)
995                         return (1);
996                 start = end;
997                 /*
998                  * Find the end of the proposed new region.  Be sure we didn't
999                  * go beyond the end of the map, or wrap around the address.
1000                  * Then check to see if this is the last entry or if the 
1001                  * proposed end fits in the gap between this and the next
1002                  * entry.
1003                  */
1004                 end = start + length;
1005                 if (end > map->max_offset || end < start)
1006                         return (1);
1007                 next = entry->next;
1008                 if (next == &map->header || next->start >= end)
1009                         break;
1010         }
1011         map->hint = entry;
1012         if (map == &kernel_map) {
1013                 vm_offset_t ksize;
1014                 if ((ksize = round_page(start + length)) > kernel_vm_end) {
1015                         pmap_growkernel(ksize);
1016                         goto retry;
1017                 }
1018         }
1019         *addr = start;
1020         return (0);
1021 }
1022
1023 /*
1024  *      vm_map_find finds an unallocated region in the target address
1025  *      map with the given length.  The search is defined to be
1026  *      first-fit from the specified address; the region found is
1027  *      returned in the same parameter.
1028  *
1029  *      If object is non-NULL, ref count must be bumped by caller
1030  *      prior to making call to account for the new entry.
1031  */
1032 int
1033 vm_map_find(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
1034             vm_offset_t *addr,  vm_size_t length,
1035             boolean_t find_space,
1036             vm_maptype_t maptype,
1037             vm_prot_t prot, vm_prot_t max,
1038             int cow)
1039 {
1040         vm_offset_t start;
1041         int result;
1042         int count;
1043
1044         start = *addr;
1045
1046         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
1047         vm_map_lock(map);
1048         if (find_space) {
1049                 if (vm_map_findspace(map, start, length, 1, addr)) {
1050                         vm_map_unlock(map);
1051                         vm_map_entry_release(count);
1052                         return (KERN_NO_SPACE);
1053                 }
1054                 start = *addr;
1055         }
1056         result = vm_map_insert(map, &count, object, offset,
1057                                start, start + length,
1058                                maptype,
1059                                prot, max,
1060                                cow);
1061         vm_map_unlock(map);
1062         vm_map_entry_release(count);
1063
1064         return (result);
1065 }
1066
1067 /*
1068  *      vm_map_simplify_entry:
1069  *
1070  *      Simplify the given map entry by merging with either neighbor.  This
1071  *      routine also has the ability to merge with both neighbors.
1072  *
1073  *      The map must be locked.
1074  *
1075  *      This routine guarentees that the passed entry remains valid (though
1076  *      possibly extended).  When merging, this routine may delete one or
1077  *      both neighbors.  No action is taken on entries which have their
1078  *      in-transition flag set.
1079  */
1080 void
1081 vm_map_simplify_entry(vm_map_t map, vm_map_entry_t entry, int *countp)
1082 {
1083         vm_map_entry_t next, prev;
1084         vm_size_t prevsize, esize;
1085
1086         if (entry->eflags & MAP_ENTRY_IN_TRANSITION) {
1087                 ++mycpu->gd_cnt.v_intrans_coll;
1088                 return;
1089         }
1090
1091         if (entry->maptype == VM_MAPTYPE_SUBMAP)
1092                 return;
1093
1094         prev = entry->prev;
1095         if (prev != &map->header) {
1096                 prevsize = prev->end - prev->start;
1097                 if ( (prev->end == entry->start) &&
1098                      (prev->maptype == entry->maptype) &&
1099                      (prev->object.vm_object == entry->object.vm_object) &&
1100                      (!prev->object.vm_object ||
1101                         (prev->offset + prevsize == entry->offset)) &&
1102                      (prev->eflags == entry->eflags) &&
1103                      (prev->protection == entry->protection) &&
1104                      (prev->max_protection == entry->max_protection) &&
1105                      (prev->inheritance == entry->inheritance) &&
1106                      (prev->wired_count == entry->wired_count)) {
1107                         if (map->first_free == prev)
1108                                 map->first_free = entry;
1109                         if (map->hint == prev)
1110                                 map->hint = entry;
1111                         vm_map_entry_unlink(map, prev);
1112                         entry->start = prev->start;
1113                         entry->offset = prev->offset;
1114                         if (prev->object.vm_object)
1115                                 vm_object_deallocate(prev->object.vm_object);
1116                         vm_map_entry_dispose(map, prev, countp);
1117                 }
1118         }
1119
1120         next = entry->next;
1121         if (next != &map->header) {
1122                 esize = entry->end - entry->start;
1123                 if ((entry->end == next->start) &&
1124                     (next->maptype == entry->maptype) &&
1125                     (next->object.vm_object == entry->object.vm_object) &&
1126                      (!entry->object.vm_object ||
1127                         (entry->offset + esize == next->offset)) &&
1128                     (next->eflags == entry->eflags) &&
1129                     (next->protection == entry->protection) &&
1130                     (next->max_protection == entry->max_protection) &&
1131                     (next->inheritance == entry->inheritance) &&
1132                     (next->wired_count == entry->wired_count)) {
1133                         if (map->first_free == next)
1134                                 map->first_free = entry;
1135                         if (map->hint == next)
1136                                 map->hint = entry;
1137                         vm_map_entry_unlink(map, next);
1138                         entry->end = next->end;
1139                         if (next->object.vm_object)
1140                                 vm_object_deallocate(next->object.vm_object);
1141                         vm_map_entry_dispose(map, next, countp);
1142                 }
1143         }
1144 }
1145 /*
1146  *      vm_map_clip_start:      [ internal use only ]
1147  *
1148  *      Asserts that the given entry begins at or after
1149  *      the specified address; if necessary,
1150  *      it splits the entry into two.
1151  */
1152 #define vm_map_clip_start(map, entry, startaddr, countp) \
1153 { \
1154         if (startaddr > entry->start) \
1155                 _vm_map_clip_start(map, entry, startaddr, countp); \
1156 }
1157
1158 /*
1159  *      This routine is called only when it is known that
1160  *      the entry must be split.
1161  */
1162 static void
1163 _vm_map_clip_start(vm_map_t map, vm_map_entry_t entry, vm_offset_t start, int *countp)
1164 {
1165         vm_map_entry_t new_entry;
1166
1167         /*
1168          * Split off the front portion -- note that we must insert the new
1169          * entry BEFORE this one, so that this entry has the specified
1170          * starting address.
1171          */
1172
1173         vm_map_simplify_entry(map, entry, countp);
1174
1175         /*
1176          * If there is no object backing this entry, we might as well create
1177          * one now.  If we defer it, an object can get created after the map
1178          * is clipped, and individual objects will be created for the split-up
1179          * map.  This is a bit of a hack, but is also about the best place to
1180          * put this improvement.
1181          */
1182         if (entry->object.vm_object == NULL && !map->system_map) {
1183                 vm_map_entry_allocate_object(entry);
1184         }
1185
1186         new_entry = vm_map_entry_create(map, countp);
1187         *new_entry = *entry;
1188
1189         new_entry->end = start;
1190         entry->offset += (start - entry->start);
1191         entry->start = start;
1192
1193         vm_map_entry_link(map, entry->prev, new_entry);
1194
1195         switch(entry->maptype) {
1196         case VM_MAPTYPE_NORMAL:
1197         case VM_MAPTYPE_VPAGETABLE:
1198                 vm_object_reference(new_entry->object.vm_object);
1199                 break;
1200         default:
1201                 break;
1202         }
1203 }
1204
1205 /*
1206  *      vm_map_clip_end:        [ internal use only ]
1207  *
1208  *      Asserts that the given entry ends at or before
1209  *      the specified address; if necessary,
1210  *      it splits the entry into two.
1211  */
1212
1213 #define vm_map_clip_end(map, entry, endaddr, countp) \
1214 { \
1215         if (endaddr < entry->end) \
1216                 _vm_map_clip_end(map, entry, endaddr, countp); \
1217 }
1218
1219 /*
1220  *      This routine is called only when it is known that
1221  *      the entry must be split.
1222  */
1223 static void
1224 _vm_map_clip_end(vm_map_t map, vm_map_entry_t entry, vm_offset_t end, int *countp)
1225 {
1226         vm_map_entry_t new_entry;
1227
1228         /*
1229          * If there is no object backing this entry, we might as well create
1230          * one now.  If we defer it, an object can get created after the map
1231          * is clipped, and individual objects will be created for the split-up
1232          * map.  This is a bit of a hack, but is also about the best place to
1233          * put this improvement.
1234          */
1235
1236         if (entry->object.vm_object == NULL && !map->system_map) {
1237                 vm_map_entry_allocate_object(entry);
1238         }
1239
1240         /*
1241          * Create a new entry and insert it AFTER the specified entry
1242          */
1243
1244         new_entry = vm_map_entry_create(map, countp);
1245         *new_entry = *entry;
1246
1247         new_entry->start = entry->end = end;
1248         new_entry->offset += (end - entry->start);
1249
1250         vm_map_entry_link(map, entry, new_entry);
1251
1252         switch(entry->maptype) {
1253         case VM_MAPTYPE_NORMAL:
1254         case VM_MAPTYPE_VPAGETABLE:
1255                 vm_object_reference(new_entry->object.vm_object);
1256                 break;
1257         default:
1258                 break;
1259         }
1260 }
1261
1262 /*
1263  *      VM_MAP_RANGE_CHECK:     [ internal use only ]
1264  *
1265  *      Asserts that the starting and ending region
1266  *      addresses fall within the valid range of the map.
1267  */
1268 #define VM_MAP_RANGE_CHECK(map, start, end)             \
1269                 {                                       \
1270                 if (start < vm_map_min(map))            \
1271                         start = vm_map_min(map);        \
1272                 if (end > vm_map_max(map))              \
1273                         end = vm_map_max(map);          \
1274                 if (start > end)                        \
1275                         start = end;                    \
1276                 }
1277
1278 /*
1279  *      vm_map_transition_wait: [ kernel use only ]
1280  *
1281  *      Used to block when an in-transition collison occurs.  The map
1282  *      is unlocked for the sleep and relocked before the return.
1283  */
1284 static
1285 void
1286 vm_map_transition_wait(vm_map_t map)
1287 {
1288         vm_map_unlock(map);
1289         tsleep(map, 0, "vment", 0);
1290         vm_map_lock(map);
1291 }
1292
1293 /*
1294  * CLIP_CHECK_BACK
1295  * CLIP_CHECK_FWD
1296  *
1297  *      When we do blocking operations with the map lock held it is
1298  *      possible that a clip might have occured on our in-transit entry,
1299  *      requiring an adjustment to the entry in our loop.  These macros
1300  *      help the pageable and clip_range code deal with the case.  The
1301  *      conditional costs virtually nothing if no clipping has occured.
1302  */
1303
1304 #define CLIP_CHECK_BACK(entry, save_start)              \
1305     do {                                                \
1306             while (entry->start != save_start) {        \
1307                     entry = entry->prev;                \
1308                     KASSERT(entry != &map->header, ("bad entry clip")); \
1309             }                                           \
1310     } while(0)
1311
1312 #define CLIP_CHECK_FWD(entry, save_end)                 \
1313     do {                                                \
1314             while (entry->end != save_end) {            \
1315                     entry = entry->next;                \
1316                     KASSERT(entry != &map->header, ("bad entry clip")); \
1317             }                                           \
1318     } while(0)
1319
1320
1321 /*
1322  *      vm_map_clip_range:      [ kernel use only ]
1323  *
1324  *      Clip the specified range and return the base entry.  The
1325  *      range may cover several entries starting at the returned base
1326  *      and the first and last entry in the covering sequence will be
1327  *      properly clipped to the requested start and end address.
1328  *
1329  *      If no holes are allowed you should pass the MAP_CLIP_NO_HOLES
1330  *      flag.  
1331  *
1332  *      The MAP_ENTRY_IN_TRANSITION flag will be set for the entries
1333  *      covered by the requested range.
1334  *
1335  *      The map must be exclusively locked on entry and will remain locked
1336  *      on return. If no range exists or the range contains holes and you
1337  *      specified that no holes were allowed, NULL will be returned.  This
1338  *      routine may temporarily unlock the map in order avoid a deadlock when
1339  *      sleeping.
1340  */
1341 static
1342 vm_map_entry_t
1343 vm_map_clip_range(vm_map_t map, vm_offset_t start, vm_offset_t end, 
1344         int *countp, int flags)
1345 {
1346         vm_map_entry_t start_entry;
1347         vm_map_entry_t entry;
1348
1349         /*
1350          * Locate the entry and effect initial clipping.  The in-transition
1351          * case does not occur very often so do not try to optimize it.
1352          */
1353 again:
1354         if (vm_map_lookup_entry(map, start, &start_entry) == FALSE)
1355                 return (NULL);
1356         entry = start_entry;
1357         if (entry->eflags & MAP_ENTRY_IN_TRANSITION) {
1358                 entry->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
1359                 ++mycpu->gd_cnt.v_intrans_coll;
1360                 ++mycpu->gd_cnt.v_intrans_wait;
1361                 vm_map_transition_wait(map);
1362                 /*
1363                  * entry and/or start_entry may have been clipped while
1364                  * we slept, or may have gone away entirely.  We have
1365                  * to restart from the lookup.
1366                  */
1367                 goto again;
1368         }
1369         /*
1370          * Since we hold an exclusive map lock we do not have to restart
1371          * after clipping, even though clipping may block in zalloc.
1372          */
1373         vm_map_clip_start(map, entry, start, countp);
1374         vm_map_clip_end(map, entry, end, countp);
1375         entry->eflags |= MAP_ENTRY_IN_TRANSITION;
1376
1377         /*
1378          * Scan entries covered by the range.  When working on the next
1379          * entry a restart need only re-loop on the current entry which
1380          * we have already locked, since 'next' may have changed.  Also,
1381          * even though entry is safe, it may have been clipped so we
1382          * have to iterate forwards through the clip after sleeping.
1383          */
1384         while (entry->next != &map->header && entry->next->start < end) {
1385                 vm_map_entry_t next = entry->next;
1386
1387                 if (flags & MAP_CLIP_NO_HOLES) {
1388                         if (next->start > entry->end) {
1389                                 vm_map_unclip_range(map, start_entry,
1390                                         start, entry->end, countp, flags);
1391                                 return(NULL);
1392                         }
1393                 }
1394
1395                 if (next->eflags & MAP_ENTRY_IN_TRANSITION) {
1396                         vm_offset_t save_end = entry->end;
1397                         next->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
1398                         ++mycpu->gd_cnt.v_intrans_coll;
1399                         ++mycpu->gd_cnt.v_intrans_wait;
1400                         vm_map_transition_wait(map);
1401
1402                         /*
1403                          * clips might have occured while we blocked.
1404                          */
1405                         CLIP_CHECK_FWD(entry, save_end);
1406                         CLIP_CHECK_BACK(start_entry, start);
1407                         continue;
1408                 }
1409                 /*
1410                  * No restart necessary even though clip_end may block, we
1411                  * are holding the map lock.
1412                  */
1413                 vm_map_clip_end(map, next, end, countp);
1414                 next->eflags |= MAP_ENTRY_IN_TRANSITION;
1415                 entry = next;
1416         }
1417         if (flags & MAP_CLIP_NO_HOLES) {
1418                 if (entry->end != end) {
1419                         vm_map_unclip_range(map, start_entry,
1420                                 start, entry->end, countp, flags);
1421                         return(NULL);
1422                 }
1423         }
1424         return(start_entry);
1425 }
1426
1427 /*
1428  *      vm_map_unclip_range:    [ kernel use only ]
1429  *
1430  *      Undo the effect of vm_map_clip_range().  You should pass the same
1431  *      flags and the same range that you passed to vm_map_clip_range().
1432  *      This code will clear the in-transition flag on the entries and
1433  *      wake up anyone waiting.  This code will also simplify the sequence 
1434  *      and attempt to merge it with entries before and after the sequence.
1435  *
1436  *      The map must be locked on entry and will remain locked on return.
1437  *
1438  *      Note that you should also pass the start_entry returned by 
1439  *      vm_map_clip_range().  However, if you block between the two calls
1440  *      with the map unlocked please be aware that the start_entry may
1441  *      have been clipped and you may need to scan it backwards to find
1442  *      the entry corresponding with the original start address.  You are
1443  *      responsible for this, vm_map_unclip_range() expects the correct
1444  *      start_entry to be passed to it and will KASSERT otherwise.
1445  */
1446 static
1447 void
1448 vm_map_unclip_range(
1449         vm_map_t map,
1450         vm_map_entry_t start_entry,
1451         vm_offset_t start,
1452         vm_offset_t end,
1453         int *countp,
1454         int flags)
1455 {
1456         vm_map_entry_t entry;
1457
1458         entry = start_entry;
1459
1460         KASSERT(entry->start == start, ("unclip_range: illegal base entry"));
1461         while (entry != &map->header && entry->start < end) {
1462                 KASSERT(entry->eflags & MAP_ENTRY_IN_TRANSITION, ("in-transition flag not set during unclip on: %p", entry));
1463                 KASSERT(entry->end <= end, ("unclip_range: tail wasn't clipped"));
1464                 entry->eflags &= ~MAP_ENTRY_IN_TRANSITION;
1465                 if (entry->eflags & MAP_ENTRY_NEEDS_WAKEUP) {
1466                         entry->eflags &= ~MAP_ENTRY_NEEDS_WAKEUP;
1467                         wakeup(map);
1468                 }
1469                 entry = entry->next;
1470         }
1471
1472         /*
1473          * Simplification does not block so there is no restart case.
1474          */
1475         entry = start_entry;
1476         while (entry != &map->header && entry->start < end) {
1477                 vm_map_simplify_entry(map, entry, countp);
1478                 entry = entry->next;
1479         }
1480 }
1481
1482 /*
1483  *      vm_map_submap:          [ kernel use only ]
1484  *
1485  *      Mark the given range as handled by a subordinate map.
1486  *
1487  *      This range must have been created with vm_map_find,
1488  *      and no other operations may have been performed on this
1489  *      range prior to calling vm_map_submap.
1490  *
1491  *      Only a limited number of operations can be performed
1492  *      within this rage after calling vm_map_submap:
1493  *              vm_fault
1494  *      [Don't try vm_map_copy!]
1495  *
1496  *      To remove a submapping, one must first remove the
1497  *      range from the superior map, and then destroy the
1498  *      submap (if desired).  [Better yet, don't try it.]
1499  */
1500 int
1501 vm_map_submap(vm_map_t map, vm_offset_t start, vm_offset_t end, vm_map_t submap)
1502 {
1503         vm_map_entry_t entry;
1504         int result = KERN_INVALID_ARGUMENT;
1505         int count;
1506
1507         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
1508         vm_map_lock(map);
1509
1510         VM_MAP_RANGE_CHECK(map, start, end);
1511
1512         if (vm_map_lookup_entry(map, start, &entry)) {
1513                 vm_map_clip_start(map, entry, start, &count);
1514         } else {
1515                 entry = entry->next;
1516         }
1517
1518         vm_map_clip_end(map, entry, end, &count);
1519
1520         if ((entry->start == start) && (entry->end == end) &&
1521             ((entry->eflags & MAP_ENTRY_COW) == 0) &&
1522             (entry->object.vm_object == NULL)) {
1523                 entry->object.sub_map = submap;
1524                 entry->maptype = VM_MAPTYPE_SUBMAP;
1525                 result = KERN_SUCCESS;
1526         }
1527         vm_map_unlock(map);
1528         vm_map_entry_release(count);
1529
1530         return (result);
1531 }
1532
1533 /*
1534  * vm_map_protect:
1535  *
1536  * Sets the protection of the specified address region in the target map. 
1537  * If "set_max" is specified, the maximum protection is to be set;
1538  * otherwise, only the current protection is affected.
1539  *
1540  * The protection is not applicable to submaps, but is applicable to normal
1541  * maps and maps governed by virtual page tables.  For example, when operating
1542  * on a virtual page table our protection basically controls how COW occurs
1543  * on the backing object, whereas the virtual page table abstraction itself
1544  * is an abstraction for userland.
1545  */
1546 int
1547 vm_map_protect(vm_map_t map, vm_offset_t start, vm_offset_t end,
1548                vm_prot_t new_prot, boolean_t set_max)
1549 {
1550         vm_map_entry_t current;
1551         vm_map_entry_t entry;
1552         int count;
1553
1554         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
1555         vm_map_lock(map);
1556
1557         VM_MAP_RANGE_CHECK(map, start, end);
1558
1559         if (vm_map_lookup_entry(map, start, &entry)) {
1560                 vm_map_clip_start(map, entry, start, &count);
1561         } else {
1562                 entry = entry->next;
1563         }
1564
1565         /*
1566          * Make a first pass to check for protection violations.
1567          */
1568         current = entry;
1569         while ((current != &map->header) && (current->start < end)) {
1570                 if (current->maptype == VM_MAPTYPE_SUBMAP) {
1571                         vm_map_unlock(map);
1572                         vm_map_entry_release(count);
1573                         return (KERN_INVALID_ARGUMENT);
1574                 }
1575                 if ((new_prot & current->max_protection) != new_prot) {
1576                         vm_map_unlock(map);
1577                         vm_map_entry_release(count);
1578                         return (KERN_PROTECTION_FAILURE);
1579                 }
1580                 current = current->next;
1581         }
1582
1583         /*
1584          * Go back and fix up protections. [Note that clipping is not
1585          * necessary the second time.]
1586          */
1587         current = entry;
1588
1589         while ((current != &map->header) && (current->start < end)) {
1590                 vm_prot_t old_prot;
1591
1592                 vm_map_clip_end(map, current, end, &count);
1593
1594                 old_prot = current->protection;
1595                 if (set_max) {
1596                         current->protection =
1597                             (current->max_protection = new_prot) &
1598                             old_prot;
1599                 } else {
1600                         current->protection = new_prot;
1601                 }
1602
1603                 /*
1604                  * Update physical map if necessary. Worry about copy-on-write
1605                  * here -- CHECK THIS XXX
1606                  */
1607
1608                 if (current->protection != old_prot) {
1609 #define MASK(entry)     (((entry)->eflags & MAP_ENTRY_COW) ? ~VM_PROT_WRITE : \
1610                                                         VM_PROT_ALL)
1611
1612                         pmap_protect(map->pmap, current->start,
1613                             current->end,
1614                             current->protection & MASK(current));
1615 #undef  MASK
1616                 }
1617
1618                 vm_map_simplify_entry(map, current, &count);
1619
1620                 current = current->next;
1621         }
1622
1623         vm_map_unlock(map);
1624         vm_map_entry_release(count);
1625         return (KERN_SUCCESS);
1626 }
1627
1628 /*
1629  *      vm_map_madvise:
1630  *
1631  *      This routine traverses a processes map handling the madvise
1632  *      system call.  Advisories are classified as either those effecting
1633  *      the vm_map_entry structure, or those effecting the underlying 
1634  *      objects.
1635  *
1636  *      The <value> argument is used for extended madvise calls.
1637  */
1638 int
1639 vm_map_madvise(vm_map_t map, vm_offset_t start, vm_offset_t end,
1640                int behav, off_t value)
1641 {
1642         vm_map_entry_t current, entry;
1643         int modify_map = 0;
1644         int error = 0;
1645         int count;
1646
1647         /*
1648          * Some madvise calls directly modify the vm_map_entry, in which case
1649          * we need to use an exclusive lock on the map and we need to perform 
1650          * various clipping operations.  Otherwise we only need a read-lock
1651          * on the map.
1652          */
1653
1654         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
1655
1656         switch(behav) {
1657         case MADV_NORMAL:
1658         case MADV_SEQUENTIAL:
1659         case MADV_RANDOM:
1660         case MADV_NOSYNC:
1661         case MADV_AUTOSYNC:
1662         case MADV_NOCORE:
1663         case MADV_CORE:
1664         case MADV_SETMAP:
1665         case MADV_INVAL:
1666                 modify_map = 1;
1667                 vm_map_lock(map);
1668                 break;
1669         case MADV_WILLNEED:
1670         case MADV_DONTNEED:
1671         case MADV_FREE:
1672                 vm_map_lock_read(map);
1673                 break;
1674         default:
1675                 vm_map_entry_release(count);
1676                 return (EINVAL);
1677         }
1678
1679         /*
1680          * Locate starting entry and clip if necessary.
1681          */
1682
1683         VM_MAP_RANGE_CHECK(map, start, end);
1684
1685         if (vm_map_lookup_entry(map, start, &entry)) {
1686                 if (modify_map)
1687                         vm_map_clip_start(map, entry, start, &count);
1688         } else {
1689                 entry = entry->next;
1690         }
1691
1692         if (modify_map) {
1693                 /*
1694                  * madvise behaviors that are implemented in the vm_map_entry.
1695                  *
1696                  * We clip the vm_map_entry so that behavioral changes are
1697                  * limited to the specified address range.
1698                  */
1699                 for (current = entry;
1700                      (current != &map->header) && (current->start < end);
1701                      current = current->next
1702                 ) {
1703                         if (current->maptype == VM_MAPTYPE_SUBMAP)
1704                                 continue;
1705
1706                         vm_map_clip_end(map, current, end, &count);
1707
1708                         switch (behav) {
1709                         case MADV_NORMAL:
1710                                 vm_map_entry_set_behavior(current, MAP_ENTRY_BEHAV_NORMAL);
1711                                 break;
1712                         case MADV_SEQUENTIAL:
1713                                 vm_map_entry_set_behavior(current, MAP_ENTRY_BEHAV_SEQUENTIAL);
1714                                 break;
1715                         case MADV_RANDOM:
1716                                 vm_map_entry_set_behavior(current, MAP_ENTRY_BEHAV_RANDOM);
1717                                 break;
1718                         case MADV_NOSYNC:
1719                                 current->eflags |= MAP_ENTRY_NOSYNC;
1720                                 break;
1721                         case MADV_AUTOSYNC:
1722                                 current->eflags &= ~MAP_ENTRY_NOSYNC;
1723                                 break;
1724                         case MADV_NOCORE:
1725                                 current->eflags |= MAP_ENTRY_NOCOREDUMP;
1726                                 break;
1727                         case MADV_CORE:
1728                                 current->eflags &= ~MAP_ENTRY_NOCOREDUMP;
1729                                 break;
1730                         case MADV_INVAL:
1731                                 /*
1732                                  * Invalidate the related pmap entries, used
1733                                  * to flush portions of the real kernel's
1734                                  * pmap when the caller has removed or
1735                                  * modified existing mappings in a virtual
1736                                  * page table.
1737                                  */
1738                                 pmap_remove(map->pmap,
1739                                             current->start, current->end);
1740                                 break;
1741                         case MADV_SETMAP:
1742                                 /*
1743                                  * Set the page directory page for a map
1744                                  * governed by a virtual page table.  Mark
1745                                  * the entry as being governed by a virtual
1746                                  * page table if it is not.
1747                                  *
1748                                  * XXX the page directory page is stored
1749                                  * in the avail_ssize field if the map_entry.
1750                                  *
1751                                  * XXX the map simplification code does not
1752                                  * compare this field so weird things may
1753                                  * happen if you do not apply this function
1754                                  * to the entire mapping governed by the
1755                                  * virtual page table.
1756                                  */
1757                                 if (current->maptype != VM_MAPTYPE_VPAGETABLE) {
1758                                         error = EINVAL;
1759                                         break;
1760                                 }
1761                                 current->aux.master_pde = value;
1762                                 pmap_remove(map->pmap,
1763                                             current->start, current->end);
1764                                 break;
1765                         default:
1766                                 error = EINVAL;
1767                                 break;
1768                         }
1769                         vm_map_simplify_entry(map, current, &count);
1770                 }
1771                 vm_map_unlock(map);
1772         } else {
1773                 vm_pindex_t pindex;
1774                 int count;
1775
1776                 /*
1777                  * madvise behaviors that are implemented in the underlying
1778                  * vm_object.
1779                  *
1780                  * Since we don't clip the vm_map_entry, we have to clip
1781                  * the vm_object pindex and count.
1782                  *
1783                  * NOTE!  We currently do not support these functions on
1784                  * virtual page tables.
1785                  */
1786                 for (current = entry;
1787                      (current != &map->header) && (current->start < end);
1788                      current = current->next
1789                 ) {
1790                         vm_offset_t useStart;
1791
1792                         if (current->maptype != VM_MAPTYPE_NORMAL)
1793                                 continue;
1794
1795                         pindex = OFF_TO_IDX(current->offset);
1796                         count = atop(current->end - current->start);
1797                         useStart = current->start;
1798
1799                         if (current->start < start) {
1800                                 pindex += atop(start - current->start);
1801                                 count -= atop(start - current->start);
1802                                 useStart = start;
1803                         }
1804                         if (current->end > end)
1805                                 count -= atop(current->end - end);
1806
1807                         if (count <= 0)
1808                                 continue;
1809
1810                         vm_object_madvise(current->object.vm_object,
1811                                           pindex, count, behav);
1812
1813                         /*
1814                          * Try to populate the page table.  Mappings governed
1815                          * by virtual page tables cannot be pre-populated
1816                          * without a lot of work so don't try.
1817                          */
1818                         if (behav == MADV_WILLNEED &&
1819                             current->maptype != VM_MAPTYPE_VPAGETABLE) {
1820                                 pmap_object_init_pt(
1821                                     map->pmap, 
1822                                     useStart,
1823                                     current->protection,
1824                                     current->object.vm_object,
1825                                     pindex, 
1826                                     (count << PAGE_SHIFT),
1827                                     MAP_PREFAULT_MADVISE
1828                                 );
1829                         }
1830                 }
1831                 vm_map_unlock_read(map);
1832         }
1833         vm_map_entry_release(count);
1834         return(error);
1835 }       
1836
1837
1838 /*
1839  *      vm_map_inherit:
1840  *
1841  *      Sets the inheritance of the specified address
1842  *      range in the target map.  Inheritance
1843  *      affects how the map will be shared with
1844  *      child maps at the time of vm_map_fork.
1845  */
1846 int
1847 vm_map_inherit(vm_map_t map, vm_offset_t start, vm_offset_t end,
1848                vm_inherit_t new_inheritance)
1849 {
1850         vm_map_entry_t entry;
1851         vm_map_entry_t temp_entry;
1852         int count;
1853
1854         switch (new_inheritance) {
1855         case VM_INHERIT_NONE:
1856         case VM_INHERIT_COPY:
1857         case VM_INHERIT_SHARE:
1858                 break;
1859         default:
1860                 return (KERN_INVALID_ARGUMENT);
1861         }
1862
1863         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
1864         vm_map_lock(map);
1865
1866         VM_MAP_RANGE_CHECK(map, start, end);
1867
1868         if (vm_map_lookup_entry(map, start, &temp_entry)) {
1869                 entry = temp_entry;
1870                 vm_map_clip_start(map, entry, start, &count);
1871         } else
1872                 entry = temp_entry->next;
1873
1874         while ((entry != &map->header) && (entry->start < end)) {
1875                 vm_map_clip_end(map, entry, end, &count);
1876
1877                 entry->inheritance = new_inheritance;
1878
1879                 vm_map_simplify_entry(map, entry, &count);
1880
1881                 entry = entry->next;
1882         }
1883         vm_map_unlock(map);
1884         vm_map_entry_release(count);
1885         return (KERN_SUCCESS);
1886 }
1887
1888 /*
1889  * Implement the semantics of mlock
1890  */
1891 int
1892 vm_map_unwire(vm_map_t map, vm_offset_t start, vm_offset_t real_end,
1893     boolean_t new_pageable)
1894 {
1895         vm_map_entry_t entry;
1896         vm_map_entry_t start_entry;
1897         vm_offset_t end;
1898         int rv = KERN_SUCCESS;
1899         int count;
1900
1901         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
1902         vm_map_lock(map);
1903         VM_MAP_RANGE_CHECK(map, start, real_end);
1904         end = real_end;
1905
1906         start_entry = vm_map_clip_range(map, start, end, &count, MAP_CLIP_NO_HOLES);
1907         if (start_entry == NULL) {
1908                 vm_map_unlock(map);
1909                 vm_map_entry_release(count);
1910                 return (KERN_INVALID_ADDRESS);
1911         }
1912
1913         if (new_pageable == 0) {
1914                 entry = start_entry;
1915                 while ((entry != &map->header) && (entry->start < end)) {
1916                         vm_offset_t save_start;
1917                         vm_offset_t save_end;
1918
1919                         /*
1920                          * Already user wired or hard wired (trivial cases)
1921                          */
1922                         if (entry->eflags & MAP_ENTRY_USER_WIRED) {
1923                                 entry = entry->next;
1924                                 continue;
1925                         }
1926                         if (entry->wired_count != 0) {
1927                                 entry->wired_count++;
1928                                 entry->eflags |= MAP_ENTRY_USER_WIRED;
1929                                 entry = entry->next;
1930                                 continue;
1931                         }
1932
1933                         /*
1934                          * A new wiring requires instantiation of appropriate
1935                          * management structures and the faulting in of the
1936                          * page.
1937                          */
1938                         if (entry->maptype != VM_MAPTYPE_SUBMAP) {
1939                                 int copyflag = entry->eflags & MAP_ENTRY_NEEDS_COPY;
1940                                 if (copyflag && ((entry->protection & VM_PROT_WRITE) != 0)) {
1941                                         vm_map_entry_shadow(entry);
1942                                 } else if (entry->object.vm_object == NULL &&
1943                                            !map->system_map) {
1944                                         vm_map_entry_allocate_object(entry);
1945                                 }
1946                         }
1947                         entry->wired_count++;
1948                         entry->eflags |= MAP_ENTRY_USER_WIRED;
1949
1950                         /*
1951                          * Now fault in the area.  Note that vm_fault_wire()
1952                          * may release the map lock temporarily, it will be
1953                          * relocked on return.  The in-transition
1954                          * flag protects the entries. 
1955                          */
1956                         save_start = entry->start;
1957                         save_end = entry->end;
1958                         rv = vm_fault_wire(map, entry, TRUE);
1959                         if (rv) {
1960                                 CLIP_CHECK_BACK(entry, save_start);
1961                                 for (;;) {
1962                                         KASSERT(entry->wired_count == 1, ("bad wired_count on entry"));
1963                                         entry->eflags &= ~MAP_ENTRY_USER_WIRED;
1964                                         entry->wired_count = 0;
1965                                         if (entry->end == save_end)
1966                                                 break;
1967                                         entry = entry->next;
1968                                         KASSERT(entry != &map->header, ("bad entry clip during backout"));
1969                                 }
1970                                 end = save_start;       /* unwire the rest */
1971                                 break;
1972                         }
1973                         /*
1974                          * note that even though the entry might have been
1975                          * clipped, the USER_WIRED flag we set prevents
1976                          * duplication so we do not have to do a 
1977                          * clip check.
1978                          */
1979                         entry = entry->next;
1980                 }
1981
1982                 /*
1983                  * If we failed fall through to the unwiring section to
1984                  * unwire what we had wired so far.  'end' has already
1985                  * been adjusted.
1986                  */
1987                 if (rv)
1988                         new_pageable = 1;
1989
1990                 /*
1991                  * start_entry might have been clipped if we unlocked the
1992                  * map and blocked.  No matter how clipped it has gotten
1993                  * there should be a fragment that is on our start boundary.
1994                  */
1995                 CLIP_CHECK_BACK(start_entry, start);
1996         }
1997
1998         /*
1999          * Deal with the unwiring case.
2000          */
2001         if (new_pageable) {
2002                 /*
2003                  * This is the unwiring case.  We must first ensure that the
2004                  * range to be unwired is really wired down.  We know there
2005                  * are no holes.
2006                  */
2007                 entry = start_entry;
2008                 while ((entry != &map->header) && (entry->start < end)) {
2009                         if ((entry->eflags & MAP_ENTRY_USER_WIRED) == 0) {
2010                                 rv = KERN_INVALID_ARGUMENT;
2011                                 goto done;
2012                         }
2013                         KASSERT(entry->wired_count != 0, ("wired count was 0 with USER_WIRED set! %p", entry));
2014                         entry = entry->next;
2015                 }
2016
2017                 /*
2018                  * Now decrement the wiring count for each region. If a region
2019                  * becomes completely unwired, unwire its physical pages and
2020                  * mappings.
2021                  */
2022                 /*
2023                  * The map entries are processed in a loop, checking to
2024                  * make sure the entry is wired and asserting it has a wired
2025                  * count. However, another loop was inserted more-or-less in
2026                  * the middle of the unwiring path. This loop picks up the
2027                  * "entry" loop variable from the first loop without first
2028                  * setting it to start_entry. Naturally, the secound loop
2029                  * is never entered and the pages backing the entries are
2030                  * never unwired. This can lead to a leak of wired pages.
2031                  */
2032                 entry = start_entry;
2033                 while ((entry != &map->header) && (entry->start < end)) {
2034                         KASSERT(entry->eflags & MAP_ENTRY_USER_WIRED,
2035                                 ("expected USER_WIRED on entry %p", entry));
2036                         entry->eflags &= ~MAP_ENTRY_USER_WIRED;
2037                         entry->wired_count--;
2038                         if (entry->wired_count == 0)
2039                                 vm_fault_unwire(map, entry);
2040                         entry = entry->next;
2041                 }
2042         }
2043 done:
2044         vm_map_unclip_range(map, start_entry, start, real_end, &count,
2045                 MAP_CLIP_NO_HOLES);
2046         map->timestamp++;
2047         vm_map_unlock(map);
2048         vm_map_entry_release(count);
2049         return (rv);
2050 }
2051
2052 /*
2053  *      vm_map_wire:
2054  *
2055  *      Sets the pageability of the specified address
2056  *      range in the target map.  Regions specified
2057  *      as not pageable require locked-down physical
2058  *      memory and physical page maps.
2059  *
2060  *      The map must not be locked, but a reference
2061  *      must remain to the map throughout the call.
2062  *
2063  *      This function may be called via the zalloc path and must properly
2064  *      reserve map entries for kernel_map.
2065  */
2066 int
2067 vm_map_wire(vm_map_t map, vm_offset_t start, vm_offset_t real_end, int kmflags)
2068 {
2069         vm_map_entry_t entry;
2070         vm_map_entry_t start_entry;
2071         vm_offset_t end;
2072         int rv = KERN_SUCCESS;
2073         int count;
2074
2075         if (kmflags & KM_KRESERVE)
2076                 count = vm_map_entry_kreserve(MAP_RESERVE_COUNT);
2077         else
2078                 count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
2079         vm_map_lock(map);
2080         VM_MAP_RANGE_CHECK(map, start, real_end);
2081         end = real_end;
2082
2083         start_entry = vm_map_clip_range(map, start, end, &count, MAP_CLIP_NO_HOLES);
2084         if (start_entry == NULL) {
2085                 vm_map_unlock(map);
2086                 rv = KERN_INVALID_ADDRESS;
2087                 goto failure;
2088         }
2089         if ((kmflags & KM_PAGEABLE) == 0) {
2090                 /*
2091                  * Wiring.  
2092                  *
2093                  * 1.  Holding the write lock, we create any shadow or zero-fill
2094                  * objects that need to be created. Then we clip each map
2095                  * entry to the region to be wired and increment its wiring
2096                  * count.  We create objects before clipping the map entries
2097                  * to avoid object proliferation.
2098                  *
2099                  * 2.  We downgrade to a read lock, and call vm_fault_wire to
2100                  * fault in the pages for any newly wired area (wired_count is
2101                  * 1).
2102                  *
2103                  * Downgrading to a read lock for vm_fault_wire avoids a 
2104                  * possible deadlock with another process that may have faulted
2105                  * on one of the pages to be wired (it would mark the page busy,
2106                  * blocking us, then in turn block on the map lock that we
2107                  * hold).  Because of problems in the recursive lock package,
2108                  * we cannot upgrade to a write lock in vm_map_lookup.  Thus,
2109                  * any actions that require the write lock must be done
2110                  * beforehand.  Because we keep the read lock on the map, the
2111                  * copy-on-write status of the entries we modify here cannot
2112                  * change.
2113                  */
2114
2115                 entry = start_entry;
2116                 while ((entry != &map->header) && (entry->start < end)) {
2117                         /*
2118                          * Trivial case if the entry is already wired
2119                          */
2120                         if (entry->wired_count) {
2121                                 entry->wired_count++;
2122                                 entry = entry->next;
2123                                 continue;
2124                         }
2125
2126                         /*
2127                          * The entry is being newly wired, we have to setup
2128                          * appropriate management structures.  A shadow 
2129                          * object is required for a copy-on-write region,
2130                          * or a normal object for a zero-fill region.  We
2131                          * do not have to do this for entries that point to sub
2132                          * maps because we won't hold the lock on the sub map.
2133                          */
2134                         if (entry->maptype != VM_MAPTYPE_SUBMAP) {
2135                                 int copyflag = entry->eflags & MAP_ENTRY_NEEDS_COPY;
2136                                 if (copyflag &&
2137                                     ((entry->protection & VM_PROT_WRITE) != 0)) {
2138                                         vm_map_entry_shadow(entry);
2139                                 } else if (entry->object.vm_object == NULL &&
2140                                            !map->system_map) {
2141                                         vm_map_entry_allocate_object(entry);
2142                                 }
2143                         }
2144
2145                         entry->wired_count++;
2146                         entry = entry->next;
2147                 }
2148
2149                 /*
2150                  * Pass 2.
2151                  */
2152
2153                 /*
2154                  * HACK HACK HACK HACK
2155                  *
2156                  * Unlock the map to avoid deadlocks.  The in-transit flag
2157                  * protects us from most changes but note that
2158                  * clipping may still occur.  To prevent clipping from
2159                  * occuring after the unlock, except for when we are
2160                  * blocking in vm_fault_wire, we must run in a critical
2161                  * section, otherwise our accesses to entry->start and 
2162                  * entry->end could be corrupted.  We have to enter the
2163                  * critical section prior to unlocking so start_entry does
2164                  * not change out from under us at the very beginning of the
2165                  * loop.
2166                  *
2167                  * HACK HACK HACK HACK
2168                  */
2169
2170                 crit_enter();
2171
2172                 entry = start_entry;
2173                 while (entry != &map->header && entry->start < end) {
2174                         /*
2175                          * If vm_fault_wire fails for any page we need to undo
2176                          * what has been done.  We decrement the wiring count
2177                          * for those pages which have not yet been wired (now)
2178                          * and unwire those that have (later).
2179                          */
2180                         vm_offset_t save_start = entry->start;
2181                         vm_offset_t save_end = entry->end;
2182
2183                         if (entry->wired_count == 1)
2184                                 rv = vm_fault_wire(map, entry, FALSE);
2185                         if (rv) {
2186                                 CLIP_CHECK_BACK(entry, save_start);
2187                                 for (;;) {
2188                                         KASSERT(entry->wired_count == 1, ("wired_count changed unexpectedly"));
2189                                         entry->wired_count = 0;
2190                                         if (entry->end == save_end)
2191                                                 break;
2192                                         entry = entry->next;
2193                                         KASSERT(entry != &map->header, ("bad entry clip during backout"));
2194                                 }
2195                                 end = save_start;
2196                                 break;
2197                         }
2198                         CLIP_CHECK_FWD(entry, save_end);
2199                         entry = entry->next;
2200                 }
2201                 crit_exit();
2202
2203                 /*
2204                  * If a failure occured undo everything by falling through
2205                  * to the unwiring code.  'end' has already been adjusted
2206                  * appropriately.
2207                  */
2208                 if (rv)
2209                         kmflags |= KM_PAGEABLE;
2210
2211                 /*
2212                  * start_entry is still IN_TRANSITION but may have been 
2213                  * clipped since vm_fault_wire() unlocks and relocks the
2214                  * map.  No matter how clipped it has gotten there should
2215                  * be a fragment that is on our start boundary.
2216                  */
2217                 CLIP_CHECK_BACK(start_entry, start);
2218         }
2219
2220         if (kmflags & KM_PAGEABLE) {
2221                 /*
2222                  * This is the unwiring case.  We must first ensure that the
2223                  * range to be unwired is really wired down.  We know there
2224                  * are no holes.
2225                  */
2226                 entry = start_entry;
2227                 while ((entry != &map->header) && (entry->start < end)) {
2228                         if (entry->wired_count == 0) {
2229                                 rv = KERN_INVALID_ARGUMENT;
2230                                 goto done;
2231                         }
2232                         entry = entry->next;
2233                 }
2234
2235                 /*
2236                  * Now decrement the wiring count for each region. If a region
2237                  * becomes completely unwired, unwire its physical pages and
2238                  * mappings.
2239                  */
2240                 entry = start_entry;
2241                 while ((entry != &map->header) && (entry->start < end)) {
2242                         entry->wired_count--;
2243                         if (entry->wired_count == 0)
2244                                 vm_fault_unwire(map, entry);
2245                         entry = entry->next;
2246                 }
2247         }
2248 done:
2249         vm_map_unclip_range(map, start_entry, start, real_end, &count,
2250                 MAP_CLIP_NO_HOLES);
2251         map->timestamp++;
2252         vm_map_unlock(map);
2253 failure:
2254         if (kmflags & KM_KRESERVE)
2255                 vm_map_entry_krelease(count);
2256         else
2257                 vm_map_entry_release(count);
2258         return (rv);
2259 }
2260
2261 /*
2262  * vm_map_set_wired_quick()
2263  *
2264  *      Mark a newly allocated address range as wired but do not fault in
2265  *      the pages.  The caller is expected to load the pages into the object.
2266  *
2267  *      The map must be locked on entry and will remain locked on return.
2268  */
2269 void
2270 vm_map_set_wired_quick(vm_map_t map, vm_offset_t addr, vm_size_t size, int *countp)
2271 {
2272         vm_map_entry_t scan;
2273         vm_map_entry_t entry;
2274
2275         entry = vm_map_clip_range(map, addr, addr + size, countp, MAP_CLIP_NO_HOLES);
2276         for (scan = entry; scan != &map->header && scan->start < addr + size; scan = scan->next) {
2277             KKASSERT(entry->wired_count == 0);
2278             entry->wired_count = 1;                                              
2279         }
2280         vm_map_unclip_range(map, entry, addr, addr + size, countp, MAP_CLIP_NO_HOLES);
2281 }
2282
2283 /*
2284  * vm_map_clean
2285  *
2286  * Push any dirty cached pages in the address range to their pager.
2287  * If syncio is TRUE, dirty pages are written synchronously.
2288  * If invalidate is TRUE, any cached pages are freed as well.
2289  *
2290  * Returns an error if any part of the specified range is not mapped.
2291  */
2292 int
2293 vm_map_clean(vm_map_t map, vm_offset_t start, vm_offset_t end, boolean_t syncio,
2294     boolean_t invalidate)
2295 {
2296         vm_map_entry_t current;
2297         vm_map_entry_t entry;
2298         vm_size_t size;
2299         vm_object_t object;
2300         vm_ooffset_t offset;
2301
2302         vm_map_lock_read(map);
2303         VM_MAP_RANGE_CHECK(map, start, end);
2304         if (!vm_map_lookup_entry(map, start, &entry)) {
2305                 vm_map_unlock_read(map);
2306                 return (KERN_INVALID_ADDRESS);
2307         }
2308         /*
2309          * Make a first pass to check for holes.
2310          */
2311         for (current = entry; current->start < end; current = current->next) {
2312                 if (current->maptype == VM_MAPTYPE_SUBMAP) {
2313                         vm_map_unlock_read(map);
2314                         return (KERN_INVALID_ARGUMENT);
2315                 }
2316                 if (end > current->end &&
2317                     (current->next == &map->header ||
2318                         current->end != current->next->start)) {
2319                         vm_map_unlock_read(map);
2320                         return (KERN_INVALID_ADDRESS);
2321                 }
2322         }
2323
2324         if (invalidate)
2325                 pmap_remove(vm_map_pmap(map), start, end);
2326         /*
2327          * Make a second pass, cleaning/uncaching pages from the indicated
2328          * objects as we go.
2329          */
2330         for (current = entry; current->start < end; current = current->next) {
2331                 offset = current->offset + (start - current->start);
2332                 size = (end <= current->end ? end : current->end) - start;
2333                 if (current->maptype == VM_MAPTYPE_SUBMAP) {
2334                         vm_map_t smap;
2335                         vm_map_entry_t tentry;
2336                         vm_size_t tsize;
2337
2338                         smap = current->object.sub_map;
2339                         vm_map_lock_read(smap);
2340                         vm_map_lookup_entry(smap, offset, &tentry);
2341                         tsize = tentry->end - offset;
2342                         if (tsize < size)
2343                                 size = tsize;
2344                         object = tentry->object.vm_object;
2345                         offset = tentry->offset + (offset - tentry->start);
2346                         vm_map_unlock_read(smap);
2347                 } else {
2348                         object = current->object.vm_object;
2349                 }
2350                 /*
2351                  * Note that there is absolutely no sense in writing out
2352                  * anonymous objects, so we track down the vnode object
2353                  * to write out.
2354                  * We invalidate (remove) all pages from the address space
2355                  * anyway, for semantic correctness.
2356                  *
2357                  * note: certain anonymous maps, such as MAP_NOSYNC maps,
2358                  * may start out with a NULL object.
2359                  */
2360                 while (object && object->backing_object) {
2361                         offset += object->backing_object_offset;
2362                         object = object->backing_object;
2363                         if (object->size < OFF_TO_IDX( offset + size))
2364                                 size = IDX_TO_OFF(object->size) - offset;
2365                 }
2366                 if (object && (object->type == OBJT_VNODE) && 
2367                     (current->protection & VM_PROT_WRITE)) {
2368                         /*
2369                          * Flush pages if writing is allowed, invalidate them
2370                          * if invalidation requested.  Pages undergoing I/O
2371                          * will be ignored by vm_object_page_remove().
2372                          *
2373                          * We cannot lock the vnode and then wait for paging
2374                          * to complete without deadlocking against vm_fault.
2375                          * Instead we simply call vm_object_page_remove() and
2376                          * allow it to block internally on a page-by-page 
2377                          * basis when it encounters pages undergoing async 
2378                          * I/O.
2379                          */
2380                         int flags;
2381
2382                         vm_object_reference(object);
2383                         vn_lock(object->handle, LK_EXCLUSIVE | LK_RETRY);
2384                         flags = (syncio || invalidate) ? OBJPC_SYNC : 0;
2385                         flags |= invalidate ? OBJPC_INVAL : 0;
2386
2387                         /*
2388                          * When operating on a virtual page table just
2389                          * flush the whole object.  XXX we probably ought
2390                          * to 
2391                          */
2392                         switch(current->maptype) {
2393                         case VM_MAPTYPE_NORMAL:
2394                                 vm_object_page_clean(object,
2395                                     OFF_TO_IDX(offset),
2396                                     OFF_TO_IDX(offset + size + PAGE_MASK),
2397                                     flags);
2398                                 break;
2399                         case VM_MAPTYPE_VPAGETABLE:
2400                                 vm_object_page_clean(object, 0, 0, flags);
2401                                 break;
2402                         }
2403                         vn_unlock(((struct vnode *)object->handle));
2404                         vm_object_deallocate(object);
2405                 }
2406                 if (object && invalidate &&
2407                    ((object->type == OBJT_VNODE) ||
2408                     (object->type == OBJT_DEVICE))) {
2409                         int clean_only = 
2410                                 (object->type == OBJT_DEVICE) ? FALSE : TRUE;
2411                         vm_object_reference(object);
2412                         switch(current->maptype) {
2413                         case VM_MAPTYPE_NORMAL:
2414                                 vm_object_page_remove(object,
2415                                     OFF_TO_IDX(offset),
2416                                     OFF_TO_IDX(offset + size + PAGE_MASK),
2417                                     clean_only);
2418                                 break;
2419                         case VM_MAPTYPE_VPAGETABLE:
2420                                 vm_object_page_remove(object, 0, 0, clean_only);
2421                                 break;
2422                         }
2423                         vm_object_deallocate(object);
2424                 }
2425                 start += size;
2426         }
2427
2428         vm_map_unlock_read(map);
2429         return (KERN_SUCCESS);
2430 }
2431
2432 /*
2433  *      vm_map_entry_unwire:    [ internal use only ]
2434  *
2435  *      Make the region specified by this entry pageable.
2436  *
2437  *      The map in question should be locked.
2438  *      [This is the reason for this routine's existence.]
2439  */
2440 static void 
2441 vm_map_entry_unwire(vm_map_t map, vm_map_entry_t entry)
2442 {
2443         entry->eflags &= ~MAP_ENTRY_USER_WIRED;
2444         entry->wired_count = 0;
2445         vm_fault_unwire(map, entry);
2446 }
2447
2448 /*
2449  *      vm_map_entry_delete:    [ internal use only ]
2450  *
2451  *      Deallocate the given entry from the target map.
2452  */
2453 static void
2454 vm_map_entry_delete(vm_map_t map, vm_map_entry_t entry, int *countp)
2455 {
2456         vm_map_entry_unlink(map, entry);
2457         map->size -= entry->end - entry->start;
2458
2459         switch(entry->maptype) {
2460         case VM_MAPTYPE_NORMAL:
2461         case VM_MAPTYPE_VPAGETABLE:
2462                 vm_object_deallocate(entry->object.vm_object);
2463                 break;
2464         default:
2465                 break;
2466         }
2467
2468         vm_map_entry_dispose(map, entry, countp);
2469 }
2470
2471 /*
2472  *      vm_map_delete:  [ internal use only ]
2473  *
2474  *      Deallocates the given address range from the target
2475  *      map.
2476  */
2477 int
2478 vm_map_delete(vm_map_t map, vm_offset_t start, vm_offset_t end, int *countp)
2479 {
2480         vm_object_t object;
2481         vm_map_entry_t entry;
2482         vm_map_entry_t first_entry;
2483
2484 again:
2485         /*
2486          * Find the start of the region, and clip it.  Set entry to point
2487          * at the first record containing the requested address or, if no
2488          * such record exists, the next record with a greater address.  The
2489          * loop will run from this point until a record beyond the termination
2490          * address is encountered.
2491          *
2492          * map->hint must be adjusted to not point to anything we delete,
2493          * so set it to the entry prior to the one being deleted.
2494          *
2495          * GGG see other GGG comment.
2496          */
2497         if (vm_map_lookup_entry(map, start, &first_entry)) {
2498                 entry = first_entry;
2499                 vm_map_clip_start(map, entry, start, countp);
2500                 map->hint = entry->prev;        /* possible problem XXX */
2501         } else {
2502                 map->hint = first_entry;        /* possible problem XXX */
2503                 entry = first_entry->next;
2504         }
2505
2506         /*
2507          * If a hole opens up prior to the current first_free then
2508          * adjust first_free.  As with map->hint, map->first_free
2509          * cannot be left set to anything we might delete.
2510          */
2511         if (entry == &map->header) {
2512                 map->first_free = &map->header;
2513         } else if (map->first_free->start >= start) {
2514                 map->first_free = entry->prev;
2515         }
2516
2517         /*
2518          * Step through all entries in this region
2519          */
2520
2521         while ((entry != &map->header) && (entry->start < end)) {
2522                 vm_map_entry_t next;
2523                 vm_offset_t s, e;
2524                 vm_pindex_t offidxstart, offidxend, count;
2525
2526                 /*
2527                  * If we hit an in-transition entry we have to sleep and
2528                  * retry.  It's easier (and not really slower) to just retry
2529                  * since this case occurs so rarely and the hint is already
2530                  * pointing at the right place.  We have to reset the
2531                  * start offset so as not to accidently delete an entry
2532                  * another process just created in vacated space.
2533                  */
2534                 if (entry->eflags & MAP_ENTRY_IN_TRANSITION) {
2535                         entry->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
2536                         start = entry->start;
2537                         ++mycpu->gd_cnt.v_intrans_coll;
2538                         ++mycpu->gd_cnt.v_intrans_wait;
2539                         vm_map_transition_wait(map);
2540                         goto again;
2541                 }
2542                 vm_map_clip_end(map, entry, end, countp);
2543
2544                 s = entry->start;
2545                 e = entry->end;
2546                 next = entry->next;
2547
2548                 offidxstart = OFF_TO_IDX(entry->offset);
2549                 count = OFF_TO_IDX(e - s);
2550                 object = entry->object.vm_object;
2551
2552                 /*
2553                  * Unwire before removing addresses from the pmap; otherwise,
2554                  * unwiring will put the entries back in the pmap.
2555                  */
2556                 if (entry->wired_count != 0)
2557                         vm_map_entry_unwire(map, entry);
2558
2559                 offidxend = offidxstart + count;
2560
2561                 if (object == &kernel_object) {
2562                         vm_object_page_remove(object, offidxstart, offidxend, FALSE);
2563                 } else {
2564                         pmap_remove(map->pmap, s, e);
2565                         if (object != NULL &&
2566                             object->ref_count != 1 &&
2567                             (object->flags & (OBJ_NOSPLIT|OBJ_ONEMAPPING)) == OBJ_ONEMAPPING &&
2568                             (object->type == OBJT_DEFAULT || object->type == OBJT_SWAP)) {
2569                                 vm_object_collapse(object);
2570                                 vm_object_page_remove(object, offidxstart, offidxend, FALSE);
2571                                 if (object->type == OBJT_SWAP) {
2572                                         swap_pager_freespace(object, offidxstart, count);
2573                                 }
2574                                 if (offidxend >= object->size &&
2575                                     offidxstart < object->size) {
2576                                         object->size = offidxstart;
2577                                 }
2578                         }
2579                 }
2580
2581                 /*
2582                  * Delete the entry (which may delete the object) only after
2583                  * removing all pmap entries pointing to its pages.
2584                  * (Otherwise, its page frames may be reallocated, and any
2585                  * modify bits will be set in the wrong object!)
2586                  */
2587                 vm_map_entry_delete(map, entry, countp);
2588                 entry = next;
2589         }
2590         return (KERN_SUCCESS);
2591 }
2592
2593 /*
2594  *      vm_map_remove:
2595  *
2596  *      Remove the given address range from the target map.
2597  *      This is the exported form of vm_map_delete.
2598  */
2599 int
2600 vm_map_remove(vm_map_t map, vm_offset_t start, vm_offset_t end)
2601 {
2602         int result;
2603         int count;
2604
2605         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
2606         vm_map_lock(map);
2607         VM_MAP_RANGE_CHECK(map, start, end);
2608         result = vm_map_delete(map, start, end, &count);
2609         vm_map_unlock(map);
2610         vm_map_entry_release(count);
2611
2612         return (result);
2613 }
2614
2615 /*
2616  *      vm_map_check_protection:
2617  *
2618  *      Assert that the target map allows the specified
2619  *      privilege on the entire address region given.
2620  *      The entire region must be allocated.
2621  */
2622 boolean_t
2623 vm_map_check_protection(vm_map_t map, vm_offset_t start, vm_offset_t end,
2624                         vm_prot_t protection)
2625 {
2626         vm_map_entry_t entry;
2627         vm_map_entry_t tmp_entry;
2628
2629         if (!vm_map_lookup_entry(map, start, &tmp_entry)) {
2630                 return (FALSE);
2631         }
2632         entry = tmp_entry;
2633
2634         while (start < end) {
2635                 if (entry == &map->header) {
2636                         return (FALSE);
2637                 }
2638                 /*
2639                  * No holes allowed!
2640                  */
2641
2642                 if (start < entry->start) {
2643                         return (FALSE);
2644                 }
2645                 /*
2646                  * Check protection associated with entry.
2647                  */
2648
2649                 if ((entry->protection & protection) != protection) {
2650                         return (FALSE);
2651                 }
2652                 /* go to next entry */
2653
2654                 start = entry->end;
2655                 entry = entry->next;
2656         }
2657         return (TRUE);
2658 }
2659
2660 /*
2661  * Split the pages in a map entry into a new object.  This affords
2662  * easier removal of unused pages, and keeps object inheritance from
2663  * being a negative impact on memory usage.
2664  */
2665 static void
2666 vm_map_split(vm_map_entry_t entry)
2667 {
2668         vm_page_t m;
2669         vm_object_t orig_object, new_object, source;
2670         vm_offset_t s, e;
2671         vm_pindex_t offidxstart, offidxend, idx;
2672         vm_size_t size;
2673         vm_ooffset_t offset;
2674
2675         orig_object = entry->object.vm_object;
2676         if (orig_object->type != OBJT_DEFAULT && orig_object->type != OBJT_SWAP)
2677                 return;
2678         if (orig_object->ref_count <= 1)
2679                 return;
2680
2681         offset = entry->offset;
2682         s = entry->start;
2683         e = entry->end;
2684
2685         offidxstart = OFF_TO_IDX(offset);
2686         offidxend = offidxstart + OFF_TO_IDX(e - s);
2687         size = offidxend - offidxstart;
2688
2689         new_object = vm_pager_allocate(orig_object->type, NULL,
2690                                        IDX_TO_OFF(size), VM_PROT_ALL, 0);
2691         if (new_object == NULL)
2692                 return;
2693
2694         source = orig_object->backing_object;
2695         if (source != NULL) {
2696                 vm_object_reference(source);    /* Referenced by new_object */
2697                 LIST_INSERT_HEAD(&source->shadow_head,
2698                                   new_object, shadow_list);
2699                 vm_object_clear_flag(source, OBJ_ONEMAPPING);
2700                 new_object->backing_object_offset = 
2701                         orig_object->backing_object_offset + IDX_TO_OFF(offidxstart);
2702                 new_object->backing_object = source;
2703                 source->shadow_count++;
2704                 source->generation++;
2705         }
2706
2707         for (idx = 0; idx < size; idx++) {
2708                 vm_page_t m;
2709
2710                 /*
2711                  * A critical section is required to avoid a race between
2712                  * the lookup and an interrupt/unbusy/free and our busy
2713                  * check.
2714                  */
2715                 crit_enter();
2716         retry:
2717                 m = vm_page_lookup(orig_object, offidxstart + idx);
2718                 if (m == NULL) {
2719                         crit_exit();
2720                         continue;
2721                 }
2722
2723                 /*
2724                  * We must wait for pending I/O to complete before we can
2725                  * rename the page.
2726                  *
2727                  * We do not have to VM_PROT_NONE the page as mappings should
2728                  * not be changed by this operation.
2729                  */
2730                 if (vm_page_sleep_busy(m, TRUE, "spltwt"))
2731                         goto retry;
2732                 vm_page_busy(m);
2733                 vm_page_rename(m, new_object, idx);
2734                 /* page automatically made dirty by rename and cache handled */
2735                 vm_page_busy(m);
2736                 crit_exit();
2737         }
2738
2739         if (orig_object->type == OBJT_SWAP) {
2740                 vm_object_pip_add(orig_object, 1);
2741                 /*
2742                  * copy orig_object pages into new_object
2743                  * and destroy unneeded pages in
2744                  * shadow object.
2745                  */
2746                 swap_pager_copy(orig_object, new_object, offidxstart, 0);
2747                 vm_object_pip_wakeup(orig_object);
2748         }
2749
2750         /*
2751          * Wakeup the pages we played with.  No spl protection is needed
2752          * for a simple wakeup.
2753          */
2754         for (idx = 0; idx < size; idx++) {
2755                 m = vm_page_lookup(new_object, idx);
2756                 if (m)
2757                         vm_page_wakeup(m);
2758         }
2759
2760         entry->object.vm_object = new_object;
2761         entry->offset = 0LL;
2762         vm_object_deallocate(orig_object);
2763 }
2764
2765 /*
2766  *      vm_map_copy_entry:
2767  *
2768  *      Copies the contents of the source entry to the destination
2769  *      entry.  The entries *must* be aligned properly.
2770  */
2771 static void
2772 vm_map_copy_entry(vm_map_t src_map, vm_map_t dst_map,
2773         vm_map_entry_t src_entry, vm_map_entry_t dst_entry)
2774 {
2775         vm_object_t src_object;
2776
2777         if (dst_entry->maptype == VM_MAPTYPE_SUBMAP)
2778                 return;
2779         if (src_entry->maptype == VM_MAPTYPE_SUBMAP)
2780                 return;
2781
2782         if (src_entry->wired_count == 0) {
2783                 /*
2784                  * If the source entry is marked needs_copy, it is already
2785                  * write-protected.
2786                  */
2787                 if ((src_entry->eflags & MAP_ENTRY_NEEDS_COPY) == 0) {
2788                         pmap_protect(src_map->pmap,
2789                             src_entry->start,
2790                             src_entry->end,
2791                             src_entry->protection & ~VM_PROT_WRITE);
2792                 }
2793
2794                 /*
2795                  * Make a copy of the object.
2796                  */
2797                 if ((src_object = src_entry->object.vm_object) != NULL) {
2798                         if ((src_object->handle == NULL) &&
2799                                 (src_object->type == OBJT_DEFAULT ||
2800                                  src_object->type == OBJT_SWAP)) {
2801                                 vm_object_collapse(src_object);
2802                                 if ((src_object->flags & (OBJ_NOSPLIT|OBJ_ONEMAPPING)) == OBJ_ONEMAPPING) {
2803                                         vm_map_split(src_entry);
2804                                         src_object = src_entry->object.vm_object;
2805                                 }
2806                         }
2807
2808                         vm_object_reference(src_object);
2809                         vm_object_clear_flag(src_object, OBJ_ONEMAPPING);
2810                         dst_entry->object.vm_object = src_object;
2811                         src_entry->eflags |= (MAP_ENTRY_COW|MAP_ENTRY_NEEDS_COPY);
2812                         dst_entry->eflags |= (MAP_ENTRY_COW|MAP_ENTRY_NEEDS_COPY);
2813                         dst_entry->offset = src_entry->offset;
2814                 } else {
2815                         dst_entry->object.vm_object = NULL;
2816                         dst_entry->offset = 0;
2817                 }
2818
2819                 pmap_copy(dst_map->pmap, src_map->pmap, dst_entry->start,
2820                     dst_entry->end - dst_entry->start, src_entry->start);
2821         } else {
2822                 /*
2823                  * Of course, wired down pages can't be set copy-on-write.
2824                  * Cause wired pages to be copied into the new map by
2825                  * simulating faults (the new pages are pageable)
2826                  */
2827                 vm_fault_copy_entry(dst_map, src_map, dst_entry, src_entry);
2828         }
2829 }
2830
2831 /*
2832  * vmspace_fork:
2833  * Create a new process vmspace structure and vm_map
2834  * based on those of an existing process.  The new map
2835  * is based on the old map, according to the inheritance
2836  * values on the regions in that map.
2837  *
2838  * The source map must not be locked.
2839  */
2840 struct vmspace *
2841 vmspace_fork(struct vmspace *vm1)
2842 {
2843         struct vmspace *vm2;
2844         vm_map_t old_map = &vm1->vm_map;
2845         vm_map_t new_map;
2846         vm_map_entry_t old_entry;
2847         vm_map_entry_t new_entry;
2848         vm_object_t object;
2849         int count;
2850
2851         vm_map_lock(old_map);
2852         old_map->infork = 1;
2853
2854         /*
2855          * XXX Note: upcalls are not copied.
2856          */
2857         vm2 = vmspace_alloc(old_map->min_offset, old_map->max_offset);
2858         bcopy(&vm1->vm_startcopy, &vm2->vm_startcopy,
2859             (caddr_t)&vm1->vm_endcopy - (caddr_t)&vm1->vm_startcopy);
2860         new_map = &vm2->vm_map; /* XXX */
2861         new_map->timestamp = 1;
2862
2863         count = 0;
2864         old_entry = old_map->header.next;
2865         while (old_entry != &old_map->header) {
2866                 ++count;
2867                 old_entry = old_entry->next;
2868         }
2869
2870         count = vm_map_entry_reserve(count + MAP_RESERVE_COUNT);
2871
2872         old_entry = old_map->header.next;
2873         while (old_entry != &old_map->header) {
2874                 if (old_entry->maptype == VM_MAPTYPE_SUBMAP)
2875                         panic("vm_map_fork: encountered a submap");
2876
2877                 switch (old_entry->inheritance) {
2878                 case VM_INHERIT_NONE:
2879                         break;
2880
2881                 case VM_INHERIT_SHARE:
2882                         /*
2883                          * Clone the entry, creating the shared object if
2884                          * necessary.
2885                          */
2886                         object = old_entry->object.vm_object;
2887                         if (object == NULL) {
2888                                 vm_map_entry_allocate_object(old_entry);
2889                                 object = old_entry->object.vm_object;
2890                         }
2891
2892                         /*
2893                          * Add the reference before calling vm_map_entry_shadow
2894                          * to insure that a shadow object is created.
2895                          */
2896                         vm_object_reference(object);
2897                         if (old_entry->eflags & MAP_ENTRY_NEEDS_COPY) {
2898                                 vm_map_entry_shadow(old_entry);
2899                                 /* Transfer the second reference too. */
2900                                 vm_object_reference(
2901                                     old_entry->object.vm_object);
2902                                 vm_object_deallocate(object);
2903                                 object = old_entry->object.vm_object;
2904                         }
2905                         vm_object_clear_flag(object, OBJ_ONEMAPPING);
2906
2907                         /*
2908                          * Clone the entry, referencing the shared object.
2909                          */
2910                         new_entry = vm_map_entry_create(new_map, &count);
2911                         *new_entry = *old_entry;
2912                         new_entry->eflags &= ~MAP_ENTRY_USER_WIRED;
2913                         new_entry->wired_count = 0;
2914
2915                         /*
2916                          * Insert the entry into the new map -- we know we're
2917                          * inserting at the end of the new map.
2918                          */
2919
2920                         vm_map_entry_link(new_map, new_map->header.prev,
2921                             new_entry);
2922
2923                         /*
2924                          * Update the physical map
2925                          */
2926
2927                         pmap_copy(new_map->pmap, old_map->pmap,
2928                             new_entry->start,
2929                             (old_entry->end - old_entry->start),
2930                             old_entry->start);
2931                         break;
2932
2933                 case VM_INHERIT_COPY:
2934                         /*
2935                          * Clone the entry and link into the map.
2936                          */
2937                         new_entry = vm_map_entry_create(new_map, &count);
2938                         *new_entry = *old_entry;
2939                         new_entry->eflags &= ~MAP_ENTRY_USER_WIRED;
2940                         new_entry->wired_count = 0;
2941                         new_entry->object.vm_object = NULL;
2942                         vm_map_entry_link(new_map, new_map->header.prev,
2943                             new_entry);
2944                         vm_map_copy_entry(old_map, new_map, old_entry,
2945                             new_entry);
2946                         break;
2947                 }
2948                 old_entry = old_entry->next;
2949         }
2950
2951         new_map->size = old_map->size;
2952         old_map->infork = 0;
2953         vm_map_unlock(old_map);
2954         vm_map_entry_release(count);
2955
2956         return (vm2);
2957 }
2958
2959 int
2960 vm_map_stack (vm_map_t map, vm_offset_t addrbos, vm_size_t max_ssize,
2961               vm_prot_t prot, vm_prot_t max, int cow)
2962 {
2963         vm_map_entry_t prev_entry;
2964         vm_map_entry_t new_stack_entry;
2965         vm_size_t      init_ssize;
2966         int            rv;
2967         int             count;
2968
2969         if (VM_MIN_USER_ADDRESS > 0 && addrbos < VM_MIN_USER_ADDRESS)
2970                 return (KERN_NO_SPACE);
2971
2972         if (max_ssize < sgrowsiz)
2973                 init_ssize = max_ssize;
2974         else
2975                 init_ssize = sgrowsiz;
2976
2977         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
2978         vm_map_lock(map);
2979
2980         /* If addr is already mapped, no go */
2981         if (vm_map_lookup_entry(map, addrbos, &prev_entry)) {
2982                 vm_map_unlock(map);
2983                 vm_map_entry_release(count);
2984                 return (KERN_NO_SPACE);
2985         }
2986
2987         /* If we would blow our VMEM resource limit, no go */
2988         if (map->size + init_ssize >
2989             curproc->p_rlimit[RLIMIT_VMEM].rlim_cur) {
2990                 vm_map_unlock(map);
2991                 vm_map_entry_release(count);
2992                 return (KERN_NO_SPACE);
2993         }
2994
2995         /* If we can't accomodate max_ssize in the current mapping,
2996          * no go.  However, we need to be aware that subsequent user
2997          * mappings might map into the space we have reserved for
2998          * stack, and currently this space is not protected.  
2999          * 
3000          * Hopefully we will at least detect this condition 
3001          * when we try to grow the stack.
3002          */
3003         if ((prev_entry->next != &map->header) &&
3004             (prev_entry->next->start < addrbos + max_ssize)) {
3005                 vm_map_unlock(map);
3006                 vm_map_entry_release(count);
3007                 return (KERN_NO_SPACE);
3008         }
3009
3010         /* We initially map a stack of only init_ssize.  We will
3011          * grow as needed later.  Since this is to be a grow 
3012          * down stack, we map at the top of the range.
3013          *
3014          * Note: we would normally expect prot and max to be
3015          * VM_PROT_ALL, and cow to be 0.  Possibly we should
3016          * eliminate these as input parameters, and just
3017          * pass these values here in the insert call.
3018          */
3019         rv = vm_map_insert(map, &count,
3020                            NULL, 0, addrbos + max_ssize - init_ssize,
3021                            addrbos + max_ssize,
3022                            VM_MAPTYPE_NORMAL,
3023                            prot, max,
3024                            cow);
3025
3026         /* Now set the avail_ssize amount */
3027         if (rv == KERN_SUCCESS) {
3028                 if (prev_entry != &map->header)
3029                         vm_map_clip_end(map, prev_entry, addrbos + max_ssize - init_ssize, &count);
3030                 new_stack_entry = prev_entry->next;
3031                 if (new_stack_entry->end   != addrbos + max_ssize ||
3032                     new_stack_entry->start != addrbos + max_ssize - init_ssize)
3033                         panic ("Bad entry start/end for new stack entry");
3034                 else 
3035                         new_stack_entry->aux.avail_ssize = max_ssize - init_ssize;
3036         }
3037
3038         vm_map_unlock(map);
3039         vm_map_entry_release(count);
3040         return (rv);
3041 }
3042
3043 /* Attempts to grow a vm stack entry.  Returns KERN_SUCCESS if the
3044  * desired address is already mapped, or if we successfully grow
3045  * the stack.  Also returns KERN_SUCCESS if addr is outside the
3046  * stack range (this is strange, but preserves compatibility with
3047  * the grow function in vm_machdep.c).
3048  */
3049 int
3050 vm_map_growstack (struct proc *p, vm_offset_t addr)
3051 {
3052         vm_map_entry_t prev_entry;
3053         vm_map_entry_t stack_entry;
3054         vm_map_entry_t new_stack_entry;
3055         struct vmspace *vm = p->p_vmspace;
3056         vm_map_t map = &vm->vm_map;
3057         vm_offset_t    end;
3058         int grow_amount;
3059         int rv = KERN_SUCCESS;
3060         int is_procstack;
3061         int use_read_lock = 1;
3062         int count;
3063
3064         count = vm_map_entry_reserve(MAP_RESERVE_COUNT);
3065 Retry:
3066         if (use_read_lock)
3067                 vm_map_lock_read(map);
3068         else
3069                 vm_map_lock(map);
3070
3071         /* If addr is already in the entry range, no need to grow.*/
3072         if (vm_map_lookup_entry(map, addr, &prev_entry))
3073                 goto done;
3074
3075         if ((stack_entry = prev_entry->next) == &map->header)
3076                 goto done;
3077         if (prev_entry == &map->header) 
3078                 end = stack_entry->start - stack_entry->aux.avail_ssize;
3079         else
3080                 end = prev_entry->end;
3081
3082         /* This next test mimics the old grow function in vm_machdep.c.
3083          * It really doesn't quite make sense, but we do it anyway
3084          * for compatibility.
3085          *
3086          * If not growable stack, return success.  This signals the
3087          * caller to proceed as he would normally with normal vm.
3088          */
3089         if (stack_entry->aux.avail_ssize < 1 ||
3090             addr >= stack_entry->start ||
3091             addr <  stack_entry->start - stack_entry->aux.avail_ssize) {
3092                 goto done;
3093         } 
3094         
3095         /* Find the minimum grow amount */
3096         grow_amount = roundup (stack_entry->start - addr, PAGE_SIZE);
3097         if (grow_amount > stack_entry->aux.avail_ssize) {
3098                 rv = KERN_NO_SPACE;
3099                 goto done;
3100         }
3101
3102         /* If there is no longer enough space between the entries
3103          * nogo, and adjust the available space.  Note: this 
3104          * should only happen if the user has mapped into the
3105          * stack area after the stack was created, and is
3106          * probably an error.
3107          *
3108          * This also effectively destroys any guard page the user
3109          * might have intended by limiting the stack size.
3110          */
3111         if (grow_amount > stack_entry->start - end) {
3112                 if (use_read_lock && vm_map_lock_upgrade(map)) {
3113                         use_read_lock = 0;
3114                         goto Retry;
3115                 }
3116                 use_read_lock = 0;
3117                 stack_entry->aux.avail_ssize = stack_entry->start - end;
3118                 rv = KERN_NO_SPACE;
3119                 goto done;
3120         }
3121
3122         is_procstack = addr >= (vm_offset_t)vm->vm_maxsaddr;
3123
3124         /* If this is the main process stack, see if we're over the 
3125          * stack limit.
3126          */
3127         if (is_procstack && (ctob(vm->vm_ssize) + grow_amount >
3128                              p->p_rlimit[RLIMIT_STACK].rlim_cur)) {
3129                 rv = KERN_NO_SPACE;
3130                 goto done;
3131         }
3132
3133         /* Round up the grow amount modulo SGROWSIZ */
3134         grow_amount = roundup (grow_amount, sgrowsiz);
3135         if (grow_amount > stack_entry->aux.avail_ssize) {
3136                 grow_amount = stack_entry->aux.avail_ssize;
3137         }
3138         if (is_procstack && (ctob(vm->vm_ssize) + grow_amount >
3139                              p->p_rlimit[RLIMIT_STACK].rlim_cur)) {
3140                 grow_amount = p->p_rlimit[RLIMIT_STACK].rlim_cur -
3141                               ctob(vm->vm_ssize);
3142         }
3143
3144         /* If we would blow our VMEM resource limit, no go */
3145         if (map->size + grow_amount > p->p_rlimit[RLIMIT_VMEM].rlim_cur) {
3146                 rv = KERN_NO_SPACE;
3147                 goto done;
3148         }
3149
3150         if (use_read_lock && vm_map_lock_upgrade(map)) {
3151                 use_read_lock = 0;
3152                 goto Retry;
3153         }
3154         use_read_lock = 0;
3155
3156         /* Get the preliminary new entry start value */
3157         addr = stack_entry->start - grow_amount;
3158
3159         /* If this puts us into the previous entry, cut back our growth
3160          * to the available space.  Also, see the note above.
3161          */
3162         if (addr < end) {
3163                 stack_entry->aux.avail_ssize = stack_entry->start - end;
3164                 addr = end;
3165         }
3166
3167         rv = vm_map_insert(map, &count,
3168                            NULL, 0, addr, stack_entry->start,
3169                            VM_MAPTYPE_NORMAL,
3170                            VM_PROT_ALL, VM_PROT_ALL,
3171                            0);
3172
3173         /* Adjust the available stack space by the amount we grew. */
3174         if (rv == KERN_SUCCESS) {
3175                 if (prev_entry != &map->header)
3176                         vm_map_clip_end(map, prev_entry, addr, &count);
3177                 new_stack_entry = prev_entry->next;
3178                 if (new_stack_entry->end   != stack_entry->start  ||
3179                     new_stack_entry->start != addr)
3180                         panic ("Bad stack grow start/end in new stack entry");
3181                 else {
3182                         new_stack_entry->aux.avail_ssize =
3183                                 stack_entry->aux.avail_ssize -
3184                                 (new_stack_entry->end - new_stack_entry->start);
3185                         if (is_procstack)
3186                                 vm->vm_ssize += btoc(new_stack_entry->end -
3187                                                      new_stack_entry->start);
3188                 }
3189         }
3190
3191 done:
3192         if (use_read_lock)
3193                 vm_map_unlock_read(map);
3194         else
3195                 vm_map_unlock(map);
3196         vm_map_entry_release(count);
3197         return (rv);
3198 }
3199
3200 /*
3201  * Unshare the specified VM space for exec.  If other processes are
3202  * mapped to it, then create a new one.  The new vmspace is null.
3203  */
3204 void
3205 vmspace_exec(struct proc *p, struct vmspace *vmcopy) 
3206 {
3207         struct vmspace *oldvmspace = p->p_vmspace;
3208         struct vmspace *newvmspace;
3209         vm_map_t map = &p->p_vmspace->vm_map;
3210
3211         /*
3212          * If we are execing a resident vmspace we fork it, otherwise
3213          * we create a new vmspace.  Note that exitingcnt and upcalls
3214          * are not copied to the new vmspace.
3215          */
3216         if (vmcopy)  {
3217             newvmspace = vmspace_fork(vmcopy);
3218         } else {
3219             newvmspace = vmspace_alloc(map->min_offset, map->max_offset);
3220             bcopy(&oldvmspace->vm_startcopy, &newvmspace->vm_startcopy,
3221                 (caddr_t)&oldvmspace->vm_endcopy - 
3222                     (caddr_t)&oldvmspace->vm_startcopy);
3223         }
3224
3225         /*
3226          * Finish initializing the vmspace before assigning it
3227          * to the process.  The vmspace will become the current vmspace
3228          * if p == curproc.
3229          */
3230         pmap_pinit2(vmspace_pmap(newvmspace));
3231         pmap_replacevm(p, newvmspace, 0);
3232         sysref_put(&oldvmspace->vm_sysref);
3233 }
3234
3235 /*
3236  * Unshare the specified VM space for forcing COW.  This
3237  * is called by rfork, for the (RFMEM|RFPROC) == 0 case.
3238  *
3239  * The exitingcnt test is not strictly necessary but has been
3240  * included for code sanity (to make the code a bit more deterministic).
3241  */
3242
3243 void
3244 vmspace_unshare(struct proc *p) 
3245 {
3246         struct vmspace *oldvmspace = p->p_vmspace;
3247         struct vmspace *newvmspace;
3248
3249         if (oldvmspace->vm_sysref.refcnt == 1 && oldvmspace->vm_exitingcnt == 0)
3250                 return;
3251         newvmspace = vmspace_fork(oldvmspace);
3252         pmap_pinit2(vmspace_pmap(newvmspace));
3253         pmap_replacevm(p, newvmspace, 0);
3254         sysref_put(&oldvmspace->vm_sysref);
3255 }
3256
3257 /*
3258  *      vm_map_lookup:
3259  *
3260  *      Finds the VM object, offset, and
3261  *      protection for a given virtual address in the
3262  *      specified map, assuming a page fault of the
3263  *      type specified.
3264  *
3265  *      Leaves the map in question locked for read; return
3266  *      values are guaranteed until a vm_map_lookup_done
3267  *      call is performed.  Note that the map argument
3268  *      is in/out; the returned map must be used in
3269  *      the call to vm_map_lookup_done.
3270  *
3271  *      A handle (out_entry) is returned for use in
3272  *      vm_map_lookup_done, to make that fast.
3273  *
3274  *      If a lookup is requested with "write protection"
3275  *      specified, the map may be changed to perform virtual
3276  *      copying operations, although the data referenced will
3277  *      remain the same.
3278  */
3279 int
3280 vm_map_lookup(vm_map_t *var_map,                /* IN/OUT */
3281               vm_offset_t vaddr,
3282               vm_prot_t fault_typea,
3283               vm_map_entry_t *out_entry,        /* OUT */
3284               vm_object_t *object,              /* OUT */
3285               vm_pindex_t *pindex,              /* OUT */
3286               vm_prot_t *out_prot,              /* OUT */
3287               boolean_t *wired)                 /* OUT */
3288 {
3289         vm_map_entry_t entry;
3290         vm_map_t map = *var_map;
3291         vm_prot_t prot;
3292         vm_prot_t fault_type = fault_typea;
3293         int use_read_lock = 1;
3294         int rv = KERN_SUCCESS;
3295
3296 RetryLookup:
3297         if (use_read_lock)
3298                 vm_map_lock_read(map);
3299         else
3300                 vm_map_lock(map);
3301
3302         /*
3303          * If the map has an interesting hint, try it before calling full
3304          * blown lookup routine.
3305          */
3306         entry = map->hint;
3307         *out_entry = entry;
3308
3309         if ((entry == &map->header) ||
3310             (vaddr < entry->start) || (vaddr >= entry->end)) {
3311                 vm_map_entry_t tmp_entry;
3312
3313                 /*
3314                  * Entry was either not a valid hint, or the vaddr was not
3315                  * contained in the entry, so do a full lookup.
3316                  */
3317                 if (!vm_map_lookup_entry(map, vaddr, &tmp_entry)) {
3318                         rv = KERN_INVALID_ADDRESS;
3319                         goto done;
3320                 }
3321
3322                 entry = tmp_entry;
3323                 *out_entry = entry;
3324         }
3325         
3326         /*
3327          * Handle submaps.
3328          */
3329         if (entry->maptype == VM_MAPTYPE_SUBMAP) {
3330                 vm_map_t old_map = map;
3331
3332                 *var_map = map = entry->object.sub_map;
3333                 if (use_read_lock)
3334                         vm_map_unlock_read(old_map);
3335                 else
3336                         vm_map_unlock(old_map);
3337                 use_read_lock = 1;
3338                 goto RetryLookup;
3339         }
3340
3341         /*
3342          * Check whether this task is allowed to have this page.
3343          * Note the special case for MAP_ENTRY_COW
3344          * pages with an override.  This is to implement a forced
3345          * COW for debuggers.
3346          */
3347
3348         if (fault_type & VM_PROT_OVERRIDE_WRITE)
3349                 prot = entry->max_protection;
3350         else
3351                 prot = entry->protection;
3352
3353         fault_type &= (VM_PROT_READ|VM_PROT_WRITE|VM_PROT_EXECUTE);
3354         if ((fault_type & prot) != fault_type) {
3355                 rv = KERN_PROTECTION_FAILURE;
3356                 goto done;
3357         }
3358
3359         if ((entry->eflags & MAP_ENTRY_USER_WIRED) &&
3360             (entry->eflags & MAP_ENTRY_COW) &&
3361             (fault_type & VM_PROT_WRITE) &&
3362             (fault_typea & VM_PROT_OVERRIDE_WRITE) == 0) {
3363                 rv = KERN_PROTECTION_FAILURE;
3364                 goto done;
3365         }
3366
3367         /*
3368          * If this page is not pageable, we have to get it for all possible
3369          * accesses.
3370          */
3371         *wired = (entry->wired_count != 0);
3372         if (*wired)
3373                 prot = fault_type = entry->protection;
3374
3375         /*
3376          * Virtual page tables may need to update the accessed (A) bit
3377          * in a page table entry.  Upgrade the fault to a write fault for
3378          * that case if the map will support it.  If the map does not support
3379          * it the page table entry simply will not be updated.
3380          */
3381         if (entry->maptype == VM_MAPTYPE_VPAGETABLE) {
3382                 if (prot & VM_PROT_WRITE)
3383                         fault_type |= VM_PROT_WRITE;
3384         }
3385
3386         /*
3387          * If the entry was copy-on-write, we either ...
3388          */
3389         if (entry->eflags & MAP_ENTRY_NEEDS_COPY) {
3390                 /*
3391                  * If we want to write the page, we may as well handle that
3392                  * now since we've got the map locked.
3393                  *
3394                  * If we don't need to write the page, we just demote the
3395                  * permissions allowed.
3396                  */
3397
3398                 if (fault_type & VM_PROT_WRITE) {
3399                         /*
3400                          * Make a new object, and place it in the object
3401                          * chain.  Note that no new references have appeared
3402                          * -- one just moved from the map to the new
3403                          * object.
3404                          */
3405
3406                         if (use_read_lock && vm_map_lock_upgrade(map)) {
3407                                 use_read_lock = 0;
3408                                 goto RetryLookup;
3409                         }
3410                         use_read_lock = 0;
3411
3412                         vm_map_entry_shadow(entry);
3413                 } else {
3414                         /*
3415                          * We're attempting to read a copy-on-write page --
3416                          * don't allow writes.
3417                          */
3418
3419                         prot &= ~VM_PROT_WRITE;
3420                 }
3421         }
3422
3423         /*
3424          * Create an object if necessary.
3425          */
3426         if (entry->object.vm_object == NULL &&
3427             !map->system_map) {
3428                 if (use_read_lock && vm_map_lock_upgrade(map))  {
3429                         use_read_lock = 0;
3430                         goto RetryLookup;
3431                 }
3432                 use_read_lock = 0;
3433                 vm_map_entry_allocate_object(entry);
3434         }
3435
3436         /*
3437          * Return the object/offset from this entry.  If the entry was
3438          * copy-on-write or empty, it has been fixed up.
3439          */
3440
3441         *pindex = OFF_TO_IDX((vaddr - entry->start) + entry->offset);
3442         *object = entry->object.vm_object;
3443
3444         /*
3445          * Return whether this is the only map sharing this data.  On
3446          * success we return with a read lock held on the map.  On failure
3447          * we return with the map unlocked.
3448          */
3449         *out_prot = prot;
3450 done:
3451         if (rv == KERN_SUCCESS) {
3452                 if (use_read_lock == 0)
3453                         vm_map_lock_downgrade(map);
3454         } else if (use_read_lock) {
3455                 vm_map_unlock_read(map);
3456         } else {
3457                 vm_map_unlock(map);
3458         }
3459         return (rv);
3460 }
3461
3462 /*
3463  *      vm_map_lookup_done:
3464  *
3465  *      Releases locks acquired by a vm_map_lookup
3466  *      (according to the handle returned by that lookup).
3467  */
3468
3469 void
3470 vm_map_lookup_done(vm_map_t map, vm_map_entry_t entry, int count)
3471 {
3472         /*
3473          * Unlock the main-level map
3474          */
3475         vm_map_unlock_read(map);
3476         if (count)
3477                 vm_map_entry_release(count);
3478 }
3479
3480 #include "opt_ddb.h"
3481 #ifdef DDB
3482 #include <sys/kernel.h>
3483
3484 #include <ddb/ddb.h>
3485
3486 /*
3487  *      vm_map_print:   [ debug ]
3488  */
3489 DB_SHOW_COMMAND(map, vm_map_print)
3490 {
3491         static int nlines;
3492         /* XXX convert args. */
3493         vm_map_t map = (vm_map_t)addr;
3494         boolean_t full = have_addr;
3495
3496         vm_map_entry_t entry;
3497
3498         db_iprintf("Task map %p: pmap=%p, nentries=%d, version=%u\n",
3499             (void *)map,
3500             (void *)map->pmap, map->nentries, map->timestamp);
3501         nlines++;
3502
3503         if (!full && db_indent)
3504                 return;
3505
3506         db_indent += 2;
3507         for (entry = map->header.next; entry != &map->header;
3508             entry = entry->next) {
3509                 db_iprintf("map entry %p: start=%p, end=%p\n",
3510                     (void *)entry, (void *)entry->start, (void *)entry->end);
3511                 nlines++;
3512                 {
3513                         static char *inheritance_name[4] =
3514                         {"share", "copy", "none", "donate_copy"};
3515
3516                         db_iprintf(" prot=%x/%x/%s",
3517                             entry->protection,
3518                             entry->max_protection,
3519                             inheritance_name[(int)(unsigned char)entry->inheritance]);
3520                         if (entry->wired_count != 0)
3521                                 db_printf(", wired");
3522                 }
3523                 if (entry->maptype == VM_MAPTYPE_SUBMAP) {
3524                         /* XXX no %qd in kernel.  Truncate entry->offset. */
3525                         db_printf(", share=%p, offset=0x%lx\n",
3526                             (void *)entry->object.sub_map,
3527                             (long)entry->offset);
3528                         nlines++;
3529                         if ((entry->prev == &map->header) ||
3530                             (entry->prev->object.sub_map !=
3531                                 entry->object.sub_map)) {
3532                                 db_indent += 2;
3533                                 vm_map_print((db_expr_t)(intptr_t)
3534                                              entry->object.sub_map,
3535                                              full, 0, (char *)0);
3536                                 db_indent -= 2;
3537                         }
3538                 } else {
3539                         /* XXX no %qd in kernel.  Truncate entry->offset. */
3540                         db_printf(", object=%p, offset=0x%lx",
3541                             (void *)entry->object.vm_object,
3542                             (long)entry->offset);
3543                         if (entry->eflags & MAP_ENTRY_COW)
3544                                 db_printf(", copy (%s)",
3545                                     (entry->eflags & MAP_ENTRY_NEEDS_COPY) ? "needed" : "done");
3546                         db_printf("\n");
3547                         nlines++;
3548
3549                         if ((entry->prev == &map->header) ||
3550                             (entry->prev->object.vm_object !=
3551                                 entry->object.vm_object)) {
3552                                 db_indent += 2;
3553                                 vm_object_print((db_expr_t)(intptr_t)
3554                                                 entry->object.vm_object,
3555                                                 full, 0, (char *)0);
3556                                 nlines += 4;
3557                                 db_indent -= 2;
3558                         }
3559                 }
3560         }
3561         db_indent -= 2;
3562         if (db_indent == 0)
3563                 nlines = 0;
3564 }
3565
3566
3567 DB_SHOW_COMMAND(procvm, procvm)
3568 {
3569         struct proc *p;
3570
3571         if (have_addr) {
3572                 p = (struct proc *) addr;
3573         } else {
3574                 p = curproc;
3575         }
3576
3577         db_printf("p = %p, vmspace = %p, map = %p, pmap = %p\n",
3578             (void *)p, (void *)p->p_vmspace, (void *)&p->p_vmspace->vm_map,
3579             (void *)vmspace_pmap(p->p_vmspace));
3580
3581         vm_map_print((db_expr_t)(intptr_t)&p->p_vmspace->vm_map, 1, 0, NULL);
3582 }
3583
3584 #endif /* DDB */