sed: fix infloop with symlink cycles

* bootstrap.conf (gnulib_modules):
Add eloop-threshold, idx, minmax, readlink.
* configure.ac: Do not check for lstat; no longer needed.
(ENABLE_FOLLOW_SYMLINKS): Remove; all uses removed.
(TEST_SYMLINKS): Depend only on readlink.
* sed/utils.c: Include eloop-threshold.h, idx.h, minmax.h.
(SSIZE_IDX_MAX): New macro.
(follow_symlink): Rewrite to not loop when given a symlink cycle.
Do not use lstat, since readlink suffices.  Use just one memory
buffer, not two; this simplifies memory management.
* testsuite/follow-symlinks.sh: Adjust diagnostics to
to match revised behavior.  Test for symlink loops.

6 files changed, 87 insertions, 66 deletions

diff --git a/NEWS b/NEWS
index e7996b3..bdabc68 100644
--- a/NEWS
+++ b/NEWS
@@ -4,6 +4,10 @@ GNU sed NEWS                                    -*- outline -*-
 
 ** Bug fixes
 
+  'sed --follow-symlinks -i' no longer loops forever when its operand
+  is a symbolic link cycle.
+  [bug introduced in sed 4.2]
+
   a program with an execution line longer than 2GB can no longer trigger
   an out-of-bounds memory write.
 
diff --git a/bootstrap.conf b/bootstrap.conf
index 9285bd6..ea5c2f9 100644
--- a/bootstrap.conf
+++ b/bootstrap.conf
@@ -29,12 +29,14 @@ btowc
 c-ctype
 closeout
 dfa
+eloop-threshold
 extensions
 fwriting
 getdelim
 gettext-h
 git-version-gen
 gitlog-to-changelog
+idx
 ignore-value
 localcharset
 manywarnings
@@ -43,10 +45,12 @@ mbrtowc
 mbsinit
 memchr
 memrchr
+minmax
 mkostemp
 obstack
 perl
 progname
+readlink
 readme-release
 regex
 rename
diff --git a/configure.ac b/configure.ac
index cfea826..62aad18 100644
--- a/configure.ac
+++ b/configure.ac
@@ -117,16 +117,11 @@ AC_TYPE_SIZE_T
 AM_GNU_GETTEXT_VERSION([0.19.2])
 AM_GNU_GETTEXT([external])
 
-AC_CHECK_FUNCS_ONCE(isatty isascii memcpy strchr strtoul lstat readlink
+AC_CHECK_FUNCS_ONCE(isatty isascii memcpy strchr strtoul readlink
                     popen pathconf fchown fchmod setlocale)
 
-# Check whether we are able to follow symlinks
-if test "$ac_cv_func_lstat:$ac_cv_func_readlink" = yes:yes; then
-   AC_DEFINE([ENABLE_FOLLOW_SYMLINKS], ,
-             [Follow symlinks when processing in place])
-fi
 AM_CONDITIONAL([TEST_SYMLINKS],
-          [test "$ac_cv_func_lstat:$ac_cv_func_readlink" = yes:yes])
+          [test "$ac_cv_func_readlink" = yes])
 
 AC_ARG_ENABLE(i18n,
 [  --disable-i18n          disable internationalization (default=enabled)], ,
diff --git a/sed/sed.c b/sed/sed.c
index 42c6a1f..af83065 100644
--- a/sed/sed.c
+++ b/sed/sed.c
@@ -143,7 +143,7 @@ Usage: %s [OPTION]... {script-only-if-no-other-script} [input-file]...\n\
   fprintf (out, _("  -f script-file, --file=script-file\n\
                  add the contents of script-file to the commands" \
                  " to be executed\n"));
-#ifdef ENABLE_FOLLOW_SYMLINKS
+#ifdef HAVE_READLINK
   fprintf (out, _("  --follow-symlinks\n\
                  follow symlinks when processing in place\n"));
 #endif
@@ -212,7 +212,7 @@ main (int argc, char **argv)
     {"unbuffered", 0, NULL, 'u'},
     {"version", 0, NULL, 'v'},
     {"help", 0, NULL, 'h'},
-#ifdef ENABLE_FOLLOW_SYMLINKS
+#ifdef HAVE_READLINK
     {"follow-symlinks", 0, NULL, 'F'},
 #endif
     {NULL, 0, NULL, 0}
diff --git a/sed/utils.c b/sed/utils.c
index 823de8d..4bd6587 100644
--- a/sed/utils.c
+++ b/sed/utils.c
@@ -27,12 +27,21 @@
 #include <limits.h>
 
 #include "binary-io.h"
+#include "eloop-threshold.h"
+#include "idx.h"
+#include "minmax.h"
 #include "unlocked-io.h"
 #include "utils.h"
 #include "progname.h"
 #include "fwriting.h"
 #include "xalloc.h"
 
+#ifdef SSIZE_MAX
+# define SSIZE_IDX_MAX MIN (SSIZE_MAX, IDX_MAX)
+#else
+# define SSIZE_IDX_MAX IDX_MAX
+#endif
+
 #if O_BINARY
 extern bool binary_mode;
 #endif
@@ -304,83 +313,88 @@ do_ck_fclose (FILE *fp, char const *name)
     panic ("couldn't close %s: %s", name, strerror (errno));
 }
 
