]> Dogcows Code - chaz/tar/blobdiff - src/incremen.c
Relicense under GPLv3
[chaz/tar] / src / incremen.c
index bde8dc39d77bb71a0369857eba4bcf38d25d13c0..4400008a87787eb172c958e35abcb6ecd411d563 100644 (file)
@@ -1,9 +1,11 @@
 /* GNU dump extensions to tar.
 /* GNU dump extensions to tar.
-   Copyright (C) 1988, 92, 93, 94, 96, 97 Free Software Foundation, Inc.
+
+   Copyright (C) 1988, 1992, 1993, 1994, 1996, 1997, 1999, 2000, 2001,
+   2003, 2004, 2005, 2006, 2007 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
 
    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 2, or (at your option) any later
+   Free Software Foundation; either version 3, or (at your option) any later
    version.
 
    This program is distributed in the hope that it will be useful, but
    version.
 
    This program is distributed in the hope that it will be useful, but
 
    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
 
    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
-   59 Place - Suite 330, Boston, MA 02111-1307, USA.  */
+   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
 
 
-#include "system.h"
+#include <system.h>
+#include <getline.h>
+#include <hash.h>
+#include <quotearg.h>
+#include "common.h"
 
 
-#include <time.h>
-time_t time ();
+/* Incremental dump specialities.  */
 
 
-#define ISDIGIT(Char) (ISASCII (Char) && isdigit (Char))
-#define ISSPACE(Char) (ISASCII (Char) && isspace (Char))
+/* Which child files to save under a directory.  */
+enum children
+  {
+    NO_CHILDREN,
+    CHANGED_CHILDREN,
+    ALL_CHILDREN
+  };
 
 
-#include "common.h"
-\f
-/* Variable sized generic character buffers.  */
+#define DIRF_INIT     0x0001    /* directory structure is initialized
+                                  (procdir called at least once) */
+#define DIRF_NFS      0x0002    /* directory is mounted on nfs */
+#define DIRF_FOUND    0x0004    /* directory is found on fs */
+#define DIRF_NEW      0x0008    /* directory is new (not found
+                                  in the previous dump) */
+#define DIRF_RENAMED  0x0010    /* directory is renamed */
 
 
-struct accumulator
-{
-  int allocated;
-  int length;
-  char *pointer;
-};
+#define DIR_IS_INITED(d) ((d)->flags & DIRF_INIT)
+#define DIR_IS_NFS(d) ((d)->flags & DIRF_NFS)
+#define DIR_IS_FOUND(d) ((d)->flags & DIRF_FOUND)
+#define DIR_IS_NEW(d) ((d)->flags & DIRF_NEW)
+#define DIR_IS_RENAMED(d) ((d)->flags & DIRF_RENAMED)
 
 
-/* Amount of space guaranteed just after a reallocation.  */
-#define ACCUMULATOR_SLACK 50
+#define DIR_SET_FLAG(d,f) (d)->flags |= (f)
+#define DIR_CLEAR_FLAG(d,f) (d)->flags &= ~(f)
 
 
-/*---------------------------------------------------------.
-| Return the accumulated data from an ACCUMULATOR buffer.  |
-`---------------------------------------------------------*/
+/* Directory attributes.  */
+struct directory
+  {
+    struct timespec mtime;      /* Modification time */
+    dev_t device_number;       /* device number for directory */
+    ino_t inode_number;                /* inode number for directory */
+    char *contents;             /* Directory contents */
+    char *icontents;            /* Initial contents if the directory was
+                                  rescanned */
+    enum children children;     /* What to save under this directory */
+    unsigned flags;             /* See DIRF_ macros above */
+    struct directory *orig;     /* If the directory was renamed, points to
+                                  the original directory structure */
+    char name[1];              /* file name of directory */
+  };
 
 
-static char *
-get_accumulator (struct accumulator *accumulator)
-{
-  return accumulator->pointer;
-}
+static Hash_table *directory_table;
+static Hash_table *directory_meta_table;
 
 
-/*-----------------------------------------------.
-| Allocate and return a new accumulator buffer.         |
-`-----------------------------------------------*/
+#if HAVE_ST_FSTYPE_STRING
+  static char const nfs_string[] = "nfs";
+# define NFS_FILE_STAT(st) (strcmp ((st).st_fstype, nfs_string) == 0)
+#else
+# define ST_DEV_MSB(st) (~ (dev_t) 0 << (sizeof (st).st_dev * CHAR_BIT - 1))
+# define NFS_FILE_STAT(st) (((st).st_dev & ST_DEV_MSB (st)) != 0)
+#endif
 
 
-static struct accumulator *
-new_accumulator (void)
+/* Calculate the hash of a directory.  */
+static size_t
+hash_directory_name (void const *entry, size_t n_buckets)
 {
 {
-  struct accumulator *accumulator
-    = (struct accumulator *) xmalloc (sizeof (struct accumulator));
+  struct directory const *directory = entry;
+  return hash_string (directory->name, n_buckets);
+}
 
 
-  accumulator->allocated = ACCUMULATOR_SLACK;
-  accumulator->pointer = (char *) xmalloc (ACCUMULATOR_SLACK);
-  accumulator->length = 0;
-  return accumulator;
+/* Compare two directories for equality of their names. */
+static bool
+compare_directory_names (void const *entry1, void const *entry2)
+{
+  struct directory const *directory1 = entry1;
+  struct directory const *directory2 = entry2;
+  return strcmp (directory1->name, directory2->name) == 0;
 }
 
 }
 
-/*-----------------------------------.
-| Deallocate an ACCUMULATOR buffer.  |
-`-----------------------------------*/
+static size_t
+hash_directory_meta (void const *entry, size_t n_buckets)
+{
+  struct directory const *directory = entry;
+  /* FIXME: Work out a better algorytm */
+  return (directory->device_number + directory->inode_number) % n_buckets;
+}
 
 
-static void
-delete_accumulator (struct accumulator *accumulator)
+/* Compare two directories for equality of their device and inode numbers. */
+static bool
+compare_directory_meta (void const *entry1, void const *entry2)
 {
 {
-  free (accumulator->pointer);
-  free (accumulator);
+  struct directory const *directory1 = entry1;
+  struct directory const *directory2 = entry2;
+  return directory1->device_number == directory2->device_number
+            && directory1->inode_number == directory2->inode_number;
 }
 
 }
 
-/*----------------------------------------------------------------------.
-| At the end of an ACCUMULATOR buffer, add a DATA block of SIZE bytes.  |
-`----------------------------------------------------------------------*/
+/* Make a directory entry for given NAME */
+static struct directory *
+make_directory (const char *name)
+{
+  size_t namelen = strlen (name);
+  size_t size = offsetof (struct directory, name) + namelen + 1;
+  struct directory *directory = xmalloc (size);
+  directory->contents = directory->icontents = NULL;
+  directory->orig = NULL;
+  directory->flags = false;
+  strcpy (directory->name, name);
+  if (ISSLASH (directory->name[namelen-1]))
+    directory->name[namelen-1] = 0;
+  return directory;
+}
 
 
-static void
-add_to_accumulator (struct accumulator *accumulator,
-                   const char *data, int size)
+/* Create and link a new directory entry for directory NAME, having a
+   device number DEV and an inode number INO, with NFS indicating
+   whether it is an NFS device and FOUND indicating whether we have
+   found that the directory exists.  */
+static struct directory *
+note_directory (char const *name, struct timespec mtime,
+               dev_t dev, ino_t ino, bool nfs, bool found, char *contents)
 {
 {
-  if (accumulator->length + size > accumulator->allocated)
+  struct directory *directory = make_directory (name);
+
+  directory->mtime = mtime;
+  directory->device_number = dev;
+  directory->inode_number = ino;
+  directory->children = CHANGED_CHILDREN;
+  if (nfs)
+    DIR_SET_FLAG (directory, DIRF_NFS);
+  if (found)
+    DIR_SET_FLAG (directory, DIRF_FOUND);
+  if (contents)
     {
     {
-      accumulator->allocated = accumulator->length + size + ACCUMULATOR_SLACK;
-      accumulator->pointer = (char *)
-       xrealloc (accumulator->pointer, (size_t) accumulator->allocated);
+      size_t size = dumpdir_size (contents);
+      directory->contents = xmalloc (size);
+      memcpy (directory->contents, contents, size);
     }
     }
-  memcpy (accumulator->pointer + accumulator->length, data, (size_t) size);
-  accumulator->length += size;
+  else
+    directory->contents = NULL;
+
+  if (! ((directory_table
+         || (directory_table = hash_initialize (0, 0,
+                                                hash_directory_name,
+                                                compare_directory_names, 0)))
+        && hash_insert (directory_table, directory)))
+    xalloc_die ();
+
+  if (! ((directory_meta_table
+         || (directory_meta_table = hash_initialize (0, 0,
+                                                     hash_directory_meta,
+                                                     compare_directory_meta,
+                                                     0)))
+        && hash_insert (directory_meta_table, directory)))
+    xalloc_die ();
+
+  return directory;
 }
 }
