Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
[mc] Don't use unprototyped functions
[simgrid.git] / src / mc / mc_page_store.h
1 /* Copyright (c) 2014. 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 <stdint.h>
8
9 #ifdef __cplusplus
10 #include <vector>
11
12 #include <boost/array.hpp>
13 #include <boost/utility.hpp>
14 #include <boost/unordered_map.hpp>
15 #include <boost/unordered_set.hpp>
16 #endif
17
18 #include <xbt.h>
19
20 #include "mc_mmu.h"
21
22 #ifndef MC_PAGE_STORE_H
23 #define MC_PAGE_STORE_H
24
25 struct s_mc_pages_store;
26
27 #ifdef __cplusplus
28
29 /** @brief Storage for snapshot memory pages
30  *
31  * The first (lower) layer of the per-page snapshot mechanism is a page
32  * store: it's responsibility is to store immutable shareable
33  * reference-counted memory pages independently of the snapshoting
34  * logic. Snapshot management and representation, soft-dirty tracking is
35  * handled to an higher layer. READMORE
36  *
37  * Data structure:
38  *
39  *  * A pointer (`memory_`) to a (currently anonymous) `mmap()`ed memory
40  *    region holding the memory pages (the address of the first page).
41  *
42  *    We want to keep this memory region aligned on the memory pages (so
43  *    that we might be able to create non-linear memory mappings on those
44  *    pages in the future) and be able to expand it without coyping the
45  *    data (there will be a lot of pages here): we will be able to
46  *    efficiently expand the memory mapping using `mremap()`, moving it
47  *    to another virtual address if necessary.
48  *
49  *    Because we will move this memory mapping on the virtual address
50  *    space, only the index of the page will be stored in the snapshots
51  *    and the page will always be looked up by going through `memory`:
52  *
53  *         void* page = (char*) page_store->memory + page_index << pagebits;
54  *
55  *  * The number of pages mapped in virtual memory (`capacity_`). Once all
56  *    those pages are used, we need to expand the page store with
57  *    `mremap()`.
58  *
59  *  * A reference count for each memory page `page_counts_`. Each time a
60  *    snapshot references a page, the counter is incremented. If a
61  *    snapshot is freed, the reference count is decremented. When the
62  *    reference count, of a page reaches 0 it is added to a list of available
63  *    pages (`free_pages_`).
64  *
65  *  * A list of free pages `free_pages_` which can be reused. This avoids having
66  *    to scan the reference count list to find a free page.
67  *
68  *  * When we are expanding the memory map we do not want to add thousand of page
69  *    to the `free_pages_` list and remove them just afterwards. The `top_index_`
70  *    field is an index after which all pages are free and are not in the `free_pages_`
71  *    list.
72  *
73  *  * When we are adding a page, we need to check if a page with the same
74  *    content is already in the page store in order to reuse it. For this
75  *    reason, we maintain an index (`hash_index_`) mapping the hash of a
76  *    page to the list of page indices with this hash.
77  *    We use a fast (non cryptographic) hash so there may be conflicts:
78  *    we must be able to store multiple indices for the same hash.
79  *
80  */
81 struct s_mc_pages_store {
82 public: // Types
83 #ifdef MC_PAGE_STORE_MD4
84   typedef boost::array<uint64_t,2> hash_type;
85 #else
86   typedef uint64_t hash_type;
87 #endif
88 private: // Types
89 #ifdef MC_PAGE_STORE_MD4
90   // We are using a secure hash to identify a page.
91   // We assume there will not be any collision: we need to map a hash
92   // to a single page index.
93   typedef boost::unordered_map<hash_type, size_t> pages_map_type;
94 #else
95   // We are using a cheap hash to index a page.
96   // We should expect collision and we need to associate multiple page indices
97   // to the same hash.
98   typedef boost::unordered_set<size_t> page_set_type;
99   typedef boost::unordered_map<hash_type, page_set_type> pages_map_type;
100 #endif
101
102 private: // Fields:
103   /** First page
104    *
105    *  mc_page_store_get_page expects that this is the first field.
106    * */
107   void* memory_;
108   /** Number of available pages in virtual memory */
109   size_t capacity_;
110   /** Top of the used pages (index of the next available page) */
111   size_t top_index_;
112   /** Page reference count */
113   std::vector<uint64_t> page_counts_;
114   /** Index of available pages before the top */
115   std::vector<size_t> free_pages_;
116   /** Index from page hash to page index */
117   pages_map_type hash_index_;
118
119 private: // Methods
120   void resize(size_t size);
121   size_t alloc_page();
122   void remove_page(size_t pageno);
123
124 public: // Constructors
125   explicit s_mc_pages_store(size_t size);
126   ~s_mc_pages_store();
127
128 public: // Methods
129
130   /** @brief Decrement the reference count for a given page
131    *
132    * Decrement the reference count of this page. Used when a snapshot is
133    * destroyed.
134    *
135    * If the reference count reaches zero, the page is recycled:
136    * it is added to the `free_pages_` list and removed from the `hash_index_`.
137    *
138    * */
139   void unref_page(size_t pageno);
140
141   /** @brief Increment the refcount for a given page
142    *
143    * This method used to increase a reference count of a page if we know
144    * that the content of a page is the same as a page already in the page
145    * store.
146    *
147    * This will be the case if a page if soft clean: we know that is has not
148    * changed since the previous cnapshot/restoration and we can avoid
149    * hashing the page, comparing byte-per-byte to candidates.
150    * */
151   void ref_page(size_t pageno);
152
153   /** @brief Store a page in the page store */
154   size_t store_page(void* page);
155
156   /** @brief Get a page from its page number
157    *
158    *  @param Number of the memory page in the store
159    *  @return Start of the page
160    */
161   const void* get_page(size_t pageno) const;
162
163 public: // Debug/test methods
164
165   /** @brief Get the number of references for a page */
166   size_t get_ref(size_t pageno);
167
168   /** @brief Get the number of used pages */
169   size_t size();
170
171   /** @brief Get the capacity of the page store
172    *
173    *  The capacity is expanded by a system call (mremap).
174    * */
175   size_t capacity();
176
177 };
178
179 inline __attribute__((always_inline))
180 void s_mc_pages_store::unref_page(size_t pageno) {
181   if ((--this->page_counts_[pageno]) == 0) {
182     this->remove_page(pageno);
183   }
184 }
185
186 inline __attribute__((always_inline))
187 void s_mc_pages_store::ref_page(size_t pageno) {
188   ++this->page_counts_[pageno];
189 }
190
191 inline __attribute__((always_inline))
192 const void* s_mc_pages_store::get_page(size_t pageno) const {
193   return mc_page_from_number(this->memory_, pageno);
194 }
195
196 inline __attribute__((always_inline))
197 size_t s_mc_pages_store::get_ref(size_t pageno)  {
198   return this->page_counts_[pageno];
199 }
200
201 inline __attribute__((always_inline))
202 size_t s_mc_pages_store::size() {
203   return this->top_index_ - this->free_pages_.size();
204 }
205
206 inline __attribute__((always_inline))
207 size_t s_mc_pages_store::capacity() {
208   return this->capacity_;
209 }
210
211 #endif
212
213 SG_BEGIN_DECL()
214
215 typedef struct s_mc_pages_store s_mc_pages_store_t, * mc_pages_store_t;
216 mc_pages_store_t mc_pages_store_new(void);
217 void mc_pages_store_delete(mc_pages_store_t store);
218
219 /**
220  */
221 static inline __attribute__((always_inline))
222 const void* mc_page_store_get_page(mc_pages_store_t page_store, size_t pageno)
223 {
224   // This is page_store->memory_:
225   void* memory = *(void**)page_store;
226   return mc_page_from_number(memory, pageno);
227 }
228
229 SG_END_DECL()
230
231 #endif