bitset: check memory allocation

bitset: check memory allocation

[Akim Demaille]

Hi!

Ok to push?

commit 1fddc3eddd988829cd2b5b74dc3fab58a3093af8
Author: Akim Demaille <akim.demaille@gmail.com>
Date:   Thu Sep 5 11:36:39 2019 +0200

    bitset: check memory allocation
    
    Reported by 江 祖铭 (Zu-Ming Jiang).
    https://lists.gnu.org/archive/html/bug-bison/2019-08/msg00016.html
    
    * lib/bitset/table.c (tbitset_resize): Use xrealloc instead of
    realloc.
    * lib/bitset/vector.c (vbitset_resize): Likewise.

diff --git a/lib/bitset/table.c b/lib/bitset/table.c
index 07184d657..01bc65167 100644
--- a/lib/bitset/table.c
+++ b/lib/bitset/table.c
@@ -25,6 +25,7 @@
 #include <string.h>
 
 #include "obstack.h"
+#include "xalloc.h"
 
 /* This file implements expandable bitsets.  These bitsets can be of
    arbitrary length and are more efficient than arrays of bits for
@@ -142,7 +143,7 @@ tbitset_resize (bitset src, bitset_bindex n_bits)
 
           bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
           EBITSET_ELTS (src)
-            = realloc (EBITSET_ELTS (src), size * sizeof (tbitset_elt *));
+            = xrealloc (EBITSET_ELTS (src), size * sizeof (tbitset_elt *));
           EBITSET_ASIZE (src) = size;
         }
 
@@ -156,7 +157,7 @@ tbitset_resize (bitset src, bitset_bindex n_bits)
       if ((oldsize - newsize) >= oldsize / 2)
         {
           EBITSET_ELTS (src)
-            = realloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
+            = xrealloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
           EBITSET_ASIZE (src) = newsize;
         }
 
diff --git a/lib/bitset/vector.c b/lib/bitset/vector.c
index 54f148d56..11960bbd0 100644
--- a/lib/bitset/vector.c
+++ b/lib/bitset/vector.c
@@ -24,6 +24,8 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include "xalloc.h"
+
 /* This file implements variable size bitsets stored as a variable
    length array of words.  Any unused bits in the last word must be
    zero.
@@ -74,7 +76,7 @@ vbitset_resize (bitset src, bitset_bindex n_bits)
 
           bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
           VBITSET_WORDS (src)
-            = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
+            = xrealloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
           VBITSET_ASIZE (src) = size;
         }
 
@@ -89,7 +91,7 @@ vbitset_resize (bitset src, bitset_bindex n_bits)
       if ((oldsize - newsize) >= oldsize / 2)
         {
           VBITSET_WORDS (src)
-            = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
+            = xrealloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
           VBITSET_ASIZE (src) = newsize;
         }
 

Re: bitset: check memory allocation

[Paul Eggert]

On 9/5/19 12:59 PM, Akim Demaille wrote:

>             EBITSET_ELTS (src)
> -            = realloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
> +            = xrealloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));

This code is trying to shrink the bitset, and in the unlikely event that 
such an attempt fails there's no need call xrealloc which will exit the 
whole program; the code can continue to call realloc and if that fails, 
the code can forge ahead with the unshrunk bitset.

There's a similar issue in the vector.c patch.

Other than that, looks OK to me; as I understand it the bitset code is 
not intended for libraries (as lib/bitset/stats.c already calls xcalloc, 
and OBSTACK_CHUNK_ALLOC and OBSTACK_CHUNK_FREE default to xmalloc and 
free) so it's OK for it to call xrealloc.

Come to think of it, though, what's the intent of OBSTACK_CHUNK_ALLOC 
and OBSTACK_CHUNK_FREE? If the intent is for the builder to replace 
xmalloc and free, shouldn't the including code also be able to redefine 
xrealloc and xrealloc?

Also, a nit in nearby code: xcalloc (1, N) is better written as xzalloc (N).

Re: bitset: check memory allocation

[Akim Demaille]

Hi Paul,

Thanks a lot for the detailed answer!

> Le 5 sept. 2019 à 22:54, Paul Eggert <eggert@cs.ucla.edu> a écrit :
> 
> On 9/5/19 12:59 PM, Akim Demaille wrote:
> 
>>            EBITSET_ELTS (src)
>> -            = realloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
>> +            = xrealloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
> 
> This code is trying to shrink the bitset, and in the unlikely event that such an attempt fails there's no need call xrealloc which will exit the whole program; the code can continue to call realloc and if that fails, the code can forge ahead with the unshrunk bitset.
> 
> There's a similar issue in the vector.c patch.

I never noticed realloc would return 0 yet preserve the allocated region, thanks!  This patch should address your concerns:

commit c9c23ad1d50cb5746dc2dd0265e0ae91c746b0b9
Author: Akim Demaille <akim.demaille@gmail.com>
Date:   Thu Sep 5 11:36:39 2019 +0200

    bitset: check memory allocation
    
    Reported by 江 祖铭 (Zu-Ming Jiang).
    With help from Paul Eggert.
    https://lists.gnu.org/archive/html/bug-bison/2019-08/msg00016.html
    
    * lib/bitset/table.c (tbitset_resize): When growing, use xrealloc
    instead of realloc.
    When shrinking, accept failures.
    * lib/bitset/vector.c (vbitset_resize): Likewise.

diff --git a/ChangeLog b/ChangeLog
index fbf95966d..08b2313cb 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2019-09-06  Akim Demaille  <akim@lrde.epita.fr>
+
+	bitset: check memory allocation
+	Reported by 江 祖铭 (Zu-Ming Jiang).
+	With help from Paul Eggert.
+	https://lists.gnu.org/archive/html/bug-bison/2019-08/msg00016.html
+	* lib/bitset/table.c (tbitset_resize): When growing, use xrealloc
+	instead of realloc.
+	When shrinking, accept failures.
+	* lib/bitset/vector.c (vbitset_resize): Likewise.
+
 2019-09-01  Bruno Haible  <bruno@clisp.org>
 
 	gitsub.sh: Add support for shallow-cloning of subdirectories.
diff --git a/lib/bitset/table.c b/lib/bitset/table.c
index 07184d657..7691d9805 100644
--- a/lib/bitset/table.c
+++ b/lib/bitset/table.c
@@ -25,6 +25,7 @@
 #include <string.h>
 
 #include "obstack.h"
+#include "xalloc.h"
 
 /* This file implements expandable bitsets.  These bitsets can be of
    arbitrary length and are more efficient than arrays of bits for
@@ -142,7 +143,7 @@ tbitset_resize (bitset src, bitset_bindex n_bits)
 
           bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
           EBITSET_ELTS (src)
-            = realloc (EBITSET_ELTS (src), size * sizeof (tbitset_elt *));
+            = xrealloc (EBITSET_ELTS (src), size * sizeof (tbitset_elt *));
           EBITSET_ASIZE (src) = size;
         }
 
@@ -155,9 +156,13 @@ tbitset_resize (bitset src, bitset_bindex n_bits)
          the memory unless it is shrinking by a reasonable amount.  */
       if ((oldsize - newsize) >= oldsize / 2)
         {
-          EBITSET_ELTS (src)
+          void *p
             = realloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
-          EBITSET_ASIZE (src) = newsize;
+          if (p)
+            {
+              EBITSET_ELTS (src) = p;
+              EBITSET_ASIZE (src) = newsize;
+            }
         }
 
       /* Need to prune any excess bits.  FIXME.  */
