1 : // Copyright 2014 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // Internal implementation of a size-limited quarantine. This file is not
16 : // meant to be included directly.
17 :
18 : #ifndef SYZYGY_AGENT_ASAN_QUARANTINES_SIZE_LIMITED_QUARANTINE_IMPL_H_
19 : #define SYZYGY_AGENT_ASAN_QUARANTINES_SIZE_LIMITED_QUARANTINE_IMPL_H_
20 :
21 : #include <algorithm>
22 :
23 : namespace agent {
24 : namespace asan {
25 : namespace quarantines {
26 :
27 : template <typename OT, typename SFT>
28 E : PushResult SizeLimitedQuarantineImpl<OT, SFT>::Push(const Object& object) {
29 E : PushResult result = {false, 0};
30 E : size_t size = size_functor_(object);
31 E : if (max_object_size_ != kUnboundedSize && size > max_object_size_)
32 E : return result;
33 :
34 : // This will contain the size of quarantine after the implementation of push,
35 : // whether successful or not.
36 E : size_t new_size = 0;
37 : {
38 : // Note that if a thread gets preempted here, the size/count will be wrong,
39 : // until the thread resumes (the size will eventually become consistent).
40 E : ScopedQuarantineSizeCountLock size_count_lock(size_count_);
41 E : new_size = size_count_.Increment(size, 1);
42 E : }
43 :
44 : // This is the size of the quarantine before the call to PushImpl and is
45 : // needed to calculate the old color and infer potential transitions.
46 E : size_t old_size = new_size - size;
47 E : if (PushImpl(object)) {
48 E : result.push_successful = true;
49 E : } else {
50 : // Decrementing here is not guaranteed to give the same size as before the
51 : // increment, as the whole sequence is not atomic. Trimming might still be
52 : // required and will be signaled if need be.
53 i : ScopedQuarantineSizeCountLock size_count_lock(size_count_);
54 i : new_size = size_count_.Decrement(size, 1);
55 i : }
56 :
57 : // Note that because GetQuarantineColor can return the wrong color (see note
58 : // in its implementation), this function might miss a transition to RED/BLACK
59 : // which would result in not signaling the asynchronous thread (under
60 : // signaling). This is a tradeoff for not having to lock the overbudget size.
61 : // As for the synchronous trimming, unless the wrong color is returned forever
62 : // (which would obviously be a bug), it will eventually be signaled when BLACK
63 : // is returned (regardless of transition).
64 E : TrimColor new_color = GetQuarantineColor(new_size);
65 E : TrimColor old_color = GetQuarantineColor(old_size);
66 :
67 E : if (new_color == TrimColor::BLACK) {
68 : // If the current color is BLACK, always request synchronous trimming. As
69 : // stated above, this ensures that regardless of the transition, the
70 : // quarantine will eventually get trimmed (no "run away" situation should be
71 : // possible).
72 E : result.trim_status |= TrimStatusBits::SYNC_TRIM_REQUIRED;
73 E : if (old_color < TrimColor::RED) {
74 : // If going from GREEN/YELLOW to BLACK, also schedule asynchronous
75 : // trimming (this is by design to improve the performance).
76 E : result.trim_status |= TrimStatusBits::ASYNC_TRIM_REQUIRED;
77 E : }
78 E : } else if (new_color == TrimColor::RED) {
79 E : if (old_color < TrimColor::RED) {
80 : // If going from GREEN/YELLOW to RED, schedule asynchronous trimming.
81 E : result.trim_status |= TrimStatusBits::ASYNC_TRIM_REQUIRED;
82 : }
83 : }
84 E : return result;
85 E : }
86 :
87 : template <typename OT, typename SFT>
88 E : PopResult SizeLimitedQuarantineImpl<OT, SFT>::Pop(Object* object) {
89 E : DCHECK_NE(static_cast<Object*>(NULL), object);
90 E : PopResult result = {false, TrimColor::GREEN};
91 :
92 E : if (max_quarantine_size_ == kUnboundedSize)
93 i : return result;
94 :
95 : {
96 : // Never pop if already in GREEN as this is the lowest bound.
97 : // Note that because GetQuarantineColor can return the wrong color (see note
98 : // in its implementation), this verification might not always be correct
99 : // which might cause either an over popping or an under popping. Either way,
100 : // that is acceptable as the extra or missing pop operations are not harmful
101 : // and the size will eventually get consistency.
102 E : ScopedQuarantineSizeCountLock size_count_lock(size_count_);
103 E : if (GetQuarantineColor(size_count_.size()) == TrimColor::GREEN)
104 E : return result;
105 E : }
106 :
107 E : if (!PopImpl(object))
108 i : return result;
109 :
110 : // Note that if a thread gets preempted here, the size/count will be wrong,
111 : // until the thread resumes.
112 E : size_t size = size_functor_(*object);
113 E : ScopedQuarantineSizeCountLock size_count_lock(size_count_);
114 :
115 E : size_t new_size = size_count_.Decrement(size, 1);
116 :
117 : // Return success and the new quarantine color.
118 E : result.pop_successful = true;
119 : // See note above about GetQuarantineColor potentially returning the wrong
120 : // color.
121 E : result.trim_color = GetQuarantineColor(new_size);
122 E : return result;
123 E : }
124 :
125 : template<typename OT, typename SFT>
126 : void SizeLimitedQuarantineImpl<OT, SFT>::Empty(
127 E : ObjectVector* objects) {
128 E : DCHECK_NE(static_cast<ObjectVector*>(NULL), objects);
129 E : EmptyImpl(objects);
130 :
131 : // In order for the quarantine to remain long-term consistent we need to
132 : // remove a size and count consistent with the output of EmptyImpl. Simply
133 : // setting the size and count to zero could introduce inconsistency, as they
134 : // may not yet reflect the contributions of some of the elements returned by
135 : // EmptyImpl.
136 E : size_t net_size = 0;
137 E : for (size_t i = 0; i < objects->size(); ++i) {
138 E : size_t size = size_functor_(objects->at(i));
139 E : net_size += size;
140 E : }
141 :
142 E : ScopedQuarantineSizeCountLock size_count_lock(size_count_);
143 E : size_count_.Decrement(net_size, objects->size());
144 E : }
145 :
146 : template <typename OT, typename SFT>
147 E : size_t SizeLimitedQuarantineImpl<OT, SFT>::GetCountForTesting() {
148 E : ScopedQuarantineSizeCountLock size_count_lock(size_count_);
149 E : return size_count_.count();
150 E : }
151 :
152 : template<typename OT, typename SFT>
153 : size_t SizeLimitedQuarantineImpl<OT, SFT>::GetLockId(
154 E : const Object& object) {
155 E : return GetLockIdImpl(object);
156 E : }
157 :
158 : template<typename OT, typename SFT>
159 E : void SizeLimitedQuarantineImpl<OT, SFT>::Lock(size_t id) {
160 E : LockImpl(id);
161 E : }
162 :
163 : template<typename OT, typename SFT>
164 E : void SizeLimitedQuarantineImpl<OT, SFT>::Unlock(size_t id) {
165 E : UnlockImpl(id);
166 E : }
167 :
168 : template <typename OT, typename SFT>
169 : TrimColor SizeLimitedQuarantineImpl<OT, SFT>::GetQuarantineColor(
170 E : size_t size) const {
171 : // The quarantine is allowed to go overbudget by |overbudget_size_|.
172 : // Furthermore, to enable hysteresis, 3 size limits are set that define 4
173 : // zones, each representing a color. These colors are as following:
174 : // GREEN if the current size is lower than |max_quarantine_size_ -
175 : // overbudget_size_|
176 : // YELLOW if it's over GREEN but lower than |max_quarantine_size_|
177 : // RED if it's over YELLOW but lower than
178 : // |max_quarantine_size_ + overbudget_size_|
179 : // BLACK if it's over |max_quarantine_size_ + overbudget_size_|
180 : //
181 : // YELLOW is basically the equivalent of the single limit that exists when the
182 : // deferred free thread is not enabled. A trim will always cross an entire
183 : // color. An async trim is triggered once the size crossed into the RED or
184 : // BLACK zone from either YELLOW or GREEN and will bring it back to GREEN.
185 : // Also, if it hits BLACK, then a sync trim is requested which will bring it
186 : // back to YELLOW. Synchronous and asynchronous trimming can therefore happen
187 : // simultanously. This is by design.
188 :
189 E : if (max_quarantine_size_ == kUnboundedSize)
190 E : return TrimColor::GREEN;
191 :
192 : // Note that this is racy by design, to avoid contention. If
193 : // |overbudget_size_| is modified before the end of the function, the wrong
194 : // color can be returned. Functions that call GetQuarantineColor must deal
195 : // with the consequences accordingly. But since |overbudget_size_| is only
196 : // modified when the thread is started or shutdown, this is seldom an issue.
197 : base::subtle::Atomic32 overbudget_size =
198 E : base::subtle::NoBarrier_Load(&overbudget_size_);
199 :
200 E : if (size <= max_quarantine_size_ - overbudget_size)
201 E : return TrimColor::GREEN;
202 :
203 E : if (size <= max_quarantine_size_)
204 E : return TrimColor::YELLOW;
205 :
206 E : if (size <= max_quarantine_size_ + overbudget_size)
207 E : return TrimColor::RED;
208 :
209 E : return TrimColor::BLACK;
210 E : }
211 :
212 : template <typename OT, typename SFT>
213 : size_t SizeLimitedQuarantineImpl<OT, SFT>::GetMaxSizeForColorForTesting(
214 E : TrimColor color) const {
215 : // Note that this is racy by design, to avoid contention. If
216 : // |overbudget_size_| is modified before the end of the function, the wrong
217 : // size can be returned. Since this function is only used in testing, this is
218 : // not an issue.
219 E : if (color == TrimColor::BLACK || max_quarantine_size_ == kUnboundedSize)
220 E : return kUnboundedSize;
221 :
222 E : switch (color) {
223 : case TrimColor::GREEN:
224 E : return max_quarantine_size_ -
225 : base::subtle::NoBarrier_Load(&overbudget_size_);
226 : case TrimColor::YELLOW:
227 E : return max_quarantine_size_;
228 : case TrimColor::RED:
229 E : return max_quarantine_size_ +
230 : base::subtle::NoBarrier_Load(&overbudget_size_);
231 : }
232 :
233 : // Should never hit this.
234 i : NOTREACHED();
235 i : return kUnboundedSize;
236 E : }
237 :
238 : template <typename OT, typename SFT>
239 : void SizeLimitedQuarantineImpl<OT, SFT>::SetOverbudgetSize(
240 E : size_t overbudget_size) {
241 E : const size_t kMinBudgetSize = 1024;
242 : // |overbudget_size_ | cannot exceed half of |max_quarantine_size_| and must
243 : // be at least 1024 (1k), or 0 (which removes the hysteresis).
244 E : size_t new_size = 0;
245 E : if (overbudget_size > 0) {
246 E : new_size = std::max(overbudget_size, kMinBudgetSize);
247 E : new_size = std::min(new_size, max_quarantine_size_ / 2);
248 : }
249 : auto old_size =
250 E : base::subtle::NoBarrier_AtomicExchange(&overbudget_size_, new_size);
251 : // This can only be called twice, once to set the size and a second time to
252 : // reset it to 0.
253 E : DCHECK((old_size == 0) != (new_size == 0));
254 E : }
255 :
256 : } // namespace quarantines
257 : } // namespace asan
258 : } // namespace agent
259 :
260 : #endif // SYZYGY_AGENT_ASAN_QUARANTINES_SIZE_LIMITED_QUARANTINE_IMPL_H_
|