git.gag.com Git - debian/tar/blob - src/sparse.c

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