diff --git a/libunwindstack/Android.bp b/libunwindstack/Android.bp
index e1957ca..ca05516 100644
--- a/libunwindstack/Android.bp
+++ b/libunwindstack/Android.bp
@@ -61,6 +61,7 @@
         "Maps.cpp",
         "Memory.cpp",
         "Regs.cpp",
+        "Unwinder.cpp",
         "Symbols.cpp",
     ],
 
diff --git a/libunwindstack/DwarfSection.cpp b/libunwindstack/DwarfSection.cpp
index 1234eb1..8b30b76 100644
--- a/libunwindstack/DwarfSection.cpp
+++ b/libunwindstack/DwarfSection.cpp
@@ -47,7 +47,7 @@
   return nullptr;
 }
 
-bool DwarfSection::Step(uint64_t pc, Regs* regs, Memory* process_memory) {
+bool DwarfSection::Step(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished) {
   last_error_ = DWARF_ERROR_NONE;
   const DwarfFde* fde = GetFdeFromPc(pc);
   if (fde == nullptr || fde->cie == nullptr) {
@@ -62,7 +62,7 @@
   }
 
   // Now eval the actual registers.
-  return Eval(fde->cie, process_memory, loc_regs, regs);
+  return Eval(fde->cie, process_memory, loc_regs, regs, finished);
 }
 
 template <typename AddressType>
@@ -92,7 +92,8 @@
 
 template <typename AddressType>
 bool DwarfSectionImpl<AddressType>::Eval(const DwarfCie* cie, Memory* regular_memory,
-                                         const dwarf_loc_regs_t& loc_regs, Regs* regs) {
+                                         const dwarf_loc_regs_t& loc_regs, Regs* regs,
+                                         bool* finished) {
   RegsImpl<AddressType>* cur_regs = reinterpret_cast<RegsImpl<AddressType>*>(regs);
   if (cie->return_address_register >= cur_regs->total_regs()) {
     last_error_ = DWARF_ERROR_ILLEGAL_VALUE;
@@ -224,12 +225,14 @@
   // Find the return address location.
   if (return_address_undefined) {
     cur_regs->set_pc(0);
+    *finished = true;
   } else {
     cur_regs->set_pc((*cur_regs)[cie->return_address_register]);
+    *finished = false;
   }
   cur_regs->set_sp(cfa);
-  // Stop if the cfa and pc are the same.
-  return prev_cfa != cfa || prev_pc != cur_regs->pc();
+  // Return false if the unwind is not finished or the cfa and pc didn't change.
+  return *finished || prev_cfa != cfa || prev_pc != cur_regs->pc();
 }
 
 template <typename AddressType>
diff --git a/libunwindstack/Elf.cpp b/libunwindstack/Elf.cpp
index 4f7476d..dc6591d 100644
--- a/libunwindstack/Elf.cpp
+++ b/libunwindstack/Elf.cpp
@@ -95,11 +95,17 @@
                      gnu_debugdata_interface_->GetFunctionName(addr, name, func_offset)));
 }
 
