reconstruct.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * reconstruct.c
 *      Reconstruct full file from incremental file and backup chain.
 *
 * Copyright (c) 2017-2026, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *    src/bin/pg_combinebackup/reconstruct.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres_fe.h"
 
#include <unistd.h>
 
#include "backup/basebackup_incremental.h"
#include "common/file_perm.h"
#include "common/logging.h"
#include "copy_file.h"
#include "lib/stringinfo.h"
#include "reconstruct.h"
#include "storage/block.h"
 
/*
 * An rfile stores the data that we need in order to be able to use some file
 * on disk for reconstruction. For any given output file, we create one rfile
 * per backup that we need to consult when we constructing that output file.
 *
 * If we find a full version of the file in the backup chain, then only
 * filename and fd are initialized; the remaining fields are 0 or NULL.
 * For an incremental file, header_length, num_blocks, relative_block_numbers,
 * and truncation_block_length are also set.
 *
 * num_blocks_read and highest_offset_read always start out as 0.
 */
typedef struct rfile
{
    char       *filename;
    int         fd;
    size_t      header_length;
    unsigned    num_blocks;
    BlockNumber *relative_block_numbers;
    unsigned    truncation_block_length;
    unsigned    num_blocks_read;
    off_t       highest_offset_read;
} rfile;
 
static void debug_reconstruction(int n_source,
                                 rfile **sources,
                                 bool dry_run);
static unsigned find_reconstructed_block_length(const rfile *s);
static rfile *make_incremental_rfile(const char *filename);
static rfile *make_rfile(const char *filename, bool missing_ok);
static void write_reconstructed_file(const char *input_filename,
                                     const char *output_filename,
                                     unsigned block_length,
                                     rfile **sourcemap,
                                     const off_t *offsetmap,
                                     pg_checksum_context *checksum_ctx,
                                     CopyMethod copy_method,
                                     bool debug,
                                     bool dry_run);
static void read_bytes(const rfile *rf, void *buffer, size_t length);
static void write_block(int fd, const char *output_filename,
                        const uint8 *buffer,
                        pg_checksum_context *checksum_ctx);
static void read_block(const rfile *s, off_t off, uint8 *buffer);
 
/*
 * Reconstruct a full file from an incremental file and a chain of prior
 * backups.
 *
 * input_filename should be the path to the incremental file, and
 * output_filename should be the path where the reconstructed file is to be
 * written.
 *
 * relative_path should be the path to the directory containing this file,
 * relative to the root of the backup (NOT relative to the root of the
 * tablespace). It must always end with a trailing slash. bare_file_name
 * should be the name of the file within that directory, without
 * "INCREMENTAL.".
 *
 * n_prior_backups is the number of prior backups, and prior_backup_dirs is
 * an array of pathnames where those backups can be found.
 */
