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 tcp_total_flows;
  29 uns tcp_arrival_times, tcp_wait_for_ack;
  30
  31 struct appl_hooks *tcp_default_appl;
  32
  33 #ifdef LOCAL_DEBUG
  34 static byte *pipe_state_names[] = { "IDLE", "SYNSENT", "SYNACK", "ESTAB", "FINSENT", "FINISH" };
  35 #endif
  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   tcp_total_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 flow_now(struct pkt *p)
 123 {
 124   return p->timestamp >> 20;
 125 }
 126
 127 static u64 flow_now_to_time(uns now)
 128 {
 129   if (now == ~0U)
 130     return ~(u64)0;
 131   else
 132     return (u64)now << 20;
 133 }
 134
 135 static inline int tcp_seq_le(u32 a, u32 b)
 136 {
 137   return ((b - a) < 0x80000000);
 138 }
 139
 140 static inline int tcp_seq_lt(u32 a, u32 b)
 141 {
 142   return (a != b && tcp_seq_le(a, b));
 143 }
 144
 145 static void tcp_time_step(uns now)
 146 {
 147   while (tcp_num_flows && flow_heap[1]->timeout <= now)
 148     {
 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++)
 155         {
 156           struct pkt *p;
 157           while (p = list_head(&f->pipe[i].queue))
 158             {
 159               list_remove(&p->n);
 160               pkt_free(p);
 161             }
 162         }
 163       uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
 164       struct flow **gg = &flow_hash[h];
 165       for(;;)
 166         {
 167           ASSERT(*gg);
 168           if (*gg == f)
 169             {
 170               *gg = f->hash_next;
 171               break;
 172             }
 173           gg = &(*gg)->hash_next;
 174         }
 175       xfree(f);
 176     }
 177 }
 178
 179 static void tcp_enqueue_data(struct pipe *b, struct pkt *p)
 180 {
 181   struct pkt *q, *prev, *new;
 182   u32 last_seq;
 183
 184   DBG("DATA:");
 185   if (tcp_seq_lt(b->queue_start_seq, p->seq) && p->seq - b->queue_start_seq >= 0x40000)
 186     {
 187       DBG(" OUT OF WINDOW (q-start=%u)\n", b->queue_start_seq);
 188       pkt_free(p);
 189       return;
 190     }
 191   prev = (struct pkt *) &b->queue.head;
 192   last_seq = b->last_acked_seq;
 193   while (p)
 194     {
 195       if (tcp_seq_lt(p->seq, last_seq))
 196         {
 197           if (tcp_seq_le(p->seq + pkt_len(p), last_seq))
 198             {
 199               DBG(" have");
 200               pkt_free(p);
 201               return;
 202             }
 203           pkt_pop(p, p->seq + pkt_len(p) - last_seq);
 204           p->seq = last_seq;
 205           DBG(" clip");
 206         }
 207       q = list_next(&b->queue, &prev->n);
 208       if (q && tcp_seq_le(q->seq, p->seq))
 209         {
 210           /* next packet starts before us => skip it */
 211           prev = q;
 212           last_seq = q->seq + pkt_len(q);
 213         }
 214       else
 215         {
 216           new = NULL;
 217           if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p)))
 218             {
 219               /* overlap with next packet => split */
 220               DBG(" 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;
 226             }
 227           DBG(" insert");
 228           list_insert(&p->n, &prev->n);
 229           prev = p;
 230           last_seq = p->seq + pkt_len(p);
 231           p = new;
 232         }
 233     }
 234 }
 235
 236 void tcp_got_packet(struct iphdr *iph, struct pkt *p)
 237 {
 238   struct tcphdr *tcph;
 239   struct {
 240     u32 src;
 241     u32 dst;
 242     byte zero;
 243     byte proto;
 244     u16 len;
 245   } fakehdr;
 246   struct pkt *q;
 247   uns now = flow_now(p);
 248
 249   tcp_time_step(now);
 250
 251   pkt_account(&stat_tcp_in, p);
 252   if (!(tcph = pkt_peek(p, sizeof(*tcph))))
 253     goto invalid;
 254   uns hdrlen = 4*tcph->doff;
 255   if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
 256     goto invalid;
 257   fakehdr.src = iph->saddr;
 258   fakehdr.dst = iph->daddr;
 259   fakehdr.zero = 0;
 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))
 265     {
 266       pkt_account(&stat_tcp_badsum, p);
 267       goto drop;
 268     }
 269   /* XXX: Check TCP options? */
 270
 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" : ""));
 282
 283   struct flow *f;
 284   struct pipe *a, *b;
 285   if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
 286     {
 287       a = &f->pipe[0];
 288       b = &f->pipe[1];
 289     }
 290   else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
 291     {
 292       a = &f->pipe[1];
 293       b = &f->pipe[0];
 294     }
 295   else
 296     {
 297       /* Flow not found, if it's a SYN packet, go create it */
 298       if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
 299         {
 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);
 303           a = &f->pipe[0];
 304           b = &f->pipe[1];
 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);
 312           goto drop;
 313         }
 314       DBG("\tUnmatched\n");
 315       pkt_account(&stat_tcp_unmatched, p);
 316       goto drop;
 317     }
 318   pkt_account(&f->stat_raw, p);
 319   pkt_pop(p, hdrlen);
 320
 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)
 323     {
 324       DBG("closed\n");
 325       pkt_account(&stat_tcp_on_closed, p);
 326       goto drop;
 327     }
 328
 329   if (tcph->rst)
 330     {
 331       DBG("RESET\n");
 332       f->appl->close(f, CAUSE_RESET, p->timestamp);
 333       a->state = b->state = FLOW_FINISHED;
 334       flow_set_timeout(f, now + 120);
 335       goto drop;
 336     }
 337
 338   flow_set_timeout(f, now + 3000);      /* Somewhat arbitrary timeout */
 339
 340   if (tcph->syn)
 341     {
 342       if (tcph->fin || pkt_len(p))
 343         goto inval;
 344       if (tcph->ack)
 345         {                       /* SYN ACK */
 346           if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack)
 347             {
 348               DBG("SYN ACK\n");
 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;
 354               goto drop;
 355             }
 356           else if (b->state == FLOW_ESTABLISHED)
 357             goto dup;
 358           else
 359             goto unex;
 360         }
 361       else
 362         goto dup; /* otherwise SYN on already existing connection gets ignored */
 363     }
 364
 365   if (tcph->ack)
 366     {
 367       if (tcp_seq_le(ack, a->last_acked_seq))
 368         DBG("DUP ACK, ");
 369       else
 370         {
 371           a->last_acked_seq = ack;
 372           if (tcp_wait_for_ack)
 373             {
 374               while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack))
 375                 {
 376                   list_remove(&q->n);
 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);
 383                 }
 384             }
 385           if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack)
 386             {
 387               a->state = b->state = FLOW_ESTABLISHED;
 388               a->queue_start_seq = ack;
 389               DBG("ACKED SYN, ");
 390             }
 391           else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack)
 392             {
 393               b->state = FLOW_FINISHED;
 394               if (a->state == FLOW_FINISHED)
 395                 {
 396                   DBG("CLOSED BOTH WAYS\n");
 397                   f->appl->close(f, CAUSE_CLOSE, p->timestamp);
 398                   flow_set_timeout(f, now + 300); /* FIXME */
 399                   goto drop;
 400                 }
 401               else
 402                 DBG("CLOSED ONE-WAY, ");
 403             }
 404           else if (tcp_seq_lt(a->queue_start_seq, ack))
 405             {
 406               DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n");
 407               goto invalid;
 408             }
 409           else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT)
 410             goto unex;
 411         }
 412     }
 413
 414   if (tcph->fin)
 415     {
 416       if (a->state == FLOW_ESTABLISHED)
 417         {
 418           a->state = FLOW_FIN_SENT;
 419           a->syn_or_fin_seq = seq + pkt_len(p);
 420           DBG("FIN SENT, waiting for FIN ACK, ");
 421         }
 422       else if (a->state == FLOW_FIN_SENT)
 423         ;
 424       else
 425         goto unex;
 426     }
 427
 428   if (!pkt_len(p))
 429     {
 430       DBG("EMPTY\n");
 431       goto drop;
 432     }
 433
 434   if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED)
 435     {
 436       u64 arrival = p->timestamp;
 437       p->seq = seq;
 438       tcp_enqueue_data(b, p);
 439       if (!tcp_wait_for_ack)
 440         {
 441           while ((q = list_head(&b->queue)) && q->seq == b->queue_start_seq)
 442             {
 443               list_remove(&q->n);
 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);
 450             }
 451         }
 452       DBG("\n");
 453       return;
 454     }
 455   else
 456     goto unex;
 457
 458  drop:
 459   pkt_free(p);
 460   return;
 461
 462  dup:
 463   DBG("DUP\n");
 464   goto drop;
 465
 466  unex:
 467   DBG("UNEXPECTED\n");
 468   pkt_account(&stat_tcp_bad_state, p);
 469   goto drop;
 470
 471  inval:
 472   DBG("???\n");
 473  invalid:
 474   pkt_account(&stat_tcp_invalid, p);
 475   goto drop;
 476 }
 477
 478 void tcp_init(void)
 479 {
 480   flow_rehash();
 481 }
 482
 483 void tcp_cleanup(void)
 484 {
 485   tcp_time_step(~0U);
 486 }