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 static uns num_flows, 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) % 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 = max_flows;
  56   struct flow **ohash = flow_hash;
  57
  58   if (flow_heap)
  59     xfree(flow_heap);
  60   if (max_flows)
  61     max_flows = nextprime(2*max_flows);
  62   else
  63     max_flows = 3;
  64   // DBG("Rehashing to %d buckets\n", max_flows);
  65   flow_hash = xmalloc_zero(sizeof(struct flow *) * max_flows);
  66   flow_heap = xmalloc_zero(sizeof(struct flow *) * (max_flows+1));
  67   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[++num_flows] = f;
  78           f->heap_pos = num_flows;
  79           f = n;
  80         }
  81     }
  82   if (ohash)
  83     xfree(ohash);
  84   HEAP_INIT(struct flow *, flow_heap, 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 (num_flows >= 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[++num_flows] = f;
 111   f->heap_pos = 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, 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 (num_flows && flow_heap[1]->timeout <= now)
 148     {
 149       struct flow *f = flow_heap[1];
 150       HEAP_DELMIN(struct flow *, flow_heap, 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       uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
 155       struct flow **gg = &flow_hash[h];
 156       for(;;)
 157         {
 158           ASSERT(*gg);
 159           if (*gg == f)
 160             {
 161               *gg = f->hash_next;
 162               break;
 163             }
 164           gg = &(*gg)->hash_next;
 165         }
 166       xfree(f);
 167     }
 168 }
 169
 170 static void tcp_enqueue_data(struct pipe *b, struct pkt *p)
 171 {
 172   struct pkt *q, *prev, *new;
 173   u32 last_seq;
 174
 175   DBG("DATA:");
 176   if (tcp_seq_lt(b->last_acked_seq, p->seq) && p->seq - b->last_acked_seq >= 0x40000)
 177     {
 178       DBG(" OUT OF WINDOW (last-ack=%u)\n", b->last_acked_seq);
 179       pkt_free(p);
 180       return;
 181     }
 182   prev = (struct pkt *) &b->queue.head;
 183   last_seq = b->last_acked_seq;
 184   while (p)
 185     {
 186       if (tcp_seq_lt(p->seq, last_seq))
 187         {
 188           if (tcp_seq_le(p->seq + pkt_len(p), last_seq))
 189             {
 190               DBG(" have");
 191               pkt_free(p);
 192               return;
 193             }
 194           pkt_pop(p, p->seq + pkt_len(p) - last_seq);
 195           p->seq = last_seq;
 196           DBG(" clip");
 197         }
 198       q = list_next(&b->queue, &prev->n);
 199       if (q && tcp_seq_le(q->seq, p->seq))
 200         {
 201           /* next packet starts before us => skip it */
 202           prev = q;
 203           last_seq = q->seq + pkt_len(q);
 204         }
 205       else
 206         {
 207           new = NULL;
 208           if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p)))
 209             {
 210               /* overlap with next packet => split */
 211               DBG(" split");
 212               uns keeplen = q->seq - p->seq;
 213               uns newlen = pkt_len(p) - keeplen;
 214               new = pkt_new(0, newlen);
 215               memcpy(pkt_append(new, newlen), pkt_unappend(p, newlen), newlen);
 216               new->seq = p->seq + keeplen;
 217             }
 218           DBG(" insert");
 219           list_insert(&p->n, &prev->n);
 220           prev = p;
 221           last_seq = p->seq + pkt_len(p);
 222           p = new;
 223         }
 224     }
 225 }
 226
 227 void tcp_got_packet(struct iphdr *iph, struct pkt *p)
 228 {
 229   struct tcphdr *tcph;
 230   struct {
 231     u32 src;
 232     u32 dst;
 233     byte zero;
 234     byte proto;
 235     u16 len;
 236   } fakehdr;
 237   struct pkt *q;
 238   uns now = flow_now(p);
 239
 240   tcp_time_step(now);
 241
 242   pkt_account(&stat_tcp_in, p);
 243   if (!(tcph = pkt_peek(p, sizeof(*tcph))))
 244     goto invalid;
 245   uns hdrlen = 4*tcph->doff;
 246   if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
 247     goto invalid;
 248   fakehdr.src = iph->saddr;
 249   fakehdr.dst = iph->daddr;
 250   fakehdr.zero = 0;
 251   fakehdr.proto = IPPROTO_TCP;
 252   fakehdr.len = htons(pkt_len(p));
 253   uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0);
 254   sum = tcpip_calc_checksum(p->data, pkt_len(p), sum);
 255   if (!tcpip_verify_checksum(sum))
 256     {
 257       pkt_account(&stat_tcp_badsum, p);
 258       goto drop;
 259     }
 260   /* XXX: Check TCP options? */
 261
 262   u32 seq = ntohl(tcph->seq);
 263   u32 ack = ntohl(tcph->ack_seq);
 264   DBG("TCP %08x %08x %04x %04x seq=%u len=%u end=%u ack=%u%s%s%s%s%s%s\n",
 265       ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest),
 266       seq, pkt_len(p) - hdrlen, seq + pkt_len(p) - hdrlen, ack,
 267       (tcph->fin ? " FIN" : ""),
 268       (tcph->syn ? " SYN" : ""),
 269       (tcph->rst ? " RST" : ""),
 270       (tcph->psh ? " PSH" : ""),
 271       (tcph->ack ? " ACK" : ""),
 272       (tcph->urg ? " URG" : ""));
 273
 274   struct flow *f;
 275   struct pipe *a, *b;
 276   if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
 277     {
 278       a = &f->pipe[0];
 279       b = &f->pipe[1];
 280     }
 281   else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
 282     {
 283       a = &f->pipe[1];
 284       b = &f->pipe[0];
 285     }
 286   else
 287     {
 288       /* Flow not found, if it's a SYN packet, go create it */
 289       if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
 290         {
 291           f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest);
 292           f->appl = tcp_default_appl;
 293           f->appl->open(f, p->timestamp);
 294           a = &f->pipe[0];
 295           b = &f->pipe[1];
 296           list_init(&a->queue);
 297           a->syn_or_fin_seq = a->last_acked_seq = seq;
 298           a->state = FLOW_SYN_SENT;
 299           list_init(&b->queue);
 300           b->state = FLOW_IDLE;
 301           DBG("\t%p NEW\n", f);
 302           pkt_account(&f->stat_raw, p);
 303           goto drop;
 304         }
 305       DBG("\tUnmatched\n");
 306       pkt_account(&stat_tcp_unmatched, p);
 307       goto drop;
 308     }
 309   pkt_account(&f->stat_raw, p);
 310   pkt_pop(p, hdrlen);
 311
 312   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]);
 313   if (a->state == FLOW_FINISHED && b->state == FLOW_FINISHED)
 314     {
 315       DBG("closed\n");
 316       pkt_account(&stat_tcp_on_closed, p);
 317       goto drop;
 318     }
 319
 320   if (tcph->rst)
 321     {
 322       DBG("RESET\n");
 323       f->appl->close(f, CAUSE_RESET, p->timestamp);
 324       a->state = b->state = FLOW_FINISHED;
 325       flow_set_timeout(f, now + 120);
 326       goto drop;
 327     }
 328
 329   flow_set_timeout(f, now + 3000);      /* Somewhat arbitrary timeout */
 330
 331   if (tcph->syn)
 332     {
 333       if (tcph->fin || pkt_len(p))
 334         goto inval;
 335       if (tcph->ack)
 336         {                       /* SYN ACK */
 337           if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack)
 338             {
 339               DBG("SYN ACK\n");
 340               a->last_acked_seq = ack;
 341               a->syn_or_fin_seq = seq;
 342               a->queue_start_seq = ack;
 343               a->state = FLOW_SYN_SENT_ACK;
 344               b->last_acked_seq = seq;
 345               goto drop;
 346             }
 347           else if (b->state == FLOW_ESTABLISHED)
 348             goto dup;
 349           else
 350             goto unex;
 351         }
 352       else
 353         goto dup; /* otherwise SYN on already existing connection gets ignored */
 354     }
 355
 356   if (tcph->ack)
 357     {
 358       if (tcp_seq_le(ack, a->last_acked_seq))
 359         DBG("DUP ACK, ");
 360       else
 361         {
 362           a->last_acked_seq = ack;
 363           if (tcp_wait_for_ack)
 364             {
 365               while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack))
 366                 {
 367                   list_remove(&q->n);
 368                   a->queue_start_seq = q->seq + pkt_len(q);
 369                   if (!tcp_arrival_times)
 370                     q->timestamp = p->timestamp;
 371                   DBG("data(%Ld-%Ld), ", a->stat.bytes, a->stat.bytes+pkt_len(q)-1);
 372                   pkt_account(&a->stat, q);
 373                   f->appl->input(f, (a == &f->pipe[0]), q);
 374                 }
 375             }
 376           if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack)
 377             {
 378               a->state = b->state = FLOW_ESTABLISHED;
 379               a->queue_start_seq = ack;
 380               DBG("ACKED SYN, ");
 381             }
 382           else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack)
 383             {
 384               b->state = FLOW_FINISHED;
 385               if (a->state == FLOW_FINISHED)
 386                 {
 387                   DBG("CLOSED BOTH WAYS\n");
 388                   f->appl->close(f, CAUSE_CLOSE, p->timestamp);
 389                   flow_set_timeout(f, now + 300); /* FIXME */
 390                   goto drop;
 391                 }
 392               else
 393                 DBG("CLOSED ONE-WAY, ");
 394             }
 395           else if (tcp_seq_lt(a->queue_start_seq, ack))
 396             {
 397               DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n");
 398               goto invalid;
 399             }
 400           else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT)
 401             goto unex;
 402         }
 403     }
 404
 405   if (tcph->fin)
 406     {
 407       if (a->state == FLOW_ESTABLISHED)
 408         {
 409           a->state = FLOW_FIN_SENT;
 410           a->syn_or_fin_seq = seq + pkt_len(p);
 411           DBG("FIN SENT, waiting for FIN ACK, ");
 412         }
 413       else if (a->state == FLOW_FIN_SENT)
 414         ;
 415       else
 416         goto unex;
 417     }
 418
 419   if (!pkt_len(p))
 420     {
 421       DBG("EMPTY\n");
 422       goto drop;
 423     }
 424
 425   if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED)
 426     {
 427       u64 arrival = p->timestamp;
 428       p->seq = seq;
 429       tcp_enqueue_data(b, p);
 430       if (!tcp_wait_for_ack)
 431         {
 432           while ((q = list_head(&b->queue)) && q->seq == b->queue_start_seq)
 433             {
 434               list_remove(&q->n);
 435               if (!tcp_arrival_times)
 436                 q->timestamp = arrival;
 437               DBG(", data(%Ld-%Ld)", b->stat.bytes, b->stat.bytes+pkt_len(q)-1);
 438               pkt_account(&b->stat, q);
 439               b->queue_start_seq += pkt_len(q);
 440               f->appl->input(f, (b == &f->pipe[1]), q);
 441             }
 442         }
 443       DBG("\n");
 444       return;
 445     }
 446   else
 447     goto unex;
 448
 449  drop:
 450   pkt_free(p);
 451   return;
 452
 453  dup:
 454   DBG("DUP\n");
 455   goto drop;
 456
 457  unex:
 458   DBG("UNEXPECTED\n");
 459   pkt_account(&stat_tcp_bad_state, p);
 460   goto drop;
 461
 462  inval:
 463   DBG("???\n");
 464  invalid:
 465   pkt_account(&stat_tcp_invalid, p);
 466   goto drop;
 467 }
 468
 469 void tcp_init(void)
 470 {
 471   flow_rehash();
 472 }
 473
 474 void tcp_cleanup(void)
 475 {
 476   tcp_time_step(~0U);
 477 }