Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Set waitpid() for model-checked flags according to platform.
[simgrid.git] / src / mc / PageStore.cpp
1 /* Copyright (c) 2015. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 #include <unistd.h>
8 #include <string.h> // memcpy, memcmp
9
10 #include <sys/mman.h>
11
12 #include <xbt/base.h>
13 #include <xbt/log.h>
14 #include <xbt/sysdep.h>
15
16 #include "src/mc/PageStore.hpp"
17
18 #include "src/mc/mc_mmu.h"
19
20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_page_snapshot, mc,
21                                 "Logging specific to mc_page_snapshot");
22
23 namespace simgrid {
24 namespace mc {
25
26 /** @brief Compute a hash for the given memory page
27  *
28  *  The page is used before inserting the page in the page store
29  *  in order to find duplicate of this page in the page store.
30  *
31  *  @param data Memory page
32  *  @return hash off the page
33  */
34 static inline  __attribute__ ((always_inline))
35 PageStore::hash_type mc_hash_page(const void* data)
36 {
37   const std::uint64_t* values = (const uint64_t*) data;
38   std::size_t n = xbt_pagesize / sizeof(uint64_t);
39
40   // This djb2:
41   std::uint64_t hash = 5381;
42   for (std::size_t i = 0; i != n; ++i)
43     hash = ((hash << 5) + hash) + values[i];
44   return hash;
45 }
46
47 // ***** snapshot_page_manager
48
49 PageStore::PageStore(size_t size) :
50   memory_(nullptr), capacity_(0), top_index_(0)
51 {
52   // Using mmap in order to be able to expand the region
53   // by relocating it somewhere else in the virtual memory
54   // space:
55   void* memory = ::mmap(nullptr, size << xbt_pagebits, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, -1, 0);
56   if (memory == MAP_FAILED)
57     xbt_die("Could not mmap initial snapshot pages.");
58
59   this->top_index_ = 0;
60   this->capacity_ = size;
61   this->memory_ = memory;
62   this->page_counts_.resize(size);
63 }
64
65 PageStore::~PageStore()
66 {
67   ::munmap(this->memory_, this->capacity_ << xbt_pagebits);
68 }
69
70 void PageStore::resize(std::size_t size)
71 {
72   size_t old_bytesize = this->capacity_ << xbt_pagebits;
73   size_t new_bytesize = size << xbt_pagebits;
74
75   // Expand the memory region by moving it into another
76   // virtual memory address if necessary:
77   void* new_memory = mremap(this->memory_, old_bytesize, new_bytesize, MREMAP_MAYMOVE);
78   if (new_memory == MAP_FAILED)
79     xbt_die("Could not mremap snapshot pages.");
80
81   this->capacity_ = size;
82   this->memory_ = new_memory;
83   this->page_counts_.resize(size, 0);
84 }
85
86 /** Allocate a free page
87  *
88  *  @return index of the free page
89  */
90 std::size_t PageStore::alloc_page()
91 {
92   if (this->free_pages_.empty()) {
93
94     // Expand the region:
95     if (this->top_index_ == this->capacity_)
96       // All the pages are allocated, we need add more pages:
97       this->resize(2 * this->capacity_);
98
99     // Use a page from the top:
100     return this->top_index_++;
101
102   } else {
103
104     // Use a page from free_pages_ (inside of the region):
105     size_t res = this->free_pages_[this->free_pages_.size() - 1];
106     this->free_pages_.pop_back();
107     return res;
108
109   }
110 }
111
112 void PageStore::remove_page(std::size_t pageno)
113 {
114   this->free_pages_.push_back(pageno);
115   const void* page = this->get_page(pageno);
116   hash_type hash = mc_hash_page(page);
117   this->hash_index_[hash].erase(pageno);
118 }
119
120 /** Store a page in memory */
121 std::size_t PageStore::store_page(void* page)
122 {
123   xbt_assert(top_index_ <= this->capacity_, "top_index is not consistent");
124
125   // First, we check if a page with the same content is already in the page
126   // store:
127   //  1. compute the hash of the page;
128   //  2. find pages with the same hash using `hash_index_`;
129   //  3. find a page with the same content.
130   hash_type hash = mc_hash_page(page);
131
132   // Try to find a duplicate in set of pages with the same hash:
133   page_set_type& page_set = this->hash_index_[hash];
134   for (size_t pageno : page_set) {
135     const void* snapshot_page = this->get_page(pageno);
136     if (memcmp(page, snapshot_page, xbt_pagesize) == 0) {
137
138       // If a page with the same content is already in the page store it is
139       // reused and its reference count is incremented.
140       page_counts_[pageno]++;
141       return pageno;
142
143     }
144   }
145
146   // Otherwise, a new page is allocated in the page store and the content
147   // of the page is `memcpy()`-ed to this new page.
148   std::size_t pageno = alloc_page();
149   xbt_assert(this->page_counts_[pageno]==0, "Allocated page is already used");
150   void* snapshot_page = (void*) this->get_page(pageno);
151   memcpy(snapshot_page, page, xbt_pagesize);
152   page_set.insert(pageno);
153   page_counts_[pageno]++;
154   return pageno;
155 }
156
157 }
158 }
159
160 #ifdef SIMGRID_TEST
161
162 #include <cstring>
163 #include <cstdint>
164
165 #include <unistd.h>
166 #include <sys/mman.h>
167
168 #include <memory>
169
170 #include "src/mc/PageStore.hpp"
171
172 static int value = 0;
173
174 static void new_content(void* data, std::size_t size)
175 {
176   ::memset(data, ++value, size);
177 }
178
179 static void* getpage()
180 {
181   return mmap(nullptr, getpagesize(), PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
182 }
183
184 XBT_TEST_SUITE("mc_page_store", "Page store");
185
186 XBT_TEST_UNIT("base", test_mc_page_store, "Test adding/removing pages in the store")
187 {
188   using simgrid::mc::PageStore;
189   
190   xbt_test_add("Init");
191   std::size_t pagesize = (size_t) getpagesize();
192   std::unique_ptr<PageStore> store
193     = std::unique_ptr<PageStore>(new simgrid::mc::PageStore(500));
194   void* data = getpage();
195   xbt_test_assert(store->size()==0, "Bad size");
196
197   xbt_test_add("Store the page once");
198   new_content(data, pagesize);
199   size_t pageno1 = store->store_page(data);
200   xbt_test_assert(store->get_ref(pageno1)==1, "Bad refcount");
201   const void* copy = store->get_page(pageno1);
202   xbt_test_assert(::memcmp(data, copy, pagesize)==0, "Page data should be the same");
203   xbt_test_assert(store->size()==1, "Bad size");
204
205   xbt_test_add("Store the same page again");
206   size_t pageno2 = store->store_page(data);
207   xbt_test_assert(pageno1==pageno2, "Page should be the same");
208   xbt_test_assert(store->get_ref(pageno1)==2, "Bad refcount");
209   xbt_test_assert(store->size()==1, "Bad size");
210
211   xbt_test_add("Store a new page");
212   new_content(data, pagesize);
213   size_t pageno3 = store->store_page(data);
214   xbt_test_assert(pageno1 != pageno3, "New page should be different");
215   xbt_test_assert(store->size()==2, "Bad size");
216
217   xbt_test_add("Unref pages");
218   store->unref_page(pageno1);
219   xbt_assert(store->get_ref(pageno1)==1, "Bad refcount");
220   xbt_assert(store->size()==2, "Bad size");
221   store->unref_page(pageno2);
222   xbt_test_assert(store->size()==1, "Bad size");
223
224   xbt_test_add("Reallocate page");
225   new_content(data, pagesize);
226   size_t pageno4 = store->store_page(data);
227   xbt_test_assert(pageno1 == pageno4, "Page was not reused");
228   xbt_test_assert(store->get_ref(pageno4)==1, "Bad refcount");
229   xbt_test_assert(store->size()==2, "Bad size");
230 }
231
232 #endif /* SIMGRID_TEST */