diff options
author | Christian Grothoff <christian@grothoff.org> | 2022-01-02 23:55:18 +0100 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2022-01-02 23:55:18 +0100 |
commit | f30d3de6fb8bbd01072df00815b5f18a1808312e (patch) | |
tree | 1932f5174084f5df09cf1c95f599d15266022736 | |
parent | 7b6ad5eedc4444ed8739932a388189bfd4e35e44 (diff) | |
download | gnunet-f30d3de6fb8bbd01072df00815b5f18a1808312e.tar.gz gnunet-f30d3de6fb8bbd01072df00815b5f18a1808312e.zip |
-DHT: clean up peer selection logic
-rw-r--r-- | src/dht/gnunet-service-dht_neighbours.c | 335 | ||||
-rw-r--r-- | src/include/gnunet_crypto_lib.h | 15 | ||||
-rw-r--r-- | src/util/crypto_hash.c | 54 | ||||
-rw-r--r-- | src/util/test_crypto_hash.c | 70 |
4 files changed, 207 insertions, 267 deletions
diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c index 6b1b73103..eb64d6202 100644 --- a/src/dht/gnunet-service-dht_neighbours.c +++ b/src/dht/gnunet-service-dht_neighbours.c | |||
@@ -944,18 +944,22 @@ GDS_am_closest_peer (const struct GNUNET_HashCode *key, | |||
944 | 944 | ||
945 | /** | 945 | /** |
946 | * Select a peer from the routing table that would be a good routing | 946 | * Select a peer from the routing table that would be a good routing |
947 | * destination for sending a message for "key". The resulting peer | 947 | * destination for sending a message for @a key. The resulting peer |
948 | * must not be in the set of blocked peers.<p> | 948 | * must not be in the set of @a bloom blocked peers. |
949 | * | 949 | * |
950 | * Note that we should not ALWAYS select the closest peer to the | 950 | * Note that we should not ALWAYS select the closest peer to the |
951 | * target, peers further away from the target should be chosen with | 951 | * target, we do a "random" peer selection if the number of @a hops |
952 | * exponentially declining probability. | 952 | * is below the logarithm of the network size estimate. |
953 | * | ||
954 | * FIXME: double-check that this is fine | ||
955 | * | 953 | * |
954 | * In all cases, we only consider at most the first #bucket_size peers of any | ||
955 | * #k_buckets. The other peers in the bucket are there because GNUnet doesn't | ||
956 | * really allow the DHT to "reject" connections, but we only use the first | ||
957 | * #bucket_size, even if more exist. (The idea is to ensure that those | ||
958 | * connections are frequently used, and for others to be not used by the DHT, | ||
959 | * and thus possibly dropped by transport due to disuse). | ||
956 | * | 960 | * |
957 | * @param key the key we are selecting a peer to route to | 961 | * @param key the key we are selecting a peer to route to |
958 | * @param bloom a bloomfilter containing entries this request has seen already | 962 | * @param bloom a Bloom filter containing entries this request has seen already |
959 | * @param hops how many hops has this message traversed thus far | 963 | * @param hops how many hops has this message traversed thus far |
960 | * @return Peer to route to, or NULL on error | 964 | * @return Peer to route to, or NULL on error |
961 | */ | 965 | */ |
@@ -964,141 +968,196 @@ select_peer (const struct GNUNET_HashCode *key, | |||
964 | const struct GNUNET_CONTAINER_BloomFilter *bloom, | 968 | const struct GNUNET_CONTAINER_BloomFilter *bloom, |
965 | uint32_t hops) | 969 | uint32_t hops) |
966 | { | 970 | { |
967 | unsigned int bc; | 971 | if (0 == closest_bucket) |
968 | unsigned int count; | 972 | { |
969 | unsigned int selected; | 973 | GNUNET_STATISTICS_update (GDS_stats, |
970 | struct PeerInfo *pos; | 974 | "# Peer selection failed", |
971 | struct PeerInfo *chosen; | 975 | 1, |
972 | 976 | GNUNET_NO); | |
977 | return NULL; /* we have zero connections */ | ||
978 | } | ||
973 | if (hops >= GDS_NSE_get ()) | 979 | if (hops >= GDS_NSE_get ()) |
974 | { | 980 | { |
975 | /* greedy selection (closest peer that is not in bloomfilter) */ | 981 | /* greedy selection (closest peer that is not in Bloom filter) */ |
976 | unsigned int best_bucket = 0; | 982 | struct PeerInfo *chosen = NULL; |
977 | uint64_t best_in_bucket = UINT64_MAX; | 983 | int best_bucket; |
984 | int bucket_offset; | ||
978 | 985 | ||
979 | chosen = NULL; | ||
980 | for (bc = 0; bc < closest_bucket; bc++) | ||
981 | { | 986 | { |
982 | count = 0; | 987 | struct GNUNET_HashCode xor; |
983 | for (pos = k_buckets[bc].head; | 988 | |
984 | (pos != NULL) && | 989 | GNUNET_CRYPTO_hash_xor (key, |
985 | (count < bucket_size); | 990 | &my_identity_hash, |
991 | &xor); | ||
992 | best_bucket = GNUNET_CRYPTO_hash_count_leading_zeros (&xor); | ||
993 | } | ||
994 | if (best_bucket >= closest_bucket) | ||
995 | bucket_offset = closest_bucket - 1; | ||
996 | else | ||
997 | bucket_offset = best_bucket; | ||
998 | while (-1 != bucket_offset) | ||
999 | { | ||
1000 | struct PeerBucket *bucket = &k_buckets[bucket_offset]; | ||
1001 | unsigned int count = 0; | ||
1002 | |||
1003 | for (struct PeerInfo *pos = bucket->head; | ||
1004 | NULL != pos; | ||
986 | pos = pos->next) | 1005 | pos = pos->next) |
987 | { | 1006 | { |
988 | struct GNUNET_HashCode xor; | 1007 | if (count >= bucket_size) |
989 | unsigned int bucket; | 1008 | break; /* we only consider first #bucket_size entries per bucket */ |
990 | uint64_t dist; | 1009 | count++; |
991 | 1010 | if (GNUNET_YES == | |
992 | GNUNET_CRYPTO_hash_xor (key, | 1011 | GNUNET_CONTAINER_bloomfilter_test (bloom, |
993 | &pos->phash, | 1012 | &pos->phash)) |
994 | &xor); | 1013 | { |
995 | bucket = GNUNET_CRYPTO_hash_count_leading_zeros (&xor); | 1014 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, |
996 | dist = GNUNET_CRYPTO_hash_bucket_distance (&xor, | 1015 | "Excluded peer `%s' due to BF match in greedy routing for %s\n", |
997 | bucket); | 1016 | GNUNET_i2s (pos->id), |
998 | if (bucket < best_bucket) | 1017 | GNUNET_h2s (key)); |
999 | continue; | ||
1000 | if (dist > best_in_bucket) | ||
1001 | continue; | 1018 | continue; |
1002 | best_bucket = bucket; | 1019 | } |
1003 | best_in_bucket = dist; | 1020 | if (NULL == chosen) |
1004 | if ( (NULL == bloom) || | ||
1005 | (GNUNET_NO == | ||
1006 | GNUNET_CONTAINER_bloomfilter_test (bloom, | ||
1007 | &pos->phash)) ) | ||
1008 | { | 1021 | { |
1022 | /* First candidate */ | ||
1009 | chosen = pos; | 1023 | chosen = pos; |
1010 | } | 1024 | } |
1011 | else | 1025 | else |
1012 | { | 1026 | { |
1013 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 1027 | int delta = GNUNET_CRYPTO_hash_xorcmp (&pos->phash, |
1014 | "Excluded peer `%s' due to BF match in greedy routing for %s\n", | 1028 | &chosen->phash, |
1015 | GNUNET_i2s (pos->id), | 1029 | key); |
1016 | GNUNET_h2s (key)); | 1030 | switch (delta) |
1017 | GNUNET_STATISTICS_update (GDS_stats, | 1031 | { |
1018 | gettext_noop ( | 1032 | case -1: /* pos closer */ |
1019 | "# Peers excluded from routing due to Bloomfilter"), | 1033 | chosen = pos; |
1020 | 1, | 1034 | break; |
1021 | GNUNET_NO); | 1035 | case 0: /* identical, impossible! */ |
1022 | chosen = NULL; | 1036 | GNUNET_assert (0); |
1037 | break; | ||
1038 | case 1: /* chosen closer */ | ||
1039 | break; | ||
1040 | } | ||
1023 | } | 1041 | } |
1024 | count++; | 1042 | count++; |
1043 | } /* for all (#bucket_size) peers in bucket */ | ||
1044 | |||
1045 | /* If we chose nothing in first iteration, first go through | ||
1046 | all (!) deeper buckets (best chance to find a good match), | ||
1047 | and if we still found nothing, then to shallower buckets | ||
1048 | (but here terminate on any match, as it can only get worse | ||
1049 | as we keep going). */ | ||
1050 | if (bucket_offset > best_bucket) | ||
1051 | { | ||
1052 | /* Go through more deeper buckets */ | ||
1053 | bucket_offset++; | ||
1054 | if (bucket_offset == closest_bucket) | ||
1055 | { | ||
1056 | /* Can't go any deeper, if nothing selected, | ||
1057 | go for shallower buckets */ | ||
1058 | if (NULL != chosen) | ||
1059 | break; | ||
1060 | bucket_offset = best_bucket - 1; | ||
1061 | } | ||
1025 | } | 1062 | } |
1026 | } | 1063 | else |
1064 | { | ||
1065 | /* We're either at the 'best_bucket' or already moving | ||
1066 | on to shallower buckets; any selection means the end. */ | ||
1067 | if (NULL != chosen) | ||
1068 | break; | ||
1069 | if (bucket_offset == best_bucket) | ||
1070 | bucket_offset++; /* go for deeper buckets */ | ||
1071 | else | ||
1072 | bucket_offset--; /* go for shallower buckets */ | ||
1073 | } | ||
1074 | } /* for applicable buckets (starting at best match) */ | ||
1027 | if (NULL == chosen) | 1075 | if (NULL == chosen) |
1076 | { | ||
1028 | GNUNET_STATISTICS_update (GDS_stats, | 1077 | GNUNET_STATISTICS_update (GDS_stats, |
1029 | gettext_noop ("# Peer selection failed"), | 1078 | "# Peer selection failed", |
1030 | 1, | 1079 | 1, |
1031 | GNUNET_NO); | 1080 | GNUNET_NO); |
1032 | else | 1081 | return NULL; |
1033 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 1082 | } |
1034 | "Selected peer `%s' in greedy routing for %s\n", | 1083 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, |
1035 | GNUNET_i2s (chosen->id), | 1084 | "Selected peer `%s' in greedy routing for %s\n", |
1036 | GNUNET_h2s (key)); | 1085 | GNUNET_i2s (chosen->id), |
1086 | GNUNET_h2s (key)); | ||
1037 | return chosen; | 1087 | return chosen; |
1038 | } | 1088 | } /* end of 'greedy' peer selection */ |
1039 | 1089 | ||
1040 | /* select "random" peer */ | 1090 | /* select "random" peer */ |
1041 | /* count number of peers that are available and not filtered */ | 1091 | /* count number of peers that are available and not filtered, |
1042 | count = 0; | 1092 | but limit to at most #bucket_size peers, starting with |
1043 | for (bc = 0; bc < closest_bucket; bc++) | 1093 | those 'furthest' from us. */ |
1044 | { | 1094 | { |
1045 | pos = k_buckets[bc].head; | 1095 | unsigned int total = 0; |
1046 | while ((NULL != pos) && (count < bucket_size)) | 1096 | unsigned int selected; |
1097 | |||
1098 | for (unsigned int bc = 0; bc < closest_bucket; bc++) | ||
1047 | { | 1099 | { |
1048 | if ((NULL != bloom) && | 1100 | unsigned int count = 0; |
1049 | (GNUNET_YES == | 1101 | |
1050 | GNUNET_CONTAINER_bloomfilter_test (bloom, | 1102 | for (struct PeerInfo *pos = k_buckets[bc].head; |
1051 | &pos->phash))) | 1103 | NULL != pos; |
1104 | pos = pos->next) | ||
1052 | { | 1105 | { |
1053 | GNUNET_STATISTICS_update (GDS_stats, | 1106 | count++; |
1054 | gettext_noop | 1107 | if (count > bucket_size) |
1055 | ( | 1108 | break; /* limits search to #bucket_size peers per bucket */ |
1056 | "# Peers excluded from routing due to Bloomfilter"), | 1109 | if (GNUNET_YES == |
1057 | 1, GNUNET_NO); | 1110 | GNUNET_CONTAINER_bloomfilter_test (bloom, |
1058 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 1111 | &pos->phash)) |
1059 | "Excluded peer `%s' due to BF match in random routing for %s\n", | 1112 | { |
1060 | GNUNET_i2s (pos->id), | 1113 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, |
1061 | GNUNET_h2s (key)); | 1114 | "Excluded peer `%s' due to BF match in random routing for %s\n", |
1062 | pos = pos->next; | 1115 | GNUNET_i2s (pos->id), |
1063 | continue; /* Ignore bloomfiltered peers */ | 1116 | GNUNET_h2s (key)); |
1064 | } | 1117 | continue; /* Ignore filtered peers */ |
1065 | count++; | 1118 | } |
1066 | pos = pos->next; | 1119 | total++; |
1120 | } /* for all peers in bucket */ | ||
1121 | } /* for all buckets */ | ||
1122 | if (0 == total) /* No peers to select from! */ | ||
1123 | { | ||
1124 | GNUNET_STATISTICS_update (GDS_stats, | ||
1125 | "# Peer selection failed", | ||
1126 | 1, | ||
1127 | GNUNET_NO); | ||
1128 | return NULL; | ||
1067 | } | 1129 | } |
1068 | } | 1130 | |
1069 | if (0 == count) /* No peers to select from! */ | 1131 | /* Now actually choose a peer */ |
1070 | { | 1132 | selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, |
1071 | GNUNET_STATISTICS_update (GDS_stats, | 1133 | total); |
1072 | gettext_noop ("# Peer selection failed"), 1, | 1134 | for (unsigned int bc = 0; bc < closest_bucket; bc++) |
1073 | GNUNET_NO); | ||
1074 | return NULL; | ||
1075 | } | ||
1076 | /* Now actually choose a peer */ | ||
1077 | selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, | ||
1078 | count); | ||
1079 | count = 0; | ||
1080 | for (bc = 0; bc < closest_bucket; bc++) | ||
1081 | { | ||
1082 | for (pos = k_buckets[bc].head; ((pos != NULL) && (count < bucket_size)); | ||
1083 | pos = pos->next) | ||
1084 | { | 1135 | { |
1085 | if ((bloom != NULL) && | 1136 | unsigned int count = 0; |
1086 | (GNUNET_YES == | 1137 | |
1087 | GNUNET_CONTAINER_bloomfilter_test (bloom, | 1138 | for (struct PeerInfo *pos = k_buckets[bc].head; |
1088 | &pos->phash))) | 1139 | pos != NULL; |
1089 | { | 1140 | pos = pos->next) |
1090 | continue; /* Ignore bloomfiltered peers */ | ||
1091 | } | ||
1092 | if (0 == selected--) | ||
1093 | { | 1141 | { |
1094 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 1142 | count++; |
1095 | "Selected peer `%s' in random routing for %s\n", | 1143 | if (count > bucket_size) |
1096 | GNUNET_i2s (pos->id), | 1144 | break; /* limits search to #bucket_size peers per bucket */ |
1097 | GNUNET_h2s (key)); | 1145 | |
1098 | return pos; | 1146 | if (GNUNET_YES == |
1099 | } | 1147 | GNUNET_CONTAINER_bloomfilter_test (bloom, |
1100 | } | 1148 | &pos->phash)) |
1101 | } | 1149 | continue; /* Ignore bloomfiltered peers */ |
1150 | if (0 == selected--) | ||
1151 | { | ||
1152 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1153 | "Selected peer `%s' in random routing for %s\n", | ||
1154 | GNUNET_i2s (pos->id), | ||
1155 | GNUNET_h2s (key)); | ||
1156 | return pos; | ||
1157 | } | ||
1158 | } /* for peers in bucket */ | ||
1159 | } /* for all buckets */ | ||
1160 | } /* random peer selection scope */ | ||
1102 | GNUNET_break (0); | 1161 | GNUNET_break (0); |
1103 | return NULL; | 1162 | return NULL; |
1104 | } | 1163 | } |
@@ -1109,13 +1168,13 @@ select_peer (const struct GNUNET_HashCode *key, | |||
1109 | * forwarded to. | 1168 | * forwarded to. |
1110 | * | 1169 | * |
1111 | * @param key routing key | 1170 | * @param key routing key |
1112 | * @param bloom bloom filter excluding peers as targets, all selected | 1171 | * @param[in,out] bloom Bloom filter excluding peers as targets, |
1113 | * peers will be added to the bloom filter | 1172 | * all selected peers will be added to the Bloom filter |
1114 | * @param hop_count number of hops the request has traversed so far | 1173 | * @param hop_count number of hops the request has traversed so far |
1115 | * @param target_replication desired number of replicas | 1174 | * @param target_replication desired number of replicas |
1116 | * @param targets where to store an array of target peers (to be | 1175 | * @param[out] targets where to store an array of target peers (to be |
1117 | * free'd by the caller) | 1176 | * free()ed by the caller) |
1118 | * @return number of peers returned in 'targets'. | 1177 | * @return number of peers returned in @a targets. |
1119 | */ | 1178 | */ |
1120 | static unsigned int | 1179 | static unsigned int |
1121 | get_target_peers (const struct GNUNET_HashCode *key, | 1180 | get_target_peers (const struct GNUNET_HashCode *key, |
@@ -1124,23 +1183,24 @@ get_target_peers (const struct GNUNET_HashCode *key, | |||
1124 | uint32_t target_replication, | 1183 | uint32_t target_replication, |
1125 | struct PeerInfo ***targets) | 1184 | struct PeerInfo ***targets) |
1126 | { | 1185 | { |
1127 | unsigned int ret; | 1186 | unsigned int target; |
1128 | unsigned int off; | 1187 | unsigned int off; |
1129 | struct PeerInfo **rtargets; | 1188 | struct PeerInfo **rtargets; |
1130 | struct PeerInfo *nxt; | ||
1131 | 1189 | ||
1132 | GNUNET_assert (NULL != bloom); | 1190 | GNUNET_assert (NULL != bloom); |
1133 | ret = get_forward_count (hop_count, | 1191 | target = get_forward_count (hop_count, |
1134 | target_replication); | 1192 | target_replication); |
1135 | if (0 == ret) | 1193 | if (0 == target) |
1136 | { | 1194 | { |
1137 | *targets = NULL; | 1195 | *targets = NULL; |
1138 | return 0; | 1196 | return 0; |
1139 | } | 1197 | } |
1140 | rtargets = GNUNET_new_array (ret, | 1198 | rtargets = GNUNET_new_array (target, |
1141 | struct PeerInfo *); | 1199 | struct PeerInfo *); |
1142 | for (off = 0; off < ret; off++) | 1200 | for (off = 0; off < target; off++) |
1143 | { | 1201 | { |
1202 | struct PeerInfo *nxt; | ||
1203 | |||
1144 | nxt = select_peer (key, | 1204 | nxt = select_peer (key, |
1145 | bloom, | 1205 | bloom, |
1146 | hop_count); | 1206 | hop_count); |
@@ -1159,7 +1219,7 @@ get_target_peers (const struct GNUNET_HashCode *key, | |||
1159 | GNUNET_CONTAINER_multipeermap_size (all_connected_peers), | 1219 | GNUNET_CONTAINER_multipeermap_size (all_connected_peers), |
1160 | (unsigned int) hop_count, | 1220 | (unsigned int) hop_count, |
1161 | GNUNET_h2s (key), | 1221 | GNUNET_h2s (key), |
1162 | ret); | 1222 | target); |
1163 | if (0 == off) | 1223 | if (0 == off) |
1164 | { | 1224 | { |
1165 | GNUNET_free (rtargets); | 1225 | GNUNET_free (rtargets); |
@@ -1171,11 +1231,13 @@ get_target_peers (const struct GNUNET_HashCode *key, | |||
1171 | "Forwarding query `%s' to %u peers (goal was %u peers)\n", | 1231 | "Forwarding query `%s' to %u peers (goal was %u peers)\n", |
1172 | GNUNET_h2s (key), | 1232 | GNUNET_h2s (key), |
1173 | off, | 1233 | off, |
1174 | ret); | 1234 | target); |
1175 | return off; | 1235 | return off; |
1176 | } | 1236 | } |
1177 | 1237 | ||
1178 | 1238 | ||
1239 | // FIXME-CG: REVIEW from here... | ||
1240 | |||
1179 | enum GNUNET_GenericReturnValue | 1241 | enum GNUNET_GenericReturnValue |
1180 | GDS_NEIGHBOURS_handle_put (const struct GDS_DATACACHE_BlockData *bd, | 1242 | GDS_NEIGHBOURS_handle_put (const struct GDS_DATACACHE_BlockData *bd, |
1181 | enum GNUNET_DHT_RouteOption options, | 1243 | enum GNUNET_DHT_RouteOption options, |
@@ -1247,8 +1309,7 @@ GDS_NEIGHBOURS_handle_put (const struct GDS_DATACACHE_BlockData *bd, | |||
1247 | { | 1309 | { |
1248 | /* skip */ | 1310 | /* skip */ |
1249 | GNUNET_STATISTICS_update (GDS_stats, | 1311 | GNUNET_STATISTICS_update (GDS_stats, |
1250 | gettext_noop ( | 1312 | "# P2P messages dropped due to full queue", |
1251 | "# P2P messages dropped due to full queue"), | ||
1252 | 1, | 1313 | 1, |
1253 | GNUNET_NO); | 1314 | GNUNET_NO); |
1254 | skip_count++; | 1315 | skip_count++; |
@@ -1316,7 +1377,7 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type, | |||
1316 | 1377 | ||
1317 | GNUNET_assert (NULL != peer_bf); | 1378 | GNUNET_assert (NULL != peer_bf); |
1318 | GNUNET_STATISTICS_update (GDS_stats, | 1379 | GNUNET_STATISTICS_update (GDS_stats, |
1319 | gettext_noop ("# GET requests routed"), | 1380 | "# GET requests routed", |
1320 | 1, | 1381 | 1, |
1321 | GNUNET_NO); | 1382 | GNUNET_NO); |
1322 | target_count = get_target_peers (key, | 1383 | target_count = get_target_peers (key, |
@@ -1359,8 +1420,7 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type, | |||
1359 | return GNUNET_NO; | 1420 | return GNUNET_NO; |
1360 | } | 1421 | } |
1361 | GNUNET_STATISTICS_update (GDS_stats, | 1422 | GNUNET_STATISTICS_update (GDS_stats, |
1362 | gettext_noop ( | 1423 | "# GET messages queued for transmission", |
1363 | "# GET messages queued for transmission"), | ||
1364 | target_count, | 1424 | target_count, |
1365 | GNUNET_NO); | 1425 | GNUNET_NO); |
1366 | /* forward request */ | 1426 | /* forward request */ |
@@ -1372,8 +1432,7 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type, | |||
1372 | { | 1432 | { |
1373 | /* skip */ | 1433 | /* skip */ |
1374 | GNUNET_STATISTICS_update (GDS_stats, | 1434 | GNUNET_STATISTICS_update (GDS_stats, |
1375 | gettext_noop ( | 1435 | "# P2P messages dropped due to full queue", |
1376 | "# P2P messages dropped due to full queue"), | ||
1377 | 1, GNUNET_NO); | 1436 | 1, GNUNET_NO); |
1378 | skip_count++; | 1437 | skip_count++; |
1379 | continue; | 1438 | continue; |
@@ -1581,7 +1640,7 @@ handle_dht_p2p_put (void *cls, | |||
1581 | if (GNUNET_TIME_absolute_is_past (bd.expiration_time)) | 1640 | if (GNUNET_TIME_absolute_is_past (bd.expiration_time)) |
1582 | { | 1641 | { |
1583 | GNUNET_STATISTICS_update (GDS_stats, | 1642 | GNUNET_STATISTICS_update (GDS_stats, |
1584 | gettext_noop ("# Expired PUTs discarded"), | 1643 | "# Expired PUTs discarded", |
1585 | 1, | 1644 | 1, |
1586 | GNUNET_NO); | 1645 | GNUNET_NO); |
1587 | return; | 1646 | return; |
@@ -1943,11 +2002,11 @@ handle_dht_p2p_get (void *cls, | |||
1943 | options = ntohl (get->options); | 2002 | options = ntohl (get->options); |
1944 | xquery = (const void *) &get[1]; | 2003 | xquery = (const void *) &get[1]; |
1945 | GNUNET_STATISTICS_update (GDS_stats, | 2004 | GNUNET_STATISTICS_update (GDS_stats, |
1946 | gettext_noop ("# P2P GET requests received"), | 2005 | "# P2P GET requests received", |
1947 | 1, | 2006 | 1, |
1948 | GNUNET_NO); | 2007 | GNUNET_NO); |
1949 | GNUNET_STATISTICS_update (GDS_stats, | 2008 | GNUNET_STATISTICS_update (GDS_stats, |
1950 | gettext_noop ("# P2P GET bytes received"), | 2009 | "# P2P GET bytes received", |
1951 | msize, | 2010 | msize, |
1952 | GNUNET_NO); | 2011 | GNUNET_NO); |
1953 | if (GNUNET_YES == log_route_details_stderr) | 2012 | if (GNUNET_YES == log_route_details_stderr) |
diff --git a/src/include/gnunet_crypto_lib.h b/src/include/gnunet_crypto_lib.h index 4e26429c9..1ab135d80 100644 --- a/src/include/gnunet_crypto_lib.h +++ b/src/include/gnunet_crypto_lib.h | |||
@@ -1058,21 +1058,6 @@ GNUNET_CRYPTO_hash_count_tailing_zeros (const struct GNUNET_HashCode *h); | |||
1058 | 1058 | ||
1059 | 1059 | ||
1060 | /** | 1060 | /** |
1061 | * Compute the distance between have and target as a 64-bit value. | ||
1062 | * Differences in the lower bits must count stronger than differences | ||
1063 | * in the higher bits. | ||
1064 | * | ||
1065 | * @param xor input hash | ||
1066 | * @param bucket up to which offset we are to ignore @a xor | ||
1067 | * @return the subsequent 64 bits after @a bucket from @a xor, in | ||
1068 | * host byte order. | ||
1069 | */ | ||
1070 | uint64_t | ||
1071 | GNUNET_CRYPTO_hash_bucket_distance (const struct GNUNET_HashCode *xor, | ||
1072 | unsigned int bucket); | ||
1073 | |||
1074 | |||
1075 | /** | ||
1076 | * @ingroup hash | 1061 | * @ingroup hash |
1077 | * Convert a hashcode into a key. | 1062 | * Convert a hashcode into a key. |
1078 | * | 1063 | * |
diff --git a/src/util/crypto_hash.c b/src/util/crypto_hash.c index b51ecd242..dcd46e5f9 100644 --- a/src/util/crypto_hash.c +++ b/src/util/crypto_hash.c | |||
@@ -146,41 +146,6 @@ GNUNET_CRYPTO_hash_xor (const struct GNUNET_HashCode *a, | |||
146 | } | 146 | } |
147 | 147 | ||
148 | 148 | ||
149 | uint64_t | ||
150 | GNUNET_CRYPTO_hash_bucket_distance (const struct GNUNET_HashCode *xor, | ||
151 | unsigned int bucket) | ||
152 | { | ||
153 | const uint64_t *u = (const uint64_t *) xor; | ||
154 | unsigned int idx; | ||
155 | unsigned int bits; | ||
156 | uint64_t rval; | ||
157 | |||
158 | if (bucket == 8 * sizeof(*xor)) | ||
159 | return 0; | ||
160 | bucket++; | ||
161 | idx = bucket / 64; | ||
162 | bits = bucket % 64; | ||
163 | if (idx >= sizeof (*xor) / sizeof (*u)) | ||
164 | return 0; | ||
165 | if (0 == bits) | ||
166 | { | ||
167 | /* keeps no bits */ | ||
168 | rval = 0; | ||
169 | } | ||
170 | else | ||
171 | { | ||
172 | /* keeps lowest (64-bits) bits */ | ||
173 | rval = GNUNET_ntohll (u[idx]) << bits; | ||
174 | } | ||
175 | if (idx + 1 < sizeof (*xor) / sizeof (*u)) | ||
176 | { | ||
177 | /* discards lowest (bits) bits */ | ||
178 | rval |= GNUNET_ntohll (u[idx + 1]) >> (64 - bits); | ||
179 | } | ||
180 | return rval; | ||
181 | } | ||
182 | |||
183 | |||
184 | void | 149 | void |
185 | GNUNET_CRYPTO_hash_to_aes_key ( | 150 | GNUNET_CRYPTO_hash_to_aes_key ( |
186 | const struct GNUNET_HashCode *hc, | 151 | const struct GNUNET_HashCode *hc, |
@@ -277,18 +242,19 @@ GNUNET_CRYPTO_hash_xorcmp (const struct GNUNET_HashCode *h1, | |||
277 | const struct GNUNET_HashCode *h2, | 242 | const struct GNUNET_HashCode *h2, |
278 | const struct GNUNET_HashCode *target) | 243 | const struct GNUNET_HashCode *target) |
279 | { | 244 | { |
280 | unsigned int d1; | 245 | const unsigned long long *l1 = (const unsigned long long *) h1; |
281 | unsigned int d2; | 246 | const unsigned long long *l2 = (const unsigned long long *) h2; |
247 | const unsigned long long *t = (const unsigned long long *) target; | ||
282 | 248 | ||
283 | for (ssize_t i = sizeof(struct GNUNET_HashCode) / sizeof(unsigned int) - 1; | 249 | GNUNET_static_assert (0 == sizeof (*h1) % sizeof (*l1)); |
284 | i >= 0; | 250 | for (size_t i = 0; i < sizeof(*h1) / sizeof(*l1); i++) |
285 | i--) | ||
286 | { | 251 | { |
287 | d1 = ((unsigned int *) h1)[i] ^ ((unsigned int *) target)[i]; | 252 | unsigned long long x1 = l1[i] ^ t[i]; |
288 | d2 = ((unsigned int *) h2)[i] ^ ((unsigned int *) target)[i]; | 253 | unsigned long long x2 = l2[i] ^ t[i]; |
289 | if (d1 > d2) | 254 | |
255 | if (x1 > x2) | ||
290 | return 1; | 256 | return 1; |
291 | else if (d1 < d2) | 257 | if (x1 < x2) |
292 | return -1; | 258 | return -1; |
293 | } | 259 | } |
294 | return 0; | 260 | return 0; |
diff --git a/src/util/test_crypto_hash.c b/src/util/test_crypto_hash.c index 1fddcfba8..8241676da 100644 --- a/src/util/test_crypto_hash.c +++ b/src/util/test_crypto_hash.c | |||
@@ -134,76 +134,6 @@ test_arithmetic (void) | |||
134 | GNUNET_CRYPTO_hash_count_leading_zeros (&h1)); | 134 | GNUNET_CRYPTO_hash_count_leading_zeros (&h1)); |
135 | GNUNET_assert (512 - 42 - 1 == | 135 | GNUNET_assert (512 - 42 - 1 == |
136 | GNUNET_CRYPTO_hash_count_tailing_zeros (&h1)); | 136 | GNUNET_CRYPTO_hash_count_tailing_zeros (&h1)); |
137 | memset (&h1, | ||
138 | 0, | ||
139 | sizeof (h1)); | ||
140 | memset (&h2, | ||
141 | 0, | ||
142 | sizeof (h2)); | ||
143 | h1.bits[3] = htonl (0x00800011); /* 3*32 + 8 Bits identical */ | ||
144 | h2.bits[3] = htonl (0x00000101); /* residual delta: 0x000220.. (+1 bit)*/ | ||
145 | /* Note: XOR: 0x00800110 */ | ||
146 | h1.bits[4] = htonl (0x14144141); | ||
147 | h2.bits[4] = htonl (0x28288282); /* residual delta: 0x3C3CC3.. */ | ||
148 | /* Note: XOR: 0x3C3CC3C3 */ | ||
149 | /* Note: XOR<<1: 0x78798786 */ | ||
150 | GNUNET_assert (104 == | ||
151 | GNUNET_CRYPTO_hash_count_leading_zeros (&h1)); | ||
152 | GNUNET_CRYPTO_hash_xor (&h1, | ||
153 | &h2, | ||
154 | &s); | ||
155 | GNUNET_assert (104 == | ||
156 | GNUNET_CRYPTO_hash_count_leading_zeros (&s)); | ||
157 | GNUNET_assert (0x0002207879878600LLU == | ||
158 | GNUNET_CRYPTO_hash_bucket_distance (&s, | ||
159 | 104)); | ||
160 | |||
161 | memset (&h1, | ||
162 | 0, | ||
163 | sizeof (h1)); | ||
164 | memset (&h2, | ||
165 | 0, | ||
166 | sizeof (h2)); | ||
167 | h1.bits[4] = htonl (0x00000001); /* 5*32 - 1 Bits identical */ | ||
168 | h2.bits[4] = htonl (0x00000000); | ||
169 | /* Note: XOR: 0x00000001 */ | ||
170 | h1.bits[5] = htonl (0x14144141); | ||
171 | h2.bits[5] = htonl (0x28288282); | ||
172 | /* Note: XOR: 0x3C3CC3C3 */ | ||
173 | GNUNET_assert (159 == | ||
174 | GNUNET_CRYPTO_hash_count_leading_zeros (&h1)); | ||
175 | GNUNET_CRYPTO_hash_xor (&h1, | ||
176 | &h2, | ||
177 | &s); | ||
178 | GNUNET_assert (159 == | ||
179 | GNUNET_CRYPTO_hash_count_leading_zeros (&s)); | ||
180 | GNUNET_assert (0x3C3CC3C300000000 == | ||
181 | GNUNET_CRYPTO_hash_bucket_distance (&s, | ||
182 | 159)); | ||
183 | |||
184 | memset (&h1, | ||
185 | 0, | ||
186 | sizeof (h1)); | ||
187 | memset (&h2, | ||
188 | 0, | ||
189 | sizeof (h2)); | ||
190 | h1.bits[14] = htonl (0x00000001); /* 15*32 - 1 Bits identical */ | ||
191 | h2.bits[14] = htonl (0x00000000); | ||
192 | /* Note: XOR: 0x00000001 */ | ||
193 | h1.bits[15] = htonl (0x14144141); | ||
194 | h2.bits[15] = htonl (0x28288282); | ||
195 | /* Note: XOR: 0x3C3CC3C3 */ | ||
196 | GNUNET_assert (479 == | ||
197 | GNUNET_CRYPTO_hash_count_leading_zeros (&h1)); | ||
198 | GNUNET_CRYPTO_hash_xor (&h1, | ||
199 | &h2, | ||
200 | &s); | ||
201 | GNUNET_assert (479 == | ||
202 | GNUNET_CRYPTO_hash_count_leading_zeros (&s)); | ||
203 | GNUNET_assert (0x3C3CC3C300000000 == | ||
204 | GNUNET_CRYPTO_hash_bucket_distance (&s, | ||
205 | 479)); | ||
206 | |||
207 | return 0; | 137 | return 0; |
208 | } | 138 | } |
209 | 139 | ||