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 // C Includes
  12 #include <inttypes.h>
  13 // C++ Includes
  14 // Other libraries and framework includes
  15 // Project includes
  16 #include "lldb/Core/DataBufferHeap.h"
  17 #include "lldb/Core/Log.h"
  18 #include "lldb/Core/RangeMap.h"
  19 #include "lldb/Core/State.h"
  20 #include "lldb/Target/Process.h"
  21
  22 using namespace lldb;
  23 using namespace lldb_private;
  24
  25 //----------------------------------------------------------------------
  26 // MemoryCache constructor
  27 //----------------------------------------------------------------------
  28 MemoryCache::MemoryCache(Process &process)
  29     : m_mutex(), m_L1_cache(), m_L2_cache(), m_invalid_ranges(),
  30       m_process(process),
  31       m_L2_cache_line_byte_size(process.GetMemoryCacheLineSize()) {}
  32
  33 //----------------------------------------------------------------------
  34 // Destructor
  35 //----------------------------------------------------------------------
  36 MemoryCache::~MemoryCache() {}
  37
  38 void MemoryCache::Clear(bool clear_invalid_ranges) {
  39   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  40   m_L1_cache.clear();
  41   m_L2_cache.clear();
  42   if (clear_invalid_ranges)
  43     m_invalid_ranges.Clear();
  44   m_L2_cache_line_byte_size = m_process.GetMemoryCacheLineSize();
  45 }
  46
  47 void MemoryCache::AddL1CacheData(lldb::addr_t addr, const void *src,
  48                                  size_t src_len) {
  49   AddL1CacheData(
  50       addr, DataBufferSP(new DataBufferHeap(DataBufferHeap(src, src_len))));
  51 }
  52
  53 void MemoryCache::AddL1CacheData(lldb::addr_t addr,
  54                                  const DataBufferSP &data_buffer_sp) {
  55   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  56   m_L1_cache[addr] = data_buffer_sp;
  57 }
  58
  59 void MemoryCache::Flush(addr_t addr, size_t size) {
  60   if (size == 0)
  61     return;
  62
  63   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  64
  65   // Erase any blocks from the L1 cache that intersect with the flush range
  66   if (!m_L1_cache.empty()) {
  67     AddrRange flush_range(addr, size);
  68     BlockMap::iterator pos = m_L1_cache.upper_bound(addr);
  69     if (pos != m_L1_cache.begin()) {
  70       --pos;
  71     }
  72     while (pos != m_L1_cache.end()) {
  73       AddrRange chunk_range(pos->first, pos->second->GetByteSize());
  74       if (!chunk_range.DoesIntersect(flush_range))
  75         break;
  76       pos = m_L1_cache.erase(pos);
  77     }
  78   }
  79
  80   if (!m_L2_cache.empty()) {
  81     const uint32_t cache_line_byte_size = m_L2_cache_line_byte_size;
  82     const addr_t end_addr = (addr + size - 1);
  83     const addr_t first_cache_line_addr = addr - (addr % cache_line_byte_size);
  84     const addr_t last_cache_line_addr =
  85         end_addr - (end_addr % cache_line_byte_size);
  86     // Watch for overflow where size will cause us to go off the end of the
  87     // 64 bit address space
  88     uint32_t num_cache_lines;
  89     if (last_cache_line_addr >= first_cache_line_addr)
  90       num_cache_lines = ((last_cache_line_addr - first_cache_line_addr) /
  91                          cache_line_byte_size) +
  92                         1;
  93     else
  94       num_cache_lines =
  95           (UINT64_MAX - first_cache_line_addr + 1) / cache_line_byte_size;
  96
  97     uint32_t cache_idx = 0;
  98     for (addr_t curr_addr = first_cache_line_addr; cache_idx < num_cache_lines;
  99          curr_addr += cache_line_byte_size, ++cache_idx) {
 100       BlockMap::iterator pos = m_L2_cache.find(curr_addr);
 101       if (pos != m_L2_cache.end())
 102         m_L2_cache.erase(pos);
 103     }
 104   }
 105 }
 106
 107 void MemoryCache::AddInvalidRange(lldb::addr_t base_addr,
 108                                   lldb::addr_t byte_size) {
 109   if (byte_size > 0) {
 110     std::lock_guard<std::recursive_mutex> guard(m_mutex);
 111     InvalidRanges::Entry range(base_addr, byte_size);
 112     m_invalid_ranges.Append(range);
 113     m_invalid_ranges.Sort();
 114   }
 115 }
 116
 117 bool MemoryCache::RemoveInvalidRange(lldb::addr_t base_addr,
 118                                      lldb::addr_t byte_size) {
 119   if (byte_size > 0) {
 120     std::lock_guard<std::recursive_mutex> guard(m_mutex);
 121     const uint32_t idx = m_invalid_ranges.FindEntryIndexThatContains(base_addr);
 122     if (idx != UINT32_MAX) {
 123       const InvalidRanges::Entry *entry = m_invalid_ranges.GetEntryAtIndex(idx);
 124       if (entry->GetRangeBase() == base_addr &&
 125           entry->GetByteSize() == byte_size)
 126         return m_invalid_ranges.RemoveEntrtAtIndex(idx);
 127     }
 128   }
 129   return false;
 130 }
 131
 132 size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len, Error &error) {
 133   size_t bytes_left = dst_len;
 134
 135   // Check the L1 cache for a range that contain the entire memory read.
 136   // If we find a range in the L1 cache that does, we use it. Else we fall
 137   // back to reading memory in m_L2_cache_line_byte_size byte sized chunks.
 138   // The L1 cache contains chunks of memory that are not required to be
 139   // m_L2_cache_line_byte_size bytes in size, so we don't try anything
 140   // tricky when reading from them (no partial reads from the L1 cache).
 141
 142   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 143   if (!m_L1_cache.empty()) {
 144     AddrRange read_range(addr, dst_len);
 145     BlockMap::iterator pos = m_L1_cache.upper_bound(addr);
 146     if (pos != m_L1_cache.begin()) {
 147       --pos;
 148     }
 149     AddrRange chunk_range(pos->first, pos->second->GetByteSize());
 150     if (chunk_range.Contains(read_range)) {
 151       memcpy(dst, pos->second->GetBytes() + addr - chunk_range.GetRangeBase(),
 152              dst_len);
 153       return dst_len;
 154     }
 155   }
 156
 157   // If this memory read request is larger than the cache line size, then
 158   // we (1) try to read as much of it at once as possible, and (2) don't
 159   // add the data to the memory cache.  We don't want to split a big read
 160   // up into more separate reads than necessary, and with a large memory read
 161   // request, it is unlikely that the caller function will ask for the next
 162   // 4 bytes after the large memory read - so there's little benefit to saving
 163   // it in the cache.
 164   if (dst && dst_len > m_L2_cache_line_byte_size) {
 165     size_t bytes_read =
 166         m_process.ReadMemoryFromInferior(addr, dst, dst_len, error);
 167     // Add this non block sized range to the L1 cache if we actually read
 168     // anything
 169     if (bytes_read > 0)
 170       AddL1CacheData(addr, dst, bytes_read);
 171     return bytes_read;
 172   }
 173
 174   if (dst && bytes_left > 0) {
 175     const uint32_t cache_line_byte_size = m_L2_cache_line_byte_size;
 176     uint8_t *dst_buf = (uint8_t *)dst;
 177     addr_t curr_addr = addr - (addr % cache_line_byte_size);
 178     addr_t cache_offset = addr - curr_addr;
 179
 180     while (bytes_left > 0) {
 181       if (m_invalid_ranges.FindEntryThatContains(curr_addr)) {
 182         error.SetErrorStringWithFormat("memory read failed for 0x%" PRIx64,
 183                                        curr_addr);
 184         return dst_len - bytes_left;
 185       }
 186
 187       BlockMap::const_iterator pos = m_L2_cache.find(curr_addr);
 188       BlockMap::const_iterator end = m_L2_cache.end();
 189
 190       if (pos != end) {
 191         size_t curr_read_size = cache_line_byte_size - cache_offset;
 192         if (curr_read_size > bytes_left)
 193           curr_read_size = bytes_left;
 194
 195         memcpy(dst_buf + dst_len - bytes_left,
 196                pos->second->GetBytes() + cache_offset, curr_read_size);
 197
 198         bytes_left -= curr_read_size;
 199         curr_addr += curr_read_size + cache_offset;
 200         cache_offset = 0;
 201
 202         if (bytes_left > 0) {
 203           // Get sequential cache page hits
 204           for (++pos; (pos != end) && (bytes_left > 0); ++pos) {
 205             assert((curr_addr % cache_line_byte_size) == 0);
 206
 207             if (pos->first != curr_addr)
 208               break;
 209
 210             curr_read_size = pos->second->GetByteSize();
 211             if (curr_read_size > bytes_left)
 212               curr_read_size = bytes_left;
 213
 214             memcpy(dst_buf + dst_len - bytes_left, pos->second->GetBytes(),
 215                    curr_read_size);
 216
 217             bytes_left -= curr_read_size;
 218             curr_addr += curr_read_size;
 219
 220             // We have a cache page that succeeded to read some bytes
 221             // but not an entire page. If this happens, we must cap
 222             // off how much data we are able to read...
 223             if (pos->second->GetByteSize() != cache_line_byte_size)
 224               return dst_len - bytes_left;
 225           }
 226         }
 227       }
 228
 229       // We need to read from the process
 230
 231       if (bytes_left > 0) {
 232         assert((curr_addr % cache_line_byte_size) == 0);
 233         std::unique_ptr<DataBufferHeap> data_buffer_heap_ap(
 234             new DataBufferHeap(cache_line_byte_size, 0));
 235         size_t process_bytes_read = m_process.ReadMemoryFromInferior(
 236             curr_addr, data_buffer_heap_ap->GetBytes(),
 237             data_buffer_heap_ap->GetByteSize(), error);
 238         if (process_bytes_read == 0)
 239           return dst_len - bytes_left;
 240
 241         if (process_bytes_read != cache_line_byte_size)
 242           data_buffer_heap_ap->SetByteSize(process_bytes_read);
 243         m_L2_cache[curr_addr] = DataBufferSP(data_buffer_heap_ap.release());
 244         // We have read data and put it into the cache, continue through the
 245         // loop again to get the data out of the cache...
 246       }
 247     }
 248   }
 249
 250   return dst_len - bytes_left;
 251 }
 252
 253 AllocatedBlock::AllocatedBlock(lldb::addr_t addr, uint32_t byte_size,
 254                                uint32_t permissions, uint32_t chunk_size)
 255     : m_addr(addr), m_byte_size(byte_size), m_permissions(permissions),
 256       m_chunk_size(chunk_size), m_offset_to_chunk_size()
 257 //    m_allocated (byte_size / chunk_size)
 258 {
 259   assert(byte_size > chunk_size);
 260 }
 261
 262 AllocatedBlock::~AllocatedBlock() {}
 263
 264 lldb::addr_t AllocatedBlock::ReserveBlock(uint32_t size) {
 265   addr_t addr = LLDB_INVALID_ADDRESS;
 266   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS | LIBLLDB_LOG_VERBOSE));
 267   if (size <= m_byte_size) {
 268     const uint32_t needed_chunks = CalculateChunksNeededForSize(size);
 269
 270     if (m_offset_to_chunk_size.empty()) {
 271       m_offset_to_chunk_size[0] = needed_chunks;
 272       if (log)
 273         log->Printf("[1] AllocatedBlock::ReserveBlock(%p) (size = %u (0x%x)) "
 274                     "=> offset = 0x%x, %u %u bit chunks",
 275                     (void *)this, size, size, 0, needed_chunks, m_chunk_size);
 276       addr = m_addr;
 277     } else {
 278       uint32_t last_offset = 0;
 279       OffsetToChunkSize::const_iterator pos = m_offset_to_chunk_size.begin();
 280       OffsetToChunkSize::const_iterator end = m_offset_to_chunk_size.end();
 281       while (pos != end) {
 282         if (pos->first > last_offset) {
 283           const uint32_t bytes_available = pos->first - last_offset;
 284           const uint32_t num_chunks =
 285               CalculateChunksNeededForSize(bytes_available);
 286           if (num_chunks >= needed_chunks) {
 287             m_offset_to_chunk_size[last_offset] = needed_chunks;
 288             if (log)
 289               log->Printf("[2] AllocatedBlock::ReserveBlock(%p) (size = %u "
 290                           "(0x%x)) => offset = 0x%x, %u %u bit chunks - "
 291                           "num_chunks %zu",
 292                           (void *)this, size, size, last_offset, needed_chunks,
 293                           m_chunk_size, m_offset_to_chunk_size.size());
 294             addr = m_addr + last_offset;
 295             break;
 296           }
 297         }
 298
 299         last_offset = pos->first + pos->second * m_chunk_size;
 300
 301         if (++pos == end) {
 302           // Last entry...
 303           const uint32_t chunks_left =
 304               CalculateChunksNeededForSize(m_byte_size - last_offset);
 305           if (chunks_left >= needed_chunks) {
 306             m_offset_to_chunk_size[last_offset] = needed_chunks;
 307             if (log)
 308               log->Printf("[3] AllocatedBlock::ReserveBlock(%p) (size = %u "
 309                           "(0x%x)) => offset = 0x%x, %u %u bit chunks - "
 310                           "num_chunks %zu",
 311                           (void *)this, size, size, last_offset, needed_chunks,
 312                           m_chunk_size, m_offset_to_chunk_size.size());
 313             addr = m_addr + last_offset;
 314             break;
 315           }
 316         }
 317       }
 318     }
 319     //        const uint32_t total_chunks = m_allocated.size ();
 320     //        uint32_t unallocated_idx = 0;
 321     //        uint32_t allocated_idx = m_allocated.find_first();
 322     //        uint32_t first_chunk_idx = UINT32_MAX;
 323     //        uint32_t num_chunks;
 324     //        while (1)
 325     //        {
 326     //            if (allocated_idx == UINT32_MAX)
 327     //            {
 328     //                // No more bits are set starting from unallocated_idx, so
 329     //                we
 330     //                // either have enough chunks for the request, or we don't.
 331     //                // Either way we break out of the while loop...
 332     //                num_chunks = total_chunks - unallocated_idx;
 333     //                if (needed_chunks <= num_chunks)
 334     //                    first_chunk_idx = unallocated_idx;
 335     //                break;
 336     //            }
 337     //            else if (allocated_idx > unallocated_idx)
 338     //            {
 339     //                // We have some allocated chunks, check if there are
 340     //                enough
 341     //                // free chunks to satisfy the request?
 342     //                num_chunks = allocated_idx - unallocated_idx;
 343     //                if (needed_chunks <= num_chunks)
 344     //                {
 345     //                    // Yep, we have enough!
 346     //                    first_chunk_idx = unallocated_idx;
 347     //                    break;
 348     //                }
 349     //            }
 350     //
 351     //            while (unallocated_idx < total_chunks)
 352     //            {
 353     //                if (m_allocated[unallocated_idx])
 354     //                    ++unallocated_idx;
 355     //                else
 356     //                    break;
 357     //            }
 358     //
 359     //            if (unallocated_idx >= total_chunks)
 360     //                break;
 361     //
 362     //            allocated_idx = m_allocated.find_next(unallocated_idx);
 363     //        }
 364     //
 365     //        if (first_chunk_idx != UINT32_MAX)
 366     //        {
 367     //            const uint32_t end_bit_idx = unallocated_idx + needed_chunks;
 368     //            for (uint32_t idx = first_chunk_idx; idx < end_bit_idx; ++idx)
 369     //                m_allocated.set(idx);
 370     //            return m_addr + m_chunk_size * first_chunk_idx;
 371     //        }
 372   }
 373
 374   if (log)
 375     log->Printf("AllocatedBlock::ReserveBlock(%p) (size = %u (0x%x)) => "
 376                 "0x%16.16" PRIx64,
 377                 (void *)this, size, size, (uint64_t)addr);
 378   return addr;
 379 }
 380
 381 bool AllocatedBlock::FreeBlock(addr_t addr) {
 382   uint32_t offset = addr - m_addr;
 383   OffsetToChunkSize::iterator pos = m_offset_to_chunk_size.find(offset);
 384   bool success = false;
 385   if (pos != m_offset_to_chunk_size.end()) {
 386     m_offset_to_chunk_size.erase(pos);
 387     success = true;
 388   }
 389   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS | LIBLLDB_LOG_VERBOSE));
 390   if (log)
 391     log->Printf("AllocatedBlock::FreeBlock(%p) (addr = 0x%16.16" PRIx64
 392                 ") => %i, num_chunks: %zu",
 393                 (void *)this, (uint64_t)addr, success,
 394                 m_offset_to_chunk_size.size());
 395   return success;
 396 }
 397
 398 AllocatedMemoryCache::AllocatedMemoryCache(Process &process)
 399     : m_process(process), m_mutex(), m_memory_map() {}
 400
 401 AllocatedMemoryCache::~AllocatedMemoryCache() {}
 402
 403 void AllocatedMemoryCache::Clear() {
 404   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 405   if (m_process.IsAlive()) {
 406     PermissionsToBlockMap::iterator pos, end = m_memory_map.end();
 407     for (pos = m_memory_map.begin(); pos != end; ++pos)
 408       m_process.DoDeallocateMemory(pos->second->GetBaseAddress());
 409   }
 410   m_memory_map.clear();
 411 }
 412
 413 AllocatedMemoryCache::AllocatedBlockSP
 414 AllocatedMemoryCache::AllocatePage(uint32_t byte_size, uint32_t permissions,
 415                                    uint32_t chunk_size, Error &error) {
 416   AllocatedBlockSP block_sp;
 417   const size_t page_size = 4096;
 418   const size_t num_pages = (byte_size + page_size - 1) / page_size;
 419   const size_t page_byte_size = num_pages * page_size;
 420
 421   addr_t addr = m_process.DoAllocateMemory(page_byte_size, permissions, error);
 422
 423   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
 424   if (log) {
 425     log->Printf("Process::DoAllocateMemory (byte_size = 0x%8.8" PRIx32
 426                 ", permissions = %s) => 0x%16.16" PRIx64,
 427                 (uint32_t)page_byte_size, GetPermissionsAsCString(permissions),
 428                 (uint64_t)addr);
 429   }
 430
 431   if (addr != LLDB_INVALID_ADDRESS) {
 432     block_sp.reset(
 433         new AllocatedBlock(addr, page_byte_size, permissions, chunk_size));
 434     m_memory_map.insert(std::make_pair(permissions, block_sp));
 435   }
 436   return block_sp;
 437 }
 438
 439 lldb::addr_t AllocatedMemoryCache::AllocateMemory(size_t byte_size,
 440                                                   uint32_t permissions,
 441                                                   Error &error) {
 442   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 443
 444   addr_t addr = LLDB_INVALID_ADDRESS;
 445   std::pair<PermissionsToBlockMap::iterator, PermissionsToBlockMap::iterator>
 446       range = m_memory_map.equal_range(permissions);
 447
 448   for (PermissionsToBlockMap::iterator pos = range.first; pos != range.second;
 449        ++pos) {
 450     addr = (*pos).second->ReserveBlock(byte_size);
 451     if (addr != LLDB_INVALID_ADDRESS)
 452       break;
 453   }
 454
 455   if (addr == LLDB_INVALID_ADDRESS) {
 456     AllocatedBlockSP block_sp(AllocatePage(byte_size, permissions, 16, error));
 457
 458     if (block_sp)
 459       addr = block_sp->ReserveBlock(byte_size);
 460   }
 461   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
 462   if (log)
 463     log->Printf(
 464         "AllocatedMemoryCache::AllocateMemory (byte_size = 0x%8.8" PRIx32
 465         ", permissions = %s) => 0x%16.16" PRIx64,
 466         (uint32_t)byte_size, GetPermissionsAsCString(permissions),
 467         (uint64_t)addr);
 468   return addr;
 469 }
 470
 471 bool AllocatedMemoryCache::DeallocateMemory(lldb::addr_t addr) {
 472   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 473
 474   PermissionsToBlockMap::iterator pos, end = m_memory_map.end();
 475   bool success = false;
 476   for (pos = m_memory_map.begin(); pos != end; ++pos) {
 477     if (pos->second->Contains(addr)) {
 478       success = pos->second->FreeBlock(addr);
 479       break;
 480     }
 481   }
 482   Log *log(GetLogIfAllCategoriesSet(LIBLLDB_LOG_PROCESS));
 483   if (log)
 484     log->Printf("AllocatedMemoryCache::DeallocateMemory (addr = 0x%16.16" PRIx64
 485                 ") => %i",
 486                 (uint64_t)addr, success);
 487   return success;
 488 }