xref: /netbsd-src/sys/uvm/uvm_map.c (revision bdc22b2e01993381dcefeff2bc9b56ca75a4235c)
1 /*	$NetBSD: uvm_map.c,v 1.354 2018/02/06 09:20:29 mrg Exp $	*/
2 
3 /*
4  * Copyright (c) 1997 Charles D. Cranor and Washington University.
5  * Copyright (c) 1991, 1993, The Regents of the University of California.
6  *
7  * All rights reserved.
8  *
9  * This code is derived from software contributed to Berkeley by
10  * The Mach Operating System project at Carnegie-Mellon University.
11  *
12  * Redistribution and use in source and binary forms, with or without
13  * modification, are permitted provided that the following conditions
14  * are met:
15  * 1. Redistributions of source code must retain the above copyright
16  *    notice, this list of conditions and the following disclaimer.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in the
19  *    documentation and/or other materials provided with the distribution.
20  * 3. Neither the name of the University nor the names of its contributors
21  *    may be used to endorse or promote products derived from this software
22  *    without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  *
36  *	@(#)vm_map.c    8.3 (Berkeley) 1/12/94
37  * from: Id: uvm_map.c,v 1.1.2.27 1998/02/07 01:16:54 chs Exp
38  *
39  *
40  * Copyright (c) 1987, 1990 Carnegie-Mellon University.
41  * All rights reserved.
42  *
43  * Permission to use, copy, modify and distribute this software and
44  * its documentation is hereby granted, provided that both the copyright
45  * notice and this permission notice appear in all copies of the
46  * software, derivative works or modified versions, and any portions
47  * thereof, and that both notices appear in supporting documentation.
48  *
49  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
50  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
51  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
52  *
53  * Carnegie Mellon requests users of this software to return to
54  *
55  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
56  *  School of Computer Science
57  *  Carnegie Mellon University
58  *  Pittsburgh PA 15213-3890
59  *
60  * any improvements or extensions that they make and grant Carnegie the
61  * rights to redistribute these changes.
62  */
63 
64 /*
65  * uvm_map.c: uvm map operations
66  */
67 
68 #include <sys/cdefs.h>
69 __KERNEL_RCSID(0, "$NetBSD: uvm_map.c,v 1.354 2018/02/06 09:20:29 mrg Exp $");
70 
71 #include "opt_ddb.h"
72 #include "opt_pax.h"
73 #include "opt_uvmhist.h"
74 #include "opt_uvm.h"
75 #include "opt_sysv.h"
76 
77 #include <sys/param.h>
78 #include <sys/systm.h>
79 #include <sys/mman.h>
80 #include <sys/proc.h>
81 #include <sys/pool.h>
82 #include <sys/kernel.h>
83 #include <sys/mount.h>
84 #include <sys/pax.h>
85 #include <sys/vnode.h>
86 #include <sys/filedesc.h>
87 #include <sys/lockdebug.h>
88 #include <sys/atomic.h>
89 #include <sys/sysctl.h>
90 #ifndef __USER_VA0_IS_SAFE
91 #include <sys/kauth.h>
92 #include "opt_user_va0_disable_default.h"
93 #endif
94 
95 #include <sys/shm.h>
96 
97 #include <uvm/uvm.h>
98 #include <uvm/uvm_readahead.h>
99 
100 #if defined(DDB) || defined(DEBUGPRINT)
101 #include <uvm/uvm_ddb.h>
102 #endif
103 
104 #ifdef UVMHIST
105 #ifndef UVMHIST_MAPHIST_SIZE
106 #define UVMHIST_MAPHIST_SIZE 100
107 #endif
108 #ifndef UVMHIST_PDHIST_SIZE
109 #define UVMHIST_PDHIST_SIZE 100
110 #endif
111 static struct kern_history_ent maphistbuf[UVMHIST_MAPHIST_SIZE];
112 UVMHIST_DEFINE(maphist) = UVMHIST_INITIALIZER(maphist, maphistbuf);
113 #endif
114 
115 #if !defined(UVMMAP_COUNTERS)
116 
117 #define	UVMMAP_EVCNT_DEFINE(name)	/* nothing */
118 #define UVMMAP_EVCNT_INCR(ev)		/* nothing */
119 #define UVMMAP_EVCNT_DECR(ev)		/* nothing */
120 
121 #else /* defined(UVMMAP_NOCOUNTERS) */
122 
123 #include <sys/evcnt.h>
124 #define	UVMMAP_EVCNT_DEFINE(name) \
125 struct evcnt uvmmap_evcnt_##name = EVCNT_INITIALIZER(EVCNT_TYPE_MISC, NULL, \
126     "uvmmap", #name); \
127 EVCNT_ATTACH_STATIC(uvmmap_evcnt_##name);
128 #define	UVMMAP_EVCNT_INCR(ev)		uvmmap_evcnt_##ev.ev_count++
129 #define	UVMMAP_EVCNT_DECR(ev)		uvmmap_evcnt_##ev.ev_count--
130 
131 #endif /* defined(UVMMAP_NOCOUNTERS) */
132 
133 UVMMAP_EVCNT_DEFINE(ubackmerge)
134 UVMMAP_EVCNT_DEFINE(uforwmerge)
135 UVMMAP_EVCNT_DEFINE(ubimerge)
136 UVMMAP_EVCNT_DEFINE(unomerge)
137 UVMMAP_EVCNT_DEFINE(kbackmerge)
138 UVMMAP_EVCNT_DEFINE(kforwmerge)
139 UVMMAP_EVCNT_DEFINE(kbimerge)
140 UVMMAP_EVCNT_DEFINE(knomerge)
141 UVMMAP_EVCNT_DEFINE(map_call)
142 UVMMAP_EVCNT_DEFINE(mlk_call)
143 UVMMAP_EVCNT_DEFINE(mlk_hint)
144 UVMMAP_EVCNT_DEFINE(mlk_list)
145 UVMMAP_EVCNT_DEFINE(mlk_tree)
146 UVMMAP_EVCNT_DEFINE(mlk_treeloop)
147 UVMMAP_EVCNT_DEFINE(mlk_listloop)
148 
149 const char vmmapbsy[] = "vmmapbsy";
150 
151 /*
152  * cache for vmspace structures.
153  */
154 
155 static struct pool_cache uvm_vmspace_cache;
156 
157 /*
158  * cache for dynamically-allocated map entries.
159  */
160 
161 static struct pool_cache uvm_map_entry_cache;
162 
163 #ifdef PMAP_GROWKERNEL
164 /*
165  * This global represents the end of the kernel virtual address
166  * space.  If we want to exceed this, we must grow the kernel
167  * virtual address space dynamically.
168  *
169  * Note, this variable is locked by kernel_map's lock.
170  */
171 vaddr_t uvm_maxkaddr;
172 #endif
173 
174 #ifndef __USER_VA0_IS_SAFE
175 #ifndef __USER_VA0_DISABLE_DEFAULT
176 #define __USER_VA0_DISABLE_DEFAULT 1
177 #endif
178 #ifdef USER_VA0_DISABLE_DEFAULT /* kernel config option overrides */
179 #undef __USER_VA0_DISABLE_DEFAULT
180 #define __USER_VA0_DISABLE_DEFAULT USER_VA0_DISABLE_DEFAULT
181 #endif
182 int user_va0_disable = __USER_VA0_DISABLE_DEFAULT;
183 #endif
184 
185 /*
186  * macros
187  */
188 
189 /*
190  * UVM_ET_ISCOMPATIBLE: check some requirements for map entry merging
191  */
192 extern struct vm_map *pager_map;
193 
194 #define	UVM_ET_ISCOMPATIBLE(ent, type, uobj, meflags, \
195     prot, maxprot, inh, adv, wire) \
196 	((ent)->etype == (type) && \
197 	(((ent)->flags ^ (meflags)) & (UVM_MAP_NOMERGE)) == 0 && \
198 	(ent)->object.uvm_obj == (uobj) && \
199 	(ent)->protection == (prot) && \
200 	(ent)->max_protection == (maxprot) && \
201 	(ent)->inheritance == (inh) && \
202 	(ent)->advice == (adv) && \
203 	(ent)->wired_count == (wire))
204 
205 /*
206  * uvm_map_entry_link: insert entry into a map
207  *
208  * => map must be locked
209  */
210 #define uvm_map_entry_link(map, after_where, entry) do { \
211 	uvm_mapent_check(entry); \
212 	(map)->nentries++; \
213 	(entry)->prev = (after_where); \
214 	(entry)->next = (after_where)->next; \
215 	(entry)->prev->next = (entry); \
216 	(entry)->next->prev = (entry); \
217 	uvm_rb_insert((map), (entry)); \
218 } while (/*CONSTCOND*/ 0)
219 
220 /*
221  * uvm_map_entry_unlink: remove entry from a map
222  *
223  * => map must be locked
224  */
225 #define uvm_map_entry_unlink(map, entry) do { \
226 	KASSERT((entry) != (map)->first_free); \
227 	KASSERT((entry) != (map)->hint); \
228 	uvm_mapent_check(entry); \
229 	(map)->nentries--; \
230 	(entry)->next->prev = (entry)->prev; \
231 	(entry)->prev->next = (entry)->next; \
232 	uvm_rb_remove((map), (entry)); \
233 } while (/*CONSTCOND*/ 0)
234 
235 /*
236  * SAVE_HINT: saves the specified entry as the hint for future lookups.
237  *
238  * => map need not be locked.
239  */
240 #define SAVE_HINT(map, check, value) do { \
241 	if ((map)->hint == (check)) \
242 		(map)->hint = (value); \
243 } while (/*CONSTCOND*/ 0)
244 
245 /*
246  * clear_hints: ensure that hints don't point to the entry.
247  *
248  * => map must be write-locked.
249  */
250 static void
251 clear_hints(struct vm_map *map, struct vm_map_entry *ent)
252 {
253 
254 	SAVE_HINT(map, ent, ent->prev);
255 	if (map->first_free == ent) {
256 		map->first_free = ent->prev;
257 	}
258 }
259 
260 /*
261  * VM_MAP_RANGE_CHECK: check and correct range
262  *
263  * => map must at least be read locked
264  */
265 
266 #define VM_MAP_RANGE_CHECK(map, start, end) do { \
267 	if (start < vm_map_min(map))		\
268 		start = vm_map_min(map);	\
269 	if (end > vm_map_max(map))		\
270 		end = vm_map_max(map);		\
271 	if (start > end)			\
272 		start = end;			\
273 } while (/*CONSTCOND*/ 0)
274 
275 /*
276  * local prototypes
277  */
278 
279 static struct vm_map_entry *
280 		uvm_mapent_alloc(struct vm_map *, int);
281 static void	uvm_mapent_copy(struct vm_map_entry *, struct vm_map_entry *);
282 static void	uvm_mapent_free(struct vm_map_entry *);
283 #if defined(DEBUG)
284 static void	_uvm_mapent_check(const struct vm_map_entry *, const char *,
285 		    int);
286 #define	uvm_mapent_check(map)	_uvm_mapent_check(map, __FILE__, __LINE__)
287 #else /* defined(DEBUG) */
288 #define	uvm_mapent_check(e)	/* nothing */
289 #endif /* defined(DEBUG) */
290 
291 static void	uvm_map_entry_unwire(struct vm_map *, struct vm_map_entry *);
292 static void	uvm_map_reference_amap(struct vm_map_entry *, int);
293 static int	uvm_map_space_avail(vaddr_t *, vsize_t, voff_t, vsize_t, int,
294 		    int, struct vm_map_entry *);
295 static void	uvm_map_unreference_amap(struct vm_map_entry *, int);
296 
297 int _uvm_map_sanity(struct vm_map *);
298 int _uvm_tree_sanity(struct vm_map *);
299 static vsize_t uvm_rb_maxgap(const struct vm_map_entry *);
300 
301 #define	ROOT_ENTRY(map)		((struct vm_map_entry *)(map)->rb_tree.rbt_root)
302 #define	LEFT_ENTRY(entry)	((struct vm_map_entry *)(entry)->rb_node.rb_left)
303 #define	RIGHT_ENTRY(entry)	((struct vm_map_entry *)(entry)->rb_node.rb_right)
304 #define	PARENT_ENTRY(map, entry) \
305 	(ROOT_ENTRY(map) == (entry) \
306 	    ? NULL : (struct vm_map_entry *)RB_FATHER(&(entry)->rb_node))
307 
308 /*
309  * These get filled in if/when SYSVSHM shared memory code is loaded
310  *
311  * We do this with function pointers rather the #ifdef SYSVSHM so the
312  * SYSVSHM code can be loaded and unloaded
313  */
314 void (*uvm_shmexit)(struct vmspace *) = NULL;
315 void (*uvm_shmfork)(struct vmspace *, struct vmspace *) = NULL;
316 
317 static int
318 uvm_map_compare_nodes(void *ctx, const void *nparent, const void *nkey)
319 {
320 	const struct vm_map_entry *eparent = nparent;
321 	const struct vm_map_entry *ekey = nkey;
322 
323 	KASSERT(eparent->start < ekey->start || eparent->start >= ekey->end);
324 	KASSERT(ekey->start < eparent->start || ekey->start >= eparent->end);
325 
326 	if (eparent->start < ekey->start)
327 		return -1;
328 	if (eparent->end >= ekey->start)
329 		return 1;
330 	return 0;
331 }
332 
333 static int
334 uvm_map_compare_key(void *ctx, const void *nparent, const void *vkey)
335 {
336 	const struct vm_map_entry *eparent = nparent;
337 	const vaddr_t va = *(const vaddr_t *) vkey;
338 
339 	if (eparent->start < va)
340 		return -1;
341 	if (eparent->end >= va)
342 		return 1;
343 	return 0;
344 }
345 
346 static const rb_tree_ops_t uvm_map_tree_ops = {
347 	.rbto_compare_nodes = uvm_map_compare_nodes,
348 	.rbto_compare_key = uvm_map_compare_key,
349 	.rbto_node_offset = offsetof(struct vm_map_entry, rb_node),
350 	.rbto_context = NULL
351 };
352 
353 /*
354  * uvm_rb_gap: return the gap size between our entry and next entry.
355  */
356 static inline vsize_t
357 uvm_rb_gap(const struct vm_map_entry *entry)
358 {
359 
360 	KASSERT(entry->next != NULL);
361 	return entry->next->start - entry->end;
362 }
363 
364 static vsize_t
365 uvm_rb_maxgap(const struct vm_map_entry *entry)
366 {
367 	struct vm_map_entry *child;
368 	vsize_t maxgap = entry->gap;
369 
370 	/*
371 	 * We need maxgap to be the largest gap of us or any of our
372 	 * descendents.  Since each of our children's maxgap is the
373 	 * cached value of their largest gap of themselves or their
374 	 * descendents, we can just use that value and avoid recursing
375 	 * down the tree to calculate it.
376 	 */
377 	if ((child = LEFT_ENTRY(entry)) != NULL && maxgap < child->maxgap)
378 		maxgap = child->maxgap;
379 
380 	if ((child = RIGHT_ENTRY(entry)) != NULL && maxgap < child->maxgap)
381 		maxgap = child->maxgap;
382 
383 	return maxgap;
384 }
385 
386 static void
387 uvm_rb_fixup(struct vm_map *map, struct vm_map_entry *entry)
388 {
389 	struct vm_map_entry *parent;
390 
391 	KASSERT(entry->gap == uvm_rb_gap(entry));
392 	entry->maxgap = uvm_rb_maxgap(entry);
393 
394 	while ((parent = PARENT_ENTRY(map, entry)) != NULL) {
395 		struct vm_map_entry *brother;
396 		vsize_t maxgap = parent->gap;
397 		unsigned int which;
398 
399 		KDASSERT(parent->gap == uvm_rb_gap(parent));
400 		if (maxgap < entry->maxgap)
401 			maxgap = entry->maxgap;
402 		/*
403 		 * Since we work towards the root, we know entry's maxgap
404 		 * value is OK, but its brothers may now be out-of-date due
405 		 * to rebalancing.  So refresh it.
406 		 */
407 		which = RB_POSITION(&entry->rb_node) ^ RB_DIR_OTHER;
408 		brother = (struct vm_map_entry *)parent->rb_node.rb_nodes[which];
409 		if (brother != NULL) {
410 			KDASSERT(brother->gap == uvm_rb_gap(brother));
411 			brother->maxgap = uvm_rb_maxgap(brother);
412 			if (maxgap < brother->maxgap)
413 				maxgap = brother->maxgap;
414 		}
415 
416 		parent->maxgap = maxgap;
417 		entry = parent;
418 	}
419 }
420 
421 static void
422 uvm_rb_insert(struct vm_map *map, struct vm_map_entry *entry)
423 {
424 	struct vm_map_entry *ret __diagused;
425 
426 	entry->gap = entry->maxgap = uvm_rb_gap(entry);
427 	if (entry->prev != &map->header)
428 		entry->prev->gap = uvm_rb_gap(entry->prev);
429 
430 	ret = rb_tree_insert_node(&map->rb_tree, entry);
431 	KASSERTMSG(ret == entry,
432 	    "uvm_rb_insert: map %p: duplicate entry %p", map, ret);
433 
434 	/*
435 	 * If the previous entry is not our immediate left child, then it's an
436 	 * ancestor and will be fixed up on the way to the root.  We don't
437 	 * have to check entry->prev against &map->header since &map->header
438 	 * will never be in the tree.
439 	 */
440 	uvm_rb_fixup(map,
441 	    LEFT_ENTRY(entry) == entry->prev ? entry->prev : entry);
442 }
443 
444 static void
445 uvm_rb_remove(struct vm_map *map, struct vm_map_entry *entry)
446 {
447 	struct vm_map_entry *prev_parent = NULL, *next_parent = NULL;
448 
449 	/*
450 	 * If we are removing an interior node, then an adjacent node will
451 	 * be used to replace its position in the tree.  Therefore we will
452 	 * need to fixup the tree starting at the parent of the replacement
453 	 * node.  So record their parents for later use.
454 	 */
455 	if (entry->prev != &map->header)
456 		prev_parent = PARENT_ENTRY(map, entry->prev);
457 	if (entry->next != &map->header)
458 		next_parent = PARENT_ENTRY(map, entry->next);
459 
460 	rb_tree_remove_node(&map->rb_tree, entry);
461 
462 	/*
463 	 * If the previous node has a new parent, fixup the tree starting
464 	 * at the previous node's old parent.
465 	 */
466 	if (entry->prev != &map->header) {
467 		/*
468 		 * Update the previous entry's gap due to our absence.
469 		 */
470 		entry->prev->gap = uvm_rb_gap(entry->prev);
471 		uvm_rb_fixup(map, entry->prev);
472 		if (prev_parent != NULL
473 		    && prev_parent != entry
474 		    && prev_parent != PARENT_ENTRY(map, entry->prev))
475 			uvm_rb_fixup(map, prev_parent);
476 	}
477 
478 	/*
479 	 * If the next node has a new parent, fixup the tree starting
480 	 * at the next node's old parent.
481 	 */
482 	if (entry->next != &map->header) {
483 		uvm_rb_fixup(map, entry->next);
484 		if (next_parent != NULL
485 		    && next_parent != entry
486 		    && next_parent != PARENT_ENTRY(map, entry->next))
487 			uvm_rb_fixup(map, next_parent);
488 	}
489 }
490 
491 #if defined(DEBUG)
492 int uvm_debug_check_map = 0;
493 int uvm_debug_check_rbtree = 0;
494 #define uvm_map_check(map, name) \
495 	_uvm_map_check((map), (name), __FILE__, __LINE__)
496 static void
497 _uvm_map_check(struct vm_map *map, const char *name,
498     const char *file, int line)
499 {
500 
501 	if ((uvm_debug_check_map && _uvm_map_sanity(map)) ||
502 	    (uvm_debug_check_rbtree && _uvm_tree_sanity(map))) {
503 		panic("uvm_map_check failed: \"%s\" map=%p (%s:%d)",
504 		    name, map, file, line);
505 	}
506 }
507 #else /* defined(DEBUG) */
508 #define uvm_map_check(map, name)	/* nothing */
509 #endif /* defined(DEBUG) */
510 
511 #if defined(DEBUG) || defined(DDB)
512 int
513 _uvm_map_sanity(struct vm_map *map)
514 {
515 	bool first_free_found = false;
516 	bool hint_found = false;
517 	const struct vm_map_entry *e;
518 	struct vm_map_entry *hint = map->hint;
519 
520 	e = &map->header;
521 	for (;;) {
522 		if (map->first_free == e) {
523 			first_free_found = true;
524 		} else if (!first_free_found && e->next->start > e->end) {
525 			printf("first_free %p should be %p\n",
526 			    map->first_free, e);
527 			return -1;
528 		}
529 		if (hint == e) {
530 			hint_found = true;
531 		}
532 
533 		e = e->next;
534 		if (e == &map->header) {
535 			break;
536 		}
537 	}
538 	if (!first_free_found) {
539 		printf("stale first_free\n");
540 		return -1;
541 	}
542 	if (!hint_found) {
543 		printf("stale hint\n");
544 		return -1;
545 	}
546 	return 0;
547 }
548 
549 int
550 _uvm_tree_sanity(struct vm_map *map)
551 {
552 	struct vm_map_entry *tmp, *trtmp;
553 	int n = 0, i = 1;
554 
555 	for (tmp = map->header.next; tmp != &map->header; tmp = tmp->next) {
556 		if (tmp->gap != uvm_rb_gap(tmp)) {
557 			printf("%d/%d gap %#lx != %#lx %s\n",
558 			    n + 1, map->nentries,
559 			    (ulong)tmp->gap, (ulong)uvm_rb_gap(tmp),
560 			    tmp->next == &map->header ? "(last)" : "");
561 			goto error;
562 		}
563 		/*
564 		 * If any entries are out of order, tmp->gap will be unsigned
565 		 * and will likely exceed the size of the map.
566 		 */
567 		if (tmp->gap >= vm_map_max(map) - vm_map_min(map)) {
568 			printf("too large gap %zu\n", (size_t)tmp->gap);
569 			goto error;
570 		}
571 		n++;
572 	}
573 
574 	if (n != map->nentries) {
575 		printf("nentries: %d vs %d\n", n, map->nentries);
576 		goto error;
577 	}
578 
579 	trtmp = NULL;
580 	for (tmp = map->header.next; tmp != &map->header; tmp = tmp->next) {
581 		if (tmp->maxgap != uvm_rb_maxgap(tmp)) {
582 			printf("maxgap %#lx != %#lx\n",
583 			    (ulong)tmp->maxgap,
584 			    (ulong)uvm_rb_maxgap(tmp));
585 			goto error;
586 		}
587 		if (trtmp != NULL && trtmp->start >= tmp->start) {
588 			printf("corrupt: 0x%"PRIxVADDR"x >= 0x%"PRIxVADDR"x\n",
589 			    trtmp->start, tmp->start);
590 			goto error;
591 		}
592 
593 		trtmp = tmp;
594 	}
595 
596 	for (tmp = map->header.next; tmp != &map->header;
597 	    tmp = tmp->next, i++) {
598 		trtmp = rb_tree_iterate(&map->rb_tree, tmp, RB_DIR_LEFT);
599 		if (trtmp == NULL)
600 			trtmp = &map->header;
601 		if (tmp->prev != trtmp) {
602 			printf("lookup: %d: %p->prev=%p: %p\n",
603 			    i, tmp, tmp->prev, trtmp);
604 			goto error;
605 		}
606 		trtmp = rb_tree_iterate(&map->rb_tree, tmp, RB_DIR_RIGHT);
607 		if (trtmp == NULL)
608 			trtmp = &map->header;
609 		if (tmp->next != trtmp) {
610 			printf("lookup: %d: %p->next=%p: %p\n",
611 			    i, tmp, tmp->next, trtmp);
612 			goto error;
613 		}
614 		trtmp = rb_tree_find_node(&map->rb_tree, &tmp->start);
615 		if (trtmp != tmp) {
616 			printf("lookup: %d: %p - %p: %p\n", i, tmp, trtmp,
617 			    PARENT_ENTRY(map, tmp));
618 			goto error;
619 		}
620 	}
621 
622 	return (0);
623  error:
624 	return (-1);
625 }
626 #endif /* defined(DEBUG) || defined(DDB) */
627 
628 /*
629  * vm_map_lock: acquire an exclusive (write) lock on a map.
630  *
631  * => The locking protocol provides for guaranteed upgrade from shared ->
632  *    exclusive by whichever thread currently has the map marked busy.
633  *    See "LOCKING PROTOCOL NOTES" in uvm_map.h.  This is horrible; among
634  *    other problems, it defeats any fairness guarantees provided by RW
635  *    locks.
636  */
637 
638 void
639 vm_map_lock(struct vm_map *map)
640 {
641 
642 	for (;;) {
643 		rw_enter(&map->lock, RW_WRITER);
644 		if (map->busy == NULL || map->busy == curlwp) {
645 			break;
646 		}
647 		mutex_enter(&map->misc_lock);
648 		rw_exit(&map->lock);
649 		if (map->busy != NULL) {
650 			cv_wait(&map->cv, &map->misc_lock);
651 		}
652 		mutex_exit(&map->misc_lock);
653 	}
654 	map->timestamp++;
655 }
656 
657 /*
658  * vm_map_lock_try: try to lock a map, failing if it is already locked.
659  */
660 
661 bool
662 vm_map_lock_try(struct vm_map *map)
663 {
664 
665 	if (!rw_tryenter(&map->lock, RW_WRITER)) {
666 		return false;
667 	}
668 	if (map->busy != NULL) {
669 		rw_exit(&map->lock);
670 		return false;
671 	}
672 	map->timestamp++;
673 	return true;
674 }
675 
676 /*
677  * vm_map_unlock: release an exclusive lock on a map.
678  */
679 
680 void
681 vm_map_unlock(struct vm_map *map)
682 {
683 
684 	KASSERT(rw_write_held(&map->lock));
685 	KASSERT(map->busy == NULL || map->busy == curlwp);
686 	rw_exit(&map->lock);
687 }
688 
689 /*
690  * vm_map_unbusy: mark the map as unbusy, and wake any waiters that
691  *     want an exclusive lock.
692  */
693 
694 void
695 vm_map_unbusy(struct vm_map *map)
696 {
697 
698 	KASSERT(map->busy == curlwp);
699 
700 	/*
701 	 * Safe to clear 'busy' and 'waiters' with only a read lock held:
702 	 *
703 	 * o they can only be set with a write lock held
704 	 * o writers are blocked out with a read or write hold
705 	 * o at any time, only one thread owns the set of values
706 	 */
707 	mutex_enter(&map->misc_lock);
708 	map->busy = NULL;
709 	cv_broadcast(&map->cv);
710 	mutex_exit(&map->misc_lock);
711 }
712 
713 /*
714  * vm_map_lock_read: acquire a shared (read) lock on a map.
715  */
716 
717 void
718 vm_map_lock_read(struct vm_map *map)
719 {
720 
721 	rw_enter(&map->lock, RW_READER);
722 }
723 
724 /*
725  * vm_map_unlock_read: release a shared lock on a map.
726  */
727 
728 void
729 vm_map_unlock_read(struct vm_map *map)
730 {
731 
732 	rw_exit(&map->lock);
733 }
734 
735 /*
736  * vm_map_busy: mark a map as busy.
737  *
738  * => the caller must hold the map write locked
739  */
740 
741 void
742 vm_map_busy(struct vm_map *map)
743 {
744 
745 	KASSERT(rw_write_held(&map->lock));
746 	KASSERT(map->busy == NULL);
747 
748 	map->busy = curlwp;
749 }
750 
751 /*
752  * vm_map_locked_p: return true if the map is write locked.
753  *
754  * => only for debug purposes like KASSERTs.
755  * => should not be used to verify that a map is not locked.
756  */
757 
758 bool
759 vm_map_locked_p(struct vm_map *map)
760 {
761 
762 	return rw_write_held(&map->lock);
763 }
764 
765 /*
766  * uvm_mapent_alloc: allocate a map entry
767  */
768 
769 static struct vm_map_entry *
770 uvm_mapent_alloc(struct vm_map *map, int flags)
771 {
772 	struct vm_map_entry *me;
773 	int pflags = (flags & UVM_FLAG_NOWAIT) ? PR_NOWAIT : PR_WAITOK;
774 	UVMHIST_FUNC("uvm_mapent_alloc"); UVMHIST_CALLED(maphist);
775 
776 	me = pool_cache_get(&uvm_map_entry_cache, pflags);
777 	if (__predict_false(me == NULL)) {
778 		return NULL;
779 	}
780 	me->flags = 0;
781 
782 	UVMHIST_LOG(maphist, "<- new entry=%#jx [kentry=%jd]", (uintptr_t)me,
783 	    (map == kernel_map), 0, 0);
784 	return me;
785 }
786 
787 /*
788  * uvm_mapent_free: free map entry
789  */
790 
791 static void
792 uvm_mapent_free(struct vm_map_entry *me)
793 {
794 	UVMHIST_FUNC("uvm_mapent_free"); UVMHIST_CALLED(maphist);
795 
796 	UVMHIST_LOG(maphist,"<- freeing map entry=%#jx [flags=%jd]",
797 		(uintptr_t)me, me->flags, 0, 0);
798 	pool_cache_put(&uvm_map_entry_cache, me);
799 }
800 
801 /*
802  * uvm_mapent_copy: copy a map entry, preserving flags
803  */
804 
805 static inline void
806 uvm_mapent_copy(struct vm_map_entry *src, struct vm_map_entry *dst)
807 {
808 
809 	memcpy(dst, src, ((char *)&src->uvm_map_entry_stop_copy) -
810 	    ((char *)src));
811 }
812 
813 #if defined(DEBUG)
814 static void
815 _uvm_mapent_check(const struct vm_map_entry *entry, const char *file, int line)
816 {
817 
818 	if (entry->start >= entry->end) {
819 		goto bad;
820 	}
821 	if (UVM_ET_ISOBJ(entry)) {
822 		if (entry->object.uvm_obj == NULL) {
823 			goto bad;
824 		}
825 	} else if (UVM_ET_ISSUBMAP(entry)) {
826 		if (entry->object.sub_map == NULL) {
827 			goto bad;
828 		}
829 	} else {
830 		if (entry->object.uvm_obj != NULL ||
831 		    entry->object.sub_map != NULL) {
832 			goto bad;
833 		}
834 	}
835 	if (!UVM_ET_ISOBJ(entry)) {
836 		if (entry->offset != 0) {
837 			goto bad;
838 		}
839 	}
840 
841 	return;
842 
843 bad:
844 	panic("%s: bad entry %p (%s:%d)", __func__, entry, file, line);
845 }
846 #endif /* defined(DEBUG) */
847 
848 /*
849  * uvm_map_entry_unwire: unwire a map entry
850  *
851  * => map should be locked by caller
852  */
853 
854 static inline void
855 uvm_map_entry_unwire(struct vm_map *map, struct vm_map_entry *entry)
856 {
857 
858 	entry->wired_count = 0;
859 	uvm_fault_unwire_locked(map, entry->start, entry->end);
860 }
861 
862 
863 /*
864  * wrapper for calling amap_ref()
865  */
866 static inline void
867 uvm_map_reference_amap(struct vm_map_entry *entry, int flags)
868 {
869 
870 	amap_ref(entry->aref.ar_amap, entry->aref.ar_pageoff,
871 	    (entry->end - entry->start) >> PAGE_SHIFT, flags);
872 }
873 
874 
875 /*
876  * wrapper for calling amap_unref()
877  */
878 static inline void
879 uvm_map_unreference_amap(struct vm_map_entry *entry, int flags)
880 {
881 
882 	amap_unref(entry->aref.ar_amap, entry->aref.ar_pageoff,
883 	    (entry->end - entry->start) >> PAGE_SHIFT, flags);
884 }
885 
886 
887 /*
888  * uvm_map_init: init mapping system at boot time.
889  */
890 
891 void
892 uvm_map_init(void)
893 {
894 #if defined(UVMHIST)
895 	static struct kern_history_ent pdhistbuf[UVMHIST_PDHIST_SIZE];
896 #endif
897 
898 	/*
899 	 * first, init logging system.
900 	 */
901 
902 	UVMHIST_FUNC("uvm_map_init");
903 	UVMHIST_LINK_STATIC(maphist);
904 	UVMHIST_INIT_STATIC(pdhist, pdhistbuf);
905 	UVMHIST_CALLED(maphist);
906 	UVMHIST_LOG(maphist,"<starting uvm map system>", 0, 0, 0, 0);
907 
908 	/*
909 	 * initialize the global lock for kernel map entry.
910 	 */
911 
912 	mutex_init(&uvm_kentry_lock, MUTEX_DRIVER, IPL_VM);
913 }
914 
915 /*
916  * uvm_map_init_caches: init mapping system caches.
917  */
918 void
919 uvm_map_init_caches(void)
920 {
921 	/*
922 	 * initialize caches.
923 	 */
924 
925 	pool_cache_bootstrap(&uvm_map_entry_cache, sizeof(struct vm_map_entry),
926 	    0, 0, 0, "vmmpepl", NULL, IPL_NONE, NULL, NULL, NULL);
927 	pool_cache_bootstrap(&uvm_vmspace_cache, sizeof(struct vmspace),
928 	    0, 0, 0, "vmsppl", NULL, IPL_NONE, NULL, NULL, NULL);
929 }
930 
931 /*
932  * clippers
933  */
934 
935 /*
936  * uvm_mapent_splitadj: adjust map entries for splitting, after uvm_mapent_copy.
937  */
938 
939 static void
940 uvm_mapent_splitadj(struct vm_map_entry *entry1, struct vm_map_entry *entry2,
941     vaddr_t splitat)
942 {
943 	vaddr_t adj;
944 
945 	KASSERT(entry1->start < splitat);
946 	KASSERT(splitat < entry1->end);
947 
948 	adj = splitat - entry1->start;
949 	entry1->end = entry2->start = splitat;
950 
951 	if (entry1->aref.ar_amap) {
952 		amap_splitref(&entry1->aref, &entry2->aref, adj);
953 	}
954 	if (UVM_ET_ISSUBMAP(entry1)) {
955 		/* ... unlikely to happen, but play it safe */
956 		 uvm_map_reference(entry1->object.sub_map);
957 	} else if (UVM_ET_ISOBJ(entry1)) {
958 		KASSERT(entry1->object.uvm_obj != NULL); /* suppress coverity */
959 		entry2->offset += adj;
960 		if (entry1->object.uvm_obj->pgops &&
961 		    entry1->object.uvm_obj->pgops->pgo_reference)
962 			entry1->object.uvm_obj->pgops->pgo_reference(
963 			    entry1->object.uvm_obj);
964 	}
965 }
966 
967 /*
968  * uvm_map_clip_start: ensure that the entry begins at or after
969  *	the starting address, if it doesn't we split the entry.
970  *
971  * => caller should use UVM_MAP_CLIP_START macro rather than calling
972  *    this directly
973  * => map must be locked by caller
974  */
975 
976 void
977 uvm_map_clip_start(struct vm_map *map, struct vm_map_entry *entry,
978     vaddr_t start)
979 {
980 	struct vm_map_entry *new_entry;
981 
982 	/* uvm_map_simplify_entry(map, entry); */ /* XXX */
983 
984 	uvm_map_check(map, "clip_start entry");
985 	uvm_mapent_check(entry);
986 
987 	/*
988 	 * Split off the front portion.  note that we must insert the new
989 	 * entry BEFORE this one, so that this entry has the specified
990 	 * starting address.
991 	 */
992 	new_entry = uvm_mapent_alloc(map, 0);
993 	uvm_mapent_copy(entry, new_entry); /* entry -> new_entry */
994 	uvm_mapent_splitadj(new_entry, entry, start);
995 	uvm_map_entry_link(map, entry->prev, new_entry);
996 
997 	uvm_map_check(map, "clip_start leave");
998 }
999 
1000 /*
1001  * uvm_map_clip_end: ensure that the entry ends at or before
1002  *	the ending address, if it does't we split the reference
1003  *
1004  * => caller should use UVM_MAP_CLIP_END macro rather than calling
1005  *    this directly
1006  * => map must be locked by caller
1007  */
1008 
1009 void
1010 uvm_map_clip_end(struct vm_map *map, struct vm_map_entry *entry, vaddr_t end)
1011 {
1012 	struct vm_map_entry *new_entry;
1013 
1014 	uvm_map_check(map, "clip_end entry");
1015 	uvm_mapent_check(entry);
1016 
1017 	/*
1018 	 *	Create a new entry and insert it
1019 	 *	AFTER the specified entry
1020 	 */
1021 	new_entry = uvm_mapent_alloc(map, 0);
1022 	uvm_mapent_copy(entry, new_entry); /* entry -> new_entry */
1023 	uvm_mapent_splitadj(entry, new_entry, end);
1024 	uvm_map_entry_link(map, entry, new_entry);
1025 
1026 	uvm_map_check(map, "clip_end leave");
1027 }
1028 
1029 /*
1030  *   M A P   -   m a i n   e n t r y   p o i n t
1031  */
1032 /*
1033  * uvm_map: establish a valid mapping in a map
1034  *
1035  * => assume startp is page aligned.
1036  * => assume size is a multiple of PAGE_SIZE.
1037  * => assume sys_mmap provides enough of a "hint" to have us skip
1038  *	over text/data/bss area.
1039  * => map must be unlocked (we will lock it)
1040  * => <uobj,uoffset> value meanings (4 cases):
1041  *	 [1] <NULL,uoffset>		== uoffset is a hint for PMAP_PREFER
1042  *	 [2] <NULL,UVM_UNKNOWN_OFFSET>	== don't PMAP_PREFER
1043  *	 [3] <uobj,uoffset>		== normal mapping
1044  *	 [4] <uobj,UVM_UNKNOWN_OFFSET>	== uvm_map finds offset based on VA
1045  *
1046  *    case [4] is for kernel mappings where we don't know the offset until
1047  *    we've found a virtual address.   note that kernel object offsets are
1048  *    always relative to vm_map_min(kernel_map).
1049  *
1050  * => if `align' is non-zero, we align the virtual address to the specified
1051  *	alignment.
1052  *	this is provided as a mechanism for large pages.
1053  *
1054  * => XXXCDC: need way to map in external amap?
1055  */
1056 
1057 int
1058 uvm_map(struct vm_map *map, vaddr_t *startp /* IN/OUT */, vsize_t size,
1059     struct uvm_object *uobj, voff_t uoffset, vsize_t align, uvm_flag_t flags)
1060 {
1061 	struct uvm_map_args args;
1062 	struct vm_map_entry *new_entry;
1063 	int error;
1064 
1065 	KASSERT((size & PAGE_MASK) == 0);
1066 
1067 #ifndef __USER_VA0_IS_SAFE
1068 	if ((flags & UVM_FLAG_FIXED) && *startp == 0 &&
1069 	    !VM_MAP_IS_KERNEL(map) && user_va0_disable) {
1070 		uprintf("%s: process wants to map virtual address 0; see "
1071 		    "vm.user_va0_disable in sysctl(7).\n", __func__);
1072 		return EACCES;
1073 	}
1074 #endif
1075 
1076 	/*
1077 	 * for pager_map, allocate the new entry first to avoid sleeping
1078 	 * for memory while we have the map locked.
1079 	 */
1080 
1081 	new_entry = NULL;
1082 	if (map == pager_map) {
1083 		new_entry = uvm_mapent_alloc(map, (flags & UVM_FLAG_NOWAIT));
1084 		if (__predict_false(new_entry == NULL))
1085 			return ENOMEM;
1086 	}
1087 	if (map == pager_map)
1088 		flags |= UVM_FLAG_NOMERGE;
1089 
1090 	error = uvm_map_prepare(map, *startp, size, uobj, uoffset, align,
1091 	    flags, &args);
1092 	if (!error) {
1093 		error = uvm_map_enter(map, &args, new_entry);
1094 		*startp = args.uma_start;
1095 	} else if (new_entry) {
1096 		uvm_mapent_free(new_entry);
1097 	}
1098 
1099 #if defined(DEBUG)
1100 	if (!error && VM_MAP_IS_KERNEL(map) && (flags & UVM_FLAG_NOWAIT) == 0) {
1101 		uvm_km_check_empty(map, *startp, *startp + size);
1102 	}
1103 #endif /* defined(DEBUG) */
1104 
1105 	return error;
1106 }
1107 
1108 /*
1109  * uvm_map_prepare:
1110  *
1111  * called with map unlocked.
1112  * on success, returns the map locked.
1113  */
1114 
1115 int
1116 uvm_map_prepare(struct vm_map *map, vaddr_t start, vsize_t size,
1117     struct uvm_object *uobj, voff_t uoffset, vsize_t align, uvm_flag_t flags,
1118     struct uvm_map_args *args)
1119 {
1120 	struct vm_map_entry *prev_entry;
1121 	vm_prot_t prot = UVM_PROTECTION(flags);
1122 	vm_prot_t maxprot = UVM_MAXPROTECTION(flags);
1123 
1124 	UVMHIST_FUNC("uvm_map_prepare");
1125 	UVMHIST_CALLED(maphist);
1126 
1127 	UVMHIST_LOG(maphist, "(map=%#jx, start=%#jx, size=%ju, flags=%#jx)",
1128 	    (uintptr_t)map, start, size, flags);
1129 	UVMHIST_LOG(maphist, "  uobj/offset %#jx/%jd", (uintptr_t)uobj,
1130 	    uoffset,0,0);
1131 
1132 	/*
1133 	 * detect a popular device driver bug.
1134 	 */
1135 
1136 	KASSERT(doing_shutdown || curlwp != NULL);
1137 
1138 	/*
1139 	 * zero-sized mapping doesn't make any sense.
1140 	 */
1141 	KASSERT(size > 0);
1142 
1143 	KASSERT((~flags & (UVM_FLAG_NOWAIT | UVM_FLAG_WAITVA)) != 0);
1144 
1145 	uvm_map_check(map, "map entry");
1146 
1147 	/*
1148 	 * check sanity of protection code
1149 	 */
1150 
1151 	if ((prot & maxprot) != prot) {
1152 		UVMHIST_LOG(maphist, "<- prot. failure:  prot=%#jx, max=%#jx",
1153 		prot, maxprot,0,0);
1154 		return EACCES;
1155 	}
1156 
1157 	/*
1158 	 * figure out where to put new VM range
1159 	 */
1160 retry:
1161 	if (vm_map_lock_try(map) == false) {
1162 		if ((flags & UVM_FLAG_TRYLOCK) != 0) {
1163 			return EAGAIN;
1164 		}
1165 		vm_map_lock(map); /* could sleep here */
1166 	}
1167 	if (flags & UVM_FLAG_UNMAP) {
1168 		KASSERT(flags & UVM_FLAG_FIXED);
1169 		KASSERT((flags & UVM_FLAG_NOWAIT) == 0);
1170 
1171 		/*
1172 		 * Set prev_entry to what it will need to be after any existing
1173 		 * entries are removed later in uvm_map_enter().
1174 		 */
1175 
1176 		if (uvm_map_lookup_entry(map, start, &prev_entry)) {
1177 			if (start == prev_entry->start)
1178 				prev_entry = prev_entry->prev;
1179 			else
1180 				UVM_MAP_CLIP_END(map, prev_entry, start);
1181 			SAVE_HINT(map, map->hint, prev_entry);
1182 		}
1183 	} else {
1184 		prev_entry = uvm_map_findspace(map, start, size, &start,
1185 		    uobj, uoffset, align, flags);
1186 	}
1187 	if (prev_entry == NULL) {
1188 		unsigned int timestamp;
1189 
1190 		timestamp = map->timestamp;
1191 		UVMHIST_LOG(maphist,"waiting va timestamp=%#jx",
1192 			    timestamp,0,0,0);
1193 		map->flags |= VM_MAP_WANTVA;
1194 		vm_map_unlock(map);
1195 
1196 		/*
1197 		 * try to reclaim kva and wait until someone does unmap.
1198 		 * fragile locking here, so we awaken every second to
1199 		 * recheck the condition.
1200 		 */
1201 
1202 		mutex_enter(&map->misc_lock);
1203 		while ((map->flags & VM_MAP_WANTVA) != 0 &&
1204 		   map->timestamp == timestamp) {
1205 			if ((flags & UVM_FLAG_WAITVA) == 0) {
1206 				mutex_exit(&map->misc_lock);
1207 				UVMHIST_LOG(maphist,
1208 				    "<- uvm_map_findspace failed!", 0,0,0,0);
1209 				return ENOMEM;
1210 			} else {
1211 				cv_timedwait(&map->cv, &map->misc_lock, hz);
1212 			}
1213 		}
1214 		mutex_exit(&map->misc_lock);
1215 		goto retry;
1216 	}
1217 
1218 #ifdef PMAP_GROWKERNEL
1219 	/*
1220 	 * If the kernel pmap can't map the requested space,
1221 	 * then allocate more resources for it.
1222 	 */
1223 	if (map == kernel_map && uvm_maxkaddr < (start + size))
1224 		uvm_maxkaddr = pmap_growkernel(start + size);
1225 #endif
1226 
1227 	UVMMAP_EVCNT_INCR(map_call);
1228 
1229 	/*
1230 	 * if uobj is null, then uoffset is either a VAC hint for PMAP_PREFER
1231 	 * [typically from uvm_map_reserve] or it is UVM_UNKNOWN_OFFSET.   in
1232 	 * either case we want to zero it  before storing it in the map entry
1233 	 * (because it looks strange and confusing when debugging...)
1234 	 *
1235 	 * if uobj is not null
1236 	 *   if uoffset is not UVM_UNKNOWN_OFFSET then we have a normal mapping
1237 	 *      and we do not need to change uoffset.
1238 	 *   if uoffset is UVM_UNKNOWN_OFFSET then we need to find the offset
1239 	 *      now (based on the starting address of the map).   this case is
1240 	 *      for kernel object mappings where we don't know the offset until
1241 	 *      the virtual address is found (with uvm_map_findspace).   the
1242 	 *      offset is the distance we are from the start of the map.
1243 	 */
1244 
1245 	if (uobj == NULL) {
1246 		uoffset = 0;
1247 	} else {
1248 		if (uoffset == UVM_UNKNOWN_OFFSET) {
1249 			KASSERT(UVM_OBJ_IS_KERN_OBJECT(uobj));
1250 			uoffset = start - vm_map_min(kernel_map);
1251 		}
1252 	}
1253 
1254 	args->uma_flags = flags;
1255 	args->uma_prev = prev_entry;
1256 	args->uma_start = start;
1257 	args->uma_size = size;
1258 	args->uma_uobj = uobj;
1259 	args->uma_uoffset = uoffset;
1260 
1261 	UVMHIST_LOG(maphist, "<- done!", 0,0,0,0);
1262 	return 0;
1263 }
1264 
1265 /*
1266  * uvm_map_enter:
1267  *
1268  * called with map locked.
1269  * unlock the map before returning.
1270  */
1271 
1272 int
1273 uvm_map_enter(struct vm_map *map, const struct uvm_map_args *args,
1274     struct vm_map_entry *new_entry)
1275 {
1276 	struct vm_map_entry *prev_entry = args->uma_prev;
1277 	struct vm_map_entry *dead = NULL, *dead_entries = NULL;
1278 
1279 	const uvm_flag_t flags = args->uma_flags;
1280 	const vm_prot_t prot = UVM_PROTECTION(flags);
1281 	const vm_prot_t maxprot = UVM_MAXPROTECTION(flags);
1282 	const vm_inherit_t inherit = UVM_INHERIT(flags);
1283 	const int amapwaitflag = (flags & UVM_FLAG_NOWAIT) ?
1284 	    AMAP_EXTEND_NOWAIT : 0;
1285 	const int advice = UVM_ADVICE(flags);
1286 
1287 	vaddr_t start = args->uma_start;
1288 	vsize_t size = args->uma_size;
1289 	struct uvm_object *uobj = args->uma_uobj;
1290 	voff_t uoffset = args->uma_uoffset;
1291 
1292 	const int kmap = (vm_map_pmap(map) == pmap_kernel());
1293 	int merged = 0;
1294 	int error;
1295 	int newetype;
1296 
1297 	UVMHIST_FUNC("uvm_map_enter");
1298 	UVMHIST_CALLED(maphist);
1299 
1300 	UVMHIST_LOG(maphist, "(map=%#jx, start=%#jx, size=%ju, flags=%#jx)",
1301 	    (uintptr_t)map, start, size, flags);
1302 	UVMHIST_LOG(maphist, "  uobj/offset %#jx/%jd", (uintptr_t)uobj,
1303 	    uoffset,0,0);
1304 
1305 	KASSERT(map->hint == prev_entry); /* bimerge case assumes this */
1306 	KASSERT(vm_map_locked_p(map));
1307 	KASSERT((flags & (UVM_FLAG_NOWAIT | UVM_FLAG_UNMAP)) !=
1308 		(UVM_FLAG_NOWAIT | UVM_FLAG_UNMAP));
1309 
1310 	if (uobj)
1311 		newetype = UVM_ET_OBJ;
1312 	else
1313 		newetype = 0;
1314 
1315 	if (flags & UVM_FLAG_COPYONW) {
1316 		newetype |= UVM_ET_COPYONWRITE;
1317 		if ((flags & UVM_FLAG_OVERLAY) == 0)
1318 			newetype |= UVM_ET_NEEDSCOPY;
1319 	}
1320 
1321 	/*
1322 	 * For mappings with unmap, remove any old entries now.  Adding the new
1323 	 * entry cannot fail because that can only happen if UVM_FLAG_NOWAIT
1324 	 * is set, and we do not support nowait and unmap together.
1325 	 */
1326 
1327 	if (flags & UVM_FLAG_UNMAP) {
1328 		KASSERT(flags & UVM_FLAG_FIXED);
1329 		uvm_unmap_remove(map, start, start + size, &dead_entries, 0);
1330 #ifdef DEBUG
1331 		struct vm_map_entry *tmp_entry __diagused;
1332 		bool rv __diagused;
1333 
1334 		rv = uvm_map_lookup_entry(map, start, &tmp_entry);
1335 		KASSERT(!rv);
1336 		KASSERTMSG(prev_entry == tmp_entry,
1337 			   "args %p prev_entry %p tmp_entry %p",
1338 			   args, prev_entry, tmp_entry);
1339 #endif
1340 		SAVE_HINT(map, map->hint, prev_entry);
1341 	}
1342 
1343 	/*
1344 	 * try and insert in map by extending previous entry, if possible.
1345 	 * XXX: we don't try and pull back the next entry.   might be useful
1346 	 * for a stack, but we are currently allocating our stack in advance.
1347 	 */
1348 
1349 	if (flags & UVM_FLAG_NOMERGE)
1350 		goto nomerge;
1351 
1352 	if (prev_entry->end == start &&
1353 	    prev_entry != &map->header &&
1354 	    UVM_ET_ISCOMPATIBLE(prev_entry, newetype, uobj, 0,
1355 	    prot, maxprot, inherit, advice, 0)) {
1356 
1357 		if (uobj && prev_entry->offset +
1358 		    (prev_entry->end - prev_entry->start) != uoffset)
1359 			goto forwardmerge;
1360 
1361 		/*
1362 		 * can't extend a shared amap.  note: no need to lock amap to
1363 		 * look at refs since we don't care about its exact value.
1364 		 * if it is one (i.e. we have only reference) it will stay there
1365 		 */
1366 
1367 		if (prev_entry->aref.ar_amap &&
1368 		    amap_refs(prev_entry->aref.ar_amap) != 1) {
1369 			goto forwardmerge;
1370 		}
1371 
1372 		if (prev_entry->aref.ar_amap) {
1373 			error = amap_extend(prev_entry, size,
1374 			    amapwaitflag | AMAP_EXTEND_FORWARDS);
1375 			if (error)
1376 				goto nomerge;
1377 		}
1378 
1379 		if (kmap) {
1380 			UVMMAP_EVCNT_INCR(kbackmerge);
1381 		} else {
1382 			UVMMAP_EVCNT_INCR(ubackmerge);
1383 		}
1384 		UVMHIST_LOG(maphist,"  starting back merge", 0, 0, 0, 0);
1385 
1386 		/*
1387 		 * drop our reference to uobj since we are extending a reference
1388 		 * that we already have (the ref count can not drop to zero).
1389 		 */
1390 
1391 		if (uobj && uobj->pgops->pgo_detach)
1392 			uobj->pgops->pgo_detach(uobj);
1393 
1394 		/*
1395 		 * Now that we've merged the entries, note that we've grown
1396 		 * and our gap has shrunk.  Then fix the tree.
1397 		 */
1398 		prev_entry->end += size;
1399 		prev_entry->gap -= size;
1400 		uvm_rb_fixup(map, prev_entry);
1401 
1402 		uvm_map_check(map, "map backmerged");
1403 
1404 		UVMHIST_LOG(maphist,"<- done (via backmerge)!", 0, 0, 0, 0);
1405 		merged++;
1406 	}
1407 
1408 forwardmerge:
1409 	if (prev_entry->next->start == (start + size) &&
1410 	    prev_entry->next != &map->header &&
1411 	    UVM_ET_ISCOMPATIBLE(prev_entry->next, newetype, uobj, 0,
1412 	    prot, maxprot, inherit, advice, 0)) {
1413 
1414 		if (uobj && prev_entry->next->offset != uoffset + size)
1415 			goto nomerge;
1416 
1417 		/*
1418 		 * can't extend a shared amap.  note: no need to lock amap to
1419 		 * look at refs since we don't care about its exact value.
1420 		 * if it is one (i.e. we have only reference) it will stay there.
1421 		 *
1422 		 * note that we also can't merge two amaps, so if we
1423 		 * merged with the previous entry which has an amap,
1424 		 * and the next entry also has an amap, we give up.
1425 		 *
1426 		 * Interesting cases:
1427 		 * amap, new, amap -> give up second merge (single fwd extend)
1428 		 * amap, new, none -> double forward extend (extend again here)
1429 		 * none, new, amap -> double backward extend (done here)
1430 		 * uobj, new, amap -> single backward extend (done here)
1431 		 *
1432 		 * XXX should we attempt to deal with someone refilling
1433 		 * the deallocated region between two entries that are
1434 		 * backed by the same amap (ie, arefs is 2, "prev" and
1435 		 * "next" refer to it, and adding this allocation will
1436 		 * close the hole, thus restoring arefs to 1 and
1437 		 * deallocating the "next" vm_map_entry)?  -- @@@
1438 		 */
1439 
1440 		if (prev_entry->next->aref.ar_amap &&
1441 		    (amap_refs(prev_entry->next->aref.ar_amap) != 1 ||
1442 		     (merged && prev_entry->aref.ar_amap))) {
1443 			goto nomerge;
1444 		}
1445 
1446 		if (merged) {
1447 			/*
1448 			 * Try to extend the amap of the previous entry to
1449 			 * cover the next entry as well.  If it doesn't work
1450 			 * just skip on, don't actually give up, since we've
1451 			 * already completed the back merge.
1452 			 */
1453 			if (prev_entry->aref.ar_amap) {
1454 				if (amap_extend(prev_entry,
1455 				    prev_entry->next->end -
1456 				    prev_entry->next->start,
1457 				    amapwaitflag | AMAP_EXTEND_FORWARDS))
1458 					goto nomerge;
1459 			}
1460 
1461 			/*
1462 			 * Try to extend the amap of the *next* entry
1463 			 * back to cover the new allocation *and* the
1464 			 * previous entry as well (the previous merge
1465 			 * didn't have an amap already otherwise we
1466 			 * wouldn't be checking here for an amap).  If
1467 			 * it doesn't work just skip on, again, don't
1468 			 * actually give up, since we've already
1469 			 * completed the back merge.
1470 			 */
1471 			else if (prev_entry->next->aref.ar_amap) {
1472 				if (amap_extend(prev_entry->next,
1473 				    prev_entry->end -
1474 				    prev_entry->start,
1475 				    amapwaitflag | AMAP_EXTEND_BACKWARDS))
1476 					goto nomerge;
1477 			}
1478 		} else {
1479 			/*
1480 			 * Pull the next entry's amap backwards to cover this
1481 			 * new allocation.
1482 			 */
1483 			if (prev_entry->next->aref.ar_amap) {
1484 				error = amap_extend(prev_entry->next, size,
1485 				    amapwaitflag | AMAP_EXTEND_BACKWARDS);
1486 				if (error)
1487 					goto nomerge;
1488 			}
1489 		}
1490 
1491 		if (merged) {
1492 			if (kmap) {
1493 				UVMMAP_EVCNT_DECR(kbackmerge);
1494 				UVMMAP_EVCNT_INCR(kbimerge);
1495 			} else {
1496 				UVMMAP_EVCNT_DECR(ubackmerge);
1497 				UVMMAP_EVCNT_INCR(ubimerge);
1498 			}
1499 		} else {
1500 			if (kmap) {
1501 				UVMMAP_EVCNT_INCR(kforwmerge);
1502 			} else {
1503 				UVMMAP_EVCNT_INCR(uforwmerge);
1504 			}
1505 		}
1506 		UVMHIST_LOG(maphist,"  starting forward merge", 0, 0, 0, 0);
1507 
1508 		/*
1509 		 * drop our reference to uobj since we are extending a reference
1510 		 * that we already have (the ref count can not drop to zero).
1511 		 */
1512 		if (uobj && uobj->pgops->pgo_detach)
1513 			uobj->pgops->pgo_detach(uobj);
1514 
1515 		if (merged) {
1516 			dead = prev_entry->next;
1517 			prev_entry->end = dead->end;
1518 			uvm_map_entry_unlink(map, dead);
1519 			if (dead->aref.ar_amap != NULL) {
1520 				prev_entry->aref = dead->aref;
1521 				dead->aref.ar_amap = NULL;
1522 			}
1523 		} else {
1524 			prev_entry->next->start -= size;
1525 			if (prev_entry != &map->header) {
1526 				prev_entry->gap -= size;
1527 				KASSERT(prev_entry->gap == uvm_rb_gap(prev_entry));
1528 				uvm_rb_fixup(map, prev_entry);
1529 			}
1530 			if (uobj)
1531 				prev_entry->next->offset = uoffset;
1532 		}
1533 
1534 		uvm_map_check(map, "map forwardmerged");
1535 
1536 		UVMHIST_LOG(maphist,"<- done forwardmerge", 0, 0, 0, 0);
1537 		merged++;
1538 	}
1539 
1540 nomerge:
1541 	if (!merged) {
1542 		UVMHIST_LOG(maphist,"  allocating new map entry", 0, 0, 0, 0);
1543 		if (kmap) {
1544 			UVMMAP_EVCNT_INCR(knomerge);
1545 		} else {
1546 			UVMMAP_EVCNT_INCR(unomerge);
1547 		}
1548 
1549 		/*
1550 		 * allocate new entry and link it in.
1551 		 */
1552 
1553 		if (new_entry == NULL) {
1554 			new_entry = uvm_mapent_alloc(map,
1555 				(flags & UVM_FLAG_NOWAIT));
1556 			if (__predict_false(new_entry == NULL)) {
1557 				error = ENOMEM;
1558 				goto done;
1559 			}
1560 		}
1561 		new_entry->start = start;
1562 		new_entry->end = new_entry->start + size;
1563 		new_entry->object.uvm_obj = uobj;
1564 		new_entry->offset = uoffset;
1565 
1566 		new_entry->etype = newetype;
1567 
1568 		if (flags & UVM_FLAG_NOMERGE) {
1569 			new_entry->flags |= UVM_MAP_NOMERGE;
1570 		}
1571 
1572 		new_entry->protection = prot;
1573 		new_entry->max_protection = maxprot;
1574 		new_entry->inheritance = inherit;
1575 		new_entry->wired_count = 0;
1576 		new_entry->advice = advice;
1577 		if (flags & UVM_FLAG_OVERLAY) {
1578 
1579 			/*
1580 			 * to_add: for BSS we overallocate a little since we
1581 			 * are likely to extend
1582 			 */
1583 
1584 			vaddr_t to_add = (flags & UVM_FLAG_AMAPPAD) ?
1585 				UVM_AMAP_CHUNK << PAGE_SHIFT : 0;
1586 			struct vm_amap *amap = amap_alloc(size, to_add,
1587 			    (flags & UVM_FLAG_NOWAIT));
1588 			if (__predict_false(amap == NULL)) {
1589 				error = ENOMEM;
1590 				goto done;
1591 			}
1592 			new_entry->aref.ar_pageoff = 0;
1593 			new_entry->aref.ar_amap = amap;
1594 		} else {
1595 			new_entry->aref.ar_pageoff = 0;
1596 			new_entry->aref.ar_amap = NULL;
1597 		}
1598 		uvm_map_entry_link(map, prev_entry, new_entry);
1599 
1600 		/*
1601 		 * Update the free space hint
1602 		 */
1603 
1604 		if ((map->first_free == prev_entry) &&
1605 		    (prev_entry->end >= new_entry->start))
1606 			map->first_free = new_entry;
1607 
1608 		new_entry = NULL;
1609 	}
1610 
1611 	map->size += size;
1612 
1613 	UVMHIST_LOG(maphist,"<- done!", 0, 0, 0, 0);
1614 
1615 	error = 0;
1616 
1617 done:
1618 	vm_map_unlock(map);
1619 
1620 	if (new_entry) {
1621 		uvm_mapent_free(new_entry);
1622 	}
1623 	if (dead) {
1624 		KDASSERT(merged);
1625 		uvm_mapent_free(dead);
1626 	}
1627 	if (dead_entries)
1628 		uvm_unmap_detach(dead_entries, 0);
1629 
1630 	return error;
1631 }
1632 
1633 /*
1634  * uvm_map_lookup_entry_bytree: lookup an entry in tree
1635  */
1636 
1637 static inline bool
1638 uvm_map_lookup_entry_bytree(struct vm_map *map, vaddr_t address,
1639     struct vm_map_entry **entry	/* OUT */)
1640 {
1641 	struct vm_map_entry *prev = &map->header;
1642 	struct vm_map_entry *cur = ROOT_ENTRY(map);
1643 
1644 	while (cur) {
1645 		UVMMAP_EVCNT_INCR(mlk_treeloop);
1646 		if (address >= cur->start) {
1647 			if (address < cur->end) {
1648 				*entry = cur;
1649 				return true;
1650 			}
1651 			prev = cur;
1652 			cur = RIGHT_ENTRY(cur);
1653 		} else
1654 			cur = LEFT_ENTRY(cur);
1655 	}
1656 	*entry = prev;
1657 	return false;
1658 }
1659 
1660 /*
1661  * uvm_map_lookup_entry: find map entry at or before an address
1662  *
1663  * => map must at least be read-locked by caller
1664  * => entry is returned in "entry"
1665  * => return value is true if address is in the returned entry
1666  */
1667 
1668 bool
1669 uvm_map_lookup_entry(struct vm_map *map, vaddr_t address,
1670     struct vm_map_entry **entry	/* OUT */)
1671 {
1672 	struct vm_map_entry *cur;
1673 	bool use_tree = false;
1674 	UVMHIST_FUNC("uvm_map_lookup_entry");
1675 	UVMHIST_CALLED(maphist);
1676 
1677 	UVMHIST_LOG(maphist,"(map=%#jx,addr=%#jx,ent=%#jx)",
1678 	    (uintptr_t)map, address, (uintptr_t)entry, 0);
1679 
1680 	/*
1681 	 * start looking either from the head of the
1682 	 * list, or from the hint.
1683 	 */
1684 
1685 	cur = map->hint;
1686 
1687 	if (cur == &map->header)
1688 		cur = cur->next;
1689 
1690 	UVMMAP_EVCNT_INCR(mlk_call);
1691 	if (address >= cur->start) {
1692 
1693 		/*
1694 		 * go from hint to end of list.
1695 		 *
1696 		 * but first, make a quick check to see if
1697 		 * we are already looking at the entry we
1698 		 * want (which is usually the case).
1699 		 * note also that we don't need to save the hint
1700 		 * here... it is the same hint (unless we are
1701 		 * at the header, in which case the hint didn't
1702 		 * buy us anything anyway).
1703 		 */
1704 
1705 		if (cur != &map->header && cur->end > address) {
1706 			UVMMAP_EVCNT_INCR(mlk_hint);
1707 			*entry = cur;
1708 			UVMHIST_LOG(maphist,"<- got it via hint (%#jx)",
1709 			    (uintptr_t)cur, 0, 0, 0);
1710 			uvm_mapent_check(*entry);
1711 			return (true);
1712 		}
1713 
1714 		if (map->nentries > 15)
1715 			use_tree = true;
1716 	} else {
1717 
1718 		/*
1719 		 * invalid hint.  use tree.
1720 		 */
1721 		use_tree = true;
1722 	}
1723 
1724 	uvm_map_check(map, __func__);
1725 
1726 	if (use_tree) {
1727 		/*
1728 		 * Simple lookup in the tree.  Happens when the hint is
1729 		 * invalid, or nentries reach a threshold.
1730 		 */
1731 		UVMMAP_EVCNT_INCR(mlk_tree);
1732 		if (uvm_map_lookup_entry_bytree(map, address, entry)) {
1733 			goto got;
1734 		} else {
1735 			goto failed;
1736 		}
1737 	}
1738 
1739 	/*
1740 	 * search linearly
1741 	 */
1742 
1743 	UVMMAP_EVCNT_INCR(mlk_list);
1744 	while (cur != &map->header) {
1745 		UVMMAP_EVCNT_INCR(mlk_listloop);
1746 		if (cur->end > address) {
1747 			if (address >= cur->start) {
1748 				/*
1749 				 * save this lookup for future
1750 				 * hints, and return
1751 				 */
1752 
1753 				*entry = cur;
1754 got:
1755 				SAVE_HINT(map, map->hint, *entry);
1756 				UVMHIST_LOG(maphist,"<- search got it (%#jx)",
1757 					(uintptr_t)cur, 0, 0, 0);
1758 				KDASSERT((*entry)->start <= address);
1759 				KDASSERT(address < (*entry)->end);
1760 				uvm_mapent_check(*entry);
1761 				return (true);
1762 			}
1763 			break;
1764 		}
1765 		cur = cur->next;
1766 	}
1767 	*entry = cur->prev;
1768 failed:
1769 	SAVE_HINT(map, map->hint, *entry);
1770 	UVMHIST_LOG(maphist,"<- failed!",0,0,0,0);
1771 	KDASSERT((*entry) == &map->header || (*entry)->end <= address);
1772 	KDASSERT((*entry)->next == &map->header ||
1773 	    address < (*entry)->next->start);
1774 	return (false);
1775 }
1776 
1777 /*
1778  * See if the range between start and start + length fits in the gap
1779  * entry->next->start and entry->end.  Returns 1 if fits, 0 if doesn't
1780  * fit, and -1 address wraps around.
1781  */
1782 static int
1783 uvm_map_space_avail(vaddr_t *start, vsize_t length, voff_t uoffset,
1784     vsize_t align, int flags, int topdown, struct vm_map_entry *entry)
1785 {
1786 	vaddr_t end;
1787 
1788 #ifdef PMAP_PREFER
1789 	/*
1790 	 * push start address forward as needed to avoid VAC alias problems.
1791 	 * we only do this if a valid offset is specified.
1792 	 */
1793 
1794 	if (uoffset != UVM_UNKNOWN_OFFSET)
1795 		PMAP_PREFER(uoffset, start, length, topdown);
1796 #endif
1797 	if ((flags & UVM_FLAG_COLORMATCH) != 0) {
1798 		KASSERT(align < uvmexp.ncolors);
1799 		if (uvmexp.ncolors > 1) {
1800 			const u_int colormask = uvmexp.colormask;
1801 			const u_int colorsize = colormask + 1;
1802 			vaddr_t hint = atop(*start);
1803 			const u_int color = hint & colormask;
1804 			if (color != align) {
1805 				hint -= color;	/* adjust to color boundary */
1806 				KASSERT((hint & colormask) == 0);
1807 				if (topdown) {
1808 					if (align > color)
1809 						hint -= colorsize;
1810 				} else {
1811 					if (align < color)
1812 						hint += colorsize;
1813 				}
1814 				*start = ptoa(hint + align); /* adjust to color */
1815 			}
1816 		}
1817 	} else if (align != 0) {
1818 		if ((*start & (align - 1)) != 0) {
1819 			if (topdown)
1820 				*start &= ~(align - 1);
1821 			else
1822 				*start = roundup(*start, align);
1823 		}
1824 		/*
1825 		 * XXX Should we PMAP_PREFER() here again?
1826 		 * eh...i think we're okay
1827 		 */
1828 	}
1829 
1830 	/*
1831 	 * Find the end of the proposed new region.  Be sure we didn't
1832 	 * wrap around the address; if so, we lose.  Otherwise, if the
1833 	 * proposed new region fits before the next entry, we win.
1834 	 */
1835 
1836 	end = *start + length;
1837 	if (end < *start)
1838 		return (-1);
1839 
1840 	if (entry->next->start >= end && *start >= entry->end)
1841 		return (1);
1842 
1843 	return (0);
1844 }
1845 
1846 /*
1847  * uvm_map_findspace: find "length" sized space in "map".
1848  *
1849  * => "hint" is a hint about where we want it, unless UVM_FLAG_FIXED is
1850  *	set in "flags" (in which case we insist on using "hint").
1851  * => "result" is VA returned
1852  * => uobj/uoffset are to be used to handle VAC alignment, if required
1853  * => if "align" is non-zero, we attempt to align to that value.
1854  * => caller must at least have read-locked map
1855  * => returns NULL on failure, or pointer to prev. map entry if success
1856  * => note this is a cross between the old vm_map_findspace and vm_map_find
1857  */
1858 
1859 struct vm_map_entry *
1860 uvm_map_findspace(struct vm_map *map, vaddr_t hint, vsize_t length,
1861     vaddr_t *result /* OUT */, struct uvm_object *uobj, voff_t uoffset,
1862     vsize_t align, int flags)
1863 {
1864 	struct vm_map_entry *entry;
1865 	struct vm_map_entry *child, *prev, *tmp;
1866 	vaddr_t orig_hint __diagused;
1867 	const int topdown = map->flags & VM_MAP_TOPDOWN;
1868 	UVMHIST_FUNC("uvm_map_findspace");
1869 	UVMHIST_CALLED(maphist);
1870 
1871 	UVMHIST_LOG(maphist, "(map=%#jx, hint=%#jx, len=%ju, flags=%#jx)",
1872 	    (uintptr_t)map, hint, length, flags);
1873 	KASSERT((flags & UVM_FLAG_COLORMATCH) != 0 || (align & (align - 1)) == 0);
1874 	KASSERT((flags & UVM_FLAG_COLORMATCH) == 0 || align < uvmexp.ncolors);
1875 	KASSERT((flags & UVM_FLAG_FIXED) == 0 || align == 0);
1876 
1877 	uvm_map_check(map, "map_findspace entry");
1878 
1879 	/*
1880 	 * remember the original hint.  if we are aligning, then we
1881 	 * may have to try again with no alignment constraint if
1882 	 * we fail the first time.
1883 	 */
1884 
1885 	orig_hint = hint;
1886 	if (hint < vm_map_min(map)) {	/* check ranges ... */
1887 		if (flags & UVM_FLAG_FIXED) {
1888 			UVMHIST_LOG(maphist,"<- VA below map range",0,0,0,0);
1889 			return (NULL);
1890 		}
1891 		hint = vm_map_min(map);
1892 	}
1893 	if (hint > vm_map_max(map)) {
1894 		UVMHIST_LOG(maphist,"<- VA %#jx > range [%#jx->%#jx]",
1895 		    hint, vm_map_min(map), vm_map_max(map), 0);
1896 		return (NULL);
1897 	}
1898 
1899 	/*
1900 	 * Look for the first possible address; if there's already
1901 	 * something at this address, we have to start after it.
1902 	 */
1903 
1904 	/*
1905 	 * @@@: there are four, no, eight cases to consider.
1906 	 *
1907 	 * 0: found,     fixed,     bottom up -> fail
1908 	 * 1: found,     fixed,     top down  -> fail
1909 	 * 2: found,     not fixed, bottom up -> start after entry->end,
1910 	 *                                       loop up
1911 	 * 3: found,     not fixed, top down  -> start before entry->start,
1912 	 *                                       loop down
1913 	 * 4: not found, fixed,     bottom up -> check entry->next->start, fail
1914 	 * 5: not found, fixed,     top down  -> check entry->next->start, fail
1915 	 * 6: not found, not fixed, bottom up -> check entry->next->start,
1916 	 *                                       loop up
1917 	 * 7: not found, not fixed, top down  -> check entry->next->start,
1918 	 *                                       loop down
1919 	 *
1920 	 * as you can see, it reduces to roughly five cases, and that
1921 	 * adding top down mapping only adds one unique case (without
1922 	 * it, there would be four cases).
1923 	 */
1924 
1925 	if ((flags & UVM_FLAG_FIXED) == 0 && hint == vm_map_min(map)) {
1926 		entry = map->first_free;
1927 	} else {
1928 		if (uvm_map_lookup_entry(map, hint, &entry)) {
1929 			/* "hint" address already in use ... */
1930 			if (flags & UVM_FLAG_FIXED) {
1931 				UVMHIST_LOG(maphist, "<- fixed & VA in use",
1932 				    0, 0, 0, 0);
1933 				return (NULL);
1934 			}
1935 			if (topdown)
1936 				/* Start from lower gap. */
1937 				entry = entry->prev;
1938 		} else if (flags & UVM_FLAG_FIXED) {
1939 			if (entry->next->start >= hint + length &&
1940 			    hint + length > hint)
1941 				goto found;
1942 
1943 			/* "hint" address is gap but too small */
1944 			UVMHIST_LOG(maphist, "<- fixed mapping failed",
1945 			    0, 0, 0, 0);
1946 			return (NULL); /* only one shot at it ... */
1947 		} else {
1948 			/*
1949 			 * See if given hint fits in this gap.
1950 			 */
1951 			switch (uvm_map_space_avail(&hint, length,
1952 			    uoffset, align, flags, topdown, entry)) {
1953 			case 1:
1954 				goto found;
1955 			case -1:
1956 				goto wraparound;
1957 			}
1958 
1959 			if (topdown) {
1960 				/*
1961 				 * Still there is a chance to fit
1962 				 * if hint > entry->end.
1963 				 */
1964 			} else {
1965 				/* Start from higher gap. */
1966 				entry = entry->next;
1967 				if (entry == &map->header)
1968 					goto notfound;
1969 				goto nextgap;
1970 			}
1971 		}
1972 	}
1973 
1974 	/*
1975 	 * Note that all UVM_FLAGS_FIXED case is already handled.
1976 	 */
1977 	KDASSERT((flags & UVM_FLAG_FIXED) == 0);
1978 
1979 	/* Try to find the space in the red-black tree */
1980 
1981 	/* Check slot before any entry */
1982 	hint = topdown ? entry->next->start - length : entry->end;
1983 	switch (uvm_map_space_avail(&hint, length, uoffset, align, flags,
1984 	    topdown, entry)) {
1985 	case 1:
1986 		goto found;
1987 	case -1:
1988 		goto wraparound;
1989 	}
1990 
1991 nextgap:
1992 	KDASSERT((flags & UVM_FLAG_FIXED) == 0);
1993 	/* If there is not enough space in the whole tree, we fail */
1994 	tmp = ROOT_ENTRY(map);
1995 	if (tmp == NULL || tmp->maxgap < length)
1996 		goto notfound;
1997 
1998 	prev = NULL; /* previous candidate */
1999 
2000 	/* Find an entry close to hint that has enough space */
2001 	for (; tmp;) {
2002 		KASSERT(tmp->next->start == tmp->end + tmp->gap);
2003 		if (topdown) {
2004 			if (tmp->next->start < hint + length &&
2005 			    (prev == NULL || tmp->end > prev->end)) {
2006 				if (tmp->gap >= length)
2007 					prev = tmp;
2008 				else if ((child = LEFT_ENTRY(tmp)) != NULL
2009 				    && child->maxgap >= length)
2010 					prev = tmp;
2011 			}
2012 		} else {
2013 			if (tmp->end >= hint &&
2014 			    (prev == NULL || tmp->end < prev->end)) {
2015 				if (tmp->gap >= length)
2016 					prev = tmp;
2017 				else if ((child = RIGHT_ENTRY(tmp)) != NULL
2018 				    && child->maxgap >= length)
2019 					prev = tmp;
2020 			}
2021 		}
2022 		if (tmp->next->start < hint + length)
2023 			child = RIGHT_ENTRY(tmp);
2024 		else if (tmp->end > hint)
2025 			child = LEFT_ENTRY(tmp);
2026 		else {
2027 			if (tmp->gap >= length)
2028 				break;
2029 			if (topdown)
2030 				child = LEFT_ENTRY(tmp);
2031 			else
2032 				child = RIGHT_ENTRY(tmp);
2033 		}
2034 		if (child == NULL || child->maxgap < length)
2035 			break;
2036 		tmp = child;
2037 	}
2038 
2039 	if (tmp != NULL && tmp->start < hint && hint < tmp->next->start) {
2040 		/*
2041 		 * Check if the entry that we found satifies the
2042 		 * space requirement
2043 		 */
2044 		if (topdown) {
2045 			if (hint > tmp->next->start - length)
2046 				hint = tmp->next->start - length;
2047 		} else {
2048 			if (hint < tmp->end)
2049 				hint = tmp->end;
2050 		}
2051 		switch (uvm_map_space_avail(&hint, length, uoffset, align,
2052 		    flags, topdown, tmp)) {
2053 		case 1:
2054 			entry = tmp;
2055 			goto found;
2056 		case -1:
2057 			goto wraparound;
2058 		}
2059 		if (tmp->gap >= length)
2060 			goto listsearch;
2061 	}
2062 	if (prev == NULL)
2063 		goto notfound;
2064 
2065 	if (topdown) {
2066 		KASSERT(orig_hint >= prev->next->start - length ||
2067 		    prev->next->start - length > prev->next->start);
2068 		hint = prev->next->start - length;
2069 	} else {
2070 		KASSERT(orig_hint <= prev->end);
2071 		hint = prev->end;
2072 	}
2073 	switch (uvm_map_space_avail(&hint, length, uoffset, align,
2074 	    flags, topdown, prev)) {
2075 	case 1:
2076 		entry = prev;
2077 		goto found;
2078 	case -1:
2079 		goto wraparound;
2080 	}
2081 	if (prev->gap >= length)
2082 		goto listsearch;
2083 
2084 	if (topdown)
2085 		tmp = LEFT_ENTRY(prev);
2086 	else
2087 		tmp = RIGHT_ENTRY(prev);
2088 	for (;;) {
2089 		KASSERT(tmp && tmp->maxgap >= length);
2090 		if (topdown)
2091 			child = RIGHT_ENTRY(tmp);
2092 		else
2093 			child = LEFT_ENTRY(tmp);
2094 		if (child && child->maxgap >= length) {
2095 			tmp = child;
2096 			continue;
2097 		}
2098 		if (tmp->gap >= length)
2099 			break;
2100 		if (topdown)
2101 			tmp = LEFT_ENTRY(tmp);
2102 		else
2103 			tmp = RIGHT_ENTRY(tmp);
2104 	}
2105 
2106 	if (topdown) {
2107 		KASSERT(orig_hint >= tmp->next->start - length ||
2108 		    tmp->next->start - length > tmp->next->start);
2109 		hint = tmp->next->start - length;
2110 	} else {
2111 		KASSERT(orig_hint <= tmp->end);
2112 		hint = tmp->end;
2113 	}
2114 	switch (uvm_map_space_avail(&hint, length, uoffset, align,
2115 	    flags, topdown, tmp)) {
2116 	case 1:
2117 		entry = tmp;
2118 		goto found;
2119 	case -1:
2120 		goto wraparound;
2121 	}
2122 
2123 	/*
2124 	 * The tree fails to find an entry because of offset or alignment
2125 	 * restrictions.  Search the list instead.
2126 	 */
2127  listsearch:
2128 	/*
2129 	 * Look through the rest of the map, trying to fit a new region in
2130 	 * the gap between existing regions, or after the very last region.
2131 	 * note: entry->end = base VA of current gap,
2132 	 *	 entry->next->start = VA of end of current gap
2133 	 */
2134 
2135 	for (;;) {
2136 		/* Update hint for current gap. */
2137 		hint = topdown ? entry->next->start - length : entry->end;
2138 
2139 		/* See if it fits. */
2140 		switch (uvm_map_space_avail(&hint, length, uoffset, align,
2141 		    flags, topdown, entry)) {
2142 		case 1:
2143 			goto found;
2144 		case -1:
2145 			goto wraparound;
2146 		}
2147 
2148 		/* Advance to next/previous gap */
2149 		if (topdown) {
2150 			if (entry == &map->header) {
2151 				UVMHIST_LOG(maphist, "<- failed (off start)",
2152 				    0,0,0,0);
2153 				goto notfound;
2154 			}
2155 			entry = entry->prev;
2156 		} else {
2157 			entry = entry->next;
2158 			if (entry == &map->header) {
2159 				UVMHIST_LOG(maphist, "<- failed (off end)",
2160 				    0,0,0,0);
2161 				goto notfound;
2162 			}
2163 		}
2164 	}
2165 
2166  found:
2167 	SAVE_HINT(map, map->hint, entry);
2168 	*result = hint;
2169 	UVMHIST_LOG(maphist,"<- got it!  (result=%#jx)", hint, 0,0,0);
2170 	KASSERTMSG( topdown || hint >= orig_hint, "hint: %jx, orig_hint: %jx",
2171 	    (uintmax_t)hint, (uintmax_t)orig_hint);
2172 	KASSERTMSG(!topdown || hint <= orig_hint, "hint: %jx, orig_hint: %jx",
2173 	    (uintmax_t)hint, (uintmax_t)orig_hint);
2174 	KASSERT(entry->end <= hint);
2175 	KASSERT(hint + length <= entry->next->start);
2176 	return (entry);
2177 
2178  wraparound:
2179 	UVMHIST_LOG(maphist, "<- failed (wrap around)", 0,0,0,0);
2180 
2181 	return (NULL);
2182 
2183  notfound:
2184 	UVMHIST_LOG(maphist, "<- failed (notfound)", 0,0,0,0);
2185 
2186 	return (NULL);
2187 }
2188 
2189 /*
2190  *   U N M A P   -   m a i n   h e l p e r   f u n c t i o n s
2191  */
2192 
2193 /*
2194  * uvm_unmap_remove: remove mappings from a vm_map (from "start" up to "stop")
2195  *
2196  * => caller must check alignment and size
2197  * => map must be locked by caller
2198  * => we return a list of map entries that we've remove from the map
2199  *    in "entry_list"
2200  */
2201 
2202 void
2203 uvm_unmap_remove(struct vm_map *map, vaddr_t start, vaddr_t end,
2204     struct vm_map_entry **entry_list /* OUT */, int flags)
2205 {
2206 	struct vm_map_entry *entry, *first_entry, *next;
2207 	vaddr_t len;
2208 	UVMHIST_FUNC("uvm_unmap_remove"); UVMHIST_CALLED(maphist);
2209 
2210 	UVMHIST_LOG(maphist,"(map=%#jx, start=%#jx, end=%#jx)",
2211 	    (uintptr_t)map, start, end, 0);
2212 	VM_MAP_RANGE_CHECK(map, start, end);
2213 
2214 	uvm_map_check(map, "unmap_remove entry");
2215 
2216 	/*
2217 	 * find first entry
2218 	 */
2219 
2220 	if (uvm_map_lookup_entry(map, start, &first_entry) == true) {
2221 		/* clip and go... */
2222 		entry = first_entry;
2223 		UVM_MAP_CLIP_START(map, entry, start);
2224 		/* critical!  prevents stale hint */
2225 		SAVE_HINT(map, entry, entry->prev);
2226 	} else {
2227 		entry = first_entry->next;
2228 	}
2229 
2230 	/*
2231 	 * Save the free space hint
2232 	 */
2233 
2234 	if (map->first_free != &map->header && map->first_free->start >= start)
2235 		map->first_free = entry->prev;
2236 
2237 	/*
2238 	 * note: we now re-use first_entry for a different task.  we remove
2239 	 * a number of map entries from the map and save them in a linked
2240 	 * list headed by "first_entry".  once we remove them from the map
2241 	 * the caller should unlock the map and drop the references to the
2242 	 * backing objects [c.f. uvm_unmap_detach].  the object is to
2243 	 * separate unmapping from reference dropping.  why?
2244 	 *   [1] the map has to be locked for unmapping
2245 	 *   [2] the map need not be locked for reference dropping
2246 	 *   [3] dropping references may trigger pager I/O, and if we hit
2247 	 *       a pager that does synchronous I/O we may have to wait for it.
2248 	 *   [4] we would like all waiting for I/O to occur with maps unlocked
2249 	 *       so that we don't block other threads.
2250 	 */
2251 
2252 	first_entry = NULL;
2253 	*entry_list = NULL;
2254 
2255 	/*
2256 	 * break up the area into map entry sized regions and unmap.  note
2257 	 * that all mappings have to be removed before we can even consider
2258 	 * dropping references to amaps or VM objects (otherwise we could end
2259 	 * up with a mapping to a page on the free list which would be very bad)
2260 	 */
2261 
2262 	while ((entry != &map->header) && (entry->start < end)) {
2263 		KASSERT((entry->flags & UVM_MAP_STATIC) == 0);
2264 
2265 		UVM_MAP_CLIP_END(map, entry, end);
2266 		next = entry->next;
2267 		len = entry->end - entry->start;
2268 
2269 		/*
2270 		 * unwire before removing addresses from the pmap; otherwise
2271 		 * unwiring will put the entries back into the pmap (XXX).
2272 		 */
2273 
2274 		if (VM_MAPENT_ISWIRED(entry)) {
2275 			uvm_map_entry_unwire(map, entry);
2276 		}
2277 		if (flags & UVM_FLAG_VAONLY) {
2278 
2279 			/* nothing */
2280 
2281 		} else if ((map->flags & VM_MAP_PAGEABLE) == 0) {
2282 
2283 			/*
2284 			 * if the map is non-pageable, any pages mapped there
2285 			 * must be wired and entered with pmap_kenter_pa(),
2286 			 * and we should free any such pages immediately.
2287 			 * this is mostly used for kmem_map.
2288 			 */
2289 			KASSERT(vm_map_pmap(map) == pmap_kernel());
2290 
2291 			uvm_km_pgremove_intrsafe(map, entry->start, entry->end);
2292 		} else if (UVM_ET_ISOBJ(entry) &&
2293 			   UVM_OBJ_IS_KERN_OBJECT(entry->object.uvm_obj)) {
2294 			panic("%s: kernel object %p %p\n",
2295 			    __func__, map, entry);
2296 		} else if (UVM_ET_ISOBJ(entry) || entry->aref.ar_amap) {
2297 			/*
2298 			 * remove mappings the standard way.  lock object
2299 			 * and/or amap to ensure vm_page state does not
2300 			 * change while in pmap_remove().
2301 			 */
2302 
2303 			uvm_map_lock_entry(entry);
2304 			pmap_remove(map->pmap, entry->start, entry->end);
2305 			uvm_map_unlock_entry(entry);
2306 		}
2307 
2308 #if defined(UVMDEBUG)
2309 		/*
2310 		 * check if there's remaining mapping,
2311 		 * which is a bug in caller.
2312 		 */
2313 
2314 		vaddr_t va;
2315 		for (va = entry->start; va < entry->end;
2316 		    va += PAGE_SIZE) {
2317 			if (pmap_extract(vm_map_pmap(map), va, NULL)) {
2318 				panic("%s: %#"PRIxVADDR" has mapping",
2319 				    __func__, va);
2320 			}
2321 		}
2322 
2323 		if (VM_MAP_IS_KERNEL(map) && (flags & UVM_FLAG_NOWAIT) == 0) {
2324 			uvm_km_check_empty(map, entry->start,
2325 			    entry->end);
2326 		}
2327 #endif /* defined(UVMDEBUG) */
2328 
2329 		/*
2330 		 * remove entry from map and put it on our list of entries
2331 		 * that we've nuked.  then go to next entry.
2332 		 */
2333 
2334 		UVMHIST_LOG(maphist, "  removed map entry %#jx",
2335 		    (uintptr_t)entry, 0, 0, 0);
2336 
2337 		/* critical!  prevents stale hint */
2338 		SAVE_HINT(map, entry, entry->prev);
2339 
2340 		uvm_map_entry_unlink(map, entry);
2341 		KASSERT(map->size >= len);
2342 		map->size -= len;
2343 		entry->prev = NULL;
2344 		entry->next = first_entry;
2345 		first_entry = entry;
2346 		entry = next;
2347 	}
2348 
2349 	/*
2350 	 * Note: if map is dying, leave pmap_update() for pmap_destroy(),
2351 	 * which will be called later.
2352 	 */
2353 	if ((map->flags & VM_MAP_DYING) == 0) {
2354 		pmap_update(vm_map_pmap(map));
2355 	} else {
2356 		KASSERT(vm_map_pmap(map) != pmap_kernel());
2357 	}
2358 
2359 	uvm_map_check(map, "unmap_remove leave");
2360 
2361 	/*
2362 	 * now we've cleaned up the map and are ready for the caller to drop
2363 	 * references to the mapped objects.
2364 	 */
2365 
2366 	*entry_list = first_entry;
2367 	UVMHIST_LOG(maphist,"<- done!", 0, 0, 0, 0);
2368 
2369 	if (map->flags & VM_MAP_WANTVA) {
2370 		mutex_enter(&map->misc_lock);
2371 		map->flags &= ~VM_MAP_WANTVA;
2372 		cv_broadcast(&map->cv);
2373 		mutex_exit(&map->misc_lock);
2374 	}
2375 }
2376 
2377 /*
2378  * uvm_unmap_detach: drop references in a chain of map entries
2379  *
2380  * => we will free the map entries as we traverse the list.
2381  */
2382 
2383 void
2384 uvm_unmap_detach(struct vm_map_entry *first_entry, int flags)
2385 {
2386 	struct vm_map_entry *next_entry;
2387 	UVMHIST_FUNC("uvm_unmap_detach"); UVMHIST_CALLED(maphist);
2388 
2389 	while (first_entry) {
2390 		KASSERT(!VM_MAPENT_ISWIRED(first_entry));
2391 		UVMHIST_LOG(maphist,
2392 		    "  detach %#jx: amap=%#jx, obj=%#jx, submap?=%jd",
2393 		    (uintptr_t)first_entry,
2394 		    (uintptr_t)first_entry->aref.ar_amap,
2395 		    (uintptr_t)first_entry->object.uvm_obj,
2396 		    UVM_ET_ISSUBMAP(first_entry));
2397 
2398 		/*
2399 		 * drop reference to amap, if we've got one
2400 		 */
2401 
2402 		if (first_entry->aref.ar_amap)
2403 			uvm_map_unreference_amap(first_entry, flags);
2404 
2405 		/*
2406 		 * drop reference to our backing object, if we've got one
2407 		 */
2408 
2409 		KASSERT(!UVM_ET_ISSUBMAP(first_entry));
2410 		if (UVM_ET_ISOBJ(first_entry) &&
2411 		    first_entry->object.uvm_obj->pgops->pgo_detach) {
2412 			(*first_entry->object.uvm_obj->pgops->pgo_detach)
2413 				(first_entry->object.uvm_obj);
2414 		}
2415 		next_entry = first_entry->next;
2416 		uvm_mapent_free(first_entry);
2417 		first_entry = next_entry;
2418 	}
2419 	UVMHIST_LOG(maphist, "<- done", 0,0,0,0);
2420 }
2421 
2422 /*
2423  *   E X T R A C T I O N   F U N C T I O N S
2424  */
2425 
2426 /*
2427  * uvm_map_reserve: reserve space in a vm_map for future use.
2428  *
2429  * => we reserve space in a map by putting a dummy map entry in the
2430  *    map (dummy means obj=NULL, amap=NULL, prot=VM_PROT_NONE)
2431  * => map should be unlocked (we will write lock it)
2432  * => we return true if we were able to reserve space
2433  * => XXXCDC: should be inline?
2434  */
2435 
2436 int
2437 uvm_map_reserve(struct vm_map *map, vsize_t size,
2438     vaddr_t offset	/* hint for pmap_prefer */,
2439     vsize_t align	/* alignment */,
2440     vaddr_t *raddr	/* IN:hint, OUT: reserved VA */,
2441     uvm_flag_t flags	/* UVM_FLAG_FIXED or UVM_FLAG_COLORMATCH or 0 */)
2442 {
2443 	UVMHIST_FUNC("uvm_map_reserve"); UVMHIST_CALLED(maphist);
2444 
2445 	UVMHIST_LOG(maphist, "(map=%#jx, size=%#jx, offset=%#jx, addr=%#jx)",
2446 	    (uintptr_t)map, size, offset, (uintptr_t)raddr);
2447 
2448 	size = round_page(size);
2449 
2450 	/*
2451 	 * reserve some virtual space.
2452 	 */
2453 
2454 	if (uvm_map(map, raddr, size, NULL, offset, align,
2455 	    UVM_MAPFLAG(UVM_PROT_NONE, UVM_PROT_NONE, UVM_INH_NONE,
2456 	    UVM_ADV_RANDOM, UVM_FLAG_NOMERGE|flags)) != 0) {
2457 	    UVMHIST_LOG(maphist, "<- done (no VM)", 0,0,0,0);
2458 		return (false);
2459 	}
2460 
2461 	UVMHIST_LOG(maphist, "<- done (*raddr=%#jx)", *raddr,0,0,0);
2462 	return (true);
2463 }
2464 
2465 /*
2466  * uvm_map_replace: replace a reserved (blank) area of memory with
2467  * real mappings.
2468  *
2469  * => caller must WRITE-LOCK the map
2470  * => we return true if replacement was a success
2471  * => we expect the newents chain to have nnewents entrys on it and
2472  *    we expect newents->prev to point to the last entry on the list
2473  * => note newents is allowed to be NULL
2474  */
2475 
2476 static int
2477 uvm_map_replace(struct vm_map *map, vaddr_t start, vaddr_t end,
2478     struct vm_map_entry *newents, int nnewents, vsize_t nsize,
2479     struct vm_map_entry **oldentryp)
2480 {
2481 	struct vm_map_entry *oldent, *last;
2482 
2483 	uvm_map_check(map, "map_replace entry");
2484 
2485 	/*
2486 	 * first find the blank map entry at the specified address
2487 	 */
2488 
2489 	if (!uvm_map_lookup_entry(map, start, &oldent)) {
2490 		return (false);
2491 	}
2492 
2493 	/*
2494 	 * check to make sure we have a proper blank entry
2495 	 */
2496 
2497 	if (end < oldent->end) {
2498 		UVM_MAP_CLIP_END(map, oldent, end);
2499 	}
2500 	if (oldent->start != start || oldent->end != end ||
2501 	    oldent->object.uvm_obj != NULL || oldent->aref.ar_amap != NULL) {
2502 		return (false);
2503 	}
2504 
2505 #ifdef DIAGNOSTIC
2506 
2507 	/*
2508 	 * sanity check the newents chain
2509 	 */
2510 
2511 	{
2512 		struct vm_map_entry *tmpent = newents;
2513 		int nent = 0;
2514 		vsize_t sz = 0;
2515 		vaddr_t cur = start;
2516 
2517 		while (tmpent) {
2518 			nent++;
2519 			sz += tmpent->end - tmpent->start;
2520 			if (tmpent->start < cur)
2521 				panic("uvm_map_replace1");
2522 			if (tmpent->start >= tmpent->end || tmpent->end > end) {
2523 				panic("uvm_map_replace2: "
2524 				    "tmpent->start=%#"PRIxVADDR
2525 				    ", tmpent->end=%#"PRIxVADDR
2526 				    ", end=%#"PRIxVADDR,
2527 				    tmpent->start, tmpent->end, end);
2528 			}
2529 			cur = tmpent->end;
2530 			if (tmpent->next) {
2531 				if (tmpent->next->prev != tmpent)
2532 					panic("uvm_map_replace3");
2533 			} else {
2534 				if (newents->prev != tmpent)
2535 					panic("uvm_map_replace4");
2536 			}
2537 			tmpent = tmpent->next;
2538 		}
2539 		if (nent != nnewents)
2540 			panic("uvm_map_replace5");
2541 		if (sz != nsize)
2542 			panic("uvm_map_replace6");
2543 	}
2544 #endif
2545 
2546 	/*
2547 	 * map entry is a valid blank!   replace it.   (this does all the
2548 	 * work of map entry link/unlink...).
2549 	 */
2550 
2551 	if (newents) {
2552 		last = newents->prev;
2553 
2554 		/* critical: flush stale hints out of map */
2555 		SAVE_HINT(map, map->hint, newents);
2556 		if (map->first_free == oldent)
2557 			map->first_free = last;
2558 
2559 		last->next = oldent->next;
2560 		last->next->prev = last;
2561 
2562 		/* Fix RB tree */
2563 		uvm_rb_remove(map, oldent);
2564 
2565 		newents->prev = oldent->prev;
2566 		newents->prev->next = newents;
2567 		map->nentries = map->nentries + (nnewents - 1);
2568 
2569 		/* Fixup the RB tree */
2570 		{
2571 			int i;
2572 			struct vm_map_entry *tmp;
2573 
2574 			tmp = newents;
2575 			for (i = 0; i < nnewents && tmp; i++) {
2576 				uvm_rb_insert(map, tmp);
2577 				tmp = tmp->next;
2578 			}
2579 		}
2580 	} else {
2581 		/* NULL list of new entries: just remove the old one */
2582 		clear_hints(map, oldent);
2583 		uvm_map_entry_unlink(map, oldent);
2584 	}
2585 	map->size -= end - start - nsize;
2586 
2587 	uvm_map_check(map, "map_replace leave");
2588 
2589 	/*
2590 	 * now we can free the old blank entry and return.
2591 	 */
2592 
2593 	*oldentryp = oldent;
2594 	return (true);
2595 }
2596 
2597 /*
2598  * uvm_map_extract: extract a mapping from a map and put it somewhere
2599  *	(maybe removing the old mapping)
2600  *
2601  * => maps should be unlocked (we will write lock them)
2602  * => returns 0 on success, error code otherwise
2603  * => start must be page aligned
2604  * => len must be page sized
2605  * => flags:
2606  *      UVM_EXTRACT_REMOVE: remove mappings from srcmap
2607  *      UVM_EXTRACT_CONTIG: abort if unmapped area (advisory only)
2608  *      UVM_EXTRACT_QREF: for a temporary extraction do quick obj refs
2609  *      UVM_EXTRACT_FIXPROT: set prot to maxprot as we go
2610  *      UVM_EXTRACT_PROT_ALL: set prot to UVM_PROT_ALL as we go
2611  *    >>>NOTE: if you set REMOVE, you are not allowed to use CONTIG or QREF!<<<
2612  *    >>>NOTE: QREF's must be unmapped via the QREF path, thus should only
2613  *             be used from within the kernel in a kernel level map <<<
2614  */
2615 
2616 int
2617 uvm_map_extract(struct vm_map *srcmap, vaddr_t start, vsize_t len,
2618     struct vm_map *dstmap, vaddr_t *dstaddrp, int flags)
2619 {
2620 	vaddr_t dstaddr, end, newend, oldoffset, fudge, orig_fudge;
2621 	struct vm_map_entry *chain, *endchain, *entry, *orig_entry, *newentry,
2622 	    *deadentry, *oldentry;
2623 	struct vm_map_entry *resentry = NULL; /* a dummy reservation entry */
2624 	vsize_t elen __unused;
2625 	int nchain, error, copy_ok;
2626 	vsize_t nsize;
2627 	UVMHIST_FUNC("uvm_map_extract"); UVMHIST_CALLED(maphist);
2628 
2629 	UVMHIST_LOG(maphist,"(srcmap=%#jx,start=%#jx, len=%#jx",
2630 	    (uintptr_t)srcmap, start, len, 0);
2631 	UVMHIST_LOG(maphist," ...,dstmap=%#jx, flags=%#jx)",
2632 	    (uintptr_t)dstmap, flags, 0, 0);
2633 
2634 	/*
2635 	 * step 0: sanity check: start must be on a page boundary, length
2636 	 * must be page sized.  can't ask for CONTIG/QREF if you asked for
2637 	 * REMOVE.
2638 	 */
2639 
2640 	KASSERT((start & PAGE_MASK) == 0 && (len & PAGE_MASK) == 0);
2641 	KASSERT((flags & UVM_EXTRACT_REMOVE) == 0 ||
2642 		(flags & (UVM_EXTRACT_CONTIG|UVM_EXTRACT_QREF)) == 0);
2643 
2644 	/*
2645 	 * step 1: reserve space in the target map for the extracted area
2646 	 */
2647 
2648 	if ((flags & UVM_EXTRACT_RESERVED) == 0) {
2649 		dstaddr = vm_map_min(dstmap);
2650 		if (!uvm_map_reserve(dstmap, len, start,
2651 		    atop(start) & uvmexp.colormask, &dstaddr,
2652 		    UVM_FLAG_COLORMATCH))
2653 			return (ENOMEM);
2654 		KASSERT((atop(start ^ dstaddr) & uvmexp.colormask) == 0);
2655 		*dstaddrp = dstaddr;	/* pass address back to caller */
2656 		UVMHIST_LOG(maphist, "  dstaddr=%#jx", dstaddr,0,0,0);
2657 	} else {
2658 		dstaddr = *dstaddrp;
2659 	}
2660 
2661 	/*
2662 	 * step 2: setup for the extraction process loop by init'ing the
2663 	 * map entry chain, locking src map, and looking up the first useful
2664 	 * entry in the map.
2665 	 */
2666 
2667 	end = start + len;
2668 	newend = dstaddr + len;
2669 	chain = endchain = NULL;
2670 	nchain = 0;
2671 	nsize = 0;
2672 	vm_map_lock(srcmap);
2673 
2674 	if (uvm_map_lookup_entry(srcmap, start, &entry)) {
2675 
2676 		/* "start" is within an entry */
2677 		if (flags & UVM_EXTRACT_QREF) {
2678 
2679 			/*
2680 			 * for quick references we don't clip the entry, so
2681 			 * the entry may map space "before" the starting
2682 			 * virtual address... this is the "fudge" factor
2683 			 * (which can be non-zero only the first time
2684 			 * through the "while" loop in step 3).
2685 			 */
2686 
2687 			fudge = start - entry->start;
2688 		} else {
2689 
2690 			/*
2691 			 * normal reference: we clip the map to fit (thus
2692 			 * fudge is zero)
2693 			 */
2694 
2695 			UVM_MAP_CLIP_START(srcmap, entry, start);
2696 			SAVE_HINT(srcmap, srcmap->hint, entry->prev);
2697 			fudge = 0;
2698 		}
2699 	} else {
2700 
2701 		/* "start" is not within an entry ... skip to next entry */
2702 		if (flags & UVM_EXTRACT_CONTIG) {
2703 			error = EINVAL;
2704 			goto bad;    /* definite hole here ... */
2705 		}
2706 
2707 		entry = entry->next;
2708 		fudge = 0;
2709 	}
2710 
2711 	/* save values from srcmap for step 6 */
2712 	orig_entry = entry;
2713 	orig_fudge = fudge;
2714 
2715 	/*
2716 	 * step 3: now start looping through the map entries, extracting
2717 	 * as we go.
2718 	 */
2719 
2720 	while (entry->start < end && entry != &srcmap->header) {
2721 
2722 		/* if we are not doing a quick reference, clip it */
2723 		if ((flags & UVM_EXTRACT_QREF) == 0)
2724 			UVM_MAP_CLIP_END(srcmap, entry, end);
2725 
2726 		/* clear needs_copy (allow chunking) */
2727 		if (UVM_ET_ISNEEDSCOPY(entry)) {
2728 			amap_copy(srcmap, entry,
2729 			    AMAP_COPY_NOWAIT|AMAP_COPY_NOMERGE, start, end);
2730 			if (UVM_ET_ISNEEDSCOPY(entry)) {  /* failed? */
2731 				error = ENOMEM;
2732 				goto bad;
2733 			}
2734 
2735 			/* amap_copy could clip (during chunk)!  update fudge */
2736 			if (fudge) {
2737 				fudge = start - entry->start;
2738 				orig_fudge = fudge;
2739 			}
2740 		}
2741 
2742 		/* calculate the offset of this from "start" */
2743 		oldoffset = (entry->start + fudge) - start;
2744 
2745 		/* allocate a new map entry */
2746 		newentry = uvm_mapent_alloc(dstmap, 0);
2747 		if (newentry == NULL) {
2748 			error = ENOMEM;
2749 			goto bad;
2750 		}
2751 
2752 		/* set up new map entry */
2753 		newentry->next = NULL;
2754 		newentry->prev = endchain;
2755 		newentry->start = dstaddr + oldoffset;
2756 		newentry->end =
2757 		    newentry->start + (entry->end - (entry->start + fudge));
2758 		if (newentry->end > newend || newentry->end < newentry->start)
2759 			newentry->end = newend;
2760 		newentry->object.uvm_obj = entry->object.uvm_obj;
2761 		if (newentry->object.uvm_obj) {
2762 			if (newentry->object.uvm_obj->pgops->pgo_reference)
2763 				newentry->object.uvm_obj->pgops->
2764 				    pgo_reference(newentry->object.uvm_obj);
2765 			newentry->offset = entry->offset + fudge;
2766 		} else {
2767 			newentry->offset = 0;
2768 		}
2769 		newentry->etype = entry->etype;
2770 		if (flags & UVM_EXTRACT_PROT_ALL) {
2771 			newentry->protection = newentry->max_protection =
2772 			    UVM_PROT_ALL;
2773 		} else {
2774 			newentry->protection = (flags & UVM_EXTRACT_FIXPROT) ?
2775 			    entry->max_protection : entry->protection;
2776 			newentry->max_protection = entry->max_protection;
2777 		}
2778 		newentry->inheritance = entry->inheritance;
2779 		newentry->wired_count = 0;
2780 		newentry->aref.ar_amap = entry->aref.ar_amap;
2781 		if (newentry->aref.ar_amap) {
2782 			newentry->aref.ar_pageoff =
2783 			    entry->aref.ar_pageoff + (fudge >> PAGE_SHIFT);
2784 			uvm_map_reference_amap(newentry, AMAP_SHARED |
2785 			    ((flags & UVM_EXTRACT_QREF) ? AMAP_REFALL : 0));
2786 		} else {
2787 			newentry->aref.ar_pageoff = 0;
2788 		}
2789 		newentry->advice = entry->advice;
2790 		if ((flags & UVM_EXTRACT_QREF) != 0) {
2791 			newentry->flags |= UVM_MAP_NOMERGE;
2792 		}
2793 
2794 		/* now link it on the chain */
2795 		nchain++;
2796 		nsize += newentry->end - newentry->start;
2797 		if (endchain == NULL) {
2798 			chain = endchain = newentry;
2799 		} else {
2800 			endchain->next = newentry;
2801 			endchain = newentry;
2802 		}
2803 
2804 		/* end of 'while' loop! */
2805 		if ((flags & UVM_EXTRACT_CONTIG) && entry->end < end &&
2806 		    (entry->next == &srcmap->header ||
2807 		    entry->next->start != entry->end)) {
2808 			error = EINVAL;
2809 			goto bad;
2810 		}
2811 		entry = entry->next;
2812 		fudge = 0;
2813 	}
2814 
2815 	/*
2816 	 * step 4: close off chain (in format expected by uvm_map_replace)
2817 	 */
2818 
2819 	if (chain)
2820 		chain->prev = endchain;
2821 
2822 	/*
2823 	 * step 5: attempt to lock the dest map so we can pmap_copy.
2824 	 * note usage of copy_ok:
2825 	 *   1 => dstmap locked, pmap_copy ok, and we "replace" here (step 5)
2826 	 *   0 => dstmap unlocked, NO pmap_copy, and we will "replace" in step 7
2827 	 */
2828 
2829 	if (srcmap == dstmap || vm_map_lock_try(dstmap) == true) {
2830 		copy_ok = 1;
2831 		if (!uvm_map_replace(dstmap, dstaddr, dstaddr+len, chain,
2832 		    nchain, nsize, &resentry)) {
2833 			if (srcmap != dstmap)
2834 				vm_map_unlock(dstmap);
2835 			error = EIO;
2836 			goto bad;
2837 		}
2838 	} else {
2839 		copy_ok = 0;
2840 		/* replace defered until step 7 */
2841 	}
2842 
2843 	/*
2844 	 * step 6: traverse the srcmap a second time to do the following:
2845 	 *  - if we got a lock on the dstmap do pmap_copy
2846 	 *  - if UVM_EXTRACT_REMOVE remove the entries
2847 	 * we make use of orig_entry and orig_fudge (saved in step 2)
2848 	 */
2849 
2850 	if (copy_ok || (flags & UVM_EXTRACT_REMOVE)) {
2851 
2852 		/* purge possible stale hints from srcmap */
2853 		if (flags & UVM_EXTRACT_REMOVE) {
2854 			SAVE_HINT(srcmap, srcmap->hint, orig_entry->prev);
2855 			if (srcmap->first_free != &srcmap->header &&
2856 			    srcmap->first_free->start >= start)
2857 				srcmap->first_free = orig_entry->prev;
2858 		}
2859 
2860 		entry = orig_entry;
2861 		fudge = orig_fudge;
2862 		deadentry = NULL;	/* for UVM_EXTRACT_REMOVE */
2863 
2864 		while (entry->start < end && entry != &srcmap->header) {
2865 			if (copy_ok) {
2866 				oldoffset = (entry->start + fudge) - start;
2867 				elen = MIN(end, entry->end) -
2868 				    (entry->start + fudge);
2869 				pmap_copy(dstmap->pmap, srcmap->pmap,
2870 				    dstaddr + oldoffset, elen,
2871 				    entry->start + fudge);
2872 			}
2873 
2874 			/* we advance "entry" in the following if statement */
2875 			if (flags & UVM_EXTRACT_REMOVE) {
2876 				uvm_map_lock_entry(entry);
2877 				pmap_remove(srcmap->pmap, entry->start,
2878 						entry->end);
2879 				uvm_map_unlock_entry(entry);
2880 				oldentry = entry;	/* save entry */
2881 				entry = entry->next;	/* advance */
2882 				uvm_map_entry_unlink(srcmap, oldentry);
2883 							/* add to dead list */
2884 				oldentry->next = deadentry;
2885 				deadentry = oldentry;
2886 			} else {
2887 				entry = entry->next;		/* advance */
2888 			}
2889 
2890 			/* end of 'while' loop */
2891 			fudge = 0;
2892 		}
2893 		pmap_update(srcmap->pmap);
2894 
2895 		/*
2896 		 * unlock dstmap.  we will dispose of deadentry in
2897 		 * step 7 if needed
2898 		 */
2899 
2900 		if (copy_ok && srcmap != dstmap)
2901 			vm_map_unlock(dstmap);
2902 
2903 	} else {
2904 		deadentry = NULL;
2905 	}
2906 
2907 	/*
2908 	 * step 7: we are done with the source map, unlock.   if copy_ok
2909 	 * is 0 then we have not replaced the dummy mapping in dstmap yet
2910 	 * and we need to do so now.
2911 	 */
2912 
2913 	vm_map_unlock(srcmap);
2914 	if ((flags & UVM_EXTRACT_REMOVE) && deadentry)
2915 		uvm_unmap_detach(deadentry, 0);   /* dispose of old entries */
2916 
2917 	/* now do the replacement if we didn't do it in step 5 */
2918 	if (copy_ok == 0) {
2919 		vm_map_lock(dstmap);
2920 		error = uvm_map_replace(dstmap, dstaddr, dstaddr+len, chain,
2921 		    nchain, nsize, &resentry);
2922 		vm_map_unlock(dstmap);
2923 
2924 		if (error == false) {
2925 			error = EIO;
2926 			goto bad2;
2927 		}
2928 	}
2929 
2930 	if (resentry != NULL)
2931 		uvm_mapent_free(resentry);
2932 
2933 	return (0);
2934 
2935 	/*
2936 	 * bad: failure recovery
2937 	 */
2938 bad:
2939 	vm_map_unlock(srcmap);
2940 bad2:			/* src already unlocked */
2941 	if (chain)
2942 		uvm_unmap_detach(chain,
2943 		    (flags & UVM_EXTRACT_QREF) ? AMAP_REFALL : 0);
2944 
2945 	if (resentry != NULL)
2946 		uvm_mapent_free(resentry);
2947 
2948 	if ((flags & UVM_EXTRACT_RESERVED) == 0) {
2949 		uvm_unmap(dstmap, dstaddr, dstaddr+len);   /* ??? */
2950 	}
2951 	return (error);
2952 }
2953 
2954 /* end of extraction functions */
2955 
2956 /*
2957  * uvm_map_submap: punch down part of a map into a submap
2958  *
2959  * => only the kernel_map is allowed to be submapped
2960  * => the purpose of submapping is to break up the locking granularity
2961  *	of a larger map
2962  * => the range specified must have been mapped previously with a uvm_map()
2963  *	call [with uobj==NULL] to create a blank map entry in the main map.
2964  *	[And it had better still be blank!]
2965  * => maps which contain submaps should never be copied or forked.
2966  * => to remove a submap, use uvm_unmap() on the main map
2967  *	and then uvm_map_deallocate() the submap.
2968  * => main map must be unlocked.
2969  * => submap must have been init'd and have a zero reference count.
2970  *	[need not be locked as we don't actually reference it]
2971  */
2972 
2973 int
2974 uvm_map_submap(struct vm_map *map, vaddr_t start, vaddr_t end,
2975     struct vm_map *submap)
2976 {
2977 	struct vm_map_entry *entry;
2978 	int error;
2979 
2980 	vm_map_lock(map);
2981 	VM_MAP_RANGE_CHECK(map, start, end);
2982 
2983 	if (uvm_map_lookup_entry(map, start, &entry)) {
2984 		UVM_MAP_CLIP_START(map, entry, start);
2985 		UVM_MAP_CLIP_END(map, entry, end);	/* to be safe */
2986 	} else {
2987 		entry = NULL;
2988 	}
2989 
2990 	if (entry != NULL &&
2991 	    entry->start == start && entry->end == end &&
2992 	    entry->object.uvm_obj == NULL && entry->aref.ar_amap == NULL &&
2993 	    !UVM_ET_ISCOPYONWRITE(entry) && !UVM_ET_ISNEEDSCOPY(entry)) {
2994 		entry->etype |= UVM_ET_SUBMAP;
2995 		entry->object.sub_map = submap;
2996 		entry->offset = 0;
2997 		uvm_map_reference(submap);
2998 		error = 0;
2999 	} else {
3000 		error = EINVAL;
3001 	}
3002 	vm_map_unlock(map);
3003 
3004 	return error;
3005 }
3006 
3007 /*
3008  * uvm_map_protect_user: change map protection on behalf of the user.
3009  * Enforces PAX settings as necessary.
3010  */
3011 int
3012 uvm_map_protect_user(struct lwp *l, vaddr_t start, vaddr_t end,
3013     vm_prot_t new_prot)
3014 {
3015 	int error;
3016 
3017 	if ((error = PAX_MPROTECT_VALIDATE(l, new_prot)))
3018 		return error;
3019 
3020 	return uvm_map_protect(&l->l_proc->p_vmspace->vm_map, start, end,
3021 	    new_prot, false);
3022 }
3023 
3024 
3025 /*
3026  * uvm_map_protect: change map protection
3027  *
3028  * => set_max means set max_protection.
3029  * => map must be unlocked.
3030  */
3031 
3032 #define MASK(entry)	(UVM_ET_ISCOPYONWRITE(entry) ? \
3033 			 ~VM_PROT_WRITE : VM_PROT_ALL)
3034 
3035 int
3036 uvm_map_protect(struct vm_map *map, vaddr_t start, vaddr_t end,
3037     vm_prot_t new_prot, bool set_max)
3038 {
3039 	struct vm_map_entry *current, *entry;
3040 	int error = 0;
3041 	UVMHIST_FUNC("uvm_map_protect"); UVMHIST_CALLED(maphist);
3042 	UVMHIST_LOG(maphist,"(map=%#jx,start=%#jx,end=%#jx,new_prot=%#jx)",
3043 	    (uintptr_t)map, start, end, new_prot);
3044 
3045 	vm_map_lock(map);
3046 	VM_MAP_RANGE_CHECK(map, start, end);
3047 	if (uvm_map_lookup_entry(map, start, &entry)) {
3048 		UVM_MAP_CLIP_START(map, entry, start);
3049 	} else {
3050 		entry = entry->next;
3051 	}
3052 
3053 	/*
3054 	 * make a first pass to check for protection violations.
3055 	 */
3056 
3057 	current = entry;
3058 	while ((current != &map->header) && (current->start < end)) {
3059 		if (UVM_ET_ISSUBMAP(current)) {
3060 			error = EINVAL;
3061 			goto out;
3062 		}
3063 		if ((new_prot & current->max_protection) != new_prot) {
3064 			error = EACCES;
3065 			goto out;
3066 		}
3067 		/*
3068 		 * Don't allow VM_PROT_EXECUTE to be set on entries that
3069 		 * point to vnodes that are associated with a NOEXEC file
3070 		 * system.
3071 		 */
3072 		if (UVM_ET_ISOBJ(current) &&
3073 		    UVM_OBJ_IS_VNODE(current->object.uvm_obj)) {
3074 			struct vnode *vp =
3075 			    (struct vnode *) current->object.uvm_obj;
3076 
3077 			if ((new_prot & VM_PROT_EXECUTE) != 0 &&
3078 			    (vp->v_mount->mnt_flag & MNT_NOEXEC) != 0) {
3079 				error = EACCES;
3080 				goto out;
3081 			}
3082 		}
3083 
3084 		current = current->next;
3085 	}
3086 
3087 	/* go back and fix up protections (no need to clip this time). */
3088 
3089 	current = entry;
3090 	while ((current != &map->header) && (current->start < end)) {
3091 		vm_prot_t old_prot;
3092 
3093 		UVM_MAP_CLIP_END(map, current, end);
3094 		old_prot = current->protection;
3095 		if (set_max)
3096 			current->protection =
3097 			    (current->max_protection = new_prot) & old_prot;
3098 		else
3099 			current->protection = new_prot;
3100 
3101 		/*
3102 		 * update physical map if necessary.  worry about copy-on-write
3103 		 * here -- CHECK THIS XXX
3104 		 */
3105 
3106 		if (current->protection != old_prot) {
3107 			/* update pmap! */
3108 			uvm_map_lock_entry(current);
3109 			pmap_protect(map->pmap, current->start, current->end,
3110 			    current->protection & MASK(entry));
3111 			uvm_map_unlock_entry(current);
3112 
3113 			/*
3114 			 * If this entry points at a vnode, and the
3115 			 * protection includes VM_PROT_EXECUTE, mark
3116 			 * the vnode as VEXECMAP.
3117 			 */
3118 			if (UVM_ET_ISOBJ(current)) {
3119 				struct uvm_object *uobj =
3120 				    current->object.uvm_obj;
3121 
3122 				if (UVM_OBJ_IS_VNODE(uobj) &&
3123 				    (current->protection & VM_PROT_EXECUTE)) {
3124 					vn_markexec((struct vnode *) uobj);
3125 				}
3126 			}
3127 		}
3128 
3129 		/*
3130 		 * If the map is configured to lock any future mappings,
3131 		 * wire this entry now if the old protection was VM_PROT_NONE
3132 		 * and the new protection is not VM_PROT_NONE.
3133 		 */
3134 
3135 		if ((map->flags & VM_MAP_WIREFUTURE) != 0 &&
3136 		    VM_MAPENT_ISWIRED(entry) == 0 &&
3137 		    old_prot == VM_PROT_NONE &&
3138 		    new_prot != VM_PROT_NONE) {
3139 			if (uvm_map_pageable(map, entry->start,
3140 			    entry->end, false,
3141 			    UVM_LK_ENTER|UVM_LK_EXIT) != 0) {
3142 
3143 				/*
3144 				 * If locking the entry fails, remember the
3145 				 * error if it's the first one.  Note we
3146 				 * still continue setting the protection in
3147 				 * the map, but will return the error
3148 				 * condition regardless.
3149 				 *
3150 				 * XXX Ignore what the actual error is,
3151 				 * XXX just call it a resource shortage
3152 				 * XXX so that it doesn't get confused
3153 				 * XXX what uvm_map_protect() itself would
3154 				 * XXX normally return.
3155 				 */
3156 
3157 				error = ENOMEM;
3158 			}
3159 		}
3160 		current = current->next;
3161 	}
3162 	pmap_update(map->pmap);
3163 
3164  out:
3165 	vm_map_unlock(map);
3166 
3167 	UVMHIST_LOG(maphist, "<- done, error=%jd",error,0,0,0);
3168 	return error;
3169 }
3170 
3171 #undef  MASK
3172 
3173 /*
3174  * uvm_map_inherit: set inheritance code for range of addrs in map.
3175  *
3176  * => map must be unlocked
3177  * => note that the inherit code is used during a "fork".  see fork
3178  *	code for details.
3179  */
3180 
3181 int
3182 uvm_map_inherit(struct vm_map *map, vaddr_t start, vaddr_t end,
3183     vm_inherit_t new_inheritance)
3184 {
3185 	struct vm_map_entry *entry, *temp_entry;
3186 	UVMHIST_FUNC("uvm_map_inherit"); UVMHIST_CALLED(maphist);
3187 	UVMHIST_LOG(maphist,"(map=%#jx,start=%#jx,end=%#jx,new_inh=%#jx)",
3188 	    (uintptr_t)map, start, end, new_inheritance);
3189 
3190 	switch (new_inheritance) {
3191 	case MAP_INHERIT_NONE:
3192 	case MAP_INHERIT_COPY:
3193 	case MAP_INHERIT_SHARE:
3194 	case MAP_INHERIT_ZERO:
3195 		break;
3196 	default:
3197 		UVMHIST_LOG(maphist,"<- done (INVALID ARG)",0,0,0,0);
3198 		return EINVAL;
3199 	}
3200 
3201 	vm_map_lock(map);
3202 	VM_MAP_RANGE_CHECK(map, start, end);
3203 	if (uvm_map_lookup_entry(map, start, &temp_entry)) {
3204 		entry = temp_entry;
3205 		UVM_MAP_CLIP_START(map, entry, start);
3206 	}  else {
3207 		entry = temp_entry->next;
3208 	}
3209 	while ((entry != &map->header) && (entry->start < end)) {
3210 		UVM_MAP_CLIP_END(map, entry, end);
3211 		entry->inheritance = new_inheritance;
3212 		entry = entry->next;
3213 	}
3214 	vm_map_unlock(map);
3215 	UVMHIST_LOG(maphist,"<- done (OK)",0,0,0,0);
3216 	return 0;
3217 }
3218 
3219 /*
3220  * uvm_map_advice: set advice code for range of addrs in map.
3221  *
3222  * => map must be unlocked
3223  */
3224 
3225 int
3226 uvm_map_advice(struct vm_map *map, vaddr_t start, vaddr_t end, int new_advice)
3227 {
3228 	struct vm_map_entry *entry, *temp_entry;
3229 	UVMHIST_FUNC("uvm_map_advice"); UVMHIST_CALLED(maphist);
3230 	UVMHIST_LOG(maphist,"(map=%#jx,start=%#jx,end=%#jx,new_adv=%#jx)",
3231 	    (uintptr_t)map, start, end, new_advice);
3232 
3233 	vm_map_lock(map);
3234 	VM_MAP_RANGE_CHECK(map, start, end);
3235 	if (uvm_map_lookup_entry(map, start, &temp_entry)) {
3236 		entry = temp_entry;
3237 		UVM_MAP_CLIP_START(map, entry, start);
3238 	} else {
3239 		entry = temp_entry->next;
3240 	}
3241 
3242 	/*
3243 	 * XXXJRT: disallow holes?
3244 	 */
3245 
3246 	while ((entry != &map->header) && (entry->start < end)) {
3247 		UVM_MAP_CLIP_END(map, entry, end);
3248 
3249 		switch (new_advice) {
3250 		case MADV_NORMAL:
3251 		case MADV_RANDOM:
3252 		case MADV_SEQUENTIAL:
3253 			/* nothing special here */
3254 			break;
3255 
3256 		default:
3257 			vm_map_unlock(map);
3258 			UVMHIST_LOG(maphist,"<- done (INVALID ARG)",0,0,0,0);
3259 			return EINVAL;
3260 		}
3261 		entry->advice = new_advice;
3262 		entry = entry->next;
3263 	}
3264 
3265 	vm_map_unlock(map);
3266 	UVMHIST_LOG(maphist,"<- done (OK)",0,0,0,0);
3267 	return 0;
3268 }
3269 
3270 /*
3271  * uvm_map_willneed: apply MADV_WILLNEED
3272  */
3273 
3274 int
3275 uvm_map_willneed(struct vm_map *map, vaddr_t start, vaddr_t end)
3276 {
3277 	struct vm_map_entry *entry;
3278 	UVMHIST_FUNC("uvm_map_willneed"); UVMHIST_CALLED(maphist);
3279 	UVMHIST_LOG(maphist,"(map=%#jx,start=%#jx,end=%#jx)",
3280 	    (uintptr_t)map, start, end, 0);
3281 
3282 	vm_map_lock_read(map);
3283 	VM_MAP_RANGE_CHECK(map, start, end);
3284 	if (!uvm_map_lookup_entry(map, start, &entry)) {
3285 		entry = entry->next;
3286 	}
3287 	while (entry->start < end) {
3288 		struct vm_amap * const amap = entry->aref.ar_amap;
3289 		struct uvm_object * const uobj = entry->object.uvm_obj;
3290 
3291 		KASSERT(entry != &map->header);
3292 		KASSERT(start < entry->end);
3293 		/*
3294 		 * For now, we handle only the easy but commonly-requested case.
3295 		 * ie. start prefetching of backing uobj pages.
3296 		 *
3297 		 * XXX It might be useful to pmap_enter() the already-in-core
3298 		 * pages by inventing a "weak" mode for uvm_fault() which would
3299 		 * only do the PGO_LOCKED pgo_get().
3300 		 */
3301 		if (UVM_ET_ISOBJ(entry) && amap == NULL && uobj != NULL) {
3302 			off_t offset;
3303 			off_t size;
3304 
3305 			offset = entry->offset;
3306 			if (start < entry->start) {
3307 				offset += entry->start - start;
3308 			}
3309 			size = entry->offset + (entry->end - entry->start);
3310 			if (entry->end < end) {
3311 				size -= end - entry->end;
3312 			}
3313 			uvm_readahead(uobj, offset, size);
3314 		}
3315 		entry = entry->next;
3316 	}
3317 	vm_map_unlock_read(map);
3318 	UVMHIST_LOG(maphist,"<- done (OK)",0,0,0,0);
3319 	return 0;
3320 }
3321 
3322 /*
3323  * uvm_map_pageable: sets the pageability of a range in a map.
3324  *
3325  * => wires map entries.  should not be used for transient page locking.
3326  *	for that, use uvm_fault_wire()/uvm_fault_unwire() (see uvm_vslock()).
3327  * => regions specified as not pageable require lock-down (wired) memory
3328  *	and page tables.
3329  * => map must never be read-locked
3330  * => if islocked is true, map is already write-locked
3331  * => we always unlock the map, since we must downgrade to a read-lock
3332  *	to call uvm_fault_wire()
3333  * => XXXCDC: check this and try and clean it up.
3334  */
3335 
3336 int
3337 uvm_map_pageable(struct vm_map *map, vaddr_t start, vaddr_t end,
3338     bool new_pageable, int lockflags)
3339 {
3340 	struct vm_map_entry *entry, *start_entry, *failed_entry;
3341 	int rv;
3342 #ifdef DIAGNOSTIC
3343 	u_int timestamp_save;
3344 #endif
3345 	UVMHIST_FUNC("uvm_map_pageable"); UVMHIST_CALLED(maphist);
3346 	UVMHIST_LOG(maphist,"(map=%#jx,start=%#jx,end=%#jx,new_pageable=%ju)",
3347 	    (uintptr_t)map, start, end, new_pageable);
3348 	KASSERT(map->flags & VM_MAP_PAGEABLE);
3349 
3350 	if ((lockflags & UVM_LK_ENTER) == 0)
3351 		vm_map_lock(map);
3352 	VM_MAP_RANGE_CHECK(map, start, end);
3353 
3354 	/*
3355 	 * only one pageability change may take place at one time, since
3356 	 * uvm_fault_wire assumes it will be called only once for each
3357 	 * wiring/unwiring.  therefore, we have to make sure we're actually
3358 	 * changing the pageability for the entire region.  we do so before
3359 	 * making any changes.
3360 	 */
3361 
3362 	if (uvm_map_lookup_entry(map, start, &start_entry) == false) {
3363 		if ((lockflags & UVM_LK_EXIT) == 0)
3364 			vm_map_unlock(map);
3365 
3366 		UVMHIST_LOG(maphist,"<- done (fault)",0,0,0,0);
3367 		return EFAULT;
3368 	}
3369 	entry = start_entry;
3370 
3371 	/*
3372 	 * handle wiring and unwiring separately.
3373 	 */
3374 
3375 	if (new_pageable) {		/* unwire */
3376 		UVM_MAP_CLIP_START(map, entry, start);
3377 
3378 		/*
3379 		 * unwiring.  first ensure that the range to be unwired is
3380 		 * really wired down and that there are no holes.
3381 		 */
3382 
3383 		while ((entry != &map->header) && (entry->start < end)) {
3384 			if (entry->wired_count == 0 ||
3385 			    (entry->end < end &&
3386 			     (entry->next == &map->header ||
3387 			      entry->next->start > entry->end))) {
3388 				if ((lockflags & UVM_LK_EXIT) == 0)
3389 					vm_map_unlock(map);
3390 				UVMHIST_LOG(maphist, "<- done (INVAL)",0,0,0,0);
3391 				return EINVAL;
3392 			}
3393 			entry = entry->next;
3394 		}
3395 
3396 		/*
3397 		 * POSIX 1003.1b - a single munlock call unlocks a region,
3398 		 * regardless of the number of mlock calls made on that
3399 		 * region.
3400 		 */
3401 
3402 		entry = start_entry;
3403 		while ((entry != &map->header) && (entry->start < end)) {
3404 			UVM_MAP_CLIP_END(map, entry, end);
3405 			if (VM_MAPENT_ISWIRED(entry))
3406 				uvm_map_entry_unwire(map, entry);
3407 			entry = entry->next;
3408 		}
3409 		if ((lockflags & UVM_LK_EXIT) == 0)
3410 			vm_map_unlock(map);
3411 		UVMHIST_LOG(maphist,"<- done (OK UNWIRE)",0,0,0,0);
3412 		return 0;
3413 	}
3414 
3415 	/*
3416 	 * wire case: in two passes [XXXCDC: ugly block of code here]
3417 	 *
3418 	 * 1: holding the write lock, we create any anonymous maps that need
3419 	 *    to be created.  then we clip each map entry to the region to
3420 	 *    be wired and increment its wiring count.
3421 	 *
3422 	 * 2: we downgrade to a read lock, and call uvm_fault_wire to fault
3423 	 *    in the pages for any newly wired area (wired_count == 1).
3424 	 *
3425 	 *    downgrading to a read lock for uvm_fault_wire avoids a possible
3426 	 *    deadlock with another thread that may have faulted on one of
3427 	 *    the pages to be wired (it would mark the page busy, blocking
3428 	 *    us, then in turn block on the map lock that we hold).  because
3429 	 *    of problems in the recursive lock package, we cannot upgrade
3430 	 *    to a write lock in vm_map_lookup.  thus, any actions that
3431 	 *    require the write lock must be done beforehand.  because we
3432 	 *    keep the read lock on the map, the copy-on-write status of the
3433 	 *    entries we modify here cannot change.
3434 	 */
3435 
3436 	while ((entry != &map->header) && (entry->start < end)) {
3437 		if (VM_MAPENT_ISWIRED(entry) == 0) { /* not already wired? */
3438 
3439 			/*
3440 			 * perform actions of vm_map_lookup that need the
3441 			 * write lock on the map: create an anonymous map
3442 			 * for a copy-on-write region, or an anonymous map
3443 			 * for a zero-fill region.  (XXXCDC: submap case
3444 			 * ok?)
3445 			 */
3446 
3447 			if (!UVM_ET_ISSUBMAP(entry)) {  /* not submap */
3448 				if (UVM_ET_ISNEEDSCOPY(entry) &&
3449 				    ((entry->max_protection & VM_PROT_WRITE) ||
3450 				     (entry->object.uvm_obj == NULL))) {
3451 					amap_copy(map, entry, 0, start, end);
3452 					/* XXXCDC: wait OK? */
3453 				}
3454 			}
3455 		}
3456 		UVM_MAP_CLIP_START(map, entry, start);
3457 		UVM_MAP_CLIP_END(map, entry, end);
3458 		entry->wired_count++;
3459 
3460 		/*
3461 		 * Check for holes
3462 		 */
3463 
3464 		if (entry->protection == VM_PROT_NONE ||
3465 		    (entry->end < end &&
3466 		     (entry->next == &map->header ||
3467 		      entry->next->start > entry->end))) {
3468 
3469 			/*
3470 			 * found one.  amap creation actions do not need to
3471 			 * be undone, but the wired counts need to be restored.
3472 			 */
3473 
3474 			while (entry != &map->header && entry->end > start) {
3475 				entry->wired_count--;
3476 				entry = entry->prev;
3477 			}
3478 			if ((lockflags & UVM_LK_EXIT) == 0)
3479 				vm_map_unlock(map);
3480 			UVMHIST_LOG(maphist,"<- done (INVALID WIRE)",0,0,0,0);
3481 			return EINVAL;
3482 		}
3483 		entry = entry->next;
3484 	}
3485 
3486 	/*
3487 	 * Pass 2.
3488 	 */
3489 
3490 #ifdef DIAGNOSTIC
3491 	timestamp_save = map->timestamp;
3492 #endif
3493 	vm_map_busy(map);
3494 	vm_map_unlock(map);
3495 
3496 	rv = 0;
3497 	entry = start_entry;
3498 	while (entry != &map->header && entry->start < end) {
3499 		if (entry->wired_count == 1) {
3500 			rv = uvm_fault_wire(map, entry->start, entry->end,
3501 			    entry->max_protection, 1);
3502 			if (rv) {
3503 
3504 				/*
3505 				 * wiring failed.  break out of the loop.
3506 				 * we'll clean up the map below, once we
3507 				 * have a write lock again.
3508 				 */
3509 
3510 				break;
3511 			}
3512 		}
3513 		entry = entry->next;
3514 	}
3515 
3516 	if (rv) {	/* failed? */
3517 
3518 		/*
3519 		 * Get back to an exclusive (write) lock.
3520 		 */
3521 
3522 		vm_map_lock(map);
3523 		vm_map_unbusy(map);
3524 
3525 #ifdef DIAGNOSTIC
3526 		if (timestamp_save + 1 != map->timestamp)
3527 			panic("uvm_map_pageable: stale map");
3528 #endif
3529 
3530 		/*
3531 		 * first drop the wiring count on all the entries
3532 		 * which haven't actually been wired yet.
3533 		 */
3534 
3535 		failed_entry = entry;
3536 		while (entry != &map->header && entry->start < end) {
3537 			entry->wired_count--;
3538 			entry = entry->next;
3539 		}
3540 
3541 		/*
3542 		 * now, unwire all the entries that were successfully
3543 		 * wired above.
3544 		 */
3545 
3546 		entry = start_entry;
3547 		while (entry != failed_entry) {
3548 			entry->wired_count--;
3549 			if (VM_MAPENT_ISWIRED(entry) == 0)
3550 				uvm_map_entry_unwire(map, entry);
3551 			entry = entry->next;
3552 		}
3553 		if ((lockflags & UVM_LK_EXIT) == 0)
3554 			vm_map_unlock(map);
3555 		UVMHIST_LOG(maphist, "<- done (RV=%jd)", rv,0,0,0);
3556 		return (rv);
3557 	}
3558 
3559 	if ((lockflags & UVM_LK_EXIT) == 0) {
3560 		vm_map_unbusy(map);
3561 	} else {
3562 
3563 		/*
3564 		 * Get back to an exclusive (write) lock.
3565 		 */
3566 
3567 		vm_map_lock(map);
3568 		vm_map_unbusy(map);
3569 	}
3570 
3571 	UVMHIST_LOG(maphist,"<- done (OK WIRE)",0,0,0,0);
3572 	return 0;
3573 }
3574 
3575 /*
3576  * uvm_map_pageable_all: special case of uvm_map_pageable - affects
3577  * all mapped regions.
3578  *
3579  * => map must not be locked.
3580  * => if no flags are specified, all regions are unwired.
3581  * => XXXJRT: has some of the same problems as uvm_map_pageable() above.
3582  */
3583 
3584 int
3585 uvm_map_pageable_all(struct vm_map *map, int flags, vsize_t limit)
3586 {
3587 	struct vm_map_entry *entry, *failed_entry;
3588 	vsize_t size;
3589 	int rv;
3590 #ifdef DIAGNOSTIC
3591 	u_int timestamp_save;
3592 #endif
3593 	UVMHIST_FUNC("uvm_map_pageable_all"); UVMHIST_CALLED(maphist);
3594 	UVMHIST_LOG(maphist,"(map=%#jx,flags=%#jx)", (uintptr_t)map, flags,
3595 	    0, 0);
3596 
3597 	KASSERT(map->flags & VM_MAP_PAGEABLE);
3598 
3599 	vm_map_lock(map);
3600 
3601 	/*
3602 	 * handle wiring and unwiring separately.
3603 	 */
3604 
3605 	if (flags == 0) {			/* unwire */
3606 
3607 		/*
3608 		 * POSIX 1003.1b -- munlockall unlocks all regions,
3609 		 * regardless of how many times mlockall has been called.
3610 		 */
3611 
3612 		for (entry = map->header.next; entry != &map->header;
3613 		     entry = entry->next) {
3614 			if (VM_MAPENT_ISWIRED(entry))
3615 				uvm_map_entry_unwire(map, entry);
3616 		}
3617 		map->flags &= ~VM_MAP_WIREFUTURE;
3618 		vm_map_unlock(map);
3619 		UVMHIST_LOG(maphist,"<- done (OK UNWIRE)",0,0,0,0);
3620 		return 0;
3621 	}
3622 
3623 	if (flags & MCL_FUTURE) {
3624 
3625 		/*
3626 		 * must wire all future mappings; remember this.
3627 		 */
3628 
3629 		map->flags |= VM_MAP_WIREFUTURE;
3630 	}
3631 
3632 	if ((flags & MCL_CURRENT) == 0) {
3633 
3634 		/*
3635 		 * no more work to do!
3636 		 */
3637 
3638 		UVMHIST_LOG(maphist,"<- done (OK no wire)",0,0,0,0);
3639 		vm_map_unlock(map);
3640 		return 0;
3641 	}
3642 
3643 	/*
3644 	 * wire case: in three passes [XXXCDC: ugly block of code here]
3645 	 *
3646 	 * 1: holding the write lock, count all pages mapped by non-wired
3647 	 *    entries.  if this would cause us to go over our limit, we fail.
3648 	 *
3649 	 * 2: still holding the write lock, we create any anonymous maps that
3650 	 *    need to be created.  then we increment its wiring count.
3651 	 *
3652 	 * 3: we downgrade to a read lock, and call uvm_fault_wire to fault
3653 	 *    in the pages for any newly wired area (wired_count == 1).
3654 	 *
3655 	 *    downgrading to a read lock for uvm_fault_wire avoids a possible
3656 	 *    deadlock with another thread that may have faulted on one of
3657 	 *    the pages to be wired (it would mark the page busy, blocking
3658 	 *    us, then in turn block on the map lock that we hold).  because
3659 	 *    of problems in the recursive lock package, we cannot upgrade
3660 	 *    to a write lock in vm_map_lookup.  thus, any actions that
3661 	 *    require the write lock must be done beforehand.  because we
3662 	 *    keep the read lock on the map, the copy-on-write status of the
3663 	 *    entries we modify here cannot change.
3664 	 */
3665 
3666 	for (size = 0, entry = map->header.next; entry != &map->header;
3667 	     entry = entry->next) {
3668 		if (entry->protection != VM_PROT_NONE &&
3669 		    VM_MAPENT_ISWIRED(entry) == 0) { /* not already wired? */
3670 			size += entry->end - entry->start;
3671 		}
3672 	}
3673 
3674 	if (atop(size) + uvmexp.wired > uvmexp.wiredmax) {
3675 		vm_map_unlock(map);
3676 		return ENOMEM;
3677 	}
3678 
3679 	if (limit != 0 &&
3680 	    (size + ptoa(pmap_wired_count(vm_map_pmap(map))) > limit)) {
3681 		vm_map_unlock(map);
3682 		return ENOMEM;
3683 	}
3684 
3685 	/*
3686 	 * Pass 2.
3687 	 */
3688 
3689 	for (entry = map->header.next; entry != &map->header;
3690 	     entry = entry->next) {
3691 		if (entry->protection == VM_PROT_NONE)
3692 			continue;
3693 		if (VM_MAPENT_ISWIRED(entry) == 0) { /* not already wired? */
3694 
3695 			/*
3696 			 * perform actions of vm_map_lookup that need the
3697 			 * write lock on the map: create an anonymous map
3698 			 * for a copy-on-write region, or an anonymous map
3699 			 * for a zero-fill region.  (XXXCDC: submap case
3700 			 * ok?)
3701 			 */
3702 
3703 			if (!UVM_ET_ISSUBMAP(entry)) {	/* not submap */
3704 				if (UVM_ET_ISNEEDSCOPY(entry) &&
3705 				    ((entry->max_protection & VM_PROT_WRITE) ||
3706 				     (entry->object.uvm_obj == NULL))) {
3707 					amap_copy(map, entry, 0, entry->start,
3708 					    entry->end);
3709 					/* XXXCDC: wait OK? */
3710 				}
3711 			}
3712 		}
3713 		entry->wired_count++;
3714 	}
3715 
3716 	/*
3717 	 * Pass 3.
3718 	 */
3719 
3720 #ifdef DIAGNOSTIC
3721 	timestamp_save = map->timestamp;
3722 #endif
3723 	vm_map_busy(map);
3724 	vm_map_unlock(map);
3725 
3726 	rv = 0;
3727 	for (entry = map->header.next; entry != &map->header;
3728 	     entry = entry->next) {
3729 		if (entry->wired_count == 1) {
3730 			rv = uvm_fault_wire(map, entry->start, entry->end,
3731 			    entry->max_protection, 1);
3732 			if (rv) {
3733 
3734 				/*
3735 				 * wiring failed.  break out of the loop.
3736 				 * we'll clean up the map below, once we
3737 				 * have a write lock again.
3738 				 */
3739 
3740 				break;
3741 			}
3742 		}
3743 	}
3744 
3745 	if (rv) {
3746 
3747 		/*
3748 		 * Get back an exclusive (write) lock.
3749 		 */
3750 
3751 		vm_map_lock(map);
3752 		vm_map_unbusy(map);
3753 
3754 #ifdef DIAGNOSTIC
3755 		if (timestamp_save + 1 != map->timestamp)
3756 			panic("uvm_map_pageable_all: stale map");
3757 #endif
3758 
3759 		/*
3760 		 * first drop the wiring count on all the entries
3761 		 * which haven't actually been wired yet.
3762 		 *
3763 		 * Skip VM_PROT_NONE entries like we did above.
3764 		 */
3765 
3766 		failed_entry = entry;
3767 		for (/* nothing */; entry != &map->header;
3768 		     entry = entry->next) {
3769 			if (entry->protection == VM_PROT_NONE)
3770 				continue;
3771 			entry->wired_count--;
3772 		}
3773 
3774 		/*
3775 		 * now, unwire all the entries that were successfully
3776 		 * wired above.
3777 		 *
3778 		 * Skip VM_PROT_NONE entries like we did above.
3779 		 */
3780 
3781 		for (entry = map->header.next; entry != failed_entry;
3782 		     entry = entry->next) {
3783 			if (entry->protection == VM_PROT_NONE)
3784 				continue;
3785 			entry->wired_count--;
3786 			if (VM_MAPENT_ISWIRED(entry))
3787 				uvm_map_entry_unwire(map, entry);
3788 		}
3789 		vm_map_unlock(map);
3790 		UVMHIST_LOG(maphist,"<- done (RV=%jd)", rv,0,0,0);
3791 		return (rv);
3792 	}
3793 
3794 	vm_map_unbusy(map);
3795 
3796 	UVMHIST_LOG(maphist,"<- done (OK WIRE)",0,0,0,0);
3797 	return 0;
3798 }
3799 
3800 /*
3801  * uvm_map_clean: clean out a map range
3802  *
3803  * => valid flags:
3804  *   if (flags & PGO_CLEANIT): dirty pages are cleaned first
3805  *   if (flags & PGO_SYNCIO): dirty pages are written synchronously
3806  *   if (flags & PGO_DEACTIVATE): any cached pages are deactivated after clean
3807  *   if (flags & PGO_FREE): any cached pages are freed after clean
3808  * => returns an error if any part of the specified range isn't mapped
3809  * => never a need to flush amap layer since the anonymous memory has
3810  *	no permanent home, but may deactivate pages there
3811  * => called from sys_msync() and sys_madvise()
3812  * => caller must not write-lock map (read OK).
3813  * => we may sleep while cleaning if SYNCIO [with map read-locked]
3814  */
3815 
3816 int
3817 uvm_map_clean(struct vm_map *map, vaddr_t start, vaddr_t end, int flags)
3818 {
3819 	struct vm_map_entry *current, *entry;
3820 	struct uvm_object *uobj;
3821 	struct vm_amap *amap;
3822 	struct vm_anon *anon, *anon_tofree;
3823 	struct vm_page *pg;
3824 	vaddr_t offset;
3825 	vsize_t size;
3826 	voff_t uoff;
3827 	int error, refs;
3828 	UVMHIST_FUNC("uvm_map_clean"); UVMHIST_CALLED(maphist);
3829 
3830 	UVMHIST_LOG(maphist,"(map=%#jx,start=%#jx,end=%#jx,flags=%#jx)",
3831 	    (uintptr_t)map, start, end, flags);
3832 	KASSERT((flags & (PGO_FREE|PGO_DEACTIVATE)) !=
3833 		(PGO_FREE|PGO_DEACTIVATE));
3834 
3835 	vm_map_lock_read(map);
3836 	VM_MAP_RANGE_CHECK(map, start, end);
3837 	if (uvm_map_lookup_entry(map, start, &entry) == false) {
3838 		vm_map_unlock_read(map);
3839 		return EFAULT;
3840 	}
3841 
3842 	/*
3843 	 * Make a first pass to check for holes and wiring problems.
3844 	 */
3845 
3846 	for (current = entry; current->start < end; current = current->next) {
3847 		if (UVM_ET_ISSUBMAP(current)) {
3848 			vm_map_unlock_read(map);
3849 			return EINVAL;
3850 		}
3851 		if ((flags & PGO_FREE) != 0 && VM_MAPENT_ISWIRED(entry)) {
3852 			vm_map_unlock_read(map);
3853 			return EBUSY;
3854 		}
3855 		if (end <= current->end) {
3856 			break;
3857 		}
3858 		if (current->end != current->next->start) {
3859 			vm_map_unlock_read(map);
3860 			return EFAULT;
3861 		}
3862 	}
3863 
3864 	error = 0;
3865 	for (current = entry; start < end; current = current->next) {
3866 		amap = current->aref.ar_amap;	/* upper layer */
3867 		uobj = current->object.uvm_obj;	/* lower layer */
3868 		KASSERT(start >= current->start);
3869 
3870 		/*
3871 		 * No amap cleaning necessary if:
3872 		 *
3873 		 *	(1) There's no amap.
3874 		 *
3875 		 *	(2) We're not deactivating or freeing pages.
3876 		 */
3877 
3878 		if (amap == NULL || (flags & (PGO_DEACTIVATE|PGO_FREE)) == 0)
3879 			goto flush_object;
3880 
3881 		offset = start - current->start;
3882 		size = MIN(end, current->end) - start;
3883 		anon_tofree = NULL;
3884 
3885 		amap_lock(amap);
3886 		for ( ; size != 0; size -= PAGE_SIZE, offset += PAGE_SIZE) {
3887 			anon = amap_lookup(&current->aref, offset);
3888 			if (anon == NULL)
3889 				continue;
3890 
3891 			KASSERT(anon->an_lock == amap->am_lock);
3892 			pg = anon->an_page;
3893 			if (pg == NULL) {
3894 				continue;
3895 			}
3896 			if (pg->flags & PG_BUSY) {
3897 				continue;
3898 			}
3899 
3900 			switch (flags & (PGO_CLEANIT|PGO_FREE|PGO_DEACTIVATE)) {
3901 
3902 			/*
3903 			 * In these first 3 cases, we just deactivate the page.
3904 			 */
3905 
3906 			case PGO_CLEANIT|PGO_FREE:
3907 			case PGO_CLEANIT|PGO_DEACTIVATE:
3908 			case PGO_DEACTIVATE:
3909  deactivate_it:
3910 				/*
3911 				 * skip the page if it's loaned or wired,
3912 				 * since it shouldn't be on a paging queue
3913 				 * at all in these cases.
3914 				 */
3915 
3916 				mutex_enter(&uvm_pageqlock);
3917 				if (pg->loan_count != 0 ||
3918 				    pg->wire_count != 0) {
3919 					mutex_exit(&uvm_pageqlock);
3920 					continue;
3921 				}
3922 				KASSERT(pg->uanon == anon);
3923 				uvm_pagedeactivate(pg);
3924 				mutex_exit(&uvm_pageqlock);
3925 				continue;
3926 
3927 			case PGO_FREE:
3928 
3929 				/*
3930 				 * If there are multiple references to
3931 				 * the amap, just deactivate the page.
3932 				 */
3933 
3934 				if (amap_refs(amap) > 1)
3935 					goto deactivate_it;
3936 
3937 				/* skip the page if it's wired */
3938 				if (pg->wire_count != 0) {
3939 					continue;
3940 				}
3941 				amap_unadd(&current->aref, offset);
3942 				refs = --anon->an_ref;
3943 				if (refs == 0) {
3944 					anon->an_link = anon_tofree;
3945 					anon_tofree = anon;
3946 				}
3947 				continue;
3948 			}
3949 		}
3950 		uvm_anon_freelst(amap, anon_tofree);
3951 
3952  flush_object:
3953 		/*
3954 		 * flush pages if we've got a valid backing object.
3955 		 * note that we must always clean object pages before
3956 		 * freeing them since otherwise we could reveal stale
3957 		 * data from files.
3958 		 */
3959 
3960 		uoff = current->offset + (start - current->start);
3961 		size = MIN(end, current->end) - start;
3962 		if (uobj != NULL) {
3963 			mutex_enter(uobj->vmobjlock);
3964 			if (uobj->pgops->pgo_put != NULL)
3965 				error = (uobj->pgops->pgo_put)(uobj, uoff,
3966 				    uoff + size, flags | PGO_CLEANIT);
3967 			else
3968 				error = 0;
3969 		}
3970 		start += size;
3971 	}
3972 	vm_map_unlock_read(map);
3973 	return (error);
3974 }
3975 
3976 
3977 /*
3978  * uvm_map_checkprot: check protection in map
3979  *
3980  * => must allow specified protection in a fully allocated region.
3981  * => map must be read or write locked by caller.
3982  */
3983 
3984 bool
3985 uvm_map_checkprot(struct vm_map *map, vaddr_t start, vaddr_t end,
3986     vm_prot_t protection)
3987 {
3988 	struct vm_map_entry *entry;
3989 	struct vm_map_entry *tmp_entry;
3990 
3991 	if (!uvm_map_lookup_entry(map, start, &tmp_entry)) {
3992 		return (false);
3993 	}
3994 	entry = tmp_entry;
3995 	while (start < end) {
3996 		if (entry == &map->header) {
3997 			return (false);
3998 		}
3999 
4000 		/*
4001 		 * no holes allowed
4002 		 */
4003 
4004 		if (start < entry->start) {
4005 			return (false);
4006 		}
4007 
4008 		/*
4009 		 * check protection associated with entry
4010 		 */
4011 
4012 		if ((entry->protection & protection) != protection) {
4013 			return (false);
4014 		}
4015 		start = entry->end;
4016 		entry = entry->next;
4017 	}
4018 	return (true);
4019 }
4020 
4021 /*
4022  * uvmspace_alloc: allocate a vmspace structure.
4023  *
4024  * - structure includes vm_map and pmap
4025  * - XXX: no locking on this structure
4026  * - refcnt set to 1, rest must be init'd by caller
4027  */
4028 struct vmspace *
4029 uvmspace_alloc(vaddr_t vmin, vaddr_t vmax, bool topdown)
4030 {
4031 	struct vmspace *vm;
4032 	UVMHIST_FUNC("uvmspace_alloc"); UVMHIST_CALLED(maphist);
4033 
4034 	vm = pool_cache_get(&uvm_vmspace_cache, PR_WAITOK);
4035 	uvmspace_init(vm, NULL, vmin, vmax, topdown);
4036 	UVMHIST_LOG(maphist,"<- done (vm=%#jx)", (uintptr_t)vm, 0, 0, 0);
4037 	return (vm);
4038 }
4039 
4040 /*
4041  * uvmspace_init: initialize a vmspace structure.
4042  *
4043  * - XXX: no locking on this structure
4044  * - refcnt set to 1, rest must be init'd by caller
4045  */
4046 void
4047 uvmspace_init(struct vmspace *vm, struct pmap *pmap, vaddr_t vmin,
4048     vaddr_t vmax, bool topdown)
4049 {
4050 	UVMHIST_FUNC("uvmspace_init"); UVMHIST_CALLED(maphist);
4051 
4052 	UVMHIST_LOG(maphist, "(vm=%#jx, pmap=%#jx, vmin=%#jx, vmax=%#jx",
4053 	    (uintptr_t)vm, (uintptr_t)pmap, vmin, vmax);
4054 	UVMHIST_LOG(maphist, "   topdown=%ju)", topdown, 0, 0, 0);
4055 
4056 	memset(vm, 0, sizeof(*vm));
4057 	uvm_map_setup(&vm->vm_map, vmin, vmax, VM_MAP_PAGEABLE
4058 	    | (topdown ? VM_MAP_TOPDOWN : 0)
4059 	    );
4060 	if (pmap)
4061 		pmap_reference(pmap);
4062 	else
4063 		pmap = pmap_create();
4064 	vm->vm_map.pmap = pmap;
4065 	vm->vm_refcnt = 1;
4066 	UVMHIST_LOG(maphist,"<- done",0,0,0,0);
4067 }
4068 
4069 /*
4070  * uvmspace_share: share a vmspace between two processes
4071  *
4072  * - used for vfork, threads(?)
4073  */
4074 
4075 void
4076 uvmspace_share(struct proc *p1, struct proc *p2)
4077 {
4078 
4079 	uvmspace_addref(p1->p_vmspace);
4080 	p2->p_vmspace = p1->p_vmspace;
4081 }
4082 
4083 #if 0
4084 
4085 /*
4086  * uvmspace_unshare: ensure that process "p" has its own, unshared, vmspace
4087  *
4088  * - XXX: no locking on vmspace
4089  */
4090 
4091 void
4092 uvmspace_unshare(struct lwp *l)
4093 {
4094 	struct proc *p = l->l_proc;
4095 	struct vmspace *nvm, *ovm = p->p_vmspace;
4096 
4097 	if (ovm->vm_refcnt == 1)
4098 		/* nothing to do: vmspace isn't shared in the first place */
4099 		return;
4100 
4101 	/* make a new vmspace, still holding old one */
4102 	nvm = uvmspace_fork(ovm);
4103 
4104 	kpreempt_disable();
4105 	pmap_deactivate(l);		/* unbind old vmspace */
4106 	p->p_vmspace = nvm;
4107 	pmap_activate(l);		/* switch to new vmspace */
4108 	kpreempt_enable();
4109 
4110 	uvmspace_free(ovm);		/* drop reference to old vmspace */
4111 }
4112 
4113 #endif
4114 
4115 
4116 /*
4117  * uvmspace_spawn: a new process has been spawned and needs a vmspace
4118  */
4119 
4120 void
4121 uvmspace_spawn(struct lwp *l, vaddr_t start, vaddr_t end, bool topdown)
4122 {
4123 	struct proc *p = l->l_proc;
4124 	struct vmspace *nvm;
4125 
4126 #ifdef __HAVE_CPU_VMSPACE_EXEC
4127 	cpu_vmspace_exec(l, start, end);
4128 #endif
4129 
4130 	nvm = uvmspace_alloc(start, end, topdown);
4131 	kpreempt_disable();
4132 	p->p_vmspace = nvm;
4133 	pmap_activate(l);
4134 	kpreempt_enable();
4135 }
4136 
4137 /*
4138  * uvmspace_exec: the process wants to exec a new program
4139  */
4140 
4141 void
4142 uvmspace_exec(struct lwp *l, vaddr_t start, vaddr_t end, bool topdown)
4143 {
4144 	struct proc *p = l->l_proc;
4145 	struct vmspace *nvm, *ovm = p->p_vmspace;
4146 	struct vm_map *map;
4147 
4148 	KASSERT(ovm != NULL);
4149 #ifdef __HAVE_CPU_VMSPACE_EXEC
4150 	cpu_vmspace_exec(l, start, end);
4151 #endif
4152 
4153 	map = &ovm->vm_map;
4154 	/*
4155 	 * see if more than one process is using this vmspace...
4156 	 */
4157 
4158 	if (ovm->vm_refcnt == 1
4159 	    && topdown == ((ovm->vm_map.flags & VM_MAP_TOPDOWN) != 0)) {
4160 
4161 		/*
4162 		 * if p is the only process using its vmspace then we can safely
4163 		 * recycle that vmspace for the program that is being exec'd.
4164 		 * But only if TOPDOWN matches the requested value for the new
4165 		 * vm space!
4166 		 */
4167 
4168 		/*
4169 		 * SYSV SHM semantics require us to kill all segments on an exec
4170 		 */
4171 		if (uvm_shmexit && ovm->vm_shm)
4172 			(*uvm_shmexit)(ovm);
4173 
4174 		/*
4175 		 * POSIX 1003.1b -- "lock future mappings" is revoked
4176 		 * when a process execs another program image.
4177 		 */
4178 
4179 		map->flags &= ~VM_MAP_WIREFUTURE;
4180 
4181 		/*
4182 		 * now unmap the old program
4183 		 */
4184 
4185 		pmap_remove_all(map->pmap);
4186 		uvm_unmap(map, vm_map_min(map), vm_map_max(map));
4187 		KASSERT(map->header.prev == &map->header);
4188 		KASSERT(map->nentries == 0);
4189 
4190 		/*
4191 		 * resize the map
4192 		 */
4193 
4194 		vm_map_setmin(map, start);
4195 		vm_map_setmax(map, end);
4196 	} else {
4197 
4198 		/*
4199 		 * p's vmspace is being shared, so we can't reuse it for p since
4200 		 * it is still being used for others.   allocate a new vmspace
4201 		 * for p
4202 		 */
4203 
4204 		nvm = uvmspace_alloc(start, end, topdown);
4205 
4206 		/*
4207 		 * install new vmspace and drop our ref to the old one.
4208 		 */
4209 
4210 		kpreempt_disable();
4211 		pmap_deactivate(l);
4212 		p->p_vmspace = nvm;
4213 		pmap_activate(l);
4214 		kpreempt_enable();
4215 
4216 		uvmspace_free(ovm);
4217 	}
4218 }
4219 
4220 /*
4221  * uvmspace_addref: add a referece to a vmspace.
4222  */
4223 
4224 void
4225 uvmspace_addref(struct vmspace *vm)
4226 {
4227 	struct vm_map *map = &vm->vm_map;
4228 
4229 	KASSERT((map->flags & VM_MAP_DYING) == 0);
4230 
4231 	mutex_enter(&map->misc_lock);
4232 	KASSERT(vm->vm_refcnt > 0);
4233 	vm->vm_refcnt++;
4234 	mutex_exit(&map->misc_lock);
4235 }
4236 
4237 /*
4238  * uvmspace_free: free a vmspace data structure
4239  */
4240 
4241 void
4242 uvmspace_free(struct vmspace *vm)
4243 {
4244 	struct vm_map_entry *dead_entries;
4245 	struct vm_map *map = &vm->vm_map;
4246 	int n;
4247 
4248 	UVMHIST_FUNC("uvmspace_free"); UVMHIST_CALLED(maphist);
4249 
4250 	UVMHIST_LOG(maphist,"(vm=%#jx) ref=%jd", (uintptr_t)vm, vm->vm_refcnt,
4251 	    0, 0);
4252 	mutex_enter(&map->misc_lock);
4253 	n = --vm->vm_refcnt;
4254 	mutex_exit(&map->misc_lock);
4255 	if (n > 0)
4256 		return;
4257 
4258 	/*
4259 	 * at this point, there should be no other references to the map.
4260 	 * delete all of the mappings, then destroy the pmap.
4261 	 */
4262 
4263 	map->flags |= VM_MAP_DYING;
4264 	pmap_remove_all(map->pmap);
4265 
4266 	/* Get rid of any SYSV shared memory segments. */
4267 	if (uvm_shmexit && vm->vm_shm != NULL)
4268 		(*uvm_shmexit)(vm);
4269 
4270 	if (map->nentries) {
4271 		uvm_unmap_remove(map, vm_map_min(map), vm_map_max(map),
4272 		    &dead_entries, 0);
4273 		if (dead_entries != NULL)
4274 			uvm_unmap_detach(dead_entries, 0);
4275 	}
4276 	KASSERT(map->nentries == 0);
4277 	KASSERT(map->size == 0);
4278 
4279 	mutex_destroy(&map->misc_lock);
4280 	rw_destroy(&map->lock);
4281 	cv_destroy(&map->cv);
4282 	pmap_destroy(map->pmap);
4283 	pool_cache_put(&uvm_vmspace_cache, vm);
4284 }
4285 
4286 static struct vm_map_entry *
4287 uvm_mapent_clone(struct vm_map *new_map, struct vm_map_entry *old_entry,
4288     int flags)
4289 {
4290 	struct vm_map_entry *new_entry;
4291 
4292 	new_entry = uvm_mapent_alloc(new_map, 0);
4293 	/* old_entry -> new_entry */
4294 	uvm_mapent_copy(old_entry, new_entry);
4295 
4296 	/* new pmap has nothing wired in it */
4297 	new_entry->wired_count = 0;
4298 
4299 	/*
4300 	 * gain reference to object backing the map (can't
4301 	 * be a submap, already checked this case).
4302 	 */
4303 
4304 	if (new_entry->aref.ar_amap)
4305 		uvm_map_reference_amap(new_entry, flags);
4306 
4307 	if (new_entry->object.uvm_obj &&
4308 	    new_entry->object.uvm_obj->pgops->pgo_reference)
4309 		new_entry->object.uvm_obj->pgops->pgo_reference(
4310 			new_entry->object.uvm_obj);
4311 
4312 	/* insert entry at end of new_map's entry list */
4313 	uvm_map_entry_link(new_map, new_map->header.prev,
4314 	    new_entry);
4315 
4316 	return new_entry;
4317 }
4318 
4319 /*
4320  * share the mapping: this means we want the old and
4321  * new entries to share amaps and backing objects.
4322  */
4323 static void
4324 uvm_mapent_forkshared(struct vm_map *new_map, struct vm_map *old_map,
4325     struct vm_map_entry *old_entry)
4326 {
4327 	/*
4328 	 * if the old_entry needs a new amap (due to prev fork)
4329 	 * then we need to allocate it now so that we have
4330 	 * something we own to share with the new_entry.   [in
4331 	 * other words, we need to clear needs_copy]
4332 	 */
4333 
4334 	if (UVM_ET_ISNEEDSCOPY(old_entry)) {
4335 		/* get our own amap, clears needs_copy */
4336 		amap_copy(old_map, old_entry, AMAP_COPY_NOCHUNK,
4337 		    0, 0);
4338 		/* XXXCDC: WAITOK??? */
4339 	}
4340 
4341 	uvm_mapent_clone(new_map, old_entry, AMAP_SHARED);
4342 }
4343 
4344 
4345 static void
4346 uvm_mapent_forkcopy(struct vm_map *new_map, struct vm_map *old_map,
4347     struct vm_map_entry *old_entry)
4348 {
4349 	struct vm_map_entry *new_entry;
4350 
4351 	/*
4352 	 * copy-on-write the mapping (using mmap's
4353 	 * MAP_PRIVATE semantics)
4354 	 *
4355 	 * allocate new_entry, adjust reference counts.
4356 	 * (note that new references are read-only).
4357 	 */
4358 
4359 	new_entry = uvm_mapent_clone(new_map, old_entry, 0);
4360 
4361 	new_entry->etype |=
4362 	    (UVM_ET_COPYONWRITE|UVM_ET_NEEDSCOPY);
4363 
4364 	/*
4365 	 * the new entry will need an amap.  it will either
4366 	 * need to be copied from the old entry or created
4367 	 * from scratch (if the old entry does not have an
4368 	 * amap).  can we defer this process until later
4369 	 * (by setting "needs_copy") or do we need to copy
4370 	 * the amap now?
4371 	 *
4372 	 * we must copy the amap now if any of the following
4373 	 * conditions hold:
4374 	 * 1. the old entry has an amap and that amap is
4375 	 *    being shared.  this means that the old (parent)
4376 	 *    process is sharing the amap with another
4377 	 *    process.  if we do not clear needs_copy here
4378 	 *    we will end up in a situation where both the
4379 	 *    parent and child process are refering to the
4380 	 *    same amap with "needs_copy" set.  if the
4381 	 *    parent write-faults, the fault routine will
4382 	 *    clear "needs_copy" in the parent by allocating
4383 	 *    a new amap.   this is wrong because the
4384 	 *    parent is supposed to be sharing the old amap
4385 	 *    and the new amap will break that.
4386 	 *
4387 	 * 2. if the old entry has an amap and a non-zero
4388 	 *    wire count then we are going to have to call
4389 	 *    amap_cow_now to avoid page faults in the
4390 	 *    parent process.   since amap_cow_now requires
4391 	 *    "needs_copy" to be clear we might as well
4392 	 *    clear it here as well.
4393 	 *
4394 	 */
4395 
4396 	if (old_entry->aref.ar_amap != NULL) {
4397 		if ((amap_flags(old_entry->aref.ar_amap) & AMAP_SHARED) != 0 ||
4398 		    VM_MAPENT_ISWIRED(old_entry)) {
4399 
4400 			amap_copy(new_map, new_entry,
4401 			    AMAP_COPY_NOCHUNK, 0, 0);
4402 			/* XXXCDC: M_WAITOK ... ok? */
4403 		}
4404 	}
4405 
4406 	/*
4407 	 * if the parent's entry is wired down, then the
4408 	 * parent process does not want page faults on
4409 	 * access to that memory.  this means that we
4410 	 * cannot do copy-on-write because we can't write
4411 	 * protect the old entry.   in this case we
4412 	 * resolve all copy-on-write faults now, using
4413 	 * amap_cow_now.   note that we have already
4414 	 * allocated any needed amap (above).
4415 	 */
4416 
4417 	if (VM_MAPENT_ISWIRED(old_entry)) {
4418 
4419 		/*
4420 		 * resolve all copy-on-write faults now
4421 		 * (note that there is nothing to do if
4422 		 * the old mapping does not have an amap).
4423 		 */
4424 		if (old_entry->aref.ar_amap)
4425 			amap_cow_now(new_map, new_entry);
4426 
4427 	} else {
4428 		/*
4429 		 * setup mappings to trigger copy-on-write faults
4430 		 * we must write-protect the parent if it has
4431 		 * an amap and it is not already "needs_copy"...
4432 		 * if it is already "needs_copy" then the parent
4433 		 * has already been write-protected by a previous
4434 		 * fork operation.
4435 		 */
4436 		if (old_entry->aref.ar_amap &&
4437 		    !UVM_ET_ISNEEDSCOPY(old_entry)) {
4438 			if (old_entry->max_protection & VM_PROT_WRITE) {
4439 				pmap_protect(old_map->pmap,
4440 				    old_entry->start, old_entry->end,
4441 				    old_entry->protection & ~VM_PROT_WRITE);
4442 			}
4443 			old_entry->etype |= UVM_ET_NEEDSCOPY;
4444 		}
4445 	}
4446 }
4447 
4448 /*
4449  * zero the mapping: the new entry will be zero initialized
4450  */
4451 static void
4452 uvm_mapent_forkzero(struct vm_map *new_map, struct vm_map *old_map,
4453     struct vm_map_entry *old_entry)
4454 {
4455 	struct vm_map_entry *new_entry;
4456 
4457 	new_entry = uvm_mapent_clone(new_map, old_entry, 0);
4458 
4459 	new_entry->etype |=
4460 	    (UVM_ET_COPYONWRITE|UVM_ET_NEEDSCOPY);
4461 
4462 	if (new_entry->aref.ar_amap) {
4463 		uvm_map_unreference_amap(new_entry, 0);
4464 		new_entry->aref.ar_pageoff = 0;
4465 		new_entry->aref.ar_amap = NULL;
4466 	}
4467 
4468 	if (UVM_ET_ISOBJ(new_entry)) {
4469 		if (new_entry->object.uvm_obj->pgops->pgo_detach)
4470 			new_entry->object.uvm_obj->pgops->pgo_detach(
4471 			    new_entry->object.uvm_obj);
4472 		new_entry->object.uvm_obj = NULL;
4473 		new_entry->etype &= ~UVM_ET_OBJ;
4474 	}
4475 }
4476 
4477 /*
4478  *   F O R K   -   m a i n   e n t r y   p o i n t
4479  */
4480 /*
4481  * uvmspace_fork: fork a process' main map
4482  *
4483  * => create a new vmspace for child process from parent.
4484  * => parent's map must not be locked.
4485  */
4486 
4487 struct vmspace *
4488 uvmspace_fork(struct vmspace *vm1)
4489 {
4490 	struct vmspace *vm2;
4491 	struct vm_map *old_map = &vm1->vm_map;
4492 	struct vm_map *new_map;
4493 	struct vm_map_entry *old_entry;
4494 	UVMHIST_FUNC("uvmspace_fork"); UVMHIST_CALLED(maphist);
4495 
4496 	vm_map_lock(old_map);
4497 
4498 	vm2 = uvmspace_alloc(vm_map_min(old_map), vm_map_max(old_map),
4499 	    vm1->vm_map.flags & VM_MAP_TOPDOWN);
4500 	memcpy(&vm2->vm_startcopy, &vm1->vm_startcopy,
4501 	    (char *) (vm1 + 1) - (char *) &vm1->vm_startcopy);
4502 	new_map = &vm2->vm_map;		  /* XXX */
4503 
4504 	old_entry = old_map->header.next;
4505 	new_map->size = old_map->size;
4506 
4507 	/*
4508 	 * go entry-by-entry
4509 	 */
4510 
4511 	while (old_entry != &old_map->header) {
4512 
4513 		/*
4514 		 * first, some sanity checks on the old entry
4515 		 */
4516 
4517 		KASSERT(!UVM_ET_ISSUBMAP(old_entry));
4518 		KASSERT(UVM_ET_ISCOPYONWRITE(old_entry) ||
4519 			!UVM_ET_ISNEEDSCOPY(old_entry));
4520 
4521 		switch (old_entry->inheritance) {
4522 		case MAP_INHERIT_NONE:
4523 			/*
4524 			 * drop the mapping, modify size
4525 			 */
4526 			new_map->size -= old_entry->end - old_entry->start;
4527 			break;
4528 
4529 		case MAP_INHERIT_SHARE:
4530 			uvm_mapent_forkshared(new_map, old_map, old_entry);
4531 			break;
4532 
4533 		case MAP_INHERIT_COPY:
4534 			uvm_mapent_forkcopy(new_map, old_map, old_entry);
4535 			break;
4536 
4537 		case MAP_INHERIT_ZERO:
4538 			uvm_mapent_forkzero(new_map, old_map, old_entry);
4539 			break;
4540 		default:
4541 			KASSERT(0);
4542 			break;
4543 		}
4544 		old_entry = old_entry->next;
4545 	}
4546 
4547 	pmap_update(old_map->pmap);
4548 	vm_map_unlock(old_map);
4549 
4550 	if (uvm_shmfork && vm1->vm_shm)
4551 		(*uvm_shmfork)(vm1, vm2);
4552 
4553 #ifdef PMAP_FORK
4554 	pmap_fork(vm1->vm_map.pmap, vm2->vm_map.pmap);
4555 #endif
4556 
4557 	UVMHIST_LOG(maphist,"<- done",0,0,0,0);
4558 	return (vm2);
4559 }
4560 
4561 
4562 /*
4563  * uvm_mapent_trymerge: try to merge an entry with its neighbors.
4564  *
4565  * => called with map locked.
4566  * => return non zero if successfully merged.
4567  */
4568 
4569 int
4570 uvm_mapent_trymerge(struct vm_map *map, struct vm_map_entry *entry, int flags)
4571 {
4572 	struct uvm_object *uobj;
4573 	struct vm_map_entry *next;
4574 	struct vm_map_entry *prev;
4575 	vsize_t size;
4576 	int merged = 0;
4577 	bool copying;
4578 	int newetype;
4579 
4580 	if (entry->aref.ar_amap != NULL) {
4581 		return 0;
4582 	}
4583 	if ((entry->flags & UVM_MAP_NOMERGE) != 0) {
4584 		return 0;
4585 	}
4586 
4587 	uobj = entry->object.uvm_obj;
4588 	size = entry->end - entry->start;
4589 	copying = (flags & UVM_MERGE_COPYING) != 0;
4590 	newetype = copying ? (entry->etype & ~UVM_ET_NEEDSCOPY) : entry->etype;
4591 
4592 	next = entry->next;
4593 	if (next != &map->header &&
4594 	    next->start == entry->end &&
4595 	    ((copying && next->aref.ar_amap != NULL &&
4596 	    amap_refs(next->aref.ar_amap) == 1) ||
4597 	    (!copying && next->aref.ar_amap == NULL)) &&
4598 	    UVM_ET_ISCOMPATIBLE(next, newetype,
4599 	    uobj, entry->flags, entry->protection,
4600 	    entry->max_protection, entry->inheritance, entry->advice,
4601 	    entry->wired_count) &&
4602 	    (uobj == NULL || entry->offset + size == next->offset)) {
4603 		int error;
4604 
4605 		if (copying) {
4606 			error = amap_extend(next, size,
4607 			    AMAP_EXTEND_NOWAIT|AMAP_EXTEND_BACKWARDS);
4608 		} else {
4609 			error = 0;
4610 		}
4611 		if (error == 0) {
4612 			if (uobj) {
4613 				if (uobj->pgops->pgo_detach) {
4614 					uobj->pgops->pgo_detach(uobj);
4615 				}
4616 			}
4617 
4618 			entry->end = next->end;
4619 			clear_hints(map, next);
4620 			uvm_map_entry_unlink(map, next);
4621 			if (copying) {
4622 				entry->aref = next->aref;
4623 				entry->etype &= ~UVM_ET_NEEDSCOPY;
4624 			}
4625 			uvm_map_check(map, "trymerge forwardmerge");
4626 			uvm_mapent_free(next);
4627 			merged++;
4628 		}
4629 	}
4630 
4631 	prev = entry->prev;
4632 	if (prev != &map->header &&
4633 	    prev->end == entry->start &&
4634 	    ((copying && !merged && prev->aref.ar_amap != NULL &&
4635 	    amap_refs(prev->aref.ar_amap) == 1) ||
4636 	    (!copying && prev->aref.ar_amap == NULL)) &&
4637 	    UVM_ET_ISCOMPATIBLE(prev, newetype,
4638 	    uobj, entry->flags, entry->protection,
4639 	    entry->max_protection, entry->inheritance, entry->advice,
4640 	    entry->wired_count) &&
4641 	    (uobj == NULL ||
4642 	    prev->offset + prev->end - prev->start == entry->offset)) {
4643 		int error;
4644 
4645 		if (copying) {
4646 			error = amap_extend(prev, size,
4647 			    AMAP_EXTEND_NOWAIT|AMAP_EXTEND_FORWARDS);
4648 		} else {
4649 			error = 0;
4650 		}
4651 		if (error == 0) {
4652 			if (uobj) {
4653 				if (uobj->pgops->pgo_detach) {
4654 					uobj->pgops->pgo_detach(uobj);
4655 				}
4656 				entry->offset = prev->offset;
4657 			}
4658 
4659 			entry->start = prev->start;
4660 			clear_hints(map, prev);
4661 			uvm_map_entry_unlink(map, prev);
4662 			if (copying) {
4663 				entry->aref = prev->aref;
4664 				entry->etype &= ~UVM_ET_NEEDSCOPY;
4665 			}
4666 			uvm_map_check(map, "trymerge backmerge");
4667 			uvm_mapent_free(prev);
4668 			merged++;
4669 		}
4670 	}
4671 
4672 	return merged;
4673 }
4674 
4675 /*
4676  * uvm_map_setup: init map
4677  *
4678  * => map must not be in service yet.
4679  */
4680 
4681 void
4682 uvm_map_setup(struct vm_map *map, vaddr_t vmin, vaddr_t vmax, int flags)
4683 {
4684 
4685 	rb_tree_init(&map->rb_tree, &uvm_map_tree_ops);
4686 	map->header.next = map->header.prev = &map->header;
4687 	map->nentries = 0;
4688 	map->size = 0;
4689 	map->ref_count = 1;
4690 	vm_map_setmin(map, vmin);
4691 	vm_map_setmax(map, vmax);
4692 	map->flags = flags;
4693 	map->first_free = &map->header;
4694 	map->hint = &map->header;
4695 	map->timestamp = 0;
4696 	map->busy = NULL;
4697 
4698 	rw_init(&map->lock);
4699 	cv_init(&map->cv, "vm_map");
4700 	mutex_init(&map->misc_lock, MUTEX_DRIVER, IPL_NONE);
4701 }
4702 
4703 /*
4704  *   U N M A P   -   m a i n   e n t r y   p o i n t
4705  */
4706 
4707 /*
4708  * uvm_unmap1: remove mappings from a vm_map (from "start" up to "stop")
4709  *
4710  * => caller must check alignment and size
4711  * => map must be unlocked (we will lock it)
4712  * => flags is UVM_FLAG_QUANTUM or 0.
4713  */
4714 
4715 void
4716 uvm_unmap1(struct vm_map *map, vaddr_t start, vaddr_t end, int flags)
4717 {
4718 	struct vm_map_entry *dead_entries;
4719 	UVMHIST_FUNC("uvm_unmap"); UVMHIST_CALLED(maphist);
4720 
4721 	KASSERT(start < end);
4722 	UVMHIST_LOG(maphist, "  (map=%#jx, start=%#jx, end=%#jx)",
4723 	    (uintptr_t)map, start, end, 0);
4724 	if (map == kernel_map) {
4725 		LOCKDEBUG_MEM_CHECK((void *)start, end - start);
4726 	}
4727 
4728 	/*
4729 	 * work now done by helper functions.   wipe the pmap's and then
4730 	 * detach from the dead entries...
4731 	 */
4732 	vm_map_lock(map);
4733 	uvm_unmap_remove(map, start, end, &dead_entries, flags);
4734 	vm_map_unlock(map);
4735 
4736 	if (dead_entries != NULL)
4737 		uvm_unmap_detach(dead_entries, 0);
4738 
4739 	UVMHIST_LOG(maphist, "<- done", 0,0,0,0);
4740 }
4741 
4742 
4743 /*
4744  * uvm_map_reference: add reference to a map
4745  *
4746  * => map need not be locked (we use misc_lock).
4747  */
4748 
4749 void
4750 uvm_map_reference(struct vm_map *map)
4751 {
4752 	mutex_enter(&map->misc_lock);
4753 	map->ref_count++;
4754 	mutex_exit(&map->misc_lock);
4755 }
4756 
4757 bool
4758 vm_map_starved_p(struct vm_map *map)
4759 {
4760 
4761 	if ((map->flags & VM_MAP_WANTVA) != 0) {
4762 		return true;
4763 	}
4764 	/* XXX */
4765 	if ((vm_map_max(map) - vm_map_min(map)) / 16 * 15 < map->size) {
4766 		return true;
4767 	}
4768 	return false;
4769 }
4770 
4771 void
4772 uvm_map_lock_entry(struct vm_map_entry *entry)
4773 {
4774 
4775 	if (entry->aref.ar_amap != NULL) {
4776 		amap_lock(entry->aref.ar_amap);
4777 	}
4778 	if (UVM_ET_ISOBJ(entry)) {
4779 		mutex_enter(entry->object.uvm_obj->vmobjlock);
4780 	}
4781 }
4782 
4783 void
4784 uvm_map_unlock_entry(struct vm_map_entry *entry)
4785 {
4786 
4787 	if (UVM_ET_ISOBJ(entry)) {
4788 		mutex_exit(entry->object.uvm_obj->vmobjlock);
4789 	}
4790 	if (entry->aref.ar_amap != NULL) {
4791 		amap_unlock(entry->aref.ar_amap);
4792 	}
4793 }
4794 
4795 #if defined(DDB) || defined(DEBUGPRINT)
4796 
4797 /*
4798  * uvm_map_printit: actually prints the map
4799  */
4800 
4801 void
4802 uvm_map_printit(struct vm_map *map, bool full,
4803     void (*pr)(const char *, ...))
4804 {
4805 	struct vm_map_entry *entry;
4806 
4807 	(*pr)("MAP %p: [%#lx->%#lx]\n", map, vm_map_min(map),
4808 	    vm_map_max(map));
4809 	(*pr)("\t#ent=%d, sz=%d, ref=%d, version=%d, flags=%#x\n",
4810 	    map->nentries, map->size, map->ref_count, map->timestamp,
4811 	    map->flags);
4812 	(*pr)("\tpmap=%p(resident=%ld, wired=%ld)\n", map->pmap,
4813 	    pmap_resident_count(map->pmap), pmap_wired_count(map->pmap));
4814 	if (!full)
4815 		return;
4816 	for (entry = map->header.next; entry != &map->header;
4817 	    entry = entry->next) {
4818 		(*pr)(" - %p: %#lx->%#lx: obj=%p/%#llx, amap=%p/%d\n",
4819 		    entry, entry->start, entry->end, entry->object.uvm_obj,
4820 		    (long long)entry->offset, entry->aref.ar_amap,
4821 		    entry->aref.ar_pageoff);
4822 		(*pr)(
4823 		    "\tsubmap=%c, cow=%c, nc=%c, prot(max)=%d/%d, inh=%d, "
4824 		    "wc=%d, adv=%d\n",
4825 		    (entry->etype & UVM_ET_SUBMAP) ? 'T' : 'F',
4826 		    (entry->etype & UVM_ET_COPYONWRITE) ? 'T' : 'F',
4827 		    (entry->etype & UVM_ET_NEEDSCOPY) ? 'T' : 'F',
4828 		    entry->protection, entry->max_protection,
4829 		    entry->inheritance, entry->wired_count, entry->advice);
4830 	}
4831 }
4832 
4833 void
4834 uvm_whatis(uintptr_t addr, void (*pr)(const char *, ...))
4835 {
4836 	struct vm_map *map;
4837 
4838 	for (map = kernel_map;;) {
4839 		struct vm_map_entry *entry;
4840 
4841 		if (!uvm_map_lookup_entry_bytree(map, (vaddr_t)addr, &entry)) {
4842 			break;
4843 		}
4844 		(*pr)("%p is %p+%zu from VMMAP %p\n",
4845 		    (void *)addr, (void *)entry->start,
4846 		    (size_t)(addr - (uintptr_t)entry->start), map);
4847 		if (!UVM_ET_ISSUBMAP(entry)) {
4848 			break;
4849 		}
4850 		map = entry->object.sub_map;
4851 	}
4852 }
4853 
4854 #endif /* DDB || DEBUGPRINT */
4855 
4856 #ifndef __USER_VA0_IS_SAFE
4857 static int
4858 sysctl_user_va0_disable(SYSCTLFN_ARGS)
4859 {
4860 	struct sysctlnode node;
4861 	int t, error;
4862 
4863 	node = *rnode;
4864 	node.sysctl_data = &t;
4865 	t = user_va0_disable;
4866 	error = sysctl_lookup(SYSCTLFN_CALL(&node));
4867 	if (error || newp == NULL)
4868 		return (error);
4869 
4870 	if (!t && user_va0_disable &&
4871 	    kauth_authorize_system(l->l_cred, KAUTH_SYSTEM_MAP_VA_ZERO, 0,
4872 	    NULL, NULL, NULL))
4873 		return EPERM;
4874 
4875 	user_va0_disable = !!t;
4876 	return 0;
4877 }
4878 #endif
4879 
4880 static int
4881 fill_vmentry(struct lwp *l, struct proc *p, struct kinfo_vmentry *kve,
4882     struct vm_map *m, struct vm_map_entry *e)
4883 {
4884 #ifndef _RUMPKERNEL
4885 	int error;
4886 
4887 	memset(kve, 0, sizeof(*kve));
4888 	KASSERT(e != NULL);
4889 	if (UVM_ET_ISOBJ(e)) {
4890 		struct uvm_object *uobj = e->object.uvm_obj;
4891 		KASSERT(uobj != NULL);
4892 		kve->kve_ref_count = uobj->uo_refs;
4893 		kve->kve_count = uobj->uo_npages;
4894 		if (UVM_OBJ_IS_VNODE(uobj)) {
4895 			struct vattr va;
4896 			struct vnode *vp = (struct vnode *)uobj;
4897 			vn_lock(vp, LK_SHARED | LK_RETRY);
4898 			error = VOP_GETATTR(vp, &va, l->l_cred);
4899 			VOP_UNLOCK(vp);
4900 			kve->kve_type = KVME_TYPE_VNODE;
4901 			if (error == 0) {
4902 				kve->kve_vn_size = vp->v_size;
4903 				kve->kve_vn_type = (int)vp->v_type;
4904 				kve->kve_vn_mode = va.va_mode;
4905 				kve->kve_vn_rdev = va.va_rdev;
4906 				kve->kve_vn_fileid = va.va_fileid;
4907 				kve->kve_vn_fsid = va.va_fsid;
4908 				error = vnode_to_path(kve->kve_path,
4909 				    sizeof(kve->kve_path) / 2, vp, l, p);
4910 #ifdef DIAGNOSTIC
4911 				if (error)
4912 					printf("%s: vp %p error %d\n", __func__,
4913 						vp, error);
4914 #endif
4915 			}
4916 		} else if (UVM_OBJ_IS_KERN_OBJECT(uobj)) {
4917 			kve->kve_type = KVME_TYPE_KERN;
4918 		} else if (UVM_OBJ_IS_DEVICE(uobj)) {
4919 			kve->kve_type = KVME_TYPE_DEVICE;
4920 		} else if (UVM_OBJ_IS_AOBJ(uobj)) {
4921 			kve->kve_type = KVME_TYPE_ANON;
4922 		} else {
4923 			kve->kve_type = KVME_TYPE_OBJECT;
4924 		}
4925 	} else if (UVM_ET_ISSUBMAP(e)) {
4926 		struct vm_map *map = e->object.sub_map;
4927 		KASSERT(map != NULL);
4928 		kve->kve_ref_count = map->ref_count;
4929 		kve->kve_count = map->nentries;
4930 		kve->kve_type = KVME_TYPE_SUBMAP;
4931 	} else
4932 		kve->kve_type = KVME_TYPE_UNKNOWN;
4933 
4934 	kve->kve_start = e->start;
4935 	kve->kve_end = e->end;
4936 	kve->kve_offset = e->offset;
4937 	kve->kve_wired_count = e->wired_count;
4938 	kve->kve_inheritance = e->inheritance;
4939 	kve->kve_attributes = e->map_attrib;
4940 	kve->kve_advice = e->advice;
4941 #define PROT(p) (((p) & VM_PROT_READ) ? KVME_PROT_READ : 0) | \
4942 	(((p) & VM_PROT_WRITE) ? KVME_PROT_WRITE : 0) | \
4943 	(((p) & VM_PROT_EXECUTE) ? KVME_PROT_EXEC : 0)
4944 	kve->kve_protection = PROT(e->protection);
4945 	kve->kve_max_protection = PROT(e->max_protection);
4946 	kve->kve_flags |= (e->etype & UVM_ET_COPYONWRITE)
4947 	    ? KVME_FLAG_COW : 0;
4948 	kve->kve_flags |= (e->etype & UVM_ET_NEEDSCOPY)
4949 	    ? KVME_FLAG_NEEDS_COPY : 0;
4950 	kve->kve_flags |= (m->flags & VM_MAP_TOPDOWN)
4951 	    ? KVME_FLAG_GROWS_DOWN : KVME_FLAG_GROWS_UP;
4952 	kve->kve_flags |= (m->flags & VM_MAP_PAGEABLE)
4953 	    ? KVME_FLAG_PAGEABLE : 0;
4954 #endif
4955 	return 0;
4956 }
4957 
4958 static int
4959 fill_vmentries(struct lwp *l, pid_t pid, u_int elem_size, void *oldp,
4960     size_t *oldlenp)
4961 {
4962 	int error;
4963 	struct proc *p;
4964 	struct kinfo_vmentry *vme;
4965 	struct vmspace *vm;
4966 	struct vm_map *map;
4967 	struct vm_map_entry *entry;
4968 	char *dp;
4969 	size_t count, vmesize;
4970 
4971 	if (elem_size == 0 || elem_size > 2 * sizeof(*vme))
4972 		return EINVAL;
4973 
4974 	if (oldp) {
4975 		if (*oldlenp > 1024 * 1024)
4976 			return E2BIG;
4977 		count = *oldlenp / elem_size;
4978 		if (count == 0)
4979 			return ENOMEM;
4980 		vmesize = count * sizeof(*vme);
4981 	} else
4982 		vmesize = 0;
4983 
4984 	if ((error = proc_find_locked(l, &p, pid)) != 0)
4985 		return error;
4986 
4987 	vme = NULL;
4988 	count = 0;
4989 
4990 	if ((error = proc_vmspace_getref(p, &vm)) != 0)
4991 		goto out;
4992 
4993 	map = &vm->vm_map;
4994 	vm_map_lock_read(map);
4995 
4996 	dp = oldp;
4997 	if (oldp)
4998 		vme = kmem_alloc(vmesize, KM_SLEEP);
4999 	for (entry = map->header.next; entry != &map->header;
5000 	    entry = entry->next) {
5001 		if (oldp && (dp - (char *)oldp) < vmesize) {
5002 			error = fill_vmentry(l, p, &vme[count], map, entry);
5003 			if (error)
5004 				goto out;
5005 			dp += elem_size;
5006 		}
5007 		count++;
5008 	}
5009 	vm_map_unlock_read(map);
5010 	uvmspace_free(vm);
5011 
5012 out:
5013 	if (pid != -1)
5014 		mutex_exit(p->p_lock);
5015 	if (error == 0) {
5016 		const u_int esize = min(sizeof(*vme), elem_size);
5017 		dp = oldp;
5018 		for (size_t i = 0; i < count; i++) {
5019 			if (oldp && (dp - (char *)oldp) < vmesize) {
5020 				error = sysctl_copyout(l, &vme[i], dp, esize);
5021 				if (error)
5022 					break;
5023 				dp += elem_size;
5024 			} else
5025 				break;
5026 		}
5027 		count *= elem_size;
5028 		if (oldp != NULL && *oldlenp < count)
5029 			error = ENOSPC;
5030 		*oldlenp = count;
5031 	}
5032 	if (vme)
5033 		kmem_free(vme, vmesize);
5034 	return error;
5035 }
5036 
5037 static int
5038 sysctl_vmproc(SYSCTLFN_ARGS)
5039 {
5040 	int error;
5041 
5042 	if (namelen == 1 && name[0] == CTL_QUERY)
5043 		return (sysctl_query(SYSCTLFN_CALL(rnode)));
5044 
5045 	if (namelen == 0)
5046 		return EINVAL;
5047 
5048 	switch (name[0]) {
5049 	case VM_PROC_MAP:
5050 		if (namelen != 3)
5051 			return EINVAL;
5052 		sysctl_unlock();
5053 		error = fill_vmentries(l, name[1], name[2], oldp, oldlenp);
5054 		sysctl_relock();
5055 		return error;
5056 	default:
5057 		return EINVAL;
5058 	}
5059 }
5060 
5061 SYSCTL_SETUP(sysctl_uvmmap_setup, "sysctl uvmmap setup")
5062 {
5063 
5064 	sysctl_createv(clog, 0, NULL, NULL,
5065 		       CTLFLAG_PERMANENT,
5066 		       CTLTYPE_STRUCT, "proc",
5067 		       SYSCTL_DESCR("Process vm information"),
5068 		       sysctl_vmproc, 0, NULL, 0,
5069 		       CTL_VM, VM_PROC, CTL_EOL);
5070 #ifndef __USER_VA0_IS_SAFE
5071         sysctl_createv(clog, 0, NULL, NULL,
5072                        CTLFLAG_PERMANENT|CTLFLAG_READWRITE,
5073                        CTLTYPE_INT, "user_va0_disable",
5074                        SYSCTL_DESCR("Disable VA 0"),
5075                        sysctl_user_va0_disable, 0, &user_va0_disable, 0,
5076                        CTL_VM, CTL_CREATE, CTL_EOL);
5077 #endif
5078 }
5079