From 7e84ae8f1efbe8e45dd5e578fc180c152669bfc1 Mon Sep 17 00:00:00 2001 From: onesphore Date: Wed, 20 Jun 2018 14:25:40 +0200 Subject: [PATCH] Modified snapshot and pagestore tests. --- src/mc/mc_checkpoint.cpp | 1 + src/mc/snapshot/AddressSpace.hpp | 175 ++ src/mc/snapshot/ChunkedData.cpp | 57 + src/mc/snapshot/ChunkedData.hpp | 105 ++ src/mc/snapshot/PageStore.cpp | 260 +++ src/mc/snapshot/PageStore.hpp | 197 ++ src/mc/snapshot/RegionSnapshot.cpp | 151 ++ src/mc/snapshot/RegionSnapshot.hpp | 281 +++ src/mc/snapshot/compare.cpp | 1663 +++++++++++++++++ src/mc/snapshot/mc_checkpoint.cpp | 695 +++++++ src/mc/snapshot/mc_ignore.hpp | 18 + src/mc/snapshot/mc_mmu.hpp | 61 + src/mc/snapshot/mc_page_snapshot.cpp | 51 + src/mc/snapshot/mc_snapshot.cpp | 287 +++ src/mc/snapshot/mc_snapshot.hpp | 210 +++ .../unitTest/PageStore_unit_BOOST.cpp | 95 + .../unitTest/mc_snapshot_unit_BOOST.cpp | 129 ++ tools/cmake/Tests.cmake | 10 + 18 files changed, 4446 insertions(+) create mode 100644 src/mc/snapshot/AddressSpace.hpp create mode 100644 src/mc/snapshot/ChunkedData.cpp create mode 100644 src/mc/snapshot/ChunkedData.hpp create mode 100644 src/mc/snapshot/PageStore.cpp create mode 100644 src/mc/snapshot/PageStore.hpp create mode 100644 src/mc/snapshot/RegionSnapshot.cpp create mode 100644 src/mc/snapshot/RegionSnapshot.hpp create mode 100644 src/mc/snapshot/compare.cpp create mode 100644 src/mc/snapshot/mc_checkpoint.cpp create mode 100644 src/mc/snapshot/mc_ignore.hpp create mode 100644 src/mc/snapshot/mc_mmu.hpp create mode 100644 src/mc/snapshot/mc_page_snapshot.cpp create mode 100644 src/mc/snapshot/mc_snapshot.cpp create mode 100644 src/mc/snapshot/mc_snapshot.hpp create mode 100644 src/mc/snapshot/unitTest/PageStore_unit_BOOST.cpp create mode 100644 src/mc/snapshot/unitTest/mc_snapshot_unit_BOOST.cpp diff --git a/src/mc/mc_checkpoint.cpp b/src/mc/mc_checkpoint.cpp index 8e872d906c..1a3675b5c1 100644 --- a/src/mc/mc_checkpoint.cpp +++ b/src/mc/mc_checkpoint.cpp @@ -622,3 +622,4 @@ void restore_snapshot(std::shared_ptr snapshot) } } + diff --git a/src/mc/snapshot/AddressSpace.hpp b/src/mc/snapshot/AddressSpace.hpp new file mode 100644 index 0000000000..e06c61ef51 --- /dev/null +++ b/src/mc/snapshot/AddressSpace.hpp @@ -0,0 +1,175 @@ +/* Copyright (c) 2008-2018. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef SIMGRID_MC_ADDRESS_SPACE_H +#define SIMGRID_MC_ADDRESS_SPACE_H + +#include +#include +#include +#include +#include + +#include +#include + +#include "src/mc/mc_forward.hpp" +#include "src/mc/remote/RemotePtr.hpp" + +namespace simgrid { +namespace mc { + +/** Process index used when no process is available (SMPI privatization) + * + * The expected behavior is that if a process index is needed it will fail. + * */ +const int ProcessIndexMissing = -1; + +/** Process index used when we don't care about the process index (SMPI privatization) + * */ +const int ProcessIndexDisabled = -2; + +/** Constant used when any process will do (SMPI privatization) + * + * Note: This is is index of the first process. + */ +const int ProcessIndexAny = 0; + +/** Options for read operations + * + * This is a set of flags managed with bitwise operators. Only the + * meaningful operations are defined: addition, conversions to/from + * integers are not allowed. + */ +class ReadOptions { + std::uint32_t value_; + constexpr explicit ReadOptions(std::uint32_t value) : value_(value) {} +public: + constexpr ReadOptions() : value_(0) {} + + explicit constexpr operator bool() const { return value_ != 0; } + constexpr bool operator!() const { return value_ == 0; } + + constexpr ReadOptions operator|(ReadOptions const& that) const + { + return ReadOptions(value_ | that.value_); + } + constexpr ReadOptions operator&(ReadOptions const& that) const + { + return ReadOptions(value_ & that.value_); + } + constexpr ReadOptions operator^(ReadOptions const& that) const + { + return ReadOptions(value_ ^ that.value_); + } + constexpr ReadOptions operator~() const + { + return ReadOptions(~value_); + } + + ReadOptions& operator|=(ReadOptions const& that) + { + value_ |= that.value_; + return *this; + } + ReadOptions& operator&=(ReadOptions const& that) + { + value_ &= that.value_; + return *this; + } + ReadOptions& operator^=(ReadOptions const& that) + { + value_ &= that.value_; + return *this; + } + + /** Copy the data to the given buffer */ + static constexpr ReadOptions none() { return ReadOptions(0); } + + /** Allows to return a pointer to another buffer where the data is + * available instead of copying the data into the buffer + */ + static constexpr ReadOptions lazy() { return ReadOptions(1); } +}; + +/** A given state of a given process (abstract base class) + * + * Currently, this might either be: + * + * * the current state of an existing process; + * + * * a snapshot. + * + * In order to support SMPI privatization, the can read the memory from the + * context of a given SMPI process: if specified, the code reads data from the + * correct SMPI privatization VMA. + */ +class AddressSpace { +private: + RemoteClient* process_; + +public: + explicit AddressSpace(RemoteClient* process) : process_(process) {} + virtual ~AddressSpace() = default; + + /** The process of this address space + * + * This is where we can get debug informations, memory layout, etc. + */ + simgrid::mc::RemoteClient* process() const { return process_; } + + /** Read data from the address space + * + * @param buffer target buffer for the data + * @param size number of bytes to read + * @param address remote source address of the data + * @param process_index which process (used for SMPI privatization) + * @param options + */ + virtual const void* read_bytes(void* buffer, std::size_t size, + RemotePtr address, int process_index = ProcessIndexAny, + ReadOptions options = ReadOptions::none()) const = 0; + + /** Read a given data structure from the address space */ + template inline + void read(T *buffer, RemotePtr ptr, int process_index = ProcessIndexAny) const + { + this->read_bytes(buffer, sizeof(T), ptr, process_index); + } + + template inline + void read(Remote& buffer, RemotePtr ptr, int process_index = ProcessIndexAny) const + { + this->read_bytes(buffer.getBuffer(), sizeof(T), ptr, process_index); + } + + /** Read a given data structure from the addres space + * + * This version returns by value. + */ + template inline + Remote read(RemotePtr ptr, int process_index = ProcessIndexMissing) const + { + Remote res; + this->read_bytes(&res, sizeof(T), ptr, process_index); + return res; + } + + /** Read a string of known size */ + std::string read_string(RemotePtr address, std::size_t len) const + { + std::string res; + res.resize(len); + this->read_bytes(&res[0], len, address); + return res; + } + +}; + +} +} + +#endif diff --git a/src/mc/snapshot/ChunkedData.cpp b/src/mc/snapshot/ChunkedData.cpp new file mode 100644 index 0000000000..4c94d7c025 --- /dev/null +++ b/src/mc/snapshot/ChunkedData.cpp @@ -0,0 +1,57 @@ +/* Copyright (c) 2007-2018. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include +#include + +#include + +#include "xbt/asserts.h" +#include "xbt/misc.h" + +#include "src/mc/AddressSpace.hpp" +#include "src/mc/ChunkedData.hpp" +#include "src/mc/PageStore.hpp" + +namespace simgrid { +namespace mc { + +/** Take a per-page snapshot of a region + * + * @param addr The start of the region (must be at the beginning of a page) + * @param page_count Number of pages of the region + * @return Snapshot page numbers of this new snapshot + */ +ChunkedData::ChunkedData(PageStore& store, AddressSpace& as, + RemotePtr addr, std::size_t page_count) +{ + store_ = &store; + this->pagenos_.resize(page_count); + std::vector buffer(xbt_pagesize); + + for (size_t i = 0; i != page_count; ++i) { + + RemotePtr page = remote((void*) + simgrid::mc::mmu::join(i, addr.address())); + xbt_assert(simgrid::mc::mmu::split(page.address()).second == 0, + "Not at the beginning of a page"); + + /* Adding another copy (and a syscall) will probably slow things a lot. + TODO, optimize this somehow (at least by grouping the syscalls) + if needed. Either: + - reduce the number of syscalls + - let the application snapshot itself + - move the segments in shared memory (this will break `fork` however) + */ + + as.read_bytes(buffer.data(), xbt_pagesize, page, simgrid::mc::ProcessIndexDisabled); + + pagenos_[i] = store_->store_page(buffer.data()); + + } +} + +} +} diff --git a/src/mc/snapshot/ChunkedData.hpp b/src/mc/snapshot/ChunkedData.hpp new file mode 100644 index 0000000000..52b56c9a55 --- /dev/null +++ b/src/mc/snapshot/ChunkedData.hpp @@ -0,0 +1,105 @@ +/* Copyright (c) 2014-2018. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef SIMGRID_MC_CHUNKED_DATA_HPP +#define SIMGRID_MC_CHUNKED_DATA_HPP + +#include +#include + +#include +#include + +#include "src/mc/mc_forward.hpp" +#include "src/mc/PageStore.hpp" + +namespace simgrid { +namespace mc { + +/** A byte-string represented as a sequence of chunks from a PageStore + * + * In order to save memory when taking memory snapshots, a given byte-string + * is split in fixed-size chunks. Identical chunks (either from the same + * snapshot or more probably from different snpashots) share the same memory + * storage. + * + * Thus a chunked is represented as a sequence of indices of each chunk. + */ +class ChunkedData { + /** This is where we store the chunks */ + PageStore* store_ = nullptr; + /** Indices of the chunks in the `PageStore` */ + std::vector pagenos_; +public: + + ChunkedData() = default; + void clear() + { + for (std::size_t const& pageno : pagenos_) + store_->unref_page(pageno); + pagenos_.clear(); + } + ~ChunkedData() + { + clear(); + } + + // Copy and move + ChunkedData(ChunkedData const& that) + : store_ (that.store_) + , pagenos_(that.pagenos_) + { + for (std::size_t const& pageno : pagenos_) + store_->ref_page(pageno); + } + ChunkedData(ChunkedData&& that) + : store_(that.store_) + , pagenos_(std::move(that.pagenos_)) + { + that.store_ = nullptr; + that.pagenos_.clear(); + } + ChunkedData& operator=(ChunkedData const& that) + { + this->clear(); + store_ = that.store_; + pagenos_ = that.pagenos_; + for (std::size_t const& pageno : pagenos_) + store_->ref_page(pageno); + return *this; + } + ChunkedData& operator=(ChunkedData && that) + { + this->clear(); + store_ = that.store_; + that.store_ = nullptr; + pagenos_ = std::move(that.pagenos_); + that.pagenos_.clear(); + return *this; + } + + /** How many pages are used */ + std::size_t page_count() const { return pagenos_.size(); } + + /** Get a chunk index */ + std::size_t pageno(std::size_t i) const { return pagenos_[i]; } + + /** Get a view of the chunk indices */ + const std::size_t* pagenos() const { return pagenos_.data(); } + + /** Get a a pointer to a chunk */ + const void* page(std::size_t i) const + { + return store_->get_page(pagenos_[i]); + } + + ChunkedData(PageStore& store, AddressSpace& as, + RemotePtr addr, std::size_t page_count); +}; + +} +} + +#endif diff --git a/src/mc/snapshot/PageStore.cpp b/src/mc/snapshot/PageStore.cpp new file mode 100644 index 0000000000..d792f1c14f --- /dev/null +++ b/src/mc/snapshot/PageStore.cpp @@ -0,0 +1,260 @@ +/* Copyright (c) 2015-2018. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include // memcpy, memcmp +#include + +#include +#ifdef __FreeBSD__ +# define MAP_POPULATE MAP_PREFAULT_READ +#endif + +#include "xbt/base.h" +#include "xbt/log.h" +#include "xbt/sysdep.h" + +#include "src/internal_config.h" + +#include "src/mc/PageStore.hpp" + +#include "src/mc/mc_mmu.hpp" + +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_page_snapshot, mc, "Logging specific to mc_page_snapshot"); + +namespace simgrid { +namespace mc { + +/** @brief Compute a hash for the given memory page + * + * The page is used before inserting the page in the page store + * in order to find duplicate of this page in the page store. + * + * @param data Memory page + * @return hash off the page + */ +static XBT_ALWAYS_INLINE PageStore::hash_type mc_hash_page(const void* data) +{ + const std::uint64_t* values = (const uint64_t*) data; + std::size_t n = xbt_pagesize / sizeof(uint64_t); + + // This djb2: + std::uint64_t hash = 5381; + for (std::size_t i = 0; i != n; ++i) + hash = ((hash << 5) + hash) + values[i]; + return hash; +} + +// ***** snapshot_page_manager + +PageStore::PageStore(size_t size) : memory_(nullptr), capacity_(size), top_index_(0) +{ + // Using mmap in order to be able to expand the region by relocating it somewhere else in the virtual memory space: + void* memory = ::mmap(nullptr, size << xbt_pagebits, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, -1, 0); + if (memory == MAP_FAILED) + xbt_die("Could not mmap initial snapshot pages."); + + this->top_index_ = 0; + this->memory_ = memory; + this->page_counts_.resize(size); +} + +PageStore::~PageStore() +{ + ::munmap(this->memory_, this->capacity_ << xbt_pagebits); +} + +void PageStore::resize(std::size_t size) +{ + size_t old_bytesize = this->capacity_ << xbt_pagebits; + size_t new_bytesize = size << xbt_pagebits; + void *new_memory; + + // Expand the memory region by moving it into another + // virtual memory address if necessary: +#if HAVE_MREMAP + new_memory = mremap(this->memory_, old_bytesize, new_bytesize, MREMAP_MAYMOVE); + if (new_memory == MAP_FAILED) + xbt_die("Could not mremap snapshot pages."); +#else + if (new_bytesize > old_bytesize) { + // Grow: first try to add new space after current map + new_memory = mmap((char *)this->memory_ + old_bytesize, + new_bytesize-old_bytesize, + PROT_READ|PROT_WRITE, + MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, + -1, 0); + if (new_memory == MAP_FAILED) + xbt_die("Could not mremap snapshot pages."); + // Check if expanding worked + if (new_memory != (char *)this->memory_ + old_bytesize) { + // New memory segment could not be put at the end of this->memory_, + // so cancel this one and try to rellocate everything and copy data + munmap(new_memory, new_bytesize-old_bytesize); + new_memory = mmap(nullptr, + new_bytesize, + PROT_READ|PROT_WRITE, + MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, + -1, 0); + if (new_memory == MAP_FAILED) + xbt_die("Could not mremap snapshot pages."); + memcpy(new_memory, this->memory_, old_bytesize); + munmap(this->memory_, old_bytesize); + } + } + else { + // We don't have functions to shrink a mapping, so leave memory as + // it is for now + new_memory = this->memory_; + } +#endif + + this->capacity_ = size; + this->memory_ = new_memory; + this->page_counts_.resize(size, 0); +} + +/** Allocate a free page + * + * @return index of the free page + */ +std::size_t PageStore::alloc_page() +{ + if (this->free_pages_.empty()) { + + // Expand the region: + if (this->top_index_ == this->capacity_) + // All the pages are allocated, we need add more pages: + this->resize(2 * this->capacity_); + + // Use a page from the top: + return this->top_index_++; + + } else { + + // Use a page from free_pages_ (inside of the region): + size_t res = this->free_pages_[this->free_pages_.size() - 1]; + this->free_pages_.pop_back(); + return res; + } +} + +void PageStore::remove_page(std::size_t pageno) +{ + this->free_pages_.push_back(pageno); + const void* page = this->get_page(pageno); + hash_type hash = mc_hash_page(page); + this->hash_index_[hash].erase(pageno); +} + +/** Store a page in memory */ +std::size_t PageStore::store_page(void* page) +{ + xbt_assert(top_index_ <= this->capacity_, "top_index is not consistent"); + + // First, we check if a page with the same content is already in the page store: + // 1. compute the hash of the page + // 2. find pages with the same hash using `hash_index_` + // 3. find a page with the same content + hash_type hash = mc_hash_page(page); + + // Try to find a duplicate in set of pages with the same hash: + page_set_type& page_set = this->hash_index_[hash]; + for (size_t const& pageno : page_set) { + const void* snapshot_page = this->get_page(pageno); + if (memcmp(page, snapshot_page, xbt_pagesize) == 0) { + + // If a page with the same content is already in the page store it's reused and its refcount is incremented. + page_counts_[pageno]++; + return pageno; + + } + } + + // Otherwise, a new page is allocated in the page store and the content of the page is `memcpy()`-ed to this new page. + std::size_t pageno = alloc_page(); + xbt_assert(this->page_counts_[pageno]==0, "Allocated page is already used"); + void* snapshot_page = (void*) this->get_page(pageno); + memcpy(snapshot_page, page, xbt_pagesize); + page_set.insert(pageno); + page_counts_[pageno]++; + return pageno; +} + +} +} + +#ifdef SIMGRID_TEST + +#include +#include + +#include +#include + +#include + +#include "src/mc/PageStore.hpp" + +static int value = 0; + +static void new_content(void* data, std::size_t size) +{ + ::memset(data, ++value, size); +} + +static void* getpage() +{ + return mmap(nullptr, getpagesize(), PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); +} + +XBT_TEST_SUITE("mc_page_store", "Page store"); + +XBT_TEST_UNIT("base", test_mc_page_store, "Test adding/removing pages in the store") +{ + using simgrid::mc::PageStore; + + xbt_test_add("Init"); + std::size_t pagesize = (size_t) getpagesize(); + std::unique_ptr store = std::unique_ptr(new simgrid::mc::PageStore(500)); + void* data = getpage(); + xbt_test_assert(store->size()==0, "Bad size"); + + xbt_test_add("Store the page once"); + new_content(data, pagesize); + size_t pageno1 = store->store_page(data); + xbt_test_assert(store->get_ref(pageno1)==1, "Bad refcount"); + const void* copy = store->get_page(pageno1); + xbt_test_assert(::memcmp(data, copy, pagesize)==0, "Page data should be the same"); + xbt_test_assert(store->size()==1, "Bad size"); + + xbt_test_add("Store the same page again"); + size_t pageno2 = store->store_page(data); + xbt_test_assert(pageno1==pageno2, "Page should be the same"); + xbt_test_assert(store->get_ref(pageno1)==2, "Bad refcount"); + xbt_test_assert(store->size()==1, "Bad size"); + + xbt_test_add("Store a new page"); + new_content(data, pagesize); + size_t pageno3 = store->store_page(data); + xbt_test_assert(pageno1 != pageno3, "New page should be different"); + xbt_test_assert(store->size()==2, "Bad size"); + + xbt_test_add("Unref pages"); + store->unref_page(pageno1); + xbt_assert(store->get_ref(pageno1)==1, "Bad refcount"); + xbt_assert(store->size()==2, "Bad size"); + store->unref_page(pageno2); + xbt_test_assert(store->size()==1, "Bad size"); + + xbt_test_add("Reallocate page"); + new_content(data, pagesize); + size_t pageno4 = store->store_page(data); + xbt_test_assert(pageno1 == pageno4, "Page was not reused"); + xbt_test_assert(store->get_ref(pageno4)==1, "Bad refcount"); + xbt_test_assert(store->size()==2, "Bad size"); +} + +#endif /* SIMGRID_TEST */ diff --git a/src/mc/snapshot/PageStore.hpp b/src/mc/snapshot/PageStore.hpp new file mode 100644 index 0000000000..da9d527c74 --- /dev/null +++ b/src/mc/snapshot/PageStore.hpp @@ -0,0 +1,197 @@ +/* Copyright (c) 2015-2018. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef SIMGRID_MC_PAGESTORE_HPP +#define SIMGRID_MC_PAGESTORE_HPP + +#include +#include + +#include +#include + +#include "xbt/base.h" + +#include "src/mc/mc_forward.hpp" +#include "src/mc/mc_mmu.hpp" + +namespace simgrid { +namespace mc { + +/** @brief Storage for snapshot memory pages + * + * The first (lower) layer of the per-page snapshot mechanism is a page store: + * its responsibility is to store immutable sharable reference-counted memory + * pages independently of the snapshotting logic. Snapshot management and + * representation is handled to an higher layer. READMORE + * + * Data structure: + * + * * A pointer (`memory_`) to a (currently anonymous) `mmap()`ed memory + * region holding the memory pages (the address of the first page). + * + * We want to keep this memory region aligned on the memory pages (so + * that we might be able to create non-linear memory mappings on those + * pages in the future) and be able to expand it without coyping the + * data (there will be a lot of pages here): we will be able to + * efficiently expand the memory mapping using `mremap()`, moving it + * to another virtual address if necessary. + * + * Because we will move this memory mapping on the virtual address + * space, only the index of the page will be stored in the snapshots + * and the page will always be looked up by going through `memory`: + * + * void* page = (char*) page_store->memory + page_index << pagebits; + * + * * The number of pages mapped in virtual memory (`capacity_`). Once all + * those pages are used, we need to expand the page store with + * `mremap()`. + * + * * A reference count for each memory page `page_counts_`. Each time a + * snapshot references a page, the counter is incremented. If a + * snapshot is freed, the reference count is decremented. When the + * reference count, of a page reaches 0 it is added to a list of available + * pages (`free_pages_`). + * + * * A list of free pages `free_pages_` which can be reused. This avoids having + * to scan the reference count list to find a free page. + * + * * When we are expanding the memory map we do not want to add thousand of page + * to the `free_pages_` list and remove them just afterwards. The `top_index_` + * field is an index after which all pages are free and are not in the `free_pages_` + * list. + * + * * When we are adding a page, we need to check if a page with the same + * content is already in the page store in order to reuse it. For this + * reason, we maintain an index (`hash_index_`) mapping the hash of a + * page to the list of page indices with this hash. + * We use a fast (non cryptographic) hash so there may be conflicts: + * we must be able to store multiple indices for the same hash. + * + */ +class PageStore { +public: // Types + typedef std::uint64_t hash_type; + +private: + // Types + // We are using a cheap hash to index a page. + // We should expect collision and we need to associate multiple page indices + // to the same hash. + typedef std::unordered_set page_set_type; + typedef std::unordered_map pages_map_type; + + // Fields: + /** First page */ + void* memory_; + /** Number of available pages in virtual memory */ + std::size_t capacity_; + /** Top of the used pages (index of the next available page) */ + std::size_t top_index_; + /** Page reference count */ + std::vector page_counts_; + /** Index of available pages before the top */ + std::vector free_pages_; + /** Index from page hash to page index */ + pages_map_type hash_index_; + + // Methods + void resize(std::size_t size); + std::size_t alloc_page(); + void remove_page(std::size_t pageno); + +public: + // Constructors + PageStore(PageStore const&) = delete; + PageStore& operator=(PageStore const&) = delete; + explicit PageStore(std::size_t size); + ~PageStore(); + + // Methods + + /** @brief Decrement the reference count for a given page + * + * Decrement the reference count of this page. Used when a snapshot is destroyed. + * + * If the reference count reaches zero, the page is recycled: + * it is added to the `free_pages_` list and removed from the `hash_index_`. + * + * */ + void unref_page(std::size_t pageno); + + /** @brief Increment the refcount for a given page + * + * This method used to increase a reference count of a page if we know + * that the content of a page is the same as a page already in the page + * store. + * + * This will be the case if a page if soft clean: we know that is has not + * changed since the previous cnapshot/restoration and we can avoid + * hashing the page, comparing byte-per-byte to candidates. + * */ + void ref_page(size_t pageno); + + /** @brief Store a page in the page store */ + std::size_t store_page(void* page); + + /** @brief Get a page from its page number + * + * @param pageno Number of the memory page in the store + * @return Start of the page + */ + const void* get_page(std::size_t pageno) const; + + // Debug/test methods + + /** @brief Get the number of references for a page */ + std::size_t get_ref(std::size_t pageno); + + /** @brief Get the number of used pages */ + std::size_t size(); + + /** @brief Get the capacity of the page store + * + * The capacity is expanded by a system call (mremap). + * */ + std::size_t capacity(); + +}; + +XBT_ALWAYS_INLINE void PageStore::unref_page(std::size_t pageno) +{ + if ((--this->page_counts_[pageno]) == 0) + this->remove_page(pageno); +} + +XBT_ALWAYS_INLINE void PageStore::ref_page(size_t pageno) +{ + ++this->page_counts_[pageno]; +} + +XBT_ALWAYS_INLINE const void* PageStore::get_page(std::size_t pageno) const +{ + return (void*) simgrid::mc::mmu::join(pageno, (std::uintptr_t) this->memory_); +} + +XBT_ALWAYS_INLINE std::size_t PageStore::get_ref(std::size_t pageno) +{ + return this->page_counts_[pageno]; +} + +XBT_ALWAYS_INLINE std::size_t PageStore::size() +{ + return this->top_index_ - this->free_pages_.size(); +} + +XBT_ALWAYS_INLINE std::size_t PageStore::capacity() +{ + return this->capacity_; +} + +} +} + +#endif diff --git a/src/mc/snapshot/RegionSnapshot.cpp b/src/mc/snapshot/RegionSnapshot.cpp new file mode 100644 index 0000000000..a659f9ae6f --- /dev/null +++ b/src/mc/snapshot/RegionSnapshot.cpp @@ -0,0 +1,151 @@ +/* Copyright (c) 2007-2018. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include + +#include +#ifdef __FreeBSD__ +# define MAP_POPULATE MAP_PREFAULT_READ +#endif + +#include "mc/mc.h" +#include "src/mc/mc_config.hpp" +#include "src/mc/mc_snapshot.hpp" + +#include "src/mc/ChunkedData.hpp" +#include "src/mc/RegionSnapshot.hpp" + +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_RegionSnaphot, mc, + "Logging specific to region snapshots"); + +namespace simgrid { +namespace mc { + +static inline +const char* to_cstr(RegionType region) +{ + switch (region) { + case RegionType::Unknown: + return "unknown"; + case RegionType::Heap: + return "Heap"; + case RegionType::Data: + return "Data"; + default: + return "?"; + } +} + +Buffer::Buffer(std::size_t size, Type type) : size_(size), type_(type) +{ + switch(type_) { + case Type::Malloc: + data_ = ::operator new(size_); + break; + case Type::Mmap: + data_ = ::mmap(nullptr, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, -1, 0); + if (data_ == MAP_FAILED) { + data_ = nullptr; + size_ = 0; + type_ = Type::Malloc; + throw std::bad_alloc(); + } + break; + default: + abort(); + } +} + +void Buffer::clear() noexcept +{ + switch(type_) { + case Type::Malloc: + ::operator delete(data_); + break; + case Type::Mmap: + if (munmap(data_, size_) != 0) + abort(); + break; + default: + abort(); + } + data_ = nullptr; + size_ = 0; + type_ = Type::Malloc; +} + +RegionSnapshot dense_region( + RegionType region_type, + void *start_addr, void* permanent_addr, size_t size) +{ + // When KSM support is enables, we allocate memory using mmap: + // * we don't want to advise bits of the heap as mergable + // * mmap gives data aligned on page boundaries which is merge friendly + simgrid::mc::Buffer data; + if (_sg_mc_ksm) + data = Buffer::mmap(size); + else + data = Buffer::malloc(size); + + mc_model_checker->process().read_bytes(data.get(), size, + remote(permanent_addr), + simgrid::mc::ProcessIndexDisabled); + +#ifdef __linux__ + if (_sg_mc_ksm) + // Mark the region as mergeable *after* we have written into it. + // Trying to merge them before is useless/counterproductive. + madvise(data.get(), size, MADV_MERGEABLE); +#endif + + simgrid::mc::RegionSnapshot region( + region_type, start_addr, permanent_addr, size); + region.flat_data(std::move(data)); + + XBT_DEBUG("New region : type : %s, data : %p (real addr %p), size : %zu", + to_cstr(region_type), region.flat_data().get(), permanent_addr, size); + return region; +} + +/** @brief Take a snapshot of a given region + * + * @param type + * @param start_addr Address of the region in the simulated process + * @param permanent_addr Permanent address of this data (for privatized variables, this is the virtual address of the privatized mapping) + * @param size Size of the data* + */ +RegionSnapshot region( + RegionType type, void *start_addr, void* permanent_addr, size_t size) +{ + if (_sg_mc_sparse_checkpoint) + return sparse_region(type, start_addr, permanent_addr, size); + else + return dense_region(type, start_addr, permanent_addr, size); +} + +RegionSnapshot sparse_region(RegionType region_type, + void *start_addr, void* permanent_addr, size_t size) +{ + simgrid::mc::RemoteClient* process = &mc_model_checker->process(); + assert(process != nullptr); + + xbt_assert((((uintptr_t)start_addr) & (xbt_pagesize-1)) == 0, + "Not at the beginning of a page"); + xbt_assert((((uintptr_t)permanent_addr) & (xbt_pagesize-1)) == 0, + "Not at the beginning of a page"); + size_t page_count = simgrid::mc::mmu::chunkCount(size); + + simgrid::mc::ChunkedData page_data(mc_model_checker->page_store(), *process, RemotePtr(permanent_addr), + page_count); + + simgrid::mc::RegionSnapshot region( + region_type, start_addr, permanent_addr, size); + region.page_data(std::move(page_data)); + return region; +} + +} +} diff --git a/src/mc/snapshot/RegionSnapshot.hpp b/src/mc/snapshot/RegionSnapshot.hpp new file mode 100644 index 0000000000..3ab73611ab --- /dev/null +++ b/src/mc/snapshot/RegionSnapshot.hpp @@ -0,0 +1,281 @@ +/* Copyright (c) 2007-2018. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef SIMGRID_MC_REGION_SNAPSHOT_HPP +#define SIMGRID_MC_REGION_SNAPSHOT_HPP + +#include +#include + +#include +#include + +#include "xbt/base.h" + +#include "src/mc/AddressSpace.hpp" +#include "src/mc/ChunkedData.hpp" +#include "src/mc/PageStore.hpp" +#include "src/mc/remote/RemotePtr.hpp" + +namespace simgrid { +namespace mc { + +enum class RegionType { + Unknown = 0, + Heap = 1, + Data = 2 +}; + +enum class StorageType { + NoData = 0, + Flat = 1, + Chunked = 2, + Privatized = 3 +}; + +class Buffer { +private: + enum class Type { + Malloc, + Mmap + }; + void* data_ = nullptr; + std::size_t size_; + Type type_ = Type::Malloc; + + Buffer(std::size_t size, Type type = Type::Malloc); + Buffer(void* data, std::size_t size, Type type = Type::Malloc) : + data_(data), size_(size), type_(type) {} +public: + Buffer() = default; + void clear() noexcept; + ~Buffer() noexcept { clear(); } + + static Buffer malloc(std::size_t size) + { + return Buffer(size, Type::Malloc); + } + static Buffer mmap(std::size_t size) + { + return Buffer(size, Type::Mmap); + } + + // No copy + Buffer(Buffer const& buffer) = delete; + Buffer& operator=(Buffer const& buffer) = delete; + + // Move + Buffer(Buffer&& that) noexcept + : data_(that.data_), size_(that.size_), type_(that.type_) + { + that.data_ = nullptr; + that.size_ = 0; + that.type_ = Type::Malloc; + } + Buffer& operator=(Buffer&& that) noexcept + { + clear(); + data_ = that.data_; + size_ = that.size_; + type_ = that.type_; + that.data_ = nullptr; + that.size_ = 0; + that.type_ = Type::Malloc; + return *this; + } + + void* get() { return data_; } + const void* get() const { return data_; } + std::size_t size() const { return size_; } +}; + +/** A copy/snapshot of a given memory region + * + * Different types of region snapshot storage types exist: + * + * * flat/dense snapshots are a simple copy of the region; + * + * * sparse/per-page snapshots are snaapshots which shared + * identical pages. + * + * * privatized (SMPI global variable privatization). + * + * This is handled with a variant based approach: + * + * * `storage_type` identified the type of storage; + * + * * an anonymous enum is used to distinguish the relevant types for + * each type. + */ +class RegionSnapshot { +public: + static const RegionType UnknownRegion = RegionType::Unknown; + static const RegionType HeapRegion = RegionType::Heap; + static const RegionType DataRegion = RegionType::Data; +private: + RegionType region_type_; + StorageType storage_type_; + simgrid::mc::ObjectInformation* object_info_; + + /** @brief Virtual address of the region in the simulated process */ + void *start_addr_; + + /** @brief Size of the data region in bytes */ + std::size_t size_; + + /** @brief Permanent virtual address of the region + * + * This is usually the same address as the simuilated process address. + * However, when using SMPI privatization of global variables, + * each SMPI process has its own set of global variables stored + * at a different virtual address. The scheduler maps those region + * on the region of the global variables. + * + * */ + void *permanent_addr_; + + Buffer flat_data_; + ChunkedData page_numbers_; + std::vector privatized_regions_; +public: + RegionSnapshot() : + region_type_(UnknownRegion), + storage_type_(StorageType::NoData), + object_info_(nullptr), + start_addr_(nullptr), + size_(0), + permanent_addr_(nullptr) + {} + RegionSnapshot(RegionType type, void *start_addr, void* permanent_addr, size_t size) : + region_type_(type), + storage_type_(StorageType::NoData), + object_info_(nullptr), + start_addr_(start_addr), + size_(size), + permanent_addr_(permanent_addr) + {} + ~RegionSnapshot() = default; + RegionSnapshot(RegionSnapshot const&) = default; + RegionSnapshot& operator=(RegionSnapshot const&) = default; + RegionSnapshot(RegionSnapshot&& that) + : region_type_(that.region_type_) + , storage_type_(that.storage_type_) + , object_info_(that.object_info_) + , start_addr_(that.start_addr_) + , size_(that.size_) + , permanent_addr_(that.permanent_addr_) + , flat_data_(std::move(that.flat_data_)) + , page_numbers_(std::move(that.page_numbers_)) + , privatized_regions_(std::move(that.privatized_regions_)) + { + that.clear(); + } + RegionSnapshot& operator=(RegionSnapshot&& that) + { + region_type_ = that.region_type_; + storage_type_ = that.storage_type_; + object_info_ = that.object_info_; + start_addr_ = that.start_addr_; + size_ = that.size_; + permanent_addr_ = that.permanent_addr_; + flat_data_ = std::move(that.flat_data_); + page_numbers_ = std::move(that.page_numbers_); + privatized_regions_ = std::move(that.privatized_regions_); + that.clear(); + return *this; + } + + // Data + + void clear() + { + region_type_ = UnknownRegion; + storage_type_ = StorageType::NoData; + privatized_regions_.clear(); + page_numbers_.clear(); + flat_data_.clear(); + object_info_ = nullptr; + start_addr_ = nullptr; + size_ = 0; + permanent_addr_ = nullptr; + } + + void clear_data() + { + storage_type_ = StorageType::NoData; + flat_data_.clear(); + page_numbers_.clear(); + privatized_regions_.clear(); + } + + void flat_data(Buffer data) + { + storage_type_ = StorageType::Flat; + flat_data_ = std::move(data); + page_numbers_.clear(); + privatized_regions_.clear(); + } + const Buffer& flat_data() const { return flat_data_; } + Buffer& flat_data() { return flat_data_; } + + void page_data(ChunkedData page_data) + { + storage_type_ = StorageType::Chunked; + flat_data_.clear(); + page_numbers_ = std::move(page_data); + privatized_regions_.clear(); + } + ChunkedData const& page_data() const { return page_numbers_; } + + void privatized_data(std::vector data) + { + storage_type_ = StorageType::Privatized; + flat_data_.clear(); + page_numbers_.clear(); + privatized_regions_ = std::move(data); + } + std::vector const& privatized_data() const + { + return privatized_regions_; + } + std::vector& privatized_data() + { + return privatized_regions_; + } + + simgrid::mc::ObjectInformation* object_info() const { return object_info_; } + void object_info(simgrid::mc::ObjectInformation* info) { object_info_ = info; } + + // Other getters + + RemotePtr start() const { return remote(start_addr_); } + RemotePtr end() const { return remote((char*)start_addr_ + size_); } + RemotePtr permanent_address() const { return remote(permanent_addr_); } + std::size_t size() const { return size_; } + StorageType storage_type() const { return storage_type_; } + RegionType region_type() const { return region_type_; } + + bool contain(RemotePtr p) const + { + return p >= start() && p < end(); + } +}; + +RegionSnapshot privatized_region( + RegionType region_type, void *start_addr, void* permanent_addr, + std::size_t size); +RegionSnapshot dense_region( + RegionType type, void *start_addr, void* data_addr, std::size_t size); +simgrid::mc::RegionSnapshot sparse_region( + RegionType type, void *start_addr, void* data_addr, std::size_t size); +simgrid::mc::RegionSnapshot region( + RegionType type, void *start_addr, void* data_addr, std::size_t size); + +} +} + +typedef simgrid::mc::RegionSnapshot s_mc_mem_region_t; +typedef s_mc_mem_region_t* mc_mem_region_t; +#endif diff --git a/src/mc/snapshot/compare.cpp b/src/mc/snapshot/compare.cpp new file mode 100644 index 0000000000..efbd0efeab --- /dev/null +++ b/src/mc/snapshot/compare.cpp @@ -0,0 +1,1663 @@ +/* Copyright (c) 2008-2018. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +/** \file compare.cpp Memory snapshooting and comparison */ + +#include + +#include +#include +#include +#include +#include + +#include "xbt/dynar.h" +#include "xbt/sysdep.h" +#include + +#include +#include + +#include "src/internal_config.h" + +#include "src/xbt/mmalloc/mmprivate.h" + +#if HAVE_SMPI +#include "src/smpi/include/private.hpp" +#endif + +#include "src/mc/Frame.hpp" +#include "src/mc/ObjectInformation.hpp" +#include "src/mc/Type.hpp" +#include "src/mc/Variable.hpp" +#include "src/mc/mc_config.hpp" +#include "src/mc/mc_dwarf.hpp" +#include "src/mc/mc_forward.hpp" +#include "src/mc/mc_private.hpp" +#include "src/mc/mc_smx.hpp" +#include "src/mc/mc_snapshot.hpp" + +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_compare, xbt, "Logging specific to mc_compare in mc"); + +namespace simgrid { +namespace mc { + +struct HeapLocation; +typedef std::array HeapLocationPair; +typedef std::set HeapLocationPairs; +struct HeapArea; +struct ProcessComparisonState; +struct StateComparator; + +static int compare_heap_area( + StateComparator& state, + int process_index, const void *area1, const void* area2, + Snapshot* snapshot1, Snapshot* snapshot2, + HeapLocationPairs* previous, Type* type, int pointer_level); + +} +} + +using simgrid::mc::remote; + +/*********************************** Heap comparison ***********************************/ +/***************************************************************************************/ + +namespace simgrid { +namespace mc { + +class HeapLocation { +public: + int block_ = 0; + int fragment_ = 0; + + HeapLocation() = default; + HeapLocation(int block, int fragment = 0) : block_(block), fragment_(fragment) {} + + bool operator==(HeapLocation const& that) const + { + return block_ == that.block_ && fragment_ == that.fragment_; + } + bool operator<(HeapLocation const& that) const + { + return std::make_pair(block_, fragment_) < std::make_pair(that.block_, that.fragment_); + } +}; + +static inline +HeapLocationPair makeHeapLocationPair(int block1, int fragment1, int block2, int fragment2) +{ + return simgrid::mc::HeapLocationPair{{ + simgrid::mc::HeapLocation(block1, fragment1), + simgrid::mc::HeapLocation(block2, fragment2) + }}; +} + +class HeapArea : public HeapLocation { +public: + bool valid_ = false; + HeapArea() = default; + explicit HeapArea(int block) : valid_(true) { block_ = block; } + HeapArea(int block, int fragment) : valid_(true) + { + block_ = block; + fragment_ = fragment; + } +}; + +class ProcessComparisonState { +public: + std::vector* to_ignore = nullptr; + std::vector equals_to; + std::vector types; + std::size_t heapsize = 0; + + void initHeapInformation(xbt_mheap_t heap, std::vector* i); +}; + +namespace { + +/** A hash which works with more stuff + * + * It can hash pairs: the standard hash currently doesn't include this. + */ +template class hash : public std::hash { +}; + +template class hash> { +public: + std::size_t operator()(std::pairconst& x) const + { + hash h1; + hash h2; + return h1(x.first) ^ h2(x.second); + } +}; + +} + +class StateComparator { +public: + s_xbt_mheap_t std_heap_copy; + std::size_t heaplimit; + std::array processStates; + + std::unordered_set, hash>> compared_pointers; + + void clear() + { + compared_pointers.clear(); + } + + int initHeapInformation( + xbt_mheap_t heap1, xbt_mheap_t heap2, + std::vector* i1, + std::vector* i2); + + HeapArea& equals_to1_(std::size_t i, std::size_t j) + { + return processStates[0].equals_to[ MAX_FRAGMENT_PER_BLOCK * i + j]; + } + HeapArea& equals_to2_(std::size_t i, std::size_t j) + { + return processStates[1].equals_to[ MAX_FRAGMENT_PER_BLOCK * i + j]; + } + Type*& types1_(std::size_t i, std::size_t j) + { + return processStates[0].types[ MAX_FRAGMENT_PER_BLOCK * i + j]; + } + Type*& types2_(std::size_t i, std::size_t j) + { + return processStates[1].types[ MAX_FRAGMENT_PER_BLOCK * i + j]; + } + + HeapArea const& equals_to1_(std::size_t i, std::size_t j) const + { + return processStates[0].equals_to[ MAX_FRAGMENT_PER_BLOCK * i + j]; + } + HeapArea const& equals_to2_(std::size_t i, std::size_t j) const + { + return processStates[1].equals_to[ MAX_FRAGMENT_PER_BLOCK * i + j]; + } + Type* const& types1_(std::size_t i, std::size_t j) const + { + return processStates[0].types[ MAX_FRAGMENT_PER_BLOCK * i + j]; + } + Type* const& types2_(std::size_t i, std::size_t j) const + { + return processStates[1].types[ MAX_FRAGMENT_PER_BLOCK * i + j]; + } + + /** Check whether two blocks are known to be matching + * + * @param b1 Block of state 1 + * @param b2 Block of state 2 + * @return if the blocks are known to be matching + */ + bool blocksEqual(int b1, int b2) const + { + return this->equals_to1_(b1, 0).block_ == b2 && this->equals_to2_(b2, 0).block_ == b1; + } + + /** Check whether two fragments are known to be matching + * + * @param b1 Block of state 1 + * @param f1 Fragment of state 1 + * @param b2 Block of state 2 + * @param f2 Fragment of state 2 + * @return if the fragments are known to be matching + */ + int fragmentsEqual(int b1, int f1, int b2, int f2) const + { + return this->equals_to1_(b1, f1).block_ == b2 && this->equals_to1_(b1, f1).fragment_ == f2 && + this->equals_to2_(b2, f2).block_ == b1 && this->equals_to2_(b2, f2).fragment_ == f1; + } + + void match_equals(HeapLocationPairs* list); +}; + +} +} + +/************************************************************************************/ + +static ssize_t heap_comparison_ignore_size( + std::vector* ignore_list, + const void *address) +{ + int start = 0; + int end = ignore_list->size() - 1; + + while (start <= end) { + unsigned int cursor = (start + end) / 2; + simgrid::mc::IgnoredHeapRegion const& region = (*ignore_list)[cursor]; + if (region.address == address) + return region.size; + if (region.address < address) + start = cursor + 1; + if (region.address > address) + end = cursor - 1; + } + + return -1; +} + +static bool is_stack(const void *address) +{ + for (auto const& stack : mc_model_checker->process().stack_areas()) + if (address == stack.address) + return true; + return false; +} + +// TODO, this should depend on the snapshot? +static bool is_block_stack(int block) +{ + for (auto const& stack : mc_model_checker->process().stack_areas()) + if (block == stack.block) + return true; + return false; +} + +namespace simgrid { +namespace mc { + +void StateComparator::match_equals(HeapLocationPairs* list) +{ + for (auto const& pair : *list) { + if (pair[0].fragment_ != -1) { + this->equals_to1_(pair[0].block_, pair[0].fragment_) = simgrid::mc::HeapArea(pair[1].block_, pair[1].fragment_); + this->equals_to2_(pair[1].block_, pair[1].fragment_) = simgrid::mc::HeapArea(pair[0].block_, pair[0].fragment_); + } else { + this->equals_to1_(pair[0].block_, 0) = simgrid::mc::HeapArea(pair[1].block_, pair[1].fragment_); + this->equals_to2_(pair[1].block_, 0) = simgrid::mc::HeapArea(pair[0].block_, pair[0].fragment_); + } + } +} + +void ProcessComparisonState::initHeapInformation(xbt_mheap_t heap, + std::vector* i) +{ + auto heaplimit = heap->heaplimit; + this->heapsize = heap->heapsize; + this->to_ignore = i; + this->equals_to.assign(heaplimit * MAX_FRAGMENT_PER_BLOCK, HeapArea()); + this->types.assign(heaplimit * MAX_FRAGMENT_PER_BLOCK, nullptr); +} + +int StateComparator::initHeapInformation(xbt_mheap_t heap1, xbt_mheap_t heap2, + std::vector* i1, + std::vector* i2) +{ + if ((heap1->heaplimit != heap2->heaplimit) || (heap1->heapsize != heap2->heapsize)) + return -1; + this->heaplimit = heap1->heaplimit; + this->std_heap_copy = *mc_model_checker->process().get_heap(); + this->processStates[0].initHeapInformation(heap1, i1); + this->processStates[1].initHeapInformation(heap2, i2); + return 0; +} + +// TODO, have a robust way to find it in O(1) +static inline +mc_mem_region_t MC_get_heap_region(simgrid::mc::Snapshot* snapshot) +{ + for (auto const& region : snapshot->snapshot_regions) + if (region->region_type() == simgrid::mc::RegionType::Heap) + return region.get(); + xbt_die("No heap region"); +} + +static +int mmalloc_compare_heap( + simgrid::mc::StateComparator& state, simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2) +{ + simgrid::mc::RemoteClient* process = &mc_model_checker->process(); + + /* Start comparison */ + size_t i1; + size_t i2; + size_t j1; + size_t j2; + size_t k; + void* addr_block1; + void* addr_block2; + void* addr_frag1; + void* addr_frag2; + int nb_diff1 = 0; + int nb_diff2 = 0; + int equal; + + /* Check busy blocks */ + i1 = 1; + + malloc_info heapinfo_temp1; + malloc_info heapinfo_temp2; + malloc_info heapinfo_temp2b; + + mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1); + mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2); + + // This is the address of std_heap->heapinfo in the application process: + void* heapinfo_address = &((xbt_mheap_t) process->heap_address)->heapinfo; + + // This is in snapshot do not use them directly: + const malloc_info* heapinfos1 = snapshot1->read( + RemotePtr((std::uint64_t)heapinfo_address), simgrid::mc::ProcessIndexMissing); + const malloc_info* heapinfos2 = snapshot2->read( + RemotePtr((std::uint64_t)heapinfo_address), simgrid::mc::ProcessIndexMissing); + + while (i1 < state.heaplimit) { + + const malloc_info* heapinfo1 = (const malloc_info*) MC_region_read(heap_region1, &heapinfo_temp1, &heapinfos1[i1], sizeof(malloc_info)); + const malloc_info* heapinfo2 = (const malloc_info*) MC_region_read(heap_region2, &heapinfo_temp2, &heapinfos2[i1], sizeof(malloc_info)); + + if (heapinfo1->type == MMALLOC_TYPE_FREE || heapinfo1->type == MMALLOC_TYPE_HEAPINFO) { /* Free block */ + i1 ++; + continue; + } + + if (heapinfo1->type < 0) { + fprintf(stderr, "Unkown mmalloc block type.\n"); + abort(); + } + + addr_block1 = ((void*)(((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase)); + + if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED) { /* Large block */ + + if (is_stack(addr_block1)) { + for (k = 0; k < heapinfo1->busy_block.size; k++) + state.equals_to1_(i1 + k, 0) = HeapArea(i1, -1); + for (k = 0; k < heapinfo2->busy_block.size; k++) + state.equals_to2_(i1 + k, 0) = HeapArea(i1, -1); + i1 += heapinfo1->busy_block.size; + continue; + } + + if (state.equals_to1_(i1, 0).valid_) { + i1++; + continue; + } + + i2 = 1; + equal = 0; + + /* Try first to associate to same block in the other heap */ + if (heapinfo2->type == heapinfo1->type && state.equals_to2_(i1, 0).valid_ == 0) { + addr_block2 = (ADDR2UINT(i1) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase; + int res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing, addr_block1, addr_block2, + snapshot1, snapshot2, nullptr, nullptr, 0); + if (res_compare != 1) { + for (k = 1; k < heapinfo2->busy_block.size; k++) + state.equals_to2_(i1 + k, 0) = HeapArea(i1, -1); + for (k = 1; k < heapinfo1->busy_block.size; k++) + state.equals_to1_(i1 + k, 0) = HeapArea(i1, -1); + equal = 1; + i1 += heapinfo1->busy_block.size; + } + } + + while (i2 < state.heaplimit && not equal) { + + addr_block2 = (ADDR2UINT(i2) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase; + + if (i2 == i1) { + i2++; + continue; + } + + const malloc_info* heapinfo2b = (const malloc_info*) MC_region_read(heap_region2, &heapinfo_temp2b, &heapinfos2[i2], sizeof(malloc_info)); + + if (heapinfo2b->type != MMALLOC_TYPE_UNFRAGMENTED) { + i2++; + continue; + } + + if (state.equals_to2_(i2, 0).valid_) { + i2++; + continue; + } + + int res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing, addr_block1, addr_block2, + snapshot1, snapshot2, nullptr, nullptr, 0); + + if (res_compare != 1) { + for (k = 1; k < heapinfo2b->busy_block.size; k++) + state.equals_to2_(i2 + k, 0) = HeapArea(i1, -1); + for (k = 1; k < heapinfo1->busy_block.size; k++) + state.equals_to1_(i1 + k, 0) = HeapArea(i2, -1); + equal = 1; + i1 += heapinfo1->busy_block.size; + } + + i2++; + } + + if (not equal) { + XBT_DEBUG("Block %zu not found (size_used = %zu, addr = %p)", i1, heapinfo1->busy_block.busy_size, addr_block1); + i1 = state.heaplimit + 1; + nb_diff1++; + } + + } else { /* Fragmented block */ + + for (j1 = 0; j1 < (size_t) (BLOCKSIZE >> heapinfo1->type); j1++) { + + if (heapinfo1->busy_frag.frag_size[j1] == -1) /* Free fragment_ */ + continue; + + if (state.equals_to1_(i1, j1).valid_) + continue; + + addr_frag1 = (void*)((char*)addr_block1 + (j1 << heapinfo1->type)); + + i2 = 1; + equal = 0; + + /* Try first to associate to same fragment_ in the other heap */ + if (heapinfo2->type == heapinfo1->type && not state.equals_to2_(i1, j1).valid_) { + addr_block2 = (ADDR2UINT(i1) - 1) * BLOCKSIZE + + (char *) state.std_heap_copy.heapbase; + addr_frag2 = + (void *) ((char *) addr_block2 + + (j1 << heapinfo2->type)); + int res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing, addr_frag1, addr_frag2, + snapshot1, snapshot2, nullptr, nullptr, 0); + if (res_compare != 1) + equal = 1; + } + + while (i2 < state.heaplimit && not equal) { + + const malloc_info* heapinfo2b = (const malloc_info*) MC_region_read( + heap_region2, &heapinfo_temp2b, &heapinfos2[i2], + sizeof(malloc_info)); + + if (heapinfo2b->type == MMALLOC_TYPE_FREE || heapinfo2b->type == MMALLOC_TYPE_HEAPINFO) { + i2 ++; + continue; + } + + // We currently do not match fragments with unfragmented blocks (maybe we should). + if (heapinfo2b->type == MMALLOC_TYPE_UNFRAGMENTED) { + i2++; + continue; + } + + if (heapinfo2b->type < 0) { + fprintf(stderr, "Unknown mmalloc block type.\n"); + abort(); + } + + for (j2 = 0; j2 < (size_t) (BLOCKSIZE >> heapinfo2b->type); + j2++) { + + if (i2 == i1 && j2 == j1) + continue; + + if (state.equals_to2_(i2, j2).valid_) + continue; + + addr_block2 = (ADDR2UINT(i2) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase; + addr_frag2 = (void*)((char*)addr_block2 + (j2 << heapinfo2b->type)); + + int res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing, addr_frag1, addr_frag2, + snapshot2, snapshot2, nullptr, nullptr, 0); + if (res_compare != 1) { + equal = 1; + break; + } + } + + i2++; + } + + if (not equal) { + XBT_DEBUG("Block %zu, fragment_ %zu not found (size_used = %zd, address = %p)\n", i1, j1, + heapinfo1->busy_frag.frag_size[j1], addr_frag1); + i1 = state.heaplimit + 1; + nb_diff1++; + break; + } + } + + i1++; + } + } + + /* All blocks/fragments are equal to another block/fragment_ ? */ + size_t i = 1; + size_t j = 0; + + for(i = 1; i < state.heaplimit; i++) { + const malloc_info* heapinfo1 = (const malloc_info*) MC_region_read( + heap_region1, &heapinfo_temp1, &heapinfos1[i], sizeof(malloc_info)); + + if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED && i1 == state.heaplimit && heapinfo1->busy_block.busy_size > 0 && + not state.equals_to1_(i, 0).valid_) { + XBT_DEBUG("Block %zu not found (size used = %zu)", i, heapinfo1->busy_block.busy_size); + nb_diff1++; + } + + if (heapinfo1->type <= 0) + continue; + for (j = 0; j < (size_t) (BLOCKSIZE >> heapinfo1->type); j++) + if (i1 == state.heaplimit && heapinfo1->busy_frag.frag_size[j] > 0 && not state.equals_to1_(i, j).valid_) { + XBT_DEBUG("Block %zu, Fragment %zu not found (size used = %zd)", i, j, heapinfo1->busy_frag.frag_size[j]); + nb_diff1++; + } + } + + if (i1 == state.heaplimit) + XBT_DEBUG("Number of blocks/fragments not found in heap1: %d", nb_diff1); + + for (i=1; i < state.heaplimit; i++) { + const malloc_info* heapinfo2 = (const malloc_info*) MC_region_read( + heap_region2, &heapinfo_temp2, &heapinfos2[i], sizeof(malloc_info)); + if (heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED && i1 == state.heaplimit && heapinfo2->busy_block.busy_size > 0 && + not state.equals_to2_(i, 0).valid_) { + XBT_DEBUG("Block %zu not found (size used = %zu)", i, + heapinfo2->busy_block.busy_size); + nb_diff2++; + } + + if (heapinfo2->type <= 0) + continue; + + for (j = 0; j < (size_t) (BLOCKSIZE >> heapinfo2->type); j++) + if (i1 == state.heaplimit && heapinfo2->busy_frag.frag_size[j] > 0 && not state.equals_to2_(i, j).valid_) { + XBT_DEBUG("Block %zu, Fragment %zu not found (size used = %zd)", + i, j, heapinfo2->busy_frag.frag_size[j]); + nb_diff2++; + } + + } + + if (i1 == state.heaplimit) + XBT_DEBUG("Number of blocks/fragments not found in heap2: %d", nb_diff2); + + return nb_diff1 > 0 || nb_diff2 > 0; +} + +/** + * + * @param state + * @param real_area1 Process address for state 1 + * @param real_area2 Process address for state 2 + * @param snapshot1 Snapshot of state 1 + * @param snapshot2 Snapshot of state 2 + * @param previous + * @param size + * @param check_ignore + */ +static int compare_heap_area_without_type( + simgrid::mc::StateComparator& state, int process_index, + const void *real_area1, const void *real_area2, + simgrid::mc::Snapshot* snapshot1, + simgrid::mc::Snapshot* snapshot2, + HeapLocationPairs* previous, int size, + int check_ignore) +{ + simgrid::mc::RemoteClient* process = &mc_model_checker->process(); + mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1); + mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2); + + for (int i = 0; i < size; ) { + + if (check_ignore > 0) { + ssize_t ignore1 = heap_comparison_ignore_size( + state.processStates[0].to_ignore, (char *) real_area1 + i); + if (ignore1 != -1) { + ssize_t ignore2 = heap_comparison_ignore_size( + state.processStates[1].to_ignore, (char *) real_area2 + i); + if (ignore2 == ignore1) { + if (ignore1 == 0) { + check_ignore--; + return 0; + } else { + i = i + ignore2; + check_ignore--; + continue; + } + } + } + } + + if (MC_snapshot_region_memcmp(((char *) real_area1) + i, heap_region1, ((char *) real_area2) + i, heap_region2, 1) != 0) { + + int pointer_align = (i / sizeof(void *)) * sizeof(void *); + const void* addr_pointed1 = snapshot1->read( + remote((void**)((char *) real_area1 + pointer_align)), process_index); + const void* addr_pointed2 = snapshot2->read( + remote((void**)((char *) real_area2 + pointer_align)), process_index); + + if (process->in_maestro_stack(remote(addr_pointed1)) + && process->in_maestro_stack(remote(addr_pointed2))) { + i = pointer_align + sizeof(void *); + continue; + } + + if (addr_pointed1 > state.std_heap_copy.heapbase + && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1) + && addr_pointed2 > state.std_heap_copy.heapbase + && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)) { + // Both addreses are in the heap: + int res_compare = compare_heap_area(state ,process_index, + addr_pointed1, addr_pointed2, + snapshot1, snapshot2, previous, nullptr, 0); + if (res_compare == 1) + return res_compare; + i = pointer_align + sizeof(void *); + continue; + } + + return 1; + } + + i++; + } + + return 0; +} + +/** + * + * @param state + * @param real_area1 Process address for state 1 + * @param real_area2 Process address for state 2 + * @param snapshot1 Snapshot of state 1 + * @param snapshot2 Snapshot of state 2 + * @param previous + * @param type + * @param area_size either a byte_size or an elements_count (?) + * @param check_ignore + * @param pointer_level + * @return 0 (same), 1 (different), -1 (unknown) + */ +static int compare_heap_area_with_type( + simgrid::mc::StateComparator& state, int process_index, + const void *real_area1, const void *real_area2, + simgrid::mc::Snapshot* snapshot1, + simgrid::mc::Snapshot* snapshot2, + HeapLocationPairs* previous, simgrid::mc::Type* type, + int area_size, int check_ignore, + int pointer_level) +{ + do { + + // HACK: This should not happen but in pratice, there are some + // DW_TAG_typedef without an associated DW_AT_type: + //<1><538832>: Abbrev Number: 111 (DW_TAG_typedef) + // <538833> DW_AT_name : (indirect string, offset: 0x2292f3): gregset_t + // <538837> DW_AT_decl_file : 98 + // <538838> DW_AT_decl_line : 37 + if (type == nullptr) + return 0; + + if (is_stack(real_area1) && is_stack(real_area2)) + return 0; + + if (check_ignore > 0) { + ssize_t ignore1 = heap_comparison_ignore_size(state.processStates[0].to_ignore, real_area1); + if (ignore1 > 0 && heap_comparison_ignore_size(state.processStates[1].to_ignore, real_area2) == ignore1) + return 0; + } + + simgrid::mc::Type* subtype; + simgrid::mc::Type* subsubtype; + int res; + int elm_size; + const void* addr_pointed1; + const void* addr_pointed2; + + mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1); + mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2); + + switch (type->type) { + case DW_TAG_unspecified_type: + return 1; + + case DW_TAG_base_type: + if (not type->name.empty() && type->name == "char") { /* String, hence random (arbitrary ?) size */ + if (real_area1 == real_area2) + return -1; + else + return MC_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, area_size) != 0; + } else { + if (area_size != -1 && type->byte_size != area_size) + return -1; + else + return MC_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, type->byte_size) != 0; + } + break; + + case DW_TAG_enumeration_type: + if (area_size != -1 && type->byte_size != area_size) + return -1; + return MC_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, type->byte_size) != 0; + + case DW_TAG_typedef: + case DW_TAG_const_type: + case DW_TAG_volatile_type: + // Poor man's TCO: + type = type->subtype; + continue; // restart + + case DW_TAG_array_type: + subtype = type->subtype; + switch (subtype->type) { + case DW_TAG_unspecified_type: + return 1; + + case DW_TAG_base_type: + case DW_TAG_enumeration_type: + case DW_TAG_pointer_type: + case DW_TAG_reference_type: + case DW_TAG_rvalue_reference_type: + case DW_TAG_structure_type: + case DW_TAG_class_type: + case DW_TAG_union_type: + if (subtype->full_type) + subtype = subtype->full_type; + elm_size = subtype->byte_size; + break; + // TODO, just remove the type indirection? + case DW_TAG_const_type: + case DW_TAG_typedef: + case DW_TAG_volatile_type: + subsubtype = subtype->subtype; + if (subsubtype->full_type) + subsubtype = subsubtype->full_type; + elm_size = subsubtype->byte_size; + break; + default: + return 0; + break; + } + for (int i = 0; i < type->element_count; i++) { + // TODO, add support for variable stride (DW_AT_byte_stride) + res = compare_heap_area_with_type(state, process_index, (char*)real_area1 + (i * elm_size), + (char*)real_area2 + (i * elm_size), snapshot1, snapshot2, previous, + type->subtype, subtype->byte_size, check_ignore, pointer_level); + if (res == 1) + return res; + } + return 0; + + case DW_TAG_reference_type: + case DW_TAG_rvalue_reference_type: + case DW_TAG_pointer_type: + if (type->subtype && type->subtype->type == DW_TAG_subroutine_type) { + addr_pointed1 = snapshot1->read(remote((void**)real_area1), process_index); + addr_pointed2 = snapshot2->read(remote((void**)real_area2), process_index); + return (addr_pointed1 != addr_pointed2); + } + pointer_level++; + if (pointer_level <= 1) { + addr_pointed1 = snapshot1->read(remote((void**)real_area1), process_index); + addr_pointed2 = snapshot2->read(remote((void**)real_area2), process_index); + if (addr_pointed1 > state.std_heap_copy.heapbase && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1) && + addr_pointed2 > state.std_heap_copy.heapbase && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)) + return compare_heap_area(state, process_index, addr_pointed1, addr_pointed2, snapshot1, snapshot2, previous, + type->subtype, pointer_level); + else + return (addr_pointed1 != addr_pointed2); + } + for (size_t i = 0; i < (area_size / sizeof(void*)); i++) { + addr_pointed1 = snapshot1->read(remote((void**)((char*)real_area1 + i * sizeof(void*))), process_index); + addr_pointed2 = snapshot2->read(remote((void**)((char*)real_area2 + i * sizeof(void*))), process_index); + if (addr_pointed1 > state.std_heap_copy.heapbase && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1) && + addr_pointed2 > state.std_heap_copy.heapbase && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)) + res = compare_heap_area(state, process_index, addr_pointed1, addr_pointed2, snapshot1, snapshot2, previous, + type->subtype, pointer_level); + else + res = (addr_pointed1 != addr_pointed2); + if (res == 1) + return res; + } + return 0; + + case DW_TAG_structure_type: + case DW_TAG_class_type: + if (type->full_type) + type = type->full_type; + if (area_size != -1 && type->byte_size != area_size) { + if (area_size <= type->byte_size || area_size % type->byte_size != 0) + return -1; + for (size_t i = 0; i < (size_t)(area_size / type->byte_size); i++) { + int res = compare_heap_area_with_type(state, process_index, (char*)real_area1 + i * type->byte_size, + (char*)real_area2 + i * type->byte_size, snapshot1, snapshot2, + previous, type, -1, check_ignore, 0); + if (res == 1) + return res; + } + } else { + for (simgrid::mc::Member& member : type->members) { + // TODO, optimize this? (for the offset case) + void* real_member1 = simgrid::dwarf::resolve_member(real_area1, type, &member, + (simgrid::mc::AddressSpace*)snapshot1, process_index); + void* real_member2 = simgrid::dwarf::resolve_member(real_area2, type, &member, + (simgrid::mc::AddressSpace*)snapshot2, process_index); + int res = compare_heap_area_with_type(state, process_index, real_member1, real_member2, snapshot1, + snapshot2, previous, member.type, -1, check_ignore, 0); + if (res == 1) + return res; + } + } + return 0; + + case DW_TAG_union_type: + return compare_heap_area_without_type(state, process_index, real_area1, real_area2, snapshot1, snapshot2, + previous, type->byte_size, check_ignore); + + default: + return 0; + } + + xbt_die("Unreachable"); + } while (true); +} + +/** Infer the type of a part of the block from the type of the block + * + * TODO, handle DW_TAG_array_type as well as arrays of the object ((*p)[5], p[5]) + * + * TODO, handle subfields ((*p).bar.foo, (*p)[5].bar…) + * + * @param type DWARF type ID of the root address + * @param area_size + * @return DWARF type ID for given offset + */ +static simgrid::mc::Type* get_offset_type(void *real_base_address, simgrid::mc::Type* type, + int offset, int area_size, + simgrid::mc::Snapshot* snapshot, int process_index) +{ + + // Beginning of the block, the infered variable type if the type of the block: + if (offset == 0) + return type; + + switch (type->type) { + + case DW_TAG_structure_type: + case DW_TAG_class_type: + if (type->full_type) + type = type->full_type; + if (area_size != -1 && type->byte_size != area_size) { + if (area_size > type->byte_size && area_size % type->byte_size == 0) + return type; + else + return nullptr; + } + + for (simgrid::mc::Member& member : type->members) { + if (member.has_offset_location()) { + // We have the offset, use it directly (shortcut): + if (member.offset() == offset) + return member.type; + } else { + void* real_member = simgrid::dwarf::resolve_member(real_base_address, type, &member, snapshot, process_index); + if ((char*)real_member - (char*)real_base_address == offset) + return member.type; + } + } + return nullptr; + + default: + /* FIXME: other cases ? */ + return nullptr; + + } +} + +/** + * + * @param area1 Process address for state 1 + * @param area2 Process address for state 2 + * @param snapshot1 Snapshot of state 1 + * @param snapshot2 Snapshot of state 2 + * @param previous Pairs of blocks already compared on the current path (or nullptr) + * @param type_id Type of variable + * @param pointer_level + * @return 0 (same), 1 (different), -1 + */ +static +int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, + const void *area1, const void *area2, + simgrid::mc::Snapshot* snapshot1, + simgrid::mc::Snapshot* snapshot2, + HeapLocationPairs* previous, + simgrid::mc::Type* type, int pointer_level) +{ + simgrid::mc::RemoteClient* process = &mc_model_checker->process(); + + ssize_t block1; + ssize_t block2; + ssize_t size; + int check_ignore = 0; + + int type_size = -1; + int offset1 = 0; + int offset2 = 0; + int new_size1 = -1; + int new_size2 = -1; + + simgrid::mc::Type* new_type1 = nullptr; + simgrid::mc::Type* new_type2 = nullptr; + + bool match_pairs = false; + + // This is the address of std_heap->heapinfo in the application process: + void* heapinfo_address = &((xbt_mheap_t) process->heap_address)->heapinfo; + + const malloc_info* heapinfos1 = snapshot1->read(remote((const malloc_info**)heapinfo_address), process_index); + const malloc_info* heapinfos2 = snapshot2->read(remote((const malloc_info**)heapinfo_address), process_index); + + malloc_info heapinfo_temp1; + malloc_info heapinfo_temp2; + + simgrid::mc::HeapLocationPairs current; + if (previous == nullptr) { + previous = ¤t; + match_pairs = true; + } + + // Get block number: + block1 = ((char*)area1 - (char*)state.std_heap_copy.heapbase) / BLOCKSIZE + 1; + block2 = ((char*)area2 - (char*)state.std_heap_copy.heapbase) / BLOCKSIZE + 1; + + // If either block is a stack block: + if (is_block_stack((int) block1) && is_block_stack((int) block2)) { + previous->insert(simgrid::mc::makeHeapLocationPair(block1, -1, block2, -1)); + if (match_pairs) + state.match_equals(previous); + return 0; + } + + // If either block is not in the expected area of memory: + if (((char*)area1 < (char*)state.std_heap_copy.heapbase) || (block1 > (ssize_t)state.processStates[0].heapsize) || + (block1 < 1) || ((char*)area2 < (char*)state.std_heap_copy.heapbase) || + (block2 > (ssize_t)state.processStates[1].heapsize) || (block2 < 1)) { + return 1; + } + + // Process address of the block: + void* real_addr_block1 = (ADDR2UINT(block1) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase; + void* real_addr_block2 = (ADDR2UINT(block2) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase; + + if (type) { + if (type->full_type) + type = type->full_type; + + // This assume that for "boring" types (volatile ...) byte_size is absent: + while (type->byte_size == 0 && type->subtype != nullptr) + type = type->subtype; + + // Find type_size: + if (type->type == DW_TAG_pointer_type || + (type->type == DW_TAG_base_type && not type->name.empty() && type->name == "char")) + type_size = -1; + else + type_size = type->byte_size; + + } + + mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1); + mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2); + + const malloc_info* heapinfo1 = (const malloc_info*) MC_region_read( + heap_region1, &heapinfo_temp1, &heapinfos1[block1], sizeof(malloc_info)); + const malloc_info* heapinfo2 = (const malloc_info*) MC_region_read( + heap_region2, &heapinfo_temp2, &heapinfos2[block2], sizeof(malloc_info)); + + if ((heapinfo1->type == MMALLOC_TYPE_FREE || heapinfo1->type==MMALLOC_TYPE_HEAPINFO) + && (heapinfo2->type == MMALLOC_TYPE_FREE || heapinfo2->type ==MMALLOC_TYPE_HEAPINFO)) { + /* Free block */ + if (match_pairs) + state.match_equals(previous); + return 0; + } + + if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED && heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED) { + /* Complete block */ + + // TODO, lookup variable type from block type as done for fragmented blocks + + if (state.equals_to1_(block1, 0).valid_ && state.equals_to2_(block2, 0).valid_ && + state.blocksEqual(block1, block2)) { + if (match_pairs) + state.match_equals(previous); + return 0; + } + + if (type_size != -1 && type_size != (ssize_t)heapinfo1->busy_block.busy_size && + type_size != (ssize_t)heapinfo2->busy_block.busy_size && + (type->name.empty() || type->name == "struct s_smx_context")) { + if (match_pairs) + state.match_equals(previous); + return -1; + } + + if (heapinfo1->busy_block.size != heapinfo2->busy_block.size) + return 1; + if (heapinfo1->busy_block.busy_size != heapinfo2->busy_block.busy_size) + return 1; + + if (not previous->insert(simgrid::mc::makeHeapLocationPair(block1, -1, block2, -1)).second) { + if (match_pairs) + state.match_equals(previous); + return 0; + } + + size = heapinfo1->busy_block.busy_size; + + // Remember (basic) type inference. + // The current data structure only allows us to do this for the whole block. + if (type != nullptr && area1 == real_addr_block1) + state.types1_(block1, 0) = type; + if (type != nullptr && area2 == real_addr_block2) + state.types2_(block2, 0) = type; + + if (size <= 0) { + if (match_pairs) + state.match_equals(previous); + return 0; + } + + if (heapinfo1->busy_block.ignore > 0 + && heapinfo2->busy_block.ignore == heapinfo1->busy_block.ignore) + check_ignore = heapinfo1->busy_block.ignore; + + } else if ((heapinfo1->type > 0) && (heapinfo2->type > 0)) { /* Fragmented block */ + + // Fragment number: + ssize_t frag1 = ((uintptr_t)(ADDR2UINT(area1) % (BLOCKSIZE))) >> heapinfo1->type; + ssize_t frag2 = ((uintptr_t)(ADDR2UINT(area2) % (BLOCKSIZE))) >> heapinfo2->type; + + // Process address of the fragment_: + void* real_addr_frag1 = (void*)((char*)real_addr_block1 + (frag1 << heapinfo1->type)); + void* real_addr_frag2 = (void*)((char*)real_addr_block2 + (frag2 << heapinfo2->type)); + + // Check the size of the fragments against the size of the type: + if (type_size != -1) { + if (heapinfo1->busy_frag.frag_size[frag1] == -1 || heapinfo2->busy_frag.frag_size[frag2] == -1) { + if (match_pairs) + state.match_equals(previous); + return -1; + } + // ? + if (type_size != heapinfo1->busy_frag.frag_size[frag1] + || type_size != heapinfo2->busy_frag.frag_size[frag2]) { + if (match_pairs) + state.match_equals(previous); + return -1; + } + } + + // Check if the blocks are already matched together: + if (state.equals_to1_(block1, frag1).valid_ && state.equals_to2_(block2, frag2).valid_ && offset1 == offset2 && + state.fragmentsEqual(block1, frag1, block2, frag2)) { + if (match_pairs) + state.match_equals(previous); + return 0; + } + // Compare the size of both fragments: + if (heapinfo1->busy_frag.frag_size[frag1] != heapinfo2->busy_frag.frag_size[frag2]) { + if (type_size == -1) { + if (match_pairs) + state.match_equals(previous); + return -1; + } else + return 1; + } + + // Size of the fragment_: + size = heapinfo1->busy_frag.frag_size[frag1]; + + // Remember (basic) type inference. + // The current data structure only allows us to do this for the whole fragment_. + if (type != nullptr && area1 == real_addr_frag1) + state.types1_(block1, frag1) = type; + if (type != nullptr && area2 == real_addr_frag2) + state.types2_(block2, frag2) = type; + + // The type of the variable is already known: + if (type) { + new_type1 = new_type2 = type; + } + // Type inference from the block type. + else if (state.types1_(block1, frag1) != nullptr || state.types2_(block2, frag2) != nullptr) { + + offset1 = (char*)area1 - (char*)real_addr_frag1; + offset2 = (char*)area2 - (char*)real_addr_frag2; + + if (state.types1_(block1, frag1) != nullptr && state.types2_(block2, frag2) != nullptr) { + new_type1 = + get_offset_type(real_addr_frag1, state.types1_(block1, frag1), offset1, size, snapshot1, process_index); + new_type2 = + get_offset_type(real_addr_frag2, state.types2_(block2, frag2), offset1, size, snapshot2, process_index); + } else if (state.types1_(block1, frag1) != nullptr) { + new_type1 = + get_offset_type(real_addr_frag1, state.types1_(block1, frag1), offset1, size, snapshot1, process_index); + new_type2 = + get_offset_type(real_addr_frag2, state.types1_(block1, frag1), offset2, size, snapshot2, process_index); + } else if (state.types2_(block2, frag2) != nullptr) { + new_type1 = + get_offset_type(real_addr_frag1, state.types2_(block2, frag2), offset1, size, snapshot1, process_index); + new_type2 = + get_offset_type(real_addr_frag2, state.types2_(block2, frag2), offset2, size, snapshot2, process_index); + } else { + if (match_pairs) + state.match_equals(previous); + return -1; + } + + if (new_type1 != nullptr && new_type2 != nullptr && new_type1 != new_type2) { + + type = new_type1; + while (type->byte_size == 0 && type->subtype != nullptr) + type = type->subtype; + new_size1 = type->byte_size; + + type = new_type2; + while (type->byte_size == 0 && type->subtype != nullptr) + type = type->subtype; + new_size2 = type->byte_size; + + } else { + if (match_pairs) + state.match_equals(previous); + return -1; + } + } + + if (new_size1 > 0 && new_size1 == new_size2) { + type = new_type1; + size = new_size1; + } + + if (offset1 == 0 && offset2 == 0 && + not previous->insert(simgrid::mc::makeHeapLocationPair(block1, frag1, block2, frag2)).second) { + if (match_pairs) + state.match_equals(previous); + return 0; + } + + if (size <= 0) { + if (match_pairs) + state.match_equals(previous); + return 0; + } + + if ((heapinfo1->busy_frag.ignore[frag1] > 0) && + (heapinfo2->busy_frag.ignore[frag2] == heapinfo1->busy_frag.ignore[frag1])) + check_ignore = heapinfo1->busy_frag.ignore[frag1]; + + } else + return 1; + + + /* Start comparison */ + int res_compare; + if (type) + res_compare = compare_heap_area_with_type(state, process_index, area1, area2, snapshot1, snapshot2, previous, type, + size, check_ignore, pointer_level); + else + res_compare = compare_heap_area_without_type(state, process_index, area1, area2, snapshot1, snapshot2, previous, + size, check_ignore); + + if (res_compare == 1) + return res_compare; + + if (match_pairs) + state.match_equals(previous); + return 0; +} + +} +} + +/************************** Snapshot comparison *******************************/ +/******************************************************************************/ + +static int compare_areas_with_type(simgrid::mc::StateComparator& state, + int process_index, + void* real_area1, simgrid::mc::Snapshot* snapshot1, mc_mem_region_t region1, + void* real_area2, simgrid::mc::Snapshot* snapshot2, mc_mem_region_t region2, + simgrid::mc::Type* type, int pointer_level) +{ + simgrid::mc::RemoteClient* process = &mc_model_checker->process(); + + simgrid::mc::Type* subtype; + simgrid::mc::Type* subsubtype; + int elm_size; + int i; + int res; + + do { + switch (type->type) { + case DW_TAG_unspecified_type: + return 1; + + case DW_TAG_base_type: + case DW_TAG_enumeration_type: + case DW_TAG_union_type: + return MC_snapshot_region_memcmp(real_area1, region1, real_area2, region2, type->byte_size) != 0; + case DW_TAG_typedef: + case DW_TAG_volatile_type: + case DW_TAG_const_type: + // Poor man's TCO: + type = type->subtype; + continue; // restart + case DW_TAG_array_type: + subtype = type->subtype; + switch (subtype->type) { + case DW_TAG_unspecified_type: + return 1; + + case DW_TAG_base_type: + case DW_TAG_enumeration_type: + case DW_TAG_pointer_type: + case DW_TAG_reference_type: + case DW_TAG_rvalue_reference_type: + case DW_TAG_structure_type: + case DW_TAG_class_type: + case DW_TAG_union_type: + if (subtype->full_type) + subtype = subtype->full_type; + elm_size = subtype->byte_size; + break; + case DW_TAG_const_type: + case DW_TAG_typedef: + case DW_TAG_volatile_type: + subsubtype = subtype->subtype; + if (subsubtype->full_type) + subsubtype = subsubtype->full_type; + elm_size = subsubtype->byte_size; + break; + default: + return 0; + break; + } + for (i = 0; i < type->element_count; i++) { + size_t off = i * elm_size; + res = compare_areas_with_type(state, process_index, (char*)real_area1 + off, snapshot1, region1, + (char*)real_area2 + off, snapshot2, region2, type->subtype, pointer_level); + if (res == 1) + return res; + } + break; + case DW_TAG_pointer_type: + case DW_TAG_reference_type: + case DW_TAG_rvalue_reference_type: { + void* addr_pointed1 = MC_region_read_pointer(region1, real_area1); + void* addr_pointed2 = MC_region_read_pointer(region2, real_area2); + + if (type->subtype && type->subtype->type == DW_TAG_subroutine_type) + return (addr_pointed1 != addr_pointed2); + if (addr_pointed1 == nullptr && addr_pointed2 == nullptr) + return 0; + if (addr_pointed1 == nullptr || addr_pointed2 == nullptr) + return 1; + if (not state.compared_pointers.insert(std::make_pair(addr_pointed1, addr_pointed2)).second) + return 0; + + pointer_level++; + + // Some cases are not handled here: + // * the pointers lead to different areas (one to the heap, the other to the RW segment ...) + // * a pointer leads to the read-only segment of the current object + // * a pointer lead to a different ELF object + + if (addr_pointed1 > process->heap_address && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)) { + if (not(addr_pointed2 > process->heap_address && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2))) + return 1; + // The pointers are both in the heap: + return simgrid::mc::compare_heap_area(state, process_index, addr_pointed1, addr_pointed2, snapshot1, + snapshot2, nullptr, type->subtype, pointer_level); + + } else if (region1->contain(simgrid::mc::remote(addr_pointed1))) { + // The pointers are both in the current object R/W segment: + if (not region2->contain(simgrid::mc::remote(addr_pointed2))) + return 1; + if (not type->type_id) + return (addr_pointed1 != addr_pointed2); + else + return compare_areas_with_type(state, process_index, addr_pointed1, snapshot1, region1, addr_pointed2, + snapshot2, region2, type->subtype, pointer_level); + } else { + + // TODO, We do not handle very well the case where + // it belongs to a different (non-heap) region from the current one. + + return (addr_pointed1 != addr_pointed2); + } + break; + } + case DW_TAG_structure_type: + case DW_TAG_class_type: + for (simgrid::mc::Member& member : type->members) { + void* member1 = simgrid::dwarf::resolve_member(real_area1, type, &member, snapshot1, process_index); + void* member2 = simgrid::dwarf::resolve_member(real_area2, type, &member, snapshot2, process_index); + mc_mem_region_t subregion1 = mc_get_region_hinted(member1, snapshot1, process_index, region1); + mc_mem_region_t subregion2 = mc_get_region_hinted(member2, snapshot2, process_index, region2); + res = compare_areas_with_type(state, process_index, member1, snapshot1, subregion1, member2, snapshot2, + subregion2, member.type, pointer_level); + if (res == 1) + return res; + } + break; + case DW_TAG_subroutine_type: + return -1; + break; + default: + XBT_VERB("Unknown case: %d", type->type); + break; + } + + return 0; + } while (true); +} + +static int compare_global_variables( + simgrid::mc::StateComparator& state, + simgrid::mc::ObjectInformation* object_info, + int process_index, + mc_mem_region_t r1, mc_mem_region_t r2, + simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2) +{ + xbt_assert(r1 && r2, "Missing region."); + +#if HAVE_SMPI + if (r1->storage_type() == simgrid::mc::StorageType::Privatized) { + xbt_assert(process_index >= 0); + if (r2->storage_type() != simgrid::mc::StorageType::Privatized) + return 1; + + size_t process_count = MC_smpi_process_count(); + xbt_assert(process_count == r1->privatized_data().size() + && process_count == r2->privatized_data().size()); + + // Compare the global variables separately for each simulates process: + for (size_t process_index = 0; process_index < process_count; process_index++) { + if (compare_global_variables(state, + object_info, process_index, + &r1->privatized_data()[process_index], + &r2->privatized_data()[process_index], + snapshot1, snapshot2)) + return 1; + } + return 0; + } +#else + xbt_assert(r1->storage_type() != simgrid::mc::StorageType::Privatized); +#endif + xbt_assert(r2->storage_type() != simgrid::mc::StorageType::Privatized); + + std::vector& variables = object_info->global_variables; + + for (simgrid::mc::Variable const& current_var : variables) { + + // If the variable is not in this object, skip it: + // We do not expect to find a pointer to something which is not reachable + // by the global variables. + if ((char *) current_var.address < (char *) object_info->start_rw + || (char *) current_var.address > (char *) object_info->end_rw) + continue; + + simgrid::mc::Type* bvariable_type = current_var.type; + int res = compare_areas_with_type(state, process_index, + (char *) current_var.address, snapshot1, r1, + (char *) current_var.address, snapshot2, r2, + bvariable_type, 0); + if (res == 1) { + XBT_VERB("Global variable %s (%p) is different between snapshots", + current_var.name.c_str(), + (char *) current_var.address); + return 1; + } + } + + return 0; +} + +static int compare_local_variables(simgrid::mc::StateComparator& state, + int process_index, + simgrid::mc::Snapshot* snapshot1, + simgrid::mc::Snapshot* snapshot2, + mc_snapshot_stack_t stack1, + mc_snapshot_stack_t stack2) +{ + if (stack1->local_variables.size() != stack2->local_variables.size()) { + XBT_VERB("Different number of local variables"); + return 1; + } + + unsigned int cursor = 0; + local_variable_t current_var1; + local_variable_t current_var2; + while (cursor < stack1->local_variables.size()) { + current_var1 = &stack1->local_variables[cursor]; + current_var2 = &stack1->local_variables[cursor]; + if (current_var1->name != current_var2->name + || current_var1->subprogram != current_var2->subprogram + || current_var1->ip != current_var2->ip) { + // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram + XBT_VERB + ("Different name of variable (%s - %s) " + "or frame (%s - %s) or ip (%lu - %lu)", + current_var1->name.c_str(), + current_var2->name.c_str(), + current_var1->subprogram->name.c_str(), + current_var2->subprogram->name.c_str(), + current_var1->ip, current_var2->ip); + return 1; + } + // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram + + simgrid::mc::Type* subtype = current_var1->type; + int res = compare_areas_with_type( + state, process_index, current_var1->address, snapshot1, + mc_get_snapshot_region(current_var1->address, snapshot1, process_index), current_var2->address, snapshot2, + mc_get_snapshot_region(current_var2->address, snapshot2, process_index), subtype, 0); + + if (res == 1) { + // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram + XBT_VERB("Local variable %s (%p - %p) in frame %s " + "is different between snapshots", + current_var1->name.c_str(), current_var1->address, current_var2->address, + current_var1->subprogram->name.c_str()); + return res; + } + cursor++; + } + return 0; +} + +namespace simgrid { +namespace mc { + +static std::unique_ptr state_comparator; + +int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc::Snapshot* s2) +{ + // TODO, make this a field of ModelChecker or something similar + + if (state_comparator == nullptr) + state_comparator = std::unique_ptr(new StateComparator()); + else + state_comparator->clear(); + + simgrid::mc::RemoteClient* process = &mc_model_checker->process(); + + int errors = 0; + + int hash_result = 0; + if (_sg_mc_hash) { + hash_result = (s1->hash != s2->hash); + if (hash_result) { + XBT_VERB("(%d - %d) Different hash: 0x%" PRIx64 "--0x%" PRIx64, num1, num2, s1->hash, s2->hash); +#ifndef MC_DEBUG + return 1; +#endif + } else + XBT_VERB("(%d - %d) Same hash: 0x%" PRIx64, num1, num2, s1->hash); + } + + /* Compare enabled processes */ + if (s1->enabled_processes != s2->enabled_processes) { + XBT_VERB("(%d - %d) Different amount of enabled processes", num1, num2); + return 1; + } + + /* Compare size of stacks */ + int is_diff = 0; + for (unsigned long i = 0; i < s1->stacks.size(); i++) { + size_t size_used1 = s1->stack_sizes[i]; + size_t size_used2 = s2->stack_sizes[i]; + if (size_used1 != size_used2) { +#ifdef MC_DEBUG + XBT_DEBUG("(%d - %d) Different size used in stacks: %zu - %zu", num1, num2, size_used1, size_used2); + errors++; + is_diff = 1; +#else +#ifdef MC_VERBOSE + XBT_VERB("(%d - %d) Different size used in stacks: %zu - %zu", num1, num2, size_used1, size_used2); +#endif + return 1; +#endif + } + } + if (is_diff) // do not proceed if there is any stacks that don't match + return 1; + + /* Init heap information used in heap comparison algorithm */ + xbt_mheap_t heap1 = (xbt_mheap_t)s1->read_bytes( + alloca(sizeof(struct mdesc)), sizeof(struct mdesc), + remote(process->heap_address), + simgrid::mc::ProcessIndexMissing, simgrid::mc::ReadOptions::lazy()); + xbt_mheap_t heap2 = (xbt_mheap_t)s2->read_bytes( + alloca(sizeof(struct mdesc)), sizeof(struct mdesc), + remote(process->heap_address), + simgrid::mc::ProcessIndexMissing, simgrid::mc::ReadOptions::lazy()); + int res_init = state_comparator->initHeapInformation(heap1, heap2, &s1->to_ignore, &s2->to_ignore); + + if (res_init == -1) { +#ifdef MC_DEBUG + XBT_DEBUG("(%d - %d) Different heap information", num1, num2); + errors++; +#else +#ifdef MC_VERBOSE + XBT_VERB("(%d - %d) Different heap information", num1, num2); +#endif + + return 1; +#endif + } + + /* Stacks comparison */ + int diff_local = 0; + for (unsigned int cursor = 0; cursor < s1->stacks.size(); cursor++) { + mc_snapshot_stack_t stack1 = &s1->stacks[cursor]; + mc_snapshot_stack_t stack2 = &s2->stacks[cursor]; + + if (stack1->process_index != stack2->process_index) { + diff_local = 1; + XBT_DEBUG("(%d - %d) Stacks with different process index (%i vs %i)", num1, num2, + stack1->process_index, stack2->process_index); + } + else diff_local = compare_local_variables(*state_comparator, + stack1->process_index, s1, s2, stack1, stack2); + if (diff_local > 0) { +#ifdef MC_DEBUG + XBT_DEBUG("(%d - %d) Different local variables between stacks %d", num1, + num2, cursor + 1); + errors++; +#else + +#ifdef MC_VERBOSE + XBT_VERB("(%d - %d) Different local variables between stacks %u", num1, num2, cursor + 1); +#endif + + return 1; +#endif + } + } + + size_t regions_count = s1->snapshot_regions.size(); + // TODO, raise a difference instead? + xbt_assert(regions_count == s2->snapshot_regions.size()); + + for (size_t k = 0; k != regions_count; ++k) { + mc_mem_region_t region1 = s1->snapshot_regions[k].get(); + mc_mem_region_t region2 = s2->snapshot_regions[k].get(); + + // Preconditions: + if (region1->region_type() != simgrid::mc::RegionType::Data) + continue; + + xbt_assert(region1->region_type() == region2->region_type()); + xbt_assert(region1->object_info() == region2->object_info()); + xbt_assert(region1->object_info()); + + std::string const& name = region1->object_info()->file_name; + + /* Compare global variables */ + if (compare_global_variables(*state_comparator, region1->object_info(), simgrid::mc::ProcessIndexDisabled, region1, + region2, s1, s2)) { + +#ifdef MC_DEBUG + XBT_DEBUG("(%d - %d) Different global variables in %s", + num1, num2, name.c_str()); + errors++; +#else +#ifdef MC_VERBOSE + XBT_VERB("(%d - %d) Different global variables in %s", + num1, num2, name.c_str()); +#endif + + return 1; +#endif + } + } + + /* Compare heap */ + if (simgrid::mc::mmalloc_compare_heap(*state_comparator, s1, s2) > 0) { + +#ifdef MC_DEBUG + XBT_DEBUG("(%d - %d) Different heap (mmalloc_compare)", num1, num2); + errors++; +#else + +#ifdef MC_VERBOSE + XBT_VERB("(%d - %d) Different heap (mmalloc_compare)", num1, num2); +#endif + return 1; +#endif + } + +#ifdef MC_VERBOSE + if (errors || hash_result) + XBT_VERB("(%d - %d) Difference found", num1, num2); + else + XBT_VERB("(%d - %d) No difference found", num1, num2); +#endif + +#if defined(MC_DEBUG) && defined(MC_VERBOSE) + if (_sg_mc_hash) { + // * false positive SHOULD be avoided. + // * There MUST not be any false negative. + + XBT_VERB("(%d - %d) State equality hash test is %s %s", num1, num2, + (hash_result != 0) == (errors != 0) ? "true" : "false", not hash_result ? "positive" : "negative"); + } +#endif + + return errors > 0 || hash_result; +} + +} +} diff --git a/src/mc/snapshot/mc_checkpoint.cpp b/src/mc/snapshot/mc_checkpoint.cpp new file mode 100644 index 0000000000..56218a82f3 --- /dev/null +++ b/src/mc/snapshot/mc_checkpoint.cpp @@ -0,0 +1,695 @@ +/* Copyright (c) 2008-2018. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include + +#include +#include +#include +#include + +#ifndef WIN32 +#include +#endif + +#include "src/internal_config.h" +#include "src/mc/mc_private.hpp" +#include "src/smpi/include/private.hpp" +#include "xbt/file.hpp" +#include "xbt/mmalloc.h" +#include "xbt/module.h" + +#include "src/xbt/mmalloc/mmprivate.h" + +#include "src/simix/smx_private.hpp" + +#include +#include + +#include "src/mc/mc_private.hpp" +#include + +#include "src/mc/mc_config.hpp" +#include "src/mc/mc_hash.hpp" +#include "src/mc/mc_mmu.hpp" +#include "src/mc/mc_smx.hpp" +#include "src/mc/mc_snapshot.hpp" +#include "src/mc/mc_unw.hpp" +#include "src/mc/remote/mc_protocol.h" + +#include "src/mc/RegionSnapshot.hpp" +#include "src/mc/ObjectInformation.hpp" +#include "src/mc/Frame.hpp" +#include "src/mc/Variable.hpp" + +using simgrid::mc::remote; + +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_checkpoint, mc, "Logging specific to mc_checkpoint"); + +#define PROT_RWX (PROT_READ | PROT_WRITE | PROT_EXEC) +#define PROT_RW (PROT_READ | PROT_WRITE) +#define PROT_RX (PROT_READ | PROT_EXEC) + +namespace simgrid { +namespace mc { + +/************************************ Free functions **************************************/ +/*****************************************************************************************/ + +/** @brief Restore a region from a snapshot + * + * @param region Target region + */ +static void restore(mc_mem_region_t region) +{ + switch(region->storage_type()) { + case simgrid::mc::StorageType::Flat: + mc_model_checker->process().write_bytes(region->flat_data().get(), + region->size(), region->permanent_address()); + break; + + case simgrid::mc::StorageType::Chunked: + mc_region_restore_sparse(&mc_model_checker->process(), region); + break; + + case simgrid::mc::StorageType::Privatized: + for (auto& p : region->privatized_data()) + restore(&p); + break; + + default: // includes StorageType::NoData + xbt_die("Storage type not supported"); + break; + } +} + +#if HAVE_SMPI +RegionSnapshot privatized_region( + RegionType region_type, void *start_addr, void* permanent_addr, + std::size_t size + ) +{ + size_t process_count = MC_smpi_process_count(); + + // Read smpi_privatization_regions from MCed: + smpi_privatization_region_t remote_smpi_privatization_regions; + mc_model_checker->process().read_variable( + "smpi_privatization_regions", + &remote_smpi_privatization_regions, sizeof(remote_smpi_privatization_regions)); + s_smpi_privatization_region_t privatization_regions[process_count]; + mc_model_checker->process().read_bytes( + &privatization_regions, sizeof(privatization_regions), + remote(remote_smpi_privatization_regions)); + + std::vector data; + data.reserve(process_count); + for (size_t i = 0; i < process_count; i++) + data.push_back(simgrid::mc::region(region_type, start_addr, + privatization_regions[i].address, size)); + + simgrid::mc::RegionSnapshot region = simgrid::mc::RegionSnapshot( + region_type, start_addr, permanent_addr, size); + region.privatized_data(std::move(data)); + return region; +} +#endif + +static +void add_region(int index, simgrid::mc::Snapshot* snapshot, + simgrid::mc::RegionType type, + simgrid::mc::ObjectInformation* object_info, + void *start_addr, void* permanent_addr, + std::size_t size) +{ + if (type == simgrid::mc::RegionType::Data) + xbt_assert(object_info, "Missing object info for object."); + else if (type == simgrid::mc::RegionType::Heap) + xbt_assert(not object_info, "Unexpected object info for heap region."); + + simgrid::mc::RegionSnapshot region; +#if HAVE_SMPI + const bool privatization_aware = object_info + && mc_model_checker->process().privatized(*object_info); + if (privatization_aware && MC_smpi_process_count()) + region = simgrid::mc::privatized_region( + type, start_addr, permanent_addr, size); + else +#endif + region = simgrid::mc::region(type, start_addr, permanent_addr, size); + + region.object_info(object_info); + snapshot->snapshot_regions[index] + = std::unique_ptr( + new simgrid::mc::RegionSnapshot(std::move(region))); +} + +static void get_memory_regions(simgrid::mc::RemoteClient* process, simgrid::mc::Snapshot* snapshot) +{ + const size_t n = process->object_infos.size(); + snapshot->snapshot_regions.resize(n + 1); + int i = 0; + for (auto const& object_info : process->object_infos) + add_region(i++, snapshot, simgrid::mc::RegionType::Data, + object_info.get(), + object_info->start_rw, object_info->start_rw, + object_info->end_rw - object_info->start_rw); + + xbt_mheap_t heap = process->get_heap(); + void *start_heap = heap->base; + void *end_heap = heap->breakval; + + add_region(n, snapshot, simgrid::mc::RegionType::Heap, nullptr, + start_heap, start_heap, + (char *) end_heap - (char *) start_heap); + snapshot->heap_bytes_used = mmalloc_get_bytes_used_remote( + heap->heaplimit, + process->get_malloc_info()); + +#if HAVE_SMPI + if (mc_model_checker->process().privatized() && MC_smpi_process_count()) + // snapshot->privatization_index = smpi_loaded_page + mc_model_checker->process().read_variable( + "smpi_loaded_page", &snapshot->privatization_index, + sizeof(snapshot->privatization_index)); + else +#endif + snapshot->privatization_index = simgrid::mc::ProcessIndexMissing; +} + +/** \brief Fills the position of the segments (executable, read-only, read/write). + * */ +// TODO, use the ELF segment information for more robustness +void find_object_address( + std::vector const& maps, + simgrid::mc::ObjectInformation* result) +{ + std::string name = simgrid::xbt::Path(result->file_name).get_base_name(); + + for (size_t i = 0; i < maps.size(); ++i) { + simgrid::xbt::VmMap const& reg = maps[i]; + if (maps[i].pathname.empty()) + continue; + std::string map_basename = simgrid::xbt::Path(maps[i].pathname).get_base_name(); + if (map_basename != name) + continue; + + // This is the non-GNU_RELRO-part of the data segment: + if (reg.prot == PROT_RW) { + xbt_assert(not result->start_rw, "Multiple read-write segments for %s, not supported", maps[i].pathname.c_str()); + result->start_rw = (char*) reg.start_addr; + result->end_rw = (char*) reg.end_addr; + + // The next VMA might be end of the data segment: + if (i + 1 < maps.size() + && maps[i + 1].pathname.empty() + && maps[i + 1].prot == PROT_RW + && maps[i + 1].start_addr == reg.end_addr) + result->end_rw = (char*) maps[i + 1].end_addr; + } + + // This is the text segment: + else if (reg.prot == PROT_RX) { + xbt_assert(not result->start_exec, "Multiple executable segments for %s, not supported", + maps[i].pathname.c_str()); + result->start_exec = (char*) reg.start_addr; + result->end_exec = (char*) reg.end_addr; + + // The next VMA might be end of the data segment: + if (i + 1 < maps.size() + && maps[i + 1].pathname.empty() + && maps[i + 1].prot == PROT_RW + && maps[i + 1].start_addr == reg.end_addr) { + result->start_rw = (char*) maps[i + 1].start_addr; + result->end_rw = (char*) maps[i + 1].end_addr; + } + } + + // This is the GNU_RELRO-part of the data segment: + else if (reg.prot == PROT_READ) { + xbt_assert(not result->start_ro, "Multiple read only segments for %s, not supported", maps[i].pathname.c_str()); + result->start_ro = (char*) reg.start_addr; + result->end_ro = (char*) reg.end_addr; + } + } + + result->start = result->start_rw; + if ((const void*) result->start_ro < result->start) + result->start = result->start_ro; + if ((const void*) result->start_exec < result->start) + result->start = result->start_exec; + + result->end = result->end_rw; + if (result->end_ro && (const void*) result->end_ro > result->end) + result->end = result->end_ro; + if (result->end_exec && (const void*) result->end_exec > result->end) + result->end = result->end_exec; + + xbt_assert(result->start_exec || result->start_rw || result->start_ro); +} + +/************************************* Take Snapshot ************************************/ +/****************************************************************************************/ + +/** \brief Checks whether the variable is in scope for a given IP. + * + * A variable may be defined only from a given value of IP. + * + * \param var Variable description + * \param scope Scope description + * \param ip Instruction pointer + * \return true if the variable is valid + * */ +static bool valid_variable(simgrid::mc::Variable* var, + simgrid::mc::Frame* scope, + const void *ip) +{ + // The variable is not yet valid: + if (scope->range.begin() + var->start_scope > (std::uint64_t) ip) + return false; + else + return true; +} + +static void fill_local_variables_values(mc_stack_frame_t stack_frame, simgrid::mc::Frame* scope, int process_index, + std::vector& result) +{ + simgrid::mc::RemoteClient* process = &mc_model_checker->process(); + + if (not scope || not scope->range.contain(stack_frame->ip)) + return; + + for (simgrid::mc::Variable& current_variable : scope->variables) { + + if (not valid_variable(¤t_variable, scope, (void*)stack_frame->ip)) + continue; + + int region_type; + // FIXME, get rid of `region_type` + if ((long) stack_frame->ip > (long) process->libsimgrid_info->start_exec) + region_type = 1; + else + region_type = 2; + + s_local_variable_t new_var; + new_var.subprogram = stack_frame->frame; + new_var.ip = stack_frame->ip; + new_var.name = current_variable.name; + new_var.type = current_variable.type; + new_var.region = region_type; + new_var.address = nullptr; + + if (current_variable.address != nullptr) + new_var.address = current_variable.address; + else if (not current_variable.location_list.empty()) { + simgrid::dwarf::Location location = + simgrid::dwarf::resolve( + current_variable.location_list, + current_variable.object_info, + &(stack_frame->unw_cursor), + (void *) stack_frame->frame_base, + &mc_model_checker->process(), process_index); + + if (not location.in_memory()) + xbt_die("Cannot handle non-address variable"); + new_var.address = location.address(); + + } else + xbt_die("No address"); + + result.push_back(std::move(new_var)); + } + + // Recursive processing of nested scopes: + for (simgrid::mc::Frame& nested_scope : scope->scopes) + fill_local_variables_values( + stack_frame, &nested_scope, process_index, result); +} + +static std::vector get_local_variables_values(std::vector& stack_frames, + int process_index) +{ + std::vector variables; + for (s_mc_stack_frame_t& stack_frame : stack_frames) + fill_local_variables_values(&stack_frame, stack_frame.frame, process_index, variables); + return variables; +} + +static std::vector unwind_stack_frames(simgrid::mc::UnwindContext* stack_context) +{ + simgrid::mc::RemoteClient* process = &mc_model_checker->process(); + std::vector result; + + unw_cursor_t c = stack_context->cursor(); + + // TODO, check condition check (unw_init_local==0 means end of frame) + + while (1) { + + s_mc_stack_frame_t stack_frame; + + stack_frame.unw_cursor = c; + + unw_word_t ip; + unw_word_t sp; + + unw_get_reg(&c, UNW_REG_IP, &ip); + unw_get_reg(&c, UNW_REG_SP, &sp); + + stack_frame.ip = ip; + stack_frame.sp = sp; + + // TODO, use real addresses in frame_t instead of fixing it here + + simgrid::mc::Frame* frame = process->find_function(remote(ip)); + stack_frame.frame = frame; + + if (frame) { + stack_frame.frame_name = frame->name; + stack_frame.frame_base = + (unw_word_t) frame->frame_base(c); + } else { + stack_frame.frame_base = 0; + stack_frame.frame_name = std::string(); + } + + result.push_back(std::move(stack_frame)); + + /* Stop before context switch with maestro */ + if (frame != nullptr && + frame->name == "smx_ctx_sysv_wrapper") + break; + + int ret = unw_step(&c); + if (ret == 0) + xbt_die("Unexpected end of stack."); + else if (ret < 0) + xbt_die("Error while unwinding stack"); + } + + if (result.empty()) { + XBT_INFO("unw_init_local failed"); + xbt_abort(); + } + + return result; +} + +static std::vector take_snapshot_stacks(simgrid::mc::Snapshot* snapshot) +{ + std::vector res; + + for (auto const& stack : mc_model_checker->process().stack_areas()) { + s_mc_snapshot_stack_t st; + + // Read the context from remote process: + unw_context_t context; + mc_model_checker->process().read_bytes( + &context, sizeof(context), remote(stack.context)); + + st.context.initialize(&mc_model_checker->process(), &context); + + st.stack_frames = unwind_stack_frames(&st.context); + st.local_variables = get_local_variables_values(st.stack_frames, stack.process_index); + st.process_index = stack.process_index; + + unw_word_t sp = st.stack_frames[0].sp; + + res.push_back(std::move(st)); + + size_t stack_size = + (char*) stack.address + stack.size - (char*) sp; + snapshot->stack_sizes.push_back(stack_size); + } + + return res; + +} + +static void snapshot_handle_ignore(simgrid::mc::Snapshot* snapshot) +{ + xbt_assert(snapshot->process()); + + // Copy the memory: + for (auto const& region : mc_model_checker->process().ignored_regions()) { + s_mc_snapshot_ignored_data_t ignored_data; + ignored_data.start = (void*)region.addr; + ignored_data.data.resize(region.size); + // TODO, we should do this once per privatization segment: + snapshot->process()->read_bytes( + ignored_data.data.data(), region.size, remote(region.addr), + simgrid::mc::ProcessIndexDisabled); + snapshot->ignored_data.push_back(std::move(ignored_data)); + } + + // Zero the memory: + for (auto const& region : mc_model_checker->process().ignored_regions()) + snapshot->process()->clear_bytes(remote(region.addr), region.size); + +} + +static void snapshot_ignore_restore(simgrid::mc::Snapshot* snapshot) +{ + for (auto const& ignored_data : snapshot->ignored_data) + snapshot->process()->write_bytes( + ignored_data.data.data(), ignored_data.data.size(), + remote(ignored_data.start)); +} + +static std::vector get_current_fds(pid_t pid) +{ + const size_t fd_dir_path_size = 20; + char fd_dir_path[fd_dir_path_size]; + int res = snprintf(fd_dir_path, fd_dir_path_size, + "/proc/%lli/fd", (long long int) pid); + xbt_assert(res >= 0); + if ((size_t) res > fd_dir_path_size) + xbt_die("Unexpected buffer is too small for fd_dir_path"); + + DIR* fd_dir = opendir(fd_dir_path); + if (fd_dir == nullptr) + xbt_die("Cannot open directory '/proc/self/fd'\n"); + + std::vector fds; + + struct dirent* fd_number; + while ((fd_number = readdir(fd_dir))) { + + int fd_value = xbt_str_parse_int(fd_number->d_name, "Found a non-numerical FD: %s. Freaking out!"); + + if(fd_value < 3) + continue; + + const size_t source_size = 25; + char source[25]; + int res = snprintf(source, source_size, "/proc/%lli/fd/%s", + (long long int) pid, fd_number->d_name); + xbt_assert(res >= 0); + if ((size_t) res > source_size) + xbt_die("Unexpected buffer is too small for fd %s", fd_number->d_name); + + const size_t link_size = 200; + char link[200]; + res = readlink(source, link, link_size); + + if (res<0) + xbt_die("Could not read link for %s", source); + if (res==200) + xbt_die("Buffer to small for link of %s", source); + + link[res] = '\0'; + +#if HAVE_SMPI + if(smpi_is_privatization_file(link)) + continue; +#endif + + // This is (probably) the DIR* we are reading: + // TODO, read all the file entries at once and close the DIR.* + if(strcmp(fd_dir_path, link) == 0) + continue; + + // We don't handle them. + // It does not mean we should silently ignore them however. + if (strncmp(link, "pipe:", std::strlen("pipe:")) == 0 || strncmp(link, "socket:", std::strlen("socket:")) == 0) + continue; + + // If dot_output enabled, do not handle the corresponding file + if (dot_output != nullptr) { + std::string link_basename = simgrid::xbt::Path(link).get_base_name(); + if (link_basename == _sg_mc_dot_output_file.get()) + continue; + } + + // This is probably a shared memory used by lttng-ust: + if(strncmp("/dev/shm/ust-shm-tmp-", link, std::strlen("/dev/shm/ust-shm-tmp-"))==0) + continue; + + // Add an entry for this FD in the snapshot: + s_fd_infos_t fd; + fd.filename = std::string(link); + fd.number = fd_value; + fd.flags = fcntl(fd_value, F_GETFL) | fcntl(fd_value, F_GETFD) ; + fd.current_position = lseek(fd_value, 0, SEEK_CUR); + fds.push_back(std::move(fd)); + } + + closedir (fd_dir); + return fds; +} + +std::shared_ptr take_snapshot(int num_state) +{ + XBT_DEBUG("Taking snapshot %i", num_state); + + simgrid::mc::RemoteClient* mc_process = &mc_model_checker->process(); + + std::shared_ptr snapshot = std::make_shared(mc_process, num_state); + + for (auto const& p : mc_model_checker->process().actors()) + snapshot->enabled_processes.insert(p.copy.getBuffer()->pid); + + snapshot_handle_ignore(snapshot.get()); + + if (_sg_mc_snapshot_fds) + snapshot->current_fds = get_current_fds(mc_model_checker->process().pid()); + + /* Save the std heap and the writable mapped pages of libsimgrid and binary */ + get_memory_regions(mc_process, snapshot.get()); + + snapshot->to_ignore = mc_model_checker->process().ignored_heap(); + + if (_sg_mc_max_visited_states > 0 || not _sg_mc_property_file.get().empty()) { + snapshot->stacks = take_snapshot_stacks(snapshot.get()); + if (_sg_mc_hash) + snapshot->hash = simgrid::mc::hash(*snapshot); + else + snapshot->hash = 0; + } else + snapshot->hash = 0; + + snapshot_ignore_restore(snapshot.get()); + return snapshot; +} + +static inline +void restore_snapshot_regions(simgrid::mc::Snapshot* snapshot) +{ + for (std::unique_ptr const& region : snapshot->snapshot_regions) { + // For privatized, variables we decided it was not necessary to take the snapshot: + if (region) + restore(region.get()); + } + +#if HAVE_SMPI + if(snapshot->privatization_index >= 0) { + // Fix the privatization mmap: + s_mc_message_restore_t message{MC_MESSAGE_RESTORE, snapshot->privatization_index}; + mc_model_checker->process().getChannel().send(message); + } +#endif +} + +static inline +void restore_snapshot_fds(simgrid::mc::Snapshot* snapshot) +{ + xbt_die("FD snapshot not implemented in client/server mode."); + + for (auto const& fd : snapshot->current_fds) { + + int new_fd = open(fd.filename.c_str(), fd.flags); + if (new_fd < 0) + xbt_die("Could not reopen the file %s fo restoring the file descriptor", fd.filename.c_str()); + if (new_fd != fd.number) { + dup2(new_fd, fd.number); + close(new_fd); + } + lseek(fd.number, fd.current_position, SEEK_SET); + } +} + +void restore_snapshot(std::shared_ptr snapshot) +{ + XBT_DEBUG("Restore snapshot %i", snapshot->num_state); + restore_snapshot_regions(snapshot.get()); + if (_sg_mc_snapshot_fds) + restore_snapshot_fds(snapshot.get()); + snapshot_ignore_restore(snapshot.get()); + mc_model_checker->process().clear_cache(); +} + +} +} + +#ifdef SIMGRID_TEST + +/* **BOOST** */ +#define BOOST_TEST_MODULE checkpoint +#define BOOST_TEST_DYN_LINK +#include + +static +void add_region(int index, simgrid::mc::Snapshot* snapshot, + simgrid::mc::RegionType type, + simgrid::mc::ObjectInformation* object_info, + void *start_addr, void* permanent_addr, + std::size_t size) +{ + if (type == simgrid::mc::RegionType::Data) + xbt_assert(object_info, "Missing object info for object."); + else if (type == simgrid::mc::RegionType::Heap) + xbt_assert(not object_info, "Unexpected object info for heap region."); + + simgrid::mc::RegionSnapshot region; +#if HAVE_SMPI + const bool privatization_aware = object_info + && mc_model_checker->process().privatized(*object_info); + if (privatization_aware && MC_smpi_process_count()) + region = simgrid::mc::privatized_region( + type, start_addr, permanent_addr, size); + else +#endif + region = simgrid::mc::region(type, start_addr, permanent_addr, size); + + region.object_info(object_info); + snapshot->snapshot_regions[index] + = std::unique_ptr( + new simgrid::mc::RegionSnapshot(std::move(region))); +} + +/* +add_region test +*/ +static +int add_region_BOOST() +{ + + RemoteClient* this_process = new RemoteClient(getpid(), -1); + /* read /proc/getpid()/maps into "this_process->memory_map", etc. */ + this_process->init(); + simgrid::mc::Snapshot* snapshot = new simgrid::mc::Snapshot(this_process, 0); // first ckpt + simgrid::mc::RegionType type = simgrid::mc::RegionType::Unknown; + // simgrid::mc::ObjectInformation* object_info; + /* TODO: mmap some memory to use */ + void* start_addr = 0x7fb7539a0000; // random addr + void* permanent_addr = 0x7fb7539a0000; // random addr + std::size_t size = 4096; // PAGESIZE + int region_num = 10; + for(int i=0; i /* context relative declarations */ + +XBT_PUBLIC void MC_register_stack_area(void* stack, smx_actor_t process, ucontext_t* context, size_t size); + +#endif + +#endif diff --git a/src/mc/snapshot/mc_mmu.hpp b/src/mc/snapshot/mc_mmu.hpp new file mode 100644 index 0000000000..34e71e4e09 --- /dev/null +++ b/src/mc/snapshot/mc_mmu.hpp @@ -0,0 +1,61 @@ +/* Copyright (c) 2014-2018. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef SIMGRID_MC_MMU_HPP +#define SIMGRID_MC_MMU_HPP + +#include "xbt/misc.h" // xbt_pagesize... +#include +#include + +namespace simgrid { +namespace mc { +// TODO, do not depend on xbt_pagesize/xbt_pagebits but our own chunk size +namespace mmu { + +static int chunkSize() +{ + return xbt_pagesize; +} + +/** @brief How many memory pages are necessary to store size bytes? + * + * @param size Byte size + * @return Number of memory pages + */ +static XBT_ALWAYS_INLINE std::size_t chunkCount(std::size_t size) +{ + size_t page_count = size >> xbt_pagebits; + if (size & (xbt_pagesize - 1)) + page_count++; + return page_count; +} + +/** @brief Split into chunk number and remaining offset */ +static XBT_ALWAYS_INLINE std::pair split(std::uintptr_t offset) +{ + return {offset >> xbt_pagebits, offset & (xbt_pagesize - 1)}; +} + +/** Merge chunk number and remaining offset info a global offset */ +static XBT_ALWAYS_INLINE std::uintptr_t join(std::size_t page, std::uintptr_t offset) +{ + return ((std::uintptr_t)page << xbt_pagebits) + offset; +} + +static XBT_ALWAYS_INLINE std::uintptr_t join(std::pair value) +{ + return join(value.first, value.second); +} + +static XBT_ALWAYS_INLINE bool sameChunk(std::uintptr_t a, std::uintptr_t b) +{ + return (a >> xbt_pagebits) == (b >> xbt_pagebits); +} +} +} +} + +#endif diff --git a/src/mc/snapshot/mc_page_snapshot.cpp b/src/mc/snapshot/mc_page_snapshot.cpp new file mode 100644 index 0000000000..a7f21c26a4 --- /dev/null +++ b/src/mc/snapshot/mc_page_snapshot.cpp @@ -0,0 +1,51 @@ +/* Copyright (c) 2014-2018. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +/* MC interface: definitions that non-MC modules must see, but not the user */ + + +#include // pread, pwrite + +#include "src/mc/PageStore.hpp" +#include "src/mc/mc_mmu.hpp" +#include "src/mc/mc_private.hpp" +#include "src/mc/mc_snapshot.hpp" + +#include +#include "src/mc/ChunkedData.hpp" + +using simgrid::mc::remote; + +/** @brief Restore a snapshot of a region + * + * If possible, the restoration will be incremental + * (the modified pages will not be touched). + * + * @param start_addr + * @param page_count Number of pages of the region + * @param pagenos + */ +void mc_restore_page_snapshot_region(simgrid::mc::RemoteClient* process, void* start_addr, + simgrid::mc::ChunkedData const& pages_copy) +{ + for (size_t i = 0; i != pages_copy.page_count(); ++i) { + // Otherwise, copy the page: + void* target_page = (void*) simgrid::mc::mmu::join(i, (std::uintptr_t) start_addr); + const void* source_page = pages_copy.page(i); + process->write_bytes(source_page, xbt_pagesize, remote(target_page)); + } +} + +// ***** High level API + +void mc_region_restore_sparse(simgrid::mc::RemoteClient* process, mc_mem_region_t reg) +{ + xbt_assert(((reg->permanent_address().address()) & (xbt_pagesize-1)) == 0, + "Not at the beginning of a page"); + xbt_assert(simgrid::mc::mmu::chunkCount(reg->size()) == reg->page_data().page_count()); + mc_restore_page_snapshot_region(process, + (void*) reg->permanent_address().address(), reg->page_data()); +} diff --git a/src/mc/snapshot/mc_snapshot.cpp b/src/mc/snapshot/mc_snapshot.cpp new file mode 100644 index 0000000000..27acf54a3a --- /dev/null +++ b/src/mc/snapshot/mc_snapshot.cpp @@ -0,0 +1,287 @@ +/* Copyright (c) 2014-2018. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include + +#include +#include + +#include "xbt/asserts.h" +#include "xbt/sysdep.h" + +#include "src/internal_config.h" +#include "src/smpi/include/private.hpp" + +#include "src/mc/PageStore.hpp" +#include "src/mc/mc_mmu.hpp" +#include "src/mc/mc_private.hpp" +#include "src/mc/mc_snapshot.hpp" + +/** @brief Find the snapshoted region from a pointer + * + * @param addr Pointer + * @param snapshot Snapshot + * @param Snapshot region in the snapshot this pointer belongs to + * (or nullptr if it does not belong to any snapshot region) + * */ +mc_mem_region_t mc_get_snapshot_region( + const void* addr, const simgrid::mc::Snapshot* snapshot, int process_index) +{ + size_t n = snapshot->snapshot_regions.size(); + for (size_t i = 0; i != n; ++i) { + mc_mem_region_t region = snapshot->snapshot_regions[i].get(); + if (not(region && region->contain(simgrid::mc::remote(addr)))) + continue; + + if (region->storage_type() == simgrid::mc::StorageType::Privatized) { +#if HAVE_SMPI + // Use the current process index of the snapshot: + if (process_index == simgrid::mc::ProcessIndexDisabled) + process_index = snapshot->privatization_index; + if (process_index < 0) + xbt_die("Missing process index"); + if (process_index >= (int) region->privatized_data().size()) + xbt_die("Invalid process index"); + simgrid::mc::RegionSnapshot& priv_region = region->privatized_data()[process_index]; + xbt_assert(priv_region.contain(simgrid::mc::remote(addr))); + return &priv_region; +#else + xbt_die("Privatized region in a non SMPI build (this should not happen)"); +#endif + } + + return region; + } + + return nullptr; +} + +/** @brief Read memory from a snapshot region broken across fragmented pages + * + * @param addr Process (non-snapshot) address of the data + * @param region Snapshot memory region where the data is located + * @param target Buffer to store the value + * @param size Size of the data to read in bytes + * @return Pointer where the data is located (target buffer of original location) + */ +const void* MC_region_read_fragmented(mc_mem_region_t region, void* target, const void* addr, size_t size) +{ + // Last byte of the memory area: + void* end = (char*) addr + size - 1; + + // TODO, we assume the chunks are aligned to natural chunk boundaries. + // We should remove this assumption. + + // Page of the last byte of the memory area: + size_t page_end = simgrid::mc::mmu::split((std::uintptr_t) end).first; + + void* dest = target; + + if (dest==nullptr) + xbt_die("Missing destination buffer for fragmented memory access"); + + // Read each page: + while (simgrid::mc::mmu::split((std::uintptr_t) addr).first != page_end) { + void* snapshot_addr = mc_translate_address_region_chunked((uintptr_t) addr, region); + void* next_page = (void*) simgrid::mc::mmu::join( + simgrid::mc::mmu::split((std::uintptr_t) addr).first + 1, + 0); + size_t readable = (char*) next_page - (char*) addr; + memcpy(dest, snapshot_addr, readable); + addr = (char*) addr + readable; + dest = (char*) dest + readable; + size -= readable; + } + + // Read the end: + void* snapshot_addr = mc_translate_address_region_chunked((uintptr_t)addr, region); + memcpy(dest, snapshot_addr, size); + + return target; +} + +/** Compare memory between snapshots (with known regions) + * + * @param addr1 Address in the first snapshot + * @param snapshot2 Region of the address in the first snapshot + * @param addr2 Address in the second snapshot + * @param snapshot2 Region of the address in the second snapshot + * @return same as memcmp + * */ +int MC_snapshot_region_memcmp( + const void* addr1, mc_mem_region_t region1, + const void* addr2, mc_mem_region_t region2, + size_t size) +{ + // Using alloca() for large allocations may trigger stack overflow: + // use malloc if the buffer is too big. + bool stack_alloc = size < 64; + void* buffer1a = nullptr; + void* buffer2a = nullptr; + if (region1 != nullptr && region1->storage_type() != simgrid::mc::StorageType::Flat) + buffer1a = stack_alloc ? alloca(size) : ::operator new(size); + if (region2 != nullptr && region2->storage_type() != simgrid::mc::StorageType::Flat) + buffer2a = stack_alloc ? alloca(size) : ::operator new(size); + const void* buffer1 = MC_region_read(region1, buffer1a, addr1, size); + const void* buffer2 = MC_region_read(region2, buffer2a, addr2, size); + int res; + if (buffer1 == buffer2) + res = 0; + else + res = memcmp(buffer1, buffer2, size); + if (not stack_alloc) { + ::operator delete(buffer1a); + ::operator delete(buffer2a); + } + return res; +} + +namespace simgrid { +namespace mc { + +Snapshot::Snapshot(RemoteClient* process, int _num_state) + : AddressSpace(process) + , num_state(_num_state) + , heap_bytes_used(0) + , enabled_processes() + , privatization_index(0) + , hash(0) +{ + +} + +const void* Snapshot::read_bytes(void* buffer, std::size_t size, + RemotePtr address, int process_index, + ReadOptions options) const +{ + mc_mem_region_t region = mc_get_snapshot_region((void*)address.address(), this, process_index); + if (region) { + const void* res = MC_region_read(region, buffer, (void*)address.address(), size); + if (buffer == res || options & ReadOptions::lazy()) + return res; + else { + memcpy(buffer, res, size); + return buffer; + } + } + else + return this->process()->read_bytes( + buffer, size, address, process_index, options); +} + +} +} + +#ifdef SIMGRID_TEST + +#include +#include + +#include + +#include "src/mc/mc_config.hpp" +#include "src/mc/mc_mmu.hpp" +#include "src/mc/mc_private.hpp" +#include "src/mc/mc_snapshot.hpp" + +XBT_TEST_SUITE("mc_snapshot", "Snapshots"); + +static inline void init_memory(void* mem, size_t size) +{ + char* dest = (char*) mem; + for (size_t i = 0; i < size; ++i) { + dest[i] = rand() & 255; + } +} + +static void test_snapshot(bool sparse_checkpoint); + +XBT_TEST_UNIT("flat_snapshot", test_flat_snapshots, "Test flat snapshots") +{ + test_snapshot(0); +} + +XBT_TEST_UNIT("page_snapshots", test_per_snpashots, "Test per-page snapshots") +{ + test_snapshot(1); +} + +static void test_snapshot(bool sparse_checkpoint) { + + xbt_test_add("Initialization"); + _sg_mc_sparse_checkpoint = sparse_checkpoint; + xbt_assert(xbt_pagesize == getpagesize()); + xbt_assert(1 << xbt_pagebits == xbt_pagesize); + + std::unique_ptr process(new simgrid::mc::RemoteClient(getpid(), -1)); + process->init(); + mc_model_checker = new ::simgrid::mc::ModelChecker(std::move(process)); + + for(int n=1; n!=256; ++n) { + + // Store region page(s): + size_t byte_size = n * xbt_pagesize; + void* source = mmap(nullptr, byte_size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); + xbt_assert(source!=MAP_FAILED, "Could not allocate source memory"); + + // Init memory and take snapshots: + init_memory(source, byte_size); + simgrid::mc::RegionSnapshot region0 = simgrid::mc::sparse_region( + simgrid::mc::RegionType::Unknown, source, source, byte_size); + for(int i=0; i +#include +#include +#include + +#include "src/mc/ModelChecker.hpp" +#include "src/mc/RegionSnapshot.hpp" +#include "src/mc/mc_forward.hpp" +#include "src/mc/mc_unw.hpp" + +// ***** Snapshot region + +XBT_PRIVATE void mc_region_restore_sparse(simgrid::mc::RemoteClient* process, mc_mem_region_t reg); + +static XBT_ALWAYS_INLINE void* mc_translate_address_region_chunked(uintptr_t addr, mc_mem_region_t region) +{ + auto split = simgrid::mc::mmu::split(addr - region->start().address()); + auto pageno = split.first; + auto offset = split.second; + const void* snapshot_page = region->page_data().page(pageno); + return (char*)snapshot_page + offset; +} + +static XBT_ALWAYS_INLINE void* mc_translate_address_region(uintptr_t addr, mc_mem_region_t region, int process_index) +{ + switch (region->storage_type()) { + case simgrid::mc::StorageType::Flat: { + uintptr_t offset = (uintptr_t)addr - (uintptr_t)region->start().address(); + return (void*)((uintptr_t)region->flat_data().get() + offset); + } + case simgrid::mc::StorageType::Chunked: + return mc_translate_address_region_chunked(addr, region); + case simgrid::mc::StorageType::Privatized: { + xbt_assert(process_index >= 0, "Missing process index for privatized region"); + xbt_assert((size_t)process_index < region->privatized_data().size(), "Out of range process index"); + simgrid::mc::RegionSnapshot& subregion = region->privatized_data()[process_index]; + return mc_translate_address_region(addr, &subregion, process_index); + } + default: // includes StorageType::NoData + xbt_die("Storage type not supported"); + } +} + +XBT_PRIVATE mc_mem_region_t mc_get_snapshot_region(const void* addr, const simgrid::mc::Snapshot* snapshot, + int process_index); + +// ***** MC Snapshot + +/** Ignored data + * + * Some parts of the snapshot are ignored by zeroing them out: the real + * values is stored here. + * */ +struct s_mc_snapshot_ignored_data_t { + void* start; + std::vector data; +}; + +struct s_fd_infos_t { + std::string filename; + int number; + off_t current_position; + int flags; +}; + +/** Information about a given stack frame */ +struct s_mc_stack_frame_t { + /** Instruction pointer */ + unw_word_t ip; + /** Stack pointer */ + unw_word_t sp; + unw_word_t frame_base; + simgrid::mc::Frame* frame; + std::string frame_name; + unw_cursor_t unw_cursor; +}; +typedef s_mc_stack_frame_t* mc_stack_frame_t; + +struct s_local_variable_t { + simgrid::mc::Frame* subprogram; + unsigned long ip; + std::string name; + simgrid::mc::Type* type; + void* address; + int region; +}; +typedef s_local_variable_t* local_variable_t; + +struct XBT_PRIVATE s_mc_snapshot_stack_t { + std::vector local_variables; + simgrid::mc::UnwindContext context; + std::vector stack_frames; + int process_index; +}; +typedef s_mc_snapshot_stack_t* mc_snapshot_stack_t; + +namespace simgrid { +namespace mc { + +class XBT_PRIVATE Snapshot final : public AddressSpace { +public: + Snapshot(RemoteClient* process, int num_state); + ~Snapshot() = default; + const void* read_bytes(void* buffer, std::size_t size, RemotePtr address, int process_index = ProcessIndexAny, + ReadOptions options = ReadOptions::none()) const override; + + // To be private + int num_state; + std::size_t heap_bytes_used; + std::vector> snapshot_regions; + std::set enabled_processes; + int privatization_index; + std::vector stack_sizes; + std::vector stacks; + std::vector to_ignore; + std::uint64_t hash; + std::vector ignored_data; + std::vector current_fds; +}; +} +} + +static XBT_ALWAYS_INLINE mc_mem_region_t mc_get_region_hinted(void* addr, simgrid::mc::Snapshot* snapshot, + int process_index, mc_mem_region_t region) +{ + if (region->contain(simgrid::mc::remote(addr))) + return region; + else + return mc_get_snapshot_region(addr, snapshot, process_index); +} + +static const void* mc_snapshot_get_heap_end(simgrid::mc::Snapshot* snapshot); + +namespace simgrid { +namespace mc { + +XBT_PRIVATE std::shared_ptr take_snapshot(int num_state); +XBT_PRIVATE void restore_snapshot(std::shared_ptr snapshot); +} +} + +XBT_PRIVATE void mc_restore_page_snapshot_region(simgrid::mc::RemoteClient* process, void* start_addr, + simgrid::mc::ChunkedData const& pagenos); + +const void* MC_region_read_fragmented(mc_mem_region_t region, void* target, const void* addr, std::size_t size); + +int MC_snapshot_region_memcmp(const void* addr1, mc_mem_region_t region1, const void* addr2, mc_mem_region_t region2, + std::size_t size); + +static XBT_ALWAYS_INLINE const void* mc_snapshot_get_heap_end(simgrid::mc::Snapshot* snapshot) +{ + if (snapshot == nullptr) + xbt_die("snapshot is nullptr"); + return mc_model_checker->process().get_heap()->breakval; +} + +/** @brief Read memory from a snapshot region + * + * @param addr Process (non-snapshot) address of the data + * @param region Snapshot memory region where the data is located + * @param target Buffer to store the value + * @param size Size of the data to read in bytes + * @return Pointer where the data is located (target buffer of original location) + */ +static XBT_ALWAYS_INLINE const void* MC_region_read(mc_mem_region_t region, void* target, const void* addr, + std::size_t size) +{ + xbt_assert(region); + + std::uintptr_t offset = (std::uintptr_t)addr - (std::uintptr_t)region->start().address(); + + xbt_assert(region->contain(simgrid::mc::remote(addr)), "Trying to read out of the region boundary."); + + switch (region->storage_type()) { + case simgrid::mc::StorageType::Flat: + return (char*)region->flat_data().get() + offset; + + case simgrid::mc::StorageType::Chunked: { + // Last byte of the region: + void* end = (char*)addr + size - 1; + if (simgrid::mc::mmu::sameChunk((std::uintptr_t)addr, (std::uintptr_t)end)) { + // The memory is contained in a single page: + return mc_translate_address_region_chunked((uintptr_t)addr, region); + } + // Otherwise, the memory spans several pages: + return MC_region_read_fragmented(region, target, addr, size); + } + + default: + // includes StorageType::NoData and StorageType::Privatized (we currently do not pass the process_index to this + // function so we assume that the privatized region has been resolved in the callers) + xbt_die("Storage type not supported"); + } +} + +static XBT_ALWAYS_INLINE void* MC_region_read_pointer(mc_mem_region_t region, const void* addr) +{ + void* res; + return *(void**)MC_region_read(region, &res, addr, sizeof(void*)); +} + +#endif diff --git a/src/mc/snapshot/unitTest/PageStore_unit_BOOST.cpp b/src/mc/snapshot/unitTest/PageStore_unit_BOOST.cpp new file mode 100644 index 0000000000..a4691405f8 --- /dev/null +++ b/src/mc/snapshot/unitTest/PageStore_unit_BOOST.cpp @@ -0,0 +1,95 @@ +/**************************************************** +TODO: comment +****************************************************/ +#define BOOST_TEST_MODULE pageStore +#define BOOST_TEST_DYN_LINK +#include + +// /*******************************/ +// /* GENERATED FILE, DO NOT EDIT */ +// /*******************************/ +// +// #include +// #include "xbt.h" +// /*******************************/ +// /* GENERATED FILE, DO NOT EDIT */ +// /*******************************/ +// +// #line 191 "mc/PageStore.cpp" + +#include +#include +#include + +#include +#include + +#include + +#include "/home/onesphore/simgrid/src/mc/PageStore.hpp" + +static int value = 0; + +static void new_content(void* data, std::size_t size) +{ + ::memset(data, ++value, size); +} + +static void* getpage() +{ + return mmap(nullptr, getpagesize(), PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); +} + +BOOST_AUTO_TEST_CASE(pageStore) { +// XBT_TEST_UNIT("base", test_mc_page_store, "Test adding/removing pages in the store") +// { + + using simgrid::mc::PageStore; + + std::cout << "Test adding/removing pages in the store" << std::endl; + + // xbt_test_add("Init"); + std::size_t pagesize = (size_t) getpagesize(); + std::unique_ptr store = std::unique_ptr(new simgrid::mc::PageStore(500)); + void* data = getpage(); + BOOST_TEST(store->size()==0, "Bad size"); + + // xbt_test_add("Store the page once"); + new_content(data, pagesize); + size_t pageno1 = store->store_page(data); + BOOST_TEST(store->get_ref(pageno1)==1, "Bad refcount"); + const void* copy = store->get_page(pageno1); + BOOST_TEST(::memcmp(data, copy, pagesize)==0, "Page data should be the same"); + BOOST_TEST(store->size()==1, "Bad size"); + + // xbt_test_add("Store the same page again"); + size_t pageno2 = store->store_page(data); + BOOST_TEST(pageno1==pageno2, "Page should be the same"); + BOOST_TEST(store->get_ref(pageno1)==2, "Bad refcount"); + BOOST_TEST(store->size()==1, "Bad size"); + + // xbt_test_add("Store a new page"); + new_content(data, pagesize); + size_t pageno3 = store->store_page(data); + BOOST_TEST(pageno1 != pageno3, "New page should be different"); + BOOST_TEST(store->size()==2, "Bad size"); + + // xbt_test_add("Unref pages"); + store->unref_page(pageno1); + BOOST_TEST(store->get_ref(pageno1)==1, "Bad refcount"); + BOOST_TEST(store->size()==2, "Bad size"); + store->unref_page(pageno2); + BOOST_TEST(store->size()==1, "Bad size"); + + // xbt_test_add("Reallocate page"); + new_content(data, pagesize); + size_t pageno4 = store->store_page(data); + BOOST_TEST(pageno1 == pageno4, "Page was not reused"); + BOOST_TEST(store->get_ref(pageno4)==1, "Bad refcount"); + BOOST_TEST(store->size()==2, "Bad size"); +} + +/*******************************/ +/* GENERATED FILE, DO NOT EDIT */ +/*******************************/ + diff --git a/src/mc/snapshot/unitTest/mc_snapshot_unit_BOOST.cpp b/src/mc/snapshot/unitTest/mc_snapshot_unit_BOOST.cpp new file mode 100644 index 0000000000..c07260fe7f --- /dev/null +++ b/src/mc/snapshot/unitTest/mc_snapshot_unit_BOOST.cpp @@ -0,0 +1,129 @@ +/************************************************* +TODO: comment +*************************************************/ +#define BOOST_TEST_MODULE snapshots +#define BOOST_TEST_DYN_LINK +#include + +// /*******************************/ +// /* GENERATED FILE, DO NOT EDIT */ +// /*******************************/ +// +// #include +// #include "xbt.h" +// /*******************************/ +// /* GENERATED FILE, DO NOT EDIT */ +// /*******************************/ +// +// #line 180 "mc/mc_snapshot.cpp" + +#include +#include + +#include + +#include "simgrid/src/mc/mc_config.hpp" +#include "simgrid/src/mc/mc_mmu.hpp" +#include "simgrid/src/mc/mc_private.hpp" +#include "simgrid/src/mc/mc_snapshot.hpp" + + +static inline void init_memory(void* mem, size_t size) +{ + char* dest = (char*) mem; + for (size_t i = 0; i < size; ++i) { + dest[i] = rand() & 255; + } +} + +static int test_snapshot(bool sparse_checkpoint); + +BOOST_AUTO_TEST_SUITE(Snapshots) +BOOST_AUTO_TEST_CASE(flat_snapshots) { + BOOST_TEST(test_snapshot(0) == 1); +} +BOOST_AUTO_TEST_CASE(page_snapshots) { + BOOST_TEST(test_snapshot(1) == 1); +} +BOOST_AUTO_TEST_SUITE_END() + +static int test_snapshot(bool sparse_checkpoint) { + + // xbt_test_add("Initialization"); + _sg_mc_sparse_checkpoint = sparse_checkpoint; + BOOST_TEST(xbt_pagesize == getpagesize()); + BOOST_TEST(1 << xbt_pagebits == xbt_pagesize); + + std::unique_ptr process(new simgrid::mc::RemoteClient(getpid(), -1)); + process->init(); + mc_model_checker = new ::simgrid::mc::ModelChecker(std::move(process)); + + for(int n=1; n!=256; ++n) { + + // Store region page(s): + size_t byte_size = n * xbt_pagesize; + void* source = mmap(nullptr, byte_size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); + BOOST_TEST(source!=MAP_FAILED, "Could not allocate source memory"); + + // Init memory and take snapshots: + init_memory(source, byte_size); + simgrid::mc::RegionSnapshot region0 = simgrid::mc::sparse_region( + simgrid::mc::RegionType::Unknown, source, source, byte_size); + for(int i=0; i