restore.pl

   1 #!/usr/bin/perl -w
   2 #
   3 # Proof-of-concept/reference decoder for LBS-format backup snapshots.
   4 #
   5 # This decoder aims to decompress an LBS snapshot.  It is not meant to be
   6 # particularly efficient, but should be a small and portable tool for doing so
   7 # (important for recovering from data loss).  It is also meant to serve as a
   8 # check on the snapshot tool and data format itself, and serve as documentation
   9 # for the format.
  10 #
  11 # This decoder does not understand TAR archives; it assumes that all segments
  12 # in the snapshot have already been decompressed, and that objects are
  13 # available simply as files in the filesystem.  This simplifies the design.
  14 #
  15 # Copyright (C) 2007  Michael Vrable
  16
  17 use strict;
  18 use Digest::SHA1;
  19 use File::Basename;
  20
  21 my $OBJECT_DIR = ".";           # Directory where objects are unpacked
  22 my $RECURSION_LIMIT = 3;        # Bound on recursive object references
  23
  24 ############################ CHECKSUM VERIFICATION ############################
  25 # A very simple later for verifying checksums.  Checksums may be used on object
  26 # references directly, and can also be used to verify entire reconstructed
  27 # files.
  28 #
  29 # A checksum to verify is given in the form "algorithm=hexdigest".  Given such
  30 # a string, we can construct a "verifier" object.  Bytes can be incrementally
  31 # added to the verifier, and at the end a test can be made to see if the
  32 # checksum matches.  The caller need not know what algorithm is used.  However,
  33 # at the moment we only support SHA-1 for computing digest (algorith name
  34 # "sha1").
  35 sub verifier_create {
  36     my $checksum = shift;
  37
  38     if ($checksum !~ m/^(\w+)=([0-9a-f]+)$/) {
  39         die "Malformed checksum: $checksum";
  40     }
  41     my ($algorithm, $hash) = ($1, $2);
  42     if ($algorithm ne 'sha1') {
  43         die "Unsupported checksum algorithm: $algorithm";
  44     }
  45
  46     my %verifier = (
  47         ALGORITHM => $algorithm,
  48         HASH => $hash,
  49         DIGESTER => new Digest::SHA1
  50     );
  51
  52     return \%verifier;
  53 }
  54
  55 sub verifier_add_bytes {
  56     my $verifier = shift;
  57     my $digester = $verifier->{DIGESTER};
  58     my $data = shift;
  59
  60     $digester->add($data);
  61 }
  62
  63 sub verifier_check {
  64     my $verifier = shift;
  65     my $digester = $verifier->{DIGESTER};
  66
  67     my $newhash = $digester->hexdigest();
  68     if ($verifier->{HASH} ne $newhash) {
  69         print STDERR "Verification failure: ",
  70             $newhash, " != ", $verifier->{HASH}, "\n";
  71     }
  72     return ($verifier->{HASH} eq $newhash);
  73 }
  74
  75 ################################ OBJECT ACCESS ################################
  76 # The base of the decompressor is the object reference layer.  See ref.h for a
  77 # description of the format for object references.  These functions will parse
  78 # an object reference, locate the object data from the filesystem, perform any
  79 # necessary integrity checks (if a checksum is included), and return the object
  80 # data.
  81 sub load_ref {
  82     # First, try to parse the object reference string into constituent pieces.
  83     # The format is segment/object(checksum)[range].  Both the checksum and
  84     # range are optional.
  85     my $ref_str = shift;
  86
  87     if ($ref_str !~ m/^([-0-9a-f]+)\/([0-9a-f]+)(\(\S+\))?(\[\S+\])?$/) {
  88         die "Malformed object reference: $ref_str";
  89     }
  90
  91     my ($segment, $object, $checksum, $range) = ($1, $2, $3, $4);
  92
  93     # Next, use the segment/object components to locate and read the object
  94     # contents from disk.
  95     open OBJECT, "<", "$OBJECT_DIR/$segment/$object"
  96         or die "Unable to open object $OBJECT_DIR/$segment/$object: $!";
  97     my $contents = join '', <OBJECT>;
  98     close OBJECT;
  99
 100     # If a checksum was specified in the object reference, verify the object
 101     # integrity by computing a checksum of the read data and comparing.
 102     if ($checksum) {
 103         $checksum =~ m/^\((\S+)\)$/;
 104         my $verifier = verifier_create($1);
 105         verifier_add_bytes($verifier, $contents);
 106         if (!verifier_check($verifier)) {
 107             die "Integrity check for object $ref_str failed";
 108         }
 109     }
 110
 111     # If a range was specified, then only a subset of the bytes of the object
 112     # are desired.  Extract just the desired bytes.
 113     if ($range) {
 114         if ($range !~ m/^\[(\d+)\+(\d+)\]$/) {
 115             die "Malformed object range: $range";
 116         }
 117
 118         my $object_size = length $contents;
 119         my ($start, $length) = ($1 + 0, $2 + 0);
 120         if ($start >= $object_size || $start + $length > $object_size) {
 121             die "Object range $range falls outside object bounds "
 122                 . "(actual size $object_size)";
 123         }
 124
 125         $contents = substr $contents, $start, $length;
 126     }
 127
 128     return $contents;
 129 }
 130
 131 ############################### FILE PROCESSING ###############################
 132 # Process the metadata for a single file.  process_file is the main entry
 133 # point; it should be given a list of file metadata key/value pairs.
 134 # iterate_objects is a helper function used to iterate over the set of object
 135 # references that contain the file data for a regular file.
 136
 137 sub uri_decode {
 138     my $str = shift;
 139     $str =~ s/%([0-9a-f]{2})/chr(hex($1))/ge;
 140     return $str;
 141 }
 142
 143 sub iterate_objects {
 144     my $callback = shift;       # Function to be called for each reference
 145     my $arg = shift;            # Argument passed to callback
 146     my $text = shift;           # Whitespace-separate list of object references
 147
 148     # Simple limit to guard against cycles in the object references
 149     my $recursion_level = shift || 0;
 150     if ($recursion_level >= $RECURSION_LIMIT) {
 151         die "Recursion limit reached";
 152     }
 153
 154     # Split the provided text at whitespace boundaries to produce the list of
 155     # object references.  If any of these start with "@", then we have an
 156     # indirect reference, and must look up that object and call iterate_objects
 157     # with the contents.
 158     my $obj;
 159     foreach $obj (split /\s+/, $text) {
 160         next if $obj eq "";
 161         if ($obj =~ /^@(\S+)$/) {
 162             my $indirect = load_ref($1);
 163             iterate_objects($callback, $arg, $1, $recursion_level + 1);
 164         } else {
 165             &$callback($arg, $obj);
 166         }
 167     }
 168 }
 169
 170 sub obj_callback {
 171     my $verifier = shift;
 172     my $obj = shift;
 173     my $data = load_ref($obj);
 174     print "    ", $obj, " (size ", length($data), ")\n";
 175     verifier_add_bytes($verifier, $data);
 176 }
 177
 178 sub process_file {
 179     my %info = @_;
 180
 181     # TODO
 182     print "process_file: ", uri_decode($info{name}), "\n";
 183
 184     if (defined $info{data}) {
 185         my $verifier = verifier_create($info{checksum});
 186
 187         iterate_objects(\&obj_callback, $verifier, $info{data});
 188
 189         print "    checksum: ", (verifier_check($verifier) ? "pass" : "fail"),
 190             " ", $info{checksum}, "\n";
 191     }
 192 }
 193
 194 ########################### METADATA LIST PROCESSING ##########################
 195 # Process the file metadata listing provided, and as information for each file
 196 # is extracted, pass it to process_file.  This will recursively follow indirect
 197 # references to other metadata objects.
 198 sub process_metadata {
 199     my ($metadata, $recursion_level) = @_;
 200
 201     # Check recursion; this will prevent us from infinitely recursing on an
 202     # indirect reference which loops back to itself.
 203     $recursion_level ||= 0;
 204     if ($recursion_level >= $RECURSION_LIMIT) {
 205         die "Recursion limit reached";
 206     }
 207
 208     # Split the metadata into lines, then start processing each line.  There
 209     # are two primary cases:
 210     #   - Lines starting with "@" are indirect references to other metadata
 211     #     objects.  Recursively process that object before continuing.
 212     #   - Other lines should come in groups separated by a blank line; these
 213     #     contain metadata for a single file that should be passed to
 214     #     process_file.
 215     # Note that blocks of metadata about a file cannot span a boundary between
 216     # metadata objects.
 217     my %info = ();
 218     my $line;
 219     foreach $line (split /\n/, $metadata) {
 220         # If we find a blank line or a reference to another block, process any
 221         # data for the previous file first.
 222         if ($line eq '' || $line =~ m/^@/) {
 223             process_file(%info) if %info;
 224             %info = ();
 225             next if $line eq '';
 226         }
 227
 228         # Recursively handle indirect metadata blocks.
 229         if ($line =~ m/^@(\S+)$/) {
 230             print "Indirect: $1\n";
 231             my $indirect = load_ref($1);
 232             process_metadata($indirect, $recursion_level + 1);
 233             next;
 234         }
 235
 236         # Try to parse the data as "key: value" pairs of file metadata.
 237         if ($line =~ m/^(\w+):\s+(.*)\s*$/) {
 238             $info{$1} = $2;
 239         } else {
 240             print STDERR "Junk in file metadata section: $line\n";
 241         }
 242     }
 243
 244     # Process any last file metadata which has not already been processed.
 245     process_file(%info) if %info;
 246 }
 247
 248 ############################### MAIN ENTRY POINT ##############################
 249 # Program start.  We expect to be called with a single argument, which is the
 250 # name of the backup descriptor file written by a backup pass.  This will name
 251 # the root object in the snapshot, from which we can reach all other data we
 252 # need.
 253
 254 my $descriptor = $ARGV[0];
 255 unless (defined($descriptor) && -r $descriptor) {
 256     print STDERR "Usage: $0 <snapshot file>\n";
 257     exit 1;
 258 }
 259
 260 $OBJECT_DIR = dirname($descriptor);
 261 print "Source directory: $OBJECT_DIR\n";
 262
 263 open DESCRIPTOR, "<", $descriptor
 264     or die "Cannot open backup descriptor file $descriptor: $!";
 265 my $line = <DESCRIPTOR>;
 266 if ($line !~ m/^root: (\S+)$/) {
 267     die "Expected 'root:' specification in backup descriptor file";
 268 }
 269 my $root = $1;
 270 close DESCRIPTOR;
 271
 272 print "Root object: $root\n";
 273
 274 my $contents = load_ref($root);
 275 process_metadata($contents);