hashtree.cpp

/*
 *  hashtree.cpp
 *  serp++
 *
 *  Created by Victor Grishchenko on 3/6/09.
 *  Copyright 2009-2016 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved.
 *
 */
#include "compat.h"
#include "hashtree.h"
#include "bin_utils.h"
//#include <openssl/sha.h>
#include "sha1.h"
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <fcntl.h>
#include "swift.h"

#include <iostream>

using namespace swift;

const Sha1Hash Sha1Hash::ZERO = Sha1Hash();

void SHA1(const void *data, size_t length, unsigned char *hash)
{
    blk_SHA_CTX ctx;
    blk_SHA1_Init(&ctx);
    blk_SHA1_Update(&ctx, data, length);
    blk_SHA1_Final(hash, &ctx);
}

Sha1Hash::Sha1Hash(const Sha1Hash& left, const Sha1Hash& right)
{
    blk_SHA_CTX ctx;
    blk_SHA1_Init(&ctx);
    blk_SHA1_Update(&ctx, left.bits,SIZE);
    blk_SHA1_Update(&ctx, right.bits,SIZE);
    blk_SHA1_Final(bits, &ctx);
}

Sha1Hash::Sha1Hash(const char* data, size_t length)
{
    if (length==-1)
        length = strlen(data);
    SHA1((unsigned char*)data,length,bits);
}

Sha1Hash::Sha1Hash(const uint8_t* data, size_t length)
{
    SHA1(data,length,bits);
}

Sha1Hash::Sha1Hash(bool hex, const char* hash)
{
    if (hex) {
        int val;
        for (int i=0; i<SIZE; i++) {
            if (sscanf(hash+i*2, "%2x", &val)!=1) {
                memset(bits,0,20);
                return;
            }
            bits[i] = val;
        }
        assert(this->hex()==std::string(hash));
    } else
        memcpy(bits,hash,SIZE);
}

std::string Sha1Hash::hex() const
{
    char hex[HASHSZ*2+1];
    for (int i=0; i<HASHSZ; i++)
        sprintf(hex+i*2, "%02x", (int)(unsigned char)bits[i]);
    return std::string(hex,HASHSZ*2);
}


Sha1Hash & Sha1Hash::operator= (const Sha1Hash & source)
{
    if (this != &source) {
        memcpy(bits,source.bits,SIZE);
    }
    return *this;
}


/**     H a s h   t r e e       */


