diff options
Diffstat (limited to 'toxcore/DHT.c')
-rw-r--r-- | toxcore/DHT.c | 231 |
1 files changed, 115 insertions, 116 deletions
diff --git a/toxcore/DHT.c b/toxcore/DHT.c index 14c59a3d..fb6a9e3a 100644 --- a/toxcore/DHT.c +++ b/toxcore/DHT.c | |||
@@ -65,6 +65,11 @@ | |||
65 | /* Number of get node requests to send to quickly find close nodes. */ | 65 | /* Number of get node requests to send to quickly find close nodes. */ |
66 | #define MAX_BOOTSTRAP_TIMES 5 | 66 | #define MAX_BOOTSTRAP_TIMES 5 |
67 | 67 | ||
68 | static uint8_t calc_dist(uint8_t a, uint8_t b) | ||
69 | { | ||
70 | return a ^ b; | ||
71 | } | ||
72 | |||
68 | /* Compares pk1 and pk2 with pk. | 73 | /* Compares pk1 and pk2 with pk. |
69 | * | 74 | * |
70 | * return 0 if both are same distance. | 75 | * return 0 if both are same distance. |
@@ -79,43 +84,38 @@ int id_closest(const uint8_t *pk, const uint8_t *pk1, const uint8_t *pk2) | |||
79 | 84 | ||
80 | for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) { | 85 | for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) { |
81 | 86 | ||
82 | distance1 = pk[i] ^ pk1[i]; | 87 | distance1 = calc_dist(pk[i], pk1[i]); |
83 | distance2 = pk[i] ^ pk2[i]; | 88 | distance2 = calc_dist(pk[i], pk2[i]); |
84 | 89 | ||
85 | if (!i) { | 90 | if (distance1 < distance2) |
86 | if (distance1 & (1 << 7)) { | 91 | return 1; |
87 | d1_abs = 1; | ||
88 | } | ||
89 | 92 | ||
90 | if (distance2 & (1 << 7)) { | 93 | if (distance1 > distance2) |
91 | d2_abs = 1; | 94 | return 2; |
92 | } | 95 | } |
93 | } | ||
94 | 96 | ||
95 | if (d1_abs) | 97 | return 0; |
96 | distance1 = ~distance1; | 98 | } |
97 | 99 | ||
98 | if (d2_abs) | 100 | /* Return index of first unequal bit number. |
99 | distance2 = ~distance2; | 101 | */ |
102 | static unsigned int bit_by_bit_cmp(const uint8_t *pk1, const uint8_t *pk2) | ||
103 | { | ||
104 | unsigned int i, j = 0; | ||
100 | 105 | ||
101 | if (i == (crypto_box_PUBLICKEYBYTES - 1)) { | 106 | for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) { |
102 | if (d1_abs) | 107 | if (pk1[i] == pk2[i]) |
103 | if (distance1 != UINT8_MAX) | 108 | continue; |
104 | ++distance1; | ||
105 | 109 | ||
106 | if (d2_abs) | 110 | for (j = 0; j < 8; ++j) { |
107 | if (distance2 != UINT8_MAX) | 111 | if ((pk1[i] & (1 << (7 - j))) != (pk2[i] & (1 << (7 - j)))) |
108 | ++distance2; | 112 | break; |
109 | } | 113 | } |
110 | 114 | ||
111 | if (distance1 < distance2) | 115 | break; |
112 | return 1; | ||
113 | |||
114 | if (distance1 > distance2) | ||
115 | return 2; | ||
116 | } | 116 | } |
117 | 117 | ||
118 | return 0; | 118 | return i * 8 + j; |
119 | } | 119 | } |
120 | 120 | ||
121 | /* Shared key generations are costly, it is therefor smart to store commonly used | 121 | /* Shared key generations are costly, it is therefor smart to store commonly used |
@@ -586,7 +586,7 @@ static int get_somewhat_close_nodes(const DHT *dht, const uint8_t *public_key, N | |||
586 | { | 586 | { |
587 | uint32_t num_nodes = 0, i; | 587 | uint32_t num_nodes = 0, i; |
588 | get_close_nodes_inner(public_key, nodes_list, sa_family, | 588 | get_close_nodes_inner(public_key, nodes_list, sa_family, |
589 | dht->close_clientlist, LCLIENT_LIST, &num_nodes, is_LAN, want_good); | 589 | dht->close_clientlist, LCLIENT_LIST, &num_nodes, is_LAN, 0); |
590 | 590 | ||
591 | /*TODO uncomment this when hardening is added to close friend clients | 591 | /*TODO uncomment this when hardening is added to close friend clients |
592 | for (i = 0; i < dht->num_friends; ++i) | 592 | for (i = 0; i < dht->num_friends; ++i) |
@@ -780,6 +780,68 @@ static int replace_all( Client_data *list, | |||
780 | return 0; | 780 | return 0; |
781 | } | 781 | } |
782 | 782 | ||
783 | /* Add node to close list. | ||
784 | * | ||
785 | * simulate is set to 1 if we want to check if a node can be added to the list without adding it. | ||
786 | * | ||
787 | * return -1 on failure. | ||
788 | * return 0 on success. | ||
789 | */ | ||
790 | static int add_to_close(DHT *dht, const uint8_t *public_key, IP_Port ip_port, _Bool simulate) | ||
791 | { | ||
792 | unsigned int i; | ||
793 | |||
794 | unsigned int index = bit_by_bit_cmp(public_key, dht->self_public_key); | ||
795 | |||
796 | if (index > LCLIENT_LENGTH) | ||
797 | index = LCLIENT_LENGTH - 1; | ||
798 | |||
799 | for (i = 0; i < LCLIENT_NODES; ++i) { | ||
800 | Client_data *client = &dht->close_clientlist[(index * LCLIENT_NODES) + i]; | ||
801 | |||
802 | if (is_timeout(client->assoc4.timestamp, BAD_NODE_TIMEOUT) && is_timeout(client->assoc6.timestamp, BAD_NODE_TIMEOUT)) { | ||
803 | if (!simulate) { | ||
804 | IPPTsPng *ipptp_write = NULL; | ||
805 | IPPTsPng *ipptp_clear = NULL; | ||
806 | |||
807 | if (ip_port.ip.family == AF_INET) { | ||
808 | ipptp_write = &client->assoc4; | ||
809 | ipptp_clear = &client->assoc6; | ||
810 | } else { | ||
811 | ipptp_write = &client->assoc6; | ||
812 | ipptp_clear = &client->assoc4; | ||
813 | } | ||
814 | |||
815 | id_copy(client->public_key, public_key); | ||
816 | ipptp_write->ip_port = ip_port; | ||
817 | ipptp_write->timestamp = unix_time(); | ||
818 | |||
819 | ip_reset(&ipptp_write->ret_ip_port.ip); | ||
820 | ipptp_write->ret_ip_port.port = 0; | ||
821 | ipptp_write->ret_timestamp = 0; | ||
822 | |||
823 | /* zero out other address */ | ||
824 | memset(ipptp_clear, 0, sizeof(*ipptp_clear)); | ||
825 | } | ||
826 | |||
827 | return 0; | ||
828 | } | ||
829 | } | ||
830 | |||
831 | return -1; | ||
832 | } | ||
833 | |||
834 | /* Return 1 if node can be added to close list, 0 if it can't. | ||
835 | */ | ||
836 | _Bool node_addable_to_close_list(DHT *dht, const uint8_t *public_key, IP_Port ip_port) | ||
837 | { | ||
838 | if (add_to_close(dht, public_key, ip_port, 1) == 0) { | ||
839 | return 1; | ||
840 | } | ||
841 | |||
842 | return 0; | ||
843 | } | ||
844 | |||
783 | static _Bool is_pk_in_client_list(Client_data *list, unsigned int client_list_length, const uint8_t *public_key, | 845 | static _Bool is_pk_in_client_list(Client_data *list, unsigned int client_list_length, const uint8_t *public_key, |
784 | IP_Port ip_port) | 846 | IP_Port ip_port) |
785 | { | 847 | { |
@@ -807,23 +869,18 @@ static unsigned int ping_node_from_getnodes_ok(DHT *dht, const uint8_t *public_k | |||
807 | { | 869 | { |
808 | _Bool ret = 0; | 870 | _Bool ret = 0; |
809 | 871 | ||
810 | if (store_node_ok(&dht->close_clientlist[1], public_key, dht->self_public_key)) { | 872 | if (add_to_close(dht, public_key, ip_port, 1) == 0) { |
811 | ret = 1; | 873 | ret = 1; |
812 | } | 874 | } |
813 | 875 | ||
814 | if (store_node_ok(&dht->close_clientlist[0], public_key, dht->self_public_key)) { | 876 | if (ret && !client_in_nodelist(dht->to_bootstrap, dht->num_to_bootstrap, public_key)) { |
815 | ret = 1; | 877 | if (dht->num_to_bootstrap < MAX_CLOSE_TO_BOOTSTRAP_NODES) { |
816 | } | ||
817 | |||
818 | if (ret && !client_in_nodelist(dht->to_bootstrap, dht->num_to_bootstrap, public_key) | ||
819 | && !is_pk_in_client_list(dht->close_clientlist, LCLIENT_LIST, public_key, ip_port)) { | ||
820 | if (dht->num_to_bootstrap < MAX_SENT_NODES) { | ||
821 | memcpy(dht->to_bootstrap[dht->num_to_bootstrap].public_key, public_key, crypto_box_PUBLICKEYBYTES); | 878 | memcpy(dht->to_bootstrap[dht->num_to_bootstrap].public_key, public_key, crypto_box_PUBLICKEYBYTES); |
822 | dht->to_bootstrap[dht->num_to_bootstrap].ip_port = ip_port; | 879 | dht->to_bootstrap[dht->num_to_bootstrap].ip_port = ip_port; |
823 | ++dht->num_to_bootstrap; | 880 | ++dht->num_to_bootstrap; |
824 | } else { | 881 | } else { |
825 | //TODO: ipv6 vs v4 | 882 | //TODO: ipv6 vs v4 |
826 | add_to_list(dht->to_bootstrap, MAX_SENT_NODES, public_key, ip_port, dht->self_public_key); | 883 | add_to_list(dht->to_bootstrap, MAX_CLOSE_TO_BOOTSTRAP_NODES, public_key, ip_port, dht->self_public_key); |
827 | } | 884 | } |
828 | } | 885 | } |
829 | 886 | ||
@@ -878,7 +935,7 @@ int addto_lists(DHT *dht, IP_Port ip_port, const uint8_t *public_key) | |||
878 | * to replace the first ip by the second. | 935 | * to replace the first ip by the second. |
879 | */ | 936 | */ |
880 | if (!client_or_ip_port_in_list(dht->close_clientlist, LCLIENT_LIST, public_key, ip_port)) { | 937 | if (!client_or_ip_port_in_list(dht->close_clientlist, LCLIENT_LIST, public_key, ip_port)) { |
881 | if (replace_all(dht->close_clientlist, LCLIENT_LIST, public_key, ip_port, dht->self_public_key)) | 938 | if (add_to_close(dht, public_key, ip_port, 0)) |
882 | used++; | 939 | used++; |
883 | } else | 940 | } else |
884 | used++; | 941 | used++; |
@@ -1079,18 +1136,19 @@ static int sendnodes_ipv6(const DHT *dht, IP_Port ip_port, const uint8_t *public | |||
1079 | Node_format nodes_list[MAX_SENT_NODES]; | 1136 | Node_format nodes_list[MAX_SENT_NODES]; |
1080 | uint32_t num_nodes = get_close_nodes(dht, client_id, nodes_list, 0, LAN_ip(ip_port.ip) == 0, 1); | 1137 | uint32_t num_nodes = get_close_nodes(dht, client_id, nodes_list, 0, LAN_ip(ip_port.ip) == 0, 1); |
1081 | 1138 | ||
1082 | if (num_nodes == 0) | ||
1083 | return 0; | ||
1084 | |||
1085 | uint8_t plain[1 + Node_format_size * MAX_SENT_NODES + length]; | 1139 | uint8_t plain[1 + Node_format_size * MAX_SENT_NODES + length]; |
1086 | uint8_t encrypt[sizeof(plain) + crypto_box_MACBYTES]; | 1140 | uint8_t encrypt[sizeof(plain) + crypto_box_MACBYTES]; |
1087 | uint8_t nonce[crypto_box_NONCEBYTES]; | 1141 | uint8_t nonce[crypto_box_NONCEBYTES]; |
1088 | new_nonce(nonce); | 1142 | new_nonce(nonce); |
1089 | 1143 | ||
1090 | int nodes_length = pack_nodes(plain + 1, Node_format_size * MAX_SENT_NODES, nodes_list, num_nodes); | 1144 | int nodes_length = 0; |
1091 | 1145 | ||
1092 | if (nodes_length <= 0) | 1146 | if (num_nodes) { |
1093 | return -1; | 1147 | nodes_length = pack_nodes(plain + 1, Node_format_size * MAX_SENT_NODES, nodes_list, num_nodes); |
1148 | |||
1149 | if (nodes_length <= 0) | ||
1150 | return -1; | ||
1151 | } | ||
1094 | 1152 | ||
1095 | plain[0] = num_nodes; | 1153 | plain[0] = num_nodes; |
1096 | memcpy(plain + 1 + nodes_length, sendback_data, length); | 1154 | memcpy(plain + 1 + nodes_length, sendback_data, length); |
@@ -1176,7 +1234,7 @@ static int handle_sendnodes_core(void *object, IP_Port source, const uint8_t *pa | |||
1176 | DHT *dht = object; | 1234 | DHT *dht = object; |
1177 | uint32_t cid_size = 1 + crypto_box_PUBLICKEYBYTES + crypto_box_NONCEBYTES + 1 + sizeof(uint64_t) + crypto_box_MACBYTES; | 1235 | uint32_t cid_size = 1 + crypto_box_PUBLICKEYBYTES + crypto_box_NONCEBYTES + 1 + sizeof(uint64_t) + crypto_box_MACBYTES; |
1178 | 1236 | ||
1179 | if (length <= cid_size) /* too short */ | 1237 | if (length < cid_size) /* too short */ |
1180 | return 1; | 1238 | return 1; |
1181 | 1239 | ||
1182 | uint32_t data_size = length - cid_size; | 1240 | uint32_t data_size = length - cid_size; |
@@ -1200,7 +1258,7 @@ static int handle_sendnodes_core(void *object, IP_Port source, const uint8_t *pa | |||
1200 | if ((unsigned int)len != sizeof(plain)) | 1258 | if ((unsigned int)len != sizeof(plain)) |
1201 | return 1; | 1259 | return 1; |
1202 | 1260 | ||
1203 | if (plain[0] > size_plain_nodes || plain[0] == 0) | 1261 | if (plain[0] > size_plain_nodes) |
1204 | return 1; | 1262 | return 1; |
1205 | 1263 | ||
1206 | Node_format sendback_node; | 1264 | Node_format sendback_node; |
@@ -1220,7 +1278,7 @@ static int handle_sendnodes_core(void *object, IP_Port source, const uint8_t *pa | |||
1220 | if (num_nodes != plain[0]) | 1278 | if (num_nodes != plain[0]) |
1221 | return 1; | 1279 | return 1; |
1222 | 1280 | ||
1223 | if (num_nodes <= 0) | 1281 | if (num_nodes < 0) |
1224 | return 1; | 1282 | return 1; |
1225 | 1283 | ||
1226 | /* store the address the *request* was sent to */ | 1284 | /* store the address the *request* was sent to */ |
@@ -1390,54 +1448,9 @@ int DHT_getfriendip(const DHT *dht, const uint8_t *public_key, IP_Port *ip_port) | |||
1390 | return -1; | 1448 | return -1; |
1391 | } | 1449 | } |
1392 | 1450 | ||
1393 | static void abs_divide_by_2(uint8_t *public_key_dist) | ||
1394 | { | ||
1395 | unsigned int i; | ||
1396 | _Bool one = 0, abs = 0; | ||
1397 | |||
1398 | if (public_key_dist[0] & (1 << 7)) { | ||
1399 | for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) { | ||
1400 | public_key_dist[i] = ~public_key_dist[i]; | ||
1401 | } | ||
1402 | |||
1403 | if (public_key_dist[crypto_box_PUBLICKEYBYTES - 1] != UINT8_MAX) | ||
1404 | ++public_key_dist[crypto_box_PUBLICKEYBYTES - 1]; | ||
1405 | } | ||
1406 | |||
1407 | for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) { | ||
1408 | _Bool temp = 0; | ||
1409 | |||
1410 | if (public_key_dist[i] & (1)) { | ||
1411 | temp = 1; | ||
1412 | } | ||
1413 | |||
1414 | public_key_dist[i] >>= 1; | ||
1415 | |||
1416 | if (one) | ||
1417 | public_key_dist[i] += (1 << 7); | ||
1418 | |||
1419 | one = temp; | ||
1420 | } | ||
1421 | } | ||
1422 | |||
1423 | static void find_midpoint(uint8_t *out, const uint8_t *top, const uint8_t *bot) | ||
1424 | { | ||
1425 | unsigned int i; | ||
1426 | |||
1427 | for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) { | ||
1428 | out[i] = top[i] ^ bot[i]; | ||
1429 | } | ||
1430 | |||
1431 | abs_divide_by_2(out); | ||
1432 | |||
1433 | for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) { | ||
1434 | out[i] ^= bot[i]; | ||
1435 | } | ||
1436 | } | ||
1437 | |||
1438 | /* returns number of nodes not in kill-timeout */ | 1451 | /* returns number of nodes not in kill-timeout */ |
1439 | static uint8_t do_ping_and_sendnode_requests(DHT *dht, uint64_t *lastgetnode, const uint8_t *public_key, | 1452 | static uint8_t do_ping_and_sendnode_requests(DHT *dht, uint64_t *lastgetnode, const uint8_t *public_key, |
1440 | Client_data *list, uint32_t list_count, uint32_t *bootstrap_times) | 1453 | Client_data *list, uint32_t list_count, uint32_t *bootstrap_times, _Bool sortable) |
1441 | { | 1454 | { |
1442 | uint32_t i; | 1455 | uint32_t i; |
1443 | uint8_t not_kill = 0; | 1456 | uint8_t not_kill = 0; |
@@ -1481,33 +1494,19 @@ static uint8_t do_ping_and_sendnode_requests(DHT *dht, uint64_t *lastgetnode, co | |||
1481 | } | 1494 | } |
1482 | } | 1495 | } |
1483 | 1496 | ||
1484 | if (sort_ok) { | 1497 | if (sortable && sort_ok) { |
1485 | sort_client_list(list, list_count, public_key); | 1498 | sort_client_list(list, list_count, public_key); |
1486 | } | 1499 | } |
1487 | 1500 | ||
1488 | if ((num_nodes != 0) && (is_timeout(*lastgetnode, GET_NODE_INTERVAL) || *bootstrap_times < MAX_BOOTSTRAP_TIMES)) { | 1501 | if ((num_nodes != 0) && (is_timeout(*lastgetnode, GET_NODE_INTERVAL) || *bootstrap_times < MAX_BOOTSTRAP_TIMES)) { |
1489 | uint32_t rand_node = rand() % (num_nodes * 2); | 1502 | uint32_t rand_node = rand() % (num_nodes); |
1490 | |||
1491 | if (rand_node >= num_nodes) { | ||
1492 | rand_node = rand_node % num_nodes; | ||
1493 | |||
1494 | if ((num_nodes - 1) != rand_node) { | ||
1495 | rand_node += rand() % (num_nodes - (rand_node + 1)); | ||
1496 | } | ||
1497 | |||
1498 | if (memcmp(client_list[rand_node]->public_key, public_key, crypto_box_PUBLICKEYBYTES) != 0) { | ||
1499 | uint8_t get_pk[crypto_box_PUBLICKEYBYTES]; | ||
1500 | find_midpoint(get_pk, client_list[rand_node]->public_key, public_key); | ||
1501 | getnodes(dht, assoc_list[rand_node]->ip_port, client_list[rand_node]->public_key, get_pk, NULL); | ||
1502 | } | ||
1503 | } else { | ||
1504 | if ((num_nodes - 1) != rand_node) { | ||
1505 | rand_node += rand() % (num_nodes - (rand_node + 1)); | ||
1506 | } | ||
1507 | 1503 | ||
1508 | getnodes(dht, assoc_list[rand_node]->ip_port, client_list[rand_node]->public_key, public_key, NULL); | 1504 | if ((num_nodes - 1) != rand_node) { |
1505 | rand_node += rand() % (num_nodes - (rand_node + 1)); | ||
1509 | } | 1506 | } |
1510 | 1507 | ||
1508 | getnodes(dht, assoc_list[rand_node]->ip_port, client_list[rand_node]->public_key, public_key, NULL); | ||
1509 | |||
1511 | *lastgetnode = temp_time; | 1510 | *lastgetnode = temp_time; |
1512 | ++*bootstrap_times; | 1511 | ++*bootstrap_times; |
1513 | } | 1512 | } |
@@ -1532,7 +1531,7 @@ static void do_DHT_friends(DHT *dht) | |||
1532 | friend->num_to_bootstrap = 0; | 1531 | friend->num_to_bootstrap = 0; |
1533 | 1532 | ||
1534 | do_ping_and_sendnode_requests(dht, &friend->lastgetnode, friend->public_key, friend->client_list, MAX_FRIEND_CLIENTS, | 1533 | do_ping_and_sendnode_requests(dht, &friend->lastgetnode, friend->public_key, friend->client_list, MAX_FRIEND_CLIENTS, |
1535 | &friend->bootstrap_times); | 1534 | &friend->bootstrap_times, 1); |
1536 | } | 1535 | } |
1537 | } | 1536 | } |
1538 | 1537 | ||
@@ -1550,7 +1549,7 @@ static void do_Close(DHT *dht) | |||
1550 | dht->num_to_bootstrap = 0; | 1549 | dht->num_to_bootstrap = 0; |
1551 | 1550 | ||
1552 | uint8_t not_killed = do_ping_and_sendnode_requests(dht, &dht->close_lastgetnodes, dht->self_public_key, | 1551 | uint8_t not_killed = do_ping_and_sendnode_requests(dht, &dht->close_lastgetnodes, dht->self_public_key, |
1553 | dht->close_clientlist, LCLIENT_LIST, &dht->close_bootstrap_times); | 1552 | dht->close_clientlist, LCLIENT_LIST, &dht->close_bootstrap_times, 0); |
1554 | 1553 | ||
1555 | if (!not_killed) { | 1554 | if (!not_killed) { |
1556 | /* all existing nodes are at least KILL_NODE_TIMEOUT, | 1555 | /* all existing nodes are at least KILL_NODE_TIMEOUT, |
@@ -2452,7 +2451,7 @@ void do_DHT(DHT *dht) | |||
2452 | do_DHT_friends(dht); | 2451 | do_DHT_friends(dht); |
2453 | do_NAT(dht); | 2452 | do_NAT(dht); |
2454 | do_to_ping(dht->ping); | 2453 | do_to_ping(dht->ping); |
2455 | do_hardening(dht); | 2454 | //do_hardening(dht); |
2456 | #ifdef ENABLE_ASSOC_DHT | 2455 | #ifdef ENABLE_ASSOC_DHT |
2457 | 2456 | ||
2458 | if (dht->assoc) | 2457 | if (dht->assoc) |