1 /*
2 * aprsc
3 *
4 * (c) Matti Aarnio, OH2MQK, <oh2mqk@sral.fi>
5 *
6 * This program is licensed under the BSD license, which can be found
7 * in the file LICENSE.
8 *
9 */
10
11 #include <string.h>
12 #include <strings.h>
13 #include <ctype.h>
14 #include <math.h>
15 #include <errno.h>
16
17 #include "hlog.h"
18 #include "worker.h"
19 #include "config.h"
20 #include "cellmalloc.h"
21 #include "historydb.h"
22 #include "hmalloc.h"
23 #include "keyhash.h"
24 #include "cJSON.h"
25
26 #ifndef _FOR_VALGRIND_
27 cellarena_t *historydb_cells;
28 #endif
29
30
31 /* OPTIMIZE: Possibly multiple parallel locks (like 1000 ?) that keep
32 //control on a subset of historydb hash bucket chains ???
33 // Note: mutex lock size is about 1/4 of rwlock size...
34 */
35
36 rwlock_t historydb_rwlock;
37
38 #define HISTORYDB_HASH_MODULO 8192 /* fold bits: 13 / 26 */
39 struct history_cell_t *historydb_hash[HISTORYDB_HASH_MODULO];
40
41 /* monitor counters and gauges */
42 long historydb_inserts;
43 long historydb_lookups;
44 long historydb_hashmatches;
45 long historydb_keymatches;
46 long historydb_cellgauge;
47 long historydb_noposcount;
48
49 long historydb_cleanup_cleaned;
50
historydb_nopos(void)51 void historydb_nopos(void) {} /* profiler call counter items */
historydb_nointerest(void)52 void historydb_nointerest(void) {}
historydb_hashmatch(void)53 void historydb_hashmatch(void) {}
historydb_keymatch(void)54 void historydb_keymatch(void) {}
historydb_dataupdate(void)55 void historydb_dataupdate(void) {}
56
57
historydb_init(void)58 void historydb_init(void)
59 {
60 rwl_init(&historydb_rwlock);
61
62 // printf("historydb_init() sizeof(mutex)=%d sizeof(rwlock)=%d\n",
63 // sizeof(pthread_mutex_t), sizeof(rwlock_t));
64
65 #ifndef _FOR_VALGRIND_
66 historydb_cells = cellinit( "historydb",
67 sizeof(struct history_cell_t),
68 __alignof__(struct history_cell_t),
69 CELLMALLOC_POLICY_FIFO,
70 2048 /* 2 MB */,
71 0 /* minfree */ );
72 #endif
73 }
74
75 /* Called only under WR-LOCK */
historydb_free(struct history_cell_t * p)76 static void historydb_free(struct history_cell_t *p)
77 {
78 #ifndef _FOR_VALGRIND_
79 cellfree( historydb_cells, p );
80 #else
81 hfree(p);
82 #endif
83 --historydb_cellgauge;
84 }
85
86 /* Called only under WR-LOCK */
historydb_alloc(void)87 static struct history_cell_t *historydb_alloc(void)
88 {
89 ++historydb_cellgauge;
90 #ifndef _FOR_VALGRIND_
91 return cellmalloc( historydb_cells );
92 #else
93 return hmalloc(sizeof(struct history_cell_t));
94 #endif
95 }
96
97 /*
98 * The historydb_atend() does exist primarily to make valgrind
99 * happy about lost memory object tracking.
100 */
historydb_atend(void)101 void historydb_atend(void)
102 {
103 int i;
104 struct history_cell_t *hp, *hp2;
105 for (i = 0; i < HISTORYDB_HASH_MODULO; ++i) {
106 hp = historydb_hash[i];
107 while (hp) {
108 hp2 = hp->next;
109 historydb_free(hp);
110 hp = hp2;
111 }
112 historydb_hash[i] = NULL;
113 }
114 }
115
historydb_dump_entry(FILE * fp,struct history_cell_t * hp)116 static int historydb_dump_entry(FILE *fp, struct history_cell_t *hp)
117 {
118 int klen;
119 char key[CALLSIGNLEN_MAX+1];
120
121 /* create a null-terminated key string */
122 klen = (hp->keylen < CALLSIGNLEN_MAX) ? hp->keylen : CALLSIGNLEN_MAX;
123 strncpy(key, hp->key, klen);
124 key[klen] = 0;
125
126 cJSON *js = cJSON_CreateObject();
127 cJSON_AddNumberToObject(js, "arrivaltime", hp->arrivaltime);
128 cJSON_AddStringToObject(js, "key", key);
129 cJSON_AddNumberToObject(js, "packettype", hp->packettype);
130 cJSON_AddNumberToObject(js, "flags", hp->flags);
131 cJSON_AddNumberToObject(js, "lat", (double)hp->lat);
132 cJSON_AddNumberToObject(js, "lon", (double)hp->lon);
133
134 /* the tree is built, print it out to a malloc'ed string */
135 char *out = cJSON_PrintUnformatted(js);
136 cJSON_Delete(js);
137 klen = fprintf(fp, "%s\n", out);
138 hfree(out);
139
140 if (klen < 0)
141 hlog(LOG_ERR, "historydb_dump_entry failed to write entry: %s", strerror(errno));
142
143 return klen;
144 }
145
historydb_load_entry(char * s)146 static int historydb_load_entry(char *s)
147 {
148 cJSON *j;
149 cJSON *arrivaltime, *key, *packettype, *flags, *lat, *lon;
150 struct history_cell_t *cp;
151 int keylen;
152 uint32_t h1, h2, i;
153 time_t expirytime = tick - lastposition_storetime;
154
155 j = cJSON_Parse(s);
156 if (!j) {
157 hlog(LOG_ERR, "historydb_load_entry JSON decode failed: %s", s);
158 return -1;
159 }
160
161 arrivaltime = cJSON_GetObjectItem(j, "arrivaltime");
162 key = cJSON_GetObjectItem(j, "key");
163 packettype = cJSON_GetObjectItem(j, "packettype");
164 flags = cJSON_GetObjectItem(j, "flags");
165 lat = cJSON_GetObjectItem(j, "lat");
166 lon = cJSON_GetObjectItem(j, "lon");
167
168 /* make sure all required keys are present */
169 if (!((arrivaltime) && (key) && (packettype) && (flags) && (lat) && (lon)))
170 goto fail;
171
172 /* check types of items */
173 if (arrivaltime->type != cJSON_Number
174 || key->type != cJSON_String
175 || packettype->type != cJSON_Number
176 || flags->type != cJSON_Number
177 || lat->type != cJSON_Number
178 || lon->type != cJSON_Number) {
179 goto fail;
180 }
181
182 if (arrivaltime->valueint < expirytime) {
183 /* too old */
184 goto fail;
185 }
186
187 keylen = strlen(key->valuestring);
188
189 /* ok, we're going to add this one - allocate, fill and push */
190 cp = historydb_alloc();
191 if (!cp) {
192 hlog(LOG_ERR, "historydb_load_entry: cellmalloc failed");
193 goto fail;
194 }
195
196 /* calculate hash */
197 h1 = keyhash(key->valuestring, keylen, 0);
198 h2 = h1 ^ (h1 >> 13) ^ (h1 >> 26); /* fold hash bits.. */
199 i = h2 % HISTORYDB_HASH_MODULO;
200
201 memcpy(cp->key, key->valuestring, keylen);
202 cp->key[keylen] = 0; /* zero terminate */
203 cp->keylen = keylen;
204 cp->hash1 = h1;
205
206 cp->lat = lat->valuedouble;
207 cp->coslat = cosf(cp->lat);
208 cp->lon = lon->valuedouble;
209 cp->arrivaltime = arrivaltime->valueint;
210 cp->packettype = packettype->valueint;
211 cp->flags = flags->valueint;
212
213 /* ok, insert it in the hash table */
214 cp->next = historydb_hash[i];
215 historydb_hash[i] = cp;
216
217 cJSON_Delete(j);
218 return 1;
219
220 fail:
221 cJSON_Delete(j);
222
223 return 0;
224 }
225
historydb_dump(FILE * fp)226 int historydb_dump(FILE *fp)
227 {
228 /* Dump the historydb out on text format */
229 int i;
230 struct history_cell_t *hp;
231 time_t expirytime = tick - lastposition_storetime;
232 int ret = 0;
233
234 /* multiple locks ? one for each bucket, or for a subset of buckets ? */
235 rwl_rdlock(&historydb_rwlock);
236
237 for ( i = 0; i < HISTORYDB_HASH_MODULO; ++i ) {
238 hp = historydb_hash[i];
239 for ( ; hp ; hp = hp->next )
240 if (hp->arrivaltime > expirytime) {
241 if (historydb_dump_entry(fp, hp) < 0) {
242 ret = -1;
243 goto fail;
244 }
245 }
246 }
247
248 fail:
249 /* Free the lock */
250 rwl_rdunlock(&historydb_rwlock);
251
252 return ret;
253 }
254
historydb_load(FILE * fp)255 int historydb_load(FILE *fp)
256 {
257 char *s;
258 int n = 0;
259 int ok = 0;
260 char buf[32768];
261
262 rwl_wrlock(&historydb_rwlock);
263
264 while ((s = fgets(buf, sizeof(buf), fp))) {
265 // squelch warning: the json file is read from disk, written by ourself when starting live upgrade
266 // coverity[tainted_data]
267 if (historydb_load_entry(s) > 0)
268 ok++;
269 n++;
270 }
271
272 rwl_wrunlock(&historydb_rwlock);
273
274 hlog(LOG_INFO, "Loaded %d of %d historydb entries.", ok, n);
275
276 return 0;
277 }
278
279 /* insert... */
280
historydb_insert(struct pbuf_t * pb)281 int historydb_insert(struct pbuf_t *pb)
282 {
283 int i;
284 uint32_t h1, h2;
285 int isdead = 0, keylen;
286 struct history_cell_t **hp, *cp, *cp1;
287
288 time_t expirytime = tick - lastposition_storetime;
289
290 char keybuf[CALLSIGNLEN_MAX+2];
291 char *s;
292
293 if (!(pb->flags & F_HASPOS)) {
294 ++historydb_noposcount;
295 historydb_nopos(); /* debug thing -- profiling counter */
296 return -1; /* No positional data... */
297 }
298
299 /* NOTE: Parser does set on MESSAGES the RECIPIENTS
300 ** location if such is known! We do not want them...
301 ** .. and several other cases where packet has no
302 ** positional data in it, but source callsign may
303 ** have previous entry with data.
304 */
305
306 /* NOTE2: We could use pb->srcname, and pb->srcname_len here,
307 ** but then we would not know if this is a "kill-item"
308 */
309
310 keybuf[CALLSIGNLEN_MAX] = 0;
311 if (pb->packettype & T_OBJECT) {
312 /* Pick object name ";item *" */
313 memcpy( keybuf, pb->info_start+1, CALLSIGNLEN_MAX+1);
314 keybuf[CALLSIGNLEN_MAX+1] = 0;
315 s = strchr(keybuf, '*');
316 if (s) *s = 0;
317 else {
318 s = strchr(keybuf, '_'); // kill an object!
319 if (s) {
320 *s = 0;
321 isdead = 1;
322 }
323 }
324 s = keybuf + strlen(keybuf);
325 for ( ; s > keybuf; --s ) { // tail space padded..
326 if (*s == ' ') *s = ' ';
327 else break;
328 }
329
330 } else if (pb->packettype & T_ITEM) {
331 // Pick item name ") . . . !" or ") . . . _"
332 memcpy( keybuf, pb->info_start+1, CALLSIGNLEN_MAX+1);
333 keybuf[CALLSIGNLEN_MAX+1] = 0;
334 s = strchr(keybuf, '!');
335 if (s) *s = 0;
336 else {
337 s = strchr(keybuf, '_'); // kill an item!
338 if (s) {
339 *s = 0;
340 isdead = 1;
341 }
342 }
343 } else if (pb->packettype & T_POSITION) {
344 // Pick originator callsign
345 memcpy( keybuf, pb->data, CALLSIGNLEN_MAX) ;
346 s = strchr(keybuf, '>');
347 if (s) *s = 0;
348 } else {
349 historydb_nointerest(); // debug thing -- a profiling counter
350 return -1; // Not a packet with positional data, not interested in...
351 }
352 keylen = strlen(keybuf);
353
354 ++historydb_inserts;
355
356 h1 = keyhash(keybuf, keylen, 0);
357 h2 = h1 ^ (h1 >> 13) ^ (h1 >> 26); /* fold hash bits.. */
358 i = h2 % HISTORYDB_HASH_MODULO;
359
360 cp = cp1 = NULL;
361 hp = &historydb_hash[i];
362
363 // multiple locks ? one for each bucket, or for a subset of buckets ?
364 rwl_wrlock(&historydb_rwlock);
365
366 // scan the hash-bucket chain, and do incidential obsolete data discard
367 while (( cp = *hp )) {
368 if (cp->arrivaltime < expirytime) {
369 // OLD...
370 *hp = cp->next;
371 cp->next = NULL;
372 historydb_free(cp);
373 continue;
374 }
375 if (cp->hash1 == h1) {
376 // Hash match, compare the key
377 historydb_hashmatch(); // debug thing -- a profiling counter
378 ++historydb_hashmatches;
379 if ( cp->keylen == keylen &&
380 (memcmp(cp->key, keybuf, keylen) == 0) ) {
381 // Key match!
382 historydb_keymatch(); // debug thing -- a profiling counter
383 ++historydb_keymatches;
384 if (isdead) {
385 // Remove this key..
386 *hp = cp->next;
387 cp->next = NULL;
388 historydb_free(cp);
389 continue;
390 } else {
391 historydb_dataupdate(); // debug thing -- a profiling counter
392 // Update the data content
393 cp1 = cp;
394 cp->lat = pb->lat;
395 cp->coslat = pb->cos_lat;
396 cp->lon = pb->lng;
397 cp->arrivaltime = pb->t;
398 cp->packettype = pb->packettype;
399 cp->flags = pb->flags;
400 }
401 }
402 } // .. else no match, advance hp..
403 hp = &(cp -> next);
404 }
405
406 if (!cp1 && !isdead) {
407 // Not found on this chain, append it!
408 cp = historydb_alloc();
409 if (!cp) {
410 hlog(LOG_ERR, "historydb: cellmalloc failed");
411 rwl_wrunlock(&historydb_rwlock);
412 return 1;
413 }
414 cp->next = NULL;
415 memcpy(cp->key, keybuf, keylen);
416 cp->key[keylen] = 0; /* zero terminate */
417 cp->keylen = keylen;
418 cp->hash1 = h1;
419
420 cp->lat = pb->lat;
421 cp->coslat = pb->cos_lat;
422 cp->lon = pb->lng;
423 cp->arrivaltime = pb->t;
424 cp->packettype = pb->packettype;
425 cp->flags = pb->flags;
426
427 *hp = cp;
428 }
429
430 // Free the lock
431 rwl_wrunlock(&historydb_rwlock);
432
433 return 1;
434 }
435
436 /* lookup... */
437
historydb_lookup(const char * keybuf,const int keylen,struct history_cell_t ** result)438 int historydb_lookup(const char *keybuf, const int keylen, struct history_cell_t **result)
439 {
440 int i;
441 uint32_t h1, h2;
442 struct history_cell_t *cp;
443
444 // validity is 5 minutes shorter than expiration time..
445 time_t validitytime = tick - lastposition_storetime + 5*60;
446
447 ++historydb_lookups;
448
449 h1 = keyhash(keybuf, keylen, 0);
450 h2 = h1 ^ (h1 >> 13) ^ (h1 >> 26); /* fold hash bits.. */
451 i = h2 % HISTORYDB_HASH_MODULO;
452
453 cp = historydb_hash[i];
454
455 // multiple locks ? one for each bucket, or for a subset of buckets ?
456 rwl_rdlock(&historydb_rwlock);
457
458 while ( cp ) {
459 if ( (cp->hash1 == h1) &&
460 // Hash match, compare the key
461 (cp->keylen == keylen) &&
462 (memcmp(cp->key, keybuf, keylen) == 0) &&
463 // Key match!
464 (cp->arrivaltime > validitytime)
465 // NOT too old..
466 ) {
467 break;
468 }
469 // Pick next possible item in hash chain
470 cp = cp->next;
471 }
472
473 // Free the lock
474 rwl_rdunlock(&historydb_rwlock);
475
476 // cp variable has the result
477 *result = cp;
478
479 if (!cp) return 0; // Not found anything
480
481 return 1;
482 }
483
484
485
486 /*
487 * The historydb_cleanup() exists to purge too old data out of
488 * the database at regular intervals. Call this about once a minute.
489 */
490
historydb_cleanup(void)491 void historydb_cleanup(void)
492 {
493 struct history_cell_t **hp, *cp;
494 int i;
495 long cleaned = 0;
496
497 // validity is 5 minutes shorter than expiration time..
498 time_t expirytime = tick - lastposition_storetime;
499
500
501 for (i = 0; i < HISTORYDB_HASH_MODULO; ++i) {
502 hp = &historydb_hash[i];
503
504 // multiple locks ? one for each bucket, or for a subset of buckets ?
505 // .. or should we just lock outside the for(i ...) loop ?
506 rwl_wrlock(&historydb_rwlock);
507
508 while (( cp = *hp )) {
509 if (cp->arrivaltime < expirytime) {
510 // OLD...
511 *hp = cp->next;
512 cp->next = NULL;
513 historydb_free(cp);
514 ++cleaned;
515 continue;
516 }
517 /* No expiry, just advance the pointer */
518 hp = &(cp -> next);
519 }
520
521 // Free the lock
522 rwl_wrunlock(&historydb_rwlock);
523 }
524
525 historydb_cleanup_cleaned = cleaned;
526
527 // hlog( LOG_DEBUG, "historydb_cleanup() removed %d entries, count now %ld",
528 // cleaned, historydb_cellgauge );
529 }
530
531 /*
532 * cellmalloc status
533 */
534
535 #ifndef _FOR_VALGRIND_
historydb_cell_stats(struct cellstatus_t * cellst)536 void historydb_cell_stats(struct cellstatus_t *cellst)
537 {
538 rwl_rdlock(&historydb_rwlock);
539 cellstatus(historydb_cells, cellst);
540 rwl_rdunlock(&historydb_rwlock);
541 }
542 #endif
543
544
545