chiark / gitweb /
pathmtu/pathmtu.{c,1.in}: New algorithms for path-MTU discovery.
authorMark Wooding <mdw@distorted.org.uk>
Wed, 21 Mar 2012 16:05:00 +0000 (16:05 +0000)
committerMark Wooding <mdw@distorted.org.uk>
Wed, 21 Mar 2012 16:05:00 +0000 (16:05 +0000)
Implement path-MTU discovery using raw sockets rather than Linux's fancy
socket options.  This should improve portability to other systems.

This involves splitting the logic which chooses probe sizes and
determines the resulting MTU from the underlying machinery which
manufactures packets and collects results.

pathmtu/pathmtu.1.in
pathmtu/pathmtu.c

index aca6bd20fb8e2b9a0f976728afbb2fef86d86601..a1eedf76229e366cbea1371d369186965e4cf99f 100644 (file)
@@ -4,7 +4,7 @@
 .\"
 .\" (c) 2008 Straylight/Edgeware.
 .\"
-
+.
 .\"----- Licensing notice ---------------------------------------------------
 .\"
 .\" This file is part of Trivial IP Encryption (TrIPE).
@@ -38,10 +38,20 @@ pathmtu \- discover path MTU to a given host
 .SH "SYNOPSIS"
 .
 .B pathmtu
-.RB [ \-t
-.IR timeout ]
 .RB [ \-H
 .IR header ]
+.RB [ \-m
+.IR method ]
+.br
+       \c
+.RB [ \-r
+.IR retransmit ]
+.RB [ \-g
+.IR factor ]
+.RB [ \-t
+.IR timeout ]
+.br
+       \c
 .I host
 .RI [ port ]
 .
