src/kademlia/routing/RoutingBin.cpp

   1 //
   2 // This file is part of aMule Project
   3 //
   4 // Copyright (c) 2004-2008 Angel Vidal ( kry@amule.org )
   5 // Copyright (c) 2003-2008 aMule Team ( admin@amule.org / http://www.amule.org )
   6 // Copyright (c) 2003-2008 Barry Dunne ( http://www.emule-project.net )
   7
   8 // This program is free software; you can redistribute it and/or
   9 // modify it under the terms of the GNU General Public License
  10 // as published by the Free Software Foundation; either
  11 // version 2 of the License, or (at your option) any later version.
  12
  13 // This program is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17
  18 // You should have received a copy of the GNU General Public License
  19 // along with this program; if not, write to the Free Software
  20 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  21
  22 // This work is based on the java implementation of the Kademlia protocol.
  23 // Kademlia: Peer-to-peer routing based on the XOR metric
  24 // Copyright (c) 2002-2008  Petar Maymounkov ( petar@post.harvard.edu )
  25 // http://kademlia.scs.cs.nyu.edu
  26
  27 // Note To Mods //
  28 /*
  29 Please do not change anything here and release it..
  30 There is going to be a new forum created just for the Kademlia side of the client..
  31 If you feel there is an error or a way to improve something, please
  32 post it in the forum first and let us look at it.. If it is a real improvement,
  33 it will be added to the offical client.. Changing something without knowing
  34 what all it does can cause great harm to the network if released in mass form..
  35 Any mod that changes anything within the Kademlia side will not be allowed to advertise
  36 there client on the eMule forum..
  37 */
  38
  39 #include "RoutingBin.h"
  40 #include "../../Logger.h"
  41 #include "../../NetworkFunctions.h"
  42 #include "../../RandomFunctions.h"
  43
  44 ////////////////////////////////////////
  45 using namespace Kademlia;
  46 ////////////////////////////////////////
  47
  48 CRoutingBin::GlobalTrackingMap  CRoutingBin::s_globalContactIPs;
  49 CRoutingBin::GlobalTrackingMap  CRoutingBin::s_globalContactSubnets;
  50
  51 CRoutingBin::~CRoutingBin()
  52 {
  53         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
  54                 AdjustGlobalTracking((*it)->GetIPAddress(), false);
  55                 if (!m_dontDeleteContacts) {
  56                         delete *it;
  57                 }
  58         }
  59
  60         m_entries.clear();
  61 }
  62
  63 bool CRoutingBin::AddContact(CContact *contact)
  64 {
  65         wxASSERT(contact != NULL);
  66
  67         uint32_t sameSubnets = 0;
  68         // Check if we already have a contact with this ID in the list.
  69         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
  70                 if (contact->GetClientID() == (*it)->GetClientID()) {
  71                         return false;
  72                 }
  73                 if ((contact->GetIPAddress() & 0xFFFFFF00) == ((*it)->GetIPAddress() & 0xFFFFFF00)) {
  74                         sameSubnets++;
  75                 }
  76         }
  77         // Several checks to make sure that we don't store multiple contacts from the same IP or too many contacts from the same subnet
  78         // This is supposed to add a bit of protection against several attacks and raise the resource needs (IPs) for a successful contact on the attacker side
  79         // Such IPs are not banned from Kad, they still can index, search, etc so multiple KAD clients behind one IP still work
  80
  81         // no more than 1 KadID per IP
  82         uint32_t sameIPCount = 0;
  83         GlobalTrackingMap::const_iterator itIP = s_globalContactIPs.find(contact->GetIPAddress());
  84         if (itIP != s_globalContactIPs.end()) {
  85                 sameIPCount = itIP->second;
  86         }
  87         if (sameIPCount >= 1) {
  88                 AddDebugLogLineM(false, logKadRouting, wxT("Ignored kad contact (IP=") + Uint32_16toStringIP_Port(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress()), contact->GetUDPPort()) + wxT(") - too many contacts with the same IP (global)"));
  89                 return false;
  90         }
  91
  92         // no more than 2 IPs from the same /24 netmask in one bin, except if its a LANIP (if we don't accept LANIPs they already have been filtered before)
  93         if (sameSubnets >= 2 && !::IsLanIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress()))) {
  94                 AddDebugLogLineM(false, logKadRouting, wxT("Ignored kad contact (IP=") + Uint32_16toStringIP_Port(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress()), contact->GetUDPPort()) + wxT(") - too many contact with the same subnet in RoutingBin"));
  95                 return false;
  96         }
  97
  98         //  no more than 10 IPs from the same /24 netmask global, except if its a LANIP (if we don't accept LANIPs they already have been filtered before)
  99         uint32_t sameSubnetGlobalCount = 0;
 100         GlobalTrackingMap::const_iterator itSubnet = s_globalContactSubnets.find(contact->GetIPAddress() & 0xFFFFFF00);
 101         if (itSubnet != s_globalContactSubnets.end()) {
 102                 sameSubnetGlobalCount = itSubnet->second;
 103         }
 104         if (sameSubnetGlobalCount >= 10 && !::IsLanIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress()))) {
 105                 AddDebugLogLineM(false, logKadRouting, wxT("Ignored kad contact (IP=") + Uint32_16toStringIP_Port(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress()), contact->GetUDPPort()) + wxT(") - too many contacts with the same subnet (global)"));
 106                 return false;
 107         }
 108
 109         // If not full, add to the end of list
 110         if (m_entries.size() < K) {
 111                 m_entries.push_back(contact);
 112                 AdjustGlobalTracking(contact->GetIPAddress(), true);
 113                 return true;
 114         }
 115         return false;
 116 }
 117
 118 void CRoutingBin::SetAlive(CContact *contact)
 119 {
 120         wxASSERT(contact != NULL);
 121         // Check if we already have a contact with this ID in the list.
 122         CContact *test = GetContact(contact->GetClientID());
 123         wxASSERT(contact == test);
 124         if (test) {
 125                 // Mark contact as being alive.
 126                 test->UpdateType();
 127                 // Move to the end of the list
 128                 PushToBottom(test);
 129         }
 130 }
 131
 132 void CRoutingBin::SetTCPPort(uint32_t ip, uint16_t port, uint16_t tcpPort)
 133 {
 134         // Find contact with IP/Port
 135         for (ContactList::iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 136                 CContact *c = *it;
 137                 if ((ip == c->GetIPAddress()) && (port == c->GetUDPPort())) {
 138                         // Set TCPPort and mark as alive.
 139                         c->SetTCPPort(tcpPort);
 140                         c->UpdateType();
 141                         // Move to the end of the list
 142                         PushToBottom(c);
 143                         break;
 144                 }
 145         }
 146 }
 147
 148 CContact *CRoutingBin::GetContact(const CUInt128 &id) const throw()
 149 {
 150         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 151                 if ((*it)->GetClientID() == id) {
 152                         return *it;
 153                 }
 154         }
 155         return NULL;
 156 }
 157
 158 CContact *CRoutingBin::GetContact(uint32_t ip, uint16_t port, bool tcpPort) const throw()
 159 {
 160         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 161                 CContact *contact = *it;
 162                 if ((contact->GetIPAddress() == ip)
 163                     && ((!tcpPort && port == contact->GetUDPPort()) || (tcpPort && port == contact->GetTCPPort()) || port == 0)) {
 164                         return contact;
 165                 }
 166         }
 167         return NULL;
 168 }
 169
 170 void CRoutingBin::GetNumContacts(uint32_t& nInOutContacts, uint32_t& nInOutFilteredContacts, uint8_t minVersion) const
 171 {
 172         // count all nodes which meet the search criteria and also report those who don't
 173         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 174                 if ((*it)->GetVersion() >= minVersion) {
 175                         nInOutContacts++;
 176                 } else {
 177                         nInOutFilteredContacts++;
 178                 }
 179         }
 180 }
 181
 182 void CRoutingBin::GetEntries(ContactList *result, bool emptyFirst) const
 183 {
 184         // Clear results if requested first.
 185         if (emptyFirst) {
 186                 result->clear();
 187         }
 188
 189         // Append all entries to the results.
 190         if (m_entries.size() > 0) {
 191                 result->insert(result->end(), m_entries.begin(), m_entries.end());
 192         }
 193 }
 194
 195 void CRoutingBin::GetClosestTo(uint32_t maxType, const CUInt128 &target, uint32_t maxRequired, ContactMap *result, bool emptyFirst, bool inUse) const
 196 {
 197         // Empty list if requested.
 198         if (emptyFirst) {
 199                 result->clear();
 200         }
 201
 202         // No entries, no closest.
 203         if (m_entries.size() == 0) {
 204                 return;
 205         }
 206
 207         // First put results in sort order for target so we can insert them correctly.
 208         // We don't care about max results at this time.
 209         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 210                 if ((*it)->GetType() <= maxType && (*it)->IsIPVerified()) {
 211                         CUInt128 targetDistance((*it)->GetClientID() ^ target);
 212                         (*result)[targetDistance] = *it;
 213                         // This list will be used for an unknown time, Inc in use so it's not deleted.
 214                         if (inUse) {
 215                                 (*it)->IncUse();
 216                         }
 217                 }
 218         }
 219
 220         // Remove any extra results by least wanted first.
 221         while (result->size() > maxRequired) {
 222                 // Dec in use count.
 223                 if (inUse) {
 224                         (--result->end())->second->DecUse();
 225                 }
 226                 // Remove from results
 227                 result->erase(--result->end());
 228         }
 229 }
 230
 231 void CRoutingBin::AdjustGlobalTracking(uint32_t ip, bool increase)
 232 {
 233         // IP
 234         uint32_t sameIPCount = 0;
 235         GlobalTrackingMap::const_iterator itIP = s_globalContactIPs.find(ip);
 236         if (itIP != s_globalContactIPs.end()) {
 237                 sameIPCount = itIP->second;
 238         }
 239         if (increase) {
 240                 if (sameIPCount >= 1) {
 241                         AddDebugLogLineM(false, logKadRouting, wxT("Global IP Tracking inconsistency on increase (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(ip)) + wxT(")"));
 242                         wxFAIL;
 243                 }
 244                 sameIPCount++;
 245         } else /* if (!increase) */ {
 246                 if (sameIPCount == 0) {
 247                         AddDebugLogLineM(false, logKadRouting, wxT("Global IP Tracking inconsistency on decrease (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(ip)) + wxT(")"));
 248                         wxFAIL;
 249                 }
 250                 sameIPCount--;
 251         }
 252         if (sameIPCount != 0) {
 253                 s_globalContactIPs[ip] = sameIPCount;
 254         } else {
 255                 s_globalContactIPs.erase(ip);
 256         }
 257
 258         // Subnet
 259         uint32_t sameSubnetCount = 0;
 260         GlobalTrackingMap::const_iterator itSubnet = s_globalContactSubnets.find(ip & 0xFFFFFF00);
 261         if (itSubnet != s_globalContactSubnets.end()) {
 262                 sameSubnetCount = itSubnet->second;
 263         }
 264         if (increase) {
 265                 if (sameSubnetCount >= 10 && !::IsLanIP(wxUINT32_SWAP_ALWAYS(ip))) {
 266                         AddDebugLogLineM(false, logKadRouting, wxT("Global Subnet Tracking inconsistency on increase (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(ip)) + wxT("/24)"));
 267                         wxFAIL;
 268                 }
 269                 sameSubnetCount++;
 270         } else /* if (!increase) */ {
 271                 if (sameSubnetCount == 0) {
 272                         AddDebugLogLineM(false, logKadRouting, wxT("Global Subnet Tracking inconsistency on decrease (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(ip)) + wxT("/24)"));
 273                         wxFAIL;
 274                 }
 275                 sameSubnetCount--;
 276         }
 277         if (sameSubnetCount != 0) {
 278                 s_globalContactSubnets[ip & 0xFFFFFF00] = sameSubnetCount;
 279         } else {
 280                 s_globalContactSubnets.erase(ip & 0xFFFFFF00);
 281         }
 282 }
 283
 284 bool CRoutingBin::ChangeContactIPAddress(CContact *contact, uint32_t newIP)
 285 {
 286         // Called if we want to update an indexed contact with a new IP. We have to check if we actually allow such a change
 287         // and if adjust our tracking. Rejecting a change will in the worst case lead a node contact to become invalid and purged later,
 288         // but it also protects against a flood of malicous update requests from one IP which would be able to "reroute" all
 289         // contacts to itself and by that making them useless
 290         if (contact->GetIPAddress() == newIP) {
 291                 return true;
 292         }
 293
 294         wxASSERT(GetContact(contact->GetClientID()) == contact);
 295
 296         // no more than 1 KadID per IP
 297         uint32_t sameIPCount = 0;
 298         GlobalTrackingMap::const_iterator itIP = s_globalContactIPs.find(newIP);
 299         if (itIP != s_globalContactIPs.end()) {
 300                 sameIPCount = itIP->second;
 301         }
 302         if (sameIPCount >= 1) {
 303                 AddDebugLogLineM(false, logKadRouting, wxT("Rejected kad contact update on IP change (old IP=") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())) + wxT(", requested IP=") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(newIP)) + wxT(") - too many contacts with the same IP (global)"));
 304                 return false;
 305         }
 306
 307         if ((contact->GetIPAddress() & 0xFFFFFF00) != (newIP & 0xFFFFFF00)) {
 308                 // no more than 10 IPs from the same /24 netmask global, except if it's a LAN IP (if we don't accept LAN IPs they already have been filtered before)
 309                 uint32_t sameSubnetGlobalCount = 0;
 310                 GlobalTrackingMap::const_iterator itGlobalSubnet = s_globalContactSubnets.find(newIP & 0xFFFFFF00);
 311                 if (itGlobalSubnet != s_globalContactSubnets.end()) {
 312                         sameSubnetGlobalCount = itGlobalSubnet->second;
 313                 }
 314                 if (sameSubnetGlobalCount >= 10 && !::IsLanIP(wxUINT32_SWAP_ALWAYS(newIP))) {
 315                         AddDebugLogLineM(false, logKadRouting, wxT("Rejected kad contact update on IP change (old IP=") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())) + wxT(", requested IP=") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(newIP)) + wxT(") - too many contacts with the same Subnet (global)"));
 316                         return false;
 317                 }
 318
 319                 // no more than 2 IPs from the same /24 netmask in one bin, except if it's a LAN IP (if we don't accept LAN IPs they already have been filtered before)
 320                 uint32_t sameSubnets = 0;
 321                 // Check if we already have a contact with this ID in the list.
 322                 for (ContactList::const_iterator itContact = m_entries.begin(); itContact != m_entries.end(); ++itContact) {
 323                         if ((newIP & 0xFFFFFF00) == ((*itContact)->GetIPAddress() & 0xFFFFFF00)) {
 324                                 sameSubnets++;
 325                         }
 326                 }
 327                 if (sameSubnets >= 2 && !::IsLanIP(wxUINT32_SWAP_ALWAYS(newIP))) {
 328                         AddDebugLogLineM(false, logKadRouting, wxT("Rejected kad contact update on IP change (old IP=") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())) + wxT(", requested IP=") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(newIP)) + wxT(") - too many contacts with the same Subnet (local)"));
 329                         return false;
 330                 }
 331         }
 332
 333         // everything fine
 334         AddDebugLogLineM(false, logKadRouting, wxT("Index contact IP change allowed ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())) + wxT(" -> ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(newIP)));
 335         AdjustGlobalTracking(contact->GetIPAddress(), false);
 336         contact->SetIPAddress(newIP);
 337         AdjustGlobalTracking(contact->GetIPAddress(), true);
 338         return true;
 339 }
 340
 341 void CRoutingBin::PushToBottom(CContact *contact)
 342 {
 343         wxASSERT(GetContact(contact->GetClientID()) == contact);
 344
 345         RemoveContact(contact, true);
 346         m_entries.push_back(contact);
 347 }
 348
 349 CContact *CRoutingBin::GetRandomContact(uint32_t maxType, uint32_t minKadVersion) const throw()
 350 {
 351         if (m_entries.empty()) {
 352                 return NULL;
 353         }
 354
 355         // Find contact
 356         CContact *lastFit = NULL;
 357         uint32_t randomStartPos = GetRandomUint16() % m_entries.size();
 358         uint32_t index = 0;
 359
 360         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 361                 if ((*it)->GetType() <= maxType && (*it)->GetVersion() >= minKadVersion) {
 362                         if (index >= randomStartPos) {
 363                                 return *it;
 364                         } else {
 365                                 lastFit = *it;
 366                         }
 367                 }
 368                 index++;
 369         }
 370
 371         return lastFit;
 372 }
 373
 374 void CRoutingBin::SetAllContactsVerified()
 375 {
 376         for (ContactList::iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 377                 (*it)->SetIPVerified(true);
 378         }
 379 }