MmapHashTree::MmapHashTree(Storage *storage, const Sha1Hash& root_hash, uint32_t chunk_size, std::string hash_filename,
                           bool force_check_diskvshash,std::string binmap_filename) :
    HashTree(), root_hash_(root_hash), hashes_(NULL),
    peak_count_(0), hash_fd_(-1), hash_filename_(hash_filename), size_(0), sizec_(0), complete_(0), completec_(0),
    chunk_size_(chunk_size), storage_(storage)
{
    // MULTIFILE
    storage_->SetHashTree(this);
    // If multi-file spec we know the exact size even before getting peaks+last chunk
    int64_t sizefromspec = storage_->GetSizeFromSpec();
    if (sizefromspec != -1) {
        set_size(sizefromspec);
        // Resize all files
        (void)storage_->ResizeReserved(sizefromspec);
    }

    // Arno: if user doesn't want to check hashes but no .mhash, check hashes anyway
    bool actually_force_check_diskvshash = force_check_diskvshash;
    bool mhash_exists=true;
    int64_t mhash_size = file_size_by_path_utf8(hash_filename);
    if (mhash_size < 0)
        mhash_exists = false;
    // Arno, 2012-07-26: Quick fix against partial downloads without .mhash.
    // Previously they would be Submit()ed and the root_hash_ would change.
    // Now if the root_hash_ is set, we don't recompute the tree. More permanent
    // solution is to hashcheck the content, and if it doesn't match the root
    // hash, revert to a clean state.
    //
    if (root_hash_==Sha1Hash::ZERO && !mhash_exists)
        actually_force_check_diskvshash = true;

    // Arno: if the remainder of the hashtree state is on disk we can
    // hashcheck very quickly
    bool binmap_exists=true;
    int res = file_exists_utf8(binmap_filename);
    if (res <= 0)
        binmap_exists = false;
    if (root_hash_==Sha1Hash::ZERO && !binmap_exists)
        actually_force_check_diskvshash = true;

    //fprintf(stderr,"hashtree: hashchecking %s file %s destdir %s want %s do %s mhash-on-disk %s binmap-on-disk %s\n", root_hash.hex().c_str(), storage_->GetOSPathName().c_str(), storage_->GetDestDir().c_str(), (force_check_diskvshash ? "yes" : "no"), (actually_force_check_diskvshash? "yes" : "no"), (mhash_exists? "yes" : "no"), (binmap_exists? "yes" : "no") );
    // Arno, 2012-07-27: Sanity check
    if ((mhash_exists || binmap_exists) && storage_->GetReservedSize() == -1) {
        print_error("meta files present but not content");
        SetBroken();
        return;
    }

    // Arno, 2012-09-19: Hash file created only when msgs incoming
    if (mhash_exists) {
        hash_fd_ = OpenHashFile();
        if (hash_fd_ < 0)
            return;
    }

    // Arno: if user wants to or no .mhash, and if root hash unknown (new file) and no checkpoint, (re)calc root hash
    if (storage_->GetReservedSize() > storage_->GetMinimalReservedSize() && actually_force_check_diskvshash) {
        // fresh submit, hash it
        dprintf("%s hashtree full compute\n",tintstr());
        //assert(storage_->GetReservedSize());
        Submit();
    } else if (mhash_exists && binmap_exists && mhash_size > 0) {
        // Arno: recreate hash tree without rereading content
        dprintf("%s hashtree read from checkpoint\n",tintstr());
        FILE *fp = fopen_utf8(binmap_filename.c_str(),"rb");
        if (!fp) {
            print_error("hashtree: cannot open .mbinmap file");
            SetBroken();
            return;
        }
        if (deserialize(fp) < 0) {
            // Try to rebuild hashtree data
            Submit();
        }
        fclose(fp);
    } else {
        // Arno: no data on disk, or mhash on disk, but no binmap. In latter
        // case recreate binmap by reading content again. Historic optimization
        // of Submit.
        dprintf("%s hashtree empty or partial recompute\n",tintstr());
        RecoverProgress();
    }
}


MmapHashTree::MmapHashTree(bool dummy, std::string binmap_filename) :
    HashTree(), root_hash_(Sha1Hash::ZERO), hashes_(NULL), peak_count_(0), hash_fd_(0),
    hash_filename_(""), filename_(""), size_(0), sizec_(0), complete_(0), completec_(0),
    chunk_size_(0)
{
    FILE *fp = fopen_utf8(binmap_filename.c_str(),"rb");
    if (!fp) {
        SetBroken();
        return;
    }
    if (partial_deserialize(fp) < 0) {
    }
    fclose(fp);
}

int MmapHashTree::OpenHashFile()
{
    hash_fd_ = open_utf8(hash_filename_.c_str(),OPENFLAGS,S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH);
    if (hash_fd_<0) {
        hash_fd_ = -1;
        print_error("cannot create/open hash file");
        SetBroken();
    }
    return hash_fd_;
}


