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