usr.sbin/traceroute/traceroute.c

   1 /*      $OpenBSD: traceroute.c,v 1.61 2004/01/26 18:23:51 deraadt Exp $ */
   2 /*      $NetBSD: traceroute.c,v 1.10 1995/05/21 15:50:45 mycroft Exp $  */
   3
   4 /*-
   5  * Copyright (c) 1990, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * This code is derived from software contributed to Berkeley by
   9  * Van Jacobson.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. Neither the name of the University nor the names of its contributors
  20  *    may be used to endorse or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  *
  35  * $DragonFly: src/usr.sbin/traceroute/traceroute.c,v 1.5 2004/11/16 14:36:01 eirikn Exp $
  36  * @(#)traceroute.c     8.1 (Berkeley) 6/6/93
  37  */
  38
  39 /*
  40  * traceroute host  - trace the route ip packets follow going to "host".
  41  *
  42  * Attempt to trace the route an ip packet would follow to some
  43  * internet host.  We find out intermediate hops by launching probe
  44  * packets with a small ttl (time to live) then listening for an
  45  * icmp "time exceeded" reply from a gateway.  We start our probes
  46  * with a ttl of one and increase by one until we get an icmp "port
  47  * unreachable" (which means we got to "host") or hit a max (which
  48  * defaults to 64 hops & can be changed with the -m flag).  Three
  49  * probes (change with -q flag) are sent at each ttl setting and a
  50  * line is printed showing the ttl, address of the gateway and
  51  * round trip time of each probe.  If the probe answers come from
  52  * different gateways, the address of each responding system will
  53  * be printed.  If there is no response within a 5 sec. timeout
  54  * interval (changed with the -w flag), a "*" is printed for that
  55  * probe.
  56  *
  57  * Probe packets are UDP format.  We don't want the destination
  58  * host to process them so the destination port is set to an
  59  * unlikely value (if some clod on the destination is using that
  60  * value, it can be changed with the -p flag).
  61  *
  62  * A sample use might be:
  63  *
  64  *     [yak 71]% traceroute nis.nsf.net.
  65  *     traceroute to nis.nsf.net (35.1.1.48), 64 hops max, 56 byte packet
  66  *      1  helios.ee.lbl.gov (128.3.112.1)  19 ms  19 ms  0 ms
  67  *      2  lilac-dmc.Berkeley.EDU (128.32.216.1)  39 ms  39 ms  19 ms
  68  *      3  lilac-dmc.Berkeley.EDU (128.32.216.1)  39 ms  39 ms  19 ms
  69  *      4  ccngw-ner-cc.Berkeley.EDU (128.32.136.23)  39 ms  40 ms  39 ms
  70  *      5  ccn-nerif22.Berkeley.EDU (128.32.168.22)  39 ms  39 ms  39 ms
  71  *      6  128.32.197.4 (128.32.197.4)  40 ms  59 ms  59 ms
  72  *      7  131.119.2.5 (131.119.2.5)  59 ms  59 ms  59 ms
  73  *      8  129.140.70.13 (129.140.70.13)  99 ms  99 ms  80 ms
  74  *      9  129.140.71.6 (129.140.71.6)  139 ms  239 ms  319 ms
  75  *     10  129.140.81.7 (129.140.81.7)  220 ms  199 ms  199 ms
  76  *     11  nic.merit.edu (35.1.1.48)  239 ms  239 ms  239 ms
  77  *
  78  * Note that lines 2 & 3 are the same.  This is due to a buggy
  79  * kernel on the 2nd hop system -- lbl-csam.arpa -- that forwards
  80  * packets with a zero ttl.
  81  *
  82  * A more interesting example is:
  83  *
  84  *     [yak 72]% traceroute allspice.lcs.mit.edu.
  85  *     traceroute to allspice.lcs.mit.edu (18.26.0.115), 64 hops max
  86  *      1  helios.ee.lbl.gov (128.3.112.1)  0 ms  0 ms  0 ms
  87  *      2  lilac-dmc.Berkeley.EDU (128.32.216.1)  19 ms  19 ms  19 ms
  88  *      3  lilac-dmc.Berkeley.EDU (128.32.216.1)  39 ms  19 ms  19 ms
  89  *      4  ccngw-ner-cc.Berkeley.EDU (128.32.136.23)  19 ms  39 ms  39 ms
  90  *      5  ccn-nerif22.Berkeley.EDU (128.32.168.22)  20 ms  39 ms  39 ms
  91  *      6  128.32.197.4 (128.32.197.4)  59 ms  119 ms  39 ms
  92  *      7  131.119.2.5 (131.119.2.5)  59 ms  59 ms  39 ms
  93  *      8  129.140.70.13 (129.140.70.13)  80 ms  79 ms  99 ms
  94  *      9  129.140.71.6 (129.140.71.6)  139 ms  139 ms  159 ms
  95  *     10  129.140.81.7 (129.140.81.7)  199 ms  180 ms  300 ms
  96  *     11  129.140.72.17 (129.140.72.17)  300 ms  239 ms  239 ms
  97  *     12  * * *
  98  *     13  128.121.54.72 (128.121.54.72)  259 ms  499 ms  279 ms
  99  *     14  * * *
 100  *     15  * * *
 101  *     16  * * *
 102  *     17  * * *
 103  *     18  ALLSPICE.LCS.MIT.EDU (18.26.0.115)  339 ms  279 ms  279 ms
 104  *
 105  * (I start to see why I'm having so much trouble with mail to
 106  * MIT.)  Note that the gateways 12, 14, 15, 16 & 17 hops away
 107  * either don't send ICMP "time exceeded" messages or send them
 108  * with a ttl too small to reach us.  14 - 17 are running the
 109  * MIT C Gateway code that doesn't send "time exceeded"s.  God
 110  * only knows what's going on with 12.
 111  *
 112  * The silent gateway 12 in the above may be the result of a bug in
 113  * the 4.[23]BSD network code (and its derivatives):  4.x (x <= 3)
 114  * sends an unreachable message using whatever ttl remains in the
 115  * original datagram.  Since, for gateways, the remaining ttl is
 116  * zero, the icmp "time exceeded" is guaranteed to not make it back
 117  * to us.  The behavior of this bug is slightly more interesting
 118  * when it appears on the destination system:
 119  *
 120  *      1  helios.ee.lbl.gov (128.3.112.1)  0 ms  0 ms  0 ms
 121  *      2  lilac-dmc.Berkeley.EDU (128.32.216.1)  39 ms  19 ms  39 ms
 122  *      3  lilac-dmc.Berkeley.EDU (128.32.216.1)  19 ms  39 ms  19 ms
 123  *      4  ccngw-ner-cc.Berkeley.EDU (128.32.136.23)  39 ms  40 ms  19 ms
 124  *      5  ccn-nerif35.Berkeley.EDU (128.32.168.35)  39 ms  39 ms  39 ms
 125  *      6  csgw.Berkeley.EDU (128.32.133.254)  39 ms  59 ms  39 ms
 126  *      7  * * *
 127  *      8  * * *
 128  *      9  * * *
 129  *     10  * * *
 130  *     11  * * *
 131  *     12  * * *
 132  *     13  rip.Berkeley.EDU (128.32.131.22)  59 ms !  39 ms !  39 ms !
 133  *
 134  * Notice that there are 12 "gateways" (13 is the final
 135  * destination) and exactly the last half of them are "missing".
 136  * What's really happening is that rip (a Sun-3 running Sun OS3.5)
 137  * is using the ttl from our arriving datagram as the ttl in its
 138  * icmp reply.  So, the reply will time out on the return path
 139  * (with no notice sent to anyone since icmp's aren't sent for
 140  * icmp's) until we probe with a ttl that's at least twice the path
 141  * length.  I.e., rip is really only 7 hops away.  A reply that
 142  * returns with a ttl of 1 is a clue this problem exists.
 143  * Traceroute prints a "!" after the time if the ttl is <= 1.
 144  * Since vendors ship a lot of obsolete (DEC's Ultrix, Sun 3.x) or
 145  * non-standard (HPUX) software, expect to see this problem
 146  * frequently and/or take care picking the target host of your
 147  * probes.
 148  *
 149  * Other possible annotations after the time are !H, !N, !P (got a host,
 150  * network or protocol unreachable, respectively), !S or !F (source
 151  * route failed or fragmentation needed -- neither of these should
 152  * ever occur and the associated gateway is busted if you see one).  If
 153  * almost all the probes result in some kind of unreachable, traceroute
 154  * will give up and exit.
 155  *
 156  * Notes
 157  * -----
 158  * This program must be run by root or be setuid.  (I suggest that
 159  * you *don't* make it setuid -- casual use could result in a lot
 160  * of unnecessary traffic on our poor, congested nets.)
 161  *
 162  * This program requires a kernel mod that does not appear in any
 163  * system available from Berkeley:  A raw ip socket using proto
 164  * IPPROTO_RAW must interpret the data sent as an ip datagram (as
 165  * opposed to data to be wrapped in a ip datagram).  See the README
 166  * file that came with the source to this program for a description
 167  * of the mods I made to /sys/netinet/raw_ip.c.  Your mileage may
 168  * vary.  But, again, ANY 4.x (x < 4) BSD KERNEL WILL HAVE TO BE
 169  * MODIFIED TO RUN THIS PROGRAM.
 170  *
 171  * The udp port usage may appear bizarre (well, ok, it is bizarre).
 172  * The problem is that an icmp message only contains 8 bytes of
 173  * data from the original datagram.  8 bytes is the size of a udp
 174  * header so, if we want to associate replies with the original
 175  * datagram, the necessary information must be encoded into the
 176  * udp header (the ip id could be used but there's no way to
 177  * interlock with the kernel's assignment of ip id's and, anyway,
 178  * it would have taken a lot more kernel hacking to allow this
 179  * code to set the ip id).  So, to allow two or more users to
 180  * use traceroute simultaneously, we use this task's pid as the
 181  * source port (the high bit is set to move the port number out
 182  * of the "likely" range).  To keep track of which probe is being
 183  * replied to (so times and/or hop counts don't get confused by a
 184  * reply that was delayed in transit), we increment the destination
 185  * port number before each probe.
 186  *
 187  * Don't use this as a coding example.  I was trying to find a
 188  * routing problem and this code sort-of popped out after 48 hours
 189  * without sleep.  I was amazed it ever compiled, much less ran.
 190  *
 191  * I stole the idea for this program from Steve Deering.  Since
 192  * the first release, I've learned that had I attended the right
 193  * IETF working group meetings, I also could have stolen it from Guy
 194  * Almes or Matt Mathis.  I don't know (or care) who came up with
 195  * the idea first.  I envy the originators' perspicacity and I'm
 196  * glad they didn't keep the idea a secret.
 197  *
 198  * Tim Seaver, Ken Adelman and C. Philip Wood provided bug fixes and/or
 199  * enhancements to the original distribution.
 200  *
 201  * I've hacked up a round-trip-route version of this that works by
 202  * sending a loose-source-routed udp datagram through the destination
 203  * back to yourself.  Unfortunately, SO many gateways botch source
 204  * routing, the thing is almost worthless.  Maybe one day...
 205  *
 206  *  -- Van Jacobson (van@helios.ee.lbl.gov)
 207  *     Tue Dec 20 03:50:13 PST 1988
 208  */
 209
 210 #include <sys/param.h>
 211 #include <sys/time.h>
 212 #include <sys/socket.h>
 213 #include <sys/file.h>
 214 #include <sys/ioctl.h>
 215 #include <sys/sysctl.h>
 216
 217 #include <netinet/in_systm.h>
 218 #include <netinet/in.h>
 219 #include <netinet/ip.h>
 220 #include <netinet/ip_icmp.h>
 221 #include <netinet/ip_var.h>
 222 #include <netinet/udp.h>
 223
 224 #include <arpa/inet.h>
 225
 226 #include <ctype.h>
 227 #include <err.h>
 228 #include <errno.h>
 229 #include <netdb.h>
 230 #include <stdio.h>
 231 #include <stdlib.h>
 232 #include <string.h>
 233 #include <unistd.h>
 234
 235 #define MAX_LSRR        ((MAX_IPOPTLEN - 4) / 4)
 236
 237 /*
 238  * Format of the data in a (udp) probe packet.
 239  */
 240 struct packetdata {
 241         u_char seq;             /* sequence number of this packet */
 242         u_int8_t ttl;           /* ttl packet left with */
 243         u_int32_t sec;          /* time packet left */
 244         u_int32_t usec;
 245 };
 246
 247 struct in_addr gateway[MAX_LSRR + 1];
 248 int lsrrlen = 0;
 249 int32_t sec_perturb;
 250 int32_t usec_perturb;
 251
 252 u_char packet[512], *outpacket; /* last inbound (icmp) packet */
 253
 254 void dump_packet(void);
 255 int wait_for_reply(int, struct sockaddr_in *, struct timeval *);
 256 void send_probe(int, u_int8_t, int, struct sockaddr_in *);
 257 int packet_ok(u_char *, int, struct sockaddr_in *, int, int);
 258 const char *pr_type(u_int8_t);
 259 void print(u_char *, int, struct sockaddr_in *);
 260 char *inetname(struct in_addr);
 261 u_short in_cksum(u_short *, int);
 262 void usage(void);
 263
 264 int s;                          /* receive (icmp) socket file descriptor */
 265 int sndsock;                    /* send (udp) socket file descriptor */
 266
 267 int datalen;                    /* How much data */
 268 int headerlen;                  /* How long packet's header is */
 269
 270 char *source = 0;
 271 char *hostname;
 272
 273 int nprobes = 3;
 274 u_int8_t max_ttl = IPDEFTTL;
 275 u_int8_t first_ttl = 1;
 276 u_short ident;
 277 u_short port = 32768+666;       /* start udp dest port # for probe packets */
 278 u_char  proto = IPPROTO_UDP;
 279 u_int8_t  icmp_type = ICMP_ECHO; /* default ICMP code/type */
 280 u_char  icmp_code = 0;
 281 int options;                    /* socket options */
 282 int verbose;
 283 int waittime = 5;               /* time to wait for response (in seconds) */
 284 int nflag;                      /* print addresses numerically */
 285 int dump;
 286
 287 int
 288 main(int argc, char *argv[])
 289 {
 290         int mib[4] = { CTL_NET, PF_INET, IPPROTO_IP, IPCTL_DEFTTL };
 291         int ttl_flag = 0, incflag = 1, protoset = 0, sump = 0;
 292         int ch, i, lsrr = 0, on = 1, probe, seq = 0, tos = 0;
 293         size_t size = sizeof(max_ttl);
 294         struct sockaddr_in from, to;
 295         struct hostent *hp;
 296         u_int32_t tmprnd;
 297         struct ip *ip;
 298         u_int8_t ttl;
 299         char *ep;
 300         long l;
 301
 302         if ((s = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP)) < 0)
 303                 err(5, "icmp socket");
 304         if ((sndsock = socket(AF_INET, SOCK_RAW, IPPROTO_RAW)) < 0)
 305                 err(5, "raw socket");
 306
 307         /* revoke privs */
 308         seteuid(getuid());
 309         setuid(getuid());
 310
 311         (void) sysctl(mib, sizeof(mib)/sizeof(mib[0]), &max_ttl, &size,
 312             NULL, 0);
 313
 314         while ((ch = getopt(argc, argv, "SDIdg:f:m:np:q:rs:t:w:vlP:c")) != -1)
 315                 switch (ch) {
 316                 case 'S':
 317                         sump = 1;
 318                         break;
 319                 case 'f':
 320                         errno = 0;
 321                         ep = NULL;
 322                         l = strtol(optarg, &ep, 10);
 323                         if (errno || !*optarg || *ep || l < 1 || l > max_ttl)
 324                                 errx(1, "min ttl must be 1 to %u.", max_ttl);
 325                         first_ttl = (u_int8_t)l;
 326                         break;
 327                 case 'c':
 328                         incflag = 0;
 329                         break;
 330                 case 'd':
 331                         options |= SO_DEBUG;
 332                         break;
 333                 case 'D':
 334                         dump = 1;
 335                         break;
 336                 case 'g':
 337                         if (lsrr >= MAX_LSRR)
 338                                 errx(1, "too many gateways; max %d", MAX_LSRR);
 339                         if (inet_aton(optarg, &gateway[lsrr]) == 0) {
 340                                 hp = gethostbyname(optarg);
 341                                 if (hp == 0)
 342                                         errx(1, "unknown host %s", optarg);
 343                                 memcpy(&gateway[lsrr], hp->h_addr, hp->h_length);
 344                         }
 345                         if (++lsrr == 1)
 346                                 lsrrlen = 4;
 347                         lsrrlen += 4;
 348                         break;
 349                 case 'I':
 350                         if (protoset)
 351                                 errx(1, "protocol already set with -P");
 352                         protoset = 1;
 353                         proto = IPPROTO_ICMP;
 354                         break;
 355                 case 'l':
 356                         ttl_flag++;
 357                         break;
 358                 case 'm':
 359                         errno = 0;
 360                         ep = NULL;
 361                         l = strtol(optarg, &ep, 10);
 362                         if (errno || !*optarg || *ep || l < first_ttl ||
 363                             l > MAXTTL)
 364                                 errx(1, "max ttl must be %u to %u.", first_ttl,
 365                                     MAXTTL);
 366                         max_ttl = (u_int8_t)l;
 367                         break;
 368                 case 'n':
 369                         nflag++;
 370                         break;
 371                 case 'p':
 372                         errno = 0;
 373                         ep = NULL;
 374                         l = strtol(optarg, &ep, 10);
 375                         if (errno || !*optarg || *ep || l <= 0 || l >= 65536)
 376                                 errx(1, "port must be >0, <65536.");
 377                         port = (int)l;
 378                         break;
 379                 case 'P':
 380                         if (protoset)
 381                                 errx(1, "protocol already set with -I");
 382                         protoset = 1;
 383                         errno = 0;
 384                         ep = NULL;
 385                         l = strtol(optarg, &ep, 10);
 386                         if (errno || !*optarg || *ep || l < 1 ||
 387                             l >= IPPROTO_MAX) {
 388                                 struct protoent *pent;
 389
 390                                 pent = getprotobyname(optarg);
 391                                 if (pent)
 392                                         proto = pent->p_proto;
 393                                 else
 394                                         errx(1, "proto must be >=1, or a name.");
 395                         } else
 396                                 proto = (int)l;
 397                         break;
 398                 case 'q':
 399                         errno = 0;
 400                         ep = NULL;
 401                         l = strtol(optarg, &ep, 10);
 402                         if (errno || !*optarg || *ep || l < 1 || l > INT_MAX)
 403                                 errx(1, "nprobes must be >0.");
 404                         nprobes = (int)l;
 405                         break;
 406                 case 'r':
 407                         options |= SO_DONTROUTE;
 408                         break;
 409                 case 's':
 410                         /*
 411                          * set the ip source address of the outbound
 412                          * probe (e.g., on a multi-homed host).
 413                          */
 414                         source = optarg;
 415                         break;
 416                 case 't':
 417                         errno = 0;
 418                         ep = NULL;
 419                         l = strtol(optarg, &ep, 10);
 420                         if (errno || !*optarg || *ep || l < 0 || l > 255)
 421                                 errx(1, "tos must be 0 to 255.");
 422                         tos = (int)l;
 423                         break;
 424                 case 'v':
 425                         verbose++;
 426                         break;
 427                 case 'w':
 428                         errno = 0;
 429                         ep = NULL;
 430                         l = strtol(optarg, &ep, 10);
 431                         if (errno || !*optarg || *ep || l <= 1 || l > INT_MAX)
 432                                 errx(1, "wait must be >1 sec.");
 433                         waittime = (int)l;
 434                         break;
 435                 default:
 436                         usage();
 437                 }
 438         argc -= optind;
 439         argv += optind;
 440
 441         if (argc < 1)
 442                 usage();
 443
 444         setlinebuf (stdout);
 445
 446         (void) memset(&to, 0, sizeof(struct sockaddr));
 447         to.sin_family = AF_INET;
 448         if (inet_aton(*argv, &to.sin_addr) != 0)
 449                 hostname = *argv;
 450         else {
 451                 hp = gethostbyname(*argv);
 452                 if (hp == 0)
 453                         errx(1, "unknown host %s", *argv);
 454                 to.sin_family = hp->h_addrtype;
 455                 memcpy(&to.sin_addr, hp->h_addr, hp->h_length);
 456                 if ((hostname = strdup(hp->h_name)) == NULL)
 457                         err(1, "malloc");
 458                 if (hp->h_addr_list[1] != NULL)
 459                         warnx("Warning: %s has multiple addresses; using %s",
 460                             hostname, inet_ntoa(to.sin_addr));
 461         }
 462         if (*++argv) {
 463                 errno = 0;
 464                 ep = NULL;
 465                 l = strtol(*argv, &ep, 10);
 466                 if (errno || !*argv || *ep || l < 0 || l > INT_MAX)
 467                         errx(1, "datalen out of range");
 468                 datalen = (int)l;
 469         }
 470
 471         switch (proto) {
 472         case IPPROTO_UDP:
 473                 headerlen = (sizeof(struct ip) + lsrrlen +
 474                     sizeof(struct udphdr) + sizeof(struct packetdata));
 475                 break;
 476         case IPPROTO_ICMP:
 477                 headerlen = (sizeof(struct ip) + lsrrlen +
 478                     sizeof(struct icmp) + sizeof(struct packetdata));
 479                 break;
 480         default:
 481                 headerlen = (sizeof(struct ip) + lsrrlen +
 482                     sizeof(struct packetdata));
 483         }
 484
 485         if (datalen < 0 || datalen > IP_MAXPACKET - headerlen)
 486                 errx(1, "packet size must be 0 to %d.",
 487                     IP_MAXPACKET - headerlen);
 488
 489         datalen += headerlen;
 490
 491         outpacket = (u_char *)malloc(datalen);
 492         if (outpacket == NULL)
 493                 err(1, "malloc");
 494         (void) memset(outpacket, 0, datalen);
 495
 496         ip = (struct ip *)outpacket;
 497         if (lsrr != 0) {
 498                 u_char *p = (u_char *)(ip + 1);
 499
 500                 *p++ = IPOPT_NOP;
 501                 *p++ = IPOPT_LSRR;
 502                 *p++ = lsrrlen - 1;
 503                 *p++ = IPOPT_MINOFF;
 504                 gateway[lsrr] = to.sin_addr;
 505                 for (i = 1; i <= lsrr; i++) {
 506                         memcpy(p, &gateway[i], sizeof(struct in_addr));
 507                         p += sizeof(struct in_addr);
 508                 }
 509                 ip->ip_dst = gateway[0];
 510         } else
 511                 ip->ip_dst = to.sin_addr;
 512         ip->ip_off = htons(0);
 513         ip->ip_hl = (sizeof(struct ip) + lsrrlen) >> 2;
 514         ip->ip_p = proto;
 515         ip->ip_v = IPVERSION;
 516         ip->ip_tos = tos;
 517
 518         ident = (getpid() & 0xffff) | 0x8000;
 519         tmprnd = arc4random();
 520         sec_perturb = (tmprnd & 0x80000000) ? -(tmprnd & 0x7ff) :
 521             (tmprnd & 0x7ff);
 522         usec_perturb = arc4random();
 523
 524         if (options & SO_DEBUG)
 525                 (void) setsockopt(s, SOL_SOCKET, SO_DEBUG,
 526                     (char *)&on, sizeof(on));
 527 #ifdef SO_SNDBUF
 528         if (setsockopt(sndsock, SOL_SOCKET, SO_SNDBUF, (char *)&datalen,
 529             sizeof(datalen)) < 0)
 530                 err(6, "SO_SNDBUF");
 531 #endif /* SO_SNDBUF */
 532 #ifdef IP_HDRINCL
 533         if (setsockopt(sndsock, IPPROTO_IP, IP_HDRINCL, (char *)&on,
 534             sizeof(on)) < 0)
 535                 err(6, "IP_HDRINCL");
 536 #endif /* IP_HDRINCL */
 537         if (options & SO_DEBUG)
 538                 (void) setsockopt(sndsock, SOL_SOCKET, SO_DEBUG,
 539                     (char *)&on, sizeof(on));
 540         if (options & SO_DONTROUTE)
 541                 (void) setsockopt(sndsock, SOL_SOCKET, SO_DONTROUTE,
 542                     (char *)&on, sizeof(on));
 543
 544         if (source) {
 545                 (void) memset(&from, 0, sizeof(struct sockaddr));
 546                 from.sin_family = AF_INET;
 547                 if (inet_aton(source, &from.sin_addr) == 0)
 548                         errx(1, "unknown host %s", source);
 549                 ip->ip_src = from.sin_addr;
 550                 if (getuid() != 0 &&
 551                     (ntohl(from.sin_addr.s_addr) & 0xff000000U) == 0x7f000000U &&
 552                     (ntohl(to.sin_addr.s_addr) & 0xff000000U) != 0x7f000000U)
 553                         errx(1, "source is on 127/8, destination is not");
 554
 555                 if (getuid() &&
 556                     bind(sndsock, (struct sockaddr *)&from, sizeof(from)) < 0)
 557                         err(1, "bind");
 558         }
 559
 560         fprintf(stderr, "traceroute to %s (%s)", hostname,
 561                 inet_ntoa(to.sin_addr));
 562         if (source)
 563                 fprintf(stderr, " from %s", source);
 564         fprintf(stderr, ", %u hops max, %d byte packets\n", max_ttl, datalen);
 565         (void) fflush(stderr);
 566
 567         if (first_ttl > 1)
 568                 printf("Skipping %u intermediate hops\n", first_ttl - 1);
 569
 570         for (ttl = first_ttl; ttl <= max_ttl; ++ttl) {
 571                 int got_there = 0, unreachable = 0, timeout = 0, loss;
 572                 in_addr_t lastaddr = 0;
 573                 quad_t dt;
 574
 575                 printf("%2u ", ttl);
 576                 for (probe = 0, loss = 0; probe < nprobes; ++probe) {
 577                         int cc;
 578                         struct timeval t1, t2;
 579                         int code;
 580
 581                         (void) gettimeofday(&t1, NULL);
 582                         send_probe(++seq, ttl, incflag, &to);
 583                         while ((cc = wait_for_reply(s, &from, &t1))) {
 584                                 (void) gettimeofday(&t2, NULL);
 585                                 if (t2.tv_sec - t1.tv_sec > waittime) {
 586                                         cc = 0;
 587                                         break;
 588                                 }
 589                                 i = packet_ok(packet, cc, &from, seq, incflag);
 590                                 /* Skip short packet */
 591                                 if (i == 0)
 592                                         continue;
 593                                 if (from.sin_addr.s_addr != lastaddr) {
 594                                         print(packet, cc, &from);
 595                                         lastaddr = from.sin_addr.s_addr;
 596                                 }
 597                                 dt = (quad_t)(t2.tv_sec - t1.tv_sec) * 1000000 +
 598                                     (quad_t)(t2.tv_usec - t1.tv_usec);
 599                                 printf("  %u", (u_int)(dt / 1000));
 600                                 if (dt % 1000)
 601                                         printf(".%u", (u_int)(dt % 1000));
 602                                 printf(" ms");
 603                                 ip = (struct ip *)packet;
 604                                 if (ttl_flag)
 605                                         printf(" (%u)", ip->ip_ttl);
 606                                 if (i == -2) {
 607 #ifndef ARCHAIC
 608                                         ip = (struct ip *)packet;
 609                                         if (ip->ip_ttl <= 1)
 610                                                 printf(" !");
 611 #endif
 612                                         ++got_there;
 613                                         break;
 614                                 }
 615                                 /* time exceeded in transit */
 616                                 if (i == -1)
 617                                         break;
 618                                 code = i - 1;
 619                                 switch (code) {
 620                                 case ICMP_UNREACH_PORT:
 621 #ifndef ARCHAIC
 622                                         ip = (struct ip *)packet;
 623                                         if (ip->ip_ttl <= 1)
 624                                                 printf(" !");
 625 #endif /* ARCHAIC */
 626                                         ++got_there;
 627                                         break;
 628                                 case ICMP_UNREACH_NET:
 629                                         ++unreachable;
 630                                         printf(" !N");
 631                                         break;
 632                                 case ICMP_UNREACH_HOST:
 633                                         ++unreachable;
 634                                         printf(" !H");
 635                                         break;
 636                                 case ICMP_UNREACH_PROTOCOL:
 637                                         ++got_there;
 638                                         printf(" !P");
 639                                         break;
 640                                 case ICMP_UNREACH_NEEDFRAG:
 641                                         ++unreachable;
 642                                         printf(" !F");
 643                                         break;
 644                                 case ICMP_UNREACH_SRCFAIL:
 645                                         ++unreachable;
 646                                         printf(" !S");
 647                                         break;
 648                                 case ICMP_UNREACH_FILTER_PROHIB:
 649                                         ++unreachable;
 650                                         printf(" !X");
 651                                         break;
 652                                 case ICMP_UNREACH_NET_PROHIB: /*misuse*/
 653                                         ++unreachable;
 654                                         printf(" !A");
 655                                         break;
 656                                 case ICMP_UNREACH_HOST_PROHIB:
 657                                         ++unreachable;
 658                                         printf(" !C");
 659                                         break;
 660                                 case ICMP_UNREACH_NET_UNKNOWN:
 661                                 case ICMP_UNREACH_HOST_UNKNOWN:
 662                                         ++unreachable;
 663                                         printf(" !U");
 664                                         break;
 665                                 case ICMP_UNREACH_ISOLATED:
 666                                         ++unreachable;
 667                                         printf(" !I");
 668                                         break;
 669                                 case ICMP_UNREACH_TOSNET:
 670                                 case ICMP_UNREACH_TOSHOST:
 671                                         ++unreachable;
 672                                         printf(" !T");
 673                                         break;
 674                                 default:
 675                                         ++unreachable;
 676                                         printf(" !<%d>", i - 1);
 677                                         break;
 678                                 }
 679                                 break;
 680                         }
 681                         if (cc == 0) {
 682                                 printf(" *");
 683                                 timeout++;
 684                                 loss++;
 685                         }
 686                         (void) fflush(stdout);
 687                 }
 688                 if (sump)
 689                         printf(" (%d%% loss)", (loss * 100) / nprobes);
 690                 putchar('\n');
 691                 if (got_there || (unreachable && (unreachable + timeout) >= nprobes))
 692                         break;
 693         }
 694         exit(0);
 695 }
 696
 697 int
 698 wait_for_reply(int sock, struct sockaddr_in *from, struct timeval *sent)
 699 {
 700         socklen_t fromlen = sizeof (*from);
 701         struct timeval now, wait;
 702         int cc = 0, fdsn;
 703         fd_set *fdsp;
 704
 705         fdsn = howmany(sock+1, NFDBITS) * sizeof(fd_mask);
 706         if ((fdsp = (fd_set *)malloc(fdsn)) == NULL)
 707                 err(1, "malloc");
 708         memset(fdsp, 0, fdsn);
 709         FD_SET(sock, fdsp);
 710         gettimeofday(&now, NULL);
 711         wait.tv_sec = (sent->tv_sec + waittime) - now.tv_sec;
 712         wait.tv_usec =  sent->tv_usec - now.tv_usec;
 713         if (wait.tv_usec < 0) {
 714                 wait.tv_usec += 1000000;
 715                 wait.tv_sec--;
 716         }
 717         if (wait.tv_sec < 0)
 718                 wait.tv_sec = wait.tv_usec = 0;
 719
 720         if (select(sock+1, fdsp, (fd_set *)0, (fd_set *)0, &wait) > 0)
 721                 cc = recvfrom(s, (char *)packet, sizeof(packet), 0,
 722                     (struct sockaddr *)from, &fromlen);
 723
 724         free(fdsp);
 725         return (cc);
 726 }
 727
 728 void
 729 dump_packet(void)
 730 {
 731         u_char *p;
 732         int i;
 733
 734         fprintf(stderr, "packet data:");
 735         for (p = outpacket, i = 0; i < datalen; i++) {
 736                 if ((i % 24) == 0)
 737                         fprintf(stderr, "\n ");
 738                 fprintf(stderr, " %02x", *p++);
 739         }
 740         fprintf(stderr, "\n");
 741 }
 742
 743 void
 744 send_probe(int seq, u_int8_t ttl, int iflag, struct sockaddr_in *to)
 745 {
 746         struct ip *ip = (struct ip *)outpacket;
 747         u_char *p = (u_char *)(ip + 1);
 748         struct udphdr *up = (struct udphdr *)(p + lsrrlen);
 749         struct icmp *icmpp = (struct icmp *)(p + lsrrlen);
 750         struct packetdata *op;
 751         struct timeval tv;
 752         int i;
 753
 754         ip->ip_len = datalen;
 755         ip->ip_ttl = ttl;
 756         ip->ip_id = htons(ident+seq);
 757
 758         switch (proto) {
 759         case IPPROTO_ICMP:
 760                 icmpp->icmp_type = icmp_type;
 761                 icmpp->icmp_code = icmp_code;
 762                 icmpp->icmp_seq = htons(seq);
 763                 icmpp->icmp_id = htons(ident);
 764                 op = (struct packetdata *)(icmpp + 1);
 765                 break;
 766         case IPPROTO_UDP:
 767                 up->uh_sport = htons(ident);
 768                 if (iflag)
 769                         up->uh_dport = htons(port+seq);
 770                 else
 771                         up->uh_dport = htons(port);
 772                 up->uh_ulen = htons((u_short)(datalen - sizeof(struct ip) -
 773                     lsrrlen));
 774                 up->uh_sum = 0;
 775                 op = (struct packetdata *)(up + 1);
 776                 break;
 777         default:
 778                 op = (struct packetdata *)(ip + 1);
 779                 break;
 780         }
 781         op->seq = seq;
 782         op->ttl = ttl;
 783
 784         /*
 785          * We don't want hostiles snooping the net to get any useful
 786          * information about us. Send the timestamp in network byte order,
 787          * and perturb the timestamp enough that they won't know our
 788          * real clock ticker. We don't want to perturb the time by too
 789          * much: being off by a suspiciously large amount might indicate
 790          * OpenBSD.
 791          *
 792          * The timestamps in the packet are currently unused. If future
 793          * work wants to use them they will have to subtract out the
 794          * perturbation first.
 795          */
 796         (void) gettimeofday(&tv, NULL);
 797         op->sec = htonl(tv.tv_sec + sec_perturb);
 798         op->usec = htonl((tv.tv_usec + usec_perturb) % 1000000);
 799
 800         if (proto == IPPROTO_ICMP && icmp_type == ICMP_ECHO) {
 801                 icmpp->icmp_cksum = 0;
 802                 icmpp->icmp_cksum = in_cksum((u_short *)icmpp,
 803                     datalen - sizeof(struct ip) - lsrrlen);
 804                 if (icmpp->icmp_cksum == 0)
 805                         icmpp->icmp_cksum = 0xffff;
 806         }
 807
 808         if (dump)
 809                 dump_packet();
 810
 811         i = sendto(sndsock, outpacket, datalen, 0, (struct sockaddr *)to,
 812             sizeof(struct sockaddr_in));
 813         if (i < 0 || i != datalen)  {
 814                 if (i < 0)
 815                         perror("sendto");
 816                 printf("traceroute: wrote %s %d chars, ret=%d\n", hostname,
 817                     datalen, i);
 818                 (void) fflush(stdout);
 819         }
 820 }
 821
 822 static const char *ttab[] = {
 823         "Echo Reply",
 824         "ICMP 1",
 825         "ICMP 2",
 826         "Dest Unreachable",
 827         "Source Quench",
 828         "Redirect",
 829         "ICMP 6",
 830         "ICMP 7",
 831         "Echo",
 832         "Router Advert",
 833         "Router Solicit",
 834         "Time Exceeded",
 835         "Param Problem",
 836         "Timestamp",
 837         "Timestamp Reply",
 838         "Info Request",
 839         "Info Reply",
 840         "Mask Request",
 841         "Mask Reply"
 842 };
 843
 844 /*
 845  * Convert an ICMP "type" field to a printable string.
 846  */
 847 const char *
 848 pr_type(u_int8_t t)
 849 {
 850         if (t > 18)
 851                 return ("OUT-OF-RANGE");
 852         return (ttab[t]);
 853 }
 854
 855 int
 856 packet_ok(u_char *buf, int cc, struct sockaddr_in *from, int seq, int iflag)
 857 {
 858         struct icmp *icp;
 859         u_char code;
 860         u_int8_t type;
 861         int hlen;
 862 #ifndef ARCHAIC
 863         struct ip *ip;
 864
 865         ip = (struct ip *) buf;
 866         hlen = ip->ip_hl << 2;
 867         if (cc < hlen + ICMP_MINLEN) {
 868                 if (verbose)
 869                         printf("packet too short (%d bytes) from %s\n", cc,
 870                             inet_ntoa(from->sin_addr));
 871                 return (0);
 872         }
 873         cc -= hlen;
 874         icp = (struct icmp *)(buf + hlen);
 875 #else
 876         icp = (struct icmp *)buf;
 877 #endif /* ARCHAIC */
 878         type = icp->icmp_type;
 879         code = icp->icmp_code;
 880         if ((type == ICMP_TIMXCEED && code == ICMP_TIMXCEED_INTRANS) ||
 881             type == ICMP_UNREACH || type == ICMP_ECHOREPLY) {
 882                 struct ip *hip;
 883                 struct udphdr *up;
 884                 struct icmp *icmpp;
 885
 886                 hip = &icp->icmp_ip;
 887                 hlen = hip->ip_hl << 2;
 888
 889                 switch (proto) {
 890                 case IPPROTO_ICMP:
 891                         if (icmp_type == ICMP_ECHO &&
 892                             type == ICMP_ECHOREPLY &&
 893                             icp->icmp_id == htons(ident) &&
 894                             icp->icmp_seq == htons(seq))
 895                                 return (-2); /* we got there */
 896
 897                         icmpp = (struct icmp *)((u_char *)hip + hlen);
 898                         if (hlen + 8 <= cc && hip->ip_p == IPPROTO_ICMP &&
 899                             icmpp->icmp_id == htons(ident) &&
 900                             icmpp->icmp_seq == htons(seq))
 901                                 return (type == ICMP_TIMXCEED? -1 : code + 1);
 902                         break;
 903
 904                 case IPPROTO_UDP:
 905                         up = (struct udphdr *)((u_char *)hip + hlen);
 906                         if (hlen + 12 <= cc && hip->ip_p == proto &&
 907                             up->uh_sport == htons(ident) &&
 908                             ((iflag && up->uh_dport == htons(port + seq)) ||
 909                             (!iflag && up->uh_dport == htons(port))))
 910                                 return (type == ICMP_TIMXCEED? -1 : code + 1);
 911                         break;
 912                 default:
 913                         /* this is some odd, user specified proto,
 914                          * how do we check it?
 915                          */
 916                         if (hip->ip_p == proto)
 917                                 return (type == ICMP_TIMXCEED? -1 : code + 1);
 918                 }
 919         }
 920 #ifndef ARCHAIC
 921         if (verbose) {
 922                 int i;
 923                 in_addr_t *lp = (in_addr_t *)&icp->icmp_ip;
 924
 925                 printf("\n%d bytes from %s", cc, inet_ntoa(from->sin_addr));
 926                 printf(" to %s", inet_ntoa(ip->ip_dst));
 927                 printf(": icmp type %u (%s) code %d\n", type, pr_type(type),
 928                     icp->icmp_code);
 929                 for (i = 4; i < cc ; i += sizeof(in_addr_t))
 930                         printf("%2d: x%8.8lx\n", i, (unsigned long)*lp++);
 931         }
 932 #endif /* ARCHAIC */
 933         return (0);
 934 }
 935
 936 void
 937 print(u_char *buf, int cc, struct sockaddr_in *from)
 938 {
 939         struct ip *ip;
 940         int hlen;
 941
 942         ip = (struct ip *) buf;
 943         hlen = ip->ip_hl << 2;
 944         cc -= hlen;
 945
 946         if (nflag)
 947                 printf(" %s", inet_ntoa(from->sin_addr));
 948         else
 949                 printf(" %s (%s)", inetname(from->sin_addr),
 950                     inet_ntoa(from->sin_addr));
 951
 952         if (verbose)
 953                 printf(" %d bytes to %s", cc, inet_ntoa (ip->ip_dst));
 954 }
 955
 956
 957 /*
 958  * Checksum routine for Internet Protocol family headers (C Version)
 959  */
 960 u_short
 961 in_cksum(u_short *addr, int len)
 962 {
 963         u_short *w = addr, answer;
 964         int nleft = len, sum = 0;
 965
 966         /*
 967          *  Our algorithm is simple, using a 32 bit accumulator (sum),
 968          *  we add sequential 16 bit words to it, and at the end, fold
 969          *  back all the carry bits from the top 16 bits into the lower
 970          *  16 bits.
 971          */
 972         while (nleft > 1)  {
 973                 sum += *w++;
 974                 nleft -= 2;
 975         }
 976
 977         /* mop up an odd byte, if necessary */
 978         if (nleft == 1)
 979                 sum += *(u_char *)w;
 980
 981         /*
 982          * add back carry outs from top 16 bits to low 16 bits
 983          */
 984         sum = (sum >> 16) + (sum & 0xffff);     /* add hi 16 to low 16 */
 985         sum += (sum >> 16);                     /* add carry */
 986         answer = ~sum;                          /* truncate to 16 bits */
 987         return (answer);
 988 }
 989
 990 /*
 991  * Construct an Internet address representation.
 992  * If the nflag has been supplied, give
 993  * numeric value, otherwise try for symbolic name.
 994  */
 995 char *
 996 inetname(struct in_addr in)
 997 {
 998         static char domain[MAXHOSTNAMELEN], line[MAXHOSTNAMELEN];
 999         static int first = 1;
1000         struct hostent *hp;
1001         char *cp;
1002
1003         if (first && !nflag) {
1004                 first = 0;
1005                 if (gethostname(domain, sizeof domain) == 0 &&
1006                     (cp = strchr(domain, '.')) != NULL) {
1007                         strlcpy(domain, cp + 1, sizeof(domain));
1008                 }
1009         }
1010         if (!nflag && in.s_addr != INADDR_ANY) {
1011                 hp = gethostbyaddr((char *)&in, sizeof(in), AF_INET);
1012                 if (hp != NULL) {
1013                         if ((cp = strchr(hp->h_name, '.')) != NULL &&
1014                             strcmp(cp + 1, domain) == 0)
1015                                 *cp = '\0';
1016                         strlcpy(line, hp->h_name, sizeof(line));
1017                         return (line);
1018                 }
1019         }
1020         return (inet_ntoa(in));
1021 }
1022
1023 void
1024 usage(void)
1025 {
1026         fprintf(stderr,
1027             "usage: %s [-cdDIlnrSv] [-f first_ttl] [-g gateway_addr] [-m max_ttl]\n"
1028             "\t[-p port] [-P proto] [-q nqueries] [-s src_addr] [-t tos]\n"
1029             "\t[-w waittime] host [packetsize]\n", getprogname());
1030         exit(1);
1031 }