2 This file is part of GNUnet.
3 Copyright (C) 2009-2017 GNUnet e.V.
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., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, 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
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_nse_service.h"
34 #include "gnunet_ats_service.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_datacache_lib.h"
37 #include "gnunet_transport_service.h"
38 #include "gnunet_hello_lib.h"
39 #include "gnunet_dht_service.h"
40 #include "gnunet_statistics_service.h"
41 #include "gnunet-service-dht.h"
42 #include "gnunet-service-dht_datacache.h"
43 #include "gnunet-service-dht_hello.h"
44 #include "gnunet-service-dht_neighbours.h"
45 #include "gnunet-service-dht_nse.h"
46 #include "gnunet-service-dht_routing.h"
49 #define LOG_TRAFFIC(kind,...) GNUNET_log_from (kind, "dht-traffic",__VA_ARGS__)
52 * Enable slow sanity checks to debug issues.
54 #define SANITY_CHECKS 1
57 * How many buckets will we allow total.
59 #define MAX_BUCKETS sizeof (struct GNUNET_HashCode) * 8
62 * What is the maximum number of peers in a given bucket.
64 #define DEFAULT_BUCKET_SIZE 8
67 * Desired replication level for FIND PEER requests
69 #define FIND_PEER_REPLICATION_LEVEL 4
72 * Maximum allowed replication level for all requests.
74 #define MAXIMUM_REPLICATION_LEVEL 16
77 * Maximum allowed number of pending messages per peer.
79 #define MAXIMUM_PENDING_PER_PEER 64
82 * How long at least to wait before sending another find peer request.
84 #define DHT_MINIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
87 * How long at most to wait before sending another find peer request.
89 #define DHT_MAXIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
92 * How long at most to wait for transmission of a GET request to another peer?
94 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
97 * Hello address expiration
99 extern struct GNUNET_TIME_Relative hello_expiration;
102 GNUNET_NETWORK_STRUCT_BEGIN
107 struct PeerPutMessage
110 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
112 struct GNUNET_MessageHeader header;
117 uint32_t options GNUNET_PACKED;
122 uint32_t type GNUNET_PACKED;
127 uint32_t hop_count GNUNET_PACKED;
130 * Replication level for this message
132 uint32_t desired_replication_level GNUNET_PACKED;
135 * Length of the PUT path that follows (if tracked).
137 uint32_t put_path_length GNUNET_PACKED;
140 * When does the content expire?
142 struct GNUNET_TIME_AbsoluteNBO expiration_time;
145 * Bloomfilter (for peer identities) to stop circular routes
147 char bloomfilter[DHT_BLOOM_SIZE];
150 * The key we are storing under.
152 struct GNUNET_HashCode key;
154 /* put path (if tracked) */
164 struct PeerResultMessage
167 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
169 struct GNUNET_MessageHeader header;
174 uint32_t type GNUNET_PACKED;
177 * Length of the PUT path that follows (if tracked).
179 uint32_t put_path_length GNUNET_PACKED;
182 * Length of the GET path that follows (if tracked).
184 uint32_t get_path_length GNUNET_PACKED;
187 * When does the content expire?
189 struct GNUNET_TIME_AbsoluteNBO expiration_time;
192 * The key of the corresponding GET request.
194 struct GNUNET_HashCode key;
196 /* put path (if tracked) */
198 /* get path (if tracked) */
208 struct PeerGetMessage
211 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
213 struct GNUNET_MessageHeader header;
218 uint32_t options GNUNET_PACKED;
221 * Desired content type.
223 uint32_t type GNUNET_PACKED;
228 uint32_t hop_count GNUNET_PACKED;
231 * Desired replication level for this request.
233 uint32_t desired_replication_level GNUNET_PACKED;
236 * Size of the extended query.
238 uint32_t xquery_size;
241 * Bloomfilter mutator.
246 * Bloomfilter (for peer identities) to stop circular routes
248 char bloomfilter[DHT_BLOOM_SIZE];
251 * The key we are looking for.
253 struct GNUNET_HashCode key;
257 /* result bloomfilter */
260 GNUNET_NETWORK_STRUCT_END
264 * Entry for a peer in a bucket.
269 * Next peer entry (DLL)
271 struct PeerInfo *next;
274 * Prev peer entry (DLL)
276 struct PeerInfo *prev;
279 * Handle for sending messages to this peer.
281 struct GNUNET_MQ_Handle *mq;
284 * What is the identity of the peer?
286 const struct GNUNET_PeerIdentity *id;
291 struct GNUNET_HashCode phash;
294 * Which bucket is this peer in?
302 * Peers are grouped into buckets.
309 struct PeerInfo *head;
314 struct PeerInfo *tail;
317 * Number of peers in the bucket.
319 unsigned int peers_size;
324 * Information about a peer that we would like to connect to.
330 * Handle to active HELLO offer operation, or NULL.
332 struct GNUNET_TRANSPORT_OfferHelloHandle *oh;
335 * Handle to active connectivity suggestion operation, or NULL.
337 struct GNUNET_ATS_ConnectivitySuggestHandle *sh;
340 * How much would we like to connect to this peer?
347 * Do we cache all results that we are routing in the local datacache?
349 static int cache_results;
352 * Should routing details be logged to stderr (for debugging)?
354 static int log_route_details_stderr;
357 * The lowest currently used bucket, initially 0 (for 0-bits matching bucket).
359 static unsigned int closest_bucket;
362 * How many peers have we added since we sent out our last
365 static unsigned int newly_found_peers;
368 * Option for testing that disables the 'connect' function of the DHT.
370 static int disable_try_connect;
373 * The buckets. Array of size #MAX_BUCKETS. Offset 0 means 0 bits matching.
375 static struct PeerBucket k_buckets[MAX_BUCKETS];
378 * Hash map of all CORE-connected peers, for easy removal from
379 * #k_buckets on disconnect. Values are of type `struct PeerInfo`.
381 static struct GNUNET_CONTAINER_MultiPeerMap *all_connected_peers;
384 * Hash map of all peers we would like to be connected to.
385 * Values are of type `struct ConnectInfo`.
387 static struct GNUNET_CONTAINER_MultiPeerMap *all_desired_peers;
390 * Maximum size for each bucket.
392 static unsigned int bucket_size = DEFAULT_BUCKET_SIZE;
395 * Task that sends FIND PEER requests.
397 static struct GNUNET_SCHEDULER_Task *find_peer_task;
400 * Identity of this peer.
402 static struct GNUNET_PeerIdentity my_identity;
405 * Hash of the identity of this peer.
407 static struct GNUNET_HashCode my_identity_hash;
412 static struct GNUNET_CORE_Handle *core_api;
415 * Handle to ATS connectivity.
417 static struct GNUNET_ATS_ConnectivityHandle *ats_ch;
421 * Find the optimal bucket for this key.
423 * @param hc the hashcode to compare our identity to
424 * @return the proper bucket index, or GNUNET_SYSERR
425 * on error (same hashcode)
428 find_bucket (const struct GNUNET_HashCode *hc)
432 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash, hc);
433 if (bits == MAX_BUCKETS)
435 /* How can all bits match? Got my own ID? */
437 return GNUNET_SYSERR;
439 return MAX_BUCKETS - bits - 1;
444 * Function called when #GNUNET_TRANSPORT_offer_hello() is done.
445 * Clean up the "oh" field in the @a cls
447 * @param cls a `struct ConnectInfo`
450 offer_hello_done (void *cls)
452 struct ConnectInfo *ci = cls;
459 * Function called for all entries in #all_desired_peers to clean up.
462 * @param peer peer the entry is for
463 * @param value the value to remove
464 * @return #GNUNET_YES
467 free_connect_info (void *cls,
468 const struct GNUNET_PeerIdentity *peer,
471 struct ConnectInfo *ci = value;
473 GNUNET_assert (GNUNET_YES ==
474 GNUNET_CONTAINER_multipeermap_remove (all_desired_peers,
479 GNUNET_ATS_connectivity_suggest_cancel (ci->sh);
484 GNUNET_TRANSPORT_offer_hello_cancel (ci->oh);
493 * Consider if we want to connect to a given peer, and if so
494 * let ATS know. If applicable, the HELLO is offered to the
497 * @param pid peer to consider connectivity requirements for
498 * @param h a HELLO message, or NULL
501 try_connect (const struct GNUNET_PeerIdentity *pid,
502 const struct GNUNET_MessageHeader *h)
505 struct GNUNET_HashCode pid_hash;
506 struct ConnectInfo *ci;
509 GNUNET_CRYPTO_hash (pid,
510 sizeof (struct GNUNET_PeerIdentity),
512 bucket = find_bucket (&pid_hash);
515 ci = GNUNET_CONTAINER_multipeermap_get (all_desired_peers,
518 if (k_buckets[bucket].peers_size < bucket_size)
519 strength = (bucket_size - k_buckets[bucket].peers_size) * bucket;
521 strength = bucket; /* minimum value of connectivity */
523 GNUNET_CONTAINER_multipeermap_contains (all_connected_peers,
525 strength *= 2; /* double for connected peers */
526 else if (k_buckets[bucket].peers_size > bucket_size)
527 strength = 0; /* bucket full, we really do not care about more */
529 if ( (0 == strength) &&
532 /* release request */
533 GNUNET_assert (GNUNET_YES ==
534 free_connect_info (NULL,
541 ci = GNUNET_new (struct ConnectInfo);
542 GNUNET_assert (GNUNET_OK ==
543 GNUNET_CONTAINER_multipeermap_put (all_desired_peers,
546 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
548 if ( (NULL != ci->oh) &&
550 GNUNET_TRANSPORT_offer_hello_cancel (ci->oh);
552 ci->oh = GNUNET_TRANSPORT_offer_hello (GDS_cfg,
556 if ( (NULL != ci->sh) &&
557 (ci->strength != strength) )
558 GNUNET_ATS_connectivity_suggest_cancel (ci->sh);
559 if (ci->strength != strength)
560 ci->sh = GNUNET_ATS_connectivity_suggest (ats_ch,
563 ci->strength = strength;
568 * Function called for each peer in #all_desired_peers during
569 * #update_connect_preferences() if we have reason to adjust
570 * the strength of our desire to keep connections to certain
571 * peers. Calls #try_connect() to update the calculations for
575 * @param pid peer to update
576 * @param value unused
577 * @return #GNUNET_YES (continue to iterate)
580 update_desire_strength (void *cls,
581 const struct GNUNET_PeerIdentity *pid,
584 try_connect (pid, NULL);
590 * Update our preferences for connectivity as given to ATS.
592 * @param cls the `struct PeerInfo` of the peer
593 * @param tc scheduler context.
596 update_connect_preferences ()
598 GNUNET_CONTAINER_multipeermap_iterate (all_desired_peers,
599 &update_desire_strength,
605 * Add each of the peers we already know to the bloom filter of
606 * the request so that we don't get duplicate HELLOs.
608 * @param cls the `struct GNUNET_BLOCK_Group`
609 * @param key peer identity to add to the bloom filter
610 * @param value value the peer information (unused)
611 * @return #GNUNET_YES (we should continue to iterate)
614 add_known_to_bloom (void *cls,
615 const struct GNUNET_PeerIdentity *key,
618 struct GNUNET_BLOCK_Group *bg = cls;
619 struct GNUNET_HashCode key_hash;
621 GNUNET_CRYPTO_hash (key,
622 sizeof (struct GNUNET_PeerIdentity),
624 GNUNET_BLOCK_group_set_seen (bg,
627 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
628 "Adding known peer (%s) to bloomfilter for FIND PEER\n",
635 * Task to send a find peer message for our own peer identifier
636 * so that we can find the closest peers in the network to ourselves
637 * and attempt to connect to them.
639 * @param cls closure for this task
642 send_find_peer_message (void *cls)
644 struct GNUNET_TIME_Relative next_send_time;
645 struct GNUNET_BLOCK_Group *bg;
646 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
648 find_peer_task = NULL;
649 if (newly_found_peers > bucket_size)
651 /* If we are finding many peers already, no need to send out our request right now! */
653 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
654 &send_find_peer_message,
656 newly_found_peers = 0;
659 bg = GNUNET_BLOCK_group_create (GDS_block_context,
660 GNUNET_BLOCK_TYPE_DHT_HELLO,
661 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
668 GNUNET_CONTAINER_multipeermap_iterate (all_connected_peers,
671 GNUNET_STATISTICS_update (GDS_stats,
672 gettext_noop ("# FIND PEER messages initiated"),
676 = GNUNET_CONTAINER_bloomfilter_init (NULL,
678 GNUNET_CONSTANTS_BLOOMFILTER_K);
679 // FIXME: pass priority!?
680 GDS_NEIGHBOURS_handle_get (GNUNET_BLOCK_TYPE_DHT_HELLO,
681 GNUNET_DHT_RO_FIND_PEER | GNUNET_DHT_RO_RECORD_ROUTE,
682 FIND_PEER_REPLICATION_LEVEL,
689 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
690 GNUNET_BLOCK_group_destroy (bg);
691 /* schedule next round */
692 next_send_time.rel_value_us =
693 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value_us +
694 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
695 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value_us /
696 (newly_found_peers + 1));
697 newly_found_peers = 0;
698 GNUNET_assert (NULL == find_peer_task);
700 GNUNET_SCHEDULER_add_delayed (next_send_time,
701 &send_find_peer_message,
707 * Method called whenever a peer connects.
710 * @param peer peer identity this notification is about
711 * @param mq message queue for sending messages to @a peer
712 * @return our `struct PeerInfo` for @a peer
715 handle_core_connect (void *cls,
716 const struct GNUNET_PeerIdentity *peer,
717 struct GNUNET_MQ_Handle *mq)
721 /* Check for connect to self message */
722 if (0 == memcmp (&my_identity,
724 sizeof (struct GNUNET_PeerIdentity)))
726 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
729 GNUNET_assert (GNUNET_NO ==
730 GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
732 GNUNET_STATISTICS_update (GDS_stats,
733 gettext_noop ("# peers connected"),
736 pi = GNUNET_new (struct PeerInfo);
739 GNUNET_CRYPTO_hash (peer,
740 sizeof (struct GNUNET_PeerIdentity),
742 pi->peer_bucket = find_bucket (&pi->phash);
743 GNUNET_assert ( (pi->peer_bucket >= 0) &&
744 (pi->peer_bucket < MAX_BUCKETS) );
745 GNUNET_CONTAINER_DLL_insert_tail (k_buckets[pi->peer_bucket].head,
746 k_buckets[pi->peer_bucket].tail,
748 k_buckets[pi->peer_bucket].peers_size++;
749 closest_bucket = GNUNET_MAX (closest_bucket,
751 GNUNET_assert (GNUNET_OK ==
752 GNUNET_CONTAINER_multipeermap_put (all_connected_peers,
755 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
756 if ( (pi->peer_bucket > 0) &&
757 (k_buckets[pi->peer_bucket].peers_size <= bucket_size))
759 update_connect_preferences ();
762 if ( (1 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
763 (GNUNET_YES != disable_try_connect))
765 /* got a first connection, good time to start with FIND PEER requests... */
766 GNUNET_assert (NULL == find_peer_task);
767 find_peer_task = GNUNET_SCHEDULER_add_now (&send_find_peer_message,
775 * Method called whenever a peer disconnects.
778 * @param peer peer identity this notification is about
779 * @param internal_cls our `struct PeerInfo` for @a peer
782 handle_core_disconnect (void *cls,
783 const struct GNUNET_PeerIdentity *peer,
786 struct PeerInfo *to_remove = internal_cls;
788 /* Check for disconnect from self message */
789 if (NULL == to_remove)
791 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
794 GNUNET_STATISTICS_update (GDS_stats,
795 gettext_noop ("# peers connected"),
798 GNUNET_assert (GNUNET_YES ==
799 GNUNET_CONTAINER_multipeermap_remove (all_connected_peers,
802 if ( (0 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
803 (GNUNET_YES != disable_try_connect) )
805 GNUNET_SCHEDULER_cancel (find_peer_task);
806 find_peer_task = NULL;
808 GNUNET_assert (to_remove->peer_bucket >= 0);
809 GNUNET_CONTAINER_DLL_remove (k_buckets[to_remove->peer_bucket].head,
810 k_buckets[to_remove->peer_bucket].tail,
812 GNUNET_assert (k_buckets[to_remove->peer_bucket].peers_size > 0);
813 k_buckets[to_remove->peer_bucket].peers_size--;
814 while ( (closest_bucket > 0) &&
815 (0 == k_buckets[to_remove->peer_bucket].peers_size) )
817 if (k_buckets[to_remove->peer_bucket].peers_size < bucket_size)
818 update_connect_preferences ();
819 GNUNET_free (to_remove);
824 * To how many peers should we (on average) forward the request to
825 * obtain the desired target_replication count (on average).
827 * @param hop_count number of hops the message has traversed
828 * @param target_replication the number of total paths desired
829 * @return Some number of peers to forward the message to
832 get_forward_count (uint32_t hop_count,
833 uint32_t target_replication)
835 uint32_t random_value;
836 uint32_t forward_count;
839 if (hop_count > GDS_NSE_get () * 4.0)
841 /* forcefully terminate */
842 GNUNET_STATISTICS_update (GDS_stats,
843 gettext_noop ("# requests TTL-dropped"),
847 if (hop_count > GDS_NSE_get () * 2.0)
849 /* Once we have reached our ideal number of hops, only forward to 1 peer */
852 /* bound by system-wide maximum */
854 GNUNET_MIN (MAXIMUM_REPLICATION_LEVEL, target_replication);
856 1 + (target_replication - 1.0) / (GDS_NSE_get () +
857 ((float) (target_replication - 1.0) *
859 /* Set forward count to floor of target_value */
860 forward_count = (uint32_t) target_value;
861 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
862 target_value = target_value - forward_count;
864 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
865 if (random_value < (target_value * UINT32_MAX))
867 return forward_count;
872 * Compute the distance between have and target as a 32-bit value.
873 * Differences in the lower bits must count stronger than differences
874 * in the higher bits.
878 * @return 0 if have==target, otherwise a number
879 * that is larger as the distance between
880 * the two hash codes increases
883 get_distance (const struct GNUNET_HashCode *target,
884 const struct GNUNET_HashCode *have)
891 /* We have to represent the distance between two 2^9 (=512)-bit
892 * numbers as a 2^5 (=32)-bit number with "0" being used for the
893 * two numbers being identical; furthermore, we need to
894 * guarantee that a difference in the number of matching
895 * bits is always represented in the result.
897 * We use 2^32/2^9 numerical values to distinguish between
898 * hash codes that have the same LSB bit distance and
899 * use the highest 2^9 bits of the result to signify the
900 * number of (mis)matching LSB bits; if we have 0 matching
901 * and hence 512 mismatching LSB bits we return -1 (since
902 * 512 itself cannot be represented with 9 bits) */
904 /* first, calculate the most significant 9 bits of our
905 * result, aka the number of LSBs */
906 bucket = GNUNET_CRYPTO_hash_matching_bits (target,
908 /* bucket is now a value between 0 and 512 */
910 return 0; /* perfect match */
912 return (unsigned int) -1; /* LSB differs; use max (if we did the bit-shifting
913 * below, we'd end up with max+1 (overflow)) */
915 /* calculate the most significant bits of the final result */
916 msb = (512 - bucket) << (32 - 9);
917 /* calculate the 32-9 least significant bits of the final result by
918 * looking at the differences in the 32-9 bits following the
919 * mismatching bit at 'bucket' */
922 (i < sizeof (struct GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9); i++)
924 if (GNUNET_CRYPTO_hash_get_bit (target, i) !=
925 GNUNET_CRYPTO_hash_get_bit (have, i))
926 lsb |= (1 << (bucket + 32 - 9 - i)); /* first bit set will be 10,
927 * last bit set will be 31 -- if
928 * i does not reach 512 first... */
935 * Check whether my identity is closer than any known peers. If a
936 * non-null bloomfilter is given, check if this is the closest peer
937 * that hasn't already been routed to.
939 * @param key hash code to check closeness to
940 * @param bloom bloomfilter, exclude these entries from the decision
941 * @return #GNUNET_YES if node location is closest,
942 * #GNUNET_NO otherwise.
945 am_closest_peer (const struct GNUNET_HashCode *key,
946 const struct GNUNET_CONTAINER_BloomFilter *bloom)
952 struct PeerInfo *pos;
954 if (0 == memcmp (&my_identity_hash, key, sizeof (struct GNUNET_HashCode)))
956 bucket_num = find_bucket (key);
957 GNUNET_assert (bucket_num >= 0);
958 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
960 pos = k_buckets[bucket_num].head;
962 while ((NULL != pos) && (count < bucket_size))
964 if ((NULL != bloom) &&
966 GNUNET_CONTAINER_bloomfilter_test (bloom,
970 continue; /* Skip already checked entries */
972 other_bits = GNUNET_CRYPTO_hash_matching_bits (&pos->phash,
974 if (other_bits > bits)
976 if (other_bits == bits) /* We match the same number of bits */
980 /* No peers closer, we are the closest! */
986 * Select a peer from the routing table that would be a good routing
987 * destination for sending a message for "key". The resulting peer
988 * must not be in the set of blocked peers.<p>
990 * Note that we should not ALWAYS select the closest peer to the
991 * target, peers further away from the target should be chosen with
992 * exponentially declining probability.
994 * FIXME: double-check that this is fine
997 * @param key the key we are selecting a peer to route to
998 * @param bloom a bloomfilter containing entries this request has seen already
999 * @param hops how many hops has this message traversed thus far
1000 * @return Peer to route to, or NULL on error
1002 static struct PeerInfo *
1003 select_peer (const struct GNUNET_HashCode *key,
1004 const struct GNUNET_CONTAINER_BloomFilter *bloom,
1009 unsigned int selected;
1010 struct PeerInfo *pos;
1012 unsigned int smallest_distance;
1013 struct PeerInfo *chosen;
1015 if (hops >= GDS_NSE_get ())
1017 /* greedy selection (closest peer that is not in bloomfilter) */
1018 smallest_distance = UINT_MAX;
1020 for (bc = 0; bc <= closest_bucket; bc++)
1022 pos = k_buckets[bc].head;
1024 while ((pos != NULL) && (count < bucket_size))
1026 if ( (NULL == bloom) ||
1028 GNUNET_CONTAINER_bloomfilter_test (bloom,
1031 dist = get_distance (key,
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),
1045 GNUNET_STATISTICS_update (GDS_stats,
1046 gettext_noop ("# Peers excluded from routing due to Bloomfilter"),
1049 dist = get_distance (key,
1051 if (dist < smallest_distance)
1054 smallest_distance = dist;
1062 GNUNET_STATISTICS_update (GDS_stats,
1063 gettext_noop ("# Peer selection failed"),
1067 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1068 "Selected peer `%s' in greedy routing for %s\n",
1069 GNUNET_i2s (chosen->id),
1074 /* select "random" peer */
1075 /* count number of peers that are available and not filtered */
1077 for (bc = 0; bc <= closest_bucket; bc++)
1079 pos = k_buckets[bc].head;
1080 while ( (NULL != pos) && (count < bucket_size) )
1082 if ( (NULL != bloom) &&
1084 GNUNET_CONTAINER_bloomfilter_test (bloom,
1087 GNUNET_STATISTICS_update (GDS_stats,
1089 ("# Peers excluded from routing due to Bloomfilter"),
1091 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1092 "Excluded peer `%s' due to BF match in random routing for %s\n",
1093 GNUNET_i2s (pos->id),
1096 continue; /* Ignore bloomfiltered peers */
1102 if (0 == count) /* No peers to select from! */
1104 GNUNET_STATISTICS_update (GDS_stats,
1105 gettext_noop ("# Peer selection failed"), 1,
1109 /* Now actually choose a peer */
1110 selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1113 for (bc = 0; bc <= closest_bucket; bc++)
1115 for (pos = k_buckets[bc].head; ((pos != NULL) && (count < bucket_size)); pos = pos->next)
1117 if ((bloom != NULL) &&
1119 GNUNET_CONTAINER_bloomfilter_test (bloom,
1122 continue; /* Ignore bloomfiltered peers */
1124 if (0 == selected--)
1126 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1127 "Selected peer `%s' in random routing for %s\n",
1128 GNUNET_i2s (pos->id),
1140 * Compute the set of peers that the given request should be
1143 * @param key routing key
1144 * @param bloom bloom filter excluding peers as targets, all selected
1145 * peers will be added to the bloom filter
1146 * @param hop_count number of hops the request has traversed so far
1147 * @param target_replication desired number of replicas
1148 * @param targets where to store an array of target peers (to be
1149 * free'd by the caller)
1150 * @return number of peers returned in 'targets'.
1153 get_target_peers (const struct GNUNET_HashCode *key,
1154 struct GNUNET_CONTAINER_BloomFilter *bloom,
1156 uint32_t target_replication,
1157 struct PeerInfo ***targets)
1161 struct PeerInfo **rtargets;
1162 struct PeerInfo *nxt;
1164 GNUNET_assert (NULL != bloom);
1165 ret = get_forward_count (hop_count,
1166 target_replication);
1172 rtargets = GNUNET_new_array (ret,
1174 for (off = 0; off < ret; off++)
1176 nxt = select_peer (key,
1181 rtargets[off] = nxt;
1182 GNUNET_break (GNUNET_NO ==
1183 GNUNET_CONTAINER_bloomfilter_test (bloom,
1185 GNUNET_CONTAINER_bloomfilter_add (bloom,
1188 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1189 "Selected %u/%u peers at hop %u for %s (target was %u)\n",
1191 GNUNET_CONTAINER_multipeermap_size (all_connected_peers),
1192 (unsigned int) hop_count,
1197 GNUNET_free (rtargets);
1201 *targets = rtargets;
1202 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1203 "Forwarding query `%s' to %u peers (goal was %u peers)\n",
1212 * Perform a PUT operation. Forwards the given request to other
1213 * peers. Does not store the data locally. Does not give the
1214 * data to local clients. May do nothing if this is the only
1215 * peer in the network (or if we are the closest peer in the
1218 * @param type type of the block
1219 * @param options routing options
1220 * @param desired_replication_level desired replication count
1221 * @param expiration_time when does the content expire
1222 * @param hop_count how many hops has this message traversed so far
1223 * @param bf Bloom filter of peers this PUT has already traversed
1224 * @param key key for the content
1225 * @param put_path_length number of entries in @a put_path
1226 * @param put_path peers this request has traversed so far (if tracked)
1227 * @param data payload to store
1228 * @param data_size number of bytes in @a data
1229 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
1232 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1233 enum GNUNET_DHT_RouteOption options,
1234 uint32_t desired_replication_level,
1235 struct GNUNET_TIME_Absolute expiration_time,
1237 struct GNUNET_CONTAINER_BloomFilter *bf,
1238 const struct GNUNET_HashCode *key,
1239 unsigned int put_path_length,
1240 struct GNUNET_PeerIdentity *put_path,
1244 unsigned int target_count;
1246 struct PeerInfo **targets;
1247 struct PeerInfo *target;
1249 struct GNUNET_MQ_Envelope *env;
1250 struct PeerPutMessage *ppm;
1251 struct GNUNET_PeerIdentity *pp;
1252 unsigned int skip_count;
1254 GNUNET_assert (NULL != bf);
1255 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1256 "Adding myself (%s) to PUT bloomfilter for %s\n",
1257 GNUNET_i2s (&my_identity),
1259 GNUNET_CONTAINER_bloomfilter_add (bf,
1261 GNUNET_STATISTICS_update (GDS_stats,
1262 gettext_noop ("# PUT requests routed"),
1266 = get_target_peers (key,
1269 desired_replication_level,
1271 if (0 == target_count)
1273 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1274 "Routing PUT for %s terminates after %u hops at %s\n",
1276 (unsigned int) hop_count,
1277 GNUNET_i2s (&my_identity));
1280 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size;
1281 if (msize + sizeof (struct PeerPutMessage)
1282 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1284 put_path_length = 0;
1287 if (msize + sizeof (struct PeerPutMessage)
1288 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1291 GNUNET_free (targets);
1294 GNUNET_STATISTICS_update (GDS_stats,
1295 gettext_noop ("# PUT messages queued for transmission"),
1299 for (i = 0; i < target_count; i++)
1301 target = targets[i];
1302 if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
1305 GNUNET_STATISTICS_update (GDS_stats,
1306 gettext_noop ("# P2P messages dropped due to full queue"),
1312 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1313 "Routing PUT for %s after %u hops to %s\n",
1315 (unsigned int) hop_count,
1316 GNUNET_i2s (target->id));
1317 env = GNUNET_MQ_msg_extra (ppm,
1319 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1320 ppm->options = htonl (options);
1321 ppm->type = htonl (type);
1322 ppm->hop_count = htonl (hop_count + 1);
1323 ppm->desired_replication_level = htonl (desired_replication_level);
1324 ppm->put_path_length = htonl (put_path_length);
1325 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1326 GNUNET_break (GNUNET_YES ==
1327 GNUNET_CONTAINER_bloomfilter_test (bf,
1329 GNUNET_assert (GNUNET_OK ==
1330 GNUNET_CONTAINER_bloomfilter_get_raw_data (bf,
1334 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1337 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
1338 GNUNET_memcpy (&pp[put_path_length],
1341 GNUNET_MQ_send (target->mq,
1344 GNUNET_free (targets);
1345 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1350 * Perform a GET operation. Forwards the given request to other
1351 * peers. Does not lookup the key locally. May do nothing if this is
1352 * the only peer in the network (or if we are the closest peer in the
1355 * @param type type of the block
1356 * @param options routing options
1357 * @param desired_replication_level desired replication count
1358 * @param hop_count how many hops did this request traverse so far?
1359 * @param key key for the content
1360 * @param xquery extended query
1361 * @param xquery_size number of bytes in @a xquery
1362 * @param bg group to use for filtering replies
1363 * @param peer_bf filter for peers not to select (again)
1364 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
1367 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1368 enum GNUNET_DHT_RouteOption options,
1369 uint32_t desired_replication_level,
1371 const struct GNUNET_HashCode *key,
1374 struct GNUNET_BLOCK_Group *bg,
1375 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1377 unsigned int target_count;
1378 struct PeerInfo **targets;
1379 struct PeerInfo *target;
1380 struct GNUNET_MQ_Envelope *env;
1382 struct PeerGetMessage *pgm;
1384 size_t reply_bf_size;
1386 unsigned int skip_count;
1389 GNUNET_assert (NULL != peer_bf);
1390 GNUNET_STATISTICS_update (GDS_stats,
1391 gettext_noop ("# GET requests routed"),
1394 target_count = get_target_peers (key,
1397 desired_replication_level,
1399 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1400 "Adding myself (%s) to GET bloomfilter for %s\n",
1401 GNUNET_i2s (&my_identity),
1403 GNUNET_CONTAINER_bloomfilter_add (peer_bf,
1405 if (0 == target_count)
1407 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1408 "Routing GET for %s terminates after %u hops at %s\n",
1410 (unsigned int) hop_count,
1411 GNUNET_i2s (&my_identity));
1415 GNUNET_BLOCK_group_serialize (bg,
1422 bf_nonce = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1425 msize = xquery_size + reply_bf_size;
1426 if (msize + sizeof (struct PeerGetMessage) >= GNUNET_MAX_MESSAGE_SIZE)
1429 GNUNET_free_non_null (reply_bf);
1430 GNUNET_free (targets);
1433 GNUNET_STATISTICS_update (GDS_stats,
1434 gettext_noop ("# GET messages queued for transmission"),
1437 /* forward request */
1439 for (unsigned int i = 0; i < target_count; i++)
1441 target = targets[i];
1442 if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
1445 GNUNET_STATISTICS_update (GDS_stats,
1446 gettext_noop ("# P2P messages dropped due to full queue"),
1451 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1452 "Routing GET for %s after %u hops to %s\n",
1454 (unsigned int) hop_count,
1455 GNUNET_i2s (target->id));
1456 env = GNUNET_MQ_msg_extra (pgm,
1458 GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
1459 pgm->options = htonl (options);
1460 pgm->type = htonl (type);
1461 pgm->hop_count = htonl (hop_count + 1);
1462 pgm->desired_replication_level = htonl (desired_replication_level);
1463 pgm->xquery_size = htonl (xquery_size);
1464 pgm->bf_mutator = bf_nonce;
1465 GNUNET_break (GNUNET_YES ==
1466 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
1468 GNUNET_assert (GNUNET_OK ==
1469 GNUNET_CONTAINER_bloomfilter_get_raw_data (peer_bf,
1473 xq = (char *) &pgm[1];
1477 GNUNET_memcpy (&xq[xquery_size],
1480 GNUNET_MQ_send (target->mq,
1483 GNUNET_free (targets);
1484 GNUNET_free_non_null (reply_bf);
1485 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1490 * Handle a reply (route to origin). Only forwards the reply back to
1491 * the given peer. Does not do local caching or forwarding to local
1494 * @param target neighbour that should receive the block (if still connected)
1495 * @param type type of the block
1496 * @param expiration_time when does the content expire
1497 * @param key key for the content
1498 * @param put_path_length number of entries in @a put_path
1499 * @param put_path peers the original PUT traversed (if tracked)
1500 * @param get_path_length number of entries in @a get_path
1501 * @param get_path peers this reply has traversed so far (if tracked)
1502 * @param data payload of the reply
1503 * @param data_size number of bytes in @a data
1506 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
1507 enum GNUNET_BLOCK_Type type,
1508 struct GNUNET_TIME_Absolute expiration_time,
1509 const struct GNUNET_HashCode *key,
1510 unsigned int put_path_length,
1511 const struct GNUNET_PeerIdentity *put_path,
1512 unsigned int get_path_length,
1513 const struct GNUNET_PeerIdentity *get_path,
1517 struct PeerInfo *pi;
1518 struct GNUNET_MQ_Envelope *env;
1520 struct PeerResultMessage *prm;
1521 struct GNUNET_PeerIdentity *paths;
1523 msize = data_size + (get_path_length + put_path_length) *
1524 sizeof (struct GNUNET_PeerIdentity);
1525 if ((msize + sizeof (struct PeerResultMessage) >= GNUNET_MAX_MESSAGE_SIZE) ||
1527 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1529 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1530 (data_size > GNUNET_MAX_MESSAGE_SIZE))
1535 pi = GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
1539 /* peer disconnected in the meantime, drop reply */
1540 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1541 "No matching peer for reply for key %s\n",
1545 if (GNUNET_MQ_get_length (pi->mq) >= MAXIMUM_PENDING_PER_PEER)
1548 GNUNET_STATISTICS_update (GDS_stats,
1549 gettext_noop ("# P2P messages dropped due to full queue"),
1552 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1553 "Peer queue full, ignoring reply for key %s\n",
1558 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1559 "Forwarding reply for key %s to peer %s\n",
1561 GNUNET_i2s (target));
1562 GNUNET_STATISTICS_update (GDS_stats,
1564 ("# RESULT messages queued for transmission"), 1,
1566 env = GNUNET_MQ_msg_extra (prm,
1568 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT);
1569 prm->type = htonl (type);
1570 prm->put_path_length = htonl (put_path_length);
1571 prm->get_path_length = htonl (get_path_length);
1572 prm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1574 paths = (struct GNUNET_PeerIdentity *) &prm[1];
1575 GNUNET_memcpy (paths,
1577 put_path_length * sizeof (struct GNUNET_PeerIdentity));
1578 GNUNET_memcpy (&paths[put_path_length],
1580 get_path_length * sizeof (struct GNUNET_PeerIdentity));
1581 GNUNET_memcpy (&paths[put_path_length + get_path_length],
1584 GNUNET_MQ_send (pi->mq,
1590 * To be called on core init/fail.
1592 * @param cls service closure
1593 * @param identity the public identity of this peer
1596 core_init (void *cls,
1597 const struct GNUNET_PeerIdentity *identity)
1599 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1600 "CORE called, I am %s\n",
1601 GNUNET_i2s (identity));
1602 my_identity = *identity;
1603 GNUNET_CRYPTO_hash (identity,
1604 sizeof (struct GNUNET_PeerIdentity),
1606 GNUNET_SERVICE_resume (GDS_service);
1611 * Check validity of a p2p put request.
1613 * @param cls closure with the `struct PeerInfo` of the sender
1614 * @param message message
1615 * @return #GNUNET_OK if the message is valid
1618 check_dht_p2p_put (void *cls,
1619 const struct PeerPutMessage *put)
1624 msize = ntohs (put->header.size);
1625 putlen = ntohl (put->put_path_length);
1627 sizeof (struct PeerPutMessage) +
1628 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
1630 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1632 GNUNET_break_op (0);
1633 return GNUNET_SYSERR;
1640 * Core handler for p2p put requests.
1642 * @param cls closure with the `struct PeerInfo` of the sender
1643 * @param message message
1646 handle_dht_p2p_put (void *cls,
1647 const struct PeerPutMessage *put)
1649 struct PeerInfo *peer = cls;
1650 const struct GNUNET_PeerIdentity *put_path;
1651 const void *payload;
1654 size_t payload_size;
1655 enum GNUNET_DHT_RouteOption options;
1656 struct GNUNET_CONTAINER_BloomFilter *bf;
1657 struct GNUNET_HashCode test_key;
1660 msize = ntohs (put->header.size);
1661 putlen = ntohl (put->put_path_length);
1662 GNUNET_STATISTICS_update (GDS_stats,
1663 gettext_noop ("# P2P PUT requests received"),
1666 GNUNET_STATISTICS_update (GDS_stats,
1667 gettext_noop ("# P2P PUT bytes received"),
1670 put_path = (const struct GNUNET_PeerIdentity *) &put[1];
1671 payload = &put_path[putlen];
1672 options = ntohl (put->options);
1673 payload_size = msize - (sizeof (struct PeerPutMessage) +
1674 putlen * sizeof (struct GNUNET_PeerIdentity));
1676 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1677 "PUT for `%s' from %s\n",
1678 GNUNET_h2s (&put->key),
1679 GNUNET_i2s (peer->id));
1680 if (GNUNET_YES == log_route_details_stderr)
1685 pp = GNUNET_STRINGS_pp2s (put_path,
1687 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
1688 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
1689 "R5N PUT %s: %s->%s (%u, %u=>%u, PP: %s)\n",
1690 GNUNET_h2s (&put->key),
1691 GNUNET_i2s (peer->id),
1693 ntohl(put->hop_count),
1694 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
1696 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
1702 switch (GNUNET_BLOCK_get_key
1710 if (0 != memcmp (&test_key,
1712 sizeof (struct GNUNET_HashCode)))
1714 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
1716 GNUNET_break_op (0);
1717 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1718 "PUT with key `%s' for block with key %s\n",
1720 GNUNET_h2s_full (&test_key));
1721 GNUNET_free (put_s);
1726 GNUNET_break_op (0);
1729 /* cannot verify, good luck */
1732 if (ntohl (put->type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
1734 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
1736 NULL, /* query group */
1737 GNUNET_BLOCK_EO_NONE,
1739 NULL, 0, /* xquery */
1743 case GNUNET_BLOCK_EVALUATION_OK_MORE:
1744 case GNUNET_BLOCK_EVALUATION_OK_LAST:
1747 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
1748 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
1749 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
1750 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
1751 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
1752 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
1754 GNUNET_break_op (0);
1759 bf = GNUNET_CONTAINER_bloomfilter_init (put->bloomfilter,
1761 GNUNET_CONSTANTS_BLOOMFILTER_K);
1762 GNUNET_break_op (GNUNET_YES ==
1763 GNUNET_CONTAINER_bloomfilter_test (bf,
1766 struct GNUNET_PeerIdentity pp[putlen + 1];
1768 /* extend 'put path' by sender */
1769 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
1772 for (unsigned int i=0;i<=putlen;i++)
1774 for (unsigned int j=0;j<i;j++)
1776 GNUNET_break (0 != memcmp (&pp[i],
1778 sizeof (struct GNUNET_PeerIdentity)));
1780 GNUNET_break (0 != memcmp (&pp[i],
1782 sizeof (struct GNUNET_PeerIdentity)));
1787 putlen * sizeof (struct GNUNET_PeerIdentity));
1788 pp[putlen] = *peer->id;
1794 /* give to local clients */
1795 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (put->expiration_time),
1805 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
1806 (am_closest_peer (&put->key, bf)))
1807 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
1814 /* route to other peers */
1815 forwarded = GDS_NEIGHBOURS_handle_put (ntohl (put->type),
1817 ntohl (put->desired_replication_level),
1818 GNUNET_TIME_absolute_ntoh (put->expiration_time),
1819 ntohl (put->hop_count),
1826 /* notify monitoring clients */
1827 GDS_CLIENTS_process_put (options
1828 | ( (GNUNET_OK == forwarded)
1829 ? GNUNET_DHT_RO_LAST_HOP
1832 ntohl (put->hop_count),
1833 ntohl (put->desired_replication_level),
1835 GNUNET_TIME_absolute_ntoh (put->expiration_time),
1840 GNUNET_CONTAINER_bloomfilter_free (bf);
1845 * We have received a FIND PEER request. Send matching
1848 * @param sender sender of the FIND PEER request
1849 * @param key peers close to this key are desired
1850 * @param bg group for filtering peers
1853 handle_find_peer (const struct GNUNET_PeerIdentity *sender,
1854 const struct GNUNET_HashCode *key,
1855 struct GNUNET_BLOCK_Group *bg)
1858 struct PeerBucket *bucket;
1859 struct PeerInfo *peer;
1860 unsigned int choice;
1861 const struct GNUNET_HELLO_Message *hello;
1864 /* first, check about our own HELLO */
1865 if (NULL != GDS_my_hello)
1867 hello_size = GNUNET_HELLO_size ((const struct GNUNET_HELLO_Message *) GDS_my_hello);
1868 GNUNET_break (hello_size >= sizeof (struct GNUNET_MessageHeader));
1869 if (GNUNET_BLOCK_EVALUATION_OK_MORE ==
1870 GNUNET_BLOCK_evaluate (GDS_block_context,
1871 GNUNET_BLOCK_TYPE_DHT_HELLO,
1873 GNUNET_BLOCK_EO_LOCAL_SKIP_CRYPTO,
1879 GDS_NEIGHBOURS_handle_reply (sender,
1880 GNUNET_BLOCK_TYPE_DHT_HELLO,
1881 GNUNET_TIME_relative_to_absolute (hello_expiration),
1892 GNUNET_STATISTICS_update (GDS_stats,
1893 gettext_noop ("# FIND PEER requests ignored due to Bloomfilter"),
1900 GNUNET_STATISTICS_update (GDS_stats,
1901 gettext_noop ("# FIND PEER requests ignored due to lack of HELLO"),
1906 /* then, also consider sending a random HELLO from the closest bucket */
1907 if (0 == memcmp (&my_identity_hash,
1909 sizeof (struct GNUNET_HashCode)))
1910 bucket_idx = closest_bucket;
1912 bucket_idx = GNUNET_MIN (closest_bucket,
1914 if (bucket_idx == GNUNET_SYSERR)
1916 bucket = &k_buckets[bucket_idx];
1917 if (bucket->peers_size == 0)
1919 choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1920 bucket->peers_size);
1921 peer = bucket->head;
1924 GNUNET_assert (NULL != peer);
1928 choice = bucket->peers_size;
1933 return; /* no non-masked peer available */
1935 peer = bucket->head;
1936 hello = GDS_HELLO_get (peer->id);
1937 } while ( (NULL == hello) ||
1938 (GNUNET_BLOCK_EVALUATION_OK_MORE !=
1939 GNUNET_BLOCK_evaluate (GDS_block_context,
1940 GNUNET_BLOCK_TYPE_DHT_HELLO,
1942 GNUNET_BLOCK_EO_LOCAL_SKIP_CRYPTO,
1946 (hello_size = GNUNET_HELLO_size (hello)))) );
1947 GDS_NEIGHBOURS_handle_reply (sender,
1948 GNUNET_BLOCK_TYPE_DHT_HELLO,
1949 GNUNET_TIME_relative_to_absolute
1950 (GNUNET_CONSTANTS_HELLO_ADDRESS_EXPIRATION),
1962 * Handle a result from local datacache for a GET operation.
1964 * @param cls the `struct PeerInfo` for which this is a reply
1965 * @param type type of the block
1966 * @param expiration_time when does the content expire
1967 * @param key key for the content
1968 * @param put_path_length number of entries in @a put_path
1969 * @param put_path peers the original PUT traversed (if tracked)
1970 * @param get_path_length number of entries in @a get_path
1971 * @param get_path peers this reply has traversed so far (if tracked)
1972 * @param data payload of the reply
1973 * @param data_size number of bytes in @a data
1976 handle_local_result (void *cls,
1977 enum GNUNET_BLOCK_Type type,
1978 struct GNUNET_TIME_Absolute expiration_time,
1979 const struct GNUNET_HashCode *key,
1980 unsigned int put_path_length,
1981 const struct GNUNET_PeerIdentity *put_path,
1982 unsigned int get_path_length,
1983 const struct GNUNET_PeerIdentity *get_path,
1987 struct PeerInfo *peer = cls;
1990 pp = GNUNET_STRINGS_pp2s (put_path,
1992 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1993 "Found local result for %s (PP: %s)\n",
1997 GDS_NEIGHBOURS_handle_reply (peer->id,
2001 put_path_length, put_path,
2002 get_path_length, get_path,
2008 * Check validity of p2p get request.
2010 * @param cls closure with the `struct PeerInfo` of the sender
2011 * @param get the message
2012 * @return #GNUNET_OK if the message is well-formed
2015 check_dht_p2p_get (void *cls,
2016 const struct PeerGetMessage *get)
2018 uint32_t xquery_size;
2021 msize = ntohs (get->header.size);
2022 xquery_size = ntohl (get->xquery_size);
2023 if (msize < sizeof (struct PeerGetMessage) + xquery_size)
2025 GNUNET_break_op (0);
2026 return GNUNET_SYSERR;
2033 * Core handler for p2p get requests.
2035 * @param cls closure with the `struct PeerInfo` of the sender
2036 * @param get the message
2039 handle_dht_p2p_get (void *cls,
2040 const struct PeerGetMessage *get)
2042 struct PeerInfo *peer = cls;
2043 uint32_t xquery_size;
2044 size_t reply_bf_size;
2046 enum GNUNET_BLOCK_Type type;
2047 enum GNUNET_DHT_RouteOption options;
2048 enum GNUNET_BLOCK_EvaluationResult eval;
2049 struct GNUNET_BLOCK_Group *bg;
2050 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
2054 /* parse and validate message */
2055 msize = ntohs (get->header.size);
2056 xquery_size = ntohl (get->xquery_size);
2057 reply_bf_size = msize - (sizeof (struct PeerGetMessage) + xquery_size);
2058 type = ntohl (get->type);
2059 options = ntohl (get->options);
2060 xquery = (const char *) &get[1];
2061 GNUNET_STATISTICS_update (GDS_stats,
2062 gettext_noop ("# P2P GET requests received"),
2065 GNUNET_STATISTICS_update (GDS_stats,
2066 gettext_noop ("# P2P GET bytes received"),
2069 if (GNUNET_YES == log_route_details_stderr)
2073 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
2074 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
2075 "R5N GET %s: %s->%s (%u, %u=>%u) xq: %.*s\n",
2076 GNUNET_h2s (&get->key),
2077 GNUNET_i2s (peer->id),
2079 ntohl(get->hop_count),
2080 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
2082 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
2084 ntohl(get->xquery_size),
2089 = GNUNET_BLOCK_evaluate (GDS_block_context,
2092 GNUNET_BLOCK_EO_NONE,
2098 if (eval != GNUNET_BLOCK_EVALUATION_REQUEST_VALID)
2100 /* request invalid or block type not supported */
2101 GNUNET_break_op (eval == GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED);
2104 peer_bf = GNUNET_CONTAINER_bloomfilter_init (get->bloomfilter,
2106 GNUNET_CONSTANTS_BLOOMFILTER_K);
2107 GNUNET_break_op (GNUNET_YES ==
2108 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
2110 bg = GNUNET_BLOCK_group_create (GDS_block_context,
2113 &xquery[xquery_size],
2118 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2119 "GET for %s at %s after %u hops\n",
2120 GNUNET_h2s (&get->key),
2121 GNUNET_i2s (&my_identity),
2122 (unsigned int) ntohl (get->hop_count));
2123 /* local lookup (this may update the reply_bf) */
2124 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
2125 (am_closest_peer (&get->key,
2128 if ((0 != (options & GNUNET_DHT_RO_FIND_PEER)))
2130 GNUNET_STATISTICS_update (GDS_stats,
2131 gettext_noop ("# P2P FIND PEER requests processed"),
2134 handle_find_peer (peer->id,
2140 eval = GDS_DATACACHE_handle_get (&get->key,
2145 &handle_local_result,
2151 GNUNET_STATISTICS_update (GDS_stats,
2152 gettext_noop ("# P2P GET requests ONLY routed"),
2157 /* remember request for routing replies */
2158 GDS_ROUTING_add (peer->id,
2160 bg, /* bg now owned by routing, but valid at least until end of this function! */
2166 /* P2P forwarding */
2167 forwarded = GNUNET_NO;
2168 if (eval != GNUNET_BLOCK_EVALUATION_OK_LAST)
2169 forwarded = GDS_NEIGHBOURS_handle_get (type,
2171 ntohl (get->desired_replication_level),
2172 ntohl (get->hop_count),
2178 GDS_CLIENTS_process_get (options
2179 | (GNUNET_OK == forwarded)
2180 ? GNUNET_DHT_RO_LAST_HOP : 0,
2182 ntohl (get->hop_count),
2183 ntohl (get->desired_replication_level),
2188 /* clean up; note that 'bg' is owned by routing now! */
2189 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
2194 * Check validity of p2p result message.
2196 * @param cls closure
2197 * @param message message
2198 * @return #GNUNET_YES if the message is well-formed
2201 check_dht_p2p_result (void *cls,
2202 const struct PeerResultMessage *prm)
2204 uint32_t get_path_length;
2205 uint32_t put_path_length;
2208 msize = ntohs (prm->header.size);
2209 put_path_length = ntohl (prm->put_path_length);
2210 get_path_length = ntohl (prm->get_path_length);
2212 sizeof (struct PeerResultMessage) + (get_path_length +
2214 sizeof (struct GNUNET_PeerIdentity)) ||
2216 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
2218 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2220 GNUNET_break_op (0);
2221 return GNUNET_SYSERR;
2228 * Process a reply, after the @a get_path has been updated.
2230 * @param expiration_time when does the reply expire
2231 * @param key key matching the query
2232 * @param get_path_length number of entries in @a get_path
2233 * @param get_path path the reply has taken
2234 * @param put_path_length number of entries in @a put_path
2235 * @param put_path path the PUT has taken
2236 * @param type type of the block
2237 * @param data_size number of bytes in @a data
2238 * @param data payload of the reply
2241 process_reply_with_path (struct GNUNET_TIME_Absolute expiration_time,
2242 const struct GNUNET_HashCode *key,
2243 unsigned int get_path_length,
2244 const struct GNUNET_PeerIdentity *get_path,
2245 unsigned int put_path_length,
2246 const struct GNUNET_PeerIdentity *put_path,
2247 enum GNUNET_BLOCK_Type type,
2251 /* forward to local clients */
2252 GDS_CLIENTS_handle_reply (expiration_time,
2261 GDS_CLIENTS_process_get_resp (type,
2270 if (GNUNET_YES == cache_results)
2272 struct GNUNET_PeerIdentity xput_path[get_path_length + 1 + put_path_length];
2274 GNUNET_memcpy (xput_path,
2276 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2277 GNUNET_memcpy (&xput_path[put_path_length],
2279 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2281 GDS_DATACACHE_handle_put (expiration_time,
2283 get_path_length + put_path_length,
2289 /* forward to other peers */
2290 GDS_ROUTING_process (type,
2303 * Core handler for p2p result messages.
2305 * @param cls closure
2306 * @param message message
2309 handle_dht_p2p_result (void *cls,
2310 const struct PeerResultMessage *prm)
2312 struct PeerInfo *peer = cls;
2313 const struct GNUNET_PeerIdentity *put_path;
2314 const struct GNUNET_PeerIdentity *get_path;
2316 uint32_t get_path_length;
2317 uint32_t put_path_length;
2320 enum GNUNET_BLOCK_Type type;
2322 /* parse and validate message */
2323 msize = ntohs (prm->header.size);
2324 put_path_length = ntohl (prm->put_path_length);
2325 get_path_length = ntohl (prm->get_path_length);
2326 put_path = (const struct GNUNET_PeerIdentity *) &prm[1];
2327 get_path = &put_path[put_path_length];
2328 type = ntohl (prm->type);
2329 data = (const void *) &get_path[get_path_length];
2330 data_size = msize - (sizeof (struct PeerResultMessage) +
2332 put_path_length) * sizeof (struct GNUNET_PeerIdentity));
2333 GNUNET_STATISTICS_update (GDS_stats,
2334 gettext_noop ("# P2P RESULTS received"),
2337 GNUNET_STATISTICS_update (GDS_stats,
2338 gettext_noop ("# P2P RESULT bytes received"),
2341 if (GNUNET_YES == log_route_details_stderr)
2347 gp = GNUNET_STRINGS_pp2s (get_path,
2349 pp = GNUNET_STRINGS_pp2s (put_path,
2351 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
2352 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
2353 "R5N RESULT %s: %s->%s (GP: %s, PP: %s)\n",
2354 GNUNET_h2s (&prm->key),
2355 GNUNET_i2s (peer->id),
2363 /* if we got a HELLO, consider it for our own routing table */
2364 if (GNUNET_BLOCK_TYPE_DHT_HELLO == type)
2366 const struct GNUNET_MessageHeader *h;
2367 struct GNUNET_PeerIdentity pid;
2369 /* Should be a HELLO, validate and consider using it! */
2370 if (data_size < sizeof (struct GNUNET_HELLO_Message))
2372 GNUNET_break_op (0);
2376 if (data_size != ntohs (h->size))
2378 GNUNET_break_op (0);
2382 GNUNET_HELLO_get_id ((const struct GNUNET_HELLO_Message *) h,
2385 GNUNET_break_op (0);
2388 if ( (GNUNET_YES != disable_try_connect) &&
2389 (0 != memcmp (&my_identity,
2391 sizeof (struct GNUNET_PeerIdentity))) )
2397 /* First, check if 'peer' is already on the path, and if
2398 so, truncate it instead of expanding. */
2399 for (unsigned int i=0;i<=get_path_length;i++)
2400 if (0 == memcmp (&get_path[i],
2402 sizeof (struct GNUNET_PeerIdentity)))
2404 process_reply_with_path (GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2416 /* Need to append 'peer' to 'get_path' (normal case) */
2418 struct GNUNET_PeerIdentity xget_path[get_path_length + 1];
2420 GNUNET_memcpy (xget_path,
2422 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2423 xget_path[get_path_length] = *peer->id;
2425 process_reply_with_path (GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2427 get_path_length + 1,
2439 * Initialize neighbours subsystem.
2441 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2444 GDS_NEIGHBOURS_init ()
2446 struct GNUNET_MQ_MessageHandler core_handlers[] = {
2447 GNUNET_MQ_hd_var_size (dht_p2p_get,
2448 GNUNET_MESSAGE_TYPE_DHT_P2P_GET,
2449 struct PeerGetMessage,
2451 GNUNET_MQ_hd_var_size (dht_p2p_put,
2452 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT,
2453 struct PeerPutMessage,
2455 GNUNET_MQ_hd_var_size (dht_p2p_result,
2456 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT,
2457 struct PeerResultMessage,
2459 GNUNET_MQ_handler_end ()
2461 unsigned long long temp_config_num;
2464 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2466 "DISABLE_TRY_CONNECT");
2468 GNUNET_CONFIGURATION_get_value_number (GDS_cfg,
2472 bucket_size = (unsigned int) temp_config_num;
2474 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2478 log_route_details_stderr =
2479 (NULL != getenv("GNUNET_DHT_ROUTE_DEBUG")) ? GNUNET_YES : GNUNET_NO;
2480 ats_ch = GNUNET_ATS_connectivity_init (GDS_cfg);
2481 core_api = GNUNET_CORE_connect (GDS_cfg,
2484 &handle_core_connect,
2485 &handle_core_disconnect,
2487 if (NULL == core_api)
2488 return GNUNET_SYSERR;
2489 all_connected_peers = GNUNET_CONTAINER_multipeermap_create (256,
2491 all_desired_peers = GNUNET_CONTAINER_multipeermap_create (256,
2498 * Shutdown neighbours subsystem.
2501 GDS_NEIGHBOURS_done ()
2503 if (NULL == core_api)
2505 GNUNET_CORE_disconnect (core_api);
2508 GNUNET_CONTAINER_multipeermap_size (all_connected_peers));
2509 GNUNET_CONTAINER_multipeermap_destroy (all_connected_peers);
2510 all_connected_peers = NULL;
2511 GNUNET_CONTAINER_multipeermap_iterate (all_desired_peers,
2514 GNUNET_CONTAINER_multipeermap_destroy (all_desired_peers);
2515 all_desired_peers = NULL;
2516 GNUNET_ATS_connectivity_done (ats_ch);
2518 GNUNET_assert (NULL == find_peer_task);
2523 * Get the ID of the local node.
2525 * @return identity of the local node
2527 struct GNUNET_PeerIdentity *
2528 GDS_NEIGHBOURS_get_id ()
2530 return &my_identity;
2534 /* end of gnunet-service-dht_neighbours.c */