[PATCH] Silently lower nmerge; don't (sometimes incorrectly) range-check it.

[Paul Eggert]

Here's a patch written by:

Paul Eggert <address@hidden>
Nima Nikzad <address@hidden>
Max Chang <address@hidden>
Alexander Nguyen <address@hidden>
Sahil Amoli <address@hidden>
Nick Graham <address@hidden>

This patch fixes a bug in 'sort' where it incorrectly deduces the number
of available file descriptors by doing the equivalent of 'ulimit -n'.
This method is incorrect, since many file descriptors could already be
open, eating into the maximum available.

I'm not quite up to speed on how you want ChangeLog entries formatted
for submissions by so many authors, but there are papers on file for all
these authors.

One other thing: we have another team who has drafted a different patch
for this problem, which I'll send soon.  You may want to wait until you
see that one as well; I'll compare the two patches when I send out the
message about the other patch.

-----

* doc/coreutils.texi (sort invocation): Document that we now silently
lower nmerge if necessary.

* src/sort.c (OPEN_MAX): Remove; no longer needed.
(specify_nmerge): Don't use getrlimit, as the value it returns (max
value "open" can return) is not the value that we want (how many file
descriptors can we open?).  Instead, just check for outlandish values;
later on, we'll lower it.
(lower_nmerge_if_necessary): New function.
(main): Call it.

* tests/Makefile.am (@Tests): Added new 'sort-merge-fdlimit' test case.

* tests/misc/sort-merge (@Tests): Adjust to new behavior: 'sort' no
longer looks at ulimit and no longer reports that (misleading) value
to user.

* tests/misc/sort-merge-fdlimit (@Tests): New file.
---
 doc/coreutils.texi            |   14 ++++--
 src/sort.c                    |   98 +++++++++++++++++++++++-----------------
 tests/Makefile.am             |    1 +
 tests/misc/sort-merge         |    3 +-
 tests/misc/sort-merge-fdlimit |   54 ++++++++++++++++++++++
 5 files changed, 121 insertions(+), 49 deletions(-)
 create mode 100644 tests/misc/sort-merge-fdlimit

diff --git a/doc/coreutils.texi b/doc/coreutils.texi
index 2c1fae5..5478fc2 100644
--- a/doc/coreutils.texi
+++ b/doc/coreutils.texi
@@ -3937,13 +3937,17 @@ and I/0.  Conversely a small value of @var{nmerge} may 
reduce memory
 requirements and I/0 at the expense of temporary storage consumption and
 merge performance.
 
-The value of @var{nmerge} must be at least 2.
+The value of @var{nmerge} must be at least 2.  The default value is
+currently 16, but this is implementation-dependent and may change in
+the future.
 
 The value of @var{nmerge} may be bounded by a resource limit for open
-file descriptors.  Try @samp{ulimit -n} or @samp{getconf OPEN_MAX} to
-to display the limit for a particular system.
-If the value of @var{nmerge} exceeds this limit, then @command{sort} will
-issue a warning to standard error and exit with a nonzero status.
+file descriptors.  The commands @samp{ulimit -n} or @samp{getconf
+OPEN_MAX} may display limits for your systems; these limits may be
+modified further if your program already has some files open, or if
+the operating system has other limits on the number of open files.  If
+the value of @var{nmerge} exceeds the resource limit, @command{sort}
+silently uses a smaller value.
 
 @item -o @var{output-file}
 @itemx address@hidden
diff --git a/src/sort.c b/src/sort.c
index 7b0b064..98aecf4 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -76,13 +76,6 @@ struct rlimit { size_t rlim_cur; };
 # endif
 #endif
 
-#if !defined OPEN_MAX && defined NR_OPEN
-# define OPEN_MAX NR_OPEN
-#endif
-#if !defined OPEN_MAX
-# define OPEN_MAX 20
-#endif
-
 #define UCHAR_LIM (UCHAR_MAX + 1)
 
 #ifndef DEFAULT_TMPDIR
