Added ping_array, a special efficient array for use in operations

that require sending ping type packets.

Made ping packets use it.

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 \
                         ../toxcore/network.c \
                         ../toxcore/crypto_core.h \
                         ../toxcore/crypto_core.c \
+                        ../toxcore/ping_array.h \
+                        ../toxcore/ping_array.c \
                         ../toxcore/net_crypto.h \
                         ../toxcore/net_crypto.c \
                         ../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 @@
 
 #include "network.h"
 #include "util.h"
+#include "ping_array.h"
 
 #define PING_NUM_MAX 512
 
@@ -43,109 +44,18 @@
 /* Ping newly announced nodes to ping per TIME_TO_PING seconds*/
 #define TIME_TO_PING 3
 
-typedef struct {
-    IP_Port  ip_port;
-    uint64_t id;
-    uint64_t timestamp;
-    uint8_t  shared_key[crypto_box_BEFORENMBYTES];
-} pinged_t;
 
 struct PING {
     DHT *dht;
 
-    pinged_t    pings[PING_NUM_MAX];
-    size_t      num_pings;
-    size_t      pos_pings;
-
+    Ping_Array  ping_array;
     Node_format to_ping[MAX_TO_PING];
     uint64_t    last_to_ping;
 };
 
-static int is_ping_timeout(uint64_t time)
-{
-    return is_timeout(time, PING_TIMEOUT);
-}
-
-static void remove_timeouts(PING *ping)    // O(n)
-{
-    size_t i, id;
-    size_t new_pos = ping->pos_pings;
-    size_t new_num = ping->num_pings;
-
-    // Loop through buffer, oldest first.
-    for (i = 0; i < ping->num_pings; i++) {
-        id = (ping->pos_pings + i) % PING_NUM_MAX;
-
-        if (is_ping_timeout(ping->pings[id].timestamp)) {
-            new_pos++;
-            new_num--;
-        }
-        // Break here because list is sorted.
-        else {
-            break;
-        }
-    }
-
-    ping->num_pings = new_num;
-    ping->pos_pings = new_pos % PING_NUM_MAX;
-}
-
-static uint64_t add_ping(PING *ping, IP_Port ipp, uint8_t *shared_encryption_key)  // O(n)
-{
-    size_t p;
-
-    remove_timeouts(ping);
-
-    /* Remove oldest ping if full buffer. */
-    if (ping->num_pings == PING_NUM_MAX) {
-        ping->num_pings--;
-        ping->pos_pings = (ping->pos_pings + 1) % PING_NUM_MAX;
-    }
-
-    /* Insert new ping at end of list. */
-    p = (ping->pos_pings + ping->num_pings) % PING_NUM_MAX;
-
-    ping->pings[p].ip_port   = ipp;
-    ping->pings[p].timestamp = unix_time();
-    ping->pings[p].id        = random_64b();
-    memcpy(ping->pings[p].shared_key, shared_encryption_key, crypto_box_BEFORENMBYTES);
-
-    ping->num_pings++;
-    return ping->pings[p].id;
-}
-
-/* checks if ip/port or ping_id are already in the list to ping
- * if both are set, both must match, otherwise the set must match
- *
- *  returns 0 if neither is set or no match was found
- *  returns the (index + 1) of the match if one was found
- */
-static int is_pinging(PING *ping, IP_Port ipp, uint64_t ping_id)
-{
-    // O(n) TODO: Replace this with something else.
-
-    /* at least one MUST be set */
-    uint8_t ip_valid = ip_isset(&ipp.ip);
-
-    if (!ip_valid && !ping_id)
-        return 0;
-
-    size_t i;
-
-    remove_timeouts(ping);
-
-    for (i = 0; i < ping->num_pings; i++) {
-        size_t id = (ping->pos_pings + i) % PING_NUM_MAX;
-
-        if (!ping_id || (ping->pings[id].id == ping_id))
-            if (!ip_valid || ipport_equal(&ping->pings[id].ip_port, &ipp))
-                return id + 1;
-    }
-
-    return 0;
-}
 
 #define DHT_PING_SIZE (1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES + sizeof(uint64_t) + crypto_box_MACBYTES)
