runtime/gc/accounting/atomic_stack.h - platform/art - Git at Google

 /*
  * Copyright (C) 2012 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_ACCOUNTING_ATOMIC_STACK_H_
 #define ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_

 #include <sys/mman.h>  // For the PROT_* and MAP_* constants.

 #include <algorithm>
 #include <memory>
 #include <string>

 #include <android-base/logging.h>

 #include "base/atomic.h"
 #include "base/macros.h"
 #include "base/mem_map.h"
 #include "stack_reference.h"

 // This implements a double-ended queue (deque) with various flavors of PushBack operations,
 // as well as PopBack and PopFront operations. We expect that all calls are performed
 // by a single thread (normally the GC). There is one exception, which accounts for the
 // name:
 // - Multiple calls to AtomicPushBack*() and AtomicBumpBack() may be made concurrently,
 // provided no other calls are made at the same time.

 namespace art {
 namespace gc {
 namespace accounting {

 // Internal representation is StackReference<T>, so this only works with mirror::Object or its
 // subclasses.
 template <typename T>
 class AtomicStack {
  public:
   class ObjectComparator {
    public:
     // These two comparators are for std::binary_search.
     bool operator()(const T* a, const StackReference<T>& b) const NO_THREAD_SAFETY_ANALYSIS {
       return a < b.AsMirrorPtr();
     }
     bool operator()(const StackReference<T>& a, const T* b) const NO_THREAD_SAFETY_ANALYSIS {
       return a.AsMirrorPtr() < b;
     }
     // This comparator is for std::sort.
     bool operator()(const StackReference<T>& a, const StackReference<T>& b) const
         NO_THREAD_SAFETY_ANALYSIS {
       return a.AsMirrorPtr() < b.AsMirrorPtr();
     }
   };

   // Capacity is how many elements we can store in the stack.
   static AtomicStack* Create(const std::string& name, size_t growth_limit, size_t capacity) {
     std::unique_ptr<AtomicStack> mark_stack(new AtomicStack(name, growth_limit, capacity));
     mark_stack->Init();
     return mark_stack.release();
   }

   ~AtomicStack() {}

   void Reset() {
     DCHECK(mem_map_.IsValid());
     DCHECK(begin_ != nullptr);
     front_index_.store(0, std::memory_order_relaxed);
     back_index_.store(0, std::memory_order_relaxed);
     debug_is_sorted_ = true;
     mem_map_.MadviseDontNeedAndZero();
   }

   // Beware: Mixing atomic pushes and atomic pops will cause ABA problem.

   // Returns false if we overflowed the stack.
   bool AtomicPushBackIgnoreGrowthLimit(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
     return AtomicPushBackInternal(value, capacity_);
   }

   // Returns false if we overflowed the stack.
   bool AtomicPushBack(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
     return AtomicPushBackInternal(value, growth_limit_);
   }

   // Atomically bump the back index by the given number of
   // slots. Returns false if we overflowed the stack.
   bool AtomicBumpBack(size_t num_slots, StackReference<T>** start_address,
                       StackReference<T>** end_address)
       REQUIRES_SHARED(Locks::mutator_lock_) {
     if (kIsDebugBuild) {
       debug_is_sorted_ = false;
     }
     int32_t index;
     int32_t new_index;
     do {
       index = back_index_.load(std::memory_order_relaxed);
       new_index = index + num_slots;
       if (UNLIKELY(static_cast<size_t>(new_index) >= growth_limit_)) {
         // Stack overflow.
         return false;
       }
     } while (!back_index_.CompareAndSetWeakRelaxed(index, new_index));
     *start_address = begin_ + index;
     *end_address = begin_ + new_index;
     if (kIsDebugBuild) {
       // Check that the memory is zero.
       for (int32_t i = index; i < new_index; ++i) {
         DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr))
             << "i=" << i << " index=" << index << " new_index=" << new_index;
       }
     }
     return true;
   }

   void AssertAllZero() REQUIRES_SHARED(Locks::mutator_lock_) {
     if (kIsDebugBuild) {
       for (size_t i = 0; i < capacity_; ++i) {
         DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr)) << "i=" << i;
       }
     }
   }

   // Bump the back index by the given number of slots. Returns false if this
   // operation will overflow the stack. New elements should be written
   // to [*start_address, *end_address).
   bool BumpBack(size_t num_slots,
                 StackReference<T>** start_address,
                 StackReference<T>** end_address)
       REQUIRES_SHARED(Locks::mutator_lock_) {
     if (kIsDebugBuild) {
       debug_is_sorted_ = false;
     }
     const int32_t index = back_index_.load(std::memory_order_relaxed);
     const int32_t new_index = index + num_slots;
     if (UNLIKELY(static_cast<size_t>(new_index) >= growth_limit_)) {
       // Stack overflow.
       return false;
     }
     back_index_.store(new_index, std::memory_order_relaxed);
     *start_address = begin_ + index;
     *end_address = begin_ + new_index;
     if (kIsDebugBuild) {
       // Check the memory is zero.
       for (int32_t i = index; i < new_index; i++) {
         DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr))
             << "i=" << i << " index=" << index << " new_index=" << new_index;
       }
     }
     return true;
   }

   void PushBack(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
     if (kIsDebugBuild) {
       debug_is_sorted_ = false;
     }
     const int32_t index = back_index_.load(std::memory_order_relaxed);
     DCHECK_LT(static_cast<size_t>(index), growth_limit_);
     back_index_.store(index + 1, std::memory_order_relaxed);
     begin_[index].Assign(value);
   }

   T* PopBack() REQUIRES_SHARED(Locks::mutator_lock_) {
     DCHECK_GT(back_index_.load(std::memory_order_relaxed),
               front_index_.load(std::memory_order_relaxed));
     // Decrement the back index non atomically.
     const int32_t index = back_index_.load(std::memory_order_relaxed) - 1;
     back_index_.store(index, std::memory_order_relaxed);
     T* ret = begin_[index].AsMirrorPtr();
     // In debug builds we expect the stack elements to be null, which may not
     // always be the case if the stack is being reused without resetting it
     // in-between.
     if (kIsDebugBuild) {
       begin_[index].Clear();
     }
     return ret;
   }

   // Take an item from the front of the stack.
   T PopFront() {
     int32_t index = front_index_.load(std::memory_order_relaxed);
     DCHECK_LT(index, back_index_.load(std::memory_order_relaxed));
     front_index_.store(index + 1, std::memory_order_relaxed);
     return begin_[index];
   }

   // Pop a number of elements.
   void PopBackCount(int32_t n) {
     DCHECK_GE(Size(), static_cast<size_t>(n));
     back_index_.store(back_index_.load(std::memory_order_relaxed) - n, std::memory_order_relaxed);
   }

   bool IsEmpty() const {
     return Size() == 0;
   }

   bool IsFull() const {
     return Size() == growth_limit_;
   }

   size_t Size() const {
     DCHECK_LE(front_index_.load(std::memory_order_relaxed),
               back_index_.load(std::memory_order_relaxed));
     return
         back_index_.load(std::memory_order_relaxed) - front_index_.load(std::memory_order_relaxed);
   }

   StackReference<T>* Begin() const {
     return begin_ + front_index_.load(std::memory_order_relaxed);
   }
   StackReference<T>* End() const {
     return begin_ + back_index_.load(std::memory_order_relaxed);
   }

   size_t Capacity() const {
     return capacity_;
   }

   // Will clear the stack.
   void Resize(size_t new_capacity) {
     capacity_ = new_capacity;
     growth_limit_ = new_capacity;
     Init();
   }

   void Sort() {
     int32_t start_back_index = back_index_.load(std::memory_order_relaxed);
     int32_t start_front_index = front_index_.load(std::memory_order_relaxed);
     std::sort(Begin(), End(), ObjectComparator());
     CHECK_EQ(start_back_index, back_index_.load(std::memory_order_relaxed));
     CHECK_EQ(start_front_index, front_index_.load(std::memory_order_relaxed));
     if (kIsDebugBuild) {
       debug_is_sorted_ = true;
     }
   }

   bool ContainsSorted(const T* value) const REQUIRES_SHARED(Locks::mutator_lock_) {
     DCHECK(debug_is_sorted_);
     return std::binary_search(Begin(), End(), value, ObjectComparator());
   }

   bool Contains(const T* value) const REQUIRES_SHARED(Locks::mutator_lock_) {
     for (auto cur = Begin(), end = End(); cur != end; ++cur) {
       if (cur->AsMirrorPtr() == value) {
         return true;
       }
     }
     return false;
   }

  private:
   AtomicStack(const std::string& name, size_t growth_limit, size_t capacity)
       : name_(name),
         back_index_(0),
         front_index_(0),
         begin_(nullptr),
         growth_limit_(growth_limit),
         capacity_(capacity),
         debug_is_sorted_(true) {
   }

   // Returns false if we overflowed the stack.
   bool AtomicPushBackInternal(T* value, size_t limit) ALWAYS_INLINE
       REQUIRES_SHARED(Locks::mutator_lock_) {
     if (kIsDebugBuild) {
       debug_is_sorted_ = false;
     }
     int32_t index;
     do {
       index = back_index_.load(std::memory_order_relaxed);
       if (UNLIKELY(static_cast<size_t>(index) >= limit)) {
         // Stack overflow.
         return false;
       }
     } while (!back_index_.CompareAndSetWeakRelaxed(index, index + 1));
     begin_[index].Assign(value);
     return true;
   }

   // Size in number of elements.
   void Init() {
     std::string error_msg;
     mem_map_ = MemMap::MapAnonymous(name_.c_str(),
                                     capacity_ * sizeof(begin_[0]),
                                     PROT_READ | PROT_WRITE,
                                     /*low_4gb=*/ false,
                                     &error_msg);
     CHECK(mem_map_.IsValid()) << "couldn't allocate mark stack.\n" << error_msg;
     uint8_t* addr = mem_map_.Begin();
     CHECK(addr != nullptr);
     debug_is_sorted_ = true;
     begin_ = reinterpret_cast<StackReference<T>*>(addr);
     Reset();
   }

   // Name of the mark stack.
   std::string name_;
   // Memory mapping of the atomic stack.
   MemMap mem_map_;
   // Back index (index after the last element pushed).
   AtomicInteger back_index_;
   // Front index, used for implementing PopFront.
   AtomicInteger front_index_;
   // Base of the atomic stack.
   StackReference<T>* begin_;
   // Current maximum which we can push back to, must be <= capacity_.
   size_t growth_limit_;
   // Maximum number of elements.
   size_t capacity_;
   // Whether or not the stack is sorted, only updated in debug mode to avoid performance overhead.
   bool debug_is_sorted_;

   DISALLOW_COPY_AND_ASSIGN(AtomicStack);
 };

 using ObjectStack = AtomicStack<mirror::Object>;

 }  // namespace accounting
 }  // namespace gc
 }  // namespace art

 #endif  // ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_
	/*
	* Copyright (C) 2012 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_ACCOUNTING_ATOMIC_STACK_H_
	#define ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_

	#include <sys/mman.h> // For the PROT_* and MAP_* constants.

	#include <algorithm>
	#include <memory>
	#include <string>

	#include <android-base/logging.h>

	#include "base/atomic.h"
	#include "base/macros.h"
	#include "base/mem_map.h"
	#include "stack_reference.h"

	// This implements a double-ended queue (deque) with various flavors of PushBack operations,
	// as well as PopBack and PopFront operations. We expect that all calls are performed
	// by a single thread (normally the GC). There is one exception, which accounts for the
	// name:
	// - Multiple calls to AtomicPushBack*() and AtomicBumpBack() may be made concurrently,
	// provided no other calls are made at the same time.

	namespace art {
	namespace gc {
	namespace accounting {

	// Internal representation is StackReference<T>, so this only works with mirror::Object or its
	// subclasses.
	template <typename T>
	class AtomicStack {
	public:
	class ObjectComparator {
	public:
	// These two comparators are for std::binary_search.
	bool operator()(const T* a, const StackReference<T>& b) const NO_THREAD_SAFETY_ANALYSIS {
	return a < b.AsMirrorPtr();
	}
	bool operator()(const StackReference<T>& a, const T* b) const NO_THREAD_SAFETY_ANALYSIS {
	return a.AsMirrorPtr() < b;
	}
	// This comparator is for std::sort.
	bool operator()(const StackReference<T>& a, const StackReference<T>& b) const
	NO_THREAD_SAFETY_ANALYSIS {
	return a.AsMirrorPtr() < b.AsMirrorPtr();
	}
	};

	// Capacity is how many elements we can store in the stack.
	static AtomicStack* Create(const std::string& name, size_t growth_limit, size_t capacity) {
	std::unique_ptr<AtomicStack> mark_stack(new AtomicStack(name, growth_limit, capacity));
	mark_stack->Init();
	return mark_stack.release();
	}

	~AtomicStack() {}

	void Reset() {
	DCHECK(mem_map_.IsValid());
	DCHECK(begin_ != nullptr);
	front_index_.store(0, std::memory_order_relaxed);
	back_index_.store(0, std::memory_order_relaxed);
	debug_is_sorted_ = true;
	mem_map_.MadviseDontNeedAndZero();
	}

	// Beware: Mixing atomic pushes and atomic pops will cause ABA problem.

	// Returns false if we overflowed the stack.
	bool AtomicPushBackIgnoreGrowthLimit(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
	return AtomicPushBackInternal(value, capacity_);
	}

	// Returns false if we overflowed the stack.
	bool AtomicPushBack(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
	return AtomicPushBackInternal(value, growth_limit_);
	}

	// Atomically bump the back index by the given number of
	// slots. Returns false if we overflowed the stack.
	bool AtomicBumpBack(size_t num_slots, StackReference<T>** start_address,
	StackReference<T>** end_address)
	REQUIRES_SHARED(Locks::mutator_lock_) {
	if (kIsDebugBuild) {
	debug_is_sorted_ = false;
	}
	int32_t index;
	int32_t new_index;
	do {
	index = back_index_.load(std::memory_order_relaxed);
	new_index = index + num_slots;
	if (UNLIKELY(static_cast<size_t>(new_index) >= growth_limit_)) {
	// Stack overflow.
	return false;
	}
	} while (!back_index_.CompareAndSetWeakRelaxed(index, new_index));
	*start_address = begin_ + index;
	*end_address = begin_ + new_index;
	if (kIsDebugBuild) {
	// Check that the memory is zero.
	for (int32_t i = index; i < new_index; ++i) {
	DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr))
	<< "i=" << i << " index=" << index << " new_index=" << new_index;
	}
	}
	return true;
	}

	void AssertAllZero() REQUIRES_SHARED(Locks::mutator_lock_) {
	if (kIsDebugBuild) {
	for (size_t i = 0; i < capacity_; ++i) {
	DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr)) << "i=" << i;
	}
	}
	}

	// Bump the back index by the given number of slots. Returns false if this
	// operation will overflow the stack. New elements should be written
	// to [start_address, end_address).
	bool BumpBack(size_t num_slots,
	StackReference<T>** start_address,
	StackReference<T>** end_address)
	REQUIRES_SHARED(Locks::mutator_lock_) {
	if (kIsDebugBuild) {
	debug_is_sorted_ = false;
	}
	const int32_t index = back_index_.load(std::memory_order_relaxed);
	const int32_t new_index = index + num_slots;
	if (UNLIKELY(static_cast<size_t>(new_index) >= growth_limit_)) {
	// Stack overflow.
	return false;
	}
	back_index_.store(new_index, std::memory_order_relaxed);
	*start_address = begin_ + index;
	*end_address = begin_ + new_index;
	if (kIsDebugBuild) {
	// Check the memory is zero.
	for (int32_t i = index; i < new_index; i++) {
	DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr))
	<< "i=" << i << " index=" << index << " new_index=" << new_index;
	}
	}
	return true;
	}

	void PushBack(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
	if (kIsDebugBuild) {
	debug_is_sorted_ = false;
	}
	const int32_t index = back_index_.load(std::memory_order_relaxed);
	DCHECK_LT(static_cast<size_t>(index), growth_limit_);
	back_index_.store(index + 1, std::memory_order_relaxed);
	begin_[index].Assign(value);
	}

	T* PopBack() REQUIRES_SHARED(Locks::mutator_lock_) {
	DCHECK_GT(back_index_.load(std::memory_order_relaxed),
	front_index_.load(std::memory_order_relaxed));
	// Decrement the back index non atomically.
	const int32_t index = back_index_.load(std::memory_order_relaxed) - 1;
	back_index_.store(index, std::memory_order_relaxed);
	T* ret = begin_[index].AsMirrorPtr();
	// In debug builds we expect the stack elements to be null, which may not
	// always be the case if the stack is being reused without resetting it
	// in-between.
	if (kIsDebugBuild) {
	begin_[index].Clear();
	}
	return ret;
	}

	// Take an item from the front of the stack.
	T PopFront() {
	int32_t index = front_index_.load(std::memory_order_relaxed);
	DCHECK_LT(index, back_index_.load(std::memory_order_relaxed));
	front_index_.store(index + 1, std::memory_order_relaxed);
	return begin_[index];
	}

	// Pop a number of elements.
	void PopBackCount(int32_t n) {
	DCHECK_GE(Size(), static_cast<size_t>(n));
	back_index_.store(back_index_.load(std::memory_order_relaxed) - n, std::memory_order_relaxed);
	}

	bool IsEmpty() const {
	return Size() == 0;
	}

	bool IsFull() const {
	return Size() == growth_limit_;
	}

	size_t Size() const {
	DCHECK_LE(front_index_.load(std::memory_order_relaxed),
	back_index_.load(std::memory_order_relaxed));
	return
	back_index_.load(std::memory_order_relaxed) - front_index_.load(std::memory_order_relaxed);
	}

	StackReference<T>* Begin() const {
	return begin_ + front_index_.load(std::memory_order_relaxed);
	}
	StackReference<T>* End() const {
	return begin_ + back_index_.load(std::memory_order_relaxed);
	}

	size_t Capacity() const {
	return capacity_;
	}

	// Will clear the stack.
	void Resize(size_t new_capacity) {
	capacity_ = new_capacity;
	growth_limit_ = new_capacity;
	Init();
	}

	void Sort() {
	int32_t start_back_index = back_index_.load(std::memory_order_relaxed);
	int32_t start_front_index = front_index_.load(std::memory_order_relaxed);
	std::sort(Begin(), End(), ObjectComparator());
	CHECK_EQ(start_back_index, back_index_.load(std::memory_order_relaxed));
	CHECK_EQ(start_front_index, front_index_.load(std::memory_order_relaxed));
	if (kIsDebugBuild) {
	debug_is_sorted_ = true;
	}
	}

	bool ContainsSorted(const T* value) const REQUIRES_SHARED(Locks::mutator_lock_) {
	DCHECK(debug_is_sorted_);
	return std::binary_search(Begin(), End(), value, ObjectComparator());
	}

	bool Contains(const T* value) const REQUIRES_SHARED(Locks::mutator_lock_) {
	for (auto cur = Begin(), end = End(); cur != end; ++cur) {
	if (cur->AsMirrorPtr() == value) {
	return true;
	}
	}
	return false;
	}

	private:
	AtomicStack(const std::string& name, size_t growth_limit, size_t capacity)
	: name_(name),
	back_index_(0),
	front_index_(0),
	begin_(nullptr),
	growth_limit_(growth_limit),
	capacity_(capacity),
	debug_is_sorted_(true) {
	}

	// Returns false if we overflowed the stack.
	bool AtomicPushBackInternal(T* value, size_t limit) ALWAYS_INLINE
	REQUIRES_SHARED(Locks::mutator_lock_) {
	if (kIsDebugBuild) {
	debug_is_sorted_ = false;
	}
	int32_t index;
	do {
	index = back_index_.load(std::memory_order_relaxed);
	if (UNLIKELY(static_cast<size_t>(index) >= limit)) {
	// Stack overflow.
	return false;
	}
	} while (!back_index_.CompareAndSetWeakRelaxed(index, index + 1));
	begin_[index].Assign(value);
	return true;
	}

	// Size in number of elements.
	void Init() {
	std::string error_msg;
	mem_map_ = MemMap::MapAnonymous(name_.c_str(),
	capacity_ * sizeof(begin_[0]),
	PROT_READ \| PROT_WRITE,
	/low_4gb=/ false,
	&error_msg);
	CHECK(mem_map_.IsValid()) << "couldn't allocate mark stack.\n" << error_msg;
	uint8_t* addr = mem_map_.Begin();
	CHECK(addr != nullptr);
	debug_is_sorted_ = true;
	begin_ = reinterpret_cast<StackReference<T>*>(addr);
	Reset();
	}

	// Name of the mark stack.
	std::string name_;
	// Memory mapping of the atomic stack.
	MemMap mem_map_;
	// Back index (index after the last element pushed).
	AtomicInteger back_index_;
	// Front index, used for implementing PopFront.
	AtomicInteger front_index_;
	// Base of the atomic stack.
	StackReference<T>* begin_;
	// Current maximum which we can push back to, must be <= capacity_.
	size_t growth_limit_;
	// Maximum number of elements.
	size_t capacity_;
	// Whether or not the stack is sorted, only updated in debug mode to avoid performance overhead.
	bool debug_is_sorted_;

	DISALLOW_COPY_AND_ASSIGN(AtomicStack);
	};

	using ObjectStack = AtomicStack<mirror::Object>;

	} // namespace accounting
	} // namespace gc
	} // namespace art

	#endif // ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_