xref: /freebsd/sys/vm/vm_map.c (revision 56b17de1e8360fe131d425de20b5e75ff3ea897c)
1 /*-
2  * SPDX-License-Identifier: (BSD-3-Clause AND MIT-CMU)
3  *
4  * Copyright (c) 1991, 1993
5  *	The Regents of the University of California.  All rights reserved.
6  *
7  * This code is derived from software contributed to Berkeley by
8  * The Mach Operating System project at Carnegie-Mellon University.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 3. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
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/param.h>
66 #include <sys/systm.h>
67 #include <sys/elf.h>
68 #include <sys/kernel.h>
69 #include <sys/ktr.h>
70 #include <sys/lock.h>
71 #include <sys/mutex.h>
72 #include <sys/proc.h>
73 #include <sys/vmmeter.h>
74 #include <sys/mman.h>
75 #include <sys/vnode.h>
76 #include <sys/racct.h>
77 #include <sys/resourcevar.h>
78 #include <sys/rwlock.h>
79 #include <sys/file.h>
80 #include <sys/sysctl.h>
81 #include <sys/sysent.h>
82 #include <sys/shm.h>
83 
84 #include <vm/vm.h>
85 #include <vm/vm_param.h>
86 #include <vm/pmap.h>
87 #include <vm/vm_map.h>
88 #include <vm/vm_page.h>
89 #include <vm/vm_pageout.h>
90 #include <vm/vm_object.h>
91 #include <vm/vm_pager.h>
92 #include <vm/vm_kern.h>
93 #include <vm/vm_extern.h>
94 #include <vm/vnode_pager.h>
95 #include <vm/swap_pager.h>
96 #include <vm/uma.h>
97 
98 /*
99  *	Virtual memory maps provide for the mapping, protection,
100  *	and sharing of virtual memory objects.  In addition,
101  *	this module provides for an efficient virtual copy of
102  *	memory from one map to another.
103  *
104  *	Synchronization is required prior to most operations.
105  *
106  *	Maps consist of an ordered doubly-linked list of simple
107  *	entries; a self-adjusting binary search tree of these
108  *	entries is used to speed up lookups.
109  *
110  *	Since portions of maps are specified by start/end addresses,
111  *	which may not align with existing map entries, all
112  *	routines merely "clip" entries to these start/end values.
113  *	[That is, an entry is split into two, bordering at a
114  *	start or end value.]  Note that these clippings may not
115  *	always be necessary (as the two resulting entries are then
116  *	not changed); however, the clipping is done for convenience.
117  *
118  *	As mentioned above, virtual copy operations are performed
119  *	by copying VM object references from one map to
120  *	another, and then marking both regions as copy-on-write.
121  */
122 
123 static struct mtx map_sleep_mtx;
124 static uma_zone_t mapentzone;
125 static uma_zone_t kmapentzone;
126 static uma_zone_t vmspace_zone;
127 static int vmspace_zinit(void *mem, int size, int flags);
128 static void _vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min,
129     vm_offset_t max);
130 static void vm_map_entry_deallocate(vm_map_entry_t entry, boolean_t system_map);
131 static void vm_map_entry_dispose(vm_map_t map, vm_map_entry_t entry);
132 static void vm_map_entry_unwire(vm_map_t map, vm_map_entry_t entry);
133 static int vm_map_growstack(vm_map_t map, vm_offset_t addr,
134     vm_map_entry_t gap_entry);
135 static void vm_map_pmap_enter(vm_map_t map, vm_offset_t addr, vm_prot_t prot,
136     vm_object_t object, vm_pindex_t pindex, vm_size_t size, int flags);
137 #ifdef INVARIANTS
138 static void vmspace_zdtor(void *mem, int size, void *arg);
139 #endif
140 static int vm_map_stack_locked(vm_map_t map, vm_offset_t addrbos,
141     vm_size_t max_ssize, vm_size_t growsize, vm_prot_t prot, vm_prot_t max,
142     int cow);
143 static void vm_map_wire_entry_failure(vm_map_t map, vm_map_entry_t entry,
144     vm_offset_t failed_addr);
145 
146 #define	CONTAINS_BITS(set, bits)	((~(set) & (bits)) == 0)
147 
148 #define	ENTRY_CHARGED(e) ((e)->cred != NULL || \
149     ((e)->object.vm_object != NULL && (e)->object.vm_object->cred != NULL && \
150      !((e)->eflags & MAP_ENTRY_NEEDS_COPY)))
151 
152 /*
153  * PROC_VMSPACE_{UN,}LOCK() can be a noop as long as vmspaces are type
154  * stable.
155  */
156 #define PROC_VMSPACE_LOCK(p) do { } while (0)
157 #define PROC_VMSPACE_UNLOCK(p) do { } while (0)
158 
159 /*
160  *	VM_MAP_RANGE_CHECK:	[ internal use only ]
161  *
162  *	Asserts that the starting and ending region
163  *	addresses fall within the valid range of the map.
164  */
165 #define	VM_MAP_RANGE_CHECK(map, start, end)		\
166 		{					\
167 		if (start < vm_map_min(map))		\
168 			start = vm_map_min(map);	\
169 		if (end > vm_map_max(map))		\
170 			end = vm_map_max(map);		\
171 		if (start > end)			\
172 			start = end;			\
173 		}
174 
175 #ifndef UMA_USE_DMAP
176 
177 /*
178  * Allocate a new slab for kernel map entries.  The kernel map may be locked or
179  * unlocked, depending on whether the request is coming from the kernel map or a
180  * submap.  This function allocates a virtual address range directly from the
181  * kernel map instead of the kmem_* layer to avoid recursion on the kernel map
182  * lock and also to avoid triggering allocator recursion in the vmem boundary
183  * tag allocator.
184  */
185 static void *
186 kmapent_alloc(uma_zone_t zone, vm_size_t bytes, int domain, uint8_t *pflag,
187     int wait)
188 {
189 	vm_offset_t addr;
190 	int error, locked;
191 
192 	*pflag = UMA_SLAB_PRIV;
193 
194 	if (!(locked = vm_map_locked(kernel_map)))
195 		vm_map_lock(kernel_map);
196 	addr = vm_map_findspace(kernel_map, vm_map_min(kernel_map), bytes);
197 	if (addr + bytes < addr || addr + bytes > vm_map_max(kernel_map))
198 		panic("%s: kernel map is exhausted", __func__);
199 	error = vm_map_insert(kernel_map, NULL, 0, addr, addr + bytes,
200 	    VM_PROT_RW, VM_PROT_RW, MAP_NOFAULT);
201 	if (error != KERN_SUCCESS)
202 		panic("%s: vm_map_insert() failed: %d", __func__, error);
203 	if (!locked)
204 		vm_map_unlock(kernel_map);
205 	error = kmem_back_domain(domain, kernel_object, addr, bytes, M_NOWAIT |
206 	    M_USE_RESERVE | (wait & M_ZERO));
207 	if (error == KERN_SUCCESS) {
208 		return ((void *)addr);
209 	} else {
210 		if (!locked)
211 			vm_map_lock(kernel_map);
212 		vm_map_delete(kernel_map, addr, bytes);
213 		if (!locked)
214 			vm_map_unlock(kernel_map);
215 		return (NULL);
216 	}
217 }
218 
219 static void
220 kmapent_free(void *item, vm_size_t size, uint8_t pflag)
221 {
222 	vm_offset_t addr;
223 	int error __diagused;
224 
225 	if ((pflag & UMA_SLAB_PRIV) == 0)
226 		/* XXX leaked */
227 		return;
228 
229 	addr = (vm_offset_t)item;
230 	kmem_unback(kernel_object, addr, size);
231 	error = vm_map_remove(kernel_map, addr, addr + size);
232 	KASSERT(error == KERN_SUCCESS,
233 	    ("%s: vm_map_remove failed: %d", __func__, error));
234 }
235 
236 /*
237  * The worst-case upper bound on the number of kernel map entries that may be
238  * created before the zone must be replenished in _vm_map_unlock().
239  */
240 #define	KMAPENT_RESERVE		1
241 
242 #endif /* !UMD_MD_SMALL_ALLOC */
243 
244 /*
245  *	vm_map_startup:
246  *
247  *	Initialize the vm_map module.  Must be called before any other vm_map
248  *	routines.
249  *
250  *	User map and entry structures are allocated from the general purpose
251  *	memory pool.  Kernel maps are statically defined.  Kernel map entries
252  *	require special handling to avoid recursion; see the comments above
253  *	kmapent_alloc() and in vm_map_entry_create().
254  */
255 void
256 vm_map_startup(void)
257 {
258 	mtx_init(&map_sleep_mtx, "vm map sleep mutex", NULL, MTX_DEF);
259 
260 	/*
261 	 * Disable the use of per-CPU buckets: map entry allocation is
262 	 * serialized by the kernel map lock.
263 	 */
264 	kmapentzone = uma_zcreate("KMAP ENTRY", sizeof(struct vm_map_entry),
265 	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR,
266 	    UMA_ZONE_VM | UMA_ZONE_NOBUCKET);
267 #ifndef UMA_USE_DMAP
268 	/* Reserve an extra map entry for use when replenishing the reserve. */
269 	uma_zone_reserve(kmapentzone, KMAPENT_RESERVE + 1);
270 	uma_prealloc(kmapentzone, KMAPENT_RESERVE + 1);
271 	uma_zone_set_allocf(kmapentzone, kmapent_alloc);
272 	uma_zone_set_freef(kmapentzone, kmapent_free);
273 #endif
274 
275 	mapentzone = uma_zcreate("MAP ENTRY", sizeof(struct vm_map_entry),
276 	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0);
277 	vmspace_zone = uma_zcreate("VMSPACE", sizeof(struct vmspace), NULL,
278 #ifdef INVARIANTS
279 	    vmspace_zdtor,
280 #else
281 	    NULL,
282 #endif
283 	    vmspace_zinit, NULL, UMA_ALIGN_PTR, UMA_ZONE_NOFREE);
284 }
285 
286 static int
287 vmspace_zinit(void *mem, int size, int flags)
288 {
289 	struct vmspace *vm;
290 	vm_map_t map;
291 
292 	vm = (struct vmspace *)mem;
293 	map = &vm->vm_map;
294 
295 	memset(map, 0, sizeof(*map));
296 	mtx_init(&map->system_mtx, "vm map (system)", NULL,
297 	    MTX_DEF | MTX_DUPOK);
298 	sx_init(&map->lock, "vm map (user)");
299 	PMAP_LOCK_INIT(vmspace_pmap(vm));
300 	return (0);
301 }
302 
303 #ifdef INVARIANTS
304 static void
305 vmspace_zdtor(void *mem, int size, void *arg)
306 {
307 	struct vmspace *vm;
308 
309 	vm = (struct vmspace *)mem;
310 	KASSERT(vm->vm_map.nentries == 0,
311 	    ("vmspace %p nentries == %d on free", vm, vm->vm_map.nentries));
312 	KASSERT(vm->vm_map.size == 0,
313 	    ("vmspace %p size == %ju on free", vm, (uintmax_t)vm->vm_map.size));
314 }
315 #endif	/* INVARIANTS */
316 
317 /*
318  * Allocate a vmspace structure, including a vm_map and pmap,
319  * and initialize those structures.  The refcnt is set to 1.
320  */
321 struct vmspace *
322 vmspace_alloc(vm_offset_t min, vm_offset_t max, pmap_pinit_t pinit)
323 {
324 	struct vmspace *vm;
325 
326 	vm = uma_zalloc(vmspace_zone, M_WAITOK);
327 	KASSERT(vm->vm_map.pmap == NULL, ("vm_map.pmap must be NULL"));
328 	if (!pinit(vmspace_pmap(vm))) {
329 		uma_zfree(vmspace_zone, vm);
330 		return (NULL);
331 	}
332 	CTR1(KTR_VM, "vmspace_alloc: %p", vm);
333 	_vm_map_init(&vm->vm_map, vmspace_pmap(vm), min, max);
334 	refcount_init(&vm->vm_refcnt, 1);
335 	vm->vm_shm = NULL;
336 	vm->vm_swrss = 0;
337 	vm->vm_tsize = 0;
338 	vm->vm_dsize = 0;
339 	vm->vm_ssize = 0;
340 	vm->vm_taddr = 0;
341 	vm->vm_daddr = 0;
342 	vm->vm_maxsaddr = 0;
343 	return (vm);
344 }
345 
346 #ifdef RACCT
347 static void
348 vmspace_container_reset(struct proc *p)
349 {
350 
351 	PROC_LOCK(p);
352 	racct_set(p, RACCT_DATA, 0);
353 	racct_set(p, RACCT_STACK, 0);
354 	racct_set(p, RACCT_RSS, 0);
355 	racct_set(p, RACCT_MEMLOCK, 0);
356 	racct_set(p, RACCT_VMEM, 0);
357 	PROC_UNLOCK(p);
358 }
359 #endif
360 
361 static inline void
362 vmspace_dofree(struct vmspace *vm)
363 {
364 
365 	CTR1(KTR_VM, "vmspace_free: %p", vm);
366 
367 	/*
368 	 * Make sure any SysV shm is freed, it might not have been in
369 	 * exit1().
370 	 */
371 	shmexit(vm);
372 
373 	/*
374 	 * Lock the map, to wait out all other references to it.
375 	 * Delete all of the mappings and pages they hold, then call
376 	 * the pmap module to reclaim anything left.
377 	 */
378 	(void)vm_map_remove(&vm->vm_map, vm_map_min(&vm->vm_map),
379 	    vm_map_max(&vm->vm_map));
380 
381 	pmap_release(vmspace_pmap(vm));
382 	vm->vm_map.pmap = NULL;
383 	uma_zfree(vmspace_zone, vm);
384 }
385 
386 void
387 vmspace_free(struct vmspace *vm)
388 {
389 
390 	WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
391 	    "vmspace_free() called");
392 
393 	if (refcount_release(&vm->vm_refcnt))
394 		vmspace_dofree(vm);
395 }
396 
397 void
398 vmspace_exitfree(struct proc *p)
399 {
400 	struct vmspace *vm;
401 
402 	PROC_VMSPACE_LOCK(p);
403 	vm = p->p_vmspace;
404 	p->p_vmspace = NULL;
405 	PROC_VMSPACE_UNLOCK(p);
406 	KASSERT(vm == &vmspace0, ("vmspace_exitfree: wrong vmspace"));
407 	vmspace_free(vm);
408 }
409 
410 void
411 vmspace_exit(struct thread *td)
412 {
413 	struct vmspace *vm;
414 	struct proc *p;
415 	bool released;
416 
417 	p = td->td_proc;
418 	vm = p->p_vmspace;
419 
420 	/*
421 	 * Prepare to release the vmspace reference.  The thread that releases
422 	 * the last reference is responsible for tearing down the vmspace.
423 	 * However, threads not releasing the final reference must switch to the
424 	 * kernel's vmspace0 before the decrement so that the subsequent pmap
425 	 * deactivation does not modify a freed vmspace.
426 	 */
427 	refcount_acquire(&vmspace0.vm_refcnt);
428 	if (!(released = refcount_release_if_last(&vm->vm_refcnt))) {
429 		if (p->p_vmspace != &vmspace0) {
430 			PROC_VMSPACE_LOCK(p);
431 			p->p_vmspace = &vmspace0;
432 			PROC_VMSPACE_UNLOCK(p);
433 			pmap_activate(td);
434 		}
435 		released = refcount_release(&vm->vm_refcnt);
436 	}
437 	if (released) {
438 		/*
439 		 * pmap_remove_pages() expects the pmap to be active, so switch
440 		 * back first if necessary.
441 		 */
442 		if (p->p_vmspace != vm) {
443 			PROC_VMSPACE_LOCK(p);
444 			p->p_vmspace = vm;
445 			PROC_VMSPACE_UNLOCK(p);
446 			pmap_activate(td);
447 		}
448 		pmap_remove_pages(vmspace_pmap(vm));
449 		PROC_VMSPACE_LOCK(p);
450 		p->p_vmspace = &vmspace0;
451 		PROC_VMSPACE_UNLOCK(p);
452 		pmap_activate(td);
453 		vmspace_dofree(vm);
454 	}
455 #ifdef RACCT
456 	if (racct_enable)
457 		vmspace_container_reset(p);
458 #endif
459 }
460 
461 /* Acquire reference to vmspace owned by another process. */
462 
463 struct vmspace *
464 vmspace_acquire_ref(struct proc *p)
465 {
466 	struct vmspace *vm;
467 
468 	PROC_VMSPACE_LOCK(p);
469 	vm = p->p_vmspace;
470 	if (vm == NULL || !refcount_acquire_if_not_zero(&vm->vm_refcnt)) {
471 		PROC_VMSPACE_UNLOCK(p);
472 		return (NULL);
473 	}
474 	if (vm != p->p_vmspace) {
475 		PROC_VMSPACE_UNLOCK(p);
476 		vmspace_free(vm);
477 		return (NULL);
478 	}
479 	PROC_VMSPACE_UNLOCK(p);
480 	return (vm);
481 }
482 
483 /*
484  * Switch between vmspaces in an AIO kernel process.
485  *
486  * The new vmspace is either the vmspace of a user process obtained
487  * from an active AIO request or the initial vmspace of the AIO kernel
488  * process (when it is idling).  Because user processes will block to
489  * drain any active AIO requests before proceeding in exit() or
490  * execve(), the reference count for vmspaces from AIO requests can
491  * never be 0.  Similarly, AIO kernel processes hold an extra
492  * reference on their initial vmspace for the life of the process.  As
493  * a result, the 'newvm' vmspace always has a non-zero reference
494  * count.  This permits an additional reference on 'newvm' to be
495  * acquired via a simple atomic increment rather than the loop in
496  * vmspace_acquire_ref() above.
497  */
498 void
499 vmspace_switch_aio(struct vmspace *newvm)
500 {
501 	struct vmspace *oldvm;
502 
503 	/* XXX: Need some way to assert that this is an aio daemon. */
504 
505 	KASSERT(refcount_load(&newvm->vm_refcnt) > 0,
506 	    ("vmspace_switch_aio: newvm unreferenced"));
507 
508 	oldvm = curproc->p_vmspace;
509 	if (oldvm == newvm)
510 		return;
511 
512 	/*
513 	 * Point to the new address space and refer to it.
514 	 */
515 	curproc->p_vmspace = newvm;
516 	refcount_acquire(&newvm->vm_refcnt);
517 
518 	/* Activate the new mapping. */
519 	pmap_activate(curthread);
520 
521 	vmspace_free(oldvm);
522 }
523 
524 void
525 _vm_map_lock(vm_map_t map, const char *file, int line)
526 {
527 
528 	if (map->system_map)
529 		mtx_lock_flags_(&map->system_mtx, 0, file, line);
530 	else
531 		sx_xlock_(&map->lock, file, line);
532 	map->timestamp++;
533 }
534 
535 void
536 vm_map_entry_set_vnode_text(vm_map_entry_t entry, bool add)
537 {
538 	vm_object_t object;
539 	struct vnode *vp;
540 	bool vp_held;
541 
542 	if ((entry->eflags & MAP_ENTRY_VN_EXEC) == 0)
543 		return;
544 	KASSERT((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0,
545 	    ("Submap with execs"));
546 	object = entry->object.vm_object;
547 	KASSERT(object != NULL, ("No object for text, entry %p", entry));
548 	if ((object->flags & OBJ_ANON) != 0)
549 		object = object->handle;
550 	else
551 		KASSERT(object->backing_object == NULL,
552 		    ("non-anon object %p shadows", object));
553 	KASSERT(object != NULL, ("No content object for text, entry %p obj %p",
554 	    entry, entry->object.vm_object));
555 
556 	/*
557 	 * Mostly, we do not lock the backing object.  It is
558 	 * referenced by the entry we are processing, so it cannot go
559 	 * away.
560 	 */
561 	vm_pager_getvp(object, &vp, &vp_held);
562 	if (vp != NULL) {
563 		if (add) {
564 			VOP_SET_TEXT_CHECKED(vp);
565 		} else {
566 			vn_lock(vp, LK_SHARED | LK_RETRY);
567 			VOP_UNSET_TEXT_CHECKED(vp);
568 			VOP_UNLOCK(vp);
569 		}
570 		if (vp_held)
571 			vdrop(vp);
572 	}
573 }
574 
575 /*
576  * Use a different name for this vm_map_entry field when it's use
577  * is not consistent with its use as part of an ordered search tree.
578  */
579 #define defer_next right
580 
581 static void
582 vm_map_process_deferred(void)
583 {
584 	struct thread *td;
585 	vm_map_entry_t entry, next;
586 	vm_object_t object;
587 
588 	td = curthread;
589 	entry = td->td_map_def_user;
590 	td->td_map_def_user = NULL;
591 	while (entry != NULL) {
592 		next = entry->defer_next;
593 		MPASS((entry->eflags & (MAP_ENTRY_WRITECNT |
594 		    MAP_ENTRY_VN_EXEC)) != (MAP_ENTRY_WRITECNT |
595 		    MAP_ENTRY_VN_EXEC));
596 		if ((entry->eflags & MAP_ENTRY_WRITECNT) != 0) {
597 			/*
598 			 * Decrement the object's writemappings and
599 			 * possibly the vnode's v_writecount.
600 			 */
601 			KASSERT((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0,
602 			    ("Submap with writecount"));
603 			object = entry->object.vm_object;
604 			KASSERT(object != NULL, ("No object for writecount"));
605 			vm_pager_release_writecount(object, entry->start,
606 			    entry->end);
607 		}
608 		vm_map_entry_set_vnode_text(entry, false);
609 		vm_map_entry_deallocate(entry, FALSE);
610 		entry = next;
611 	}
612 }
613 
614 #ifdef INVARIANTS
615 static void
616 _vm_map_assert_locked(vm_map_t map, const char *file, int line)
617 {
618 
619 	if (map->system_map)
620 		mtx_assert_(&map->system_mtx, MA_OWNED, file, line);
621 	else
622 		sx_assert_(&map->lock, SA_XLOCKED, file, line);
623 }
624 
625 #define	VM_MAP_ASSERT_LOCKED(map) \
626     _vm_map_assert_locked(map, LOCK_FILE, LOCK_LINE)
627 
628 enum { VMMAP_CHECK_NONE, VMMAP_CHECK_UNLOCK, VMMAP_CHECK_ALL };
629 #ifdef DIAGNOSTIC
630 static int enable_vmmap_check = VMMAP_CHECK_UNLOCK;
631 #else
632 static int enable_vmmap_check = VMMAP_CHECK_NONE;
633 #endif
634 SYSCTL_INT(_debug, OID_AUTO, vmmap_check, CTLFLAG_RWTUN,
635     &enable_vmmap_check, 0, "Enable vm map consistency checking");
636 
637 static void _vm_map_assert_consistent(vm_map_t map, int check);
638 
639 #define VM_MAP_ASSERT_CONSISTENT(map) \
640     _vm_map_assert_consistent(map, VMMAP_CHECK_ALL)
641 #ifdef DIAGNOSTIC
642 #define VM_MAP_UNLOCK_CONSISTENT(map) do {				\
643 	if (map->nupdates > map->nentries) {				\
644 		_vm_map_assert_consistent(map, VMMAP_CHECK_UNLOCK);	\
645 		map->nupdates = 0;					\
646 	}								\
647 } while (0)
648 #else
649 #define VM_MAP_UNLOCK_CONSISTENT(map)
650 #endif
651 #else
652 #define	VM_MAP_ASSERT_LOCKED(map)
653 #define VM_MAP_ASSERT_CONSISTENT(map)
654 #define VM_MAP_UNLOCK_CONSISTENT(map)
655 #endif /* INVARIANTS */
656 
657 void
658 _vm_map_unlock(vm_map_t map, const char *file, int line)
659 {
660 
661 	VM_MAP_UNLOCK_CONSISTENT(map);
662 	if (map->system_map) {
663 #ifndef UMA_USE_DMAP
664 		if (map == kernel_map && (map->flags & MAP_REPLENISH) != 0) {
665 			uma_prealloc(kmapentzone, 1);
666 			map->flags &= ~MAP_REPLENISH;
667 		}
668 #endif
669 		mtx_unlock_flags_(&map->system_mtx, 0, file, line);
670 	} else {
671 		sx_xunlock_(&map->lock, file, line);
672 		vm_map_process_deferred();
673 	}
674 }
675 
676 void
677 _vm_map_lock_read(vm_map_t map, const char *file, int line)
678 {
679 
680 	if (map->system_map)
681 		mtx_lock_flags_(&map->system_mtx, 0, file, line);
682 	else
683 		sx_slock_(&map->lock, file, line);
684 }
685 
686 void
687 _vm_map_unlock_read(vm_map_t map, const char *file, int line)
688 {
689 
690 	if (map->system_map) {
691 		KASSERT((map->flags & MAP_REPLENISH) == 0,
692 		    ("%s: MAP_REPLENISH leaked", __func__));
693 		mtx_unlock_flags_(&map->system_mtx, 0, file, line);
694 	} else {
695 		sx_sunlock_(&map->lock, file, line);
696 		vm_map_process_deferred();
697 	}
698 }
699 
700 int
701 _vm_map_trylock(vm_map_t map, const char *file, int line)
702 {
703 	int error;
704 
705 	error = map->system_map ?
706 	    !mtx_trylock_flags_(&map->system_mtx, 0, file, line) :
707 	    !sx_try_xlock_(&map->lock, file, line);
708 	if (error == 0)
709 		map->timestamp++;
710 	return (error == 0);
711 }
712 
713 int
714 _vm_map_trylock_read(vm_map_t map, const char *file, int line)
715 {
716 	int error;
717 
718 	error = map->system_map ?
719 	    !mtx_trylock_flags_(&map->system_mtx, 0, file, line) :
720 	    !sx_try_slock_(&map->lock, file, line);
721 	return (error == 0);
722 }
723 
724 /*
725  *	_vm_map_lock_upgrade:	[ internal use only ]
726  *
727  *	Tries to upgrade a read (shared) lock on the specified map to a write
728  *	(exclusive) lock.  Returns the value "0" if the upgrade succeeds and a
729  *	non-zero value if the upgrade fails.  If the upgrade fails, the map is
730  *	returned without a read or write lock held.
731  *
732  *	Requires that the map be read locked.
733  */
734 int
735 _vm_map_lock_upgrade(vm_map_t map, const char *file, int line)
736 {
737 	unsigned int last_timestamp;
738 
739 	if (map->system_map) {
740 		mtx_assert_(&map->system_mtx, MA_OWNED, file, line);
741 	} else {
742 		if (!sx_try_upgrade_(&map->lock, file, line)) {
743 			last_timestamp = map->timestamp;
744 			sx_sunlock_(&map->lock, file, line);
745 			vm_map_process_deferred();
746 			/*
747 			 * If the map's timestamp does not change while the
748 			 * map is unlocked, then the upgrade succeeds.
749 			 */
750 			sx_xlock_(&map->lock, file, line);
751 			if (last_timestamp != map->timestamp) {
752 				sx_xunlock_(&map->lock, file, line);
753 				return (1);
754 			}
755 		}
756 	}
757 	map->timestamp++;
758 	return (0);
759 }
760 
761 void
762 _vm_map_lock_downgrade(vm_map_t map, const char *file, int line)
763 {
764 
765 	if (map->system_map) {
766 		KASSERT((map->flags & MAP_REPLENISH) == 0,
767 		    ("%s: MAP_REPLENISH leaked", __func__));
768 		mtx_assert_(&map->system_mtx, MA_OWNED, file, line);
769 	} else {
770 		VM_MAP_UNLOCK_CONSISTENT(map);
771 		sx_downgrade_(&map->lock, file, line);
772 	}
773 }
774 
775 /*
776  *	vm_map_locked:
777  *
778  *	Returns a non-zero value if the caller holds a write (exclusive) lock
779  *	on the specified map and the value "0" otherwise.
780  */
781 int
782 vm_map_locked(vm_map_t map)
783 {
784 
785 	if (map->system_map)
786 		return (mtx_owned(&map->system_mtx));
787 	else
788 		return (sx_xlocked(&map->lock));
789 }
790 
791 /*
792  *	_vm_map_unlock_and_wait:
793  *
794  *	Atomically releases the lock on the specified map and puts the calling
795  *	thread to sleep.  The calling thread will remain asleep until either
796  *	vm_map_wakeup() is performed on the map or the specified timeout is
797  *	exceeded.
798  *
799  *	WARNING!  This function does not perform deferred deallocations of
800  *	objects and map	entries.  Therefore, the calling thread is expected to
801  *	reacquire the map lock after reawakening and later perform an ordinary
802  *	unlock operation, such as vm_map_unlock(), before completing its
803  *	operation on the map.
804  */
805 int
806 _vm_map_unlock_and_wait(vm_map_t map, int timo, const char *file, int line)
807 {
808 
809 	VM_MAP_UNLOCK_CONSISTENT(map);
810 	mtx_lock(&map_sleep_mtx);
811 	if (map->system_map) {
812 		KASSERT((map->flags & MAP_REPLENISH) == 0,
813 		    ("%s: MAP_REPLENISH leaked", __func__));
814 		mtx_unlock_flags_(&map->system_mtx, 0, file, line);
815 	} else {
816 		sx_xunlock_(&map->lock, file, line);
817 	}
818 	return (msleep(&map->root, &map_sleep_mtx, PDROP | PVM, "vmmaps",
819 	    timo));
820 }
821 
822 /*
823  *	vm_map_wakeup:
824  *
825  *	Awaken any threads that have slept on the map using
826  *	vm_map_unlock_and_wait().
827  */
828 void
829 vm_map_wakeup(vm_map_t map)
830 {
831 
832 	/*
833 	 * Acquire and release map_sleep_mtx to prevent a wakeup()
834 	 * from being performed (and lost) between the map unlock
835 	 * and the msleep() in _vm_map_unlock_and_wait().
836 	 */
837 	mtx_lock(&map_sleep_mtx);
838 	mtx_unlock(&map_sleep_mtx);
839 	wakeup(&map->root);
840 }
841 
842 void
843 vm_map_busy(vm_map_t map)
844 {
845 
846 	VM_MAP_ASSERT_LOCKED(map);
847 	map->busy++;
848 }
849 
850 void
851 vm_map_unbusy(vm_map_t map)
852 {
853 
854 	VM_MAP_ASSERT_LOCKED(map);
855 	KASSERT(map->busy, ("vm_map_unbusy: not busy"));
856 	if (--map->busy == 0 && (map->flags & MAP_BUSY_WAKEUP)) {
857 		vm_map_modflags(map, 0, MAP_BUSY_WAKEUP);
858 		wakeup(&map->busy);
859 	}
860 }
861 
862 void
863 vm_map_wait_busy(vm_map_t map)
864 {
865 
866 	VM_MAP_ASSERT_LOCKED(map);
867 	while (map->busy) {
868 		vm_map_modflags(map, MAP_BUSY_WAKEUP, 0);
869 		if (map->system_map)
870 			msleep(&map->busy, &map->system_mtx, 0, "mbusy", 0);
871 		else
872 			sx_sleep(&map->busy, &map->lock, 0, "mbusy", 0);
873 	}
874 	map->timestamp++;
875 }
876 
877 long
878 vmspace_resident_count(struct vmspace *vmspace)
879 {
880 	return pmap_resident_count(vmspace_pmap(vmspace));
881 }
882 
883 /*
884  * Initialize an existing vm_map structure
885  * such as that in the vmspace structure.
886  */
887 static void
888 _vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min, vm_offset_t max)
889 {
890 
891 	map->header.eflags = MAP_ENTRY_HEADER;
892 	map->needs_wakeup = FALSE;
893 	map->system_map = 0;
894 	map->pmap = pmap;
895 	map->header.end = min;
896 	map->header.start = max;
897 	map->flags = 0;
898 	map->header.left = map->header.right = &map->header;
899 	map->root = NULL;
900 	map->timestamp = 0;
901 	map->busy = 0;
902 	map->anon_loc = 0;
903 #ifdef DIAGNOSTIC
904 	map->nupdates = 0;
905 #endif
906 }
907 
908 void
909 vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min, vm_offset_t max)
910 {
911 
912 	_vm_map_init(map, pmap, min, max);
913 	mtx_init(&map->system_mtx, "vm map (system)", NULL,
914 	    MTX_DEF | MTX_DUPOK);
915 	sx_init(&map->lock, "vm map (user)");
916 }
917 
918 /*
919  *	vm_map_entry_dispose:	[ internal use only ]
920  *
921  *	Inverse of vm_map_entry_create.
922  */
923 static void
924 vm_map_entry_dispose(vm_map_t map, vm_map_entry_t entry)
925 {
926 	uma_zfree(map->system_map ? kmapentzone : mapentzone, entry);
927 }
928 
929 /*
930  *	vm_map_entry_create:	[ internal use only ]
931  *
932  *	Allocates a VM map entry for insertion.
933  *	No entry fields are filled in.
934  */
935 static vm_map_entry_t
936 vm_map_entry_create(vm_map_t map)
937 {
938 	vm_map_entry_t new_entry;
939 
940 #ifndef UMA_USE_DMAP
941 	if (map == kernel_map) {
942 		VM_MAP_ASSERT_LOCKED(map);
943 
944 		/*
945 		 * A new slab of kernel map entries cannot be allocated at this
946 		 * point because the kernel map has not yet been updated to
947 		 * reflect the caller's request.  Therefore, we allocate a new
948 		 * map entry, dipping into the reserve if necessary, and set a
949 		 * flag indicating that the reserve must be replenished before
950 		 * the map is unlocked.
951 		 */
952 		new_entry = uma_zalloc(kmapentzone, M_NOWAIT | M_NOVM);
953 		if (new_entry == NULL) {
954 			new_entry = uma_zalloc(kmapentzone,
955 			    M_NOWAIT | M_NOVM | M_USE_RESERVE);
956 			kernel_map->flags |= MAP_REPLENISH;
957 		}
958 	} else
959 #endif
960 	if (map->system_map) {
961 		new_entry = uma_zalloc(kmapentzone, M_NOWAIT);
962 	} else {
963 		new_entry = uma_zalloc(mapentzone, M_WAITOK);
964 	}
965 	KASSERT(new_entry != NULL,
966 	    ("vm_map_entry_create: kernel resources exhausted"));
967 	return (new_entry);
968 }
969 
970 /*
971  *	vm_map_entry_set_behavior:
972  *
973  *	Set the expected access behavior, either normal, random, or
974  *	sequential.
975  */
976 static inline void
977 vm_map_entry_set_behavior(vm_map_entry_t entry, u_char behavior)
978 {
979 	entry->eflags = (entry->eflags & ~MAP_ENTRY_BEHAV_MASK) |
980 	    (behavior & MAP_ENTRY_BEHAV_MASK);
981 }
982 
983 /*
984  *	vm_map_entry_max_free_{left,right}:
985  *
986  *	Compute the size of the largest free gap between two entries,
987  *	one the root of a tree and the other the ancestor of that root
988  *	that is the least or greatest ancestor found on the search path.
989  */
990 static inline vm_size_t
991 vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor)
992 {
993 
994 	return (root->left != left_ancestor ?
995 	    root->left->max_free : root->start - left_ancestor->end);
996 }
997 
998 static inline vm_size_t
999 vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)
1000 {
1001 
1002 	return (root->right != right_ancestor ?
1003 	    root->right->max_free : right_ancestor->start - root->end);
1004 }
1005 
1006 /*
1007  *	vm_map_entry_{pred,succ}:
1008  *
1009  *	Find the {predecessor, successor} of the entry by taking one step
1010  *	in the appropriate direction and backtracking as much as necessary.
1011  *	vm_map_entry_succ is defined in vm_map.h.
1012  */
1013 static inline vm_map_entry_t
1014 vm_map_entry_pred(vm_map_entry_t entry)
1015 {
1016 	vm_map_entry_t prior;
1017 
1018 	prior = entry->left;
1019 	if (prior->right->start < entry->start) {
1020 		do
1021 			prior = prior->right;
1022 		while (prior->right != entry);
1023 	}
1024 	return (prior);
1025 }
1026 
1027 static inline vm_size_t
1028 vm_size_max(vm_size_t a, vm_size_t b)
1029 {
1030 
1031 	return (a > b ? a : b);
1032 }
1033 
1034 #define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do {		\
1035 	vm_map_entry_t z;						\
1036 	vm_size_t max_free;						\
1037 									\
1038 	/*								\
1039 	 * Infer root->right->max_free == root->max_free when		\
1040 	 * y->max_free < root->max_free || root->max_free == 0.		\
1041 	 * Otherwise, look right to find it.				\
1042 	 */								\
1043 	y = root->left;							\
1044 	max_free = root->max_free;					\
1045 	KASSERT(max_free == vm_size_max(				\
1046 	    vm_map_entry_max_free_left(root, llist),			\
1047 	    vm_map_entry_max_free_right(root, rlist)),			\
1048 	    ("%s: max_free invariant fails", __func__));		\
1049 	if (max_free - 1 < vm_map_entry_max_free_left(root, llist))	\
1050 		max_free = vm_map_entry_max_free_right(root, rlist);	\
1051 	if (y != llist && (test)) {					\
1052 		/* Rotate right and make y root. */			\
1053 		z = y->right;						\
1054 		if (z != root) {					\
1055 			root->left = z;					\
1056 			y->right = root;				\
1057 			if (max_free < y->max_free)			\
1058 			    root->max_free = max_free =			\
1059 			    vm_size_max(max_free, z->max_free);		\
1060 		} else if (max_free < y->max_free)			\
1061 			root->max_free = max_free =			\
1062 			    vm_size_max(max_free, root->start - y->end);\
1063 		root = y;						\
1064 		y = root->left;						\
1065 	}								\
1066 	/* Copy right->max_free.  Put root on rlist. */			\
1067 	root->max_free = max_free;					\
1068 	KASSERT(max_free == vm_map_entry_max_free_right(root, rlist),	\
1069 	    ("%s: max_free not copied from right", __func__));		\
1070 	root->left = rlist;						\
1071 	rlist = root;							\
1072 	root = y != llist ? y : NULL;					\
1073 } while (0)
1074 
1075 #define SPLAY_RIGHT_STEP(root, y, llist, rlist, test) do {		\
1076 	vm_map_entry_t z;						\
1077 	vm_size_t max_free;						\
1078 									\
1079 	/*								\
1080 	 * Infer root->left->max_free == root->max_free when		\
1081 	 * y->max_free < root->max_free || root->max_free == 0.		\
1082 	 * Otherwise, look left to find it.				\
1083 	 */								\
1084 	y = root->right;						\
1085 	max_free = root->max_free;					\
1086 	KASSERT(max_free == vm_size_max(				\
1087 	    vm_map_entry_max_free_left(root, llist),			\
1088 	    vm_map_entry_max_free_right(root, rlist)),			\
1089 	    ("%s: max_free invariant fails", __func__));		\
1090 	if (max_free - 1 < vm_map_entry_max_free_right(root, rlist))	\
1091 		max_free = vm_map_entry_max_free_left(root, llist);	\
1092 	if (y != rlist && (test)) {					\
1093 		/* Rotate left and make y root. */			\
1094 		z = y->left;						\
1095 		if (z != root) {					\
1096 			root->right = z;				\
1097 			y->left = root;					\
1098 			if (max_free < y->max_free)			\
1099 			    root->max_free = max_free =			\
1100 			    vm_size_max(max_free, z->max_free);		\
1101 		} else if (max_free < y->max_free)			\
1102 			root->max_free = max_free =			\
1103 			    vm_size_max(max_free, y->start - root->end);\
1104 		root = y;						\
1105 		y = root->right;					\
1106 	}								\
1107 	/* Copy left->max_free.  Put root on llist. */			\
1108 	root->max_free = max_free;					\
1109 	KASSERT(max_free == vm_map_entry_max_free_left(root, llist),	\
1110 	    ("%s: max_free not copied from left", __func__));		\
1111 	root->right = llist;						\
1112 	llist = root;							\
1113 	root = y != rlist ? y : NULL;					\
1114 } while (0)
1115 
1116 /*
1117  * Walk down the tree until we find addr or a gap where addr would go, breaking
1118  * off left and right subtrees of nodes less than, or greater than addr.  Treat
1119  * subtrees with root->max_free < length as empty trees.  llist and rlist are
1120  * the two sides in reverse order (bottom-up), with llist linked by the right
1121  * pointer and rlist linked by the left pointer in the vm_map_entry, and both
1122  * lists terminated by &map->header.  This function, and the subsequent call to
1123  * vm_map_splay_merge_{left,right,pred,succ}, rely on the start and end address
1124  * values in &map->header.
1125  */
1126 static __always_inline vm_map_entry_t
1127 vm_map_splay_split(vm_map_t map, vm_offset_t addr, vm_size_t length,
1128     vm_map_entry_t *llist, vm_map_entry_t *rlist)
1129 {
1130 	vm_map_entry_t left, right, root, y;
1131 
1132 	left = right = &map->header;
1133 	root = map->root;
1134 	while (root != NULL && root->max_free >= length) {
1135 		KASSERT(left->end <= root->start &&
1136 		    root->end <= right->start,
1137 		    ("%s: root not within tree bounds", __func__));
1138 		if (addr < root->start) {
1139 			SPLAY_LEFT_STEP(root, y, left, right,
1140 			    y->max_free >= length && addr < y->start);
1141 		} else if (addr >= root->end) {
1142 			SPLAY_RIGHT_STEP(root, y, left, right,
1143 			    y->max_free >= length && addr >= y->end);
1144 		} else
1145 			break;
1146 	}
1147 	*llist = left;
1148 	*rlist = right;
1149 	return (root);
1150 }
1151 
1152 static __always_inline void
1153 vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *rlist)
1154 {
1155 	vm_map_entry_t hi, right, y;
1156 
1157 	right = *rlist;
1158 	hi = root->right == right ? NULL : root->right;
1159 	if (hi == NULL)
1160 		return;
1161 	do
1162 		SPLAY_LEFT_STEP(hi, y, root, right, true);
1163 	while (hi != NULL);
1164 	*rlist = right;
1165 }
1166 
1167 static __always_inline void
1168 vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *llist)
1169 {
1170 	vm_map_entry_t left, lo, y;
1171 
1172 	left = *llist;
1173 	lo = root->left == left ? NULL : root->left;
1174 	if (lo == NULL)
1175 		return;
1176 	do
1177 		SPLAY_RIGHT_STEP(lo, y, left, root, true);
1178 	while (lo != NULL);
1179 	*llist = left;
1180 }
1181 
1182 static inline void
1183 vm_map_entry_swap(vm_map_entry_t *a, vm_map_entry_t *b)
1184 {
1185 	vm_map_entry_t tmp;
1186 
1187 	tmp = *b;
1188 	*b = *a;
1189 	*a = tmp;
1190 }
1191 
1192 /*
1193  * Walk back up the two spines, flip the pointers and set max_free.  The
1194  * subtrees of the root go at the bottom of llist and rlist.
1195  */
1196 static vm_size_t
1197 vm_map_splay_merge_left_walk(vm_map_entry_t header, vm_map_entry_t root,
1198     vm_map_entry_t tail, vm_size_t max_free, vm_map_entry_t llist)
1199 {
1200 	do {
1201 		/*
1202 		 * The max_free values of the children of llist are in
1203 		 * llist->max_free and max_free.  Update with the
1204 		 * max value.
1205 		 */
1206 		llist->max_free = max_free =
1207 		    vm_size_max(llist->max_free, max_free);
1208 		vm_map_entry_swap(&llist->right, &tail);
1209 		vm_map_entry_swap(&tail, &llist);
1210 	} while (llist != header);
1211 	root->left = tail;
1212 	return (max_free);
1213 }
1214 
1215 /*
1216  * When llist is known to be the predecessor of root.
1217  */
1218 static inline vm_size_t
1219 vm_map_splay_merge_pred(vm_map_entry_t header, vm_map_entry_t root,
1220     vm_map_entry_t llist)
1221 {
1222 	vm_size_t max_free;
1223 
1224 	max_free = root->start - llist->end;
1225 	if (llist != header) {
1226 		max_free = vm_map_splay_merge_left_walk(header, root,
1227 		    root, max_free, llist);
1228 	} else {
1229 		root->left = header;
1230 		header->right = root;
1231 	}
1232 	return (max_free);
1233 }
1234 
1235 /*
1236  * When llist may or may not be the predecessor of root.
1237  */
1238 static inline vm_size_t
1239 vm_map_splay_merge_left(vm_map_entry_t header, vm_map_entry_t root,
1240     vm_map_entry_t llist)
1241 {
1242 	vm_size_t max_free;
1243 
1244 	max_free = vm_map_entry_max_free_left(root, llist);
1245 	if (llist != header) {
1246 		max_free = vm_map_splay_merge_left_walk(header, root,
1247 		    root->left == llist ? root : root->left,
1248 		    max_free, llist);
1249 	}
1250 	return (max_free);
1251 }
1252 
1253 static vm_size_t
1254 vm_map_splay_merge_right_walk(vm_map_entry_t header, vm_map_entry_t root,
1255     vm_map_entry_t tail, vm_size_t max_free, vm_map_entry_t rlist)
1256 {
1257 	do {
1258 		/*
1259 		 * The max_free values of the children of rlist are in
1260 		 * rlist->max_free and max_free.  Update with the
1261 		 * max value.
1262 		 */
1263 		rlist->max_free = max_free =
1264 		    vm_size_max(rlist->max_free, max_free);
1265 		vm_map_entry_swap(&rlist->left, &tail);
1266 		vm_map_entry_swap(&tail, &rlist);
1267 	} while (rlist != header);
1268 	root->right = tail;
1269 	return (max_free);
1270 }
1271 
1272 /*
1273  * When rlist is known to be the succecessor of root.
1274  */
1275 static inline vm_size_t
1276 vm_map_splay_merge_succ(vm_map_entry_t header, vm_map_entry_t root,
1277     vm_map_entry_t rlist)
1278 {
1279 	vm_size_t max_free;
1280 
1281 	max_free = rlist->start - root->end;
1282 	if (rlist != header) {
1283 		max_free = vm_map_splay_merge_right_walk(header, root,
1284 		    root, max_free, rlist);
1285 	} else {
1286 		root->right = header;
1287 		header->left = root;
1288 	}
1289 	return (max_free);
1290 }
1291 
1292 /*
1293  * When rlist may or may not be the succecessor of root.
1294  */
1295 static inline vm_size_t
1296 vm_map_splay_merge_right(vm_map_entry_t header, vm_map_entry_t root,
1297     vm_map_entry_t rlist)
1298 {
1299 	vm_size_t max_free;
1300 
1301 	max_free = vm_map_entry_max_free_right(root, rlist);
1302 	if (rlist != header) {
1303 		max_free = vm_map_splay_merge_right_walk(header, root,
1304 		    root->right == rlist ? root : root->right,
1305 		    max_free, rlist);
1306 	}
1307 	return (max_free);
1308 }
1309 
1310 /*
1311  *	vm_map_splay:
1312  *
1313  *	The Sleator and Tarjan top-down splay algorithm with the
1314  *	following variation.  Max_free must be computed bottom-up, so
1315  *	on the downward pass, maintain the left and right spines in
1316  *	reverse order.  Then, make a second pass up each side to fix
1317  *	the pointers and compute max_free.  The time bound is O(log n)
1318  *	amortized.
1319  *
1320  *	The tree is threaded, which means that there are no null pointers.
1321  *	When a node has no left child, its left pointer points to its
1322  *	predecessor, which the last ancestor on the search path from the root
1323  *	where the search branched right.  Likewise, when a node has no right
1324  *	child, its right pointer points to its successor.  The map header node
1325  *	is the predecessor of the first map entry, and the successor of the
1326  *	last.
1327  *
1328  *	The new root is the vm_map_entry containing "addr", or else an
1329  *	adjacent entry (lower if possible) if addr is not in the tree.
1330  *
1331  *	The map must be locked, and leaves it so.
1332  *
1333  *	Returns: the new root.
1334  */
1335 static vm_map_entry_t
1336 vm_map_splay(vm_map_t map, vm_offset_t addr)
1337 {
1338 	vm_map_entry_t header, llist, rlist, root;
1339 	vm_size_t max_free_left, max_free_right;
1340 
1341 	header = &map->header;
1342 	root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
1343 	if (root != NULL) {
1344 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1345 		max_free_right = vm_map_splay_merge_right(header, root, rlist);
1346 	} else if (llist != header) {
1347 		/*
1348 		 * Recover the greatest node in the left
1349 		 * subtree and make it the root.
1350 		 */
1351 		root = llist;
1352 		llist = root->right;
1353 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1354 		max_free_right = vm_map_splay_merge_succ(header, root, rlist);
1355 	} else if (rlist != header) {
1356 		/*
1357 		 * Recover the least node in the right
1358 		 * subtree and make it the root.
1359 		 */
1360 		root = rlist;
1361 		rlist = root->left;
1362 		max_free_left = vm_map_splay_merge_pred(header, root, llist);
1363 		max_free_right = vm_map_splay_merge_right(header, root, rlist);
1364 	} else {
1365 		/* There is no root. */
1366 		return (NULL);
1367 	}
1368 	root->max_free = vm_size_max(max_free_left, max_free_right);
1369 	map->root = root;
1370 	VM_MAP_ASSERT_CONSISTENT(map);
1371 	return (root);
1372 }
1373 
1374 /*
1375  *	vm_map_entry_{un,}link:
1376  *
1377  *	Insert/remove entries from maps.  On linking, if new entry clips
1378  *	existing entry, trim existing entry to avoid overlap, and manage
1379  *	offsets.  On unlinking, merge disappearing entry with neighbor, if
1380  *	called for, and manage offsets.  Callers should not modify fields in
1381  *	entries already mapped.
1382  */
1383 static void
1384 vm_map_entry_link(vm_map_t map, vm_map_entry_t entry)
1385 {
1386 	vm_map_entry_t header, llist, rlist, root;
1387 	vm_size_t max_free_left, max_free_right;
1388 
1389 	CTR3(KTR_VM,
1390 	    "vm_map_entry_link: map %p, nentries %d, entry %p", map,
1391 	    map->nentries, entry);
1392 	VM_MAP_ASSERT_LOCKED(map);
1393 	map->nentries++;
1394 	header = &map->header;
1395 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1396 	if (root == NULL) {
1397 		/*
1398 		 * The new entry does not overlap any existing entry in the
1399 		 * map, so it becomes the new root of the map tree.
1400 		 */
1401 		max_free_left = vm_map_splay_merge_pred(header, entry, llist);
1402 		max_free_right = vm_map_splay_merge_succ(header, entry, rlist);
1403 	} else if (entry->start == root->start) {
1404 		/*
1405 		 * The new entry is a clone of root, with only the end field
1406 		 * changed.  The root entry will be shrunk to abut the new
1407 		 * entry, and will be the right child of the new root entry in
1408 		 * the modified map.
1409 		 */
1410 		KASSERT(entry->end < root->end,
1411 		    ("%s: clip_start not within entry", __func__));
1412 		vm_map_splay_findprev(root, &llist);
1413 		if ((root->eflags & (MAP_ENTRY_STACK_GAP_DN |
1414 		    MAP_ENTRY_STACK_GAP_UP)) == 0)
1415 			root->offset += entry->end - root->start;
1416 		root->start = entry->end;
1417 		max_free_left = vm_map_splay_merge_pred(header, entry, llist);
1418 		max_free_right = root->max_free = vm_size_max(
1419 		    vm_map_splay_merge_pred(entry, root, entry),
1420 		    vm_map_splay_merge_right(header, root, rlist));
1421 	} else {
1422 		/*
1423 		 * The new entry is a clone of root, with only the start field
1424 		 * changed.  The root entry will be shrunk to abut the new
1425 		 * entry, and will be the left child of the new root entry in
1426 		 * the modified map.
1427 		 */
1428 		KASSERT(entry->end == root->end,
1429 		    ("%s: clip_start not within entry", __func__));
1430 		vm_map_splay_findnext(root, &rlist);
1431 		if ((entry->eflags & (MAP_ENTRY_STACK_GAP_DN |
1432 		    MAP_ENTRY_STACK_GAP_UP)) == 0)
1433 			entry->offset += entry->start - root->start;
1434 		root->end = entry->start;
1435 		max_free_left = root->max_free = vm_size_max(
1436 		    vm_map_splay_merge_left(header, root, llist),
1437 		    vm_map_splay_merge_succ(entry, root, entry));
1438 		max_free_right = vm_map_splay_merge_succ(header, entry, rlist);
1439 	}
1440 	entry->max_free = vm_size_max(max_free_left, max_free_right);
1441 	map->root = entry;
1442 	VM_MAP_ASSERT_CONSISTENT(map);
1443 }
1444 
1445 enum unlink_merge_type {
1446 	UNLINK_MERGE_NONE,
1447 	UNLINK_MERGE_NEXT
1448 };
1449 
1450 static void
1451 vm_map_entry_unlink(vm_map_t map, vm_map_entry_t entry,
1452     enum unlink_merge_type op)
1453 {
1454 	vm_map_entry_t header, llist, rlist, root;
1455 	vm_size_t max_free_left, max_free_right;
1456 
1457 	VM_MAP_ASSERT_LOCKED(map);
1458 	header = &map->header;
1459 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1460 	KASSERT(root != NULL,
1461 	    ("vm_map_entry_unlink: unlink object not mapped"));
1462 
1463 	vm_map_splay_findprev(root, &llist);
1464 	vm_map_splay_findnext(root, &rlist);
1465 	if (op == UNLINK_MERGE_NEXT) {
1466 		rlist->start = root->start;
1467 		MPASS((rlist->eflags & (MAP_ENTRY_STACK_GAP_DN |
1468 		    MAP_ENTRY_STACK_GAP_UP)) == 0);
1469 		rlist->offset = root->offset;
1470 	}
1471 	if (llist != header) {
1472 		root = llist;
1473 		llist = root->right;
1474 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1475 		max_free_right = vm_map_splay_merge_succ(header, root, rlist);
1476 	} else if (rlist != header) {
1477 		root = rlist;
1478 		rlist = root->left;
1479 		max_free_left = vm_map_splay_merge_pred(header, root, llist);
1480 		max_free_right = vm_map_splay_merge_right(header, root, rlist);
1481 	} else {
1482 		header->left = header->right = header;
1483 		root = NULL;
1484 	}
1485 	if (root != NULL)
1486 		root->max_free = vm_size_max(max_free_left, max_free_right);
1487 	map->root = root;
1488 	VM_MAP_ASSERT_CONSISTENT(map);
1489 	map->nentries--;
1490 	CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
1491 	    map->nentries, entry);
1492 }
1493 
1494 /*
1495  *	vm_map_entry_resize:
1496  *
1497  *	Resize a vm_map_entry, recompute the amount of free space that
1498  *	follows it and propagate that value up the tree.
1499  *
1500  *	The map must be locked, and leaves it so.
1501  */
1502 static void
1503 vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry, vm_size_t grow_amount)
1504 {
1505 	vm_map_entry_t header, llist, rlist, root;
1506 
1507 	VM_MAP_ASSERT_LOCKED(map);
1508 	header = &map->header;
1509 	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1510 	KASSERT(root != NULL, ("%s: resize object not mapped", __func__));
1511 	vm_map_splay_findnext(root, &rlist);
1512 	entry->end += grow_amount;
1513 	root->max_free = vm_size_max(
1514 	    vm_map_splay_merge_left(header, root, llist),
1515 	    vm_map_splay_merge_succ(header, root, rlist));
1516 	map->root = root;
1517 	VM_MAP_ASSERT_CONSISTENT(map);
1518 	CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p",
1519 	    __func__, map, map->nentries, entry);
1520 }
1521 
1522 /*
1523  *	vm_map_lookup_entry:	[ internal use only ]
1524  *
1525  *	Finds the map entry containing (or
1526  *	immediately preceding) the specified address
1527  *	in the given map; the entry is returned
1528  *	in the "entry" parameter.  The boolean
1529  *	result indicates whether the address is
1530  *	actually contained in the map.
1531  */
1532 boolean_t
1533 vm_map_lookup_entry(
1534 	vm_map_t map,
1535 	vm_offset_t address,
1536 	vm_map_entry_t *entry)	/* OUT */
1537 {
1538 	vm_map_entry_t cur, header, lbound, ubound;
1539 	boolean_t locked;
1540 
1541 	/*
1542 	 * If the map is empty, then the map entry immediately preceding
1543 	 * "address" is the map's header.
1544 	 */
1545 	header = &map->header;
1546 	cur = map->root;
1547 	if (cur == NULL) {
1548 		*entry = header;
1549 		return (FALSE);
1550 	}
1551 	if (address >= cur->start && cur->end > address) {
1552 		*entry = cur;
1553 		return (TRUE);
1554 	}
1555 	if ((locked = vm_map_locked(map)) ||
1556 	    sx_try_upgrade(&map->lock)) {
1557 		/*
1558 		 * Splay requires a write lock on the map.  However, it only
1559 		 * restructures the binary search tree; it does not otherwise
1560 		 * change the map.  Thus, the map's timestamp need not change
1561 		 * on a temporary upgrade.
1562 		 */
1563 		cur = vm_map_splay(map, address);
1564 		if (!locked) {
1565 			VM_MAP_UNLOCK_CONSISTENT(map);
1566 			sx_downgrade(&map->lock);
1567 		}
1568 
1569 		/*
1570 		 * If "address" is contained within a map entry, the new root
1571 		 * is that map entry.  Otherwise, the new root is a map entry
1572 		 * immediately before or after "address".
1573 		 */
1574 		if (address < cur->start) {
1575 			*entry = header;
1576 			return (FALSE);
1577 		}
1578 		*entry = cur;
1579 		return (address < cur->end);
1580 	}
1581 	/*
1582 	 * Since the map is only locked for read access, perform a
1583 	 * standard binary search tree lookup for "address".
1584 	 */
1585 	lbound = ubound = header;
1586 	for (;;) {
1587 		if (address < cur->start) {
1588 			ubound = cur;
1589 			cur = cur->left;
1590 			if (cur == lbound)
1591 				break;
1592 		} else if (cur->end <= address) {
1593 			lbound = cur;
1594 			cur = cur->right;
1595 			if (cur == ubound)
1596 				break;
1597 		} else {
1598 			*entry = cur;
1599 			return (TRUE);
1600 		}
1601 	}
1602 	*entry = lbound;
1603 	return (FALSE);
1604 }
1605 
1606 /*
1607  * vm_map_insert1() is identical to vm_map_insert() except that it
1608  * returns the newly inserted map entry in '*res'.  In case the new
1609  * entry is coalesced with a neighbor or an existing entry was
1610  * resized, that entry is returned.  In any case, the returned entry
1611  * covers the specified address range.
1612  */
1613 static int
1614 vm_map_insert1(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
1615     vm_offset_t start, vm_offset_t end, vm_prot_t prot, vm_prot_t max, int cow,
1616     vm_map_entry_t *res)
1617 {
1618 	vm_map_entry_t new_entry, next_entry, prev_entry;
1619 	struct ucred *cred;
1620 	vm_eflags_t protoeflags;
1621 	vm_inherit_t inheritance;
1622 	u_long bdry;
1623 	u_int bidx;
1624 
1625 	VM_MAP_ASSERT_LOCKED(map);
1626 	KASSERT(object != kernel_object ||
1627 	    (cow & MAP_COPY_ON_WRITE) == 0,
1628 	    ("vm_map_insert: kernel object and COW"));
1629 	KASSERT(object == NULL || (cow & MAP_NOFAULT) == 0 ||
1630 	    (cow & MAP_SPLIT_BOUNDARY_MASK) != 0,
1631 	    ("vm_map_insert: paradoxical MAP_NOFAULT request, obj %p cow %#x",
1632 	    object, cow));
1633 	KASSERT((prot & ~max) == 0,
1634 	    ("prot %#x is not subset of max_prot %#x", prot, max));
1635 
1636 	/*
1637 	 * Check that the start and end points are not bogus.
1638 	 */
1639 	if (start == end || !vm_map_range_valid(map, start, end))
1640 		return (KERN_INVALID_ADDRESS);
1641 
1642 	if ((map->flags & MAP_WXORX) != 0 && (prot & (VM_PROT_WRITE |
1643 	    VM_PROT_EXECUTE)) == (VM_PROT_WRITE | VM_PROT_EXECUTE))
1644 		return (KERN_PROTECTION_FAILURE);
1645 
1646 	/*
1647 	 * Find the entry prior to the proposed starting address; if it's part
1648 	 * of an existing entry, this range is bogus.
1649 	 */
1650 	if (vm_map_lookup_entry(map, start, &prev_entry))
1651 		return (KERN_NO_SPACE);
1652 
1653 	/*
1654 	 * Assert that the next entry doesn't overlap the end point.
1655 	 */
1656 	next_entry = vm_map_entry_succ(prev_entry);
1657 	if (next_entry->start < end)
1658 		return (KERN_NO_SPACE);
1659 
1660 	if ((cow & MAP_CREATE_GUARD) != 0 && (object != NULL ||
1661 	    max != VM_PROT_NONE))
1662 		return (KERN_INVALID_ARGUMENT);
1663 
1664 	protoeflags = 0;
1665 	if (cow & MAP_COPY_ON_WRITE)
1666 		protoeflags |= MAP_ENTRY_COW | MAP_ENTRY_NEEDS_COPY;
1667 	if (cow & MAP_NOFAULT)
1668 		protoeflags |= MAP_ENTRY_NOFAULT;
1669 	if (cow & MAP_DISABLE_SYNCER)
1670 		protoeflags |= MAP_ENTRY_NOSYNC;
1671 	if (cow & MAP_DISABLE_COREDUMP)
1672 		protoeflags |= MAP_ENTRY_NOCOREDUMP;
1673 	if (cow & MAP_STACK_GROWS_DOWN)
1674 		protoeflags |= MAP_ENTRY_GROWS_DOWN;
1675 	if (cow & MAP_STACK_GROWS_UP)
1676 		protoeflags |= MAP_ENTRY_GROWS_UP;
1677 	if (cow & MAP_WRITECOUNT)
1678 		protoeflags |= MAP_ENTRY_WRITECNT;
1679 	if (cow & MAP_VN_EXEC)
1680 		protoeflags |= MAP_ENTRY_VN_EXEC;
1681 	if ((cow & MAP_CREATE_GUARD) != 0)
1682 		protoeflags |= MAP_ENTRY_GUARD;
1683 	if ((cow & MAP_CREATE_STACK_GAP_DN) != 0)
1684 		protoeflags |= MAP_ENTRY_STACK_GAP_DN;
1685 	if ((cow & MAP_CREATE_STACK_GAP_UP) != 0)
1686 		protoeflags |= MAP_ENTRY_STACK_GAP_UP;
1687 	if (cow & MAP_INHERIT_SHARE)
1688 		inheritance = VM_INHERIT_SHARE;
1689 	else
1690 		inheritance = VM_INHERIT_DEFAULT;
1691 	if ((cow & MAP_SPLIT_BOUNDARY_MASK) != 0) {
1692 		/* This magically ignores index 0, for usual page size. */
1693 		bidx = (cow & MAP_SPLIT_BOUNDARY_MASK) >>
1694 		    MAP_SPLIT_BOUNDARY_SHIFT;
1695 		if (bidx >= MAXPAGESIZES)
1696 			return (KERN_INVALID_ARGUMENT);
1697 		bdry = pagesizes[bidx] - 1;
1698 		if ((start & bdry) != 0 || (end & bdry) != 0)
1699 			return (KERN_INVALID_ARGUMENT);
1700 		protoeflags |= bidx << MAP_ENTRY_SPLIT_BOUNDARY_SHIFT;
1701 	}
1702 
1703 	cred = NULL;
1704 	if ((cow & (MAP_ACC_NO_CHARGE | MAP_NOFAULT | MAP_CREATE_GUARD)) != 0)
1705 		goto charged;
1706 	if ((cow & MAP_ACC_CHARGED) || ((prot & VM_PROT_WRITE) &&
1707 	    ((protoeflags & MAP_ENTRY_NEEDS_COPY) || object == NULL))) {
1708 		if (!(cow & MAP_ACC_CHARGED) && !swap_reserve(end - start))
1709 			return (KERN_RESOURCE_SHORTAGE);
1710 		KASSERT(object == NULL ||
1711 		    (protoeflags & MAP_ENTRY_NEEDS_COPY) != 0 ||
1712 		    object->cred == NULL,
1713 		    ("overcommit: vm_map_insert o %p", object));
1714 		cred = curthread->td_ucred;
1715 	}
1716 
1717 charged:
1718 	/* Expand the kernel pmap, if necessary. */
1719 	if (map == kernel_map && end > kernel_vm_end)
1720 		pmap_growkernel(end);
1721 	if (object != NULL) {
1722 		/*
1723 		 * OBJ_ONEMAPPING must be cleared unless this mapping
1724 		 * is trivially proven to be the only mapping for any
1725 		 * of the object's pages.  (Object granularity
1726 		 * reference counting is insufficient to recognize
1727 		 * aliases with precision.)
1728 		 */
1729 		if ((object->flags & OBJ_ANON) != 0) {
1730 			VM_OBJECT_WLOCK(object);
1731 			if (object->ref_count > 1 || object->shadow_count != 0)
1732 				vm_object_clear_flag(object, OBJ_ONEMAPPING);
1733 			VM_OBJECT_WUNLOCK(object);
1734 		}
1735 	} else if ((prev_entry->eflags & ~MAP_ENTRY_USER_WIRED) ==
1736 	    protoeflags &&
1737 	    (cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP |
1738 	    MAP_VN_EXEC)) == 0 &&
1739 	    prev_entry->end == start && (prev_entry->cred == cred ||
1740 	    (prev_entry->object.vm_object != NULL &&
1741 	    prev_entry->object.vm_object->cred == cred)) &&
1742 	    vm_object_coalesce(prev_entry->object.vm_object,
1743 	    prev_entry->offset,
1744 	    (vm_size_t)(prev_entry->end - prev_entry->start),
1745 	    (vm_size_t)(end - prev_entry->end), cred != NULL &&
1746 	    (protoeflags & MAP_ENTRY_NEEDS_COPY) == 0)) {
1747 		/*
1748 		 * We were able to extend the object.  Determine if we
1749 		 * can extend the previous map entry to include the
1750 		 * new range as well.
1751 		 */
1752 		if (prev_entry->inheritance == inheritance &&
1753 		    prev_entry->protection == prot &&
1754 		    prev_entry->max_protection == max &&
1755 		    prev_entry->wired_count == 0) {
1756 			KASSERT((prev_entry->eflags & MAP_ENTRY_USER_WIRED) ==
1757 			    0, ("prev_entry %p has incoherent wiring",
1758 			    prev_entry));
1759 			if ((prev_entry->eflags & MAP_ENTRY_GUARD) == 0)
1760 				map->size += end - prev_entry->end;
1761 			vm_map_entry_resize(map, prev_entry,
1762 			    end - prev_entry->end);
1763 			*res = vm_map_try_merge_entries(map, prev_entry,
1764 			    next_entry);
1765 			return (KERN_SUCCESS);
1766 		}
1767 
1768 		/*
1769 		 * If we can extend the object but cannot extend the
1770 		 * map entry, we have to create a new map entry.  We
1771 		 * must bump the ref count on the extended object to
1772 		 * account for it.  object may be NULL.
1773 		 */
1774 		object = prev_entry->object.vm_object;
1775 		offset = prev_entry->offset +
1776 		    (prev_entry->end - prev_entry->start);
1777 		vm_object_reference(object);
1778 		if (cred != NULL && object != NULL && object->cred != NULL &&
1779 		    !(prev_entry->eflags & MAP_ENTRY_NEEDS_COPY)) {
1780 			/* Object already accounts for this uid. */
1781 			cred = NULL;
1782 		}
1783 	}
1784 	if (cred != NULL)
1785 		crhold(cred);
1786 
1787 	/*
1788 	 * Create a new entry
1789 	 */
1790 	new_entry = vm_map_entry_create(map);
1791 	new_entry->start = start;
1792 	new_entry->end = end;
1793 	new_entry->cred = NULL;
1794 
1795 	new_entry->eflags = protoeflags;
1796 	new_entry->object.vm_object = object;
1797 	new_entry->offset = offset;
1798 
1799 	new_entry->inheritance = inheritance;
1800 	new_entry->protection = prot;
1801 	new_entry->max_protection = max;
1802 	new_entry->wired_count = 0;
1803 	new_entry->wiring_thread = NULL;
1804 	new_entry->read_ahead = VM_FAULT_READ_AHEAD_INIT;
1805 	new_entry->next_read = start;
1806 
1807 	KASSERT(cred == NULL || !ENTRY_CHARGED(new_entry),
1808 	    ("overcommit: vm_map_insert leaks vm_map %p", new_entry));
1809 	new_entry->cred = cred;
1810 
1811 	/*
1812 	 * Insert the new entry into the list
1813 	 */
1814 	vm_map_entry_link(map, new_entry);
1815 	if ((new_entry->eflags & MAP_ENTRY_GUARD) == 0)
1816 		map->size += new_entry->end - new_entry->start;
1817 
1818 	/*
1819 	 * Try to coalesce the new entry with both the previous and next
1820 	 * entries in the list.  Previously, we only attempted to coalesce
1821 	 * with the previous entry when object is NULL.  Here, we handle the
1822 	 * other cases, which are less common.
1823 	 */
1824 	vm_map_try_merge_entries(map, prev_entry, new_entry);
1825 	*res = vm_map_try_merge_entries(map, new_entry, next_entry);
1826 
1827 	if ((cow & (MAP_PREFAULT | MAP_PREFAULT_PARTIAL)) != 0) {
1828 		vm_map_pmap_enter(map, start, prot, object, OFF_TO_IDX(offset),
1829 		    end - start, cow & MAP_PREFAULT_PARTIAL);
1830 	}
1831 
1832 	return (KERN_SUCCESS);
1833 }
1834 
1835 /*
1836  *	vm_map_insert:
1837  *
1838  *	Inserts the given VM object into the target map at the
1839  *	specified address range.
1840  *
1841  *	Requires that the map be locked, and leaves it so.
1842  *
1843  *	If object is non-NULL, ref count must be bumped by caller
1844  *	prior to making call to account for the new entry.
1845  */
1846 int
1847 vm_map_insert(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
1848     vm_offset_t start, vm_offset_t end, vm_prot_t prot, vm_prot_t max, int cow)
1849 {
1850 	vm_map_entry_t res;
1851 
1852 	return (vm_map_insert1(map, object, offset, start, end, prot, max,
1853 	    cow, &res));
1854 }
1855 
1856 /*
1857  *	vm_map_findspace:
1858  *
1859  *	Find the first fit (lowest VM address) for "length" free bytes
1860  *	beginning at address >= start in the given map.
1861  *
1862  *	In a vm_map_entry, "max_free" is the maximum amount of
1863  *	contiguous free space between an entry in its subtree and a
1864  *	neighbor of that entry.  This allows finding a free region in
1865  *	one path down the tree, so O(log n) amortized with splay
1866  *	trees.
1867  *
1868  *	The map must be locked, and leaves it so.
1869  *
1870  *	Returns: starting address if sufficient space,
1871  *		 vm_map_max(map)-length+1 if insufficient space.
1872  */
1873 vm_offset_t
1874 vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length)
1875 {
1876 	vm_map_entry_t header, llist, rlist, root, y;
1877 	vm_size_t left_length, max_free_left, max_free_right;
1878 	vm_offset_t gap_end;
1879 
1880 	VM_MAP_ASSERT_LOCKED(map);
1881 
1882 	/*
1883 	 * Request must fit within min/max VM address and must avoid
1884 	 * address wrap.
1885 	 */
1886 	start = MAX(start, vm_map_min(map));
1887 	if (start >= vm_map_max(map) || length > vm_map_max(map) - start)
1888 		return (vm_map_max(map) - length + 1);
1889 
1890 	/* Empty tree means wide open address space. */
1891 	if (map->root == NULL)
1892 		return (start);
1893 
1894 	/*
1895 	 * After splay_split, if start is within an entry, push it to the start
1896 	 * of the following gap.  If rlist is at the end of the gap containing
1897 	 * start, save the end of that gap in gap_end to see if the gap is big
1898 	 * enough; otherwise set gap_end to start skip gap-checking and move
1899 	 * directly to a search of the right subtree.
1900 	 */
1901 	header = &map->header;
1902 	root = vm_map_splay_split(map, start, length, &llist, &rlist);
1903 	gap_end = rlist->start;
1904 	if (root != NULL) {
1905 		start = root->end;
1906 		if (root->right != rlist)
1907 			gap_end = start;
1908 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1909 		max_free_right = vm_map_splay_merge_right(header, root, rlist);
1910 	} else if (rlist != header) {
1911 		root = rlist;
1912 		rlist = root->left;
1913 		max_free_left = vm_map_splay_merge_pred(header, root, llist);
1914 		max_free_right = vm_map_splay_merge_right(header, root, rlist);
1915 	} else {
1916 		root = llist;
1917 		llist = root->right;
1918 		max_free_left = vm_map_splay_merge_left(header, root, llist);
1919 		max_free_right = vm_map_splay_merge_succ(header, root, rlist);
1920 	}
1921 	root->max_free = vm_size_max(max_free_left, max_free_right);
1922 	map->root = root;
1923 	VM_MAP_ASSERT_CONSISTENT(map);
1924 	if (length <= gap_end - start)
1925 		return (start);
1926 
1927 	/* With max_free, can immediately tell if no solution. */
1928 	if (root->right == header || length > root->right->max_free)
1929 		return (vm_map_max(map) - length + 1);
1930 
1931 	/*
1932 	 * Splay for the least large-enough gap in the right subtree.
1933 	 */
1934 	llist = rlist = header;
1935 	for (left_length = 0;;
1936 	    left_length = vm_map_entry_max_free_left(root, llist)) {
1937 		if (length <= left_length)
1938 			SPLAY_LEFT_STEP(root, y, llist, rlist,
1939 			    length <= vm_map_entry_max_free_left(y, llist));
1940 		else
1941 			SPLAY_RIGHT_STEP(root, y, llist, rlist,
1942 			    length > vm_map_entry_max_free_left(y, root));
1943 		if (root == NULL)
1944 			break;
1945 	}
1946 	root = llist;
1947 	llist = root->right;
1948 	max_free_left = vm_map_splay_merge_left(header, root, llist);
1949 	if (rlist == header) {
1950 		root->max_free = vm_size_max(max_free_left,
1951 		    vm_map_splay_merge_succ(header, root, rlist));
1952 	} else {
1953 		y = rlist;
1954 		rlist = y->left;
1955 		y->max_free = vm_size_max(
1956 		    vm_map_splay_merge_pred(root, y, root),
1957 		    vm_map_splay_merge_right(header, y, rlist));
1958 		root->max_free = vm_size_max(max_free_left, y->max_free);
1959 	}
1960 	map->root = root;
1961 	VM_MAP_ASSERT_CONSISTENT(map);
1962 	return (root->end);
1963 }
1964 
1965 int
1966 vm_map_fixed(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
1967     vm_offset_t start, vm_size_t length, vm_prot_t prot,
1968     vm_prot_t max, int cow)
1969 {
1970 	vm_offset_t end;
1971 	int result;
1972 
1973 	end = start + length;
1974 	KASSERT((cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP)) == 0 ||
1975 	    object == NULL,
1976 	    ("vm_map_fixed: non-NULL backing object for stack"));
1977 	vm_map_lock(map);
1978 	VM_MAP_RANGE_CHECK(map, start, end);
1979 	if ((cow & MAP_CHECK_EXCL) == 0) {
1980 		result = vm_map_delete(map, start, end);
1981 		if (result != KERN_SUCCESS)
1982 			goto out;
1983 	}
1984 	if ((cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP)) != 0) {
1985 		result = vm_map_stack_locked(map, start, length, sgrowsiz,
1986 		    prot, max, cow);
1987 	} else {
1988 		result = vm_map_insert(map, object, offset, start, end,
1989 		    prot, max, cow);
1990 	}
1991 out:
1992 	vm_map_unlock(map);
1993 	return (result);
1994 }
1995 
1996 #if VM_NRESERVLEVEL <= 1
1997 static const int aslr_pages_rnd_64[2] = {0x1000, 0x10};
1998 static const int aslr_pages_rnd_32[2] = {0x100, 0x4};
1999 #elif VM_NRESERVLEVEL == 2
2000 static const int aslr_pages_rnd_64[3] = {0x1000, 0x1000, 0x10};
2001 static const int aslr_pages_rnd_32[3] = {0x100, 0x100, 0x4};
2002 #else
2003 #error "Unsupported VM_NRESERVLEVEL"
2004 #endif
2005 
2006 static int cluster_anon = 1;
2007 SYSCTL_INT(_vm, OID_AUTO, cluster_anon, CTLFLAG_RW,
2008     &cluster_anon, 0,
2009     "Cluster anonymous mappings: 0 = no, 1 = yes if no hint, 2 = always");
2010 
2011 static bool
2012 clustering_anon_allowed(vm_offset_t addr, int cow)
2013 {
2014 
2015 	switch (cluster_anon) {
2016 	case 0:
2017 		return (false);
2018 	case 1:
2019 		return (addr == 0 || (cow & MAP_NO_HINT) != 0);
2020 	case 2:
2021 	default:
2022 		return (true);
2023 	}
2024 }
2025 
2026 static long aslr_restarts;
2027 SYSCTL_LONG(_vm, OID_AUTO, aslr_restarts, CTLFLAG_RD,
2028     &aslr_restarts, 0,
2029     "Number of aslr failures");
2030 
2031 /*
2032  * Searches for the specified amount of free space in the given map with the
2033  * specified alignment.  Performs an address-ordered, first-fit search from
2034  * the given address "*addr", with an optional upper bound "max_addr".  If the
2035  * parameter "alignment" is zero, then the alignment is computed from the
2036  * given (object, offset) pair so as to enable the greatest possible use of
2037  * superpage mappings.  Returns KERN_SUCCESS and the address of the free space
2038  * in "*addr" if successful.  Otherwise, returns KERN_NO_SPACE.
2039  *
2040  * The map must be locked.  Initially, there must be at least "length" bytes
2041  * of free space at the given address.
2042  */
2043 static int
2044 vm_map_alignspace(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
2045     vm_offset_t *addr, vm_size_t length, vm_offset_t max_addr,
2046     vm_offset_t alignment)
2047 {
2048 	vm_offset_t aligned_addr, free_addr;
2049 
2050 	VM_MAP_ASSERT_LOCKED(map);
2051 	free_addr = *addr;
2052 	KASSERT(free_addr == vm_map_findspace(map, free_addr, length),
2053 	    ("caller failed to provide space %#jx at address %p",
2054 	     (uintmax_t)length, (void *)free_addr));
2055 	for (;;) {
2056 		/*
2057 		 * At the start of every iteration, the free space at address
2058 		 * "*addr" is at least "length" bytes.
2059 		 */
2060 		if (alignment == 0)
2061 			pmap_align_superpage(object, offset, addr, length);
2062 		else
2063 			*addr = roundup2(*addr, alignment);
2064 		aligned_addr = *addr;
2065 		if (aligned_addr == free_addr) {
2066 			/*
2067 			 * Alignment did not change "*addr", so "*addr" must
2068 			 * still provide sufficient free space.
2069 			 */
2070 			return (KERN_SUCCESS);
2071 		}
2072 
2073 		/*
2074 		 * Test for address wrap on "*addr".  A wrapped "*addr" could
2075 		 * be a valid address, in which case vm_map_findspace() cannot
2076 		 * be relied upon to fail.
2077 		 */
2078 		if (aligned_addr < free_addr)
2079 			return (KERN_NO_SPACE);
2080 		*addr = vm_map_findspace(map, aligned_addr, length);
2081 		if (*addr + length > vm_map_max(map) ||
2082 		    (max_addr != 0 && *addr + length > max_addr))
2083 			return (KERN_NO_SPACE);
2084 		free_addr = *addr;
2085 		if (free_addr == aligned_addr) {
2086 			/*
2087 			 * If a successful call to vm_map_findspace() did not
2088 			 * change "*addr", then "*addr" must still be aligned
2089 			 * and provide sufficient free space.
2090 			 */
2091 			return (KERN_SUCCESS);
2092 		}
2093 	}
2094 }
2095 
2096 int
2097 vm_map_find_aligned(vm_map_t map, vm_offset_t *addr, vm_size_t length,
2098     vm_offset_t max_addr, vm_offset_t alignment)
2099 {
2100 	/* XXXKIB ASLR eh ? */
2101 	*addr = vm_map_findspace(map, *addr, length);
2102 	if (*addr + length > vm_map_max(map) ||
2103 	    (max_addr != 0 && *addr + length > max_addr))
2104 		return (KERN_NO_SPACE);
2105 	return (vm_map_alignspace(map, NULL, 0, addr, length, max_addr,
2106 	    alignment));
2107 }
2108 
2109 /*
2110  *	vm_map_find finds an unallocated region in the target address
2111  *	map with the given length.  The search is defined to be
2112  *	first-fit from the specified address; the region found is
2113  *	returned in the same parameter.
2114  *
2115  *	If object is non-NULL, ref count must be bumped by caller
2116  *	prior to making call to account for the new entry.
2117  */
2118 int
2119 vm_map_find(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
2120     vm_offset_t *addr,	/* IN/OUT */
2121     vm_size_t length, vm_offset_t max_addr, int find_space,
2122     vm_prot_t prot, vm_prot_t max, int cow)
2123 {
2124 	int rv;
2125 
2126 	vm_map_lock(map);
2127 	rv = vm_map_find_locked(map, object, offset, addr, length, max_addr,
2128 	    find_space, prot, max, cow);
2129 	vm_map_unlock(map);
2130 	return (rv);
2131 }
2132 
2133 int
2134 vm_map_find_locked(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
2135     vm_offset_t *addr,	/* IN/OUT */
2136     vm_size_t length, vm_offset_t max_addr, int find_space,
2137     vm_prot_t prot, vm_prot_t max, int cow)
2138 {
2139 	vm_offset_t alignment, curr_min_addr, min_addr;
2140 	int gap, pidx, rv, try;
2141 	bool cluster, en_aslr, update_anon;
2142 
2143 	KASSERT((cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP)) == 0 ||
2144 	    object == NULL,
2145 	    ("non-NULL backing object for stack"));
2146 	MPASS((cow & MAP_REMAP) == 0 || (find_space == VMFS_NO_SPACE &&
2147 	    (cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP)) == 0));
2148 	if (find_space == VMFS_OPTIMAL_SPACE && (object == NULL ||
2149 	    (object->flags & OBJ_COLORED) == 0))
2150 		find_space = VMFS_ANY_SPACE;
2151 	if (find_space >> 8 != 0) {
2152 		KASSERT((find_space & 0xff) == 0, ("bad VMFS flags"));
2153 		alignment = (vm_offset_t)1 << (find_space >> 8);
2154 	} else
2155 		alignment = 0;
2156 	en_aslr = (map->flags & MAP_ASLR) != 0;
2157 	update_anon = cluster = clustering_anon_allowed(*addr, cow) &&
2158 	    (map->flags & MAP_IS_SUB_MAP) == 0 && max_addr == 0 &&
2159 	    find_space != VMFS_NO_SPACE && object == NULL &&
2160 	    (cow & (MAP_INHERIT_SHARE | MAP_STACK_GROWS_UP |
2161 	    MAP_STACK_GROWS_DOWN)) == 0 && prot != PROT_NONE;
2162 	curr_min_addr = min_addr = *addr;
2163 	if (en_aslr && min_addr == 0 && !cluster &&
2164 	    find_space != VMFS_NO_SPACE &&
2165 	    (map->flags & MAP_ASLR_IGNSTART) != 0)
2166 		curr_min_addr = min_addr = vm_map_min(map);
2167 	try = 0;
2168 	if (cluster) {
2169 		curr_min_addr = map->anon_loc;
2170 		if (curr_min_addr == 0)
2171 			cluster = false;
2172 	}
2173 	if (find_space != VMFS_NO_SPACE) {
2174 		KASSERT(find_space == VMFS_ANY_SPACE ||
2175 		    find_space == VMFS_OPTIMAL_SPACE ||
2176 		    find_space == VMFS_SUPER_SPACE ||
2177 		    alignment != 0, ("unexpected VMFS flag"));
2178 again:
2179 		/*
2180 		 * When creating an anonymous mapping, try clustering
2181 		 * with an existing anonymous mapping first.
2182 		 *
2183 		 * We make up to two attempts to find address space
2184 		 * for a given find_space value. The first attempt may
2185 		 * apply randomization or may cluster with an existing
2186 		 * anonymous mapping. If this first attempt fails,
2187 		 * perform a first-fit search of the available address
2188 		 * space.
2189 		 *
2190 		 * If all tries failed, and find_space is
2191 		 * VMFS_OPTIMAL_SPACE, fallback to VMFS_ANY_SPACE.
2192 		 * Again enable clustering and randomization.
2193 		 */
2194 		try++;
2195 		MPASS(try <= 2);
2196 
2197 		if (try == 2) {
2198 			/*
2199 			 * Second try: we failed either to find a
2200 			 * suitable region for randomizing the
2201 			 * allocation, or to cluster with an existing
2202 			 * mapping.  Retry with free run.
2203 			 */
2204 			curr_min_addr = (map->flags & MAP_ASLR_IGNSTART) != 0 ?
2205 			    vm_map_min(map) : min_addr;
2206 			atomic_add_long(&aslr_restarts, 1);
2207 		}
2208 
2209 		if (try == 1 && en_aslr && !cluster) {
2210 			/*
2211 			 * Find space for allocation, including
2212 			 * gap needed for later randomization.
2213 			 */
2214 			pidx = 0;
2215 #if VM_NRESERVLEVEL > 0
2216 			if ((find_space == VMFS_SUPER_SPACE ||
2217 			    find_space == VMFS_OPTIMAL_SPACE) &&
2218 			    pagesizes[VM_NRESERVLEVEL] != 0) {
2219 				/*
2220 				 * Do not pointlessly increase the space that
2221 				 * is requested from vm_map_findspace().
2222 				 * pmap_align_superpage() will only change a
2223 				 * mapping's alignment if that mapping is at
2224 				 * least a superpage in size.
2225 				 */
2226 				pidx = VM_NRESERVLEVEL;
2227 				while (pidx > 0 && length < pagesizes[pidx])
2228 					pidx--;
2229 			}
2230 #endif
2231 			gap = vm_map_max(map) > MAP_32BIT_MAX_ADDR &&
2232 			    (max_addr == 0 || max_addr > MAP_32BIT_MAX_ADDR) ?
2233 			    aslr_pages_rnd_64[pidx] : aslr_pages_rnd_32[pidx];
2234 			*addr = vm_map_findspace(map, curr_min_addr,
2235 			    length + gap * pagesizes[pidx]);
2236 			if (*addr + length + gap * pagesizes[pidx] >
2237 			    vm_map_max(map))
2238 				goto again;
2239 			/* And randomize the start address. */
2240 			*addr += (arc4random() % gap) * pagesizes[pidx];
2241 			if (max_addr != 0 && *addr + length > max_addr)
2242 				goto again;
2243 		} else {
2244 			*addr = vm_map_findspace(map, curr_min_addr, length);
2245 			if (*addr + length > vm_map_max(map) ||
2246 			    (max_addr != 0 && *addr + length > max_addr)) {
2247 				if (cluster) {
2248 					cluster = false;
2249 					MPASS(try == 1);
2250 					goto again;
2251 				}
2252 				return (KERN_NO_SPACE);
2253 			}
2254 		}
2255 
2256 		if (find_space != VMFS_ANY_SPACE &&
2257 		    (rv = vm_map_alignspace(map, object, offset, addr, length,
2258 		    max_addr, alignment)) != KERN_SUCCESS) {
2259 			if (find_space == VMFS_OPTIMAL_SPACE) {
2260 				find_space = VMFS_ANY_SPACE;
2261 				curr_min_addr = min_addr;
2262 				cluster = update_anon;
2263 				try = 0;
2264 				goto again;
2265 			}
2266 			return (rv);
2267 		}
2268 	} else if ((cow & MAP_REMAP) != 0) {
2269 		if (!vm_map_range_valid(map, *addr, *addr + length))
2270 			return (KERN_INVALID_ADDRESS);
2271 		rv = vm_map_delete(map, *addr, *addr + length);
2272 		if (rv != KERN_SUCCESS)
2273 			return (rv);
2274 	}
2275 	if ((cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP)) != 0) {
2276 		rv = vm_map_stack_locked(map, *addr, length, sgrowsiz, prot,
2277 		    max, cow);
2278 	} else {
2279 		rv = vm_map_insert(map, object, offset, *addr, *addr + length,
2280 		    prot, max, cow);
2281 	}
2282 
2283 	/*
2284 	 * Update the starting address for clustered anonymous memory mappings
2285 	 * if a starting address was not previously defined or an ASLR restart
2286 	 * placed an anonymous memory mapping at a lower address.
2287 	 */
2288 	if (update_anon && rv == KERN_SUCCESS && (map->anon_loc == 0 ||
2289 	    *addr < map->anon_loc))
2290 		map->anon_loc = *addr;
2291 	return (rv);
2292 }
2293 
2294 /*
2295  *	vm_map_find_min() is a variant of vm_map_find() that takes an
2296  *	additional parameter ("default_addr") and treats the given address
2297  *	("*addr") differently.  Specifically, it treats "*addr" as a hint
2298  *	and not as the minimum address where the mapping is created.
2299  *
2300  *	This function works in two phases.  First, it tries to
2301  *	allocate above the hint.  If that fails and the hint is
2302  *	greater than "default_addr", it performs a second pass, replacing
2303  *	the hint with "default_addr" as the minimum address for the
2304  *	allocation.
2305  */
2306 int
2307 vm_map_find_min(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
2308     vm_offset_t *addr, vm_size_t length, vm_offset_t default_addr,
2309     vm_offset_t max_addr, int find_space, vm_prot_t prot, vm_prot_t max,
2310     int cow)
2311 {
2312 	vm_offset_t hint;
2313 	int rv;
2314 
2315 	hint = *addr;
2316 	if (hint == 0) {
2317 		cow |= MAP_NO_HINT;
2318 		*addr = hint = default_addr;
2319 	}
2320 	for (;;) {
2321 		rv = vm_map_find(map, object, offset, addr, length, max_addr,
2322 		    find_space, prot, max, cow);
2323 		if (rv == KERN_SUCCESS || default_addr >= hint)
2324 			return (rv);
2325 		*addr = hint = default_addr;
2326 	}
2327 }
2328 
2329 /*
2330  * A map entry with any of the following flags set must not be merged with
2331  * another entry.
2332  */
2333 #define	MAP_ENTRY_NOMERGE_MASK	(MAP_ENTRY_GROWS_DOWN | MAP_ENTRY_GROWS_UP | \
2334     MAP_ENTRY_IN_TRANSITION | MAP_ENTRY_IS_SUB_MAP | MAP_ENTRY_VN_EXEC | \
2335     MAP_ENTRY_STACK_GAP_UP | MAP_ENTRY_STACK_GAP_DN)
2336 
2337 static bool
2338 vm_map_mergeable_neighbors(vm_map_entry_t prev, vm_map_entry_t entry)
2339 {
2340 
2341 	KASSERT((prev->eflags & MAP_ENTRY_NOMERGE_MASK) == 0 ||
2342 	    (entry->eflags & MAP_ENTRY_NOMERGE_MASK) == 0,
2343 	    ("vm_map_mergeable_neighbors: neither %p nor %p are mergeable",
2344 	    prev, entry));
2345 	return (prev->end == entry->start &&
2346 	    prev->object.vm_object == entry->object.vm_object &&
2347 	    (prev->object.vm_object == NULL ||
2348 	    prev->offset + (prev->end - prev->start) == entry->offset) &&
2349 	    prev->eflags == entry->eflags &&
2350 	    prev->protection == entry->protection &&
2351 	    prev->max_protection == entry->max_protection &&
2352 	    prev->inheritance == entry->inheritance &&
2353 	    prev->wired_count == entry->wired_count &&
2354 	    prev->cred == entry->cred);
2355 }
2356 
2357 static void
2358 vm_map_merged_neighbor_dispose(vm_map_t map, vm_map_entry_t entry)
2359 {
2360 
2361 	/*
2362 	 * If the backing object is a vnode object, vm_object_deallocate()
2363 	 * calls vrele().  However, vrele() does not lock the vnode because
2364 	 * the vnode has additional references.  Thus, the map lock can be
2365 	 * kept without causing a lock-order reversal with the vnode lock.
2366 	 *
2367 	 * Since we count the number of virtual page mappings in
2368 	 * object->un_pager.vnp.writemappings, the writemappings value
2369 	 * should not be adjusted when the entry is disposed of.
2370 	 */
2371 	if (entry->object.vm_object != NULL)
2372 		vm_object_deallocate(entry->object.vm_object);
2373 	if (entry->cred != NULL)
2374 		crfree(entry->cred);
2375 	vm_map_entry_dispose(map, entry);
2376 }
2377 
2378 /*
2379  *	vm_map_try_merge_entries:
2380  *
2381  *	Compare two map entries that represent consecutive ranges. If
2382  *	the entries can be merged, expand the range of the second to
2383  *	cover the range of the first and delete the first. Then return
2384  *	the map entry that includes the first range.
2385  *
2386  *	The map must be locked.
2387  */
2388 vm_map_entry_t
2389 vm_map_try_merge_entries(vm_map_t map, vm_map_entry_t prev_entry,
2390     vm_map_entry_t entry)
2391 {
2392 
2393 	VM_MAP_ASSERT_LOCKED(map);
2394 	if ((entry->eflags & MAP_ENTRY_NOMERGE_MASK) == 0 &&
2395 	    vm_map_mergeable_neighbors(prev_entry, entry)) {
2396 		vm_map_entry_unlink(map, prev_entry, UNLINK_MERGE_NEXT);
2397 		vm_map_merged_neighbor_dispose(map, prev_entry);
2398 		return (entry);
2399 	}
2400 	return (prev_entry);
2401 }
2402 
2403 /*
2404  *	vm_map_entry_back:
2405  *
2406  *	Allocate an object to back a map entry.
2407  */
2408 static inline void
2409 vm_map_entry_back(vm_map_entry_t entry)
2410 {
2411 	vm_object_t object;
2412 
2413 	KASSERT(entry->object.vm_object == NULL,
2414 	    ("map entry %p has backing object", entry));
2415 	KASSERT((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0,
2416 	    ("map entry %p is a submap", entry));
2417 	object = vm_object_allocate_anon(atop(entry->end - entry->start), NULL,
2418 	    entry->cred, entry->end - entry->start);
2419 	entry->object.vm_object = object;
2420 	entry->offset = 0;
2421 	entry->cred = NULL;
2422 }
2423 
2424 /*
2425  *	vm_map_entry_charge_object
2426  *
2427  *	If there is no object backing this entry, create one.  Otherwise, if
2428  *	the entry has cred, give it to the backing object.
2429  */
2430 static inline void
2431 vm_map_entry_charge_object(vm_map_t map, vm_map_entry_t entry)
2432 {
2433 
2434 	VM_MAP_ASSERT_LOCKED(map);
2435 	KASSERT((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0,
2436 	    ("map entry %p is a submap", entry));
2437 	if (entry->object.vm_object == NULL && !map->system_map &&
2438 	    (entry->eflags & MAP_ENTRY_GUARD) == 0)
2439 		vm_map_entry_back(entry);
2440 	else if (entry->object.vm_object != NULL &&
2441 	    ((entry->eflags & MAP_ENTRY_NEEDS_COPY) == 0) &&
2442 	    entry->cred != NULL) {
2443 		VM_OBJECT_WLOCK(entry->object.vm_object);
2444 		KASSERT(entry->object.vm_object->cred == NULL,
2445 		    ("OVERCOMMIT: %s: both cred e %p", __func__, entry));
2446 		entry->object.vm_object->cred = entry->cred;
2447 		entry->object.vm_object->charge = entry->end - entry->start;
2448 		VM_OBJECT_WUNLOCK(entry->object.vm_object);
2449 		entry->cred = NULL;
2450 	}
2451 }
2452 
2453 /*
2454  *	vm_map_entry_clone
2455  *
2456  *	Create a duplicate map entry for clipping.
2457  */
2458 static vm_map_entry_t
2459 vm_map_entry_clone(vm_map_t map, vm_map_entry_t entry)
2460 {
2461 	vm_map_entry_t new_entry;
2462 
2463 	VM_MAP_ASSERT_LOCKED(map);
2464 
2465 	/*
2466 	 * Create a backing object now, if none exists, so that more individual
2467 	 * objects won't be created after the map entry is split.
2468 	 */
2469 	vm_map_entry_charge_object(map, entry);
2470 
2471 	/* Clone the entry. */
2472 	new_entry = vm_map_entry_create(map);
2473 	*new_entry = *entry;
2474 	if (new_entry->cred != NULL)
2475 		crhold(entry->cred);
2476 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
2477 		vm_object_reference(new_entry->object.vm_object);
2478 		vm_map_entry_set_vnode_text(new_entry, true);
2479 		/*
2480 		 * The object->un_pager.vnp.writemappings for the object of
2481 		 * MAP_ENTRY_WRITECNT type entry shall be kept as is here.  The
2482 		 * virtual pages are re-distributed among the clipped entries,
2483 		 * so the sum is left the same.
2484 		 */
2485 	}
2486 	return (new_entry);
2487 }
2488 
2489 /*
2490  *	vm_map_clip_start:	[ internal use only ]
2491  *
2492  *	Asserts that the given entry begins at or after
2493  *	the specified address; if necessary,
2494  *	it splits the entry into two.
2495  */
2496 static int
2497 vm_map_clip_start(vm_map_t map, vm_map_entry_t entry, vm_offset_t startaddr)
2498 {
2499 	vm_map_entry_t new_entry;
2500 	int bdry_idx;
2501 
2502 	if (!map->system_map)
2503 		WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
2504 		    "%s: map %p entry %p start 0x%jx", __func__, map, entry,
2505 		    (uintmax_t)startaddr);
2506 
2507 	if (startaddr <= entry->start)
2508 		return (KERN_SUCCESS);
2509 
2510 	VM_MAP_ASSERT_LOCKED(map);
2511 	KASSERT(entry->end > startaddr && entry->start < startaddr,
2512 	    ("%s: invalid clip of entry %p", __func__, entry));
2513 
2514 	bdry_idx = MAP_ENTRY_SPLIT_BOUNDARY_INDEX(entry);
2515 	if (bdry_idx != 0) {
2516 		if ((startaddr & (pagesizes[bdry_idx] - 1)) != 0)
2517 			return (KERN_INVALID_ARGUMENT);
2518 	}
2519 
2520 	new_entry = vm_map_entry_clone(map, entry);
2521 
2522 	/*
2523 	 * Split off the front portion.  Insert the new entry BEFORE this one,
2524 	 * so that this entry has the specified starting address.
2525 	 */
2526 	new_entry->end = startaddr;
2527 	vm_map_entry_link(map, new_entry);
2528 	return (KERN_SUCCESS);
2529 }
2530 
2531 /*
2532  *	vm_map_lookup_clip_start:
2533  *
2534  *	Find the entry at or just after 'start', and clip it if 'start' is in
2535  *	the interior of the entry.  Return entry after 'start', and in
2536  *	prev_entry set the entry before 'start'.
2537  */
2538 static int
2539 vm_map_lookup_clip_start(vm_map_t map, vm_offset_t start,
2540     vm_map_entry_t *res_entry, vm_map_entry_t *prev_entry)
2541 {
2542 	vm_map_entry_t entry;
2543 	int rv;
2544 
2545 	if (!map->system_map)
2546 		WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
2547 		    "%s: map %p start 0x%jx prev %p", __func__, map,
2548 		    (uintmax_t)start, prev_entry);
2549 
2550 	if (vm_map_lookup_entry(map, start, prev_entry)) {
2551 		entry = *prev_entry;
2552 		rv = vm_map_clip_start(map, entry, start);
2553 		if (rv != KERN_SUCCESS)
2554 			return (rv);
2555 		*prev_entry = vm_map_entry_pred(entry);
2556 	} else
2557 		entry = vm_map_entry_succ(*prev_entry);
2558 	*res_entry = entry;
2559 	return (KERN_SUCCESS);
2560 }
2561 
2562 /*
2563  *	vm_map_clip_end:	[ internal use only ]
2564  *
2565  *	Asserts that the given entry ends at or before
2566  *	the specified address; if necessary,
2567  *	it splits the entry into two.
2568  */
2569 static int
2570 vm_map_clip_end(vm_map_t map, vm_map_entry_t entry, vm_offset_t endaddr)
2571 {
2572 	vm_map_entry_t new_entry;
2573 	int bdry_idx;
2574 
2575 	if (!map->system_map)
2576 		WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
2577 		    "%s: map %p entry %p end 0x%jx", __func__, map, entry,
2578 		    (uintmax_t)endaddr);
2579 
2580 	if (endaddr >= entry->end)
2581 		return (KERN_SUCCESS);
2582 
2583 	VM_MAP_ASSERT_LOCKED(map);
2584 	KASSERT(entry->start < endaddr && entry->end > endaddr,
2585 	    ("%s: invalid clip of entry %p", __func__, entry));
2586 
2587 	bdry_idx = MAP_ENTRY_SPLIT_BOUNDARY_INDEX(entry);
2588 	if (bdry_idx != 0) {
2589 		if ((endaddr & (pagesizes[bdry_idx] - 1)) != 0)
2590 			return (KERN_INVALID_ARGUMENT);
2591 	}
2592 
2593 	new_entry = vm_map_entry_clone(map, entry);
2594 
2595 	/*
2596 	 * Split off the back portion.  Insert the new entry AFTER this one,
2597 	 * so that this entry has the specified ending address.
2598 	 */
2599 	new_entry->start = endaddr;
2600 	vm_map_entry_link(map, new_entry);
2601 
2602 	return (KERN_SUCCESS);
2603 }
2604 
2605 /*
2606  *	vm_map_submap:		[ kernel use only ]
2607  *
2608  *	Mark the given range as handled by a subordinate map.
2609  *
2610  *	This range must have been created with vm_map_find,
2611  *	and no other operations may have been performed on this
2612  *	range prior to calling vm_map_submap.
2613  *
2614  *	Only a limited number of operations can be performed
2615  *	within this rage after calling vm_map_submap:
2616  *		vm_fault
2617  *	[Don't try vm_map_copy!]
2618  *
2619  *	To remove a submapping, one must first remove the
2620  *	range from the superior map, and then destroy the
2621  *	submap (if desired).  [Better yet, don't try it.]
2622  */
2623 int
2624 vm_map_submap(
2625 	vm_map_t map,
2626 	vm_offset_t start,
2627 	vm_offset_t end,
2628 	vm_map_t submap)
2629 {
2630 	vm_map_entry_t entry;
2631 	int result;
2632 
2633 	result = KERN_INVALID_ARGUMENT;
2634 
2635 	vm_map_lock(submap);
2636 	submap->flags |= MAP_IS_SUB_MAP;
2637 	vm_map_unlock(submap);
2638 
2639 	vm_map_lock(map);
2640 	VM_MAP_RANGE_CHECK(map, start, end);
2641 	if (vm_map_lookup_entry(map, start, &entry) && entry->end >= end &&
2642 	    (entry->eflags & MAP_ENTRY_COW) == 0 &&
2643 	    entry->object.vm_object == NULL) {
2644 		result = vm_map_clip_start(map, entry, start);
2645 		if (result != KERN_SUCCESS)
2646 			goto unlock;
2647 		result = vm_map_clip_end(map, entry, end);
2648 		if (result != KERN_SUCCESS)
2649 			goto unlock;
2650 		entry->object.sub_map = submap;
2651 		entry->eflags |= MAP_ENTRY_IS_SUB_MAP;
2652 		result = KERN_SUCCESS;
2653 	}
2654 unlock:
2655 	vm_map_unlock(map);
2656 
2657 	if (result != KERN_SUCCESS) {
2658 		vm_map_lock(submap);
2659 		submap->flags &= ~MAP_IS_SUB_MAP;
2660 		vm_map_unlock(submap);
2661 	}
2662 	return (result);
2663 }
2664 
2665 /*
2666  * The maximum number of pages to map if MAP_PREFAULT_PARTIAL is specified
2667  */
2668 #define	MAX_INIT_PT	96
2669 
2670 /*
2671  *	vm_map_pmap_enter:
2672  *
2673  *	Preload the specified map's pmap with mappings to the specified
2674  *	object's memory-resident pages.  No further physical pages are
2675  *	allocated, and no further virtual pages are retrieved from secondary
2676  *	storage.  If the specified flags include MAP_PREFAULT_PARTIAL, then a
2677  *	limited number of page mappings are created at the low-end of the
2678  *	specified address range.  (For this purpose, a superpage mapping
2679  *	counts as one page mapping.)  Otherwise, all resident pages within
2680  *	the specified address range are mapped.
2681  */
2682 static void
2683 vm_map_pmap_enter(vm_map_t map, vm_offset_t addr, vm_prot_t prot,
2684     vm_object_t object, vm_pindex_t pindex, vm_size_t size, int flags)
2685 {
2686 	vm_offset_t start;
2687 	vm_page_t p, p_start;
2688 	vm_pindex_t mask, psize, threshold, tmpidx;
2689 	int psind;
2690 
2691 	if ((prot & (VM_PROT_READ | VM_PROT_EXECUTE)) == 0 || object == NULL)
2692 		return;
2693 	if (object->type == OBJT_DEVICE || object->type == OBJT_SG) {
2694 		VM_OBJECT_WLOCK(object);
2695 		if (object->type == OBJT_DEVICE || object->type == OBJT_SG) {
2696 			pmap_object_init_pt(map->pmap, addr, object, pindex,
2697 			    size);
2698 			VM_OBJECT_WUNLOCK(object);
2699 			return;
2700 		}
2701 		VM_OBJECT_LOCK_DOWNGRADE(object);
2702 	} else
2703 		VM_OBJECT_RLOCK(object);
2704 
2705 	psize = atop(size);
2706 	if (psize + pindex > object->size) {
2707 		if (pindex >= object->size) {
2708 			VM_OBJECT_RUNLOCK(object);
2709 			return;
2710 		}
2711 		psize = object->size - pindex;
2712 	}
2713 
2714 	start = 0;
2715 	p_start = NULL;
2716 	threshold = MAX_INIT_PT;
2717 
2718 	p = vm_page_find_least(object, pindex);
2719 	/*
2720 	 * Assert: the variable p is either (1) the page with the
2721 	 * least pindex greater than or equal to the parameter pindex
2722 	 * or (2) NULL.
2723 	 */
2724 	for (;
2725 	     p != NULL && (tmpidx = p->pindex - pindex) < psize;
2726 	     p = TAILQ_NEXT(p, listq)) {
2727 		/*
2728 		 * don't allow an madvise to blow away our really
2729 		 * free pages allocating pv entries.
2730 		 */
2731 		if (((flags & MAP_PREFAULT_MADVISE) != 0 &&
2732 		    vm_page_count_severe()) ||
2733 		    ((flags & MAP_PREFAULT_PARTIAL) != 0 &&
2734 		    tmpidx >= threshold)) {
2735 			psize = tmpidx;
2736 			break;
2737 		}
2738 		if (vm_page_all_valid(p)) {
2739 			if (p_start == NULL) {
2740 				start = addr + ptoa(tmpidx);
2741 				p_start = p;
2742 			}
2743 			/* Jump ahead if a superpage mapping is possible. */
2744 			for (psind = p->psind; psind > 0; psind--) {
2745 				if (((addr + ptoa(tmpidx)) &
2746 				    (pagesizes[psind] - 1)) == 0) {
2747 					mask = atop(pagesizes[psind]) - 1;
2748 					if (tmpidx + mask < psize &&
2749 					    vm_page_ps_test(p, psind,
2750 					    PS_ALL_VALID, NULL)) {
2751 						p += mask;
2752 						threshold += mask;
2753 						break;
2754 					}
2755 				}
2756 			}
2757 		} else if (p_start != NULL) {
2758 			pmap_enter_object(map->pmap, start, addr +
2759 			    ptoa(tmpidx), p_start, prot);
2760 			p_start = NULL;
2761 		}
2762 	}
2763 	if (p_start != NULL)
2764 		pmap_enter_object(map->pmap, start, addr + ptoa(psize),
2765 		    p_start, prot);
2766 	VM_OBJECT_RUNLOCK(object);
2767 }
2768 
2769 static void
2770 vm_map_protect_guard(vm_map_entry_t entry, vm_prot_t new_prot,
2771     vm_prot_t new_maxprot, int flags)
2772 {
2773 	vm_prot_t old_prot;
2774 
2775 	MPASS((entry->eflags & MAP_ENTRY_GUARD) != 0);
2776 	if ((entry->eflags & (MAP_ENTRY_STACK_GAP_UP |
2777 	    MAP_ENTRY_STACK_GAP_DN)) == 0)
2778 		return;
2779 
2780 	old_prot = PROT_EXTRACT(entry->offset);
2781 	if ((flags & VM_MAP_PROTECT_SET_MAXPROT) != 0) {
2782 		entry->offset = PROT_MAX(new_maxprot) |
2783 		    (new_maxprot & old_prot);
2784 	}
2785 	if ((flags & VM_MAP_PROTECT_SET_PROT) != 0) {
2786 		entry->offset = new_prot | PROT_MAX(
2787 		    PROT_MAX_EXTRACT(entry->offset));
2788 	}
2789 }
2790 
2791 /*
2792  *	vm_map_protect:
2793  *
2794  *	Sets the protection and/or the maximum protection of the
2795  *	specified address region in the target map.
2796  */
2797 int
2798 vm_map_protect(vm_map_t map, vm_offset_t start, vm_offset_t end,
2799     vm_prot_t new_prot, vm_prot_t new_maxprot, int flags)
2800 {
2801 	vm_map_entry_t entry, first_entry, in_tran, prev_entry;
2802 	vm_object_t obj;
2803 	struct ucred *cred;
2804 	vm_offset_t orig_start;
2805 	vm_prot_t check_prot, max_prot, old_prot;
2806 	int rv;
2807 
2808 	if (start == end)
2809 		return (KERN_SUCCESS);
2810 
2811 	if (CONTAINS_BITS(flags, VM_MAP_PROTECT_SET_PROT |
2812 	    VM_MAP_PROTECT_SET_MAXPROT) &&
2813 	    !CONTAINS_BITS(new_maxprot, new_prot))
2814 		return (KERN_OUT_OF_BOUNDS);
2815 
2816 	orig_start = start;
2817 again:
2818 	in_tran = NULL;
2819 	start = orig_start;
2820 	vm_map_lock(map);
2821 
2822 	if ((map->flags & MAP_WXORX) != 0 &&
2823 	    (flags & VM_MAP_PROTECT_SET_PROT) != 0 &&
2824 	    CONTAINS_BITS(new_prot, VM_PROT_WRITE | VM_PROT_EXECUTE)) {
2825 		vm_map_unlock(map);
2826 		return (KERN_PROTECTION_FAILURE);
2827 	}
2828 
2829 	/*
2830 	 * Ensure that we are not concurrently wiring pages.  vm_map_wire() may
2831 	 * need to fault pages into the map and will drop the map lock while
2832 	 * doing so, and the VM object may end up in an inconsistent state if we
2833 	 * update the protection on the map entry in between faults.
2834 	 */
2835 	vm_map_wait_busy(map);
2836 
2837 	VM_MAP_RANGE_CHECK(map, start, end);
2838 
2839 	if (!vm_map_lookup_entry(map, start, &first_entry))
2840 		first_entry = vm_map_entry_succ(first_entry);
2841 
2842 	if ((flags & VM_MAP_PROTECT_GROWSDOWN) != 0 &&
2843 	    (first_entry->eflags & MAP_ENTRY_GROWS_DOWN) != 0) {
2844 		/*
2845 		 * Handle Linux's PROT_GROWSDOWN flag.
2846 		 * It means that protection is applied down to the
2847 		 * whole stack, including the specified range of the
2848 		 * mapped region, and the grow down region (AKA
2849 		 * guard).
2850 		 */
2851 		while (!CONTAINS_BITS(first_entry->eflags,
2852 		    MAP_ENTRY_GUARD | MAP_ENTRY_STACK_GAP_DN) &&
2853 		    first_entry != vm_map_entry_first(map))
2854 			first_entry = vm_map_entry_pred(first_entry);
2855 		start = first_entry->start;
2856 	}
2857 
2858 	/*
2859 	 * Make a first pass to check for protection violations.
2860 	 */
2861 	check_prot = 0;
2862 	if ((flags & VM_MAP_PROTECT_SET_PROT) != 0)
2863 		check_prot |= new_prot;
2864 	if ((flags & VM_MAP_PROTECT_SET_MAXPROT) != 0)
2865 		check_prot |= new_maxprot;
2866 	for (entry = first_entry; entry->start < end;
2867 	    entry = vm_map_entry_succ(entry)) {
2868 		if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) != 0) {
2869 			vm_map_unlock(map);
2870 			return (KERN_INVALID_ARGUMENT);
2871 		}
2872 		if ((entry->eflags & (MAP_ENTRY_GUARD |
2873 		    MAP_ENTRY_STACK_GAP_DN | MAP_ENTRY_STACK_GAP_UP)) ==
2874 		    MAP_ENTRY_GUARD)
2875 			continue;
2876 		max_prot = (entry->eflags & (MAP_ENTRY_STACK_GAP_DN |
2877 		    MAP_ENTRY_STACK_GAP_UP)) != 0 ?
2878 		    PROT_MAX_EXTRACT(entry->offset) : entry->max_protection;
2879 		if (!CONTAINS_BITS(max_prot, check_prot)) {
2880 			vm_map_unlock(map);
2881 			return (KERN_PROTECTION_FAILURE);
2882 		}
2883 		if ((entry->eflags & MAP_ENTRY_IN_TRANSITION) != 0)
2884 			in_tran = entry;
2885 	}
2886 
2887 	/*
2888 	 * Postpone the operation until all in-transition map entries have
2889 	 * stabilized.  An in-transition entry might already have its pages
2890 	 * wired and wired_count incremented, but not yet have its
2891 	 * MAP_ENTRY_USER_WIRED flag set.  In which case, we would fail to call
2892 	 * vm_fault_copy_entry() in the final loop below.
2893 	 */
2894 	if (in_tran != NULL) {
2895 		in_tran->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
2896 		vm_map_unlock_and_wait(map, 0);
2897 		goto again;
2898 	}
2899 
2900 	/*
2901 	 * Before changing the protections, try to reserve swap space for any
2902 	 * private (i.e., copy-on-write) mappings that are transitioning from
2903 	 * read-only to read/write access.  If a reservation fails, break out
2904 	 * of this loop early and let the next loop simplify the entries, since
2905 	 * some may now be mergeable.
2906 	 */
2907 	rv = vm_map_clip_start(map, first_entry, start);
2908 	if (rv != KERN_SUCCESS) {
2909 		vm_map_unlock(map);
2910 		return (rv);
2911 	}
2912 	for (entry = first_entry; entry->start < end;
2913 	    entry = vm_map_entry_succ(entry)) {
2914 		rv = vm_map_clip_end(map, entry, end);
2915 		if (rv != KERN_SUCCESS) {
2916 			vm_map_unlock(map);
2917 			return (rv);
2918 		}
2919 
2920 		if ((flags & VM_MAP_PROTECT_SET_PROT) == 0 ||
2921 		    ((new_prot & ~entry->protection) & VM_PROT_WRITE) == 0 ||
2922 		    ENTRY_CHARGED(entry) ||
2923 		    (entry->eflags & MAP_ENTRY_GUARD) != 0)
2924 			continue;
2925 
2926 		cred = curthread->td_ucred;
2927 		obj = entry->object.vm_object;
2928 
2929 		if (obj == NULL ||
2930 		    (entry->eflags & MAP_ENTRY_NEEDS_COPY) != 0) {
2931 			if (!swap_reserve(entry->end - entry->start)) {
2932 				rv = KERN_RESOURCE_SHORTAGE;
2933 				end = entry->end;
2934 				break;
2935 			}
2936 			crhold(cred);
2937 			entry->cred = cred;
2938 			continue;
2939 		}
2940 
2941 		VM_OBJECT_WLOCK(obj);
2942 		if ((obj->flags & OBJ_SWAP) == 0) {
2943 			VM_OBJECT_WUNLOCK(obj);
2944 			continue;
2945 		}
2946 
2947 		/*
2948 		 * Charge for the whole object allocation now, since
2949 		 * we cannot distinguish between non-charged and
2950 		 * charged clipped mapping of the same object later.
2951 		 */
2952 		KASSERT(obj->charge == 0,
2953 		    ("vm_map_protect: object %p overcharged (entry %p)",
2954 		    obj, entry));
2955 		if (!swap_reserve(ptoa(obj->size))) {
2956 			VM_OBJECT_WUNLOCK(obj);
2957 			rv = KERN_RESOURCE_SHORTAGE;
2958 			end = entry->end;
2959 			break;
2960 		}
2961 
2962 		crhold(cred);
2963 		obj->cred = cred;
2964 		obj->charge = ptoa(obj->size);
2965 		VM_OBJECT_WUNLOCK(obj);
2966 	}
2967 
2968 	/*
2969 	 * If enough swap space was available, go back and fix up protections.
2970 	 * Otherwise, just simplify entries, since some may have been modified.
2971 	 * [Note that clipping is not necessary the second time.]
2972 	 */
2973 	for (prev_entry = vm_map_entry_pred(first_entry), entry = first_entry;
2974 	    entry->start < end;
2975 	    vm_map_try_merge_entries(map, prev_entry, entry),
2976 	    prev_entry = entry, entry = vm_map_entry_succ(entry)) {
2977 		if (rv != KERN_SUCCESS)
2978 			continue;
2979 
2980 		if ((entry->eflags & MAP_ENTRY_GUARD) != 0) {
2981 			vm_map_protect_guard(entry, new_prot, new_maxprot,
2982 			    flags);
2983 			continue;
2984 		}
2985 
2986 		old_prot = entry->protection;
2987 
2988 		if ((flags & VM_MAP_PROTECT_SET_MAXPROT) != 0) {
2989 			entry->max_protection = new_maxprot;
2990 			entry->protection = new_maxprot & old_prot;
2991 		}
2992 		if ((flags & VM_MAP_PROTECT_SET_PROT) != 0)
2993 			entry->protection = new_prot;
2994 
2995 		/*
2996 		 * For user wired map entries, the normal lazy evaluation of
2997 		 * write access upgrades through soft page faults is
2998 		 * undesirable.  Instead, immediately copy any pages that are
2999 		 * copy-on-write and enable write access in the physical map.
3000 		 */
3001 		if ((entry->eflags & MAP_ENTRY_USER_WIRED) != 0 &&
3002 		    (entry->protection & VM_PROT_WRITE) != 0 &&
3003 		    (old_prot & VM_PROT_WRITE) == 0)
3004 			vm_fault_copy_entry(map, map, entry, entry, NULL);
3005 
3006 		/*
3007 		 * When restricting access, update the physical map.  Worry
3008 		 * about copy-on-write here.
3009 		 */
3010 		if ((old_prot & ~entry->protection) != 0) {
3011 #define MASK(entry)	(((entry)->eflags & MAP_ENTRY_COW) ? ~VM_PROT_WRITE : \
3012 							VM_PROT_ALL)
3013 			pmap_protect(map->pmap, entry->start,
3014 			    entry->end,
3015 			    entry->protection & MASK(entry));
3016 #undef	MASK
3017 		}
3018 	}
3019 	vm_map_try_merge_entries(map, prev_entry, entry);
3020 	vm_map_unlock(map);
3021 	return (rv);
3022 }
3023 
3024 /*
3025  *	vm_map_madvise:
3026  *
3027  *	This routine traverses a processes map handling the madvise
3028  *	system call.  Advisories are classified as either those effecting
3029  *	the vm_map_entry structure, or those effecting the underlying
3030  *	objects.
3031  */
3032 int
3033 vm_map_madvise(
3034 	vm_map_t map,
3035 	vm_offset_t start,
3036 	vm_offset_t end,
3037 	int behav)
3038 {
3039 	vm_map_entry_t entry, prev_entry;
3040 	int rv;
3041 	bool modify_map;
3042 
3043 	/*
3044 	 * Some madvise calls directly modify the vm_map_entry, in which case
3045 	 * we need to use an exclusive lock on the map and we need to perform
3046 	 * various clipping operations.  Otherwise we only need a read-lock
3047 	 * on the map.
3048 	 */
3049 	switch(behav) {
3050 	case MADV_NORMAL:
3051 	case MADV_SEQUENTIAL:
3052 	case MADV_RANDOM:
3053 	case MADV_NOSYNC:
3054 	case MADV_AUTOSYNC:
3055 	case MADV_NOCORE:
3056 	case MADV_CORE:
3057 		if (start == end)
3058 			return (0);
3059 		modify_map = true;
3060 		vm_map_lock(map);
3061 		break;
3062 	case MADV_WILLNEED:
3063 	case MADV_DONTNEED:
3064 	case MADV_FREE:
3065 		if (start == end)
3066 			return (0);
3067 		modify_map = false;
3068 		vm_map_lock_read(map);
3069 		break;
3070 	default:
3071 		return (EINVAL);
3072 	}
3073 
3074 	/*
3075 	 * Locate starting entry and clip if necessary.
3076 	 */
3077 	VM_MAP_RANGE_CHECK(map, start, end);
3078 
3079 	if (modify_map) {
3080 		/*
3081 		 * madvise behaviors that are implemented in the vm_map_entry.
3082 		 *
3083 		 * We clip the vm_map_entry so that behavioral changes are
3084 		 * limited to the specified address range.
3085 		 */
3086 		rv = vm_map_lookup_clip_start(map, start, &entry, &prev_entry);
3087 		if (rv != KERN_SUCCESS) {
3088 			vm_map_unlock(map);
3089 			return (vm_mmap_to_errno(rv));
3090 		}
3091 
3092 		for (; entry->start < end; prev_entry = entry,
3093 		    entry = vm_map_entry_succ(entry)) {
3094 			if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) != 0)
3095 				continue;
3096 
3097 			rv = vm_map_clip_end(map, entry, end);
3098 			if (rv != KERN_SUCCESS) {
3099 				vm_map_unlock(map);
3100 				return (vm_mmap_to_errno(rv));
3101 			}
3102 
3103 			switch (behav) {
3104 			case MADV_NORMAL:
3105 				vm_map_entry_set_behavior(entry,
3106 				    MAP_ENTRY_BEHAV_NORMAL);
3107 				break;
3108 			case MADV_SEQUENTIAL:
3109 				vm_map_entry_set_behavior(entry,
3110 				    MAP_ENTRY_BEHAV_SEQUENTIAL);
3111 				break;
3112 			case MADV_RANDOM:
3113 				vm_map_entry_set_behavior(entry,
3114 				    MAP_ENTRY_BEHAV_RANDOM);
3115 				break;
3116 			case MADV_NOSYNC:
3117 				entry->eflags |= MAP_ENTRY_NOSYNC;
3118 				break;
3119 			case MADV_AUTOSYNC:
3120 				entry->eflags &= ~MAP_ENTRY_NOSYNC;
3121 				break;
3122 			case MADV_NOCORE:
3123 				entry->eflags |= MAP_ENTRY_NOCOREDUMP;
3124 				break;
3125 			case MADV_CORE:
3126 				entry->eflags &= ~MAP_ENTRY_NOCOREDUMP;
3127 				break;
3128 			default:
3129 				break;
3130 			}
3131 			vm_map_try_merge_entries(map, prev_entry, entry);
3132 		}
3133 		vm_map_try_merge_entries(map, prev_entry, entry);
3134 		vm_map_unlock(map);
3135 	} else {
3136 		vm_pindex_t pstart, pend;
3137 
3138 		/*
3139 		 * madvise behaviors that are implemented in the underlying
3140 		 * vm_object.
3141 		 *
3142 		 * Since we don't clip the vm_map_entry, we have to clip
3143 		 * the vm_object pindex and count.
3144 		 */
3145 		if (!vm_map_lookup_entry(map, start, &entry))
3146 			entry = vm_map_entry_succ(entry);
3147 		for (; entry->start < end;
3148 		    entry = vm_map_entry_succ(entry)) {
3149 			vm_offset_t useEnd, useStart;
3150 
3151 			if ((entry->eflags & (MAP_ENTRY_IS_SUB_MAP |
3152 			    MAP_ENTRY_GUARD)) != 0)
3153 				continue;
3154 
3155 			/*
3156 			 * MADV_FREE would otherwise rewind time to
3157 			 * the creation of the shadow object.  Because
3158 			 * we hold the VM map read-locked, neither the
3159 			 * entry's object nor the presence of a
3160 			 * backing object can change.
3161 			 */
3162 			if (behav == MADV_FREE &&
3163 			    entry->object.vm_object != NULL &&
3164 			    entry->object.vm_object->backing_object != NULL)
3165 				continue;
3166 
3167 			pstart = OFF_TO_IDX(entry->offset);
3168 			pend = pstart + atop(entry->end - entry->start);
3169 			useStart = entry->start;
3170 			useEnd = entry->end;
3171 
3172 			if (entry->start < start) {
3173 				pstart += atop(start - entry->start);
3174 				useStart = start;
3175 			}
3176 			if (entry->end > end) {
3177 				pend -= atop(entry->end - end);
3178 				useEnd = end;
3179 			}
3180 
3181 			if (pstart >= pend)
3182 				continue;
3183 
3184 			/*
3185 			 * Perform the pmap_advise() before clearing
3186 			 * PGA_REFERENCED in vm_page_advise().  Otherwise, a
3187 			 * concurrent pmap operation, such as pmap_remove(),
3188 			 * could clear a reference in the pmap and set
3189 			 * PGA_REFERENCED on the page before the pmap_advise()
3190 			 * had completed.  Consequently, the page would appear
3191 			 * referenced based upon an old reference that
3192 			 * occurred before this pmap_advise() ran.
3193 			 */
3194 			if (behav == MADV_DONTNEED || behav == MADV_FREE)
3195 				pmap_advise(map->pmap, useStart, useEnd,
3196 				    behav);
3197 
3198 			vm_object_madvise(entry->object.vm_object, pstart,
3199 			    pend, behav);
3200 
3201 			/*
3202 			 * Pre-populate paging structures in the
3203 			 * WILLNEED case.  For wired entries, the
3204 			 * paging structures are already populated.
3205 			 */
3206 			if (behav == MADV_WILLNEED &&
3207 			    entry->wired_count == 0) {
3208 				vm_map_pmap_enter(map,
3209 				    useStart,
3210 				    entry->protection,
3211 				    entry->object.vm_object,
3212 				    pstart,
3213 				    ptoa(pend - pstart),
3214 				    MAP_PREFAULT_MADVISE
3215 				);
3216 			}
3217 		}
3218 		vm_map_unlock_read(map);
3219 	}
3220 	return (0);
3221 }
3222 
3223 /*
3224  *	vm_map_inherit:
3225  *
3226  *	Sets the inheritance of the specified address
3227  *	range in the target map.  Inheritance
3228  *	affects how the map will be shared with
3229  *	child maps at the time of vmspace_fork.
3230  */
3231 int
3232 vm_map_inherit(vm_map_t map, vm_offset_t start, vm_offset_t end,
3233 	       vm_inherit_t new_inheritance)
3234 {
3235 	vm_map_entry_t entry, lentry, prev_entry, start_entry;
3236 	int rv;
3237 
3238 	switch (new_inheritance) {
3239 	case VM_INHERIT_NONE:
3240 	case VM_INHERIT_COPY:
3241 	case VM_INHERIT_SHARE:
3242 	case VM_INHERIT_ZERO:
3243 		break;
3244 	default:
3245 		return (KERN_INVALID_ARGUMENT);
3246 	}
3247 	if (start == end)
3248 		return (KERN_SUCCESS);
3249 	vm_map_lock(map);
3250 	VM_MAP_RANGE_CHECK(map, start, end);
3251 	rv = vm_map_lookup_clip_start(map, start, &start_entry, &prev_entry);
3252 	if (rv != KERN_SUCCESS)
3253 		goto unlock;
3254 	if (vm_map_lookup_entry(map, end - 1, &lentry)) {
3255 		rv = vm_map_clip_end(map, lentry, end);
3256 		if (rv != KERN_SUCCESS)
3257 			goto unlock;
3258 	}
3259 	if (new_inheritance == VM_INHERIT_COPY) {
3260 		for (entry = start_entry; entry->start < end;
3261 		    prev_entry = entry, entry = vm_map_entry_succ(entry)) {
3262 			if ((entry->eflags & MAP_ENTRY_SPLIT_BOUNDARY_MASK)
3263 			    != 0) {
3264 				rv = KERN_INVALID_ARGUMENT;
3265 				goto unlock;
3266 			}
3267 		}
3268 	}
3269 	for (entry = start_entry; entry->start < end; prev_entry = entry,
3270 	    entry = vm_map_entry_succ(entry)) {
3271 		KASSERT(entry->end <= end, ("non-clipped entry %p end %jx %jx",
3272 		    entry, (uintmax_t)entry->end, (uintmax_t)end));
3273 		if ((entry->eflags & MAP_ENTRY_GUARD) == 0 ||
3274 		    new_inheritance != VM_INHERIT_ZERO)
3275 			entry->inheritance = new_inheritance;
3276 		vm_map_try_merge_entries(map, prev_entry, entry);
3277 	}
3278 	vm_map_try_merge_entries(map, prev_entry, entry);
3279 unlock:
3280 	vm_map_unlock(map);
3281 	return (rv);
3282 }
3283 
3284 /*
3285  *	vm_map_entry_in_transition:
3286  *
3287  *	Release the map lock, and sleep until the entry is no longer in
3288  *	transition.  Awake and acquire the map lock.  If the map changed while
3289  *	another held the lock, lookup a possibly-changed entry at or after the
3290  *	'start' position of the old entry.
3291  */
3292 static vm_map_entry_t
3293 vm_map_entry_in_transition(vm_map_t map, vm_offset_t in_start,
3294     vm_offset_t *io_end, bool holes_ok, vm_map_entry_t in_entry)
3295 {
3296 	vm_map_entry_t entry;
3297 	vm_offset_t start;
3298 	u_int last_timestamp;
3299 
3300 	VM_MAP_ASSERT_LOCKED(map);
3301 	KASSERT((in_entry->eflags & MAP_ENTRY_IN_TRANSITION) != 0,
3302 	    ("not in-tranition map entry %p", in_entry));
3303 	/*
3304 	 * We have not yet clipped the entry.
3305 	 */
3306 	start = MAX(in_start, in_entry->start);
3307 	in_entry->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
3308 	last_timestamp = map->timestamp;
3309 	if (vm_map_unlock_and_wait(map, 0)) {
3310 		/*
3311 		 * Allow interruption of user wiring/unwiring?
3312 		 */
3313 	}
3314 	vm_map_lock(map);
3315 	if (last_timestamp + 1 == map->timestamp)
3316 		return (in_entry);
3317 
3318 	/*
3319 	 * Look again for the entry because the map was modified while it was
3320 	 * unlocked.  Specifically, the entry may have been clipped, merged, or
3321 	 * deleted.
3322 	 */
3323 	if (!vm_map_lookup_entry(map, start, &entry)) {
3324 		if (!holes_ok) {
3325 			*io_end = start;
3326 			return (NULL);
3327 		}
3328 		entry = vm_map_entry_succ(entry);
3329 	}
3330 	return (entry);
3331 }
3332 
3333 /*
3334  *	vm_map_unwire:
3335  *
3336  *	Implements both kernel and user unwiring.
3337  */
3338 int
3339 vm_map_unwire(vm_map_t map, vm_offset_t start, vm_offset_t end,
3340     int flags)
3341 {
3342 	vm_map_entry_t entry, first_entry, next_entry, prev_entry;
3343 	int rv;
3344 	bool holes_ok, need_wakeup, user_unwire;
3345 
3346 	if (start == end)
3347 		return (KERN_SUCCESS);
3348 	holes_ok = (flags & VM_MAP_WIRE_HOLESOK) != 0;
3349 	user_unwire = (flags & VM_MAP_WIRE_USER) != 0;
3350 	vm_map_lock(map);
3351 	VM_MAP_RANGE_CHECK(map, start, end);
3352 	if (!vm_map_lookup_entry(map, start, &first_entry)) {
3353 		if (holes_ok)
3354 			first_entry = vm_map_entry_succ(first_entry);
3355 		else {
3356 			vm_map_unlock(map);
3357 			return (KERN_INVALID_ADDRESS);
3358 		}
3359 	}
3360 	rv = KERN_SUCCESS;
3361 	for (entry = first_entry; entry->start < end; entry = next_entry) {
3362 		if (entry->eflags & MAP_ENTRY_IN_TRANSITION) {
3363 			/*
3364 			 * We have not yet clipped the entry.
3365 			 */
3366 			next_entry = vm_map_entry_in_transition(map, start,
3367 			    &end, holes_ok, entry);
3368 			if (next_entry == NULL) {
3369 				if (entry == first_entry) {
3370 					vm_map_unlock(map);
3371 					return (KERN_INVALID_ADDRESS);
3372 				}
3373 				rv = KERN_INVALID_ADDRESS;
3374 				break;
3375 			}
3376 			first_entry = (entry == first_entry) ?
3377 			    next_entry : NULL;
3378 			continue;
3379 		}
3380 		rv = vm_map_clip_start(map, entry, start);
3381 		if (rv != KERN_SUCCESS)
3382 			break;
3383 		rv = vm_map_clip_end(map, entry, end);
3384 		if (rv != KERN_SUCCESS)
3385 			break;
3386 
3387 		/*
3388 		 * Mark the entry in case the map lock is released.  (See
3389 		 * above.)
3390 		 */
3391 		KASSERT((entry->eflags & MAP_ENTRY_IN_TRANSITION) == 0 &&
3392 		    entry->wiring_thread == NULL,
3393 		    ("owned map entry %p", entry));
3394 		entry->eflags |= MAP_ENTRY_IN_TRANSITION;
3395 		entry->wiring_thread = curthread;
3396 		next_entry = vm_map_entry_succ(entry);
3397 		/*
3398 		 * Check the map for holes in the specified region.
3399 		 * If holes_ok, skip this check.
3400 		 */
3401 		if (!holes_ok &&
3402 		    entry->end < end && next_entry->start > entry->end) {
3403 			end = entry->end;
3404 			rv = KERN_INVALID_ADDRESS;
3405 			break;
3406 		}
3407 		/*
3408 		 * If system unwiring, require that the entry is system wired.
3409 		 */
3410 		if (!user_unwire &&
3411 		    vm_map_entry_system_wired_count(entry) == 0) {
3412 			end = entry->end;
3413 			rv = KERN_INVALID_ARGUMENT;
3414 			break;
3415 		}
3416 	}
3417 	need_wakeup = false;
3418 	if (first_entry == NULL &&
3419 	    !vm_map_lookup_entry(map, start, &first_entry)) {
3420 		KASSERT(holes_ok, ("vm_map_unwire: lookup failed"));
3421 		prev_entry = first_entry;
3422 		entry = vm_map_entry_succ(first_entry);
3423 	} else {
3424 		prev_entry = vm_map_entry_pred(first_entry);
3425 		entry = first_entry;
3426 	}
3427 	for (; entry->start < end;
3428 	    prev_entry = entry, entry = vm_map_entry_succ(entry)) {
3429 		/*
3430 		 * If holes_ok was specified, an empty
3431 		 * space in the unwired region could have been mapped
3432 		 * while the map lock was dropped for draining
3433 		 * MAP_ENTRY_IN_TRANSITION.  Moreover, another thread
3434 		 * could be simultaneously wiring this new mapping
3435 		 * entry.  Detect these cases and skip any entries
3436 		 * marked as in transition by us.
3437 		 */
3438 		if ((entry->eflags & MAP_ENTRY_IN_TRANSITION) == 0 ||
3439 		    entry->wiring_thread != curthread) {
3440 			KASSERT(holes_ok,
3441 			    ("vm_map_unwire: !HOLESOK and new/changed entry"));
3442 			continue;
3443 		}
3444 
3445 		if (rv == KERN_SUCCESS && (!user_unwire ||
3446 		    (entry->eflags & MAP_ENTRY_USER_WIRED))) {
3447 			if (entry->wired_count == 1)
3448 				vm_map_entry_unwire(map, entry);
3449 			else
3450 				entry->wired_count--;
3451 			if (user_unwire)
3452 				entry->eflags &= ~MAP_ENTRY_USER_WIRED;
3453 		}
3454 		KASSERT((entry->eflags & MAP_ENTRY_IN_TRANSITION) != 0,
3455 		    ("vm_map_unwire: in-transition flag missing %p", entry));
3456 		KASSERT(entry->wiring_thread == curthread,
3457 		    ("vm_map_unwire: alien wire %p", entry));
3458 		entry->eflags &= ~MAP_ENTRY_IN_TRANSITION;
3459 		entry->wiring_thread = NULL;
3460 		if (entry->eflags & MAP_ENTRY_NEEDS_WAKEUP) {
3461 			entry->eflags &= ~MAP_ENTRY_NEEDS_WAKEUP;
3462 			need_wakeup = true;
3463 		}
3464 		vm_map_try_merge_entries(map, prev_entry, entry);
3465 	}
3466 	vm_map_try_merge_entries(map, prev_entry, entry);
3467 	vm_map_unlock(map);
3468 	if (need_wakeup)
3469 		vm_map_wakeup(map);
3470 	return (rv);
3471 }
3472 
3473 static void
3474 vm_map_wire_user_count_sub(u_long npages)
3475 {
3476 
3477 	atomic_subtract_long(&vm_user_wire_count, npages);
3478 }
3479 
3480 static bool
3481 vm_map_wire_user_count_add(u_long npages)
3482 {
3483 	u_long wired;
3484 
3485 	wired = vm_user_wire_count;
3486 	do {
3487 		if (npages + wired > vm_page_max_user_wired)
3488 			return (false);
3489 	} while (!atomic_fcmpset_long(&vm_user_wire_count, &wired,
3490 	    npages + wired));
3491 
3492 	return (true);
3493 }
3494 
3495 /*
3496  *	vm_map_wire_entry_failure:
3497  *
3498  *	Handle a wiring failure on the given entry.
3499  *
3500  *	The map should be locked.
3501  */
3502 static void
3503 vm_map_wire_entry_failure(vm_map_t map, vm_map_entry_t entry,
3504     vm_offset_t failed_addr)
3505 {
3506 
3507 	VM_MAP_ASSERT_LOCKED(map);
3508 	KASSERT((entry->eflags & MAP_ENTRY_IN_TRANSITION) != 0 &&
3509 	    entry->wired_count == 1,
3510 	    ("vm_map_wire_entry_failure: entry %p isn't being wired", entry));
3511 	KASSERT(failed_addr < entry->end,
3512 	    ("vm_map_wire_entry_failure: entry %p was fully wired", entry));
3513 
3514 	/*
3515 	 * If any pages at the start of this entry were successfully wired,
3516 	 * then unwire them.
3517 	 */
3518 	if (failed_addr > entry->start) {
3519 		pmap_unwire(map->pmap, entry->start, failed_addr);
3520 		vm_object_unwire(entry->object.vm_object, entry->offset,
3521 		    failed_addr - entry->start, PQ_ACTIVE);
3522 	}
3523 
3524 	/*
3525 	 * Assign an out-of-range value to represent the failure to wire this
3526 	 * entry.
3527 	 */
3528 	entry->wired_count = -1;
3529 }
3530 
3531 int
3532 vm_map_wire(vm_map_t map, vm_offset_t start, vm_offset_t end, int flags)
3533 {
3534 	int rv;
3535 
3536 	vm_map_lock(map);
3537 	rv = vm_map_wire_locked(map, start, end, flags);
3538 	vm_map_unlock(map);
3539 	return (rv);
3540 }
3541 
3542 /*
3543  *	vm_map_wire_locked:
3544  *
3545  *	Implements both kernel and user wiring.  Returns with the map locked,
3546  *	the map lock may be dropped.
3547  */
3548 int
3549 vm_map_wire_locked(vm_map_t map, vm_offset_t start, vm_offset_t end, int flags)
3550 {
3551 	vm_map_entry_t entry, first_entry, next_entry, prev_entry;
3552 	vm_offset_t faddr, saved_end, saved_start;
3553 	u_long incr, npages;
3554 	u_int bidx, last_timestamp;
3555 	int rv;
3556 	bool holes_ok, need_wakeup, user_wire;
3557 	vm_prot_t prot;
3558 
3559 	VM_MAP_ASSERT_LOCKED(map);
3560 
3561 	if (start == end)
3562 		return (KERN_SUCCESS);
3563 	prot = 0;
3564 	if (flags & VM_MAP_WIRE_WRITE)
3565 		prot |= VM_PROT_WRITE;
3566 	holes_ok = (flags & VM_MAP_WIRE_HOLESOK) != 0;
3567 	user_wire = (flags & VM_MAP_WIRE_USER) != 0;
3568 	VM_MAP_RANGE_CHECK(map, start, end);
3569 	if (!vm_map_lookup_entry(map, start, &first_entry)) {
3570 		if (holes_ok)
3571 			first_entry = vm_map_entry_succ(first_entry);
3572 		else
3573 			return (KERN_INVALID_ADDRESS);
3574 	}
3575 	for (entry = first_entry; entry->start < end; entry = next_entry) {
3576 		if (entry->eflags & MAP_ENTRY_IN_TRANSITION) {
3577 			/*
3578 			 * We have not yet clipped the entry.
3579 			 */
3580 			next_entry = vm_map_entry_in_transition(map, start,
3581 			    &end, holes_ok, entry);
3582 			if (next_entry == NULL) {
3583 				if (entry == first_entry)
3584 					return (KERN_INVALID_ADDRESS);
3585 				rv = KERN_INVALID_ADDRESS;
3586 				goto done;
3587 			}
3588 			first_entry = (entry == first_entry) ?
3589 			    next_entry : NULL;
3590 			continue;
3591 		}
3592 		rv = vm_map_clip_start(map, entry, start);
3593 		if (rv != KERN_SUCCESS)
3594 			goto done;
3595 		rv = vm_map_clip_end(map, entry, end);
3596 		if (rv != KERN_SUCCESS)
3597 			goto done;
3598 
3599 		/*
3600 		 * Mark the entry in case the map lock is released.  (See
3601 		 * above.)
3602 		 */
3603 		KASSERT((entry->eflags & MAP_ENTRY_IN_TRANSITION) == 0 &&
3604 		    entry->wiring_thread == NULL,
3605 		    ("owned map entry %p", entry));
3606 		entry->eflags |= MAP_ENTRY_IN_TRANSITION;
3607 		entry->wiring_thread = curthread;
3608 		if ((entry->protection & (VM_PROT_READ | VM_PROT_EXECUTE)) == 0
3609 		    || (entry->protection & prot) != prot) {
3610 			entry->eflags |= MAP_ENTRY_WIRE_SKIPPED;
3611 			if (!holes_ok) {
3612 				end = entry->end;
3613 				rv = KERN_INVALID_ADDRESS;
3614 				goto done;
3615 			}
3616 		} else if (entry->wired_count == 0) {
3617 			entry->wired_count++;
3618 
3619 			npages = atop(entry->end - entry->start);
3620 			if (user_wire && !vm_map_wire_user_count_add(npages)) {
3621 				vm_map_wire_entry_failure(map, entry,
3622 				    entry->start);
3623 				end = entry->end;
3624 				rv = KERN_RESOURCE_SHORTAGE;
3625 				goto done;
3626 			}
3627 
3628 			/*
3629 			 * Release the map lock, relying on the in-transition
3630 			 * mark.  Mark the map busy for fork.
3631 			 */
3632 			saved_start = entry->start;
3633 			saved_end = entry->end;
3634 			last_timestamp = map->timestamp;
3635 			bidx = MAP_ENTRY_SPLIT_BOUNDARY_INDEX(entry);
3636 			incr =  pagesizes[bidx];
3637 			vm_map_busy(map);
3638 			vm_map_unlock(map);
3639 
3640 			for (faddr = saved_start; faddr < saved_end;
3641 			    faddr += incr) {
3642 				/*
3643 				 * Simulate a fault to get the page and enter
3644 				 * it into the physical map.
3645 				 */
3646 				rv = vm_fault(map, faddr, VM_PROT_NONE,
3647 				    VM_FAULT_WIRE, NULL);
3648 				if (rv != KERN_SUCCESS)
3649 					break;
3650 			}
3651 			vm_map_lock(map);
3652 			vm_map_unbusy(map);
3653 			if (last_timestamp + 1 != map->timestamp) {
3654 				/*
3655 				 * Look again for the entry because the map was
3656 				 * modified while it was unlocked.  The entry
3657 				 * may have been clipped, but NOT merged or
3658 				 * deleted.
3659 				 */
3660 				if (!vm_map_lookup_entry(map, saved_start,
3661 				    &next_entry))
3662 					KASSERT(false,
3663 					    ("vm_map_wire: lookup failed"));
3664 				first_entry = (entry == first_entry) ?
3665 				    next_entry : NULL;
3666 				for (entry = next_entry; entry->end < saved_end;
3667 				    entry = vm_map_entry_succ(entry)) {
3668 					/*
3669 					 * In case of failure, handle entries
3670 					 * that were not fully wired here;
3671 					 * fully wired entries are handled
3672 					 * later.
3673 					 */
3674 					if (rv != KERN_SUCCESS &&
3675 					    faddr < entry->end)
3676 						vm_map_wire_entry_failure(map,
3677 						    entry, faddr);
3678 				}
3679 			}
3680 			if (rv != KERN_SUCCESS) {
3681 				vm_map_wire_entry_failure(map, entry, faddr);
3682 				if (user_wire)
3683 					vm_map_wire_user_count_sub(npages);
3684 				end = entry->end;
3685 				goto done;
3686 			}
3687 		} else if (!user_wire ||
3688 			   (entry->eflags & MAP_ENTRY_USER_WIRED) == 0) {
3689 			entry->wired_count++;
3690 		}
3691 		/*
3692 		 * Check the map for holes in the specified region.
3693 		 * If holes_ok was specified, skip this check.
3694 		 */
3695 		next_entry = vm_map_entry_succ(entry);
3696 		if (!holes_ok &&
3697 		    entry->end < end && next_entry->start > entry->end) {
3698 			end = entry->end;
3699 			rv = KERN_INVALID_ADDRESS;
3700 			goto done;
3701 		}
3702 	}
3703 	rv = KERN_SUCCESS;
3704 done:
3705 	need_wakeup = false;
3706 	if (first_entry == NULL &&
3707 	    !vm_map_lookup_entry(map, start, &first_entry)) {
3708 		KASSERT(holes_ok, ("vm_map_wire: lookup failed"));
3709 		prev_entry = first_entry;
3710 		entry = vm_map_entry_succ(first_entry);
3711 	} else {
3712 		prev_entry = vm_map_entry_pred(first_entry);
3713 		entry = first_entry;
3714 	}
3715 	for (; entry->start < end;
3716 	    prev_entry = entry, entry = vm_map_entry_succ(entry)) {
3717 		/*
3718 		 * If holes_ok was specified, an empty
3719 		 * space in the unwired region could have been mapped
3720 		 * while the map lock was dropped for faulting in the
3721 		 * pages or draining MAP_ENTRY_IN_TRANSITION.
3722 		 * Moreover, another thread could be simultaneously
3723 		 * wiring this new mapping entry.  Detect these cases
3724 		 * and skip any entries marked as in transition not by us.
3725 		 *
3726 		 * Another way to get an entry not marked with
3727 		 * MAP_ENTRY_IN_TRANSITION is after failed clipping,
3728 		 * which set rv to KERN_INVALID_ARGUMENT.
3729 		 */
3730 		if ((entry->eflags & MAP_ENTRY_IN_TRANSITION) == 0 ||
3731 		    entry->wiring_thread != curthread) {
3732 			KASSERT(holes_ok || rv == KERN_INVALID_ARGUMENT,
3733 			    ("vm_map_wire: !HOLESOK and new/changed entry"));
3734 			continue;
3735 		}
3736 
3737 		if ((entry->eflags & MAP_ENTRY_WIRE_SKIPPED) != 0) {
3738 			/* do nothing */
3739 		} else if (rv == KERN_SUCCESS) {
3740 			if (user_wire)
3741 				entry->eflags |= MAP_ENTRY_USER_WIRED;
3742 		} else if (entry->wired_count == -1) {
3743 			/*
3744 			 * Wiring failed on this entry.  Thus, unwiring is
3745 			 * unnecessary.
3746 			 */
3747 			entry->wired_count = 0;
3748 		} else if (!user_wire ||
3749 		    (entry->eflags & MAP_ENTRY_USER_WIRED) == 0) {
3750 			/*
3751 			 * Undo the wiring.  Wiring succeeded on this entry
3752 			 * but failed on a later entry.
3753 			 */
3754 			if (entry->wired_count == 1) {
3755 				vm_map_entry_unwire(map, entry);
3756 				if (user_wire)
3757 					vm_map_wire_user_count_sub(
3758 					    atop(entry->end - entry->start));
3759 			} else
3760 				entry->wired_count--;
3761 		}
3762 		KASSERT((entry->eflags & MAP_ENTRY_IN_TRANSITION) != 0,
3763 		    ("vm_map_wire: in-transition flag missing %p", entry));
3764 		KASSERT(entry->wiring_thread == curthread,
3765 		    ("vm_map_wire: alien wire %p", entry));
3766 		entry->eflags &= ~(MAP_ENTRY_IN_TRANSITION |
3767 		    MAP_ENTRY_WIRE_SKIPPED);
3768 		entry->wiring_thread = NULL;
3769 		if (entry->eflags & MAP_ENTRY_NEEDS_WAKEUP) {
3770 			entry->eflags &= ~MAP_ENTRY_NEEDS_WAKEUP;
3771 			need_wakeup = true;
3772 		}
3773 		vm_map_try_merge_entries(map, prev_entry, entry);
3774 	}
3775 	vm_map_try_merge_entries(map, prev_entry, entry);
3776 	if (need_wakeup)
3777 		vm_map_wakeup(map);
3778 	return (rv);
3779 }
3780 
3781 /*
3782  * vm_map_sync
3783  *
3784  * Push any dirty cached pages in the address range to their pager.
3785  * If syncio is TRUE, dirty pages are written synchronously.
3786  * If invalidate is TRUE, any cached pages are freed as well.
3787  *
3788  * If the size of the region from start to end is zero, we are
3789  * supposed to flush all modified pages within the region containing
3790  * start.  Unfortunately, a region can be split or coalesced with
3791  * neighboring regions, making it difficult to determine what the
3792  * original region was.  Therefore, we approximate this requirement by
3793  * flushing the current region containing start.
3794  *
3795  * Returns an error if any part of the specified range is not mapped.
3796  */
3797 int
3798 vm_map_sync(
3799 	vm_map_t map,
3800 	vm_offset_t start,
3801 	vm_offset_t end,
3802 	boolean_t syncio,
3803 	boolean_t invalidate)
3804 {
3805 	vm_map_entry_t entry, first_entry, next_entry;
3806 	vm_size_t size;
3807 	vm_object_t object;
3808 	vm_ooffset_t offset;
3809 	unsigned int last_timestamp;
3810 	int bdry_idx;
3811 	boolean_t failed;
3812 
3813 	vm_map_lock_read(map);
3814 	VM_MAP_RANGE_CHECK(map, start, end);
3815 	if (!vm_map_lookup_entry(map, start, &first_entry)) {
3816 		vm_map_unlock_read(map);
3817 		return (KERN_INVALID_ADDRESS);
3818 	} else if (start == end) {
3819 		start = first_entry->start;
3820 		end = first_entry->end;
3821 	}
3822 
3823 	/*
3824 	 * Make a first pass to check for user-wired memory, holes,
3825 	 * and partial invalidation of largepage mappings.
3826 	 */
3827 	for (entry = first_entry; entry->start < end; entry = next_entry) {
3828 		if (invalidate) {
3829 			if ((entry->eflags & MAP_ENTRY_USER_WIRED) != 0) {
3830 				vm_map_unlock_read(map);
3831 				return (KERN_INVALID_ARGUMENT);
3832 			}
3833 			bdry_idx = MAP_ENTRY_SPLIT_BOUNDARY_INDEX(entry);
3834 			if (bdry_idx != 0 &&
3835 			    ((start & (pagesizes[bdry_idx] - 1)) != 0 ||
3836 			    (end & (pagesizes[bdry_idx] - 1)) != 0)) {
3837 				vm_map_unlock_read(map);
3838 				return (KERN_INVALID_ARGUMENT);
3839 			}
3840 		}
3841 		next_entry = vm_map_entry_succ(entry);
3842 		if (end > entry->end &&
3843 		    entry->end != next_entry->start) {
3844 			vm_map_unlock_read(map);
3845 			return (KERN_INVALID_ADDRESS);
3846 		}
3847 	}
3848 
3849 	if (invalidate)
3850 		pmap_remove(map->pmap, start, end);
3851 	failed = FALSE;
3852 
3853 	/*
3854 	 * Make a second pass, cleaning/uncaching pages from the indicated
3855 	 * objects as we go.
3856 	 */
3857 	for (entry = first_entry; entry->start < end;) {
3858 		offset = entry->offset + (start - entry->start);
3859 		size = (end <= entry->end ? end : entry->end) - start;
3860 		if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) != 0) {
3861 			vm_map_t smap;
3862 			vm_map_entry_t tentry;
3863 			vm_size_t tsize;
3864 
3865 			smap = entry->object.sub_map;
3866 			vm_map_lock_read(smap);
3867 			(void) vm_map_lookup_entry(smap, offset, &tentry);
3868 			tsize = tentry->end - offset;
3869 			if (tsize < size)
3870 				size = tsize;
3871 			object = tentry->object.vm_object;
3872 			offset = tentry->offset + (offset - tentry->start);
3873 			vm_map_unlock_read(smap);
3874 		} else {
3875 			object = entry->object.vm_object;
3876 		}
3877 		vm_object_reference(object);
3878 		last_timestamp = map->timestamp;
3879 		vm_map_unlock_read(map);
3880 		if (!vm_object_sync(object, offset, size, syncio, invalidate))
3881 			failed = TRUE;
3882 		start += size;
3883 		vm_object_deallocate(object);
3884 		vm_map_lock_read(map);
3885 		if (last_timestamp == map->timestamp ||
3886 		    !vm_map_lookup_entry(map, start, &entry))
3887 			entry = vm_map_entry_succ(entry);
3888 	}
3889 
3890 	vm_map_unlock_read(map);
3891 	return (failed ? KERN_FAILURE : KERN_SUCCESS);
3892 }
3893 
3894 /*
3895  *	vm_map_entry_unwire:	[ internal use only ]
3896  *
3897  *	Make the region specified by this entry pageable.
3898  *
3899  *	The map in question should be locked.
3900  *	[This is the reason for this routine's existence.]
3901  */
3902 static void
3903 vm_map_entry_unwire(vm_map_t map, vm_map_entry_t entry)
3904 {
3905 	vm_size_t size;
3906 
3907 	VM_MAP_ASSERT_LOCKED(map);
3908 	KASSERT(entry->wired_count > 0,
3909 	    ("vm_map_entry_unwire: entry %p isn't wired", entry));
3910 
3911 	size = entry->end - entry->start;
3912 	if ((entry->eflags & MAP_ENTRY_USER_WIRED) != 0)
3913 		vm_map_wire_user_count_sub(atop(size));
3914 	pmap_unwire(map->pmap, entry->start, entry->end);
3915 	vm_object_unwire(entry->object.vm_object, entry->offset, size,
3916 	    PQ_ACTIVE);
3917 	entry->wired_count = 0;
3918 }
3919 
3920 static void
3921 vm_map_entry_deallocate(vm_map_entry_t entry, boolean_t system_map)
3922 {
3923 
3924 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0)
3925 		vm_object_deallocate(entry->object.vm_object);
3926 	uma_zfree(system_map ? kmapentzone : mapentzone, entry);
3927 }
3928 
3929 /*
3930  *	vm_map_entry_delete:	[ internal use only ]
3931  *
3932  *	Deallocate the given entry from the target map.
3933  */
3934 static void
3935 vm_map_entry_delete(vm_map_t map, vm_map_entry_t entry)
3936 {
3937 	vm_object_t object;
3938 	vm_pindex_t offidxstart, offidxend, size1;
3939 	vm_size_t size;
3940 
3941 	vm_map_entry_unlink(map, entry, UNLINK_MERGE_NONE);
3942 	object = entry->object.vm_object;
3943 
3944 	if ((entry->eflags & MAP_ENTRY_GUARD) != 0) {
3945 		MPASS(entry->cred == NULL);
3946 		MPASS((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0);
3947 		MPASS(object == NULL);
3948 		vm_map_entry_deallocate(entry, map->system_map);
3949 		return;
3950 	}
3951 
3952 	size = entry->end - entry->start;
3953 	map->size -= size;
3954 
3955 	if (entry->cred != NULL) {
3956 		swap_release_by_cred(size, entry->cred);
3957 		crfree(entry->cred);
3958 	}
3959 
3960 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) != 0 || object == NULL) {
3961 		entry->object.vm_object = NULL;
3962 	} else if ((object->flags & OBJ_ANON) != 0 ||
3963 	    object == kernel_object) {
3964 		KASSERT(entry->cred == NULL || object->cred == NULL ||
3965 		    (entry->eflags & MAP_ENTRY_NEEDS_COPY),
3966 		    ("OVERCOMMIT vm_map_entry_delete: both cred %p", entry));
3967 		offidxstart = OFF_TO_IDX(entry->offset);
3968 		offidxend = offidxstart + atop(size);
3969 		VM_OBJECT_WLOCK(object);
3970 		if (object->ref_count != 1 &&
3971 		    ((object->flags & OBJ_ONEMAPPING) != 0 ||
3972 		    object == kernel_object)) {
3973 			vm_object_collapse(object);
3974 
3975 			/*
3976 			 * The option OBJPR_NOTMAPPED can be passed here
3977 			 * because vm_map_delete() already performed
3978 			 * pmap_remove() on the only mapping to this range
3979 			 * of pages.
3980 			 */
3981 			vm_object_page_remove(object, offidxstart, offidxend,
3982 			    OBJPR_NOTMAPPED);
3983 			if (offidxend >= object->size &&
3984 			    offidxstart < object->size) {
3985 				size1 = object->size;
3986 				object->size = offidxstart;
3987 				if (object->cred != NULL) {
3988 					size1 -= object->size;
3989 					KASSERT(object->charge >= ptoa(size1),
3990 					    ("object %p charge < 0", object));
3991 					swap_release_by_cred(ptoa(size1),
3992 					    object->cred);
3993 					object->charge -= ptoa(size1);
3994 				}
3995 			}
3996 		}
3997 		VM_OBJECT_WUNLOCK(object);
3998 	}
3999 	if (map->system_map)
4000 		vm_map_entry_deallocate(entry, TRUE);
4001 	else {
4002 		entry->defer_next = curthread->td_map_def_user;
4003 		curthread->td_map_def_user = entry;
4004 	}
4005 }
4006 
4007 /*
4008  *	vm_map_delete:	[ internal use only ]
4009  *
4010  *	Deallocates the given address range from the target
4011  *	map.
4012  */
4013 int
4014 vm_map_delete(vm_map_t map, vm_offset_t start, vm_offset_t end)
4015 {
4016 	vm_map_entry_t entry, next_entry, scratch_entry;
4017 	int rv;
4018 
4019 	VM_MAP_ASSERT_LOCKED(map);
4020 
4021 	if (start == end)
4022 		return (KERN_SUCCESS);
4023 
4024 	/*
4025 	 * Find the start of the region, and clip it.
4026 	 * Step through all entries in this region.
4027 	 */
4028 	rv = vm_map_lookup_clip_start(map, start, &entry, &scratch_entry);
4029 	if (rv != KERN_SUCCESS)
4030 		return (rv);
4031 	for (; entry->start < end; entry = next_entry) {
4032 		/*
4033 		 * Wait for wiring or unwiring of an entry to complete.
4034 		 * Also wait for any system wirings to disappear on
4035 		 * user maps.
4036 		 */
4037 		if ((entry->eflags & MAP_ENTRY_IN_TRANSITION) != 0 ||
4038 		    (vm_map_pmap(map) != kernel_pmap &&
4039 		    vm_map_entry_system_wired_count(entry) != 0)) {
4040 			unsigned int last_timestamp;
4041 			vm_offset_t saved_start;
4042 
4043 			saved_start = entry->start;
4044 			entry->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
4045 			last_timestamp = map->timestamp;
4046 			(void) vm_map_unlock_and_wait(map, 0);
4047 			vm_map_lock(map);
4048 			if (last_timestamp + 1 != map->timestamp) {
4049 				/*
4050 				 * Look again for the entry because the map was
4051 				 * modified while it was unlocked.
4052 				 * Specifically, the entry may have been
4053 				 * clipped, merged, or deleted.
4054 				 */
4055 				rv = vm_map_lookup_clip_start(map, saved_start,
4056 				    &next_entry, &scratch_entry);
4057 				if (rv != KERN_SUCCESS)
4058 					break;
4059 			} else
4060 				next_entry = entry;
4061 			continue;
4062 		}
4063 
4064 		/* XXXKIB or delete to the upper superpage boundary ? */
4065 		rv = vm_map_clip_end(map, entry, end);
4066 		if (rv != KERN_SUCCESS)
4067 			break;
4068 		next_entry = vm_map_entry_succ(entry);
4069 
4070 		/*
4071 		 * Unwire before removing addresses from the pmap; otherwise,
4072 		 * unwiring will put the entries back in the pmap.
4073 		 */
4074 		if (entry->wired_count != 0)
4075 			vm_map_entry_unwire(map, entry);
4076 
4077 		/*
4078 		 * Remove mappings for the pages, but only if the
4079 		 * mappings could exist.  For instance, it does not
4080 		 * make sense to call pmap_remove() for guard entries.
4081 		 */
4082 		if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) != 0 ||
4083 		    entry->object.vm_object != NULL)
4084 			pmap_map_delete(map->pmap, entry->start, entry->end);
4085 
4086 		/*
4087 		 * Delete the entry only after removing all pmap
4088 		 * entries pointing to its pages.  (Otherwise, its
4089 		 * page frames may be reallocated, and any modify bits
4090 		 * will be set in the wrong object!)
4091 		 */
4092 		vm_map_entry_delete(map, entry);
4093 	}
4094 	return (rv);
4095 }
4096 
4097 /*
4098  *	vm_map_remove:
4099  *
4100  *	Remove the given address range from the target map.
4101  *	This is the exported form of vm_map_delete.
4102  */
4103 int
4104 vm_map_remove(vm_map_t map, vm_offset_t start, vm_offset_t end)
4105 {
4106 	int result;
4107 
4108 	vm_map_lock(map);
4109 	VM_MAP_RANGE_CHECK(map, start, end);
4110 	result = vm_map_delete(map, start, end);
4111 	vm_map_unlock(map);
4112 	return (result);
4113 }
4114 
4115 /*
4116  *	vm_map_check_protection:
4117  *
4118  *	Assert that the target map allows the specified privilege on the
4119  *	entire address region given.  The entire region must be allocated.
4120  *
4121  *	WARNING!  This code does not and should not check whether the
4122  *	contents of the region is accessible.  For example a smaller file
4123  *	might be mapped into a larger address space.
4124  *
4125  *	NOTE!  This code is also called by munmap().
4126  *
4127  *	The map must be locked.  A read lock is sufficient.
4128  */
4129 boolean_t
4130 vm_map_check_protection(vm_map_t map, vm_offset_t start, vm_offset_t end,
4131 			vm_prot_t protection)
4132 {
4133 	vm_map_entry_t entry;
4134 	vm_map_entry_t tmp_entry;
4135 
4136 	if (!vm_map_lookup_entry(map, start, &tmp_entry))
4137 		return (FALSE);
4138 	entry = tmp_entry;
4139 
4140 	while (start < end) {
4141 		/*
4142 		 * No holes allowed!
4143 		 */
4144 		if (start < entry->start)
4145 			return (FALSE);
4146 		/*
4147 		 * Check protection associated with entry.
4148 		 */
4149 		if ((entry->protection & protection) != protection)
4150 			return (FALSE);
4151 		/* go to next entry */
4152 		start = entry->end;
4153 		entry = vm_map_entry_succ(entry);
4154 	}
4155 	return (TRUE);
4156 }
4157 
4158 /*
4159  *
4160  *	vm_map_copy_swap_object:
4161  *
4162  *	Copies a swap-backed object from an existing map entry to a
4163  *	new one.  Carries forward the swap charge.  May change the
4164  *	src object on return.
4165  */
4166 static void
4167 vm_map_copy_swap_object(vm_map_entry_t src_entry, vm_map_entry_t dst_entry,
4168     vm_offset_t size, vm_ooffset_t *fork_charge)
4169 {
4170 	vm_object_t src_object;
4171 	struct ucred *cred;
4172 	int charged;
4173 
4174 	src_object = src_entry->object.vm_object;
4175 	charged = ENTRY_CHARGED(src_entry);
4176 	if ((src_object->flags & OBJ_ANON) != 0) {
4177 		VM_OBJECT_WLOCK(src_object);
4178 		vm_object_collapse(src_object);
4179 		if ((src_object->flags & OBJ_ONEMAPPING) != 0) {
4180 			vm_object_split(src_entry);
4181 			src_object = src_entry->object.vm_object;
4182 		}
4183 		vm_object_reference_locked(src_object);
4184 		vm_object_clear_flag(src_object, OBJ_ONEMAPPING);
4185 		VM_OBJECT_WUNLOCK(src_object);
4186 	} else
4187 		vm_object_reference(src_object);
4188 	if (src_entry->cred != NULL &&
4189 	    !(src_entry->eflags & MAP_ENTRY_NEEDS_COPY)) {
4190 		KASSERT(src_object->cred == NULL,
4191 		    ("OVERCOMMIT: vm_map_copy_anon_entry: cred %p",
4192 		     src_object));
4193 		src_object->cred = src_entry->cred;
4194 		src_object->charge = size;
4195 	}
4196 	dst_entry->object.vm_object = src_object;
4197 	if (charged) {
4198 		cred = curthread->td_ucred;
4199 		crhold(cred);
4200 		dst_entry->cred = cred;
4201 		*fork_charge += size;
4202 		if (!(src_entry->eflags & MAP_ENTRY_NEEDS_COPY)) {
4203 			crhold(cred);
4204 			src_entry->cred = cred;
4205 			*fork_charge += size;
4206 		}
4207 	}
4208 }
4209 
4210 /*
4211  *	vm_map_copy_entry:
4212  *
4213  *	Copies the contents of the source entry to the destination
4214  *	entry.  The entries *must* be aligned properly.
4215  */
4216 static void
4217 vm_map_copy_entry(
4218 	vm_map_t src_map,
4219 	vm_map_t dst_map,
4220 	vm_map_entry_t src_entry,
4221 	vm_map_entry_t dst_entry,
4222 	vm_ooffset_t *fork_charge)
4223 {
4224 	vm_object_t src_object;
4225 	vm_map_entry_t fake_entry;
4226 	vm_offset_t size;
4227 
4228 	VM_MAP_ASSERT_LOCKED(dst_map);
4229 
4230 	if ((dst_entry->eflags|src_entry->eflags) & MAP_ENTRY_IS_SUB_MAP)
4231 		return;
4232 
4233 	if (src_entry->wired_count == 0 ||
4234 	    (src_entry->protection & VM_PROT_WRITE) == 0) {
4235 		/*
4236 		 * If the source entry is marked needs_copy, it is already
4237 		 * write-protected.
4238 		 */
4239 		if ((src_entry->eflags & MAP_ENTRY_NEEDS_COPY) == 0 &&
4240 		    (src_entry->protection & VM_PROT_WRITE) != 0) {
4241 			pmap_protect(src_map->pmap,
4242 			    src_entry->start,
4243 			    src_entry->end,
4244 			    src_entry->protection & ~VM_PROT_WRITE);
4245 		}
4246 
4247 		/*
4248 		 * Make a copy of the object.
4249 		 */
4250 		size = src_entry->end - src_entry->start;
4251 		if ((src_object = src_entry->object.vm_object) != NULL) {
4252 			if ((src_object->flags & OBJ_SWAP) != 0) {
4253 				vm_map_copy_swap_object(src_entry, dst_entry,
4254 				    size, fork_charge);
4255 				/* May have split/collapsed, reload obj. */
4256 				src_object = src_entry->object.vm_object;
4257 			} else {
4258 				vm_object_reference(src_object);
4259 				dst_entry->object.vm_object = src_object;
4260 			}
4261 			src_entry->eflags |= MAP_ENTRY_COW |
4262 			    MAP_ENTRY_NEEDS_COPY;
4263 			dst_entry->eflags |= MAP_ENTRY_COW |
4264 			    MAP_ENTRY_NEEDS_COPY;
4265 			dst_entry->offset = src_entry->offset;
4266 			if (src_entry->eflags & MAP_ENTRY_WRITECNT) {
4267 				/*
4268 				 * MAP_ENTRY_WRITECNT cannot
4269 				 * indicate write reference from
4270 				 * src_entry, since the entry is
4271 				 * marked as needs copy.  Allocate a
4272 				 * fake entry that is used to
4273 				 * decrement object->un_pager writecount
4274 				 * at the appropriate time.  Attach
4275 				 * fake_entry to the deferred list.
4276 				 */
4277 				fake_entry = vm_map_entry_create(dst_map);
4278 				fake_entry->eflags = MAP_ENTRY_WRITECNT;
4279 				src_entry->eflags &= ~MAP_ENTRY_WRITECNT;
4280 				vm_object_reference(src_object);
4281 				fake_entry->object.vm_object = src_object;
4282 				fake_entry->start = src_entry->start;
4283 				fake_entry->end = src_entry->end;
4284 				fake_entry->defer_next =
4285 				    curthread->td_map_def_user;
4286 				curthread->td_map_def_user = fake_entry;
4287 			}
4288 
4289 			pmap_copy(dst_map->pmap, src_map->pmap,
4290 			    dst_entry->start, dst_entry->end - dst_entry->start,
4291 			    src_entry->start);
4292 		} else {
4293 			dst_entry->object.vm_object = NULL;
4294 			if ((dst_entry->eflags & MAP_ENTRY_GUARD) == 0)
4295 				dst_entry->offset = 0;
4296 			if (src_entry->cred != NULL) {
4297 				dst_entry->cred = curthread->td_ucred;
4298 				crhold(dst_entry->cred);
4299 				*fork_charge += size;
4300 			}
4301 		}
4302 	} else {
4303 		/*
4304 		 * We don't want to make writeable wired pages copy-on-write.
4305 		 * Immediately copy these pages into the new map by simulating
4306 		 * page faults.  The new pages are pageable.
4307 		 */
4308 		vm_fault_copy_entry(dst_map, src_map, dst_entry, src_entry,
4309 		    fork_charge);
4310 	}
4311 }
4312 
4313 /*
4314  * vmspace_map_entry_forked:
4315  * Update the newly-forked vmspace each time a map entry is inherited
4316  * or copied.  The values for vm_dsize and vm_tsize are approximate
4317  * (and mostly-obsolete ideas in the face of mmap(2) et al.)
4318  */
4319 static void
4320 vmspace_map_entry_forked(const struct vmspace *vm1, struct vmspace *vm2,
4321     vm_map_entry_t entry)
4322 {
4323 	vm_size_t entrysize;
4324 	vm_offset_t newend;
4325 
4326 	if ((entry->eflags & MAP_ENTRY_GUARD) != 0)
4327 		return;
4328 	entrysize = entry->end - entry->start;
4329 	vm2->vm_map.size += entrysize;
4330 	if (entry->eflags & (MAP_ENTRY_GROWS_DOWN | MAP_ENTRY_GROWS_UP)) {
4331 		vm2->vm_ssize += btoc(entrysize);
4332 	} else if (entry->start >= (vm_offset_t)vm1->vm_daddr &&
4333 	    entry->start < (vm_offset_t)vm1->vm_daddr + ctob(vm1->vm_dsize)) {
4334 		newend = MIN(entry->end,
4335 		    (vm_offset_t)vm1->vm_daddr + ctob(vm1->vm_dsize));
4336 		vm2->vm_dsize += btoc(newend - entry->start);
4337 	} else if (entry->start >= (vm_offset_t)vm1->vm_taddr &&
4338 	    entry->start < (vm_offset_t)vm1->vm_taddr + ctob(vm1->vm_tsize)) {
4339 		newend = MIN(entry->end,
4340 		    (vm_offset_t)vm1->vm_taddr + ctob(vm1->vm_tsize));
4341 		vm2->vm_tsize += btoc(newend - entry->start);
4342 	}
4343 }
4344 
4345 /*
4346  * vmspace_fork:
4347  * Create a new process vmspace structure and vm_map
4348  * based on those of an existing process.  The new map
4349  * is based on the old map, according to the inheritance
4350  * values on the regions in that map.
4351  *
4352  * XXX It might be worth coalescing the entries added to the new vmspace.
4353  *
4354  * The source map must not be locked.
4355  */
4356 struct vmspace *
4357 vmspace_fork(struct vmspace *vm1, vm_ooffset_t *fork_charge)
4358 {
4359 	struct vmspace *vm2;
4360 	vm_map_t new_map, old_map;
4361 	vm_map_entry_t new_entry, old_entry;
4362 	vm_object_t object;
4363 	int error, locked __diagused;
4364 	vm_inherit_t inh;
4365 
4366 	old_map = &vm1->vm_map;
4367 	/* Copy immutable fields of vm1 to vm2. */
4368 	vm2 = vmspace_alloc(vm_map_min(old_map), vm_map_max(old_map),
4369 	    pmap_pinit);
4370 	if (vm2 == NULL)
4371 		return (NULL);
4372 
4373 	vm2->vm_taddr = vm1->vm_taddr;
4374 	vm2->vm_daddr = vm1->vm_daddr;
4375 	vm2->vm_maxsaddr = vm1->vm_maxsaddr;
4376 	vm2->vm_stacktop = vm1->vm_stacktop;
4377 	vm2->vm_shp_base = vm1->vm_shp_base;
4378 	vm_map_lock(old_map);
4379 	if (old_map->busy)
4380 		vm_map_wait_busy(old_map);
4381 	new_map = &vm2->vm_map;
4382 	locked = vm_map_trylock(new_map); /* trylock to silence WITNESS */
4383 	KASSERT(locked, ("vmspace_fork: lock failed"));
4384 
4385 	error = pmap_vmspace_copy(new_map->pmap, old_map->pmap);
4386 	if (error != 0) {
4387 		sx_xunlock(&old_map->lock);
4388 		sx_xunlock(&new_map->lock);
4389 		vm_map_process_deferred();
4390 		vmspace_free(vm2);
4391 		return (NULL);
4392 	}
4393 
4394 	new_map->anon_loc = old_map->anon_loc;
4395 	new_map->flags |= old_map->flags & (MAP_ASLR | MAP_ASLR_IGNSTART |
4396 	    MAP_ASLR_STACK | MAP_WXORX);
4397 
4398 	VM_MAP_ENTRY_FOREACH(old_entry, old_map) {
4399 		if ((old_entry->eflags & MAP_ENTRY_IS_SUB_MAP) != 0)
4400 			panic("vm_map_fork: encountered a submap");
4401 
4402 		inh = old_entry->inheritance;
4403 		if ((old_entry->eflags & MAP_ENTRY_GUARD) != 0 &&
4404 		    inh != VM_INHERIT_NONE)
4405 			inh = VM_INHERIT_COPY;
4406 
4407 		switch (inh) {
4408 		case VM_INHERIT_NONE:
4409 			break;
4410 
4411 		case VM_INHERIT_SHARE:
4412 			/*
4413 			 * Clone the entry, creating the shared object if
4414 			 * necessary.
4415 			 */
4416 			object = old_entry->object.vm_object;
4417 			if (object == NULL) {
4418 				vm_map_entry_back(old_entry);
4419 				object = old_entry->object.vm_object;
4420 			}
4421 
4422 			/*
4423 			 * Add the reference before calling vm_object_shadow
4424 			 * to insure that a shadow object is created.
4425 			 */
4426 			vm_object_reference(object);
4427 			if (old_entry->eflags & MAP_ENTRY_NEEDS_COPY) {
4428 				vm_object_shadow(&old_entry->object.vm_object,
4429 				    &old_entry->offset,
4430 				    old_entry->end - old_entry->start,
4431 				    old_entry->cred,
4432 				    /* Transfer the second reference too. */
4433 				    true);
4434 				old_entry->eflags &= ~MAP_ENTRY_NEEDS_COPY;
4435 				old_entry->cred = NULL;
4436 
4437 				/*
4438 				 * As in vm_map_merged_neighbor_dispose(),
4439 				 * the vnode lock will not be acquired in
4440 				 * this call to vm_object_deallocate().
4441 				 */
4442 				vm_object_deallocate(object);
4443 				object = old_entry->object.vm_object;
4444 			} else {
4445 				VM_OBJECT_WLOCK(object);
4446 				vm_object_clear_flag(object, OBJ_ONEMAPPING);
4447 				if (old_entry->cred != NULL) {
4448 					KASSERT(object->cred == NULL,
4449 					    ("vmspace_fork both cred"));
4450 					object->cred = old_entry->cred;
4451 					object->charge = old_entry->end -
4452 					    old_entry->start;
4453 					old_entry->cred = NULL;
4454 				}
4455 
4456 				/*
4457 				 * Assert the correct state of the vnode
4458 				 * v_writecount while the object is locked, to
4459 				 * not relock it later for the assertion
4460 				 * correctness.
4461 				 */
4462 				if (old_entry->eflags & MAP_ENTRY_WRITECNT &&
4463 				    object->type == OBJT_VNODE) {
4464 					KASSERT(((struct vnode *)object->
4465 					    handle)->v_writecount > 0,
4466 					    ("vmspace_fork: v_writecount %p",
4467 					    object));
4468 					KASSERT(object->un_pager.vnp.
4469 					    writemappings > 0,
4470 					    ("vmspace_fork: vnp.writecount %p",
4471 					    object));
4472 				}
4473 				VM_OBJECT_WUNLOCK(object);
4474 			}
4475 
4476 			/*
4477 			 * Clone the entry, referencing the shared object.
4478 			 */
4479 			new_entry = vm_map_entry_create(new_map);
4480 			*new_entry = *old_entry;
4481 			new_entry->eflags &= ~(MAP_ENTRY_USER_WIRED |
4482 			    MAP_ENTRY_IN_TRANSITION);
4483 			new_entry->wiring_thread = NULL;
4484 			new_entry->wired_count = 0;
4485 			if (new_entry->eflags & MAP_ENTRY_WRITECNT) {
4486 				vm_pager_update_writecount(object,
4487 				    new_entry->start, new_entry->end);
4488 			}
4489 			vm_map_entry_set_vnode_text(new_entry, true);
4490 
4491 			/*
4492 			 * Insert the entry into the new map -- we know we're
4493 			 * inserting at the end of the new map.
4494 			 */
4495 			vm_map_entry_link(new_map, new_entry);
4496 			vmspace_map_entry_forked(vm1, vm2, new_entry);
4497 
4498 			/*
4499 			 * Update the physical map
4500 			 */
4501 			pmap_copy(new_map->pmap, old_map->pmap,
4502 			    new_entry->start,
4503 			    (old_entry->end - old_entry->start),
4504 			    old_entry->start);
4505 			break;
4506 
4507 		case VM_INHERIT_COPY:
4508 			/*
4509 			 * Clone the entry and link into the map.
4510 			 */
4511 			new_entry = vm_map_entry_create(new_map);
4512 			*new_entry = *old_entry;
4513 			/*
4514 			 * Copied entry is COW over the old object.
4515 			 */
4516 			new_entry->eflags &= ~(MAP_ENTRY_USER_WIRED |
4517 			    MAP_ENTRY_IN_TRANSITION | MAP_ENTRY_WRITECNT);
4518 			new_entry->wiring_thread = NULL;
4519 			new_entry->wired_count = 0;
4520 			new_entry->object.vm_object = NULL;
4521 			new_entry->cred = NULL;
4522 			vm_map_entry_link(new_map, new_entry);
4523 			vmspace_map_entry_forked(vm1, vm2, new_entry);
4524 			vm_map_copy_entry(old_map, new_map, old_entry,
4525 			    new_entry, fork_charge);
4526 			vm_map_entry_set_vnode_text(new_entry, true);
4527 			break;
4528 
4529 		case VM_INHERIT_ZERO:
4530 			/*
4531 			 * Create a new anonymous mapping entry modelled from
4532 			 * the old one.
4533 			 */
4534 			new_entry = vm_map_entry_create(new_map);
4535 			memset(new_entry, 0, sizeof(*new_entry));
4536 
4537 			new_entry->start = old_entry->start;
4538 			new_entry->end = old_entry->end;
4539 			new_entry->eflags = old_entry->eflags &
4540 			    ~(MAP_ENTRY_USER_WIRED | MAP_ENTRY_IN_TRANSITION |
4541 			    MAP_ENTRY_WRITECNT | MAP_ENTRY_VN_EXEC |
4542 			    MAP_ENTRY_SPLIT_BOUNDARY_MASK);
4543 			new_entry->protection = old_entry->protection;
4544 			new_entry->max_protection = old_entry->max_protection;
4545 			new_entry->inheritance = VM_INHERIT_ZERO;
4546 
4547 			vm_map_entry_link(new_map, new_entry);
4548 			vmspace_map_entry_forked(vm1, vm2, new_entry);
4549 
4550 			new_entry->cred = curthread->td_ucred;
4551 			crhold(new_entry->cred);
4552 			*fork_charge += (new_entry->end - new_entry->start);
4553 
4554 			break;
4555 		}
4556 	}
4557 	/*
4558 	 * Use inlined vm_map_unlock() to postpone handling the deferred
4559 	 * map entries, which cannot be done until both old_map and
4560 	 * new_map locks are released.
4561 	 */
4562 	sx_xunlock(&old_map->lock);
4563 	sx_xunlock(&new_map->lock);
4564 	vm_map_process_deferred();
4565 
4566 	return (vm2);
4567 }
4568 
4569 /*
4570  * Create a process's stack for exec_new_vmspace().  This function is never
4571  * asked to wire the newly created stack.
4572  */
4573 int
4574 vm_map_stack(vm_map_t map, vm_offset_t addrbos, vm_size_t max_ssize,
4575     vm_prot_t prot, vm_prot_t max, int cow)
4576 {
4577 	vm_size_t growsize, init_ssize;
4578 	rlim_t vmemlim;
4579 	int rv;
4580 
4581 	MPASS((map->flags & MAP_WIREFUTURE) == 0);
4582 	growsize = sgrowsiz;
4583 	init_ssize = (max_ssize < growsize) ? max_ssize : growsize;
4584 	vm_map_lock(map);
4585 	vmemlim = lim_cur(curthread, RLIMIT_VMEM);
4586 	/* If we would blow our VMEM resource limit, no go */
4587 	if (map->size + init_ssize > vmemlim) {
4588 		rv = KERN_NO_SPACE;
4589 		goto out;
4590 	}
4591 	rv = vm_map_stack_locked(map, addrbos, max_ssize, growsize, prot,
4592 	    max, cow);
4593 out:
4594 	vm_map_unlock(map);
4595 	return (rv);
4596 }
4597 
4598 static int stack_guard_page = 1;
4599 SYSCTL_INT(_security_bsd, OID_AUTO, stack_guard_page, CTLFLAG_RWTUN,
4600     &stack_guard_page, 0,
4601     "Specifies the number of guard pages for a stack that grows");
4602 
4603 static int
4604 vm_map_stack_locked(vm_map_t map, vm_offset_t addrbos, vm_size_t max_ssize,
4605     vm_size_t growsize, vm_prot_t prot, vm_prot_t max, int cow)
4606 {
4607 	vm_map_entry_t gap_entry, new_entry, prev_entry;
4608 	vm_offset_t bot, gap_bot, gap_top, top;
4609 	vm_size_t init_ssize, sgp;
4610 	int orient, rv;
4611 
4612 	/*
4613 	 * The stack orientation is piggybacked with the cow argument.
4614 	 * Extract it into orient and mask the cow argument so that we
4615 	 * don't pass it around further.
4616 	 */
4617 	orient = cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP);
4618 	KASSERT(orient != 0, ("No stack grow direction"));
4619 	KASSERT(orient != (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP),
4620 	    ("bi-dir stack"));
4621 
4622 	if (max_ssize == 0 ||
4623 	    !vm_map_range_valid(map, addrbos, addrbos + max_ssize))
4624 		return (KERN_INVALID_ADDRESS);
4625 	sgp = ((curproc->p_flag2 & P2_STKGAP_DISABLE) != 0 ||
4626 	    (curproc->p_fctl0 & NT_FREEBSD_FCTL_STKGAP_DISABLE) != 0) ? 0 :
4627 	    (vm_size_t)stack_guard_page * PAGE_SIZE;
4628 	if (sgp >= max_ssize)
4629 		return (KERN_INVALID_ARGUMENT);
4630 
4631 	init_ssize = growsize;
4632 	if (max_ssize < init_ssize + sgp)
4633 		init_ssize = max_ssize - sgp;
4634 
4635 	/* If addr is already mapped, no go */
4636 	if (vm_map_lookup_entry(map, addrbos, &prev_entry))
4637 		return (KERN_NO_SPACE);
4638 
4639 	/*
4640 	 * If we can't accommodate max_ssize in the current mapping, no go.
4641 	 */
4642 	if (vm_map_entry_succ(prev_entry)->start < addrbos + max_ssize)
4643 		return (KERN_NO_SPACE);
4644 
4645 	/*
4646 	 * We initially map a stack of only init_ssize.  We will grow as
4647 	 * needed later.  Depending on the orientation of the stack (i.e.
4648 	 * the grow direction) we either map at the top of the range, the
4649 	 * bottom of the range or in the middle.
4650 	 *
4651 	 * Note: we would normally expect prot and max to be VM_PROT_ALL,
4652 	 * and cow to be 0.  Possibly we should eliminate these as input
4653 	 * parameters, and just pass these values here in the insert call.
4654 	 */
4655 	if (orient == MAP_STACK_GROWS_DOWN) {
4656 		bot = addrbos + max_ssize - init_ssize;
4657 		top = bot + init_ssize;
4658 		gap_bot = addrbos;
4659 		gap_top = bot;
4660 	} else /* if (orient == MAP_STACK_GROWS_UP) */ {
4661 		bot = addrbos;
4662 		top = bot + init_ssize;
4663 		gap_bot = top;
4664 		gap_top = addrbos + max_ssize;
4665 	}
4666 	rv = vm_map_insert1(map, NULL, 0, bot, top, prot, max, cow,
4667 	    &new_entry);
4668 	if (rv != KERN_SUCCESS)
4669 		return (rv);
4670 	KASSERT(new_entry->end == top || new_entry->start == bot,
4671 	    ("Bad entry start/end for new stack entry"));
4672 	KASSERT((orient & MAP_STACK_GROWS_DOWN) == 0 ||
4673 	    (new_entry->eflags & MAP_ENTRY_GROWS_DOWN) != 0,
4674 	    ("new entry lacks MAP_ENTRY_GROWS_DOWN"));
4675 	KASSERT((orient & MAP_STACK_GROWS_UP) == 0 ||
4676 	    (new_entry->eflags & MAP_ENTRY_GROWS_UP) != 0,
4677 	    ("new entry lacks MAP_ENTRY_GROWS_UP"));
4678 	if (gap_bot == gap_top)
4679 		return (KERN_SUCCESS);
4680 	rv = vm_map_insert1(map, NULL, 0, gap_bot, gap_top, VM_PROT_NONE,
4681 	    VM_PROT_NONE, MAP_CREATE_GUARD | (orient == MAP_STACK_GROWS_DOWN ?
4682 	    MAP_CREATE_STACK_GAP_DN : MAP_CREATE_STACK_GAP_UP), &gap_entry);
4683 	if (rv == KERN_SUCCESS) {
4684 		KASSERT((gap_entry->eflags & MAP_ENTRY_GUARD) != 0,
4685 		    ("entry %p not gap %#x", gap_entry, gap_entry->eflags));
4686 		KASSERT((gap_entry->eflags & (MAP_ENTRY_STACK_GAP_DN |
4687 		    MAP_ENTRY_STACK_GAP_UP)) != 0,
4688 		    ("entry %p not stack gap %#x", gap_entry,
4689 		    gap_entry->eflags));
4690 
4691 		/*
4692 		 * Gap can never successfully handle a fault, so
4693 		 * read-ahead logic is never used for it.  Re-use
4694 		 * next_read of the gap entry to store
4695 		 * stack_guard_page for vm_map_growstack().
4696 		 * Similarly, since a gap cannot have a backing object,
4697 		 * store the original stack protections in the
4698 		 * object offset.
4699 		 */
4700 		gap_entry->next_read = sgp;
4701 		gap_entry->offset = prot | PROT_MAX(max);
4702 	} else {
4703 		(void)vm_map_delete(map, bot, top);
4704 	}
4705 	return (rv);
4706 }
4707 
4708 /*
4709  * Attempts to grow a vm stack entry.  Returns KERN_SUCCESS if we
4710  * successfully grow the stack.
4711  */
4712 static int
4713 vm_map_growstack(vm_map_t map, vm_offset_t addr, vm_map_entry_t gap_entry)
4714 {
4715 	vm_map_entry_t stack_entry;
4716 	struct proc *p;
4717 	struct vmspace *vm;
4718 	struct ucred *cred;
4719 	vm_offset_t gap_end, gap_start, grow_start;
4720 	vm_size_t grow_amount, guard, max_grow, sgp;
4721 	vm_prot_t prot, max;
4722 	rlim_t lmemlim, stacklim, vmemlim;
4723 	int rv, rv1 __diagused;
4724 	bool gap_deleted, grow_down, is_procstack;
4725 #ifdef notyet
4726 	uint64_t limit;
4727 #endif
4728 #ifdef RACCT
4729 	int error __diagused;
4730 #endif
4731 
4732 	p = curproc;
4733 	vm = p->p_vmspace;
4734 
4735 	/*
4736 	 * Disallow stack growth when the access is performed by a
4737 	 * debugger or AIO daemon.  The reason is that the wrong
4738 	 * resource limits are applied.
4739 	 */
4740 	if (p != initproc && (map != &p->p_vmspace->vm_map ||
4741 	    p->p_textvp == NULL))
4742 		return (KERN_FAILURE);
4743 
4744 	MPASS(!map->system_map);
4745 
4746 	lmemlim = lim_cur(curthread, RLIMIT_MEMLOCK);
4747 	stacklim = lim_cur(curthread, RLIMIT_STACK);
4748 	vmemlim = lim_cur(curthread, RLIMIT_VMEM);
4749 retry:
4750 	/* If addr is not in a hole for a stack grow area, no need to grow. */
4751 	if (gap_entry == NULL && !vm_map_lookup_entry(map, addr, &gap_entry))
4752 		return (KERN_FAILURE);
4753 	if ((gap_entry->eflags & MAP_ENTRY_GUARD) == 0)
4754 		return (KERN_SUCCESS);
4755 	if ((gap_entry->eflags & MAP_ENTRY_STACK_GAP_DN) != 0) {
4756 		stack_entry = vm_map_entry_succ(gap_entry);
4757 		if ((stack_entry->eflags & MAP_ENTRY_GROWS_DOWN) == 0 ||
4758 		    stack_entry->start != gap_entry->end)
4759 			return (KERN_FAILURE);
4760 		grow_amount = round_page(stack_entry->start - addr);
4761 		grow_down = true;
4762 	} else if ((gap_entry->eflags & MAP_ENTRY_STACK_GAP_UP) != 0) {
4763 		stack_entry = vm_map_entry_pred(gap_entry);
4764 		if ((stack_entry->eflags & MAP_ENTRY_GROWS_UP) == 0 ||
4765 		    stack_entry->end != gap_entry->start)
4766 			return (KERN_FAILURE);
4767 		grow_amount = round_page(addr + 1 - stack_entry->end);
4768 		grow_down = false;
4769 	} else {
4770 		return (KERN_FAILURE);
4771 	}
4772 	guard = ((curproc->p_flag2 & P2_STKGAP_DISABLE) != 0 ||
4773 	    (curproc->p_fctl0 & NT_FREEBSD_FCTL_STKGAP_DISABLE) != 0) ? 0 :
4774 	    gap_entry->next_read;
4775 	max_grow = gap_entry->end - gap_entry->start;
4776 	if (guard > max_grow)
4777 		return (KERN_NO_SPACE);
4778 	max_grow -= guard;
4779 	if (grow_amount > max_grow)
4780 		return (KERN_NO_SPACE);
4781 
4782 	/*
4783 	 * If this is the main process stack, see if we're over the stack
4784 	 * limit.
4785 	 */
4786 	is_procstack = addr >= (vm_offset_t)vm->vm_maxsaddr &&
4787 	    addr < (vm_offset_t)vm->vm_stacktop;
4788 	if (is_procstack && (ctob(vm->vm_ssize) + grow_amount > stacklim))
4789 		return (KERN_NO_SPACE);
4790 
4791 #ifdef RACCT
4792 	if (racct_enable) {
4793 		PROC_LOCK(p);
4794 		if (is_procstack && racct_set(p, RACCT_STACK,
4795 		    ctob(vm->vm_ssize) + grow_amount)) {
4796 			PROC_UNLOCK(p);
4797 			return (KERN_NO_SPACE);
4798 		}
4799 		PROC_UNLOCK(p);
4800 	}
4801 #endif
4802 
4803 	grow_amount = roundup(grow_amount, sgrowsiz);
4804 	if (grow_amount > max_grow)
4805 		grow_amount = max_grow;
4806 	if (is_procstack && (ctob(vm->vm_ssize) + grow_amount > stacklim)) {
4807 		grow_amount = trunc_page((vm_size_t)stacklim) -
4808 		    ctob(vm->vm_ssize);
4809 	}
4810 
4811 #ifdef notyet
4812 	PROC_LOCK(p);
4813 	limit = racct_get_available(p, RACCT_STACK);
4814 	PROC_UNLOCK(p);
4815 	if (is_procstack && (ctob(vm->vm_ssize) + grow_amount > limit))
4816 		grow_amount = limit - ctob(vm->vm_ssize);
4817 #endif
4818 
4819 	if (!old_mlock && (map->flags & MAP_WIREFUTURE) != 0) {
4820 		if (ptoa(pmap_wired_count(map->pmap)) + grow_amount > lmemlim) {
4821 			rv = KERN_NO_SPACE;
4822 			goto out;
4823 		}
4824 #ifdef RACCT
4825 		if (racct_enable) {
4826 			PROC_LOCK(p);
4827 			if (racct_set(p, RACCT_MEMLOCK,
4828 			    ptoa(pmap_wired_count(map->pmap)) + grow_amount)) {
4829 				PROC_UNLOCK(p);
4830 				rv = KERN_NO_SPACE;
4831 				goto out;
4832 			}
4833 			PROC_UNLOCK(p);
4834 		}
4835 #endif
4836 	}
4837 
4838 	/* If we would blow our VMEM resource limit, no go */
4839 	if (map->size + grow_amount > vmemlim) {
4840 		rv = KERN_NO_SPACE;
4841 		goto out;
4842 	}
4843 #ifdef RACCT
4844 	if (racct_enable) {
4845 		PROC_LOCK(p);
4846 		if (racct_set(p, RACCT_VMEM, map->size + grow_amount)) {
4847 			PROC_UNLOCK(p);
4848 			rv = KERN_NO_SPACE;
4849 			goto out;
4850 		}
4851 		PROC_UNLOCK(p);
4852 	}
4853 #endif
4854 
4855 	if (vm_map_lock_upgrade(map)) {
4856 		gap_entry = NULL;
4857 		vm_map_lock_read(map);
4858 		goto retry;
4859 	}
4860 
4861 	if (grow_down) {
4862 		/*
4863 		 * The gap_entry "offset" field is overloaded.  See
4864 		 * vm_map_stack_locked().
4865 		 */
4866 		prot = PROT_EXTRACT(gap_entry->offset);
4867 		max = PROT_MAX_EXTRACT(gap_entry->offset);
4868 		sgp = gap_entry->next_read;
4869 
4870 		grow_start = gap_entry->end - grow_amount;
4871 		if (gap_entry->start + grow_amount == gap_entry->end) {
4872 			gap_start = gap_entry->start;
4873 			gap_end = gap_entry->end;
4874 			vm_map_entry_delete(map, gap_entry);
4875 			gap_deleted = true;
4876 		} else {
4877 			MPASS(gap_entry->start < gap_entry->end - grow_amount);
4878 			vm_map_entry_resize(map, gap_entry, -grow_amount);
4879 			gap_deleted = false;
4880 		}
4881 		rv = vm_map_insert(map, NULL, 0, grow_start,
4882 		    grow_start + grow_amount, prot, max, MAP_STACK_GROWS_DOWN);
4883 		if (rv != KERN_SUCCESS) {
4884 			if (gap_deleted) {
4885 				rv1 = vm_map_insert1(map, NULL, 0, gap_start,
4886 				    gap_end, VM_PROT_NONE, VM_PROT_NONE,
4887 				    MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN,
4888 				    &gap_entry);
4889 				MPASS(rv1 == KERN_SUCCESS);
4890 				gap_entry->next_read = sgp;
4891 				gap_entry->offset = prot | PROT_MAX(max);
4892 			} else
4893 				vm_map_entry_resize(map, gap_entry,
4894 				    grow_amount);
4895 		}
4896 	} else {
4897 		grow_start = stack_entry->end;
4898 		cred = stack_entry->cred;
4899 		if (cred == NULL && stack_entry->object.vm_object != NULL)
4900 			cred = stack_entry->object.vm_object->cred;
4901 		if (cred != NULL && !swap_reserve_by_cred(grow_amount, cred))
4902 			rv = KERN_NO_SPACE;
4903 		/* Grow the underlying object if applicable. */
4904 		else if (stack_entry->object.vm_object == NULL ||
4905 		    vm_object_coalesce(stack_entry->object.vm_object,
4906 		    stack_entry->offset,
4907 		    (vm_size_t)(stack_entry->end - stack_entry->start),
4908 		    grow_amount, cred != NULL)) {
4909 			if (gap_entry->start + grow_amount == gap_entry->end) {
4910 				vm_map_entry_delete(map, gap_entry);
4911 				vm_map_entry_resize(map, stack_entry,
4912 				    grow_amount);
4913 			} else {
4914 				gap_entry->start += grow_amount;
4915 				stack_entry->end += grow_amount;
4916 			}
4917 			map->size += grow_amount;
4918 			rv = KERN_SUCCESS;
4919 		} else
4920 			rv = KERN_FAILURE;
4921 	}
4922 	if (rv == KERN_SUCCESS && is_procstack)
4923 		vm->vm_ssize += btoc(grow_amount);
4924 
4925 	/*
4926 	 * Heed the MAP_WIREFUTURE flag if it was set for this process.
4927 	 */
4928 	if (rv == KERN_SUCCESS && (map->flags & MAP_WIREFUTURE) != 0) {
4929 		rv = vm_map_wire_locked(map, grow_start,
4930 		    grow_start + grow_amount,
4931 		    VM_MAP_WIRE_USER | VM_MAP_WIRE_NOHOLES);
4932 	}
4933 	vm_map_lock_downgrade(map);
4934 
4935 out:
4936 #ifdef RACCT
4937 	if (racct_enable && rv != KERN_SUCCESS) {
4938 		PROC_LOCK(p);
4939 		error = racct_set(p, RACCT_VMEM, map->size);
4940 		KASSERT(error == 0, ("decreasing RACCT_VMEM failed"));
4941 		if (!old_mlock) {
4942 			error = racct_set(p, RACCT_MEMLOCK,
4943 			    ptoa(pmap_wired_count(map->pmap)));
4944 			KASSERT(error == 0, ("decreasing RACCT_MEMLOCK failed"));
4945 		}
4946 	    	error = racct_set(p, RACCT_STACK, ctob(vm->vm_ssize));
4947 		KASSERT(error == 0, ("decreasing RACCT_STACK failed"));
4948 		PROC_UNLOCK(p);
4949 	}
4950 #endif
4951 
4952 	return (rv);
4953 }
4954 
4955 /*
4956  * Unshare the specified VM space for exec.  If other processes are
4957  * mapped to it, then create a new one.  The new vmspace is null.
4958  */
4959 int
4960 vmspace_exec(struct proc *p, vm_offset_t minuser, vm_offset_t maxuser)
4961 {
4962 	struct vmspace *oldvmspace = p->p_vmspace;
4963 	struct vmspace *newvmspace;
4964 
4965 	KASSERT((curthread->td_pflags & TDP_EXECVMSPC) == 0,
4966 	    ("vmspace_exec recursed"));
4967 	newvmspace = vmspace_alloc(minuser, maxuser, pmap_pinit);
4968 	if (newvmspace == NULL)
4969 		return (ENOMEM);
4970 	newvmspace->vm_swrss = oldvmspace->vm_swrss;
4971 	/*
4972 	 * This code is written like this for prototype purposes.  The
4973 	 * goal is to avoid running down the vmspace here, but let the
4974 	 * other process's that are still using the vmspace to finally
4975 	 * run it down.  Even though there is little or no chance of blocking
4976 	 * here, it is a good idea to keep this form for future mods.
4977 	 */
4978 	PROC_VMSPACE_LOCK(p);
4979 	p->p_vmspace = newvmspace;
4980 	PROC_VMSPACE_UNLOCK(p);
4981 	if (p == curthread->td_proc)
4982 		pmap_activate(curthread);
4983 	curthread->td_pflags |= TDP_EXECVMSPC;
4984 	return (0);
4985 }
4986 
4987 /*
4988  * Unshare the specified VM space for forcing COW.  This
4989  * is called by rfork, for the (RFMEM|RFPROC) == 0 case.
4990  */
4991 int
4992 vmspace_unshare(struct proc *p)
4993 {
4994 	struct vmspace *oldvmspace = p->p_vmspace;
4995 	struct vmspace *newvmspace;
4996 	vm_ooffset_t fork_charge;
4997 
4998 	/*
4999 	 * The caller is responsible for ensuring that the reference count
5000 	 * cannot concurrently transition 1 -> 2.
5001 	 */
5002 	if (refcount_load(&oldvmspace->vm_refcnt) == 1)
5003 		return (0);
5004 	fork_charge = 0;
5005 	newvmspace = vmspace_fork(oldvmspace, &fork_charge);
5006 	if (newvmspace == NULL)
5007 		return (ENOMEM);
5008 	if (!swap_reserve_by_cred(fork_charge, p->p_ucred)) {
5009 		vmspace_free(newvmspace);
5010 		return (ENOMEM);
5011 	}
5012 	PROC_VMSPACE_LOCK(p);
5013 	p->p_vmspace = newvmspace;
5014 	PROC_VMSPACE_UNLOCK(p);
5015 	if (p == curthread->td_proc)
5016 		pmap_activate(curthread);
5017 	vmspace_free(oldvmspace);
5018 	return (0);
5019 }
5020 
5021 /*
5022  *	vm_map_lookup:
5023  *
5024  *	Finds the VM object, offset, and
5025  *	protection for a given virtual address in the
5026  *	specified map, assuming a page fault of the
5027  *	type specified.
5028  *
5029  *	Leaves the map in question locked for read; return
5030  *	values are guaranteed until a vm_map_lookup_done
5031  *	call is performed.  Note that the map argument
5032  *	is in/out; the returned map must be used in
5033  *	the call to vm_map_lookup_done.
5034  *
5035  *	A handle (out_entry) is returned for use in
5036  *	vm_map_lookup_done, to make that fast.
5037  *
5038  *	If a lookup is requested with "write protection"
5039  *	specified, the map may be changed to perform virtual
5040  *	copying operations, although the data referenced will
5041  *	remain the same.
5042  */
5043 int
5044 vm_map_lookup(vm_map_t *var_map,		/* IN/OUT */
5045 	      vm_offset_t vaddr,
5046 	      vm_prot_t fault_typea,
5047 	      vm_map_entry_t *out_entry,	/* OUT */
5048 	      vm_object_t *object,		/* OUT */
5049 	      vm_pindex_t *pindex,		/* OUT */
5050 	      vm_prot_t *out_prot,		/* OUT */
5051 	      boolean_t *wired)			/* OUT */
5052 {
5053 	vm_map_entry_t entry;
5054 	vm_map_t map = *var_map;
5055 	vm_prot_t prot;
5056 	vm_prot_t fault_type;
5057 	vm_object_t eobject;
5058 	vm_size_t size;
5059 	struct ucred *cred;
5060 
5061 RetryLookup:
5062 
5063 	vm_map_lock_read(map);
5064 
5065 RetryLookupLocked:
5066 	/*
5067 	 * Lookup the faulting address.
5068 	 */
5069 	if (!vm_map_lookup_entry(map, vaddr, out_entry)) {
5070 		vm_map_unlock_read(map);
5071 		return (KERN_INVALID_ADDRESS);
5072 	}
5073 
5074 	entry = *out_entry;
5075 
5076 	/*
5077 	 * Handle submaps.
5078 	 */
5079 	if (entry->eflags & MAP_ENTRY_IS_SUB_MAP) {
5080 		vm_map_t old_map = map;
5081 
5082 		*var_map = map = entry->object.sub_map;
5083 		vm_map_unlock_read(old_map);
5084 		goto RetryLookup;
5085 	}
5086 
5087 	/*
5088 	 * Check whether this task is allowed to have this page.
5089 	 */
5090 	prot = entry->protection;
5091 	if ((fault_typea & VM_PROT_FAULT_LOOKUP) != 0) {
5092 		fault_typea &= ~VM_PROT_FAULT_LOOKUP;
5093 		if (prot == VM_PROT_NONE && map != kernel_map &&
5094 		    (entry->eflags & MAP_ENTRY_GUARD) != 0 &&
5095 		    (entry->eflags & (MAP_ENTRY_STACK_GAP_DN |
5096 		    MAP_ENTRY_STACK_GAP_UP)) != 0 &&
5097 		    vm_map_growstack(map, vaddr, entry) == KERN_SUCCESS)
5098 			goto RetryLookupLocked;
5099 	}
5100 	fault_type = fault_typea & VM_PROT_ALL;
5101 	if ((fault_type & prot) != fault_type || prot == VM_PROT_NONE) {
5102 		vm_map_unlock_read(map);
5103 		return (KERN_PROTECTION_FAILURE);
5104 	}
5105 	KASSERT((prot & VM_PROT_WRITE) == 0 || (entry->eflags &
5106 	    (MAP_ENTRY_USER_WIRED | MAP_ENTRY_NEEDS_COPY)) !=
5107 	    (MAP_ENTRY_USER_WIRED | MAP_ENTRY_NEEDS_COPY),
5108 	    ("entry %p flags %x", entry, entry->eflags));
5109 	if ((fault_typea & VM_PROT_COPY) != 0 &&
5110 	    (entry->max_protection & VM_PROT_WRITE) == 0 &&
5111 	    (entry->eflags & MAP_ENTRY_COW) == 0) {
5112 		vm_map_unlock_read(map);
5113 		return (KERN_PROTECTION_FAILURE);
5114 	}
5115 
5116 	/*
5117 	 * If this page is not pageable, we have to get it for all possible
5118 	 * accesses.
5119 	 */
5120 	*wired = (entry->wired_count != 0);
5121 	if (*wired)
5122 		fault_type = entry->protection;
5123 	size = entry->end - entry->start;
5124 
5125 	/*
5126 	 * If the entry was copy-on-write, we either ...
5127 	 */
5128 	if (entry->eflags & MAP_ENTRY_NEEDS_COPY) {
5129 		/*
5130 		 * If we want to write the page, we may as well handle that
5131 		 * now since we've got the map locked.
5132 		 *
5133 		 * If we don't need to write the page, we just demote the
5134 		 * permissions allowed.
5135 		 */
5136 		if ((fault_type & VM_PROT_WRITE) != 0 ||
5137 		    (fault_typea & VM_PROT_COPY) != 0) {
5138 			/*
5139 			 * Make a new object, and place it in the object
5140 			 * chain.  Note that no new references have appeared
5141 			 * -- one just moved from the map to the new
5142 			 * object.
5143 			 */
5144 			if (vm_map_lock_upgrade(map))
5145 				goto RetryLookup;
5146 
5147 			if (entry->cred == NULL) {
5148 				/*
5149 				 * The debugger owner is charged for
5150 				 * the memory.
5151 				 */
5152 				cred = curthread->td_ucred;
5153 				crhold(cred);
5154 				if (!swap_reserve_by_cred(size, cred)) {
5155 					crfree(cred);
5156 					vm_map_unlock(map);
5157 					return (KERN_RESOURCE_SHORTAGE);
5158 				}
5159 				entry->cred = cred;
5160 			}
5161 			eobject = entry->object.vm_object;
5162 			vm_object_shadow(&entry->object.vm_object,
5163 			    &entry->offset, size, entry->cred, false);
5164 			if (eobject == entry->object.vm_object) {
5165 				/*
5166 				 * The object was not shadowed.
5167 				 */
5168 				swap_release_by_cred(size, entry->cred);
5169 				crfree(entry->cred);
5170 			}
5171 			entry->cred = NULL;
5172 			entry->eflags &= ~MAP_ENTRY_NEEDS_COPY;
5173 
5174 			vm_map_lock_downgrade(map);
5175 		} else {
5176 			/*
5177 			 * We're attempting to read a copy-on-write page --
5178 			 * don't allow writes.
5179 			 */
5180 			prot &= ~VM_PROT_WRITE;
5181 		}
5182 	}
5183 
5184 	/*
5185 	 * Create an object if necessary.
5186 	 */
5187 	if (entry->object.vm_object == NULL && !map->system_map) {
5188 		if (vm_map_lock_upgrade(map))
5189 			goto RetryLookup;
5190 		entry->object.vm_object = vm_object_allocate_anon(atop(size),
5191 		    NULL, entry->cred, size);
5192 		entry->offset = 0;
5193 		entry->cred = NULL;
5194 		vm_map_lock_downgrade(map);
5195 	}
5196 
5197 	/*
5198 	 * Return the object/offset from this entry.  If the entry was
5199 	 * copy-on-write or empty, it has been fixed up.
5200 	 */
5201 	*pindex = OFF_TO_IDX((vaddr - entry->start) + entry->offset);
5202 	*object = entry->object.vm_object;
5203 
5204 	*out_prot = prot;
5205 	return (KERN_SUCCESS);
5206 }
5207 
5208 /*
5209  *	vm_map_lookup_locked:
5210  *
5211  *	Lookup the faulting address.  A version of vm_map_lookup that returns
5212  *      KERN_FAILURE instead of blocking on map lock or memory allocation.
5213  */
5214 int
5215 vm_map_lookup_locked(vm_map_t *var_map,		/* IN/OUT */
5216 		     vm_offset_t vaddr,
5217 		     vm_prot_t fault_typea,
5218 		     vm_map_entry_t *out_entry,	/* OUT */
5219 		     vm_object_t *object,	/* OUT */
5220 		     vm_pindex_t *pindex,	/* OUT */
5221 		     vm_prot_t *out_prot,	/* OUT */
5222 		     boolean_t *wired)		/* OUT */
5223 {
5224 	vm_map_entry_t entry;
5225 	vm_map_t map = *var_map;
5226 	vm_prot_t prot;
5227 	vm_prot_t fault_type = fault_typea;
5228 
5229 	/*
5230 	 * Lookup the faulting address.
5231 	 */
5232 	if (!vm_map_lookup_entry(map, vaddr, out_entry))
5233 		return (KERN_INVALID_ADDRESS);
5234 
5235 	entry = *out_entry;
5236 
5237 	/*
5238 	 * Fail if the entry refers to a submap.
5239 	 */
5240 	if (entry->eflags & MAP_ENTRY_IS_SUB_MAP)
5241 		return (KERN_FAILURE);
5242 
5243 	/*
5244 	 * Check whether this task is allowed to have this page.
5245 	 */
5246 	prot = entry->protection;
5247 	fault_type &= VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE;
5248 	if ((fault_type & prot) != fault_type)
5249 		return (KERN_PROTECTION_FAILURE);
5250 
5251 	/*
5252 	 * If this page is not pageable, we have to get it for all possible
5253 	 * accesses.
5254 	 */
5255 	*wired = (entry->wired_count != 0);
5256 	if (*wired)
5257 		fault_type = entry->protection;
5258 
5259 	if (entry->eflags & MAP_ENTRY_NEEDS_COPY) {
5260 		/*
5261 		 * Fail if the entry was copy-on-write for a write fault.
5262 		 */
5263 		if (fault_type & VM_PROT_WRITE)
5264 			return (KERN_FAILURE);
5265 		/*
5266 		 * We're attempting to read a copy-on-write page --
5267 		 * don't allow writes.
5268 		 */
5269 		prot &= ~VM_PROT_WRITE;
5270 	}
5271 
5272 	/*
5273 	 * Fail if an object should be created.
5274 	 */
5275 	if (entry->object.vm_object == NULL && !map->system_map)
5276 		return (KERN_FAILURE);
5277 
5278 	/*
5279 	 * Return the object/offset from this entry.  If the entry was
5280 	 * copy-on-write or empty, it has been fixed up.
5281 	 */
5282 	*pindex = OFF_TO_IDX((vaddr - entry->start) + entry->offset);
5283 	*object = entry->object.vm_object;
5284 
5285 	*out_prot = prot;
5286 	return (KERN_SUCCESS);
5287 }
5288 
5289 /*
5290  *	vm_map_lookup_done:
5291  *
5292  *	Releases locks acquired by a vm_map_lookup
5293  *	(according to the handle returned by that lookup).
5294  */
5295 void
5296 vm_map_lookup_done(vm_map_t map, vm_map_entry_t entry)
5297 {
5298 	/*
5299 	 * Unlock the main-level map
5300 	 */
5301 	vm_map_unlock_read(map);
5302 }
5303 
5304 vm_offset_t
5305 vm_map_max_KBI(const struct vm_map *map)
5306 {
5307 
5308 	return (vm_map_max(map));
5309 }
5310 
5311 vm_offset_t
5312 vm_map_min_KBI(const struct vm_map *map)
5313 {
5314 
5315 	return (vm_map_min(map));
5316 }
5317 
5318 pmap_t
5319 vm_map_pmap_KBI(vm_map_t map)
5320 {
5321 
5322 	return (map->pmap);
5323 }
5324 
5325 bool
5326 vm_map_range_valid_KBI(vm_map_t map, vm_offset_t start, vm_offset_t end)
5327 {
5328 
5329 	return (vm_map_range_valid(map, start, end));
5330 }
5331 
5332 #ifdef INVARIANTS
5333 static void
5334 _vm_map_assert_consistent(vm_map_t map, int check)
5335 {
5336 	vm_map_entry_t entry, prev;
5337 	vm_map_entry_t cur, header, lbound, ubound;
5338 	vm_size_t max_left, max_right;
5339 
5340 #ifdef DIAGNOSTIC
5341 	++map->nupdates;
5342 #endif
5343 	if (enable_vmmap_check != check)
5344 		return;
5345 
5346 	header = prev = &map->header;
5347 	VM_MAP_ENTRY_FOREACH(entry, map) {
5348 		KASSERT(prev->end <= entry->start,
5349 		    ("map %p prev->end = %jx, start = %jx", map,
5350 		    (uintmax_t)prev->end, (uintmax_t)entry->start));
5351 		KASSERT(entry->start < entry->end,
5352 		    ("map %p start = %jx, end = %jx", map,
5353 		    (uintmax_t)entry->start, (uintmax_t)entry->end));
5354 		KASSERT(entry->left == header ||
5355 		    entry->left->start < entry->start,
5356 		    ("map %p left->start = %jx, start = %jx", map,
5357 		    (uintmax_t)entry->left->start, (uintmax_t)entry->start));
5358 		KASSERT(entry->right == header ||
5359 		    entry->start < entry->right->start,
5360 		    ("map %p start = %jx, right->start = %jx", map,
5361 		    (uintmax_t)entry->start, (uintmax_t)entry->right->start));
5362 		cur = map->root;
5363 		lbound = ubound = header;
5364 		for (;;) {
5365 			if (entry->start < cur->start) {
5366 				ubound = cur;
5367 				cur = cur->left;
5368 				KASSERT(cur != lbound,
5369 				    ("map %p cannot find %jx",
5370 				    map, (uintmax_t)entry->start));
5371 			} else if (cur->end <= entry->start) {
5372 				lbound = cur;
5373 				cur = cur->right;
5374 				KASSERT(cur != ubound,
5375 				    ("map %p cannot find %jx",
5376 				    map, (uintmax_t)entry->start));
5377 			} else {
5378 				KASSERT(cur == entry,
5379 				    ("map %p cannot find %jx",
5380 				    map, (uintmax_t)entry->start));
5381 				break;
5382 			}
5383 		}
5384 		max_left = vm_map_entry_max_free_left(entry, lbound);
5385 		max_right = vm_map_entry_max_free_right(entry, ubound);
5386 		KASSERT(entry->max_free == vm_size_max(max_left, max_right),
5387 		    ("map %p max = %jx, max_left = %jx, max_right = %jx", map,
5388 		    (uintmax_t)entry->max_free,
5389 		    (uintmax_t)max_left, (uintmax_t)max_right));
5390 		prev = entry;
5391 	}
5392 	KASSERT(prev->end <= entry->start,
5393 	    ("map %p prev->end = %jx, start = %jx", map,
5394 	    (uintmax_t)prev->end, (uintmax_t)entry->start));
5395 }
5396 #endif
5397 
5398 #include "opt_ddb.h"
5399 #ifdef DDB
5400 #include <sys/kernel.h>
5401 
5402 #include <ddb/ddb.h>
5403 
5404 static void
5405 vm_map_print(vm_map_t map)
5406 {
5407 	vm_map_entry_t entry, prev;
5408 
5409 	db_iprintf("Task map %p: pmap=%p, nentries=%d, version=%u\n",
5410 	    (void *)map,
5411 	    (void *)map->pmap, map->nentries, map->timestamp);
5412 
5413 	db_indent += 2;
5414 	prev = &map->header;
5415 	VM_MAP_ENTRY_FOREACH(entry, map) {
5416 		db_iprintf("map entry %p: start=%p, end=%p, eflags=%#x, \n",
5417 		    (void *)entry, (void *)entry->start, (void *)entry->end,
5418 		    entry->eflags);
5419 		{
5420 			static const char * const inheritance_name[4] =
5421 			{"share", "copy", "none", "donate_copy"};
5422 
5423 			db_iprintf(" prot=%x/%x/%s",
5424 			    entry->protection,
5425 			    entry->max_protection,
5426 			    inheritance_name[(int)(unsigned char)
5427 			    entry->inheritance]);
5428 			if (entry->wired_count != 0)
5429 				db_printf(", wired");
5430 		}
5431 		if (entry->eflags & MAP_ENTRY_IS_SUB_MAP) {
5432 			db_printf(", share=%p, offset=0x%jx\n",
5433 			    (void *)entry->object.sub_map,
5434 			    (uintmax_t)entry->offset);
5435 			if (prev == &map->header ||
5436 			    prev->object.sub_map !=
5437 				entry->object.sub_map) {
5438 				db_indent += 2;
5439 				vm_map_print((vm_map_t)entry->object.sub_map);
5440 				db_indent -= 2;
5441 			}
5442 		} else {
5443 			if (entry->cred != NULL)
5444 				db_printf(", ruid %d", entry->cred->cr_ruid);
5445 			db_printf(", object=%p, offset=0x%jx",
5446 			    (void *)entry->object.vm_object,
5447 			    (uintmax_t)entry->offset);
5448 			if (entry->object.vm_object && entry->object.vm_object->cred)
5449 				db_printf(", obj ruid %d charge %jx",
5450 				    entry->object.vm_object->cred->cr_ruid,
5451 				    (uintmax_t)entry->object.vm_object->charge);
5452 			if (entry->eflags & MAP_ENTRY_COW)
5453 				db_printf(", copy (%s)",
5454 				    (entry->eflags & MAP_ENTRY_NEEDS_COPY) ? "needed" : "done");
5455 			db_printf("\n");
5456 
5457 			if (prev == &map->header ||
5458 			    prev->object.vm_object !=
5459 				entry->object.vm_object) {
5460 				db_indent += 2;
5461 				vm_object_print((db_expr_t)(intptr_t)
5462 						entry->object.vm_object,
5463 						0, 0, (char *)0);
5464 				db_indent -= 2;
5465 			}
5466 		}
5467 		prev = entry;
5468 	}
5469 	db_indent -= 2;
5470 }
5471 
5472 DB_SHOW_COMMAND(map, map)
5473 {
5474 
5475 	if (!have_addr) {
5476 		db_printf("usage: show map <addr>\n");
5477 		return;
5478 	}
5479 	vm_map_print((vm_map_t)addr);
5480 }
5481 
5482 DB_SHOW_COMMAND(procvm, procvm)
5483 {
5484 	struct proc *p;
5485 
5486 	if (have_addr) {
5487 		p = db_lookup_proc(addr);
5488 	} else {
5489 		p = curproc;
5490 	}
5491 
5492 	db_printf("p = %p, vmspace = %p, map = %p, pmap = %p\n",
5493 	    (void *)p, (void *)p->p_vmspace, (void *)&p->p_vmspace->vm_map,
5494 	    (void *)vmspace_pmap(p->p_vmspace));
5495 
5496 	vm_map_print((vm_map_t)&p->p_vmspace->vm_map);
5497 }
5498 
5499 #endif /* DDB */
5500