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 #define 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;
  28
  29 static byte *pipe_state_names[] = { "IDLE", "SYNSENT", "SYNACK", "ESTAB", "FINSENT", "FINISH" };
  30
  31 static uns num_flows, max_flows;
  32 static struct flow **flow_hash;
  33 static struct flow **flow_heap;
  34
  35 static uns flow_calc_hash(u32 saddr, u32 daddr, u32 sport, u32 dport)
  36 {
  37   saddr = (saddr >> 16) | (saddr << 16);
  38   daddr = (daddr >>  8) | (daddr << 24);
  39   sport <<= 7;
  40   dport <<= 21;
  41   return (saddr + daddr + sport + dport) % max_flows;
  42 }
  43
  44 #define FLOW_HEAP_LESS(a,b) (a->timeout < b->timeout)
  45 #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)
  46
  47 static void flow_rehash(void)
  48 {
  49   uns omax = max_flows;
  50   struct flow **ohash = flow_hash;
  51
  52   if (flow_heap)
  53     xfree(flow_heap);
  54   if (max_flows)
  55     max_flows = nextprime(2*max_flows);
  56   else
  57     max_flows = 3;
  58   DBG("Rehashing to %d buckets\n", max_flows);
  59   flow_hash = xmalloc_zero(sizeof(struct flow *) * max_flows);
  60   flow_heap = xmalloc_zero(sizeof(struct flow *) * (max_flows+1));
  61   num_flows = 0;
  62   for (uns i=0; i<omax; i++)
  63     {
  64       struct flow *f = ohash[i];
  65       while (f)
  66         {
  67           struct flow *n = f->hash_next;
  68           uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
  69           f->hash_next = flow_hash[h];
  70           flow_hash[h] = f;
  71           flow_heap[++num_flows] = f;
  72           f->heap_pos = num_flows;
  73           f = n;
  74         }
  75     }
  76   if (ohash)
  77     xfree(ohash);
  78   HEAP_INIT(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
  79 }
  80
  81 static struct flow *flow_lookup(u32 saddr, u32 daddr, u32 sport, u32 dport)
  82 {
  83   uns h = flow_calc_hash(saddr, daddr, sport, dport);
  84   for (struct flow *f = flow_hash[h]; f; f=f->hash_next)
  85     if (f->saddr == saddr && f->daddr == daddr &&
  86         f->sport == sport && f->dport == dport)
  87       return f;
  88   return NULL;
  89 }
  90
  91 static struct flow *flow_create(u32 saddr, u32 daddr, u32 sport, u32 dport)
  92 {
  93   if (num_flows >= max_flows)
  94     flow_rehash();
  95   uns h = flow_calc_hash(saddr, daddr, sport, dport);
  96   struct flow *f = xmalloc_zero(sizeof(struct flow));
  97   f->saddr = saddr;
  98   f->daddr = daddr;
  99   f->sport = sport;
 100   f->dport = dport;
 101   f->timeout = ~0U;
 102   f->hash_next = flow_hash[h];
 103   flow_hash[h] = f;
 104   flow_heap[++num_flows] = f;
 105   f->heap_pos = num_flows;
 106   return f;
 107 }
 108
 109 static void flow_set_timeout(struct flow *f, u32 when)
 110 {
 111   f->timeout = when;
 112   HEAP_CHANGE(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP, f->heap_pos);
 113 }
 114
 115 static uns flow_now(struct pkt *p)
 116 {
 117   return p->timestamp >> 20;
 118 }
 119
 120 static u64 flow_now_to_time(uns now)
 121 {
 122   return (u64)now << 20;
 123 }
 124
 125 static inline int tcp_seq_le(u32 a, u32 b)
 126 {
 127   return ((b - a) < 0x80000000);
 128 }
 129
 130 static inline int tcp_seq_lt(u32 a, u32 b)
 131 {
 132   return (a != b && tcp_seq_le(a, b));
 133 }
 134
 135 static void tcp_time_step(uns now)
 136 {
 137   while (num_flows && flow_heap[1]->timeout <= now)
 138     {
 139       struct flow *f = flow_heap[1];
 140       HEAP_DELMIN(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
 141       DBG("TIMEOUT for flow %p(%s/%s)\n", f, pipe_state_names[f->pipe[0].state], pipe_state_names[f->pipe[1].state]);
 142       if (f->pipe[0].state != FLOW_FINISHED || f->pipe[1].state != FLOW_FINISHED)
 143         f->appl->close(f, (now == ~0U) ? CAUSE_DOOMSDAY : CAUSE_TIMEOUT, flow_now_to_time(now));
 144       uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
 145       struct flow **gg = &flow_hash[h];
 146       for(;;)
 147         {
 148           ASSERT(*gg);
 149           if (*gg == f)
 150             {
 151               *gg = f->hash_next;
 152               break;
 153             }
 154           gg = &(*gg)->hash_next;
 155         }
 156       xfree(f);
 157     }
 158 }
 159
 160 static void tcp_enqueue_data(struct pipe *b, struct pkt *p)
 161 {
 162   struct pkt *q, *prev, *new;
 163   u32 last_seq;
 164
 165   DBG("DATA:");
 166   if (tcp_seq_lt(b->last_acked_seq, p->seq) && p->seq - b->last_acked_seq >= 0x40000)
 167     {
 168       DBG(" OUT OF WINDOW (last-ack=%u)\n", b->last_acked_seq);
 169       pkt_free(p);
 170       return;
 171     }
 172   prev = (struct pkt *) &b->queue.head;
 173   last_seq = b->last_acked_seq;
 174   while (p)
 175     {
 176       if (tcp_seq_lt(p->seq, last_seq))
 177         {
 178           if (tcp_seq_le(p->seq + pkt_len(p), last_seq))
 179             {
 180               DBG(" have\n");
 181               pkt_free(p);
 182               return;
 183             }
 184           pkt_pop(p, p->seq + pkt_len(p) - last_seq);
 185           p->seq = last_seq;
 186           DBG(" clip");
 187         }
 188       q = list_next(&b->queue, &prev->n);
 189       if (q && tcp_seq_le(q->seq, p->seq))
 190         {
 191           /* next packet starts before us => skip it */
 192           prev = q;
 193           last_seq = q->seq + pkt_len(q);
 194         }
 195       else
 196         {
 197           new = NULL;
 198           if (q && tcp_seq_lt(q->seq, p->seq + pkt_len(p)))
 199             {
 200               /* overlap with next packet => split */
 201               DBG(" split");
 202               uns keeplen = q->seq - p->seq;
 203               uns newlen = pkt_len(p) - keeplen;
 204               new = pkt_new(0, newlen);
 205               memcpy(pkt_append(new, newlen), pkt_unappend(p, newlen), newlen);
 206               new->seq = p->seq + keeplen;
 207             }
 208           DBG(" insert");
 209           list_insert(&p->n, &prev->n);
 210           prev = p;
 211           last_seq = p->seq + pkt_len(p);
 212           p = new;
 213         }
 214     }
 215   DBG("\n");
 216 }
 217
 218 void tcp_got_packet(struct iphdr *iph, struct pkt *p)
 219 {
 220   struct tcphdr *tcph;
 221   struct {
 222     u32 src;
 223     u32 dst;
 224     byte zero;
 225     byte proto;
 226     u16 len;
 227   } fakehdr;
 228   uns now = flow_now(p);
 229
 230   tcp_time_step(now);
 231
 232   pkt_account(&stat_tcp_in, p);
 233   if (!(tcph = pkt_peek(p, sizeof(*tcph))))
 234     goto invalid;
 235   uns hdrlen = 4*tcph->doff;
 236   if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
 237     goto invalid;
 238   fakehdr.src = iph->saddr;
 239   fakehdr.dst = iph->daddr;
 240   fakehdr.zero = 0;
 241   fakehdr.proto = IPPROTO_TCP;
 242   fakehdr.len = htons(pkt_len(p));
 243   uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0);
 244   sum = tcpip_calc_checksum(p->data, pkt_len(p), sum);
 245   if (!tcpip_verify_checksum(sum))
 246     {
 247       pkt_account(&stat_tcp_badsum, p);
 248       goto drop;
 249     }
 250   /* XXX: Check TCP options? */
 251   pkt_pop(p, hdrlen);
 252
 253   u32 seq = ntohl(tcph->seq);
 254   u32 ack = ntohl(tcph->ack_seq);
 255   DBG("TCP %08x %08x %04x %04x seq=%u+%u ack=%u%s%s%s%s%s%s\n",
 256       ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest), seq, pkt_len(p), ack,
 257       (tcph->fin ? " FIN" : ""),
 258       (tcph->syn ? " SYN" : ""),
 259       (tcph->rst ? " RST" : ""),
 260       (tcph->psh ? " PSH" : ""),
 261       (tcph->ack ? " ACK" : ""),
 262       (tcph->urg ? " URG" : ""));
 263
 264   struct flow *f;
 265   struct pipe *a, *b;
 266   if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
 267     {
 268       a = &f->pipe[0];
 269       b = &f->pipe[1];
 270     }
 271   else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
 272     {
 273       a = &f->pipe[1];
 274       b = &f->pipe[0];
 275     }
 276   else
 277     {
 278       /* Flow not found, if it's a SYN packet, go create it */
 279       if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
 280         {
 281           f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest);
 282           f->appl = &appl_asave;
 283           f->appl->open(f, p->timestamp);
 284           a = &f->pipe[0];
 285           b = &f->pipe[1];
 286           list_init(&a->queue);
 287           a->syn_or_fin_seq = a->last_acked_seq = seq;
 288           a->state = FLOW_SYN_SENT;
 289           list_init(&b->queue);
 290           b->state = FLOW_IDLE;
 291           DBG("\t%p NEW\n", f);
 292           goto drop;
 293         }
 294       DBG("\tUnmatched\n");
 295       pkt_account(&stat_tcp_unmatched, p);
 296       goto drop;
 297     }
 298
 299   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]);
 300   if (a->state == FLOW_FINISHED && b->state == FLOW_FINISHED)
 301     {
 302       DBG("closed\n");
 303       pkt_account(&stat_tcp_on_closed, p);
 304       goto drop;
 305     }
 306
 307   if (tcph->rst)
 308     {
 309       DBG("RESET\n");
 310       f->appl->close(f, CAUSE_RESET, p->timestamp);
 311       a->state = b->state = FLOW_FINISHED;
 312       flow_set_timeout(f, now + 300); /* FIXME */
 313       goto drop;
 314     }
 315
 316   flow_set_timeout(f, now + 600); /* FIXME */
 317
 318   if (tcph->syn)
 319     {
 320       if (tcph->fin || pkt_len(p))
 321         goto inval;
 322       if (tcph->ack)
 323         {                       /* SYN ACK */
 324           if (b->state == FLOW_SYN_SENT && b->syn_or_fin_seq+1 == ack)
 325             {
 326               DBG("SYN ACK\n");
 327               a->last_acked_seq = ack;
 328               a->syn_or_fin_seq = seq;
 329               a->state = FLOW_SYN_SENT_ACK;
 330               b->last_acked_seq = seq;
 331               goto drop;
 332             }
 333           else if (b->state == FLOW_ESTABLISHED)
 334             goto dup;
 335           else
 336             goto unex;
 337         }
 338       else
 339         goto dup; /* otherwise SYN on already existing connection gets ignored */
 340     }
 341
 342   if (tcph->ack)
 343     {
 344       if (tcp_seq_le(ack, a->last_acked_seq))
 345         DBG("DUP ACK, ");
 346       else
 347         {
 348           struct pkt *q;
 349           a->last_acked_seq = ack;
 350           while ((q = list_head(&a->queue)) && tcp_seq_le(q->seq+pkt_len(q), ack))
 351             {
 352               list_remove(&q->n);
 353               q->timestamp = p->timestamp;
 354               DBG("data(%Ld-%Ld), ", a->stat_in.bytes, a->stat_in.bytes+pkt_len(q)-1);
 355               pkt_account(&a->stat_in, q);
 356               f->appl->input(f, (a == &f->pipe[0]), q);
 357             }
 358           if (b->state == FLOW_SYN_SENT_ACK && b->syn_or_fin_seq+1 == ack)
 359             {
 360               a->state = b->state = FLOW_ESTABLISHED;
 361               DBG("ACKED SYN, ");
 362             }
 363           else if (b->state == FLOW_FIN_SENT && b->syn_or_fin_seq+1 == ack)
 364             {
 365               b->state = FLOW_FINISHED;
 366               if (a->state == FLOW_FINISHED)
 367                 {
 368                   DBG("CLOSED BOTH WAYS\n");
 369                   f->appl->close(f, CAUSE_CLOSE, p->timestamp);
 370                   flow_set_timeout(f, now + 300); /* FIXME */
 371                   goto drop;
 372                 }
 373               else
 374                 DBG("CLOSED ONE-WAY, ");
 375             }
 376           else if ((q = list_head(&a->queue)) && tcp_seq_lt(ack, q->seq))
 377             {
 378               DBG("DAMNED, ACK FOR UNCAUGHT DATA!\n");
 379               goto invalid;
 380             }
 381           else if (b->state == FLOW_SYN_SENT_ACK || b->state == FLOW_SYN_SENT)
 382             goto unex;
 383         }
 384     }
 385
 386   if (tcph->fin)
 387     {
 388       if (a->state == FLOW_ESTABLISHED)
 389         {
 390           a->state = FLOW_FIN_SENT;
 391           a->syn_or_fin_seq = seq;
 392           DBG("FIN SENT, waiting for FIN ACK, ");
 393         }
 394       else if (a->state == FLOW_FIN_SENT)
 395         ;
 396       else
 397         goto unex;
 398     }
 399
 400   if (!pkt_len(p))
 401     {
 402       DBG("EMPTY\n");
 403       goto drop;
 404     }
 405
 406   if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_FINISHED)
 407     {
 408       p->seq = seq;
 409       tcp_enqueue_data(b, p);
 410       return;
 411     }
 412   else
 413     goto unex;
 414
 415  drop:
 416   pkt_free(p);
 417   return;
 418
 419  dup:
 420   DBG("DUP\n");
 421   goto drop;
 422
 423  unex:
 424   DBG("UNEXPECTED\n");
 425   goto drop;
 426
 427  inval:
 428   DBG("???\n");
 429  invalid:
 430   pkt_account(&stat_tcp_invalid, p);
 431   goto drop;
 432 }
 433
 434 void tcp_init(void)
 435 {
 436   flow_rehash();
 437 }
 438
 439 void tcp_cleanup(void)
 440 {
 441   tcp_time_step(~0U);
 442 }