@@ -65,11 +75,29 @@ destination does not need to be listening on the given port \(en indeed,
 it doesn't matter if the port is firewalled.  The default port is 7
 (echo), chosen because if it is active, we'll get an answer.
 .PP
-If the local host or some intermediate router is configured to drop ICMP
-fragmentation-required errors then the discovery attempt will silently
-fail.  It is likely that TCP connections with the destination host will
-fail in unexpected ways if this is the case.  Don't drop
-fragmentation-required errors!
+The
+.B pathmtu
+program attempts to find a correct answer even if ICMP
+fragmentation-required packets are suppressed.  It distinguishes between
+the remote host dropping packets and an intermediate router failing to
+report fragmentation-needed errors by sending a minimum-size packet and
+seeing whether it gets any response to that.
+.PP
+The
+.B pathmtu
+program (currently) contains two different methods for MTU probing.  One
+uses the Linux-specific
+.B IP_MTU
+and
+.B IP_MTU_DISCOVER
+socket options; this works fine even as an unprivileged user.  The other
+uses raw sockets, so it's fairly portable, but
+.B pathmtu
+must be installed setuid-root to work.  (It attempts to create its raw
+sockets as its first action \(en before processing the command line \(en
+and drops privileges immediately afterwards, so the attack surface is
+very tiny.)  The raw sockets method is very slightly more robust:
+specifically, it's much less likely to get confused by delayed errors.
 .PP
 Command-line options are as follows.
 .TP
@@ -84,25 +112,62 @@ Writes tripe's version number to standard output and exits with status
 .B "\-u, \-\-usage"
 Writes a brief usage summary to standard output and exits with status 0.
 .TP
+.BI "\-g, \-\-growth=" factor
+Sets the retransmit interval growth factor.  Each time a packet is
+retransmitted,
+.B pathmtu
+increases the amount of time it waits before retransmitting again by
+this
+.IR factor .
+The default growth factor is 3.
+.TP
+.BI "\-m, \-\-method=" name
+Select the MTU probing method.  The available methods are shown by
+.BR \-\-help .
+The
+.B linux
+method is Linux-specific and might be confused by delayed errors under
+some circumstances, but it's usable by unprivileged users; the
+.B raw
+method is portable but requires
+.B pathmtu
+to be installed setuid-root.
+.TP
+.BI "\-r, \-\-retransmit=" interval
+Sets the initial retransmit interval, in seconds.  If no reply is
+received to a probe within the interval, then a second packet is sent,
+and the retransmit interval increased by the growth factor (see
+.BR \-g ).
+The default initial retransmit interval is 0.333 seconds.
+.TP
 .BI "\-t, \-\-timeout=" timeout
 Sets the time to wait for a reply, in seconds.  If no reply or error is
-received within the timeout, it is assumed that the attempt to send a
-packet was successful.  The timeout can be fractional; the default is
-five seconds.
+received within the timeout, it is assumed that no reply will be
+forthcoming.  If we've ever received a reply from the remote host in the
+past, then
+.B pathmtu
+assumes that a timeout indicates that the packet was too large, but the
+ICMP fragmentation-required error was suppressed as a result of
+administrative incompetence by someone responsible for an intermediate
+router.  Otherwise,
+.B pathmtu
+sends a small packet to settle the question of where packets are being
+dropped: if it doesn't receive a response to this packet either, then it
+assumes that the timeout means that the remote host
+.I did
+receive the packet.  The default timeout is 8 seconds.
 .TP
 .BI "\-H, \-\-header=" header
 Sets the packet header, in hexadecimal.  If you set an explicit port
 number, it may be worth setting the packet header too, so as not to
-alarm anything which might be listening on that port.  The default
-packet contents are a fixed pseudorandomly-generated block of data.
+alarm anything which might be listening on that port.  A sequence number
+(in order to disambiguate replies) and some pseudorandom data are
+appended to the header.  The default header is empty.
 .
 .\"--------------------------------------------------------------------------
 .SH "BUGS"
 .
-The
-.B pathmtu
-program currently only works on Linux.  Code for other operating systems
-is welcome.
+The whole business of probing path MTUs is rather unpleasant.
 .
 .\"--------------------------------------------------------------------------
 .SH "AUTHOR"
index c86397fdcabf9edfcf4e4bce34ec47897c309a87..d347b0dddf20070b938e9301bfba7026c9bde7bf 100644 (file)
 
 /*----- Header files ------------------------------------------------------*/
 
+#if defined(linux)
+#  define _BSD_SOURCE
+#endif
+
 #include "config.h"
 
 #include <errno.h>
+#include <stddef.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <arpa/inet.h>
 #include <netdb.h>
 
+#include <netinet/in_systm.h>
+#include <netinet/ip.h>
+#include <netinet/ip_icmp.h>
+#include <netinet/udp.h>
+
+#include <net/if.h>
+#include <ifaddrs.h>
+#include <sys/ioctl.h>
+
+#include <mLib/alloc.h>
+#include <mLib/bits.h>
 #include <mLib/dstr.h>
 #include <mLib/hex.h>
 #include <mLib/mdwopt.h>
 
 static unsigned char buf[65536];
 
+#define POLY 0x1002d
+
 /*----- Utility functions -------------------------------------------------*/
 
+/* Step a value according to a simple LFSR. */
+#define STEP(q)                                                                \
+  do (q) = ((q) & 0x8000) ? ((q) << 1) ^ POLY : ((q) << 1); while (0)
+
 /* Fill buffer with a constant but pseudorandom string.  Uses a simple
  * LFSR.
  */
@@ -64,77 +86,608 @@ static void fillbuffer(unsigned char *p, size_t sz)
   unsigned int y = 0xbc20;
   const unsigned char *l = p + sz;
   int i;
-#define POLY 0x002d
 
   while (p < l) {
     *p++ = y & 0xff;
-    for (i = 0; i < 8; i++) {
-      if (!(y & 0x8000)) y <<= 1;
-      else  y = (y << 1) ^ POLY;
-    }
+    for (i = 0; i < 8; i++) STEP(y);
   }
 }
 
-/*----- Doing the actual job ----------------------------------------------*/
+/* Convert a string to floating point. */
+static double s2f(const char *s, const char *what)
+{
+  double f;
+  char *q;
 
-#if defined(linux)
+  errno = 0;
+  f = strtod(s, &q);
+  if (errno || *q) die(EXIT_FAILURE, "bad %s", what);
+  return (f);
+}
 
-#ifndef IP_MTU
-#  define IP_MTU 14                    /* Blech! */
-#endif
+/* Convert a floating-point value into a struct timeval. */
+static void f2tv(struct timeval *tv, double t)
+  { tv->tv_sec = t; tv->tv_usec = (t - tv->tv_sec)*MILLION; }
+
+/*----- Main algorithm skeleton -------------------------------------------*/
+
+struct param {
+  unsigned f;                          /* Various flags */
+#define F_VERBOSE 1u                   /*   Give a running commentary */
+  double retx;                         /* Initial retransmit interval */
+  double regr;                         /* Retransmit growth factor */
+  double timeout;                      /* Retransmission timeout */
+  int seqoff;                          /* Offset to write sequence number */
+  const struct probe_ops *pops;                /* Probe algorithm description */
+  struct sockaddr_in sin;              /* Destination address */
+};
+
+struct probestate {
+  const struct param *pp;
+  unsigned q;
+};
+
+struct probe_ops {
+  const char *name;
+  const struct probe_ops *next;
+  size_t statesz;
+  int (*setup)(void *, int, const struct param *);
+  void (*finish)(void *);
+  void (*selprep)(void *, int *, fd_set *);
+  int (*xmit)(void *, int);
+  int (*selproc)(void *, fd_set *, struct probestate *);
+};
+
+#define OPS_CHAIN 0
+
+enum {
+  RC_FAIL = -99,
+  RC_OK = 0,
+  RC_LOWER = -1,
+  RC_HIGHER = -2,
+  RC_NOREPLY = -3
+  /* or a positive MTU upper-bound */
+};
+
+/* Add a file descriptor FD to the set `fd_in', updating `*maxfd'. */
+#define ADDFD(fd) \
+  do { FD_SET(fd, fd_in); if (*maxfd < fd) *maxfd = fd; } while (0)
+
+/* Check whether a buffer contains a packet from our current probe. */
+static int mypacketp(struct probestate *ps,
+                    const unsigned char *p, size_t sz)
+{
+  const struct param *pp = ps->pp;
 
-static int pathmtu(struct sockaddr_in *sin, double to)
+  return (sz >= pp->seqoff + 2 && LOAD16(p + pp->seqoff) == ps->q);
+}
+
+/* See whether MTU is an acceptable MTU value.  Return an appropriate
+ * RC_... code or a new suggested MTU.
+ */
+static int probe(struct probestate *ps, void *st, int mtu)
 {
-  int sk;
+  const struct param *pp = ps->pp;
   fd_set fd_in;
-  int mtu;
-  int i;
-  size_t sz;
-  struct timeval tv, tvproto;
+  struct timeval tv, now, when, done;
+  double timer = pp->retx;
+  int rc, maxfd;
+
+  /* Set up the first retransmit and give-up timers. */
+  gettimeofday(&now, 0);
+  f2tv(&tv, pp->timeout); TV_ADD(&done, &now, &tv);
+  f2tv(&tv, timer); TV_ADD(&when, &now, &tv);
+  if (TV_CMP(&when, >, &done)) when = done;
+
+  /* Send the initial probe. */
+  if (pp->f & F_VERBOSE)
+    moan("sending probe of size %d (seq = %04x)", mtu, ps->q);
+  STEP(ps->q);
+  STORE16(buf + pp->seqoff, ps->q);
+  if ((rc = pp->pops->xmit(st, mtu)) != RC_OK) return (rc);
+
+  for (;;) {
+
+    /* Wait for something interesting to happen. */
+    maxfd = 0; FD_ZERO(&fd_in);
+    pp->pops->selprep(st, &maxfd, &fd_in);
+    TV_SUB(&tv, &when, &now);
+    if (select(maxfd + 1, &fd_in, 0, 0, &tv) < 0) return (RC_FAIL);
+    gettimeofday(&now, 0);
+
+    /* See whether the probe method has any answers for us. */
+    if ((rc = pp->pops->selproc(st, &fd_in, ps)) != RC_OK) return (rc);
+
+    /* If we've waited too long, give up.  If we should retransmit, do
+     * that.
+     */
+    if (TV_CMP(&now, >, &done))
+      return (RC_NOREPLY);
+    else if (TV_CMP(&now, >, &when)) {
+      if (pp->f & F_VERBOSE) moan("re-sending probe of size %d", mtu);
+      if ((rc = pp->pops->xmit(st, mtu)) != RC_OK) return (rc);
+      do {
+       timer *= pp->regr; f2tv(&tv, timer); TV_ADD(&when, &when, &tv);
+      } while (TV_CMP(&when, <, &now));
+      if (TV_CMP(&when, >, &done)) when = done;
+    }
+  }
+}
 
-  tvproto.tv_sec = to; tvproto.tv_usec = (to - tvproto.tv_sec) * 1000000;
+/* Discover the path MTU to the destination address. */
+static int pathmtu(const struct param *pp)
+{
+  int sk;
+  int mtu, lo, hi;
+  int rc, droppy = -1;
+  void *st;
+  struct probestate ps;
+
+  /* Build and connect a UDP socket.  We'll need this to know the local port
+   * number to use if nothing else.  Set other stuff up.
+   */
   if ((sk = socket(PF_INET, SOCK_DGRAM, 0)) < 0) goto fail_0;
-  i = IP_PMTUDISC_DO;
-  if (setsockopt(sk, SOL_IP, IP_MTU_DISCOVER, &i, sizeof(i)))
-    goto fail_1;
-  if (connect(sk, (struct sockaddr *)sin, sizeof(*sin))) goto fail_1;
+  if (connect(sk, (struct sockaddr *)&pp->sin, sizeof(pp->sin))) goto fail_1;
+  st = xmalloc(pp->pops->statesz);
+  if ((mtu = pp->pops->setup(st, sk, pp)) < 0) goto fail_2;
+  ps.pp = pp; ps.q = rand() & 0xffff;
+  lo = 576; hi = mtu;
+
+  /* And now we do a thing which is sort of like a binary search, except that
+   * we also take explicit clues as establishing a new upper bound, and we
+   * try to hug that initially.
+   */
   for (;;) {
-    sz = sizeof(mtu);
-    if (getsockopt(sk, SOL_IP, IP_MTU, &mtu, &sz)) goto fail_1;
-    if (write(sk, buf, mtu - 28) < 0) goto fail_1;
-    FD_SET(sk, &fd_in); tv = tvproto;
-    if (select(sk + 1, &fd_in, 0, 0, &tv) < 0) goto fail_1;
-    if (!FD_ISSET(sk, &fd_in)) break;
-    if (read(sk, &i, 1) >= 0 ||
-       errno == ECONNREFUSED || errno == EHOSTUNREACH)
-      break;
-    if (errno != EMSGSIZE) goto fail_1;
+    rc = probe(&ps, st, mtu);
+    switch (rc) {
+
+      case RC_FAIL:
+       if (pp->f & F_VERBOSE) moan("probe failed");
+       goto fail_3;
+
+      case RC_NOREPLY:
+       /* If we've not seen a dropped packet before then we don't know what
+        * this means yet -- in particular, we don't know which bit of the
+        * network is swallowing packets.  Send a minimum-size probe.  If
+        * that doesn't come back then assume that the remote host is
+        * swallowing our packets.  If it does, then we assume that dropped
+        * packets are a result of ICMP fragmentation-needed reports being
+        * lost or suppressed.
+        */
+       if (pp->f & F_VERBOSE) moan("gave up: black hole detected");
+       if (droppy == -1) {
+         if (pp->f & F_VERBOSE) moan("sending minimum-size probe");
+         switch (probe(&ps, st, lo)) {
+           case RC_FAIL:
+             goto fail_3;
+           case RC_NOREPLY:
+             if (pp->f & F_VERBOSE) {
+               moan("no reply from min-size probe: "
+                    "assume black hole at target");
+             }
+             droppy = 1;
+             break;
+           case RC_HIGHER:
+             if (pp->f & F_VERBOSE) {
+               moan("reply from min-size probe OK: "
+                    "assume black hole in network");
+             }
+             droppy = 0;
+             break;
+           default:
+             if (pp->f & F_VERBOSE)
+               moan("unexpected return code from probe");
+             errno = ENOTCONN;
+             goto fail_3;
+         }
+       }
+
+       if (droppy) goto higher; else goto lower;
+
+      case RC_HIGHER:
+      higher:
+       if (droppy == -1) {
+         if (pp->f & F_VERBOSE)
+           moan("probe returned: remote host is not a black hole");
+         droppy = 0;
+       }
+       if (mtu == hi) {
+         if (pp->f & F_VERBOSE) moan("probe returned: found correct MTU");
+         goto done;
+       }
+       if (pp->f & F_VERBOSE) moan("probe returned: guessing higher");
+       lo = mtu;
+       mtu += (hi - lo + 1)/2;
+       break;
+
+      case RC_LOWER:
+      lower:
+       if (mtu == lo) {
+         if (pp->f & F_VERBOSE) moan("error returned: found correct MTU");
+         goto done;
+       }
+       if (pp->f & F_VERBOSE) moan("error returned: guessing lower");
+       hi = mtu - 1;
+       mtu -= (hi - lo + 1)/2;
+       break;
+
+      default:
+       if (pp->f & F_VERBOSE) moan("error returned with new MTU estimate");
+       mtu = hi = rc;
+       break;
+    }
   }
+
+done:
+  /* Clean up and return our result. */
+  pp->pops->finish(st);
+  xfree(st);
   close(sk);
   return (mtu);
 
+fail_3:
+  pp->pops->finish(st);
+fail_2:
+  xfree(st);
 fail_1:
   close(sk);
 fail_0:
   return (-1);
 }
 
+/*----- Doing it the hard way ---------------------------------------------*/
+
+#if defined(linux) || defined(__OpenBSD__)
+#define IPHDR_SANE
+#endif
+
+#ifdef IPHDR_SANE
+#  define sane_htons htons
+#  define sane_htonl htonl
 #else
+#  define sane_htons
+#  define sane_htonl
+#endif
+
+static int rawicmp = -1, rawudp = -1, rawerr = 0;
+
+#define IPCK_INIT 0xffff
+
+/* Compute an IP checksum over some data.  This is a restartable interface:
+ * initialize A to `IPCK_INIT' for the first call.
+ */
+static unsigned ipcksum(const void *buf, size_t n, unsigned a)
+{
+  unsigned long aa = a ^ 0xffff;
+  const unsigned char *p = buf, *l = p + n;
+
+  while (p < l - 1) { aa += LOAD16_B(p); p += 2; }
+  if (p < l) { aa += (unsigned)(*p) << 8; }
+  do aa = (aa & 0xffff) + (aa >> 16); while (aa >= 0x10000);
+  return (aa == 0xffff ? aa : aa ^ 0xffff);
+}
+
+/* TCP/UDP pseudoheader structure. */
+struct phdr {
+  struct in_addr ph_src, ph_dst;
+  u_char ph_z, ph_p;
+  u_short ph_len;
+};
+
+struct raw_state {
+  struct sockaddr_in me, sin;
+  int sk, rawicmp, rawudp;
+  unsigned q;
+};
+
+static int raw_setup(void *stv, int sk, const struct param *pp)
+{
+  struct raw_state *st = stv;
+  size_t sz;
+  int i, mtu = -1;
+  struct ifaddrs *ifa, *ifaa, *ifap;
+  struct ifreq ifr;
+
+  /* If we couldn't acquire raw sockets, we fail here. */
+  if (rawerr) { errno = rawerr; goto fail_0; }
+  st->rawicmp = rawicmp; st->rawudp = rawudp; st->sk = sk;
+
+  /* Initialize the sequence number. */
+  st->q = rand() & 0xffff;
+
+  /* Snaffle the local and remote address and port number. */
+  st->sin = pp->sin;
+  sz = sizeof(st->me);
+  if (getsockname(sk, (struct sockaddr *)&st->me, &sz))
+    goto fail_0;
+
+  /* There isn't a portable way to force the DF flag onto a packet through
+   * UDP, or even through raw IP, unless we write the entire IP header
+   * ourselves.  This is somewhat annoying, especially since we have an
+   * uphill struggle keeping track of which systems randomly expect which
+   * header fields to be presented in host byte order.  Oh, well.
+   */
+  i = 1;
+  if (setsockopt(rawudp, IPPROTO_IP, IP_HDRINCL, &i, sizeof(i))) goto fail_0;
+
+  /* Find an upper bound on the MTU.  Do two passes over the interface
+   * list.  If we can find matches for our local address then use the
+   * highest one of those; otherwise do a second pass and simply take the
+   * highest MTU of any network interface.
+   */
+  if (getifaddrs(&ifaa)) goto fail_0;
+  for (i = 0; i < 2; i++) {
+    for (ifap = 0, ifa = ifaa; ifa; ifa = ifa->ifa_next) {
+      if (!(ifa->ifa_flags & IFF_UP) || !ifa->ifa_addr ||
+         ifa->ifa_addr->sa_family != AF_INET ||
+         (i == 0 &&
+          ((struct sockaddr_in *)ifa->ifa_addr)->sin_addr.s_addr !=
+               st->me.sin_addr.s_addr) ||
+         (i == 1 && ifap && strcmp(ifap->ifa_name, ifa->ifa_name) == 0) ||
+         strlen(ifa->ifa_name) >= sizeof(ifr.ifr_name))
+       continue;
+      ifap = ifa;
+      strcpy(ifr.ifr_name, ifa->ifa_name);
+      if (ioctl(sk, SIOCGIFMTU, &ifr)) goto fail_1;
+      if (mtu < ifr.ifr_mtu) mtu = ifr.ifr_mtu;
+    }
+    if (mtu > 0) break;
+  }
+  if (mtu < 0) { errno = ENOTCONN; goto fail_1; }
+  freeifaddrs(ifaa);
+
+  /* Done. */
+  return (mtu);
+
+fail_1:
+  freeifaddrs(ifaa);
+fail_0:
+  return (-1);
+}
+
+static void raw_finish(void *stv) { ; }
+
+static void raw_selprep(void *stv, int *maxfd, fd_set *fd_in)
+  { struct raw_state *st = stv; ADDFD(st->sk); ADDFD(st->rawicmp); }
+
+static int raw_xmit(void *stv, int mtu)
+{
+  struct raw_state *st = stv;
+  unsigned char b[65536], *p;
+  struct ip *ip;
+  struct udphdr *udp;
+  struct phdr ph;
+  unsigned ck;
+
+  /* Build the IP header. */
+  ip = (struct ip *)b;
+  ip->ip_v = 4;
+  ip->ip_hl = sizeof(*ip)/4;
+  ip->ip_tos = IPTOS_RELIABILITY;
+  ip->ip_len = sane_htons(mtu);
+  STEP(st->q); ip->ip_id = htons(st->q);
+  ip->ip_off = sane_htons(0 | IP_DF);
+  ip->ip_ttl = 64;
+  ip->ip_p = IPPROTO_UDP;
+  ip->ip_sum = 0;
+  ip->ip_src = st->me.sin_addr;
+  ip->ip_dst = st->sin.sin_addr;
+
+  /* Build a UDP packet in the output buffer. */
+  udp = (struct udphdr *)(ip + 1);
+  udp->uh_sport = st->me.sin_port;
+  udp->uh_dport = st->sin.sin_port;
+  udp->uh_ulen = htons(mtu - sizeof(*ip));
+  udp->uh_sum = 0;
+
+  /* Copy the payload. */
+  p = (unsigned char *)(udp + 1);
+  memcpy(p, buf, mtu - (p - b));
+
+  /* Calculate the UDP checksum. */
+  ph.ph_src = ip->ip_src;
+  ph.ph_dst = ip->ip_dst;
+  ph.ph_z = 0;
+  ph.ph_p = IPPROTO_UDP;
+  ph.ph_len = udp->uh_ulen;
+  ck = IPCK_INIT;
+  ck = ipcksum(&ph, sizeof(ph), ck);
+  ck = ipcksum(udp, mtu - sizeof(*ip), ck);
+  udp->uh_sum = htons(ck);
+
+  /* Send the whole thing off.  If we're too big for the interface then we
+   * might need to trim immediately.
+   */
+  if (sendto(st->rawudp, b, mtu, 0,
+            (struct sockaddr *)&st->sin, sizeof(st->sin)) < 0) {
+    if (errno == EMSGSIZE) return (RC_LOWER);
+    else goto fail_0;
+  }
+
+  /* Done. */
+  return (RC_OK);
+
+fail_0:
+  return (RC_FAIL);
+}
+
+static int raw_selproc(void *stv, fd_set *fd_in, struct probestate *ps)
+{
+  struct raw_state *st = stv;
+  unsigned char b[65536];
+  struct ip *ip;
+  struct icmp *icmp;
+  struct udphdr *udp;
+  ssize_t n;
+
+  /* An ICMP packet: see what's inside. */
+  if (FD_ISSET(st->rawicmp, fd_in)) {
+    if ((n = read(st->rawicmp, b, sizeof(b))) < 0) goto fail_0;
+
+    ip = (struct ip *)b;
+    if (n < sizeof(*ip) || n < sizeof(4*ip->ip_hl) ||
+       ip->ip_v != 4 || ip->ip_p != IPPROTO_ICMP)
+      goto skip_icmp;
+    n -= sizeof(4*ip->ip_hl);
+
+    icmp = (struct icmp *)(b + 4*ip->ip_hl);
+    if (n < sizeof(*icmp) || icmp->icmp_type != ICMP_UNREACH)
+      goto skip_icmp;
+    n -= offsetof(struct icmp, icmp_ip);
+
+    ip = &icmp->icmp_ip;
+    if (n < sizeof(*ip) ||
+       ip->ip_p != IPPROTO_UDP || ip->ip_hl != sizeof(*ip)/4 ||
+       ip->ip_id != htons(st->q) ||
+       ip->ip_src.s_addr != st->me.sin_addr.s_addr ||
+       ip->ip_dst.s_addr != st->sin.sin_addr.s_addr)
+      goto skip_icmp;
+    n -= sizeof(*ip);
+
+    udp = (struct udphdr *)(ip + 1);
+    if (n < sizeof(udp) || udp->uh_sport != st->me.sin_port ||
+       udp->uh_dport != st->sin.sin_port)
+      goto skip_icmp;
+    n -= sizeof(*udp);
+
+    if (icmp->icmp_code == ICMP_UNREACH_PORT) return (RC_HIGHER);
+    else if (icmp->icmp_code != ICMP_UNREACH_NEEDFRAG) goto skip_icmp;
+    else if (icmp->icmp_nextmtu) return (htons(icmp->icmp_nextmtu));
+    else return (RC_LOWER);
+  }
+skip_icmp:;
+
+  /* If we got a reply to the current probe then we're good.  If we got an
+   * error, or the packet's sequence number is wrong, then ignore it.
+   */
+  if (FD_ISSET(st->sk, fd_in)) {
+    if ((n = read(st->sk, b, sizeof(b))) < 0) return (RC_OK);
+    else if (mypacketp(ps, b, n)) return (RC_HIGHER);
+    else return (RC_OK);
+  }
+
+  return (RC_OK);
+
+fail_0:
+  return (RC_FAIL);
+}
+
+static const struct probe_ops raw_ops = {
+  "raw", OPS_CHAIN, sizeof(struct raw_state),
+  raw_setup, raw_finish,
+  raw_selprep, raw_xmit, raw_selproc
+};
+
+#undef OPS_CHAIN
+#define OPS_CHAIN &raw_ops
+
+/*----- Doing the job on Linux --------------------------------------------*/
+
+#if defined(linux)
+
+#ifndef IP_MTU
+#  define IP_MTU 14                    /* Blech! */
+#endif
+
+struct linux_state {
+  int sk;
+};
+
+static int linux_setup(void *stv, int sk, const struct param *pp)
+{
+  struct linux_state *st = stv;
+  int i, mtu;
+  size_t sz;
+
+  /* Snaffle the UDP socket. */
+  st->sk = sk;
+
+  /* Turn on kernel path-MTU discovery and force DF on. */
+  i = IP_PMTUDISC_DO;
+  if (setsockopt(st->sk, IPPROTO_IP, IP_MTU_DISCOVER, &i, sizeof(i)))
+    return (-1);
+
+  /* Read the initial MTU guess back and report it. */
+  sz = sizeof(mtu);
+  if (getsockopt(st->sk, IPPROTO_IP, IP_MTU, &mtu, &sz))
+    return (-1);
+
+  /* Done. */
+  return (mtu);
+}
+
+static void linux_finish(void *stv) { ; }
+
+static void linux_selprep(void *stv, int *maxfd, fd_set *fd_in)
+  { struct linux_state *st = stv; ADDFD(st->sk); }
+
+static int linux_xmit(void *stv, int mtu)
+{
+  struct linux_state *st = stv;
+
+  /* Write the packet. */
+  if (write(st->sk, buf, mtu - 28) >= 0) return (RC_OK);
+  else if (errno == EMSGSIZE) return (RC_LOWER);
+  else return (RC_FAIL);
+}
+
+static int linux_selproc(void *stv, fd_set *fd_in, struct probestate *ps)
+{
+  struct linux_state *st = stv;
+  int mtu;
+  size_t sz;
+  ssize_t n;
+  unsigned char b[65536];
+
+  /* Read an answer.  If it looks like the right kind of error then report a
+   * success.  This is potentially wrong, since we can't tell whether an
+   * error was delayed from an earlier probe.  However, we never return
+   * RC_LOWER from this method, so the packet sizes ought to be monotonically
+   * decreasing and this won't cause trouble.  Otherwise update from the
+   * kernel's idea of the right MTU.
+   */
+  if (FD_ISSET(st->sk, fd_in)) {
+    n = read(st->sk, &buf, sizeof(buf));
+    if (n >= 0 ?
+       mypacketp(ps, b, n) :
+       errno == ECONNREFUSED || errno == EHOSTUNREACH)
+      return (RC_HIGHER);
+    sz = sizeof(mtu);
+    if (getsockopt(st->sk, IPPROTO_IP, IP_MTU, &mtu, &sz))
+      return (RC_FAIL);
+    return (mtu);
+  }
+  return (RC_OK);
+}
+
+static const struct probe_ops linux_ops = {
+  "linux", OPS_CHAIN, sizeof(struct linux_state),
+  linux_setup, linux_finish,
+  linux_selprep, linux_xmit, linux_selproc
+};
 
-#  error "path MTU discovery not implemented"
+#undef OPS_CHAIN
+#define OPS_CHAIN &linux_ops
 
 #endif
 
 /*----- Help options ------------------------------------------------------*/
 
+static const struct probe_ops *probe_ops = OPS_CHAIN;
+
 static void version(FILE *fp)
   { pquis(fp, "$, TrIPE version " VERSION "\n"); }
 
 static void usage(FILE *fp)
-  { pquis(fp, "Usage: $ [-t TIMEOUT] [-H HEADER] HOST [PORT]\n"); }
+{
+  pquis(fp, "Usage: $ [-H HEADER] [-m METHOD]\n\
+        [-r SECS] [-g FACTOR] [-t SECS] HOST [PORT]\n");
+}
 
 static void help(FILE *fp)
 {
+  const struct probe_ops *ops;
+
   version(fp);
   fputc('\n', fp);
   usage(fp);
@@ -146,16 +699,23 @@ Options in full:\n\
 -v, --version          Show version number.\n\
 -u, --usage            Show brief usage message.\n\
 \n\
--t, --timeout=TIMEOUT  Time to wait for reply, in seconds.\n\
+-g, --growth=FACTOR    Growth factor for retransmit interval.\n\
+-m, --method=METHOD    Use METHOD to probe for MTU.\n\
+-r, --retransmit=SECS  Retransmit if no reply after SEC.\n\
+-t, --timeout=SECS     Give up expecting a reply after SECS.\n\
 -H, --header=HEX       Packet header, in hexadecimal.\n\
+\n\
+Probe methods:\n\
 ", fp);
+  for (ops = probe_ops; ops; ops = ops->next)
+    printf("\t%s\n", ops->name);
 }
 
 /*----- Main code ---------------------------------------------------------*/
 
 int main(int argc, char *argv[])
 {
-  struct sockaddr_in sin;
+  struct param pp = { 0, 0.333, 3.0, 8.0, 0, OPS_CHAIN };
   hex_ctx hc;
   dstr d = DSTR_INIT;
   size_t sz;
@@ -164,30 +724,39 @@ int main(int argc, char *argv[])
   char *q;
   struct hostent *h;
   struct servent *s;
-  double to = 5.0;
   unsigned f = 0;
 
 #define f_bogus 1u
 
+  if ((rawicmp = socket(PF_INET, SOCK_RAW, IPPROTO_ICMP)) < 0 ||
+      (rawudp = socket(PF_INET, SOCK_RAW, IPPROTO_UDP)) < 0)
+    rawerr = errno;
+  if (setuid(getuid()))
+    abort();
+
   ego(argv[0]);
   fillbuffer(buf, sizeof(buf));
-  sin.sin_port = htons(7);
+  pp.sin.sin_port = htons(7);
 
   for (;;) {
     static const struct option opts[] = {
       { "help",                0,              0,      'h' },
-      { "version",     0,              0,      'v' },
+      { "version",     0,              0,      'V' },
       { "usage",       0,              0,      'u' },
       { "header",      OPTF_ARGREQ,    0,      'H' },
+      { "growth",      OPTF_ARGREQ,    0,      'g' },
+      { "method",      OPTF_ARGREQ,    0,      'm' },
+      { "retransmit",  OPTF_ARGREQ,    0,      'r' },
       { "timeout",     OPTF_ARGREQ,    0,      't' },
+      { "verbose",     0,              0,      'v' },
       { 0,             0,              0,      0 }
     };
 
-    i = mdwopt(argc, argv, "hvu" "H:", opts, 0, 0, 0);
+    i = mdwopt(argc, argv, "hVu" "H:g:m:r:t:v", opts, 0, 0, 0);
     if (i < 0) break;
     switch (i) {
       case 'h': help(stdout); exit(0);
-      case 'v': version(stdout); exit(0);
+      case 'V': version(stdout); exit(0);
       case 'u': usage(stdout); exit(0);
 
       case 'H':
@@ -195,16 +764,24 @@ int main(int argc, char *argv[])
        hex_init(&hc);
        hex_decode(&hc, optarg, strlen(optarg), &d);
        hex_decode(&hc, 0, 0, &d);
-       sz = d.len < sizeof(buf) ? d.len : sizeof(buf);
+       sz = d.len < 532 ? d.len : 532;
        memcpy(buf, d.buf, sz);
+       pp.seqoff = sz;
        break;
 
-      case 't':
-       errno = 0;
-       to = strtod(optarg, &q);
-       if (errno || *q) die(EXIT_FAILURE, "bad timeout");
+      case 'g': pp.regr = s2f(optarg, "retransmit growth factor"); break;
+      case 'r': pp.retx = s2f(optarg, "retransmit interval"); break;
+      case 't': pp.timeout = s2f(optarg, "timeout"); break;
+
+      case 'm':
+       for (pp.pops = OPS_CHAIN; pp.pops; pp.pops = pp.pops->next)
+         if (strcmp(pp.pops->name, optarg) == 0) goto found_alg;
+       die(EXIT_FAILURE, "unknown probe algorithm `%s'", optarg);
+      found_alg:
        break;
 
+      case 'v': pp.f |= F_VERBOSE; break;
+
       default:
        f |= f_bogus;
        break;
@@ -220,22 +797,22 @@ int main(int argc, char *argv[])
     die(EXIT_FAILURE, "unknown host `%s': %s", *argv, hstrerror(h_errno));
   if (h->h_addrtype != AF_INET)
     die(EXIT_FAILURE, "unsupported address family for host `%s'", *argv);
-  memcpy(&sin.sin_addr, h->h_addr, sizeof(struct in_addr));
+  memcpy(&pp.sin.sin_addr, h->h_addr, sizeof(struct in_addr));
   argv++; argc--;
 
   if (*argv) {
     errno = 0;
     u = strtoul(*argv, &q, 0);
     if (!errno && !*q)
-      sin.sin_port = htons(u);
+      pp.sin.sin_port = htons(u);
     else if ((s = getservbyname(*argv, "udp")) == 0)
       die(EXIT_FAILURE, "unknown UDP service `%s'", *argv);
     else
-      sin.sin_port = s->s_port;
+      pp.sin.sin_port = s->s_port;
   }
 
-  sin.sin_family = AF_INET;
-  i = pathmtu(&sin, to);
+  pp.sin.sin_family = AF_INET;
+  i = pathmtu(&pp);
   if (i < 0)
     die(EXIT_FAILURE, "failed to discover MTU: %s", strerror(errno));
   printf("%d\n", i);