/* Functions for dealing with sparse files Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include #include #include #include "common.h" struct tar_sparse_file; static bool sparse_select_optab (struct tar_sparse_file *file); enum sparse_scan_state { scan_begin, scan_block, scan_end }; struct tar_sparse_optab { bool (*init) (struct tar_sparse_file *); bool (*done) (struct tar_sparse_file *); bool (*sparse_member_p) (struct tar_sparse_file *); bool (*dump_header) (struct tar_sparse_file *); bool (*fixup_header) (struct tar_sparse_file *); bool (*decode_header) (struct tar_sparse_file *); bool (*scan_block) (struct tar_sparse_file *, enum sparse_scan_state, void *); bool (*dump_region) (struct tar_sparse_file *, size_t); bool (*extract_region) (struct tar_sparse_file *, size_t); }; struct tar_sparse_file { int fd; /* File descriptor */ bool seekable; /* Is fd seekable? */ off_t offset; /* Current offset in fd if seekable==false. Otherwise unused */ off_t dumped_size; /* Number of bytes actually written to the archive */ struct tar_stat_info *stat_info; /* Information about the file */ struct tar_sparse_optab const *optab; /* Operation table */ void *closure; /* Any additional data optab calls might require */ }; /* Dump zeros to file->fd until offset is reached. It is used instead of lseek if the output file is not seekable */ static bool dump_zeros (struct tar_sparse_file *file, off_t offset) { static char const zero_buf[BLOCKSIZE]; if (offset < file->offset) { errno = EINVAL; return false; } while (file->offset < offset) { size_t size = (BLOCKSIZE < offset - file->offset ? BLOCKSIZE : offset - file->offset); ssize_t wrbytes; wrbytes = write (file->fd, zero_buf, size); if (wrbytes <= 0) { if (wrbytes == 0) errno = EINVAL; return false; } file->offset += wrbytes; } return true; } static bool tar_sparse_member_p (struct tar_sparse_file *file) { if (file->optab->sparse_member_p) return file->optab->sparse_member_p (file); return false; } static bool tar_sparse_init (struct tar_sparse_file *file) { memset (file, 0, sizeof *file); if (!sparse_select_optab (file)) return false; if (file->optab->init) return file->optab->init (file); return true; } static bool tar_sparse_done (struct tar_sparse_file *file) { if (file->optab->done) return file->optab->done (file); return true; } static bool tar_sparse_scan (struct tar_sparse_file *file, enum sparse_scan_state state, void *block) { if (file->optab->scan_block) return file->optab->scan_block (file, state, block); return true; } static bool tar_sparse_dump_region (struct tar_sparse_file *file, size_t i) { if (file->optab->dump_region) return file->optab->dump_region (file, i); return false; } static bool tar_sparse_extract_region (struct tar_sparse_file *file, size_t i) { if (file->optab->extract_region) return file->optab->extract_region (file, i); return false; } static bool tar_sparse_dump_header (struct tar_sparse_file *file) { if (file->optab->dump_header) return file->optab->dump_header (file); return false; } static bool tar_sparse_decode_header (struct tar_sparse_file *file) { if (file->optab->decode_header) return file->optab->decode_header (file); return true; } static bool tar_sparse_fixup_header (struct tar_sparse_file *file) { if (file->optab->fixup_header) return file->optab->fixup_header (file); return true; } static bool lseek_or_error (struct tar_sparse_file *file, off_t offset) { if (file->seekable ? lseek (file->fd, offset, SEEK_SET) < 0 : ! dump_zeros (file, offset)) { seek_diag_details (file->stat_info->orig_file_name, offset); return false; } return true; } /* Takes a blockful of data and basically cruises through it to see if it's made *entirely* of zeros, returning a 0 the instant it finds something that is a nonzero, i.e., useful data. */ static bool zero_block_p (char const *buffer, size_t size) { while (size--) if (*buffer++) return false; return true; } static void sparse_add_map (struct tar_stat_info *st, struct sp_array const *sp) { struct sp_array *sparse_map = st->sparse_map; size_t avail = st->sparse_map_avail; if (avail == st->sparse_map_size) st->sparse_map = sparse_map = x2nrealloc (sparse_map, &st->sparse_map_size, sizeof *sparse_map); sparse_map[avail] = *sp; st->sparse_map_avail = avail + 1; } /* Scan the sparse file and create its map */ static bool sparse_scan_file (struct tar_sparse_file *file) { struct tar_stat_info *st = file->stat_info; int fd = file->fd; char buffer[BLOCKSIZE]; size_t count; off_t offset = 0; struct sp_array sp = {0, 0}; if (!lseek_or_error (file, 0)) return false; st->archive_file_size = 0; if (!tar_sparse_scan (file, scan_begin, NULL)) return false; while ((count = safe_read (fd, buffer, sizeof buffer)) != 0 && count != SAFE_READ_ERROR) { /* Analyze the block. */ if (zero_block_p (buffer, count)) { if (sp.numbytes) { sparse_add_map (st, &sp); sp.numbytes = 0; if (!tar_sparse_scan (file, scan_block, NULL)) return false; } } else { if (sp.numbytes == 0) sp.offset = offset; sp.numbytes += count; st->archive_file_size += count; if (!tar_sparse_scan (file, scan_block, buffer)) return false; } offset += count; } if (sp.numbytes == 0) sp.offset = offset; sparse_add_map (st, &sp); st->archive_file_size += count; return tar_sparse_scan (file, scan_end, NULL); } static struct tar_sparse_optab const oldgnu_optab; static struct tar_sparse_optab const star_optab; static struct tar_sparse_optab const pax_optab; static bool sparse_select_optab (struct tar_sparse_file *file) { switch (current_format == DEFAULT_FORMAT ? archive_format : current_format) { case V7_FORMAT: case USTAR_FORMAT: return false; case OLDGNU_FORMAT: case GNU_FORMAT: /*FIXME: This one should disappear? */ file->optab = &oldgnu_optab; break; case POSIX_FORMAT: file->optab = &pax_optab; break; case STAR_FORMAT: file->optab = &star_optab; break; default: return false; } return true; } static bool sparse_dump_region (struct tar_sparse_file *file, size_t i) { union block *blk; off_t bytes_left = file->stat_info->sparse_map[i].numbytes; if (!lseek_or_error (file, file->stat_info->sparse_map[i].offset)) return false; while (bytes_left > 0) { size_t bufsize = (bytes_left > BLOCKSIZE) ? BLOCKSIZE : bytes_left; size_t bytes_read; blk = find_next_block (); bytes_read = safe_read (file->fd, blk->buffer, bufsize); if (bytes_read == SAFE_READ_ERROR) { read_diag_details (file->stat_info->orig_file_name, (file->stat_info->sparse_map[i].offset + file->stat_info->sparse_map[i].numbytes - bytes_left), bufsize); return false; } memset (blk->buffer + bytes_read, 0, BLOCKSIZE - bytes_read); bytes_left -= bytes_read; file->dumped_size += bytes_read; mv_size_left (file->stat_info->archive_file_size - file->dumped_size); set_next_block_after (blk); } return true; } static bool sparse_extract_region (struct tar_sparse_file *file, size_t i) { size_t write_size; if (!lseek_or_error (file, file->stat_info->sparse_map[i].offset)) return false; write_size = file->stat_info->sparse_map[i].numbytes; if (write_size == 0) { /* Last block of the file is a hole */ if (file->seekable && sys_truncate (file->fd)) truncate_warn (file->stat_info->orig_file_name); } else while (write_size > 0) { size_t count; size_t wrbytes = (write_size > BLOCKSIZE) ? BLOCKSIZE : write_size; union block *blk = find_next_block (); if (!blk) { ERROR ((0, 0, _("Unexpected EOF in archive"))); return false; } set_next_block_after (blk); count = full_write (file->fd, blk->buffer, wrbytes); write_size -= count; file->dumped_size += count; mv_size_left (file->stat_info->archive_file_size - file->dumped_size); file->offset += count; if (count != wrbytes) { write_error_details (file->stat_info->orig_file_name, count, wrbytes); return false; } } return true; } /* Interface functions */ enum dump_status sparse_dump_file (int fd, struct tar_stat_info *st) { bool rc; struct tar_sparse_file file; if (!tar_sparse_init (&file)) return dump_status_not_implemented; file.stat_info = st; file.fd = fd; file.seekable = true; /* File *must* be seekable for dump to work */ rc = sparse_scan_file (&file); if (rc && file.optab->dump_region) { tar_sparse_dump_header (&file); if (fd >= 0) { size_t i; mv_begin (file.stat_info); for (i = 0; rc && i < file.stat_info->sparse_map_avail; i++) rc = tar_sparse_dump_region (&file, i); mv_end (); } } pad_archive (file.stat_info->archive_file_size - file.dumped_size); return (tar_sparse_done (&file) && rc) ? dump_status_ok : dump_status_short; } /* Returns true if the file represented by stat is a sparse one */ bool sparse_file_p (struct tar_stat_info *st) { return (ST_NBLOCKS (st->stat) < (st->stat.st_size / ST_NBLOCKSIZE + (st->stat.st_size % ST_NBLOCKSIZE != 0))); } bool sparse_member_p (struct tar_stat_info *st) { struct tar_sparse_file file; if (!tar_sparse_init (&file)) return false; file.stat_info = st; return tar_sparse_member_p (&file); } bool sparse_fixup_header (struct tar_stat_info *st) { struct tar_sparse_file file; if (!tar_sparse_init (&file)) return false; file.stat_info = st; return tar_sparse_fixup_header (&file); } enum dump_status sparse_extract_file (int fd, struct tar_stat_info *st, off_t *size) { bool rc = true; struct tar_sparse_file file; size_t i; if (!tar_sparse_init (&file)) return dump_status_not_implemented; file.stat_info = st; file.fd = fd; file.seekable = lseek (fd, 0, SEEK_SET) == 0; file.offset = 0; rc = tar_sparse_decode_header (&file); for (i = 0; rc && i < file.stat_info->sparse_map_avail; i++) rc = tar_sparse_extract_region (&file, i); *size = file.stat_info->archive_file_size - file.dumped_size; return (tar_sparse_done (&file) && rc) ? dump_status_ok : dump_status_short; } enum dump_status sparse_skip_file (struct tar_stat_info *st) { bool rc = true; struct tar_sparse_file file; if (!tar_sparse_init (&file)) return dump_status_not_implemented; file.stat_info = st; file.fd = -1; rc = tar_sparse_decode_header (&file); skip_file (file.stat_info->archive_file_size); return (tar_sparse_done (&file) && rc) ? dump_status_ok : dump_status_short; } static bool check_sparse_region (struct tar_sparse_file *file, off_t beg, off_t end) { if (!lseek_or_error (file, beg)) return false; while (beg < end) { size_t bytes_read; size_t rdsize = BLOCKSIZE < end - beg ? BLOCKSIZE : end - beg; char diff_buffer[BLOCKSIZE]; bytes_read = safe_read (file->fd, diff_buffer, rdsize); if (bytes_read == SAFE_READ_ERROR) { read_diag_details (file->stat_info->orig_file_name, beg, rdsize); return false; } if (!zero_block_p (diff_buffer, bytes_read)) { char begbuf[INT_BUFSIZE_BOUND (off_t)]; report_difference (file->stat_info, _("File fragment at %s is not a hole"), offtostr (beg, begbuf)); return false; } beg += bytes_read; } return true; } static bool check_data_region (struct tar_sparse_file *file, size_t i) { size_t size_left; if (!lseek_or_error (file, file->stat_info->sparse_map[i].offset)) return false; size_left = file->stat_info->sparse_map[i].numbytes; mv_size_left (file->stat_info->archive_file_size - file->dumped_size); while (size_left > 0) { size_t bytes_read; size_t rdsize = (size_left > BLOCKSIZE) ? BLOCKSIZE : size_left; char diff_buffer[BLOCKSIZE]; union block *blk = find_next_block (); if (!blk) { ERROR ((0, 0, _("Unexpected EOF in archive"))); return false; } set_next_block_after (blk); bytes_read = safe_read (file->fd, diff_buffer, rdsize); if (bytes_read == SAFE_READ_ERROR) { read_diag_details (file->stat_info->orig_file_name, (file->stat_info->sparse_map[i].offset + file->stat_info->sparse_map[i].numbytes - size_left), rdsize); return false; } file->dumped_size += bytes_read; size_left -= bytes_read; mv_size_left (file->stat_info->archive_file_size - file->dumped_size); if (memcmp (blk->buffer, diff_buffer, rdsize)) { report_difference (file->stat_info, _("Contents differ")); return false; } } return true; } bool sparse_diff_file (int fd, struct tar_stat_info *st) { bool rc = true; struct tar_sparse_file file; size_t i; off_t offset = 0; if (!tar_sparse_init (&file)) return dump_status_not_implemented; file.stat_info = st; file.fd = fd; file.seekable = true; /* File *must* be seekable for compare to work */ rc = tar_sparse_decode_header (&file); mv_begin (st); for (i = 0; rc && i < file.stat_info->sparse_map_avail; i++) { rc = check_sparse_region (&file, offset, file.stat_info->sparse_map[i].offset) && check_data_region (&file, i); offset = file.stat_info->sparse_map[i].offset + file.stat_info->sparse_map[i].numbytes; } if (!rc) skip_file (file.stat_info->archive_file_size - file.dumped_size); mv_end (); tar_sparse_done (&file); return rc; } /* Old GNU Format. The sparse file information is stored in the oldgnu_header in the following manner: The header is marked with type 'S'. Its `size' field contains the cumulative size of all non-empty blocks of the file. The actual file size is stored in `realsize' member of oldgnu_header. The map of the file is stored in a list of `struct sparse'. Each struct contains offset to the block of data and its size (both as octal numbers). The first file header contains at most 4 such structs (SPARSES_IN_OLDGNU_HEADER). If the map contains more structs, then the field `isextended' of the main header is set to 1 (binary) and the `struct sparse_header' header follows, containing at most 21 following structs (SPARSES_IN_SPARSE_HEADER). If more structs follow, `isextended' field of the extended header is set and next next extension header follows, etc... */ enum oldgnu_add_status { add_ok, add_finish, add_fail }; static bool oldgnu_sparse_member_p (struct tar_sparse_file *file __attribute__ ((unused))) { return current_header->header.typeflag == GNUTYPE_SPARSE; } /* Add a sparse item to the sparse file and its obstack */ static enum oldgnu_add_status oldgnu_add_sparse (struct tar_sparse_file *file, struct sparse *s) { struct sp_array sp; if (s->numbytes[0] == '\0') return add_finish; sp.offset = OFF_FROM_HEADER (s->offset); sp.numbytes = SIZE_FROM_HEADER (s->numbytes); if (sp.offset < 0 || file->stat_info->stat.st_size < sp.offset + sp.numbytes || file->stat_info->archive_file_size < 0) return add_fail; sparse_add_map (file->stat_info, &sp); return add_ok; } static bool oldgnu_fixup_header (struct tar_sparse_file *file) { /* NOTE! st_size was initialized from the header which actually contains archived size. The following fixes it */ file->stat_info->archive_file_size = file->stat_info->stat.st_size; file->stat_info->stat.st_size = OFF_FROM_HEADER (current_header->oldgnu_header.realsize); return true; } /* Convert old GNU format sparse data to internal representation */ static bool oldgnu_get_sparse_info (struct tar_sparse_file *file) { size_t i; union block *h = current_header; int ext_p; enum oldgnu_add_status rc; file->stat_info->sparse_map_avail = 0; for (i = 0; i < SPARSES_IN_OLDGNU_HEADER; i++) { rc = oldgnu_add_sparse (file, &h->oldgnu_header.sp[i]); if (rc != add_ok) break; } for (ext_p = h->oldgnu_header.isextended; rc == add_ok && ext_p; ext_p = h->sparse_header.isextended) { h = find_next_block (); if (!h) { ERROR ((0, 0, _("Unexpected EOF in archive"))); return false; } set_next_block_after (h); for (i = 0; i < SPARSES_IN_SPARSE_HEADER && rc == add_ok; i++) rc = oldgnu_add_sparse (file, &h->sparse_header.sp[i]); } if (rc == add_fail) { ERROR ((0, 0, _("%s: invalid sparse archive member"), file->stat_info->orig_file_name)); return false; } return true; } static void oldgnu_store_sparse_info (struct tar_sparse_file *file, size_t *pindex, struct sparse *sp, size_t sparse_size) { for (; *pindex < file->stat_info->sparse_map_avail && sparse_size > 0; sparse_size--, sp++, ++*pindex) { OFF_TO_CHARS (file->stat_info->sparse_map[*pindex].offset, sp->offset); SIZE_TO_CHARS (file->stat_info->sparse_map[*pindex].numbytes, sp->numbytes); } } static bool oldgnu_dump_header (struct tar_sparse_file *file) { off_t block_ordinal = current_block_ordinal (); union block *blk; size_t i; blk = start_header (file->stat_info); blk->header.typeflag = GNUTYPE_SPARSE; if (file->stat_info->sparse_map_avail > SPARSES_IN_OLDGNU_HEADER) blk->oldgnu_header.isextended = 1; /* Store the real file size */ OFF_TO_CHARS (file->stat_info->stat.st_size, blk->oldgnu_header.realsize); /* Store the effective (shrunken) file size */ OFF_TO_CHARS (file->stat_info->archive_file_size, blk->header.size); i = 0; oldgnu_store_sparse_info (file, &i, blk->oldgnu_header.sp, SPARSES_IN_OLDGNU_HEADER); blk->oldgnu_header.isextended = i < file->stat_info->sparse_map_avail; finish_header (file->stat_info, blk, block_ordinal); while (i < file->stat_info->sparse_map_avail) { blk = find_next_block (); memset (blk->buffer, 0, BLOCKSIZE); oldgnu_store_sparse_info (file, &i, blk->sparse_header.sp, SPARSES_IN_SPARSE_HEADER); set_next_block_after (blk); if (i < file->stat_info->sparse_map_avail) blk->sparse_header.isextended = 1; else break; } return true; } static struct tar_sparse_optab const oldgnu_optab = { NULL, /* No init function */ NULL, /* No done function */ oldgnu_sparse_member_p, oldgnu_dump_header, oldgnu_fixup_header, oldgnu_get_sparse_info, NULL, /* No scan_block function */ sparse_dump_region, sparse_extract_region, }; /* Star */ static bool star_sparse_member_p (struct tar_sparse_file *file __attribute__ ((unused))) { return current_header->header.typeflag == GNUTYPE_SPARSE; } static bool star_fixup_header (struct tar_sparse_file *file) { /* NOTE! st_size was initialized from the header which actually contains archived size. The following fixes it */ file->stat_info->archive_file_size = file->stat_info->stat.st_size; file->stat_info->stat.st_size = OFF_FROM_HEADER (current_header->star_in_header.realsize); return true; } /* Convert STAR format sparse data to internal representation */ static bool star_get_sparse_info (struct tar_sparse_file *file) { size_t i; union block *h = current_header; int ext_p; enum oldgnu_add_status rc = add_ok; file->stat_info->sparse_map_avail = 0; if (h->star_in_header.prefix[0] == '\0' && h->star_in_header.sp[0].offset[10] != '\0') { /* Old star format */ for (i = 0; i < SPARSES_IN_STAR_HEADER; i++) { rc = oldgnu_add_sparse (file, &h->star_in_header.sp[i]); if (rc != add_ok) break; } ext_p = h->star_in_header.isextended; } else ext_p = 1; for (; rc == add_ok && ext_p; ext_p = h->star_ext_header.isextended) { h = find_next_block (); if (!h) { ERROR ((0, 0, _("Unexpected EOF in archive"))); return false; } set_next_block_after (h); for (i = 0; i < SPARSES_IN_STAR_EXT_HEADER && rc == add_ok; i++) rc = oldgnu_add_sparse (file, &h->star_ext_header.sp[i]); } if (rc == add_fail) { ERROR ((0, 0, _("%s: invalid sparse archive member"), file->stat_info->orig_file_name)); return false; } return true; } static struct tar_sparse_optab const star_optab = { NULL, /* No init function */ NULL, /* No done function */ star_sparse_member_p, NULL, star_fixup_header, star_get_sparse_info, NULL, /* No scan_block function */ NULL, /* No dump region function */ sparse_extract_region, }; /* GNU PAX sparse file format. The sparse file map is stored in x header: GNU.sparse.size Real size of the stored file GNU.sparse.numblocks Number of blocks in the sparse map GNU.sparse.map Map of non-null data chunks. A string consisting of comma-separated values "offset,size[,offset,size]..." Tar versions 1.14-1.15.1 instead of the latter used: repeat numblocks time GNU.sparse.offset Offset of the next data block GNU.sparse.numbytes Size of the next data block end repeat This has been reported as conflicting with the POSIX specs. The reason is that offsets and sizes of non-zero data blocks were stored in multiple instances of GNU.sparse.offset/GNU.sparse.numbytes variables. However, POSIX requires the latest occurrence of the variable to override all previous occurrences. To avoid this incompatibility new keyword GNU.sparse.map was introduced in tar 1.15.2. Some people might still need the 1.14 way of handling sparse files for the compatibility reasons: it can be achieved by specifying `--pax-option delete=GNU.sparse.map' in the command line. See FIXME-1.14-1.15.1-1.20, below. */ static bool pax_sparse_member_p (struct tar_sparse_file *file) { return file->stat_info->sparse_map_avail > 0; } static bool pax_dump_header (struct tar_sparse_file *file) { off_t block_ordinal = current_block_ordinal (); union block *blk; size_t i; char nbuf[UINTMAX_STRSIZE_BOUND]; struct sp_array *map = file->stat_info->sparse_map; /* Store the real file size */ xheader_store ("GNU.sparse.size", file->stat_info, NULL); xheader_store ("GNU.sparse.numblocks", file->stat_info, NULL); /* FIXME-1.14-1.15.1-1.20: See the comment above. Starting with 1.17 this should display a warning about POSIX-incompatible keywords being generated. In 1.20, the true branch of the if block below will be removed and GNU.sparse.map will be marked in xhdr_tab as protected. */ if (xheader_keyword_deleted_p ("GNU.sparse.map")) { for (i = 0; i < file->stat_info->sparse_map_avail; i++) { xheader_store ("GNU.sparse.offset", file->stat_info, &i); xheader_store ("GNU.sparse.numbytes", file->stat_info, &i); } } else { xheader_string_begin (); for (i = 0; i < file->stat_info->sparse_map_avail; i++) { if (i) xheader_string_add (","); xheader_string_add (umaxtostr (map[i].offset, nbuf)); xheader_string_add (","); xheader_string_add (umaxtostr (map[i].numbytes, nbuf)); } xheader_string_end ("GNU.sparse.map"); } blk = start_header (file->stat_info); /* Store the effective (shrunken) file size */ OFF_TO_CHARS (file->stat_info->archive_file_size, blk->header.size); finish_header (file->stat_info, blk, block_ordinal); return true; } static struct tar_sparse_optab const pax_optab = { NULL, /* No init function */ NULL, /* No done function */ pax_sparse_member_p, pax_dump_header, NULL, /* No decode_header function */ NULL, /* No fixup_header function */ NULL, /* No scan_block function */ sparse_dump_region, sparse_extract_region, };