void
reconstruct_from_incremental_file(char *input_filename,
                                  char *output_filename,
                                  char *relative_path,
                                  char *bare_file_name,
                                  int n_prior_backups,
                                  char **prior_backup_dirs,
                                  manifest_data **manifests,
                                  char *manifest_path,
                                  pg_checksum_type checksum_type,
                                  int *checksum_length,
                                  uint8 **checksum_payload,
                                  CopyMethod copy_method,
                                  bool debug,
                                  bool dry_run)
{
    rfile     **source;
    rfile      *latest_source = NULL;
    rfile     **sourcemap;
    off_t      *offsetmap;
    unsigned    block_length;
    unsigned    sidx = n_prior_backups;
    bool        full_copy_possible = true;
    int         copy_source_index = -1;
    rfile      *copy_source = NULL;
    pg_checksum_context checksum_ctx;
 
    /* Sanity check the relative_path. */
    Assert(relative_path[0] != '\0');
    Assert(relative_path[strlen(relative_path) - 1] == '/');
 
    /*
     * Every block must come either from the latest version of the file or
     * from one of the prior backups.
     */
    source = pg_malloc0_array(rfile *, 1 + n_prior_backups);
 
    /*
     * Use the information from the latest incremental file to figure out how
     * long the reconstructed file should be.
     */
    latest_source = make_incremental_rfile(input_filename);
    source[n_prior_backups] = latest_source;
    block_length = find_reconstructed_block_length(latest_source);
 
    /*
     * For each block in the output file, we need to know from which file we
     * need to obtain it and at what offset in that file it's stored.
     * sourcemap gives us the first of these things, and offsetmap the latter.
     */
    sourcemap = pg_malloc0_array(rfile *, block_length);
    offsetmap = pg_malloc0_array(off_t, block_length);
 
    /*
     * Every block that is present in the newest incremental file should be
     * sourced from that file. If it precedes the truncation_block_length,
     * it's a block that we would otherwise have had to find in an older
     * backup and thus reduces the number of blocks remaining to be found by
     * one; otherwise, it's an extra block that needs to be included in the
     * output but would not have needed to be found in an older backup if it
     * had not been present.
     */
    for (unsigned i = 0; i < latest_source->num_blocks; ++i)
    {
        BlockNumber b = latest_source->relative_block_numbers[i];
 
        Assert(b < block_length);
        sourcemap[b] = latest_source;
        offsetmap[b] = latest_source->header_length + (i * BLCKSZ);
 
        /*
         * A full copy of a file from an earlier backup is only possible if no
         * blocks are needed from any later incremental file.
         */
        full_copy_possible = false;
    }
 
    while (1)
    {
        char        source_filename[MAXPGPATH];
        rfile      *s;
 
        /*
         * Move to the next backup in the chain. If there are no more, then
         * we're done.
         */
        if (sidx == 0)
            break;
        --sidx;
 
        /*
         * Look for the full file in the previous backup. If not found, then
         * look for an incremental file instead.
         */
        snprintf(source_filename, MAXPGPATH, "%s/%s%s",
                 prior_backup_dirs[sidx], relative_path, bare_file_name);
        if ((s = make_rfile(source_filename, true)) == NULL)
        {
            snprintf(source_filename, MAXPGPATH, "%s/%sINCREMENTAL.%s",
                     prior_backup_dirs[sidx], relative_path, bare_file_name);
            s = make_incremental_rfile(source_filename);
        }
        source[sidx] = s;
 
        /*
         * If s->header_length == 0, then this is a full file; otherwise, it's
         * an incremental file.
         */
        if (s->header_length == 0)
        {
            struct stat sb;
            BlockNumber b;
            BlockNumber blocklength;
 
            /* We need to know the length of the file. */
            if (fstat(s->fd, &sb) < 0)
                pg_fatal("could not stat file \"%s\": %m", s->filename);
 
            /*
             * Since we found a full file, source all blocks from it that
             * exist in the file.
             *
             * Note that there may be blocks that don't exist either in this
             * file or in any incremental file but that precede
             * truncation_block_length. These are, presumably, zero-filled
             * blocks that result from the server extending the file but
             * taking no action on those blocks that generated any WAL.
             *
             * Sadly, we have no way of validating that this is really what
             * happened, and neither does the server.  From its perspective,
             * an unmodified block that contains data looks exactly the same
             * as a zero-filled block that never had any data: either way,
             * it's not mentioned in any WAL summary and the server has no
             * reason to read it. From our perspective, all we know is that
             * nobody had a reason to back up the block. That certainly means
             * that the block didn't exist at the time of the full backup, but
             * the supposition that it was all zeroes at the time of every
             * later backup is one that we can't validate.
             */
            blocklength = sb.st_size / BLCKSZ;
            for (b = 0; b < latest_source->truncation_block_length; ++b)
            {
                if (sourcemap[b] == NULL && b < blocklength)
                {
                    sourcemap[b] = s;
                    offsetmap[b] = b * BLCKSZ;
                }
            }
 
            /*
             * If a full copy looks possible, check whether the resulting file
             * should be exactly as long as the source file is. If so, a full
             * copy is acceptable, otherwise not.
             */
            if (full_copy_possible)
            {
                uint64      expected_length;
 
                expected_length =
                    (uint64) latest_source->truncation_block_length;
                expected_length *= BLCKSZ;
                if (expected_length == sb.st_size)
                {
                    copy_source = s;
                    copy_source_index = sidx;
                }
            }
 
            /* We don't need to consider any further sources. */
            break;
        }
 
        /*
         * Since we found another incremental file, source all blocks from it
         * that we need but don't yet have.
         */
        for (unsigned i = 0; i < s->num_blocks; ++i)
        {
            BlockNumber b = s->relative_block_numbers[i];
 
            if (b < latest_source->truncation_block_length &&
                sourcemap[b] == NULL)
            {
                sourcemap[b] = s;
                offsetmap[b] = s->header_length + (i * BLCKSZ);
 
                /*
                 * A full copy of a file from an earlier backup is only
                 * possible if no blocks are needed from any later incremental
                 * file.
                 */
                full_copy_possible = false;
            }
        }
    }
 
    /*
     * If a checksum of the required type already exists in the
     * backup_manifest for the relevant input directory, we can save some work
     * by reusing that checksum instead of computing a new one.
     */
    if (copy_source_index >= 0 && manifests[copy_source_index] != NULL &&
        checksum_type != CHECKSUM_TYPE_NONE)
    {
        manifest_file *mfile;
 
        mfile = manifest_files_lookup(manifests[copy_source_index]->files,
                                      manifest_path);
        if (mfile == NULL)
        {
            char       *path = psprintf("%s/backup_manifest",
                                        prior_backup_dirs[copy_source_index]);
 
            /*
             * The directory is out of sync with the backup_manifest, so emit
             * a warning.
             */
            pg_log_warning("manifest file \"%s\" contains no entry for file \"%s\"",
                           path,
                           manifest_path);
            pfree(path);
        }
        else if (mfile->checksum_type == checksum_type)
        {
            *checksum_length = mfile->checksum_length;
            *checksum_payload = pg_malloc(*checksum_length);
            memcpy(*checksum_payload, mfile->checksum_payload,
                   *checksum_length);
            checksum_type = CHECKSUM_TYPE_NONE;
        }
    }
 
    /* Prepare for checksum calculation, if required. */
    pg_checksum_init(&checksum_ctx, checksum_type);
 
    /*
     * If the full file can be created by copying a file from an older backup
     * in the chain without needing to overwrite any blocks or truncate the
     * result, then forget about performing reconstruction and just copy that
     * file in its entirety.
     *
     * If we have only incremental files, and there's no full file at any
     * point in the backup chain, something has gone wrong. Emit an error.
     *
     * Otherwise, reconstruct.
     */
    if (copy_source != NULL)
        copy_file(copy_source->filename, output_filename,
                  &checksum_ctx, copy_method, dry_run);
    else if (sidx == 0 && source[0]->header_length != 0)
    {
        pg_fatal("full backup contains unexpected incremental file \"%s\"",
                 source[0]->filename);
    }
    else
    {
        write_reconstructed_file(input_filename, output_filename,
                                 block_length, sourcemap, offsetmap,
                                 &checksum_ctx, copy_method,
                                 debug, dry_run);
        debug_reconstruction(n_prior_backups + 1, source, dry_run);
    }
 
    /* Save results of checksum calculation. */
    if (checksum_type != CHECKSUM_TYPE_NONE)
    {
        *checksum_payload = pg_malloc(PG_CHECKSUM_MAX_LENGTH);
        *checksum_length = pg_checksum_final(&checksum_ctx,
                                             *checksum_payload);
    }
 
    /*
     * Close files and release memory.
     */
    for (int i = 0; i <= n_prior_backups; ++i)
    {
        rfile      *s = source[i];
 
        if (s == NULL)
            continue;
        if (close(s->fd) != 0)
            pg_fatal("could not close file \"%s\": %m", s->filename);
        if (s->relative_block_numbers != NULL)
            pfree(s->relative_block_numbers);
        pg_free(s->filename);
        pg_free(s);
    }
    pg_free(sourcemap);
    pg_free(offsetmap);
    pg_free(source);
}
 