-/* Follow symlink and panic if something fails.  Return the ultimate
-   symlink target, stored in a temporary buffer that the caller should
-   not free.  */
+/* Follow symlink FNAME and return the ultimate target, stored in a
+   temporary buffer that the caller should not free.  Return FNAME if
+   it is not a symlink.  Panic if a symlink loop is found.  */
 const char *
 follow_symlink (const char *fname)
 {
-#ifdef ENABLE_FOLLOW_SYMLINKS
-  static char *buf1, *buf2;
-  static int buf_size;
+  /* The file name, as adjusted so far by replacing symlinks with
+     their contents.  Only the last file name component is replaced,
+     as we need not do all the work of realpath.  */
 
-  struct stat statbuf;
-  const char *buf = fname, *c;
-  int rc;
+  /* FIXME: We should get a file descriptor on the parent directory,
+     to avoid resolving that directory name more than once (which can
+     lead to races).  Perhaps someday the Gnulib 'supersede' module
+     can get a function openat_supersede that will do this for us.  */
+  char const *fn = fname;
 
-  if (buf_size == 0)
-    {
-      buf1 = xzalloc (PATH_MAX + 1);
-      buf2 = xzalloc (PATH_MAX + 1);
-      buf_size = PATH_MAX + 1;
-    }
+#ifdef HAVE_READLINK
+  static char *buf;
+  static idx_t buf_size;
+
+  idx_t buf_used = 0;
 
-  while ((rc = lstat (buf, &statbuf)) == 0
-         && (statbuf.st_mode & S_IFLNK) == S_IFLNK)
+  for (idx_t num_links = 0; ; num_links++)
     {
-      if (buf == buf2)
+      ssize_t linklen;
+      idx_t newlen;
+      char const *c;
+
+      /* Put symlink contents into BUF + BUF_USED.  */
+      while ((linklen = (buf_used < buf_size
+                         ? readlink (fn, buf + buf_used, buf_size - buf_used)
+                         : 0))
+             == buf_size)
         {
-          strcpy (buf1, buf2);
-          buf = buf1;
+          buf = xpalloc (buf, &buf_size, 1, SSIZE_IDX_MAX, 1);
+          if (num_links)
+            fn = buf;
         }
-
-      while ((rc = readlink (buf, buf2, buf_size)) == buf_size)
+      if (linklen < 0)
         {
-          buf_size *= 2;
-          buf1 = xrealloc (buf1, buf_size);
-          buf2 = xrealloc (buf2, buf_size);
+          if (errno == EINVAL)
+            break;
+          panic (_("couldn't readlink %s: %s"), fn, strerror (errno));
         }
-      if (rc < 0)
-        panic (_("couldn't follow symlink %s: %s"), buf, strerror (errno));
-      else
-        buf2 [rc] = '\0';
+      if (__eloop_threshold () <= num_links)
+        panic (_("couldn't follow symlink %s: %s"), fname, strerror (ELOOP));
 
-      if (buf2[0] != '/' && (c = strrchr (buf, '/')) != NULL)
+      if ((linklen == 0 || buf[buf_used] != '/') && (c = strrchr (fn, '/')))
         {
-          /* Need to handle relative paths with care.  Reallocate buf1 and
-             buf2 to be big enough.  */
-          int len = c - buf + 1;
-          if (len + rc + 1 > buf_size)
+          /* A relative symlink not from the working directory.
+             Make sure BUF is big enough.  */
+          idx_t dirlen = c - fn + 1;
+          newlen = dirlen + linklen;
+          if (buf_size <= newlen)
             {
-              buf_size = len + rc + 1;
-              buf1 = xrealloc (buf1, buf_size);
-              buf2 = xrealloc (buf2, buf_size);
+              buf = xpalloc (buf, &buf_size, newlen + 1 - buf_size,
+                             SSIZE_IDX_MAX, 1);
+              if (num_links)
+                fn = buf;
             }
 
-          /* Always store the new path in buf1.  */
-          if (buf != buf1)
-            memcpy (buf1, buf, len);
-
-          /* Tack the relative symlink at the end of buf1.  */
-          memcpy (buf1 + len, buf2, rc + 1);
-          buf = buf1;
+          /* Store the new file name in BUF.  Beware overlap.  */
+          memmove (buf + dirlen, buf + buf_used, linklen);
+          if (fn != buf)
+            memcpy (buf, fn, dirlen);
         }
       else
         {
-          /* Use buf2 as the buffer, it saves a strcpy if it is not pointing to
-             another link.  It works for absolute symlinks, and as long as
-             symlinks do not leave the current directory.  */
-           buf = buf2;
+          /* A symlink to an absolute file name, or a relative symlink
+             from the working directory.  The new file name is simply
+             the symlink contents.  */
+          memmove (buf, buf + buf_used, linklen);
+          newlen = linklen;
         }
-    }
 
-  if (rc < 0)
-    panic (_("cannot stat %s: %s"), buf, strerror (errno));
+      buf[newlen] = '\0';
+      buf_used = newlen + 1;
+      fn = buf;
+    }
+#endif
 
