2 * Netgrind -- TCP Layer 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/pkt.h"
15 #include "netgrind/netgrind.h"
20 #include <netinet/in.h>
21 #include <netinet/ip.h>
22 #include <netinet/tcp.h>
26 struct pkt_stats stat_tcp_in, stat_tcp_invalid, stat_tcp_badsum, stat_tcp_unmatched,
27 stat_tcp_on_closed, stat_tcp_bad_state;
29 uns tcp_arrival_times, tcp_wait_for_ack;
31 struct appl_hooks *tcp_default_appl;
34 static byte *pipe_state_names[] = { "IDLE", "SYNSENT", "SYNACK", "ESTAB", "FINSENT", "FINISH" };
37 uns tcp_num_flows, tcp_max_flows;
38 static struct flow **flow_hash;
39 static struct flow **flow_heap;
41 static uns flow_calc_hash(u32 saddr, u32 daddr, u32 sport, u32 dport)
43 saddr = (saddr >> 16) | (saddr << 16);
44 daddr = (daddr >> 8) | (daddr << 24);
47 return (saddr + daddr + sport + dport) % tcp_max_flows;
50 #define FLOW_HEAP_LESS(a,b) (a->timeout < b->timeout)
51 #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)
53 static void flow_rehash(void)
55 uns omax = tcp_max_flows;
56 struct flow **ohash = flow_hash;
61 tcp_max_flows = nextprime(2*tcp_max_flows);
64 // DBG("Rehashing to %d buckets\n", tcp_max_flows);
65 flow_hash = xmalloc_zero(sizeof(struct flow *) * tcp_max_flows);
66 flow_heap = xmalloc_zero(sizeof(struct flow *) * (tcp_max_flows+1));
68 for (uns i=0; i<omax; i++)
70 struct flow *f = ohash[i];
73 struct flow *n = f->hash_next;
74 uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
75 f->hash_next = flow_hash[h];
77 flow_heap[++tcp_num_flows] = f;
78 f->heap_pos = tcp_num_flows;
84 HEAP_INIT(struct flow *, flow_heap, tcp_num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
87 static struct flow *flow_lookup(u32 saddr, u32 daddr, u32 sport, u32 dport)
89 uns h = flow_calc_hash(saddr, daddr, sport, dport);
90 for (struct flow *f = flow_hash[h]; f; f=f->hash_next)
91 if (f->saddr == saddr && f->daddr == daddr &&
92 f->sport == sport && f->dport == dport)
97 static struct flow *flow_create(u32 saddr, u32 daddr, u32 sport, u32 dport)
99 if (tcp_num_flows >= tcp_max_flows)
101 uns h = flow_calc_hash(saddr, daddr, sport, dport);
102 struct flow *f = xmalloc_zero(sizeof(struct flow));
108 f->hash_next = flow_hash[h];
110 flow_heap[++tcp_num_flows] = f;
111 f->heap_pos = tcp_num_flows;
116 static void flow_set_timeout(struct flow *f, u32 when)
119 HEAP_CHANGE(struct flow *, flow_heap, tcp_num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP, f->heap_pos);
122 static uns flow_now(struct pkt *p)
124 return p->timestamp >> 20;
127 static u64 flow_now_to_time(uns now)
132 return (u64)now << 20;
135 static inline int tcp_seq_le(u32 a, u32 b)
137 return ((b - a) < 0x80000000);
140 static inline int tcp_seq_lt(u32 a, u32 b)
142 return (a != b && tcp_seq_le(a, b));
145 static void tcp_time_step(uns now)
147 while (tcp_num_flows && flow_heap[1]->timeout <= now)
149 struct flow *f = flow_heap[1];
150 HEAP_DELMIN(struct flow *, flow_heap, tcp_num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
151 DBG("TIMEOUT for flow %p(%s/%s)\n", f, pipe_state_names[f->pipe[0].state], pipe_state_names[f->pipe[1].state]);
152 if (f->pipe[0].state != FLOW_FINISHED || f->pipe[1].state != FLOW_FINISHED)
153 f->appl->close(f, (now == ~0U) ? CAUSE_DOOMSDAY : CAUSE_TIMEOUT, flow_now_to_time(now));
154 for (uns i=0; i<2; i++)
157 while (p = list_head(&f->pipe[i].queue))
163 uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
164 struct flow **gg = &flow_hash[h];
173 gg = &(*gg)->hash_next;
179 static void tcp_enqueue_data(struct pipe *b, struct pkt *p)
181 struct pkt *q, *prev, *new;
185 if (tcp_seq_lt(b->queue_start_seq, p->seq) && p->seq - b->queue_start_seq >= 0x40000)
187 DBG(" OUT OF WINDOW (q-start=%u)\n", b->queue_start_seq);
191 prev = (struct pkt *) &b->queue.head;
192 last_seq = b->last_acked_seq;
195 if (tcp_seq_lt(p->seq, last_seq))
197 if (tcp_seq_le(p->seq + pkt_len(p), last_seq))
203 pkt_pop(p, p->seq + pkt_len(p) - last_seq);
207 q = list_next(&b->queue, &prev->n);
208 if (q && tcp_seq_le(q->seq, p->seq))
210 /* next packet starts before us => skip it */
212 last_seq = q->seq + pkt_len(q);
217 if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p)))
219 /* overlap with next packet => split */
221 uns keeplen = q->seq - p->seq;
222 uns newlen = pkt_len(p) - keeplen;
223 new = pkt_new(0, newlen);
224 memcpy(pkt_append(new, newlen), pkt_unappend(p, newlen), newlen);
225 new->seq = p->seq + keeplen;
228 list_insert(&p->n, &prev->n);
230 last_seq = p->seq + pkt_len(p);
236 void tcp_got_packet(struct iphdr *iph, struct pkt *p)
247 uns now = flow_now(p);
251 pkt_account(&stat_tcp_in, p);
252 if (!(tcph = pkt_peek(p, sizeof(*tcph))))
254 uns hdrlen = 4*tcph->doff;
255 if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
257 fakehdr.src = iph->saddr;
258 fakehdr.dst = iph->daddr;
260 fakehdr.proto = IPPROTO_TCP;
261 fakehdr.len = htons(pkt_len(p));
262 uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0);
263 sum = tcpip_calc_checksum(p->data, pkt_len(p), sum);
264 if (!tcpip_verify_checksum(sum))
266 pkt_account(&stat_tcp_badsum, p);
269 /* XXX: Check TCP options? */
271 u32 seq = ntohl(tcph->seq);
272 u32 ack = ntohl(tcph->ack_seq);
273 DBG("TCP %08x %08x %04x %04x seq=%u len=%u end=%u ack=%u%s%s%s%s%s%s\n",
274 ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest),
275 seq, pkt_len(p) - hdrlen, seq + pkt_len(p) - hdrlen, ack,
276 (tcph->fin ? " FIN" : ""),
277 (tcph->syn ? " SYN" : ""),
278 (tcph->rst ? " RST" : ""),
279 (tcph->psh ? " PSH" : ""),
280 (tcph->ack ? " ACK" : ""),
281 (tcph->urg ? " URG" : ""));
285 if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
290 else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
297 /* Flow not found, if it's a SYN packet, go create it */
298 if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
300 f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest);
301 f->appl = tcp_default_appl;
302 f->appl->open(f, p->timestamp);
305 list_init(&a->queue);
306 a->syn_or_fin_seq = a->last_acked_seq = seq;
307 a->state = FLOW_SYN_SENT;
308 list_init(&b->queue);
309 b->state = FLOW_IDLE;
310 DBG("\t%p NEW\n", f);
311 pkt_account(&f->stat_raw, p);
314 DBG("\tUnmatched\n");
315 pkt_account(&stat_tcp_unmatched, p);
318 pkt_account(&f->stat_raw, p);
321 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]);
322 if (a->state == FLOW_FINISHED && b->state == FLOW_FINISHED)
325 pkt_account(&stat_tcp_on_closed, p);
332 f->appl->close(f, CAUSE_RESET, p->timestamp);
333 a->state = b->state = FLOW_FINISHED;
334 flow_set_timeout(f, now + 120);
338 flow_set_timeout(f, now + 3000); /* Somewhat arbitrary timeout */
342 if (tcph->fin || pkt_len(p))
346 if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack)
349 a->last_acked_seq = ack;
350 a->syn_or_fin_seq = seq;
351 a->queue_start_seq = ack;
352 a->state = FLOW_SYN_SENT_ACK;
353 b->last_acked_seq = seq;
356 else if (b->state == FLOW_ESTABLISHED)
362 goto dup; /* otherwise SYN on already existing connection gets ignored */
367 if (tcp_seq_le(ack, a->last_acked_seq))
371 a->last_acked_seq = ack;
372 if (tcp_wait_for_ack)
374 while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack))
377 a->queue_start_seq = q->seq + pkt_len(q);
378 if (!tcp_arrival_times)
379 q->timestamp = p->timestamp;
380 DBG("data(%Ld-%Ld), ", a->stat.bytes, a->stat.bytes+pkt_len(q)-1);
381 pkt_account(&a->stat, q);
382 f->appl->input(f, (a == &f->pipe[0]), q);
385 if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack)
387 a->state = b->state = FLOW_ESTABLISHED;
388 a->queue_start_seq = ack;
391 else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack)
393 b->state = FLOW_FINISHED;
394 if (a->state == FLOW_FINISHED)
396 DBG("CLOSED BOTH WAYS\n");
397 f->appl->close(f, CAUSE_CLOSE, p->timestamp);
398 flow_set_timeout(f, now + 300); /* FIXME */
402 DBG("CLOSED ONE-WAY, ");
404 else if (tcp_seq_lt(a->queue_start_seq, ack))
406 DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n");
409 else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT)
416 if (a->state == FLOW_ESTABLISHED)
418 a->state = FLOW_FIN_SENT;
419 a->syn_or_fin_seq = seq + pkt_len(p);
420 DBG("FIN SENT, waiting for FIN ACK, ");
422 else if (a->state == FLOW_FIN_SENT)
434 if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED)
436 u64 arrival = p->timestamp;
438 tcp_enqueue_data(b, p);
439 if (!tcp_wait_for_ack)
441 while ((q = list_head(&b->queue)) && q->seq == b->queue_start_seq)
444 if (!tcp_arrival_times)
445 q->timestamp = arrival;
446 DBG(", data(%Ld-%Ld)", b->stat.bytes, b->stat.bytes+pkt_len(q)-1);
447 pkt_account(&b->stat, q);
448 b->queue_start_seq += pkt_len(q);
449 f->appl->input(f, (b == &f->pipe[1]), q);
468 pkt_account(&stat_tcp_bad_state, p);
474 pkt_account(&stat_tcp_invalid, p);
483 void tcp_cleanup(void)