-\f
-/* Incremental dump specialities.  */
-
-/* Current time.  */
-static time_t time_now;
 
 
-/* List of directory names.  */
-struct directory
-  {
-    struct directory *next;    /* next entry in list */
-    const char *name;          /* path name of directory */
-    int device_number;         /* device number for directory */
-    int inode_number;          /* inode number for directory */
-    int allnew;
-    const char *dir_text;
-  };
-static struct directory *directory_list = NULL;
-
-/*-------------------------------------------------------------------.
-| Create and link a new directory entry for directory NAME, having a |
-| DEVICE_NUMBER and a INODE_NUMBER, with some TEXT.                 |
-`-------------------------------------------------------------------*/
+/* Return a directory entry for a given file NAME, or zero if none found.  */
+static struct directory *
+find_directory (const char *name)
+{
+  if (! directory_table)
+    return 0;
+  else
+    {
+      struct directory *dir = make_directory (name);
+      struct directory *ret = hash_lookup (directory_table, dir);
+      free (dir);
+      return ret;
+    }
+}
 
 
-static void
-note_directory (char *name, dev_t device_number, ino_t inode_number,
-               const char *text)
+/* Return a directory entry for a given combination of device and inode
+   numbers, or zero if none found.  */
+static struct directory *
+find_directory_meta (dev_t dev, ino_t ino)
 {
 {
-  struct directory *directory
-    = (struct directory *) xmalloc (sizeof (struct directory));
+  if (! directory_meta_table)
+    return 0;
+  else
+    {
+      struct directory *dir = make_directory ("");
+      struct directory *ret;
+      dir->device_number = dev;
+      dir->inode_number = ino;
+      ret = hash_lookup (directory_meta_table, dir);
+      free (dir);
+      return ret;
+    }
+}
 
 
-  directory->next = directory_list;
-  directory_list = directory;
+void
+update_parent_directory (const char *name)
+{
+  struct directory *directory;
+  char *p;
 
 
-  directory->device_number = device_number;
-  directory->inode_number = inode_number;
-  directory->name = xstrdup (name);
-  directory->dir_text = text;
-  directory->allnew = 0;
+  p = dir_name (name);
+  directory = find_directory (p);
+  if (directory)
+    {
+      struct stat st;
+      if (deref_stat (dereference_option, p, &st) != 0)
+       stat_diag (name);
+      else
+       directory->mtime = get_stat_mtime (&st);
+    }
+  free (p);
 }
 
 }
 
-/*------------------------------------------------------------------------.
-| Return a directory entry for a given path NAME, or NULL if none found.  |
-`------------------------------------------------------------------------*/
-
 static struct directory *
 static struct directory *
-find_directory (char *name)
+procdir (char *name_buffer, struct stat *stat_data,
+        dev_t device,
+        enum children children,
+        bool verbose)
 {
   struct directory *directory;
 {
   struct directory *directory;
+  bool nfs = NFS_FILE_STAT (*stat_data);
 
 
-  for (directory = directory_list;
-       directory;
-       directory = directory->next)
+  if ((directory = find_directory (name_buffer)) != NULL)
     {
     {
-      if (!strcmp (directory->name, name))
+      if (DIR_IS_INITED (directory))
        return directory;
        return directory;
+
+      /* With NFS, the same file can have two different devices
+        if an NFS directory is mounted in multiple locations,
+        which is relatively common when automounting.
+        To avoid spurious incremental redumping of
+        directories, consider all NFS devices as equal,
+        relying on the i-node to establish differences.  */
+
+      if (! (((DIR_IS_NFS (directory) & nfs)
+             || directory->device_number == stat_data->st_dev)
+            && directory->inode_number == stat_data->st_ino))
+       {
+         /* FIXME: find_directory_meta ignores nfs */
+         struct directory *d = find_directory_meta (stat_data->st_dev,
+                                                    stat_data->st_ino);
+         if (d)
+           {
+             if (verbose_option)
+               WARN ((0, 0, _("%s: Directory has been renamed from %s"),
+                      quotearg_colon (name_buffer),
+                      quote_n (1, d->name)));
+             directory->orig = d;
+             DIR_SET_FLAG (directory, DIRF_RENAMED);
+             directory->children = CHANGED_CHILDREN;
+           }
+         else
+           {
+             if (verbose_option)
+               WARN ((0, 0, _("%s: Directory has been renamed"),
+                      quotearg_colon (name_buffer)));
+             directory->children = ALL_CHILDREN;
+             directory->device_number = stat_data->st_dev;
+             directory->inode_number = stat_data->st_ino;
+           }
+         if (nfs)
+           DIR_SET_FLAG (directory, DIRF_NFS);
+       }
+      else
+       directory->children = CHANGED_CHILDREN;
+
+      DIR_SET_FLAG (directory, DIRF_FOUND);
     }
     }
+  else
+    {
+      struct directory *d = find_directory_meta (stat_data->st_dev,
+                                                stat_data->st_ino);
+
+      directory = note_directory (name_buffer,
+                                 get_stat_mtime(stat_data),
+                                 stat_data->st_dev,
+                                 stat_data->st_ino,
+                                 nfs,
+                                 true,
+                                 NULL);
+
+      if (d)
+       {
+         if (verbose)
+           WARN ((0, 0, _("%s: Directory has been renamed from %s"),
+                  quotearg_colon (name_buffer),
+                  quote_n (1, d->name)));
+         directory->orig = d;
+         DIR_SET_FLAG (directory, DIRF_RENAMED);
+         directory->children = CHANGED_CHILDREN;
+       }
+      else
+       {
+         DIR_SET_FLAG (directory, DIRF_NEW);
+         if (verbose)
+           WARN ((0, 0, _("%s: Directory is new"),
+                  quotearg_colon (name_buffer)));
+         directory->children =
+           (listed_incremental_option
+            || (OLDER_STAT_TIME (*stat_data, m)
+                || (after_date_option
+                    && OLDER_STAT_TIME (*stat_data, c))))
+           ? ALL_CHILDREN
+           : CHANGED_CHILDREN;
+       }
+    }
+
+  /* If the directory is on another device and --one-file-system was given,
+     omit it... */
+  if (one_file_system_option && device != stat_data->st_dev
+      /* ... except if it was explicitely given in the command line */
+      && !is_individual_file (name_buffer))
+    directory->children = NO_CHILDREN;
+  else if (children == ALL_CHILDREN)
+    directory->children = ALL_CHILDREN;
+
+  DIR_SET_FLAG (directory, DIRF_INIT);
+
+  return directory;
+}
+
+/* Locate NAME in the dumpdir array DUMP.
+   Return pointer to the slot in the array, or NULL if not found */
+const char *
+dumpdir_locate (const char *dump, const char *name)
+{
+  if (dump)
+    while (*dump)
+      {
+       /* Ignore 'R' (rename) and 'X' (tempname) entries, since they break
+          alphabetical ordering.
+          They normally do not occur in dumpdirs from the snapshot files,
+          but this function is also used by purge_directory, which operates
+          on a dumpdir from the archive, hence the need for this test. */
+       if (!strchr ("RX", *dump))
+         {
+           int rc = strcmp (dump + 1, name);
+           if (rc == 0)
+             return dump;
+           if (rc > 1)
+             break;
+         }
+       dump += strlen (dump) + 1;
+      }
   return NULL;
 }
 
   return NULL;
 }
 
-/*---.
-| ?  |
-`---*/
+/* Return size in bytes of the dumpdir array P */
+size_t
+dumpdir_size (const char *p)
+{
+  size_t totsize = 0;
+
+  while (*p)
+    {
+      size_t size = strlen (p) + 1;
+      totsize += size;
+      p += size;
+    }
+  return totsize + 1;
+}
 
 static int
 
 static int