-bool Elf::Step(uint64_t rel_pc, Regs* regs, Memory* process_memory) {
-  return valid_ && (regs->StepIfSignalHandler(rel_pc, this, process_memory) ||
-                    interface_->Step(rel_pc, regs, process_memory) ||
-                    (gnu_debugdata_interface_ &&
-                     gnu_debugdata_interface_->Step(rel_pc, regs, process_memory)));
+bool Elf::Step(uint64_t rel_pc, Regs* regs, Memory* process_memory, bool* finished) {
+  if (!valid_) {
+    return false;
+  }
+  if (regs->StepIfSignalHandler(rel_pc, this, process_memory)) {
+    *finished = false;
+    return true;
+  }
+  return interface_->Step(rel_pc, regs, process_memory, finished) ||
+         (gnu_debugdata_interface_ &&
+          gnu_debugdata_interface_->Step(rel_pc, regs, process_memory, finished));
 }
 
 uint64_t Elf::GetLoadBias() {
diff --git a/libunwindstack/ElfInterface.cpp b/libunwindstack/ElfInterface.cpp
index be4f88a..46a3f3f 100644
--- a/libunwindstack/ElfInterface.cpp
+++ b/libunwindstack/ElfInterface.cpp
@@ -348,7 +348,7 @@
   return false;
 }
 
-bool ElfInterface::Step(uint64_t pc, Regs* regs, Memory* process_memory) {
+bool ElfInterface::Step(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished) {
   // Need to subtract off the load_bias to get the correct pc.
   if (pc < load_bias_) {
     return false;
@@ -357,16 +357,15 @@
 
   // Try the eh_frame first.
   DwarfSection* eh_frame = eh_frame_.get();
-  if (eh_frame != nullptr && eh_frame->Step(pc, regs, process_memory)) {
+  if (eh_frame != nullptr && eh_frame->Step(pc, regs, process_memory, finished)) {
     return true;
   }
 
   // Try the debug_frame next.
   DwarfSection* debug_frame = debug_frame_.get();
-  if (debug_frame != nullptr && debug_frame->Step(pc, regs, process_memory)) {
+  if (debug_frame != nullptr && debug_frame->Step(pc, regs, process_memory, finished)) {
     return true;
   }
-
   return false;
 }
 
diff --git a/libunwindstack/ElfInterfaceArm.cpp b/libunwindstack/ElfInterfaceArm.cpp
index 66bc51f..17364d0 100644
--- a/libunwindstack/ElfInterfaceArm.cpp
+++ b/libunwindstack/ElfInterfaceArm.cpp
@@ -99,22 +99,25 @@
   return true;
 }
 
-bool ElfInterfaceArm::Step(uint64_t pc, Regs* regs, Memory* process_memory) {
+bool ElfInterfaceArm::Step(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished) {
   // Dwarf unwind information is precise about whether a pc is covered or not,
   // but arm unwind information only has ranges of pc. In order to avoid
   // incorrectly doing a bad unwind using arm unwind information for a
   // different function, always try and unwind with the dwarf information first.
-  return ElfInterface32::Step(pc, regs, process_memory) || StepExidx(pc, regs, process_memory);
+  return ElfInterface32::Step(pc, regs, process_memory, finished) ||
+         StepExidx(pc, regs, process_memory, finished);
 }
 
-bool ElfInterfaceArm::StepExidx(uint64_t pc, Regs* regs, Memory* process_memory) {
+bool ElfInterfaceArm::StepExidx(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished) {
   RegsArm* regs_arm = reinterpret_cast<RegsArm*>(regs);
   uint64_t entry_offset;
   if (!FindEntry(pc, &entry_offset)) {
     return false;
   }
+
   ArmExidx arm(regs_arm, memory_, process_memory);
   arm.set_cfa(regs_arm->sp());
+  bool return_value = false;
   if (arm.ExtractEntryData(entry_offset) && arm.Eval()) {
     // If the pc was not set, then use the LR registers for the PC.
     if (!arm.pc_set()) {
@@ -125,9 +128,15 @@
     }
     regs_arm->set_sp(arm.cfa());
     (*regs_arm)[ARM_REG_SP] = regs_arm->sp();
+    *finished = false;
+    return_value = true;
+  }
+
+  if (arm.status() == ARM_STATUS_NO_UNWIND) {
+    *finished = true;
     return true;
   }
-  return false;
+  return return_value;
 }
 
 }  // namespace unwindstack
diff --git a/libunwindstack/ElfInterfaceArm.h b/libunwindstack/ElfInterfaceArm.h
index 1f4e8cb..bfe7704 100644
--- a/libunwindstack/ElfInterfaceArm.h
+++ b/libunwindstack/ElfInterfaceArm.h
@@ -70,9 +70,9 @@
 
   bool HandleType(uint64_t offset, uint32_t type) override;
 
-  bool Step(uint64_t pc, Regs* regs, Memory* process_memory) override;
+  bool Step(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished) override;
 
-  bool StepExidx(uint64_t pc, Regs* regs, Memory* process_memory);
+  bool StepExidx(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished);
 
   uint64_t start_offset() { return start_offset_; }
 
diff --git a/libunwindstack/Regs.cpp b/libunwindstack/Regs.cpp
index 4d09c1b..8c6172e 100644
--- a/libunwindstack/Regs.cpp
+++ b/libunwindstack/Regs.cpp
@@ -91,6 +91,15 @@
   set_sp(regs_[ARM_REG_SP]);
 }
 
+bool RegsArm::SetPcFromReturnAddress(Memory*) {
+  if (pc() == regs_[ARM_REG_LR]) {
+    return false;
+  }
+
+  set_pc(regs_[ARM_REG_LR]);
+  return true;
+}
+
 RegsArm64::RegsArm64()
     : RegsImpl<uint64_t>(ARM64_REG_LAST, ARM64_REG_SP, Location(LOCATION_REGISTER, ARM64_REG_LR)) {}
 
@@ -114,6 +123,15 @@
   set_sp(regs_[ARM64_REG_SP]);
 }
 
+bool RegsArm64::SetPcFromReturnAddress(Memory*) {
+  if (pc() == regs_[ARM64_REG_LR]) {
+    return false;
+  }
+
+  set_pc(regs_[ARM64_REG_LR]);
+  return true;
+}
+
 RegsX86::RegsX86()
     : RegsImpl<uint32_t>(X86_REG_LAST, X86_REG_SP, Location(LOCATION_SP_OFFSET, -4)) {}
 
@@ -137,6 +155,17 @@
   set_sp(regs_[X86_REG_SP]);
 }
 
+bool RegsX86::SetPcFromReturnAddress(Memory* process_memory) {
+  // Attempt to get the return address from the top of the stack.
+  uint32_t new_pc;
+  if (!process_memory->Read(sp_, &new_pc, sizeof(new_pc)) || new_pc == pc()) {
+    return false;
+  }
+
+  set_pc(new_pc);
+  return true;
+}
+
 RegsX86_64::RegsX86_64()
     : RegsImpl<uint64_t>(X86_64_REG_LAST, X86_64_REG_SP, Location(LOCATION_SP_OFFSET, -8)) {}
 
@@ -161,6 +190,17 @@
   set_sp(regs_[X86_64_REG_SP]);
 }
 
+bool RegsX86_64::SetPcFromReturnAddress(Memory* process_memory) {
+  // Attempt to get the return address from the top of the stack.
+  uint64_t new_pc;
+  if (!process_memory->Read(sp_, &new_pc, sizeof(new_pc)) || new_pc == pc()) {
+    return false;
+  }
+
+  set_pc(new_pc);
+  return true;
+}
+
 static Regs* ReadArm(void* remote_data) {
   arm_user_regs* user = reinterpret_cast<arm_user_regs*>(remote_data);
 
diff --git a/libunwindstack/Unwinder.cpp b/libunwindstack/Unwinder.cpp
new file mode 100644
index 0000000..1a86e16
--- /dev/null
+++ b/libunwindstack/Unwinder.cpp
@@ -0,0 +1,145 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * 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 <elf.h>
+#include <inttypes.h>
+#include <stdint.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <android-base/stringprintf.h>
+
+#include <unwindstack/Elf.h>
+#include <unwindstack/MapInfo.h>
+#include <unwindstack/Unwinder.h>
+
+namespace unwindstack {
+
+void Unwinder::FillInFrame(MapInfo* map_info, uint64_t* rel_pc) {
+  size_t frame_num = frames_.size();
+  frames_.resize(frame_num + 1);
+  FrameData* frame = &frames_.at(frame_num);
+  frame->num = frame_num;
+  frame->pc = regs_->pc();
+  frame->sp = regs_->sp();
+  frame->rel_pc = frame->pc;
+
+  if (map_info == nullptr) {
+    return;
+  }
+
+  Elf* elf = map_info->GetElf(process_memory_, true);
+  *rel_pc = elf->GetRelPc(regs_->pc(), map_info);
+  if (frame_num != 0) {
+    // Don't adjust the first frame pc.
+    frame->rel_pc = regs_->GetAdjustedPc(*rel_pc, elf);
+
+    // Adjust the original pc.
+    frame->pc -= *rel_pc - frame->rel_pc;
+  } else {
+    frame->rel_pc = *rel_pc;
+  }
+
+  frame->map_name = map_info->name;
+  frame->map_offset = map_info->elf_offset;
+  frame->map_start = map_info->start;
+  frame->map_end = map_info->end;
+
+  if (!elf->GetFunctionName(frame->rel_pc, &frame->function_name, &frame->function_offset)) {
+    frame->function_name = "";
+    frame->function_offset = 0;
+  }
+}
+
+void Unwinder::Unwind() {
+  frames_.clear();
+
+  bool return_address_attempt = false;
+  for (; frames_.size() < max_frames_;) {
+    MapInfo* map_info = maps_->Find(regs_->pc());
+
+    uint64_t rel_pc;
+    FillInFrame(map_info, &rel_pc);
+
+    bool stepped;
+    if (map_info == nullptr) {
+      stepped = false;
+    } else {
+      bool finished;
+      stepped = map_info->elf->Step(rel_pc + map_info->elf_offset, regs_, process_memory_.get(),
+                                    &finished);
+      if (stepped && finished) {
+        break;
+      }
+    }
+    if (!stepped) {
+      if (return_address_attempt) {
+        // Remove the speculative frame.
+        frames_.pop_back();
+        break;
+      } else {
+        // Steping didn't work, try this secondary method.
+        if (!regs_->SetPcFromReturnAddress(process_memory_.get())) {
+          break;
+        }
+        return_address_attempt = true;
+      }
+    } else {
+      return_address_attempt = false;
+    }
+  }
+}
+
+std::string Unwinder::FormatFrame(size_t frame_num) {
+  if (frame_num >= frames_.size()) {
+    return "";
+  }
+  return FormatFrame(frames_[frame_num],
+                     regs_->MachineType() == EM_ARM || regs_->MachineType() == EM_386);
+}
+
+std::string Unwinder::FormatFrame(const FrameData& frame, bool bits32) {
+  std::string data;
+
+  if (bits32) {
+    data += android::base::StringPrintf("  #%02zu pc %08" PRIx64, frame.num, frame.rel_pc);
+  } else {
+    data += android::base::StringPrintf("  #%02zu pc %016" PRIx64, frame.num, frame.rel_pc);
+  }
+
+  if (frame.map_offset != 0) {
+    data += android::base::StringPrintf(" (offset 0x%" PRIx64 ")", frame.map_offset);
+  }
+
+  if (frame.map_start == frame.map_end) {
+    // No valid map associated with this frame.
+    data += "  <unknown>";
+  } else if (!frame.map_name.empty()) {
+    data += "  " + frame.map_name;
+  } else {
+    data += android::base::StringPrintf("  <anonymous:%" PRIx64 ">", frame.map_start);
+  }
+  if (!frame.function_name.empty()) {
+    data += " (" + frame.function_name;
+    if (frame.function_offset != 0) {
+      data += android::base::StringPrintf("+%" PRId64, frame.function_offset);
+    }
+    data += ')';
+  }
+  return data;
+}
+
+}  // namespace unwindstack
diff --git a/libunwindstack/include/unwindstack/DwarfSection.h b/libunwindstack/include/unwindstack/DwarfSection.h
index 26485ae..1e843c3 100644
--- a/libunwindstack/include/unwindstack/DwarfSection.h
+++ b/libunwindstack/include/unwindstack/DwarfSection.h
@@ -76,7 +76,7 @@
 
   virtual bool Init(uint64_t offset, uint64_t size) = 0;
 
-  virtual bool Eval(const DwarfCie*, Memory*, const dwarf_loc_regs_t&, Regs*) = 0;
+  virtual bool Eval(const DwarfCie*, Memory*, const dwarf_loc_regs_t&, Regs*, bool*) = 0;
 
   virtual bool GetFdeOffsetFromPc(uint64_t pc, uint64_t* fde_offset) = 0;
 
@@ -100,7 +100,7 @@
 
   virtual uint64_t AdjustPcFromFde(uint64_t pc) = 0;
 
-  bool Step(uint64_t pc, Regs* regs, Memory* process_memory);
+  bool Step(uint64_t pc, Regs* regs, Memory* process_memory, bool* finished);
 
  protected:
   DwarfMemory memory_;
@@ -119,7 +119,7 @@
   virtual ~DwarfSectionImpl() = default;
 
   bool Eval(const DwarfCie* cie, Memory* regular_memory, const dwarf_loc_regs_t& loc_regs,
-            Regs* regs) override;
+            Regs* regs, bool* finished) override;
 
   const DwarfCie* GetCie(uint64_t offset);
   bool FillInCie(DwarfCie* cie);
diff --git a/libunwindstack/include/unwindstack/Elf.h b/libunwindstack/include/unwindstack/Elf.h
index 4e7eb34..f246beb 100644
--- a/libunwindstack/include/unwindstack/Elf.h
+++ b/libunwindstack/include/unwindstack/Elf.h
@@ -50,7 +50,7 @@
 
   uint64_t GetRelPc(uint64_t pc, const MapInfo* map_info);
 
-  bool Step(uint64_t rel_pc, Regs* regs, Memory* process_memory);
+  bool Step(uint64_t rel_pc, Regs* regs, Memory* process_memory, bool* finished);
 
   ElfInterface* CreateInterfaceFromMemory(Memory* memory);
 
diff --git a/libunwindstack/include/unwindstack/ElfInterface.h b/libunwindstack/include/unwindstack/ElfInterface.h
index 142a625..4fe966f 100644
--- a/libunwindstack/include/unwindstack/ElfInterface.h
+++ b/libunwindstack/include/unwindstack/ElfInterface.h
@@ -59,7 +59,7 @@
 
   virtual bool GetFunctionName(uint64_t addr, std::string* name, uint64_t* offset) = 0;
 
-  virtual bool Step(uint64_t rel_pc, Regs* regs, Memory* process_memory);
+  virtual bool Step(uint64_t rel_pc, Regs* regs, Memory* process_memory, bool* finished);
 
   Memory* CreateGnuDebugdataMemory();
 
diff --git a/libunwindstack/include/unwindstack/Regs.h b/libunwindstack/include/unwindstack/Regs.h
index ed4d38a..385ee18 100644
--- a/libunwindstack/include/unwindstack/Regs.h
+++ b/libunwindstack/include/unwindstack/Regs.h
@@ -63,6 +63,8 @@
 
   virtual void SetFromRaw() = 0;
 
+  virtual bool SetPcFromReturnAddress(Memory* process_memory) = 0;
+
   uint16_t sp_reg() { return sp_reg_; }
   uint16_t total_regs() { return total_regs_; }
 
@@ -113,6 +115,8 @@
 
   void SetFromRaw() override;
 
+  bool SetPcFromReturnAddress(Memory* process_memory) override;
+
   bool StepIfSignalHandler(uint64_t rel_pc, Elf* elf, Memory* process_memory) override;
 };
 
