RosAlloc对象分配过程

// art/runtime/gc/allocator/rosalloc.h
// A combination of SizeToIndex() and RoundToBracketSize().
static size_t SizeToIndexAndBracketSize(size_t size, size_t* bracket_size_out) {
    DCHECK(size <= kLargeSizeThreshold);
    size_t idx;
    size_t bracket_size;
    if (LIKELY(size <= kMaxThreadLocalBracketSize)) {
      bracket_size = RoundUp(size, kThreadLocalBracketQuantumSize);
      idx = bracket_size / kThreadLocalBracketQuantumSize - 1;
    } else if (size <= kMaxRegularBracketSize) {
      bracket_size = RoundUp(size, kBracketQuantumSize);
      idx = ((bracket_size - kMaxThreadLocalBracketSize) / kBracketQuantumSize - 1)
          + kNumThreadLocalSizeBrackets;
    } else if (size <= 1 * KB) {
      bracket_size = 1 * KB;
      idx = kNumOfSizeBrackets - 2;
    } else {
      DCHECK(size <= 2 * KB);
      bracket_size = 2 * KB;
      idx = kNumOfSizeBrackets - 1;
    }
    DCHECK_EQ(idx, SizeToIndex(size)) << idx;
    DCHECK_EQ(bracket_size, IndexToBracketSize(idx)) << idx;
    DCHECK_EQ(bracket_size, bracketSizes[idx]) << idx;
    DCHECK_LE(size, bracket_size) << idx;
    DCHECK(size > kMaxRegularBracketSize ||
           (size <= kMaxThreadLocalBracketSize &&
            bracket_size - size < kThreadLocalBracketQuantumSize) ||
           (size <= kMaxRegularBracketSize && bracket_size - size < kBracketQuantumSize)) << idx;
    *bracket_size_out = bracket_size;
    return idx;
}

// art/runtime/gc/allocator/rosallac-inl.h
template<bool kThreadSafe>
inline ALWAYS_INLINE void* RosAlloc::Alloc(Thread* self, size_t size, size_t* bytes_allocated,
                                           size_t* usable_size,
                                           size_t* bytes_tl_bulk_allocated) {
  if (UNLIKELY(size > kLargeSizeThreshold)) {
    return AllocLargeObject(self, size, bytes_allocated, usable_size, bytes_tl_bulk_allocated);
  }
  void* m;
  if (kThreadSafe) {
    m = AllocFromRun(self, size, bytes_allocated, usable_size, bytes_tl_bulk_allocated);
  } else {
    m = AllocFromRunThreadUnsafe(self, size, bytes_allocated, usable_size,
                                 bytes_tl_bulk_allocated);
  }
  // Check if the returned memory is really all zero.
  if (ShouldCheckZeroMemory() && m != nullptr) {
    uint8_t* bytes = reinterpret_cast<uint8_t*>(m);
    for (size_t i = 0; i < size; ++i) {
      DCHECK_EQ(bytes[i], 0);
    }
  }
  return m;
}

// art/runtime/gc/allocator/rosalloc.cc
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)
  // ...
  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);
}

// art/runtime/gc/allocator/rosalloc.h
 enum PageMapKind {
    kPageMapReleased = 0,     // Zero and released back to the OS.
    kPageMapEmpty,            // Zero but probably dirty.
    kPageMapRun,              // The beginning of a run.
    kPageMapRunPart,          // The non-beginning part of a run.
    kPageMapLargeObject,      // The beginning of a large object.
    kPageMapLargeObjectPart,  // The non-beginning part of a large object.
  };

// art/runtime/gc/allocator/rosalloc.cc
void* RosAlloc::AllocPages(Thread* self, size_t num_pages, uint8_t page_map_type) {
  // ...
  // 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(); // reverse_iterator(end())
    if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) {
      // ...
      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;
    }
    // 以上为获取last_free_page_run
    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;
      // ...
      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);
        // ...
      } else {
        // Otherwise, insert a new free page run at the end.
        FreePageRun* new_free_page_run = reinterpret_cast<FreePageRun*>(base_ + footprint_);
        // ...
        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);
        // ...
      }
      // 以上为重新分配内存
      // ...
      footprint_ = new_footprint;
      // And retry the last free page run.
      it = free_page_runs_.rbegin();
      DCHECK(it != free_page_runs_.rend());
      FreePageRun* fpr = *it;
      // ...
      size_t fpr_byte_size = fpr->ByteSize(this);
      // ...
      free_page_runs_.erase(fpr);
      // ...
      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);
        // ...
        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);
        // ...
        fpr->SetByteSize(this, req_byte_size);
        DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
      }
      res = fpr;
    }
  }

// art/runtime/gc/allocator/rosalloc.h
  // The slot header.
  class Slot {
   public:
    Slot* Next() const {
      return next_;
    }
    void SetNext(Slot* next) {
      next_ = next;
    }
    // The slot right before this slot in terms of the address.
    Slot* Left(size_t bracket_size) {
      return reinterpret_cast<Slot*>(reinterpret_cast<uintptr_t>(this) - bracket_size);
    }
    void Clear() {
      next_ = nullptr;
    }

   private:
    Slot* next_;  // Next slot in the list.
    friend class RosAlloc;
  };
  
  
Slot* FirstSlot() const {
  const uint8_t idx = size_bracket_idx_;
  return reinterpret_cast<Slot*>(reinterpret_cast<uintptr_t>(this) + headerSizes[idx]);
}

Slot* LastSlot() {
  const uint8_t idx = size_bracket_idx_;
  const size_t bracket_size = bracketSizes[idx];
  uintptr_t end = reinterpret_cast<uintptr_t>(End());
  Slot* last_slot = reinterpret_cast<Slot*>(end - bracket_size);
  DCHECK_LE(FirstSlot(), last_slot);
  return last_slot;
}

// art/runtime/gc/allocator/rosalloc.h

void InitFreeList() {
  const uint8_t idx = size_bracket_idx_;
  const size_t bracket_size = bracketSizes[idx];
  Slot* first_slot = FirstSlot();
  // Add backwards so the first slot is at the head of the list.
  for (Slot* slot = LastSlot(); slot >= first_slot; slot = slot->Left(bracket_size)) {
    free_list_.Add(slot);
  }
}

// art/runtime/gc/allocator/rosalloc-inl.h
inline void* RosAlloc::Run::AllocSlot() {
  Slot* slot = free_list_.Remove();
  if (kTraceRosAlloc && slot != nullptr) {
    const uint8_t idx = size_bracket_idx_;
    LOG(INFO) << "RosAlloc::Run::AllocSlot() : " << slot
              << ", bracket_size=" << std::dec << bracketSizes[idx]
              << ", slot_idx=" << SlotIndex(slot);
  }
  return slot;
}

// art/runtime/gc/allocator/rosalloc.cc
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;
}

// art/runtime/gc/allocator/rosalloc.cc
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);
}

// art/runtime/gc/allocator/rosalloc.cc
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)) {
    new_run->size_bracket_idx_ = idx;
    if (kUsePrefetchDuringAllocRun && idx < kNumThreadLocalSizeBrackets) {
      if (kPrefetchNewRunDataByZeroing) {
        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;
}