// Reads complete file and constructs hash tree
void MmapHashTree::Submit()
{
    size_ = storage_->GetReservedSize();
    sizec_ = (size_ + chunk_size_-1) / chunk_size_;

    //fprintf(stderr,"hashtree: submit: cs %i\n", chunk_size_);

    peak_count_ = gen_peaks(sizec_,peaks_);
    int hashes_size = Sha1Hash::SIZE*sizec_*2;
    dprintf("%s hashtree submit resizing hash file to %d\n",tintstr(), hashes_size);
    if (hashes_size == 0) {
        SetBroken();
        return;
    }

    // Arno, 2012-09-19: Hash file created only when msgs incoming
    if (hash_fd_ == -1) {
        hash_fd_ = OpenHashFile();
        if (hash_fd_ < 0)
            return;
    }

    file_resize(hash_fd_,hashes_size);
    hashes_ = (Sha1Hash*) memory_map(hash_fd_,hashes_size);
    if (!hashes_) {
        size_ = sizec_ = complete_ = completec_ = 0;
        print_error("mmap failed");
        SetBroken();
        return;
    }
    size_t last_piece_size = (sizec_ - 1) % (chunk_size_) + 1;
    char *chunk = new char[chunk_size_];
    for (uint64_t i=0; i<sizec_; i++) {

        ssize_t rd = storage_->Read(chunk,chunk_size_,i*chunk_size_);
        if (rd<(chunk_size_) && i!=sizec_-1) {
            free(hashes_);
            hashes_=NULL;
            SetBroken();
            return;
        }
        bin_t pos(0,i);
        hashes_[pos.toUInt()] = Sha1Hash(chunk,rd);
        ack_out_.set(pos);
        while (pos.is_right()) {
            pos = pos.parent();
            hashes_[pos.toUInt()] = Sha1Hash(hashes_[pos.left().toUInt()],hashes_[pos.right().toUInt()]);
        }
        complete_+=rd;
        completec_++;
    }
    delete chunk;
    for (int p=0; p<peak_count_; p++) {
        peak_hashes_[p] = hashes_[peaks_[p].toUInt()];
    }

    Sha1Hash calcroothash = DeriveRoot();
    if (root_hash_ != Sha1Hash::ZERO && calcroothash != root_hash_) {
        print_error("hash tree calculation error");
        SetBroken();
        return;
    }
    root_hash_ = calcroothash;
}


/** Basically, simulated receiving every single chunk, except
 for some optimizations.
 Precondition: root hash known */
void MmapHashTree::RecoverProgress()
{

    //fprintf(stderr,"hashtree: recover: cs %i\n", chunk_size_);

    if (!RecoverPeakHashes())
        return; // Not fatal

    // at this point, we may use mmapd hashes already
    // so, lets verify hashes and the data we've got
    char *zero_chunk = new char[chunk_size_];
    memset(zero_chunk, 0, chunk_size_);
    Sha1Hash zero_hash(zero_chunk,chunk_size_);

    // Arno: loop over all pieces, read each from file
    // Note that we may have the complete hashtree, but not have all pieces.
    // So hash file gives too little information to determine whether file is
    // complete on disk, hence the .mbinmap file.
    //
    char *buf = new char[chunk_size_];
    for (int p=0; p<size_in_chunks(); p++) {
        bin_t pos(0,p);
        if (hashes_[pos.toUInt()]==Sha1Hash::ZERO)
            continue;
        ssize_t rd = storage_->Read(buf,chunk_size_,p*chunk_size_);
        if (rd!=(chunk_size_) && p!=size_in_chunks()-1)
            break;
        if (rd==(chunk_size_) && !memcmp(buf, zero_chunk, rd) &&
                hashes_[pos.toUInt()]!=zero_hash) // FIXME // Arno == don't have piece yet?
            continue;
        if (!OfferHash(pos, Sha1Hash(buf,rd)))
            continue;
        ack_out_.set(pos);
        completec_++;
        complete_+=rd;
        if (rd!=(chunk_size_) && p==size_in_chunks()-1) // set the exact file size
            size_ = ((sizec_-1)*chunk_size_) + rd;
    }
    delete[] buf;
    delete[] zero_chunk;
}

/** Precondition: root hash known */
bool MmapHashTree::RecoverPeakHashes()
{
    int64_t ret = storage_->GetReservedSize();
    if (ret < 0)
        return false;

    uint64_t size = ret;
    uint64_t sizek = (size + chunk_size_-1) / chunk_size_;

    // Arno: Calc location of peak hashes, read them from hash file and check if
    // they match to root hash. If so, load hashes into memory.
    bin_t peaks[64];
    int peak_count = gen_peaks(sizek,peaks);
    for (int i=0; i<peak_count; i++) {
        Sha1Hash peak_hash;
        file_seek(hash_fd_,peaks[i].toUInt()*sizeof(Sha1Hash));
        if (read(hash_fd_,&peak_hash,sizeof(Sha1Hash))!=sizeof(Sha1Hash))
            return false;
        OfferPeakHash(peaks[i], peak_hash);
    }
    if (!this->size())
        return false; // if no valid peak hashes found

    return true;
}

