1/* GNU dump extensions to tar.
2
3   Copyright (C) 1988, 1992, 1993, 1994, 1996, 1997, 1999, 2000, 2001,
4   2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
5
6   This program is free software; you can redistribute it and/or modify it
7   under the terms of the GNU General Public License as published by the
8   Free Software Foundation; either version 2, or (at your option) any later
9   version.
10
11   This program is distributed in the hope that it will be useful, but
12   WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
14   Public License for more details.
15
16   You should have received a copy of the GNU General Public License along
17   with this program; if not, write to the Free Software Foundation, Inc.,
18   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
19
20#include <system.h>
21#include <getline.h>
22#include <hash.h>
23#include <quotearg.h>
24#include "common.h"
25
26/* Incremental dump specialities.  */
27
28/* Which child files to save under a directory.  */
29enum children
30  {
31    NO_CHILDREN,
32    CHANGED_CHILDREN,
33    ALL_CHILDREN
34  };
35
36#define DIRF_INIT     0x0001    /* directory structure is initialized
37				   (procdir called at least once) */
38#define DIRF_NFS      0x0002    /* directory is mounted on nfs */
39#define DIRF_FOUND    0x0004    /* directory is found on fs */
40#define DIRF_NEW      0x0008    /* directory is new (not found
41				   in the previous dump) */
42#define DIRF_RENAMED  0x0010    /* directory is renamed */
43
44#define DIR_IS_INITED(d) ((d)->flags & DIRF_INIT)
45#define DIR_IS_NFS(d) ((d)->flags & DIRF_NFS)
46#define DIR_IS_FOUND(d) ((d)->flags & DIRF_FOUND)
47#define DIR_IS_NEW(d) ((d)->flags & DIRF_NEW)
48#define DIR_IS_RENAMED(d) ((d)->flags & DIRF_RENAMED)
49
50#define DIR_SET_FLAG(d,f) (d)->flags |= (f)
51#define DIR_CLEAR_FLAG(d,f) (d)->flags &= ~(f)
52
53/* Directory attributes.  */
54struct directory
55  {
56    struct timespec mtime;      /* Modification time */
57    dev_t device_number;	/* device number for directory */
58    ino_t inode_number;		/* inode number for directory */
59    char *contents;             /* Directory contents */
60    char *icontents;            /* Initial contents if the directory was
61				   rescanned */
62    enum children children;     /* What to save under this directory */
63    unsigned flags;             /* See DIRF_ macros above */
64    struct directory *orig;     /* If the directory was renamed, points to
65				   the original directory structure */
66    char name[1];		/* file name of directory */
67  };
68
69static Hash_table *directory_table;
70static Hash_table *directory_meta_table;
71
72#if HAVE_ST_FSTYPE_STRING
73  static char const nfs_string[] = "nfs";
74# define NFS_FILE_STAT(st) (strcmp ((st).st_fstype, nfs_string) == 0)
75#else
76# define ST_DEV_MSB(st) (~ (dev_t) 0 << (sizeof (st).st_dev * CHAR_BIT - 1))
77# define NFS_FILE_STAT(st) (((st).st_dev & ST_DEV_MSB (st)) != 0)
78#endif
79
80/* Calculate the hash of a directory.  */
81static size_t
82hash_directory_name (void const *entry, size_t n_buckets)
83{
84  struct directory const *directory = entry;
85  return hash_string (directory->name, n_buckets);
86}
87
88/* Compare two directories for equality of their names. */
89static bool
90compare_directory_names (void const *entry1, void const *entry2)
91{
92  struct directory const *directory1 = entry1;
93  struct directory const *directory2 = entry2;
94  return strcmp (directory1->name, directory2->name) == 0;
95}
96
97static size_t
98hash_directory_meta (void const *entry, size_t n_buckets)
99{
100  struct directory const *directory = entry;
101  /* FIXME: Work out a better algorytm */
102  return (directory->device_number + directory->inode_number) % n_buckets;
103}
104
105/* Compare two directories for equality of their device and inode numbers. */
106static bool
107compare_directory_meta (void const *entry1, void const *entry2)
108{
109  struct directory const *directory1 = entry1;
110  struct directory const *directory2 = entry2;
111  return directory1->device_number == directory2->device_number
112            && directory1->inode_number == directory2->inode_number;
113}
114
115/* Make a directory entry for given NAME */
116static struct directory *
117make_directory (const char *name)
118{
119  size_t namelen = strlen (name);
120  size_t size = offsetof (struct directory, name) + namelen + 1;
121  struct directory *directory = xmalloc (size);
122  directory->contents = directory->icontents = NULL;
123  directory->orig = NULL;
124  directory->flags = false;
125  strcpy (directory->name, name);
126  if (ISSLASH (directory->name[namelen-1]))
127    directory->name[namelen-1] = 0;
128  return directory;
129}
130
131/* Create and link a new directory entry for directory NAME, having a
132   device number DEV and an inode number INO, with NFS indicating
133   whether it is an NFS device and FOUND indicating whether we have
134   found that the directory exists.  */
135static struct directory *
136note_directory (char const *name, struct timespec mtime,
137		dev_t dev, ino_t ino, bool nfs, bool found, char *contents)
138{
139  struct directory *directory = make_directory (name);
140
141  directory->mtime = mtime;
142  directory->device_number = dev;
143  directory->inode_number = ino;
144  directory->children = CHANGED_CHILDREN;
145  if (nfs)
146    DIR_SET_FLAG (directory, DIRF_NFS);
147  if (found)
148    DIR_SET_FLAG (directory, DIRF_FOUND);
149  if (contents)
150    {
151      size_t size = dumpdir_size (contents);
152      directory->contents = xmalloc (size);
153      memcpy (directory->contents, contents, size);
154    }
155  else
156    directory->contents = NULL;
157
158  if (! ((directory_table
159	  || (directory_table = hash_initialize (0, 0,
160						 hash_directory_name,
161						 compare_directory_names, 0)))
162	 && hash_insert (directory_table, directory)))
163    xalloc_die ();
164
165  if (! ((directory_meta_table
166	  || (directory_meta_table = hash_initialize (0, 0,
167						      hash_directory_meta,
168						      compare_directory_meta,
169						      0)))
170	 && hash_insert (directory_meta_table, directory)))
171    xalloc_die ();
172
173  return directory;
174}
175
176/* Return a directory entry for a given file NAME, or zero if none found.  */
177static struct directory *
178find_directory (const char *name)
179{
180  if (! directory_table)
181    return 0;
182  else
183    {
184      struct directory *dir = make_directory (name);
185      struct directory *ret = hash_lookup (directory_table, dir);
186      free (dir);
187      return ret;
188    }
189}
190
191/* Return a directory entry for a given combination of device and inode
192   numbers, or zero if none found.  */
193static struct directory *
194find_directory_meta (dev_t dev, ino_t ino)
195{
196  if (! directory_meta_table)
197    return 0;
198  else
199    {
200      struct directory *dir = make_directory ("");
201      struct directory *ret;
202      dir->device_number = dev;
203      dir->inode_number = ino;
204      ret = hash_lookup (directory_meta_table, dir);
205      free (dir);
206      return ret;
207    }
208}
209
210void
211update_parent_directory (const char *name)
212{
213  struct directory *directory;
214  char *p;
215
216  p = dir_name (name);
217  directory = find_directory (p);
218  if (directory)
219    {
220      struct stat st;
221      if (deref_stat (dereference_option, p, &st) != 0)
222	stat_diag (name);
223      else
224	directory->mtime = get_stat_mtime (&st);
225    }
226  free (p);
227}
228
229static struct directory *
230procdir (char *name_buffer, struct stat *stat_data,
231	 dev_t device,
232	 enum children children,
233	 bool verbose)
234{
235  struct directory *directory;
236  bool nfs = NFS_FILE_STAT (*stat_data);
237
238  if ((directory = find_directory (name_buffer)) != NULL)
239    {
240      if (DIR_IS_INITED (directory))
241	return directory;
242
243      /* With NFS, the same file can have two different devices
244	 if an NFS directory is mounted in multiple locations,
245	 which is relatively common when automounting.
246	 To avoid spurious incremental redumping of
247	 directories, consider all NFS devices as equal,
248	 relying on the i-node to establish differences.  */
249
250      if (! (((DIR_IS_NFS (directory) & nfs)
251	      || directory->device_number == stat_data->st_dev)
252	     && directory->inode_number == stat_data->st_ino))
253	{
254	  /* FIXME: find_directory_meta ignores nfs */
255	  struct directory *d = find_directory_meta (stat_data->st_dev,
256						     stat_data->st_ino);
257	  if (d)
258	    {
259	      if (verbose_option)
260		WARN ((0, 0, _("%s: Directory has been renamed from %s"),
261		       quotearg_colon (name_buffer),
262		       quote_n (1, d->name)));
263	      directory->orig = d;
264	      DIR_SET_FLAG (directory, DIRF_RENAMED);
265	      directory->children = CHANGED_CHILDREN;
266	    }
267	  else
268	    {
269	      if (verbose_option)
270		WARN ((0, 0, _("%s: Directory has been renamed"),
271		       quotearg_colon (name_buffer)));
272	      directory->children = ALL_CHILDREN;
273	      directory->device_number = stat_data->st_dev;
274	      directory->inode_number = stat_data->st_ino;
275	    }
276	  if (nfs)
277	    DIR_SET_FLAG (directory, DIRF_NFS);
278	}
279      else
280	directory->children = CHANGED_CHILDREN;
281
282      DIR_SET_FLAG (directory, DIRF_FOUND);
283    }
284  else
285    {
286      struct directory *d = find_directory_meta (stat_data->st_dev,
287						 stat_data->st_ino);
288
289      directory = note_directory (name_buffer,
290				  get_stat_mtime(stat_data),
291				  stat_data->st_dev,
292				  stat_data->st_ino,
293				  nfs,
294				  true,
295				  NULL);
296
297      if (d)
298	{
299	  if (verbose)
300	    WARN ((0, 0, _("%s: Directory has been renamed from %s"),
301		   quotearg_colon (name_buffer),
302		   quote_n (1, d->name)));
303	  directory->orig = d;
304	  DIR_SET_FLAG (directory, DIRF_RENAMED);
305	  directory->children = CHANGED_CHILDREN;
306	}
307      else
308	{
309	  DIR_SET_FLAG (directory, DIRF_NEW);
310	  if (verbose)
311	    WARN ((0, 0, _("%s: Directory is new"),
312		   quotearg_colon (name_buffer)));
313	  directory->children =
314	    (listed_incremental_option
315	     || (OLDER_STAT_TIME (*stat_data, m)
316		 || (after_date_option
317		     && OLDER_STAT_TIME (*stat_data, c))))
318	    ? ALL_CHILDREN
319	    : CHANGED_CHILDREN;
320	}
321    }
322
323  /* If the directory is on another device and --one-file-system was given,
324     omit it... */
325  if (one_file_system_option && device != stat_data->st_dev
326      /* ... except if it was explicitely given in the command line */
327      && !is_individual_file (name_buffer))
328    directory->children = NO_CHILDREN;
329  else if (children == ALL_CHILDREN)
330    directory->children = ALL_CHILDREN;
331
332  DIR_SET_FLAG (directory, DIRF_INIT);
333
334  return directory;
335}
336
337/* Locate NAME in the dumpdir array DUMP.
338   Return pointer to the slot in the array, or NULL if not found */
339const char *
340dumpdir_locate (const char *dump, const char *name)
341{
342  if (dump)
343    while (*dump)
344      {
345	/* Ignore 'R' (rename) and 'X' (tempname) entries, since they break
346	   alphabetical ordering.
347	   They normally do not occur in dumpdirs from the snapshot files,
348	   but this function is also used by purge_directory, which operates
349	   on a dumpdir from the archive, hence the need for this test. */
350	if (!strchr ("RX", *dump))
351	  {
352	    int rc = strcmp (dump + 1, name);
353	    if (rc == 0)
354	      return dump;
355	    if (rc > 1)
356	      break;
357	  }
358	dump += strlen (dump) + 1;
359      }
360  return NULL;
361}
362
363/* Return size in bytes of the dumpdir array P */
364size_t
365dumpdir_size (const char *p)
366{
367  size_t totsize = 0;
368
369  while (*p)
370    {
371      size_t size = strlen (p) + 1;
372      totsize += size;
373      p += size;
374    }
375  return totsize + 1;
376}
377
378static int
379compare_dirnames (const void *first, const void *second)
380{
381  char const *const *name1 = first;
382  char const *const *name2 = second;
383  return strcmp (*name1, *name2);
384}
385
386/* Compare dumpdir array from DIRECTORY with directory listing DIR and
387   build a new dumpdir template.
388
389   DIR must be returned by a previous call to savedir().
390
391   File names in DIRECTORY->contents must be sorted
392   alphabetically.
393
394   DIRECTORY->contents is replaced with the created template. Each entry is
395   prefixed with ' ' if it was present in DUMP and with 'Y' otherwise. */
396
397void
398makedumpdir (struct directory *directory, const char *dir)
399{
400  size_t i,
401         dirsize,  /* Number of elements in DIR */
402         len;      /* Length of DIR, including terminating nul */
403  const char *p;
404  char const **array;
405  char *new_dump, *new_dump_ptr;
406  const char *dump;
407
408  if (directory->children == ALL_CHILDREN)
409    dump = NULL;
410  else if (DIR_IS_RENAMED (directory))
411    dump = directory->orig->icontents ?
412              directory->orig->icontents : directory->orig->contents;
413  else
414    dump = directory->contents;
415
416  /* Count the size of DIR and the number of elements it contains */
417  dirsize = 0;
418  len = 0;
419  for (p = dir; *p; p += strlen (p) + 1, dirsize++)
420    len += strlen (p) + 2;
421  len++;
422
423  /* Create a sorted directory listing */
424  array = xcalloc (dirsize, sizeof array[0]);
425  for (i = 0, p = dir; *p; p += strlen (p) + 1, i++)
426    array[i] = p;
427
428  qsort (array, dirsize, sizeof (array[0]), compare_dirnames);
429
430  /* Prepare space for new dumpdir */
431  new_dump = xmalloc (len);
432  new_dump_ptr = new_dump;
433
434  /* Fill in the dumpdir template */
435  for (i = 0; i < dirsize; i++)
436    {
437      const char *loc = dumpdir_locate (dump, array[i]);
438      if (loc)
439	{
440	  *new_dump_ptr++ = ' ';
441	  dump = loc + strlen (loc) + 1;
442	}
443      else
444	*new_dump_ptr++ = 'Y'; /* New entry */
445
446      /* Copy the file name */
447      for (p = array[i]; (*new_dump_ptr++ = *p++); )
448	;
449    }
450  *new_dump_ptr = 0;
451  directory->icontents = directory->contents;
452  directory->contents = new_dump;
453  free (array);
454}
455
456/* Recursively scan the given directory. */
457static char *
458scan_directory (char *dir_name, dev_t device)
459{
460  char *dirp = savedir (dir_name);	/* for scanning directory */
461  char *name_buffer;		/* directory, `/', and directory member */
462  size_t name_buffer_size;	/* allocated size of name_buffer, minus 2 */
463  size_t name_length;		/* used length in name_buffer */
464  struct stat stat_data;
465  struct directory *directory;
466
467  if (! dirp)
468    savedir_error (dir_name);
469
470  name_buffer_size = strlen (dir_name) + NAME_FIELD_SIZE;
471  name_buffer = xmalloc (name_buffer_size + 2);
472  strcpy (name_buffer, dir_name);
473  if (! ISSLASH (dir_name[strlen (dir_name) - 1]))
474    strcat (name_buffer, "/");
475  name_length = strlen (name_buffer);
476
477  if (deref_stat (dereference_option, name_buffer, &stat_data))
478    {
479      stat_diag (name_buffer);
480      /* FIXME: used to be
481           children = CHANGED_CHILDREN;
482	 but changed to: */
483      free (name_buffer);
484      free (dirp);
485      return NULL;
486    }
487
488  directory = procdir (name_buffer, &stat_data, device, NO_CHILDREN, false);
489
490  if (dirp && directory->children != NO_CHILDREN)
491    {
492      char  *entry;	/* directory entry being scanned */
493      size_t entrylen;	/* length of directory entry */
494
495      makedumpdir (directory, dirp);
496
497      for (entry = directory->contents;
498	   (entrylen = strlen (entry)) != 0;
499	   entry += entrylen + 1)
500	{
501	  if (name_buffer_size <= entrylen - 1 + name_length)
502	    {
503	      do
504		name_buffer_size += NAME_FIELD_SIZE;
505	      while (name_buffer_size <= entrylen - 1 + name_length);
506	      name_buffer = xrealloc (name_buffer, name_buffer_size + 2);
507	    }
508	  strcpy (name_buffer + name_length, entry + 1);
509
510	  if (excluded_name (name_buffer))
511	    *entry = 'N';
512	  else
513	    {
514	      if (deref_stat (dereference_option, name_buffer, &stat_data))
515		{
516		  stat_diag (name_buffer);
517		  *entry = 'N';
518		  continue;
519		}
520
521	      if (S_ISDIR (stat_data.st_mode))
522		{
523		  procdir (name_buffer, &stat_data, device,
524			   directory->children,
525			   verbose_option);
526		  *entry = 'D';
527		}
528
529	      else if (one_file_system_option && device != stat_data.st_dev)
530		*entry = 'N';
531
532	      else if (*entry == 'Y')
533		/* New entry, skip further checks */;
534
535	      /* FIXME: if (S_ISHIDDEN (stat_data.st_mode))?? */
536
537	      else if (OLDER_STAT_TIME (stat_data, m)
538		       && (!after_date_option
539			   || OLDER_STAT_TIME (stat_data, c)))
540		*entry = 'N';
541	      else
542		*entry = 'Y';
543	    }
544	}
545    }
546
547  free (name_buffer);
548  if (dirp)
549    free (dirp);
550
551  return directory->contents;
552}
553
554char *
555get_directory_contents (char *dir_name, dev_t device)
556{
557  return scan_directory (dir_name, device);
558}
559
560
561static void
562obstack_code_rename (struct obstack *stk, char *from, char *to)
563{
564  obstack_1grow (stk, 'R');
565  obstack_grow (stk, from, strlen (from) + 1);
566  obstack_1grow (stk, 'T');
567  obstack_grow (stk, to, strlen (to) + 1);
568}
569
570static bool
571rename_handler (void *data, void *proc_data)
572{
573  struct directory *dir = data;
574  struct obstack *stk = proc_data;
575
576  if (DIR_IS_RENAMED (dir))
577    {
578      struct directory *prev, *p;
579
580      /* Detect eventual cycles and clear DIRF_RENAMED flag, so these entries
581	 are ignored when hit by this function next time.
582	 If the chain forms a cycle, prev points to the entry DIR is renamed
583	 from. In this case it still retains DIRF_RENAMED flag, which will be
584	 cleared in the `else' branch below */
585      for (prev = dir; prev && prev->orig != dir; prev = prev->orig)
586	DIR_CLEAR_FLAG (prev, DIRF_RENAMED);
587
588      if (prev == NULL)
589	{
590	  for (p = dir; p && p->orig; p = p->orig)
591	    obstack_code_rename (stk, p->orig->name, p->name);
592	}
593      else
594	{
595	  char *temp_name;
596
597	  DIR_CLEAR_FLAG (prev, DIRF_RENAMED);
598
599	  /* Break the cycle by using a temporary name for one of its
600	     elements.
601	     First, create a temp name stub entry. */
602	  temp_name = dir_name (dir->name);
603	  obstack_1grow (stk, 'X');
604	  obstack_grow (stk, temp_name, strlen (temp_name) + 1);
605
606	  obstack_code_rename (stk, dir->name, "");
607
608	  for (p = dir; p != prev; p = p->orig)
609	    obstack_code_rename (stk, p->orig->name, p->name);
610
611	  obstack_code_rename (stk, "", prev->name);
612	}
613    }
614  return true;
615}
616
617const char *
618append_incremental_renames (const char *dump)
619{
620  struct obstack stk;
621  size_t size;
622
623  if (directory_table == NULL)
624    return dump;
625
626  obstack_init (&stk);
627  if (dump)
628    {
629      size = dumpdir_size (dump) - 1;
630      obstack_grow (&stk, dump, size);
631    }
632  else
633    size = 0;
634
635  hash_do_for_each (directory_table, rename_handler, &stk);
636  if (obstack_object_size (&stk) != size)
637    {
638      obstack_1grow (&stk, 0);
639      dump = obstack_finish (&stk);
640    }
641  else
642    obstack_free (&stk, NULL);
643  return dump;
644}
645
646
647
648static FILE *listed_incremental_stream;
649
650/* Version of incremental format snapshots (directory files) used by this
651   tar. Currently it is supposed to be a single decimal number. 0 means
652   incremental snapshots as per tar version before 1.15.2.
653
654   The current tar version supports incremental versions from
655   0 up to TAR_INCREMENTAL_VERSION, inclusive.
656   It is able to create only snapshots of TAR_INCREMENTAL_VERSION */
657
658#define TAR_INCREMENTAL_VERSION 2
659
660/* Read incremental snapshot formats 0 and 1 */
661static void
662read_incr_db_01 (int version, const char *initbuf)
663{
664  int n;
665  uintmax_t u;
666  time_t sec;
667  long int nsec;
668  char *buf = 0;
669  size_t bufsize;
670  char *ebuf;
671  long lineno = 1;
672
673  if (version == 1)
674    {
675      if (getline (&buf, &bufsize, listed_incremental_stream) <= 0)
676	{
677	  read_error (listed_incremental_option);
678	  free (buf);
679	  return;
680	}
681      ++lineno;
682    }
683  else
684    {
685      buf = strdup (initbuf);
686      bufsize = strlen (buf) + 1;
687    }
688
689  sec = TYPE_MINIMUM (time_t);
690  nsec = -1;
691  errno = 0;
692  u = strtoumax (buf, &ebuf, 10);
693  if (!errno && TYPE_MAXIMUM (time_t) < u)
694    errno = ERANGE;
695  if (errno || buf == ebuf)
696    ERROR ((0, errno, "%s:%ld: %s",
697	    quotearg_colon (listed_incremental_option),
698	    lineno,
699	    _("Invalid time stamp")));
700  else
701    {
702      sec = u;
703
704      if (version == 1 && *ebuf)
705	{
706	  char const *buf_ns = ebuf + 1;
707	  errno = 0;
708	  u = strtoumax (buf_ns, &ebuf, 10);
709	  if (!errno && BILLION <= u)
710	    errno = ERANGE;
711	  if (errno || buf_ns == ebuf)
712	    {
713	      ERROR ((0, errno, "%s:%ld: %s",
714		      quotearg_colon (listed_incremental_option),
715		      lineno,
716		      _("Invalid time stamp")));
717	      sec = TYPE_MINIMUM (time_t);
718	    }
719	  else
720	    nsec = u;
721	}
722      else
723	{
724	  /* pre-1 incremental format does not contain nanoseconds */
725	  nsec = 0;
726	}
727    }
728  newer_mtime_option.tv_sec = sec;
729  newer_mtime_option.tv_nsec = nsec;
730
731
732  while (0 < (n = getline (&buf, &bufsize, listed_incremental_stream)))
733    {
734      dev_t dev;
735      ino_t ino;
736      bool nfs = buf[0] == '+';
737      char *strp = buf + nfs;
738      struct timespec mtime;
739
740      lineno++;
741
742      if (buf[n - 1] == '\n')
743	buf[n - 1] = '\0';
744
745      if (version == 1)
746	{
747	  errno = 0;
748	  u = strtoumax (strp, &ebuf, 10);
749	  if (!errno && TYPE_MAXIMUM (time_t) < u)
750	    errno = ERANGE;
751	  if (errno || strp == ebuf || *ebuf != ' ')
752	    {
753	      ERROR ((0, errno, "%s:%ld: %s",
754		      quotearg_colon (listed_incremental_option), lineno,
755		      _("Invalid modification time (seconds)")));
756	      sec = (time_t) -1;
757	    }
758	  else
759	    sec = u;
760	  strp = ebuf;
761
762	  errno = 0;
763	  u = strtoumax (strp, &ebuf, 10);
764	  if (!errno && BILLION <= u)
765	    errno = ERANGE;
766	  if (errno || strp == ebuf || *ebuf != ' ')
767	    {
768	      ERROR ((0, errno, "%s:%ld: %s",
769		      quotearg_colon (listed_incremental_option), lineno,
770		      _("Invalid modification time (nanoseconds)")));
771	      nsec = -1;
772	    }
773	  else
774	    nsec = u;
775	  mtime.tv_sec = sec;
776	  mtime.tv_nsec = nsec;
777	  strp = ebuf;
778	}
779      else
780	memset (&mtime, 0, sizeof mtime);
781
782      errno = 0;
783      u = strtoumax (strp, &ebuf, 10);
784      if (!errno && TYPE_MAXIMUM (dev_t) < u)
785	errno = ERANGE;
786      if (errno || strp == ebuf || *ebuf != ' ')
787	{
788	  ERROR ((0, errno, "%s:%ld: %s",
789		  quotearg_colon (listed_incremental_option), lineno,
790		  _("Invalid device number")));
791	  dev = (dev_t) -1;
792	}
793      else
794	dev = u;
795      strp = ebuf;
796
797      errno = 0;
798      u = strtoumax (strp, &ebuf, 10);
799      if (!errno && TYPE_MAXIMUM (ino_t) < u)
800	errno = ERANGE;
801      if (errno || strp == ebuf || *ebuf != ' ')
802	{
803	  ERROR ((0, errno, "%s:%ld: %s",
804		  quotearg_colon (listed_incremental_option), lineno,
805		  _("Invalid inode number")));
806	  ino = (ino_t) -1;
807	}
808      else
809	ino = u;
810      strp = ebuf;
811
812      strp++;
813      unquote_string (strp);
814      note_directory (strp, mtime, dev, ino, nfs, false, NULL);
815    }
816  free (buf);
817}
818
819/* Read a nul-terminated string from FP and store it in STK.
820   Store the number of bytes read (including nul terminator) in PCOUNT.
821
822   Return the last character read or EOF on end of file. */
823static int
824read_obstack (FILE *fp, struct obstack *stk, size_t *pcount)
825{
826  int c;
827  size_t i;
828
829  for (i = 0, c = getc (fp); c != EOF && c != 0; c = getc (fp), i++)
830    obstack_1grow (stk, c);
831  obstack_1grow (stk, 0);
832
833  *pcount = i;
834  return c;
835}
836
837/* Read from file FP a nul-terminated string and convert it to
838   intmax_t.  Return the resulting value in PVAL.  Assume '-' has
839   already been read.
840
841   Throw a fatal error if the string cannot be converted or if the
842   converted value is less than MIN_VAL.  */
843
844static void
845read_negative_num (FILE *fp, intmax_t min_val, intmax_t *pval)
846{
847  int c;
848  size_t i;
849  char buf[INT_BUFSIZE_BOUND (intmax_t)];
850  char *ep;
851  buf[0] = '-';
852
853  for (i = 1; ISDIGIT (c = getc (fp)); i++)
854    {
855      if (i == sizeof buf - 1)
856	FATAL_ERROR ((0, 0, _("Field too long while reading snapshot file")));
857      buf[i] = c;
858    }
859
860  if (c < 0)
861    {
862      if (ferror (fp))
863	FATAL_ERROR ((0, errno, _("Read error in snapshot file")));
864      else
865	FATAL_ERROR ((0, 0, _("Unexpected EOF in snapshot file")));
866    }
867
868  buf[i] = 0;
869  errno = 0;
870  *pval = strtoimax (buf, &ep, 10);
871  if (c || errno || *pval < min_val)
872    FATAL_ERROR ((0, errno, _("Unexpected field value in snapshot file")));
873}
874
875/* Read from file FP a nul-terminated string and convert it to
876   uintmax_t.  Return the resulting value in PVAL.  Assume C has
877   already been read.
878
879   Throw a fatal error if the string cannot be converted or if the
880   converted value exceeds MAX_VAL.
881
882   Return the last character read or EOF on end of file. */
883
884static int
885read_unsigned_num (int c, FILE *fp, uintmax_t max_val, uintmax_t *pval)
886{
887  size_t i;
888  char buf[UINTMAX_STRSIZE_BOUND], *ep;
889
890  for (i = 0; ISDIGIT (c); i++)
891    {
892      if (i == sizeof buf - 1)
893	FATAL_ERROR ((0, 0, _("Field too long while reading snapshot file")));
894      buf[i] = c;
895      c = getc (fp);
896    }
897
898  if (c < 0)
899    {
900      if (ferror (fp))
901	FATAL_ERROR ((0, errno, _("Read error in snapshot file")));
902      else if (i == 0)
903	return c;
904      else
905	FATAL_ERROR ((0, 0, _("Unexpected EOF in snapshot file")));
906    }
907
908  buf[i] = 0;
909  errno = 0;
910  *pval = strtoumax (buf, &ep, 10);
911  if (c || errno || max_val < *pval)
912    FATAL_ERROR ((0, errno, _("Unexpected field value in snapshot file")));
913  return c;
914}
915
916/* Read from file FP a nul-terminated string and convert it to
917   uintmax_t.  Return the resulting value in PVAL.
918
919   Throw a fatal error if the string cannot be converted or if the
920   converted value exceeds MAX_VAL.
921
922   Return the last character read or EOF on end of file. */
923
924static int
925read_num (FILE *fp, uintmax_t max_val, uintmax_t *pval)
926{
927  return read_unsigned_num (getc (fp), fp, max_val, pval);
928}
929
930/* Read from FP two NUL-terminated strings representing a struct
931   timespec.  Return the resulting value in PVAL.
932
933   Throw a fatal error if the string cannot be converted.  */
934
935static void
936read_timespec (FILE *fp, struct timespec *pval)
937{
938  int c = getc (fp);
939  intmax_t i;
940  uintmax_t u;
941
942  if (c == '-')
943    {
944      read_negative_num (fp, TYPE_MINIMUM (time_t), &i);
945      c = 0;
946      pval->tv_sec = i;
947    }
948  else
949    {
950      c = read_unsigned_num (c, fp, TYPE_MAXIMUM (time_t), &u);
951      pval->tv_sec = u;
952    }
953
954  if (c || read_num (fp, BILLION - 1, &u))
955    FATAL_ERROR ((0, 0, "%s: %s",
956		  quotearg_colon (listed_incremental_option),
957		  _("Unexpected EOF in snapshot file")));
958  pval->tv_nsec = u;
959}
960
961/* Read incremental snapshot format 2 */
962static void
963read_incr_db_2 ()
964{
965  uintmax_t u;
966  struct obstack stk;
967
968  obstack_init (&stk);
969
970  read_timespec (listed_incremental_stream, &newer_mtime_option);
971
972  for (;;)
973    {
974      struct timespec mtime;
975      dev_t dev;
976      ino_t ino;
977      bool nfs;
978      char *name;
979      char *content;
980      size_t s;
981
982      if (read_num (listed_incremental_stream, 1, &u))
983	return; /* Normal return */
984
985      nfs = u;
986
987      read_timespec (listed_incremental_stream, &mtime);
988
989      if (read_num (listed_incremental_stream, TYPE_MAXIMUM (dev_t), &u))
990	break;
991      dev = u;
992
993      if (read_num (listed_incremental_stream, TYPE_MAXIMUM (ino_t), &u))
994	break;
995      ino = u;
996
997      if (read_obstack (listed_incremental_stream, &stk, &s))
998	break;
999
1000      name = obstack_finish (&stk);
1001
1002      while (read_obstack (listed_incremental_stream, &stk, &s) == 0 && s > 1)
1003	;
1004      if (getc (listed_incremental_stream) != 0)
1005	FATAL_ERROR ((0, 0, "%s: %s",
1006		      quotearg_colon (listed_incremental_option),
1007		      _("Missing record terminator")));
1008
1009      content = obstack_finish (&stk);
1010      note_directory (name, mtime, dev, ino, nfs, false, content);
1011      obstack_free (&stk, content);
1012    }
1013  FATAL_ERROR ((0, 0, "%s: %s",
1014		quotearg_colon (listed_incremental_option),
1015		_("Unexpected EOF in snapshot file")));
1016}
1017
1018/* Read incremental snapshot file (directory file).
1019   If the file has older incremental version, make sure that it is processed
1020   correctly and that tar will use the most conservative backup method among
1021   possible alternatives (i.e. prefer ALL_CHILDREN over CHANGED_CHILDREN,
1022   etc.) This ensures that the snapshots are updated to the recent version
1023   without any loss of data. */
1024void
1025read_directory_file (void)
1026{
1027  int fd;
1028  char *buf = 0;
1029  size_t bufsize;
1030
1031  /* Open the file for both read and write.  That way, we can write
1032     it later without having to reopen it, and don't have to worry if
1033     we chdir in the meantime.  */
1034  fd = open (listed_incremental_option, O_RDWR | O_CREAT, MODE_RW);
1035  if (fd < 0)
1036    {
1037      open_error (listed_incremental_option);
1038      return;
1039    }
1040
1041  listed_incremental_stream = fdopen (fd, "r+");
1042  if (! listed_incremental_stream)
1043    {
1044      open_error (listed_incremental_option);
1045      close (fd);
1046      return;
1047    }
1048
1049  if (0 < getline (&buf, &bufsize, listed_incremental_stream))
1050    {
1051      char *ebuf;
1052      uintmax_t incremental_version;
1053
1054      if (strncmp (buf, PACKAGE_NAME, sizeof PACKAGE_NAME - 1) == 0)
1055	{
1056	  ebuf = buf + sizeof PACKAGE_NAME - 1;
1057	  if (*ebuf++ != '-')
1058	    ERROR((1, 0, _("Bad incremental file format")));
1059	  for (; *ebuf != '-'; ebuf++)
1060	    if (!*ebuf)
1061	      ERROR((1, 0, _("Bad incremental file format")));
1062
1063	  incremental_version = strtoumax (ebuf + 1, NULL, 10);
1064	}
1065      else
1066	incremental_version = 0;
1067
1068      switch (incremental_version)
1069	{
1070	case 0:
1071	case 1:
1072	  read_incr_db_01 (incremental_version, buf);
1073	  break;
1074
1075	case TAR_INCREMENTAL_VERSION:
1076	  read_incr_db_2 ();
1077	  break;
1078
1079	default:
1080	  ERROR ((1, 0, _("Unsupported incremental format version: %"PRIuMAX),
1081		  incremental_version));
1082	}
1083
1084    }
1085
1086  if (ferror (listed_incremental_stream))
1087    read_error (listed_incremental_option);
1088  if (buf)
1089    free (buf);
1090}
1091
1092/* Output incremental data for the directory ENTRY to the file DATA.
1093   Return nonzero if successful, preserving errno on write failure.  */
1094static bool
1095write_directory_file_entry (void *entry, void *data)
1096{
1097  struct directory const *directory = entry;
1098  FILE *fp = data;
1099
1100  if (DIR_IS_FOUND (directory))
1101    {
1102      char buf[UINTMAX_STRSIZE_BOUND];
1103      char *s;
1104
1105      s = DIR_IS_NFS (directory) ? "1" : "0";
1106      fwrite (s, 2, 1, fp);
1107      s = (TYPE_SIGNED (time_t)
1108	   ? imaxtostr (directory->mtime.tv_sec, buf)
1109	   : umaxtostr (directory->mtime.tv_sec, buf));
1110      fwrite (s, strlen (s) + 1, 1, fp);
1111      s = umaxtostr (directory->mtime.tv_nsec, buf);
1112      fwrite (s, strlen (s) + 1, 1, fp);
1113      s = umaxtostr (directory->device_number, buf);
1114      fwrite (s, strlen (s) + 1, 1, fp);
1115      s = umaxtostr (directory->inode_number, buf);
1116      fwrite (s, strlen (s) + 1, 1, fp);
1117
1118      fwrite (directory->name, strlen (directory->name) + 1, 1, fp);
1119      if (directory->contents)
1120	{
1121	  char *p;
1122	  for (p = directory->contents; *p; p += strlen (p) + 1)
1123	    {
1124	      if (strchr ("YND", *p))
1125		fwrite (p, strlen (p) + 1, 1, fp);
1126	    }
1127	}
1128      fwrite ("\0\0", 2, 1, fp);
1129    }
1130
1131  return ! ferror (fp);
1132}
1133
1134void
1135write_directory_file (void)
1136{
1137  FILE *fp = listed_incremental_stream;
1138  char buf[UINTMAX_STRSIZE_BOUND];
1139  char *s;
1140
1141  if (! fp)
1142    return;
1143
1144  if (fseek (fp, 0L, SEEK_SET) != 0)
1145    seek_error (listed_incremental_option);
1146  if (sys_truncate (fileno (fp)) != 0)
1147    truncate_error (listed_incremental_option);
1148
1149  fprintf (fp, "%s-%s-%d\n", PACKAGE_NAME, PACKAGE_VERSION,
1150	   TAR_INCREMENTAL_VERSION);
1151
1152  s = (TYPE_SIGNED (time_t)
1153       ? imaxtostr (start_time.tv_sec, buf)
1154       : umaxtostr (start_time.tv_sec, buf));
1155  fwrite (s, strlen (s) + 1, 1, fp);
1156  s = umaxtostr (start_time.tv_nsec, buf);
1157  fwrite (s, strlen (s) + 1, 1, fp);
1158
1159  if (! ferror (fp) && directory_table)
1160    hash_do_for_each (directory_table, write_directory_file_entry, fp);
1161
1162  if (ferror (fp))
1163    write_error (listed_incremental_option);
1164  if (fclose (fp) != 0)
1165    close_error (listed_incremental_option);
1166}
1167
1168
1169/* Restoration of incremental dumps.  */
1170
1171static void
1172get_gnu_dumpdir (struct tar_stat_info *stat_info)
1173{
1174  size_t size;
1175  size_t copied;
1176  union block *data_block;
1177  char *to;
1178  char *archive_dir;
1179
1180  size = stat_info->stat.st_size;
1181
1182  archive_dir = xmalloc (size);
1183  to = archive_dir;
1184
1185  set_next_block_after (current_header);
1186  mv_begin (stat_info);
1187
1188  for (; size > 0; size -= copied)
1189    {
1190      mv_size_left (size);
1191      data_block = find_next_block ();
1192      if (!data_block)
1193	ERROR ((1, 0, _("Unexpected EOF in archive")));
1194      copied = available_space_after (data_block);
1195      if (copied > size)
1196	copied = size;
1197      memcpy (to, data_block->buffer, copied);
1198      to += copied;
1199      set_next_block_after ((union block *)
1200			    (data_block->buffer + copied - 1));
1201    }
1202
1203  mv_end ();
1204
1205  stat_info->dumpdir = archive_dir;
1206  stat_info->skipped = true; /* For skip_member() and friends
1207				to work correctly */
1208}
1209
1210/* Return T if STAT_INFO represents a dumpdir archive member.
1211   Note: can invalidate current_header. It happens if flush_archive()
1212   gets called within get_gnu_dumpdir() */
1213bool
1214is_dumpdir (struct tar_stat_info *stat_info)
1215{
1216  if (stat_info->is_dumpdir && !stat_info->dumpdir)
1217    get_gnu_dumpdir (stat_info);
1218  return stat_info->is_dumpdir;
1219}
1220
1221static bool
1222dumpdir_ok (char *dumpdir)
1223{
1224  char *p;
1225  int has_tempdir = 0;
1226  int expect = 0;
1227
1228  for (p = dumpdir; *p; p += strlen (p) + 1)
1229    {
1230      if (expect && *p != expect)
1231	{
1232	  ERROR ((0, 0,
1233		  _("Malformed dumpdir: expected '%c' but found %#3o"),
1234		  expect, *p));
1235	  return false;
1236	}
1237      switch (*p)
1238	{
1239	case 'X':
1240	  if (has_tempdir)
1241	    {
1242	      ERROR ((0, 0,
1243		      _("Malformed dumpdir: 'X' duplicated")));
1244	      return false;
1245	    }
1246	  else
1247	    has_tempdir = 1;
1248	  break;
1249
1250	case 'R':
1251	  if (p[1] == 0)
1252	    {
1253	      if (!has_tempdir)
1254		{
1255		  ERROR ((0, 0,
1256			  _("Malformed dumpdir: empty name in 'R'")));
1257		  return false;
1258		}
1259	      else
1260		has_tempdir = 0;
1261	    }
1262	  expect = 'T';
1263	  break;
1264
1265	case 'T':
1266	  if (expect != 'T')
1267	    {
1268	      ERROR ((0, 0,
1269		      _("Malformed dumpdir: 'T' not preceeded by 'R'")));
1270	      return false;
1271	    }
1272	  if (p[1] == 0 && !has_tempdir)
1273	    {
1274	      ERROR ((0, 0,
1275		      _("Malformed dumpdir: empty name in 'T'")));
1276	      return false;
1277	    }
1278	  expect = 0;
1279	  break;
1280
1281	case 'N':
1282	case 'Y':
1283	case 'D':
1284	  break;
1285
1286	default:
1287	  /* FIXME: bail out? */
1288	  break;
1289	}
1290    }
1291
1292  if (expect)
1293    {
1294      ERROR ((0, 0,
1295	      _("Malformed dumpdir: expected '%c' but found end of data"),
1296	      expect));
1297      return false;
1298    }
1299
1300  if (has_tempdir)
1301    WARN ((0, 0, _("Malformed dumpdir: 'X' never used")));
1302
1303  return true;
1304}
1305
1306/* Examine the directories under directory_name and delete any
1307   files that were not there at the time of the back-up. */
1308static bool
1309try_purge_directory (char const *directory_name)
1310{
1311  char *current_dir;
1312  char *cur, *arc, *p;
1313  char *temp_stub = NULL;
1314
1315  if (!is_dumpdir (&current_stat_info))
1316    return false;
1317
1318  current_dir = savedir (directory_name);
1319
1320  if (!current_dir)
1321    /* The directory doesn't exist now.  It'll be created.  In any
1322       case, we don't have to delete any files out of it.  */
1323    return false;
1324
1325  /* Verify if dump directory is sane */
1326  if (!dumpdir_ok (current_stat_info.dumpdir))
1327    return false;
1328
1329  /* Process renames */
1330  for (arc = current_stat_info.dumpdir; *arc; arc += strlen (arc) + 1)
1331    {
1332      if (*arc == 'X')
1333	{
1334#define TEMP_DIR_TEMPLATE "tar.XXXXXX"
1335	  size_t len = strlen (arc + 1);
1336	  temp_stub = xrealloc (temp_stub, len + 1 + sizeof TEMP_DIR_TEMPLATE);
1337	  memcpy (temp_stub, arc + 1, len);
1338	  temp_stub[len] = '/';
1339	  memcpy (temp_stub + len + 1, TEMP_DIR_TEMPLATE,
1340		  sizeof TEMP_DIR_TEMPLATE);
1341	  if (!mkdtemp (temp_stub))
1342	    {
1343	      ERROR ((0, errno,
1344		      _("Cannot create temporary directory using template %s"),
1345		      quote (temp_stub)));
1346	      free (temp_stub);
1347	      free (current_dir);
1348	      return false;
1349	    }
1350	}
1351      else if (*arc == 'R')
1352	{
1353	  char *src, *dst;
1354	  src = arc + 1;
1355	  arc += strlen (arc) + 1;
1356	  dst = arc + 1;
1357
1358	  if (*src == 0)
1359	    src = temp_stub;
1360	  else if (*dst == 0)
1361	    dst = temp_stub;
1362
1363	  if (!rename_directory (src, dst))
1364	    {
1365	      free (temp_stub);
1366	      free (current_dir);
1367	      /* FIXME: Make sure purge_directory(dst) will return
1368		 immediately */
1369	      return false;
1370	    }
1371	}
1372    }
1373
1374  free (temp_stub);
1375
1376  /* Process deletes */
1377  p = NULL;
1378  for (cur = current_dir; *cur; cur += strlen (cur) + 1)
1379    {
1380      const char *entry;
1381      struct stat st;
1382      if (p)
1383	free (p);
1384      p = new_name (directory_name, cur);
1385
1386      if (deref_stat (false, p, &st))
1387	{
1388	  if (errno != ENOENT) /* FIXME: Maybe keep a list of renamed
1389				  dirs and check it here? */
1390	    {
1391	      stat_diag (p);
1392	      WARN ((0, 0, _("%s: Not purging directory: unable to stat"),
1393		     quotearg_colon (p)));
1394	    }
1395	  continue;
1396	}
1397
1398      if (!(entry = dumpdir_locate (current_stat_info.dumpdir, cur))
1399	  || (*entry == 'D' && !S_ISDIR (st.st_mode))
1400	  || (*entry == 'Y' && S_ISDIR (st.st_mode)))
1401	{
1402	  if (one_file_system_option && st.st_dev != root_device)
1403	    {
1404	      WARN ((0, 0,
1405		     _("%s: directory is on a different device: not purging"),
1406		     quotearg_colon (p)));
1407	      continue;
1408	    }
1409
1410	  if (! interactive_option || confirm ("delete", p))
1411	    {
1412	      if (verbose_option)
1413		fprintf (stdlis, _("%s: Deleting %s\n"),
1414			 program_name, quote (p));
1415	      if (! remove_any_file (p, RECURSIVE_REMOVE_OPTION))
1416		{
1417		  int e = errno;
1418		  ERROR ((0, e, _("%s: Cannot remove"), quotearg_colon (p)));
1419		}
1420	    }
1421	}
1422    }
1423  free (p);
1424
1425  free (current_dir);
1426  return true;
1427}
1428
1429void
1430purge_directory (char const *directory_name)
1431{
1432  if (!try_purge_directory (directory_name))
1433    skip_member ();
1434}
1435
1436void
1437list_dumpdir (char *buffer, size_t size)
1438{
1439  int state = 0;
1440  while (size)
1441    {
1442      switch (*buffer)
1443	{
1444	case 'Y':
1445	case 'N':
1446	case 'D':
1447	case 'R':
1448	case 'T':
1449	case 'X':
1450	  fprintf (stdlis, "%c", *buffer);
1451	  if (state == 0)
1452	    {
1453	      fprintf (stdlis, " ");
1454	      state = 1;
1455	    }
1456	  buffer++;
1457	  size--;
1458	  break;
1459
1460	case 0:
1461	  fputc ('\n', stdlis);
1462	  buffer++;
1463	  size--;
1464	  state = 0;
1465	  break;
1466
1467	default:
1468	  fputc (*buffer, stdlis);
1469	  buffer++;
1470	  size--;
1471	}
1472    }
1473}
1474