[svn-r17766] Purpose: Fix bug 1483

Description:
H5HG_load made improper assumptions about the ordering of object indices, namely
that they are in order.  Not only is this not guaranteed by the file format
spec, but this condition can be violated if id's "wrap around" which can happen
when overwriting VL data.  H5HG_load has been fixed to handle any order of
indices.  Also fixed some other bugs involving allocation of global heaps in
memory.

Tested: jam, linew, amani (h5committest)

3 files changed, 155 insertions, 14 deletions

diff --git a/src/H5HG.c b/src/H5HG.c
index 0703eef..b4662eb 100644
--- a/src/H5HG.c
+++ b/src/H5HG.c
@@ -311,7 +311,7 @@ H5HG_alloc (H5F_t *f, H5HG_heap_t *heap, size_t size, unsigned * heap_flags_ptr)
      * Find an ID for the new object. ID zero is reserved for the free space
      * object.
      */
-    if(heap->nused<H5HG_MAXIDX)
+    if(heap->nused<=H5HG_MAXIDX)
         idx=heap->nused++;
     else {
         for (idx=1; idx<heap->nused; idx++)
@@ -327,17 +327,21 @@ H5HG_alloc (H5F_t *f, H5HG_heap_t *heap, size_t size, unsigned * heap_flags_ptr)
         H5HG_obj_t *new_obj;	/* New array of object descriptions */
 
         /* Determine the new number of objects to index */
-        new_alloc=MAX(heap->nalloc*2,(idx+1));
-        assert(new_alloc<=(H5HG_MAXIDX+1));
+        /* nalloc is *not* guaranteed to be a power of 2! - NAF 10/26/09 */
+        new_alloc = MIN(MAX(heap->nalloc * 2, (idx + 1)), (H5HG_MAXIDX + 1));
+        HDassert(idx < new_alloc);
 
         /* Reallocate array of objects */
         if (NULL==(new_obj = H5FL_SEQ_REALLOC (H5HG_obj_t, heap->obj, new_alloc)))
             HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, 0, "memory allocation failed")
 
+        /* Clear newly allocated space */
+        HDmemset(&new_obj[heap->nalloc], 0, (new_alloc - heap->nalloc) * sizeof(heap->obj[0]));
+
         /* Update heap information */
         heap->nalloc=new_alloc;
         heap->obj=new_obj;
-        assert(heap->nalloc>heap->nused);
+        HDassert(heap->nalloc>heap->nused);
     } /* end if */
 
     /* Initialize the new object */
diff --git a/src/H5HGcache.c b/src/H5HGcache.c
index 9419eef..19f2526 100644
--- a/src/H5HGcache.c
+++ b/src/H5HGcache.c
@@ -170,11 +170,12 @@ H5HG_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void UNUSED * udata1,
     /* Decode each object */
     p = heap->chunk + H5HG_SIZEOF_HDR(f);
     nalloc = H5HG_NOBJS(f, heap->size);
-    if(NULL == (heap->obj = H5FL_SEQ_MALLOC(H5HG_obj_t, nalloc)))
+
+    /* Calloc the obj array because the file format spec makes no guarantee
+     * about the order of the objects, and unused slots must be set to zero.
+     */
+    if(NULL == (heap->obj = H5FL_SEQ_CALLOC(H5HG_obj_t, nalloc)))
 	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
-    heap->obj[0].nrefs = 0;
-    heap->obj[0].size = 0;
-    heap->obj[0].begin = NULL;
 
     heap->nalloc = nalloc;
     while(p < (heap->chunk + heap->size)) {
@@ -201,14 +202,19 @@ H5HG_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void UNUSED * udata1,
 
                 /* Determine the new number of objects to index */
                 new_alloc = MAX(heap->nalloc * 2, (idx + 1));
+                HDassert(idx < new_alloc);
 
                 /* Reallocate array of objects */
                 if(NULL == (new_obj = H5FL_SEQ_REALLOC(H5HG_obj_t, heap->obj, new_alloc)))
                     HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
 
+                /* Clear newly allocated space */
+                HDmemset(&new_obj[heap->nalloc], 0, (new_alloc - heap->nalloc) * sizeof(heap->obj[0]));
+
                 /* Update heap information */
                 heap->nalloc = new_alloc;
                 heap->obj = new_obj;
+                HDassert(heap->nalloc>heap->nused);
             } /* end if */
 
 	    UINT16DECODE(p, heap->obj[idx].nrefs);
@@ -219,16 +225,16 @@ H5HG_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void UNUSED * udata1,
 	    /*
 	     * The total storage size includes the size of the object header
 	     * and is zero padded so the next object header is properly
-	     * aligned. The last bit of space is the free space object whose
-	     * size is never padded and already includes the object header.
+	     * aligned. The entire obj array was calloc'ed, so no need to zero
+	     * the space here. The last bit of space is the free space object
+	     * whose size is never padded and already includes the object
+	     * header.
 	     */
 	    if(idx > 0) {
 		need = H5HG_SIZEOF_OBJHDR(f) + H5HG_ALIGN(heap->obj[idx].size);
 
-                /* Check for "gap" in index numbers (caused by deletions) and fill in heap object values */
-                if(idx > (max_idx + 1))
-                    HDmemset(&heap->obj[max_idx + 1], 0, sizeof(H5HG_obj_t) * (idx - (max_idx + 1)));
-                max_idx = idx;
+                if(idx > max_idx)
+                    max_idx = idx;
 	    } /* end if */
             else
 		need = heap->obj[idx].size;
