1 /* 2 * Copyright 2009-2011, 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 "VMKernelAddressSpace.h" 12 13 #include <stdlib.h> 14 15 #include <KernelExport.h> 16 17 #include <heap.h> 18 #include <slab/Slab.h> 19 #include <thread.h> 20 #include <vm/vm.h> 21 #include <vm/VMArea.h> 22 23 24 //#define TRACE_VM 25 #ifdef TRACE_VM 26 # define TRACE(x...) dprintf(x) 27 #else 28 # define TRACE(x...) ; 29 #endif 30 31 32 //#define PARANOIA_CHECKS 33 #ifdef PARANOIA_CHECKS 34 # define PARANOIA_CHECK_STRUCTURES() _CheckStructures() 35 #else 36 # define PARANOIA_CHECK_STRUCTURES() do {} while (false) 37 #endif 38 39 40 static int 41 ld(size_t value) 42 { 43 int index = -1; 44 while (value > 0) { 45 value >>= 1; 46 index++; 47 } 48 49 return index; 50 } 51 52 53 /*! Verifies that an area with the given aligned base and size fits into 54 the spot defined by base and limit and checks for overflows. 55 \param base Minimum base address valid for the area. 56 \param alignedBase The base address of the range to check. 57 \param size The size of the area. 58 \param limit The last (inclusive) addresss of the range to check. 59 */ 60 static inline bool 61 is_valid_spot(addr_t base, addr_t alignedBase, addr_t size, addr_t limit) 62 { 63 return (alignedBase >= base && alignedBase + (size - 1) > alignedBase 64 && alignedBase + (size - 1) <= limit); 65 } 66 67 68 // #pragma mark - VMKernelAddressSpace 69 70 71 VMKernelAddressSpace::VMKernelAddressSpace(team_id id, addr_t base, size_t size) 72 : 73 VMAddressSpace(id, base, size, "kernel address space"), 74 fAreaObjectCache(NULL), 75 fRangesObjectCache(NULL) 76 { 77 } 78 79 80 VMKernelAddressSpace::~VMKernelAddressSpace() 81 { 82 panic("deleting the kernel aspace!\n"); 83 } 84 85 86 status_t 87 VMKernelAddressSpace::InitObject() 88 { 89 fAreaObjectCache = create_object_cache("kernel areas", 90 sizeof(VMKernelArea), 0, NULL, NULL, NULL); 91 if (fAreaObjectCache == NULL) 92 return B_NO_MEMORY; 93 94 fRangesObjectCache = create_object_cache("kernel address ranges", 95 sizeof(Range), 0, NULL, NULL, NULL); 96 if (fRangesObjectCache == NULL) 97 return B_NO_MEMORY; 98 99 // create the free lists 100 size_t size = fEndAddress - fBase + 1; 101 fFreeListCount = ld(size) - PAGE_SHIFT + 1; 102 fFreeLists = new(std::nothrow) RangeFreeList[fFreeListCount]; 103 if (fFreeLists == NULL) 104 return B_NO_MEMORY; 105 106 Range* range = new(fRangesObjectCache, 0) Range(fBase, size, 107 Range::RANGE_FREE); 108 if (range == NULL) 109 return B_NO_MEMORY; 110 111 _InsertRange(range); 112 113 TRACE("VMKernelAddressSpace::InitObject(): address range: %#" B_PRIxADDR 114 " - %#" B_PRIxADDR ", free lists: %d\n", fBase, fEndAddress, 115 fFreeListCount); 116 117 return B_OK; 118 } 119 120 121 inline VMArea* 122 VMKernelAddressSpace::FirstArea() const 123 { 124 Range* range = fRangeList.Head(); 125 while (range != NULL && range->type != Range::RANGE_AREA) 126 range = fRangeList.GetNext(range); 127 return range != NULL ? range->area : NULL; 128 } 129 130 131 inline VMArea* 132 VMKernelAddressSpace::NextArea(VMArea* _area) const 133 { 134 Range* range = static_cast<VMKernelArea*>(_area)->Range(); 135 do { 136 range = fRangeList.GetNext(range); 137 } while (range != NULL && range->type != Range::RANGE_AREA); 138 return range != NULL ? range->area : NULL; 139 } 140 141 142 VMArea* 143 VMKernelAddressSpace::CreateArea(const char* name, uint32 wiring, 144 uint32 protection, uint32 allocationFlags) 145 { 146 return VMKernelArea::Create(this, name, wiring, protection, 147 fAreaObjectCache, allocationFlags); 148 } 149 150 151 void 152 VMKernelAddressSpace::DeleteArea(VMArea* _area, uint32 allocationFlags) 153 { 154 TRACE("VMKernelAddressSpace::DeleteArea(%p)\n", _area); 155 156 VMKernelArea* area = static_cast<VMKernelArea*>(_area); 157 object_cache_delete(fAreaObjectCache, area); 158 } 159 160 161 //! You must hold the address space's read lock. 162 VMArea* 163 VMKernelAddressSpace::LookupArea(addr_t address) const 164 { 165 Range* range = fRangeTree.FindClosest(address, true); 166 if (range == NULL || range->type != Range::RANGE_AREA) 167 return NULL; 168 169 VMKernelArea* area = range->area; 170 return area->ContainsAddress(address) ? area : NULL; 171 } 172 173 174 /*! This inserts the area you pass into the address space. 175 It will also set the "_address" argument to its base address when 176 the call succeeds. 177 You need to hold the VMAddressSpace write lock. 178 */ 179 status_t 180 VMKernelAddressSpace::InsertArea(VMArea* _area, size_t size, 181 const virtual_address_restrictions* addressRestrictions, 182 uint32 allocationFlags, void** _address) 183 { 184 TRACE("VMKernelAddressSpace::InsertArea(%p, %" B_PRIu32 ", %#" B_PRIxSIZE 185 ", %p \"%s\")\n", addressRestrictions->address, 186 addressRestrictions->address_specification, size, _area, _area->name); 187 188 VMKernelArea* area = static_cast<VMKernelArea*>(_area); 189 190 Range* range; 191 status_t error = _AllocateRange(addressRestrictions, size, 192 addressRestrictions->address_specification == B_EXACT_ADDRESS, 193 allocationFlags, range); 194 if (error != B_OK) 195 return error; 196 197 range->type = Range::RANGE_AREA; 198 range->area = area; 199 area->SetRange(range); 200 area->SetBase(range->base); 201 area->SetSize(range->size); 202 203 if (_address != NULL) 204 *_address = (void*)area->Base(); 205 fFreeSpace -= area->Size(); 206 207 PARANOIA_CHECK_STRUCTURES(); 208 209 return B_OK; 210 } 211 212 213 //! You must hold the address space's write lock. 214 void 215 VMKernelAddressSpace::RemoveArea(VMArea* _area, uint32 allocationFlags) 216 { 217 TRACE("VMKernelAddressSpace::RemoveArea(%p)\n", _area); 218 219 VMKernelArea* area = static_cast<VMKernelArea*>(_area); 220 221 _FreeRange(area->Range(), allocationFlags); 222 223 fFreeSpace += area->Size(); 224 225 PARANOIA_CHECK_STRUCTURES(); 226 } 227 228 229 bool 230 VMKernelAddressSpace::CanResizeArea(VMArea* area, size_t newSize) 231 { 232 Range* range = static_cast<VMKernelArea*>(area)->Range(); 233 234 if (newSize <= range->size) 235 return true; 236 237 Range* nextRange = fRangeList.GetNext(range); 238 if (nextRange == NULL || nextRange->type == Range::RANGE_AREA) 239 return false; 240 241 if (nextRange->type == Range::RANGE_RESERVED 242 && nextRange->reserved.base > range->base) { 243 return false; 244 } 245 246 // TODO: If there is free space after a reserved range (or vice versa), it 247 // could be used as well. 248 return newSize - range->size <= nextRange->size; 249 } 250 251 252 status_t 253 VMKernelAddressSpace::ResizeArea(VMArea* _area, size_t newSize, 254 uint32 allocationFlags) 255 { 256 TRACE("VMKernelAddressSpace::ResizeArea(%p, %#" B_PRIxSIZE ")\n", _area, 257 newSize); 258 259 VMKernelArea* area = static_cast<VMKernelArea*>(_area); 260 Range* range = area->Range(); 261 262 if (newSize == range->size) 263 return B_OK; 264 265 Range* nextRange = fRangeList.GetNext(range); 266 267 if (newSize < range->size) { 268 if (nextRange != NULL && nextRange->type == Range::RANGE_FREE) { 269 // a free range is following -- just enlarge it 270 _FreeListRemoveRange(nextRange, nextRange->size); 271 nextRange->size += range->size - newSize; 272 nextRange->base = range->base + newSize; 273 _FreeListInsertRange(nextRange, nextRange->size); 274 } else { 275 // no free range following -- we need to allocate a new one and 276 // insert it 277 nextRange = new(fRangesObjectCache, allocationFlags) Range( 278 range->base + newSize, range->size - newSize, 279 Range::RANGE_FREE); 280 if (nextRange == NULL) 281 return B_NO_MEMORY; 282 _InsertRange(nextRange); 283 } 284 } else { 285 if (nextRange == NULL 286 || (nextRange->type == Range::RANGE_RESERVED 287 && nextRange->reserved.base > range->base)) { 288 return B_BAD_VALUE; 289 } 290 // TODO: If there is free space after a reserved range (or vice versa), 291 // it could be used as well. 292 size_t sizeDiff = newSize - range->size; 293 if (sizeDiff > nextRange->size) 294 return B_BAD_VALUE; 295 296 if (sizeDiff == nextRange->size) { 297 // The next range is completely covered -- remove and delete it. 298 _RemoveRange(nextRange); 299 object_cache_delete(fRangesObjectCache, nextRange, allocationFlags); 300 } else { 301 // The next range is only partially covered -- shrink it. 302 if (nextRange->type == Range::RANGE_FREE) 303 _FreeListRemoveRange(nextRange, nextRange->size); 304 nextRange->size -= sizeDiff; 305 nextRange->base = range->base + newSize; 306 if (nextRange->type == Range::RANGE_FREE) 307 _FreeListInsertRange(nextRange, nextRange->size); 308 } 309 } 310 311 range->size = newSize; 312 area->SetSize(newSize); 313 314 IncrementChangeCount(); 315 PARANOIA_CHECK_STRUCTURES(); 316 return B_OK; 317 } 318 319 320 status_t 321 VMKernelAddressSpace::ShrinkAreaHead(VMArea* _area, size_t newSize, 322 uint32 allocationFlags) 323 { 324 TRACE("VMKernelAddressSpace::ShrinkAreaHead(%p, %#" B_PRIxSIZE ")\n", _area, 325 newSize); 326 327 VMKernelArea* area = static_cast<VMKernelArea*>(_area); 328 Range* range = area->Range(); 329 330 if (newSize == range->size) 331 return B_OK; 332 333 if (newSize > range->size) 334 return B_BAD_VALUE; 335 336 Range* previousRange = fRangeList.GetPrevious(range); 337 338 size_t sizeDiff = range->size - newSize; 339 if (previousRange != NULL && previousRange->type == Range::RANGE_FREE) { 340 // the previous range is free -- just enlarge it 341 _FreeListRemoveRange(previousRange, previousRange->size); 342 previousRange->size += sizeDiff; 343 _FreeListInsertRange(previousRange, previousRange->size); 344 range->base += sizeDiff; 345 range->size = newSize; 346 } else { 347 // no free range before -- we need to allocate a new one and 348 // insert it 349 previousRange = new(fRangesObjectCache, allocationFlags) Range( 350 range->base, sizeDiff, Range::RANGE_FREE); 351 if (previousRange == NULL) 352 return B_NO_MEMORY; 353 range->base += sizeDiff; 354 range->size = newSize; 355 _InsertRange(previousRange); 356 } 357 358 area->SetBase(range->base); 359 area->SetSize(range->size); 360 361 IncrementChangeCount(); 362 PARANOIA_CHECK_STRUCTURES(); 363 return B_OK; 364 } 365 366 367 status_t 368 VMKernelAddressSpace::ShrinkAreaTail(VMArea* area, size_t newSize, 369 uint32 allocationFlags) 370 { 371 return ResizeArea(area, newSize, allocationFlags); 372 } 373 374 375 status_t 376 VMKernelAddressSpace::ReserveAddressRange(size_t size, 377 const virtual_address_restrictions* addressRestrictions, 378 uint32 flags, uint32 allocationFlags, void** _address) 379 { 380 TRACE("VMKernelAddressSpace::ReserveAddressRange(%p, %" B_PRIu32 ", %#" 381 B_PRIxSIZE ", %#" B_PRIx32 ")\n", addressRestrictions->address, 382 addressRestrictions->address_specification, size, flags); 383 384 // Don't allow range reservations, if the address space is about to be 385 // deleted. 386 if (fDeleting) 387 return B_BAD_TEAM_ID; 388 389 Range* range; 390 status_t error = _AllocateRange(addressRestrictions, size, false, 391 allocationFlags, range); 392 if (error != B_OK) 393 return error; 394 395 range->type = Range::RANGE_RESERVED; 396 range->reserved.base = range->base; 397 range->reserved.flags = flags; 398 399 if (_address != NULL) 400 *_address = (void*)range->base; 401 402 Get(); 403 PARANOIA_CHECK_STRUCTURES(); 404 return B_OK; 405 } 406 407 408 status_t 409 VMKernelAddressSpace::UnreserveAddressRange(addr_t address, size_t size, 410 uint32 allocationFlags) 411 { 412 TRACE("VMKernelAddressSpace::UnreserveAddressRange(%#" B_PRIxADDR ", %#" 413 B_PRIxSIZE ")\n", address, size); 414 415 // Don't allow range unreservations, if the address space is about to be 416 // deleted. UnreserveAllAddressRanges() must be used. 417 if (fDeleting) 418 return B_BAD_TEAM_ID; 419 420 // search range list and remove any matching reserved ranges 421 addr_t endAddress = address + (size - 1); 422 Range* range = fRangeTree.FindClosest(address, false); 423 while (range != NULL && range->base + (range->size - 1) <= endAddress) { 424 // Get the next range for the iteration -- we need to skip free ranges, 425 // since _FreeRange() might join them with the current range and delete 426 // them. 427 Range* nextRange = fRangeList.GetNext(range); 428 while (nextRange != NULL && nextRange->type == Range::RANGE_FREE) 429 nextRange = fRangeList.GetNext(nextRange); 430 431 if (range->type == Range::RANGE_RESERVED) { 432 _FreeRange(range, allocationFlags); 433 Put(); 434 } 435 436 range = nextRange; 437 } 438 439 PARANOIA_CHECK_STRUCTURES(); 440 return B_OK; 441 } 442 443 444 void 445 VMKernelAddressSpace::UnreserveAllAddressRanges(uint32 allocationFlags) 446 { 447 Range* range = fRangeList.Head(); 448 while (range != NULL) { 449 // Get the next range for the iteration -- we need to skip free ranges, 450 // since _FreeRange() might join them with the current range and delete 451 // them. 452 Range* nextRange = fRangeList.GetNext(range); 453 while (nextRange != NULL && nextRange->type == Range::RANGE_FREE) 454 nextRange = fRangeList.GetNext(nextRange); 455 456 if (range->type == Range::RANGE_RESERVED) { 457 _FreeRange(range, allocationFlags); 458 Put(); 459 } 460 461 range = nextRange; 462 } 463 464 PARANOIA_CHECK_STRUCTURES(); 465 } 466 467 468 void 469 VMKernelAddressSpace::Dump() const 470 { 471 VMAddressSpace::Dump(); 472 473 kprintf("area_list:\n"); 474 475 for (RangeList::ConstIterator it = fRangeList.GetIterator(); 476 Range* range = it.Next();) { 477 if (range->type != Range::RANGE_AREA) 478 continue; 479 480 VMKernelArea* area = range->area; 481 kprintf(" area %" B_PRId32 ": ", area->id); 482 kprintf("base_addr = %#" B_PRIxADDR " ", area->Base()); 483 kprintf("size = %#" B_PRIxSIZE " ", area->Size()); 484 kprintf("name = '%s' ", area->name); 485 kprintf("protection = %#" B_PRIx32 "\n", area->protection); 486 } 487 } 488 489 490 inline void 491 VMKernelAddressSpace::_FreeListInsertRange(Range* range, size_t size) 492 { 493 TRACE(" VMKernelAddressSpace::_FreeListInsertRange(%p (%#" B_PRIxADDR 494 ", %#" B_PRIxSIZE ", %d), %#" B_PRIxSIZE " (%d))\n", range, range->base, 495 range->size, range->type, size, ld(size) - PAGE_SHIFT); 496 497 fFreeLists[ld(size) - PAGE_SHIFT].Add(range); 498 } 499 500 501 inline void 502 VMKernelAddressSpace::_FreeListRemoveRange(Range* range, size_t size) 503 { 504 TRACE(" VMKernelAddressSpace::_FreeListRemoveRange(%p (%#" B_PRIxADDR 505 ", %#" B_PRIxSIZE ", %d), %#" B_PRIxSIZE " (%d))\n", range, range->base, 506 range->size, range->type, size, ld(size) - PAGE_SHIFT); 507 508 fFreeLists[ld(size) - PAGE_SHIFT].Remove(range); 509 } 510 511 512 void 513 VMKernelAddressSpace::_InsertRange(Range* range) 514 { 515 TRACE(" VMKernelAddressSpace::_InsertRange(%p (%#" B_PRIxADDR ", %#" 516 B_PRIxSIZE ", %d))\n", range, range->base, range->size, range->type); 517 518 // insert at the correct position in the range list 519 Range* insertBeforeRange = fRangeTree.FindClosest(range->base, true); 520 fRangeList.Insert( 521 insertBeforeRange != NULL 522 ? fRangeList.GetNext(insertBeforeRange) : fRangeList.Head(), 523 range); 524 525 // insert into tree 526 fRangeTree.Insert(range); 527 528 // insert in the free ranges list, if the range is free 529 if (range->type == Range::RANGE_FREE) 530 _FreeListInsertRange(range, range->size); 531 } 532 533 534 void 535 VMKernelAddressSpace::_RemoveRange(Range* range) 536 { 537 TRACE(" VMKernelAddressSpace::_RemoveRange(%p (%#" B_PRIxADDR ", %#" 538 B_PRIxSIZE ", %d))\n", range, range->base, range->size, range->type); 539 540 // remove from tree and range list 541 // insert at the correct position in the range list 542 fRangeTree.Remove(range); 543 fRangeList.Remove(range); 544 545 // if it is a free range, also remove it from the free list 546 if (range->type == Range::RANGE_FREE) 547 _FreeListRemoveRange(range, range->size); 548 } 549 550 551 status_t 552 VMKernelAddressSpace::_AllocateRange( 553 const virtual_address_restrictions* addressRestrictions, 554 size_t size, bool allowReservedRange, uint32 allocationFlags, 555 Range*& _range) 556 { 557 TRACE(" VMKernelAddressSpace::_AllocateRange(address: %p, size: %#" 558 B_PRIxSIZE ", addressSpec: %#" B_PRIx32 ", reserved allowed: %d)\n", 559 addressRestrictions->address, size, 560 addressRestrictions->address_specification, allowReservedRange); 561 562 // prepare size, alignment and the base address for the range search 563 addr_t address = (addr_t)addressRestrictions->address; 564 size = ROUNDUP(size, B_PAGE_SIZE); 565 size_t alignment = addressRestrictions->alignment != 0 566 ? addressRestrictions->alignment : B_PAGE_SIZE; 567 568 switch (addressRestrictions->address_specification) { 569 case B_EXACT_ADDRESS: 570 { 571 if (address % B_PAGE_SIZE != 0) 572 return B_BAD_VALUE; 573 break; 574 } 575 576 case B_BASE_ADDRESS: 577 address = ROUNDUP(address, B_PAGE_SIZE); 578 break; 579 580 case B_ANY_KERNEL_BLOCK_ADDRESS: 581 // align the memory to the next power of two of the size 582 while (alignment < size) 583 alignment <<= 1; 584 585 // fall through... 586 587 case B_ANY_ADDRESS: 588 case B_ANY_KERNEL_ADDRESS: 589 address = fBase; 590 // TODO: remove this again when vm86 mode is moved into the kernel 591 // completely (currently needs a userland address space!) 592 if (address == USER_BASE) 593 address = USER_BASE_ANY; 594 break; 595 596 default: 597 return B_BAD_VALUE; 598 } 599 600 // find a range 601 Range* range = _FindFreeRange(address, size, alignment, 602 addressRestrictions->address_specification, allowReservedRange, 603 address); 604 if (range == NULL) { 605 return addressRestrictions->address_specification == B_EXACT_ADDRESS 606 ? B_BAD_VALUE : B_NO_MEMORY; 607 } 608 609 TRACE(" VMKernelAddressSpace::_AllocateRange() found range:(%p (%#" 610 B_PRIxADDR ", %#" B_PRIxSIZE ", %d)\n", range, range->base, range->size, 611 range->type); 612 613 // We have found a range. It might not be a perfect fit, in which case 614 // we have to split the range. 615 size_t rangeSize = range->size; 616 617 if (address == range->base) { 618 // allocation at the beginning of the range 619 if (range->size > size) { 620 // only partial -- split the range 621 Range* leftOverRange = new(fRangesObjectCache, allocationFlags) 622 Range(address + size, range->size - size, range); 623 if (leftOverRange == NULL) 624 return B_NO_MEMORY; 625 626 range->size = size; 627 _InsertRange(leftOverRange); 628 } 629 } else if (address + size == range->base + range->size) { 630 // allocation at the end of the range -- split the range 631 Range* leftOverRange = new(fRangesObjectCache, allocationFlags) Range( 632 range->base, range->size - size, range); 633 if (leftOverRange == NULL) 634 return B_NO_MEMORY; 635 636 range->base = address; 637 range->size = size; 638 _InsertRange(leftOverRange); 639 } else { 640 // allocation in the middle of the range -- split the range in three 641 Range* leftOverRange1 = new(fRangesObjectCache, allocationFlags) Range( 642 range->base, address - range->base, range); 643 if (leftOverRange1 == NULL) 644 return B_NO_MEMORY; 645 Range* leftOverRange2 = new(fRangesObjectCache, allocationFlags) Range( 646 address + size, range->size - size - leftOverRange1->size, range); 647 if (leftOverRange2 == NULL) { 648 object_cache_delete(fRangesObjectCache, leftOverRange1, 649 allocationFlags); 650 return B_NO_MEMORY; 651 } 652 653 range->base = address; 654 range->size = size; 655 _InsertRange(leftOverRange1); 656 _InsertRange(leftOverRange2); 657 } 658 659 // If the range is a free range, remove it from the respective free list. 660 if (range->type == Range::RANGE_FREE) 661 _FreeListRemoveRange(range, rangeSize); 662 663 IncrementChangeCount(); 664 665 TRACE(" VMKernelAddressSpace::_AllocateRange() -> %p (%#" B_PRIxADDR ", %#" 666 B_PRIxSIZE ")\n", range, range->base, range->size); 667 668 _range = range; 669 return B_OK; 670 } 671 672 673 VMKernelAddressSpace::Range* 674 VMKernelAddressSpace::_FindFreeRange(addr_t start, size_t size, 675 size_t alignment, uint32 addressSpec, bool allowReservedRange, 676 addr_t& _foundAddress) 677 { 678 TRACE(" VMKernelAddressSpace::_FindFreeRange(start: %#" B_PRIxADDR 679 ", size: %#" B_PRIxSIZE ", alignment: %#" B_PRIxSIZE ", addressSpec: %#" 680 B_PRIx32 ", reserved allowed: %d)\n", start, size, alignment, 681 addressSpec, allowReservedRange); 682 683 switch (addressSpec) { 684 case B_BASE_ADDRESS: 685 { 686 // We have to iterate through the range list starting at the given 687 // address. This is the most inefficient case. 688 Range* range = fRangeTree.FindClosest(start, true); 689 while (range != NULL) { 690 if (range->type == Range::RANGE_FREE) { 691 addr_t alignedBase = ROUNDUP(range->base, alignment); 692 if (is_valid_spot(start, alignedBase, size, 693 range->base + (range->size - 1))) { 694 _foundAddress = alignedBase; 695 return range; 696 } 697 } 698 range = fRangeList.GetNext(range); 699 } 700 701 // We didn't find a free spot in the requested range, so we'll 702 // try again without any restrictions. 703 start = fBase; 704 addressSpec = B_ANY_ADDRESS; 705 // fall through... 706 } 707 708 case B_ANY_ADDRESS: 709 case B_ANY_KERNEL_ADDRESS: 710 case B_ANY_KERNEL_BLOCK_ADDRESS: 711 { 712 // We want to allocate from the first non-empty free list that is 713 // guaranteed to contain the size. Finding a free range is O(1), 714 // unless there are constraints (min base address, alignment). 715 int freeListIndex = ld((size * 2 - 1) >> PAGE_SHIFT); 716 717 for (int32 i = freeListIndex; i < fFreeListCount; i++) { 718 RangeFreeList& freeList = fFreeLists[i]; 719 if (freeList.IsEmpty()) 720 continue; 721 722 for (RangeFreeList::Iterator it = freeList.GetIterator(); 723 Range* range = it.Next();) { 724 addr_t alignedBase = ROUNDUP(range->base, alignment); 725 if (is_valid_spot(start, alignedBase, size, 726 range->base + (range->size - 1))) { 727 _foundAddress = alignedBase; 728 return range; 729 } 730 } 731 } 732 733 if (!allowReservedRange) 734 return NULL; 735 736 // We haven't found any free ranges, but we're supposed to look 737 // for reserved ones, too. Iterate through the range list starting 738 // at the given address. 739 Range* range = fRangeTree.FindClosest(start, true); 740 while (range != NULL) { 741 if (range->type == Range::RANGE_RESERVED) { 742 addr_t alignedBase = ROUNDUP(range->base, alignment); 743 if (is_valid_spot(start, alignedBase, size, 744 range->base + (range->size - 1))) { 745 // allocation from the back might be preferred 746 // -- adjust the base accordingly 747 if ((range->reserved.flags & RESERVED_AVOID_BASE) 748 != 0) { 749 alignedBase = ROUNDDOWN( 750 range->base + (range->size - size), alignment); 751 } 752 753 _foundAddress = alignedBase; 754 return range; 755 } 756 } 757 range = fRangeList.GetNext(range); 758 } 759 760 return NULL; 761 } 762 763 case B_EXACT_ADDRESS: 764 { 765 Range* range = fRangeTree.FindClosest(start, true); 766 TRACE(" B_EXACT_ADDRESS: range: %p\n", range); 767 if (range == NULL || range->type == Range::RANGE_AREA 768 || range->base + (range->size - 1) < start + (size - 1)) { 769 // TODO: Support allocating if the area range covers multiple 770 // free and reserved ranges! 771 TRACE(" -> no suitable range\n"); 772 return NULL; 773 } 774 775 if (range->type != Range::RANGE_FREE && !allowReservedRange) 776 { 777 TRACE(" -> reserved range not allowed\n"); 778 return NULL; 779 } 780 781 _foundAddress = start; 782 return range; 783 } 784 785 default: 786 return NULL; 787 } 788 } 789 790 791 void 792 VMKernelAddressSpace::_FreeRange(Range* range, uint32 allocationFlags) 793 { 794 TRACE(" VMKernelAddressSpace::_FreeRange(%p (%#" B_PRIxADDR ", %#" 795 B_PRIxSIZE ", %d))\n", range, range->base, range->size, range->type); 796 797 // Check whether one or both of the neighboring ranges are free already, 798 // and join them, if so. 799 Range* previousRange = fRangeList.GetPrevious(range); 800 Range* nextRange = fRangeList.GetNext(range); 801 802 if (previousRange != NULL && previousRange->type == Range::RANGE_FREE) { 803 if (nextRange != NULL && nextRange->type == Range::RANGE_FREE) { 804 // join them all -- keep the first one, delete the others 805 _FreeListRemoveRange(previousRange, previousRange->size); 806 _RemoveRange(range); 807 _RemoveRange(nextRange); 808 previousRange->size += range->size + nextRange->size; 809 object_cache_delete(fRangesObjectCache, range, allocationFlags); 810 object_cache_delete(fRangesObjectCache, nextRange, allocationFlags); 811 _FreeListInsertRange(previousRange, previousRange->size); 812 } else { 813 // join with the previous range only, delete the supplied one 814 _FreeListRemoveRange(previousRange, previousRange->size); 815 _RemoveRange(range); 816 previousRange->size += range->size; 817 object_cache_delete(fRangesObjectCache, range, allocationFlags); 818 _FreeListInsertRange(previousRange, previousRange->size); 819 } 820 } else { 821 if (nextRange != NULL && nextRange->type == Range::RANGE_FREE) { 822 // join with the next range and delete it 823 _RemoveRange(nextRange); 824 range->size += nextRange->size; 825 object_cache_delete(fRangesObjectCache, nextRange, allocationFlags); 826 } 827 828 // mark the range free and add it to the respective free list 829 range->type = Range::RANGE_FREE; 830 _FreeListInsertRange(range, range->size); 831 } 832 833 IncrementChangeCount(); 834 } 835 836 837 #ifdef PARANOIA_CHECKS 838 839 void 840 VMKernelAddressSpace::_CheckStructures() const 841 { 842 // general tree structure check 843 fRangeTree.CheckTree(); 844 845 // check range list and tree 846 size_t spaceSize = fEndAddress - fBase + 1; 847 addr_t nextBase = fBase; 848 Range* previousRange = NULL; 849 int previousRangeType = Range::RANGE_AREA; 850 uint64 freeRanges = 0; 851 852 RangeList::ConstIterator listIt = fRangeList.GetIterator(); 853 RangeTree::ConstIterator treeIt = fRangeTree.GetIterator(); 854 while (true) { 855 Range* range = listIt.Next(); 856 Range* treeRange = treeIt.Next(); 857 if (range != treeRange) { 858 panic("VMKernelAddressSpace::_CheckStructures(): list/tree range " 859 "mismatch: %p vs %p", range, treeRange); 860 } 861 if (range == NULL) 862 break; 863 864 if (range->base != nextBase) { 865 panic("VMKernelAddressSpace::_CheckStructures(): range base %#" 866 B_PRIxADDR ", expected: %#" B_PRIxADDR, range->base, nextBase); 867 } 868 869 if (range->size == 0) { 870 panic("VMKernelAddressSpace::_CheckStructures(): empty range %p", 871 range); 872 } 873 874 if (range->size % B_PAGE_SIZE != 0) { 875 panic("VMKernelAddressSpace::_CheckStructures(): range %p (%#" 876 B_PRIxADDR ", %#" B_PRIxSIZE ") not page aligned", range, 877 range->base, range->size); 878 } 879 880 if (range->size > spaceSize - (range->base - fBase)) { 881 panic("VMKernelAddressSpace::_CheckStructures(): range too large: " 882 "(%#" B_PRIxADDR ", %#" B_PRIxSIZE "), address space end: %#" 883 B_PRIxADDR, range->base, range->size, fEndAddress); 884 } 885 886 if (range->type == Range::RANGE_FREE) { 887 freeRanges++; 888 889 if (previousRangeType == Range::RANGE_FREE) { 890 panic("VMKernelAddressSpace::_CheckStructures(): adjoining " 891 "free ranges: %p (%#" B_PRIxADDR ", %#" B_PRIxSIZE 892 "), %p (%#" B_PRIxADDR ", %#" B_PRIxSIZE ")", previousRange, 893 previousRange->base, previousRange->size, range, 894 range->base, range->size); 895 } 896 } 897 898 previousRange = range; 899 nextBase = range->base + range->size; 900 previousRangeType = range->type; 901 } 902 903 if (nextBase - 1 != fEndAddress) { 904 panic("VMKernelAddressSpace::_CheckStructures(): space not fully " 905 "covered by ranges: last: %#" B_PRIxADDR ", expected %#" B_PRIxADDR, 906 nextBase - 1, fEndAddress); 907 } 908 909 // check free lists 910 uint64 freeListRanges = 0; 911 for (int i = 0; i < fFreeListCount; i++) { 912 RangeFreeList& freeList = fFreeLists[i]; 913 if (freeList.IsEmpty()) 914 continue; 915 916 for (RangeFreeList::Iterator it = freeList.GetIterator(); 917 Range* range = it.Next();) { 918 if (range->type != Range::RANGE_FREE) { 919 panic("VMKernelAddressSpace::_CheckStructures(): non-free " 920 "range %p (%#" B_PRIxADDR ", %#" B_PRIxSIZE ", %d) in " 921 "free list %d", range, range->base, range->size, 922 range->type, i); 923 } 924 925 if (fRangeTree.Find(range->base) != range) { 926 panic("VMKernelAddressSpace::_CheckStructures(): unknown " 927 "range %p (%#" B_PRIxADDR ", %#" B_PRIxSIZE ", %d) in " 928 "free list %d", range, range->base, range->size, 929 range->type, i); 930 } 931 932 if (ld(range->size) - PAGE_SHIFT != i) { 933 panic("VMKernelAddressSpace::_CheckStructures(): " 934 "range %p (%#" B_PRIxADDR ", %#" B_PRIxSIZE ", %d) in " 935 "wrong free list %d", range, range->base, range->size, 936 range->type, i); 937 } 938 939 freeListRanges++; 940 } 941 } 942 } 943 944 #endif // PARANOIA_CHECKS 945