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