Remove the is_nested bit from the BlockInfo structure.

syzygy/agent/asan/shadow.cc

 // Copyright 2012 Google Inc. All Rights Reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
@@ skipping 640 matching lines @@
   // Determine the distribution of bytes in the shadow.
   size_t left_redzone_bytes = info.TotalHeaderSize() / kShadowRatio;
   size_t body_bytes = (info.body_size + kShadowRatio - 1) / kShadowRatio;
   size_t block_bytes = info.block_size / kShadowRatio;
   size_t right_redzone_bytes = block_bytes - left_redzone_bytes - body_bytes;
 
   // Determine the marker byte for the header. This encodes the length of the
   // body of the allocation modulo the shadow ratio, so that the exact length
   // can be inferred from inspecting the shadow memory.
   uint8_t body_size_mod = info.body_size % kShadowRatio;
-  ShadowMarker header_marker = ShadowMarkerHelper::BuildBlockStart(
-      true, info.header->is_nested, body_size_mod);
+  ShadowMarker header_marker =
+      ShadowMarkerHelper::BuildBlockStart(true, body_size_mod);
 
   // Determine the marker byte for the trailer.
-  ShadowMarker trailer_marker =
-      ShadowMarkerHelper::BuildBlockEnd(true, info.header->is_nested);
+  ShadowMarker trailer_marker = ShadowMarkerHelper::BuildBlockEnd(true);
 
   // Poison the header and left padding.
   uint8_t* cursor = shadow_ + index;
   ::memset(cursor, header_marker, 1);
   ::memset(cursor + 1, kHeapLeftPaddingMarker, left_redzone_bytes - 1);
   cursor += left_redzone_bytes;
   ::memset(cursor, kHeapAddressableMarker, body_bytes);
   cursor += body_bytes;
 
   // Poison the right padding and the trailer.
   if (body_size_mod > 0)
     cursor[-1] = body_size_mod;
   ::memset(cursor, kHeapRightPaddingMarker, right_redzone_bytes - 1);
   ::memset(cursor + right_redzone_bytes - 1, trailer_marker, 1);
 
   SetShadowMemory(info.header,
                   info.TotalHeaderSize(),
                   kHeapLeftPaddingMarker);
   SetShadowMemory(info.body, info.body_size, kHeapAddressableMarker);
   SetShadowMemory(info.trailer_padding,
                   info.TotalTrailerSize(),
                   kHeapRightPaddingMarker);
 }
 
-bool Shadow::BlockIsNested(const BlockInfo& info) const {
-  uint8_t marker = GetShadowMarkerForAddress(info.header);
-  DCHECK(ShadowMarkerHelper::IsActiveBlockStart(marker));
-  return ShadowMarkerHelper::IsNestedBlockStart(marker);
-}
-
 bool Shadow::BlockInfoFromShadow(
     const void* addr, CompactBlockInfo* info) const {
   DCHECK_NE(static_cast<void*>(NULL), addr);
   DCHECK_NE(static_cast<CompactBlockInfo*>(NULL), info);
-  if (!BlockInfoFromShadowImpl(0, addr, info))
+  if (!BlockInfoFromShadowImpl(addr, info))
     return false;
   return true;
 }
 
 bool Shadow::BlockInfoFromShadow(const void* addr, BlockInfo* info) const {
   DCHECK_NE(static_cast<void*>(NULL), addr);
   DCHECK_NE(static_cast<BlockInfo*>(NULL), info);
   CompactBlockInfo compact = {};
   if (!BlockInfoFromShadow(addr, &compact))
     return false;
   ConvertBlockInfo(compact, info);
   return true;
 }
 