/*
 * Perform post-reconstruction logging and sanity checks.
 */
static void
debug_reconstruction(int n_source, rfile **sources, bool dry_run)
{
    for (int i = 0; i < n_source; ++i)
    {
        rfile      *s = sources[i];
 
        /* Ignore source if not used. */
        if (s == NULL)
            continue;
 
        /* If no data is needed from this file, we can ignore it. */
        if (s->num_blocks_read == 0)
            continue;
 
        /* Debug logging. */
        if (dry_run)
            pg_log_debug("would have read %u blocks from \"%s\"",
                         s->num_blocks_read, s->filename);
        else
            pg_log_debug("read %u blocks from \"%s\"",
                         s->num_blocks_read, s->filename);
 
        /*
         * In dry-run mode, we don't actually try to read data from the file,
         * but we do try to verify that the file is long enough that we could
         * have read the data if we'd tried.
         *
         * If this fails, then it means that a non-dry-run attempt would fail,
         * complaining of not being able to read the required bytes from the
         * file.
         */
        if (dry_run)
        {
            struct stat sb;
 
            if (fstat(s->fd, &sb) < 0)
                pg_fatal("could not stat file \"%s\": %m", s->filename);
            if (sb.st_size < s->highest_offset_read)
                pg_fatal("file \"%s\" is too short: expected %lld, found %lld",
                         s->filename,
                         (long long) s->highest_offset_read,
                         (long long) sb.st_size);
        }
    }
}
 