@@ -127,6 +131,8 @@
 
   void SetFromRaw() override;
 
+  bool SetPcFromReturnAddress(Memory* process_memory) override;
+
   bool StepIfSignalHandler(uint64_t rel_pc, Elf* elf, Memory* process_memory) override;
 };
 
@@ -141,6 +147,8 @@
 
   void SetFromRaw() override;
 
+  bool SetPcFromReturnAddress(Memory* process_memory) override;
+
   bool StepIfSignalHandler(uint64_t rel_pc, Elf* elf, Memory* process_memory) override;
 
   void SetFromUcontext(x86_ucontext_t* ucontext);
@@ -157,6 +165,8 @@
 
   void SetFromRaw() override;
 
+  bool SetPcFromReturnAddress(Memory* process_memory) override;
+
   bool StepIfSignalHandler(uint64_t rel_pc, Elf* elf, Memory* process_memory) override;
 
   void SetFromUcontext(x86_64_ucontext_t* ucontext);
diff --git a/libunwindstack/include/unwindstack/Unwinder.h b/libunwindstack/include/unwindstack/Unwinder.h
new file mode 100644
index 0000000..d66fe55
--- /dev/null
+++ b/libunwindstack/include/unwindstack/Unwinder.h
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#ifndef _LIBUNWINDSTACK_UNWINDER_H
+#define _LIBUNWINDSTACK_UNWINDER_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include <unwindstack/Maps.h>
+#include <unwindstack/Memory.h>
+#include <unwindstack/Regs.h>
+
+namespace unwindstack {
+
+struct FrameData {
+  size_t num;
+
+  uint64_t rel_pc;
+  uint64_t pc;
+  uint64_t sp;
+
+  std::string function_name;
+  uint64_t function_offset;
+
+  std::string map_name;
+  uint64_t map_offset;
+  uint64_t map_start;
+  uint64_t map_end;
+};
+
+class Unwinder {
+ public:
+  Unwinder(size_t max_frames, Maps* maps, Regs* regs, std::shared_ptr<Memory> process_memory)
+      : max_frames_(max_frames), maps_(maps), regs_(regs), process_memory_(process_memory) {
+    frames_.reserve(max_frames);
+  }
+  ~Unwinder() = default;
+
+  void Unwind();
+
+  size_t NumFrames() { return frames_.size(); }
+
+  const std::vector<FrameData>& frames() { return frames_; }
+
+  std::string FormatFrame(size_t frame_num);
+  static std::string FormatFrame(const FrameData& frame, bool bits32);
+
+ private:
+  void FillInFrame(MapInfo* map_info, uint64_t* rel_pc);
+
+  size_t max_frames_;
+  Maps* maps_;
+  Regs* regs_;
+  std::vector<FrameData> frames_;
+  std::shared_ptr<Memory> process_memory_;
+};
+
+}  // namespace unwindstack
+
+#endif  // _LIBUNWINDSTACK_UNWINDER_H
diff --git a/libunwindstack/tests/DwarfSectionImplTest.cpp b/libunwindstack/tests/DwarfSectionImplTest.cpp
index b871539..2939126 100644
--- a/libunwindstack/tests/DwarfSectionImplTest.cpp
+++ b/libunwindstack/tests/DwarfSectionImplTest.cpp
@@ -98,7 +98,8 @@
   regs[5] = 0x20;
   regs[9] = 0x3000;
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_EXPRESSION, {0x2, 0x5000}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_MEMORY_INVALID, this->section_->last_error());
 }
 
