Logo AND Algorithmique Numérique Distribuée

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