2 This file is part of GNUnet.
3 Copyright (C) 2009-2016 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 * How many buckets will we allow total.
54 #define MAX_BUCKETS sizeof (struct GNUNET_HashCode) * 8
57 * What is the maximum number of peers in a given bucket.
59 #define DEFAULT_BUCKET_SIZE 8
62 * Desired replication level for FIND PEER requests
64 #define FIND_PEER_REPLICATION_LEVEL 4
67 * Maximum allowed replication level for all requests.
69 #define MAXIMUM_REPLICATION_LEVEL 16
72 * Maximum allowed number of pending messages per peer.
74 #define MAXIMUM_PENDING_PER_PEER 64
77 * How long at least to wait before sending another find peer request.
79 #define DHT_MINIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
82 * How long at most to wait before sending another find peer request.
84 #define DHT_MAXIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
87 * How long at most to wait for transmission of a GET request to another peer?
89 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
92 * Hello address expiration
94 extern struct GNUNET_TIME_Relative hello_expiration;
97 GNUNET_NETWORK_STRUCT_BEGIN
102 struct PeerPutMessage
105 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
107 struct GNUNET_MessageHeader header;
112 uint32_t options GNUNET_PACKED;
117 uint32_t type GNUNET_PACKED;
122 uint32_t hop_count GNUNET_PACKED;
125 * Replication level for this message
127 uint32_t desired_replication_level GNUNET_PACKED;
130 * Length of the PUT path that follows (if tracked).
132 uint32_t put_path_length GNUNET_PACKED;
135 * When does the content expire?
137 struct GNUNET_TIME_AbsoluteNBO expiration_time;
140 * Bloomfilter (for peer identities) to stop circular routes
142 char bloomfilter[DHT_BLOOM_SIZE];
145 * The key we are storing under.
147 struct GNUNET_HashCode key;
149 /* put path (if tracked) */
159 struct PeerResultMessage
162 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
164 struct GNUNET_MessageHeader header;
169 uint32_t type GNUNET_PACKED;
172 * Length of the PUT path that follows (if tracked).
174 uint32_t put_path_length GNUNET_PACKED;
177 * Length of the GET path that follows (if tracked).
179 uint32_t get_path_length GNUNET_PACKED;
182 * When does the content expire?
184 struct GNUNET_TIME_AbsoluteNBO expiration_time;
187 * The key of the corresponding GET request.
189 struct GNUNET_HashCode key;
191 /* put path (if tracked) */
193 /* get path (if tracked) */
203 struct PeerGetMessage
206 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
208 struct GNUNET_MessageHeader header;
213 uint32_t options GNUNET_PACKED;
216 * Desired content type.
218 uint32_t type GNUNET_PACKED;
223 uint32_t hop_count GNUNET_PACKED;
226 * Desired replication level for this request.
228 uint32_t desired_replication_level GNUNET_PACKED;
231 * Size of the extended query.
233 uint32_t xquery_size;
236 * Bloomfilter mutator.
241 * Bloomfilter (for peer identities) to stop circular routes
243 char bloomfilter[DHT_BLOOM_SIZE];
246 * The key we are looking for.
248 struct GNUNET_HashCode key;
252 /* result bloomfilter */
255 GNUNET_NETWORK_STRUCT_END
259 * Entry for a peer in a bucket.
264 * Next peer entry (DLL)
266 struct PeerInfo *next;
269 * Prev peer entry (DLL)
271 struct PeerInfo *prev;
274 * Handle for sending messages to this peer.
276 struct GNUNET_MQ_Handle *mq;
279 * What is the identity of the peer?
281 const struct GNUNET_PeerIdentity *id;
286 struct GNUNET_HashCode phash;
289 * Which bucket is this peer in?
297 * Peers are grouped into buckets.
304 struct PeerInfo *head;
309 struct PeerInfo *tail;
312 * Number of peers in the bucket.
314 unsigned int peers_size;
319 * Information about a peer that we would like to connect to.
325 * Handle to active HELLO offer operation, or NULL.
327 struct GNUNET_TRANSPORT_OfferHelloHandle *oh;
330 * Handle to active connectivity suggestion operation, or NULL.
332 struct GNUNET_ATS_ConnectivitySuggestHandle *sh;
335 * How much would we like to connect to this peer?
342 * Do we cache all results that we are routing in the local datacache?
344 static int cache_results;
347 * Should routing details be logged to stderr (for debugging)?
349 static int log_route_details_stderr;
352 * The lowest currently used bucket, initially 0 (for 0-bits matching bucket).
354 static unsigned int closest_bucket;
357 * How many peers have we added since we sent out our last
360 static unsigned int newly_found_peers;
363 * Option for testing that disables the 'connect' function of the DHT.
365 static int disable_try_connect;
368 * The buckets. Array of size #MAX_BUCKETS. Offset 0 means 0 bits matching.
370 static struct PeerBucket k_buckets[MAX_BUCKETS];
373 * Hash map of all CORE-connected peers, for easy removal from
374 * #k_buckets on disconnect. Values are of type `struct PeerInfo`.
376 static struct GNUNET_CONTAINER_MultiPeerMap *all_connected_peers;
379 * Hash map of all peers we would like to be connected to.
380 * Values are of type `struct ConnectInfo`.
382 static struct GNUNET_CONTAINER_MultiPeerMap *all_desired_peers;
385 * Maximum size for each bucket.
387 static unsigned int bucket_size = DEFAULT_BUCKET_SIZE;
390 * Task that sends FIND PEER requests.
392 static struct GNUNET_SCHEDULER_Task *find_peer_task;
395 * Identity of this peer.
397 static struct GNUNET_PeerIdentity my_identity;
400 * Hash of the identity of this peer.
402 static struct GNUNET_HashCode my_identity_hash;
407 static struct GNUNET_CORE_Handle *core_api;
410 * Handle to ATS connectivity.
412 static struct GNUNET_ATS_ConnectivityHandle *ats_ch;
416 * Find the optimal bucket for this key.
418 * @param hc the hashcode to compare our identity to
419 * @return the proper bucket index, or GNUNET_SYSERR
420 * on error (same hashcode)
423 find_bucket (const struct GNUNET_HashCode *hc)
427 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash, hc);
428 if (bits == MAX_BUCKETS)
430 /* How can all bits match? Got my own ID? */
432 return GNUNET_SYSERR;
434 return MAX_BUCKETS - bits - 1;
439 * Function called when #GNUNET_TRANSPORT_offer_hello() is done.
440 * Clean up the "oh" field in the @a cls
442 * @param cls a `struct ConnectInfo`
445 offer_hello_done (void *cls)
447 struct ConnectInfo *ci = cls;
454 * Function called for all entries in #all_desired_peers to clean up.
457 * @param peer peer the entry is for
458 * @param value the value to remove
459 * @return #GNUNET_YES
462 free_connect_info (void *cls,
463 const struct GNUNET_PeerIdentity *peer,
466 struct ConnectInfo *ci = value;
468 GNUNET_assert (GNUNET_YES ==
469 GNUNET_CONTAINER_multipeermap_remove (all_desired_peers,
474 GNUNET_ATS_connectivity_suggest_cancel (ci->sh);
479 GNUNET_TRANSPORT_offer_hello_cancel (ci->oh);
488 * Consider if we want to connect to a given peer, and if so
489 * let ATS know. If applicable, the HELLO is offered to the
492 * @param pid peer to consider connectivity requirements for
493 * @param h a HELLO message, or NULL
496 try_connect (const struct GNUNET_PeerIdentity *pid,
497 const struct GNUNET_MessageHeader *h)
500 struct GNUNET_HashCode pid_hash;
501 struct ConnectInfo *ci;
504 GNUNET_CRYPTO_hash (pid,
505 sizeof (struct GNUNET_PeerIdentity),
507 bucket = find_bucket (&pid_hash);
510 ci = GNUNET_CONTAINER_multipeermap_get (all_desired_peers,
513 if (k_buckets[bucket].peers_size < bucket_size)
514 strength = (bucket_size - k_buckets[bucket].peers_size) * bucket;
516 strength = bucket; /* minimum value of connectivity */
518 GNUNET_CONTAINER_multipeermap_contains (all_connected_peers,
520 strength *= 2; /* double for connected peers */
521 else if (k_buckets[bucket].peers_size > bucket_size)
522 strength = 0; /* bucket full, we really do not care about more */
524 if ( (0 == strength) &&
527 /* release request */
528 GNUNET_assert (GNUNET_YES ==
529 free_connect_info (NULL,
536 ci = GNUNET_new (struct ConnectInfo);
537 GNUNET_assert (GNUNET_OK ==
538 GNUNET_CONTAINER_multipeermap_put (all_desired_peers,
541 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
543 if ( (NULL != ci->oh) &&
545 GNUNET_TRANSPORT_offer_hello_cancel (ci->oh);
547 ci->oh = GNUNET_TRANSPORT_offer_hello (GDS_cfg,
551 if ( (NULL != ci->sh) &&
552 (ci->strength != strength) )
553 GNUNET_ATS_connectivity_suggest_cancel (ci->sh);
554 if (ci->strength != strength)
555 ci->sh = GNUNET_ATS_connectivity_suggest (ats_ch,
558 ci->strength = strength;
563 * Function called for each peer in #all_desired_peers during
564 * #update_connect_preferences() if we have reason to adjust
565 * the strength of our desire to keep connections to certain
566 * peers. Calls #try_connect() to update the calculations for
570 * @param pid peer to update
571 * @param value unused
572 * @return #GNUNET_YES (continue to iterate)
575 update_desire_strength (void *cls,
576 const struct GNUNET_PeerIdentity *pid,
579 try_connect (pid, NULL);
585 * Update our preferences for connectivity as given to ATS.
587 * @param cls the `struct PeerInfo` of the peer
588 * @param tc scheduler context.
591 update_connect_preferences ()
593 GNUNET_CONTAINER_multipeermap_iterate (all_desired_peers,
594 &update_desire_strength,
600 * Closure for #add_known_to_bloom().
602 struct BloomConstructorContext
605 * Bloom filter under construction.
607 struct GNUNET_CONTAINER_BloomFilter *bloom;
617 * Add each of the peers we already know to the bloom filter of
618 * the request so that we don't get duplicate HELLOs.
620 * @param cls the 'struct BloomConstructorContext'.
621 * @param key peer identity to add to the bloom filter
622 * @param value value the peer information (unused)
623 * @return #GNUNET_YES (we should continue to iterate)
626 add_known_to_bloom (void *cls,
627 const struct GNUNET_PeerIdentity *key,
630 struct BloomConstructorContext *ctx = cls;
631 struct GNUNET_HashCode key_hash;
632 struct GNUNET_HashCode mh;
634 GNUNET_CRYPTO_hash (key,
635 sizeof (struct GNUNET_PeerIdentity),
637 GNUNET_BLOCK_mingle_hash (&key_hash,
640 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
641 "Adding known peer (%s) to bloomfilter for FIND PEER with mutation %u\n",
644 GNUNET_CONTAINER_bloomfilter_add (ctx->bloom,
651 * Task to send a find peer message for our own peer identifier
652 * so that we can find the closest peers in the network to ourselves
653 * and attempt to connect to them.
655 * @param cls closure for this task
658 send_find_peer_message (void *cls)
660 struct GNUNET_TIME_Relative next_send_time;
661 struct BloomConstructorContext bcc;
662 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
664 find_peer_task = NULL;
665 if (newly_found_peers > bucket_size)
667 /* If we are finding many peers already, no need to send out our request right now! */
669 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
670 &send_find_peer_message,
672 newly_found_peers = 0;
676 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
679 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE,
680 GNUNET_CONSTANTS_BLOOMFILTER_K);
681 GNUNET_CONTAINER_multipeermap_iterate (all_connected_peers,
684 GNUNET_STATISTICS_update (GDS_stats,
685 gettext_noop ("# FIND PEER messages initiated"),
689 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE,
690 GNUNET_CONSTANTS_BLOOMFILTER_K);
691 // FIXME: pass priority!?
692 GDS_NEIGHBOURS_handle_get (GNUNET_BLOCK_TYPE_DHT_HELLO,
693 GNUNET_DHT_RO_FIND_PEER,
694 FIND_PEER_REPLICATION_LEVEL, 0,
695 &my_identity_hash, NULL, 0, bcc.bloom,
696 bcc.bf_mutator, peer_bf);
697 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
698 GNUNET_CONTAINER_bloomfilter_free (bcc.bloom);
699 /* schedule next round */
700 next_send_time.rel_value_us =
701 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value_us +
702 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
703 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value_us /
704 (newly_found_peers + 1));
705 newly_found_peers = 0;
706 GNUNET_assert (NULL == find_peer_task);
708 GNUNET_SCHEDULER_add_delayed (next_send_time,
709 &send_find_peer_message,
715 * Method called whenever a peer connects.
718 * @param peer peer identity this notification is about
719 * @param mq message queue for sending messages to @a peer
720 * @return our `struct PeerInfo` for @a peer
723 handle_core_connect (void *cls,
724 const struct GNUNET_PeerIdentity *peer,
725 struct GNUNET_MQ_Handle *mq)
729 /* Check for connect to self message */
730 if (0 == memcmp (&my_identity,
732 sizeof (struct GNUNET_PeerIdentity)))
734 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
737 GNUNET_assert (GNUNET_NO ==
738 GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
740 GNUNET_STATISTICS_update (GDS_stats,
741 gettext_noop ("# peers connected"),
744 pi = GNUNET_new (struct PeerInfo);
747 GNUNET_CRYPTO_hash (peer,
748 sizeof (struct GNUNET_PeerIdentity),
750 pi->peer_bucket = find_bucket (&pi->phash);
751 GNUNET_assert ( (pi->peer_bucket >= 0) &&
752 (pi->peer_bucket < MAX_BUCKETS) );
753 GNUNET_CONTAINER_DLL_insert_tail (k_buckets[pi->peer_bucket].head,
754 k_buckets[pi->peer_bucket].tail,
756 k_buckets[pi->peer_bucket].peers_size++;
757 closest_bucket = GNUNET_MAX (closest_bucket,
759 GNUNET_assert (GNUNET_OK ==
760 GNUNET_CONTAINER_multipeermap_put (all_connected_peers,
763 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
764 if ( (pi->peer_bucket > 0) &&
765 (k_buckets[pi->peer_bucket].peers_size <= bucket_size))
767 update_connect_preferences ();
770 if ( (1 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
771 (GNUNET_YES != disable_try_connect))
773 /* got a first connection, good time to start with FIND PEER requests... */
774 GNUNET_assert (NULL == find_peer_task);
775 find_peer_task = GNUNET_SCHEDULER_add_now (&send_find_peer_message,
783 * Method called whenever a peer disconnects.
786 * @param peer peer identity this notification is about
787 * @param internal_cls our `struct PeerInfo` for @a peer
790 handle_core_disconnect (void *cls,
791 const struct GNUNET_PeerIdentity *peer,
794 struct PeerInfo *to_remove = internal_cls;
796 /* Check for disconnect from self message */
797 if (NULL == to_remove)
799 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
802 GNUNET_STATISTICS_update (GDS_stats,
803 gettext_noop ("# peers connected"),
806 GNUNET_assert (GNUNET_YES ==
807 GNUNET_CONTAINER_multipeermap_remove (all_connected_peers,
810 if ( (0 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
811 (GNUNET_YES != disable_try_connect) )
813 GNUNET_SCHEDULER_cancel (find_peer_task);
814 find_peer_task = NULL;
816 GNUNET_assert (to_remove->peer_bucket >= 0);
817 GNUNET_CONTAINER_DLL_remove (k_buckets[to_remove->peer_bucket].head,
818 k_buckets[to_remove->peer_bucket].tail,
820 GNUNET_assert (k_buckets[to_remove->peer_bucket].peers_size > 0);
821 k_buckets[to_remove->peer_bucket].peers_size--;
822 while ( (closest_bucket > 0) &&
823 (0 == k_buckets[to_remove->peer_bucket].peers_size) )
825 if (k_buckets[to_remove->peer_bucket].peers_size < bucket_size)
826 update_connect_preferences ();
827 GNUNET_free (to_remove);
832 * To how many peers should we (on average) forward the request to
833 * obtain the desired target_replication count (on average).
835 * @param hop_count number of hops the message has traversed
836 * @param target_replication the number of total paths desired
837 * @return Some number of peers to forward the message to
840 get_forward_count (uint32_t hop_count,
841 uint32_t target_replication)
843 uint32_t random_value;
844 uint32_t forward_count;
847 if (hop_count > GDS_NSE_get () * 4.0)
849 /* forcefully terminate */
850 GNUNET_STATISTICS_update (GDS_stats,
851 gettext_noop ("# requests TTL-dropped"),
855 if (hop_count > GDS_NSE_get () * 2.0)
857 /* Once we have reached our ideal number of hops, only forward to 1 peer */
860 /* bound by system-wide maximum */
862 GNUNET_MIN (MAXIMUM_REPLICATION_LEVEL, target_replication);
864 1 + (target_replication - 1.0) / (GDS_NSE_get () +
865 ((float) (target_replication - 1.0) *
867 /* Set forward count to floor of target_value */
868 forward_count = (uint32_t) target_value;
869 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
870 target_value = target_value - forward_count;
872 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
873 if (random_value < (target_value * UINT32_MAX))
875 return forward_count;
880 * Compute the distance between have and target as a 32-bit value.
881 * Differences in the lower bits must count stronger than differences
882 * 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,
892 const struct GNUNET_HashCode *have)
899 /* We have to represent the distance between two 2^9 (=512)-bit
900 * numbers as a 2^5 (=32)-bit number with "0" being used for the
901 * two numbers being identical; furthermore, we need to
902 * guarantee that a difference in the number of matching
903 * bits is always represented in the result.
905 * We use 2^32/2^9 numerical values to distinguish between
906 * hash codes that have the same LSB bit distance and
907 * use the highest 2^9 bits of the result to signify the
908 * number of (mis)matching LSB bits; if we have 0 matching
909 * and hence 512 mismatching LSB bits we return -1 (since
910 * 512 itself cannot be represented with 9 bits) */
912 /* first, calculate the most significant 9 bits of our
913 * result, aka the number of LSBs */
914 bucket = GNUNET_CRYPTO_hash_matching_bits (target,
916 /* bucket is now a value between 0 and 512 */
918 return 0; /* perfect match */
920 return (unsigned int) -1; /* LSB differs; use max (if we did the bit-shifting
921 * below, we'd end up with max+1 (overflow)) */
923 /* calculate the most significant bits of the final result */
924 msb = (512 - bucket) << (32 - 9);
925 /* calculate the 32-9 least significant bits of the final result by
926 * looking at the differences in the 32-9 bits following the
927 * mismatching bit at 'bucket' */
930 (i < sizeof (struct GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9); i++)
932 if (GNUNET_CRYPTO_hash_get_bit (target, i) !=
933 GNUNET_CRYPTO_hash_get_bit (have, i))
934 lsb |= (1 << (bucket + 32 - 9 - i)); /* first bit set will be 10,
935 * last bit set will be 31 -- if
936 * i does not reach 512 first... */
943 * Check whether my identity is closer than any known peers. If a
944 * non-null bloomfilter is given, check if this is the closest peer
945 * that hasn't already been routed to.
947 * @param key hash code to check closeness to
948 * @param bloom bloomfilter, exclude these entries from the decision
949 * @return #GNUNET_YES if node location is closest,
950 * #GNUNET_NO otherwise.
953 am_closest_peer (const struct GNUNET_HashCode *key,
954 const struct GNUNET_CONTAINER_BloomFilter *bloom)
960 struct PeerInfo *pos;
962 if (0 == memcmp (&my_identity_hash, key, sizeof (struct GNUNET_HashCode)))
964 bucket_num = find_bucket (key);
965 GNUNET_assert (bucket_num >= 0);
966 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
968 pos = k_buckets[bucket_num].head;
970 while ((NULL != pos) && (count < bucket_size))
972 if ((NULL != bloom) &&
974 GNUNET_CONTAINER_bloomfilter_test (bloom,
978 continue; /* Skip already checked entries */
980 other_bits = GNUNET_CRYPTO_hash_matching_bits (&pos->phash,
982 if (other_bits > bits)
984 if (other_bits == bits) /* We match the same number of bits */
988 /* No peers closer, we are the closest! */
994 * Select a peer from the routing table that would be a good routing
995 * destination for sending a message for "key". The resulting peer
996 * must not be in the set of blocked peers.<p>
998 * Note that we should not ALWAYS select the closest peer to the
999 * target, peers further away from the target should be chosen with
1000 * exponentially declining probability.
1002 * FIXME: double-check that this is fine
1005 * @param key the key we are selecting a peer to route to
1006 * @param bloom a bloomfilter containing entries this request has seen already
1007 * @param hops how many hops has this message traversed thus far
1008 * @return Peer to route to, or NULL on error
1010 static struct PeerInfo *
1011 select_peer (const struct GNUNET_HashCode *key,
1012 const struct GNUNET_CONTAINER_BloomFilter *bloom,
1017 unsigned int selected;
1018 struct PeerInfo *pos;
1020 unsigned int smallest_distance;
1021 struct PeerInfo *chosen;
1023 if (hops >= GDS_NSE_get ())
1025 /* greedy selection (closest peer that is not in bloomfilter) */
1026 smallest_distance = UINT_MAX;
1028 for (bc = 0; bc <= closest_bucket; bc++)
1030 pos = k_buckets[bc].head;
1032 while ((pos != NULL) && (count < bucket_size))
1034 if ((bloom == NULL) ||
1036 GNUNET_CONTAINER_bloomfilter_test (bloom,
1039 dist = get_distance (key,
1041 if (dist < smallest_distance)
1044 smallest_distance = dist;
1049 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1050 "Excluded peer `%s' due to BF match in greedy routing for %s\n",
1051 GNUNET_i2s (pos->id),
1053 GNUNET_STATISTICS_update (GDS_stats,
1054 gettext_noop ("# Peers excluded from routing due to Bloomfilter"),
1057 dist = get_distance (key,
1059 if (dist < smallest_distance)
1062 smallest_distance = dist;
1070 GNUNET_STATISTICS_update (GDS_stats,
1071 gettext_noop ("# Peer selection failed"), 1,
1076 /* select "random" peer */
1077 /* count number of peers that are available and not filtered */
1079 for (bc = 0; bc <= closest_bucket; bc++)
1081 pos = k_buckets[bc].head;
1082 while ((pos != NULL) && (count < bucket_size))
1084 if ((bloom != NULL) &&
1086 GNUNET_CONTAINER_bloomfilter_test (bloom,
1089 GNUNET_STATISTICS_update (GDS_stats,
1091 ("# Peers excluded from routing due to Bloomfilter"),
1093 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1094 "Excluded peer `%s' due to BF match in random routing for %s\n",
1095 GNUNET_i2s (pos->id),
1098 continue; /* Ignore bloomfiltered peers */
1104 if (0 == count) /* No peers to select from! */
1106 GNUNET_STATISTICS_update (GDS_stats,
1107 gettext_noop ("# Peer selection failed"), 1,
1111 /* Now actually choose a peer */
1112 selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1115 for (bc = 0; bc <= closest_bucket; bc++)
1117 for (pos = k_buckets[bc].head; ((pos != NULL) && (count < bucket_size)); pos = pos->next)
1119 if ((bloom != NULL) &&
1121 GNUNET_CONTAINER_bloomfilter_test (bloom,
1124 continue; /* Ignore bloomfiltered peers */
1126 if (0 == selected--)
1136 * Compute the set of peers that the given request should be
1139 * @param key routing key
1140 * @param bloom bloom filter excluding peers as targets, all selected
1141 * peers will be added to the bloom filter
1142 * @param hop_count number of hops the request has traversed so far
1143 * @param target_replication desired number of replicas
1144 * @param targets where to store an array of target peers (to be
1145 * free'd by the caller)
1146 * @return number of peers returned in 'targets'.
1149 get_target_peers (const struct GNUNET_HashCode *key,
1150 struct GNUNET_CONTAINER_BloomFilter *bloom,
1152 uint32_t target_replication,
1153 struct PeerInfo ***targets)
1157 struct PeerInfo **rtargets;
1158 struct PeerInfo *nxt;
1160 GNUNET_assert (NULL != bloom);
1161 ret = get_forward_count (hop_count,
1162 target_replication);
1168 rtargets = GNUNET_new_array (ret,
1170 for (off = 0; off < ret; off++)
1172 nxt = select_peer (key, bloom, hop_count);
1175 rtargets[off] = nxt;
1176 GNUNET_break (GNUNET_NO ==
1177 GNUNET_CONTAINER_bloomfilter_test (bloom,
1179 GNUNET_CONTAINER_bloomfilter_add (bloom,
1182 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1183 "Selected %u/%u peers at hop %u for %s (target was %u)\n",
1185 GNUNET_CONTAINER_multipeermap_size (all_connected_peers),
1186 (unsigned int) hop_count,
1191 GNUNET_free (rtargets);
1195 *targets = rtargets;
1196 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1197 "Forwarding query `%s' to %u peers (goal was %u peers)\n",
1206 * Perform a PUT operation. Forwards the given request to other
1207 * peers. Does not store the data locally. Does not give the
1208 * data to local clients. May do nothing if this is the only
1209 * peer in the network (or if we are the closest peer in the
1212 * @param type type of the block
1213 * @param options routing options
1214 * @param desired_replication_level desired replication count
1215 * @param expiration_time when does the content expire
1216 * @param hop_count how many hops has this message traversed so far
1217 * @param bf Bloom filter of peers this PUT has already traversed
1218 * @param key key for the content
1219 * @param put_path_length number of entries in @a put_path
1220 * @param put_path peers this request has traversed so far (if tracked)
1221 * @param data payload to store
1222 * @param data_size number of bytes in @a data
1223 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
1226 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1227 enum GNUNET_DHT_RouteOption options,
1228 uint32_t desired_replication_level,
1229 struct GNUNET_TIME_Absolute expiration_time,
1231 struct GNUNET_CONTAINER_BloomFilter *bf,
1232 const struct GNUNET_HashCode *key,
1233 unsigned int put_path_length,
1234 struct GNUNET_PeerIdentity *put_path,
1238 unsigned int target_count;
1240 struct PeerInfo **targets;
1241 struct PeerInfo *target;
1243 struct GNUNET_MQ_Envelope *env;
1244 struct PeerPutMessage *ppm;
1245 struct GNUNET_PeerIdentity *pp;
1246 unsigned int skip_count;
1248 GNUNET_assert (NULL != bf);
1249 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1250 "Adding myself (%s) to PUT bloomfilter for %s\n",
1251 GNUNET_i2s (&my_identity),
1253 GNUNET_CONTAINER_bloomfilter_add (bf, &my_identity_hash);
1254 GNUNET_STATISTICS_update (GDS_stats,
1255 gettext_noop ("# PUT requests routed"),
1259 = get_target_peers (key,
1262 desired_replication_level,
1264 if (0 == target_count)
1266 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1267 "Routing PUT for %s terminates after %u hops at %s\n",
1269 (unsigned int) hop_count,
1270 GNUNET_i2s (&my_identity));
1273 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size;
1274 if (msize + sizeof (struct PeerPutMessage)
1275 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1277 put_path_length = 0;
1280 if (msize + sizeof (struct PeerPutMessage)
1281 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1284 GNUNET_free (targets);
1287 GNUNET_STATISTICS_update (GDS_stats,
1288 gettext_noop ("# PUT messages queued for transmission"),
1292 for (i = 0; i < target_count; i++)
1294 target = targets[i];
1295 if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
1298 GNUNET_STATISTICS_update (GDS_stats,
1299 gettext_noop ("# P2P messages dropped due to full queue"),
1305 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1306 "Routing PUT for %s after %u hops to %s\n",
1308 (unsigned int) hop_count,
1309 GNUNET_i2s (target->id));
1310 env = GNUNET_MQ_msg_extra (ppm,
1312 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1313 ppm->options = htonl (options);
1314 ppm->type = htonl (type);
1315 ppm->hop_count = htonl (hop_count + 1);
1316 ppm->desired_replication_level = htonl (desired_replication_level);
1317 ppm->put_path_length = htonl (put_path_length);
1318 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1319 GNUNET_break (GNUNET_YES ==
1320 GNUNET_CONTAINER_bloomfilter_test (bf,
1322 GNUNET_assert (GNUNET_OK ==
1323 GNUNET_CONTAINER_bloomfilter_get_raw_data (bf,
1327 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1330 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
1331 GNUNET_memcpy (&pp[put_path_length],
1334 GNUNET_MQ_send (target->mq,
1337 GNUNET_free (targets);
1338 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1343 * Perform a GET operation. Forwards the given request to other
1344 * peers. Does not lookup the key locally. May do nothing if this is
1345 * the only peer in the network (or if we are the closest peer in the
1348 * @param type type of the block
1349 * @param options routing options
1350 * @param desired_replication_level desired replication count
1351 * @param hop_count how many hops did this request traverse so far?
1352 * @param key key for the content
1353 * @param xquery extended query
1354 * @param xquery_size number of bytes in @a xquery
1355 * @param reply_bf bloomfilter to filter duplicates
1356 * @param reply_bf_mutator mutator for @a reply_bf
1357 * @param peer_bf filter for peers not to select (again)
1358 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
1361 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1362 enum GNUNET_DHT_RouteOption options,
1363 uint32_t desired_replication_level,
1364 uint32_t hop_count, const struct GNUNET_HashCode * key,
1365 const void *xquery, size_t xquery_size,
1366 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
1367 uint32_t reply_bf_mutator,
1368 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1370 unsigned int target_count;
1372 struct PeerInfo **targets;
1373 struct PeerInfo *target;
1374 struct GNUNET_MQ_Envelope *env;
1376 struct PeerGetMessage *pgm;
1378 size_t reply_bf_size;
1379 unsigned int skip_count;
1381 GNUNET_assert (NULL != peer_bf);
1382 GNUNET_STATISTICS_update (GDS_stats,
1383 gettext_noop ("# GET requests routed"),
1386 target_count = get_target_peers (key,
1389 desired_replication_level,
1391 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1392 "Adding myself (%s) to GET bloomfilter for %s\n",
1393 GNUNET_i2s (&my_identity),
1395 GNUNET_CONTAINER_bloomfilter_add (peer_bf,
1397 if (0 == target_count)
1399 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1400 "Routing GET for %s terminates after %u hops at %s\n",
1402 (unsigned int) hop_count,
1403 GNUNET_i2s (&my_identity));
1406 reply_bf_size = GNUNET_CONTAINER_bloomfilter_get_size (reply_bf);
1407 msize = xquery_size + reply_bf_size;
1408 if (msize + sizeof (struct PeerGetMessage) >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1411 GNUNET_free (targets);
1414 GNUNET_STATISTICS_update (GDS_stats,
1415 gettext_noop ("# GET messages queued for transmission"),
1418 /* forward request */
1420 for (i = 0; i < target_count; i++)
1422 target = targets[i];
1423 if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
1426 GNUNET_STATISTICS_update (GDS_stats,
1427 gettext_noop ("# P2P messages dropped due to full queue"),
1432 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1433 "Routing GET for %s after %u hops to %s\n",
1435 (unsigned int) hop_count,
1436 GNUNET_i2s (target->id));
1437 env = GNUNET_MQ_msg_extra (pgm,
1439 GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
1440 pgm->options = htonl (options);
1441 pgm->type = htonl (type);
1442 pgm->hop_count = htonl (hop_count + 1);
1443 pgm->desired_replication_level = htonl (desired_replication_level);
1444 pgm->xquery_size = htonl (xquery_size);
1445 pgm->bf_mutator = reply_bf_mutator;
1446 GNUNET_break (GNUNET_YES ==
1447 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
1449 GNUNET_assert (GNUNET_OK ==
1450 GNUNET_CONTAINER_bloomfilter_get_raw_data (peer_bf,
1454 xq = (char *) &pgm[1];
1458 if (NULL != reply_bf)
1459 GNUNET_assert (GNUNET_OK ==
1460 GNUNET_CONTAINER_bloomfilter_get_raw_data (reply_bf,
1464 GNUNET_MQ_send (target->mq,
1467 GNUNET_free (targets);
1468 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1473 * Handle a reply (route to origin). Only forwards the reply back to
1474 * the given peer. Does not do local caching or forwarding to local
1477 * @param target neighbour that should receive the block (if still connected)
1478 * @param type type of the block
1479 * @param expiration_time when does the content expire
1480 * @param key key for the content
1481 * @param put_path_length number of entries in @a put_path
1482 * @param put_path peers the original PUT traversed (if tracked)
1483 * @param get_path_length number of entries in @a get_path
1484 * @param get_path peers this reply has traversed so far (if tracked)
1485 * @param data payload of the reply
1486 * @param data_size number of bytes in @a data
1489 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
1490 enum GNUNET_BLOCK_Type type,
1491 struct GNUNET_TIME_Absolute expiration_time,
1492 const struct GNUNET_HashCode *key,
1493 unsigned int put_path_length,
1494 const struct GNUNET_PeerIdentity *put_path,
1495 unsigned int get_path_length,
1496 const struct GNUNET_PeerIdentity *get_path,
1500 struct PeerInfo *pi;
1501 struct GNUNET_MQ_Envelope *env;
1503 struct PeerResultMessage *prm;
1504 struct GNUNET_PeerIdentity *paths;
1506 msize = data_size + (get_path_length + put_path_length) *
1507 sizeof (struct GNUNET_PeerIdentity);
1508 if ((msize + sizeof (struct PeerResultMessage) >= GNUNET_SERVER_MAX_MESSAGE_SIZE) ||
1510 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1512 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1513 (data_size > GNUNET_SERVER_MAX_MESSAGE_SIZE))
1518 pi = GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
1522 /* peer disconnected in the meantime, drop reply */
1523 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1524 "No matching peer for reply for key %s\n",
1528 if (GNUNET_MQ_get_length (pi->mq) >= MAXIMUM_PENDING_PER_PEER)
1531 GNUNET_STATISTICS_update (GDS_stats,
1532 gettext_noop ("# P2P messages dropped due to full queue"),
1535 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1536 "Peer queue full, ignoring reply for key %s\n",
1541 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1542 "Forwarding reply for key %s to peer %s\n",
1544 GNUNET_i2s (target));
1545 GNUNET_STATISTICS_update (GDS_stats,
1547 ("# RESULT messages queued for transmission"), 1,
1549 env = GNUNET_MQ_msg_extra (prm,
1551 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT);
1552 prm->type = htonl (type);
1553 prm->put_path_length = htonl (put_path_length);
1554 prm->get_path_length = htonl (get_path_length);
1555 prm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1557 paths = (struct GNUNET_PeerIdentity *) &prm[1];
1558 GNUNET_memcpy (paths,
1560 put_path_length * sizeof (struct GNUNET_PeerIdentity));
1561 GNUNET_memcpy (&paths[put_path_length],
1563 get_path_length * sizeof (struct GNUNET_PeerIdentity));
1564 GNUNET_memcpy (&paths[put_path_length + get_path_length],
1567 GNUNET_MQ_send (pi->mq,
1573 * To be called on core init/fail.
1575 * @param cls service closure
1576 * @param identity the public identity of this peer
1579 core_init (void *cls,
1580 const struct GNUNET_PeerIdentity *identity)
1582 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1583 "CORE called, I am %s\n",
1584 GNUNET_i2s (identity));
1585 my_identity = *identity;
1586 GNUNET_CRYPTO_hash (identity,
1587 sizeof (struct GNUNET_PeerIdentity),
1589 GNUNET_SERVICE_resume (GDS_service);
1594 * Check validity of a p2p put request.
1596 * @param cls closure with the `struct PeerInfo` of the sender
1597 * @param message message
1598 * @return #GNUNET_OK if the message is valid
1601 check_dht_p2p_put (void *cls,
1602 const struct PeerPutMessage *put)
1607 msize = ntohs (put->header.size);
1608 putlen = ntohl (put->put_path_length);
1610 sizeof (struct PeerPutMessage) +
1611 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
1613 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1615 GNUNET_break_op (0);
1616 return GNUNET_SYSERR;
1623 * Core handler for p2p put requests.
1625 * @param cls closure with the `struct PeerInfo` of the sender
1626 * @param message message
1629 handle_dht_p2p_put (void *cls,
1630 const struct PeerPutMessage *put)
1632 struct PeerInfo *peer = cls;
1633 const struct GNUNET_PeerIdentity *put_path;
1634 const void *payload;
1637 size_t payload_size;
1638 enum GNUNET_DHT_RouteOption options;
1639 struct GNUNET_CONTAINER_BloomFilter *bf;
1640 struct GNUNET_HashCode test_key;
1643 msize = ntohs (put->header.size);
1644 putlen = ntohl (put->put_path_length);
1645 GNUNET_STATISTICS_update (GDS_stats,
1646 gettext_noop ("# P2P PUT requests received"),
1649 GNUNET_STATISTICS_update (GDS_stats,
1650 gettext_noop ("# P2P PUT bytes received"),
1653 put_path = (const struct GNUNET_PeerIdentity *) &put[1];
1654 payload = &put_path[putlen];
1655 options = ntohl (put->options);
1656 payload_size = msize - (sizeof (struct PeerPutMessage) +
1657 putlen * sizeof (struct GNUNET_PeerIdentity));
1659 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1660 "PUT for `%s' from %s\n",
1661 GNUNET_h2s (&put->key),
1662 GNUNET_i2s (peer->id));
1663 if (GNUNET_YES == log_route_details_stderr)
1667 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
1668 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
1669 "R5N PUT %s: %s->%s (%u, %u=>%u)\n",
1670 GNUNET_h2s (&put->key),
1671 GNUNET_i2s (peer->id),
1673 ntohl(put->hop_count),
1674 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
1676 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
1681 switch (GNUNET_BLOCK_get_key
1689 if (0 != memcmp (&test_key,
1691 sizeof (struct GNUNET_HashCode)))
1693 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
1695 GNUNET_break_op (0);
1696 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1697 "PUT with key `%s' for block with key %s\n",
1699 GNUNET_h2s_full (&test_key));
1700 GNUNET_free (put_s);
1705 GNUNET_break_op (0);
1708 /* cannot verify, good luck */
1711 if (ntohl (put->type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
1713 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
1715 GNUNET_BLOCK_EO_NONE,
1717 NULL, 0, /* bloom filer */
1718 NULL, 0, /* xquery */
1719 payload, payload_size))
1721 case GNUNET_BLOCK_EVALUATION_OK_MORE:
1722 case GNUNET_BLOCK_EVALUATION_OK_LAST:
1725 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
1726 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
1727 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
1728 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
1729 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
1730 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
1732 GNUNET_break_op (0);
1737 bf = GNUNET_CONTAINER_bloomfilter_init (put->bloomfilter,
1739 GNUNET_CONSTANTS_BLOOMFILTER_K);
1740 GNUNET_break_op (GNUNET_YES ==
1741 GNUNET_CONTAINER_bloomfilter_test (bf,
1744 struct GNUNET_PeerIdentity pp[putlen + 1];
1746 /* extend 'put path' by sender */
1747 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
1751 putlen * sizeof (struct GNUNET_PeerIdentity));
1752 pp[putlen] = *peer->id;
1758 /* give to local clients */
1759 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (put->expiration_time),
1769 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
1770 (am_closest_peer (&put->key, bf)))
1771 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
1778 /* route to other peers */
1779 forwarded = GDS_NEIGHBOURS_handle_put (ntohl (put->type),
1781 ntohl (put->desired_replication_level),
1782 GNUNET_TIME_absolute_ntoh (put->expiration_time),
1783 ntohl (put->hop_count),
1790 /* notify monitoring clients */
1791 GDS_CLIENTS_process_put (options
1792 | ( (GNUNET_OK == forwarded)
1793 ? GNUNET_DHT_RO_LAST_HOP
1796 ntohl (put->hop_count),
1797 ntohl (put->desired_replication_level),
1799 GNUNET_TIME_absolute_ntoh (put->expiration_time),
1804 GNUNET_CONTAINER_bloomfilter_free (bf);
1809 * We have received a FIND PEER request. Send matching
1812 * @param sender sender of the FIND PEER request
1813 * @param key peers close to this key are desired
1814 * @param bf peers matching this bf are excluded
1815 * @param bf_mutator mutator for bf
1818 handle_find_peer (const struct GNUNET_PeerIdentity *sender,
1819 const struct GNUNET_HashCode *key,
1820 struct GNUNET_CONTAINER_BloomFilter *bf,
1821 uint32_t bf_mutator)
1824 struct PeerBucket *bucket;
1825 struct PeerInfo *peer;
1826 unsigned int choice;
1827 struct GNUNET_HashCode mhash;
1828 const struct GNUNET_HELLO_Message *hello;
1830 /* first, check about our own HELLO */
1831 if (NULL != GDS_my_hello)
1833 GNUNET_BLOCK_mingle_hash (&my_identity_hash,
1837 (GNUNET_YES != GNUNET_CONTAINER_bloomfilter_test (bf, &mhash)))
1841 hello_size = GNUNET_HELLO_size ((const struct GNUNET_HELLO_Message *) GDS_my_hello);
1842 GNUNET_break (hello_size >= sizeof (struct GNUNET_MessageHeader));
1843 GDS_NEIGHBOURS_handle_reply (sender,
1844 GNUNET_BLOCK_TYPE_DHT_HELLO,
1845 GNUNET_TIME_relative_to_absolute
1857 GNUNET_STATISTICS_update (GDS_stats,
1858 gettext_noop ("# FIND PEER requests ignored due to Bloomfilter"),
1865 GNUNET_STATISTICS_update (GDS_stats,
1866 gettext_noop ("# FIND PEER requests ignored due to lack of HELLO"),
1871 /* then, also consider sending a random HELLO from the closest bucket */
1872 if (0 == memcmp (&my_identity_hash,
1874 sizeof (struct GNUNET_HashCode)))
1875 bucket_idx = closest_bucket;
1877 bucket_idx = GNUNET_MIN (closest_bucket,
1879 if (bucket_idx == GNUNET_SYSERR)
1881 bucket = &k_buckets[bucket_idx];
1882 if (bucket->peers_size == 0)
1884 choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1885 bucket->peers_size);
1886 peer = bucket->head;
1889 GNUNET_assert (NULL != peer);
1893 choice = bucket->peers_size;
1898 return; /* no non-masked peer available */
1900 peer = bucket->head;
1901 GNUNET_BLOCK_mingle_hash (&peer->phash,
1904 hello = GDS_HELLO_get (peer->id);
1905 } while ( (hello == NULL) ||
1907 GNUNET_CONTAINER_bloomfilter_test (bf,
1909 GDS_NEIGHBOURS_handle_reply (sender,
1910 GNUNET_BLOCK_TYPE_DHT_HELLO,
1911 GNUNET_TIME_relative_to_absolute
1912 (GNUNET_CONSTANTS_HELLO_ADDRESS_EXPIRATION),
1919 GNUNET_HELLO_size (hello));
1924 * Handle a result from local datacache for a GET operation.
1926 * @param cls the `struct ClientHandle` of the client doing the query
1927 * @param type type of the block
1928 * @param expiration_time when does the content expire
1929 * @param key key for the content
1930 * @param put_path_length number of entries in @a put_path
1931 * @param put_path peers the original PUT traversed (if tracked)
1932 * @param get_path_length number of entries in @a get_path
1933 * @param get_path peers this reply has traversed so far (if tracked)
1934 * @param data payload of the reply
1935 * @param data_size number of bytes in @a data
1938 handle_local_result (void *cls,
1939 enum GNUNET_BLOCK_Type type,
1940 struct GNUNET_TIME_Absolute expiration_time,
1941 const struct GNUNET_HashCode *key,
1942 unsigned int put_path_length,
1943 const struct GNUNET_PeerIdentity *put_path,
1944 unsigned int get_path_length,
1945 const struct GNUNET_PeerIdentity *get_path,
1949 // FIXME: we can probably do better here by
1950 // passing the peer that did the query in the closure...
1951 GDS_ROUTING_process (NULL,
1955 put_path_length, put_path,
1962 * Check validity of p2p get request.
1964 * @param cls closure with the `struct PeerInfo` of the sender
1965 * @param get the message
1966 * @return #GNUNET_OK if the message is well-formed
1969 check_dht_p2p_get (void *cls,
1970 const struct PeerGetMessage *get)
1972 uint32_t xquery_size;
1975 msize = ntohs (get->header.size);
1976 xquery_size = ntohl (get->xquery_size);
1977 if (msize < sizeof (struct PeerGetMessage) + xquery_size)
1979 GNUNET_break_op (0);
1980 return GNUNET_SYSERR;
1987 * Core handler for p2p get requests.
1989 * @param cls closure with the `struct PeerInfo` of the sender
1990 * @param get the message
1993 handle_dht_p2p_get (void *cls,
1994 const struct PeerGetMessage *get)
1996 struct PeerInfo *peer = cls;
1997 uint32_t xquery_size;
1998 size_t reply_bf_size;
2000 enum GNUNET_BLOCK_Type type;
2001 enum GNUNET_DHT_RouteOption options;
2002 enum GNUNET_BLOCK_EvaluationResult eval;
2003 struct GNUNET_CONTAINER_BloomFilter *reply_bf;
2004 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
2013 /* parse and validate message */
2014 msize = ntohs (get->header.size);
2015 xquery_size = ntohl (get->xquery_size);
2016 reply_bf_size = msize - (sizeof (struct PeerGetMessage) + xquery_size);
2017 type = ntohl (get->type);
2018 options = ntohl (get->options);
2019 xquery = (const char *) &get[1];
2021 GNUNET_STATISTICS_update (GDS_stats,
2022 gettext_noop ("# P2P GET requests received"),
2025 GNUNET_STATISTICS_update (GDS_stats,
2026 gettext_noop ("# P2P GET bytes received"),
2029 if (GNUNET_YES == log_route_details_stderr)
2033 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
2034 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
2035 "R5N GET %s: %s->%s (%u, %u=>%u) xq: %.*s\n",
2036 GNUNET_h2s (&get->key),
2037 GNUNET_i2s (peer->id),
2039 ntohl(get->hop_count),
2040 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
2042 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
2044 ntohl(get->xquery_size),
2049 if (reply_bf_size > 0)
2051 GNUNET_CONTAINER_bloomfilter_init (&xquery[xquery_size],
2053 GNUNET_CONSTANTS_BLOOMFILTER_K);
2055 GNUNET_BLOCK_evaluate (GDS_block_context,
2057 GNUNET_BLOCK_EO_NONE,
2065 if (eval != GNUNET_BLOCK_EVALUATION_REQUEST_VALID)
2067 /* request invalid or block type not supported */
2068 GNUNET_break_op (eval == GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED);
2069 if (NULL != reply_bf)
2070 GNUNET_CONTAINER_bloomfilter_free (reply_bf);
2073 peer_bf = GNUNET_CONTAINER_bloomfilter_init (get->bloomfilter,
2075 GNUNET_CONSTANTS_BLOOMFILTER_K);
2076 GNUNET_break_op (GNUNET_YES ==
2077 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
2079 /* remember request for routing replies */
2080 GDS_ROUTING_add (peer->id,
2088 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2089 "GET for %s at %s after %u hops\n",
2090 GNUNET_h2s (&get->key),
2091 GNUNET_i2s (&my_identity),
2092 (unsigned int) ntohl (get->hop_count));
2093 /* local lookup (this may update the reply_bf) */
2094 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
2095 (am_closest_peer (&get->key,
2098 if ((0 != (options & GNUNET_DHT_RO_FIND_PEER)))
2100 GNUNET_STATISTICS_update (GDS_stats,
2101 gettext_noop ("# P2P FIND PEER requests processed"),
2104 handle_find_peer (peer->id,
2111 eval = GDS_DATACACHE_handle_get (&get->key,
2117 &handle_local_result,
2123 GNUNET_STATISTICS_update (GDS_stats,
2124 gettext_noop ("# P2P GET requests ONLY routed"),
2129 /* P2P forwarding */
2130 forwarded = GNUNET_NO;
2131 if (eval != GNUNET_BLOCK_EVALUATION_OK_LAST)
2132 forwarded = GDS_NEIGHBOURS_handle_get (type,
2134 ntohl (get->desired_replication_level),
2135 ntohl (get->hop_count),
2142 GDS_CLIENTS_process_get (options
2143 | (GNUNET_OK == forwarded)
2144 ? GNUNET_DHT_RO_LAST_HOP : 0,
2146 ntohl (get->hop_count),
2147 ntohl (get->desired_replication_level),
2154 if (NULL != reply_bf)
2155 GNUNET_CONTAINER_bloomfilter_free (reply_bf);
2156 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
2161 * Check validity of p2p result message.
2163 * @param cls closure
2164 * @param message message
2165 * @return #GNUNET_YES if the message is well-formed
2168 check_dht_p2p_result (void *cls,
2169 const struct PeerResultMessage *prm)
2171 uint32_t get_path_length;
2172 uint32_t put_path_length;
2175 msize = ntohs (prm->header.size);
2176 put_path_length = ntohl (prm->put_path_length);
2177 get_path_length = ntohl (prm->get_path_length);
2179 sizeof (struct PeerResultMessage) + (get_path_length +
2181 sizeof (struct GNUNET_PeerIdentity)) ||
2183 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
2185 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2187 GNUNET_break_op (0);
2188 return GNUNET_SYSERR;
2195 * Core handler for p2p result messages.
2197 * @param cls closure
2198 * @param message message
2201 handle_dht_p2p_result (void *cls,
2202 const struct PeerResultMessage *prm)
2204 struct PeerInfo *peer = cls;
2205 const struct GNUNET_PeerIdentity *put_path;
2206 const struct GNUNET_PeerIdentity *get_path;
2208 uint32_t get_path_length;
2209 uint32_t put_path_length;
2212 enum GNUNET_BLOCK_Type type;
2214 /* parse and validate message */
2215 msize = ntohs (prm->header.size);
2216 put_path_length = ntohl (prm->put_path_length);
2217 get_path_length = ntohl (prm->get_path_length);
2218 put_path = (const struct GNUNET_PeerIdentity *) &prm[1];
2219 get_path = &put_path[put_path_length];
2220 type = ntohl (prm->type);
2221 data = (const void *) &get_path[get_path_length];
2222 data_size = msize - (sizeof (struct PeerResultMessage) +
2224 put_path_length) * sizeof (struct GNUNET_PeerIdentity));
2225 GNUNET_STATISTICS_update (GDS_stats,
2226 gettext_noop ("# P2P RESULTS received"),
2229 GNUNET_STATISTICS_update (GDS_stats,
2230 gettext_noop ("# P2P RESULT bytes received"),
2233 if (GNUNET_YES == log_route_details_stderr)
2237 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
2238 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
2239 "R5N RESULT %s: %s->%s (%u)\n",
2240 GNUNET_h2s (&prm->key),
2241 GNUNET_i2s (peer->id),
2243 get_path_length + 1);
2246 /* if we got a HELLO, consider it for our own routing table */
2247 if (GNUNET_BLOCK_TYPE_DHT_HELLO == type)
2249 const struct GNUNET_MessageHeader *h;
2250 struct GNUNET_PeerIdentity pid;
2252 /* Should be a HELLO, validate and consider using it! */
2253 if (data_size < sizeof (struct GNUNET_HELLO_Message))
2255 GNUNET_break_op (0);
2259 if (data_size != ntohs (h->size))
2261 GNUNET_break_op (0);
2265 GNUNET_HELLO_get_id ((const struct GNUNET_HELLO_Message *) h,
2268 GNUNET_break_op (0);
2271 if ( (GNUNET_YES != disable_try_connect) &&
2272 (0 != memcmp (&my_identity,
2274 sizeof (struct GNUNET_PeerIdentity))) )
2279 /* append 'peer' to 'get_path' */
2281 struct GNUNET_PeerIdentity xget_path[get_path_length + 1];
2283 GNUNET_memcpy (xget_path,
2285 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2286 xget_path[get_path_length] = *peer->id;
2289 /* forward to local clients */
2290 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2299 GDS_CLIENTS_process_get_resp (type,
2302 put_path, put_path_length,
2303 GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2307 if (GNUNET_YES == cache_results)
2309 struct GNUNET_PeerIdentity xput_path[get_path_length + 1 + put_path_length];
2311 GNUNET_memcpy (xput_path,
2313 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2314 GNUNET_memcpy (&xput_path[put_path_length],
2316 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2318 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2320 get_path_length + put_path_length,
2326 /* forward to other peers */
2327 GDS_ROUTING_process (NULL,
2329 GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2342 * Initialize neighbours subsystem.
2344 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2347 GDS_NEIGHBOURS_init ()
2349 struct GNUNET_MQ_MessageHandler core_handlers[] = {
2350 GNUNET_MQ_hd_var_size (dht_p2p_get,
2351 GNUNET_MESSAGE_TYPE_DHT_P2P_GET,
2352 struct PeerGetMessage,
2354 GNUNET_MQ_hd_var_size (dht_p2p_put,
2355 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT,
2356 struct PeerPutMessage,
2358 GNUNET_MQ_hd_var_size (dht_p2p_result,
2359 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT,
2360 struct PeerResultMessage,
2362 GNUNET_MQ_handler_end ()
2364 unsigned long long temp_config_num;
2367 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2369 "DISABLE_TRY_CONNECT");
2371 GNUNET_CONFIGURATION_get_value_number (GDS_cfg,
2375 bucket_size = (unsigned int) temp_config_num;
2377 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2381 log_route_details_stderr =
2382 (NULL != getenv("GNUNET_DHT_ROUTE_DEBUG")) ? GNUNET_YES : GNUNET_NO;
2383 ats_ch = GNUNET_ATS_connectivity_init (GDS_cfg);
2384 core_api = GNUNET_CORE_connect (GDS_cfg,
2387 &handle_core_connect,
2388 &handle_core_disconnect,
2390 if (NULL == core_api)
2391 return GNUNET_SYSERR;
2392 all_connected_peers = GNUNET_CONTAINER_multipeermap_create (256,
2394 all_desired_peers = GNUNET_CONTAINER_multipeermap_create (256,
2401 * Shutdown neighbours subsystem.
2404 GDS_NEIGHBOURS_done ()
2406 if (NULL == core_api)
2408 GNUNET_CORE_disconnect (core_api);
2411 GNUNET_CONTAINER_multipeermap_size (all_connected_peers));
2412 GNUNET_CONTAINER_multipeermap_destroy (all_connected_peers);
2413 all_connected_peers = NULL;
2414 GNUNET_CONTAINER_multipeermap_iterate (all_desired_peers,
2417 GNUNET_CONTAINER_multipeermap_destroy (all_desired_peers);
2418 all_desired_peers = NULL;
2419 GNUNET_ATS_connectivity_done (ats_ch);
2421 GNUNET_assert (NULL == find_peer_task);
2426 * Get the ID of the local node.
2428 * @return identity of the local node
2430 struct GNUNET_PeerIdentity *
2431 GDS_NEIGHBOURS_get_id ()
2433 return &my_identity;
2437 /* end of gnunet-service-dht_neighbours.c */