[lldb][AArch64] Add MakeTaggedRanges to MemoryTagManager

[DavidSpickett]

Summary

This is to be used when you want to know what subranges
of a larger range have memory tagging. Like MakeTaggedRange
but memory without tags is skipped and you get a list of ranges back.

Will be used later by DumpDataExtractor to show memory tags.

MakeTaggedRanges assumes that the memory regions it is
given are sorted in ascending order and do not overlap.
For the current use case where you get regions from
GetMemoryRegions and are on some Linux like OS, this is
reasonable to assume.

I've used asserts to check those conditions. In future
any API binding will check them up front to prevent a crash.

[omjavaid]

lldb/source/Plugins/Process/Utility/MemoryTagManagerAArch64MTE.cpp

71

I think this function name should be camel-case although there are examples of similar functions not following the camel case. I am bit unsure do you a reference for/against?

149

so what would be the behavior if regions do overlap. Should we return an error rather than keep going?

161

RemoveNonAddressBits hard-coded but symbols may resolve to higher order bits containing PACs. For now I only came across code pointers with PACs. But if you suspect code regions can be inputs to this function then may be make accommodating changes probably in separate patch.

168

this loop looks like a candidate for using range based for instead of declaring iterate. We can always break if range in invalid.

for (auto region : memory_regions) may be ?

[DavidSpickett]

• Range based for loop over memory regions
• Reduce number of ->GetRange calls
• Check for overlapping regions up front and error if founda
• Added test that the range invesion check removes ignores tags
• Added the same test to existing MakeTaggedRange tests

[DavidSpickett]

lldb/source/Plugins/Process/Utility/MemoryTagManagerAArch64MTE.cpp

149

I've addressed this by checking up front for overlaps in the list. We might see this if:

• there is invalid data from the remote
• the remote is using a memory protection unit that allows overlaps (Arm M class allows this)

Afaik no hosted OS would let you have two mappings that use the same range of virtual memory.

There's no good way to reconcile the overlap so an error is what I've gone with. I'll handle this error in the later patch to DumpDataExtractor.

It is a shame to walk the regions up front but as mentioned in the comment I found some corner cases that lead to some ugly code that would have its own drawbacks.

Given that the eventual goal here is "memory read <...> --show-tags" which is opt in, and we expect a fairly small amount of regions, I think the compromise is worth it.

(if M class ever got memory tagging we can make this smarter overall)

161

The end goal here is "memory read <...> --show-tags" and that command will have to use the ABI plugin in any case so the addresses this gets will be PAC/TBI/MTE free already.

So for now this should be addressed by https://reviews.llvm.org/D103626. (once I convince myself which address should be show in the output but that's not for this issue)

I agree that there is a bit of a conflict here with the ABI plugin removing everything vs the MemoryTagManager removing only the tag. However I think that it will work fine in this case.

[DavidSpickett]

lldb/source/Plugins/Process/Utility/MemoryTagManagerAArch64MTE.cpp

161

Speaking of conflict, MemoryTagManagerAArch64MTE::RemoveNonAddressBits should probably be renamed to RemoveTagBits but I'll do that as another change.

[DavidSpickett]

ping!

lldb/source/Plugins/Process/Utility/MemoryTagManagerAArch64MTE.cpp

161

On second thought this will be better done in a general effort to remove the layering weirdness we currently have. Where we've got a tag manager that is removing the tags and the rest of the top byte. Then the ABI removing all of that and more.

Ideally the tag manager should only know about tags but some places assume it can also remove non-address bits in general. So this is more than just a rename and will take a bit more time.

[DavidSpickett]

Rebase, update the name of RemoveTagBits.

[omjavaid]

lldb/source/Plugins/Process/Utility/MemoryTagManagerAArch64MTE.cpp

178

From implementation of Process::GetMemoryRegions It seems our regions vector will always be sorted and non-overlapping? Is it no so?

Process::GetMemoryRegions starts from addr zero and keeps fetching regions based on end_addr of previous range. So in all cases regions will be sorted.

[DavidSpickett]

Since output of GetMemoryRegions will be sorted and not overlap,
switch the checks to asserts and don't sort the input regions.

Updated the testing to reflect that and added some comment
diagrams showing what regions are used for the later tests.

[omjavaid]

LGTM Thanks! for your patience

[DavidSpickett]

MakeTaggedRanges now takes const MemoryRegionInfos& like MakeTaggedRange does.

