#!/usr/bin/perl
#============================================================= -*-perl-*-
#
# BackupPC_copyPcPool.pl: Reliably & efficiently copy pool and pc tree
#
# DESCRIPTION
#   See below for detailed description of what it does and how it works
#   
# AUTHOR
#   Jeff Kosowsky
#
# COPYRIGHT
#   Copyright (C) 2011  Jeff Kosowsky
#
#   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 of the License, 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#
#========================================================================
#
# Version 0.1.3, released September 2011
#
#========================================================================
#
# DESCRIPTION

# 1. The program first creates a new inode-labeled pool (called by
# default 'ipool') which is a decimal tree of depth $ilevels, indexed
# by the last $ilevels significant digits of the inode of the
# corresponding pool/cpool file.  Each file in the Ipool tree
# consists of two lines. The first line is just the pool file name
# (i.e the partial file md5sum plus a potential '_N' suffix). The
# second line consists of an (optional) full file mdsum checksum,
# which is zero if we don't want to use mdsums. Optionally, the
# program will remove any orphan pool file entries (i.e. those with
# only 1 hard link) and renumber the chain accordingly (this is the same
# functionality as provided by BackupPC_nightly

# Note: the indexing is done by the least significant inode digits in
# order to ensure a more uniformly balanced tree.
# Note: the full file mdsum functionality has not yet been
# implemented.

# 2. The program then runs through the pc tree (or a designated
# subtree thereof) to create a single long list of all of the
# directories, hard links, and zero-lengthfiles
# For hard links, the entry is:
#  <path-to-pool-file> <path-to-pc-file>
# For directories, the entry is:
#    D <owner> <group> <mode> <mtime> <path-to-directory>
# For zero-length files, the entry is:
#    Z <owner> <group> <mode> <mtime> <path-to-file>
# For 'errors' (e.g., non-linked, non-zero length files), the
# entry is:
#    X <owner> <group> <mode> <mtime> <path-to-file>
# Comments can be indicated by:
#   #

# Note: all paths are relative to TopDir

# The partial file md5sum is obtained by looking up the inode of the
# pc tree file in the Ipool. Files with multiple links are optionally
# cached in memory which saves IO look-ups at the expense of
# memory. (Note the caching algorithm tries to preferentially cache
# files with the most links)

# Any (non-zero length) pc files that are not linked (i.e. only one
# hard link) or that are not linked to an Ipool file may optionally be
# corrected and linked to the pool and if this results in a new pool
# entry then that entry is added to the Ipool too. Files that are not
# corrected are listed for separate examination and manual correction
# or backup.

# The output consists of 3 files:

# <outfile>.links   is the file consisting of the list of links,
#                   directories and zero-length files described above

# <outfile>.nopool  is a listing of the normal top-level log and info
#                   files that are not linked and need to be copied
#                   over directly

# <outfile>.nolinks is a listing of the non-linked, non-zero length
#                   files that either couldn't be linked or that you
#                   decided not to link

# NOTE: Backuppc on the source machine should be disabled (or a
# snapshot used) during the entire backup process

# 3. Restoring then consists of the following steps:

#    A. Copy over the pool/cpool any way you like, including
#       rsync but without having to worry about hard links

#    B. Copy over the non-pooled files (<outfile>.nopool) any way you want,
#       e.g., rsync, tar, etc.

#    C. Run this program again using the -r|--restore flag and the
#       <outfile>.nolinks as the input

#    D. Optionally copy over the non-linked files in <outfile>.nolinks


# NOTE: Backuppc on the target machine should be disabled (or a
# snapshot used) during the entire restore process

# Selected features:
#   --gzip|-g      flag creates compressed output/input
#   --stdio        writes/reads to stdio allowing you to pipe the backup
#                  stage directly into the restore stage
#   --fixlinks|-f  fixes any missing/broken pc links
#   --topdir|-t    allows setting of alternative topdir
#   --dryrun|-d    doesn't make any changes to pool or pc tree
#   --verbose|-v   verbosity (repeat for higher verbosity)
#   --icache|-i    size of optional memory cache of ipool tree
#
#========================================================================

use strict;
use warnings;
use File::Path;
use Getopt::Long qw(:config no_ignore_case bundling);
use Fcntl;  #Required for RW I/O masks
use Switch;

use lib "/usr/share/BackupPC/lib";
use BackupPC::FileZIO;
use BackupPC::Lib;
use BackupPC::jLib 0.4.0;  # Requires version >= 0.4.0
use BackupPC::Attrib qw(:all);

no  utf8;

#use Data::Dumper; #JJK-DEBUG

select(STDERR); #Auto-flush (i.e., unbuffer) STDERR
$| = 1;
select(STDOUT);

#Variables
my $bpc = BackupPC::Lib->new or die "BackupPC::Lib->new failed\n";	
my $md5 = Digest::MD5->new;
my $attr; #Re-bless for each backup since may have different compress level
my $MaxLinks = $bpc->{Conf}{HardLinkMax};
my $CREATMASK = O_WRONLY|O_CREAT|O_TRUNC;
my %IpoolCache=(); #Cache for retrieved Ipool entries
my @nonpooled = ();
my @backups = ();
my @compresslvls=(); #Pool to use for each backup;

my $directories = 0;
my $totfiles = 0; #Total of next 6 variables
my $zerolengthfiles = 0;
my $existinglink_pcfiles = 0;
my $fixedlink_pcfiles = 0;
my $unlinkable_pcfiles = 0;
my $unlinked_pcfiles = 0;
my $unlinked_nonpcfiles = 0;
my $unlinked_files = 0; #Total of above three
my $missing_attribs = 0;

