runtime/gc/allocator/rosalloc.cc

/*
 * Copyright (C) 2013 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "rosalloc.h"

#include "base/memory_tool.h"
#include "base/mutex-inl.h"
#include "gc/space/memory_tool_settings.h"
#include "mem_map.h"
#include "mirror/class-inl.h"
#include "mirror/object.h"
#include "mirror/object-inl.h"
#include "thread-inl.h"
#include "thread_list.h"

#include <map>
#include <list>
#include <sstream>
#include <vector>

namespace art {
namespace gc {
namespace allocator {

static constexpr bool kUsePrefetchDuringAllocRun = false;
static constexpr bool kPrefetchNewRunDataByZeroing = false;
static constexpr size_t kPrefetchStride = 64;

size_t RosAlloc::bracketSizes[kNumOfSizeBrackets];
size_t RosAlloc::numOfPages[kNumOfSizeBrackets];
size_t RosAlloc::numOfSlots[kNumOfSizeBrackets];
size_t RosAlloc::headerSizes[kNumOfSizeBrackets];
bool RosAlloc::initialized_ = false;
size_t RosAlloc::dedicated_full_run_storage_[kPageSize / sizeof(size_t)] = { 0 };
RosAlloc::Run* RosAlloc::dedicated_full_run_ =
    reinterpret_cast<RosAlloc::Run*>(dedicated_full_run_storage_);

RosAlloc::RosAlloc(void* base, size_t capacity, size_t max_capacity,
                   PageReleaseMode page_release_mode, bool running_on_memory_tool,
                   size_t page_release_size_threshold)
    : base_(reinterpret_cast<uint8_t*>(base)), footprint_(capacity),
      capacity_(capacity), max_capacity_(max_capacity),
      lock_("rosalloc global lock", kRosAllocGlobalLock),
      bulk_free_lock_("rosalloc bulk free lock", kRosAllocBulkFreeLock),
      page_release_mode_(page_release_mode),
      page_release_size_threshold_(page_release_size_threshold),
      is_running_on_memory_tool_(running_on_memory_tool) {
  DCHECK_ALIGNED(base, kPageSize);
  DCHECK_EQ(RoundUp(capacity, kPageSize), capacity);
  DCHECK_EQ(RoundUp(max_capacity, kPageSize), max_capacity);
  CHECK_LE(capacity, max_capacity);
  CHECK_ALIGNED(page_release_size_threshold_, kPageSize);
  // Zero the memory explicitly (don't rely on that the mem map is zero-initialized).
  if (!kMadviseZeroes) {
    memset(base_, 0, max_capacity);
  }
  CHECK_EQ(madvise(base_, max_capacity, MADV_DONTNEED), 0);
  if (!initialized_) {
    Initialize();
  }
  VLOG(heap) << "RosAlloc base="
             << std::hex << (intptr_t)base_ << ", end="
             << std::hex << (intptr_t)(base_ + capacity_)
             << ", capacity=" << std::dec << capacity_
             << ", max_capacity=" << std::dec << max_capacity_;
  for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
    size_bracket_lock_names_[i] =
        StringPrintf("an rosalloc size bracket %d lock", static_cast<int>(i));
    size_bracket_locks_[i] = new Mutex(size_bracket_lock_names_[i].c_str(), kRosAllocBracketLock);
    current_runs_[i] = dedicated_full_run_;
  }
  DCHECK_EQ(footprint_, capacity_);
  size_t num_of_pages = footprint_ / kPageSize;
  size_t max_num_of_pages = max_capacity_ / kPageSize;
  std::string error_msg;
  page_map_mem_map_.reset(MemMap::MapAnonymous("rosalloc page map", nullptr,
                                               RoundUp(max_num_of_pages, kPageSize),
                                               PROT_READ | PROT_WRITE, false, false, &error_msg));
  CHECK(page_map_mem_map_.get() != nullptr) << "Couldn't allocate the page map : " << error_msg;
  page_map_ = page_map_mem_map_->Begin();
  page_map_size_ = num_of_pages;
  max_page_map_size_ = max_num_of_pages;
  free_page_run_size_map_.resize(num_of_pages);
  FreePageRun* free_pages = reinterpret_cast<FreePageRun*>(base_);
  if (kIsDebugBuild) {
    free_pages->magic_num_ = kMagicNumFree;
  }
  free_pages->SetByteSize(this, capacity_);
  DCHECK_EQ(capacity_ % kPageSize, static_cast<size_t>(0));
  DCHECK(free_pages->IsFree());
  free_pages->ReleasePages(this);
  DCHECK(free_pages->IsFree());
  free_page_runs_.insert(free_pages);
  if (kTraceRosAlloc) {
    LOG(INFO) << "RosAlloc::RosAlloc() : Inserted run 0x" << std::hex
              << reinterpret_cast<intptr_t>(free_pages)
              << " into free_page_runs_";
  }
}

RosAlloc::~RosAlloc() {
  for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
    delete size_bracket_locks_[i];
  }
  if (is_running_on_memory_tool_) {
    MEMORY_TOOL_MAKE_DEFINED(base_, capacity_);
  }
}

void* RosAlloc::AllocPages(Thread* self, size_t num_pages, uint8_t page_map_type) {
  lock_.AssertHeld(self);
  DCHECK(page_map_type == kPageMapRun || page_map_type == kPageMapLargeObject);
  FreePageRun* res = nullptr;
  const size_t req_byte_size = num_pages * kPageSize;
  // Find the lowest address free page run that's large enough.
  for (auto it = free_page_runs_.begin(); it != free_page_runs_.end(); ) {
    FreePageRun* fpr = *it;
    DCHECK(fpr->IsFree());
    size_t fpr_byte_size = fpr->ByteSize(this);
    DCHECK_EQ(fpr_byte_size % kPageSize, static_cast<size_t>(0));
    if (req_byte_size <= fpr_byte_size) {
      // Found one.
      free_page_runs_.erase(it++);
      if (kTraceRosAlloc) {
        LOG(INFO) << "RosAlloc::AllocPages() : Erased run 0x"
                  << std::hex << reinterpret_cast<intptr_t>(fpr)
                  << " from free_page_runs_";
      }
      if (req_byte_size < fpr_byte_size) {
        // Split.
        FreePageRun* remainder = reinterpret_cast<FreePageRun*>(reinterpret_cast<uint8_t*>(fpr) + req_byte_size);
        if (kIsDebugBuild) {
          remainder->magic_num_ = kMagicNumFree;
        }
        remainder->SetByteSize(this, fpr_byte_size - req_byte_size);
        DCHECK_EQ(remainder->ByteSize(this) % kPageSize, static_cast<size_t>(0));
        // Don't need to call madvise on remainder here.
        free_page_runs_.insert(remainder);
        if (kTraceRosAlloc) {
          LOG(INFO) << "RosAlloc::AllocPages() : Inserted run 0x" << std::hex
                    << reinterpret_cast<intptr_t>(remainder)
                    << " into free_page_runs_";
        }
        fpr->SetByteSize(this, req_byte_size);
        DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
      }
      res = fpr;
      break;
    } else {
      ++it;
    }
  }

  // Failed to allocate pages. Grow the footprint, if possible.
  if (UNLIKELY(res == nullptr && capacity_ > footprint_)) {
    FreePageRun* last_free_page_run = nullptr;
    size_t last_free_page_run_size;
    auto it = free_page_runs_.rbegin();
    if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) {
      // There is a free page run at the end.
      DCHECK(last_free_page_run->IsFree());
      DCHECK(IsFreePage(ToPageMapIndex(last_free_page_run)));
      last_free_page_run_size = last_free_page_run->ByteSize(this);
    } else {
      // There is no free page run at the end.
      last_free_page_run_size = 0;
    }
    DCHECK_LT(last_free_page_run_size, req_byte_size);
    if (capacity_ - footprint_ + last_free_page_run_size >= req_byte_size) {
      // If we grow the heap, we can allocate it.
      size_t increment = std::min(std::max(2 * MB, req_byte_size - last_free_page_run_size),
                                  capacity_ - footprint_);
      DCHECK_EQ(increment % kPageSize, static_cast<size_t>(0));
      size_t new_footprint = footprint_ + increment;
      size_t new_num_of_pages = new_footprint / kPageSize;
      DCHECK_LT(page_map_size_, new_num_of_pages);
      DCHECK_LT(free_page_run_size_map_.size(), new_num_of_pages);
      page_map_size_ = new_num_of_pages;
      DCHECK_LE(page_map_size_, max_page_map_size_);
      free_page_run_size_map_.resize(new_num_of_pages);
      ArtRosAllocMoreCore(this, increment);
      if (last_free_page_run_size > 0) {
        // There was a free page run at the end. Expand its size.
        DCHECK_EQ(last_free_page_run_size, last_free_page_run->ByteSize(this));
        last_free_page_run->SetByteSize(this, last_free_page_run_size + increment);
        DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
        DCHECK_EQ(last_free_page_run->End(this), base_ + new_footprint);
      } else {
        // Otherwise, insert a new free page run at the end.
        FreePageRun* new_free_page_run = reinterpret_cast<FreePageRun*>(base_ + footprint_);
        if (kIsDebugBuild) {
          new_free_page_run->magic_num_ = kMagicNumFree;
        }
        new_free_page_run->SetByteSize(this, increment);
        DCHECK_EQ(new_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
        free_page_runs_.insert(new_free_page_run);
        DCHECK_EQ(*free_page_runs_.rbegin(), new_free_page_run);
        if (kTraceRosAlloc) {
          LOG(INFO) << "RosAlloc::AlloPages() : Grew the heap by inserting run 0x"
                    << std::hex << reinterpret_cast<intptr_t>(new_free_page_run)
                    << " into free_page_runs_";
        }
      }
      DCHECK_LE(footprint_ + increment, capacity_);
      if (kTraceRosAlloc) {
        LOG(INFO) << "RosAlloc::AllocPages() : increased the footprint from "
                  << footprint_ << " to " << new_footprint;
      }
      footprint_ = new_footprint;

      // And retry the last free page run.
      it = free_page_runs_.rbegin();
      DCHECK(it != free_page_runs_.rend());
      FreePageRun* fpr = *it;
      if (kIsDebugBuild && last_free_page_run_size > 0) {
        DCHECK(last_free_page_run != nullptr);
        DCHECK_EQ(last_free_page_run, fpr);
      }
      size_t fpr_byte_size = fpr->ByteSize(this);
      DCHECK_EQ(fpr_byte_size % kPageSize, static_cast<size_t>(0));
      DCHECK_LE(req_byte_size, fpr_byte_size);
      free_page_runs_.erase(fpr);
      if (kTraceRosAlloc) {
        LOG(INFO) << "RosAlloc::AllocPages() : Erased run 0x" << std::hex << reinterpret_cast<intptr_t>(fpr)
                  << " from free_page_runs_";
      }
      if (req_byte_size < fpr_byte_size) {
        // Split if there's a remainder.
        FreePageRun* remainder = reinterpret_cast<FreePageRun*>(reinterpret_cast<uint8_t*>(fpr) + req_byte_size);
        if (kIsDebugBuild) {
          remainder->magic_num_ = kMagicNumFree;
        }
        remainder->SetByteSize(this, fpr_byte_size - req_byte_size);
        DCHECK_EQ(remainder->ByteSize(this) % kPageSize, static_cast<size_t>(0));
        free_page_runs_.insert(remainder);
        if (kTraceRosAlloc) {
          LOG(INFO) << "RosAlloc::AllocPages() : Inserted run 0x" << std::hex
                    << reinterpret_cast<intptr_t>(remainder)
                    << " into free_page_runs_";
        }
        fpr->SetByteSize(this, req_byte_size);
        DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
      }
      res = fpr;
    }
  }
  if (LIKELY(res != nullptr)) {
    // Update the page map.
    size_t page_map_idx = ToPageMapIndex(res);
    for (size_t i = 0; i < num_pages; i++) {
      DCHECK(IsFreePage(page_map_idx + i));
    }
    switch (page_map_type) {
    case kPageMapRun:
      page_map_[page_map_idx] = kPageMapRun;
      for (size_t i = 1; i < num_pages; i++) {
        page_map_[page_map_idx + i] = kPageMapRunPart;
      }
      break;
    case kPageMapLargeObject:
      page_map_[page_map_idx] = kPageMapLargeObject;
      for (size_t i = 1; i < num_pages; i++) {
        page_map_[page_map_idx + i] = kPageMapLargeObjectPart;
      }
      break;
    default:
      LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_type);
      break;
    }
    if (kIsDebugBuild) {
      // Clear the first page since it is not madvised due to the magic number.
      memset(res, 0, kPageSize);
    }
    if (kTraceRosAlloc) {
      LOG(INFO) << "RosAlloc::AllocPages() : 0x" << std::hex << reinterpret_cast<intptr_t>(res)
                << "-0x" << (reinterpret_cast<intptr_t>(res) + num_pages * kPageSize)
                << "(" << std::dec << (num_pages * kPageSize) << ")";
    }
    return res;
  }

  // Fail.
  if (kTraceRosAlloc) {
    LOG(INFO) << "RosAlloc::AllocPages() : nullptr";
  }
  return nullptr;
}

size_t RosAlloc::FreePages(Thread* self, void* ptr, bool already_zero) {
  lock_.AssertHeld(self);
  size_t pm_idx = ToPageMapIndex(ptr);
  DCHECK_LT(pm_idx, page_map_size_);
  uint8_t pm_type = page_map_[pm_idx];
  DCHECK(pm_type == kPageMapRun || pm_type == kPageMapLargeObject);
  uint8_t pm_part_type;
  switch (pm_type) {
  case kPageMapRun:
    pm_part_type = kPageMapRunPart;
    break;
  case kPageMapLargeObject:
    pm_part_type = kPageMapLargeObjectPart;
    break;
  default:
    LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << " : " << "pm_idx=" << pm_idx << ", pm_type="
               << static_cast<int>(pm_type) << ", ptr=" << std::hex
               << reinterpret_cast<intptr_t>(ptr);
    return 0;
  }
  // Update the page map and count the number of pages.
  size_t num_pages = 1;
  page_map_[pm_idx] = kPageMapEmpty;
  size_t idx = pm_idx + 1;
  size_t end = page_map_size_;
  while (idx < end && page_map_[idx] == pm_part_type) {
    page_map_[idx] = kPageMapEmpty;
    num_pages++;
    idx++;
  }
  const size_t byte_size = num_pages * kPageSize;
  if (already_zero) {
    if (ShouldCheckZeroMemory()) {
      const uintptr_t* word_ptr = reinterpret_cast<uintptr_t*>(ptr);
      for (size_t i = 0; i < byte_size / sizeof(uintptr_t); ++i) {
        CHECK_EQ(word_ptr[i], 0U) << "words don't match at index " << i;
      }
    }
  } else if (!DoesReleaseAllPages()) {
    memset(ptr, 0, byte_size);
  }

  if (kTraceRosAlloc) {
    LOG(INFO) << __PRETTY_FUNCTION__ << " : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr)
              << "-0x" << (reinterpret_cast<intptr_t>(ptr) + byte_size)
              << "(" << std::dec << (num_pages * kPageSize) << ")";
  }

  // Turn it into a free run.
  FreePageRun* fpr = reinterpret_cast<FreePageRun*>(ptr);
  if (kIsDebugBuild) {
    fpr->magic_num_ = kMagicNumFree;
  }
  fpr->SetByteSize(this, byte_size);
  DCHECK_ALIGNED(fpr->ByteSize(this), kPageSize);

  DCHECK(free_page_runs_.find(fpr) == free_page_runs_.end());
  if (!free_page_runs_.empty()) {
    // Try to coalesce in the higher address direction.
    if (kTraceRosAlloc) {
      LOG(INFO) << __PRETTY_FUNCTION__ << "RosAlloc::FreePages() : trying to coalesce a free page run 0x"
                << std::hex << reinterpret_cast<uintptr_t>(fpr) << " [" << std::dec << pm_idx << "] -0x"
                << std::hex << reinterpret_cast<uintptr_t>(fpr->End(this)) << " [" << std::dec
                << (fpr->End(this) == End() ? page_map_size_ : ToPageMapIndex(fpr->End(this))) << "]";
    }
    auto higher_it = free_page_runs_.upper_bound(fpr);
    if (higher_it != free_page_runs_.end()) {
      for (auto it = higher_it; it != free_page_runs_.end(); ) {
        FreePageRun* h = *it;
        DCHECK_EQ(h->ByteSize(this) % kPageSize, static_cast<size_t>(0));
        if (kTraceRosAlloc) {
          LOG(INFO) << "RosAlloc::FreePages() : trying to coalesce with a higher free page run 0x"
                    << std::hex << reinterpret_cast<uintptr_t>(h) << " [" << std::dec << ToPageMapIndex(h) << "] -0x"
                    << std::hex << reinterpret_cast<uintptr_t>(h->End(this)) << " [" << std::dec
                    << (h->End(this) == End() ? page_map_size_ : ToPageMapIndex(h->End(this))) << "]";
        }
        if (fpr->End(this) == h->Begin()) {
          if (kTraceRosAlloc) {
            LOG(INFO) << "Success";
          }
          // Clear magic num since this is no longer the start of a free page run.
          if (kIsDebugBuild) {
            h->magic_num_ = 0;
          }
          free_page_runs_.erase(it++);
          if (kTraceRosAlloc) {
            LOG(INFO) << "RosAlloc::FreePages() : (coalesce) Erased run 0x" << std::hex
                      << reinterpret_cast<intptr_t>(h)
                      << " from free_page_runs_";
          }
          fpr->SetByteSize(this, fpr->ByteSize(this) + h->ByteSize(this));
          DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
        } else {
          // Not adjacent. Stop.
          if (kTraceRosAlloc) {
            LOG(INFO) << "Fail";
          }
          break;
        }
      }
    }
    // Try to coalesce in the lower address direction.
    auto lower_it = free_page_runs_.upper_bound(fpr);
    if (lower_it != free_page_runs_.begin()) {
      --lower_it;
      for (auto it = lower_it; ; ) {
        // We want to try to coalesce with the first element but
        // there's no "<=" operator for the iterator.
        bool to_exit_loop = it == free_page_runs_.begin();

        FreePageRun* l = *it;
        DCHECK_EQ(l->ByteSize(this) % kPageSize, static_cast<size_t>(0));
        if (kTraceRosAlloc) {
          LOG(INFO) << "RosAlloc::FreePages() : trying to coalesce with a lower free page run 0x"
                    << std::hex << reinterpret_cast<uintptr_t>(l) << " [" << std::dec << ToPageMapIndex(l) << "] -0x"
                    << std::hex << reinterpret_cast<uintptr_t>(l->End(this)) << " [" << std::dec
                    << (l->End(this) == End() ? page_map_size_ : ToPageMapIndex(l->End(this))) << "]";
        }
        if (l->End(this) == fpr->Begin()) {
          if (kTraceRosAlloc) {
            LOG(INFO) << "Success";
          }
          free_page_runs_.erase(it--);
          if (kTraceRosAlloc) {
            LOG(INFO) << "RosAlloc::FreePages() : (coalesce) Erased run 0x" << std::hex
                      << reinterpret_cast<intptr_t>(l)
                      << " from free_page_runs_";
          }
          l->SetByteSize(this, l->ByteSize(this) + fpr->ByteSize(this));
          DCHECK_EQ(l->ByteSize(this) % kPageSize, static_cast<size_t>(0));
          // Clear magic num since this is no longer the start of a free page run.
          if (kIsDebugBuild) {
            fpr->magic_num_ = 0;
          }
          fpr = l;
        } else {
          // Not adjacent. Stop.
          if (kTraceRosAlloc) {
            LOG(INFO) << "Fail";
          }
          break;
        }
        if (to_exit_loop) {
          break;
        }
      }
    }
  }

  // Insert it.
  DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
  DCHECK(free_page_runs_.find(fpr) == free_page_runs_.end());
  DCHECK(fpr->IsFree());
  fpr->ReleasePages(this);
  DCHECK(fpr->IsFree());
  free_page_runs_.insert(fpr);
  DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end());
  if (kTraceRosAlloc) {
    LOG(INFO) << "RosAlloc::FreePages() : Inserted run 0x" << std::hex << reinterpret_cast<intptr_t>(fpr)
              << " into free_page_runs_";
  }
  return byte_size;
}

void* RosAlloc::AllocLargeObject(Thread* self, size_t size, size_t* bytes_allocated,
                                 size_t* usable_size, size_t* bytes_tl_bulk_allocated) {
  DCHECK(bytes_allocated != nullptr);
  DCHECK(usable_size != nullptr);
  DCHECK_GT(size, kLargeSizeThreshold);
  size_t num_pages = RoundUp(size, kPageSize) / kPageSize;
  void* r;
  {
    MutexLock mu(self, lock_);
    r = AllocPages(self, num_pages, kPageMapLargeObject);
  }
  if (UNLIKELY(r == nullptr)) {
    if (kTraceRosAlloc) {
      LOG(INFO) << "RosAlloc::AllocLargeObject() : nullptr";
    }
    return nullptr;
  }
  const size_t total_bytes = num_pages * kPageSize;
  *bytes_allocated = total_bytes;
  *usable_size = total_bytes;
  *bytes_tl_bulk_allocated = total_bytes;
  if (kTraceRosAlloc) {
    LOG(INFO) << "RosAlloc::AllocLargeObject() : 0x" << std::hex << reinterpret_cast<intptr_t>(r)
              << "-0x" << (reinterpret_cast<intptr_t>(r) + num_pages * kPageSize)
              << "(" << std::dec << (num_pages * kPageSize) << ")";
  }
  // Check if the returned memory is really all zero.
  if (ShouldCheckZeroMemory()) {
    CHECK_EQ(total_bytes % sizeof(uintptr_t), 0U);
    const uintptr_t* words = reinterpret_cast<uintptr_t*>(r);
    for (size_t i = 0; i < total_bytes / sizeof(uintptr_t); ++i) {
      CHECK_EQ(words[i], 0U);
    }
  }
  return r;
}

size_t RosAlloc::FreeInternal(Thread* self, void* ptr) {
  DCHECK_LE(base_, ptr);
  DCHECK_LT(ptr, base_ + footprint_);
  size_t pm_idx = RoundDownToPageMapIndex(ptr);
  Run* run = nullptr;
  {
    MutexLock mu(self, lock_);
    DCHECK_LT(pm_idx, page_map_size_);
    uint8_t page_map_entry = page_map_[pm_idx];
    if (kTraceRosAlloc) {
      LOG(INFO) << "RosAlloc::FreeInternal() : " << std::hex << ptr << ", pm_idx=" << std::dec << pm_idx
                << ", page_map_entry=" << static_cast<int>(page_map_entry);
    }
    switch (page_map_[pm_idx]) {
      case kPageMapLargeObject:
        return FreePages(self, ptr, false);
      case kPageMapLargeObjectPart:
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
        return 0;
      case kPageMapRunPart: {
        // Find the beginning of the run.
        do {
          --pm_idx;
          DCHECK_LT(pm_idx, capacity_ / kPageSize);
        } while (page_map_[pm_idx] != kPageMapRun);
        FALLTHROUGH_INTENDED;
      case kPageMapRun:
        run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
        DCHECK_EQ(run->magic_num_, kMagicNum);
        break;
      case kPageMapReleased:
      case kPageMapEmpty:
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
        return 0;
      }
      default:
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
        return 0;
    }
  }
  DCHECK(run != nullptr);
  return FreeFromRun(self, ptr, run);
}

size_t RosAlloc::Free(Thread* self, void* ptr) {
  ReaderMutexLock rmu(self, bulk_free_lock_);
  return FreeInternal(self, ptr);
}

RosAlloc::Run* RosAlloc::AllocRun(Thread* self, size_t idx) {
  RosAlloc::Run* new_run = nullptr;
  {
    MutexLock mu(self, lock_);
    new_run = reinterpret_cast<Run*>(AllocPages(self, numOfPages[idx], kPageMapRun));
  }
  if (LIKELY(new_run != nullptr)) {
    if (kIsDebugBuild) {
      new_run->magic_num_ = kMagicNum;
    }
    new_run->size_bracket_idx_ = idx;
    DCHECK(!new_run->IsThreadLocal());
    DCHECK(!new_run->to_be_bulk_freed_);
    if (kUsePrefetchDuringAllocRun && idx < kNumThreadLocalSizeBrackets) {
      // Take ownership of the cache lines if we are likely to be thread local run.
      if (kPrefetchNewRunDataByZeroing) {
        // Zeroing the data is sometimes faster than prefetching but it increases memory usage
        // since we end up dirtying zero pages which may have been madvised.
        new_run->ZeroData();
      } else {
        const size_t num_of_slots = numOfSlots[idx];
        const size_t bracket_size = bracketSizes[idx];
        const size_t num_of_bytes = num_of_slots * bracket_size;
        uint8_t* begin = reinterpret_cast<uint8_t*>(new_run) + headerSizes[idx];
        for (size_t i = 0; i < num_of_bytes; i += kPrefetchStride) {
          __builtin_prefetch(begin + i);
        }
      }
    }
    new_run->InitFreeList();
  }
  return new_run;
}

RosAlloc::Run* RosAlloc::RefillRun(Thread* self, size_t idx) {
  // Get the lowest address non-full run from the binary tree.
  auto* const bt = &non_full_runs_[idx];
  if (!bt->empty()) {
    // If there's one, use it as the current run.
    auto it = bt->begin();
    Run* non_full_run = *it;
    DCHECK(non_full_run != nullptr);
    DCHECK(!non_full_run->IsThreadLocal());
    bt->erase(it);
    return non_full_run;
  }
  // If there's none, allocate a new run and use it as the current run.
  return AllocRun(self, idx);
}

inline void* RosAlloc::AllocFromCurrentRunUnlocked(Thread* self, size_t idx) {
  Run* current_run = current_runs_[idx];
  DCHECK(current_run != nullptr);
  void* slot_addr = current_run->AllocSlot();
  if (UNLIKELY(slot_addr == nullptr)) {
    // The current run got full. Try to refill it.
    DCHECK(current_run->IsFull());
    if (kIsDebugBuild && current_run != dedicated_full_run_) {
      full_runs_[idx].insert(current_run);
      if (kTraceRosAlloc) {
        LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex
                  << reinterpret_cast<intptr_t>(current_run)
                  << " into full_runs_[" << std::dec << idx << "]";
      }
      DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end());
      DCHECK(full_runs_[idx].find(current_run) != full_runs_[idx].end());
    }
    current_run = RefillRun(self, idx);
    if (UNLIKELY(current_run == nullptr)) {
      // Failed to allocate a new run, make sure that it is the dedicated full run.
      current_runs_[idx] = dedicated_full_run_;
      return nullptr;
    }
    DCHECK(current_run != nullptr);
    DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end());
    DCHECK(full_runs_[idx].find(current_run) == full_runs_[idx].end());
    current_run->SetIsThreadLocal(false);
    current_runs_[idx] = current_run;
    DCHECK(!current_run->IsFull());
    slot_addr = current_run->AllocSlot();
    // Must succeed now with a new run.
    DCHECK(slot_addr != nullptr);
  }
  return slot_addr;
}

void* RosAlloc::AllocFromRunThreadUnsafe(Thread* self, size_t size, size_t* bytes_allocated,
                                         size_t* usable_size,
                                         size_t* bytes_tl_bulk_allocated) {
  DCHECK(bytes_allocated != nullptr);
  DCHECK(usable_size != nullptr);
  DCHECK(bytes_tl_bulk_allocated != nullptr);
  DCHECK_LE(size, kLargeSizeThreshold);
  size_t bracket_size;
  size_t idx = SizeToIndexAndBracketSize(size, &bracket_size);
  Locks::mutator_lock_->AssertExclusiveHeld(self);
  void* slot_addr = AllocFromCurrentRunUnlocked(self, idx);
  if (LIKELY(slot_addr != nullptr)) {
    *bytes_allocated = bracket_size;
    *usable_size = bracket_size;
    *bytes_tl_bulk_allocated = bracket_size;
  }
  // Caller verifies that it is all 0.
  return slot_addr;
}

void* RosAlloc::AllocFromRun(Thread* self, size_t size, size_t* bytes_allocated,
                             size_t* usable_size, size_t* bytes_tl_bulk_allocated) {
  DCHECK(bytes_allocated != nullptr);
  DCHECK(usable_size != nullptr);
  DCHECK(bytes_tl_bulk_allocated != nullptr);
  DCHECK_LE(size, kLargeSizeThreshold);
  size_t bracket_size;
  size_t idx = SizeToIndexAndBracketSize(size, &bracket_size);
  void* slot_addr;
  if (LIKELY(idx < kNumThreadLocalSizeBrackets)) {
    // Use a thread-local run.
    Run* thread_local_run = reinterpret_cast<Run*>(self->GetRosAllocRun(idx));
    // Allow invalid since this will always fail the allocation.
    if (kIsDebugBuild) {
      // Need the lock to prevent race conditions.
      MutexLock mu(self, *size_bracket_locks_[idx]);
      CHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
      CHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
    }
    DCHECK(thread_local_run != nullptr);
    DCHECK(thread_local_run->IsThreadLocal() || thread_local_run == dedicated_full_run_);
    slot_addr = thread_local_run->AllocSlot();
    // The allocation must fail if the run is invalid.
    DCHECK(thread_local_run != dedicated_full_run_ || slot_addr == nullptr)
        << "allocated from an invalid run";
    if (UNLIKELY(slot_addr == nullptr)) {
      // The run got full. Try to free slots.
      DCHECK(thread_local_run->IsFull());
      MutexLock mu(self, *size_bracket_locks_[idx]);
      bool is_all_free_after_merge;
      // This is safe to do for the dedicated_full_run_ since the bitmaps are empty.
      if (thread_local_run->MergeThreadLocalFreeListToFreeList(&is_all_free_after_merge)) {
        DCHECK_NE(thread_local_run, dedicated_full_run_);
        // Some slot got freed. Keep it.
        DCHECK(!thread_local_run->IsFull());
        DCHECK_EQ(is_all_free_after_merge, thread_local_run->IsAllFree());
      } else {
        // No slots got freed. Try to refill the thread-local run.
        DCHECK(thread_local_run->IsFull());
        if (thread_local_run != dedicated_full_run_) {
          thread_local_run->SetIsThreadLocal(false);
          if (kIsDebugBuild) {
            full_runs_[idx].insert(thread_local_run);
            if (kTraceRosAlloc) {
              LOG(INFO) << "RosAlloc::AllocFromRun() : Inserted run 0x" << std::hex
                        << reinterpret_cast<intptr_t>(thread_local_run)
                        << " into full_runs_[" << std::dec << idx << "]";
            }
          }
          DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
          DCHECK(full_runs_[idx].find(thread_local_run) != full_runs_[idx].end());
        }

        thread_local_run = RefillRun(self, idx);
        if (UNLIKELY(thread_local_run == nullptr)) {
          self->SetRosAllocRun(idx, dedicated_full_run_);
          return nullptr;
        }
        DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
        DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
        thread_local_run->SetIsThreadLocal(true);
        self->SetRosAllocRun(idx, thread_local_run);
        DCHECK(!thread_local_run->IsFull());
      }
      DCHECK(thread_local_run != nullptr);
      DCHECK(!thread_local_run->IsFull());
      DCHECK(thread_local_run->IsThreadLocal());
      // Account for all the free slots in the new or refreshed thread local run.
      *bytes_tl_bulk_allocated = thread_local_run->NumberOfFreeSlots() * bracket_size;
      slot_addr = thread_local_run->AllocSlot();
      // Must succeed now with a new run.
      DCHECK(slot_addr != nullptr);
    } else {
      // The slot is already counted. Leave it as is.
      *bytes_tl_bulk_allocated = 0;
    }
    DCHECK(slot_addr != nullptr);
    if (kTraceRosAlloc) {
      LOG(INFO) << "RosAlloc::AllocFromRun() thread-local : 0x" << std::hex
                << reinterpret_cast<intptr_t>(slot_addr)
                << "-0x" << (reinterpret_cast<intptr_t>(slot_addr) + bracket_size)
                << "(" << std::dec << (bracket_size) << ")";
    }
    *bytes_allocated = bracket_size;
    *usable_size = bracket_size;
  } else {
    // Use the (shared) current run.
    MutexLock mu(self, *size_bracket_locks_[idx]);
    slot_addr = AllocFromCurrentRunUnlocked(self, idx);
    if (kTraceRosAlloc) {
      LOG(INFO) << "RosAlloc::AllocFromRun() : 0x" << std::hex
                << reinterpret_cast<intptr_t>(slot_addr)
                << "-0x" << (reinterpret_cast<intptr_t>(slot_addr) + bracket_size)
                << "(" << std::dec << (bracket_size) << ")";
    }
    if (LIKELY(slot_addr != nullptr)) {
      *bytes_allocated = bracket_size;
      *usable_size = bracket_size;
      *bytes_tl_bulk_allocated = bracket_size;
    }
  }
  // Caller verifies that it is all 0.
  return slot_addr;
}

size_t RosAlloc::FreeFromRun(Thread* self, void* ptr, Run* run) {
  DCHECK_EQ(run->magic_num_, kMagicNum);
  DCHECK_LT(run, ptr);
  DCHECK_LT(ptr, run->End());
  const size_t idx = run->size_bracket_idx_;
  const size_t bracket_size = bracketSizes[idx];
  bool run_was_full = false;
  MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
  if (kIsDebugBuild) {
    run_was_full = run->IsFull();
  }
  if (kTraceRosAlloc) {
    LOG(INFO) << "RosAlloc::FreeFromRun() : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr);
  }
  if (LIKELY(run->IsThreadLocal())) {
    // It's a thread-local run. Just mark the thread-local free bit map and return.
    DCHECK_LT(run->size_bracket_idx_, kNumThreadLocalSizeBrackets);
    DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
    DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
    run->AddToThreadLocalFreeList(ptr);
    if (kTraceRosAlloc) {
      LOG(INFO) << "RosAlloc::FreeFromRun() : Freed a slot in a thread local run 0x" << std::hex
                << reinterpret_cast<intptr_t>(run);
    }
    // A thread local run will be kept as a thread local even if it's become all free.
    return bracket_size;
  }
  // Free the slot in the run.
  run->FreeSlot(ptr);
  auto* non_full_runs = &non_full_runs_[idx];
  if (run->IsAllFree()) {
    // It has just become completely free. Free the pages of this run.
    std::set<Run*>::iterator pos = non_full_runs->find(run);
    if (pos != non_full_runs->end()) {
      non_full_runs->erase(pos);
      if (kTraceRosAlloc) {
        LOG(INFO) << "RosAlloc::FreeFromRun() : Erased run 0x" << std::hex
                  << reinterpret_cast<intptr_t>(run) << " from non_full_runs_";
      }
    }
    if (run == current_runs_[idx]) {
      current_runs_[idx] = dedicated_full_run_;
    }
    DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
    DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
    run->ZeroHeaderAndSlotHeaders();
    {
      MutexLock lock_mu(self, lock_);
      FreePages(self, run, true);
    }
  } else {
    // It is not completely free. If it wasn't the current run or
    // already in the non-full run set (i.e., it was full) insert it
    // into the non-full run set.
    if (run != current_runs_[idx]) {
      auto* full_runs = kIsDebugBuild ? &full_runs_[idx] : nullptr;
      auto pos = non_full_runs->find(run);
      if (pos == non_full_runs->end()) {
        DCHECK(run_was_full);
        DCHECK(full_runs->find(run) != full_runs->end());
        if (kIsDebugBuild) {
          full_runs->erase(run);
          if (kTraceRosAlloc) {
            LOG(INFO) << "RosAlloc::FreeFromRun() : Erased run 0x" << std::hex
                      << reinterpret_cast<intptr_t>(run) << " from full_runs_";
          }
        }
        non_full_runs->insert(run);
        DCHECK(!run->IsFull());
        if (kTraceRosAlloc) {
          LOG(INFO) << "RosAlloc::FreeFromRun() : Inserted run 0x" << std::hex
                    << reinterpret_cast<intptr_t>(run)
                    << " into non_full_runs_[" << std::dec << idx << "]";
        }
      }
    }
  }
  return bracket_size;
}

template<bool kUseTail>
std::string RosAlloc::Run::FreeListToStr(SlotFreeList<kUseTail>* free_list) {
  std::string free_list_str;
  const uint8_t idx = size_bracket_idx_;
  const size_t bracket_size = bracketSizes[idx];
  for (Slot* slot = free_list->Head(); slot != nullptr; slot = slot->Next()) {
    bool is_last = slot->Next() == nullptr;
    uintptr_t slot_offset = reinterpret_cast<uintptr_t>(slot) -
        reinterpret_cast<uintptr_t>(FirstSlot());
    DCHECK_EQ(slot_offset % bracket_size, 0U);
    uintptr_t slot_idx = slot_offset / bracket_size;
    if (!is_last) {
      free_list_str.append(StringPrintf("%u-", static_cast<uint32_t>(slot_idx)));
    } else {
      free_list_str.append(StringPrintf("%u", static_cast<uint32_t>(slot_idx)));
    }
  }
  return free_list_str;
}

std::string RosAlloc::Run::Dump() {
  size_t idx = size_bracket_idx_;
  std::ostringstream stream;
  stream << "RosAlloc Run = " << reinterpret_cast<void*>(this)
         << "{ magic_num=" << static_cast<int>(magic_num_)
         << " size_bracket_idx=" << idx
         << " is_thread_local=" << static_cast<int>(is_thread_local_)
         << " to_be_bulk_freed=" << static_cast<int>(to_be_bulk_freed_)
         << " free_list=" << FreeListToStr(&free_list_)
         << " bulk_free_list=" << FreeListToStr(&bulk_free_list_)
         << " thread_local_list=" << FreeListToStr(&thread_local_free_list_)
         << " }" << std::endl;
  return stream.str();
}

void RosAlloc::Run::FreeSlot(void* ptr) {
  DCHECK(!IsThreadLocal());
  const uint8_t idx = size_bracket_idx_;
  const size_t bracket_size = bracketSizes[idx];
  Slot* slot = ToSlot(ptr);
  // Zero out the memory.
  // TODO: Investigate alternate memset since ptr is guaranteed to be aligned to 16.
  memset(slot, 0, bracket_size);
  free_list_.Add(slot);
  if (kTraceRosAlloc) {
    LOG(INFO) << "RosAlloc::Run::FreeSlot() : " << slot
              << ", bracket_size=" << std::dec << bracket_size << ", slot_idx=" << SlotIndex(slot);
  }
}

inline bool RosAlloc::Run::MergeThreadLocalFreeListToFreeList(bool* is_all_free_after_out) {
  DCHECK(IsThreadLocal());
  // Merge the thread local free list into the free list and clear the thread local free list.
  const uint8_t idx = size_bracket_idx_;
  bool thread_local_free_list_size = thread_local_free_list_.Size();
  const size_t size_before = free_list_.Size();
  free_list_.Merge(&thread_local_free_list_);
  const size_t size_after = free_list_.Size();
  DCHECK_EQ(size_before < size_after, thread_local_free_list_size > 0);
  DCHECK_LE(size_before, size_after);
  *is_all_free_after_out = free_list_.Size() == numOfSlots[idx];
  // Return true at least one slot was added to the free list.
  return size_before < size_after;
}

inline void RosAlloc::Run::MergeBulkFreeListToFreeList() {
  DCHECK(!IsThreadLocal());
  // Merge the bulk free list into the free list and clear the bulk free list.
  free_list_.Merge(&bulk_free_list_);
}

inline void RosAlloc::Run::MergeBulkFreeListToThreadLocalFreeList() {
  DCHECK(IsThreadLocal());
  // Merge the bulk free list into the thread local free list and clear the bulk free list.
  thread_local_free_list_.Merge(&bulk_free_list_);
}

inline void RosAlloc::Run::AddToThreadLocalFreeList(void* ptr) {
  DCHECK(IsThreadLocal());
  AddToFreeListShared(ptr, &thread_local_free_list_, __FUNCTION__);
}

inline size_t RosAlloc::Run::AddToBulkFreeList(void* ptr) {
  return AddToFreeListShared(ptr, &bulk_free_list_, __FUNCTION__);
}

inline size_t RosAlloc::Run::AddToFreeListShared(void* ptr,
                                                 SlotFreeList<true>* free_list,
                                                 const char* caller_name) {
  const uint8_t idx = size_bracket_idx_;
  const size_t bracket_size = bracketSizes[idx];
  Slot* slot = ToSlot(ptr);
  memset(slot, 0, bracket_size);
  free_list->Add(slot);
  if (kTraceRosAlloc) {
    LOG(INFO) << "RosAlloc::Run::" << caller_name << "() : " << ptr
              << ", bracket_size=" << std::dec << bracket_size << ", slot_idx=" << SlotIndex(slot);
  }
  return bracket_size;
}

inline void RosAlloc::Run::ZeroHeaderAndSlotHeaders() {
  DCHECK(IsAllFree());
  const uint8_t idx = size_bracket_idx_;
  // Zero the slot header (next pointers).
  for (Slot* slot = free_list_.Head(); slot != nullptr; ) {
    Slot* next_slot = slot->Next();
    slot->Clear();
    slot = next_slot;
  }
  // Zero the header.
  memset(this, 0, headerSizes[idx]);
  // Check that the entire run is all zero.
  if (kIsDebugBuild) {
    const size_t size = numOfPages[idx] * kPageSize;
    const uintptr_t* word_ptr = reinterpret_cast<uintptr_t*>(this);
    for (size_t i = 0; i < size / sizeof(uintptr_t); ++i) {
      CHECK_EQ(word_ptr[i], 0U) << "words don't match at index " << i;
    }
  }
}

inline void RosAlloc::Run::ZeroData() {
  const uint8_t idx = size_bracket_idx_;
  uint8_t* slot_begin = reinterpret_cast<uint8_t*>(FirstSlot());
  memset(slot_begin, 0, numOfSlots[idx] * bracketSizes[idx]);
}

void RosAlloc::Run::InspectAllSlots(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg),
                                    void* arg) {
  size_t idx = size_bracket_idx_;
  uint8_t* slot_base = reinterpret_cast<uint8_t*>(this) + headerSizes[idx];
  size_t num_slots = numOfSlots[idx];
  size_t bracket_size = IndexToBracketSize(idx);
  DCHECK_EQ(slot_base + num_slots * bracket_size,
            reinterpret_cast<uint8_t*>(this) + numOfPages[idx] * kPageSize);
  // Free slots are on the free list and the allocated/used slots are not. We traverse the free list
  // to find out and record which slots are free in the is_free array.
  std::unique_ptr<bool[]> is_free(new bool[num_slots]());  // zero initialized
  for (Slot* slot = free_list_.Head(); slot != nullptr; slot = slot->Next()) {
    size_t slot_idx = SlotIndex(slot);
    DCHECK_LT(slot_idx, num_slots);
    is_free[slot_idx] = true;
  }
  if (IsThreadLocal()) {
    for (Slot* slot = thread_local_free_list_.Head(); slot != nullptr; slot = slot->Next()) {
      size_t slot_idx = SlotIndex(slot);
      DCHECK_LT(slot_idx, num_slots);
      is_free[slot_idx] = true;
    }
  }
  for (size_t slot_idx = 0; slot_idx < num_slots; ++slot_idx) {
    uint8_t* slot_addr = slot_base + slot_idx * bracket_size;
    if (!is_free[slot_idx]) {
      handler(slot_addr, slot_addr + bracket_size, bracket_size, arg);
    } else {
      handler(slot_addr, slot_addr + bracket_size, 0, arg);
    }
  }
}

// If true, read the page map entries in BulkFree() without using the
// lock for better performance, assuming that the existence of an
// allocated chunk/pointer being freed in BulkFree() guarantees that
// the page map entry won't change. Disabled for now.
static constexpr bool kReadPageMapEntryWithoutLockInBulkFree = true;

size_t RosAlloc::BulkFree(Thread* self, void** ptrs, size_t num_ptrs) {
  size_t freed_bytes = 0;
  if ((false)) {
    // Used only to test Free() as GC uses only BulkFree().
    for (size_t i = 0; i < num_ptrs; ++i) {
      freed_bytes += FreeInternal(self, ptrs[i]);
    }
    return freed_bytes;
  }

  WriterMutexLock wmu(self, bulk_free_lock_);

  // First mark slots to free in the bulk free bit map without locking the
  // size bracket locks. On host, unordered_set is faster than vector + flag.
#ifdef __ANDROID__
  std::vector<Run*> runs;
#else
  std::unordered_set<Run*, hash_run, eq_run> runs;
#endif
  for (size_t i = 0; i < num_ptrs; i++) {
    void* ptr = ptrs[i];
    DCHECK_LE(base_, ptr);
    DCHECK_LT(ptr, base_ + footprint_);
    size_t pm_idx = RoundDownToPageMapIndex(ptr);
    Run* run = nullptr;
    if (kReadPageMapEntryWithoutLockInBulkFree) {
      // Read the page map entries without locking the lock.
      uint8_t page_map_entry = page_map_[pm_idx];
      if (kTraceRosAlloc) {
        LOG(INFO) << "RosAlloc::BulkFree() : " << std::hex << ptr << ", pm_idx="
                  << std::dec << pm_idx
                  << ", page_map_entry=" << static_cast<int>(page_map_entry);
      }
      if (LIKELY(page_map_entry == kPageMapRun)) {
        run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
      } else if (LIKELY(page_map_entry == kPageMapRunPart)) {
        size_t pi = pm_idx;
        // Find the beginning of the run.
        do {
          --pi;
          DCHECK_LT(pi, capacity_ / kPageSize);
        } while (page_map_[pi] != kPageMapRun);
        run = reinterpret_cast<Run*>(base_ + pi * kPageSize);
      } else if (page_map_entry == kPageMapLargeObject) {
        MutexLock mu(self, lock_);
        freed_bytes += FreePages(self, ptr, false);
        continue;
      } else {
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_entry);
      }
    } else {
      // Read the page map entries with a lock.
      MutexLock mu(self, lock_);
      DCHECK_LT(pm_idx, page_map_size_);
      uint8_t page_map_entry = page_map_[pm_idx];
      if (kTraceRosAlloc) {
        LOG(INFO) << "RosAlloc::BulkFree() : " << std::hex << ptr << ", pm_idx="
                  << std::dec << pm_idx
                  << ", page_map_entry=" << static_cast<int>(page_map_entry);
      }
      if (LIKELY(page_map_entry == kPageMapRun)) {
        run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
      } else if (LIKELY(page_map_entry == kPageMapRunPart)) {
        size_t pi = pm_idx;
        // Find the beginning of the run.
        do {
          --pi;
          DCHECK_LT(pi, capacity_ / kPageSize);
        } while (page_map_[pi] != kPageMapRun);
        run = reinterpret_cast<Run*>(base_ + pi * kPageSize);
      } else if (page_map_entry == kPageMapLargeObject) {
        freed_bytes += FreePages(self, ptr, false);
        continue;
      } else {
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_entry);
      }
    }
    DCHECK(run != nullptr);
    DCHECK_EQ(run->magic_num_, kMagicNum);
    // Set the bit in the bulk free bit map.
    freed_bytes += run->AddToBulkFreeList(ptr);
#ifdef __ANDROID__
    if (!run->to_be_bulk_freed_) {
      run->to_be_bulk_freed_ = true;
      runs.push_back(run);
    }
#else
    runs.insert(run);
#endif
  }

  // Now, iterate over the affected runs and update the alloc bit map
  // based on the bulk free bit map (for non-thread-local runs) and
  // union the bulk free bit map into the thread-local free bit map
  // (for thread-local runs.)
  for (Run* run : runs) {
#ifdef __ANDROID__
    DCHECK(run->to_be_bulk_freed_);
    run->to_be_bulk_freed_ = false;
#endif
    size_t idx = run->size_bracket_idx_;
    MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
    if (run->IsThreadLocal()) {
      DCHECK_LT(run->size_bracket_idx_, kNumThreadLocalSizeBrackets);
      DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
      DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
      run->MergeBulkFreeListToThreadLocalFreeList();
      if (kTraceRosAlloc) {
        LOG(INFO) << "RosAlloc::BulkFree() : Freed slot(s) in a thread local run 0x"
                  << std::hex << reinterpret_cast<intptr_t>(run);
      }
      DCHECK(run->IsThreadLocal());
      // A thread local run will be kept as a thread local even if
      // it's become all free.
    } else {
      bool run_was_full = run->IsFull();
      run->MergeBulkFreeListToFreeList();
      if (kTraceRosAlloc) {
        LOG(INFO) << "RosAlloc::BulkFree() : Freed slot(s) in a run 0x" << std::hex
                  << reinterpret_cast<intptr_t>(run);
      }
      // Check if the run should be moved to non_full_runs_ or
      // free_page_runs_.
      auto* non_full_runs = &non_full_runs_[idx];
      auto* full_runs = kIsDebugBuild ? &full_runs_[idx] : nullptr;
      if (run->IsAllFree()) {
        // It has just become completely free. Free the pages of the
        // run.
        bool run_was_current = run == current_runs_[idx];
        if (run_was_current) {
          DCHECK(full_runs->find(run) == full_runs->end());
          DCHECK(non_full_runs->find(run) == non_full_runs->end());
          // If it was a current run, reuse it.
        } else if (run_was_full) {
          // If it was full, remove it from the full run set (debug
          // only.)
          if (kIsDebugBuild) {
            std::unordered_set<Run*, hash_run, eq_run>::iterator pos = full_runs->find(run);
            DCHECK(pos != full_runs->end());
            full_runs->erase(pos);
            if (kTraceRosAlloc) {
              LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
                        << reinterpret_cast<intptr_t>(run)
                        << " from full_runs_";
            }
            DCHECK(full_runs->find(run) == full_runs->end());
          }
        } else {
          // If it was in a non full run set, remove it from the set.
          DCHECK(full_runs->find(run) == full_runs->end());
          DCHECK(non_full_runs->find(run) != non_full_runs->end());
          non_full_runs->erase(run);
          if (kTraceRosAlloc) {
            LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
                      << reinterpret_cast<intptr_t>(run)
                      << " from non_full_runs_";
          }
          DCHECK(non_full_runs->find(run) == non_full_runs->end());
        }
        if (!run_was_current) {
          run->ZeroHeaderAndSlotHeaders();
          MutexLock lock_mu(self, lock_);
          FreePages(self, run, true);
        }
      } else {
        // It is not completely free. If it wasn't the current run or
        // already in the non-full run set (i.e., it was full) insert
        // it into the non-full run set.
        if (run == current_runs_[idx]) {
          DCHECK(non_full_runs->find(run) == non_full_runs->end());
          DCHECK(full_runs->find(run) == full_runs->end());
          // If it was a current run, keep it.
        } else if (run_was_full) {
          // If it was full, remove it from the full run set (debug
          // only) and insert into the non-full run set.
          DCHECK(full_runs->find(run) != full_runs->end());
          DCHECK(non_full_runs->find(run) == non_full_runs->end());
          if (kIsDebugBuild) {
            full_runs->erase(run);
            if (kTraceRosAlloc) {
              LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
                        << reinterpret_cast<intptr_t>(run)
                        << " from full_runs_";
            }
          }
          non_full_runs->insert(run);
          if (kTraceRosAlloc) {
            LOG(INFO) << "RosAlloc::BulkFree() : Inserted run 0x" << std::hex
                      << reinterpret_cast<intptr_t>(run)
                      << " into non_full_runs_[" << std::dec << idx;
          }
        } else {
          // If it was not full, so leave it in the non full run set.
          DCHECK(full_runs->find(run) == full_runs->end());
          DCHECK(non_full_runs->find(run) != non_full_runs->end());
        }
      }
    }
  }
  return freed_bytes;
}

std::string RosAlloc::DumpPageMap() {
  std::ostringstream stream;
  stream << "RosAlloc PageMap: " << std::endl;
  lock_.AssertHeld(Thread::Current());
  size_t end = page_map_size_;
  FreePageRun* curr_fpr = nullptr;
  size_t curr_fpr_size = 0;
  size_t remaining_curr_fpr_size = 0;
  size_t num_running_empty_pages = 0;
  for (size_t i = 0; i < end; ++i) {
    uint8_t pm = page_map_[i];
    switch (pm) {
      case kPageMapReleased:
        // Fall-through.
      case kPageMapEmpty: {
        FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
        if (free_page_runs_.find(fpr) != free_page_runs_.end()) {
          // Encountered a fresh free page run.
          DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
          DCHECK(fpr->IsFree());
          DCHECK(curr_fpr == nullptr);
          DCHECK_EQ(curr_fpr_size, static_cast<size_t>(0));
          curr_fpr = fpr;
          curr_fpr_size = fpr->ByteSize(this);
          DCHECK_EQ(curr_fpr_size % kPageSize, static_cast<size_t>(0));
          remaining_curr_fpr_size = curr_fpr_size - kPageSize;
          stream << "[" << i << "]=" << (pm == kPageMapReleased ? "Released" : "Empty")
                 << " (FPR start) fpr_size=" << curr_fpr_size
                 << " remaining_fpr_size=" << remaining_curr_fpr_size << std::endl;
          if (remaining_curr_fpr_size == 0) {
            // Reset at the end of the current free page run.
            curr_fpr = nullptr;
            curr_fpr_size = 0;
          }
          stream << "curr_fpr=0x" << std::hex << reinterpret_cast<intptr_t>(curr_fpr) << std::endl;
          DCHECK_EQ(num_running_empty_pages, static_cast<size_t>(0));
        } else {
          // Still part of the current free page run.
          DCHECK_NE(num_running_empty_pages, static_cast<size_t>(0));
          DCHECK(curr_fpr != nullptr && curr_fpr_size > 0 && remaining_curr_fpr_size > 0);
          DCHECK_EQ(remaining_curr_fpr_size % kPageSize, static_cast<size_t>(0));
          DCHECK_GE(remaining_curr_fpr_size, static_cast<size_t>(kPageSize));
          remaining_curr_fpr_size -= kPageSize;
          stream << "[" << i << "]=Empty (FPR part)"
                 << " remaining_fpr_size=" << remaining_curr_fpr_size << std::endl;
          if (remaining_curr_fpr_size == 0) {
            // Reset at the end of the current free page run.
            curr_fpr = nullptr;
            curr_fpr_size = 0;
          }
        }
        num_running_empty_pages++;
        break;
      }
      case kPageMapLargeObject: {
        DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
        num_running_empty_pages = 0;
        stream << "[" << i << "]=Large (start)" << std::endl;
        break;
      }
      case kPageMapLargeObjectPart:
        DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
        num_running_empty_pages = 0;
        stream << "[" << i << "]=Large (part)" << std::endl;
        break;
      case kPageMapRun: {
        DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
        num_running_empty_pages = 0;
        Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
        size_t idx = run->size_bracket_idx_;
        stream << "[" << i << "]=Run (start)"
               << " idx=" << idx
               << " numOfPages=" << numOfPages[idx]
               << " is_thread_local=" << run->is_thread_local_
               << " is_all_free=" << (run->IsAllFree() ? 1 : 0)
               << std::endl;
        break;
      }
      case kPageMapRunPart:
        DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
        num_running_empty_pages = 0;
        stream << "[" << i << "]=Run (part)" << std::endl;
        break;
      default:
        stream << "[" << i << "]=Unrecognizable page map type: " << pm;
        break;
    }
  }
  return stream.str();
}

size_t RosAlloc::UsableSize(const void* ptr) {
  DCHECK_LE(base_, ptr);
  DCHECK_LT(ptr, base_ + footprint_);
  size_t pm_idx = RoundDownToPageMapIndex(ptr);
  MutexLock mu(Thread::Current(), lock_);
  switch (page_map_[pm_idx]) {
    case kPageMapReleased:
      // Fall-through.
    case kPageMapEmpty:
      LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << ": pm_idx=" << pm_idx << ", ptr="
                 << std::hex << reinterpret_cast<intptr_t>(ptr);
      break;
    case kPageMapLargeObject: {
      size_t num_pages = 1;
      size_t idx = pm_idx + 1;
      size_t end = page_map_size_;
      while (idx < end && page_map_[idx] == kPageMapLargeObjectPart) {
        num_pages++;
        idx++;
      }
      return num_pages * kPageSize;
    }
    case kPageMapLargeObjectPart:
      LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << ": pm_idx=" << pm_idx << ", ptr="
                 << std::hex << reinterpret_cast<intptr_t>(ptr);
      break;
    case kPageMapRun:
    case kPageMapRunPart: {
      // Find the beginning of the run.
      while (page_map_[pm_idx] != kPageMapRun) {
        pm_idx--;
        DCHECK_LT(pm_idx, capacity_ / kPageSize);
      }
      DCHECK_EQ(page_map_[pm_idx], kPageMapRun);
      Run* run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
      DCHECK_EQ(run->magic_num_, kMagicNum);
      size_t idx = run->size_bracket_idx_;
      size_t offset_from_slot_base = reinterpret_cast<const uint8_t*>(ptr)
          - (reinterpret_cast<uint8_t*>(run) + headerSizes[idx]);
      DCHECK_EQ(offset_from_slot_base % bracketSizes[idx], static_cast<size_t>(0));
      return IndexToBracketSize(idx);
    }
    default: {
      LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
      break;
    }
  }
  return 0;
}

bool RosAlloc::Trim() {
  MutexLock mu(Thread::Current(), lock_);
  FreePageRun* last_free_page_run;
  DCHECK_EQ(footprint_ % kPageSize, static_cast<size_t>(0));
  auto it = free_page_runs_.rbegin();
  if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) {
    // Remove the last free page run, if any.
    DCHECK(last_free_page_run->IsFree());
    DCHECK(IsFreePage(ToPageMapIndex(last_free_page_run)));
    DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
    DCHECK_EQ(last_free_page_run->End(this), base_ + footprint_);
    free_page_runs_.erase(last_free_page_run);
    size_t decrement = last_free_page_run->ByteSize(this);
    size_t new_footprint = footprint_ - decrement;
    DCHECK_EQ(new_footprint % kPageSize, static_cast<size_t>(0));
    size_t new_num_of_pages = new_footprint / kPageSize;
    DCHECK_GE(page_map_size_, new_num_of_pages);
    // Zero out the tail of the page map.
    uint8_t* zero_begin = const_cast<uint8_t*>(page_map_) + new_num_of_pages;
    uint8_t* madvise_begin = AlignUp(zero_begin, kPageSize);
    DCHECK_LE(madvise_begin, page_map_mem_map_->End());
    size_t madvise_size = page_map_mem_map_->End() - madvise_begin;
    if (madvise_size > 0) {
      DCHECK_ALIGNED(madvise_begin, kPageSize);
      DCHECK_EQ(RoundUp(madvise_size, kPageSize), madvise_size);
      if (!kMadviseZeroes) {
        memset(madvise_begin, 0, madvise_size);
      }
      CHECK_EQ(madvise(madvise_begin, madvise_size, MADV_DONTNEED), 0);
    }
    if (madvise_begin - zero_begin) {
      memset(zero_begin, 0, madvise_begin - zero_begin);
    }
    page_map_size_ = new_num_of_pages;
    free_page_run_size_map_.resize(new_num_of_pages);
    DCHECK_EQ(free_page_run_size_map_.size(), new_num_of_pages);
    ArtRosAllocMoreCore(this, -(static_cast<intptr_t>(decrement)));
    if (kTraceRosAlloc) {
      LOG(INFO) << "RosAlloc::Trim() : decreased the footprint from "
                << footprint_ << " to " << new_footprint;
    }
    DCHECK_LT(new_footprint, footprint_);
    DCHECK_LT(new_footprint, capacity_);
    footprint_ = new_footprint;
    return true;
  }
  return false;
}

void RosAlloc::InspectAll(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg),
                          void* arg) {
  // Note: no need to use this to release pages as we already do so in FreePages().
  if (handler == nullptr) {
    return;
  }
  MutexLock mu(Thread::Current(), lock_);
  size_t pm_end = page_map_size_;
  size_t i = 0;
  while (i < pm_end) {
    uint8_t pm = page_map_[i];
    switch (pm) {
      case kPageMapReleased:
        // Fall-through.
      case kPageMapEmpty: {
        // The start of a free page run.
        FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
        DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end());
        size_t fpr_size = fpr->ByteSize(this);
        DCHECK_ALIGNED(fpr_size, kPageSize);
        void* start = fpr;
        if (kIsDebugBuild) {
          // In the debug build, the first page of a free page run
          // contains a magic number for debugging. Exclude it.
          start = reinterpret_cast<uint8_t*>(fpr) + kPageSize;
        }
        void* end = reinterpret_cast<uint8_t*>(fpr) + fpr_size;
        handler(start, end, 0, arg);
        size_t num_pages = fpr_size / kPageSize;
        if (kIsDebugBuild) {
          for (size_t j = i + 1; j < i + num_pages; ++j) {
            DCHECK(IsFreePage(j));
          }
        }
        i += fpr_size / kPageSize;
        DCHECK_LE(i, pm_end);
        break;
      }
      case kPageMapLargeObject: {
        // The start of a large object.
        size_t num_pages = 1;
        size_t idx = i + 1;
        while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) {
          num_pages++;
          idx++;
        }
        void* start = base_ + i * kPageSize;
        void* end = base_ + (i + num_pages) * kPageSize;
        size_t used_bytes = num_pages * kPageSize;
        handler(start, end, used_bytes, arg);
        if (kIsDebugBuild) {
          for (size_t j = i + 1; j < i + num_pages; ++j) {
            DCHECK_EQ(page_map_[j], kPageMapLargeObjectPart);
          }
        }
        i += num_pages;
        DCHECK_LE(i, pm_end);
        break;
      }
      case kPageMapLargeObjectPart:
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
        break;
      case kPageMapRun: {
        // The start of a run.
        Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
        DCHECK_EQ(run->magic_num_, kMagicNum);
        // The dedicated full run doesn't contain any real allocations, don't visit the slots in
        // there.
        run->InspectAllSlots(handler, arg);
        size_t num_pages = numOfPages[run->size_bracket_idx_];
        if (kIsDebugBuild) {
          for (size_t j = i + 1; j < i + num_pages; ++j) {
            DCHECK_EQ(page_map_[j], kPageMapRunPart);
          }
        }
        i += num_pages;
        DCHECK_LE(i, pm_end);
        break;
      }
      case kPageMapRunPart:
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
        break;
      default:
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
        break;
    }
  }
}

size_t RosAlloc::Footprint() {
  MutexLock mu(Thread::Current(), lock_);
  return footprint_;
}

size_t RosAlloc::FootprintLimit() {
  MutexLock mu(Thread::Current(), lock_);
  return capacity_;
}

void RosAlloc::SetFootprintLimit(size_t new_capacity) {
  MutexLock mu(Thread::Current(), lock_);
  DCHECK_EQ(RoundUp(new_capacity, kPageSize), new_capacity);
  // Only growing is supported here. But Trim() is supported.
  if (capacity_ < new_capacity) {
    CHECK_LE(new_capacity, max_capacity_);
    capacity_ = new_capacity;
    VLOG(heap) << "new capacity=" << capacity_;
  }
}

// Below may be called by mutator itself just before thread termination.
size_t RosAlloc::RevokeThreadLocalRuns(Thread* thread) {
  Thread* self = Thread::Current();
  size_t free_bytes = 0U;
  for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) {
    MutexLock mu(self, *size_bracket_locks_[idx]);
    Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx));
    CHECK(thread_local_run != nullptr);
    // Invalid means already revoked.
    DCHECK(thread_local_run->IsThreadLocal());
    if (thread_local_run != dedicated_full_run_) {
      // Note the thread local run may not be full here.
      thread->SetRosAllocRun(idx, dedicated_full_run_);
      DCHECK_EQ(thread_local_run->magic_num_, kMagicNum);
      // Count the number of free slots left.
      size_t num_free_slots = thread_local_run->NumberOfFreeSlots();
      free_bytes += num_free_slots * bracketSizes[idx];
      // The above bracket index lock guards thread local free list to avoid race condition
      // with unioning bulk free list to thread local free list by GC thread in BulkFree.
      // If thread local run is true, GC thread will help update thread local free list
      // in BulkFree. And the latest thread local free list will be merged to free list
      // either when this thread local run is full or when revoking this run here. In this
      // case the free list wll be updated. If thread local run is false, GC thread will help
      // merge bulk free list in next BulkFree.
      // Thus no need to merge bulk free list to free list again here.
      bool dont_care;
      thread_local_run->MergeThreadLocalFreeListToFreeList(&dont_care);
      thread_local_run->SetIsThreadLocal(false);
      DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
      DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
      RevokeRun(self, idx, thread_local_run);
    }
  }
  return free_bytes;
}

void RosAlloc::RevokeRun(Thread* self, size_t idx, Run* run) {
  size_bracket_locks_[idx]->AssertHeld(self);
  DCHECK(run != dedicated_full_run_);
  if (run->IsFull()) {
    if (kIsDebugBuild) {
      full_runs_[idx].insert(run);
      DCHECK(full_runs_[idx].find(run) != full_runs_[idx].end());
      if (kTraceRosAlloc) {
        LOG(INFO) << __PRETTY_FUNCTION__  << " : Inserted run 0x" << std::hex
                  << reinterpret_cast<intptr_t>(run)
                  << " into full_runs_[" << std::dec << idx << "]";
      }
    }
  } else if (run->IsAllFree()) {
    run->ZeroHeaderAndSlotHeaders();
    MutexLock mu(self, lock_);
    FreePages(self, run, true);
  } else {
    non_full_runs_[idx].insert(run);
    DCHECK(non_full_runs_[idx].find(run) != non_full_runs_[idx].end());
    if (kTraceRosAlloc) {
      LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex
                << reinterpret_cast<intptr_t>(run)
                << " into non_full_runs_[" << std::dec << idx << "]";
    }
  }
}

void RosAlloc::RevokeThreadUnsafeCurrentRuns() {
  // Revoke the current runs which share the same idx as thread local runs.
  Thread* self = Thread::Current();
  for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) {
    MutexLock mu(self, *size_bracket_locks_[idx]);
    if (current_runs_[idx] != dedicated_full_run_) {
      RevokeRun(self, idx, current_runs_[idx]);
      current_runs_[idx] = dedicated_full_run_;
    }
  }
}

size_t RosAlloc::RevokeAllThreadLocalRuns() {
  // This is called when a mutator thread won't allocate such as at
  // the Zygote creation time or during the GC pause.
  MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_);
  MutexLock mu2(Thread::Current(), *Locks::thread_list_lock_);
  std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
  size_t free_bytes = 0U;
  for (Thread* thread : thread_list) {
    free_bytes += RevokeThreadLocalRuns(thread);
  }
  RevokeThreadUnsafeCurrentRuns();
  return free_bytes;
}

void RosAlloc::AssertThreadLocalRunsAreRevoked(Thread* thread) {
  if (kIsDebugBuild) {
    Thread* self = Thread::Current();
    // Avoid race conditions on the bulk free bit maps with BulkFree() (GC).
    ReaderMutexLock wmu(self, bulk_free_lock_);
    for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) {
      MutexLock mu(self, *size_bracket_locks_[idx]);
      Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx));
      DCHECK(thread_local_run == nullptr || thread_local_run == dedicated_full_run_);
    }
  }
}

void RosAlloc::AssertAllThreadLocalRunsAreRevoked() {
  if (kIsDebugBuild) {
    Thread* self = Thread::Current();
    MutexLock shutdown_mu(self, *Locks::runtime_shutdown_lock_);
    MutexLock thread_list_mu(self, *Locks::thread_list_lock_);
    std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
    for (Thread* t : thread_list) {
      AssertThreadLocalRunsAreRevoked(t);
    }
    for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) {
      MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
      CHECK_EQ(current_runs_[idx], dedicated_full_run_);
    }
  }
}

void RosAlloc::Initialize() {
  // bracketSizes.
  static_assert(kNumRegularSizeBrackets == kNumOfSizeBrackets - 2,
                "There should be two non-regular brackets");
  for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
    if (i < kNumThreadLocalSizeBrackets) {
      bracketSizes[i] = kThreadLocalBracketQuantumSize * (i + 1);
    } else if (i < kNumRegularSizeBrackets) {
      bracketSizes[i] = kBracketQuantumSize * (i - kNumThreadLocalSizeBrackets + 1) +
          (kThreadLocalBracketQuantumSize *  kNumThreadLocalSizeBrackets);
    } else if (i == kNumOfSizeBrackets - 2) {
      bracketSizes[i] = 1 * KB;
    } else {
      DCHECK_EQ(i, kNumOfSizeBrackets - 1);
      bracketSizes[i] = 2 * KB;
    }
    if (kTraceRosAlloc) {
      LOG(INFO) << "bracketSizes[" << i << "]=" << bracketSizes[i];
    }
  }
  // numOfPages.
  for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
    if (i < kNumThreadLocalSizeBrackets) {
      numOfPages[i] = 1;
    } else if (i < (kNumThreadLocalSizeBrackets + kNumRegularSizeBrackets) / 2) {
      numOfPages[i] = 4;
    } else if (i < kNumRegularSizeBrackets) {
      numOfPages[i] = 8;
    } else if (i == kNumOfSizeBrackets - 2) {
      numOfPages[i] = 16;
    } else {
      DCHECK_EQ(i, kNumOfSizeBrackets - 1);
      numOfPages[i] = 32;
    }
    if (kTraceRosAlloc) {
      LOG(INFO) << "numOfPages[" << i << "]=" << numOfPages[i];
    }
  }
  // Compute numOfSlots and slotOffsets.
  for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
    size_t bracket_size = bracketSizes[i];
    size_t run_size = kPageSize * numOfPages[i];
    size_t max_num_of_slots = run_size / bracket_size;
    // Compute the actual number of slots by taking the header and
    // alignment into account.
    size_t fixed_header_size = RoundUp(Run::fixed_header_size(), sizeof(uint64_t));
    DCHECK_EQ(fixed_header_size, 80U);
    size_t header_size = 0;
    size_t num_of_slots = 0;
    // Search for the maximum number of slots that allows enough space
    // for the header.
    for (int s = max_num_of_slots; s >= 0; s--) {
      size_t tmp_slots_size = bracket_size * s;
      size_t tmp_unaligned_header_size = fixed_header_size;
      // Align up the unaligned header size. bracket_size may not be a power of two.
      size_t tmp_header_size = (tmp_unaligned_header_size % bracket_size == 0) ?
          tmp_unaligned_header_size :
          tmp_unaligned_header_size + (bracket_size - tmp_unaligned_header_size % bracket_size);
      DCHECK_EQ(tmp_header_size % bracket_size, 0U);
      DCHECK_EQ(tmp_header_size % sizeof(uint64_t), 0U);
      if (tmp_slots_size + tmp_header_size <= run_size) {
        // Found the right number of slots, that is, there was enough
        // space for the header (including the bit maps.)
        num_of_slots = s;
        header_size = tmp_header_size;
        break;
      }
    }
    DCHECK_GT(num_of_slots, 0U) << i;
    DCHECK_GT(header_size, 0U) << i;
    // Add the padding for the alignment remainder.
    header_size += run_size % bracket_size;
    DCHECK_EQ(header_size + num_of_slots * bracket_size, run_size);
    numOfSlots[i] = num_of_slots;
    headerSizes[i] = header_size;
    if (kTraceRosAlloc) {
      LOG(INFO) << "numOfSlots[" << i << "]=" << numOfSlots[i]
                << ", headerSizes[" << i << "]=" << headerSizes[i];
    }
  }
  // Set up the dedicated full run so that nobody can successfully allocate from it.
  if (kIsDebugBuild) {
    dedicated_full_run_->magic_num_ = kMagicNum;
  }
  // It doesn't matter which size bracket we use since the main goal is to have the allocation
  // fail 100% of the time you attempt to allocate into the dedicated full run.
  dedicated_full_run_->size_bracket_idx_ = 0;
  DCHECK_EQ(dedicated_full_run_->FreeList()->Size(), 0U);  // It looks full.
  dedicated_full_run_->SetIsThreadLocal(true);

  // The smallest bracket size must be at least as large as the sizeof(Slot).
  DCHECK_LE(sizeof(Slot), bracketSizes[0]) << "sizeof(Slot) <= the smallest bracket size";
  // Check the invariants between the max bracket sizes and the number of brackets.
  DCHECK_EQ(kMaxThreadLocalBracketSize, bracketSizes[kNumThreadLocalSizeBrackets - 1]);
  DCHECK_EQ(kMaxRegularBracketSize, bracketSizes[kNumRegularSizeBrackets - 1]);
}

void RosAlloc::BytesAllocatedCallback(void* start ATTRIBUTE_UNUSED, void* end ATTRIBUTE_UNUSED,
                                      size_t used_bytes, void* arg) {
  if (used_bytes == 0) {
    return;
  }
  size_t* bytes_allocated = reinterpret_cast<size_t*>(arg);
  *bytes_allocated += used_bytes;
}

void RosAlloc::ObjectsAllocatedCallback(void* start ATTRIBUTE_UNUSED, void* end ATTRIBUTE_UNUSED,
                                        size_t used_bytes, void* arg) {
  if (used_bytes == 0) {
    return;
  }
  size_t* objects_allocated = reinterpret_cast<size_t*>(arg);
  ++(*objects_allocated);
}

void RosAlloc::Verify() {
  Thread* self = Thread::Current();
  CHECK(Locks::mutator_lock_->IsExclusiveHeld(self))
      << "The mutator locks isn't exclusively locked at " << __PRETTY_FUNCTION__;
  MutexLock thread_list_mu(self, *Locks::thread_list_lock_);
  ReaderMutexLock wmu(self, bulk_free_lock_);
  std::vector<Run*> runs;
  {
    MutexLock lock_mu(self, lock_);
    size_t pm_end = page_map_size_;
    size_t i = 0;
    size_t memory_tool_modifier =  is_running_on_memory_tool_ ?
        2 * ::art::gc::space::kDefaultMemoryToolRedZoneBytes :  // Redzones before and after.
        0;
    while (i < pm_end) {
      uint8_t pm = page_map_[i];
      switch (pm) {
        case kPageMapReleased:
          // Fall-through.
        case kPageMapEmpty: {
          // The start of a free page run.
          FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
          DCHECK_EQ(fpr->magic_num_, kMagicNumFree);
          CHECK(free_page_runs_.find(fpr) != free_page_runs_.end())
              << "An empty page must belong to the free page run set";
          size_t fpr_size = fpr->ByteSize(this);
          CHECK_ALIGNED(fpr_size, kPageSize)
              << "A free page run size isn't page-aligned : " << fpr_size;
          size_t num_pages = fpr_size / kPageSize;
          CHECK_GT(num_pages, static_cast<uintptr_t>(0))
              << "A free page run size must be > 0 : " << fpr_size;
          for (size_t j = i + 1; j < i + num_pages; ++j) {
            CHECK(IsFreePage(j))
                << "A mismatch between the page map table for kPageMapEmpty "
                << " at page index " << j
                << " and the free page run size : page index range : "
                << i << " to " << (i + num_pages) << std::endl << DumpPageMap();
          }
          i += num_pages;
          CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
                              << std::endl << DumpPageMap();
          break;
        }
        case kPageMapLargeObject: {
          // The start of a large object.
          size_t num_pages = 1;
          size_t idx = i + 1;
          while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) {
            num_pages++;
            idx++;
          }
          uint8_t* start = base_ + i * kPageSize;
          if (is_running_on_memory_tool_) {
            start += ::art::gc::space::kDefaultMemoryToolRedZoneBytes;
          }
          mirror::Object* obj = reinterpret_cast<mirror::Object*>(start);
          size_t obj_size = obj->SizeOf();
          CHECK_GT(obj_size + memory_tool_modifier, kLargeSizeThreshold)
              << "A rosalloc large object size must be > " << kLargeSizeThreshold;
          CHECK_EQ(num_pages, RoundUp(obj_size + memory_tool_modifier, kPageSize) / kPageSize)
              << "A rosalloc large object size " << obj_size + memory_tool_modifier
              << " does not match the page map table " << (num_pages * kPageSize)
              << std::endl << DumpPageMap();
          i += num_pages;
          CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
                              << std::endl << DumpPageMap();
          break;
        }
        case kPageMapLargeObjectPart:
          LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl << DumpPageMap();
          break;
        case kPageMapRun: {
          // The start of a run.
          Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
          DCHECK_EQ(run->magic_num_, kMagicNum);
          size_t idx = run->size_bracket_idx_;
          CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << idx;
          size_t num_pages = numOfPages[idx];
          CHECK_GT(num_pages, static_cast<uintptr_t>(0))
              << "Run size must be > 0 : " << num_pages;
          for (size_t j = i + 1; j < i + num_pages; ++j) {
            CHECK_EQ(page_map_[j], kPageMapRunPart)
                << "A mismatch between the page map table for kPageMapRunPart "
                << " at page index " << j
                << " and the run size : page index range " << i << " to " << (i + num_pages)
                << std::endl << DumpPageMap();
          }
          // Don't verify the dedicated_full_run_ since it doesn't have any real allocations.
          runs.push_back(run);
          i += num_pages;
          CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
                              << std::endl << DumpPageMap();
          break;
        }
        case kPageMapRunPart:
          // Fall-through.
        default:
          LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl << DumpPageMap();
          break;
      }
    }
  }
  std::list<Thread*> threads = Runtime::Current()->GetThreadList()->GetList();
  for (Thread* thread : threads) {
    for (size_t i = 0; i < kNumThreadLocalSizeBrackets; ++i) {
      MutexLock brackets_mu(self, *size_bracket_locks_[i]);
      Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i));
      CHECK(thread_local_run != nullptr);
      CHECK(thread_local_run->IsThreadLocal());
      CHECK(thread_local_run == dedicated_full_run_ ||
            thread_local_run->size_bracket_idx_ == i);
    }
  }
  for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
    MutexLock brackets_mu(self, *size_bracket_locks_[i]);
    Run* current_run = current_runs_[i];
    CHECK(current_run != nullptr);
    if (current_run != dedicated_full_run_) {
      // The dedicated full run is currently marked as thread local.
      CHECK(!current_run->IsThreadLocal());
      CHECK_EQ(current_run->size_bracket_idx_, i);
    }
  }
  // Call Verify() here for the lock order.
  for (auto& run : runs) {
    run->Verify(self, this, is_running_on_memory_tool_);
  }
}

void RosAlloc::Run::Verify(Thread* self, RosAlloc* rosalloc, bool running_on_memory_tool) {
  DCHECK_EQ(magic_num_, kMagicNum) << "Bad magic number : " << Dump();
  const size_t idx = size_bracket_idx_;
  CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << Dump();
  uint8_t* slot_base = reinterpret_cast<uint8_t*>(this) + headerSizes[idx];
  const size_t num_slots = numOfSlots[idx];
  size_t bracket_size = IndexToBracketSize(idx);
  CHECK_EQ(slot_base + num_slots * bracket_size,
           reinterpret_cast<uint8_t*>(this) + numOfPages[idx] * kPageSize)
      << "Mismatch in the end address of the run " << Dump();
  // Check that the bulk free list is empty. It's only used during BulkFree().
  CHECK(IsBulkFreeListEmpty()) << "The bulk free isn't empty " << Dump();
  // Check the thread local runs, the current runs, and the run sets.
  if (IsThreadLocal()) {
    // If it's a thread local run, then it must be pointed to by an owner thread.
    bool owner_found = false;
    std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
    for (auto it = thread_list.begin(); it != thread_list.end(); ++it) {
      Thread* thread = *it;
      for (size_t i = 0; i < kNumThreadLocalSizeBrackets; i++) {
        MutexLock mu(self, *rosalloc->size_bracket_locks_[i]);
        Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i));
        if (thread_local_run == this) {
          CHECK(!owner_found)
              << "A thread local run has more than one owner thread " << Dump();
          CHECK_EQ(i, idx)
              << "A mismatching size bracket index in a thread local run " << Dump();
          owner_found = true;
        }
      }
    }
    CHECK(owner_found) << "A thread local run has no owner thread " << Dump();
  } else {
    // If it's not thread local, check that the thread local free list is empty.
    CHECK(IsThreadLocalFreeListEmpty())
        << "A non-thread-local run's thread local free list isn't empty "
        << Dump();
    // Check if it's a current run for the size bracket.
    bool is_current_run = false;
    for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
      MutexLock mu(self, *rosalloc->size_bracket_locks_[i]);
      Run* current_run = rosalloc->current_runs_[i];
      if (idx == i) {
        if (this == current_run) {
          is_current_run = true;
        }
      } else {
        // If the size bucket index does not match, then it must not
        // be a current run.
        CHECK_NE(this, current_run)
            << "A current run points to a run with a wrong size bracket index " << Dump();
      }
    }
    // If it's neither a thread local or current run, then it must be
    // in a run set.
    if (!is_current_run) {
      MutexLock mu(self, rosalloc->lock_);
      auto& non_full_runs = rosalloc->non_full_runs_[idx];
      // If it's all free, it must be a free page run rather than a run.
      CHECK(!IsAllFree()) << "A free run must be in a free page run set " << Dump();
      if (!IsFull()) {
        // If it's not full, it must in the non-full run set.
        CHECK(non_full_runs.find(this) != non_full_runs.end())
            << "A non-full run isn't in the non-full run set " << Dump();
      } else {
        // If it's full, it must in the full run set (debug build only.)
        if (kIsDebugBuild) {
          auto& full_runs = rosalloc->full_runs_[idx];
          CHECK(full_runs.find(this) != full_runs.end())
              << " A full run isn't in the full run set " << Dump();
        }
      }
    }
  }
  // Check each slot.
  size_t memory_tool_modifier = running_on_memory_tool ?
      2 * ::art::gc::space::kDefaultMemoryToolRedZoneBytes :
      0U;
  // TODO: reuse InspectAllSlots().
  std::unique_ptr<bool[]> is_free(new bool[num_slots]());  // zero initialized
  // Mark the free slots and the remaining ones are allocated.
  for (Slot* slot = free_list_.Head(); slot != nullptr; slot = slot->Next()) {
    size_t slot_idx = SlotIndex(slot);
    DCHECK_LT(slot_idx, num_slots);
    is_free[slot_idx] = true;
  }
  if (IsThreadLocal()) {
    for (Slot* slot = thread_local_free_list_.Head(); slot != nullptr; slot = slot->Next()) {
      size_t slot_idx = SlotIndex(slot);
      DCHECK_LT(slot_idx, num_slots);
      is_free[slot_idx] = true;
    }
  }
  for (size_t slot_idx = 0; slot_idx < num_slots; ++slot_idx) {
    uint8_t* slot_addr = slot_base + slot_idx * bracket_size;
    if (running_on_memory_tool) {
      slot_addr += ::art::gc::space::kDefaultMemoryToolRedZoneBytes;
    }
    if (!is_free[slot_idx]) {
      // The slot is allocated
      mirror::Object* obj = reinterpret_cast<mirror::Object*>(slot_addr);
      size_t obj_size = obj->SizeOf();
      CHECK_LE(obj_size + memory_tool_modifier, kLargeSizeThreshold)
          << "A run slot contains a large object " << Dump();
      CHECK_EQ(SizeToIndex(obj_size + memory_tool_modifier), idx)
          << PrettyTypeOf(obj) << " "
          << "obj_size=" << obj_size << "(" << obj_size + memory_tool_modifier << "), idx=" << idx
          << " A run slot contains an object with wrong size " << Dump();
    }
  }
}

size_t RosAlloc::ReleasePages() {
  VLOG(heap) << "RosAlloc::ReleasePages()";
  DCHECK(!DoesReleaseAllPages());
  Thread* self = Thread::Current();
  size_t reclaimed_bytes = 0;
  size_t i = 0;
  // Check the page map size which might have changed due to grow/shrink.
  while (i < page_map_size_) {
    // Reading the page map without a lock is racy but the race is benign since it should only
    // result in occasionally not releasing pages which we could release.
    uint8_t pm = page_map_[i];
    switch (pm) {
      case kPageMapReleased:
        // Fall through.
      case kPageMapEmpty: {
        // This is currently the start of a free page run.
        // Acquire the lock to prevent other threads racing in and modifying the page map.
        MutexLock mu(self, lock_);
        // Check that it's still empty after we acquired the lock since another thread could have
        // raced in and placed an allocation here.
        if (IsFreePage(i)) {
          // Free page runs can start with a released page if we coalesced a released page free
          // page run with an empty page run.
          FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
          // There is a race condition where FreePage can coalesce fpr with the previous
          // free page run before we acquire lock_. In that case free_page_runs_.find will not find
          // a run starting at fpr. To handle this race, we skip reclaiming the page range and go
          // to the next page.
          if (free_page_runs_.find(fpr) != free_page_runs_.end()) {
            size_t fpr_size = fpr->ByteSize(this);
            DCHECK_ALIGNED(fpr_size, kPageSize);
            uint8_t* start = reinterpret_cast<uint8_t*>(fpr);
            reclaimed_bytes += ReleasePageRange(start, start + fpr_size);
            size_t pages = fpr_size / kPageSize;
            CHECK_GT(pages, 0U) << "Infinite loop probable";
            i += pages;
            DCHECK_LE(i, page_map_size_);
            break;
          }
        }
        FALLTHROUGH_INTENDED;
      }
      case kPageMapLargeObject:      // Fall through.
      case kPageMapLargeObjectPart:  // Fall through.
      case kPageMapRun:              // Fall through.
      case kPageMapRunPart:          // Fall through.
        ++i;
        break;  // Skip.
      default:
        LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
        break;
    }
  }
  return reclaimed_bytes;
}

size_t RosAlloc::ReleasePageRange(uint8_t* start, uint8_t* end) {
  DCHECK_ALIGNED(start, kPageSize);
  DCHECK_ALIGNED(end, kPageSize);
  DCHECK_LT(start, end);
  if (kIsDebugBuild) {
    // In the debug build, the first page of a free page run
    // contains a magic number for debugging. Exclude it.
    start += kPageSize;

    // Single pages won't be released.
    if (start == end) {
      return 0;
    }
  }
  if (!kMadviseZeroes) {
    // TODO: Do this when we resurrect the page instead.
    memset(start, 0, end - start);
  }
  CHECK_EQ(madvise(start, end - start, MADV_DONTNEED), 0);
  size_t pm_idx = ToPageMapIndex(start);
  size_t reclaimed_bytes = 0;
  // Calculate reclaimed bytes and upate page map.
  const size_t max_idx = pm_idx + (end - start) / kPageSize;
  for (; pm_idx < max_idx; ++pm_idx) {
    DCHECK(IsFreePage(pm_idx));
    if (page_map_[pm_idx] == kPageMapEmpty) {
      // Mark the page as released and update how many bytes we released.
      reclaimed_bytes += kPageSize;
      page_map_[pm_idx] = kPageMapReleased;
    }
  }
  return reclaimed_bytes;
}

void RosAlloc::LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) {
  Thread* self = Thread::Current();
  size_t largest_continuous_free_pages = 0;
  WriterMutexLock wmu(self, bulk_free_lock_);
  MutexLock mu(self, lock_);
  for (FreePageRun* fpr : free_page_runs_) {
    largest_continuous_free_pages = std::max(largest_continuous_free_pages,
                                             fpr->ByteSize(this));
  }
  if (failed_alloc_bytes > kLargeSizeThreshold) {
    // Large allocation.
    size_t required_bytes = RoundUp(failed_alloc_bytes, kPageSize);
    if (required_bytes > largest_continuous_free_pages) {
      os << "; failed due to fragmentation (required continguous free "
         << required_bytes << " bytes where largest contiguous free "
         <<  largest_continuous_free_pages << " bytes)";
    }
  } else {
    // Non-large allocation.
    size_t required_bytes = numOfPages[SizeToIndex(failed_alloc_bytes)] * kPageSize;
    if (required_bytes > largest_continuous_free_pages) {
      os << "; failed due to fragmentation (required continguous free "
         << required_bytes << " bytes for a new buffer where largest contiguous free "
         <<  largest_continuous_free_pages << " bytes)";
    }
  }
}

}  // namespace allocator
}  // namespace gc
}  // namespace art