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 "syzygy/agent/asan/constants.h"
90 :
91 m : namespace agent {
92 :
93 : // Forward declaration.
94 m : namespace common {
95 m : class StackCapture;
96 m : } // namespace common
97 :
98 m : namespace asan {
99 :
100 : // Forward declaration.
101 m : struct BlockLayout;
102 :
103 : // Various constants for identifying the beginnings of regions of memory.
104 m : static const uint16 kBlockHeaderMagic = 0xCA80;
105 :
106 : // Various constants used for filling regions of memory.
107 m : static const uint8 kBlockHeaderPaddingByte = 0x1C;
108 m : static const uint8 kBlockTrailerPaddingByte = 0xC3;
109 :
110 : // The number of bits in the checksum field. This is parameterized so that
111 : // it can be referred to by the checksumming code.
112 m : static const size_t kBlockHeaderChecksumBits = 13;
113 :
114 : // The state of an Asan block. These are in the order that reflects the typical
115 : // lifespan of an allocation.
116 m : enum BlockState {
117 : // The block is allocated and valid for reading/writing.
118 m : ALLOCATED_BLOCK,
119 : // The block has been quarantined, and not valid for reading/writing.
120 : // While in the quarantine it is still allocated as far as the underlying
121 : // heap is concerned, and won't be reclaimed.
122 m : QUARANTINED_BLOCK,
123 : // The block has been returned to the heap and is eligible to be reused
124 : // in a future allocation. In the meantime it is still not valid for
125 : // reading and writing.
126 m : FREED_BLOCK,
127 m : };
128 :
129 : // Declares the block header that is found in every left redzone. Since
130 : // overwrites are far more common than underwrites critical information should
131 : // be stored here.
132 : #pragma pack(push, 1)
133 m : struct BlockHeader {
134 m : struct {
135 : // A magic constant that identifies the block header in memory.
136 m : unsigned magic : 16;
137 : // The checksum of the entire block. The semantics of this vary with the
138 : // block state.
139 m : unsigned checksum : kBlockHeaderChecksumBits;
140 : // If this bit is set then the block is a nested block.
141 m : unsigned is_nested : 1;
142 : // If this bit is positive then header padding is present. The size of the
143 : // header padding is encoded in the padding itself.
144 m : unsigned has_header_padding : 1;
145 : // If this bit is positive then trailer padding in excess of
146 : // kShadowRatio/2 is present, and the size of the trailer padding itself
147 : // will be encoded in these bytes. Otherwise it is implicit as
148 : // (kShadowRatio / 2) - (body_size % (kShadowRatio / 2)).
149 m : unsigned has_excess_trailer_padding : 1;
150 : // This is implicitly a BlockState value.
151 m : unsigned state : 2;
152 : // The size of the body of the allocation, in bytes.
153 m : unsigned body_size : 30;
154 m : };
155 : // The allocation stack of this block.
156 m : const common::StackCapture* alloc_stack;
157 : // The free stack of this block (NULL if not yet quarantined/freed).
158 m : const common::StackCapture* free_stack;
159 m : };
160 : #pragma pack(pop)
161 m : COMPILE_ASSERT((sizeof(BlockHeader) % kShadowRatio) == 0,
162 m : invalid_BlockHeader_mod_size);
163 m : COMPILE_ASSERT(sizeof(BlockHeader) == 16, invalid_BlockHeader_size);
164 :
165 : // Declares the block trailer that is found in every right redzone.
166 : // This should ideally be a multiple of size (n + 1/2) * kShadowRatio. This
167 : // is because on average we have half of kShadowRatio as padding trailing
168 : // the body of the allocation. This takes advantage of it, without incurring
169 : // additional penalty on allocation overhead (on average). As of late 2013
170 : // this is supported by the actual distribution of allocations in Chrome.
171 : #pragma pack(push, 1)
172 m : struct BlockTrailer {
173 : // The IDs of the threads that allocated/freed the block. If the block is
174 : // not yet quarantined/freed then |free_tid| is zero.
175 : // TODO(chrisha): Make these thread serial numbers, to deal with thread
176 : // number reuse. This can be accomplished in the agent via the existing
177 : // thread attach/detach callbacks.
178 m : uint32 alloc_tid;
179 m : uint32 free_tid;
180 : // The time at which the block was allocated. Combined with the address of
181 : // the block itself this acts as a (unique with high probability) serial
182 : // number for the block (especially if the heap is lazy to reuse
183 : // allocations).
184 m : uint32 alloc_ticks;
185 : // The time at which the block was freed (zero if not yet freed).
186 m : uint32 free_ticks;
187 : // The ID of the heap that allocated the block.
188 m : uint32 heap_id;
189 m : };
190 : #pragma pack(pop)
191 m : COMPILE_ASSERT((sizeof(BlockTrailer) % kShadowRatio) == (kShadowRatio / 2),
192 m : invalid_BlockTrailer_mod_size);
193 m : COMPILE_ASSERT(sizeof(BlockTrailer) == 20, invalid_BlockTrailer_size);
194 :
195 : // A structure for recording the minimum pertinent information about a block.
196 : // Can easily be expanded into a BlockInfo, but requires less space. This makes
197 : // it suitable for storing blocks in a quarantine, for example.
198 m : struct CompactBlockInfo {
199 : // Pointer to the beginning of the allocation.
200 m : uint8* block;
201 : // The size of the entire allocation.
202 m : uint32 block_size;
203 m : struct {
204 : // The entire size of the header, including padding.
205 m : unsigned header_size : 15;
206 : // The entire size of the trailer, including padding.
207 m : unsigned trailer_size : 15;
208 : // Indicates if the block is nested.
209 m : unsigned is_nested : 1;
210 m : };
211 m : };
212 m : COMPILE_ASSERT(sizeof(CompactBlockInfo) == 12, invalid_CompactBlockInfo_size);
213 :
214 : // A struct for initializing, modifying and navigating the various portions
215 : // of an allocated block. This can be initialized as part of the creation of
216 : // a new block, inferred from an in-memory investigation of an existing block
217 : // (assuming no corruption), or from an investigation of the shadow memory.
218 m : struct BlockInfo {
219 : // Points to the beginning of the entire allocation.
220 m : uint8* block;
221 : // The size of the entire allocation.
222 m : size_t block_size;
223 :
224 : // Left redzone. If there's no padding |header_padding| and |body| will
225 : // point to the same location, and |header_padding_size| will be zero.
226 m : BlockHeader* header;
227 m : uint8* header_padding;
228 m : size_t header_padding_size;
229 :
230 : // Body of the allocation.
231 m : uint8* body;
232 m : size_t body_size;
233 :
234 : // Right redzone. If there's no padding |trailer_padding| and |trailer| will
235 : // point to the same location, and |trailer_padding_size| will be zero.
236 m : uint8* trailer_padding;
237 m : size_t trailer_padding_size;
238 m : BlockTrailer* trailer;
239 :
240 : // Pages of memory that are *exclusive* to this block. These pages may be a
241 : // strict subset of the entire block, depending on how it was allocated.
242 : // These pages will have protections toggled as the block changes state.
243 : // These must stay contiguous.
244 m : uint8* block_pages;
245 m : size_t block_pages_size;
246 m : uint8* left_redzone_pages;
247 m : size_t left_redzone_pages_size;
248 m : uint8* right_redzone_pages;
249 m : size_t right_redzone_pages_size;
250 :
251 : // Indicates if the block is nested.
252 m : bool is_nested;
253 m : };
254 :
255 : // Plans the layout of a block given allocation requirements. The layout will
256 : // be of minimum size to respect the requested requirements. Padding will be
257 : // introduced to respect alignment constraints, and it will be added strictly
258 : // between the allocation body and the header/trailer (this lowers the
259 : // likelihood of over/underflows corrupting the metadata).
260 : // @param chunk_size The allocation will be assumed to be made with this
261 : // alignment, and will be a multiple of this in length. Must be a power of
262 : // 2, and >= kShadowRatio.
263 : // @param alignment The minimum alignment that the body of the allocation must
264 : // respect. This must be a power of two and satisfy
265 : // kShadowRatio <= |alignment| <= |chunk_size|.
266 : // @param size The size of the body of the allocation. Can be 0.
267 : // @param min_left_redzone_size The minimum size of the left redzone.
268 : // @param min_right_redzone_size The minimum size of the right redzone.
269 : // @param layout The layout structure to be populated.
270 : // @returns true if the layout of the block is valid, false otherwise.
271 m : bool BlockPlanLayout(size_t chunk_size,
272 m : size_t alignment,
273 m : size_t size,
274 m : size_t min_left_redzone_size,
275 m : size_t min_right_redzone_size,
276 m : BlockLayout* layout);
277 :
278 : // Given a fresh allocation and a block layout, lays out and initializes the
279 : // given block. Initializes everything except for the allocation stack and the
280 : // checksum. Initializes the block to the ALLOCATED_BLOCK state, setting
281 : // |alloc_ticks| and |alloc_tid|. Sets |alloc_stack| to NULL; the caller should
282 : // set this stack upon return so as to minimize the number of useless frames on
283 : // the stack. Does not set the checksum.
284 : // @param layout The layout to be respected.
285 : // @param allocation The allocation to be filled in. This must be of
286 : // |layout.block_size| in size, and be aligned with
287 : // |layout.block_alignment|.
288 : // @param is_nested Indicates if the block is nested.
289 : // @param block_info Will be filled in with pointers to the various portions
290 : // of the block. May be NULL.
291 : // @note The pages containing the block must be writable and readable.
292 m : void BlockInitialize(const BlockLayout& layout,
293 m : void* allocation,
294 m : bool is_nested,
295 m : BlockInfo* block_info);
296 :
297 : // Converts between the two BlockInfo formats. This will work as long as the
298 : // input is valid; garbage in implies garbage out.
299 : // @param compact The populated compact block info.
300 : // @param expanded The full expanded block info.
301 m : void ConvertBlockInfo(const CompactBlockInfo& compact, BlockInfo* expanded);
302 m : void ConvertBlockInfo(const BlockInfo& expanded, CompactBlockInfo* compact);
303 :
304 : // Given a pointer to a block examines memory and extracts the block layout.
305 : // This protects against invalid memory accesses that may occur as a result of
306 : // block corruption, or the block pages being protected; in case of error,
307 : // this will return false.
308 : // @param raw_block A pointer to the beginning of the block.
309 : // @param block_info The description of the block to be populated.
310 : // @returns true if a valid block was encountered at the provided location,
311 : // false otherwise.
312 m : bool BlockInfoFromMemory(const void* raw_block, CompactBlockInfo* block_info);
313 m : bool BlockInfoFromMemory(const void* raw_block, BlockInfo* block_info);
314 :
315 : // Given a block body, finds the header. To find any other part of the
316 : // block first parse it using BlockInfoFromMemory. This protects against
317 : // invalid memory accesses that may occur as a result of block corruption,
318 : // or the block pages being protected; in case of error, this will return
319 : // NULL.
320 : // @param body The body of the block.
321 : // @returns a pointer to the block header, NULL if it was not found or in
322 : // case of error.
323 m : BlockHeader* BlockGetHeaderFromBody(const void* body);
324 :
325 : // @name Checksum related functions.
326 : // @{
327 : // Calculates the checksum for the given block. This causes the contents
328 : // of the block header to be modified temporarily while calculating the
329 : // checksum, and as such is not thread safe.
330 : // @param block_info The block to be checksummed.
331 : // @returns the calculated checksum.
332 : // @note The pages containing the block must be writable and readable.
333 m : uint32 BlockCalculateChecksum(const BlockInfo& block_info);
334 :
335 : // Determines if the block checksum is valid.
336 : // @param block_info The block to be validated.
337 : // @returns true on success, false otherwise.
338 : // @note The pages containing the block must be writable and readable.
339 m : bool BlockChecksumIsValid(const BlockInfo& block_info);
340 :
341 : // Calculates and sets the block checksum in place.
342 : // @param block_info The block to be checksummed.
343 : // @note The pages containing the block must be writable and readable.
344 m : void BlockSetChecksum(const BlockInfo& block_info);
345 : // @}
346 :
347 :
348 : // @name Block analysis related functions and declarations.
349 : // @{
350 : // An enumeration of possible states of snippets of data.
351 m : enum DataState {
352 : // Unable to determine if the data is corrupt or clean.
353 m : kDataStateUnknown,
354 : // The data is in a known good state.
355 m : kDataIsClean,
356 : // The data is corrupt.
357 m : kDataIsCorrupt,
358 m : };
359 :
360 : // Results of an analysis of block contents.
361 m : struct BlockAnalysisResult {
362 : // The overall result of the block state.
363 m : DataState block_state;
364 : // The state of the sub-components of the block.
365 m : DataState header_state;
366 m : DataState body_state;
367 m : DataState trailer_state;
368 m : };
369 :
370 : // Analyzes a block for types of corruption. For each of the header,
371 : // the body and the trailer, determines their state.
372 : // TODO(chrisha): This currently gets data via singleton AsanRuntime.
373 : // Open a seam and use dependency injection for this?
374 : // @param block_info The block to be analyzed.
375 : // @param result The determined state of the block will be written
376 : // here.
377 : // @note The pages of the block must be readable.
378 m : void BlockAnalyze(const BlockInfo& block_info,
379 m : BlockAnalysisResult* result);
380 :
381 : // @}
382 :
383 m : } // namespace asan
384 m : } // namespace agent
385 :
386 : #include "syzygy/agent/asan/block_impl.h"
387 :
388 : #endif // SYZYGY_AGENT_ASAN_BLOCK_H_
|