-compare_dirents (const voidstar first, const voidstar second)
+compare_dirnames (const void *first, const void *second)
 {
 {
-  return strcmp ((*(char *const *) first) + 1,
-                (*(char *const *) second) + 1);
+  char const *const *name1 = first;
+  char const *const *name2 = second;
+  return strcmp (*name1, *name2);
 }
 
 }
 
-/*---.
-| ?  |
-`---*/
+/* Compare dumpdir array from DIRECTORY with directory listing DIR and
+   build a new dumpdir template.
 
 
-char *
-get_directory_contents (char *path, int device)
+   DIR must be returned by a previous call to savedir().
+
+   File names in DIRECTORY->contents must be sorted
+   alphabetically.
+
+   DIRECTORY->contents is replaced with the created template. Each entry is
+   prefixed with ' ' if it was present in DUMP and with 'Y' otherwise. */
+
+void
+makedumpdir (struct directory *directory, const char *dir)
 {
 {
-  struct accumulator *accumulator;
+  size_t i,
+         dirsize,  /* Number of elements in DIR */
+         len;      /* Length of DIR, including terminating nul */
+  const char *p;
+  char const **array;
+  char *new_dump, *new_dump_ptr;
+  const char *dump;
+
+  if (directory->children == ALL_CHILDREN)
+    dump = NULL;
+  else if (DIR_IS_RENAMED (directory))
+    dump = directory->orig->icontents ?
+              directory->orig->icontents : directory->orig->contents;
+  else
+    dump = directory->contents;
+
+  /* Count the size of DIR and the number of elements it contains */
+  dirsize = 0;
+  len = 0;
+  for (p = dir; *p; p += strlen (p) + 1, dirsize++)
+    len += strlen (p) + 2;
+  len++;
+
+  /* Create a sorted directory listing */
+  array = xcalloc (dirsize, sizeof array[0]);
+  for (i = 0, p = dir; *p; p += strlen (p) + 1, i++)
+    array[i] = p;
+
+  qsort (array, dirsize, sizeof (array[0]), compare_dirnames);
+
+  /* Prepare space for new dumpdir */
+  new_dump = xmalloc (len);
+  new_dump_ptr = new_dump;
+
+  /* Fill in the dumpdir template */
+  for (i = 0; i < dirsize; i++)
+    {
+      const char *loc = dumpdir_locate (dump, array[i]);
+      if (loc)
+       {
+         *new_dump_ptr++ = ' ';
+         dump = loc + strlen (loc) + 1;
+       }
+      else
+       *new_dump_ptr++ = 'Y'; /* New entry */
 
 
-  /* Recursively scan the given PATH.  */
+      /* Copy the file name */
+      for (p = array[i]; (*new_dump_ptr++ = *p++); )
+       ;
+    }
+  *new_dump_ptr = 0;
+  directory->icontents = directory->contents;
+  directory->contents = new_dump;
+  free (array);
+}
 
 
-  {
-    DIR *dirp = opendir (path);        /* for scanning directory */
-    struct dirent *entry;      /* directory entry being scanned */
-    char *name_buffer;         /* directory, `/', and directory member */
-    int name_buffer_size;      /* allocated size of name_buffer, minus 2 */
-    int name_length;           /* used length in name_buffer */
-    struct directory *directory; /* for checking if already already seen */
-    int all_children;
-
-    if (dirp == NULL)
-      {
-       ERROR ((0, errno, _("Cannot open directory %s"), path));
-       return NULL;
-      }
-    errno = 0;                 /* FIXME: errno should be read-only */
+/* Recursively scan the given directory. */
+static char *
+scan_directory (char *dir_name, dev_t device)
+{
+  char *dirp = savedir (dir_name);     /* for scanning directory */
+  char *name_buffer;           /* directory, `/', and directory member */
+  size_t name_buffer_size;     /* allocated size of name_buffer, minus 2 */
+  size_t name_length;          /* used length in name_buffer */
+  struct stat stat_data;
+  struct directory *directory;
 
 
-    name_buffer_size = strlen (path) + NAME_FIELD_SIZE;
-    name_buffer = xmalloc ((size_t) (name_buffer_size + 2));
-    strcpy (name_buffer, path);
-    if (path[strlen (path) - 1] != '/')
-      strcat (name_buffer, "/");
-    name_length = strlen (name_buffer);
+  if (! dirp)
+    savedir_error (dir_name);
 
 
-    directory = find_directory (path);
-    all_children = directory ? directory->allnew : 0;
+  name_buffer_size = strlen (dir_name) + NAME_FIELD_SIZE;
+  name_buffer = xmalloc (name_buffer_size + 2);
+  strcpy (name_buffer, dir_name);
+  if (! ISSLASH (dir_name[strlen (dir_name) - 1]))
+    strcat (name_buffer, "/");
+  name_length = strlen (name_buffer);
 
 
-    accumulator = new_accumulator ();
+  if (deref_stat (dereference_option, name_buffer, &stat_data))
+    {
+      stat_diag (name_buffer);
+      /* FIXME: used to be
+           children = CHANGED_CHILDREN;
+        but changed to: */
+      free (name_buffer);
+      free (dirp);
+      return NULL;
+    }
 
 
-    while (entry = readdir (dirp), entry)
-      {
-       struct stat stat_data;
+  directory = procdir (name_buffer, &stat_data, device, NO_CHILDREN, false);
 
 
-       /* Skip `.' and `..'.  */
+  if (dirp && directory->children != NO_CHILDREN)
+    {
+      char  *entry;    /* directory entry being scanned */
+      size_t entrylen; /* length of directory entry */
 
 
-       if (is_dot_or_dotdot (entry->d_name))
-         continue;
+      makedumpdir (directory, dirp);
 
 
-       if ((int) NAMLEN (entry) + name_length >= name_buffer_size)
-         {
-           while ((int) NAMLEN (entry) + name_length >= name_buffer_size)
-             name_buffer_size += NAME_FIELD_SIZE;
-           name_buffer = (char *)
-             xrealloc (name_buffer, (size_t) (name_buffer_size + 2));
-         }
-       strcpy (name_buffer + name_length, entry->d_name);
+      for (entry = directory->contents;
+          (entrylen = strlen (entry)) != 0;
+          entry += entrylen + 1)
+       {
+         if (name_buffer_size <= entrylen - 1 + name_length)
+           {
+             do
+               name_buffer_size += NAME_FIELD_SIZE;
+             while (name_buffer_size <= entrylen - 1 + name_length);
+             name_buffer = xrealloc (name_buffer, name_buffer_size + 2);
+           }
+         strcpy (name_buffer + name_length, entry + 1);
 
 
-       if (dereference_option
-#ifdef AIX
-           ? statx (name_buffer, &stat_data, STATSIZE, STX_HIDDEN)
-           : statx (name_buffer, &stat_data, STATSIZE, STX_HIDDEN | STX_LINK)
-#else
-           ? stat (name_buffer, &stat_data)
-           : lstat (name_buffer, &stat_data)
-#endif
-           )
-         {
-           ERROR ((0, errno, _("Cannot stat %s"), name_buffer));
-           continue;
-         }
+         if (excluded_name (name_buffer))
+           *entry = 'N';
+         else
+           {
+             if (deref_stat (dereference_option, name_buffer, &stat_data))
+               {
+                 stat_diag (name_buffer);
+                 *entry = 'N';
+                 continue;
+               }
 
 
-       if ((one_file_system_option && device != stat_data.st_dev)
-           || (exclude_option && check_exclude (name_buffer)))
-         add_to_accumulator (accumulator, "N", 1);
+             if (S_ISDIR (stat_data.st_mode))
+               {
+                 procdir (name_buffer, &stat_data, device,
+                          directory->children,
+                          verbose_option);
+                 *entry = 'D';
+               }
 
 
-#ifdef AIX
-       else if (S_ISHIDDEN (stat_data.st_mode))
-         {
-           add_to_accumulator (accumulator, "D", 1);
-           strcat (entry->d_name, "A");
-           entry->d_namlen++;
-         }
-#endif
+             else if (one_file_system_option && device != stat_data.st_dev)
+               *entry = 'N';
 
 
-       else if (S_ISDIR (stat_data.st_mode))
-         {
-           if (directory = find_directory (name_buffer), directory)
-             {
-               /* Devices having the high bit set are NFS devices, which are
-                  attributed somewhat randomly in automounting situations.
-                  For avoiding spurious incremental redumping of directories,
-                  we have to plainly consider all NFS devices as equal,
-                  relying on the i-node only to establish differences.  */
-
-               /* FIXME: Göran Uddeborg <goeran@uddeborg.pp.se> says, on
-                  1996-09-20, that SunOS 5/Solaris 2 uses unsigned long for
-                  the device number type.  */
-
-               if ((((short) directory->device_number >= 0
-                     || (short) stat_data.st_dev >= 0)
-                    && directory->device_number != stat_data.st_dev)
-                   || directory->inode_number != stat_data.st_ino)
-                 {
-                   if (verbose_option)
-                     WARN ((0, 0, _("Directory %s has been renamed"),
-                            name_buffer));
-                   directory->allnew = 1;
-                   directory->device_number = stat_data.st_dev;
-                   directory->inode_number = stat_data.st_ino;
-                 }
-               directory->dir_text = "";
-             }
-           else
-             {
-               if (verbose_option)
-                 WARN ((0, 0, _("Directory %s is new"), name_buffer));
-               note_directory (name_buffer, stat_data.st_dev, stat_data.st_ino,
-                               "");
-               directory = find_directory (name_buffer);
-               directory->allnew = 1;
-             }
-           if (all_children && directory)
-             directory->allnew = 1;
-
-           add_to_accumulator (accumulator, "D", 1);
-         }
+             else if (*entry == 'Y')
+               /* New entry, skip further checks */;
 
 
-       else
-         if (!all_children
-             && stat_data.st_mtime < newer_mtime_option
-             && (!after_date_option
-                 || stat_data.st_ctime < newer_ctime_option))
-           add_to_accumulator (accumulator, "N", 1);
-         else
-           add_to_accumulator (accumulator, "Y", 1);
+             /* FIXME: if (S_ISHIDDEN (stat_data.st_mode))?? */
 
 
-       add_to_accumulator (accumulator,
-                           entry->d_name, (int) (NAMLEN (entry) + 1));
-      }
-    add_to_accumulator (accumulator, "\000\000", 2);
+             else if (OLDER_STAT_TIME (stat_data, m)
+                      && (!after_date_option
+                          || OLDER_STAT_TIME (stat_data, c)))
+               *entry = 'N';
+             else
+               *entry = 'Y';
+           }
+       }
+    }
 
 
-    free (name_buffer);
-    closedir (dirp);
-  }
+  free (name_buffer);
+  if (dirp)
+    free (dirp);
 
 
-  /* Sort the contents of the directory, now that we have it all.  */
+  return directory->contents;
+}
 
 
-  {
-    char *pointer = get_accumulator (accumulator);
-    size_t counter;
-    char *cursor;
-    char *buffer;
-    char **array;
-    char **array_cursor;
-
-    counter = 0;
-    for (cursor = pointer; *cursor; cursor += strlen (cursor) + 1)
-      counter++;
-
-    if (counter == 0)
-      {
-       delete_accumulator (accumulator);
-       return NULL;
-      }
+char *
+get_directory_contents (char *dir_name, dev_t device)
+{
+  return scan_directory (dir_name, device);
+}
 
 
-    array = (char **) xmalloc (sizeof (char *) * (counter + 1));
+\f
+static void
+obstack_code_rename (struct obstack *stk, char *from, char *to)
+{
+  obstack_1grow (stk, 'R');
+  obstack_grow (stk, from, strlen (from) + 1);
+  obstack_1grow (stk, 'T');
+  obstack_grow (stk, to, strlen (to) + 1);
+}
 
 
-    array_cursor = array;
-    for (cursor = pointer; *cursor; cursor += strlen (cursor) + 1)
-      *array_cursor++ = cursor;
-    *array_cursor = NULL;
+static bool
+rename_handler (void *data, void *proc_data)
+{
+  struct directory *dir = data;
+  struct obstack *stk = proc_data;
 
 
-    qsort ((voidstar) array, counter, sizeof (char *), compare_dirents);
+  if (DIR_IS_RENAMED (dir))
+    {
+      struct directory *prev, *p;
 
 
-    buffer = (char *) xmalloc ((size_t) (cursor - pointer + 2));
+      /* Detect eventual cycles and clear DIRF_RENAMED flag, so these entries
+        are ignored when hit by this function next time.
+        If the chain forms a cycle, prev points to the entry DIR is renamed
+        from. In this case it still retains DIRF_RENAMED flag, which will be
+        cleared in the `else' branch below */
+      for (prev = dir; prev && prev->orig != dir; prev = prev->orig)
+       DIR_CLEAR_FLAG (prev, DIRF_RENAMED);
 
 
-    cursor = buffer;
-    for (array_cursor = array; *array_cursor; array_cursor++)
-      {
-       char *string = *array_cursor;
+      if (prev == NULL)
+       {
+         for (p = dir; p && p->orig; p = p->orig)
+           obstack_code_rename (stk, p->orig->name, p->name);
+       }
+      else
+       {
+         char *temp_name;
 
 
-       while ((*cursor++ = *string++))
-         continue;
-      }
-    *cursor = '\0';
+         DIR_CLEAR_FLAG (prev, DIRF_RENAMED);
+
+         /* Break the cycle by using a temporary name for one of its
+            elements.
+            First, create a temp name stub entry. */
+         temp_name = dir_name (dir->name);
+         obstack_1grow (stk, 'X');
+         obstack_grow (stk, temp_name, strlen (temp_name) + 1);
 
 
-    delete_accumulator (accumulator);
-    free (array);
-    return buffer;
-  }
+         obstack_code_rename (stk, dir->name, "");
+
+         for (p = dir; p != prev; p = p->orig)
+           obstack_code_rename (stk, p->orig->name, p->name);
+
+         obstack_code_rename (stk, "", prev->name);
+       }
+    }
+  return true;
 }
 
 }
 
