Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
mc: move some files related to ELF, DWARF or unwind reading into their own directory
[simgrid.git] / src / mc / sosp / PageStore.cpp
1 /* Copyright (c) 2015-2019. The SimGrid Team. All rights reserved.          */
2
3 /* This program is free software; you can redistribute it and/or modify it
4  * under the terms of the license (GNU LGPL) which comes with this package. */
5
6 #include <cstring> // memcpy, memcmp
7 #include <unistd.h>
8
9 #include <sys/mman.h>
10 #ifdef __FreeBSD__
11 #define MAP_POPULATE MAP_PREFAULT_READ
12 #endif
13
14 #include "xbt/base.h"
15 #include "xbt/log.h"
16 #include "xbt/sysdep.h"
17
18 #include "src/internal_config.h"
19
20 #include "src/mc/sosp/PageStore.hpp"
21
22 #include "src/mc/mc_mmu.hpp"
23
24 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_page_snapshot, mc, "Logging specific to mc_page_snapshot");
25
26 namespace simgrid {
27 namespace mc {
28
29 /** @brief Compute a hash for the given memory page
30  *
31  *  The page is used before inserting the page in the page store
32  *  in order to find duplicate of this page in the page store.
33  *
34  *  @param data Memory page
35  *  @return hash off the page
36  */
37 static XBT_ALWAYS_INLINE PageStore::hash_type mc_hash_page(const void* data)
38 {
39   const std::uint64_t* values = (const uint64_t*)data;
40   std::size_t n               = xbt_pagesize / sizeof(uint64_t);
41
42   // This djb2:
43   std::uint64_t hash = 5381;
44   for (std::size_t i = 0; i != n; ++i)
45     hash = ((hash << 5) + hash) + values[i];
46   return hash;
47 }
48
49 // ***** snapshot_page_manager
50
51 PageStore::PageStore(std::size_t size) : memory_(nullptr), capacity_(size), top_index_(0)
52 {
53   // Using mmap in order to be able to expand the region by relocating it somewhere else in the virtual memory space:
54   void* memory =
55       ::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->memory_    = memory;
61   this->page_counts_.resize(size);
62 }
63
64 PageStore::~PageStore()
65 {
66   ::munmap(this->memory_, this->capacity_ << xbt_pagebits);
67 }
68
69 void PageStore::resize(std::size_t size)
70 {
71   size_t old_bytesize = this->capacity_ << xbt_pagebits;
72   size_t new_bytesize = size << xbt_pagebits;
73   void* new_memory;
74
75   // Expand the memory region by moving it into another
76   // virtual memory address if necessary:
77 #if HAVE_MREMAP
78   new_memory = mremap(this->memory_, old_bytesize, new_bytesize, MREMAP_MAYMOVE);
79   if (new_memory == MAP_FAILED)
80     xbt_die("Could not mremap snapshot pages.");
81 #else
82   if (new_bytesize > old_bytesize) {
83     // Grow: first try to add new space after current map
84     new_memory = mmap((char*)this->memory_ + old_bytesize, new_bytesize - old_bytesize, PROT_READ | PROT_WRITE,
85                       MAP_PRIVATE | MAP_ANONYMOUS | MAP_POPULATE, -1, 0);
86     if (new_memory == MAP_FAILED)
87       xbt_die("Could not mremap snapshot pages.");
88     // Check if expanding worked
89     if (new_memory != (char*)this->memory_ + old_bytesize) {
90       // New memory segment could not be put at the end of this->memory_,
91       // so cancel this one and try to rellocate everything and copy data
92       munmap(new_memory, new_bytesize - old_bytesize);
93       new_memory =
94           mmap(nullptr, new_bytesize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_POPULATE, -1, 0);
95       if (new_memory == MAP_FAILED)
96         xbt_die("Could not mremap snapshot pages.");
97       memcpy(new_memory, this->memory_, old_bytesize);
98       munmap(this->memory_, old_bytesize);
99     }
100   } else {
101     // We don't have functions to shrink a mapping, so leave memory as
102     // it is for now
103     new_memory = this->memory_;
104   }
105 #endif
106
107   this->capacity_ = size;
108   this->memory_   = new_memory;
109   this->page_counts_.resize(size, 0);
110 }
111
112 /** Allocate a free page
113  *
114  *  @return index of the free page
115  */
116 std::size_t PageStore::alloc_page()
117 {
118   if (this->free_pages_.empty()) {
119
120     // Expand the region:
121     if (this->top_index_ == this->capacity_)
122       // All the pages are allocated, we need add more pages:
123       this->resize(2 * this->capacity_);
124
125     // Use a page from the top:
126     return this->top_index_++;
127
128   } else {
129
130     // Use a page from free_pages_ (inside of the region):
131     size_t res = this->free_pages_[this->free_pages_.size() - 1];
132     this->free_pages_.pop_back();
133     return res;
134   }
135 }
136
137 void PageStore::remove_page(std::size_t pageno)
138 {
139   this->free_pages_.push_back(pageno);
140   const void* page = this->get_page(pageno);
141   hash_type hash   = mc_hash_page(page);
142   this->hash_index_[hash].erase(pageno);
143 }
144
145 /** Store a page in memory */
146 std::size_t PageStore::store_page(void* page)
147 {
148   xbt_assert(top_index_ <= this->capacity_, "top_index is not consistent");
149
150   // First, we check if a page with the same content is already in the page store:
151   //  1. compute the hash of the page
152   //  2. find pages with the same hash using `hash_index_`
153   //  3. find a page with the same content
154   hash_type hash = mc_hash_page(page);
155
156   // Try to find a duplicate in set of pages with the same hash:
157   page_set_type& page_set = this->hash_index_[hash];
158   for (size_t const& pageno : page_set) {
159     const void* snapshot_page = this->get_page(pageno);
160     if (memcmp(page, snapshot_page, xbt_pagesize) == 0) {
161
162       // If a page with the same content is already in the page store it's reused and its refcount is incremented.
163       page_counts_[pageno]++;
164       return pageno;
165     }
166   }
167
168   // Otherwise, a new page is allocated in the page store and the content of the page is `memcpy()`-ed to this new page.
169   std::size_t pageno = alloc_page();
170   xbt_assert(this->page_counts_[pageno] == 0, "Allocated page is already used");
171   void* snapshot_page = (void*)this->get_page(pageno);
172   memcpy(snapshot_page, page, xbt_pagesize);
173   page_set.insert(pageno);
174   page_counts_[pageno]++;
175   return pageno;
176 }
177
178 } // namespace mc
179 } // namespace simgrid