1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_HEAP_POINTER_BLOCK_H_
6#define RUNTIME_VM_HEAP_POINTER_BLOCK_H_
7
8#include "platform/assert.h"
9#include "vm/globals.h"
10#include "vm/os_thread.h"
11#include "vm/tagged_pointer.h"
12
13namespace dart {
14
15// Forward declarations.
16class Isolate;
17class ObjectPointerVisitor;
18
19// A set of ObjectPtr. Must be emptied before destruction (using Pop/Reset).
20template <int Size>
21class PointerBlock {
22 public:
23 enum { kSize = Size };
24
25 void Reset() {
26 top_ = 0;
27 next_ = nullptr;
28 }
29
30 PointerBlock<Size>* next() const { return next_; }
31
32 intptr_t Count() const { return top_; }
33 bool IsFull() const { return Count() == kSize; }
34 bool IsEmpty() const { return Count() == 0; }
35
36 void Push(ObjectPtr obj) {
37 ASSERT(!IsFull());
38 pointers_[top_++] = obj;
39 }
40
41 ObjectPtr Pop() {
42 ASSERT(!IsEmpty());
43 return pointers_[--top_];
44 }
45
46#if defined(TESTING)
47 bool Contains(ObjectPtr obj) const {
48 // Generated code appends to store buffers; tell MemorySanitizer.
49 MSAN_UNPOISON(this, sizeof(*this));
50 for (intptr_t i = 0; i < Count(); i++) {
51 if (pointers_[i] == obj) {
52 return true;
53 }
54 }
55 return false;
56 }
57#endif // TESTING
58
59 static intptr_t top_offset() { return OFFSET_OF(PointerBlock<Size>, top_); }
60 static intptr_t pointers_offset() {
61 return OFFSET_OF(PointerBlock<Size>, pointers_);
62 }
63
64 void VisitObjectPointers(ObjectPointerVisitor* visitor);
65
66 private:
67 PointerBlock() : next_(nullptr), top_(0) {}
68 ~PointerBlock() {
69 ASSERT(IsEmpty()); // Guard against unintentionally discarding pointers.
70 }
71
72 PointerBlock<Size>* next_;
73 int32_t top_;
74 ObjectPtr pointers_[kSize];
75
76 template <int>
77 friend class BlockStack;
78
79 DISALLOW_COPY_AND_ASSIGN(PointerBlock);
80};
81
82// A synchronized collection of pointer blocks of a particular size.
83// This class is meant to be used as a base (note PushBlockImpl is protected).
84// The global list of cached empty blocks is currently per-size.
85template <int BlockSize>
86class BlockStack {
87 public:
88 typedef PointerBlock<BlockSize> Block;
89
90 BlockStack();
91 ~BlockStack();
92 static void Init();
93 static void Cleanup();
94
95 // Partially filled blocks can be reused, and there is an "inifite" supply
96 // of empty blocks (reused or newly allocated). In any case, the caller
97 // takes ownership of the returned block.
98 Block* PopNonFullBlock();
99 Block* PopEmptyBlock();
100 Block* PopNonEmptyBlock();
101
102 // Pops and returns all non-empty blocks as a linked list (owned by caller).
103 Block* TakeBlocks();
104
105 // Discards the contents of all non-empty blocks.
106 void Reset();
107
108 bool IsEmpty();
109
110 protected:
111 class List {
112 public:
113 List() : head_(nullptr), length_(0) {}
114 ~List();
115 void Push(Block* block);
116 Block* Pop();
117 intptr_t length() const { return length_; }
118 bool IsEmpty() const { return head_ == nullptr; }
119 Block* PopAll();
120 Block* Peek() { return head_; }
121
122 private:
123 Block* head_;
124 intptr_t length_;
125 DISALLOW_COPY_AND_ASSIGN(List);
126 };
127
128 // Adds and transfers ownership of the block to the buffer.
129 void PushBlockImpl(Block* block);
130
131 // If needed, trims the global cache of empty blocks.
132 static void TrimGlobalEmpty();
133
134 List full_;
135 List partial_;
136 Mutex mutex_;
137
138 // Note: This is shared on the basis of block size.
139 static const intptr_t kMaxGlobalEmpty = 100;
140 static List* global_empty_;
141 static Mutex* global_mutex_;
142
143 private:
144 DISALLOW_COPY_AND_ASSIGN(BlockStack);
145};
146
147template <typename Stack>
148class BlockWorkList : public ValueObject {
149 public:
150 typedef typename Stack::Block Block;
151
152 explicit BlockWorkList(Stack* stack) : stack_(stack) {
153 work_ = stack_->PopEmptyBlock();
154 }
155
156 ~BlockWorkList() {
157 ASSERT(work_ == nullptr);
158 ASSERT(stack_ == nullptr);
159 }
160
161 // Returns nullptr if no more work was found.
162 ObjectPtr Pop() {
163 ASSERT(work_ != nullptr);
164 if (work_->IsEmpty()) {
165 // TODO(koda): Track over/underflow events and use in heuristics to
166 // distribute work and prevent degenerate flip-flopping.
167 Block* new_work = stack_->PopNonEmptyBlock();
168 if (new_work == nullptr) {
169 return nullptr;
170 }
171 stack_->PushBlock(work_);
172 work_ = new_work;
173 // Generated code appends to marking stacks; tell MemorySanitizer.
174 MSAN_UNPOISON(work_, sizeof(*work_));
175 }
176 return work_->Pop();
177 }
178
179 void Push(ObjectPtr raw_obj) {
180 if (work_->IsFull()) {
181 // TODO(koda): Track over/underflow events and use in heuristics to
182 // distribute work and prevent degenerate flip-flopping.
183 stack_->PushBlock(work_);
184 work_ = stack_->PopEmptyBlock();
185 }
186 work_->Push(raw_obj);
187 }
188
189 void Finalize() {
190 ASSERT(work_->IsEmpty());
191 stack_->PushBlock(work_);
192 work_ = nullptr;
193 // Fail fast on attempts to mark after finalizing.
194 stack_ = nullptr;
195 }
196
197 void AbandonWork() {
198 stack_->PushBlock(work_);
199 work_ = nullptr;
200 stack_ = nullptr;
201 }
202
203 bool IsEmpty() {
204 if (!work_->IsEmpty()) {
205 return false;
206 }
207 return stack_->IsEmpty();
208 }
209
210 private:
211 Block* work_;
212 Stack* stack_;
213};
214
215static const int kStoreBufferBlockSize = 1024;
216class StoreBuffer : public BlockStack<kStoreBufferBlockSize> {
217 public:
218 // Interrupt when crossing this threshold of non-empty blocks in the buffer.
219 static const intptr_t kMaxNonEmpty = 100;
220
221 enum ThresholdPolicy { kCheckThreshold, kIgnoreThreshold };
222
223 // Adds and transfers ownership of the block to the buffer. Optionally
224 // checks the number of non-empty blocks for overflow, and schedules an
225 // interrupt on the current isolate if so.
226 void PushBlock(Block* block, ThresholdPolicy policy);
227
228 // Check whether non-empty blocks have exceeded kMaxNonEmpty (but takes no
229 // action).
230 bool Overflowed();
231
232 void VisitObjectPointers(ObjectPointerVisitor* visitor);
233};
234
235typedef StoreBuffer::Block StoreBufferBlock;
236
237static const int kMarkingStackBlockSize = 64;
238class MarkingStack : public BlockStack<kMarkingStackBlockSize> {
239 public:
240 // Adds and transfers ownership of the block to the buffer.
241 void PushBlock(Block* block) {
242 BlockStack<Block::kSize>::PushBlockImpl(block);
243 }
244};
245
246typedef MarkingStack::Block MarkingStackBlock;
247typedef BlockWorkList<MarkingStack> MarkerWorkList;
248
249static const int kPromotionStackBlockSize = 64;
250class PromotionStack : public BlockStack<kPromotionStackBlockSize> {
251 public:
252 // Adds and transfers ownership of the block to the buffer.
253 void PushBlock(Block* block) {
254 BlockStack<Block::kSize>::PushBlockImpl(block);
255 }
256};
257
258typedef PromotionStack::Block PromotionStackBlock;
259typedef BlockWorkList<PromotionStack> PromotionWorkList;
260
261} // namespace dart
262
263#endif // RUNTIME_VM_HEAP_POINTER_BLOCK_H_
264