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