-bool Shadow::ParentBlockInfoFromShadow(const BlockInfo& nested,
-                                       BlockInfo* info) const {
-  DCHECK_NE(static_cast<BlockInfo*>(NULL), info);
-  if (!BlockIsNested(nested))
-    return false;
-  CompactBlockInfo compact = {};
-  if (!BlockInfoFromShadowImpl(1, nested.header, &compact))
-    return false;
-  ConvertBlockInfo(compact, info);
-  return true;
-}
-
 bool Shadow::IsBeginningOfBlockBody(const void* addr) const {
   DCHECK_NE(static_cast<void*>(NULL), addr);
   // If the block has a non-zero body size then the beginning of the body will
   // be accessible or tagged as freed.
   // If the block has an empty body then the beginning of the body will be a
   // right redzone.
   if (IsAccessible(addr) || IsRightRedzone(addr) ||
       GetShadowMarkerForAddress(addr) == kHeapFreedMarker) {
     return IsLeftRedzone(reinterpret_cast<const uint8_t*>(addr) - 1);
   }
@@ skipping 102 matching lines @@
 void Shadow::AppendShadowMemoryText(
     const void* addr, std::string* output) const {
   base::StringAppendF(output, "Shadow bytes around the buggy address:\n");
   AppendShadowArrayText(addr, output);
   base::StringAppendF(output, "Shadow byte legend (one shadow byte represents "
                               "8 application bytes):\n");
   base::StringAppendF(output, "  Addressable:           00\n");
   base::StringAppendF(output, "  Partially addressable: 01 - 07\n");
   base::StringAppendF(output, "  Block start redzone:   %02x - %02x\n",
                       kHeapBlockStartMarker0, kHeapBlockStartMarker7);
-  base::StringAppendF(output, "  Nested block start:    %02x - %02x\n",
-                      kHeapNestedBlockStartMarker0,
-                      kHeapNestedBlockStartMarker7);
   base::StringAppendF(output, "  Asan memory byte:      %02x\n",
                       kAsanMemoryMarker);
   base::StringAppendF(output, "  Invalid address:       %02x\n",
                       kInvalidAddressMarker);
   base::StringAppendF(output, "  User redzone:          %02x\n",
                       kUserRedzoneMarker);
   base::StringAppendF(output, "  Block end redzone:     %02x\n",
                       kHeapBlockEndMarker);
-  base::StringAppendF(output, "  Nested block end:      %02x\n",
-                      kHeapNestedBlockEndMarker);
   base::StringAppendF(output, "  Heap left redzone:     %02x\n",
                       kHeapLeftPaddingMarker);
   base::StringAppendF(output, "  Heap right redzone:    %02x\n",
                       kHeapRightPaddingMarker);
   base::StringAppendF(output, "  Asan reserved byte:    %02x\n",
                       kAsanReservedMarker);
   base::StringAppendF(output, "  Freed heap region:     %02x\n",
                       kHeapFreedMarker);
 }
 
 size_t Shadow::GetAllocSize(const uint8_t* mem) const {
   BlockInfo block_info = {};
   if (!Shadow::BlockInfoFromShadow(mem, &block_info))
     return 0;
   return block_info.block_size;
 }
 
-bool Shadow::ScanLeftForBracketingBlockStart(
-    size_t initial_nesting_depth, size_t cursor, size_t* location) const {
+bool Shadow::ScanLeftForBracketingBlockStart(size_t cursor,
+                                             size_t* location) const {
   DCHECK_NE(static_cast<size_t*>(NULL), location);
 
   static const size_t kLowerBound = kAddressLowerBound / kShadowRatio;
 
   size_t left = cursor;
-  int nesting_depth = static_cast<int>(initial_nesting_depth);
 
   MEMORY_BASIC_INFORMATION memory_info = {};
   SIZE_T ret =
       ::VirtualQuery(&shadow_[left], &memory_info, sizeof(memory_info));
   DCHECK_GT(ret, 0u);
   if (memory_info.State != MEM_COMMIT)
     return false;
 
-  if (ShadowMarkerHelper::IsBlockEnd(shadow_[left]))
-    --nesting_depth;
   while (true) {
     if (&shadow_[left] < static_cast<const uint8_t*>(memory_info.BaseAddress)) {
       ret = ::VirtualQuery(&shadow_[left], &memory_info, sizeof(memory_info));
       DCHECK_GT(ret, 0u);
       if (memory_info.State != MEM_COMMIT)
         return false;
     }
     if (ShadowMarkerHelper::IsBlockStart(shadow_[left])) {
-      if (nesting_depth == 0) {
-        *location = left;
-        return true;
-      }
-      // If this is not a nested block then there's no hope of finding a
-      // block containing the original cursor.
-      if (!ShadowMarkerHelper::IsNestedBlockStart(shadow_[left]))
-        return false;
-      --nesting_depth;
-    } else if (ShadowMarkerHelper::IsBlockEnd(shadow_[left])) {
-      ++nesting_depth;
-
-      // If we encounter the end of a non-nested block there's no way for
-      // a block to bracket us.
-      if (nesting_depth > 0 &&
-          !ShadowMarkerHelper::IsNestedBlockEnd(shadow_[left])) {
-        return false;
-      }
+      *location = left;
+      return true;
     }
     if (left <= kLowerBound)
       return false;
     --left;
   }
 
   NOTREACHED();
 }
 
 namespace {
@@ skipping 70 matching lines @@
       return pos;
     }
     pos += 8;
   }
 
   return pos;
 }
 
 }  // namespace
 