#GetOptions defaults:
my $IcacheSize = my $IcacheSize_def = 10000;
my $cleanpool;
my $create=0; #Default is not to create if non-empty
#$dryrun=1;  #Global variable defined in jLib.pm (do not use 'my') #JJK-DEBUG
my $fixlinks=0;
my $Force;
my $FORCE;
my $gzip;
my $ilevels = my $ilevels_def = 4; #Number of levels in the Ipool tree
my $mdsumflg;
my $outfile;
my $Overwrite;
my $paranoid;
my $pool = my $pool_def = 'both';
my $restore;
my $skippc;
my $stdio;
my $TopDir = my	$TopDir_def = $bpc->{TopDir};
my $IpoolDir = my $IpoolDir_def = "ipool";
my $verbose = my $verbose_def = 2;
my $noverbose;

usage() unless( 
	GetOptions( 
		"cleanpool|c"   => \$cleanpool, #Remove orphan pool entries
		"dryrun|d!"     => \$dryrun,    #1=dry run
		"create|C!"     => \$create,    #Create new Ipool
		"fixlinks|f"    => \$fixlinks,  #Fix unlinked/broken pc files
		"Force|F"       => \$Force,     #Override stuff...
		"FORCE"         => \$FORCE,     #OVERWRITES during restore (dangerous)
		"icache|I=i"    => \$IcacheSize,#Size of Ipool Cache
		"ipool|i=s"     => \$IpoolDir,  #Inode Pool location relative to TopDir
		"gzip|g"        => \$gzip,      #Compress files
		"levels|l=i"    => \$ilevels,   #Number of levels in Inode tree
		"mdsum|m"       => \$mdsumflg,  #Include mdsum;
		"outfile|o=s"   => \$outfile,   #Output file (required)
		"Overwrite|O"   => \$Overwrite, #Overwrite existing files/dirs (restore)
		"pool|p=s"      => \$pool,      #Pool (pool|cpool|both)
		"paranoid|P"    => \$paranoid,  #Paranoid error checking
		"restore|r"     => \$restore,     #Restore rather than backup
		"skippc|S"      => \$skippc,    #Only create & populate Ipool
		"stdio"         => \$stdio,     #Print/read to/from stdout/stdin
		"topdir|t=s"    => \$TopDir,    #Location of TopDir
		"verbose|v+"    => \$verbose,   #Verbosity (repeats allowed)
		"noverbose"     => \$noverbose, #Shut off all verbosity
		"help|h"        => \&usage,
	) &&
	($create || !$cleanpool)
	);

if($restore) {
	usage() if $mdsumflg || $outfile || 
		(!$stdio && @ARGV != 1) || ($stdio && @ARGV != 0);
}else {
	usage() if ! defined($outfile) || $restore ||
		($pool !~ /^(pool|cpool|both)/);
}

$verbose = 0 if $noverbose;

