[Refinery] Introduce TypePropagatorAnalyzer - pointer types.

syzygy/refinery/analyzers/type_propagator_analyzer.cc

Index: syzygy/refinery/analyzers/type_propagator_analyzer.cc
diff --git a/syzygy/refinery/analyzers/type_propagator_analyzer.cc b/syzygy/refinery/analyzers/type_propagator_analyzer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..d3e6787ace6cf8da55996d36dd2e93f7d7de8ccc
--- /dev/null
+++ b/syzygy/refinery/analyzers/type_propagator_analyzer.cc
@@ -0,0 +1,164 @@
+// Copyright 2015 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,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "syzygy/refinery/analyzers/type_propagator_analyzer.h"
+
+#include <queue>
+
+#include "syzygy/refinery/process_state/process_state_util.h"
+#include "syzygy/refinery/process_state/refinery.pb.h"
+#include "syzygy/refinery/types/type.h"
+
+namespace refinery {
+
+// static
+const char TypePropagatorAnalyzer::kTypePropagatorAnalyzerName[] =
+    "TypePropagatorAnalyzer";
+
+TypePropagatorAnalyzer::TypePropagatorAnalyzer(
+    scoped_refptr<SymbolProvider> symbol_provider)
+    : symbol_provider_(symbol_provider) {
+  DCHECK(symbol_provider.get() != nullptr);
+}
+
+Analyzer::AnalysisResult TypePropagatorAnalyzer::Analyze(
+    const minidump::Minidump& minidump,
+    ProcessState* process_state) {
+  DCHECK(process_state != nullptr);
+
+  // Bytes and typed block layer must be present.
+  BytesLayerPtr bytes_layer;
+  if (!process_state->FindLayer(&bytes_layer)) {
+    LOG(ERROR) << "Missing bytes layer.";
+    return ANALYSIS_ERROR;
+  }
+  TypedBlockLayerPtr typed_layer;
+  if (!process_state->FindLayer(&typed_layer)) {
+    LOG(ERROR) << "Missing typed block layer.";
+    return ANALYSIS_ERROR;

[Sigurður Ásgeirsson, 2015/11/26 21:45:12]

Is this an error, or just unexpected?

[manzagop (departed), 2015/11/27 15:20:28]

I'm using this as a proxy for "StackFrameAnalyzer must have run". Although it's
possible it ran without creating the typed block layer, it's pretty unlikely. 

I clarified the comment.

+  }
+
+  ModuleLayerAccessor accessor(process_state);
+
+  std::queue<TypedData> process_queue;
+
+  // Recover typed data from the typed block layer.
+  for (TypedBlockRecordPtr rec : *typed_layer) {
+    const TypedBlock& typedblock = rec->data();
+
+    // Recover the type.
+    pe::PEFile::Signature signature;
+    if (!accessor.GetModuleSignature(typedblock.module_id(), &signature))
+      return ANALYSIS_ERROR;
+
+    scoped_refptr<TypeRepository> type_repository;
+    if (!symbol_provider_->FindOrCreateTypeRepository(signature,
+                                                      &type_repository)) {
+      return ANALYSIS_ERROR;
+    }
+
+    TypePtr type = type_repository->GetType(typedblock.type_id());
+    if (type == nullptr)
+      return ANALYSIS_ERROR;
+
+    // Queue typed data for processing.
+    process_queue.emplace(process_state, type, rec->range().start());

[Sigurður Ásgeirsson, 2015/11/26 21:45:12]

nit: I don't think we're allowed emplace just yet?

[manzagop (departed), 2015/11/27 15:20:28]

Haha. I'd actually checked and seen "Use where element construction within a
container is needed." Turns out this is just a description, and this content
appears in a "Don't use these" section.

Done.

+  }
+
+  // Process typed data looking for pointers or contained pointers.
+  while (!process_queue.empty()) {
+    if (!AnalyzeTypedData(process_queue.front(), process_state))
+      return ANALYSIS_ERROR;
+    process_queue.pop();
+  }
+
+  return ANALYSIS_COMPLETE;

[Sigurður Ásgeirsson, 2015/11/26 21:45:12]

Hmmm - I think you want to iterate here until stable?

[manzagop (departed), 2015/11/27 15:20:28]

As you guessed, there's recursion in AnalyzeTypedData.

[Sigurður Ásgeirsson, 2015/11/27 15:33:40]

That's not quite the same thing. A single iteration through this Analyzer can
unwind only one level of e.g. a linked list, or a tree.
Generally each time a new typed data is discovered, this Analyzer may
potentially propagate types from that. 

As type recovery/discovery is not limited to the stack analyzer - nor this
analyzer - the best thing to do is probably to return the "please call again"
code until no more propagation can be done?
This also implies maintaining state someplace - a simple thing to do would be to
e.g. assign an ordinal to each record in our layers, maintain the max-seen
ordinal and then iterate over only new records?

[manzagop (departed), 2015/11/27 18:17:03]

As discussed, there's currently recursion that goes beyond the first level, but
there's two issues with it:
- possibly large recursion depth
- cycles in the TypedData

Removing the recursion and adding a TODO for now.
Good idea. Also adding a TODO for this mechanism.

+}
+
+bool TypePropagatorAnalyzer::AnalyzeTypedData(const TypedData& typed_data,
+                                              ProcessState* process_state) {
+  DCHECK(process_state != nullptr);
+
+  TypePtr type = typed_data.type();
+  DCHECK(type.get());
+
+  switch (type->kind()) {
+    case Type::USER_DEFINED_TYPE_KIND:
+      return AnalyzeTypedDataUDT(typed_data, process_state);
+    case Type::POINTER_TYPE_KIND:
+      return AnalyzeTypedDataPointer(typed_data, process_state);
+    case Type::ARRAY_TYPE_KIND:
+      return AnalyzeTypedDataArray(typed_data, process_state);
+    case Type::BASIC_TYPE_KIND:
+    case Type::FUNCTION_TYPE_KIND:
+    case Type::GLOBAL_TYPE_KIND:
+    case Type::WILDCARD_TYPE_KIND:
+      // Nothing to do with these.
+      return true;
+    default:
+      DCHECK(false);
+      return false;
+  }
+}
+
+bool TypePropagatorAnalyzer::AnalyzeTypedDataUDT(const TypedData& typed_data,
+                                                 ProcessState* process_state) {
+  DCHECK_EQ(Type::USER_DEFINED_TYPE_KIND, typed_data.type()->kind());
+  DCHECK(process_state != nullptr);
+
+  // TODO(manzagop): implement.

[Sigurður Ásgeirsson, 2015/11/26 21:45:12]

aha - this is where you'd recurse?

[manzagop (departed), 2015/11/27 15:20:28]

That is correct.

+
+  return true;
+}
+
+bool TypePropagatorAnalyzer::AnalyzeTypedDataPointer(
+    const TypedData& typed_data,
+    ProcessState* process_state) {
+  DCHECK_EQ(Type::POINTER_TYPE_KIND, typed_data.type()->kind());
+  DCHECK(process_state != nullptr);
+
+  TypedData content_data;
+  typed_data.Dereference(&content_data);
+
+  if (!AddTypedBlock(content_data, process_state))
+    return false;
+
+  return AnalyzeTypedData(content_data, process_state);
+}
+
+bool TypePropagatorAnalyzer::AnalyzeTypedDataArray(
+    const TypedData& typed_data,
+    ProcessState* process_state) {
+  DCHECK_EQ(Type::ARRAY_TYPE_KIND, typed_data.type()->kind());
+  DCHECK(process_state != nullptr);
+
+  // TODO(manzagop): implement.
+  return true;
+}
+
+bool TypePropagatorAnalyzer::AddTypedBlock(const TypedData& typed_data,
+                                           ProcessState* process_state) {
+  ModuleLayerAccessor accessor(process_state);
+  pe::PEFile::Signature signature;
+  if (!typed_data.type()->repository()->GetModuleSignature(&signature))
+    return false;
+  ModuleId module_id = accessor.GetModuleId(signature);
+  if (module_id == kNoModuleId)
+    return false;
+
+  return AddTypedBlockRecord(typed_data.GetRange(), L"", module_id,
+                             typed_data.type()->type_id(), process_state);
+}
+
+}  // namespace refinery