Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
[mc] Add a (compile time) option for content addressage page store
authorGabriel Corona <gabriel.corona@loria.fr>
Tue, 16 Sep 2014 07:44:29 +0000 (09:44 +0200)
committerGabriel Corona <gabriel.corona@loria.fr>
Tue, 16 Sep 2014 12:09:44 +0000 (14:09 +0200)
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
buildtools/Cmake/MakeLib.cmake
buildtools/Cmake/Option.cmake
src/mc/mc_page_store.cpp
src/mc/mc_page_store.h

index a46ae13..19e0106 100644 (file)
@@ -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 ")
index ef15efa..f73882a 100644 (file)
@@ -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.
index 0bde6df..eb1aae1 100644 (file)
@@ -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)
index a2072b3..11022f8 100644 (file)
 
 #include "mc_page_store.h"
 
+#ifdef MC_PAGE_STORE_MD4
+#include <nettle/md4.h>
+#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<uint64_t,2> 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;
 }
index 8018016..9b78418 100644 (file)
@@ -9,6 +9,7 @@
 #ifdef __cplusplus
 #include <vector>
 
+#include <boost/array.hpp>
 #include <boost/utility.hpp>
 #include <boost/unordered_map.hpp>
 #include <boost/unordered_set.hpp>
@@ -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<uint64_t,2> hash_type;
+#else
   typedef uint64_t hash_type;
-  typedef boost ::unordered_set<size_t> 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<hash_type, size_t> 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<size_t> page_set_type;
   typedef boost::unordered_map<hash_type, page_set_type> pages_map_type;
+#endif
 
 private: // Fields:
   /** First page