incremen.c

gnu tar 源码包。 tar 软件是 Unix 系统下的一个打包软件

/* GNU dump extensions to tar.

   Copyright (C) 1988, 1992, 1993, 1994, 1996, 1997, 1999, 2000, 2001,
   2003, 2004, 2005, 2006, 2007, 2008 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, 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, write to the Free Software Foundation, Inc.,
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */

#include <system.h>
#include <hash.h>
#include <quotearg.h>
#include "common.h"

/* Incremental dump specialities.  */

/* Which child files to save under a directory.  */
enum children
  {
    NO_CHILDREN,
    CHANGED_CHILDREN,
    ALL_CHILDREN
  };

#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 */

#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)

#define DIR_SET_FLAG(d,f) (d)->flags |= (f)
#define DIR_CLEAR_FLAG(d,f) (d)->flags &= ~(f)

struct dumpdir                 /* Dump directory listing */
{
  char *contents;              /* Actual contents */
  size_t total;                /* Total number of elements */
  size_t elc;                  /* Number of D/N/Y elements. */
  char **elv;                  /* Array of D/N/Y elements */
};

/* 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 */
    struct dumpdir *dump;       /* Directory contents */
    struct dumpdir *idump;      /* 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 */
    const char *tagfile;        /* Tag file, if the directory falls under
				   exclusion_tag_under */
    char name[1];		/* file name of directory */
  };

struct dumpdir *
dumpdir_create0 (const char *contents, const char *cmask)
{
  struct dumpdir *dump;
  size_t i, total, ctsize, len;
  const char *p;
  
  for (i = 0, total = 0, ctsize = 1, p = contents; *p; total++, p += len)
    {
      len = strlen (p) + 1;
      ctsize += len;
      if (!cmask || strchr (cmask, *p))
	i++;
    }
  dump = xmalloc (sizeof (*dump) + ctsize);
  dump->contents = (char*)(dump + 1);
  memcpy (dump->contents, contents, ctsize);
  dump->total = total;
  dump->elc = i;
  dump->elv = xcalloc (i + 1, sizeof (dump->elv[0]));

  for (i = 0, p = dump->contents; *p; p += strlen (p) + 1)
    {
      if (!cmask || strchr (cmask, *p))
	dump->elv[i++] = p + 1;
    }
  dump->elv[i] = NULL;
  return dump;
}

struct dumpdir *
dumpdir_create (const char *contents)
{
  return dumpdir_create0 (contents, "YND");
}

void
dumpdir_free (struct dumpdir *dump)
{
  free (dump->elv);
  free (dump);
}

static int
compare_dirnames (const void *first, const void *second)
{
  char const *const *name1 = first;
  char const *const *name2 = second;
  return strcmp (*name1, *name2);
}

/* Locate NAME in the dumpdir array DUMP.
   Return pointer to the slot in DUMP->contents, or NULL if not found */
char *
dumpdir_locate (struct dumpdir *dump, const char *name)
{
  char **ptr;
  if (!dump)
    return NULL;

  ptr = bsearch (&name, dump->elv, dump->elc, sizeof (dump->elv[0]),
		 compare_dirnames);
  return ptr ? *ptr - 1: NULL;
}

struct dumpdir_iter
{
  struct dumpdir *dump; /* Dumpdir being iterated */
  int all;              /* Iterate over all entries, not only D/N/Y */ 
  size_t next;          /* Index of the next element */
};

char *
dumpdir_next (struct dumpdir_iter *itr)
{
  size_t cur = itr->next;
  char *ret = NULL;
  
  if (itr->all)
    {
      ret = itr->dump->contents + cur;
      if (*ret == 0)
	return NULL;
      itr->next += strlen (ret) + 1;
    }
  else if (cur < itr->dump->elc)
    {
      ret = itr->dump->elv[cur] - 1;
      itr->next++;
    }

  return ret;
}

char *
dumpdir_first (struct dumpdir *dump, int all, struct dumpdir_iter **pitr)
{
  struct dumpdir_iter *itr = xmalloc (sizeof (*itr));
  itr->dump = dump;
  itr->all = all;
  itr->next = 0;
  *pitr = itr;
  return dumpdir_next (itr);
}

/* 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 Hash_table *directory_table;
static Hash_table *directory_meta_table;

#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

/* Calculate the hash of a directory.  */
static size_t
hash_directory_name (void const *entry, size_t n_buckets)
{
  struct directory const *directory = entry;
  return hash_string (directory->name, n_buckets);
}

/* 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;
}

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;
}

/* Compare two directories for equality of their device and inode numbers. */
static bool
compare_directory_meta (void const *entry1, void const *entry2)
{
  struct directory const *directory1 = entry1;
  struct directory const *directory2 = entry2;
  return directory1->device_number == directory2->device_number
            && directory1->inode_number == directory2->inode_number;
}

/* 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->dump = directory->idump = NULL;
  directory->orig = NULL;
  directory->flags = false;
  strcpy (directory->name, name);
  if (namelen && ISSLASH (directory->name[namelen - 1]))
    directory->name[namelen - 1] = 0;
  directory->tagfile = NULL;
  return directory;
}

/* 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,
		const char *contents)
{
  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)
    directory->dump = dumpdir_create (contents);
  else
    directory->dump = 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;
}

/* 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;
    }
}

/* 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)
{
  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;
    }
}

void
update_parent_directory (const char *name)
{
  struct directory *directory;
  char *p;

  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);
}

static struct directory *
procdir (char *name_buffer, struct stat *stat_data,
	 dev_t device,
	 enum children children,
	 bool verbose,
	 char *entry)
{
  struct directory *directory;
  bool nfs = NFS_FILE_STAT (*stat_data);

  if ((directory = find_directory (name_buffer)) != NULL)
    {
      if (DIR_IS_INITED (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 (! ((!check_device_option
	      || (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);

  {
    const char *tag_file_name;

    switch (check_exclusion_tags (name_buffer, &tag_file_name))
      {
      case exclusion_tag_all:
	/* This warning can be duplicated by code in dump_file0, but only
	   in case when the topmost directory being archived contains
	   an exclusion tag. */
	exclusion_tag_warning (name_buffer, tag_file_name,
			       _("directory not dumped"));
	if (entry)
	  *entry = 'N';
	directory->children = NO_CHILDREN;
	break;

      case exclusion_tag_contents:
	exclusion_tag_warning (name_buffer, tag_file_name,
			       _("contents not dumped"));
	directory->children = NO_CHILDREN;
	break;

      case exclusion_tag_under:
	exclusion_tag_warning (name_buffer, tag_file_name,
			       _("contents not dumped"));
	directory->tagfile = tag_file_name;
	break;

      case exclusion_tag_none:
	break;
      }
  }

  return directory;
}

/* Compare dumpdir array from DIRECTORY with directory listing DIR and
   build a new dumpdir template.

   DIR must be returned by a previous call to savedir().

   File names in DIRECTORY->dump->contents must be sorted
   alphabetically.

   DIRECTORY->dump 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)
{
  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;
  struct dumpdir *dump;

  if (directory->children == ALL_CHILDREN)
    dump = NULL;
  else if (DIR_IS_RENAMED (directory))
    dump = directory->orig->idump ?
           directory->orig->idump : directory->orig->dump;
  else
    dump = directory->dump;

  /* 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);