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; 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/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/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 + +#include + +typedef std::list 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. +}