git.cworth.org Git - tar/blob - src/sparse.c

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