From 966adccc597418b63f7299701210bdd035d5cdf7 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Tue, 27 Aug 2002 14:59:12 -0500 Subject: [svn-r5900] Purpose: Code cleanup/New Feature Description: Improve the space allocation in the file by re-using freed space more effectively. Platforms tested: FreeBSD 4.6 (sleipnir) w/serial & parallel --- release_docs/RELEASE.txt | 2 + src/H5FD.c | 126 ++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 117 insertions(+), 11 deletions(-) diff --git a/release_docs/RELEASE.txt b/release_docs/RELEASE.txt index 37fb5ab..ff86398 100644 --- a/release_docs/RELEASE.txt +++ b/release_docs/RELEASE.txt @@ -35,6 +35,8 @@ Bug Fixes since HDF5-1.4.0 Library ------- + * Partially fixed space allocation inefficiencies in the file by + improving our algorithms for re-using freed space. QAK - 2002/08/27 * Fixed data corruption problem which could occur when fill values were written to a contiguously stored dataset in parallel. QAK - 2002/08/27 * Fixed metadata corruption problem which could occur when many objects diff --git a/src/H5FD.c b/src/H5FD.c index 6451435..dd15734 100644 --- a/src/H5FD.c +++ b/src/H5FD.c @@ -35,6 +35,9 @@ static herr_t H5FD_init_interface(void); static herr_t H5FD_free_cls(H5FD_class_t *cls); static haddr_t H5FD_real_alloc(H5FD_t *file, H5FD_mem_t type, hsize_t size); +/* Declare a free list to manage the H5FD_free_t struct */ +H5FL_DEFINE(H5FD_free_t); + /* Declare a PQ free list to manage the metadata accumulator buffer */ H5FL_BLK_DEFINE_STATIC(meta_accum); @@ -920,7 +923,7 @@ H5FD_close(H5FD_t *file) nbytes += cur->size; #endif next = cur->next; - H5MM_xfree(cur); + H5FL_FREE(H5FD_free_t,cur); } file->fl[i]=NULL; } @@ -1277,7 +1280,7 @@ H5FD_alloc(H5FD_t *file, H5FD_mem_t type, hsize_t size) prev->next = cur->next; else file->fl[mapped_type] = cur->next; - H5MM_xfree(cur); + H5FL_FREE(H5FD_free_t,cur); if (size==file->maxsize) file->maxsize=0; /*unknown*/ HGOTO_DONE(ret_value); @@ -1329,7 +1332,7 @@ H5FD_alloc(H5FD_t *file, H5FD_mem_t type, hsize_t size) prev->next = cur->next; else file->fl[mapped_type] = cur->next; - H5MM_xfree(cur); + H5FL_FREE(H5FD_free_t,cur); if (size==file->maxsize) file->maxsize=0; /*unknown*/ HGOTO_DONE(ret_value); @@ -1389,7 +1392,7 @@ H5FD_alloc(H5FD_t *file, H5FD_mem_t type, hsize_t size) else { /* Attempt to allocate memory for temporary node */ - tmp = H5MM_malloc(sizeof(H5FD_free_t)); + tmp = H5FL_ALLOC(H5FD_free_t,0); #ifdef H5F_DEBUG if (H5DEBUG(F)) { HDfprintf(H5DEBUG(F), @@ -1407,7 +1410,7 @@ H5FD_alloc(H5FD_t *file, H5FD_mem_t type, hsize_t size) } /* end if */ else { /* no tail piece */ - H5MM_xfree(tmp); + H5FL_FREE(H5FD_free_t,tmp); } /* end else */ } /* end if */ else { @@ -1754,13 +1757,114 @@ H5FD_free(H5FD_t *file, H5FD_mem_t type, haddr_t addr, hsize_t size) * driver deallocate the memory. */ if (mapped_type>=0) { - H5FD_free_t *cur = H5MM_malloc(sizeof(H5FD_free_t)); + H5FD_free_t *curr; /* Current free block being inspected */ + H5FD_free_t *prev; /* Previous free block being inspected */ + + /* Scan through the existing blocks for the mapped type to see if we can extend one */ + curr=file->fl[mapped_type]; + prev=NULL; + while(curr!=NULL) { + /* Check if the block to free adjoins the start of the current block */ + if((addr+size)==curr->addr) { + /* Adjust the address and size of the block found */ + curr->addr=addr; + curr->size+=size; + + /* Break out of loop */ + break; + } /* end if */ + else { + /* Check if the block to free adjoins the end of the current block */ + if((curr->addr+curr->size)==addr) { + /* Adjust the size of the block found */ + curr->size+=size; + + /* Break out of loop */ + break; + } /* end if */ + else { + /* Advance to next node in list */ + prev=curr; + curr=curr->next; + } /* end else */ + } /* end else */ + } /* end while */ + + /* Check if we adjusted an existing block */ + if(curr!=NULL) { + H5FD_free_t *merge_curr; /* Current free block for merging */ + H5FD_free_t *merge_prev; /* Previous free block for merging */ + + + /* Scan through the existing blocks for the mapped type to see if we can merge the block we just found */ + merge_curr=file->fl[mapped_type]; + merge_prev=NULL; + while(merge_curr!=NULL) { + /* Check if the found block adjoins the start of the current block */ + if((curr->addr+curr->size)==merge_curr->addr) { + /* Adjust the size of the block found */ + curr->size+=merge_curr->size; + + /* Break out of loop */ + break; + } /* end if */ + else { + /* Check if the found block adjoins the end of the current block */ + if((merge_curr->addr+merge_curr->size)==curr->addr) { + /* Adjust the address and size of the block found */ + curr->addr=merge_curr->addr; + curr->size+=merge_curr->size; + + /* Break out of loop */ + break; + } /* end if */ + else { + /* Advance to next node in list */ + merge_prev=merge_curr; + merge_curr=merge_curr->next; + } /* end else */ + } /* end else */ + } /* end while */ + + /* Check if we merged a block out of existance */ + if(merge_curr!=NULL) { + /* Check if there was a previous block in the list */ + if(merge_prev!=NULL) + /* Eliminate the merged block from the list */ + merge_prev->next=merge_curr->next; + /* No previous block, this must be the head of the list */ + else + /* Eliminate the merged block from the list */ + file->fl[mapped_type] = merge_curr->next; + + /* Check for eliminating the block before the 'found' one */ + if(merge_curr==prev) + prev=merge_prev; + + /* Free the memory for the merged block */ + H5FL_FREE(H5FD_free_t,merge_curr); + } /* end if */ + + /* Move the node found to the front, if it wasn't already there */ + if(prev!=NULL) { + prev->next=curr->next; + curr->next = file->fl[mapped_type]; + file->fl[mapped_type] = curr; + } /* end if */ + } /* end if */ + else { + /* Allocate a new node to hold the free block's information */ + if(NULL==(curr = H5FL_ALLOC(H5FD_free_t,0))) + HGOTO_ERROR(H5E_FILE, H5E_NOSPACE, FAIL, "can't allocate node for free space info"); + + curr->addr = addr; + curr->size = size; + curr->next = file->fl[mapped_type]; + file->fl[mapped_type] = curr; + } /* end else */ - cur->addr = addr; - cur->size = size; - cur->next = file->fl[mapped_type]; - file->fl[mapped_type] = cur; - file->maxsize = MAX(file->maxsize, size); + /* Check if we increased the size of the largest block on the list */ + file->maxsize = MAX(file->maxsize, curr->size); } else if (file->cls->free) { if ((file->cls->free)(file, type, addr, size)<0) HGOTO_ERROR(H5E_VFL, H5E_CANTINIT, FAIL, "driver free request failed"); -- cgit v0.12