1 /*
2  * Copyright (C) 2012 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_
18 #define ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_
19 
20 #include <algorithm>
21 #include <memory>
22 #include <string>
23 
24 #include "atomic.h"
25 #include "base/logging.h"
26 #include "base/macros.h"
27 #include "mem_map.h"
28 #include "stack.h"
29 
30 namespace art {
31 namespace gc {
32 namespace accounting {
33 
34 // Internal representation is StackReference<T>, so this only works with mirror::Object or it's
35 // subclasses.
36 template <typename T>
37 class AtomicStack {
38  public:
39   class ObjectComparator {
40    public:
41     // These two comparators are for std::binary_search.
operator()42     bool operator()(const T* a, const StackReference<T>& b) const NO_THREAD_SAFETY_ANALYSIS {
43       return a < b.AsMirrorPtr();
44     }
operator()45     bool operator()(const StackReference<T>& a, const T* b) const NO_THREAD_SAFETY_ANALYSIS {
46       return a.AsMirrorPtr() < b;
47     }
48     // This comparator is for std::sort.
operator()49     bool operator()(const StackReference<T>& a, const StackReference<T>& b) const
50         NO_THREAD_SAFETY_ANALYSIS {
51       return a.AsMirrorPtr() < b.AsMirrorPtr();
52     }
53   };
54 
55   // Capacity is how many elements we can store in the stack.
Create(const std::string & name,size_t growth_limit,size_t capacity)56   static AtomicStack* Create(const std::string& name, size_t growth_limit, size_t capacity) {
57     std::unique_ptr<AtomicStack> mark_stack(new AtomicStack(name, growth_limit, capacity));
58     mark_stack->Init();
59     return mark_stack.release();
60   }
61 
~AtomicStack()62   ~AtomicStack() {}
63 
Reset()64   void Reset() {
65     DCHECK(mem_map_.get() != nullptr);
66     DCHECK(begin_ != nullptr);
67     front_index_.StoreRelaxed(0);
68     back_index_.StoreRelaxed(0);
69     debug_is_sorted_ = true;
70     mem_map_->MadviseDontNeedAndZero();
71   }
72 
73   // Beware: Mixing atomic pushes and atomic pops will cause ABA problem.
74 
75   // Returns false if we overflowed the stack.
AtomicPushBackIgnoreGrowthLimit(T * value)76   bool AtomicPushBackIgnoreGrowthLimit(T* value) SHARED_REQUIRES(Locks::mutator_lock_) {
77     return AtomicPushBackInternal(value, capacity_);
78   }
79 
80   // Returns false if we overflowed the stack.
AtomicPushBack(T * value)81   bool AtomicPushBack(T* value) SHARED_REQUIRES(Locks::mutator_lock_) {
82     return AtomicPushBackInternal(value, growth_limit_);
83   }
84 
85   // Atomically bump the back index by the given number of
86   // slots. Returns false if we overflowed the stack.
AtomicBumpBack(size_t num_slots,StackReference<T> ** start_address,StackReference<T> ** end_address)87   bool AtomicBumpBack(size_t num_slots, StackReference<T>** start_address,
88                       StackReference<T>** end_address)
89       SHARED_REQUIRES(Locks::mutator_lock_) {
90     if (kIsDebugBuild) {
91       debug_is_sorted_ = false;
92     }
93     int32_t index;
94     int32_t new_index;
95     do {
96       index = back_index_.LoadRelaxed();
97       new_index = index + num_slots;
98       if (UNLIKELY(static_cast<size_t>(new_index) >= growth_limit_)) {
99         // Stack overflow.
100         return false;
101       }
102     } while (!back_index_.CompareExchangeWeakRelaxed(index, new_index));
103     *start_address = begin_ + index;
104     *end_address = begin_ + new_index;
105     if (kIsDebugBuild) {
106       // Sanity check that the memory is zero.
107       for (int32_t i = index; i < new_index; ++i) {
108         DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr))
109             << "i=" << i << " index=" << index << " new_index=" << new_index;
110       }
111     }
112     return true;
113   }
114 
AssertAllZero()115   void AssertAllZero() SHARED_REQUIRES(Locks::mutator_lock_) {
116     if (kIsDebugBuild) {
117       for (size_t i = 0; i < capacity_; ++i) {
118         DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr)) << "i=" << i;
119       }
120     }
121   }
122 
PushBack(T * value)123   void PushBack(T* value) SHARED_REQUIRES(Locks::mutator_lock_) {
124     if (kIsDebugBuild) {
125       debug_is_sorted_ = false;
126     }
127     const int32_t index = back_index_.LoadRelaxed();
128     DCHECK_LT(static_cast<size_t>(index), growth_limit_);
129     back_index_.StoreRelaxed(index + 1);
130     begin_[index].Assign(value);
131   }
132 
PopBack()133   T* PopBack() SHARED_REQUIRES(Locks::mutator_lock_) {
134     DCHECK_GT(back_index_.LoadRelaxed(), front_index_.LoadRelaxed());
135     // Decrement the back index non atomically.
136     back_index_.StoreRelaxed(back_index_.LoadRelaxed() - 1);
137     return begin_[back_index_.LoadRelaxed()].AsMirrorPtr();
138   }
139 
140   // Take an item from the front of the stack.
PopFront()141   T PopFront() {
142     int32_t index = front_index_.LoadRelaxed();
143     DCHECK_LT(index, back_index_.LoadRelaxed());
144     front_index_.StoreRelaxed(index + 1);
145     return begin_[index];
146   }
147 
148   // Pop a number of elements.
PopBackCount(int32_t n)149   void PopBackCount(int32_t n) {
150     DCHECK_GE(Size(), static_cast<size_t>(n));
151     back_index_.FetchAndSubSequentiallyConsistent(n);
152   }
153 
IsEmpty()154   bool IsEmpty() const {
155     return Size() == 0;
156   }
157 
IsFull()158   bool IsFull() const {
159     return Size() == growth_limit_;
160   }
161 
Size()162   size_t Size() const {
163     DCHECK_LE(front_index_.LoadRelaxed(), back_index_.LoadRelaxed());
164     return back_index_.LoadRelaxed() - front_index_.LoadRelaxed();
165   }
166 
Begin()167   StackReference<T>* Begin() const {
168     return begin_ + front_index_.LoadRelaxed();
169   }
End()170   StackReference<T>* End() const {
171     return begin_ + back_index_.LoadRelaxed();
172   }
173 
Capacity()174   size_t Capacity() const {
175     return capacity_;
176   }
177 
178   // Will clear the stack.
Resize(size_t new_capacity)179   void Resize(size_t new_capacity) {
180     capacity_ = new_capacity;
181     growth_limit_ = new_capacity;
182     Init();
183   }
184 
Sort()185   void Sort() {
186     int32_t start_back_index = back_index_.LoadRelaxed();
187     int32_t start_front_index = front_index_.LoadRelaxed();
188     std::sort(Begin(), End(), ObjectComparator());
189     CHECK_EQ(start_back_index, back_index_.LoadRelaxed());
190     CHECK_EQ(start_front_index, front_index_.LoadRelaxed());
191     if (kIsDebugBuild) {
192       debug_is_sorted_ = true;
193     }
194   }
195 
ContainsSorted(const T * value)196   bool ContainsSorted(const T* value) const SHARED_REQUIRES(Locks::mutator_lock_) {
197     DCHECK(debug_is_sorted_);
198     return std::binary_search(Begin(), End(), value, ObjectComparator());
199   }
200 
Contains(const T * value)201   bool Contains(const T* value) const SHARED_REQUIRES(Locks::mutator_lock_) {
202     for (auto cur = Begin(), end = End(); cur != end; ++cur) {
203       if (cur->AsMirrorPtr() == value) {
204         return true;
205       }
206     }
207     return false;
208   }
209 
210  private:
AtomicStack(const std::string & name,size_t growth_limit,size_t capacity)211   AtomicStack(const std::string& name, size_t growth_limit, size_t capacity)
212       : name_(name),
213         back_index_(0),
214         front_index_(0),
215         begin_(nullptr),
216         growth_limit_(growth_limit),
217         capacity_(capacity),
218         debug_is_sorted_(true) {
219   }
220 
221   // Returns false if we overflowed the stack.
AtomicPushBackInternal(T * value,size_t limit)222   bool AtomicPushBackInternal(T* value, size_t limit) ALWAYS_INLINE
223       SHARED_REQUIRES(Locks::mutator_lock_) {
224     if (kIsDebugBuild) {
225       debug_is_sorted_ = false;
226     }
227     int32_t index;
228     do {
229       index = back_index_.LoadRelaxed();
230       if (UNLIKELY(static_cast<size_t>(index) >= limit)) {
231         // Stack overflow.
232         return false;
233       }
234     } while (!back_index_.CompareExchangeWeakRelaxed(index, index + 1));
235     begin_[index].Assign(value);
236     return true;
237   }
238 
239   // Size in number of elements.
Init()240   void Init() {
241     std::string error_msg;
242     mem_map_.reset(MemMap::MapAnonymous(name_.c_str(), nullptr, capacity_ * sizeof(begin_[0]),
243                                         PROT_READ | PROT_WRITE, false, false, &error_msg));
244     CHECK(mem_map_.get() != nullptr) << "couldn't allocate mark stack.\n" << error_msg;
245     uint8_t* addr = mem_map_->Begin();
246     CHECK(addr != nullptr);
247     debug_is_sorted_ = true;
248     begin_ = reinterpret_cast<StackReference<T>*>(addr);
249     Reset();
250   }
251 
252   // Name of the mark stack.
253   std::string name_;
254   // Memory mapping of the atomic stack.
255   std::unique_ptr<MemMap> mem_map_;
256   // Back index (index after the last element pushed).
257   AtomicInteger back_index_;
258   // Front index, used for implementing PopFront.
259   AtomicInteger front_index_;
260   // Base of the atomic stack.
261   StackReference<T>* begin_;
262   // Current maximum which we can push back to, must be <= capacity_.
263   size_t growth_limit_;
264   // Maximum number of elements.
265   size_t capacity_;
266   // Whether or not the stack is sorted, only updated in debug mode to avoid performance overhead.
267   bool debug_is_sorted_;
268 
269   DISALLOW_COPY_AND_ASSIGN(AtomicStack);
270 };
271 
272 typedef AtomicStack<mirror::Object> ObjectStack;
273 
274 }  // namespace accounting
275 }  // namespace gc
276 }  // namespace art
277 
278 #endif  // ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_
279