-/*----------------------------------------------------------------------.
-| Add all the files in PATH, which is a directory, to the namelist.  If |
-| any of the files is a directory, recurse on the subdirectory.                |
-`----------------------------------------------------------------------*/
+const char *
+append_incremental_renames (const char *dump)
+{
+  struct obstack stk;
+  size_t size;
+
+  if (directory_table == NULL)
+    return dump;
 
 
+  obstack_init (&stk);
+  if (dump)
+    {
+      size = dumpdir_size (dump) - 1;
+      obstack_grow (&stk, dump, size);
+    }
+  else
+    size = 0;
+
+  hash_do_for_each (directory_table, rename_handler, &stk);
+  if (obstack_object_size (&stk) != size)
+    {
+      obstack_1grow (&stk, 0);
+      dump = obstack_finish (&stk);
+    }
+  else
+    obstack_free (&stk, NULL);
+  return dump;
+}
+
+\f
+
+static FILE *listed_incremental_stream;
+
+/* Version of incremental format snapshots (directory files) used by this
+   tar. Currently it is supposed to be a single decimal number. 0 means
+   incremental snapshots as per tar version before 1.15.2.
+
+   The current tar version supports incremental versions from
+   0 up to TAR_INCREMENTAL_VERSION, inclusive.
+   It is able to create only snapshots of TAR_INCREMENTAL_VERSION */
+
+#define TAR_INCREMENTAL_VERSION 2
+
+/* Read incremental snapshot formats 0 and 1 */
 static void
 static void
