Committed a change to the SectionList that introduces

a cache of address ranges for child sections,
accelerating lookups.  This cache is built during
object file loading, and is then set in stone once
the object files are done loading.  (In Debug builds,
we ensure that the cache is never invalidated after
that.)

llvm-svn: 158188

7 files changed, 109 insertions, 15 deletions

diff --git a/lldb/include/lldb/Core/Section.h b/lldb/include/lldb/Core/Section.h
index fad783533f1..d3dbe1adee7 100644
--- a/lldb/include/lldb/Core/Section.h
+++ b/lldb/include/lldb/Core/Section.h
@@ -15,6 +15,7 @@
 #include "lldb/Core/Flags.h"
 #include "lldb/Core/ModuleChild.h"
 #include "lldb/Core/ConstString.h"
+#include "lldb/Core/RangeMap.h"
 #include "lldb/Core/UserID.h"
 #include "lldb/Core/VMRange.h"
 #include <limits.h>
@@ -85,9 +86,23 @@ public:
 
     size_t
     Slide (lldb::addr_t slide_amount, bool slide_children);
+    
+    // Update all section lookup caches
+    void
+    Finalize ();
 
 protected:
     collection  m_sections;
+
+    typedef RangeDataArray<uint64_t, uint64_t, collection::size_type, 1> SectionRangeCache;
+    mutable SectionRangeCache   m_range_cache;
+#ifdef LLDB_CONFIGURATION_DEBUG
+    mutable bool                m_finalized;
+#endif
+    
+    void BuildRangeCache() const;
+    
+    void InvalidateRangeCache() const;
 };
 
 
@@ -273,6 +288,13 @@ public:
     {
         m_thread_specific = b;
     }
+    
+    // Update all section lookup caches
+    void
+    Finalize ()
+    {
+        m_children.Finalize();
+    }
 
 protected:
 
diff --git a/lldb/source/Core/Section.cpp b/lldb/source/Core/Section.cpp
index 0c9f8ec398f..bdaa66be0b7 100644
--- a/lldb/source/Core/Section.cpp
+++ b/lldb/source/Core/Section.cpp
@@ -379,6 +379,9 @@ Section::SetLinkedLocation (const lldb::SectionSP &linked_section_sp, uint64_t l
 
 SectionList::SectionList () :
     m_sections()
+#ifdef LLDB_CONFIGURATION_DEBUG
+    , m_finalized(false)
+#endif
 {
 }
 
@@ -393,6 +396,7 @@ SectionList::AddSection (const lldb::SectionSP& section_sp)
     assert (section_sp.get());
     uint32_t section_index = m_sections.size();
     m_sections.push_back(section_sp);
+    InvalidateRangeCache();
     return section_index;
 }
 
@@ -432,6 +436,7 @@ SectionList::ReplaceSection (user_id_t sect_id, const lldb::SectionSP& sect_sp,
         if ((*sect_iter)->GetID() == sect_id)
         {
             *sect_iter = sect_sp;
+            InvalidateRangeCache();
             return true;
         }
         else if (depth > 0)
@@ -565,26 +570,69 @@ SectionList::FindSectionContainingFileAddress (addr_t vm_addr, uint32_t depth) c
     return sect_sp;
 }
 
+void
+SectionList::BuildRangeCache() const
+{
+    m_range_cache.Clear();
+    
+    for (collection::size_type idx = 0, last_idx = m_sections.size();
+         idx < last_idx;
+         ++idx)
+    {
+        Section *sect = m_sections[idx].get();
+        
+        addr_t linked_file_address = sect->GetLinkedFileAddress();
+        
+        if (linked_file_address != LLDB_INVALID_ADDRESS)
+            m_range_cache.Append(SectionRangeCache::Entry(linked_file_address, sect->GetByteSize(), idx));
+    }
+    
+    m_range_cache.Sort();
+    
+#ifdef LLDB_CONFIGURATION_DEBUG
+    m_finalized = true;
+#endif
+}
+
+void
+SectionList::InvalidateRangeCache() const
+{
+#ifdef LLDB_CONFIGURATION_DEBUG
+    assert(!m_finalized);
+#endif
+    m_range_cache.Clear();
+}
 
 SectionSP
 SectionList::FindSectionContainingLinkedFileAddress (addr_t vm_addr, uint32_t depth) const
 {
-    SectionSP sect_sp;
-    const_iterator sect_iter;
-    const_iterator end = m_sections.end();
-    for (sect_iter = m_sections.begin(); sect_iter != end && sect_sp.get() == NULL; ++sect_iter)
+    //if (m_range_cache.IsEmpty())
+    //    BuildRangeCache();
+#ifdef LLDB_CONFIGURATION_DEBUG
+    assert(m_finalized);
+#endif
+    
+    SectionRangeCache::Entry *entry = m_range_cache.FindEntryThatContains(vm_addr);
+    
+    if (entry)
+        return m_sections[entry->data];
+        
+    if (depth == 0)
+        return SectionSP();
+    
+    for (const_iterator si = m_sections.begin(), se = m_sections.end();
+         si != se;
+         ++si)
     {
-        Section *sect = sect_iter->get();
-        if (sect->ContainsLinkedFileAddress (vm_addr))
-        {
-            sect_sp = *sect_iter;
-        }
-        else if (depth > 0)
-        {
-            sect_sp = sect->GetChildren().FindSectionContainingLinkedFileAddress (vm_addr, depth - 1);
-        }
+        Section *sect = si->get();
+        
+        SectionSP sect_sp = sect->GetChildren().FindSectionContainingLinkedFileAddress(vm_addr, depth - 1);
+            
+        if (sect_sp)
+            return sect_sp;
     }
-    return sect_sp;
+    
+    return SectionSP();
 }
 
 bool
