contrib/llvm/tools/lldb/source/Target/Memory.cpp

   1 //===-- Memory.cpp ----------------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "lldb/Target/Memory.h"
  11 #include <inttypes.h>
  12 #include "lldb/Core/RangeMap.h"
  13 #include "lldb/Target/Process.h"
  14 #include "lldb/Utility/DataBufferHeap.h"
  15 #include "lldb/Utility/Log.h"
  16 #include "lldb/Utility/State.h"
  17
  18 using namespace lldb;
  19 using namespace lldb_private;
  20
  21 //----------------------------------------------------------------------
  22 // MemoryCache constructor
  23 //----------------------------------------------------------------------
  24 MemoryCache::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 //----------------------------------------------------------------------
  30 // Destructor
  31 //----------------------------------------------------------------------
  32 MemoryCache::~MemoryCache() {}
  33
  34 void MemoryCache::Clear(bool clear_invalid_ranges) {
  35   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  36   m_L1_cache.clear();
  37   m_L2_cache.clear();
  38   if (clear_invalid_ranges)
  39     m_invalid_ranges.Clear();
  40   m_L2_cache_line_byte_size = m_process.GetMemoryCacheLineSize();
  41 }
  42
  43 void MemoryCache::AddL1CacheData(lldb::addr_t addr, const void *src,
  44                                  size_t src_len) {
  45   AddL1CacheData(
  46       addr, DataBufferSP(new DataBufferHeap(DataBufferHeap(src, src_len))));
  47 }
  48
  49 void MemoryCache::AddL1CacheData(lldb::addr_t addr,
  50                                  const DataBufferSP &data_buffer_sp) {
  51   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  52   m_L1_cache[addr] = data_buffer_sp;
  53 }
  54
  55 void MemoryCache::Flush(addr_t addr, size_t size) {
  56   if (size == 0)
  57     return;
  58
  59   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  60
  61   // Erase any blocks from the L1 cache that intersect with the flush range
  62   if (!m_L1_cache.empty()) {
  63     AddrRange flush_range(addr, size);
  64     BlockMap::iterator pos = m_L1_cache.upper_bound(addr);
  65     if (pos != m_L1_cache.begin()) {
  66       --pos;
  67     }
  68     while (pos != m_L1_cache.end()) {
  69       AddrRange chunk_range(pos->first, pos->second->GetByteSize());
  70       if (!chunk_range.DoesIntersect(flush_range))
  71         break;
  72       pos = m_L1_cache.erase(pos);
  73     }
  74   }
  75
  76   if (!m_L2_cache.empty()) {
  77     const uint32_t cache_line_byte_size = m_L2_cache_line_byte_size;
  78     const addr_t end_addr = (addr + size - 1);
  79     const addr_t first_cache_line_addr = addr - (addr % cache_line_byte_size);
  80     const addr_t last_cache_line_addr =
  81         end_addr - (end_addr % cache_line_byte_size);
  82     // Watch for overflow where size will cause us to go off the end of the
  83     // 64 bit address space
  84     uint32_t num_cache_lines;
  85     if (last_cache_line_addr >= first_cache_line_addr)
  86       num_cache_lines = ((last_cache_line_addr - first_cache_line_addr) /
  87                          cache_line_byte_size) +
  88                         1;
  89     else
  90       num_cache_lines =
  91           (UINT64_MAX - first_cache_line_addr + 1) / cache_line_byte_size;
  92
  93     uint32_t cache_idx = 0;
  94     for (addr_t curr_addr = first_cache_line_addr; cache_idx < num_cache_lines;
  95          curr_addr += cache_line_byte_size, ++cache_idx) {
  96       BlockMap::iterator pos = m_L2_cache.find(curr_addr);
  97       if (pos != m_L2_cache.end())
  98         m_L2_cache.erase(pos);
  99     }
 100   }
 101 }
 102
 103 void MemoryCache::AddInvalidRange(lldb::addr_t base_addr,
 104                                   lldb::addr_t byte_size) {
 105   if (byte_size > 0) {
 106     std::lock_guard<std::recursive_mutex> guard(m_mutex);
 107     InvalidRanges::Entry range(base_addr, byte_size);
 108     m_invalid_ranges.Append(range);
 109     m_invalid_ranges.Sort();
 110   }
 111 }
 112
 113 bool MemoryCache::RemoveInvalidRange(lldb::addr_t base_addr,
 114                                      lldb::addr_t byte_size) {
 115   if (byte_size > 0) {
 116     std::lock_guard<std::recursive_mutex> guard(m_mutex);
 117     const uint32_t idx = m_invalid_ranges.FindEntryIndexThatContains(base_addr);
 118     if (idx != UINT32_MAX) {
 119       const InvalidRanges::Entry *entry = m_invalid_ranges.GetEntryAtIndex(idx);
 120       if (entry->GetRangeBase() == base_addr &&
 121           entry->GetByteSize() == byte_size)
 122         return m_invalid_ranges.RemoveEntrtAtIndex(idx);
 123     }
 124   }
 125   return false;
 126 }
 127
 128 size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len,
 129                          Status &error) {
 130   size_t bytes_left = dst_len;
 131
 132   // Check the L1 cache for a range that contain the entire memory read. If we
 133   // find a range in the L1 cache that does, we use it. Else we fall back to
 134   // reading memory in m_L2_cache_line_byte_size byte sized chunks. The L1
 135   // cache contains chunks of memory that are not required to be
 136   // m_L2_cache_line_byte_size bytes in size, so we don't try anything tricky
 137   // when reading from them (no partial reads from the L1 cache).
 138
 139   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 140   if (!m_L1_cache.empty()) {
 141     AddrRange read_range(addr, dst_len);
 142     BlockMap::iterator pos = m_L1_cache.upper_bound(addr);
 143     if (pos != m_L1_cache.begin()) {
 144       --pos;
 145     }
 146     AddrRange chunk_range(pos->first, pos->second->GetByteSize());
 147     if (chunk_range.Contains(read_range)) {
 148       memcpy(dst, pos->second->GetBytes() + addr - chunk_range.GetRangeBase(),
 149              dst_len);
 150       return dst_len;
 151     }
 152   }
 153
 154   // If this memory read request is larger than the cache line size, then we
 155   // (1) try to read as much of it at once as possible, and (2) don't add the
 156   // data to the memory cache.  We don't want to split a big read up into more
 157   // separate reads than necessary, and with a large memory read request, it is
 158   // unlikely that the caller function will ask for the next
 159   // 4 bytes after the large memory read - so there's little benefit to saving
 160   // it in the cache.
 161   if (dst && dst_len > m_L2_cache_line_byte_size) {
 162     size_t bytes_read =
 163         m_process.ReadMemoryFromInferior(addr, dst, dst_len, error);
 164     // Add this non block sized range to the L1 cache if we actually read
 165     // anything
 166     if (bytes_read > 0)
 167       AddL1CacheData(addr, dst, bytes_read);
 168     return bytes_read;
 169   }
 170
 171   if (dst && bytes_left > 0) {
 172     const uint32_t cache_line_byte_size = m_L2_cache_line_byte_size;
 173     uint8_t *dst_buf = (uint8_t *)dst;
 174     addr_t curr_addr = addr - (addr % cache_line_byte_size);
 175     addr_t cache_offset = addr - curr_addr;
 176
 177     while (bytes_left > 0) {
 178       if (m_invalid_ranges.FindEntryThatContains(curr_addr)) {
 179         error.SetErrorStringWithFormat("memory read failed for 0x%" PRIx64,
 180                                        curr_addr);
 181         return dst_len - bytes_left;
 182       }
 183
 184       BlockMap::const_iterator pos = m_L2_cache.find(curr_addr);
 185       BlockMap::const_iterator end = m_L2_cache.end();
 186
 187       if (pos != end) {
 188         size_t curr_read_size = cache_line_byte_size - cache_offset;
 189         if (curr_read_size > bytes_left)
 190           curr_read_size = bytes_left;
 191
 192         memcpy(dst_buf + dst_len - bytes_left,
 193                pos->second->GetBytes() + cache_offset, curr_read_size);
 194
 195         bytes_left -= curr_read_size;
 196         curr_addr += curr_read_size + cache_offset;
 197         cache_offset = 0;
 198
 199         if (bytes_left > 0) {
 200           // Get sequential cache page hits
 201           for (++pos; (pos != end) && (bytes_left > 0); ++pos) {
 202             assert((curr_addr % cache_line_byte_size) == 0);
 203
 204             if (pos->first != curr_addr)
 205               break;
 206
 207             curr_read_size = pos->second->GetByteSize();
 208             if (curr_read_size > bytes_left)
 209               curr_read_size = bytes_left;
 210
 211             memcpy(dst_buf + dst_len - bytes_left, pos->second->GetBytes(),
 212                    curr_read_size);
 213
 214             bytes_left -= curr_read_size;
 215             curr_addr += curr_read_size;
 216
 217             // We have a cache page that succeeded to read some bytes but not
 218             // an entire page. If this happens, we must cap off how much data
 219             // we are able to read...
 220             if (pos->second->GetByteSize() != cache_line_byte_size)
 221               return dst_len - bytes_left;
 222           }
 223         }
 224       }
 225
 226       // We need to read from the process
 227
 228       if (bytes_left > 0) {
 229         assert((curr_addr % cache_line_byte_size) == 0);
 230         std::unique_ptr<DataBufferHeap> data_buffer_heap_ap(
 231             new DataBufferHeap(cache_line_byte_size, 0));
 232         size_t process_bytes_read = m_process.ReadMemoryFromInferior(
 233             curr_addr, data_buffer_heap_ap->GetBytes(),
 234             data_buffer_heap_ap->GetByteSize(), error);
 235         if (process_bytes_read == 0)
 236           return dst_len - bytes_left;
 237
 238         if (process_bytes_read != cache_line_byte_size)
 239           data_buffer_heap_ap->SetByteSize(process_bytes_read);
 240         m_L2_cache[curr_addr] = DataBufferSP(data_buffer_heap_ap.release());
 241         // We have read data and put it into the cache, continue through the
 242         // loop again to get the data out of the cache...
 243       }
 244     }
 245   }
 246
 247   return dst_len - bytes_left;
 248 }
 249
 250 AllocatedBlock::AllocatedBlock(lldb::addr_t addr, uint32_t byte_size,
 251                                uint32_t permissions, uint32_t chunk_size)
 252     : m_range(addr, byte_size), m_permissions(permissions),
 253       m_chunk_size(chunk_size)
 254 {
 255   // The entire address range is free to start with.
 256   m_free_blocks.Append(m_range);
 257   assert(byte_size > chunk_size);
 258 }
 259
 260 AllocatedBlock::~AllocatedBlock() {}
 261
 262 lldb::addr_t AllocatedBlock::ReserveBlock(uint32_t size) {
 263   // We must return something valid for zero bytes.
 264   if (size == 0)
 265     size = 1;
 266   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
 267
 268   const size_t free_count = m_free_blocks.GetSize();
 269   for (size_t i=0; i<free_count; ++i)
 270   {
 271     auto &free_block = m_free_blocks.GetEntryRef(i);
 272     const lldb::addr_t range_size = free_block.GetByteSize();
 273     if (range_size >= size)
 274     {
 275       // We found a free block that is big enough for our data. Figure out how
 276       // many chunks we will need and calculate the resulting block size we
 277       // will reserve.
 278       addr_t addr = free_block.GetRangeBase();
 279       size_t num_chunks = CalculateChunksNeededForSize(size);
 280       lldb::addr_t block_size = num_chunks * m_chunk_size;
 281       lldb::addr_t bytes_left = range_size - block_size;
 282       if (bytes_left == 0)
 283       {
 284         // The newly allocated block will take all of the bytes in this
 285         // available block, so we can just add it to the allocated ranges and
 286         // remove the range from the free ranges.
 287         m_reserved_blocks.Insert(free_block, false);
 288         m_free_blocks.RemoveEntryAtIndex(i);
 289       }
 290       else
 291       {
 292         // Make the new allocated range and add it to the allocated ranges.
 293         Range<lldb::addr_t, uint32_t> reserved_block(free_block);
 294         reserved_block.SetByteSize(block_size);
 295         // Insert the reserved range and don't combine it with other blocks in
 296         // the reserved blocks list.
 297         m_reserved_blocks.Insert(reserved_block, false);
 298         // Adjust the free range in place since we won't change the sorted
 299         // ordering of the m_free_blocks list.
 300         free_block.SetRangeBase(reserved_block.GetRangeEnd());
 301         free_block.SetByteSize(bytes_left);
 302       }
 303       LLDB_LOGV(log, "({0}) (size = {1} ({1:x})) => {2:x}", this, size, addr);
 304       return addr;
 305     }
 306   }
 307
 308   LLDB_LOGV(log, "({0}) (size = {1} ({1:x})) => {2:x}", this, size,
 309             LLDB_INVALID_ADDRESS);
 310   return LLDB_INVALID_ADDRESS;
 311 }
 312
 313 bool AllocatedBlock::FreeBlock(addr_t addr) {
 314   bool success = false;
 315   auto entry_idx = m_reserved_blocks.FindEntryIndexThatContains(addr);
 316   if (entry_idx != UINT32_MAX)
 317   {
 318     m_free_blocks.Insert(m_reserved_blocks.GetEntryRef(entry_idx), true);
 319     m_reserved_blocks.RemoveEntryAtIndex(entry_idx);
 320     success = true;
 321   }
 322   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
 323   LLDB_LOGV(log, "({0}) (addr = {1:x}) => {2}", this, addr, success);
 324   return success;
 325 }
 326
 327 AllocatedMemoryCache::AllocatedMemoryCache(Process &process)
 328     : m_process(process), m_mutex(), m_memory_map() {}
 329
 330 AllocatedMemoryCache::~AllocatedMemoryCache() {}
 331
 332 void AllocatedMemoryCache::Clear() {
 333   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 334   if (m_process.IsAlive()) {
 335     PermissionsToBlockMap::iterator pos, end = m_memory_map.end();
 336     for (pos = m_memory_map.begin(); pos != end; ++pos)
 337       m_process.DoDeallocateMemory(pos->second->GetBaseAddress());
 338   }
 339   m_memory_map.clear();
 340 }
 341
 342 AllocatedMemoryCache::AllocatedBlockSP
 343 AllocatedMemoryCache::AllocatePage(uint32_t byte_size, uint32_t permissions,
 344                                    uint32_t chunk_size, Status &error) {
 345   AllocatedBlockSP block_sp;
 346   const size_t page_size = 4096;
 347   const size_t num_pages = (byte_size + page_size - 1) / page_size;
 348   const size_t page_byte_size = num_pages * page_size;
 349
 350   addr_t addr = m_process.DoAllocateMemory(page_byte_size, permissions, error);
 351
 352   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
 353   if (log) {
 354     log->Printf("Process::DoAllocateMemory (byte_size = 0x%8.8" PRIx32
 355                 ", permissions = %s) => 0x%16.16" PRIx64,
 356                 (uint32_t)page_byte_size, GetPermissionsAsCString(permissions),
 357                 (uint64_t)addr);
 358   }
 359
 360   if (addr != LLDB_INVALID_ADDRESS) {
 361     block_sp.reset(
 362         new AllocatedBlock(addr, page_byte_size, permissions, chunk_size));
 363     m_memory_map.insert(std::make_pair(permissions, block_sp));
 364   }
 365   return block_sp;
 366 }
 367
 368 lldb::addr_t AllocatedMemoryCache::AllocateMemory(size_t byte_size,
 369                                                   uint32_t permissions,
 370                                                   Status &error) {
 371   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 372
 373   addr_t addr = LLDB_INVALID_ADDRESS;
 374   std::pair<PermissionsToBlockMap::iterator, PermissionsToBlockMap::iterator>
 375       range = m_memory_map.equal_range(permissions);
 376
 377   for (PermissionsToBlockMap::iterator pos = range.first; pos != range.second;
 378        ++pos) {
 379     addr = (*pos).second->ReserveBlock(byte_size);
 380     if (addr != LLDB_INVALID_ADDRESS)
 381       break;
 382   }
 383
 384   if (addr == LLDB_INVALID_ADDRESS) {
 385     AllocatedBlockSP block_sp(AllocatePage(byte_size, permissions, 16, error));
 386
 387     if (block_sp)
 388       addr = block_sp->ReserveBlock(byte_size);
 389   }
 390   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
 391   if (log)
 392     log->Printf(
 393         "AllocatedMemoryCache::AllocateMemory (byte_size = 0x%8.8" PRIx32
 394         ", permissions = %s) => 0x%16.16" PRIx64,
 395         (uint32_t)byte_size, GetPermissionsAsCString(permissions),
 396         (uint64_t)addr);
 397   return addr;
 398 }
 399
 400 bool AllocatedMemoryCache::DeallocateMemory(lldb::addr_t addr) {
 401   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 402
 403   PermissionsToBlockMap::iterator pos, end = m_memory_map.end();
 404   bool success = false;
 405   for (pos = m_memory_map.begin(); pos != end; ++pos) {
 406     if (pos->second->Contains(addr)) {
 407       success = pos->second->FreeBlock(addr);
 408       break;
 409     }
 410   }
 411   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
 412   if (log)
 413     log->Printf("AllocatedMemoryCache::DeallocateMemory (addr = 0x%16.16" PRIx64
 414                 ") => %i",
 415                 (uint64_t)addr, success);
 416   return success;
 417 }