diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/dht/gnunet-service-dht_neighbours.c | 73 |
1 files changed, 45 insertions, 28 deletions
diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c index eb64d6202..01a68b0b7 100644 --- a/src/dht/gnunet-service-dht_neighbours.c +++ b/src/dht/gnunet-service-dht_neighbours.c | |||
@@ -915,27 +915,46 @@ enum GNUNET_GenericReturnValue | |||
915 | GDS_am_closest_peer (const struct GNUNET_HashCode *key, | 915 | GDS_am_closest_peer (const struct GNUNET_HashCode *key, |
916 | const struct GNUNET_CONTAINER_BloomFilter *bloom) | 916 | const struct GNUNET_CONTAINER_BloomFilter *bloom) |
917 | { | 917 | { |
918 | int bucket_num; | ||
919 | |||
920 | if (0 == GNUNET_memcmp (&my_identity_hash, | 918 | if (0 == GNUNET_memcmp (&my_identity_hash, |
921 | key)) | 919 | key)) |
922 | return GNUNET_YES; | 920 | return GNUNET_YES; |
923 | bucket_num = find_bucket (key); | 921 | for (int bucket_num = find_bucket (key); |
924 | GNUNET_assert (bucket_num >= 0); | 922 | bucket_num < closest_bucket; |
925 | for (struct PeerInfo *pos = k_buckets[bucket_num].head; | 923 | bucket_num++) |
926 | NULL != pos; | ||
927 | pos = pos->next) | ||
928 | { | 924 | { |
929 | if ( (NULL != bloom) && | 925 | unsigned int count = 0; |
930 | (GNUNET_YES == | 926 | |
931 | GNUNET_CONTAINER_bloomfilter_test (bloom, | 927 | GNUNET_assert (bucket_num >= 0); |
932 | &pos->phash)) ) | 928 | for (struct PeerInfo *pos = k_buckets[bucket_num].head; |
933 | continue; /* Ignore filtered peers */ | 929 | NULL != pos; |
934 | /* All peers in this bucket must be closer than us, as | 930 | pos = pos->next) |
935 | they mismatch with our PID on the pivotal bit. So | 931 | { |
936 | because an unfiltered peer exists, we are not the | 932 | if (count >= bucket_size) |
937 | closest. */ | 933 | break; /* we only consider first #bucket_size entries per bucket */ |
938 | return GNUNET_NO; | 934 | count++; |
935 | if ( (NULL != bloom) && | ||
936 | (GNUNET_YES == | ||
937 | GNUNET_CONTAINER_bloomfilter_test (bloom, | ||
938 | &pos->phash)) ) | ||
939 | continue; /* Ignore filtered peers */ | ||
940 | /* All peers in this bucket must be closer than us, as | ||
941 | they mismatch with our PID on the pivotal bit. So | ||
942 | because an unfiltered peer exists, we are not the | ||
943 | closest. */ | ||
944 | int delta = GNUNET_CRYPTO_hash_xorcmp (&pos->phash, | ||
945 | &my_identity_hash, | ||
946 | key); | ||
947 | switch (delta) | ||
948 | { | ||
949 | case -1: /* pos closer */ | ||
950 | return GNUNET_NO; | ||
951 | case 0: /* identical, impossible! */ | ||
952 | GNUNET_assert (0); | ||
953 | break; | ||
954 | case 1: /* I am closer */ | ||
955 | break; | ||
956 | } | ||
957 | } | ||
939 | } | 958 | } |
940 | /* No closer (unfiltered) peers found; we must be the closest! */ | 959 | /* No closer (unfiltered) peers found; we must be the closest! */ |
941 | return GNUNET_YES; | 960 | return GNUNET_YES; |
@@ -1041,12 +1060,14 @@ select_peer (const struct GNUNET_HashCode *key, | |||
1041 | } | 1060 | } |
1042 | count++; | 1061 | count++; |
1043 | } /* for all (#bucket_size) peers in bucket */ | 1062 | } /* for all (#bucket_size) peers in bucket */ |
1044 | 1063 | if (NULL != chosen) | |
1045 | /* If we chose nothing in first iteration, first go through | 1064 | break; |
1046 | all (!) deeper buckets (best chance to find a good match), | 1065 | |
1047 | and if we still found nothing, then to shallower buckets | 1066 | /* If we chose nothing in first iteration, first go through deeper |
1048 | (but here terminate on any match, as it can only get worse | 1067 | buckets (best chance to find a good match), and if we still found |
1049 | as we keep going). */ | 1068 | nothing, then to shallower buckets. Terminate on any match in the |
1069 | current bucket, as this search order guarantees that it can only get | ||
1070 | worse as we keep going. */ | ||
1050 | if (bucket_offset > best_bucket) | 1071 | if (bucket_offset > best_bucket) |
1051 | { | 1072 | { |
1052 | /* Go through more deeper buckets */ | 1073 | /* Go through more deeper buckets */ |
@@ -1055,17 +1076,13 @@ select_peer (const struct GNUNET_HashCode *key, | |||
1055 | { | 1076 | { |
1056 | /* Can't go any deeper, if nothing selected, | 1077 | /* Can't go any deeper, if nothing selected, |
1057 | go for shallower buckets */ | 1078 | go for shallower buckets */ |
1058 | if (NULL != chosen) | ||
1059 | break; | ||
1060 | bucket_offset = best_bucket - 1; | 1079 | bucket_offset = best_bucket - 1; |
1061 | } | 1080 | } |
1062 | } | 1081 | } |
1063 | else | 1082 | else |
1064 | { | 1083 | { |
1065 | /* We're either at the 'best_bucket' or already moving | 1084 | /* We're either at the 'best_bucket' or already moving |
1066 | on to shallower buckets; any selection means the end. */ | 1085 | on to shallower buckets. */ |
1067 | if (NULL != chosen) | ||
1068 | break; | ||
1069 | if (bucket_offset == best_bucket) | 1086 | if (bucket_offset == best_bucket) |
1070 | bucket_offset++; /* go for deeper buckets */ | 1087 | bucket_offset++; /* go for deeper buckets */ |
1071 | else | 1088 | else |