@@ -1102,53 +1095,72 @@ static void
 specify_nmerge (int oi, char c, char const *s)
 {
   uintmax_t n;
-  struct rlimit rlimit;
   enum strtol_error e = xstrtoumax (s, NULL, 10, &n, NULL);
 
-  /* Try to find out how many file descriptors we'll be able
-     to open.  We need at least nmerge + 3 (STDIN_FILENO,
-     STDOUT_FILENO and STDERR_FILENO). */
-  unsigned int max_nmerge = ((getrlimit (RLIMIT_NOFILE, &rlimit) == 0
-                             ? rlimit.rlim_cur
-                             : OPEN_MAX)
-                            - 3);
-
   if (e == LONGINT_OK)
     {
       nmerge = n;
-      if (nmerge != n)
+      if (nmerge != n || INT_MAX - 1 < nmerge)
        e = LONGINT_OVERFLOW;
-      else
-       {
-         if (nmerge < 2)
-           {
-             error (0, 0, _("invalid --%s argument %s"),
-                    long_options[oi].name, quote(s));
-             error (SORT_FAILURE, 0,
-                    _("minimum --%s argument is %s"),
-                    long_options[oi].name, quote("2"));
-           }
-         else if (max_nmerge < nmerge)
-           {
-             e = LONGINT_OVERFLOW;
-           }
-         else
-           return;
-       }
     }
 
-  if (e == LONGINT_OVERFLOW)
+  if (e != LONGINT_OK)
+    {
+      if (e == LONGINT_OVERFLOW)
+       error (SORT_FAILURE, 0, _("--%s argument %s too large"),
+              long_options[oi].name, quote(s));
+      xstrtol_fatal (e, oi, c, long_options, s);
+    }
+
+  if (nmerge < 2)
     {
-      char max_nmerge_buf[INT_BUFSIZE_BOUND (unsigned int)];
-      error (0, 0, _("--%s argument %s too large"),
+      error (0, 0, _("invalid --%s argument %s"),
             long_options[oi].name, quote(s));
       error (SORT_FAILURE, 0,
-            _("maximum --%s argument with current rlimit is %s"),
-            long_options[oi].name,
-            uinttostr (max_nmerge, max_nmerge_buf));
+            _("minimum --%s argument is %s"),
+            long_options[oi].name, quote("2"));
     }
-  else
-    xstrtol_fatal (e, oi, c, long_options, s);
+}
+
+/* Lower NMERGE if necessary, to fit within operating system limits.  */
+static void
+lower_nmerge_if_necessary (void)
+{
+  /* How many file descriptors are needed per input and output file.  */
+  int fds_per_file = (compress_program ? 3 : 1);
+
+  /* How many file descriptors we think we'll need, total.  It
+     obviously can't exceed INT_MAX.  */
+  int fds_needed = (nmerge <= INT_MAX / fds_per_file - 1
+                   ? (nmerge + 1) * fds_per_file
+                   : INT_MAX);
+
+  int *fd = xnmalloc (fds_needed, sizeof *fd);
+  int fds = 0;
+
+  /* Find out how many file descriptors we actually can create, and set
+     NMERGE accordingly.  */
+
+  int nmerge_val = 0;
+
+  if (pipe (fd) == 0)
+    {
+      for (fds = 2; fds < fds_needed; fds++)
+       {
+         fd[fds] = dup (fd[0]);
+         if (fd[fds] < 0)
+           break;
+       }
+      nmerge_val = fds / fds_per_file - 1;
+    }
+
+  if (nmerge_val < 2)
+    error (SORT_FAILURE, EMFILE, _("cannot merge"));
+  nmerge = nmerge_val;
+
+  while (0 <= --fds)
+    close (fd[fds]);
+  free (fd);
 }
 
 /* Specify the amount of main memory to use when sorting.  */
@@ -3381,6 +3393,8 @@ main (int argc, char **argv)
       files = &minus;
     }
 
+  lower_nmerge_if_necessary ();
+
   /* Need to re-check that we meet the minimum requirement for memory
      usage with the final value for NMERGE. */
   if (0 < sort_size)
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 07e9473..bb2aaad 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -202,6 +202,7 @@ TESTS =                                             \
   misc/sort-compress                           \
   misc/sort-files0-from                                \
   misc/sort-merge                              \
+  misc/sort-merge-fdlimit                      \
   misc/sort-rand                               \
   misc/sort-version                            \
   misc/split-a                                 \
diff --git a/tests/misc/sort-merge b/tests/misc/sort-merge
index e360d1c..f11ac1a 100755
--- a/tests/misc/sort-merge
+++ b/tests/misc/sort-merge
@@ -57,8 +57,7 @@ my @Tests =
 
      ['nmerge-big', "-m --batch-size=$bigint", @inputs,
        {ERR_SUBST=>'s/(current rlimit is) \d+/$1/'},
-        {ERR=>"$prog: --batch-size argument `$bigint' too large\n".
-             "$prog: maximum --batch-size argument with current rlimit is\n"},
+        {ERR=>"$prog: --batch-size argument `$bigint' too large\n"},
         {EXIT=>2}],
 
      # This should work since nmerge >= the number of input files
diff --git a/tests/misc/sort-merge-fdlimit b/tests/misc/sort-merge-fdlimit
new file mode 100644
index 0000000..82305be
--- /dev/null
+++ b/tests/misc/sort-merge-fdlimit
@@ -0,0 +1,54 @@
+#!/bin/sh
+# Test whether sort avoids opening more file descriptors than it is
+# allowed when merging files.
+
+# Copyright (C) 2009 Free Software Foundation, Inc.
+
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+if test "$VERBOSE" = yes; then
+  set -x
+  sort --version
+fi
+
+. $srcdir/test-lib.sh
+require_ulimit_
+
+mkdir in err || framework_failure
+
+fail=0
+
+for i in `seq 17`; do
+  echo $i >in/$i
+done
+
+# When these tests are run inside the automated testing framework, they
+# have one less available file descriptor than when run outside the
+# automated testing framework. If a test with a batch size of b fails
+# inside the ATF, then the same test with batch size b+1 may pass outside
+# the ATF but fail inside it.
+
+# The default batch size (nmerge) is 16.
+(ulimit -n 19 \
+   && sort -m --batch-size=16 in/* 2>err/merge-default-err \
+   || ! grep "open failed" err/merge-default-err) || fail=1
+
+# If sort opens a file (/dev/urandom) to sort by random hashes of keys,
+# it needs to consider this file against its limit on open file
+# descriptors.
+(ulimit -n 20 \
+   && sort -mR --batch-size=16 in/* 2>err/merge-random-err \
+   || ! grep "open failed" err/merge-random-err) || fail=1
+
+Exit $fail
-- 
1.5.4.3