lldb/include/lldb/Target/MemoryTagManager.h

public:
   virtual TagRange ExpandToGranule(TagRange range) const = 0;
 
   // Given a range addr to end_addr, check that:
   // * end_addr >= addr (when memory tags are removed)
   // * the granule aligned range is completely covered by tagged memory
   //   (which may include one or more memory regions)
   //
   // If so, return a modified range which will have been expanded
-  // to be granule aligned.
+  // to be granule aligned. Otherwise return an error.
   //
   // Tags in the input addresses are ignored and not present
   // in the returned range.
   virtual llvm::Expected<TagRange> MakeTaggedRange(
       lldb::addr_t addr, lldb::addr_t end_addr,
       const lldb_private::MemoryRegionInfos &memory_regions) const = 0;
 
+  // Given a range addr to end_addr, check that end_addr >= addr.
+  // If it is not, return an error saying so.
+  // Otherwise, granule align it and return a set of ranges representing
+  // subsections of the aligned range that have memory tagging enabled.
+  //
+  // Basically a sparse version of MakeTaggedRange. Use this when you
+  // want to know which parts of a larger range have memory tagging.
+  //
+  // Regions in memory_regions should be sorted in ascending order and
+  // not overlap. (use Process GetMemoryRegions)
+  //
+  // Tags in the input addresses are ignored and not present
+  // in the returned ranges.
+  virtual llvm::Expected<std::vector<TagRange>> MakeTaggedRanges(
+      lldb::addr_t addr, lldb::addr_t end_addr,
+      const lldb_private::MemoryRegionInfos &memory_regions) const = 0;
+
   // Return the type value to use in GDB protocol qMemTags packets to read
   // allocation tags. This is named "Allocation" specifically because the spec
   // allows for logical tags to be read the same way, though we do not use that.
   //
   // This value is unique within a given architecture. Meaning that different
   // tagging schemes within the same architecture should use unique values,
   // but other architectures can overlap those values.
   virtual int32_t GetAllocationTagType() const = 0;

lldb/source/Plugins/Process/Utility/MemoryTagManagerAArch64MTE.h

public:
   ptrdiff_t AddressDiff(lldb::addr_t addr1, lldb::addr_t addr2) const override;
 
   TagRange ExpandToGranule(TagRange range) const override;
 
   llvm::Expected<TagRange> MakeTaggedRange(
       lldb::addr_t addr, lldb::addr_t end_addr,
       const lldb_private::MemoryRegionInfos &memory_regions) const override;
 
+  llvm::Expected<std::vector<TagRange>> MakeTaggedRanges(
+      lldb::addr_t addr, lldb::addr_t end_addr,
+      const lldb_private::MemoryRegionInfos &memory_regions) const override;
+
   llvm::Expected<std::vector<lldb::addr_t>>
   UnpackTagsData(const std::vector<uint8_t> &tags,
                  size_t granules = 0) const override;
 
   llvm::Expected<std::vector<uint8_t>>
   PackTags(const std::vector<lldb::addr_t> &tags) const override;
 
   llvm::Expected<std::vector<lldb::addr_t>>
   RepeatTagsForRange(const std::vector<lldb::addr_t> &tags,
                      TagRange range) const override;
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_SOURCE_PLUGINS_PROCESS_UTILITY_MEMORYTAGMANAGERAARCH64MTE_H

lldb/source/Plugins/Process/Utility/MemoryTagManagerAArch64MTE.cpp

 //===-- MemoryTagManagerAArch64MTE.cpp --------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "MemoryTagManagerAArch64MTE.h"
+#include "llvm/Support/Error.h"
+#include <assert.h>
 
 using namespace lldb_private;
 
 static const unsigned MTE_START_BIT = 56;
 static const unsigned MTE_TAG_MAX = 0xf;
 static const unsigned MTE_GRANULE_SIZE = 16;
 
 lldb::addr_t
MemoryTagManagerAArch64MTE::ExpandToGranule(TagRange range) const {
   // Then align up to the end of the granule
   size_t align_up_amount = granule - (new_len % granule);
   if (align_up_amount != granule)
     new_len += align_up_amount;
 
   return TagRange(new_start, new_len);
 }
 
