du: handle bind-mounted directory cycles gracefully

Before this change, a directory cycle induced by a bind mount
would be treated as a fatal error, i.e., probable disk corruption.
However, such cycles are relatively common, and can be detected
efficiently, so now du emits a descriptive warning and arranges
to exit nonzero.

* NEWS (Bug fixes): Mention it.
* src/du.c: Include "mountlist.h".
(di_mnt): New global set.
(di_files): Rename global from di_set, now that there are two.
(fill_mount_table): New function.
(hash_ins): Add DI_SET parameter.
(process_file): Look up each dir dev/ino pair in the new set.
(main): Allocate, initialize, and free the new set.
* tests/du/bind-mount-dir-cycle: Add a test for the fix.
* tests/Makefile.am (TESTS): Add it.
* THANKS.in: Update.
This implements the proposal in http://bugs.gnu.org/11844.
Originally reported in http://bugs.debian.org/563254 by Alan Jenkins
and more recently as http://bugzilla.redhat.com/836557

Improved by: Jim Meyering

5 files changed, 113 insertions, 10 deletions

diff --git a/NEWS b/NEWS
index f7672d9e3..d8a47ab57 100644
--- a/NEWS
+++ b/NEWS
@@ -2,6 +2,13 @@ GNU coreutils NEWS                                    -*- outline -*-
 
 * Noteworthy changes in release ?.? (????-??-??) [?]
 
+** Bug fixes
+
+  du no longer emits a "disk-corrupted"-style diagnostic when it detects
+  a directory cycle that is due to a bind-mounted directory.  Instead,
+  it detects this precise type of cycle, diagnoses it as such and
+  eventually exits nonzero.
+
 
 * Noteworthy changes in release 8.19 (2012-08-20) [stable]
 
diff --git a/THANKS.in b/THANKS.in
index a73620171..ca22e155f 100644
--- a/THANKS.in
+++ b/THANKS.in
@@ -24,6 +24,7 @@ AIDA Shinra                         shinra@j10n.org
 Akim Demaille                       demaille@inf.enst.fr
 Alain Magloire                      alain@qnx.com
 Alan Iwi                            iwi@atm.ox.ac.uk
+Alan Jenkins                        alan-jenkins@tuffmail.co.uk
 Albert Chin-A-Young                 china@thewrittenword.com
 Albert Hopkins                      ahopkins@dynacare.com
 Alberto Accomazzi                   alberto@cfa0.harvard.edu
diff --git a/src/du.c b/src/du.c
index 733394126..ee90da9ba 100644
--- a/src/du.c
+++ b/src/du.c
@@ -35,6 +35,7 @@
 #include "exclude.h"
 #include "fprintftime.h"
 #include "human.h"
+#include "mountlist.h"
 #include "quote.h"
 #include "quotearg.h"
 #include "stat-size.h"
@@ -60,8 +61,12 @@ extern bool fts_debug;
 # define FTS_CROSS_CHECK(Fts)
 #endif
 
-/* A set of dev/ino pairs.  */
-static struct di_set *di_set;
+/* A set of dev/ino pairs to help identify files and directories
+   whose sizes have already been counted.  */
+static struct di_set *di_files;
+
+/* A set containing a dev/ino pair for each local mount point directory.  */
+static struct di_set *di_mnt;
 
 /* Keep track of the preceding "level" (depth in hierarchy)
    from one call of process_file to the next.  */
@@ -333,11 +338,11 @@ Mandatory arguments to long options are mandatory for short options too.\n\
   exit (status);
 }
 
-/* Try to insert the INO/DEV pair into the global table, HTAB.
+/* Try to insert the INO/DEV pair into DI_SET.
    Return true if the pair is successfully inserted,
-   false if the pair is already in the table.  */
+   false if the pair was already there.  */
 static bool