int MmapHashTree::serialize(FILE *fp)
{
    fprintf_retiffail(fp,"version %i\n", 1);
    fprintf_retiffail(fp,"root hash %s\n", root_hash_.hex().c_str());
    fprintf_retiffail(fp,"chunk size %" PRIu32 "\n", chunk_size_);
    fprintf_retiffail(fp,"complete %" PRIu64 "\n", complete_);
    fprintf_retiffail(fp,"completec %" PRIu64 "\n", completec_);
    return ack_out_.serialize(fp);
}


/** Arno: recreate hash tree from .mbinmap file without rereading content.
 * Precondition: root hash known
 */
int MmapHashTree::deserialize(FILE *fp)
{
    return internal_deserialize(fp,true);
}

int MmapHashTree::partial_deserialize(FILE *fp)
{
    return internal_deserialize(fp,false);
}


int MmapHashTree::internal_deserialize(FILE *fp,bool contentavail)
{

    char hexhashstr[256];
    uint64_t c,cc;
    uint32_t cs;
    int version;

    fscanf_retiffail(fp,"version %i\n", &version);
    fscanf_retiffail(fp,"root hash %s\n", hexhashstr);
    fscanf_retiffail(fp,"chunk size %" PRIu32 "\n", &cs);
    fscanf_retiffail(fp,"complete %" PRIu64 "\n", &c);
    fscanf_retiffail(fp,"completec %" PRIu64 "\n", &cc);

    if (ack_out_.deserialize(fp) < 0)
        return -1;
    root_hash_ = Sha1Hash(true, hexhashstr);
    chunk_size_ = cs;
    complete_ = c;
    completec_ = cc;

    // Arno, 2012-01-03: Hack to just get root hash
    if (!contentavail)
        return 2;

    if (!RecoverPeakHashes()) {
        root_hash_ = Sha1Hash::ZERO;
        ack_out_.clear();
        return -1;
    }

    // Are reset by RecoverPeakHashes() for some reason.
    complete_ = c;
    completec_ = cc;
    size_ = storage_->GetReservedSize();
    sizec_ = (size_ + chunk_size_-1) / chunk_size_;

    return 0;
}


bool MmapHashTree::OfferPeakHash(bin_t pos, const Sha1Hash& hash)
{
    dprintf("%s hashtree offer peak %s\n",tintstr(),pos.str().c_str());

    // Arno: This code expects peaks to be sent in tree descending order,
    // as is now required in PPSP-04.
    //assert(!size_);
    if (peak_count_) {
        bin_t last_peak = peaks_[peak_count_-1];
        if (pos.layer()>=last_peak.layer() ||
                pos.base_offset()!=last_peak.base_offset()+last_peak.base_length())
            peak_count_ = 0;
    }
    peaks_[peak_count_] = pos;
    peak_hashes_[peak_count_] = hash;
    peak_count_++;
    // check whether peak hash candidates add up to the root hash
    Sha1Hash mustbe_root = DeriveRoot();
    if (mustbe_root!=root_hash_)
        return false;
    for (int i=0; i<peak_count_; i++)
        sizec_ += peaks_[i].base_length();

    // bingo, we now know the file size (rounded up to a chunk_size() unit)

    if (!size_) // MULTIFILE: not known from spec
        size_ = sizec_ * chunk_size_;
    completec_ = complete_ = 0;
    sizec_ = (size_ + chunk_size_-1) / chunk_size_;

    // ARNOTODO: win32: this is pretty slow for ~200 MB already. Perhaps do
    // on-demand sizing for Win32?
    uint64_t cur_size = storage_->GetReservedSize();
    if (cur_size<=(sizec_-1)*chunk_size_  || cur_size>sizec_*chunk_size_) {
        dprintf("%s hashtree offerpeak resizing file\n",tintstr());
        if (storage_->ResizeReserved(size_)) {
            print_error("cannot set file size\n");
            size_=0; // remain in the 0-state
            return false;
        }
    }

    // Arno, 2012-09-19: Hash file created only when msgs incoming
    if (hash_fd_ == -1) {
        hash_fd_ = OpenHashFile();
        if (hash_fd_ < 0)
            return false;
    }

    // mmap the hash file into memory
    uint64_t expected_size = sizeof(Sha1Hash)*sizec_*2;
    // Arno, 2011-10-18: on Windows we could optimize this away,
    //CreateFileMapping, see compat.cpp will resize the file for us with
    // the right params.
    //
    if (file_size(hash_fd_) != expected_size) {
        dprintf("%s hashtree offerpeak resizing hash file\n",tintstr());
        file_resize(hash_fd_, expected_size);
    }

    hashes_ = (Sha1Hash*) memory_map(hash_fd_,expected_size);
    if (!hashes_) {
        size_ = sizec_ = complete_ = completec_ = 0;
        print_error("mmap failed");
        return false;
    }

    for (int i=0; i<peak_count_; i++)
        hashes_[peaks_[i].toUInt()] = peak_hashes_[i];

    dprintf("%s hashtree memory mapped\n",tintstr());

    return true;
}


