1// 2// This file is part of the aMule Project. 3// 4// Copyright (c) 2004-2011 Angel Vidal ( kry@amule.org ) 5// Copyright (c) 2003-2011 aMule Team ( admin@amule.org / http://www.amule.org ) 6// Copyright (c) 2002-2011 Merkur ( devs@emule-project.net / http://www.emule-project.net ) 7// 8// Any parts of this program derived from the xMule, lMule or eMule project, 9// or contributed by third-party developers are copyrighted by their 10// respective authors. 11// 12// This program is free software; you can redistribute it and/or modify 13// it under the terms of the GNU General Public License as published by 14// the Free Software Foundation; either version 2 of the License, or 15// (at your option) any later version. 16// 17// This program is distributed in the hope that it will be useful, 18// but WITHOUT ANY WARRANTY; without even the implied warranty of 19// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 20// GNU General Public License for more details. 21// 22// You should have received a copy of the GNU General Public License 23// along with this program; if not, write to the Free Software 24// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA 25// 26 27#include <wx/file.h> 28 29#include "SHAHashSet.h" 30#include "amule.h" 31#include "MemFile.h" 32#include "Preferences.h" 33#include "SHA.h" 34#include "updownclient.h" 35#include "DownloadQueue.h" 36#include "PartFile.h" 37#include "Logger.h" 38#include <common/Format.h> 39 40 41 42// for this version the limits are set very high, they might be lowered later 43// to make a hash trustworthy, at least 10 unique Ips (255.255.128.0) must have sent it 44// and if we have received more than one hash for the file, one hash has to be sent by more than 95% of all unique IPs 45#define MINUNIQUEIPS_TOTRUST 10 // how many unique IPs have to send us a hash to make it trustworthy 46#define MINPERCENTAGE_TOTRUST 92 // how many percentage of clients have to send the same hash to make it trustworthy 47 48CAICHRequestedDataList CAICHHashSet::m_liRequestedData; 49 50///////////////////////////////////////////////////////////////////////////////////////// 51///CAICHHash 52wxString CAICHHash::GetString() const 53{ 54 return EncodeBase32(m_abyBuffer, HASHSIZE); 55} 56 57 58void CAICHHash::Read(CFileDataIO* file) 59{ 60 file->Read(m_abyBuffer,HASHSIZE); 61} 62 63 64void CAICHHash::Write(CFileDataIO* file) const 65{ 66 file->Write(m_abyBuffer,HASHSIZE); 67} 68 69unsigned int CAICHHash::DecodeBase32(const wxString &base32) 70{ 71 return ::DecodeBase32(base32, HASHSIZE, m_abyBuffer); 72} 73 74 75///////////////////////////////////////////////////////////////////////////////////////// 76///CAICHHashTree 77 78CAICHHashTree::CAICHHashTree(uint64 nDataSize, bool bLeftBranch, uint64 nBaseSize) 79{ 80 m_nDataSize = nDataSize; 81 m_nBaseSize = nBaseSize; 82 m_bIsLeftBranch = bLeftBranch; 83 m_pLeftTree = NULL; 84 m_pRightTree = NULL; 85 m_bHashValid = false; 86} 87 88 89CAICHHashTree::~CAICHHashTree() 90{ 91 delete m_pLeftTree; 92 delete m_pRightTree; 93} 94 95 96// recursive 97CAICHHashTree* CAICHHashTree::FindHash(uint64 nStartPos, uint64 nSize, uint8* nLevel) 98{ 99 (*nLevel)++; 100 101 wxCHECK(*nLevel <= 22, NULL); 102 wxCHECK(nStartPos + nSize <= m_nDataSize, NULL); 103 wxCHECK(nSize <= m_nDataSize, NULL); 104 105 if (nStartPos == 0 && nSize == m_nDataSize) { 106 // this is the searched hash 107 return this; 108 } else if (m_nDataSize <= m_nBaseSize) { // sanity 109 // this is already the last level, cant go deeper 110 wxFAIL; 111 return NULL; 112 } else { 113 uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0); 114 uint64 nLeft = (((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize; 115 uint64 nRight = m_nDataSize - nLeft; 116 if (nStartPos < nLeft) { 117 if (nStartPos + nSize > nLeft) { // sanity 118 wxFAIL; 119 return NULL; 120 } 121 122 if (m_pLeftTree == NULL) { 123 m_pLeftTree = new CAICHHashTree(nLeft, true, (nLeft <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE); 124 } else { 125 wxASSERT( m_pLeftTree->m_nDataSize == nLeft ); 126 } 127 128 return m_pLeftTree->FindHash(nStartPos, nSize, nLevel); 129 } else { 130 nStartPos -= nLeft; 131 if (nStartPos + nSize > nRight) { // sanity 132 wxFAIL; 133 return NULL; 134 } 135 136 if (m_pRightTree == NULL) { 137 m_pRightTree = new CAICHHashTree(nRight, false, (nRight <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE); 138 } else { 139 wxASSERT( m_pRightTree->m_nDataSize == nRight ); 140 } 141 142 return m_pRightTree->FindHash(nStartPos, nSize, nLevel); 143 } 144 } 145} 146 147 148// recursive 149// calculates missing hash from the existing ones 150// overwrites existing hashs 151// fails if no hash is found for any branch 152bool CAICHHashTree::ReCalculateHash(CAICHHashAlgo* hashalg, bool bDontReplace) 153{ 154 if (m_pLeftTree && m_pRightTree) { 155 if ( !m_pLeftTree->ReCalculateHash(hashalg, bDontReplace) || !m_pRightTree->ReCalculateHash(hashalg, bDontReplace) ) { 156 return false; 157 } 158 if (bDontReplace && m_bHashValid) { 159 return true; 160 } 161 if (m_pRightTree->m_bHashValid && m_pLeftTree->m_bHashValid) { 162 hashalg->Reset(); 163 hashalg->Add(m_pLeftTree->m_Hash.GetRawHash(), HASHSIZE); 164 hashalg->Add(m_pRightTree->m_Hash.GetRawHash(), HASHSIZE); 165 hashalg->Finish(m_Hash); 166 m_bHashValid = true; 167 return true; 168 } else { 169 return m_bHashValid; 170 } 171 } else if (m_pLeftTree == NULL && m_pRightTree == NULL) { 172 return true; 173 } else { 174 AddDebugLogLineN(logSHAHashSet, wxT("ReCalculateHash failed - Hashtree incomplete")); 175 return false; 176 } 177} 178 179bool CAICHHashTree::VerifyHashTree(CAICHHashAlgo* hashalg, bool bDeleteBadTrees) 180{ 181 if (!m_bHashValid) { 182 wxFAIL; 183 if (bDeleteBadTrees) { 184 if (m_pLeftTree) { 185 delete m_pLeftTree; 186 m_pLeftTree = NULL; 187 } 188 if (m_pRightTree) { 189 delete m_pRightTree; 190 m_pRightTree = NULL; 191 } 192 } 193 AddDebugLogLineN(logSHAHashSet, wxT("VerifyHashTree - No masterhash available")); 194 return false; 195 } 196 197 // calculated missing hashs without overwriting anything 198 if (m_pLeftTree && !m_pLeftTree->m_bHashValid) { 199 m_pLeftTree->ReCalculateHash(hashalg, true); 200 } 201 if (m_pRightTree && !m_pRightTree->m_bHashValid) { 202 m_pRightTree->ReCalculateHash(hashalg, true); 203 } 204 205 if ((m_pRightTree && m_pRightTree->m_bHashValid) ^ (m_pLeftTree && m_pLeftTree->m_bHashValid)) { 206 // one branch can never be verified 207 if (bDeleteBadTrees) { 208 if (m_pLeftTree) { 209 delete m_pLeftTree; 210 m_pLeftTree = NULL; 211 } 212 if (m_pRightTree) { 213 delete m_pRightTree; 214 m_pRightTree = NULL; 215 } 216 } 217 AddDebugLogLineN(logSHAHashSet, wxT("VerifyHashSet failed - Hashtree incomplete")); 218 return false; 219 } 220 if ((m_pRightTree && m_pRightTree->m_bHashValid) && (m_pLeftTree && m_pLeftTree->m_bHashValid)) { 221 // check verify the hashs of both child nodes against my hash 222 223 CAICHHash CmpHash; 224 hashalg->Reset(); 225 hashalg->Add(m_pLeftTree->m_Hash.GetRawHash(), HASHSIZE); 226 hashalg->Add(m_pRightTree->m_Hash.GetRawHash(), HASHSIZE); 227 hashalg->Finish(CmpHash); 228 229 if (m_Hash != CmpHash) { 230 if (bDeleteBadTrees) { 231 if (m_pLeftTree) { 232 delete m_pLeftTree; 233 m_pLeftTree = NULL; 234 } 235 if (m_pRightTree) { 236 delete m_pRightTree; 237 m_pRightTree = NULL; 238 } 239 } 240 return false; 241 } 242 return m_pLeftTree->VerifyHashTree(hashalg, bDeleteBadTrees) && m_pRightTree->VerifyHashTree(hashalg, bDeleteBadTrees); 243 } else { 244 // last hash in branch - nothing below to verify 245 return true; 246 } 247} 248 249 250void CAICHHashTree::SetBlockHash(uint64 nSize, uint64 nStartPos, CAICHHashAlgo* pHashAlg) 251{ 252 wxASSERT ( nSize <= EMBLOCKSIZE ); 253 CAICHHashTree* pToInsert = FindHash(nStartPos, nSize); 254 if (pToInsert == NULL) { // sanity 255 wxFAIL; 256 AddDebugLogLineN(logSHAHashSet, wxT("Critical Error: Failed to Insert SHA-HashBlock, FindHash() failed!")); 257 return; 258 } 259 260 //sanity 261 if (pToInsert->m_nBaseSize != EMBLOCKSIZE || pToInsert->m_nDataSize != nSize) { 262 wxFAIL; 263 AddDebugLogLineN(logSHAHashSet, wxT("Critical Error: Logical error on values in SetBlockHashFromData")); 264 return; 265 } 266 267 pHashAlg->Finish(pToInsert->m_Hash); 268 pToInsert->m_bHashValid = true; 269} 270 271 272bool CAICHHashTree::CreatePartRecoveryData(uint64 nStartPos, uint64 nSize, CFileDataIO* fileDataOut, uint32 wHashIdent, bool b32BitIdent) 273{ 274 wxCHECK(nStartPos + nSize <= m_nDataSize, false); 275 wxCHECK(nSize <= m_nDataSize, false); 276 277 if (nStartPos == 0 && nSize == m_nDataSize) { 278 // this is the searched part, now write all blocks of this part 279 // hashident for this level will be adjsuted by WriteLowestLevelHash 280 return WriteLowestLevelHashs(fileDataOut, wHashIdent, false, b32BitIdent); 281 } else if (m_nDataSize <= m_nBaseSize) { // sanity 282 // this is already the last level, cant go deeper 283 wxFAIL; 284 return false; 285 } else { 286 wHashIdent <<= 1; 287 wHashIdent |= (m_bIsLeftBranch) ? 1: 0; 288 289 uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0); 290 uint64 nLeft = ( ((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize; 291 uint64 nRight = m_nDataSize - nLeft; 292 if (m_pLeftTree == NULL || m_pRightTree == NULL) { 293 wxFAIL; 294 return false; 295 } 296 if (nStartPos < nLeft) { 297 if (nStartPos + nSize > nLeft || !m_pRightTree->m_bHashValid) { // sanity 298 wxFAIL; 299 return false; 300 } 301 m_pRightTree->WriteHash(fileDataOut, wHashIdent, b32BitIdent); 302 return m_pLeftTree->CreatePartRecoveryData(nStartPos, nSize, fileDataOut, wHashIdent, b32BitIdent); 303 } else { 304 nStartPos -= nLeft; 305 if (nStartPos + nSize > nRight || !m_pLeftTree->m_bHashValid) { // sanity 306 wxFAIL; 307 return false; 308 } 309 m_pLeftTree->WriteHash(fileDataOut, wHashIdent, b32BitIdent); 310 return m_pRightTree->CreatePartRecoveryData(nStartPos, nSize, fileDataOut, wHashIdent, b32BitIdent); 311 312 } 313 } 314} 315 316 317void CAICHHashTree::WriteHash(CFileDataIO* fileDataOut, uint32 wHashIdent, bool b32BitIdent) const 318{ 319 wxASSERT( m_bHashValid ); 320 wHashIdent <<= 1; 321 wHashIdent |= (m_bIsLeftBranch) ? 1: 0; 322 323 if (!b32BitIdent) { 324 wxASSERT( wHashIdent <= 0xFFFF ); 325 fileDataOut->WriteUInt16((uint16)wHashIdent); 326 } else { 327 fileDataOut->WriteUInt32(wHashIdent); 328 } 329 330 m_Hash.Write(fileDataOut); 331} 332 333 334// write lowest level hashs into file, ordered from left to right optional without identifier 335bool CAICHHashTree::WriteLowestLevelHashs(CFileDataIO* fileDataOut, uint32 wHashIdent, bool bNoIdent, bool b32BitIdent) const 336{ 337 wHashIdent <<= 1; 338 wHashIdent |= (m_bIsLeftBranch) ? 1: 0; 339 if (m_pLeftTree == NULL && m_pRightTree == NULL) { 340 if (m_nDataSize <= m_nBaseSize && m_bHashValid ) { 341 if (!bNoIdent && !b32BitIdent) { 342 wxASSERT( wHashIdent <= 0xFFFF ); 343 fileDataOut->WriteUInt16((uint16)wHashIdent); 344 } else if (!bNoIdent && b32BitIdent) { 345 fileDataOut->WriteUInt32(wHashIdent); 346 } 347 348 m_Hash.Write(fileDataOut); 349 return true; 350 } else { 351 wxFAIL; 352 return false; 353 } 354 } else if (m_pLeftTree == NULL || m_pRightTree == NULL) { 355 wxFAIL; 356 return false; 357 } else { 358 return m_pLeftTree->WriteLowestLevelHashs(fileDataOut, wHashIdent, bNoIdent, b32BitIdent) 359 && m_pRightTree->WriteLowestLevelHashs(fileDataOut, wHashIdent, bNoIdent, b32BitIdent); 360 } 361} 362 363// recover all low level hashs from given data. hashs are assumed to be ordered in left to right - no identifier used 364bool CAICHHashTree::LoadLowestLevelHashs(CFileDataIO* fileInput) 365{ 366 if (m_nDataSize <= m_nBaseSize) { // sanity 367 // lowest level, read hash 368 m_Hash.Read(fileInput); 369 m_bHashValid = true; 370 return true; 371 } else { 372 uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0); 373 uint64 nLeft = ( ((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize; 374 uint64 nRight = m_nDataSize - nLeft; 375 if (m_pLeftTree == NULL) { 376 m_pLeftTree = new CAICHHashTree(nLeft, true, (nLeft <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE); 377 } else { 378 wxASSERT( m_pLeftTree->m_nDataSize == nLeft ); 379 } 380 if (m_pRightTree == NULL) { 381 m_pRightTree = new CAICHHashTree(nRight, false, (nRight <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE); 382 } else { 383 wxASSERT( m_pRightTree->m_nDataSize == nRight ); 384 } 385 return m_pLeftTree->LoadLowestLevelHashs(fileInput) 386 && m_pRightTree->LoadLowestLevelHashs(fileInput); 387 } 388} 389 390 391// write the hash, specified by wHashIdent, with Data from fileInput. 392bool CAICHHashTree::SetHash(CFileDataIO* fileInput, uint32 wHashIdent, sint8 nLevel, bool bAllowOverwrite) 393{ 394 if (nLevel == (-1)) { 395 // first call, check how many level we need to go 396 uint8 i = 0; 397 for (; i != 32 && (wHashIdent & 0x80000000) == 0; ++i) { 398 wHashIdent <<= 1; 399 } 400 if (i > 31) { 401 AddDebugLogLineN(logSHAHashSet, wxT("CAICHHashTree::SetHash - found invalid HashIdent (0)")); 402 return false; 403 } else { 404 nLevel = 31 - i; 405 } 406 } 407 if (nLevel == 0) { 408 // this is the searched hash 409 if (m_bHashValid && !bAllowOverwrite) { 410 // not allowed to overwrite this hash, however move the filepointer by reading a hash 411 CAICHHash(file); 412 return true; 413 } 414 m_Hash.Read(fileInput); 415 m_bHashValid = true; 416 return true; 417 } else if (m_nDataSize <= m_nBaseSize) { // sanity 418 // this is already the last level, cant go deeper 419 wxFAIL; 420 return false; 421 } else { 422 // adjust ident to point the path to the next node 423 wHashIdent <<= 1; 424 nLevel--; 425 uint64 nBlocks = m_nDataSize / m_nBaseSize + ((m_nDataSize % m_nBaseSize != 0 )? 1:0); 426 uint64 nLeft = ( ((m_bIsLeftBranch) ? nBlocks+1:nBlocks) / 2)* m_nBaseSize; 427 uint64 nRight = m_nDataSize - nLeft; 428 if ((wHashIdent & 0x80000000) > 0) { 429 if (m_pLeftTree == NULL) { 430 m_pLeftTree = new CAICHHashTree(nLeft, true, (nLeft <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE); 431 } else { 432 wxASSERT( m_pLeftTree->m_nDataSize == nLeft ); 433 } 434 return m_pLeftTree->SetHash(fileInput, wHashIdent, nLevel); 435 } else { 436 if (m_pRightTree == NULL) { 437 m_pRightTree = new CAICHHashTree(nRight, false, (nRight <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE); 438 } else { 439 wxASSERT( m_pRightTree->m_nDataSize == nRight ); 440 } 441 return m_pRightTree->SetHash(fileInput, wHashIdent, nLevel); 442 } 443 } 444} 445 446 447///////////////////////////////////////////////////////////////////////////////////////// 448///CAICHUntrustedHash 449bool CAICHUntrustedHash::AddSigningIP(uint32 dwIP) 450{ 451 dwIP &= 0x00F0FFFF; // we use only the 20 most significant bytes for unique IPs 452 return m_adwIpsSigning.insert(dwIP).second; 453} 454 455 456 457///////////////////////////////////////////////////////////////////////////////////////// 458///CAICHHashSet 459CAICHHashSet::CAICHHashSet(CKnownFile* pOwner) 460 : m_pHashTree(0, true, PARTSIZE) 461{ 462 m_eStatus = AICH_EMPTY; 463 m_pOwner = pOwner; 464} 465 466CAICHHashSet::~CAICHHashSet(void) 467{ 468 FreeHashSet(); 469} 470 471bool CAICHHashSet::CreatePartRecoveryData(uint64 nPartStartPos, CFileDataIO* fileDataOut, bool bDbgDontLoad) 472{ 473 wxASSERT( m_pOwner ); 474 if (m_pOwner->IsPartFile() || m_eStatus != AICH_HASHSETCOMPLETE) { 475 wxFAIL; 476 return false; 477 } 478 if (m_pHashTree.m_nDataSize <= EMBLOCKSIZE) { 479 wxFAIL; 480 return false; 481 } 482 if (!bDbgDontLoad) { 483 if (!LoadHashSet()) { 484 AddDebugLogLineN(logSHAHashSet, 485 CFormat(wxT("Created RecoveryData error: failed to load hashset. File: %s")) % m_pOwner->GetFileName()); 486 SetStatus(AICH_ERROR); 487 return false; 488 } 489 } 490 bool bResult; 491 uint8 nLevel = 0; 492 uint32 nPartSize = min<uint64>(PARTSIZE, m_pOwner->GetFileSize()-nPartStartPos); 493 m_pHashTree.FindHash(nPartStartPos, nPartSize,&nLevel); 494 uint16 nHashsToWrite = (nLevel-1) + nPartSize/EMBLOCKSIZE + ((nPartSize % EMBLOCKSIZE != 0 )? 1:0); 495 const bool bUse32BitIdentifier = m_pOwner->IsLargeFile(); 496 497 if (bUse32BitIdentifier) { 498 fileDataOut->WriteUInt16(0); // no 16bit hashs to write 499 } 500 501 fileDataOut->WriteUInt16(nHashsToWrite); 502 uint64 nCheckFilePos = fileDataOut->GetPosition(); 503 if (m_pHashTree.CreatePartRecoveryData(nPartStartPos, nPartSize, fileDataOut, 0, bUse32BitIdentifier)) { 504 if (nHashsToWrite*(HASHSIZE+(bUse32BitIdentifier? 4u:2u)) != fileDataOut->GetPosition() - nCheckFilePos) { 505 wxFAIL; 506 AddDebugLogLineN( logSHAHashSet, 507 CFormat(wxT("Created RecoveryData has wrong length. File: %s")) % m_pOwner->GetFileName() ); 508 bResult = false; 509 SetStatus(AICH_ERROR); 510 } else { 511 bResult = true; 512 } 513 } else { 514 AddDebugLogLineN(logSHAHashSet, 515 CFormat(wxT("Failed to create RecoveryData for '%s'")) % m_pOwner->GetFileName()); 516 bResult = false; 517 SetStatus(AICH_ERROR); 518 } 519 if (!bUse32BitIdentifier) { 520 fileDataOut->WriteUInt16(0); // no 32bit hashs to write 521 } 522 523 if (!bDbgDontLoad) { 524 FreeHashSet(); 525 } 526 return bResult; 527} 528 529bool CAICHHashSet::ReadRecoveryData(uint64 nPartStartPos, CMemFile* fileDataIn) 530{ 531 if (/*eMule TODO !m_pOwner->IsPartFile() ||*/ !(m_eStatus == AICH_VERIFIED || m_eStatus == AICH_TRUSTED) ) { 532 wxFAIL; 533 return false; 534 } 535 536 /* V2 AICH Hash Packet: 537 <count1 uint16> 16bit-hashs-to-read 538 (<identifier uint16><hash HASHSIZE>)[count1] AICH hashs 539 <count2 uint16> 32bit-hashs-to-read 540 (<identifier uint32><hash HASHSIZE>)[count2] AICH hashs 541 */ 542 543 // at this time we check the recoverydata for the correct ammounts of hashs only 544 // all hash are then taken into the tree, depending on there hashidentifier (except the masterhash) 545 546 uint8 nLevel = 0; 547 uint32 nPartSize = min<uint64>(PARTSIZE, m_pOwner->GetFileSize()-nPartStartPos); 548 m_pHashTree.FindHash(nPartStartPos, nPartSize,&nLevel); 549 uint16 nHashsToRead = (nLevel-1) + nPartSize/EMBLOCKSIZE + ((nPartSize % EMBLOCKSIZE != 0 )? 1:0); 550 551 // read hashs with 16 bit identifier 552 uint16 nHashsAvailable = fileDataIn->ReadUInt16(); 553 if (fileDataIn->GetLength()-fileDataIn->GetPosition() < nHashsToRead*(HASHSIZE+2u) || (nHashsToRead != nHashsAvailable && nHashsAvailable != 0)) { 554 // this check is redunant, CSafememfile would catch such an error too 555 AddDebugLogLineN(logSHAHashSet, 556 CFormat(wxT("Failed to read RecoveryData for '%s' - Received datasize/amounts of hashs was invalid")) 557 % m_pOwner->GetFileName()); 558 return false; 559 } 560 for (uint32 i = 0; i != nHashsAvailable; i++) { 561 uint16 wHashIdent = fileDataIn->ReadUInt16(); 562 if (wHashIdent == 1 /*never allow masterhash to be overwritten*/ 563 || !m_pHashTree.SetHash(fileDataIn, wHashIdent,(-1), false)) 564 { 565 AddDebugLogLineN(logSHAHashSet, 566 CFormat(wxT("Failed to read RecoveryData for '%s' - Error when trying to read hash into tree")) 567 % m_pOwner->GetFileName()); 568 VerifyHashTree(true); // remove invalid hashes which we have already written 569 return false; 570 } 571 } 572 573 574 // read hashs with 32bit identifier 575 if (nHashsAvailable == 0 && fileDataIn->GetLength() - fileDataIn->GetPosition() >= 2) { 576 nHashsAvailable = fileDataIn->ReadUInt16(); 577 if (fileDataIn->GetLength()-fileDataIn->GetPosition() < nHashsToRead*(HASHSIZE+4u) || (nHashsToRead != nHashsAvailable && nHashsAvailable != 0)) { 578 // this check is redunant, CSafememfile would catch such an error too 579// TODO: theApp->QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("Failed to read RecoveryData for %s - Received datasize/amounts of hashs was invalid (2)"), m_pOwner->GetFileName() ); 580 return false; 581 } 582 583// TODO: DEBUG_ONLY( theApp->QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("read RecoveryData for %s - Received packet with %u 32bit hash identifiers)"), m_pOwner->GetFileName(), nHashsAvailable ) ); 584 for (uint32 i = 0; i != nHashsToRead; i++) { 585 uint32 wHashIdent = fileDataIn->ReadUInt32(); 586 if (wHashIdent == 1 /*never allow masterhash to be overwritten*/ 587 || wHashIdent > 0x400000 588 || !m_pHashTree.SetHash(fileDataIn, wHashIdent,(-1), false)) 589 { 590// TODO: theApp->QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("Failed to read RecoveryData for %s - Error when trying to read hash into tree (2)"), m_pOwner->GetFileName() ); 591 VerifyHashTree(true); // remove invalid hashes which we have already written 592 return false; 593 } 594 } 595 } 596 597 if (nHashsAvailable == 0) { 598// TODO: theApp->QueueDebugLogLine(/*DLP_VERYHIGH,*/ false, _T("Failed to read RecoveryData for %s - Packet didn't contained any hashs"), m_pOwner->GetFileName() ); 599 return false; 600 } 601 602 603 if (VerifyHashTree(true)) { 604 // some final check if all hashs we wanted are there 605 for (uint32 nPartPos = 0; nPartPos < nPartSize; nPartPos += EMBLOCKSIZE) { 606 CAICHHashTree* phtToCheck = m_pHashTree.FindHash(nPartStartPos+nPartPos, min<uint64>(EMBLOCKSIZE, nPartSize-nPartPos)); 607 if (phtToCheck == NULL || !phtToCheck->m_bHashValid) { 608 AddDebugLogLineN(logSHAHashSet, 609 CFormat(wxT("Failed to read RecoveryData for '%s' - Error while verifying presence of all lowest level hashes")) 610 % m_pOwner->GetFileName()); 611 return false; 612 } 613 } 614 // all done 615 return true; 616 } else { 617 AddDebugLogLineN(logSHAHashSet, 618 CFormat(wxT("Failed to read RecoveryData for '%s' - Verifying received hashtree failed")) 619 % m_pOwner->GetFileName()); 620 return false; 621 } 622} 623 624// this function is only allowed to be called right after successfully calculating the hashset (!) 625// will delete the hashset, after saving to free the memory 626bool CAICHHashSet::SaveHashSet() 627{ 628 if (m_eStatus != AICH_HASHSETCOMPLETE) { 629 wxFAIL; 630 return false; 631 } 632 if ( !m_pHashTree.m_bHashValid || m_pHashTree.m_nDataSize != m_pOwner->GetFileSize()) { 633 wxFAIL; 634 return false; 635 } 636 637 638 try { 639 const wxString fullpath = theApp->ConfigDir + KNOWN2_MET_FILENAME; 640 const bool exists = wxFile::Exists(fullpath); 641 642 CFile file(fullpath, exists ? CFile::read_write : CFile::write); 643 if (!file.IsOpened()) { 644 AddDebugLogLineC(logSHAHashSet, wxT("Failed to save HashSet: opening met file failed!")); 645 return false; 646 } 647 648 uint64 nExistingSize = file.GetLength(); 649 if (nExistingSize) { 650 uint8 header = file.ReadUInt8(); 651 if (header != KNOWN2_MET_VERSION) { 652 AddDebugLogLineC(logSHAHashSet, wxT("Saving failed: Current file is not a met-file!")); 653 return false; 654 } 655 656 AddDebugLogLineN(logSHAHashSet, CFormat(wxT("Met file is version 0x%2.2x.")) % header); 657 } else { 658 file.WriteUInt8(KNOWN2_MET_VERSION); 659 // Update the recorded size, in order for the sanity check below to work. 660 nExistingSize += 1; 661 } 662 663 // first we check if the hashset we want to write is already stored 664 CAICHHash CurrentHash; 665 while (file.GetPosition() < nExistingSize) { 666 CurrentHash.Read(&file); 667 if (m_pHashTree.m_Hash == CurrentHash) { 668 // this hashset if already available, no need to save it again 669 return true; 670 } 671 uint32 nHashCount = file.ReadUInt32(); 672 if (file.GetPosition() + nHashCount*HASHSIZE > nExistingSize) { 673 AddDebugLogLineC(logSHAHashSet, wxT("Saving failed: File contains fewer entries than specified!")); 674 return false; 675 } 676 // skip the rest of this hashset 677 file.Seek(nHashCount*HASHSIZE, wxFromCurrent); 678 } 679 680 // write hashset 681 m_pHashTree.m_Hash.Write(&file); 682 uint32 nHashCount = (PARTSIZE/EMBLOCKSIZE + ((PARTSIZE % EMBLOCKSIZE != 0)? 1 : 0)) * (m_pHashTree.m_nDataSize/PARTSIZE); 683 if (m_pHashTree.m_nDataSize % PARTSIZE != 0) { 684 nHashCount += (m_pHashTree.m_nDataSize % PARTSIZE)/EMBLOCKSIZE + (((m_pHashTree.m_nDataSize % PARTSIZE) % EMBLOCKSIZE != 0)? 1 : 0); 685 } 686 file.WriteUInt32(nHashCount); 687 if (!m_pHashTree.WriteLowestLevelHashs(&file, 0, true, true)) { 688 // thats bad... really 689 file.SetLength(nExistingSize); 690 AddDebugLogLineC(logSHAHashSet, wxT("Failed to save HashSet: WriteLowestLevelHashs() failed!")); 691 return false; 692 } 693 if (file.GetLength() != nExistingSize + (nHashCount+1)*HASHSIZE + 4) { 694 // thats even worse 695 file.SetLength(nExistingSize); 696 AddDebugLogLineC(logSHAHashSet, wxT("Failed to save HashSet: Calculated and real size of hashset differ!")); 697 return false; 698 } 699 AddDebugLogLineN(logSHAHashSet, CFormat(wxT("Successfully saved eMuleAC Hashset, %u Hashs + 1 Masterhash written")) % nHashCount); 700 } catch (const CSafeIOException& e) { 701 AddDebugLogLineC(logSHAHashSet, wxT("IO error while saving AICH HashSet: ") + e.what()); 702 return false; 703 } 704 705 FreeHashSet(); 706 return true; 707} 708 709 710bool CAICHHashSet::LoadHashSet() 711{ 712 if (m_eStatus != AICH_HASHSETCOMPLETE) { 713 wxFAIL; 714 return false; 715 } 716 if ( !m_pHashTree.m_bHashValid || m_pHashTree.m_nDataSize != m_pOwner->GetFileSize() || m_pHashTree.m_nDataSize == 0) { 717 wxFAIL; 718 return false; 719 } 720 wxString fullpath = theApp->ConfigDir + KNOWN2_MET_FILENAME; 721 CFile file(fullpath, CFile::read); 722 if (!file.IsOpened()) { 723 if (wxFileExists(fullpath)) { 724 wxString strError(wxT("Failed to load ") KNOWN2_MET_FILENAME wxT(" file")); 725 AddDebugLogLineC(logSHAHashSet, strError); 726 } 727 return false; 728 } 729 730 try { 731 uint8 header = file.ReadUInt8(); 732 if (header != KNOWN2_MET_VERSION) { 733 AddDebugLogLineC(logSHAHashSet, wxT("Loading failed: Current file is not a met-file!")); 734 return false; 735 } 736 737 CAICHHash CurrentHash; 738 uint64 nExistingSize = file.GetLength(); 739 uint32 nHashCount; 740 while (file.GetPosition() < nExistingSize) { 741 CurrentHash.Read(&file); 742 if (m_pHashTree.m_Hash == CurrentHash) { 743 // found Hashset 744 uint32 nExpectedCount = (PARTSIZE/EMBLOCKSIZE + ((PARTSIZE % EMBLOCKSIZE != 0)? 1 : 0)) * (m_pHashTree.m_nDataSize/PARTSIZE); 745 if (m_pHashTree.m_nDataSize % PARTSIZE != 0) { 746 nExpectedCount += (m_pHashTree.m_nDataSize % PARTSIZE)/EMBLOCKSIZE + (((m_pHashTree.m_nDataSize % PARTSIZE) % EMBLOCKSIZE != 0)? 1 : 0); 747 } 748 nHashCount = file.ReadUInt32(); 749 if (nHashCount != nExpectedCount) { 750 AddDebugLogLineC(logSHAHashSet, wxT("Failed to load HashSet: Available Hashs and expected hashcount differ!")); 751 return false; 752 } 753 if (!m_pHashTree.LoadLowestLevelHashs(&file)) { 754 AddDebugLogLineC(logSHAHashSet, wxT("Failed to load HashSet: LoadLowestLevelHashs failed!")); 755 return false; 756 } 757 if (!ReCalculateHash(false)) { 758 AddDebugLogLineC(logSHAHashSet, wxT("Failed to load HashSet: Calculating loaded hashs failed!")); 759 return false; 760 } 761 if (CurrentHash != m_pHashTree.m_Hash) { 762 AddDebugLogLineC(logSHAHashSet, wxT("Failed to load HashSet: Calculated Masterhash differs from given Masterhash - hashset corrupt!")); 763 return false; 764 } 765 return true; 766 } 767 nHashCount = file.ReadUInt32(); 768 if (file.GetPosition() + nHashCount*HASHSIZE > nExistingSize) { 769 AddDebugLogLineC(logSHAHashSet, wxT("Saving failed: File contains fewer entries than specified!")); 770 return false; 771 } 772 // skip the rest of this hashset 773 file.Seek(nHashCount*HASHSIZE, wxFromCurrent); 774 } 775 AddDebugLogLineC(logSHAHashSet, wxT("Failed to load HashSet: HashSet not found!")); 776 } catch (const CSafeIOException& e) { 777 AddDebugLogLineC(logSHAHashSet, wxT("IO error while loading AICH HashSet: ") + e.what()); 778 } 779 780 return false; 781} 782 783// delete the hashset except the masterhash (we dont keep aich hashsets in memory to save ressources) 784void CAICHHashSet::FreeHashSet() 785{ 786 if (m_pHashTree.m_pLeftTree) { 787 delete m_pHashTree.m_pLeftTree; 788 m_pHashTree.m_pLeftTree = NULL; 789 } 790 if (m_pHashTree.m_pRightTree) { 791 delete m_pHashTree.m_pRightTree; 792 m_pHashTree.m_pRightTree = NULL; 793 } 794} 795 796void CAICHHashSet::SetMasterHash(const CAICHHash& Hash, EAICHStatus eNewStatus) 797{ 798 m_pHashTree.m_Hash = Hash; 799 m_pHashTree.m_bHashValid = true; 800 SetStatus(eNewStatus); 801} 802 803CAICHHashAlgo* CAICHHashSet::GetNewHashAlgo() 804{ 805 return new CSHA(); 806} 807 808bool CAICHHashSet::ReCalculateHash(bool bDontReplace) 809{ 810 CAICHHashAlgo* hashalg = GetNewHashAlgo(); 811 bool bResult = m_pHashTree.ReCalculateHash(hashalg, bDontReplace); 812 delete hashalg; 813 return bResult; 814} 815 816bool CAICHHashSet::VerifyHashTree(bool bDeleteBadTrees) 817{ 818 CAICHHashAlgo* hashalg = GetNewHashAlgo(); 819 bool bResult = m_pHashTree.VerifyHashTree(hashalg, bDeleteBadTrees); 820 delete hashalg; 821 return bResult; 822} 823 824 825void CAICHHashSet::SetFileSize(uint64 nSize) 826{ 827 m_pHashTree.m_nDataSize = nSize; 828 m_pHashTree.m_nBaseSize = (nSize <= PARTSIZE) ? EMBLOCKSIZE : PARTSIZE; 829} 830 831 832void CAICHHashSet::UntrustedHashReceived(const CAICHHash& Hash, uint32 dwFromIP) 833{ 834 switch(GetStatus()) { 835 case AICH_EMPTY: 836 case AICH_UNTRUSTED: 837 case AICH_TRUSTED: 838 break; 839 default: 840 return; 841 } 842 bool bFound = false; 843 bool bAdded = false; 844 for (uint32 i = 0; i < m_aUntrustedHashs.size(); ++i) { 845 if (m_aUntrustedHashs[i].m_Hash == Hash) { 846 bAdded = m_aUntrustedHashs[i].AddSigningIP(dwFromIP); 847 bFound = true; 848 break; 849 } 850 } 851 if (!bFound) { 852 bAdded = true; 853 CAICHUntrustedHash uhToAdd; 854 uhToAdd.m_Hash = Hash; 855 uhToAdd.AddSigningIP(dwFromIP); 856 m_aUntrustedHashs.push_back(uhToAdd); 857 } 858 859 uint32 nSigningIPsTotal = 0; // unique clients who send us a hash 860 int nMostTrustedPos = (-1); // the hash which most clients send us 861 uint32 nMostTrustedIPs = 0; 862 for (uint32 i = 0; i < (uint32)m_aUntrustedHashs.size(); ++i) { 863 nSigningIPsTotal += m_aUntrustedHashs[i].m_adwIpsSigning.size(); 864 if ((uint32)m_aUntrustedHashs[i].m_adwIpsSigning.size() > nMostTrustedIPs) { 865 nMostTrustedIPs = m_aUntrustedHashs[i].m_adwIpsSigning.size(); 866 nMostTrustedPos = i; 867 } 868 } 869 if (nMostTrustedPos == (-1) || nSigningIPsTotal == 0) { 870 wxFAIL; 871 return; 872 } 873 // the check if we trust any hash 874 if ( thePrefs::IsTrustingEveryHash() || 875 (nMostTrustedIPs >= MINUNIQUEIPS_TOTRUST && (100 * nMostTrustedIPs)/nSigningIPsTotal >= MINPERCENTAGE_TOTRUST)) { 876 //trusted 877 AddDebugLogLineN(logSHAHashSet, 878 CFormat(wxT("AICH Hash received (%sadded), We have now %u hash(es) from %u unique IP(s). ") 879 wxT("We trust the Hash %s from %u client(s) (%u%%). File: %s")) 880 % (bAdded ? wxT("") : wxT("not ")) 881 % m_aUntrustedHashs.size() 882 % nSigningIPsTotal 883 % m_aUntrustedHashs[nMostTrustedPos].m_Hash.GetString() 884 % nMostTrustedIPs 885 % ((100 * nMostTrustedIPs) / nSigningIPsTotal) 886 % m_pOwner->GetFileName()); 887 888 SetStatus(AICH_TRUSTED); 889 if (!HasValidMasterHash() || GetMasterHash() != m_aUntrustedHashs[nMostTrustedPos].m_Hash) { 890 SetMasterHash(m_aUntrustedHashs[nMostTrustedPos].m_Hash, AICH_TRUSTED); 891 FreeHashSet(); 892 } 893 } else { 894 // untrusted 895 AddDebugLogLineN(logSHAHashSet, 896 CFormat(wxT("AICH Hash received (%sadded), We have now %u hash(es) from %u unique IP(s). ") 897 wxT("Best Hash %s from %u clients (%u%%) - but we don't trust it yet. File: %s")) 898 % (bAdded ? wxT(""): wxT("not ")) 899 % m_aUntrustedHashs.size() 900 % nSigningIPsTotal 901 % m_aUntrustedHashs[nMostTrustedPos].m_Hash.GetString() 902 % nMostTrustedIPs 903 % ((100 * nMostTrustedIPs) / nSigningIPsTotal) 904 % m_pOwner->GetFileName()); 905 906 SetStatus(AICH_UNTRUSTED); 907 if (!HasValidMasterHash() || GetMasterHash() != m_aUntrustedHashs[nMostTrustedPos].m_Hash) { 908 SetMasterHash(m_aUntrustedHashs[nMostTrustedPos].m_Hash, AICH_UNTRUSTED); 909 FreeHashSet(); 910 } 911 } 912 if (bAdded) {} // get rid of unused variable warning 913} 914 915 916void CAICHHashSet::ClientAICHRequestFailed(CUpDownClient* pClient) 917{ 918 pClient->SetReqFileAICHHash(NULL); 919 CAICHRequestedData data = GetAICHReqDetails(pClient); 920 RemoveClientAICHRequest(pClient); 921 if (data.m_pClient.GetClient() != pClient) { 922 return; 923 } 924 if( theApp->downloadqueue->IsPartFile(data.m_pPartFile)) { 925 AddDebugLogLineN(logSHAHashSet, 926 CFormat(wxT("AICH Request failed, Trying to ask another client (File: '%s', Part: %u, Client '%s'")) 927 % data.m_pPartFile->GetFileName() % data.m_nPart % pClient->GetClientFullInfo()); 928 data.m_pPartFile->RequestAICHRecovery(data.m_nPart); 929 } 930} 931 932 933void CAICHHashSet::RemoveClientAICHRequest(const CUpDownClient* pClient) 934{ 935 for (CAICHRequestedDataList::iterator it = m_liRequestedData.begin();it != m_liRequestedData.end(); ++it) { 936 if (it->m_pClient.GetClient() == pClient) { 937 m_liRequestedData.erase(it); 938 return; 939 } 940 } 941 wxFAIL; 942} 943 944bool CAICHHashSet::IsClientRequestPending(const CPartFile* pForFile, uint16 nPart) 945{ 946 for (CAICHRequestedDataList::iterator it = m_liRequestedData.begin();it != m_liRequestedData.end(); ++it) { 947 if (it->m_pPartFile == pForFile && it->m_nPart == nPart) { 948 return true; 949 } 950 } 951 return false; 952} 953 954CAICHRequestedData CAICHHashSet::GetAICHReqDetails(const CUpDownClient* pClient) 955{ 956 for (CAICHRequestedDataList::iterator it = m_liRequestedData.begin();it != m_liRequestedData.end(); ++it) { 957 if (it->m_pClient.GetClient() == pClient) { 958 return *(it); 959 } 960 } 961 wxFAIL; 962 CAICHRequestedData empty; 963 return empty; 964} 965 966bool CAICHHashSet::IsPartDataAvailable(uint64 nPartStartPos) 967{ 968 if (!(m_eStatus == AICH_VERIFIED || m_eStatus == AICH_TRUSTED || m_eStatus == AICH_HASHSETCOMPLETE) ) { 969 wxFAIL; 970 return false; 971 } 972 uint64 nPartSize = min<uint64>(PARTSIZE, m_pOwner->GetFileSize()-nPartStartPos); 973 for (uint64 nPartPos = 0; nPartPos < nPartSize; nPartPos += EMBLOCKSIZE) { 974 CAICHHashTree* phtToCheck = m_pHashTree.FindHash(nPartStartPos+nPartPos, min<uint64>(EMBLOCKSIZE, nPartSize-nPartPos)); 975 if (phtToCheck == NULL || !phtToCheck->m_bHashValid) { 976 return false; 977 } 978 } 979 return true; 980} 981 982// VC++ defines Assert as ASSERT. VC++ also defines VERIFY MACRO, which is the equivalent of ASSERT but also works in Released builds. 983 984#define VERIFY(x) wxASSERT(x) 985 986void CAICHHashSet::DbgTest() 987{ 988#ifdef _DEBUG 989 //define TESTSIZE 4294567295 990 uint8 maxLevel = 0; 991 uint32 cHash = 1; 992 uint8 curLevel = 0; 993 //uint32 cParts = 0; 994 maxLevel = 0; 995/* CAICHHashTree* pTest = new CAICHHashTree(TESTSIZE, true, 9728000); 996 for (uint64 i = 0; i+9728000 < TESTSIZE; i += 9728000) { 997 CAICHHashTree* pTest2 = new CAICHHashTree(9728000, true, EMBLOCKSIZE); 998 pTest->ReplaceHashTree(i, 9728000, &pTest2); 999 cParts++; 1000 } 1001 CAICHHashTree* pTest2 = new CAICHHashTree(TESTSIZE-i, true, EMBLOCKSIZE); 1002 pTest->ReplaceHashTree(i, (TESTSIZE-i), &pTest2); 1003 cParts++; 1004*/ 1005#define TESTSIZE m_pHashTree.m_nDataSize 1006 if (m_pHashTree.m_nDataSize <= EMBLOCKSIZE) { 1007 return; 1008 } 1009 CAICHHashSet TestHashSet(m_pOwner); 1010 TestHashSet.SetFileSize(m_pOwner->GetFileSize()); 1011 TestHashSet.SetMasterHash(GetMasterHash(), AICH_VERIFIED); 1012 CMemFile file; 1013 uint64 i; 1014 for (i = 0; i+9728000 < TESTSIZE; i += 9728000) { 1015 VERIFY( CreatePartRecoveryData(i, &file) ); 1016 1017 /*uint32 nRandomCorruption = (rand() * rand()) % (file.GetLength()-4); 1018 file.Seek(nRandomCorruption, CFile::begin); 1019 file.Write(&nRandomCorruption, 4);*/ 1020 1021 file.Seek(0,wxFromStart); 1022 VERIFY( TestHashSet.ReadRecoveryData(i, &file) ); 1023 file.Seek(0,wxFromStart); 1024 TestHashSet.FreeHashSet(); 1025 uint32 j; 1026 for (j = 0; j+EMBLOCKSIZE < 9728000; j += EMBLOCKSIZE) { 1027 VERIFY( m_pHashTree.FindHash(i+j, EMBLOCKSIZE, &curLevel) ); 1028 //TRACE(wxT("%u - %s\r\n"), cHash, m_pHashTree.FindHash(i+j, EMBLOCKSIZE, &curLevel)->m_Hash.GetString()); 1029 maxLevel = max(curLevel, maxLevel); 1030 curLevel = 0; 1031 cHash++; 1032 } 1033 VERIFY( m_pHashTree.FindHash(i+j, 9728000-j, &curLevel) ); 1034 //TRACE(wxT("%u - %s\r\n"), cHash, m_pHashTree.FindHash(i+j, 9728000-j, &curLevel)->m_Hash.GetString()); 1035 maxLevel = max(curLevel, maxLevel); 1036 curLevel = 0; 1037 cHash++; 1038 1039 } 1040 VERIFY( CreatePartRecoveryData(i, &file) ); 1041 file.Seek(0,wxFromStart); 1042 VERIFY( TestHashSet.ReadRecoveryData(i, &file) ); 1043 file.Seek(0,wxFromStart); 1044 TestHashSet.FreeHashSet(); 1045 for (uint64 j = 0; j+EMBLOCKSIZE < TESTSIZE-i; j += EMBLOCKSIZE) { 1046 VERIFY( m_pHashTree.FindHash(i+j, EMBLOCKSIZE, &curLevel) ); 1047 //TRACE(wxT("%u - %s\r\n"), cHash,m_pHashTree.FindHash(i+j, EMBLOCKSIZE, &curLevel)->m_Hash.GetString()); 1048 maxLevel = max(curLevel, maxLevel); 1049 curLevel = 0; 1050 cHash++; 1051 } 1052 //VERIFY( m_pHashTree.FindHash(i+j, (TESTSIZE-i)-j, &curLevel) ); 1053 //TRACE(wxT("%u - %s\r\n"), cHash,m_pHashTree.FindHash(i+j, (TESTSIZE-i)-j, &curLevel)->m_Hash.GetString()); 1054 maxLevel = max(curLevel, maxLevel); 1055#endif 1056} 1057// File_checked_for_headers 1058