1 /* $OpenBSD: uvm_map.c,v 1.270 2021/01/19 13:21:36 mpi Exp $ */ 2 /* $NetBSD: uvm_map.c,v 1.86 2000/11/27 08:40:03 chs Exp $ */ 3 4 /* 5 * Copyright (c) 2011 Ariane van der Steldt <ariane@openbsd.org> 6 * 7 * Permission to use, copy, modify, and distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 * 19 * 20 * Copyright (c) 1997 Charles D. Cranor and Washington University. 21 * Copyright (c) 1991, 1993, The Regents of the University of California. 22 * 23 * All rights reserved. 24 * 25 * This code is derived from software contributed to Berkeley by 26 * The Mach Operating System project at Carnegie-Mellon University. 27 * 28 * Redistribution and use in source and binary forms, with or without 29 * modification, are permitted provided that the following conditions 30 * are met: 31 * 1. Redistributions of source code must retain the above copyright 32 * notice, this list of conditions and the following disclaimer. 33 * 2. Redistributions in binary form must reproduce the above copyright 34 * notice, this list of conditions and the following disclaimer in the 35 * documentation and/or other materials provided with the distribution. 36 * 3. Neither the name of the University nor the names of its contributors 37 * may be used to endorse or promote products derived from this software 38 * without specific prior written permission. 39 * 40 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * @(#)vm_map.c 8.3 (Berkeley) 1/12/94 53 * from: Id: uvm_map.c,v 1.1.2.27 1998/02/07 01:16:54 chs Exp 54 * 55 * 56 * Copyright (c) 1987, 1990 Carnegie-Mellon University. 57 * All rights reserved. 58 * 59 * Permission to use, copy, modify and distribute this software and 60 * its documentation is hereby granted, provided that both the copyright 61 * notice and this permission notice appear in all copies of the 62 * software, derivative works or modified versions, and any portions 63 * thereof, and that both notices appear in supporting documentation. 64 * 65 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 66 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 67 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 68 * 69 * Carnegie Mellon requests users of this software to return to 70 * 71 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 72 * School of Computer Science 73 * Carnegie Mellon University 74 * Pittsburgh PA 15213-3890 75 * 76 * any improvements or extensions that they make and grant Carnegie the 77 * rights to redistribute these changes. 78 */ 79 80 /* 81 * uvm_map.c: uvm map operations 82 */ 83 84 /* #define DEBUG */ 85 /* #define VMMAP_DEBUG */ 86 87 #include <sys/param.h> 88 #include <sys/systm.h> 89 #include <sys/acct.h> 90 #include <sys/mman.h> 91 #include <sys/proc.h> 92 #include <sys/malloc.h> 93 #include <sys/pool.h> 94 #include <sys/sysctl.h> 95 #include <sys/signalvar.h> 96 #include <sys/syslog.h> 97 #include <sys/user.h> 98 #include <sys/tracepoint.h> 99 100 #ifdef SYSVSHM 101 #include <sys/shm.h> 102 #endif 103 104 #include <uvm/uvm.h> 105 106 #ifdef DDB 107 #include <uvm/uvm_ddb.h> 108 #endif 109 110 #include <uvm/uvm_addr.h> 111 112 113 vsize_t uvmspace_dused(struct vm_map*, vaddr_t, vaddr_t); 114 int uvm_mapent_isjoinable(struct vm_map*, 115 struct vm_map_entry*, struct vm_map_entry*); 116 struct vm_map_entry *uvm_mapent_merge(struct vm_map*, struct vm_map_entry*, 117 struct vm_map_entry*, struct uvm_map_deadq*); 118 struct vm_map_entry *uvm_mapent_tryjoin(struct vm_map*, 119 struct vm_map_entry*, struct uvm_map_deadq*); 120 struct vm_map_entry *uvm_map_mkentry(struct vm_map*, struct vm_map_entry*, 121 struct vm_map_entry*, vaddr_t, vsize_t, int, 122 struct uvm_map_deadq*, struct vm_map_entry*); 123 struct vm_map_entry *uvm_mapent_alloc(struct vm_map*, int); 124 void uvm_mapent_free(struct vm_map_entry*); 125 void uvm_unmap_kill_entry(struct vm_map*, 126 struct vm_map_entry*); 127 void uvm_unmap_detach_intrsafe(struct uvm_map_deadq *); 128 void uvm_mapent_mkfree(struct vm_map*, 129 struct vm_map_entry*, struct vm_map_entry**, 130 struct uvm_map_deadq*, boolean_t); 131 void uvm_map_pageable_pgon(struct vm_map*, 132 struct vm_map_entry*, struct vm_map_entry*, 133 vaddr_t, vaddr_t); 134 int uvm_map_pageable_wire(struct vm_map*, 135 struct vm_map_entry*, struct vm_map_entry*, 136 vaddr_t, vaddr_t, int); 137 void uvm_map_setup_entries(struct vm_map*); 138 void uvm_map_setup_md(struct vm_map*); 139 void uvm_map_teardown(struct vm_map*); 140 void uvm_map_vmspace_update(struct vm_map*, 141 struct uvm_map_deadq*, int); 142 void uvm_map_kmem_grow(struct vm_map*, 143 struct uvm_map_deadq*, vsize_t, int); 144 void uvm_map_freelist_update_clear(struct vm_map*, 145 struct uvm_map_deadq*); 146 void uvm_map_freelist_update_refill(struct vm_map *, int); 147 void uvm_map_freelist_update(struct vm_map*, 148 struct uvm_map_deadq*, vaddr_t, vaddr_t, 149 vaddr_t, vaddr_t, int); 150 struct vm_map_entry *uvm_map_fix_space(struct vm_map*, struct vm_map_entry*, 151 vaddr_t, vaddr_t, int); 152 int uvm_map_sel_limits(vaddr_t*, vaddr_t*, vsize_t, int, 153 struct vm_map_entry*, vaddr_t, vaddr_t, vaddr_t, 154 int); 155 int uvm_map_findspace(struct vm_map*, 156 struct vm_map_entry**, struct vm_map_entry**, 157 vaddr_t*, vsize_t, vaddr_t, vaddr_t, vm_prot_t, 158 vaddr_t); 159 vsize_t uvm_map_addr_augment_get(struct vm_map_entry*); 160 void uvm_map_addr_augment(struct vm_map_entry*); 161 162 int uvm_map_inentry_recheck(u_long, vaddr_t, 163 struct p_inentry *); 164 boolean_t uvm_map_inentry_fix(struct proc *, struct p_inentry *, 165 vaddr_t, int (*)(vm_map_entry_t), u_long); 166 /* 167 * Tree management functions. 168 */ 169 170 static inline void uvm_mapent_copy(struct vm_map_entry*, 171 struct vm_map_entry*); 172 static inline int uvm_mapentry_addrcmp(const struct vm_map_entry*, 173 const struct vm_map_entry*); 174 void uvm_mapent_free_insert(struct vm_map*, 175 struct uvm_addr_state*, struct vm_map_entry*); 176 void uvm_mapent_free_remove(struct vm_map*, 177 struct uvm_addr_state*, struct vm_map_entry*); 178 void uvm_mapent_addr_insert(struct vm_map*, 179 struct vm_map_entry*); 180 void uvm_mapent_addr_remove(struct vm_map*, 181 struct vm_map_entry*); 182 void uvm_map_splitentry(struct vm_map*, 183 struct vm_map_entry*, struct vm_map_entry*, 184 vaddr_t); 185 vsize_t uvm_map_boundary(struct vm_map*, vaddr_t, vaddr_t); 186 int uvm_mapent_bias(struct vm_map*, struct vm_map_entry*); 187 188 /* 189 * uvm_vmspace_fork helper functions. 190 */ 191 struct vm_map_entry *uvm_mapent_clone(struct vm_map*, vaddr_t, vsize_t, 192 vsize_t, vm_prot_t, vm_prot_t, 193 struct vm_map_entry*, struct uvm_map_deadq*, int, 194 int); 195 struct vm_map_entry *uvm_mapent_share(struct vm_map*, vaddr_t, vsize_t, 196 vsize_t, vm_prot_t, vm_prot_t, struct vm_map*, 197 struct vm_map_entry*, struct uvm_map_deadq*); 198 struct vm_map_entry *uvm_mapent_forkshared(struct vmspace*, struct vm_map*, 199 struct vm_map*, struct vm_map_entry*, 200 struct uvm_map_deadq*); 201 struct vm_map_entry *uvm_mapent_forkcopy(struct vmspace*, struct vm_map*, 202 struct vm_map*, struct vm_map_entry*, 203 struct uvm_map_deadq*); 204 struct vm_map_entry *uvm_mapent_forkzero(struct vmspace*, struct vm_map*, 205 struct vm_map*, struct vm_map_entry*, 206 struct uvm_map_deadq*); 207 208 /* 209 * Tree validation. 210 */ 211 #ifdef VMMAP_DEBUG 212 void uvm_tree_assert(struct vm_map*, int, char*, 213 char*, int); 214 #define UVM_ASSERT(map, cond, file, line) \ 215 uvm_tree_assert((map), (cond), #cond, (file), (line)) 216 void uvm_tree_sanity(struct vm_map*, char*, int); 217 void uvm_tree_size_chk(struct vm_map*, char*, int); 218 void vmspace_validate(struct vm_map*); 219 #else 220 #define uvm_tree_sanity(_map, _file, _line) do {} while (0) 221 #define uvm_tree_size_chk(_map, _file, _line) do {} while (0) 222 #define vmspace_validate(_map) do {} while (0) 223 #endif 224 225 /* 226 * All architectures will have pmap_prefer. 227 */ 228 #ifndef PMAP_PREFER 229 #define PMAP_PREFER_ALIGN() (vaddr_t)PAGE_SIZE 230 #define PMAP_PREFER_OFFSET(off) 0 231 #define PMAP_PREFER(addr, off) (addr) 232 #endif 233 234 /* 235 * The kernel map will initially be VM_MAP_KSIZE_INIT bytes. 236 * Every time that gets cramped, we grow by at least VM_MAP_KSIZE_DELTA bytes. 237 * 238 * We attempt to grow by UVM_MAP_KSIZE_ALLOCMUL times the allocation size 239 * each time. 240 */ 241 #define VM_MAP_KSIZE_INIT (512 * (vaddr_t)PAGE_SIZE) 242 #define VM_MAP_KSIZE_DELTA (256 * (vaddr_t)PAGE_SIZE) 243 #define VM_MAP_KSIZE_ALLOCMUL 4 244 /* 245 * When selecting a random free-space block, look at most FSPACE_DELTA blocks 246 * ahead. 247 */ 248 #define FSPACE_DELTA 8 249 /* 250 * Put allocations adjecent to previous allocations when the free-space tree 251 * is larger than FSPACE_COMPACT entries. 252 * 253 * Alignment and PMAP_PREFER may still cause the entry to not be fully 254 * adjecent. Note that this strategy reduces memory fragmentation (by leaving 255 * a large space before or after the allocation). 256 */ 257 #define FSPACE_COMPACT 128 258 /* 259 * Make the address selection skip at most this many bytes from the start of 260 * the free space in which the allocation takes place. 261 * 262 * The main idea behind a randomized address space is that an attacker cannot 263 * know where to target his attack. Therefore, the location of objects must be 264 * as random as possible. However, the goal is not to create the most sparse 265 * map that is possible. 266 * FSPACE_MAXOFF pushes the considered range in bytes down to less insane 267 * sizes, thereby reducing the sparseness. The biggest randomization comes 268 * from fragmentation, i.e. FSPACE_COMPACT. 269 */ 270 #define FSPACE_MAXOFF ((vaddr_t)32 * 1024 * 1024) 271 /* 272 * Allow for small gaps in the overflow areas. 273 * Gap size is in bytes and does not have to be a multiple of page-size. 274 */ 275 #define FSPACE_BIASGAP ((vaddr_t)32 * 1024) 276 277 /* auto-allocate address lower bound */ 278 #define VMMAP_MIN_ADDR PAGE_SIZE 279 280 281 #ifdef DEADBEEF0 282 #define UVMMAP_DEADBEEF ((unsigned long)DEADBEEF0) 283 #else 284 #define UVMMAP_DEADBEEF ((unsigned long)0xdeadd0d0) 285 #endif 286 287 #ifdef DEBUG 288 int uvm_map_printlocks = 0; 289 290 #define LPRINTF(_args) \ 291 do { \ 292 if (uvm_map_printlocks) \ 293 printf _args; \ 294 } while (0) 295 #else 296 #define LPRINTF(_args) do {} while (0) 297 #endif 298 299 static struct mutex uvm_kmapent_mtx; 300 static struct timeval uvm_kmapent_last_warn_time; 301 static struct timeval uvm_kmapent_warn_rate = { 10, 0 }; 302 303 const char vmmapbsy[] = "vmmapbsy"; 304 305 /* 306 * pool for vmspace structures. 307 */ 308 struct pool uvm_vmspace_pool; 309 310 /* 311 * pool for dynamically-allocated map entries. 312 */ 313 struct pool uvm_map_entry_pool; 314 struct pool uvm_map_entry_kmem_pool; 315 316 /* 317 * This global represents the end of the kernel virtual address 318 * space. If we want to exceed this, we must grow the kernel 319 * virtual address space dynamically. 320 * 321 * Note, this variable is locked by kernel_map's lock. 322 */ 323 vaddr_t uvm_maxkaddr; 324 325 /* 326 * Locking predicate. 327 */ 328 #define UVM_MAP_REQ_WRITE(_map) \ 329 do { \ 330 if ((_map)->ref_count > 0) { \ 331 if (((_map)->flags & VM_MAP_INTRSAFE) == 0) \ 332 rw_assert_wrlock(&(_map)->lock); \ 333 else \ 334 MUTEX_ASSERT_LOCKED(&(_map)->mtx); \ 335 } \ 336 } while (0) 337 338 #define vm_map_modflags(map, set, clear) \ 339 do { \ 340 mtx_enter(&(map)->flags_lock); \ 341 (map)->flags = ((map)->flags | (set)) & ~(clear); \ 342 mtx_leave(&(map)->flags_lock); \ 343 } while (0) 344 345 346 /* 347 * Tree describing entries by address. 348 * 349 * Addresses are unique. 350 * Entries with start == end may only exist if they are the first entry 351 * (sorted by address) within a free-memory tree. 352 */ 353 354 static inline int 355 uvm_mapentry_addrcmp(const struct vm_map_entry *e1, 356 const struct vm_map_entry *e2) 357 { 358 return e1->start < e2->start ? -1 : e1->start > e2->start; 359 } 360 361 /* 362 * Copy mapentry. 363 */ 364 static inline void 365 uvm_mapent_copy(struct vm_map_entry *src, struct vm_map_entry *dst) 366 { 367 caddr_t csrc, cdst; 368 size_t sz; 369 370 csrc = (caddr_t)src; 371 cdst = (caddr_t)dst; 372 csrc += offsetof(struct vm_map_entry, uvm_map_entry_start_copy); 373 cdst += offsetof(struct vm_map_entry, uvm_map_entry_start_copy); 374 375 sz = offsetof(struct vm_map_entry, uvm_map_entry_stop_copy) - 376 offsetof(struct vm_map_entry, uvm_map_entry_start_copy); 377 memcpy(cdst, csrc, sz); 378 } 379 380 /* 381 * Handle free-list insertion. 382 */ 383 void 384 uvm_mapent_free_insert(struct vm_map *map, struct uvm_addr_state *uaddr, 385 struct vm_map_entry *entry) 386 { 387 const struct uvm_addr_functions *fun; 388 #ifdef VMMAP_DEBUG 389 vaddr_t min, max, bound; 390 #endif 391 392 #ifdef VMMAP_DEBUG 393 /* 394 * Boundary check. 395 * Boundaries are folded if they go on the same free list. 396 */ 397 min = VMMAP_FREE_START(entry); 398 max = VMMAP_FREE_END(entry); 399 400 while (min < max) { 401 bound = uvm_map_boundary(map, min, max); 402 KASSERT(uvm_map_uaddr(map, min) == uaddr); 403 min = bound; 404 } 405 #endif 406 KDASSERT((entry->fspace & (vaddr_t)PAGE_MASK) == 0); 407 KASSERT((entry->etype & UVM_ET_FREEMAPPED) == 0); 408 409 UVM_MAP_REQ_WRITE(map); 410 411 /* Actual insert: forward to uaddr pointer. */ 412 if (uaddr != NULL) { 413 fun = uaddr->uaddr_functions; 414 KDASSERT(fun != NULL); 415 if (fun->uaddr_free_insert != NULL) 416 (*fun->uaddr_free_insert)(map, uaddr, entry); 417 entry->etype |= UVM_ET_FREEMAPPED; 418 } 419 420 /* Update fspace augmentation. */ 421 uvm_map_addr_augment(entry); 422 } 423 424 /* 425 * Handle free-list removal. 426 */ 427 void 428 uvm_mapent_free_remove(struct vm_map *map, struct uvm_addr_state *uaddr, 429 struct vm_map_entry *entry) 430 { 431 const struct uvm_addr_functions *fun; 432 433 KASSERT((entry->etype & UVM_ET_FREEMAPPED) != 0 || uaddr == NULL); 434 KASSERT(uvm_map_uaddr_e(map, entry) == uaddr); 435 UVM_MAP_REQ_WRITE(map); 436 437 if (uaddr != NULL) { 438 fun = uaddr->uaddr_functions; 439 if (fun->uaddr_free_remove != NULL) 440 (*fun->uaddr_free_remove)(map, uaddr, entry); 441 entry->etype &= ~UVM_ET_FREEMAPPED; 442 } 443 } 444 445 /* 446 * Handle address tree insertion. 447 */ 448 void 449 uvm_mapent_addr_insert(struct vm_map *map, struct vm_map_entry *entry) 450 { 451 struct vm_map_entry *res; 452 453 if (!RBT_CHECK(uvm_map_addr, entry, UVMMAP_DEADBEEF)) 454 panic("uvm_mapent_addr_insert: entry still in addr list"); 455 KDASSERT(entry->start <= entry->end); 456 KDASSERT((entry->start & (vaddr_t)PAGE_MASK) == 0 && 457 (entry->end & (vaddr_t)PAGE_MASK) == 0); 458 459 TRACEPOINT(uvm, map_insert, 460 entry->start, entry->end, entry->protection, NULL); 461 462 UVM_MAP_REQ_WRITE(map); 463 res = RBT_INSERT(uvm_map_addr, &map->addr, entry); 464 if (res != NULL) { 465 panic("uvm_mapent_addr_insert: map %p entry %p " 466 "(0x%lx-0x%lx G=0x%lx F=0x%lx) insert collision " 467 "with entry %p (0x%lx-0x%lx G=0x%lx F=0x%lx)", 468 map, entry, 469 entry->start, entry->end, entry->guard, entry->fspace, 470 res, res->start, res->end, res->guard, res->fspace); 471 } 472 } 473 474 /* 475 * Handle address tree removal. 476 */ 477 void 478 uvm_mapent_addr_remove(struct vm_map *map, struct vm_map_entry *entry) 479 { 480 struct vm_map_entry *res; 481 482 TRACEPOINT(uvm, map_remove, 483 entry->start, entry->end, entry->protection, NULL); 484 485 UVM_MAP_REQ_WRITE(map); 486 res = RBT_REMOVE(uvm_map_addr, &map->addr, entry); 487 if (res != entry) 488 panic("uvm_mapent_addr_remove"); 489 RBT_POISON(uvm_map_addr, entry, UVMMAP_DEADBEEF); 490 } 491 492 /* 493 * uvm_map_reference: add reference to a map 494 * 495 * XXX check map reference counter lock 496 */ 497 #define uvm_map_reference(_map) \ 498 do { \ 499 map->ref_count++; \ 500 } while (0) 501 502 /* 503 * Calculate the dused delta. 504 */ 505 vsize_t 506 uvmspace_dused(struct vm_map *map, vaddr_t min, vaddr_t max) 507 { 508 struct vmspace *vm; 509 vsize_t sz; 510 vaddr_t lmax; 511 vaddr_t stack_begin, stack_end; /* Position of stack. */ 512 513 KASSERT(map->flags & VM_MAP_ISVMSPACE); 514 vm = (struct vmspace *)map; 515 stack_begin = MIN((vaddr_t)vm->vm_maxsaddr, (vaddr_t)vm->vm_minsaddr); 516 stack_end = MAX((vaddr_t)vm->vm_maxsaddr, (vaddr_t)vm->vm_minsaddr); 517 518 sz = 0; 519 while (min != max) { 520 lmax = max; 521 if (min < stack_begin && lmax > stack_begin) 522 lmax = stack_begin; 523 else if (min < stack_end && lmax > stack_end) 524 lmax = stack_end; 525 526 if (min >= stack_begin && min < stack_end) { 527 /* nothing */ 528 } else 529 sz += lmax - min; 530 min = lmax; 531 } 532 533 return sz >> PAGE_SHIFT; 534 } 535 536 /* 537 * Find the entry describing the given address. 538 */ 539 struct vm_map_entry* 540 uvm_map_entrybyaddr(struct uvm_map_addr *atree, vaddr_t addr) 541 { 542 struct vm_map_entry *iter; 543 544 iter = RBT_ROOT(uvm_map_addr, atree); 545 while (iter != NULL) { 546 if (iter->start > addr) 547 iter = RBT_LEFT(uvm_map_addr, iter); 548 else if (VMMAP_FREE_END(iter) <= addr) 549 iter = RBT_RIGHT(uvm_map_addr, iter); 550 else 551 return iter; 552 } 553 return NULL; 554 } 555 556 /* 557 * DEAD_ENTRY_PUSH(struct vm_map_deadq *deadq, struct vm_map_entry *entry) 558 * 559 * Push dead entries into a linked list. 560 * Since the linked list abuses the address tree for storage, the entry 561 * may not be linked in a map. 562 * 563 * *head must be initialized to NULL before the first call to this macro. 564 * uvm_unmap_detach(*head, 0) will remove dead entries. 565 */ 566 static inline void 567 dead_entry_push(struct uvm_map_deadq *deadq, struct vm_map_entry *entry) 568 { 569 TAILQ_INSERT_TAIL(deadq, entry, dfree.deadq); 570 } 571 #define DEAD_ENTRY_PUSH(_headptr, _entry) \ 572 dead_entry_push((_headptr), (_entry)) 573 574 /* 575 * Helper function for uvm_map_findspace_tree. 576 * 577 * Given allocation constraints and pmap constraints, finds the 578 * lowest and highest address in a range that can be used for the 579 * allocation. 580 * 581 * pmap_align and pmap_off are ignored on non-PMAP_PREFER archs. 582 * 583 * 584 * Big chunk of math with a seasoning of dragons. 585 */ 586 int 587 uvm_map_sel_limits(vaddr_t *min, vaddr_t *max, vsize_t sz, int guardpg, 588 struct vm_map_entry *sel, vaddr_t align, 589 vaddr_t pmap_align, vaddr_t pmap_off, int bias) 590 { 591 vaddr_t sel_min, sel_max; 592 #ifdef PMAP_PREFER 593 vaddr_t pmap_min, pmap_max; 594 #endif /* PMAP_PREFER */ 595 #ifdef DIAGNOSTIC 596 int bad; 597 #endif /* DIAGNOSTIC */ 598 599 sel_min = VMMAP_FREE_START(sel); 600 sel_max = VMMAP_FREE_END(sel) - sz - (guardpg ? PAGE_SIZE : 0); 601 602 #ifdef PMAP_PREFER 603 604 /* 605 * There are two special cases, in which we can satisfy the align 606 * requirement and the pmap_prefer requirement. 607 * - when pmap_off == 0, we always select the largest of the two 608 * - when pmap_off % align == 0 and pmap_align > align, we simply 609 * satisfy the pmap_align requirement and automatically 610 * satisfy the align requirement. 611 */ 612 if (align > PAGE_SIZE && 613 !(pmap_align > align && (pmap_off & (align - 1)) == 0)) { 614 /* 615 * Simple case: only use align. 616 */ 617 sel_min = roundup(sel_min, align); 618 sel_max &= ~(align - 1); 619 620 if (sel_min > sel_max) 621 return ENOMEM; 622 623 /* Correct for bias. */ 624 if (sel_max - sel_min > FSPACE_BIASGAP) { 625 if (bias > 0) { 626 sel_min = sel_max - FSPACE_BIASGAP; 627 sel_min = roundup(sel_min, align); 628 } else if (bias < 0) { 629 sel_max = sel_min + FSPACE_BIASGAP; 630 sel_max &= ~(align - 1); 631 } 632 } 633 } else if (pmap_align != 0) { 634 /* 635 * Special case: satisfy both pmap_prefer and 636 * align argument. 637 */ 638 pmap_max = sel_max & ~(pmap_align - 1); 639 pmap_min = sel_min; 640 if (pmap_max < sel_min) 641 return ENOMEM; 642 643 /* Adjust pmap_min for BIASGAP for top-addr bias. */ 644 if (bias > 0 && pmap_max - pmap_min > FSPACE_BIASGAP) 645 pmap_min = pmap_max - FSPACE_BIASGAP; 646 /* Align pmap_min. */ 647 pmap_min &= ~(pmap_align - 1); 648 if (pmap_min < sel_min) 649 pmap_min += pmap_align; 650 if (pmap_min > pmap_max) 651 return ENOMEM; 652 653 /* Adjust pmap_max for BIASGAP for bottom-addr bias. */ 654 if (bias < 0 && pmap_max - pmap_min > FSPACE_BIASGAP) { 655 pmap_max = (pmap_min + FSPACE_BIASGAP) & 656 ~(pmap_align - 1); 657 } 658 if (pmap_min > pmap_max) 659 return ENOMEM; 660 661 /* Apply pmap prefer offset. */ 662 pmap_max |= pmap_off; 663 if (pmap_max > sel_max) 664 pmap_max -= pmap_align; 665 pmap_min |= pmap_off; 666 if (pmap_min < sel_min) 667 pmap_min += pmap_align; 668 669 /* 670 * Fixup: it's possible that pmap_min and pmap_max 671 * cross eachother. In this case, try to find one 672 * address that is allowed. 673 * (This usually happens in biased case.) 674 */ 675 if (pmap_min > pmap_max) { 676 if (pmap_min < sel_max) 677 pmap_max = pmap_min; 678 else if (pmap_max > sel_min) 679 pmap_min = pmap_max; 680 else 681 return ENOMEM; 682 } 683 684 /* Internal validation. */ 685 KDASSERT(pmap_min <= pmap_max); 686 687 sel_min = pmap_min; 688 sel_max = pmap_max; 689 } else if (bias > 0 && sel_max - sel_min > FSPACE_BIASGAP) 690 sel_min = sel_max - FSPACE_BIASGAP; 691 else if (bias < 0 && sel_max - sel_min > FSPACE_BIASGAP) 692 sel_max = sel_min + FSPACE_BIASGAP; 693 694 #else 695 696 if (align > PAGE_SIZE) { 697 sel_min = roundup(sel_min, align); 698 sel_max &= ~(align - 1); 699 if (sel_min > sel_max) 700 return ENOMEM; 701 702 if (bias != 0 && sel_max - sel_min > FSPACE_BIASGAP) { 703 if (bias > 0) { 704 sel_min = roundup(sel_max - FSPACE_BIASGAP, 705 align); 706 } else { 707 sel_max = (sel_min + FSPACE_BIASGAP) & 708 ~(align - 1); 709 } 710 } 711 } else if (bias > 0 && sel_max - sel_min > FSPACE_BIASGAP) 712 sel_min = sel_max - FSPACE_BIASGAP; 713 else if (bias < 0 && sel_max - sel_min > FSPACE_BIASGAP) 714 sel_max = sel_min + FSPACE_BIASGAP; 715 716 #endif 717 718 if (sel_min > sel_max) 719 return ENOMEM; 720 721 #ifdef DIAGNOSTIC 722 bad = 0; 723 /* Lower boundary check. */ 724 if (sel_min < VMMAP_FREE_START(sel)) { 725 printf("sel_min: 0x%lx, but should be at least 0x%lx\n", 726 sel_min, VMMAP_FREE_START(sel)); 727 bad++; 728 } 729 /* Upper boundary check. */ 730 if (sel_max > VMMAP_FREE_END(sel) - sz - (guardpg ? PAGE_SIZE : 0)) { 731 printf("sel_max: 0x%lx, but should be at most 0x%lx\n", 732 sel_max, 733 VMMAP_FREE_END(sel) - sz - (guardpg ? PAGE_SIZE : 0)); 734 bad++; 735 } 736 /* Lower boundary alignment. */ 737 if (align != 0 && (sel_min & (align - 1)) != 0) { 738 printf("sel_min: 0x%lx, not aligned to 0x%lx\n", 739 sel_min, align); 740 bad++; 741 } 742 /* Upper boundary alignment. */ 743 if (align != 0 && (sel_max & (align - 1)) != 0) { 744 printf("sel_max: 0x%lx, not aligned to 0x%lx\n", 745 sel_max, align); 746 bad++; 747 } 748 /* Lower boundary PMAP_PREFER check. */ 749 if (pmap_align != 0 && align == 0 && 750 (sel_min & (pmap_align - 1)) != pmap_off) { 751 printf("sel_min: 0x%lx, aligned to 0x%lx, expected 0x%lx\n", 752 sel_min, sel_min & (pmap_align - 1), pmap_off); 753 bad++; 754 } 755 /* Upper boundary PMAP_PREFER check. */ 756 if (pmap_align != 0 && align == 0 && 757 (sel_max & (pmap_align - 1)) != pmap_off) { 758 printf("sel_max: 0x%lx, aligned to 0x%lx, expected 0x%lx\n", 759 sel_max, sel_max & (pmap_align - 1), pmap_off); 760 bad++; 761 } 762 763 if (bad) { 764 panic("uvm_map_sel_limits(sz = %lu, guardpg = %c, " 765 "align = 0x%lx, pmap_align = 0x%lx, pmap_off = 0x%lx, " 766 "bias = %d, " 767 "FREE_START(sel) = 0x%lx, FREE_END(sel) = 0x%lx)", 768 sz, (guardpg ? 'T' : 'F'), align, pmap_align, pmap_off, 769 bias, VMMAP_FREE_START(sel), VMMAP_FREE_END(sel)); 770 } 771 #endif /* DIAGNOSTIC */ 772 773 *min = sel_min; 774 *max = sel_max; 775 return 0; 776 } 777 778 /* 779 * Test if memory starting at addr with sz bytes is free. 780 * 781 * Fills in *start_ptr and *end_ptr to be the first and last entry describing 782 * the space. 783 * If called with prefilled *start_ptr and *end_ptr, they are to be correct. 784 */ 785 int 786 uvm_map_isavail(struct vm_map *map, struct uvm_addr_state *uaddr, 787 struct vm_map_entry **start_ptr, struct vm_map_entry **end_ptr, 788 vaddr_t addr, vsize_t sz) 789 { 790 struct uvm_addr_state *free; 791 struct uvm_map_addr *atree; 792 struct vm_map_entry *i, *i_end; 793 794 if (addr + sz < addr) 795 return 0; 796 797 /* 798 * Kernel memory above uvm_maxkaddr is considered unavailable. 799 */ 800 if ((map->flags & VM_MAP_ISVMSPACE) == 0) { 801 if (addr + sz > uvm_maxkaddr) 802 return 0; 803 } 804 805 atree = &map->addr; 806 807 /* 808 * Fill in first, last, so they point at the entries containing the 809 * first and last address of the range. 810 * Note that if they are not NULL, we don't perform the lookup. 811 */ 812 KDASSERT(atree != NULL && start_ptr != NULL && end_ptr != NULL); 813 if (*start_ptr == NULL) { 814 *start_ptr = uvm_map_entrybyaddr(atree, addr); 815 if (*start_ptr == NULL) 816 return 0; 817 } else 818 KASSERT(*start_ptr == uvm_map_entrybyaddr(atree, addr)); 819 if (*end_ptr == NULL) { 820 if (VMMAP_FREE_END(*start_ptr) >= addr + sz) 821 *end_ptr = *start_ptr; 822 else { 823 *end_ptr = uvm_map_entrybyaddr(atree, addr + sz - 1); 824 if (*end_ptr == NULL) 825 return 0; 826 } 827 } else 828 KASSERT(*end_ptr == uvm_map_entrybyaddr(atree, addr + sz - 1)); 829 830 /* Validation. */ 831 KDASSERT(*start_ptr != NULL && *end_ptr != NULL); 832 KDASSERT((*start_ptr)->start <= addr && 833 VMMAP_FREE_END(*start_ptr) > addr && 834 (*end_ptr)->start < addr + sz && 835 VMMAP_FREE_END(*end_ptr) >= addr + sz); 836 837 /* 838 * Check the none of the entries intersects with <addr, addr+sz>. 839 * Also, if the entry belong to uaddr_exe or uaddr_brk_stack, it is 840 * considered unavailable unless called by those allocators. 841 */ 842 i = *start_ptr; 843 i_end = RBT_NEXT(uvm_map_addr, *end_ptr); 844 for (; i != i_end; 845 i = RBT_NEXT(uvm_map_addr, i)) { 846 if (i->start != i->end && i->end > addr) 847 return 0; 848 849 /* 850 * uaddr_exe and uaddr_brk_stack may only be used 851 * by these allocators and the NULL uaddr (i.e. no 852 * uaddr). 853 * Reject if this requirement is not met. 854 */ 855 if (uaddr != NULL) { 856 free = uvm_map_uaddr_e(map, i); 857 858 if (uaddr != free && free != NULL && 859 (free == map->uaddr_exe || 860 free == map->uaddr_brk_stack)) 861 return 0; 862 } 863 } 864 865 return -1; 866 } 867 868 /* 869 * Invoke each address selector until an address is found. 870 * Will not invoke uaddr_exe. 871 */ 872 int 873 uvm_map_findspace(struct vm_map *map, struct vm_map_entry**first, 874 struct vm_map_entry**last, vaddr_t *addr, vsize_t sz, 875 vaddr_t pmap_align, vaddr_t pmap_offset, vm_prot_t prot, vaddr_t hint) 876 { 877 struct uvm_addr_state *uaddr; 878 int i; 879 880 /* 881 * Allocation for sz bytes at any address, 882 * using the addr selectors in order. 883 */ 884 for (i = 0; i < nitems(map->uaddr_any); i++) { 885 uaddr = map->uaddr_any[i]; 886 887 if (uvm_addr_invoke(map, uaddr, first, last, 888 addr, sz, pmap_align, pmap_offset, prot, hint) == 0) 889 return 0; 890 } 891 892 /* Fall back to brk() and stack() address selectors. */ 893 uaddr = map->uaddr_brk_stack; 894 if (uvm_addr_invoke(map, uaddr, first, last, 895 addr, sz, pmap_align, pmap_offset, prot, hint) == 0) 896 return 0; 897 898 return ENOMEM; 899 } 900 901 /* Calculate entry augmentation value. */ 902 vsize_t 903 uvm_map_addr_augment_get(struct vm_map_entry *entry) 904 { 905 vsize_t augment; 906 struct vm_map_entry *left, *right; 907 908 augment = entry->fspace; 909 if ((left = RBT_LEFT(uvm_map_addr, entry)) != NULL) 910 augment = MAX(augment, left->fspace_augment); 911 if ((right = RBT_RIGHT(uvm_map_addr, entry)) != NULL) 912 augment = MAX(augment, right->fspace_augment); 913 return augment; 914 } 915 916 /* 917 * Update augmentation data in entry. 918 */ 919 void 920 uvm_map_addr_augment(struct vm_map_entry *entry) 921 { 922 vsize_t augment; 923 924 while (entry != NULL) { 925 /* Calculate value for augmentation. */ 926 augment = uvm_map_addr_augment_get(entry); 927 928 /* 929 * Descend update. 930 * Once we find an entry that already has the correct value, 931 * stop, since it means all its parents will use the correct 932 * value too. 933 */ 934 if (entry->fspace_augment == augment) 935 return; 936 entry->fspace_augment = augment; 937 entry = RBT_PARENT(uvm_map_addr, entry); 938 } 939 } 940 941 /* 942 * uvm_mapanon: establish a valid mapping in map for an anon 943 * 944 * => *addr and sz must be a multiple of PAGE_SIZE. 945 * => *addr is ignored, except if flags contains UVM_FLAG_FIXED. 946 * => map must be unlocked. 947 * 948 * => align: align vaddr, must be a power-of-2. 949 * Align is only a hint and will be ignored if the alignment fails. 950 */ 951 int 952 uvm_mapanon(struct vm_map *map, vaddr_t *addr, vsize_t sz, 953 vsize_t align, unsigned int flags) 954 { 955 struct vm_map_entry *first, *last, *entry, *new; 956 struct uvm_map_deadq dead; 957 vm_prot_t prot; 958 vm_prot_t maxprot; 959 vm_inherit_t inherit; 960 int advice; 961 int error; 962 vaddr_t pmap_align, pmap_offset; 963 vaddr_t hint; 964 965 KASSERT((map->flags & VM_MAP_ISVMSPACE) == VM_MAP_ISVMSPACE); 966 KASSERT(map != kernel_map); 967 KASSERT((map->flags & UVM_FLAG_HOLE) == 0); 968 KASSERT((map->flags & VM_MAP_INTRSAFE) == 0); 969 splassert(IPL_NONE); 970 KASSERT((flags & UVM_FLAG_TRYLOCK) == 0); 971 972 /* 973 * We use pmap_align and pmap_offset as alignment and offset variables. 974 * 975 * Because the align parameter takes precedence over pmap prefer, 976 * the pmap_align will need to be set to align, with pmap_offset = 0, 977 * if pmap_prefer will not align. 978 */ 979 pmap_align = MAX(align, PAGE_SIZE); 980 pmap_offset = 0; 981 982 /* Decode parameters. */ 983 prot = UVM_PROTECTION(flags); 984 maxprot = UVM_MAXPROTECTION(flags); 985 advice = UVM_ADVICE(flags); 986 inherit = UVM_INHERIT(flags); 987 error = 0; 988 hint = trunc_page(*addr); 989 TAILQ_INIT(&dead); 990 KASSERT((sz & (vaddr_t)PAGE_MASK) == 0); 991 KASSERT((align & (align - 1)) == 0); 992 993 /* Check protection. */ 994 if ((prot & maxprot) != prot) 995 return EACCES; 996 997 /* 998 * Before grabbing the lock, allocate a map entry for later 999 * use to ensure we don't wait for memory while holding the 1000 * vm_map_lock. 1001 */ 1002 new = uvm_mapent_alloc(map, flags); 1003 if (new == NULL) 1004 return(ENOMEM); 1005 1006 vm_map_lock(map); 1007 first = last = NULL; 1008 if (flags & UVM_FLAG_FIXED) { 1009 /* 1010 * Fixed location. 1011 * 1012 * Note: we ignore align, pmap_prefer. 1013 * Fill in first, last and *addr. 1014 */ 1015 KASSERT((*addr & PAGE_MASK) == 0); 1016 1017 /* Check that the space is available. */ 1018 if (flags & UVM_FLAG_UNMAP) { 1019 if ((flags & UVM_FLAG_STACK) && 1020 !uvm_map_is_stack_remappable(map, *addr, sz)) { 1021 error = EINVAL; 1022 goto unlock; 1023 } 1024 uvm_unmap_remove(map, *addr, *addr + sz, &dead, FALSE, TRUE); 1025 } 1026 if (!uvm_map_isavail(map, NULL, &first, &last, *addr, sz)) { 1027 error = ENOMEM; 1028 goto unlock; 1029 } 1030 } else if (*addr != 0 && (*addr & PAGE_MASK) == 0 && 1031 (align == 0 || (*addr & (align - 1)) == 0) && 1032 uvm_map_isavail(map, NULL, &first, &last, *addr, sz)) { 1033 /* 1034 * Address used as hint. 1035 * 1036 * Note: we enforce the alignment restriction, 1037 * but ignore pmap_prefer. 1038 */ 1039 } else if ((prot & PROT_EXEC) != 0 && map->uaddr_exe != NULL) { 1040 /* Run selection algorithm for executables. */ 1041 error = uvm_addr_invoke(map, map->uaddr_exe, &first, &last, 1042 addr, sz, pmap_align, pmap_offset, prot, hint); 1043 1044 if (error != 0) 1045 goto unlock; 1046 } else { 1047 /* Update freelists from vmspace. */ 1048 uvm_map_vmspace_update(map, &dead, flags); 1049 1050 error = uvm_map_findspace(map, &first, &last, addr, sz, 1051 pmap_align, pmap_offset, prot, hint); 1052 1053 if (error != 0) 1054 goto unlock; 1055 } 1056 1057 /* Double-check if selected address doesn't cause overflow. */ 1058 if (*addr + sz < *addr) { 1059 error = ENOMEM; 1060 goto unlock; 1061 } 1062 1063 /* If we only want a query, return now. */ 1064 if (flags & UVM_FLAG_QUERY) { 1065 error = 0; 1066 goto unlock; 1067 } 1068 1069 /* 1070 * Create new entry. 1071 * first and last may be invalidated after this call. 1072 */ 1073 entry = uvm_map_mkentry(map, first, last, *addr, sz, flags, &dead, 1074 new); 1075 if (entry == NULL) { 1076 error = ENOMEM; 1077 goto unlock; 1078 } 1079 new = NULL; 1080 KDASSERT(entry->start == *addr && entry->end == *addr + sz); 1081 entry->object.uvm_obj = NULL; 1082 entry->offset = 0; 1083 entry->protection = prot; 1084 entry->max_protection = maxprot; 1085 entry->inheritance = inherit; 1086 entry->wired_count = 0; 1087 entry->advice = advice; 1088 if (prot & PROT_WRITE) 1089 map->wserial++; 1090 if (flags & UVM_FLAG_SYSCALL) { 1091 entry->etype |= UVM_ET_SYSCALL; 1092 map->wserial++; 1093 } 1094 if (flags & UVM_FLAG_STACK) { 1095 entry->etype |= UVM_ET_STACK; 1096 if (flags & (UVM_FLAG_FIXED | UVM_FLAG_UNMAP)) 1097 map->sserial++; 1098 } 1099 if (flags & UVM_FLAG_COPYONW) { 1100 entry->etype |= UVM_ET_COPYONWRITE; 1101 if ((flags & UVM_FLAG_OVERLAY) == 0) 1102 entry->etype |= UVM_ET_NEEDSCOPY; 1103 } 1104 if (flags & UVM_FLAG_CONCEAL) 1105 entry->etype |= UVM_ET_CONCEAL; 1106 if (flags & UVM_FLAG_OVERLAY) { 1107 entry->aref.ar_pageoff = 0; 1108 entry->aref.ar_amap = amap_alloc(sz, M_WAITOK, 0); 1109 } 1110 1111 /* Update map and process statistics. */ 1112 map->size += sz; 1113 if (prot != PROT_NONE) { 1114 ((struct vmspace *)map)->vm_dused += 1115 uvmspace_dused(map, *addr, *addr + sz); 1116 } 1117 1118 unlock: 1119 vm_map_unlock(map); 1120 1121 /* 1122 * Remove dead entries. 1123 * 1124 * Dead entries may be the result of merging. 1125 * uvm_map_mkentry may also create dead entries, when it attempts to 1126 * destroy free-space entries. 1127 */ 1128 uvm_unmap_detach(&dead, 0); 1129 1130 if (new) 1131 uvm_mapent_free(new); 1132 return error; 1133 } 1134 1135 /* 1136 * uvm_map: establish a valid mapping in map 1137 * 1138 * => *addr and sz must be a multiple of PAGE_SIZE. 1139 * => map must be unlocked. 1140 * => <uobj,uoffset> value meanings (4 cases): 1141 * [1] <NULL,uoffset> == uoffset is a hint for PMAP_PREFER 1142 * [2] <NULL,UVM_UNKNOWN_OFFSET> == don't PMAP_PREFER 1143 * [3] <uobj,uoffset> == normal mapping 1144 * [4] <uobj,UVM_UNKNOWN_OFFSET> == uvm_map finds offset based on VA 1145 * 1146 * case [4] is for kernel mappings where we don't know the offset until 1147 * we've found a virtual address. note that kernel object offsets are 1148 * always relative to vm_map_min(kernel_map). 1149 * 1150 * => align: align vaddr, must be a power-of-2. 1151 * Align is only a hint and will be ignored if the alignment fails. 1152 */ 1153 int 1154 uvm_map(struct vm_map *map, vaddr_t *addr, vsize_t sz, 1155 struct uvm_object *uobj, voff_t uoffset, 1156 vsize_t align, unsigned int flags) 1157 { 1158 struct vm_map_entry *first, *last, *entry, *new; 1159 struct uvm_map_deadq dead; 1160 vm_prot_t prot; 1161 vm_prot_t maxprot; 1162 vm_inherit_t inherit; 1163 int advice; 1164 int error; 1165 vaddr_t pmap_align, pmap_offset; 1166 vaddr_t hint; 1167 1168 if ((map->flags & VM_MAP_INTRSAFE) == 0) 1169 splassert(IPL_NONE); 1170 else 1171 splassert(IPL_VM); 1172 1173 /* 1174 * We use pmap_align and pmap_offset as alignment and offset variables. 1175 * 1176 * Because the align parameter takes precedence over pmap prefer, 1177 * the pmap_align will need to be set to align, with pmap_offset = 0, 1178 * if pmap_prefer will not align. 1179 */ 1180 if (uoffset == UVM_UNKNOWN_OFFSET) { 1181 pmap_align = MAX(align, PAGE_SIZE); 1182 pmap_offset = 0; 1183 } else { 1184 pmap_align = MAX(PMAP_PREFER_ALIGN(), PAGE_SIZE); 1185 pmap_offset = PMAP_PREFER_OFFSET(uoffset); 1186 1187 if (align == 0 || 1188 (align <= pmap_align && (pmap_offset & (align - 1)) == 0)) { 1189 /* pmap_offset satisfies align, no change. */ 1190 } else { 1191 /* Align takes precedence over pmap prefer. */ 1192 pmap_align = align; 1193 pmap_offset = 0; 1194 } 1195 } 1196 1197 /* Decode parameters. */ 1198 prot = UVM_PROTECTION(flags); 1199 maxprot = UVM_MAXPROTECTION(flags); 1200 advice = UVM_ADVICE(flags); 1201 inherit = UVM_INHERIT(flags); 1202 error = 0; 1203 hint = trunc_page(*addr); 1204 TAILQ_INIT(&dead); 1205 KASSERT((sz & (vaddr_t)PAGE_MASK) == 0); 1206 KASSERT((align & (align - 1)) == 0); 1207 1208 /* Holes are incompatible with other types of mappings. */ 1209 if (flags & UVM_FLAG_HOLE) { 1210 KASSERT(uobj == NULL && (flags & UVM_FLAG_FIXED) && 1211 (flags & (UVM_FLAG_OVERLAY | UVM_FLAG_COPYONW)) == 0); 1212 } 1213 1214 /* Unset hint for kernel_map non-fixed allocations. */ 1215 if (!(map->flags & VM_MAP_ISVMSPACE) && !(flags & UVM_FLAG_FIXED)) 1216 hint = 0; 1217 1218 /* Check protection. */ 1219 if ((prot & maxprot) != prot) 1220 return EACCES; 1221 1222 if (map == kernel_map && 1223 (prot & (PROT_WRITE | PROT_EXEC)) == (PROT_WRITE | PROT_EXEC)) 1224 panic("uvm_map: kernel map W^X violation requested"); 1225 1226 /* 1227 * Before grabbing the lock, allocate a map entry for later 1228 * use to ensure we don't wait for memory while holding the 1229 * vm_map_lock. 1230 */ 1231 new = uvm_mapent_alloc(map, flags); 1232 if (new == NULL) 1233 return(ENOMEM); 1234 1235 if (flags & UVM_FLAG_TRYLOCK) { 1236 if (vm_map_lock_try(map) == FALSE) { 1237 error = EFAULT; 1238 goto out; 1239 } 1240 } else { 1241 vm_map_lock(map); 1242 } 1243 1244 first = last = NULL; 1245 if (flags & UVM_FLAG_FIXED) { 1246 /* 1247 * Fixed location. 1248 * 1249 * Note: we ignore align, pmap_prefer. 1250 * Fill in first, last and *addr. 1251 */ 1252 KASSERT((*addr & PAGE_MASK) == 0); 1253 1254 /* 1255 * Grow pmap to include allocated address. 1256 * If the growth fails, the allocation will fail too. 1257 */ 1258 if ((map->flags & VM_MAP_ISVMSPACE) == 0 && 1259 uvm_maxkaddr < (*addr + sz)) { 1260 uvm_map_kmem_grow(map, &dead, 1261 *addr + sz - uvm_maxkaddr, flags); 1262 } 1263 1264 /* Check that the space is available. */ 1265 if (flags & UVM_FLAG_UNMAP) 1266 uvm_unmap_remove(map, *addr, *addr + sz, &dead, FALSE, TRUE); 1267 if (!uvm_map_isavail(map, NULL, &first, &last, *addr, sz)) { 1268 error = ENOMEM; 1269 goto unlock; 1270 } 1271 } else if (*addr != 0 && (*addr & PAGE_MASK) == 0 && 1272 (map->flags & VM_MAP_ISVMSPACE) == VM_MAP_ISVMSPACE && 1273 (align == 0 || (*addr & (align - 1)) == 0) && 1274 uvm_map_isavail(map, NULL, &first, &last, *addr, sz)) { 1275 /* 1276 * Address used as hint. 1277 * 1278 * Note: we enforce the alignment restriction, 1279 * but ignore pmap_prefer. 1280 */ 1281 } else if ((prot & PROT_EXEC) != 0 && map->uaddr_exe != NULL) { 1282 /* Run selection algorithm for executables. */ 1283 error = uvm_addr_invoke(map, map->uaddr_exe, &first, &last, 1284 addr, sz, pmap_align, pmap_offset, prot, hint); 1285 1286 /* Grow kernel memory and try again. */ 1287 if (error != 0 && (map->flags & VM_MAP_ISVMSPACE) == 0) { 1288 uvm_map_kmem_grow(map, &dead, sz, flags); 1289 1290 error = uvm_addr_invoke(map, map->uaddr_exe, 1291 &first, &last, addr, sz, 1292 pmap_align, pmap_offset, prot, hint); 1293 } 1294 1295 if (error != 0) 1296 goto unlock; 1297 } else { 1298 /* Update freelists from vmspace. */ 1299 if (map->flags & VM_MAP_ISVMSPACE) 1300 uvm_map_vmspace_update(map, &dead, flags); 1301 1302 error = uvm_map_findspace(map, &first, &last, addr, sz, 1303 pmap_align, pmap_offset, prot, hint); 1304 1305 /* Grow kernel memory and try again. */ 1306 if (error != 0 && (map->flags & VM_MAP_ISVMSPACE) == 0) { 1307 uvm_map_kmem_grow(map, &dead, sz, flags); 1308 1309 error = uvm_map_findspace(map, &first, &last, addr, sz, 1310 pmap_align, pmap_offset, prot, hint); 1311 } 1312 1313 if (error != 0) 1314 goto unlock; 1315 } 1316 1317 /* Double-check if selected address doesn't cause overflow. */ 1318 if (*addr + sz < *addr) { 1319 error = ENOMEM; 1320 goto unlock; 1321 } 1322 1323 KASSERT((map->flags & VM_MAP_ISVMSPACE) == VM_MAP_ISVMSPACE || 1324 uvm_maxkaddr >= *addr + sz); 1325 1326 /* If we only want a query, return now. */ 1327 if (flags & UVM_FLAG_QUERY) { 1328 error = 0; 1329 goto unlock; 1330 } 1331 1332 if (uobj == NULL) 1333 uoffset = 0; 1334 else if (uoffset == UVM_UNKNOWN_OFFSET) { 1335 KASSERT(UVM_OBJ_IS_KERN_OBJECT(uobj)); 1336 uoffset = *addr - vm_map_min(kernel_map); 1337 } 1338 1339 /* 1340 * Create new entry. 1341 * first and last may be invalidated after this call. 1342 */ 1343 entry = uvm_map_mkentry(map, first, last, *addr, sz, flags, &dead, 1344 new); 1345 if (entry == NULL) { 1346 error = ENOMEM; 1347 goto unlock; 1348 } 1349 new = NULL; 1350 KDASSERT(entry->start == *addr && entry->end == *addr + sz); 1351 entry->object.uvm_obj = uobj; 1352 entry->offset = uoffset; 1353 entry->protection = prot; 1354 entry->max_protection = maxprot; 1355 entry->inheritance = inherit; 1356 entry->wired_count = 0; 1357 entry->advice = advice; 1358 if (prot & PROT_WRITE) 1359 map->wserial++; 1360 if (flags & UVM_FLAG_SYSCALL) { 1361 entry->etype |= UVM_ET_SYSCALL; 1362 map->wserial++; 1363 } 1364 if (flags & UVM_FLAG_STACK) { 1365 entry->etype |= UVM_ET_STACK; 1366 if (flags & UVM_FLAG_UNMAP) 1367 map->sserial++; 1368 } 1369 if (uobj) 1370 entry->etype |= UVM_ET_OBJ; 1371 else if (flags & UVM_FLAG_HOLE) 1372 entry->etype |= UVM_ET_HOLE; 1373 if (flags & UVM_FLAG_NOFAULT) 1374 entry->etype |= UVM_ET_NOFAULT; 1375 if (flags & UVM_FLAG_WC) 1376 entry->etype |= UVM_ET_WC; 1377 if (flags & UVM_FLAG_COPYONW) { 1378 entry->etype |= UVM_ET_COPYONWRITE; 1379 if ((flags & UVM_FLAG_OVERLAY) == 0) 1380 entry->etype |= UVM_ET_NEEDSCOPY; 1381 } 1382 if (flags & UVM_FLAG_CONCEAL) 1383 entry->etype |= UVM_ET_CONCEAL; 1384 if (flags & UVM_FLAG_OVERLAY) { 1385 entry->aref.ar_pageoff = 0; 1386 entry->aref.ar_amap = amap_alloc(sz, M_WAITOK, 0); 1387 } 1388 1389 /* Update map and process statistics. */ 1390 if (!(flags & UVM_FLAG_HOLE)) { 1391 map->size += sz; 1392 if ((map->flags & VM_MAP_ISVMSPACE) && uobj == NULL && 1393 prot != PROT_NONE) { 1394 ((struct vmspace *)map)->vm_dused += 1395 uvmspace_dused(map, *addr, *addr + sz); 1396 } 1397 } 1398 1399 /* 1400 * Try to merge entry. 1401 * 1402 * Userland allocations are kept separated most of the time. 1403 * Forego the effort of merging what most of the time can't be merged 1404 * and only try the merge if it concerns a kernel entry. 1405 */ 1406 if ((flags & UVM_FLAG_NOMERGE) == 0 && 1407 (map->flags & VM_MAP_ISVMSPACE) == 0) 1408 uvm_mapent_tryjoin(map, entry, &dead); 1409 1410 unlock: 1411 vm_map_unlock(map); 1412 1413 /* 1414 * Remove dead entries. 1415 * 1416 * Dead entries may be the result of merging. 1417 * uvm_map_mkentry may also create dead entries, when it attempts to 1418 * destroy free-space entries. 1419 */ 1420 if (map->flags & VM_MAP_INTRSAFE) 1421 uvm_unmap_detach_intrsafe(&dead); 1422 else 1423 uvm_unmap_detach(&dead, 0); 1424 out: 1425 if (new) 1426 uvm_mapent_free(new); 1427 return error; 1428 } 1429 1430 /* 1431 * True iff e1 and e2 can be joined together. 1432 */ 1433 int 1434 uvm_mapent_isjoinable(struct vm_map *map, struct vm_map_entry *e1, 1435 struct vm_map_entry *e2) 1436 { 1437 KDASSERT(e1 != NULL && e2 != NULL); 1438 1439 /* Must be the same entry type and not have free memory between. */ 1440 if (e1->etype != e2->etype || e1->end != e2->start) 1441 return 0; 1442 1443 /* Submaps are never joined. */ 1444 if (UVM_ET_ISSUBMAP(e1)) 1445 return 0; 1446 1447 /* Never merge wired memory. */ 1448 if (VM_MAPENT_ISWIRED(e1) || VM_MAPENT_ISWIRED(e2)) 1449 return 0; 1450 1451 /* Protection, inheritance and advice must be equal. */ 1452 if (e1->protection != e2->protection || 1453 e1->max_protection != e2->max_protection || 1454 e1->inheritance != e2->inheritance || 1455 e1->advice != e2->advice) 1456 return 0; 1457 1458 /* If uvm_object: object itself and offsets within object must match. */ 1459 if (UVM_ET_ISOBJ(e1)) { 1460 if (e1->object.uvm_obj != e2->object.uvm_obj) 1461 return 0; 1462 if (e1->offset + (e1->end - e1->start) != e2->offset) 1463 return 0; 1464 } 1465 1466 /* 1467 * Cannot join shared amaps. 1468 * Note: no need to lock amap to look at refs, since we don't care 1469 * about its exact value. 1470 * If it is 1 (i.e. we have the only reference) it will stay there. 1471 */ 1472 if (e1->aref.ar_amap && amap_refs(e1->aref.ar_amap) != 1) 1473 return 0; 1474 if (e2->aref.ar_amap && amap_refs(e2->aref.ar_amap) != 1) 1475 return 0; 1476 1477 /* Apprently, e1 and e2 match. */ 1478 return 1; 1479 } 1480 1481 /* 1482 * Join support function. 1483 * 1484 * Returns the merged entry on succes. 1485 * Returns NULL if the merge failed. 1486 */ 1487 struct vm_map_entry* 1488 uvm_mapent_merge(struct vm_map *map, struct vm_map_entry *e1, 1489 struct vm_map_entry *e2, struct uvm_map_deadq *dead) 1490 { 1491 struct uvm_addr_state *free; 1492 1493 /* 1494 * Merging is not supported for map entries that 1495 * contain an amap in e1. This should never happen 1496 * anyway, because only kernel entries are merged. 1497 * These do not contain amaps. 1498 * e2 contains no real information in its amap, 1499 * so it can be erased immediately. 1500 */ 1501 KASSERT(e1->aref.ar_amap == NULL); 1502 1503 /* 1504 * Don't drop obj reference: 1505 * uvm_unmap_detach will do this for us. 1506 */ 1507 free = uvm_map_uaddr_e(map, e1); 1508 uvm_mapent_free_remove(map, free, e1); 1509 1510 free = uvm_map_uaddr_e(map, e2); 1511 uvm_mapent_free_remove(map, free, e2); 1512 uvm_mapent_addr_remove(map, e2); 1513 e1->end = e2->end; 1514 e1->guard = e2->guard; 1515 e1->fspace = e2->fspace; 1516 uvm_mapent_free_insert(map, free, e1); 1517 1518 DEAD_ENTRY_PUSH(dead, e2); 1519 return e1; 1520 } 1521 1522 /* 1523 * Attempt forward and backward joining of entry. 1524 * 1525 * Returns entry after joins. 1526 * We are guaranteed that the amap of entry is either non-existent or 1527 * has never been used. 1528 */ 1529 struct vm_map_entry* 1530 uvm_mapent_tryjoin(struct vm_map *map, struct vm_map_entry *entry, 1531 struct uvm_map_deadq *dead) 1532 { 1533 struct vm_map_entry *other; 1534 struct vm_map_entry *merged; 1535 1536 /* Merge with previous entry. */ 1537 other = RBT_PREV(uvm_map_addr, entry); 1538 if (other && uvm_mapent_isjoinable(map, other, entry)) { 1539 merged = uvm_mapent_merge(map, other, entry, dead); 1540 if (merged) 1541 entry = merged; 1542 } 1543 1544 /* 1545 * Merge with next entry. 1546 * 1547 * Because amap can only extend forward and the next entry 1548 * probably contains sensible info, only perform forward merging 1549 * in the absence of an amap. 1550 */ 1551 other = RBT_NEXT(uvm_map_addr, entry); 1552 if (other && entry->aref.ar_amap == NULL && 1553 other->aref.ar_amap == NULL && 1554 uvm_mapent_isjoinable(map, entry, other)) { 1555 merged = uvm_mapent_merge(map, entry, other, dead); 1556 if (merged) 1557 entry = merged; 1558 } 1559 1560 return entry; 1561 } 1562 1563 /* 1564 * Kill entries that are no longer in a map. 1565 */ 1566 void 1567 uvm_unmap_detach(struct uvm_map_deadq *deadq, int flags) 1568 { 1569 struct vm_map_entry *entry, *tmp; 1570 int waitok = flags & UVM_PLA_WAITOK; 1571 1572 TAILQ_FOREACH_SAFE(entry, deadq, dfree.deadq, tmp) { 1573 /* Skip entries for which we have to grab the kernel lock. */ 1574 if (entry->aref.ar_amap || UVM_ET_ISSUBMAP(entry) || 1575 UVM_ET_ISOBJ(entry)) 1576 continue; 1577 1578 TAILQ_REMOVE(deadq, entry, dfree.deadq); 1579 uvm_mapent_free(entry); 1580 } 1581 1582 if (TAILQ_EMPTY(deadq)) 1583 return; 1584 1585 KERNEL_LOCK(); 1586 while ((entry = TAILQ_FIRST(deadq)) != NULL) { 1587 if (waitok) 1588 uvm_pause(); 1589 /* Drop reference to amap, if we've got one. */ 1590 if (entry->aref.ar_amap) 1591 amap_unref(entry->aref.ar_amap, 1592 entry->aref.ar_pageoff, 1593 atop(entry->end - entry->start), 1594 flags & AMAP_REFALL); 1595 1596 /* Drop reference to our backing object, if we've got one. */ 1597 if (UVM_ET_ISSUBMAP(entry)) { 1598 /* ... unlikely to happen, but play it safe */ 1599 uvm_map_deallocate(entry->object.sub_map); 1600 } else if (UVM_ET_ISOBJ(entry) && 1601 entry->object.uvm_obj->pgops->pgo_detach) { 1602 entry->object.uvm_obj->pgops->pgo_detach( 1603 entry->object.uvm_obj); 1604 } 1605 1606 /* Step to next. */ 1607 TAILQ_REMOVE(deadq, entry, dfree.deadq); 1608 uvm_mapent_free(entry); 1609 } 1610 KERNEL_UNLOCK(); 1611 } 1612 1613 void 1614 uvm_unmap_detach_intrsafe(struct uvm_map_deadq *deadq) 1615 { 1616 struct vm_map_entry *entry; 1617 1618 while ((entry = TAILQ_FIRST(deadq)) != NULL) { 1619 KASSERT(entry->aref.ar_amap == NULL); 1620 KASSERT(!UVM_ET_ISSUBMAP(entry)); 1621 KASSERT(!UVM_ET_ISOBJ(entry)); 1622 TAILQ_REMOVE(deadq, entry, dfree.deadq); 1623 uvm_mapent_free(entry); 1624 } 1625 } 1626 1627 /* 1628 * Create and insert new entry. 1629 * 1630 * Returned entry contains new addresses and is inserted properly in the tree. 1631 * first and last are (probably) no longer valid. 1632 */ 1633 struct vm_map_entry* 1634 uvm_map_mkentry(struct vm_map *map, struct vm_map_entry *first, 1635 struct vm_map_entry *last, vaddr_t addr, vsize_t sz, int flags, 1636 struct uvm_map_deadq *dead, struct vm_map_entry *new) 1637 { 1638 struct vm_map_entry *entry, *prev; 1639 struct uvm_addr_state *free; 1640 vaddr_t min, max; /* free space boundaries for new entry */ 1641 1642 KDASSERT(map != NULL); 1643 KDASSERT(first != NULL); 1644 KDASSERT(last != NULL); 1645 KDASSERT(dead != NULL); 1646 KDASSERT(sz > 0); 1647 KDASSERT(addr + sz > addr); 1648 KDASSERT(first->end <= addr && VMMAP_FREE_END(first) > addr); 1649 KDASSERT(last->start < addr + sz && VMMAP_FREE_END(last) >= addr + sz); 1650 KDASSERT(uvm_map_isavail(map, NULL, &first, &last, addr, sz)); 1651 uvm_tree_sanity(map, __FILE__, __LINE__); 1652 1653 min = addr + sz; 1654 max = VMMAP_FREE_END(last); 1655 1656 /* Initialize new entry. */ 1657 if (new == NULL) 1658 entry = uvm_mapent_alloc(map, flags); 1659 else 1660 entry = new; 1661 if (entry == NULL) 1662 return NULL; 1663 entry->offset = 0; 1664 entry->etype = 0; 1665 entry->wired_count = 0; 1666 entry->aref.ar_pageoff = 0; 1667 entry->aref.ar_amap = NULL; 1668 1669 entry->start = addr; 1670 entry->end = min; 1671 entry->guard = 0; 1672 entry->fspace = 0; 1673 1674 /* Reset free space in first. */ 1675 free = uvm_map_uaddr_e(map, first); 1676 uvm_mapent_free_remove(map, free, first); 1677 first->guard = 0; 1678 first->fspace = 0; 1679 1680 /* 1681 * Remove all entries that are fully replaced. 1682 * We are iterating using last in reverse order. 1683 */ 1684 for (; first != last; last = prev) { 1685 prev = RBT_PREV(uvm_map_addr, last); 1686 1687 KDASSERT(last->start == last->end); 1688 free = uvm_map_uaddr_e(map, last); 1689 uvm_mapent_free_remove(map, free, last); 1690 uvm_mapent_addr_remove(map, last); 1691 DEAD_ENTRY_PUSH(dead, last); 1692 } 1693 /* Remove first if it is entirely inside <addr, addr+sz>. */ 1694 if (first->start == addr) { 1695 uvm_mapent_addr_remove(map, first); 1696 DEAD_ENTRY_PUSH(dead, first); 1697 } else { 1698 uvm_map_fix_space(map, first, VMMAP_FREE_START(first), 1699 addr, flags); 1700 } 1701 1702 /* Finally, link in entry. */ 1703 uvm_mapent_addr_insert(map, entry); 1704 uvm_map_fix_space(map, entry, min, max, flags); 1705 1706 uvm_tree_sanity(map, __FILE__, __LINE__); 1707 return entry; 1708 } 1709 1710 1711 /* 1712 * uvm_mapent_alloc: allocate a map entry 1713 */ 1714 struct vm_map_entry * 1715 uvm_mapent_alloc(struct vm_map *map, int flags) 1716 { 1717 struct vm_map_entry *me, *ne; 1718 int pool_flags; 1719 int i; 1720 1721 pool_flags = PR_WAITOK; 1722 if (flags & UVM_FLAG_TRYLOCK) 1723 pool_flags = PR_NOWAIT; 1724 1725 if (map->flags & VM_MAP_INTRSAFE || cold) { 1726 mtx_enter(&uvm_kmapent_mtx); 1727 if (SLIST_EMPTY(&uvm.kentry_free)) { 1728 ne = km_alloc(PAGE_SIZE, &kv_page, &kp_dirty, 1729 &kd_nowait); 1730 if (ne == NULL) 1731 panic("uvm_mapent_alloc: cannot allocate map " 1732 "entry"); 1733 for (i = 0; i < PAGE_SIZE / sizeof(*ne); i++) { 1734 SLIST_INSERT_HEAD(&uvm.kentry_free, 1735 &ne[i], daddrs.addr_kentry); 1736 } 1737 if (ratecheck(&uvm_kmapent_last_warn_time, 1738 &uvm_kmapent_warn_rate)) 1739 printf("uvm_mapent_alloc: out of static " 1740 "map entries\n"); 1741 } 1742 me = SLIST_FIRST(&uvm.kentry_free); 1743 SLIST_REMOVE_HEAD(&uvm.kentry_free, daddrs.addr_kentry); 1744 uvmexp.kmapent++; 1745 mtx_leave(&uvm_kmapent_mtx); 1746 me->flags = UVM_MAP_STATIC; 1747 } else if (map == kernel_map) { 1748 splassert(IPL_NONE); 1749 me = pool_get(&uvm_map_entry_kmem_pool, pool_flags); 1750 if (me == NULL) 1751 goto out; 1752 me->flags = UVM_MAP_KMEM; 1753 } else { 1754 splassert(IPL_NONE); 1755 me = pool_get(&uvm_map_entry_pool, pool_flags); 1756 if (me == NULL) 1757 goto out; 1758 me->flags = 0; 1759 } 1760 1761 RBT_POISON(uvm_map_addr, me, UVMMAP_DEADBEEF); 1762 out: 1763 return(me); 1764 } 1765 1766 /* 1767 * uvm_mapent_free: free map entry 1768 * 1769 * => XXX: static pool for kernel map? 1770 */ 1771 void 1772 uvm_mapent_free(struct vm_map_entry *me) 1773 { 1774 if (me->flags & UVM_MAP_STATIC) { 1775 mtx_enter(&uvm_kmapent_mtx); 1776 SLIST_INSERT_HEAD(&uvm.kentry_free, me, daddrs.addr_kentry); 1777 uvmexp.kmapent--; 1778 mtx_leave(&uvm_kmapent_mtx); 1779 } else if (me->flags & UVM_MAP_KMEM) { 1780 splassert(IPL_NONE); 1781 pool_put(&uvm_map_entry_kmem_pool, me); 1782 } else { 1783 splassert(IPL_NONE); 1784 pool_put(&uvm_map_entry_pool, me); 1785 } 1786 } 1787 1788 /* 1789 * uvm_map_lookup_entry: find map entry at or before an address. 1790 * 1791 * => map must at least be read-locked by caller 1792 * => entry is returned in "entry" 1793 * => return value is true if address is in the returned entry 1794 * ET_HOLE entries are considered to not contain a mapping, ergo FALSE is 1795 * returned for those mappings. 1796 */ 1797 boolean_t 1798 uvm_map_lookup_entry(struct vm_map *map, vaddr_t address, 1799 struct vm_map_entry **entry) 1800 { 1801 *entry = uvm_map_entrybyaddr(&map->addr, address); 1802 return *entry != NULL && !UVM_ET_ISHOLE(*entry) && 1803 (*entry)->start <= address && (*entry)->end > address; 1804 } 1805 1806 /* 1807 * Stack must be in a MAP_STACK entry. PROT_NONE indicates stack not yet 1808 * grown -- then uvm_map_check_region_range() should not cache the entry 1809 * because growth won't be seen. 1810 */ 1811 int 1812 uvm_map_inentry_sp(vm_map_entry_t entry) 1813 { 1814 if ((entry->etype & UVM_ET_STACK) == 0) { 1815 if (entry->protection == PROT_NONE) 1816 return (-1); /* don't update range */ 1817 return (0); 1818 } 1819 return (1); 1820 } 1821 1822 /* 1823 * The system call must not come from a writeable entry, W^X is violated. 1824 * (Would be nice if we can spot aliasing, which is also kind of bad) 1825 * 1826 * The system call must come from an syscall-labeled entry (which are 1827 * the text regions of the main program, sigtramp, ld.so, or libc). 1828 */ 1829 int 1830 uvm_map_inentry_pc(vm_map_entry_t entry) 1831 { 1832 if (entry->protection & PROT_WRITE) 1833 return (0); /* not permitted */ 1834 if ((entry->etype & UVM_ET_SYSCALL) == 0) 1835 return (0); /* not permitted */ 1836 return (1); 1837 } 1838 1839 int 1840 uvm_map_inentry_recheck(u_long serial, vaddr_t addr, struct p_inentry *ie) 1841 { 1842 return (serial != ie->ie_serial || ie->ie_start == 0 || 1843 addr < ie->ie_start || addr >= ie->ie_end); 1844 } 1845 1846 /* 1847 * Inside a vm_map find the reg address and verify it via function. 1848 * Remember low and high addresses of region if valid and return TRUE, 1849 * else return FALSE. 1850 */ 1851 boolean_t 1852 uvm_map_inentry_fix(struct proc *p, struct p_inentry *ie, vaddr_t addr, 1853 int (*fn)(vm_map_entry_t), u_long serial) 1854 { 1855 vm_map_t map = &p->p_vmspace->vm_map; 1856 vm_map_entry_t entry; 1857 int ret; 1858 1859 if (addr < map->min_offset || addr >= map->max_offset) 1860 return (FALSE); 1861 1862 /* lock map */ 1863 vm_map_lock_read(map); 1864 1865 /* lookup */ 1866 if (!uvm_map_lookup_entry(map, trunc_page(addr), &entry)) { 1867 vm_map_unlock_read(map); 1868 return (FALSE); 1869 } 1870 1871 ret = (*fn)(entry); 1872 if (ret == 0) { 1873 vm_map_unlock_read(map); 1874 return (FALSE); 1875 } else if (ret == 1) { 1876 ie->ie_start = entry->start; 1877 ie->ie_end = entry->end; 1878 ie->ie_serial = serial; 1879 } else { 1880 /* do not update, re-check later */ 1881 } 1882 vm_map_unlock_read(map); 1883 return (TRUE); 1884 } 1885 1886 boolean_t 1887 uvm_map_inentry(struct proc *p, struct p_inentry *ie, vaddr_t addr, 1888 const char *fmt, int (*fn)(vm_map_entry_t), u_long serial) 1889 { 1890 union sigval sv; 1891 boolean_t ok = TRUE; 1892 1893 if (uvm_map_inentry_recheck(serial, addr, ie)) { 1894 ok = uvm_map_inentry_fix(p, ie, addr, fn, serial); 1895 if (!ok) { 1896 KERNEL_LOCK(); 1897 printf(fmt, p->p_p->ps_comm, p->p_p->ps_pid, p->p_tid, 1898 addr, ie->ie_start, ie->ie_end); 1899 p->p_p->ps_acflag |= AMAP; 1900 sv.sival_ptr = (void *)PROC_PC(p); 1901 trapsignal(p, SIGSEGV, 0, SEGV_ACCERR, sv); 1902 KERNEL_UNLOCK(); 1903 } 1904 } 1905 return (ok); 1906 } 1907 1908 /* 1909 * Check whether the given address range can be converted to a MAP_STACK 1910 * mapping. 1911 * 1912 * Must be called with map locked. 1913 */ 1914 boolean_t 1915 uvm_map_is_stack_remappable(struct vm_map *map, vaddr_t addr, vaddr_t sz) 1916 { 1917 vaddr_t end = addr + sz; 1918 struct vm_map_entry *first, *iter, *prev = NULL; 1919 1920 if (!uvm_map_lookup_entry(map, addr, &first)) { 1921 printf("map stack 0x%lx-0x%lx of map %p failed: no mapping\n", 1922 addr, end, map); 1923 return FALSE; 1924 } 1925 1926 /* 1927 * Check that the address range exists and is contiguous. 1928 */ 1929 for (iter = first; iter != NULL && iter->start < end; 1930 prev = iter, iter = RBT_NEXT(uvm_map_addr, iter)) { 1931 /* 1932 * Make sure that we do not have holes in the range. 1933 */ 1934 #if 0 1935 if (prev != NULL) { 1936 printf("prev->start 0x%lx, prev->end 0x%lx, " 1937 "iter->start 0x%lx, iter->end 0x%lx\n", 1938 prev->start, prev->end, iter->start, iter->end); 1939 } 1940 #endif 1941 1942 if (prev != NULL && prev->end != iter->start) { 1943 printf("map stack 0x%lx-0x%lx of map %p failed: " 1944 "hole in range\n", addr, end, map); 1945 return FALSE; 1946 } 1947 if (iter->start == iter->end || UVM_ET_ISHOLE(iter)) { 1948 printf("map stack 0x%lx-0x%lx of map %p failed: " 1949 "hole in range\n", addr, end, map); 1950 return FALSE; 1951 } 1952 } 1953 1954 return TRUE; 1955 } 1956 1957 /* 1958 * Remap the middle-pages of an existing mapping as a stack range. 1959 * If there exists a previous contiguous mapping with the given range 1960 * [addr, addr + sz), with protection PROT_READ|PROT_WRITE, then the 1961 * mapping is dropped, and a new anon mapping is created and marked as 1962 * a stack. 1963 * 1964 * Must be called with map unlocked. 1965 */ 1966 int 1967 uvm_map_remap_as_stack(struct proc *p, vaddr_t addr, vaddr_t sz) 1968 { 1969 vm_map_t map = &p->p_vmspace->vm_map; 1970 vaddr_t start, end; 1971 int error; 1972 int flags = UVM_MAPFLAG(PROT_READ | PROT_WRITE, 1973 PROT_READ | PROT_WRITE | PROT_EXEC, 1974 MAP_INHERIT_COPY, MADV_NORMAL, 1975 UVM_FLAG_STACK | UVM_FLAG_FIXED | UVM_FLAG_UNMAP | 1976 UVM_FLAG_COPYONW); 1977 1978 start = round_page(addr); 1979 end = trunc_page(addr + sz); 1980 #ifdef MACHINE_STACK_GROWS_UP 1981 if (end == addr + sz) 1982 end -= PAGE_SIZE; 1983 #else 1984 if (start == addr) 1985 start += PAGE_SIZE; 1986 #endif 1987 1988 if (start < map->min_offset || end >= map->max_offset || end < start) 1989 return EINVAL; 1990 1991 error = uvm_mapanon(map, &start, end - start, 0, flags); 1992 if (error != 0) 1993 printf("map stack for pid %d failed\n", p->p_p->ps_pid); 1994 1995 return error; 1996 } 1997 1998 /* 1999 * uvm_map_pie: return a random load address for a PIE executable 2000 * properly aligned. 2001 */ 2002 #ifndef VM_PIE_MAX_ADDR 2003 #define VM_PIE_MAX_ADDR (VM_MAXUSER_ADDRESS / 4) 2004 #endif 2005 2006 #ifndef VM_PIE_MIN_ADDR 2007 #define VM_PIE_MIN_ADDR VM_MIN_ADDRESS 2008 #endif 2009 2010 #ifndef VM_PIE_MIN_ALIGN 2011 #define VM_PIE_MIN_ALIGN PAGE_SIZE 2012 #endif 2013 2014 vaddr_t 2015 uvm_map_pie(vaddr_t align) 2016 { 2017 vaddr_t addr, space, min; 2018 2019 align = MAX(align, VM_PIE_MIN_ALIGN); 2020 2021 /* round up to next alignment */ 2022 min = (VM_PIE_MIN_ADDR + align - 1) & ~(align - 1); 2023 2024 if (align >= VM_PIE_MAX_ADDR || min >= VM_PIE_MAX_ADDR) 2025 return (align); 2026 2027 space = (VM_PIE_MAX_ADDR - min) / align; 2028 space = MIN(space, (u_int32_t)-1); 2029 2030 addr = (vaddr_t)arc4random_uniform((u_int32_t)space) * align; 2031 addr += min; 2032 2033 return (addr); 2034 } 2035 2036 void 2037 uvm_unmap(struct vm_map *map, vaddr_t start, vaddr_t end) 2038 { 2039 struct uvm_map_deadq dead; 2040 2041 KASSERT((start & (vaddr_t)PAGE_MASK) == 0 && 2042 (end & (vaddr_t)PAGE_MASK) == 0); 2043 TAILQ_INIT(&dead); 2044 vm_map_lock(map); 2045 uvm_unmap_remove(map, start, end, &dead, FALSE, TRUE); 2046 vm_map_unlock(map); 2047 2048 if (map->flags & VM_MAP_INTRSAFE) 2049 uvm_unmap_detach_intrsafe(&dead); 2050 else 2051 uvm_unmap_detach(&dead, 0); 2052 } 2053 2054 /* 2055 * Mark entry as free. 2056 * 2057 * entry will be put on the dead list. 2058 * The free space will be merged into the previous or a new entry, 2059 * unless markfree is false. 2060 */ 2061 void 2062 uvm_mapent_mkfree(struct vm_map *map, struct vm_map_entry *entry, 2063 struct vm_map_entry **prev_ptr, struct uvm_map_deadq *dead, 2064 boolean_t markfree) 2065 { 2066 struct uvm_addr_state *free; 2067 struct vm_map_entry *prev; 2068 vaddr_t addr; /* Start of freed range. */ 2069 vaddr_t end; /* End of freed range. */ 2070 2071 prev = *prev_ptr; 2072 if (prev == entry) 2073 *prev_ptr = prev = NULL; 2074 2075 if (prev == NULL || 2076 VMMAP_FREE_END(prev) != entry->start) 2077 prev = RBT_PREV(uvm_map_addr, entry); 2078 2079 /* Entry is describing only free memory and has nothing to drain into. */ 2080 if (prev == NULL && entry->start == entry->end && markfree) { 2081 *prev_ptr = entry; 2082 return; 2083 } 2084 2085 addr = entry->start; 2086 end = VMMAP_FREE_END(entry); 2087 free = uvm_map_uaddr_e(map, entry); 2088 uvm_mapent_free_remove(map, free, entry); 2089 uvm_mapent_addr_remove(map, entry); 2090 DEAD_ENTRY_PUSH(dead, entry); 2091 2092 if (markfree) { 2093 if (prev) { 2094 free = uvm_map_uaddr_e(map, prev); 2095 uvm_mapent_free_remove(map, free, prev); 2096 } 2097 *prev_ptr = uvm_map_fix_space(map, prev, addr, end, 0); 2098 } 2099 } 2100 2101 /* 2102 * Unwire and release referenced amap and object from map entry. 2103 */ 2104 void 2105 uvm_unmap_kill_entry(struct vm_map *map, struct vm_map_entry *entry) 2106 { 2107 /* Unwire removed map entry. */ 2108 if (VM_MAPENT_ISWIRED(entry)) { 2109 KERNEL_LOCK(); 2110 entry->wired_count = 0; 2111 uvm_fault_unwire_locked(map, entry->start, entry->end); 2112 KERNEL_UNLOCK(); 2113 } 2114 2115 /* Entry-type specific code. */ 2116 if (UVM_ET_ISHOLE(entry)) { 2117 /* Nothing to be done for holes. */ 2118 } else if (map->flags & VM_MAP_INTRSAFE) { 2119 KASSERT(vm_map_pmap(map) == pmap_kernel()); 2120 uvm_km_pgremove_intrsafe(entry->start, entry->end); 2121 pmap_kremove(entry->start, entry->end - entry->start); 2122 } else if (UVM_ET_ISOBJ(entry) && 2123 UVM_OBJ_IS_KERN_OBJECT(entry->object.uvm_obj)) { 2124 KASSERT(vm_map_pmap(map) == pmap_kernel()); 2125 /* 2126 * Note: kernel object mappings are currently used in 2127 * two ways: 2128 * [1] "normal" mappings of pages in the kernel object 2129 * [2] uvm_km_valloc'd allocations in which we 2130 * pmap_enter in some non-kernel-object page 2131 * (e.g. vmapbuf). 2132 * 2133 * for case [1], we need to remove the mapping from 2134 * the pmap and then remove the page from the kernel 2135 * object (because, once pages in a kernel object are 2136 * unmapped they are no longer needed, unlike, say, 2137 * a vnode where you might want the data to persist 2138 * until flushed out of a queue). 2139 * 2140 * for case [2], we need to remove the mapping from 2141 * the pmap. there shouldn't be any pages at the 2142 * specified offset in the kernel object [but it 2143 * doesn't hurt to call uvm_km_pgremove just to be 2144 * safe?] 2145 * 2146 * uvm_km_pgremove currently does the following: 2147 * for pages in the kernel object range: 2148 * - drops the swap slot 2149 * - uvm_pagefree the page 2150 * 2151 * note there is version of uvm_km_pgremove() that 2152 * is used for "intrsafe" objects. 2153 */ 2154 /* 2155 * remove mappings from pmap and drop the pages 2156 * from the object. offsets are always relative 2157 * to vm_map_min(kernel_map). 2158 */ 2159 pmap_remove(pmap_kernel(), entry->start, entry->end); 2160 uvm_km_pgremove(entry->object.uvm_obj, 2161 entry->start - vm_map_min(kernel_map), 2162 entry->end - vm_map_min(kernel_map)); 2163 2164 /* 2165 * null out kernel_object reference, we've just 2166 * dropped it 2167 */ 2168 entry->etype &= ~UVM_ET_OBJ; 2169 entry->object.uvm_obj = NULL; /* to be safe */ 2170 } else { 2171 /* remove mappings the standard way. */ 2172 pmap_remove(map->pmap, entry->start, entry->end); 2173 } 2174 } 2175 2176 /* 2177 * Remove all entries from start to end. 2178 * 2179 * If remove_holes, then remove ET_HOLE entries as well. 2180 * If markfree, entry will be properly marked free, otherwise, no replacement 2181 * entry will be put in the tree (corrupting the tree). 2182 */ 2183 void 2184 uvm_unmap_remove(struct vm_map *map, vaddr_t start, vaddr_t end, 2185 struct uvm_map_deadq *dead, boolean_t remove_holes, 2186 boolean_t markfree) 2187 { 2188 struct vm_map_entry *prev_hint, *next, *entry; 2189 2190 start = MAX(start, map->min_offset); 2191 end = MIN(end, map->max_offset); 2192 if (start >= end) 2193 return; 2194 2195 if ((map->flags & VM_MAP_INTRSAFE) == 0) 2196 splassert(IPL_NONE); 2197 else 2198 splassert(IPL_VM); 2199 2200 /* Find first affected entry. */ 2201 entry = uvm_map_entrybyaddr(&map->addr, start); 2202 KDASSERT(entry != NULL && entry->start <= start); 2203 if (entry->end <= start && markfree) 2204 entry = RBT_NEXT(uvm_map_addr, entry); 2205 else 2206 UVM_MAP_CLIP_START(map, entry, start); 2207 2208 /* 2209 * Iterate entries until we reach end address. 2210 * prev_hint hints where the freed space can be appended to. 2211 */ 2212 prev_hint = NULL; 2213 for (; entry != NULL && entry->start < end; entry = next) { 2214 KDASSERT(entry->start >= start); 2215 if (entry->end > end || !markfree) 2216 UVM_MAP_CLIP_END(map, entry, end); 2217 KDASSERT(entry->start >= start && entry->end <= end); 2218 next = RBT_NEXT(uvm_map_addr, entry); 2219 2220 /* Don't remove holes unless asked to do so. */ 2221 if (UVM_ET_ISHOLE(entry)) { 2222 if (!remove_holes) { 2223 prev_hint = entry; 2224 continue; 2225 } 2226 } 2227 2228 /* A stack has been removed.. */ 2229 if (UVM_ET_ISSTACK(entry) && (map->flags & VM_MAP_ISVMSPACE)) 2230 map->sserial++; 2231 2232 /* Kill entry. */ 2233 uvm_unmap_kill_entry(map, entry); 2234 2235 /* Update space usage. */ 2236 if ((map->flags & VM_MAP_ISVMSPACE) && 2237 entry->object.uvm_obj == NULL && 2238 entry->protection != PROT_NONE && 2239 !UVM_ET_ISHOLE(entry)) { 2240 ((struct vmspace *)map)->vm_dused -= 2241 uvmspace_dused(map, entry->start, entry->end); 2242 } 2243 if (!UVM_ET_ISHOLE(entry)) 2244 map->size -= entry->end - entry->start; 2245 2246 /* Actual removal of entry. */ 2247 uvm_mapent_mkfree(map, entry, &prev_hint, dead, markfree); 2248 } 2249 2250 pmap_update(vm_map_pmap(map)); 2251 2252 #ifdef VMMAP_DEBUG 2253 if (markfree) { 2254 for (entry = uvm_map_entrybyaddr(&map->addr, start); 2255 entry != NULL && entry->start < end; 2256 entry = RBT_NEXT(uvm_map_addr, entry)) { 2257 KDASSERT(entry->end <= start || 2258 entry->start == entry->end || 2259 UVM_ET_ISHOLE(entry)); 2260 } 2261 } else { 2262 vaddr_t a; 2263 for (a = start; a < end; a += PAGE_SIZE) 2264 KDASSERT(uvm_map_entrybyaddr(&map->addr, a) == NULL); 2265 } 2266 #endif 2267 } 2268 2269 /* 2270 * Mark all entries from first until end (exclusive) as pageable. 2271 * 2272 * Lock must be exclusive on entry and will not be touched. 2273 */ 2274 void 2275 uvm_map_pageable_pgon(struct vm_map *map, struct vm_map_entry *first, 2276 struct vm_map_entry *end, vaddr_t start_addr, vaddr_t end_addr) 2277 { 2278 struct vm_map_entry *iter; 2279 2280 for (iter = first; iter != end; 2281 iter = RBT_NEXT(uvm_map_addr, iter)) { 2282 KDASSERT(iter->start >= start_addr && iter->end <= end_addr); 2283 if (!VM_MAPENT_ISWIRED(iter) || UVM_ET_ISHOLE(iter)) 2284 continue; 2285 2286 iter->wired_count = 0; 2287 uvm_fault_unwire_locked(map, iter->start, iter->end); 2288 } 2289 } 2290 2291 /* 2292 * Mark all entries from first until end (exclusive) as wired. 2293 * 2294 * Lockflags determines the lock state on return from this function. 2295 * Lock must be exclusive on entry. 2296 */ 2297 int 2298 uvm_map_pageable_wire(struct vm_map *map, struct vm_map_entry *first, 2299 struct vm_map_entry *end, vaddr_t start_addr, vaddr_t end_addr, 2300 int lockflags) 2301 { 2302 struct vm_map_entry *iter; 2303 #ifdef DIAGNOSTIC 2304 unsigned int timestamp_save; 2305 #endif 2306 int error; 2307 2308 /* 2309 * Wire pages in two passes: 2310 * 2311 * 1: holding the write lock, we create any anonymous maps that need 2312 * to be created. then we clip each map entry to the region to 2313 * be wired and increment its wiring count. 2314 * 2315 * 2: we downgrade to a read lock, and call uvm_fault_wire to fault 2316 * in the pages for any newly wired area (wired_count == 1). 2317 * 2318 * downgrading to a read lock for uvm_fault_wire avoids a possible 2319 * deadlock with another thread that may have faulted on one of 2320 * the pages to be wired (it would mark the page busy, blocking 2321 * us, then in turn block on the map lock that we hold). 2322 * because we keep the read lock on the map, the copy-on-write 2323 * status of the entries we modify here cannot change. 2324 */ 2325 for (iter = first; iter != end; 2326 iter = RBT_NEXT(uvm_map_addr, iter)) { 2327 KDASSERT(iter->start >= start_addr && iter->end <= end_addr); 2328 if (UVM_ET_ISHOLE(iter) || iter->start == iter->end || 2329 iter->protection == PROT_NONE) 2330 continue; 2331 2332 /* 2333 * Perform actions of vm_map_lookup that need the write lock. 2334 * - create an anonymous map for copy-on-write 2335 * - anonymous map for zero-fill 2336 * Skip submaps. 2337 */ 2338 if (!VM_MAPENT_ISWIRED(iter) && !UVM_ET_ISSUBMAP(iter) && 2339 UVM_ET_ISNEEDSCOPY(iter) && 2340 ((iter->protection & PROT_WRITE) || 2341 iter->object.uvm_obj == NULL)) { 2342 amap_copy(map, iter, M_WAITOK, 2343 UVM_ET_ISSTACK(iter) ? FALSE : TRUE, 2344 iter->start, iter->end); 2345 } 2346 iter->wired_count++; 2347 } 2348 2349 /* 2350 * Pass 2. 2351 */ 2352 #ifdef DIAGNOSTIC 2353 timestamp_save = map->timestamp; 2354 #endif 2355 vm_map_busy(map); 2356 vm_map_downgrade(map); 2357 2358 error = 0; 2359 for (iter = first; error == 0 && iter != end; 2360 iter = RBT_NEXT(uvm_map_addr, iter)) { 2361 if (UVM_ET_ISHOLE(iter) || iter->start == iter->end || 2362 iter->protection == PROT_NONE) 2363 continue; 2364 2365 error = uvm_fault_wire(map, iter->start, iter->end, 2366 iter->protection); 2367 } 2368 2369 if (error) { 2370 /* 2371 * uvm_fault_wire failure 2372 * 2373 * Reacquire lock and undo our work. 2374 */ 2375 vm_map_upgrade(map); 2376 vm_map_unbusy(map); 2377 #ifdef DIAGNOSTIC 2378 if (timestamp_save != map->timestamp) 2379 panic("uvm_map_pageable_wire: stale map"); 2380 #endif 2381 2382 /* 2383 * first is no longer needed to restart loops. 2384 * Use it as iterator to unmap successful mappings. 2385 */ 2386 for (; first != iter; 2387 first = RBT_NEXT(uvm_map_addr, first)) { 2388 if (UVM_ET_ISHOLE(first) || 2389 first->start == first->end || 2390 first->protection == PROT_NONE) 2391 continue; 2392 2393 first->wired_count--; 2394 if (!VM_MAPENT_ISWIRED(first)) { 2395 uvm_fault_unwire_locked(map, 2396 iter->start, iter->end); 2397 } 2398 } 2399 2400 /* decrease counter in the rest of the entries */ 2401 for (; iter != end; 2402 iter = RBT_NEXT(uvm_map_addr, iter)) { 2403 if (UVM_ET_ISHOLE(iter) || iter->start == iter->end || 2404 iter->protection == PROT_NONE) 2405 continue; 2406 2407 iter->wired_count--; 2408 } 2409 2410 if ((lockflags & UVM_LK_EXIT) == 0) 2411 vm_map_unlock(map); 2412 return error; 2413 } 2414 2415 /* We are currently holding a read lock. */ 2416 if ((lockflags & UVM_LK_EXIT) == 0) { 2417 vm_map_unbusy(map); 2418 vm_map_unlock_read(map); 2419 } else { 2420 vm_map_upgrade(map); 2421 vm_map_unbusy(map); 2422 #ifdef DIAGNOSTIC 2423 if (timestamp_save != map->timestamp) 2424 panic("uvm_map_pageable_wire: stale map"); 2425 #endif 2426 } 2427 return 0; 2428 } 2429 2430 /* 2431 * uvm_map_pageable: set pageability of a range in a map. 2432 * 2433 * Flags: 2434 * UVM_LK_ENTER: map is already locked by caller 2435 * UVM_LK_EXIT: don't unlock map on exit 2436 * 2437 * The full range must be in use (entries may not have fspace != 0). 2438 * UVM_ET_HOLE counts as unmapped. 2439 */ 2440 int 2441 uvm_map_pageable(struct vm_map *map, vaddr_t start, vaddr_t end, 2442 boolean_t new_pageable, int lockflags) 2443 { 2444 struct vm_map_entry *first, *last, *tmp; 2445 int error; 2446 2447 start = trunc_page(start); 2448 end = round_page(end); 2449 2450 if (start > end) 2451 return EINVAL; 2452 if (start == end) 2453 return 0; /* nothing to do */ 2454 if (start < map->min_offset) 2455 return EFAULT; /* why? see first XXX below */ 2456 if (end > map->max_offset) 2457 return EINVAL; /* why? see second XXX below */ 2458 2459 KASSERT(map->flags & VM_MAP_PAGEABLE); 2460 if ((lockflags & UVM_LK_ENTER) == 0) 2461 vm_map_lock(map); 2462 2463 /* 2464 * Find first entry. 2465 * 2466 * Initial test on start is different, because of the different 2467 * error returned. Rest is tested further down. 2468 */ 2469 first = uvm_map_entrybyaddr(&map->addr, start); 2470 if (first->end <= start || UVM_ET_ISHOLE(first)) { 2471 /* 2472 * XXX if the first address is not mapped, it is EFAULT? 2473 */ 2474 error = EFAULT; 2475 goto out; 2476 } 2477 2478 /* Check that the range has no holes. */ 2479 for (last = first; last != NULL && last->start < end; 2480 last = RBT_NEXT(uvm_map_addr, last)) { 2481 if (UVM_ET_ISHOLE(last) || 2482 (last->end < end && VMMAP_FREE_END(last) != last->end)) { 2483 /* 2484 * XXX unmapped memory in range, why is it EINVAL 2485 * instead of EFAULT? 2486 */ 2487 error = EINVAL; 2488 goto out; 2489 } 2490 } 2491 2492 /* 2493 * Last ended at the first entry after the range. 2494 * Move back one step. 2495 * 2496 * Note that last may be NULL. 2497 */ 2498 if (last == NULL) { 2499 last = RBT_MAX(uvm_map_addr, &map->addr); 2500 if (last->end < end) { 2501 error = EINVAL; 2502 goto out; 2503 } 2504 } else { 2505 KASSERT(last != first); 2506 last = RBT_PREV(uvm_map_addr, last); 2507 } 2508 2509 /* Wire/unwire pages here. */ 2510 if (new_pageable) { 2511 /* 2512 * Mark pageable. 2513 * entries that are not wired are untouched. 2514 */ 2515 if (VM_MAPENT_ISWIRED(first)) 2516 UVM_MAP_CLIP_START(map, first, start); 2517 /* 2518 * Split last at end. 2519 * Make tmp be the first entry after what is to be touched. 2520 * If last is not wired, don't touch it. 2521 */ 2522 if (VM_MAPENT_ISWIRED(last)) { 2523 UVM_MAP_CLIP_END(map, last, end); 2524 tmp = RBT_NEXT(uvm_map_addr, last); 2525 } else 2526 tmp = last; 2527 2528 uvm_map_pageable_pgon(map, first, tmp, start, end); 2529 error = 0; 2530 2531 out: 2532 if ((lockflags & UVM_LK_EXIT) == 0) 2533 vm_map_unlock(map); 2534 return error; 2535 } else { 2536 /* 2537 * Mark entries wired. 2538 * entries are always touched (because recovery needs this). 2539 */ 2540 if (!VM_MAPENT_ISWIRED(first)) 2541 UVM_MAP_CLIP_START(map, first, start); 2542 /* 2543 * Split last at end. 2544 * Make tmp be the first entry after what is to be touched. 2545 * If last is not wired, don't touch it. 2546 */ 2547 if (!VM_MAPENT_ISWIRED(last)) { 2548 UVM_MAP_CLIP_END(map, last, end); 2549 tmp = RBT_NEXT(uvm_map_addr, last); 2550 } else 2551 tmp = last; 2552 2553 return uvm_map_pageable_wire(map, first, tmp, start, end, 2554 lockflags); 2555 } 2556 } 2557 2558 /* 2559 * uvm_map_pageable_all: special case of uvm_map_pageable - affects 2560 * all mapped regions. 2561 * 2562 * Map must not be locked. 2563 * If no flags are specified, all ragions are unwired. 2564 */ 2565 int 2566 uvm_map_pageable_all(struct vm_map *map, int flags, vsize_t limit) 2567 { 2568 vsize_t size; 2569 struct vm_map_entry *iter; 2570 2571 KASSERT(map->flags & VM_MAP_PAGEABLE); 2572 vm_map_lock(map); 2573 2574 if (flags == 0) { 2575 uvm_map_pageable_pgon(map, RBT_MIN(uvm_map_addr, &map->addr), 2576 NULL, map->min_offset, map->max_offset); 2577 2578 vm_map_modflags(map, 0, VM_MAP_WIREFUTURE); 2579 vm_map_unlock(map); 2580 return 0; 2581 } 2582 2583 if (flags & MCL_FUTURE) 2584 vm_map_modflags(map, VM_MAP_WIREFUTURE, 0); 2585 if (!(flags & MCL_CURRENT)) { 2586 vm_map_unlock(map); 2587 return 0; 2588 } 2589 2590 /* 2591 * Count number of pages in all non-wired entries. 2592 * If the number exceeds the limit, abort. 2593 */ 2594 size = 0; 2595 RBT_FOREACH(iter, uvm_map_addr, &map->addr) { 2596 if (VM_MAPENT_ISWIRED(iter) || UVM_ET_ISHOLE(iter)) 2597 continue; 2598 2599 size += iter->end - iter->start; 2600 } 2601 2602 if (atop(size) + uvmexp.wired > uvmexp.wiredmax) { 2603 vm_map_unlock(map); 2604 return ENOMEM; 2605 } 2606 2607 /* XXX non-pmap_wired_count case must be handled by caller */ 2608 #ifdef pmap_wired_count 2609 if (limit != 0 && 2610 size + ptoa(pmap_wired_count(vm_map_pmap(map))) > limit) { 2611 vm_map_unlock(map); 2612 return ENOMEM; 2613 } 2614 #endif 2615 2616 /* 2617 * uvm_map_pageable_wire will release lock 2618 */ 2619 return uvm_map_pageable_wire(map, RBT_MIN(uvm_map_addr, &map->addr), 2620 NULL, map->min_offset, map->max_offset, 0); 2621 } 2622 2623 /* 2624 * Initialize map. 2625 * 2626 * Allocates sufficient entries to describe the free memory in the map. 2627 */ 2628 void 2629 uvm_map_setup(struct vm_map *map, pmap_t pmap, vaddr_t min, vaddr_t max, 2630 int flags) 2631 { 2632 int i; 2633 2634 KASSERT((min & (vaddr_t)PAGE_MASK) == 0); 2635 KASSERT((max & (vaddr_t)PAGE_MASK) == 0 || 2636 (max & (vaddr_t)PAGE_MASK) == (vaddr_t)PAGE_MASK); 2637 2638 /* 2639 * Update parameters. 2640 * 2641 * This code handles (vaddr_t)-1 and other page mask ending addresses 2642 * properly. 2643 * We lose the top page if the full virtual address space is used. 2644 */ 2645 if (max & (vaddr_t)PAGE_MASK) { 2646 max += 1; 2647 if (max == 0) /* overflow */ 2648 max -= PAGE_SIZE; 2649 } 2650 2651 RBT_INIT(uvm_map_addr, &map->addr); 2652 map->uaddr_exe = NULL; 2653 for (i = 0; i < nitems(map->uaddr_any); ++i) 2654 map->uaddr_any[i] = NULL; 2655 map->uaddr_brk_stack = NULL; 2656 2657 map->pmap = pmap; 2658 map->size = 0; 2659 map->ref_count = 0; 2660 map->min_offset = min; 2661 map->max_offset = max; 2662 map->b_start = map->b_end = 0; /* Empty brk() area by default. */ 2663 map->s_start = map->s_end = 0; /* Empty stack area by default. */ 2664 map->flags = flags; 2665 map->timestamp = 0; 2666 if (flags & VM_MAP_ISVMSPACE) 2667 rw_init_flags(&map->lock, "vmmaplk", RWL_DUPOK); 2668 else 2669 rw_init(&map->lock, "kmmaplk"); 2670 mtx_init(&map->mtx, IPL_VM); 2671 mtx_init(&map->flags_lock, IPL_VM); 2672 2673 /* Configure the allocators. */ 2674 if (flags & VM_MAP_ISVMSPACE) 2675 uvm_map_setup_md(map); 2676 else 2677 map->uaddr_any[3] = &uaddr_kbootstrap; 2678 2679 /* 2680 * Fill map entries. 2681 * We do not need to write-lock the map here because only the current 2682 * thread sees it right now. Initialize ref_count to 0 above to avoid 2683 * bogus triggering of lock-not-held assertions. 2684 */ 2685 uvm_map_setup_entries(map); 2686 uvm_tree_sanity(map, __FILE__, __LINE__); 2687 map->ref_count = 1; 2688 } 2689 2690 /* 2691 * Destroy the map. 2692 * 2693 * This is the inverse operation to uvm_map_setup. 2694 */ 2695 void 2696 uvm_map_teardown(struct vm_map *map) 2697 { 2698 struct uvm_map_deadq dead_entries; 2699 struct vm_map_entry *entry, *tmp; 2700 #ifdef VMMAP_DEBUG 2701 size_t numq, numt; 2702 #endif 2703 int i; 2704 2705 KERNEL_ASSERT_LOCKED(); 2706 KERNEL_UNLOCK(); 2707 KERNEL_ASSERT_UNLOCKED(); 2708 2709 KASSERT((map->flags & VM_MAP_INTRSAFE) == 0); 2710 2711 /* Remove address selectors. */ 2712 uvm_addr_destroy(map->uaddr_exe); 2713 map->uaddr_exe = NULL; 2714 for (i = 0; i < nitems(map->uaddr_any); i++) { 2715 uvm_addr_destroy(map->uaddr_any[i]); 2716 map->uaddr_any[i] = NULL; 2717 } 2718 uvm_addr_destroy(map->uaddr_brk_stack); 2719 map->uaddr_brk_stack = NULL; 2720 2721 /* 2722 * Remove entries. 2723 * 2724 * The following is based on graph breadth-first search. 2725 * 2726 * In color terms: 2727 * - the dead_entries set contains all nodes that are reachable 2728 * (i.e. both the black and the grey nodes) 2729 * - any entry not in dead_entries is white 2730 * - any entry that appears in dead_entries before entry, 2731 * is black, the rest is grey. 2732 * The set [entry, end] is also referred to as the wavefront. 2733 * 2734 * Since the tree is always a fully connected graph, the breadth-first 2735 * search guarantees that each vmmap_entry is visited exactly once. 2736 * The vm_map is broken down in linear time. 2737 */ 2738 TAILQ_INIT(&dead_entries); 2739 if ((entry = RBT_ROOT(uvm_map_addr, &map->addr)) != NULL) 2740 DEAD_ENTRY_PUSH(&dead_entries, entry); 2741 while (entry != NULL) { 2742 sched_pause(yield); 2743 uvm_unmap_kill_entry(map, entry); 2744 if ((tmp = RBT_LEFT(uvm_map_addr, entry)) != NULL) 2745 DEAD_ENTRY_PUSH(&dead_entries, tmp); 2746 if ((tmp = RBT_RIGHT(uvm_map_addr, entry)) != NULL) 2747 DEAD_ENTRY_PUSH(&dead_entries, tmp); 2748 /* Update wave-front. */ 2749 entry = TAILQ_NEXT(entry, dfree.deadq); 2750 } 2751 2752 #ifdef VMMAP_DEBUG 2753 numt = numq = 0; 2754 RBT_FOREACH(entry, uvm_map_addr, &map->addr) 2755 numt++; 2756 TAILQ_FOREACH(entry, &dead_entries, dfree.deadq) 2757 numq++; 2758 KASSERT(numt == numq); 2759 #endif 2760 uvm_unmap_detach(&dead_entries, UVM_PLA_WAITOK); 2761 2762 KERNEL_LOCK(); 2763 2764 pmap_destroy(map->pmap); 2765 map->pmap = NULL; 2766 } 2767 2768 /* 2769 * Populate map with free-memory entries. 2770 * 2771 * Map must be initialized and empty. 2772 */ 2773 void 2774 uvm_map_setup_entries(struct vm_map *map) 2775 { 2776 KDASSERT(RBT_EMPTY(uvm_map_addr, &map->addr)); 2777 2778 uvm_map_fix_space(map, NULL, map->min_offset, map->max_offset, 0); 2779 } 2780 2781 /* 2782 * Split entry at given address. 2783 * 2784 * orig: entry that is to be split. 2785 * next: a newly allocated map entry that is not linked. 2786 * split: address at which the split is done. 2787 */ 2788 void 2789 uvm_map_splitentry(struct vm_map *map, struct vm_map_entry *orig, 2790 struct vm_map_entry *next, vaddr_t split) 2791 { 2792 struct uvm_addr_state *free, *free_before; 2793 vsize_t adj; 2794 2795 if ((split & PAGE_MASK) != 0) { 2796 panic("uvm_map_splitentry: split address 0x%lx " 2797 "not on page boundary!", split); 2798 } 2799 KDASSERT(map != NULL && orig != NULL && next != NULL); 2800 uvm_tree_sanity(map, __FILE__, __LINE__); 2801 KASSERT(orig->start < split && VMMAP_FREE_END(orig) > split); 2802 2803 #ifdef VMMAP_DEBUG 2804 KDASSERT(RBT_FIND(uvm_map_addr, &map->addr, orig) == orig); 2805 KDASSERT(RBT_FIND(uvm_map_addr, &map->addr, next) != next); 2806 #endif /* VMMAP_DEBUG */ 2807 2808 /* 2809 * Free space will change, unlink from free space tree. 2810 */ 2811 free = uvm_map_uaddr_e(map, orig); 2812 uvm_mapent_free_remove(map, free, orig); 2813 2814 adj = split - orig->start; 2815 2816 uvm_mapent_copy(orig, next); 2817 if (split >= orig->end) { 2818 next->etype = 0; 2819 next->offset = 0; 2820 next->wired_count = 0; 2821 next->start = next->end = split; 2822 next->guard = 0; 2823 next->fspace = VMMAP_FREE_END(orig) - split; 2824 next->aref.ar_amap = NULL; 2825 next->aref.ar_pageoff = 0; 2826 orig->guard = MIN(orig->guard, split - orig->end); 2827 orig->fspace = split - VMMAP_FREE_START(orig); 2828 } else { 2829 orig->fspace = 0; 2830 orig->guard = 0; 2831 orig->end = next->start = split; 2832 2833 if (next->aref.ar_amap) { 2834 amap_splitref(&orig->aref, &next->aref, adj); 2835 } 2836 if (UVM_ET_ISSUBMAP(orig)) { 2837 uvm_map_reference(next->object.sub_map); 2838 next->offset += adj; 2839 } else if (UVM_ET_ISOBJ(orig)) { 2840 if (next->object.uvm_obj->pgops && 2841 next->object.uvm_obj->pgops->pgo_reference) { 2842 KERNEL_LOCK(); 2843 next->object.uvm_obj->pgops->pgo_reference( 2844 next->object.uvm_obj); 2845 KERNEL_UNLOCK(); 2846 } 2847 next->offset += adj; 2848 } 2849 } 2850 2851 /* 2852 * Link next into address tree. 2853 * Link orig and next into free-space tree. 2854 * 2855 * Don't insert 'next' into the addr tree until orig has been linked, 2856 * in case the free-list looks at adjecent entries in the addr tree 2857 * for its decisions. 2858 */ 2859 if (orig->fspace > 0) 2860 free_before = free; 2861 else 2862 free_before = uvm_map_uaddr_e(map, orig); 2863 uvm_mapent_free_insert(map, free_before, orig); 2864 uvm_mapent_addr_insert(map, next); 2865 uvm_mapent_free_insert(map, free, next); 2866 2867 uvm_tree_sanity(map, __FILE__, __LINE__); 2868 } 2869 2870 2871 #ifdef VMMAP_DEBUG 2872 2873 void 2874 uvm_tree_assert(struct vm_map *map, int test, char *test_str, 2875 char *file, int line) 2876 { 2877 char* map_special; 2878 2879 if (test) 2880 return; 2881 2882 if (map == kernel_map) 2883 map_special = " (kernel_map)"; 2884 else if (map == kmem_map) 2885 map_special = " (kmem_map)"; 2886 else 2887 map_special = ""; 2888 panic("uvm_tree_sanity %p%s (%s %d): %s", map, map_special, file, 2889 line, test_str); 2890 } 2891 2892 /* 2893 * Check that map is sane. 2894 */ 2895 void 2896 uvm_tree_sanity(struct vm_map *map, char *file, int line) 2897 { 2898 struct vm_map_entry *iter; 2899 vaddr_t addr; 2900 vaddr_t min, max, bound; /* Bounds checker. */ 2901 struct uvm_addr_state *free; 2902 2903 addr = vm_map_min(map); 2904 RBT_FOREACH(iter, uvm_map_addr, &map->addr) { 2905 /* 2906 * Valid start, end. 2907 * Catch overflow for end+fspace. 2908 */ 2909 UVM_ASSERT(map, iter->end >= iter->start, file, line); 2910 UVM_ASSERT(map, VMMAP_FREE_END(iter) >= iter->end, file, line); 2911 2912 /* May not be empty. */ 2913 UVM_ASSERT(map, iter->start < VMMAP_FREE_END(iter), 2914 file, line); 2915 2916 /* Addresses for entry must lie within map boundaries. */ 2917 UVM_ASSERT(map, iter->start >= vm_map_min(map) && 2918 VMMAP_FREE_END(iter) <= vm_map_max(map), file, line); 2919 2920 /* Tree may not have gaps. */ 2921 UVM_ASSERT(map, iter->start == addr, file, line); 2922 addr = VMMAP_FREE_END(iter); 2923 2924 /* 2925 * Free space may not cross boundaries, unless the same 2926 * free list is used on both sides of the border. 2927 */ 2928 min = VMMAP_FREE_START(iter); 2929 max = VMMAP_FREE_END(iter); 2930 2931 while (min < max && 2932 (bound = uvm_map_boundary(map, min, max)) != max) { 2933 UVM_ASSERT(map, 2934 uvm_map_uaddr(map, bound - 1) == 2935 uvm_map_uaddr(map, bound), 2936 file, line); 2937 min = bound; 2938 } 2939 2940 free = uvm_map_uaddr_e(map, iter); 2941 if (free) { 2942 UVM_ASSERT(map, (iter->etype & UVM_ET_FREEMAPPED) != 0, 2943 file, line); 2944 } else { 2945 UVM_ASSERT(map, (iter->etype & UVM_ET_FREEMAPPED) == 0, 2946 file, line); 2947 } 2948 } 2949 UVM_ASSERT(map, addr == vm_map_max(map), file, line); 2950 } 2951 2952 void 2953 uvm_tree_size_chk(struct vm_map *map, char *file, int line) 2954 { 2955 struct vm_map_entry *iter; 2956 vsize_t size; 2957 2958 size = 0; 2959 RBT_FOREACH(iter, uvm_map_addr, &map->addr) { 2960 if (!UVM_ET_ISHOLE(iter)) 2961 size += iter->end - iter->start; 2962 } 2963 2964 if (map->size != size) 2965 printf("map size = 0x%lx, should be 0x%lx\n", map->size, size); 2966 UVM_ASSERT(map, map->size == size, file, line); 2967 2968 vmspace_validate(map); 2969 } 2970 2971 /* 2972 * This function validates the statistics on vmspace. 2973 */ 2974 void 2975 vmspace_validate(struct vm_map *map) 2976 { 2977 struct vmspace *vm; 2978 struct vm_map_entry *iter; 2979 vaddr_t imin, imax; 2980 vaddr_t stack_begin, stack_end; /* Position of stack. */ 2981 vsize_t stack, heap; /* Measured sizes. */ 2982 2983 if (!(map->flags & VM_MAP_ISVMSPACE)) 2984 return; 2985 2986 vm = (struct vmspace *)map; 2987 stack_begin = MIN((vaddr_t)vm->vm_maxsaddr, (vaddr_t)vm->vm_minsaddr); 2988 stack_end = MAX((vaddr_t)vm->vm_maxsaddr, (vaddr_t)vm->vm_minsaddr); 2989 2990 stack = heap = 0; 2991 RBT_FOREACH(iter, uvm_map_addr, &map->addr) { 2992 imin = imax = iter->start; 2993 2994 if (UVM_ET_ISHOLE(iter) || iter->object.uvm_obj != NULL || 2995 iter->prot != PROT_NONE) 2996 continue; 2997 2998 /* 2999 * Update stack, heap. 3000 * Keep in mind that (theoretically) the entries of 3001 * userspace and stack may be joined. 3002 */ 3003 while (imin != iter->end) { 3004 /* 3005 * Set imax to the first boundary crossed between 3006 * imin and stack addresses. 3007 */ 3008 imax = iter->end; 3009 if (imin < stack_begin && imax > stack_begin) 3010 imax = stack_begin; 3011 else if (imin < stack_end && imax > stack_end) 3012 imax = stack_end; 3013 3014 if (imin >= stack_begin && imin < stack_end) 3015 stack += imax - imin; 3016 else 3017 heap += imax - imin; 3018 imin = imax; 3019 } 3020 } 3021 3022 heap >>= PAGE_SHIFT; 3023 if (heap != vm->vm_dused) { 3024 printf("vmspace stack range: 0x%lx-0x%lx\n", 3025 stack_begin, stack_end); 3026 panic("vmspace_validate: vmspace.vm_dused invalid, " 3027 "expected %ld pgs, got %ld pgs in map %p", 3028 heap, vm->vm_dused, 3029 map); 3030 } 3031 } 3032 3033 #endif /* VMMAP_DEBUG */ 3034 3035 /* 3036 * uvm_map_init: init mapping system at boot time. note that we allocate 3037 * and init the static pool of structs vm_map_entry for the kernel here. 3038 */ 3039 void 3040 uvm_map_init(void) 3041 { 3042 static struct vm_map_entry kernel_map_entry[MAX_KMAPENT]; 3043 int lcv; 3044 3045 /* now set up static pool of kernel map entries ... */ 3046 mtx_init(&uvm_kmapent_mtx, IPL_VM); 3047 SLIST_INIT(&uvm.kentry_free); 3048 for (lcv = 0 ; lcv < MAX_KMAPENT ; lcv++) { 3049 SLIST_INSERT_HEAD(&uvm.kentry_free, 3050 &kernel_map_entry[lcv], daddrs.addr_kentry); 3051 } 3052 3053 /* initialize the map-related pools. */ 3054 pool_init(&uvm_vmspace_pool, sizeof(struct vmspace), 0, 3055 IPL_NONE, PR_WAITOK, "vmsppl", NULL); 3056 pool_init(&uvm_map_entry_pool, sizeof(struct vm_map_entry), 0, 3057 IPL_VM, PR_WAITOK, "vmmpepl", NULL); 3058 pool_init(&uvm_map_entry_kmem_pool, sizeof(struct vm_map_entry), 0, 3059 IPL_VM, 0, "vmmpekpl", NULL); 3060 pool_sethiwat(&uvm_map_entry_pool, 8192); 3061 3062 uvm_addr_init(); 3063 } 3064 3065 #if defined(DDB) 3066 3067 /* 3068 * DDB hooks 3069 */ 3070 3071 /* 3072 * uvm_map_printit: actually prints the map 3073 */ 3074 void 3075 uvm_map_printit(struct vm_map *map, boolean_t full, 3076 int (*pr)(const char *, ...)) 3077 { 3078 struct vmspace *vm; 3079 struct vm_map_entry *entry; 3080 struct uvm_addr_state *free; 3081 int in_free, i; 3082 char buf[8]; 3083 3084 (*pr)("MAP %p: [0x%lx->0x%lx]\n", map, map->min_offset,map->max_offset); 3085 (*pr)("\tbrk() allocate range: 0x%lx-0x%lx\n", 3086 map->b_start, map->b_end); 3087 (*pr)("\tstack allocate range: 0x%lx-0x%lx\n", 3088 map->s_start, map->s_end); 3089 (*pr)("\tsz=%u, ref=%d, version=%u, flags=0x%x\n", 3090 map->size, map->ref_count, map->timestamp, 3091 map->flags); 3092 (*pr)("\tpmap=%p(resident=%d)\n", map->pmap, 3093 pmap_resident_count(map->pmap)); 3094 3095 /* struct vmspace handling. */ 3096 if (map->flags & VM_MAP_ISVMSPACE) { 3097 vm = (struct vmspace *)map; 3098 3099 (*pr)("\tvm_refcnt=%d vm_shm=%p vm_rssize=%u vm_swrss=%u\n", 3100 vm->vm_refcnt, vm->vm_shm, vm->vm_rssize, vm->vm_swrss); 3101 (*pr)("\tvm_tsize=%u vm_dsize=%u\n", 3102 vm->vm_tsize, vm->vm_dsize); 3103 (*pr)("\tvm_taddr=%p vm_daddr=%p\n", 3104 vm->vm_taddr, vm->vm_daddr); 3105 (*pr)("\tvm_maxsaddr=%p vm_minsaddr=%p\n", 3106 vm->vm_maxsaddr, vm->vm_minsaddr); 3107 } 3108 3109 if (!full) 3110 goto print_uaddr; 3111 RBT_FOREACH(entry, uvm_map_addr, &map->addr) { 3112 (*pr)(" - %p: 0x%lx->0x%lx: obj=%p/0x%llx, amap=%p/%d\n", 3113 entry, entry->start, entry->end, entry->object.uvm_obj, 3114 (long long)entry->offset, entry->aref.ar_amap, 3115 entry->aref.ar_pageoff); 3116 (*pr)("\tsubmap=%c, cow=%c, nc=%c, stack=%c, " 3117 "syscall=%c, prot(max)=%d/%d, inh=%d, " 3118 "wc=%d, adv=%d\n", 3119 (entry->etype & UVM_ET_SUBMAP) ? 'T' : 'F', 3120 (entry->etype & UVM_ET_COPYONWRITE) ? 'T' : 'F', 3121 (entry->etype & UVM_ET_NEEDSCOPY) ? 'T' : 'F', 3122 (entry->etype & UVM_ET_STACK) ? 'T' : 'F', 3123 (entry->etype & UVM_ET_SYSCALL) ? 'T' : 'F', 3124 entry->protection, entry->max_protection, 3125 entry->inheritance, entry->wired_count, entry->advice); 3126 3127 free = uvm_map_uaddr_e(map, entry); 3128 in_free = (free != NULL); 3129 (*pr)("\thole=%c, free=%c, guard=0x%lx, " 3130 "free=0x%lx-0x%lx\n", 3131 (entry->etype & UVM_ET_HOLE) ? 'T' : 'F', 3132 in_free ? 'T' : 'F', 3133 entry->guard, 3134 VMMAP_FREE_START(entry), VMMAP_FREE_END(entry)); 3135 (*pr)("\tfspace_augment=%lu\n", entry->fspace_augment); 3136 (*pr)("\tfreemapped=%c, uaddr=%p\n", 3137 (entry->etype & UVM_ET_FREEMAPPED) ? 'T' : 'F', free); 3138 if (free) { 3139 (*pr)("\t\t(0x%lx-0x%lx %s)\n", 3140 free->uaddr_minaddr, free->uaddr_maxaddr, 3141 free->uaddr_functions->uaddr_name); 3142 } 3143 } 3144 3145 print_uaddr: 3146 uvm_addr_print(map->uaddr_exe, "exe", full, pr); 3147 for (i = 0; i < nitems(map->uaddr_any); i++) { 3148 snprintf(&buf[0], sizeof(buf), "any[%d]", i); 3149 uvm_addr_print(map->uaddr_any[i], &buf[0], full, pr); 3150 } 3151 uvm_addr_print(map->uaddr_brk_stack, "brk/stack", full, pr); 3152 } 3153 3154 /* 3155 * uvm_object_printit: actually prints the object 3156 */ 3157 void 3158 uvm_object_printit(uobj, full, pr) 3159 struct uvm_object *uobj; 3160 boolean_t full; 3161 int (*pr)(const char *, ...); 3162 { 3163 struct vm_page *pg; 3164 int cnt = 0; 3165 3166 (*pr)("OBJECT %p: pgops=%p, npages=%d, ", 3167 uobj, uobj->pgops, uobj->uo_npages); 3168 if (UVM_OBJ_IS_KERN_OBJECT(uobj)) 3169 (*pr)("refs=<SYSTEM>\n"); 3170 else 3171 (*pr)("refs=%d\n", uobj->uo_refs); 3172 3173 if (!full) { 3174 return; 3175 } 3176 (*pr)(" PAGES <pg,offset>:\n "); 3177 RBT_FOREACH(pg, uvm_objtree, &uobj->memt) { 3178 (*pr)("<%p,0x%llx> ", pg, (long long)pg->offset); 3179 if ((cnt % 3) == 2) { 3180 (*pr)("\n "); 3181 } 3182 cnt++; 3183 } 3184 if ((cnt % 3) != 2) { 3185 (*pr)("\n"); 3186 } 3187 } 3188 3189 /* 3190 * uvm_page_printit: actually print the page 3191 */ 3192 static const char page_flagbits[] = 3193 "\20\1BUSY\2WANTED\3TABLED\4CLEAN\5CLEANCHK\6RELEASED\7FAKE\10RDONLY" 3194 "\11ZERO\12DEV\15PAGER1\21FREE\22INACTIVE\23ACTIVE\25ANON\26AOBJ" 3195 "\27ENCRYPT\31PMAP0\32PMAP1\33PMAP2\34PMAP3\35PMAP4\36PMAP5"; 3196 3197 void 3198 uvm_page_printit(pg, full, pr) 3199 struct vm_page *pg; 3200 boolean_t full; 3201 int (*pr)(const char *, ...); 3202 { 3203 struct vm_page *tpg; 3204 struct uvm_object *uobj; 3205 struct pglist *pgl; 3206 3207 (*pr)("PAGE %p:\n", pg); 3208 (*pr)(" flags=%b, vers=%d, wire_count=%d, pa=0x%llx\n", 3209 pg->pg_flags, page_flagbits, pg->pg_version, pg->wire_count, 3210 (long long)pg->phys_addr); 3211 (*pr)(" uobject=%p, uanon=%p, offset=0x%llx\n", 3212 pg->uobject, pg->uanon, (long long)pg->offset); 3213 #if defined(UVM_PAGE_TRKOWN) 3214 if (pg->pg_flags & PG_BUSY) 3215 (*pr)(" owning thread = %d, tag=%s", 3216 pg->owner, pg->owner_tag); 3217 else 3218 (*pr)(" page not busy, no owner"); 3219 #else 3220 (*pr)(" [page ownership tracking disabled]"); 3221 #endif 3222 (*pr)("\tvm_page_md %p\n", &pg->mdpage); 3223 3224 if (!full) 3225 return; 3226 3227 /* cross-verify object/anon */ 3228 if ((pg->pg_flags & PQ_FREE) == 0) { 3229 if (pg->pg_flags & PQ_ANON) { 3230 if (pg->uanon == NULL || pg->uanon->an_page != pg) 3231 (*pr)(" >>> ANON DOES NOT POINT HERE <<< (%p)\n", 3232 (pg->uanon) ? pg->uanon->an_page : NULL); 3233 else 3234 (*pr)(" anon backpointer is OK\n"); 3235 } else { 3236 uobj = pg->uobject; 3237 if (uobj) { 3238 (*pr)(" checking object list\n"); 3239 RBT_FOREACH(tpg, uvm_objtree, &uobj->memt) { 3240 if (tpg == pg) { 3241 break; 3242 } 3243 } 3244 if (tpg) 3245 (*pr)(" page found on object list\n"); 3246 else 3247 (*pr)(" >>> PAGE NOT FOUND " 3248 "ON OBJECT LIST! <<<\n"); 3249 } 3250 } 3251 } 3252 3253 /* cross-verify page queue */ 3254 if (pg->pg_flags & PQ_FREE) { 3255 if (uvm_pmr_isfree(pg)) 3256 (*pr)(" page found in uvm_pmemrange\n"); 3257 else 3258 (*pr)(" >>> page not found in uvm_pmemrange <<<\n"); 3259 pgl = NULL; 3260 } else if (pg->pg_flags & PQ_INACTIVE) { 3261 pgl = (pg->pg_flags & PQ_SWAPBACKED) ? 3262 &uvm.page_inactive_swp : &uvm.page_inactive_obj; 3263 } else if (pg->pg_flags & PQ_ACTIVE) { 3264 pgl = &uvm.page_active; 3265 } else { 3266 pgl = NULL; 3267 } 3268 3269 if (pgl) { 3270 (*pr)(" checking pageq list\n"); 3271 TAILQ_FOREACH(tpg, pgl, pageq) { 3272 if (tpg == pg) { 3273 break; 3274 } 3275 } 3276 if (tpg) 3277 (*pr)(" page found on pageq list\n"); 3278 else 3279 (*pr)(" >>> PAGE NOT FOUND ON PAGEQ LIST! <<<\n"); 3280 } 3281 } 3282 #endif 3283 3284 /* 3285 * uvm_map_protect: change map protection 3286 * 3287 * => set_max means set max_protection. 3288 * => map must be unlocked. 3289 */ 3290 int 3291 uvm_map_protect(struct vm_map *map, vaddr_t start, vaddr_t end, 3292 vm_prot_t new_prot, boolean_t set_max) 3293 { 3294 struct vm_map_entry *first, *iter; 3295 vm_prot_t old_prot; 3296 vm_prot_t mask; 3297 vsize_t dused; 3298 int error; 3299 3300 if (start > end) 3301 return EINVAL; 3302 start = MAX(start, map->min_offset); 3303 end = MIN(end, map->max_offset); 3304 if (start >= end) 3305 return 0; 3306 3307 dused = 0; 3308 error = 0; 3309 vm_map_lock(map); 3310 3311 /* 3312 * Set up first and last. 3313 * - first will contain first entry at or after start. 3314 */ 3315 first = uvm_map_entrybyaddr(&map->addr, start); 3316 KDASSERT(first != NULL); 3317 if (first->end <= start) 3318 first = RBT_NEXT(uvm_map_addr, first); 3319 3320 /* First, check for protection violations. */ 3321 for (iter = first; iter != NULL && iter->start < end; 3322 iter = RBT_NEXT(uvm_map_addr, iter)) { 3323 /* Treat memory holes as free space. */ 3324 if (iter->start == iter->end || UVM_ET_ISHOLE(iter)) 3325 continue; 3326 3327 old_prot = iter->protection; 3328 if (old_prot == PROT_NONE && new_prot != old_prot) { 3329 dused += uvmspace_dused( 3330 map, MAX(start, iter->start), MIN(end, iter->end)); 3331 } 3332 3333 if (UVM_ET_ISSUBMAP(iter)) { 3334 error = EINVAL; 3335 goto out; 3336 } 3337 if ((new_prot & iter->max_protection) != new_prot) { 3338 error = EACCES; 3339 goto out; 3340 } 3341 if (map == kernel_map && 3342 (new_prot & (PROT_WRITE | PROT_EXEC)) == (PROT_WRITE | PROT_EXEC)) 3343 panic("uvm_map_protect: kernel map W^X violation requested"); 3344 } 3345 3346 /* Check limits. */ 3347 if (dused > 0 && (map->flags & VM_MAP_ISVMSPACE)) { 3348 vsize_t limit = lim_cur(RLIMIT_DATA); 3349 dused = ptoa(dused); 3350 if (limit < dused || 3351 limit - dused < ptoa(((struct vmspace *)map)->vm_dused)) { 3352 error = ENOMEM; 3353 goto out; 3354 } 3355 } 3356 3357 /* Fix protections. */ 3358 for (iter = first; iter != NULL && iter->start < end; 3359 iter = RBT_NEXT(uvm_map_addr, iter)) { 3360 /* Treat memory holes as free space. */ 3361 if (iter->start == iter->end || UVM_ET_ISHOLE(iter)) 3362 continue; 3363 3364 old_prot = iter->protection; 3365 3366 /* 3367 * Skip adapting protection iff old and new protection 3368 * are equal. 3369 */ 3370 if (set_max) { 3371 if (old_prot == (new_prot & old_prot) && 3372 iter->max_protection == new_prot) 3373 continue; 3374 } else { 3375 if (old_prot == new_prot) 3376 continue; 3377 } 3378 3379 UVM_MAP_CLIP_START(map, iter, start); 3380 UVM_MAP_CLIP_END(map, iter, end); 3381 3382 if (set_max) { 3383 iter->max_protection = new_prot; 3384 iter->protection &= new_prot; 3385 } else 3386 iter->protection = new_prot; 3387 3388 /* 3389 * update physical map if necessary. worry about copy-on-write 3390 * here -- CHECK THIS XXX 3391 */ 3392 if (iter->protection != old_prot) { 3393 mask = UVM_ET_ISCOPYONWRITE(iter) ? 3394 ~PROT_WRITE : PROT_MASK; 3395 3396 /* XXX should only wserial++ if no split occurs */ 3397 if (iter->protection & PROT_WRITE) 3398 map->wserial++; 3399 3400 if (map->flags & VM_MAP_ISVMSPACE) { 3401 if (old_prot == PROT_NONE) { 3402 ((struct vmspace *)map)->vm_dused += 3403 uvmspace_dused(map, iter->start, 3404 iter->end); 3405 } 3406 if (iter->protection == PROT_NONE) { 3407 ((struct vmspace *)map)->vm_dused -= 3408 uvmspace_dused(map, iter->start, 3409 iter->end); 3410 } 3411 } 3412 3413 /* update pmap */ 3414 if ((iter->protection & mask) == PROT_NONE && 3415 VM_MAPENT_ISWIRED(iter)) { 3416 /* 3417 * TODO(ariane) this is stupid. wired_count 3418 * is 0 if not wired, otherwise anything 3419 * larger than 0 (incremented once each time 3420 * wire is called). 3421 * Mostly to be able to undo the damage on 3422 * failure. Not the actually be a wired 3423 * refcounter... 3424 * Originally: iter->wired_count--; 3425 * (don't we have to unwire this in the pmap 3426 * as well?) 3427 */ 3428 iter->wired_count = 0; 3429 } 3430 pmap_protect(map->pmap, iter->start, iter->end, 3431 iter->protection & mask); 3432 } 3433 3434 /* 3435 * If the map is configured to lock any future mappings, 3436 * wire this entry now if the old protection was PROT_NONE 3437 * and the new protection is not PROT_NONE. 3438 */ 3439 if ((map->flags & VM_MAP_WIREFUTURE) != 0 && 3440 VM_MAPENT_ISWIRED(iter) == 0 && 3441 old_prot == PROT_NONE && 3442 new_prot != PROT_NONE) { 3443 if (uvm_map_pageable(map, iter->start, iter->end, 3444 FALSE, UVM_LK_ENTER | UVM_LK_EXIT) != 0) { 3445 /* 3446 * If locking the entry fails, remember the 3447 * error if it's the first one. Note we 3448 * still continue setting the protection in 3449 * the map, but it will return the resource 3450 * storage condition regardless. 3451 * 3452 * XXX Ignore what the actual error is, 3453 * XXX just call it a resource shortage 3454 * XXX so that it doesn't get confused 3455 * XXX what uvm_map_protect() itself would 3456 * XXX normally return. 3457 */ 3458 error = ENOMEM; 3459 } 3460 } 3461 } 3462 pmap_update(map->pmap); 3463 3464 out: 3465 vm_map_unlock(map); 3466 return error; 3467 } 3468 3469 /* 3470 * uvmspace_alloc: allocate a vmspace structure. 3471 * 3472 * - structure includes vm_map and pmap 3473 * - XXX: no locking on this structure 3474 * - refcnt set to 1, rest must be init'd by caller 3475 */ 3476 struct vmspace * 3477 uvmspace_alloc(vaddr_t min, vaddr_t max, boolean_t pageable, 3478 boolean_t remove_holes) 3479 { 3480 struct vmspace *vm; 3481 3482 vm = pool_get(&uvm_vmspace_pool, PR_WAITOK | PR_ZERO); 3483 uvmspace_init(vm, NULL, min, max, pageable, remove_holes); 3484 return (vm); 3485 } 3486 3487 /* 3488 * uvmspace_init: initialize a vmspace structure. 3489 * 3490 * - XXX: no locking on this structure 3491 * - refcnt set to 1, rest must be init'd by caller 3492 */ 3493 void 3494 uvmspace_init(struct vmspace *vm, struct pmap *pmap, vaddr_t min, vaddr_t max, 3495 boolean_t pageable, boolean_t remove_holes) 3496 { 3497 KASSERT(pmap == NULL || pmap == pmap_kernel()); 3498 3499 if (pmap) 3500 pmap_reference(pmap); 3501 else 3502 pmap = pmap_create(); 3503 3504 uvm_map_setup(&vm->vm_map, pmap, min, max, 3505 (pageable ? VM_MAP_PAGEABLE : 0) | VM_MAP_ISVMSPACE); 3506 3507 vm->vm_refcnt = 1; 3508 3509 if (remove_holes) 3510 pmap_remove_holes(vm); 3511 } 3512 3513 /* 3514 * uvmspace_share: share a vmspace between two processes 3515 * 3516 * - used for vfork 3517 */ 3518 3519 struct vmspace * 3520 uvmspace_share(struct process *pr) 3521 { 3522 struct vmspace *vm = pr->ps_vmspace; 3523 3524 uvmspace_addref(vm); 3525 return vm; 3526 } 3527 3528 /* 3529 * uvmspace_exec: the process wants to exec a new program 3530 * 3531 * - XXX: no locking on vmspace 3532 */ 3533 3534 void 3535 uvmspace_exec(struct proc *p, vaddr_t start, vaddr_t end) 3536 { 3537 struct process *pr = p->p_p; 3538 struct vmspace *nvm, *ovm = pr->ps_vmspace; 3539 struct vm_map *map = &ovm->vm_map; 3540 struct uvm_map_deadq dead_entries; 3541 3542 KASSERT((start & (vaddr_t)PAGE_MASK) == 0); 3543 KASSERT((end & (vaddr_t)PAGE_MASK) == 0 || 3544 (end & (vaddr_t)PAGE_MASK) == (vaddr_t)PAGE_MASK); 3545 3546 pmap_unuse_final(p); /* before stack addresses go away */ 3547 TAILQ_INIT(&dead_entries); 3548 3549 /* see if more than one process is using this vmspace... */ 3550 if (ovm->vm_refcnt == 1) { 3551 /* 3552 * If pr is the only process using its vmspace then 3553 * we can safely recycle that vmspace for the program 3554 * that is being exec'd. 3555 */ 3556 3557 #ifdef SYSVSHM 3558 /* 3559 * SYSV SHM semantics require us to kill all segments on an exec 3560 */ 3561 if (ovm->vm_shm) 3562 shmexit(ovm); 3563 #endif 3564 3565 /* 3566 * POSIX 1003.1b -- "lock future mappings" is revoked 3567 * when a process execs another program image. 3568 */ 3569 vm_map_lock(map); 3570 vm_map_modflags(map, 0, VM_MAP_WIREFUTURE|VM_MAP_SYSCALL_ONCE); 3571 3572 /* 3573 * now unmap the old program 3574 * 3575 * Instead of attempting to keep the map valid, we simply 3576 * nuke all entries and ask uvm_map_setup to reinitialize 3577 * the map to the new boundaries. 3578 * 3579 * uvm_unmap_remove will actually nuke all entries for us 3580 * (as in, not replace them with free-memory entries). 3581 */ 3582 uvm_unmap_remove(map, map->min_offset, map->max_offset, 3583 &dead_entries, TRUE, FALSE); 3584 3585 KDASSERT(RBT_EMPTY(uvm_map_addr, &map->addr)); 3586 3587 /* Nuke statistics and boundaries. */ 3588 memset(&ovm->vm_startcopy, 0, 3589 (caddr_t) (ovm + 1) - (caddr_t) &ovm->vm_startcopy); 3590 3591 3592 if (end & (vaddr_t)PAGE_MASK) { 3593 end += 1; 3594 if (end == 0) /* overflow */ 3595 end -= PAGE_SIZE; 3596 } 3597 3598 /* Setup new boundaries and populate map with entries. */ 3599 map->min_offset = start; 3600 map->max_offset = end; 3601 uvm_map_setup_entries(map); 3602 vm_map_unlock(map); 3603 3604 /* but keep MMU holes unavailable */ 3605 pmap_remove_holes(ovm); 3606 } else { 3607 /* 3608 * pr's vmspace is being shared, so we can't reuse 3609 * it for pr since it is still being used for others. 3610 * allocate a new vmspace for pr 3611 */ 3612 nvm = uvmspace_alloc(start, end, 3613 (map->flags & VM_MAP_PAGEABLE) ? TRUE : FALSE, TRUE); 3614 3615 /* install new vmspace and drop our ref to the old one. */ 3616 pmap_deactivate(p); 3617 p->p_vmspace = pr->ps_vmspace = nvm; 3618 pmap_activate(p); 3619 3620 uvmspace_free(ovm); 3621 } 3622 3623 /* Release dead entries */ 3624 uvm_unmap_detach(&dead_entries, 0); 3625 } 3626 3627 /* 3628 * uvmspace_addref: add a reference to a vmspace. 3629 */ 3630 void 3631 uvmspace_addref(struct vmspace *vm) 3632 { 3633 KERNEL_ASSERT_LOCKED(); 3634 KASSERT(vm->vm_refcnt > 0); 3635 3636 vm->vm_refcnt++; 3637 } 3638 3639 /* 3640 * uvmspace_free: free a vmspace data structure 3641 */ 3642 void 3643 uvmspace_free(struct vmspace *vm) 3644 { 3645 KERNEL_ASSERT_LOCKED(); 3646 3647 if (--vm->vm_refcnt == 0) { 3648 /* 3649 * lock the map, to wait out all other references to it. delete 3650 * all of the mappings and pages they hold, then call the pmap 3651 * module to reclaim anything left. 3652 */ 3653 #ifdef SYSVSHM 3654 /* Get rid of any SYSV shared memory segments. */ 3655 if (vm->vm_shm != NULL) 3656 shmexit(vm); 3657 #endif 3658 3659 uvm_map_teardown(&vm->vm_map); 3660 pool_put(&uvm_vmspace_pool, vm); 3661 } 3662 } 3663 3664 /* 3665 * uvm_share: Map the address range [srcaddr, srcaddr + sz) in 3666 * srcmap to the address range [dstaddr, dstaddr + sz) in 3667 * dstmap. 3668 * 3669 * The whole address range in srcmap must be backed by an object 3670 * (no holes). 3671 * 3672 * If successful, the address ranges share memory and the destination 3673 * address range uses the protection flags in prot. 3674 * 3675 * This routine assumes that sz is a multiple of PAGE_SIZE and 3676 * that dstaddr and srcaddr are page-aligned. 3677 */ 3678 int 3679 uvm_share(struct vm_map *dstmap, vaddr_t dstaddr, vm_prot_t prot, 3680 struct vm_map *srcmap, vaddr_t srcaddr, vsize_t sz) 3681 { 3682 int ret = 0; 3683 vaddr_t unmap_end; 3684 vaddr_t dstva; 3685 vsize_t s_off, len, n = sz, remain; 3686 struct vm_map_entry *first = NULL, *last = NULL; 3687 struct vm_map_entry *src_entry, *psrc_entry = NULL; 3688 struct uvm_map_deadq dead; 3689 3690 if (srcaddr >= srcmap->max_offset || sz > srcmap->max_offset - srcaddr) 3691 return EINVAL; 3692 3693 TAILQ_INIT(&dead); 3694 vm_map_lock(dstmap); 3695 vm_map_lock_read(srcmap); 3696 3697 if (!uvm_map_isavail(dstmap, NULL, &first, &last, dstaddr, sz)) { 3698 ret = ENOMEM; 3699 goto exit_unlock; 3700 } 3701 if (!uvm_map_lookup_entry(srcmap, srcaddr, &src_entry)) { 3702 ret = EINVAL; 3703 goto exit_unlock; 3704 } 3705 3706 dstva = dstaddr; 3707 unmap_end = dstaddr; 3708 for (; src_entry != NULL; 3709 psrc_entry = src_entry, 3710 src_entry = RBT_NEXT(uvm_map_addr, src_entry)) { 3711 /* hole in address space, bail out */ 3712 if (psrc_entry != NULL && psrc_entry->end != src_entry->start) 3713 break; 3714 if (src_entry->start >= srcaddr + sz) 3715 break; 3716 3717 if (UVM_ET_ISSUBMAP(src_entry)) 3718 panic("uvm_share: encountered a submap (illegal)"); 3719 if (!UVM_ET_ISCOPYONWRITE(src_entry) && 3720 UVM_ET_ISNEEDSCOPY(src_entry)) 3721 panic("uvm_share: non-copy_on_write map entries " 3722 "marked needs_copy (illegal)"); 3723 3724 /* 3725 * srcaddr > map entry start? means we are in the middle of a 3726 * map, so we calculate the offset to use in the source map. 3727 */ 3728 if (srcaddr > src_entry->start) 3729 s_off = srcaddr - src_entry->start; 3730 else if (srcaddr == src_entry->start) 3731 s_off = 0; 3732 else 3733 panic("uvm_share: map entry start > srcaddr"); 3734 3735 remain = src_entry->end - src_entry->start - s_off; 3736 3737 /* Determine how many bytes to share in this pass */ 3738 if (n < remain) 3739 len = n; 3740 else 3741 len = remain; 3742 3743 if (uvm_mapent_share(dstmap, dstva, len, s_off, prot, prot, 3744 srcmap, src_entry, &dead) == NULL) 3745 break; 3746 3747 n -= len; 3748 dstva += len; 3749 srcaddr += len; 3750 unmap_end = dstva + len; 3751 if (n == 0) 3752 goto exit_unlock; 3753 } 3754 3755 ret = EINVAL; 3756 uvm_unmap_remove(dstmap, dstaddr, unmap_end, &dead, FALSE, TRUE); 3757 3758 exit_unlock: 3759 vm_map_unlock_read(srcmap); 3760 vm_map_unlock(dstmap); 3761 uvm_unmap_detach(&dead, 0); 3762 3763 return ret; 3764 } 3765 3766 /* 3767 * Clone map entry into other map. 3768 * 3769 * Mapping will be placed at dstaddr, for the same length. 3770 * Space must be available. 3771 * Reference counters are incremented. 3772 */ 3773 struct vm_map_entry * 3774 uvm_mapent_clone(struct vm_map *dstmap, vaddr_t dstaddr, vsize_t dstlen, 3775 vsize_t off, vm_prot_t prot, vm_prot_t maxprot, 3776 struct vm_map_entry *old_entry, struct uvm_map_deadq *dead, 3777 int mapent_flags, int amap_share_flags) 3778 { 3779 struct vm_map_entry *new_entry, *first, *last; 3780 3781 KDASSERT(!UVM_ET_ISSUBMAP(old_entry)); 3782 3783 /* Create new entry (linked in on creation). Fill in first, last. */ 3784 first = last = NULL; 3785 if (!uvm_map_isavail(dstmap, NULL, &first, &last, dstaddr, dstlen)) { 3786 panic("uvm_mapent_clone: no space in map for " 3787 "entry in empty map"); 3788 } 3789 new_entry = uvm_map_mkentry(dstmap, first, last, 3790 dstaddr, dstlen, mapent_flags, dead, NULL); 3791 if (new_entry == NULL) 3792 return NULL; 3793 /* old_entry -> new_entry */ 3794 new_entry->object = old_entry->object; 3795 new_entry->offset = old_entry->offset; 3796 new_entry->aref = old_entry->aref; 3797 new_entry->etype |= old_entry->etype & ~UVM_ET_FREEMAPPED; 3798 new_entry->protection = prot; 3799 new_entry->max_protection = maxprot; 3800 new_entry->inheritance = old_entry->inheritance; 3801 new_entry->advice = old_entry->advice; 3802 3803 /* gain reference to object backing the map (can't be a submap). */ 3804 if (new_entry->aref.ar_amap) { 3805 new_entry->aref.ar_pageoff += off >> PAGE_SHIFT; 3806 amap_ref(new_entry->aref.ar_amap, new_entry->aref.ar_pageoff, 3807 (new_entry->end - new_entry->start) >> PAGE_SHIFT, 3808 amap_share_flags); 3809 } 3810 3811 if (UVM_ET_ISOBJ(new_entry) && 3812 new_entry->object.uvm_obj->pgops->pgo_reference) { 3813 new_entry->offset += off; 3814 new_entry->object.uvm_obj->pgops->pgo_reference 3815 (new_entry->object.uvm_obj); 3816 } 3817 3818 return new_entry; 3819 } 3820 3821 struct vm_map_entry * 3822 uvm_mapent_share(struct vm_map *dstmap, vaddr_t dstaddr, vsize_t dstlen, 3823 vsize_t off, vm_prot_t prot, vm_prot_t maxprot, struct vm_map *old_map, 3824 struct vm_map_entry *old_entry, struct uvm_map_deadq *dead) 3825 { 3826 /* 3827 * If old_entry refers to a copy-on-write region that has not yet been 3828 * written to (needs_copy flag is set), then we need to allocate a new 3829 * amap for old_entry. 3830 * 3831 * If we do not do this, and the process owning old_entry does a copy-on 3832 * write later, old_entry and new_entry will refer to different memory 3833 * regions, and the memory between the processes is no longer shared. 3834 * 3835 * [in other words, we need to clear needs_copy] 3836 */ 3837 3838 if (UVM_ET_ISNEEDSCOPY(old_entry)) { 3839 /* get our own amap, clears needs_copy */ 3840 amap_copy(old_map, old_entry, M_WAITOK, FALSE, 0, 0); 3841 /* XXXCDC: WAITOK??? */ 3842 } 3843 3844 return uvm_mapent_clone(dstmap, dstaddr, dstlen, off, 3845 prot, maxprot, old_entry, dead, 0, AMAP_SHARED); 3846 } 3847 3848 /* 3849 * share the mapping: this means we want the old and 3850 * new entries to share amaps and backing objects. 3851 */ 3852 struct vm_map_entry * 3853 uvm_mapent_forkshared(struct vmspace *new_vm, struct vm_map *new_map, 3854 struct vm_map *old_map, 3855 struct vm_map_entry *old_entry, struct uvm_map_deadq *dead) 3856 { 3857 struct vm_map_entry *new_entry; 3858 3859 new_entry = uvm_mapent_share(new_map, old_entry->start, 3860 old_entry->end - old_entry->start, 0, old_entry->protection, 3861 old_entry->max_protection, old_map, old_entry, dead); 3862 3863 /* 3864 * pmap_copy the mappings: this routine is optional 3865 * but if it is there it will reduce the number of 3866 * page faults in the new proc. 3867 */ 3868 if (!UVM_ET_ISHOLE(new_entry)) 3869 pmap_copy(new_map->pmap, old_map->pmap, new_entry->start, 3870 (new_entry->end - new_entry->start), new_entry->start); 3871 3872 return (new_entry); 3873 } 3874 3875 /* 3876 * copy-on-write the mapping (using mmap's 3877 * MAP_PRIVATE semantics) 3878 * 3879 * allocate new_entry, adjust reference counts. 3880 * (note that new references are read-only). 3881 */ 3882 struct vm_map_entry * 3883 uvm_mapent_forkcopy(struct vmspace *new_vm, struct vm_map *new_map, 3884 struct vm_map *old_map, 3885 struct vm_map_entry *old_entry, struct uvm_map_deadq *dead) 3886 { 3887 struct vm_map_entry *new_entry; 3888 boolean_t protect_child; 3889 3890 new_entry = uvm_mapent_clone(new_map, old_entry->start, 3891 old_entry->end - old_entry->start, 0, old_entry->protection, 3892 old_entry->max_protection, old_entry, dead, 0, 0); 3893 3894 new_entry->etype |= 3895 (UVM_ET_COPYONWRITE|UVM_ET_NEEDSCOPY); 3896 3897 /* 3898 * the new entry will need an amap. it will either 3899 * need to be copied from the old entry or created 3900 * from scratch (if the old entry does not have an 3901 * amap). can we defer this process until later 3902 * (by setting "needs_copy") or do we need to copy 3903 * the amap now? 3904 * 3905 * we must copy the amap now if any of the following 3906 * conditions hold: 3907 * 1. the old entry has an amap and that amap is 3908 * being shared. this means that the old (parent) 3909 * process is sharing the amap with another 3910 * process. if we do not clear needs_copy here 3911 * we will end up in a situation where both the 3912 * parent and child process are referring to the 3913 * same amap with "needs_copy" set. if the 3914 * parent write-faults, the fault routine will 3915 * clear "needs_copy" in the parent by allocating 3916 * a new amap. this is wrong because the 3917 * parent is supposed to be sharing the old amap 3918 * and the new amap will break that. 3919 * 3920 * 2. if the old entry has an amap and a non-zero 3921 * wire count then we are going to have to call 3922 * amap_cow_now to avoid page faults in the 3923 * parent process. since amap_cow_now requires 3924 * "needs_copy" to be clear we might as well 3925 * clear it here as well. 3926 * 3927 */ 3928 if (old_entry->aref.ar_amap != NULL && 3929 ((amap_flags(old_entry->aref.ar_amap) & 3930 AMAP_SHARED) != 0 || 3931 VM_MAPENT_ISWIRED(old_entry))) { 3932 amap_copy(new_map, new_entry, M_WAITOK, FALSE, 3933 0, 0); 3934 /* XXXCDC: M_WAITOK ... ok? */ 3935 } 3936 3937 /* 3938 * if the parent's entry is wired down, then the 3939 * parent process does not want page faults on 3940 * access to that memory. this means that we 3941 * cannot do copy-on-write because we can't write 3942 * protect the old entry. in this case we 3943 * resolve all copy-on-write faults now, using 3944 * amap_cow_now. note that we have already 3945 * allocated any needed amap (above). 3946 */ 3947 if (VM_MAPENT_ISWIRED(old_entry)) { 3948 /* 3949 * resolve all copy-on-write faults now 3950 * (note that there is nothing to do if 3951 * the old mapping does not have an amap). 3952 * XXX: is it worthwhile to bother with 3953 * pmap_copy in this case? 3954 */ 3955 if (old_entry->aref.ar_amap) 3956 amap_cow_now(new_map, new_entry); 3957 } else { 3958 if (old_entry->aref.ar_amap) { 3959 /* 3960 * setup mappings to trigger copy-on-write faults 3961 * we must write-protect the parent if it has 3962 * an amap and it is not already "needs_copy"... 3963 * if it is already "needs_copy" then the parent 3964 * has already been write-protected by a previous 3965 * fork operation. 3966 * 3967 * if we do not write-protect the parent, then 3968 * we must be sure to write-protect the child 3969 * after the pmap_copy() operation. 3970 * 3971 * XXX: pmap_copy should have some way of telling 3972 * us that it didn't do anything so we can avoid 3973 * calling pmap_protect needlessly. 3974 */ 3975 if (!UVM_ET_ISNEEDSCOPY(old_entry)) { 3976 if (old_entry->max_protection & PROT_WRITE) { 3977 pmap_protect(old_map->pmap, 3978 old_entry->start, 3979 old_entry->end, 3980 old_entry->protection & 3981 ~PROT_WRITE); 3982 pmap_update(old_map->pmap); 3983 } 3984 old_entry->etype |= UVM_ET_NEEDSCOPY; 3985 } 3986 3987 /* parent must now be write-protected */ 3988 protect_child = FALSE; 3989 } else { 3990 /* 3991 * we only need to protect the child if the 3992 * parent has write access. 3993 */ 3994 if (old_entry->max_protection & PROT_WRITE) 3995 protect_child = TRUE; 3996 else 3997 protect_child = FALSE; 3998 } 3999 /* 4000 * copy the mappings 4001 * XXX: need a way to tell if this does anything 4002 */ 4003 if (!UVM_ET_ISHOLE(new_entry)) 4004 pmap_copy(new_map->pmap, old_map->pmap, 4005 new_entry->start, 4006 (old_entry->end - old_entry->start), 4007 old_entry->start); 4008 4009 /* protect the child's mappings if necessary */ 4010 if (protect_child) { 4011 pmap_protect(new_map->pmap, new_entry->start, 4012 new_entry->end, 4013 new_entry->protection & 4014 ~PROT_WRITE); 4015 } 4016 } 4017 4018 return (new_entry); 4019 } 4020 4021 /* 4022 * zero the mapping: the new entry will be zero initialized 4023 */ 4024 struct vm_map_entry * 4025 uvm_mapent_forkzero(struct vmspace *new_vm, struct vm_map *new_map, 4026 struct vm_map *old_map, 4027 struct vm_map_entry *old_entry, struct uvm_map_deadq *dead) 4028 { 4029 struct vm_map_entry *new_entry; 4030 4031 new_entry = uvm_mapent_clone(new_map, old_entry->start, 4032 old_entry->end - old_entry->start, 0, old_entry->protection, 4033 old_entry->max_protection, old_entry, dead, 0, 0); 4034 4035 new_entry->etype |= 4036 (UVM_ET_COPYONWRITE|UVM_ET_NEEDSCOPY); 4037 4038 if (new_entry->aref.ar_amap) { 4039 amap_unref(new_entry->aref.ar_amap, new_entry->aref.ar_pageoff, 4040 atop(new_entry->end - new_entry->start), 0); 4041 new_entry->aref.ar_amap = NULL; 4042 new_entry->aref.ar_pageoff = 0; 4043 } 4044 4045 if (UVM_ET_ISOBJ(new_entry)) { 4046 if (new_entry->object.uvm_obj->pgops->pgo_detach) 4047 new_entry->object.uvm_obj->pgops->pgo_detach( 4048 new_entry->object.uvm_obj); 4049 new_entry->object.uvm_obj = NULL; 4050 new_entry->etype &= ~UVM_ET_OBJ; 4051 } 4052 4053 return (new_entry); 4054 } 4055 4056 /* 4057 * uvmspace_fork: fork a process' main map 4058 * 4059 * => create a new vmspace for child process from parent. 4060 * => parent's map must not be locked. 4061 */ 4062 struct vmspace * 4063 uvmspace_fork(struct process *pr) 4064 { 4065 struct vmspace *vm1 = pr->ps_vmspace; 4066 struct vmspace *vm2; 4067 struct vm_map *old_map = &vm1->vm_map; 4068 struct vm_map *new_map; 4069 struct vm_map_entry *old_entry, *new_entry; 4070 struct uvm_map_deadq dead; 4071 4072 vm_map_lock(old_map); 4073 4074 vm2 = uvmspace_alloc(old_map->min_offset, old_map->max_offset, 4075 (old_map->flags & VM_MAP_PAGEABLE) ? TRUE : FALSE, FALSE); 4076 memcpy(&vm2->vm_startcopy, &vm1->vm_startcopy, 4077 (caddr_t) (vm1 + 1) - (caddr_t) &vm1->vm_startcopy); 4078 vm2->vm_dused = 0; /* Statistic managed by us. */ 4079 new_map = &vm2->vm_map; 4080 vm_map_lock(new_map); 4081 4082 /* go entry-by-entry */ 4083 TAILQ_INIT(&dead); 4084 RBT_FOREACH(old_entry, uvm_map_addr, &old_map->addr) { 4085 if (old_entry->start == old_entry->end) 4086 continue; 4087 4088 /* first, some sanity checks on the old entry */ 4089 if (UVM_ET_ISSUBMAP(old_entry)) { 4090 panic("fork: encountered a submap during fork " 4091 "(illegal)"); 4092 } 4093 4094 if (!UVM_ET_ISCOPYONWRITE(old_entry) && 4095 UVM_ET_ISNEEDSCOPY(old_entry)) { 4096 panic("fork: non-copy_on_write map entry marked " 4097 "needs_copy (illegal)"); 4098 } 4099 4100 /* Apply inheritance. */ 4101 switch (old_entry->inheritance) { 4102 case MAP_INHERIT_SHARE: 4103 new_entry = uvm_mapent_forkshared(vm2, new_map, 4104 old_map, old_entry, &dead); 4105 break; 4106 case MAP_INHERIT_COPY: 4107 new_entry = uvm_mapent_forkcopy(vm2, new_map, 4108 old_map, old_entry, &dead); 4109 break; 4110 case MAP_INHERIT_ZERO: 4111 new_entry = uvm_mapent_forkzero(vm2, new_map, 4112 old_map, old_entry, &dead); 4113 break; 4114 default: 4115 continue; 4116 } 4117 4118 /* Update process statistics. */ 4119 if (!UVM_ET_ISHOLE(new_entry)) 4120 new_map->size += new_entry->end - new_entry->start; 4121 if (!UVM_ET_ISOBJ(new_entry) && !UVM_ET_ISHOLE(new_entry) && 4122 new_entry->protection != PROT_NONE) { 4123 vm2->vm_dused += uvmspace_dused( 4124 new_map, new_entry->start, new_entry->end); 4125 } 4126 } 4127 4128 vm_map_unlock(old_map); 4129 vm_map_unlock(new_map); 4130 4131 /* 4132 * This can actually happen, if multiple entries described a 4133 * space in which an entry was inherited. 4134 */ 4135 uvm_unmap_detach(&dead, 0); 4136 4137 #ifdef SYSVSHM 4138 if (vm1->vm_shm) 4139 shmfork(vm1, vm2); 4140 #endif 4141 4142 return vm2; 4143 } 4144 4145 /* 4146 * uvm_map_hint: return the beginning of the best area suitable for 4147 * creating a new mapping with "prot" protection. 4148 */ 4149 vaddr_t 4150 uvm_map_hint(struct vmspace *vm, vm_prot_t prot, vaddr_t minaddr, 4151 vaddr_t maxaddr) 4152 { 4153 vaddr_t addr; 4154 vaddr_t spacing; 4155 4156 #ifdef __i386__ 4157 /* 4158 * If executable skip first two pages, otherwise start 4159 * after data + heap region. 4160 */ 4161 if ((prot & PROT_EXEC) != 0 && 4162 (vaddr_t)vm->vm_daddr >= I386_MAX_EXE_ADDR) { 4163 addr = (PAGE_SIZE*2) + 4164 (arc4random() & (I386_MAX_EXE_ADDR / 2 - 1)); 4165 return (round_page(addr)); 4166 } 4167 #endif 4168 4169 #if defined (__LP64__) 4170 spacing = MIN(4UL * 1024 * 1024 * 1024, MAXDSIZ) - 1; 4171 #else 4172 spacing = MIN(1 * 1024 * 1024 * 1024, MAXDSIZ) - 1; 4173 #endif 4174 4175 /* 4176 * Start malloc/mmap after the brk. 4177 */ 4178 addr = (vaddr_t)vm->vm_daddr + BRKSIZ; 4179 addr = MAX(addr, minaddr); 4180 4181 if (addr < maxaddr) { 4182 while (spacing > maxaddr - addr) 4183 spacing >>= 1; 4184 } 4185 addr += arc4random() & spacing; 4186 return (round_page(addr)); 4187 } 4188 4189 /* 4190 * uvm_map_submap: punch down part of a map into a submap 4191 * 4192 * => only the kernel_map is allowed to be submapped 4193 * => the purpose of submapping is to break up the locking granularity 4194 * of a larger map 4195 * => the range specified must have been mapped previously with a uvm_map() 4196 * call [with uobj==NULL] to create a blank map entry in the main map. 4197 * [And it had better still be blank!] 4198 * => maps which contain submaps should never be copied or forked. 4199 * => to remove a submap, use uvm_unmap() on the main map 4200 * and then uvm_map_deallocate() the submap. 4201 * => main map must be unlocked. 4202 * => submap must have been init'd and have a zero reference count. 4203 * [need not be locked as we don't actually reference it] 4204 */ 4205 int 4206 uvm_map_submap(struct vm_map *map, vaddr_t start, vaddr_t end, 4207 struct vm_map *submap) 4208 { 4209 struct vm_map_entry *entry; 4210 int result; 4211 4212 if (start > map->max_offset || end > map->max_offset || 4213 start < map->min_offset || end < map->min_offset) 4214 return EINVAL; 4215 4216 vm_map_lock(map); 4217 4218 if (uvm_map_lookup_entry(map, start, &entry)) { 4219 UVM_MAP_CLIP_START(map, entry, start); 4220 UVM_MAP_CLIP_END(map, entry, end); 4221 } else 4222 entry = NULL; 4223 4224 if (entry != NULL && 4225 entry->start == start && entry->end == end && 4226 entry->object.uvm_obj == NULL && entry->aref.ar_amap == NULL && 4227 !UVM_ET_ISCOPYONWRITE(entry) && !UVM_ET_ISNEEDSCOPY(entry)) { 4228 entry->etype |= UVM_ET_SUBMAP; 4229 entry->object.sub_map = submap; 4230 entry->offset = 0; 4231 uvm_map_reference(submap); 4232 result = 0; 4233 } else 4234 result = EINVAL; 4235 4236 vm_map_unlock(map); 4237 return(result); 4238 } 4239 4240 /* 4241 * uvm_map_checkprot: check protection in map 4242 * 4243 * => must allow specific protection in a fully allocated region. 4244 * => map mut be read or write locked by caller. 4245 */ 4246 boolean_t 4247 uvm_map_checkprot(struct vm_map *map, vaddr_t start, vaddr_t end, 4248 vm_prot_t protection) 4249 { 4250 struct vm_map_entry *entry; 4251 4252 if (start < map->min_offset || end > map->max_offset || start > end) 4253 return FALSE; 4254 if (start == end) 4255 return TRUE; 4256 4257 /* 4258 * Iterate entries. 4259 */ 4260 for (entry = uvm_map_entrybyaddr(&map->addr, start); 4261 entry != NULL && entry->start < end; 4262 entry = RBT_NEXT(uvm_map_addr, entry)) { 4263 /* Fail if a hole is found. */ 4264 if (UVM_ET_ISHOLE(entry) || 4265 (entry->end < end && entry->end != VMMAP_FREE_END(entry))) 4266 return FALSE; 4267 4268 /* Check protection. */ 4269 if ((entry->protection & protection) != protection) 4270 return FALSE; 4271 } 4272 return TRUE; 4273 } 4274 4275 /* 4276 * uvm_map_create: create map 4277 */ 4278 vm_map_t 4279 uvm_map_create(pmap_t pmap, vaddr_t min, vaddr_t max, int flags) 4280 { 4281 vm_map_t map; 4282 4283 map = malloc(sizeof *map, M_VMMAP, M_WAITOK); 4284 uvm_map_setup(map, pmap, min, max, flags); 4285 return (map); 4286 } 4287 4288 /* 4289 * uvm_map_deallocate: drop reference to a map 4290 * 4291 * => caller must not lock map 4292 * => we will zap map if ref count goes to zero 4293 */ 4294 void 4295 uvm_map_deallocate(vm_map_t map) 4296 { 4297 int c; 4298 struct uvm_map_deadq dead; 4299 4300 c = --map->ref_count; 4301 if (c > 0) { 4302 return; 4303 } 4304 4305 /* 4306 * all references gone. unmap and free. 4307 * 4308 * No lock required: we are only one to access this map. 4309 */ 4310 TAILQ_INIT(&dead); 4311 uvm_tree_sanity(map, __FILE__, __LINE__); 4312 uvm_unmap_remove(map, map->min_offset, map->max_offset, &dead, 4313 TRUE, FALSE); 4314 pmap_destroy(map->pmap); 4315 KASSERT(RBT_EMPTY(uvm_map_addr, &map->addr)); 4316 free(map, M_VMMAP, sizeof *map); 4317 4318 uvm_unmap_detach(&dead, 0); 4319 } 4320 4321 /* 4322 * uvm_map_inherit: set inheritance code for range of addrs in map. 4323 * 4324 * => map must be unlocked 4325 * => note that the inherit code is used during a "fork". see fork 4326 * code for details. 4327 */ 4328 int 4329 uvm_map_inherit(struct vm_map *map, vaddr_t start, vaddr_t end, 4330 vm_inherit_t new_inheritance) 4331 { 4332 struct vm_map_entry *entry; 4333 4334 switch (new_inheritance) { 4335 case MAP_INHERIT_NONE: 4336 case MAP_INHERIT_COPY: 4337 case MAP_INHERIT_SHARE: 4338 case MAP_INHERIT_ZERO: 4339 break; 4340 default: 4341 return (EINVAL); 4342 } 4343 4344 if (start > end) 4345 return EINVAL; 4346 start = MAX(start, map->min_offset); 4347 end = MIN(end, map->max_offset); 4348 if (start >= end) 4349 return 0; 4350 4351 vm_map_lock(map); 4352 4353 entry = uvm_map_entrybyaddr(&map->addr, start); 4354 if (entry->end > start) 4355 UVM_MAP_CLIP_START(map, entry, start); 4356 else 4357 entry = RBT_NEXT(uvm_map_addr, entry); 4358 4359 while (entry != NULL && entry->start < end) { 4360 UVM_MAP_CLIP_END(map, entry, end); 4361 entry->inheritance = new_inheritance; 4362 entry = RBT_NEXT(uvm_map_addr, entry); 4363 } 4364 4365 vm_map_unlock(map); 4366 return (0); 4367 } 4368 4369 /* 4370 * uvm_map_syscall: permit system calls for range of addrs in map. 4371 * 4372 * => map must be unlocked 4373 */ 4374 int 4375 uvm_map_syscall(struct vm_map *map, vaddr_t start, vaddr_t end) 4376 { 4377 struct vm_map_entry *entry; 4378 4379 if (start > end) 4380 return EINVAL; 4381 start = MAX(start, map->min_offset); 4382 end = MIN(end, map->max_offset); 4383 if (start >= end) 4384 return 0; 4385 if (map->flags & VM_MAP_SYSCALL_ONCE) /* only allowed once */ 4386 return (EPERM); 4387 4388 vm_map_lock(map); 4389 4390 entry = uvm_map_entrybyaddr(&map->addr, start); 4391 if (entry->end > start) 4392 UVM_MAP_CLIP_START(map, entry, start); 4393 else 4394 entry = RBT_NEXT(uvm_map_addr, entry); 4395 4396 while (entry != NULL && entry->start < end) { 4397 UVM_MAP_CLIP_END(map, entry, end); 4398 entry->etype |= UVM_ET_SYSCALL; 4399 entry = RBT_NEXT(uvm_map_addr, entry); 4400 } 4401 4402 map->wserial++; 4403 map->flags |= VM_MAP_SYSCALL_ONCE; 4404 vm_map_unlock(map); 4405 return (0); 4406 } 4407 4408 /* 4409 * uvm_map_advice: set advice code for range of addrs in map. 4410 * 4411 * => map must be unlocked 4412 */ 4413 int 4414 uvm_map_advice(struct vm_map *map, vaddr_t start, vaddr_t end, int new_advice) 4415 { 4416 struct vm_map_entry *entry; 4417 4418 switch (new_advice) { 4419 case MADV_NORMAL: 4420 case MADV_RANDOM: 4421 case MADV_SEQUENTIAL: 4422 break; 4423 default: 4424 return (EINVAL); 4425 } 4426 4427 if (start > end) 4428 return EINVAL; 4429 start = MAX(start, map->min_offset); 4430 end = MIN(end, map->max_offset); 4431 if (start >= end) 4432 return 0; 4433 4434 vm_map_lock(map); 4435 4436 entry = uvm_map_entrybyaddr(&map->addr, start); 4437 if (entry != NULL && entry->end > start) 4438 UVM_MAP_CLIP_START(map, entry, start); 4439 else if (entry!= NULL) 4440 entry = RBT_NEXT(uvm_map_addr, entry); 4441 4442 /* 4443 * XXXJRT: disallow holes? 4444 */ 4445 while (entry != NULL && entry->start < end) { 4446 UVM_MAP_CLIP_END(map, entry, end); 4447 entry->advice = new_advice; 4448 entry = RBT_NEXT(uvm_map_addr, entry); 4449 } 4450 4451 vm_map_unlock(map); 4452 return (0); 4453 } 4454 4455 /* 4456 * uvm_map_extract: extract a mapping from a map and put it somewhere 4457 * in the kernel_map, setting protection to max_prot. 4458 * 4459 * => map should be unlocked (we will write lock it and kernel_map) 4460 * => returns 0 on success, error code otherwise 4461 * => start must be page aligned 4462 * => len must be page sized 4463 * => flags: 4464 * UVM_EXTRACT_FIXPROT: set prot to maxprot as we go 4465 * Mappings are QREF's. 4466 */ 4467 int 4468 uvm_map_extract(struct vm_map *srcmap, vaddr_t start, vsize_t len, 4469 vaddr_t *dstaddrp, int flags) 4470 { 4471 struct uvm_map_deadq dead; 4472 struct vm_map_entry *first, *entry, *newentry, *tmp1, *tmp2; 4473 vaddr_t dstaddr; 4474 vaddr_t end; 4475 vaddr_t cp_start; 4476 vsize_t cp_len, cp_off; 4477 int error; 4478 4479 TAILQ_INIT(&dead); 4480 end = start + len; 4481 4482 /* 4483 * Sanity check on the parameters. 4484 * Also, since the mapping may not contain gaps, error out if the 4485 * mapped area is not in source map. 4486 */ 4487 if ((start & (vaddr_t)PAGE_MASK) != 0 || 4488 (end & (vaddr_t)PAGE_MASK) != 0 || end < start) 4489 return EINVAL; 4490 if (start < srcmap->min_offset || end > srcmap->max_offset) 4491 return EINVAL; 4492 4493 /* Initialize dead entries. Handle len == 0 case. */ 4494 if (len == 0) 4495 return 0; 4496 4497 /* Acquire lock on srcmap. */ 4498 vm_map_lock(srcmap); 4499 4500 /* Lock srcmap, lookup first and last entry in <start,len>. */ 4501 first = uvm_map_entrybyaddr(&srcmap->addr, start); 4502 4503 /* Check that the range is contiguous. */ 4504 for (entry = first; entry != NULL && entry->end < end; 4505 entry = RBT_NEXT(uvm_map_addr, entry)) { 4506 if (VMMAP_FREE_END(entry) != entry->end || 4507 UVM_ET_ISHOLE(entry)) { 4508 error = EINVAL; 4509 goto fail; 4510 } 4511 } 4512 if (entry == NULL || UVM_ET_ISHOLE(entry)) { 4513 error = EINVAL; 4514 goto fail; 4515 } 4516 4517 /* 4518 * Handle need-copy flag. 4519 */ 4520 for (entry = first; entry != NULL && entry->start < end; 4521 entry = RBT_NEXT(uvm_map_addr, entry)) { 4522 if (UVM_ET_ISNEEDSCOPY(entry)) 4523 amap_copy(srcmap, entry, M_NOWAIT, 4524 UVM_ET_ISSTACK(entry) ? FALSE : TRUE, start, end); 4525 if (UVM_ET_ISNEEDSCOPY(entry)) { 4526 /* 4527 * amap_copy failure 4528 */ 4529 error = ENOMEM; 4530 goto fail; 4531 } 4532 } 4533 4534 /* Lock destination map (kernel_map). */ 4535 vm_map_lock(kernel_map); 4536 4537 if (uvm_map_findspace(kernel_map, &tmp1, &tmp2, &dstaddr, len, 4538 MAX(PAGE_SIZE, PMAP_PREFER_ALIGN()), PMAP_PREFER_OFFSET(start), 4539 PROT_NONE, 0) != 0) { 4540 error = ENOMEM; 4541 goto fail2; 4542 } 4543 *dstaddrp = dstaddr; 4544 4545 /* 4546 * We now have srcmap and kernel_map locked. 4547 * dstaddr contains the destination offset in dstmap. 4548 */ 4549 /* step 1: start looping through map entries, performing extraction. */ 4550 for (entry = first; entry != NULL && entry->start < end; 4551 entry = RBT_NEXT(uvm_map_addr, entry)) { 4552 KDASSERT(!UVM_ET_ISNEEDSCOPY(entry)); 4553 if (UVM_ET_ISHOLE(entry)) 4554 continue; 4555 4556 /* Calculate uvm_mapent_clone parameters. */ 4557 cp_start = entry->start; 4558 if (cp_start < start) { 4559 cp_off = start - cp_start; 4560 cp_start = start; 4561 } else 4562 cp_off = 0; 4563 cp_len = MIN(entry->end, end) - cp_start; 4564 4565 newentry = uvm_mapent_clone(kernel_map, 4566 cp_start - start + dstaddr, cp_len, cp_off, 4567 entry->protection, entry->max_protection, 4568 entry, &dead, flags, AMAP_SHARED | AMAP_REFALL); 4569 if (newentry == NULL) { 4570 error = ENOMEM; 4571 goto fail2_unmap; 4572 } 4573 kernel_map->size += cp_len; 4574 if (flags & UVM_EXTRACT_FIXPROT) 4575 newentry->protection = newentry->max_protection; 4576 4577 /* 4578 * Step 2: perform pmap copy. 4579 * (Doing this in the loop saves one RB traversal.) 4580 */ 4581 pmap_copy(kernel_map->pmap, srcmap->pmap, 4582 cp_start - start + dstaddr, cp_len, cp_start); 4583 } 4584 pmap_update(kernel_map->pmap); 4585 4586 error = 0; 4587 4588 /* Unmap copied entries on failure. */ 4589 fail2_unmap: 4590 if (error) { 4591 uvm_unmap_remove(kernel_map, dstaddr, dstaddr + len, &dead, 4592 FALSE, TRUE); 4593 } 4594 4595 /* Release maps, release dead entries. */ 4596 fail2: 4597 vm_map_unlock(kernel_map); 4598 4599 fail: 4600 vm_map_unlock(srcmap); 4601 4602 uvm_unmap_detach(&dead, 0); 4603 4604 return error; 4605 } 4606 4607 /* 4608 * uvm_map_clean: clean out a map range 4609 * 4610 * => valid flags: 4611 * if (flags & PGO_CLEANIT): dirty pages are cleaned first 4612 * if (flags & PGO_SYNCIO): dirty pages are written synchronously 4613 * if (flags & PGO_DEACTIVATE): any cached pages are deactivated after clean 4614 * if (flags & PGO_FREE): any cached pages are freed after clean 4615 * => returns an error if any part of the specified range isn't mapped 4616 * => never a need to flush amap layer since the anonymous memory has 4617 * no permanent home, but may deactivate pages there 4618 * => called from sys_msync() and sys_madvise() 4619 * => caller must not write-lock map (read OK). 4620 * => we may sleep while cleaning if SYNCIO [with map read-locked] 4621 */ 4622 4623 int 4624 uvm_map_clean(struct vm_map *map, vaddr_t start, vaddr_t end, int flags) 4625 { 4626 struct vm_map_entry *first, *entry; 4627 struct vm_amap *amap; 4628 struct vm_anon *anon; 4629 struct vm_page *pg; 4630 struct uvm_object *uobj; 4631 vaddr_t cp_start, cp_end; 4632 int refs; 4633 int error; 4634 boolean_t rv; 4635 4636 KASSERT((flags & (PGO_FREE|PGO_DEACTIVATE)) != 4637 (PGO_FREE|PGO_DEACTIVATE)); 4638 4639 if (start > end || start < map->min_offset || end > map->max_offset) 4640 return EINVAL; 4641 4642 vm_map_lock_read(map); 4643 first = uvm_map_entrybyaddr(&map->addr, start); 4644 4645 /* Make a first pass to check for holes. */ 4646 for (entry = first; entry != NULL && entry->start < end; 4647 entry = RBT_NEXT(uvm_map_addr, entry)) { 4648 if (UVM_ET_ISSUBMAP(entry)) { 4649 vm_map_unlock_read(map); 4650 return EINVAL; 4651 } 4652 if (UVM_ET_ISSUBMAP(entry) || 4653 UVM_ET_ISHOLE(entry) || 4654 (entry->end < end && 4655 VMMAP_FREE_END(entry) != entry->end)) { 4656 vm_map_unlock_read(map); 4657 return EFAULT; 4658 } 4659 } 4660 4661 error = 0; 4662 for (entry = first; entry != NULL && entry->start < end; 4663 entry = RBT_NEXT(uvm_map_addr, entry)) { 4664 amap = entry->aref.ar_amap; /* top layer */ 4665 if (UVM_ET_ISOBJ(entry)) 4666 uobj = entry->object.uvm_obj; 4667 else 4668 uobj = NULL; 4669 4670 /* 4671 * No amap cleaning necessary if: 4672 * - there's no amap 4673 * - we're not deactivating or freeing pages. 4674 */ 4675 if (amap == NULL || (flags & (PGO_DEACTIVATE|PGO_FREE)) == 0) 4676 goto flush_object; 4677 4678 cp_start = MAX(entry->start, start); 4679 cp_end = MIN(entry->end, end); 4680 4681 amap_lock(amap); 4682 for (; cp_start != cp_end; cp_start += PAGE_SIZE) { 4683 anon = amap_lookup(&entry->aref, 4684 cp_start - entry->start); 4685 if (anon == NULL) 4686 continue; 4687 4688 KASSERT(anon->an_lock == amap->am_lock); 4689 pg = anon->an_page; 4690 if (pg == NULL) { 4691 continue; 4692 } 4693 KASSERT(pg->pg_flags & PQ_ANON); 4694 4695 switch (flags & (PGO_CLEANIT|PGO_FREE|PGO_DEACTIVATE)) { 4696 /* 4697 * XXX In these first 3 cases, we always just 4698 * XXX deactivate the page. We may want to 4699 * XXX handle the different cases more 4700 * XXX specifically, in the future. 4701 */ 4702 case PGO_CLEANIT|PGO_FREE: 4703 case PGO_CLEANIT|PGO_DEACTIVATE: 4704 case PGO_DEACTIVATE: 4705 deactivate_it: 4706 /* skip the page if it's wired */ 4707 if (pg->wire_count != 0) 4708 break; 4709 4710 uvm_lock_pageq(); 4711 4712 KASSERT(pg->uanon == anon); 4713 4714 /* zap all mappings for the page. */ 4715 pmap_page_protect(pg, PROT_NONE); 4716 4717 /* ...and deactivate the page. */ 4718 uvm_pagedeactivate(pg); 4719 4720 uvm_unlock_pageq(); 4721 break; 4722 case PGO_FREE: 4723 /* 4724 * If there are multiple references to 4725 * the amap, just deactivate the page. 4726 */ 4727 if (amap_refs(amap) > 1) 4728 goto deactivate_it; 4729 4730 /* XXX skip the page if it's wired */ 4731 if (pg->wire_count != 0) { 4732 break; 4733 } 4734 amap_unadd(&entry->aref, 4735 cp_start - entry->start); 4736 refs = --anon->an_ref; 4737 if (refs == 0) 4738 uvm_anfree(anon); 4739 break; 4740 default: 4741 panic("uvm_map_clean: weird flags"); 4742 } 4743 } 4744 amap_unlock(amap); 4745 4746 flush_object: 4747 cp_start = MAX(entry->start, start); 4748 cp_end = MIN(entry->end, end); 4749 4750 /* 4751 * flush pages if we've got a valid backing object. 4752 * 4753 * Don't PGO_FREE if we don't have write permission 4754 * and don't flush if this is a copy-on-write object 4755 * since we can't know our permissions on it. 4756 */ 4757 if (uobj != NULL && 4758 ((flags & PGO_FREE) == 0 || 4759 ((entry->max_protection & PROT_WRITE) != 0 && 4760 (entry->etype & UVM_ET_COPYONWRITE) == 0))) { 4761 rv = uobj->pgops->pgo_flush(uobj, 4762 cp_start - entry->start + entry->offset, 4763 cp_end - entry->start + entry->offset, flags); 4764 4765 if (rv == FALSE) 4766 error = EFAULT; 4767 } 4768 } 4769 4770 vm_map_unlock_read(map); 4771 return error; 4772 } 4773 4774 /* 4775 * UVM_MAP_CLIP_END implementation 4776 */ 4777 void 4778 uvm_map_clip_end(struct vm_map *map, struct vm_map_entry *entry, vaddr_t addr) 4779 { 4780 struct vm_map_entry *tmp; 4781 4782 KASSERT(entry->start < addr && VMMAP_FREE_END(entry) > addr); 4783 tmp = uvm_mapent_alloc(map, 0); 4784 4785 /* Invoke splitentry. */ 4786 uvm_map_splitentry(map, entry, tmp, addr); 4787 } 4788 4789 /* 4790 * UVM_MAP_CLIP_START implementation 4791 * 4792 * Clippers are required to not change the pointers to the entry they are 4793 * clipping on. 4794 * Since uvm_map_splitentry turns the original entry into the lowest 4795 * entry (address wise) we do a swap between the new entry and the original 4796 * entry, prior to calling uvm_map_splitentry. 4797 */ 4798 void 4799 uvm_map_clip_start(struct vm_map *map, struct vm_map_entry *entry, vaddr_t addr) 4800 { 4801 struct vm_map_entry *tmp; 4802 struct uvm_addr_state *free; 4803 4804 /* Unlink original. */ 4805 free = uvm_map_uaddr_e(map, entry); 4806 uvm_mapent_free_remove(map, free, entry); 4807 uvm_mapent_addr_remove(map, entry); 4808 4809 /* Copy entry. */ 4810 KASSERT(entry->start < addr && VMMAP_FREE_END(entry) > addr); 4811 tmp = uvm_mapent_alloc(map, 0); 4812 uvm_mapent_copy(entry, tmp); 4813 4814 /* Put new entry in place of original entry. */ 4815 uvm_mapent_addr_insert(map, tmp); 4816 uvm_mapent_free_insert(map, free, tmp); 4817 4818 /* Invoke splitentry. */ 4819 uvm_map_splitentry(map, tmp, entry, addr); 4820 } 4821 4822 /* 4823 * Boundary fixer. 4824 */ 4825 static inline vaddr_t uvm_map_boundfix(vaddr_t, vaddr_t, vaddr_t); 4826 static inline vaddr_t 4827 uvm_map_boundfix(vaddr_t min, vaddr_t max, vaddr_t bound) 4828 { 4829 return (min < bound && max > bound) ? bound : max; 4830 } 4831 4832 /* 4833 * Choose free list based on address at start of free space. 4834 * 4835 * The uvm_addr_state returned contains addr and is the first of: 4836 * - uaddr_exe 4837 * - uaddr_brk_stack 4838 * - uaddr_any 4839 */ 4840 struct uvm_addr_state* 4841 uvm_map_uaddr(struct vm_map *map, vaddr_t addr) 4842 { 4843 struct uvm_addr_state *uaddr; 4844 int i; 4845 4846 /* Special case the first page, to prevent mmap from returning 0. */ 4847 if (addr < VMMAP_MIN_ADDR) 4848 return NULL; 4849 4850 /* Upper bound for kernel maps at uvm_maxkaddr. */ 4851 if ((map->flags & VM_MAP_ISVMSPACE) == 0) { 4852 if (addr >= uvm_maxkaddr) 4853 return NULL; 4854 } 4855 4856 /* Is the address inside the exe-only map? */ 4857 if (map->uaddr_exe != NULL && addr >= map->uaddr_exe->uaddr_minaddr && 4858 addr < map->uaddr_exe->uaddr_maxaddr) 4859 return map->uaddr_exe; 4860 4861 /* Check if the space falls inside brk/stack area. */ 4862 if ((addr >= map->b_start && addr < map->b_end) || 4863 (addr >= map->s_start && addr < map->s_end)) { 4864 if (map->uaddr_brk_stack != NULL && 4865 addr >= map->uaddr_brk_stack->uaddr_minaddr && 4866 addr < map->uaddr_brk_stack->uaddr_maxaddr) { 4867 return map->uaddr_brk_stack; 4868 } else 4869 return NULL; 4870 } 4871 4872 /* 4873 * Check the other selectors. 4874 * 4875 * These selectors are only marked as the owner, if they have insert 4876 * functions. 4877 */ 4878 for (i = 0; i < nitems(map->uaddr_any); i++) { 4879 uaddr = map->uaddr_any[i]; 4880 if (uaddr == NULL) 4881 continue; 4882 if (uaddr->uaddr_functions->uaddr_free_insert == NULL) 4883 continue; 4884 4885 if (addr >= uaddr->uaddr_minaddr && 4886 addr < uaddr->uaddr_maxaddr) 4887 return uaddr; 4888 } 4889 4890 return NULL; 4891 } 4892 4893 /* 4894 * Choose free list based on address at start of free space. 4895 * 4896 * The uvm_addr_state returned contains addr and is the first of: 4897 * - uaddr_exe 4898 * - uaddr_brk_stack 4899 * - uaddr_any 4900 */ 4901 struct uvm_addr_state* 4902 uvm_map_uaddr_e(struct vm_map *map, struct vm_map_entry *entry) 4903 { 4904 return uvm_map_uaddr(map, VMMAP_FREE_START(entry)); 4905 } 4906 4907 /* 4908 * Returns the first free-memory boundary that is crossed by [min-max]. 4909 */ 4910 vsize_t 4911 uvm_map_boundary(struct vm_map *map, vaddr_t min, vaddr_t max) 4912 { 4913 struct uvm_addr_state *uaddr; 4914 int i; 4915 4916 /* Never return first page. */ 4917 max = uvm_map_boundfix(min, max, VMMAP_MIN_ADDR); 4918 4919 /* Treat the maxkaddr special, if the map is a kernel_map. */ 4920 if ((map->flags & VM_MAP_ISVMSPACE) == 0) 4921 max = uvm_map_boundfix(min, max, uvm_maxkaddr); 4922 4923 /* Check for exe-only boundaries. */ 4924 if (map->uaddr_exe != NULL) { 4925 max = uvm_map_boundfix(min, max, map->uaddr_exe->uaddr_minaddr); 4926 max = uvm_map_boundfix(min, max, map->uaddr_exe->uaddr_maxaddr); 4927 } 4928 4929 /* Check for exe-only boundaries. */ 4930 if (map->uaddr_brk_stack != NULL) { 4931 max = uvm_map_boundfix(min, max, 4932 map->uaddr_brk_stack->uaddr_minaddr); 4933 max = uvm_map_boundfix(min, max, 4934 map->uaddr_brk_stack->uaddr_maxaddr); 4935 } 4936 4937 /* Check other boundaries. */ 4938 for (i = 0; i < nitems(map->uaddr_any); i++) { 4939 uaddr = map->uaddr_any[i]; 4940 if (uaddr != NULL) { 4941 max = uvm_map_boundfix(min, max, uaddr->uaddr_minaddr); 4942 max = uvm_map_boundfix(min, max, uaddr->uaddr_maxaddr); 4943 } 4944 } 4945 4946 /* Boundaries at stack and brk() area. */ 4947 max = uvm_map_boundfix(min, max, map->s_start); 4948 max = uvm_map_boundfix(min, max, map->s_end); 4949 max = uvm_map_boundfix(min, max, map->b_start); 4950 max = uvm_map_boundfix(min, max, map->b_end); 4951 4952 return max; 4953 } 4954 4955 /* 4956 * Update map allocation start and end addresses from proc vmspace. 4957 */ 4958 void 4959 uvm_map_vmspace_update(struct vm_map *map, 4960 struct uvm_map_deadq *dead, int flags) 4961 { 4962 struct vmspace *vm; 4963 vaddr_t b_start, b_end, s_start, s_end; 4964 4965 KASSERT(map->flags & VM_MAP_ISVMSPACE); 4966 KASSERT(offsetof(struct vmspace, vm_map) == 0); 4967 4968 /* 4969 * Derive actual allocation boundaries from vmspace. 4970 */ 4971 vm = (struct vmspace *)map; 4972 b_start = (vaddr_t)vm->vm_daddr; 4973 b_end = b_start + BRKSIZ; 4974 s_start = MIN((vaddr_t)vm->vm_maxsaddr, (vaddr_t)vm->vm_minsaddr); 4975 s_end = MAX((vaddr_t)vm->vm_maxsaddr, (vaddr_t)vm->vm_minsaddr); 4976 #ifdef DIAGNOSTIC 4977 if ((b_start & (vaddr_t)PAGE_MASK) != 0 || 4978 (b_end & (vaddr_t)PAGE_MASK) != 0 || 4979 (s_start & (vaddr_t)PAGE_MASK) != 0 || 4980 (s_end & (vaddr_t)PAGE_MASK) != 0) { 4981 panic("uvm_map_vmspace_update: vmspace %p invalid bounds: " 4982 "b=0x%lx-0x%lx s=0x%lx-0x%lx", 4983 vm, b_start, b_end, s_start, s_end); 4984 } 4985 #endif 4986 4987 if (__predict_true(map->b_start == b_start && map->b_end == b_end && 4988 map->s_start == s_start && map->s_end == s_end)) 4989 return; 4990 4991 uvm_map_freelist_update(map, dead, b_start, b_end, 4992 s_start, s_end, flags); 4993 } 4994 4995 /* 4996 * Grow kernel memory. 4997 * 4998 * This function is only called for kernel maps when an allocation fails. 4999 * 5000 * If the map has a gap that is large enough to accommodate alloc_sz, this 5001 * function will make sure map->free will include it. 5002 */ 5003 void 5004 uvm_map_kmem_grow(struct vm_map *map, struct uvm_map_deadq *dead, 5005 vsize_t alloc_sz, int flags) 5006 { 5007 vsize_t sz; 5008 vaddr_t end; 5009 struct vm_map_entry *entry; 5010 5011 /* Kernel memory only. */ 5012 KASSERT((map->flags & VM_MAP_ISVMSPACE) == 0); 5013 /* Destroy free list. */ 5014 uvm_map_freelist_update_clear(map, dead); 5015 5016 /* Include the guard page in the hard minimum requirement of alloc_sz. */ 5017 if (map->flags & VM_MAP_GUARDPAGES) 5018 alloc_sz += PAGE_SIZE; 5019 5020 /* 5021 * Grow by ALLOCMUL * alloc_sz, but at least VM_MAP_KSIZE_DELTA. 5022 * 5023 * Don't handle the case where the multiplication overflows: 5024 * if that happens, the allocation is probably too big anyway. 5025 */ 5026 sz = MAX(VM_MAP_KSIZE_ALLOCMUL * alloc_sz, VM_MAP_KSIZE_DELTA); 5027 5028 /* 5029 * Walk forward until a gap large enough for alloc_sz shows up. 5030 * 5031 * We assume the kernel map has no boundaries. 5032 * uvm_maxkaddr may be zero. 5033 */ 5034 end = MAX(uvm_maxkaddr, map->min_offset); 5035 entry = uvm_map_entrybyaddr(&map->addr, end); 5036 while (entry && entry->fspace < alloc_sz) 5037 entry = RBT_NEXT(uvm_map_addr, entry); 5038 if (entry) { 5039 end = MAX(VMMAP_FREE_START(entry), end); 5040 end += MIN(sz, map->max_offset - end); 5041 } else 5042 end = map->max_offset; 5043 5044 /* Reserve pmap entries. */ 5045 #ifdef PMAP_GROWKERNEL 5046 uvm_maxkaddr = pmap_growkernel(end); 5047 #else 5048 uvm_maxkaddr = MAX(uvm_maxkaddr, end); 5049 #endif 5050 5051 /* Rebuild free list. */ 5052 uvm_map_freelist_update_refill(map, flags); 5053 } 5054 5055 /* 5056 * Freelist update subfunction: unlink all entries from freelists. 5057 */ 5058 void 5059 uvm_map_freelist_update_clear(struct vm_map *map, struct uvm_map_deadq *dead) 5060 { 5061 struct uvm_addr_state *free; 5062 struct vm_map_entry *entry, *prev, *next; 5063 5064 prev = NULL; 5065 for (entry = RBT_MIN(uvm_map_addr, &map->addr); entry != NULL; 5066 entry = next) { 5067 next = RBT_NEXT(uvm_map_addr, entry); 5068 5069 free = uvm_map_uaddr_e(map, entry); 5070 uvm_mapent_free_remove(map, free, entry); 5071 5072 if (prev != NULL && entry->start == entry->end) { 5073 prev->fspace += VMMAP_FREE_END(entry) - entry->end; 5074 uvm_mapent_addr_remove(map, entry); 5075 DEAD_ENTRY_PUSH(dead, entry); 5076 } else 5077 prev = entry; 5078 } 5079 } 5080 5081 /* 5082 * Freelist update subfunction: refill the freelists with entries. 5083 */ 5084 void 5085 uvm_map_freelist_update_refill(struct vm_map *map, int flags) 5086 { 5087 struct vm_map_entry *entry; 5088 vaddr_t min, max; 5089 5090 RBT_FOREACH(entry, uvm_map_addr, &map->addr) { 5091 min = VMMAP_FREE_START(entry); 5092 max = VMMAP_FREE_END(entry); 5093 entry->fspace = 0; 5094 5095 entry = uvm_map_fix_space(map, entry, min, max, flags); 5096 } 5097 5098 uvm_tree_sanity(map, __FILE__, __LINE__); 5099 } 5100 5101 /* 5102 * Change {a,b}_{start,end} allocation ranges and associated free lists. 5103 */ 5104 void 5105 uvm_map_freelist_update(struct vm_map *map, struct uvm_map_deadq *dead, 5106 vaddr_t b_start, vaddr_t b_end, vaddr_t s_start, vaddr_t s_end, int flags) 5107 { 5108 KDASSERT(b_end >= b_start && s_end >= s_start); 5109 5110 /* Clear all free lists. */ 5111 uvm_map_freelist_update_clear(map, dead); 5112 5113 /* Apply new bounds. */ 5114 map->b_start = b_start; 5115 map->b_end = b_end; 5116 map->s_start = s_start; 5117 map->s_end = s_end; 5118 5119 /* Refill free lists. */ 5120 uvm_map_freelist_update_refill(map, flags); 5121 } 5122 5123 /* 5124 * Assign a uvm_addr_state to the specified pointer in vm_map. 5125 * 5126 * May sleep. 5127 */ 5128 void 5129 uvm_map_set_uaddr(struct vm_map *map, struct uvm_addr_state **which, 5130 struct uvm_addr_state *newval) 5131 { 5132 struct uvm_map_deadq dead; 5133 5134 /* Pointer which must be in this map. */ 5135 KASSERT(which != NULL); 5136 KASSERT((void*)map <= (void*)(which) && 5137 (void*)(which) < (void*)(map + 1)); 5138 5139 vm_map_lock(map); 5140 TAILQ_INIT(&dead); 5141 uvm_map_freelist_update_clear(map, &dead); 5142 5143 uvm_addr_destroy(*which); 5144 *which = newval; 5145 5146 uvm_map_freelist_update_refill(map, 0); 5147 vm_map_unlock(map); 5148 uvm_unmap_detach(&dead, 0); 5149 } 5150 5151 /* 5152 * Correct space insert. 5153 * 5154 * Entry must not be on any freelist. 5155 */ 5156 struct vm_map_entry* 5157 uvm_map_fix_space(struct vm_map *map, struct vm_map_entry *entry, 5158 vaddr_t min, vaddr_t max, int flags) 5159 { 5160 struct uvm_addr_state *free, *entfree; 5161 vaddr_t lmax; 5162 5163 KASSERT(entry == NULL || (entry->etype & UVM_ET_FREEMAPPED) == 0); 5164 KDASSERT(min <= max); 5165 KDASSERT((entry != NULL && VMMAP_FREE_END(entry) == min) || 5166 min == map->min_offset); 5167 5168 /* 5169 * During the function, entfree will always point at the uaddr state 5170 * for entry. 5171 */ 5172 entfree = (entry == NULL ? NULL : 5173 uvm_map_uaddr_e(map, entry)); 5174 5175 while (min != max) { 5176 /* Claim guard page for entry. */ 5177 if ((map->flags & VM_MAP_GUARDPAGES) && entry != NULL && 5178 VMMAP_FREE_END(entry) == entry->end && 5179 entry->start != entry->end) { 5180 if (max - min == 2 * PAGE_SIZE) { 5181 /* 5182 * If the free-space gap is exactly 2 pages, 5183 * we make the guard 2 pages instead of 1. 5184 * Because in a guarded map, an area needs 5185 * at least 2 pages to allocate from: 5186 * one page for the allocation and one for 5187 * the guard. 5188 */ 5189 entry->guard = 2 * PAGE_SIZE; 5190 min = max; 5191 } else { 5192 entry->guard = PAGE_SIZE; 5193 min += PAGE_SIZE; 5194 } 5195 continue; 5196 } 5197 5198 /* 5199 * Handle the case where entry has a 2-page guard, but the 5200 * space after entry is freed. 5201 */ 5202 if (entry != NULL && entry->fspace == 0 && 5203 entry->guard > PAGE_SIZE) { 5204 entry->guard = PAGE_SIZE; 5205 min = VMMAP_FREE_START(entry); 5206 } 5207 5208 lmax = uvm_map_boundary(map, min, max); 5209 free = uvm_map_uaddr(map, min); 5210 5211 /* 5212 * Entries are merged if they point at the same uvm_free(). 5213 * Exception to that rule: if min == uvm_maxkaddr, a new 5214 * entry is started regardless (otherwise the allocators 5215 * will get confused). 5216 */ 5217 if (entry != NULL && free == entfree && 5218 !((map->flags & VM_MAP_ISVMSPACE) == 0 && 5219 min == uvm_maxkaddr)) { 5220 KDASSERT(VMMAP_FREE_END(entry) == min); 5221 entry->fspace += lmax - min; 5222 } else { 5223 /* 5224 * Commit entry to free list: it'll not be added to 5225 * anymore. 5226 * We'll start a new entry and add to that entry 5227 * instead. 5228 */ 5229 if (entry != NULL) 5230 uvm_mapent_free_insert(map, entfree, entry); 5231 5232 /* New entry for new uaddr. */ 5233 entry = uvm_mapent_alloc(map, flags); 5234 KDASSERT(entry != NULL); 5235 entry->end = entry->start = min; 5236 entry->guard = 0; 5237 entry->fspace = lmax - min; 5238 entry->object.uvm_obj = NULL; 5239 entry->offset = 0; 5240 entry->etype = 0; 5241 entry->protection = entry->max_protection = 0; 5242 entry->inheritance = 0; 5243 entry->wired_count = 0; 5244 entry->advice = 0; 5245 entry->aref.ar_pageoff = 0; 5246 entry->aref.ar_amap = NULL; 5247 uvm_mapent_addr_insert(map, entry); 5248 5249 entfree = free; 5250 } 5251 5252 min = lmax; 5253 } 5254 /* Finally put entry on the uaddr state. */ 5255 if (entry != NULL) 5256 uvm_mapent_free_insert(map, entfree, entry); 5257 5258 return entry; 5259 } 5260 5261 /* 5262 * MQuery style of allocation. 5263 * 5264 * This allocator searches forward until sufficient space is found to map 5265 * the given size. 5266 * 5267 * XXX: factor in offset (via pmap_prefer) and protection? 5268 */ 5269 int 5270 uvm_map_mquery(struct vm_map *map, vaddr_t *addr_p, vsize_t sz, voff_t offset, 5271 int flags) 5272 { 5273 struct vm_map_entry *entry, *last; 5274 vaddr_t addr; 5275 vaddr_t tmp, pmap_align, pmap_offset; 5276 int error; 5277 5278 addr = *addr_p; 5279 vm_map_lock_read(map); 5280 5281 /* Configure pmap prefer. */ 5282 if (offset != UVM_UNKNOWN_OFFSET) { 5283 pmap_align = MAX(PAGE_SIZE, PMAP_PREFER_ALIGN()); 5284 pmap_offset = PMAP_PREFER_OFFSET(offset); 5285 } else { 5286 pmap_align = PAGE_SIZE; 5287 pmap_offset = 0; 5288 } 5289 5290 /* Align address to pmap_prefer unless FLAG_FIXED is set. */ 5291 if (!(flags & UVM_FLAG_FIXED) && offset != UVM_UNKNOWN_OFFSET) { 5292 tmp = (addr & ~(pmap_align - 1)) | pmap_offset; 5293 if (tmp < addr) 5294 tmp += pmap_align; 5295 addr = tmp; 5296 } 5297 5298 /* First, check if the requested range is fully available. */ 5299 entry = uvm_map_entrybyaddr(&map->addr, addr); 5300 last = NULL; 5301 if (uvm_map_isavail(map, NULL, &entry, &last, addr, sz)) { 5302 error = 0; 5303 goto out; 5304 } 5305 if (flags & UVM_FLAG_FIXED) { 5306 error = EINVAL; 5307 goto out; 5308 } 5309 5310 error = ENOMEM; /* Default error from here. */ 5311 5312 /* 5313 * At this point, the memory at <addr, sz> is not available. 5314 * The reasons are: 5315 * [1] it's outside the map, 5316 * [2] it starts in used memory (and therefore needs to move 5317 * toward the first free page in entry), 5318 * [3] it starts in free memory but bumps into used memory. 5319 * 5320 * Note that for case [2], the forward moving is handled by the 5321 * for loop below. 5322 */ 5323 if (entry == NULL) { 5324 /* [1] Outside the map. */ 5325 if (addr >= map->max_offset) 5326 goto out; 5327 else 5328 entry = RBT_MIN(uvm_map_addr, &map->addr); 5329 } else if (VMMAP_FREE_START(entry) <= addr) { 5330 /* [3] Bumped into used memory. */ 5331 entry = RBT_NEXT(uvm_map_addr, entry); 5332 } 5333 5334 /* Test if the next entry is sufficient for the allocation. */ 5335 for (; entry != NULL; 5336 entry = RBT_NEXT(uvm_map_addr, entry)) { 5337 if (entry->fspace == 0) 5338 continue; 5339 addr = VMMAP_FREE_START(entry); 5340 5341 restart: /* Restart address checks on address change. */ 5342 tmp = (addr & ~(pmap_align - 1)) | pmap_offset; 5343 if (tmp < addr) 5344 tmp += pmap_align; 5345 addr = tmp; 5346 if (addr >= VMMAP_FREE_END(entry)) 5347 continue; 5348 5349 /* Skip brk() allocation addresses. */ 5350 if (addr + sz > map->b_start && addr < map->b_end) { 5351 if (VMMAP_FREE_END(entry) > map->b_end) { 5352 addr = map->b_end; 5353 goto restart; 5354 } else 5355 continue; 5356 } 5357 /* Skip stack allocation addresses. */ 5358 if (addr + sz > map->s_start && addr < map->s_end) { 5359 if (VMMAP_FREE_END(entry) > map->s_end) { 5360 addr = map->s_end; 5361 goto restart; 5362 } else 5363 continue; 5364 } 5365 5366 last = NULL; 5367 if (uvm_map_isavail(map, NULL, &entry, &last, addr, sz)) { 5368 error = 0; 5369 goto out; 5370 } 5371 } 5372 5373 out: 5374 vm_map_unlock_read(map); 5375 if (error == 0) 5376 *addr_p = addr; 5377 return error; 5378 } 5379 5380 /* 5381 * Determine allocation bias. 5382 * 5383 * Returns 1 if we should bias to high addresses, -1 for a bias towards low 5384 * addresses, or 0 for no bias. 5385 * The bias mechanism is intended to avoid clashing with brk() and stack 5386 * areas. 5387 */ 5388 int 5389 uvm_mapent_bias(struct vm_map *map, struct vm_map_entry *entry) 5390 { 5391 vaddr_t start, end; 5392 5393 start = VMMAP_FREE_START(entry); 5394 end = VMMAP_FREE_END(entry); 5395 5396 /* Stay at the top of brk() area. */ 5397 if (end >= map->b_start && start < map->b_end) 5398 return 1; 5399 /* Stay at the far end of the stack area. */ 5400 if (end >= map->s_start && start < map->s_end) { 5401 #ifdef MACHINE_STACK_GROWS_UP 5402 return 1; 5403 #else 5404 return -1; 5405 #endif 5406 } 5407 5408 /* No bias, this area is meant for us. */ 5409 return 0; 5410 } 5411 5412 5413 boolean_t 5414 vm_map_lock_try_ln(struct vm_map *map, char *file, int line) 5415 { 5416 boolean_t rv; 5417 5418 if (map->flags & VM_MAP_INTRSAFE) { 5419 rv = mtx_enter_try(&map->mtx); 5420 } else { 5421 mtx_enter(&map->flags_lock); 5422 if (map->flags & VM_MAP_BUSY) { 5423 mtx_leave(&map->flags_lock); 5424 return (FALSE); 5425 } 5426 mtx_leave(&map->flags_lock); 5427 rv = (rw_enter(&map->lock, RW_WRITE|RW_NOSLEEP) == 0); 5428 /* check if the lock is busy and back out if we won the race */ 5429 if (rv) { 5430 mtx_enter(&map->flags_lock); 5431 if (map->flags & VM_MAP_BUSY) { 5432 rw_exit(&map->lock); 5433 rv = FALSE; 5434 } 5435 mtx_leave(&map->flags_lock); 5436 } 5437 } 5438 5439 if (rv) { 5440 map->timestamp++; 5441 LPRINTF(("map lock: %p (at %s %d)\n", map, file, line)); 5442 uvm_tree_sanity(map, file, line); 5443 uvm_tree_size_chk(map, file, line); 5444 } 5445 5446 return (rv); 5447 } 5448 5449 void 5450 vm_map_lock_ln(struct vm_map *map, char *file, int line) 5451 { 5452 if ((map->flags & VM_MAP_INTRSAFE) == 0) { 5453 do { 5454 mtx_enter(&map->flags_lock); 5455 tryagain: 5456 while (map->flags & VM_MAP_BUSY) { 5457 map->flags |= VM_MAP_WANTLOCK; 5458 msleep_nsec(&map->flags, &map->flags_lock, 5459 PVM, vmmapbsy, INFSLP); 5460 } 5461 mtx_leave(&map->flags_lock); 5462 } while (rw_enter(&map->lock, RW_WRITE|RW_SLEEPFAIL) != 0); 5463 /* check if the lock is busy and back out if we won the race */ 5464 mtx_enter(&map->flags_lock); 5465 if (map->flags & VM_MAP_BUSY) { 5466 rw_exit(&map->lock); 5467 goto tryagain; 5468 } 5469 mtx_leave(&map->flags_lock); 5470 } else { 5471 mtx_enter(&map->mtx); 5472 } 5473 5474 map->timestamp++; 5475 LPRINTF(("map lock: %p (at %s %d)\n", map, file, line)); 5476 uvm_tree_sanity(map, file, line); 5477 uvm_tree_size_chk(map, file, line); 5478 } 5479 5480 void 5481 vm_map_lock_read_ln(struct vm_map *map, char *file, int line) 5482 { 5483 if ((map->flags & VM_MAP_INTRSAFE) == 0) 5484 rw_enter_read(&map->lock); 5485 else 5486 mtx_enter(&map->mtx); 5487 LPRINTF(("map lock: %p (at %s %d)\n", map, file, line)); 5488 uvm_tree_sanity(map, file, line); 5489 uvm_tree_size_chk(map, file, line); 5490 } 5491 5492 void 5493 vm_map_unlock_ln(struct vm_map *map, char *file, int line) 5494 { 5495 uvm_tree_sanity(map, file, line); 5496 uvm_tree_size_chk(map, file, line); 5497 LPRINTF(("map unlock: %p (at %s %d)\n", map, file, line)); 5498 if ((map->flags & VM_MAP_INTRSAFE) == 0) 5499 rw_exit(&map->lock); 5500 else 5501 mtx_leave(&map->mtx); 5502 } 5503 5504 void 5505 vm_map_unlock_read_ln(struct vm_map *map, char *file, int line) 5506 { 5507 /* XXX: RO */ uvm_tree_sanity(map, file, line); 5508 /* XXX: RO */ uvm_tree_size_chk(map, file, line); 5509 LPRINTF(("map unlock: %p (at %s %d)\n", map, file, line)); 5510 if ((map->flags & VM_MAP_INTRSAFE) == 0) 5511 rw_exit_read(&map->lock); 5512 else 5513 mtx_leave(&map->mtx); 5514 } 5515 5516 void 5517 vm_map_downgrade_ln(struct vm_map *map, char *file, int line) 5518 { 5519 uvm_tree_sanity(map, file, line); 5520 uvm_tree_size_chk(map, file, line); 5521 LPRINTF(("map unlock: %p (at %s %d)\n", map, file, line)); 5522 LPRINTF(("map lock: %p (at %s %d)\n", map, file, line)); 5523 KASSERT((map->flags & VM_MAP_INTRSAFE) == 0); 5524 if ((map->flags & VM_MAP_INTRSAFE) == 0) 5525 rw_enter(&map->lock, RW_DOWNGRADE); 5526 } 5527 5528 void 5529 vm_map_upgrade_ln(struct vm_map *map, char *file, int line) 5530 { 5531 /* XXX: RO */ uvm_tree_sanity(map, file, line); 5532 /* XXX: RO */ uvm_tree_size_chk(map, file, line); 5533 LPRINTF(("map unlock: %p (at %s %d)\n", map, file, line)); 5534 KASSERT((map->flags & VM_MAP_INTRSAFE) == 0); 5535 if ((map->flags & VM_MAP_INTRSAFE) == 0) { 5536 rw_exit_read(&map->lock); 5537 rw_enter_write(&map->lock); 5538 } 5539 LPRINTF(("map lock: %p (at %s %d)\n", map, file, line)); 5540 uvm_tree_sanity(map, file, line); 5541 } 5542 5543 void 5544 vm_map_busy_ln(struct vm_map *map, char *file, int line) 5545 { 5546 KASSERT((map->flags & VM_MAP_INTRSAFE) == 0); 5547 mtx_enter(&map->flags_lock); 5548 map->flags |= VM_MAP_BUSY; 5549 mtx_leave(&map->flags_lock); 5550 } 5551 5552 void 5553 vm_map_unbusy_ln(struct vm_map *map, char *file, int line) 5554 { 5555 int oflags; 5556 5557 KASSERT((map->flags & VM_MAP_INTRSAFE) == 0); 5558 mtx_enter(&map->flags_lock); 5559 oflags = map->flags; 5560 map->flags &= ~(VM_MAP_BUSY|VM_MAP_WANTLOCK); 5561 mtx_leave(&map->flags_lock); 5562 if (oflags & VM_MAP_WANTLOCK) 5563 wakeup(&map->flags); 5564 } 5565 5566 #ifndef SMALL_KERNEL 5567 int 5568 uvm_map_fill_vmmap(struct vm_map *map, struct kinfo_vmentry *kve, 5569 size_t *lenp) 5570 { 5571 struct vm_map_entry *entry; 5572 vaddr_t start; 5573 int cnt, maxcnt, error = 0; 5574 5575 KASSERT(*lenp > 0); 5576 KASSERT((*lenp % sizeof(*kve)) == 0); 5577 cnt = 0; 5578 maxcnt = *lenp / sizeof(*kve); 5579 KASSERT(maxcnt > 0); 5580 5581 /* 5582 * Return only entries whose address is above the given base 5583 * address. This allows userland to iterate without knowing the 5584 * number of entries beforehand. 5585 */ 5586 start = (vaddr_t)kve[0].kve_start; 5587 5588 vm_map_lock(map); 5589 RBT_FOREACH(entry, uvm_map_addr, &map->addr) { 5590 if (cnt == maxcnt) { 5591 error = ENOMEM; 5592 break; 5593 } 5594 if (start != 0 && entry->start < start) 5595 continue; 5596 kve->kve_start = entry->start; 5597 kve->kve_end = entry->end; 5598 kve->kve_guard = entry->guard; 5599 kve->kve_fspace = entry->fspace; 5600 kve->kve_fspace_augment = entry->fspace_augment; 5601 kve->kve_offset = entry->offset; 5602 kve->kve_wired_count = entry->wired_count; 5603 kve->kve_etype = entry->etype; 5604 kve->kve_protection = entry->protection; 5605 kve->kve_max_protection = entry->max_protection; 5606 kve->kve_advice = entry->advice; 5607 kve->kve_inheritance = entry->inheritance; 5608 kve->kve_flags = entry->flags; 5609 kve++; 5610 cnt++; 5611 } 5612 vm_map_unlock(map); 5613 5614 KASSERT(cnt <= maxcnt); 5615 5616 *lenp = sizeof(*kve) * cnt; 5617 return error; 5618 } 5619 #endif 5620 5621 5622 RBT_GENERATE_AUGMENT(uvm_map_addr, vm_map_entry, daddrs.addr_entry, 5623 uvm_mapentry_addrcmp, uvm_map_addr_augment); 5624 5625 5626 /* 5627 * MD code: vmspace allocator setup. 5628 */ 5629 5630 #ifdef __i386__ 5631 void 5632 uvm_map_setup_md(struct vm_map *map) 5633 { 5634 vaddr_t min, max; 5635 5636 min = map->min_offset; 5637 max = map->max_offset; 5638 5639 /* 5640 * Ensure the selectors will not try to manage page 0; 5641 * it's too special. 5642 */ 5643 if (min < VMMAP_MIN_ADDR) 5644 min = VMMAP_MIN_ADDR; 5645 5646 #if 0 /* Cool stuff, not yet */ 5647 /* Executable code is special. */ 5648 map->uaddr_exe = uaddr_rnd_create(min, I386_MAX_EXE_ADDR); 5649 /* Place normal allocations beyond executable mappings. */ 5650 map->uaddr_any[3] = uaddr_pivot_create(2 * I386_MAX_EXE_ADDR, max); 5651 #else /* Crappy stuff, for now */ 5652 map->uaddr_any[0] = uaddr_rnd_create(min, max); 5653 #endif 5654 5655 #ifndef SMALL_KERNEL 5656 map->uaddr_brk_stack = uaddr_stack_brk_create(min, max); 5657 #endif /* !SMALL_KERNEL */ 5658 } 5659 #elif __LP64__ 5660 void 5661 uvm_map_setup_md(struct vm_map *map) 5662 { 5663 vaddr_t min, max; 5664 5665 min = map->min_offset; 5666 max = map->max_offset; 5667 5668 /* 5669 * Ensure the selectors will not try to manage page 0; 5670 * it's too special. 5671 */ 5672 if (min < VMMAP_MIN_ADDR) 5673 min = VMMAP_MIN_ADDR; 5674 5675 #if 0 /* Cool stuff, not yet */ 5676 map->uaddr_any[3] = uaddr_pivot_create(MAX(min, 0x100000000ULL), max); 5677 #else /* Crappy stuff, for now */ 5678 map->uaddr_any[0] = uaddr_rnd_create(min, max); 5679 #endif 5680 5681 #ifndef SMALL_KERNEL 5682 map->uaddr_brk_stack = uaddr_stack_brk_create(min, max); 5683 #endif /* !SMALL_KERNEL */ 5684 } 5685 #else /* non-i386, 32 bit */ 5686 void 5687 uvm_map_setup_md(struct vm_map *map) 5688 { 5689 vaddr_t min, max; 5690 5691 min = map->min_offset; 5692 max = map->max_offset; 5693 5694 /* 5695 * Ensure the selectors will not try to manage page 0; 5696 * it's too special. 5697 */ 5698 if (min < VMMAP_MIN_ADDR) 5699 min = VMMAP_MIN_ADDR; 5700 5701 #if 0 /* Cool stuff, not yet */ 5702 map->uaddr_any[3] = uaddr_pivot_create(min, max); 5703 #else /* Crappy stuff, for now */ 5704 map->uaddr_any[0] = uaddr_rnd_create(min, max); 5705 #endif 5706 5707 #ifndef SMALL_KERNEL 5708 map->uaddr_brk_stack = uaddr_stack_brk_create(min, max); 5709 #endif /* !SMALL_KERNEL */ 5710 } 5711 #endif 5712