src/kademlia/routing/RoutingZone.cpp

   1 //
   2 // This file is part of aMule Project
   3 //
   4 // Copyright (c) 2004-2008 Angel Vidal (Kry) ( kry@amule.org )
   5 // Copyright (c) 2004-2008 aMule Project ( http://www.amule-project.net )
   6 // Copyright (C)2003 Barry Dunne (http://www.emule-project.net)
   7
   8 // This program is free software; you can redistribute it and/or
   9 // modify it under the terms of the GNU General Public License
  10 // as published by the Free Software Foundation; either
  11 // version 2 of the License, or (at your option) any later version.
  12
  13 // This program is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17
  18 // You should have received a copy of the GNU General Public License
  19 // along with this program; if not, write to the Free Software
  20 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  21
  22 // This work is based on the java implementation of the Kademlia protocol.
  23 // Kademlia: Peer-to-peer routing based on the XOR metric
  24 // Copyright (C) 2002  Petar Maymounkov [petar@post.harvard.edu]
  25 // http://kademlia.scs.cs.nyu.edu
  26
  27 // Note To Mods //
  28 /*
  29 Please do not change anything here and release it..
  30 There is going to be a new forum created just for the Kademlia side of the client..
  31 If you feel there is an error or a way to improve something, please
  32 post it in the forum first and let us look at it.. If it is a real improvement,
  33 it will be added to the offical client.. Changing something without knowing
  34 what all it does can cause great harm to the network if released in mass form..
  35 Any mod that changes anything within the Kademlia side will not be allowed to advertise
  36 there client on the eMule forum..
  37 */
  38
  39 /**
  40  * The *Zone* is just a node in a binary tree of *Zone*s.
  41  * Each zone is either an internal node or a leaf node.
  42  * Internal nodes have "bin == null" and "subZones[i] != null",
  43  * leaf nodes have "subZones[i] == null" and "bin != null".
  44  *
  45  * All key unique id's are relative to the center (self), which
  46  * is considered to be 000..000
  47  */
  48 #include "RoutingZone.h"
  49
  50 #include <protocol/kad/Client2Client/UDP.h>
  51 #include <common/Macros.h>
  52
  53 #include "Contact.h"
  54 #include "RoutingBin.h"
  55 #include "../kademlia/SearchManager.h"
  56 #include "../kademlia/Defines.h"
  57 #include "../net/KademliaUDPListener.h"
  58 #include "../../amule.h"
  59 #include "../../CFile.h"
  60 #include "../../Logger.h"
  61 #include "../../NetworkFunctions.h"
  62
  63 #include <cmath>
  64
  65 ////////////////////////////////////////
  66 using namespace Kademlia;
  67 ////////////////////////////////////////
  68
  69 // This is just a safety precaution
  70 #define CONTACT_FILE_LIMIT 5000
  71
  72 wxString CRoutingZone::m_filename;
  73 CUInt128 CRoutingZone::me((uint32)0);
  74
  75 CRoutingZone::CRoutingZone()
  76 {
  77         // Can only create routing zone after prefs
  78         me = CKademlia::GetPrefs()->GetKadID();
  79         m_filename = theApp->ConfigDir + wxT("nodes.dat");
  80         CUInt128 zero((uint32)0);
  81         Init(NULL, 0, zero);
  82 }
  83
  84 CRoutingZone::CRoutingZone(CRoutingZone *super_zone, int level, const CUInt128 &zone_index)
  85 {
  86         Init(super_zone, level, zone_index);
  87 }
  88
  89 void CRoutingZone::Init(CRoutingZone *super_zone, int level, const CUInt128 &zone_index)
  90 {
  91         m_superZone = super_zone;
  92         m_level = level;
  93         m_zoneIndex = zone_index;
  94         m_subZones[0] = NULL;
  95         m_subZones[1] = NULL;
  96         m_bin = new CRoutingBin();
  97
  98         m_nextSmallTimer = time(NULL) + m_zoneIndex.Get32BitChunk(3);
  99
 100         if ((m_superZone == NULL) && (m_filename.Length() > 0)) {
 101                 ReadFile();
 102         }
 103
 104         dirty = false;
 105
 106         StartTimer();
 107 }
 108
 109 CRoutingZone::~CRoutingZone()
 110 {
 111         if ((m_superZone == NULL) && (m_filename.Length() > 0)) {
 112                 WriteFile();
 113         }
 114         if (IsLeaf()) {
 115                 delete m_bin;
 116         } else {
 117                 delete m_subZones[0];
 118                 delete m_subZones[1];
 119         }
 120 }
 121
 122 void CRoutingZone::ReadFile(void)
 123 {
 124         try {
 125                 uint32 numContacts = 0;
 126                 CFile file;
 127                 if (CPath::FileExists(m_filename) && file.Open(m_filename, CFile::read)) {
 128                         numContacts = file.ReadUInt32();
 129                         for (uint32 i = 0; i < numContacts; i++) {
 130                                 CUInt128 id = file.ReadUInt128();
 131                                 uint32 ip = file.ReadUInt32();
 132                                 uint16 udpPort = file.ReadUInt16();
 133                                 uint16 tcpPort = file.ReadUInt16();
 134                                 byte type = file.ReadUInt8();
 135                                 if(IsGoodIPPort(wxUINT32_SWAP_ALWAYS(ip),udpPort)) {
 136                                         if( type < 4) {
 137                                                 Add(id, ip, udpPort, tcpPort, type);
 138                                         }
 139                                 }
 140                         }
 141                         AddLogLineM( false, wxString::Format(wxPLURAL("Read %u Kad contact", "Read %u Kad contacts", numContacts), numContacts));
 142                 }
 143                 if (numContacts == 0) {
 144                         AddDebugLogLineM( false, logKadRouting, wxT("Error while reading Kad contacts - 0 entries"));
 145                 }
 146         } catch (const CSafeIOException& e) {
 147                 AddDebugLogLineM(false, logKadRouting, wxT("IO error in CRoutingZone::readFile: ") + e.what());
 148         }
 149 }
 150
 151 void CRoutingZone::WriteFile(void)
 152 {
 153         try {
 154                 unsigned int count = 0;
 155                 CContact *c;
 156                 CFile file;
 157                 if (file.Open(m_filename, CFile::write)) {
 158                         ContactList contacts;
 159                         GetBootstrapContacts(&contacts, 200);
 160                         file.WriteUInt32((uint32)std::min((int)contacts.size(), CONTACT_FILE_LIMIT));
 161                         ContactList::const_iterator it;
 162                         for (it = contacts.begin(); it != contacts.end(); ++it) {
 163                                 count++;
 164                                 c = *it;
 165                                 file.WriteUInt128(c->GetClientID());
 166                                 file.WriteUInt32(c->GetIPAddress());
 167                                 file.WriteUInt16(c->GetUDPPort());
 168                                 file.WriteUInt16(c->GetTCPPort());
 169                                 file.WriteUInt8(c->GetType());
 170                                 if (count == CONTACT_FILE_LIMIT) {
 171                                         break;
 172                                 }
 173                         }
 174                 }
 175                 AddDebugLogLineM( false, logKadRouting, wxString::Format(wxT("Wrote %d contacts to file."), count));
 176         } catch (const CIOFailureException& e) {
 177                 AddDebugLogLineM(true, logKadRouting, wxT("IO failure in CRoutingZone::writeFile: ") + e.what());
 178         }
 179 }
 180
 181 bool CRoutingZone::CanSplit(void) const
 182 {
 183         if (m_level >= 127) {
 184                 return false;
 185         }
 186
 187         /* Check if we are close to the center */
 188         if ( (m_zoneIndex < KK || m_level < KBASE) && m_bin->GetSize() == K) {
 189                 return true;
 190         }
 191         return false;
 192 }
 193
 194 bool CRoutingZone::Add(const CUInt128 &id, uint32 ip, uint16 port, uint16 tport, byte type)
 195 {
 196
 197         //AddDebugLogLineM(false, logKadMain, wxT("Adding a contact (routing) with ip ") + Uint32_16toStringIP_Port(wxUINT32_SWAP_ALWAYS(ip),port));
 198
 199         if (id == me) {
 200                 return false;
 201         }
 202
 203         CUInt128 distance(me);
 204         distance.XOR(id);
 205
 206         return AddByDistance(distance,id,ip,port,tport,type);
 207 }
 208
 209 bool CRoutingZone::AddByDistance(const CUInt128 &distance, const CUInt128 &id, uint32 ip, uint16 port, uint16 tport, byte type) {
 210
 211         bool retVal = false;
 212         CContact *c = NULL;
 213
 214         if (!IsLeaf()) {
 215                 retVal = m_subZones[distance.GetBitNumber(m_level)]->AddByDistance(distance, id, ip, port, tport, type);
 216         } else {
 217                 c = m_bin->GetContact(id);
 218                 if (c != NULL) {
 219                         c->SetIPAddress(ip);
 220                         c->SetUDPPort(port);
 221                         c->SetTCPPort(tport);
 222                         retVal = true;
 223                 } else if (m_bin->GetRemaining() > 0) {
 224                         c = new CContact(id, ip, port, tport);
 225                         retVal = m_bin->Add(c,false);
 226                 } else if (CanSplit()) {
 227                         Split();
 228                         retVal = m_subZones[distance.GetBitNumber(m_level)]->AddByDistance(distance, id, ip, port, tport, type);
 229                 }/* else {
 230                         Merge();
 231                         c = new CContact(id, ip, port, tport);
 232                         retVal = m_bin->Add(c,false);
 233                 }*/
 234
 235                 if (!retVal) {
 236                         if (c != NULL) {
 237                                 delete c;
 238                         }
 239                 }
 240         }
 241
 242         return retVal;
 243 }
 244
 245 void CRoutingZone::Remove(const CUInt128 &id) {
 246         CUInt128 distance(me);
 247         distance.XOR(id);
 248         if (!IsLeaf()) {
 249                 m_subZones[distance.GetBitNumber(m_level)]->Remove(id);
 250         } else {
 251                 CContact *c = m_bin->GetContact(id);
 252                 if (c) {
 253                         m_bin->Remove(c);
 254                 }
 255         }
 256 }
 257
 258 void CRoutingZone::SetAlive(uint32 ip, uint16 port)
 259 {
 260         if (IsLeaf()) {
 261                 m_bin->SetAlive(ip, port);
 262         } else {
 263                 m_subZones[0]->SetAlive(ip, port);
 264                 m_subZones[1]->SetAlive(ip, port);
 265         }
 266 }
 267
 268 CContact *CRoutingZone::GetContact(const CUInt128 &id) const
 269 {
 270         if (IsLeaf()) {
 271                 return m_bin->GetContact(id);
 272         } else {
 273                 return m_subZones[id.GetBitNumber(m_level)]->GetContact(id);
 274         }
 275 }
 276
 277 void CRoutingZone::GetClosestTo(uint32 maxType, const CUInt128 &target, const CUInt128 &distance, uint32 maxRequired, ContactMap *result, bool emptyFirst, bool inUse) const
 278 {
 279         // If leaf zone, do it here
 280         if (IsLeaf()) {
 281                 m_bin->GetClosestTo(maxType, target, maxRequired, result, emptyFirst, inUse);
 282                 return;
 283         }
 284
 285         // otherwise, recurse in the closer-to-the-target subzone first
 286         int closer = distance.GetBitNumber(m_level);
 287         m_subZones[closer]->GetClosestTo(maxType, target, distance, maxRequired, result, emptyFirst, inUse);
 288
 289         // if still not enough tokens found, recurse in the other subzone too
 290         if (result->size() < maxRequired) {
 291                 m_subZones[1-closer]->GetClosestTo(maxType, target, distance, maxRequired, result, false, inUse);
 292         }
 293 }
 294
 295 void CRoutingZone::GetAllEntries(ContactList *result, bool emptyFirst)
 296 {
 297         if (IsLeaf()) {
 298                 m_bin->GetEntries(result, emptyFirst);
 299         } else {
 300                 m_subZones[0]->GetAllEntries(result, emptyFirst);
 301                 m_subZones[1]->GetAllEntries(result, false);
 302         }
 303 }
 304
 305 void CRoutingZone::TopDepth(int depth, ContactList *result, bool emptyFirst)
 306 {
 307         if (IsLeaf()) {
 308                 m_bin->GetEntries(result, emptyFirst);
 309         } else if (depth <= 0) {
 310                 RandomBin(result, emptyFirst);
 311         } else {
 312                 m_subZones[0]->TopDepth(depth-1, result, emptyFirst);
 313                 m_subZones[1]->TopDepth(depth-1, result, false);
 314         }
 315 }
 316
 317 void CRoutingZone::RandomBin(ContactList *result, bool emptyFirst)
 318 {
 319         if (IsLeaf()) {
 320                 m_bin->GetEntries(result, emptyFirst);
 321         } else {
 322                 m_subZones[rand()&1]->RandomBin(result, emptyFirst);
 323         }
 324 }
 325
 326 uint32 CRoutingZone::GetMaxDepth(void) const
 327 {
 328         if (IsLeaf()) {
 329                 return 0;
 330         }
 331         return 1 + std::max(m_subZones[0]->GetMaxDepth(), m_subZones[1]->GetMaxDepth());
 332 }
 333
 334 void CRoutingZone::Split(void)
 335 {
 336         StopTimer();
 337
 338         m_subZones[0] = GenSubZone(0);
 339         m_subZones[1] = GenSubZone(1);
 340
 341         ContactList entries;
 342         m_bin->GetEntries(&entries);
 343         ContactList::const_iterator it;
 344         for (it = entries.begin(); it != entries.end(); ++it) {
 345                 int sz = (*it)->GetDistance().GetBitNumber(m_level);
 346                 m_subZones[sz]->m_bin->Add(*it);
 347         }
 348         m_bin->m_dontDeleteContacts = true;
 349         delete m_bin;
 350         m_bin = NULL;
 351 }
 352
 353 void CRoutingZone::Merge(void)
 354 {
 355         dirty = false; /* This subzone/superzone won't be re-checked */
 356
 357         AddDebugLogLineM( false, logKadRouting, wxT("Merge attempt"));
 358
 359         if (IsLeaf() && m_superZone != NULL) {
 360                 AddDebugLogLineM( false, logKadRouting, wxT("Recursive merge"));
 361                 m_superZone->Merge();
 362         } else if ((!IsLeaf())
 363                 && (m_subZones[0]->IsLeaf() && m_subZones[1]->IsLeaf())
 364                 &&      (GetNumContacts()) < (K/2) )
 365                 {
 366                 m_bin = new CRoutingBin();
 367
 368                 m_subZones[0]->StopTimer();
 369                 m_subZones[1]->StopTimer();
 370
 371                 if (GetNumContacts() > 0) {
 372                         ContactList list0;
 373                         ContactList list1;
 374                         m_subZones[0]->m_bin->GetEntries(&list0);
 375                         m_subZones[1]->m_bin->GetEntries(&list1);
 376                         ContactList::const_iterator it;
 377                         for (it = list0.begin(); it != list0.end(); ++it) {
 378                                 m_bin->Add(*it);
 379                         }
 380                         for (it = list1.begin(); it != list1.end(); ++it) {
 381                                 m_bin->Add(*it);
 382                         }
 383                 }
 384
 385                 m_subZones[0]->m_superZone = NULL;
 386                 m_subZones[1]->m_superZone = NULL;
 387
 388                 m_subZones[0]->m_bin->m_dontDeleteContacts = true;
 389                 m_subZones[1]->m_bin->m_dontDeleteContacts = true;
 390
 391                 delete m_subZones[0];
 392                 delete m_subZones[1];
 393
 394                 m_subZones[0] = NULL;
 395                 m_subZones[1] = NULL;
 396
 397                 StartTimer();
 398
 399                 AddDebugLogLineM( false, logKadRouting, wxT("Sucessful merge!"));
 400
 401                 if (m_superZone != NULL) {
 402                         m_superZone->Merge();
 403                 }
 404         } else {
 405                 AddDebugLogLineM( false, logKadRouting, wxT("No merge possible"));
 406         }
 407 }
 408
 409 bool CRoutingZone::IsLeaf(void) const
 410 {
 411         return (m_bin != NULL);
 412 }
 413
 414 CRoutingZone *CRoutingZone::GenSubZone(int side)
 415 {
 416         CUInt128 newIndex(m_zoneIndex);
 417         newIndex.ShiftLeft(1);
 418         if (side != 0) {
 419                 newIndex.Add(1);
 420         }
 421         CRoutingZone *retVal = new CRoutingZone(this, m_level+1, newIndex);
 422         return retVal;
 423 }
 424
 425 void CRoutingZone::StartTimer(void)
 426 {
 427         time_t now = time(NULL);
 428         // Start filling the tree, closest bins first.
 429         m_nextBigTimer = now + (MIN2S(1)*m_zoneIndex.Get32BitChunk(3)) + SEC(10);
 430         CKademlia::AddEvent(this);
 431 }
 432
 433 void CRoutingZone::StopTimer(void)
 434 {
 435         CKademlia::RemoveEvent(this);
 436 }
 437
 438 bool CRoutingZone::OnBigTimer(void)
 439 {
 440         if (!IsLeaf()) {
 441                 return false;
 442         }
 443
 444         if ( (m_zoneIndex < KK || m_level < KBASE || m_bin->GetRemaining() >= (K*.4))) {
 445                 RandomLookup();
 446                 return true;
 447         }
 448
 449         return false;
 450 }
 451
 452 //This is used when we find a leaf and want to know what this sample looks like.
 453 //We fall back two levels and take a sample to try to minimize any areas of the
 454 //tree that will give very bad results.
 455 uint32 CRoutingZone::EstimateCount()
 456 {
 457         if( !IsLeaf() ) {
 458                 return 0;
 459         }
 460         if( m_level < KBASE ) {
 461                 return (uint32)(pow((double)2, (int)m_level)*10);
 462         }
 463         CRoutingZone* curZone = m_superZone->m_superZone->m_superZone;
 464
 465         float modify = ((float)curZone->GetNumContacts())/20.0F;
 466         return (uint32)(pow((double) 2, (int)m_level-2)*10*(modify));
 467 }
 468
 469 void CRoutingZone::OnSmallTimer(void)
 470 {
 471         if (!IsLeaf()) {
 472                 return;
 473         }
 474
 475         dirty = false;
 476
 477         wxString test(m_zoneIndex.ToBinaryString());
 478
 479         CContact *c = NULL;
 480         time_t now = time(NULL);
 481         ContactList entries;
 482         ContactList::iterator it;
 483
 484         // Remove dead entries
 485         m_bin->GetEntries(&entries);
 486         for (it = entries.begin(); it != entries.end(); ++it) {
 487                 c = *it;
 488                 if ( c->GetType() == 4) {
 489                         if (((c->GetExpireTime() > 0) && (c->GetExpireTime() <= now))) {
 490                                 if(!c->InUse()) {
 491                                         m_bin->Remove(c);
 492                                         delete c;
 493                                         dirty = true;
 494                                 }
 495                                 continue;
 496                         }
 497                 }
 498                 if(c->GetExpireTime() == 0) {
 499                         c->SetExpireTime(now);
 500                 }
 501         }
 502         c = NULL;
 503         //Ping only contacts that are in the branches that meet the set level and are not close to our ID.
 504         //The other contacts are checked with the big timer.
 505         if( m_bin->GetRemaining() < (K*(.4)) ) {
 506                 c = m_bin->GetOldest();
 507         }
 508
 509         if( c != NULL ) {
 510                 if ( c->GetExpireTime() >= now || c->GetType() == 4) {
 511                         dirty = true;
 512                         m_bin->Remove(c);
 513                         m_bin->m_entries.push_back(c);
 514                         c = NULL;
 515                 }
 516         }
 517
 518         if(c != NULL) {
 519                 c->CheckingType();
 520                 AddDebugLogLineM(false, logClientKadUDP, wxT("KadHelloReq to ") + Uint32_16toStringIP_Port(wxUINT32_SWAP_ALWAYS(c->GetIPAddress()), c->GetUDPPort()));
 521                 CKademlia::GetUDPListener()->SendMyDetails(KADEMLIA_HELLO_REQ, c->GetIPAddress(), c->GetUDPPort());
 522         }
 523 }
 524
 525 void CRoutingZone::RandomLookup(void)
 526 {
 527         // Look-up a random client in this zone
 528         CUInt128 prefix(m_zoneIndex);
 529         prefix.ShiftLeft(128 - m_level);
 530         CUInt128 random(prefix, m_level);
 531         random.XOR(me);
 532         CSearchManager::FindNode(random);
 533 }
 534
 535 uint32 CRoutingZone::GetNumContacts(void) const
 536 {
 537         if (IsLeaf()) {
 538                 return m_bin->GetSize();
 539         } else {
 540                 return m_subZones[0]->GetNumContacts() + m_subZones[1]->GetNumContacts();
 541         }
 542 }
 543
 544 uint32 CRoutingZone::GetBootstrapContacts(ContactList *results, uint32 maxRequired)
 545 {
 546         wxASSERT(m_superZone == NULL);
 547
 548         results->clear();
 549
 550         uint32 retVal = 0;
 551         ContactList top;
 552         TopDepth(LOG_BASE_EXPONENT, &top);
 553         if (top.size() > 0) {
 554                 ContactList::const_iterator it;
 555                 for (it = top.begin(); it != top.end(); ++it) {
 556                         results->push_back(*it);
 557                         retVal++;
 558                         if (retVal == maxRequired) {
 559                                 break;
 560                         }
 561                 }
 562         }
 563
 564         return retVal;
 565 }
 566 // File_checked_for_headers