-hash_ins (ino_t ino, dev_t dev)
+hash_ins (struct di_set *di_set, ino_t ino, dev_t dev)
 {
   int inserted = di_set_insert (di_set, dev, ino);
   if (inserted < 0)
@@ -461,7 +466,7 @@ process_file (FTS *fts, FTSENT *ent)
       if (excluded
           || (! opt_count_all
               && (hash_all || (! S_ISDIR (sb->st_mode) && 1 < sb->st_nlink))
-              && ! hash_ins (sb->st_ino, sb->st_dev)))
+              && ! hash_ins (di_files, sb->st_ino, sb->st_dev)))
         {
           /* If ignoring a directory in preorder, skip its children.
              Ignore the next fts_read output too, as it's a postorder
@@ -490,7 +495,13 @@ process_file (FTS *fts, FTSENT *ent)
         case FTS_DC:
           if (cycle_warning_required (fts, ent))
             {
-              emit_cycle_warning (file);
+              /* If this is a mount point, then diagnose it and avoid
+                 the cycle.  */
+              if (di_set_lookup (di_mnt, sb->st_dev, sb->st_ino))
+                error (0, 0, _("mount point %s already traversed"),
+                       quote (file));
+              else
+                emit_cycle_warning (file);
               return false;
             }
           return true;
@@ -623,6 +634,37 @@ du_files (char **files, int bit_flags)
   return ok;
 }
 
+/* Fill the di_mnt set with local mount point dev/ino pairs.  */
+
+static void
+fill_mount_table (void)
+{
+  struct mount_entry *mnt_ent = read_file_system_list (false);
+  while (mnt_ent)
+    {
+      struct mount_entry *mnt_free;
+      if (!mnt_ent->me_remote && !mnt_ent->me_dummy)
+        {
+          struct stat buf;
+          if (!stat (mnt_ent->me_mountdir, &buf))
+            hash_ins (di_mnt, buf.st_ino, buf.st_dev);
+          else
+            {
+              /* Ignore stat failure.  False positives are too common.
+                 E.g., "Permission denied" on /run/user/<name>/gvfs.  */
+            }
+        }
+
+      mnt_free = mnt_ent;
+      mnt_ent = mnt_ent->me_next;
+
+      free (mnt_free->me_devname);
+      free (mnt_free->me_mountdir);
+      free (mnt_free->me_type);
+      free (mnt_free);
+    }
+}
+
 int
 main (int argc, char **argv)
 {
@@ -922,8 +964,15 @@ main (int argc, char **argv)
     xalloc_die ();
 
   /* Initialize the set of dev,inode pairs.  */
-  di_set = di_set_alloc ();
-  if (!di_set)
+
+  di_mnt = di_set_alloc ();
+  if (!di_mnt)
+    xalloc_die ();
+
+  fill_mount_table ();
+
+  di_files = di_set_alloc ();
+  if (!di_files)
     xalloc_die ();
 
   /* If not hashing everything, process_file won't find cycles on its
@@ -1001,7 +1050,8 @@ main (int argc, char **argv)
  argv_iter_done:
 
   argv_iter_free (ai);
-  di_set_free (di_set);
+  di_set_free (di_files);
+  di_set_free (di_mnt);
 
   if (files_from && (ferror (stdin) || fclose (stdin) != 0) && ok)
     error (EXIT_FAILURE, 0, _("error reading %s"), quote (files_from));
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 69078bdd2..acd816d6c 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -32,6 +32,7 @@ root_tests =					\
   cp/sparse-fiemap				\
   dd/skip-seek-past-dev				\
   df/problematic-chars				\
+  du/bind-mount-dir-cycle			\
   install/install-C-root			\
   ls/capability					\
   ls/nameless-uid				\
diff --git a/tests/du/bind-mount-dir-cycle b/tests/du/bind-mount-dir-cycle
new file mode 100755
index 000000000..8f9e197f9
--- /dev/null
+++ b/tests/du/bind-mount-dir-cycle
@@ -0,0 +1,44 @@
+#!/bin/sh
+# Exercise du's new ability to handle bind-mount-induced dir cycles.
+
+# Copyright (C) 2012 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/>.
+
+. "${srcdir=.}/init.sh"; path_prepend_ ../src
+print_ver_ rm
+require_root_
+
+cleanup_()
+{
+  # When you take the undesirable shortcut of making /etc/mtab a link
+  # to /proc/mounts, unmounting "$other_partition_tmpdir" would fail.
+  # So, here we unmount a/b instead.
+  umount a/b
+}
+
+mkdir -p a/b || framework_failure_
+mount --bind a a/b \
+  || skip_ "This test requires mount with a working --bind option."
+
+echo a > exp || framework_failure_
+echo "du: mount point 'a/b' already traversed" > exp-err || framework_failure_
+
+du a > out 2> err && fail=1
+sed 's/^[0-9][0-9]*	//' out > k && mv k out
+
+compare exp-err err || fail=1
+compare exp out || fail=1
+
+Exit $fail