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.SetErrorStringWithFormat("memory read failed for 0x%" PRIx64, addr);
168 return 0;
169 }
170
171 // Check the L1 cache for a range that contains the entire memory read.
172 // L1 cache contains chunks of memory that are not required to be the size of
173 // an L2 cache line. We avoid trying to do partial reads from the L1 cache to
174 // simplify the implementation.
175 if (!m_L1_cache.empty()) {
176 AddrRange read_range(addr, dst_len);
177 BlockMap::iterator pos = m_L1_cache.upper_bound(x: addr);
178 if (pos != m_L1_cache.begin()) {
179 --pos;
180 }
181 AddrRange chunk_range(pos->first, pos->second->GetByteSize());
182 if (chunk_range.Contains(range: read_range)) {
183 memcpy(dest: dst, src: pos->second->GetBytes() + (addr - chunk_range.GetRangeBase()),
184 n: dst_len);
185 return dst_len;
186 }
187 }
188
189 // If the size of the read is greater than the size of an L2 cache line, we'll
190 // just read from the inferior. If that read is successful, we'll cache what
191 // we read in the L1 cache for future use.
192 if (dst_len > m_L2_cache_line_byte_size) {
193 size_t bytes_read =
194 m_process.ReadMemoryFromInferior(vm_addr: addr, buf: dst, size: dst_len, error);
195 if (bytes_read > 0)
196 AddL1CacheData(addr, src: dst, src_len: bytes_read);
197 return bytes_read;
198 }
199
200 // If the size of the read fits inside one L2 cache line, we'll try reading
201 // from the L2 cache. Note that if the range of memory we're reading sits
202 // between two contiguous cache lines, we'll touch two cache lines instead of
203 // just one.
204
205 // We're going to have all of our loads and reads be cache line aligned.
206 addr_t cache_line_offset = addr % m_L2_cache_line_byte_size;
207 addr_t cache_line_base_addr = addr - cache_line_offset;
208 DataBufferSP first_cache_line = GetL2CacheLine(line_base_addr: cache_line_base_addr, error);
209 // If we get nothing, then the read to the inferior likely failed. Nothing to
210 // do here.
211 if (!first_cache_line)
212 return 0;
213
214 // If the cache line was not filled out completely and the offset is greater
215 // than what we have available, we can't do anything further here.
216 if (cache_line_offset >= first_cache_line->GetByteSize())
217 return 0;
218
219 uint8_t *dst_buf = (uint8_t *)dst;
220 size_t bytes_left = dst_len;
221 size_t read_size = first_cache_line->GetByteSize() - cache_line_offset;
222 if (read_size > bytes_left)
223 read_size = bytes_left;
224
225 memcpy(dest: dst_buf + dst_len - bytes_left,
226 src: first_cache_line->GetBytes() + cache_line_offset, n: read_size);
227 bytes_left -= read_size;
228
229 // If the cache line was not filled out completely and we still have data to
230 // read, we can't do anything further.
231 if (first_cache_line->GetByteSize() < m_L2_cache_line_byte_size &&
232 bytes_left > 0)
233 return dst_len - bytes_left;
234
235 // We'll hit this scenario if our read straddles two cache lines.
236 if (bytes_left > 0) {
237 cache_line_base_addr += m_L2_cache_line_byte_size;
238
239 // FIXME: Until we are able to more thoroughly check for invalid ranges, we
240 // will have to check the second line to see if it is in an invalid range as
241 // well. See the check near the beginning of the function for more details.
242 if (m_invalid_ranges.FindEntryThatContains(addr: cache_line_base_addr)) {
243 error.SetErrorStringWithFormat("memory read failed for 0x%" PRIx64,
244 cache_line_base_addr);
245 return dst_len - bytes_left;
246 }
247
248 DataBufferSP second_cache_line =
249 GetL2CacheLine(line_base_addr: cache_line_base_addr, error);
250 if (!second_cache_line)
251 return dst_len - bytes_left;
252
253 read_size = bytes_left;
254 if (read_size > second_cache_line->GetByteSize())
255 read_size = second_cache_line->GetByteSize();
256
257 memcpy(dest: dst_buf + dst_len - bytes_left, src: second_cache_line->GetBytes(),
258 n: read_size);
259 bytes_left -= read_size;
260
261 return dst_len - bytes_left;
262 }
263
264 return dst_len;
265}
266
267AllocatedBlock::AllocatedBlock(lldb::addr_t addr, uint32_t byte_size,
268 uint32_t permissions, uint32_t chunk_size)
269 : m_range(addr, byte_size), m_permissions(permissions),
270 m_chunk_size(chunk_size)
271{
272 // The entire address range is free to start with.
273 m_free_blocks.Append(entry: m_range);
274 assert(byte_size > chunk_size);
275}
276
277AllocatedBlock::~AllocatedBlock() = default;
278
279lldb::addr_t AllocatedBlock::ReserveBlock(uint32_t size) {
280 // We must return something valid for zero bytes.
281 if (size == 0)
282 size = 1;
283 Log *log = GetLog(mask: LLDBLog::Process);
284
285 const size_t free_count = m_free_blocks.GetSize();
286 for (size_t i=0; i<free_count; ++i)
287 {
288 auto &free_block = m_free_blocks.GetEntryRef(i);
289 const lldb::addr_t range_size = free_block.GetByteSize();
290 if (range_size >= size)
291 {
292 // We found a free block that is big enough for our data. Figure out how
293 // many chunks we will need and calculate the resulting block size we
294 // will reserve.
295 addr_t addr = free_block.GetRangeBase();
296 size_t num_chunks = CalculateChunksNeededForSize(size);
297 lldb::addr_t block_size = num_chunks * m_chunk_size;
298 lldb::addr_t bytes_left = range_size - block_size;
299 if (bytes_left == 0)
300 {
301 // The newly allocated block will take all of the bytes in this
302 // available block, so we can just add it to the allocated ranges and
303 // remove the range from the free ranges.
304 m_reserved_blocks.Insert(entry: free_block, combine: false);
305 m_free_blocks.RemoveEntryAtIndex(idx: i);
306 }
307 else
308 {
309 // Make the new allocated range and add it to the allocated ranges.
310 Range<lldb::addr_t, uint32_t> reserved_block(free_block);
311 reserved_block.SetByteSize(block_size);
312 // Insert the reserved range and don't combine it with other blocks in
313 // the reserved blocks list.
314 m_reserved_blocks.Insert(entry: reserved_block, combine: false);
315 // Adjust the free range in place since we won't change the sorted
316 // ordering of the m_free_blocks list.
317 free_block.SetRangeBase(reserved_block.GetRangeEnd());
318 free_block.SetByteSize(bytes_left);
319 }
320 LLDB_LOGV(log, "({0}) (size = {1} ({1:x})) => {2:x}", this, size, addr);
321 return addr;
322 }
323 }
324
325 LLDB_LOGV(log, "({0}) (size = {1} ({1:x})) => {2:x}", this, size,
326 LLDB_INVALID_ADDRESS);
327 return LLDB_INVALID_ADDRESS;
328}
329
330bool AllocatedBlock::FreeBlock(addr_t addr) {
331 bool success = false;
332 auto entry_idx = m_reserved_blocks.FindEntryIndexThatContains(addr);
333 if (entry_idx != UINT32_MAX)
334 {
335 m_free_blocks.Insert(entry: m_reserved_blocks.GetEntryRef(i: entry_idx), combine: true);
336 m_reserved_blocks.RemoveEntryAtIndex(idx: entry_idx);
337 success = true;
338 }
339 Log *log = GetLog(mask: LLDBLog::Process);
340 LLDB_LOGV(log, "({0}) (addr = {1:x}) => {2}", this, addr, success);
341 return success;
342}
343
344AllocatedMemoryCache::AllocatedMemoryCache(Process &process)
345 : m_process(process), m_mutex(), m_memory_map() {}
346
347AllocatedMemoryCache::~AllocatedMemoryCache() = default;
348
349void AllocatedMemoryCache::Clear(bool deallocate_memory) {
350 std::lock_guard<std::recursive_mutex> guard(m_mutex);
351 if (m_process.IsAlive() && deallocate_memory) {
352 PermissionsToBlockMap::iterator pos, end = m_memory_map.end();
353 for (pos = m_memory_map.begin(); pos != end; ++pos)
354 m_process.DoDeallocateMemory(ptr: pos->second->GetBaseAddress());
355 }
356 m_memory_map.clear();
357}
358
359AllocatedMemoryCache::AllocatedBlockSP
360AllocatedMemoryCache::AllocatePage(uint32_t byte_size, uint32_t permissions,
361 uint32_t chunk_size, Status &error) {
362 AllocatedBlockSP block_sp;
363 const size_t page_size = 4096;
364 const size_t num_pages = (byte_size + page_size - 1) / page_size;
365 const size_t page_byte_size = num_pages * page_size;
366
367 addr_t addr = m_process.DoAllocateMemory(size: page_byte_size, permissions, error);
368
369 Log *log = GetLog(mask: LLDBLog::Process);
370 if (log) {
371 LLDB_LOGF(log,
372 "Process::DoAllocateMemory (byte_size = 0x%8.8" PRIx32
373 ", permissions = %s) => 0x%16.16" PRIx64,
374 (uint32_t)page_byte_size, GetPermissionsAsCString(permissions),
375 (uint64_t)addr);
376 }
377
378 if (addr != LLDB_INVALID_ADDRESS) {
379 block_sp = std::make_shared<AllocatedBlock>(args&: addr, args: page_byte_size,
380 args&: permissions, args&: chunk_size);
381 m_memory_map.insert(x: std::make_pair(x&: permissions, y&: block_sp));
382 }
383 return block_sp;
384}
385
386lldb::addr_t AllocatedMemoryCache::AllocateMemory(size_t byte_size,
387 uint32_t permissions,
388 Status &error) {
389 std::lock_guard<std::recursive_mutex> guard(m_mutex);
390
391 addr_t addr = LLDB_INVALID_ADDRESS;
392 std::pair<PermissionsToBlockMap::iterator, PermissionsToBlockMap::iterator>
393 range = m_memory_map.equal_range(x: permissions);
394
395 for (PermissionsToBlockMap::iterator pos = range.first; pos != range.second;
396 ++pos) {
397 addr = (*pos).second->ReserveBlock(size: byte_size);
398 if (addr != LLDB_INVALID_ADDRESS)
399 break;
400 }
401
402 if (addr == LLDB_INVALID_ADDRESS) {
403 AllocatedBlockSP block_sp(AllocatePage(byte_size, permissions, chunk_size: 16, error));
404
405 if (block_sp)
406 addr = block_sp->ReserveBlock(size: byte_size);
407 }
408 Log *log = GetLog(mask: LLDBLog::Process);
409 LLDB_LOGF(log,
410 "AllocatedMemoryCache::AllocateMemory (byte_size = 0x%8.8" PRIx32
411 ", permissions = %s) => 0x%16.16" PRIx64,
412 (uint32_t)byte_size, GetPermissionsAsCString(permissions),
413 (uint64_t)addr);
414 return addr;
415}
416
417bool AllocatedMemoryCache::DeallocateMemory(lldb::addr_t addr) {
418 std::lock_guard<std::recursive_mutex> guard(m_mutex);
419
420 PermissionsToBlockMap::iterator pos, end = m_memory_map.end();
421 bool success = false;
422 for (pos = m_memory_map.begin(); pos != end; ++pos) {
423 if (pos->second->Contains(addr)) {
424 success = pos->second->FreeBlock(addr);
425 break;
426 }
427 }
428 Log *log = GetLog(mask: LLDBLog::Process);
429 LLDB_LOGF(log,
430 "AllocatedMemoryCache::DeallocateMemory (addr = 0x%16.16" PRIx64
431 ") => %i",
432 (uint64_t)addr, success);
433 return success;
434}
435

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