[Lldb-commits] [lldb] d4eca12 - [lldb/gdb-remote] Add support for the qOffsets packet

[Pavel Labath via lldb-commits]

Author: Pavel Labath
Date: 2020-02-26T10:18:58+01:00
New Revision: d4eca120ac0af2a805c19301412bf843a71c14b5

URL: 
https://github.com/llvm/llvm-project/commit/d4eca120ac0af2a805c19301412bf843a71c14b5
DIFF: 
https://github.com/llvm/llvm-project/commit/d4eca120ac0af2a805c19301412bf843a71c14b5.diff

LOG: [lldb/gdb-remote] Add support for the qOffsets packet

Summary:
This packet is necessary to make lldb work with the remote-gdb stub in
user mode qemu when running position-independent binaries. It reports
the relative position (load bias) of the loaded executable wrt. the
addresses in the file itself.

Lldb needs to know this information in order to correctly set the load
address of the executable. Normally, lldb would be able to find this out
on its own by following the breadcrumbs in the process auxiliary vector,
but we can't do this here because qemu does not support the
qXfer:auxv:read packet.

This patch does not implement full scope of the qOffsets packet (it only
supports packets with identical code, data and bss offsets), because it
is not fully clear how should the different offsets be handled and I am
not aware of a producer which would make use of this feature (qemu will
always

return the same value for code and data offsets). In fact, even gdb
ignores the offset for the bss sections, and uses the "data" offset
instead.  So, until the we need more of this packet, I think it's best
to stick to the simplest solution possible. This patch simply rejects
replies with non-uniform offsets.

Reviewers: clayborg, jasonmolenda

Subscribers: lldb-commits

Tags: #lldb

Differential Revision: https://reviews.llvm.org/D74598

Added: 
lldb/test/API/functionalities/gdb_remote_client/TestqOffsets.py
lldb/test/API/functionalities/gdb_remote_client/qOffsets.yaml

Modified: 
lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp
lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.h
lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp
lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.h
lldb/test/API/functionalities/gdb_remote_client/gdbclientutils.py
lldb/unittests/Process/gdb-remote/GDBRemoteCommunicationClientTest.cpp

Removed: 




diff  --git 
a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp 
b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp
index 018b753bebc6..67e5d59d199e 100644
--- a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp
+++ b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp
@@ -45,6 +45,13 @@ using namespace lldb_private::process_gdb_remote;
 using namespace lldb_private;
 using namespace std::chrono;
 
+llvm::raw_ostream &process_gdb_remote::operator<<(llvm::raw_ostream &os,
+  const QOffsets &offsets) {
+  return os << llvm::formatv(
+ "QOffsets({0}, [{1:@[x]}])", offsets.segments,
+ llvm::make_range(offsets.offsets.begin(), offsets.offsets.end()));
+}
+
 // GDBRemoteCommunicationClient constructor
 GDBRemoteCommunicationClient::GDBRemoteCommunicationClient()
 : GDBRemoteClientBase("gdb-remote.client", "gdb-remote.client.rx_packet"),
@@ -3531,6 +3538,46 @@ Status 
GDBRemoteCommunicationClient::SendGetTraceDataPacket(
   return error;
 }
 
+llvm::Optional GDBRemoteCommunicationClient::GetQOffsets() {
+  StringExtractorGDBRemote response;
+  if (SendPacketAndWaitForResponse(
+  "qOffsets", response, /*send_async=*/false) != PacketResult::Success)
+return llvm::None;
+  if (!response.IsNormalResponse())
+return llvm::None;
+
+  QOffsets result;
+  llvm::StringRef ref = response.GetStringRef();
+  const auto &GetOffset = [&] {
+addr_t offset;
+if (ref.consumeInteger(16, offset))
+  return false;
+result.offsets.push_back(offset);
+return true;
+  };
+
+  if (ref.consume_front("Text=")) {
+result.segments = false;
+if (!GetOffset())
+  return llvm::None;
+if (!ref.consume_front(";Data=") || !GetOffset())
+  return llvm::None;
+if (ref.empty())
+  return result;
+if (ref.consume_front(";Bss=") && GetOffset() && ref.empty())
+  return result;
+  } else if (ref.consume_front("TextSeg=")) {
+result.segments = true;
+if (!GetOffset())
+  return llvm::None;
+if (ref.empty())
+  return result;
+if (ref.consume_front(";DataSeg=") && GetOffset() && ref.empty())
+  return result;
+  }
+  return llvm::None;
+}
+
 bool GDBRemoteCommunicationClient::GetModuleInfo(
 const FileSpec &module_file_spec, const lldb_private::ArchSpec &arch_spec,
 ModuleSpec &module_spec) {

diff  --git 
a/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.h 
b/lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunication

[Lldb-commits] [PATCH] D74598: [lldb/gdb-remote] Add support for the qOffsets packet

[Pavel Labath via Phabricator via lldb-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rGd4eca120ac0a: [lldb/gdb-remote] Add support for the qOffsets 
packet (authored by labath).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74598/new/

https://reviews.llvm.org/D74598

Files:
  lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.cpp
  lldb/source/Plugins/Process/gdb-remote/GDBRemoteCommunicationClient.h
  lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp
  lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.h
  lldb/test/API/functionalities/gdb_remote_client/TestqOffsets.py
  lldb/test/API/functionalities/gdb_remote_client/gdbclientutils.py
  lldb/test/API/functionalities/gdb_remote_client/qOffsets.yaml
  lldb/unittests/Process/gdb-remote/GDBRemoteCommunicationClientTest.cpp

Index: lldb/unittests/Process/gdb-remote/GDBRemoteCommunicationClientTest.cpp
===
--- lldb/unittests/Process/gdb-remote/GDBRemoteCommunicationClientTest.cpp
+++ lldb/unittests/Process/gdb-remote/GDBRemoteCommunicationClientTest.cpp
@@ -552,3 +552,29 @@
   incorrect_custom_params2);
   ASSERT_FALSE(result4.get().Success());
 }
