This revision was automatically updated to reflect the committed changes.
Closed by commit rL250890: [DataFormatters] Make libc++ list loop detection
linear (authored by labath).
Changed prior to commit:
http://reviews.llvm.org/D13902?vs=37891&id=37981#toc
Repository:
rL LLVM
http://reviews.llvm.org/D13902
Files:
lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
Index: lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
===================================================================
--- lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
+++ lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
@@ -0,0 +1,28 @@
+// Evil hack: To simulate memory corruption, we want to fiddle with some internals of std::list.
+// Make those accessible to us.
+#define private public
+#define protected public
+
+#ifdef _LIBCPP_INLINE_VISIBILITY
+#undef _LIBCPP_INLINE_VISIBILITY
+#endif
+#define _LIBCPP_INLINE_VISIBILITY
+#include <list>
+
+#include <assert.h>
+
+typedef std::list<int> int_list;
+
+int main()
+{
+ int_list *numbers_list = new int_list{1,2,3,4,5,6,7,8,9,10};
+
+ auto *third_elem = numbers_list->__end_.__next_->__next_->__next_; // Set break point at this line.
+ assert(third_elem->__value_ == 3);
+ auto *fifth_elem = third_elem->__next_->__next_;
+ assert(fifth_elem->__value_ == 5);
+ fifth_elem->__next_ = third_elem;
+
+ // Any attempt to free the list will probably crash the program. Let's just leak it.
+ return 0; // Set second break point at this line.
+}
Index: lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
===================================================================
--- lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
+++ lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
@@ -0,0 +1,56 @@
+"""
+Test that the debugger handles loops in std::list (which can appear as a result of e.g. memory
+corruption).
+"""
+
+import os, time, re
+import unittest2
+import lldb
+from lldbtest import *
+import lldbutil
+
+class LibcxxListDataFormatterTestCase(TestBase):
+
+ mydir = TestBase.compute_mydir(__file__)
+
+ @skipIfGcc
+ @skipIfWindows # libc++ not ported to Windows yet
+ def test_with_run_command(self):
+ self.build()
+ exe = os.path.join(os.getcwd(), "a.out")
+ target = self.dbg.CreateTarget(exe)
+ self.assertTrue(target and target.IsValid(), "Target is valid")
+
+ file_spec = lldb.SBFileSpec ("main.cpp", False)
+ breakpoint1 = target.BreakpointCreateBySourceRegex('// Set break point at this line.', file_spec)
+ self.assertTrue(breakpoint1 and breakpoint1.IsValid())
+ breakpoint2 = target.BreakpointCreateBySourceRegex('// Set second break point at this line.', file_spec)
+ self.assertTrue(breakpoint2 and breakpoint2.IsValid())
+
+ # Run the program, it should stop at breakpoint 1.
+ process = target.LaunchSimple(None, None, self.get_process_working_directory())
+ lldbutil.skip_if_library_missing(self, target, lldbutil.PrintableRegex("libc\+\+"))
+ self.assertTrue(process and process.IsValid(), PROCESS_IS_VALID)
+ self.assertEquals(len(lldbutil.get_threads_stopped_at_breakpoint(process, breakpoint1)), 1)
+
+ # verify our list is displayed correctly
+ self.expect("frame variable *numbers_list", substrs=['[0] = 1', '[1] = 2', '[2] = 3', '[3] = 4', '[5] = 6'])
+
+ # Continue to breakpoint 2.
+ process.Continue()
+ self.assertTrue(process and process.IsValid(), PROCESS_IS_VALID)
+ self.assertEquals(len(lldbutil.get_threads_stopped_at_breakpoint(process, breakpoint2)), 1)
+
+ # The list is now inconsistent. However, we should be able to get the first three
+ # elements at least (and most importantly, not crash).
+ self.expect("frame variable *numbers_list", substrs=['[0] = 1', '[1] = 2', '[2] = 3'])
+
+ # Run to completion.
+ process.Continue()
+ self.assertEqual(process.GetState(), lldb.eStateExited, PROCESS_EXITED)
+
+if __name__ == '__main__':
+ import atexit
+ lldb.SBDebugger.Initialize()
+ atexit.register(lambda: lldb.SBDebugger.Terminate())
+ unittest2.main()
Index: lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
===================================================================
--- lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
+++ lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
@@ -0,0 +1,7 @@
+LEVEL = ../../../../../../make
+
+CXX_SOURCES := main.cpp
+
+USE_LIBCPP := 1
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -O0
Index: lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp
===================================================================
--- lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp
+++ lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp
@@ -27,6 +27,81 @@
using namespace lldb_private;
using namespace lldb_private::formatters;
+namespace {
+
+ class ListEntry
+ {
+ public:
+ ListEntry() = default;
+ ListEntry (ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
+ ListEntry (const ListEntry& rhs) : m_entry_sp(rhs.m_entry_sp) {}
+ ListEntry (ValueObject* entry) : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
+
+ ListEntry
+ next ()
+ {
+ if (!m_entry_sp)
+ return ListEntry();
+ return ListEntry(m_entry_sp->GetChildMemberWithName(ConstString("__next_"), true));
+ }
+
+ ListEntry
+ prev ()
+ {
+ if (!m_entry_sp)
+ return ListEntry();
+ return ListEntry(m_entry_sp->GetChildMemberWithName(ConstString("__prev_"), true));
+ }
+
+ uint64_t
+ value () const
+ {
+ if (!m_entry_sp)
+ return 0;
+ return m_entry_sp->GetValueAsUnsigned(0);
+ }
+
+ bool
+ null()
+ {
+ return (value() == 0);
+ }
+
+ explicit operator bool ()
+ {
+ return GetEntry().get() != nullptr && null() == false;
+ }
+
+ ValueObjectSP
+ GetEntry ()
+ {
+ return m_entry_sp;
+ }
+
+ void
+ SetEntry (ValueObjectSP entry)
+ {
+ m_entry_sp = entry;
+ }
+
+ bool
+ operator == (const ListEntry& rhs) const
+ {
+ return value() == rhs.value();
+ }
+
+ bool
+ operator != (const ListEntry& rhs) const
+ {
+ return !(*this == rhs);
+ }
+
+ private:
+ ValueObjectSP m_entry_sp;
+ };
+
+} // end anonymous namespace
+
namespace lldb_private {
namespace formatters {
class LibcxxStdListSyntheticFrontEnd : public SyntheticChildrenFrontEnd
@@ -53,11 +128,15 @@
private:
bool
- HasLoop(size_t);
+ HasLoop(size_t count);
size_t m_list_capping_size;
static const bool g_use_loop_detect = true;
- size_t m_loop_detected;
+
+ size_t m_loop_detected; // The number of elements that have had loop detection run over them.
+ ListEntry m_slow_runner; // Used for loop detection
+ ListEntry m_fast_runner; // Used for loop detection
+
lldb::addr_t m_node_address;
ValueObject* m_head;
ValueObject* m_tail;
@@ -68,71 +147,6 @@
} // namespace formatters
} // namespace lldb_private
-class ListEntry
-{
-public:
- ListEntry() = default;
- ListEntry (ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
- ListEntry (const ListEntry& rhs) : m_entry_sp(rhs.m_entry_sp) {}
- ListEntry (ValueObject* entry) : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
-
- ListEntry
- next ()
- {
- if (!m_entry_sp)
- return ListEntry();
- return ListEntry(m_entry_sp->GetChildMemberWithName(ConstString("__next_"), true));
- }
-
- ListEntry
- prev ()
- {
- if (!m_entry_sp)
- return ListEntry();
- return ListEntry(m_entry_sp->GetChildMemberWithName(ConstString("__prev_"), true));
- }
-
- uint64_t
- value ()
- {
- if (!m_entry_sp)
- return 0;
- return m_entry_sp->GetValueAsUnsigned(0);
- }
-
- bool
- null()
- {
- return (value() == 0);
- }
-
- explicit operator bool ()
- {
- return GetEntry().get() != nullptr && null() == false;
- }
-
- ValueObjectSP
- GetEntry ()
- {
- return m_entry_sp;
- }
-
- void
- SetEntry (ValueObjectSP entry)
- {
- m_entry_sp = entry;
- }
-
- bool
- operator == (const ListEntry& rhs) const
- {
- return (rhs.m_entry_sp.get() == m_entry_sp.get());
- }
-
-private:
- ValueObjectSP m_entry_sp;
-};
-
class ListIterator
{
public:
@@ -214,25 +228,34 @@
// don't bother checking for a loop if we won't actually need to jump nodes
if (m_count < 2)
return false;
- auto steps_left = std::min(count,m_count);
- auto steps_left_save = steps_left;
- ListEntry slow(m_head);
- ListEntry fast(m_head);
- while (steps_left-- > 0)
+
+ if (m_loop_detected == 0)
{
- slow = slow.next();
- fast = fast.next();
- if (fast.next())
- fast = fast.next().next();
- else
- fast = nullptr;
- if (!slow || !fast)
- return false;
- if (slow == fast)
- return true;
- }
- m_loop_detected = steps_left_save;
- return false;
+ // This is the first time we are being run (after the last update). Set up the loop
+ // invariant for the first element.
+ m_slow_runner = ListEntry(m_head).next();
+ m_fast_runner = m_slow_runner.next();
+ m_loop_detected = 1;
+ }
+
+ // Loop invariant:
+ // Loop detection has been run over the first m_loop_detected elements. If m_slow_runner ==
+ // m_fast_runner then the loop has been detected after m_loop_detected elements.
+ const size_t steps_to_run = std::min(count,m_count);
+ while (m_loop_detected < steps_to_run
+ && m_slow_runner
+ && m_fast_runner
+ && m_slow_runner != m_fast_runner) {
+
+ m_slow_runner = m_slow_runner.next();
+ m_fast_runner = m_fast_runner.next().next();
+ m_loop_detected++;
+ }
+ if (count <= m_loop_detected)
+ return false; // No loop in the first m_loop_detected elements.
+ if (!m_slow_runner || !m_fast_runner)
+ return false; // Reached the end of the list. Definitely no loops.
+ return m_slow_runner == m_fast_runner;
}
size_t
@@ -291,9 +314,8 @@
if (cached != m_children.end())
return cached->second;
- if (m_loop_detected <= idx)
- if (HasLoop(idx))
- return lldb::ValueObjectSP();
+ if (HasLoop(idx+1))
+ return lldb::ValueObjectSP();
ListIterator current(m_head);
ValueObjectSP current_sp(current.advance(idx));
@@ -321,7 +343,10 @@
m_head = m_tail = NULL;
m_node_address = 0;
m_count = UINT32_MAX;
- m_loop_detected = false;
+ m_loop_detected = 0;
+ m_slow_runner.SetEntry(nullptr);
+ m_fast_runner.SetEntry(nullptr);
+
Error err;
ValueObjectSP backend_addr(m_backend.AddressOf(err));
m_list_capping_size = 0;
_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
