1 /* SPDX-License-Identifier: GPL-3.0-or-later
2 * Copyright © 2016-2018 The TokTok team.
3 * Copyright © 2014 Tox project.
4 */
5
6 /*
7 * Implementation of an efficient array to store that we pinged something.
8 */
9 #ifdef HAVE_CONFIG_H
10 #include "config.h"
11 #endif
12
13 #include "ping_array.h"
14
15 #include <stdlib.h>
16 #include <string.h>
17
18 #include "crypto_core.h"
19 #include "mono_time.h"
20 #include "util.h"
21
22 typedef struct Ping_Array_Entry {
23 void *data;
24 uint32_t length;
25 uint64_t time;
26 uint64_t ping_id;
27 } Ping_Array_Entry;
28
29 struct Ping_Array {
30 Ping_Array_Entry *entries;
31
32 uint32_t last_deleted; /* number representing the next entry to be deleted. */
33 uint32_t last_added; /* number representing the last entry to be added. */
34 uint32_t total_size; /* The length of entries */
35 uint32_t timeout; /* The timeout after which entries are cleared. */
36 };
37
ping_array_new(uint32_t size,uint32_t timeout)38 Ping_Array *ping_array_new(uint32_t size, uint32_t timeout)
39 {
40 if (size == 0 || timeout == 0) {
41 return nullptr;
42 }
43
44 if ((size & (size - 1)) != 0) {
45 // Not a power of 2.
46 return nullptr;
47 }
48
49 Ping_Array *const empty_array = (Ping_Array *)calloc(1, sizeof(Ping_Array));
50
51 if (empty_array == nullptr) {
52 return nullptr;
53 }
54
55 empty_array->entries = (Ping_Array_Entry *)calloc(size, sizeof(Ping_Array_Entry));
56
57 if (empty_array->entries == nullptr) {
58 free(empty_array);
59 return nullptr;
60 }
61
62 empty_array->last_deleted = 0;
63 empty_array->last_added = 0;
64 empty_array->total_size = size;
65 empty_array->timeout = timeout;
66 return empty_array;
67 }
68
clear_entry(Ping_Array * array,uint32_t index)69 static void clear_entry(Ping_Array *array, uint32_t index)
70 {
71 const Ping_Array_Entry empty = {nullptr};
72 free(array->entries[index].data);
73 array->entries[index] = empty;
74 }
75
ping_array_kill(Ping_Array * array)76 void ping_array_kill(Ping_Array *array)
77 {
78 if (array == nullptr) {
79 return;
80 }
81
82 while (array->last_deleted != array->last_added) {
83 const uint32_t index = array->last_deleted % array->total_size;
84 clear_entry(array, index);
85 ++array->last_deleted;
86 }
87
88 free(array->entries);
89 free(array);
90 }
91
92 /* Clear timed out entries.
93 */
ping_array_clear_timedout(Ping_Array * array,const Mono_Time * mono_time)94 static void ping_array_clear_timedout(Ping_Array *array, const Mono_Time *mono_time)
95 {
96 while (array->last_deleted != array->last_added) {
97 const uint32_t index = array->last_deleted % array->total_size;
98
99 if (!mono_time_is_timeout(mono_time, array->entries[index].time, array->timeout)) {
100 break;
101 }
102
103 clear_entry(array, index);
104 ++array->last_deleted;
105 }
106 }
107
ping_array_add(Ping_Array * array,const Mono_Time * mono_time,const uint8_t * data,uint32_t length)108 uint64_t ping_array_add(Ping_Array *array, const Mono_Time *mono_time, const uint8_t *data,
109 uint32_t length)
110 {
111 ping_array_clear_timedout(array, mono_time);
112 const uint32_t index = array->last_added % array->total_size;
113
114 if (array->entries[index].data != nullptr) {
115 array->last_deleted = array->last_added - array->total_size;
116 clear_entry(array, index);
117 }
118
119 array->entries[index].data = malloc(length);
120
121 if (array->entries[index].data == nullptr) {
122 return 0;
123 }
124
125 memcpy(array->entries[index].data, data, length);
126 array->entries[index].length = length;
127 array->entries[index].time = mono_time_get(mono_time);
128 ++array->last_added;
129 uint64_t ping_id = random_u64();
130 ping_id /= array->total_size;
131 ping_id *= array->total_size;
132 ping_id += index;
133
134 if (ping_id == 0) {
135 ping_id += array->total_size;
136 }
137
138 array->entries[index].ping_id = ping_id;
139 return ping_id;
140 }
141
ping_array_check(Ping_Array * array,const Mono_Time * mono_time,uint8_t * data,size_t length,uint64_t ping_id)142 int32_t ping_array_check(Ping_Array *array, const Mono_Time *mono_time, uint8_t *data,
143 size_t length, uint64_t ping_id)
144 {
145 if (ping_id == 0) {
146 return -1;
147 }
148
149 const uint32_t index = ping_id % array->total_size;
150
151 if (array->entries[index].ping_id != ping_id) {
152 return -1;
153 }
154
155 if (mono_time_is_timeout(mono_time, array->entries[index].time, array->timeout)) {
156 return -1;
157 }
158
159 if (array->entries[index].length > length) {
160 return -1;
161 }
162
163 // TODO(iphydf): This can't happen? If it indeed can't, turn it into an assert.
164 if (array->entries[index].data == nullptr) {
165 return -1;
166 }
167
168 memcpy(data, array->entries[index].data, array->entries[index].length);
169 const uint32_t len = array->entries[index].length;
170 clear_entry(array, index);
171 return len;
172 }
173