From 87268e5dc49c30b2c159e7a80c292baf37deab9f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 7 Jun 2003 14:24:46 +0000 Subject: [PATCH] ... splitting ... --- netgrind/Makefile | 2 +- netgrind/ip.c | 97 ++++++++ netgrind/link.c | 46 ++++ netgrind/netgrind.c | 595 +------------------------------------------- netgrind/netgrind.h | 68 +++++ netgrind/save.c | 146 +++++++++++ netgrind/tcp.c | 442 ++++++++++++++++++++++++++++++++ 7 files changed, 806 insertions(+), 590 deletions(-) create mode 100644 netgrind/ip.c create mode 100644 netgrind/link.c create mode 100644 netgrind/save.c create mode 100644 netgrind/tcp.c diff --git a/netgrind/Makefile b/netgrind/Makefile index 60ce104..5f0bd0f 100644 --- a/netgrind/Makefile +++ b/netgrind/Makefile @@ -1,6 +1,6 @@ DIRS+=netgrind PROGS+=obj/netgrind/netgrind -NG_OBJS=netgrind.o pkt.o +NG_OBJS=netgrind.o pkt.o link.o ip.o tcp.o save.o obj/netgrind/netgrind: $(addprefix obj/netgrind/,$(NG_OBJS)) $(LIBSH) obj/netgrind/netgrind: LIBS+=-lpcap diff --git a/netgrind/ip.c b/netgrind/ip.c new file mode 100644 index 0000000..0eff8e2 --- /dev/null +++ b/netgrind/ip.c @@ -0,0 +1,97 @@ +/* + * Netgrind -- IP Layer Analyser + * + * (c) 2003 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU General Public License. + */ + +#include "lib/lib.h" +#include "netgrind/pkt.h" +#include "netgrind/netgrind.h" + +#include +#include +#include + +uns tcpip_calc_checksum(void *data, uns len, uns csum) +{ + byte *x = data; + + while (len >= 2) + { + csum += (x[0] << 8) | x[1]; + if (csum & 0xffff0000) + { + csum &= 0x0000ffff; + csum++; + } + x += 2; + len -= 2; + } + if (len) + { + csum += x[0]; + if (csum & 0xffff0000) + { + csum &= 0x0000ffff; + csum++; + } + } + return csum; +} + +uns tcpip_verify_checksum(uns csum) +{ + return 1; + /* FIXME: Fix checksum calculation! */ + return (csum == 0xffff); +} + +struct pkt_stats stat_ip_in, stat_ip_invalid, stat_ip_uninteresting, stat_ip_fragmented, stat_ip_badsum; + +void ip_got_packet(struct pkt *p) +{ + struct iphdr *iph; + + pkt_account(&stat_ip_in, p); + if (!(iph = pkt_peek(p, sizeof(*iph)))) + goto invalid; + if (iph->ihl < 5) + goto invalid; + if (iph->version != 4) + goto invalid; + uns hdrlen = 4*iph->ihl; + if (pkt_len(p) < hdrlen) + goto invalid; + if (!tcpip_verify_checksum(tcpip_calc_checksum(p->data, hdrlen, 0))) + { + pkt_account(&stat_ip_badsum, p); + goto drop; + } + uns len = ntohs(iph->tot_len); + if (len < hdrlen || len > pkt_len(p)) + goto invalid; + pkt_unappend(p, pkt_len(p) - len); + pkt_pop(p, hdrlen); + + if (iph->protocol != IPPROTO_TCP) + { + pkt_account(&stat_ip_uninteresting, p); + goto drop; + } + /* XXX: Fragmentation not supported yet, but well-behaved TCP stacks don't use it anyway */ + if (ntohs(iph->frag_off) & 0x3fff) + { + pkt_account(&stat_ip_fragmented, p); + goto drop; + } + tcp_got_packet(iph, p); + return; + + invalid: + pkt_account(&stat_ip_invalid, p); + drop: + pkt_free(p); +} diff --git a/netgrind/link.c b/netgrind/link.c new file mode 100644 index 0000000..f17f538 --- /dev/null +++ b/netgrind/link.c @@ -0,0 +1,46 @@ +/* + * Netgrind -- Link Layer Analyser + * + * (c) 2003 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU General Public License. + */ + +#include "lib/lib.h" +#include "netgrind/pkt.h" +#include "netgrind/netgrind.h" + +#include +#include +#include + +struct pkt_stats stat_link_dwarf, stat_link_in, stat_link_unknown, stat_link_arp; + +void link_eth_got_packet(struct pkt *p) +{ + struct ether_header *eth; + uns etype; + + pkt_account(&stat_link_in, p); + if (!(eth = pkt_pop(p, sizeof(*eth)))) + { + pkt_account(&stat_link_dwarf, p); + return; + } + etype = ntohs(eth->ether_type); + switch (etype) + { + case ETHERTYPE_IP: + ip_got_packet(p); + break; + case ETHERTYPE_ARP: + pkt_account(&stat_link_arp, p); + pkt_free(p); + break; + default: + // printf("Unknown ethertype: %04x\n", etype); + pkt_account(&stat_link_unknown, p); + pkt_free(p); + } +} diff --git a/netgrind/netgrind.c b/netgrind/netgrind.c index 1c1f80e..a54797a 100644 --- a/netgrind/netgrind.c +++ b/netgrind/netgrind.c @@ -7,21 +7,18 @@ * of the GNU General Public License. */ -#define LOCAL_DEBUG +/* + * FIXME: TCP stats + */ #include "lib/lib.h" -#include "lib/heap.h" -#include "netgrind/netgrind.h" #include "netgrind/pkt.h" +#include "netgrind/netgrind.h" #include #include #include #include -#include -#include -#include -#include #include @@ -36,586 +33,6 @@ void die(byte *msg, ...) exit(1); } -/*** CHECKSUMMING ***/ - -static uns tcpip_calc_checksum(void *data, uns len, uns csum) -{ - byte *x = data; - - while (len >= 2) - { - csum += (x[0] << 8) | x[1]; - if (csum & 0xffff0000) - { - csum &= 0x0000ffff; - csum++; - } - x += 2; - len -= 2; - } - if (len) - { - csum += x[0]; - if (csum & 0xffff0000) - { - csum &= 0x0000ffff; - csum++; - } - } - return csum; -} - -static inline uns tcpip_verify_checksum(uns csum) -{ - return (csum == 0xffff); -} - -/*** FLOW ANALYSIS ***/ - -enum close_cause { - CAUSE_CLOSE, - CAUSE_RESET, - CAUSE_TIMEOUT, - CAUSE_DOOMSDAY -}; - -struct flow; - -struct appl_hooks { - void (*open)(struct flow *f); - void (*input)(struct flow *f, int dir, struct pkt *p); - void (*close)(struct flow *f, int cause); -}; - -static void sink_open(struct flow *f) -{ -} - -static void sink_close(struct flow *f, int cause) -{ -} - -static void sink_input(struct flow *f, int dir, struct pkt *p) -{ - pkt_free(p); -} - -struct appl_hooks appl_sink = { - .open = sink_open, - .input = sink_input, - .close = sink_close -}; - -/*** TCP LAYER ***/ - -static struct pkt_stats stat_tcp_in, stat_tcp_invalid, stat_tcp_badsum, stat_tcp_unmatched, - stat_tcp_on_closed; - -struct pipe { - list queue; /* incoming packets */ - u32 last_acked_seq; /* last sequence number for which I sent ACK */ - u32 syn_or_fin_seq; /* sequence number of SYN/FIN I sent */ - enum { /* very simplified TCP state machine */ - FLOW_IDLE, - FLOW_SYN_SENT, /* sent SYN, waiting for SYN ACK */ - FLOW_SYN_SENT_ACK, /* sent SYN ACK, waiting for first ACK */ - FLOW_ESTABLISHED, /* established state including waiting for ACK of SYN ACK */ - FLOW_FIN_SENT, /* sent FIN, waiting for its ACK */ - FLOW_FINISHED /* closed, ignoring further packets */ - } state; - struct pkt_stats stat_in; -}; - -static byte *pipe_state_names[] = { "IDLE", "SYNSENT", "SYNACK", "ESTAB", "FINSENT", "FINISH" }; - -struct flow { - struct flow *hash_next; - u32 saddr, daddr, sport, dport; - u32 timeout; - uns heap_pos; - struct appl_hooks *appl; - void *appl_data; - struct pipe pipe[2]; -}; - -static uns num_flows, max_flows; -static struct flow **flow_hash; -static struct flow **flow_heap; - -static uns flow_calc_hash(u32 saddr, u32 daddr, u32 sport, u32 dport) -{ - saddr = (saddr >> 16) | (saddr << 16); - daddr = (daddr >> 8) | (daddr << 24); - sport <<= 7; - dport <<= 21; - return (saddr + daddr + sport + dport) % max_flows; -} - -#define FLOW_HEAP_LESS(a,b) (a->timeout < b->timeout) -#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) - -static void flow_rehash(void) -{ - uns omax = max_flows; - struct flow **ohash = flow_hash; - - if (flow_heap) - xfree(flow_heap); - if (max_flows) - max_flows = nextprime(2*max_flows); - else - max_flows = 3; - DBG("Rehashing to %d buckets\n", max_flows); - flow_hash = xmalloc_zero(sizeof(struct flow *) * max_flows); - flow_heap = xmalloc_zero(sizeof(struct flow *) * (max_flows+1)); - num_flows = 0; - for (uns i=0; ihash_next; - uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport); - f->hash_next = flow_hash[h]; - flow_hash[h] = f; - flow_heap[++num_flows] = f; - f->heap_pos = num_flows; - f = n; - } - } - if (ohash) - xfree(ohash); - HEAP_INIT(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP); -} - -static struct flow *flow_lookup(u32 saddr, u32 daddr, u32 sport, u32 dport) -{ - uns h = flow_calc_hash(saddr, daddr, sport, dport); - for (struct flow *f = flow_hash[h]; f; f=f->hash_next) - if (f->saddr == saddr && f->daddr == daddr && - f->sport == sport && f->dport == dport) - return f; - return NULL; -} - -static struct flow *flow_create(u32 saddr, u32 daddr, u32 sport, u32 dport) -{ - if (num_flows >= max_flows) - flow_rehash(); - uns h = flow_calc_hash(saddr, daddr, sport, dport); - struct flow *f = xmalloc_zero(sizeof(struct flow)); - f->saddr = saddr; - f->daddr = daddr; - f->sport = sport; - f->dport = dport; - f->timeout = ~0U; - f->hash_next = flow_hash[h]; - flow_hash[h] = f; - flow_heap[++num_flows] = f; - f->heap_pos = num_flows; - return f; -} - -static void flow_set_timeout(struct flow *f, u32 when) -{ - f->timeout = when; - HEAP_CHANGE(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP, f->heap_pos); -} - -static uns flow_now(struct pkt *p) -{ - return p->timestamp >> 20; -} - -static inline int tcp_seq_le(u32 a, u32 b) -{ - return ((b - a) < 0x80000000); -} - -static inline int tcp_seq_lt(u32 a, u32 b) -{ - return (a != b && tcp_seq_le(a, b)); -} - -static void tcp_time_step(uns now) -{ - while (num_flows && flow_heap[1]->timeout <= now) - { - struct flow *f = flow_heap[1]; - HEAP_DELMIN(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP); - DBG("TIMEOUT for flow %p(%s/%s)\n", f, pipe_state_names[f->pipe[0].state], pipe_state_names[f->pipe[1].state]); - if (f->pipe[0].state != FLOW_FINISHED || f->pipe[1].state != FLOW_FINISHED) - f->appl->close(f, (now == ~0U) ? CAUSE_DOOMSDAY : CAUSE_TIMEOUT); - uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport); - struct flow **gg = &flow_hash[h]; - for(;;) - { - ASSERT(*gg); - if (*gg == f) - { - *gg = f->hash_next; - break; - } - gg = &(*gg)->hash_next; - } - xfree(f); - } -} - -static void tcp_enqueue_data(struct pipe *b, struct pkt *p) -{ - struct pkt *q, *prev, *new; - u32 last_seq; - - DBG("DATA:"); - if (tcp_seq_lt(b->last_acked_seq, p->seq) && p->seq - b->last_acked_seq >= 0x40000) - { - DBG(" OUT OF WINDOW (last-ack=%u)\n", b->last_acked_seq); - pkt_free(p); - return; - } - prev = (struct pkt *) &b->queue.head; - last_seq = b->last_acked_seq; - while (p) - { - if (tcp_seq_lt(p->seq, last_seq)) - { - if (tcp_seq_le(p->seq + pkt_len(p), last_seq)) - { - DBG(" have\n"); - pkt_free(p); - return; - } - pkt_pop(p, p->seq + pkt_len(p) - last_seq); - p->seq = last_seq; - DBG(" clip"); - } - q = list_next(&b->queue, &prev->n); - if (q && tcp_seq_le(q->seq, p->seq)) - { - /* next packet starts before us => skip it */ - prev = q; - last_seq = q->seq + pkt_len(q); - } - else - { - new = NULL; - if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p))) - { - /* overlap with next packet => split */ - DBG(" split"); - uns keeplen = q->seq - p->seq; - uns newlen = pkt_len(p) - keeplen; - new = pkt_new(0, newlen); - memcpy(pkt_append(new, newlen), pkt_unappend(p, newlen), newlen); - new->seq = p->seq + keeplen; - } - DBG(" insert"); - list_insert(&p->n, &prev->n); - prev = p; - last_seq = p->seq + pkt_len(p); - p = new; - } - } - DBG("\n"); -} - -static void tcp_got_packet(struct iphdr *iph, struct pkt *p) -{ - struct tcphdr *tcph; - struct { - u32 src; - u32 dst; - byte zero; - byte proto; - u16 len; - } fakehdr; - uns now = flow_now(p); - - tcp_time_step(now); - - pkt_account(&stat_tcp_in, p); - if (!(tcph = pkt_peek(p, sizeof(*tcph)))) - goto invalid; - uns hdrlen = 4*tcph->doff; - if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p)) - goto invalid; - fakehdr.src = iph->saddr; - fakehdr.dst = iph->daddr; - fakehdr.zero = 0; - fakehdr.proto = IPPROTO_TCP; - fakehdr.len = htons(pkt_len(p)); - uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0); - sum = tcpip_calc_checksum(p->data, pkt_len(p), sum); - if (!tcpip_verify_checksum(sum)) - { - pkt_account(&stat_tcp_badsum, p); - goto drop; - } - /* XXX: Check TCP options? */ - pkt_pop(p, hdrlen); - - u32 seq = ntohl(tcph->seq); - u32 ack = ntohl(tcph->ack_seq); - DBG("TCP %08x %08x %04x %04x seq=%u+%u ack=%u%s%s%s%s%s%s\n", - ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest), seq, pkt_len(p), ack, - (tcph->fin ? " FIN" : ""), - (tcph->syn ? " SYN" : ""), - (tcph->rst ? " RST" : ""), - (tcph->psh ? " PSH" : ""), - (tcph->ack ? " ACK" : ""), - (tcph->urg ? " URG" : "")); - - struct flow *f; - struct pipe *a, *b; - if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest)) - { - a = &f->pipe[0]; - b = &f->pipe[1]; - } - else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source)) - { - a = &f->pipe[1]; - b = &f->pipe[0]; - } - else - { - /* Flow not found, if it's a SYN packet, go create it */ - if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin) - { - f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest); - f->appl = &appl_sink; - f->appl->open(f); - a = &f->pipe[0]; - b = &f->pipe[1]; - list_init(&a->queue); - a->syn_or_fin_seq = a->last_acked_seq = seq; - a->state = FLOW_SYN_SENT; - list_init(&b->queue); - b->state = FLOW_IDLE; - DBG("\t%p NEW\n", f); - goto drop; - } - DBG("\tUnmatched\n"); - pkt_account(&stat_tcp_unmatched, p); - goto drop; - } - - 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]); - if (a->state == FLOW_FINISHED && b->state == FLOW_FINISHED) - { - DBG("closed\n"); - pkt_account(&stat_tcp_on_closed, p); - goto drop; - } - - if (tcph->rst) - { - DBG("RESET\n"); - f->appl->close(f, CAUSE_RESET); - a->state = b->state = FLOW_FINISHED; - flow_set_timeout(f, now + 300); /* FIXME */ - goto drop; - } - - flow_set_timeout(f, now + 600); /* FIXME */ - - if (tcph->syn) - { - if (tcph->fin || pkt_len(p)) - goto inval; - if (tcph->ack) - { /* SYN ACK */ - if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack) - { - DBG("SYN ACK\n"); - a->last_acked_seq = ack; - a->syn_or_fin_seq = seq; - a->state = FLOW_SYN_SENT_ACK; - b->last_acked_seq = seq; - goto drop; - } - else if (b->state == FLOW_ESTABLISHED) - goto dup; - else - goto unex; - } - else - goto dup; /* otherwise SYN on already existing connection gets ignored */ - } - - if (tcph->ack) - { - if (tcp_seq_le(ack, a->last_acked_seq)) - DBG("DUP ACK, "); - else - { - struct pkt *q; - a->last_acked_seq = ack; - while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack)) - { - list_remove(&q->n); - DBG("data(%Ld-%Ld), ", a->stat_in.bytes, a->stat_in.bytes+pkt_len(q)-1); - pkt_account(&a->stat_in, q); - f->appl->input(f, (a == &f->pipe[1]), q); - } - if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack) - { - a->state = b->state = FLOW_ESTABLISHED; - DBG("ACKED SYN, "); - } - else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack) - { - b->state = FLOW_FINISHED; - if (a->state == FLOW_FINISHED) - { - DBG("CLOSED BOTH WAYS\n"); - f->appl->close(f, CAUSE_CLOSE); - flow_set_timeout(f, now + 300); /* FIXME */ - goto drop; - } - else - DBG("CLOSED ONE-WAY, "); - } - else if ((q = list_head(&a->queue)) && tcp_seq_lt(ack, q->seq)) - { - DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n"); - goto invalid; - } - else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT) - goto unex; - } - } - - if (tcph->fin) - { - if (a->state == FLOW_ESTABLISHED) - { - a->state = FLOW_FIN_SENT; - a->syn_or_fin_seq = seq; - DBG("FIN SENT, waiting for FIN ACK, "); - } - else if (a->state == FLOW_FIN_SENT) - ; - else - goto unex; - } - - if (!pkt_len(p)) - { - DBG("EMPTY\n"); - goto drop; - } - - if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED) - { - p->seq = seq; - tcp_enqueue_data(b, p); - return; - } - else - goto unex; - - drop: - pkt_free(p); - return; - - dup: - DBG("DUP\n"); - goto drop; - - unex: - DBG("UNEXPECTED\n"); - goto drop; - - inval: - DBG("???\n"); - invalid: - pkt_account(&stat_tcp_invalid, p); - goto drop; -} - -/*** IP LAYER ***/ - -static struct pkt_stats stat_ip_in, stat_ip_invalid, stat_ip_uninteresting, stat_ip_fragmented, stat_ip_badsum; - -static void ip_got_packet(struct pkt *p) -{ - struct iphdr *iph; - - pkt_account(&stat_ip_in, p); - if (!(iph = pkt_peek(p, sizeof(*iph)))) - goto invalid; - if (iph->ihl < 5) - goto invalid; - if (iph->version != 4) - goto invalid; - uns hdrlen = 4*iph->ihl; - if (pkt_len(p) < hdrlen) - goto invalid; - if (!tcpip_verify_checksum(tcpip_calc_checksum(p->data, hdrlen, 0))) - { - pkt_account(&stat_ip_badsum, p); - goto drop; - } - uns len = ntohs(iph->tot_len); - if (len < hdrlen || len > pkt_len(p)) - goto invalid; - pkt_unappend(p, pkt_len(p) - len); - pkt_pop(p, hdrlen); - - if (iph->protocol != IPPROTO_TCP) - { - pkt_account(&stat_ip_uninteresting, p); - goto drop; - } - /* XXX: Fragmentation not supported yet, but well-behaved TCP stacks don't use it anyway */ - if (ntohs(iph->frag_off) & 0x3fff) - { - pkt_account(&stat_ip_fragmented, p); - goto drop; - } - tcp_got_packet(iph, p); - return; - - invalid: - pkt_account(&stat_ip_invalid, p); - drop: - pkt_free(p); -} - -/*** LINK LAYER ***/ - -static struct pkt_stats stat_link_dwarf, stat_link_in, stat_link_unknown, stat_link_arp; - -static void link_eth_got_packet(struct pkt *p) -{ - struct ether_header *eth; - uns etype; - - pkt_account(&stat_link_in, p); - if (!(eth = pkt_pop(p, sizeof(*eth)))) - { - pkt_account(&stat_link_dwarf, p); - return; - } - etype = ntohs(eth->ether_type); - switch (etype) - { - case ETHERTYPE_IP: - ip_got_packet(p); - break; - case ETHERTYPE_ARP: - pkt_account(&stat_link_arp, p); - pkt_free(p); - break; - default: - // printf("Unknown ethertype: %04x\n", etype); - pkt_account(&stat_link_unknown, p); - pkt_free(p); - } -} - /*** PCAP INTERFACE ***/ static void (*link_handler)(struct pkt *); @@ -653,7 +70,7 @@ int main(int argc, char **argv) if (argc != 2) die("Usage: netgrind "); - flow_rehash(); + tcp_init(); if (!(pcap = pcap_open_offline(argv[1], errbuf))) die("Unable to open %s: %s", argv[1], errbuf); @@ -662,7 +79,7 @@ int main(int argc, char **argv) die("Don't know how to handle data link type %d", dlt); if (pcap_loop(pcap, -1, got_pcap_packet, NULL) < 0) die("Capture failed: %s", pcap_geterr(pcap)); - tcp_time_step(~0U); + tcp_cleanup(); #if 0 struct pcap_stat stats; if (pcap_stats(pcap, &stats)) diff --git a/netgrind/netgrind.h b/netgrind/netgrind.h index 60512ca..ab899ec 100644 --- a/netgrind/netgrind.h +++ b/netgrind/netgrind.h @@ -6,3 +6,71 @@ * This software may be freely distributed and used according to the terms * of the GNU General Public License. */ + +/* link.c */ + +extern struct pkt_stats stat_link_dwarf, stat_link_in, stat_link_unknown, stat_link_arp; + +void link_eth_got_packet(struct pkt *p); + +/* ip.c */ + +extern struct pkt_stats stat_ip_in, stat_ip_invalid, stat_ip_uninteresting, stat_ip_fragmented, stat_ip_badsum; + +uns tcpip_calc_checksum(void *data, uns len, uns csum); +uns tcpip_verify_checksum(uns csum); +void ip_got_packet(struct pkt *p); + +/* tcp.c */ + +extern struct pkt_stats stat_tcp_in, stat_tcp_invalid, stat_tcp_badsum, stat_tcp_unmatched, + stat_tcp_on_closed; + +struct pipe { + list queue; /* incoming packets */ + u32 last_acked_seq; /* last sequence number for which I sent ACK */ + u32 syn_or_fin_seq; /* sequence number of SYN/FIN I sent */ + enum { /* very simplified TCP state machine */ + FLOW_IDLE, + FLOW_SYN_SENT, /* sent SYN, waiting for SYN ACK */ + FLOW_SYN_SENT_ACK, /* sent SYN ACK, waiting for first ACK */ + FLOW_ESTABLISHED, /* established state including waiting for ACK of SYN ACK */ + FLOW_FIN_SENT, /* sent FIN, waiting for its ACK */ + FLOW_FINISHED /* closed, ignoring further packets */ + } state; + struct pkt_stats stat_in; +}; + +struct flow { + struct flow *hash_next; + u32 saddr, daddr, sport, dport; + u32 timeout; + uns heap_pos; + struct appl_hooks *appl; + void *appl_data; + struct pipe pipe[2]; +}; + +enum close_cause { + CAUSE_CLOSE, + CAUSE_RESET, + CAUSE_TIMEOUT, + CAUSE_DOOMSDAY +}; + +struct appl_hooks { + void (*open)(struct flow *f, u64 when); + void (*input)(struct flow *f, int dir, struct pkt *p); /* dir0 = sent by initiator */ + void (*close)(struct flow *f, int cause, u64 when); +}; + +struct iphdr; + +void tcp_init(void); +void tcp_cleanup(void); +void tcp_got_packet(struct iphdr *iph, struct pkt *p); + +/* save.c */ + +extern struct appl_hooks appl_save, appl_asave; +extern uns asave_width; diff --git a/netgrind/save.c b/netgrind/save.c new file mode 100644 index 0000000..80754bc --- /dev/null +++ b/netgrind/save.c @@ -0,0 +1,146 @@ +/* + * Netgrind -- Saving to Files + * + * (c) 2003 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU General Public License. + */ + +#include "lib/lib.h" +#include "netgrind/pkt.h" +#include "netgrind/netgrind.h" + +#include +#include +#include + +struct save_state { + FILE *file[2]; +}; + +static void save_open(struct flow *f, u64 when UNUSED) +{ + struct save_state *s = xmalloc(sizeof(*s)); + static uns save_counter; + for (uns dir=0; dir<2; dir++) + { + byte name[256]; + sprintf(name, "flows/%06u-%04x:%d-%04x:%d-%c", save_counter, f->saddr, f->sport, f->daddr, f->dport, 'A' + dir); + if (!(s->file[dir] = fopen(name, "w"))) + die("Unable to create %s: %m", name); + } + f->appl_data = s; + save_counter++; +} + +static void save_close(struct flow *f, int cause UNUSED, u64 when UNUSED) +{ + struct save_state *s = f->appl_data; + fclose(s->file[0]); + fclose(s->file[1]); + xfree(s); +} + +static void save_input(struct flow *f, int dir, struct pkt *p) +{ + struct save_state *s = f->appl_data; + fwrite(p->data, pkt_len(p), 1, s->file[dir]); + pkt_free(p); +} + +struct appl_hooks appl_save = { + .open = save_open, + .input = save_input, + .close = save_close +}; + +uns asave_width = 80; + +struct asave_state { + FILE *file; + u64 start_time; +}; + +static void asave_event(struct asave_state *s, u64 time, byte *msg, ...) +{ + va_list args; + + va_start(args, msg); + time -= s->start_time; + fprintf(s->file, "%04d.%03d ", (int)(time/1000000), (int)(time%1000000)%1000); + vfprintf(s->file, msg, args); + va_end(args); +} + +static void asave_open(struct flow *f, u64 when) +{ + struct asave_state *s = xmalloc(sizeof(*s)); + byte name[256]; + static uns asave_counter; + sprintf(name, "flows/%06u-%04x:%d-%04x:%d", asave_counter++, f->saddr, f->sport, f->daddr, f->dport); + if (!(s->file = fopen(name, "w"))) + die("Unable to create %s: %m", name); + f->appl_data = s; + s->start_time = when; + asave_event(s, when, "Established\n"); +} + +static void asave_close(struct flow *f, int cause, u64 when) +{ + struct asave_state *s = f->appl_data; + static byte *close_reasons[] = { "Closed", "Connection reset", "Timed out", "Doomsday" }; + asave_event(s, when, "%s\n", close_reasons[cause]); + asave_event(s, when, "TX %Ld bytes in %Ld packets, RX %Ld bytes in %Ld packets\n", + f->pipe[0]. +XXXXXXXXXXXXXXXXXXXXX + fclose(s->file); + xfree(s); +} + +static void asave_input(struct flow *f, int dir, struct pkt *p) +{ + struct asave_state *s = f->appl_data; + asave_event(s, p->timestamp, (dir ? ">>> " : "<<< ")); + uns len = pkt_len(p); + uns cnt = 0; + uns last_char = 0; + for (uns i=0; i= asave_width) + { + if (last_char != '\n') + fputc('\\', s->file); + fputc('\n', s->file); + asave_event(s, p->timestamp, (dir ? ">>> " : "<<< ")); + cnt = 0; + } + uns c = p->data[i]; + if (c == '\n') + cnt = ~0U; + else if (c >= 0x20 && c < 0x7f || c >= 0xa0) + { + fputc(c, s->file); + cnt++; + } + else + { + fprintf(s->file, "<%02x>", c); + cnt += 4; + } + last_char = c; + } + if (cnt) + { + if (last_char != '\n') + fputc('\\', s->file); + fputc('\n', s->file); + } + pkt_free(p); +} + +struct appl_hooks appl_asave = { + .open = asave_open, + .input = asave_input, + .close = asave_close +}; diff --git a/netgrind/tcp.c b/netgrind/tcp.c new file mode 100644 index 0000000..ab912d5 --- /dev/null +++ b/netgrind/tcp.c @@ -0,0 +1,442 @@ +/* + * Netgrind -- TCP Layer Analyser + * + * (c) 2003 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU General Public License. + */ + +#define LOCAL_DEBUG + +#include "lib/lib.h" +#include "lib/heap.h" +#include "netgrind/pkt.h" +#include "netgrind/netgrind.h" + +#include +#include +#include +#include +#include +#include + +/*** TCP LAYER ***/ + +struct pkt_stats stat_tcp_in, stat_tcp_invalid, stat_tcp_badsum, stat_tcp_unmatched, + stat_tcp_on_closed; + +static byte *pipe_state_names[] = { "IDLE", "SYNSENT", "SYNACK", "ESTAB", "FINSENT", "FINISH" }; + +static uns num_flows, max_flows; +static struct flow **flow_hash; +static struct flow **flow_heap; + +static uns flow_calc_hash(u32 saddr, u32 daddr, u32 sport, u32 dport) +{ + saddr = (saddr >> 16) | (saddr << 16); + daddr = (daddr >> 8) | (daddr << 24); + sport <<= 7; + dport <<= 21; + return (saddr + daddr + sport + dport) % max_flows; +} + +#define FLOW_HEAP_LESS(a,b) (a->timeout < b->timeout) +#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) + +static void flow_rehash(void) +{ + uns omax = max_flows; + struct flow **ohash = flow_hash; + + if (flow_heap) + xfree(flow_heap); + if (max_flows) + max_flows = nextprime(2*max_flows); + else + max_flows = 3; + DBG("Rehashing to %d buckets\n", max_flows); + flow_hash = xmalloc_zero(sizeof(struct flow *) * max_flows); + flow_heap = xmalloc_zero(sizeof(struct flow *) * (max_flows+1)); + num_flows = 0; + for (uns i=0; ihash_next; + uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport); + f->hash_next = flow_hash[h]; + flow_hash[h] = f; + flow_heap[++num_flows] = f; + f->heap_pos = num_flows; + f = n; + } + } + if (ohash) + xfree(ohash); + HEAP_INIT(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP); +} + +static struct flow *flow_lookup(u32 saddr, u32 daddr, u32 sport, u32 dport) +{ + uns h = flow_calc_hash(saddr, daddr, sport, dport); + for (struct flow *f = flow_hash[h]; f; f=f->hash_next) + if (f->saddr == saddr && f->daddr == daddr && + f->sport == sport && f->dport == dport) + return f; + return NULL; +} + +static struct flow *flow_create(u32 saddr, u32 daddr, u32 sport, u32 dport) +{ + if (num_flows >= max_flows) + flow_rehash(); + uns h = flow_calc_hash(saddr, daddr, sport, dport); + struct flow *f = xmalloc_zero(sizeof(struct flow)); + f->saddr = saddr; + f->daddr = daddr; + f->sport = sport; + f->dport = dport; + f->timeout = ~0U; + f->hash_next = flow_hash[h]; + flow_hash[h] = f; + flow_heap[++num_flows] = f; + f->heap_pos = num_flows; + return f; +} + +static void flow_set_timeout(struct flow *f, u32 when) +{ + f->timeout = when; + HEAP_CHANGE(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP, f->heap_pos); +} + +static uns flow_now(struct pkt *p) +{ + return p->timestamp >> 20; +} + +static u64 flow_now_to_time(uns now) +{ + return (u64)now << 20; +} + +static inline int tcp_seq_le(u32 a, u32 b) +{ + return ((b - a) < 0x80000000); +} + +static inline int tcp_seq_lt(u32 a, u32 b) +{ + return (a != b && tcp_seq_le(a, b)); +} + +static void tcp_time_step(uns now) +{ + while (num_flows && flow_heap[1]->timeout <= now) + { + struct flow *f = flow_heap[1]; + HEAP_DELMIN(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP); + DBG("TIMEOUT for flow %p(%s/%s)\n", f, pipe_state_names[f->pipe[0].state], pipe_state_names[f->pipe[1].state]); + if (f->pipe[0].state != FLOW_FINISHED || f->pipe[1].state != FLOW_FINISHED) + f->appl->close(f, (now == ~0U) ? CAUSE_DOOMSDAY : CAUSE_TIMEOUT, flow_now_to_time(now)); + uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport); + struct flow **gg = &flow_hash[h]; + for(;;) + { + ASSERT(*gg); + if (*gg == f) + { + *gg = f->hash_next; + break; + } + gg = &(*gg)->hash_next; + } + xfree(f); + } +} + +static void tcp_enqueue_data(struct pipe *b, struct pkt *p) +{ + struct pkt *q, *prev, *new; + u32 last_seq; + + DBG("DATA:"); + if (tcp_seq_lt(b->last_acked_seq, p->seq) && p->seq - b->last_acked_seq >= 0x40000) + { + DBG(" OUT OF WINDOW (last-ack=%u)\n", b->last_acked_seq); + pkt_free(p); + return; + } + prev = (struct pkt *) &b->queue.head; + last_seq = b->last_acked_seq; + while (p) + { + if (tcp_seq_lt(p->seq, last_seq)) + { + if (tcp_seq_le(p->seq + pkt_len(p), last_seq)) + { + DBG(" have\n"); + pkt_free(p); + return; + } + pkt_pop(p, p->seq + pkt_len(p) - last_seq); + p->seq = last_seq; + DBG(" clip"); + } + q = list_next(&b->queue, &prev->n); + if (q && tcp_seq_le(q->seq, p->seq)) + { + /* next packet starts before us => skip it */ + prev = q; + last_seq = q->seq + pkt_len(q); + } + else + { + new = NULL; + if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p))) + { + /* overlap with next packet => split */ + DBG(" split"); + uns keeplen = q->seq - p->seq; + uns newlen = pkt_len(p) - keeplen; + new = pkt_new(0, newlen); + memcpy(pkt_append(new, newlen), pkt_unappend(p, newlen), newlen); + new->seq = p->seq + keeplen; + } + DBG(" insert"); + list_insert(&p->n, &prev->n); + prev = p; + last_seq = p->seq + pkt_len(p); + p = new; + } + } + DBG("\n"); +} + +void tcp_got_packet(struct iphdr *iph, struct pkt *p) +{ + struct tcphdr *tcph; + struct { + u32 src; + u32 dst; + byte zero; + byte proto; + u16 len; + } fakehdr; + uns now = flow_now(p); + + tcp_time_step(now); + + pkt_account(&stat_tcp_in, p); + if (!(tcph = pkt_peek(p, sizeof(*tcph)))) + goto invalid; + uns hdrlen = 4*tcph->doff; + if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p)) + goto invalid; + fakehdr.src = iph->saddr; + fakehdr.dst = iph->daddr; + fakehdr.zero = 0; + fakehdr.proto = IPPROTO_TCP; + fakehdr.len = htons(pkt_len(p)); + uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0); + sum = tcpip_calc_checksum(p->data, pkt_len(p), sum); + if (!tcpip_verify_checksum(sum)) + { + pkt_account(&stat_tcp_badsum, p); + goto drop; + } + /* XXX: Check TCP options? */ + pkt_pop(p, hdrlen); + + u32 seq = ntohl(tcph->seq); + u32 ack = ntohl(tcph->ack_seq); + DBG("TCP %08x %08x %04x %04x seq=%u+%u ack=%u%s%s%s%s%s%s\n", + ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest), seq, pkt_len(p), ack, + (tcph->fin ? " FIN" : ""), + (tcph->syn ? " SYN" : ""), + (tcph->rst ? " RST" : ""), + (tcph->psh ? " PSH" : ""), + (tcph->ack ? " ACK" : ""), + (tcph->urg ? " URG" : "")); + + struct flow *f; + struct pipe *a, *b; + if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest)) + { + a = &f->pipe[0]; + b = &f->pipe[1]; + } + else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source)) + { + a = &f->pipe[1]; + b = &f->pipe[0]; + } + else + { + /* Flow not found, if it's a SYN packet, go create it */ + if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin) + { + f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest); + f->appl = &appl_asave; + f->appl->open(f, p->timestamp); + a = &f->pipe[0]; + b = &f->pipe[1]; + list_init(&a->queue); + a->syn_or_fin_seq = a->last_acked_seq = seq; + a->state = FLOW_SYN_SENT; + list_init(&b->queue); + b->state = FLOW_IDLE; + DBG("\t%p NEW\n", f); + goto drop; + } + DBG("\tUnmatched\n"); + pkt_account(&stat_tcp_unmatched, p); + goto drop; + } + + 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]); + if (a->state == FLOW_FINISHED && b->state == FLOW_FINISHED) + { + DBG("closed\n"); + pkt_account(&stat_tcp_on_closed, p); + goto drop; + } + + if (tcph->rst) + { + DBG("RESET\n"); + f->appl->close(f, CAUSE_RESET, p->timestamp); + a->state = b->state = FLOW_FINISHED; + flow_set_timeout(f, now + 300); /* FIXME */ + goto drop; + } + + flow_set_timeout(f, now + 600); /* FIXME */ + + if (tcph->syn) + { + if (tcph->fin || pkt_len(p)) + goto inval; + if (tcph->ack) + { /* SYN ACK */ + if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack) + { + DBG("SYN ACK\n"); + a->last_acked_seq = ack; + a->syn_or_fin_seq = seq; + a->state = FLOW_SYN_SENT_ACK; + b->last_acked_seq = seq; + goto drop; + } + else if (b->state == FLOW_ESTABLISHED) + goto dup; + else + goto unex; + } + else + goto dup; /* otherwise SYN on already existing connection gets ignored */ + } + + if (tcph->ack) + { + if (tcp_seq_le(ack, a->last_acked_seq)) + DBG("DUP ACK, "); + else + { + struct pkt *q; + a->last_acked_seq = ack; + while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack)) + { + list_remove(&q->n); + q->timestamp = p->timestamp; + DBG("data(%Ld-%Ld), ", a->stat_in.bytes, a->stat_in.bytes+pkt_len(q)-1); + pkt_account(&a->stat_in, q); + f->appl->input(f, (a == &f->pipe[0]), q); + } + if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack) + { + a->state = b->state = FLOW_ESTABLISHED; + DBG("ACKED SYN, "); + } + else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack) + { + b->state = FLOW_FINISHED; + if (a->state == FLOW_FINISHED) + { + DBG("CLOSED BOTH WAYS\n"); + f->appl->close(f, CAUSE_CLOSE, p->timestamp); + flow_set_timeout(f, now + 300); /* FIXME */ + goto drop; + } + else + DBG("CLOSED ONE-WAY, "); + } + else if ((q = list_head(&a->queue)) && tcp_seq_lt(ack, q->seq)) + { + DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n"); + goto invalid; + } + else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT) + goto unex; + } + } + + if (tcph->fin) + { + if (a->state == FLOW_ESTABLISHED) + { + a->state = FLOW_FIN_SENT; + a->syn_or_fin_seq = seq; + DBG("FIN SENT, waiting for FIN ACK, "); + } + else if (a->state == FLOW_FIN_SENT) + ; + else + goto unex; + } + + if (!pkt_len(p)) + { + DBG("EMPTY\n"); + goto drop; + } + + if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED) + { + p->seq = seq; + tcp_enqueue_data(b, p); + return; + } + else + goto unex; + + drop: + pkt_free(p); + return; + + dup: + DBG("DUP\n"); + goto drop; + + unex: + DBG("UNEXPECTED\n"); + goto drop; + + inval: + DBG("???\n"); + invalid: + pkt_account(&stat_tcp_invalid, p); + goto drop; +} + +void tcp_init(void) +{ + flow_rehash(); +} + +void tcp_cleanup(void) +{ + tcp_time_step(~0U); +} -- 2.39.2