From 27a8e7140628e183c77a13561e88fb32848d892a Mon Sep 17 00:00:00 2001 From: Gabriel Corona Date: Fri, 13 Jun 2014 11:17:52 +0200 Subject: [PATCH] [mc] Update doc for page_store --- src/mc/mc_page_store.cpp | 14 +++++-- src/mc/mc_page_store.h | 81 ++++++++++++++++++++++++++++++++++------ 2 files changed, 81 insertions(+), 14 deletions(-) diff --git a/src/mc/mc_page_store.cpp b/src/mc/mc_page_store.cpp index b91af866ed..ba917a125f 100644 --- a/src/mc/mc_page_store.cpp +++ b/src/mc/mc_page_store.cpp @@ -128,19 +128,27 @@ size_t s_mc_pages_store::store_page(void* page) xbt_assert(mc_page_offset(page)==0, "Not at the beginning of a page"); xbt_assert(top_index_ <= this->capacity_, "top_index is not consistent"); - // Search the page in the snapshot pages: + // First, we check if a page with the same content is already in the page + // store: + // 1. compute the hash of the page; + // 2. find pages with the same hash using `hash_index_`; + // 3. find a page with the same content. uint64_t hash = mc_hash_page(page); page_set_type& page_set = this->hash_index_[hash]; BOOST_FOREACH (size_t pageno, page_set) { const void* snapshot_page = this->get_page(pageno); if (memcmp(page, snapshot_page, xbt_pagesize) == 0) { - // Page found, reuse it: + + // If a page with the same content is already in the page store it is + // reused and its reference count is incremented. page_counts_[pageno]++; return pageno; + } } - // Allocate a new page for this page: + // Otherwise, a new page is allocated in the page store and the content + // of the page is `memcpy()`-ed to this new page. size_t pageno = alloc_page(); void* snapshot_page = (void*) this->get_page(pageno); memcpy(snapshot_page, page, xbt_pagesize); diff --git a/src/mc/mc_page_store.h b/src/mc/mc_page_store.h index db52b1851c..092ad23347 100644 --- a/src/mc/mc_page_store.h +++ b/src/mc/mc_page_store.h @@ -20,11 +20,57 @@ #ifndef MC_PAGE_SNAPSHOT_H #define MC_PAGE_SNAPSHOT_H -/** @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 @@ -57,23 +103,36 @@ public: // Constructors public: // Methods - /** @brief Decrement the refcount for a given page */ + /** @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) { if ((--this->page_counts_[pageno]) == 0) { this->remove_page(pageno); } } - /** @brief Increment the refcount for a given page */ + /** @brief Increment the refcount for a given page + * + * 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) { ++this->page_counts_[pageno]; } - /** @brief Store a page - * - * Either allocate a new page in the store or reuse - * a shared page if is is already in the page store. - */ + /** @brief Store a page in the page store */ size_t store_page(void* page); /** @brief Get a page from its page number -- 2.20.1