+static llvm::Error MakeInvalidRangeErr(lldb::addr_t addr,
+                                       lldb::addr_t end_addr) {
+  return llvm::createStringError(
+      llvm::inconvertibleErrorCode(),
+      "End address (0x%" PRIx64
+      ") must be greater than the start address (0x%" PRIx64 ")",
+      end_addr, addr);
+}
+
 llvm::Expected<MemoryTagManager::TagRange>
 MemoryTagManagerAArch64MTE::MakeTaggedRange(
     lldb::addr_t addr, lldb::addr_t end_addr,
     const lldb_private::MemoryRegionInfos &memory_regions) const {
   // First check that the range is not inverted.
   // We must remove tags here otherwise an address with a higher
   // tag value will always be > the other.
   ptrdiff_t len = AddressDiff(end_addr, addr);
-  if (len <= 0) {
-    return llvm::createStringError(
-        llvm::inconvertibleErrorCode(),
-        "End address (0x%" PRIx64
-        ") must be greater than the start address (0x%" PRIx64 ")",
-        end_addr, addr);
-  }
+  if (len <= 0)
+    return MakeInvalidRangeErr(addr, end_addr);
 
   // Region addresses will not have memory tags. So when searching
   // we must use an untagged address.
   MemoryRegionInfo::RangeType tag_range(RemoveTagBits(addr), len);
   tag_range = ExpandToGranule(tag_range);
 
   // Make a copy so we can use the original for errors and the final return.
   MemoryRegionInfo::RangeType remaining_range(tag_range);
while (remaining_range.IsValid()) {
     remaining_range.SetRangeBase(region->GetRange().GetRangeEnd());
     remaining_range.SetRangeEnd(old_end);
   }
 
   // Every part of the range is contained within a tagged memory region.
   return tag_range;
 }
 
