2 * Netgrind -- The Network Traffic Analyser
4 * (c) 2003 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU General Public License.
14 #include "netgrind/netgrind.h"
15 #include "netgrind/pkt.h"
21 #include <net/ethernet.h>
22 #include <netinet/in.h>
23 #include <netinet/ip.h>
24 #include <netinet/tcp.h>
28 void die(byte *msg, ...)
33 fputs("netgrind: ", stderr);
34 vfprintf(stderr, msg, args);
39 /*** CHECKSUMMING ***/
41 static uns tcpip_calc_checksum(void *data, uns len, uns csum)
47 csum += (x[0] << 8) | x[1];
48 if (csum & 0xffff0000)
59 if (csum & 0xffff0000)
68 static inline uns tcpip_verify_checksum(uns csum)
70 return (csum == 0xffff);
73 /*** FLOW ANALYSIS ***/
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);
90 static void sink_open(struct flow *f)
94 static void sink_close(struct flow *f, int cause)
98 static void sink_input(struct flow *f, int dir, struct pkt *p)
103 struct appl_hooks appl_sink = {
111 static struct pkt_stats stat_tcp_in, stat_tcp_invalid, stat_tcp_badsum, stat_tcp_unmatched,
115 list queue; /* incoming packets */
116 u32 last_acked_seq; /* last sequence number for which I sent ACK */
117 u32 syn_or_fin_seq; /* sequence number of SYN/FIN I sent */
118 enum { /* very simplified TCP state machine */
120 FLOW_SYN_SENT, /* sent SYN, waiting for SYN ACK */
121 FLOW_SYN_SENT_ACK, /* sent SYN ACK, waiting for first ACK */
122 FLOW_ESTABLISHED, /* established state including waiting for ACK of SYN ACK */
123 FLOW_FIN_SENT, /* sent FIN, waiting for its ACK */
124 FLOW_FINISHED /* closed, ignoring further packets */
126 struct pkt_stats stat_in;
129 static byte *pipe_state_names[] = { "IDLE", "SYNSENT", "SYNACK", "ESTAB", "FINSENT", "FINISH" };
132 struct flow *hash_next;
133 u32 saddr, daddr, sport, dport;
136 struct appl_hooks *appl;
141 static uns num_flows, max_flows;
142 static struct flow **flow_hash;
143 static struct flow **flow_heap;
145 static uns flow_calc_hash(u32 saddr, u32 daddr, u32 sport, u32 dport)
147 saddr = (saddr >> 16) | (saddr << 16);
148 daddr = (daddr >> 8) | (daddr << 24);
151 return (saddr + daddr + sport + dport) % max_flows;
154 #define FLOW_HEAP_LESS(a,b) (a->timeout < b->timeout)
155 #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)
157 static void flow_rehash(void)
159 uns omax = max_flows;
160 struct flow **ohash = flow_hash;
165 max_flows = nextprime(2*max_flows);
168 DBG("Rehashing to %d buckets\n", max_flows);
169 flow_hash = xmalloc_zero(sizeof(struct flow *) * max_flows);
170 flow_heap = xmalloc_zero(sizeof(struct flow *) * (max_flows+1));
172 for (uns i=0; i<omax; i++)
174 struct flow *f = ohash[i];
177 struct flow *n = f->hash_next;
178 uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
179 f->hash_next = flow_hash[h];
181 flow_heap[++num_flows] = f;
182 f->heap_pos = num_flows;
188 HEAP_INIT(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
191 static struct flow *flow_lookup(u32 saddr, u32 daddr, u32 sport, u32 dport)
193 uns h = flow_calc_hash(saddr, daddr, sport, dport);
194 for (struct flow *f = flow_hash[h]; f; f=f->hash_next)
195 if (f->saddr == saddr && f->daddr == daddr &&
196 f->sport == sport && f->dport == dport)
201 static struct flow *flow_create(u32 saddr, u32 daddr, u32 sport, u32 dport)
203 if (num_flows >= max_flows)
205 uns h = flow_calc_hash(saddr, daddr, sport, dport);
206 struct flow *f = xmalloc_zero(sizeof(struct flow));
212 f->hash_next = flow_hash[h];
214 flow_heap[++num_flows] = f;
215 f->heap_pos = num_flows;
219 static void flow_set_timeout(struct flow *f, u32 when)
222 HEAP_CHANGE(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP, f->heap_pos);
225 static uns flow_now(struct pkt *p)
227 return p->timestamp >> 20;
230 static inline int tcp_seq_le(u32 a, u32 b)
232 return ((b - a) < 0x80000000);
235 static inline int tcp_seq_lt(u32 a, u32 b)
237 return (a != b && tcp_seq_le(a, b));
240 static void tcp_time_step(uns now)
242 while (num_flows && flow_heap[1]->timeout <= now)
244 struct flow *f = flow_heap[1];
245 HEAP_DELMIN(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
246 DBG("TIMEOUT for flow %p(%s/%s)\n", f, pipe_state_names[f->pipe[0].state], pipe_state_names[f->pipe[1].state]);
247 if (f->pipe[0].state != FLOW_FINISHED || f->pipe[1].state != FLOW_FINISHED)
248 f->appl->close(f, (now == ~0U) ? CAUSE_DOOMSDAY : CAUSE_TIMEOUT);
249 uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
250 struct flow **gg = &flow_hash[h];
259 gg = &(*gg)->hash_next;
265 static void tcp_enqueue_data(struct pipe *b, struct pkt *p)
267 struct pkt *q, *prev, *new;
271 if (tcp_seq_lt(b->last_acked_seq, p->seq) && p->seq - b->last_acked_seq >= 0x40000)
273 DBG(" OUT OF WINDOW (last-ack=%u)\n", b->last_acked_seq);
277 prev = (struct pkt *) &b->queue.head;
278 last_seq = b->last_acked_seq;
281 if (tcp_seq_lt(p->seq, last_seq))
283 if (tcp_seq_le(p->seq + pkt_len(p), last_seq))
289 pkt_pop(p, p->seq + pkt_len(p) - last_seq);
293 q = list_next(&b->queue, &prev->n);
294 if (q && tcp_seq_le(q->seq, p->seq))
296 /* next packet starts before us => skip it */
298 last_seq = q->seq + pkt_len(q);
303 if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p)))
305 /* overlap with next packet => split */
307 uns keeplen = q->seq - p->seq;
308 uns newlen = pkt_len(p) - keeplen;
309 new = pkt_new(0, newlen);
310 memcpy(pkt_append(new, newlen), pkt_unappend(p, newlen), newlen);
311 new->seq = p->seq + keeplen;
314 list_insert(&p->n, &prev->n);
316 last_seq = p->seq + pkt_len(p);
323 static void tcp_got_packet(struct iphdr *iph, struct pkt *p)
333 uns now = flow_now(p);
337 pkt_account(&stat_tcp_in, p);
338 if (!(tcph = pkt_peek(p, sizeof(*tcph))))
340 uns hdrlen = 4*tcph->doff;
341 if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
343 fakehdr.src = iph->saddr;
344 fakehdr.dst = iph->daddr;
346 fakehdr.proto = IPPROTO_TCP;
347 fakehdr.len = htons(pkt_len(p));
348 uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0);
349 sum = tcpip_calc_checksum(p->data, pkt_len(p), sum);
350 if (!tcpip_verify_checksum(sum))
352 pkt_account(&stat_tcp_badsum, p);
355 /* XXX: Check TCP options? */
358 u32 seq = ntohl(tcph->seq);
359 u32 ack = ntohl(tcph->ack_seq);
360 DBG("TCP %08x %08x %04x %04x seq=%u+%u ack=%u%s%s%s%s%s%s\n",
361 ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest), seq, pkt_len(p), ack,
362 (tcph->fin ? " FIN" : ""),
363 (tcph->syn ? " SYN" : ""),
364 (tcph->rst ? " RST" : ""),
365 (tcph->psh ? " PSH" : ""),
366 (tcph->ack ? " ACK" : ""),
367 (tcph->urg ? " URG" : ""));
371 if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
376 else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
383 /* Flow not found, if it's a SYN packet, go create it */
384 if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
386 f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest);
387 f->appl = &appl_sink;
391 list_init(&a->queue);
392 a->syn_or_fin_seq = a->last_acked_seq = seq;
393 a->state = FLOW_SYN_SENT;
394 list_init(&b->queue);
395 b->state = FLOW_IDLE;
396 DBG("\t%p NEW\n", f);
399 DBG("\tUnmatched\n");
400 pkt_account(&stat_tcp_unmatched, p);
404 DBG("\t%p %s (%s/%s) ", f, (a == &f->pipe[0] ? "A->B" : "B->A"), pipe_state_names[f->pipe[0].state], pipe_state_names[f->pipe[1].state]);
405 if (a->state == FLOW_FINISHED && b->state == FLOW_FINISHED)
408 pkt_account(&stat_tcp_on_closed, p);
415 f->appl->close(f, CAUSE_RESET);
416 a->state = b->state = FLOW_FINISHED;
417 flow_set_timeout(f, now + 300); /* FIXME */
421 flow_set_timeout(f, now + 600); /* FIXME */
425 if (tcph->fin || pkt_len(p))
429 if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack)
432 a->last_acked_seq = ack;
433 a->syn_or_fin_seq = seq;
434 a->state = FLOW_SYN_SENT_ACK;
435 b->last_acked_seq = seq;
438 else if (b->state == FLOW_ESTABLISHED)
444 goto dup; /* otherwise SYN on already existing connection gets ignored */
449 if (tcp_seq_le(ack, a->last_acked_seq))
454 a->last_acked_seq = ack;
455 while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack))
458 DBG("data(%Ld-%Ld), ", a->stat_in.bytes, a->stat_in.bytes+pkt_len(q)-1);
459 pkt_account(&a->stat_in, q);
460 f->appl->input(f, (a == &f->pipe[1]), q);
462 if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack)
464 a->state = b->state = FLOW_ESTABLISHED;
467 else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack)
469 b->state = FLOW_FINISHED;
470 if (a->state == FLOW_FINISHED)
472 DBG("CLOSED BOTH WAYS\n");
473 f->appl->close(f, CAUSE_CLOSE);
474 flow_set_timeout(f, now + 300); /* FIXME */
478 DBG("CLOSED ONE-WAY, ");
480 else if ((q = list_head(&a->queue)) && tcp_seq_lt(ack, q->seq))
482 DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n");
485 else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT)
492 if (a->state == FLOW_ESTABLISHED)
494 a->state = FLOW_FIN_SENT;
495 a->syn_or_fin_seq = seq;
496 DBG("FIN SENT, waiting for FIN ACK, ");
498 else if (a->state == FLOW_FIN_SENT)
510 if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED)
513 tcp_enqueue_data(b, p);
534 pkt_account(&stat_tcp_invalid, p);
540 static struct pkt_stats stat_ip_in, stat_ip_invalid, stat_ip_uninteresting, stat_ip_fragmented, stat_ip_badsum;
542 static void ip_got_packet(struct pkt *p)
546 pkt_account(&stat_ip_in, p);
547 if (!(iph = pkt_peek(p, sizeof(*iph))))
551 if (iph->version != 4)
553 uns hdrlen = 4*iph->ihl;
554 if (pkt_len(p) < hdrlen)
556 if (!tcpip_verify_checksum(tcpip_calc_checksum(p->data, hdrlen, 0)))
558 pkt_account(&stat_ip_badsum, p);
561 uns len = ntohs(iph->tot_len);
562 if (len < hdrlen || len > pkt_len(p))
564 pkt_unappend(p, pkt_len(p) - len);
567 if (iph->protocol != IPPROTO_TCP)
569 pkt_account(&stat_ip_uninteresting, p);
572 /* XXX: Fragmentation not supported yet, but well-behaved TCP stacks don't use it anyway */
573 if (ntohs(iph->frag_off) & 0x3fff)
575 pkt_account(&stat_ip_fragmented, p);
578 tcp_got_packet(iph, p);
582 pkt_account(&stat_ip_invalid, p);
589 static struct pkt_stats stat_link_dwarf, stat_link_in, stat_link_unknown, stat_link_arp;
591 static void link_eth_got_packet(struct pkt *p)
593 struct ether_header *eth;
596 pkt_account(&stat_link_in, p);
597 if (!(eth = pkt_pop(p, sizeof(*eth))))
599 pkt_account(&stat_link_dwarf, p);
602 etype = ntohs(eth->ether_type);
609 pkt_account(&stat_link_arp, p);
613 // printf("Unknown ethertype: %04x\n", etype);
614 pkt_account(&stat_link_unknown, p);
619 /*** PCAP INTERFACE ***/
621 static void (*link_handler)(struct pkt *);
622 static struct pkt_stats stat_pcap_incomplete;
624 static int link_setup_handler(int dlt)
628 case DLT_EN10MB: link_handler = link_eth_got_packet; return 1;
633 static void got_pcap_packet(u_char *userdata UNUSED, const struct pcap_pkthdr *hdr, const u_char *pkt)
635 if (hdr->caplen != hdr->len)
637 stat_pcap_incomplete.packets++;
638 stat_pcap_incomplete.bytes += hdr->len - hdr->caplen;
641 struct pkt *p = pkt_new(0, hdr->len);
642 memcpy(pkt_append(p, hdr->len), pkt, hdr->len);
643 p->timestamp = (u64)hdr->ts.tv_sec * 1000000 + hdr->ts.tv_usec;
647 int main(int argc, char **argv)
649 char errbuf[PCAP_ERRBUF_SIZE];
654 die("Usage: netgrind <capture-file>");
658 if (!(pcap = pcap_open_offline(argv[1], errbuf)))
659 die("Unable to open %s: %s", argv[1], errbuf);
660 dlt = pcap_datalink(pcap);
661 if (!link_setup_handler(dlt))
662 die("Don't know how to handle data link type %d", dlt);
663 if (pcap_loop(pcap, -1, got_pcap_packet, NULL) < 0)
664 die("Capture failed: %s", pcap_geterr(pcap));
667 struct pcap_stat stats;
668 if (pcap_stats(pcap, &stats))
669 die("pcap_stats: %s", pcap_geterr(pcap));
670 printf("libpcap stats: %d packets received, %d dropped\n", stats.ps_recv, stats.ps_drop);
672 printf("Pcap: %Ld(%Ld) incomplete\n",
673 stat_pcap_incomplete.packets, stat_pcap_incomplete.bytes);
674 printf("Link: %Ld(%Ld) in, %Ld(%Ld) dwarves, %Ld(%Ld) strangers, %Ld(%Ld) ARPs\n",
675 stat_link_in.packets, stat_link_in.bytes,
676 stat_link_dwarf.packets, stat_link_dwarf.bytes,
677 stat_link_unknown.packets, stat_link_unknown.bytes,
678 stat_link_arp.packets, stat_link_arp.bytes);
679 printf("IP: %Ld(%Ld) in, %Ld(%Ld) invalid, %Ld(%Ld) boring, %Ld(%Ld) fragmented, %Ld(%Ld) bad checksum\n",
680 stat_ip_in.packets, stat_ip_in.bytes,
681 stat_ip_invalid.packets, stat_ip_invalid.bytes,
682 stat_ip_uninteresting.packets, stat_ip_uninteresting.bytes,
683 stat_ip_fragmented.packets, stat_ip_fragmented.bytes,
684 stat_ip_badsum.packets, stat_ip_badsum.bytes);
685 printf("TCP: %Ld(%Ld) in, %Ld(%Ld) invalid, %Ld(%Ld) bad checksum\n",
686 stat_tcp_in.packets, stat_tcp_in.bytes,
687 stat_tcp_invalid.packets, stat_tcp_invalid.bytes,
688 stat_tcp_badsum.packets, stat_tcp_badsum.bytes);