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