diff --git a/lib/bitset/vector.c b/lib/bitset/vector.c
index 54f148d56..5e543283a 100644
--- a/lib/bitset/vector.c
+++ b/lib/bitset/vector.c
@@ -24,6 +24,8 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include "xalloc.h"
+
 /* This file implements variable size bitsets stored as a variable
    length array of words.  Any unused bits in the last word must be
    zero.
@@ -74,7 +76,7 @@ vbitset_resize (bitset src, bitset_bindex n_bits)
 
           bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
           VBITSET_WORDS (src)
-            = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
+            = xrealloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
           VBITSET_ASIZE (src) = size;
         }
 
@@ -88,9 +90,13 @@ vbitset_resize (bitset src, bitset_bindex n_bits)
          the memory unless it is shrinking by a reasonable amount.  */
       if ((oldsize - newsize) >= oldsize / 2)
         {
-          VBITSET_WORDS (src)
+          void *p
             = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
-          VBITSET_ASIZE (src) = newsize;
+          if (p)
+            {
+              VBITSET_WORDS (src) = p;
+              VBITSET_ASIZE (src) = newsize;
+            }
         }
 
       /* Need to prune any excess bits.  FIXME.  */


> Also, a nit in nearby code: xcalloc (1, N) is better written as xzalloc (N).

How about this stylistic patch?

commit 44e2124e57689417228fc04ded0026dc53cbee57
Author: Akim Demaille <akim.demaille@gmail.com>
Date:   Fri Sep 6 11:38:48 2019 +0200

    bitset: style changes
    
    * lib/bitset/vector.c (vbitset_resize): Factor computation.
    * lib/bitset.c, lib/bitset/stats.c, lib/bitsetv.c: Prefer
    xzalloc to xcalloc.
    Suggested by Paul Eggert.

diff --git a/ChangeLog b/ChangeLog
index 08b2313cb..0e86eba72 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2019-09-06  Akim Demaille  <akim@lrde.epita.fr>
+
+	bitset: style changes
+	* lib/bitset/vector.c (vbitset_resize): Factor computation.
+	* lib/bitset.c, lib/bitset/stats.c, lib/bitsetv.c: Prefer
+	xzalloc to xcalloc.
+	Suggested by Paul Eggert.
+
 2019-09-06  Akim Demaille  <akim@lrde.epita.fr>
 
 	bitset: check memory allocation
