X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/0700b488178346d3cccc454f641a7155c6ff6026..b487d5a9259b88670b8cd97e9c16e4b000c11008:/src/mc/mc_page_store.h diff --git a/src/mc/mc_page_store.h b/src/mc/mc_page_store.h index db52b1851c..9b7841876e 100644 --- a/src/mc/mc_page_store.h +++ b/src/mc/mc_page_store.h @@ -6,34 +6,104 @@ #include +#ifdef __cplusplus #include +#include #include #include #include +#endif #include -#include "mc_private.h" #include "mc_mmu.h" -#ifndef MC_PAGE_SNAPSHOT_H -#define MC_PAGE_SNAPSHOT_H +#ifndef MC_PAGE_STORE_H +#define MC_PAGE_STORE_H + +struct s_mc_pages_store; + +#ifdef __cplusplus -/** @brief Manager for snapshot pages +/** @brief Storage for snapshot memory pages + * + * The first (lower) layer of the per-page snapshot mechanism is a page + * store: it's responsibility is to store immutable shareable + * reference-counted memory pages independently of the snapshoting + * logic. Snapshot management and representation, soft-dirty tracking is + * handled to an higher layer. READMORE + * + * Data structure: + * + * * A pointer (`memory_`) to a (currently anonymous) `mmap()`ed memory + * region holding the memory pages (the address of the first page). + * + * We want to keep this memory region aligned on the memory pages (so + * that we might be able to create non-linear memory mappings on those + * pages in the future) and be able to expand it without coyping the + * data (there will be a lot of pages here): we will be able to + * efficiently expand the memory mapping using `mremap()`, moving it + * to another virtual address if necessary. + * + * Because we will move this memory mapping on the virtual address + * space, only the index of the page will be stored in the snapshots + * and the page will always be looked up by going through `memory`: + * + * void* page = (char*) page_store->memory + page_index << pagebits; + * + * * The number of pages mapped in virtual memory (`capacity_`). Once all + * those pages are used, we need to expand the page store with + * `mremap()`. + * + * * A reference count for each memory page `page_counts_`. Each time a + * snapshot references a page, the counter is incremented. If a + * snapshot is freed, the reference count is decremented. When the + * reference count, of a page reaches 0 it is added to a list of available + * pages (`free_pages_`). + * + * * A list of free pages `free_pages_` which can be reused. This avoids having + * to scan the reference count list to find a free page. + * + * * When we are expanding the memory map we do not want to add thousand of page + * to the `free_pages_` list and remove them just afterwards. The `top_index_` + * field is an index after which all pages are free and are not in the `free_pages_` + * list. + * + * * When we are adding a page, we need to check if a page with the same + * content is already in the page store in order to reuse it. For this + * reason, we maintain an index (`hash_index_`) mapping the hash of a + * page to the list of page indices with this hash. + * We use a fast (non cryptographic) hash so there may be conflicts: + * we must be able to store multiple indices for the same hash. * - * Page management: the free pages are stored as a simple linked-list. - * The number of the first page if stored in `free_pages`. - * Each free page store the number of the next free page. */ struct s_mc_pages_store { -private: // Types +public: // Types +#ifdef MC_PAGE_STORE_MD4 + typedef boost::array hash_type; +#else typedef uint64_t hash_type; - typedef boost ::unordered_set page_set_type; +#endif +private: // Types +#ifdef MC_PAGE_STORE_MD4 + // We are using a secure hash to identify a page. + // We assume there will not be any collision: we need to map a hash + // to a single page index. + typedef boost::unordered_map pages_map_type; +#else + // We are using a cheap hash to index a page. + // We should expect collision and we need to associate multiple page indices + // to the same hash. + typedef boost::unordered_set page_set_type; typedef boost::unordered_map pages_map_type; +#endif private: // Fields: - /** First page */ + /** First page + * + * mc_page_store_get_page expects that this is the first field. + * */ void* memory_; /** Number of available pages in virtual memory */ size_t capacity_; @@ -57,23 +127,30 @@ public: // Constructors public: // Methods - /** @brief Decrement the refcount for a given page */ - void unref_page(size_t pageno) { - if ((--this->page_counts_[pageno]) == 0) { - this->remove_page(pageno); - } - } - - /** @brief Increment the refcount for a given page */ - void ref_page(size_t pageno) { - ++this->page_counts_[pageno]; - } + /** @brief Decrement the reference count for a given page + * + * Decrement the reference count of this page. Used when a snapshot is + * destroyed. + * + * If the reference count reaches zero, the page is recycled: + * it is added to the `free_pages_` list and removed from the `hash_index_`. + * + * */ + void unref_page(size_t pageno); - /** @brief Store a page + /** @brief Increment the refcount for a given page * - * Either allocate a new page in the store or reuse - * a shared page if is is already in the page store. - */ + * This method used to increase a reference count of a page if we know + * that the content of a page is the same as a page already in the page + * store. + * + * This will be the case if a page if soft clean: we know that is has not + * changed since the previous cnapshot/restoration and we can avoid + * hashing the page, comparing byte-per-byte to candidates. + * */ + void ref_page(size_t pageno); + + /** @brief Store a page in the page store */ size_t store_page(void* page); /** @brief Get a page from its page number @@ -81,31 +158,74 @@ public: // Methods * @param Number of the memory page in the store * @return Start of the page */ - const void* get_page(size_t pageno) const { - return mc_page_from_number(this->memory_, pageno); - } + const void* get_page(size_t pageno) const; public: // Debug/test methods /** @brief Get the number of references for a page */ - size_t get_ref(size_t pageno) { - return this->page_counts_[pageno]; - } + size_t get_ref(size_t pageno); /** @brief Get the number of used pages */ - size_t size() { - return this->top_index_ - this->free_pages_.size(); - } + size_t size(); /** @brief Get the capacity of the page store * * The capacity is expanded by a system call (mremap). * */ - size_t capacity() { - return this->capacity_; - } + size_t capacity(); }; +inline __attribute__((always_inline)) +void s_mc_pages_store::unref_page(size_t pageno) { + if ((--this->page_counts_[pageno]) == 0) { + this->remove_page(pageno); + } +} + +inline __attribute__((always_inline)) +void s_mc_pages_store::ref_page(size_t pageno) { + ++this->page_counts_[pageno]; +} + +inline __attribute__((always_inline)) +const void* s_mc_pages_store::get_page(size_t pageno) const { + return mc_page_from_number(this->memory_, pageno); +} + +inline __attribute__((always_inline)) +size_t s_mc_pages_store::get_ref(size_t pageno) { + return this->page_counts_[pageno]; +} + +inline __attribute__((always_inline)) +size_t s_mc_pages_store::size() { + return this->top_index_ - this->free_pages_.size(); +} + +inline __attribute__((always_inline)) +size_t s_mc_pages_store::capacity() { + return this->capacity_; +} + #endif +SG_BEGIN_DECL() + +typedef struct s_mc_pages_store s_mc_pages_store_t, * mc_pages_store_t; +mc_pages_store_t mc_pages_store_new(); +void mc_pages_store_delete(mc_pages_store_t store); + +/** + */ +static inline __attribute__((always_inline)) +const void* mc_page_store_get_page(mc_pages_store_t page_store, size_t pageno) +{ + // This is page_store->memory_: + void* memory = *(void**)page_store; + return mc_page_from_number(memory, pageno); +} + +SG_END_DECL() + +#endif