making GNU ls -i (--inode) work around the linux readdir bug

[Jim Meyering]

With a Linux-based kernel, GNU ls -i can list the wrong inode
for a mount point.

Ian Jackson raised this issue two years ago with
http://bugs.debian.org/369822, and Wayne Pollock reported it
last week via http://bugzilla.redhat.com/453709

FYI, now, I'm planning to make GNU ls work around what may be a
Linux kernel bug.

I admit I did consider simply turning off the optimization that allows
"ls -i" to print inode numbers without calling stat on systems with
usable d_ino data, but that would be contrary to my philosophy of "don't
compromise quality on working systems to accommodate bugs on others".
The difference here is that Linux-based systems are the ones that must
be penalized for the sake of correctness.

The plan is to test each non-root mount point at configure time by
running a C program that calls readdir and lstat and compares the
resulting inode numbers.  If they ever mismatch, or the test fails
for any other reason, disable the "optimization" whereby ls.c relies
on readdir's POSIX-specified d_ino value rather than calling "lstat"
for each directory entry.  Note that this applies only to "implicit"
arguments, i.e., not to names listed on the ls command-line.

This test would run only on a Linux kernel-using system, and would
probably require a timeout, in case stat'ing mount points takes too long.

The first step is to get a list of mount points, excluding /.
If GNU df is available, use it.  Otherwise, use a default list
of directory names (or maybe just use mountlist.c):

default_mount_points='
/boot
/dev/shm
/home
/tmp
/usr
/usr/local
/usr/tmp
/var
/var/tmp
'
mount_points=$(df -P 2>&1 | sed -n 's,.*[0-9]% \(/.\),\1,p')
test -z "$mount_points" \
  && mount_points=$default_mount_points

Wanting to test for this once it's fixed, I wrote the following shell
code (this will become a test script).  Of course, we can't use such a
check from configure.  I did consider a sort of bootstrap phase, where
after building ls as usual, something would run shell code like this
using just-built binaries, then change some header file to reflect the
result and recompile ls, but that is too ugly, and wouldn't work in a
cross-compiling environment.

# Given e.g., /dev/shm, produce the list of GNU ls options that
# let us list just that entry using readdir data from its parent:
# ls -i -I '[^s]*' -I 's[^h]*' -I 'sh[^m]*' -I 'shm?*' -I '.?*' \
# -I '?' -I '??' /dev

ls_ignore_options()
{
  local name=$1
  local opts="-I '.?*' -I '$name?*'"
  while :; do
    local glob=$(echo "$name"|sed 's/\(.*\)\(.\)$/\1[^\2]*/')
    opts="$opts -I '$glob'"
    name=$(echo "$name"|sed 's/.$//')
    test -z "$name" && break
    glob=$(echo "$name"|sed 's/./?/g')
    opts="$opts -I '$glob'"
  done
  echo "$opts"
}

inode_via_readdir()
{
  local t=$1
  local base=$(basename $t)
  case $base in
    .*) skip_test_ 'pwd component starts with "."' ;;
    *[*?]*) skip_test_ 'pwd component contains "?" or "*"' ;;
  esac
  local opts=$(ls_ignore_options "$base")
  local parent_dir=$(dirname $t)
  eval "ls -i $opts $parent_dir" | sed 's/ .*//'
}

for dir in $(echo $mount_points); do
  test "$(inode_via_readdir $dir)" = $(env stat --format=%i $dir) || fail=1
done

===========================================
Here's an outline of how the configure-time run test would work:

