src/kademlia/routing/RoutingZone.cpp

   1 //
   2 // This file is part of 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) 2003-2011 Barry Dunne ( http://www.emule-project.net )
   7 // Copyright (C)2007-2011 Merkur ( strEmail.Format("%s@%s", "devteam", "emule-project.net") / http://www.emule-project.net )
   8
   9 // This program is free software; you can redistribute it and/or
  10 // modify it under the terms of the GNU General Public License
  11 // as published by the Free Software Foundation; either
  12 // version 2 of the License, or (at your option) any later version.
  13
  14 // This program is distributed in the hope that it will be useful,
  15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 // GNU General Public License for more details.
  18
  19 // You should have received a copy of the GNU General Public License
  20 // along with this program; if not, write to the Free Software
  21 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  22
  23 // This work is based on the java implementation of the Kademlia protocol.
  24 // Kademlia: Peer-to-peer routing based on the XOR metric
  25 // Copyright (c) 2002-2011  Petar Maymounkov ( petar@post.harvard.edu )
  26 // http://kademlia.scs.cs.nyu.edu
  27
  28 // Note To Mods //
  29 /*
  30 Please do not change anything here and release it..
  31 There is going to be a new forum created just for the Kademlia side of the client..
  32 If you feel there is an error or a way to improve something, please
  33 post it in the forum first and let us look at it.. If it is a real improvement,
  34 it will be added to the offical client.. Changing something without knowing
  35 what all it does can cause great harm to the network if released in mass form..
  36 Any mod that changes anything within the Kademlia side will not be allowed to advertise
  37 there client on the eMule forum..
  38 */
  39
  40 /**
  41  * The *Zone* is just a node in a binary tree of *Zone*s.
  42  * Each zone is either an internal node or a leaf node.
  43  * Internal nodes have "bin == null" and "subZones[i] != null",
  44  * leaf nodes have "subZones[i] == null" and "bin != null".
  45  *
  46  * All key unique id's are relative to the center (self), which
  47  * is considered to be 000..000
  48  */
  49 #include "RoutingZone.h"
  50
  51 #include <protocol/kad/Client2Client/UDP.h>
  52 #include <protocol/kad2/Client2Client/UDP.h>
  53 #include <common/Macros.h>
  54
  55 #include "Contact.h"
  56 #include "RoutingBin.h"
  57 #include "../kademlia/Defines.h"
  58 #include "../kademlia/SearchManager.h"
  59 #include "../kademlia/UDPFirewallTester.h"
  60 #include "../net/KademliaUDPListener.h"
  61 #include "../utils/KadUDPKey.h"
  62 #include "../../amule.h"
  63 #include "../../CFile.h"
  64 #include "../../Logger.h"
  65 #include "../../NetworkFunctions.h"
  66 #include "../../IPFilter.h"
  67 #include "../../RandomFunctions.h"
  68
  69 #include <cmath>
  70
  71 ////////////////////////////////////////
  72 using namespace Kademlia;
  73 ////////////////////////////////////////
  74
  75 // This is just a safety precaution
  76 #define CONTACT_FILE_LIMIT      500
  77
  78 wxString CRoutingZone::m_filename;
  79 CUInt128 CRoutingZone::me((uint32_t)0);
  80
  81 CRoutingZone::CRoutingZone()
  82 {
  83         // Can only create routing zone after prefs
  84         // Set our KadID for creating the contact tree
  85         me = CKademlia::GetPrefs()->GetKadID();
  86         // Set the preference file name.
  87         m_filename = theApp->ConfigDir + wxT("nodes.dat");
  88         Init(NULL, 0, CUInt128((uint32_t)0));
  89 }
  90
  91 void CRoutingZone::Init(CRoutingZone *super_zone, int level, const CUInt128& zone_index)
  92 {
  93         // Init all Zone vars
  94         // Set this zone's parent
  95         m_superZone = super_zone;
  96         // Set this zone's level
  97         m_level = level;
  98         // Set this zone's CUInt128 index
  99         m_zoneIndex = zone_index;
 100         // Mark this zone as having no leafs.
 101         m_subZones[0] = NULL;
 102         m_subZones[1] = NULL;
 103         // Create a new contact bin as this is a leaf.
 104         m_bin = new CRoutingBin();
 105
 106         // Set timer so that zones closer to the root are processed earlier.
 107         m_nextSmallTimer = time(NULL) + m_zoneIndex.Get32BitChunk(3);
 108
 109         // Start this zone.
 110         StartTimer();
 111
 112         // If we are initializing the root node, read in our saved contact list.
 113         if ((m_superZone == NULL) && (m_filename.Length() > 0)) {
 114                 ReadFile();
 115         }
 116 }
 117
 118 CRoutingZone::~CRoutingZone()
 119 {
 120         // Root node is processed first so that we can write our contact list and delete all branches.
 121         if ((m_superZone == NULL) && (m_filename.Length() > 0)) {
 122                 WriteFile();
 123         }
 124
 125         // If this zone is a leaf, delete our contact bin.
 126         if (IsLeaf()) {
 127                 delete m_bin;
 128         } else {
 129                 // If this zone is a branch, delete its leafs.
 130                 delete m_subZones[0];
 131                 delete m_subZones[1];
 132         }
 133 }
 134
 135 void CRoutingZone::ReadFile(const wxString& specialNodesdat)
 136 {
 137         if (m_superZone != NULL || (m_filename.IsEmpty() && specialNodesdat.IsEmpty())) {
 138                 wxFAIL;
 139                 return;
 140         }
 141
 142         bool doHaveVerifiedContacts = false;
 143         // Read in the saved contact list
 144         try {
 145                 uint32_t numContacts = 0;
 146                 uint32_t validContacts = 0;
 147                 CFile file;
 148                 if (CPath::FileExists(specialNodesdat.IsEmpty() ? m_filename : specialNodesdat) && file.Open(m_filename, CFile::read)) {
 149                         // Get how many contacts in the saved list.
 150                         // NOTE: Older clients put the number of contacts here...
 151                         //       Newer clients always have 0 here to prevent older clients from reading it.
 152                         numContacts = file.ReadUInt32();
 153                         uint32_t fileVersion = 0;
 154                         if (numContacts == 0) {
 155                                 if (file.GetLength() >= 8) {
 156                                         fileVersion = file.ReadUInt32();
 157                                         if (fileVersion == 3) {
 158                                                 uint32_t bootstrapEdition = file.ReadUInt32();
 159                                                 if (bootstrapEdition == 1) {
 160                                                         // this is a special bootstrap-only nodes.dat, handle it in a separate reading function
 161                                                         ReadBootstrapNodesDat(file);
 162                                                         file.Close();
 163                                                         return;
 164                                                 }
 165                                         }
 166                                         if (fileVersion >= 1 && fileVersion <= 3) {
 167                                                 numContacts = file.ReadUInt32();
 168                                         }
 169                                 }
 170                         } else {
 171                                 // Don't read version 0 nodes.dat files, because they can't tell the kad version of the contacts stored.
 172                                 AddLogLineC(_("Failed to read nodes.dat file - too old. This version (0) is not supported anymore."));
 173                                 numContacts = 0;
 174                         }
 175                         DEBUG_ONLY( unsigned kad1Count = 0; )
 176                         if (numContacts != 0 && numContacts * 25 <= (file.GetLength() - file.GetPosition())) {
 177                                 for (uint32_t i = 0; i < numContacts; i++) {
 178                                         CUInt128 id = file.ReadUInt128();
 179                                         uint32_t ip = file.ReadUInt32();
 180                                         uint16_t udpPort = file.ReadUInt16();
 181                                         uint16_t tcpPort = file.ReadUInt16();
 182                                         uint8_t contactVersion = 0;
 183                                         contactVersion = file.ReadUInt8();
 184                                         CKadUDPKey kadUDPKey;
 185                                         bool verified = false;
 186                                         if (fileVersion >= 2) {
 187                                                 kadUDPKey.ReadFromFile(file);
 188                                                 verified = file.ReadUInt8() != 0;
 189                                                 if (verified) {
 190                                                         doHaveVerifiedContacts = true;
 191                                                 }
 192                                         }
 193                                         // IP appears valid
 194                                         if (contactVersion > 1) {
 195                                                 if(IsGoodIPPort(wxUINT32_SWAP_ALWAYS(ip),udpPort)) {
 196                                                         if (!theApp->ipfilter->IsFiltered(wxUINT32_SWAP_ALWAYS(ip)) &&
 197                                                             !(udpPort == 53 && contactVersion <= 5 /*No DNS Port without encryption*/)) {
 198                                                                 // This was not a dead contact, inc counter if add was successful
 199                                                                 if (AddUnfiltered(id, ip, udpPort, tcpPort, contactVersion, kadUDPKey, verified, false, false)) {
 200                                                                         validContacts++;
 201                                                                 }
 202                                                         }
 203                                                 }
 204                                         } else {
 205                                                 DEBUG_ONLY( kad1Count++; )
 206                                         }
 207                                 }
 208                         }
 209                         file.Close();
 210                         AddLogLineN(CFormat(wxPLURAL("Read %u Kad contact", "Read %u Kad contacts", validContacts)) % validContacts);
 211 #ifdef __DEBUG__
 212                         if (kad1Count > 0) {
 213                                 AddDebugLogLineN(logKadRouting, CFormat(wxT("Ignored %u kad1 %s in nodes.dat file.")) % kad1Count % (kad1Count > 1 ? wxT("contacts"): wxT("contact")));
 214                         }
 215 #endif
 216                         if (!doHaveVerifiedContacts) {
 217                                 AddDebugLogLineN(logKadRouting, wxT("No verified contacts found in nodes.dat - might be an old file version. Setting all contacts verified for this time to speed up Kad bootstrapping."));
 218                                 SetAllContactsVerified();
 219                         }
 220                 }
 221                 if (validContacts == 0) {
 222                         AddLogLineC(_("No contacts found, please bootstrap, or download a nodes.dat file."));
 223                 }
 224         } catch (const CSafeIOException& DEBUG_ONLY(e)) {
 225                 AddDebugLogLineN(logKadRouting, wxT("IO error in CRoutingZone::readFile: ") + e.what());
 226         }
 227 }
 228
 229 void CRoutingZone::ReadBootstrapNodesDat(CFileDataIO& file)
 230 {
 231         // Bootstrap versions of nodes.dat files are in the style of version 1 nodes.dats. The difference is that
 232         // they will contain more contacts, 500-1000 instead of 50, and those contacts are not added into the routing table
 233         // but used to sent Bootstrap packets to. The advantage is that on a list with a high ratio of dead nodes,
 234         // we will be able to bootstrap faster than on a normal nodes.dat and more important, if we would deliver
 235         // a normal nodes.dat with eMule, those 50 nodes would be kinda DDOSed because everyone adds them to their routing
 236         // table, while with this style, we don't actually add any of the contacts to our routing table in the end and we
 237         // ask only one of those 1000 contacts one time (well or more until we find an alive one).
 238         if (!CKademlia::s_bootstrapList.empty()){
 239                 wxFAIL;
 240                 return;
 241         }
 242         uint32_t numContacts = file.ReadUInt32();
 243         if (numContacts != 0 && numContacts * 25 == (file.GetLength() - file.GetPosition())) {
 244                 uint32_t validContacts = 0;
 245                 while (numContacts) {
 246                         CUInt128 id = file.ReadUInt128();
 247                         uint32_t ip = file.ReadUInt32();
 248                         uint16_t udpPort = file.ReadUInt16();
 249                         uint16_t tcpPort = file.ReadUInt16();
 250                         uint8_t contactVersion = file.ReadUInt8();
 251
 252                         if (::IsGoodIPPort(wxUINT32_SWAP_ALWAYS(ip), udpPort)) {
 253                                 if (!theApp->ipfilter->IsFiltered(wxUINT32_SWAP_ALWAYS(ip)) &&
 254                                     !(udpPort == 53 && contactVersion <= 5) &&
 255                                     (contactVersion > 1))       // only kad2 nodes
 256                                 {
 257                                         // we want the 50 nodes closest to our own ID (provides randomness between different users and gets has good chances to get a bootstrap with close Nodes which is a nice start for our routing table)
 258                                         CUInt128 distance = me;
 259                                         distance ^= id;
 260                                         validContacts++;
 261                                         // don't bother if we already have 50 and the farest distance is smaller than this contact
 262                                         if (CKademlia::s_bootstrapList.size() < 50 || CKademlia::s_bootstrapList.back()->GetDistance() > distance) {
 263                                                 // look where to put this contact into the proper position
 264                                                 bool inserted = false;
 265                                                 CContact* contact = new CContact(id, ip, udpPort, tcpPort, contactVersion, 0, false, me);
 266                                                 for (ContactList::iterator it = CKademlia::s_bootstrapList.begin(); it != CKademlia::s_bootstrapList.end(); ++it) {
 267                                                         if ((*it)->GetDistance() > distance) {
 268                                                                 CKademlia::s_bootstrapList.insert(it, contact);
 269                                                                 inserted = true;
 270                                                                 break;
 271                                                         }
 272                                                 }
 273                                                 if (!inserted) {
 274                                                         wxASSERT(CKademlia::s_bootstrapList.size() < 50);
 275                                                         CKademlia::s_bootstrapList.push_back(contact);
 276                                                 } else if (CKademlia::s_bootstrapList.size() > 50) {
 277                                                         delete CKademlia::s_bootstrapList.back();
 278                                                         CKademlia::s_bootstrapList.pop_back();
 279                                                 }
 280                                         }
 281                                 }
 282                         }
 283                         numContacts--;
 284                 }
 285                 AddLogLineN(CFormat(wxPLURAL("Read %u Kad contact", "Read %u Kad contacts", CKademlia::s_bootstrapList.size())) % CKademlia::s_bootstrapList.size());
 286                 AddDebugLogLineN(logKadRouting, CFormat(wxT("Loaded Bootstrap nodes.dat, selected %u out of %u valid contacts")) % CKademlia::s_bootstrapList.size() % validContacts);
 287         }
 288         if (CKademlia::s_bootstrapList.size() == 0) {
 289                 AddLogLineC(_("No contacts found, please bootstrap, or download a nodes.dat file."));
 290         }
 291 }
 292
 293 void CRoutingZone::WriteFile()
 294 {
 295         // don't overwrite a bootstrap nodes.dat with an empty one, if we didn't finish probing
 296         if (!CKademlia::s_bootstrapList.empty() && GetNumContacts() == 0) {
 297                 AddDebugLogLineN(logKadRouting, wxT("Skipped storing nodes.dat, because we have an unfinished bootstrap of the nodes.dat version and no contacts in our routing table"));
 298                 return;
 299         }
 300
 301         // The bootstrap method gets a very nice sample of contacts to save.
 302         ContactList contacts;
 303         GetBootstrapContacts(&contacts, 200);
 304         ContactList::size_type numContacts = contacts.size();
 305         numContacts = std::min<ContactList::size_type>(numContacts, CONTACT_FILE_LIMIT); // safety precaution, should not be above
 306         if (numContacts < 25) {
 307                 AddLogLineN(CFormat(wxPLURAL("Only %d Kad contact available, nodes.dat not written", "Only %d Kad contacts available, nodes.dat not written", numContacts)) % numContacts);
 308                 return;
 309         }
 310         try {
 311                 unsigned int count = 0;
 312                 CFile file;
 313                 if (file.Open(m_filename, CFile::write_safe)) {
 314                         // Start file with 0 to prevent older clients from reading it.
 315                         file.WriteUInt32(0);
 316                         // Now tag it with a version which happens to be 2.
 317                         file.WriteUInt32(2);
 318                         // file.WriteUInt32(0); // if we would use version >= 3 this would mean that this is a normal nodes.dat
 319                         file.WriteUInt32(numContacts);
 320                         for (ContactList::const_iterator it = contacts.begin(); it != contacts.end(); ++it) {
 321                                 CContact *c = *it;
 322                                 count++;
 323                                 if (count > CONTACT_FILE_LIMIT) {
 324                                         // This should never happen
 325                                         wxFAIL;
 326                                         break;
 327                                 }
 328                                 file.WriteUInt128(c->GetClientID());
 329                                 file.WriteUInt32(c->GetIPAddress());
 330                                 file.WriteUInt16(c->GetUDPPort());
 331                                 file.WriteUInt16(c->GetTCPPort());
 332                                 file.WriteUInt8(c->GetVersion());
 333                                 c->GetUDPKey().StoreToFile(file);
 334                                 file.WriteUInt8(c->IsIPVerified() ? 1 : 0);
 335                         }
 336                         file.Close();
 337                 }
 338                 AddLogLineN(CFormat(wxPLURAL("Wrote %d Kad contact", "Wrote %d Kad contacts", count)) % count);
 339         } catch (const CIOFailureException& e) {
 340                 AddDebugLogLineC(logKadRouting, wxT("IO failure in CRoutingZone::writeFile: ") + e.what());
 341         }
 342 }
 343
 344 #if 0
 345 void CRoutingZone::WriteBootstrapFile()
 346 {
 347         AddDebugLogLineC(logKadRouting, wxT("Writing special bootstrap nodes.dat - not intended for normal use"));
 348         try {
 349                 // Write a saved contact list.
 350                 CUInt128 id;
 351                 CFile file;
 352                 if (file.Open(m_filename, CFile::write)) {
 353                         // The bootstrap method gets a very nice sample of contacts to save.
 354                         ContactMap mapContacts;
 355                         CUInt128 random(CUInt128((uint32_t)0), 0);
 356                         CUInt128 distance = random;
 357                         distance ^= me;
 358                         GetClosestTo(2, random, distance, 1200, &mapContacts, false, false);
 359                         // filter out Kad1 nodes
 360                         for (ContactMap::iterator it = mapContacts.begin(); it != mapContacts.end(); ) {
 361                                 ContactMap::iterator itCur = it++;
 362                                 CContact* contact = itCur->second;
 363                                 if (contact->GetVersion() <= 1) {
 364                                         mapContacts.erase(itCur);
 365                                 }
 366                         }
 367                         // Start file with 0 to prevent older clients from reading it.
 368                         file.WriteUInt32(0);
 369                         // Now tag it with a version which happens to be 3.
 370                         file.WriteUInt32(3);
 371                         file.WriteUInt32(1); // using version >= 3, this means that this is not a normal nodes.dat
 372                         file.WriteUInt32((uint32_t)mapContacts.size());
 373                         for (ContactMap::const_iterator it = mapContacts.begin(); it != mapContacts.end(); ++it)
 374                         {
 375                                 CContact* contact = it->second;
 376                                 file.WriteUInt128(contact->GetClientID());
 377                                 file.WriteUInt32(contact->GetIPAddress());
 378                                 file.WriteUInt16(contact->GetUDPPort());
 379                                 file.WriteUInt16(contact->GetTCPPort());
 380                                 file.WriteUInt8(contact->GetVersion());
 381                         }
 382                         file.Close();
 383                         AddDebugLogLineN(logKadRouting, CFormat(wxT("Wrote %u contacts to bootstrap file.")) % mapContacts.size());
 384                 } else {
 385                         AddDebugLogLineC(logKadRouting, wxT("Unable to store Kad file: ") + m_filename);
 386                 }
 387         } catch (const CIOFailureException& e) {
 388                 AddDebugLogLineC(logKadRouting, wxT("CFileException in CRoutingZone::writeFile") + e.what());
 389         }
 390 }
 391 #endif
 392
 393 bool CRoutingZone::CanSplit() const throw()
 394 {
 395         // Max levels allowed.
 396         if (m_level >= 127) {
 397                 return false;
 398         }
 399
 400         // Check if this zone is allowed to split.
 401         return ((m_zoneIndex < KK || m_level < KBASE) && m_bin->GetSize() == K);
 402 }
 403
 404 // Returns true if a contact was added or updated, false if the routing table was not touched.
 405 bool CRoutingZone::Add(const CUInt128& id, uint32_t ip, uint16_t port, uint16_t tport, uint8_t version, const CKadUDPKey& key, bool& ipVerified, bool update, bool fromHello)
 406 {
 407         if (IsGoodIPPort(wxUINT32_SWAP_ALWAYS(ip), port)) {
 408                 if (!theApp->ipfilter->IsFiltered(wxUINT32_SWAP_ALWAYS(ip)) && !(port == 53 && version <= 5) /*No DNS Port without encryption*/) {
 409                         return AddUnfiltered(id, ip, port, tport, version, key, ipVerified, update, fromHello);
 410                 }
 411         }
 412         return false;
 413 }
 414
 415 // Returns true if a contact was added or updated, false if the routing table was not touched.
 416 bool CRoutingZone::AddUnfiltered(const CUInt128& id, uint32_t ip, uint16_t port, uint16_t tport, uint8_t version, const CKadUDPKey& key, bool& ipVerified, bool update, bool fromHello)
 417 {
 418         if (id != me) {
 419                 CContact *contact = new CContact(id, ip, port, tport, version, key, ipVerified);
 420                 if (fromHello) {
 421                         contact->SetReceivedHelloPacket();
 422                 }
 423                 if (Add(contact, update, ipVerified)) {
 424                         wxASSERT(!update);
 425                         return true;
 426                 } else {
 427                         delete contact;
 428                         return update;
 429                 }
 430         }
 431         return false;
 432 }
 433
 434 bool CRoutingZone::Add(CContact *contact, bool& update, bool& outIpVerified)
 435 {
 436         // If we're not a leaf, call add on the correct branch.
 437         if (!IsLeaf()) {
 438                 return m_subZones[contact->GetDistance().GetBitNumber(m_level)]->Add(contact, update, outIpVerified);
 439         } else {
 440                 // Do we already have a contact with this KadID?
 441                 CContact *contactUpdate = m_bin->GetContact(contact->GetClientID());
 442                 if (contactUpdate) {
 443                         if (update) {
 444                                 if (contactUpdate->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false)) != 0 && contactUpdate->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false)) != contact->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false))) {
 445                                         // if our existing contact has a UDPSender-Key (which should be the case for all > = 0.49a clients)
 446                                         // except if our IP has changed recently, we demand that the key is the same as the key we received
 447                                         // from the packet which wants to update this contact in order to make sure this is not a try to
 448                                         // hijack this entry
 449                                         AddDebugLogLineN(logKadRouting, wxT("Sender (") + KadIPToString(contact->GetIPAddress()) + wxT(") tried to update contact entry but failed to provide the proper sender key (Sent Empty: ") + (contact->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false)) == 0 ? wxT("Yes") : wxT("No")) + wxT(") for the entry (") + KadIPToString(contactUpdate->GetIPAddress()) + wxT(") - denying update"));
 450                                         update = false;
 451                                 } else if (contactUpdate->GetVersion() >= 1 && contactUpdate->GetVersion() < 6 && contactUpdate->GetReceivedHelloPacket()) {
 452                                         // legacy kad2 contacts are allowed only to update their RefreshTimer to avoid having them hijacked/corrupted by an attacker
 453                                         // (kad1 contacts do not have this restriction as they might turn out as kad2 later on)
 454                                         // only exception is if we didn't received a HELLO packet from this client yet
 455                                         if (contactUpdate->GetIPAddress() == contact->GetIPAddress() && contactUpdate->GetTCPPort() == contact->GetTCPPort() && contactUpdate->GetVersion() == contact->GetVersion() && contactUpdate->GetUDPPort() == contact->GetUDPPort()) {
 456                                                 wxASSERT(!contact->IsIPVerified());     // legacy kad2 nodes should be unable to verify their IP on a HELLO
 457                                                 outIpVerified = contactUpdate->IsIPVerified();
 458                                                 m_bin->SetAlive(contactUpdate);
 459                                                 AddDebugLogLineN(logKadRouting, CFormat(wxT("Updated kad contact refreshtimer only for legacy kad2 contact (%s, %u)")) % KadIPToString(contactUpdate->GetIPAddress()) % contactUpdate->GetVersion());
 460                                         } else {
 461                                                 AddDebugLogLineN(logKadRouting, CFormat(wxT("Rejected value update for legacy kad2 contact (%s -> %s, %u -> %u)"))
 462                                                         % KadIPToString(contactUpdate->GetIPAddress()) % KadIPToString(contact->GetIPAddress()) % contactUpdate->GetVersion() % contact->GetVersion());
 463                                                 update = false;
 464                                         }
 465                                 } else {
 466 #ifdef __DEBUG__
 467                                         // just for outlining, get removed anyway
 468                                         //debug logging stuff - remove later
 469                                         if (contact->GetUDPKey().GetKeyValue(theApp->GetPublicIP(false)) == 0) {
 470                                                 if (contact->GetVersion() >= 6 && contact->GetType() < 2) {
 471                                                         AddDebugLogLineN(logKadRouting, wxT("Updating > 0.49a + type < 2 contact without valid key stored ") + KadIPToString(contact->GetIPAddress()));
 472                                                 }
 473                                         } else {
 474                                                 AddDebugLogLineN(logKadRouting, wxT("Updating contact, passed key check ") + KadIPToString(contact->GetIPAddress()));
 475                                         }
 476
 477                                         if (contactUpdate->GetVersion() >= 1 && contactUpdate->GetVersion() < 6) {
 478                                                 wxASSERT(!contactUpdate->GetReceivedHelloPacket());
 479                                                 AddDebugLogLineN(logKadRouting, CFormat(wxT("Accepted update for legacy kad2 contact, because of first HELLO (%s -> %s, %u -> %u)"))
 480                                                         % KadIPToString(contactUpdate->GetIPAddress()) % KadIPToString(contact->GetIPAddress()) % contactUpdate->GetVersion() % contact->GetVersion());
 481                                         }
 482 #endif
 483                                         // All other nodes (Kad1, Kad2 > 0.49a with UDPKey checked or not set, first hello updates) are allowed to do full updates
 484                                         // do not let Kad1 responses overwrite Kad2 ones
 485                                         if (m_bin->ChangeContactIPAddress(contactUpdate, contact->GetIPAddress()) && contact->GetVersion() >= contactUpdate->GetVersion()) {
 486                                                 contactUpdate->SetUDPPort(contact->GetUDPPort());
 487                                                 contactUpdate->SetTCPPort(contact->GetTCPPort());
 488                                                 contactUpdate->SetVersion(contact->GetVersion());
 489                                                 contactUpdate->SetUDPKey(contact->GetUDPKey());
 490                                                 // don't unset the verified flag (will clear itself on ipchanges)
 491                                                 if (!contactUpdate->IsIPVerified()) {
 492                                                         contactUpdate->SetIPVerified(contact->IsIPVerified());
 493                                                 }
 494                                                 outIpVerified = contactUpdate->IsIPVerified();
 495                                                 m_bin->SetAlive(contactUpdate);
 496                                                 if (contact->GetReceivedHelloPacket()) {
 497                                                         contactUpdate->SetReceivedHelloPacket();
 498                                                 }
 499                                         } else {
 500                                                 update = false;
 501                                         }
 502                                 }
 503                         }
 504                         return false;
 505                 } else if (m_bin->GetRemaining()) {
 506                         update = false;
 507                         // This bin is not full, so add the new contact
 508                         return m_bin->AddContact(contact);
 509                 } else if (CanSplit()) {
 510                         // This bin was full and split, call add on the correct branch.
 511                         Split();
 512                         return m_subZones[contact->GetDistance().GetBitNumber(m_level)]->Add(contact, update, outIpVerified);
 513                 } else {
 514                         update = false;
 515                         return false;
 516                 }
 517         }
 518 }
 519
 520 CContact *CRoutingZone::GetContact(const CUInt128& id) const throw()
 521 {
 522         if (IsLeaf()) {
 523                 return m_bin->GetContact(id);
 524         } else {
 525                 CUInt128 distance = CKademlia::GetPrefs()->GetKadID();
 526                 distance ^= id;
 527                 return m_subZones[distance.GetBitNumber(m_level)]->GetContact(id);
 528         }
 529 }
 530
 531 CContact *CRoutingZone::GetContact(uint32_t ip, uint16_t port, bool tcpPort) const throw()
 532 {
 533         if (IsLeaf()) {
 534                 return m_bin->GetContact(ip, port, tcpPort);
 535         } else {
 536                 CContact *contact = m_subZones[0]->GetContact(ip, port, tcpPort);
 537                 return (contact != NULL) ? contact : m_subZones[1]->GetContact(ip, port, tcpPort);
 538         }
 539 }
 540
 541 CContact *CRoutingZone::GetRandomContact(uint32_t maxType, uint32_t minKadVersion) const
 542 {
 543         if (IsLeaf()) {
 544                 return m_bin->GetRandomContact(maxType, minKadVersion);
 545         } else {
 546                 unsigned zone = GetRandomUint16() & 1 /* GetRandomUint16() % 2 */;
 547                 CContact *contact = m_subZones[zone]->GetRandomContact(maxType, minKadVersion);
 548                 return (contact != NULL) ? contact : m_subZones[1 - zone]->GetRandomContact(maxType, minKadVersion);
 549         }
 550 }
 551
 552 void CRoutingZone::GetClosestTo(uint32_t maxType, const CUInt128& target, const CUInt128& distance, uint32_t maxRequired, ContactMap *result, bool emptyFirst, bool inUse) const
 553 {
 554         // If leaf zone, do it here
 555         if (IsLeaf()) {
 556                 m_bin->GetClosestTo(maxType, target, maxRequired, result, emptyFirst, inUse);
 557                 return;
 558         }
 559
 560         // otherwise, recurse in the closer-to-the-target subzone first
 561         int closer = distance.GetBitNumber(m_level);
 562         m_subZones[closer]->GetClosestTo(maxType, target, distance, maxRequired, result, emptyFirst, inUse);
 563
 564         // if still not enough tokens found, recurse in the other subzone too
 565         if (result->size() < maxRequired) {
 566                 m_subZones[1-closer]->GetClosestTo(maxType, target, distance, maxRequired, result, false, inUse);
 567         }
 568 }
 569
 570 void CRoutingZone::GetAllEntries(ContactList *result, bool emptyFirst) const
 571 {
 572         if (IsLeaf()) {
 573                 m_bin->GetEntries(result, emptyFirst);
 574         } else {
 575                 m_subZones[0]->GetAllEntries(result, emptyFirst);
 576                 m_subZones[1]->GetAllEntries(result, false);
 577         }
 578 }
 579
 580 void CRoutingZone::TopDepth(int depth, ContactList *result, bool emptyFirst) const
 581 {
 582         if (IsLeaf()) {
 583                 m_bin->GetEntries(result, emptyFirst);
 584         } else if (depth <= 0) {
 585                 RandomBin(result, emptyFirst);
 586         } else {
 587                 m_subZones[0]->TopDepth(depth-1, result, emptyFirst);
 588                 m_subZones[1]->TopDepth(depth-1, result, false);
 589         }
 590 }
 591
 592 void CRoutingZone::RandomBin(ContactList *result, bool emptyFirst) const
 593 {
 594         if (IsLeaf()) {
 595                 m_bin->GetEntries(result, emptyFirst);
 596         } else {
 597                 m_subZones[rand()&1]->RandomBin(result, emptyFirst);
 598         }
 599 }
 600
 601 uint32_t CRoutingZone::GetMaxDepth() const throw()
 602 {
 603         if (IsLeaf()) {
 604                 return 0;
 605         }
 606         return 1 + std::max(m_subZones[0]->GetMaxDepth(), m_subZones[1]->GetMaxDepth());
 607 }
 608
 609 void CRoutingZone::Split()
 610 {
 611         StopTimer();
 612
 613         m_subZones[0] = GenSubZone(0);
 614         m_subZones[1] = GenSubZone(1);
 615
 616         ContactList entries;
 617         m_bin->GetEntries(&entries);
 618         m_bin->m_dontDeleteContacts = true;
 619         delete m_bin;
 620         m_bin = NULL;
 621
 622         for (ContactList::const_iterator it = entries.begin(); it != entries.end(); ++it) {
 623                 if (!m_subZones[(*it)->GetDistance().GetBitNumber(m_level)]->m_bin->AddContact(*it)) {
 624                         delete *it;
 625                 }
 626         }
 627 }
 628
 629 uint32_t CRoutingZone::Consolidate()
 630 {
 631         uint32_t mergeCount = 0;
 632
 633         if (IsLeaf()) {
 634                 return mergeCount;
 635         }
 636
 637         wxASSERT(m_bin == NULL);
 638
 639         if (!m_subZones[0]->IsLeaf()) {
 640                 mergeCount += m_subZones[0]->Consolidate();
 641         }
 642         if (!m_subZones[1]->IsLeaf()) {
 643                 mergeCount += m_subZones[1]->Consolidate();
 644         }
 645
 646         if (m_subZones[0]->IsLeaf() && m_subZones[1]->IsLeaf() && GetNumContacts() < K / 2) {
 647                 m_bin = new CRoutingBin();
 648
 649                 m_subZones[0]->StopTimer();
 650                 m_subZones[1]->StopTimer();
 651
 652                 ContactList list0;
 653                 ContactList list1;
 654                 m_subZones[0]->m_bin->GetEntries(&list0);
 655                 m_subZones[1]->m_bin->GetEntries(&list1);
 656
 657                 m_subZones[0]->m_bin->m_dontDeleteContacts = true;
 658                 m_subZones[1]->m_bin->m_dontDeleteContacts = true;
 659
 660                 delete m_subZones[0];
 661                 delete m_subZones[1];
 662
 663                 m_subZones[0] = NULL;
 664                 m_subZones[1] = NULL;
 665
 666                 for (ContactList::const_iterator it = list0.begin(); it != list0.end(); ++it) {
 667                         m_bin->AddContact(*it);
 668                 }
 669                 for (ContactList::const_iterator it = list1.begin(); it != list1.end(); ++it) {
 670                         m_bin->AddContact(*it);
 671                 }
 672
 673                 StartTimer();
 674
 675                 mergeCount++;
 676         }
 677         return mergeCount;
 678 }
 679
 680 CRoutingZone *CRoutingZone::GenSubZone(unsigned side)
 681 {
 682         wxASSERT(side <= 1);
 683
 684         CUInt128 newIndex(m_zoneIndex);
 685         newIndex <<= 1;
 686         newIndex += side;
 687         return new CRoutingZone(this, m_level + 1, newIndex);
 688 }
 689
 690 void CRoutingZone::StartTimer()
 691 {
 692         // Start filling the tree, closest bins first.
 693         m_nextBigTimer = time(NULL) + SEC(10);
 694         CKademlia::AddEvent(this);
 695 }
 696
 697 void CRoutingZone::StopTimer()
 698 {
 699         CKademlia::RemoveEvent(this);
 700 }
 701
 702 bool CRoutingZone::OnBigTimer() const
 703 {
 704         if (IsLeaf() && (m_zoneIndex < KK || m_level < KBASE || m_bin->GetRemaining() >= (K * 0.8))) {
 705                 RandomLookup();
 706                 return true;
 707         }
 708
 709         return false;
 710 }
 711
 712 //This is used when we find a leaf and want to know what this sample looks like.
 713 //We fall back two levels and take a sample to try to minimize any areas of the
 714 //tree that will give very bad results.
 715 uint32_t CRoutingZone::EstimateCount() const
 716 {
 717         if (!IsLeaf()) {
 718                 return 0;
 719         }
 720
 721         if (m_level < KBASE) {
 722                 return (uint32_t)(pow(2.0, (int)m_level) * K);
 723         }
 724
 725         CRoutingZone* curZone = m_superZone->m_superZone->m_superZone;
 726
 727         // Find out how full this part of the tree is.
 728         float modify = ((float)curZone->GetNumContacts()) / (float)(K * 2);
 729
 730         // First calculate users assuming the tree is full.
 731         // Modify count by bin size.
 732         // Modify count by how full the tree is.
 733
 734         // LowIDModififier
 735         // Modify count by assuming 20% of the users are firewalled and can't be a contact for < 0.49b nodes
 736         // Modify count by actual statistics of Firewalled ratio for >= 0.49b if we are not firewalled ourself
 737         // Modify count by 40% for >= 0.49b if we are firewalled ourself (the actual Firewalled count at this date on kad is 35-55%)
 738         const float firewalledModifyOld = 1.20f;
 739         float firewalledModifyNew = 0;
 740         if (CUDPFirewallTester::IsFirewalledUDP(true)) {
 741                 firewalledModifyNew = 1.40f;    // we are firewalled and can't get the real statistics, assume 40% firewalled >=0.49b nodes
 742         } else if (CKademlia::GetPrefs()->StatsGetFirewalledRatio(true) > 0) {
 743                 firewalledModifyNew = 1.0 + (CKademlia::GetPrefs()->StatsGetFirewalledRatio(true));     // apply the firewalled ratio to the modify
 744                 wxASSERT(firewalledModifyNew > 1.0 && firewalledModifyNew < 1.90);
 745         }
 746         float newRatio = CKademlia::GetPrefs()->StatsGetKadV8Ratio();
 747         float firewalledModifyTotal = 0;
 748         if (newRatio > 0 && firewalledModifyNew > 0) {  // weight the old and the new modifier based on how many new contacts we have
 749                 firewalledModifyTotal = (newRatio * firewalledModifyNew) + ((1 - newRatio) * firewalledModifyOld);
 750         } else {
 751                 firewalledModifyTotal = firewalledModifyOld;
 752         }
 753         wxASSERT(firewalledModifyTotal > 1.0 && firewalledModifyTotal < 1.90);
 754
 755         return (uint32_t)(pow(2.0, (int)m_level - 2) * (float)K * modify * firewalledModifyTotal);
 756 }
 757
 758 void CRoutingZone::OnSmallTimer()
 759 {
 760         if (!IsLeaf()) {
 761                 return;
 762         }
 763
 764         CContact *c = NULL;
 765         time_t now = time(NULL);
 766         ContactList entries;
 767
 768         // Remove dead entries
 769         m_bin->GetEntries(&entries);
 770         for (ContactList::iterator it = entries.begin(); it != entries.end(); ++it) {
 771                 c = *it;
 772                 if (c->GetType() == 4) {
 773                         if ((c->GetExpireTime() > 0) && (c->GetExpireTime() <= now)) {
 774                                 if (!c->InUse()) {
 775                                         m_bin->RemoveContact(c);
 776                                         delete c;
 777                                 }
 778                                 continue;
 779                         }
 780                 }
 781                 if(c->GetExpireTime() == 0) {
 782                         c->SetExpireTime(now);
 783                 }
 784         }
 785
 786         c = m_bin->GetOldest();
 787         if (c != NULL) {
 788                 if (c->GetExpireTime() >= now || c->GetType() == 4) {
 789                         m_bin->PushToBottom(c);
 790                         c = NULL;
 791                 }
 792         }
 793
 794         if (c != NULL) {
 795                 c->CheckingType();
 796                 if (c->GetVersion() >= 6) {
 797                         DebugSend(Kad2HelloReq, c->GetIPAddress(), c->GetUDPPort());
 798                         CUInt128 clientID = c->GetClientID();
 799                         CKademlia::GetUDPListener()->SendMyDetails(KADEMLIA2_HELLO_REQ, c->GetIPAddress(), c->GetUDPPort(), c->GetVersion(), c->GetUDPKey(), &clientID, false);
 800                         if (c->GetVersion() >= 8) {
 801                                 // FIXME:
 802                                 // This is a bit of a work around for statistic values. Normally we only count values from incoming HELLO_REQs for
 803                                 // the firewalled statistics in order to get numbers from nodes which have us on their routing table,
 804                                 // however if we send a HELLO due to the timer, the remote node won't send a HELLO_REQ itself anymore (but
 805                                 // a HELLO_RES which we don't count), so count those statistics here. This isn't really accurate, but it should
 806                                 // do fair enough. Maybe improve it later for example by putting a flag into the contact and make the answer count
 807                                 CKademlia::GetPrefs()->StatsIncUDPFirewalledNodes(false);
 808                                 CKademlia::GetPrefs()->StatsIncTCPFirewalledNodes(false);
 809                         }
 810                 } else if (c->GetVersion() >= 2) {
 811                         DebugSend(Kad2HelloReq, c->GetIPAddress(), c->GetUDPPort());
 812                         CKademlia::GetUDPListener()->SendMyDetails(KADEMLIA2_HELLO_REQ, c->GetIPAddress(), c->GetUDPPort(), c->GetVersion(), 0, NULL, false);
 813                         wxASSERT(c->GetUDPKey() == CKadUDPKey(0));
 814                 } else {
 815                         wxFAIL;
 816                 }
 817         }
 818 }
 819
 820 void CRoutingZone::RandomLookup() const
 821 {
 822         // Look-up a random client in this zone
 823         CUInt128 prefix(m_zoneIndex);
 824         prefix <<= 128 - m_level;
 825         CUInt128 random(prefix, m_level);
 826         random ^= me;
 827         CSearchManager::FindNode(random, false);
 828 }
 829
 830 uint32_t CRoutingZone::GetNumContacts() const throw()
 831 {
 832         if (IsLeaf()) {
 833                 return m_bin->GetSize();
 834         } else {
 835                 return m_subZones[0]->GetNumContacts() + m_subZones[1]->GetNumContacts();
 836         }
 837 }
 838
 839 void CRoutingZone::GetNumContacts(uint32_t& nInOutContacts, uint32_t& nInOutFilteredContacts, uint8_t minVersion) const throw()
 840 {
 841         if (IsLeaf()) {
 842                 m_bin->GetNumContacts(nInOutContacts, nInOutFilteredContacts, minVersion);
 843         } else {
 844                 m_subZones[0]->GetNumContacts(nInOutContacts, nInOutFilteredContacts, minVersion);
 845                 m_subZones[1]->GetNumContacts(nInOutContacts, nInOutFilteredContacts, minVersion);
 846         }
 847 }
 848
 849 uint32_t CRoutingZone::GetBootstrapContacts(ContactList *results, uint32_t maxRequired) const
 850 {
 851         wxASSERT(m_superZone == NULL);
 852
 853         results->clear();
 854
 855         uint32_t count = 0;
 856         ContactList top;
 857         TopDepth(LOG_BASE_EXPONENT, &top);
 858         if (top.size() > 0) {
 859                 for (ContactList::const_iterator it = top.begin(); it != top.end(); ++it) {
 860                         results->push_back(*it);
 861                         count++;
 862                         if (count == maxRequired) {
 863                                 break;
 864                         }
 865                 }
 866         }
 867
 868         return count;
 869 }
 870
 871 bool CRoutingZone::VerifyContact(const CUInt128& id, uint32_t ip)
 872 {
 873         CContact* contact = GetContact(id);
 874         if (contact == NULL) {
 875                 return false;
 876         } else if (ip != contact->GetIPAddress()) {
 877                 return false;
 878         } else {
 879                 if (contact->IsIPVerified()) {
 880                         AddDebugLogLineN(logKadRouting, wxT("Sender already verified (sender: ") + KadIPToString(ip) + wxT(")"));
 881                 } else {
 882                         contact->SetIPVerified(true);
 883                 }
 884                 return true;
 885         }
 886 }
 887
 888 void CRoutingZone::SetAllContactsVerified()
 889 {
 890         if (IsLeaf()) {
 891                 m_bin->SetAllContactsVerified();
 892         } else {
 893                 m_subZones[0]->SetAllContactsVerified();
 894                 m_subZones[1]->SetAllContactsVerified();
 895         }
 896 }
 897
 898 bool CRoutingZone::IsAcceptableContact(const CContact *toCheck) const
 899 {
 900         // Check if we know a contact with the same ID or IP but notmatching IP/ID and other limitations, similar checks like when adding a node to the table except allowing duplicates
 901         // we use this to check KADEMLIA_RES routing answers on searches
 902         if (toCheck->GetVersion() <= 1) {
 903                 // No Kad1 contacts allowed
 904                 return false;
 905         }
 906         CContact *duplicate = GetContact(toCheck->GetClientID());
 907         if (duplicate != NULL) {
 908                 if ((duplicate->IsIPVerified() && duplicate->GetIPAddress() != toCheck->GetIPAddress()) || duplicate->GetUDPPort() != toCheck->GetUDPPort()) {
 909                         // already existing verified node with different IP
 910                         return false;
 911                 } else {
 912                         // node exists already in our routing table, that's fine
 913                         return true;
 914                 }
 915         }
 916         // if the node is not yet known, check if our IP limitations would hit
 917         return CRoutingBin::CheckGlobalIPLimits(toCheck->GetIPAddress(), toCheck->GetUDPPort());
 918 }
 919
 920 bool CRoutingZone::HasOnlyLANNodes() const throw()
 921 {
 922         if (IsLeaf()) {
 923                 return m_bin->HasOnlyLANNodes();
 924         } else {
 925                 return m_subZones[0]->HasOnlyLANNodes() && m_subZones[1]->HasOnlyLANNodes();
 926         }
 927 }