diff options
Diffstat (limited to 'src/dht/gnunet-service-dht_neighbours.c')
-rw-r--r-- | src/dht/gnunet-service-dht_neighbours.c | 104 |
1 files changed, 40 insertions, 64 deletions
diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c index 88b0c5d92..2c30f0b68 100644 --- a/src/dht/gnunet-service-dht_neighbours.c +++ b/src/dht/gnunet-service-dht_neighbours.c | |||
@@ -1,6 +1,6 @@ | |||
1 | /* | 1 | /* |
2 | This file is part of GNUnet. | 2 | This file is part of GNUnet. |
3 | Copyright (C) 2009-2017 GNUnet e.V. | 3 | Copyright (C) 2009-2017, 2021 GNUnet e.V. |
4 | 4 | ||
5 | GNUnet is free software: you can redistribute it and/or modify it | 5 | GNUnet is free software: you can redistribute it and/or modify it |
6 | under the terms of the GNU Affero General Public License as published | 6 | under the terms of the GNU Affero General Public License as published |
@@ -877,63 +877,36 @@ get_forward_count (uint32_t hop_count, | |||
877 | 877 | ||
878 | 878 | ||
879 | /** | 879 | /** |
880 | * Compute the distance between have and target as a 32-bit value. | 880 | * Compute the distance between have and target as a 64-bit value. |
881 | * Differences in the lower bits must count stronger than differences | 881 | * Differences in the lower bits must count stronger than differences |
882 | * in the higher bits. | 882 | * in the higher bits. |
883 | * | 883 | * |
884 | * @param target | 884 | * @param target |
885 | * @param have | 885 | * @param have |
886 | * @param bucket up to which offset are @a target and @a have identical and thus those bits should not be considered | ||
886 | * @return 0 if have==target, otherwise a number | 887 | * @return 0 if have==target, otherwise a number |
887 | * that is larger as the distance between | 888 | * that is larger as the distance between |
888 | * the two hash codes increases | 889 | * the two hash codes increases |
889 | */ | 890 | */ |
890 | static unsigned int | 891 | static uint64_t |
891 | get_distance (const struct GNUNET_HashCode *target, | 892 | get_distance (const struct GNUNET_HashCode *target, |
892 | const struct GNUNET_HashCode *have) | 893 | const struct GNUNET_HashCode *have, |
894 | unsigned int bucket) | ||
893 | { | 895 | { |
894 | unsigned int bucket; | 896 | uint64_t lsb = 0; |
895 | unsigned int msb; | 897 | |
896 | unsigned int lsb; | 898 | for (unsigned int i = bucket + 1; |
897 | unsigned int i; | 899 | (i < sizeof(struct GNUNET_HashCode) * 8) && |
898 | 900 | (i < bucket + 1 + 64); | |
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. | ||
904 | * | ||
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) *//* first, calculate the most significant 9 bits of our | ||
911 | * result, aka the number of LSBs */bucket = GNUNET_CRYPTO_hash_matching_bits (target, | ||
912 | have); | ||
913 | /* bucket is now a value between 0 and 512 */ | ||
914 | if (bucket == 512) | ||
915 | return 0; /* perfect match */ | ||
916 | if (bucket == 0) | ||
917 | return (unsigned int) -1; /* LSB differs; use max (if we did the bit-shifting | ||
918 | * below, we'd end up with max+1 (overflow)) */ | ||
919 | |||
920 | /* calculate the most significant bits of the final result */ | ||
921 | msb = (512 - bucket) << (32 - 9); | ||
922 | /* calculate the 32-9 least significant bits of the final result by | ||
923 | * looking at the differences in the 32-9 bits following the | ||
924 | * mismatching bit at 'bucket' */ | ||
925 | lsb = 0; | ||
926 | for (i = bucket + 1; | ||
927 | (i < sizeof(struct GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9); | ||
928 | i++) | 901 | i++) |
929 | { | 902 | { |
930 | if (GNUNET_CRYPTO_hash_get_bit_rtl (target, i) != | 903 | if (GNUNET_CRYPTO_hash_get_bit_rtl (target, i) != |
931 | GNUNET_CRYPTO_hash_get_bit_rtl (have, i)) | 904 | GNUNET_CRYPTO_hash_get_bit_rtl (have, i)) |
932 | lsb |= (1 << (bucket + 32 - 9 - i)); /* first bit set will be 10, | 905 | lsb |= (1LLU << (bucket + 64 - i)); /* first bit set will be 1, |
933 | * last bit set will be 31 -- if | 906 | * last bit set will be 63 -- if |
934 | * i does not reach 512 first... */ | 907 | * i does not reach 512 first... */ |
935 | } | 908 | } |
936 | return msb | lsb; | 909 | return lsb; |
937 | } | 910 | } |
938 | 911 | ||
939 | 912 | ||
@@ -1013,33 +986,42 @@ select_peer (const struct GNUNET_HashCode *key, | |||
1013 | unsigned int count; | 986 | unsigned int count; |
1014 | unsigned int selected; | 987 | unsigned int selected; |
1015 | struct PeerInfo *pos; | 988 | struct PeerInfo *pos; |
1016 | unsigned int dist; | ||
1017 | unsigned int smallest_distance; | ||
1018 | struct PeerInfo *chosen; | 989 | struct PeerInfo *chosen; |
1019 | 990 | ||
1020 | if (hops >= GDS_NSE_get ()) | 991 | if (hops >= GDS_NSE_get ()) |
1021 | { | 992 | { |
1022 | /* greedy selection (closest peer that is not in bloomfilter) */ | 993 | /* greedy selection (closest peer that is not in bloomfilter) */ |
1023 | smallest_distance = UINT_MAX; | 994 | unsigned int best_bucket = 0; |
995 | uint64_t best_in_bucket = UINT64_MAX; | ||
996 | |||
1024 | chosen = NULL; | 997 | chosen = NULL; |
1025 | for (bc = 0; bc <= closest_bucket; bc++) | 998 | for (bc = 0; bc <= closest_bucket; bc++) |
1026 | { | 999 | { |
1027 | pos = k_buckets[bc].head; | 1000 | pos = k_buckets[bc].head; |
1028 | count = 0; | 1001 | count = 0; |
1029 | while ((pos != NULL) && (count < bucket_size)) | 1002 | while ( (pos != NULL) && |
1003 | (count < bucket_size) ) | ||
1030 | { | 1004 | { |
1031 | if ((NULL == bloom) || | 1005 | unsigned int bucket; |
1032 | (GNUNET_NO == | 1006 | uint64_t dist; |
1033 | GNUNET_CONTAINER_bloomfilter_test (bloom, | 1007 | |
1034 | &pos->phash))) | 1008 | bucket = GNUNET_CRYPTO_hash_matching_bits (key, |
1009 | &pos->phash); | ||
1010 | dist = get_distance (key, | ||
1011 | &pos->phash, | ||
1012 | bucket); | ||
1013 | if (bucket < best_bucket) | ||
1014 | continue; | ||
1015 | if (dist > best_in_bucket) | ||
1016 | continue; | ||
1017 | best_bucket = bucket; | ||
1018 | best_in_bucket = dist; | ||
1019 | if ( (NULL == bloom) || | ||
1020 | (GNUNET_NO == | ||
1021 | GNUNET_CONTAINER_bloomfilter_test (bloom, | ||
1022 | &pos->phash)) ) | ||
1035 | { | 1023 | { |
1036 | dist = get_distance (key, | 1024 | chosen = pos; |
1037 | &pos->phash); | ||
1038 | if (dist < smallest_distance) | ||
1039 | { | ||
1040 | chosen = pos; | ||
1041 | smallest_distance = dist; | ||
1042 | } | ||
1043 | } | 1025 | } |
1044 | else | 1026 | else |
1045 | { | 1027 | { |
@@ -1052,13 +1034,7 @@ select_peer (const struct GNUNET_HashCode *key, | |||
1052 | "# Peers excluded from routing due to Bloomfilter"), | 1034 | "# Peers excluded from routing due to Bloomfilter"), |
1053 | 1, | 1035 | 1, |
1054 | GNUNET_NO); | 1036 | GNUNET_NO); |
1055 | dist = get_distance (key, | 1037 | chosen = NULL; |
1056 | &pos->phash); | ||
1057 | if (dist < smallest_distance) | ||
1058 | { | ||
1059 | chosen = NULL; | ||
1060 | smallest_distance = dist; | ||
1061 | } | ||
1062 | } | 1038 | } |
1063 | count++; | 1039 | count++; |
1064 | pos = pos->next; | 1040 | pos = pos->next; |