if cross-compiling; then
  if linux (adding a version-based test if/when it's fixed)
    assume have_working_readdir_vs_mount_points=no
  else
    have_working_readdir_vs_mount_points=yes
else
  gl_CHECK_TYPE_STRUCT_DIRENT_D_INO
  if test $gl_cv_struct_dirent_d_ino = yes; then
    perform run-test using the C code below, with $mount_points as arguments
fi


================================
Here's the C program that will probably end up in the configure-time
run-test (it includes slightly massaged copies of basename.c and
dirname.c -- I'll probably adjust it to use actual e.g.,
#include "basename.c" statements instead):

cat <<\EOF > readdir-inode.c
/* Test a list of file names for the Linux readdir/mount-point bug.
   If for any name, the inode reported by lstat is not the same as
   the one reported by calling readdir on the parent, exit nonzero.  */
#include "config.h"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <dirent.h>
#include <errno.h>
#include <sys/stat.h>
#include <unistd.h>

#define _(msg) msg
#define error(a, b, c, d) /* empty */
#define STREQ(a, b) (strcmp (a, b) == 0)

enum
{
  NOT_AN_INODE_NUMBER = 0
};

#ifdef D_INO_IN_DIRENT
# define D_INO(dp) (dp)->d_ino
#else
/* Some systems don't have inodes, so fake them to avoid lots of ifdefs.  */
# define D_INO(dp) NOT_AN_INODE_NUMBER
#endif

#ifndef DIRECTORY_SEPARATOR
# define DIRECTORY_SEPARATOR '/'
#endif

#ifndef ISSLASH
# define ISSLASH(C) ((C) == DIRECTORY_SEPARATOR)
#endif

#define FILE_SYSTEM_PREFIX_LEN(Filename) 0
#define FILE_SYSTEM_DRIVE_PREFIX_CAN_BE_RELATIVE 0
#define DOUBLE_SLASH_IS_DISTINCT_ROOT 0

static char *
last_component (char const *name)
{
  char const *base = name + FILE_SYSTEM_PREFIX_LEN (name);
  char const *p;
  int saw_slash = 0;

  while (ISSLASH (*base))
    base++;

  for (p = base; *p; p++)
    {
      if (ISSLASH (*p))
        saw_slash = 1;
      else if (saw_slash)
        {
          base = p;
          saw_slash = 0;
        }
    }

  return (char *) base;
}

size_t
dir_len (char const *file)
{
  size_t prefix_length = FILE_SYSTEM_PREFIX_LEN (file);
  size_t length;

  /* Advance prefix_length beyond important leading slashes.  */
  prefix_length += (prefix_length != 0
                    ? (FILE_SYSTEM_DRIVE_PREFIX_CAN_BE_RELATIVE
                       && ISSLASH (file[prefix_length]))
                    : (ISSLASH (file[0])
                       ? ((DOUBLE_SLASH_IS_DISTINCT_ROOT
                           && ISSLASH (file[1]) && ! ISSLASH (file[2])
                           ? 2 : 1))
                       : 0));

  /* Strip the basename and any redundant slashes before it.  */
  for (length = last_component (file) - file;
       prefix_length < length; length--)
    if (! ISSLASH (file[length - 1]))
      break;
  return length;
}

static char *
dir_name (char const *file)
{
  size_t length = dir_len (file);
  int append_dot = (length == 0
                    || (FILE_SYSTEM_DRIVE_PREFIX_CAN_BE_RELATIVE
                        && length == FILE_SYSTEM_PREFIX_LEN (file)
                        && file[2] != '\0' && ! ISSLASH (file[2])));
  char *dir = malloc (length + append_dot + 1);
  if (!dir)
    abort ();
  memcpy (dir, file, length);
  if (append_dot)
    dir[length++] = '.';
  dir[length] = '\0';
  return dir;
}

static int
readdir_inode_check (char const *file)
{
  char *d = dir_name (file);
  char const *b = last_component (file);
  DIR *dirp = opendir (d);
  int mismatch = 0;

  if (dirp == NULL)
    {
      error (0, errno, _("cannot open directory %s"), d);
      free (d);
      return mismatch;
    }

  while (1)
    {
      struct dirent const *dp;

      errno = 0;
      if ((dp = readdir (dirp)) == NULL)
        {
          if (errno)
            {
              /* Save/restore errno across closedir call.  */
              int e = errno;
              closedir (dirp);
              errno = e;

              /* Arrange to give a diagnostic after exiting this loop.  */
              dirp = NULL;
            }
          break;
        }

      if (STREQ (dp->d_name, b))
        {
          struct stat stat_buf;
          ino_t ino = D_INO (dp);
          if (lstat (file, &stat_buf) < 0)
            {
              error (0, errno, _("failed to lstat %s"), file);
              continue;
            }
          if (ino != stat_buf.st_ino)
            mismatch = 1;
          break;
        }
    }

  if (dirp == NULL || closedir (dirp) != 0)
    {
      error (0, errno, _("reading directory %s"), d);
    }

  free (d);

  return mismatch;
}

int
main (int argc, char **argv)
{
  int fail = 0;
  int i;
  for (i = 1; i < argc; i++)
    if (readdir_inode_check (argv[i]))
      {
        printf ("mismatch: %s\n", argv[i]);
        fail = 1;
      }

  return fail;
}
EOF

To demonstrate stand-alone, you'll need a config.h file.
Here, I'm using the one from coreutils/lib:

  $ gcc -O -W -Wall readdir-inode.c -I ~/coreutils/lib
  $ ./a.out /dev/shm
  mismatch: /dev/shm