diff --git a/test/gheap.c b/test/gheap.c
index 6dbd8a3..b2c9090 100644
--- a/test/gheap.c
+++ b/test/gheap.c
@@ -30,11 +30,27 @@
 #include "H5Iprivate.h"
 #include "H5Pprivate.h"
 
+/* Macros for printing error messages in loops.  These print up to
+ * GHEAP_REPEATED_ERR_LIM errors, and suppress the rest */
+#define GHEAP_REPEATED_ERR_LIM 20
+
+#define GHEAP_REPEATED_ERR(MSG)                                                \
+{                                                                              \
+    nerrors++;                                                                 \
+    if(nerrors <= GHEAP_REPEATED_ERR_LIM) {                                    \
+        H5_FAILED();                                                           \
+        puts(MSG);                                                             \
+        if(nerrors == GHEAP_REPEATED_ERR_LIM)                                  \
+            puts("    Suppressing further errors...");                         \
+    } /* end if */                                                             \
+} /* end GHEAP_REPEATED_ERR */
+
 const char *FILENAME[] = {
     "gheap1",
     "gheap2",
     "gheap3",
     "gheap4",
+    "gheapooo",
     NULL
 };
 
@@ -385,6 +401,120 @@ test_4 (hid_t fapl)
 
 
 /*-------------------------------------------------------------------------
+ * Function:	test_ooo_indices
+ *
+ * Purpose:	Tests that indices can be stored out of order.  This can
+ *              happen when the indices "wrap around" due to many
+ *              insertions and deletions (for example, from rewriting a
+ *              VL dataset).
+ *
+ * Return:	Success:	0
+ *
+ *		Failure:	number of errors
+ *
+ * Programmer:	Neil Fortner
+ *              Monday, October 26, 2009
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static int
+test_ooo_indices(hid_t fapl)
+{
+    hid_t	file = -1;
+    H5F_t 	*f = NULL;
+    unsigned	i, j;
+    H5HG_t	*obj = NULL;
+    herr_t	status;
+    int		nerrors=0;
+    char	filename[1024];
+
+    TESTING("out of order indices");
+
+    if(NULL == (obj = (H5HG_t *)HDmalloc(2000 * sizeof(*obj))))
+        goto error;
+
+    /* Open a clean file */
+    h5_fixname(FILENAME[4], fapl, filename, sizeof filename);
+    if((file = H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl)) < 0)
+        goto error;
+    if(NULL == (f = (H5F_t *)H5I_object(file))) {
+        H5_FAILED();
+        puts("    Unable to create file");
+        goto error;
+    } /* end if */
+
+    /* Alternately insert 1000 entries and remove the previous group of 1000
+     * entries, until the indices wrap around */
+    for(i=0; i<66; i++) {
+        /* Insert 1000 entries.  The index into the obj array will alternate up
+         * and down by 1000 so the previous set of insertions is preserved and
+         * can be deleted. */
+        for(j=1000*((~i&1)); j<1000*((~i&1)+1); j++) {
+            H5Eclear2(H5E_DEFAULT);
+            status = H5HG_insert(f, H5P_DATASET_XFER_DEFAULT, sizeof(j), &j, &obj[j]);
+            if (status<0)
+                GHEAP_REPEATED_ERR("    Unable to insert object into global heap")
+
+            /* Check that the index is as expected */
+            if(obj[j].idx != ((1000 * i) + j - (1000 * ((~i & 1)))) % ((1u << 16) - 1) + 1)
+                GHEAP_REPEATED_ERR("    Unexpected global heap index");
+        } /* end for */
+
+        /* Remove the previous 1000 entries */
+        if(i>0)
+            for(j=1000*(i&1); j<1000*((i&1)+1); j++) {
+                H5Eclear2(H5E_DEFAULT);
+                status = H5HG_remove(f, H5P_DATASET_XFER_DEFAULT, &obj[j]);
+                if (status<0)
+                    GHEAP_REPEATED_ERR("    Unable to remove object from global heap");
+            } /* end for */
+    } /* end for */
+
+    /* The indices should have "wrapped around" on the last iteration */
+    HDassert(obj[534].idx == 65535);
+    HDassert(obj[535].idx == 1);
+
+    /* Reopen the file */
+    if (H5Fclose(file)<0) goto error;
+    if((file = H5Fopen(filename, H5F_ACC_RDWR, fapl)) < 0)
+        goto error;
+    if(NULL == (f = (H5F_t *)H5I_object(file))) {
+        H5_FAILED();
+        puts("    Unable to open file");
+        goto error;
+    } /* end if */
+
+    /* Read the objects to make sure the heap is still readable */
+    for(i=0; i<1000; i++) {
+        if(NULL == H5HG_read(f, H5P_DATASET_XFER_DEFAULT, &obj[i], &j, NULL))
+            goto error;
+        if(i != j) {
+            H5_FAILED();
+            puts("    Incorrect read value");
+            goto error;
+        } /* end if */
+    } /* end for */
+
+    if (H5Fclose(file)<0) goto error;
+    if (nerrors) goto error;
+    HDfree(obj);
+    obj = NULL;
+    PASSED();
+    return 0;
+
+ error:
+    H5E_BEGIN_TRY {
+	H5Fclose(file);
+    } H5E_END_TRY;
+    if(obj)
+        HDfree(obj);
+    return MAX(1, nerrors);
+} /* end test_ooo_indices */
+
+
+/*-------------------------------------------------------------------------
  * Function:	main
  *
  * Purpose:	Tests global heap.
@@ -413,6 +543,7 @@ main (void)
     nerrors += test_2(fapl);
     nerrors += test_3(fapl);
     nerrors += test_4(fapl);
+    nerrors += test_ooo_indices(fapl);
     if (nerrors) goto error;
 
     puts("All global heap tests passed.");