-add_hierarchy_to_namelist (char *path, int device)
+read_incr_db_01 (int version, const char *initbuf)
 {
 {
-  char *buffer = get_directory_contents (path, device);
+  int n;
+  uintmax_t u;
+  time_t sec;
+  long int nsec;
+  char *buf = 0;
+  size_t bufsize;
+  char *ebuf;
+  long lineno = 1;
+
+  if (version == 1)
+    {
+      if (getline (&buf, &bufsize, listed_incremental_stream) <= 0)
+       {
+         read_error (listed_incremental_option);
+         free (buf);
+         return;
+       }
+      ++lineno;
+    }
+  else
+    {
+      buf = strdup (initbuf);
+      bufsize = strlen (buf) + 1;
+    }
 
 
-  {
-    struct name *name;
+  sec = TYPE_MINIMUM (time_t);
+  nsec = -1;
+  errno = 0;
+  u = strtoumax (buf, &ebuf, 10);
+  if (!errno && TYPE_MAXIMUM (time_t) < u)
+    errno = ERANGE;
+  if (errno || buf == ebuf)
+    ERROR ((0, errno, "%s:%ld: %s",
+           quotearg_colon (listed_incremental_option),
+           lineno,
+           _("Invalid time stamp")));
+  else
+    {
+      sec = u;
 
 
-    for (name = namelist; name; name = name->next)
-      if (strcmp (name->name, path) == 0)
-         break;
-    if (name)
-      name->dir_contents = buffer ? buffer : "\0\0\0\0";
-  }
-
-  if (buffer)
-    {
-      int name_length = strlen (path);
-      int allocated_length = (name_length >= NAME_FIELD_SIZE
-                             ? name_length + NAME_FIELD_SIZE
-                             : NAME_FIELD_SIZE);
-      char *name_buffer = xmalloc ((size_t) (allocated_length + 1));
-                               /* FIXME: + 2 above?  */
-      char *string;
-      int string_length;
-
-      strcpy (name_buffer, path);
-      if (name_buffer[name_length - 1] != '/')
+      if (version == 1 && *ebuf)
+       {
+         char const *buf_ns = ebuf + 1;
+         errno = 0;
+         u = strtoumax (buf_ns, &ebuf, 10);
+         if (!errno && BILLION <= u)
+           errno = ERANGE;
+         if (errno || buf_ns == ebuf)
+           {
+             ERROR ((0, errno, "%s:%ld: %s",
+                     quotearg_colon (listed_incremental_option),
+                     lineno,
+                     _("Invalid time stamp")));
+             sec = TYPE_MINIMUM (time_t);
+           }
+         else
+           nsec = u;
+       }
+      else
        {
        {
-         name_buffer[name_length++] = '/';
-         name_buffer[name_length] = '\0';
+         /* pre-1 incremental format does not contain nanoseconds */
+         nsec = 0;
        }
        }
+    }
+  newer_mtime_option.tv_sec = sec;
+  newer_mtime_option.tv_nsec = nsec;
+
+
+  while (0 < (n = getline (&buf, &bufsize, listed_incremental_stream)))
+    {
+      dev_t dev;
+      ino_t ino;
+      bool nfs = buf[0] == '+';
+      char *strp = buf + nfs;
+      struct timespec mtime;
+
+      lineno++;
 
 
-      for (string = buffer; *string; string += string_length + 1)
+      if (buf[n - 1] == '\n')
+       buf[n - 1] = '\0';
+
+      if (version == 1)
        {
        {
-         string_length = strlen (string);
-         if (*string == 'D')
+         errno = 0;
+         u = strtoumax (strp, &ebuf, 10);
+         if (!errno && TYPE_MAXIMUM (time_t) < u)
+           errno = ERANGE;
+         if (errno || strp == ebuf || *ebuf != ' ')
            {
            {
-             if (name_length + string_length >= allocated_length)
-               {
-                 while (name_length + string_length >= allocated_length)
-                   allocated_length += NAME_FIELD_SIZE;
-                 name_buffer = (char *)
-                   xrealloc (name_buffer, (size_t) (allocated_length + 1));
-               }
-             strcpy (name_buffer + name_length, string + 1);
-             addname (name_buffer);
-             add_hierarchy_to_namelist (name_buffer, device);
+             ERROR ((0, errno, "%s:%ld: %s",
+                     quotearg_colon (listed_incremental_option), lineno,
+                     _("Invalid modification time (seconds)")));
+             sec = (time_t) -1;
+           }
+         else
+           sec = u;
+         strp = ebuf;
+
+         errno = 0;
+         u = strtoumax (strp, &ebuf, 10);
+         if (!errno && BILLION <= u)
+           errno = ERANGE;
+         if (errno || strp == ebuf || *ebuf != ' ')
+           {
+             ERROR ((0, errno, "%s:%ld: %s",
+                     quotearg_colon (listed_incremental_option), lineno,
+                     _("Invalid modification time (nanoseconds)")));
+             nsec = -1;
            }
            }
+         else
+           nsec = u;
+         mtime.tv_sec = sec;
+         mtime.tv_nsec = nsec;
+         strp = ebuf;
        }
        }
+      else
+       memset (&mtime, 0, sizeof mtime);
 
 
-      free (name_buffer);
+      errno = 0;
+      u = strtoumax (strp, &ebuf, 10);
+      if (!errno && TYPE_MAXIMUM (dev_t) < u)
+       errno = ERANGE;
+      if (errno || strp == ebuf || *ebuf != ' ')
+       {
+         ERROR ((0, errno, "%s:%ld: %s",
+                 quotearg_colon (listed_incremental_option), lineno,
+                 _("Invalid device number")));
+         dev = (dev_t) -1;
+       }
+      else
+       dev = u;
+      strp = ebuf;
+
+      errno = 0;
+      u = strtoumax (strp, &ebuf, 10);
+      if (!errno && TYPE_MAXIMUM (ino_t) < u)
+       errno = ERANGE;
+      if (errno || strp == ebuf || *ebuf != ' ')
+       {
+         ERROR ((0, errno, "%s:%ld: %s",
+                 quotearg_colon (listed_incremental_option), lineno,
+                 _("Invalid inode number")));
+         ino = (ino_t) -1;
+       }
+      else
+       ino = u;
+      strp = ebuf;
+
+      strp++;
+      unquote_string (strp);
+      note_directory (strp, mtime, dev, ino, nfs, false, NULL);
     }
     }
+  free (buf);
 }
 }
