1 /* 2 * Copyright 2009, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Copyright 2002-2009, Axel Dörfler, axeld@pinc-software.de. 4 * Distributed under the terms of the MIT License. 5 * 6 * Copyright 2001-2002, Travis Geiselbrecht. All rights reserved. 7 * Distributed under the terms of the NewOS License. 8 */ 9 10 11 #include "VMUserAddressSpace.h" 12 13 #include <stdlib.h> 14 15 #include <KernelExport.h> 16 17 #include <heap.h> 18 #include <thread.h> 19 #include <vm/vm.h> 20 #include <vm/VMArea.h> 21 22 23 //#define TRACE_VM 24 #ifdef TRACE_VM 25 # define TRACE(x) dprintf x 26 #else 27 # define TRACE(x) ; 28 #endif 29 30 31 /*! Verifies that an area with the given aligned base and size fits into 32 the spot defined by base and limit and checks for overflows. 33 */ 34 static inline bool 35 is_valid_spot(addr_t base, addr_t alignedBase, addr_t size, addr_t limit) 36 { 37 return (alignedBase >= base && alignedBase + (size - 1) > alignedBase 38 && alignedBase + (size - 1) <= limit); 39 } 40 41 42 VMUserAddressSpace::VMUserAddressSpace(team_id id, addr_t base, size_t size) 43 : 44 VMAddressSpace(id, base, size, "address space"), 45 fAreaHint(NULL) 46 { 47 } 48 49 50 VMUserAddressSpace::~VMUserAddressSpace() 51 { 52 } 53 54 55 inline VMArea* 56 VMUserAddressSpace::FirstArea() const 57 { 58 VMUserArea* area = fAreas.Head(); 59 while (area != NULL && area->id == RESERVED_AREA_ID) 60 area = fAreas.GetNext(area); 61 return area; 62 } 63 64 65 inline VMArea* 66 VMUserAddressSpace::NextArea(VMArea* _area) const 67 { 68 VMUserArea* area = static_cast<VMUserArea*>(_area); 69 area = fAreas.GetNext(area); 70 while (area != NULL && area->id == RESERVED_AREA_ID) 71 area = fAreas.GetNext(area); 72 return area; 73 } 74 75 76 VMArea* 77 VMUserAddressSpace::CreateArea(const char* name, uint32 wiring, 78 uint32 protection) 79 { 80 return VMUserArea::Create(this, name, wiring, protection); 81 } 82 83 84 void 85 VMUserAddressSpace::DeleteArea(VMArea* area) 86 { 87 delete static_cast<VMUserArea*>(area); 88 } 89 90 91 //! You must hold the address space's read lock. 92 VMArea* 93 VMUserAddressSpace::LookupArea(addr_t address) const 94 { 95 // check the area hint first 96 if (fAreaHint != NULL && fAreaHint->ContainsAddress(address)) 97 return fAreaHint; 98 99 for (VMUserAreaList::ConstIterator it = fAreas.GetIterator(); 100 VMUserArea* area = it.Next();) { 101 if (area->id == RESERVED_AREA_ID) 102 continue; 103 104 if (area->ContainsAddress(address)) { 105 fAreaHint = area; 106 return area; 107 } 108 } 109 110 return NULL; 111 } 112 113 114 /*! This inserts the area you pass into the address space. 115 It will also set the "_address" argument to its base address when 116 the call succeeds. 117 You need to hold the VMAddressSpace write lock. 118 */ 119 status_t 120 VMUserAddressSpace::InsertArea(void** _address, uint32 addressSpec, 121 size_t size, VMArea* _area) 122 { 123 VMUserArea* area = static_cast<VMUserArea*>(_area); 124 125 addr_t searchBase, searchEnd; 126 status_t status; 127 128 switch (addressSpec) { 129 case B_EXACT_ADDRESS: 130 searchBase = (addr_t)*_address; 131 searchEnd = (addr_t)*_address + (size - 1); 132 break; 133 134 case B_BASE_ADDRESS: 135 searchBase = (addr_t)*_address; 136 searchEnd = fEndAddress; 137 break; 138 139 case B_ANY_ADDRESS: 140 case B_ANY_KERNEL_ADDRESS: 141 case B_ANY_KERNEL_BLOCK_ADDRESS: 142 searchBase = fBase; 143 // TODO: remove this again when vm86 mode is moved into the kernel 144 // completely (currently needs a userland address space!) 145 if (searchBase == USER_BASE) 146 searchBase = USER_BASE_ANY; 147 searchEnd = fEndAddress; 148 break; 149 150 default: 151 return B_BAD_VALUE; 152 } 153 154 status = _InsertAreaSlot(searchBase, size, searchEnd, addressSpec, area); 155 if (status == B_OK) { 156 *_address = (void*)area->Base(); 157 fFreeSpace -= area->Size(); 158 } 159 160 return status; 161 } 162 163 164 //! You must hold the address space's write lock. 165 void 166 VMUserAddressSpace::RemoveArea(VMArea* _area) 167 { 168 VMUserArea* area = static_cast<VMUserArea*>(_area); 169 170 fAreas.Remove(area); 171 172 if (area->id != RESERVED_AREA_ID) { 173 IncrementChangeCount(); 174 fFreeSpace += area->Size(); 175 176 if (area == fAreaHint) 177 fAreaHint = NULL; 178 } 179 } 180 181 182 bool 183 VMUserAddressSpace::CanResizeArea(VMArea* area, size_t newSize) 184 { 185 VMUserArea* next = fAreas.GetNext(static_cast<VMUserArea*>(area)); 186 addr_t newEnd = area->Base() + (newSize - 1); 187 if (next == NULL) { 188 if (fEndAddress >= newEnd) 189 return true; 190 } else { 191 if (next->Base() > newEnd) 192 return true; 193 } 194 195 // If the area was created inside a reserved area, it can 196 // also be resized in that area 197 // TODO: if there is free space after the reserved area, it could 198 // be used as well... 199 if (next->id == RESERVED_AREA_ID && next->cache_offset <= area->Base() 200 && next->Base() + (next->Size() - 1) >= newEnd) { 201 return true; 202 } 203 204 return false; 205 } 206 207 208 status_t 209 VMUserAddressSpace::ResizeArea(VMArea* _area, size_t newSize) 210 { 211 VMUserArea* area = static_cast<VMUserArea*>(_area); 212 213 addr_t newEnd = area->Base() + (newSize - 1); 214 VMUserArea* next = fAreas.GetNext(area); 215 if (next != NULL && next->Base() <= newEnd) { 216 if (next->id != RESERVED_AREA_ID 217 || next->cache_offset > area->Base() 218 || next->Base() + (next->Size() - 1) < newEnd) { 219 panic("resize situation for area %p has changed although we " 220 "should have the address space lock", area); 221 return B_ERROR; 222 } 223 224 // resize reserved area 225 addr_t offset = area->Base() + newSize - next->Base(); 226 if (next->Size() <= offset) { 227 RemoveArea(next); 228 delete next; 229 } else { 230 status_t error = ShrinkAreaHead(next, next->Size() - offset); 231 if (error != B_OK) 232 return error; 233 } 234 } 235 236 area->SetSize(newSize); 237 return B_OK; 238 } 239 240 241 status_t 242 VMUserAddressSpace::ShrinkAreaHead(VMArea* area, size_t size) 243 { 244 size_t oldSize = area->Size(); 245 if (size == oldSize) 246 return B_OK; 247 248 area->SetBase(area->Base() + oldSize - size); 249 area->SetSize(size); 250 251 return B_OK; 252 } 253 254 255 status_t 256 VMUserAddressSpace::ShrinkAreaTail(VMArea* area, size_t size) 257 { 258 size_t oldSize = area->Size(); 259 if (size == oldSize) 260 return B_OK; 261 262 area->SetSize(size); 263 264 return B_OK; 265 } 266 267 268 status_t 269 VMUserAddressSpace::ReserveAddressRange(void** _address, uint32 addressSpec, 270 size_t size, uint32 flags) 271 { 272 // check to see if this address space has entered DELETE state 273 if (fDeleting) { 274 // okay, someone is trying to delete this address space now, so we 275 // can't insert the area, let's back out 276 return B_BAD_TEAM_ID; 277 } 278 279 VMUserArea* area = VMUserArea::CreateReserved(this, flags); 280 if (area == NULL) 281 return B_NO_MEMORY; 282 283 status_t status = InsertArea(_address, addressSpec, size, area); 284 if (status != B_OK) { 285 delete area; 286 return status; 287 } 288 289 area->cache_offset = area->Base(); 290 // we cache the original base address here 291 292 Get(); 293 return B_OK; 294 } 295 296 297 status_t 298 VMUserAddressSpace::UnreserveAddressRange(addr_t address, size_t size) 299 { 300 // check to see if this address space has entered DELETE state 301 if (fDeleting) { 302 // okay, someone is trying to delete this address space now, so we can't 303 // insert the area, so back out 304 return B_BAD_TEAM_ID; 305 } 306 307 // search area list and remove any matching reserved ranges 308 addr_t endAddress = address + (size - 1); 309 for (VMUserAreaList::Iterator it = fAreas.GetIterator(); 310 VMUserArea* area = it.Next();) { 311 // the area must be completely part of the reserved range 312 if (area->Base() + (area->Size() - 1) > endAddress) 313 break; 314 if (area->id == RESERVED_AREA_ID && area->Base() >= (addr_t)address) { 315 // remove reserved range 316 RemoveArea(area); 317 Put(); 318 delete area; 319 } 320 } 321 322 return B_OK; 323 } 324 325 326 void 327 VMUserAddressSpace::UnreserveAllAddressRanges() 328 { 329 for (VMUserAreaList::Iterator it = fAreas.GetIterator(); 330 VMUserArea* area = it.Next();) { 331 if (area->id == RESERVED_AREA_ID) { 332 RemoveArea(area); 333 Put(); 334 delete area; 335 } 336 } 337 } 338 339 340 void 341 VMUserAddressSpace::Dump() const 342 { 343 VMAddressSpace::Dump(); 344 kprintf("area_hint: %p\n", fAreaHint); 345 346 kprintf("area_list:\n"); 347 348 for (VMUserAreaList::ConstIterator it = fAreas.GetIterator(); 349 VMUserArea* area = it.Next();) { 350 kprintf(" area 0x%lx: ", area->id); 351 kprintf("base_addr = 0x%lx ", area->Base()); 352 kprintf("size = 0x%lx ", area->Size()); 353 kprintf("name = '%s' ", area->name); 354 kprintf("protection = 0x%lx\n", area->protection); 355 } 356 } 357 358 359 /*! Finds a reserved area that covers the region spanned by \a start and 360 \a size, inserts the \a area into that region and makes sure that 361 there are reserved regions for the remaining parts. 362 */ 363 status_t 364 VMUserAddressSpace::_InsertAreaIntoReservedRegion(addr_t start, size_t size, 365 VMUserArea* area) 366 { 367 VMUserArea* next; 368 369 for (VMUserAreaList::Iterator it = fAreas.GetIterator(); 370 (next = it.Next()) != NULL;) { 371 if (next->Base() <= start 372 && next->Base() + (next->Size() - 1) >= start + (size - 1)) { 373 // This area covers the requested range 374 if (next->id != RESERVED_AREA_ID) { 375 // but it's not reserved space, it's a real area 376 return B_BAD_VALUE; 377 } 378 379 break; 380 } 381 } 382 383 if (next == NULL) 384 return B_ENTRY_NOT_FOUND; 385 386 // Now we have to transfer the requested part of the reserved 387 // range to the new area - and remove, resize or split the old 388 // reserved area. 389 390 if (start == next->Base()) { 391 // the area starts at the beginning of the reserved range 392 fAreas.Insert(next, area); 393 394 if (size == next->Size()) { 395 // the new area fully covers the reversed range 396 fAreas.Remove(next); 397 Put(); 398 delete next; 399 } else { 400 // resize the reserved range behind the area 401 next->SetBase(next->Base() + size); 402 next->SetSize(next->Size() - size); 403 } 404 } else if (start + size == next->Base() + next->Size()) { 405 // the area is at the end of the reserved range 406 fAreas.Insert(fAreas.GetNext(next), area); 407 408 // resize the reserved range before the area 409 next->SetSize(start - next->Base()); 410 } else { 411 // the area splits the reserved range into two separate ones 412 // we need a new reserved area to cover this space 413 VMUserArea* reserved = VMUserArea::CreateReserved(this, 414 next->protection); 415 if (reserved == NULL) 416 return B_NO_MEMORY; 417 418 Get(); 419 fAreas.Insert(fAreas.GetNext(next), reserved); 420 fAreas.Insert(reserved, area); 421 422 // resize regions 423 reserved->SetSize(next->Base() + next->Size() - start - size); 424 next->SetSize(start - next->Base()); 425 reserved->SetBase(start + size); 426 reserved->cache_offset = next->cache_offset; 427 } 428 429 area->SetBase(start); 430 area->SetSize(size); 431 IncrementChangeCount(); 432 433 return B_OK; 434 } 435 436 437 /*! Must be called with this address space's write lock held */ 438 status_t 439 VMUserAddressSpace::_InsertAreaSlot(addr_t start, addr_t size, addr_t end, 440 uint32 addressSpec, VMUserArea* area) 441 { 442 VMUserArea* last = NULL; 443 VMUserArea* next; 444 bool foundSpot = false; 445 446 TRACE(("VMUserAddressSpace::_InsertAreaSlot: address space %p, start " 447 "0x%lx, size %ld, end 0x%lx, addressSpec %ld, area %p\n", this, start, 448 size, end, addressSpec, area)); 449 450 // do some sanity checking 451 if (start < fBase || size == 0 || end > fEndAddress 452 || start + (size - 1) > end) 453 return B_BAD_ADDRESS; 454 455 if (addressSpec == B_EXACT_ADDRESS && area->id != RESERVED_AREA_ID) { 456 // search for a reserved area 457 status_t status = _InsertAreaIntoReservedRegion(start, size, area); 458 if (status == B_OK || status == B_BAD_VALUE) 459 return status; 460 461 // There was no reserved area, and the slot doesn't seem to be used 462 // already 463 // TODO: this could be further optimized. 464 } 465 466 size_t alignment = B_PAGE_SIZE; 467 if (addressSpec == B_ANY_KERNEL_BLOCK_ADDRESS) { 468 // align the memory to the next power of two of the size 469 while (alignment < size) 470 alignment <<= 1; 471 } 472 473 start = ROUNDUP(start, alignment); 474 475 // walk up to the spot where we should start searching 476 second_chance: 477 VMUserAreaList::Iterator it = fAreas.GetIterator(); 478 while ((next = it.Next()) != NULL) { 479 if (next->Base() > start + (size - 1)) { 480 // we have a winner 481 break; 482 } 483 484 last = next; 485 } 486 487 // find the right spot depending on the address specification - the area 488 // will be inserted directly after "last" ("next" is not referenced anymore) 489 490 switch (addressSpec) { 491 case B_ANY_ADDRESS: 492 case B_ANY_KERNEL_ADDRESS: 493 case B_ANY_KERNEL_BLOCK_ADDRESS: 494 { 495 // find a hole big enough for a new area 496 if (last == NULL) { 497 // see if we can build it at the beginning of the virtual map 498 addr_t alignedBase = ROUNDUP(fBase, alignment); 499 if (is_valid_spot(fBase, alignedBase, size, 500 next == NULL ? end : next->Base())) { 501 foundSpot = true; 502 area->SetBase(alignedBase); 503 break; 504 } 505 506 last = next; 507 next = it.Next(); 508 } 509 510 // keep walking 511 while (next != NULL) { 512 addr_t alignedBase = ROUNDUP(last->Base() + last->Size(), 513 alignment); 514 if (is_valid_spot(last->Base() + (last->Size() - 1), 515 alignedBase, size, next->Base())) { 516 foundSpot = true; 517 area->SetBase(alignedBase); 518 break; 519 } 520 521 last = next; 522 next = it.Next(); 523 } 524 525 if (foundSpot) 526 break; 527 528 addr_t alignedBase = ROUNDUP(last->Base() + last->Size(), 529 alignment); 530 if (is_valid_spot(last->Base() + (last->Size() - 1), alignedBase, 531 size, end)) { 532 // got a spot 533 foundSpot = true; 534 area->SetBase(alignedBase); 535 break; 536 } else if (area->id != RESERVED_AREA_ID) { 537 // We didn't find a free spot - if there are any reserved areas, 538 // we can now test those for free space 539 // TODO: it would make sense to start with the biggest of them 540 it.Rewind(); 541 next = it.Next(); 542 for (last = NULL; next != NULL; next = it.Next()) { 543 if (next->id != RESERVED_AREA_ID) { 544 last = next; 545 continue; 546 } 547 548 // TODO: take free space after the reserved area into 549 // account! 550 addr_t alignedBase = ROUNDUP(next->Base(), alignment); 551 if (next->Base() == alignedBase && next->Size() == size) { 552 // The reserved area is entirely covered, and thus, 553 // removed 554 fAreas.Remove(next); 555 556 foundSpot = true; 557 area->SetBase(alignedBase); 558 delete next; 559 break; 560 } 561 562 if ((next->protection & RESERVED_AVOID_BASE) == 0 563 && alignedBase == next->Base() 564 && next->Size() >= size) { 565 // The new area will be placed at the beginning of the 566 // reserved area and the reserved area will be offset 567 // and resized 568 foundSpot = true; 569 next->SetBase(next->Base() + size); 570 next->SetSize(next->Size() - size); 571 area->SetBase(alignedBase); 572 break; 573 } 574 575 if (is_valid_spot(next->Base(), alignedBase, size, 576 next->Base() + (next->Size() - 1))) { 577 // The new area will be placed at the end of the 578 // reserved area, and the reserved area will be resized 579 // to make space 580 alignedBase = ROUNDDOWN( 581 next->Base() + next->Size() - size, alignment); 582 583 foundSpot = true; 584 next->SetSize(alignedBase - next->Base()); 585 area->SetBase(alignedBase); 586 last = next; 587 break; 588 } 589 590 last = next; 591 } 592 } 593 break; 594 } 595 596 case B_BASE_ADDRESS: 597 { 598 // find a hole big enough for a new area beginning with "start" 599 if (last == NULL) { 600 // see if we can build it at the beginning of the specified 601 // start 602 if (next == NULL || next->Base() > start + (size - 1)) { 603 foundSpot = true; 604 area->SetBase(start); 605 break; 606 } 607 608 last = next; 609 next = it.Next(); 610 } 611 612 // keep walking 613 while (next != NULL) { 614 if (next->Base() - (last->Base() + last->Size()) >= size) { 615 // we found a spot (it'll be filled up below) 616 break; 617 } 618 619 last = next; 620 next = it.Next(); 621 } 622 623 addr_t lastEnd = last->Base() + (last->Size() - 1); 624 if (next != NULL || end - lastEnd >= size) { 625 // got a spot 626 foundSpot = true; 627 if (lastEnd < start) 628 area->SetBase(start); 629 else 630 area->SetBase(lastEnd + 1); 631 break; 632 } 633 634 // we didn't find a free spot in the requested range, so we'll 635 // try again without any restrictions 636 start = fBase; 637 addressSpec = B_ANY_ADDRESS; 638 last = NULL; 639 goto second_chance; 640 } 641 642 case B_EXACT_ADDRESS: 643 // see if we can create it exactly here 644 if ((last == NULL || last->Base() + (last->Size() - 1) < start) 645 && (next == NULL || next->Base() > start + (size - 1))) { 646 foundSpot = true; 647 area->SetBase(start); 648 break; 649 } 650 break; 651 default: 652 return B_BAD_VALUE; 653 } 654 655 if (!foundSpot) 656 return addressSpec == B_EXACT_ADDRESS ? B_BAD_VALUE : B_NO_MEMORY; 657 658 area->SetSize(size); 659 if (last) 660 fAreas.Insert(fAreas.GetNext(last), area); 661 else 662 fAreas.Insert(fAreas.Head(), area); 663 664 IncrementChangeCount(); 665 return B_OK; 666 } 667