From df1ce61f1b4884681c00b342a8651e4d48a91881 Mon Sep 17 00:00:00 2001 From: Dana Robinson <43805+derobins@users.noreply.github.com> Date: Mon, 25 Jul 2022 09:51:09 -0700 Subject: Switches the tagged metadata list from a skip list to a hash table (#1925) --- src/H5C.c | 90 ++++++++++++++++++--------------------------------------- src/H5Cpkg.h | 35 ++++++++++++---------- src/H5Ctag.c | 85 ++++++++++++++++++++++++++--------------------------- src/H5Ipkg.h | 9 ------ src/H5private.h | 9 ++++++ 5 files changed, 98 insertions(+), 130 deletions(-) diff --git a/src/H5C.c b/src/H5C.c index 51fa334..b0115c8 100644 --- a/src/H5C.c +++ b/src/H5C.c @@ -294,8 +294,7 @@ H5C_create(size_t max_cache_size, size_t min_clean_size, int max_type_id, if (NULL == (cache_ptr->slist_ptr = H5SL_create(H5SL_TYPE_HADDR, NULL))) HGOTO_ERROR(H5E_CACHE, H5E_CANTCREATE, NULL, "can't create skip list") - if (NULL == (cache_ptr->tag_list = H5SL_create(H5SL_TYPE_HADDR, NULL))) - HGOTO_ERROR(H5E_CACHE, H5E_CANTCREATE, NULL, "can't create skip list for tagged entry addresses") + cache_ptr->tag_list = NULL; /* If we get this far, we should succeed. Go ahead and initialize all * the fields. @@ -513,16 +512,16 @@ done: if (cache_ptr->slist_ptr != NULL) H5SL_close(cache_ptr->slist_ptr); - if (cache_ptr->tag_list != NULL) - H5SL_close(cache_ptr->tag_list); + HASH_CLEAR(hh, cache_ptr->tag_list); + cache_ptr->tag_list = NULL; if (cache_ptr->log_info != NULL) H5MM_xfree(cache_ptr->log_info); cache_ptr->magic = 0; cache_ptr = H5FL_FREE(H5C_t, cache_ptr); - } /* end if */ - } /* end if */ + } + } FUNC_LEAVE_NOAPI(ret_value) } /* H5C_create() */ @@ -662,33 +661,6 @@ H5C_def_auto_resize_rpt_fcn(H5C_t *cache_ptr, } /* H5C_def_auto_resize_rpt_fcn() */ /*------------------------------------------------------------------------- - * Function: H5C__free_tag_list_cb - * - * Purpose: Callback function to free tag nodes from the skip list. - * - * Return: Non-negative on success/Negative on failure - * - * Programmer: Vailin Choi - * January 2014 - * - *------------------------------------------------------------------------- - */ -static herr_t -H5C__free_tag_list_cb(void *_item, void H5_ATTR_UNUSED *key, void H5_ATTR_UNUSED *op_data) -{ - H5C_tag_info_t *tag_info = (H5C_tag_info_t *)_item; - - FUNC_ENTER_PACKAGE_NOERR - - HDassert(tag_info); - - /* Release the item */ - tag_info = H5FL_FREE(H5C_tag_info_t, tag_info); - - FUNC_LEAVE_NOAPI(0) -} /* H5C__free_tag_list_cb() */ - -/*------------------------------------------------------------------------- * * Function: H5C_prep_for_file_close * @@ -851,28 +823,24 @@ H5C_dest(H5F_t *f) * point? If no, shouldn't this if statement be an assert? */ if (cache_ptr->slist_ptr != NULL) { - HDassert(cache_ptr->slist_len == 0); HDassert(cache_ptr->slist_size == 0); H5SL_close(cache_ptr->slist_ptr); cache_ptr->slist_ptr = NULL; + } - } /* end if */ - - if (cache_ptr->tag_list != NULL) { - - H5SL_destroy(cache_ptr->tag_list, H5C__free_tag_list_cb, NULL); - - cache_ptr->tag_list = NULL; - - } /* end if */ - - if (cache_ptr->log_info != NULL) { + H5C_tag_info_t *item = NULL; + H5C_tag_info_t *tmp = NULL; + HASH_ITER(hh, cache_ptr->tag_list, item, tmp) + { + HASH_DELETE(hh, cache_ptr->tag_list, item); + item = H5FL_FREE(H5C_tag_info_t, item); + } + if (cache_ptr->log_info != NULL) H5MM_xfree(cache_ptr->log_info); - } #ifndef NDEBUG #if H5C_DO_SANITY_CHECKS @@ -8104,7 +8072,7 @@ done: herr_t H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked) { - H5C_tag_info_t *tag_info; /* Points to a tag info struct */ + H5C_tag_info_t *tag_info = NULL; herr_t ret_value = SUCCEED; FUNC_ENTER_NOAPI_NOINIT @@ -8115,7 +8083,7 @@ H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked) HDassert(action == H5C__SET_CORK || action == H5C__UNCORK || action == H5C__GET_CORKED); /* Search the list of corked object addresses in the cache */ - tag_info = (H5C_tag_info_t *)H5SL_search(cache_ptr->tag_list, &obj_addr); + HASH_FIND(hh, cache_ptr->tag_list, &obj_addr, sizeof(haddr_t), tag_info); if (H5C__GET_CORKED == action) { HDassert(corked); @@ -8123,7 +8091,7 @@ H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked) *corked = TRUE; else *corked = FALSE; - } /* end if */ + } else { /* Sanity check */ HDassert(H5C__SET_CORK == action || H5C__UNCORK == action); @@ -8139,25 +8107,24 @@ H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked) /* Set the tag for all entries */ tag_info->tag = obj_addr; - /* Insert tag info into skip list */ - if (H5SL_insert(cache_ptr->tag_list, tag_info, &(tag_info->tag)) < 0) - HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, "can't insert tag info in skip list") - } /* end if */ + /* Insert tag info into hash table */ + HASH_ADD(hh, cache_ptr->tag_list, tag, sizeof(haddr_t), tag_info); + } else { /* Check for object already corked */ if (tag_info->corked) HGOTO_ERROR(H5E_CACHE, H5E_CANTCORK, FAIL, "object already corked") HDassert(tag_info->entry_cnt > 0 && tag_info->head); - } /* end else */ + } /* Set the corked status for the entire object */ tag_info->corked = TRUE; cache_ptr->num_objs_corked++; - - } /* end if */ + } else { /* Sanity check */ - HDassert(tag_info); + if (NULL == tag_info) + HGOTO_ERROR(H5E_CACHE, H5E_CANTUNCORK, FAIL, "tag info pointer is NULL") /* Check for already uncorked */ if (!tag_info->corked) @@ -8172,16 +8139,15 @@ H5C_cork(H5C_t *cache_ptr, haddr_t obj_addr, unsigned action, hbool_t *corked) /* Sanity check */ HDassert(NULL == tag_info->head); - if (H5SL_remove(cache_ptr->tag_list, &(tag_info->tag)) != tag_info) - HGOTO_ERROR(H5E_CACHE, H5E_CANTREMOVE, FAIL, "can't remove tag info from list") + HASH_DELETE(hh, cache_ptr->tag_list, tag_info); /* Release the tag info */ tag_info = H5FL_FREE(H5C_tag_info_t, tag_info); - } /* end if */ + } else HDassert(NULL != tag_info->head); - } /* end else */ - } /* end else */ + } + } done: FUNC_LEAVE_NOAPI(ret_value) diff --git a/src/H5Cpkg.h b/src/H5Cpkg.h index 61c3afc..5caa051 100644 --- a/src/H5Cpkg.h +++ b/src/H5Cpkg.h @@ -3566,15 +3566,17 @@ if ( ( (entry_ptr) == NULL ) || \ * * The fields of this structure are discussed individually below: * - * tag: Address (i.e. "tag") of the object header for all the entries + * tag: Address (i.e. "tag") of the object header for all the entries * corresponding to parts of that object. * - * head: Head of doubly-linked list of all entries belonging to the tag. + * head: Head of doubly-linked list of all entries belonging to the tag. * - * entry_cnt: Number of entries on linked list of entries for this tag. + * entry_cnt: Number of entries on linked list of entries for this tag. * - * corked: Boolean flag indicating whether entries for this object can be - * evicted. + * corked: Boolean flag indicating whether entries for this object can be + * evicted. + * + * hh: uthash hash table handle (must be last) * ****************************************************************************/ typedef struct H5C_tag_info_t { @@ -3582,6 +3584,9 @@ typedef struct H5C_tag_info_t { H5C_cache_entry_t *head; /* Head of the list of entries for this tag */ size_t entry_cnt; /* Number of entries on list */ hbool_t corked; /* Whether this object is corked */ + + /* Hash table fields */ + UT_hash_handle hh; /* Hash table handle (must be LAST) */ } H5C_tag_info_t; @@ -3974,17 +3979,17 @@ typedef struct H5C_tag_info_t { * * The following fields are maintained to facilitate this. * - * tag_list: A skip list to track entries that belong to an object. - * Each H5C_tag_info_t struct on the tag list corresponds to - * a particular object in the file. Tagged entries can be - * flushed or evicted as a group, or corked to prevent entries - * from being evicted from the cache. + * tag_list: A collection to track entries that belong to an object. + * Each H5C_tag_info_t struct on the tag list corresponds to + * a particular object in the file. Tagged entries can be + * flushed or evicted as a group, or corked to prevent entries + * from being evicted from the cache. * - * "Global" entries, like the superblock and the file's - * freelist, as well as shared entries like global - * heaps and shared object header messages, are not tagged. + * "Global" entries, like the superblock and the file's + * freelist, as well as shared entries like global + * heaps and shared object header messages, are not tagged. * - * ignore_tags: Boolean flag to disable tag validation during entry insertion. + * ignore_tags: Boolean flag to disable tag validation during entry insertion. * * num_objs_corked: Unsigned integer field containing the number of objects * that are "corked". The "corked" status of an object is @@ -4863,7 +4868,7 @@ struct H5C_t { #endif /* H5C_DO_SANITY_CHECKS */ /* Fields for maintaining list of tagged entries */ - H5SL_t * tag_list; + H5C_tag_info_t * tag_list; hbool_t ignore_tags; uint32_t num_objs_corked; diff --git a/src/H5Ctag.c b/src/H5Ctag.c index 92f7dcd..08141a8 100644 --- a/src/H5Ctag.c +++ b/src/H5Ctag.c @@ -82,7 +82,7 @@ typedef struct { /********************/ /* Local Prototypes */ /********************/ -static herr_t H5C__mark_tagged_entries(H5C_t *cache_ptr, haddr_t tag); +static herr_t H5C__mark_tagged_entries(H5C_t *cache, haddr_t tag); /*********************/ /* Package Variables */ @@ -122,16 +122,16 @@ H5FL_EXTERN(H5C_tag_info_t); *------------------------------------------------------------------------- */ herr_t -H5C_ignore_tags(H5C_t *cache_ptr) +H5C_ignore_tags(H5C_t *cache) { FUNC_ENTER_NOAPI_NOERR /* Assertions */ - HDassert(cache_ptr != NULL); - HDassert(cache_ptr->magic == H5C__H5C_T_MAGIC); + HDassert(cache != NULL); + HDassert(cache->magic == H5C__H5C_T_MAGIC); /* Set variable to ignore tag values upon assignment */ - cache_ptr->ignore_tags = TRUE; + cache->ignore_tags = TRUE; FUNC_LEAVE_NOAPI(SUCCEED) } /* H5C_ignore_tags */ @@ -150,16 +150,16 @@ H5C_ignore_tags(H5C_t *cache_ptr) *------------------------------------------------------------------------- */ hbool_t -H5C_get_ignore_tags(const H5C_t *cache_ptr) +H5C_get_ignore_tags(const H5C_t *cache) { FUNC_ENTER_NOAPI_NOERR /* Sanity checks */ - HDassert(cache_ptr); - HDassert(cache_ptr->magic == H5C__H5C_T_MAGIC); + HDassert(cache); + HDassert(cache->magic == H5C__H5C_T_MAGIC); /* Return ignore tag value */ - FUNC_LEAVE_NOAPI(cache_ptr->ignore_tags) + FUNC_LEAVE_NOAPI(cache->ignore_tags) } /* H5C_get_ignore_tags */ /*------------------------------------------------------------------------- @@ -175,16 +175,16 @@ H5C_get_ignore_tags(const H5C_t *cache_ptr) *------------------------------------------------------------------------- */ uint32_t -H5C_get_num_objs_corked(const H5C_t *cache_ptr) +H5C_get_num_objs_corked(const H5C_t *cache) { FUNC_ENTER_NOAPI_NOERR /* Sanity checks */ - HDassert(cache_ptr); - HDassert(cache_ptr->magic == H5C__H5C_T_MAGIC); + HDassert(cache); + HDassert(cache->magic == H5C__H5C_T_MAGIC); /* Return value for num_objs_corked */ - FUNC_LEAVE_NOAPI(cache_ptr->num_objs_corked) + FUNC_LEAVE_NOAPI(cache->num_objs_corked) } /* H5C_get_num_objs_corked */ /*------------------------------------------------------------------------- @@ -230,17 +230,17 @@ H5C__tag_entry(H5C_t *cache, H5C_cache_entry_t *entry) additional checking for correctness. */ if (!H5F_addr_defined(tag)) tag = H5AC__IGNORE_TAG; - } /* end if */ + } #if H5C_DO_TAGGING_SANITY_CHECKS else { /* Perform some sanity checks to ensure that a correct tag is being applied */ if (H5C_verify_tag(entry->type->id, tag) < 0) HGOTO_ERROR(H5E_CACHE, H5E_CANTTAG, FAIL, "tag verification failed") - } /* end else */ + } #endif /* Search the list of tagged object addresses in the cache */ - tag_info = (H5C_tag_info_t *)H5SL_search(cache->tag_list, &tag); + HASH_FIND(hh, cache->tag_list, &tag, sizeof(haddr_t), tag_info); /* Check if this is the first entry for this tagged object */ if (NULL == tag_info) { @@ -251,10 +251,9 @@ H5C__tag_entry(H5C_t *cache, H5C_cache_entry_t *entry) /* Set the tag for all entries */ tag_info->tag = tag; - /* Insert tag info into skip list */ - if (H5SL_insert(cache->tag_list, tag_info, &(tag_info->tag)) < 0) - HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, "can't insert tag info in skip list") - } /* end if */ + /* Insert tag info into the hash table */ + HASH_ADD(hh, cache->tag_list, tag, sizeof(haddr_t), tag_info); + } else HDassert(tag_info->corked || (tag_info->entry_cnt > 0 && tag_info->head)); @@ -295,7 +294,7 @@ H5C__untag_entry(H5C_t *cache, H5C_cache_entry_t *entry) H5C_tag_info_t *tag_info; /* Points to a tag info struct */ herr_t ret_value = SUCCEED; /* Return value */ - FUNC_ENTER_PACKAGE + FUNC_ENTER_PACKAGE_NOERR /* Assertions */ HDassert(cache != NULL); @@ -323,17 +322,14 @@ H5C__untag_entry(H5C_t *cache, H5C_cache_entry_t *entry) /* Sanity check */ HDassert(NULL == tag_info->head); - if (H5SL_remove(cache->tag_list, &(tag_info->tag)) != tag_info) - HGOTO_ERROR(H5E_CACHE, H5E_CANTREMOVE, FAIL, "can't remove tag info from list") - /* Release the tag info */ + HASH_DELETE(hh, cache->tag_list, tag_info); tag_info = H5FL_FREE(H5C_tag_info_t, tag_info); - } /* end if */ + } else HDassert(tag_info->corked || NULL != tag_info->head); - } /* end if */ + } -done: FUNC_LEAVE_NOAPI(ret_value) } /* H5C__untag_entry */ @@ -364,7 +360,7 @@ H5C__iter_tagged_entries_real(H5C_t *cache, haddr_t tag, H5C_tag_iter_cb_t cb, v HDassert(cache->magic == H5C__H5C_T_MAGIC); /* Search the list of tagged object addresses in the cache */ - tag_info = (H5C_tag_info_t *)H5SL_search(cache->tag_list, &tag); + HASH_FIND(hh, cache->tag_list, &tag, sizeof(haddr_t), tag_info); /* If there's any entries for this tag, iterate over them */ if (tag_info) { @@ -387,8 +383,8 @@ H5C__iter_tagged_entries_real(H5C_t *cache, haddr_t tag, H5C_tag_iter_cb_t cb, v /* Advance to next entry */ entry = next_entry; - } /* end while */ - } /* end if */ + } + } done: FUNC_LEAVE_NOAPI(ret_value) @@ -724,7 +720,7 @@ herr_t H5C_flush_tagged_entries(H5F_t *f, haddr_t tag) { /* Variable Declarations */ - H5C_t *cache_ptr = NULL; + H5C_t *cache = NULL; herr_t ret_value = SUCCEED; FUNC_ENTER_NOAPI(FAIL) @@ -734,10 +730,10 @@ H5C_flush_tagged_entries(H5F_t *f, haddr_t tag) HDassert(f->shared); /* Get cache pointer */ - cache_ptr = f->shared->cache; + cache = f->shared->cache; /* Mark all entries with specified tag */ - if (H5C__mark_tagged_entries(cache_ptr, tag) < 0) + if (H5C__mark_tagged_entries(cache, tag) < 0) HGOTO_ERROR(H5E_CACHE, H5E_CANTFLUSH, FAIL, "Can't mark tagged entries") /* Flush all marked entries */ @@ -756,7 +752,7 @@ done: * value specified by src_tag and changes it to the value * specified by dest_tag. * - * Return: SUCCEED or FAIL. + * Return: SUCCEED/FAIL * * Programmer: Mike McGreevy * March 17, 2010 @@ -766,27 +762,28 @@ done: herr_t H5C_retag_entries(H5C_t *cache, haddr_t src_tag, haddr_t dest_tag) { - H5C_tag_info_t *tag_info; /* Points to a tag info struct */ - herr_t ret_value = SUCCEED; /* Return value */ + H5C_tag_info_t *tag_info = NULL; /* Function enter macro */ - FUNC_ENTER_NOAPI(FAIL) + FUNC_ENTER_NOAPI_NOERR /* Sanity check */ HDassert(cache); /* Remove tag info from tag list */ - if (NULL != (tag_info = (H5C_tag_info_t *)H5SL_remove(cache->tag_list, &src_tag))) { + HASH_FIND(hh, cache->tag_list, &src_tag, sizeof(haddr_t), tag_info); + if (NULL != tag_info) { + /* Remove info with old tag */ + HASH_DELETE(hh, cache->tag_list, tag_info); + /* Change to new tag */ tag_info->tag = dest_tag; - /* Re-insert tag info into skip list */ - if (H5SL_insert(cache->tag_list, tag_info, &(tag_info->tag)) < 0) - HGOTO_ERROR(H5E_CACHE, H5E_CANTINSERT, FAIL, "can't insert tag info in skip list") - } /* end if */ + /* Re-insert tag info into tag list */ + HASH_ADD(hh, cache->tag_list, tag, sizeof(haddr_t), tag_info); + } -done: - FUNC_LEAVE_NOAPI(ret_value) + FUNC_LEAVE_NOAPI(SUCCEED) } /* H5C_retag_entries() */ /*------------------------------------------------------------------------- diff --git a/src/H5Ipkg.h b/src/H5Ipkg.h index e93ec74..34e6174 100644 --- a/src/H5Ipkg.h +++ b/src/H5Ipkg.h @@ -29,15 +29,6 @@ /* Get package's private header */ #include "H5Iprivate.h" -/* uthash is an external, header-only hash table implementation. - * - * We include the file directly in src/ and #define a few functions - * to use our internal memory calls. - */ -#define uthash_malloc(sz) H5MM_malloc(sz) -#define uthash_free(ptr, sz) H5MM_free(ptr) /* Ignoring sz is intentional */ -#include "uthash.h" - /**************************/ /* Package Private Macros */ /**************************/ diff --git a/src/H5private.h b/src/H5private.h index 415855a..53ed809 100644 --- a/src/H5private.h +++ b/src/H5private.h @@ -139,6 +139,15 @@ #define R_OK 04 #endif +/* uthash is an external, header-only hash table implementation. + * + * We include the file directly in src/ and #define a few functions + * to use our internal memory calls. + */ +#define uthash_malloc(sz) H5MM_malloc(sz) +#define uthash_free(ptr, sz) H5MM_free(ptr) /* Ignoring sz is intentional */ +#include "uthash.h" + /* * MPE Instrumentation support */ -- cgit v0.12