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