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