1 // libTorrent - BitTorrent library
2 // Copyright (C) 2005-2011, Jari Sundell
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17 //
18 // In addition, as a special exception, the copyright holders give
19 // permission to link the code of portions of this program with the
20 // OpenSSL library under certain conditions as described in each
21 // individual source file, and distribute linked combinations
22 // including the two.
23 //
24 // You must obey the GNU General Public License in all respects for
25 // all of the code used other than OpenSSL.  If you modify file(s)
26 // with this exception, you may extend this exception to your version
27 // of the file(s), but you are not obligated to do so.  If you do not
28 // wish to do so, delete this exception statement from your version.
29 // If you delete this exception statement from all source files in the
30 // program, then also delete it here.
31 //
32 // Contact:  Jari Sundell <jaris@ifi.uio.no>
33 //
34 //           Skomakerveien 33
35 //           3185 Skoppum, NORWAY
36 
37 #ifndef LIBTORRENT_DHT_BUCKET_H
38 #define LIBTORRENT_DHT_BUCKET_H
39 
40 #include <list>
41 
42 #include "globals.h"
43 
44 #include "torrent/hash_string.h"
45 #include "torrent/object_raw_bencode.h"
46 
47 namespace torrent {
48 
49 class DhtNode;
50 
51 // A container holding a small number of nodes that fall in a given binary
52 // partition of the 160-bit ID space (i.e. the range ID1..ID2 where ID2-ID1+1 is
53 // a power of 2.)
54 class DhtBucket : private std::vector<DhtNode*> {
55 public:
56   static const unsigned int num_nodes = 8;
57 
58   typedef std::vector<DhtNode*>      base_type;
59 
60   using base_type::const_iterator;
61   using base_type::iterator;
62 
63   using base_type::begin;
64   using base_type::end;
65   using base_type::size;
66   using base_type::empty;
67 
68   DhtBucket(const HashString& begin, const HashString& end);
69 
70   // Add new node. Does NOT set node's bucket automatically (to allow adding a
71   // node to multiple buckets, with only one "main" bucket.)
72   void                add_node(DhtNode* n);
73 
74   void                remove_node(DhtNode* n);
75 
76   // Bucket's ID range functions.
77   const HashString&   id_range_begin() const                  { return m_begin; }
78   HashString&         id_range_begin()                        { return m_begin; }
79   const HashString&   id_range_end() const                    { return m_end; }
80 
81   bool                is_in_range(const HashString& id) const { return m_begin <= id && id <= m_end; }
82 
83   // Find middle or random ID in bucket.
84   void                get_mid_point(HashString* middle) const;
85   void                get_random_id(HashString* rand_id) const;
86 
87   // Node counts and bucket stats.
88   bool                is_full() const                         { return size() >= num_nodes; }
89   bool                has_space() const                       { return !is_full() || num_bad() > 0; }
90   unsigned int        num_good() const                        { return m_good; }
91   unsigned int        num_bad() const                         { return m_bad; }
92 
93   unsigned int        age() const                             { return cachedTime.seconds() - m_lastChanged; }
94   void                touch()                                 { m_lastChanged = cachedTime.seconds(); }
95   void                set_time(int32_t time)                  { m_lastChanged = time; }
96 
97   // Called every 15 minutes after updating nodes.
98   void                update();
99 
100   // Return candidate for replacement (a bad node or the oldest node); may
101   // return end() unless has_space() is true.
102   iterator            find_replacement_candidate(bool onlyOldest = false);
103 
104   // Split the bucket in two and redistribute nodes. Returned bucket is the
105   // lower half, "this" bucket keeps the upper half.   Sets parent/child so
106   // that the bucket the given ID falls in is the child.
107   DhtBucket*          split(const HashString& id);
108 
109   // Parent and child buckets.  Parent is the adjacent bucket with double the
110   // ID width, child the adjacent bucket with half the width (except the very
111   // last child which has the same width.)
112   DhtBucket*          parent() const                          { return m_parent; }
113   DhtBucket*          child() const                           { return m_child; }
114 
115   // Return a full bucket's worth of compact node data. If this bucket is not
116   // full, it uses nodes from the child/parent buckets until we have enough.
117   raw_string          full_bucket();
118 
119   // Called by the DhtNode on its bucket to update good/bad node counts.
120   void                node_now_good(bool was_bad);
121   void                node_now_bad(bool was_good);
122 
123 private:
124   void                count();
125 
126   void                build_full_cache();
127 
128   DhtBucket*          m_parent;
129   DhtBucket*          m_child;
130 
131   int32_t             m_lastChanged;
132 
133   unsigned int        m_good;
134   unsigned int        m_bad;
135 
136   size_t              m_fullCacheLength;
137 
138   // These are 40 bytes together, so might as well put them last.
139   // m_end is const because it is used as key for the DhtRouter routing table
140   // map, which would be inconsistent if m_end were changed carelessly.
141   HashString          m_begin;
142   const HashString    m_end;
143 
144   char                m_fullCache[num_nodes * 26];
145 };
146 
147 // Helper class to recursively follow a chain of buckets.  It first recurses
148 // into the bucket's children since they are by definition closer to the bucket,
149 // then continues with the bucket's parents.
150 class DhtBucketChain {
151 public:
152   DhtBucketChain(const DhtBucket* b) : m_restart(b), m_cur(b) { }
153 
154   const DhtBucket*          bucket()                          { return m_cur; }
155   const DhtBucket*          next();
156 
157 private:
158   const DhtBucket*          m_restart;
159   const DhtBucket*          m_cur;
160 };
161 
162 inline void
163 DhtBucket::node_now_good(bool was_bad) {
164   m_bad -= was_bad;
165   m_good++;
166 }
167 
168 inline void
169 DhtBucket::node_now_bad(bool was_good) {
170   m_good -= was_good;
171   m_bad++;
172 }
173 
174 inline raw_string
175 DhtBucket::full_bucket() {
176   if (!m_fullCacheLength)
177     build_full_cache();
178 
179   return raw_string(m_fullCache, m_fullCacheLength);
180 }
181 
182 inline const DhtBucket*
183 DhtBucketChain::next() {
184   // m_restart is clear when we're done recursing into the children and
185   // follow the parents instead.
186   if (m_restart == NULL) {
187     m_cur = m_cur->parent();
188 
189   } else {
190     m_cur = m_cur->child();
191 
192     if (m_cur == NULL) {
193       m_cur = m_restart->parent();
194       m_restart = NULL;
195     }
196   }
197 
198   return m_cur;
199 }
200 
201 }
202 
203 #endif
204