+#define PING_DATA_SIZE (CLIENT_ID_SIZE + sizeof(IP_Port))
 
 int send_ping_request(PING *ping, IP_Port ipp, uint8_t *client_id)
 {
@@ -153,7 +63,7 @@ int send_ping_request(PING *ping, IP_Port ipp, uint8_t *client_id)
     int       rc;
     uint64_t  ping_id;
 
-    if (is_pinging(ping, ipp, 0) || id_equal(client_id, ping->dht->self_public_key))
+    if (id_equal(client_id, ping->dht->self_public_key))
         return 1;
 
     uint8_t shared_key[crypto_box_BEFORENMBYTES];
@@ -161,7 +71,13 @@ int send_ping_request(PING *ping, IP_Port ipp, uint8_t *client_id)
     // generate key to encrypt ping_id with recipient privkey
     DHT_get_shared_key_sent(ping->dht, shared_key, client_id);
     // Generate random ping_id.
-    ping_id = add_ping(ping, ipp, shared_key);
+    uint8_t data[PING_DATA_SIZE];
+    id_copy(data, client_id);
+    memcpy(data + CLIENT_ID_SIZE, &ipp, sizeof(IP_Port));
+    ping_id = ping_array_add(&ping->ping_array, data, sizeof(data));
+
+    if (ping_id == 0)
+        return 1;
 
     pk[0] = NET_PACKET_PING_REQUEST;
     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
     if (id_equal(packet + 1, ping->dht->self_public_key))
         return 1;
 
-    int ping_index = is_pinging(ping, source, 0);
+    uint8_t shared_key[crypto_box_BEFORENMBYTES];
 
-    if (!ping_index)
-        return 1;
+    // generate key to encrypt ping_id with recipient privkey
+    DHT_get_shared_key_sent(ping->dht, shared_key, packet + 1);
 
-    --ping_index;
     // Decrypt ping_id
-    rc = decrypt_data_symmetric(ping->pings[ping_index].shared_key,
+    rc = decrypt_data_symmetric(shared_key,
                                 packet + 1 + CLIENT_ID_SIZE,
                                 packet + 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES,
                                 sizeof(ping_id) + crypto_box_MACBYTES,
@@ -268,11 +183,21 @@ static int handle_ping_response(void *_dht, IP_Port source, uint8_t *packet, uin
     if (rc != sizeof(ping_id))
         return 1;
 
-    if (ping->pings[ping_index].id != ping_id)
+    uint8_t data[PING_DATA_SIZE];
+
+    if (ping_array_check(data, sizeof(data), &ping->ping_array, ping_id) != sizeof(data))
         return 1;
 
-    addto_lists(dht, source, packet + 1);
+    if (!id_equal(packet + 1, data))
+        return 1;
+
+    IP_Port ipp;
+    memcpy(&ipp, data + CLIENT_ID_SIZE, sizeof(IP_Port));
 
+    if (!ipport_equal(&ipp, &source))
+        return 1;
+
+    addto_lists(dht, source, packet + 1);
     return 0;
 }
 
@@ -348,6 +273,11 @@ PING *new_ping(DHT *dht)
     if (ping == NULL)
         return NULL;
 
+    if (ping_array_init(&ping->ping_array, PING_NUM_MAX, PING_TIMEOUT) != 0) {
+        free(ping);
+        return NULL;
+    }
+
     ping->dht = dht;
     networking_registerhandler(ping->dht->net, NET_PACKET_PING_REQUEST, &handle_ping_request, dht);
     networking_registerhandler(ping->dht->net, NET_PACKET_PING_RESPONSE, &handle_ping_response, dht);
@@ -359,6 +289,7 @@ void kill_ping(PING *ping)
 {
     networking_registerhandler(ping->dht->net, NET_PACKET_PING_REQUEST, NULL, NULL);
     networking_registerhandler(ping->dht->net, NET_PACKET_PING_RESPONSE, NULL, NULL);
+    ping_array_free_all(&ping->ping_array);
 
     free(ping);
 }
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 @@
+/* ping_array.c
+ *
+ * Implementation of an efficient array to store that we pinged something.
+ *
+ *
+ *  Copyright (C) 2014 Tox project All Rights Reserved.
+ *
+ *  This file is part of Tox.
+ *
+ *  Tox is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation, either version 3 of the License, or
+ *  (at your option) any later version.
+ *
+ *  Tox is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with Tox.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include "ping_array.h"
+#include "crypto_core.h"
+#include "util.h"
+
+static void clear_entry(Ping_Array *array, uint32_t index)
+{
+    free(array->entries[index].data);
+    array->entries[index].data = NULL;
+    array->entries[index].length =
+        array->entries[index].time =
+            array->entries[index].ping_id = 0;
+}
+
+/* Clear timed out entries.
+ */
+static void ping_array_clear_timedout(Ping_Array *array)
+{
+    while (array->last_deleted != array->last_added) {
+        uint32_t index = array->last_deleted % array->total_size;
+
+        if (!is_timeout(array->entries[index].time, array->timeout))
+            break;
+
+        clear_entry(array, index);
+        ++array->last_deleted;
+    }
+}
+
+/* Add a data with length to the Ping_Array list and return a ping_id.
+ *
+ * return ping_id on success.
+ * return 0 on failure.
+ */
+uint64_t ping_array_add(Ping_Array *array, uint8_t *data, uint32_t length)
+{
+    ping_array_clear_timedout(array);
+    uint32_t index = array->last_added % array->total_size;
+
+    if (array->entries[index].data != NULL) {
+        array->last_deleted = array->last_added - array->total_size;
+        clear_entry(array, index);
+    }
+
+    array->entries[index].data = malloc(length);
+
+    if (array->entries[index].data == NULL)
+        return 0;
+
+    memcpy(array->entries[index].data, data, length);
+    array->entries[index].length = length;
+    array->entries[index].time = unix_time();
+    ++array->last_added;
+    uint64_t ping_id = random_64b();
+    ping_id /= array->total_size;
+    ping_id *= array->total_size;
+    ping_id += index;
+
+    if (ping_id == 0)
+        ping_id += array->total_size;
+
+    array->entries[index].ping_id = ping_id;
+    return ping_id;
+}
+
+
+/* Check if ping_id is valid and not timed out.
+ *
+ * On success, copies the data into data of length,
+ *
+ * return length of data copied on success.
+ * return -1 on failure.
+ */
+int ping_array_check(uint8_t *data, uint32_t length, Ping_Array *array, uint64_t ping_id)
+{
+    if (ping_id == 0)
+        return -1;
+
+    uint32_t index = ping_id % array->total_size;
+
+    if (array->entries[index].ping_id != ping_id)
+        return -1;
+
+    if (is_timeout(array->entries[index].time, array->timeout))
+        return -1;
+
+    if (array->entries[index].length > length)
+        return -1;
+
+    if (array->entries[index].data == NULL)
+        return -1;
+
+    memcpy(data, array->entries[index].data, array->entries[index].length);
+    uint32_t len = array->entries[index].length;
+    clear_entry(array, index);
+    return len;
+}
+
+/* Initialize a Ping_Array.
+ * size represents the total size of the array and should be a power of 2.
+ * timeout represents the maximum timeout in seconds for the entry.
+ *
+ * return 0 on success.
+ * return -1 on failure.
+ */
+int ping_array_init(Ping_Array *empty_array, uint32_t size, uint32_t timeout)
+{
+    if (size == 0 || timeout == 0 || empty_array == NULL)
+        return -1;
+
+    empty_array->entries = malloc(size * sizeof(Ping_Array_Entry));
+
+    if (empty_array->entries == NULL)
+        return -1;
+
+    empty_array->last_deleted = empty_array->last_added = 0;
+    empty_array->total_size = size;
+    empty_array->timeout = timeout;
+    return 0;
+}
+
+/* Free all the allocated memory in a Ping_Array.
+ */
+void ping_array_free_all(Ping_Array *array)
+{
+    while (array->last_deleted != array->last_added) {
+        uint32_t index = array->last_deleted % array->total_size;
+        clear_entry(array, index);
+        ++array->last_deleted;
+    }
+
+    free(array->entries);
+    array->entries = NULL;
+}
+
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 @@
+/* ping_array.h
+ *
+ * Implementation of an efficient array to store that we pinged something.
+ *
+ *  Copyright (C) 2013 Tox project All Rights Reserved.
+ *
+ *  This file is part of Tox.
+ *
+ *  Tox is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation, either version 3 of the License, or
+ *  (at your option) any later version.
+ *
+ *  Tox is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with Tox.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+#ifndef PING_ARRAY_H
+#define PING_ARRAY_H
+
+#include "network.h"
+
+typedef struct {
+    void *data;
+    uint32_t length;
+    uint64_t time;
+    uint64_t ping_id;
+} Ping_Array_Entry;
+
+
+typedef struct {
+    Ping_Array_Entry *entries;
+
+    uint32_t last_deleted; /* number representing the next entry to be deleted. */
+    uint32_t last_added; /* number representing the last entry to be added. */
+    uint32_t total_size; /* The length of entries */
+    uint32_t timeout; /* The timeout after which entries are cleared. */
+} Ping_Array;
+
+
+/* Add a data with length to the Ping_Array list and return a ping_id.
+ *
+ * return ping_id on success.
+ * return 0 on failure.
+ */
+uint64_t ping_array_add(Ping_Array *array, uint8_t *data, uint32_t length);
+
+/* Check if ping_id is valid and not timed out.
+ *
+ * On success, copies the data into data of length,
+ * 
+ * return length of data copied on success.
+ * return -1 on failure.
+ */
+int ping_array_check(uint8_t *data, uint32_t length, Ping_Array *array, uint64_t ping_id);
+
+/* Initialize a Ping_Array.
+ * size represents the total size of the array and should be a power of 2.
+ * timeout represents the maximum timeout in seconds for the entry.
+ *
+ * return 0 on success.
+ * return -1 on failure.
+ */
+int ping_array_init(Ping_Array *empty_array, uint32_t size, uint32_t timeout);
+
+/* Free all the allocated memory in a Ping_Array.
+ */
+void ping_array_free_all(Ping_Array *array);
+
+#endif