@@ -113,7 +114,8 @@
   regs[9] = 0x3000;
   this->memory_.SetMemory(0x5000, std::vector<uint8_t>{0x96, 0x96, 0x96});
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_EXPRESSION, {0x2, 0x5000}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_ILLEGAL_STATE, this->section_->last_error());
 }
 
@@ -130,7 +132,9 @@
   TypeParam cfa_value = 0x12345;
   this->memory_.SetMemory(0x80000000, &cfa_value, sizeof(cfa_value));
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_EXPRESSION, {0x4, 0x5000}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_FALSE(finished);
   EXPECT_EQ(0x12345U, regs.sp());
   EXPECT_EQ(0x20U, regs.pc());
 }
@@ -146,7 +150,9 @@
   regs[9] = 0x3000;
   this->memory_.SetMemory(0x5000, std::vector<uint8_t>{0x0c, 0x00, 0x00, 0x00, 0x80});
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_VAL_EXPRESSION, {0x4, 0x5000}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  ASSERT_FALSE(finished);
   EXPECT_EQ(0x80000000U, regs.sp());
   EXPECT_EQ(0x20U, regs.pc());
 }
@@ -162,7 +168,8 @@
   regs[9] = 0x3000;
   this->memory_.SetMemory(0x5000, std::vector<uint8_t>{0x50, 0x96, 0x96});
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_EXPRESSION, {0x2, 0x5000}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_NOT_IMPLEMENTED, this->section_->last_error());
 }
 
@@ -171,7 +178,8 @@
   RegsFake<TypeParam> regs(10, 9);
   dwarf_loc_regs_t loc_regs;
 
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_ILLEGAL_VALUE, this->section_->last_error());
 }
 
@@ -180,7 +188,8 @@
   RegsFake<TypeParam> regs(10, 9);
   dwarf_loc_regs_t loc_regs;
 
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_CFA_NOT_DEFINED, this->section_->last_error());
 }
 
@@ -190,25 +199,26 @@
   dwarf_loc_regs_t loc_regs;
 
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {20, 0}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_ILLEGAL_VALUE, this->section_->last_error());
 
   this->section_->TestClearError();
   loc_regs.erase(CFA_REG);
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_INVALID, {0, 0}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_ILLEGAL_VALUE, this->section_->last_error());
 
   this->section_->TestClearError();
   loc_regs.erase(CFA_REG);
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_OFFSET, {0, 0}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_ILLEGAL_VALUE, this->section_->last_error());
 
   this->section_->TestClearError();
   loc_regs.erase(CFA_REG);
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_VAL_OFFSET, {0, 0}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_ILLEGAL_VALUE, this->section_->last_error());
 }
 
@@ -222,7 +232,9 @@
   regs[5] = 0x20;
   regs[9] = 0x3000;
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {9, 0}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_FALSE(finished);
   EXPECT_EQ(0x20U, regs.pc());
   EXPECT_EQ(0x2000U, regs.sp());
 }
@@ -238,7 +250,9 @@
   regs[6] = 0x4000;
   regs[9] = 0x3000;
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {6, 0}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_FALSE(finished);
   EXPECT_EQ(0x20U, regs.pc());
   EXPECT_EQ(0x4000U, regs.sp());
 }
@@ -254,7 +268,8 @@
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
   loc_regs[1] = DwarfLocation{DWARF_LOCATION_REGISTER, {3, 0}};
   loc_regs[9] = DwarfLocation{DWARF_LOCATION_REGISTER, {1, 0}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_ILLEGAL_STATE, this->section_->last_error());
 }
 
@@ -268,7 +283,8 @@
   regs[8] = 0x10;
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
   loc_regs[1] = DwarfLocation{DWARF_LOCATION_REGISTER, {10, 0}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(DWARF_ERROR_ILLEGAL_VALUE, this->section_->last_error());
 }
 
@@ -292,7 +308,9 @@
   loc_regs[1] = DwarfLocation{DWARF_LOCATION_VAL_OFFSET, {0x100, 0}};
   loc_regs[2] = DwarfLocation{DWARF_LOCATION_OFFSET, {0x50, 0}};
   loc_regs[3] = DwarfLocation{DWARF_LOCATION_UNDEFINED, {0, 0}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_FALSE(finished);
   EXPECT_EQ(0x10U, regs.pc());
   EXPECT_EQ(0x2100U, regs.sp());
   EXPECT_EQ(0x2200U, regs[1]);
@@ -315,7 +333,9 @@
   regs[8] = 0x10;
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
   loc_regs[5] = DwarfLocation{DWARF_LOCATION_UNDEFINED, {0, 0}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_TRUE(finished);
   EXPECT_EQ(0U, regs.pc());
   EXPECT_EQ(0x10U, regs.sp());
 }
@@ -330,7 +350,9 @@
   regs[5] = 0x20;
   regs[8] = 0x10;
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_FALSE(finished);
   EXPECT_EQ(0x20U, regs.pc());
   EXPECT_EQ(0x10U, regs.sp());
 }
@@ -347,7 +369,9 @@
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
   // This should not result in any errors.
   loc_regs[20] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_FALSE(finished);
   EXPECT_EQ(0x20U, regs.pc());
   EXPECT_EQ(0x10U, regs.sp());
 }