-\f
-/*---.
-| ?  |
-`---*/
 
 
-static void
-read_directory_file (void)
+/* Read a nul-terminated string from FP and store it in STK.
+   Store the number of bytes read (including nul terminator) in PCOUNT.
+
+   Return the last character read or EOF on end of file. */
+static int
+read_obstack (FILE *fp, struct obstack *stk, size_t *pcount)
 {
 {
-  dev_t device_number;
-  ino_t inode_number;
-  char *strp;
-  FILE *fp;
-  char buf[512];
-  static char *path = NULL;
-
-  if (path == NULL)
-    path = xmalloc (PATH_MAX);
-  time (&time_now);
-  if (listed_incremental_option[0] != '/')
-    {
-#if HAVE_GETCWD
-      if (!getcwd (path, PATH_MAX))
-       FATAL_ERROR ((0, 0, _("Could not get current directory")));
-#else
-      char *getwd ();
+  int c;
+  size_t i;
 
 
-      if (!getwd (path))
-       FATAL_ERROR ((0, 0, _("Could not get current directory: %s"), path));
-#endif
+  for (i = 0, c = getc (fp); c != EOF && c != 0; c = getc (fp), i++)
+    obstack_1grow (stk, c);
+  obstack_1grow (stk, 0);
+
+  *pcount = i;
+  return c;
+}
 
 
-      if (strlen (path) + 1 + strlen (listed_incremental_option) + 1 > PATH_MAX)
-       ERROR ((TAREXIT_FAILURE, 0, _("File name %s/%s too long"),
-               path, listed_incremental_option));
+/* Read from file FP a nul-terminated string and convert it to
+   intmax_t.  Return the resulting value in PVAL.  Assume '-' has
+   already been read.
 
 
-      strcat (path, "/");
-      strcat (path, listed_incremental_option);
-      listed_incremental_option = path;
-    }
-  fp = fopen (listed_incremental_option, "r");
-  if (fp == 0 && errno != ENOENT)
+   Throw a fatal error if the string cannot be converted or if the
+   converted value is less than MIN_VAL.  */
+
+static void
+read_negative_num (FILE *fp, intmax_t min_val, intmax_t *pval)
+{
+  int c;
+  size_t i;
+  char buf[INT_BUFSIZE_BOUND (intmax_t)];
+  char *ep;
+  buf[0] = '-';
+
+  for (i = 1; ISDIGIT (c = getc (fp)); i++)
     {
     {
-      ERROR ((0, errno, _("Cannot open %s"), listed_incremental_option));
-      return;
+      if (i == sizeof buf - 1)
+       FATAL_ERROR ((0, 0, _("Field too long while reading snapshot file")));
+      buf[i] = c;
     }
     }
-  if (!fp)
-    return;
-  fgets (buf, sizeof (buf), fp);
-
-  /* FIXME: Using after_date_option as a first time flag looks fairly
-     dubious to me!  So, using -N with incremental might be buggy just
-     because of the next few lines.  I saw a few unexplained, almost harsh
-     advices, from other GNU people, about *not* using -N with incremental
-     dumps, and here might lie (part of) the reason.  */
-  if (!after_date_option)
-    {
-      newer_mtime_option = atol (buf);
-      after_date_option = 1;
-    }
-
-  while (fgets (buf, sizeof (buf), fp))
-    {
-      strp = &buf[strlen (buf)];
-      if (strp[-1] == '\n')
-       strp[-1] = '\0';
-      /* FIXME: For files ending with an incomplete line, maybe a NUL might
-        be missing, here...  */
-
-      strp = buf;
-      device_number = atol (strp);
-      while (ISDIGIT (*strp))
-       strp++;
-      inode_number = atol (strp);
-      while (ISSPACE (*strp))
-       strp++;
-      while (ISDIGIT (*strp))
-       strp++;
-      strp++;
-      unquote_string (strp);
-      note_directory (strp, device_number, inode_number, NULL);
+
+  if (c < 0)
+    {
+      if (ferror (fp))
+       FATAL_ERROR ((0, errno, _("Read error in snapshot file")));
+      else
+       FATAL_ERROR ((0, 0, _("Unexpected EOF in snapshot file")));
     }
     }
-  if (fclose (fp) == EOF)
-    ERROR ((0, errno, "%s", listed_incremental_option));
+
+  buf[i] = 0;
+  errno = 0;
+  *pval = strtoimax (buf, &ep, 10);
+  if (c || errno || *pval < min_val)
+    FATAL_ERROR ((0, errno, _("Unexpected field value in snapshot file")));
 }
 
 }
 
-/*---.
-| ?  |
-`---*/
+/* Read from file FP a nul-terminated string and convert it to
+   uintmax_t.  Return the resulting value in PVAL.  Assume C has
+   already been read.
 
 
-void
-write_dir_file (void)
+   Throw a fatal error if the string cannot be converted or if the
+   converted value exceeds MAX_VAL.
+
+   Return the last character read or EOF on end of file. */
+
+static int
+read_unsigned_num (int c, FILE *fp, uintmax_t max_val, uintmax_t *pval)
 {
 {
-  FILE *fp;
-  struct directory *directory;
-  char *str;
+  size_t i;
+  char buf[UINTMAX_STRSIZE_BOUND], *ep;
 
 
-  fp = fopen (listed_incremental_option, "w");
-  if (fp == 0)
+  for (i = 0; ISDIGIT (c); i++)
     {
     {
-      ERROR ((0, errno, _("Cannot write to %s"), listed_incremental_option));
-      return;
+      if (i == sizeof buf - 1)
+       FATAL_ERROR ((0, 0, _("Field too long while reading snapshot file")));
+      buf[i] = c;
+      c = getc (fp);
     }
     }
-  fprintf (fp, "%lu\n", time_now);
-  for (directory = directory_list; directory; directory = directory->next)
+
+  if (c < 0)
     {
     {
-      if (!directory->dir_text)
-       continue;
-      str = quote_copy_string (directory->name);
-      if (str)
-       {
-         fprintf (fp, "%u %u %s\n", directory->device_number,
-                  directory->inode_number, str);
-         free (str);
-       }
+      if (ferror (fp))
+       FATAL_ERROR ((0, errno, _("Read error in snapshot file")));
+      else if (i == 0)
+       return c;
       else
       else
-       fprintf (fp, "%u %u %s\n", directory->device_number,
-                directory->inode_number, directory->name);
+       FATAL_ERROR ((0, 0, _("Unexpected EOF in snapshot file")));
     }
     }
-  if (fclose (fp) == EOF)
-    ERROR ((0, errno, "%s", listed_incremental_option));
+
+  buf[i] = 0;
+  errno = 0;
+  *pval = strtoumax (buf, &ep, 10);
+  if (c || errno || max_val < *pval)
+    FATAL_ERROR ((0, errno, _("Unexpected field value in snapshot file")));
+  return c;
 }
 
 }
 
-/*---.
-| ?  |
-`---*/
+/* Read from file FP a nul-terminated string and convert it to
+   uintmax_t.  Return the resulting value in PVAL.
+
+   Throw a fatal error if the string cannot be converted or if the
+   converted value exceeds MAX_VAL.
+
+   Return the last character read or EOF on end of file. */
 
 static int
 
 static int
-compare_names (char *param1, char *param2)
+read_num (FILE *fp, uintmax_t max_val, uintmax_t *pval)
 {
 {
-  struct name *n1 = (struct name *) param1;
-  struct name *n2 = (struct name *) param2;
+  return read_unsigned_num (getc (fp), fp, max_val, pval);
+}
 
 
-  if (n1->found)
-    return n2->found ? strcmp (n1->name, n2->name) : -1;
+/* Read from FP two NUL-terminated strings representing a struct
+   timespec.  Return the resulting value in PVAL.
 
 
-  if (n2->found)
-    return 1;
+   Throw a fatal error if the string cannot be converted.  */
 
 
-  return strcmp (n1->name, n2->name);
-}
+static void
+read_timespec (FILE *fp, struct timespec *pval)
+{
+  int c = getc (fp);
+  intmax_t i;
+  uintmax_t u;
+
+  if (c == '-')
+    {
+      read_negative_num (fp, TYPE_MINIMUM (time_t), &i);
+      c = 0;
+      pval->tv_sec = i;
+    }
+  else
+    {
+      c = read_unsigned_num (c, fp, TYPE_MAXIMUM (time_t), &u);
+      pval->tv_sec = u;
+    }
 
 
-/*-------------------------------------------------------------------------.
-| Collect all the names from argv[] (or whatever), then expand them into a |
-| directory tree, and put all the directories at the beginning.                   |
-`-------------------------------------------------------------------------*/
+  if (c || read_num (fp, BILLION - 1, &u))
+    FATAL_ERROR ((0, 0, "%s: %s",
+                 quotearg_colon (listed_incremental_option),
+                 _("Unexpected EOF in snapshot file")));
+  pval->tv_nsec = u;
+}
 
 
-void
-collect_and_sort_names (void)
+/* Read incremental snapshot format 2 */
+static void
+read_incr_db_2 ()
 {
 {
-  struct name *name;
-  struct name *next_name;
-  int num_names;
-  struct stat statbuf;
+  uintmax_t u;
+  struct obstack stk;
+
+  obstack_init (&stk);
+
+  read_timespec (listed_incremental_stream, &newer_mtime_option);
+
+  for (;;)
+    {
+      struct timespec mtime;
+      dev_t dev;
+      ino_t ino;
+      bool nfs;
+      char *name;
+      char *content;
+      size_t s;
+
+      if (read_num (listed_incremental_stream, 1, &u))
+       return; /* Normal return */
+
+      nfs = u;
+
+      read_timespec (listed_incremental_stream, &mtime);
+
+      if (read_num (listed_incremental_stream, TYPE_MAXIMUM (dev_t), &u))
+       break;
+      dev = u;
 
 
-  name_gather ();
+      if (read_num (listed_incremental_stream, TYPE_MAXIMUM (ino_t), &u))
+       break;
+      ino = u;
 
 
-  if (listed_incremental_option)
-    read_directory_file ();
+      if (read_obstack (listed_incremental_stream, &stk, &s))
+       break;
 
 
-  if (!namelist)
-    addname (".");
+      name = obstack_finish (&stk);
 
 
-  for (name = namelist; name; name = next_name)
+      while (read_obstack (listed_incremental_stream, &stk, &s) == 0 && s > 1)
+       ;
+      if (getc (listed_incremental_stream) != 0)
+       FATAL_ERROR ((0, 0, "%s: %s",
+                     quotearg_colon (listed_incremental_option),
+                     _("Missing record terminator")));
+
+      content = obstack_finish (&stk);
+      note_directory (name, mtime, dev, ino, nfs, false, content);
+      obstack_free (&stk, content);
+    }
+  FATAL_ERROR ((0, 0, "%s: %s",
+               quotearg_colon (listed_incremental_option),
+               _("Unexpected EOF in snapshot file")));
+}
+
+/* Read incremental snapshot file (directory file).
+   If the file has older incremental version, make sure that it is processed
+   correctly and that tar will use the most conservative backup method among
+   possible alternatives (i.e. prefer ALL_CHILDREN over CHANGED_CHILDREN,
+   etc.) This ensures that the snapshots are updated to the recent version
+   without any loss of data. */
+void
+read_directory_file (void)
+{
+  int fd;
+  char *buf = 0;
+  size_t bufsize;
+
+  /* Open the file for both read and write.  That way, we can write
+     it later without having to reopen it, and don't have to worry if
+     we chdir in the meantime.  */
+  fd = open (listed_incremental_option, O_RDWR | O_CREAT, MODE_RW);
+  if (fd < 0)
     {
     {
-      next_name = name->next;
-      if (name->found || name->dir_contents)
-       continue;
-      if (name->regexp)                /* FIXME: just skip regexps for now */
-       continue;
-      if (name->change_dir)
-       if (chdir (name->change_dir) < 0)
-         {
-           ERROR ((0, errno, _("Cannot chdir to %s"), name->change_dir));
-           continue;
-         }
+      open_error (listed_incremental_option);
+      return;
+    }
 
 
-      if (
-#ifdef AIX
-         statx (name->name, &statbuf, STATSIZE, STX_HIDDEN | STX_LINK)
-#else
-         lstat (name->name, &statbuf) < 0
-#endif
-         )
+  listed_incremental_stream = fdopen (fd, "r+");
+  if (! listed_incremental_stream)
+    {
+      open_error (listed_incremental_option);
+      close (fd);
+      return;
+    }
+
+  if (0 < getline (&buf, &bufsize, listed_incremental_stream))
+    {
+      char *ebuf;
+      uintmax_t incremental_version;
+
+      if (strncmp (buf, PACKAGE_NAME, sizeof PACKAGE_NAME - 1) == 0)
        {
        {
-         ERROR ((0, errno, _("Cannot stat %s"), name->name));
-         continue;
+         ebuf = buf + sizeof PACKAGE_NAME - 1;
+         if (*ebuf++ != '-')
+           ERROR((1, 0, _("Bad incremental file format")));
+         for (; *ebuf != '-'; ebuf++)
+           if (!*ebuf)
+             ERROR((1, 0, _("Bad incremental file format")));
+
+         incremental_version = strtoumax (ebuf + 1, NULL, 10);
        }
        }
-      if (S_ISDIR (statbuf.st_mode))
+      else
+       incremental_version = 0;
+
+      switch (incremental_version)
        {
        {
-         name->found = 1;
-         add_hierarchy_to_namelist (name->name, statbuf.st_dev);
+       case 0:
+       case 1:
+         read_incr_db_01 (incremental_version, buf);
+         break;
+
+       case TAR_INCREMENTAL_VERSION:
+         read_incr_db_2 ();
+         break;
+
+       default:
+         ERROR ((1, 0, _("Unsupported incremental format version: %"PRIuMAX),
+                 incremental_version));
        }
        }
+
     }
 
     }
 
-  num_names = 0;
-  for (name = namelist; name; name = name->next)
-    num_names++;
-  namelist = (struct name *)
-    merge_sort ((voidstar) namelist, num_names,
-               (char *) (&(namelist->next)) - (char *) namelist,
-               compare_names);
+  if (ferror (listed_incremental_stream))
+    read_error (listed_incremental_option);
+  if (buf)
+    free (buf);
+}
 
 
-  for (name = namelist; name; name = name->next)
-    name->found = 0;
+/* Output incremental data for the directory ENTRY to the file DATA.
+   Return nonzero if successful, preserving errno on write failure.  */
+static bool
+write_directory_file_entry (void *entry, void *data)
+{
+  struct directory const *directory = entry;
+  FILE *fp = data;
 
 
-  if (listed_incremental_option)
-    write_dir_file ();
-}
-\f
-/* Restoration of incremental dumps.  */
+  if (DIR_IS_FOUND (directory))
+    {
+      char buf[UINTMAX_STRSIZE_BOUND];
+      char *s;
+
+      s = DIR_IS_NFS (directory) ? "1" : "0";
+      fwrite (s, 2, 1, fp);
+      s = (TYPE_SIGNED (time_t)
+          ? imaxtostr (directory->mtime.tv_sec, buf)
+          : umaxtostr (directory->mtime.tv_sec, buf));
+      fwrite (s, strlen (s) + 1, 1, fp);
+      s = umaxtostr (directory->mtime.tv_nsec, buf);
+      fwrite (s, strlen (s) + 1, 1, fp);
+      s = umaxtostr (directory->device_number, buf);
+      fwrite (s, strlen (s) + 1, 1, fp);
+      s = umaxtostr (directory->inode_number, buf);
+      fwrite (s, strlen (s) + 1, 1, fp);
+
+      fwrite (directory->name, strlen (directory->name) + 1, 1, fp);
+      if (directory->contents)
+       {
+         char *p;
+         for (p = directory->contents; *p; p += strlen (p) + 1)
+           {
+             if (strchr ("YND", *p))
+               fwrite (p, strlen (p) + 1, 1, fp);
+           }
+       }
+      fwrite ("\0\0", 2, 1, fp);
+    }
 
 
-/*---.
-| ?  |
-`---*/
+  return ! ferror (fp);
+}
 
 void
 
 void
-gnu_restore (int skipcrud)
+write_directory_file (void)
 {
 {
-  char *current_dir;
-  char *archive_dir;
-  struct accumulator *accumulator;
-  char *p;
-  DIR *dirp;
-  struct dirent *d;
-  char *cur, *arc;
-  long size, copied;
-  union block *data_block;
-  char *to;
+  FILE *fp = listed_incremental_stream;
+  char buf[UINTMAX_STRSIZE_BOUND];
+  char *s;
 
 
-#define CURRENT_FILE_NAME (skipcrud + current_file_name)
+  if (! fp)
+    return;
 
 
-  dirp = opendir (CURRENT_FILE_NAME);
+  if (fseek (fp, 0L, SEEK_SET) != 0)
+    seek_error (listed_incremental_option);
+  if (sys_truncate (fileno (fp)) != 0)
+    truncate_error (listed_incremental_option);
 
 
-  if (!dirp)
-    {
-      /* The directory doesn't exist now.  It'll be created.  In any
-        case, we don't have to delete any files out of it.  */
+  fprintf (fp, "%s-%s-%d\n", PACKAGE_NAME, PACKAGE_VERSION,
+          TAR_INCREMENTAL_VERSION);
 
 
-      skip_file ((long) current_stat.st_size);
-      return;
-    }
+  s = (TYPE_SIGNED (time_t)
+       ? imaxtostr (start_time.tv_sec, buf)
+       : umaxtostr (start_time.tv_sec, buf));
+  fwrite (s, strlen (s) + 1, 1, fp);
+  s = umaxtostr (start_time.tv_nsec, buf);
+  fwrite (s, strlen (s) + 1, 1, fp);
 
 
-  accumulator = new_accumulator ();
-  while (d = readdir (dirp), d)
-    {
-      if (is_dot_or_dotdot (d->d_name))
-       continue;
+  if (! ferror (fp) && directory_table)
+    hash_do_for_each (directory_table, write_directory_file_entry, fp);
 
 
-      add_to_accumulator (accumulator, d->d_name, (int) (NAMLEN (d) + 1));
-    }
-  closedir (dirp);
-  add_to_accumulator (accumulator, "", 1);
+  if (ferror (fp))
+    write_error (listed_incremental_option);
+  if (fclose (fp) != 0)
+    close_error (listed_incremental_option);
+}
+
+\f
+/* Restoration of incremental dumps.  */
+
+static void
+get_gnu_dumpdir (struct tar_stat_info *stat_info)
+{
+  size_t size;
+  size_t copied;
+  union block *data_block;
+  char *to;
+  char *archive_dir;
+
+  size = stat_info->stat.st_size;
 
 
-  current_dir = get_accumulator (accumulator);
-  archive_dir = (char *) xmalloc ((size_t) current_stat.st_size);
+  archive_dir = xmalloc (size);
   to = archive_dir;
   to = archive_dir;
-  for (size = current_stat.st_size; size > 0; size -= copied)
+
+  set_next_block_after (current_header);
+  mv_begin (stat_info);
+
+  for (; size > 0; size -= copied)
     {
     {
+      mv_size_left (size);
       data_block = find_next_block ();
       if (!data_block)
       data_block = find_next_block ();
       if (!data_block)
-       {
-         ERROR ((0, 0, _("Unexpected EOF in archive")));
-         break;                /* FIXME: What happens then?  */
-       }
+       ERROR ((1, 0, _("Unexpected EOF in archive")));
       copied = available_space_after (data_block);
       if (copied > size)
        copied = size;
       copied = available_space_after (data_block);
       if (copied > size)
        copied = size;
-      memcpy (to, data_block->buffer, (size_t) copied);
+      memcpy (to, data_block->buffer, copied);
       to += copied;
       set_next_block_after ((union block *)
                            (data_block->buffer + copied - 1));
     }
 
       to += copied;
       set_next_block_after ((union block *)
                            (data_block->buffer + copied - 1));
     }
 
+  mv_end ();
+
+  stat_info->dumpdir = archive_dir;
+  stat_info->skipped = true; /* For skip_member() and friends
+                               to work correctly */
+}
+
+/* Return T if STAT_INFO represents a dumpdir archive member.
+   Note: can invalidate current_header. It happens if flush_archive()
+   gets called within get_gnu_dumpdir() */
+bool
+is_dumpdir (struct tar_stat_info *stat_info)
+{
+  if (stat_info->is_dumpdir && !stat_info->dumpdir)
+    get_gnu_dumpdir (stat_info);
+  return stat_info->is_dumpdir;
+}
+
+static bool
+dumpdir_ok (char *dumpdir)
+{
+  char *p;
+  int has_tempdir = 0;
+  int expect = 0;
+
+  for (p = dumpdir; *p; p += strlen (p) + 1)
+    {
+      if (expect && *p != expect)
+       {
+         ERROR ((0, 0,
+                 _("Malformed dumpdir: expected '%c' but found %#3o"),
+                 expect, *p));
+         return false;
+       }
+      switch (*p)
+       {
+       case 'X':
+         if (has_tempdir)
+           {
+             ERROR ((0, 0,
+                     _("Malformed dumpdir: 'X' duplicated")));
+             return false;
+           }
+         else
+           has_tempdir = 1;
+         break;
+
+       case 'R':
+         if (p[1] == 0)
+           {
+             if (!has_tempdir)
+               {
+                 ERROR ((0, 0,
+                         _("Malformed dumpdir: empty name in 'R'")));
+                 return false;
+               }
+             else
+               has_tempdir = 0;
+           }
+         expect = 'T';
+         break;
+
+       case 'T':
+         if (expect != 'T')
+           {
+             ERROR ((0, 0,
+                     _("Malformed dumpdir: 'T' not preceeded by 'R'")));
+             return false;
+           }
+         if (p[1] == 0 && !has_tempdir)
+           {
+             ERROR ((0, 0,
+                     _("Malformed dumpdir: empty name in 'T'")));
+             return false;
+           }
+         expect = 0;
+         break;
+
+       case 'N':
+       case 'Y':
+       case 'D':
+         break;
+
+       default:
+         /* FIXME: bail out? */
+         break;
+       }
+    }
+
+  if (expect)
+    {
+      ERROR ((0, 0,
+             _("Malformed dumpdir: expected '%c' but found end of data"),
+             expect));
+      return false;
+    }
+
+  if (has_tempdir)
+    WARN ((0, 0, _("Malformed dumpdir: 'X' never used")));
+
+  return true;
+}
+
+/* Examine the directories under directory_name and delete any
+   files that were not there at the time of the back-up. */
+static bool
+try_purge_directory (char const *directory_name)
+{
+  char *current_dir;
+  char *cur, *arc, *p;
+  char *temp_stub = NULL;
+
+  if (!is_dumpdir (&current_stat_info))
+    return false;
+
+  current_dir = savedir (directory_name);
+
+  if (!current_dir)
+    /* The directory doesn't exist now.  It'll be created.  In any
+       case, we don't have to delete any files out of it.  */
+    return false;
+
+  /* Verify if dump directory is sane */
+  if (!dumpdir_ok (current_stat_info.dumpdir))
+    return false;
+
+  /* Process renames */
+  for (arc = current_stat_info.dumpdir; *arc; arc += strlen (arc) + 1)
+    {
+      if (*arc == 'X')
+       {
+#define TEMP_DIR_TEMPLATE "tar.XXXXXX"
+         size_t len = strlen (arc + 1);
+         temp_stub = xrealloc (temp_stub, len + 1 + sizeof TEMP_DIR_TEMPLATE);
+         memcpy (temp_stub, arc + 1, len);
+         temp_stub[len] = '/';
+         memcpy (temp_stub + len + 1, TEMP_DIR_TEMPLATE,
+                 sizeof TEMP_DIR_TEMPLATE);
+         if (!mkdtemp (temp_stub))
+           {
+             ERROR ((0, errno,
+                     _("Cannot create temporary directory using template %s"),
+                     quote (temp_stub)));
+             free (temp_stub);
+             free (current_dir);
+             return false;
+           }
+       }
+      else if (*arc == 'R')
+       {
+         char *src, *dst;
+         src = arc + 1;
+         arc += strlen (arc) + 1;
+         dst = arc + 1;
+
+         if (*src == 0)
+           src = temp_stub;
+         else if (*dst == 0)
+           dst = temp_stub;
+
+         if (!rename_directory (src, dst))
+           {
+             free (temp_stub);
+             free (current_dir);
+             /* FIXME: Make sure purge_directory(dst) will return
+                immediately */
+             return false;
+           }
+       }
+    }
+
+  free (temp_stub);
+
+  /* Process deletes */
+  p = NULL;
   for (cur = current_dir; *cur; cur += strlen (cur) + 1)
     {
   for (cur = current_dir; *cur; cur += strlen (cur) + 1)
     {
-      for (arc = archive_dir; *arc; arc += strlen (arc) + 1)
+      const char *entry;
+      struct stat st;
+      if (p)
+       free (p);
+      p = new_name (directory_name, cur);
+
+      if (deref_stat (false, p, &st))
        {
        {
-         arc++;
-         if (!strcmp (arc, cur))
-           break;
+         if (errno != ENOENT) /* FIXME: Maybe keep a list of renamed
+                                 dirs and check it here? */
+           {
+             stat_diag (p);
+             WARN ((0, 0, _("%s: Not purging directory: unable to stat"),
+                    quotearg_colon (p)));
+           }
+         continue;
        }
        }
-      if (*arc == '\0')
+
+      if (!(entry = dumpdir_locate (current_stat_info.dumpdir, cur))
+         || (*entry == 'D' && !S_ISDIR (st.st_mode))
+         || (*entry == 'Y' && S_ISDIR (st.st_mode)))
        {
        {
-         p = new_name (CURRENT_FILE_NAME, cur);
-         if (interactive_option && !confirm ("delete", p))
+         if (one_file_system_option && st.st_dev != root_device)
            {
            {
-             free (p);
+             WARN ((0, 0,
+                    _("%s: directory is on a different device: not purging"),
+                    quotearg_colon (p)));
              continue;
            }
              continue;
            }
-         if (verbose_option)
-           fprintf (stdlis, _("%s: Deleting %s\n"), program_name, p);
-         if (!remove_any_file (p, 1))
-           ERROR ((0, errno, _("Error while deleting %s"), p));
-         free (p);
-       }
 
 
+         if (! interactive_option || confirm ("delete", p))
+           {
+             if (verbose_option)
+               fprintf (stdlis, _("%s: Deleting %s\n"),
+                        program_name, quote (p));
+             if (! remove_any_file (p, RECURSIVE_REMOVE_OPTION))
+               {
+                 int e = errno;
+                 ERROR ((0, e, _("%s: Cannot remove"), quotearg_colon (p)));
+               }
+           }
+       }
     }
     }
-  delete_accumulator (accumulator);
-  free (archive_dir);
+  free (p);
+
+  free (current_dir);
+  return true;
+}
+
+void
+purge_directory (char const *directory_name)
+{
+  if (!try_purge_directory (directory_name))
+    skip_member ();
+}
 
 
-#undef CURRENT_FILE_NAME
+void
+list_dumpdir (char *buffer, size_t size)
+{
+  int state = 0;
+  while (size)
+    {
+      switch (*buffer)
+       {
+       case 'Y':
+       case 'N':
+       case 'D':
+       case 'R':
+       case 'T':
+       case 'X':
+         fprintf (stdlis, "%c", *buffer);
+         if (state == 0)
+           {
+             fprintf (stdlis, " ");
+             state = 1;
+           }
+         buffer++;
+         size--;
+         break;
+
+       case 0:
+         fputc ('\n', stdlis);
+         buffer++;
+         size--;
+         state = 0;
+         break;
+
+       default:
+         fputc (*buffer, stdlis);
+         buffer++;
+         size--;
+       }
+    }
 }
 }
This page took 0.069458 seconds and 4 git commands to generate.