Small IPv6 corrections and an IPv6 hash function.
[darkstat.git] / hosts_db.c
1 /* darkstat 3
2  * copyright (c) 2001-2009 Emil Mikulic.
3  *
4  * hosts_db.c: database of hosts, ports, protocols.
5  *
6  * You may use, modify and redistribute this file under the terms of the
7  * GNU General Public License version 2. (see COPYING.GPL)
8  */
9
10 #include "darkstat.h"
11 #include "conv.h"
12 #include "decode.h"
13 #include "dns.h"
14 #include "err.h"
15 #include "hosts_db.h"
16 #include "db.h"
17 #include "html.h"
18 #include "ncache.h"
19 #include "now.h"
20
21 #include <arpa/inet.h> /* inet_aton() */
22 #include <assert.h>
23 #include <errno.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h> /* memset(), strcmp() */
27 #include <unistd.h>
28
29 extern int want_lastseen;
30 int show_mac_addrs = 0;
31 extern const char *interface;
32
33 /* FIXME: specify somewhere more sane/tunable */
34 #define MAX_ENTRIES 30 /* in an HTML table rendered from a hashtable */
35
36 typedef uint32_t (hash_func_t)(const struct hashtable *, const void *);
37 typedef void (free_func_t)(struct bucket *);
38 typedef const void * (key_func_t)(const struct bucket *);
39 typedef int (find_func_t)(const struct bucket *, const void *);
40 typedef struct bucket * (make_func_t)(const void *);
41 typedef void (format_cols_func_t)(struct str *);
42 typedef void (format_row_func_t)(struct str *, const struct bucket *,
43    const char *);
44
45 struct hashtable {
46    uint8_t bits;     /* size of hashtable in bits */
47    uint32_t size, mask;
48    uint32_t count, count_max, count_keep;   /* items in table */
49    uint32_t coeff;   /* coefficient for Fibonacci hashing */
50    struct bucket **table;
51
52    struct {
53       uint64_t inserts, searches, deletions, rehashes;
54    } stats;
55
56    hash_func_t *hash_func;
57    /* returns hash value of given key (passed as void*) */
58
59    free_func_t *free_func;
60    /* free of bucket payload */
61
62    key_func_t *key_func;
63    /* returns pointer to key of bucket (to pass to hash_func) */
64
65    find_func_t *find_func;
66    /* returns true if given bucket matches key (passed as void*) */
67
68    make_func_t *make_func;
69    /* returns bucket containing new record with key (passed as void*) */
70
71    format_cols_func_t *format_cols_func;
72    /* append table columns to str */
73
74    format_row_func_t *format_row_func;
75    /* format record and append to str */
76 };
77
78 static void hashtable_reduce(struct hashtable *ht);
79 static void hashtable_free(struct hashtable *h);
80
81 #define HOST_BITS 1  /* initial size of hosts table */
82 #define PORT_BITS 1  /* initial size of ports tables */
83 #define PROTO_BITS 1 /* initial size of proto table */
84
85 /* We only use one hosts_db hashtable and this is it. */
86 static struct hashtable *hosts_db = NULL;
87
88 /* phi^-1 (reciprocal of golden ratio) = (sqrt(5) - 1) / 2 */
89 static const double phi_1 =
90    0.61803398874989490252573887119069695472717285156250;
91
92 /* Co-prime of u, using phi^-1 */
93 inline static uint32_t
94 coprime(const uint32_t u)
95 {
96    return ( (uint32_t)( (double)(u) * phi_1 ) | 1U );
97 }
98
99 /*
100  * This is the "recommended" IPv4 hash function, as seen in FreeBSD's
101  * src/sys/netinet/tcp_hostcache.c 1.1
102  */
103 inline static uint32_t
104 ipv4_hash(const uint32_t ip)
105 {
106    return ( (ip) ^ ((ip) >> 7) ^ ((ip) >> 17) );
107 }
108
109 #ifndef s6_addr32
110 /* Covers OpenBSD and FreeBSD.  The macro __USE_GNU has
111  * taken care of GNU/Linux and GNU/kfreebsd.  */
112 # define s6_addr32 __u6_addr.__u6_addr32
113 #endif
114
115 /*
116  * This is the IPv6 hash function used by FreeBSD in the same file as above,
117  * svn rev 122922.
118  */
119 inline static uint32_t
120 ipv6_hash(const struct in6_addr *const ip6)
121 {
122    return ( ip6->s6_addr32[0] ^ ip6->s6_addr32[1] ^ ip6->s6_addr32[2] ^ ip6->s6_addr32[3] );
123 }
124
125 /* ---------------------------------------------------------------------------
126  * hash_func collection
127  */
128 #define CASTKEY(type) (*((const type *)key))
129
130 static uint32_t
131 hash_func_host(const struct hashtable *h _unused_, const void *key)
132 {
133    return (ipv4_hash(CASTKEY(in_addr_t)));
134 }
135
136 static uint32_t
137 hash_func_short(const struct hashtable *h, const void *key)
138 {
139    return (CASTKEY(uint16_t) * h->coeff);
140 }
141
142 static uint32_t
143 hash_func_byte(const struct hashtable *h, const void *key)
144 {
145    return (CASTKEY(uint8_t) * h->coeff);
146 }
147
148 /* ---------------------------------------------------------------------------
149  * key_func collection
150  */
151
152 static const void *
153 key_func_host(const struct bucket *b)
154 {
155    return &(b->u.host.ip);
156 }
157
158 static const void *
159 key_func_port_tcp(const struct bucket *b)
160 {
161    return &(b->u.port_tcp.port);
162 }
163
164 static const void *
165 key_func_port_udp(const struct bucket *b)
166 {
167    return &(b->u.port_udp.port);
168 }
169
170 static const void *
171 key_func_ip_proto(const struct bucket *b)
172 {
173    return &(b->u.ip_proto.proto);
174 }
175
176 /* ---------------------------------------------------------------------------
177  * find_func collection
178  */
179
180 static int
181 find_func_host(const struct bucket *b, const void *key)
182 {
183    return (b->u.host.ip == CASTKEY(in_addr_t));
184 }
185
186 static int
187 find_func_port_tcp(const struct bucket *b, const void *key)
188 {
189    return (b->u.port_tcp.port == CASTKEY(uint16_t));
190 }
191
192 static int
193 find_func_port_udp(const struct bucket *b, const void *key)
194 {
195    return (b->u.port_udp.port == CASTKEY(uint16_t));
196 }
197
198 static int
199 find_func_ip_proto(const struct bucket *b, const void *key)
200 {
201    return (b->u.ip_proto.proto == CASTKEY(uint8_t));
202 }
203
204 /* ---------------------------------------------------------------------------
205  * make_func collection
206  */
207
208 #define MAKE_BUCKET(name_bucket, name_content, type) struct { \
209    struct bucket *next; \
210    uint64_t in, out, total; \
211    union { struct type t; } u; } _custom_bucket; \
212    struct bucket *name_bucket = xcalloc(1, sizeof(_custom_bucket)); \
213    struct type *name_content = &(name_bucket->u.type); \
214    name_bucket->next = NULL; \
215    name_bucket->in = name_bucket->out = name_bucket->total = 0;
216
217 static struct bucket *
218 make_func_host(const void *key)
219 {
220    MAKE_BUCKET(b, h, host);
221    h->ip = CASTKEY(in_addr_t);
222    h->dns = NULL;
223    h->last_seen = now;
224    memset(&h->mac_addr, 0, sizeof(h->mac_addr));
225    h->ports_tcp = NULL;
226    h->ports_udp = NULL;
227    h->ip_protos = NULL;
228    return (b);
229 }
230
231 static void
232 free_func_host(struct bucket *b)
233 {
234    struct host *h = &(b->u.host);
235    if (h->dns != NULL) free(h->dns);
236    hashtable_free(h->ports_tcp);
237    hashtable_free(h->ports_udp);
238    hashtable_free(h->ip_protos);
239 }
240
241 static struct bucket *
242 make_func_port_tcp(const void *key)
243 {
244    MAKE_BUCKET(b, p, port_tcp);
245    p->port = CASTKEY(uint16_t);
246    p->syn = 0;
247    return (b);
248 }
249
250 static struct bucket *
251 make_func_port_udp(const void *key)
252 {
253    MAKE_BUCKET(b, p, port_udp);
254    p->port = CASTKEY(uint16_t);
255    return (b);
256 }
257
258 static struct bucket *
259 make_func_ip_proto(const void *key)
260 {
261    MAKE_BUCKET(b, p, ip_proto);
262    p->proto = CASTKEY(uint8_t);
263    return (b);
264 }
265
266 static void
267 free_func_simple(struct bucket *b _unused_)
268 {
269    /* nop */
270 }
271
272 /* ---------------------------------------------------------------------------
273  * format_func collection (ordered by struct)
274  */
275
276 static void
277 format_cols_host(struct str *buf)
278 {
279    /* FIXME: don't clobber parts of the query string
280     * specifically "full" and "start"
281     * when setting sort direction
282     */
283    str_append(buf,
284       "<table>\n"
285       "<tr>\n"
286       " <th>IP</th>\n"
287       " <th>Hostname</th>\n");
288    if (show_mac_addrs) str_append(buf,
289       " <th>MAC Address</th>\n");
290    str_append(buf,
291       " <th><a href=\"?sort=in\">In</a></th>\n"
292       " <th><a href=\"?sort=out\">Out</a></th>\n"
293       " <th><a href=\"?sort=total\">Total</a></th>\n");
294    if (want_lastseen) str_append(buf,
295       " <th>Last seen</th>\n");
296    str_append(buf,
297       "</tr>\n");
298 }
299
300 static void
301 format_row_host(struct str *buf, const struct bucket *b,
302    const char *css_class)
303 {
304    const char *ip = ip_to_str( b->u.host.ip );
305
306    str_appendf(buf,
307       "<tr class=\"%s\">\n"
308       " <td><a href=\"%s/\">%s</a></td>\n"
309       " <td>%s</td>\n",
310       css_class,
311       ip, ip,
312       (b->u.host.dns == NULL) ? "" : b->u.host.dns);
313
314    if (show_mac_addrs)
315       str_appendf(buf,
316          " <td><tt>%x:%x:%x:%x:%x:%x</tt></td>\n",
317          b->u.host.mac_addr[0],
318          b->u.host.mac_addr[1],
319          b->u.host.mac_addr[2],
320          b->u.host.mac_addr[3],
321          b->u.host.mac_addr[4],
322          b->u.host.mac_addr[5]);
323
324    str_appendf(buf,
325       " <td class=\"num\">%'qu</td>\n"
326       " <td class=\"num\">%'qu</td>\n"
327       " <td class=\"num\">%'qu</td>\n",
328       b->in, b->out, b->total);
329
330    if (want_lastseen) {
331       time_t last_t = b->u.host.last_seen;
332       struct str *lastseen = NULL;
333
334       if (now >= last_t)
335          lastseen = length_of_time(now - last_t);
336
337       str_append(buf,
338          " <td class=\"num\">");
339       if (lastseen == NULL)
340          str_append(buf, "(clock error)");
341       else {
342          str_appendstr(buf, lastseen);
343          str_free(lastseen);
344       }
345       str_append(buf,
346          "</td>");
347    }
348
349    str_appendf(buf,
350       "</tr>\n");
351
352    /* Only resolve hosts "on demand" */
353    if (b->u.host.dns == NULL)
354       dns_queue(b->u.host.ip);
355 }
356
357 static void
358 format_cols_port_tcp(struct str *buf)
359 {
360    str_append(buf,
361       "<table>\n"
362       "<tr>\n"
363       " <th>Port</td>\n"
364       " <th>Service</td>\n"
365       " <th>In</td>\n"
366       " <th>Out</td>\n"
367       " <th>Total</td>\n"
368       " <th>SYNs</td>\n"
369       "</tr>\n"
370    );
371 }
372
373 static void
374 format_row_port_tcp(struct str *buf, const struct bucket *b,
375    const char *css_class)
376 {
377    const struct port_tcp *p = &(b->u.port_tcp);
378
379    str_appendf(buf,
380       "<tr class=\"%s\">\n"
381       " <td class=\"num\">%u</td>\n"
382       " <td>%s</td>\n"
383       " <td class=\"num\">%'qu</td>\n"
384       " <td class=\"num\">%'qu</td>\n"
385       " <td class=\"num\">%'qu</td>\n"
386       " <td class=\"num\">%'qu</td>\n"
387       "</tr>\n",
388       css_class,
389       p->port, getservtcp(p->port), b->in, b->out, b->total, p->syn
390    );
391 }
392
393 static void
394 format_cols_port_udp(struct str *buf)
395 {
396    str_append(buf,
397       "<table>\n"
398       "<tr>\n"
399       " <th>Port</td>\n"
400       " <th>Service</td>\n"
401       " <th>In</td>\n"
402       " <th>Out</td>\n"
403       " <th>Total</td>\n"
404       "</tr>\n"
405    );
406 }
407
408 static void
409 format_row_port_udp(struct str *buf, const struct bucket *b,
410    const char *css_class)
411 {
412    const struct port_udp *p = &(b->u.port_udp);
413
414    str_appendf(buf,
415       "<tr class=\"%s\">\n"
416       " <td class=\"num\">%u</td>\n"
417       " <td>%s</td>\n"
418       " <td class=\"num\">%'qu</td>\n"
419       " <td class=\"num\">%'qu</td>\n"
420       " <td class=\"num\">%'qu</td>\n"
421       "</tr>\n",
422       css_class,
423       p->port, getservudp(p->port), b->in, b->out, b->total
424    );
425 }
426
427 static void
428 format_cols_ip_proto(struct str *buf)
429 {
430    str_append(buf,
431       "<table>\n"
432       "<tr>\n"
433       " <th>#</td>\n"
434       " <th>Protocol</td>\n"
435       " <th>In</td>\n"
436       " <th>Out</td>\n"
437       " <th>Total</td>\n"
438       "</tr>\n"
439    );
440 }
441
442 static void
443 format_row_ip_proto(struct str *buf, const struct bucket *b,
444    const char *css_class)
445 {
446    const struct ip_proto *p = &(b->u.ip_proto);
447
448    str_appendf(buf,
449       "<tr class=\"%s\">\n"
450       " <td class=\"num\">%u</td>\n"
451       " <td>%s</td>\n"
452       " <td class=\"num\">%'qu</td>\n"
453       " <td class=\"num\">%'qu</td>\n"
454       " <td class=\"num\">%'qu</td>\n"
455       "</tr>\n",
456       css_class,
457       p->proto, getproto(p->proto),
458       b->in, b->out, b->total
459    );
460 }
461
462 /* ---------------------------------------------------------------------------
463  * Initialise a hashtable.
464  */
465 static struct hashtable *
466 hashtable_make(const uint8_t bits,
467    const unsigned int count_max,
468    const unsigned int count_keep,
469    hash_func_t *hash_func,
470    free_func_t *free_func,
471    key_func_t *key_func,
472    find_func_t *find_func,
473    make_func_t *make_func,
474    format_cols_func_t *format_cols_func,
475    format_row_func_t *format_row_func)
476 {
477    struct hashtable *hash;
478    assert(bits > 0);
479
480    hash = xmalloc(sizeof(*hash));
481    hash->bits = bits;
482    hash->count_max = count_max;
483    hash->count_keep = count_keep;
484    hash->size = 1U << bits;
485    hash->mask = hash->size - 1;
486    hash->coeff = coprime(hash->size);
487    hash->hash_func = hash_func;
488    hash->free_func = free_func;
489    hash->key_func = key_func;
490    hash->find_func = find_func;
491    hash->make_func = make_func;
492    hash->format_cols_func = format_cols_func;
493    hash->format_row_func = format_row_func;
494    hash->count = 0;
495    hash->table = xcalloc(hash->size, sizeof(*hash->table));
496    memset(&(hash->stats), 0, sizeof(hash->stats));
497    return (hash);
498 }
499
500 /* ---------------------------------------------------------------------------
501  * Initialise global hosts_db.
502  */
503 void
504 hosts_db_init(void)
505 {
506    assert(hosts_db == NULL);
507    hosts_db = hashtable_make(HOST_BITS, hosts_max, hosts_keep,
508       hash_func_host, free_func_host, key_func_host, find_func_host,
509       make_func_host, format_cols_host, format_row_host);
510 }
511
512 static void
513 hashtable_rehash(struct hashtable *h, const uint8_t bits)
514 {
515    struct bucket **old_table, **new_table;
516    uint32_t i, old_size;
517    assert(h != NULL);
518    assert(bits > 0);
519
520    h->stats.rehashes++;
521    old_size = h->size;
522    old_table = h->table;
523
524    h->bits = bits;
525    h->size = 1U << bits;
526    h->mask = h->size - 1;
527    h->coeff = coprime(h->size);
528    new_table = xcalloc(h->size, sizeof(*new_table));
529
530    for (i=0; i<old_size; i++) {
531       struct bucket *next, *b = old_table[i];
532       while (b != NULL) {
533          uint32_t pos = h->hash_func(h, h->key_func(b)) & h->mask;
534          next = b->next;
535          b->next = new_table[pos];
536          new_table[pos] = b;
537          b = next;
538       }
539    }
540
541    free(h->table);
542    h->table = new_table;
543 }
544
545 static void
546 hashtable_insert(struct hashtable *h, struct bucket *b)
547 {
548    uint32_t pos;
549    assert(h != NULL);
550    assert(b != NULL);
551    assert(b->next == NULL);
552
553    /* Rehash on 80% occupancy */
554    if ((h->count > h->size) ||
555        ((h->size - h->count) < h->size / 5))
556       hashtable_rehash(h, h->bits+1);
557
558    pos = h->hash_func(h, h->key_func(b)) & h->mask;
559    if (h->table[pos] == NULL)
560       h->table[pos] = b;
561    else {
562       /* Insert at top of chain. */
563       b->next = h->table[pos];
564       h->table[pos] = b;
565    }
566    h->count++;
567    h->stats.inserts++;
568 }
569
570 /* Return bucket matching key, or NULL if no such entry. */
571 static struct bucket *
572 hashtable_search(struct hashtable *h, const void *key)
573 {
574    uint32_t pos;
575    struct bucket *b;
576
577    h->stats.searches++;
578    pos = h->hash_func(h, key) & h->mask;
579    b = h->table[pos];
580    while (b != NULL) {
581       if (h->find_func(b, key))
582          return (b);
583       else
584          b = b->next;
585    }
586    return (NULL);
587 }
588
589 /* Search for a key.  If it's not there, make and insert a bucket for it. */
590 static struct bucket *
591 hashtable_find_or_insert(struct hashtable *h, const void *key)
592 {
593    struct bucket *b = hashtable_search(h, key);
594
595    if (b == NULL) {
596       /* Not found, so insert after checking occupancy. */
597       /*assert(h->count <= h->count_max);*/
598       if (h->count >= h->count_max) hashtable_reduce(h);
599       b = h->make_func(key);
600       hashtable_insert(h, b);
601    }
602    return (b);
603 }
604
605 /*
606  * Frees the hashtable and the buckets.  The contents are assumed to be
607  * "simple" -- i.e. no "destructor" action is required beyond simply freeing
608  * the bucket.
609  */
610 static void
611 hashtable_free(struct hashtable *h)
612 {
613    uint32_t i;
614
615    if (h == NULL)
616       return;
617    for (i=0; i<h->size; i++) {
618       struct bucket *tmp, *b = h->table[i];
619       while (b != NULL) {
620          tmp = b;
621          b = b->next;
622          h->free_func(tmp);
623          free(tmp);
624       }
625    }
626    free(h->table);
627    free(h);
628 }
629
630 /* ---------------------------------------------------------------------------
631  * Return existing host or insert a new one.
632  */
633 struct bucket *
634 host_get(const in_addr_t ip)
635 {
636    return (hashtable_find_or_insert(hosts_db, &ip));
637 }
638
639 /* ---------------------------------------------------------------------------
640  * Find host, returns NULL if not in DB.
641  */
642 struct bucket *
643 host_find(const in_addr_t ip)
644 {
645    return (hashtable_search(hosts_db, &ip));
646 }
647
648 /* ---------------------------------------------------------------------------
649  * Find host, returns NULL if not in DB.
650  */
651 static struct bucket *
652 host_search(const char *ipstr)
653 {
654    struct in_addr addr;
655
656    if (inet_aton(ipstr, &addr) != 1)
657       return (NULL); /* invalid addr */
658    return (hashtable_search(hosts_db, &(addr.s_addr)));
659 }
660
661 /* ---------------------------------------------------------------------------
662  * Reduce a hashtable to the top <keep> entries.
663  */
664 static void
665 hashtable_reduce(struct hashtable *ht)
666 {
667    uint32_t i, pos, rmd;
668    const struct bucket **table;
669    uint64_t cutoff;
670
671    assert(ht->count_keep < ht->count);
672
673    /* Fill table with pointers to buckets in hashtable. */
674    table = xcalloc(ht->count, sizeof(*table));
675    for (pos=0, i=0; i<ht->size; i++) {
676       struct bucket *b = ht->table[i];
677       while (b != NULL) {
678          table[pos++] = b;
679          b = b->next;
680       }
681    }
682    assert(pos == ht->count);
683    qsort_buckets(table, ht->count, 0, ht->count_keep, TOTAL);
684    cutoff = table[ht->count_keep]->total;
685    free(table);
686
687    /* Remove all elements with total <= cutoff. */
688    rmd = 0;
689    for (i=0; i<ht->size; i++) {
690       struct bucket *last = NULL, *next, *b = ht->table[i];
691       while (b != NULL) {
692          next = b->next;
693          if (b->total <= cutoff) {
694             /* Remove this one. */
695             ht->free_func(b);
696             free(b);
697             if (last == NULL)
698                ht->table[i] = next;
699             else
700                last->next = next;
701             rmd++;
702             ht->count--;
703          } else {
704             last = b;
705          }
706          b = next;
707       }
708    }
709    verbosef("hashtable_reduce: removed %u buckets, left %u",
710       rmd, ht->count);
711    hashtable_rehash(ht, ht->bits); /* is this needed? */
712 }
713
714 /* ---------------------------------------------------------------------------
715  * Reset hosts_db to empty.
716  */
717 void
718 hosts_db_reset(void)
719 {
720    unsigned int i;
721
722    for (i=0; i<hosts_db->size; i++) {
723       struct bucket *next, *b = hosts_db->table[i];
724       while (b != NULL) {
725          next = b->next;
726          hosts_db->free_func(b);
727          free(b);
728          b = next;
729       }
730       hosts_db->table[i] = NULL;
731    }
732    verbosef("hosts_db reset to empty, freed %u hosts", hosts_db->count);
733    hosts_db->count = 0;
734 }
735
736 /* ---------------------------------------------------------------------------
737  * Deallocate hosts_db.
738  */
739 void hosts_db_free(void)
740 {
741    uint32_t i;
742
743    assert(hosts_db != NULL);
744    for (i=0; i<hosts_db->size; i++) {
745       struct bucket *tmp, *b = hosts_db->table[i];
746       while (b != NULL) {
747          tmp = b;
748          b = b->next;
749          hosts_db->free_func(tmp);
750          free(tmp);
751       }
752    }
753    free(hosts_db->table);
754    free(hosts_db);
755    hosts_db = NULL;
756 }
757
758 /* ---------------------------------------------------------------------------
759  * Find or create a port_tcp inside a host.
760  */
761 struct bucket *
762 host_get_port_tcp(struct bucket *host, const uint16_t port)
763 {
764    struct host *h = &host->u.host;
765    assert(h != NULL);
766    if (h->ports_tcp == NULL)
767       h->ports_tcp = hashtable_make(PORT_BITS, ports_max, ports_keep,
768          hash_func_short, free_func_simple, key_func_port_tcp,
769          find_func_port_tcp, make_func_port_tcp,
770          format_cols_port_tcp, format_row_port_tcp);
771    return (hashtable_find_or_insert(h->ports_tcp, &port));
772 }
773
774 /* ---------------------------------------------------------------------------
775  * Find or create a port_udp inside a host.
776  */
777 struct bucket *
778 host_get_port_udp(struct bucket *host, const uint16_t port)
779 {
780    struct host *h = &host->u.host;
781    assert(h != NULL);
782    if (h->ports_udp == NULL)
783       h->ports_udp = hashtable_make(PORT_BITS, ports_max, ports_keep,
784          hash_func_short, free_func_simple, key_func_port_udp,
785          find_func_port_udp, make_func_port_udp,
786          format_cols_port_udp, format_row_port_udp);
787    return (hashtable_find_or_insert(h->ports_udp, &port));
788 }
789
790 /* ---------------------------------------------------------------------------
791  * Find or create an ip_proto inside a host.
792  */
793 struct bucket *
794 host_get_ip_proto(struct bucket *host, const uint8_t proto)
795 {
796    struct host *h = &host->u.host;
797    static const unsigned int PROTOS_MAX = 512, PROTOS_KEEP = 256;
798    assert(h != NULL);
799    if (h->ip_protos == NULL)
800       h->ip_protos = hashtable_make(PROTO_BITS, PROTOS_MAX, PROTOS_KEEP,
801          hash_func_byte, free_func_simple, key_func_ip_proto,
802          find_func_ip_proto, make_func_ip_proto,
803          format_cols_ip_proto, format_row_ip_proto);
804    return (hashtable_find_or_insert(h->ip_protos, &proto));
805 }
806
807 static struct str *html_hosts_main(const char *qs);
808 static struct str *html_hosts_detail(const char *ip);
809
810 /* ---------------------------------------------------------------------------
811  * Web interface: delegate the /hosts/ space.
812  */
813 struct str *
814 html_hosts(const char *uri, const char *query)
815 {
816    int i, num_elems;
817    char **elem = split('/', uri, &num_elems);
818    struct str *buf = NULL;
819
820    assert(num_elems >= 1);
821    assert(strcmp(elem[0], "hosts") == 0);
822
823    if (num_elems == 1)
824       /* /hosts/ */
825       buf = html_hosts_main(query);
826    else if (num_elems == 2)
827       /* /hosts/<IP of host>/ */
828       buf = html_hosts_detail(elem[1]);
829
830    for (i=0; i<num_elems; i++)
831       free(elem[i]);
832    free(elem);
833    return (buf); /* FIXME: a NULL here becomes 404 Not Found, we might want
834    other codes to be possible */
835 }
836
837 /* ---------------------------------------------------------------------------
838  * Format hashtable into HTML.
839  */
840 static void
841 format_table(struct str *buf, struct hashtable *ht, int start,
842    const enum sort_dir sort, const int full)
843 {
844    const struct bucket **table;
845    uint32_t i, pos, end;
846    int alt = 0;
847
848    if ((ht == NULL) || (ht->count == 0)) {
849       str_append(buf, "<p>The table is empty.</p>\n");
850       return;
851    }
852
853    /* Fill table with pointers to buckets in hashtable. */
854    table = xcalloc(ht->count, sizeof(*table));
855    for (pos=0, i=0; i<ht->size; i++) {
856       struct bucket *b = ht->table[i];
857       while (b != NULL) {
858          table[pos++] = b;
859          b = b->next;
860       }
861    }
862    assert(pos == ht->count);
863
864    if (full) {
865       /* full report overrides start and end */
866       start = 0;
867       end = ht->count;
868    } else
869       end = min(ht->count, (uint32_t)start+MAX_ENTRIES);
870
871    str_appendf(buf, "(%u-%u of %u)<br/>\n", start+1, end, ht->count);
872    qsort_buckets(table, ht->count, start, end, sort);
873    ht->format_cols_func(buf);
874
875    for (i=start; i<end; i++) {
876       ht->format_row_func(buf, table[i], alt ? "alt1" : "alt2");
877       alt = !alt; /* alternate class for table rows */
878    }
879    free(table);
880    str_append(buf, "</table>\n");
881 }
882
883 /* ---------------------------------------------------------------------------
884  * Web interface: sorted table of hosts.
885  */
886 static struct str *
887 html_hosts_main(const char *qs)
888 {
889    struct str *buf = str_make();
890    char *qs_start, *qs_sort, *qs_full, *ep;
891    const char *sortstr;
892    int start, full = 0;
893    enum sort_dir sort;
894
895    /* parse query string */
896    qs_start = qs_get(qs, "start");
897    qs_sort = qs_get(qs, "sort");
898    qs_full = qs_get(qs, "full");
899    if (qs_full != NULL) {
900       full = 1;
901       free(qs_full);
902    }
903
904    /* validate sort */
905    if (qs_sort == NULL) sort = TOTAL;
906    else if (strcmp(qs_sort, "total") == 0) sort = TOTAL;
907    else if (strcmp(qs_sort, "in") == 0) sort = IN;
908    else if (strcmp(qs_sort, "out") == 0) sort = OUT;
909    else {
910       str_append(buf, "Error: invalid value for \"sort\".\n");
911       goto done;
912    }
913
914    /* parse start */
915    if (qs_start == NULL)
916       start = 0;
917    else {
918       start = (int)strtoul(qs_start, &ep, 10);
919       if (*ep != '\0') {
920          str_append(buf, "Error: \"start\" is not a number.\n");
921          goto done;
922       }
923       if ((errno == ERANGE) ||
924           (start < 0) || (start >= (int)hosts_db->count)) {
925          str_append(buf, "Error: \"start\" is out of bounds.\n");
926          goto done;
927       }
928    }
929
930 #define PREV "&lt;&lt;&lt; prev page"
931 #define NEXT "next page &gt;&gt;&gt;"
932 #define FULL "full table"
933
934    str_append(buf, html_header_1);
935    str_appendf(buf, " <title>darkstat3: Hosts (%s)</title>\n", interface);
936    str_append(buf, html_header_2);
937    str_appendf(buf, "<h2 class=\"pageheader\">Hosts (%s)</h2>\n", interface);
938    format_table(buf, hosts_db, start, sort, full);
939
940    /* <prev | full | stats | next> */
941    sortstr = qs_sort;
942    if (sortstr == NULL) sortstr = "total";
943    if (start > 0) {
944       int prev = max(start - MAX_ENTRIES, 0);
945       str_appendf(buf, "<a href=\"?start=%d&sort=%s\">" PREV "</a>",
946          prev, sortstr);
947    } else
948       str_append(buf, PREV);
949
950    if (full)
951       str_append(buf, " | " FULL);
952    else
953       str_appendf(buf, " | <a href=\"?full=yes&sort=%s\">" FULL "</a>",
954          sortstr);
955
956    if (start+MAX_ENTRIES < (int)hosts_db->count)
957       str_appendf(buf, " | <a href=\"?start=%d&sort=%s\">" NEXT "</a>",
958          start+MAX_ENTRIES, sortstr);
959    else
960       str_append(buf, " | " NEXT);
961
962    str_append(buf, "<br/>\n");
963    str_append(buf, html_footer);
964 done:
965    if (qs_start != NULL) free(qs_start);
966    if (qs_sort != NULL) free(qs_sort);
967    return buf;
968 #undef PREV
969 #undef NEXT
970 #undef FULL
971 }
972
973 /* ---------------------------------------------------------------------------
974  * Web interface: detailed view of a single host.
975  */
976 static struct str *
977 html_hosts_detail(const char *ip)
978 {
979    struct bucket *h;
980    struct str *buf, *ls_len;
981    char ls_when[100];
982    time_t ls;
983
984    h = host_search(ip);
985    if (h == NULL)
986       return (NULL); /* no such host */
987
988    /* Overview. */
989    buf = str_make();
990    str_append(buf, html_header_1);
991    str_appendf(buf, " <title>%s</title>\n", ip);
992    str_append(buf, html_header_2);
993    str_appendf(buf,
994       "<h2>%s</h2>\n"
995       "<p>\n"
996        "<b>Hostname:</b> %s<br/>\n",
997       ip,
998       (h->u.host.dns == NULL)?"(resolving...)":h->u.host.dns);
999
1000    /* Resolve host "on demand" */
1001    if (h->u.host.dns == NULL)
1002       dns_queue(h->u.host.ip);
1003
1004    if (show_mac_addrs)
1005    str_appendf(buf,
1006       "<b>MAC Address:</b> "
1007       "<tt>%x:%x:%x:%x:%x:%x</tt><br/>\n",
1008       h->u.host.mac_addr[0],
1009       h->u.host.mac_addr[1],
1010       h->u.host.mac_addr[2],
1011       h->u.host.mac_addr[3],
1012       h->u.host.mac_addr[4],
1013       h->u.host.mac_addr[5]);
1014
1015    str_append(buf,
1016       "</p>\n"
1017       "<p>\n"
1018       "<b>Last seen:</b> ");
1019
1020    ls = h->u.host.last_seen;
1021    if (strftime(ls_when, sizeof(ls_when),
1022       "%Y-%m-%d %H:%M:%S %Z%z", localtime(&ls)) != 0)
1023          str_append(buf, ls_when);
1024
1025    if (h->u.host.last_seen <= now) {
1026       ls_len = length_of_time(now - h->u.host.last_seen);
1027       str_append(buf, " (");
1028       str_appendstr(buf, ls_len);
1029       str_free(ls_len);
1030       str_append(buf, " ago)");
1031    } else {
1032       str_append(buf, " (in the future, possible clock problem)");
1033    }
1034
1035    str_appendf(buf,
1036       "</p>\n"
1037       "<p>\n"
1038       " <b>In:</b> %'qu<br/>\n"
1039       " <b>Out:</b> %'qu<br/>\n"
1040       " <b>Total:</b> %'qu<br/>\n"
1041       "</p>\n",
1042       h->in, h->out, h->total);
1043
1044    str_append(buf, "<h3>TCP ports</h3>\n");
1045    format_table(buf, h->u.host.ports_tcp, 0,TOTAL,0);
1046
1047    str_append(buf, "<h3>UDP ports</h3>\n");
1048    format_table(buf, h->u.host.ports_udp, 0,TOTAL,0);
1049
1050    str_append(buf, "<h3>IP protocols</h3>\n");
1051    format_table(buf, h->u.host.ip_protos, 0,TOTAL,0);
1052
1053    str_append(buf, html_footer);
1054    return (buf);
1055 }
1056
1057 /* ---------------------------------------------------------------------------
1058  * Database import and export code:
1059  * Initially written and contributed by Ben Stewart.
1060  * copyright (c) 2007 Ben Stewart, Emil Mikulic.
1061  */
1062 static int hosts_db_export_ip(const struct hashtable *h, const int fd);
1063 static int hosts_db_export_tcp(const struct hashtable *h, const int fd);
1064 static int hosts_db_export_udp(const struct hashtable *h, const int fd);
1065
1066 static const char
1067    export_proto_ip  = 'P',
1068    export_proto_tcp = 'T',
1069    export_proto_udp = 'U';
1070
1071 static const unsigned char
1072    export_tag_host_ver1[] = {'H', 'S', 'T', 0x01},
1073    export_tag_host_ver2[] = {'H', 'S', 'T', 0x02};
1074
1075 /* ---------------------------------------------------------------------------
1076  * Load a host's ip_proto table from a file.
1077  * Returns 0 on failure, 1 on success.
1078  */
1079 static int
1080 hosts_db_import_ip(const int fd, struct bucket *host)
1081 {
1082    uint8_t count, i;
1083
1084    if (!expect8(fd, export_proto_ip)) return 0;
1085    if (!read8(fd, &count)) return 0;
1086
1087    for (i=0; i<count; i++) {
1088       struct bucket *b;
1089       uint8_t proto;
1090       uint64_t in, out;
1091
1092       if (!read8(fd, &proto)) return 0;
1093       if (!read64(fd, &in)) return 0;
1094       if (!read64(fd, &out)) return 0;
1095
1096       /* Store data */
1097       b = host_get_ip_proto(host, proto);
1098       b->in = in;
1099       b->out = out;
1100       b->total = in + out;
1101       assert(b->u.ip_proto.proto == proto); /* should be done by make fn */
1102    }
1103    return 1;
1104 }
1105
1106 /* ---------------------------------------------------------------------------
1107  * Load a host's port_tcp table from a file.
1108  * Returns 0 on failure, 1 on success.
1109  */
1110 static int
1111 hosts_db_import_tcp(const int fd, struct bucket *host)
1112 {
1113    uint16_t count, i;
1114
1115    if (!expect8(fd, export_proto_tcp)) return 0;
1116    if (!read16(fd, &count)) return 0;
1117
1118    for (i=0; i<count; i++) {
1119       struct bucket *b;
1120       uint16_t port;
1121       uint64_t in, out, syn;
1122
1123       if (!read16(fd, &port)) return 0;
1124       if (!read64(fd, &syn)) return 0;
1125       if (!read64(fd, &in)) return 0;
1126       if (!read64(fd, &out)) return 0;
1127
1128       /* Store data */
1129       b = host_get_port_tcp(host, port);
1130       b->in = in;
1131       b->out = out;
1132       b->total = in + out;
1133       assert(b->u.port_tcp.port == port); /* done by make_func_port_tcp */
1134       b->u.port_tcp.syn = syn;
1135    }
1136    return 1;
1137 }
1138
1139 /* ---------------------------------------------------------------------------
1140  * Load a host's port_tcp table from a file.
1141  * Returns 0 on failure, 1 on success.
1142  */
1143 static int
1144 hosts_db_import_udp(const int fd, struct bucket *host)
1145 {
1146    uint16_t count, i;
1147
1148    if (!expect8(fd, export_proto_udp)) return 0;
1149    if (!read16(fd, &count)) return 0;
1150
1151    for (i=0; i<count; i++) {
1152       struct bucket *b;
1153       uint16_t port;
1154       uint64_t in, out;
1155
1156       if (!read16(fd, &port)) return 0;
1157       if (!read64(fd, &in)) return 0;
1158       if (!read64(fd, &out)) return 0;
1159
1160       /* Store data */
1161       b = host_get_port_udp(host, port);
1162       b->in = in;
1163       b->out = out;
1164       b->total = in + out;
1165       assert(b->u.port_udp.port == port); /* done by make_func */
1166    }
1167    return 1;
1168 }
1169
1170 /* ---------------------------------------------------------------------------
1171  * Load all hosts from a file.
1172  * Returns 0 on failure, 1 on success.
1173  */
1174 static int
1175 hosts_db_import_host(const int fd)
1176 {
1177    struct bucket *host;
1178    in_addr_t addr;
1179    uint8_t hostname_len;
1180    uint64_t in, out;
1181    unsigned int pos = xtell(fd);
1182    char hdr[4];
1183    int ver = 0;
1184
1185    if (!readn(fd, hdr, sizeof(hdr))) return 0;
1186    if (memcmp(hdr, export_tag_host_ver2, sizeof(hdr)) == 0)
1187       ver = 2;
1188    else if (memcmp(hdr, export_tag_host_ver1, sizeof(hdr)) == 0)
1189       ver = 1;
1190    else {
1191       warnx("bad host header: %02x%02x%02x%02x",
1192          hdr[0], hdr[1], hdr[2], hdr[3]);
1193       return 0;
1194    }
1195
1196    if (!readaddr(fd, &addr)) return 0;
1197    verbosef("at file pos %u, importing host %s", pos, ip_to_str(addr));
1198    host = host_get(addr);
1199    assert(host->u.host.ip == addr); /* make fn? */
1200
1201    if (ver > 1) {
1202       uint64_t t;
1203       if (!read64(fd, &t)) return 0;
1204       host->u.host.last_seen = (time_t)t;
1205    }
1206
1207    assert(sizeof(host->u.host.mac_addr) == 6);
1208    if (!readn(fd, host->u.host.mac_addr, sizeof(host->u.host.mac_addr)))
1209       return 0;
1210
1211    /* HOSTNAME */
1212    assert(host->u.host.dns == NULL); /* make fn? */
1213    if (!read8(fd, &hostname_len)) return 0;
1214    if (hostname_len > 0) {
1215       host->u.host.dns = xmalloc(hostname_len + 1);
1216       host->u.host.dns[0] = '\0';
1217
1218       /* At this point, the hostname is attached to a host which is in our
1219        * hosts_db, so if we bail out due to an import error, this pointer
1220        * isn't lost and leaked, it can be cleaned up in hosts_db_{free,reset}
1221        */
1222
1223       if (!readn(fd, host->u.host.dns, hostname_len)) return 0;
1224       host->u.host.dns[hostname_len] = '\0';
1225    }
1226
1227    if (!read64(fd, &in)) return 0;
1228    if (!read64(fd, &out)) return 0;
1229
1230    host->in = in;
1231    host->out = out;
1232    host->total = in + out;
1233
1234    /* Host's port and proto subtables: */
1235    if (!hosts_db_import_ip(fd, host)) return 0;
1236    if (!hosts_db_import_tcp(fd, host)) return 0;
1237    if (!hosts_db_import_udp(fd, host)) return 0;
1238    return 1;
1239 }
1240
1241 /* ---------------------------------------------------------------------------
1242  * Database Import: Grab hosts_db from a file provided by the caller.
1243  *
1244  * This function will retrieve the data sans the header.  We expect the caller
1245  * to have validated the header of the hosts_db segment, and left the file
1246  * sitting at the start of the data.
1247  */
1248 int hosts_db_import(const int fd)
1249 {
1250    uint32_t host_count, i;
1251
1252    if (!read32(fd, &host_count)) return 0;
1253
1254    for (i=0; i<host_count; i++)
1255       if (!hosts_db_import_host(fd)) return 0;
1256
1257    return 1;
1258 }
1259
1260 /* ---------------------------------------------------------------------------
1261  * Database Export: Dump hosts_db into a file provided by the caller.
1262  * The caller is responsible for writing out export_tag_hosts_ver1 first.
1263  */
1264 int hosts_db_export(const int fd)
1265 {
1266    uint32_t i;
1267    struct bucket *b;
1268
1269    if (!write32(fd, hosts_db->count)) return 0;
1270
1271    for (i = 0; i<hosts_db->size; i++)
1272    for (b = hosts_db->table[i]; b != NULL; b = b->next) {
1273       /* For each host: */
1274       if (!writen(fd, export_tag_host_ver2, sizeof(export_tag_host_ver2)))
1275          return 0;
1276
1277       if (!writeaddr(fd, b->u.host.ip)) return 0;
1278
1279       if (!write64(fd, (uint64_t)(b->u.host.last_seen))) return 0;
1280
1281       assert(sizeof(b->u.host.mac_addr) == 6);
1282       if (!writen(fd, b->u.host.mac_addr, sizeof(b->u.host.mac_addr)))
1283          return 0;
1284
1285       /* HOSTNAME */
1286       if (b->u.host.dns == NULL) {
1287          if (!write8(fd, 0)) return 0;
1288       } else {
1289          int dnslen = strlen(b->u.host.dns);
1290
1291          if (dnslen > 255) {
1292            warnx("found a very long hostname: \"%s\"\n"
1293               "wasn't expecting one longer than 255 chars (this one is %d)",
1294               b->u.host.dns, dnslen);
1295            dnslen = 255;
1296          }
1297
1298          if (!write8(fd, (uint8_t)dnslen)) return 0;
1299          if (!writen(fd, b->u.host.dns, dnslen)) return 0;
1300       }
1301
1302       if (!write64(fd, b->in)) return 0;
1303       if (!write64(fd, b->out)) return 0;
1304
1305       if (!hosts_db_export_ip(b->u.host.ip_protos, fd)) return 0;
1306       if (!hosts_db_export_tcp(b->u.host.ports_tcp, fd)) return 0;
1307       if (!hosts_db_export_udp(b->u.host.ports_udp, fd)) return 0;
1308    }
1309    return 1;
1310 }
1311
1312 /* ---------------------------------------------------------------------------
1313  * Dump the ip_proto table of a host.
1314  */
1315 static int
1316 hosts_db_export_ip(const struct hashtable *h, const int fd)
1317 {
1318    uint32_t i, written = 0;
1319    struct bucket *b;
1320
1321    /* IP DATA */
1322    if (!write8(fd, export_proto_ip)) return 0;
1323
1324    /* If no data, write a IP Proto count of 0 and we're done. */
1325    if (h == NULL) {
1326       if (!write8(fd, 0)) return 0;
1327       return 1;
1328    }
1329
1330    assert(h->count < 256);
1331    if (!write8(fd, (uint8_t)h->count)) return 0;
1332
1333    for (i = 0; i<h->size; i++)
1334    for (b = h->table[i]; b != NULL; b = b->next) {
1335       /* For each ip_proto bucket: */
1336
1337       if (!write8(fd, b->u.ip_proto.proto)) return 0;
1338       if (!write64(fd, b->in)) return 0;
1339       if (!write64(fd, b->out)) return 0;
1340       written++;
1341    }
1342    assert(written == h->count);
1343    return 1;
1344 }
1345
1346 /* ---------------------------------------------------------------------------
1347  * Dump the port_tcp table of a host.
1348  */
1349 static int
1350 hosts_db_export_tcp(const struct hashtable *h, const int fd)
1351 {
1352    struct bucket *b;
1353    uint32_t i, written = 0;
1354
1355    /* TCP DATA */
1356    if (!write8(fd, export_proto_tcp)) return 0;
1357
1358    /* If no data, write a count of 0 and we're done. */
1359    if (h == NULL) {
1360       if (!write16(fd, 0)) return 0;
1361       return 1;
1362    }
1363
1364    assert(h->count < 65536);
1365    if (!write16(fd, (uint16_t)h->count)) return 0;
1366
1367    for (i = 0; i<h->size; i++)
1368    for (b = h->table[i]; b != NULL; b = b->next) {
1369       if (!write16(fd, b->u.port_tcp.port)) return 0;
1370       if (!write64(fd, b->u.port_tcp.syn)) return 0;
1371       if (!write64(fd, b->in)) return 0;
1372       if (!write64(fd, b->out)) return 0;
1373       written++;
1374    }
1375    assert(written == h->count);
1376    return 1;
1377 }
1378
1379 /* ---------------------------------------------------------------------------
1380  * Dump the port_udp table of a host.
1381  */
1382 static int
1383 hosts_db_export_udp(const struct hashtable *h, const int fd)
1384 {
1385    struct bucket *b;
1386    uint32_t i, written = 0;
1387
1388    /* UDP DATA */
1389    if (!write8(fd, export_proto_udp)) return 0;
1390
1391    /* If no data, write a count of 0 and we're done. */
1392    if (h == NULL) {
1393       if (!write16(fd, 0)) return 0;
1394       return 1;
1395    }
1396
1397    assert(h->count < 65536);
1398    if (!write16(fd, (uint16_t)h->count)) return 0;
1399
1400    for (i = 0; i<h->size; i++)
1401    for (b = h->table[i]; b != NULL; b = b->next) {
1402       if (!write16(fd, b->u.port_udp.port)) return 0;
1403       if (!write64(fd, b->in)) return 0;
1404       if (!write64(fd, b->out)) return 0;
1405       written++;
1406    }
1407    assert(written == h->count);
1408    return 1;
1409 }
1410
1411 /* vim:set ts=3 sw=3 tw=78 expandtab: */