@@ -365,7 +389,9 @@
   this->memory_.SetMemory(0x80000000, &cfa_value, sizeof(cfa_value));
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
   loc_regs[5] = DwarfLocation{DWARF_LOCATION_EXPRESSION, {0x4, 0x5000}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_FALSE(finished);
   EXPECT_EQ(0x3000U, regs.sp());
   EXPECT_EQ(0x12345U, regs.pc());
 }
@@ -381,7 +407,9 @@
   this->memory_.SetMemory(0x5000, std::vector<uint8_t>{0x0c, 0x00, 0x00, 0x00, 0x80});
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
   loc_regs[5] = DwarfLocation{DWARF_LOCATION_VAL_EXPRESSION, {0x4, 0x5000}};
-  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_TRUE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
+  EXPECT_FALSE(finished);
   EXPECT_EQ(0x3000U, regs.sp());
   EXPECT_EQ(0x80000000U, regs.pc());
 }
@@ -396,7 +424,8 @@
   regs[5] = 0x100;
   regs[8] = 0x2000;
   loc_regs[CFA_REG] = DwarfLocation{DWARF_LOCATION_REGISTER, {8, 0}};
-  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs));
+  bool finished;
+  ASSERT_FALSE(this->section_->Eval(&cie, &this->memory_, loc_regs, &regs, &finished));
   EXPECT_EQ(0x2000U, regs.sp());
   EXPECT_EQ(0x100U, regs.pc());
 }
diff --git a/libunwindstack/tests/DwarfSectionTest.cpp b/libunwindstack/tests/DwarfSectionTest.cpp
index fc67063..3fcd2b6 100644
--- a/libunwindstack/tests/DwarfSectionTest.cpp
+++ b/libunwindstack/tests/DwarfSectionTest.cpp
@@ -32,7 +32,7 @@
 
   MOCK_METHOD4(Log, bool(uint8_t, uint64_t, uint64_t, const DwarfFde*));
 
-  MOCK_METHOD4(Eval, bool(const DwarfCie*, Memory*, const dwarf_loc_regs_t&, Regs*));
+  MOCK_METHOD5(Eval, bool(const DwarfCie*, Memory*, const dwarf_loc_regs_t&, Regs*, bool*));
 
   MOCK_METHOD3(GetCfaLocationInfo, bool(uint64_t, const DwarfFde*, dwarf_loc_regs_t*));
 
@@ -104,7 +104,8 @@
   EXPECT_CALL(mock_section, GetFdeOffsetFromPc(0x1000, ::testing::_))
       .WillOnce(::testing::Return(false));
 
-  ASSERT_FALSE(mock_section.Step(0x1000, nullptr, nullptr));
+  bool finished;
+  ASSERT_FALSE(mock_section.Step(0x1000, nullptr, nullptr, &finished));
 }
 
 TEST_F(DwarfSectionTest, Step_fail_cie_null) {
@@ -118,7 +119,8 @@
       .WillOnce(::testing::Return(true));
   EXPECT_CALL(mock_section, GetFdeFromOffset(::testing::_)).WillOnce(::testing::Return(&fde));
 
-  ASSERT_FALSE(mock_section.Step(0x1000, nullptr, nullptr));
+  bool finished;
+  ASSERT_FALSE(mock_section.Step(0x1000, nullptr, nullptr, &finished));
 }
 
 TEST_F(DwarfSectionTest, Step_fail_cfa_location) {
@@ -136,7 +138,8 @@
   EXPECT_CALL(mock_section, GetCfaLocationInfo(0x1000, &fde, ::testing::_))
       .WillOnce(::testing::Return(false));
 
-  ASSERT_FALSE(mock_section.Step(0x1000, nullptr, nullptr));
+  bool finished;
+  ASSERT_FALSE(mock_section.Step(0x1000, nullptr, nullptr, &finished));
 }
 
 TEST_F(DwarfSectionTest, Step_pass) {
@@ -155,10 +158,11 @@
       .WillOnce(::testing::Return(true));
 
   MemoryFake process;
-  EXPECT_CALL(mock_section, Eval(&cie, &process, ::testing::_, nullptr))
+  EXPECT_CALL(mock_section, Eval(&cie, &process, ::testing::_, nullptr, ::testing::_))
       .WillOnce(::testing::Return(true));
 
-  ASSERT_TRUE(mock_section.Step(0x1000, nullptr, &process));
+  bool finished;
+  ASSERT_TRUE(mock_section.Step(0x1000, nullptr, &process, &finished));
 }
 
 }  // namespace unwindstack
diff --git a/libunwindstack/tests/ElfInterfaceArmTest.cpp b/libunwindstack/tests/ElfInterfaceArmTest.cpp
index c7ef4a1..4df7e1c 100644
--- a/libunwindstack/tests/ElfInterfaceArmTest.cpp
+++ b/libunwindstack/tests/ElfInterfaceArmTest.cpp
@@ -322,7 +322,8 @@
   ElfInterfaceArm interface(&memory_);
 
   // FindEntry fails.
-  ASSERT_FALSE(interface.StepExidx(0x7000, nullptr, nullptr));
+  bool finished;
+  ASSERT_FALSE(interface.StepExidx(0x7000, nullptr, nullptr, &finished));
 
   // ExtractEntry should fail.
   interface.set_start_offset(0x1000);
@@ -335,15 +336,16 @@
   regs[ARM_REG_LR] = 0x20000;
   regs.set_sp(regs[ARM_REG_SP]);
   regs.set_pc(0x1234);
-  ASSERT_FALSE(interface.StepExidx(0x7000, &regs, &process_memory_));
+  ASSERT_FALSE(interface.StepExidx(0x7000, &regs, &process_memory_, &finished));
 
   // Eval should fail.
   memory_.SetData32(0x1004, 0x81000000);
-  ASSERT_FALSE(interface.StepExidx(0x7000, &regs, &process_memory_));
+  ASSERT_FALSE(interface.StepExidx(0x7000, &regs, &process_memory_, &finished));
 
   // Everything should pass.
   memory_.SetData32(0x1004, 0x80b0b0b0);
-  ASSERT_TRUE(interface.StepExidx(0x7000, &regs, &process_memory_));
+  ASSERT_TRUE(interface.StepExidx(0x7000, &regs, &process_memory_, &finished));
+  ASSERT_FALSE(finished);
   ASSERT_EQ(0x1000U, regs.sp());
   ASSERT_EQ(0x1000U, regs[ARM_REG_SP]);
   ASSERT_EQ(0x20000U, regs.pc());
@@ -367,11 +369,57 @@
   regs.set_pc(0x1234);
 
   // Everything should pass.
-  ASSERT_TRUE(interface.StepExidx(0x7000, &regs, &process_memory_));
+  bool finished;
+  ASSERT_TRUE(interface.StepExidx(0x7000, &regs, &process_memory_, &finished));
+  ASSERT_FALSE(finished);
   ASSERT_EQ(0x10004U, regs.sp());
   ASSERT_EQ(0x10004U, regs[ARM_REG_SP]);
   ASSERT_EQ(0x10U, regs.pc());
   ASSERT_EQ(0x10U, regs[ARM_REG_PC]);
 }
 
