diff options
-rw-r--r-- | toxcore/Makefile.inc | 2 | ||||
-rw-r--r-- | toxcore/ping.c | 135 | ||||
-rw-r--r-- | toxcore/ping_array.c | 162 | ||||
-rw-r--r-- | toxcore/ping_array.h | 75 |
4 files changed, 272 insertions, 102 deletions
diff --git a/toxcore/Makefile.inc b/toxcore/Makefile.inc index 4c959789..7c1cf66e 100644 --- a/toxcore/Makefile.inc +++ b/toxcore/Makefile.inc | |||
@@ -11,6 +11,8 @@ libtoxcore_la_SOURCES = ../toxcore/DHT.h \ | |||
11 | ../toxcore/network.c \ | 11 | ../toxcore/network.c \ |
12 | ../toxcore/crypto_core.h \ | 12 | ../toxcore/crypto_core.h \ |
13 | ../toxcore/crypto_core.c \ | 13 | ../toxcore/crypto_core.c \ |
14 | ../toxcore/ping_array.h \ | ||
15 | ../toxcore/ping_array.c \ | ||
14 | ../toxcore/net_crypto.h \ | 16 | ../toxcore/net_crypto.h \ |
15 | ../toxcore/net_crypto.c \ | 17 | ../toxcore/net_crypto.c \ |
16 | ../toxcore/friend_requests.h \ | 18 | ../toxcore/friend_requests.h \ |
diff --git a/toxcore/ping.c b/toxcore/ping.c index 35aab86f..52817cd6 100644 --- a/toxcore/ping.c +++ b/toxcore/ping.c | |||
@@ -34,6 +34,7 @@ | |||
34 | 34 | ||
35 | #include "network.h" | 35 | #include "network.h" |
36 | #include "util.h" | 36 | #include "util.h" |
37 | #include "ping_array.h" | ||
37 | 38 | ||
38 | #define PING_NUM_MAX 512 | 39 | #define PING_NUM_MAX 512 |
39 | 40 | ||
@@ -43,109 +44,18 @@ | |||
43 | /* Ping newly announced nodes to ping per TIME_TO_PING seconds*/ | 44 | /* Ping newly announced nodes to ping per TIME_TO_PING seconds*/ |
44 | #define TIME_TO_PING 3 | 45 | #define TIME_TO_PING 3 |
45 | 46 | ||
46 | typedef struct { | ||
47 | IP_Port ip_port; | ||
48 | uint64_t id; | ||
49 | uint64_t timestamp; | ||
50 | uint8_t shared_key[crypto_box_BEFORENMBYTES]; | ||
51 | } pinged_t; | ||
52 | 47 | ||
53 | struct PING { | 48 | struct PING { |
54 | DHT *dht; | 49 | DHT *dht; |
55 | 50 | ||
56 | pinged_t pings[PING_NUM_MAX]; | 51 | Ping_Array ping_array; |
57 | size_t num_pings; | ||
58 | size_t pos_pings; | ||
59 | |||
60 | Node_format to_ping[MAX_TO_PING]; | 52 | Node_format to_ping[MAX_TO_PING]; |
61 | uint64_t last_to_ping; | 53 | uint64_t last_to_ping; |
62 | }; | 54 | }; |
63 | 55 | ||
64 | static int is_ping_timeout(uint64_t time) | ||
65 | { | ||
66 | return is_timeout(time, PING_TIMEOUT); | ||
67 | } | ||
68 | |||
69 | static void remove_timeouts(PING *ping) // O(n) | ||
70 | { | ||
71 | size_t i, id; | ||
72 | size_t new_pos = ping->pos_pings; | ||
73 | size_t new_num = ping->num_pings; | ||
74 | |||
75 | // Loop through buffer, oldest first. | ||
76 | for (i = 0; i < ping->num_pings; i++) { | ||
77 | id = (ping->pos_pings + i) % PING_NUM_MAX; | ||
78 | |||
79 | if (is_ping_timeout(ping->pings[id].timestamp)) { | ||
80 | new_pos++; | ||
81 | new_num--; | ||
82 | } | ||
83 | // Break here because list is sorted. | ||
84 | else { | ||
85 | break; | ||
86 | } | ||
87 | } | ||
88 | |||
89 | ping->num_pings = new_num; | ||
90 | ping->pos_pings = new_pos % PING_NUM_MAX; | ||
91 | } | ||
92 | |||
93 | static uint64_t add_ping(PING *ping, IP_Port ipp, uint8_t *shared_encryption_key) // O(n) | ||
94 | { | ||
95 | size_t p; | ||
96 | |||
97 | remove_timeouts(ping); | ||
98 | |||
99 | /* Remove oldest ping if full buffer. */ | ||
100 | if (ping->num_pings == PING_NUM_MAX) { | ||
101 | ping->num_pings--; | ||
102 | ping->pos_pings = (ping->pos_pings + 1) % PING_NUM_MAX; | ||
103 | } | ||
104 | |||
105 | /* Insert new ping at end of list. */ | ||
106 | p = (ping->pos_pings + ping->num_pings) % PING_NUM_MAX; | ||
107 | |||
108 | ping->pings[p].ip_port = ipp; | ||
109 | ping->pings[p].timestamp = unix_time(); | ||
110 | ping->pings[p].id = random_64b(); | ||
111 | memcpy(ping->pings[p].shared_key, shared_encryption_key, crypto_box_BEFORENMBYTES); | ||
112 | |||
113 | ping->num_pings++; | ||
114 | return ping->pings[p].id; | ||
115 | } | ||
116 | |||
117 | /* checks if ip/port or ping_id are already in the list to ping | ||
118 | * if both are set, both must match, otherwise the set must match | ||
119 | * | ||
120 | * returns 0 if neither is set or no match was found | ||
121 | * returns the (index + 1) of the match if one was found | ||
122 | */ | ||
123 | static int is_pinging(PING *ping, IP_Port ipp, uint64_t ping_id) | ||
124 | { | ||
125 | // O(n) TODO: Replace this with something else. | ||
126 | |||
127 | /* at least one MUST be set */ | ||
128 | uint8_t ip_valid = ip_isset(&ipp.ip); | ||
129 | |||
130 | if (!ip_valid && !ping_id) | ||
131 | return 0; | ||
132 | |||
133 | size_t i; | ||
134 | |||
135 | remove_timeouts(ping); | ||
136 | |||
137 | for (i = 0; i < ping->num_pings; i++) { | ||
138 | size_t id = (ping->pos_pings + i) % PING_NUM_MAX; | ||
139 | |||
140 | if (!ping_id || (ping->pings[id].id == ping_id)) | ||
141 | if (!ip_valid || ipport_equal(&ping->pings[id].ip_port, &ipp)) | ||
142 | return id + 1; | ||
143 | } | ||
144 | |||
145 | return 0; | ||
146 | } | ||
147 | 56 | ||
148 | #define DHT_PING_SIZE (1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES + sizeof(uint64_t) + crypto_box_MACBYTES) | 57 | #define DHT_PING_SIZE (1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES + sizeof(uint64_t) + crypto_box_MACBYTES) |
58 | #define PING_DATA_SIZE (CLIENT_ID_SIZE + sizeof(IP_Port)) | ||
149 | 59 | ||
150 | int send_ping_request(PING *ping, IP_Port ipp, uint8_t *client_id) | 60 | int send_ping_request(PING *ping, IP_Port ipp, uint8_t *client_id) |
151 | { | 61 | { |
@@ -153,7 +63,7 @@ int send_ping_request(PING *ping, IP_Port ipp, uint8_t *client_id) | |||
153 | int rc; | 63 | int rc; |
154 | uint64_t ping_id; | 64 | uint64_t ping_id; |
155 | 65 | ||
156 | if (is_pinging(ping, ipp, 0) || id_equal(client_id, ping->dht->self_public_key)) | 66 | if (id_equal(client_id, ping->dht->self_public_key)) |
157 | return 1; | 67 | return 1; |
158 | 68 | ||
159 | uint8_t shared_key[crypto_box_BEFORENMBYTES]; | 69 | uint8_t shared_key[crypto_box_BEFORENMBYTES]; |
@@ -161,7 +71,13 @@ int send_ping_request(PING *ping, IP_Port ipp, uint8_t *client_id) | |||
161 | // generate key to encrypt ping_id with recipient privkey | 71 | // generate key to encrypt ping_id with recipient privkey |
162 | DHT_get_shared_key_sent(ping->dht, shared_key, client_id); | 72 | DHT_get_shared_key_sent(ping->dht, shared_key, client_id); |
163 | // Generate random ping_id. | 73 | // Generate random ping_id. |
164 | ping_id = add_ping(ping, ipp, shared_key); | 74 | uint8_t data[PING_DATA_SIZE]; |
75 | id_copy(data, client_id); | ||
76 | memcpy(data + CLIENT_ID_SIZE, &ipp, sizeof(IP_Port)); | ||
77 | ping_id = ping_array_add(&ping->ping_array, data, sizeof(data)); | ||
78 | |||
79 | if (ping_id == 0) | ||
80 | return 1; | ||
165 | 81 | ||
166 | pk[0] = NET_PACKET_PING_REQUEST; | 82 | pk[0] = NET_PACKET_PING_REQUEST; |
167 | id_copy(pk + 1, ping->dht->self_public_key); // Our pubkey | 83 | id_copy(pk + 1, ping->dht->self_public_key); // Our pubkey |
@@ -252,14 +168,13 @@ static int handle_ping_response(void *_dht, IP_Port source, uint8_t *packet, uin | |||
252 | if (id_equal(packet + 1, ping->dht->self_public_key)) | 168 | if (id_equal(packet + 1, ping->dht->self_public_key)) |
253 | return 1; | 169 | return 1; |
254 | 170 | ||
255 | int ping_index = is_pinging(ping, source, 0); | 171 | uint8_t shared_key[crypto_box_BEFORENMBYTES]; |
256 | 172 | ||
257 | if (!ping_index) | 173 | // generate key to encrypt ping_id with recipient privkey |
258 | return 1; | 174 | DHT_get_shared_key_sent(ping->dht, shared_key, packet + 1); |
259 | 175 | ||
260 | --ping_index; | ||
261 | // Decrypt ping_id | 176 | // Decrypt ping_id |
262 | rc = decrypt_data_symmetric(ping->pings[ping_index].shared_key, | 177 | rc = decrypt_data_symmetric(shared_key, |
263 | packet + 1 + CLIENT_ID_SIZE, | 178 | packet + 1 + CLIENT_ID_SIZE, |
264 | packet + 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES, | 179 | packet + 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES, |
265 | sizeof(ping_id) + crypto_box_MACBYTES, | 180 | sizeof(ping_id) + crypto_box_MACBYTES, |
@@ -268,11 +183,21 @@ static int handle_ping_response(void *_dht, IP_Port source, uint8_t *packet, uin | |||
268 | if (rc != sizeof(ping_id)) | 183 | if (rc != sizeof(ping_id)) |
269 | return 1; | 184 | return 1; |
270 | 185 | ||
271 | if (ping->pings[ping_index].id != ping_id) | 186 | uint8_t data[PING_DATA_SIZE]; |
187 | |||
188 | if (ping_array_check(data, sizeof(data), &ping->ping_array, ping_id) != sizeof(data)) | ||
272 | return 1; | 189 | return 1; |
273 | 190 | ||
274 | addto_lists(dht, source, packet + 1); | 191 | if (!id_equal(packet + 1, data)) |
192 | return 1; | ||
193 | |||
194 | IP_Port ipp; | ||
195 | memcpy(&ipp, data + CLIENT_ID_SIZE, sizeof(IP_Port)); | ||
275 | 196 | ||
197 | if (!ipport_equal(&ipp, &source)) | ||
198 | return 1; | ||
199 | |||
200 | addto_lists(dht, source, packet + 1); | ||
276 | return 0; | 201 | return 0; |
277 | } | 202 | } |
278 | 203 | ||
@@ -348,6 +273,11 @@ PING *new_ping(DHT *dht) | |||
348 | if (ping == NULL) | 273 | if (ping == NULL) |
349 | return NULL; | 274 | return NULL; |
350 | 275 | ||
276 | if (ping_array_init(&ping->ping_array, PING_NUM_MAX, PING_TIMEOUT) != 0) { | ||
277 | free(ping); | ||
278 | return NULL; | ||
279 | } | ||
280 | |||
351 | ping->dht = dht; | 281 | ping->dht = dht; |
352 | networking_registerhandler(ping->dht->net, NET_PACKET_PING_REQUEST, &handle_ping_request, dht); | 282 | networking_registerhandler(ping->dht->net, NET_PACKET_PING_REQUEST, &handle_ping_request, dht); |
353 | networking_registerhandler(ping->dht->net, NET_PACKET_PING_RESPONSE, &handle_ping_response, dht); | 283 | networking_registerhandler(ping->dht->net, NET_PACKET_PING_RESPONSE, &handle_ping_response, dht); |
@@ -359,6 +289,7 @@ void kill_ping(PING *ping) | |||
359 | { | 289 | { |
360 | networking_registerhandler(ping->dht->net, NET_PACKET_PING_REQUEST, NULL, NULL); | 290 | networking_registerhandler(ping->dht->net, NET_PACKET_PING_REQUEST, NULL, NULL); |
361 | networking_registerhandler(ping->dht->net, NET_PACKET_PING_RESPONSE, NULL, NULL); | 291 | networking_registerhandler(ping->dht->net, NET_PACKET_PING_RESPONSE, NULL, NULL); |
292 | ping_array_free_all(&ping->ping_array); | ||
362 | 293 | ||
363 | free(ping); | 294 | free(ping); |
364 | } | 295 | } |
diff --git a/toxcore/ping_array.c b/toxcore/ping_array.c new file mode 100644 index 00000000..cb18ceb3 --- /dev/null +++ b/toxcore/ping_array.c | |||
@@ -0,0 +1,162 @@ | |||
1 | /* ping_array.c | ||
2 | * | ||
3 | * Implementation of an efficient array to store that we pinged something. | ||
4 | * | ||
5 | * | ||
6 | * Copyright (C) 2014 Tox project All Rights Reserved. | ||
7 | * | ||
8 | * This file is part of Tox. | ||
9 | * | ||
10 | * Tox is free software: you can redistribute it and/or modify | ||
11 | * it under the terms of the GNU General Public License as published by | ||
12 | * the Free Software Foundation, either version 3 of the License, or | ||
13 | * (at your option) any later version. | ||
14 | * | ||
15 | * Tox is distributed in the hope that it will be useful, | ||
16 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
17 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
18 | * GNU General Public License for more details. | ||
19 | * | ||
20 | * You should have received a copy of the GNU General Public License | ||
21 | * along with Tox. If not, see <http://www.gnu.org/licenses/>. | ||
22 | * | ||
23 | */ | ||
24 | |||
25 | #ifdef HAVE_CONFIG_H | ||
26 | #include "config.h" | ||
27 | #endif | ||
28 | |||
29 | #include "ping_array.h" | ||
30 | #include "crypto_core.h" | ||
31 | #include "util.h" | ||
32 | |||
33 | static void clear_entry(Ping_Array *array, uint32_t index) | ||
34 | { | ||
35 | free(array->entries[index].data); | ||
36 | array->entries[index].data = NULL; | ||
37 | array->entries[index].length = | ||
38 | array->entries[index].time = | ||
39 | array->entries[index].ping_id = 0; | ||
40 | } | ||
41 | |||
42 | /* Clear timed out entries. | ||
43 | */ | ||
44 | static void ping_array_clear_timedout(Ping_Array *array) | ||
45 | { | ||
46 | while (array->last_deleted != array->last_added) { | ||
47 | uint32_t index = array->last_deleted % array->total_size; | ||
48 | |||
49 | if (!is_timeout(array->entries[index].time, array->timeout)) | ||
50 | break; | ||
51 | |||
52 | clear_entry(array, index); | ||
53 | ++array->last_deleted; | ||
54 | } | ||
55 | } | ||
56 | |||
57 | /* Add a data with length to the Ping_Array list and return a ping_id. | ||
58 | * | ||
59 | * return ping_id on success. | ||
60 | * return 0 on failure. | ||
61 | */ | ||
62 | uint64_t ping_array_add(Ping_Array *array, uint8_t *data, uint32_t length) | ||
63 | { | ||
64 | ping_array_clear_timedout(array); | ||
65 | uint32_t index = array->last_added % array->total_size; | ||
66 | |||
67 | if (array->entries[index].data != NULL) { | ||
68 | array->last_deleted = array->last_added - array->total_size; | ||
69 | clear_entry(array, index); | ||
70 | } | ||
71 | |||
72 | array->entries[index].data = malloc(length); | ||
73 | |||
74 | if (array->entries[index].data == NULL) | ||
75 | return 0; | ||
76 | |||
77 | memcpy(array->entries[index].data, data, length); | ||
78 | array->entries[index].length = length; | ||
79 | array->entries[index].time = unix_time(); | ||
80 | ++array->last_added; | ||
81 | uint64_t ping_id = random_64b(); | ||
82 | ping_id /= array->total_size; | ||
83 | ping_id *= array->total_size; | ||
84 | ping_id += index; | ||
85 | |||
86 | if (ping_id == 0) | ||
87 | ping_id += array->total_size; | ||
88 | |||
89 | array->entries[index].ping_id = ping_id; | ||
90 | return ping_id; | ||
91 | } | ||
92 | |||
93 | |||
94 | /* Check if ping_id is valid and not timed out. | ||
95 | * | ||
96 | * On success, copies the data into data of length, | ||
97 | * | ||
98 | * return length of data copied on success. | ||
99 | * return -1 on failure. | ||
100 | */ | ||
101 | int ping_array_check(uint8_t *data, uint32_t length, Ping_Array *array, uint64_t ping_id) | ||
102 | { | ||
103 | if (ping_id == 0) | ||
104 | return -1; | ||
105 | |||
106 | uint32_t index = ping_id % array->total_size; | ||
107 | |||
108 | if (array->entries[index].ping_id != ping_id) | ||
109 | return -1; | ||
110 | |||
111 | if (is_timeout(array->entries[index].time, array->timeout)) | ||
112 | return -1; | ||
113 | |||
114 | if (array->entries[index].length > length) | ||
115 | return -1; | ||
116 | |||
117 | if (array->entries[index].data == NULL) | ||
118 | return -1; | ||
119 | |||
120 | memcpy(data, array->entries[index].data, array->entries[index].length); | ||
121 | uint32_t len = array->entries[index].length; | ||
122 | clear_entry(array, index); | ||
123 | return len; | ||
124 | } | ||
125 | |||
126 | /* Initialize a Ping_Array. | ||
127 | * size represents the total size of the array and should be a power of 2. | ||
128 | * timeout represents the maximum timeout in seconds for the entry. | ||
129 | * | ||
130 | * return 0 on success. | ||
131 | * return -1 on failure. | ||
132 | */ | ||
133 | int ping_array_init(Ping_Array *empty_array, uint32_t size, uint32_t timeout) | ||
134 | { | ||
135 | if (size == 0 || timeout == 0 || empty_array == NULL) | ||
136 | return -1; | ||
137 | |||
138 | empty_array->entries = malloc(size * sizeof(Ping_Array_Entry)); | ||
139 | |||
140 | if (empty_array->entries == NULL) | ||
141 | return -1; | ||
142 | |||
143 | empty_array->last_deleted = empty_array->last_added = 0; | ||
144 | empty_array->total_size = size; | ||
145 | empty_array->timeout = timeout; | ||
146 | return 0; | ||
147 | } | ||
148 | |||
149 | /* Free all the allocated memory in a Ping_Array. | ||
150 | */ | ||
151 | void ping_array_free_all(Ping_Array *array) | ||
152 | { | ||
153 | while (array->last_deleted != array->last_added) { | ||
154 | uint32_t index = array->last_deleted % array->total_size; | ||
155 | clear_entry(array, index); | ||
156 | ++array->last_deleted; | ||
157 | } | ||
158 | |||
159 | free(array->entries); | ||
160 | array->entries = NULL; | ||
161 | } | ||
162 | |||
diff --git a/toxcore/ping_array.h b/toxcore/ping_array.h new file mode 100644 index 00000000..b7fff1eb --- /dev/null +++ b/toxcore/ping_array.h | |||
@@ -0,0 +1,75 @@ | |||
1 | /* ping_array.h | ||
2 | * | ||
3 | * Implementation of an efficient array to store that we pinged something. | ||
4 | * | ||
5 | * Copyright (C) 2013 Tox project All Rights Reserved. | ||
6 | * | ||
7 | * This file is part of Tox. | ||
8 | * | ||
9 | * Tox is free software: you can redistribute it and/or modify | ||
10 | * it under the terms of the GNU General Public License as published by | ||
11 | * the Free Software Foundation, either version 3 of the License, or | ||
12 | * (at your option) any later version. | ||
13 | * | ||
14 | * Tox is distributed in the hope that it will be useful, | ||
15 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
17 | * GNU General Public License for more details. | ||
18 | * | ||
19 | * You should have received a copy of the GNU General Public License | ||
20 | * along with Tox. If not, see <http://www.gnu.org/licenses/>. | ||
21 | * | ||
22 | */ | ||
23 | #ifndef PING_ARRAY_H | ||
24 | #define PING_ARRAY_H | ||
25 | |||
26 | #include "network.h" | ||
27 | |||
28 | typedef struct { | ||
29 | void *data; | ||
30 | uint32_t length; | ||
31 | uint64_t time; | ||
32 | uint64_t ping_id; | ||
33 | } Ping_Array_Entry; | ||
34 | |||
35 | |||
36 | typedef struct { | ||
37 | Ping_Array_Entry *entries; | ||
38 | |||
39 | uint32_t last_deleted; /* number representing the next entry to be deleted. */ | ||
40 | uint32_t last_added; /* number representing the last entry to be added. */ | ||
41 | uint32_t total_size; /* The length of entries */ | ||
42 | uint32_t timeout; /* The timeout after which entries are cleared. */ | ||
43 | } Ping_Array; | ||
44 | |||
45 | |||
46 | /* Add a data with length to the Ping_Array list and return a ping_id. | ||
47 | * | ||
48 | * return ping_id on success. | ||
49 | * return 0 on failure. | ||
50 | */ | ||
51 | uint64_t ping_array_add(Ping_Array *array, uint8_t *data, uint32_t length); | ||
52 | |||
53 | /* Check if ping_id is valid and not timed out. | ||
54 | * | ||
55 | * On success, copies the data into data of length, | ||
56 | * | ||
57 | * return length of data copied on success. | ||
58 | * return -1 on failure. | ||
59 | */ | ||
60 | int ping_array_check(uint8_t *data, uint32_t length, Ping_Array *array, uint64_t ping_id); | ||
61 | |||
62 | /* Initialize a Ping_Array. | ||
63 | * size represents the total size of the array and should be a power of 2. | ||
64 | * timeout represents the maximum timeout in seconds for the entry. | ||
65 | * | ||
66 | * return 0 on success. | ||
67 | * return -1 on failure. | ||
68 | */ | ||
69 | int ping_array_init(Ping_Array *empty_array, uint32_t size, uint32_t timeout); | ||
70 | |||
71 | /* Free all the allocated memory in a Ping_Array. | ||
72 | */ | ||
73 | void ping_array_free_all(Ping_Array *array); | ||
74 | |||
75 | #endif | ||