]> mj.ucw.cz Git - netgrind.git/blob - netgrind/netgrind.c
fda19165e35da9d5f2823beb5208d4390af7d5c7
[netgrind.git] / netgrind / netgrind.c
1 /*
2  *      Netgrind -- The Network Traffic Analyser
3  *
4  *      (c) 2003 Martin Mares <mj@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU General Public License.
8  */
9
10 #define LOCAL_DEBUG
11
12 #include "lib/lib.h"
13 #include "lib/heap.h"
14 #include "netgrind/netgrind.h"
15 #include "netgrind/pkt.h"
16
17 #include <stdio.h>
18 #include <stdarg.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <net/ethernet.h>
22 #include <netinet/in.h>
23 #include <netinet/ip.h>
24 #include <netinet/tcp.h>
25
26 #include <pcap.h>
27
28 void die(byte *msg, ...)
29 {
30   va_list args;
31
32   va_start(args, msg);
33   fputs("netgrind: ", stderr);
34   vfprintf(stderr, msg, args);
35   fputs("\n", stderr);
36   exit(1);
37 }
38
39 /*** CHECKSUMMING ***/
40
41 static uns tcpip_calc_checksum(void *data, uns len, uns csum)
42 {
43   byte *x = data;
44
45   while (len >= 2)
46     {
47       csum += (x[0] << 8) | x[1];
48       if (csum & 0xffff0000)
49         {
50           csum &= 0x0000ffff;
51           csum++;
52         }
53       x += 2;
54       len -= 2;
55     }
56   if (len)
57     {
58       csum += x[0];
59       if (csum & 0xffff0000)
60         {
61           csum &= 0x0000ffff;
62           csum++;
63         }
64     }
65   return csum;
66 }
67
68 static inline uns tcpip_verify_checksum(uns csum)
69 {
70   return (csum == 0xffff);
71 }
72
73 /*** FLOW ANALYSIS ***/
74
75 enum close_cause {
76   CAUSE_CLOSE,
77   CAUSE_RESET,
78   CAUSE_TIMEOUT,
79   CAUSE_DOOMSDAY
80 };
81
82 struct flow;
83
84 struct appl_hooks {
85   void (*open)(struct flow *f);
86   void (*input)(struct flow *f, int dir, struct pkt *p);
87   void (*close)(struct flow *f, int cause);
88 };
89
90 static void sink_open(struct flow *f)
91 {
92 }
93
94 static void sink_close(struct flow *f, int cause)
95 {
96 }
97
98 static void sink_input(struct flow *f, int dir, struct pkt *p)
99 {
100 }
101
102 struct appl_hooks appl_sink = {
103   .open = sink_open,
104   .input = sink_input,
105   .close = sink_close
106 };
107
108 /*** TCP LAYER ***/
109
110 static struct pkt_stats stat_tcp_in, stat_tcp_invalid, stat_tcp_badsum, stat_tcp_unmatched,
111   stat_tcp_on_closed;
112
113 struct pipe {
114   list queue;
115   u32 last_acked_seq;
116   enum {
117     FLOW_IDLE,
118     FLOW_SYN_SENT,                      /* sent SYN, waiting for SYN ACK */
119     FLOW_SYN_SENT_ACK,                  /* sent SYN ACK, waiting for first ACK */
120     FLOW_ESTABLISHED,                   /* established state including waiting for ACK of SYN ACK */
121     FLOW_FIN_SENT,                      /* sent FIN, waiting for its ACK */
122     FLOW_CLOSED                         /* closed, ignoring further packets */
123   } state;
124 };
125
126 struct flow {
127   struct flow *hash_next;
128   u32 saddr, daddr, sport, dport;
129   u32 timeout;
130   uns heap_pos;
131   struct appl_hooks *appl;
132   void *appl_data;
133   struct pipe pipe[2];
134 };
135
136 static uns num_flows, max_flows;
137 static struct flow **flow_hash;
138 static struct flow **flow_heap;
139
140 static uns flow_calc_hash(u32 saddr, u32 daddr, u32 sport, u32 dport)
141 {
142   saddr = (saddr >> 16) | (saddr << 16);
143   daddr = (daddr >>  8) | (daddr << 24);
144   sport <<= 7;
145   dport <<= 21;
146   return (saddr + daddr + sport + dport) % max_flows;
147 }
148
149 #define FLOW_HEAP_LESS(a,b) (a->timeout < b->timeout)
150 #define FLOW_HEAP_SWAP(h,a,b,t) do { t=h[a]; h[a]=h[b]; h[b]=t; h[a]->heap_pos=a; h[b]->heap_pos=b; } while(0)
151
152 static void flow_rehash(void)
153 {
154   uns omax = max_flows;
155   struct flow **ohash = flow_hash;
156
157   if (flow_heap)
158     xfree(flow_heap);
159   if (max_flows)
160     max_flows = nextprime(2*max_flows);
161   else
162     max_flows = 3;
163   DBG("Rehashing to %d buckets\n", max_flows);
164   flow_hash = xmalloc_zero(sizeof(struct flow *) * max_flows);
165   flow_heap = xmalloc_zero(sizeof(struct flow *) * (max_flows+1));
166   num_flows = 0;
167   for (uns i=0; i<omax; i++)
168     {
169       struct flow *f = ohash[i];
170       while (f)
171         {
172           struct flow *n = f->hash_next;
173           uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
174           f->hash_next = flow_hash[h];
175           flow_hash[h] = f;
176           flow_heap[++num_flows] = f;
177           f->heap_pos = num_flows;
178           f = n;
179         }
180     }
181   if (ohash)
182     xfree(ohash);
183   HEAP_INIT(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
184 }
185
186 static struct flow *flow_lookup(u32 saddr, u32 daddr, u32 sport, u32 dport)
187 {
188   uns h = flow_calc_hash(saddr, daddr, sport, dport);
189   for (struct flow *f = flow_hash[h]; f; f=f->hash_next)
190     if (f->saddr == saddr && f->daddr == daddr &&
191         f->sport == sport && f->dport == dport)
192       return f;
193   return NULL;
194 }
195
196 static struct flow *flow_create(u32 saddr, u32 daddr, u32 sport, u32 dport)
197 {
198   if (num_flows >= max_flows)
199     flow_rehash();
200   uns h = flow_calc_hash(saddr, daddr, sport, dport);
201   struct flow *f = xmalloc_zero(sizeof(struct flow));
202   f->saddr = saddr;
203   f->daddr = daddr;
204   f->sport = sport;
205   f->dport = dport;
206   f->timeout = ~0U;
207   f->hash_next = flow_hash[h];
208   flow_hash[h] = f;
209   flow_heap[++num_flows] = f;
210   f->heap_pos = num_flows;
211   return f;
212 }
213
214 static void flow_set_timeout(struct flow *f, u32 when)
215 {
216   f->timeout = when;
217   HEAP_CHANGE(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP, f->heap_pos);
218 }
219
220 static uns flow_now(struct pkt *p)
221 {
222   return p->timestamp >> 20;
223 }
224
225 static void tcp_time_step(uns now)
226 {
227   while (num_flows && flow_heap[1]->timeout <= now)
228     {
229       struct flow *f = flow_heap[1];
230       HEAP_DELMIN(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
231       DBG("TIMEOUT for flow %p(%d/%d)\n", f, f->pipe[0].state, f->pipe[1].state);
232       if (f->pipe[0].state != FLOW_CLOSED || f->pipe[1].state != FLOW_CLOSED)
233         f->appl->close(f, (now == ~0U) ? CAUSE_DOOMSDAY : CAUSE_TIMEOUT);
234       uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
235       struct flow **gg = &flow_hash[h];
236       for(;;)
237         {
238           ASSERT(*gg);
239           if (*gg == f)
240             {
241               *gg = f->hash_next;
242               break;
243             }
244           gg = &(*gg)->hash_next;
245         }
246       xfree(f);
247     }
248 }
249
250 static void tcp_got_packet(struct iphdr *iph, struct pkt *p)
251 {
252   struct tcphdr *tcph;
253   struct {
254     u32 src;
255     u32 dst;
256     byte zero;
257     byte proto;
258     u16 len;
259   } fakehdr;
260   uns now = flow_now(p);
261
262   tcp_time_step(now);
263
264   pkt_account(&stat_tcp_in, p);
265   if (!(tcph = pkt_peek(p, sizeof(*tcph))))
266     goto invalid;
267   uns hdrlen = 4*tcph->doff;
268   if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
269     goto invalid;
270   fakehdr.src = iph->saddr;
271   fakehdr.dst = iph->daddr;
272   fakehdr.zero = 0;
273   fakehdr.proto = IPPROTO_TCP;
274   fakehdr.len = htons(pkt_len(p));
275   uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0);
276   sum = tcpip_calc_checksum(p->data, pkt_len(p), sum);
277   if (!tcpip_verify_checksum(sum))
278     {
279       pkt_account(&stat_tcp_badsum, p);
280       goto drop;
281     }
282   /* XXX: Check TCP options? */
283   pkt_pop(p, hdrlen);
284
285   u32 seq = ntohl(tcph->seq);
286   u32 ack = ntohl(tcph->ack_seq);
287   DBG("TCP %08x %08x %04x %04x seq=%u+%u ack=%u%s%s%s%s%s%s\n",
288       ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest), seq, pkt_len(p), ack,
289       (tcph->fin ? " FIN" : ""),
290       (tcph->syn ? " SYN" : ""),
291       (tcph->rst ? " RST" : ""),
292       (tcph->psh ? " PSH" : ""),
293       (tcph->ack ? " ACK" : ""),
294       (tcph->urg ? " URG" : ""));
295
296   struct flow *f;
297   struct pipe *a, *b;
298   if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
299     {
300       a = &f->pipe[0];
301       b = &f->pipe[1];
302     }
303   else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
304     {
305       a = &f->pipe[1];
306       b = &f->pipe[0];
307     }
308   else
309     {
310       /* Flow not found, if it's a SYN packet, go create it */
311       if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
312         {
313           f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest);
314           f->appl = &appl_sink;
315           f->appl->open(f);
316           a = &f->pipe[0];
317           b = &f->pipe[1];
318           list_init(&a->queue);
319           a->last_acked_seq = seq;
320           a->state = FLOW_SYN_SENT;
321           list_init(&b->queue);
322           b->state = FLOW_IDLE;
323           DBG("\t%p NEW\n", f);
324           goto drop;
325         }
326       DBG("\tUnmatched\n");
327       pkt_account(&stat_tcp_unmatched, p);
328       goto drop;
329     }
330
331   DBG("\t%p(%d/%d) ", f, a->state, b->state);
332   if (a->state == FLOW_CLOSED && b->state == FLOW_CLOSED)
333     {
334       DBG("closed\n");
335       pkt_account(&stat_tcp_on_closed, p);
336       goto drop;
337     }
338
339   if (tcph->rst)
340     {
341       DBG("RESET\n");
342       f->appl->close(f, CAUSE_RESET);
343       a->state = b->state = FLOW_CLOSED;
344       flow_set_timeout(f, now + 300); /* FIXME */
345       goto drop;
346     }
347
348   flow_set_timeout(f, now + 600); /* FIXME */
349
350   if (tcph->syn)
351     {
352       if (tcph->fin || pkt_len(p))
353         goto inval;
354       if (tcph->ack)
355         {                       /* SYN ACK */
356           if (b->state == FLOW_SYN_SENT && b->last_acked_seq+1 == ack)
357             {
358               DBG("SYN ACK\n");
359               b->last_acked_seq = ack;
360               a->state = FLOW_SYN_SENT_ACK;
361               a->last_acked_seq = seq;
362               goto drop;
363             }
364           else if (b->state == FLOW_ESTABLISHED)
365             goto dup;
366           else
367             goto unex;
368         }
369       else
370         goto dup; /* otherwise SYN on already existing connection gets ignored */
371     }
372
373   if (tcph->ack)
374     {
375       if (b->state == FLOW_SYN_SENT_ACK && b->last_acked_seq+1 == ack)
376         {
377           a->state = b->state = FLOW_ESTABLISHED;
378           b->last_acked_seq = ack+1;
379           DBG("ACKED SYN, ");
380         }
381       if (b->state == FLOW_FIN_SENT && b->last_acked_seq+1 == ack)
382         {
383           b->state = FLOW_CLOSED;
384           if (a->state == FLOW_CLOSED)
385             {
386               DBG("CLOSED BOTH WAYS\n");
387               f->appl->close(f, CAUSE_CLOSE);
388               flow_set_timeout(f, now + 300); /* FIXME */
389               goto drop;
390             }
391           else
392             DBG("CLOSED ONE-WAY, ");
393         }
394       else if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT)
395         DBG("ACK, ");
396       else if (b->state == FLOW_CLOSED)
397         ;
398       else
399         goto unex;
400     }
401
402   if (tcph->fin)
403     {
404       if (a->state == FLOW_ESTABLISHED)
405         {
406           a->state = FLOW_FIN_SENT;
407           a->last_acked_seq = seq;
408           DBG("FIN SENT, waiting for FIN ACK, ");
409         }
410       else if (a->state == FLOW_FIN_SENT)
411         ;
412       else
413         goto unex;
414     }
415
416   if (!pkt_len(p))
417     {
418       DBG("EMPTY\n");
419       goto drop;
420     }
421
422   if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_CLOSED)
423     {
424       DBG("DATA\n");
425       // list_add_tail(&b->queue, &p->n); /* FIXME */
426       if (pkt_len(p))
427         f->appl->input(f, (a == &f->pipe[1]), p);
428       return;
429     }
430   else
431     goto unex;
432
433  drop:
434   pkt_free(p);
435   return;
436
437  dup:
438   DBG("DUP\n");
439   goto drop;
440
441  unex:
442   DBG("UNEXPECTED\n");
443   goto drop;
444
445  inval:
446   DBG("???\n");
447  invalid:
448   pkt_account(&stat_tcp_invalid, p);
449   goto drop;
450 }
451
452 /*** IP LAYER ***/
453
454 static struct pkt_stats stat_ip_in, stat_ip_invalid, stat_ip_uninteresting, stat_ip_fragmented, stat_ip_badsum;
455
456 static void ip_got_packet(struct pkt *p)
457 {
458   struct iphdr *iph;
459
460   pkt_account(&stat_ip_in, p);
461   if (!(iph = pkt_peek(p, sizeof(*iph))))
462     goto invalid;
463   if (iph->ihl < 5)
464     goto invalid;
465   if (iph->version != 4)
466     goto invalid;
467   uns hdrlen = 4*iph->ihl;
468   if (pkt_len(p) < hdrlen)
469     goto invalid;
470   if (!tcpip_verify_checksum(tcpip_calc_checksum(p->data, hdrlen, 0)))
471     {
472       pkt_account(&stat_ip_badsum, p);
473       goto drop;
474     }
475   uns len = ntohs(iph->tot_len);
476   if (len < hdrlen || len > pkt_len(p))
477     goto invalid;
478   pkt_unappend(p, pkt_len(p) - len);
479   pkt_pop(p, hdrlen);
480
481   if (iph->protocol != IPPROTO_TCP)
482     {
483       pkt_account(&stat_ip_uninteresting, p);
484       goto drop;
485     }
486   /* XXX: Fragmentation not supported yet, but well-behaved TCP stacks don't use it anyway */
487   if (ntohs(iph->frag_off) & 0x3fff)
488     {
489       pkt_account(&stat_ip_fragmented, p);
490       goto drop;
491     }
492   tcp_got_packet(iph, p);
493   return;
494
495  invalid:
496   pkt_account(&stat_ip_invalid, p);
497  drop:
498   pkt_free(p);
499 }
500
501 /*** LINK LAYER ***/
502
503 static struct pkt_stats stat_link_dwarf, stat_link_in, stat_link_unknown, stat_link_arp;
504
505 static void link_eth_got_packet(struct pkt *p)
506 {
507   struct ether_header *eth;
508   uns etype;
509
510   pkt_account(&stat_link_in, p);
511   if (!(eth = pkt_pop(p, sizeof(*eth))))
512     {
513       pkt_account(&stat_link_dwarf, p);
514       return;
515     }
516   etype = ntohs(eth->ether_type);
517   switch (etype)
518     {
519     case ETHERTYPE_IP:
520       ip_got_packet(p);
521       break;
522     case ETHERTYPE_ARP:
523       pkt_account(&stat_link_arp, p);
524       pkt_free(p);
525       break;
526     default:
527       // printf("Unknown ethertype: %04x\n", etype);
528       pkt_account(&stat_link_unknown, p);
529       pkt_free(p);
530     }
531 }
532
533 /*** PCAP INTERFACE ***/
534
535 static void (*link_handler)(struct pkt *);
536 static struct pkt_stats stat_pcap_incomplete;
537
538 static int link_setup_handler(int dlt)
539 {
540   switch (dlt)
541     {
542     case DLT_EN10MB:    link_handler = link_eth_got_packet; return 1;
543     default:            return 0;
544     }
545 }
546
547 static void got_pcap_packet(u_char *userdata UNUSED, const struct pcap_pkthdr *hdr, const u_char *pkt)
548 {
549   if (hdr->caplen != hdr->len)
550     {
551       stat_pcap_incomplete.packets++;
552       stat_pcap_incomplete.bytes += hdr->len - hdr->caplen;
553       return;
554     }
555   struct pkt *p = pkt_new(0, hdr->len);
556   memcpy(pkt_append(p, hdr->len), pkt, hdr->len);
557   p->timestamp = (u64)hdr->ts.tv_sec * 1000000 + hdr->ts.tv_usec;
558   link_handler(p);
559 }
560
561 int main(int argc, char **argv)
562 {
563   char errbuf[PCAP_ERRBUF_SIZE];
564   pcap_t *pcap;
565   int dlt;
566
567   if (argc != 2)
568     die("Usage: netgrind <capture-file>");
569
570   flow_rehash();
571
572   if (!(pcap = pcap_open_offline(argv[1], errbuf)))
573     die("Unable to open %s: %s", argv[1], errbuf);
574   dlt = pcap_datalink(pcap);
575   if (!link_setup_handler(dlt))
576     die("Don't know how to handle data link type %d", dlt);
577   if (pcap_loop(pcap, -1, got_pcap_packet, NULL) < 0)
578     die("Capture failed: %s", pcap_geterr(pcap));
579   tcp_time_step(~0U);
580 #if 0
581   struct pcap_stat stats;
582   if (pcap_stats(pcap, &stats))
583     die("pcap_stats: %s", pcap_geterr(pcap));
584   printf("libpcap stats: %d packets received, %d dropped\n", stats.ps_recv, stats.ps_drop);
585 #endif
586   printf("Pcap: %Ld(%Ld) incomplete\n",
587          stat_pcap_incomplete.packets, stat_pcap_incomplete.bytes);
588   printf("Link: %Ld(%Ld) in, %Ld(%Ld) dwarves, %Ld(%Ld) strangers, %Ld(%Ld) ARPs\n",
589          stat_link_in.packets, stat_link_in.bytes,
590          stat_link_dwarf.packets, stat_link_dwarf.bytes,
591          stat_link_unknown.packets, stat_link_unknown.bytes,
592          stat_link_arp.packets, stat_link_arp.bytes);
593   printf("IP: %Ld(%Ld) in, %Ld(%Ld) invalid, %Ld(%Ld) boring, %Ld(%Ld) fragmented, %Ld(%Ld) bad checksum\n",
594          stat_ip_in.packets, stat_ip_in.bytes,
595          stat_ip_invalid.packets, stat_ip_invalid.bytes,
596          stat_ip_uninteresting.packets, stat_ip_uninteresting.bytes,
597          stat_ip_fragmented.packets, stat_ip_fragmented.bytes,
598          stat_ip_badsum.packets, stat_ip_badsum.bytes);
599   printf("TCP: %Ld(%Ld) in, %Ld(%Ld) invalid, %Ld(%Ld) bad checksum\n",
600          stat_tcp_in.packets, stat_tcp_in.bytes,
601          stat_tcp_invalid.packets, stat_tcp_invalid.bytes,
602          stat_tcp_badsum.packets, stat_tcp_badsum.bytes);
603   pcap_close(pcap);
604   return 0;
605 }