Additional validation of avail_table.

Verify that avail_table is sorted by size and that each element's
size falls within allowed range.

* src/bucket.c (gdbm_get_bucket): Fix bucket validation. Validate
bucket_avail.
(_gdbm_split_bucket): Check return from _gdbm_free.
* src/falloc.c (adjust_bucket_avail,_gdbm_free): Return error code.
All uses updated.
(pop_avail_block): Fix eventual memory leak. Use gdbm_avail_block_validate.
* src/gdbmdefs.h (gdbm_avail_table_valid_p): Change signature.
* src/gdbmopen.c (gdbm_avail_table_valid_p): Traverse the array verifying
address and size of each element.
(gdbm_avail_block_validate)
(gdbm_bucket_avail_table_validate): New functions.
(validate_header): Remove call to gdbm_avail_block_valid_p. Avail_block
is validated later, after it's been loaded.
Bail out if header->next_block does not equal the file size.
(gdbm_fd_open): Validate avail_block.
* src/gdbmstore.c (_gdbm_store): Check return from _gdbm_free. Avoid
endless loop in case of inconsistent h_table.
* src/gdbmtool.c (_gdbm_print_avail_list): Use gdbm_avail_block_validate.
* src/proto.h: Update.
* tests/gtload.c: Improve error diagnostics.

9 files changed, 135 insertions, 49 deletions

diff --git a/src/bucket.c b/src/bucket.c
index 1d961e2..7d65e32 100644
--- a/src/bucket.c
+++ b/src/bucket.c
@@ -96,6 +96,7 @@ _gdbm_get_bucket (GDBM_FILE dbf, int dir_index)
   if (dbf->cache_entry->ca_adr != bucket_adr)
     {
       size_t lru;
+      hash_bucket *bucket;
       
       /* Look in the cache. */
       for (index = 0; index < dbf->cache_size; index++)
@@ -143,14 +144,16 @@ _gdbm_get_bucket (GDBM_FILE dbf, int dir_index)
 	  return -1;
 	}
       /* Validate the bucket */
-      if (!(dbf->bucket->count >= 0
-	    && dbf->bucket->av_count >= 0
-	    && dbf->bucket->count <= dbf->header->bucket_elems
-	    && dbf->bucket->av_count <= dbf->header->bucket_elems))
+      bucket = dbf->bucket_cache[lru].ca_bucket;
+      if (!(bucket->count >= 0 && bucket->count <= dbf->header->bucket_elems))
 	{
 	  GDBM_SET_ERRNO (dbf, GDBM_BAD_BUCKET, TRUE);
 	  return -1;
 	}
+      /* Validate bucket_avail table */
+      if (gdbm_bucket_avail_table_validate (dbf, bucket))
+	return -1;
+
       /* Finally, store it in cache */
       dbf->last_read = lru;
       dbf->bucket_cache[lru].ca_adr = bucket_adr;
@@ -234,7 +237,7 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
   int          elem_loc;	/* Location in new bucket to put element. */
   bucket_element *old_el;	/* Pointer into the old bucket. */
   int	       select;		/* Used to index bucket during movement. */
-
+  
   /* No directories are yet old. */
   old_count = 0;
 
@@ -416,7 +419,8 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
 
   /* Get rid of old directories. */
   for (index = 0; index < old_count; index++)
-    _gdbm_free (dbf, old_adr[index], old_size[index]);
+    if (_gdbm_free (dbf, old_adr[index], old_size[index]))
+      return -1;
 
   return 0;
 }
diff --git a/src/falloc.c b/src/falloc.c
index d146dd0..c3bd145 100644
--- a/src/falloc.c
+++ b/src/falloc.c
@@ -30,7 +30,7 @@ static avail_elem get_elem (int, avail_elem [], int *);
 static avail_elem get_block (int, GDBM_FILE);
 static int push_avail_block (GDBM_FILE);
 static int pop_avail_block (GDBM_FILE);
-static void adjust_bucket_avail (GDBM_FILE);
+static int adjust_bucket_avail (GDBM_FILE);
 
 /* Allocate space in the file DBF for a block NUM_BYTES in length.  Return
    the file address of the start of the block.  
@@ -84,7 +84,8 @@ _gdbm_alloc (GDBM_FILE dbf, int num_bytes)
   /* Put the unused space back in the avail block. */
   av_el.av_adr += num_bytes;
   av_el.av_size -= num_bytes;
-  _gdbm_free (dbf, av_el.av_adr, av_el.av_size);
+  if (_gdbm_free (dbf, av_el.av_adr, av_el.av_size))
+    return 0;
 
   /* Return the address. */
   return file_adr;