+TEST_F(ElfInterfaceArmTest, StepExidx_cant_unwind) {
+  ElfInterfaceArm interface(&memory_);
+
+  interface.set_start_offset(0x1000);
+  interface.set_total_entries(1);
+  memory_.SetData32(0x1000, 0x6000);
+  memory_.SetData32(0x1004, 1);
+
+  RegsArm regs;
+  regs[ARM_REG_SP] = 0x10000;
+  regs[ARM_REG_LR] = 0x20000;
+  regs.set_sp(regs[ARM_REG_SP]);
+  regs.set_pc(0x1234);
+
+  bool finished;
+  ASSERT_TRUE(interface.StepExidx(0x7000, &regs, &process_memory_, &finished));
+  ASSERT_TRUE(finished);
+  ASSERT_EQ(0x10000U, regs.sp());
+  ASSERT_EQ(0x10000U, regs[ARM_REG_SP]);
+  ASSERT_EQ(0x1234U, regs.pc());
+}
+
+TEST_F(ElfInterfaceArmTest, StepExidx_refuse_unwind) {
+  ElfInterfaceArm interface(&memory_);
+
+  interface.set_start_offset(0x1000);
+  interface.set_total_entries(1);
+  memory_.SetData32(0x1000, 0x6000);
+  memory_.SetData32(0x1004, 0x808000b0);
+
+  RegsArm regs;
+  regs[ARM_REG_SP] = 0x10000;
+  regs[ARM_REG_LR] = 0x20000;
+  regs.set_sp(regs[ARM_REG_SP]);
+  regs.set_pc(0x1234);
+
+  bool finished;
+  ASSERT_TRUE(interface.StepExidx(0x7000, &regs, &process_memory_, &finished));
+  ASSERT_TRUE(finished);
+  ASSERT_EQ(0x10000U, regs.sp());
+  ASSERT_EQ(0x10000U, regs[ARM_REG_SP]);
+  ASSERT_EQ(0x1234U, regs.pc());
+}
+
 }  // namespace unwindstack
diff --git a/libunwindstack/tests/ElfTest.cpp b/libunwindstack/tests/ElfTest.cpp
index ed1be3b..42a0246 100644
--- a/libunwindstack/tests/ElfTest.cpp
+++ b/libunwindstack/tests/ElfTest.cpp
@@ -129,7 +129,8 @@
   uint64_t func_offset;
   ASSERT_FALSE(elf.GetFunctionName(0, &name, &func_offset));
 
-  ASSERT_FALSE(elf.Step(0, nullptr, nullptr));
+  bool finished;
+  ASSERT_FALSE(elf.Step(0, nullptr, nullptr, &finished));
 }
 
 TEST_F(ElfTest, elf32_invalid_machine) {
diff --git a/libunwindstack/tests/RegsFake.h b/libunwindstack/tests/RegsFake.h
index c76ecaa..b667ec1 100644
--- a/libunwindstack/tests/RegsFake.h
+++ b/libunwindstack/tests/RegsFake.h
@@ -35,6 +35,7 @@
 
   uint64_t GetAdjustedPc(uint64_t, Elf*) override { return 0; }
   void SetFromRaw() override {}
+  bool SetPcFromReturnAddress(Memory*) override { return false; }
   bool StepIfSignalHandler(uint64_t, Elf*, Memory*) override { return false; }
   bool GetReturnAddressFromDefault(Memory*, uint64_t*) { return false; }
 };
diff --git a/libunwindstack/tests/RegsTest.cpp b/libunwindstack/tests/RegsTest.cpp
index f549a50..3912e17 100644
--- a/libunwindstack/tests/RegsTest.cpp
+++ b/libunwindstack/tests/RegsTest.cpp
@@ -46,7 +46,7 @@
   void InitHeaders() override {}
   bool GetSoname(std::string*) override { return false; }
   bool GetFunctionName(uint64_t, std::string*, uint64_t*) override { return false; }
-  bool Step(uint64_t, Regs*, Memory*) override { return false; }
+  bool Step(uint64_t, Regs*, Memory*, bool*) override { return false; }
 };
 
 template <typename TypeParam>
@@ -62,6 +62,7 @@
 
   uint64_t GetAdjustedPc(uint64_t, Elf*) override { return 0; }
   void SetFromRaw() override {}
+  bool SetPcFromReturnAddress(Memory*) override { return false; }
   bool StepIfSignalHandler(uint64_t, Elf*, Memory*) override { return false; }
 };
 
diff --git a/libunwindstack/tests/UnwindTest.cpp b/libunwindstack/tests/UnwindTest.cpp
index a4f920a..9f9ca8b 100644
--- a/libunwindstack/tests/UnwindTest.cpp
+++ b/libunwindstack/tests/UnwindTest.cpp
@@ -31,12 +31,13 @@
 #include <thread>
 #include <vector>
 
-#include <unwindstack/Elf.h>
-#include <unwindstack/MapInfo.h>
+#include <android-base/stringprintf.h>
+
 #include <unwindstack/Maps.h>
 #include <unwindstack/Memory.h>
 #include <unwindstack/Regs.h>
 #include <unwindstack/RegsGetLocal.h>
+#include <unwindstack/Unwinder.h>
 
 #include "TestUtils.h"
 
@@ -56,11 +57,11 @@
   g_ucontext = 0;
 }
 
-static std::vector<const char*> kFunctionOrder{"InnerFunction", "MiddleFunction", "OuterFunction"};
+static std::vector<const char*> kFunctionOrder{"OuterFunction", "MiddleFunction", "InnerFunction"};
 
-static std::vector<const char*> kFunctionSignalOrder{"SignalInnerFunction", "SignalMiddleFunction",
-                                                     "SignalOuterFunction", "InnerFunction",
-                                                     "MiddleFunction",      "OuterFunction"};
+static std::vector<const char*> kFunctionSignalOrder{"OuterFunction",        "MiddleFunction",
+                                                     "InnerFunction",        "SignalOuterFunction",
+                                                     "SignalMiddleFunction", "SignalInnerFunction"};
 
 static void SignalHandler(int, siginfo_t*, void* sigcontext) {
   g_ucontext = reinterpret_cast<uintptr_t>(sigcontext);
@@ -86,62 +87,44 @@
   SignalOuterFunction();
 }
 
