Subject: bug#76613: [bug-diffutils] bug#76613: bug#76613: diff -y crashes with apparent memory corruption

From: Collin Funk <[email-masked]>
Date: Thu, 27 Feb 2025 20:35:57 -0800

Hi Paul,

Paul Eggert <[email-masked]> writes:

> Thanks for the bug report. I can reproduce it with gcc
> -fsanitize=address on Ubuntu 24.10 x86-64. I plan to take a look at it
> soon.

I see -fsanitize=address and valgrind fail this test starting at this
commit f54e901c329ba7b7d98ecae2571712f43444c2bd:

    maint: use xpalloc    
    * bootstrap.conf (gnulib_modules): Add ialloc, to document
    the now-direct dependency.
    * src/diff.c (add_regexp):
    * src/diff3.c (read_diff):
    * src/dir.c (dir_read):
    * src/io.c (slurp, find_and_hash_each_line, find_identical_ends):
    * src/sdiff.c (diffarg):
    Prefer xpalloc to doing it by hand.
    * src/io.c: Include ialloc.h, for irealloc.
    (equivs_alloc): Now idx_t, not lin, for xpalloc.
    (sip): Don’t bother subtracting 2 * sizeof (word) from the
    buffer_lcm upper bound, as later code works anyway now.
    (slurp): Simplify buffer allocation so that xpalloc can be used.
    Use irealloc for speculative reallocation, since the code could
    work anyway if the irealloc fails.  Use current->eof to check
    for EOF, rather than the less-intuitive buffer size checks.

The previous commit passes it. Here are the relevant lines:

@@ -419,17 +411,16 @@ find_and_hash_each_line (struct file_data *current)
       /* Maybe increase the size of the line table.  */
       if (line == alloc_lines)
         {
-          /* Double (alloc_lines - linbuf_base) by adding to alloc_lines.  */
-          if (IDX_MAX / 3 <= alloc_lines
-              || IDX_MAX / sizeof *cureqs <= 2 * alloc_lines - linbuf_base
-              || IDX_MAX / sizeof *linbuf <= alloc_lines - linbuf_base)
-            xalloc_die ();
-          alloc_lines = 2 * alloc_lines - linbuf_base;
-          cureqs = xirealloc (cureqs, alloc_lines * sizeof *cureqs);
+         idx_t eqs_max = MIN (LIN_MAX, IDX_MAX / sizeof *cureqs);
+
+         /* Grow (alloc_lines - linbuf_base) by adding to alloc_lines.  */
+         idx_t n = alloc_lines - linbuf_base;
           linbuf += linbuf_base;
-          linbuf = xirealloc (linbuf,
-                             (alloc_lines - linbuf_base) * sizeof *linbuf);
+         linbuf = xpalloc (linbuf, &n, 1, eqs_max - linbuf_base,
+                           sizeof *linbuf);
           linbuf -= linbuf_base;
+         alloc_lines = linbuf_base + n;
+          cureqs = xirealloc (cureqs, alloc_lines * sizeof *cureqs);
         }
       linbuf[line] = ip;
       cureqs[line] = i;
@@ -445,16 +436,13 @@ find_and_hash_each_line (struct file_data *current)
          so that we can compute the length of any buffered line.  */
       if (line == alloc_lines)
         {
-          /* Double (alloc_lines - linbuf_base) by adding to alloc_lines.  */
-          if (IDX_MAX / 3 <= alloc_lines
-              || IDX_MAX / sizeof *cureqs <= 2 * alloc_lines - linbuf_base
-              || IDX_MAX / sizeof *linbuf <= alloc_lines - linbuf_base)
-            xalloc_die ();
-          alloc_lines = 2 * alloc_lines - linbuf_base;
-          linbuf += linbuf_base;
-          linbuf = xirealloc (linbuf,
-                             (alloc_lines - linbuf_base) * sizeof *linbuf);
-          linbuf -= linbuf_base;
+         /* Grow (alloc_lines - linbuf_base) by adding to alloc_lines.  */
+         idx_t n = alloc_lines - linbuf_base;
+         linbuf += linbuf_base;
+         linbuf = xpalloc (linbuf, &n, 1, MAX (0, IDX_MAX - linbuf_base),
+                           sizeof *linbuf);
+         linbuf -= linbuf_base;
+         alloc_lines = n - linbuf_base;
         }
       linbuf[line] = p;

In the original version alloc_lines is calculated as
2 * alloc_lines - linbuf_base in both hunks. Afterwards it is
linbuf_base + n in one section and n - linbuf_base in the other.

I've attached a patch that satisfies sanitizers, but maybe I am missing
something in this code...

Collin

>From 03e529dd69d50c247a217b9b659659538dfa397a Mon Sep 17 00:00:00 2001
From: Collin Funk <[email-masked]>
Date: Thu, 27 Feb 2025 20:15:55 -0800
Subject: [PATCH] diff: fix allocation size computation that could cause bad
 writes

Reported by Nick Smallbone <[email-masked]> in:
<https://lists.gnu.org/r/bug-diffutils/2025-02/msg00012.html>.

* src/io.c (find_and_hash_each_line): Fix size computation.
---
 src/io.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/io.c b/src/io.c
index a62c529..adb4f50 100644
--- a/src/io.c
+++ b/src/io.c
@@ -1012,7 +1012,7 @@ find_and_hash_each_line (struct file_data *current)
 	  linbuf += linbuf_base;
 	  linbuf = xpalloc (linbuf, &n, 1, -1, sizeof *linbuf);
 	  linbuf -= linbuf_base;
-	  alloc_lines = n - linbuf_base;
+          alloc_lines = linbuf_base + n;
         }
       linbuf[line] = p;
 
-- 
2.48.1