/*
 * When we perform reconstruction using an incremental file, the output file
 * should be at least as long as the truncation_block_length. Any blocks
 * present in the incremental file increase the output length as far as is
 * necessary to include those blocks.
 */
static unsigned
find_reconstructed_block_length(const rfile *s)
{
    unsigned    block_length = s->truncation_block_length;
    unsigned    i;
 
    for (i = 0; i < s->num_blocks; ++i)
        if (s->relative_block_numbers[i] >= block_length)
            block_length = s->relative_block_numbers[i] + 1;
 
    return block_length;
}
 
/*
 * Initialize an incremental rfile, reading the header so that we know which
 * blocks it contains.
 */
static rfile *
make_incremental_rfile(const char *filename)
{
    rfile      *rf;
    unsigned    magic;
 
    rf = make_rfile(filename, false);
 
    /* Read and validate magic number. */
    read_bytes(rf, &magic, sizeof(magic));
    if (magic != INCREMENTAL_MAGIC)
        pg_fatal("file \"%s\" has bad incremental magic number (0x%x, expected 0x%x)",
                 filename, magic, INCREMENTAL_MAGIC);
 
    /* Read block count. */
    read_bytes(rf, &rf->num_blocks, sizeof(rf->num_blocks));
    if (rf->num_blocks > RELSEG_SIZE)
        pg_fatal("file \"%s\" has block count %u in excess of segment size %u",
                 filename, rf->num_blocks, RELSEG_SIZE);
 
    /* Read truncation block length. */
    read_bytes(rf, &rf->truncation_block_length,
               sizeof(rf->truncation_block_length));
    if (rf->truncation_block_length > RELSEG_SIZE)
        pg_fatal("file \"%s\" has truncation block length %u in excess of segment size %u",
                 filename, rf->truncation_block_length, RELSEG_SIZE);
 
    /* Read block numbers if there are any. */
    if (rf->num_blocks > 0)
    {
        rf->relative_block_numbers =
            pg_malloc0_array(BlockNumber, rf->num_blocks);
        read_bytes(rf, rf->relative_block_numbers,
                   sizeof(BlockNumber) * rf->num_blocks);
    }
 
    /* Remember length of header. */
    rf->header_length = sizeof(magic) + sizeof(rf->num_blocks) +
        sizeof(rf->truncation_block_length) +
        sizeof(BlockNumber) * rf->num_blocks;
 
    /*
     * Round header length to a multiple of BLCKSZ, so that blocks contents
     * are properly aligned. Only do this when the file actually has data for
     * some blocks.
     */
    if ((rf->num_blocks > 0) && ((rf->header_length % BLCKSZ) != 0))
        rf->header_length += (BLCKSZ - (rf->header_length % BLCKSZ));
 
    return rf;
}
 
/*
 * Allocate and perform basic initialization of an rfile.
 */
static rfile *
make_rfile(const char *filename, bool missing_ok)
{
    rfile      *rf;
 
    rf = pg_malloc0_object(rfile);
    rf->filename = pstrdup(filename);
    if ((rf->fd = open(filename, O_RDONLY | PG_BINARY, 0)) < 0)
    {
        if (missing_ok && errno == ENOENT)
        {
            pfree(rf->filename);
            pg_free(rf);
            return NULL;
        }
        pg_fatal("could not open file \"%s\": %m", filename);
    }
 
    return rf;
}
 