-bool Shadow::ScanRightForBracketingBlockEnd(
-    size_t initial_nesting_depth, size_t cursor, size_t* location) const {
+bool Shadow::ScanRightForBracketingBlockEnd(size_t cursor,
+                                            size_t* location) const {
   DCHECK_NE(static_cast<size_t*>(NULL), location);
 
   const uint8_t* shadow_end = shadow_ + length_;
   const uint8_t* pos = shadow_ + cursor;
-  int nesting_depth = static_cast<int>(initial_nesting_depth);
-  if (ShadowMarkerHelper::IsBlockStart(*pos))
-    --nesting_depth;
   while (pos < shadow_end) {
     // Skips past as many addressable and freed bytes as possible.
     pos = ScanRightForPotentialHeaderBytes(pos, shadow_end);
     if (pos == shadow_end)
       return false;
 
     // When the above loop exits early then somewhere in the next 8 bytes
     // there's non-addressable data that isn't 'freed'. Look byte by byte to
     // see what's up.
 
     if (ShadowMarkerHelper::IsBlockEnd(*pos)) {
-      if (nesting_depth == 0) {
-        *location = pos - shadow_;
-        return true;
-      }
-      if (!ShadowMarkerHelper::IsNestedBlockEnd(*pos))
-        return false;
-      --nesting_depth;
-    } else if (ShadowMarkerHelper::IsBlockStart(*pos)) {
-      ++nesting_depth;
-
-      // If we encounter the beginning of a non-nested block then there's
-      // clearly no way for any block to bracket us.
-      if (nesting_depth > 0 &&
-          !ShadowMarkerHelper::IsNestedBlockStart(*pos)) {
-        return false;
-      }
+      *location = pos - shadow_;
+      return true;
     }
     ++pos;
   }
   return false;
 }
 
 bool Shadow::BlockInfoFromShadowImpl(
-    size_t initial_nesting_depth,
     const void* addr,
     CompactBlockInfo* info) const {
   DCHECK_NE(static_cast<void*>(NULL), addr);
   DCHECK_NE(static_cast<CompactBlockInfo*>(NULL), info);
 
   // Convert the address to an offset in the shadow memory.
   size_t left = reinterpret_cast<uintptr_t>(addr) / kShadowRatio;
   size_t right = left;
 
-  if (!ScanLeftForBracketingBlockStart(initial_nesting_depth, left, &left))
+  if (!ScanLeftForBracketingBlockStart(left, &left))
     return false;
-  if (!ScanRightForBracketingBlockEnd(initial_nesting_depth, right, &right))
+  if (!ScanRightForBracketingBlockEnd(right, &right))
     return false;
   ++right;
 
   uint8_t* block = reinterpret_cast<uint8_t*>(left * kShadowRatio);
   info->header = reinterpret_cast<BlockHeader*>(block);
   info->block_size = static_cast<uint32_t>((right - left) * kShadowRatio);
 
   // Get the length of the body modulo the shadow ratio.
   size_t body_size_mod = ShadowMarkerHelper::GetBlockStartData(shadow_[left]);
-  info->is_nested = ShadowMarkerHelper::IsNestedBlockStart(shadow_[left]);
 
   // Find the beginning of the body (end of the left redzone).
   ++left;
   while (left < right && shadow_[left] == kHeapLeftPaddingMarker)
     ++left;
 
   // Find the beginning of the right redzone (end of the body).
   --right;
   while (right > left && shadow_[right - 1] == kHeapRightPaddingMarker)
     --right;
 
   // Calculate the body location and size.
   uint8_t* body = reinterpret_cast<uint8_t*>(left * kShadowRatio);
   size_t body_size = (right - left) * kShadowRatio;
   if (body_size_mod > 0) {
     DCHECK_LE(8u, body_size);
     body_size = body_size - kShadowRatio + body_size_mod;
   }
 
   // Fill out header and trailer sizes.
   info->header_size = body - block;
   info->trailer_size = info->block_size - body_size - info->header_size;
 
   return true;
 }
 
 ShadowWalker::ShadowWalker(const Shadow* shadow,
-                           bool recursive,
                            const void* lower_bound,
                            const void* upper_bound)
-    : shadow_(shadow), recursive_(recursive), lower_index_(0), upper_index_(0),
-      shadow_cursor_(nullptr), nesting_depth_(0) {
+    : shadow_(shadow),
+      lower_index_(0),
+      upper_index_(0),
+      shadow_cursor_(nullptr) {
   DCHECK_NE(static_cast<Shadow*>(nullptr), shadow);
   DCHECK_LE(Shadow::kAddressLowerBound, reinterpret_cast<size_t>(lower_bound));
 
   // Get the bounds as shadow indices, being careful to deal with overflow
   // of |upper_bound|.
   lower_index_ = reinterpret_cast<uintptr_t>(lower_bound) >> kShadowRatioLog;
   upper_index_ = reinterpret_cast<size_t>(::common::AlignUp(
       reinterpret_cast<const uint8_t*>(upper_bound), kShadowRatio));
   upper_index_--;
   upper_index_ >>= kShadowRatioLog;
   upper_index_++;
 
   DCHECK_LE(lower_index_, upper_index_);
   DCHECK_GE(shadow->length(), upper_index_ - lower_index_);
 
   Reset();
 }
 
 void ShadowWalker::Reset() {
-  nesting_depth_ = -1;
   shadow_cursor_ = shadow_->shadow() + lower_index_;
 }
 
 bool ShadowWalker::Next(BlockInfo* info) {
   DCHECK_NE(static_cast<BlockInfo*>(NULL), info);
 
   auto shadow_upper_bound = shadow_->shadow() + upper_index_;
 
   while (shadow_cursor_ < shadow_upper_bound) {
     // Skip uncommitted ranges of memory. This is possible when using a sparse
@@ skipping 26 matching lines @@
     } else {
       end_of_region = std::min(shadow_upper_bound, end_of_region);
     }
 
     // Scan this committed portion of the shadow.
     while (shadow_cursor_ < end_of_region) {
       uint8_t marker = *shadow_cursor_;
 
       // Update the nesting depth when block end markers are encountered.
       if (ShadowMarkerHelper::IsBlockEnd(marker)) {
-        DCHECK_LE(0, nesting_depth_);
-        --nesting_depth_;
         ++shadow_cursor_;
         continue;
       }
 
       // Look for a block start marker.
       if (ShadowMarkerHelper::IsBlockStart(marker)) {
-        // Update the nesting depth when block start bytes are encountered.
-        ++nesting_depth_;
+        // This can only fail if the shadow memory is malformed.
+        size_t block_index = shadow_cursor_ - shadow_->shadow();
+        void* block_address =
+            reinterpret_cast<void*>(block_index << kShadowRatioLog);
+        CHECK(shadow_->BlockInfoFromShadow(block_address, info));
 
-        // Non-nested blocks should only be encountered at depth 0.
-        bool is_nested = ShadowMarkerHelper::IsNestedBlockStart(marker);
-        DCHECK(is_nested || nesting_depth_ == 0);
+        // We skip directly to the end marker.
+        auto block_end =
+            reinterpret_cast<const uint8_t*>(info->header) + info->block_size;
+        shadow_cursor_ = shadow_->GetShadowMemoryForAddress(block_end) - 1;
 
-        // Determine if the block is to be reported.
-        if (!is_nested || recursive_) {
-          // This can only fail if the shadow memory is malformed.
-          size_t block_index = shadow_cursor_ - shadow_->shadow();
-          void* block_address = reinterpret_cast<void*>(
-              block_index << kShadowRatioLog);
-          CHECK(shadow_->BlockInfoFromShadow(block_address, info));
-
-          // In a recursive descent we have to process body contents.
-          if (recursive_) {
-            // Jump straight to the body of the nested block.
-            shadow_cursor_ = shadow_->GetShadowMemoryForAddress(
-                info->body);
-          } else {
-            // Otherwise we can skip the body of the block we just reported.
-            // We skip directly to the end marker (but not past it so that depth
-            // bookkeeping works properly).
-            auto block_end = reinterpret_cast<const uint8_t*>(info->header) +
-                info->block_size;
-            shadow_cursor_ = shadow_->GetShadowMemoryForAddress(block_end) - 1;
-          }
-
-          // A block has been found and its |info| is parsed. Return to the
-          // caller.
-          return true;
-        }
+        // A block has been found and its |info| is parsed. Return to the
+        // caller.
+        return true;
       }
 
       // Advance the shadow cursor.
       ++shadow_cursor_;
     }  // while (shadow_cursor_ < end_of_region)
   }
 
   return false;
 }
 
 }  // namespace asan
 }  // namespace agent