Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
cut some more includes
[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 #ifdef __FreeBSD__
12 # define MAP_POPULATE MAP_PREFAULT_READ
13 #endif
14
15 #include "xbt/base.h"
16 #include "xbt/log.h"
17 #include "xbt/sysdep.h"
18
19 #include "src/internal_config.h"
20
21 #include "src/mc/PageStore.hpp"
22
23 #include "src/mc/mc_mmu.h"
24
25 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_page_snapshot, mc,
26                                 "Logging specific to mc_page_snapshot");
27
28 namespace simgrid {
29 namespace mc {
30
31 /** @brief Compute a hash for the given memory page
32  *
33  *  The page is used before inserting the page in the page store
34  *  in order to find duplicate of this page in the page store.
35  *
36  *  @param data Memory page
37  *  @return hash off the page
38  */
39 static XBT_ALWAYS_INLINE PageStore::hash_type mc_hash_page(const void* data)
40 {
41   const std::uint64_t* values = (const uint64_t*) data;
42   std::size_t n = xbt_pagesize / sizeof(uint64_t);
43
44   // This djb2:
45   std::uint64_t hash = 5381;
46   for (std::size_t i = 0; i != n; ++i)
47     hash = ((hash << 5) + hash) + values[i];
48   return hash;
49 }
50
51 // ***** snapshot_page_manager
52
53 PageStore::PageStore(size_t size) :
54   memory_(nullptr), capacity_(0), top_index_(0)
55 {
56   // Using mmap in order to be able to expand the region
57   // by relocating it somewhere else in the virtual memory
58   // space:
59   void* memory = ::mmap(nullptr, size << xbt_pagebits, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, -1, 0);
60   if (memory == MAP_FAILED)
61     xbt_die("Could not mmap initial snapshot pages.");
62
63   this->top_index_ = 0;
64   this->capacity_ = size;
65   this->memory_ = memory;
66   this->page_counts_.resize(size);
67 }
68
69 PageStore::~PageStore()
70 {
71   ::munmap(this->memory_, this->capacity_ << xbt_pagebits);
72 }
73
74 void PageStore::resize(std::size_t size)
75 {
76   size_t old_bytesize = this->capacity_ << xbt_pagebits;
77   size_t new_bytesize = size << xbt_pagebits;
78   void *new_memory;
79
80   // Expand the memory region by moving it into another
81   // virtual memory address if necessary:
82 #if HAVE_MREMAP
83   new_memory = mremap(this->memory_, old_bytesize, new_bytesize, MREMAP_MAYMOVE);
84   if (new_memory == MAP_FAILED)
85     xbt_die("Could not mremap snapshot pages.");
86 #else
87   if (new_bytesize > old_bytesize) {
88     // Grow: first try to add new space after current map
89     new_memory = mmap((char *)this->memory_ + old_bytesize,
90                       new_bytesize-old_bytesize,
91                       PROT_READ|PROT_WRITE,
92                       MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE,
93                       -1, 0);
94     if (new_memory == MAP_FAILED)
95       xbt_die("Could not mremap snapshot pages.");
96     // Check if expanding worked
97     if (new_memory != (char *)this->memory_ + old_bytesize) {
98       // New memory segment could not be put at the end of this->memory_,
99       // so cancel this one and try to rellocate everything and copy data
100       munmap(new_memory, new_bytesize-old_bytesize);
101       new_memory = mmap(nullptr,
102                         new_bytesize,
103                         PROT_READ|PROT_WRITE,
104                         MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE,
105                         -1, 0);
106       if (new_memory == MAP_FAILED)
107         xbt_die("Could not mremap snapshot pages.");
108       memcpy(new_memory, this->memory_, old_bytesize);
109       munmap(this->memory_, old_bytesize);
110     }
111   }
112   else {
113     // We don't have functions to shrink a mapping, so leave memory as
114     // it is for now
115     new_memory = this->memory_;
116   }
117 #endif
118
119   this->capacity_ = size;
120   this->memory_ = new_memory;
121   this->page_counts_.resize(size, 0);
122 }
123
124 /** Allocate a free page
125  *
126  *  @return index of the free page
127  */
128 std::size_t PageStore::alloc_page()
129 {
130   if (this->free_pages_.empty()) {
131
132     // Expand the region:
133     if (this->top_index_ == this->capacity_)
134       // All the pages are allocated, we need add more pages:
135       this->resize(2 * this->capacity_);
136
137     // Use a page from the top:
138     return this->top_index_++;
139
140   } else {
141
142     // Use a page from free_pages_ (inside of the region):
143     size_t res = this->free_pages_[this->free_pages_.size() - 1];
144     this->free_pages_.pop_back();
145     return res;
146
147   }
148 }
149
150 void PageStore::remove_page(std::size_t pageno)
151 {
152   this->free_pages_.push_back(pageno);
153   const void* page = this->get_page(pageno);
154   hash_type hash = mc_hash_page(page);
155   this->hash_index_[hash].erase(pageno);
156 }
157
158 /** Store a page in memory */
159 std::size_t PageStore::store_page(void* page)
160 {
161   xbt_assert(top_index_ <= this->capacity_, "top_index is not consistent");
162
163   // First, we check if a page with the same content is already in the page
164   // store:
165   //  1. compute the hash of the page;
166   //  2. find pages with the same hash using `hash_index_`;
167   //  3. find a page with the same content.
168   hash_type hash = mc_hash_page(page);
169
170   // Try to find a duplicate in set of pages with the same hash:
171   page_set_type& page_set = this->hash_index_[hash];
172   for (size_t pageno : page_set) {
173     const void* snapshot_page = this->get_page(pageno);
174     if (memcmp(page, snapshot_page, xbt_pagesize) == 0) {
175
176       // If a page with the same content is already in the page store it is
177       // reused and its reference count is incremented.
178       page_counts_[pageno]++;
179       return pageno;
180
181     }
182   }
183
184   // Otherwise, a new page is allocated in the page store and the content
185   // of the page is `memcpy()`-ed to this new page.
186   std::size_t pageno = alloc_page();
187   xbt_assert(this->page_counts_[pageno]==0, "Allocated page is already used");
188   void* snapshot_page = (void*) this->get_page(pageno);
189   memcpy(snapshot_page, page, xbt_pagesize);
190   page_set.insert(pageno);
191   page_counts_[pageno]++;
192   return pageno;
193 }
194
195 }
196 }
197
198 #ifdef SIMGRID_TEST
199
200 #include <cstring>
201 #include <cstdint>
202
203 #include <unistd.h>
204 #include <sys/mman.h>
205
206 #include <memory>
207
208 #include "src/mc/PageStore.hpp"
209
210 static int value = 0;
211
212 static void new_content(void* data, std::size_t size)
213 {
214   ::memset(data, ++value, size);
215 }
216
217 static void* getpage()
218 {
219   return mmap(nullptr, getpagesize(), PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
220 }
221
222 XBT_TEST_SUITE("mc_page_store", "Page store");
223
224 XBT_TEST_UNIT("base", test_mc_page_store, "Test adding/removing pages in the store")
225 {
226   using simgrid::mc::PageStore;
227   
228   xbt_test_add("Init");
229   std::size_t pagesize = (size_t) getpagesize();
230   std::unique_ptr<PageStore> store
231     = std::unique_ptr<PageStore>(new simgrid::mc::PageStore(500));
232   void* data = getpage();
233   xbt_test_assert(store->size()==0, "Bad size");
234
235   xbt_test_add("Store the page once");
236   new_content(data, pagesize);
237   size_t pageno1 = store->store_page(data);
238   xbt_test_assert(store->get_ref(pageno1)==1, "Bad refcount");
239   const void* copy = store->get_page(pageno1);
240   xbt_test_assert(::memcmp(data, copy, pagesize)==0, "Page data should be the same");
241   xbt_test_assert(store->size()==1, "Bad size");
242
243   xbt_test_add("Store the same page again");
244   size_t pageno2 = store->store_page(data);
245   xbt_test_assert(pageno1==pageno2, "Page should be the same");
246   xbt_test_assert(store->get_ref(pageno1)==2, "Bad refcount");
247   xbt_test_assert(store->size()==1, "Bad size");
248
249   xbt_test_add("Store a new page");
250   new_content(data, pagesize);
251   size_t pageno3 = store->store_page(data);
252   xbt_test_assert(pageno1 != pageno3, "New page should be different");
253   xbt_test_assert(store->size()==2, "Bad size");
254
255   xbt_test_add("Unref pages");
256   store->unref_page(pageno1);
257   xbt_assert(store->get_ref(pageno1)==1, "Bad refcount");
258   xbt_assert(store->size()==2, "Bad size");
259   store->unref_page(pageno2);
260   xbt_test_assert(store->size()==1, "Bad size");
261
262   xbt_test_add("Reallocate page");
263   new_content(data, pagesize);
264   size_t pageno4 = store->store_page(data);
265   xbt_test_assert(pageno1 == pageno4, "Page was not reused");
266   xbt_test_assert(store->get_ref(pageno4)==1, "Bad refcount");
267   xbt_test_assert(store->size()==2, "Bad size");
268 }
269
270 #endif /* SIMGRID_TEST */