2 This file is part of GNUnet.
3 (C) 2009, 2010, 2011 Christian Grothoff (and other contributing authors)
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.
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.
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.
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
29 #include "gnunet_block_lib.h"
30 #include "gnunet_util_lib.h"
31 #include "gnunet_hello_lib.h"
32 #include "gnunet_constants.h"
33 #include "gnunet_protocols.h"
34 #include "gnunet_nse_service.h"
35 #include "gnunet_ats_service.h"
36 #include "gnunet_core_service.h"
37 #include "gnunet_datacache_lib.h"
38 #include "gnunet_transport_service.h"
39 #include "gnunet_hello_lib.h"
40 #include "gnunet_dht_service.h"
41 #include "gnunet_statistics_service.h"
42 #include "gnunet-service-dht.h"
43 #include "gnunet-service-dht_clients.h"
44 #include "gnunet-service-dht_datacache.h"
45 #include "gnunet-service-dht_hello.h"
46 #include "gnunet-service-dht_neighbours.h"
47 #include "gnunet-service-dht_nse.h"
48 #include "gnunet-service-dht_routing.h"
53 * How many buckets will we allow total.
55 #define MAX_BUCKETS sizeof (struct GNUNET_HashCode) * 8
58 * What is the maximum number of peers in a given bucket.
60 #define DEFAULT_BUCKET_SIZE 8
63 * Desired replication level for FIND PEER requests
65 #define FIND_PEER_REPLICATION_LEVEL 4
68 * Maximum allowed replication level for all requests.
70 #define MAXIMUM_REPLICATION_LEVEL 16
73 * Maximum allowed number of pending messages per peer.
75 #define MAXIMUM_PENDING_PER_PEER 64
78 * How often to update our preference levels for peers in our routing tables.
80 #define DHT_DEFAULT_PREFERENCE_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
83 * How long at least to wait before sending another find peer request.
85 #define DHT_MINIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
88 * How long at most to wait before sending another find peer request.
90 #define DHT_MAXIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
93 * How long at most to wait for transmission of a GET request to another peer?
95 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
98 * Should routing details be logged to stderr (for debugging)?
100 #define LOG_ROUTE_DETAILS_STDERR GNUNET_YES
103 GNUNET_NETWORK_STRUCT_BEGIN
108 struct PeerPutMessage
111 * Type: GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
113 struct GNUNET_MessageHeader header;
118 uint32_t options GNUNET_PACKED;
123 uint32_t type GNUNET_PACKED;
128 uint32_t hop_count GNUNET_PACKED;
131 * Replication level for this message
133 uint32_t desired_replication_level GNUNET_PACKED;
136 * Length of the PUT path that follows (if tracked).
138 uint32_t put_path_length GNUNET_PACKED;
141 * When does the content expire?
143 struct GNUNET_TIME_AbsoluteNBO expiration_time;
146 * Bloomfilter (for peer identities) to stop circular routes
148 char bloomfilter[DHT_BLOOM_SIZE];
151 * The key we are storing under.
153 struct GNUNET_HashCode key;
155 /* put path (if tracked) */
165 struct PeerResultMessage
168 * Type: GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
170 struct GNUNET_MessageHeader header;
175 uint32_t type GNUNET_PACKED;
178 * Length of the PUT path that follows (if tracked).
180 uint32_t put_path_length GNUNET_PACKED;
183 * Length of the GET path that follows (if tracked).
185 uint32_t get_path_length GNUNET_PACKED;
188 * When does the content expire?
190 struct GNUNET_TIME_AbsoluteNBO expiration_time;
193 * The key of the corresponding GET request.
195 struct GNUNET_HashCode key;
197 /* put path (if tracked) */
199 /* get path (if tracked) */
209 struct PeerGetMessage
212 * Type: GNUNET_MESSAGE_TYPE_DHT_P2P_GET
214 struct GNUNET_MessageHeader header;
219 uint32_t options GNUNET_PACKED;
222 * Desired content type.
224 uint32_t type GNUNET_PACKED;
229 uint32_t hop_count GNUNET_PACKED;
232 * Desired replication level for this request.
234 uint32_t desired_replication_level GNUNET_PACKED;
237 * Size of the extended query.
239 uint32_t xquery_size;
242 * Bloomfilter mutator.
247 * Bloomfilter (for peer identities) to stop circular routes
249 char bloomfilter[DHT_BLOOM_SIZE];
252 * The key we are looking for.
254 struct GNUNET_HashCode key;
258 /* result bloomfilter */
261 GNUNET_NETWORK_STRUCT_END
264 * Linked list of messages to send to a particular other peer.
266 struct P2PPendingMessage
269 * Pointer to next item in the list
271 struct P2PPendingMessage *next;
274 * Pointer to previous item in the list
276 struct P2PPendingMessage *prev;
279 * Message importance level. FIXME: used? useful?
281 unsigned int importance;
284 * When does this message time out?
286 struct GNUNET_TIME_Absolute timeout;
289 * Actual message to be sent, allocated at the end of the struct:
290 * // msg = (cast) &pm[1];
291 * // memcpy (&pm[1], data, len);
293 const struct GNUNET_MessageHeader *msg;
299 * Entry for a peer in a bucket.
304 * Next peer entry (DLL)
306 struct PeerInfo *next;
309 * Prev peer entry (DLL)
311 struct PeerInfo *prev;
314 * Count of outstanding messages for peer.
316 unsigned int pending_count;
319 * Head of pending messages to be sent to this peer.
321 struct P2PPendingMessage *head;
324 * Tail of pending messages to be sent to this peer.
326 struct P2PPendingMessage *tail;
329 * Core handle for sending messages to this peer.
331 struct GNUNET_CORE_TransmitHandle *th;
334 * Task for scheduling preference updates
336 GNUNET_SCHEDULER_TaskIdentifier preference_task;
339 * What is the identity of the peer?
341 struct GNUNET_PeerIdentity id;
345 * What is the average latency for replies received?
347 struct GNUNET_TIME_Relative latency;
350 * Transport level distance to peer.
352 unsigned int distance;
359 * Peers are grouped into buckets.
366 struct PeerInfo *head;
371 struct PeerInfo *tail;
374 * Number of peers in the bucket.
376 unsigned int peers_size;
381 * The lowest currently used bucket, initially 0 (for 0-bits matching bucket).
383 static unsigned int closest_bucket;
386 * How many peers have we added since we sent out our last
389 static unsigned int newly_found_peers;
392 * Option for testing that disables the 'connect' function of the DHT.
394 static int disable_try_connect;
397 * The buckets. Array of size MAX_BUCKET_SIZE. Offset 0 means 0 bits matching.
399 static struct PeerBucket k_buckets[MAX_BUCKETS];
402 * Hash map of all known peers, for easy removal from k_buckets on disconnect.
404 static struct GNUNET_CONTAINER_MultiHashMap *all_known_peers;
407 * Maximum size for each bucket.
409 static unsigned int bucket_size = DEFAULT_BUCKET_SIZE;
412 * Task that sends FIND PEER requests.
414 static GNUNET_SCHEDULER_TaskIdentifier find_peer_task;
417 * Identity of this peer.
419 static struct GNUNET_PeerIdentity my_identity;
424 static struct GNUNET_CORE_Handle *coreAPI;
429 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
434 * Find the optimal bucket for this key.
436 * @param hc the hashcode to compare our identity to
437 * @return the proper bucket index, or GNUNET_SYSERR
438 * on error (same hashcode)
441 find_bucket (const struct GNUNET_HashCode * hc)
445 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey, hc);
446 if (bits == MAX_BUCKETS)
448 /* How can all bits match? Got my own ID? */
450 return GNUNET_SYSERR;
452 return MAX_BUCKETS - bits - 1;
457 * Let GNUnet core know that we like the given peer.
459 * @param cls the 'struct PeerInfo' of the peer
460 * @param tc scheduler context.
463 update_core_preference (void *cls,
464 const struct GNUNET_SCHEDULER_TaskContext *tc)
466 struct PeerInfo *peer = cls;
468 unsigned int matching;
471 peer->preference_task = GNUNET_SCHEDULER_NO_TASK;
472 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
475 GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey,
476 &peer->id.hashPubKey);
479 bucket = find_bucket (&peer->id.hashPubKey);
480 if (bucket == GNUNET_SYSERR)
484 GNUNET_assert (k_buckets[bucket].peers_size != 0);
485 preference = (1LL << matching) / k_buckets[bucket].peers_size;
489 peer->preference_task =
490 GNUNET_SCHEDULER_add_delayed (DHT_DEFAULT_PREFERENCE_INTERVAL,
491 &update_core_preference, peer);
494 GNUNET_STATISTICS_update (GDS_stats,
495 gettext_noop ("# Preference updates given to core"),
497 GNUNET_ATS_change_preference (atsAPI, &peer->id,
498 GNUNET_ATS_PREFERENCE_BANDWIDTH,
499 (double) preference, GNUNET_ATS_PREFERENCE_END);
500 peer->preference_task =
501 GNUNET_SCHEDULER_add_delayed (DHT_DEFAULT_PREFERENCE_INTERVAL,
502 &update_core_preference, peer);
509 * Closure for 'add_known_to_bloom'.
511 struct BloomConstructorContext
514 * Bloom filter under construction.
516 struct GNUNET_CONTAINER_BloomFilter *bloom;
526 * Add each of the peers we already know to the bloom filter of
527 * the request so that we don't get duplicate HELLOs.
529 * @param cls the 'struct BloomConstructorContext'.
530 * @param key peer identity to add to the bloom filter
531 * @param value value the peer information (unused)
532 * @return GNUNET_YES (we should continue to iterate)
535 add_known_to_bloom (void *cls, const struct GNUNET_HashCode * key, void *value)
537 struct BloomConstructorContext *ctx = cls;
538 struct GNUNET_HashCode mh;
540 GNUNET_BLOCK_mingle_hash (key, ctx->bf_mutator, &mh);
541 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
542 "Adding known peer (%s) to bloomfilter for FIND PEER with mutation %u\n",
543 GNUNET_h2s (key), ctx->bf_mutator);
544 GNUNET_CONTAINER_bloomfilter_add (ctx->bloom, &mh);
550 * Task to send a find peer message for our own peer identifier
551 * so that we can find the closest peers in the network to ourselves
552 * and attempt to connect to them.
554 * @param cls closure for this task
555 * @param tc the context under which the task is running
558 send_find_peer_message (void *cls,
559 const struct GNUNET_SCHEDULER_TaskContext *tc)
561 struct GNUNET_TIME_Relative next_send_time;
562 struct BloomConstructorContext bcc;
563 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
565 find_peer_task = GNUNET_SCHEDULER_NO_TASK;
566 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
568 if (newly_found_peers > bucket_size)
570 /* If we are finding many peers already, no need to send out our request right now! */
572 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
573 &send_find_peer_message, NULL);
574 newly_found_peers = 0;
578 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
580 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE,
581 GNUNET_CONSTANTS_BLOOMFILTER_K);
582 GNUNET_CONTAINER_multihashmap_iterate (all_known_peers, &add_known_to_bloom,
584 GNUNET_STATISTICS_update (GDS_stats,
585 gettext_noop ("# FIND PEER messages initiated"), 1,
588 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE,
589 GNUNET_CONSTANTS_BLOOMFILTER_K);
590 // FIXME: pass priority!?
591 GDS_NEIGHBOURS_handle_get (GNUNET_BLOCK_TYPE_DHT_HELLO,
592 GNUNET_DHT_RO_FIND_PEER,
593 FIND_PEER_REPLICATION_LEVEL, 0,
594 &my_identity.hashPubKey, NULL, 0, bcc.bloom,
595 bcc.bf_mutator, peer_bf);
596 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
597 GNUNET_CONTAINER_bloomfilter_free (bcc.bloom);
598 /* schedule next round */
599 next_send_time.rel_value =
600 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value +
601 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
602 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value /
603 (newly_found_peers + 1));
604 newly_found_peers = 0;
606 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_peer_message,
612 * Method called whenever a peer connects.
615 * @param peer peer identity this notification is about
616 * @param atsi performance data
617 * @param atsi_count number of records in 'atsi'
620 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer,
621 const struct GNUNET_ATS_Information *atsi,
622 unsigned int atsi_count)
624 struct PeerInfo *ret;
627 /* Check for connect to self message */
628 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
630 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected %s to %s\n",
631 GNUNET_i2s (&my_identity), GNUNET_h2s (&peer->hashPubKey));
633 GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
639 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
641 peer_bucket = find_bucket (&peer->hashPubKey);
642 GNUNET_assert ((peer_bucket >= 0) && (peer_bucket < MAX_BUCKETS));
643 ret = GNUNET_malloc (sizeof (struct PeerInfo));
645 ret->latency = latency;
646 ret->distance = distance;
649 GNUNET_CONTAINER_DLL_insert_tail (k_buckets[peer_bucket].head,
650 k_buckets[peer_bucket].tail, ret);
651 k_buckets[peer_bucket].peers_size++;
652 closest_bucket = GNUNET_MAX (closest_bucket, peer_bucket);
653 if ((peer_bucket > 0) && (k_buckets[peer_bucket].peers_size <= bucket_size))
655 ret->preference_task =
656 GNUNET_SCHEDULER_add_now (&update_core_preference, ret);
659 GNUNET_assert (GNUNET_OK ==
660 GNUNET_CONTAINER_multihashmap_put (all_known_peers,
661 &peer->hashPubKey, ret,
662 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
663 if (1 == GNUNET_CONTAINER_multihashmap_size (all_known_peers))
665 /* got a first connection, good time to start with FIND PEER requests... */
666 find_peer_task = GNUNET_SCHEDULER_add_now (&send_find_peer_message, NULL);
672 * Method called whenever a peer disconnects.
675 * @param peer peer identity this notification is about
678 handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer)
680 struct PeerInfo *to_remove;
682 struct P2PPendingMessage *pos;
683 unsigned int discarded;
685 /* Check for disconnect from self message */
686 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
688 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Disconnected %s from %s\n",
689 GNUNET_i2s (&my_identity), GNUNET_h2s (&peer->hashPubKey));
691 GNUNET_CONTAINER_multihashmap_get (all_known_peers, &peer->hashPubKey);
692 if (NULL == to_remove)
697 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), -1,
699 GNUNET_assert (GNUNET_YES ==
700 GNUNET_CONTAINER_multihashmap_remove (all_known_peers,
703 if (GNUNET_SCHEDULER_NO_TASK != to_remove->preference_task)
705 GNUNET_SCHEDULER_cancel (to_remove->preference_task);
706 to_remove->preference_task = GNUNET_SCHEDULER_NO_TASK;
708 current_bucket = find_bucket (&to_remove->id.hashPubKey);
709 GNUNET_assert (current_bucket >= 0);
710 GNUNET_CONTAINER_DLL_remove (k_buckets[current_bucket].head,
711 k_buckets[current_bucket].tail, to_remove);
712 GNUNET_assert (k_buckets[current_bucket].peers_size > 0);
713 k_buckets[current_bucket].peers_size--;
714 while ((closest_bucket > 0) && (k_buckets[closest_bucket].peers_size == 0))
717 if (to_remove->th != NULL)
719 GNUNET_CORE_notify_transmit_ready_cancel (to_remove->th);
720 to_remove->th = NULL;
723 while (NULL != (pos = to_remove->head))
725 GNUNET_CONTAINER_DLL_remove (to_remove->head, to_remove->tail, pos);
729 GNUNET_STATISTICS_update (GDS_stats,
731 ("# Queued messages discarded (peer disconnected)"),
732 discarded, GNUNET_NO);
733 GNUNET_free (to_remove);
738 * Called when core is ready to send a message we asked for
739 * out to the destination.
741 * @param cls the 'struct PeerInfo' of the target peer
742 * @param size number of bytes available in buf
743 * @param buf where the callee should write the message
744 * @return number of bytes written to buf
747 core_transmit_notify (void *cls, size_t size, void *buf)
749 struct PeerInfo *peer = cls;
751 struct P2PPendingMessage *pending;
756 while ((NULL != (pending = peer->head)) &&
757 (GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value == 0))
759 peer->pending_count--;
760 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
761 GNUNET_free (pending);
765 /* no messages pending */
771 GNUNET_CORE_notify_transmit_ready (coreAPI, GNUNET_YES,
773 GNUNET_TIME_absolute_get_remaining
774 (pending->timeout), &peer->id,
775 ntohs (pending->msg->size),
776 &core_transmit_notify, peer);
777 GNUNET_break (NULL != peer->th);
781 while ((NULL != (pending = peer->head)) &&
782 (size - off >= (msize = ntohs (pending->msg->size))))
784 GNUNET_STATISTICS_update (GDS_stats,
786 ("# Bytes transmitted to other peers"), msize,
788 memcpy (&cbuf[off], pending->msg, msize);
790 peer->pending_count--;
791 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
792 GNUNET_free (pending);
794 if (peer->head != NULL)
797 GNUNET_CORE_notify_transmit_ready (coreAPI, GNUNET_YES,
799 GNUNET_TIME_absolute_get_remaining
800 (pending->timeout), &peer->id, msize,
801 &core_transmit_notify, peer);
802 GNUNET_break (NULL != peer->th);
809 * Transmit all messages in the peer's message queue.
811 * @param peer message queue to process
814 process_peer_queue (struct PeerInfo *peer)
816 struct P2PPendingMessage *pending;
818 if (NULL == (pending = peer->head))
820 if (NULL != peer->th)
822 GNUNET_STATISTICS_update (GDS_stats,
824 ("# Bytes of bandwidth requested from core"),
825 ntohs (pending->msg->size), GNUNET_NO);
827 GNUNET_CORE_notify_transmit_ready (coreAPI, GNUNET_YES,
829 GNUNET_TIME_absolute_get_remaining
830 (pending->timeout), &peer->id,
831 ntohs (pending->msg->size),
832 &core_transmit_notify, peer);
833 GNUNET_break (NULL != peer->th);
838 * To how many peers should we (on average) forward the request to
839 * obtain the desired target_replication count (on average).
841 * @param hop_count number of hops the message has traversed
842 * @param target_replication the number of total paths desired
843 * @return Some number of peers to forward the message to
846 get_forward_count (uint32_t hop_count, uint32_t target_replication)
848 uint32_t random_value;
849 uint32_t forward_count;
852 if (hop_count > GDS_NSE_get () * 6.0)
854 /* forcefully terminate */
857 if (hop_count > GDS_NSE_get () * 4.0)
859 /* Once we have reached our ideal number of hops, only forward to 1 peer */
862 /* bound by system-wide maximum */
864 GNUNET_MIN (MAXIMUM_REPLICATION_LEVEL, target_replication);
866 1 + (target_replication - 1.0) / (GDS_NSE_get () +
867 ((float) (target_replication - 1.0) *
869 /* Set forward count to floor of target_value */
870 forward_count = (uint32_t) target_value;
871 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
872 target_value = target_value - forward_count;
874 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
875 if (random_value < (target_value * UINT32_MAX))
877 return forward_count;
882 * Compute the distance between have and target as a 32-bit value.
883 * Differences in the lower bits must count stronger than differences
884 * in the higher bits.
886 * @return 0 if have==target, otherwise a number
887 * that is larger as the distance between
888 * the two hash codes increases
891 get_distance (const struct GNUNET_HashCode * target, const struct GNUNET_HashCode * have)
898 /* We have to represent the distance between two 2^9 (=512)-bit
899 * numbers as a 2^5 (=32)-bit number with "0" being used for the
900 * two numbers being identical; furthermore, we need to
901 * guarantee that a difference in the number of matching
902 * bits is always represented in the result.
904 * We use 2^32/2^9 numerical values to distinguish between
905 * hash codes that have the same LSB bit distance and
906 * use the highest 2^9 bits of the result to signify the
907 * number of (mis)matching LSB bits; if we have 0 matching
908 * and hence 512 mismatching LSB bits we return -1 (since
909 * 512 itself cannot be represented with 9 bits) */
911 /* first, calculate the most significant 9 bits of our
912 * result, aka the number of LSBs */
913 bucket = GNUNET_CRYPTO_hash_matching_bits (target, have);
914 /* bucket is now a value between 0 and 512 */
916 return 0; /* perfect match */
918 return (unsigned int) -1; /* LSB differs; use max (if we did the bit-shifting
919 * below, we'd end up with max+1 (overflow)) */
921 /* calculate the most significant bits of the final result */
922 msb = (512 - bucket) << (32 - 9);
923 /* calculate the 32-9 least significant bits of the final result by
924 * looking at the differences in the 32-9 bits following the
925 * mismatching bit at 'bucket' */
928 (i < sizeof (struct GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9); i++)
930 if (GNUNET_CRYPTO_hash_get_bit (target, i) !=
931 GNUNET_CRYPTO_hash_get_bit (have, i))
932 lsb |= (1 << (bucket + 32 - 9 - i)); /* first bit set will be 10,
933 * last bit set will be 31 -- if
934 * i does not reach 512 first... */
941 * Check whether my identity is closer than any known peers. If a
942 * non-null bloomfilter is given, check if this is the closest peer
943 * that hasn't already been routed to.
945 * @param key hash code to check closeness to
946 * @param bloom bloomfilter, exclude these entries from the decision
947 * @return GNUNET_YES if node location is closest,
948 * GNUNET_NO otherwise.
951 am_closest_peer (const struct GNUNET_HashCode * key,
952 const struct GNUNET_CONTAINER_BloomFilter *bloom)
958 struct PeerInfo *pos;
960 if (0 == memcmp (&my_identity.hashPubKey, key, sizeof (struct GNUNET_HashCode)))
962 bucket_num = find_bucket (key);
963 GNUNET_assert (bucket_num >= 0);
964 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey, key);
965 pos = k_buckets[bucket_num].head;
967 while ((pos != NULL) && (count < bucket_size))
969 if ((bloom != NULL) &&
971 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)))
974 continue; /* Skip already checked entries */
976 other_bits = GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey, key);
977 if (other_bits > bits)
979 if (other_bits == bits) /* We match the same number of bits */
983 /* No peers closer, we are the closest! */
989 * Select a peer from the routing table that would be a good routing
990 * destination for sending a message for "key". The resulting peer
991 * must not be in the set of blocked peers.<p>
993 * Note that we should not ALWAYS select the closest peer to the
994 * target, peers further away from the target should be chosen with
995 * exponentially declining probability.
997 * FIXME: double-check that this is fine
1000 * @param key the key we are selecting a peer to route to
1001 * @param bloom a bloomfilter containing entries this request has seen already
1002 * @param hops how many hops has this message traversed thus far
1003 * @return Peer to route to, or NULL on error
1005 static struct PeerInfo *
1006 select_peer (const struct GNUNET_HashCode * key,
1007 const struct GNUNET_CONTAINER_BloomFilter *bloom, uint32_t hops)
1011 unsigned int selected;
1012 struct PeerInfo *pos;
1014 unsigned int smallest_distance;
1015 struct PeerInfo *chosen;
1017 if (hops >= GDS_NSE_get ())
1019 /* greedy selection (closest peer that is not in bloomfilter) */
1020 smallest_distance = UINT_MAX;
1022 for (bc = 0; bc <= closest_bucket; bc++)
1024 pos = k_buckets[bc].head;
1026 while ((pos != NULL) && (count < bucket_size))
1028 if ((bloom == NULL) ||
1030 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)))
1032 dist = get_distance (key, &pos->id.hashPubKey);
1033 if (dist < smallest_distance)
1036 smallest_distance = dist;
1041 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1042 "Excluded peer `%s' due to BF match in greedy routing for %s\n",
1043 GNUNET_i2s (&pos->id), GNUNET_h2s (key));
1044 GNUNET_STATISTICS_update (GDS_stats,
1046 ("# Peers excluded from routing due to Bloomfilter"),
1054 GNUNET_STATISTICS_update (GDS_stats,
1055 gettext_noop ("# Peer selection failed"), 1,
1060 /* select "random" peer */
1061 /* count number of peers that are available and not filtered */
1063 for (bc = 0; bc <= closest_bucket; bc++)
1065 pos = k_buckets[bc].head;
1066 while ((pos != NULL) && (count < bucket_size))
1068 if ((bloom != NULL) &&
1070 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)))
1072 GNUNET_STATISTICS_update (GDS_stats,
1074 ("# Peers excluded from routing due to Bloomfilter"),
1076 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1077 "Excluded peer `%s' due to BF match in random routing for %s\n",
1078 GNUNET_i2s (&pos->id), GNUNET_h2s (key));
1080 continue; /* Ignore bloomfiltered peers */
1086 if (count == 0) /* No peers to select from! */
1088 GNUNET_STATISTICS_update (GDS_stats,
1089 gettext_noop ("# Peer selection failed"), 1,
1093 /* Now actually choose a peer */
1094 selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, count);
1096 for (bc = 0; bc <= closest_bucket; bc++)
1098 for (pos = k_buckets[bc].head; ((pos != NULL) && (count < bucket_size)); pos = pos->next)
1100 if ((bloom != NULL) &&
1102 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)))
1104 continue; /* Ignore bloomfiltered peers */
1106 if (0 == selected--)
1116 * Compute the set of peers that the given request should be
1119 * @param key routing key
1120 * @param bloom bloom filter excluding peers as targets, all selected
1121 * peers will be added to the bloom filter
1122 * @param hop_count number of hops the request has traversed so far
1123 * @param target_replication desired number of replicas
1124 * @param targets where to store an array of target peers (to be
1125 * free'd by the caller)
1126 * @return number of peers returned in 'targets'.
1129 get_target_peers (const struct GNUNET_HashCode *key,
1130 struct GNUNET_CONTAINER_BloomFilter *bloom,
1131 uint32_t hop_count, uint32_t target_replication,
1132 struct PeerInfo ***targets)
1136 struct PeerInfo **rtargets;
1137 struct PeerInfo *nxt;
1139 GNUNET_assert (NULL != bloom);
1140 ret = get_forward_count (hop_count, target_replication);
1146 rtargets = GNUNET_malloc (sizeof (struct PeerInfo *) * ret);
1147 for (off = 0; off < ret; off++)
1149 nxt = select_peer (key, bloom, hop_count);
1152 rtargets[off] = nxt;
1153 GNUNET_break (GNUNET_NO ==
1154 GNUNET_CONTAINER_bloomfilter_test (bloom,
1155 &nxt->id.hashPubKey));
1156 GNUNET_CONTAINER_bloomfilter_add (bloom, &rtargets[off]->id.hashPubKey);
1158 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1159 "Selected %u/%u peers at hop %u for %s (target was %u)\n", off,
1160 GNUNET_CONTAINER_multihashmap_size (all_known_peers),
1161 (unsigned int) hop_count, GNUNET_h2s (key), ret);
1164 GNUNET_free (rtargets);
1168 *targets = rtargets;
1169 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1170 "Forwarding query `%s' to %u peers (goal was %u peers)\n",
1179 * Perform a PUT operation. Forwards the given request to other
1180 * peers. Does not store the data locally. Does not give the
1181 * data to local clients. May do nothing if this is the only
1182 * peer in the network (or if we are the closest peer in the
1185 * @param type type of the block
1186 * @param options routing options
1187 * @param desired_replication_level desired replication count
1188 * @param expiration_time when does the content expire
1189 * @param hop_count how many hops has this message traversed so far
1190 * @param bf Bloom filter of peers this PUT has already traversed
1191 * @param key key for the content
1192 * @param put_path_length number of entries in put_path
1193 * @param put_path peers this request has traversed so far (if tracked)
1194 * @param data payload to store
1195 * @param data_size number of bytes in data
1198 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1199 enum GNUNET_DHT_RouteOption options,
1200 uint32_t desired_replication_level,
1201 struct GNUNET_TIME_Absolute expiration_time,
1203 struct GNUNET_CONTAINER_BloomFilter *bf,
1204 const struct GNUNET_HashCode * key,
1205 unsigned int put_path_length,
1206 struct GNUNET_PeerIdentity *put_path,
1207 const void *data, size_t data_size)
1209 unsigned int target_count;
1211 struct PeerInfo **targets;
1212 struct PeerInfo *target;
1213 struct P2PPendingMessage *pending;
1215 struct PeerPutMessage *ppm;
1216 struct GNUNET_PeerIdentity *pp;
1218 GNUNET_assert (NULL != bf);
1219 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1220 "Adding myself (%s) to PUT bloomfilter for %s\n",
1221 GNUNET_i2s (&my_identity), GNUNET_h2s (key));
1222 GNUNET_CONTAINER_bloomfilter_add (bf, &my_identity.hashPubKey);
1223 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# PUT requests routed"),
1226 get_target_peers (key, bf, hop_count, desired_replication_level,
1228 if (0 == target_count)
1230 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1231 "Routing PUT for %s terminates after %u hops at %s\n",
1232 GNUNET_h2s (key), (unsigned int) hop_count,
1233 GNUNET_i2s (&my_identity));
1237 put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
1238 sizeof (struct PeerPutMessage);
1239 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1241 put_path_length = 0;
1242 msize = data_size + sizeof (struct PeerPutMessage);
1244 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1247 GNUNET_free (targets);
1250 GNUNET_STATISTICS_update (GDS_stats,
1252 ("# PUT messages queued for transmission"),
1253 target_count, GNUNET_NO);
1254 for (i = 0; i < target_count; i++)
1256 target = targets[i];
1257 if (target->pending_count >= MAXIMUM_PENDING_PER_PEER)
1259 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1261 continue; /* skip */
1263 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1264 "Routing PUT for %s after %u hops to %s\n", GNUNET_h2s (key),
1265 (unsigned int) hop_count, GNUNET_i2s (&target->id));
1266 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1267 pending->importance = 0; /* FIXME */
1268 pending->timeout = expiration_time;
1269 ppm = (struct PeerPutMessage *) &pending[1];
1270 pending->msg = &ppm->header;
1271 ppm->header.size = htons (msize);
1272 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1273 ppm->options = htonl (options);
1274 ppm->type = htonl (type);
1275 ppm->hop_count = htonl (hop_count + 1);
1276 ppm->desired_replication_level = htonl (desired_replication_level);
1277 ppm->put_path_length = htonl (put_path_length);
1278 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1279 GNUNET_break (GNUNET_YES ==
1280 GNUNET_CONTAINER_bloomfilter_test (bf,
1281 &target->id.hashPubKey));
1282 GNUNET_assert (GNUNET_OK ==
1283 GNUNET_CONTAINER_bloomfilter_get_raw_data (bf,
1287 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1288 memcpy (pp, put_path,
1289 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
1290 memcpy (&pp[put_path_length], data, data_size);
1291 GNUNET_CONTAINER_DLL_insert_tail (target->head, target->tail, pending);
1292 target->pending_count++;
1293 process_peer_queue (target);
1295 GNUNET_free (targets);
1300 * Perform a GET operation. Forwards the given request to other
1301 * peers. Does not lookup the key locally. May do nothing if this is
1302 * the only peer in the network (or if we are the closest peer in the
1305 * @param type type of the block
1306 * @param options routing options
1307 * @param desired_replication_level desired replication count
1308 * @param hop_count how many hops did this request traverse so far?
1309 * @param key key for the content
1310 * @param xquery extended query
1311 * @param xquery_size number of bytes in xquery
1312 * @param reply_bf bloomfilter to filter duplicates
1313 * @param reply_bf_mutator mutator for reply_bf
1314 * @param peer_bf filter for peers not to select (again)
1317 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1318 enum GNUNET_DHT_RouteOption options,
1319 uint32_t desired_replication_level,
1320 uint32_t hop_count, const struct GNUNET_HashCode * key,
1321 const void *xquery, size_t xquery_size,
1322 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
1323 uint32_t reply_bf_mutator,
1324 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1326 unsigned int target_count;
1328 struct PeerInfo **targets;
1329 struct PeerInfo *target;
1330 struct P2PPendingMessage *pending;
1332 struct PeerGetMessage *pgm;
1334 size_t reply_bf_size;
1336 GNUNET_assert (NULL != peer_bf);
1337 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# GET requests routed"),
1340 get_target_peers (key, peer_bf, hop_count, desired_replication_level,
1342 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1343 "Adding myself (%s) to GET bloomfilter for %s\n",
1344 GNUNET_i2s (&my_identity), GNUNET_h2s (key));
1345 GNUNET_CONTAINER_bloomfilter_add (peer_bf, &my_identity.hashPubKey);
1346 if (0 == target_count)
1348 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1349 "Routing GET for %s terminates after %u hops at %s\n",
1350 GNUNET_h2s (key), (unsigned int) hop_count,
1351 GNUNET_i2s (&my_identity));
1354 reply_bf_size = GNUNET_CONTAINER_bloomfilter_get_size (reply_bf);
1355 msize = xquery_size + sizeof (struct PeerGetMessage) + reply_bf_size;
1356 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1359 GNUNET_free (targets);
1362 GNUNET_STATISTICS_update (GDS_stats,
1364 ("# GET messages queued for transmission"),
1365 target_count, GNUNET_NO);
1366 /* forward request */
1367 for (i = 0; i < target_count; i++)
1369 target = targets[i];
1370 if (target->pending_count >= MAXIMUM_PENDING_PER_PEER)
1372 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1374 continue; /* skip */
1376 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1377 "Routing GET for %s after %u hops to %s\n", GNUNET_h2s (key),
1378 (unsigned int) hop_count, GNUNET_i2s (&target->id));
1379 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1380 pending->importance = 0; /* FIXME */
1381 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1382 pgm = (struct PeerGetMessage *) &pending[1];
1383 pending->msg = &pgm->header;
1384 pgm->header.size = htons (msize);
1385 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
1386 pgm->options = htonl (options);
1387 pgm->type = htonl (type);
1388 pgm->hop_count = htonl (hop_count + 1);
1389 pgm->desired_replication_level = htonl (desired_replication_level);
1390 pgm->xquery_size = htonl (xquery_size);
1391 pgm->bf_mutator = reply_bf_mutator;
1392 GNUNET_break (GNUNET_YES ==
1393 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
1394 &target->id.hashPubKey));
1395 GNUNET_assert (GNUNET_OK ==
1396 GNUNET_CONTAINER_bloomfilter_get_raw_data (peer_bf,
1400 xq = (char *) &pgm[1];
1401 memcpy (xq, xquery, xquery_size);
1402 if (NULL != reply_bf)
1403 GNUNET_assert (GNUNET_OK ==
1404 GNUNET_CONTAINER_bloomfilter_get_raw_data (reply_bf,
1408 GNUNET_CONTAINER_DLL_insert_tail (target->head, target->tail, pending);
1409 target->pending_count++;
1410 process_peer_queue (target);
1412 GNUNET_free (targets);
1417 * Handle a reply (route to origin). Only forwards the reply back to
1418 * the given peer. Does not do local caching or forwarding to local
1421 * @param target neighbour that should receive the block (if still connected)
1422 * @param type type of the block
1423 * @param expiration_time when does the content expire
1424 * @param key key for the content
1425 * @param put_path_length number of entries in put_path
1426 * @param put_path peers the original PUT traversed (if tracked)
1427 * @param get_path_length number of entries in put_path
1428 * @param get_path peers this reply has traversed so far (if tracked)
1429 * @param data payload of the reply
1430 * @param data_size number of bytes in data
1433 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
1434 enum GNUNET_BLOCK_Type type,
1435 struct GNUNET_TIME_Absolute expiration_time,
1436 const struct GNUNET_HashCode * key,
1437 unsigned int put_path_length,
1438 const struct GNUNET_PeerIdentity *put_path,
1439 unsigned int get_path_length,
1440 const struct GNUNET_PeerIdentity *get_path,
1441 const void *data, size_t data_size)
1443 struct PeerInfo *pi;
1444 struct P2PPendingMessage *pending;
1446 struct PeerResultMessage *prm;
1447 struct GNUNET_PeerIdentity *paths;
1450 data_size + sizeof (struct PeerResultMessage) + (get_path_length +
1452 sizeof (struct GNUNET_PeerIdentity);
1453 if ((msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) ||
1455 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1457 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1458 (data_size > GNUNET_SERVER_MAX_MESSAGE_SIZE))
1463 pi = GNUNET_CONTAINER_multihashmap_get (all_known_peers, &target->hashPubKey);
1466 /* peer disconnected in the meantime, drop reply */
1469 if (pi->pending_count >= MAXIMUM_PENDING_PER_PEER)
1472 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1477 GNUNET_STATISTICS_update (GDS_stats,
1479 ("# RESULT messages queued for transmission"), 1,
1481 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1482 pending->importance = 0; /* FIXME */
1483 pending->timeout = expiration_time;
1484 prm = (struct PeerResultMessage *) &pending[1];
1485 pending->msg = &prm->header;
1486 prm->header.size = htons (msize);
1487 prm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT);
1488 prm->type = htonl (type);
1489 prm->put_path_length = htonl (put_path_length);
1490 prm->get_path_length = htonl (get_path_length);
1491 prm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1493 paths = (struct GNUNET_PeerIdentity *) &prm[1];
1494 memcpy (paths, put_path,
1495 put_path_length * sizeof (struct GNUNET_PeerIdentity));
1496 memcpy (&paths[put_path_length], get_path,
1497 get_path_length * sizeof (struct GNUNET_PeerIdentity));
1498 memcpy (&paths[put_path_length + get_path_length], data, data_size);
1499 GNUNET_CONTAINER_DLL_insert (pi->head, pi->tail, pending);
1500 pi->pending_count++;
1501 process_peer_queue (pi);
1506 * To be called on core init/fail.
1508 * @param cls service closure
1509 * @param server handle to the server for this service
1510 * @param identity the public identity of this peer
1513 core_init (void *cls, struct GNUNET_CORE_Handle *server,
1514 const struct GNUNET_PeerIdentity *identity)
1516 GNUNET_assert (server != NULL);
1517 my_identity = *identity;
1522 * Core handler for p2p put requests.
1524 * @param cls closure
1525 * @param peer sender of the request
1526 * @param message message
1527 * @param peer peer identity this notification is about
1528 * @param atsi performance data
1529 * @param atsi_count number of records in 'atsi'
1530 * @return GNUNET_OK to keep the connection open,
1531 * GNUNET_SYSERR to close it (signal serious error)
1534 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
1535 const struct GNUNET_MessageHeader *message,
1536 const struct GNUNET_ATS_Information *atsi,
1537 unsigned int atsi_count)
1539 const struct PeerPutMessage *put;
1540 const struct GNUNET_PeerIdentity *put_path;
1541 const void *payload;
1544 size_t payload_size;
1545 enum GNUNET_DHT_RouteOption options;
1546 struct GNUNET_CONTAINER_BloomFilter *bf;
1547 struct GNUNET_HashCode test_key;
1549 msize = ntohs (message->size);
1550 if (msize < sizeof (struct PeerPutMessage))
1552 GNUNET_break_op (0);
1555 put = (const struct PeerPutMessage *) message;
1556 putlen = ntohl (put->put_path_length);
1558 sizeof (struct PeerPutMessage) +
1559 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
1561 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1563 GNUNET_break_op (0);
1566 GNUNET_STATISTICS_update (GDS_stats,
1567 gettext_noop ("# P2P PUT requests received"), 1,
1569 put_path = (const struct GNUNET_PeerIdentity *) &put[1];
1570 payload = &put_path[putlen];
1571 options = ntohl (put->options);
1573 msize - (sizeof (struct PeerPutMessage) +
1574 putlen * sizeof (struct GNUNET_PeerIdentity));
1575 switch (GNUNET_BLOCK_get_key
1576 (GDS_block_context, ntohl (put->type), payload, payload_size,
1580 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
1582 GNUNET_break_op (0);
1587 GNUNET_break_op (0);
1590 /* cannot verify, good luck */
1593 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "PUT for `%s' from %s\n",
1594 GNUNET_h2s (&put->key), GNUNET_i2s (peer));
1596 if (LOG_ROUTE_DETAILS_STDERR)
1600 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
1601 fprintf (stderr, "XDHT PUT %s: %s(%u)<-%s\n",
1602 GNUNET_h2s (&put->key), tmp, getpid (),
1608 bf = GNUNET_CONTAINER_bloomfilter_init (put->bloomfilter, DHT_BLOOM_SIZE,
1609 GNUNET_CONSTANTS_BLOOMFILTER_K);
1610 GNUNET_break_op (GNUNET_YES ==
1611 GNUNET_CONTAINER_bloomfilter_test (bf, &peer->hashPubKey));
1613 struct GNUNET_PeerIdentity pp[putlen + 1];
1615 /* extend 'put path' by sender */
1616 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
1618 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
1625 /* give to local clients */
1626 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (put->expiration_time),
1627 &put->key, 0, NULL, putlen, pp, ntohl (put->type),
1628 payload_size, payload);
1630 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
1631 (am_closest_peer (&put->key, bf)))
1632 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh
1633 (put->expiration_time), &put->key, putlen, pp,
1634 ntohl (put->type), payload_size, payload);
1635 /* route to other peers */
1636 GDS_NEIGHBOURS_handle_put (ntohl (put->type), options,
1637 ntohl (put->desired_replication_level),
1638 GNUNET_TIME_absolute_ntoh (put->expiration_time),
1639 ntohl (put->hop_count), bf, &put->key, putlen,
1640 pp, payload, payload_size);
1642 GNUNET_CONTAINER_bloomfilter_free (bf);
1643 GDS_CLIENTS_process_put (options,
1645 ntohl (put->hop_count),
1646 ntohl (put->desired_replication_level),
1648 GNUNET_TIME_absolute_ntoh (put->expiration_time),
1657 * We have received a FIND PEER request. Send matching
1660 * @param sender sender of the FIND PEER request
1661 * @param key peers close to this key are desired
1662 * @param bf peers matching this bf are excluded
1663 * @param bf_mutator mutator for bf
1666 handle_find_peer (const struct GNUNET_PeerIdentity *sender,
1667 const struct GNUNET_HashCode * key,
1668 struct GNUNET_CONTAINER_BloomFilter *bf, uint32_t bf_mutator)
1671 struct PeerBucket *bucket;
1672 struct PeerInfo *peer;
1673 unsigned int choice;
1674 struct GNUNET_HashCode mhash;
1675 const struct GNUNET_HELLO_Message *hello;
1677 /* first, check about our own HELLO */
1678 if (NULL != GDS_my_hello)
1680 GNUNET_BLOCK_mingle_hash (&my_identity.hashPubKey, bf_mutator, &mhash);
1682 (GNUNET_YES != GNUNET_CONTAINER_bloomfilter_test (bf, &mhash)))
1684 GDS_NEIGHBOURS_handle_reply (sender, GNUNET_BLOCK_TYPE_DHT_HELLO,
1685 GNUNET_TIME_relative_to_absolute
1686 (GNUNET_CONSTANTS_HELLO_ADDRESS_EXPIRATION),
1687 key, 0, NULL, 0, NULL, GDS_my_hello,
1688 GNUNET_HELLO_size ((const struct
1689 GNUNET_HELLO_Message *)
1694 GNUNET_STATISTICS_update (GDS_stats,
1696 ("# FIND PEER requests ignored due to Bloomfilter"),
1702 GNUNET_STATISTICS_update (GDS_stats,
1704 ("# FIND PEER requests ignored due to lack of HELLO"),
1708 /* then, also consider sending a random HELLO from the closest bucket */
1709 if (0 == memcmp (&my_identity.hashPubKey, key, sizeof (struct GNUNET_HashCode)))
1710 bucket_idx = closest_bucket;
1712 bucket_idx = GNUNET_MIN (closest_bucket, find_bucket (key));
1713 if (bucket_idx == GNUNET_SYSERR)
1715 bucket = &k_buckets[bucket_idx];
1716 if (bucket->peers_size == 0)
1719 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, bucket->peers_size);
1720 peer = bucket->head;
1723 GNUNET_assert (peer != NULL);
1727 choice = bucket->peers_size;
1732 return; /* no non-masked peer available */
1734 peer = bucket->head;
1735 GNUNET_BLOCK_mingle_hash (&peer->id.hashPubKey, bf_mutator, &mhash);
1736 hello = GDS_HELLO_get (&peer->id);
1738 while ((hello == NULL) ||
1739 (GNUNET_YES == GNUNET_CONTAINER_bloomfilter_test (bf, &mhash)));
1740 GDS_NEIGHBOURS_handle_reply (sender, GNUNET_BLOCK_TYPE_DHT_HELLO,
1741 GNUNET_TIME_relative_to_absolute
1742 (GNUNET_CONSTANTS_HELLO_ADDRESS_EXPIRATION), key,
1743 0, NULL, 0, NULL, hello,
1744 GNUNET_HELLO_size (hello));
1749 * Core handler for p2p get requests.
1751 * @param cls closure
1752 * @param peer sender of the request
1753 * @param message message
1754 * @param peer peer identity this notification is about
1755 * @param atsi performance data
1756 * @param atsi_count number of records in 'atsi'
1757 * @return GNUNET_OK to keep the connection open,
1758 * GNUNET_SYSERR to close it (signal serious error)
1761 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1762 const struct GNUNET_MessageHeader *message,
1763 const struct GNUNET_ATS_Information *atsi,
1764 unsigned int atsi_count)
1766 struct PeerGetMessage *get;
1767 uint32_t xquery_size;
1768 size_t reply_bf_size;
1770 enum GNUNET_BLOCK_Type type;
1771 enum GNUNET_DHT_RouteOption options;
1772 enum GNUNET_BLOCK_EvaluationResult eval;
1773 struct GNUNET_CONTAINER_BloomFilter *reply_bf;
1774 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
1778 memcmp (peer, &my_identity,
1779 sizeof (struct GNUNET_PeerIdentity)));
1780 /* parse and validate message */
1781 msize = ntohs (message->size);
1782 if (msize < sizeof (struct PeerGetMessage))
1784 GNUNET_break_op (0);
1787 get = (struct PeerGetMessage *) message;
1788 xquery_size = ntohl (get->xquery_size);
1789 if (msize < sizeof (struct PeerGetMessage) + xquery_size)
1791 GNUNET_break_op (0);
1794 GNUNET_STATISTICS_update (GDS_stats,
1795 gettext_noop ("# P2P GET requests received"), 1,
1797 reply_bf_size = msize - (sizeof (struct PeerGetMessage) + xquery_size);
1798 type = ntohl (get->type);
1799 options = ntohl (get->options);
1800 xquery = (const char *) &get[1];
1802 if (reply_bf_size > 0)
1804 GNUNET_CONTAINER_bloomfilter_init (&xquery[xquery_size], reply_bf_size,
1805 GNUNET_CONSTANTS_BLOOMFILTER_K);
1807 GNUNET_BLOCK_evaluate (GDS_block_context, type, &get->key, &reply_bf,
1808 get->bf_mutator, xquery, xquery_size, NULL, 0);
1809 if (eval != GNUNET_BLOCK_EVALUATION_REQUEST_VALID)
1811 /* request invalid or block type not supported */
1812 GNUNET_break_op (eval == GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED);
1813 if (NULL != reply_bf)
1814 GNUNET_CONTAINER_bloomfilter_free (reply_bf);
1818 GNUNET_CONTAINER_bloomfilter_init (get->bloomfilter, DHT_BLOOM_SIZE,
1819 GNUNET_CONSTANTS_BLOOMFILTER_K);
1820 GNUNET_break_op (GNUNET_YES ==
1821 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
1822 &peer->hashPubKey));
1823 /* remember request for routing replies */
1824 GDS_ROUTING_add (peer, type, options, &get->key, xquery, xquery_size,
1825 reply_bf, get->bf_mutator);
1826 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "GET for %s at %s after %u hops\n",
1827 GNUNET_h2s (&get->key), GNUNET_i2s (&my_identity),
1828 (unsigned int) ntohl (get->hop_count));
1829 /* local lookup (this may update the reply_bf) */
1830 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
1831 (am_closest_peer (&get->key, peer_bf)))
1833 if ((0 != (options & GNUNET_DHT_RO_FIND_PEER)))
1835 GNUNET_STATISTICS_update (GDS_stats,
1837 ("# P2P FIND PEER requests processed"), 1,
1839 handle_find_peer (peer, &get->key, reply_bf, get->bf_mutator);
1844 GDS_DATACACHE_handle_get (&get->key, type, xquery, xquery_size,
1845 &reply_bf, get->bf_mutator);
1850 GNUNET_STATISTICS_update (GDS_stats,
1851 gettext_noop ("# P2P GET requests ONLY routed"),
1855 if (LOG_ROUTE_DETAILS_STDERR)
1859 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
1860 fprintf (stderr, "XDHT GET %s: %s(%u)<-%s\n",
1861 GNUNET_h2s (&get->key), tmp, getpid(),
1869 GDS_CLIENTS_process_get (options,
1871 ntohl(get->hop_count),
1872 ntohl(get->desired_replication_level),
1876 /* P2P forwarding */
1877 if (eval != GNUNET_BLOCK_EVALUATION_OK_LAST)
1878 GDS_NEIGHBOURS_handle_get (type, options,
1879 ntohl (get->desired_replication_level),
1880 ntohl (get->hop_count), &get->key, xquery,
1881 xquery_size, reply_bf, get->bf_mutator, peer_bf);
1883 if (NULL != reply_bf)
1884 GNUNET_CONTAINER_bloomfilter_free (reply_bf);
1885 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
1891 * Core handler for p2p result messages.
1893 * @param cls closure
1894 * @param message message
1895 * @param peer peer identity this notification is about
1896 * @param atsi performance data
1897 * @param atsi_count number of records in 'atsi'
1898 * @return GNUNET_YES (do not cut p2p connection)
1901 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1902 const struct GNUNET_MessageHeader *message,
1903 const struct GNUNET_ATS_Information *atsi,
1904 unsigned int atsi_count)
1906 const struct PeerResultMessage *prm;
1907 const struct GNUNET_PeerIdentity *put_path;
1908 const struct GNUNET_PeerIdentity *get_path;
1910 uint32_t get_path_length;
1911 uint32_t put_path_length;
1914 enum GNUNET_BLOCK_Type type;
1916 /* parse and validate message */
1917 msize = ntohs (message->size);
1918 if (msize < sizeof (struct PeerResultMessage))
1920 GNUNET_break_op (0);
1923 prm = (struct PeerResultMessage *) message;
1924 put_path_length = ntohl (prm->put_path_length);
1925 get_path_length = ntohl (prm->get_path_length);
1927 sizeof (struct PeerResultMessage) + (get_path_length +
1929 sizeof (struct GNUNET_PeerIdentity)) ||
1931 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1933 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1935 GNUNET_break_op (0);
1938 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P RESULTS received"),
1940 put_path = (const struct GNUNET_PeerIdentity *) &prm[1];
1941 get_path = &put_path[put_path_length];
1942 type = ntohl (prm->type);
1943 data = (const void *) &get_path[get_path_length];
1945 msize - (sizeof (struct PeerResultMessage) +
1947 put_path_length) * sizeof (struct GNUNET_PeerIdentity));
1949 /* if we got a HELLO, consider it for our own routing table */
1950 if (type == GNUNET_BLOCK_TYPE_DHT_HELLO)
1952 const struct GNUNET_MessageHeader *h;
1953 struct GNUNET_PeerIdentity pid;
1956 /* Should be a HELLO, validate and consider using it! */
1957 if (data_size < sizeof (struct GNUNET_MessageHeader))
1959 GNUNET_break_op (0);
1963 if (data_size != ntohs (h->size))
1965 GNUNET_break_op (0);
1969 GNUNET_HELLO_get_id ((const struct GNUNET_HELLO_Message *) h, &pid))
1971 GNUNET_break_op (0);
1974 if (0 != memcmp (&my_identity, &pid, sizeof (struct GNUNET_PeerIdentity)))
1976 bucket = find_bucket (&pid.hashPubKey);
1977 if ((bucket >= 0) && (k_buckets[bucket].peers_size < bucket_size))
1979 if (NULL != GDS_transport_handle)
1981 GNUNET_TRANSPORT_offer_hello (GDS_transport_handle, h, NULL, NULL);
1983 disable_try_connect)
1984 GNUNET_TRANSPORT_try_connect (GDS_transport_handle, &pid, NULL, NULL); /*FIXME TRY_CONNECT change */
1991 if (LOG_ROUTE_DETAILS_STDERR)
1995 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
1997 "XDHT RESULT %s: %s(%u)<-%s\n",
1998 GNUNET_h2s (&prm->key), tmp,
1999 getpid(), GNUNET_i2s (peer));
2003 /* append 'peer' to 'get_path' */
2005 struct GNUNET_PeerIdentity xget_path[get_path_length + 1];
2007 memcpy (xget_path, get_path,
2008 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2009 xget_path[get_path_length] = *peer;
2012 /* forward to local clients */
2013 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2014 &prm->key, get_path_length, xget_path,
2015 put_path_length, put_path, type, data_size, data);
2017 /* forward to other peers */
2018 GDS_ROUTING_process (type, GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2019 &prm->key, put_path_length, put_path, get_path_length,
2020 xget_path, data, data_size);
2023 GDS_CLIENTS_process_get_resp (type,
2028 GNUNET_TIME_absolute_ntoh (
2029 prm->expiration_time),
2039 * Initialize neighbours subsystem.
2041 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2044 GDS_NEIGHBOURS_init ()
2046 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2047 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2048 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2049 {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
2052 unsigned long long temp_config_num;
2055 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg, "DHT", "DISABLE_TRY_CONNECT");
2057 GNUNET_CONFIGURATION_get_value_number (GDS_cfg, "DHT", "bucket_size",
2059 bucket_size = (unsigned int) temp_config_num;
2060 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
2062 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2063 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2064 GNUNET_NO, core_handlers);
2065 if (coreAPI == NULL)
2066 return GNUNET_SYSERR;
2067 all_known_peers = GNUNET_CONTAINER_multihashmap_create (256, GNUNET_NO);
2073 * Shutdown neighbours subsystem.
2076 GDS_NEIGHBOURS_done ()
2078 if (coreAPI == NULL)
2080 GNUNET_CORE_disconnect (coreAPI);
2082 GNUNET_ATS_performance_done (atsAPI);
2084 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (all_known_peers));
2085 GNUNET_CONTAINER_multihashmap_destroy (all_known_peers);
2086 all_known_peers = NULL;
2087 if (GNUNET_SCHEDULER_NO_TASK != find_peer_task)
2089 GNUNET_SCHEDULER_cancel (find_peer_task);
2090 find_peer_task = GNUNET_SCHEDULER_NO_TASK;
2095 * Get the ID of the local node.
2097 * @return identity of the local node
2099 struct GNUNET_PeerIdentity *
2100 GDS_NEIGHBOURS_get_id ()
2102 return &my_identity;
2106 /* end of gnunet-service-dht_neighbours.c */