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 a 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 : #include <vector>
72 :
73 : #include "base/basictypes.h"
74 : #include "base/logging.h"
75 : #include "base/synchronization/lock.h"
76 : #include "syzygy/agent/asan/block.h"
77 : #include "syzygy/agent/asan/constants.h"
78 : #include "syzygy/agent/asan/shadow_marker.h"
79 :
80 : namespace agent {
81 : namespace asan {
82 :
83 : // A class for managing shadow memory state.
84 : class Shadow {
85 : public:
86 : // The first 64k of the memory are not addressable.
87 : static const size_t kAddressLowerBound = 0x10000;
88 :
89 : // The number of shadow bytes to emit per line of a report.
90 : static const size_t kShadowBytesPerLine = 8;
91 :
92 : // The number of lines of shadow memory to emit before and after the
93 : // faulting address. Thus, information about
94 : //
95 : // (2 * kShadowContextLines + 1) * kShadowBytesPerLine
96 : //
97 : // shadow bytes will be reported in all.
98 : static const size_t kShadowContextLines = 4;
99 :
100 : // Default constructor. Creates a shadow memory of the appropriate size
101 : // depending on the addressable memory for this process.
102 : // @note The allocation may fail, in which case 'shadow()' will return
103 : // nullptr. If this is true the object should not be used.
104 : Shadow();
105 :
106 : // Shadow constructor. Allocates shadow memory internally.
107 : // @param length The length of the shadow memory in bytes. This implicitly
108 : // encodes the maximum addressable address of the shadow.
109 : // @note The allocation may fail, in which case 'shadow()' will return
110 : // nullptr. If this is true the object should not be used.
111 : explicit Shadow(size_t length);
112 :
113 : // Shadow constructor.
114 : // @param shadow The array to use for storing the shadow memory. The shadow
115 : // memory allocation *must* be kShadowRatio byte aligned.
116 : // @param length The length of the shadow memory in bytes. This implicitly
117 : // encodes the maximum addressable address of the shadow.
118 : Shadow(void* shadow, size_t length);
119 :
120 : // Destructor.
121 : virtual ~Shadow();
122 :
123 : // @returns the length of the shadow memory required for the current process.
124 : static size_t RequiredLength();
125 :
126 : // Set up the shadow memory.
127 : void SetUp();
128 :
129 : // Tear down the shadow memory.
130 : void TearDown();
131 :
132 : // Poisons @p size bytes starting at @p addr with @p shadow_val value.
133 : // @pre addr + size mod 8 == 0.
134 : // @param address The starting address.
135 : // @param size The size of the memory to poison.
136 : // @param shadow_val The poison marker value.
137 : void Poison(const void* addr, size_t size, ShadowMarker shadow_val);
138 :
139 : // Un-poisons @p size bytes starting at @p addr.
140 : // @pre addr mod 8 == 0 && size mod 8 == 0.
141 : // @param addr The starting address.
142 : // @param size The size of the memory to unpoison.
143 : void Unpoison(const void* addr, size_t size);
144 :
145 : // Mark @p size bytes starting at @p addr as freed. This will preserve
146 : // nested block headers/trailers/redzones, but mark all contents as freed.
147 : // It is expected that the states of all nested blocks have already been
148 : // marked as freed prior to possibly freeing the parent block.
149 : // @param addr The starting address.
150 : // @param size The size of the memory to mark as freed.
151 : void MarkAsFreed(const void* addr, size_t size);
152 :
153 : // Returns true iff the byte at @p addr is not poisoned.
154 : // @param addr The address that we want to check.
155 : // @returns true if this address is accessible, false otherwise.
156 : bool IsAccessible(const void* addr) const;
157 :
158 : // @param address The address that we want to check.
159 : // @returns true if the byte at @p address is an active left redzone.
160 : bool IsLeftRedzone(const void* address) const;
161 :
162 : // @param address The address that we want to check.
163 : // @returns true if the byte at @p address is an active right redzone.
164 : bool IsRightRedzone(const void* address) const;
165 :
166 : // @param address The address that we want to check.
167 : // @returns true if the byte at @p address is the start of a block.
168 : bool IsBlockStartByte(const void* address) const;
169 :
170 : // Gets the shadow memory associated with an address.
171 : // @param addr The address for which we want the ShadowMarker value.
172 : // @returns a pointer to the shadow memory corresponding to the given
173 : // address.
174 : const uint8* GetShadowMemoryForAddress(const void* addr) const;
175 :
176 : // Returns the ShadowMarker value for the byte at @p addr.
177 : // @param addr The address for which we want the ShadowMarker value.
178 : // @returns the ShadowMarker value for this address.
179 : ShadowMarker GetShadowMarkerForAddress(const void* addr) const;
180 :
181 : // Appends a textual description of the shadow memory for @p addr to
182 : // @p output, including the values of the shadow bytes and a legend.
183 : // @param addr The address for which we want to get the textual description.
184 : // @param output The string in which we want to store this information.
185 : void AppendShadowMemoryText(const void* addr, std::string* output) const;
186 :
187 : // Appends a textual description of the shadow memory for @p addr to
188 : // @p output. This only appends the values of the shadow bytes.
189 : // @param addr The address whose shadow memory is to be described.
190 : // @param output The string to be populated with the shadow memory
191 : // information.
192 : void AppendShadowArrayText(const void* addr, std::string* output) const;
193 :
194 : // Returns true iff the array starting at @p addr is terminated with
195 : // sizeof(@p type) null bytes within a contiguous accessible region of memory.
196 : // When returning true the length of the null-terminated array (including the
197 : // trailings zero) will be returned via @p size. When returning false the
198 : // offset of the invalid access will be returned via @p size.
199 : // @tparam type The type of the null terminated value, this determines the
200 : // numbers of null bytes that we want to have at the end of the array.
201 : // @param addr The starting address of the array that we want to check.
202 : // @param max_size The maximum length to check (in bytes). Ignored if set to
203 : // zero.
204 : // @param size Will receive the size (in bytes) of the array terminated with
205 : // sizeof(type) bytes or the offset of the invalid access.
206 : // @returns true iff the array starting at @p addr is null terminated within a
207 : // contiguous accessible region of memory, false otherwise.
208 : template<typename type>
209 : bool GetNullTerminatedArraySize(const void* addr,
210 : size_t max_size,
211 : size_t* size) const;
212 :
213 : // Calculate the allocation size of a block by using the shadow memory.
214 : // @param mem A pointer inside the memory block for which we want to calculate
215 : // the underlying allocation size.
216 : // @returns The underlying allocation size or 0 if it can't find a valid block
217 : // at this address.
218 : // @note This function doesn't work for nested blocks.
219 : // TODO(sebmarchand): Add support for nested blocks.
220 : size_t GetAllocSize(const uint8* mem) const;
221 :
222 : // Poisons memory for an freshly allocated block.
223 : // @param info Info about the block layout.
224 : // @note The block must be readable.
225 : void PoisonAllocatedBlock(const BlockInfo& info);
226 :
227 : // Determines if the block is nested simply by inspecting shadow memory.
228 : bool BlockIsNested(const BlockInfo& info) const;
229 :
230 : // Inspects shadow memory to determine the layout of a block in memory.
231 : // Does not rely on any block content itself, strictly reading from the
232 : // shadow memory. In the case of nested blocks this will always return
233 : // the innermost containing block.
234 : // @param addr An address in the block to be inspected.
235 : // @param info The block information to be populated.
236 : // @returns true on success, false otherwise.
237 : bool BlockInfoFromShadow(const void* addr, CompactBlockInfo* info) const;
238 : bool BlockInfoFromShadow(const void* addr, BlockInfo* info) const;
239 :
240 : // Inspects shadow memory to find the block containing a nested block.
241 : // @param nested Information about the nested block.
242 : // @param info The block information to be populated.
243 : // @returns true on success, false otherwise.
244 : bool ParentBlockInfoFromShadow(
245 : const BlockInfo& nested, BlockInfo* info) const;
246 :
247 : // Checks if the address @p addr corresponds to the beginning of a block's
248 : // body, i.e. if it's preceded by a left redzone.
249 : // @param addr The address that we want to check.
250 : // @returns true if the address corresponds to the beginning of a block's
251 : // body, false otherwise.
252 : bool IsBeginningOfBlockBody(const void* addr) const;
253 :
254 : // Queries a given page's protection status.
255 : // @param addr An address in the page to be queried.
256 : // @returns true if the address containing the given page is protected,
257 : // false otherwise.
258 : // @note The read does not occur under a lock, so it is possible to get
259 : // stale data. Users must be robust for this.
260 : bool PageIsProtected(const void* addr) const;
261 :
262 : // Marks a given page as being protected.
263 : // @param addr An address in the page to be protected.
264 : // @note Grabs a global shadow lock.
265 : void MarkPageProtected(const void* addr);
266 :
267 : // Marks a given page as being unprotected.
268 : // @param addr An address in the page to be protected.
269 : // @note Grabs a global shadow lock.
270 : void MarkPageUnprotected(const void* addr);
271 :
272 : // Marks a given range of pages as being protected.
273 : // @param addr The first page to be marked.
274 : // @param size The extent of the memory to be marked.
275 : // @note Grabs a global shadow lock.
276 : void MarkPagesProtected(const void* addr, size_t size);
277 :
278 : // Marks a given range of pages as being unprotected.
279 : // @param addr The first page to be marked.
280 : // @param size The extent of the memory to be marked.
281 : // @note Grabs a global shadow lock.
282 : void MarkPagesUnprotected(const void* addr, size_t size);
283 :
284 : // Returns the size of memory represented by the shadow.
285 E : const size_t memory_size() const { return length_ << kShadowRatioLog; }
286 :
287 : // Read only accessor of shadow memory.
288 : // @returns a pointer to the actual shadow memory.
289 E : const uint8* shadow() const { return shadow_; }
290 :
291 : // Returns the length of the shadow array.
292 E : size_t length() const { return length_; }
293 :
294 : // Read only accessor of page protection bits.
295 E : const uint8* page_bits() const { return page_bits_.data(); }
296 :
297 : // Returns the length of the page bits array.
298 : size_t const page_bits_size() const { return page_bits_.size(); }
299 :
300 : // Determines if the shadow memory is clean. That is, it reflects the
301 : // state of shadow memory immediately after construction and a call to
302 : // SetUp.
303 : // @returns true if the shadow memory is clean (as it would appear directly
304 : // after an initialization), false otherwise.
305 : bool IsClean() const;
306 :
307 : protected:
308 : // Seam for debug and testing shadow implementations. This is called for
309 : // every change made to a region of shadow memory.
310 : virtual void SetShadowMemory(
311 : const void* address, size_t length, ShadowMarker marker);
312 :
313 : // Returns the appropriately aligned (rounded as necessary) pointer and
314 : // size of the most derived class implementing Shadow.
315 : void GetPointerAndSize(void const** self, size_t* size) const;
316 :
317 : // Must be implemented by any derived classes. This returns the this pointer
318 : // and the size of the *most derived* class.
319 : virtual void GetPointerAndSizeImpl(void const** self, size_t* size) const;
320 :
321 : // Initializes this shadow object.
322 : void Init(size_t length);
323 : void Init(bool own_memory, void* shadow, size_t length);
324 :
325 : // Reset the shadow memory.
326 : void Reset();
327 :
328 : // Appends a line of shadow byte text for the bytes ranging from
329 : // shadow_[index] to shadow_[index + 7], prefixed by @p prefix. If the index
330 : // @p bug_index is present in this range then its value will be surrounded by
331 : // brackets.
332 : void AppendShadowByteText(const char *prefix,
333 : uintptr_t index,
334 : std::string* output,
335 : size_t bug_index) const;
336 :
337 : // Scans to the left of the provided cursor, looking for the presence of a
338 : // block start marker that brackets the cursor.
339 : // @param initial_nesting_depth If zero then this will return the inner
340 : // most block containing the cursor. If 1 then this will find the start of
341 : // the block containing that block, and so on.
342 : // @param cursor The position in shadow memory from which to start the scan.
343 : // @param location Will be set to the location of the start marker, if found.
344 : // @returns true on success, false otherwise.
345 : bool ScanLeftForBracketingBlockStart(
346 : size_t initial_nesting_depth, size_t cursor, size_t* location) const;
347 :
348 : // Scans to the right of the provided cursor, looking for the presence of a
349 : // block end marker that brackets the cursor.
350 : // @param initial_nesting_depth If zero then this will return the inner
351 : // most block containing the cursor. If 1 then this will find the end of
352 : // the block containing that block, and so on.
353 : // @param cursor The position in shadow memory from which to start the scan.
354 : // @param location Will be set to the location of the end marker, if found.
355 : // @returns true on success, false otherwise.
356 : bool ScanRightForBracketingBlockEnd(
357 : size_t initial_nesting_depth, size_t cursor, size_t* location) const;
358 :
359 : // Inspects shadow memory to determine the layout of a block in memory.
360 : // @param initial_nesting_depth If zero then this will return the inner
361 : // most block containing the cursor. If 1 then this will find the end of
362 : // the block containing that block, and so on.
363 : // @param addr An address in the block to be inspected.
364 : // @param info The block information to be populated.
365 : // @returns true on success, false otherwise.
366 : bool BlockInfoFromShadowImpl(
367 : size_t initial_nesting_depth,
368 : const void* addr,
369 : CompactBlockInfo* info) const;
370 :
371 : // If this is true then this shadow object owns the memory.
372 : bool own_memory_;
373 :
374 : // The actual shadow that is being referred to.
375 : uint8* shadow_;
376 :
377 : // The length of the underlying shadow.
378 : size_t length_;
379 :
380 : // A lock under which page protection bits are modified.
381 : base::Lock page_bits_lock_;
382 :
383 : // Data about which pages are protected. This changes relatively rarely, so
384 : // is reasonable to synchronize. Under page_bits_lock_.
385 : std::vector<uint8> page_bits_;
386 : };
387 :
388 : // A helper class to walk over the blocks contained in a given memory region.
389 : // This uses only the metadata present in the shadow to identify the blocks.
390 : class ShadowWalker {
391 : public:
392 : // Constructor.
393 : // @param shadow The shadow memory object to walk.
394 : // @param recursive If true then this will recursively descend into nested
395 : // blocks. Otherwise it will only return the outermost blocks in the
396 : // provided region.
397 : // @param lower_bound The lower bound of the region that this walker should
398 : // cover in the actual memory.
399 : // @param upper_bound The upper bound of the region that this walker should
400 : // cover in the actual memory.
401 : ShadowWalker(const Shadow* shadow,
402 : bool recursive,
403 : const void* lower_bound,
404 : const void* upper_bound);
405 :
406 : // Return the next block in this memory region.
407 : // @param info The block information to be populated.
408 : // @return true if a block was found, false otherwise.
409 : bool Next(BlockInfo* info);
410 :
411 : // Reset the walker to its initial state.
412 : void Reset();
413 :
414 : // @returns the nesting depth of the last returned block. If no blocks have
415 : // been walked then this returns -1.
416 E : int nesting_depth() const { return nesting_depth_; }
417 :
418 : private:
419 : // The shadow memory being walked.
420 : const Shadow* shadow_;
421 :
422 : // Indicates whether or not the walker will descend recursively into nested
423 : // blocks.
424 : bool recursive_;
425 :
426 : // The bounds of the memory region for this walker.
427 : const uint8* lower_bound_;
428 : const uint8* upper_bound_;
429 :
430 : // The current cursor of the shadow walker. This points to upper_bound_ when
431 : // the walk is terminated.
432 : const uint8* cursor_;
433 :
434 : // The shadow cursor. This is maintained simply for debugging and to ensure
435 : // that the shadow memory associated with |cursor_| makes it into the crash
436 : // report.
437 : const uint8* shadow_cursor_;
438 :
439 : // The current nesting depth. Starts at -1.
440 : int nesting_depth_;
441 :
442 : DISALLOW_COPY_AND_ASSIGN(ShadowWalker);
443 : };
444 :
445 : // The static shadow memory that is referred to by the memory interceptors.
446 : // These are provided by one of 'dummy_shadow.cc' or 'static_shadow.cc'.
447 : extern "C" {
448 : extern const size_t asan_memory_interceptors_shadow_memory_size;
449 : extern uint8_t asan_memory_interceptors_shadow_memory[];
450 : }
451 :
452 : // Bring in the implementation of the templated functions.
453 : #include "syzygy/agent/asan/shadow_impl.h"
454 :
455 : } // namespace asan
456 : } // namespace agent
457 :
458 : #endif // SYZYGY_AGENT_ASAN_SHADOW_H_
|