1// Copyright 2016 The Fuchsia Authors 2// 3// Use of this source code is governed by a MIT-style 4// license that can be found in the LICENSE file or at 5// https://opensource.org/licenses/MIT 6 7#include <vm/vm_address_region.h> 8 9#include "vm_priv.h" 10#include <assert.h> 11#include <err.h> 12#include <fbl/alloc_checker.h> 13#include <inttypes.h> 14#include <lib/vdso.h> 15#include <pow2.h> 16#include <trace.h> 17#include <vm/vm.h> 18#include <vm/vm_aspace.h> 19#include <vm/vm_object.h> 20#include <zircon/types.h> 21 22#define LOCAL_TRACE MAX(VM_GLOBAL_TRACE, 0) 23 24VmAddressRegion::VmAddressRegion(VmAspace& aspace, vaddr_t base, size_t size, uint32_t vmar_flags) 25 : VmAddressRegionOrMapping(base, size, vmar_flags | VMAR_CAN_RWX_FLAGS, 26 &aspace, nullptr) { 27 28 // We add in CAN_RWX_FLAGS above, since an address space can't usefully 29 // contain a process without all of these. 30 31 strlcpy(const_cast<char*>(name_), "root", sizeof(name_)); 32 LTRACEF("%p '%s'\n", this, name_); 33} 34 35VmAddressRegion::VmAddressRegion(VmAddressRegion& parent, vaddr_t base, size_t size, 36 uint32_t vmar_flags, const char* name) 37 : VmAddressRegionOrMapping(base, size, vmar_flags, parent.aspace_.get(), 38 &parent) { 39 40 strlcpy(const_cast<char*>(name_), name, sizeof(name_)); 41 LTRACEF("%p '%s'\n", this, name_); 42} 43 44VmAddressRegion::VmAddressRegion(VmAspace& kernel_aspace) 45 : VmAddressRegion(kernel_aspace, kernel_aspace.base(), kernel_aspace.size(), 46 VMAR_FLAG_CAN_MAP_SPECIFIC) { 47 48 // Activate the kernel root aspace immediately 49 state_ = LifeCycleState::ALIVE; 50} 51 52VmAddressRegion::VmAddressRegion() 53 : VmAddressRegionOrMapping(0, 0, 0, nullptr, nullptr) { 54 55 strlcpy(const_cast<char*>(name_), "dummy", sizeof(name_)); 56 LTRACEF("%p '%s'\n", this, name_); 57} 58 59zx_status_t VmAddressRegion::CreateRoot(VmAspace& aspace, uint32_t vmar_flags, 60 fbl::RefPtr<VmAddressRegion>* out) { 61 DEBUG_ASSERT(out); 62 63 fbl::AllocChecker ac; 64 auto vmar = new (&ac) VmAddressRegion(aspace, aspace.base(), aspace.size(), vmar_flags); 65 if (!ac.check()) { 66 return ZX_ERR_NO_MEMORY; 67 } 68 69 vmar->state_ = LifeCycleState::ALIVE; 70 *out = fbl::AdoptRef(vmar); 71 return ZX_OK; 72} 73 74zx_status_t VmAddressRegion::CreateSubVmarInternal(size_t offset, size_t size, uint8_t align_pow2, 75 uint32_t vmar_flags, fbl::RefPtr<VmObject> vmo, 76 uint64_t vmo_offset, uint arch_mmu_flags, 77 const char* name, 78 fbl::RefPtr<VmAddressRegionOrMapping>* out) { 79 DEBUG_ASSERT(out); 80 81 Guard<fbl::Mutex> guard{aspace_->lock()}; 82 if (state_ != LifeCycleState::ALIVE) { 83 return ZX_ERR_BAD_STATE; 84 } 85 86 if (size == 0) { 87 return ZX_ERR_INVALID_ARGS; 88 } 89 90 // Check if there are any RWX privileges that the child would have that the 91 // parent does not. 92 if (vmar_flags & ~flags_ & VMAR_CAN_RWX_FLAGS) { 93 return ZX_ERR_ACCESS_DENIED; 94 } 95 96 bool is_specific_overwrite = static_cast<bool>(vmar_flags & VMAR_FLAG_SPECIFIC_OVERWRITE); 97 bool is_specific = static_cast<bool>(vmar_flags & VMAR_FLAG_SPECIFIC) || is_specific_overwrite; 98 if (!is_specific && offset != 0) { 99 return ZX_ERR_INVALID_ARGS; 100 } 101 102 // Check to see if a cache policy exists if a VMO is passed in. VMOs that do not support 103 // cache policy return ERR_UNSUPPORTED, anything aside from that and ZX_OK is an error. 104 if (vmo) { 105 uint32_t cache_policy; 106 zx_status_t status = vmo->GetMappingCachePolicy(&cache_policy); 107 if (status == ZX_OK) { 108 // Warn in the event that we somehow receive a VMO that has a cache 109 // policy set while also holding cache policy flags within the arch 110 // flags. The only path that should be able to achieve this is if 111 // something in the kernel maps into their aspace incorrectly. 112 if ((arch_mmu_flags & ARCH_MMU_FLAG_CACHE_MASK) != 0 && 113 (arch_mmu_flags & ARCH_MMU_FLAG_CACHE_MASK) != cache_policy) { 114 TRACEF("warning: mapping %s has conflicting cache policies: vmo %02x " 115 "arch_mmu_flags %02x.\n", 116 name, cache_policy, arch_mmu_flags & ARCH_MMU_FLAG_CACHE_MASK); 117 } 118 arch_mmu_flags |= cache_policy; 119 } else if (status != ZX_ERR_NOT_SUPPORTED) { 120 return ZX_ERR_INVALID_ARGS; 121 } 122 } 123 124 // Check that we have the required privileges if we want a SPECIFIC mapping 125 if (is_specific && !(flags_ & VMAR_FLAG_CAN_MAP_SPECIFIC)) { 126 return ZX_ERR_ACCESS_DENIED; 127 } 128 129 if (offset >= size_ || size > size_ - offset) { 130 return ZX_ERR_INVALID_ARGS; 131 } 132 133 vaddr_t new_base = -1; 134 if (is_specific) { 135 new_base = base_ + offset; 136 if (!IS_PAGE_ALIGNED(new_base)) { 137 return ZX_ERR_INVALID_ARGS; 138 } 139 if (align_pow2 > 0 && (new_base & ((1ULL << align_pow2) - 1))) { 140 return ZX_ERR_INVALID_ARGS; 141 } 142 if (!IsRangeAvailableLocked(new_base, size)) { 143 if (is_specific_overwrite) { 144 return OverwriteVmMapping(new_base, size, vmar_flags, 145 vmo, vmo_offset, arch_mmu_flags, out); 146 } 147 return ZX_ERR_NO_MEMORY; 148 } 149 } else { 150 // If we're not mapping to a specific place, search for an opening. 151 zx_status_t status = AllocSpotLocked(size, align_pow2, arch_mmu_flags, &new_base); 152 if (status != ZX_OK) { 153 return status; 154 } 155 } 156 157 // Notice if this is an executable mapping from the vDSO VMO 158 // before we lose the VMO reference via fbl::move(vmo). 159 const bool is_vdso_code = (vmo && 160 (arch_mmu_flags & ARCH_MMU_FLAG_PERM_EXECUTE) && 161 VDso::vmo_is_vdso(vmo)); 162 163 fbl::AllocChecker ac; 164 fbl::RefPtr<VmAddressRegionOrMapping> vmar; 165 if (vmo) { 166 vmar = fbl::AdoptRef(new (&ac) 167 VmMapping(*this, new_base, size, vmar_flags, 168 fbl::move(vmo), vmo_offset, arch_mmu_flags)); 169 } else { 170 vmar = fbl::AdoptRef(new (&ac) 171 VmAddressRegion(*this, new_base, size, vmar_flags, name)); 172 } 173 174 if (!ac.check()) { 175 return ZX_ERR_NO_MEMORY; 176 } 177 178 if (is_vdso_code) { 179 // For an executable mapping of the vDSO, allow only one per process 180 // and only for the valid range of the image. 181 if (aspace_->vdso_code_mapping_ || 182 !VDso::valid_code_mapping(vmo_offset, size)) { 183 return ZX_ERR_ACCESS_DENIED; 184 } 185 aspace_->vdso_code_mapping_ = fbl::RefPtr<VmMapping>::Downcast(vmar); 186 } 187 188 vmar->Activate(); 189 *out = fbl::move(vmar); 190 return ZX_OK; 191} 192 193zx_status_t VmAddressRegion::CreateSubVmar(size_t offset, size_t size, uint8_t align_pow2, 194 uint32_t vmar_flags, const char* name, 195 fbl::RefPtr<VmAddressRegion>* out) { 196 DEBUG_ASSERT(out); 197 198 if (!IS_PAGE_ALIGNED(size)) { 199 return ZX_ERR_INVALID_ARGS; 200 } 201 202 // Check that only allowed flags have been set 203 if (vmar_flags & ~(VMAR_FLAG_SPECIFIC | VMAR_FLAG_CAN_MAP_SPECIFIC | VMAR_FLAG_COMPACT | VMAR_CAN_RWX_FLAGS)) { 204 return ZX_ERR_INVALID_ARGS; 205 } 206 207 fbl::RefPtr<VmAddressRegionOrMapping> res; 208 zx_status_t status = CreateSubVmarInternal(offset, size, align_pow2, vmar_flags, nullptr, 0, 209 ARCH_MMU_FLAG_INVALID, name, &res); 210 if (status != ZX_OK) { 211 return status; 212 } 213 // TODO(teisenbe): optimize this 214 *out = res->as_vm_address_region(); 215 return ZX_OK; 216} 217 218zx_status_t VmAddressRegion::CreateVmMapping(size_t mapping_offset, size_t size, uint8_t align_pow2, 219 uint32_t vmar_flags, fbl::RefPtr<VmObject> vmo, 220 uint64_t vmo_offset, uint arch_mmu_flags, const char* name, 221 fbl::RefPtr<VmMapping>* out) { 222 DEBUG_ASSERT(out); 223 LTRACEF("%p %#zx %#zx %x\n", this, mapping_offset, size, vmar_flags); 224 225 // Check that only allowed flags have been set 226 if (vmar_flags & ~(VMAR_FLAG_SPECIFIC | VMAR_FLAG_SPECIFIC_OVERWRITE | VMAR_CAN_RWX_FLAGS)) { 227 return ZX_ERR_INVALID_ARGS; 228 } 229 230 // Validate that arch_mmu_flags does not contain any prohibited flags 231 if (!is_valid_mapping_flags(arch_mmu_flags)) { 232 return ZX_ERR_ACCESS_DENIED; 233 } 234 235 // If size overflows, it'll become 0 and get rejected in 236 // CreateSubVmarInternal. 237 size = ROUNDUP(size, PAGE_SIZE); 238 239 // Make sure that vmo_offset is aligned and that a mapping of this size 240 // wouldn't overflow the vmo offset. 241 if (!IS_PAGE_ALIGNED(vmo_offset) || vmo_offset + size < vmo_offset) { 242 return ZX_ERR_INVALID_ARGS; 243 } 244 245 // If we're mapping it with a specific permission, we should allow 246 // future Protect() calls on the mapping to keep that permission. 247 if (arch_mmu_flags & ARCH_MMU_FLAG_PERM_READ) { 248 vmar_flags |= VMAR_FLAG_CAN_MAP_READ; 249 } 250 if (arch_mmu_flags & ARCH_MMU_FLAG_PERM_WRITE) { 251 vmar_flags |= VMAR_FLAG_CAN_MAP_WRITE; 252 } 253 if (arch_mmu_flags & ARCH_MMU_FLAG_PERM_EXECUTE) { 254 vmar_flags |= VMAR_FLAG_CAN_MAP_EXECUTE; 255 } 256 257 fbl::RefPtr<VmAddressRegionOrMapping> res; 258 zx_status_t status = 259 CreateSubVmarInternal(mapping_offset, size, align_pow2, vmar_flags, fbl::move(vmo), 260 vmo_offset, arch_mmu_flags, name, &res); 261 if (status != ZX_OK) { 262 return status; 263 } 264 // TODO(teisenbe): optimize this 265 *out = res->as_vm_mapping(); 266 return ZX_OK; 267} 268 269zx_status_t VmAddressRegion::OverwriteVmMapping( 270 vaddr_t base, size_t size, uint32_t vmar_flags, 271 fbl::RefPtr<VmObject> vmo, uint64_t vmo_offset, 272 uint arch_mmu_flags, fbl::RefPtr<VmAddressRegionOrMapping>* out) { 273 274 canary_.Assert(); 275 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 276 DEBUG_ASSERT(vmo); 277 DEBUG_ASSERT(vmar_flags & VMAR_FLAG_SPECIFIC_OVERWRITE); 278 279 fbl::AllocChecker ac; 280 fbl::RefPtr<VmAddressRegionOrMapping> vmar; 281 vmar = fbl::AdoptRef(new (&ac) 282 VmMapping(*this, base, size, vmar_flags, 283 fbl::move(vmo), vmo_offset, arch_mmu_flags)); 284 if (!ac.check()) { 285 return ZX_ERR_NO_MEMORY; 286 } 287 288 zx_status_t status = UnmapInternalLocked(base, size, false /* can_destroy_regions */, 289 false /* allow_partial_vmar */); 290 if (status != ZX_OK) { 291 return status; 292 } 293 294 vmar->Activate(); 295 *out = fbl::move(vmar); 296 return ZX_OK; 297} 298 299zx_status_t VmAddressRegion::DestroyLocked() { 300 canary_.Assert(); 301 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 302 LTRACEF("%p '%s'\n", this, name_); 303 304 // The cur reference prevents regions from being destructed after dropping 305 // the last reference to them when removing from their parent. 306 fbl::RefPtr<VmAddressRegion> cur(this); 307 while (cur) { 308 // Iterate through children destroying mappings. If we find a 309 // subregion, stop so we can traverse down. 310 fbl::RefPtr<VmAddressRegion> child_region = nullptr; 311 while (!cur->subregions_.is_empty() && !child_region) { 312 VmAddressRegionOrMapping* child = &cur->subregions_.front(); 313 if (child->is_mapping()) { 314 // DestroyLocked should remove this child from our list on success. 315 zx_status_t status = child->DestroyLocked(); 316 if (status != ZX_OK) { 317 // TODO(teisenbe): Do we want to handle this case differently? 318 return status; 319 } 320 } else { 321 child_region = child->as_vm_address_region(); 322 } 323 } 324 325 if (child_region) { 326 // If we found a child region, traverse down the tree. 327 cur = child_region; 328 } else { 329 // All children are destroyed, so now destroy the current node. 330 if (cur->parent_) { 331 DEBUG_ASSERT(cur->subregion_list_node_.InContainer()); 332 cur->parent_->RemoveSubregion(cur.get()); 333 } 334 cur->state_ = LifeCycleState::DEAD; 335 VmAddressRegion* cur_parent = cur->parent_; 336 cur->parent_ = nullptr; 337 338 // If we destroyed the original node, stop. Otherwise traverse 339 // up the tree and keep destroying. 340 cur.reset((cur.get() == this) ? nullptr : cur_parent); 341 } 342 } 343 return ZX_OK; 344} 345 346void VmAddressRegion::RemoveSubregion(VmAddressRegionOrMapping* region) { 347 subregions_.erase(*region); 348} 349 350fbl::RefPtr<VmAddressRegionOrMapping> VmAddressRegion::FindRegion(vaddr_t addr) { 351 Guard<fbl::Mutex> guard{aspace_->lock()}; 352 if (state_ != LifeCycleState::ALIVE) { 353 return nullptr; 354 } 355 return FindRegionLocked(addr); 356} 357 358fbl::RefPtr<VmAddressRegionOrMapping> VmAddressRegion::FindRegionLocked(vaddr_t addr) { 359 canary_.Assert(); 360 361 // Find the first region with a base greather than *addr*. If a region 362 // exists for *addr*, it will be immediately before it. 363 auto itr = --subregions_.upper_bound(addr); 364 if (!itr.IsValid() || itr->base() > addr || addr > itr->base() + itr->size() - 1) { 365 return nullptr; 366 } 367 368 return itr.CopyPointer(); 369} 370 371size_t VmAddressRegion::AllocatedPagesLocked() const { 372 canary_.Assert(); 373 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 374 375 if (state_ != LifeCycleState::ALIVE) { 376 return 0; 377 } 378 379 size_t sum = 0; 380 for (const auto& child : subregions_) { 381 sum += child.AllocatedPagesLocked(); 382 } 383 return sum; 384} 385 386zx_status_t VmAddressRegion::PageFault(vaddr_t va, uint pf_flags) { 387 canary_.Assert(); 388 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 389 390 auto vmar = WrapRefPtr(this); 391 while (auto next = vmar->FindRegionLocked(va)) { 392 if (next->is_mapping()) { 393 return next->PageFault(va, pf_flags); 394 } 395 vmar = next->as_vm_address_region(); 396 } 397 398 return ZX_ERR_NOT_FOUND; 399} 400 401bool VmAddressRegion::IsRangeAvailableLocked(vaddr_t base, size_t size) { 402 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 403 DEBUG_ASSERT(size > 0); 404 405 // Find the first region with base > *base*. Since subregions_ has no 406 // overlapping elements, we just need to check this one and the prior 407 // child. 408 409 auto prev = subregions_.upper_bound(base); 410 auto next = prev--; 411 412 if (prev.IsValid()) { 413 vaddr_t prev_last_byte; 414 if (add_overflow(prev->base(), prev->size() - 1, &prev_last_byte)) { 415 return false; 416 } 417 if (prev_last_byte >= base) { 418 return false; 419 } 420 } 421 422 if (next.IsValid() && next != subregions_.end()) { 423 vaddr_t last_byte; 424 if (add_overflow(base, size - 1, &last_byte)) { 425 return false; 426 } 427 if (next->base() <= last_byte) { 428 return false; 429 } 430 } 431 return true; 432} 433 434bool VmAddressRegion::CheckGapLocked(const ChildList::iterator& prev, 435 const ChildList::iterator& next, 436 vaddr_t* pva, vaddr_t search_base, vaddr_t align, 437 size_t region_size, size_t min_gap, uint arch_mmu_flags) { 438 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 439 440 vaddr_t gap_beg; // first byte of a gap 441 vaddr_t gap_end; // last byte of a gap 442 443 uint prev_arch_mmu_flags; 444 uint next_arch_mmu_flags; 445 446 DEBUG_ASSERT(pva); 447 448 // compute the starting address of the gap 449 if (prev.IsValid()) { 450 if (add_overflow(prev->base(), prev->size(), &gap_beg) || 451 add_overflow(gap_beg, min_gap, &gap_beg)) { 452 goto not_found; 453 } 454 } else { 455 gap_beg = base_; 456 } 457 458 // compute the ending address of the gap 459 if (next.IsValid()) { 460 if (gap_beg == next->base()) { 461 goto next_gap; // no gap between regions 462 } 463 if (sub_overflow(next->base(), 1, &gap_end) || 464 sub_overflow(gap_end, min_gap, &gap_end)) { 465 goto not_found; 466 } 467 } else { 468 if (gap_beg == base_ + size_) { 469 goto not_found; // no gap at the end of address space. Stop search 470 } 471 if (add_overflow(base_, size_ - 1, &gap_end)) { 472 goto not_found; 473 } 474 } 475 476 DEBUG_ASSERT(gap_end > gap_beg); 477 478 // trim it to the search range 479 if (gap_end <= search_base) { 480 return false; 481 } 482 if (gap_beg < search_base) { 483 gap_beg = search_base; 484 } 485 486 DEBUG_ASSERT(gap_end > gap_beg); 487 488 LTRACEF_LEVEL(2, "search base %#" PRIxPTR " gap_beg %#" PRIxPTR " end %#" PRIxPTR "\n", 489 search_base, gap_beg, gap_end); 490 491 prev_arch_mmu_flags = (prev.IsValid() && prev->is_mapping()) 492 ? prev->as_vm_mapping()->arch_mmu_flags() 493 : ARCH_MMU_FLAG_INVALID; 494 495 next_arch_mmu_flags = (next.IsValid() && next->is_mapping()) 496 ? next->as_vm_mapping()->arch_mmu_flags() 497 : ARCH_MMU_FLAG_INVALID; 498 499 *pva = aspace_->arch_aspace().PickSpot(gap_beg, prev_arch_mmu_flags, gap_end, 500 next_arch_mmu_flags, align, region_size, arch_mmu_flags); 501 if (*pva < gap_beg) { 502 goto not_found; // address wrapped around 503 } 504 505 if (*pva < gap_end && ((gap_end - *pva + 1) >= region_size)) { 506 // we have enough room 507 return true; // found spot, stop search 508 } 509 510next_gap: 511 return false; // continue search 512 513not_found: 514 *pva = -1; 515 return true; // not_found: stop search 516} 517 518zx_status_t VmAddressRegion::AllocSpotLocked(size_t size, uint8_t align_pow2, uint arch_mmu_flags, 519 vaddr_t* spot) { 520 canary_.Assert(); 521 DEBUG_ASSERT(size > 0 && IS_PAGE_ALIGNED(size)); 522 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 523 524 LTRACEF_LEVEL(2, "aspace %p size 0x%zx align %hhu\n", this, size, 525 align_pow2); 526 527 if (aspace_->is_aslr_enabled()) { 528 if (flags_ & VMAR_FLAG_COMPACT) { 529 return CompactRandomizedRegionAllocatorLocked(size, align_pow2, arch_mmu_flags, spot); 530 } else { 531 return NonCompactRandomizedRegionAllocatorLocked(size, align_pow2, arch_mmu_flags, 532 spot); 533 } 534 } 535 return LinearRegionAllocatorLocked(size, align_pow2, arch_mmu_flags, spot); 536} 537 538bool VmAddressRegion::EnumerateChildrenLocked(VmEnumerator* ve, uint depth) { 539 canary_.Assert(); 540 DEBUG_ASSERT(ve != nullptr); 541 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 542 543 const uint min_depth = depth; 544 for (auto itr = subregions_.begin(), end = subregions_.end(); itr != end;) { 545 DEBUG_ASSERT(itr->IsAliveLocked()); 546 auto curr = itr++; 547 VmAddressRegion* up = curr->parent_; 548 549 if (curr->is_mapping()) { 550 VmMapping* mapping = curr->as_vm_mapping().get(); 551 DEBUG_ASSERT(mapping != nullptr); 552 if (!ve->OnVmMapping(mapping, this, depth)) { 553 return false; 554 } 555 } else { 556 VmAddressRegion* vmar = curr->as_vm_address_region().get(); 557 DEBUG_ASSERT(vmar != nullptr); 558 if (!ve->OnVmAddressRegion(vmar, depth)) { 559 return false; 560 } 561 if (!vmar->subregions_.is_empty()) { 562 // If the sub-VMAR is not empty, iterate through its children. 563 itr = vmar->subregions_.begin(); 564 end = vmar->subregions_.end(); 565 depth++; 566 continue; 567 } 568 } 569 if (depth > min_depth && itr == end) { 570 // If we are at a depth greater than the minimum, and have reached 571 // the end of a sub-VMAR range, we ascend and continue iteration. 572 do { 573 itr = up->subregions_.upper_bound(curr->base()); 574 if (itr.IsValid()) { 575 break; 576 } 577 up = up->parent_; 578 } while (depth-- != min_depth); 579 if (!itr.IsValid()) { 580 // If we have reached the end after ascending all the way up, 581 // break out of the loop. 582 break; 583 } 584 end = up->subregions_.end(); 585 } 586 } 587 return true; 588} 589 590bool VmAddressRegion::has_parent() const { 591 Guard<fbl::Mutex> guard{aspace_->lock()}; 592 return parent_ != nullptr; 593} 594 595void VmAddressRegion::Dump(uint depth, bool verbose) const { 596 canary_.Assert(); 597 for (uint i = 0; i < depth; ++i) { 598 printf(" "); 599 } 600 printf("vmar %p [%#" PRIxPTR " %#" PRIxPTR "] sz %#zx ref %d '%s'\n", this, 601 base_, base_ + size_ - 1, size_, ref_count_debug(), name_); 602 for (const auto& child : subregions_) { 603 child.Dump(depth + 1, verbose); 604 } 605} 606 607void VmAddressRegion::Activate() { 608 DEBUG_ASSERT(state_ == LifeCycleState::NOT_READY); 609 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 610 611 state_ = LifeCycleState::ALIVE; 612 parent_->subregions_.insert(fbl::RefPtr<VmAddressRegionOrMapping>(this)); 613} 614 615zx_status_t VmAddressRegion::Unmap(vaddr_t base, size_t size) { 616 canary_.Assert(); 617 618 size = ROUNDUP(size, PAGE_SIZE); 619 if (size == 0 || !IS_PAGE_ALIGNED(base)) { 620 return ZX_ERR_INVALID_ARGS; 621 } 622 623 Guard<fbl::Mutex> guard{aspace_->lock()}; 624 if (state_ != LifeCycleState::ALIVE) { 625 return ZX_ERR_BAD_STATE; 626 } 627 628 return UnmapInternalLocked(base, size, true /* can_destroy_regions */, 629 false /* allow_partial_vmar */); 630} 631 632zx_status_t VmAddressRegion::UnmapAllowPartial(vaddr_t base, size_t size) { 633 canary_.Assert(); 634 635 size = ROUNDUP(size, PAGE_SIZE); 636 if (size == 0 || !IS_PAGE_ALIGNED(base)) { 637 return ZX_ERR_INVALID_ARGS; 638 } 639 640 Guard<fbl::Mutex> guard{aspace_->lock()}; 641 if (state_ != LifeCycleState::ALIVE) { 642 return ZX_ERR_BAD_STATE; 643 } 644 645 return UnmapInternalLocked(base, size, true /* can_destroy_regions */, 646 true /* allow_partial_vmar */); 647} 648 649VmAddressRegion::ChildList::iterator VmAddressRegion::UpperBoundInternalLocked(vaddr_t base) { 650 // Find the first region with a base greater than *base*. If a region 651 // exists for *base*, it will be immediately before it. 652 auto itr = --subregions_.upper_bound(base); 653 if (!itr.IsValid()) { 654 itr = subregions_.begin(); 655 } else if (base >= itr->base() + itr->size()) { 656 // If *base* isn't in this region, ignore it. 657 ++itr; 658 } 659 return itr; 660} 661 662zx_status_t VmAddressRegion::UnmapInternalLocked(vaddr_t base, size_t size, 663 bool can_destroy_regions, 664 bool allow_partial_vmar) { 665 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 666 667 if (!is_in_range(base, size)) { 668 return ZX_ERR_INVALID_ARGS; 669 } 670 671 if (subregions_.is_empty()) { 672 return ZX_OK; 673 } 674 675 // Any unmap spanning the vDSO code mapping is verboten. 676 if (aspace_->vdso_code_mapping_ && 677 aspace_->vdso_code_mapping_->base() >= base && 678 aspace_->vdso_code_mapping_->base() - base < size) { 679 return ZX_ERR_ACCESS_DENIED; 680 } 681 682 const vaddr_t end_addr = base + size; 683 auto end = subregions_.lower_bound(end_addr); 684 auto begin = UpperBoundInternalLocked(base); 685 686 if (!allow_partial_vmar) { 687 // Check if we're partially spanning a subregion, or aren't allowed to 688 // destroy regions and are spanning a region, and bail if we are. 689 for (auto itr = begin; itr != end; ++itr) { 690 const vaddr_t itr_end = itr->base() + itr->size(); 691 if (!itr->is_mapping() && (!can_destroy_regions || 692 itr->base() < base || itr_end > end_addr)) { 693 return ZX_ERR_INVALID_ARGS; 694 } 695 } 696 } 697 698 bool at_top = true; 699 for (auto itr = begin; itr != end;) { 700 // Create a copy of the iterator, in case we destroy this element 701 auto curr = itr++; 702 VmAddressRegion* up = curr->parent_; 703 704 if (curr->is_mapping()) { 705 const vaddr_t curr_end = curr->base() + curr->size(); 706 const vaddr_t unmap_base = fbl::max(curr->base(), base); 707 const vaddr_t unmap_end = fbl::min(curr_end, end_addr); 708 const size_t unmap_size = unmap_end - unmap_base; 709 710 if (unmap_base == curr->base() && unmap_size == curr->size()) { 711 // If we're unmapping the entire region, just call Destroy 712 __UNUSED zx_status_t status = curr->DestroyLocked(); 713 DEBUG_ASSERT(status == ZX_OK); 714 } else { 715 // VmMapping::Unmap should only fail if it needs to allocate, 716 // which only happens if it is unmapping from the middle of a 717 // region. That can only happen if there is only one region 718 // being operated on here, so we can just forward along the 719 // error without having to rollback. 720 // 721 // TODO(teisenbe): Technically arch_mmu_unmap() itself can also 722 // fail. We need to rework the system so that is no longer 723 // possible. 724 zx_status_t status = curr->as_vm_mapping()->UnmapLocked(unmap_base, unmap_size); 725 DEBUG_ASSERT(status == ZX_OK || curr == begin); 726 if (status != ZX_OK) { 727 return status; 728 } 729 } 730 } else { 731 vaddr_t unmap_base = 0; 732 size_t unmap_size = 0; 733 __UNUSED bool intersects = GetIntersect(base, size, curr->base(), curr->size(), 734 &unmap_base, &unmap_size); 735 DEBUG_ASSERT(intersects); 736 if (allow_partial_vmar) { 737 // If partial VMARs are allowed, we descend into sub-VMARs. 738 fbl::RefPtr<VmAddressRegion> vmar = curr->as_vm_address_region(); 739 if (!vmar->subregions_.is_empty()) { 740 begin = vmar->UpperBoundInternalLocked(base); 741 end = vmar->subregions_.lower_bound(end_addr); 742 itr = begin; 743 at_top = false; 744 } 745 } else if (unmap_base == curr->base() && unmap_size == curr->size()) { 746 __UNUSED zx_status_t status = curr->DestroyLocked(); 747 DEBUG_ASSERT(status == ZX_OK); 748 } 749 } 750 751 if (allow_partial_vmar && !at_top && itr == end) { 752 // If partial VMARs are allowed, and we have reached the end of a 753 // sub-VMAR range, we ascend and continue iteration. 754 do { 755 begin = up->subregions_.upper_bound(curr->base()); 756 if (begin.IsValid()) { 757 break; 758 } 759 at_top = up == this; 760 up = up->parent_; 761 } while (!at_top); 762 if (!begin.IsValid()) { 763 // If we have reached the end after ascending all the way up, 764 // break out of the loop. 765 break; 766 } 767 end = up->subregions_.lower_bound(end_addr); 768 itr = begin; 769 } 770 } 771 772 return ZX_OK; 773} 774 775zx_status_t VmAddressRegion::Protect(vaddr_t base, size_t size, uint new_arch_mmu_flags) { 776 canary_.Assert(); 777 778 size = ROUNDUP(size, PAGE_SIZE); 779 if (size == 0 || !IS_PAGE_ALIGNED(base)) { 780 return ZX_ERR_INVALID_ARGS; 781 } 782 783 Guard<fbl::Mutex> guard{aspace_->lock()}; 784 if (state_ != LifeCycleState::ALIVE) { 785 return ZX_ERR_BAD_STATE; 786 } 787 788 if (!is_in_range(base, size)) { 789 return ZX_ERR_INVALID_ARGS; 790 } 791 792 if (subregions_.is_empty()) { 793 return ZX_ERR_NOT_FOUND; 794 } 795 796 const vaddr_t end_addr = base + size; 797 const auto end = subregions_.lower_bound(end_addr); 798 799 // Find the first region with a base greater than *base*. If a region 800 // exists for *base*, it will be immediately before it. If *base* isn't in 801 // that entry, bail since it's unmapped. 802 auto begin = --subregions_.upper_bound(base); 803 if (!begin.IsValid() || begin->base() + begin->size() <= base) { 804 return ZX_ERR_NOT_FOUND; 805 } 806 807 // Check if we're overlapping a subregion, or a part of the range is not 808 // mapped, or the new permissions are invalid for some mapping in the range. 809 vaddr_t last_mapped = begin->base(); 810 for (auto itr = begin; itr != end; ++itr) { 811 if (!itr->is_mapping()) { 812 return ZX_ERR_INVALID_ARGS; 813 } 814 if (itr->base() != last_mapped) { 815 return ZX_ERR_NOT_FOUND; 816 } 817 if (!itr->is_valid_mapping_flags(new_arch_mmu_flags)) { 818 return ZX_ERR_ACCESS_DENIED; 819 } 820 if (itr->as_vm_mapping() == aspace_->vdso_code_mapping_) { 821 return ZX_ERR_ACCESS_DENIED; 822 } 823 824 last_mapped = itr->base() + itr->size(); 825 } 826 if (last_mapped < base + size) { 827 return ZX_ERR_NOT_FOUND; 828 } 829 830 for (auto itr = begin; itr != end;) { 831 DEBUG_ASSERT(itr->is_mapping()); 832 833 auto next = itr; 834 ++next; 835 836 const vaddr_t curr_end = itr->base() + itr->size(); 837 const vaddr_t protect_base = fbl::max(itr->base(), base); 838 const vaddr_t protect_end = fbl::min(curr_end, end_addr); 839 const size_t protect_size = protect_end - protect_base; 840 841 zx_status_t status = itr->as_vm_mapping()->ProtectLocked(protect_base, protect_size, 842 new_arch_mmu_flags); 843 if (status != ZX_OK) { 844 // TODO(teisenbe): Try to work out a way to guarantee success, or 845 // provide a full unwind? 846 return status; 847 } 848 849 itr = fbl::move(next); 850 } 851 852 return ZX_OK; 853} 854 855zx_status_t VmAddressRegion::LinearRegionAllocatorLocked(size_t size, uint8_t align_pow2, 856 uint arch_mmu_flags, vaddr_t* spot) { 857 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 858 859 const vaddr_t base = 0; 860 861 if (align_pow2 < PAGE_SIZE_SHIFT) { 862 align_pow2 = PAGE_SIZE_SHIFT; 863 } 864 const vaddr_t align = 1UL << align_pow2; 865 866 // Find the first gap in the address space which can contain a region of the 867 // requested size. 868 auto before_iter = subregions_.end(); 869 auto after_iter = subregions_.begin(); 870 871 do { 872 if (CheckGapLocked(before_iter, after_iter, spot, base, align, size, 0, arch_mmu_flags)) { 873 if (*spot != static_cast<vaddr_t>(-1)) { 874 return ZX_OK; 875 } else { 876 return ZX_ERR_NO_MEMORY; 877 } 878 } 879 880 before_iter = after_iter++; 881 } while (before_iter.IsValid()); 882 883 // couldn't find anything 884 return ZX_ERR_NO_MEMORY; 885} 886 887template <typename F> 888void VmAddressRegion::ForEachGap(F func, uint8_t align_pow2) { 889 const vaddr_t align = 1UL << align_pow2; 890 891 // Scan the regions list to find the gap to the left of each region. We 892 // round up the end of the previous region to the requested alignment, so 893 // all gaps reported will be for aligned ranges. 894 vaddr_t prev_region_end = ROUNDUP(base_, align); 895 for (const auto& region : subregions_) { 896 if (region.base() > prev_region_end) { 897 const size_t gap = region.base() - prev_region_end; 898 if (!func(prev_region_end, gap)) { 899 return; 900 } 901 } 902 prev_region_end = ROUNDUP(region.base() + region.size(), align); 903 } 904 905 // Grab the gap to the right of the last region (note that if there are no 906 // regions, this handles reporting the VMAR's whole span as a gap). 907 const vaddr_t end = base_ + size_; 908 if (end > prev_region_end) { 909 const size_t gap = end - prev_region_end; 910 func(prev_region_end, gap); 911 } 912} 913 914namespace { 915 916// Compute the number of allocation spots that satisfy the alignment within the 917// given range size, for a range that has a base that satisfies the alignment. 918constexpr size_t AllocationSpotsInRange(size_t range_size, size_t alloc_size, uint8_t align_pow2) { 919 return ((range_size - alloc_size) >> align_pow2) + 1; 920} 921 922} // namespace {} 923 924// Perform allocations for VMARs that aren't using the COMPACT policy. This 925// allocator works by choosing uniformly at random from the set of positions 926// that could satisfy the allocation. 927zx_status_t VmAddressRegion::NonCompactRandomizedRegionAllocatorLocked(size_t size, uint8_t align_pow2, 928 uint arch_mmu_flags, 929 vaddr_t* spot) { 930 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 931 DEBUG_ASSERT(spot); 932 933 align_pow2 = fbl::max(align_pow2, static_cast<uint8_t>(PAGE_SIZE_SHIFT)); 934 const vaddr_t align = 1UL << align_pow2; 935 936 // Calculate the number of spaces that we can fit this allocation in. 937 size_t candidate_spaces = 0; 938 ForEachGap([align, align_pow2, size, &candidate_spaces](vaddr_t gap_base, size_t gap_len) -> bool { 939 DEBUG_ASSERT(IS_ALIGNED(gap_base, align)); 940 if (gap_len >= size) { 941 candidate_spaces += AllocationSpotsInRange(gap_len, size, align_pow2); 942 } 943 return true; 944 }, 945 align_pow2); 946 947 if (candidate_spaces == 0) { 948 return ZX_ERR_NO_MEMORY; 949 } 950 951 // Choose the index of the allocation to use. 952 size_t selected_index = aspace_->AslrPrng().RandInt(candidate_spaces); 953 DEBUG_ASSERT(selected_index < candidate_spaces); 954 955 // Find which allocation we picked. 956 vaddr_t alloc_spot = static_cast<vaddr_t>(-1); 957 ForEachGap([align_pow2, size, &alloc_spot, &selected_index](vaddr_t gap_base, 958 size_t gap_len) -> bool { 959 if (gap_len < size) { 960 return true; 961 } 962 963 const size_t spots = AllocationSpotsInRange(gap_len, size, align_pow2); 964 if (selected_index < spots) { 965 alloc_spot = gap_base + (selected_index << align_pow2); 966 return false; 967 } 968 selected_index -= spots; 969 return true; 970 }, 971 align_pow2); 972 ASSERT(alloc_spot != static_cast<vaddr_t>(-1)); 973 ASSERT(IS_ALIGNED(alloc_spot, align)); 974 975 // Sanity check that the allocation fits. 976 auto after_iter = subregions_.upper_bound(alloc_spot + size - 1); 977 auto before_iter = after_iter; 978 979 if (after_iter == subregions_.begin() || subregions_.size() == 0) { 980 before_iter = subregions_.end(); 981 } else { 982 --before_iter; 983 } 984 985 ASSERT(before_iter == subregions_.end() || before_iter.IsValid()); 986 987 if (CheckGapLocked(before_iter, after_iter, spot, alloc_spot, align, size, 0, 988 arch_mmu_flags) && 989 *spot != static_cast<vaddr_t>(-1)) { 990 return ZX_OK; 991 } 992 panic("Unexpected allocation failure\n"); 993} 994 995// The COMPACT allocator begins by picking a random offset in the region to 996// start allocations at, and then places new allocations to the left and right 997// of the original region with small random-length gaps between. 998zx_status_t VmAddressRegion::CompactRandomizedRegionAllocatorLocked(size_t size, uint8_t align_pow2, 999 uint arch_mmu_flags, 1000 vaddr_t* spot) { 1001 DEBUG_ASSERT(aspace_->lock()->lock().IsHeld()); 1002 1003 align_pow2 = fbl::max(align_pow2, static_cast<uint8_t>(PAGE_SIZE_SHIFT)); 1004 const vaddr_t align = 1UL << align_pow2; 1005 1006 if (unlikely(subregions_.size() == 0)) { 1007 return NonCompactRandomizedRegionAllocatorLocked(size, align_pow2, arch_mmu_flags, spot); 1008 } 1009 1010 // Decide if we're allocating before or after the existing allocations, and 1011 // how many gap pages to use. 1012 bool alloc_before; 1013 size_t num_gap_pages; 1014 { 1015 uint8_t entropy; 1016 aspace_->AslrPrng().Draw(&entropy, sizeof(entropy)); 1017 alloc_before = entropy & 1; 1018 num_gap_pages = (entropy >> 1) + 1; 1019 } 1020 1021 // Try our first choice for *num_gap_pages*, but if that fails, try fewer 1022 for (size_t gap_pages = num_gap_pages; gap_pages > 0; gap_pages >>= 1) { 1023 // Try our first choice for *alloc_before*, but if that fails, try the other 1024 for (size_t i = 0; i < 2; ++i, alloc_before = !alloc_before) { 1025 ChildList::iterator before_iter; 1026 ChildList::iterator after_iter; 1027 vaddr_t chosen_base; 1028 if (alloc_before) { 1029 before_iter = subregions_.end(); 1030 after_iter = subregions_.begin(); 1031 1032 vaddr_t base; 1033 if (sub_overflow(after_iter->base(), size, &base) || 1034 sub_overflow(base, PAGE_SIZE * gap_pages, &base)) { 1035 continue; 1036 } 1037 1038 chosen_base = base; 1039 } else { 1040 before_iter = --subregions_.end(); 1041 after_iter = subregions_.end(); 1042 DEBUG_ASSERT(before_iter.IsValid()); 1043 1044 vaddr_t base; 1045 if (add_overflow(before_iter->base(), before_iter->size(), &base) || 1046 add_overflow(base, PAGE_SIZE * gap_pages, &base)) { 1047 continue; 1048 } 1049 1050 chosen_base = base; 1051 } 1052 1053 if (CheckGapLocked(before_iter, after_iter, spot, chosen_base, align, size, 0, 1054 arch_mmu_flags) && 1055 *spot != static_cast<vaddr_t>(-1)) { 1056 return ZX_OK; 1057 } 1058 } 1059 } 1060 1061 return ZX_ERR_NO_MEMORY; 1062} 1063