-static std::string ErrorMsg(const std::vector<const char*>& function_names, size_t index,
-                            std::stringstream& unwind_stream) {
+static std::string ErrorMsg(const std::vector<const char*>& function_names, Unwinder& unwinder) {
+  std::string unwind;
+  for (size_t i = 0; i < unwinder.NumFrames(); i++) {
+    unwind += unwinder.FormatFrame(i) + '\n';
+  }
+
   return std::string(
              "Unwind completed without finding all frames\n"
              "  Looking for function: ") +
-         function_names[index] + "\n" + "Unwind data:\n" + unwind_stream.str();
+         function_names.front() + "\n" + "Unwind data:\n" + unwind;
 }
 
 static void VerifyUnwind(pid_t pid, Maps* maps, Regs* regs,
-                         std::vector<const char*>& function_names) {
-  size_t function_name_index = 0;
+                         std::vector<const char*> expected_function_names) {
+  auto process_memory(Memory::CreateProcessMemory(pid));
 
-  auto process_memory = Memory::CreateProcessMemory(pid);
-  std::stringstream unwind_stream;
-  unwind_stream << std::hex;
-  for (size_t frame_num = 0; frame_num < 64; frame_num++) {
-    ASSERT_NE(0U, regs->pc()) << ErrorMsg(function_names, function_name_index, unwind_stream);
-    MapInfo* map_info = maps->Find(regs->pc());
-    ASSERT_TRUE(map_info != nullptr) << ErrorMsg(function_names, function_name_index, unwind_stream);
+  Unwinder unwinder(512, maps, regs, process_memory);
+  unwinder.Unwind();
 
-    Elf* elf = map_info->GetElf(process_memory, true);
-    uint64_t rel_pc = elf->GetRelPc(regs->pc(), map_info);
-    uint64_t adjusted_rel_pc = rel_pc;
-    if (frame_num != 0) {
-      adjusted_rel_pc = regs->GetAdjustedPc(rel_pc, elf);
-    }
-    unwind_stream << "  PC: 0x" << regs->pc() << " Rel: 0x" << adjusted_rel_pc;
-    unwind_stream << " Map: ";
-    if (!map_info->name.empty()) {
-      unwind_stream << map_info->name;
-    } else {
-      unwind_stream << " anonymous";
-    }
-    unwind_stream << "<" << map_info->start << "-" << map_info->end << ">";
-
-    std::string name;
-    uint64_t func_offset;
-    if (elf->GetFunctionName(adjusted_rel_pc, &name, &func_offset)) {
-      if (name == function_names[function_name_index]) {
-        if (++function_name_index == function_names.size()) {
-          return;
-        }
+  std::string expected_function = expected_function_names.back();
+  expected_function_names.pop_back();
+  for (auto& frame : unwinder.frames()) {
+    if (frame.function_name == expected_function) {
+      if (expected_function_names.empty()) {
+        break;
       }
-      unwind_stream << " " << name;
+      expected_function = expected_function_names.back();
+      expected_function_names.pop_back();
     }
-    unwind_stream << "\n";
-    ASSERT_TRUE(elf->Step(rel_pc + map_info->elf_offset, regs, process_memory.get()))
-        << ErrorMsg(function_names, function_name_index, unwind_stream);
   }
-  ASSERT_TRUE(false) << ErrorMsg(function_names, function_name_index, unwind_stream);
+
+  ASSERT_TRUE(expected_function_names.empty()) << ErrorMsg(expected_function_names, unwinder);
 }
 
 // This test assumes that this code is compiled with optimizations turned
 // off. If this doesn't happen, then all of the calls will be optimized
 // away.
-extern "C" void InnerFunction(bool local) {
+extern "C" void InnerFunction(bool local, bool trigger_invalid_call) {
   if (local) {
     LocalMaps maps;
     ASSERT_TRUE(maps.Parse());
@@ -152,17 +135,21 @@
   } else {
     g_ready_for_remote = true;
     g_ready = true;
+    if (trigger_invalid_call) {
+      void (*crash_func)() = nullptr;
+      crash_func();
+    }
     while (!g_finish.load()) {
     }
   }
 }
 
-extern "C" void MiddleFunction(bool local) {
-  InnerFunction(local);
+extern "C" void MiddleFunction(bool local, bool trigger_invalid_call) {
+  InnerFunction(local, trigger_invalid_call);
 }
 
-extern "C" void OuterFunction(bool local) {
-  MiddleFunction(local);
+extern "C" void OuterFunction(bool local, bool trigger_invalid_call) {
+  MiddleFunction(local, trigger_invalid_call);
 }
 
 class UnwindTest : public ::testing::Test {
@@ -171,7 +158,7 @@
 };
 
 TEST_F(UnwindTest, local) {
-  OuterFunction(true);
+  OuterFunction(true, false);
 }
 
 void WaitForRemote(pid_t pid, uint64_t addr, bool leave_attached, bool* completed) {
@@ -206,7 +193,7 @@
 TEST_F(UnwindTest, remote) {
   pid_t pid;
   if ((pid = fork()) == 0) {
-    OuterFunction(false);
+    OuterFunction(false, false);
     exit(0);
   }
   ASSERT_NE(-1, pid);
@@ -231,7 +218,7 @@
   std::atomic_int tid(0);
   std::thread thread([&]() {
     tid = syscall(__NR_gettid);
-    OuterFunction(false);
+    OuterFunction(false, false);
   });
 
   struct sigaction act, oldact;
@@ -273,25 +260,27 @@
   thread.join();
 }
 
-static void RemoteThroughSignal(unsigned int sa_flags) {
+static void RemoteThroughSignal(int signal, unsigned int sa_flags) {
   pid_t pid;
   if ((pid = fork()) == 0) {
     struct sigaction act, oldact;
     memset(&act, 0, sizeof(act));
     act.sa_sigaction = SignalCallerHandler;
     act.sa_flags = SA_RESTART | SA_ONSTACK | sa_flags;
-    ASSERT_EQ(0, sigaction(SIGUSR1, &act, &oldact));
+    ASSERT_EQ(0, sigaction(signal, &act, &oldact));
 
-    OuterFunction(false);
+    OuterFunction(false, signal == SIGSEGV);
     exit(0);
   }
   ASSERT_NE(-1, pid);
   TestScopedPidReaper reap(pid);
 
   bool completed;
-  WaitForRemote(pid, reinterpret_cast<uint64_t>(&g_ready_for_remote), false, &completed);
-  ASSERT_TRUE(completed) << "Timed out waiting for remote process to be ready.";
-  ASSERT_EQ(0, kill(pid, SIGUSR1));
+  if (signal != SIGSEGV) {
+    WaitForRemote(pid, reinterpret_cast<uint64_t>(&g_ready_for_remote), false, &completed);
+    ASSERT_TRUE(completed) << "Timed out waiting for remote process to be ready.";
+    ASSERT_EQ(0, kill(pid, SIGUSR1));
+  }
   WaitForRemote(pid, reinterpret_cast<uint64_t>(&g_signal_ready_for_remote), true, &completed);
   ASSERT_TRUE(completed) << "Timed out waiting for remote process to be in signal handler.";
 
@@ -307,11 +296,19 @@
 }
 
 TEST_F(UnwindTest, remote_through_signal) {
-  RemoteThroughSignal(0);
+  RemoteThroughSignal(SIGUSR1, 0);
 }
 
 TEST_F(UnwindTest, remote_through_signal_sa_siginfo) {
-  RemoteThroughSignal(SA_SIGINFO);
+  RemoteThroughSignal(SIGUSR1, SA_SIGINFO);
+}
+
+TEST_F(UnwindTest, remote_through_signal_with_invalid_func) {
+  RemoteThroughSignal(SIGSEGV, 0);
+}
+
+TEST_F(UnwindTest, remote_through_signal_sa_siginfo_with_invalid_func) {
+  RemoteThroughSignal(SIGSEGV, SA_SIGINFO);
 }
 
 }  // namespace unwindstack
diff --git a/libunwindstack/tools/unwind.cpp b/libunwindstack/tools/unwind.cpp
index 3614198..faac2ef 100644
--- a/libunwindstack/tools/unwind.cpp
+++ b/libunwindstack/tools/unwind.cpp
@@ -26,7 +26,11 @@
 #include <sys/types.h>
 #include <unistd.h>
 
+#include <memory>
 #include <string>
+#include <vector>
+
+#include <android-base/stringprintf.h>
 
 #include <unwindstack/Elf.h>
 #include <unwindstack/MapInfo.h>
@@ -55,6 +59,62 @@
   return ptrace(PTRACE_DETACH, pid, 0, 0) == 0;
 }
 
+std::string GetFrameInfo(size_t frame_num, unwindstack::Regs* regs,
+                         const std::shared_ptr<unwindstack::Memory>& process_memory,
+                         unwindstack::MapInfo* map_info, uint64_t* rel_pc) {
+  bool bits32;
+  switch (regs->MachineType()) {
+    case EM_ARM:
+    case EM_386:
+      bits32 = true;
+      break;
+
+    default:
+      bits32 = false;
+  }
+
+  if (map_info == nullptr) {
+    if (bits32) {
+      return android::base::StringPrintf("  #%02zu pc %08" PRIx64, frame_num, regs->pc());
+    } else {
+      return android::base::StringPrintf("  #%02zu pc %016" PRIx64, frame_num, regs->pc());
+    }
+  }
+
+  unwindstack::Elf* elf = map_info->GetElf(process_memory, true);
+  *rel_pc = elf->GetRelPc(regs->pc(), map_info);
+  uint64_t adjusted_rel_pc = *rel_pc;
+  // Don't need to adjust the first frame pc.
+  if (frame_num != 0) {
+    adjusted_rel_pc = regs->GetAdjustedPc(*rel_pc, elf);
+  }
+
+  std::string line;
+  if (bits32) {
+    line = android::base::StringPrintf("  #%02zu pc %08" PRIx64, frame_num, adjusted_rel_pc);
+  } else {
+    line = android::base::StringPrintf("  #%02zu pc %016" PRIx64, frame_num, adjusted_rel_pc);
+  }
+  if (!map_info->name.empty()) {
+    line += "  " + map_info->name;
+    if (map_info->elf_offset != 0) {
+      line += android::base::StringPrintf(" (offset 0x%" PRIx64 ")", map_info->elf_offset);
+    }
+  } else {
+    line += android::base::StringPrintf("  <anonymous:%" PRIx64 ">", map_info->offset);
+  }
+  uint64_t func_offset;
+  std::string func_name;
+  if (elf->GetFunctionName(adjusted_rel_pc, &func_name, &func_offset)) {
+    line += " (" + func_name;
+    if (func_offset != 0) {
+      line += android::base::StringPrintf("+%" PRId64, func_offset);
+    }
+    line += ')';
+  }
+  return line;
+}
+
 void DoUnwind(pid_t pid) {
   unwindstack::RemoteMaps remote_maps(pid);
   if (!remote_maps.Parse()) {
@@ -68,7 +128,6 @@
     return;
   }
 
-  bool bits32 = true;
   printf("ABI: ");
   switch (regs->MachineType()) {
     case EM_ARM:
@@ -79,11 +138,9 @@
       break;
     case EM_AARCH64:
       printf("arm64");
-      bits32 = false;
       break;
     case EM_X86_64:
       printf("x86_64");
-      bits32 = false;
       break;
     default:
       printf("unknown\n");
@@ -92,52 +149,48 @@
   printf("\n");
 
   auto process_memory = unwindstack::Memory::CreateProcessMemory(pid);
+  bool return_address_attempt = false;
+  std::vector<std::string> frames;
   for (size_t frame_num = 0; frame_num < 64; frame_num++) {
-    if (regs->pc() == 0) {
-      break;
-    }
     unwindstack::MapInfo* map_info = remote_maps.Find(regs->pc());
+    uint64_t rel_pc;
+    frames.push_back(GetFrameInfo(frame_num, regs, process_memory, map_info, &rel_pc));
+    bool stepped;
     if (map_info == nullptr) {
-      printf("Failed to find map data for the pc\n");
-      break;
-    }
-
-    unwindstack::Elf* elf = map_info->GetElf(process_memory, true);
-
-    uint64_t rel_pc = elf->GetRelPc(regs->pc(), map_info);
-    uint64_t adjusted_rel_pc = rel_pc;
-    // Don't need to adjust the first frame pc.
-    if (frame_num != 0) {
-      adjusted_rel_pc = regs->GetAdjustedPc(rel_pc, elf);
-    }
-
-    std::string name;
-    if (bits32) {
-      printf("  #%02zu pc %08" PRIx64, frame_num, adjusted_rel_pc);
+      stepped = false;
     } else {
-      printf("  #%02zu pc %016" PRIx64, frame_num, adjusted_rel_pc);
+      bool finished;
+      stepped =
+          map_info->elf->Step(rel_pc + map_info->elf_offset, regs, process_memory.get(), &finished);
+      if (stepped && finished) {
+        break;
+      }
     }
-    if (!map_info->name.empty()) {
-      printf("  %s", map_info->name.c_str());
-      if (map_info->elf_offset != 0) {
-        printf(" (offset 0x%" PRIx64 ")", map_info->elf_offset);
+    if (!stepped) {
+      if (return_address_attempt) {
+        // We tried the return address and it didn't work, remove the last
+        // two frames. If this bad frame is the only frame, only remove
+        // the last frame.
+        frames.pop_back();
+        if (frame_num != 1) {
+          frames.pop_back();
+        }
+        break;
+      } else {
+        // Steping didn't work, try this secondary method.
+        if (!regs->SetPcFromReturnAddress(process_memory.get())) {
+          break;
+        }
+        return_address_attempt = true;
       }
     } else {
-      printf("  <anonymous:%" PRIx64 ">", map_info->offset);
+      return_address_attempt = false;
     }
-    uint64_t func_offset;
-    if (elf->GetFunctionName(adjusted_rel_pc, &name, &func_offset)) {
-      printf(" (%s", name.c_str());
-      if (func_offset != 0) {
-        printf("+%" PRId64, func_offset);
-      }
-      printf(")");
-    }
-    printf("\n");
+  }
 
-    if (!elf->Step(rel_pc + map_info->elf_offset, regs, process_memory.get())) {
-      break;
-    }
+  // Print the frames.
+  for (auto& frame : frames) {
+    printf("%s\n", frame.c_str());
   }
 }