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