Sha1Hash MmapHashTree::DeriveRoot()
{

    dprintf("%s hashtree deriving root\n",tintstr());

    int c = peak_count_-1;
    bin_t p = peaks_[c];
    Sha1Hash hash = peak_hashes_[c];
    c--;
    // Arno, 2011-10-14: Root hash = top of smallest tree covering content IMHO.
    //while (!p.is_all()) {
    while (c >= 0) {
        if (p.is_left()) {
            p = p.parent();
            hash = Sha1Hash(hash,Sha1Hash::ZERO);
        } else {
            if (c<0 || peaks_[c]!=p.sibling())
                return Sha1Hash::ZERO;
            hash = Sha1Hash(peak_hashes_[c],hash);
            p = p.parent();
            c--;
        }
    }

    //fprintf(stderr,"hashtree: derive: root hash is %s\n", hash.hex().c_str() );

    //fprintf(stderr,"root bin is %" PRIi64 " covers %" PRIi64 "\n", p.toUInt(), p.base_length() );
    return hash;
}


/** For live streaming: appends the data, adjusts the tree.
    @ return the number of fresh (tail) peak hashes */
int MmapHashTree::AppendData(char* data, int length)
{
    return 0;
}


bin_t MmapHashTree::peak_for(bin_t pos) const
{
    int pi=0;
    while (pi<peak_count_ && !peaks_[pi].contains(pos))
        pi++;
    return pi==peak_count_ ? bin_t(bin_t::NONE) : peaks_[pi];
}

bool MmapHashTree::OfferHash(bin_t pos, const Sha1Hash& hash)
{
    if (!size_)  // only peak hashes are accepted at this point
        return OfferPeakHash(pos,hash);
    if (hashes_ == NULL) {
        dprintf("%s hashtree never loaded correctly from disk\n",tintstr());
        return false;
    }

    bin_t peak = peak_for(pos);
    if (peak.is_none())
        return false;
    if (peak==pos)
        return hash == hashes_[pos.toUInt()];
    if (!ack_out_.is_empty(pos.parent()))
        return hash==hashes_[pos.toUInt()]; // have this hash already, even accptd data
    // LESSHASH
    // Arno: if we already verified this hash against the root, don't replace
    if (!is_hash_verified_.is_empty(bin_t(0,pos.toUInt())))
        return hash == hashes_[pos.toUInt()];

    hashes_[pos.toUInt()] = hash;
    if (!pos.is_base())
        return false; // who cares?
    bin_t p = pos;
    Sha1Hash uphash = hash;
    // Arno: Note well: bin_t(0,p.toUInt()) is to abuse binmap as bitmap.
    while (p!=peak && ack_out_.is_empty(p) && is_hash_verified_.is_empty(bin_t(0,p.toUInt()))) {
        hashes_[p.toUInt()] = uphash;
        p = p.parent();
        // Arno: Prevent poisoning the tree with bad values:
        // Left hand hashes should never be zero, and right
        // hand hash is only zero for the last packet, i.e.,
        // layer 0. Higher layers will never have 0 hashes
        // as SHA1(zero+zero) != zero (but b80de5...)
        //
        if (hashes_[p.left().toUInt()] == Sha1Hash::ZERO || hashes_[p.right().toUInt()] == Sha1Hash::ZERO)
            break;
        uphash = Sha1Hash(hashes_[p.left().toUInt()],hashes_[p.right().toUInt()]);
    }// walk to the nearest proven hash

    bool success = (uphash==hashes_[p.toUInt()]);
    // LESSHASH
    if (success) {
        // Arno: The hash checks out. Mark all hashes on the uncle path as
        // being verified, so we don't have to go higher than them on a next
        // check.
        p = pos;
        // Arno: Note well: bin_t(0,p.toUInt()) is to abuse binmap as bitmap.
        is_hash_verified_.set(bin_t(0,p.toUInt()));
        while (p.layer() != peak.layer()) {
            p = p.parent().sibling();
            is_hash_verified_.set(bin_t(0,p.toUInt()));
        }
        // Also mark hashes on direct path to root as verified. Doesn't decrease
        // #checks, but does increase the number of verified hashes faster.
        p = pos;
        while (p != peak) {
            p = p.parent();
            is_hash_verified_.set(bin_t(0,p.toUInt()));
        }
    }

    return success;
}