############################################################################
if($TopDir ne $TopDir_def) {
	#NOTE: if we are not using the TopDir in the config file, then we
	# need to manually override the settings of BackupPC::Lib->new
	# which *doesn't* allow you to set TopDir (even though it seems so
	# from the function definition, it gets overwritten later when the
	# config file is read)
	$TopDir =~ s|//*|/|g; #Remove any lurking double slashes
	$TopDir =~ s|/*$||g; #Remove trailing slash
	$bpc->{TopDir} = $TopDir;
	$bpc->{Conf}{TopDir} = $TopDir;

	$bpc->{storage}->setPaths({TopDir => $TopDir});
	$bpc->{PoolDir}  = "$bpc->{TopDir}/pool";
	$bpc->{CPoolDir} = "$bpc->{TopDir}/cpool";
}

%Conf   = $bpc->Conf(); #Global variable defined in jLib.pm (do not use 'my')
#############################################################################
#By convention for the rest of this program, we will assume that all
#directory variables have a trailing "/". This should save us some
#efficiency in terms of not having to always add back the slash.
$TopDir .= "/"; $TopDir =~ s|//*|/|g;
my $pcdir = 'pc/';

die "TopDir = '$TopDir' doesn't exist!\n" unless -d $TopDir;
die "TopDir = '$TopDir' doesn't look like a valid TopDir!\n" 
	unless -d "$TopDir/pool" && -d "$TopDir/cpool" && -d "$TopDir/${pcdir}";

system("$bpc->{InstallDir}/bin/BackupPC_serverMesg status jobs >/dev/null 2>&1");
unless(($? >>8) == 1) {
	die "Dangerous to run when BackupPC is running!!! (use '--Force' to override)\n"
		if !$Force && $TopDir eq $TopDir_def;
	warn "WARNING: May be dangerous to run when BackupPC is running!!!\n"; 
    #Warn but don't die if *appear* to be in different TopDir
}

############################################################################
if(defined $restore) {
	do_restore($ARGV[0]);
	exit; #DONE
}
############################################################################
my $sfx = $gzip ? ".gz" : "";
my $linksfile = "${outfile}.links${sfx}";
my $nopoolfile = "${outfile}.nopool${sfx}";
my $nolinksfile = "${outfile}.nolinks${sfx}";
unless($skippc) {
	die "ERROR: '$linksfile' already exists!\n" if !$stdio && -e $linksfile;
	die "ERROR: '$nopoolfile' already exists!\n" if -e $nopoolfile;
	die "ERROR: '$nolinksfile' already exists!\n" if -e $nolinksfile;
	
	my $outpipe = $gzip ? "| gzip > " : "> ";
	if($stdio) {
		open(LINKS, $gzip ? "| gzip -f" : ">&STDOUT"); #Redirect LINKS to STDOUT
	}else {
		open(LINKS,  $outpipe . $linksfile)
			or die "ERROR: Can't open '$linksfile' for writing!($!)\n";
	}
	
	open(NOPOOL, $outpipe . $nopoolfile)
			or die "ERROR: Can't open '$nopoolfile' for writing!($!)\n";
	open(NOLINKS, $outpipe . $nolinksfile)
			or die "ERROR: Can't open '$nolinksfile' for writing!($!)\n";
}

############################################################################
chdir($TopDir); #Do this so we don't need to worry about distinguishing
                #between absolute and relative (to TopDir) pathnames
                #Everything following opening the files occurs in TopDir
############################################################################
initialize_backups() unless($skippc);

$IpoolDir .= '/';
$IpoolDir  =~ s|//*|/|g;
if($create || ! -d $IpoolDir) { #Need to create Ipool...
	warn "**Creating new Ipool (${TopDir}$IpoolDir)...\n" if $verbose>=1;
	warn "* Removing old Ipool tree...\n" if $verbose >=2;
	rmtree($IpoolDir) if -d $IpoolDir; #Remove existing Ipool;
	print STDERR "* Creating Ipool directories:[0-9] " if $verbose >=2;
	create_ipool($ilevels, $IpoolDir);
	my $totipool=0;
	if($pool eq "both") {
		$totipool += populate_ipool("pool");
		$totipool += populate_ipool("cpool");
	}
	else {
		$totipool += populate_ipool($pool);
	}
	warn "*Ipool entries created=$totipool\n" if $verbose >=2;
}else { #Use existing pool
	die "ERROR: Inode tree levels ($ilevels) does not match number of levels in existing tree ($IpoolDir) -- either remove tree or select --create to override...\n"
		if ! -d $IpoolDir . ("9/" x $ilevels) || 
		-d $IpoolDir . ("9/" x ($ilevels+1));
	warn "**Using existing Ipool tree (${TopDir}$IpoolDir) [--create overrides]...\n" if $verbose>=1;
}
exit if $skippc;

warn "**Recording nonpooled top level files...\n" if $verbose>=1;
foreach (@nonpooled) {  #Print out the nonpooled files
	printf NOPOOL "%s\n", $_;
}
close(NOPOOL);

warn "**Recording linked & non-linked pc files...\n" if $verbose>=1;
my $lastmachine = '';
my ($compresslvl);
foreach (@backups) {
	m|$pcdir([^/]*)|;
	if($1 ne $lastmachine) {
		$lastmachine = $1;
		Clear_Icache();
	}
	warn "* Recursing through backup: $_\n" if $verbose>=1;
	$compresslvl = shift(@compresslvls);
	$attr = BackupPC::Attrib->new({ compress => $compresslvl });
    #Reinitialize this jLib global variable in case new compress level
	m|(.*/)(.*)|;
	find_cpool_links($1, $2);
}
close(LINKS);
close(NOLINKS);

