Program Listing for File AllocationMap.cpp¶
↰ Return to documentation for file (umpire/util/AllocationMap.cpp
)
//////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2016-20, Lawrence Livermore National Security, LLC and Umpire
// project contributors. See the COPYRIGHT file for details.
//
// SPDX-License-Identifier: (MIT)
//////////////////////////////////////////////////////////////////////////////
#include "umpire/util/AllocationMap.hpp"
#include <functional>
#include <sstream>
#include <type_traits>
#include <utility>
#include "umpire/Replay.hpp"
#include "umpire/util/FixedMallocPool.hpp"
#include "umpire/util/Macros.hpp"
#include "umpire/util/backtrace.hpp"
namespace umpire {
namespace util {
// Record List
AllocationMap::RecordList::RecordList(AllocationMap& map,
AllocationRecord record)
: m_map{map}, m_tail{nullptr}, m_length{0}
{
push_back(record);
}
AllocationMap::RecordList::~RecordList()
{
RecordBlock* curr = m_tail;
while (curr) {
RecordBlock* prev = curr->prev;
m_map.m_block_pool.deallocate(curr);
curr = prev;
}
}
void AllocationMap::RecordList::push_back(const AllocationRecord& rec)
{
RecordBlock* curr = static_cast<RecordBlock*>(m_map.m_block_pool.allocate());
curr->prev = m_tail;
curr->rec = rec;
m_tail = curr;
m_length++;
}
AllocationRecord AllocationMap::RecordList::pop_back()
{
if (m_length == 0) {
UMPIRE_ERROR("pop_back() called, but m_length == 0");
}
const AllocationRecord ret = m_tail->rec;
RecordBlock* prev = m_tail->prev;
// Deallocate and move tail pointer
m_map.m_block_pool.deallocate(m_tail);
m_tail = prev;
// Reduce size
m_length--;
return ret;
}
AllocationMap::RecordList::ConstIterator AllocationMap::RecordList::begin()
const
{
return AllocationMap::RecordList::ConstIterator{this, iterator_begin{}};
}
AllocationMap::RecordList::ConstIterator AllocationMap::RecordList::end() const
{
return AllocationMap::RecordList::ConstIterator{this, iterator_end{}};
}
std::size_t AllocationMap::RecordList::size() const
{
return m_length;
}
bool AllocationMap::RecordList::empty() const
{
return size() == 0;
}
AllocationRecord* AllocationMap::RecordList::back()
{
return &m_tail->rec;
}
const AllocationRecord* AllocationMap::RecordList::back() const
{
return &m_tail->rec;
}
AllocationMap::RecordList::ConstIterator::ConstIterator()
: m_list(nullptr), m_curr(nullptr)
{
}
AllocationMap::RecordList::ConstIterator::ConstIterator(const RecordList* list,
iterator_begin)
: m_list(list), m_curr(m_list->m_tail)
{
}
AllocationMap::RecordList::ConstIterator::ConstIterator(const RecordList* list,
iterator_end)
: m_list(list), m_curr(nullptr)
{
}
const AllocationRecord& AllocationMap::RecordList::ConstIterator::operator*()
{
return *operator->();
}
const AllocationRecord* AllocationMap::RecordList::ConstIterator::operator->()
{
if (!m_curr)
UMPIRE_ERROR("Cannot dereference nullptr");
return &m_curr->rec;
}
AllocationMap::RecordList::ConstIterator&
AllocationMap::RecordList::ConstIterator::operator++()
{
if (!m_curr)
UMPIRE_ERROR("Cannot dereference nullptr");
m_curr = m_curr->prev;
return *this;
}
AllocationMap::RecordList::ConstIterator
AllocationMap::RecordList::ConstIterator::operator++(int)
{
ConstIterator tmp{*this};
this->operator++();
return tmp;
}
bool AllocationMap::RecordList::ConstIterator::operator==(
const AllocationMap::RecordList::ConstIterator& other) const
{
return m_list == other.m_list && m_curr == other.m_curr;
}
bool AllocationMap::RecordList::ConstIterator::operator!=(
const AllocationMap::RecordList::ConstIterator& other) const
{
return !(*this == other);
}
// AllocationMap
AllocationMap::AllocationMap()
: m_block_pool{sizeof(RecordList::RecordBlock)},
m_map{},
m_size{0},
m_mutex{}
{
}
void AllocationMap::insert(void* ptr, AllocationRecord record)
{
std::lock_guard<std::mutex> lock(m_mutex);
UMPIRE_LOG(Debug, "Inserting " << ptr);
UMPIRE_REPLAY(
"\"event\": \"allocation_map_insert\", \"payload\": { \"ptr\": \""
<< ptr << "\", \"record_ptr\": \"" << record.ptr
<< "\", \"record_size\": \"" << record.size
<< "\", \"record_strategy\": \"" << record.strategy << "\" }");
auto pair = m_map.insert(ptr, *this, record);
Map::Iterator it{pair.first};
const bool inserted{pair.second};
if (!inserted) {
// Record was not added
it->second->push_back(record);
}
// else
// -> insert() already added it
++m_size;
}
const AllocationRecord* AllocationMap::find(void* ptr) const
{
std::lock_guard<std::mutex> lock(m_mutex);
UMPIRE_LOG(Debug, "Searching for " << ptr);
UMPIRE_REPLAY("\"event\": \"allocation_map_find\", \"payload\": { \"ptr\": \""
<< ptr << "\" }");
const AllocationRecord* alloc_record = doFindRecord(ptr);
if (alloc_record) {
return alloc_record;
} else {
#if !defined(NDEBUG)
// use this from a debugger to dump the contents of the AllocationMap
printAll();
#endif
UMPIRE_ERROR("Allocation not mapped: " << ptr);
}
}
AllocationRecord* AllocationMap::find(void* ptr)
{
return const_cast<AllocationRecord*>(
const_cast<const AllocationMap*>(this)->find(ptr));
}
const AllocationRecord* AllocationMap::doFindRecord(void* ptr) const noexcept
{
const AllocationRecord* alloc_record = nullptr;
Map::ConstIterator iter = m_map.findOrBefore(ptr);
// faster, equivalent way of checking iter != m_map->end()
if (iter->second) {
auto candidate = iter->second->back();
UMPIRE_ASSERT(candidate->ptr <= ptr);
// Check if ptr is inside candidate's allocation
const bool in_candidate = (static_cast<char*>(candidate->ptr) +
candidate->size) > static_cast<char*>(ptr) ||
(candidate->ptr == ptr);
if (in_candidate) {
UMPIRE_LOG(Debug, "Found " << ptr << " at " << candidate->ptr
<< " with size " << candidate->size);
alloc_record = candidate;
} else {
alloc_record = nullptr;
}
}
return alloc_record;
}
const AllocationRecord* AllocationMap::findRecord(void* ptr) const noexcept
{
std::lock_guard<std::mutex> lock(m_mutex);
// Call method
return doFindRecord(ptr);
}
AllocationRecord* AllocationMap::findRecord(void* ptr) noexcept
{
return const_cast<AllocationRecord*>(
const_cast<const AllocationMap*>(this)->findRecord(ptr));
}
AllocationRecord AllocationMap::remove(void* ptr)
{
std::lock_guard<std::mutex> lock(m_mutex);
AllocationRecord ret;
UMPIRE_LOG(Debug, "Removing " << ptr);
UMPIRE_REPLAY(
"\"event\": \"allocation_map_remove\", \"payload\": { \"ptr\": \""
<< ptr << "\" }");
auto iter = m_map.find(ptr);
if (iter->second) {
// faster, equivalent way of checking iter != m_map->end()
ret = iter->second->pop_back();
if (iter->second->empty())
m_map.removeLast();
} else {
UMPIRE_ERROR("Cannot remove " << ptr);
}
--m_size;
return ret;
}
bool AllocationMap::contains(void* ptr) const
{
UMPIRE_LOG(Debug, "Searching for " << ptr);
return (findRecord(ptr) != nullptr);
}
void AllocationMap::clear()
{
std::lock_guard<std::mutex> lock(m_mutex);
UMPIRE_LOG(Debug, "Clearing");
UMPIRE_REPLAY("\"event\": \"allocation_map_clear\"");
m_map.clear();
m_size = 0;
}
std::size_t AllocationMap::size() const
{
return m_size;
}
void AllocationMap::print(
const std::function<bool(const AllocationRecord&)>&& pred,
std::ostream& os) const
{
for (auto p : m_map) {
std::stringstream ss;
bool any_match = false;
ss << p.first << " {" << std::endl;
auto iter = p.second->begin();
auto end = p.second->end();
while (iter != end) {
if (pred(*iter)) {
any_match = true;
auto end_ptr = static_cast<unsigned char*>(iter->ptr) + iter->size;
ss << iter->size << " [ " << reinterpret_cast<void*>(iter->ptr)
<< " -- " << reinterpret_cast<void*>(end_ptr) << " ] " << std::endl
#if defined(UMPIRE_ENABLE_BACKTRACE)
<< umpire::util::backtracer<trace_optional>::print(
iter->allocation_backtrace)
#endif // UMPIRE_ENABLE_BACKTRACE
<< std::endl;
}
++iter;
}
ss << "}" << std::endl;
if (any_match) {
os << ss.str();
}
}
}
void AllocationMap::printAll(std::ostream& os) const
{
os << "🔍 Printing allocation map contents..." << std::endl;
print([](const AllocationRecord&) { return true; }, os);
os << "done." << std::endl;
}
AllocationMap::ConstIterator AllocationMap::begin() const
{
return AllocationMap::ConstIterator{this, iterator_begin{}};
}
AllocationMap::ConstIterator AllocationMap::end() const
{
return AllocationMap::ConstIterator{this, iterator_end{}};
}
AllocationMap::ConstIterator::ConstIterator(const AllocationMap* map,
iterator_begin)
: m_outer_iter(map->m_map.begin()),
m_inner_iter(m_outer_iter->first ? m_outer_iter->second->begin()
: InnerIter{}),
m_inner_end(m_outer_iter->first ? m_outer_iter->second->end()
: InnerIter{}),
m_outer_end(map->m_map.end())
{
}
AllocationMap::ConstIterator::ConstIterator(const AllocationMap* map,
iterator_end)
: m_outer_iter(map->m_map.end()),
m_inner_iter(InnerIter{}),
m_inner_end(InnerIter{}),
m_outer_end(map->m_map.end())
{
}
const AllocationRecord& AllocationMap::ConstIterator::operator*()
{
return m_inner_iter.operator*();
}
const AllocationRecord* AllocationMap::ConstIterator::operator->()
{
return m_inner_iter.operator->();
}
AllocationMap::ConstIterator& AllocationMap::ConstIterator::operator++()
{
++m_inner_iter;
if (m_inner_iter == m_inner_end) {
++m_outer_iter;
if (m_outer_iter != m_outer_end) {
m_inner_iter = m_outer_iter->second->begin();
m_inner_end = m_outer_iter->second->end();
} else {
m_inner_iter = InnerIter{};
}
}
return *this;
}
AllocationMap::ConstIterator AllocationMap::ConstIterator::operator++(int)
{
ConstIterator tmp{*this};
++(*this);
return tmp;
}
bool AllocationMap::ConstIterator::operator==(
const AllocationMap::ConstIterator& other) const
{
return m_outer_iter == other.m_outer_iter &&
m_inner_iter == other.m_inner_iter;
}
bool AllocationMap::ConstIterator::operator!=(
const AllocationMap::ConstIterator& other) const
{
return !(*this == other);
}
} // end of namespace util
} // end of namespace umpire