bool MmapHashTree::OfferData(bin_t pos, const char* data, size_t length)
{
    if (!size())
        return false;
    if (!pos.is_base())
        return false;
    if (length<chunk_size_ && pos!=bin_t(0,sizec_-1))
        return false;
    if (ack_out_.is_filled(pos))
        return true; // to set data_in_
    bin_t peak = peak_for(pos);
    if (peak.is_none())
        return false;

    Sha1Hash data_hash(data,length);
    if (!OfferHash(pos, data_hash)) {
        //printf("invalid hash for %s: %s\n",pos.str(bin_name_buf),data_hash.hex().c_str()); // paranoid
        //fprintf(stderr,"INVALID HASH FOR %" PRIi64 " layer %d\n", pos.toUInt(), pos.layer() );
        // Ric: TODO it's not necessarily a bug.. it happens if a pkt was lost!
        dprintf("%s hashtree check failed (bug TODO) %s\n",tintstr(),pos.str().c_str());
        return false;
    }

    //printf("g %" PRIi64 " %s\n",(uint64_t)pos,hash.hex().c_str());
    ack_out_.set(pos);
    // Arno,2011-10-03: appease g++
    if (storage_->Write(data,length,pos.base_offset()*chunk_size_) < 0)
        print_error("pwrite failed");
    complete_ += length;
    completec_++;
    if (pos.base_offset()==sizec_-1) {
        size_ = ((sizec_-1)*chunk_size_) + length;
        if (storage_->GetReservedSize()!=size_)
            storage_->ResizeReserved(size_);
    }
    return true;
}


uint64_t MmapHashTree::seq_complete(int64_t offset)
{

    uint64_t seqc = 0;
    if (offset == 0) {
        uint64_t seqc = ack_out_.find_empty().base_offset();
        if (seqc==sizec_)
            return size_;
        else
            return seqc*chunk_size_;
    } else {
        // SEEK: Calc sequentially complete bytes from an offset
        bin_t binoff = bin_t(0,(offset - (offset % chunk_size_)) / chunk_size_);
        bin_t nextempty = ack_out_.find_empty(binoff);
        if (nextempty == bin_t::NONE || nextempty.base_offset() * chunk_size_ > size_)
            return size_-offset; // All filled from offset

        bin_t::uint_t diffc = nextempty.layer_offset() - binoff.layer_offset();
        uint64_t diffb = diffc * chunk_size_;
        if (diffb > 0)
            diffb -= (offset % chunk_size_);

        return diffb;
    }
}


MmapHashTree::~MmapHashTree()
{
    if (hashes_)
        memory_unmap(hash_fd_, hashes_, sizec_*2*sizeof(Sha1Hash));
    if (hash_fd_ >= 0) {
        close(hash_fd_);
    }
}