diff --git a/lib/bitset.c b/lib/bitset.c
index cccb1e834..6b983f438 100644
--- a/lib/bitset.c
+++ b/lib/bitset.c
@@ -129,7 +129,7 @@ bitset_alloc (bitset_bindex n_bits, enum bitset_type type)
 {
   size_t bytes = bitset_bytes (type, n_bits);
 
-  bitset bset = xcalloc (1, bytes);
+  bitset bset = xzalloc (bytes);
 
   /* The cache is disabled until some elements are allocated.  If we
      have variable length arrays, then we may need to allocate a dummy
diff --git a/lib/bitset/stats.c b/lib/bitset/stats.c
index da73cdcac..fd1ca5912 100644
--- a/lib/bitset/stats.c
+++ b/lib/bitset/stats.c
@@ -694,7 +694,7 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
     case BITSET_ARRAY:
       {
         size_t bytes = abitset_bytes (n_bits);
-        bset->s.bset = xcalloc (1, bytes);
+        bset->s.bset = xzalloc (bytes);
         abitset_init (bset->s.bset, n_bits);
       }
       break;
@@ -702,7 +702,7 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
     case BITSET_LIST:
       {
         size_t bytes = lbitset_bytes (n_bits);
-        bset->s.bset = xcalloc (1, bytes);
+        bset->s.bset = xzalloc (bytes);
         lbitset_init (bset->s.bset, n_bits);
       }
       break;
@@ -710,7 +710,7 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
     case BITSET_TABLE:
       {
         size_t bytes = tbitset_bytes (n_bits);
-        bset->s.bset = xcalloc (1, bytes);
+        bset->s.bset = xzalloc (bytes);
         tbitset_init (bset->s.bset, n_bits);
       }
       break;
@@ -718,7 +718,7 @@ bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
     case BITSET_VECTOR:
       {
         size_t bytes = vbitset_bytes (n_bits);
-        bset->s.bset = xcalloc (1, bytes);
+        bset->s.bset = xzalloc (bytes);
         vbitset_init (bset->s.bset, n_bits);
       }
       break;
diff --git a/lib/bitset/vector.c b/lib/bitset/vector.c
index 5e543283a..ac9ba803b 100644
--- a/lib/bitset/vector.c
+++ b/lib/bitset/vector.c
@@ -82,7 +82,6 @@ vbitset_resize (bitset src, bitset_bindex n_bits)
 
       memset (VBITSET_WORDS (src) + oldsize, 0,
               (newsize - oldsize) * sizeof (bitset_word));
-      VBITSET_SIZE (src) = newsize;
     }
   else
     {
@@ -100,10 +99,9 @@ vbitset_resize (bitset src, bitset_bindex n_bits)
         }
 
       /* Need to prune any excess bits.  FIXME.  */
-
-      VBITSET_SIZE (src) = newsize;
     }
 
+  VBITSET_SIZE (src) = newsize;
   BITSET_NBITS_ (src) = n_bits;
   return n_bits;
 }
diff --git a/lib/bitsetv.c b/lib/bitsetv.c
index b7d0a0191..745f27aef 100644
--- a/lib/bitsetv.c
+++ b/lib/bitsetv.c
@@ -41,7 +41,7 @@ bitsetv_alloc (bitset_bindex n_vecs, bitset_bindex n_bits,
   /* Allocate vector table at head of bitset array.  */
   size_t vector_bytes = (n_vecs + 1) * sizeof (bitset) + bytes - 1;
   vector_bytes -= vector_bytes % bytes;
-  bitset *bsetv = xcalloc (1, vector_bytes + bytes * n_vecs);
+  bitset *bsetv = xzalloc (vector_bytes + bytes * n_vecs);
 
   bitset_bindex i = 0;
   for (i = 0; i < n_vecs; i++)



> Other than that, looks OK to me; as I understand it the bitset code is not intended for libraries (as lib/bitset/stats.c already calls xcalloc, and OBSTACK_CHUNK_ALLOC and OBSTACK_CHUNK_FREE default to xmalloc and free) so it's OK for it to call xrealloc.

Yes, bitset was written this way when we imported it in Bison, where xalloc_die is fine.  I don't know if there are other users of (gnulib's) bitset yet.

> Come to think of it, though, what's the intent of OBSTACK_CHUNK_ALLOC and OBSTACK_CHUNK_FREE? If the intent is for the builder to replace xmalloc and free, shouldn't the including code also be able to redefine xrealloc and xrealloc?

I don't have a strong opinion about this.  We could expose more customization points via macros, or just less: bitset is not ready to be resilient to memory exhaustion.  I have left these OBSTACK_CHUNK_ALLOC, but I would be happier with an explicit 'xmalloc'.

Cheers!

Re: bitset: check memory allocation

[Paul Eggert]

Thanks, and your changes all look good to me; please install when you have the 
time. We can worry about the other issues later (if ever...).

Re: bitset: check memory allocation

[Akim Demaille]

> Le 8 sept. 2019 à 03:17, Paul Eggert <eggert@cs.ucla.edu> a écrit :
> 
> Thanks, and your changes all look good to me; please install when you have the time. We can worry about the other issues later (if ever...).

Installed, thanks!