@@ -97,14 +98,14 @@ _gdbm_alloc (GDBM_FILE dbf, int num_bytes)
    it avaliable for reuse through _gdbm_alloc.  This routine changes the
    avail structure. */
 
-void
+int
 _gdbm_free (GDBM_FILE dbf, off_t file_adr, int num_bytes)
 {
   avail_elem temp;
 
   /* Is it too small to worry about? */
   if (num_bytes <= IGNORE_SIZE)
-    return;
+    return 0;
 
   /* Initialize the avail element. */
   temp.av_size = num_bytes;
@@ -115,7 +116,8 @@ _gdbm_free (GDBM_FILE dbf, off_t file_adr, int num_bytes)
     {
       if (dbf->header->avail.count == dbf->header->avail.size)
 	{
-	  push_avail_block (dbf);//FIXME: return
+	  if (push_avail_block (dbf))
+	    return -1;
 	}
       _gdbm_put_av_elem (temp, dbf->header->avail.av_table,
 			 &dbf->header->avail.count, dbf->coalesce_blocks);
@@ -131,7 +133,8 @@ _gdbm_free (GDBM_FILE dbf, off_t file_adr, int num_bytes)
 	{
 	  if (dbf->header->avail.count == dbf->header->avail.size)
 	    {
-	      push_avail_block (dbf); //FIXME: return
+	      if (push_avail_block (dbf))
+		return -1;
 	    }
 	  _gdbm_put_av_elem (temp, dbf->header->avail.av_table,
 			     &dbf->header->avail.count, dbf->coalesce_blocks);
@@ -139,11 +142,11 @@ _gdbm_free (GDBM_FILE dbf, off_t file_adr, int num_bytes)
 	}
     }
 
-  if (dbf->header_changed)
-    adjust_bucket_avail (dbf);
+  if (dbf->header_changed && adjust_bucket_avail (dbf))
+    return -1;
 
   /* All work is done. */
-  return;
+  return 0;
 }
 
 
@@ -184,7 +187,7 @@ pop_avail_block (GDBM_FILE dbf)
   if (new_blk == NULL)
     {
       GDBM_SET_ERRNO (dbf, GDBM_MALLOC_ERROR, TRUE);
-      _gdbm_fatal(dbf, _("malloc failed"));
+      _gdbm_fatal (dbf, _("malloc failed"));
       return -1;
     }
 
@@ -194,6 +197,7 @@ pop_avail_block (GDBM_FILE dbf)
   if (file_pos != new_el.av_adr)
     {
       GDBM_SET_ERRNO (dbf, GDBM_FILE_SEEK_ERROR, TRUE);
+      free (new_blk);
       _gdbm_fatal (dbf, _("lseek error"));
       return -1;
     }
@@ -202,13 +206,14 @@ pop_avail_block (GDBM_FILE dbf)
 			    _gdbm_full_read (dbf, new_blk, new_el.av_size));
   if (rc)
     {
+      free (new_blk);
       _gdbm_fatal (dbf, gdbm_db_strerror (dbf));
       return -1;
     }
 
-  if (!gdbm_avail_table_valid_p (dbf, new_blk))
+  if (gdbm_avail_block_validate (dbf, new_blk))
     {
-      gdbm_set_errno (dbf, GDBM_BAD_AVAIL, TRUE);
+      free (new_blk);
       _gdbm_fatal (dbf, gdbm_db_strerror (dbf));
       return -1;
     }
@@ -231,7 +236,10 @@ pop_avail_block (GDBM_FILE dbf)
           /* We're kind of stuck here, so we re-split the header in order to
              avoid crashing.  Sigh. */
           if (push_avail_block (dbf))
-	    return -1;
+	    {
+	      free (new_blk);
+	      return -1;
+	    }
 	}
     }
 
@@ -248,7 +256,10 @@ pop_avail_block (GDBM_FILE dbf)
       /* We're kind of stuck here, so we re-split the header in order to
          avoid crashing.  Sigh. */
       if (push_avail_block (dbf))
