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 : // Describes and declares an Asan block, which is fundamentally a single
16 : // instrumented allocation of memory.
17 : //
18 : // Under Asan instrumentation allocations are instrumented with leading
19 : // (left) and trailing (right) redzones. The left redzone contains a
20 : // BlockHeader, while the right redzone contains a BlockTrailer. Each of
21 : // these contain metadata about the allocation itself. In both cases the
22 : // redzones may be larger than the headers they contain. Visually, a block is
23 : // laid out as follows:
24 : //
25 : // +------------------+ <-- N>=8 aligned \
26 : // | header | |
27 : // +------------------+ |- left redzone
28 : // | header padding | | (mod 8 in size)
29 : // | (optional) | /
30 : // +------------------+ <-- N>=8 aligned
31 : // | body |
32 : // +------------------+
33 : // | trailer padding | \
34 : // | (optional) | |_ right redzone
35 : // +------------------+ |
36 : // | trailer | /
37 : // +------------------+ <-- N>=8 aligned
38 : //
39 : // The information contained in the block headers is insufficient to recover
40 : // the block extents. However, sufficiently detailed bookkeeping information is
41 : // maintained in the shadow memory to allow inferring this data given a block
42 : // pointer.
43 : //
44 : // NAVIGATING A BLOCK
45 : //
46 : // If the block is not corrupt it contains sufficient information to navigate
47 : // the various components simply from inspecting the contents of memory itself.
48 : //
49 : // In the absence of any header padding the body immediately follows the
50 : // header, and the length of the body is encoded directly in the header. The
51 : // header has a bit indicating the presence of header padding. If present it
52 : // has a length of at least kShadowRatio[1], and encodes the total length of
53 : // the padding in the first 4 *and* last 4 bytes of the padding. This makes it
54 : // possible to navigate in O(1) time from the body to the header and vice
55 : // versa.
56 : //
57 : // There is always some implicit minimal amount of trailer padding required to
58 : // flesh out the block body such that the end of the trailer is properly
59 : // aligned. Another header bit indicates if there is more than this implicit
60 : // padding present. If so, the trailer padding length is explicitly encoded in
61 : // the first 4 bytes of the trailer padding. Either way it is possible to
62 : // navigate to the beginning of the trailer.
63 : //
64 : // The rest of the header and trailer padding are filled with constant values
65 : // as a visual debugging aid. An example block (with body of size 16, header
66 : // padding of size 16, and trailer padding of 12) is shown in memory:
67 : //
68 : // | 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
69 : // --+------------------------------------------------
70 : // 00| 80 CA .. .. .. .. .. .. .. .. .. .. .. .. .. ..
71 : // | magic \______________header data______________/
72 : // 10| 10 00 00 00 1C 1C 1C 1C 1C 1C 1C 1C 10 00 00 00
73 : // | \_length__/ \____padding bytes____/ \_length__/
74 : // 20| .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
75 : // | \____________________body_____________________/
76 : // 30| 0C 00 00 00 C3 C3 C3 C3 C3 C3 C3 C3 .. .. .. ..
77 : // | \_length__/ \____padding bytes____/ \___trailer
78 : // 40| .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
79 : // | _________________trailer data_________________/
80 : //
81 : // [1] kShadowRatio: The ratio of main memory to shadow memory. This many
82 : // bytes of main memory map to a single byte of shadow memory. Currently
83 : // 8:1, but may be higher.
84 :
85 : #ifndef SYZYGY_AGENT_ASAN_BLOCK_H_
86 : #define SYZYGY_AGENT_ASAN_BLOCK_H_
87 :
88 : #include "base/callback.h"
89 : #include "base/logging.h"
90 : #include "syzygy/agent/asan/constants.h"
91 :
92 : namespace agent {
93 :
94 : // Forward declaration.
95 : namespace common {
96 : class StackCapture;
97 : } // namespace common
98 :
99 : namespace asan {
100 :
101 : // Forward declarations.
102 : struct BlockLayout;
103 : class Shadow;
104 :
105 : // Various constants for identifying the beginnings of regions of memory.
106 : static const uint16_t kBlockHeaderMagic = 0xCA80;
107 :
108 : // Various constants used for filling regions of memory.
109 : static const uint8_t kBlockHeaderPaddingByte = 0x1C;
110 : static const uint8_t kBlockTrailerPaddingByte = 0xC3;
111 : static const uint8_t kBlockFloodFillByte = 0xFD;
112 :
113 : // The number of bits in the checksum field. This is parameterized so that
114 : // it can be referred to by the checksumming code.
115 : static const size_t kBlockHeaderChecksumBits = 13;
116 :
117 : // The state of an Asan block. These are in the order that reflects the typical
118 : // lifespan of an allocation.
119 : enum BlockState {
120 : // The block is allocated and valid for reading/writing.
121 : ALLOCATED_BLOCK,
122 : // The block has been quarantined, and not valid for reading/writing.
123 : // While in the quarantine it is still allocated as far as the underlying
124 : // heap is concerned, and won't be reclaimed.
125 : QUARANTINED_BLOCK,
126 : // The block is quarantined and its contents flood-filled. When a block is
127 : // quarantined in this mode it helps to identify the actual ranges of bytes
128 : // that have been overwritten in an uninstrumented use-after-free.
129 : QUARANTINED_FLOODED_BLOCK,
130 : // The block has been returned to the heap and is eligible to be reused
131 : // in a future allocation. In the meantime it is still not valid for
132 : // reading and writing.
133 : FREED_BLOCK,
134 :
135 : BLOCK_STATE_MAX,
136 : };
137 :
138 : // Declares the block header that is found in every left redzone. Since
139 : // overwrites are far more common than underwrites critical information should
140 : // be stored here.
141 : #pragma pack(push, 1)
142 : struct BlockHeader {
143 : struct {
144 : // A magic constant that identifies the block header in memory.
145 : unsigned magic : 16;
146 : // The checksum of the entire block. The semantics of this vary with the
147 : // block state.
148 : unsigned checksum : kBlockHeaderChecksumBits;
149 : // If this bit is set then the block is a nested block.
150 : unsigned is_nested : 1;
151 : // If this bit is positive then header padding is present. The size of the
152 : // header padding is encoded in the padding itself.
153 : unsigned has_header_padding : 1;
154 : // If this bit is positive then trailer padding in excess of
155 : // kShadowRatio/2 is present, and the size of the trailer padding itself
156 : // will be encoded in these bytes. Otherwise it is implicit as
157 : // (kShadowRatio / 2) - (body_size % (kShadowRatio / 2)).
158 : unsigned has_excess_trailer_padding : 1;
159 : // This is implicitly a BlockState value.
160 : unsigned state : 2;
161 : // The size of the body of the allocation, in bytes.
162 : unsigned body_size : 30;
163 : };
164 : // TODO(loskutov): replace pointers with something more compact.
165 : // The allocation stack of this block.
166 : const common::StackCapture* alloc_stack;
167 : // The free stack of this block (NULL if not yet quarantined/freed).
168 : const common::StackCapture* free_stack;
169 : };
170 : #pragma pack(pop)
171 : static_assert((sizeof(BlockHeader) % kShadowRatio) == 0,
172 : "Invalid BlockHeader mod size.");
173 : #ifdef _WIN64
174 : static_assert(sizeof(BlockHeader) == 24, "Invalid BlockHeader size.");
175 : #else
176 : static_assert(sizeof(BlockHeader) == 16, "Invalid BlockHeader size.");
177 : #endif
178 :
179 : // Declares dummy types for various parts of a block. These are used for type
180 : // safety of the various utility functions for navigating blocks. These are
181 : // forward declarations only and have no actual definition. This prevents them
182 : // from being used as anything other than pointers, and prohibits pointer
183 : // arithmetic.
184 : struct BlockHeaderPadding;
185 : struct BlockBody;
186 : struct BlockTrailerPadding;
187 :
188 : // Declares the block trailer that is found in every right redzone.
189 : // This should ideally be a multiple of size (n + 1/2) * kShadowRatio. This
190 : // is because on average we have half of kShadowRatio as padding trailing
191 : // the body of the allocation. This takes advantage of it, without incurring
192 : // additional penalty on allocation overhead (on average). As of late 2013
193 : // this is supported by the actual distribution of allocations in Chrome.
194 : #pragma pack(push, 1)
195 : struct BlockTrailer {
196 : // The IDs of the threads that allocated/freed the block. If the block is
197 : // not yet quarantined/freed then |free_tid| is zero.
198 : // TODO(chrisha): Make these thread serial numbers, to deal with thread
199 : // number reuse. This can be accomplished in the agent via the existing
200 : // thread attach/detach callbacks.
201 : uint32_t alloc_tid;
202 : uint32_t free_tid;
203 : // The time at which the block was allocated. Combined with the address of
204 : // the block itself this acts as a (unique with high probability) serial
205 : // number for the block (especially if the heap is lazy to reuse
206 : // allocations).
207 : uint32_t alloc_ticks;
208 : // The time at which the block was freed (zero if not yet freed).
209 : uint32_t free_ticks;
210 : // The ID of the heap that allocated the block.
211 : uint32_t heap_id;
212 : };
213 : #pragma pack(pop)
214 : static_assert((sizeof(BlockTrailer) % kShadowRatio) == (kShadowRatio / 2),
215 : "Invalid BlockTrailer mod size.");
216 : static_assert(sizeof(BlockTrailer) == 20, "Invalid BlockTrailer size.");
217 :
218 : // A structure for recording the minimum pertinent information about a block.
219 : // Can easily be expanded into a BlockInfo, but requires less space. This makes
220 : // it suitable for storing blocks in a quarantine, for example.
221 : // NOTE: If you want to navigate a block thoroughly and conveniently it is best
222 : // to first upgrade a CompactBlockInfo to a full BlockInfo struct.
223 : struct CompactBlockInfo {
224 : // Pointer to the beginning of the allocation.
225 : BlockHeader* header;
226 : // The size of the entire allocation. It's supposed to fit into 30 bits.
227 : // (See BlockHeader::body_size)
228 : uint32_t block_size;
229 : struct {
230 : // The entire size of the header, including padding.
231 : unsigned header_size : 15;
232 : // The entire size of the trailer, including padding.
233 : unsigned trailer_size : 15;
234 : // Indicates if the block is nested.
235 : unsigned is_nested : 1;
236 : };
237 : };
238 : #ifdef _WIN64
239 : static_assert(sizeof(CompactBlockInfo) == 16, "Invalid CompactBlockInfo size.");
240 : #else
241 : static_assert(sizeof(CompactBlockInfo) == 12, "Invalid CompactBlockInfo size.");
242 : #endif
243 :
244 : // A struct for initializing, modifying and navigating the various portions
245 : // of an allocated block. This can be initialized as part of the creation of
246 : // a new block, inferred from an in-memory investigation of an existing block
247 : // (assuming no corruption), or from an investigation of the shadow memory.
248 : struct BlockInfo {
249 : // The size of the entire allocation. This includes the header, the body,
250 : // the trailer and any padding. The block starts with the header.
251 : uint32_t block_size;
252 :
253 : // Left redzone. If there's no padding |header_padding| and |body| will
254 : // point to the same location, and |header_padding_size| will be zero.
255 : BlockHeader* header;
256 : BlockHeaderPadding* header_padding;
257 : uint32_t header_padding_size;
258 :
259 : // Body of the allocation.
260 : BlockBody* body;
261 : uint32_t body_size;
262 :
263 : // Right redzone. If there's no padding |trailer_padding| and |trailer| will
264 : // point to the same location, and |trailer_padding_size| will be zero.
265 : BlockTrailerPadding* trailer_padding;
266 : uint32_t trailer_padding_size;
267 : BlockTrailer* trailer;
268 :
269 : // Pages of memory that are *exclusive* to this block. These pages may be a
270 : // strict subset of the entire block, depending on how it was allocated.
271 : // These pages will have protections toggled as the block changes state.
272 : // These must stay contiguous.
273 : uint8_t* block_pages;
274 : uint32_t block_pages_size;
275 : uint8_t* left_redzone_pages;
276 : uint32_t left_redzone_pages_size;
277 : uint8_t* right_redzone_pages;
278 : uint32_t right_redzone_pages_size;
279 :
280 : // Indicates if the block is nested.
281 : bool is_nested;
282 :
283 : // Convenience accessors to various parts of the block. All access should be
284 : // gated through these as they provide strong bounds checking in debug
285 : // builds.
286 : // @name
287 : // @{
288 E : uint8_t* RawBlock() const { return reinterpret_cast<uint8_t*>(header); }
289 E : uint8_t& RawBlock(uint32_t index) const {
290 E : DCHECK_GT(block_size, index);
291 E : return RawBlock()[index];
292 E : }
293 E : uint8_t* RawHeader() const { return reinterpret_cast<uint8_t*>(header); }
294 E : uint8_t& RawHeader(uint32_t index) const {
295 E : DCHECK_GT(sizeof(BlockHeader), index);
296 E : return RawHeader()[index];
297 E : }
298 E : uint8_t* RawHeaderPadding() const {
299 E : return reinterpret_cast<uint8_t*>(header_padding);
300 E : }
301 E : uint8_t& RawHeaderPadding(uint32_t index) const {
302 E : DCHECK_GT(header_padding_size, index);
303 E : return RawHeaderPadding()[index];
304 E : }
305 E : uint8_t* RawBody() const { return reinterpret_cast<uint8_t*>(body); }
306 E : uint8_t& RawBody(uint32_t index) const {
307 E : DCHECK_GT(body_size, index);
308 E : return RawBody()[index];
309 E : }
310 E : uint8_t* RawTrailerPadding() const {
311 E : return reinterpret_cast<uint8_t*>(trailer_padding);
312 E : }
313 E : uint8_t& RawTrailerPadding(uint32_t index) const {
314 E : DCHECK_GT(trailer_padding_size, index);
315 E : return RawTrailerPadding()[index];
316 E : }
317 E : uint8_t* RawTrailer() const { return reinterpret_cast<uint8_t*>(trailer); }
318 E : uint8_t& RawTrailer(uint32_t index) const {
319 E : DCHECK_GT(sizeof(BlockTrailer), index);
320 E : return RawTrailer()[index];
321 E : }
322 : // @}
323 :
324 : // @returns the total header size, including the header and any padding.
325 E : uint32_t TotalHeaderSize() const {
326 E : return sizeof(BlockHeader) + header_padding_size;
327 E : }
328 :
329 : // @returns the total trailer size, including the trailer and any padding.
330 E : uint32_t TotalTrailerSize() const {
331 E : return sizeof(BlockTrailer) + trailer_padding_size;
332 E : }
333 : };
334 :
335 : // Plans the layout of a block given allocation requirements. The layout will
336 : // be of minimum size to respect the requested requirements. Padding will be
337 : // introduced to respect alignment constraints, and it will be added strictly
338 : // between the allocation body and the header/trailer (this lowers the
339 : // likelihood of over/underflows corrupting the metadata).
340 : // @param chunk_size The allocation will be assumed to be made with this
341 : // alignment, and will be a multiple of this in length. Must be a power of
342 : // 2, and >= kShadowRatio.
343 : // @param alignment The minimum alignment that the body of the allocation must
344 : // respect. This must be a power of two and satisfy
345 : // kShadowRatio <= |alignment| <= |chunk_size|.
346 : // @param size The size of the body of the allocation. Can be 0.
347 : // @param min_left_redzone_size The minimum size of the left redzone.
348 : // @param min_right_redzone_size The minimum size of the right redzone.
349 : // @param layout The layout structure to be populated.
350 : // @returns true if the layout of the block is valid, false otherwise.
351 : bool BlockPlanLayout(uint32_t chunk_size,
352 : uint32_t alignment,
353 : uint32_t size,
354 : uint32_t min_left_redzone_size,
355 : uint32_t min_right_redzone_size,
356 : BlockLayout* layout);
357 :
358 : // Given a fresh allocation and a block layout, lays out and initializes the
359 : // given block. Initializes everything except for the allocation stack and the
360 : // checksum. Initializes the block to the ALLOCATED_BLOCK state, setting
361 : // |alloc_ticks| and |alloc_tid|. Sets |alloc_stack| to NULL; the caller should
362 : // set this stack upon return so as to minimize the number of useless frames on
363 : // the stack. Does not set the checksum.
364 : // @param layout The layout to be respected.
365 : // @param allocation The allocation to be filled in. This must be of
366 : // |layout.block_size| in size, and be aligned with
367 : // |layout.block_alignment|.
368 : // @param is_nested Indicates if the block is nested.
369 : // @param block_info Will be filled in with pointers to the various portions
370 : // of the block. May be NULL.
371 : // @note The pages containing the block must be writable and readable.
372 : void BlockInitialize(const BlockLayout& layout,
373 : void* allocation,
374 : bool is_nested,
375 : BlockInfo* block_info);
376 :
377 : // Converts between the two BlockInfo formats. This will work as long as the
378 : // input is valid; garbage in implies garbage out.
379 : // @param compact The populated compact block info.
380 : // @param expanded The full expanded block info.
381 : void ConvertBlockInfo(const CompactBlockInfo& compact, BlockInfo* expanded);
382 : void ConvertBlockInfo(const BlockInfo& expanded, CompactBlockInfo* compact);
383 :
384 : // Given a pointer to a block examines memory and extracts the block layout.
385 : // This protects against invalid memory accesses that may occur as a result of
386 : // block corruption, or the block pages being protected; in case of error,
387 : // this will return false.
388 : // @note For unittesting the OnExceptionCallback may be used to determine if
389 : // an exception was handled.
390 : // @param header A pointer to the block header.
391 : // @param block_info The description of the block to be populated.
392 : // @returns true if a valid block was encountered at the provided location,
393 : // false otherwise.
394 : bool BlockInfoFromMemory(const BlockHeader* header,
395 : CompactBlockInfo* block_info);
396 : bool BlockInfoFromMemory(const BlockHeader* header, BlockInfo* block_info);
397 :
398 : // Given a block body, finds the header. To find any other part of the
399 : // block first parse it using BlockInfoFromMemory. This protects against
400 : // invalid memory accesses that may occur as a result of block corruption,
401 : // or the block pages being protected; in case of error, this will return
402 : // NULL.
403 : // @note For unittesting the OnExceptionCallback may be used to determine if
404 : // an exception was handled.
405 : // @param body The body of the block.
406 : // @returns a pointer to the block header, NULL if it was not found or in
407 : // case of error.
408 : BlockHeader* BlockGetHeaderFromBody(const BlockBody* body);
409 :
410 : // @name Checksum related functions.
411 : // @{
412 : // Calculates the checksum for the given block. This causes the contents
413 : // of the block header to be modified temporarily while calculating the
414 : // checksum, and as such is not thread safe.
415 : // @param block_info The block to be checksummed.
416 : // @returns the calculated checksum.
417 : // @note The pages containing the block must be writable and readable.
418 : uint32_t BlockCalculateChecksum(const BlockInfo& block_info);
419 :
420 : // Determines if the block checksum is valid.
421 : // @param block_info The block to be validated.
422 : // @returns true on success, false otherwise.
423 : // @note The pages containing the block must be writable and readable.
424 : bool BlockChecksumIsValid(const BlockInfo& block_info);
425 :
426 : // Calculates and sets the block checksum in place.
427 : // @param block_info The block to be checksummed.
428 : // @note The pages containing the block must be writable and readable.
429 : void BlockSetChecksum(const BlockInfo& block_info);
430 : // @}
431 :
432 : // Determines if the body of a block is a valid flood-filled body.
433 : // @param block_info The block to be checked.
434 : // @returns true if the body is appropriately flood-filled.
435 : bool BlockBodyIsFloodFilled(const BlockInfo& block_info);
436 :
437 : // Infers the most likely block state from an analysis of the block header,
438 : // contents, and the shadow memory.
439 : // @param shadow The shadow memory to be queried.
440 : // @param block_info The block to be analyzed.
441 : // @returns the likely state of the block.
442 : // @note The pages of the block must be readable.
443 : BlockState BlockDetermineMostLikelyState(const Shadow* shadow,
444 : const BlockInfo& block_info);
445 :
446 : // Determines if a block can be made checksum consistent with exactly
447 : // the given number of bitflips.
448 : // @param block_state The state of the block to be assumed during the
449 : // analysis. (The state encoded in the header may itself be corrupt.)
450 : // @param block_info The block to be analyzed.
451 : // @param bitflips The maximum number of bitflips to try. Values larger
452 : // than kBlockHeaderChecksumBits are meaningless.
453 : bool BlockBitFlipsFixChecksum(BlockState block_state,
454 : const BlockInfo& block_info,
455 : uint32_t bitflips);
456 :
457 : // Explores a block to see how many bitflips are required to make the checksum
458 : // valid. This is always at most kBlockHeaderChecksumBits.
459 : // @param block_state The state of the block to be assumed during the
460 : // analysis. (The state encoded in the header may itself be corrupt.)
461 : // @param block_info The block to be analyzed.
462 : // @param max_bitflips The maximum number of bitflips to try. Values larger
463 : // than kBlockHeaderChecksumBits are meaningless.
464 : // @returns the number of bitflips that are required to make the checksum
465 : // match.
466 : // @note The pages of the block must be readable and writable.
467 : // @nore Any checksum can be made good using exactly kBlockHeaderChecksumBits
468 : // bitflips.
469 : uint32_t BlockBitFlipsRequired(BlockState block_state,
470 : const BlockInfo& block_info,
471 : uint32_t max_bitflips);
472 :
473 : // @name Block analysis related functions and declarations.
474 : // @{
475 : // An enumeration of possible states of snippets of data.
476 : enum DataState {
477 : // Unable to determine if the data is corrupt or clean.
478 : kDataStateUnknown,
479 : // The data is in a known good state.
480 : kDataIsClean,
481 : // The data is corrupt.
482 : kDataIsCorrupt,
483 : };
484 :
485 : // Results of an analysis of block contents.
486 : struct BlockAnalysisResult {
487 : // The overall result of the block state.
488 : DataState block_state;
489 : // The state of the sub-components of the block.
490 : DataState header_state;
491 : DataState body_state;
492 : DataState trailer_state;
493 : };
494 :
495 : // Analyzes a block for types of corruption. For each of the header,
496 : // the body and the trailer, determines their state.
497 : // @param block_state The state of the block to be assumed during the
498 : // analysis. (The state encoded in the header may itself be corrupt.)
499 : // @param block_info The block to be analyzed.
500 : // @param result The determined state of the block will be written
501 : // here.
502 : // @note The pages of the block must be readable.
503 : void BlockAnalyze(BlockState block_state,
504 : const BlockInfo& block_info,
505 : BlockAnalysisResult* result);
506 :
507 : // @}
508 :
509 : // This is a testing seam. If a callback is provided it will be invoked by
510 : // the exception handling code in block.cc. Exceptions can occur due to the
511 : // RTL playing with page protections, but during unittests it is known whether
512 : // or not an exception should occur. This allows testing those expectations
513 : // explicitly.
514 : typedef base::Callback<void(EXCEPTION_POINTERS*)> OnExceptionCallback;
515 : void SetOnExceptionCallback(OnExceptionCallback callback);
516 : void ClearOnExceptionCallback();
517 :
518 : } // namespace asan
519 : } // namespace agent
520 :
521 : #include "syzygy/agent/asan/block_impl.h"
522 :
523 : #endif // SYZYGY_AGENT_ASAN_BLOCK_H_
|