1 /*
2 * aprsc
3 *
4 * (c) Heikki Hannikainen, OH7LZB <hessu@hes.iki.fi>
5 *
6 * This program is licensed under the BSD license, which can be found
7 * in the file LICENSE.
8 *
9 */
10
11 /*
12 * The clients heard list contains a list of stations heard by
13 * a given station. It's used for message routing by the
14 * message destination callsign.
15 *
16 * The module also maintains a list of callsigns which have transmitted
17 * messages to a given client. The list is used to pass courtesy
18 * positions to the client.
19 *
20 * The heard list is only touched by the worker thread operating
21 * on that client socket, so it doesn't need any locking at all.
22 *
23 * Igates typically have up to ~300 "heard" stations at any given
24 * moment, so we use a hash table with 16 buckets, about 18 calls
25 * in each bucket. Store and check the hash value before doing
26 * string comparisons.
27 */
28
29 #include <strings.h>
30 #include <string.h>
31
32 #include "client_heard.h"
33 #include "hlog.h"
34 #include "config.h"
35 #include "hmalloc.h"
36 #include "cellmalloc.h"
37 #include "keyhash.h"
38
39 #define MAX_HEARD_PER_CLIENT 2000
40
41 //#define HEARD_DEBUG
42
43 #ifdef HEARD_DEBUG
44 #define DLOG(level, fmt, ...) \
45 do { hlog(level, fmt, __VA_ARGS__); } while (0)
46 #else
47 #define DLOG(fmt, ...)
48 #endif
49
50 #ifndef _FOR_VALGRIND_
51 cellarena_t *client_heard_cells;
52 #endif
53
54
55 /*
56 * Update the heard list, either update timestamp of a heard
57 * callsign or insert a new entry
58 */
59
heard_list_update(struct client_t * c,char * call,int call_len,time_t t,struct client_heard_t ** list,int * entrycount,char * which)60 static void heard_list_update(struct client_t *c, char *call, int call_len, time_t t, struct client_heard_t **list, int *entrycount, char *which)
61 {
62 struct client_heard_t *h;
63 uint32_t hash, idx;
64 int i;
65
66 hash = keyhashuc(call, call_len, 0);
67 idx = hash;
68 // "CLIENT_HEARD_BUCKETS" is 16..
69 idx ^= (idx >> 16);
70 //idx ^= (idx >> 8);
71 //idx ^= (idx >> 4);
72 i = idx % CLIENT_HEARD_BUCKETS;
73
74 DLOG(LOG_DEBUG, "heard_list_update fd %d %s: updating %.*s (hash %u i %d)", c->fd, which, call_len, call, hash, i);
75
76 for (h = list[i]; (h); h = h->next) {
77 if (h->hash == hash && call_len == h->call_len
78 && strncasecmp(call, h->callsign, h->call_len) == 0) {
79 // OK, found it from the list
80
81 //DLOG(LOG_DEBUG, "heard_list_update fd %d %s: found, updating %.*s", c->fd, which, call_len, call);
82 h->last_heard = t;
83
84 /* Because of digipeating we'll see the same station
85 * really quickly again, and the less active stations are, well, less active,
86 * let's move it in the beginning of the list to find it quicker.
87 */
88
89 if (list[i] != h) {
90 //DLOG(LOG_DEBUG, "heard_list_update fd %d %s: moving to front %.*s", c->fd, which, call_len, call);
91 *h->prevp = h->next;
92 if (h->next)
93 h->next->prevp = h->prevp;
94
95 h->next = list[i];
96 h->prevp = &list[i];
97 if (h->next)
98 h->next->prevp = &h->next;
99 list[i] = h;
100 }
101
102 return;
103 }
104 }
105
106 /* sanity limit */
107 if (*entrycount >= MAX_HEARD_PER_CLIENT)
108 return;
109
110 /* Not found, insert. */
111 DLOG(LOG_DEBUG, "heard_list_update fd %d %s: inserting %.*s", c->fd, which, call_len, call);
112 #ifndef _FOR_VALGRIND_
113 h = cellmalloc(client_heard_cells);
114 if (!h) {
115 DLOG(LOG_ERR, "heard_list_update: cellmalloc failed");
116 return;
117 }
118 #else
119 h = hmalloc(sizeof(*h));
120 #endif
121 h->hash = hash;
122 strncpy(h->callsign, call, call_len);
123 h->callsign[sizeof(h->callsign)-1] = 0;
124 h->call_len = call_len;
125 h->last_heard = t;
126
127 /* insert in beginning of linked list */
128 h->next = list[i];
129 h->prevp = &list[i];
130 if (h->next)
131 h->next->prevp = &h->next;
132 list[i] = h;
133 *entrycount = *entrycount + 1;
134 }
135
client_heard_update(struct client_t * c,struct pbuf_t * pb)136 void client_heard_update(struct client_t *c, struct pbuf_t *pb)
137 {
138 heard_list_update(c, pb->data, pb->srccall_end - pb->data, pb->t, c->client_heard, &c->client_heard_count, "heard");
139 }
140
client_courtesy_update(struct client_t * c,struct pbuf_t * pb)141 void client_courtesy_update(struct client_t *c, struct pbuf_t *pb)
142 {
143 heard_list_update(c, pb->data, pb->srccall_end - pb->data, pb->t, c->client_courtesy, &c->client_courtesy_count, "courtesy");
144 }
145
146 /*
147 * Check for and optionally remove a callsign from a heard list.
148 *
149 * NOTE: THIS IS THE MOST FREQUENTLY CALLED FUNCTION IN THE APPLICATION.
150 *
151 * It's called more than once per packet per filtered client,
152 * currently about 1.24 * number-of-filtered-clients * packets.
153 * Not very scalable, as the number of packets goes up with the amount of
154 * clients on the network, O(N^2) complexity.
155 * A single tree keyed by the callsign and containing a list of clients
156 * having heard the callsign, looked up once per packet, would be O(N).
157 * For the time being this will work fine.
158 *
159 * Do not bloat.
160 */
161
heard_find(struct client_heard_t ** list,int * entrycount,const char * callsign,int call_len,uint32_t hash,int drop_if_found)162 static int heard_find(struct client_heard_t **list, int *entrycount, const char *callsign, int call_len, uint32_t hash, int drop_if_found)
163 {
164 struct client_heard_t *h;
165 uint32_t idx;
166
167 // "CLIENT_HEARD_BUCKETS" is 16..
168 /*
169 idx = hash;
170 idx ^= (idx >> 16);
171 //idx ^= (idx >> 8);
172 //idx ^= (idx >> 4);
173 idx = idx % CLIENT_HEARD_BUCKETS;
174 */
175 idx = (hash ^ (hash >> 16)) % CLIENT_HEARD_BUCKETS;
176
177 //DLOG(LOG_DEBUG, "heard_find fd %d %s: checking for %.*s (hash %u idx %d)", c->fd, which, call_len, callsign, hash, idx);
178
179 for (h = list[idx]; (h); h = h->next) {
180 if (h->hash == hash && call_len == h->call_len
181 && strncasecmp(callsign, h->callsign, h->call_len) == 0) {
182 /* OK, found it from the list. */
183 //DLOG(LOG_DEBUG, "heard_find: found %.*s%s", call_len, callsign, (drop_if_found) ? " (dropping)" : "");
184
185 if (drop_if_found) {
186 //DLOG(LOG_DEBUG, "heard_find: dropping %.*s%s", call_len, callsign, (drop_if_found) ? " (dropping)" : "");
187 *h->prevp = h->next;
188 if (h->next)
189 h->next->prevp = h->prevp;
190
191 #ifndef _FOR_VALGRIND_
192 cellfree(client_heard_cells, h);
193 #else
194 hfree(h);
195 #endif
196 *entrycount = *entrycount -1;
197 }
198
199 return 1;
200 }
201 }
202
203 return 0;
204 }
205
client_heard_check(struct client_t * c,const char * callsign,int call_len,uint32_t hash)206 int client_heard_check(struct client_t *c, const char *callsign, int call_len, uint32_t hash)
207 {
208 return heard_find(c->client_heard, &c->client_heard_count,
209 callsign, call_len, hash,
210 0);
211 }
212
client_courtesy_needed(struct client_t * c,struct pbuf_t * pb)213 int client_courtesy_needed(struct client_t *c, struct pbuf_t *pb)
214 {
215 return heard_find(c->client_courtesy, &c->client_courtesy_count,
216 pb->srcname, pb->srcname_len, pb->srcname_hash,
217 1);
218 }
219
220 /*
221 * Free the whole client heard list
222 */
223
heard_free_single(struct client_heard_t ** list)224 static void heard_free_single(struct client_heard_t **list)
225 {
226 int i;
227 struct client_heard_t *n, *h;
228
229 for (i = 0; i < CLIENT_HEARD_BUCKETS; i++) {
230 h = list[i];
231 while (h) {
232 n = h->next;
233 #ifndef _FOR_VALGRIND_
234 cellfree(client_heard_cells, h);
235 #else
236 hfree(h);
237 #endif
238 h = n;
239 }
240 list[i] = NULL;
241 }
242 }
243
client_heard_free(struct client_t * c)244 void client_heard_free(struct client_t *c)
245 {
246 heard_free_single(c->client_heard);
247 heard_free_single(c->client_courtesy);
248
249 c->client_heard_count = 0;
250 c->client_courtesy_count = 0;
251 }
252
253 /*
254 * Expire old entries from client_heard list
255 */
256
heard_expire_single(struct client_heard_t ** list,int * entrycount,int storetime)257 static void heard_expire_single(struct client_heard_t **list, int *entrycount, int storetime)
258 {
259 struct client_heard_t *n, *h;
260 int expire_below = tick - storetime;
261 int i;
262
263 for (i = 0; i < CLIENT_HEARD_BUCKETS; i++) {
264 h = list[i];
265 while (h) {
266 n = h->next;
267 if (h->last_heard < expire_below || h->last_heard > tick) {
268 DLOG(LOG_DEBUG, "heard_expire_single: expiring %.*s (%ul below %ul)", h->call_len, h->callsign, h->last_heard, expire_below);
269
270 *h->prevp = h->next;
271 if (h->next)
272 h->next->prevp = h->prevp;
273 #ifndef _FOR_VALGRIND_
274 cellfree(client_heard_cells, h);
275 #else
276 hfree(h);
277 #endif
278 *entrycount = *entrycount -1;
279 }
280 h = n;
281 }
282 }
283 }
284
client_heard_expire(struct client_t * c)285 void client_heard_expire(struct client_t *c)
286 {
287 heard_expire_single(c->client_heard, &c->client_heard_count, heard_list_storetime);
288 heard_expire_single(c->client_courtesy, &c->client_courtesy_count, courtesy_list_storetime);
289 }
290
291
client_heard_init(void)292 void client_heard_init(void)
293 {
294 #ifndef _FOR_VALGRIND_
295 client_heard_cells = cellinit( "client_heard",
296 sizeof(struct client_heard_t),
297 __alignof__(struct client_heard_t),
298 CELLMALLOC_POLICY_FIFO,
299 512 /* 512 KB at the time */, 0 /* minfree */ );
300 /* 512 KB arena size -> about 18k entries per single arena */
301 #endif
302 }
303
304 /*
305 * Generate JSON tree containing a client_heard_t list
306 */
307
client_heard_json(struct client_heard_t ** list)308 struct cJSON *client_heard_json(struct client_heard_t **list)
309 {
310 struct client_heard_t *h;
311 int i;
312 cJSON *j = cJSON_CreateArray();
313
314 for (i = 0; i < CLIENT_HEARD_BUCKETS; i++) {
315 h = list[i];
316 while (h) {
317 cJSON_AddItemToArray(j, cJSON_CreateString(h->callsign));
318 h = h->next;
319 }
320 }
321
322 return j;
323 }
324
325 /*
326 * Load client_heard_t list from a JSON dump
327 */
328
client_heard_json_load(struct client_t * c,cJSON * dump)329 int client_heard_json_load(struct client_t *c, cJSON *dump)
330 {
331 int i, len;
332 cJSON *h;
333 time_t t = tick;
334
335 len = cJSON_GetArraySize(dump);
336
337 for (i = 0; i < len; i++) {
338 h = cJSON_GetArrayItem(dump, i);
339 if (!h || !h->valuestring)
340 continue;
341 heard_list_update(c, h->valuestring, strlen(h->valuestring), t, c->client_heard, &c->client_heard_count, "heard");
342
343 }
344
345 return i;
346 }
347
348 /*
349 * cellmalloc status
350 */
351 #ifndef _FOR_VALGRIND_
client_heard_cell_stats(struct cellstatus_t * cellst)352 void client_heard_cell_stats(struct cellstatus_t *cellst)
353 {
354 /* this is not quite thread safe, but is OK since the
355 * results are only used for statistics (no-one will
356 * notice if they don't quite add up always)
357 */
358 cellstatus(client_heard_cells, cellst);
359 }
360 #endif
361
362
363