+
+TEST_F(GDBRemoteCommunicationClientTest, GetQOffsets) {
+  const auto &GetQOffsets = [&](llvm::StringRef response) {
+std::future> result = std::async(
+std::launch::async, [&] { return client.GetQOffsets(); });
+
+HandlePacket(server, "qOffsets", response);
+return result.get();
+  };
+  EXPECT_EQ((QOffsets{false, {0x1234, 0x1234}}),
+GetQOffsets("Text=1234;Data=1234"));
+  EXPECT_EQ((QOffsets{false, {0x1234, 0x1234, 0x1234}}),
+GetQOffsets("Text=1234;Data=1234;Bss=1234"));
+  EXPECT_EQ((QOffsets{true, {0x1234}}), GetQOffsets("TextSeg=1234"));
+  EXPECT_EQ((QOffsets{true, {0x1234, 0x2345}}),
+GetQOffsets("TextSeg=1234;DataSeg=2345"));
+
+  EXPECT_EQ(llvm::None, GetQOffsets("E05"));
+  EXPECT_EQ(llvm::None, GetQOffsets("Text=bogus"));
+  EXPECT_EQ(llvm::None, GetQOffsets("Text=1234"));
+  EXPECT_EQ(llvm::None, GetQOffsets("Text=1234;Data=1234;"));
+  EXPECT_EQ(llvm::None, GetQOffsets("Text=1234;Data=1234;Bss=1234;"));
+  EXPECT_EQ(llvm::None, GetQOffsets("TEXTSEG=1234"));
+  EXPECT_EQ(llvm::None, GetQOffsets("TextSeg=0x1234"));
+  EXPECT_EQ(llvm::None, GetQOffsets("TextSeg=12345678123456789"));
+}
Index: lldb/test/API/functionalities/gdb_remote_client/qOffsets.yaml
===
--- /dev/null
+++ lldb/test/API/functionalities/gdb_remote_client/qOffsets.yaml
@@ -0,0 +1,19 @@
+!ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:ELFDATA2LSB
+  Type:ET_EXEC
+  Machine: EM_AARCH64
+Sections:
+  - Name:.text
+Type:SHT_PROGBITS
+Flags:   [ SHF_ALLOC, SHF_EXECINSTR ]
+Address: 0x1000
+AddressAlign:0x4
+Content: "c3c3c3c3"
+  - Name:.note.ABI-tag
+Type:SHT_NOTE
+Flags:   [ SHF_ALLOC ]
+Address: 0x1004
+AddressAlign:0x4
+Content: 04001100474e550003000700
Index: lldb/test/API/functionalities/gdb_remote_client/gdbclientutils.py
===
--- lldb/test/API/functionalities/gdb_remote_client/gdbclientutils.py
+++ lldb/test/API/functionalities/gdb_remote_client/gdbclientutils.py
@@ -172,6 +172,8 @@
 return self.qHostInfo()
 if packet == "qGetWorkingDir":
 return self.qGetWorkingDir()
+if packet == "qOffsets":
+return self.qOffsets();
 if packet == "qsProcessInfo":
 return self.qsProcessInfo()
 if packet.startswith("qfProcessInfo"):
@@ -188,6 +190,9 @@
 def qGetWorkingDir(self):
 return "2f"
 
+def qOffsets(self):
+return ""
+
 def qHostInfo(self):
 return "ptrsize:8;endian:little;"
 
