1 //===-- MemoryTagManagerAArch64MTE.cpp --------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "MemoryTagManagerAArch64MTE.h"
10 #include "llvm/Support/Error.h"
11 #include <assert.h>
12 
13 using namespace lldb_private;
14 
15 static const unsigned MTE_START_BIT = 56;
16 static const unsigned MTE_TAG_MAX = 0xf;
17 static const unsigned MTE_GRANULE_SIZE = 16;
18 
19 lldb::addr_t
GetLogicalTag(lldb::addr_t addr) const20 MemoryTagManagerAArch64MTE::GetLogicalTag(lldb::addr_t addr) const {
21   return (addr >> MTE_START_BIT) & MTE_TAG_MAX;
22 }
23 
24 lldb::addr_t
RemoveTagBits(lldb::addr_t addr) const25 MemoryTagManagerAArch64MTE::RemoveTagBits(lldb::addr_t addr) const {
26   // Here we're ignoring the whole top byte. If you've got MTE
27   // you must also have TBI (top byte ignore).
28   // The other 4 bits could contain other extension bits or
29   // user metadata.
30   return addr & ~((lldb::addr_t)0xFF << MTE_START_BIT);
31 }
32 
AddressDiff(lldb::addr_t addr1,lldb::addr_t addr2) const33 ptrdiff_t MemoryTagManagerAArch64MTE::AddressDiff(lldb::addr_t addr1,
34                                                   lldb::addr_t addr2) const {
35   return RemoveTagBits(addr1) - RemoveTagBits(addr2);
36 }
37 
GetGranuleSize() const38 lldb::addr_t MemoryTagManagerAArch64MTE::GetGranuleSize() const {
39   return MTE_GRANULE_SIZE;
40 }
41 
GetAllocationTagType() const42 int32_t MemoryTagManagerAArch64MTE::GetAllocationTagType() const {
43   return eMTE_allocation;
44 }
45 
GetTagSizeInBytes() const46 size_t MemoryTagManagerAArch64MTE::GetTagSizeInBytes() const { return 1; }
47 
48 MemoryTagManagerAArch64MTE::TagRange
ExpandToGranule(TagRange range) const49 MemoryTagManagerAArch64MTE::ExpandToGranule(TagRange range) const {
50   // Ignore reading a length of 0
51   if (!range.IsValid())
52     return range;
53 
54   const size_t granule = GetGranuleSize();
55 
56   // Align start down to granule start
57   lldb::addr_t new_start = range.GetRangeBase();
58   lldb::addr_t align_down_amount = new_start % granule;
59   new_start -= align_down_amount;
60 
61   // Account for the distance we moved the start above
62   size_t new_len = range.GetByteSize() + align_down_amount;
63   // Then align up to the end of the granule
64   size_t align_up_amount = granule - (new_len % granule);
65   if (align_up_amount != granule)
66     new_len += align_up_amount;
67 
68   return TagRange(new_start, new_len);
69 }
70 
MakeInvalidRangeErr(lldb::addr_t addr,lldb::addr_t end_addr)71 static llvm::Error MakeInvalidRangeErr(lldb::addr_t addr,
72                                        lldb::addr_t end_addr) {
73   return llvm::createStringError(
74       llvm::inconvertibleErrorCode(),
75       "End address (0x%" PRIx64
76       ") must be greater than the start address (0x%" PRIx64 ")",
77       end_addr, addr);
78 }
79 
80 llvm::Expected<MemoryTagManager::TagRange>
MakeTaggedRange(lldb::addr_t addr,lldb::addr_t end_addr,const lldb_private::MemoryRegionInfos & memory_regions) const81 MemoryTagManagerAArch64MTE::MakeTaggedRange(
82     lldb::addr_t addr, lldb::addr_t end_addr,
83     const lldb_private::MemoryRegionInfos &memory_regions) const {
84   // First check that the range is not inverted.
85   // We must remove tags here otherwise an address with a higher
86   // tag value will always be > the other.
87   ptrdiff_t len = AddressDiff(end_addr, addr);
88   if (len <= 0)
89     return MakeInvalidRangeErr(addr, end_addr);
90 
91   // Region addresses will not have memory tags. So when searching
92   // we must use an untagged address.
93   MemoryRegionInfo::RangeType tag_range(RemoveTagBits(addr), len);
94   tag_range = ExpandToGranule(tag_range);
95 
96   // Make a copy so we can use the original for errors and the final return.
97   MemoryRegionInfo::RangeType remaining_range(tag_range);
98 
99   // While there are parts of the range that don't have a matching tagged memory
100   // region
101   while (remaining_range.IsValid()) {
102     // Search for a region that contains the start of the range
103     MemoryRegionInfos::const_iterator region = std::find_if(
104         memory_regions.cbegin(), memory_regions.cend(),
105         [&remaining_range](const MemoryRegionInfo &region) {
106           return region.GetRange().Contains(remaining_range.GetRangeBase());
107         });
108 
109     if (region == memory_regions.cend() ||
110         region->GetMemoryTagged() != MemoryRegionInfo::eYes) {
111       // Some part of this range is untagged (or unmapped) so error
112       return llvm::createStringError(llvm::inconvertibleErrorCode(),
113                                      "Address range 0x%" PRIx64 ":0x%" PRIx64
114                                      " is not in a memory tagged region",
115                                      tag_range.GetRangeBase(),
116                                      tag_range.GetRangeEnd());
117     }
118 
119     // We've found some part of the range so remove that part and continue
120     // searching for the rest. Moving the base "slides" the range so we need to
121     // save/restore the original end. If old_end is less than the new base, the
122     // range will be set to have 0 size and we'll exit the while.
123     lldb::addr_t old_end = remaining_range.GetRangeEnd();
124     remaining_range.SetRangeBase(region->GetRange().GetRangeEnd());
125     remaining_range.SetRangeEnd(old_end);
126   }
127 
128   // Every part of the range is contained within a tagged memory region.
129   return tag_range;
130 }
131 
132 llvm::Expected<std::vector<MemoryTagManager::TagRange>>
MakeTaggedRanges(lldb::addr_t addr,lldb::addr_t end_addr,const lldb_private::MemoryRegionInfos & memory_regions) const133 MemoryTagManagerAArch64MTE::MakeTaggedRanges(
134     lldb::addr_t addr, lldb::addr_t end_addr,
135     const lldb_private::MemoryRegionInfos &memory_regions) const {
136   // First check that the range is not inverted.
137   // We must remove tags here otherwise an address with a higher
138   // tag value will always be > the other.
139   ptrdiff_t len = AddressDiff(end_addr, addr);
140   if (len <= 0)
141     return MakeInvalidRangeErr(addr, end_addr);
142 
143   std::vector<MemoryTagManager::TagRange> tagged_ranges;
144   // No memory regions means no tagged memory at all
145   if (memory_regions.empty())
146     return tagged_ranges;
147 
148   // For the logic to work regions must be in ascending order
149   // which is what you'd have if you used GetMemoryRegions.
150   assert(std::is_sorted(
151       memory_regions.begin(), memory_regions.end(),
152       [](const MemoryRegionInfo &lhs, const MemoryRegionInfo &rhs) {
153         return lhs.GetRange().GetRangeBase() < rhs.GetRange().GetRangeBase();
154       }));
155 
156   // If we're debugging userspace in an OS like Linux that uses an MMU,
157   // the only reason we'd get overlapping regions is incorrect data.
158   // It is possible that won't hold for embedded with memory protection
159   // units (MPUs) that allow overlaps.
160   //
161   // For now we're going to assume the former, as there is no good way
162   // to handle overlaps. For example:
163   // < requested range >
164   // [--  region 1   --]
165   //           [-- region 2--]
166   // Where the first region will reduce the requested range to nothing
167   // and exit early before it sees the overlap.
168   MemoryRegionInfos::const_iterator overlap = std::adjacent_find(
169       memory_regions.begin(), memory_regions.end(),
170       [](const MemoryRegionInfo &lhs, const MemoryRegionInfo &rhs) {
171         return rhs.GetRange().DoesIntersect(lhs.GetRange());
172       });
173   UNUSED_IF_ASSERT_DISABLED(overlap);
174   assert(overlap == memory_regions.end());
175 
176   // Region addresses will not have memory tags so when searching
177   // we must use an untagged address.
178   MemoryRegionInfo::RangeType range(RemoveTagBits(addr), len);
179   range = ExpandToGranule(range);
180 
181   // While there are regions to check and the range has non zero length
182   for (const MemoryRegionInfo &region : memory_regions) {
183     // If range we're checking has been reduced to zero length, exit early
184     if (!range.IsValid())
185       break;
186 
187     // If the region doesn't overlap the range at all, ignore it.
188     if (!region.GetRange().DoesIntersect(range))
189       continue;
190 
191     // If it's tagged record this sub-range.
192     // (assuming that it's already granule aligned)
193     if (region.GetMemoryTagged()) {
194       // The region found may extend outside the requested range.
195       // For example the first region might start before the range.
196       // We must only add what covers the requested range.
197       lldb::addr_t start =
198           std::max(range.GetRangeBase(), region.GetRange().GetRangeBase());
199       lldb::addr_t end =
200           std::min(range.GetRangeEnd(), region.GetRange().GetRangeEnd());
201       tagged_ranges.push_back(MemoryTagManager::TagRange(start, end - start));
202     }
203 
204     // Move the range up to start at the end of the region.
205     lldb::addr_t old_end = range.GetRangeEnd();
206     // This "slides" the range so it moves the end as well.
207     range.SetRangeBase(region.GetRange().GetRangeEnd());
208     // So we set the end back to the original end address after sliding it up.
209     range.SetRangeEnd(old_end);
210     // (if the above were to try to set end < begin the range will just be set
211     // to 0 size)
212   }
213 
214   return tagged_ranges;
215 }
216 
217 llvm::Expected<std::vector<lldb::addr_t>>
UnpackTagsData(const std::vector<uint8_t> & tags,size_t granules) const218 MemoryTagManagerAArch64MTE::UnpackTagsData(const std::vector<uint8_t> &tags,
219                                            size_t granules /*=0*/) const {
220   // 0 means don't check the number of tags before unpacking
221   if (granules) {
222     size_t num_tags = tags.size() / GetTagSizeInBytes();
223     if (num_tags != granules) {
224       return llvm::createStringError(
225           llvm::inconvertibleErrorCode(),
226           "Packed tag data size does not match expected number of tags. "
227           "Expected %zu tag(s) for %zu granule(s), got %zu tag(s).",
228           granules, granules, num_tags);
229     }
230   }
231 
232   // (if bytes per tag was not 1, we would reconstruct them here)
233 
234   std::vector<lldb::addr_t> unpacked;
235   unpacked.reserve(tags.size());
236   for (auto it = tags.begin(); it != tags.end(); ++it) {
237     // Check all tags are in range
238     if (*it > MTE_TAG_MAX) {
239       return llvm::createStringError(
240           llvm::inconvertibleErrorCode(),
241           "Found tag 0x%x which is > max MTE tag value of 0x%x.", *it,
242           MTE_TAG_MAX);
243     }
244     unpacked.push_back(*it);
245   }
246 
247   return unpacked;
248 }
249 
250 std::vector<lldb::addr_t>
UnpackTagsFromCoreFileSegment(CoreReaderFn reader,lldb::addr_t tag_segment_virtual_address,lldb::addr_t tag_segment_data_address,lldb::addr_t addr,size_t len) const251 MemoryTagManagerAArch64MTE::UnpackTagsFromCoreFileSegment(
252     CoreReaderFn reader, lldb::addr_t tag_segment_virtual_address,
253     lldb::addr_t tag_segment_data_address, lldb::addr_t addr,
254     size_t len) const {
255   // We can assume by now that addr and len have been granule aligned by a tag
256   // manager. However because we have 2 tags per byte we need to round the range
257   // up again to align to 2 granule boundaries.
258   const size_t granule = GetGranuleSize();
259   const size_t two_granules = granule * 2;
260   lldb::addr_t aligned_addr = addr;
261   size_t aligned_len = len;
262 
263   // First align the start address down.
264   if (aligned_addr % two_granules) {
265     assert(aligned_addr % two_granules == granule);
266     aligned_addr -= granule;
267     aligned_len += granule;
268   }
269 
270   // Then align the length up.
271   bool aligned_length_up = false;
272   if (aligned_len % two_granules) {
273     assert(aligned_len % two_granules == granule);
274     aligned_len += granule;
275     aligned_length_up = true;
276   }
277 
278   // ProcessElfCore should have validated this when it found the segment.
279   assert(aligned_addr >= tag_segment_virtual_address);
280 
281   // By now we know that aligned_addr is aligned to a 2 granule boundary.
282   const size_t offset_granules =
283       (aligned_addr - tag_segment_virtual_address) / granule;
284   // 2 tags per byte.
285   const size_t file_offset_in_bytes = offset_granules / 2;
286 
287   // By now we know that aligned_len is at least 2 granules.
288   const size_t tag_bytes_to_read = aligned_len / granule / 2;
289   std::vector<uint8_t> tag_data(tag_bytes_to_read);
290   const size_t bytes_copied =
291       reader(tag_segment_data_address + file_offset_in_bytes, tag_bytes_to_read,
292              tag_data.data());
293   UNUSED_IF_ASSERT_DISABLED(bytes_copied);
294   assert(bytes_copied == tag_bytes_to_read);
295 
296   std::vector<lldb::addr_t> tags;
297   tags.reserve(2 * tag_data.size());
298   // No need to check the range of the tag value here as each occupies only 4
299   // bits.
300   for (auto tag_byte : tag_data) {
301     tags.push_back(tag_byte & 0xf);
302     tags.push_back(tag_byte >> 4);
303   }
304 
305   // If we aligned the address down, don't return the extra first tag.
306   if (addr != aligned_addr)
307     tags.erase(tags.begin());
308   // If we aligned the length up, don't return the extra last tag.
309   if (aligned_length_up)
310     tags.pop_back();
311 
312   return tags;
313 }
314 
PackTags(const std::vector<lldb::addr_t> & tags) const315 llvm::Expected<std::vector<uint8_t>> MemoryTagManagerAArch64MTE::PackTags(
316     const std::vector<lldb::addr_t> &tags) const {
317   std::vector<uint8_t> packed;
318   packed.reserve(tags.size() * GetTagSizeInBytes());
319 
320   for (auto tag : tags) {
321     if (tag > MTE_TAG_MAX) {
322       return llvm::createStringError(llvm::inconvertibleErrorCode(),
323                                      "Found tag 0x%" PRIx64
324                                      " which is > max MTE tag value of 0x%x.",
325                                      tag, MTE_TAG_MAX);
326     }
327     packed.push_back(static_cast<uint8_t>(tag));
328   }
329 
330   return packed;
331 }
332 
333 llvm::Expected<std::vector<lldb::addr_t>>
RepeatTagsForRange(const std::vector<lldb::addr_t> & tags,TagRange range) const334 MemoryTagManagerAArch64MTE::RepeatTagsForRange(
335     const std::vector<lldb::addr_t> &tags, TagRange range) const {
336   std::vector<lldb::addr_t> new_tags;
337 
338   // If the range is not empty
339   if (range.IsValid()) {
340     if (tags.empty()) {
341       return llvm::createStringError(
342           llvm::inconvertibleErrorCode(),
343           "Expected some tags to cover given range, got zero.");
344     }
345 
346     // We assume that this range has already been expanded/aligned to granules
347     size_t granules = range.GetByteSize() / GetGranuleSize();
348     new_tags.reserve(granules);
349     for (size_t to_copy = 0; granules > 0; granules -= to_copy) {
350       to_copy = granules > tags.size() ? tags.size() : granules;
351       new_tags.insert(new_tags.end(), tags.begin(), tags.begin() + to_copy);
352     }
353   }
354 
355   return new_tags;
356 }
357