[lldb][AArch64] Add class for managing memory tags

[DavidSpickett]

Summary

This adds the MemoryTagManager class and a specialisation
of that class for AArch64 MTE tags. It provides a generic
interface for various tagging operations.
Adding/removing tags, diffing tagged pointers, etc.

Later patches will use this manager to handle memory tags
in generic code in both lldb and lldb-server.
Since it will be used in both, the base class header is in
lldb/Target.
(MemoryRegionInfo is another example of this pattern)

[DavidSpickett]

Omair, I've taken one of your suggestions on the class name from the other review.

The MTE RFC gives some background on why we need such a class (https://lists.llvm.org/pipermail/lldb-dev/2020-August/016402.html).

Some of the operations map to the intrinsics provided by the ACLE:
https://developer.arm.com/documentation/101028/0012/10--Memory-tagging-intrinsics

[omjavaid]

This looks good overall except for one comment inline.

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

44

I am a little apprehensive about this AddressDiff function. AArch64 virtual address is either 48 bits or 52 bits. MTE start from 56th bit and I believe bits (48 - 55) will be either set zero (for user address) and set to one for kernel addresses.
I am not sure if there is an interface available for us to know if VA is 48 or 52 bits. What do you think how should we manage this here.

[DavidSpickett]

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

44

I looked at this a while back and there is no user space way to tell what size virtual address you have. You can assume at least 48 but then the rest I think is handled by some backwards compatibility stuff that means you don't have to care.

What is an issue is this only ignores the tag bits, not the whole top byte. This is the instruction the ptrdiff intrinsic emits:

C6.2.317 SUBPS
Subtract Pointer, setting Flags subtracts the 56-bit address held in the second source register from the 56-bit address
held in the first source register, sign-extends the result to 64-bits, and writes the result to the destination register. It
updates the condition flags based on the result of the subtraction.

That assumes top byte ignore, so I should be doing the same here along with the sign extension to handle the 0/1 fill.
(this might apply to a lot more than just this diff call too)

[omjavaid]

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

44

hmm .. yes GDB also assumes 52 bit address for AArch64. Did you try reading kenel space address during testing and see what you get in that case may be stepping into a syscall (never tried it with LLDB) not sure if this is a must have for LLDB as its currently a user application debugger as far as AArch64 is concerned.

Even if this is 52 bits VA this function assumes bit 52-55 set to zero? This can also mean that by the time we get this address TBI interface would have cleaned it up for us?

I think we should have a way to figure out significant address bits and clean up the rest. For now this needs no change but I guess I ll have to manage this in TBI support and provided and interface for significant address bit for a process.

[DavidSpickett]

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

44

I wasn't aware stepping into a syscall was a thing for lldb but I'll see what I can find.

General TBI handling would solve some of this, still need to sign extend based on bit 55 I think.

I'm going to change this to ignore the top byte always, so it'll work on a PAC+MTE system. Then later we can make it use the "proper" TBI hooks.

[DavidSpickett]

• Add RemoveNonAddressBits which will remove the entire top byte not just tags
• Remove SetLogicalTag/RemoveLogicalTag/CopyLogicalTag which are now unused in the proceeding patches

[DavidSpickett]

@labath Could you comment on the overall strategy that I'm going for?

I'll summarise my intention, the rest of the review stack here implements that if you have time/want to dig into the details.

• Tag managers provide utilities to handle tags without knowing the details of each tagging scheme
• lldb commands can get one by asking the current process, which looks for an architecture plugin, which can then provide a tag manager or not
• lldb uses the "mt" flag of memory regions to precheck reads before sending them
• lldb-server will ask the native register context for a manager, which can provide one or not based on the target and what it's being asked to do

It would be great to get agreement on those key points since it forms the basis of the new commands.

FWIW I have implemented "memory tag write" based on this and it works quite well, but I can put that up too if you feel the context would help. (another 4/5 patches)

@omjavaid The tag manager AddressDiff is currently removing the whole top byte. I think eventually we'll want to go back to removing just the tag bits and let your non address bits handle the rest but for now it's working ok.

[DavidSpickett]

• Rebase onto main

[DavidSpickett]

Rebase onto main.

[DavidSpickett]

Rebase

[omjavaid]

This looks ok to me apart from some cosmetic nits. Also you may figure out a way to clean up the whole address including pauth now after D99944 is merged.

lldb/include/lldb/Target/MemoryTagManager.h

73

Bytes per tag conveys a different message like "No of bytes of memory this tag corresponds to"
It could GetTagByteSize or something.

80

This might also be renamed to UnpackTagsData because input is not guaranteed to be tags unless their byte size is 1.

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

29

This function need to take care of Pointer Auth mask which could be living in bits 48:54

62

May be consider doing something like below to avoid calculating mod twice.

lldb::addr_t align_up_amount = new_len % granule;
if (align_up_amount)
....

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

25

All functions below have no spacing between them may be consider adding a few spaces while combining declaration of setter/getter or other similar function in consecutive lines.

lldb/unittests/Process/Utility/MemoryTagManagerAArch64MTETest.cpp

74

This is confusing // Reading less than 1 granule, rounds up to 1 granule
May be reword a little like "No of bytes being read are less than bytes per granule"

101

This should be able to remove pointer auth mask so fix this test accordingly.

117

likewise.

[DavidSpickett]

Address all comments apart from address handling that I need
to spend some time thinking about.

It may end up that the best way to do this is have the tag manager
provide a way to remove only the tags and let the other parts
of lldb deal with addresses using the ABI methods you're adding.

[DavidSpickett]

Rebase

[DavidSpickett]

Rebase

[omjavaid]

@DavidSpickett Do you have any further plans for this and other patches in the series. I was wondering if there is nothing to add we can go ahead and merge this series.

[DavidSpickett]

I am going to go over them this afternoon. I'm about to land some lldb patches that allow some easy refactoring, and your ABI patch might be useable too. If using the ABI method is better as a follow up then we can get started landing them.

[DavidSpickett]

Rebase onto main.

[DavidSpickett]

@omjavaid As it stands, RemoveNonAddressBits here removes the top byte unconditionally.

You asked for pointer signatures to be removed as well, which would be neatly solved by using the ABI plugin. Ok to land this as is, then write a follow up to migrate to using the ABI plugin?

[omjavaid]

In D97281#2824678, @DavidSpickett wrote:

@omjavaid As it stands, RemoveNonAddressBits here removes the top byte unconditionally.

You asked for pointer signatures to be removed as well, which would be neatly solved by using the ABI plugin. Ok to land this as is, then write a follow up to migrate to using the ABI plugin?

Yes I think this is LGTM.

lldb/include/lldb/Target/MemoryTagManager.h

+//===-- MemoryTagManager.h --------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLDB_TARGET_MEMORYTAGMANAGER_H
+#define LLDB_TARGET_MEMORYTAGMANAGER_H
+
+#include "lldb/Utility/RangeMap.h"
+#include "lldb/lldb-private.h"
+#include "llvm/Support/Error.h"
+
+namespace lldb_private {
+
+// This interface allows high level commands to handle memory tags
+// in a generic way.
+//
+// Definitions:
+//   logical tag    - the tag stored in a pointer
+//   allocation tag - the tag stored in hardware
+//                    (e.g. special memory, cache line bits)
+//   granule        - number of bytes of memory a single tag applies to
+
+class MemoryTagManager {
+public:
+  typedef Range<lldb::addr_t, size_t> TagRange;
+
+  // Extract the logical tag from a pointer
+  // The tag is returned as a plain value, with any shifts removed.
+  // For example if your tags are stored in bits 56-60 then the logical tag
+  // you get will have been shifted down 56 before being returned.
+  virtual lldb::addr_t GetLogicalTag(lldb::addr_t addr) const = 0;
+
+  // Remove non address bits from a pointer
+  virtual lldb::addr_t RemoveNonAddressBits(lldb::addr_t addr) const = 0;
+
+  // Return the difference between two addresses, ignoring any logical tags they
+  // have. If your tags are just part of a larger set of ignored bits, this
+  // should ignore all those bits.
+  virtual ptrdiff_t AddressDiff(lldb::addr_t addr1,
+                                lldb::addr_t addr2) const = 0;
+
+  // Return the number of bytes a single tag covers
+  virtual lldb::addr_t GetGranuleSize() const = 0;
+
+  // Align an address range to granule boundaries.
+  // So that reading memory tags for the new range returns
+  // tags that will cover the original range.
+  //
+  // Say your granules are 16 bytes and you want
+  // tags for 16 bytes of memory starting from address 8.
+  // 1 granule isn't enough because it only covers addresses
+  // 0-16, we want addresses 8-24. So the range must be
+  // expanded to 2 granules.
+  virtual TagRange ExpandToGranule(TagRange range) 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;
+
+  // Return the number of bytes a single tag will be packed into during
+  // transport. For example an MTE tag is 4 bits but occupies 1 byte during
+  // transport.
+  virtual size_t GetTagSizeInBytes() const = 0;
+
+  // Unpack tags from their stored format (e.g. gdb qMemTags data) into seperate
+  // tags. Checks that each tag is within the expected value range and that the
+  // number of tags found matches the number of granules we originally asked
+  // for.
+  virtual llvm::Expected<std::vector<lldb::addr_t>>
+  UnpackTagsData(const std::vector<uint8_t> &tags, size_t granules) const = 0;
+
+  virtual ~MemoryTagManager() {}
+};
+
+} // namespace lldb_private
+
+#endif // LLDB_TARGET_MEMORYTAGMANAGER_H

lldb/source/Plugins/Process/Utility/CMakeLists.txt

 add_lldb_library(lldbPluginProcessUtility
   AuxVector.cpp
   DynamicRegisterInfo.cpp
   FreeBSDSignals.cpp
   GDBRemoteSignals.cpp
   HistoryThread.cpp
   HistoryUnwind.cpp
   InferiorCallPOSIX.cpp
   LinuxProcMaps.cpp
   LinuxSignals.cpp
+  MemoryTagManagerAArch64MTE.cpp
   MipsLinuxSignals.cpp
   NativeProcessSoftwareSingleStep.cpp
   NativeRegisterContextDBReg_arm64.cpp
   NativeRegisterContextDBReg_x86.cpp
   NativeRegisterContextRegisterInfo.cpp
   NetBSDSignals.cpp
   RegisterContext_x86.cpp
   RegisterContextDarwin_arm.cpp

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

+//===-- MemoryTagManagerAArch64MTE.h ----------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLDB_SOURCE_PLUGINS_PROCESS_UTILITY_MEMORYTAGMANAGERAARCH64MTE_H
+#define LLDB_SOURCE_PLUGINS_PROCESS_UTILITY_MEMORYTAGMANAGERAARCH64MTE_H
+
+#include "lldb/Target/MemoryTagManager.h"
+
+namespace lldb_private {
+
+class MemoryTagManagerAArch64MTE : public MemoryTagManager {
+public:
+  // This enum is supposed to be shared for all of AArch64 but until
+  // there are more tag types than MTE, it will live here.
+  enum MTETagTypes {
+    eMTE_logical = 0,
+    eMTE_allocation = 1,
+  };
+
+  lldb::addr_t GetGranuleSize() const override;
+  int32_t GetAllocationTagType() const override;
+  size_t GetTagSizeInBytes() const override;
+
+  lldb::addr_t GetLogicalTag(lldb::addr_t addr) const override;
+  lldb::addr_t RemoveNonAddressBits(lldb::addr_t addr) const override;
+  ptrdiff_t AddressDiff(lldb::addr_t addr1, lldb::addr_t addr2) const override;
+
+  TagRange ExpandToGranule(TagRange range) const override;
+
+  llvm::Expected<std::vector<lldb::addr_t>>
+  UnpackTagsData(const std::vector<uint8_t> &tags,
+                 size_t granules) 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"
+
+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::GetLogicalTag(lldb::addr_t addr) const {
+  return (addr >> MTE_START_BIT) & MTE_TAG_MAX;
+}
+
+lldb::addr_t
+MemoryTagManagerAArch64MTE::RemoveNonAddressBits(lldb::addr_t addr) const {
+  // Here we're ignoring the whole top byte. If you've got MTE
+  // you must also have TBI (top byte ignore).
+  // The other 4 bits could contain other extension bits or
+  // user metadata.
+  return addr & ~((lldb::addr_t)0xFF << MTE_START_BIT);
+}
+
+ptrdiff_t MemoryTagManagerAArch64MTE::AddressDiff(lldb::addr_t addr1,
+                                                  lldb::addr_t addr2) const {
+  return RemoveNonAddressBits(addr1) - RemoveNonAddressBits(addr2);
+}
+
+lldb::addr_t MemoryTagManagerAArch64MTE::GetGranuleSize() const {
+  return MTE_GRANULE_SIZE;
+}
+
+int32_t MemoryTagManagerAArch64MTE::GetAllocationTagType() const {
+  return eMTE_allocation;
+}
+
+size_t MemoryTagManagerAArch64MTE::GetTagSizeInBytes() const { return 1; }
+
+MemoryTagManagerAArch64MTE::TagRange
+MemoryTagManagerAArch64MTE::ExpandToGranule(TagRange range) const {
+  // Ignore reading a length of 0
+  if (!range.IsValid())
+    return range;
+
+  const size_t granule = GetGranuleSize();
+
+  // Align start down to granule start
+  lldb::addr_t new_start = range.GetRangeBase();
+  lldb::addr_t align_down_amount = new_start % granule;
+  new_start -= align_down_amount;
+
+  // Account for the distance we moved the start above
+  size_t new_len = range.GetByteSize() + align_down_amount;
+  // 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);
+}
+
+llvm::Expected<std::vector<lldb::addr_t>>
+MemoryTagManagerAArch64MTE::UnpackTagsData(const std::vector<uint8_t> &tags,
+                                           size_t granules) const {
+  size_t num_tags = tags.size() / GetTagSizeInBytes();
+  if (num_tags != granules) {
+    return llvm::createStringError(
+        llvm::inconvertibleErrorCode(),
+        "Packed tag data size does not match expected number of tags. "
+        "Expected %" PRIu64 " tag(s) for %" PRIu64 " granules, got %" PRIu64
+        " tag(s).",
+        granules, granules, num_tags);
+  }
+
+  // (if bytes per tag was not 1, we would reconstruct them here)
+
+  std::vector<lldb::addr_t> unpacked;
+  unpacked.reserve(tags.size());
+  for (auto it = tags.begin(); it != tags.end(); ++it) {
+    // Check all tags are in range
+    if (*it > MTE_TAG_MAX) {
+      return llvm::createStringError(
+          llvm::inconvertibleErrorCode(),
+          "Found tag 0x%x which is > max MTE tag value of 0x%x.", *it,
+          MTE_TAG_MAX);
+    }
+    unpacked.push_back(*it);
+  }
+
+  return unpacked;
+}

lldb/unittests/Process/Utility/CMakeLists.txt

 
 set(LLVM_OPTIONAL_SOURCES
   ${FREEBSD_SOURCES}
   ${NETBSD_SOURCES})
 
 add_lldb_unittest(ProcessUtilityTests
   RegisterContextTest.cpp
   LinuxProcMapsTest.cpp
+  MemoryTagManagerAArch64MTETest.cpp
   ${PLATFORM_SOURCES}
 
   LINK_LIBS
-    lldbPluginProcessUtility)
+    lldbPluginProcessUtility
+    LLVMTestingSupport)

lldb/unittests/Process/Utility/MemoryTagManagerAArch64MTETest.cpp

+//===-- MemoryTagManagerAArch64MTETest.cpp --------------------------------===//
+//
+// 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 "Plugins/Process/Utility/MemoryTagManagerAArch64MTE.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gtest/gtest.h"
+
+using namespace lldb_private;
+
+TEST(MemoryTagManagerAArch64MTETest, UnpackTagsData) {
+  MemoryTagManagerAArch64MTE manager;
+
+  // Error for insufficient tag data
+  std::vector<uint8_t> input;
+  ASSERT_THAT_EXPECTED(
+      manager.UnpackTagsData(input, 2),
+      llvm::FailedWithMessage(
+          "Packed tag data size does not match expected number of tags. "
+          "Expected 2 tag(s) for 2 granules, got 0 tag(s)."));
+
+  // This is out of the valid tag range
+  input.push_back(0x1f);
+  ASSERT_THAT_EXPECTED(
+      manager.UnpackTagsData(input, 1),
+      llvm::FailedWithMessage(
+          "Found tag 0x1f which is > max MTE tag value of 0xf."));
+
+  // MTE tags are 1 per byte
+  input.pop_back();
+  input.push_back(0xe);
+  input.push_back(0xf);
+
+  std::vector<lldb::addr_t> expected{0xe, 0xf};
+
+  llvm::Expected<std::vector<lldb::addr_t>> got =
+      manager.UnpackTagsData(input, 2);
+  ASSERT_THAT_EXPECTED(got, llvm::Succeeded());
+  ASSERT_THAT(expected, testing::ContainerEq(*got));
+}
+
+TEST(MemoryTagManagerAArch64MTETest, GetLogicalTag) {
+  MemoryTagManagerAArch64MTE manager;
+
+  // Set surrounding bits to check shift is correct
+  ASSERT_EQ((lldb::addr_t)0, manager.GetLogicalTag(0xe0e00000ffffffff));
+  // Max tag value
+  ASSERT_EQ((lldb::addr_t)0xf, manager.GetLogicalTag(0x0f000000ffffffff));
+  ASSERT_EQ((lldb::addr_t)2, manager.GetLogicalTag(0x02000000ffffffff));
+}
+
+TEST(MemoryTagManagerAArch64MTETest, ExpandToGranule) {
+  MemoryTagManagerAArch64MTE manager;
+  // Reading nothing, no alignment needed
+  ASSERT_EQ(
+      MemoryTagManagerAArch64MTE::TagRange(0, 0),
+      manager.ExpandToGranule(MemoryTagManagerAArch64MTE::TagRange(0, 0)));
+
+  // Ranges with 0 size are unchanged even if address is non 0
+  // (normally 0x1234 would be aligned to 0x1230)
+  ASSERT_EQ(
+      MemoryTagManagerAArch64MTE::TagRange(0x1234, 0),
+      manager.ExpandToGranule(MemoryTagManagerAArch64MTE::TagRange(0x1234, 0)));
+
+  // Ranges already aligned don't change
+  ASSERT_EQ(
+      MemoryTagManagerAArch64MTE::TagRange(0x100, 64),
+      manager.ExpandToGranule(MemoryTagManagerAArch64MTE::TagRange(0x100, 64)));
+
+  // Any read of less than 1 granule is rounded up to reading 1 granule
+  ASSERT_EQ(
+      MemoryTagManagerAArch64MTE::TagRange(0, 16),
+      manager.ExpandToGranule(MemoryTagManagerAArch64MTE::TagRange(0, 1)));
+
+  // Start address is aligned down, and length modified accordingly
+  // Here bytes 8 through 24 straddle 2 granules. So the resulting range starts
+  // at 0 and covers 32 bytes.
+  ASSERT_EQ(
+      MemoryTagManagerAArch64MTE::TagRange(0, 32),
+      manager.ExpandToGranule(MemoryTagManagerAArch64MTE::TagRange(8, 16)));
+
+  // Here only the size of the range needs aligning
+  ASSERT_EQ(
+      MemoryTagManagerAArch64MTE::TagRange(16, 32),
+      manager.ExpandToGranule(MemoryTagManagerAArch64MTE::TagRange(16, 24)));
+
+  // Start and size need aligning here but we only need 1 granule to cover it
+  ASSERT_EQ(
+      MemoryTagManagerAArch64MTE::TagRange(16, 16),
+      manager.ExpandToGranule(MemoryTagManagerAArch64MTE::TagRange(18, 4)));
+}
+
+TEST(MemoryTagManagerAArch64MTETest, RemoveNonAddressBits) {
+  MemoryTagManagerAArch64MTE manager;
+
+  ASSERT_EQ(0, 0);
+  ASSERT_EQ((lldb::addr_t)0x00ffeedd11223344,
+            manager.RemoveNonAddressBits(0x00ffeedd11223344));
+  ASSERT_EQ((lldb::addr_t)0x0000000000000000,
+            manager.RemoveNonAddressBits(0xFF00000000000000));
+  ASSERT_EQ((lldb::addr_t)0x0055555566666666,
+            manager.RemoveNonAddressBits(0xee55555566666666));
+}
+
+TEST(MemoryTagManagerAArch64MTETest, AddressDiff) {
+  MemoryTagManagerAArch64MTE manager;
+
+  ASSERT_EQ(0, manager.AddressDiff(0, 0));
+  // Result is signed
+  ASSERT_EQ(10, manager.AddressDiff(10, 0));
+  ASSERT_EQ(-10, manager.AddressDiff(0, 10));
+  // Anything in the top byte is ignored
+  ASSERT_EQ(0, manager.AddressDiff(0x2211222233334444, 0x3311222233334444));
+  ASSERT_EQ(-32, manager.AddressDiff(0x5511222233334400, 0x4411222233334420));
+  ASSERT_EQ(65, manager.AddressDiff(0x9911222233334441, 0x6611222233334400));
+}