Index: lldb/test/API/functionalities/gdb_remote_client/TestqOffsets.py
===
--- /dev/null
+++ lldb/test/API/functionalities/gdb_remote_client/TestqOffsets.py
@@ -0,0 +1,28 @@
+import lldb
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test.decorators import *
+from gdbclientutils import *
+
+
+class TestqOffsets(GDBRemoteTestBase):
+
+class Responder(MockGDBServerResponder):
+def qOffsets(self):
+return 'Text=47;Data=47'
+
+def setUp(self):
+super(TestqOffsets, self).setUp()
+self._initial_platform = lldb.DBG.GetSelectedPlatform()
+
+def tearDown(self):
+lldb.DBG.SetSelectedPlatform(self._initial_platform)
+super(TestqOffsets, self).tearDown()
+
+def test(self):
+self.server.responder = TestqOffsets.Responder()
+target = self.createTarget("qOf

[Lldb-commits] [PATCH] D72751: [LLDB] Add DynamicLoaderWasmDYLD plugin for WebAssembly debugging

[Pavel Labath via Phabricator via lldb-commits]

labath added a comment.

> Who is the owner of this MemoryCache code I should ask for a review?

It sounds like the fix will be fairly straightforward. I think anyone on this 
thread should be able to review that.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72751/new/

https://reviews.llvm.org/D72751



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

[Lldb-commits] [PATCH] D65872: [lldb][NFC] Check in test case for testing virtual function calls in pointers and references.

[Raphael Isemann via Phabricator via lldb-commits]

teemperor abandoned this revision.
teemperor added a comment.
Herald added a subscriber: JDevlieghere.

This was fixed/tested in D73024 


Repository:
  rLLDB LLDB

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D65872/new/

https://reviews.llvm.org/D65872



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

[Lldb-commits] [PATCH] D75164: [lldb][cmake] Move remove_modue_flags macro to AddLLDB.cmake

[Raphael Isemann via Phabricator via lldb-commits]

teemperor created this revision.
teemperor added a reviewer: JDevlieghere.
Herald added subscribers: lldb-commits, mgorny.
Herald added a project: LLDB.

This is currently hidden in the Host CMakeLists but we should also use this 
macro in other parts of LLDB where we have ObjC++ sources.


Repository:
  rLLDB LLDB

https://reviews.llvm.org/D75164

Files:
  lldb/cmake/modules/AddLLDB.cmake
  lldb/source/Host/CMakeLists.txt


Index: lldb/source/Host/CMakeLists.txt
===
--- lldb/source/Host/CMakeLists.txt
+++ lldb/source/Host/CMakeLists.txt
@@ -3,20 +3,6 @@
   source_group(${group} FILES ${ARGN})
 endmacro()
 
-# Removes all module flags from the current CMAKE_CXX_FLAGS. Used for
-# the Objective-C++ code in lldb which we don't want to build with modules.
-# Reasons for this are that modules with Objective-C++ would require that
-# all LLVM/Clang modules are Objective-C++ compatible (which they are likely
-# not) and we would have rebuild a second set of modules just for the few
-# Objective-C++ files in lldb (which slows down the build process).
-macro(remove_module_flags)
-  string(REGEX REPLACE "-fmodules-cache-path=[^ ]+" "" CMAKE_CXX_FLAGS 
"${CMAKE_CXX_FLAGS}")
-  string(REGEX REPLACE "-fmodules-local-submodule-visibility" "" 
CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-  string(REGEX REPLACE "-fmodules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-  string(REGEX REPLACE "-gmodules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-  string(REGEX REPLACE "-fcxx-modules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-endmacro()
-
 add_host_subdirectory(common
   common/FileAction.cpp
   common/FileCache.cpp
Index: lldb/cmake/modules/AddLLDB.cmake
===
--- lldb/cmake/modules/AddLLDB.cmake
+++ lldb/cmake/modules/AddLLDB.cmake
@@ -336,3 +336,17 @@
 endif()
   endif()
 endfunction()
+
+# Removes all module flags from the current CMAKE_CXX_FLAGS. Used for
+# the Objective-C++ code in lldb which we don't want to build with modules.
+# Reasons for this are that modules with Objective-C++ would require that
+# all LLVM/Clang modules are Objective-C++ compatible (which they are likely
+# not) and we would have rebuild a second set of modules just for the few
+# Objective-C++ files in lldb (which slows down the build process).
+macro(remove_module_flags)
+  string(REGEX REPLACE "-fmodules-cache-path=[^ ]+" "" CMAKE_CXX_FLAGS 
"${CMAKE_CXX_FLAGS}")
+  string(REGEX REPLACE "-fmodules-local-submodule-visibility" "" 
CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
+  string(REGEX REPLACE "-fmodules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
+  string(REGEX REPLACE "-gmodules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
+  string(REGEX REPLACE "-fcxx-modules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
+endmacro()


Index: lldb/source/Host/CMakeLists.txt
===
--- lldb/source/Host/CMakeLists.txt
+++ lldb/source/Host/CMakeLists.txt
@@ -3,20 +3,6 @@
   source_group(${group} FILES ${ARGN})
 endmacro()
 
-# Removes all module flags from the current CMAKE_CXX_FLAGS. Used for
-# the Objective-C++ code in lldb which we don't want to build with modules.
-# Reasons for this are that modules with Objective-C++ would require that
-# all LLVM/Clang modules are Objective-C++ compatible (which they are likely
-# not) and we would have rebuild a second set of modules just for the few
-# Objective-C++ files in lldb (which slows down the build process).
-macro(remove_module_flags)
-  string(REGEX REPLACE "-fmodules-cache-path=[^ ]+" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-  string(REGEX REPLACE "-fmodules-local-submodule-visibility" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-  string(REGEX REPLACE "-fmodules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-  string(REGEX REPLACE "-gmodules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-  string(REGEX REPLACE "-fcxx-modules" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
-endmacro()
-
 add_host_subdirectory(common
   common/FileAction.cpp
   common/FileCache.cpp
Index: lldb/cmake/modules/AddLLDB.cmake
===
--- lldb/cmake/modules/AddLLDB.cmake
+++ lldb/cmake/modules/AddLLDB.cmake
@@ -336,3 +336,17 @@
 endif()
   endif()
 endfunction()
+
+# Removes all module flags from the current CMAKE_CXX_FLAGS. Used for
+# the Objective-C++ code in lldb which we don't want to build with modules.
+# Reasons for this are that modules with Objective-C++ would require that
+# all LLVM/Clang modules are Objective-C++ compatible (which they are likely
+# not) and we would have rebuild a second set of modules just for the few
+# Objective-C++ files in lldb (which slows down the build process).
+macro(remove_module_flags)
+  string(REGEX REPLACE "-fmodules-cache-path=[^ ]+" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}")
+  string(REGEX REPLACE "-fmodules-local-submodule-visibility" "" CMAKE_CXX_FLAGS "${CMAKE_CX

[Lldb-commits] [PATCH] D74891: [lldb] Never compile the debugserver with Clang module flags

[Raphael Isemann via Phabricator via lldb-commits]

teemperor updated this revision to Diff 246673.
teemperor added a comment.

- rebased on top of  D75164 


Repository:
  rLLDB LLDB

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74891/new/

https://reviews.llvm.org/D74891

Files:
  lldb/tools/debugserver/CMakeLists.txt


Index: lldb/tools/debugserver/CMakeLists.txt
===
--- lldb/tools/debugserver/CMakeLists.txt
+++ lldb/tools/debugserver/CMakeLists.txt
@@ -13,6 +13,11 @@
   include(debugserverConfig)
   include(AddLLDB)
 
+  # debugserver contains ObjC++ code, so let's disable Clang modules
+  # in this subdirectory to avoid building ObjC++ modules (which often
+  # doesn't properly work).
+  remove_module_flags()
+
   set(LLDB_SOURCE_DIR "${CMAKE_SOURCE_DIR}/../../")
   include_directories(${LLDB_SOURCE_DIR}/include)
 endif()


Index: lldb/tools/debugserver/CMakeLists.txt
===
--- lldb/tools/debugserver/CMakeLists.txt
+++ lldb/tools/debugserver/CMakeLists.txt
@@ -13,6 +13,11 @@
   include(debugserverConfig)
   include(AddLLDB)
 
+  # debugserver contains ObjC++ code, so let's disable Clang modules
+  # in this subdirectory to avoid building ObjC++ modules (which often
+  # doesn't properly work).
+  remove_module_flags()
+
   set(LLDB_SOURCE_DIR "${CMAKE_SOURCE_DIR}/../../")
   include_directories(${LLDB_SOURCE_DIR}/include)
 endif()
___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar updated this revision to Diff 246679.
unnar marked 5 inline comments as done.
unnar added a comment.

In D74759#1880499 , @labath wrote:

> Have you done a proper complexity analysis here? I doubt the `O(log n)` claim 
> is true in general. It would have to be at least `O(m + log n)` (m - number 
> of elements found), but it's not clear to me whether even this is true in 
> general. (However, I believe this can achieve ~~log(n) for non-degenerate 
> cases.)


I should have been more specific, searching for any interval that contains a 
point can be done in `O(log n)` but in our case where we are searching for all 
intervals that contain the point and as Jarin said we believe it takes `O(m log 
n)` (I admit I have not done a thorough analysis of the time complexity 
myself). The theoretical best you can do is indeed `O(m + log n)`.

> The implementation itself needs some work though. My incomplete list of 
> comments is:
> 
> - replace `int` with `size_t` and closed intervals with half-open ones

Done.

> - let's move the computation of the upper bound into the "Sort" function. 
> sorting is O(n log(n)), this is O(n) -- we can just hide it there.

That was my first thought but I decided to have it generated lazily instead, I 
will move it back to the sort.

> - make private functions private

Done.

> - we should avoid the business of figuring out what is the suitable "minimum" 
> value of B by ensuring we call the recursive function on non-empty intervals

Done.

> - clang-format the patch

Done.

> For testing you should add some c++ unit tests for the relevant interfaces.

Done. Do you think we should also unit test ComputeUpperBounds or just the 
interface?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759

Files:
  lldb/include/lldb/Utility/RangeMap.h
  lldb/unittests/Utility/RangeMapTest.cpp

Index: lldb/unittests/Utility/RangeMapTest.cpp
===
--- lldb/unittests/Utility/RangeMapTest.cpp
+++ lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,13 @@
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+const std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +101,37 @@
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}
Index: lldb/include/lldb/Utility/RangeMap.h
===
--- lldb/include/lldb/Utility/RangeMap.h
+++ lldb/include/lldb/Utility/RangeMap.h
@@ -592,13 +592,18 @@
 struct RangeData : public Range {
   typedef T DataType;
 
+  B upper_bound;
   DataType data;
 
-  RangeData() : Range(), data() {}
+  RangeData() : Range(), upper_bound(), data() {}
 
-  RangeData(B base, S size) : Range(base, size), data() {}
+  RangeData(B base, S size) : Range(base, size), upper_bound(), data() {}
 
-  RangeData(B base, S size, DataType d) : Range(base, size), data(d) {}
+  RangeData(B base, S size, DataType d)
+  : Range(base, size), upper_bound(), data(d) {}
+
+  RangeData(B base, S size, B ub, DataType d)
+  : Range(base, size), upper_bound(ub), data(d) 

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar added inline comments.



Comment at: lldb/include/lldb/Utility/RangeMap.h:642
+  B ComputeUpperBounds(int lo, int hi) {
+if (lo > hi) return B();
+

jarin wrote:
> Here, B() should be the min value of type B, no? Perhaps this should be 
> `std::numeric_limits::min()` instead of `B()`?
Removed and made sure not to recursively call in degenerate cases.



Comment at: lldb/include/lldb/Utility/RangeMap.h:745
+  void FindEntryIndexesThatContain(B addr, int lo, int hi,
+   std::vector &indexes) {
+if (lo > hi) return;

jarin wrote:
> Hmm, weird, I am surprised this is not `std::vector &indexes` (I realize 
> this was in the code before).
I suspect this function used to have a different implementation where it would 
return the indexes of the entries rather than the data itself similar to 
FindEntryIndexThatContains and it was not properly changed when it was updated.



Comment at: lldb/include/lldb/Utility/RangeMap.h:849
   Compare m_compare;
+  bool upper_bound_computed;
 };

jarin wrote:
> I am guessing this should have the `m_` prefix?
Removed as it is no longer needed.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759



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

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar updated this revision to Diff 246681.
unnar added a comment.

Added reference to Wikipedia article.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759

Files:
  lldb/include/lldb/Utility/RangeMap.h
  lldb/unittests/Utility/RangeMapTest.cpp

Index: lldb/unittests/Utility/RangeMapTest.cpp
===
--- lldb/unittests/Utility/RangeMapTest.cpp
+++ lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,13 @@
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+const std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +101,37 @@
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}
Index: lldb/include/lldb/Utility/RangeMap.h
===
--- lldb/include/lldb/Utility/RangeMap.h
+++ lldb/include/lldb/Utility/RangeMap.h
@@ -592,13 +592,18 @@
 struct RangeData : public Range {
   typedef T DataType;
 
+  B upper_bound;
   DataType data;
 
-  RangeData() : Range(), data() {}
+  RangeData() : Range(), upper_bound(), data() {}
 
-  RangeData(B base, S size) : Range(base, size), data() {}
+  RangeData(B base, S size) : Range(base, size), upper_bound(), data() {}
 
-  RangeData(B base, S size, DataType d) : Range(base, size), data(d) {}
+  RangeData(B base, S size, DataType d)
+  : Range(base, size), upper_bound(), data(d) {}
+
+  RangeData(B base, S size, B ub, DataType d)
+  : Range(base, size), upper_bound(ub), data(d) {}
 };
 
 template  &indexes) const {
+  uint32_t FindEntryIndexesThatContain(B addr, std::vector &indexes) {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 assert(IsSorted());
 #endif
-// Search the entries until the first entry that has a larger base address
-// than `addr`. As m_entries is sorted by their base address, all following
-// entries can't contain `addr` as their base address is already larger.
-for (const auto &entry : m_entries) {
-  if (entry.Contains(addr))
-indexes.push_back(entry.data);
-  else if (entry.GetRangeBase() > addr)
-break;
-}
+if (!m_entries.empty())
+  FindEntryIndexesThatContain(addr, 0, m_entries.size(), indexes);
+
 return indexes.size();
   }
 
@@ -806,6 +804,56 @@
 protected:
   Collection m_entries;
   Compare m_compare;
+
+private:
+  // We can treat the vector as a flattened Binary Search Tree, augmenting it
+  // with upper bounds (max of range endpoints) for every index allows us to
+  // query for range containment quicker.
+  B ComputeUpperBounds(size_t lo, size_t hi) {
+size_t mid = (lo + hi) / 2;
+auto &entry = m_entries[mid];
+
+entry.upper_bound = entry.base + entry.size;
+
+if (lo < mid)
+  entry.upper_bound =
+  std::max(entry.upper_bound, ComputeUpperBounds(lo, mid));
+
+if (mid + 1 < hi)
+  entry.upper_bound =
+  std::max(entry.upper_bound, ComputeUpperBounds(mid + 1, hi));
+
+return entry.upper_bound;
+  }
+
+  // This is based on the augmented tree implementation found at
+  // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
+  void FindEntryI

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

[Pavel Labath via Phabricator via lldb-commits]

labath added a comment.

Thanks for adding the tests. They look good. Could you split them off into a 
separate patch? I believe @teemperor wanted (and I do agree it's a good idea) 
to check them in first in order to demonstrate that this patch does not change 
the behavior (or to make it what exactly changes).




Comment at: lldb/unittests/Utility/RangeMapTest.cpp:22
 
+const std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {

returning a const value from a function is fairly useless. All it does is make 
the caller jump through some hoops if he really wants to modify it.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759



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

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar updated this revision to Diff 246716.
unnar marked 2 inline comments as done.

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759

Files:
  lldb/include/lldb/Utility/RangeMap.h

Index: lldb/include/lldb/Utility/RangeMap.h
===
--- lldb/include/lldb/Utility/RangeMap.h
+++ lldb/include/lldb/Utility/RangeMap.h
@@ -592,13 +592,18 @@
 struct RangeData : public Range {
   typedef T DataType;
 
+  B upper_bound;
   DataType data;
 
-  RangeData() : Range(), data() {}
+  RangeData() : Range(), upper_bound(), data() {}
 
-  RangeData(B base, S size) : Range(base, size), data() {}
+  RangeData(B base, S size) : Range(base, size), upper_bound(), data() {}
 
-  RangeData(B base, S size, DataType d) : Range(base, size), data(d) {}
+  RangeData(B base, S size, DataType d)
+  : Range(base, size), upper_bound(), data(d) {}
+
+  RangeData(B base, S size, B ub, DataType d)
+  : Range(base, size), upper_bound(ub), data(d) {}
 };
 
 template  &indexes) const {
+  uint32_t FindEntryIndexesThatContain(B addr, std::vector &indexes) {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 assert(IsSorted());
 #endif
-// Search the entries until the first entry that has a larger base address
-// than `addr`. As m_entries is sorted by their base address, all following
-// entries can't contain `addr` as their base address is already larger.
-for (const auto &entry : m_entries) {
-  if (entry.Contains(addr))
-indexes.push_back(entry.data);
-  else if (entry.GetRangeBase() > addr)
-break;
-}
+if (!m_entries.empty())
+  FindEntryIndexesThatContain(addr, 0, m_entries.size(), indexes);
+
 return indexes.size();
   }
 
@@ -806,6 +804,56 @@
 protected:
   Collection m_entries;
   Compare m_compare;
+
+private:
+  // We can treat the vector as a flattened Binary Search Tree, augmenting it
+  // with upper bounds (max of range endpoints) for every index allows us to
+  // query for range containment quicker.
+  B ComputeUpperBounds(size_t lo, size_t hi) {
+size_t mid = (lo + hi) / 2;
+auto &entry = m_entries[mid];
+
+entry.upper_bound = entry.base + entry.size;
+
+if (lo < mid)
+  entry.upper_bound =
+  std::max(entry.upper_bound, ComputeUpperBounds(lo, mid));
+
+if (mid + 1 < hi)
+  entry.upper_bound =
+  std::max(entry.upper_bound, ComputeUpperBounds(mid + 1, hi));
+
+return entry.upper_bound;
+  }
+
+  // This is based on the augmented tree implementation found at
+  // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
+  void FindEntryIndexesThatContain(B addr, size_t lo, size_t hi,
+   std::vector &indexes) {
+size_t mid = (lo + hi) / 2;
+auto entry = m_entries[mid];
+
+// addr is greater than the rightmost point of any interval below mid
+// so there are cannot be any matches.
+if (addr > entry.upper_bound)
+  return;
+
+// Recursively search left subtree
+if (lo < mid)
+  FindEntryIndexesThatContain(addr, lo, mid, indexes);
+
+// If addr is smaller than the start of the current interval it
+// cannot contain it nor can any of its right subtree.
+if (addr < entry.base)
+  return;
+
+if (entry.Contains(addr))
+  indexes.push_back(entry.data);
+
+// Recursively search right subtree
+if (mid + 1 < hi)
+  FindEntryIndexesThatContain(addr, mid + 1, hi, indexes);
+  }
 };
 
 // A simple range  with data class where you get to define the type of
___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [PATCH] D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar created this revision.
unnar added reviewers: labath, teemperor.
Herald added subscribers: lldb-commits, JDevlieghere, arphaman.
Herald added a project: LLDB.

This adds unit tests for FindEntryIndexesThatContain, this is done in 
preparation for changing the logic of the function.


Repository:
  rLLDB LLDB

https://reviews.llvm.org/D75180

Files:
  lldb/unittests/Utility/RangeMapTest.cpp


Index: lldb/unittests/Utility/RangeMapTest.cpp
===
--- lldb/unittests/Utility/RangeMapTest.cpp
+++ lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,13 @@
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +101,37 @@
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}


Index: lldb/unittests/Utility/RangeMapTest.cpp
===
--- lldb/unittests/Utility/RangeMapTest.cpp
+++ lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,13 @@
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +101,37 @@
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}
___
lldb-commits mailing list
lldb-com

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

[Pavel Labath via Phabricator via lldb-commits]

labath added a comment.

In D74759#1893186 , @unnar wrote:

> In D74759#1880499 , @labath wrote:
>
> > Have you done a proper complexity analysis here? I doubt the `O(log n)` 
> > claim is true in general. It would have to be at least `O(m + log n)` (m - 
> > number of elements found), but it's not clear to me whether even this is 
> > true in general. (However, I believe this can achieve ~~log(n) for 
> > non-degenerate cases.)
>
>
> I should have been more specific, searching for any interval that contains a 
> point can be done in `O(log n)` but in our case where we are searching for 
> all intervals that contain the point and as Jarin said we believe it takes 
> `O(m log n)` (I admit I have not done a thorough analysis of the time 
> complexity myself). The theoretical best you can do is indeed `O(m + log n)`.


Yep, I can easily convince myself is m*log(n). I can believe it can be 
O(m+log(n)) too, but proving that would require some pretty careful accounting. 
In either case, I am sure this is better than what we have now.

>> For testing you should add some c++ unit tests for the relevant interfaces.
> 
> Done. Do you think we should also unit test ComputeUpperBounds or just the 
> interface?

Testing the interface should be enough. In fact, the main thing that is 
bothering me about this patch at this stage is that the new "upper_bound" 
member is public and accessible to the user. I haven't decided yet what to do 
about it. Have you looked at what it would take to make that private somehow? 
Maybe by storing std::pair in the private vector, and only 
handing out pointers to the `Entry` component ?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759



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

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar added a comment.

Sure, removed tests from this patch. They are now at D75180 





Comment at: lldb/unittests/Utility/RangeMapTest.cpp:22
 
+const std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {

labath wrote:
> returning a const value from a function is fairly useless. All it does is 
> make the caller jump through some hoops if he really wants to modify it.
Noted.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759



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

[Lldb-commits] [PATCH] D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain

[Pavel Labath via Phabricator via lldb-commits]

labath accepted this revision.
labath added a comment.
This revision is now accepted and ready to land.

Thanks for doing this. Are you able to commit this yourself ?




Comment at: lldb/unittests/Utility/RangeMapTest.cpp:23
+std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {
+  std::vector result;

This doesn't look right. Could you run clang-format over this?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75180/new/

https://reviews.llvm.org/D75180



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

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar added a comment.

In D74759#1893450 , @labath wrote:

> In D74759#1893186 , @unnar wrote:
>
> > In D74759#1880499 , @labath wrote:
> >
> > > Have you done a proper complexity analysis here? I doubt the `O(log n)` 
> > > claim is true in general. It would have to be at least `O(m + log n)` (m 
> > > - number of elements found), but it's not clear to me whether even this 
> > > is true in general. (However, I believe this can achieve ~~log(n) for 
> > > non-degenerate cases.)
> >
> >
> > I should have been more specific, searching for any interval that contains 
> > a point can be done in `O(log n)` but in our case where we are searching 
> > for all intervals that contain the point and as Jarin said we believe it 
> > takes `O(m log n)` (I admit I have not done a thorough analysis of the time 
> > complexity myself). The theoretical best you can do is indeed `O(m + log 
> > n)`.
>
>
> Yep, I can easily convince myself is m*log(n). I can believe it can be 
> O(m+log(n)) too, but proving that would require some pretty careful 
> accounting. In either case, I am sure this is better than what we have now.
>
> >> For testing you should add some c++ unit tests for the relevant interfaces.
> > 
> > Done. Do you think we should also unit test ComputeUpperBounds or just the 
> > interface?
>
> Testing the interface should be enough. In fact, the main thing that is 
> bothering me about this patch at this stage is that the new "upper_bound" 
> member is public and accessible to the user. I haven't decided yet what to do 
> about it. Have you looked at what it would take to make that private somehow? 
> Maybe by storing std::pair in the private vector, and only 
> handing out pointers to the `Entry` component ?


That should work...although I'm not sure how that is any different to the range 
or data being public. If a user modifies anything then it has essentially 
invalidated the whole structure anyway.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74759/new/

https://reviews.llvm.org/D74759



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

[Lldb-commits] [PATCH] D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar updated this revision to Diff 246721.

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75180/new/

https://reviews.llvm.org/D75180

Files:
  lldb/unittests/Utility/RangeMapTest.cpp


Index: lldb/unittests/Utility/RangeMapTest.cpp
===
--- lldb/unittests/Utility/RangeMapTest.cpp
+++ lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,12 @@
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+std::vector FindEntryIndexes(uint32_t address, RangeDataVectorT map) 
{
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +100,37 @@
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}


Index: lldb/unittests/Utility/RangeMapTest.cpp
===
--- lldb/unittests/Utility/RangeMapTest.cpp
+++ lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,12 @@
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+std::vector FindEntryIndexes(uint32_t address, RangeDataVectorT map) {
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +100,37 @@
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}
___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [PATCH] D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain

[Unnar Freyr Erlendsson via Phabricator via lldb-commits]

unnar marked 2 inline comments as done.
unnar added a comment.

No, I can't. If you could submit this for me it would be great.




Comment at: lldb/unittests/Utility/RangeMapTest.cpp:23
+std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {
+  std::vector result;

labath wrote:
> This doesn't look right. Could you run clang-format over this?
I'm not sure what happened there while splitting up the patch but it's fixed. 
(I will also set up a pre-commit hook for clang-format so that it should stop 
this from happening going forward)


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75180/new/

https://reviews.llvm.org/D75180



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

[Lldb-commits] [PATCH] D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain

[Pavel Labath via Phabricator via lldb-commits]

labath added inline comments.



Comment at: lldb/unittests/Utility/RangeMapTest.cpp:23
+std::vector FindEntryIndexes(uint32_t address,
+ RangeDataVectorT map) {
+  std::vector result;

unnar wrote:
> labath wrote:
> > This doesn't look right. Could you run clang-format over this?
> I'm not sure what happened there while splitting up the patch but it's fixed. 
> (I will also set up a pre-commit hook for clang-format so that it should stop 
> this from happening going forward)
That's ok. Don't worry about it.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75180/new/

https://reviews.llvm.org/D75180



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

[Lldb-commits] [lldb] 594130d - Add unit tests for RangeDataVector::FindEntryIndexesThatContain

[Pavel Labath via lldb-commits]

Author: Unnar Freyr Erlendsson
Date: 2020-02-26T16:47:42+01:00
New Revision: 594130db0a56c3c3d889f750c5c971fac6f33594

URL: 
https://github.com/llvm/llvm-project/commit/594130db0a56c3c3d889f750c5c971fac6f33594
DIFF: 
https://github.com/llvm/llvm-project/commit/594130db0a56c3c3d889f750c5c971fac6f33594.diff

LOG: Add unit tests for RangeDataVector::FindEntryIndexesThatContain

Summary: This adds unit tests for FindEntryIndexesThatContain, this is done in 
preparation for changing the logic of the function.

Reviewers: labath, teemperor

Reviewed By: labath

Subscribers: arphaman, JDevlieghere, lldb-commits

Tags: #lldb

Differential Revision: https://reviews.llvm.org/D75180

Added: 


Modified: 
lldb/unittests/Utility/RangeMapTest.cpp

Removed: 




diff  --git a/lldb/unittests/Utility/RangeMapTest.cpp 
b/lldb/unittests/Utility/RangeMapTest.cpp
index fcefa4797ab7..8a243b656218 100644
--- a/lldb/unittests/Utility/RangeMapTest.cpp
+++ b/lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,12 @@ static testing::Matcher EntryIs(uint32_t ID) 
{
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+std::vector FindEntryIndexes(uint32_t address, RangeDataVectorT map) 
{
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +100,37 @@ TEST(RangeDataVector, CustomSort) {
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}



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

[Lldb-commits] [PATCH] D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain

[Pavel Labath via Phabricator via lldb-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG594130db0a56: Add unit tests for 
RangeDataVector::FindEntryIndexesThatContain (authored by unnar, committed by 
labath).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75180/new/

https://reviews.llvm.org/D75180

Files:
  lldb/unittests/Utility/RangeMapTest.cpp


Index: lldb/unittests/Utility/RangeMapTest.cpp
===
--- lldb/unittests/Utility/RangeMapTest.cpp
+++ lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,12 @@
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+std::vector FindEntryIndexes(uint32_t address, RangeDataVectorT map) 
{
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +100,37 @@
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}


Index: lldb/unittests/Utility/RangeMapTest.cpp
===
--- lldb/unittests/Utility/RangeMapTest.cpp
+++ lldb/unittests/Utility/RangeMapTest.cpp
@@ -19,6 +19,12 @@
   return testing::Pointee(testing::Field(&EntryT::data, ID));
 }
 
+std::vector FindEntryIndexes(uint32_t address, RangeDataVectorT map) {
+  std::vector result;
+  map.FindEntryIndexesThatContain(address, result);
+  return result;
+}
+
 TEST(RangeDataVector, FindEntryThatContains) {
   RangeDataVectorT Map;
   uint32_t NextID = 0;
@@ -94,3 +100,37 @@
   EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
   EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
 }
+
+TEST(RangeDataVector, FindEntryIndexesThatContain) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 10, 10));
+  Map.Append(EntryT(10, 10, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
+}
+
+TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
+  RangeDataVectorT Map;
+  Map.Append(EntryT(0, 40, 10));
+  Map.Append(EntryT(10, 20, 11));
+  Map.Append(EntryT(20, 10, 12));
+  Map.Sort();
+
+  EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
+  EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
+  EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
+  EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
+}
___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [lldb] 7822c8c - [lldb/test] Skip running a test under ASan, it intentionally double-frees

[Vedant Kumar via lldb-commits]

Author: Vedant Kumar
Date: 2020-02-26T10:11:39-08:00
New Revision: 7822c8c03e9fe8c857da21c4ccbe28396b43130d

URL: 
https://github.com/llvm/llvm-project/commit/7822c8c03e9fe8c857da21c4ccbe28396b43130d
DIFF: 
https://github.com/llvm/llvm-project/commit/7822c8c03e9fe8c857da21c4ccbe28396b43130d.diff

LOG: [lldb/test] Skip running a test under ASan, it intentionally double-frees

Added: 


Modified: 
lldb/test/API/functionalities/process_crash_info/TestProcessCrashInfo.py

Removed: 




diff  --git 
a/lldb/test/API/functionalities/process_crash_info/TestProcessCrashInfo.py 
b/lldb/test/API/functionalities/process_crash_info/TestProcessCrashInfo.py
index 3caa7c5d905a..d0f47de83eea 100644
--- a/lldb/test/API/functionalities/process_crash_info/TestProcessCrashInfo.py
+++ b/lldb/test/API/functionalities/process_crash_info/TestProcessCrashInfo.py
@@ -25,6 +25,7 @@ def tearDown(self):
 self.runCmd("settings clear auto-confirm")
 TestBase.tearDown(self)
 
+@skipIfAsan # The test process intentionally double-frees.
 @skipUnlessDarwin
 def test_cli(self):
 """Test that `process status --verbose` fetches the extended crash
@@ -41,6 +42,7 @@ def test_cli(self):
 patterns=["\"message\".*pointer being freed was not 
allocated"])
 
 
+@skipIfAsan # The test process intentionally hits a memory bug.
 @skipUnlessDarwin
 def test_api(self):
 """Test that lldb can fetch a crashed process' extended crash 
information



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

[Lldb-commits] [lldb] 34312ed - Remove unneeded Compiler.h and DataTypes.h includes, NFC

[Reid Kleckner via lldb-commits]

Author: Reid Kleckner
Date: 2020-02-26T10:36:17-08:00
New Revision: 34312ed24e17a0e8269611b954e489fa7759f115

URL: 
https://github.com/llvm/llvm-project/commit/34312ed24e17a0e8269611b954e489fa7759f115
DIFF: 
https://github.com/llvm/llvm-project/commit/34312ed24e17a0e8269611b954e489fa7759f115.diff

LOG: Remove unneeded Compiler.h and DataTypes.h includes, NFC

Added: 


Modified: 
lldb/source/Utility/Timer.cpp
llvm/include/llvm/Support/MathExtras.h
llvm/include/llvm/Support/SwapByteOrder.h

Removed: 




diff  --git a/lldb/source/Utility/Timer.cpp b/lldb/source/Utility/Timer.cpp
index 003afa1cb114..d55c9863117b 100644
--- a/lldb/source/Utility/Timer.cpp
+++ b/lldb/source/Utility/Timer.cpp
@@ -15,6 +15,7 @@
 #include 
 
 #include 
+#include 
 #include 
 #include 
 

diff  --git a/llvm/include/llvm/Support/MathExtras.h 
b/llvm/include/llvm/Support/MathExtras.h
index 5ad055a4f478..67a96911a765 100644
--- a/llvm/include/llvm/Support/MathExtras.h
+++ b/llvm/include/llvm/Support/MathExtras.h
@@ -18,6 +18,7 @@
 #include 
 #include 
 #include 
+#include 
 #include 
 #include 
 #include 

diff  --git a/llvm/include/llvm/Support/SwapByteOrder.h 
b/llvm/include/llvm/Support/SwapByteOrder.h
index 700ede7eb589..94ba1aa0a266 100644
--- a/llvm/include/llvm/Support/SwapByteOrder.h
+++ b/llvm/include/llvm/Support/SwapByteOrder.h
@@ -14,9 +14,8 @@
 #ifndef LLVM_SUPPORT_SWAPBYTEORDER_H
 #define LLVM_SUPPORT_SWAPBYTEORDER_H
 
-#include "llvm/Support/Compiler.h"
-#include "llvm/Support/DataTypes.h"
 #include 
+#include 
 #include 
 #if defined(_MSC_VER) && !defined(_DEBUG)
 #include 



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

[Lldb-commits] [PATCH] D75200: AddressSanitizer failure in MemoryCache

[Paolo Severini via Phabricator via lldb-commits]

paolosev created this revision.
paolosev added reviewers: labath, vsk, JDevlieghere, clayborg.
paolosev added a project: LLDB.
Herald added subscribers: lldb-commits, sunfish, aheejin.

The original discussion for this issues is here 
.

The lldb sanitized bot is flagging a container-overflow error after we 
introduced test `TestWasm.py`:
http://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake-sanitized/992/testReport/junit/lldb-api/functionalities_gdb_remote_client/TestWasm_py/




11283==ERROR: AddressSanitizer: container-overflow on address 0x61516184 at 
pc 0x00010b4608f0 bp 0x7ffee4f00130 sp 0x7ffee4eff8f8
-

READ of size 512 at 0x61516184 thread T0

  #0 0x10b4608ef in __asan_memcpy+0x1af 
(libclang_rt.asan_osx_dynamic.dylib:x86_64+0x418ef)
  #1 0x1116486d5 in lldb_private::MemoryCache::Read(unsigned long long, void*, 
unsigned long, lldb_private::Status&) Memory.cpp:189
  #2 0x9d0e9 in 
lldb_private::Module::GetMemoryObjectFile(std::__1::shared_ptr
 const&, unsigned long long, lldb_private::Status&, unsigned long) 
Module.cpp:298
  #3 0x11169eeef in 
lldb_private::Process::ReadModuleFromMemory(lldb_private::FileSpec const&, 
unsigned long long, unsigned long) Process.cpp:2402
  #4 0x3337b in 
lldb_private::DynamicLoader::LoadModuleAtAddress(lldb_private::FileSpec const&, 
unsigned long long, unsigned long long, bool) DynamicLoader.cpp:212
  #5 0x111ed53da in 
lldb_private::process_gdb_remote::ProcessGDBRemote::LoadModuleAtAddress(lldb_private::FileSpec
 const&, unsigned long long, unsigned long long, bool) ProcessGDBRemote.cpp:4767
  #6 0x111ed59b8 in 
lldb_private::process_gdb_remote::ProcessGDBRemote::LoadModules() 
ProcessGDBRemote.cpp:4801
  #7 0x1119c59aa in lldb_private::wasm::DynamicLoaderWasmDYLD::DidAttach() 
DynamicLoaderWasmDYLD.cpp:63
  #8 0x1116a3a97 in lldb_private::Process::CompleteAttach() Process.cpp:2930
  #9 0x1116a6bdf in lldb_private::Process::ConnectRemote(lldb_private::Stream*, 
llvm::StringRef) Process.cpp:3015
  #10 0x110a362ee in lldb::SBTarget::ConnectRemote(lldb::SBListener&, char 
const*, char const*, lldb::SBError&) SBTarget.cpp:559

There is actually a problem in the MemoryCache code. From 
ProcessGDBRemote::LoadModules we read the initial chunk (512 bytes) of an 
object file. In MemoryCache::Read, since this data is not cached yet, we call 
m_process.ReadMemoryFromInferior to actually read the memory (lines 174-241), 
look at the bottom of:

  size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len,
   Status &error) {
  [...]
  while (bytes_left > 0) {
[...]
BlockMap::const_iterator pos = m_L2_cache.find(curr_addr);
BlockMap::const_iterator end = m_L2_cache.end();
  
if (pos != end) {
  size_t curr_read_size = cache_line_byte_size - cache_offset;
  if (curr_read_size > bytes_left)
curr_read_size = bytes_left;
  
  memcpy(dst_buf + dst_len - bytes_left,
 pos->second->GetBytes() + cache_offset, curr_read_size);
  [...]
}
  
// We need to read from the process
  
if (bytes_left > 0) {
  assert((curr_addr % cache_line_byte_size) == 0);
  std::unique_ptr data_buffer_heap_up(
  new DataBufferHeap(cache_line_byte_size, 0));
  size_t process_bytes_read = m_process.ReadMemoryFromInferior(
  curr_addr, data_buffer_heap_up->GetBytes(),
  data_buffer_heap_up->GetByteSize(), error);
  if (process_bytes_read == 0)
return dst_len - bytes_left;
  
  if (process_bytes_read != cache_line_byte_size)
data_buffer_heap_up->SetByteSize(process_bytes_read);
  m_L2_cache[curr_addr] = DataBufferSP(data_buffer_heap_up.release());
  // We have read data and put it into the cache, continue through the
  // loop again to get the data out of the cache...
}

First, we allocate a DataBufferHeap with the size of our cache_line_byte_size, 
512 bytes, and we pass it to ReadMemoryFromInferior().
The problem is that in this test the whole object file is only 0x84 bytes, so 
we resize data_buffer_heap_up to a smaller size with 
data_buffer_heap_up->SetByteSize(process_bytes_read).
Then we iterate back up in the while loop, and try to read from this 
reallocated buffer. But we still try to read curr_read_size==512 bytes, so read 
past the buffer size. In fact the overflow is at address 0x61516184 for a 
buffer that starts at 0x61516100.

Note that the simple fix of just reading the available bytes doesn't work: 
Module::GetMemoryObjectFile expects to always be able to read at least 512 
bytes, and it fails if the object file is smaller:

  ObjectFile *Module::GetMemoryObjectFile(const lldb::ProcessSP &process_sp,

[Lldb-commits] [PATCH] D72751: [LLDB] Add DynamicLoaderWasmDYLD plugin for WebAssembly debugging

[Paolo Severini via Phabricator via lldb-commits]

paolosev added a comment.

In D72751#1892925 , @labath wrote:

> > Who is the owner of this MemoryCache code I should ask for a review?
>
> It sounds like the fix will be fairly straightforward. I think anyone on this 
> thread should be able to review that.


Patch created: https://reviews.llvm.org/D75200.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72751/new/

https://reviews.llvm.org/D72751



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

[Lldb-commits] [PATCH] D75200: AddressSanitizer failure in MemoryCache

[Greg Clayton via Phabricator via lldb-commits]

clayborg added a comment.

Not sure this is the right fix. The calling code should listen to how many 
bytes were actually read from memory and avoid touching any bytes. So we should 
fix Module::GetMemoryObjectFile to resize its buffer back to only the size that 
was read. Something like:

  const size_t bytes_read =
  process_sp->ReadMemory(header_addr, data_up->GetBytes(),
 data_up->GetByteSize(), readmem_error);
  if (bytes_read < size_to_read)
data_sp->SetByteSize(bytes_read);
  if (data_sp->GetByteSize() > 0) {
DataBufferSP data_sp(data_up.release());
m_objfile_sp = ObjectFile::FindPlugin(shared_from_this(), process_sp,
  header_addr, data_sp);


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75200/new/

https://reviews.llvm.org/D75200



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

[Lldb-commits] [lldb] 34ee941 - [ObjectFileMachO] Fix a build error on embedded.

[Davide Italiano via lldb-commits]

Author: Davide Italiano
Date: 2020-02-26T14:31:48-08:00
New Revision: 34ee941f6d04454838456f0dc692f4abab5cdd19

URL: 
https://github.com/llvm/llvm-project/commit/34ee941f6d04454838456f0dc692f4abab5cdd19
DIFF: 
https://github.com/llvm/llvm-project/commit/34ee941f6d04454838456f0dc692f4abab5cdd19.diff

LOG: [ObjectFileMachO] Fix a build error on embedded.

Added: 


Modified: 
lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

Removed: 




diff  --git a/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp 
b/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
index 5b75e1f2a2ec..ad12819847cd 100644
--- a/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
+++ b/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
@@ -3506,8 +3506,8 @@ size_t ObjectFileMachO::ParseSymtab() {
   N_FUN_addr_to_sym_idx.equal_range(nlist.n_value);
   if (range.first != range.second) {
 bool found_it = false;
-for (const auto pos = range.first;
- pos != range.second; ++pos) {
+for (auto pos = range.first; pos != range.second;
+ ++pos) {
   if (sym[sym_idx].GetMangled().GetName(
   lldb::eLanguageTypeUnknown,
   Mangled::ePreferMangled) ==
@@ -3551,8 +3551,8 @@ size_t ObjectFileMachO::ParseSymtab() {
   nlist.n_value);
   if (range.first != range.second) {
 bool found_it = false;
-for (const auto pos = range.first;
- pos != range.second; ++pos) {
+for (auto pos = range.first; pos != range.second;
+ ++pos) {
   if (sym[sym_idx].GetMangled().GetName(
   lldb::eLanguageTypeUnknown,
   Mangled::ePreferMangled) ==



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

[Lldb-commits] [PATCH] D74892: [lldb][cmake] Also use local submodule visibility on Darwin

[Michael Spencer via Phabricator via lldb-commits]

Bigcheese accepted this revision.
Bigcheese added a comment.
This revision is now accepted and ready to land.

lgtm


Repository:
  rLLDB LLDB

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D74892/new/

https://reviews.llvm.org/D74892



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

[Lldb-commits] [PATCH] D75200: AddressSanitizer failure in MemoryCache

[Paolo Severini via Phabricator via lldb-commits]

paolosev updated this revision to Diff 246868.
paolosev added a comment.

In D75200#1894162 , @clayborg wrote:

> Not sure this is the right fix. The calling code should listen to how many 
> bytes were actually read from memory and avoid touching any bytes. So we 
> should fix Module::GetMemoryObjectFile to resize its buffer back to only the 
> size that was read. S


I agree that the previous fix wasn't great, but it had the advantage that it 
did not change the semantics of `MemoryCache::Read`. I was afraid there could 
be other places where the caller might assume that MemoryCache::Read fills the 
whole buffer even when it does not have enough data to copy, even though it was 
a strange semantics.

(By the way, I am having some difficulties in running //all// the tests with 
'ninja check-lldb' to check this fix, both on Windows and on Linux/WSL2, there 
must be something wrong with my CMake configurations).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75200/new/

https://reviews.llvm.org/D75200

Files:
  lldb/source/Core/Module.cpp
  lldb/source/Target/Memory.cpp


Index: lldb/source/Target/Memory.cpp
===
--- lldb/source/Target/Memory.cpp
+++ lldb/source/Target/Memory.cpp
@@ -232,8 +232,13 @@
 if (process_bytes_read == 0)
   return dst_len - bytes_left;
 
-if (process_bytes_read != cache_line_byte_size)
+if (process_bytes_read != cache_line_byte_size) {
+  if (process_bytes_read < data_buffer_heap_up->GetByteSize()) {
+dst_len -= data_buffer_heap_up->GetByteSize() - process_bytes_read;
+bytes_left = process_bytes_read;
+  }
   data_buffer_heap_up->SetByteSize(process_bytes_read);
+}
 m_L2_cache[curr_addr] = DataBufferSP(data_buffer_heap_up.release());
 // We have read data and put it into the cache, continue through the
 // loop again to get the data out of the cache...
Index: lldb/source/Core/Module.cpp
===
--- lldb/source/Core/Module.cpp
+++ lldb/source/Core/Module.cpp
@@ -297,7 +297,9 @@
   const size_t bytes_read =
   process_sp->ReadMemory(header_addr, data_up->GetBytes(),
  data_up->GetByteSize(), readmem_error);
-  if (bytes_read == size_to_read) {
+  if (bytes_read < size_to_read)
+data_up->SetByteSize(bytes_read);
+  if (data_up->GetByteSize() > 0) {
 DataBufferSP data_sp(data_up.release());
 m_objfile_sp = ObjectFile::FindPlugin(shared_from_this(), process_sp,
   header_addr, data_sp);


Index: lldb/source/Target/Memory.cpp
===
--- lldb/source/Target/Memory.cpp
+++ lldb/source/Target/Memory.cpp
@@ -232,8 +232,13 @@
 if (process_bytes_read == 0)
   return dst_len - bytes_left;
 
-if (process_bytes_read != cache_line_byte_size)
+if (process_bytes_read != cache_line_byte_size) {
+  if (process_bytes_read < data_buffer_heap_up->GetByteSize()) {
+dst_len -= data_buffer_heap_up->GetByteSize() - process_bytes_read;
+bytes_left = process_bytes_read;
+  }
   data_buffer_heap_up->SetByteSize(process_bytes_read);
+}
 m_L2_cache[curr_addr] = DataBufferSP(data_buffer_heap_up.release());
 // We have read data and put it into the cache, continue through the
 // loop again to get the data out of the cache...
Index: lldb/source/Core/Module.cpp
===
--- lldb/source/Core/Module.cpp
+++ lldb/source/Core/Module.cpp
@@ -297,7 +297,9 @@
   const size_t bytes_read =
   process_sp->ReadMemory(header_addr, data_up->GetBytes(),
  data_up->GetByteSize(), readmem_error);
-  if (bytes_read == size_to_read) {
+  if (bytes_read < size_to_read)
+data_up->SetByteSize(bytes_read);
+  if (data_up->GetByteSize() > 0) {
 DataBufferSP data_sp(data_up.release());
 m_objfile_sp = ObjectFile::FindPlugin(shared_from_this(), process_sp,
   header_addr, data_sp);
___
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits

[Lldb-commits] [PATCH] D75200: AddressSanitizer failure in MemoryCache

[Paolo Severini via Phabricator via lldb-commits]

paolosev added a comment.

The Harbormaster errors don't seem to be real failures:

  
/mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/source/Core/Module.cpp:9:10:
 error: 'lldb/Core/Module.h' file not found [clang-diagnostic-error]
  #include "lldb/Core/Module.h"
   ^
  
/mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/source/Target/Memory.cpp:9:10:
 error: 'lldb/Target/Memory.h' file not found [clang-diagnostic-error]
  #include "lldb/Target/Memory.h"
   ^


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D75200/new/

https://reviews.llvm.org/D75200



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