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