From df886c57fca24425956766c6c2b094557ba9797a Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Fri, 11 Mar 2005 14:21:04 -0500 Subject: [svn-r10198] Purpose: New feature Description: Handle merging new blocks with existing blocks Platforms tested: FreeBSD 4.11 (sleipnir) Solaris 2.9 (shanti) --- src/H5BT.c | 216 +++++++++++++++++++++++++++++++++++++++++++---------- test/blocktrack.c | 217 ++++++++++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 388 insertions(+), 45 deletions(-) diff --git a/src/H5BT.c b/src/H5BT.c index 88377cc..4e76278 100644 --- a/src/H5BT.c +++ b/src/H5BT.c @@ -142,6 +142,37 @@ H5BT_insert_neighbor_cb(const void *_record, void *_op_data) /*------------------------------------------------------------------------- + * Function: H5BT_insert_modify_cb + * + * Purpose: v2 B-tree modify callback for H5BT_insert() + * + * Return: Success: 0 + * + * Failure: 1 + * + * Programmer: Quincey Koziol + * Friday, March 11, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static int +H5BT_insert_modify_cb(void *_record, void *_op_data, hbool_t *changed) +{ + H5BT_blk_info_t *record = (H5BT_blk_info_t *)_record; + H5BT_blk_info_t *modify = (H5BT_blk_info_t *)_op_data; + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BT_insert_modify_cb) + + *record = *modify; + *changed = TRUE; + + FUNC_LEAVE_NOAPI(0) +} /* end H5BT_insert_modify_cb() */ + + +/*------------------------------------------------------------------------- * Function: H5BT_insert * * Purpose: Insert new block (offset/length) into a block tracker. @@ -163,6 +194,7 @@ H5BT_insert(H5F_t *f, hid_t dxpl_id, haddr_t addr, haddr_t offset, hsize_t lengt hbool_t lower_valid = FALSE, upper_valid = FALSE; /* Lower & upper blocks valid? */ H5BT_blk_info_t new_block; /* Info for new block */ hsize_t nblks; /* Number of blocks tracked */ + unsigned merged = 0; /* How many blocks were merged with */ herr_t ret_value=SUCCEED; FUNC_ENTER_NOAPI(H5BT_insert, FAIL) @@ -205,51 +237,161 @@ H5BT_insert(H5F_t *f, hid_t dxpl_id, haddr_t addr, haddr_t offset, hsize_t lengt /* Clear any errors from H5B2_neighbor() */ H5E_clear_stack(NULL); -#ifdef QAK /* Check for merged blocks */ if(lower_valid || upper_valid) { -HDfprintf(stderr,"%s: Lower & upper block merging not supported yet!\n",FUNC); -HGOTO_ERROR(H5E_BLKTRK, H5E_UNSUPPORTED, FAIL, "lower or upper block found!") - } /* end if */ -#endif /* QAK */ - - /* Insert new block into B-tree */ - new_block.addr = offset; - new_block.len = length; - if(H5B2_insert(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, &new_block) < 0) - HDONE_ERROR(H5E_BLKTRK, H5E_CANTINSERT, FAIL, "unable to insert block") - -/* Update block tracker metadata */ - - /* Determine the number of blocks being tracked */ - if(H5B2_get_nrec(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, &nblks) < 0) - HDONE_ERROR(H5E_BLKTRK, H5E_CANTINSERT, FAIL, "unable to determine # of blocks") - - /* This is the only block tracked so far */ - if(nblks == 1) { - bt->max_block_size = length; - bt->max_block_cnt = 1; - bt->status |= H5BT_STATUS_MAX_VALID; - bt->min_block_size = length; - bt->min_block_cnt = 1; - bt->status |= H5BT_STATUS_MIN_VALID; + H5BT_blk_info_t *old_block=NULL; /* Pointer to info for block merged with */ + + /* Check if the new block should merge with both the lower & upper blocks */ + if((lower_valid && (lower.addr+lower.len) == offset) + && (upper_valid && (offset+length) == upper.addr)) { + /* Delete upper block */ + if(H5B2_remove(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, &upper)<0) + HGOTO_ERROR(H5E_BLKTRK, H5E_CANTDELETE, FAIL, "can't remove block") + + /* Update existing lower block */ + new_block.addr = lower.addr; + new_block.len = lower.len + length + upper.len; + if(H5B2_modify(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, &lower, H5BT_insert_modify_cb, &new_block) < 0) + HGOTO_ERROR(H5E_BLKTRK, H5E_CANTMODIFY, FAIL, "can't change block size") + + /* Merged with 2 blocks */ + merged = 2; + } /* end if */ + /* Check if the new block should merge with just the lower block */ + else if(lower_valid && (lower.addr+lower.len) == offset) { + /* Update existing lower block */ + new_block.addr = lower.addr; + new_block.len = lower.len + length; + if(H5B2_modify(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, &lower, H5BT_insert_modify_cb, &new_block) < 0) + HGOTO_ERROR(H5E_BLKTRK, H5E_CANTMODIFY, FAIL, "can't change block size") + + /* Indicate which block we merged with */ + old_block = &lower; + + /* Merged with 1 block */ + merged = 1; + } /* end else */ + /* Check if the new block should merge with just the upper block */ + else if(upper_valid && (offset+length) == upper.addr) { + /* Update existing upper block */ + new_block.addr = offset; + new_block.len = length + upper.len; + if(H5B2_modify(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, &upper, H5BT_insert_modify_cb, &new_block) < 0) + HGOTO_ERROR(H5E_BLKTRK, H5E_CANTMODIFY, FAIL, "can't change block size") + + /* Indicate which block we merged with */ + old_block = &upper; + + /* Merged with 1 block */ + merged = 1; + } /* end else */ + + /* Check for adjusting the block tracking metadata */ + if(merged == 1) { + /* Check for adjusting the max. block size tracked */ + if(new_block.len > bt->max_block_size) { + bt->max_block_size = new_block.len; + bt->max_block_cnt = 1; + } /* end if */ + else if(new_block.len == bt->max_block_size) + bt->max_block_cnt++; + + /* Check for adjusting the min. block size tracked */ + if(old_block->len < bt->min_block_size) { + /* This should only happen if we don't have full knowledge of all the blocks' sizes */ + HDassert((bt->status & H5BT_STATUS_MIN_VALID) == 0); + + if(new_block.len < bt->min_block_size) { + bt->min_block_size = new_block.len; + bt->min_block_cnt = 1; + } /* end if */ + } /* end if */ + else if(old_block->len == bt->min_block_size) { + /* If this was the minimum block, indicate that the min. size + * is no longer guaranteed valid over the whole set of blocks + * tracked and use the new block size as the minimum value */ + if(bt->min_block_cnt == 1) { + bt->min_block_size = new_block.len; + bt->status &= ~H5BT_STATUS_MIN_VALID; + } /* end if */ + else + /* Decrement the ref. count for the min. block size */ + bt->min_block_cnt--; + } /* end if */ + } /* end if */ + else if(merged == 2) { + /* Check for adjusting the max. block size tracked */ + if(new_block.len > bt->max_block_size) { + bt->max_block_size = new_block.len; + bt->max_block_cnt = 1; + } /* end if */ + else if(new_block.len == bt->max_block_size) + bt->max_block_cnt++; + + /* Check for adjusting the min. block size tracked */ + if(upper.len < bt->min_block_size || lower.len < bt->min_block_size) { + /* This should only happen if we don't have full knowledge of all the blocks' sizes */ + HDassert((bt->status & H5BT_STATUS_MIN_VALID) == 0); + + if(new_block.len < bt->min_block_size) { + bt->min_block_size = new_block.len; + bt->min_block_cnt = 1; + } /* end if */ + } /* end if */ + else if(upper.len == bt->min_block_size || lower.len == bt->min_block_size) { + /* If this was the minimum block, indicate that the min. size + * is no longer guaranteed valid over the whole set of blocks + * tracked and use the new block size as the minimum value */ + if(bt->min_block_cnt == 1) { + bt->min_block_size = new_block.len; + bt->status &= ~H5BT_STATUS_MIN_VALID; + } /* end if */ + else + /* Decrement the ref. count for the min. block size */ + bt->min_block_cnt--; + } /* end if */ + } /* end if */ } /* end if */ - else { - /* Update maximum block size */ - if (length > bt->max_block_size) { + + /* Insert new block into B-tree, if it wasn't marged already*/ + if(!merged) { + new_block.addr = offset; + new_block.len = length; + if(H5B2_insert(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, &new_block) < 0) + HGOTO_ERROR(H5E_BLKTRK, H5E_CANTINSERT, FAIL, "unable to insert block") + + /* Update block tracker metadata */ + + /* Determine the number of blocks being tracked */ + if(H5B2_get_nrec(f, dxpl_id, H5B2_BLKTRK, bt->bt2_addr, &nblks) < 0) + HGOTO_ERROR(H5E_BLKTRK, H5E_CANTINSERT, FAIL, "unable to determine # of blocks") + + /* This is the only block tracked so far */ + if(nblks == 1) { bt->max_block_size = length; bt->max_block_cnt = 1; - } /* end if */ - else if (length == bt->max_block_size) - bt->max_block_cnt++; - - /* Update minimum block size */ - if (length < bt->min_block_size) { + bt->status |= H5BT_STATUS_MAX_VALID; bt->min_block_size = length; bt->min_block_cnt = 1; + bt->status |= H5BT_STATUS_MIN_VALID; + } /* end if */ + else { + /* Update maximum block size */ + if (length > bt->max_block_size) { + bt->max_block_size = length; + bt->max_block_cnt = 1; + } /* end if */ + else if (length == bt->max_block_size) + bt->max_block_cnt++; + + /* Update minimum block size */ + if (length < bt->min_block_size) { + bt->min_block_size = length; + bt->min_block_cnt = 1; + } /* end if */ + else if (length == bt->min_block_size) + bt->min_block_cnt++; } /* end if */ - else if (length == bt->min_block_size) - bt->min_block_cnt++; } /* end if */ /* Increment total number of bytes tracked in all blocks */ diff --git a/test/blocktrack.c b/test/blocktrack.c index 4d9b33c..224de78 100644 --- a/test/blocktrack.c +++ b/test/blocktrack.c @@ -311,7 +311,7 @@ test_insert_few(hid_t fapl) H5Eprint_stack(H5E_DEFAULT, stdout); goto error; } /* end if */ - /* Make certain that the max. info is correct */ + /* Make certain that the min. info is correct */ if(min_size != 20) TEST_ERROR; if(min_count != 1) TEST_ERROR; if(min_valid != 1) TEST_ERROR; @@ -345,7 +345,7 @@ test_insert_few(hid_t fapl) H5Eprint_stack(H5E_DEFAULT, stdout); goto error; } /* end if */ - /* Make certain that the max. info is correct */ + /* Make certain that the min. info is correct */ if(min_size != 20) TEST_ERROR; if(min_count != 1) TEST_ERROR; if(min_valid != 1) TEST_ERROR; @@ -379,12 +379,12 @@ test_insert_few(hid_t fapl) H5Eprint_stack(H5E_DEFAULT, stdout); goto error; } /* end if */ - /* Make certain that the max. info is correct */ + /* Make certain that the min. info is correct */ if(min_size != 20) TEST_ERROR; if(min_count != 1) TEST_ERROR; if(min_valid != 1) TEST_ERROR; - if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)120, (hsize_t)20)<0) { + if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)130, (hsize_t)20)<0) { H5_FAILED(); H5Eprint_stack(H5E_DEFAULT, stdout); goto error; @@ -413,12 +413,12 @@ test_insert_few(hid_t fapl) H5Eprint_stack(H5E_DEFAULT, stdout); goto error; } /* end if */ - /* Make certain that the max. info is correct */ + /* Make certain that the min. info is correct */ if(min_size != 20) TEST_ERROR; if(min_count != 2) TEST_ERROR; if(min_valid != 1) TEST_ERROR; - if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)150, (hsize_t)10)<0) { + if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)160, (hsize_t)10)<0) { H5_FAILED(); H5Eprint_stack(H5E_DEFAULT, stdout); goto error; @@ -447,7 +447,7 @@ test_insert_few(hid_t fapl) H5Eprint_stack(H5E_DEFAULT, stdout); goto error; } /* end if */ - /* Make certain that the max. info is correct */ + /* Make certain that the min. info is correct */ if(min_size != 10) TEST_ERROR; if(min_count != 1) TEST_ERROR; if(min_valid != 1) TEST_ERROR; @@ -549,7 +549,7 @@ test_insert_many(hid_t fapl) H5Eprint_stack(H5E_DEFAULT, stdout); goto error; } /* end if */ - /* Make certain that the max. info is correct */ + /* Make certain that the min. info is correct */ if(min_size != 20) TEST_ERROR; if(min_count != (u+1)) TEST_ERROR; if(min_valid != 1) TEST_ERROR; @@ -675,6 +675,206 @@ error: /*------------------------------------------------------------------------- + * Function: test_insert_merge + * + * Purpose: Basic tests for the block tracker code + * + * Return: Success: 0 + * + * Failure: 1 + * + * Programmer: Quincey Koziol + * Thursday, March 10, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static int +test_insert_merge(hid_t fapl) +{ + hid_t file=-1; + char filename[1024]; + H5F_t *f=NULL; + haddr_t bt_addr; /* Address of block tracker created */ + hsize_t tot_size; /* Total size of blocks tracked */ + hsize_t max_size; /* Max. size of blocks tracked */ + uint32_t max_count; /* Ref. count of max. size of blocks tracked */ + hbool_t max_valid; /* Is max. size valid over all blocks? */ + hsize_t min_size; /* Min. size of blocks tracked */ + uint32_t min_count; /* Ref. count of min. size of blocks tracked */ + hbool_t min_valid; /* Is min. size valid over all blocks? */ + + h5_fixname(FILENAME[0], fapl, filename, sizeof filename); + + /* Create the file to work on */ + if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) TEST_ERROR; + + /* Get a pointer to the internal file object */ + if (NULL==(f=H5I_object(file))) { + H5Eprint_stack(H5E_DEFAULT, stdout); + TEST_ERROR; + } /* end if */ + + if (H5BT_create(f, H5P_DATASET_XFER_DEFAULT, &bt_addr/*out*/)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Insert first block */ + if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)10, (hsize_t)20)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* + * Test inserting blocks which should merge into existing block(s) + */ + TESTING("insert block which merges with existing upper block"); + + /* Insert block which should merge with beginning of existing block */ + if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)8, (hsize_t)2)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + if (H5BT_get_total_size(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &tot_size)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the size is correct */ + if(tot_size != 22) TEST_ERROR; + + if (H5BT_get_max_info(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &max_size, &max_count, &max_valid)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the max. info is correct */ + if(max_size != 22) TEST_ERROR; + if(max_count != 1) TEST_ERROR; + if(max_valid != 1) TEST_ERROR; + + if (H5BT_get_min_info(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &min_size, &min_count, &min_valid)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the min. info is correct */ + if(min_size != 22) TEST_ERROR; + if(min_count != 1) TEST_ERROR; + if(min_valid != 0) TEST_ERROR; + + PASSED(); + + /* + * Test inserting blocks which should merge into existing block(s) + */ + TESTING("insert block which merges with existing lower block"); + + /* Insert block which should merge with end of existing block */ + if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)30, (hsize_t)4)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + if (H5BT_get_total_size(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &tot_size)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the size is correct */ + if(tot_size != 26) TEST_ERROR; + + if (H5BT_get_max_info(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &max_size, &max_count, &max_valid)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the max. info is correct */ + if(max_size != 26) TEST_ERROR; + if(max_count != 1) TEST_ERROR; + if(max_valid != 1) TEST_ERROR; + + if (H5BT_get_min_info(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &min_size, &min_count, &min_valid)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the min. info is correct */ + if(min_size != 26) TEST_ERROR; + if(min_count != 1) TEST_ERROR; + if(min_valid != 0) TEST_ERROR; + + PASSED(); + + /* + * Test inserting blocks which should merge into existing block(s) + */ + TESTING("insert block which merges with existing upper & lower blocks"); + + /* Insert block to merge with */ + if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)40, (hsize_t)10) < 0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + /* Insert block which should merge with end of existing block */ + if (H5BT_insert(f, H5P_DATASET_XFER_DEFAULT, bt_addr, (haddr_t)34, (hsize_t)6) < 0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + + if (H5BT_get_total_size(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &tot_size)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the size is correct */ + if(tot_size != 42) TEST_ERROR; + + if (H5BT_get_max_info(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &max_size, &max_count, &max_valid)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the max. info is correct */ + if(max_size != 42) TEST_ERROR; + if(max_count != 1) TEST_ERROR; + if(max_valid != 1) TEST_ERROR; + + if (H5BT_get_min_info(f, H5P_DATASET_XFER_DEFAULT, bt_addr, &min_size, &min_count, &min_valid)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } /* end if */ + /* Make certain that the min. info is correct */ + if(min_size != 42) TEST_ERROR; + if(min_count != 1) TEST_ERROR; + if(min_valid != 0) TEST_ERROR; + + PASSED(); + + if (H5Fclose(file)<0) TEST_ERROR; + + return 0; + +error: + H5E_BEGIN_TRY { + H5Fclose(file); + } H5E_END_TRY; + return 1; +} /* test_insert_merge() */ + + +/*------------------------------------------------------------------------- * Function: main * * Purpose: Test the block tracker code @@ -708,6 +908,7 @@ main(void) nerrors += test_insert_few(fapl); nerrors += test_insert_many(fapl); nerrors += test_insert_overlap(fapl); + nerrors += test_insert_merge(fapl); if (nerrors) goto error; puts("All block tracker tests passed."); -- cgit v0.12