Subject: bug#64316: [bug-diffutils] bug#64316: ASAN failures in dir.c

From: Paul Eggert <[email-masked]>
Date: Wed, 28 Jun 2023 15:31:55 -0700

On 2023-06-28 03:32, Gisle Vanem wrote:
> 'PTRDIFF_T_MAX - - 3' folds to '-9223372036854775806'.
> 
> But how can 'linbuf_base' become negative?

Ordinarily it's zero, but it can be negative. It's never positive.

Thanks for the report. I reproduced the signed integer overflow issue 
with -fsanitize=undefined and installed the attached patch to fix it and 
add a regression test (and also a comment about linbuf_base).

Although I don't see how this would fix a "memory exhausted" error, 
please give the latest Git commit a try and see whether it fixes things 
for you.

From 359b8c3ef28c6439ff9438e8e9fe8b45b50e1408 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Wed, 28 Jun 2023 14:08:14 -0700
Subject: [PATCH] diff: fix xpalloc-related signed integer overflow

Problem reported by Gisle Vanem <https://bugs.gnu.org/64316>.
* src/io.c (find_and_hash_each_line):
Rely on xpalloc to check for integer overflow instead
of trying to do it ourselves incorrectly, with old code
that predated the use of xpalloc.
* src/system.h: Verify that LIN_MAX == IDX_MAX,
since the code now relies on this.
* tests/Makefile.am (TESTS): Add bug-64316.
* tests/bug-64316: New file
---
 src/diff.h        |  8 ++++----
 src/io.c          | 12 +++---------
 src/system.h      |  2 +-
 tests/Makefile.am |  1 +
 tests/bug-64316   | 31 +++++++++++++++++++++++++++++++
 5 files changed, 40 insertions(+), 14 deletions(-)
 create mode 100755 tests/bug-64316

diff --git a/src/diff.h b/src/diff.h
index ec39b73..b52c1f5 100644
--- a/src/diff.h
+++ b/src/diff.h
@@ -288,10 +288,10 @@ struct file_data {
     /* Array of pointers to lines in the file.  */
     char const **linbuf;
 
-    /* linbuf_base <= buffered_lines <= valid_lines <= alloc_lines.
-       linebuf[linbuf_base ... buffered_lines - 1] are possibly differing.
-       linebuf[linbuf_base ... valid_lines - 1] contain valid data.
-       linebuf[linbuf_base ... alloc_lines - 1] are allocated.  */
+    /* linbuf_base <= 0 <= buffered_lines <= valid_lines <= alloc_lines.
+       linbuf[0 ... buffered_lines - 1] are possibly differing.
+       linbuf[linbuf_base ... valid_lines - 1] contain valid data.
+       linbuf[linbuf_base ... alloc_lines - 1] are allocated.  */
     lin linbuf_base, buffered_lines, valid_lines, alloc_lines;
 
     /* Pointer to end of prefix of this file to ignore when hashing.  */
diff --git a/src/io.c b/src/io.c
index 1851c9a..7fb30f4 100644
--- a/src/io.c
+++ b/src/io.c
@@ -381,9 +381,7 @@ find_and_hash_each_line (struct file_data *current)
             /* Create a new equivalence class in this bucket.  */
             i = eqs_index++;
             if (i == eqs_alloc)
-	      eqs = xpalloc (eqs, &eqs_alloc, 1,
-			     LIN_MAX < PTRDIFF_MAX ? LIN_MAX : -1,
-			     sizeof *eqs);
+	      eqs = xpalloc (eqs, &eqs_alloc, 1, -1, sizeof *eqs);
             eqs[i].next = *bucket;
             eqs[i].hash = h;
             eqs[i].line = ip;
@@ -417,13 +415,10 @@ find_and_hash_each_line (struct file_data *current)
       /* Maybe increase the size of the line table.  */
       if (line == alloc_lines)
         {
-	  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 = xpalloc (linbuf, &n, 1, eqs_max - linbuf_base,
-			    sizeof *linbuf);
+	  linbuf = xpalloc (linbuf, &n, 1, -1, sizeof *linbuf);
           linbuf -= linbuf_base;
 	  alloc_lines = linbuf_base + n;
           cureqs = xirealloc (cureqs, alloc_lines * sizeof *cureqs);
@@ -445,8 +440,7 @@ find_and_hash_each_line (struct file_data *current)
 	  /* 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 = xpalloc (linbuf, &n, 1, -1, sizeof *linbuf);
 	  linbuf -= linbuf_base;
 	  alloc_lines = n - linbuf_base;
         }
diff --git a/src/system.h b/src/system.h
index c633a25..32d680d 100644
--- a/src/system.h
+++ b/src/system.h
@@ -129,7 +129,7 @@ typedef struct incomplete *word;
 typedef ptrdiff_t lin;
 #define LIN_MAX PTRDIFF_MAX
 #define pI "t"
-verify (LIN_MAX <= IDX_MAX);
+verify (LIN_MAX == IDX_MAX);
 
 /* This section contains POSIX-compliant defaults for macros
    that are meant to be overridden by hand in config.h as needed.  */
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 79bacfb..db757bd 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -5,6 +5,7 @@ TESTS = \
   bignum \
   binary \
   brief-vs-stat-zero-kernel-lies \
+  bug-64316 \
   cmp \
   colliding-file-names \
   diff3 \
diff --git a/tests/bug-64316 b/tests/bug-64316
new file mode 100755
index 0000000..2c1331c
--- /dev/null
+++ b/tests/bug-64316
@@ -0,0 +1,31 @@
+#!/bin/sh
+# Test for signed integer overflow bug within diff.
+# Bug reported by Gisele Vanem <http://bugs.gnu.org/64316>.
+# Compile with gcc -fsanitize=undefined to test for this bug.
+
+. "${srcdir=.}/init.sh"; path_prepend_ ../src
+
+fail=0
+
+for f in a b; do
+  printf 'c\nd\ne\nf\ng\n%s\nh\ni\nj\nk\nl\n' $f >$f || framework_failure_
+done
+
+cat >exp <<'EOF' || framework_failure_
+@@ -3,7 +3,7 @@
+ e
+ f
+ g
+-a
++b
+ h
+ i
+ j
+EOF
+
+returns_ 1 diff -u a b >out 2>err || fail=1
+sed '1,2d' out >out1 || framework_failure_
+compare exp out1 || fail=1
+compare /dev/null err || fail=1
+
+Exit $fail
-- 
2.39.2