From: Gabriel Corona Date: Tue, 27 May 2014 10:27:47 +0000 (+0200) Subject: [mc] Page-level sparse snapshot: work-in-progress, working page_store X-Git-Tag: v3_12~956^2~1^2~48 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/0700b488178346d3cccc454f641a7155c6ff6026 [mc] Page-level sparse snapshot: work-in-progress, working page_store Implement page_store which stores immutables/shared/refcounted copies of memory pages. --- diff --git a/buildtools/Cmake/AddTests.cmake b/buildtools/Cmake/AddTests.cmake index 304dc051fb..256435b489 100644 --- a/buildtools/Cmake/AddTests.cmake +++ b/buildtools/Cmake/AddTests.cmake @@ -96,6 +96,7 @@ IF(NOT enable_memcheck) ### MC ### IF(HAVE_MC) + ADD_TESH(page_store --setenv bindir=${CMAKE_BINARY_DIR}/teshsuite/mc --cd ${CMAKE_HOME_DIRECTORY}/teshsuite/mc page_store.tesh) ADD_TESH(tesh-mc-dwarf --setenv bindir=${CMAKE_BINARY_DIR}/teshsuite/mc/dwarf --cd ${CMAKE_HOME_DIRECTORY}/teshsuite/mc/dwarf dwarf.tesh) ADD_TESH(tesh-mc-dwarf-expression --setenv bindir=${CMAKE_BINARY_DIR}/teshsuite/mc/dwarf_expression --cd ${CMAKE_HOME_DIRECTORY}/teshsuite/mc/dwarf_expression dwarf_expression.tesh) diff --git a/buildtools/Cmake/DefinePackages.cmake b/buildtools/Cmake/DefinePackages.cmake index 1ce371e50d..c12c3e29ba 100644 --- a/buildtools/Cmake/DefinePackages.cmake +++ b/buildtools/Cmake/DefinePackages.cmake @@ -584,6 +584,8 @@ set(JEDULE_SRC set(MC_SRC src/mc/mc_checkpoint.c + src/mc/mc_page_store.cpp + src/mc/mc_page_snapshot.cpp src/mc/mc_comm_determinism.c src/mc/mc_compare.c src/mc/mc_diff.c diff --git a/buildtools/Cmake/MakeExe.cmake b/buildtools/Cmake/MakeExe.cmake index 8c3a10751d..a8d13ccde4 100644 --- a/buildtools/Cmake/MakeExe.cmake +++ b/buildtools/Cmake/MakeExe.cmake @@ -80,6 +80,7 @@ add_subdirectory(${CMAKE_HOME_DIRECTORY}/examples/smpi/energy/f90) add_subdirectory(${CMAKE_HOME_DIRECTORY}/examples/xbt) +add_subdirectory(${CMAKE_HOME_DIRECTORY}/teshsuite/mc) add_subdirectory(${CMAKE_HOME_DIRECTORY}/teshsuite/mc/dwarf) add_subdirectory(${CMAKE_HOME_DIRECTORY}/teshsuite/mc/dwarf_expression) diff --git a/include/xbt/misc.h b/include/xbt/misc.h index 3be8fc11f4..a0620abe54 100644 --- a/include/xbt/misc.h +++ b/include/xbt/misc.h @@ -235,6 +235,9 @@ SG_BEGIN_DECL() /** Cache the size of a memory page for the current system. */ XBT_PUBLIC_DATA(int) xbt_pagesize; +/** Cache the number of bits of addresses inside a given page, log2(xbt_pagesize). */ + XBT_PUBLIC_DATA(int) xbt_pagebits; + XBT_PUBLIC(const char *) xbt_procname(void); #define XBT_BACKTRACE_SIZE 10 /* FIXME: better place? Do document */ diff --git a/include/xbt/sysdep.h b/include/xbt/sysdep.h index 4b901a3592..33b10eb449 100644 --- a/include/xbt/sysdep.h +++ b/include/xbt/sysdep.h @@ -45,12 +45,13 @@ XBT_PUBLIC(void) xbt_abort(void) _XBT_GNUC_NORETURN; */ #define xbt_die(...) \ do { \ - XBT_LOG_EXTERNAL_CATEGORY(xbt); \ XBT_CCRITICAL(xbt, __VA_ARGS__); \ xbt_abort(); \ } while (0) /** @} */ +XBT_LOG_EXTERNAL_CATEGORY(xbt); + /* these ones live in str.h, but redeclare them here so that we do not need to load the whole str.h and its heavy dependencies */ #ifndef __USE_GNU /* do not redeclare existing headers */ diff --git a/src/include/mc/mc.h b/src/include/mc/mc.h index 85cb1ac665..a49184d90a 100644 --- a/src/include/mc/mc.h +++ b/src/include/mc/mc.h @@ -38,6 +38,7 @@ SG_BEGIN_DECL() /********************************** Configuration of MC **************************************/ extern int _sg_do_model_check; extern int _sg_mc_checkpoint; +extern int _sg_mc_sparse_checkpoint; extern char* _sg_mc_property_file; extern int _sg_mc_timeout; extern int _sg_mc_hash; @@ -57,6 +58,7 @@ extern void *maestro_stack_end; /********************************* Global *************************************/ void _mc_cfg_cb_reduce(const char *name, int pos); void _mc_cfg_cb_checkpoint(const char *name, int pos); +void _mc_cfg_cb_sparse_checkpoint(const char *name, int pos); void _mc_cfg_cb_property(const char *name, int pos); void _mc_cfg_cb_timeout(const char *name, int pos); void _mc_cfg_cb_hash(const char *name, int pos); diff --git a/src/mc/mc_checkpoint.c b/src/mc/mc_checkpoint.c index 2b350b74ac..08b335234a 100644 --- a/src/mc/mc_checkpoint.c +++ b/src/mc/mc_checkpoint.c @@ -13,6 +13,7 @@ #include "xbt/module.h" #include #include "../smpi/private.h" +#include #include "xbt/mmalloc/mmprivate.h" @@ -22,6 +23,9 @@ #include #include "mc_private.h" +#include + +#include "mc_mmu.h" XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_checkpoint, mc, "Logging specific to mc_checkpoint"); @@ -85,41 +89,57 @@ void MC_free_snapshot(mc_snapshot_t snapshot) xbt_free(snapshot); } - /******************************* Snapshot regions ********************************/ /*********************************************************************************/ -static mc_mem_region_t MC_region_new(int type, void *start_addr, size_t size) +static mc_mem_region_t MC_region_new(int type, void *start_addr, size_t size, mc_mem_region_t ref_reg) { + if (_sg_mc_sparse_checkpoint) { + return mc_region_new_sparse(type, start_addr, size, ref_reg); + } + mc_mem_region_t new_reg = xbt_new(s_mc_mem_region_t, 1); new_reg->start_addr = start_addr; + new_reg->data = NULL; new_reg->size = size; - //new_reg->data = mmap(NULL, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); - //if(new_reg->data==MAP_FAILED) - //xbt_die("Could not mmap new memory for snapshot."); + new_reg->page_numbers = NULL; new_reg->data = xbt_malloc(size); memcpy(new_reg->data, start_addr, size); - //madvise(new_reg->data, size, MADV_MERGEABLE); - XBT_DEBUG("New region : type : %d, data : %p (real addr %p), size : %zu", type, new_reg->data, start_addr, size); - return new_reg; + } -static void MC_region_restore(mc_mem_region_t reg) +/** @brief Restore a region from a snapshot + * + * If we are using per page snapshots, it is possible to use the reference + * region in order to do an incremental restoration of the region: the + * softclean pages which are shared between the two snapshots do not need + * to be restored. + * + * @param reg Target region + * @param reg_reg Current region (if not NULL), used for lazy per page restoration + */ +static void MC_region_restore(mc_mem_region_t reg, mc_mem_region_t ref_reg) { /*FIXME: check if start_addr is still mapped, if it is not, then map it - before copying the data */ - - memcpy(reg->start_addr, reg->data, reg->size); + before copying the data */ + if (!reg->page_numbers) { + memcpy(reg->start_addr, reg->data, reg->size); + } else { + mc_region_restore_sparse(reg, ref_reg); + } return; } static void MC_snapshot_add_region(mc_snapshot_t snapshot, int type, void *start_addr, size_t size) + { - mc_mem_region_t new_reg = MC_region_new(type, start_addr, size); + mc_mem_region_t ref_reg = + mc_model_checker->parent_snapshot ? mc_model_checker->parent_snapshot->regions[type] : NULL; + mc_mem_region_t new_reg = MC_region_new(type, start_addr, size, ref_reg); snapshot->regions[type] = new_reg; return; } @@ -146,8 +166,9 @@ static void MC_get_memory_regions(mc_snapshot_t snapshot) snapshot->privatization_regions = xbt_new(mc_mem_region_t, SIMIX_process_count()); for (i = 0; i < SIMIX_process_count(); i++) { + // TODO, add support for sparse snapshot snapshot->privatization_regions[i] = - MC_region_new(-1, mappings[i], size_data_exe); + MC_region_new(-1, mappings[i], size_data_exe, NULL); } snapshot->privatization_index = loaded_page; } @@ -539,6 +560,23 @@ static void MC_snapshot_ignore_restore(mc_snapshot_t snapshot) } } +/** @brief Can we remove this snapshot? + * + * Some snapshots cannot be removed (yet) because we need them + * at this point. + * + * @param snapshot + */ +int mc_important_snapshot(mc_snapshot_t snapshot) +{ + // We need this snapshot in order to know which + // pages needs to be stored in the next snapshot: + if (_sg_mc_sparse_checkpoint && snapshot == mc_model_checker->parent_snapshot) + return true; + + return false; +} + mc_snapshot_t MC_take_snapshot(int num_state) { @@ -553,6 +591,9 @@ mc_snapshot_t MC_take_snapshot(int num_state) /* Save the std heap and the writable mapped pages of libsimgrid and binary */ MC_get_memory_regions(snapshot); + if (_sg_mc_sparse_checkpoint) { + mc_softdirty_reset(); + } snapshot->to_ignore = MC_take_snapshot_ignore(); @@ -568,38 +609,38 @@ mc_snapshot_t MC_take_snapshot(int num_state) snapshot->hash = 0; } - // mprotect the region after zero-ing ignored parts: - /*size_t i; - for(i=0; i!=NB_REGIONS; ++i) { - mc_mem_region_t region = snapshot->regions[i]; - mprotect(region->data, region->size, PROT_READ); - } */ - MC_snapshot_ignore_restore(snapshot); - + mc_model_checker->parent_snapshot = snapshot; return snapshot; - } void MC_restore_snapshot(mc_snapshot_t snapshot) { + mc_snapshot_t parent_snapshot = mc_model_checker->parent_snapshot; + unsigned int i; for (i = 0; i < NB_REGIONS; i++) { // For privatized, variables we decided it was not necessary to take the snapshot: if (snapshot->regions[i]) - MC_region_restore(snapshot->regions[i]); + MC_region_restore(snapshot->regions[i], + parent_snapshot ? parent_snapshot->regions[i] : NULL); } if (snapshot->privatization_regions) { for (i = 0; i < SIMIX_process_count(); i++) { if (snapshot->privatization_regions[i]) { - MC_region_restore(snapshot->privatization_regions[i]); + MC_region_restore(snapshot->privatization_regions[i], + parent_snapshot ? parent_snapshot->privatization_regions[i] : NULL); } } switch_data_segment(snapshot->privatization_index); } MC_snapshot_ignore_restore(snapshot); + if (_sg_mc_sparse_checkpoint) { + mc_softdirty_reset(); + } + mc_model_checker->parent_snapshot = snapshot; } void *mc_translate_address(uintptr_t addr, mc_snapshot_t snapshot) diff --git a/src/mc/mc_global.c b/src/mc/mc_global.c index a3de319ea1..e9520f680d 100644 --- a/src/mc/mc_global.c +++ b/src/mc/mc_global.c @@ -29,6 +29,7 @@ e_mc_reduce_t mc_reduce_kind = e_mc_reduce_unset; int _sg_do_model_check = 0; int _sg_mc_checkpoint = 0; +int _sg_mc_sparse_checkpoint = 0; char *_sg_mc_property_file = NULL; int _sg_mc_timeout = 0; int _sg_mc_hash = 0; @@ -68,6 +69,13 @@ void _mc_cfg_cb_checkpoint(const char *name, int pos) _sg_mc_checkpoint = xbt_cfg_get_int(_sg_cfg_set, name); } +void _mc_cfg_cb_sparse_checkpoint(const char *name, int pos) { + if (_sg_cfg_init_status && !_sg_do_model_check) { + xbt_die("You are specifying a checkpointing value after the initialization (through MSG_config?), but model-checking was not activated at config time (through --cfg=model-check:1). This won't work, sorry."); + } + _sg_mc_sparse_checkpoint = xbt_cfg_get_int(_sg_cfg_set, name); +} + void _mc_cfg_cb_property(const char *name, int pos) { if (_sg_cfg_init_status && !_sg_do_model_check) { @@ -220,9 +228,10 @@ static void MC_init_debug_info(void) } +mc_model_checker_t mc_model_checker = NULL; + void MC_init() { - int raw_mem_set = (mmalloc_get_current_heap() == mc_heap); mc_time = xbt_new0(double, simix_process_maxpid); @@ -232,6 +241,11 @@ void MC_init() MC_SET_MC_HEAP; + mc_model_checker = xbt_new0(s_mc_model_checker_t, 1); + mc_model_checker->pages = mc_pages_store_new(); + mc_model_checker->fd_clear_refs = -1; + mc_model_checker->fd_pagemap = -1; + mc_comp_times = xbt_new0(s_mc_comparison_times_t, 1); /* Initialize statistics */ @@ -261,12 +275,16 @@ void MC_init() MC_ignore_local_variable("ctx", "*"); MC_ignore_local_variable("self", "simcall_BODY_mc_snapshot"); - MC_ignore_local_variable("next_context", "smx_ctx_sysv_suspend_serial"); + MC_ignore_local_variable("next_cont" + "ext", "smx_ctx_sysv_suspend_serial"); MC_ignore_local_variable("i", "smx_ctx_sysv_suspend_serial"); /* Ignore local variable about time used for tracing */ MC_ignore_local_variable("start_time", "*"); + MC_ignore_global_variable("mc_model_checker"); + + // Mot of those things could be moved into mc_model_checker: MC_ignore_global_variable("compared_pointers"); MC_ignore_global_variable("mc_comp_times"); MC_ignore_global_variable("mc_snapshot_comparison_time"); @@ -277,6 +295,7 @@ void MC_init() MC_ignore_global_variable("maestro_stack_end"); MC_ignore_global_variable("smx_total_comms"); + MC_ignore_heap(mc_time, simix_process_maxpid * sizeof(double)); smx_process_t process; diff --git a/src/mc/mc_mmu.h b/src/mc/mc_mmu.h new file mode 100644 index 0000000000..8df82fa306 --- /dev/null +++ b/src/mc/mc_mmu.h @@ -0,0 +1,58 @@ +/* Copyright (c) 2014. 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 MC_MMU_H +#define MC_MMU_H + +#include + +#include "mc_private.h" + +/** @brief How many memory pages are necessary to store size bytes? + * + * @param size Byte size + * @return Number of memory pages + */ +static inline size_t mc_page_count(size_t size) +{ + size_t page_count = size >> xbt_pagebits; + if (size & (xbt_pagesize-1)) { + page_count ++; + } + return page_count; +} + +/** @brief Get the virtual memory page number of a given address + * + * @param address Address + * @return Virtual memory page number of the given address + */ +static inline size_t mc_page_number(void* address) +{ + return ((uintptr_t) address) >> xbt_pagebits; +} + +/** @brief Get the offset of an address within a memory page + * + * @param address Address + * @return Offset within the memory page + */ +static inline size_t mc_page_offset(void* address) +{ + return ((uintptr_t) address) & (xbt_pagesize-1); +} + +/** @brief Get the virtual address of a virtual memory page + * + * @param base Address of the first page + * @param page Index of the page + */ +static inline void* mc_page_from_number(void* base, size_t page) +{ + return (void*) ((char*)base + (page << xbt_pagebits)); +} + +#endif diff --git a/src/mc/mc_page_snapshot.cpp b/src/mc/mc_page_snapshot.cpp new file mode 100644 index 0000000000..245fc13e53 --- /dev/null +++ b/src/mc/mc_page_snapshot.cpp @@ -0,0 +1,174 @@ +#include "mc_page_store.h" +#include "mc_mmu.h" + +#define SOFT_DIRTY_BIT_NUMBER 55 +#define SOFT_DIRTY (((uint64_t)1) << SOFT_DIRTY_BIT_NUMBER) + +extern "C" { + +// ***** Region management: + +size_t* mc_take_page_snapshot_region(void* data, size_t page_count, uint64_t* pagemap, size_t* reference_pages) +{ + size_t* pagenos = (size_t*) malloc(page_count * sizeof(size_t)); + + for (size_t i=0; i!=page_count; ++i) { + if (pagemap && (pagemap[i] & SOFT_DIRTY)) { + // The page is softclean, it is the same page as the reference page: + pagenos[i] = reference_pages[i]; + mc_model_checker->pages->ref_page(reference_pages[i]); + } else { + // Otherwise, we need to store the page the hard hard + // (by reading its content): + void* page = (char*) data + (i << xbt_pagebits); + pagenos[i] = mc_model_checker->pages->store_page(page); + } + } + + return pagenos; +} + +void mc_free_page_snapshot_region(size_t* pagenos, size_t page_count) +{ + for (size_t i=0; i!=page_count; ++i) { + mc_model_checker->pages->unref_page(pagenos[i]); + } +} + +void mc_restore_page_snapshot_region(mc_mem_region_t region, size_t page_count, uint64_t* pagemap, mc_mem_region_t reference_region) +{ + for (size_t i=0; i!=page_count; ++i) { + + bool softclean = pagemap && !(pagemap[i] & SOFT_DIRTY); + if (softclean && reference_region && reference_region->page_numbers[i] == region->page_numbers[i]) { + // The page is softclean and is the same as the reference one: + // the page is already in the target state. + continue; + } + + // Otherwise, copy the page: + void* target_page = mc_page_from_number(region->start_addr, i); + const void* source_page = mc_model_checker->pages->get_page(region->page_numbers[i]); + memcpy(target_page, source_page, xbt_pagesize); + } +} + +// ***** Soft dirty tracking + +/** @brief Like pread() but without partial reads */ +static size_t pread_whole(int fd, void* buf, size_t count, off_t offset) { + size_t res; + + char* data = (char*) buf; + while(count) { + ssize_t n = pread(fd, buf, count, offset); + // EOF + if (n==0) + return res; + + // Error (or EAGAIN): + if (n==-1) { + if (errno == EAGAIN) + continue; + else + return -1; + } + + count -= n; + data += n; + offset += n; + res += n; + } + + return res; +} + +static inline void mc_ensure_fd(int* fd, const char* path, int flags) { + if (*fd != -1) + return; + *fd = open(path, flags); + if (*fd == -1) { + xbt_die("Could not open file %s", path); + } +} + +/** @brief Reset the softdirty bits + * + * This is done after checkpointing and after checkpoint restoration + * (if per page checkpoiting is used) in order to know which pages were + * modified. + * */ +void mc_softdirty_reset() { + mc_ensure_fd(&mc_model_checker->fd_clear_refs, "/proc/self/clear_refs", O_WRONLY|O_CLOEXEC); + if( ::write(mc_model_checker->fd_clear_refs, "4\n", 2) != 2) { + xbt_die("Could not reset softdirty bits"); + } +} + +/** @brief Read /proc/self/pagemap informations in order to find properties on the pages + * + * For each virtual memory page, this file provides informations. + * We are interested in the soft-dirty bit: with this we can track which + * pages were modified between snapshots/restorations and avoid + * copying data which was not modified. + * + * @param pagemap Output buffer for pagemap informations + * @param start_addr Address of the first page + * @param page_count Number of pages + */ +static void mc_read_pagemap(uint64_t* pagemap, size_t page_start, size_t page_count) +{ + mc_ensure_fd(&mc_model_checker->fd_pagemap, "/proc/self/pagemap", O_RDONLY|O_CLOEXEC); + size_t bytesize = sizeof(uint64_t) * page_count; + off_t offset = sizeof(uint64_t) * page_start; + if (pread_whole(mc_model_checker->fd_pagemap, pagemap, bytesize, offset) != bytesize) { + xbt_die("Coult not read pagemap"); + } +} + +// ***** High level API + +mc_mem_region_t mc_region_new_sparse(int type, void *start_addr, size_t size, mc_mem_region_t ref_reg) +{ + mc_mem_region_t new_reg = xbt_new(s_mc_mem_region_t, 1); + + new_reg->start_addr = start_addr; + new_reg->data = NULL; + new_reg->size = size; + new_reg->page_numbers = NULL; + + xbt_assert((((uintptr_t)start_addr) & (xbt_pagesize-1)) == 0, + "Not at the beginning of a page"); + size_t page_count = mc_page_count(size); + + uint64_t* pagemap = NULL; + if (mc_model_checker->parent_snapshot) { + pagemap = (uint64_t*) alloca(sizeof(uint64_t) * page_count); + mc_read_pagemap(pagemap, mc_page_number(start_addr), page_count); + } + + // Take incremental snapshot: + new_reg->page_numbers = mc_take_page_snapshot_region(start_addr, page_count, pagemap, ref_reg->page_numbers); + + return new_reg; +} + +void mc_region_restore_sparse(mc_mem_region_t reg, mc_mem_region_t ref_reg) +{ + xbt_assert((((uintptr_t)reg->start_addr) & (xbt_pagesize-1)) == 0, + "Not at the beginning of a page"); + size_t page_count = mc_page_count(reg->size); + + uint64_t* pagemap = NULL; + + // Read soft-dirty bits if necessary in order to know which pages have changed: + if (mc_model_checker->parent_snapshot) { + pagemap = (uint64_t*) alloca(sizeof(uint64_t) * page_count); + mc_read_pagemap(pagemap, mc_page_number(reg->start_addr), page_count); + } + + // Incremental per-page snapshot restoration: + mc_restore_page_snapshot_region(reg, page_count, pagemap, ref_reg); +} + +} diff --git a/src/mc/mc_page_store.cpp b/src/mc/mc_page_store.cpp new file mode 100644 index 0000000000..b91af866ed --- /dev/null +++ b/src/mc/mc_page_store.cpp @@ -0,0 +1,161 @@ +/* Copyright (c) 2014. 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 // memcpy, memcp + +#include + +#include + +#include "mc_page_store.h" + +#include "mc_mmu.h" + +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_page_snapshot, mc, + "Logging specific to mc_page_snapshot"); + +extern "C" { + +static void mc_read_pagemap(uint64_t* pagemap, size_t page_start, size_t page_count); + +} + +// ***** Utility: + +/** @brief Compte 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 pae in the page store. + * + * @param data Memory page + * @return hash off the page + */ +static inline uint64_t mc_hash_page(const void* data) +{ + const uint64_t* values = (const uint64_t*) data; + size_t n = xbt_pagesize / sizeof(uint64_t); + + // This djb2: + uint64_t hash = 5381; + for (size_t i=0; i!=n; ++i) { + hash = ((hash << 5) + hash) + values[i]; + } + return hash; +} + +// ***** snapshot_page_manager + +s_mc_pages_store::s_mc_pages_store(size_t size) : + memory_(NULL), capacity_(0), 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(NULL, size << xbt_pagebits, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS|MAP_POPULATE, -1, 0); + if (memory==MAP_FAILED) { + xbt_die("Could not mmap initial snapshot pages."); + } + + this->top_index_ = 0; + this->capacity_ = size; + this->memory_ = memory; + this->page_counts_.resize(size); +} + +s_mc_pages_store::~s_mc_pages_store() +{ + ::munmap(this->memory_, this->capacity_ << xbt_pagebits); +} + +void s_mc_pages_store::resize(size_t size) +{ + size_t new_bytesize = size << xbt_pagebits; + + // Expand the memory region by moving it into another + // virtual memory address if necessary: + void* new_memory = mremap(this->memory_, this->capacity_ << xbt_pagesize, new_bytesize, MREMAP_MAYMOVE); + if (new_memory == MAP_FAILED) { + xbt_die("Could not mremap snapshot pages."); + } + + this->capacity_ = size; + this->memory_ = new_memory; + this->page_counts_.resize(size); +} + +/** Allocate a free page + * + * @return index of the free page + */ +size_t s_mc_pages_store::alloc_page() +{ + if (this->free_pages_.empty()) { + + // Expand the region: + if (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 s_mc_pages_store::remove_page(size_t pageno) +{ + this->free_pages_.push_back(pageno); + void* page = mc_page_from_number(this->memory_, pageno); + uint64_t hash = mc_hash_page(page); + this->hash_index_[hash].erase(pageno); +} + +/** Store a page in memory */ +size_t s_mc_pages_store::store_page(void* page) +{ + xbt_assert(mc_page_offset(page)==0, "Not at the beginning of a page"); + xbt_assert(top_index_ <= this->capacity_, "top_index is not consistent"); + + // Search the page in the snapshot pages: + uint64_t hash = mc_hash_page(page); + page_set_type& page_set = this->hash_index_[hash]; + BOOST_FOREACH (size_t pageno, page_set) { + const void* snapshot_page = this->get_page(pageno); + if (memcmp(page, snapshot_page, xbt_pagesize) == 0) { + // Page found, reuse it: + page_counts_[pageno]++; + return pageno; + } + } + + // Allocate a new page for this page: + size_t pageno = alloc_page(); + void* snapshot_page = (void*) this->get_page(pageno); + memcpy(snapshot_page, page, xbt_pagesize); + page_set.insert(pageno); + page_counts_[pageno]++; + return pageno; +} + +// ***** Main C API + +extern "C" { + +mc_pages_store_t mc_pages_store_new() +{ + return new s_mc_pages_store_t(500); +} + +} diff --git a/src/mc/mc_page_store.h b/src/mc/mc_page_store.h new file mode 100644 index 0000000000..db52b1851c --- /dev/null +++ b/src/mc/mc_page_store.h @@ -0,0 +1,111 @@ +/* Copyright (c) 2014. 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 + +#include + +#include "mc_private.h" +#include "mc_mmu.h" + +#ifndef MC_PAGE_SNAPSHOT_H +#define MC_PAGE_SNAPSHOT_H + +/** @brief Manager for snapshot pages + * + * Page management: the free pages are stored as a simple linked-list. + * The number of the first page if stored in `free_pages`. + * Each free page store the number of the next free page. + */ +struct s_mc_pages_store { +private: // Types + typedef uint64_t hash_type; + typedef boost ::unordered_set page_set_type; + typedef boost::unordered_map pages_map_type; + +private: // Fields: + /** First page */ + void* memory_; + /** Number of available pages in virtual memory */ + size_t capacity_; + /** Top of the used pages (index of the next available page) */ + 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_; + +private: // Methods + void resize(size_t size); + size_t alloc_page(); + void remove_page(size_t pageno); + +public: // Constructors + explicit s_mc_pages_store(size_t size); + ~s_mc_pages_store(); + +public: // Methods + + /** @brief Decrement the refcount for a given page */ + void unref_page(size_t pageno) { + if ((--this->page_counts_[pageno]) == 0) { + this->remove_page(pageno); + } + } + + /** @brief Increment the refcount for a given page */ + void ref_page(size_t pageno) { + ++this->page_counts_[pageno]; + } + + /** @brief Store a page + * + * Either allocate a new page in the store or reuse + * a shared page if is is already in the page store. + */ + size_t store_page(void* page); + + /** @brief Get a page from its page number + * + * @param Number of the memory page in the store + * @return Start of the page + */ + const void* get_page(size_t pageno) const { + return mc_page_from_number(this->memory_, pageno); + } + +public: // Debug/test methods + + /** @brief Get the number of references for a page */ + size_t get_ref(size_t pageno) { + return this->page_counts_[pageno]; + } + + /** @brief Get the number of used pages */ + size_t size() { + return this->top_index_ - this->free_pages_.size(); + } + + /** @brief Get the capacity of the page store + * + * The capacity is expanded by a system call (mremap). + * */ + size_t capacity() { + return this->capacity_; + } + +}; + +#endif + diff --git a/src/mc/mc_private.h b/src/mc/mc_private.h index dd30b53972..62a82f5fdd 100644 --- a/src/mc/mc_private.h +++ b/src/mc/mc_private.h @@ -43,6 +43,8 @@ typedef struct s_mc_mem_region{ void *data; // Size of the data region: size_t size; + // For per-page snapshots, this is an array to the number of + size_t* page_numbers; } s_mc_mem_region_t, *mc_mem_region_t; /** Ignored data @@ -105,6 +107,8 @@ typedef struct s_mc_checkpoint_ignore_region{ size_t size; }s_mc_checkpoint_ignore_region_t, *mc_checkpoint_ignore_region_t; +SG_BEGIN_DECL() + inline static void* mc_snapshot_get_heap_end(mc_snapshot_t snapshot) { if(snapshot==NULL) xbt_die("snapshot is NULL"); @@ -117,6 +121,36 @@ mc_snapshot_t MC_take_snapshot(int num_state); void MC_restore_snapshot(mc_snapshot_t); void MC_free_snapshot(mc_snapshot_t); +int mc_important_snapshot(mc_snapshot_t snapshot); + +size_t* mc_take_page_snapshot_region(void* data, size_t page_count, uint64_t* pagemap, size_t* reference_pages); +void mc_free_page_snapshot_region(size_t* pagenos, size_t page_count); +void mc_restore_page_snapshot_region(mc_mem_region_t region, size_t page_count, uint64_t* pagemap, mc_mem_region_t reference_region); + +mc_mem_region_t mc_region_new_sparse(int type, void *start_addr, size_t size, mc_mem_region_t ref_reg); +void mc_region_restore_sparse(mc_mem_region_t reg, mc_mem_region_t ref_reg); +void mc_softdirty_reset(); + +typedef struct s_mc_pages_store s_mc_pages_store_t, * mc_pages_store_t; +mc_pages_store_t mc_pages_store_new(); + +/** @brief State of the model-checker (global variables for the model checker) + * + * Each part of the state of the model chercker represented as a global + * variable prevents some sharing between snapshots and must be ignored. + * By moving as much state as possible in this structure allocated + * on the model-chercker heap, we avoid those issues. + */ +typedef struct s_mc_model_checker { + // This is the parent snapshot of the current state: + mc_snapshot_t parent_snapshot; + mc_pages_store_t pages; + int fd_clear_refs; + int fd_pagemap; +} s_mc_model_checker_t, *mc_model_checker_t; + +extern mc_model_checker_t mc_model_checker; + /** \brief Translate a pointer from process address space to snapshot address space * * The address space contains snapshot of the main/application memory: @@ -618,5 +652,7 @@ bool mc_address_test(mc_address_set_t p, const void* value); * */ uint64_t mc_hash_processes_state(int num_state, xbt_dynar_t stacks); +SG_END_DECL() + #endif diff --git a/src/mc/mc_visited.c b/src/mc/mc_visited.c index 172d1a8c3b..671d702eaf 100644 --- a/src/mc/mc_visited.c +++ b/src/mc/mc_visited.c @@ -312,8 +312,8 @@ int is_visited_state() int min2 = mc_stats->expanded_states; unsigned int cursor2 = 0; unsigned int index2 = 0; - xbt_dynar_foreach(visited_states, cursor2, state_test) { - if (state_test->num < min2) { + xbt_dynar_foreach(visited_states, cursor2, state_test){ + if (!mc_important_snapshot(state_test->system_state) && state_test->num < min2) { index2 = cursor2; min2 = state_test->num; } @@ -457,7 +457,7 @@ int is_visited_pair(mc_visited_pair_t pair, int pair_num, unsigned int cursor2 = 0; unsigned int index2 = 0; xbt_dynar_foreach(visited_pairs, cursor2, pair_test) { - if (pair_test->num < min2) { + if (!mc_important_snapshot(pair_test->graph_state->system_state) && pair_test->num < min2) { index2 = cursor2; min2 = pair_test->num; } diff --git a/src/xbt/xbt_main.c b/src/xbt/xbt_main.c index 615ad8d16b..c355f497ab 100644 --- a/src/xbt/xbt_main.c +++ b/src/xbt/xbt_main.c @@ -39,6 +39,7 @@ int xbt_initialized = 0; int _sg_do_clean_atexit = 1; int xbt_pagesize; +int xbt_pagebits = 0; /* Declare xbt_preinit and xbt_postexit as constructor/destructor of the library. * This is crude and rather compiler-specific, unfortunately. @@ -95,6 +96,13 @@ static void xbt_preinit(void) { GetSystemInfo(&si); xbt_pagesize = si.dwPageSize; #endif + + xbt_pagebits = 0; + int x = xbt_pagesize; + while(x >>= 1) { + ++xbt_pagebits; + } + #ifdef MMALLOC_WANT_OVERRIDE_LEGACY mmalloc_preinit(); #endif @@ -112,7 +120,6 @@ static void xbt_preinit(void) { #ifndef _WIN32 srand48(seed); #endif - atexit(xbt_postexit); } diff --git a/teshsuite/mc/CMakeLists.txt b/teshsuite/mc/CMakeLists.txt new file mode 100644 index 0000000000..8e986cf79e --- /dev/null +++ b/teshsuite/mc/CMakeLists.txt @@ -0,0 +1,19 @@ +cmake_minimum_required(VERSION 2.6) + +if(HAVE_MC) + set(EXECUTABLE_OUTPUT_PATH "${CMAKE_CURRENT_BINARY_DIR}") + + add_executable(page_store page_store.cpp) + target_link_libraries(page_store simgrid) +endif() + +set(tesh_files + ${tesh_files} + ${CMAKE_CURRENT_SOURCE_DIR}/page_store.tesh + PARENT_SCOPE + ) +set(testsuite_src + ${testsuite_src} + ${CMAKE_CURRENT_SOURCE_DIR}/page_store.cpp + PARENT_SCOPE + ) diff --git a/teshsuite/mc/page_store.cpp b/teshsuite/mc/page_store.cpp new file mode 100644 index 0000000000..592b9babac --- /dev/null +++ b/teshsuite/mc/page_store.cpp @@ -0,0 +1,66 @@ +#include +#include +#include +#include +#include + +#include "mc/mc_page_store.h" + +static int value = 0; + +static void new_content(void* data, size_t size) +{ + memset(data, ++value, size); +} + +static void* getpage() +{ + return mmap(NULL, getpagesize(), PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); +} + +int main(int argc, char** argv) +{ + // Init + size_t pagesize = (size_t) getpagesize(); + mc_pages_store_t store = new s_mc_pages_store(500); + void* data = getpage(); + + // Init: + xbt_assert(store->size()==0, "Bad size"); + + // Store the page once: + new_content(data, pagesize); + size_t pageno1 = store->store_page(data); + xbt_assert(store->get_ref(pageno1)==1, "Bad refcount"); + const void* copy = store->get_page(pageno1); + xbt_assert(memcmp(data, copy, pagesize)==0, "Page data should be the same"); + xbt_assert(store->size()==1, "Bad size"); + + // Store the same page again: + size_t pageno2 = store->store_page(data); + xbt_assert(pageno1==pageno2, "Page should be the same"); + xbt_assert(store->get_ref(pageno1)==2, "Bad refcount"); + xbt_assert(store->size()==1, "Bad size"); + + // Store a new page: + new_content(data, pagesize); + size_t pageno3 = store->store_page(data); + xbt_assert(pageno1 != pageno3, "New page should be different"); + xbt_assert(store->size()==2, "Bad size"); + + // 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_assert(store->size()==1, "Bad size"); + + // Reallocate page: + new_content(data, pagesize); + size_t pageno4 = store->store_page(data); + xbt_assert(pageno1 == pageno4, "Page was not reused"); + xbt_assert(store->get_ref(pageno4)==1, "Bad refcount"); + xbt_assert(store->size()==2, "Bad size"); + + return 0; +} diff --git a/teshsuite/mc/page_store.tesh b/teshsuite/mc/page_store.tesh new file mode 100644 index 0000000000..f319a51257 --- /dev/null +++ b/teshsuite/mc/page_store.tesh @@ -0,0 +1,3 @@ +#! ./tesh + +$ $SG_TEST_EXENV ${bindir:=.}/page_store