-	return -1;
+	{
+	  free (new_blk);
+	  return -1;
+	}
     }
 
   _gdbm_put_av_elem (new_el, dbf->header->avail.av_table,
@@ -405,7 +416,7 @@ _gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count,
 	  if ((av_table[index].av_adr
 	       + av_table[index].av_size) == new_el.av_adr)
 	    {
-	      /* Simply expand the endtry. */
+	      /* Simply expand the entry. */
 	      av_table[index].av_size += new_el.av_size;
 	    }
 	    /* Can we merge with the next block? */
@@ -457,7 +468,7 @@ _gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count,
 
 
 /* Get_block "allocates" new file space and the end of the file.  This is
-   done in integral block sizes.  (This helps insure that data smaller than
+   done in integral block sizes.  (This helps ensure that data smaller than
    one block size is in a single block.)  Enough blocks are allocated to
    make sure the number of bytes allocated in the blocks is larger than SIZE.
    DBF contains the file header that needs updating.  This routine does
@@ -489,7 +500,7 @@ get_block (int size, GDBM_FILE dbf)
 
 /*  When the header already needs writing, we can make sure the current
     bucket has its avail block as close to 1/3 full as possible. */
-static void
+static int
 adjust_bucket_avail (GDBM_FILE dbf)
 {
   int third = BUCKET_AVAIL / 3;
@@ -500,13 +511,14 @@ adjust_bucket_avail (GDBM_FILE dbf)
     {
       if (dbf->header->avail.count > 0)
 	{
+	  //FIXME: what if _gdbm_put_av_elem return FALSE?
 	  dbf->header->avail.count -= 1;
 	  av_el = dbf->header->avail.av_table[dbf->header->avail.count];
 	  _gdbm_put_av_elem (av_el, dbf->bucket->bucket_avail,
 			     &dbf->bucket->av_count, dbf->coalesce_blocks);
 	  dbf->bucket_changed = TRUE;
 	}
-      return;
+      return 0;
     }
 
   /* Is there too much in the bucket? */
@@ -514,8 +526,15 @@ adjust_bucket_avail (GDBM_FILE dbf)
 	 && dbf->header->avail.count < dbf->header->avail.size)
     {
       av_el = get_elem (0, dbf->bucket->bucket_avail, &dbf->bucket->av_count);
-      _gdbm_put_av_elem (av_el, dbf->header->avail.av_table,
-			 &dbf->header->avail.count, dbf->coalesce_blocks);
+      if (av_el.av_size == 0
+	  || _gdbm_put_av_elem (av_el, dbf->header->avail.av_table,
+				&dbf->header->avail.count,
+				dbf->coalesce_blocks) == FALSE) 
+	{
+	  GDBM_SET_ERRNO (dbf, GDBM_BAD_AVAIL, TRUE);
+	  return -1;
+	}
       dbf->bucket_changed = TRUE;
     }
+  return 0;
 }
diff --git a/src/gdbmdefs.h b/src/gdbmdefs.h
index a53f637..d940c5d 100644
--- a/src/gdbmdefs.h
+++ b/src/gdbmdefs.h
@@ -75,7 +75,8 @@ gdbm_avail_block_valid_p (avail_block const *av)
 }
 
 /* Return true if both AV and the size of AV->av_table are valid */
-extern int gdbm_avail_table_valid_p (GDBM_FILE dbf, avail_block const *av);
+extern int gdbm_avail_table_valid_p (GDBM_FILE dbf,
+				     avail_elem const *av, int count);
 
 /* The dbm file header keeps track of the current location of the hash
    directory and the free space in the file.  */
diff --git a/src/gdbmdelete.c b/src/gdbmdelete.c
index a71ab2c..5660d3a 100644
--- a/src/gdbmdelete.c
+++ b/src/gdbmdelete.c
@@ -82,7 +82,8 @@ gdbm_delete (GDBM_FILE dbf, datum key)
   /* Free the file space. */
   free_adr = elem.data_pointer;
   free_size = elem.key_size + elem.data_size;
-  _gdbm_free (dbf, free_adr, free_size);
+  if (_gdbm_free (dbf, free_adr, free_size))
+    return -1;
 
   /* Set the flags. */
   dbf->bucket_changed = TRUE;
diff --git a/src/gdbmopen.c b/src/gdbmopen.c
index 974e9e2..5d8dc50 100644
--- a/src/gdbmopen.c
+++ b/src/gdbmopen.c
@@ -21,6 +21,7 @@
 #include "autoconf.h"
 
 #include "gdbmdefs.h"
+#include <stddef.h>
 
 /* Determine our native magic number and bail if we can't. */
 #if SIZEOF_OFF_T == 4
@@ -56,9 +57,47 @@ bucket_element_count (size_t bucket_size)
 }
 
 int
