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 <sys/mman.h>  // For the PROT_* and MAP_* constants.
21 
22 #include <algorithm>
23 #include <memory>
24 #include <string>
25 
26 #include <android-base/logging.h>
27 
28 #include "base/atomic.h"
29 #include "base/macros.h"
30 #include "base/mem_map.h"
31 #include "stack_reference.h"
32 
33 // This implements a double-ended queue (deque) with various flavors of PushBack operations,
34 // as well as PopBack and PopFront operations. We expect that all calls are performed
35 // by a single thread (normally the GC). There is one exception, which accounts for the
36 // name:
37 // - Multiple calls to AtomicPushBack*() and AtomicBumpBack() may be made concurrently,
38 // provided no other calls are made at the same time.
39 
40 namespace art {
41 namespace gc {
42 namespace accounting {
43 
44 // Internal representation is StackReference<T>, so this only works with mirror::Object or its
45 // subclasses.
46 template <typename T>
47 class AtomicStack {
48  public:
49   class ObjectComparator {
50    public:
51     // These two comparators are for std::binary_search.
operator()52     bool operator()(const T* a, const StackReference<T>& b) const NO_THREAD_SAFETY_ANALYSIS {
53       return a < b.AsMirrorPtr();
54     }
operator()55     bool operator()(const StackReference<T>& a, const T* b) const NO_THREAD_SAFETY_ANALYSIS {
56       return a.AsMirrorPtr() < b;
57     }
58     // This comparator is for std::sort.
operator()59     bool operator()(const StackReference<T>& a, const StackReference<T>& b) const
60         NO_THREAD_SAFETY_ANALYSIS {
61       return a.AsMirrorPtr() < b.AsMirrorPtr();
62     }
63   };
64 
65   // Capacity is how many elements we can store in the stack.
Create(const std::string & name,size_t growth_limit,size_t capacity)66   static AtomicStack* Create(const std::string& name, size_t growth_limit, size_t capacity) {
67     std::unique_ptr<AtomicStack> mark_stack(new AtomicStack(name, growth_limit, capacity));
68     mark_stack->Init();
69     return mark_stack.release();
70   }
71 
~AtomicStack()72   ~AtomicStack() {}
73 
Reset()74   void Reset() {
75     DCHECK(mem_map_.IsValid());
76     DCHECK(begin_ != nullptr);
77     front_index_.store(0, std::memory_order_relaxed);
78     back_index_.store(0, std::memory_order_relaxed);
79     debug_is_sorted_ = true;
80     mem_map_.MadviseDontNeedAndZero();
81   }
82 
83   // Beware: Mixing atomic pushes and atomic pops will cause ABA problem.
84 
85   // Returns false if we overflowed the stack.
AtomicPushBackIgnoreGrowthLimit(T * value)86   bool AtomicPushBackIgnoreGrowthLimit(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
87     return AtomicPushBackInternal(value, capacity_);
88   }
89 
90   // Returns false if we overflowed the stack.
AtomicPushBack(T * value)91   bool AtomicPushBack(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
92     return AtomicPushBackInternal(value, growth_limit_);
93   }
94 
95   // Atomically bump the back index by the given number of
96   // slots. Returns false if we overflowed the stack.
AtomicBumpBack(size_t num_slots,StackReference<T> ** start_address,StackReference<T> ** end_address)97   bool AtomicBumpBack(size_t num_slots, StackReference<T>** start_address,
98                       StackReference<T>** end_address)
99       REQUIRES_SHARED(Locks::mutator_lock_) {
100     if (kIsDebugBuild) {
101       debug_is_sorted_ = false;
102     }
103     int32_t index;
104     int32_t new_index;
105     do {
106       index = back_index_.load(std::memory_order_relaxed);
107       new_index = index + num_slots;
108       if (UNLIKELY(static_cast<size_t>(new_index) >= growth_limit_)) {
109         // Stack overflow.
110         return false;
111       }
112     } while (!back_index_.CompareAndSetWeakRelaxed(index, new_index));
113     *start_address = begin_ + index;
114     *end_address = begin_ + new_index;
115     if (kIsDebugBuild) {
116       // Sanity check that the memory is zero.
117       for (int32_t i = index; i < new_index; ++i) {
118         DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr))
119             << "i=" << i << " index=" << index << " new_index=" << new_index;
120       }
121     }
122     return true;
123   }
124 
AssertAllZero()125   void AssertAllZero() REQUIRES_SHARED(Locks::mutator_lock_) {
126     if (kIsDebugBuild) {
127       for (size_t i = 0; i < capacity_; ++i) {
128         DCHECK_EQ(begin_[i].AsMirrorPtr(), static_cast<T*>(nullptr)) << "i=" << i;
129       }
130     }
131   }
132 
PushBack(T * value)133   void PushBack(T* value) REQUIRES_SHARED(Locks::mutator_lock_) {
134     if (kIsDebugBuild) {
135       debug_is_sorted_ = false;
136     }
137     const int32_t index = back_index_.load(std::memory_order_relaxed);
138     DCHECK_LT(static_cast<size_t>(index), growth_limit_);
139     back_index_.store(index + 1, std::memory_order_relaxed);
140     begin_[index].Assign(value);
141   }
142 
PopBack()143   T* PopBack() REQUIRES_SHARED(Locks::mutator_lock_) {
144     DCHECK_GT(back_index_.load(std::memory_order_relaxed),
145               front_index_.load(std::memory_order_relaxed));
146     // Decrement the back index non atomically.
147     back_index_.store(back_index_.load(std::memory_order_relaxed) - 1, std::memory_order_relaxed);
148     return begin_[back_index_.load(std::memory_order_relaxed)].AsMirrorPtr();
149   }
150 
151   // Take an item from the front of the stack.
PopFront()152   T PopFront() {
153     int32_t index = front_index_.load(std::memory_order_relaxed);
154     DCHECK_LT(index, back_index_.load(std::memory_order_relaxed));
155     front_index_.store(index + 1, std::memory_order_relaxed);
156     return begin_[index];
157   }
158 
159   // Pop a number of elements.
PopBackCount(int32_t n)160   void PopBackCount(int32_t n) {
161     DCHECK_GE(Size(), static_cast<size_t>(n));
162     back_index_.store(back_index_.load(std::memory_order_relaxed) - n, std::memory_order_relaxed);
163   }
164 
IsEmpty()165   bool IsEmpty() const {
166     return Size() == 0;
167   }
168 
IsFull()169   bool IsFull() const {
170     return Size() == growth_limit_;
171   }
172 
Size()173   size_t Size() const {
174     DCHECK_LE(front_index_.load(std::memory_order_relaxed),
175               back_index_.load(std::memory_order_relaxed));
176     return
177         back_index_.load(std::memory_order_relaxed) - front_index_.load(std::memory_order_relaxed);
178   }
179 
Begin()180   StackReference<T>* Begin() const {
181     return begin_ + front_index_.load(std::memory_order_relaxed);
182   }
End()183   StackReference<T>* End() const {
184     return begin_ + back_index_.load(std::memory_order_relaxed);
185   }
186 
Capacity()187   size_t Capacity() const {
188     return capacity_;
189   }
190 
191   // Will clear the stack.
Resize(size_t new_capacity)192   void Resize(size_t new_capacity) {
193     capacity_ = new_capacity;
194     growth_limit_ = new_capacity;
195     Init();
196   }
197 
Sort()198   void Sort() {
199     int32_t start_back_index = back_index_.load(std::memory_order_relaxed);
200     int32_t start_front_index = front_index_.load(std::memory_order_relaxed);
201     std::sort(Begin(), End(), ObjectComparator());
202     CHECK_EQ(start_back_index, back_index_.load(std::memory_order_relaxed));
203     CHECK_EQ(start_front_index, front_index_.load(std::memory_order_relaxed));
204     if (kIsDebugBuild) {
205       debug_is_sorted_ = true;
206     }
207   }
208 
ContainsSorted(const T * value)209   bool ContainsSorted(const T* value) const REQUIRES_SHARED(Locks::mutator_lock_) {
210     DCHECK(debug_is_sorted_);
211     return std::binary_search(Begin(), End(), value, ObjectComparator());
212   }
213 
Contains(const T * value)214   bool Contains(const T* value) const REQUIRES_SHARED(Locks::mutator_lock_) {
215     for (auto cur = Begin(), end = End(); cur != end; ++cur) {
216       if (cur->AsMirrorPtr() == value) {
217         return true;
218       }
219     }
220     return false;
221   }
222 
223  private:
AtomicStack(const std::string & name,size_t growth_limit,size_t capacity)224   AtomicStack(const std::string& name, size_t growth_limit, size_t capacity)
225       : name_(name),
226         back_index_(0),
227         front_index_(0),
228         begin_(nullptr),
229         growth_limit_(growth_limit),
230         capacity_(capacity),
231         debug_is_sorted_(true) {
232   }
233 
234   // Returns false if we overflowed the stack.
AtomicPushBackInternal(T * value,size_t limit)235   bool AtomicPushBackInternal(T* value, size_t limit) ALWAYS_INLINE
236       REQUIRES_SHARED(Locks::mutator_lock_) {
237     if (kIsDebugBuild) {
238       debug_is_sorted_ = false;
239     }
240     int32_t index;
241     do {
242       index = back_index_.load(std::memory_order_relaxed);
243       if (UNLIKELY(static_cast<size_t>(index) >= limit)) {
244         // Stack overflow.
245         return false;
246       }
247     } while (!back_index_.CompareAndSetWeakRelaxed(index, index + 1));
248     begin_[index].Assign(value);
249     return true;
250   }
251 
252   // Size in number of elements.
Init()253   void Init() {
254     std::string error_msg;
255     mem_map_ = MemMap::MapAnonymous(name_.c_str(),
256                                     capacity_ * sizeof(begin_[0]),
257                                     PROT_READ | PROT_WRITE,
258                                     /*low_4gb=*/ false,
259                                     &error_msg);
260     CHECK(mem_map_.IsValid()) << "couldn't allocate mark stack.\n" << error_msg;
261     uint8_t* addr = mem_map_.Begin();
262     CHECK(addr != nullptr);
263     debug_is_sorted_ = true;
264     begin_ = reinterpret_cast<StackReference<T>*>(addr);
265     Reset();
266   }
267 
268   // Name of the mark stack.
269   std::string name_;
270   // Memory mapping of the atomic stack.
271   MemMap mem_map_;
272   // Back index (index after the last element pushed).
273   AtomicInteger back_index_;
274   // Front index, used for implementing PopFront.
275   AtomicInteger front_index_;
276   // Base of the atomic stack.
277   StackReference<T>* begin_;
278   // Current maximum which we can push back to, must be <= capacity_.
279   size_t growth_limit_;
280   // Maximum number of elements.
281   size_t capacity_;
282   // Whether or not the stack is sorted, only updated in debug mode to avoid performance overhead.
283   bool debug_is_sorted_;
284 
285   DISALLOW_COPY_AND_ASSIGN(AtomicStack);
286 };
287 
288 typedef AtomicStack<mirror::Object> ObjectStack;
289 
290 }  // namespace accounting
291 }  // namespace gc
292 }  // namespace art
293 
294 #endif  // ART_RUNTIME_GC_ACCOUNTING_ATOMIC_STACK_H_
295