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 : // An implementation of a size-limited quarantine. This encapsulates the
16 : // logic for maintaining a size invariant over the items in a quarantine.
17 :
18 : #ifndef SYZYGY_AGENT_ASAN_QUARANTINES_SIZE_LIMITED_QUARANTINE_H_
19 : #define SYZYGY_AGENT_ASAN_QUARANTINES_SIZE_LIMITED_QUARANTINE_H_
20 :
21 : #include <utility>
22 :
23 : #include "base/atomicops.h"
24 : #include "base/synchronization/lock.h"
25 : #include "syzygy/agent/asan/quarantine.h"
26 :
27 : namespace agent {
28 : namespace asan {
29 : namespace quarantines {
30 :
31 : // Provides both the size of the quarantine and the number of elements it
32 : // contains. Both of these are accessed behind a lock, to ensure their
33 : // consistency. Hence, the lock must be acquired (by calling Lock) before any
34 : // other operation is performed. The lock should be returned (by calling Unlock)
35 : // as soon as possible to minimize the locked time.
36 : // Note that since pushing/popping the quarantine are not atomic operations, the
37 : // size/count can become negative in transition, hence the need to have them as
38 : // signed integer (only their eventual consistency is guaranteed).
39 : class QuarantineSizeCount {
40 : public:
41 : // Default constructor that sets the size and count to 0.
42 E : QuarantineSizeCount() : size_(0), count_(0) {}
43 :
44 : // Must be called before any other operation to acquire the lock.
45 E : void Lock() { lock_.Acquire(); }
46 :
47 : // Releases the lock.
48 E : void Unlock() {
49 E : lock_.AssertAcquired();
50 E : lock_.Release();
51 E : }
52 :
53 : // @returns the size.
54 E : SSIZE_T size() const {
55 E : lock_.AssertAcquired();
56 E : return size_;
57 E : }
58 :
59 : // @returns the count.
60 E : SSIZE_T count() const {
61 E : lock_.AssertAcquired();
62 E : return count_;
63 E : }
64 :
65 : // Increments the size and count.
66 : // @param size_delta The delta by which the size is incremented.
67 : // @param count_delta The delta by which the count is incremented.
68 : // @returns the new size.
69 E : SSIZE_T Increment(SSIZE_T size_delta, SSIZE_T count_delta) {
70 E : lock_.AssertAcquired();
71 E : size_ += size_delta;
72 E : count_ += count_delta;
73 E : return size_;
74 E : }
75 :
76 : // Decrements the size and count.
77 : // @param size_delta The delta by which the size is decremented.
78 : // @param count_delta The delta by which the count is decremented.
79 : // @returns the new size.
80 E : SSIZE_T Decrement(SSIZE_T size_delta, SSIZE_T count_delta) {
81 E : lock_.AssertAcquired();
82 E : size_ -= size_delta;
83 E : count_ -= count_delta;
84 E : return size_;
85 E : }
86 :
87 : private:
88 : // The current size of the quarantine.
89 : SSIZE_T size_;
90 : // The number of elements in the quarantine.
91 : SSIZE_T count_;
92 : // Single lock that's used for both |size_| and |count_|.
93 : base::Lock lock_;
94 : };
95 :
96 : // An automatic lock on QuarantineSizeCount.
97 : class ScopedQuarantineSizeCountLock {
98 : public:
99 : // Constructor. Automatically lock the quarantine.
100 E : explicit ScopedQuarantineSizeCountLock(QuarantineSizeCount& size_count)
101 E : : size_count_(size_count) {
102 E : size_count_.Lock();
103 E : }
104 :
105 : // Destructor. Automatically unlock the quarantine.
106 E : ~ScopedQuarantineSizeCountLock() { size_count_.Unlock(); }
107 :
108 : private:
109 : // The QuarantineSizeCount that this holds.
110 : QuarantineSizeCount& size_count_;
111 :
112 : DISALLOW_COPY_AND_ASSIGN(ScopedQuarantineSizeCountLock);
113 : };
114 :
115 : // A partial implementation of a size-limited quarantine. This quarantine
116 : // obeys a simple invariant: the sum of object weights within it must be
117 : // less than a certain threshold, and all objects within it must be smaller
118 : // than another given threshold.
119 : //
120 : // Provides implementations of QuarantineInterface Push/Pop/Empty methods.
121 : // Expects the derived class to provide implementations for a few methods:
122 : //
123 : // bool PushImpl(const ObjectType& object);
124 : // bool PopImpl(ObjectType* object);
125 : // void EmptyImpl(ObjectVector* object);
126 : //
127 : // Calculates the sizes of objects using the provided SizeFunctor. This
128 : // must satisfy the following interface:
129 : //
130 : // struct SizeFunctor {
131 : // size_t operator()(const ObjectType& object);
132 : // };
133 : //
134 : // @tparam ObjectType The type of object stored in the quarantine.
135 : // @tparam SizeFunctorType The size functor that will be used to extract
136 : // a size from an object.
137 : template<typename ObjectType, typename SizeFunctorType>
138 : class SizeLimitedQuarantineImpl : public QuarantineInterface<ObjectType> {
139 : public:
140 : typedef SizeFunctorType SizeFunctor;
141 :
142 : static const size_t kUnboundedSize = SIZE_MAX;
143 :
144 : // Constructor. Initially the quarantine has unlimited capacity.
145 : SizeLimitedQuarantineImpl()
146 E : : max_object_size_(kUnboundedSize),
147 E : max_quarantine_size_(kUnboundedSize),
148 : size_functor_(),
149 E : overbudget_size_(0) {}
150 :
151 : // Constructor. Initially the quarantine has unlimited capacity.
152 : // @param size_functor The size functor to be used. This will be copied
153 : // into the classes member size functor.
154 : explicit SizeLimitedQuarantineImpl(const SizeFunctor& size_functor)
155 : : max_object_size_(kUnboundedSize),
156 : max_quarantine_size_(kUnboundedSize),
157 : size_functor_(size_functor),
158 : overbudget_size_(0) {}
159 :
160 : // Constructor. Takes the quarantine capacity.
161 : // @param max_quarantine_size The capacity of the quarantine.
162 : explicit SizeLimitedQuarantineImpl(size_t max_quarantine_size)
163 : : max_object_size_(kUnboundedSize),
164 : max_quarantine_size_(max_quarantine_size),
165 : size_functor_(),
166 : overbudget_size_(0) {}
167 :
168 : // Virtual destructor.
169 E : virtual ~SizeLimitedQuarantineImpl() { }
170 :
171 : // Sets the maximum object size. This only gates the entry of future
172 : // objects to 'Push', and does not invalidate overly objects already in
173 : // the quarantine.
174 : // @param max_object_size The maximum size of any single object in the
175 : // quarantine. Use kUnboundedSize for unlimited (no max).
176 E : void set_max_object_size(size_t max_object_size) {
177 E : max_object_size_ = max_object_size;
178 E : }
179 :
180 : // Sets the maximum quarantine size. This may cause the quarantine
181 : // invariant to be immediately invalidated, requiring calls to 'Pop'.
182 : // @param max_quarantine_size The maximum size of the entire quarantine.
183 : // Use kUnboundedSize for unlimited (no max).
184 E : void set_max_quarantine_size(size_t max_quarantine_size) {
185 E : max_quarantine_size_ = max_quarantine_size;
186 E : }
187 :
188 : // @returns the maximum object size.
189 E : size_t max_object_size() const { return max_object_size_; }
190 :
191 : // @returns the maximum quarantine size.
192 E : size_t max_quarantine_size() const { return max_quarantine_size_; }
193 :
194 : // @returns the current size of the quarantine.
195 : // @note that this function could be racing with a push/pop operation and
196 : // return a stale value. It is only used in tests.
197 E : size_t GetSizeForTesting() {
198 E : ScopedQuarantineSizeCountLock size_count_lock(size_count_);
199 E : return size_count_.size();
200 E : }
201 :
202 : // @returns the current overbudget size.
203 E : size_t GetOverbudgetSizeForTesting() const { return overbudget_size_; }
204 :
205 : // Sets the overbudget size by which the quarantine is allowed to go over and
206 : // enables hysteresis by defining color regions. Note that once the size is
207 : // set, it cannot be changed unless the hysteresis is removed first by setting
208 : // the size to 0. It is also illegal to set the size to 0 if it's already at
209 : // that value.
210 : // @param overbudget_size The overbudget size. This is capped to half of
211 : // the maximum size of the quarantine and must be at least 1024 bytes. If
212 : // 0, this removes the hysteresis.
213 : void SetOverbudgetSize(size_t overbudget_size);
214 :
215 : // Returns the color of the quarantine, depending on the size. See note in
216 : // implementation about the raciness of the function.
217 : // @param size The size that is used to calculate the color.
218 : // @returns the color of the quarantine.
219 : TrimColor GetQuarantineColor(size_t size) const;
220 :
221 : // Returns the maximum size of a certain color. Used only in testing.
222 : // @param color The color for which the size is queried.
223 : // @returns the size.
224 : size_t GetMaxSizeForColorForTesting(TrimColor color) const;
225 :
226 : // @name QuarantineInterface implementation.
227 : // @note that GetCountForTest could be racing with a push/pop operation and
228 : // return a stale value. It is only used in in tests.
229 : // @{
230 : virtual PushResult Push(const Object& object);
231 : virtual PopResult Pop(Object* object);
232 : virtual void Empty(ObjectVector* objects);
233 : virtual size_t GetCountForTesting();
234 : virtual size_t GetLockId(const Object& object);
235 : virtual void Lock(size_t id);
236 : virtual void Unlock(size_t id);
237 : // @}
238 :
239 : protected:
240 : // @name SizeLimitedQuarantine interface.
241 : // @{
242 : virtual bool PushImpl(const Object& object) = 0;
243 : virtual bool PopImpl(Object* object) = 0;
244 : virtual void EmptyImpl(ObjectVector* objects) = 0;
245 : virtual size_t GetLockIdImpl(const Object& object) = 0;
246 : virtual void LockImpl(size_t id) = 0;
247 : virtual void UnlockImpl(size_t id) = 0;
248 : // @}
249 :
250 : // Parameters controlling the quarantine invariant.
251 : size_t max_object_size_;
252 : size_t max_quarantine_size_;
253 :
254 : QuarantineSizeCount size_count_;
255 :
256 : // The size functor.
257 : SizeFunctor size_functor_;
258 :
259 : // The size by which the quarantine is allowed to go over until it has to be
260 : // synchronously trimmed. This is atomically accessed. Since it is not behind
261 : // a lock, when modified, this could potentially lead to transitions between
262 : // colors being missed. The implementation takes this factor into
263 : // consideration.
264 : base::subtle::AtomicWord overbudget_size_;
265 :
266 : private:
267 : DISALLOW_COPY_AND_ASSIGN(SizeLimitedQuarantineImpl);
268 : };
269 :
270 : } // namespace quarantines
271 : } // namespace asan
272 : } // namespace agent
273 :
274 : #include "syzygy/agent/asan/quarantines/size_limited_quarantine_impl.h"
275 :
276 : #endif // SYZYGY_AGENT_ASAN_QUARANTINES_SIZE_LIMITED_QUARANTINE_H_
|