src/sparse.c

   1 /* Functions for dealing with sparse files
   2
   3    Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   4
   5    This program is free software; you can redistribute it and/or modify it
   6    under the terms of the GNU General Public License as published by the
   7    Free Software Foundation; either version 3, or (at your option) any later
   8    version.
   9
  10    This program is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
  13    Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License along
  16    with this program; if not, write to the Free Software Foundation, Inc.,
  17    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 #include <system.h>
  20 #include <inttostr.h>
  21 #include <quotearg.h>
  22 #include "common.h"
  23
  24 struct tar_sparse_file;
  25 static bool sparse_select_optab (struct tar_sparse_file *file);
  26
  27 enum sparse_scan_state
  28   {
  29     scan_begin,
  30     scan_block,
  31     scan_end
  32   };
  33
  34 struct tar_sparse_optab
  35 {
  36   bool (*init) (struct tar_sparse_file *);
  37   bool (*done) (struct tar_sparse_file *);
  38   bool (*sparse_member_p) (struct tar_sparse_file *);
  39   bool (*dump_header) (struct tar_sparse_file *);
  40   bool (*fixup_header) (struct tar_sparse_file *);
  41   bool (*decode_header) (struct tar_sparse_file *);
  42   bool (*scan_block) (struct tar_sparse_file *, enum sparse_scan_state,
  43                       void *);
  44   bool (*dump_region) (struct tar_sparse_file *, size_t);
  45   bool (*extract_region) (struct tar_sparse_file *, size_t);
  46 };
  47
  48 struct tar_sparse_file
  49 {
  50   int fd;                           /* File descriptor */
  51   bool seekable;                    /* Is fd seekable? */
  52   off_t offset;                     /* Current offset in fd if seekable==false.
  53                                        Otherwise unused */
  54   off_t dumped_size;                /* Number of bytes actually written
  55                                        to the archive */
  56   struct tar_stat_info *stat_info;  /* Information about the file */
  57   struct tar_sparse_optab const *optab; /* Operation table */
  58   void *closure;                    /* Any additional data optab calls might
  59                                        require */
  60 };
  61
  62 /* Dump zeros to file->fd until offset is reached. It is used instead of
  63    lseek if the output file is not seekable */
  64 static bool
  65 dump_zeros (struct tar_sparse_file *file, off_t offset)
  66 {
  67   static char const zero_buf[BLOCKSIZE];
  68
  69   if (offset < file->offset)
  70     {
  71       errno = EINVAL;
  72       return false;
  73     }
  74
  75   while (file->offset < offset)
  76     {
  77       size_t size = (BLOCKSIZE < offset - file->offset
  78                      ? BLOCKSIZE
  79                      : offset - file->offset);
  80       ssize_t wrbytes;
  81
  82       wrbytes = write (file->fd, zero_buf, size);
  83       if (wrbytes <= 0)
  84         {
  85           if (wrbytes == 0)
  86             errno = EINVAL;
  87           return false;
  88         }
  89       file->offset += wrbytes;
  90     }
  91
  92   return true;
  93 }
  94
  95 static bool
  96 tar_sparse_member_p (struct tar_sparse_file *file)
  97 {
  98   if (file->optab->sparse_member_p)
  99     return file->optab->sparse_member_p (file);
 100   return false;
 101 }
 102
 103 static bool
 104 tar_sparse_init (struct tar_sparse_file *file)
 105 {
 106   memset (file, 0, sizeof *file);
 107
 108   if (!sparse_select_optab (file))
 109     return false;
 110
 111   if (file->optab->init)
 112     return file->optab->init (file);
 113
 114   return true;
 115 }
 116
 117 static bool
 118 tar_sparse_done (struct tar_sparse_file *file)
 119 {
 120   if (file->optab->done)
 121     return file->optab->done (file);
 122   return true;
 123 }
 124
 125 static bool
 126 tar_sparse_scan (struct tar_sparse_file *file, enum sparse_scan_state state,
 127                  void *block)
 128 {
 129   if (file->optab->scan_block)
 130     return file->optab->scan_block (file, state, block);
 131   return true;
 132 }
 133
 134 static bool
 135 tar_sparse_dump_region (struct tar_sparse_file *file, size_t i)
 136 {
 137   if (file->optab->dump_region)
 138     return file->optab->dump_region (file, i);
 139   return false;
 140 }
 141
 142 static bool
 143 tar_sparse_extract_region (struct tar_sparse_file *file, size_t i)
 144 {
 145   if (file->optab->extract_region)
 146     return file->optab->extract_region (file, i);
 147   return false;
 148 }
 149
 150 static bool
 151 tar_sparse_dump_header (struct tar_sparse_file *file)
 152 {
 153   if (file->optab->dump_header)
 154     return file->optab->dump_header (file);
 155   return false;
 156 }
 157
 158 static bool
 159 tar_sparse_decode_header (struct tar_sparse_file *file)
 160 {
 161   if (file->optab->decode_header)
 162     return file->optab->decode_header (file);
 163   return true;
 164 }
 165
 166 static bool
 167 tar_sparse_fixup_header (struct tar_sparse_file *file)
 168 {
 169   if (file->optab->fixup_header)
 170     return file->optab->fixup_header (file);
 171   return true;
 172 }
 173
 174 \f
 175 static bool
 176 lseek_or_error (struct tar_sparse_file *file, off_t offset)
 177 {
 178   if (file->seekable
 179       ? lseek (file->fd, offset, SEEK_SET) < 0
 180       : ! dump_zeros (file, offset))
 181     {
 182       seek_diag_details (file->stat_info->orig_file_name, offset);
 183       return false;
 184     }
 185   return true;
 186 }
 187
 188 /* Takes a blockful of data and basically cruises through it to see if
 189    it's made *entirely* of zeros, returning a 0 the instant it finds
 190    something that is a nonzero, i.e., useful data.  */
 191 static bool
 192 zero_block_p (char const *buffer, size_t size)
 193 {
 194   while (size--)
 195     if (*buffer++)
 196       return false;
 197   return true;
 198 }
 199
 200 static void
 201 sparse_add_map (struct tar_stat_info *st, struct sp_array const *sp)
 202 {
 203   struct sp_array *sparse_map = st->sparse_map;
 204   size_t avail = st->sparse_map_avail;
 205   if (avail == st->sparse_map_size)
 206     st->sparse_map = sparse_map =
 207       x2nrealloc (sparse_map, &st->sparse_map_size, sizeof *sparse_map);
 208   sparse_map[avail] = *sp;
 209   st->sparse_map_avail = avail + 1;
 210 }
 211
 212 /* Scan the sparse file and create its map */
 213 static bool
 214 sparse_scan_file (struct tar_sparse_file *file)
 215 {
 216   struct tar_stat_info *st = file->stat_info;
 217   int fd = file->fd;
 218   char buffer[BLOCKSIZE];
 219   size_t count;
 220   off_t offset = 0;
 221   struct sp_array sp = {0, 0};
 222
 223   if (!lseek_or_error (file, 0))
 224     return false;
 225
 226   st->archive_file_size = 0;
 227
 228   if (!tar_sparse_scan (file, scan_begin, NULL))
 229     return false;
 230
 231   while ((count = safe_read (fd, buffer, sizeof buffer)) != 0
 232          && count != SAFE_READ_ERROR)
 233     {
 234       /* Analyze the block.  */
 235       if (zero_block_p (buffer, count))
 236         {
 237           if (sp.numbytes)
 238             {
 239               sparse_add_map (st, &sp);
 240               sp.numbytes = 0;
 241               if (!tar_sparse_scan (file, scan_block, NULL))
 242                 return false;
 243             }
 244         }
 245       else
 246         {
 247           if (sp.numbytes == 0)
 248             sp.offset = offset;
 249           sp.numbytes += count;
 250           st->archive_file_size += count;
 251           if (!tar_sparse_scan (file, scan_block, buffer))
 252             return false;
 253         }
 254
 255       offset += count;
 256     }
 257
 258   if (sp.numbytes == 0)
 259     sp.offset = offset;
 260
 261   sparse_add_map (st, &sp);
 262   st->archive_file_size += count;
 263   return tar_sparse_scan (file, scan_end, NULL);
 264 }
 265
 266 static struct tar_sparse_optab const oldgnu_optab;
 267 static struct tar_sparse_optab const star_optab;
 268 static struct tar_sparse_optab const pax_optab;
 269
 270 static bool
 271 sparse_select_optab (struct tar_sparse_file *file)
 272 {
 273   switch (current_format == DEFAULT_FORMAT ? archive_format : current_format)
 274     {
 275     case V7_FORMAT:
 276     case USTAR_FORMAT:
 277       return false;
 278
 279     case OLDGNU_FORMAT:
 280     case GNU_FORMAT: /*FIXME: This one should disappear? */
 281       file->optab = &oldgnu_optab;
 282       break;
 283
 284     case POSIX_FORMAT:
 285       file->optab = &pax_optab;
 286       break;
 287
 288     case STAR_FORMAT:
 289       file->optab = &star_optab;
 290       break;
 291
 292     default:
 293       return false;
 294     }
 295   return true;
 296 }
 297
 298 static bool
 299 sparse_dump_region (struct tar_sparse_file *file, size_t i)
 300 {
 301   union block *blk;
 302   off_t bytes_left = file->stat_info->sparse_map[i].numbytes;
 303
 304   if (!lseek_or_error (file, file->stat_info->sparse_map[i].offset))
 305     return false;
 306
 307   while (bytes_left > 0)
 308     {
 309       size_t bufsize = (bytes_left > BLOCKSIZE) ? BLOCKSIZE : bytes_left;
 310       size_t bytes_read;
 311
 312       blk = find_next_block ();
 313       bytes_read = safe_read (file->fd, blk->buffer, bufsize);
 314       if (bytes_read == SAFE_READ_ERROR)
 315         {
 316           read_diag_details (file->stat_info->orig_file_name,
 317                              (file->stat_info->sparse_map[i].offset
 318                               + file->stat_info->sparse_map[i].numbytes
 319                               - bytes_left),
 320                              bufsize);
 321           return false;
 322         }
 323
 324       memset (blk->buffer + bytes_read, 0, BLOCKSIZE - bytes_read);
 325       bytes_left -= bytes_read;
 326       file->dumped_size += bytes_read;
 327       mv_size_left (file->stat_info->archive_file_size - file->dumped_size);
 328       set_next_block_after (blk);
 329     }
 330
 331   return true;
 332 }
 333
 334 static bool
 335 sparse_extract_region (struct tar_sparse_file *file, size_t i)
 336 {
 337   size_t write_size;
 338
 339   if (!lseek_or_error (file, file->stat_info->sparse_map[i].offset))
 340     return false;
 341
 342   write_size = file->stat_info->sparse_map[i].numbytes;
 343
 344   if (write_size == 0)
 345     {
 346       /* Last block of the file is a hole */
 347       if (file->seekable && sys_truncate (file->fd))
 348         truncate_warn (file->stat_info->orig_file_name);
 349     }
 350   else while (write_size > 0)
 351     {
 352       size_t count;
 353       size_t wrbytes = (write_size > BLOCKSIZE) ? BLOCKSIZE : write_size;
 354       union block *blk = find_next_block ();
 355       if (!blk)
 356         {
 357           ERROR ((0, 0, _("Unexpected EOF in archive")));
 358           return false;
 359         }
 360       set_next_block_after (blk);
 361       count = full_write (file->fd, blk->buffer, wrbytes);
 362       write_size -= count;
 363       file->dumped_size += count;
 364       mv_size_left (file->stat_info->archive_file_size - file->dumped_size);
 365       file->offset += count;
 366       if (count != wrbytes)
 367         {
 368           write_error_details (file->stat_info->orig_file_name,
 369                                count, wrbytes);
 370           return false;
 371         }
 372     }
 373   return true;
 374 }
 375
 376 \f
 377
 378 /* Interface functions */
 379 enum dump_status
 380 sparse_dump_file (int fd, struct tar_stat_info *st)
 381 {
 382   bool rc;
 383   struct tar_sparse_file file;
 384
 385   if (!tar_sparse_init (&file))
 386     return dump_status_not_implemented;
 387
 388   file.stat_info = st;
 389   file.fd = fd;
 390   file.seekable = true; /* File *must* be seekable for dump to work */
 391
 392   rc = sparse_scan_file (&file);
 393   if (rc && file.optab->dump_region)
 394     {
 395       tar_sparse_dump_header (&file);
 396
 397       if (fd >= 0)
 398         {
 399           size_t i;
 400
 401           mv_begin (file.stat_info);
 402           for (i = 0; rc && i < file.stat_info->sparse_map_avail; i++)
 403             rc = tar_sparse_dump_region (&file, i);
 404           mv_end ();
 405         }
 406     }
 407
 408   pad_archive (file.stat_info->archive_file_size - file.dumped_size);
 409   return (tar_sparse_done (&file) && rc) ? dump_status_ok : dump_status_short;
 410 }
 411
 412 bool
 413 sparse_member_p (struct tar_stat_info *st)
 414 {
 415   struct tar_sparse_file file;
 416
 417   if (!tar_sparse_init (&file))
 418     return false;
 419   file.stat_info = st;
 420   return tar_sparse_member_p (&file);
 421 }
 422
 423 bool
 424 sparse_fixup_header (struct tar_stat_info *st)
 425 {
 426   struct tar_sparse_file file;
 427
 428   if (!tar_sparse_init (&file))
 429     return false;
 430   file.stat_info = st;
 431   return tar_sparse_fixup_header (&file);
 432 }
 433
 434 enum dump_status
 435 sparse_extract_file (int fd, struct tar_stat_info *st, off_t *size)
 436 {
 437   bool rc = true;
 438   struct tar_sparse_file file;
 439   size_t i;
 440
 441   if (!tar_sparse_init (&file))
 442     return dump_status_not_implemented;
 443
 444   file.stat_info = st;
 445   file.fd = fd;
 446   file.seekable = lseek (fd, 0, SEEK_SET) == 0;
 447   file.offset = 0;
 448
 449   rc = tar_sparse_decode_header (&file);
 450   for (i = 0; rc && i < file.stat_info->sparse_map_avail; i++)
 451     rc = tar_sparse_extract_region (&file, i);
 452   *size = file.stat_info->archive_file_size - file.dumped_size;
 453   return (tar_sparse_done (&file) && rc) ? dump_status_ok : dump_status_short;
 454 }
 455
 456 enum dump_status
 457 sparse_skip_file (struct tar_stat_info *st)
 458 {
 459   bool rc = true;
 460   struct tar_sparse_file file;
 461
 462   if (!tar_sparse_init (&file))
 463     return dump_status_not_implemented;
 464
 465   file.stat_info = st;
 466   file.fd = -1;
 467
 468   rc = tar_sparse_decode_header (&file);
 469   skip_file (file.stat_info->archive_file_size - file.dumped_size);
 470   return (tar_sparse_done (&file) && rc) ? dump_status_ok : dump_status_short;
 471 }
 472
 473 \f
 474 static bool
 475 check_sparse_region (struct tar_sparse_file *file, off_t beg, off_t end)
 476 {
 477   if (!lseek_or_error (file, beg))
 478     return false;
 479
 480   while (beg < end)
 481     {
 482       size_t bytes_read;
 483       size_t rdsize = BLOCKSIZE < end - beg ? BLOCKSIZE : end - beg;
 484       char diff_buffer[BLOCKSIZE];
 485
 486       bytes_read = safe_read (file->fd, diff_buffer, rdsize);
 487       if (bytes_read == SAFE_READ_ERROR)
 488         {
 489           read_diag_details (file->stat_info->orig_file_name,
 490                              beg,
 491                              rdsize);
 492           return false;
 493         }
 494       if (!zero_block_p (diff_buffer, bytes_read))
 495         {
 496           char begbuf[INT_BUFSIZE_BOUND (off_t)];
 497           report_difference (file->stat_info,
 498                              _("File fragment at %s is not a hole"),
 499                              offtostr (beg, begbuf));
 500           return false;
 501         }
 502
 503       beg += bytes_read;
 504     }
 505   return true;
 506 }
 507
 508 static bool
 509 check_data_region (struct tar_sparse_file *file, size_t i)
 510 {
 511   size_t size_left;
 512
 513   if (!lseek_or_error (file, file->stat_info->sparse_map[i].offset))
 514     return false;
 515   size_left = file->stat_info->sparse_map[i].numbytes;
 516   mv_size_left (file->stat_info->archive_file_size - file->dumped_size);
 517
 518   while (size_left > 0)
 519     {
 520       size_t bytes_read;
 521       size_t rdsize = (size_left > BLOCKSIZE) ? BLOCKSIZE : size_left;
 522       char diff_buffer[BLOCKSIZE];
 523
 524       union block *blk = find_next_block ();
 525       if (!blk)
 526         {
 527           ERROR ((0, 0, _("Unexpected EOF in archive")));
 528           return false;
 529         }
 530       set_next_block_after (blk);
 531       bytes_read = safe_read (file->fd, diff_buffer, rdsize);
 532       if (bytes_read == SAFE_READ_ERROR)
 533         {
 534           read_diag_details (file->stat_info->orig_file_name,
 535                              (file->stat_info->sparse_map[i].offset
 536                               + file->stat_info->sparse_map[i].numbytes
 537                               - size_left),
 538                              rdsize);
 539           return false;
 540         }
 541       file->dumped_size += bytes_read;
 542       size_left -= bytes_read;
 543       mv_size_left (file->stat_info->archive_file_size - file->dumped_size);
 544       if (memcmp (blk->buffer, diff_buffer, rdsize))
 545         {
 546           report_difference (file->stat_info, _("Contents differ"));
 547           return false;
 548         }
 549     }
 550   return true;
 551 }
 552
 553 bool
 554 sparse_diff_file (int fd, struct tar_stat_info *st)
 555 {
 556   bool rc = true;
 557   struct tar_sparse_file file;
 558   size_t i;
 559   off_t offset = 0;
 560
 561   if (!tar_sparse_init (&file))
 562     return dump_status_not_implemented;
 563
 564   file.stat_info = st;
 565   file.fd = fd;
 566   file.seekable = true; /* File *must* be seekable for compare to work */
 567
 568   rc = tar_sparse_decode_header (&file);
 569   mv_begin (st);
 570   for (i = 0; rc && i < file.stat_info->sparse_map_avail; i++)
 571     {
 572       rc = check_sparse_region (&file,
 573                                 offset, file.stat_info->sparse_map[i].offset)
 574             && check_data_region (&file, i);
 575       offset = file.stat_info->sparse_map[i].offset
 576                 + file.stat_info->sparse_map[i].numbytes;
 577     }
 578
 579   if (!rc)
 580     skip_file (file.stat_info->archive_file_size - file.dumped_size);
 581   mv_end ();
 582
 583   tar_sparse_done (&file);
 584   return rc;
 585 }
 586
 587 \f
 588 /* Old GNU Format. The sparse file information is stored in the
 589    oldgnu_header in the following manner:
 590
 591    The header is marked with type 'S'. Its `size' field contains
 592    the cumulative size of all non-empty blocks of the file. The
 593    actual file size is stored in `realsize' member of oldgnu_header.
 594
 595    The map of the file is stored in a list of `struct sparse'.
 596    Each struct contains offset to the block of data and its
 597    size (both as octal numbers). The first file header contains
 598    at most 4 such structs (SPARSES_IN_OLDGNU_HEADER). If the map
 599    contains more structs, then the field `isextended' of the main
 600    header is set to 1 (binary) and the `struct sparse_header'
 601    header follows, containing at most 21 following structs
 602    (SPARSES_IN_SPARSE_HEADER). If more structs follow, `isextended'
 603    field of the extended header is set and next  next extension header
 604    follows, etc... */
 605
 606 enum oldgnu_add_status
 607   {
 608     add_ok,
 609     add_finish,
 610     add_fail
 611   };
 612
 613 static bool
 614 oldgnu_sparse_member_p (struct tar_sparse_file *file __attribute__ ((unused)))
 615 {
 616   return current_header->header.typeflag == GNUTYPE_SPARSE;
 617 }
 618
 619 /* Add a sparse item to the sparse file and its obstack */
 620 static enum oldgnu_add_status
 621 oldgnu_add_sparse (struct tar_sparse_file *file, struct sparse *s)
 622 {
 623   struct sp_array sp;
 624
 625   if (s->numbytes[0] == '\0')
 626     return add_finish;
 627   sp.offset = OFF_FROM_HEADER (s->offset);
 628   sp.numbytes = SIZE_FROM_HEADER (s->numbytes);
 629   if (sp.offset < 0
 630       || file->stat_info->stat.st_size < sp.offset + sp.numbytes
 631       || file->stat_info->archive_file_size < 0)
 632     return add_fail;
 633
 634   sparse_add_map (file->stat_info, &sp);
 635   return add_ok;
 636 }
 637
 638 static bool
 639 oldgnu_fixup_header (struct tar_sparse_file *file)
 640 {
 641   /* NOTE! st_size was initialized from the header
 642      which actually contains archived size. The following fixes it */
 643   file->stat_info->archive_file_size = file->stat_info->stat.st_size;
 644   file->stat_info->stat.st_size =
 645     OFF_FROM_HEADER (current_header->oldgnu_header.realsize);
 646   return true;
 647 }
 648
 649 /* Convert old GNU format sparse data to internal representation */
 650 static bool
 651 oldgnu_get_sparse_info (struct tar_sparse_file *file)
 652 {
 653   size_t i;
 654   union block *h = current_header;
 655   int ext_p;
 656   enum oldgnu_add_status rc;
 657
 658   file->stat_info->sparse_map_avail = 0;
 659   for (i = 0; i < SPARSES_IN_OLDGNU_HEADER; i++)
 660     {
 661       rc = oldgnu_add_sparse (file, &h->oldgnu_header.sp[i]);
 662       if (rc != add_ok)
 663         break;
 664     }
 665
 666   for (ext_p = h->oldgnu_header.isextended;
 667        rc == add_ok && ext_p; ext_p = h->sparse_header.isextended)
 668     {
 669       h = find_next_block ();
 670       if (!h)
 671         {
 672           ERROR ((0, 0, _("Unexpected EOF in archive")));
 673           return false;
 674         }
 675       set_next_block_after (h);
 676       for (i = 0; i < SPARSES_IN_SPARSE_HEADER && rc == add_ok; i++)
 677         rc = oldgnu_add_sparse (file, &h->sparse_header.sp[i]);
 678     }
 679
 680   if (rc == add_fail)
 681     {
 682       ERROR ((0, 0, _("%s: invalid sparse archive member"),
 683               file->stat_info->orig_file_name));
 684       return false;
 685     }
 686   return true;
 687 }
 688
 689 static void
 690 oldgnu_store_sparse_info (struct tar_sparse_file *file, size_t *pindex,
 691                           struct sparse *sp, size_t sparse_size)
 692 {
 693   for (; *pindex < file->stat_info->sparse_map_avail
 694          && sparse_size > 0; sparse_size--, sp++, ++*pindex)
 695     {
 696       OFF_TO_CHARS (file->stat_info->sparse_map[*pindex].offset,
 697                     sp->offset);
 698       SIZE_TO_CHARS (file->stat_info->sparse_map[*pindex].numbytes,
 699                      sp->numbytes);
 700     }
 701 }
 702
 703 static bool
 704 oldgnu_dump_header (struct tar_sparse_file *file)
 705 {
 706   off_t block_ordinal = current_block_ordinal ();
 707   union block *blk;
 708   size_t i;
 709
 710   blk = start_header (file->stat_info);
 711   blk->header.typeflag = GNUTYPE_SPARSE;
 712   if (file->stat_info->sparse_map_avail > SPARSES_IN_OLDGNU_HEADER)
 713     blk->oldgnu_header.isextended = 1;
 714
 715   /* Store the real file size */
 716   OFF_TO_CHARS (file->stat_info->stat.st_size, blk->oldgnu_header.realsize);
 717   /* Store the effective (shrunken) file size */
 718   OFF_TO_CHARS (file->stat_info->archive_file_size, blk->header.size);
 719
 720   i = 0;
 721   oldgnu_store_sparse_info (file, &i,
 722                             blk->oldgnu_header.sp,
 723                             SPARSES_IN_OLDGNU_HEADER);
 724   blk->oldgnu_header.isextended = i < file->stat_info->sparse_map_avail;
 725   finish_header (file->stat_info, blk, block_ordinal);
 726
 727   while (i < file->stat_info->sparse_map_avail)
 728     {
 729       blk = find_next_block ();
 730       memset (blk->buffer, 0, BLOCKSIZE);
 731       oldgnu_store_sparse_info (file, &i,
 732                                 blk->sparse_header.sp,
 733                                 SPARSES_IN_SPARSE_HEADER);
 734       if (i < file->stat_info->sparse_map_avail)
 735         blk->sparse_header.isextended = 1;
 736       set_next_block_after (blk);
 737     }
 738   return true;
 739 }
 740
 741 static struct tar_sparse_optab const oldgnu_optab = {
 742   NULL,  /* No init function */
 743   NULL,  /* No done function */
 744   oldgnu_sparse_member_p,
 745   oldgnu_dump_header,
 746   oldgnu_fixup_header,
 747   oldgnu_get_sparse_info,
 748   NULL,  /* No scan_block function */
 749   sparse_dump_region,
 750   sparse_extract_region,
 751 };
 752
 753 \f
 754 /* Star */
 755
 756 static bool
 757 star_sparse_member_p (struct tar_sparse_file *file __attribute__ ((unused)))
 758 {
 759   return current_header->header.typeflag == GNUTYPE_SPARSE;
 760 }
 761
 762 static bool
 763 star_fixup_header (struct tar_sparse_file *file)
 764 {
 765   /* NOTE! st_size was initialized from the header
 766      which actually contains archived size. The following fixes it */
 767   file->stat_info->archive_file_size = file->stat_info->stat.st_size;
 768   file->stat_info->stat.st_size =
 769             OFF_FROM_HEADER (current_header->star_in_header.realsize);
 770   return true;
 771 }
 772
 773 /* Convert STAR format sparse data to internal representation */
 774 static bool
 775 star_get_sparse_info (struct tar_sparse_file *file)
 776 {
 777   size_t i;
 778   union block *h = current_header;
 779   int ext_p;
 780   enum oldgnu_add_status rc = add_ok;
 781
 782   file->stat_info->sparse_map_avail = 0;
 783
 784   if (h->star_in_header.prefix[0] == '\0'
 785       && h->star_in_header.sp[0].offset[10] != '\0')
 786     {
 787       /* Old star format */
 788       for (i = 0; i < SPARSES_IN_STAR_HEADER; i++)
 789         {
 790           rc = oldgnu_add_sparse (file, &h->star_in_header.sp[i]);
 791           if (rc != add_ok)
 792             break;
 793         }
 794       ext_p = h->star_in_header.isextended;
 795     }
 796   else
 797     ext_p = 1;
 798
 799   for (; rc == add_ok && ext_p; ext_p = h->star_ext_header.isextended)
 800     {
 801       h = find_next_block ();
 802       if (!h)
 803         {
 804           ERROR ((0, 0, _("Unexpected EOF in archive")));
 805           return false;
 806         }
 807       set_next_block_after (h);
 808       for (i = 0; i < SPARSES_IN_STAR_EXT_HEADER && rc == add_ok; i++)
 809         rc = oldgnu_add_sparse (file, &h->star_ext_header.sp[i]);
 810     }
 811
 812   if (rc == add_fail)
 813     {
 814       ERROR ((0, 0, _("%s: invalid sparse archive member"),
 815               file->stat_info->orig_file_name));
 816       return false;
 817     }
 818   return true;
 819 }
 820
 821
 822 static struct tar_sparse_optab const star_optab = {
 823   NULL,  /* No init function */
 824   NULL,  /* No done function */
 825   star_sparse_member_p,
 826   NULL,
 827   star_fixup_header,
 828   star_get_sparse_info,
 829   NULL,  /* No scan_block function */
 830   NULL, /* No dump region function */
 831   sparse_extract_region,
 832 };
 833
 834 \f
 835 /* GNU PAX sparse file format. There are several versions:
 836
 837    * 0.0
 838
 839    The initial version of sparse format used by tar 1.14-1.15.1.
 840    The sparse file map is stored in x header:
 841
 842    GNU.sparse.size      Real size of the stored file
 843    GNU.sparse.numblocks Number of blocks in the sparse map
 844    repeat numblocks time
 845      GNU.sparse.offset    Offset of the next data block
 846      GNU.sparse.numbytes  Size of the next data block
 847    end repeat
 848
 849    This has been reported as conflicting with the POSIX specs. The reason is
 850    that offsets and sizes of non-zero data blocks were stored in multiple
 851    instances of GNU.sparse.offset/GNU.sparse.numbytes variables, whereas
 852    POSIX requires the latest occurrence of the variable to override all
 853    previous occurrences.
 854
 855    To avoid this incompatibility two following versions were introduced.
 856
 857    * 0.1
 858
 859    Used by tar 1.15.2 -- 1.15.91 (alpha releases).
 860
 861    The sparse file map is stored in
 862    x header:
 863
 864    GNU.sparse.size      Real size of the stored file
 865    GNU.sparse.numblocks Number of blocks in the sparse map
 866    GNU.sparse.map       Map of non-null data chunks. A string consisting
 867                        of comma-separated values "offset,size[,offset,size]..."
 868
 869    The resulting GNU.sparse.map string can be *very* long. While POSIX does not
 870    impose any limit on the length of a x header variable, this can confuse some
 871    tars.
 872
 873    * 1.0
 874
 875    Starting from this version, the exact sparse format version is specified
 876    explicitely in the header using the following variables:
 877
 878    GNU.sparse.major     Major version
 879    GNU.sparse.minor     Minor version
 880
 881    X header keeps the following variables:
 882
 883    GNU.sparse.name      Real file name of the sparse file
 884    GNU.sparse.realsize  Real size of the stored file (corresponds to the old
 885                         GNU.sparse.size variable)
 886
 887    The name field of the ustar header is constructed using the pattern
 888    "%d/GNUSparseFile.%p/%f".
 889
 890    The sparse map itself is stored in the file data block, preceding the actual
 891    file data. It consists of a series of octal numbers of arbitrary length,
 892    delimited by newlines. The map is padded with nulls to the nearest block
 893    boundary.
 894
 895    The first number gives the number of entries in the map. Following are map
 896    entries, each one consisting of two numbers giving the offset and size of
 897    the data block it describes.
 898
 899    The format is designed in such a way that non-posix aware tars and tars not
 900    supporting GNU.sparse.* keywords will extract each sparse file in its
 901    condensed form with the file map attached and will place it into a separate
 902    directory. Then, using a simple program it would be possible to expand the
 903    file to its original form even without GNU tar.
 904
 905    Bu default, v.1.0 archives are created. To use other formats,
 906    --sparse-version option is provided. Additionally, v.0.0 can be obtained
 907    by deleting GNU.sparse.map from 0.1 format: --sparse-version 0.1
 908    --pax-option delete=GNU.sparse.map
 909 */
 910
 911 static bool
 912 pax_sparse_member_p (struct tar_sparse_file *file)
 913 {
 914   return file->stat_info->sparse_map_avail > 0
 915           || file->stat_info->sparse_major > 0;
 916 }
 917
 918 static bool
 919 pax_dump_header_0 (struct tar_sparse_file *file)
 920 {
 921   off_t block_ordinal = current_block_ordinal ();
 922   union block *blk;
 923   size_t i;
 924   char nbuf[UINTMAX_STRSIZE_BOUND];
 925   struct sp_array *map = file->stat_info->sparse_map;
 926   char *save_file_name = NULL;
 927
 928   /* Store the real file size */
 929   xheader_store ("GNU.sparse.size", file->stat_info, NULL);
 930   xheader_store ("GNU.sparse.numblocks", file->stat_info, NULL);
 931
 932   if (xheader_keyword_deleted_p ("GNU.sparse.map")
 933       || tar_sparse_minor == 0)
 934     {
 935       for (i = 0; i < file->stat_info->sparse_map_avail; i++)
 936         {
 937           xheader_store ("GNU.sparse.offset", file->stat_info, &i);
 938           xheader_store ("GNU.sparse.numbytes", file->stat_info, &i);
 939         }
 940     }
 941   else
 942     {
 943       xheader_store ("GNU.sparse.name", file->stat_info, NULL);
 944       save_file_name = file->stat_info->file_name;
 945       file->stat_info->file_name = xheader_format_name (file->stat_info,
 946                                                "%d/GNUSparseFile.%p/%f", 0);
 947
 948       xheader_string_begin (&file->stat_info->xhdr);
 949       for (i = 0; i < file->stat_info->sparse_map_avail; i++)
 950         {
 951           if (i)
 952             xheader_string_add (&file->stat_info->xhdr, ",");
 953           xheader_string_add (&file->stat_info->xhdr,
 954                               umaxtostr (map[i].offset, nbuf));
 955           xheader_string_add (&file->stat_info->xhdr, ",");
 956           xheader_string_add (&file->stat_info->xhdr,
 957                               umaxtostr (map[i].numbytes, nbuf));
 958         }
 959       if (!xheader_string_end (&file->stat_info->xhdr,
 960                                "GNU.sparse.map"))
 961         {
 962           free (file->stat_info->file_name);
 963           file->stat_info->file_name = save_file_name;
 964           return false;
 965         }
 966     }
 967   blk = start_header (file->stat_info);
 968   /* Store the effective (shrunken) file size */
 969   OFF_TO_CHARS (file->stat_info->archive_file_size, blk->header.size);
 970   finish_header (file->stat_info, blk, block_ordinal);
 971   if (save_file_name)
 972     {
 973       free (file->stat_info->file_name);
 974       file->stat_info->file_name = save_file_name;
 975     }
 976   return true;
 977 }
 978
 979 static bool
 980 pax_dump_header_1 (struct tar_sparse_file *file)
 981 {
 982   off_t block_ordinal = current_block_ordinal ();
 983   union block *blk;
 984   char *p, *q;
 985   size_t i;
 986   char nbuf[UINTMAX_STRSIZE_BOUND];
 987   off_t size = 0;
 988   struct sp_array *map = file->stat_info->sparse_map;
 989   char *save_file_name = file->stat_info->file_name;
 990
 991 #define COPY_STRING(b,dst,src) do                \
 992  {                                               \
 993    char *endp = b->buffer + BLOCKSIZE;           \
 994    char *srcp = src;                             \
 995    while (*srcp)                                 \
 996      {                                           \
 997        if (dst == endp)                          \
 998          {                                       \
 999            set_next_block_after (b);             \
1000            b = find_next_block ();               \
1001            dst = b->buffer;                      \
1002            endp = b->buffer + BLOCKSIZE;         \
1003          }                                       \
1004        *dst++ = *srcp++;                         \
1005      }                                           \
1006    } while (0)
1007
1008   /* Compute stored file size */
1009   p = umaxtostr (file->stat_info->sparse_map_avail, nbuf);
1010   size += strlen (p) + 1;
1011   for (i = 0; i < file->stat_info->sparse_map_avail; i++)
1012     {
1013       p = umaxtostr (map[i].offset, nbuf);
1014       size += strlen (p) + 1;
1015       p = umaxtostr (map[i].numbytes, nbuf);
1016       size += strlen (p) + 1;
1017     }
1018   size = (size + BLOCKSIZE - 1) / BLOCKSIZE;
1019   file->stat_info->archive_file_size += size * BLOCKSIZE;
1020   file->dumped_size += size * BLOCKSIZE;
1021
1022   /* Store sparse file identification */
1023   xheader_store ("GNU.sparse.major", file->stat_info, NULL);
1024   xheader_store ("GNU.sparse.minor", file->stat_info, NULL);
1025   xheader_store ("GNU.sparse.name", file->stat_info, NULL);
1026   xheader_store ("GNU.sparse.realsize", file->stat_info, NULL);
1027
1028   file->stat_info->file_name = xheader_format_name (file->stat_info,
1029                                             "%d/GNUSparseFile.%p/%f", 0);
1030
1031   blk = start_header (file->stat_info);
1032   /* Store the effective (shrunken) file size */
1033   OFF_TO_CHARS (file->stat_info->archive_file_size, blk->header.size);
1034   finish_header (file->stat_info, blk, block_ordinal);
1035   free (file->stat_info->file_name);
1036   file->stat_info->file_name = save_file_name;
1037
1038   blk = find_next_block ();
1039   q = blk->buffer;
1040   p = umaxtostr (file->stat_info->sparse_map_avail, nbuf);
1041   COPY_STRING (blk, q, p);
1042   COPY_STRING (blk, q, "\n");
1043   for (i = 0; i < file->stat_info->sparse_map_avail; i++)
1044     {
1045       p = umaxtostr (map[i].offset, nbuf);
1046       COPY_STRING (blk, q, p);
1047       COPY_STRING (blk, q, "\n");
1048       p = umaxtostr (map[i].numbytes, nbuf);
1049       COPY_STRING (blk, q, p);
1050       COPY_STRING (blk, q, "\n");
1051     }
1052   memset (q, 0, BLOCKSIZE - (q - blk->buffer));
1053   set_next_block_after (blk);
1054   return true;
1055 }
1056
1057 static bool
1058 pax_dump_header (struct tar_sparse_file *file)
1059 {
1060   file->stat_info->sparse_major = tar_sparse_major;
1061   file->stat_info->sparse_minor = tar_sparse_minor;
1062
1063   return (file->stat_info->sparse_major == 0) ?
1064            pax_dump_header_0 (file) : pax_dump_header_1 (file);
1065 }
1066
1067 static bool
1068 decode_num (uintmax_t *num, char const *arg, uintmax_t maxval)
1069 {
1070   uintmax_t u;
1071   char *arg_lim;
1072
1073   if (!ISDIGIT (*arg))
1074     return false;
1075
1076   u = strtoumax (arg, &arg_lim, 10);
1077
1078   if (! (u <= maxval && errno != ERANGE) || *arg_lim)
1079     return false;
1080
1081   *num = u;
1082   return true;
1083 }
1084
1085 static bool
1086 pax_decode_header (struct tar_sparse_file *file)
1087 {
1088   if (file->stat_info->sparse_major > 0)
1089     {
1090       uintmax_t u;
1091       char nbuf[UINTMAX_STRSIZE_BOUND];
1092       union block *blk;
1093       char *p;
1094       size_t i;
1095
1096 #define COPY_BUF(b,buf,src) do                                     \
1097  {                                                                 \
1098    char *endp = b->buffer + BLOCKSIZE;                             \
1099    char *dst = buf;                                                \
1100    do                                                              \
1101      {                                                             \
1102        if (dst == buf + UINTMAX_STRSIZE_BOUND -1)                  \
1103          {                                                         \
1104            ERROR ((0, 0, _("%s: numeric overflow in sparse archive member"), \
1105                   file->stat_info->orig_file_name));               \
1106            return false;                                           \
1107          }                                                         \
1108        if (src == endp)                                            \
1109          {                                                         \
1110            set_next_block_after (b);                               \
1111            file->dumped_size += BLOCKSIZE;                         \
1112            b = find_next_block ();                                 \
1113            src = b->buffer;                                        \
1114            endp = b->buffer + BLOCKSIZE;                           \
1115          }                                                         \
1116        *dst = *src++;                                              \
1117      }                                                             \
1118    while (*dst++ != '\n');                                         \
1119    dst[-1] = 0;                                                    \
1120  } while (0)
1121
1122       set_next_block_after (current_header);
1123       file->dumped_size += BLOCKSIZE;
1124       blk = find_next_block ();
1125       p = blk->buffer;
1126       COPY_BUF (blk,nbuf,p);
1127       if (!decode_num (&u, nbuf, TYPE_MAXIMUM (size_t)))
1128         {
1129           ERROR ((0, 0, _("%s: malformed sparse archive member"),
1130                   file->stat_info->orig_file_name));
1131           return false;
1132         }
1133       file->stat_info->sparse_map_size = u;
1134       file->stat_info->sparse_map = xcalloc (file->stat_info->sparse_map_size,
1135                                              sizeof (*file->stat_info->sparse_map));
1136       file->stat_info->sparse_map_avail = 0;
1137       for (i = 0; i < file->stat_info->sparse_map_size; i++)
1138         {
1139           struct sp_array sp;
1140
1141           COPY_BUF (blk,nbuf,p);
1142           if (!decode_num (&u, nbuf, TYPE_MAXIMUM (off_t)))
1143             {
1144               ERROR ((0, 0, _("%s: malformed sparse archive member"),
1145                       file->stat_info->orig_file_name));
1146               return false;
1147             }
1148           sp.offset = u;
1149           COPY_BUF (blk,nbuf,p);
1150           if (!decode_num (&u, nbuf, TYPE_MAXIMUM (size_t)))
1151             {
1152               ERROR ((0, 0, _("%s: malformed sparse archive member"),
1153                       file->stat_info->orig_file_name));
1154               return false;
1155             }
1156           sp.numbytes = u;
1157           sparse_add_map (file->stat_info, &sp);
1158         }
1159       set_next_block_after (blk);
1160     }
1161
1162   return true;
1163 }
1164
1165 static struct tar_sparse_optab const pax_optab = {
1166   NULL,  /* No init function */
1167   NULL,  /* No done function */
1168   pax_sparse_member_p,
1169   pax_dump_header,
1170   NULL,
1171   pax_decode_header,
1172   NULL,  /* No scan_block function */
1173   sparse_dump_region,
1174   sparse_extract_region,
1175 };