hashtree.cpp

   1 /*
   2  *  hashtree.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 3/6/09.
   6  *  Copyright 2009 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9
  10 #include "hashtree.h"
  11 //#include <openssl/sha.h>
  12 #include "sha1.h"
  13 #include <string.h>
  14 #include <stdlib.h>
  15 #include <fcntl.h>
  16 #include "compat.h"
  17
  18 #ifdef _WIN32
  19 #define OPENFLAGS         O_RDWR|O_CREAT|_O_BINARY
  20 #else
  21 #define OPENFLAGS         O_RDWR|O_CREAT
  22 #endif
  23
  24
  25 using namespace swift;
  26
  27 #define HASHSZ 20
  28 const size_t Sha1Hash::SIZE = HASHSZ;
  29 const Sha1Hash Sha1Hash::ZERO = Sha1Hash();
  30
  31 void SHA1 (const void *data, size_t length, unsigned char *hash) {
  32     blk_SHA_CTX ctx;
  33     blk_SHA1_Init(&ctx);
  34     blk_SHA1_Update(&ctx, data, length);
  35     blk_SHA1_Final(hash, &ctx);
  36 }
  37
  38 Sha1Hash::Sha1Hash(const Sha1Hash& left, const Sha1Hash& right) {
  39     char data[HASHSZ*2];
  40     memcpy(data,left.bits,SIZE);
  41     memcpy(data+SIZE,right.bits,SIZE);
  42     SHA1((unsigned char*)data,SIZE*2,bits);
  43 }
  44
  45 Sha1Hash::Sha1Hash(const char* data, size_t length) {
  46     if (length==-1)
  47         length = strlen(data);
  48     SHA1((unsigned char*)data,length,bits);
  49 }
  50
  51 Sha1Hash::Sha1Hash(const uint8_t* data, size_t length) {
  52     SHA1(data,length,bits);
  53 }
  54
  55 Sha1Hash::Sha1Hash(bool hex, const char* hash) {
  56     if (hex) {
  57         char hx[3]; hx[2]=0;
  58         int val;
  59         for(int i=0; i<SIZE; i++) {
  60             strncpy(hx,hash+i*2,2);
  61             if (sscanf(hx, "%x", &val)!=1) {
  62                 memset(bits,0,20);
  63                 return;
  64             }
  65             bits[i] = val;
  66         }
  67         assert(this->hex()==std::string(hash));
  68     } else
  69         memcpy(bits,hash,SIZE);
  70 }
  71
  72 std::string    Sha1Hash::hex() const {
  73     char hex[HASHSZ*2+1];
  74     for(int i=0; i<HASHSZ; i++)
  75         sprintf(hex+i*2, "%02x", (int)(unsigned char)bits[i]);
  76     return std::string(hex,HASHSZ*2);
  77 }
  78
  79
  80
  81 /**     H a s h   t r e e       */
  82
  83
  84 HashTree::HashTree (const char* filename, const Sha1Hash& root_hash, const char* hash_filename) :
  85 root_hash_(root_hash), fd_(0), hash_fd_(0), data_recheck_(true),
  86 peak_count_(0), hashes_(NULL), size_(0), sizek_(0),
  87 complete_(0), completek_(0)
  88 {
  89     fd_ = open(filename,OPENFLAGS,S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH);
  90     if (fd_<0) {
  91         fd_ = 0;
  92         print_error("cannot open the file");
  93         return;
  94     }
  95     char hfn[1024] = "";
  96     if (!hash_filename) {
  97         strcat(hfn, filename);
  98         strcat(hfn, ".mhash");
  99     } else
 100         strcpy(hfn,hash_filename);
 101     hash_fd_ = open(hfn,OPENFLAGS,S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH);
 102     if (hash_fd_<0) {
 103         hash_fd_ = 0;
 104         print_error("cannot open hash file");
 105         return;
 106     }
 107     if (root_hash_==Sha1Hash::ZERO) { // fresh submit, hash it
 108         assert(file_size(fd_));
 109         Submit();
 110     } else {
 111         RecoverProgress();
 112     } // else  LoadComplete()
 113 }
 114
 115
 116 void            HashTree::Submit () {
 117     size_ = file_size(fd_);
 118     sizek_ = (size_ + 1023) >> 10;
 119     peak_count_ = bin64_t::peaks(sizek_,peaks_);
 120     int hashes_size = Sha1Hash::SIZE*sizek_*2;
 121     file_resize(hash_fd_,hashes_size);
 122     hashes_ = (Sha1Hash*) memory_map(hash_fd_,hashes_size);
 123     if (!hashes_) {
 124         size_ = sizek_ = complete_ = completek_ = 0;
 125         print_error("mmap failed");
 126         return;
 127     }
 128     for (size_t i=0; i<sizek_; i++) {
 129         char kilo[1<<10];
 130         size_t rd = read(fd_,kilo,1<<10);
 131         if (rd<(1<<10) && i!=sizek_-1) {
 132             free(hashes_);
 133             hashes_=NULL;
 134             return;
 135         }
 136         bin64_t pos(0,i);
 137         hashes_[pos] = Sha1Hash(kilo,rd);
 138         ack_out_.set(pos);
 139         complete_+=rd;
 140         completek_++;
 141     }
 142     for (int p=0; p<peak_count_; p++) {
 143         if (!peaks_[p].is_base())
 144             for(bin64_t b=peaks_[p].left_foot().parent(); b.within(peaks_[p]); b=b.next_dfsio(1))
 145                 hashes_[b] = Sha1Hash(hashes_[b.left()],hashes_[b.right()]);
 146         peak_hashes_[p] = hashes_[peaks_[p]];
 147     }
 148
 149     root_hash_ = DeriveRoot();
 150
 151 }
 152
 153
 154 /** Basically, simulated receiving every single packet, except
 155  for some optimizations. */
 156 void            HashTree::RecoverProgress () {
 157     size_t size = file_size(fd_);
 158     size_t sizek = (size + 1023) >> 10;
 159     bin64_t peaks[64];
 160     int peak_count = bin64_t::peaks(sizek,peaks);
 161     for(int i=0; i<peak_count; i++) {
 162         Sha1Hash peak_hash;
 163         file_seek(hash_fd_,peaks[i]*sizeof(Sha1Hash));
 164         if (read(hash_fd_,&peak_hash,sizeof(Sha1Hash))!=sizeof(Sha1Hash))
 165             return;
 166         OfferPeakHash(peaks[i], peak_hash);
 167     }
 168     if (!this->size())
 169         return; // if no valid peak hashes found
 170     // at this point, we may use mmapd hashes already
 171     // so, lets verify hashes and the data we've got
 172     char zeros[1<<10];
 173     memset(zeros, 0, 1<<10);
 174     Sha1Hash kilo_zero(zeros,1<<10);
 175     for(int p=0; p<packet_size(); p++) {
 176         char buf[1<<10];
 177         bin64_t pos(0,p);
 178         if (hashes_[pos]==Sha1Hash::ZERO)
 179             continue;
 180         size_t rd = read(fd_,buf,1<<10);
 181         if (rd!=(1<<10) && p!=packet_size()-1)
 182             break;
 183         if (rd==(1<<10) && !memcmp(buf, zeros, rd) &&
 184                 hashes_[pos]!=kilo_zero) // FIXME
 185             continue;
 186         if ( data_recheck_ && !OfferHash(pos, Sha1Hash(buf,rd)) )
 187             continue;
 188         ack_out_.set(pos);
 189         completek_++;
 190         complete_+=rd;
 191         if (rd!=(1<<10) && p==packet_size()-1)
 192             size_ = ((sizek_-1)<<10) + rd;
 193     }
 194 }
 195
 196
 197 bool            HashTree::OfferPeakHash (bin64_t pos, const Sha1Hash& hash) {
 198     assert(!size_);
 199     if (peak_count_) {
 200         bin64_t last_peak = peaks_[peak_count_-1];
 201         if ( pos.layer()>=last_peak.layer() ||
 202             pos.base_offset()!=last_peak.base_offset()+last_peak.width() )
 203             peak_count_ = 0;
 204     }
 205     peaks_[peak_count_] = pos;
 206     peak_hashes_[peak_count_] = hash;
 207     peak_count_++;
 208     // check whether peak hash candidates add up to the root hash
 209     Sha1Hash mustbe_root = DeriveRoot();
 210     if (mustbe_root!=root_hash_)
 211         return false;
 212     for(int i=0; i<peak_count_; i++)
 213         sizek_ += peaks_[i].width();
 214
 215     // bingo, we now know the file size (rounded up to a KByte)
 216
 217     size_ = sizek_<<10;
 218     completek_ = complete_ = 0;
 219     sizek_ = (size_ + 1023) >> 10;
 220
 221     size_t cur_size = file_size(fd_);
 222     if ( cur_size<=(sizek_-1)<<10  || cur_size>sizek_<<10 )
 223         if (file_resize(fd_, size_)) {
 224             print_error("cannot set file size\n");
 225             size_=0; // remain in the 0-state
 226             return false;
 227         }
 228
 229     // mmap the hash file into memory
 230     size_t expected_size = sizeof(Sha1Hash)*sizek_*2;
 231     if ( file_size(hash_fd_) != expected_size )
 232         file_resize (hash_fd_, expected_size);
 233
 234     hashes_ = (Sha1Hash*) memory_map(hash_fd_,expected_size);
 235     if (!hashes_) {
 236         size_ = sizek_ = complete_ = completek_ = 0;
 237         print_error("mmap failed");
 238         return false;
 239     }
 240
 241     for(int i=0; i<peak_count_; i++)
 242         hashes_[peaks_[i]] = peak_hashes_[i];
 243     return true;
 244 }
 245
 246
 247 Sha1Hash        HashTree::DeriveRoot () {
 248     int c = peak_count_-1;
 249     bin64_t p = peaks_[c];
 250     Sha1Hash hash = peak_hashes_[c];
 251     c--;
 252     while (p!=bin64_t::ALL) {
 253         if (p.is_left()) {
 254             p = p.parent();
 255             hash = Sha1Hash(hash,Sha1Hash::ZERO);
 256         } else {
 257             if (c<0 || peaks_[c]!=p.sibling())
 258                 return Sha1Hash::ZERO;
 259             hash = Sha1Hash(peak_hashes_[c],hash);
 260             p = p.parent();
 261             c--;
 262         }
 263     }
 264     return hash;
 265 }
 266
 267
 268 /** For live streaming: appends the data, adjusts the tree.
 269     @ return the number of fresh (tail) peak hashes */
 270 int         HashTree::AppendData (char* data, int length) {
 271     return 0;
 272 }
 273
 274
 275 bin64_t         HashTree::peak_for (bin64_t pos) const {
 276     int pi=0;
 277     while (pi<peak_count_ && !pos.within(peaks_[pi]))
 278         pi++;
 279     return pi==peak_count_ ? bin64_t(bin64_t::NONE) : peaks_[pi];
 280 }
 281
 282
 283 bool            HashTree::OfferHash (bin64_t pos, const Sha1Hash& hash) {
 284     if (!size_)  // only peak hashes are accepted at this point
 285         return OfferPeakHash(pos,hash);
 286     bin64_t peak = peak_for(pos);
 287     if (peak==bin64_t::NONE)
 288         return false;
 289     if (peak==pos)
 290         return hash == hashes_[pos];
 291     if (ack_out_.get(pos.parent())!=binmap_t::EMPTY)
 292         return hash==hashes_[pos]; // have this hash already, even accptd data
 293     hashes_[pos] = hash;
 294     if (!pos.is_base())
 295         return false; // who cares?
 296     bin64_t p = pos;
 297     Sha1Hash uphash = hash;
 298     while ( p!=peak && ack_out_.get(p)==binmap_t::EMPTY ) {
 299         hashes_[p] = uphash;
 300         p = p.parent();
 301         uphash = Sha1Hash(hashes_[p.left()],hashes_[p.right()]) ;
 302     }// walk to the nearest proven hash
 303     return uphash==hashes_[p];
 304 }
 305
 306
 307 bool            HashTree::OfferData (bin64_t pos, const char* data, size_t length) {
 308     if (!size())
 309         return false;
 310     if (!pos.is_base())
 311         return false;
 312     if (length<1024 && pos!=bin64_t(0,sizek_-1))
 313         return false;
 314     if (ack_out_.get(pos)==binmap_t::FILLED)
 315         return true; // to set data_in_
 316     bin64_t peak = peak_for(pos);
 317     if (peak==bin64_t::NONE)
 318         return false;
 319
 320     Sha1Hash data_hash(data,length);
 321     if (!OfferHash(pos, data_hash)) {
 322         //printf("invalid hash for %s: %s\n",pos.str(),data_hash.hex().c_str()); // paranoid
 323         return false;
 324     }
 325
 326     //printf("g %lli %s\n",(uint64_t)pos,hash.hex().c_str());
 327     ack_out_.set(pos,binmap_t::FILLED);
 328     pwrite(fd_,data,length,pos.base_offset()<<10);
 329     complete_ += length;
 330     completek_++;
 331     if (pos.base_offset()==sizek_-1) {
 332         size_ = ((sizek_-1)<<10) + length;
 333         if (file_size(fd_)!=size_)
 334             file_resize(fd_,size_);
 335     }
 336     return true;
 337 }
 338
 339
 340 uint64_t      HashTree::seq_complete () {
 341     uint64_t seqk = ack_out_.seq_length();
 342     if (seqk==sizek_)
 343         return size_;
 344     else
 345         return seqk<<10;
 346 }
 347
 348 HashTree::~HashTree () {
 349     if (hashes_)
 350         memory_unmap(hash_fd_, hashes_, sizek_*2*sizeof(Sha1Hash));
 351     if (fd_)
 352         close(fd_);
 353     if (hash_fd_)
 354         close(hash_fd_);
 355 }
 356