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 #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   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)\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)
 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)\n", 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
 250   tcp_time_step(now, 0);
 251
 252   pkt_account(&stat_tcp_in, p);
 253   if (!(tcph = pkt_peek(p, sizeof(*tcph))))
 254     goto invalid;
 255   uns hdrlen = 4*tcph->doff;
 256   if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
 257     goto invalid;
 258   fakehdr.src = iph->saddr;
 259   fakehdr.dst = iph->daddr;
 260   fakehdr.zero = 0;
 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))
 266     {
 267       pkt_account(&stat_tcp_badsum, p);
 268       goto drop;
 269     }
 270   /* XXX: Check TCP options? */
 271
 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" : ""));
 283
 284   struct flow *f;
 285   struct pipe *a, *b;
 286   if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
 287     {
 288       a = &f->pipe[0];
 289       b = &f->pipe[1];
 290     }
 291   else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
 292     {
 293       a = &f->pipe[1];
 294       b = &f->pipe[0];
 295     }
 296   else
 297     {
 298       /* Flow not found, if it's a SYN packet, go create it */
 299       if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
 300         {
 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);
 304           a = &f->pipe[0];
 305           b = &f->pipe[1];
 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);
 313           goto drop;
 314         }
 315       DBG("\tUnmatched\n");
 316       pkt_account(&stat_tcp_unmatched, p);
 317       goto drop;
 318     }
 319   pkt_account(&f->stat_raw, p);
 320   pkt_pop(p, hdrlen);
 321
 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)
 324     {
 325       DBG("closed\n");
 326       pkt_account(&stat_tcp_on_closed, p);
 327       goto drop;
 328     }
 329
 330   if (tcph->rst)
 331     {
 332       DBG("RESET\n");
 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);
 337       goto drop;
 338     }
 339
 340   flow_set_timeout(f, now + 3000);      /* Somewhat arbitrary timeout */
 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                   flow_set_timeout(f, now + 300); /* FIXME */
 405                   goto drop;
 406                 }
 407               else
 408                 DBG("CLOSED ONE-WAY, ");
 409             }
 410           else if (tcp_seq_lt(a->queue_start_seq, ack))
 411             {
 412               DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n");
 413               goto unexpected;
 414             }
 415           else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT)
 416             goto unex;
 417         }
 418     }
 419
 420   if (tcph->fin)
 421     {
 422       if (a->state == FLOW_ESTABLISHED)
 423         {
 424           a->state = FLOW_FIN_SENT;
 425           a->syn_or_fin_seq = seq + pkt_len(p);
 426           DBG("FIN SENT, waiting for FIN ACK, ");
 427         }
 428       else if (a->state == FLOW_FIN_SENT)
 429         ;
 430       else
 431         goto unex;
 432     }
 433
 434   if (!pkt_len(p))
 435     {
 436       DBG("EMPTY\n");
 437       goto drop;
 438     }
 439
 440   if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED)
 441     {
 442       u64 arrival = p->timestamp;
 443       p->seq = seq;
 444       tcp_enqueue_data(b, p);
 445       if (!tcp_wait_for_ack)
 446         {
 447           while ((q = list_head(&b->queue)) && q->seq == b->queue_start_seq)
 448             {
 449               list_remove(&q->n);
 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);
 456             }
 457         }
 458       DBG("\n");
 459       return;
 460     }
 461   else
 462     goto unex;
 463
 464  drop:
 465   pkt_free(p);
 466   return;
 467
 468  dup:
 469   DBG("DUP\n");
 470   goto drop;
 471
 472  unex:
 473   DBG("UNEXPECTED\n");
 474  unexpected:
 475   f->cnt_unexpected++;
 476   pkt_account(&stat_tcp_bad_state, p);
 477   goto drop;
 478
 479  inval:
 480   DBG("???\n");
 481  invalid:
 482   pkt_account(&stat_tcp_invalid, p);
 483   goto drop;
 484 }
 485
 486 void tcp_init(void)
 487 {
 488   flow_rehash();
 489 }
 490
 491 void tcp_cleanup(u64 timestamp)
 492 {
 493   tcp_time_step(timestamp_to_now(timestamp), 1);
 494 }