Update
[debian/tar] / src / incremen.c
1 /* GNU dump extensions to tar.
2
3    Copyright (C) 1988, 1992, 1993, 1994, 1996, 1997, 1999, 2000, 2001,
4    2003, 2004, 2005 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.  */
29 enum children {NO_CHILDREN, CHANGED_CHILDREN, ALL_CHILDREN};
30
31 /* Directory attributes.  */
32 struct directory
33   {
34     struct timespec mtime;      /* Modification time */
35     dev_t device_number;        /* device number for directory */
36     ino_t inode_number;         /* inode number for directory */
37     enum children children;
38     bool nfs;
39     bool found;
40     char name[1];               /* file name of directory */
41   };
42
43 static Hash_table *directory_table;
44
45 #if HAVE_ST_FSTYPE_STRING
46   static char const nfs_string[] = "nfs";
47 # define NFS_FILE_STAT(st) (strcmp ((st).st_fstype, nfs_string) == 0)
48 #else
49 # define ST_DEV_MSB(st) (~ (dev_t) 0 << (sizeof (st).st_dev * CHAR_BIT - 1))
50 # define NFS_FILE_STAT(st) (((st).st_dev & ST_DEV_MSB (st)) != 0)
51 #endif
52
53 /* Calculate the hash of a directory.  */
54 static size_t
55 hash_directory (void const *entry, size_t n_buckets)
56 {
57   struct directory const *directory = entry;
58   return hash_string (directory->name, n_buckets);
59 }
60
61 /* Compare two directories for equality.  */
62 static bool
63 compare_directories (void const *entry1, void const *entry2)
64 {
65   struct directory const *directory1 = entry1;
66   struct directory const *directory2 = entry2;
67   return strcmp (directory1->name, directory2->name) == 0;
68 }
69
70 /* Create and link a new directory entry for directory NAME, having a
71    device number DEV and an inode number INO, with NFS indicating
72    whether it is an NFS device and FOUND indicating whether we have
73    found that the directory exists.  */
74 static struct directory *
75 note_directory (char const *name, struct timespec mtime,
76                 dev_t dev, ino_t ino, bool nfs, bool found)
77 {
78   size_t size = offsetof (struct directory, name) + strlen (name) + 1;
79   struct directory *directory = xmalloc (size);
80
81   directory->mtime = mtime;
82   directory->device_number = dev;
83   directory->inode_number = ino;
84   directory->children = CHANGED_CHILDREN;
85   directory->nfs = nfs;
86   directory->found = found;
87   strcpy (directory->name, name);
88
89   if (! ((directory_table
90           || (directory_table = hash_initialize (0, 0, hash_directory,
91                                                  compare_directories, 0)))
92          && hash_insert (directory_table, directory)))
93     xalloc_die ();
94
95   return directory;
96 }
97
98 /* Return a directory entry for a given file NAME, or zero if none found.  */
99 static struct directory *
100 find_directory (char *name)
101 {
102   if (! directory_table)
103     return 0;
104   else
105     {
106       size_t size = offsetof (struct directory, name) + strlen (name) + 1;
107       struct directory *dir = alloca (size);
108       strcpy (dir->name, name);
109       return hash_lookup (directory_table, dir);
110     }
111 }
112
113 void
114 update_parent_directory (const char *name)
115 {
116   struct directory *directory;
117   char *p, *name_buffer;
118   
119   p = dir_name (name);
120   name_buffer = xmalloc (strlen (p) + 2);
121   strcpy (name_buffer, p);
122   if (! ISSLASH (p[strlen (p) - 1]))
123     strcat (name_buffer, "/");
124   
125   directory = find_directory (name_buffer);
126   free (name_buffer);
127   if (directory)
128     {
129       struct stat st;
130       if (deref_stat (dereference_option, p, &st) != 0)
131         stat_diag (name);
132       else
133         directory->mtime = get_stat_mtime (&st);
134     }
135   free (p);
136 }
137
138 static int
139 compare_dirents (const void *first, const void *second)
140 {
141   return strcmp ((*(char *const *) first) + 1,
142                  (*(char *const *) second) + 1);
143 }
144
145 enum children 
146 procdir (char *name_buffer, struct stat *stat_data,
147          dev_t device,
148          enum children children,
149          bool verbose)
150
151   struct directory *directory;
152   bool nfs = NFS_FILE_STAT (*stat_data);
153   
154   if ((directory = find_directory (name_buffer)) != NULL)
155     {
156       /* With NFS, the same file can have two different devices
157          if an NFS directory is mounted in multiple locations,
158          which is relatively common when automounting.
159          To avoid spurious incremental redumping of
160          directories, consider all NFS devices as equal,
161          relying on the i-node to establish differences.  */
162       
163       if (! (((directory->nfs & nfs)
164               || directory->device_number == stat_data->st_dev)
165              && directory->inode_number == stat_data->st_ino))
166         {
167           if (verbose)
168             WARN ((0, 0, _("%s: Directory has been renamed"),
169                    quotearg_colon (name_buffer)));
170           directory->children = ALL_CHILDREN;
171           directory->nfs = nfs;
172           directory->device_number = stat_data->st_dev;
173           directory->inode_number = stat_data->st_ino;
174         }
175       else if (listed_incremental_option)
176         /* Newer modification time can mean that new files were
177            created in the directory or some of the existing files
178            were renamed. */
179         directory->children =
180           timespec_cmp (get_stat_mtime (stat_data), directory->mtime) > 0
181           ? ALL_CHILDREN : CHANGED_CHILDREN;
182
183       directory->found = true;
184     }
185   else
186     {
187       if (verbose)
188         WARN ((0, 0, _("%s: Directory is new"),
189                quotearg_colon (name_buffer)));
190       directory = note_directory (name_buffer,
191                                   get_stat_mtime(stat_data),
192                                   stat_data->st_dev,
193                                   stat_data->st_ino,
194                                   nfs,
195                                   true);
196
197       directory->children =
198         (listed_incremental_option
199          || (OLDER_STAT_TIME (*stat_data, m)
200              || (after_date_option
201                  && OLDER_STAT_TIME (*stat_data, c))))
202         ? ALL_CHILDREN
203         : CHANGED_CHILDREN;
204     }
205   
206   if (one_file_system_option && device != stat_data->st_dev)
207     directory->children = NO_CHILDREN;
208   else if (children == ALL_CHILDREN)
209     directory->children = ALL_CHILDREN;
210   
211   return directory->children;
212 }
213
214
215 /* Recursively scan the given directory. */
216 static void
217 scan_directory (struct obstack *stk, char *dir_name, dev_t device)
218 {
219   char *dirp = savedir (dir_name);      /* for scanning directory */
220   char const *entry;    /* directory entry being scanned */
221   size_t entrylen;      /* length of directory entry */
222   char *name_buffer;            /* directory, `/', and directory member */
223   size_t name_buffer_size;      /* allocated size of name_buffer, minus 2 */
224   size_t name_length;           /* used length in name_buffer */
225   enum children children;
226   struct stat stat_data;
227
228   if (! dirp)
229     savedir_error (dir_name);
230
231   name_buffer_size = strlen (dir_name) + NAME_FIELD_SIZE;
232   name_buffer = xmalloc (name_buffer_size + 2);
233   strcpy (name_buffer, dir_name);
234   if (! ISSLASH (dir_name[strlen (dir_name) - 1]))
235     strcat (name_buffer, "/");
236   name_length = strlen (name_buffer);
237
238   if (deref_stat (dereference_option, name_buffer, &stat_data))
239     {
240       stat_diag (name_buffer);
241       children = CHANGED_CHILDREN;
242     }
243   else
244     children = procdir (name_buffer, &stat_data, device, NO_CHILDREN, false);
245   
246   if (dirp && children != NO_CHILDREN)
247     for (entry = dirp;
248          (entrylen = strlen (entry)) != 0;
249          entry += entrylen + 1)
250       {
251         if (name_buffer_size <= entrylen + name_length)
252           {
253             do
254               name_buffer_size += NAME_FIELD_SIZE;
255             while (name_buffer_size <= entrylen + name_length);
256             name_buffer = xrealloc (name_buffer, name_buffer_size + 2);
257           }
258         strcpy (name_buffer + name_length, entry);
259
260         if (excluded_name (name_buffer))
261           obstack_1grow (stk, 'N');
262         else
263           {
264
265             if (deref_stat (dereference_option, name_buffer, &stat_data))
266               {
267                 stat_diag (name_buffer);
268                 continue;
269               }
270
271             if (S_ISDIR (stat_data.st_mode))
272               {
273                 procdir (name_buffer, &stat_data, device, children,
274                          verbose_option);
275                 obstack_1grow (stk, 'D');
276               }
277
278             else if (one_file_system_option && device != stat_data.st_dev)
279               obstack_1grow (stk, 'N');
280
281 #ifdef S_ISHIDDEN
282             else if (S_ISHIDDEN (stat_data.st_mode))
283               {
284                 obstack_1grow (stk, 'D');
285                 obstack_grow (stk, entry, entrylen);
286                 obstack_grow (stk, "A", 2);
287                 continue;
288               }
289 #endif
290
291             else
292               if (children == CHANGED_CHILDREN
293                   && OLDER_STAT_TIME (stat_data, m)
294                   && (!after_date_option || OLDER_STAT_TIME (stat_data, c)))
295                 obstack_1grow (stk, 'N');
296               else
297                 obstack_1grow (stk, 'Y');
298           }
299
300         obstack_grow (stk, entry, entrylen + 1);
301       }
302
303   obstack_grow (stk, "\000\000", 2);
304
305   free (name_buffer);
306   if (dirp)
307     free (dirp);
308 }
309
310 /* Sort the contents of the obstack, and convert it to the char * */
311 static char *
312 sort_obstack (struct obstack *stk)
313 {
314   char *pointer = obstack_finish (stk);
315   size_t counter;
316   char *cursor;
317   char *buffer;
318   char **array;
319   char **array_cursor;
320
321   counter = 0;
322   for (cursor = pointer; *cursor; cursor += strlen (cursor) + 1)
323     counter++;
324
325   if (!counter)
326     return NULL;
327
328   array = obstack_alloc (stk, sizeof (char *) * (counter + 1));
329
330   array_cursor = array;
331   for (cursor = pointer; *cursor; cursor += strlen (cursor) + 1)
332     *array_cursor++ = cursor;
333   *array_cursor = 0;
334
335   qsort (array, counter, sizeof (char *), compare_dirents);
336
337   buffer = xmalloc (cursor - pointer + 2);
338
339   cursor = buffer;
340   for (array_cursor = array; *array_cursor; array_cursor++)
341     {
342       char *string = *array_cursor;
343
344       while ((*cursor++ = *string++))
345         continue;
346     }
347   *cursor = '\0';
348   return buffer;
349 }
350
351 char *
352 get_directory_contents (char *dir_name, dev_t device)
353 {
354   struct obstack stk;
355   char *buffer;
356
357   obstack_init (&stk);
358   scan_directory (&stk, dir_name, device);
359   buffer = sort_obstack (&stk);
360   obstack_free (&stk, NULL);
361   return buffer;
362 }
363
364 size_t
365 dumpdir_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
378 \f
379
380 static FILE *listed_incremental_stream;
381
382 /* Version of incremental format snapshots (directory files) used by this
383    tar. Currently it is supposed to be a single decimal number. 0 means
384    incremental snapshots as per tar version before 1.15.2.
385
386    The current tar version supports incremental versions from
387    0 up to TAR_INCREMENTAL_VERSION, inclusive.
388    It is able to create only snapshots of TAR_INCREMENTAL_VERSION */
389
390 #define TAR_INCREMENTAL_VERSION 1
391
392 /* Read incremental snapshot file (directory file).
393    If the file has older incremental version, make sure that it is processed
394    correctly and that tar will use the most conservative backup method among
395    possible alternatives (i.e. prefer ALL_CHILDREN over CHANGED_CHILDREN,
396    etc.) This ensures that the snapshots are updated to the recent version
397    without any loss of data. */ 
398 void
399 read_directory_file (void)
400 {
401   int fd;
402   FILE *fp;
403   char *buf = 0;
404   size_t bufsize;
405
406   /* Open the file for both read and write.  That way, we can write
407      it later without having to reopen it, and don't have to worry if
408      we chdir in the meantime.  */
409   fd = open (listed_incremental_option, O_RDWR | O_CREAT, MODE_RW);
410   if (fd < 0)
411     {
412       open_error (listed_incremental_option);
413       return;
414     }
415
416   fp = fdopen (fd, "r+");
417   if (! fp)
418     {
419       open_error (listed_incremental_option);
420       close (fd);
421       return;
422     }
423
424   listed_incremental_stream = fp;
425
426   if (0 < getline (&buf, &bufsize, fp))
427     {
428       char *ebuf;
429       int n;
430       long lineno = 1;
431       uintmax_t u;
432       time_t t = u;
433       int incremental_version;
434       
435       if (strncmp (buf, PACKAGE_NAME, sizeof PACKAGE_NAME - 1) == 0)
436         {
437           ebuf = buf + sizeof PACKAGE_NAME - 1;
438           if (*ebuf++ != '-')
439             ERROR((1, 0, _("Bad incremental file format")));
440           for (; *ebuf != '-'; ebuf++)
441             if (!*ebuf)
442               ERROR((1, 0, _("Bad incremental file format")));
443           
444           incremental_version = (errno = 0, strtoumax (ebuf+1, &ebuf, 10));
445           if (getline (&buf, &bufsize, fp) <= 0)
446             {
447               read_error (listed_incremental_option);
448               free (buf);
449               return;
450             }
451           ++lineno;
452         }
453       else
454         incremental_version = 0;
455
456       if (incremental_version > TAR_INCREMENTAL_VERSION)
457         ERROR((1, 0, _("Unsupported incremental format version: %s"),
458                incremental_version));
459       
460       t = u = (errno = 0, strtoumax (buf, &ebuf, 10));
461       if (buf == ebuf || (u == 0 && errno == EINVAL))
462         ERROR ((0, 0, "%s:%ld: %s",
463                 quotearg_colon (listed_incremental_option),
464                 lineno,
465                 _("Invalid time stamp")));
466       else if (t != u)
467         ERROR ((0, 0, "%s:%ld: %s",
468                 quotearg_colon (listed_incremental_option),
469                 lineno,
470                 _("Time stamp out of range")));
471       else if (incremental_version == 1)
472         {
473           newer_mtime_option.tv_sec = t;
474           
475           t = u = (errno = 0, strtoumax (buf, &ebuf, 10));
476           if (buf == ebuf || (u == 0 && errno == EINVAL))
477             ERROR ((0, 0, "%s:%ld: %s",
478                     quotearg_colon (listed_incremental_option),
479                     lineno,
480                     _("Invalid time stamp")));
481           else if (t != u)
482             ERROR ((0, 0, "%s:%ld: %s",
483                     quotearg_colon (listed_incremental_option),
484                     lineno,
485                     _("Time stamp out of range")));
486           newer_mtime_option.tv_nsec = t;
487         }
488       else
489         {
490           /* pre-1 incremental format does not contain nanoseconds */
491           newer_mtime_option.tv_sec = t;
492           newer_mtime_option.tv_nsec = 0;
493         }
494
495       while (0 < (n = getline (&buf, &bufsize, fp)))
496         {
497           dev_t dev;
498           ino_t ino;
499           bool nfs = buf[0] == '+';
500           char *strp = buf + nfs;
501           struct timespec mtime;
502
503           lineno++;
504
505           if (buf[n - 1] == '\n')
506             buf[n - 1] = '\0';
507
508           if (incremental_version == 1)
509             {
510               errno = 0;
511               mtime.tv_sec = u = strtoumax (strp, &ebuf, 10);
512               if (!isspace (*ebuf))
513                 ERROR ((0, 0, "%s:%ld: %s",
514                         quotearg_colon (listed_incremental_option), lineno,
515                         _("Invalid modification time (seconds)")));
516               else if (mtime.tv_sec != u) 
517                 ERROR ((0, 0, "%s:%ld: %s",
518                         quotearg_colon (listed_incremental_option), lineno,
519                         _("Modification time (seconds) out of range")));
520               strp = ebuf;
521           
522               errno = 0;
523               mtime.tv_nsec = u = strtoumax (strp, &ebuf, 10);
524               if (!isspace (*ebuf))
525                 ERROR ((0, 0, "%s:%ld: %s",
526                         quotearg_colon (listed_incremental_option), lineno,
527                         _("Invalid modification time (nanoseconds)")));
528               else if (mtime.tv_nsec != u) 
529                 ERROR ((0, 0, "%s:%ld: %s",
530                         quotearg_colon (listed_incremental_option), lineno,
531                         _("Modification time (nanoseconds) out of range")));
532               strp = ebuf;
533             }
534           else
535             memset (&mtime, 0, sizeof mtime);
536           
537           errno = 0;
538           dev = u = strtoumax (strp, &ebuf, 10);
539           if (!isspace (*ebuf))
540             ERROR ((0, 0, "%s:%ld: %s",
541                     quotearg_colon (listed_incremental_option), lineno,
542                     _("Invalid device number")));
543           else if (dev != u) 
544             ERROR ((0, 0, "%s:%ld: %s",
545                     quotearg_colon (listed_incremental_option), lineno,
546                     _("Device number out of range")));
547           strp = ebuf;
548
549           errno = 0;
550           ino = u = strtoumax (strp, &ebuf, 10);
551           if (!isspace (*ebuf))
552             ERROR ((0, 0, "%s:%ld: %s",
553                     quotearg_colon (listed_incremental_option), lineno,
554                     _("Invalid inode number")));
555           else if (ino != u)
556             ERROR ((0, 0, "%s:%ld: %s",
557                     quotearg_colon (listed_incremental_option), lineno,
558                     _("Inode number out of range")));
559           strp = ebuf;
560
561           strp++;
562           unquote_string (strp);
563           note_directory (strp, mtime, dev, ino, nfs, 0);
564         }
565     }
566
567   if (ferror (fp))
568     read_error (listed_incremental_option);
569   if (buf)
570     free (buf);
571 }
572
573 /* Output incremental data for the directory ENTRY to the file DATA.
574    Return nonzero if successful, preserving errno on write failure.  */
575 static bool
576 write_directory_file_entry (void *entry, void *data)
577 {
578   struct directory const *directory = entry;
579   FILE *fp = data;
580
581   if (directory->found)
582     {
583       int e;
584       char buf[UINTMAX_STRSIZE_BOUND];
585       char *str = quote_copy_string (directory->name);
586       
587       if (directory->nfs)
588         fprintf (fp, "+");
589       fprintf (fp, "%s ", umaxtostr (directory->mtime.tv_sec, buf));
590       fprintf (fp, "%s ", umaxtostr (directory->mtime.tv_nsec, buf));
591       fprintf (fp, "%s ", umaxtostr (directory->device_number, buf));
592       fprintf (fp, "%s ", umaxtostr (directory->inode_number, buf));
593       fprintf (fp, "%s\n", str ? str : directory->name);
594                
595       e = errno;
596       if (str)
597         free (str);
598       errno = e;
599     }
600
601   return ! ferror (fp);
602 }
603
604 void
605 write_directory_file (void)
606 {
607   FILE *fp = listed_incremental_stream;
608
609   if (! fp)
610     return;
611
612   if (fseek (fp, 0L, SEEK_SET) != 0)
613     seek_error (listed_incremental_option);
614   if (sys_truncate (fileno (fp)) != 0)
615     truncate_error (listed_incremental_option);
616
617   fprintf (fp, "%s-%s-%d\n", PACKAGE_NAME, PACKAGE_VERSION,
618            TAR_INCREMENTAL_VERSION);
619   
620   fprintf (fp, "%lu %lu\n",
621            (unsigned long int) start_time.tv_sec,
622            (unsigned long int) start_time.tv_nsec);
623   if (! ferror (fp) && directory_table)
624     hash_do_for_each (directory_table, write_directory_file_entry, fp);
625   if (ferror (fp))
626     write_error (listed_incremental_option);
627   if (fclose (fp) != 0)
628     close_error (listed_incremental_option);
629 }
630
631 \f
632 /* Restoration of incremental dumps.  */
633
634 void
635 get_gnu_dumpdir ()
636 {
637   size_t size;
638   size_t copied;
639   union block *data_block;
640   char *to;
641   char *archive_dir;
642   
643   size = current_stat_info.stat.st_size;
644   if (size != current_stat_info.stat.st_size)
645     xalloc_die ();
646
647   archive_dir = xmalloc (size);
648   to = archive_dir;
649
650   set_next_block_after (current_header);
651   mv_begin (&current_stat_info);
652
653   for (; size > 0; size -= copied)
654     {
655       mv_size_left (size);
656       data_block = find_next_block ();
657       if (!data_block)
658         ERROR ((1, 0, _("Unexpected EOF in archive")));
659       copied = available_space_after (data_block);
660       if (copied > size)
661         copied = size;
662       memcpy (to, data_block->buffer, copied);
663       to += copied;
664       set_next_block_after ((union block *)
665                             (data_block->buffer + copied - 1));
666     }
667
668   mv_end ();
669   
670   current_stat_info.stat.st_size = 0; /* For skip_member() and friends
671                                          to work correctly */
672   current_stat_info.dumpdir = archive_dir;
673 }
674
675
676 /* Examine the directories under directory_name and delete any
677    files that were not there at the time of the back-up. */
678 void
679 purge_directory (char const *directory_name)
680 {
681   char *current_dir;
682   char *cur, *arc;
683
684   if (!current_stat_info.dumpdir)
685     {
686       skip_member ();
687       return;
688     }
689   
690   current_dir = savedir (directory_name);
691
692   if (!current_dir)
693     {
694       /* The directory doesn't exist now.  It'll be created.  In any
695          case, we don't have to delete any files out of it.  */
696
697       skip_member ();
698       return;
699     }
700
701   for (cur = current_dir; *cur; cur += strlen (cur) + 1)
702     {
703       for (arc = current_stat_info.dumpdir; *arc; arc += strlen (arc) + 1)
704         {
705           arc++;
706           if (!strcmp (arc, cur))
707             break;
708         }
709       if (*arc == '\0')
710         {
711           struct stat st;
712           char *p = new_name (directory_name, cur);
713
714           if (deref_stat (false, p, &st))
715             {
716               stat_diag (p);
717               WARN((0, 0, _("%s: Not purging directory: unable to stat"),
718                     quotearg_colon (p)));
719               continue;
720             }
721           else if (one_file_system_option && st.st_dev != root_device)
722             {
723               WARN((0, 0,
724                     _("%s: directory is on a different device: not purging"),
725                     quotearg_colon (p)));
726               continue;
727             }
728
729           if (! interactive_option || confirm ("delete", p))
730             {
731               if (verbose_option)
732                 fprintf (stdlis, _("%s: Deleting %s\n"),
733                          program_name, quote (p));
734               if (! remove_any_file (p, RECURSIVE_REMOVE_OPTION))
735                 {
736                   int e = errno;
737                   ERROR ((0, e, _("%s: Cannot remove"), quotearg_colon (p)));
738                 }
739             }
740           free (p);
741         }
742
743     }
744   free (current_dir);
745 }
746
747 void
748 list_dumpdir (char *buffer, size_t size)
749 {
750   while (size)
751     {
752       switch (*buffer)
753         {
754         case 'Y':
755         case 'N':
756         case 'D':
757           fprintf (stdlis, "%c ", *buffer);
758           buffer++;
759           size--;
760           break;
761           
762         case 0:
763           fputc ('\n', stdlis);
764           buffer++;
765           size--;
766           break;
767           
768         default:
769           fputc (*buffer, stdlis);
770           buffer++;
771           size--;
772         }
773     }
774 }