-  return buf;
-#else
-  return fname;
-#endif /* ENABLE_FOLLOW_SYMLINKS */
+  return fn;
 }
 
 /* Panic on failing rename */
diff --git a/testsuite/follow-symlinks.sh b/testsuite/follow-symlinks.sh
index 9066876..880a80e 100644
--- a/testsuite/follow-symlinks.sh
+++ b/testsuite/follow-symlinks.sh
@@ -52,9 +52,9 @@ sed --follow-symlinks -n 'F' la1 la2 > out-two-symlinks || fail=1
 compare_ exp-two-symlinks out-two-symlinks || fail=1
 
 # non-existing input with --follow-symlink
-# implementation note: lstat() will be called before open(), thus 'cannot stat'.
+# implementation note: readlink called before open, thus "couldn't readlink"
 cat <<\EOF >exp-stat || framework_failure_
-sed: cannot stat badfile:
+sed: couldn't readlink badfile:
 EOF
 returns_ 4 sed --follow-symlinks 'F' badfile >/dev/null 2>err-stat || fail=1
 
@@ -69,4 +69,8 @@ echo "$PWD/a" > exp-la-abs || framework_failure_
 sed -n --follow-symlinks 'F' la-abs > out-la-abs || fail=1
 compare_ exp-la-abs out-la-abs || fail=1
 
+# symlink loop
+ln -s la-loop la-loop || framework_failure_
+sed --follow-symlinks -i s/a/b/ la-loop && fail=1
+
 Exit $fail