src/dht/gnunet-service-dht_neighbours.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2009, 2010, 2011 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file dht/gnunet-service-dht_neighbours.c
  23  * @brief GNUnet DHT service's bucket and neighbour management code
  24  * @author Christian Grothoff
  25  * @author Nathan Evans
  26  */
  27
  28 #include "platform.h"
  29 #include "gnunet_block_lib.h"
  30 #include "gnunet_util_lib.h"
  31 #include "gnunet_protocols.h"
  32 #include "gnunet_nse_service.h"
  33 #include "gnunet_core_service.h"
  34 #include "gnunet_datacache_lib.h"
  35 #include "gnunet_transport_service.h"
  36 #include "gnunet_hello_lib.h"
  37 #include "gnunet_dht_service.h"
  38 #include "gnunet_statistics_service.h"
  39 #include "dht.h"
  40 #include <fenv.h>
  41
  42 /**
  43  * How many buckets will we allow total.
  44  */
  45 #define MAX_BUCKETS sizeof (GNUNET_HashCode) * 8
  46
  47 /**
  48  * What is the maximum number of peers in a given bucket.
  49  */
  50 #define DEFAULT_BUCKET_SIZE 4
  51
  52
  53 /**
  54  * Linked list of messages to send to a particular other peer.
  55  */
  56 struct P2PPendingMessage
  57 {
  58   /**
  59    * Pointer to next item in the list
  60    */
  61   struct P2PPendingMessage *next;
  62
  63   /**
  64    * Pointer to previous item in the list
  65    */
  66   struct P2PPendingMessage *prev;
  67
  68   /**
  69    * Message importance level.
  70    */
  71   unsigned int importance;
  72
  73   /**
  74    * Time when this request was scheduled to be sent.
  75    */
  76   struct GNUNET_TIME_Absolute scheduled;
  77
  78   /**
  79    * How long to wait before sending message.
  80    */
  81   struct GNUNET_TIME_Relative timeout;
  82
  83   /**
  84    * Actual message to be sent, allocated at the end of the struct:
  85    * // msg = (cast) &pm[1];
  86    * // memcpy (&pm[1], data, len);
  87    */
  88   const struct GNUNET_MessageHeader *msg;
  89
  90 };
  91
  92
  93 /**
  94  * Entry for a peer in a bucket.
  95  */
  96 struct PeerInfo
  97 {
  98   /**
  99    * Next peer entry (DLL)
 100    */
 101   struct PeerInfo *next;
 102
 103   /**
 104    *  Prev peer entry (DLL)
 105    */
 106   struct PeerInfo *prev;
 107
 108   /**
 109    * Count of outstanding messages for peer.
 110    */
 111   unsigned int pending_count;
 112
 113   /**
 114    * Head of pending messages to be sent to this peer.
 115    */
 116   struct P2PPendingMessage *head;
 117
 118   /**
 119    * Tail of pending messages to be sent to this peer.
 120    */
 121   struct P2PPendingMessage *tail;
 122
 123   /**
 124    * Core handle for sending messages to this peer.
 125    */
 126   struct GNUNET_CORE_TransmitHandle *th;
 127
 128   /**
 129    * Preference update context
 130    */
 131   struct GNUNET_CORE_InformationRequestContext *info_ctx;
 132
 133   /**
 134    * Task for scheduling message sends.
 135    */
 136   GNUNET_SCHEDULER_TaskIdentifier send_task;
 137
 138   /**
 139    * Task for scheduling preference updates
 140    */
 141   GNUNET_SCHEDULER_TaskIdentifier preference_task;
 142
 143   /**
 144    * What is the identity of the peer?
 145    */
 146   struct GNUNET_PeerIdentity id;
 147
 148 #if 0
 149   /**
 150    * What is the average latency for replies received?
 151    */
 152   struct GNUNET_TIME_Relative latency;
 153
 154   /**
 155    * Transport level distance to peer.
 156    */
 157   unsigned int distance;
 158 #endif
 159
 160 };
 161
 162
 163 /**
 164  * Peers are grouped into buckets.
 165  */
 166 struct PeerBucket
 167 {
 168   /**
 169    * Head of DLL
 170    */
 171   struct PeerInfo *head;
 172
 173   /**
 174    * Tail of DLL
 175    */
 176   struct PeerInfo *tail;
 177
 178   /**
 179    * Number of peers in the bucket.
 180    */
 181   unsigned int peers_size;
 182 };
 183
 184
 185 /**
 186  * The lowest currently used bucket.
 187  */
 188 static unsigned int lowest_bucket;      /* Initially equal to MAX_BUCKETS - 1 */
 189
 190 /**
 191  * The buckets (Kademlia routing table, complete with growth).
 192  * Array of size MAX_BUCKET_SIZE.
 193  */
 194 static struct PeerBucket k_buckets[MAX_BUCKETS];
 195
 196 /**
 197  * Hash map of all known peers, for easy removal from k_buckets on disconnect.
 198  */
 199 static struct GNUNET_CONTAINER_MultiHashMap *all_known_peers;
 200
 201 /**
 202  * Maximum size for each bucket.
 203  */
 204 static unsigned int bucket_size = DEFAULT_BUCKET_SIZE;
 205
 206
 207
 208 /**
 209  * Method called whenever a peer connects.
 210  *
 211  * @param cls closure
 212  * @param peer peer identity this notification is about
 213  * @param atsi performance data
 214  */
 215 static void
 216 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer,
 217                      const struct GNUNET_TRANSPORT_ATS_Information *atsi)
 218 {
 219   struct PeerInfo *ret;
 220   int peer_bucket;
 221
 222   /* Check for connect to self message */
 223   if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
 224     return;
 225
 226 #if DEBUG_DHT
 227   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 228               "%s:%s Receives core connect message for peer %s distance %d!\n",
 229               my_short_id, "dht", GNUNET_i2s (peer), distance);
 230 #endif
 231
 232   if (GNUNET_YES ==
 233       GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
 234                                               &peer->hashPubKey))
 235   {
 236 #if DEBUG_DHT
 237     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 238                 "%s:%s Received %s message for peer %s, but already have peer in RT!",
 239                 my_short_id, "DHT", "CORE CONNECT", GNUNET_i2s (peer));
 240 #endif
 241     GNUNET_break (0);
 242     return;
 243   }
 244
 245   peer_bucket = find_current_bucket (&peer->hashPubKey);
 246   GNUNET_assert (peer_bucket >= lowest_bucket);
 247   GNUNET_assert (peer_bucket < MAX_BUCKETS);
 248   ret = GNUNET_malloc (sizeof (struct PeerInfo));
 249 #if 0
 250   ret->latency = latency;
 251   ret->distance = distance;
 252 #endif
 253   ret->id = *peer;
 254   GNUNET_CONTAINER_DLL_insert_after (k_buckets[peer_bucket].head,
 255                                      k_buckets[peer_bucket].tail,
 256                                      k_buckets[peer_bucket].tail, ret);
 257   k_buckets[peer_bucket].peers_size++;
 258   if ((GNUNET_CRYPTO_hash_matching_bits
 259        (&my_identity.hashPubKey, &peer->hashPubKey) > 0) &&
 260       (k_buckets[peer_bucket].peers_size <= bucket_size))
 261     ret->preference_task =
 262         GNUNET_SCHEDULER_add_now (&update_core_preference, ret);
 263   if ((k_buckets[lowest_bucket].peers_size) >= bucket_size)
 264     enable_next_bucket ();
 265   newly_found_peers++;
 266   GNUNET_CONTAINER_multihashmap_put (all_known_peers, &peer->hashPubKey, ret,
 267                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 268   increment_stats (STAT_PEERS_KNOWN);
 269
 270 #if DEBUG_DHT
 271   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 272               "%s:%s Adding peer to routing list: %s\n", my_short_id, "DHT",
 273               ret == NULL ? "NOT ADDED" : "PEER ADDED");
 274 #endif
 275 }
 276
 277
 278 /**
 279  * Method called whenever a peer disconnects.
 280  *
 281  * @param cls closure
 282  * @param peer peer identity this notification is about
 283  */
 284 static void
 285 handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer)
 286 {
 287   struct PeerInfo *to_remove;
 288   int current_bucket;
 289
 290   /* Check for disconnect from self message */
 291   if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
 292     return;
 293 #if DEBUG_DHT
 294   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 295               "%s:%s: Received peer disconnect message for peer `%s' from %s\n",
 296               my_short_id, "DHT", GNUNET_i2s (peer), "CORE");
 297 #endif
 298
 299   if (GNUNET_YES !=
 300       GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
 301                                               &peer->hashPubKey))
 302   {
 303     GNUNET_break (0);
 304 #if DEBUG_DHT
 305     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 306                 "%s:%s: do not have peer `%s' in RT, can't disconnect!\n",
 307                 my_short_id, "DHT", GNUNET_i2s (peer));
 308 #endif
 309     return;
 310   }
 311   increment_stats (STAT_DISCONNECTS);
 312   GNUNET_assert (GNUNET_CONTAINER_multihashmap_contains
 313                  (all_known_peers, &peer->hashPubKey));
 314   to_remove =
 315       GNUNET_CONTAINER_multihashmap_get (all_known_peers, &peer->hashPubKey);
 316   GNUNET_assert (to_remove != NULL);
 317   if (NULL != to_remove->info_ctx)
 318   {
 319     GNUNET_CORE_peer_change_preference_cancel (to_remove->info_ctx);
 320     to_remove->info_ctx = NULL;
 321   }
 322   GNUNET_assert (0 ==
 323                  memcmp (peer, &to_remove->id,
 324                          sizeof (struct GNUNET_PeerIdentity)));
 325   current_bucket = find_current_bucket (&to_remove->id.hashPubKey);
 326   delete_peer (to_remove, current_bucket);
 327 }
 328
 329
 330
 331 /**
 332  * Initialize neighbours subsystem.
 333  */
 334 void
 335 GST_NEIGHBOURS_init ()
 336 {
 337 }
 338
 339
 340 /**
 341  * Shutdown neighbours subsystem.
 342  */
 343 void
 344 GST_NEIGHBOURS_done ()
 345 {
 346 }
 347
 348
 349
 350
 351
 352
 353 /* end of gnunet-service-dht_neighbours.c */