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