1 /* 2 * Copyright (C) 2009-2010 Big Muscle, http://strongdc.sf.net 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 17 */ 18 19 #include "stdafx.h" 20 #include "Constants.h" 21 #include "DHT.h" 22 #include "KBucket.h" 23 #include "Utils.h" 24 #include "dcpp/ClientManager.h" 25 26 namespace dht 27 { 28 29 // Set all new nodes' type to 3 to avoid spreading dead nodes.. Node(const UserPtr & u)30 Node::Node(const UserPtr& u) : 31 OnlineUser(u, *DHT::getInstance(), 0), created(GET_TICK()), expires(0), type(3), ipVerified(false), online(false) 32 { 33 } 34 getUdpKey() const35 CID Node::getUdpKey() const 36 { 37 // if our external IP changed from the last time, we can't encrypt packet with this key 38 if(DHT::getInstance()->getLastExternalIP() == key.ip) 39 return key.key; 40 else 41 return CID(); 42 } 43 setUdpKey(const CID & _key)44 void Node::setUdpKey(const CID& _key) 45 { 46 // store key with our current IP address 47 key.ip = DHT::getInstance()->getLastExternalIP(); 48 key.key = _key; 49 } 50 setAlive()51 void Node::setAlive() 52 { 53 // long existing nodes will probably be there for another long time 54 uint64_t hours = (GET_TICK() - created) / 1000 / 60 / 60; 55 switch(hours) 56 { 57 case 0: 58 type = 2; 59 expires = GET_TICK() + (NODE_EXPIRATION / 2); 60 break; 61 case 1: 62 type = 1; 63 expires = GET_TICK() + (uint64_t)(NODE_EXPIRATION / 1.5); 64 break; 65 default: // long existing nodes 66 type = 0; 67 expires = GET_TICK() + NODE_EXPIRATION; 68 } 69 } 70 setTimeout(uint64_t now)71 void Node::setTimeout(uint64_t now) 72 { 73 if(type == 4) 74 return; 75 76 type++; 77 expires = now + NODE_RESPONSE_TIMEOUT; 78 } 79 80 KBucket(void)81 KBucket::KBucket(void) 82 { 83 } 84 ~KBucket(void)85 KBucket::~KBucket(void) 86 { 87 // empty table 88 for(NodeList::iterator it = nodes.begin(); it != nodes.end(); ++it) 89 { 90 Node::Ptr& node = *it; 91 if(node->isOnline()) 92 { 93 ClientManager::getInstance()->putOffline(node.get()); 94 node->dec(); 95 } 96 } 97 nodes.clear(); 98 } 99 100 /* 101 * Creates new (or update existing) node which is NOT added to our routing table 102 */ createNode(const UserPtr & u,const string & ip,uint16_t port,bool update,bool isUdpKeyValid)103 Node::Ptr KBucket::createNode(const UserPtr& u, const string& ip, uint16_t port, bool update, bool isUdpKeyValid) 104 { 105 if(u->isSet(User::DHT)) // is this user already known in DHT? 106 { 107 Node::Ptr node = NULL; 108 109 // no online node found, try get from routing table 110 for(NodeList::iterator it = nodes.begin(); it != nodes.end(); ++it) 111 { 112 if(u->getCID() == (*it)->getUser()->getCID()) 113 { 114 node = *it; 115 116 // put node at the end of the list 117 nodes.erase(it); 118 nodes.push_back(node); 119 break; 120 } 121 } 122 123 if(node == NULL && u->isOnline()) 124 { 125 // try to get node from ClientManager (user can be online but not in our routing table) 126 // this fixes the bug with DHT node online twice 127 node = (Node*)ClientManager::getInstance()->findDHTNode(u->getCID()); 128 node = node.get(); 129 } 130 131 if(node != NULL) 132 { 133 // fine, node found, update it and return it 134 if(update) 135 { 136 string oldIp = node->getIdentity().getIp(); 137 string oldPort = node->getIdentity().getUdpPort(); 138 if(ip != oldIp || static_cast<uint16_t>(Util::toInt(oldPort)) != port) 139 { 140 node->setIpVerified(false); 141 142 // TODO: don't allow update when new IP already exists for different node 143 144 // erase old IP and remember new one 145 ipMap.erase(oldIp + ":" + oldPort); 146 ipMap.insert(ip + ":" + Util::toString(port)); 147 } 148 149 if(!node->isIpVerified()) 150 node->setIpVerified(isUdpKeyValid); 151 152 node->setAlive(); 153 node->getIdentity().setIp(ip); 154 node->getIdentity().setUdpPort(Util::toString(port)); 155 156 DHT::getInstance()->setDirty(); 157 } 158 159 return node; 160 } 161 } 162 163 u->setFlag(User::DHT); 164 165 Node::Ptr node(new Node(u)); 166 node->getIdentity().setIp(ip); 167 node->getIdentity().setUdpPort(Util::toString(port)); 168 node->setIpVerified(isUdpKeyValid); 169 return node; 170 } 171 172 /* 173 * Adds node to routing table 174 */ insert(const Node::Ptr & node)175 bool KBucket::insert(const Node::Ptr& node) 176 { 177 if(node->isInList) 178 return true; // node is already in the table 179 180 string ip = node->getIdentity().getIp(); 181 string port = node->getIdentity().getUdpPort(); 182 183 // allow only one same IP:port 184 bool isAcceptable = (ipMap.find(ip + ":" + port) == ipMap.end()); 185 186 if((nodes.size() < (K * ID_BITS)) && isAcceptable) 187 { 188 nodes.push_back(node); 189 node->isInList = true; 190 ipMap.insert(ip + ":" + port); 191 192 if(DHT::getInstance()) 193 DHT::getInstance()->setDirty(); 194 195 return true; 196 } 197 198 return isAcceptable; 199 } 200 201 /* 202 * Finds "max" closest nodes and stores them to the list 203 */ getClosestNodes(const CID & cid,Node::Map & closest,unsigned int max,uint8_t maxType) const204 void KBucket::getClosestNodes(const CID& cid, Node::Map& closest, unsigned int max, uint8_t maxType) const 205 { 206 for(NodeList::const_iterator it = nodes.begin(); it != nodes.end(); ++it) 207 { 208 const Node::Ptr& node = *it; 209 if(node->getType() <= maxType && node->isIpVerified() && !node->getUser()->isSet(User::PASSIVE)) 210 { 211 CID distance = Utils::getDistance(cid, node->getUser()->getCID()); 212 213 if(closest.size() < max) 214 { 215 // just insert 216 closest.insert(std::make_pair(distance, node)); 217 } 218 else 219 { 220 // not enough room, so insert only closer nodes 221 if(distance < closest.rbegin()->first) // "closest" is sorted map, so just compare with last node 222 { 223 closest.erase(closest.rbegin()->first); 224 closest.insert(std::make_pair(distance, node)); 225 } 226 } 227 } 228 } 229 } 230 231 /* 232 * Remove dead nodes 233 */ checkExpiration(uint64_t currentTime)234 bool KBucket::checkExpiration(uint64_t currentTime) 235 { 236 bool dirty = false; 237 238 // we should ping oldest node from every bucket here 239 // but since we have only one bucket now, simulate it by pinging more nodes 240 unsigned int pingCount = max(K, min((int)2 * K, (int)(nodes.size() / (K * 10)) + 1)); // <-- pings 10 - 20 oldest nodes 241 unsigned int pinged = 0; 242 dcdrun(unsigned int removed = 0); 243 244 // first, remove dead nodes 245 NodeList::iterator i = nodes.begin(); 246 while(i != nodes.end()) 247 { 248 Node::Ptr& node = *i; 249 250 if(node->getType() == 4 && node->expires > 0 && node->expires <= currentTime) 251 { 252 if(node->unique(2)) 253 { 254 // node is dead, remove it 255 string ip = node->getIdentity().getIp(); 256 string port = node->getIdentity().getUdpPort(); 257 ipMap.erase(ip + ":" + port); 258 259 if(node->isOnline()) 260 { 261 ClientManager::getInstance()->putOffline(node.get()); 262 node->dec(); 263 } 264 265 i = nodes.erase(i); 266 dirty = true; 267 268 dcdrun(removed++); 269 } 270 else 271 { 272 ++i; 273 } 274 275 continue; 276 } 277 278 if(node->expires == 0) 279 node->expires = currentTime; 280 281 // select the oldest expired node 282 if(pinged < pingCount && node->getType() < 4 && node->expires <= currentTime) 283 { 284 // ping the oldest (expired) node 285 node->setTimeout(currentTime); 286 DHT::getInstance()->info(node->getIdentity().getIp(), static_cast<uint16_t>(Util::toInt(node->getIdentity().getUdpPort())), DHT::PING, node->getUser()->getCID(), node->getUdpKey()); 287 pinged++; 288 } 289 290 ++i; 291 } 292 293 #ifdef _DEBUG 294 int verified = 0; int types[5] = { 0 }; 295 for(NodeList::const_iterator j = nodes.begin(); j != nodes.end(); ++j) 296 { 297 Node::Ptr n = *j; 298 if(n->isIpVerified()) verified++; 299 300 dcassert(n->getType() >= 0 && n->getType() <= 4); 301 types[n->getType()]++; 302 } 303 304 dcdebug("DHT Nodes: %d (%d verified), Types: %d/%d/%d/%d/%d, pinged %d of %d, removed %d\n", nodes.size(), verified, types[0], types[1], types[2], types[3], types[4], pinged, pingCount, removed); 305 #endif 306 307 return dirty; 308 } 309 310 /* 311 * Loads existing nodes from disk 312 */ loadNodes(SimpleXML & xml)313 void KBucket::loadNodes(SimpleXML& xml) 314 { 315 xml.resetCurrentChild(); 316 if(xml.findChild("Nodes")) 317 { 318 xml.stepIn(); 319 while(xml.findChild("Node")) 320 { 321 CID cid = CID(xml.getChildAttrib("CID")); 322 string i4 = xml.getChildAttrib("I4"); 323 uint16_t u4 = static_cast<uint16_t>(xml.getIntChildAttrib("U4")); 324 325 if(Utils::isGoodIPPort(i4, u4)) 326 { 327 UDPKey udpKey; 328 string key = xml.getChildAttrib("key"); 329 string keyIp = xml.getChildAttrib("keyIP"); 330 331 if(!key.empty() && !keyIp.empty()) 332 { 333 udpKey.key = CID(key); 334 udpKey.ip = keyIp; 335 } 336 337 //addUser(cid, i4, u4); 338 BootstrapManager::getInstance()->addBootstrapNode(i4, u4, cid, udpKey); 339 } 340 } 341 xml.stepOut(); 342 } 343 } 344 345 /* 346 * Save bootstrap nodes to disk 347 */ saveNodes(SimpleXML & xml)348 void KBucket::saveNodes(SimpleXML& xml) 349 { 350 xml.addTag("Nodes"); 351 xml.stepIn(); 352 353 // get 50 random nodes to bootstrap from them next time 354 Node::Map closestToMe; 355 getClosestNodes(CID::generate(), closestToMe, 50, 3); 356 357 for(Node::Map::const_iterator j = closestToMe.begin(); j != closestToMe.end(); ++j) 358 { 359 const Node::Ptr& node = j->second; 360 361 xml.addTag("Node"); 362 xml.addChildAttrib("CID", node->getUser()->getCID().toBase32()); 363 xml.addChildAttrib("type", node->getType()); 364 xml.addChildAttrib("verified", node->isIpVerified()); 365 366 if(!node->getUDPKey().key.isZero() && !node->getUDPKey().ip.empty()) 367 { 368 xml.addChildAttrib("key", node->getUDPKey().key.toBase32()); 369 xml.addChildAttrib("keyIP", node->getUDPKey().ip); 370 } 371 372 StringMap params; 373 node->getIdentity().getParams(params, Util::emptyString, false, true); 374 375 for(StringMap::const_iterator i = params.begin(); i != params.end(); ++i) 376 xml.addChildAttrib(i->first, i->second); 377 } 378 379 xml.stepOut(); 380 } 381 382 383 } 384