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;
28 uns cnt_tcp_flows, cnt_tcp_causes[CAUSE_MAX];
29 uns tcp_arrival_times, tcp_wait_for_ack;
31 struct appl_hooks *tcp_default_appl;
33 byte *flow_state_names[] = { "IDLE", "SYNSENT", "SYNACK", "ESTAB", "FINSENT", "FINISH" };
34 byte *flow_cause_names[] = { "Close", "Reset", "Timeout", "Doomsday", "Corrupted" };
35 byte *flow_cause_names_short[] = { "OK", "RE", "TO", "DD", "CO" };
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 timestamp_to_now(u64 timestamp)
124 return timestamp >> 20;
127 static u64 now_to_timestamp(uns now)
129 return (u64)now << 20;
132 static inline int tcp_seq_le(u32 a, u32 b)
134 return ((b - a) < 0x80000000);
137 static inline int tcp_seq_lt(u32 a, u32 b)
139 return (a != b && tcp_seq_le(a, b));
142 static void tcp_time_step(uns now, uns doomsday)
144 while (tcp_num_flows && (flow_heap[1]->timeout <= now || doomsday))
146 struct flow *f = flow_heap[1];
147 HEAP_DELMIN(struct flow *, flow_heap, tcp_num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
148 DBG("%s for flow %p(%s/%s)\n", (doomsday ? "DOOMSDAY" : "TIMEOUT"), f,
149 pipe_state_names[f->pipe[0].state], pipe_state_names[f->pipe[1].state]);
150 if (f->pipe[0].state != FLOW_FINISHED || f->pipe[1].state != FLOW_FINISHED)
153 if (f->cnt_unexpected)
154 cause = CAUSE_CORRUPT;
156 cause = CAUSE_DOOMSDAY;
158 cause = CAUSE_TIMEOUT;
159 cnt_tcp_causes[cause]++;
160 f->appl->close(f, cause, now_to_timestamp(now));
162 for (uns i=0; i<2; i++)
163 pkt_flush_queue(&f->pipe[i].queue);
164 uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
165 struct flow **gg = &flow_hash[h];
174 gg = &(*gg)->hash_next;
180 static void tcp_enqueue_data(struct pipe *b, struct pkt *p)
182 struct pkt *q, *prev, *new;
186 if (tcp_seq_lt(b->queue_start_seq, p->seq) && p->seq - b->queue_start_seq >= 0x40000)
188 DBG(" OUT OF WINDOW (q-start=%u)\n", b->queue_start_seq);
192 prev = (struct pkt *) &b->queue.head;
193 last_seq = b->last_acked_seq;
196 if (tcp_seq_lt(p->seq, last_seq))
198 if (tcp_seq_le(p->seq + pkt_len(p), last_seq))
204 pkt_pop(p, p->seq + pkt_len(p) - last_seq);
208 q = list_next(&b->queue, &prev->n);
209 if (q && tcp_seq_le(q->seq, p->seq))
211 /* next packet starts before us => skip it */
213 last_seq = q->seq + pkt_len(q);
218 if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p)))
220 /* overlap with next packet => split */
222 uns keeplen = q->seq - p->seq;
223 uns newlen = pkt_len(p) - keeplen;
224 new = pkt_new(0, newlen);
225 memcpy(pkt_append(new, newlen), pkt_unappend(p, newlen), newlen);
226 new->seq = p->seq + keeplen;
229 list_insert(&p->n, &prev->n);
231 last_seq = p->seq + pkt_len(p);
237 void tcp_got_packet(struct iphdr *iph, struct pkt *p)
248 uns now = timestamp_to_now(p->timestamp);
250 tcp_time_step(now, 0);
252 pkt_account(&stat_tcp_in, p);
253 if (!(tcph = pkt_peek(p, sizeof(*tcph))))
255 uns hdrlen = 4*tcph->doff;
256 if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
258 fakehdr.src = iph->saddr;
259 fakehdr.dst = iph->daddr;
261 fakehdr.proto = IPPROTO_TCP;
262 fakehdr.len = htons(pkt_len(p));
263 uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0);
264 sum = tcpip_calc_checksum(p->data, pkt_len(p), sum);
265 if (!tcpip_verify_checksum(sum))
267 pkt_account(&stat_tcp_badsum, p);
270 /* XXX: Check TCP options? */
272 u32 seq = ntohl(tcph->seq);
273 u32 ack = ntohl(tcph->ack_seq);
274 DBG("TCP %08x %08x %04x %04x seq=%u len=%u end=%u ack=%u%s%s%s%s%s%s\n",
275 ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest),
276 seq, pkt_len(p) - hdrlen, seq + pkt_len(p) - hdrlen, ack,
277 (tcph->fin ? " FIN" : ""),
278 (tcph->syn ? " SYN" : ""),
279 (tcph->rst ? " RST" : ""),
280 (tcph->psh ? " PSH" : ""),
281 (tcph->ack ? " ACK" : ""),
282 (tcph->urg ? " URG" : ""));
286 if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
291 else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
298 /* Flow not found, if it's a SYN packet, go create it */
299 if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
301 f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest);
302 f->appl = tcp_default_appl;
303 f->appl->open(f, p->timestamp);
306 list_init(&a->queue);
307 a->syn_or_fin_seq = a->last_acked_seq = seq;
308 a->state = FLOW_SYN_SENT;
309 list_init(&b->queue);
310 b->state = FLOW_IDLE;
311 DBG("\t%p NEW\n", f);
312 pkt_account(&f->stat_raw, p);
315 DBG("\tUnmatched\n");
316 pkt_account(&stat_tcp_unmatched, p);
319 pkt_account(&f->stat_raw, p);
322 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]);
323 if (a->state == FLOW_FINISHED && b->state == FLOW_FINISHED)
326 pkt_account(&stat_tcp_on_closed, p);
333 cnt_tcp_causes[CAUSE_RESET]++;
334 f->appl->close(f, CAUSE_RESET, p->timestamp);
335 a->state = b->state = FLOW_FINISHED;
336 flow_set_timeout(f, now + 120);
340 flow_set_timeout(f, now + 3000); /* Somewhat arbitrary timeout */
344 if (tcph->fin || pkt_len(p))
348 if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack)
351 a->last_acked_seq = ack;
352 a->syn_or_fin_seq = seq;
353 a->queue_start_seq = ack;
354 a->state = FLOW_SYN_SENT_ACK;
355 b->last_acked_seq = seq;
358 else if (b->state == FLOW_ESTABLISHED)
364 goto dup; /* otherwise SYN on already existing connection gets ignored */
369 if (tcp_seq_le(ack, a->last_acked_seq))
373 a->last_acked_seq = ack;
374 if (tcp_wait_for_ack)
376 while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack))
379 a->queue_start_seq = q->seq + pkt_len(q);
380 if (!tcp_arrival_times)
381 q->timestamp = p->timestamp;
382 DBG("data(%Ld-%Ld), ", a->stat.bytes, a->stat.bytes+pkt_len(q)-1);
383 pkt_account(&a->stat, q);
384 f->appl->input(f, (a == &f->pipe[0]), q);
387 if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack)
389 a->state = b->state = FLOW_ESTABLISHED;
390 a->queue_start_seq = ack;
393 else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack)
395 b->state = FLOW_FINISHED;
397 q->timestamp = p->timestamp;
398 f->appl->input(f, (b == &f->pipe[0]), q);
399 if (a->state == FLOW_FINISHED)
401 DBG("CLOSED BOTH WAYS\n");
402 cnt_tcp_causes[CAUSE_CLOSE]++;
403 f->appl->close(f, CAUSE_CLOSE, p->timestamp);
404 flow_set_timeout(f, now + 300); /* FIXME */
408 DBG("CLOSED ONE-WAY, ");
410 else if (tcp_seq_lt(a->queue_start_seq, ack))
412 DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n");
415 else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT)
422 if (a->state == FLOW_ESTABLISHED)
424 a->state = FLOW_FIN_SENT;
425 a->syn_or_fin_seq = seq + pkt_len(p);
426 DBG("FIN SENT, waiting for FIN ACK, ");
428 else if (a->state == FLOW_FIN_SENT)
440 if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED)
442 u64 arrival = p->timestamp;
444 tcp_enqueue_data(b, p);
445 if (!tcp_wait_for_ack)
447 while ((q = list_head(&b->queue)) && q->seq == b->queue_start_seq)
450 if (!tcp_arrival_times)
451 q->timestamp = arrival;
452 DBG(", data(%Ld-%Ld)", b->stat.bytes, b->stat.bytes+pkt_len(q)-1);
453 pkt_account(&b->stat, q);
454 b->queue_start_seq += pkt_len(q);
455 f->appl->input(f, (b == &f->pipe[1]), q);
476 pkt_account(&stat_tcp_bad_state, p);
482 pkt_account(&stat_tcp_invalid, p);
491 void tcp_cleanup(u64 timestamp)
493 tcp_time_step(timestamp_to_now(timestamp), 1);