##############################################################################
#Print summary & concluding message:
printf STDERR "\nDirectories=%d\tTotal Files=%d\n",
	$directories, ($totfiles + $#nonpooled);
printf STDERR "Link files=%d\t [Zero-length=%d,  Hardlinks=%d (Fixed=%d)]\n",
	($zerolengthfiles+$existinglink_pcfiles+$fixedlink_pcfiles),
	$zerolengthfiles, ($existinglink_pcfiles+$fixedlink_pcfiles),
	$fixedlink_pcfiles;
printf STDERR "Non-pooled Toplevel=%d\n", $#nonpooled;
printf STDERR "Non-pooled Other=%d [Valid-pc=%d (Failed-fixes=%d),  Invalid-pc=%d]\n",
	$unlinked_files, ($unlinked_pcfiles+$unlinkable_pcfiles),
	$unlinkable_pcfiles, $unlinked_nonpcfiles;
printf STDERR "PC files missing attrib entry=%d\n", $missing_attribs;

my ($rsyncnopool, $rsyncnolinks);
if($gzip) {
	$gzip="-g ";
	$rsyncnopool = "zcat $nopoolfile | rsync -aOH --files-from=- $TopDir <newTopDir>";
	$rsyncnolinks = "zcat $nolinksfile | rsync -aOH --files-from=- $TopDir <newTopDir>";
} else {
	$rsyncnopool = "rsync -aOH --files-from=$nopoolfile $TopDir <newTopDir>";
	$rsyncnolinks = "rsync -aOH --files-from=$nolinksfile $TopDir <newTopDir>";
}

print STDERR <<EOF;
------------------------------------------------------------------------------
To complete copy, do the following as user 'root' or 'backuppc':
  1. Copy/rsync over the pool & cpool directories to the new TopDir
     (note this must be done *before* restoring '$linksfile')
     For rsync:
        rsync -aO $TopDir\{pool,cpool\} <newTopDir>

  2. Copy/rsync over the non-pooled top level files ($nopoolfile)
     For rsync:
        $rsyncnopool

  3. Restore the pc directory tree, hard links and zero-sized files:
        $0 -r ${gzip}[-t <newTopDir>] $linksfile

  4. Optionally, copy/rsync over the non-linked pc files ($nolinksfile)
     For rsync:
        $rsyncnolinks

------------------------------------------------------------------------------

EOF
exit;

##############################################################################
##############################################################################
#SUBROUTINES:

sub usage
{
    print STDERR <<EOF;

usage: $0 [options] -o <outfile> [<relpath-to-pcdir> <relpath-to-pcdir> ...]
       $0 [options] -r <restorefile>

  where the optional <relpath-to-pcdir> arguments are paths relative to the pc
  tree of form: 'host' or 'host/share' or 'host/share/n' or 'host/share/n/.../'
  If no optional <relpath-to-pcdir> arguments are given then the entire pc tree
  is backed up.
  
  Options: [Common to copy & restore]
   --dryrun|-d            Dry-run - doesn\'t change pool or pc trees
                          Negate with: --nodryrun
   --Force|-F             Overrides various checks (e.g., if BackupPC running
                          or if directories present)
   --FORCE                OVERWRITES during restore (DANGEROUS)
   --gzip|-g              Pipe files to/from gzip compression
   --paranoid|P           Perform extra error checking that should not be 
                          necessary assuming pool, ipool, and pc trees have
                          not changed in the interim
   --topdir|-t            Location of TopDir.
                          [Default = $TopDir_def]
                          Note you may want to change from default for example
                          if you are working on a shadow copy.
   --verbose|-v           Verbose (repeat for more verbosity)
                          [Default level = $verbose_def]
                          Use --noverbose to turn off all verbosity
   --help|-h              This help message

  Options: [Copy only]
   --cleanpool|c          If orphaned files (nlinks=1) found when populating
                          Ipool, remove them (and renumber chain as needed). 
                          NOTE: This shouldn\'t happen if you have just run
                          BackupPC_nightly
   --create|-C            Override creation of new Ipool even if already present
                          Negate with: --nocreate
   --fixlinks|-f          Attempt to link valid pc files back to the pool
                          if not already hard-linked
                          NOTE: this changes files in the pc and\/or pool
                          of your source too!
   --icache|I N           Size of Ipool *memory* cache (0 = off)
                          [Default = $IcacheSize_def]
   --ipool|i [location]   Location relative to TopDir of Ipool tree
                          [Default = $IpoolDir_def]
   --levels|l N           Number of levels in the Ipool tree
                          [Default = $ilevels_def]
   --mdsum|m              Include mdsums [NOT IMPLEMENTED]
   --outfile|-o [outfile] Required stem name for the 3 output files
                             <outfile>.nopools
                             <outfile>.links
                             <outfile>.nolinks
   --pool|-p  [pool|cpool|both]  Pools to include in Ipool tree
   --skippc|-S            Skip recursing pc directory (implies create pool)
   --stdio                Print the directory tree, links and zero-sized files
                          to stdout so it can be piped directly to another copy
                          of the program running --restore
                          NOTE: Status, Warnings, and Errors are printed to 
                          stdout.

  Options: [Restore only]
   --Overwrite|-O         Overwrite existing files & directories
   --stdio                Read the directory tree, links and zero-sized files
                          from stdin so it can be piped directly from another
                          copy of the program running in the create mode
                          For example, the following pipe works:
                          $0 -t <source TopDir> [-g] --stdio | $0 -t <dest TopDir> [-g] -r --stdio

OVERVIEW:
  First, if Ipool tree doesn\'t exist (or if --create option selected), 
  create a new Inode tree (default: ${TopDir_def}$IpoolDir_def).

  Then, recurse through the pool and\/or cpool directories (default: $pool_def)
  and create a new Ipool tree inode corresponding to each pool entry. The Ipool
  tree entry is indexed by the last digits of the Inode and contains the path
  relative to TopDir of the pool entry (plus an optional md5sum line --
  not yet implemented).

  Then, recurse through the paths specified relative to the pc tree or if no
  paths specified then the entire pc tree. 
  - If the file is a (non-pooled) top-level log file, then write its path
    relative to pcdir out to <outfile>.nopool
    Note this includes all non-directories above the share level plus the
    backInfo files that are covered by the input paths
  - If the file is a directory, zero length file, or an existing hard link to
    the tree, then write it out to <outfile>.links
  - If the file is not hard-linked but is a valid non-zero length pc file 
    (f-mangled and present in the attrib file) and --fixlinks is selected,
    then try to link it properly to the appropriate pool.
  - Otherwise, add it to <outfile>.nolinks

  The entries in the IpoolDir can also optionally be cached in a hash, using
  the --icache <cache size> option but the speedup is relatively minimal since
  you are just saving a one block file read

  NOTE: TO ENSURE INTEGRITY OF RESULTS IT IS IMPORTANT THAT BACKUPPC IS NOT
  RUNNING (use --Force to override)

  Note: you should run BackupPC_nightly before running this program so that
  no unnecessary links are backed up; alternatively, set the --cleanpool
  option which will remove orphan pool entries.

EOF
exit(1);
}

#Glob to determine what is being backed up. 
#Make sure each backup seems valid and determine it's compress level
#Collect top-level non-pooled files
sub initialize_backups
{
	if (!@ARGV) { # All backups at backup number level
		# TopDir/pc/<host>/<nn>
		@backups = glob("${pcdir}*/*"); #2 levels down;
		@nonpooled = grep(! -d , glob("${pcdir}*")); #All non-directories
	} else { # Subset of backups
		foreach(@ARGV) {
			my $backupdir = $pcdir . $_ . '/';
			$backupdir  =~ s|//*|/|g; #Remove redundant slashes
			$backupdir =~ s|/\.(?=/)||g; #Replace /./ with /
			die "ERROR: '$backupdir' is not a valid pc tree subdirectory\n" if $pcdir eq $backupdir || !-d $backupdir;
			if($backupdir =~ m|^\Q${pcdir}\E[^/]+/$|) {  #Hostname only
				push(@backups, glob("${backupdir}*"));
			} else { # At share level or below #Backup number or below
				push(@backups, ${backupdir});
			}
		}
		@backups = keys %{{map {$_ => 1} @backups}}; #Eliminate dups
		@nonpooled = keys %{{map {$_ => 1} @nonpooled}}; #Eliminate dups
	}

	push(@nonpooled, grep(! -d, @backups)); #Non-directories
	@backups = grep(-d , @backups); #Directories
	push(@nonpooled, grep(m|/backupInfo$|, @backups)); # backupInfo not pooled
    #Note everything else *should* be pooled - if not, we will catch it later as an error
	@backups = grep(!m|/backupInfo$|, @backups);

	foreach(@backups) {
		s|/*$||; #Remove trailing slash
		m|^(\Q${pcdir}\E[^/]+/[^/]+)(/)?|;
		die "Backup '$1' does not contain a 'backupInfo' file\n"
			unless -f "$1/backupInfo";
		push(@nonpooled, "$1/backupInfo") unless $2; #Don't include if share level or below
		my $compress = get_bakinfo("$1","compress");
		push(@compresslvls, $compress);
		my $thepool = $compress > 0 ? 'cpool' : 'pool';
		die "Backup '$1' links to non-included '$thepool'\n"
			if $pool ne 'both' && $pool ne $thepool;
	}
}

#Recursively create directory tree for Ipool - $levels deep starting from
#$newdir. Note: $newdir should have a trailing slash
sub create_ipool
{
	my ($level, $newdir) = @_;
#	print STDERR "$level: $newdir\n"; #JJK-DEBUG
	unless(-d $newdir) {
		mkdir $newdir or die "Can't create directory: $newdir\n";
	}
	if($level--) {
		for(my $i=0; $i <= 9; $i++) {
			print STDERR "$i " if $level==$ilevels-1 && $verbose >=2;
			create_ipool($level, $newdir . $i . "/"); #Recurse
		}
	}
}

#Iterate through the 'pooldir' tree and populate the Ipool tree
sub populate_ipool
{
	my ($fpool) = @_;
	my (@fstat, $dh, @dirlist, $pfile);
	my $ipoolfiles = 0;

	return unless glob("$fpool/[0-9a-f]"); #No entries in pool
	my @hexlist = ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f');
	my ($idir,$jdir,$kdir);
	print STDERR "\n* Populating Ipool with '$fpool' branch:[0-f] " if $verbose >=2;
	foreach my $i (@hexlist) {
	print STDERR "$i " if $verbose >=2;
		$idir = $fpool . "/" . $i . "/";
		foreach my $j (@hexlist) {
			$jdir = $idir . $j . "/";
			foreach my $k (@hexlist) {
				$kdir = $jdir . $k . "/";
				unless(opendir($dh, $kdir)) {
					warn "Can't open pool directory: $kdir\n" if $verbose>=4;
					next;
				}
				my @entries = grep(!/^\.\.?$/, readdir ($dh)); #Remove dot files
				closedir($dh);
				warn "POOLDIR: $kdir (" . ($#entries+1) ." files)\n"
					if $verbose >=3;
				if($cleanpool) { #Remove orphans & renumber first and then
					#create the Ipool after orphan deletion & chain renumbering
					my @poolorphans = 
						grep(-f $kdir . $_ && (stat(_))[3] < 2, @entries);
					foreach (sort {poolname2number($b) cmp poolname2number($a)} 
							 @poolorphans) { #Reverse sort to minimize moves
						$pfile = $kdir . $_;
						my $res =delete_pool_file($pfile);
						if($verbose >=1) {
							$res == 1 ?
								warn "WARN: Deleted orphan pool entry: $pfile\n": 
								warn "ERROR: Couldn't properly delete orphan pool entry: $pfile\n"
						}
					}
				}
				foreach (@entries) {
					# Go through all entries in terminal cpool branch
					$pfile = $kdir . $_;
					next unless -f $pfile;
					@fstat = stat(_);
					#Note: 0=dev, 1=ino, 2=mode, 3=nlink, 4=uid, 5=gid, 6=rdev
					#7=size, 8=atime, 9=mtime, 10=ctime, 11=blksize, 12=blocks
					if($fstat[3] < 2) { #Orphan pool entry
						warn "WARN: Orphan pool entry: $pfile\n" 
							if $verbose>=1;
					} else { #No sense in creating ipool entries for orphans
						create_ipool_file($fstat[1], $pfile);
						$ipoolfiles++;
					}
				}
			} # kdir
		} # jdir
	} # idir
	print STDERR "\n" if $verbose >=2;
	return $ipoolfiles;
}

sub create_ipool_file
{
	my ($inode, $poolname) = @_;
	my ($fh, $ifile);
	
	my $mdsum = 0;
	$mdsum = get_mdsum($poolname) if $mdsumflg;
	$ifile = InodePath($inode);
#    print STDERR "IFILE: $ifile\n"; #JJK-DEBUG
	if(sysopen($fh, $ifile, $CREATMASK)) {
		syswrite($fh, "$poolname\n$mdsum\n");
		close($fh);
	}
	else {
		warn "ERROR: Can't write to inode pool file: $ifile\n";
	}
}

#Return the Ipool location of inode
#Note: each inode is stored based on the $ilevels least significant digits
#so that the tree should be relatively balanced
#Note this is analogous to MD52Path
sub InodePath
{
	my ($inode, $ipooldir) = @_;

	my $ipath= $inode;
	for(my $i=0; $i < $ilevels; $i++) {
		$ipath = ($inode%10) . '/' . $ipath;
		$inode /=10;
	}
	return((defined $ipooldir ? $ipooldir : $IpoolDir) . $ipath);

}

#Recursively go through pc tree
sub find_cpool_links
{
	my ($dir, $filename) = @_;

	my ($fh, $dh);
	my $file = $dir . $filename;
	if(-d $file) {
		my @fstat = stat(_); #Note last stat was -d $file
		#Print info to signal & re-create directory:
		#D <user> <group> <mod> <atime> <mtime> <file name>
		print_file_reference("D", $file, \@fstat);
		$directories++;
		opendir($dh,$file);
		my @contents = readdir($dh);
		foreach (@contents) {
			next if /^\.\.?$/;     # skip dot files (. and ..)
			find_cpool_links($file . '/', $_); #Recurse
		}
	}
	else { #Not a directory
		my @fstat = stat(_);
		$totfiles++;
		if($fstat[7] == 0) { #Zero size file
			print_file_reference("Z", $file, \@fstat);
			$zerolengthfiles++;
			return;
		}elsif($fstat[3] > 1) { #More than one link
			my ($pooltarget, $ifile);
			if($IcacheSize && ($pooltarget = $IpoolCache{$fstat[1]})) {
#				print STDERR "Cache hit: $fstat[1]\n"; #JJK-DEBUG
			}elsif(open($fh, '<', ($ifile = InodePath($fstat[1])) )) {
				if ($pooltarget = <$fh>) {
					chomp($pooltarget);
					close($fh);
				} else { #Shouldn't happen...
					warn "ERROR: Ipool file '$ifile' has no data\n";
					$pooltarget = undef;
				}
			}
			if($pooltarget) {  #Hard link found in Cache or Ipool
			   if($paranoid &&
				  ($pooltarget !~  #Not a standard pool name
				   m|^(c?pool/[0-9a-f]/[0-9a-f]/[0-9a-f]/[0-9a-f]{32}(_[0-9]+)?)$|
				   ||  ! -f $pooltarget  #Target pool file doesn't exist
				   || $fstat[1] != (stat(_))[1])) { #Inodes don't match
				   delete $IpoolCache{$fstat[1]};
				   warn "ERROR: Ipool file '$ifile' for file '$file' has bad entry: $pooltarget\n";
			   }else { #Valid hit
				   $existinglink_pcfiles++;

				   Add_Icache ($pooltarget, $fstat[1], $fstat[3])
					   if $IcacheSize;
				   print_hardlink_reference($pooltarget, $file);
				   return;
			   }
			}
		}

		if($file =~ m|^\Q${pcdir}\E[^/]+/[^/]+/backupInfo$|) {
			$totfiles--;
			return;		#BackupInfo already taken care of in 'nonpooled'
		}

		#Non-zero sized file not in Ipool/Icache that is not 'backupInfo'
		if($filename =~ /^f|^attrib$/ && -f $file) {
			#VALID pc file if f-mangled or attrib file
			if( $filename =~ /^f/ && 
				!( -f "$dir/attrib" &&
				   $attr->read($dir,"attrib") == 1 &&
				   defined($attr->get($bpc->fileNameUnmangle($filename))))) {
				#Attrib file error if attrib file missing or
				#unmangled name not an element of the attrib file
				warn "ERROR: $file (inode=$fstat[1], nlinks=$fstat[3]) VALID pc file with MISSING attrib entry\n";
				$missing_attribs++;
			}
			if($fixlinks) {
				if(fix_link($file, \@fstat) == 1) {
					$fixedlink_pcfiles++;
					return;
				}else {$unlinkable_pcfiles++;}
			}else{
				warn "ERROR: $file (inode=$fstat[1], nlinks=$fstat[3]) VALID pc file NOT LINKED to pool\n";
				$unlinked_pcfiles++;
			}
		}else {
			warn "ERROR: $file (inode=$fstat[1], nlinks=$fstat[3]) INVALID pc file and UNLINKED to pool\n";
			$unlinked_nonpcfiles++
		}
		#ERROR: Not linked/linkable to pool (and not zero length file or directory
		print_file_reference("X", $file, \@fstat);
		printf NOLINKS "%s\n", $file;
		$unlinked_files++
	}
}

#Try to fix link by finding/creating new pool-link
sub fix_link
{
	my ($filename, $fstatptr) = @_;

	my $poollink = undef;
	my ($md5sum, $result) = zFile2MD5($bpc, $md5, $filename, 0, $compresslvl);
	$result = jMakeFileLink($bpc, $filename, $md5sum, 2, $compresslvl, \$poollink)
		if $result > 0;
	#Note we choose NewFile=2 since if we are fixing, we always want to make the link
	if($result > 0) { #(true if both above calls succeed)
		my $pool = ($compresslvl > 0 ? "cpool" : "pool");
		$poollink =~ m|.*(${pool}.*)|;
		$poollink = $1; #Relative to TopDir
		print_hardlink_reference($poollink, $filename);
		create_ipool_file((stat($poollink))[1], $poollink); #Update Ipool
		if($verbose >=2) {
			warn "NOTICE: pool entry '$poollink' (inode=$fstatptr->[1]) missing from Ipool and added back\n" if $result == 3;
			warn sprintf("NOTICE: '%s' (inode=%d, nlinks=%d) was fixed by linking to *%s* pool entry: %s (inode=%d, nlinks=%d)\n", 
						 $filename, $fstatptr->[1], $fstatptr->[3],
						 ($result == 1 ? "existing" : "new"), 
						 $poollink, (stat(_))[1], (stat(_))[3])
				if $result !=3;
		}
		return 1;
	}
	warn "ERROR: '$filename' (inode $fstatptr->[1]); fstatptr->[3] links; md5sum=$md5sum) VALID pc file FAILED FIXING by linking to pool\n";
	return 0;
}

sub print_hardlink_reference
{
	my ($poolname, $filename) = @_;
	
	printf LINKS "%s %s\n", $poolname, $filename; #Print hard link
}

sub print_file_reference
{
	my ($firstcol, $filename, $fstatptr) = @_;

	#<firstcol>  <user> <group> <mod> <mtime> <filename>
	printf(LINKS "%s %s %s %04o %u %s\n",
		   $firstcol, UID($fstatptr->[4]), GID($fstatptr->[5]), 
		   $fstatptr->[2] & 07777, $fstatptr->[9], $filename);
}


sub get_mdsum
{
}

###############################################################################
my ($avglinks, $totentries, $totlinks, $cachesize);
sub Add_Icache
{
	my ($target, $inode, $nlinks) = @_;
	my $fraction = 1/2;

#	printf STDERR "(size=%d|%d)\n", $cachesize, $size2; #JJK-DEBUG
	return if defined $IpoolCache{$inode} || #Already stored
		$nlinks <= 2 || #Only add new keys if nlinks >2 links 
		$nlinks < $fraction * $avglinks; #And if > fraction * average

	if($cachesize >= $IcacheSize) { #Delete "random" key if full
		my $key = each %IpoolCache || each %IpoolCache;
		#Note repetition needed to swallow the 'undef' token and allow 'each to circle around again (also in scalar context note each returns just the key)
		delete($IpoolCache{$key});
		$cachesize--;
#		printf STDERR "Deleting cache link (size=%d, avg=%d)\n", $cachesize, $avglinks; #JJK-DEBUG
	}
	$IpoolCache{$inode} = $target;
	$totentries++;
	$totlinks += $nlinks;
	$cachesize++;
	$avglinks = $totlinks/$totentries;
#	printf STDERR "Adding cache link (inode=$inode nlinks=%d) [size=%d, avg=%.1f]\n", $nlinks, $cachesize, $avglinks; #JJK-DEBUG
}

sub Clear_Icache
{
	%IpoolCache = ();
	$totentries = 0;
	$totlinks = 0;
	$cachesize = 0;
	$avglinks = 3;
}
		
my (%UIDcache, %GIDcache);
# Return user name corresponding to numerical UID with caching
sub UID
{
    $UIDcache{$_[0]} = getpwuid($_[0]) unless exists($UIDcache{$_[0]});
    return $UIDcache{$_[0]};
}

# Return group name corresponding to numerical GID with caching
sub GID
{
    $GIDcache{$_[0]} = getgrgid($_[0]) unless exists($GIDcache{$_[0]});
    return $GIDcache{$_[0]};
}

my (%USERcache, %GROUPcache);
# Return numerical UID corresponding to user name with caching
sub USER
{
    $USERcache{$_[0]} = getpwnam($_[0]) unless exists($USERcache{$_[0]});
    return $USERcache{$_[0]};
}

# Return numerical GUID coresponding to group name with caching
sub GROUP
{
    $GROUPcache{$_[0]} = getgrnam($_[0]) unless exists($GROUPcache{$_[0]});
    return $GROUPcache{$_[0]};
}
################################################################################
################################################################################
sub do_restore
{
	my ($restorefile) = @_;

	my $currbackup = "";

	my $formaterr = 0;
	my $ownererr = 0;
	my $permserr = 0;
	my $mkdirerr = 0;
	my $mkzeroerr = 0;
	my $mklinkerr = 0;
	my $filexsterr = 0;
	my $utimerr = 0;
	my $newdir = 0;
	my $newzero = 0;
	my $newlink = 0;
	my $skipped = 0;

################################################################################
	if($stdio) {
		open(LINKS, $gzip ? "/bin/zcat - |" : "<& STDIN");
	}else {
		open(LINKS, $gzip ? "/bin/zcat $restorefile |" : "< $restorefile") or
			die "ERROR: Can't open '$restorefile' for reading!($!)\n";
	}

	chdir($TopDir); #Do this so we don't need to worry about distinguishing
                    #between absolute and relative (to TopDir) pathnames
	die "ERROR: pc directory contains existing backups!\n(use --Force to override; --FORCE to OVERWRITE)\n"
		unless $Force || $FORCE || !grep(-d, glob("${pcdir}*/[0-9]*/f*"));
	die "ERROR: pool directories empty! (use --Force to override)\n"
		unless $Force || glob("{cpool,pool}/*");

	umask 0000; #No permission bits disabled
	my $time = time; #We will use this for setting atimes.
	my @dirmtimes =();
	my ($line);
LINE:	while($line = <LINKS>) {
		chomp $line;

		unless($line =~ m|^[a-f0-9DZX#]|) { #First character test
			print STDOUT "ERR_CHAR1: $line\n";
			warn sprintf("ERROR: Illegal first line character: %s\n", 
						 substr($line,0,1))
				if $verbose >=1;
			next LINE;  
		}
		switch ($&) {
			case 'D' {
				unless($line =~ m|^D +([^ ]+) +([^ ]+) +([^ ]+) +([^ ]+) +(\Q${pcdir}\E.*)|) {
					print STDOUT "ERR_DFRMT $line\n";
					$formaterr++;
					next LINE; #NOTE: next without line would go to the next switch case
				}
				#NOTE: 1=uname 2=group 3=mode 4=mtime 5=dirpath
#				print STDERR "$1|$2|$3|$4|$5|\n"; #JJK-DEBUG
				my $user = USER($1);
				my $group = GROUP($2);
				my $mode = oct($3);
				my $mtime = $4;
				my $dir = $5; $dir =~ s|/*$|/|;

				if($verbose >= 1) {
					$dir =~ m|pc/([^/]*/[^/]*).*|;
					if($1 ne $currbackup) {
						$currbackup = $1;
						warn "RESTORING: $currbackup\n";
					}
				}
				#Look at @dirtimes stack to see if we have backed out of
				#top directory(ies) on stack and can now set mtime
				my $lastdir; #If in new part of tree, set mtimes for past dirs
				while(defined($lastdir = shift(@dirmtimes)) && 
					  $dir !~ m|^\Q$lastdir\E|) {
					utime($time, shift(@dirmtimes), $lastdir);
				}
				unshift(@dirmtimes, $lastdir) if $lastdir; #Put back last one

				if( -d $dir) { #Already exists, just update own/mod
					unless(chown $user, $group, $dir){
						print STDOUT "ERR_OWNER $line\n";
						$ownererr++;
						next LINE;
					}
					unless(chmod $mode, $dir) {
						print STDOUT "ERR_PERMS $line\n";
						$permserr++;
						next LINE;
					}
				}elsif(! -e $dir) { #Make directory (nothing in the way)
					unless(jmake_path $dir, 
						   {user=>$user, group=>$group, mode=>$mode}) {
						print STDOUT "ERR_MKDIR $line\n";
						$mkdirerr++;
						next LINE;
					}
					$newdir++;
					unshift(@dirmtimes, $mtime); #We need to set dir mtime
					unshift(@dirmtimes, $dir)   #when done adding files to dir
				}else { #Non-directory in the way
					print STDOUT "ERR_DEXST $line\n";
					$filexsterr++;
					next LINE;
				}
			}
			case 'Z' {
				unless($line =~ m|^Z +([^ ]+) +([^ ]+) +([^ ]+) +([^ ]+) +((\Q${pcdir}\E.*/)(.*))|) {
					print STDOUT "ERR_ZFRMT $line\n";
					$formaterr++;
					next LINE;
				}
				#NOTE: 1=uname 2=group 3=mode 4=mtime 5=fullpath 6=dir 7=file
#				print STDERR "$1|$2|$3|$4|$5|$6|$7\n"; #JJK-DEBUG
				my $user = USER($1);
				my $group = GROUP($2);
				my $mode = oct($3);
				my $mtime = $4;
				my $file = $5;
				my $dir = $6;
				my $name = $7;
				if(-e $file) {
					unless($FORCE && -f $file && unlink($file)) {
						print STDOUT "ERR_ZEXST $line\n";
						$filexsterr++;
						next LINE;
					}
				}
				unless( -d $dir ||  jmake_path $dir){ #Make directory if doesn't exist
					#NOTE: typically shouldn't be necesary since list is created
					#with directories along the way
					print STDOUT "ERR_MKDIR $line\n";
					$mkdirerr++;
					next LINE;
				}
				unless(sysopen(ZERO, $file, $CREATMASK, $mode) && close(ZERO)) {
					print STDOUT "ERR_MKZER $line\n";
					$mkzeroerr++;
					next LINE;
				}
				unless(chown $user, $group, $file){
					print STDOUT "ERR_OWNER $line\n";
					$ownererr++;
					next LINE;
				}
				unless(utime $time, $mtime, $file) {
					$utimerr++;
					next LINE;
				}
				$newzero++;
			}
			case 'X' {$skipped++; next LINE; }  #Error line
			case '#' {next LINE; }  #Comment line
			else { #Hard link 
			#Note: linking does not change atime/mtime (only ctime), so ignore
				unless($line =~ m|(c?pool/[0-9a-f]/[0-9a-f]/[0-9a-f]/[^/]+) +((\Q${pcdir}\E.*/).*)|) {
					print STDOUT "ERR_LFRMT $line\n";
					$formaterr++;
					next LINE;
				}
#				print STDERR "$1|$2|$3\n"; # 1=source 2=target 3=targetdir #JJK-DEBUG
				my $source = $1;
				my $target = $2;
				my $targetdir = $3;
				if(-e $target) {
					unless($FORCE && -f $target && unlink($target)) {
						print STDOUT "ERR_LEXST $line\n";
						$filexsterr++;
						next LINE;
					}
				}
				unless(-d $targetdir || jmake_path $targetdir){
                #Make targetdir if doesn't exist
				#NOTE: typically shouldn't be necesary since list is created
				#with directories along the way
					print STDOUT "ERR_MKDIR $line\n";
					$mkdirerr++;
					next LINE;
				}
				unless(jlink $source, $target) {
					print STDOUT "ERR_MKLNK $line\n";
					$mklinkerr++;
					next LINE;
				}
				$newlink++
			}
		} #SWITCH
	} # WHILE reading lines

	#Set mtimes for any remaining directories in @dirmtimes stack
	while(my $dir = shift(@dirmtimes)){
		utime($time, shift(@dirmtimes), $dir);
	}
################################################################################
	#Print results:
	

	printf("\nSUCCESSES: Restores=%d [Dirs=%d Zeros=%d Links=%d] Skipped=%d\n", 
		   ($newdir+$newzero+$newlink), $newdir, $newzero, $newlink, $skipped);
	printf("ERRORS: TOTAL=%d Format=%d Mkdir=%d Mkzero=%d Mklink=%d\n",
		   ($formaterr + $mkdirerr + $mkzeroerr + $mklinkerr +
			$filexsterr + $ownererr + $permserr + $utimerr),
		   $formaterr, $mkdirerr, $mkzeroerr, $mklinkerr);
	printf("        File_exists=%d Owner=%d Perms=%d Mtime=%d\n\n",
		   $filexsterr, $ownererr, $permserr, $utimerr);

	exit; #RESTORE DONE		   
}
###############################################################################