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 an all-static class that manages shadow memory for Asan.
16 : //
17 : // The layout of a block is fully encoded in shadow memory, allowing for
18 : // recovery of the block simply by inspecting the shadow memory. This is
19 : // accomplished as follows:
20 : //
21 : // - Blocks are always a multiple of kShadowRatio in size and alignment.
22 : // - Each group of kShadowRatio contiguous bytes is represented by a single
23 : // marker in the shadow.
24 : // - The first marker of a block is a single block start marker, and the last
25 : // is a single block end marker. This uniquely identifies the beginning
26 : // and end of a block simply by scanning and looking for balanced markers.
27 : // - The left and right redzones are uniquely identified by distinct markers.
28 : // - The location of the header and trailer of a block are always at the
29 : // extremes, thus knowing the locations of the start and end markers
30 : // uniquely identifies their positions.
31 : // - The left redzone markers uniquely encodes the length of the header padding
32 : // as it must also be a multiple of kShadowRatio in length.
33 : // - The right redzone implies the length of the body of the allocation and
34 : // the trailer padding modulo kShadowRatio. The remaining bits are encoded
35 : // directly in the block start marker.
36 : // - Nested blocks and regular blocks use differing block start/end markers.
37 : // This allows navigation through allocation hierarchies to terminate
38 : // without necessitating a scan through the entire shadow memory.
39 : //
40 : // A typical block will look something like the following in shadow memory:
41 : //
42 : // 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
43 : // E7 FA FA FA 00 00 00 00 00 00 FB FB FB FB FB F4
44 : // | \______/ \_______________/ \____________/ |
45 : // | : | : +-- Block end.
46 : // | : | + - - - - - Right redzone.
47 : // | : +--------------------------- Body of allocation.
48 : // | +- - - - - - - - - - - - - - - - - - - - - Left redzone.
49 : // +----------------------------------------------- Block start.
50 : //
51 : // - Both the end marker and the start marker indicate the block
52 : // is not nested. Together they indicate the total length of the
53 : // block is 128 bytes.
54 : // - The start marker indicates that the body length is 7 % 8.
55 : // - The header padding indicates that the 16 byte header is followed
56 : // by a further 16 bytes of padding.
57 : // - The 6 body markers indicate an allocation size of 41..48 bytes.
58 : // Combined with the start marker bits the allocation size can be
59 : // inferred as being 47 bytes, with the last byte contributing to
60 : // the trailer padding.
61 : // - The 5 right redzone markers indicate that the 20 byte trailer is
62 : // preceded by at least 28 trailer padding bytes. The additional
63 : // padding from the body means that there are in total 29 trailer
64 : // padding bytes.
65 : // - 16(header) + 16(pad) + 47(body) + 29(pad) + 20(trailer) = 128
66 :
67 : #ifndef SYZYGY_AGENT_ASAN_SHADOW_H_
68 : #define SYZYGY_AGENT_ASAN_SHADOW_H_
69 :
70 : #include <string>
71 :
72 : #include "base/basictypes.h"
73 : #include "base/logging.h"
74 : #include "base/synchronization/lock.h"
75 : #include "syzygy/agent/asan/block.h"
76 : #include "syzygy/agent/asan/constants.h"
77 : #include "syzygy/agent/asan/shadow_marker.h"
78 :
79 : namespace agent {
80 : namespace asan {
81 :
82 : // An all-static class that manages the Asan shadow memory.
83 : class Shadow {
84 : public:
85 : // The first 64k of the memory are not addressable.
86 : static const size_t kAddressLowerBound = 0x10000;
87 :
88 : // One shadow byte for per group of kShadowRatio bytes in a 2G address space.
89 : // NOTE: This is dependent on the process NOT being large address aware.
90 : static const size_t kShadowSize = 1 << (31 - kShadowRatioLog);
91 :
92 : // We use a 2GB address space (2^31), divided into 4KB (2^12) pages, and only
93 : // need 1 bit per page.
94 : static const size_t kPageBitsSize = 1 << (31 - 12 - 3);
95 :
96 : // The upper bound of the addressable memory.
97 : static const size_t kAddressUpperBound = kShadowSize << kShadowRatioLog;
98 :
99 : // The number of shadow bytes to emit per line of a report.
100 : static const size_t kShadowBytesPerLine = 8;
101 :
102 : // The number of lines of shadow memory to emit before and after the
103 : // faulting address. Thus, information about
104 : //
105 : // (2 * kShadowContextLines + 1) * kShadowBytesPerLine
106 : //
107 : // shadow bytes will be reported in all.
108 : static const size_t kShadowContextLines = 4;
109 :
110 : // Set up the shadow memory.
111 : static void SetUp();
112 :
113 : // Tear down the shadow memory.
114 : static void TearDown();
115 :
116 : // Poisons @p size bytes starting at @p addr with @p shadow_val value.
117 : // @pre addr + size mod 8 == 0.
118 : // @param address The starting address.
119 : // @param size The size of the memory to poison.
120 : // @param shadow_val The poison marker value.
121 : static void Poison(const void* addr, size_t size, ShadowMarker shadow_val);
122 :
123 : // Un-poisons @p size bytes starting at @p addr.
124 : // @pre addr mod 8 == 0 && size mod 8 == 0.
125 : // @param addr The starting address.
126 : // @param size The size of the memory to unpoison.
127 : static void Unpoison(const void* addr, size_t size);
128 :
129 : // Mark @p size bytes starting at @p addr as freed. This will preserve
130 : // nested block headers/trailers/redzones, but mark all contents as freed.
131 : // It is expected that the states of all nested blocks have already been
132 : // marked as freed prior to possibly freeing the parent block.
133 : // @param addr The starting address.
134 : // @param size The size of the memory to mark as freed.
135 : static void MarkAsFreed(const void* addr, size_t size);
136 :
137 : // Returns true iff the byte at @p addr is not poisoned.
138 : // @param addr The address that we want to check.
139 : // @returns true if this address is accessible, false otherwise.
140 : static bool IsAccessible(const void* addr);
141 :
142 : // @param address The address that we want to check.
143 : // @returns true if the byte at @p address is an active left redzone.
144 : static bool IsLeftRedzone(const void* address);
145 :
146 : // @param address The address that we want to check.
147 : // @returns true if the byte at @p address is an active right redzone.
148 : static bool IsRightRedzone(const void* address);
149 :
150 : // @param address The address that we want to check.
151 : // @returns true if the byte at @p address is the start of a block.
152 : static bool IsBlockStartByte(const void* address);
153 :
154 : // Returns the ShadowMarker value for the byte at @p addr.
155 : // @param addr The address for which we want the ShadowMarker value.
156 : // @returns the ShadowMarker value for this address.
157 : static ShadowMarker GetShadowMarkerForAddress(const void* addr);
158 :
159 : // Appends a textual description of the shadow memory for @p addr to
160 : // @p output, including the values of the shadow bytes and a legend.
161 : // @param addr The address for which we want to get the textual description.
162 : // @param output The string in which we want to store this information.
163 : static void AppendShadowMemoryText(const void* addr, std::string* output);
164 :
165 : // Appends a textual description of the shadow memory for @p addr to
166 : // @p output. This only appends the values of the shadow bytes.
167 : // @param addr The address whose shadow memory is to be described.
168 : // @param output The string to be populated with the shadow memory
169 : // information.
170 : static void AppendShadowArrayText(const void* addr, std::string* output);
171 :
172 : // Returns true iff the array starting at @p addr is terminated with
173 : // sizeof(@p type) null bytes within a contiguous accessible region of memory.
174 : // When returning true the length of the null-terminated array (including the
175 : // trailings zero) will be returned via @p size. When returning false the
176 : // offset of the invalid access will be returned via @p size.
177 : // @tparam type The type of the null terminated value, this determines the
178 : // numbers of null bytes that we want to have at the end of the array.
179 : // @param addr The starting address of the array that we want to check.
180 : // @param max_size The maximum length to check (in bytes). Ignored if set to
181 : // zero.
182 : // @param size Will receive the size (in bytes) of the array terminated with
183 : // sizeof(type) bytes or the offset of the invalid access.
184 : // @returns true iff the array starting at @p addr is null terminated within a
185 : // contiguous accessible region of memory, false otherwise.
186 : template<typename type>
187 : static bool GetNullTerminatedArraySize(const void* addr,
188 : size_t max_size,
189 : size_t* size);
190 :
191 : // Clones a shadow memory range from one location to another.
192 : // @pre src_pointer mod 8 == 0.
193 : // @pre dst_pointer mod 8 == 0.
194 : // @pre size mod 8 == 0.
195 : // @param src_pointer The starting address of the range to copy.
196 : // @param dst_pointer The destination where the copy should be made.
197 : // @param size The size of the range to copy.
198 : static void CloneShadowRange(const void* src_pointer,
199 : void* dst_pointer,
200 : size_t size);
201 :
202 : // Calculate the allocation size of a block by using the shadow memory.
203 : // @param mem A pointer inside the memory block for which we want to calculate
204 : // the underlying allocation size.
205 : // @returns The underlying allocation size or 0 if it can't find a valid block
206 : // at this address.
207 : // @note This function doesn't work for nested blocks.
208 : // TODO(sebmarchand): Add support for nested blocks.
209 : static size_t GetAllocSize(const uint8* mem);
210 :
211 : // Poisons memory for an freshly allocated block.
212 : // @param info Info about the block layout.
213 : // @note The block must be readable.
214 : static void PoisonAllocatedBlock(const BlockInfo& info);
215 :
216 : // Determines if the block is nested simply by inspecting shadow memory.
217 : static bool BlockIsNested(const BlockInfo& info);
218 :
219 : // Inspects shadow memory to determine the layout of a block in memory.
220 : // Does not rely on any block content itself, strictly reading from the
221 : // shadow memory. In the case of nested blocks this will always return
222 : // the innermost containing block.
223 : // @param addr An address in the block to be inspected.
224 : // @param info The block information to be populated.
225 : // @returns true on success, false otherwise.
226 : static bool BlockInfoFromShadow(const void* addr, CompactBlockInfo* info);
227 : static bool BlockInfoFromShadow(const void* addr, BlockInfo* info);
228 :
229 : // Inspects shadow memory to find the block containing a nested block.
230 : // @param nested Information about the nested block.
231 : // @param info The block information to be populated.
232 : // @returns true on success, false otherwise.
233 : static bool ParentBlockInfoFromShadow(
234 : const BlockInfo& nested, BlockInfo* info);
235 :
236 : // Checks if the address @p addr corresponds to the beginning of a block's
237 : // body, i.e. if it's preceded by a left redzone.
238 : // @param addr The address that we want to check.
239 : // @returns true if the address corresponds to the beginning of a block's
240 : // body, false otherwise.
241 : static bool IsBeginningOfBlockBody(const void* addr);
242 :
243 : // Queries a given page's protection status.
244 : // @param addr An address in the page to be queried.
245 : // @returns true if the address containing the given page is protected,
246 : // false otherwise.
247 : // @note The read does not occur under a lock, so it is possible to get
248 : // stale data. Users must be robust for this.
249 : static bool PageIsProtected(const void* addr);
250 :
251 : // Marks a given page as being protected.
252 : // @param addr An address in the page to be protected.
253 : // @note Grabs a global shadow lock.
254 : static void MarkPageProtected(const void* addr);
255 :
256 : // Marks a given page as being unprotected.
257 : // @param addr An address in the page to be protected.
258 : // @note Grabs a global shadow lock.
259 : static void MarkPageUnprotected(const void* addr);
260 :
261 : // Marks a given range of pages as being protected.
262 : // @param addr The first page to be marked.
263 : // @param size The extent of the memory to be marked.
264 : // @note Grabs a global shadow lock.
265 : static void MarkPagesProtected(const void* addr, size_t size);
266 :
267 : // Marks a given range of pages as being unprotected.
268 : // @param addr The first page to be marked.
269 : // @param size The extent of the memory to be marked.
270 : // @note Grabs a global shadow lock.
271 : static void MarkPagesUnprotected(const void* addr, size_t size);
272 :
273 : // Read only accessor of shadow memory.
274 : // @returns a pointer to the actual shadow memory.
275 E : static const uint8* shadow() { return shadow_; }
276 :
277 : // Read only accessor of page protection bits.
278 E : static const uint8* page_bits() { return page_bits_; }
279 :
280 : // Determines if the shadow memory is clean. That is, it reflects the
281 : // state of shadow memory immediately after construction and a call to
282 : // SetUp.
283 : static bool IsClean();
284 :
285 : protected:
286 : // Reset the shadow memory.
287 : static void Reset();
288 :
289 : // Appends a line of shadow byte text for the bytes ranging from
290 : // shadow_[index] to shadow_[index + 7], prefixed by @p prefix. If the index
291 : // @p bug_index is present in this range then its value will be surrounded by
292 : // brackets.
293 : static void AppendShadowByteText(const char *prefix,
294 : uintptr_t index,
295 : std::string* output,
296 : size_t bug_index);
297 :
298 : // Scans to the left of the provided cursor, looking for the presence of a
299 : // block start marker that brackets the cursor.
300 : // @param initial_nesting_depth If zero then this will return the inner
301 : // most block containing the cursor. If 1 then this will find the start of
302 : // the block containing that block, and so on.
303 : // @param cursor The position in shadow memory from which to start the scan.
304 : // @param location Will be set to the location of the start marker, if found.
305 : // @returns true on success, false otherwise.
306 : static bool ScanLeftForBracketingBlockStart(
307 : size_t initial_nesting_depth, size_t cursor, size_t* location);
308 :
309 : // Scans to the right of the provided cursor, looking for the presence of a
310 : // block end marker that brackets the cursor.
311 : // @param initial_nesting_depth If zero then this will return the inner
312 : // most block containing the cursor. If 1 then this will find the end of
313 : // the block containing that block, and so on.
314 : // @param cursor The position in shadow memory from which to start the scan.
315 : // @param location Will be set to the location of the end marker, if found.
316 : // @returns true on success, false otherwise.
317 : static bool ScanRightForBracketingBlockEnd(
318 : size_t initial_nesting_depth, size_t cursor, size_t* location);
319 :
320 : // Inspects shadow memory to determine the layout of a block in memory.
321 : // @param initial_nesting_depth If zero then this will return the inner
322 : // most block containing the cursor. If 1 then this will find the end of
323 : // the block containing that block, and so on.
324 : // @param addr An address in the block to be inspected.
325 : // @param info The block information to be populated.
326 : // @returns true on success, false otherwise.
327 : static bool BlockInfoFromShadowImpl(
328 : size_t initial_nesting_depth, const void* addr, CompactBlockInfo* info);
329 :
330 : // The shadow memory.
331 : static uint8 shadow_[kShadowSize];
332 :
333 : // A lock under which page protection bits are modified.
334 : static base::Lock page_bits_lock_;
335 :
336 : // Data about which pages are protected. This changes relatively rarely, so
337 : // is reasonable to synchronize.
338 : static uint8 page_bits_[kPageBitsSize]; // Under page_bits_lock_.
339 : };
340 :
341 : // A helper class to walk over the blocks contained in a given memory region.
342 : // This uses only the metadata present in the shadow to identify the blocks.
343 : class ShadowWalker {
344 : public:
345 : // Constructor.
346 : // @param recursive If true then this will recursively descend into nested
347 : // blocks. Otherwise it will only return the outermost blocks in the
348 : // provided region.
349 : // @param lower_bound The lower bound of the region that this walker should
350 : // cover in the actual memory.
351 : // @param upper_bound The upper bound of the region that this walker should
352 : // cover in the actual memory.
353 : ShadowWalker(bool recursive,
354 : const void* lower_bound,
355 : const void* upper_bound);
356 :
357 : // Return the next block in this memory region.
358 : // @param info The block information to be populated.
359 : // @return true if a block was found, false otherwise.
360 : bool Next(BlockInfo* info);
361 :
362 : // Reset the walker to its initial state.
363 : void Reset();
364 :
365 : // @returns the nesting depth of the last returned block. If no blocks have
366 : // been walked then this returns -1.
367 E : int nesting_depth() const { return nesting_depth_; }
368 :
369 : private:
370 : // Indicates whether or not the walker will descend recursively into nested
371 : // blocks.
372 : bool recursive_;
373 :
374 : // The bounds of the memory region for this walker.
375 : const uint8* lower_bound_;
376 : const uint8* upper_bound_;
377 :
378 : // The cursor of the shadow walker. This points to upper_bound_ when
379 : // the walk is terminated.
380 : const uint8* cursor_;
381 :
382 : // The current nesting depth. Starts at -1.
383 : int nesting_depth_;
384 :
385 : DISALLOW_COPY_AND_ASSIGN(ShadowWalker);
386 : };
387 :
388 : // Bring in the implementation of the templated functions.
389 : #include "syzygy/agent/asan/shadow_impl.h"
390 :
391 : } // namespace asan
392 : } // namespace agent
393 :
394 : #endif // SYZYGY_AGENT_ASAN_SHADOW_H_
|