src/system/kernel/vm/VMKernelAddressSpace.cpp

   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