@@ -628,6 +676,22 @@ SectionList::Slide (addr_t slide_amount, bool slide_children)
         if ((*pos)->Slide(slide_amount, slide_children))
             ++count;
     }
+    InvalidateRangeCache();
     return count;
 }
 
+void
+SectionList::Finalize ()
+{
+    BuildRangeCache();
+    
+    for (const_iterator si = m_sections.begin(), se = m_sections.end();
+         si != se;
+         ++si)
+    {
+        Section *sect = si->get();
+        
+        sect->GetChildren().Finalize();
+    }
+}
+
diff --git a/lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp b/lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
index be9f4271d69..3db50391f33 100644
--- a/lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
+++ b/lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp
@@ -682,6 +682,8 @@ ObjectFileELF::GetSectionList()
                 section_sp->SetIsThreadSpecific (is_thread_specific);
             m_sections_ap->AddSection(section_sp);
         }
+        
+        m_sections_ap->Finalize(); // Now that we're done adding sections, finalize to build fast-lookup caches
     }
 
     return m_sections_ap.get();
diff --git a/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp b/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
index 9b9cbb68aa3..514c3966ee3 100644
--- a/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
+++ b/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
@@ -889,7 +889,7 @@ ObjectFileMachO::ParseSections ()
                                     // adjust the child section offsets for all existing children.
                                     const lldb::addr_t slide_amount = sect64_min_addr - curr_seg_min_addr;
                                     segment->Slide(slide_amount, false);
-                                    segment->GetChildren().Slide (-slide_amount, false);
+                                    segment->GetChildren().Slide(-slide_amount, false);
                                     segment->SetByteSize (curr_seg_max_addr - sect64_min_addr);
                                 }
 
diff --git a/lldb/source/Plugins/ObjectFile/PECOFF/ObjectFilePECOFF.cpp b/lldb/source/Plugins/ObjectFile/PECOFF/ObjectFilePECOFF.cpp
index f908ec0a3c8..cc37568d6a0 100644
--- a/lldb/source/Plugins/ObjectFile/PECOFF/ObjectFilePECOFF.cpp
+++ b/lldb/source/Plugins/ObjectFile/PECOFF/ObjectFilePECOFF.cpp
@@ -648,6 +648,8 @@ ObjectFilePECOFF::GetSectionList()
 
                 m_sections_ap->AddSection(section_sp);
             }
+            
+            m_sections_ap->Finalize(); // Now that we're done adding sections, finalize to build fast-lookup caches
         }
     }
     return m_sections_ap.get();
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp
index 7e69d453cfb..57a061f6127 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp
@@ -426,6 +426,8 @@ SymbolFileDWARFDebugMap::GetSymbolFileByCompUnitInfo (CompileUnitInfo *comp_unit
                         }
                     }
                 }
+                oso_objfile->GetSectionList()->Finalize(); // Now that we're done adding sections, finalize to build fast-lookup caches
+                comp_unit_info->debug_map_sections_sp->Finalize();
 #if defined(DEBUG_OSO_DMAP)
                 s << "OSO sections after:\n";
                 oso_objfile->GetSectionList()->Dump(&s, NULL, true);
diff --git a/lldb/source/Plugins/SymbolVendor/MacOSX/SymbolVendorMacOSX.cpp b/lldb/source/Plugins/SymbolVendor/MacOSX/SymbolVendorMacOSX.cpp
index 8ff2cc59544..0b42bfbbebb 100644
--- a/lldb/source/Plugins/SymbolVendor/MacOSX/SymbolVendorMacOSX.cpp
+++ b/lldb/source/Plugins/SymbolVendor/MacOSX/SymbolVendorMacOSX.cpp
@@ -78,6 +78,8 @@ ReplaceDSYMSectionsWithExecutableSections (ObjectFile *exec_objfile, ObjectFile
                     dsym_section_list->AddSection(exec_sect_sp);
             }
         }
+        
+        dsym_section_list->Finalize(); // Now that we're done adding sections, finalize to build fast-lookup caches
     }
 }