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 : // Implementation of a heap manager that allocates blocks.
16 :
17 : #ifndef SYZYGY_AGENT_ASAN_HEAP_MANAGERS_BLOCK_HEAP_MANAGER_H_
18 : #define SYZYGY_AGENT_ASAN_HEAP_MANAGERS_BLOCK_HEAP_MANAGER_H_
19 :
20 : #include <windows.h>
21 :
22 : #include <unordered_map>
23 : #include <utility>
24 :
25 : #include "base/logging.h"
26 : #include "base/memory/scoped_ptr.h"
27 : #include "syzygy/agent/asan/block_utils.h"
28 : #include "syzygy/agent/asan/error_info.h"
29 : #include "syzygy/agent/asan/heap.h"
30 : #include "syzygy/agent/asan/heap_manager.h"
31 : #include "syzygy/agent/asan/quarantine.h"
32 : #include "syzygy/agent/asan/stack_capture_cache.h"
33 : #include "syzygy/agent/asan/memory_notifiers/shadow_memory_notifier.h"
34 : #include "syzygy/agent/asan/quarantines/sharded_quarantine.h"
35 : #include "syzygy/agent/common/stack_capture.h"
36 : #include "syzygy/common/asan_parameters.h"
37 :
38 : namespace agent {
39 : namespace asan {
40 :
41 : // Forward declarations
42 : namespace heaps {
43 :
44 : class ZebraBlockHeap;
45 :
46 : } // namespace heaps
47 :
48 : namespace heap_managers {
49 :
50 : // A block heap manager is an implementation of a heap manager that allocates
51 : // and manages blocks.
52 : //
53 : // It is responsible for maintaining the state of the shadow memory, and thus
54 : // updating it when a block's state changes. This also takes care of maintaining
55 : // a quarantine of freed blocks.
56 : //
57 : // When the user requests a new heap he will receive a pointer to a
58 : // SimpleBlockHeap by default. However the goal of this manager is to
59 : // automatically choose the most appropriate heap for a given allocation so the
60 : // actual heap that serves an allocation can be different from the one returned
61 : // to the user.
62 : //
63 : // The zebra heap is created once, when enabled for the first time, with a
64 : // specified size. It can't be resized after creation. Disabling the zebra
65 : // heap only disables allocations on it, deallocations will continue to work.
66 : class BlockHeapManager : public HeapManagerInterface {
67 : public:
68 : // Constructor.
69 : // @param stack_cache The stack cache to use.
70 : explicit BlockHeapManager(StackCaptureCache* stack_cache);
71 :
72 : // Destructor.
73 : virtual ~BlockHeapManager();
74 :
75 : // Initializes this block heap manager. Must be called prior to any
76 : // HeapManagerInterface functions. Parameters may be set prior to this.
77 : void Init();
78 :
79 : // @name HeapManagerInterface functions.
80 : // @{
81 : virtual HeapId CreateHeap();
82 : virtual bool DestroyHeap(HeapId heap_id);
83 : virtual void* Allocate(HeapId heap_id, size_t bytes);
84 : virtual bool Free(HeapId heap_id, void* alloc);
85 : virtual size_t Size(HeapId heap_id, const void* alloc);
86 : virtual void Lock(HeapId heap_id);
87 : virtual void Unlock(HeapId heap_id);
88 : virtual void BestEffortLockAll();
89 : virtual void UnlockAll();
90 : // @}
91 :
92 : // Set the parameters of this heap manager.
93 : // @param trailer_padding_size The trailer padding size, in bytes.
94 : void set_parameters(const ::common::AsanParameters& parameters);
95 :
96 : // Get the parameters.
97 E : ::common::AsanParameters parameters() {
98 E : return parameters_;
99 E : }
100 :
101 : // Sets the callback that this heap will invoke when heap corruption is
102 : // encountered.
103 : // @param heap_error_callback The callback to be invoked when heap
104 : // corruption is encountered.
105 E : void SetHeapErrorCallback(HeapErrorCallback heap_error_callback) {
106 E : heap_error_callback_ = heap_error_callback;
107 E : }
108 :
109 : // Returns the process heap ID.
110 E : HeapId process_heap() { return process_heap_id_; }
111 :
112 : // Returns the allocation-filter flag value.
113 : // @returns the allocation-filter flag value.
114 : // @note The flag is stored per-thread using TLS. Multiple threads do not
115 : // share the same flag.
116 : bool allocation_filter_flag() const;
117 :
118 : // Sets the allocation-filter flag to the specified value.
119 : // @param value the new value for the flag.
120 : // @note The flag is stored per-thread using TLS. Multiple threads do not
121 : // share the same flag.
122 : void set_allocation_filter_flag(bool value);
123 :
124 : protected:
125 : // This allows the runtime access to our internals, necessary for crash
126 : // processing.
127 : friend class AsanRuntime;
128 :
129 : // @name Functions intended for use exclusively by the AsanRuntime for
130 : // introspection during crash processing.
131 : // @{
132 : HeapType GetHeapTypeUnlocked(HeapId heap_id);
133 : // @}
134 :
135 : // The type of quarantine that we use internally.
136 : using ShardedBlockQuarantine =
137 : quarantines::ShardedQuarantine<CompactBlockInfo,
138 : GetTotalBlockSizeFunctor,
139 : GetBlockHashFunctor,
140 : kQuarantineDefaultShardingFactor>;
141 :
142 : // A map associating a block heap with its underlying heap.
143 : using UnderlyingHeapMap =
144 : std::unordered_map<BlockHeapInterface*, HeapInterface*>;
145 :
146 : // A map associating a block heap with a pair containing the quarantine it
147 : // will use and a bit indicating if it's dying. Many heaps may share a single
148 : // quarantine.
149 : struct HeapMetadata {
150 : BlockQuarantineInterface* quarantine;
151 : bool is_dying;
152 : };
153 : using HeapQuarantineMap =
154 : std::unordered_map<BlockHeapInterface*, HeapMetadata>;
155 : using HeapQuarantinePair = BlockHeapManager::HeapQuarantineMap::value_type;
156 :
157 : using StackId = agent::common::StackCapture::StackId;
158 :
159 : // Contains the information allowing to determine which rate targeted heap
160 : // should serve a given allocation.
161 : struct AllocationRateInfo {
162 : typedef std::unordered_map<StackId, size_t> AllocationSiteCountMap;
163 :
164 : // Estimates of the current min and max values contained in the allocation
165 : // site count map.
166 : size_t allocation_site_count_max;
167 : size_t allocation_site_count_min;
168 :
169 : // Map that tracks how many time we've seen a given allocation stack.
170 : AllocationSiteCountMap allocation_site_count_map;
171 :
172 E : AllocationRateInfo() : allocation_site_count_max(0) { }
173 : };
174 :
175 : // Causes the heap manager to tear itself down. If the heap manager
176 : // encounters corrupt blocks while tearing itself dow it will report an
177 : // error. This will in turn cause the asan runtime to call back into itself
178 : // and access the block heap manager. Thus, the block heap manager needs to
179 : // still be alive while this process is occurring. Hence, the need to
180 : // separate the work of tearing down the heap manager from its destructor.
181 : void TearDownHeapManager();
182 :
183 : // Given the result of an HeapQuarantineMap insert or find, returns a heap id.
184 : // @param iterator An iterator to a heap.
185 : // @param insert_result The result of a call to heaps_.insert.
186 : // @returns the ID associated with the inserted heap.
187 : HeapId GetHeapId(
188 : HeapQuarantineMap::iterator iterator) const;
189 : HeapId GetHeapId(
190 : const std::pair<HeapQuarantineMap::iterator, bool>& insert_result) const;
191 :
192 : // @name Heap validation. There are multiple ways to do this because of the
193 : // need to do this during crash processing, when locks are already
194 : // implicitly acquired. As such, the runtime has been made a friend of
195 : // this class.
196 : // Determines if a heap ID is valid.
197 : // @param heap_id The heap_id to validate.
198 : // @param allow_dying If true then also consider heaps that are in the
199 : // process of dying. Otherwise, only consider live heaps.
200 : // @returns true if the given heap id is valid.
201 : // @note The unsafe variants can raise access violations.
202 : bool IsValidHeapIdUnsafe(HeapId heap_id, bool allow_dying);
203 : bool IsValidHeapIdUnsafeUnlocked(HeapId heap_id, bool allow_dying);
204 : bool IsValidHeapId(HeapId heap_id, bool allow_dying);
205 : bool IsValidHeapIdUnlocked(HeapId heap_id, bool allow_dying);
206 :
207 : // Helpers for the above functions. This is split into two to keep the
208 : // locking as narrow as possible.
209 : // @param hq The heap quarantine pair being queried.
210 : // @param allow_dying If true then also consider heaps that are in the
211 : // process of dying. Otherwise, only consider live heaps.
212 : bool IsValidHeapIdUnsafeUnlockedImpl1(HeapQuarantinePair* hq);
213 : bool IsValidHeapIdUnlockedImpl1(HeapQuarantinePair* hq);
214 : bool IsValidHeapIdUnlockedImpl2(HeapQuarantinePair* hq, bool allow_dying);
215 : // @}
216 :
217 : // Given a heap ID, returns the underlying heap.
218 : // @param heap_id The ID of the heap to look up.
219 : // @returns a pointer to the heap implementation.
220 : // @note DCHECKs on invalid input.
221 : static BlockHeapInterface* GetHeapFromId(HeapId heap_id);
222 :
223 : // Given a heap ID, returns the associated quarantine.
224 : // @param heap_id The ID of the heap whose quarantine is to be looked up.
225 : // @returns a pointer to the quarantine implementation.
226 : // @note DCHECKs on invalid input.
227 : static BlockQuarantineInterface* GetQuarantineFromId(HeapId heap_id);
228 :
229 : // Propagates the parameters to the appropriate modules.
230 : // @note This function is responsible for acquiring lock_ when necessary.
231 : void PropagateParameters();
232 :
233 : // Destroy a heap and flush its quarantine. If this heap has an underlying
234 : // heap it'll also destroy it. All the blocks belonging to this heap that are
235 : // in the quarantine will be freed.
236 : //
237 : // @param heap The heap to destroy.
238 : // @param quarantine The quarantine of this heap.
239 : // @returns true on success, false otherwise.
240 : // @note The heap pointer will be invalid if this function succeeds.
241 : bool DestroyHeapContents(BlockHeapInterface* heap,
242 : BlockQuarantineInterface* quarantine);
243 :
244 : // Removes a heap from the manager, then frees it and any resources
245 : // associated with it. This does not remove the heap pointer from the
246 : // heaps_ structure.
247 : // @note This must be called under lock_.
248 : void DestroyHeapResourcesUnlocked(BlockHeapInterface* heap,
249 : BlockQuarantineInterface* quarantine);
250 :
251 : // If the quarantine of a heap is over its maximum size, trim it down until
252 : // it's below the limit. If parameters_.quarantine_size is 0 then
253 : // then quarantine is flushed.
254 : // @param quarantine The quarantine to trim.
255 : // TODO(peterssen): Change the 0-size contract. The quarantine 'contract'
256 : // establish that when the size is 0, it means unlimited, this is rather
257 : // awkward since trimming with size 0 should flush the quarantine.
258 : void TrimQuarantine(BlockQuarantineInterface* quarantine);
259 :
260 : // Free a vector of blocks.
261 : // @param vec The vector of blocks to be freed.
262 : void FreeBlockVector(BlockQuarantineInterface::ObjectVector& vec);
263 :
264 : // Free a block that might be corrupt. If the block is corrupt first reports
265 : // an error before safely releasing the block.
266 : // @param block_info The information about this block.
267 : // @returns true if the block has been successfully freed, false otherwise.
268 : bool FreePotentiallyCorruptBlock(BlockInfo* block_info);
269 :
270 : // Free a corrupt block. This takes care of cleaning its metadata before
271 : // trying to free it.
272 : // @param block_info The information about this block.
273 : // @returns true if the block has been successfully freed, false otherwise.
274 : bool FreeCorruptBlock(BlockInfo* block_info);
275 :
276 : // Free an allocated block. This should be called when a block is removed from
277 : // the quarantine or directly freed. This takes care of updating the shadow
278 : // memory and releasing the resources acquired by this block (like its stack
279 : // traces). The block should either not be corrupt or cleaned from its unsafe
280 : // metadata.
281 : // @param block_info The information about this block.
282 : // @returns true on success, false otherwise.
283 : bool FreePristineBlock(BlockInfo* block_info);
284 :
285 : // Free an unguarded allocation.
286 : // @param heap_id A hint about the heap that might contain this allocation.
287 : // @param alloc The allocation to be freed.
288 : // @returns true if the allocation has been successfully freed, false
289 : // otherwise.
290 : bool FreeUnguardedAlloc(HeapId heap_id, void* alloc);
291 :
292 : // Clears the metadata of a corrupt block. After calling this function the
293 : // block can safely be passed to FreeBlock.
294 : // @param block_info The information about this block.
295 : void ClearCorruptBlockMetadata(BlockInfo* block_info);
296 :
297 : // Reports a heap error via the heap error callback. This is for originating
298 : // errors that are detected while performing operations on a heap metadata.
299 : // Read/write errors are detected outside of the manager, and query the heap
300 : // for information about the error itself.
301 : // @param address The address that was being accessed/manipulating when the
302 : // error was detected.
303 : // @param kind The type of error encountered.
304 : void ReportHeapError(void* address, BadAccessKind kind);
305 :
306 : // Initializes internal heap structures, if not yet done. This must be called
307 : // before PropagateParameters and InitProcessHeap.
308 : void InitInternalHeap();
309 :
310 : // Initialize the process heap. This is only meant to be called at
311 : // initialization time when process_heap_ is NULL.
312 : // Exposed for unittesting.
313 : void InitProcessHeap();
314 :
315 : // Initialize the rate targeted heaps.
316 : void InitRateTargetedHeaps();
317 :
318 : // Determines if the large block heap should be used for an allocation of
319 : // the given size.
320 : // @param bytes The allocation size.
321 : // @returns true if the large block heap should be used for this allocation,
322 : // false otherwise.
323 : bool MayUseLargeBlockHeap(size_t bytes) const;
324 :
325 : // Determines if the zebra block heap should be used for an allocation of
326 : // the given size.
327 : // @param bytes The allocation size.
328 : // @returns true if the zebra heap should be used for this allocation, false
329 : // otherwise.
330 : bool MayUseZebraBlockHeap(size_t bytes) const;
331 :
332 : // Determines if we should use a rate targeted heap for an allocation of the
333 : // given size.
334 : // @param bytes The allocation size.
335 : // @returns true if a rate targeted heap should be used for this allocation,
336 : // false otherwise.
337 : bool MayUseRateTargetedHeap(size_t bytes) const;
338 :
339 : // Given an allocation stack, choose the rate targeted heap that should be
340 : // used to serve it.
341 : // @param stack The allocation stack.
342 : // @returns The rate targeted heap that should serve this allocation.
343 : HeapId ChooseRateTargetedHeap(const agent::common::StackCapture& stack);
344 :
345 : // The number of rate targeted heaps.
346 : // TODO(sebmarchand): Make this value configurable.
347 : static const size_t kRateTargetedHeapCount = 4;
348 :
349 : // The minimum and maximum sizes of the blocks that should go into the rate
350 : // targeted heaps. After analyzing crash data, two intervals of blocks have
351 : // been identified and targeted.
352 : // TODO(sebmarchand): Make these values configurable.
353 : static const size_t kDefaultRateTargetedHeapsMinBlockSize[2];
354 : static const size_t kDefaultRateTargetedHeapsMaxBlockSize[2];
355 :
356 : // The rate targeted heaps.
357 : HeapId rate_targeted_heaps_[kRateTargetedHeapCount];
358 :
359 : // The number of blocks that have been served by each rate targeted heap, for
360 : // unittesting.
361 : size_t rate_targeted_heaps_count_[kRateTargetedHeapCount];
362 :
363 : base::Lock targeted_heaps_info_lock_;
364 :
365 : // The information used by the rate targeted heaps.
366 : AllocationRateInfo targeted_heaps_info_; // Under targeted_heaps_info_lock_.
367 :
368 : // The stack cache used to store the stack traces.
369 : StackCaptureCache* stack_cache_;
370 :
371 : // Protects concurrent access to the heap manager internals.
372 : base::Lock lock_;
373 :
374 : // Indicates if 'Init' has been called.
375 : bool initialized_; // Under lock_.
376 :
377 : // Contains the heaps owned by this manager.
378 : HeapQuarantineMap heaps_; // Under lock_.
379 :
380 : // The quarantine shared by the heaps created by this manager. This is also
381 : // used by the LargeBlockHeap.
382 : ShardedBlockQuarantine shared_quarantine_;
383 :
384 : // Map the block heaps to their underlying heap.
385 : UnderlyingHeapMap underlying_heaps_map_; // Under lock_.
386 :
387 : // The parameters of this heap manager.
388 : ::common::AsanParameters parameters_;
389 :
390 : // The callback this manager uses to expose internal state errors. These are
391 : // caused by uninstrumented code (system libraries, etc), thus aren't caught
392 : // at their source. Catching their side effect as early as possible allows the
393 : // recovery of some useful debugging information.
394 : HeapErrorCallback heap_error_callback_;
395 :
396 : // The process heap.
397 : //
398 : // TODO(sebmarchand): Put the interception of the process heap behind a flag
399 : // and return the original process heap by default.
400 : BlockHeapInterface* process_heap_;
401 : HeapInterface* process_heap_underlying_heap_;
402 : HeapId process_heap_id_;
403 :
404 : // Memory notifier used to update the shadow memory.
405 : memory_notifiers::ShadowMemoryNotifier shadow_memory_notifier_;
406 :
407 : // The heap that gets used for allocation of internal data structures.
408 : scoped_ptr<HeapInterface> internal_win_heap_;
409 : scoped_ptr<HeapInterface> internal_heap_;
410 :
411 : // Hold the single ZebraBlockHeap instance used by this heap manager.
412 : // The lifetime management of the zebra heap is provided by the
413 : // HeapQuarantineMap, this is simply a useful pointer for finding the
414 : // zebra heap directly.
415 : heaps::ZebraBlockHeap* zebra_block_heap_;
416 : HeapId zebra_block_heap_id_;
417 :
418 : // The ID of the large block heap. Allows accessing it directly.
419 : HeapId large_block_heap_id_;
420 :
421 : // Stores the AllocationFilterFlag TLS slot.
422 : DWORD allocation_filter_flag_tls_;
423 :
424 : // A list of all heaps whose locks were acquired by the last call to
425 : // BestEffortLockAll. This uses the internal heap, otherwise the default
426 : // allocator makes use of the process heap. The process heap may itself
427 : // be locked when we try to use this, hence a deadlock can occur. This ends
428 : // up being a null terminated array of HeapInterface*.
429 : // Under lock_.
430 : HeapInterface** locked_heaps_;
431 :
432 : private:
433 : DISALLOW_COPY_AND_ASSIGN(BlockHeapManager);
434 : };
435 :
436 : } // namespace heap_managers
437 : } // namespace asan
438 : } // namespace agent
439 :
440 : #endif // SYZYGY_AGENT_ASAN_HEAP_MANAGERS_BLOCK_HEAP_MANAGER_H_
|