/*
 * Read the indicated number of bytes from an rfile into the buffer.
 */
static void
read_bytes(const rfile *rf, void *buffer, size_t length)
{
    ssize_t     rb;
 
    rb = read(rf->fd, buffer, length);
 
    if (rb != length)
    {
        if (rb < 0)
            pg_fatal("could not read file \"%s\": %m", rf->filename);
        else
            pg_fatal("could not read file \"%s\": read %zd of %zu",
                     rf->filename, rb, length);
    }
}
 
/*
 * Write out a reconstructed file.
 */
static void
write_reconstructed_file(const char *input_filename,
                         const char *output_filename,
                         unsigned block_length,
                         rfile **sourcemap,
                         const off_t *offsetmap,
                         pg_checksum_context *checksum_ctx,
                         CopyMethod copy_method,
                         bool debug,
                         bool dry_run)
{
    int         wfd = -1;
    unsigned    i;
    unsigned    zero_blocks = 0;
 
    /* Debugging output. */
    if (debug)
    {
        StringInfoData debug_buf;
        unsigned    start_of_range = 0;
        unsigned    current_block = 0;
 
        /* Basic information about the output file to be produced. */
        if (dry_run)
            pg_log_debug("would reconstruct \"%s\" (%u blocks, checksum %s)",
                         output_filename, block_length,
                         pg_checksum_type_name(checksum_ctx->type));
        else
            pg_log_debug("reconstructing \"%s\" (%u blocks, checksum %s)",
                         output_filename, block_length,
                         pg_checksum_type_name(checksum_ctx->type));
 
        /* Print out the plan for reconstructing this file. */
        initStringInfo(&debug_buf);
        while (current_block < block_length)
        {
            rfile      *s = sourcemap[current_block];
 
            /* Extend range, if possible. */
            if (current_block + 1 < block_length &&
                s == sourcemap[current_block + 1])
            {
                ++current_block;
                continue;
            }
 
            /* Add details about this range. */
            if (s == NULL)
            {
                if (current_block == start_of_range)
                    appendStringInfo(&debug_buf, " %u:zero", current_block);
                else
                    appendStringInfo(&debug_buf, " %u-%u:zero",
                                     start_of_range, current_block);
            }
            else
            {
                if (current_block == start_of_range)
                    appendStringInfo(&debug_buf, " %u:%s@" UINT64_FORMAT,
                                     current_block, s->filename,
                                     (uint64) offsetmap[current_block]);
                else
                    appendStringInfo(&debug_buf, " %u-%u:%s@" UINT64_FORMAT,
                                     start_of_range, current_block,
                                     s->filename,
                                     (uint64) offsetmap[current_block]);
            }
 
            /* Begin new range. */
            start_of_range = ++current_block;
 
            /* If the output is very long or we are done, dump it now. */
            if (current_block == block_length || debug_buf.len > 1024)
            {
                pg_log_debug("reconstruction plan:%s", debug_buf.data);
                resetStringInfo(&debug_buf);
            }
        }
 
        /* Free memory. */
        pfree(debug_buf.data);
    }
 
    /* Open the output file, except in dry_run mode. */
    if (!dry_run &&
        (wfd = open(output_filename,
                    O_RDWR | PG_BINARY | O_CREAT | O_EXCL,
                    pg_file_create_mode)) < 0)
        pg_fatal("could not open file \"%s\": %m", output_filename);
 
    /* Read and write the blocks as required. */
    for (i = 0; i < block_length; ++i)
    {
        uint8       buffer[BLCKSZ];
        rfile      *s = sourcemap[i];
 
        /* Update accounting information. */
        if (s == NULL)
            ++zero_blocks;
        else
        {
            s->num_blocks_read++;
            s->highest_offset_read = Max(s->highest_offset_read,
                                         offsetmap[i] + BLCKSZ);
        }
 
        /* Skip the rest of this in dry-run mode. */
        if (dry_run)
            continue;
 
        /* Read or zero-fill the block as appropriate. */
        if (s == NULL)
        {
            /*
             * New block not mentioned in the WAL summary. Should have been an
             * uninitialized block, so just zero-fill it.
             */
            memset(buffer, 0, BLCKSZ);
 
            /* Write out the block, update the checksum if needed. */
            write_block(wfd, output_filename, buffer, checksum_ctx);
 
            /* Nothing else to do for zero-filled blocks. */
            continue;
        }
 
        /* Copy the block using the appropriate copy method. */
        if (copy_method != COPY_METHOD_COPY_FILE_RANGE)
        {
            /*
             * Read the block from the correct source file, and then write it
             * out, possibly with a checksum update.
             */
            read_block(s, offsetmap[i], buffer);
            write_block(wfd, output_filename, buffer, checksum_ctx);
        }
        else                    /* use copy_file_range */
        {
#if defined(HAVE_COPY_FILE_RANGE)
            /* copy_file_range modifies the offset, so use a local copy */
            off_t       off = offsetmap[i];
            size_t      nwritten = 0;
 
            /*
             * Retry until we've written all the bytes (the offset is updated
             * by copy_file_range, and so is the wfd file offset).
             */
            do
            {
                ssize_t     wb;
 
                wb = copy_file_range(s->fd, &off, wfd, NULL, BLCKSZ - nwritten, 0);
 
                if (wb < 0)
                    pg_fatal("error while copying file range from \"%s\" to \"%s\": %m",
                             input_filename, output_filename);
                else if (wb == 0)
                    pg_fatal("unexpected end of file while copying file range from \"%s\" to \"%s\"",
                             input_filename, output_filename);
 
                nwritten += wb;
 
            } while (BLCKSZ > nwritten);
 
            /*
             * When checksum calculation not needed, we're done, otherwise
             * read the block and pass it to the checksum calculation.
             */
            if (checksum_ctx->type == CHECKSUM_TYPE_NONE)
                continue;
 
            read_block(s, offsetmap[i], buffer);
 
            if (pg_checksum_update(checksum_ctx, buffer, BLCKSZ) < 0)
                pg_fatal("could not update checksum of file \"%s\"",
                         output_filename);
#else
            pg_fatal("copy_file_range not supported on this platform");
#endif
        }
    }
 
    /* Debugging output. */
    if (zero_blocks > 0)
    {
        if (dry_run)
            pg_log_debug("would have zero-filled %u blocks", zero_blocks);
        else
            pg_log_debug("zero-filled %u blocks", zero_blocks);
    }
 
    /* Close the output file. */
    if (wfd >= 0 && close(wfd) != 0)
        pg_fatal("could not close file \"%s\": %m", output_filename);
}
 
