Author: labath
Date: Wed Oct 21 05:17:21 2015
New Revision: 250890

URL: http://llvm.org/viewvc/llvm-project?rev=250890&view=rev
Log:
[DataFormatters] Make libc++ list loop detection linear

Summary:
Loop detection code is being called before every element access. Although it 
tries to cache some
of the data by remembering the loop-free initial segment, every time it needs 
to increase this
segment, it will start from scratch. For the typical usage pattern, where one 
accesses the
elements in order, the loop detection will need to be run after every access, 
resulting in
quadratic behavior. This behavior is noticable even for the default 255 element 
limit.

In this commit, I rewrite the algorithm to be truly incremental -- it maintains 
the state of its
loop-detection runners between calls, and reuses them when it needs to check 
another segment.
This way, each part of the list is scanned only once, resulting in linear 
behavior.

Also note that I have changed the operator== of ListEntry to do the comparison 
based on the
value() function (instead of relying on ValueObjectSP equality). In my 
experiments, I kept
getting different ValueObjectSPs when going through the same element twice.

Reviewers: granata.enrico

Subscribers: lldb-commits, sivachandra

Differential Revision: http://reviews.llvm.org/D13902

Added:
    
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/
    
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
Modified:
    lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp

Modified: lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp
URL: 
http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp?rev=250890&r1=250889&r2=250890&view=diff
==============================================================================
--- lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp (original)
+++ lldb/trunk/source/Plugins/Language/CPlusPlus/LibCxxList.cpp Wed Oct 21 
05:17:21 2015
@@ -27,6 +27,81 @@ using namespace lldb;
 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 @@ namespace lldb_private {
             
         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 lldb_private {
     } // 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 @@ lldb_private::formatters::LibcxxStdListS
     // 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 @@ lldb_private::formatters::LibcxxStdListS
     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 @@ lldb_private::formatters::LibcxxStdListS
     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;

Added: 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
URL: 
http://llvm.org/viewvc/llvm-project/lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile?rev=250890&view=auto
==============================================================================
--- 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
 (added)
+++ 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/Makefile
 Wed Oct 21 05:17:21 2015
@@ -0,0 +1,7 @@
+LEVEL = ../../../../../../make
+
+CXX_SOURCES := main.cpp
+
+USE_LIBCPP := 1
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -O0

Added: 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
URL: 
http://llvm.org/viewvc/llvm-project/lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py?rev=250890&view=auto
==============================================================================
--- 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
 (added)
+++ 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/TestDataFormatterLibcxxListLoop.py
 Wed Oct 21 05:17:21 2015
@@ -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()

Added: 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
URL: 
http://llvm.org/viewvc/llvm-project/lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp?rev=250890&view=auto
==============================================================================
--- 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
 (added)
+++ 
lldb/trunk/test/functionalities/data-formatter/data-formatter-stl/libcxx/list/loop/main.cpp
 Wed Oct 21 05:17:21 2015
@@ -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.
+}


_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

Reply via email to