netgrind/tcp.c

   1 /*
   2  *      Netgrind -- TCP Layer Analyser
   3  *
   4  *      (c) 2003 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU General Public License.
   8  */
   9
  10 #undef LOCAL_DEBUG
  11
  12 #include "lib/lib.h"
  13 #include "lib/heap.h"
  14 #include "netgrind/pkt.h"
  15 #include "netgrind/netgrind.h"
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <netinet/in.h>
  21 #include <netinet/ip.h>
  22 #include <netinet/tcp.h>
  23
  24 /*** TCP LAYER ***/
  25
  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;
  30
  31 struct appl_hooks *tcp_default_appl;
  32
  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" };
  36
  37 uns tcp_num_flows, tcp_max_flows;
  38 static struct flow **flow_hash;
  39 static struct flow **flow_heap;
  40
  41 static uns flow_calc_hash(u32 saddr, u32 daddr, u32 sport, u32 dport)
  42 {
  43   saddr = (saddr >> 16) | (saddr << 16);
  44   daddr = (daddr >>  8) | (daddr << 24);
  45   sport <<= 7;
  46   dport <<= 21;
  47   return (saddr + daddr + sport + dport) % tcp_max_flows;
  48 }
  49
  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)
  52
  53 static void flow_rehash(void)
  54 {
  55   uns omax = tcp_max_flows;
  56   struct flow **ohash = flow_hash;
  57
  58   if (flow_heap)
  59     xfree(flow_heap);
  60   if (tcp_max_flows)
  61     tcp_max_flows = nextprime(2*tcp_max_flows);
  62   else
  63     tcp_max_flows = 3;
  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));
  67   tcp_num_flows = 0;
  68   for (uns i=0; i<omax; i++)
  69     {
  70       struct flow *f = ohash[i];
  71       while (f)
  72         {
  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];
  76           flow_hash[h] = f;
  77           flow_heap[++tcp_num_flows] = f;
  78           f->heap_pos = tcp_num_flows;
  79           f = n;
  80         }
  81     }
  82   if (ohash)
  83     xfree(ohash);
  84   HEAP_INIT(struct flow *, flow_heap, tcp_num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
  85 }
  86
  87 static struct flow *flow_lookup(u32 saddr, u32 daddr, u32 sport, u32 dport)
  88 {
  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)
  93       return f;
  94   return NULL;
  95 }
  96
  97 static struct flow *flow_create(u32 saddr, u32 daddr, u32 sport, u32 dport)
  98 {
  99   if (tcp_num_flows >= tcp_max_flows)
 100     flow_rehash();
 101   uns h = flow_calc_hash(saddr, daddr, sport, dport);
 102   struct flow *f = xmalloc_zero(sizeof(struct flow));
 103   f->saddr = saddr;
 104   f->daddr = daddr;
 105   f->sport = sport;
 106   f->dport = dport;
 107   f->timeout = ~0U;
 108   f->hash_next = flow_hash[h];
 109   flow_hash[h] = f;
 110   flow_heap[++tcp_num_flows] = f;
 111   f->heap_pos = tcp_num_flows;
 112   cnt_tcp_flows++;
 113   return f;
 114 }
 115
 116 static void flow_set_timeout(struct flow *f, u32 when)
 117 {
 118   f->timeout = when;
 119   HEAP_CHANGE(struct flow *, flow_heap, tcp_num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP, f->heap_pos);
 120 }
 121
 122 static uns timestamp_to_now(u64 timestamp)
 123 {
 124   return timestamp >> 20;
 125 }
 126
 127 static u64 now_to_timestamp(uns now)
 128 {
 129   return (u64)now << 20;
 130 }
 131
 132 static inline int tcp_seq_le(u32 a, u32 b)
 133 {
 134   return ((b - a) < 0x80000000);
 135 }
 136
 137 static inline int tcp_seq_lt(u32 a, u32 b)
 138 {
 139   return (a != b && tcp_seq_le(a, b));
 140 }
 141
 142 static void tcp_time_step(uns now, uns doomsday)
 143 {
 144   while (tcp_num_flows && (flow_heap[1]->timeout <= now || doomsday))
 145     {
 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) now=%d\n", (doomsday ? "DOOMSDAY" : "TIMEOUT"), f,
 149           flow_state_names[f->pipe[0].state], flow_state_names[f->pipe[1].state], now);
 150       if (f->pipe[0].state != FLOW_FINISHED || f->pipe[1].state != FLOW_FINISHED)
 151         {
 152           uns cause;
 153           if (f->cnt_unexpected)
 154             cause = CAUSE_CORRUPT;
 155           else if (doomsday)
 156             cause = CAUSE_DOOMSDAY;
 157           else
 158             cause = CAUSE_TIMEOUT;
 159           cnt_tcp_causes[cause]++;
 160           f->appl->close(f, cause, now_to_timestamp(now));
 161         }
 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];
 166       for(;;)
 167         {
 168           ASSERT(*gg);
 169           if (*gg == f)
 170             {
 171               *gg = f->hash_next;
 172               break;
 173             }
 174           gg = &(*gg)->hash_next;
 175         }
 176       xfree(f);
 177     }
 178 }
 179
 180 static void tcp_enqueue_data(struct pipe *b, struct pkt *p)
 181 {
 182   struct pkt *q, *prev, *new;
 183   u32 last_seq;
 184
 185   DBG("DATA:");
 186   if (tcp_seq_lt(b->queue_start_seq, p->seq) && p->seq - b->queue_start_seq >= 0x40000)
 187     {
 188       DBG(" OUT OF WINDOW (q-start=%u)", b->queue_start_seq);
 189       pkt_free(p);
 190       return;
 191     }
 192   prev = (struct pkt *) &b->queue.head;
 193   last_seq = b->last_acked_seq;
 194   while (p)
 195     {
 196       if (tcp_seq_lt(p->seq, last_seq))
 197         {
 198           if (tcp_seq_le(p->seq + pkt_len(p), last_seq))
 199             {
 200               DBG(" have");
 201               pkt_free(p);
 202               return;
 203             }
 204           pkt_pop(p, p->seq + pkt_len(p) - last_seq);
 205           p->seq = last_seq;
 206           DBG(" clip");
 207         }
 208       q = list_next(&b->queue, &prev->n);
 209       if (q && tcp_seq_le(q->seq, p->seq))
 210         {
 211           /* next packet starts before us => skip it */
 212           prev = q;
 213           last_seq = q->seq + pkt_len(q);
 214         }
 215       else
 216         {
 217           new = NULL;
 218           if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p)))
 219             {
 220               /* overlap with next packet => split */
 221               DBG(" 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;
 227             }
 228           DBG(" insert");
 229           list_insert(&p->n, &prev->n);
 230           prev = p;
 231           last_seq = p->seq + pkt_len(p);
 232           p = new;
 233         }
 234     }
 235 }
 236
 237 void tcp_got_packet(struct iphdr *iph, struct pkt *p)
 238 {
 239   struct tcphdr *tcph;
 240   struct {
 241     u32 src;
 242     u32 dst;
 243     byte zero;
 244     byte proto;
 245     u16 len;
 246   } fakehdr;
 247   struct pkt *q;
 248   uns now = timestamp_to_now(p->timestamp);
 249   struct flow *f = NULL;
 250
 251   tcp_time_step(now, 0);
 252
 253   pkt_account(&stat_tcp_in, p);
 254   if (!(tcph = pkt_peek(p, sizeof(*tcph))))
 255     goto invalid;
 256   uns hdrlen = 4*tcph->doff;
 257   if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
 258     goto invalid;
 259   fakehdr.src = iph->saddr;
 260   fakehdr.dst = iph->daddr;
 261   fakehdr.zero = 0;
 262   fakehdr.proto = IPPROTO_TCP;
 263   fakehdr.len = htons(pkt_len(p));
 264   uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0);
 265   sum = tcpip_calc_checksum(p->data, pkt_len(p), sum);
 266   if (!tcpip_verify_checksum(sum))
 267     {
 268       pkt_account(&stat_tcp_badsum, p);
 269       goto drop;
 270     }
 271   /* XXX: Check TCP options? */
 272
 273   u32 seq = ntohl(tcph->seq);
 274   u32 ack = ntohl(tcph->ack_seq);
 275   DBG("TCP %08x %08x %04x %04x seq=%u len=%u end=%u ack=%u%s%s%s%s%s%s now=%d\n",
 276       ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest),
 277       seq, pkt_len(p) - hdrlen, seq + pkt_len(p) - hdrlen, ack,
 278       (tcph->fin ? " FIN" : ""),
 279       (tcph->syn ? " SYN" : ""),
 280       (tcph->rst ? " RST" : ""),
 281       (tcph->psh ? " PSH" : ""),
 282       (tcph->ack ? " ACK" : ""),
 283       (tcph->urg ? " URG" : ""),
 284       now);
 285
 286   struct pipe *a, *b;
 287   if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
 288     {
 289       a = &f->pipe[0];
 290       b = &f->pipe[1];
 291     }
 292   else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
 293     {
 294       a = &f->pipe[1];
 295       b = &f->pipe[0];
 296     }
 297   else
 298     {
 299       /* Flow not found, if it's a SYN packet, go create it */
 300       if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
 301         {
 302           f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest);
 303           f->appl = tcp_default_appl;
 304           f->appl->open(f, p->timestamp);
 305           a = &f->pipe[0];
 306           b = &f->pipe[1];
 307           list_init(&a->queue);
 308           a->syn_or_fin_seq = a->last_acked_seq = seq;
 309           a->state = FLOW_SYN_SENT;
 310           list_init(&b->queue);
 311           b->state = FLOW_IDLE;
 312           DBG("\t%p NEW\n", f);
 313           pkt_account(&f->stat_raw, p);
 314           goto drop;
 315         }
 316       DBG("\tUnmatched\n");
 317       pkt_account(&stat_tcp_unmatched, p);
 318       goto drop;
 319     }
 320   pkt_account(&f->stat_raw, p);
 321   pkt_pop(p, hdrlen);
 322
 323   DBG("\t%p %s (%s/%s) ", f, (a == &f->pipe[0] ? "A->B" : "B->A"), flow_state_names[f->pipe[0].state], flow_state_names[f->pipe[1].state]);
 324   if (a->state == FLOW_FINISHED && b->state == FLOW_FINISHED)
 325     {
 326       /* XXX: Here we probably should handle SYN (fast recycling of ports) */
 327       DBG("closed\n");
 328       pkt_account(&stat_tcp_on_closed, p);
 329       f = NULL;                      /* Avoid shifting flow timeout */
 330       goto drop;
 331     }
 332
 333   if (tcph->rst)
 334     {
 335       DBG("RESET\n");
 336       cnt_tcp_causes[CAUSE_RESET]++;
 337       f->appl->close(f, CAUSE_RESET, p->timestamp);
 338       a->state = b->state = FLOW_FINISHED;
 339       goto drop;
 340     }
 341
 342   if (tcph->syn)
 343     {
 344       if (tcph->fin || pkt_len(p))
 345         goto inval;
 346       if (tcph->ack)
 347         {                       /* SYN ACK */
 348           if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack)
 349             {
 350               DBG("SYN ACK\n");
 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;
 356               goto drop;
 357             }
 358           else if (b->state == FLOW_ESTABLISHED)
 359             goto dup;
 360           else
 361             goto unex;
 362         }
 363       else
 364         goto dup; /* otherwise SYN on already existing connection gets ignored */
 365     }
 366
 367   if (tcph->ack)
 368     {
 369       if (tcp_seq_le(ack, a->last_acked_seq))
 370         DBG("DUP ACK, ");
 371       else
 372         {
 373           a->last_acked_seq = ack;
 374           if (tcp_wait_for_ack)
 375             {
 376               while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack))
 377                 {
 378                   list_remove(&q->n);
 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);
 385                 }
 386             }
 387           if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack)
 388             {
 389               a->state = b->state = FLOW_ESTABLISHED;
 390               a->queue_start_seq = ack;
 391               DBG("ACKED SYN, ");
 392             }
 393           else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack)
 394             {
 395               b->state = FLOW_FINISHED;
 396               q = pkt_new(0, 0);
 397               q->timestamp = p->timestamp;
 398               f->appl->input(f, (b == &f->pipe[0]), q);
 399               if (a->state == FLOW_FINISHED)
 400                 {
 401                   DBG("CLOSED BOTH WAYS\n");
 402                   cnt_tcp_causes[CAUSE_CLOSE]++;
 403                   f->appl->close(f, CAUSE_CLOSE, p->timestamp);
 404                   goto drop;
 405                 }
 406               else
 407                 DBG("CLOSED ONE-WAY, ");
 408             }
 409           else if (tcp_seq_lt(a->queue_start_seq, ack))
 410             {
 411               DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n");
 412               goto unexpected;
 413             }
 414           else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT)
 415             goto unex;
 416         }
 417     }
 418
 419   if (tcph->fin)
 420     {
 421       if (a->state == FLOW_ESTABLISHED)
 422         {
 423           a->state = FLOW_FIN_SENT;
 424           a->syn_or_fin_seq = seq + pkt_len(p);
 425           DBG("FIN SENT, waiting for FIN ACK, ");
 426         }
 427       else if (a->state == FLOW_FIN_SENT)
 428         ;
 429       else
 430         goto unex;
 431     }
 432
 433   if (!pkt_len(p))
 434     {
 435       DBG("EMPTY\n");
 436       goto drop;
 437     }
 438
 439   if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED)
 440     {
 441       u64 arrival = p->timestamp;
 442       p->seq = seq;
 443       tcp_enqueue_data(b, p);
 444       if (!tcp_wait_for_ack)
 445         {
 446           while ((q = list_head(&b->queue)) && q->seq == b->queue_start_seq)
 447             {
 448               list_remove(&q->n);
 449               if (!tcp_arrival_times)
 450                 q->timestamp = arrival;
 451               DBG(", data(%Ld-%Ld)", b->stat.bytes, b->stat.bytes+pkt_len(q)-1);
 452               pkt_account(&b->stat, q);
 453               b->queue_start_seq += pkt_len(q);
 454               f->appl->input(f, (b == &f->pipe[1]), q);
 455             }
 456         }
 457       DBG("\n");
 458       goto done;
 459     }
 460   else
 461     goto unex;
 462   /* Not reached */
 463
 464  dup:
 465   DBG("DUP\n");
 466  drop:
 467   pkt_free(p);
 468  done:
 469   if (f)
 470     {
 471       int timeout = 60;                 /* Connection setup timeout */
 472       if (f->pipe[0].state == FLOW_FINISHED && f->pipe[1].state == FLOW_FINISHED)
 473         timeout = 30;                   /* After connection close; later the packets are just unmatched */
 474       else if ((f->pipe[0].state == FLOW_ESTABLISHED || f->pipe[0].state == FLOW_FIN_SENT || f->pipe[0].state == FLOW_FINISHED) &&
 475                (f->pipe[1].state == FLOW_ESTABLISHED || f->pipe[1].state == FLOW_FIN_SENT || f->pipe[1].state == FLOW_FINISHED))
 476         timeout = 900;                  /* Data phase timeout */
 477       DBG("timeout at %d\n", now+timeout);
 478       flow_set_timeout(f, now + timeout);
 479     }
 480   return;
 481
 482  unex:
 483   DBG("UNEXPECTED\n");
 484  unexpected:
 485   f->cnt_unexpected++;
 486   pkt_account(&stat_tcp_bad_state, p);
 487   goto drop;
 488
 489  inval:
 490   DBG("???\n");
 491  invalid:
 492   pkt_account(&stat_tcp_invalid, p);
 493   goto drop;
 494 }
 495
 496 void tcp_init(void)
 497 {
 498   flow_rehash();
 499 }
 500
 501 void tcp_cleanup(u64 timestamp)
 502 {
 503   tcp_time_step(timestamp_to_now(timestamp), 1);
 504 }