/*
 * Write the block into the file (using the file descriptor), and
 * if needed update the checksum calculation.
 *
 * The buffer is expected to contain BLCKSZ bytes. The filename is
 * provided only for the error message.
 */
static void
write_block(int fd, const char *output_filename,
            const uint8 *buffer, pg_checksum_context *checksum_ctx)
{
    ssize_t     wb;
 
    if ((wb = write(fd, buffer, BLCKSZ)) != BLCKSZ)
    {
        if (wb < 0)
            pg_fatal("could not write file \"%s\": %m", output_filename);
        else
            pg_fatal("could not write file \"%s\": wrote %zd of %zu",
                     output_filename, wb, (size_t) BLCKSZ);
    }
 
    /* Update the checksum computation. */
    if (pg_checksum_update(checksum_ctx, buffer, BLCKSZ) < 0)
        pg_fatal("could not update checksum of file \"%s\"",
                 output_filename);
}
 
/*
 * Read a block of data (BLCKSZ bytes) into the buffer.
 */
static void
read_block(const rfile *s, off_t off, uint8 *buffer)
{
    ssize_t     rb;
 
    /* Read the block from the correct source, except if dry-run. */
    rb = pg_pread(s->fd, buffer, BLCKSZ, off);
    if (rb != BLCKSZ)
    {
        if (rb < 0)
            pg_fatal("could not read from file \"%s\": %m", s->filename);
        else
            pg_fatal("could not read from file \"%s\", offset %lld: read %zd of %zu",
                     s->filename, (long long) off, rb, (size_t) BLCKSZ);
    }
}