1// Copyright (c) 2013, 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_WEAK_TABLE_H_
6#define RUNTIME_VM_HEAP_WEAK_TABLE_H_
7
8#include "vm/globals.h"
9
10#include "platform/assert.h"
11#include "vm/lockers.h"
12#include "vm/raw_object.h"
13
14namespace dart {
15
16class WeakTable {
17 public:
18 static constexpr intptr_t kNoValue = 0;
19
20 WeakTable() : WeakTable(kMinSize) {}
21 explicit WeakTable(intptr_t size) : used_(0), count_(0) {
22 ASSERT(size >= 0);
23 ASSERT(Utils::IsPowerOfTwo(kMinSize));
24 if (size < kMinSize) {
25 size = kMinSize;
26 }
27 // Get a max size that avoids overflows.
28 const intptr_t kMaxSize =
29 (kIntptrOne << (kBitsPerWord - 2)) / (kEntrySize * kWordSize);
30 ASSERT(Utils::IsPowerOfTwo(kMaxSize));
31 if (size > kMaxSize) {
32 size = kMaxSize;
33 }
34 size_ = size;
35 ASSERT(Utils::IsPowerOfTwo(size_));
36 data_ = reinterpret_cast<intptr_t*>(malloc(size: size_ * kEntrySize * kWordSize));
37 for (intptr_t i = 0; i < size_; i++) {
38 data_[ObjectIndex(i)] = kNoEntry;
39 data_[ValueIndex(i)] = kNoValue;
40 }
41 }
42
43 ~WeakTable() { free(data_); }
44
45 static WeakTable* NewFrom(WeakTable* original) {
46 return new WeakTable(SizeFor(count: original->count(), size: original->size()));
47 }
48
49 intptr_t size() const { return size_; }
50 intptr_t used() const { return used_; }
51 intptr_t count() const { return count_; }
52
53 // The following methods can be called concurrently and are guarded by a lock.
54
55 intptr_t GetValue(ObjectPtr key) {
56 MutexLocker ml(&mutex_);
57 return GetValueExclusive(key);
58 }
59
60 void SetValue(ObjectPtr key, intptr_t val) {
61 MutexLocker ml(&mutex_);
62 return SetValueExclusive(key, val);
63 }
64
65 intptr_t SetValueIfNonExistent(ObjectPtr key, intptr_t val) {
66 MutexLocker ml(&mutex_);
67 const auto old_value = GetValueExclusive(key);
68 if (old_value == kNoValue) {
69 SetValueExclusive(key, val);
70 return val;
71 }
72 return old_value;
73 }
74
75 // The following "exclusive" methods must only be called from call sites
76 // which are known to have exclusive access to the weak table.
77 //
78 // This is mostly limited to GC related code (e.g. scavenger, marker, ...)
79
80 bool IsValidEntryAtExclusive(intptr_t i) const {
81 ASSERT((ValueAtExclusive(i) == 0 &&
82 (data_[ObjectIndex(i)] == kNoEntry ||
83 data_[ObjectIndex(i)] == kDeletedEntry)) ||
84 (ValueAtExclusive(i) != 0 && data_[ObjectIndex(i)] != kNoEntry &&
85 data_[ObjectIndex(i)] != kDeletedEntry));
86 return (data_[ValueIndex(i)] != 0);
87 }
88
89 void InvalidateAtExclusive(intptr_t i) {
90 ASSERT(IsValidEntryAtExclusive(i));
91 SetValueAt(i, val: 0);
92 }
93
94 ObjectPtr ObjectAtExclusive(intptr_t i) const {
95 ASSERT(i >= 0);
96 ASSERT(i < size());
97 return static_cast<ObjectPtr>(data_[ObjectIndex(i)]);
98 }
99
100 intptr_t ValueAtExclusive(intptr_t i) const {
101 ASSERT(i >= 0);
102 ASSERT(i < size());
103 return data_[ValueIndex(i)];
104 }
105
106 void SetValueExclusive(ObjectPtr key, intptr_t val);
107 bool MarkValueExclusive(ObjectPtr key, intptr_t val);
108
109 intptr_t GetValueExclusive(ObjectPtr key) const {
110 intptr_t mask = size() - 1;
111 intptr_t idx = Hash(key) & mask;
112 ObjectPtr obj = ObjectAtExclusive(i: idx);
113 while (obj != static_cast<ObjectPtr>(kNoEntry)) {
114 if (obj == key) {
115 return ValueAtExclusive(i: idx);
116 }
117 idx = (idx + 1) & mask;
118 obj = ObjectAtExclusive(i: idx);
119 }
120 ASSERT(ValueAtExclusive(idx) == 0);
121 return kNoValue;
122 }
123
124 // Removes and returns the value associated with |key|. Returns 0 if there is
125 // no value associated with |key|.
126 intptr_t RemoveValueExclusive(ObjectPtr key) {
127 intptr_t mask = size() - 1;
128 intptr_t idx = Hash(key) & mask;
129 ObjectPtr obj = ObjectAtExclusive(i: idx);
130 while (obj != static_cast<ObjectPtr>(kNoEntry)) {
131 if (obj == key) {
132 intptr_t result = ValueAtExclusive(i: idx);
133 InvalidateAtExclusive(i: idx);
134 return result;
135 }
136 idx = (idx + 1) & mask;
137 obj = ObjectAtExclusive(i: idx);
138 }
139 ASSERT(ValueAtExclusive(idx) == 0);
140 return kNoValue;
141 }
142
143 void Forward(ObjectPointerVisitor* visitor);
144 void ReportSurvivingAllocations(Dart_HeapSamplingReportCallback callback,
145 void* context);
146 void CleanupValues(Dart_HeapSamplingDeleteCallback cleanup);
147
148 void Reset();
149
150 private:
151 enum {
152 kObjectOffset = 0,
153 kValueOffset,
154 kEntrySize,
155 };
156
157 static constexpr intptr_t kNoEntry = 1; // Not a valid OOP.
158 static constexpr intptr_t kDeletedEntry = 3; // Not a valid OOP.
159 static constexpr intptr_t kMinSize = 8;
160
161 static intptr_t SizeFor(intptr_t count, intptr_t size);
162 static intptr_t LimitFor(intptr_t size) {
163 // Maintain a maximum of 75% fill rate.
164 return 3 * (size / 4);
165 }
166 intptr_t limit() const { return LimitFor(size: size()); }
167
168 intptr_t index(intptr_t i) const { return i * kEntrySize; }
169
170 void set_used(intptr_t val) {
171 ASSERT(val <= limit());
172 used_ = val;
173 }
174
175 void set_count(intptr_t val) {
176 ASSERT(val <= limit());
177 ASSERT(val <= used());
178 count_ = val;
179 }
180
181 intptr_t ObjectIndex(intptr_t i) const { return index(i) + kObjectOffset; }
182
183 intptr_t ValueIndex(intptr_t i) const { return index(i) + kValueOffset; }
184
185 ObjectPtr* ObjectPointerAt(intptr_t i) const {
186 ASSERT(i >= 0);
187 ASSERT(i < size());
188 return reinterpret_cast<ObjectPtr*>(&data_[ObjectIndex(i)]);
189 }
190
191 void SetObjectAt(intptr_t i, ObjectPtr key) {
192 ASSERT(i >= 0);
193 ASSERT(i < size());
194 data_[ObjectIndex(i)] = static_cast<intptr_t>(key);
195 }
196
197 void SetValueAt(intptr_t i, intptr_t val) {
198 ASSERT(i >= 0);
199 ASSERT(i < size());
200 // Setting a value of 0 is equivalent to invalidating the entry.
201 if (val == 0) {
202 data_[ObjectIndex(i)] = kDeletedEntry;
203 set_count(count() - 1);
204 }
205 data_[ValueIndex(i)] = val;
206 }
207
208 void Rehash();
209
210 static uword Hash(ObjectPtr key) {
211 return (static_cast<uword>(key) * 92821) ^ (static_cast<uword>(key) >> 8);
212 }
213
214 Mutex mutex_;
215
216 // data_ contains size_ tuples of key/value.
217 intptr_t* data_;
218 // size_ keeps the number of entries in data_. used_ maintains the number of
219 // non-NULL entries and will trigger rehashing if needed. count_ stores the
220 // number valid entries, and will determine the size_ after rehashing.
221 intptr_t size_;
222 intptr_t used_;
223 intptr_t count_;
224
225 DISALLOW_COPY_AND_ASSIGN(WeakTable);
226};
227
228} // namespace dart
229
230#endif // RUNTIME_VM_HEAP_WEAK_TABLE_H_
231

source code of dart_sdk/runtime/vm/heap/weak_table.h