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