+llvm::Expected<std::vector<MemoryTagManager::TagRange>>
+MemoryTagManagerAArch64MTE::MakeTaggedRanges(
+    lldb::addr_t addr, lldb::addr_t end_addr,
+    const lldb_private::MemoryRegionInfos &memory_regions) const {
+  // First check that the range is not inverted.
+  // We must remove tags here otherwise an address with a higher
+  // tag value will always be > the other.
+  ptrdiff_t len = AddressDiff(end_addr, addr);
+  if (len <= 0)
+    return MakeInvalidRangeErr(addr, end_addr);
+
+  std::vector<MemoryTagManager::TagRange> tagged_ranges;
+  // No memory regions means no tagged memory at all
+  if (memory_regions.empty())
+    return tagged_ranges;
+
+  // For the logic to work regions must be in ascending order
+  // which is what you'd have if you used GetMemoryRegions.
+  assert(std::is_sorted(
+      memory_regions.begin(), memory_regions.end(),
+      [](const MemoryRegionInfo &lhs, const MemoryRegionInfo &rhs) {
+        return lhs.GetRange().GetRangeBase() < rhs.GetRange().GetRangeBase();
+      }));
+
+  // If we're debugging userspace in an OS like Linux that uses an MMU,
+  // the only reason we'd get overlapping regions is incorrect data.
+  // It is possible that won't hold for embedded with memory protection
+  // units (MPUs) that allow overlaps.
+  //
+  // For now we're going to assume the former, as there is no good way
+  // to handle overlaps. For example:
+  // < requested range >
+  // [--  region 1   --]
+  //           [-- region 2--]
+  // Where the first region will reduce the requested range to nothing
+  // and exit early before it sees the overlap.
+  MemoryRegionInfos::const_iterator overlap = std::adjacent_find(
+      memory_regions.begin(), memory_regions.end(),
+      [](const MemoryRegionInfo &lhs, const MemoryRegionInfo &rhs) {
+        return rhs.GetRange().DoesIntersect(lhs.GetRange());
+      });
+  UNUSED_IF_ASSERT_DISABLED(overlap);
+  assert(overlap == memory_regions.end());
+
+  // Region addresses will not have memory tags so when searching
+  // we must use an untagged address.
+  MemoryRegionInfo::RangeType range(RemoveTagBits(addr), len);
+  range = ExpandToGranule(range);
+
+  // While there are regions to check and the range has non zero length
+  for (const MemoryRegionInfo &region : memory_regions) {
+    // If range we're checking has been reduced to zero length, exit early
+    if (!range.IsValid())
+      break;
+
+    // If the region doesn't overlap the range at all, ignore it.
+    if (!region.GetRange().DoesIntersect(range))
+      continue;
+
+    // If it's tagged record this sub-range.
+    // (assuming that it's already granule aligned)
+    if (region.GetMemoryTagged()) {
+      // The region found may extend outside the requested range.
+      // For example the first region might start before the range.
+      // We must only add what covers the requested range.
+      lldb::addr_t start =
+          std::max(range.GetRangeBase(), region.GetRange().GetRangeBase());
+      lldb::addr_t end =
+          std::min(range.GetRangeEnd(), region.GetRange().GetRangeEnd());
+      tagged_ranges.push_back(MemoryTagManager::TagRange(start, end - start));
+    }
+
+    // Move the range up to start at the end of the region.
+    lldb::addr_t old_end = range.GetRangeEnd();
+    // This "slides" the range so it moves the end as well.
+    range.SetRangeBase(region.GetRange().GetRangeEnd());
+    // So we set the end back to the original end address after sliding it up.
+    range.SetRangeEnd(old_end);
+    // (if the above were to try to set end < begin the range will just be set
+    // to 0 size)
+  }
+
+  return tagged_ranges;
+}
+
 llvm::Expected<std::vector<lldb::addr_t>>
 MemoryTagManagerAArch64MTE::UnpackTagsData(const std::vector<uint8_t> &tags,
                                            size_t granules /*=0*/) const {
   // 0 means don't check the number of tags before unpacking
   if (granules) {
     size_t num_tags = tags.size() / GetTagSizeInBytes();
     if (num_tags != granules) {
       return llvm::createStringError(

lldb/unittests/Process/Utility/MemoryTagManagerAArch64MTETest.cpp

ASSERT_THAT_EXPECTED(
           "Address range 0x0:0x10 is not in a memory tagged region"));
 
   // Range must not be inverted
   ASSERT_THAT_EXPECTED(
       manager.MakeTaggedRange(1, 0, memory_regions),
       llvm::FailedWithMessage(
           "End address (0x0) must be greater than the start address (0x1)"));
 
+  // The inversion check ignores tags in the addresses (MTE tags start at bit
+  // 56).
+  ASSERT_THAT_EXPECTED(
+      manager.MakeTaggedRange((lldb::addr_t)1 << 56,
+                              ((lldb::addr_t)2 << 56) + 0x10, memory_regions),
+      llvm::FailedWithMessage(
+          "Address range 0x0:0x10 is not in a memory tagged region"));
+
   // Adding a single region to cover the whole range
   memory_regions.push_back(MakeRegionInfo(0, 0x1000, true));
 
   // Range can have different tags for begin and end
   // (which would make it look inverted if we didn't remove them)
   // Note that range comes back with an untagged base and alginment
   // applied.
   MemoryTagManagerAArch64MTE::TagRange expected_range(0x0, 0x10);
TEST(MemoryTagManagerAArch64MTETest, MakeTaggedRange) {
 
   // If we tag the middle part it succeeds
   memory_regions.back().SetMemoryTagged(MemoryRegionInfo::eYes);
   got = manager.MakeTaggedRange(0, 0x1000, memory_regions);
   ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
   ASSERT_EQ(*got, expected_range);
 }
 
+TEST(MemoryTagManagerAArch64MTETest, MakeTaggedRanges) {
+  MemoryTagManagerAArch64MTE manager;
+  MemoryRegionInfos memory_regions;
+
+  // Note that MakeTaggedRanges takes start/end address.
+  // Whereas TagRanges and regions take start address and size.
+
+  // Range must not be inverted
+  ASSERT_THAT_EXPECTED(
+      manager.MakeTaggedRanges(1, 0, memory_regions),
+      llvm::FailedWithMessage(
+          "End address (0x0) must be greater than the start address (0x1)"));
+
+  // We remove tags before doing the inversion check, so this is not an error.
+  // Also no regions means no tagged regions returned.
+  // (bit 56 is where MTE tags begin)
+  llvm::Expected<std::vector<MemoryTagManager::TagRange>> got =
+      manager.MakeTaggedRanges((lldb::addr_t)2 << 56,
+                               ((lldb::addr_t)1 << 56) + 0x10, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_EQ(*got, std::vector<MemoryTagManager::TagRange>{});
+
+  // Cover whole range, untagged. No ranges returned.
+  memory_regions.push_back(MakeRegionInfo(0, 0x20, false));
+  got = manager.MakeTaggedRanges(0, 0x20, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_EQ(*got, std::vector<MemoryTagManager::TagRange>{});
+
+  // Make the region tagged and it'll be the one range returned.
+  memory_regions.back().SetMemoryTagged(MemoryRegionInfo::eYes);
+  got = manager.MakeTaggedRanges(0, 0x20, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_EQ(*got, std::vector<MemoryTagManager::TagRange>{
+                      MemoryTagManager::TagRange(0, 0x20)});
+
+  // This region will be trimmed if it's larger than the whole range.
+  memory_regions.clear();
+  memory_regions.push_back(MakeRegionInfo(0, 0x40, true));
+  got = manager.MakeTaggedRanges(0x10, 0x30, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_EQ(*got, std::vector<MemoryTagManager::TagRange>{
+                      MemoryTagManager::TagRange(0x10, 0x20)});
+
+  memory_regions.clear();
+
+  // For the following tests we keep the input regions
+  // in ascending order as MakeTaggedRanges expects.
+
+  // Only start of range is tagged, only that is returned.
+  // Start the region just before the requested range to check
+  // we limit the result to the requested range.
+  memory_regions.push_back(MakeRegionInfo(0, 0x20, true));
+  got = manager.MakeTaggedRanges(0x10, 0x100, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_EQ(*got, std::vector<MemoryTagManager::TagRange>{
+                      MemoryTagManager::TagRange(0x10, 0x10)});
+
+  // Add a tagged region at the end, now we get both
+  // and the middle is untagged.
+  // <tagged: [0x0, 0x20)>
+  // <...>
+  // <tagged: [0xE0, 0x120)>
+  // The range added here is deliberately over the end of the
+  // requested range to show that we trim the end.
+  memory_regions.push_back(MakeRegionInfo(0xE0, 0x40, true));
+  got = manager.MakeTaggedRanges(0x10, 0x110, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+
+  std::vector<MemoryTagManager::TagRange> expected{
+      MemoryTagManager::TagRange(0x10, 0x10),
+      MemoryTagManager::TagRange(0xE0, 0x30)};
+  ASSERT_EQ(*got, expected);
+
+  // Now add a middle tagged region.
+  // <tagged: [0x0, 0x20)>
+  // <...>
+  // <tagged: [0x90, 0xB0)>
+  // <...>
+  // <tagged: [0xE0, 0x120)>
+  memory_regions.insert(std::next(memory_regions.begin()),
+                        MakeRegionInfo(0x90, 0x20, true));
+
+  // As the given regions are in ascending order, the resulting
+  // tagged ranges are also. So this new range goes in the middle.
+  expected.insert(std::next(expected.begin()),
+                  MemoryTagManager::TagRange(0x90, 0x20));
+  got = manager.MakeTaggedRanges(0x10, 0x110, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_EQ(*got, expected);
+
+  // Then if we add untagged regions in between the tagged,
+  // the output should stay the same.
+  // <tagged:   [0x0, 0x20)>
+  // <untagged: [0x20, 0x90)>
+  // <tagged:   [0x90, 0xB0)>
+  // <untagged: [0xB0, 0xE0)>
+  // <tagged:   [0xE0, 0x120)>
+  memory_regions.insert(std::next(memory_regions.begin()),
+                        MakeRegionInfo(0x20, 0x70, false));
+  memory_regions.insert(std::prev(memory_regions.end()),
+                        MakeRegionInfo(0xB0, 0x30, false));
+  got = manager.MakeTaggedRanges(0x10, 0x110, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_EQ(*got, expected);
+
+  // Finally check that we handle only having the end of the range.
+  memory_regions.clear();
+  expected.clear();
+
+  memory_regions.push_back(MakeRegionInfo(0x100, 0x10, true));
+  expected.push_back(MemoryTagManager::TagRange(0x100, 0x10));
+  got = manager.MakeTaggedRanges(0x10, 0x110, memory_regions);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_EQ(*got, expected);
+}
+
 TEST(MemoryTagManagerAArch64MTETest, RemoveTagBits) {
   MemoryTagManagerAArch64MTE manager;
 
   ASSERT_EQ(0, 0);
   // Removes the whole top byte
   ASSERT_EQ((lldb::addr_t)0x00ffeedd11223344,
             manager.RemoveTagBits(0x00ffeedd11223344));
   ASSERT_EQ((lldb::addr_t)0x0000000000000000,