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       file->dumped_size += BLOCKSIZE;
 813     }
 814
 815   if (rc == add_fail)
 816     {
 817       ERROR ((0, 0, _("%s: invalid sparse archive member"),
 818               file->stat_info->orig_file_name));
 819       return false;
 820     }
 821   return true;
 822 }
 823
 824
 825 static struct tar_sparse_optab const star_optab = {
 826   NULL,  /* No init function */
 827   NULL,  /* No done function */
 828   star_sparse_member_p,
 829   NULL,
 830   star_fixup_header,
 831   star_get_sparse_info,
 832   NULL,  /* No scan_block function */
 833   NULL, /* No dump region function */
 834   sparse_extract_region,
 835 };
 836
 837 \f
 838 /* GNU PAX sparse file format. There are several versions:
 839
 840    * 0.0
 841
 842    The initial version of sparse format used by tar 1.14-1.15.1.
 843    The sparse file map is stored in x header:
 844
 845    GNU.sparse.size      Real size of the stored file
 846    GNU.sparse.numblocks Number of blocks in the sparse map
 847    repeat numblocks time
 848      GNU.sparse.offset    Offset of the next data block
 849      GNU.sparse.numbytes  Size of the next data block
 850    end repeat
 851
 852    This has been reported as conflicting with the POSIX specs. The reason is
 853    that offsets and sizes of non-zero data blocks were stored in multiple
 854    instances of GNU.sparse.offset/GNU.sparse.numbytes variables, whereas
 855    POSIX requires the latest occurrence of the variable to override all
 856    previous occurrences.
 857
 858    To avoid this incompatibility two following versions were introduced.
 859
 860    * 0.1
 861
 862    Used by tar 1.15.2 -- 1.15.91 (alpha releases).
 863
 864    The sparse file map is stored in
 865    x header:
 866
 867    GNU.sparse.size      Real size of the stored file
 868    GNU.sparse.numblocks Number of blocks in the sparse map
 869    GNU.sparse.map       Map of non-null data chunks. A string consisting
 870                        of comma-separated values "offset,size[,offset,size]..."
 871
 872    The resulting GNU.sparse.map string can be *very* long. While POSIX does not
 873    impose any limit on the length of a x header variable, this can confuse some
 874    tars.
 875
 876    * 1.0
 877
 878    Starting from this version, the exact sparse format version is specified
 879    explicitely in the header using the following variables:
 880
 881    GNU.sparse.major     Major version
 882    GNU.sparse.minor     Minor version
 883
 884    X header keeps the following variables:
 885
 886    GNU.sparse.name      Real file name of the sparse file
 887    GNU.sparse.realsize  Real size of the stored file (corresponds to the old
 888                         GNU.sparse.size variable)
 889
 890    The name field of the ustar header is constructed using the pattern
 891    "%d/GNUSparseFile.%p/%f".
 892
 893    The sparse map itself is stored in the file data block, preceding the actual
 894    file data. It consists of a series of octal numbers of arbitrary length,
 895    delimited by newlines. The map is padded with nulls to the nearest block
 896    boundary.
 897
 898    The first number gives the number of entries in the map. Following are map
 899    entries, each one consisting of two numbers giving the offset and size of
 900    the data block it describes.
 901
 902    The format is designed in such a way that non-posix aware tars and tars not
 903    supporting GNU.sparse.* keywords will extract each sparse file in its
 904    condensed form with the file map attached and will place it into a separate
 905    directory. Then, using a simple program it would be possible to expand the
 906    file to its original form even without GNU tar.
 907
 908    Bu default, v.1.0 archives are created. To use other formats,
 909    --sparse-version option is provided. Additionally, v.0.0 can be obtained
 910    by deleting GNU.sparse.map from 0.1 format: --sparse-version 0.1
 911    --pax-option delete=GNU.sparse.map
 912 */
 913
 914 static bool
 915 pax_sparse_member_p (struct tar_sparse_file *file)
 916 {
 917   return file->stat_info->sparse_map_avail > 0
 918           || file->stat_info->sparse_major > 0;
 919 }
 920
 921 /* Start a header that uses the effective (shrunken) file size.  */
 922 static union block *
 923 pax_start_header (struct tar_stat_info *st)
 924 {
 925   off_t realsize = st->stat.st_size;
 926   union block *blk;
 927   st->stat.st_size = st->archive_file_size;
 928   blk = start_header (st);
 929   st->stat.st_size = realsize;
 930   return blk;
 931 }
 932
 933 static bool
 934 pax_dump_header_0 (struct tar_sparse_file *file)
 935 {
 936   off_t block_ordinal = current_block_ordinal ();
 937   union block *blk;
 938   size_t i;
 939   char nbuf[UINTMAX_STRSIZE_BOUND];
 940   struct sp_array *map = file->stat_info->sparse_map;
 941   char *save_file_name = NULL;
 942
 943   /* Store the real file size */
 944   xheader_store ("GNU.sparse.size", file->stat_info, NULL);
 945   xheader_store ("GNU.sparse.numblocks", file->stat_info, NULL);
 946
 947   if (xheader_keyword_deleted_p ("GNU.sparse.map")
 948       || tar_sparse_minor == 0)
 949     {
 950       for (i = 0; i < file->stat_info->sparse_map_avail; i++)
 951         {
 952           xheader_store ("GNU.sparse.offset", file->stat_info, &i);
 953           xheader_store ("GNU.sparse.numbytes", file->stat_info, &i);
 954         }
 955     }
 956   else
 957     {
 958       xheader_store ("GNU.sparse.name", file->stat_info, NULL);
 959       save_file_name = file->stat_info->file_name;
 960       file->stat_info->file_name = xheader_format_name (file->stat_info,
 961                                                "%d/GNUSparseFile.%p/%f", 0);
 962
 963       xheader_string_begin (&file->stat_info->xhdr);
 964       for (i = 0; i < file->stat_info->sparse_map_avail; i++)
 965         {
 966           if (i)
 967             xheader_string_add (&file->stat_info->xhdr, ",");
 968           xheader_string_add (&file->stat_info->xhdr,
 969                               umaxtostr (map[i].offset, nbuf));
 970           xheader_string_add (&file->stat_info->xhdr, ",");
 971           xheader_string_add (&file->stat_info->xhdr,
 972                               umaxtostr (map[i].numbytes, nbuf));
 973         }
 974       if (!xheader_string_end (&file->stat_info->xhdr,
 975                                "GNU.sparse.map"))
 976         {
 977           free (file->stat_info->file_name);
 978           file->stat_info->file_name = save_file_name;
 979           return false;
 980         }
 981     }
 982   blk = pax_start_header (file->stat_info);
 983   finish_header (file->stat_info, blk, block_ordinal);
 984   if (save_file_name)
 985     {
 986       free (file->stat_info->file_name);
 987       file->stat_info->file_name = save_file_name;
 988     }
 989   return true;
 990 }
 991
 992 static bool
 993 pax_dump_header_1 (struct tar_sparse_file *file)
 994 {
 995   off_t block_ordinal = current_block_ordinal ();
 996   union block *blk;
 997   char *p, *q;
 998   size_t i;
 999   char nbuf[UINTMAX_STRSIZE_BOUND];
1000   off_t size = 0;
1001   struct sp_array *map = file->stat_info->sparse_map;
1002   char *save_file_name = file->stat_info->file_name;
1003
1004 #define COPY_STRING(b,dst,src) do                \
1005  {                                               \
1006    char *endp = b->buffer + BLOCKSIZE;           \
1007    char const *srcp = src;                       \
1008    while (*srcp)                                 \
1009      {                                           \
1010        if (dst == endp)                          \
1011          {                                       \
1012            set_next_block_after (b);             \
1013            b = find_next_block ();               \
1014            dst = b->buffer;                      \
1015            endp = b->buffer + BLOCKSIZE;         \
1016          }                                       \
1017        *dst++ = *srcp++;                         \
1018      }                                           \
1019    } while (0)
1020
1021   /* Compute stored file size */
1022   p = umaxtostr (file->stat_info->sparse_map_avail, nbuf);
1023   size += strlen (p) + 1;
1024   for (i = 0; i < file->stat_info->sparse_map_avail; i++)
1025     {
1026       p = umaxtostr (map[i].offset, nbuf);
1027       size += strlen (p) + 1;
1028       p = umaxtostr (map[i].numbytes, nbuf);
1029       size += strlen (p) + 1;
1030     }
1031   size = (size + BLOCKSIZE - 1) / BLOCKSIZE;
1032   file->stat_info->archive_file_size += size * BLOCKSIZE;
1033   file->dumped_size += size * BLOCKSIZE;
1034
1035   /* Store sparse file identification */
1036   xheader_store ("GNU.sparse.major", file->stat_info, NULL);
1037   xheader_store ("GNU.sparse.minor", file->stat_info, NULL);
1038   xheader_store ("GNU.sparse.name", file->stat_info, NULL);
1039   xheader_store ("GNU.sparse.realsize", file->stat_info, NULL);
1040
1041   file->stat_info->file_name =
1042     xheader_format_name (file->stat_info, "%d/GNUSparseFile.%p/%f", 0);
1043   /* Make sure the created header name is shorter than NAME_FIELD_SIZE: */
1044   if (strlen (file->stat_info->file_name) > NAME_FIELD_SIZE)
1045     file->stat_info->file_name[NAME_FIELD_SIZE] = 0;
1046
1047   blk = pax_start_header (file->stat_info);
1048   finish_header (file->stat_info, blk, block_ordinal);
1049   free (file->stat_info->file_name);
1050   file->stat_info->file_name = save_file_name;
1051
1052   blk = find_next_block ();
1053   q = blk->buffer;
1054   p = umaxtostr (file->stat_info->sparse_map_avail, nbuf);
1055   COPY_STRING (blk, q, p);
1056   COPY_STRING (blk, q, "\n");
1057   for (i = 0; i < file->stat_info->sparse_map_avail; i++)
1058     {
1059       p = umaxtostr (map[i].offset, nbuf);
1060       COPY_STRING (blk, q, p);
1061       COPY_STRING (blk, q, "\n");
1062       p = umaxtostr (map[i].numbytes, nbuf);
1063       COPY_STRING (blk, q, p);
1064       COPY_STRING (blk, q, "\n");
1065     }
1066   memset (q, 0, BLOCKSIZE - (q - blk->buffer));
1067   set_next_block_after (blk);
1068   return true;
1069 }
1070
1071 static bool
1072 pax_dump_header (struct tar_sparse_file *file)
1073 {
1074   file->stat_info->sparse_major = tar_sparse_major;
1075   file->stat_info->sparse_minor = tar_sparse_minor;
1076
1077   return (file->stat_info->sparse_major == 0) ?
1078            pax_dump_header_0 (file) : pax_dump_header_1 (file);
1079 }
1080
1081 static bool
1082 decode_num (uintmax_t *num, char const *arg, uintmax_t maxval)
1083 {
1084   uintmax_t u;
1085   char *arg_lim;
1086
1087   if (!ISDIGIT (*arg))
1088     return false;
1089
1090   errno = 0;
1091   u = strtoumax (arg, &arg_lim, 10);
1092
1093   if (! (u <= maxval && errno != ERANGE) || *arg_lim)
1094     return false;
1095
1096   *num = u;
1097   return true;
1098 }
1099
1100 static bool
1101 pax_decode_header (struct tar_sparse_file *file)
1102 {
1103   if (file->stat_info->sparse_major > 0)
1104     {
1105       uintmax_t u;
1106       char nbuf[UINTMAX_STRSIZE_BOUND];
1107       union block *blk;
1108       char *p;
1109       size_t i;
1110
1111 #define COPY_BUF(b,buf,src) do                                     \
1112  {                                                                 \
1113    char *endp = b->buffer + BLOCKSIZE;                             \
1114    char *dst = buf;                                                \
1115    do                                                              \
1116      {                                                             \
1117        if (dst == buf + UINTMAX_STRSIZE_BOUND -1)                  \
1118          {                                                         \
1119            ERROR ((0, 0, _("%s: numeric overflow in sparse archive member"), \
1120                   file->stat_info->orig_file_name));               \
1121            return false;                                           \
1122          }                                                         \
1123        if (src == endp)                                            \
1124          {                                                         \
1125            set_next_block_after (b);                               \
1126            file->dumped_size += BLOCKSIZE;                         \
1127            b = find_next_block ();                                 \
1128            src = b->buffer;                                        \
1129            endp = b->buffer + BLOCKSIZE;                           \
1130          }                                                         \
1131        *dst = *src++;                                              \
1132      }                                                             \
1133    while (*dst++ != '\n');                                         \
1134    dst[-1] = 0;                                                    \
1135  } while (0)
1136
1137       set_next_block_after (current_header);
1138       file->dumped_size += BLOCKSIZE;
1139       blk = find_next_block ();
1140       p = blk->buffer;
1141       COPY_BUF (blk,nbuf,p);
1142       if (!decode_num (&u, nbuf, TYPE_MAXIMUM (size_t)))
1143         {
1144           ERROR ((0, 0, _("%s: malformed sparse archive member"),
1145                   file->stat_info->orig_file_name));
1146           return false;
1147         }
1148       file->stat_info->sparse_map_size = u;
1149       file->stat_info->sparse_map = xcalloc (file->stat_info->sparse_map_size,
1150                                              sizeof (*file->stat_info->sparse_map));
1151       file->stat_info->sparse_map_avail = 0;
1152       for (i = 0; i < file->stat_info->sparse_map_size; i++)
1153         {
1154           struct sp_array sp;
1155
1156           COPY_BUF (blk,nbuf,p);
1157           if (!decode_num (&u, nbuf, TYPE_MAXIMUM (off_t)))
1158             {
1159               ERROR ((0, 0, _("%s: malformed sparse archive member"),
1160                       file->stat_info->orig_file_name));
1161               return false;
1162             }
1163           sp.offset = u;
1164           COPY_BUF (blk,nbuf,p);
1165           if (!decode_num (&u, nbuf, TYPE_MAXIMUM (off_t)))
1166             {
1167               ERROR ((0, 0, _("%s: malformed sparse archive member"),
1168                       file->stat_info->orig_file_name));
1169               return false;
1170             }
1171           sp.numbytes = u;
1172           sparse_add_map (file->stat_info, &sp);
1173         }
1174       set_next_block_after (blk);
1175     }
1176
1177   return true;
1178 }
1179
1180 static struct tar_sparse_optab const pax_optab = {
1181   NULL,  /* No init function */
1182   NULL,  /* No done function */
1183   pax_sparse_member_p,
1184   pax_dump_header,
1185   NULL,
1186   pax_decode_header,
1187   NULL,  /* No scan_block function */
1188   sparse_dump_region,
1189   sparse_extract_region,
1190 };