-gdbm_avail_table_valid_p (GDBM_FILE dbf, avail_block const *av)
+gdbm_avail_table_valid_p (GDBM_FILE dbf, avail_elem const *av, int count)
 {
-  return gdbm_avail_block_valid_p (av) && av->size <= dbf->header->avail.size;
+  off_t prev = 0;
+  int i;
+    
+  prev = 0;
+  for (i = 0; i < count; i++, av++)
+    {
+      if (!(av->av_size >= prev
+	    && av->av_adr >= dbf->header->bucket_size
+	    && av->av_adr + av->av_size <= dbf->header->next_block))
+	return 0;
+      prev = av->av_size;
+    }
+  return 1;
+}
+
+int
+gdbm_avail_block_validate (GDBM_FILE dbf, avail_block *avblk)
+{
+  if (!(gdbm_avail_block_valid_p (avblk)
+	&& gdbm_avail_table_valid_p (dbf, avblk->av_table, avblk->count)))
+    {
+      GDBM_SET_ERRNO (dbf, GDBM_BAD_AVAIL, TRUE);
+      return -1;
+    }
+  return 0;
+}
+
+int
+gdbm_bucket_avail_table_validate (GDBM_FILE dbf, hash_bucket *bucket)
+{
+  if (!(bucket->av_count >= 0
+	&& bucket->av_count <= BUCKET_AVAIL
+	&& gdbm_avail_table_valid_p (dbf, bucket->bucket_avail,
+				     bucket->av_count)))
+    {
+      GDBM_SET_ERRNO (dbf, GDBM_BAD_AVAIL, TRUE);
+      return -1;
+    }
+  return 0;
 }
 
 static int
@@ -97,6 +136,10 @@ validate_header (gdbm_file_header const *hdr, struct stat const *st)
       return GDBM_BLOCK_SIZE_ERROR;
     }
 
