From e3ab35679ccd20b749f6034f17e86c2b51abcc2e Mon Sep 17 00:00:00 2001 From: Gabriel Corona Date: Tue, 16 Sep 2014 09:44:29 +0200 Subject: [PATCH] [mc] Add a (compile time) option for content addressage page store MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit With a simple hash, we expect collision to happen: when inserting a new page in the store, each stored page with the same hash is compared (memcmp-ed) with the current page. If a page already present is inserted, the content of the stored page is always pulled in the cache: when inserting n pages, into the page store at least 2×n pages are pulled in the cache. With this option, a collision-free fingerprint of each page is computed. As there is no collision, we do not have to check the content of the stored pages. MD4 is used as we do not need security against malicious users and it is much faster than more sescure cryptographic hashes. --- buildtools/Cmake/Flags.cmake | 5 ++++ buildtools/Cmake/MakeLib.cmake | 4 ++++ buildtools/Cmake/Option.cmake | 1 + src/mc/mc_page_store.cpp | 43 ++++++++++++++++++++++++++++++---- src/mc/mc_page_store.h | 20 ++++++++++++++-- 5 files changed, 67 insertions(+), 6 deletions(-) diff --git a/buildtools/Cmake/Flags.cmake b/buildtools/Cmake/Flags.cmake index a46ae13e79..19e010636c 100644 --- a/buildtools/Cmake/Flags.cmake +++ b/buildtools/Cmake/Flags.cmake @@ -68,6 +68,11 @@ if(enable_model-checking AND enable_compile_optimizations) endforeach() endif() +if(enable_mc_content_adressable_pages) + set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -DMC_PAGE_STORE_MD4") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DMC_PAGE_STORE_MD4") +endif() + if(APPLE AND COMPILER_C_VERSION_MAJOR_MINOR MATCHES "4.6") set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -Wno-deprecated-declarations") set(optCFLAGS "-O0 ") diff --git a/buildtools/Cmake/MakeLib.cmake b/buildtools/Cmake/MakeLib.cmake index ef15efa4a7..f73882a51d 100644 --- a/buildtools/Cmake/MakeLib.cmake +++ b/buildtools/Cmake/MakeLib.cmake @@ -81,6 +81,10 @@ if(HAVE_GTNETS) SET(SIMGRID_DEP "${SIMGRID_DEP} -lgtnets") endif() +if(enable_mc_content_adressable_pages) + SET(SIMGRID_DEP "${SIMGRID_DEP} -lnettle") +endif() + if(HAVE_MC) # The availability of libunwind was checked in CompleteInFiles.cmake # (that includes FindLibunwind.cmake), so simply load it now. diff --git a/buildtools/Cmake/Option.cmake b/buildtools/Cmake/Option.cmake index 0bde6df58e..eb1aae11ff 100644 --- a/buildtools/Cmake/Option.cmake +++ b/buildtools/Cmake/Option.cmake @@ -36,6 +36,7 @@ option(enable_mallocators "Enable mallocators (disable only for debugging purpos option(enable_print_message "Enable print message during config." off) mark_as_advanced(enable_print_message) option(enable_model-checking "Turn this on to experiment with our prototype of model-checker (hinders the simulation's performance even if turned of at runtime)" off) +option(enable_mc_content_adressable_pages "Content addressable page storage (rely on the hash of the pages for page snapshot)" off) option(enable_lib_static "" off) option(enable_lib_in_jar "Whether the native libraries are bundled into the Java jar file" on) option(enable_jedule "Jedule output of SimDAG." off) diff --git a/src/mc/mc_page_store.cpp b/src/mc/mc_page_store.cpp index a2072b39c3..11022f8991 100644 --- a/src/mc/mc_page_store.cpp +++ b/src/mc/mc_page_store.cpp @@ -15,6 +15,10 @@ #include "mc_page_store.h" +#ifdef MC_PAGE_STORE_MD4 +#include +#endif + #include "mc_mmu.h" XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_page_snapshot, mc, @@ -25,14 +29,22 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_page_snapshot, mc, /** @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. + * in order to find duplicate of this page in the page store. * * @param data Memory page * @return hash off the page */ static inline __attribute__ ((always_inline)) -uint64_t mc_hash_page(const void* data) +s_mc_pages_store::hash_type mc_hash_page(const void* data) { +#ifdef MC_PAGE_STORE_MD4 + boost::array result; + md4_ctx context; + md4_init(&context); + md4_update(&context, xbt_pagesize, (const uint8_t*) data); + md4_digest(&context, MD4_DIGEST_SIZE, (uint8_t*) &(result[0])); + return result; +#else const uint64_t* values = (const uint64_t*) data; size_t n = xbt_pagesize / sizeof(uint64_t); @@ -42,6 +54,7 @@ uint64_t mc_hash_page(const void* data) hash = ((hash << 5) + hash) + values[i]; } return hash; +#endif } // ***** snapshot_page_manager @@ -116,8 +129,12 @@ void s_mc_pages_store::remove_page(size_t pageno) { this->free_pages_.push_back(pageno); const void* page = this->get_page(pageno); - uint64_t hash = mc_hash_page(page); + hash_type hash = mc_hash_page(page); +#ifdef MC_PAGE_STORE_MD4 + this->hash_index_.erase(hash); +#else this->hash_index_[hash].erase(pageno); +#endif } /** Store a page in memory */ @@ -131,7 +148,20 @@ size_t s_mc_pages_store::store_page(void* page) // 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. - uint64_t hash = mc_hash_page(page); + hash_type hash = mc_hash_page(page); +#ifdef MC_PAGE_STORE_MD4 + s_mc_pages_store::pages_map_type::const_iterator i = + this->hash_index_.find(hash); + if (i!=this->hash_index_.cend()) { + // If a page with the same content is already in the page store it is + // reused and its reference count is incremented. + size_t pageno = i->second; + page_counts_[pageno]++; + return pageno; + } +#else + + // Try to find a duplicate in set of pages with the same hash: page_set_type& page_set = this->hash_index_[hash]; BOOST_FOREACH (size_t pageno, page_set) { const void* snapshot_page = this->get_page(pageno); @@ -144,6 +174,7 @@ size_t s_mc_pages_store::store_page(void* page) } } +#endif // Otherwise, a new page is allocated in the page store and the content // of the page is `memcpy()`-ed to this new page. @@ -151,7 +182,11 @@ size_t s_mc_pages_store::store_page(void* 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); +#ifdef MC_PAGE_STORE_MD4 + this->hash_index_[hash] = pageno; +#else page_set.insert(pageno); +#endif page_counts_[pageno]++; return pageno; } diff --git a/src/mc/mc_page_store.h b/src/mc/mc_page_store.h index 8018016b2f..9b7841876e 100644 --- a/src/mc/mc_page_store.h +++ b/src/mc/mc_page_store.h @@ -9,6 +9,7 @@ #ifdef __cplusplus #include +#include #include #include #include @@ -78,10 +79,25 @@ struct s_mc_pages_store; * */ struct s_mc_pages_store { -private: // Types +public: // Types +#ifdef MC_PAGE_STORE_MD4 + typedef boost::array hash_type; +#else typedef uint64_t hash_type; - typedef boost ::unordered_set page_set_type; +#endif +private: // Types +#ifdef MC_PAGE_STORE_MD4 + // We are using a secure hash to identify a page. + // We assume there will not be any collision: we need to map a hash + // to a single page index. + typedef boost::unordered_map pages_map_type; +#else + // 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 boost::unordered_set page_set_type; typedef boost::unordered_map pages_map_type; +#endif private: // Fields: /** First page -- 2.20.1