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) 2004-2008 aMule Project ( http://www.amule-project.net )
   6 // Copyright (C)2003 Barry Dunne (http://www.emule-project.net)
   7
   8 // This program is free software; you can redistribute it and/or
   9 // modify it under the terms of the GNU General Public License
  10 // as published by the Free Software Foundation; either
  11 // version 2 of the License, or (at your option) any later version.
  12
  13 // This program is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17
  18 // You should have received a copy of the GNU General Public License
  19 // along with this program; if not, write to the Free Software
  20 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  21
  22 // This work is based on the java implementation of the Kademlia protocol.
  23 // Kademlia: Peer-to-peer routing based on the XOR metric
  24 // Copyright (C) 2002  Petar Maymounkov [petar@post.harvard.edu]
  25 // http://kademlia.scs.cs.nyu.edu
  26
  27 // Note To Mods //
  28 /*
  29 Please do not change anything here and release it..
  30 There is going to be a new forum created just for the Kademlia side of the client..
  31 If you feel there is an error or a way to improve something, please
  32 post it in the forum first and let us look at it.. If it is a real improvement,
  33 it will be added to the offical client.. Changing something without knowing
  34 what all it does can cause great harm to the network if released in mass form..
  35 Any mod that changes anything within the Kademlia side will not be allowed to advertise
  36 there client on the eMule forum..
  37 */
  38
  39 #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::GetEntries(ContactList *result, bool emptyFirst) const
 171 {
 172         // Clear results if requested first.
 173         if (emptyFirst) {
 174                 result->clear();
 175         }
 176
 177         // Append all entries to the results.
 178         if (m_entries.size() > 0) {
 179                 result->insert(result->end(), m_entries.begin(), m_entries.end());
 180         }
 181 }
 182
 183 void CRoutingBin::GetClosestTo(uint32_t maxType, const CUInt128 &target, uint32_t maxRequired, ContactMap *result, bool emptyFirst, bool inUse) const
 184 {
 185         // Empty list if requested.
 186         if (emptyFirst) {
 187                 result->clear();
 188         }
 189
 190         // No entries, no closest.
 191         if (m_entries.size() == 0) {
 192                 return;
 193         }
 194
 195         // First put results in sort order for target so we can insert them correctly.
 196         // We don't care about max results at this time.
 197         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 198                 if ((*it)->GetType() <= maxType) {
 199                         CUInt128 targetDistance((*it)->GetClientID() ^ target);
 200                         (*result)[targetDistance] = *it;
 201                         // This list will be used for an unknown time, Inc in use so it's not deleted.
 202                         if (inUse) {
 203                                 (*it)->IncUse();
 204                         }
 205                 }
 206         }
 207
 208         // Remove any extra results by least wanted first.
 209         while (result->size() > maxRequired) {
 210                 // Dec in use count.
 211                 if (inUse) {
 212                         (--result->end())->second->DecUse();
 213                 }
 214                 // Remove from results
 215                 result->erase(--result->end());
 216         }
 217 }
 218
 219 void CRoutingBin::AdjustGlobalTracking(uint32_t ip, bool increase)
 220 {
 221         // IP
 222         uint32_t sameIPCount = 0;
 223         GlobalTrackingMap::const_iterator itIP = s_globalContactIPs.find(ip);
 224         if (itIP != s_globalContactIPs.end()) {
 225                 sameIPCount = itIP->second;
 226         }
 227         if (increase) {
 228                 if (sameIPCount >= 1) {
 229                         AddDebugLogLineM(false, logKadRouting, wxT("Global IP Tracking inconsistency on increase (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(ip)) + wxT(")"));
 230                         wxFAIL;
 231                 }
 232                 sameIPCount++;
 233         } else /* if (!increase) */ {
 234                 if (sameIPCount == 0) {
 235                         AddDebugLogLineM(false, logKadRouting, wxT("Global IP Tracking inconsistency on decrease (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(ip)) + wxT(")"));
 236                         wxFAIL;
 237                 }
 238                 sameIPCount--;
 239         }
 240         if (sameIPCount != 0) {
 241                 s_globalContactIPs[ip] = sameIPCount;
 242         } else {
 243                 s_globalContactIPs.erase(ip);
 244         }
 245
 246         // Subnet
 247         uint32_t sameSubnetCount = 0;
 248         GlobalTrackingMap::const_iterator itSubnet = s_globalContactSubnets.find(ip & 0xFFFFFF00);
 249         if (itSubnet != s_globalContactSubnets.end()) {
 250                 sameSubnetCount = itSubnet->second;
 251         }
 252         if (increase) {
 253                 if (sameSubnetCount >= 10 && !::IsLanIP(wxUINT32_SWAP_ALWAYS(ip))) {
 254                         AddDebugLogLineM(false, logKadRouting, wxT("Global Subnet Tracking inconsistency on increase (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(ip)) + wxT("/24)"));
 255                         wxFAIL;
 256                 }
 257                 sameSubnetCount++;
 258         } else /* if (!increase) */ {
 259                 if (sameSubnetCount == 0) {
 260                         AddDebugLogLineM(false, logKadRouting, wxT("Global Subnet Tracking inconsistency on decrease (") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(ip)) + wxT("/24)"));
 261                         wxFAIL;
 262                 }
 263                 sameSubnetCount--;
 264         }
 265         if (sameSubnetCount != 0) {
 266                 s_globalContactSubnets[ip & 0xFFFFFF00] = sameSubnetCount;
 267         } else {
 268                 s_globalContactSubnets.erase(ip & 0xFFFFFF00);
 269         }
 270 }
 271
 272 bool CRoutingBin::ChangeContactIPAddress(CContact *contact, uint32_t newIP)
 273 {
 274         // Called if we want to update an indexed contact with a new IP. We have to check if we actually allow such a change
 275         // and if adjust our tracking. Rejecting a change will in the worst case lead a node contact to become invalid and purged later,
 276         // but it also protects against a flood of malicous update requests from one IP which would be able to "reroute" all
 277         // contacts to itself and by that making them useless
 278         if (contact->GetIPAddress() == newIP) {
 279                 return true;
 280         }
 281
 282         wxASSERT(GetContact(contact->GetClientID()) == contact);
 283
 284         // no more than 1 KadID per IP
 285         uint32_t sameIPCount = 0;
 286         GlobalTrackingMap::const_iterator itIP = s_globalContactIPs.find(newIP);
 287         if (itIP != s_globalContactIPs.end()) {
 288                 sameIPCount = itIP->second;
 289         }
 290         if (sameIPCount >= 1) {
 291                 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)"));
 292                 return false;
 293         }
 294
 295         if ((contact->GetIPAddress() & 0xFFFFFF00) != (newIP & 0xFFFFFF00)) {
 296                 // 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)
 297                 uint32_t sameSubnetGlobalCount = 0;
 298                 GlobalTrackingMap::const_iterator itGlobalSubnet = s_globalContactSubnets.find(newIP & 0xFFFFFF00);
 299                 if (itGlobalSubnet != s_globalContactSubnets.end()) {
 300                         sameSubnetGlobalCount = itGlobalSubnet->second;
 301                 }
 302                 if (sameSubnetGlobalCount >= 10 && !::IsLanIP(wxUINT32_SWAP_ALWAYS(newIP))) {
 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 Subnet (global)"));
 304                         return false;
 305                 }
 306
 307                 // 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)
 308                 uint32_t sameSubnets = 0;
 309                 // Check if we already have a contact with this ID in the list.
 310                 for (ContactList::const_iterator itContact = m_entries.begin(); itContact != m_entries.end(); ++itContact) {
 311                         if ((newIP & 0xFFFFFF00) == ((*itContact)->GetIPAddress() & 0xFFFFFF00)) {
 312                                 sameSubnets++;
 313                         }
 314                 }
 315                 if (sameSubnets >= 2 && !::IsLanIP(wxUINT32_SWAP_ALWAYS(newIP))) {
 316                         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)"));
 317                         return false;
 318                 }
 319         }
 320
 321         // everything fine
 322         AddDebugLogLineM(false, logKadRouting, wxT("Index contact IP change allowed ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(contact->GetIPAddress())) + wxT(" -> ") + Uint32toStringIP(wxUINT32_SWAP_ALWAYS(newIP)));
 323         AdjustGlobalTracking(contact->GetIPAddress(), false);
 324         contact->SetIPAddress(newIP);
 325         AdjustGlobalTracking(contact->GetIPAddress(), true);
 326         return true;
 327 }
 328
 329 void CRoutingBin::PushToBottom(CContact *contact)
 330 {
 331         wxASSERT(GetContact(contact->GetClientID()) == contact);
 332
 333         RemoveContact(contact, true);
 334         m_entries.push_back(contact);
 335 }
 336
 337 CContact *CRoutingBin::GetRandomContact(uint32_t maxType, uint32_t minKadVersion) const throw()
 338 {
 339         if (m_entries.empty()) {
 340                 return NULL;
 341         }
 342
 343         // Find contact
 344         CContact *lastFit = NULL;
 345         uint32_t randomStartPos = GetRandomUint16() % m_entries.size();
 346         uint32_t index = 0;
 347
 348         for (ContactList::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
 349                 if ((*it)->GetType() <= maxType && (*it)->GetVersion() >= minKadVersion) {
 350                         if (index >= randomStartPos) {
 351                                 return *it;
 352                         } else {
 353                                 lastFit = *it;
 354                         }
 355                 }
 356                 index++;
 357         }
 358
 359         return lastFit;
 360 }