From 4b70e13e14a9fa13696fbcf2d8a9bb329db90c57 Mon Sep 17 00:00:00 2001 From: David Young Date: Wed, 26 Feb 2020 16:24:42 -0600 Subject: Where n is the number of page-table/shadow-index entries, avoid spending O(n^2) time in H5PB_dest(). While we're in H5PB_dest(), mark deleted shadow-index entries as "garbage" and skip the O(n) shadow index-entries copy. Rename shadow index-entry member `moved_to_hdf5_file` to `moved_to_lower_file` while I'm in here---NFCI. --- src/H5FDprivate.h | 9 +++++---- src/H5FDvfd_swmr.c | 3 ++- src/H5Fvfd_swmr.c | 2 +- src/H5PB.c | 59 ++++++++++++++++++++++++++++++++++++++---------------- 4 files changed, 50 insertions(+), 23 deletions(-) diff --git a/src/H5FDprivate.h b/src/H5FDprivate.h index d35ce3d..df49682 100644 --- a/src/H5FDprivate.h +++ b/src/H5FDprivate.h @@ -169,7 +169,8 @@ typedef struct H5FD_vfd_swmr_idx_entry_t { hbool_t clean; uint64_t tick_of_last_flush; uint64_t delayed_flush; - hbool_t moved_to_hdf5_file; + bool moved_to_lower_file; + bool garbage; } H5FD_vfd_swmr_idx_entry_t; /* @@ -204,7 +205,7 @@ typedef struct H5FD_vfd_swmr_md_header { static inline H5FD_vfd_swmr_idx_entry_t * vfd_swmr_pageno_to_mdf_idx_entry(H5FD_vfd_swmr_idx_entry_t *idx, - uint32_t nindices, uint64_t target_page) + uint32_t nindices, uint64_t target_page, bool reuse_garbage) { uint32_t top; uint32_t bottom; @@ -223,8 +224,8 @@ vfd_swmr_pageno_to_mdf_idx_entry(H5FD_vfd_swmr_idx_entry_t *idx, bottom = probe + 1; else if (idx[probe].hdf5_page_offset > target_page) top = probe; - else - return &idx[probe]; /* found it */ + else /* found it */ + return (reuse_garbage || !idx[probe].garbage) ? &idx[probe] : NULL; } while (bottom < top); /* Previous interval was [top - 1, top] or [bottom, bottom + 1]. * The new interval is [top, top] or [bottom, bottom], respectively. diff --git a/src/H5FDvfd_swmr.c b/src/H5FDvfd_swmr.c index 8ed760b..008db8e 100644 --- a/src/H5FDvfd_swmr.c +++ b/src/H5FDvfd_swmr.c @@ -690,7 +690,8 @@ H5FD_vfd_swmr_read(H5FD_t *_file, H5FD_mem_t type, HDfprintf(stderr, "vfd swmr read index num_entries = %d\n", num_entries); #endif /* JRM */ - entry = vfd_swmr_pageno_to_mdf_idx_entry(index, num_entries, target_page); + entry = vfd_swmr_pageno_to_mdf_idx_entry(index, num_entries, target_page, + false); #if 0 /* JRM */ if (entry != NULL) { diff --git a/src/H5Fvfd_swmr.c b/src/H5Fvfd_swmr.c index c4635a0..2dc11e8 100644 --- a/src/H5Fvfd_swmr.c +++ b/src/H5Fvfd_swmr.c @@ -662,7 +662,7 @@ H5F_vfd_swmr_writer__delay_write(H5F_shared_t *shared, uint64_t page, ie_ptr = NULL; } else { ie_ptr = vfd_swmr_pageno_to_mdf_idx_entry(idx, - shared->mdf_idx_entries_used, page); + shared->mdf_idx_entries_used, page, false); } if (ie_ptr == NULL) diff --git a/src/H5PB.c b/src/H5PB.c index 8ad1b24..99c8a3b 100644 --- a/src/H5PB.c +++ b/src/H5PB.c @@ -74,7 +74,7 @@ static herr_t H5PB__create_new_page(H5PB_t *pb_ptr, haddr_t addr, size_t size, static void H5PB__deallocate_page(H5PB_entry_t *entry_ptr); -static herr_t H5PB__evict_entry(H5F_shared_t *, H5PB_entry_t *, hbool_t); +static herr_t H5PB__evict_entry(H5F_shared_t *, H5PB_entry_t *, bool, bool); static herr_t H5PB__flush_entry(H5F_shared_t *, H5PB_t *, H5PB_entry_t *); @@ -710,7 +710,7 @@ H5PB_dest(H5F_shared_t *shared) "Can't flush entry") } - if ( H5PB__evict_entry(shared, evict_ptr, TRUE) < 0 ) + if ( H5PB__evict_entry(shared, evict_ptr, TRUE, true) < 0 ) HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, \ "forced eviction failed") @@ -1121,14 +1121,25 @@ done: } /* end H5PB_read() */ +/* Remove the entry corresponding to lower-file page number `page`. + * Return 0 if there was no such entry or if the entry was removed + * successfully. Return -1 on error. + * + * If `only_mark` is true, then the entry corresponding shadow-index + * entry is not removed. Instead, it is marked as garbage. This is + * a stop-gap fix for a performance problem in H5PB_dest(): deleting + * all of the index entries took time quadratic in their number because + * this routine performs an O(n) copy of index entries. + */ static int -vfd_swmr_mdf_idx_entry_remove(H5F_shared_t *shared, uint64_t page) +vfd_swmr_mdf_idx_entry_remove(H5F_shared_t *shared, uint64_t page, + bool only_mark) { ptrdiff_t i; H5FD_vfd_swmr_idx_entry_t *entry; entry = vfd_swmr_pageno_to_mdf_idx_entry(shared->mdf_idx, - shared->mdf_idx_entries_used, page); + shared->mdf_idx_entries_used, page, false); if (entry == NULL) return 0; @@ -1137,6 +1148,11 @@ vfd_swmr_mdf_idx_entry_remove(H5F_shared_t *shared, uint64_t page) shadow_image_defer_free(shared, entry) != 0) return -1; + if (only_mark) { + entry->garbage = true; + return 0; + } + i = entry - shared->mdf_idx; if (shared->mdf_idx_entries_used > i + 1) { @@ -1252,11 +1268,11 @@ H5PB_remove_entry(H5F_shared_t *shared, haddr_t addr) HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, \ "mark entry clean failed") - if ( H5PB__evict_entry(shared, entry_ptr, TRUE) < 0 ) + if ( H5PB__evict_entry(shared, entry_ptr, TRUE, false) < 0 ) HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, "forced eviction failed") - assert(vfd_swmr_pageno_to_mdf_idx_entry(shared->mdf_idx, shared->mdf_idx_entries_used, page) == NULL); + assert(vfd_swmr_pageno_to_mdf_idx_entry(shared->mdf_idx, shared->mdf_idx_entries_used, page, false) == NULL); } done: @@ -1422,7 +1438,7 @@ H5PB_vfd_swmr__release_delayed_writes(H5F_shared_t *shared) HGOTO_ERROR(H5E_PAGEBUF, H5E_WRITEERROR, FAIL, \ "flush of mpmde failed") - if ( H5PB__evict_entry(shared, entry_ptr, TRUE) < 0 ) + if ( H5PB__evict_entry(shared, entry_ptr, TRUE, false) < 0 ) HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, \ "eviction of mpmde failed") @@ -1501,7 +1517,7 @@ H5PB_vfd_swmr__release_tick_list(H5F_shared_t *shared) HGOTO_ERROR(H5E_PAGEBUF, H5E_WRITEERROR, FAIL, \ "flush of mpmde failed") - if ( H5PB__evict_entry(shared, entry_ptr, TRUE) < 0 ) + if ( H5PB__evict_entry(shared, entry_ptr, TRUE, false) < 0 ) HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, \ "eviction of mpmde failed") @@ -1718,7 +1734,7 @@ H5PB_vfd_swmr__update_index(H5F_t *f, /* see if the shadow index already contains an entry for *entry. */ ie_ptr = vfd_swmr_pageno_to_mdf_idx_entry(idx, - shared->mdf_idx_entries_used, target_page); + shared->mdf_idx_entries_used, target_page, true); if ( ie_ptr == NULL ) { /* alloc new entry in the metadata file index*/ uint32_t new_index_entry_index; @@ -1747,7 +1763,8 @@ H5PB_vfd_swmr__update_index(H5F_t *f, /* ie_ptr->clean initialized below */ /* ie_ptr->tick_of_last_flush initialized below */ ie_ptr->delayed_flush = entry->delay_write_until; - ie_ptr->moved_to_hdf5_file = FALSE; + ie_ptr->moved_to_lower_file = false; + ie_ptr->garbage = false; } else { @@ -2281,7 +2298,13 @@ H5PB__deallocate_page(H5PB_entry_t *entry_ptr) * must be respected. Attempts to evict an entry that * that do not respect these constraints will generate * and error unless the force parameter is TRUE, in which - * case, these constraints are igmored. + * case, these constraints are ignored. + * + * If `only_mark` is true, then the page-table entry's + * corresponding shadow-index entry is not removed. Instead, + * it is marked as garbage. This is a stop-gap fix for a + * performance problem in H5PB_dest(): deleting all of the + * index entries took time quadratic in their number. * * In the context of VFD SWMR, there is also the requirement * that entries to be evicted not be on the tick list, and @@ -2299,7 +2322,8 @@ H5PB__deallocate_page(H5PB_entry_t *entry_ptr) *------------------------------------------------------------------------- */ static herr_t -H5PB__evict_entry(H5F_shared_t *shared, H5PB_entry_t *entry_ptr, hbool_t force) +H5PB__evict_entry(H5F_shared_t *shared, H5PB_entry_t *entry_ptr, bool force, + bool only_mark) { H5PB_t *pb_ptr = shared->pb_ptr; herr_t ret_value = SUCCEED; /* Return value */ @@ -2383,7 +2407,8 @@ H5PB__evict_entry(H5F_shared_t *shared, H5PB_entry_t *entry_ptr, hbool_t force) * the image will be bigger. So the shadow file will never see the * entire image written, just the first page of the image. */ - if (vfd_swmr_mdf_idx_entry_remove(shared, entry_ptr->page) == -1) { + if (vfd_swmr_mdf_idx_entry_remove(shared, entry_ptr->page, + only_mark) == -1) { HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, "failed to remove shadow index entry") } @@ -2425,7 +2450,7 @@ done: *------------------------------------------------------------------------- */ static herr_t -H5PB__flush_entry(H5F_shared_t *shared, H5PB_t *pb_ptr, H5PB_entry_t *entry_ptr) +H5PB__flush_entry(H5F_shared_t *shared, H5PB_t *pb_ptr, H5PB_entry_t *const entry_ptr) { haddr_t eoa; /* Current EOA for the file */ herr_t ret_value = SUCCEED; /* Return value */ @@ -2797,7 +2822,7 @@ H5PB__make_space(H5F_shared_t *shared, H5PB_t *pb_ptr, H5FD_mem_t inserted_type) evict_ptr = search_ptr; search_ptr = search_ptr->prev; - if ( H5PB__evict_entry(shared, evict_ptr, FALSE) < 0 ) + if ( H5PB__evict_entry(shared, evict_ptr, FALSE, false) < 0 ) HGOTO_ERROR(H5E_PAGEBUF, H5E_WRITEERROR, FAIL, \ "Can't evict entry") @@ -3247,7 +3272,7 @@ H5PB__read_meta(H5F_shared_t *shared, H5FD_mem_t type, haddr_t addr, size_t size HDassert( ! ( entry_ptr->is_dirty ) ); - if ( H5PB__evict_entry(shared, entry_ptr, TRUE) < 0 ) + if (H5PB__evict_entry(shared, entry_ptr, TRUE, false) < 0) HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, \ "forced eviction failed (1)") @@ -4046,7 +4071,7 @@ H5PB__write_raw(H5F_shared_t *shared, H5FD_mem_t type, haddr_t addr, size_t size HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, \ "mark entry clean failed") - if ( H5PB__evict_entry(shared, entry_ptr, TRUE) < 0 ) + if (H5PB__evict_entry(shared, entry_ptr, TRUE, false) < 0) HGOTO_ERROR(H5E_PAGEBUF, H5E_SYSTEM, FAIL, \ "forced eviction failed (1)") -- cgit v0.12