[PATCH 1/2] quotearg: avoid undefined and/or O(N**2)

[PATCH 1/2] quotearg: avoid undefined and/or O(N**2)

[Paul Eggert]

Avoid undefined and O(N**2) behavior in some very unlikely cases.
* lib/quotearg.c (quotearg_n_options): Document that N must
be less than MIN (INT_MAX, IDX_MAX), and add this to the
abort test; this also avoids a conditional branch.
Use xpalloc instead of xrealloc, to avoid O(N**2) behavior in
very-unlikely cases.
---
 ChangeLog      |  8 ++++++++
 lib/quotearg.c | 18 +++++++++---------
 2 files changed, 17 insertions(+), 9 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 804e22897..d511911fd 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,13 @@
 2021-04-03  Paul Eggert  <eggert@cs.ucla.edu>
 
+	quotearg: avoid undefined and/or O(N**2)
+	Avoid undefined and O(N**2) behavior in some very unlikely cases.
+	* lib/quotearg.c (quotearg_n_options): Document that N must
+	be less than MIN (INT_MAX, IDX_MAX), and add this to the
+	abort test; this also avoids a conditional branch.
+	Use xpalloc instead of xrealloc, to avoid O(N**2) behavior in
+	very-unlikely cases.
+
 	xgethostname: reorganize / simplify
 	xgethostname and xgetdomainname were essentially copies long
 	ago, but they’ve diverged.  Bring them back together again
diff --git a/lib/quotearg.c b/lib/quotearg.c
index 365d6d1dd..570468917 100644
--- a/lib/quotearg.c
+++ b/lib/quotearg.c
@@ -864,7 +864,8 @@ quotearg_free (void)
    OPTIONS specifies the quoting options.
    The returned value points to static storage that can be
    reused by the next call to this function with the same value of N.
-   N must be nonnegative.  N is deliberately declared with type "int"
+   N must be nonnegative; it is typically small, and must be
+   less than MIN (INT_MAX, IDX_MAX).  The type of N is signed
    to allow for future extensions (using negative values).  */
 static char *
 quotearg_n_options (int n, char const *arg, size_t argsize,
@@ -874,22 +875,21 @@ quotearg_n_options (int n, char const *arg, size_t argsize,
 
   struct slotvec *sv = slotvec;
 
-  if (n < 0)
+  int nslots_max = MIN (INT_MAX, IDX_MAX);
+  if (! (0 <= n && n < nslots_max))
     abort ();
 
   if (nslots <= n)
     {
       bool preallocated = (sv == &slotvec0);
-      int nmax = MIN (INT_MAX, MIN (PTRDIFF_MAX, SIZE_MAX) / sizeof *sv) - 1;
+      idx_t new_nslots = nslots;
 
-      if (nmax < n)
-        xalloc_die ();
-
-      slotvec = sv = xrealloc (preallocated ? NULL : sv, (n + 1) * sizeof *sv);
+      slotvec = sv = xpalloc (preallocated ? NULL : sv, &new_nslots,
+                              n - nslots + 1, nslots_max, sizeof *sv);
       if (preallocated)
         *sv = slotvec0;
-      memset (sv + nslots, 0, (n + 1 - nslots) * sizeof *sv);
-      nslots = n + 1;
+      memset (sv + nslots, 0, (new_nslots - nslots) * sizeof *sv);
+      nslots = new_nslots;
     }
 
   {
-- 
2.30.2

[PATCH 2/2] savedir: avoid unlikely undefined behavior

[Paul Eggert]

* lib/savedir.c (streamsavedir): Prefer idx_to size_t where
either will do.  Simplify reallocation of entries.
Use xpalloc to reallocate name_space, to avoid some unlikely
integer overflows.
---
 ChangeLog     |  6 ++++++
 lib/savedir.c | 25 +++++++++----------------
 2 files changed, 15 insertions(+), 16 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index d511911fd..4a665c275 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 2021-04-03  Paul Eggert  <eggert@cs.ucla.edu>
 
+	savedir: avoid unlikely undefined behavior
+	* lib/savedir.c (streamsavedir): Prefer idx_to size_t where
+	either will do.  Simplify reallocation of entries.
+	Use xpalloc to reallocate name_space, to avoid some unlikely
+	integer overflows.
+
 	quotearg: avoid undefined and/or O(N**2)
 	Avoid undefined and O(N**2) behavior in some very unlikely cases.
 	* lib/quotearg.c (quotearg_n_options): Document that N must
diff --git a/lib/savedir.c b/lib/savedir.c
index bcf41700d..1c23d75b6 100644
--- a/lib/savedir.c
+++ b/lib/savedir.c
@@ -91,11 +91,11 @@ char *
 streamsavedir (DIR *dirp, enum savedir_option option)
 {
   char *name_space = NULL;
-  size_t allocated = 0;
+  idx_t allocated = 0;
   direntry_t *entries = NULL;
   size_t entries_allocated = 0;
-  size_t entries_used = 0;
-  size_t used = 0;
+  idx_t entries_used = 0;
+  idx_t used = 0;
   comparison_function cmp = comparison_function_table[option];
 
   if (dirp == NULL)
@@ -116,15 +116,12 @@ streamsavedir (DIR *dirp, enum savedir_option option)
       entry = dp->d_name;
       if (entry[entry[0] != '.' ? 0 : entry[1] != '.' ? 1 : 2] != '\0')
         {
-          size_t entry_size = _D_EXACT_NAMLEN (dp) + 1;
+          idx_t entry_size = _D_EXACT_NAMLEN (dp) + 1;
           if (cmp)
             {
               if (entries_allocated == entries_used)
-                {
-                  size_t n = entries_allocated;
-                  entries = x2nrealloc (entries, &n, sizeof *entries);
-                  entries_allocated = n;
-                }
+                entries = x2nrealloc (entries, &entries_allocated,
+                                      sizeof *entries);
               entries[entries_used].name = xstrdup (entry);
 #if D_INO_IN_DIRENT
               entries[entries_used].ino = dp->d_ino;
@@ -134,13 +131,9 @@ streamsavedir (DIR *dirp, enum savedir_option option)
           else
             {
               if (allocated - used <= entry_size)
-                {
-                  size_t n = used + entry_size;
-                  if (n < used)
-                    xalloc_die ();
-                  name_space = x2nrealloc (name_space, &n, 1);
-                  allocated = n;
-                }
+                name_space = xpalloc (name_space, &allocated,
+                                      entry_size - (allocated - used),
+                                      IDX_MAX - 1, sizeof *name_space);
               memcpy (name_space + used, entry, entry_size);
             }
           used += entry_size;
-- 
2.30.2