1d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier/* 2d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * Copyright (C) 2012 The Android Open Source Project 3d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * 4d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * Licensed under the Apache License, Version 2.0 (the "License"); 5d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * you may not use this file except in compliance with the License. 6d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * You may obtain a copy of the License at 7d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * 8d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * http://www.apache.org/licenses/LICENSE-2.0 9d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * 10d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * Unless required by applicable law or agreed to in writing, software 11d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * distributed under the License is distributed on an "AS IS" BASIS, 12d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * See the License for the specific language governing permissions and 14d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier * limitations under the License. 15d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier */ 16d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_ 19d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 20d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier#include <string> 21d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 22d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier#include "atomic_integer.h" 2307ed66b5ae659c452cbe1ab20c3dbf1d6f546461Elliott Hughes#include "base/logging.h" 24761600567d73b23324ae0251e871c15d6849ffd8Elliott Hughes#include "base/macros.h" 25d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier#include "UniquePtr.h" 26d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier#include "mem_map.h" 27d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier#include "utils.h" 28d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 29d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartiernamespace art { 301d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace gc { 311d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace accounting { 32d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 33d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartiertemplate <typename T> 34d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartierclass AtomicStack { 35d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier public: 36d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Capacity is how many elements we can store in the stack. 37d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier static AtomicStack* Create(const std::string& name, size_t capacity) { 38d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier UniquePtr<AtomicStack> mark_stack(new AtomicStack(name, capacity)); 39d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier mark_stack->Init(); 40d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier return mark_stack.release(); 41d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 42d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 431d54e73444e017d3a65234e0f193846f3e27472bIan Rogers ~AtomicStack() {} 44d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 45d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier void Reset() { 46d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK(mem_map_.get() != NULL); 47d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK(begin_ != NULL); 48d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier front_index_ = 0; 49d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier back_index_ = 0; 50f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier debug_is_sorted_ = true; 51d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier int result = madvise(begin_, sizeof(T) * capacity_, MADV_DONTNEED); 52d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier if (result == -1) { 53d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier PLOG(WARNING) << "madvise failed"; 54d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 55d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 56d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 57d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Beware: Mixing atomic pushes and atomic pops will cause ABA problem. 58d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 59d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Returns false if we overflowed the stack. 60d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier bool AtomicPushBack(const T& value) { 61f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier if (kIsDebugBuild) { 62f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier debug_is_sorted_ = false; 63f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier } 6456edc432fa914f7ccfa87ce443e64f5ef475666dIan Rogers int32_t index; 6556edc432fa914f7ccfa87ce443e64f5ef475666dIan Rogers do { 6656edc432fa914f7ccfa87ce443e64f5ef475666dIan Rogers index = back_index_; 6756edc432fa914f7ccfa87ce443e64f5ef475666dIan Rogers if (UNLIKELY(static_cast<size_t>(index) >= capacity_)) { 6856edc432fa914f7ccfa87ce443e64f5ef475666dIan Rogers // Stack overflow. 6956edc432fa914f7ccfa87ce443e64f5ef475666dIan Rogers return false; 7056edc432fa914f7ccfa87ce443e64f5ef475666dIan Rogers } 71b9070095218595a5d6a37ef874df2794c1761030Brian Carlstrom } while (!back_index_.compare_and_swap(index, index + 1)); 72d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier begin_[index] = value; 73d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier return true; 74d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 75d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 76d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier void PushBack(const T& value) { 77f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier if (kIsDebugBuild) { 78f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier debug_is_sorted_ = false; 79f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier } 80d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier int32_t index = back_index_; 81d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK_LT(static_cast<size_t>(index), capacity_); 82d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier back_index_ = index + 1; 83d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier begin_[index] = value; 84d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 85d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 86d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier T PopBack() { 87d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK_GT(back_index_, front_index_); 88d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Decrement the back index non atomically. 89d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier back_index_ = back_index_ - 1; 90d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier return begin_[back_index_]; 91d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 92d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 93d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Take an item from the front of the stack. 94d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier T PopFront() { 95d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier int32_t index = front_index_; 964b95e8fad803ad307fa09c11c08894544e07a731Mathieu Chartier DCHECK_LT(index, back_index_.load()); 97d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier front_index_ = front_index_ + 1; 98d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier return begin_[index]; 99d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 100d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 10194c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier // Pop a number of elements. 10294c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier void PopBackCount(int32_t n) { 10394c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier DCHECK_GE(Size(), static_cast<size_t>(n)); 10494c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier back_index_.fetch_sub(n); 10594c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier } 10694c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier 107d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier bool IsEmpty() const { 108d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier return Size() == 0; 109d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 110d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 111d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t Size() const { 112d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DCHECK_LE(front_index_, back_index_); 113d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier return back_index_ - front_index_; 114d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 115d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 1161d54e73444e017d3a65234e0f193846f3e27472bIan Rogers T* Begin() const { 11794c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier return const_cast<T*>(begin_ + front_index_); 118d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 119d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 1201d54e73444e017d3a65234e0f193846f3e27472bIan Rogers T* End() const { 12194c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier return const_cast<T*>(begin_ + back_index_); 122d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 123d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 124d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t Capacity() const { 125d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier return capacity_; 126d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 127d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 128d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Will clear the stack. 129d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier void Resize(size_t new_capacity) { 130d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier capacity_ = new_capacity; 131d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier Init(); 132d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 133d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 1341d54e73444e017d3a65234e0f193846f3e27472bIan Rogers void Sort() { 135f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier int32_t start_back_index = back_index_.load(); 136f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier int32_t start_front_index = front_index_.load(); 137f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier std::sort(Begin(), End()); 138f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier CHECK_EQ(start_back_index, back_index_.load()); 139f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier CHECK_EQ(start_front_index, front_index_.load()); 140f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier if (kIsDebugBuild) { 141f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier debug_is_sorted_ = true; 1421d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 1431d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 1441d54e73444e017d3a65234e0f193846f3e27472bIan Rogers 145f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier bool ContainsSorted(const T& value) const { 146f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier DCHECK(debug_is_sorted_); 147f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier return std::binary_search(Begin(), End(), value); 148f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier } 149f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier 1501d54e73444e017d3a65234e0f193846f3e27472bIan Rogers bool Contains(const T& value) const { 151f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier return std::find(Begin(), End(), value) != End(); 1521d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 1531d54e73444e017d3a65234e0f193846f3e27472bIan Rogers 154d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier private: 155d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier AtomicStack(const std::string& name, const size_t capacity) 156d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier : name_(name), 157d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier back_index_(0), 158d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier front_index_(0), 159d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier begin_(NULL), 1601d54e73444e017d3a65234e0f193846f3e27472bIan Rogers capacity_(capacity), 161f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier debug_is_sorted_(true) { 162d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 163d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 164d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Size in number of elements. 165d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier void Init() { 166d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier mem_map_.reset(MemMap::MapAnonymous(name_.c_str(), NULL, capacity_ * sizeof(T), PROT_READ | PROT_WRITE)); 1678161c0336b97e11e02c000af357f8f40de2e23e4jeffhao CHECK(mem_map_.get() != NULL) << "couldn't allocate mark stack"; 168d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier byte* addr = mem_map_->Begin(); 169d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier CHECK(addr != NULL); 170f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier debug_is_sorted_ = true; 171d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier begin_ = reinterpret_cast<T*>(addr); 172d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier Reset(); 173d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier } 174d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 175d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Name of the mark stack. 176d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier std::string name_; 177d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 178d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Memory mapping of the atomic stack. 179d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier UniquePtr<MemMap> mem_map_; 180d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 181d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Back index (index after the last element pushed). 182d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier AtomicInteger back_index_; 183d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 184d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Front index, used for implementing PopFront. 185d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier AtomicInteger front_index_; 186d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 187d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Base of the atomic stack. 188d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier T* begin_; 189d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 190d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier // Maximum number of elements. 191d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier size_t capacity_; 192d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 193f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier // Whether or not the stack is sorted, only updated in debug mode to avoid performance overhead. 194f082d3ce16c520b2d039869e8eb3055eda04e591Mathieu Chartier bool debug_is_sorted_; 1951d54e73444e017d3a65234e0f193846f3e27472bIan Rogers 196d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier DISALLOW_COPY_AND_ASSIGN(AtomicStack); 197d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier}; 198d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 1992dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogerstypedef AtomicStack<mirror::Object*> ObjectStack; 2002dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers 2011d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace accounting 2021d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 203d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier} // namespace art 204d8195f19840911a73b1491dfc8e7c18139753731Mathieu Chartier 205fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_ 206