src/libswift_udp/hashtree.cpp

   1 /*
   2  *  hashtree.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 3/6/09.
   6  *  Copyright 2009-2012 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved.
   7  *
   8  */
   9
  10 #include "hashtree.h"
  11 #include "bin_utils.h"
  12 //#include <openssl/sha.h>
  13 #include "sha1.h"
  14 #include <cassert>
  15 #include <cstring>
  16 #include <cstdlib>
  17 #include <fcntl.h>
  18 #include "compat.h"
  19 #include "swift.h"
  20
  21 #include <iostream>
  22
  23 #ifdef _WIN32
  24 #define OPENFLAGS         O_RDWR|O_CREAT|_O_BINARY
  25 #else
  26 #define OPENFLAGS         O_RDWR|O_CREAT
  27 #endif
  28
  29
  30 using namespace swift;
  31
  32 const Sha1Hash Sha1Hash::ZERO = Sha1Hash();
  33
  34 void SHA1 (const void *data, size_t length, unsigned char *hash) {
  35     blk_SHA_CTX ctx;
  36     blk_SHA1_Init(&ctx);
  37     blk_SHA1_Update(&ctx, data, length);
  38     blk_SHA1_Final(hash, &ctx);
  39 }
  40
  41 Sha1Hash::Sha1Hash(const Sha1Hash& left, const Sha1Hash& right) {
  42     blk_SHA_CTX ctx;
  43     blk_SHA1_Init(&ctx);
  44     blk_SHA1_Update(&ctx, left.bits,SIZE);
  45     blk_SHA1_Update(&ctx, right.bits,SIZE);
  46     blk_SHA1_Final(bits, &ctx);
  47 }
  48
  49 Sha1Hash::Sha1Hash(const char* data, size_t length) {
  50     if (length==-1)
  51         length = strlen(data);
  52     SHA1((unsigned char*)data,length,bits);
  53 }
  54
  55 Sha1Hash::Sha1Hash(const uint8_t* data, size_t length) {
  56     SHA1(data,length,bits);
  57 }
  58
  59 Sha1Hash::Sha1Hash(bool hex, const char* hash) {
  60     if (hex) {
  61         int val;
  62         for(int i=0; i<SIZE; i++) {
  63             if (sscanf(hash+i*2, "%2x", &val)!=1) {
  64                 memset(bits,0,20);
  65                 return;
  66             }
  67             bits[i] = val;
  68         }
  69         assert(this->hex()==std::string(hash));
  70     } else
  71         memcpy(bits,hash,SIZE);
  72 }
  73
  74 std::string    Sha1Hash::hex() const {
  75     char hex[HASHSZ*2+1];
  76     for(int i=0; i<HASHSZ; i++)
  77         sprintf(hex+i*2, "%02x", (int)(unsigned char)bits[i]);
  78     return std::string(hex,HASHSZ*2);
  79 }
  80
  81
  82
  83 /**     H a s h   t r e e       */
  84
  85
  86 HashTree::HashTree (const char* filename, const Sha1Hash& root_hash, uint32_t chunk_size, const char* hash_filename, bool force_check_diskvshash, bool check_netwvshash, const char* binmap_filename) :
  87 root_hash_(root_hash), hashes_(NULL), peak_count_(0), fd_(0), hash_fd_(0),
  88 filename_(filename), size_(0), sizec_(0), complete_(0), completec_(0),
  89 chunk_size_(chunk_size), check_netwvshash_(check_netwvshash)
  90 {
  91     fd_ = open(filename,OPENFLAGS,S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH);
  92     if (fd_<0) {
  93         fd_ = 0;
  94         print_error("cannot open the file");
  95         return;
  96     }
  97         std::string hfn;
  98         if (!hash_filename){
  99                 hfn.assign(filename);
 100                 hfn.append(".mhash");
 101                 hash_filename = hfn.c_str();
 102         }
 103
 104         std::string bfn;
 105         if (!binmap_filename){
 106                 bfn.assign(filename);
 107                 bfn.append(".mbinmap");
 108                 binmap_filename = bfn.c_str();
 109         }
 110
 111         // Arno: if user doesn't want to check hashes but no .mhash, check hashes anyway
 112         bool actually_force_check_diskvshash = force_check_diskvshash;
 113     bool mhash_exists=true;
 114 #ifdef WIN32
 115     struct _stat buf;
 116 #else
 117     struct stat buf;
 118 #endif
 119     int res = stat( hash_filename, &buf );
 120     if( res < 0 && errno == ENOENT)
 121         mhash_exists = false;
 122     if (!mhash_exists && !force_check_diskvshash)
 123         actually_force_check_diskvshash = true;
 124
 125
 126     // Arno: if the remainder of the hashtree state is on disk we can
 127     // hashcheck very quickly
 128     bool binmap_exists=true;
 129     res = stat( binmap_filename, &buf );
 130     if( res < 0 && errno == ENOENT)
 131         binmap_exists = false;
 132
 133     //fprintf(stderr,"hashtree: hashchecking want %s do %s binmap-on-disk %s\n", (force_check_diskvshash ? "yes" : "no"), (actually_force_check_diskvshash? "yes" : "no"), (binmap_exists? "yes" : "no") );
 134
 135     hash_fd_ = open(hfn.c_str(),OPENFLAGS,S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH);
 136     if (hash_fd_<0) {
 137         hash_fd_ = 0;
 138         print_error("cannot open hash file");
 139         return;
 140     }
 141
 142     // Arno: if user wants to or no .mhash, and if root hash unknown (new file) and no checkpoint, (re)calc root hash
 143     if (file_size(fd_) && ((actually_force_check_diskvshash) || (root_hash_==Sha1Hash::ZERO && !binmap_exists) || (!mhash_exists)) ) {
 144         // fresh submit, hash it
 145         dprintf("%s hashtree full compute\n",tintstr());
 146         assert(file_size(fd_));
 147         Submit();
 148     } else if (mhash_exists && binmap_exists && file_size(hash_fd_)) {
 149         // Arno: recreate hash tree without rereading content
 150         dprintf("%s hashtree read from checkpoint\n",tintstr());
 151         FILE *fp = fopen(binmap_filename,"rb");
 152         if (!fp) {
 153                  print_error("hashtree: cannot open .mbinmap file");
 154                  return;
 155         }
 156         if (deserialize(fp) < 0) {
 157                 // Try to rebuild hashtree data
 158                 Submit();
 159         }
 160     } else {
 161         // Arno: no data on disk, or mhash on disk, but no binmap. In latter
 162         // case recreate binmap by reading content again. Historic optimization
 163         // of Submit.
 164         dprintf("%s hashtree empty or partial recompute\n",tintstr());
 165         RecoverProgress();
 166     }
 167 }
 168
 169
 170 HashTree::HashTree(bool dummy, const char* binmap_filename) :
 171 root_hash_(Sha1Hash::ZERO), hashes_(NULL), peak_count_(0), fd_(0), hash_fd_(0),
 172 filename_(""), size_(0), sizec_(0), complete_(0), completec_(0),
 173 chunk_size_(0), check_netwvshash_(false)
 174 {
 175         FILE *fp = fopen(binmap_filename,"rb");
 176         if (!fp) {
 177                  return;
 178         }
 179         if (partial_deserialize(fp) < 0) {
 180         }
 181         fclose(fp);
 182 }
 183
 184
 185 // Reads complete file and constructs hash tree
 186 void            HashTree::Submit () {
 187     size_ = file_size(fd_);
 188     sizec_ = (size_ + chunk_size_-1) / chunk_size_;
 189
 190     //fprintf(stderr,"hashtree: submit: cs %i\n", chunk_size_);
 191
 192     peak_count_ = gen_peaks(sizec_,peaks_);
 193     int hashes_size = Sha1Hash::SIZE*sizec_*2;
 194     dprintf("%s hashtree submit resizing hash file\n",tintstr() );
 195     file_resize(hash_fd_,hashes_size);
 196     hashes_ = (Sha1Hash*) memory_map(hash_fd_,hashes_size);
 197     if (!hashes_) {
 198         size_ = sizec_ = complete_ = completec_ = 0;
 199         print_error("mmap failed");
 200         return;
 201     }
 202     size_t last_piece_size = (sizec_ - 1) % (chunk_size_) + 1;
 203     char *chunk = new char[chunk_size_];
 204     for (uint64_t i=0; i<sizec_; i++) {
 205
 206         size_t rd = read(fd_,chunk,chunk_size_);
 207         if (rd<(chunk_size_) && i!=sizec_-1) {
 208             free(hashes_);
 209             hashes_=NULL;
 210             return;
 211         }
 212         bin_t pos(0,i);
 213         hashes_[pos.toUInt()] = Sha1Hash(chunk,rd);
 214         ack_out_.set(pos);
 215         while (pos.is_right()){
 216             pos = pos.parent();
 217             hashes_[pos.toUInt()] = Sha1Hash(hashes_[pos.left().toUInt()],hashes_[pos.right().toUInt()]);
 218         }
 219         complete_+=rd;
 220         completec_++;
 221     }
 222     delete chunk;
 223     for (int p=0; p<peak_count_; p++) {
 224         peak_hashes_[p] = hashes_[peaks_[p].toUInt()];
 225     }
 226
 227     root_hash_ = DeriveRoot();
 228
 229 }
 230
 231
 232 /** Basically, simulated receiving every single chunk, except
 233  for some optimizations.
 234  Precondition: root hash known */
 235 void            HashTree::RecoverProgress () {
 236
 237         //fprintf(stderr,"hashtree: recover: cs %i\n", chunk_size_);
 238
 239         if (!RecoverPeakHashes())
 240                 return;
 241
 242     // at this point, we may use mmapd hashes already
 243     // so, lets verify hashes and the data we've got
 244     char *zero_chunk = new char[chunk_size_];
 245     memset(zero_chunk, 0, chunk_size_);
 246     Sha1Hash zero_hash(zero_chunk,chunk_size_);
 247
 248     // Arno: loop over all pieces, read each from file
 249     // ARNOSMPTODO: problem is that we may have the complete hashtree, but
 250     // not have all pieces. So hash file gives too little information to
 251     // determine whether file is complete on disk.
 252     //
 253     char *buf = new char[chunk_size_];
 254     for(int p=0; p<size_in_chunks(); p++) {
 255         bin_t pos(0,p);
 256         if (hashes_[pos.toUInt()]==Sha1Hash::ZERO)
 257             continue;
 258         size_t rd = read(fd_,buf,chunk_size_);
 259         if (rd!=(chunk_size_) && p!=size_in_chunks()-1)
 260             break;
 261         if (rd==(chunk_size_) && !memcmp(buf, zero_chunk, rd) &&
 262                 hashes_[pos.toUInt()]!=zero_hash) // FIXME // Arno == don't have piece yet?
 263             continue;
 264         if (!OfferHash(pos, Sha1Hash(buf,rd)) )
 265             continue;
 266         ack_out_.set(pos);
 267         completec_++;
 268         complete_+=rd;
 269         if (rd!=(chunk_size_) && p==size_in_chunks()-1) // set the exact file size
 270             size_ = ((sizec_-1)*chunk_size_) + rd;
 271     }
 272     delete buf;
 273     delete zero_chunk;
 274 }
 275
 276 /** Precondition: root hash known */
 277 bool HashTree::RecoverPeakHashes()
 278 {
 279     uint64_t size = file_size(fd_);
 280     uint64_t sizek = (size + chunk_size_-1) / chunk_size_;
 281
 282         // Arno: Calc location of peak hashes, read them from hash file and check if
 283         // they match to root hash. If so, load hashes into memory.
 284         bin_t peaks[64];
 285     int peak_count = gen_peaks(sizek,peaks);
 286     for(int i=0; i<peak_count; i++) {
 287         Sha1Hash peak_hash;
 288         file_seek(hash_fd_,peaks[i].toUInt()*sizeof(Sha1Hash));
 289         if (read(hash_fd_,&peak_hash,sizeof(Sha1Hash))!=sizeof(Sha1Hash))
 290             return false;
 291         OfferPeakHash(peaks[i], peak_hash);
 292     }
 293     if (!this->size())
 294         return false; // if no valid peak hashes found
 295
 296     return true;
 297 }
 298
 299 int HashTree::serialize(FILE *fp)
 300 {
 301         fprintf_retiffail(fp,"version %i\n", 1 );
 302         fprintf_retiffail(fp,"root hash %s\n", root_hash_.hex().c_str() );
 303         fprintf_retiffail(fp,"chunk size %lu\n", chunk_size_ );
 304         fprintf_retiffail(fp,"complete %llu\n", complete_ );
 305         fprintf_retiffail(fp,"completec %llu\n", completec_ );
 306         return ack_out_.serialize(fp);
 307 }
 308
 309
 310 /** Arno: recreate hash tree from .mbinmap file without rereading content.
 311  * Precondition: root hash known
 312  */
 313 int HashTree::deserialize(FILE *fp) {
 314         return internal_deserialize(fp,true);
 315 }
 316
 317 int HashTree::partial_deserialize(FILE *fp) {
 318         return internal_deserialize(fp,false);
 319 }
 320
 321
 322 int HashTree::internal_deserialize(FILE *fp,bool contentavail) {
 323
 324         char hexhashstr[256];
 325         uint64_t c,cc;
 326         size_t cs;
 327         int version;
 328
 329         fscanf_retiffail(fp,"version %i\n", &version );
 330         fscanf_retiffail(fp,"root hash %s\n", hexhashstr);
 331         fscanf_retiffail(fp,"chunk size %lu\n", &cs);
 332         fscanf_retiffail(fp,"complete %llu\n", &c );
 333         fscanf_retiffail(fp,"completec %llu\n", &cc );
 334
 335         //fprintf(stderr,"hashtree: deserialize: %s %llu ~ %llu * %i\n", hexhashstr, c, cc, cs );
 336
 337         if (ack_out_.deserialize(fp) < 0)
 338                 return -1;
 339         root_hash_ = Sha1Hash(true, hexhashstr);
 340         chunk_size_ = cs;
 341
 342         // Arno, 2012-01-03: Hack to just get root hash
 343         if (!contentavail)
 344                 return 2;
 345
 346         if (!RecoverPeakHashes()) {
 347                 root_hash_ = Sha1Hash::ZERO;
 348                 ack_out_.clear();
 349                 return -1;
 350         }
 351
 352         // Are reset by RecoverPeakHashes() for some reason.
 353         complete_ = c;
 354         completec_ = cc;
 355     size_ = file_size(fd_);
 356     sizec_ = (size_ + chunk_size_-1) / chunk_size_;
 357
 358     return 0;
 359 }
 360
 361
 362 bool            HashTree::OfferPeakHash (bin_t pos, const Sha1Hash& hash) {
 363         char bin_name_buf[32];
 364         dprintf("%s hashtree offer peak %s\n",tintstr(),pos.str(bin_name_buf));
 365
 366     assert(!size_);
 367     if (peak_count_) {
 368         bin_t last_peak = peaks_[peak_count_-1];
 369         if ( pos.layer()>=last_peak.layer() ||
 370             pos.base_offset()!=last_peak.base_offset()+last_peak.base_length() )
 371             peak_count_ = 0;
 372     }
 373     peaks_[peak_count_] = pos;
 374     peak_hashes_[peak_count_] = hash;
 375     peak_count_++;
 376     // check whether peak hash candidates add up to the root hash
 377     Sha1Hash mustbe_root = DeriveRoot();
 378     if (mustbe_root!=root_hash_)
 379         return false;
 380     for(int i=0; i<peak_count_; i++)
 381         sizec_ += peaks_[i].base_length();
 382
 383     // bingo, we now know the file size (rounded up to a chunk_size() unit)
 384
 385     size_ = sizec_ * chunk_size_;
 386     completec_ = complete_ = 0;
 387     sizec_ = (size_ + chunk_size_-1) / chunk_size_;
 388
 389     // ARNOTODO: win32: this is pretty slow for ~200 MB already. Perhaps do
 390     // on-demand sizing for Win32?
 391     uint64_t cur_size = file_size(fd_);
 392     if ( cur_size<=(sizec_-1)*chunk_size_  || cur_size>sizec_*chunk_size_ ) {
 393         dprintf("%s hashtree offerpeak resizing file\n",tintstr() );
 394         if (file_resize(fd_, size_)) {
 395             print_error("cannot set file size\n");
 396             size_=0; // remain in the 0-state
 397             return false;
 398         }
 399     }
 400
 401     // mmap the hash file into memory
 402     uint64_t expected_size = sizeof(Sha1Hash)*sizec_*2;
 403     // Arno, 2011-10-18: on Windows we could optimize this away,
 404     //CreateFileMapping, see compat.cpp will resize the file for us with
 405     // the right params.
 406     //
 407     if ( file_size(hash_fd_) != expected_size ) {
 408         dprintf("%s hashtree offerpeak resizing hash file\n",tintstr() );
 409         file_resize (hash_fd_, expected_size);
 410     }
 411
 412     hashes_ = (Sha1Hash*) memory_map(hash_fd_,expected_size);
 413     if (!hashes_) {
 414         size_ = sizec_ = complete_ = completec_ = 0;
 415         print_error("mmap failed");
 416         return false;
 417     }
 418
 419     for(int i=0; i<peak_count_; i++)
 420         hashes_[peaks_[i].toUInt()] = peak_hashes_[i];
 421
 422     dprintf("%s hashtree memory mapped\n",tintstr() );
 423
 424     return true;
 425 }
 426
 427
 428 Sha1Hash        HashTree::DeriveRoot () {
 429
 430         dprintf("%s hashtree deriving root\n",tintstr() );
 431
 432     int c = peak_count_-1;
 433     bin_t p = peaks_[c];
 434     Sha1Hash hash = peak_hashes_[c];
 435     c--;
 436     // Arno, 2011-10-14: Root hash = top of smallest tree covering content IMHO.
 437     //while (!p.is_all()) {
 438     while (c >= 0) {
 439         if (p.is_left()) {
 440             p = p.parent();
 441             hash = Sha1Hash(hash,Sha1Hash::ZERO);
 442         } else {
 443             if (c<0 || peaks_[c]!=p.sibling())
 444                 return Sha1Hash::ZERO;
 445             hash = Sha1Hash(peak_hashes_[c],hash);
 446             p = p.parent();
 447             c--;
 448         }
 449     }
 450     //fprintf(stderr,"root bin is %lli covers %lli\n", p.toUInt(), p.base_length() );
 451     return hash;
 452 }
 453
 454
 455 /** For live streaming: appends the data, adjusts the tree.
 456     @ return the number of fresh (tail) peak hashes */
 457 int         HashTree::AppendData (char* data, int length) {
 458     return 0;
 459 }
 460
 461
 462 bin_t         HashTree::peak_for (bin_t pos) const {
 463     int pi=0;
 464     while (pi<peak_count_ && !peaks_[pi].contains(pos))
 465         pi++;
 466     return pi==peak_count_ ? bin_t(bin_t::NONE) : peaks_[pi];
 467 }
 468
 469 bool            HashTree::OfferHash (bin_t pos, const Sha1Hash& hash) {
 470     if (!size_)  // only peak hashes are accepted at this point
 471         return OfferPeakHash(pos,hash);
 472
 473     //NETWVSHASH
 474     if (!check_netwvshash_)
 475         return true;
 476
 477     bin_t peak = peak_for(pos);
 478     if (peak.is_none())
 479         return false;
 480     if (peak==pos)
 481         return hash == hashes_[pos.toUInt()];
 482     if (!ack_out_.is_empty(pos.parent()))
 483         return hash==hashes_[pos.toUInt()]; // have this hash already, even accptd data
 484     // LESSHASH
 485     // Arno: if we already verified this hash against the root, don't replace
 486     if (!is_hash_verified_.is_empty(bin_t(0,pos.toUInt())))
 487         return hash == hashes_[pos.toUInt()];
 488
 489     hashes_[pos.toUInt()] = hash;
 490     if (!pos.is_base())
 491         return false; // who cares?
 492     bin_t p = pos;
 493     Sha1Hash uphash = hash;
 494     // Arno: Note well: bin_t(0,p.toUInt()) is to abuse binmap as bitmap.
 495     while ( p!=peak && ack_out_.is_empty(p) && is_hash_verified_.is_empty(bin_t(0,p.toUInt())) ) {
 496         hashes_[p.toUInt()] = uphash;
 497         p = p.parent();
 498                 // Arno: Prevent poisoning the tree with bad values:
 499                 // Left hand hashes should never be zero, and right
 500                 // hand hash is only zero for the last packet, i.e.,
 501                 // layer 0. Higher layers will never have 0 hashes
 502                 // as SHA1(zero+zero) != zero (but b80de5...)
 503                 //
 504         if (hashes_[p.left().toUInt()] == Sha1Hash::ZERO || hashes_[p.right().toUInt()] == Sha1Hash::ZERO)
 505                 break;
 506         uphash = Sha1Hash(hashes_[p.left().toUInt()],hashes_[p.right().toUInt()]);
 507     }// walk to the nearest proven hash
 508
 509     bool success = (uphash==hashes_[p.toUInt()]);
 510     // LESSHASH
 511     if (success) {
 512         // Arno: The hash checks out. Mark all hashes on the uncle path as
 513         // being verified, so we don't have to go higher than them on a next
 514         // check.
 515         p = pos;
 516         // Arno: Note well: bin_t(0,p.toUInt()) is to abuse binmap as bitmap.
 517         is_hash_verified_.set(bin_t(0,p.toUInt()));
 518         while (p.layer() != peak.layer()) {
 519             p = p.parent().sibling();
 520                 is_hash_verified_.set(bin_t(0,p.toUInt()));
 521         }
 522         // Also mark hashes on direct path to root as verified. Doesn't decrease
 523         // #checks, but does increase the number of verified hashes faster.
 524         p = pos;
 525         while (p != peak) {
 526             p = p.parent();
 527                 is_hash_verified_.set(bin_t(0,p.toUInt()));
 528         }
 529     }
 530
 531     return success;
 532 }
 533
 534
 535 bool            HashTree::OfferData (bin_t pos, const char* data, size_t length) {
 536     if (!size())
 537         return false;
 538     if (!pos.is_base())
 539         return false;
 540     if (length<chunk_size_ && pos!=bin_t(0,sizec_-1))
 541         return false;
 542     if (ack_out_.is_filled(pos))
 543         return true; // to set data_in_
 544     bin_t peak = peak_for(pos);
 545     if (peak.is_none())
 546         return false;
 547
 548     Sha1Hash data_hash(data,length);
 549     if (!OfferHash(pos, data_hash)) {
 550         char bin_name_buf[32];
 551 //        printf("invalid hash for %s: %s\n",pos.str(bin_name_buf),data_hash.hex().c_str()); // paranoid
 552         //fprintf(stderr,"INVALID HASH FOR %lli layer %d\n", pos.toUInt(), pos.layer() );
 553         dprintf("%s hashtree check failed (bug TODO) %s\n",tintstr(),pos.str(bin_name_buf));
 554         return false;
 555     }
 556
 557     //printf("g %lli %s\n",(uint64_t)pos,hash.hex().c_str());
 558     ack_out_.set(pos);
 559     // Arno,2011-10-03: appease g++
 560     if (pwrite(fd_,data,length,pos.base_offset()*chunk_size_) < 0)
 561         print_error("pwrite failed");
 562     complete_ += length;
 563     completec_++;
 564     if (pos.base_offset()==sizec_-1) {
 565         size_ = ((sizec_-1)*chunk_size_) + length;
 566         if (file_size(fd_)!=size_)
 567             file_resize(fd_,size_);
 568     }
 569     return true;
 570 }
 571
 572
 573 uint64_t      HashTree::seq_complete () {
 574     uint64_t seqc = ack_out_.find_empty().base_offset();
 575     if (seqc==sizec_)
 576         return size_;
 577     else
 578         return seqc*chunk_size_;
 579 }
 580
 581 HashTree::~HashTree () {
 582     if (hashes_)
 583         memory_unmap(hash_fd_, hashes_, sizec_*2*sizeof(Sha1Hash));
 584     if (fd_)
 585         close(fd_);
 586     if (hash_fd_)
 587         close(hash_fd_);
 588 }
 589