1 : // Copyright 2012 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 : // Implements HeapProxy, a class that wraps Win32 heap allocations but adds
16 : // heap/tail redzones.
17 :
18 : #ifndef SYZYGY_AGENT_ASAN_ASAN_HEAP_H_
19 : #define SYZYGY_AGENT_ASAN_ASAN_HEAP_H_
20 :
21 : #include <windows.h> // NOLINT
22 :
23 : #include "base/logging.h"
24 : #include "base/string_piece.h"
25 : #include "base/debug/stack_trace.h"
26 : #include "base/synchronization/lock.h"
27 : #include "syzygy/agent/asan/stack_capture_cache.h"
28 : #include "syzygy/agent/common/dlist.h"
29 :
30 : namespace agent {
31 : namespace asan {
32 :
33 : // Forward declaration.
34 : class StackCapture;
35 : class StackCaptureCache;
36 : struct AsanErrorInfo;
37 :
38 : // Makes like a Win32 heap manager heap, but adds a redzone before and after
39 : // each allocation and maintains a quarantine list of freed blocks.
40 : class HeapProxy {
41 : public:
42 : // The different memory access modes that we can encounter.
43 : enum AccessMode {
44 : ASAN_READ_ACCESS,
45 : ASAN_WRITE_ACCESS,
46 : ASAN_UNKNOWN_ACCESS
47 : };
48 :
49 : // Enumeration of the different kinds of bad heap accesses that we can
50 : // encounter.
51 : enum BadAccessKind {
52 : // This enum should start with bad access type that are not relative to a
53 : // heap block.
54 : // @note The ordering is important because those labels are used in
55 : // numeric inequalities.
56 : UNKNOWN_BAD_ACCESS,
57 : WILD_ACCESS,
58 : INVALID_ADDRESS,
59 :
60 : // This enum should end with bad access types that are relative to heap
61 : // blocks.
62 : USE_AFTER_FREE,
63 : HEAP_BUFFER_OVERFLOW,
64 : HEAP_BUFFER_UNDERFLOW,
65 : DOUBLE_FREE
66 : };
67 :
68 : // The different types of error we can encounter.
69 : static const char* kHeapUseAfterFree;
70 : static const char* kHeapBufferUnderFlow;
71 : static const char* kHeapBufferOverFlow;
72 : static const char* kAttemptingDoubleFree;
73 : static const char* kInvalidAddress;
74 : static const char* kWildAccess;
75 : static const char* kHeapUnknownError;
76 :
77 : // The sleep time (in milliseconds) used to approximate the CPU frequency.
78 : // Exposed for testing.
79 : static const size_t kSleepTimeForApproximatingCPUFrequency = 100;
80 :
81 : HeapProxy();
82 : ~HeapProxy();
83 :
84 : // @name Cast to/from HANDLE.
85 : // @{
86 : static HANDLE ToHandle(HeapProxy* proxy);
87 : static HeapProxy* FromHandle(HANDLE heap);
88 : // @}
89 :
90 : // @name Heap interface.
91 : // @{
92 : bool Create(DWORD options,
93 : size_t initial_size,
94 : size_t maximum_size);
95 : bool Destroy();
96 : void* Alloc(DWORD flags, size_t bytes);
97 : void* ReAlloc(DWORD flags, void* mem, size_t bytes);
98 : bool Free(DWORD flags, void* mem);
99 : size_t Size(DWORD flags, const void* mem);
100 : bool Validate(DWORD flags, const void* mem);
101 : size_t Compact(DWORD flags);
102 : bool Lock();
103 : bool Unlock();
104 : bool Walk(PROCESS_HEAP_ENTRY* entry);
105 : bool SetInformation(HEAP_INFORMATION_CLASS info_class,
106 : void* info,
107 : size_t info_length);
108 : bool QueryInformation(HEAP_INFORMATION_CLASS info_class,
109 : void* info,
110 : size_t info_length,
111 : unsigned long* return_length);
112 : // @}
113 :
114 : // Get information about a bad access.
115 : // @param bad_access_info Will receive the information about this access.
116 : // @returns true if the address belongs to a memory block, false otherwise.
117 : static bool GetBadAccessInformation(AsanErrorInfo* bad_access_info);
118 :
119 : // @name Cast to/from HANDLE.
120 : // @{
121 : static LIST_ENTRY* ToListEntry(HeapProxy* proxy);
122 : static HeapProxy* FromListEntry(LIST_ENTRY* list_entry);
123 : // @}
124 :
125 : // Set the default max size of the quarantine of a heap proxy.
126 : // @param quarantine_size The maximum size of the quarantine list, in
127 : // bytes.
128 : static void set_default_quarantine_max_size(
129 E : size_t default_quarantine_max_size) {
130 E : default_quarantine_max_size_ = default_quarantine_max_size;
131 E : }
132 :
133 : // Get the default max size of the quarantine of a heap proxy.
134 E : static size_t default_quarantine_max_size() {
135 E : return default_quarantine_max_size_;
136 E : }
137 :
138 : // Set the max size of the quarantine of a heap proxy. If the current size of
139 : // the quarantine is greater than this new max size then the extra blocks are
140 : // removed from the quarantine.
141 : // @param quarantine_size The maximum size of the quarantine list, in
142 : // bytes.
143 : void SetQuarantineMaxSize(size_t quarantine_max_size);
144 :
145 : // Get the max size of the quarantine of a heap proxy.
146 E : size_t quarantine_max_size() {
147 E : return quarantine_max_size_;
148 E : }
149 :
150 : // Set the trailer padding size.
151 : // @param trailer_padding_size The trailer padding size, in bytes.
152 E : static void set_trailer_padding_size(size_t trailer_padding_size) {
153 E : trailer_padding_size_ = trailer_padding_size;
154 E : }
155 :
156 : // Get the trailer padding size.
157 E : static size_t trailer_padding_size() {
158 E : return trailer_padding_size_;
159 E : }
160 :
161 : // Static initialization of HeapProxy context.
162 : // @param cache The stack capture cache shared by the HeapProxy.
163 : static void Init(StackCaptureCache* cache);
164 :
165 : // Returns a string describing a bad access kind.
166 : static const char* AccessTypeToStr(BadAccessKind bad_access_kind);
167 :
168 : // Calculates the underlying allocation size for a requested allocation of
169 : // @p bytes, with an alignment of @p alignment bytes.
170 : static size_t GetAllocSize(size_t bytes, size_t alignment);
171 :
172 : // Returns the location and size of the ASan block wrapping a given user
173 : // pointer.
174 : // @param user_pointer The user pointer for this ASan block.
175 : // @param asan_pointer Receives the ASan pointer.
176 : // @param size Receives the size of this ASan block.
177 : static void GetAsanExtent(const void* user_pointer,
178 : void** asan_pointer,
179 : size_t* size);
180 :
181 : // Given a pointer to an ASan wrapped allocation, returns the location and
182 : // size of the user data contained within.
183 : // @param asan_pointer The pointer to the ASan block.
184 : // @param user_pointer Receives the user pointer.
185 : // @param size Receives the size of the user part of this block.
186 : static void GetUserExtent(const void* asan_pointer,
187 : void** user_pointer,
188 : size_t* size);
189 :
190 : // Initialize an ASan block. This will red-zone the header and trailer, green
191 : // zone the user data, and save the allocation stack trace and other metadata.
192 : // @param asan_pointer The ASan block to initialize.
193 : // @param user_size The user size for this block.
194 : // @param asan_size The total size of this block.
195 : // @param alloc_granularity_log The allocation granularity for this block.
196 : // @param stack The allocation stack capture for this block.
197 : // @returns The user pointer for this block on success, NULL otherwise.
198 : static void* InitializeAsanBlock(uint8* asan_pointer,
199 : size_t user_size,
200 : size_t asan_size,
201 : size_t alloc_granularity_log,
202 : const StackCapture& stack);
203 :
204 : // Mark the given block as freed, but still residing in memory. This will
205 : // red-zone the user data and grab a free stack trace and other metadata.
206 : // After this call the object is effectively quarantined and access to it will
207 : // be caught as errors.
208 : // @param asan_pointer The pointer to the ASan block.
209 : // @param stack The free stack capture for this block.
210 : static void MarkBlockAsQuarantined(void* asan_pointer,
211 : const StackCapture& stack);
212 :
213 : // Clean up the object's metadata. The object is dead entirely, clean up the
214 : // metadata. This makes sure that we can decrement stack trace ref-counts and
215 : // reap them. This leaves the memory red-zoned (inaccessible).
216 : // @param asan_pointer The pointer to the ASan block.
217 : static void DestroyAsanBlock(void* asan_pointer);
218 :
219 : // Clones an object from one location to another. This mediates access to the
220 : // protected header and footer wrapping the user object, as the client code
221 : // may itself be instrumented. This will also copy the shadow memory and the
222 : // contents of the block: the new object will preserve the alive or free
223 : // status of the old object.
224 : // NOTES:
225 : // - The client must ensure there is sufficient room at the destination for
226 : // the object to be cloned.
227 : // - If the source object is no longer needed it is up to the client to call
228 : // QuarantineObject or DestroyObject.
229 : // - It is up to the client to ensure that the destination address meets any
230 : // alignment requirements of the source object.
231 : // @param src_asan_pointer The pointer to the ASan source block.
232 : // @param dst_asan_pointer The pointer to the ASan destination block.
233 : static void CloneObject(const void* src_asan_pointer,
234 : void* dst_asan_pointer);
235 :
236 : protected:
237 : enum BlockState {
238 : ALLOCATED,
239 : FREED,
240 : QUARANTINED,
241 : };
242 :
243 : // Every allocated block starts with a BlockHeader...
244 : struct BlockHeader {
245 : size_t magic_number : 24;
246 : BlockState state : 4;
247 : size_t alignment_log : 4;
248 : size_t block_size;
249 : const StackCapture* alloc_stack;
250 : const StackCapture* free_stack;
251 : };
252 : COMPILE_ASSERT((sizeof(BlockHeader) & 7) == 0,
253 : asan_block_header_not_multiple_of_8_bytes);
254 : COMPILE_ASSERT(sizeof(BlockHeader) == 16, asan_block_header_too_big);
255 :
256 : // ... and ends with a BlockTrailer.
257 : #pragma pack(push, 4)
258 : struct BlockTrailer {
259 : DWORD alloc_tid;
260 : uint64 free_timestamp;
261 : DWORD free_tid;
262 : // Free blocks are linked together.
263 : BlockHeader* next_free_block;
264 : };
265 : #pragma pack(pop)
266 : COMPILE_ASSERT(sizeof(BlockTrailer) == 20, asan_block_trailer_too_big);
267 :
268 : // Magic number to identify the beginning of a block header.
269 : static const size_t kBlockHeaderSignature = 0xCA80;
270 :
271 : // Mark a block as quarantined. This will red-zone the user data, and save the
272 : // deallocation stack trace and other metadata.
273 : // @param block_header The header for this block.
274 : // @param stack The deallocation stack for this block.
275 : // @returns true on success, false otherwise.
276 : static bool MarkBlockAsQuarantined(BlockHeader* block_header,
277 : const StackCapture& stack);
278 :
279 : // Clean up the metadata of an ASan block.
280 : // @param block_header The header of the block.
281 : // @param block_header The trailer of the block.
282 : // @note This leaves the memory red-zoned.
283 : static void ReleaseASanBlock(BlockHeader* block_header,
284 : BlockTrailer* block_trailer);
285 :
286 : // Returns the block header for a user pointer.
287 : // @param user_pointer The user pointer for which we want the block header
288 : // pointer.
289 : // @returns A pointer to the block header of @p user_pointer on success, NULL
290 : // otherwise.
291 : static BlockHeader* UserPointerToBlockHeader(const void* user_pointer);
292 :
293 : // Returns the ASan pointer for a user pointer. This should be equal to the
294 : // block pointer for the blocks allocated by this proxy.
295 : // @param user_pointer The user pointer for which we want the ASan pointer.
296 : // @returns A pointer to the ASan pointer of @p user_pointer on success, NULL
297 : // otherwise.
298 : static uint8* UserPointerToAsanPointer(const void* user_pointer);
299 :
300 : // Returns the block header for an ASan pointer.
301 : // @param asan_pointer The ASan pointer for which we want the block header
302 : // pointer.
303 : // @returns A pointer to the block header of @p asan_pointer on success, NULL
304 : // otherwise.
305 : static BlockHeader* AsanPointerToBlockHeader(void* asan_pointer);
306 :
307 : // Returns the user pointer for an ASan pointer.
308 : // @param asan_pointer The ASan pointer for which we want the user pointer.
309 : // @returns A pointer to the user pointer of @p asan_pointer on success, NULL
310 : // otherwise.
311 : static uint8* AsanPointerToUserPointer(void* asan_pointer);
312 :
313 : // Returns the ASan pointer for a block header.
314 : // @param header The block header pointer for which we want the ASan pointer.
315 : // @returns A pointer to the ASan pointer of @p header.
316 : static uint8* BlockHeaderToAsanPointer(const BlockHeader* header);
317 :
318 : // Returns the user pointer for a block header.
319 : // @param header The block header pointer for which we want the user pointer.
320 : // @returns A pointer to the user pointer of @p header.
321 : static uint8* BlockHeaderToUserPointer(BlockHeader* header);
322 :
323 : // Returns the block trailer for a block header.
324 : // @param block The block header pointer for which we want the block trailer
325 : // pointer.
326 : // @returns A pointer to the block trailer of @p header.
327 : // @note This function doesn't validate its return value, it just checks that
328 : // the given block header is valid and returns a pointer to the location
329 : // where the trailer should be.
330 : static BlockTrailer* BlockHeaderToBlockTrailer(const BlockHeader* header);
331 :
332 : // Returns the time since the block @p header was freed (in microseconds).
333 : // @param header The block for which we want the time since free.
334 : static uint64 GetTimeSinceFree(const BlockHeader* header);
335 :
336 : // Give the type of a bad heap access corresponding to an address.
337 : // @param addr The address causing a bad heap access.
338 : // @param header The header of the block containing this address.
339 : // @returns The type of the bad heap access corresponding to this address.
340 : static BadAccessKind GetBadAccessKind(const void* addr, BlockHeader* header);
341 :
342 : // Get the information about an address relative to a block.
343 : // @param header The header of the block containing this address.
344 : // @param bad_access_info Will receive the information about this address.
345 : static void GetAddressInformation(BlockHeader* header,
346 : AsanErrorInfo* bad_access_info);
347 :
348 : // Find the memory block containing @p addr.
349 : // @param addr The address for which we want to find the containing block.
350 : // @note |addr| may be in the header or trailer of the block, not strictly
351 : // within its data.
352 : // @returns a pointer to this memory block in case of success, NULL otherwise.
353 : static BlockHeader* FindBlockContainingAddress(uint8* addr);
354 :
355 : // Find the memory block containing the block @p inner_block.
356 : // @param inner_block The block for which we want to find the containing
357 : // block.
358 : // @returns a pointer to this memory block in case of success, NULL otherwise.
359 : static BlockHeader* FindContainingBlock(BlockHeader* inner_block);
360 :
361 : // Find the freed memory block containing the block @p inner_block.
362 : // @param inner_block The block for which we want to find the containing
363 : // freed block.
364 : // @returns a pointer to this memory block in case of success, NULL otherwise.
365 : static BlockHeader* FindContainingFreedBlock(BlockHeader* inner_block);
366 :
367 : // Quarantines @p block and trims the quarantine if it has grown too big.
368 : // @param block The block to quarantine.
369 : void QuarantineBlock(BlockHeader* block);
370 :
371 : // If the quarantine size is over quarantine_max_size_, trim it down until
372 : // it's below the limit.
373 : void TrimQuarantine();
374 :
375 : // Arbitrarily keep 16 megabytes of quarantine per heap by default.
376 : static const size_t kDefaultQuarantineMaxSize = 16 * 1024 * 1024;
377 :
378 : // By default we use no additional padding between heap blocks, beyond the
379 : // header and footer.
380 : static const size_t kDefaultTrailerPaddingSize = 0;
381 :
382 : // The default alloc granularity. The Windows heap is 8-byte granular, so
383 : // there's no gain in a lower allocation granularity.
384 : static const size_t kDefaultAllocGranularity = 8;
385 : static const uint16 kDefaultAllocGranularityLog = 3;
386 :
387 : // Default max size of blocks in quarantine (in bytes).
388 : static size_t default_quarantine_max_size_;
389 :
390 : // The size of the padding that we append to every block (in bytes). Defaults
391 : // to zero.
392 : static size_t trailer_padding_size_;
393 :
394 : // The number of CPU cycles per microsecond on the current machine.
395 : static double cpu_cycles_per_us_;
396 :
397 : // The underlying heap we delegate to.
398 : HANDLE heap_;
399 :
400 : // A repository of unique stack captures recorded on alloc and free.
401 : // @note This variable is declared as static to improve the stack cache
402 : // compression for the process with several heap.
403 : static StackCaptureCache* stack_cache_;
404 :
405 : // Protects concurrent access to HeapProxy internals.
406 : base::Lock lock_;
407 :
408 : // Points to the head of the quarantine queue.
409 : BlockHeader* head_; // Under lock_.
410 :
411 : // Points to the tail of the quarantine queue.
412 : BlockHeader* tail_; // Under lock_.
413 :
414 : // Total size of blocks in quarantine.
415 : size_t quarantine_size_; // Under lock_.
416 :
417 : // Max size of blocks in quarantine.
418 : size_t quarantine_max_size_; // Under lock_.
419 :
420 : // The entry linking to us.
421 : LIST_ENTRY list_entry_;
422 : };
423 :
424 : } // namespace asan
425 : } // namespace agent
426 :
427 : #endif // SYZYGY_AGENT_ASAN_ASAN_HEAP_H_
|