1//===-- Memory.cpp --------------------------------------------------------===//
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 "lldb/Target/Memory.h"
10#include "lldb/Target/Process.h"
11#include "lldb/Utility/DataBufferHeap.h"
12#include "lldb/Utility/LLDBLog.h"
13#include "lldb/Utility/Log.h"
14#include "lldb/Utility/RangeMap.h"
15#include "lldb/Utility/State.h"
16
17#include <cinttypes>
18#include <memory>
19
20using namespace lldb;
21using namespace lldb_private;
22
23// MemoryCache constructor
24MemoryCache::MemoryCache(Process &process)
25 : m_mutex(), m_L1_cache(), m_L2_cache(), m_invalid_ranges(),
26 m_process(process),
27 m_L2_cache_line_byte_size(process.GetMemoryCacheLineSize()) {}
28
29// Destructor
30MemoryCache::~MemoryCache() = default;
31
32void MemoryCache::Clear(bool clear_invalid_ranges) {
33 std::lock_guard<std::recursive_mutex> guard(m_mutex);
34 m_L1_cache.clear();
35 m_L2_cache.clear();
36 if (clear_invalid_ranges)
37 m_invalid_ranges.Clear();
38 m_L2_cache_line_byte_size = m_process.GetMemoryCacheLineSize();
39}
40
41void MemoryCache::AddL1CacheData(lldb::addr_t addr, const void *src,
42 size_t src_len) {
43 AddL1CacheData(
44 addr, data_buffer_sp: DataBufferSP(new DataBufferHeap(DataBufferHeap(src, src_len))));
45}
46
47void MemoryCache::AddL1CacheData(lldb::addr_t addr,
48 const DataBufferSP &data_buffer_sp) {
49 std::lock_guard<std::recursive_mutex> guard(m_mutex);
50 m_L1_cache[addr] = data_buffer_sp;
51}
52
53void MemoryCache::Flush(addr_t addr, size_t size) {
54 if (size == 0)
55 return;
56
57 std::lock_guard<std::recursive_mutex> guard(m_mutex);
58
59 // Erase any blocks from the L1 cache that intersect with the flush range
60 if (!m_L1_cache.empty()) {
61 AddrRange flush_range(addr, size);
62 BlockMap::iterator pos = m_L1_cache.upper_bound(x: addr);
63 if (pos != m_L1_cache.begin()) {
64 --pos;
65 }
66 while (pos != m_L1_cache.end()) {
67 AddrRange chunk_range(pos->first, pos->second->GetByteSize());
68 if (!chunk_range.DoesIntersect(rhs: flush_range))
69 break;
70 pos = m_L1_cache.erase(position: pos);
71 }
72 }
73
74 if (!m_L2_cache.empty()) {
75 const uint32_t cache_line_byte_size = m_L2_cache_line_byte_size;
76 const addr_t end_addr = (addr + size - 1);
77 const addr_t first_cache_line_addr = addr - (addr % cache_line_byte_size);
78 const addr_t last_cache_line_addr =
79 end_addr - (end_addr % cache_line_byte_size);
80 // Watch for overflow where size will cause us to go off the end of the
81 // 64 bit address space
82 uint32_t num_cache_lines;
83 if (last_cache_line_addr >= first_cache_line_addr)
84 num_cache_lines = ((last_cache_line_addr - first_cache_line_addr) /
85 cache_line_byte_size) +
86 1;
87 else
88 num_cache_lines =
89 (UINT64_MAX - first_cache_line_addr + 1) / cache_line_byte_size;
90
91 uint32_t cache_idx = 0;
92 for (addr_t curr_addr = first_cache_line_addr; cache_idx < num_cache_lines;
93 curr_addr += cache_line_byte_size, ++cache_idx) {
94 BlockMap::iterator pos = m_L2_cache.find(x: curr_addr);
95 if (pos != m_L2_cache.end())
96 m_L2_cache.erase(position: pos);
97 }
98 }
99}
100
101void MemoryCache::AddInvalidRange(lldb::addr_t base_addr,
102 lldb::addr_t byte_size) {
103 if (byte_size > 0) {
104 std::lock_guard<std::recursive_mutex> guard(m_mutex);
105 InvalidRanges::Entry range(base_addr, byte_size);
106 m_invalid_ranges.Append(entry: range);
107 m_invalid_ranges.Sort();
108 }
109}
110
111bool MemoryCache::RemoveInvalidRange(lldb::addr_t base_addr,
112 lldb::addr_t byte_size) {
113 if (byte_size > 0) {
114 std::lock_guard<std::recursive_mutex> guard(m_mutex);
115 const uint32_t idx = m_invalid_ranges.FindEntryIndexThatContains(addr: base_addr);
116 if (idx != UINT32_MAX) {
117 const InvalidRanges::Entry *entry = m_invalid_ranges.GetEntryAtIndex(i: idx);
118 if (entry->GetRangeBase() == base_addr &&
119 entry->GetByteSize() == byte_size)
120 return m_invalid_ranges.RemoveEntryAtIndex(idx);
121 }
122 }
123 return false;
124}
125
126lldb::DataBufferSP MemoryCache::GetL2CacheLine(lldb::addr_t line_base_addr,
127 Status &error) {
128 // This function assumes that the address given is aligned correctly.
129 assert((line_base_addr % m_L2_cache_line_byte_size) == 0);
130
131 std::lock_guard<std::recursive_mutex> guard(m_mutex);
132 auto pos = m_L2_cache.find(x: line_base_addr);
133 if (pos != m_L2_cache.end())
134 return pos->second;
135
136 auto data_buffer_heap_sp =
137 std::make_shared<DataBufferHeap>(args&: m_L2_cache_line_byte_size, args: 0);
138 size_t process_bytes_read = m_process.ReadMemoryFromInferior(
139 vm_addr: line_base_addr, buf: data_buffer_heap_sp->GetBytes(),
140 size: data_buffer_heap_sp->GetByteSize(), error);
141
142 // If we failed a read, not much we can do.
143 if (process_bytes_read == 0)
144 return lldb::DataBufferSP();
145
146 // If we didn't get a complete read, we can still cache what we did get.
147 if (process_bytes_read < m_L2_cache_line_byte_size)
148 data_buffer_heap_sp->SetByteSize(process_bytes_read);
149
150 m_L2_cache[line_base_addr] = data_buffer_heap_sp;
151 return data_buffer_heap_sp;
152}
153
154size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len,
155 Status &error) {
156 if (!dst || dst_len == 0)
157 return 0;
158
159 std::lock_guard<std::recursive_mutex> guard(m_mutex);
160 // FIXME: We should do a more thorough check to make sure that we're not
161 // overlapping with any invalid ranges (e.g. Read 0x100 - 0x200 but there's an
162 // invalid range 0x180 - 0x280). `FindEntryThatContains` has an implementation
163 // that takes a range, but it only checks to see if the argument is contained
164 // by an existing invalid range. It cannot check if the argument contains
165 // invalid ranges and cannot check for overlaps.
166 if (m_invalid_ranges.FindEntryThatContains(addr)) {
167 error = Status::FromErrorStringWithFormat(
168 format: "memory read failed for 0x%" PRIx64, addr);
169 return 0;
170 }
171
172 // Check the L1 cache for a range that contains the entire memory read.
173 // L1 cache contains chunks of memory that are not required to be the size of
174 // an L2 cache line. We avoid trying to do partial reads from the L1 cache to
175 // simplify the implementation.
176 if (!m_L1_cache.empty()) {
177 AddrRange read_range(addr, dst_len);
178 BlockMap::iterator pos = m_L1_cache.upper_bound(x: addr);
179 if (pos != m_L1_cache.begin()) {
180 --pos;
181 }
182 AddrRange chunk_range(pos->first, pos->second->GetByteSize());
183 if (chunk_range.Contains(range: read_range)) {
184 memcpy(dest: dst, src: pos->second->GetBytes() + (addr - chunk_range.GetRangeBase()),
185 n: dst_len);
186 return dst_len;
187 }
188 }
189
190 // If the size of the read is greater than the size of an L2 cache line, we'll
191 // just read from the inferior. If that read is successful, we'll cache what
192 // we read in the L1 cache for future use.
193 if (dst_len > m_L2_cache_line_byte_size) {
194 size_t bytes_read =
195 m_process.ReadMemoryFromInferior(vm_addr: addr, buf: dst, size: dst_len, error);
196 if (bytes_read > 0)
197 AddL1CacheData(addr, src: dst, src_len: bytes_read);
198 return bytes_read;
199 }
200
201 // If the size of the read fits inside one L2 cache line, we'll try reading
202 // from the L2 cache. Note that if the range of memory we're reading sits
203 // between two contiguous cache lines, we'll touch two cache lines instead of
204 // just one.
205
206 // We're going to have all of our loads and reads be cache line aligned.
207 addr_t cache_line_offset = addr % m_L2_cache_line_byte_size;
208 addr_t cache_line_base_addr = addr - cache_line_offset;
209 DataBufferSP first_cache_line = GetL2CacheLine(line_base_addr: cache_line_base_addr, error);
210 // If we get nothing, then the read to the inferior likely failed. Nothing to
211 // do here.
212 if (!first_cache_line)
213 return 0;
214
215 // If the cache line was not filled out completely and the offset is greater
216 // than what we have available, we can't do anything further here.
217 if (cache_line_offset >= first_cache_line->GetByteSize())
218 return 0;
219
220 uint8_t *dst_buf = (uint8_t *)dst;
221 size_t bytes_left = dst_len;
222 size_t read_size = first_cache_line->GetByteSize() - cache_line_offset;
223 if (read_size > bytes_left)
224 read_size = bytes_left;
225
226 memcpy(dest: dst_buf + dst_len - bytes_left,
227 src: first_cache_line->GetBytes() + cache_line_offset, n: read_size);
228 bytes_left -= read_size;
229
230 // If the cache line was not filled out completely and we still have data to
231 // read, we can't do anything further.
232 if (first_cache_line->GetByteSize() < m_L2_cache_line_byte_size &&
233 bytes_left > 0)
234 return dst_len - bytes_left;
235
236 // We'll hit this scenario if our read straddles two cache lines.
237 if (bytes_left > 0) {
238 cache_line_base_addr += m_L2_cache_line_byte_size;
239
240 // FIXME: Until we are able to more thoroughly check for invalid ranges, we
241 // will have to check the second line to see if it is in an invalid range as
242 // well. See the check near the beginning of the function for more details.
243 if (m_invalid_ranges.FindEntryThatContains(addr: cache_line_base_addr)) {
244 error = Status::FromErrorStringWithFormat(
245 format: "memory read failed for 0x%" PRIx64, cache_line_base_addr);
246 return dst_len - bytes_left;
247 }
248
249 DataBufferSP second_cache_line =
250 GetL2CacheLine(line_base_addr: cache_line_base_addr, error);
251 if (!second_cache_line)
252 return dst_len - bytes_left;
253
254 read_size = bytes_left;
255 if (read_size > second_cache_line->GetByteSize())
256 read_size = second_cache_line->GetByteSize();
257
258 memcpy(dest: dst_buf + dst_len - bytes_left, src: second_cache_line->GetBytes(),
259 n: read_size);
260 bytes_left -= read_size;
261
262 return dst_len - bytes_left;
263 }
264
265 return dst_len;
266}
267
268AllocatedBlock::AllocatedBlock(lldb::addr_t addr, uint32_t byte_size,
269 uint32_t permissions, uint32_t chunk_size)
270 : m_range(addr, byte_size), m_permissions(permissions),
271 m_chunk_size(chunk_size)
272{
273 // The entire address range is free to start with.
274 m_free_blocks.Append(entry: m_range);
275 assert(byte_size > chunk_size);
276}
277
278AllocatedBlock::~AllocatedBlock() = default;
279
280lldb::addr_t AllocatedBlock::ReserveBlock(uint32_t size) {
281 // We must return something valid for zero bytes.
282 if (size == 0)
283 size = 1;
284 Log *log = GetLog(mask: LLDBLog::Process);
285
286 const size_t free_count = m_free_blocks.GetSize();
287 for (size_t i=0; i<free_count; ++i)
288 {
289 auto &free_block = m_free_blocks.GetEntryRef(i);
290 const lldb::addr_t range_size = free_block.GetByteSize();
291 if (range_size >= size)
292 {
293 // We found a free block that is big enough for our data. Figure out how
294 // many chunks we will need and calculate the resulting block size we
295 // will reserve.
296 addr_t addr = free_block.GetRangeBase();
297 size_t num_chunks = CalculateChunksNeededForSize(size);
298 lldb::addr_t block_size = num_chunks * m_chunk_size;
299 lldb::addr_t bytes_left = range_size - block_size;
300 if (bytes_left == 0)
301 {
302 // The newly allocated block will take all of the bytes in this
303 // available block, so we can just add it to the allocated ranges and
304 // remove the range from the free ranges.
305 m_reserved_blocks.Insert(entry: free_block, combine: false);
306 m_free_blocks.RemoveEntryAtIndex(idx: i);
307 }
308 else
309 {
310 // Make the new allocated range and add it to the allocated ranges.
311 Range<lldb::addr_t, uint32_t> reserved_block(free_block);
312 reserved_block.SetByteSize(block_size);
313 // Insert the reserved range and don't combine it with other blocks in
314 // the reserved blocks list.
315 m_reserved_blocks.Insert(entry: reserved_block, combine: false);
316 // Adjust the free range in place since we won't change the sorted
317 // ordering of the m_free_blocks list.
318 free_block.SetRangeBase(reserved_block.GetRangeEnd());
319 free_block.SetByteSize(bytes_left);
320 }
321 LLDB_LOGV(log, "({0}) (size = {1} ({1:x})) => {2:x}", this, size, addr);
322 return addr;
323 }
324 }
325
326 LLDB_LOGV(log, "({0}) (size = {1} ({1:x})) => {2:x}", this, size,
327 LLDB_INVALID_ADDRESS);
328 return LLDB_INVALID_ADDRESS;
329}
330
331bool AllocatedBlock::FreeBlock(addr_t addr) {
332 bool success = false;
333 auto entry_idx = m_reserved_blocks.FindEntryIndexThatContains(addr);
334 if (entry_idx != UINT32_MAX)
335 {
336 m_free_blocks.Insert(entry: m_reserved_blocks.GetEntryRef(i: entry_idx), combine: true);
337 m_reserved_blocks.RemoveEntryAtIndex(idx: entry_idx);
338 success = true;
339 }
340 Log *log = GetLog(mask: LLDBLog::Process);
341 LLDB_LOGV(log, "({0}) (addr = {1:x}) => {2}", this, addr, success);
342 return success;
343}
344
345AllocatedMemoryCache::AllocatedMemoryCache(Process &process)
346 : m_process(process), m_mutex(), m_memory_map() {}
347
348AllocatedMemoryCache::~AllocatedMemoryCache() = default;
349
350void AllocatedMemoryCache::Clear(bool deallocate_memory) {
351 std::lock_guard<std::recursive_mutex> guard(m_mutex);
352 if (m_process.IsAlive() && deallocate_memory) {
353 PermissionsToBlockMap::iterator pos, end = m_memory_map.end();
354 for (pos = m_memory_map.begin(); pos != end; ++pos)
355 m_process.DoDeallocateMemory(ptr: pos->second->GetBaseAddress());
356 }
357 m_memory_map.clear();
358}
359
360AllocatedMemoryCache::AllocatedBlockSP
361AllocatedMemoryCache::AllocatePage(uint32_t byte_size, uint32_t permissions,
362 uint32_t chunk_size, Status &error) {
363 AllocatedBlockSP block_sp;
364 const size_t page_size = 4096;
365 const size_t num_pages = (byte_size + page_size - 1) / page_size;
366 const size_t page_byte_size = num_pages * page_size;
367
368 addr_t addr = m_process.DoAllocateMemory(size: page_byte_size, permissions, error);
369
370 Log *log = GetLog(mask: LLDBLog::Process);
371 if (log) {
372 LLDB_LOGF(log,
373 "Process::DoAllocateMemory (byte_size = 0x%8.8" PRIx32
374 ", permissions = %s) => 0x%16.16" PRIx64,
375 (uint32_t)page_byte_size, GetPermissionsAsCString(permissions),
376 (uint64_t)addr);
377 }
378
379 if (addr != LLDB_INVALID_ADDRESS) {
380 block_sp = std::make_shared<AllocatedBlock>(args&: addr, args: page_byte_size,
381 args&: permissions, args&: chunk_size);
382 m_memory_map.insert(x: std::make_pair(x&: permissions, y&: block_sp));
383 }
384 return block_sp;
385}
386
387lldb::addr_t AllocatedMemoryCache::AllocateMemory(size_t byte_size,
388 uint32_t permissions,
389 Status &error) {
390 std::lock_guard<std::recursive_mutex> guard(m_mutex);
391
392 addr_t addr = LLDB_INVALID_ADDRESS;
393 std::pair<PermissionsToBlockMap::iterator, PermissionsToBlockMap::iterator>
394 range = m_memory_map.equal_range(x: permissions);
395
396 for (PermissionsToBlockMap::iterator pos = range.first; pos != range.second;
397 ++pos) {
398 addr = (*pos).second->ReserveBlock(size: byte_size);
399 if (addr != LLDB_INVALID_ADDRESS)
400 break;
401 }
402
403 if (addr == LLDB_INVALID_ADDRESS) {
404 AllocatedBlockSP block_sp(AllocatePage(byte_size, permissions, chunk_size: 16, error));
405
406 if (block_sp)
407 addr = block_sp->ReserveBlock(size: byte_size);
408 }
409 Log *log = GetLog(mask: LLDBLog::Process);
410 LLDB_LOGF(log,
411 "AllocatedMemoryCache::AllocateMemory (byte_size = 0x%8.8" PRIx32
412 ", permissions = %s) => 0x%16.16" PRIx64,
413 (uint32_t)byte_size, GetPermissionsAsCString(permissions),
414 (uint64_t)addr);
415 return addr;
416}
417
418bool AllocatedMemoryCache::DeallocateMemory(lldb::addr_t addr) {
419 std::lock_guard<std::recursive_mutex> guard(m_mutex);
420
421 PermissionsToBlockMap::iterator pos, end = m_memory_map.end();
422 bool success = false;
423 for (pos = m_memory_map.begin(); pos != end; ++pos) {
424 if (pos->second->Contains(addr)) {
425 success = pos->second->FreeBlock(addr);
426 break;
427 }
428 }
429 Log *log = GetLog(mask: LLDBLog::Process);
430 LLDB_LOGF(log,
431 "AllocatedMemoryCache::DeallocateMemory (addr = 0x%16.16" PRIx64
432 ") => %i",
433 (uint64_t)addr, success);
434 return success;
435}
436
437bool AllocatedMemoryCache::IsInCache(lldb::addr_t addr) const {
438 std::lock_guard<std::recursive_mutex> guard(m_mutex);
439
440 return llvm::any_of(Range: m_memory_map, P: [addr](const auto &block) {
441 return block.second->Contains(addr);
442 });
443}
444

source code of lldb/source/Target/Memory.cpp