xref: /freebsd/sys/vm/vm_map.c (revision d184218c18d067f8fd47203f54ab02a7b2ed9b11)
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  * 4. Neither the name of the University nor the names of its contributors
17  *    may be used to endorse or promote products derived from this software
18  *    without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  *
32  *	from: @(#)vm_map.c	8.3 (Berkeley) 1/12/94
33  *
34  *
35  * Copyright (c) 1987, 1990 Carnegie-Mellon University.
36  * All rights reserved.
37  *
38  * Authors: Avadis Tevanian, Jr., Michael Wayne Young
39  *
40  * Permission to use, copy, modify and distribute this software and
41  * its documentation is hereby granted, provided that both the copyright
42  * notice and this permission notice appear in all copies of the
43  * software, derivative works or modified versions, and any portions
44  * thereof, and that both notices appear in supporting documentation.
45  *
46  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
47  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
48  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
49  *
50  * Carnegie Mellon requests users of this software to return to
51  *
52  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
53  *  School of Computer Science
54  *  Carnegie Mellon University
55  *  Pittsburgh PA 15213-3890
56  *
57  * any improvements or extensions that they make and grant Carnegie the
58  * rights to redistribute these changes.
59  */
60 
61 /*
62  *	Virtual memory mapping module.
63  */
64 
65 #include <sys/cdefs.h>
66 __FBSDID("$FreeBSD$");
67 
68 #include <sys/param.h>
69 #include <sys/systm.h>
70 #include <sys/kernel.h>
71 #include <sys/ktr.h>
72 #include <sys/lock.h>
73 #include <sys/mutex.h>
74 #include <sys/proc.h>
75 #include <sys/vmmeter.h>
76 #include <sys/mman.h>
77 #include <sys/vnode.h>
78 #include <sys/racct.h>
79 #include <sys/resourcevar.h>
80 #include <sys/rwlock.h>
81 #include <sys/file.h>
82 #include <sys/sysctl.h>
83 #include <sys/sysent.h>
84 #include <sys/shm.h>
85 
86 #include <vm/vm.h>
87 #include <vm/vm_param.h>
88 #include <vm/pmap.h>
89 #include <vm/vm_map.h>
90 #include <vm/vm_page.h>
91 #include <vm/vm_object.h>
92 #include <vm/vm_pager.h>
93 #include <vm/vm_kern.h>
94 #include <vm/vm_extern.h>
95 #include <vm/vnode_pager.h>
96 #include <vm/swap_pager.h>
97 #include <vm/uma.h>
98 
99 /*
100  *	Virtual memory maps provide for the mapping, protection,
101  *	and sharing of virtual memory objects.  In addition,
102  *	this module provides for an efficient virtual copy of
103  *	memory from one map to another.
104  *
105  *	Synchronization is required prior to most operations.
106  *
107  *	Maps consist of an ordered doubly-linked list of simple
108  *	entries; a self-adjusting binary search tree of these
109  *	entries 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 struct mtx map_sleep_mtx;
125 static uma_zone_t mapentzone;
126 static uma_zone_t kmapentzone;
127 static uma_zone_t mapzone;
128 static uma_zone_t vmspace_zone;
129 static int vmspace_zinit(void *mem, int size, int flags);
130 static void vmspace_zfini(void *mem, int size);
131 static int vm_map_zinit(void *mem, int ize, int flags);
132 static void vm_map_zfini(void *mem, int size);
133 static void _vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min,
134     vm_offset_t max);
135 static void vm_map_entry_deallocate(vm_map_entry_t entry, boolean_t system_map);
136 static void vm_map_entry_dispose(vm_map_t map, vm_map_entry_t entry);
137 #ifdef INVARIANTS
138 static void vm_map_zdtor(void *mem, int size, void *arg);
139 static void vmspace_zdtor(void *mem, int size, void *arg);
140 #endif
141 
142 #define	ENTRY_CHARGED(e) ((e)->cred != NULL || \
143     ((e)->object.vm_object != NULL && (e)->object.vm_object->cred != NULL && \
144      !((e)->eflags & MAP_ENTRY_NEEDS_COPY)))
145 
146 /*
147  * PROC_VMSPACE_{UN,}LOCK() can be a noop as long as vmspaces are type
148  * stable.
149  */
150 #define PROC_VMSPACE_LOCK(p) do { } while (0)
151 #define PROC_VMSPACE_UNLOCK(p) do { } while (0)
152 
153 /*
154  *	VM_MAP_RANGE_CHECK:	[ internal use only ]
155  *
156  *	Asserts that the starting and ending region
157  *	addresses fall within the valid range of the map.
158  */
159 #define	VM_MAP_RANGE_CHECK(map, start, end)		\
160 		{					\
161 		if (start < vm_map_min(map))		\
162 			start = vm_map_min(map);	\
163 		if (end > vm_map_max(map))		\
164 			end = vm_map_max(map);		\
165 		if (start > end)			\
166 			start = end;			\
167 		}
168 
169 /*
170  *	vm_map_startup:
171  *
172  *	Initialize the vm_map module.  Must be called before
173  *	any other vm_map routines.
174  *
175  *	Map and entry structures are allocated from the general
176  *	purpose memory pool with some exceptions:
177  *
178  *	- The kernel map and kmem submap are allocated statically.
179  *	- Kernel map entries are allocated out of a static pool.
180  *
181  *	These restrictions are necessary since malloc() uses the
182  *	maps and requires map entries.
183  */
184 
185 void
186 vm_map_startup(void)
187 {
188 	mtx_init(&map_sleep_mtx, "vm map sleep mutex", NULL, MTX_DEF);
189 	mapzone = uma_zcreate("MAP", sizeof(struct vm_map), NULL,
190 #ifdef INVARIANTS
191 	    vm_map_zdtor,
192 #else
193 	    NULL,
194 #endif
195 	    vm_map_zinit, vm_map_zfini, UMA_ALIGN_PTR, UMA_ZONE_NOFREE);
196 	uma_prealloc(mapzone, MAX_KMAP);
197 	kmapentzone = uma_zcreate("KMAP ENTRY", sizeof(struct vm_map_entry),
198 	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR,
199 	    UMA_ZONE_MTXCLASS | UMA_ZONE_VM);
200 	uma_prealloc(kmapentzone, MAX_KMAPENT);
201 	mapentzone = uma_zcreate("MAP ENTRY", sizeof(struct vm_map_entry),
202 	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0);
203 }
204 
205 static void
206 vmspace_zfini(void *mem, int size)
207 {
208 	struct vmspace *vm;
209 
210 	vm = (struct vmspace *)mem;
211 	vm_map_zfini(&vm->vm_map, sizeof(vm->vm_map));
212 }
213 
214 static int
215 vmspace_zinit(void *mem, int size, int flags)
216 {
217 	struct vmspace *vm;
218 
219 	vm = (struct vmspace *)mem;
220 
221 	vm->vm_map.pmap = NULL;
222 	(void)vm_map_zinit(&vm->vm_map, sizeof(vm->vm_map), flags);
223 	return (0);
224 }
225 
226 static void
227 vm_map_zfini(void *mem, int size)
228 {
229 	vm_map_t map;
230 
231 	map = (vm_map_t)mem;
232 	mtx_destroy(&map->system_mtx);
233 	sx_destroy(&map->lock);
234 }
235 
236 static int
237 vm_map_zinit(void *mem, int size, int flags)
238 {
239 	vm_map_t map;
240 
241 	map = (vm_map_t)mem;
242 	map->nentries = 0;
243 	map->size = 0;
244 	mtx_init(&map->system_mtx, "vm map (system)", NULL, MTX_DEF | MTX_DUPOK);
245 	sx_init(&map->lock, "vm map (user)");
246 	return (0);
247 }
248 
249 #ifdef INVARIANTS
250 static void
251 vmspace_zdtor(void *mem, int size, void *arg)
252 {
253 	struct vmspace *vm;
254 
255 	vm = (struct vmspace *)mem;
256 
257 	vm_map_zdtor(&vm->vm_map, sizeof(vm->vm_map), arg);
258 }
259 static void
260 vm_map_zdtor(void *mem, int size, void *arg)
261 {
262 	vm_map_t map;
263 
264 	map = (vm_map_t)mem;
265 	KASSERT(map->nentries == 0,
266 	    ("map %p nentries == %d on free.",
267 	    map, map->nentries));
268 	KASSERT(map->size == 0,
269 	    ("map %p size == %lu on free.",
270 	    map, (unsigned long)map->size));
271 }
272 #endif	/* INVARIANTS */
273 
274 /*
275  * Allocate a vmspace structure, including a vm_map and pmap,
276  * and initialize those structures.  The refcnt is set to 1.
277  */
278 struct vmspace *
279 vmspace_alloc(min, max)
280 	vm_offset_t min, max;
281 {
282 	struct vmspace *vm;
283 
284 	vm = uma_zalloc(vmspace_zone, M_WAITOK);
285 	if (vm->vm_map.pmap == NULL && !pmap_pinit(vmspace_pmap(vm))) {
286 		uma_zfree(vmspace_zone, vm);
287 		return (NULL);
288 	}
289 	CTR1(KTR_VM, "vmspace_alloc: %p", vm);
290 	_vm_map_init(&vm->vm_map, vmspace_pmap(vm), min, max);
291 	vm->vm_refcnt = 1;
292 	vm->vm_shm = NULL;
293 	vm->vm_swrss = 0;
294 	vm->vm_tsize = 0;
295 	vm->vm_dsize = 0;
296 	vm->vm_ssize = 0;
297 	vm->vm_taddr = 0;
298 	vm->vm_daddr = 0;
299 	vm->vm_maxsaddr = 0;
300 	return (vm);
301 }
302 
303 void
304 vm_init2(void)
305 {
306 	uma_zone_reserve_kva(kmapentzone, lmin(cnt.v_page_count,
307 	    (VM_MAX_KERNEL_ADDRESS - VM_MIN_KERNEL_ADDRESS) / PAGE_SIZE) / 8 +
308 	     maxproc * 2 + maxfiles);
309 	vmspace_zone = uma_zcreate("VMSPACE", sizeof(struct vmspace), NULL,
310 #ifdef INVARIANTS
311 	    vmspace_zdtor,
312 #else
313 	    NULL,
314 #endif
315 	    vmspace_zinit, vmspace_zfini, UMA_ALIGN_PTR, UMA_ZONE_NOFREE);
316 }
317 
318 static void
319 vmspace_container_reset(struct proc *p)
320 {
321 
322 #ifdef RACCT
323 	PROC_LOCK(p);
324 	racct_set(p, RACCT_DATA, 0);
325 	racct_set(p, RACCT_STACK, 0);
326 	racct_set(p, RACCT_RSS, 0);
327 	racct_set(p, RACCT_MEMLOCK, 0);
328 	racct_set(p, RACCT_VMEM, 0);
329 	PROC_UNLOCK(p);
330 #endif
331 }
332 
333 static inline void
334 vmspace_dofree(struct vmspace *vm)
335 {
336 
337 	CTR1(KTR_VM, "vmspace_free: %p", vm);
338 
339 	/*
340 	 * Make sure any SysV shm is freed, it might not have been in
341 	 * exit1().
342 	 */
343 	shmexit(vm);
344 
345 	/*
346 	 * Lock the map, to wait out all other references to it.
347 	 * Delete all of the mappings and pages they hold, then call
348 	 * the pmap module to reclaim anything left.
349 	 */
350 	(void)vm_map_remove(&vm->vm_map, vm->vm_map.min_offset,
351 	    vm->vm_map.max_offset);
352 
353 	pmap_release(vmspace_pmap(vm));
354 	vm->vm_map.pmap = NULL;
355 	uma_zfree(vmspace_zone, vm);
356 }
357 
358 void
359 vmspace_free(struct vmspace *vm)
360 {
361 
362 	if (vm->vm_refcnt == 0)
363 		panic("vmspace_free: attempt to free already freed vmspace");
364 
365 	if (atomic_fetchadd_int(&vm->vm_refcnt, -1) == 1)
366 		vmspace_dofree(vm);
367 }
368 
369 void
370 vmspace_exitfree(struct proc *p)
371 {
372 	struct vmspace *vm;
373 
374 	PROC_VMSPACE_LOCK(p);
375 	vm = p->p_vmspace;
376 	p->p_vmspace = NULL;
377 	PROC_VMSPACE_UNLOCK(p);
378 	KASSERT(vm == &vmspace0, ("vmspace_exitfree: wrong vmspace"));
379 	vmspace_free(vm);
380 }
381 
382 void
383 vmspace_exit(struct thread *td)
384 {
385 	int refcnt;
386 	struct vmspace *vm;
387 	struct proc *p;
388 
389 	/*
390 	 * Release user portion of address space.
391 	 * This releases references to vnodes,
392 	 * which could cause I/O if the file has been unlinked.
393 	 * Need to do this early enough that we can still sleep.
394 	 *
395 	 * The last exiting process to reach this point releases as
396 	 * much of the environment as it can. vmspace_dofree() is the
397 	 * slower fallback in case another process had a temporary
398 	 * reference to the vmspace.
399 	 */
400 
401 	p = td->td_proc;
402 	vm = p->p_vmspace;
403 	atomic_add_int(&vmspace0.vm_refcnt, 1);
404 	do {
405 		refcnt = vm->vm_refcnt;
406 		if (refcnt > 1 && p->p_vmspace != &vmspace0) {
407 			/* Switch now since other proc might free vmspace */
408 			PROC_VMSPACE_LOCK(p);
409 			p->p_vmspace = &vmspace0;
410 			PROC_VMSPACE_UNLOCK(p);
411 			pmap_activate(td);
412 		}
413 	} while (!atomic_cmpset_int(&vm->vm_refcnt, refcnt, refcnt - 1));
414 	if (refcnt == 1) {
415 		if (p->p_vmspace != vm) {
416 			/* vmspace not yet freed, switch back */
417 			PROC_VMSPACE_LOCK(p);
418 			p->p_vmspace = vm;
419 			PROC_VMSPACE_UNLOCK(p);
420 			pmap_activate(td);
421 		}
422 		pmap_remove_pages(vmspace_pmap(vm));
423 		/* Switch now since this proc will free vmspace */
424 		PROC_VMSPACE_LOCK(p);
425 		p->p_vmspace = &vmspace0;
426 		PROC_VMSPACE_UNLOCK(p);
427 		pmap_activate(td);
428 		vmspace_dofree(vm);
429 	}
430 	vmspace_container_reset(p);
431 }
432 
433 /* Acquire reference to vmspace owned by another process. */
434 
435 struct vmspace *
436 vmspace_acquire_ref(struct proc *p)
437 {
438 	struct vmspace *vm;
439 	int refcnt;
440 
441 	PROC_VMSPACE_LOCK(p);
442 	vm = p->p_vmspace;
443 	if (vm == NULL) {
444 		PROC_VMSPACE_UNLOCK(p);
445 		return (NULL);
446 	}
447 	do {
448 		refcnt = vm->vm_refcnt;
449 		if (refcnt <= 0) { 	/* Avoid 0->1 transition */
450 			PROC_VMSPACE_UNLOCK(p);
451 			return (NULL);
452 		}
453 	} while (!atomic_cmpset_int(&vm->vm_refcnt, refcnt, refcnt + 1));
454 	if (vm != p->p_vmspace) {
455 		PROC_VMSPACE_UNLOCK(p);
456 		vmspace_free(vm);
457 		return (NULL);
458 	}
459 	PROC_VMSPACE_UNLOCK(p);
460 	return (vm);
461 }
462 
463 void
464 _vm_map_lock(vm_map_t map, const char *file, int line)
465 {
466 
467 	if (map->system_map)
468 		mtx_lock_flags_(&map->system_mtx, 0, file, line);
469 	else
470 		sx_xlock_(&map->lock, file, line);
471 	map->timestamp++;
472 }
473 
474 static void
475 vm_map_process_deferred(void)
476 {
477 	struct thread *td;
478 	vm_map_entry_t entry, next;
479 	vm_object_t object;
480 
481 	td = curthread;
482 	entry = td->td_map_def_user;
483 	td->td_map_def_user = NULL;
484 	while (entry != NULL) {
485 		next = entry->next;
486 		if ((entry->eflags & MAP_ENTRY_VN_WRITECNT) != 0) {
487 			/*
488 			 * Decrement the object's writemappings and
489 			 * possibly the vnode's v_writecount.
490 			 */
491 			KASSERT((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0,
492 			    ("Submap with writecount"));
493 			object = entry->object.vm_object;
494 			KASSERT(object != NULL, ("No object for writecount"));
495 			vnode_pager_release_writecount(object, entry->start,
496 			    entry->end);
497 		}
498 		vm_map_entry_deallocate(entry, FALSE);
499 		entry = next;
500 	}
501 }
502 
503 void
504 _vm_map_unlock(vm_map_t map, const char *file, int line)
505 {
506 
507 	if (map->system_map)
508 		mtx_unlock_flags_(&map->system_mtx, 0, file, line);
509 	else {
510 		sx_xunlock_(&map->lock, file, line);
511 		vm_map_process_deferred();
512 	}
513 }
514 
515 void
516 _vm_map_lock_read(vm_map_t map, const char *file, int line)
517 {
518 
519 	if (map->system_map)
520 		mtx_lock_flags_(&map->system_mtx, 0, file, line);
521 	else
522 		sx_slock_(&map->lock, file, line);
523 }
524 
525 void
526 _vm_map_unlock_read(vm_map_t map, const char *file, int line)
527 {
528 
529 	if (map->system_map)
530 		mtx_unlock_flags_(&map->system_mtx, 0, file, line);
531 	else {
532 		sx_sunlock_(&map->lock, file, line);
533 		vm_map_process_deferred();
534 	}
535 }
536 
537 int
538 _vm_map_trylock(vm_map_t map, const char *file, int line)
539 {
540 	int error;
541 
542 	error = map->system_map ?
543 	    !mtx_trylock_flags_(&map->system_mtx, 0, file, line) :
544 	    !sx_try_xlock_(&map->lock, file, line);
545 	if (error == 0)
546 		map->timestamp++;
547 	return (error == 0);
548 }
549 
550 int
551 _vm_map_trylock_read(vm_map_t map, const char *file, int line)
552 {
553 	int error;
554 
555 	error = map->system_map ?
556 	    !mtx_trylock_flags_(&map->system_mtx, 0, file, line) :
557 	    !sx_try_slock_(&map->lock, file, line);
558 	return (error == 0);
559 }
560 
561 /*
562  *	_vm_map_lock_upgrade:	[ internal use only ]
563  *
564  *	Tries to upgrade a read (shared) lock on the specified map to a write
565  *	(exclusive) lock.  Returns the value "0" if the upgrade succeeds and a
566  *	non-zero value if the upgrade fails.  If the upgrade fails, the map is
567  *	returned without a read or write lock held.
568  *
569  *	Requires that the map be read locked.
570  */
571 int
572 _vm_map_lock_upgrade(vm_map_t map, const char *file, int line)
573 {
574 	unsigned int last_timestamp;
575 
576 	if (map->system_map) {
577 		mtx_assert_(&map->system_mtx, MA_OWNED, file, line);
578 	} else {
579 		if (!sx_try_upgrade_(&map->lock, file, line)) {
580 			last_timestamp = map->timestamp;
581 			sx_sunlock_(&map->lock, file, line);
582 			vm_map_process_deferred();
583 			/*
584 			 * If the map's timestamp does not change while the
585 			 * map is unlocked, then the upgrade succeeds.
586 			 */
587 			sx_xlock_(&map->lock, file, line);
588 			if (last_timestamp != map->timestamp) {
589 				sx_xunlock_(&map->lock, file, line);
590 				return (1);
591 			}
592 		}
593 	}
594 	map->timestamp++;
595 	return (0);
596 }
597 
598 void
599 _vm_map_lock_downgrade(vm_map_t map, const char *file, int line)
600 {
601 
602 	if (map->system_map) {
603 		mtx_assert_(&map->system_mtx, MA_OWNED, file, line);
604 	} else
605 		sx_downgrade_(&map->lock, file, line);
606 }
607 
608 /*
609  *	vm_map_locked:
610  *
611  *	Returns a non-zero value if the caller holds a write (exclusive) lock
612  *	on the specified map and the value "0" otherwise.
613  */
614 int
615 vm_map_locked(vm_map_t map)
616 {
617 
618 	if (map->system_map)
619 		return (mtx_owned(&map->system_mtx));
620 	else
621 		return (sx_xlocked(&map->lock));
622 }
623 
624 #ifdef INVARIANTS
625 static void
626 _vm_map_assert_locked(vm_map_t map, const char *file, int line)
627 {
628 
629 	if (map->system_map)
630 		mtx_assert_(&map->system_mtx, MA_OWNED, file, line);
631 	else
632 		sx_assert_(&map->lock, SA_XLOCKED, file, line);
633 }
634 
635 #define	VM_MAP_ASSERT_LOCKED(map) \
636     _vm_map_assert_locked(map, LOCK_FILE, LOCK_LINE)
637 #else
638 #define	VM_MAP_ASSERT_LOCKED(map)
639 #endif
640 
641 /*
642  *	_vm_map_unlock_and_wait:
643  *
644  *	Atomically releases the lock on the specified map and puts the calling
645  *	thread to sleep.  The calling thread will remain asleep until either
646  *	vm_map_wakeup() is performed on the map or the specified timeout is
647  *	exceeded.
648  *
649  *	WARNING!  This function does not perform deferred deallocations of
650  *	objects and map	entries.  Therefore, the calling thread is expected to
651  *	reacquire the map lock after reawakening and later perform an ordinary
652  *	unlock operation, such as vm_map_unlock(), before completing its
653  *	operation on the map.
654  */
655 int
656 _vm_map_unlock_and_wait(vm_map_t map, int timo, const char *file, int line)
657 {
658 
659 	mtx_lock(&map_sleep_mtx);
660 	if (map->system_map)
661 		mtx_unlock_flags_(&map->system_mtx, 0, file, line);
662 	else
663 		sx_xunlock_(&map->lock, file, line);
664 	return (msleep(&map->root, &map_sleep_mtx, PDROP | PVM, "vmmaps",
665 	    timo));
666 }
667 
668 /*
669  *	vm_map_wakeup:
670  *
671  *	Awaken any threads that have slept on the map using
672  *	vm_map_unlock_and_wait().
673  */
674 void
675 vm_map_wakeup(vm_map_t map)
676 {
677 
678 	/*
679 	 * Acquire and release map_sleep_mtx to prevent a wakeup()
680 	 * from being performed (and lost) between the map unlock
681 	 * and the msleep() in _vm_map_unlock_and_wait().
682 	 */
683 	mtx_lock(&map_sleep_mtx);
684 	mtx_unlock(&map_sleep_mtx);
685 	wakeup(&map->root);
686 }
687 
688 void
689 vm_map_busy(vm_map_t map)
690 {
691 
692 	VM_MAP_ASSERT_LOCKED(map);
693 	map->busy++;
694 }
695 
696 void
697 vm_map_unbusy(vm_map_t map)
698 {
699 
700 	VM_MAP_ASSERT_LOCKED(map);
701 	KASSERT(map->busy, ("vm_map_unbusy: not busy"));
702 	if (--map->busy == 0 && (map->flags & MAP_BUSY_WAKEUP)) {
703 		vm_map_modflags(map, 0, MAP_BUSY_WAKEUP);
704 		wakeup(&map->busy);
705 	}
706 }
707 
708 void
709 vm_map_wait_busy(vm_map_t map)
710 {
711 
712 	VM_MAP_ASSERT_LOCKED(map);
713 	while (map->busy) {
714 		vm_map_modflags(map, MAP_BUSY_WAKEUP, 0);
715 		if (map->system_map)
716 			msleep(&map->busy, &map->system_mtx, 0, "mbusy", 0);
717 		else
718 			sx_sleep(&map->busy, &map->lock, 0, "mbusy", 0);
719 	}
720 	map->timestamp++;
721 }
722 
723 long
724 vmspace_resident_count(struct vmspace *vmspace)
725 {
726 	return pmap_resident_count(vmspace_pmap(vmspace));
727 }
728 
729 /*
730  *	vm_map_create:
731  *
732  *	Creates and returns a new empty VM map with
733  *	the given physical map structure, and having
734  *	the given lower and upper address bounds.
735  */
736 vm_map_t
737 vm_map_create(pmap_t pmap, vm_offset_t min, vm_offset_t max)
738 {
739 	vm_map_t result;
740 
741 	result = uma_zalloc(mapzone, M_WAITOK);
742 	CTR1(KTR_VM, "vm_map_create: %p", result);
743 	_vm_map_init(result, pmap, min, max);
744 	return (result);
745 }
746 
747 /*
748  * Initialize an existing vm_map structure
749  * such as that in the vmspace structure.
750  */
751 static void
752 _vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min, vm_offset_t max)
753 {
754 
755 	map->header.next = map->header.prev = &map->header;
756 	map->needs_wakeup = FALSE;
757 	map->system_map = 0;
758 	map->pmap = pmap;
759 	map->min_offset = min;
760 	map->max_offset = max;
761 	map->flags = 0;
762 	map->root = NULL;
763 	map->timestamp = 0;
764 	map->busy = 0;
765 }
766 
767 void
768 vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min, vm_offset_t max)
769 {
770 
771 	_vm_map_init(map, pmap, min, max);
772 	mtx_init(&map->system_mtx, "system map", NULL, MTX_DEF | MTX_DUPOK);
773 	sx_init(&map->lock, "user map");
774 }
775 
776 /*
777  *	vm_map_entry_dispose:	[ internal use only ]
778  *
779  *	Inverse of vm_map_entry_create.
780  */
781 static void
782 vm_map_entry_dispose(vm_map_t map, vm_map_entry_t entry)
783 {
784 	uma_zfree(map->system_map ? kmapentzone : mapentzone, entry);
785 }
786 
787 /*
788  *	vm_map_entry_create:	[ internal use only ]
789  *
790  *	Allocates a VM map entry for insertion.
791  *	No entry fields are filled in.
792  */
793 static vm_map_entry_t
794 vm_map_entry_create(vm_map_t map)
795 {
796 	vm_map_entry_t new_entry;
797 
798 	if (map->system_map)
799 		new_entry = uma_zalloc(kmapentzone, M_NOWAIT);
800 	else
801 		new_entry = uma_zalloc(mapentzone, M_WAITOK);
802 	if (new_entry == NULL)
803 		panic("vm_map_entry_create: kernel resources exhausted");
804 	return (new_entry);
805 }
806 
807 /*
808  *	vm_map_entry_set_behavior:
809  *
810  *	Set the expected access behavior, either normal, random, or
811  *	sequential.
812  */
813 static inline void
814 vm_map_entry_set_behavior(vm_map_entry_t entry, u_char behavior)
815 {
816 	entry->eflags = (entry->eflags & ~MAP_ENTRY_BEHAV_MASK) |
817 	    (behavior & MAP_ENTRY_BEHAV_MASK);
818 }
819 
820 /*
821  *	vm_map_entry_set_max_free:
822  *
823  *	Set the max_free field in a vm_map_entry.
824  */
825 static inline void
826 vm_map_entry_set_max_free(vm_map_entry_t entry)
827 {
828 
829 	entry->max_free = entry->adj_free;
830 	if (entry->left != NULL && entry->left->max_free > entry->max_free)
831 		entry->max_free = entry->left->max_free;
832 	if (entry->right != NULL && entry->right->max_free > entry->max_free)
833 		entry->max_free = entry->right->max_free;
834 }
835 
836 /*
837  *	vm_map_entry_splay:
838  *
839  *	The Sleator and Tarjan top-down splay algorithm with the
840  *	following variation.  Max_free must be computed bottom-up, so
841  *	on the downward pass, maintain the left and right spines in
842  *	reverse order.  Then, make a second pass up each side to fix
843  *	the pointers and compute max_free.  The time bound is O(log n)
844  *	amortized.
845  *
846  *	The new root is the vm_map_entry containing "addr", or else an
847  *	adjacent entry (lower or higher) if addr is not in the tree.
848  *
849  *	The map must be locked, and leaves it so.
850  *
851  *	Returns: the new root.
852  */
853 static vm_map_entry_t
854 vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
855 {
856 	vm_map_entry_t llist, rlist;
857 	vm_map_entry_t ltree, rtree;
858 	vm_map_entry_t y;
859 
860 	/* Special case of empty tree. */
861 	if (root == NULL)
862 		return (root);
863 
864 	/*
865 	 * Pass One: Splay down the tree until we find addr or a NULL
866 	 * pointer where addr would go.  llist and rlist are the two
867 	 * sides in reverse order (bottom-up), with llist linked by
868 	 * the right pointer and rlist linked by the left pointer in
869 	 * the vm_map_entry.  Wait until Pass Two to set max_free on
870 	 * the two spines.
871 	 */
872 	llist = NULL;
873 	rlist = NULL;
874 	for (;;) {
875 		/* root is never NULL in here. */
876 		if (addr < root->start) {
877 			y = root->left;
878 			if (y == NULL)
879 				break;
880 			if (addr < y->start && y->left != NULL) {
881 				/* Rotate right and put y on rlist. */
882 				root->left = y->right;
883 				y->right = root;
884 				vm_map_entry_set_max_free(root);
885 				root = y->left;
886 				y->left = rlist;
887 				rlist = y;
888 			} else {
889 				/* Put root on rlist. */
890 				root->left = rlist;
891 				rlist = root;
892 				root = y;
893 			}
894 		} else if (addr >= root->end) {
895 			y = root->right;
896 			if (y == NULL)
897 				break;
898 			if (addr >= y->end && y->right != NULL) {
899 				/* Rotate left and put y on llist. */
900 				root->right = y->left;
901 				y->left = root;
902 				vm_map_entry_set_max_free(root);
903 				root = y->right;
904 				y->right = llist;
905 				llist = y;
906 			} else {
907 				/* Put root on llist. */
908 				root->right = llist;
909 				llist = root;
910 				root = y;
911 			}
912 		} else
913 			break;
914 	}
915 
916 	/*
917 	 * Pass Two: Walk back up the two spines, flip the pointers
918 	 * and set max_free.  The subtrees of the root go at the
919 	 * bottom of llist and rlist.
920 	 */
921 	ltree = root->left;
922 	while (llist != NULL) {
923 		y = llist->right;
924 		llist->right = ltree;
925 		vm_map_entry_set_max_free(llist);
926 		ltree = llist;
927 		llist = y;
928 	}
929 	rtree = root->right;
930 	while (rlist != NULL) {
931 		y = rlist->left;
932 		rlist->left = rtree;
933 		vm_map_entry_set_max_free(rlist);
934 		rtree = rlist;
935 		rlist = y;
936 	}
937 
938 	/*
939 	 * Final assembly: add ltree and rtree as subtrees of root.
940 	 */
941 	root->left = ltree;
942 	root->right = rtree;
943 	vm_map_entry_set_max_free(root);
944 
945 	return (root);
946 }
947 
948 /*
949  *	vm_map_entry_{un,}link:
950  *
951  *	Insert/remove entries from maps.
952  */
953 static void
954 vm_map_entry_link(vm_map_t map,
955 		  vm_map_entry_t after_where,
956 		  vm_map_entry_t entry)
957 {
958 
959 	CTR4(KTR_VM,
960 	    "vm_map_entry_link: map %p, nentries %d, entry %p, after %p", map,
961 	    map->nentries, entry, after_where);
962 	VM_MAP_ASSERT_LOCKED(map);
963 	map->nentries++;
964 	entry->prev = after_where;
965 	entry->next = after_where->next;
966 	entry->next->prev = entry;
967 	after_where->next = entry;
968 
969 	if (after_where != &map->header) {
970 		if (after_where != map->root)
971 			vm_map_entry_splay(after_where->start, map->root);
972 		entry->right = after_where->right;
973 		entry->left = after_where;
974 		after_where->right = NULL;
975 		after_where->adj_free = entry->start - after_where->end;
976 		vm_map_entry_set_max_free(after_where);
977 	} else {
978 		entry->right = map->root;
979 		entry->left = NULL;
980 	}
981 	entry->adj_free = (entry->next == &map->header ? map->max_offset :
982 	    entry->next->start) - entry->end;
983 	vm_map_entry_set_max_free(entry);
984 	map->root = entry;
985 }
986 
987 static void
988 vm_map_entry_unlink(vm_map_t map,
989 		    vm_map_entry_t entry)
990 {
991 	vm_map_entry_t next, prev, root;
992 
993 	VM_MAP_ASSERT_LOCKED(map);
994 	if (entry != map->root)
995 		vm_map_entry_splay(entry->start, map->root);
996 	if (entry->left == NULL)
997 		root = entry->right;
998 	else {
999 		root = vm_map_entry_splay(entry->start, entry->left);
1000 		root->right = entry->right;
1001 		root->adj_free = (entry->next == &map->header ? map->max_offset :
1002 		    entry->next->start) - root->end;
1003 		vm_map_entry_set_max_free(root);
1004 	}
1005 	map->root = root;
1006 
1007 	prev = entry->prev;
1008 	next = entry->next;
1009 	next->prev = prev;
1010 	prev->next = next;
1011 	map->nentries--;
1012 	CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
1013 	    map->nentries, entry);
1014 }
1015 
1016 /*
1017  *	vm_map_entry_resize_free:
1018  *
1019  *	Recompute the amount of free space following a vm_map_entry
1020  *	and propagate that value up the tree.  Call this function after
1021  *	resizing a map entry in-place, that is, without a call to
1022  *	vm_map_entry_link() or _unlink().
1023  *
1024  *	The map must be locked, and leaves it so.
1025  */
1026 static void
1027 vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry)
1028 {
1029 
1030 	/*
1031 	 * Using splay trees without parent pointers, propagating
1032 	 * max_free up the tree is done by moving the entry to the
1033 	 * root and making the change there.
1034 	 */
1035 	if (entry != map->root)
1036 		map->root = vm_map_entry_splay(entry->start, map->root);
1037 
1038 	entry->adj_free = (entry->next == &map->header ? map->max_offset :
1039 	    entry->next->start) - entry->end;
1040 	vm_map_entry_set_max_free(entry);
1041 }
1042 
1043 /*
1044  *	vm_map_lookup_entry:	[ internal use only ]
1045  *
1046  *	Finds the map entry containing (or
1047  *	immediately preceding) the specified address
1048  *	in the given map; the entry is returned
1049  *	in the "entry" parameter.  The boolean
1050  *	result indicates whether the address is
1051  *	actually contained in the map.
1052  */
1053 boolean_t
1054 vm_map_lookup_entry(
1055 	vm_map_t map,
1056 	vm_offset_t address,
1057 	vm_map_entry_t *entry)	/* OUT */
1058 {
1059 	vm_map_entry_t cur;
1060 	boolean_t locked;
1061 
1062 	/*
1063 	 * If the map is empty, then the map entry immediately preceding
1064 	 * "address" is the map's header.
1065 	 */
1066 	cur = map->root;
1067 	if (cur == NULL)
1068 		*entry = &map->header;
1069 	else if (address >= cur->start && cur->end > address) {
1070 		*entry = cur;
1071 		return (TRUE);
1072 	} else if ((locked = vm_map_locked(map)) ||
1073 	    sx_try_upgrade(&map->lock)) {
1074 		/*
1075 		 * Splay requires a write lock on the map.  However, it only
1076 		 * restructures the binary search tree; it does not otherwise
1077 		 * change the map.  Thus, the map's timestamp need not change
1078 		 * on a temporary upgrade.
1079 		 */
1080 		map->root = cur = vm_map_entry_splay(address, cur);
1081 		if (!locked)
1082 			sx_downgrade(&map->lock);
1083 
1084 		/*
1085 		 * If "address" is contained within a map entry, the new root
1086 		 * is that map entry.  Otherwise, the new root is a map entry
1087 		 * immediately before or after "address".
1088 		 */
1089 		if (address >= cur->start) {
1090 			*entry = cur;
1091 			if (cur->end > address)
1092 				return (TRUE);
1093 		} else
1094 			*entry = cur->prev;
1095 	} else
1096 		/*
1097 		 * Since the map is only locked for read access, perform a
1098 		 * standard binary search tree lookup for "address".
1099 		 */
1100 		for (;;) {
1101 			if (address < cur->start) {
1102 				if (cur->left == NULL) {
1103 					*entry = cur->prev;
1104 					break;
1105 				}
1106 				cur = cur->left;
1107 			} else if (cur->end > address) {
1108 				*entry = cur;
1109 				return (TRUE);
1110 			} else {
1111 				if (cur->right == NULL) {
1112 					*entry = cur;
1113 					break;
1114 				}
1115 				cur = cur->right;
1116 			}
1117 		}
1118 	return (FALSE);
1119 }
1120 
1121 /*
1122  *	vm_map_insert:
1123  *
1124  *	Inserts the given whole VM object into the target
1125  *	map at the specified address range.  The object's
1126  *	size should match that of the address range.
1127  *
1128  *	Requires that the map be locked, and leaves it so.
1129  *
1130  *	If object is non-NULL, ref count must be bumped by caller
1131  *	prior to making call to account for the new entry.
1132  */
1133 int
1134 vm_map_insert(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
1135 	      vm_offset_t start, vm_offset_t end, vm_prot_t prot, vm_prot_t max,
1136 	      int cow)
1137 {
1138 	vm_map_entry_t new_entry;
1139 	vm_map_entry_t prev_entry;
1140 	vm_map_entry_t temp_entry;
1141 	vm_eflags_t protoeflags;
1142 	struct ucred *cred;
1143 	vm_inherit_t inheritance;
1144 	boolean_t charge_prev_obj;
1145 
1146 	VM_MAP_ASSERT_LOCKED(map);
1147 
1148 	/*
1149 	 * Check that the start and end points are not bogus.
1150 	 */
1151 	if ((start < map->min_offset) || (end > map->max_offset) ||
1152 	    (start >= end))
1153 		return (KERN_INVALID_ADDRESS);
1154 
1155 	/*
1156 	 * Find the entry prior to the proposed starting address; if it's part
1157 	 * of an existing entry, this range is bogus.
1158 	 */
1159 	if (vm_map_lookup_entry(map, start, &temp_entry))
1160 		return (KERN_NO_SPACE);
1161 
1162 	prev_entry = temp_entry;
1163 
1164 	/*
1165 	 * Assert that the next entry doesn't overlap the end point.
1166 	 */
1167 	if ((prev_entry->next != &map->header) &&
1168 	    (prev_entry->next->start < end))
1169 		return (KERN_NO_SPACE);
1170 
1171 	protoeflags = 0;
1172 	charge_prev_obj = FALSE;
1173 
1174 	if (cow & MAP_COPY_ON_WRITE)
1175 		protoeflags |= MAP_ENTRY_COW|MAP_ENTRY_NEEDS_COPY;
1176 
1177 	if (cow & MAP_NOFAULT) {
1178 		protoeflags |= MAP_ENTRY_NOFAULT;
1179 
1180 		KASSERT(object == NULL,
1181 			("vm_map_insert: paradoxical MAP_NOFAULT request"));
1182 	}
1183 	if (cow & MAP_DISABLE_SYNCER)
1184 		protoeflags |= MAP_ENTRY_NOSYNC;
1185 	if (cow & MAP_DISABLE_COREDUMP)
1186 		protoeflags |= MAP_ENTRY_NOCOREDUMP;
1187 	if (cow & MAP_VN_WRITECOUNT)
1188 		protoeflags |= MAP_ENTRY_VN_WRITECNT;
1189 	if (cow & MAP_INHERIT_SHARE)
1190 		inheritance = VM_INHERIT_SHARE;
1191 	else
1192 		inheritance = VM_INHERIT_DEFAULT;
1193 
1194 	cred = NULL;
1195 	KASSERT((object != kmem_object && object != kernel_object) ||
1196 	    ((object == kmem_object || object == kernel_object) &&
1197 		!(protoeflags & MAP_ENTRY_NEEDS_COPY)),
1198 	    ("kmem or kernel object and cow"));
1199 	if (cow & (MAP_ACC_NO_CHARGE | MAP_NOFAULT))
1200 		goto charged;
1201 	if ((cow & MAP_ACC_CHARGED) || ((prot & VM_PROT_WRITE) &&
1202 	    ((protoeflags & MAP_ENTRY_NEEDS_COPY) || object == NULL))) {
1203 		if (!(cow & MAP_ACC_CHARGED) && !swap_reserve(end - start))
1204 			return (KERN_RESOURCE_SHORTAGE);
1205 		KASSERT(object == NULL || (protoeflags & MAP_ENTRY_NEEDS_COPY) ||
1206 		    object->cred == NULL,
1207 		    ("OVERCOMMIT: vm_map_insert o %p", object));
1208 		cred = curthread->td_ucred;
1209 		crhold(cred);
1210 		if (object == NULL && !(protoeflags & MAP_ENTRY_NEEDS_COPY))
1211 			charge_prev_obj = TRUE;
1212 	}
1213 
1214 charged:
1215 	/* Expand the kernel pmap, if necessary. */
1216 	if (map == kernel_map && end > kernel_vm_end)
1217 		pmap_growkernel(end);
1218 	if (object != NULL) {
1219 		/*
1220 		 * OBJ_ONEMAPPING must be cleared unless this mapping
1221 		 * is trivially proven to be the only mapping for any
1222 		 * of the object's pages.  (Object granularity
1223 		 * reference counting is insufficient to recognize
1224 		 * aliases with precision.)
1225 		 */
1226 		VM_OBJECT_WLOCK(object);
1227 		if (object->ref_count > 1 || object->shadow_count != 0)
1228 			vm_object_clear_flag(object, OBJ_ONEMAPPING);
1229 		VM_OBJECT_WUNLOCK(object);
1230 	}
1231 	else if ((prev_entry != &map->header) &&
1232 		 (prev_entry->eflags == protoeflags) &&
1233 		 (prev_entry->end == start) &&
1234 		 (prev_entry->wired_count == 0) &&
1235 		 (prev_entry->cred == cred ||
1236 		  (prev_entry->object.vm_object != NULL &&
1237 		   (prev_entry->object.vm_object->cred == cred))) &&
1238 		   vm_object_coalesce(prev_entry->object.vm_object,
1239 		       prev_entry->offset,
1240 		       (vm_size_t)(prev_entry->end - prev_entry->start),
1241 		       (vm_size_t)(end - prev_entry->end), charge_prev_obj)) {
1242 		/*
1243 		 * We were able to extend the object.  Determine if we
1244 		 * can extend the previous map entry to include the
1245 		 * new range as well.
1246 		 */
1247 		if ((prev_entry->inheritance == inheritance) &&
1248 		    (prev_entry->protection == prot) &&
1249 		    (prev_entry->max_protection == max)) {
1250 			map->size += (end - prev_entry->end);
1251 			prev_entry->end = end;
1252 			vm_map_entry_resize_free(map, prev_entry);
1253 			vm_map_simplify_entry(map, prev_entry);
1254 			if (cred != NULL)
1255 				crfree(cred);
1256 			return (KERN_SUCCESS);
1257 		}
1258 
1259 		/*
1260 		 * If we can extend the object but cannot extend the
1261 		 * map entry, we have to create a new map entry.  We
1262 		 * must bump the ref count on the extended object to
1263 		 * account for it.  object may be NULL.
1264 		 */
1265 		object = prev_entry->object.vm_object;
1266 		offset = prev_entry->offset +
1267 			(prev_entry->end - prev_entry->start);
1268 		vm_object_reference(object);
1269 		if (cred != NULL && object != NULL && object->cred != NULL &&
1270 		    !(prev_entry->eflags & MAP_ENTRY_NEEDS_COPY)) {
1271 			/* Object already accounts for this uid. */
1272 			crfree(cred);
1273 			cred = NULL;
1274 		}
1275 	}
1276 
1277 	/*
1278 	 * NOTE: if conditionals fail, object can be NULL here.  This occurs
1279 	 * in things like the buffer map where we manage kva but do not manage
1280 	 * backing objects.
1281 	 */
1282 
1283 	/*
1284 	 * Create a new entry
1285 	 */
1286 	new_entry = vm_map_entry_create(map);
1287 	new_entry->start = start;
1288 	new_entry->end = end;
1289 	new_entry->cred = NULL;
1290 
1291 	new_entry->eflags = protoeflags;
1292 	new_entry->object.vm_object = object;
1293 	new_entry->offset = offset;
1294 	new_entry->avail_ssize = 0;
1295 
1296 	new_entry->inheritance = inheritance;
1297 	new_entry->protection = prot;
1298 	new_entry->max_protection = max;
1299 	new_entry->wired_count = 0;
1300 	new_entry->read_ahead = VM_FAULT_READ_AHEAD_INIT;
1301 	new_entry->next_read = OFF_TO_IDX(offset);
1302 
1303 	KASSERT(cred == NULL || !ENTRY_CHARGED(new_entry),
1304 	    ("OVERCOMMIT: vm_map_insert leaks vm_map %p", new_entry));
1305 	new_entry->cred = cred;
1306 
1307 	/*
1308 	 * Insert the new entry into the list
1309 	 */
1310 	vm_map_entry_link(map, prev_entry, new_entry);
1311 	map->size += new_entry->end - new_entry->start;
1312 
1313 	/*
1314 	 * It may be possible to merge the new entry with the next and/or
1315 	 * previous entries.  However, due to MAP_STACK_* being a hack, a
1316 	 * panic can result from merging such entries.
1317 	 */
1318 	if ((cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP)) == 0)
1319 		vm_map_simplify_entry(map, new_entry);
1320 
1321 	if (cow & (MAP_PREFAULT|MAP_PREFAULT_PARTIAL)) {
1322 		vm_map_pmap_enter(map, start, prot,
1323 				    object, OFF_TO_IDX(offset), end - start,
1324 				    cow & MAP_PREFAULT_PARTIAL);
1325 	}
1326 
1327 	return (KERN_SUCCESS);
1328 }
1329 
1330 /*
1331  *	vm_map_findspace:
1332  *
1333  *	Find the first fit (lowest VM address) for "length" free bytes
1334  *	beginning at address >= start in the given map.
1335  *
1336  *	In a vm_map_entry, "adj_free" is the amount of free space
1337  *	adjacent (higher address) to this entry, and "max_free" is the
1338  *	maximum amount of contiguous free space in its subtree.  This
1339  *	allows finding a free region in one path down the tree, so
1340  *	O(log n) amortized with splay trees.
1341  *
1342  *	The map must be locked, and leaves it so.
1343  *
1344  *	Returns: 0 on success, and starting address in *addr,
1345  *		 1 if insufficient space.
1346  */
1347 int
1348 vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length,
1349     vm_offset_t *addr)	/* OUT */
1350 {
1351 	vm_map_entry_t entry;
1352 	vm_offset_t st;
1353 
1354 	/*
1355 	 * Request must fit within min/max VM address and must avoid
1356 	 * address wrap.
1357 	 */
1358 	if (start < map->min_offset)
1359 		start = map->min_offset;
1360 	if (start + length > map->max_offset || start + length < start)
1361 		return (1);
1362 
1363 	/* Empty tree means wide open address space. */
1364 	if (map->root == NULL) {
1365 		*addr = start;
1366 		return (0);
1367 	}
1368 
1369 	/*
1370 	 * After splay, if start comes before root node, then there
1371 	 * must be a gap from start to the root.
1372 	 */
1373 	map->root = vm_map_entry_splay(start, map->root);
1374 	if (start + length <= map->root->start) {
1375 		*addr = start;
1376 		return (0);
1377 	}
1378 
1379 	/*
1380 	 * Root is the last node that might begin its gap before
1381 	 * start, and this is the last comparison where address
1382 	 * wrap might be a problem.
1383 	 */
1384 	st = (start > map->root->end) ? start : map->root->end;
1385 	if (length <= map->root->end + map->root->adj_free - st) {
1386 		*addr = st;
1387 		return (0);
1388 	}
1389 
1390 	/* With max_free, can immediately tell if no solution. */
1391 	entry = map->root->right;
1392 	if (entry == NULL || length > entry->max_free)
1393 		return (1);
1394 
1395 	/*
1396 	 * Search the right subtree in the order: left subtree, root,
1397 	 * right subtree (first fit).  The previous splay implies that
1398 	 * all regions in the right subtree have addresses > start.
1399 	 */
1400 	while (entry != NULL) {
1401 		if (entry->left != NULL && entry->left->max_free >= length)
1402 			entry = entry->left;
1403 		else if (entry->adj_free >= length) {
1404 			*addr = entry->end;
1405 			return (0);
1406 		} else
1407 			entry = entry->right;
1408 	}
1409 
1410 	/* Can't get here, so panic if we do. */
1411 	panic("vm_map_findspace: max_free corrupt");
1412 }
1413 
1414 int
1415 vm_map_fixed(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
1416     vm_offset_t start, vm_size_t length, vm_prot_t prot,
1417     vm_prot_t max, int cow)
1418 {
1419 	vm_offset_t end;
1420 	int result;
1421 
1422 	end = start + length;
1423 	vm_map_lock(map);
1424 	VM_MAP_RANGE_CHECK(map, start, end);
1425 	(void) vm_map_delete(map, start, end);
1426 	result = vm_map_insert(map, object, offset, start, end, prot,
1427 	    max, cow);
1428 	vm_map_unlock(map);
1429 	return (result);
1430 }
1431 
1432 /*
1433  *	vm_map_find finds an unallocated region in the target address
1434  *	map with the given length.  The search is defined to be
1435  *	first-fit from the specified address; the region found is
1436  *	returned in the same parameter.
1437  *
1438  *	If object is non-NULL, ref count must be bumped by caller
1439  *	prior to making call to account for the new entry.
1440  */
1441 int
1442 vm_map_find(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
1443 	    vm_offset_t *addr,	/* IN/OUT */
1444 	    vm_size_t length, int find_space, vm_prot_t prot,
1445 	    vm_prot_t max, int cow)
1446 {
1447 	vm_offset_t start;
1448 	int result;
1449 
1450 	start = *addr;
1451 	vm_map_lock(map);
1452 	do {
1453 		if (find_space != VMFS_NO_SPACE) {
1454 			if (vm_map_findspace(map, start, length, addr)) {
1455 				vm_map_unlock(map);
1456 				return (KERN_NO_SPACE);
1457 			}
1458 			switch (find_space) {
1459 			case VMFS_ALIGNED_SPACE:
1460 				pmap_align_superpage(object, offset, addr,
1461 				    length);
1462 				break;
1463 #ifdef VMFS_TLB_ALIGNED_SPACE
1464 			case VMFS_TLB_ALIGNED_SPACE:
1465 				pmap_align_tlb(addr);
1466 				break;
1467 #endif
1468 			default:
1469 				break;
1470 			}
1471 
1472 			start = *addr;
1473 		}
1474 		result = vm_map_insert(map, object, offset, start, start +
1475 		    length, prot, max, cow);
1476 	} while (result == KERN_NO_SPACE && (find_space == VMFS_ALIGNED_SPACE
1477 #ifdef VMFS_TLB_ALIGNED_SPACE
1478 	    || find_space == VMFS_TLB_ALIGNED_SPACE
1479 #endif
1480 	    ));
1481 	vm_map_unlock(map);
1482 	return (result);
1483 }
1484 
1485 /*
1486  *	vm_map_simplify_entry:
1487  *
1488  *	Simplify the given map entry by merging with either neighbor.  This
1489  *	routine also has the ability to merge with both neighbors.
1490  *
1491  *	The map must be locked.
1492  *
1493  *	This routine guarentees that the passed entry remains valid (though
1494  *	possibly extended).  When merging, this routine may delete one or
1495  *	both neighbors.
1496  */
1497 void
1498 vm_map_simplify_entry(vm_map_t map, vm_map_entry_t entry)
1499 {
1500 	vm_map_entry_t next, prev;
1501 	vm_size_t prevsize, esize;
1502 
1503 	if (entry->eflags & (MAP_ENTRY_IN_TRANSITION | MAP_ENTRY_IS_SUB_MAP))
1504 		return;
1505 
1506 	prev = entry->prev;
1507 	if (prev != &map->header) {
1508 		prevsize = prev->end - prev->start;
1509 		if ( (prev->end == entry->start) &&
1510 		     (prev->object.vm_object == entry->object.vm_object) &&
1511 		     (!prev->object.vm_object ||
1512 			(prev->offset + prevsize == entry->offset)) &&
1513 		     (prev->eflags == entry->eflags) &&
1514 		     (prev->protection == entry->protection) &&
1515 		     (prev->max_protection == entry->max_protection) &&
1516 		     (prev->inheritance == entry->inheritance) &&
1517 		     (prev->wired_count == entry->wired_count) &&
1518 		     (prev->cred == entry->cred)) {
1519 			vm_map_entry_unlink(map, prev);
1520 			entry->start = prev->start;
1521 			entry->offset = prev->offset;
1522 			if (entry->prev != &map->header)
1523 				vm_map_entry_resize_free(map, entry->prev);
1524 
1525 			/*
1526 			 * If the backing object is a vnode object,
1527 			 * vm_object_deallocate() calls vrele().
1528 			 * However, vrele() does not lock the vnode
1529 			 * because the vnode has additional
1530 			 * references.  Thus, the map lock can be kept
1531 			 * without causing a lock-order reversal with
1532 			 * the vnode lock.
1533 			 *
1534 			 * Since we count the number of virtual page
1535 			 * mappings in object->un_pager.vnp.writemappings,
1536 			 * the writemappings value should not be adjusted
1537 			 * when the entry is disposed of.
1538 			 */
1539 			if (prev->object.vm_object)
1540 				vm_object_deallocate(prev->object.vm_object);
1541 			if (prev->cred != NULL)
1542 				crfree(prev->cred);
1543 			vm_map_entry_dispose(map, prev);
1544 		}
1545 	}
1546 
1547 	next = entry->next;
1548 	if (next != &map->header) {
1549 		esize = entry->end - entry->start;
1550 		if ((entry->end == next->start) &&
1551 		    (next->object.vm_object == entry->object.vm_object) &&
1552 		     (!entry->object.vm_object ||
1553 			(entry->offset + esize == next->offset)) &&
1554 		    (next->eflags == entry->eflags) &&
1555 		    (next->protection == entry->protection) &&
1556 		    (next->max_protection == entry->max_protection) &&
1557 		    (next->inheritance == entry->inheritance) &&
1558 		    (next->wired_count == entry->wired_count) &&
1559 		    (next->cred == entry->cred)) {
1560 			vm_map_entry_unlink(map, next);
1561 			entry->end = next->end;
1562 			vm_map_entry_resize_free(map, entry);
1563 
1564 			/*
1565 			 * See comment above.
1566 			 */
1567 			if (next->object.vm_object)
1568 				vm_object_deallocate(next->object.vm_object);
1569 			if (next->cred != NULL)
1570 				crfree(next->cred);
1571 			vm_map_entry_dispose(map, next);
1572 		}
1573 	}
1574 }
1575 /*
1576  *	vm_map_clip_start:	[ internal use only ]
1577  *
1578  *	Asserts that the given entry begins at or after
1579  *	the specified address; if necessary,
1580  *	it splits the entry into two.
1581  */
1582 #define vm_map_clip_start(map, entry, startaddr) \
1583 { \
1584 	if (startaddr > entry->start) \
1585 		_vm_map_clip_start(map, entry, startaddr); \
1586 }
1587 
1588 /*
1589  *	This routine is called only when it is known that
1590  *	the entry must be split.
1591  */
1592 static void
1593 _vm_map_clip_start(vm_map_t map, vm_map_entry_t entry, vm_offset_t start)
1594 {
1595 	vm_map_entry_t new_entry;
1596 
1597 	VM_MAP_ASSERT_LOCKED(map);
1598 
1599 	/*
1600 	 * Split off the front portion -- note that we must insert the new
1601 	 * entry BEFORE this one, so that this entry has the specified
1602 	 * starting address.
1603 	 */
1604 	vm_map_simplify_entry(map, entry);
1605 
1606 	/*
1607 	 * If there is no object backing this entry, we might as well create
1608 	 * one now.  If we defer it, an object can get created after the map
1609 	 * is clipped, and individual objects will be created for the split-up
1610 	 * map.  This is a bit of a hack, but is also about the best place to
1611 	 * put this improvement.
1612 	 */
1613 	if (entry->object.vm_object == NULL && !map->system_map) {
1614 		vm_object_t object;
1615 		object = vm_object_allocate(OBJT_DEFAULT,
1616 				atop(entry->end - entry->start));
1617 		entry->object.vm_object = object;
1618 		entry->offset = 0;
1619 		if (entry->cred != NULL) {
1620 			object->cred = entry->cred;
1621 			object->charge = entry->end - entry->start;
1622 			entry->cred = NULL;
1623 		}
1624 	} else if (entry->object.vm_object != NULL &&
1625 		   ((entry->eflags & MAP_ENTRY_NEEDS_COPY) == 0) &&
1626 		   entry->cred != NULL) {
1627 		VM_OBJECT_WLOCK(entry->object.vm_object);
1628 		KASSERT(entry->object.vm_object->cred == NULL,
1629 		    ("OVERCOMMIT: vm_entry_clip_start: both cred e %p", entry));
1630 		entry->object.vm_object->cred = entry->cred;
1631 		entry->object.vm_object->charge = entry->end - entry->start;
1632 		VM_OBJECT_WUNLOCK(entry->object.vm_object);
1633 		entry->cred = NULL;
1634 	}
1635 
1636 	new_entry = vm_map_entry_create(map);
1637 	*new_entry = *entry;
1638 
1639 	new_entry->end = start;
1640 	entry->offset += (start - entry->start);
1641 	entry->start = start;
1642 	if (new_entry->cred != NULL)
1643 		crhold(entry->cred);
1644 
1645 	vm_map_entry_link(map, entry->prev, new_entry);
1646 
1647 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
1648 		vm_object_reference(new_entry->object.vm_object);
1649 		/*
1650 		 * The object->un_pager.vnp.writemappings for the
1651 		 * object of MAP_ENTRY_VN_WRITECNT type entry shall be
1652 		 * kept as is here.  The virtual pages are
1653 		 * re-distributed among the clipped entries, so the sum is
1654 		 * left the same.
1655 		 */
1656 	}
1657 }
1658 
1659 /*
1660  *	vm_map_clip_end:	[ internal use only ]
1661  *
1662  *	Asserts that the given entry ends at or before
1663  *	the specified address; if necessary,
1664  *	it splits the entry into two.
1665  */
1666 #define vm_map_clip_end(map, entry, endaddr) \
1667 { \
1668 	if ((endaddr) < (entry->end)) \
1669 		_vm_map_clip_end((map), (entry), (endaddr)); \
1670 }
1671 
1672 /*
1673  *	This routine is called only when it is known that
1674  *	the entry must be split.
1675  */
1676 static void
1677 _vm_map_clip_end(vm_map_t map, vm_map_entry_t entry, vm_offset_t end)
1678 {
1679 	vm_map_entry_t new_entry;
1680 
1681 	VM_MAP_ASSERT_LOCKED(map);
1682 
1683 	/*
1684 	 * If there is no object backing this entry, we might as well create
1685 	 * one now.  If we defer it, an object can get created after the map
1686 	 * is clipped, and individual objects will be created for the split-up
1687 	 * map.  This is a bit of a hack, but is also about the best place to
1688 	 * put this improvement.
1689 	 */
1690 	if (entry->object.vm_object == NULL && !map->system_map) {
1691 		vm_object_t object;
1692 		object = vm_object_allocate(OBJT_DEFAULT,
1693 				atop(entry->end - entry->start));
1694 		entry->object.vm_object = object;
1695 		entry->offset = 0;
1696 		if (entry->cred != NULL) {
1697 			object->cred = entry->cred;
1698 			object->charge = entry->end - entry->start;
1699 			entry->cred = NULL;
1700 		}
1701 	} else if (entry->object.vm_object != NULL &&
1702 		   ((entry->eflags & MAP_ENTRY_NEEDS_COPY) == 0) &&
1703 		   entry->cred != NULL) {
1704 		VM_OBJECT_WLOCK(entry->object.vm_object);
1705 		KASSERT(entry->object.vm_object->cred == NULL,
1706 		    ("OVERCOMMIT: vm_entry_clip_end: both cred e %p", entry));
1707 		entry->object.vm_object->cred = entry->cred;
1708 		entry->object.vm_object->charge = entry->end - entry->start;
1709 		VM_OBJECT_WUNLOCK(entry->object.vm_object);
1710 		entry->cred = NULL;
1711 	}
1712 
1713 	/*
1714 	 * Create a new entry and insert it AFTER the specified entry
1715 	 */
1716 	new_entry = vm_map_entry_create(map);
1717 	*new_entry = *entry;
1718 
1719 	new_entry->start = entry->end = end;
1720 	new_entry->offset += (end - entry->start);
1721 	if (new_entry->cred != NULL)
1722 		crhold(entry->cred);
1723 
1724 	vm_map_entry_link(map, entry, new_entry);
1725 
1726 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
1727 		vm_object_reference(new_entry->object.vm_object);
1728 	}
1729 }
1730 
1731 /*
1732  *	vm_map_submap:		[ kernel use only ]
1733  *
1734  *	Mark the given range as handled by a subordinate map.
1735  *
1736  *	This range must have been created with vm_map_find,
1737  *	and no other operations may have been performed on this
1738  *	range prior to calling vm_map_submap.
1739  *
1740  *	Only a limited number of operations can be performed
1741  *	within this rage after calling vm_map_submap:
1742  *		vm_fault
1743  *	[Don't try vm_map_copy!]
1744  *
1745  *	To remove a submapping, one must first remove the
1746  *	range from the superior map, and then destroy the
1747  *	submap (if desired).  [Better yet, don't try it.]
1748  */
1749 int
1750 vm_map_submap(
1751 	vm_map_t map,
1752 	vm_offset_t start,
1753 	vm_offset_t end,
1754 	vm_map_t submap)
1755 {
1756 	vm_map_entry_t entry;
1757 	int result = KERN_INVALID_ARGUMENT;
1758 
1759 	vm_map_lock(map);
1760 
1761 	VM_MAP_RANGE_CHECK(map, start, end);
1762 
1763 	if (vm_map_lookup_entry(map, start, &entry)) {
1764 		vm_map_clip_start(map, entry, start);
1765 	} else
1766 		entry = entry->next;
1767 
1768 	vm_map_clip_end(map, entry, end);
1769 
1770 	if ((entry->start == start) && (entry->end == end) &&
1771 	    ((entry->eflags & MAP_ENTRY_COW) == 0) &&
1772 	    (entry->object.vm_object == NULL)) {
1773 		entry->object.sub_map = submap;
1774 		entry->eflags |= MAP_ENTRY_IS_SUB_MAP;
1775 		result = KERN_SUCCESS;
1776 	}
1777 	vm_map_unlock(map);
1778 
1779 	return (result);
1780 }
1781 
1782 /*
1783  * The maximum number of pages to map
1784  */
1785 #define	MAX_INIT_PT	96
1786 
1787 /*
1788  *	vm_map_pmap_enter:
1789  *
1790  *	Preload read-only mappings for the specified object's resident pages
1791  *	into the target map.  If "flags" is MAP_PREFAULT_PARTIAL, then only
1792  *	the resident pages within the address range [addr, addr + ulmin(size,
1793  *	ptoa(MAX_INIT_PT))) are mapped.  Otherwise, all resident pages within
1794  *	the specified address range are mapped.  This eliminates many soft
1795  *	faults on process startup and immediately after an mmap(2).  Because
1796  *	these are speculative mappings, cached pages are not reactivated and
1797  *	mapped.
1798  */
1799 void
1800 vm_map_pmap_enter(vm_map_t map, vm_offset_t addr, vm_prot_t prot,
1801     vm_object_t object, vm_pindex_t pindex, vm_size_t size, int flags)
1802 {
1803 	vm_offset_t start;
1804 	vm_page_t p, p_start;
1805 	vm_pindex_t psize, tmpidx;
1806 
1807 	if ((prot & (VM_PROT_READ | VM_PROT_EXECUTE)) == 0 || object == NULL)
1808 		return;
1809 	VM_OBJECT_WLOCK(object);
1810 	if (object->type == OBJT_DEVICE || object->type == OBJT_SG) {
1811 		pmap_object_init_pt(map->pmap, addr, object, pindex, size);
1812 		goto unlock_return;
1813 	}
1814 
1815 	psize = atop(size);
1816 	if (psize > MAX_INIT_PT && (flags & MAP_PREFAULT_PARTIAL) != 0)
1817 		psize = MAX_INIT_PT;
1818 	if (psize + pindex > object->size) {
1819 		if (object->size < pindex)
1820 			goto unlock_return;
1821 		psize = object->size - pindex;
1822 	}
1823 
1824 	start = 0;
1825 	p_start = NULL;
1826 
1827 	p = vm_page_find_least(object, pindex);
1828 	/*
1829 	 * Assert: the variable p is either (1) the page with the
1830 	 * least pindex greater than or equal to the parameter pindex
1831 	 * or (2) NULL.
1832 	 */
1833 	for (;
1834 	     p != NULL && (tmpidx = p->pindex - pindex) < psize;
1835 	     p = TAILQ_NEXT(p, listq)) {
1836 		/*
1837 		 * don't allow an madvise to blow away our really
1838 		 * free pages allocating pv entries.
1839 		 */
1840 		if ((flags & MAP_PREFAULT_MADVISE) &&
1841 		    cnt.v_free_count < cnt.v_free_reserved) {
1842 			psize = tmpidx;
1843 			break;
1844 		}
1845 		if (p->valid == VM_PAGE_BITS_ALL) {
1846 			if (p_start == NULL) {
1847 				start = addr + ptoa(tmpidx);
1848 				p_start = p;
1849 			}
1850 		} else if (p_start != NULL) {
1851 			pmap_enter_object(map->pmap, start, addr +
1852 			    ptoa(tmpidx), p_start, prot);
1853 			p_start = NULL;
1854 		}
1855 	}
1856 	if (p_start != NULL)
1857 		pmap_enter_object(map->pmap, start, addr + ptoa(psize),
1858 		    p_start, prot);
1859 unlock_return:
1860 	VM_OBJECT_WUNLOCK(object);
1861 }
1862 
1863 /*
1864  *	vm_map_protect:
1865  *
1866  *	Sets the protection of the specified address
1867  *	region in the target map.  If "set_max" is
1868  *	specified, the maximum protection is to be set;
1869  *	otherwise, only the current protection is affected.
1870  */
1871 int
1872 vm_map_protect(vm_map_t map, vm_offset_t start, vm_offset_t end,
1873 	       vm_prot_t new_prot, boolean_t set_max)
1874 {
1875 	vm_map_entry_t current, entry;
1876 	vm_object_t obj;
1877 	struct ucred *cred;
1878 	vm_prot_t old_prot;
1879 
1880 	vm_map_lock(map);
1881 
1882 	VM_MAP_RANGE_CHECK(map, start, end);
1883 
1884 	if (vm_map_lookup_entry(map, start, &entry)) {
1885 		vm_map_clip_start(map, entry, start);
1886 	} else {
1887 		entry = entry->next;
1888 	}
1889 
1890 	/*
1891 	 * Make a first pass to check for protection violations.
1892 	 */
1893 	current = entry;
1894 	while ((current != &map->header) && (current->start < end)) {
1895 		if (current->eflags & MAP_ENTRY_IS_SUB_MAP) {
1896 			vm_map_unlock(map);
1897 			return (KERN_INVALID_ARGUMENT);
1898 		}
1899 		if ((new_prot & current->max_protection) != new_prot) {
1900 			vm_map_unlock(map);
1901 			return (KERN_PROTECTION_FAILURE);
1902 		}
1903 		current = current->next;
1904 	}
1905 
1906 
1907 	/*
1908 	 * Do an accounting pass for private read-only mappings that
1909 	 * now will do cow due to allowed write (e.g. debugger sets
1910 	 * breakpoint on text segment)
1911 	 */
1912 	for (current = entry; (current != &map->header) &&
1913 	     (current->start < end); current = current->next) {
1914 
1915 		vm_map_clip_end(map, current, end);
1916 
1917 		if (set_max ||
1918 		    ((new_prot & ~(current->protection)) & VM_PROT_WRITE) == 0 ||
1919 		    ENTRY_CHARGED(current)) {
1920 			continue;
1921 		}
1922 
1923 		cred = curthread->td_ucred;
1924 		obj = current->object.vm_object;
1925 
1926 		if (obj == NULL || (current->eflags & MAP_ENTRY_NEEDS_COPY)) {
1927 			if (!swap_reserve(current->end - current->start)) {
1928 				vm_map_unlock(map);
1929 				return (KERN_RESOURCE_SHORTAGE);
1930 			}
1931 			crhold(cred);
1932 			current->cred = cred;
1933 			continue;
1934 		}
1935 
1936 		VM_OBJECT_WLOCK(obj);
1937 		if (obj->type != OBJT_DEFAULT && obj->type != OBJT_SWAP) {
1938 			VM_OBJECT_WUNLOCK(obj);
1939 			continue;
1940 		}
1941 
1942 		/*
1943 		 * Charge for the whole object allocation now, since
1944 		 * we cannot distinguish between non-charged and
1945 		 * charged clipped mapping of the same object later.
1946 		 */
1947 		KASSERT(obj->charge == 0,
1948 		    ("vm_map_protect: object %p overcharged\n", obj));
1949 		if (!swap_reserve(ptoa(obj->size))) {
1950 			VM_OBJECT_WUNLOCK(obj);
1951 			vm_map_unlock(map);
1952 			return (KERN_RESOURCE_SHORTAGE);
1953 		}
1954 
1955 		crhold(cred);
1956 		obj->cred = cred;
1957 		obj->charge = ptoa(obj->size);
1958 		VM_OBJECT_WUNLOCK(obj);
1959 	}
1960 
1961 	/*
1962 	 * Go back and fix up protections. [Note that clipping is not
1963 	 * necessary the second time.]
1964 	 */
1965 	current = entry;
1966 	while ((current != &map->header) && (current->start < end)) {
1967 		old_prot = current->protection;
1968 
1969 		if (set_max)
1970 			current->protection =
1971 			    (current->max_protection = new_prot) &
1972 			    old_prot;
1973 		else
1974 			current->protection = new_prot;
1975 
1976 		if ((current->eflags & (MAP_ENTRY_COW | MAP_ENTRY_USER_WIRED))
1977 		     == (MAP_ENTRY_COW | MAP_ENTRY_USER_WIRED) &&
1978 		    (current->protection & VM_PROT_WRITE) != 0 &&
1979 		    (old_prot & VM_PROT_WRITE) == 0) {
1980 			vm_fault_copy_entry(map, map, current, current, NULL);
1981 		}
1982 
1983 		/*
1984 		 * When restricting access, update the physical map.  Worry
1985 		 * about copy-on-write here.
1986 		 */
1987 		if ((old_prot & ~current->protection) != 0) {
1988 #define MASK(entry)	(((entry)->eflags & MAP_ENTRY_COW) ? ~VM_PROT_WRITE : \
1989 							VM_PROT_ALL)
1990 			pmap_protect(map->pmap, current->start,
1991 			    current->end,
1992 			    current->protection & MASK(current));
1993 #undef	MASK
1994 		}
1995 		vm_map_simplify_entry(map, current);
1996 		current = current->next;
1997 	}
1998 	vm_map_unlock(map);
1999 	return (KERN_SUCCESS);
2000 }
2001 
2002 /*
2003  *	vm_map_madvise:
2004  *
2005  *	This routine traverses a processes map handling the madvise
2006  *	system call.  Advisories are classified as either those effecting
2007  *	the vm_map_entry structure, or those effecting the underlying
2008  *	objects.
2009  */
2010 int
2011 vm_map_madvise(
2012 	vm_map_t map,
2013 	vm_offset_t start,
2014 	vm_offset_t end,
2015 	int behav)
2016 {
2017 	vm_map_entry_t current, entry;
2018 	int modify_map = 0;
2019 
2020 	/*
2021 	 * Some madvise calls directly modify the vm_map_entry, in which case
2022 	 * we need to use an exclusive lock on the map and we need to perform
2023 	 * various clipping operations.  Otherwise we only need a read-lock
2024 	 * on the map.
2025 	 */
2026 	switch(behav) {
2027 	case MADV_NORMAL:
2028 	case MADV_SEQUENTIAL:
2029 	case MADV_RANDOM:
2030 	case MADV_NOSYNC:
2031 	case MADV_AUTOSYNC:
2032 	case MADV_NOCORE:
2033 	case MADV_CORE:
2034 		modify_map = 1;
2035 		vm_map_lock(map);
2036 		break;
2037 	case MADV_WILLNEED:
2038 	case MADV_DONTNEED:
2039 	case MADV_FREE:
2040 		vm_map_lock_read(map);
2041 		break;
2042 	default:
2043 		return (KERN_INVALID_ARGUMENT);
2044 	}
2045 
2046 	/*
2047 	 * Locate starting entry and clip if necessary.
2048 	 */
2049 	VM_MAP_RANGE_CHECK(map, start, end);
2050 
2051 	if (vm_map_lookup_entry(map, start, &entry)) {
2052 		if (modify_map)
2053 			vm_map_clip_start(map, entry, start);
2054 	} else {
2055 		entry = entry->next;
2056 	}
2057 
2058 	if (modify_map) {
2059 		/*
2060 		 * madvise behaviors that are implemented in the vm_map_entry.
2061 		 *
2062 		 * We clip the vm_map_entry so that behavioral changes are
2063 		 * limited to the specified address range.
2064 		 */
2065 		for (current = entry;
2066 		     (current != &map->header) && (current->start < end);
2067 		     current = current->next
2068 		) {
2069 			if (current->eflags & MAP_ENTRY_IS_SUB_MAP)
2070 				continue;
2071 
2072 			vm_map_clip_end(map, current, end);
2073 
2074 			switch (behav) {
2075 			case MADV_NORMAL:
2076 				vm_map_entry_set_behavior(current, MAP_ENTRY_BEHAV_NORMAL);
2077 				break;
2078 			case MADV_SEQUENTIAL:
2079 				vm_map_entry_set_behavior(current, MAP_ENTRY_BEHAV_SEQUENTIAL);
2080 				break;
2081 			case MADV_RANDOM:
2082 				vm_map_entry_set_behavior(current, MAP_ENTRY_BEHAV_RANDOM);
2083 				break;
2084 			case MADV_NOSYNC:
2085 				current->eflags |= MAP_ENTRY_NOSYNC;
2086 				break;
2087 			case MADV_AUTOSYNC:
2088 				current->eflags &= ~MAP_ENTRY_NOSYNC;
2089 				break;
2090 			case MADV_NOCORE:
2091 				current->eflags |= MAP_ENTRY_NOCOREDUMP;
2092 				break;
2093 			case MADV_CORE:
2094 				current->eflags &= ~MAP_ENTRY_NOCOREDUMP;
2095 				break;
2096 			default:
2097 				break;
2098 			}
2099 			vm_map_simplify_entry(map, current);
2100 		}
2101 		vm_map_unlock(map);
2102 	} else {
2103 		vm_pindex_t pstart, pend;
2104 
2105 		/*
2106 		 * madvise behaviors that are implemented in the underlying
2107 		 * vm_object.
2108 		 *
2109 		 * Since we don't clip the vm_map_entry, we have to clip
2110 		 * the vm_object pindex and count.
2111 		 */
2112 		for (current = entry;
2113 		     (current != &map->header) && (current->start < end);
2114 		     current = current->next
2115 		) {
2116 			vm_offset_t useStart;
2117 
2118 			if (current->eflags & MAP_ENTRY_IS_SUB_MAP)
2119 				continue;
2120 
2121 			pstart = OFF_TO_IDX(current->offset);
2122 			pend = pstart + atop(current->end - current->start);
2123 			useStart = current->start;
2124 
2125 			if (current->start < start) {
2126 				pstart += atop(start - current->start);
2127 				useStart = start;
2128 			}
2129 			if (current->end > end)
2130 				pend -= atop(current->end - end);
2131 
2132 			if (pstart >= pend)
2133 				continue;
2134 
2135 			vm_object_madvise(current->object.vm_object, pstart,
2136 			    pend, behav);
2137 			if (behav == MADV_WILLNEED) {
2138 				vm_map_pmap_enter(map,
2139 				    useStart,
2140 				    current->protection,
2141 				    current->object.vm_object,
2142 				    pstart,
2143 				    ptoa(pend - pstart),
2144 				    MAP_PREFAULT_MADVISE
2145 				);
2146 			}
2147 		}
2148 		vm_map_unlock_read(map);
2149 	}
2150 	return (0);
2151 }
2152 
2153 
2154 /*
2155  *	vm_map_inherit:
2156  *
2157  *	Sets the inheritance of the specified address
2158  *	range in the target map.  Inheritance
2159  *	affects how the map will be shared with
2160  *	child maps at the time of vmspace_fork.
2161  */
2162 int
2163 vm_map_inherit(vm_map_t map, vm_offset_t start, vm_offset_t end,
2164 	       vm_inherit_t new_inheritance)
2165 {
2166 	vm_map_entry_t entry;
2167 	vm_map_entry_t temp_entry;
2168 
2169 	switch (new_inheritance) {
2170 	case VM_INHERIT_NONE:
2171 	case VM_INHERIT_COPY:
2172 	case VM_INHERIT_SHARE:
2173 		break;
2174 	default:
2175 		return (KERN_INVALID_ARGUMENT);
2176 	}
2177 	vm_map_lock(map);
2178 	VM_MAP_RANGE_CHECK(map, start, end);
2179 	if (vm_map_lookup_entry(map, start, &temp_entry)) {
2180 		entry = temp_entry;
2181 		vm_map_clip_start(map, entry, start);
2182 	} else
2183 		entry = temp_entry->next;
2184 	while ((entry != &map->header) && (entry->start < end)) {
2185 		vm_map_clip_end(map, entry, end);
2186 		entry->inheritance = new_inheritance;
2187 		vm_map_simplify_entry(map, entry);
2188 		entry = entry->next;
2189 	}
2190 	vm_map_unlock(map);
2191 	return (KERN_SUCCESS);
2192 }
2193 
2194 /*
2195  *	vm_map_unwire:
2196  *
2197  *	Implements both kernel and user unwiring.
2198  */
2199 int
2200 vm_map_unwire(vm_map_t map, vm_offset_t start, vm_offset_t end,
2201     int flags)
2202 {
2203 	vm_map_entry_t entry, first_entry, tmp_entry;
2204 	vm_offset_t saved_start;
2205 	unsigned int last_timestamp;
2206 	int rv;
2207 	boolean_t need_wakeup, result, user_unwire;
2208 
2209 	user_unwire = (flags & VM_MAP_WIRE_USER) ? TRUE : FALSE;
2210 	vm_map_lock(map);
2211 	VM_MAP_RANGE_CHECK(map, start, end);
2212 	if (!vm_map_lookup_entry(map, start, &first_entry)) {
2213 		if (flags & VM_MAP_WIRE_HOLESOK)
2214 			first_entry = first_entry->next;
2215 		else {
2216 			vm_map_unlock(map);
2217 			return (KERN_INVALID_ADDRESS);
2218 		}
2219 	}
2220 	last_timestamp = map->timestamp;
2221 	entry = first_entry;
2222 	while (entry != &map->header && entry->start < end) {
2223 		if (entry->eflags & MAP_ENTRY_IN_TRANSITION) {
2224 			/*
2225 			 * We have not yet clipped the entry.
2226 			 */
2227 			saved_start = (start >= entry->start) ? start :
2228 			    entry->start;
2229 			entry->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
2230 			if (vm_map_unlock_and_wait(map, 0)) {
2231 				/*
2232 				 * Allow interruption of user unwiring?
2233 				 */
2234 			}
2235 			vm_map_lock(map);
2236 			if (last_timestamp+1 != map->timestamp) {
2237 				/*
2238 				 * Look again for the entry because the map was
2239 				 * modified while it was unlocked.
2240 				 * Specifically, the entry may have been
2241 				 * clipped, merged, or deleted.
2242 				 */
2243 				if (!vm_map_lookup_entry(map, saved_start,
2244 				    &tmp_entry)) {
2245 					if (flags & VM_MAP_WIRE_HOLESOK)
2246 						tmp_entry = tmp_entry->next;
2247 					else {
2248 						if (saved_start == start) {
2249 							/*
2250 							 * First_entry has been deleted.
2251 							 */
2252 							vm_map_unlock(map);
2253 							return (KERN_INVALID_ADDRESS);
2254 						}
2255 						end = saved_start;
2256 						rv = KERN_INVALID_ADDRESS;
2257 						goto done;
2258 					}
2259 				}
2260 				if (entry == first_entry)
2261 					first_entry = tmp_entry;
2262 				else
2263 					first_entry = NULL;
2264 				entry = tmp_entry;
2265 			}
2266 			last_timestamp = map->timestamp;
2267 			continue;
2268 		}
2269 		vm_map_clip_start(map, entry, start);
2270 		vm_map_clip_end(map, entry, end);
2271 		/*
2272 		 * Mark the entry in case the map lock is released.  (See
2273 		 * above.)
2274 		 */
2275 		entry->eflags |= MAP_ENTRY_IN_TRANSITION;
2276 		/*
2277 		 * Check the map for holes in the specified region.
2278 		 * If VM_MAP_WIRE_HOLESOK was specified, skip this check.
2279 		 */
2280 		if (((flags & VM_MAP_WIRE_HOLESOK) == 0) &&
2281 		    (entry->end < end && (entry->next == &map->header ||
2282 		    entry->next->start > entry->end))) {
2283 			end = entry->end;
2284 			rv = KERN_INVALID_ADDRESS;
2285 			goto done;
2286 		}
2287 		/*
2288 		 * If system unwiring, require that the entry is system wired.
2289 		 */
2290 		if (!user_unwire &&
2291 		    vm_map_entry_system_wired_count(entry) == 0) {
2292 			end = entry->end;
2293 			rv = KERN_INVALID_ARGUMENT;
2294 			goto done;
2295 		}
2296 		entry = entry->next;
2297 	}
2298 	rv = KERN_SUCCESS;
2299 done:
2300 	need_wakeup = FALSE;
2301 	if (first_entry == NULL) {
2302 		result = vm_map_lookup_entry(map, start, &first_entry);
2303 		if (!result && (flags & VM_MAP_WIRE_HOLESOK))
2304 			first_entry = first_entry->next;
2305 		else
2306 			KASSERT(result, ("vm_map_unwire: lookup failed"));
2307 	}
2308 	entry = first_entry;
2309 	while (entry != &map->header && entry->start < end) {
2310 		if (rv == KERN_SUCCESS && (!user_unwire ||
2311 		    (entry->eflags & MAP_ENTRY_USER_WIRED))) {
2312 			if (user_unwire)
2313 				entry->eflags &= ~MAP_ENTRY_USER_WIRED;
2314 			entry->wired_count--;
2315 			if (entry->wired_count == 0) {
2316 				/*
2317 				 * Retain the map lock.
2318 				 */
2319 				vm_fault_unwire(map, entry->start, entry->end,
2320 				    entry->object.vm_object != NULL &&
2321 				    (entry->object.vm_object->flags &
2322 				    OBJ_FICTITIOUS) != 0);
2323 			}
2324 		}
2325 		KASSERT(entry->eflags & MAP_ENTRY_IN_TRANSITION,
2326 			("vm_map_unwire: in-transition flag missing"));
2327 		entry->eflags &= ~MAP_ENTRY_IN_TRANSITION;
2328 		if (entry->eflags & MAP_ENTRY_NEEDS_WAKEUP) {
2329 			entry->eflags &= ~MAP_ENTRY_NEEDS_WAKEUP;
2330 			need_wakeup = TRUE;
2331 		}
2332 		vm_map_simplify_entry(map, entry);
2333 		entry = entry->next;
2334 	}
2335 	vm_map_unlock(map);
2336 	if (need_wakeup)
2337 		vm_map_wakeup(map);
2338 	return (rv);
2339 }
2340 
2341 /*
2342  *	vm_map_wire:
2343  *
2344  *	Implements both kernel and user wiring.
2345  */
2346 int
2347 vm_map_wire(vm_map_t map, vm_offset_t start, vm_offset_t end,
2348     int flags)
2349 {
2350 	vm_map_entry_t entry, first_entry, tmp_entry;
2351 	vm_offset_t saved_end, saved_start;
2352 	unsigned int last_timestamp;
2353 	int rv;
2354 	boolean_t fictitious, need_wakeup, result, user_wire;
2355 	vm_prot_t prot;
2356 
2357 	prot = 0;
2358 	if (flags & VM_MAP_WIRE_WRITE)
2359 		prot |= VM_PROT_WRITE;
2360 	user_wire = (flags & VM_MAP_WIRE_USER) ? TRUE : FALSE;
2361 	vm_map_lock(map);
2362 	VM_MAP_RANGE_CHECK(map, start, end);
2363 	if (!vm_map_lookup_entry(map, start, &first_entry)) {
2364 		if (flags & VM_MAP_WIRE_HOLESOK)
2365 			first_entry = first_entry->next;
2366 		else {
2367 			vm_map_unlock(map);
2368 			return (KERN_INVALID_ADDRESS);
2369 		}
2370 	}
2371 	last_timestamp = map->timestamp;
2372 	entry = first_entry;
2373 	while (entry != &map->header && entry->start < end) {
2374 		if (entry->eflags & MAP_ENTRY_IN_TRANSITION) {
2375 			/*
2376 			 * We have not yet clipped the entry.
2377 			 */
2378 			saved_start = (start >= entry->start) ? start :
2379 			    entry->start;
2380 			entry->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
2381 			if (vm_map_unlock_and_wait(map, 0)) {
2382 				/*
2383 				 * Allow interruption of user wiring?
2384 				 */
2385 			}
2386 			vm_map_lock(map);
2387 			if (last_timestamp + 1 != map->timestamp) {
2388 				/*
2389 				 * Look again for the entry because the map was
2390 				 * modified while it was unlocked.
2391 				 * Specifically, the entry may have been
2392 				 * clipped, merged, or deleted.
2393 				 */
2394 				if (!vm_map_lookup_entry(map, saved_start,
2395 				    &tmp_entry)) {
2396 					if (flags & VM_MAP_WIRE_HOLESOK)
2397 						tmp_entry = tmp_entry->next;
2398 					else {
2399 						if (saved_start == start) {
2400 							/*
2401 							 * first_entry has been deleted.
2402 							 */
2403 							vm_map_unlock(map);
2404 							return (KERN_INVALID_ADDRESS);
2405 						}
2406 						end = saved_start;
2407 						rv = KERN_INVALID_ADDRESS;
2408 						goto done;
2409 					}
2410 				}
2411 				if (entry == first_entry)
2412 					first_entry = tmp_entry;
2413 				else
2414 					first_entry = NULL;
2415 				entry = tmp_entry;
2416 			}
2417 			last_timestamp = map->timestamp;
2418 			continue;
2419 		}
2420 		vm_map_clip_start(map, entry, start);
2421 		vm_map_clip_end(map, entry, end);
2422 		/*
2423 		 * Mark the entry in case the map lock is released.  (See
2424 		 * above.)
2425 		 */
2426 		entry->eflags |= MAP_ENTRY_IN_TRANSITION;
2427 		if ((entry->protection & (VM_PROT_READ | VM_PROT_EXECUTE)) == 0
2428 		    || (entry->protection & prot) != prot) {
2429 			entry->eflags |= MAP_ENTRY_WIRE_SKIPPED;
2430 			if ((flags & VM_MAP_WIRE_HOLESOK) == 0) {
2431 				end = entry->end;
2432 				rv = KERN_INVALID_ADDRESS;
2433 				goto done;
2434 			}
2435 			goto next_entry;
2436 		}
2437 		if (entry->wired_count == 0) {
2438 			entry->wired_count++;
2439 			saved_start = entry->start;
2440 			saved_end = entry->end;
2441 			fictitious = entry->object.vm_object != NULL &&
2442 			    (entry->object.vm_object->flags &
2443 			    OBJ_FICTITIOUS) != 0;
2444 			/*
2445 			 * Release the map lock, relying on the in-transition
2446 			 * mark.  Mark the map busy for fork.
2447 			 */
2448 			vm_map_busy(map);
2449 			vm_map_unlock(map);
2450 			rv = vm_fault_wire(map, saved_start, saved_end,
2451 			    fictitious);
2452 			vm_map_lock(map);
2453 			vm_map_unbusy(map);
2454 			if (last_timestamp + 1 != map->timestamp) {
2455 				/*
2456 				 * Look again for the entry because the map was
2457 				 * modified while it was unlocked.  The entry
2458 				 * may have been clipped, but NOT merged or
2459 				 * deleted.
2460 				 */
2461 				result = vm_map_lookup_entry(map, saved_start,
2462 				    &tmp_entry);
2463 				KASSERT(result, ("vm_map_wire: lookup failed"));
2464 				if (entry == first_entry)
2465 					first_entry = tmp_entry;
2466 				else
2467 					first_entry = NULL;
2468 				entry = tmp_entry;
2469 				while (entry->end < saved_end) {
2470 					if (rv != KERN_SUCCESS) {
2471 						KASSERT(entry->wired_count == 1,
2472 						    ("vm_map_wire: bad count"));
2473 						entry->wired_count = -1;
2474 					}
2475 					entry = entry->next;
2476 				}
2477 			}
2478 			last_timestamp = map->timestamp;
2479 			if (rv != KERN_SUCCESS) {
2480 				KASSERT(entry->wired_count == 1,
2481 				    ("vm_map_wire: bad count"));
2482 				/*
2483 				 * Assign an out-of-range value to represent
2484 				 * the failure to wire this entry.
2485 				 */
2486 				entry->wired_count = -1;
2487 				end = entry->end;
2488 				goto done;
2489 			}
2490 		} else if (!user_wire ||
2491 			   (entry->eflags & MAP_ENTRY_USER_WIRED) == 0) {
2492 			entry->wired_count++;
2493 		}
2494 		/*
2495 		 * Check the map for holes in the specified region.
2496 		 * If VM_MAP_WIRE_HOLESOK was specified, skip this check.
2497 		 */
2498 	next_entry:
2499 		if (((flags & VM_MAP_WIRE_HOLESOK) == 0) &&
2500 		    (entry->end < end && (entry->next == &map->header ||
2501 		    entry->next->start > entry->end))) {
2502 			end = entry->end;
2503 			rv = KERN_INVALID_ADDRESS;
2504 			goto done;
2505 		}
2506 		entry = entry->next;
2507 	}
2508 	rv = KERN_SUCCESS;
2509 done:
2510 	need_wakeup = FALSE;
2511 	if (first_entry == NULL) {
2512 		result = vm_map_lookup_entry(map, start, &first_entry);
2513 		if (!result && (flags & VM_MAP_WIRE_HOLESOK))
2514 			first_entry = first_entry->next;
2515 		else
2516 			KASSERT(result, ("vm_map_wire: lookup failed"));
2517 	}
2518 	entry = first_entry;
2519 	while (entry != &map->header && entry->start < end) {
2520 		if ((entry->eflags & MAP_ENTRY_WIRE_SKIPPED) != 0)
2521 			goto next_entry_done;
2522 		if (rv == KERN_SUCCESS) {
2523 			if (user_wire)
2524 				entry->eflags |= MAP_ENTRY_USER_WIRED;
2525 		} else if (entry->wired_count == -1) {
2526 			/*
2527 			 * Wiring failed on this entry.  Thus, unwiring is
2528 			 * unnecessary.
2529 			 */
2530 			entry->wired_count = 0;
2531 		} else {
2532 			if (!user_wire ||
2533 			    (entry->eflags & MAP_ENTRY_USER_WIRED) == 0)
2534 				entry->wired_count--;
2535 			if (entry->wired_count == 0) {
2536 				/*
2537 				 * Retain the map lock.
2538 				 */
2539 				vm_fault_unwire(map, entry->start, entry->end,
2540 				    entry->object.vm_object != NULL &&
2541 				    (entry->object.vm_object->flags &
2542 				    OBJ_FICTITIOUS) != 0);
2543 			}
2544 		}
2545 	next_entry_done:
2546 		KASSERT(entry->eflags & MAP_ENTRY_IN_TRANSITION,
2547 			("vm_map_wire: in-transition flag missing"));
2548 		entry->eflags &= ~(MAP_ENTRY_IN_TRANSITION|MAP_ENTRY_WIRE_SKIPPED);
2549 		if (entry->eflags & MAP_ENTRY_NEEDS_WAKEUP) {
2550 			entry->eflags &= ~MAP_ENTRY_NEEDS_WAKEUP;
2551 			need_wakeup = TRUE;
2552 		}
2553 		vm_map_simplify_entry(map, entry);
2554 		entry = entry->next;
2555 	}
2556 	vm_map_unlock(map);
2557 	if (need_wakeup)
2558 		vm_map_wakeup(map);
2559 	return (rv);
2560 }
2561 
2562 /*
2563  * vm_map_sync
2564  *
2565  * Push any dirty cached pages in the address range to their pager.
2566  * If syncio is TRUE, dirty pages are written synchronously.
2567  * If invalidate is TRUE, any cached pages are freed as well.
2568  *
2569  * If the size of the region from start to end is zero, we are
2570  * supposed to flush all modified pages within the region containing
2571  * start.  Unfortunately, a region can be split or coalesced with
2572  * neighboring regions, making it difficult to determine what the
2573  * original region was.  Therefore, we approximate this requirement by
2574  * flushing the current region containing start.
2575  *
2576  * Returns an error if any part of the specified range is not mapped.
2577  */
2578 int
2579 vm_map_sync(
2580 	vm_map_t map,
2581 	vm_offset_t start,
2582 	vm_offset_t end,
2583 	boolean_t syncio,
2584 	boolean_t invalidate)
2585 {
2586 	vm_map_entry_t current;
2587 	vm_map_entry_t entry;
2588 	vm_size_t size;
2589 	vm_object_t object;
2590 	vm_ooffset_t offset;
2591 	unsigned int last_timestamp;
2592 	boolean_t failed;
2593 
2594 	vm_map_lock_read(map);
2595 	VM_MAP_RANGE_CHECK(map, start, end);
2596 	if (!vm_map_lookup_entry(map, start, &entry)) {
2597 		vm_map_unlock_read(map);
2598 		return (KERN_INVALID_ADDRESS);
2599 	} else if (start == end) {
2600 		start = entry->start;
2601 		end = entry->end;
2602 	}
2603 	/*
2604 	 * Make a first pass to check for user-wired memory and holes.
2605 	 */
2606 	for (current = entry; current != &map->header && current->start < end;
2607 	    current = current->next) {
2608 		if (invalidate && (current->eflags & MAP_ENTRY_USER_WIRED)) {
2609 			vm_map_unlock_read(map);
2610 			return (KERN_INVALID_ARGUMENT);
2611 		}
2612 		if (end > current->end &&
2613 		    (current->next == &map->header ||
2614 			current->end != current->next->start)) {
2615 			vm_map_unlock_read(map);
2616 			return (KERN_INVALID_ADDRESS);
2617 		}
2618 	}
2619 
2620 	if (invalidate)
2621 		pmap_remove(map->pmap, start, end);
2622 	failed = FALSE;
2623 
2624 	/*
2625 	 * Make a second pass, cleaning/uncaching pages from the indicated
2626 	 * objects as we go.
2627 	 */
2628 	for (current = entry; current != &map->header && current->start < end;) {
2629 		offset = current->offset + (start - current->start);
2630 		size = (end <= current->end ? end : current->end) - start;
2631 		if (current->eflags & MAP_ENTRY_IS_SUB_MAP) {
2632 			vm_map_t smap;
2633 			vm_map_entry_t tentry;
2634 			vm_size_t tsize;
2635 
2636 			smap = current->object.sub_map;
2637 			vm_map_lock_read(smap);
2638 			(void) vm_map_lookup_entry(smap, offset, &tentry);
2639 			tsize = tentry->end - offset;
2640 			if (tsize < size)
2641 				size = tsize;
2642 			object = tentry->object.vm_object;
2643 			offset = tentry->offset + (offset - tentry->start);
2644 			vm_map_unlock_read(smap);
2645 		} else {
2646 			object = current->object.vm_object;
2647 		}
2648 		vm_object_reference(object);
2649 		last_timestamp = map->timestamp;
2650 		vm_map_unlock_read(map);
2651 		if (!vm_object_sync(object, offset, size, syncio, invalidate))
2652 			failed = TRUE;
2653 		start += size;
2654 		vm_object_deallocate(object);
2655 		vm_map_lock_read(map);
2656 		if (last_timestamp == map->timestamp ||
2657 		    !vm_map_lookup_entry(map, start, &current))
2658 			current = current->next;
2659 	}
2660 
2661 	vm_map_unlock_read(map);
2662 	return (failed ? KERN_FAILURE : KERN_SUCCESS);
2663 }
2664 
2665 /*
2666  *	vm_map_entry_unwire:	[ internal use only ]
2667  *
2668  *	Make the region specified by this entry pageable.
2669  *
2670  *	The map in question should be locked.
2671  *	[This is the reason for this routine's existence.]
2672  */
2673 static void
2674 vm_map_entry_unwire(vm_map_t map, vm_map_entry_t entry)
2675 {
2676 	vm_fault_unwire(map, entry->start, entry->end,
2677 	    entry->object.vm_object != NULL &&
2678 	    (entry->object.vm_object->flags & OBJ_FICTITIOUS) != 0);
2679 	entry->wired_count = 0;
2680 }
2681 
2682 static void
2683 vm_map_entry_deallocate(vm_map_entry_t entry, boolean_t system_map)
2684 {
2685 
2686 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0)
2687 		vm_object_deallocate(entry->object.vm_object);
2688 	uma_zfree(system_map ? kmapentzone : mapentzone, entry);
2689 }
2690 
2691 /*
2692  *	vm_map_entry_delete:	[ internal use only ]
2693  *
2694  *	Deallocate the given entry from the target map.
2695  */
2696 static void
2697 vm_map_entry_delete(vm_map_t map, vm_map_entry_t entry)
2698 {
2699 	vm_object_t object;
2700 	vm_pindex_t offidxstart, offidxend, count, size1;
2701 	vm_ooffset_t size;
2702 
2703 	vm_map_entry_unlink(map, entry);
2704 	object = entry->object.vm_object;
2705 	size = entry->end - entry->start;
2706 	map->size -= size;
2707 
2708 	if (entry->cred != NULL) {
2709 		swap_release_by_cred(size, entry->cred);
2710 		crfree(entry->cred);
2711 	}
2712 
2713 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0 &&
2714 	    (object != NULL)) {
2715 		KASSERT(entry->cred == NULL || object->cred == NULL ||
2716 		    (entry->eflags & MAP_ENTRY_NEEDS_COPY),
2717 		    ("OVERCOMMIT vm_map_entry_delete: both cred %p", entry));
2718 		count = OFF_TO_IDX(size);
2719 		offidxstart = OFF_TO_IDX(entry->offset);
2720 		offidxend = offidxstart + count;
2721 		VM_OBJECT_WLOCK(object);
2722 		if (object->ref_count != 1 &&
2723 		    ((object->flags & (OBJ_NOSPLIT|OBJ_ONEMAPPING)) == OBJ_ONEMAPPING ||
2724 		    object == kernel_object || object == kmem_object)) {
2725 			vm_object_collapse(object);
2726 
2727 			/*
2728 			 * The option OBJPR_NOTMAPPED can be passed here
2729 			 * because vm_map_delete() already performed
2730 			 * pmap_remove() on the only mapping to this range
2731 			 * of pages.
2732 			 */
2733 			vm_object_page_remove(object, offidxstart, offidxend,
2734 			    OBJPR_NOTMAPPED);
2735 			if (object->type == OBJT_SWAP)
2736 				swap_pager_freespace(object, offidxstart, count);
2737 			if (offidxend >= object->size &&
2738 			    offidxstart < object->size) {
2739 				size1 = object->size;
2740 				object->size = offidxstart;
2741 				if (object->cred != NULL) {
2742 					size1 -= object->size;
2743 					KASSERT(object->charge >= ptoa(size1),
2744 					    ("vm_map_entry_delete: object->charge < 0"));
2745 					swap_release_by_cred(ptoa(size1), object->cred);
2746 					object->charge -= ptoa(size1);
2747 				}
2748 			}
2749 		}
2750 		VM_OBJECT_WUNLOCK(object);
2751 	} else
2752 		entry->object.vm_object = NULL;
2753 	if (map->system_map)
2754 		vm_map_entry_deallocate(entry, TRUE);
2755 	else {
2756 		entry->next = curthread->td_map_def_user;
2757 		curthread->td_map_def_user = entry;
2758 	}
2759 }
2760 
2761 /*
2762  *	vm_map_delete:	[ internal use only ]
2763  *
2764  *	Deallocates the given address range from the target
2765  *	map.
2766  */
2767 int
2768 vm_map_delete(vm_map_t map, vm_offset_t start, vm_offset_t end)
2769 {
2770 	vm_map_entry_t entry;
2771 	vm_map_entry_t first_entry;
2772 
2773 	VM_MAP_ASSERT_LOCKED(map);
2774 
2775 	/*
2776 	 * Find the start of the region, and clip it
2777 	 */
2778 	if (!vm_map_lookup_entry(map, start, &first_entry))
2779 		entry = first_entry->next;
2780 	else {
2781 		entry = first_entry;
2782 		vm_map_clip_start(map, entry, start);
2783 	}
2784 
2785 	/*
2786 	 * Step through all entries in this region
2787 	 */
2788 	while ((entry != &map->header) && (entry->start < end)) {
2789 		vm_map_entry_t next;
2790 
2791 		/*
2792 		 * Wait for wiring or unwiring of an entry to complete.
2793 		 * Also wait for any system wirings to disappear on
2794 		 * user maps.
2795 		 */
2796 		if ((entry->eflags & MAP_ENTRY_IN_TRANSITION) != 0 ||
2797 		    (vm_map_pmap(map) != kernel_pmap &&
2798 		    vm_map_entry_system_wired_count(entry) != 0)) {
2799 			unsigned int last_timestamp;
2800 			vm_offset_t saved_start;
2801 			vm_map_entry_t tmp_entry;
2802 
2803 			saved_start = entry->start;
2804 			entry->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
2805 			last_timestamp = map->timestamp;
2806 			(void) vm_map_unlock_and_wait(map, 0);
2807 			vm_map_lock(map);
2808 			if (last_timestamp + 1 != map->timestamp) {
2809 				/*
2810 				 * Look again for the entry because the map was
2811 				 * modified while it was unlocked.
2812 				 * Specifically, the entry may have been
2813 				 * clipped, merged, or deleted.
2814 				 */
2815 				if (!vm_map_lookup_entry(map, saved_start,
2816 							 &tmp_entry))
2817 					entry = tmp_entry->next;
2818 				else {
2819 					entry = tmp_entry;
2820 					vm_map_clip_start(map, entry,
2821 							  saved_start);
2822 				}
2823 			}
2824 			continue;
2825 		}
2826 		vm_map_clip_end(map, entry, end);
2827 
2828 		next = entry->next;
2829 
2830 		/*
2831 		 * Unwire before removing addresses from the pmap; otherwise,
2832 		 * unwiring will put the entries back in the pmap.
2833 		 */
2834 		if (entry->wired_count != 0) {
2835 			vm_map_entry_unwire(map, entry);
2836 		}
2837 
2838 		pmap_remove(map->pmap, entry->start, entry->end);
2839 
2840 		/*
2841 		 * Delete the entry only after removing all pmap
2842 		 * entries pointing to its pages.  (Otherwise, its
2843 		 * page frames may be reallocated, and any modify bits
2844 		 * will be set in the wrong object!)
2845 		 */
2846 		vm_map_entry_delete(map, entry);
2847 		entry = next;
2848 	}
2849 	return (KERN_SUCCESS);
2850 }
2851 
2852 /*
2853  *	vm_map_remove:
2854  *
2855  *	Remove the given address range from the target map.
2856  *	This is the exported form of vm_map_delete.
2857  */
2858 int
2859 vm_map_remove(vm_map_t map, vm_offset_t start, vm_offset_t end)
2860 {
2861 	int result;
2862 
2863 	vm_map_lock(map);
2864 	VM_MAP_RANGE_CHECK(map, start, end);
2865 	result = vm_map_delete(map, start, end);
2866 	vm_map_unlock(map);
2867 	return (result);
2868 }
2869 
2870 /*
2871  *	vm_map_check_protection:
2872  *
2873  *	Assert that the target map allows the specified privilege on the
2874  *	entire address region given.  The entire region must be allocated.
2875  *
2876  *	WARNING!  This code does not and should not check whether the
2877  *	contents of the region is accessible.  For example a smaller file
2878  *	might be mapped into a larger address space.
2879  *
2880  *	NOTE!  This code is also called by munmap().
2881  *
2882  *	The map must be locked.  A read lock is sufficient.
2883  */
2884 boolean_t
2885 vm_map_check_protection(vm_map_t map, vm_offset_t start, vm_offset_t end,
2886 			vm_prot_t protection)
2887 {
2888 	vm_map_entry_t entry;
2889 	vm_map_entry_t tmp_entry;
2890 
2891 	if (!vm_map_lookup_entry(map, start, &tmp_entry))
2892 		return (FALSE);
2893 	entry = tmp_entry;
2894 
2895 	while (start < end) {
2896 		if (entry == &map->header)
2897 			return (FALSE);
2898 		/*
2899 		 * No holes allowed!
2900 		 */
2901 		if (start < entry->start)
2902 			return (FALSE);
2903 		/*
2904 		 * Check protection associated with entry.
2905 		 */
2906 		if ((entry->protection & protection) != protection)
2907 			return (FALSE);
2908 		/* go to next entry */
2909 		start = entry->end;
2910 		entry = entry->next;
2911 	}
2912 	return (TRUE);
2913 }
2914 
2915 /*
2916  *	vm_map_copy_entry:
2917  *
2918  *	Copies the contents of the source entry to the destination
2919  *	entry.  The entries *must* be aligned properly.
2920  */
2921 static void
2922 vm_map_copy_entry(
2923 	vm_map_t src_map,
2924 	vm_map_t dst_map,
2925 	vm_map_entry_t src_entry,
2926 	vm_map_entry_t dst_entry,
2927 	vm_ooffset_t *fork_charge)
2928 {
2929 	vm_object_t src_object;
2930 	vm_map_entry_t fake_entry;
2931 	vm_offset_t size;
2932 	struct ucred *cred;
2933 	int charged;
2934 
2935 	VM_MAP_ASSERT_LOCKED(dst_map);
2936 
2937 	if ((dst_entry->eflags|src_entry->eflags) & MAP_ENTRY_IS_SUB_MAP)
2938 		return;
2939 
2940 	if (src_entry->wired_count == 0) {
2941 
2942 		/*
2943 		 * If the source entry is marked needs_copy, it is already
2944 		 * write-protected.
2945 		 */
2946 		if ((src_entry->eflags & MAP_ENTRY_NEEDS_COPY) == 0) {
2947 			pmap_protect(src_map->pmap,
2948 			    src_entry->start,
2949 			    src_entry->end,
2950 			    src_entry->protection & ~VM_PROT_WRITE);
2951 		}
2952 
2953 		/*
2954 		 * Make a copy of the object.
2955 		 */
2956 		size = src_entry->end - src_entry->start;
2957 		if ((src_object = src_entry->object.vm_object) != NULL) {
2958 			VM_OBJECT_WLOCK(src_object);
2959 			charged = ENTRY_CHARGED(src_entry);
2960 			if ((src_object->handle == NULL) &&
2961 				(src_object->type == OBJT_DEFAULT ||
2962 				 src_object->type == OBJT_SWAP)) {
2963 				vm_object_collapse(src_object);
2964 				if ((src_object->flags & (OBJ_NOSPLIT|OBJ_ONEMAPPING)) == OBJ_ONEMAPPING) {
2965 					vm_object_split(src_entry);
2966 					src_object = src_entry->object.vm_object;
2967 				}
2968 			}
2969 			vm_object_reference_locked(src_object);
2970 			vm_object_clear_flag(src_object, OBJ_ONEMAPPING);
2971 			if (src_entry->cred != NULL &&
2972 			    !(src_entry->eflags & MAP_ENTRY_NEEDS_COPY)) {
2973 				KASSERT(src_object->cred == NULL,
2974 				    ("OVERCOMMIT: vm_map_copy_entry: cred %p",
2975 				     src_object));
2976 				src_object->cred = src_entry->cred;
2977 				src_object->charge = size;
2978 			}
2979 			VM_OBJECT_WUNLOCK(src_object);
2980 			dst_entry->object.vm_object = src_object;
2981 			if (charged) {
2982 				cred = curthread->td_ucred;
2983 				crhold(cred);
2984 				dst_entry->cred = cred;
2985 				*fork_charge += size;
2986 				if (!(src_entry->eflags &
2987 				      MAP_ENTRY_NEEDS_COPY)) {
2988 					crhold(cred);
2989 					src_entry->cred = cred;
2990 					*fork_charge += size;
2991 				}
2992 			}
2993 			src_entry->eflags |= (MAP_ENTRY_COW|MAP_ENTRY_NEEDS_COPY);
2994 			dst_entry->eflags |= (MAP_ENTRY_COW|MAP_ENTRY_NEEDS_COPY);
2995 			dst_entry->offset = src_entry->offset;
2996 			if (src_entry->eflags & MAP_ENTRY_VN_WRITECNT) {
2997 				/*
2998 				 * MAP_ENTRY_VN_WRITECNT cannot
2999 				 * indicate write reference from
3000 				 * src_entry, since the entry is
3001 				 * marked as needs copy.  Allocate a
3002 				 * fake entry that is used to
3003 				 * decrement object->un_pager.vnp.writecount
3004 				 * at the appropriate time.  Attach
3005 				 * fake_entry to the deferred list.
3006 				 */
3007 				fake_entry = vm_map_entry_create(dst_map);
3008 				fake_entry->eflags = MAP_ENTRY_VN_WRITECNT;
3009 				src_entry->eflags &= ~MAP_ENTRY_VN_WRITECNT;
3010 				vm_object_reference(src_object);
3011 				fake_entry->object.vm_object = src_object;
3012 				fake_entry->start = src_entry->start;
3013 				fake_entry->end = src_entry->end;
3014 				fake_entry->next = curthread->td_map_def_user;
3015 				curthread->td_map_def_user = fake_entry;
3016 			}
3017 		} else {
3018 			dst_entry->object.vm_object = NULL;
3019 			dst_entry->offset = 0;
3020 			if (src_entry->cred != NULL) {
3021 				dst_entry->cred = curthread->td_ucred;
3022 				crhold(dst_entry->cred);
3023 				*fork_charge += size;
3024 			}
3025 		}
3026 
3027 		pmap_copy(dst_map->pmap, src_map->pmap, dst_entry->start,
3028 		    dst_entry->end - dst_entry->start, src_entry->start);
3029 	} else {
3030 		/*
3031 		 * Of course, wired down pages can't be set copy-on-write.
3032 		 * Cause wired pages to be copied into the new map by
3033 		 * simulating faults (the new pages are pageable)
3034 		 */
3035 		vm_fault_copy_entry(dst_map, src_map, dst_entry, src_entry,
3036 		    fork_charge);
3037 	}
3038 }
3039 
3040 /*
3041  * vmspace_map_entry_forked:
3042  * Update the newly-forked vmspace each time a map entry is inherited
3043  * or copied.  The values for vm_dsize and vm_tsize are approximate
3044  * (and mostly-obsolete ideas in the face of mmap(2) et al.)
3045  */
3046 static void
3047 vmspace_map_entry_forked(const struct vmspace *vm1, struct vmspace *vm2,
3048     vm_map_entry_t entry)
3049 {
3050 	vm_size_t entrysize;
3051 	vm_offset_t newend;
3052 
3053 	entrysize = entry->end - entry->start;
3054 	vm2->vm_map.size += entrysize;
3055 	if (entry->eflags & (MAP_ENTRY_GROWS_DOWN | MAP_ENTRY_GROWS_UP)) {
3056 		vm2->vm_ssize += btoc(entrysize);
3057 	} else if (entry->start >= (vm_offset_t)vm1->vm_daddr &&
3058 	    entry->start < (vm_offset_t)vm1->vm_daddr + ctob(vm1->vm_dsize)) {
3059 		newend = MIN(entry->end,
3060 		    (vm_offset_t)vm1->vm_daddr + ctob(vm1->vm_dsize));
3061 		vm2->vm_dsize += btoc(newend - entry->start);
3062 	} else if (entry->start >= (vm_offset_t)vm1->vm_taddr &&
3063 	    entry->start < (vm_offset_t)vm1->vm_taddr + ctob(vm1->vm_tsize)) {
3064 		newend = MIN(entry->end,
3065 		    (vm_offset_t)vm1->vm_taddr + ctob(vm1->vm_tsize));
3066 		vm2->vm_tsize += btoc(newend - entry->start);
3067 	}
3068 }
3069 
3070 /*
3071  * vmspace_fork:
3072  * Create a new process vmspace structure and vm_map
3073  * based on those of an existing process.  The new map
3074  * is based on the old map, according to the inheritance
3075  * values on the regions in that map.
3076  *
3077  * XXX It might be worth coalescing the entries added to the new vmspace.
3078  *
3079  * The source map must not be locked.
3080  */
3081 struct vmspace *
3082 vmspace_fork(struct vmspace *vm1, vm_ooffset_t *fork_charge)
3083 {
3084 	struct vmspace *vm2;
3085 	vm_map_t new_map, old_map;
3086 	vm_map_entry_t new_entry, old_entry;
3087 	vm_object_t object;
3088 	int locked;
3089 
3090 	old_map = &vm1->vm_map;
3091 	/* Copy immutable fields of vm1 to vm2. */
3092 	vm2 = vmspace_alloc(old_map->min_offset, old_map->max_offset);
3093 	if (vm2 == NULL)
3094 		return (NULL);
3095 	vm2->vm_taddr = vm1->vm_taddr;
3096 	vm2->vm_daddr = vm1->vm_daddr;
3097 	vm2->vm_maxsaddr = vm1->vm_maxsaddr;
3098 	vm_map_lock(old_map);
3099 	if (old_map->busy)
3100 		vm_map_wait_busy(old_map);
3101 	new_map = &vm2->vm_map;
3102 	locked = vm_map_trylock(new_map); /* trylock to silence WITNESS */
3103 	KASSERT(locked, ("vmspace_fork: lock failed"));
3104 
3105 	old_entry = old_map->header.next;
3106 
3107 	while (old_entry != &old_map->header) {
3108 		if (old_entry->eflags & MAP_ENTRY_IS_SUB_MAP)
3109 			panic("vm_map_fork: encountered a submap");
3110 
3111 		switch (old_entry->inheritance) {
3112 		case VM_INHERIT_NONE:
3113 			break;
3114 
3115 		case VM_INHERIT_SHARE:
3116 			/*
3117 			 * Clone the entry, creating the shared object if necessary.
3118 			 */
3119 			object = old_entry->object.vm_object;
3120 			if (object == NULL) {
3121 				object = vm_object_allocate(OBJT_DEFAULT,
3122 					atop(old_entry->end - old_entry->start));
3123 				old_entry->object.vm_object = object;
3124 				old_entry->offset = 0;
3125 				if (old_entry->cred != NULL) {
3126 					object->cred = old_entry->cred;
3127 					object->charge = old_entry->end -
3128 					    old_entry->start;
3129 					old_entry->cred = NULL;
3130 				}
3131 			}
3132 
3133 			/*
3134 			 * Add the reference before calling vm_object_shadow
3135 			 * to insure that a shadow object is created.
3136 			 */
3137 			vm_object_reference(object);
3138 			if (old_entry->eflags & MAP_ENTRY_NEEDS_COPY) {
3139 				vm_object_shadow(&old_entry->object.vm_object,
3140 				    &old_entry->offset,
3141 				    old_entry->end - old_entry->start);
3142 				old_entry->eflags &= ~MAP_ENTRY_NEEDS_COPY;
3143 				/* Transfer the second reference too. */
3144 				vm_object_reference(
3145 				    old_entry->object.vm_object);
3146 
3147 				/*
3148 				 * As in vm_map_simplify_entry(), the
3149 				 * vnode lock will not be acquired in
3150 				 * this call to vm_object_deallocate().
3151 				 */
3152 				vm_object_deallocate(object);
3153 				object = old_entry->object.vm_object;
3154 			}
3155 			VM_OBJECT_WLOCK(object);
3156 			vm_object_clear_flag(object, OBJ_ONEMAPPING);
3157 			if (old_entry->cred != NULL) {
3158 				KASSERT(object->cred == NULL, ("vmspace_fork both cred"));
3159 				object->cred = old_entry->cred;
3160 				object->charge = old_entry->end - old_entry->start;
3161 				old_entry->cred = NULL;
3162 			}
3163 
3164 			/*
3165 			 * Assert the correct state of the vnode
3166 			 * v_writecount while the object is locked, to
3167 			 * not relock it later for the assertion
3168 			 * correctness.
3169 			 */
3170 			if (old_entry->eflags & MAP_ENTRY_VN_WRITECNT &&
3171 			    object->type == OBJT_VNODE) {
3172 				KASSERT(((struct vnode *)object->handle)->
3173 				    v_writecount > 0,
3174 				    ("vmspace_fork: v_writecount %p", object));
3175 				KASSERT(object->un_pager.vnp.writemappings > 0,
3176 				    ("vmspace_fork: vnp.writecount %p",
3177 				    object));
3178 			}
3179 			VM_OBJECT_WUNLOCK(object);
3180 
3181 			/*
3182 			 * Clone the entry, referencing the shared object.
3183 			 */
3184 			new_entry = vm_map_entry_create(new_map);
3185 			*new_entry = *old_entry;
3186 			new_entry->eflags &= ~(MAP_ENTRY_USER_WIRED |
3187 			    MAP_ENTRY_IN_TRANSITION);
3188 			new_entry->wired_count = 0;
3189 			if (new_entry->eflags & MAP_ENTRY_VN_WRITECNT) {
3190 				vnode_pager_update_writecount(object,
3191 				    new_entry->start, new_entry->end);
3192 			}
3193 
3194 			/*
3195 			 * Insert the entry into the new map -- we know we're
3196 			 * inserting at the end of the new map.
3197 			 */
3198 			vm_map_entry_link(new_map, new_map->header.prev,
3199 			    new_entry);
3200 			vmspace_map_entry_forked(vm1, vm2, new_entry);
3201 
3202 			/*
3203 			 * Update the physical map
3204 			 */
3205 			pmap_copy(new_map->pmap, old_map->pmap,
3206 			    new_entry->start,
3207 			    (old_entry->end - old_entry->start),
3208 			    old_entry->start);
3209 			break;
3210 
3211 		case VM_INHERIT_COPY:
3212 			/*
3213 			 * Clone the entry and link into the map.
3214 			 */
3215 			new_entry = vm_map_entry_create(new_map);
3216 			*new_entry = *old_entry;
3217 			/*
3218 			 * Copied entry is COW over the old object.
3219 			 */
3220 			new_entry->eflags &= ~(MAP_ENTRY_USER_WIRED |
3221 			    MAP_ENTRY_IN_TRANSITION | MAP_ENTRY_VN_WRITECNT);
3222 			new_entry->wired_count = 0;
3223 			new_entry->object.vm_object = NULL;
3224 			new_entry->cred = NULL;
3225 			vm_map_entry_link(new_map, new_map->header.prev,
3226 			    new_entry);
3227 			vmspace_map_entry_forked(vm1, vm2, new_entry);
3228 			vm_map_copy_entry(old_map, new_map, old_entry,
3229 			    new_entry, fork_charge);
3230 			break;
3231 		}
3232 		old_entry = old_entry->next;
3233 	}
3234 	/*
3235 	 * Use inlined vm_map_unlock() to postpone handling the deferred
3236 	 * map entries, which cannot be done until both old_map and
3237 	 * new_map locks are released.
3238 	 */
3239 	sx_xunlock(&old_map->lock);
3240 	sx_xunlock(&new_map->lock);
3241 	vm_map_process_deferred();
3242 
3243 	return (vm2);
3244 }
3245 
3246 int
3247 vm_map_stack(vm_map_t map, vm_offset_t addrbos, vm_size_t max_ssize,
3248     vm_prot_t prot, vm_prot_t max, int cow)
3249 {
3250 	vm_map_entry_t new_entry, prev_entry;
3251 	vm_offset_t bot, top;
3252 	vm_size_t growsize, init_ssize;
3253 	int orient, rv;
3254 	rlim_t lmemlim, vmemlim;
3255 
3256 	/*
3257 	 * The stack orientation is piggybacked with the cow argument.
3258 	 * Extract it into orient and mask the cow argument so that we
3259 	 * don't pass it around further.
3260 	 * NOTE: We explicitly allow bi-directional stacks.
3261 	 */
3262 	orient = cow & (MAP_STACK_GROWS_DOWN|MAP_STACK_GROWS_UP);
3263 	cow &= ~orient;
3264 	KASSERT(orient != 0, ("No stack grow direction"));
3265 
3266 	if (addrbos < vm_map_min(map) ||
3267 	    addrbos > vm_map_max(map) ||
3268 	    addrbos + max_ssize < addrbos)
3269 		return (KERN_NO_SPACE);
3270 
3271 	growsize = sgrowsiz;
3272 	init_ssize = (max_ssize < growsize) ? max_ssize : growsize;
3273 
3274 	PROC_LOCK(curproc);
3275 	lmemlim = lim_cur(curproc, RLIMIT_MEMLOCK);
3276 	vmemlim = lim_cur(curproc, RLIMIT_VMEM);
3277 	PROC_UNLOCK(curproc);
3278 
3279 	vm_map_lock(map);
3280 
3281 	/* If addr is already mapped, no go */
3282 	if (vm_map_lookup_entry(map, addrbos, &prev_entry)) {
3283 		vm_map_unlock(map);
3284 		return (KERN_NO_SPACE);
3285 	}
3286 
3287 	if (!old_mlock && map->flags & MAP_WIREFUTURE) {
3288 		if (ptoa(pmap_wired_count(map->pmap)) + init_ssize > lmemlim) {
3289 			vm_map_unlock(map);
3290 			return (KERN_NO_SPACE);
3291 		}
3292 	}
3293 
3294 	/* If we would blow our VMEM resource limit, no go */
3295 	if (map->size + init_ssize > vmemlim) {
3296 		vm_map_unlock(map);
3297 		return (KERN_NO_SPACE);
3298 	}
3299 
3300 	/*
3301 	 * If we can't accomodate max_ssize in the current mapping, no go.
3302 	 * However, we need to be aware that subsequent user mappings might
3303 	 * map into the space we have reserved for stack, and currently this
3304 	 * space is not protected.
3305 	 *
3306 	 * Hopefully we will at least detect this condition when we try to
3307 	 * grow the stack.
3308 	 */
3309 	if ((prev_entry->next != &map->header) &&
3310 	    (prev_entry->next->start < addrbos + max_ssize)) {
3311 		vm_map_unlock(map);
3312 		return (KERN_NO_SPACE);
3313 	}
3314 
3315 	/*
3316 	 * We initially map a stack of only init_ssize.  We will grow as
3317 	 * needed later.  Depending on the orientation of the stack (i.e.
3318 	 * the grow direction) we either map at the top of the range, the
3319 	 * bottom of the range or in the middle.
3320 	 *
3321 	 * Note: we would normally expect prot and max to be VM_PROT_ALL,
3322 	 * and cow to be 0.  Possibly we should eliminate these as input
3323 	 * parameters, and just pass these values here in the insert call.
3324 	 */
3325 	if (orient == MAP_STACK_GROWS_DOWN)
3326 		bot = addrbos + max_ssize - init_ssize;
3327 	else if (orient == MAP_STACK_GROWS_UP)
3328 		bot = addrbos;
3329 	else
3330 		bot = round_page(addrbos + max_ssize/2 - init_ssize/2);
3331 	top = bot + init_ssize;
3332 	rv = vm_map_insert(map, NULL, 0, bot, top, prot, max, cow);
3333 
3334 	/* Now set the avail_ssize amount. */
3335 	if (rv == KERN_SUCCESS) {
3336 		if (prev_entry != &map->header)
3337 			vm_map_clip_end(map, prev_entry, bot);
3338 		new_entry = prev_entry->next;
3339 		if (new_entry->end != top || new_entry->start != bot)
3340 			panic("Bad entry start/end for new stack entry");
3341 
3342 		new_entry->avail_ssize = max_ssize - init_ssize;
3343 		if (orient & MAP_STACK_GROWS_DOWN)
3344 			new_entry->eflags |= MAP_ENTRY_GROWS_DOWN;
3345 		if (orient & MAP_STACK_GROWS_UP)
3346 			new_entry->eflags |= MAP_ENTRY_GROWS_UP;
3347 	}
3348 
3349 	vm_map_unlock(map);
3350 	return (rv);
3351 }
3352 
3353 static int stack_guard_page = 0;
3354 TUNABLE_INT("security.bsd.stack_guard_page", &stack_guard_page);
3355 SYSCTL_INT(_security_bsd, OID_AUTO, stack_guard_page, CTLFLAG_RW,
3356     &stack_guard_page, 0,
3357     "Insert stack guard page ahead of the growable segments.");
3358 
3359 /* Attempts to grow a vm stack entry.  Returns KERN_SUCCESS if the
3360  * desired address is already mapped, or if we successfully grow
3361  * the stack.  Also returns KERN_SUCCESS if addr is outside the
3362  * stack range (this is strange, but preserves compatibility with
3363  * the grow function in vm_machdep.c).
3364  */
3365 int
3366 vm_map_growstack(struct proc *p, vm_offset_t addr)
3367 {
3368 	vm_map_entry_t next_entry, prev_entry;
3369 	vm_map_entry_t new_entry, stack_entry;
3370 	struct vmspace *vm = p->p_vmspace;
3371 	vm_map_t map = &vm->vm_map;
3372 	vm_offset_t end;
3373 	vm_size_t growsize;
3374 	size_t grow_amount, max_grow;
3375 	rlim_t lmemlim, stacklim, vmemlim;
3376 	int is_procstack, rv;
3377 	struct ucred *cred;
3378 #ifdef notyet
3379 	uint64_t limit;
3380 #endif
3381 #ifdef RACCT
3382 	int error;
3383 #endif
3384 
3385 Retry:
3386 	PROC_LOCK(p);
3387 	lmemlim = lim_cur(p, RLIMIT_MEMLOCK);
3388 	stacklim = lim_cur(p, RLIMIT_STACK);
3389 	vmemlim = lim_cur(p, RLIMIT_VMEM);
3390 	PROC_UNLOCK(p);
3391 
3392 	vm_map_lock_read(map);
3393 
3394 	/* If addr is already in the entry range, no need to grow.*/
3395 	if (vm_map_lookup_entry(map, addr, &prev_entry)) {
3396 		vm_map_unlock_read(map);
3397 		return (KERN_SUCCESS);
3398 	}
3399 
3400 	next_entry = prev_entry->next;
3401 	if (!(prev_entry->eflags & MAP_ENTRY_GROWS_UP)) {
3402 		/*
3403 		 * This entry does not grow upwards. Since the address lies
3404 		 * beyond this entry, the next entry (if one exists) has to
3405 		 * be a downward growable entry. The entry list header is
3406 		 * never a growable entry, so it suffices to check the flags.
3407 		 */
3408 		if (!(next_entry->eflags & MAP_ENTRY_GROWS_DOWN)) {
3409 			vm_map_unlock_read(map);
3410 			return (KERN_SUCCESS);
3411 		}
3412 		stack_entry = next_entry;
3413 	} else {
3414 		/*
3415 		 * This entry grows upward. If the next entry does not at
3416 		 * least grow downwards, this is the entry we need to grow.
3417 		 * otherwise we have two possible choices and we have to
3418 		 * select one.
3419 		 */
3420 		if (next_entry->eflags & MAP_ENTRY_GROWS_DOWN) {
3421 			/*
3422 			 * We have two choices; grow the entry closest to
3423 			 * the address to minimize the amount of growth.
3424 			 */
3425 			if (addr - prev_entry->end <= next_entry->start - addr)
3426 				stack_entry = prev_entry;
3427 			else
3428 				stack_entry = next_entry;
3429 		} else
3430 			stack_entry = prev_entry;
3431 	}
3432 
3433 	if (stack_entry == next_entry) {
3434 		KASSERT(stack_entry->eflags & MAP_ENTRY_GROWS_DOWN, ("foo"));
3435 		KASSERT(addr < stack_entry->start, ("foo"));
3436 		end = (prev_entry != &map->header) ? prev_entry->end :
3437 		    stack_entry->start - stack_entry->avail_ssize;
3438 		grow_amount = roundup(stack_entry->start - addr, PAGE_SIZE);
3439 		max_grow = stack_entry->start - end;
3440 	} else {
3441 		KASSERT(stack_entry->eflags & MAP_ENTRY_GROWS_UP, ("foo"));
3442 		KASSERT(addr >= stack_entry->end, ("foo"));
3443 		end = (next_entry != &map->header) ? next_entry->start :
3444 		    stack_entry->end + stack_entry->avail_ssize;
3445 		grow_amount = roundup(addr + 1 - stack_entry->end, PAGE_SIZE);
3446 		max_grow = end - stack_entry->end;
3447 	}
3448 
3449 	if (grow_amount > stack_entry->avail_ssize) {
3450 		vm_map_unlock_read(map);
3451 		return (KERN_NO_SPACE);
3452 	}
3453 
3454 	/*
3455 	 * If there is no longer enough space between the entries nogo, and
3456 	 * adjust the available space.  Note: this  should only happen if the
3457 	 * user has mapped into the stack area after the stack was created,
3458 	 * and is probably an error.
3459 	 *
3460 	 * This also effectively destroys any guard page the user might have
3461 	 * intended by limiting the stack size.
3462 	 */
3463 	if (grow_amount + (stack_guard_page ? PAGE_SIZE : 0) > max_grow) {
3464 		if (vm_map_lock_upgrade(map))
3465 			goto Retry;
3466 
3467 		stack_entry->avail_ssize = max_grow;
3468 
3469 		vm_map_unlock(map);
3470 		return (KERN_NO_SPACE);
3471 	}
3472 
3473 	is_procstack = (addr >= (vm_offset_t)vm->vm_maxsaddr) ? 1 : 0;
3474 
3475 	/*
3476 	 * If this is the main process stack, see if we're over the stack
3477 	 * limit.
3478 	 */
3479 	if (is_procstack && (ctob(vm->vm_ssize) + grow_amount > stacklim)) {
3480 		vm_map_unlock_read(map);
3481 		return (KERN_NO_SPACE);
3482 	}
3483 #ifdef RACCT
3484 	PROC_LOCK(p);
3485 	if (is_procstack &&
3486 	    racct_set(p, RACCT_STACK, ctob(vm->vm_ssize) + grow_amount)) {
3487 		PROC_UNLOCK(p);
3488 		vm_map_unlock_read(map);
3489 		return (KERN_NO_SPACE);
3490 	}
3491 	PROC_UNLOCK(p);
3492 #endif
3493 
3494 	/* Round up the grow amount modulo sgrowsiz */
3495 	growsize = sgrowsiz;
3496 	grow_amount = roundup(grow_amount, growsize);
3497 	if (grow_amount > stack_entry->avail_ssize)
3498 		grow_amount = stack_entry->avail_ssize;
3499 	if (is_procstack && (ctob(vm->vm_ssize) + grow_amount > stacklim)) {
3500 		grow_amount = trunc_page((vm_size_t)stacklim) -
3501 		    ctob(vm->vm_ssize);
3502 	}
3503 #ifdef notyet
3504 	PROC_LOCK(p);
3505 	limit = racct_get_available(p, RACCT_STACK);
3506 	PROC_UNLOCK(p);
3507 	if (is_procstack && (ctob(vm->vm_ssize) + grow_amount > limit))
3508 		grow_amount = limit - ctob(vm->vm_ssize);
3509 #endif
3510 	if (!old_mlock && map->flags & MAP_WIREFUTURE) {
3511 		if (ptoa(pmap_wired_count(map->pmap)) + grow_amount > lmemlim) {
3512 			vm_map_unlock_read(map);
3513 			rv = KERN_NO_SPACE;
3514 			goto out;
3515 		}
3516 #ifdef RACCT
3517 		PROC_LOCK(p);
3518 		if (racct_set(p, RACCT_MEMLOCK,
3519 		    ptoa(pmap_wired_count(map->pmap)) + grow_amount)) {
3520 			PROC_UNLOCK(p);
3521 			vm_map_unlock_read(map);
3522 			rv = KERN_NO_SPACE;
3523 			goto out;
3524 		}
3525 		PROC_UNLOCK(p);
3526 #endif
3527 	}
3528 	/* If we would blow our VMEM resource limit, no go */
3529 	if (map->size + grow_amount > vmemlim) {
3530 		vm_map_unlock_read(map);
3531 		rv = KERN_NO_SPACE;
3532 		goto out;
3533 	}
3534 #ifdef RACCT
3535 	PROC_LOCK(p);
3536 	if (racct_set(p, RACCT_VMEM, map->size + grow_amount)) {
3537 		PROC_UNLOCK(p);
3538 		vm_map_unlock_read(map);
3539 		rv = KERN_NO_SPACE;
3540 		goto out;
3541 	}
3542 	PROC_UNLOCK(p);
3543 #endif
3544 
3545 	if (vm_map_lock_upgrade(map))
3546 		goto Retry;
3547 
3548 	if (stack_entry == next_entry) {
3549 		/*
3550 		 * Growing downward.
3551 		 */
3552 		/* Get the preliminary new entry start value */
3553 		addr = stack_entry->start - grow_amount;
3554 
3555 		/*
3556 		 * If this puts us into the previous entry, cut back our
3557 		 * growth to the available space. Also, see the note above.
3558 		 */
3559 		if (addr < end) {
3560 			stack_entry->avail_ssize = max_grow;
3561 			addr = end;
3562 			if (stack_guard_page)
3563 				addr += PAGE_SIZE;
3564 		}
3565 
3566 		rv = vm_map_insert(map, NULL, 0, addr, stack_entry->start,
3567 		    next_entry->protection, next_entry->max_protection, 0);
3568 
3569 		/* Adjust the available stack space by the amount we grew. */
3570 		if (rv == KERN_SUCCESS) {
3571 			if (prev_entry != &map->header)
3572 				vm_map_clip_end(map, prev_entry, addr);
3573 			new_entry = prev_entry->next;
3574 			KASSERT(new_entry == stack_entry->prev, ("foo"));
3575 			KASSERT(new_entry->end == stack_entry->start, ("foo"));
3576 			KASSERT(new_entry->start == addr, ("foo"));
3577 			grow_amount = new_entry->end - new_entry->start;
3578 			new_entry->avail_ssize = stack_entry->avail_ssize -
3579 			    grow_amount;
3580 			stack_entry->eflags &= ~MAP_ENTRY_GROWS_DOWN;
3581 			new_entry->eflags |= MAP_ENTRY_GROWS_DOWN;
3582 		}
3583 	} else {
3584 		/*
3585 		 * Growing upward.
3586 		 */
3587 		addr = stack_entry->end + grow_amount;
3588 
3589 		/*
3590 		 * If this puts us into the next entry, cut back our growth
3591 		 * to the available space. Also, see the note above.
3592 		 */
3593 		if (addr > end) {
3594 			stack_entry->avail_ssize = end - stack_entry->end;
3595 			addr = end;
3596 			if (stack_guard_page)
3597 				addr -= PAGE_SIZE;
3598 		}
3599 
3600 		grow_amount = addr - stack_entry->end;
3601 		cred = stack_entry->cred;
3602 		if (cred == NULL && stack_entry->object.vm_object != NULL)
3603 			cred = stack_entry->object.vm_object->cred;
3604 		if (cred != NULL && !swap_reserve_by_cred(grow_amount, cred))
3605 			rv = KERN_NO_SPACE;
3606 		/* Grow the underlying object if applicable. */
3607 		else if (stack_entry->object.vm_object == NULL ||
3608 			 vm_object_coalesce(stack_entry->object.vm_object,
3609 			 stack_entry->offset,
3610 			 (vm_size_t)(stack_entry->end - stack_entry->start),
3611 			 (vm_size_t)grow_amount, cred != NULL)) {
3612 			map->size += (addr - stack_entry->end);
3613 			/* Update the current entry. */
3614 			stack_entry->end = addr;
3615 			stack_entry->avail_ssize -= grow_amount;
3616 			vm_map_entry_resize_free(map, stack_entry);
3617 			rv = KERN_SUCCESS;
3618 
3619 			if (next_entry != &map->header)
3620 				vm_map_clip_start(map, next_entry, addr);
3621 		} else
3622 			rv = KERN_FAILURE;
3623 	}
3624 
3625 	if (rv == KERN_SUCCESS && is_procstack)
3626 		vm->vm_ssize += btoc(grow_amount);
3627 
3628 	vm_map_unlock(map);
3629 
3630 	/*
3631 	 * Heed the MAP_WIREFUTURE flag if it was set for this process.
3632 	 */
3633 	if (rv == KERN_SUCCESS && (map->flags & MAP_WIREFUTURE)) {
3634 		vm_map_wire(map,
3635 		    (stack_entry == next_entry) ? addr : addr - grow_amount,
3636 		    (stack_entry == next_entry) ? stack_entry->start : addr,
3637 		    (p->p_flag & P_SYSTEM)
3638 		    ? VM_MAP_WIRE_SYSTEM|VM_MAP_WIRE_NOHOLES
3639 		    : VM_MAP_WIRE_USER|VM_MAP_WIRE_NOHOLES);
3640 	}
3641 
3642 out:
3643 #ifdef RACCT
3644 	if (rv != KERN_SUCCESS) {
3645 		PROC_LOCK(p);
3646 		error = racct_set(p, RACCT_VMEM, map->size);
3647 		KASSERT(error == 0, ("decreasing RACCT_VMEM failed"));
3648 		if (!old_mlock) {
3649 			error = racct_set(p, RACCT_MEMLOCK,
3650 			    ptoa(pmap_wired_count(map->pmap)));
3651 			KASSERT(error == 0, ("decreasing RACCT_MEMLOCK failed"));
3652 		}
3653 	    	error = racct_set(p, RACCT_STACK, ctob(vm->vm_ssize));
3654 		KASSERT(error == 0, ("decreasing RACCT_STACK failed"));
3655 		PROC_UNLOCK(p);
3656 	}
3657 #endif
3658 
3659 	return (rv);
3660 }
3661 
3662 /*
3663  * Unshare the specified VM space for exec.  If other processes are
3664  * mapped to it, then create a new one.  The new vmspace is null.
3665  */
3666 int
3667 vmspace_exec(struct proc *p, vm_offset_t minuser, vm_offset_t maxuser)
3668 {
3669 	struct vmspace *oldvmspace = p->p_vmspace;
3670 	struct vmspace *newvmspace;
3671 
3672 	newvmspace = vmspace_alloc(minuser, maxuser);
3673 	if (newvmspace == NULL)
3674 		return (ENOMEM);
3675 	newvmspace->vm_swrss = oldvmspace->vm_swrss;
3676 	/*
3677 	 * This code is written like this for prototype purposes.  The
3678 	 * goal is to avoid running down the vmspace here, but let the
3679 	 * other process's that are still using the vmspace to finally
3680 	 * run it down.  Even though there is little or no chance of blocking
3681 	 * here, it is a good idea to keep this form for future mods.
3682 	 */
3683 	PROC_VMSPACE_LOCK(p);
3684 	p->p_vmspace = newvmspace;
3685 	PROC_VMSPACE_UNLOCK(p);
3686 	if (p == curthread->td_proc)
3687 		pmap_activate(curthread);
3688 	vmspace_free(oldvmspace);
3689 	return (0);
3690 }
3691 
3692 /*
3693  * Unshare the specified VM space for forcing COW.  This
3694  * is called by rfork, for the (RFMEM|RFPROC) == 0 case.
3695  */
3696 int
3697 vmspace_unshare(struct proc *p)
3698 {
3699 	struct vmspace *oldvmspace = p->p_vmspace;
3700 	struct vmspace *newvmspace;
3701 	vm_ooffset_t fork_charge;
3702 
3703 	if (oldvmspace->vm_refcnt == 1)
3704 		return (0);
3705 	fork_charge = 0;
3706 	newvmspace = vmspace_fork(oldvmspace, &fork_charge);
3707 	if (newvmspace == NULL)
3708 		return (ENOMEM);
3709 	if (!swap_reserve_by_cred(fork_charge, p->p_ucred)) {
3710 		vmspace_free(newvmspace);
3711 		return (ENOMEM);
3712 	}
3713 	PROC_VMSPACE_LOCK(p);
3714 	p->p_vmspace = newvmspace;
3715 	PROC_VMSPACE_UNLOCK(p);
3716 	if (p == curthread->td_proc)
3717 		pmap_activate(curthread);
3718 	vmspace_free(oldvmspace);
3719 	return (0);
3720 }
3721 
3722 /*
3723  *	vm_map_lookup:
3724  *
3725  *	Finds the VM object, offset, and
3726  *	protection for a given virtual address in the
3727  *	specified map, assuming a page fault of the
3728  *	type specified.
3729  *
3730  *	Leaves the map in question locked for read; return
3731  *	values are guaranteed until a vm_map_lookup_done
3732  *	call is performed.  Note that the map argument
3733  *	is in/out; the returned map must be used in
3734  *	the call to vm_map_lookup_done.
3735  *
3736  *	A handle (out_entry) is returned for use in
3737  *	vm_map_lookup_done, to make that fast.
3738  *
3739  *	If a lookup is requested with "write protection"
3740  *	specified, the map may be changed to perform virtual
3741  *	copying operations, although the data referenced will
3742  *	remain the same.
3743  */
3744 int
3745 vm_map_lookup(vm_map_t *var_map,		/* IN/OUT */
3746 	      vm_offset_t vaddr,
3747 	      vm_prot_t fault_typea,
3748 	      vm_map_entry_t *out_entry,	/* OUT */
3749 	      vm_object_t *object,		/* OUT */
3750 	      vm_pindex_t *pindex,		/* OUT */
3751 	      vm_prot_t *out_prot,		/* OUT */
3752 	      boolean_t *wired)			/* OUT */
3753 {
3754 	vm_map_entry_t entry;
3755 	vm_map_t map = *var_map;
3756 	vm_prot_t prot;
3757 	vm_prot_t fault_type = fault_typea;
3758 	vm_object_t eobject;
3759 	vm_size_t size;
3760 	struct ucred *cred;
3761 
3762 RetryLookup:;
3763 
3764 	vm_map_lock_read(map);
3765 
3766 	/*
3767 	 * Lookup the faulting address.
3768 	 */
3769 	if (!vm_map_lookup_entry(map, vaddr, out_entry)) {
3770 		vm_map_unlock_read(map);
3771 		return (KERN_INVALID_ADDRESS);
3772 	}
3773 
3774 	entry = *out_entry;
3775 
3776 	/*
3777 	 * Handle submaps.
3778 	 */
3779 	if (entry->eflags & MAP_ENTRY_IS_SUB_MAP) {
3780 		vm_map_t old_map = map;
3781 
3782 		*var_map = map = entry->object.sub_map;
3783 		vm_map_unlock_read(old_map);
3784 		goto RetryLookup;
3785 	}
3786 
3787 	/*
3788 	 * Check whether this task is allowed to have this page.
3789 	 */
3790 	prot = entry->protection;
3791 	fault_type &= (VM_PROT_READ|VM_PROT_WRITE|VM_PROT_EXECUTE);
3792 	if ((fault_type & prot) != fault_type || prot == VM_PROT_NONE) {
3793 		vm_map_unlock_read(map);
3794 		return (KERN_PROTECTION_FAILURE);
3795 	}
3796 	if ((entry->eflags & MAP_ENTRY_USER_WIRED) &&
3797 	    (entry->eflags & MAP_ENTRY_COW) &&
3798 	    (fault_type & VM_PROT_WRITE)) {
3799 		vm_map_unlock_read(map);
3800 		return (KERN_PROTECTION_FAILURE);
3801 	}
3802 
3803 	/*
3804 	 * If this page is not pageable, we have to get it for all possible
3805 	 * accesses.
3806 	 */
3807 	*wired = (entry->wired_count != 0);
3808 	if (*wired)
3809 		fault_type = entry->protection;
3810 	size = entry->end - entry->start;
3811 	/*
3812 	 * If the entry was copy-on-write, we either ...
3813 	 */
3814 	if (entry->eflags & MAP_ENTRY_NEEDS_COPY) {
3815 		/*
3816 		 * If we want to write the page, we may as well handle that
3817 		 * now since we've got the map locked.
3818 		 *
3819 		 * If we don't need to write the page, we just demote the
3820 		 * permissions allowed.
3821 		 */
3822 		if ((fault_type & VM_PROT_WRITE) != 0 ||
3823 		    (fault_typea & VM_PROT_COPY) != 0) {
3824 			/*
3825 			 * Make a new object, and place it in the object
3826 			 * chain.  Note that no new references have appeared
3827 			 * -- one just moved from the map to the new
3828 			 * object.
3829 			 */
3830 			if (vm_map_lock_upgrade(map))
3831 				goto RetryLookup;
3832 
3833 			if (entry->cred == NULL) {
3834 				/*
3835 				 * The debugger owner is charged for
3836 				 * the memory.
3837 				 */
3838 				cred = curthread->td_ucred;
3839 				crhold(cred);
3840 				if (!swap_reserve_by_cred(size, cred)) {
3841 					crfree(cred);
3842 					vm_map_unlock(map);
3843 					return (KERN_RESOURCE_SHORTAGE);
3844 				}
3845 				entry->cred = cred;
3846 			}
3847 			vm_object_shadow(&entry->object.vm_object,
3848 			    &entry->offset, size);
3849 			entry->eflags &= ~MAP_ENTRY_NEEDS_COPY;
3850 			eobject = entry->object.vm_object;
3851 			if (eobject->cred != NULL) {
3852 				/*
3853 				 * The object was not shadowed.
3854 				 */
3855 				swap_release_by_cred(size, entry->cred);
3856 				crfree(entry->cred);
3857 				entry->cred = NULL;
3858 			} else if (entry->cred != NULL) {
3859 				VM_OBJECT_WLOCK(eobject);
3860 				eobject->cred = entry->cred;
3861 				eobject->charge = size;
3862 				VM_OBJECT_WUNLOCK(eobject);
3863 				entry->cred = NULL;
3864 			}
3865 
3866 			vm_map_lock_downgrade(map);
3867 		} else {
3868 			/*
3869 			 * We're attempting to read a copy-on-write page --
3870 			 * don't allow writes.
3871 			 */
3872 			prot &= ~VM_PROT_WRITE;
3873 		}
3874 	}
3875 
3876 	/*
3877 	 * Create an object if necessary.
3878 	 */
3879 	if (entry->object.vm_object == NULL &&
3880 	    !map->system_map) {
3881 		if (vm_map_lock_upgrade(map))
3882 			goto RetryLookup;
3883 		entry->object.vm_object = vm_object_allocate(OBJT_DEFAULT,
3884 		    atop(size));
3885 		entry->offset = 0;
3886 		if (entry->cred != NULL) {
3887 			VM_OBJECT_WLOCK(entry->object.vm_object);
3888 			entry->object.vm_object->cred = entry->cred;
3889 			entry->object.vm_object->charge = size;
3890 			VM_OBJECT_WUNLOCK(entry->object.vm_object);
3891 			entry->cred = NULL;
3892 		}
3893 		vm_map_lock_downgrade(map);
3894 	}
3895 
3896 	/*
3897 	 * Return the object/offset from this entry.  If the entry was
3898 	 * copy-on-write or empty, it has been fixed up.
3899 	 */
3900 	*pindex = OFF_TO_IDX((vaddr - entry->start) + entry->offset);
3901 	*object = entry->object.vm_object;
3902 
3903 	*out_prot = prot;
3904 	return (KERN_SUCCESS);
3905 }
3906 
3907 /*
3908  *	vm_map_lookup_locked:
3909  *
3910  *	Lookup the faulting address.  A version of vm_map_lookup that returns
3911  *      KERN_FAILURE instead of blocking on map lock or memory allocation.
3912  */
3913 int
3914 vm_map_lookup_locked(vm_map_t *var_map,		/* IN/OUT */
3915 		     vm_offset_t vaddr,
3916 		     vm_prot_t fault_typea,
3917 		     vm_map_entry_t *out_entry,	/* OUT */
3918 		     vm_object_t *object,	/* OUT */
3919 		     vm_pindex_t *pindex,	/* OUT */
3920 		     vm_prot_t *out_prot,	/* OUT */
3921 		     boolean_t *wired)		/* OUT */
3922 {
3923 	vm_map_entry_t entry;
3924 	vm_map_t map = *var_map;
3925 	vm_prot_t prot;
3926 	vm_prot_t fault_type = fault_typea;
3927 
3928 	/*
3929 	 * Lookup the faulting address.
3930 	 */
3931 	if (!vm_map_lookup_entry(map, vaddr, out_entry))
3932 		return (KERN_INVALID_ADDRESS);
3933 
3934 	entry = *out_entry;
3935 
3936 	/*
3937 	 * Fail if the entry refers to a submap.
3938 	 */
3939 	if (entry->eflags & MAP_ENTRY_IS_SUB_MAP)
3940 		return (KERN_FAILURE);
3941 
3942 	/*
3943 	 * Check whether this task is allowed to have this page.
3944 	 */
3945 	prot = entry->protection;
3946 	fault_type &= VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE;
3947 	if ((fault_type & prot) != fault_type)
3948 		return (KERN_PROTECTION_FAILURE);
3949 	if ((entry->eflags & MAP_ENTRY_USER_WIRED) &&
3950 	    (entry->eflags & MAP_ENTRY_COW) &&
3951 	    (fault_type & VM_PROT_WRITE))
3952 		return (KERN_PROTECTION_FAILURE);
3953 
3954 	/*
3955 	 * If this page is not pageable, we have to get it for all possible
3956 	 * accesses.
3957 	 */
3958 	*wired = (entry->wired_count != 0);
3959 	if (*wired)
3960 		fault_type = entry->protection;
3961 
3962 	if (entry->eflags & MAP_ENTRY_NEEDS_COPY) {
3963 		/*
3964 		 * Fail if the entry was copy-on-write for a write fault.
3965 		 */
3966 		if (fault_type & VM_PROT_WRITE)
3967 			return (KERN_FAILURE);
3968 		/*
3969 		 * We're attempting to read a copy-on-write page --
3970 		 * don't allow writes.
3971 		 */
3972 		prot &= ~VM_PROT_WRITE;
3973 	}
3974 
3975 	/*
3976 	 * Fail if an object should be created.
3977 	 */
3978 	if (entry->object.vm_object == NULL && !map->system_map)
3979 		return (KERN_FAILURE);
3980 
3981 	/*
3982 	 * Return the object/offset from this entry.  If the entry was
3983 	 * copy-on-write or empty, it has been fixed up.
3984 	 */
3985 	*pindex = OFF_TO_IDX((vaddr - entry->start) + entry->offset);
3986 	*object = entry->object.vm_object;
3987 
3988 	*out_prot = prot;
3989 	return (KERN_SUCCESS);
3990 }
3991 
3992 /*
3993  *	vm_map_lookup_done:
3994  *
3995  *	Releases locks acquired by a vm_map_lookup
3996  *	(according to the handle returned by that lookup).
3997  */
3998 void
3999 vm_map_lookup_done(vm_map_t map, vm_map_entry_t entry)
4000 {
4001 	/*
4002 	 * Unlock the main-level map
4003 	 */
4004 	vm_map_unlock_read(map);
4005 }
4006 
4007 #include "opt_ddb.h"
4008 #ifdef DDB
4009 #include <sys/kernel.h>
4010 
4011 #include <ddb/ddb.h>
4012 
4013 static void
4014 vm_map_print(vm_map_t map)
4015 {
4016 	vm_map_entry_t entry;
4017 
4018 	db_iprintf("Task map %p: pmap=%p, nentries=%d, version=%u\n",
4019 	    (void *)map,
4020 	    (void *)map->pmap, map->nentries, map->timestamp);
4021 
4022 	db_indent += 2;
4023 	for (entry = map->header.next; entry != &map->header;
4024 	    entry = entry->next) {
4025 		db_iprintf("map entry %p: start=%p, end=%p\n",
4026 		    (void *)entry, (void *)entry->start, (void *)entry->end);
4027 		{
4028 			static char *inheritance_name[4] =
4029 			{"share", "copy", "none", "donate_copy"};
4030 
4031 			db_iprintf(" prot=%x/%x/%s",
4032 			    entry->protection,
4033 			    entry->max_protection,
4034 			    inheritance_name[(int)(unsigned char)entry->inheritance]);
4035 			if (entry->wired_count != 0)
4036 				db_printf(", wired");
4037 		}
4038 		if (entry->eflags & MAP_ENTRY_IS_SUB_MAP) {
4039 			db_printf(", share=%p, offset=0x%jx\n",
4040 			    (void *)entry->object.sub_map,
4041 			    (uintmax_t)entry->offset);
4042 			if ((entry->prev == &map->header) ||
4043 			    (entry->prev->object.sub_map !=
4044 				entry->object.sub_map)) {
4045 				db_indent += 2;
4046 				vm_map_print((vm_map_t)entry->object.sub_map);
4047 				db_indent -= 2;
4048 			}
4049 		} else {
4050 			if (entry->cred != NULL)
4051 				db_printf(", ruid %d", entry->cred->cr_ruid);
4052 			db_printf(", object=%p, offset=0x%jx",
4053 			    (void *)entry->object.vm_object,
4054 			    (uintmax_t)entry->offset);
4055 			if (entry->object.vm_object && entry->object.vm_object->cred)
4056 				db_printf(", obj ruid %d charge %jx",
4057 				    entry->object.vm_object->cred->cr_ruid,
4058 				    (uintmax_t)entry->object.vm_object->charge);
4059 			if (entry->eflags & MAP_ENTRY_COW)
4060 				db_printf(", copy (%s)",
4061 				    (entry->eflags & MAP_ENTRY_NEEDS_COPY) ? "needed" : "done");
4062 			db_printf("\n");
4063 
4064 			if ((entry->prev == &map->header) ||
4065 			    (entry->prev->object.vm_object !=
4066 				entry->object.vm_object)) {
4067 				db_indent += 2;
4068 				vm_object_print((db_expr_t)(intptr_t)
4069 						entry->object.vm_object,
4070 						1, 0, (char *)0);
4071 				db_indent -= 2;
4072 			}
4073 		}
4074 	}
4075 	db_indent -= 2;
4076 }
4077 
4078 DB_SHOW_COMMAND(map, map)
4079 {
4080 
4081 	if (!have_addr) {
4082 		db_printf("usage: show map <addr>\n");
4083 		return;
4084 	}
4085 	vm_map_print((vm_map_t)addr);
4086 }
4087 
4088 DB_SHOW_COMMAND(procvm, procvm)
4089 {
4090 	struct proc *p;
4091 
4092 	if (have_addr) {
4093 		p = (struct proc *) addr;
4094 	} else {
4095 		p = curproc;
4096 	}
4097 
4098 	db_printf("p = %p, vmspace = %p, map = %p, pmap = %p\n",
4099 	    (void *)p, (void *)p->p_vmspace, (void *)&p->p_vmspace->vm_map,
4100 	    (void *)vmspace_pmap(p->p_vmspace));
4101 
4102 	vm_map_print((vm_map_t)&p->p_vmspace->vm_map);
4103 }
4104 
4105 #endif /* DDB */
4106