+  if (hdr->next_block != st->st_size)
+    /* FIXME: Should return GDBM_NEED_RECOVERY instead? */
+    return GDBM_BAD_HEADER;
+  
   /* Make sure dir and dir + dir_size fall within the file boundary */
   if (!(hdr->dir > 0
 	&& hdr->dir < st->st_size
@@ -117,10 +160,6 @@ validate_header (gdbm_file_header const *hdr, struct stat const *st)
   if (hdr->bucket_elems != bucket_element_count (hdr->bucket_size))
     return GDBM_BAD_HEADER;
 
-  /* Validate the avail block */
-  if (!gdbm_avail_block_valid_p (&hdr->avail))
-    return GDBM_BAD_HEADER;
-
   if (((hdr->block_size - sizeof (gdbm_file_header)) / sizeof(avail_elem) + 1)
       != hdr->avail.size)
     return GDBM_BAD_HEADER;    
@@ -448,6 +487,14 @@ gdbm_fd_open (int fd, const char *file_name, int block_size,
 	  SAVE_ERRNO (gdbm_close (dbf));
 	  return NULL;
 	}
+
+      if (gdbm_avail_block_validate (dbf, &dbf->header->avail))
+	{
+	  if (!(flags & GDBM_CLOERROR))
+	    dbf->desc = -1;
+	  SAVE_ERRNO (gdbm_close (dbf));
+	  return NULL;
+	}	  
 	
       /* Allocate space for the hash table directory.  */
       dbf->dir = malloc (dbf->header->dir_size);
diff --git a/src/gdbmstore.c b/src/gdbmstore.c
index 7b2ed04..2ed1616 100644
--- a/src/gdbmstore.c
+++ b/src/gdbmstore.c
@@ -28,12 +28,13 @@
    before returning from this procedure.  The FLAGS define the action to
    take when the KEY is already in the database.  The value GDBM_REPLACE
    asks that the old data be replaced by the new CONTENT.  The value
-   GDBM_INSERT asks that an error be returned and no action taken.  A
-   return value of 0 means no errors.  A return value of -1 means that
-   the item was not stored in the data base because the caller was not an
-   official writer. A return value of 0 means that the item was not stored
-   because the argument FLAGS was GDBM_INSERT and the KEY was already in
-   the database. */
+   GDBM_INSERT asks that an error be returned and no action taken.
+
+   On success (the item was stored), 0 is returned. If the item could
+   not be stored because a matching key already exists and GDBM_REPLACE
+   was not given, 1 is returned and gdbm_errno (as well as the database
+   errno value) is set to GDBM_CANNOT_REPLACE. Otherwise, if another
+   error occurred, -1 is returned. */
 
 int
 gdbm_store (GDBM_FILE dbf, datum key, datum content, int flags)
@@ -91,7 +92,8 @@ gdbm_store (GDBM_FILE dbf, datum key, datum content, int flags)
 	              + dbf->bucket->h_table[elem_loc].data_size;
 	  if (free_size != new_size)
 	    {
-	      _gdbm_free (dbf, free_adr, free_size);
+	      if (_gdbm_free (dbf, free_adr, free_size))
+		return -1;
 	    }
 	  else
 	    {
@@ -123,6 +125,8 @@ gdbm_store (GDBM_FILE dbf, datum key, datum content, int flags)
   /* If this is a new entry in the bucket, we need to do special things. */
   if (elem_loc == -1)
     {
+      int start_loc;
+      
       if (dbf->bucket->count == dbf->header->bucket_elems)
 	{
 	  /* Split the current bucket. */
@@ -131,10 +135,17 @@ gdbm_store (GDBM_FILE dbf, datum key, datum content, int flags)
 	}
       
       /* Find space to insert into bucket and set elem_loc to that place. */
-      elem_loc = new_hash_val % dbf->header->bucket_elems;
+      elem_loc = start_loc = new_hash_val % dbf->header->bucket_elems;
       while (dbf->bucket->h_table[elem_loc].hash_value != -1)
-	elem_loc = (elem_loc + 1) % dbf->header->bucket_elems;
-
+	{
+	  elem_loc = (elem_loc + 1) % dbf->header->bucket_elems;
+	  if (elem_loc == start_loc)
+	    {
+	      GDBM_SET_ERRNO (dbf, GDBM_BAD_HASH_TABLE, TRUE);
+	      return -1;
+	    }
+	}
+      
       /* We now have another element in the bucket.  Add the new information.*/
       dbf->bucket->count++;
       dbf->bucket->h_table[elem_loc].hash_value = new_hash_val;
diff --git a/src/gdbmtool.c b/src/gdbmtool.c
index 06cd593..6096c07 100644
--- a/src/gdbmtool.c
+++ b/src/gdbmtool.c
@@ -281,7 +281,7 @@ _gdbm_print_avail_list (FILE *fp, GDBM_FILE dbf)
       /* Print the block! */
       fprintf (fp, _("\nblock = %d\nsize  = %d\ncount = %d\n"), temp,
 	       av_stk->size, av_stk->count);
-      if (gdbm_avail_table_valid_p (dbf, av_stk))
+      if (gdbm_avail_block_validate (dbf, av_stk))
 	av_table_display (av_stk->av_table, av_stk->count, fp);
       else
 	terror (_("invalid avail_block"));
@@ -468,7 +468,7 @@ store_handler (struct handler_param *param)
   if (gdbm_store (gdbm_file,
 		  PARAM_DATUM (param, 0), PARAM_DATUM (param, 1),
 		  GDBM_REPLACE) != 0)
-    terror ("%s", _("Item not inserted."));
+    terror (_("Item not inserted: %s."), gdbm_db_strerror (gdbm_file));
 }
 
 /* first - begin iteration */
diff --git a/src/proto.h b/src/proto.h
index 114221e..c8c9e53 100644
--- a/src/proto.h
+++ b/src/proto.h
@@ -29,7 +29,7 @@ int _gdbm_write_bucket (GDBM_FILE, cache_elem *);
 
 /* From falloc.c */
 off_t _gdbm_alloc       (GDBM_FILE, int);
-void _gdbm_free         (GDBM_FILE, off_t, int);
+int  _gdbm_free         (GDBM_FILE, off_t, int);
 int  _gdbm_put_av_elem  (avail_elem, avail_elem [], int *, int);
 
 /* From findkey.c */
@@ -50,6 +50,9 @@ void _gdbm_fatal	(GDBM_FILE, const char *);
 int _gdbm_init_cache	(GDBM_FILE, size_t);
 void _gdbm_init_cache_entry (GDBM_FILE, int);
 
+int gdbm_avail_block_validate (GDBM_FILE dbf, avail_block *avblk);
+int gdbm_bucket_avail_table_validate (GDBM_FILE dbf, hash_bucket *bucket);
+
 /* From mmap.c */
 int _gdbm_mapped_init	(GDBM_FILE);
 void _gdbm_mapped_unmap	(GDBM_FILE);
diff --git a/tests/gtload.c b/tests/gtload.c
index cc66b94..273ebbe 100644
--- a/tests/gtload.c
+++ b/tests/gtload.c
@@ -333,8 +333,8 @@ main (int argc, char **argv)
       data.dsize = strlen (data.dptr) + data_z;
       if (gdbm_store (dbf, key, data, replace) != 0)
 	{
-	  fprintf (stderr, "%s: %d: item not inserted\n",
-		   progname, line);
+	  fprintf (stderr, "%s: %d: item not inserted: %s\n",
+		   progname, line, gdbm_db_strerror (dbf));
 	  if (gdbm_needs_recovery (dbf) && recover)
 	    {
 	      int rc = gdbm_recover (dbf, &rcvr, rcvr_flags);