text: /*
   * Copyright (C) 2014 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.
   */
  
  #ifndef ART_RUNTIME_GC_SPACE_REGION_SPACE_H_
  #define ART_RUNTIME_GC_SPACE_REGION_SPACE_H_
  
  #include <museum/7.1.2/art/runtime/gc/accounting/read_barrier_table.h>
  #include <museum/7.1.2/art/runtime/object_callbacks.h>
  #include <museum/7.1.2/art/runtime/gc/space/space.h>
  #include <museum/7.1.2/art/runtime/thread.h>
  
  namespace facebook { namespace museum { namespace MUSEUM_VERSION { namespace art {
  namespace gc {
  namespace space {
  
  // A space that consists of equal-sized regions.
  class RegionSpace FINAL : public ContinuousMemMapAllocSpace {
   public:
    typedef void(*WalkCallback)(void *start, void *end, size_t num_bytes, void* callback_arg);
  
    SpaceType GetType() const OVERRIDE {
      return kSpaceTypeRegionSpace;
    }
  
    // Create a region space with the requested sizes. The requested base address is not
    // guaranteed to be granted, if it is required, the caller should call Begin on the returned
    // space to confirm the request was granted.
    static RegionSpace* Create(const std::string& name, size_t capacity, uint8_t* requested_begin);
  
    // Allocate num_bytes, returns null if the space is full.
    mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated,
                          size_t* usable_size, size_t* bytes_tl_bulk_allocated)
        OVERRIDE REQUIRES(!region_lock_);
    // Thread-unsafe allocation for when mutators are suspended, used by the semispace collector.
    mirror::Object* AllocThreadUnsafe(Thread* self, size_t num_bytes, size_t* bytes_allocated,
                                      size_t* usable_size, size_t* bytes_tl_bulk_allocated)
        OVERRIDE REQUIRES(Locks::mutator_lock_) REQUIRES(!region_lock_);
    // The main allocation routine.
    template<bool kForEvac>
    ALWAYS_INLINE mirror::Object* AllocNonvirtual(size_t num_bytes, size_t* bytes_allocated,
                                                  size_t* usable_size,
                                                  size_t* bytes_tl_bulk_allocated)
        REQUIRES(!region_lock_);
    // Allocate/free large objects (objects that are larger than the region size.)
    template<bool kForEvac>
    mirror::Object* AllocLarge(size_t num_bytes, size_t* bytes_allocated, size_t* usable_size,
                               size_t* bytes_tl_bulk_allocated) REQUIRES(!region_lock_);
    void FreeLarge(mirror::Object* large_obj, size_t bytes_allocated) REQUIRES(!region_lock_);
  
    // Return the storage space required by obj.
    size_t AllocationSize(mirror::Object* obj, size_t* usable_size) OVERRIDE
        SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!region_lock_) {
      return AllocationSizeNonvirtual(obj, usable_size);
    }
    size_t AllocationSizeNonvirtual(mirror::Object* obj, size_t* usable_size)
        SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!region_lock_);
  
    size_t Free(Thread*, mirror::Object*) OVERRIDE {
      UNIMPLEMENTED(FATAL);
      return 0;
    }
    size_t FreeList(Thread*, size_t, mirror::Object**) OVERRIDE {
      UNIMPLEMENTED(FATAL);
      return 0;
    }
    accounting::ContinuousSpaceBitmap* GetLiveBitmap() const OVERRIDE {
      // No live bitmap.
      return nullptr;
    }
    accounting::ContinuousSpaceBitmap* GetMarkBitmap() const OVERRIDE {
      // No mark bitmap.
      return nullptr;
    }
  
    void Clear() OVERRIDE REQUIRES(!region_lock_);
  
    void Dump(std::ostream& os) const;
    void DumpRegions(std::ostream& os) REQUIRES(!region_lock_);
    void DumpNonFreeRegions(std::ostream& os) REQUIRES(!region_lock_);
  
    size_t RevokeThreadLocalBuffers(Thread* thread) REQUIRES(!region_lock_);
    void RevokeThreadLocalBuffersLocked(Thread* thread) REQUIRES(region_lock_);
    size_t RevokeAllThreadLocalBuffers()
        REQUIRES(!Locks::runtime_shutdown_lock_, !Locks::thread_list_lock_, !region_lock_);
    void AssertThreadLocalBuffersAreRevoked(Thread* thread) REQUIRES(!region_lock_);
    void AssertAllThreadLocalBuffersAreRevoked()
        REQUIRES(!Locks::runtime_shutdown_lock_, !Locks::thread_list_lock_, !region_lock_);
  
    enum class RegionType : uint8_t {
      kRegionTypeAll,              // All types.
      kRegionTypeFromSpace,        // From-space. To be evacuated.
      kRegionTypeUnevacFromSpace,  // Unevacuated from-space. Not to be evacuated.
      kRegionTypeToSpace,          // To-space.
      kRegionTypeNone,             // None.
    };
  
    enum class RegionState : uint8_t {
      kRegionStateFree,            // Free region.
      kRegionStateAllocated,       // Allocated region.
      kRegionStateLarge,           // Large allocated (allocation larger than the region size).
      kRegionStateLargeTail,       // Large tail (non-first regions of a large allocation).
    };
  
    template<RegionType kRegionType> uint64_t GetBytesAllocatedInternal() REQUIRES(!region_lock_);
    template<RegionType kRegionType> uint64_t GetObjectsAllocatedInternal() REQUIRES(!region_lock_);
    uint64_t GetBytesAllocated() REQUIRES(!region_lock_) {
      return GetBytesAllocatedInternal<RegionType::kRegionTypeAll>();
    }
    uint64_t GetObjectsAllocated() REQUIRES(!region_lock_) {
      return GetObjectsAllocatedInternal<RegionType::kRegionTypeAll>();
    }
    uint64_t GetBytesAllocatedInFromSpace() REQUIRES(!region_lock_) {
      return GetBytesAllocatedInternal<RegionType::kRegionTypeFromSpace>();
    }
    uint64_t GetObjectsAllocatedInFromSpace() REQUIRES(!region_lock_) {
      return GetObjectsAllocatedInternal<RegionType::kRegionTypeFromSpace>();
    }
    uint64_t GetBytesAllocatedInUnevacFromSpace() REQUIRES(!region_lock_) {
      return GetBytesAllocatedInternal<RegionType::kRegionTypeUnevacFromSpace>();
    }
    uint64_t GetObjectsAllocatedInUnevacFromSpace() REQUIRES(!region_lock_) {
      return GetObjectsAllocatedInternal<RegionType::kRegionTypeUnevacFromSpace>();
    }
  
    bool CanMoveObjects() const OVERRIDE {
      return true;
    }
  
    bool Contains(const mirror::Object* obj) const {
      const uint8_t* byte_obj = reinterpret_cast<const uint8_t*>(obj);
      return byte_obj >= Begin() && byte_obj < Limit();
    }
  
    RegionSpace* AsRegionSpace() OVERRIDE {
      return this;
    }
  
    // Go through all of the blocks and visit the continuous objects.
    void Walk(ObjectCallback* callback, void* arg)
        REQUIRES(Locks::mutator_lock_) {
      WalkInternal<false>(callback, arg);
    }
  
    void WalkToSpace(ObjectCallback* callback, void* arg)
        REQUIRES(Locks::mutator_lock_) {
      WalkInternal<true>(callback, arg);
    }
  
    accounting::ContinuousSpaceBitmap::SweepCallback* GetSweepCallback() OVERRIDE {
      return nullptr;
    }
    void LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) OVERRIDE
        SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!region_lock_);
  
    // Object alignment within the space.
    static constexpr size_t kAlignment = kObjectAlignment;
    // The region size.
    static constexpr size_t kRegionSize = 1 * MB;
  
    bool IsInFromSpace(mirror::Object* ref) {
      if (HasAddress(ref)) {
        Region* r = RefToRegionUnlocked(ref);
        return r->IsInFromSpace();
      }
      return false;
    }
  
    bool IsInUnevacFromSpace(mirror::Object* ref) {
      if (HasAddress(ref)) {
        Region* r = RefToRegionUnlocked(ref);
        return r->IsInUnevacFromSpace();
      }
      return false;
    }
  
    bool IsInToSpace(mirror::Object* ref) {
      if (HasAddress(ref)) {
        Region* r = RefToRegionUnlocked(ref);
        return r->IsInToSpace();
      }
      return false;
    }
  
    RegionType GetRegionType(mirror::Object* ref) {
      if (HasAddress(ref)) {
        Region* r = RefToRegionUnlocked(ref);
        return r->Type();
      }
      return RegionType::kRegionTypeNone;
    }
  
    void SetFromSpace(accounting::ReadBarrierTable* rb_table, bool force_evacuate_all)
        REQUIRES(!region_lock_);
  
    size_t FromSpaceSize() REQUIRES(!region_lock_);
    size_t UnevacFromSpaceSize() REQUIRES(!region_lock_);
    size_t ToSpaceSize() REQUIRES(!region_lock_);
    void ClearFromSpace() REQUIRES(!region_lock_);
  
    void AddLiveBytes(mirror::Object* ref, size_t alloc_size) {
      Region* reg = RefToRegionUnlocked(ref);
      reg->AddLiveBytes(alloc_size);
    }
  
    void AssertAllRegionLiveBytesZeroOrCleared() REQUIRES(!region_lock_);
  
    void RecordAlloc(mirror::Object* ref) REQUIRES(!region_lock_);
    bool AllocNewTlab(Thread* self) REQUIRES(!region_lock_);
  
    uint32_t Time() {
      return time_;
    }
  
   private:
    RegionSpace(const std::string& name, MemMap* mem_map);
  
    template<bool kToSpaceOnly>
    void WalkInternal(ObjectCallback* callback, void* arg) NO_THREAD_SAFETY_ANALYSIS;
  
    class Region {
     public:
      Region()
          : idx_(static_cast<size_t>(-1)),
            begin_(nullptr), top_(nullptr), end_(nullptr),
            state_(RegionState::kRegionStateAllocated), type_(RegionType::kRegionTypeToSpace),
            objects_allocated_(0), alloc_time_(0), live_bytes_(static_cast<size_t>(-1)),
            is_newly_allocated_(false), is_a_tlab_(false), thread_(nullptr) {}
  
      Region(size_t idx, uint8_t* begin, uint8_t* end)
          : idx_(idx), begin_(begin), top_(begin), end_(end),
            state_(RegionState::kRegionStateFree), type_(RegionType::kRegionTypeNone),
            objects_allocated_(0), alloc_time_(0), live_bytes_(static_cast<size_t>(-1)),
            is_newly_allocated_(false), is_a_tlab_(false), thread_(nullptr) {
        DCHECK_LT(begin, end);
        DCHECK_EQ(static_cast<size_t>(end - begin), kRegionSize);
      }
  
      RegionState State() const {
        return state_;
      }
  
      RegionType Type() const {
        return type_;
      }
  
      void Clear() {
        top_ = begin_;
        state_ = RegionState::kRegionStateFree;
        type_ = RegionType::kRegionTypeNone;
        objects_allocated_ = 0;
        alloc_time_ = 0;
        live_bytes_ = static_cast<size_t>(-1);
        if (!kMadviseZeroes) {
          memset(begin_, 0, end_ - begin_);
        }
        madvise(begin_, end_ - begin_, MADV_DONTNEED);
        is_newly_allocated_ = false;
        is_a_tlab_ = false;
        thread_ = nullptr;
      }
  
      ALWAYS_INLINE mirror::Object* Alloc(size_t num_bytes, size_t* bytes_allocated,
                                          size_t* usable_size,
                                          size_t* bytes_tl_bulk_allocated);
  
      bool IsFree() const {
        bool is_free = state_ == RegionState::kRegionStateFree;
        if (is_free) {
          DCHECK(IsInNoSpace());
          DCHECK_EQ(begin_, top_);
          DCHECK_EQ(objects_allocated_, 0U);
        }
        return is_free;
      }
  
      // Given a free region, declare it non-free (allocated).
      void Unfree(uint32_t alloc_time) {
        DCHECK(IsFree());
        state_ = RegionState::kRegionStateAllocated;
        type_ = RegionType::kRegionTypeToSpace;
        alloc_time_ = alloc_time;
      }
  
      void UnfreeLarge(uint32_t alloc_time) {
        DCHECK(IsFree());
        state_ = RegionState::kRegionStateLarge;
        type_ = RegionType::kRegionTypeToSpace;
        alloc_time_ = alloc_time;
      }
  
      void UnfreeLargeTail(uint32_t alloc_time) {
        DCHECK(IsFree());
        state_ = RegionState::kRegionStateLargeTail;
        type_ = RegionType::kRegionTypeToSpace;
        alloc_time_ = alloc_time;
      }
  
      void SetNewlyAllocated() {
        is_newly_allocated_ = true;
      }
  
      // Non-large, non-large-tail allocated.
      bool IsAllocated() const {
        return state_ == RegionState::kRegionStateAllocated;
      }
  
      // Large allocated.
      bool IsLarge() const {
        bool is_large = state_ == RegionState::kRegionStateLarge;
        if (is_large) {
          DCHECK_LT(begin_ + 1 * MB, top_);
        }
        return is_large;
      }
  
      // Large-tail allocated.
      bool IsLargeTail() const {
        bool is_large_tail = state_ == RegionState::kRegionStateLargeTail;
        if (is_large_tail) {
          DCHECK_EQ(begin_, top_);
        }
        return is_large_tail;
      }
  
      size_t Idx() const {
        return idx_;
      }
  
      bool IsInFromSpace() const {
        return type_ == RegionType::kRegionTypeFromSpace;
      }
  
      bool IsInToSpace() const {
        return type_ == RegionType::kRegionTypeToSpace;
      }
  
      bool IsInUnevacFromSpace() const {
        return type_ == RegionType::kRegionTypeUnevacFromSpace;
      }
  
      bool IsInNoSpace() const {
        return type_ == RegionType::kRegionTypeNone;
      }
  
      void SetAsFromSpace() {
        DCHECK(!IsFree() && IsInToSpace());
        type_ = RegionType::kRegionTypeFromSpace;
        live_bytes_ = static_cast<size_t>(-1);
      }
  
      void SetAsUnevacFromSpace() {
        DCHECK(!IsFree() && IsInToSpace());
        type_ = RegionType::kRegionTypeUnevacFromSpace;
        live_bytes_ = 0U;
      }
  
      void SetUnevacFromSpaceAsToSpace() {
        DCHECK(!IsFree() && IsInUnevacFromSpace());
        type_ = RegionType::kRegionTypeToSpace;
      }
  
      ALWAYS_INLINE bool ShouldBeEvacuated();
  
      void AddLiveBytes(size_t live_bytes) {
        DCHECK(IsInUnevacFromSpace());
        DCHECK(!IsLargeTail());
        DCHECK_NE(live_bytes_, static_cast<size_t>(-1));
        live_bytes_ += live_bytes;
        DCHECK_LE(live_bytes_, BytesAllocated());
      }
  
      size_t LiveBytes() const {
        return live_bytes_;
      }
  
      uint GetLivePercent() const {
        DCHECK(IsInToSpace());
        DCHECK(!IsLargeTail());
        DCHECK_NE(live_bytes_, static_cast<size_t>(-1));
        DCHECK_LE(live_bytes_, BytesAllocated());
        size_t bytes_allocated = RoundUp(BytesAllocated(), kRegionSize);
        DCHECK_GE(bytes_allocated, 0U);
        uint result = (live_bytes_ * 100U) / bytes_allocated;
        DCHECK_LE(result, 100U);
        return result;
      }
  
      size_t BytesAllocated() const {
        if (IsLarge()) {
          DCHECK_LT(begin_ + kRegionSize, top_);
          return static_cast<size_t>(top_ - begin_);
        } else if (IsLargeTail()) {
          DCHECK_EQ(begin_, top_);
          return 0;
        } else {
          DCHECK(IsAllocated()) << static_cast<uint>(state_);
          DCHECK_LE(begin_, top_);
          size_t bytes = static_cast<size_t>(top_ - begin_);
          DCHECK_LE(bytes, kRegionSize);
          return bytes;
        }
      }
  
      size_t ObjectsAllocated() const {
        if (IsLarge()) {
          DCHECK_LT(begin_ + 1 * MB, top_);
          DCHECK_EQ(objects_allocated_, 0U);
          return 1;
        } else if (IsLargeTail()) {
          DCHECK_EQ(begin_, top_);
          DCHECK_EQ(objects_allocated_, 0U);
          return 0;
        } else {
          DCHECK(IsAllocated()) << static_cast<uint>(state_);
          return objects_allocated_;
        }
      }
  
      uint8_t* Begin() const {
        return begin_;
      }
  
      uint8_t* Top() const {
        return top_;
      }
  
      void SetTop(uint8_t* new_top) {
        top_ = new_top;
      }
  
      uint8_t* End() const {
        return end_;
      }
  
      bool Contains(mirror::Object* ref) const {
        return begin_ <= reinterpret_cast<uint8_t*>(ref) && reinterpret_cast<uint8_t*>(ref) < end_;
      }
  
      void Dump(std::ostream& os) const;
  
      void RecordThreadLocalAllocations(size_t num_objects, size_t num_bytes) {
        DCHECK(IsAllocated());
        DCHECK_EQ(objects_allocated_, 0U);
        DCHECK_EQ(top_, end_);
        objects_allocated_ = num_objects;
        top_ = begin_ + num_bytes;
        DCHECK_EQ(top_, end_);
      }
  
     private:
      size_t idx_;                   // The region's index in the region space.
      uint8_t* begin_;               // The begin address of the region.
      // Can't use Atomic<uint8_t*> as Atomic's copy operator is implicitly deleted.
      uint8_t* top_;                 // The current position of the allocation.
      uint8_t* end_;                 // The end address of the region.
      RegionState state_;            // The region state (see RegionState).
      RegionType type_;              // The region type (see RegionType).
      uint64_t objects_allocated_;   // The number of objects allocated.
      uint32_t alloc_time_;          // The allocation time of the region.
      size_t live_bytes_;            // The live bytes. Used to compute the live percent.
      bool is_newly_allocated_;      // True if it's allocated after the last collection.
      bool is_a_tlab_;               // True if it's a tlab.
      Thread* thread_;               // The owning thread if it's a tlab.
  
      friend class RegionSpace;
    };
  
    Region* RefToRegion(mirror::Object* ref) REQUIRES(!region_lock_) {
      MutexLock mu(Thread::Current(), region_lock_);
      return RefToRegionLocked(ref);
    }
  
    Region* RefToRegionUnlocked(mirror::Object* ref) NO_THREAD_SAFETY_ANALYSIS {
      // For a performance reason (this is frequently called via
      // IsInFromSpace() etc.) we avoid taking a lock here. Note that
      // since we only change a region from to-space to from-space only
      // during a pause (SetFromSpace()) and from from-space to free
      // (after GC is done) as long as ref is a valid reference into an
      // allocated region, it's safe to access the region state without
      // the lock.
      return RefToRegionLocked(ref);
    }
  
    Region* RefToRegionLocked(mirror::Object* ref) REQUIRES(region_lock_) {
      DCHECK(HasAddress(ref));
      uintptr_t offset = reinterpret_cast<uintptr_t>(ref) - reinterpret_cast<uintptr_t>(Begin());
      size_t reg_idx = offset / kRegionSize;
      DCHECK_LT(reg_idx, num_regions_);
      Region* reg = &regions_[reg_idx];
      DCHECK_EQ(reg->Idx(), reg_idx);
      DCHECK(reg->Contains(ref));
      return reg;
    }
  
    mirror::Object* GetNextObject(mirror::Object* obj)
        SHARED_REQUIRES(Locks::mutator_lock_);
  
    Mutex region_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
  
    uint32_t time_;                  // The time as the number of collections since the startup.
    size_t num_regions_;             // The number of regions in this space.
    size_t num_non_free_regions_;    // The number of non-free regions in this space.
    std::unique_ptr<Region[]> regions_ GUARDED_BY(region_lock_);
                                     // The pointer to the region array.
    Region* current_region_;         // The region that's being allocated currently.
    Region* evac_region_;            // The region that's being evacuated to currently.
    Region full_region_;             // The dummy/sentinel region that looks full.
  
    DISALLOW_COPY_AND_ASSIGN(RegionSpace);
  };
  
  std::ostream& operator<<(std::ostream& os, const RegionSpace::RegionState& value);
  std::ostream& operator<<(std::ostream& os, const RegionSpace::RegionType& value);
  
  }  // namespace space
  }  // namespace gc
  } } } } // namespace facebook::museum::MUSEUM_VERSION::art
  
  #endif  // ART_RUNTIME_GC_SPACE_REGION_SPACE_H_
  