From 3879155b5112f9dd4677ebc1fb6003175b36ca0b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 7 Jun 2003 13:14:07 +0000 Subject: [PATCH] Hopefully complete TCP analyser. --- lib/lists.h | 14 +++- netgrind/netgrind.c | 166 +++++++++++++++++++++++++++++++++----------- netgrind/pkt.h | 3 +- 3 files changed, 140 insertions(+), 43 deletions(-) diff --git a/lib/lists.h b/lib/lists.h index 2f7cea1..325654a 100644 --- a/lib/lists.h +++ b/lib/lists.h @@ -18,16 +18,26 @@ typedef struct list { struct node head; } list; -static inline void *list_first(list *l) +static inline void *list_head(list *l) { return (l->head.next != &l->head) ? l->head.next : NULL; } -static inline void *list_last(list *l) +static inline void *list_tail(list *l) { return (l->head.prev != &l->head) ? l->head.prev : NULL; } +static inline void *list_next(list *l, node *n) +{ + return (n->next != &l->head) ? (void *) n->next : NULL; +} + +static inline void *list_prev(list *l, node *n) +{ + return (n->prev != &l->head) ? (void *) n->prev : NULL; +} + #define WALK_LIST(n,list) for(n=(void*)(list).head; ((node*)(n))->next != &(list).head; n=(void*)((node*)(n))->next) static inline void list_insert(node *what, node *after) diff --git a/netgrind/netgrind.c b/netgrind/netgrind.c index fda1916..1c1f80e 100644 --- a/netgrind/netgrind.c +++ b/netgrind/netgrind.c @@ -97,6 +97,7 @@ 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 = { @@ -111,18 +112,22 @@ static struct pkt_stats stat_tcp_in, stat_tcp_invalid, stat_tcp_badsum, stat_tcp stat_tcp_on_closed; struct pipe { - list queue; - u32 last_acked_seq; - enum { + 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_CLOSED /* closed, ignoring further packets */ + 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; @@ -222,14 +227,24 @@ 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(%d/%d)\n", f, f->pipe[0].state, f->pipe[1].state); - if (f->pipe[0].state != FLOW_CLOSED || f->pipe[1].state != FLOW_CLOSED) + 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]; @@ -247,6 +262,64 @@ static void tcp_time_step(uns now) } } +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; @@ -316,7 +389,7 @@ static void tcp_got_packet(struct iphdr *iph, struct pkt *p) a = &f->pipe[0]; b = &f->pipe[1]; list_init(&a->queue); - a->last_acked_seq = seq; + a->syn_or_fin_seq = a->last_acked_seq = seq; a->state = FLOW_SYN_SENT; list_init(&b->queue); b->state = FLOW_IDLE; @@ -328,8 +401,8 @@ static void tcp_got_packet(struct iphdr *iph, struct pkt *p) goto drop; } - DBG("\t%p(%d/%d) ", f, a->state, b->state); - if (a->state == FLOW_CLOSED && b->state == FLOW_CLOSED) + 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); @@ -340,7 +413,7 @@ static void tcp_got_packet(struct iphdr *iph, struct pkt *p) { DBG("RESET\n"); f->appl->close(f, CAUSE_RESET); - a->state = b->state = FLOW_CLOSED; + a->state = b->state = FLOW_FINISHED; flow_set_timeout(f, now + 300); /* FIXME */ goto drop; } @@ -353,12 +426,13 @@ static void tcp_got_packet(struct iphdr *iph, struct pkt *p) goto inval; if (tcph->ack) { /* SYN ACK */ - if (b->state == FLOW_SYN_SENT && b->last_acked_seq+1 == ack) + if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack) { DBG("SYN ACK\n"); - b->last_acked_seq = ack; + a->last_acked_seq = ack; + a->syn_or_fin_seq = seq; a->state = FLOW_SYN_SENT_ACK; - a->last_acked_seq = seq; + b->last_acked_seq = seq; goto drop; } else if (b->state == FLOW_ESTABLISHED) @@ -372,31 +446,45 @@ static void tcp_got_packet(struct iphdr *iph, struct pkt *p) if (tcph->ack) { - if (b->state == FLOW_SYN_SENT_ACK && b->last_acked_seq+1 == ack) - { - a->state = b->state = FLOW_ESTABLISHED; - b->last_acked_seq = ack+1; - DBG("ACKED SYN, "); - } - if (b->state == FLOW_FIN_SENT && b->last_acked_seq+1 == ack) + if (tcp_seq_le(ack, a->last_acked_seq)) + DBG("DUP ACK, "); + else { - b->state = FLOW_CLOSED; - if (a->state == FLOW_CLOSED) + struct pkt *q; + a->last_acked_seq = ack; + while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack)) { - DBG("CLOSED BOTH WAYS\n"); - f->appl->close(f, CAUSE_CLOSE); - flow_set_timeout(f, now + 300); /* FIXME */ - goto drop; + 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); } - else - DBG("CLOSED ONE-WAY, "); + 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; } - else if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT) - DBG("ACK, "); - else if (b->state == FLOW_CLOSED) - ; - else - goto unex; } if (tcph->fin) @@ -404,7 +492,7 @@ static void tcp_got_packet(struct iphdr *iph, struct pkt *p) if (a->state == FLOW_ESTABLISHED) { a->state = FLOW_FIN_SENT; - a->last_acked_seq = seq; + a->syn_or_fin_seq = seq; DBG("FIN SENT, waiting for FIN ACK, "); } else if (a->state == FLOW_FIN_SENT) @@ -419,12 +507,10 @@ static void tcp_got_packet(struct iphdr *iph, struct pkt *p) goto drop; } - if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_CLOSED) + if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED) { - DBG("DATA\n"); - // list_add_tail(&b->queue, &p->n); /* FIXME */ - if (pkt_len(p)) - f->appl->input(f, (a == &f->pipe[1]), p); + p->seq = seq; + tcp_enqueue_data(b, p); return; } else diff --git a/netgrind/pkt.h b/netgrind/pkt.h index c53946e..0a6afd5 100644 --- a/netgrind/pkt.h +++ b/netgrind/pkt.h @@ -53,10 +53,11 @@ static inline byte *pkt_append(struct pkt *p, uns len) return d; } -static inline void pkt_unappend(struct pkt *p, uns len) +static inline byte *pkt_unappend(struct pkt *p, uns len) { p->stop -= len; ASSERT(p->stop >= p->data); + return p->stop; } struct pkt *pkt_new(uns preroom, uns postroom); -- 2.39.2