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