netgrind/netgrind.c

   1 /*
   2  *      Netgrind -- The Network Traffic 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/netgrind.h"
  15 #include "netgrind/pkt.h"
  16
  17 #include <stdio.h>
  18 #include <stdarg.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <net/ethernet.h>
  22 #include <netinet/in.h>
  23 #include <netinet/ip.h>
  24 #include <netinet/tcp.h>
  25
  26 #include <pcap.h>
  27
  28 void die(byte *msg, ...)
  29 {
  30   va_list args;
  31
  32   va_start(args, msg);
  33   fputs("netgrind: ", stderr);
  34   vfprintf(stderr, msg, args);
  35   fputs("\n", stderr);
  36   exit(1);
  37 }
  38
  39 /*** CHECKSUMMING ***/
  40
  41 static uns tcpip_calc_checksum(void *data, uns len, uns csum)
  42 {
  43   byte *x = data;
  44
  45   while (len >= 2)
  46     {
  47       csum += (x[0] << 8) | x[1];
  48       if (csum & 0xffff0000)
  49         {
  50           csum &= 0x0000ffff;
  51           csum++;
  52         }
  53       x += 2;
  54       len -= 2;
  55     }
  56   if (len)
  57     {
  58       csum += x[0];
  59       if (csum & 0xffff0000)
  60         {
  61           csum &= 0x0000ffff;
  62           csum++;
  63         }
  64     }
  65   return csum;
  66 }
  67
  68 static inline uns tcpip_verify_checksum(uns csum)
  69 {
  70   return (csum == 0xffff);
  71 }
  72
  73 /*** FLOW ANALYSIS ***/
  74
  75 enum close_cause {
  76   CAUSE_CLOSE,
  77   CAUSE_RESET,
  78   CAUSE_TIMEOUT,
  79   CAUSE_DOOMSDAY
  80 };
  81
  82 struct flow;
  83
  84 struct appl_hooks {
  85   void (*open)(struct flow *f);
  86   void (*input)(struct flow *f, int dir, struct pkt *p);
  87   void (*close)(struct flow *f, int cause);
  88 };
  89
  90 static void sink_open(struct flow *f)
  91 {
  92 }
  93
  94 static void sink_close(struct flow *f, int cause)
  95 {
  96 }
  97
  98 static void sink_input(struct flow *f, int dir, struct pkt *p)
  99 {
 100 }
 101
 102 struct appl_hooks appl_sink = {
 103   .open = sink_open,
 104   .input = sink_input,
 105   .close = sink_close
 106 };
 107
 108 /*** TCP LAYER ***/
 109
 110 static struct pkt_stats stat_tcp_in, stat_tcp_invalid, stat_tcp_badsum, stat_tcp_unmatched,
 111   stat_tcp_on_closed;
 112
 113 struct pipe {
 114   list queue;
 115   u32 last_acked_seq;
 116   enum {
 117     FLOW_IDLE,
 118     FLOW_SYN_SENT,                      /* sent SYN, waiting for SYN ACK */
 119     FLOW_SYN_SENT_ACK,                  /* sent SYN ACK, waiting for first ACK */
 120     FLOW_ESTABLISHED,                   /* established state including waiting for ACK of SYN ACK */
 121     FLOW_FIN_SENT,                      /* sent FIN, waiting for its ACK */
 122     FLOW_CLOSED                         /* closed, ignoring further packets */
 123   } state;
 124 };
 125
 126 struct flow {
 127   struct flow *hash_next;
 128   u32 saddr, daddr, sport, dport;
 129   u32 timeout;
 130   uns heap_pos;
 131   struct appl_hooks *appl;
 132   void *appl_data;
 133   struct pipe pipe[2];
 134 };
 135
 136 static uns num_flows, max_flows;
 137 static struct flow **flow_hash;
 138 static struct flow **flow_heap;
 139
 140 static uns flow_calc_hash(u32 saddr, u32 daddr, u32 sport, u32 dport)
 141 {
 142   saddr = (saddr >> 16) | (saddr << 16);
 143   daddr = (daddr >>  8) | (daddr << 24);
 144   sport <<= 7;
 145   dport <<= 21;
 146   return (saddr + daddr + sport + dport) % max_flows;
 147 }
 148
 149 #define FLOW_HEAP_LESS(a,b) (a->timeout < b->timeout)
 150 #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)
 151
 152 static void flow_rehash(void)
 153 {
 154   uns omax = max_flows;
 155   struct flow **ohash = flow_hash;
 156
 157   if (flow_heap)
 158     xfree(flow_heap);
 159   if (max_flows)
 160     max_flows = nextprime(2*max_flows);
 161   else
 162     max_flows = 3;
 163   DBG("Rehashing to %d buckets\n", max_flows);
 164   flow_hash = xmalloc_zero(sizeof(struct flow *) * max_flows);
 165   flow_heap = xmalloc_zero(sizeof(struct flow *) * (max_flows+1));
 166   num_flows = 0;
 167   for (uns i=0; i<omax; i++)
 168     {
 169       struct flow *f = ohash[i];
 170       while (f)
 171         {
 172           struct flow *n = f->hash_next;
 173           uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
 174           f->hash_next = flow_hash[h];
 175           flow_hash[h] = f;
 176           flow_heap[++num_flows] = f;
 177           f->heap_pos = num_flows;
 178           f = n;
 179         }
 180     }
 181   if (ohash)
 182     xfree(ohash);
 183   HEAP_INIT(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
 184 }
 185
 186 static struct flow *flow_lookup(u32 saddr, u32 daddr, u32 sport, u32 dport)
 187 {
 188   uns h = flow_calc_hash(saddr, daddr, sport, dport);
 189   for (struct flow *f = flow_hash[h]; f; f=f->hash_next)
 190     if (f->saddr == saddr && f->daddr == daddr &&
 191         f->sport == sport && f->dport == dport)
 192       return f;
 193   return NULL;
 194 }
 195
 196 static struct flow *flow_create(u32 saddr, u32 daddr, u32 sport, u32 dport)
 197 {
 198   if (num_flows >= max_flows)
 199     flow_rehash();
 200   uns h = flow_calc_hash(saddr, daddr, sport, dport);
 201   struct flow *f = xmalloc_zero(sizeof(struct flow));
 202   f->saddr = saddr;
 203   f->daddr = daddr;
 204   f->sport = sport;
 205   f->dport = dport;
 206   f->timeout = ~0U;
 207   f->hash_next = flow_hash[h];
 208   flow_hash[h] = f;
 209   flow_heap[++num_flows] = f;
 210   f->heap_pos = num_flows;
 211   return f;
 212 }
 213
 214 static void flow_set_timeout(struct flow *f, u32 when)
 215 {
 216   f->timeout = when;
 217   HEAP_CHANGE(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP, f->heap_pos);
 218 }
 219
 220 static uns flow_now(struct pkt *p)
 221 {
 222   return p->timestamp >> 20;
 223 }
 224
 225 static void tcp_time_step(uns now)
 226 {
 227   while (num_flows && flow_heap[1]->timeout <= now)
 228     {
 229       struct flow *f = flow_heap[1];
 230       HEAP_DELMIN(struct flow *, flow_heap, num_flows, FLOW_HEAP_LESS, FLOW_HEAP_SWAP);
 231       DBG("TIMEOUT for flow %p(%d/%d)\n", f, f->pipe[0].state, f->pipe[1].state);
 232       if (f->pipe[0].state != FLOW_CLOSED || f->pipe[1].state != FLOW_CLOSED)
 233         f->appl->close(f, (now == ~0U) ? CAUSE_DOOMSDAY : CAUSE_TIMEOUT);
 234       uns h = flow_calc_hash(f->saddr, f->daddr, f->sport, f->dport);
 235       struct flow **gg = &flow_hash[h];
 236       for(;;)
 237         {
 238           ASSERT(*gg);
 239           if (*gg == f)
 240             {
 241               *gg = f->hash_next;
 242               break;
 243             }
 244           gg = &(*gg)->hash_next;
 245         }
 246       xfree(f);
 247     }
 248 }
 249
 250 static void tcp_got_packet(struct iphdr *iph, struct pkt *p)
 251 {
 252   struct tcphdr *tcph;
 253   struct {
 254     u32 src;
 255     u32 dst;
 256     byte zero;
 257     byte proto;
 258     u16 len;
 259   } fakehdr;
 260   uns now = flow_now(p);
 261
 262   tcp_time_step(now);
 263
 264   pkt_account(&stat_tcp_in, p);
 265   if (!(tcph = pkt_peek(p, sizeof(*tcph))))
 266     goto invalid;
 267   uns hdrlen = 4*tcph->doff;
 268   if (hdrlen < sizeof(*tcph) || hdrlen > pkt_len(p))
 269     goto invalid;
 270   fakehdr.src = iph->saddr;
 271   fakehdr.dst = iph->daddr;
 272   fakehdr.zero = 0;
 273   fakehdr.proto = IPPROTO_TCP;
 274   fakehdr.len = htons(pkt_len(p));
 275   uns sum = tcpip_calc_checksum(&fakehdr, sizeof(fakehdr), 0);
 276   sum = tcpip_calc_checksum(p->data, pkt_len(p), sum);
 277   if (!tcpip_verify_checksum(sum))
 278     {
 279       pkt_account(&stat_tcp_badsum, p);
 280       goto drop;
 281     }
 282   /* XXX: Check TCP options? */
 283   pkt_pop(p, hdrlen);
 284
 285   u32 seq = ntohl(tcph->seq);
 286   u32 ack = ntohl(tcph->ack_seq);
 287   DBG("TCP %08x %08x %04x %04x seq=%u+%u ack=%u%s%s%s%s%s%s\n",
 288       ntohl(iph->saddr), ntohl(iph->daddr), ntohs(tcph->source), ntohs(tcph->dest), seq, pkt_len(p), ack,
 289       (tcph->fin ? " FIN" : ""),
 290       (tcph->syn ? " SYN" : ""),
 291       (tcph->rst ? " RST" : ""),
 292       (tcph->psh ? " PSH" : ""),
 293       (tcph->ack ? " ACK" : ""),
 294       (tcph->urg ? " URG" : ""));
 295
 296   struct flow *f;
 297   struct pipe *a, *b;
 298   if (f = flow_lookup(iph->saddr, iph->daddr, tcph->source, tcph->dest))
 299     {
 300       a = &f->pipe[0];
 301       b = &f->pipe[1];
 302     }
 303   else if (f = flow_lookup(iph->daddr, iph->saddr, tcph->dest, tcph->source))
 304     {
 305       a = &f->pipe[1];
 306       b = &f->pipe[0];
 307     }
 308   else
 309     {
 310       /* Flow not found, if it's a SYN packet, go create it */
 311       if (tcph->syn && !tcph->ack && !tcph->rst && !tcph->fin)
 312         {
 313           f = flow_create(iph->saddr, iph->daddr, tcph->source, tcph->dest);
 314           f->appl = &appl_sink;
 315           f->appl->open(f);
 316           a = &f->pipe[0];
 317           b = &f->pipe[1];
 318           list_init(&a->queue);
 319           a->last_acked_seq = seq;
 320           a->state = FLOW_SYN_SENT;
 321           list_init(&b->queue);
 322           b->state = FLOW_IDLE;
 323           DBG("\t%p NEW\n", f);
 324           goto drop;
 325         }
 326       DBG("\tUnmatched\n");
 327       pkt_account(&stat_tcp_unmatched, p);
 328       goto drop;
 329     }
 330
 331   DBG("\t%p(%d/%d) ", f, a->state, b->state);
 332   if (a->state == FLOW_CLOSED && b->state == FLOW_CLOSED)
 333     {
 334       DBG("closed\n");
 335       pkt_account(&stat_tcp_on_closed, p);
 336       goto drop;
 337     }
 338
 339   if (tcph->rst)
 340     {
 341       DBG("RESET\n");
 342       f->appl->close(f, CAUSE_RESET);
 343       a->state = b->state = FLOW_CLOSED;
 344       flow_set_timeout(f, now + 300); /* FIXME */
 345       goto drop;
 346     }
 347
 348   flow_set_timeout(f, now + 600); /* FIXME */
 349
 350   if (tcph->syn)
 351     {
 352       if (tcph->fin || pkt_len(p))
 353         goto inval;
 354       if (tcph->ack)
 355         {                       /* SYN ACK */
 356           if (b->state == FLOW_SYN_SENT && b->last_acked_seq+1 == ack)
 357             {
 358               DBG("SYN ACK\n");
 359               b->last_acked_seq = ack;
 360               a->state = FLOW_SYN_SENT_ACK;
 361               a->last_acked_seq = seq;
 362               goto drop;
 363             }
 364           else if (b->state == FLOW_ESTABLISHED)
 365             goto dup;
 366           else
 367             goto unex;
 368         }
 369       else
 370         goto dup; /* otherwise SYN on already existing connection gets ignored */
 371     }
 372
 373   if (tcph->ack)
 374     {
 375       if (b->state == FLOW_SYN_SENT_ACK && b->last_acked_seq+1 == ack)
 376         {
 377           a->state = b->state = FLOW_ESTABLISHED;
 378           b->last_acked_seq = ack+1;
 379           DBG("ACKED SYN, ");
 380         }
 381       if (b->state == FLOW_FIN_SENT && b->last_acked_seq+1 == ack)
 382         {
 383           b->state = FLOW_CLOSED;
 384           if (a->state == FLOW_CLOSED)
 385             {
 386               DBG("CLOSED BOTH WAYS\n");
 387               f->appl->close(f, CAUSE_CLOSE);
 388               flow_set_timeout(f, now + 300); /* FIXME */
 389               goto drop;
 390             }
 391           else
 392             DBG("CLOSED ONE-WAY, ");
 393         }
 394       else if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT)
 395         DBG("ACK, ");
 396       else if (b->state == FLOW_CLOSED)
 397         ;
 398       else
 399         goto unex;
 400     }
 401
 402   if (tcph->fin)
 403     {
 404       if (a->state == FLOW_ESTABLISHED)
 405         {
 406           a->state = FLOW_FIN_SENT;
 407           a->last_acked_seq = seq;
 408           DBG("FIN SENT, waiting for FIN ACK, ");
 409         }
 410       else if (a->state == FLOW_FIN_SENT)
 411         ;
 412       else
 413         goto unex;
 414     }
 415
 416   if (!pkt_len(p))
 417     {
 418       DBG("EMPTY\n");
 419       goto drop;
 420     }
 421
 422   if (b->state == FLOW_ESTABLISHED || b->state == FLOW_FIN_SENT || b->state == FLOW_CLOSED)
 423     {
 424       DBG("DATA\n");
 425       // list_add_tail(&b->queue, &p->n); /* FIXME */
 426       if (pkt_len(p))
 427         f->appl->input(f, (a == &f->pipe[1]), p);
 428       return;
 429     }
 430   else
 431     goto unex;
 432
 433  drop:
 434   pkt_free(p);
 435   return;
 436
 437  dup:
 438   DBG("DUP\n");
 439   goto drop;
 440
 441  unex:
 442   DBG("UNEXPECTED\n");
 443   goto drop;
 444
 445  inval:
 446   DBG("???\n");
 447  invalid:
 448   pkt_account(&stat_tcp_invalid, p);
 449   goto drop;
 450 }
 451
 452 /*** IP LAYER ***/
 453
 454 static struct pkt_stats stat_ip_in, stat_ip_invalid, stat_ip_uninteresting, stat_ip_fragmented, stat_ip_badsum;
 455
 456 static void ip_got_packet(struct pkt *p)
 457 {
 458   struct iphdr *iph;
 459
 460   pkt_account(&stat_ip_in, p);
 461   if (!(iph = pkt_peek(p, sizeof(*iph))))
 462     goto invalid;
 463   if (iph->ihl < 5)
 464     goto invalid;
 465   if (iph->version != 4)
 466     goto invalid;
 467   uns hdrlen = 4*iph->ihl;
 468   if (pkt_len(p) < hdrlen)
 469     goto invalid;
 470   if (!tcpip_verify_checksum(tcpip_calc_checksum(p->data, hdrlen, 0)))
 471     {
 472       pkt_account(&stat_ip_badsum, p);
 473       goto drop;
 474     }
 475   uns len = ntohs(iph->tot_len);
 476   if (len < hdrlen || len > pkt_len(p))
 477     goto invalid;
 478   pkt_unappend(p, pkt_len(p) - len);
 479   pkt_pop(p, hdrlen);
 480
 481   if (iph->protocol != IPPROTO_TCP)
 482     {
 483       pkt_account(&stat_ip_uninteresting, p);
 484       goto drop;
 485     }
 486   /* XXX: Fragmentation not supported yet, but well-behaved TCP stacks don't use it anyway */
 487   if (ntohs(iph->frag_off) & 0x3fff)
 488     {
 489       pkt_account(&stat_ip_fragmented, p);
 490       goto drop;
 491     }
 492   tcp_got_packet(iph, p);
 493   return;
 494
 495  invalid:
 496   pkt_account(&stat_ip_invalid, p);
 497  drop:
 498   pkt_free(p);
 499 }
 500
 501 /*** LINK LAYER ***/
 502
 503 static struct pkt_stats stat_link_dwarf, stat_link_in, stat_link_unknown, stat_link_arp;
 504
 505 static void link_eth_got_packet(struct pkt *p)
 506 {
 507   struct ether_header *eth;
 508   uns etype;
 509
 510   pkt_account(&stat_link_in, p);
 511   if (!(eth = pkt_pop(p, sizeof(*eth))))
 512     {
 513       pkt_account(&stat_link_dwarf, p);
 514       return;
 515     }
 516   etype = ntohs(eth->ether_type);
 517   switch (etype)
 518     {
 519     case ETHERTYPE_IP:
 520       ip_got_packet(p);
 521       break;
 522     case ETHERTYPE_ARP:
 523       pkt_account(&stat_link_arp, p);
 524       pkt_free(p);
 525       break;
 526     default:
 527       // printf("Unknown ethertype: %04x\n", etype);
 528       pkt_account(&stat_link_unknown, p);
 529       pkt_free(p);
 530     }
 531 }
 532
 533 /*** PCAP INTERFACE ***/
 534
 535 static void (*link_handler)(struct pkt *);
 536 static struct pkt_stats stat_pcap_incomplete;
 537
 538 static int link_setup_handler(int dlt)
 539 {
 540   switch (dlt)
 541     {
 542     case DLT_EN10MB:    link_handler = link_eth_got_packet; return 1;
 543     default:            return 0;
 544     }
 545 }
 546
 547 static void got_pcap_packet(u_char *userdata UNUSED, const struct pcap_pkthdr *hdr, const u_char *pkt)
 548 {
 549   if (hdr->caplen != hdr->len)
 550     {
 551       stat_pcap_incomplete.packets++;
 552       stat_pcap_incomplete.bytes += hdr->len - hdr->caplen;
 553       return;
 554     }
 555   struct pkt *p = pkt_new(0, hdr->len);
 556   memcpy(pkt_append(p, hdr->len), pkt, hdr->len);
 557   p->timestamp = (u64)hdr->ts.tv_sec * 1000000 + hdr->ts.tv_usec;
 558   link_handler(p);
 559 }
 560
 561 int main(int argc, char **argv)
 562 {
 563   char errbuf[PCAP_ERRBUF_SIZE];
 564   pcap_t *pcap;
 565   int dlt;
 566
 567   if (argc != 2)
 568     die("Usage: netgrind <capture-file>");
 569
 570   flow_rehash();
 571
 572   if (!(pcap = pcap_open_offline(argv[1], errbuf)))
 573     die("Unable to open %s: %s", argv[1], errbuf);
 574   dlt = pcap_datalink(pcap);
 575   if (!link_setup_handler(dlt))
 576     die("Don't know how to handle data link type %d", dlt);
 577   if (pcap_loop(pcap, -1, got_pcap_packet, NULL) < 0)
 578     die("Capture failed: %s", pcap_geterr(pcap));
 579   tcp_time_step(~0U);
 580 #if 0
 581   struct pcap_stat stats;
 582   if (pcap_stats(pcap, &stats))
 583     die("pcap_stats: %s", pcap_geterr(pcap));
 584   printf("libpcap stats: %d packets received, %d dropped\n", stats.ps_recv, stats.ps_drop);
 585 #endif
 586   printf("Pcap: %Ld(%Ld) incomplete\n",
 587          stat_pcap_incomplete.packets, stat_pcap_incomplete.bytes);
 588   printf("Link: %Ld(%Ld) in, %Ld(%Ld) dwarves, %Ld(%Ld) strangers, %Ld(%Ld) ARPs\n",
 589          stat_link_in.packets, stat_link_in.bytes,
 590          stat_link_dwarf.packets, stat_link_dwarf.bytes,
 591          stat_link_unknown.packets, stat_link_unknown.bytes,
 592          stat_link_arp.packets, stat_link_arp.bytes);
 593   printf("IP: %Ld(%Ld) in, %Ld(%Ld) invalid, %Ld(%Ld) boring, %Ld(%Ld) fragmented, %Ld(%Ld) bad checksum\n",
 594          stat_ip_in.packets, stat_ip_in.bytes,
 595          stat_ip_invalid.packets, stat_ip_invalid.bytes,
 596          stat_ip_uninteresting.packets, stat_ip_uninteresting.bytes,
 597          stat_ip_fragmented.packets, stat_ip_fragmented.bytes,
 598          stat_ip_badsum.packets, stat_ip_badsum.bytes);
 599   printf("TCP: %Ld(%Ld) in, %Ld(%Ld) invalid, %Ld(%Ld) bad checksum\n",
 600          stat_tcp_in.packets, stat_tcp_in.bytes,
 601          stat_tcp_invalid.packets, stat_tcp_invalid.bytes,
 602          stat_tcp_badsum.packets, stat_tcp_badsum.bytes);
 603   pcap_close(pcap);
 604   return 0;
 605 }