2 * Copyright (C) 1999 WIDE Project.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the project nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * Copyright (c) 1998 by the University of Southern California.
31 * All rights reserved.
33 * Permission to use, copy, modify, and distribute this software and
34 * its documentation in source and binary forms for lawful
35 * non-commercial purposes and without fee is hereby granted, provided
36 * that the above copyright notice appear in all copies and that both
37 * the copyright notice and this permission notice appear in supporting
38 * documentation, and that any documentation, advertising materials,
39 * and other materials related to such distribution and use acknowledge
40 * that the software was developed by the University of Southern
41 * California and/or Information Sciences Institute.
42 * The name of the University of Southern California may not
43 * be used to endorse or promote products derived from this software
44 * without specific prior written permission.
46 * THE UNIVERSITY OF SOUTHERN CALIFORNIA DOES NOT MAKE ANY REPRESENTATIONS
47 * ABOUT THE SUITABILITY OF THIS SOFTWARE FOR ANY PURPOSE. THIS SOFTWARE IS
48 * PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES,
49 * INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
50 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, TITLE, AND
53 * IN NO EVENT SHALL USC, OR ANY OTHER CONTRIBUTOR BE LIABLE FOR ANY
54 * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES, WHETHER IN CONTRACT,
55 * TORT, OR OTHER FORM OF ACTION, ARISING OUT OF OR IN CONNECTION WITH,
56 * THE USE OR PERFORMANCE OF THIS SOFTWARE.
58 * Other copyrights might apply to parts of this software and are so
59 * noted when applicable.
62 * Questions concerning this software should be directed to
63 * Pavlin Ivanov Radoslavov (pavlin@catarina.usc.edu)
65 * $Id: trace.c,v 1.5 1999/09/16 08:46:00 jinmei Exp $
68 * Part of this program has been derived from mrouted.
69 * The mrouted program is covered by the license in the accompanying file
70 * named "LICENSE.mrouted".
72 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
73 * Leland Stanford Junior University.
84 * Traceroute function which returns traceroute replies to the requesting
85 * router. Also forwards the request to downstream routers.
88 accept_mtrace(src, dst, group, ifindex, data, no, datalen)
89 struct sockaddr_in6 *src;
91 struct in6_addr *group;
94 u_int no; /* promoted u_char */
99 struct tr6_query *qry;
100 struct tr6_resp *resp;
104 int errcode = TR_NO_ERR;
107 struct sioc_mif_req6 mreq;
108 struct in6_addr parent_address;
109 struct sockaddr_in6 src_sa6 = {sizeof(src_sa6), AF_INET6};
110 struct sockaddr_in6 dst_sa6 = {sizeof(dst_sa6), AF_INET6};
111 struct sockaddr_in6 resp_sa6 = {sizeof(resp_sa6), AF_INET6};
112 struct sockaddr_in6 grp_sa6 = {sizeof(grp_sa6), AF_INET6};
113 struct sockaddr_in6 *sa_global;
115 rpentry_t *rpentry_ptr;
118 /* Remember qid across invocations */
119 static u_int32 oqid = 0;
121 /* timestamp the request/response */
122 gettimeofday(&tp, 0);
125 * Check if it is a query or a response
127 if (datalen == QLEN) {
129 IF_DEBUG(DEBUG_TRACE)
130 log(LOG_DEBUG, 0, "Initial traceroute query rcvd "
132 inet6_fmt(&src->sin6_addr),
135 else if ((datalen - QLEN) % RLEN == 0) {
137 IF_DEBUG(DEBUG_TRACE)
138 log(LOG_DEBUG, 0, "In-transit traceroute query rcvd "
140 inet6_fmt(&src->sin6_addr),
142 if (IN6_IS_ADDR_MULTICAST(dst)) {
143 IF_DEBUG(DEBUG_TRACE)
144 log(LOG_DEBUG, 0, "Dropping multicast response");
149 log(LOG_WARNING, 0, "%s from %s to %s",
150 "Non decipherable traceroute request recieved",
151 inet6_fmt(&src->sin6_addr), inet6_fmt(dst));
155 qry = (struct tr6_query *)data;
156 src_sa6.sin6_addr = qry->tr_src;
157 src_sa6.sin6_scope_id =
158 (IN6_IS_ADDR_LINKLOCAL(&qry->tr_src)
159 || IN6_IS_ADDR_MC_LINKLOCAL(&qry->tr_src)) ? ifindex : 0;
160 dst_sa6.sin6_addr = qry->tr_dst;
161 dst_sa6.sin6_scope_id =
162 (IN6_IS_ADDR_LINKLOCAL(&qry->tr_dst)
163 || IN6_IS_ADDR_MC_LINKLOCAL(&qry->tr_dst)) ? ifindex : 0;
164 grp_sa6.sin6_addr = *group;
165 grp_sa6.sin6_scope_id = 0;
168 * if it is a packet with all reports filled, drop it
170 if ((rcount = (datalen - QLEN)/RLEN) == no) {
171 IF_DEBUG(DEBUG_TRACE)
172 log(LOG_DEBUG, 0, "packet with all reports filled in");
176 IF_DEBUG(DEBUG_TRACE) {
177 log(LOG_DEBUG, 0, "s: %s g: %s d: %s ",
178 inet6_fmt(&qry->tr_src),
179 inet6_fmt(group), inet6_fmt(&qry->tr_dst));
180 log(LOG_DEBUG, 0, "rhlim: %d rd: %s", qry->tr_rhlim,
181 inet6_fmt(&qry->tr_raddr));
182 log(LOG_DEBUG, 0, "rcount:%d, qid:%06x", rcount, qry->tr_qid);
185 /* determine the routing table entry for this traceroute */
186 mrt = find_route(&src_sa6, &grp_sa6, MRTF_SG | MRTF_WC | MRTF_PMBR,
188 IF_DEBUG(DEBUG_TRACE) {
189 if (mrt != (mrtentry_t *)NULL) {
190 if (mrt->upstream != (pim_nbr_entry_t *)NULL)
191 parent_address = mrt->upstream->address.sin6_addr;
193 parent_address = in6addr_any;
195 "mrt parent mif: %d rtr: %s metric: %d",
197 inet6_fmt(&parent_address), mrt->metric);
199 log(LOG_DEBUG, 0, "mrt origin %s",
203 log(LOG_DEBUG, 0, "...no route");
207 * Query type packet - check if rte exists
208 * Check if the query destination is a vif connected to me.
209 * and if so, whether I should start response back
212 if (oqid == qry->tr_qid) {
214 * If the multicast router is a member of the group
215 * being queried, and the query is multicasted,
216 * then the router can recieve multiple copies of
217 * the same query. If we have already replied to
218 * this traceroute, just ignore it this time.
220 * This is not a total solution, but since if this
221 * fails you only get N copies, N <= the number of
222 * interfaces on the router, it is not fatal.
224 IF_DEBUG(DEBUG_TRACE)
226 "ignoring duplicate traceroute packet");
230 if (mrt == (mrtentry_t *)NULL) {
231 IF_DEBUG(DEBUG_TRACE)
233 "Mcast traceroute: no route entry %s",
234 inet6_fmt(&qry->tr_src));
236 if (IN6_IS_ADDR_MULTICAST(dst))
240 vifi = find_vif_direct(&dst_sa6);
242 if (vifi == NO_VIF) {
244 * The traceroute destination is not on one of
247 IF_DEBUG(DEBUG_TRACE)
249 "Destination %s not an interface",
250 inet6_fmt(&qry->tr_dst));
251 if (IN6_IS_ADDR_MULTICAST(dst))
253 errcode = TR_WRONG_IF;
254 } else if (mrt != (mrtentry_t *)NULL &&
255 !IF_ISSET(vifi, &mrt->oifs)) {
256 IF_DEBUG(DEBUG_TRACE)
258 "Destination %s not on forwarding tree "
260 inet6_fmt(&qry->tr_dst),
261 inet6_fmt(&qry->tr_src));
262 if (IN6_IS_ADDR_MULTICAST(dst))
264 errcode = TR_WRONG_IF;
269 * determine which interface the packet came in on
270 * RESP packets travel hop-by-hop so this either traversed
271 * a tunnel or came from a directly attached mrouter.
273 if ((vifi = find_vif_direct(src)) == NO_VIF) {
274 IF_DEBUG(DEBUG_TRACE)
276 "Wrong interface for packet");
277 errcode = TR_WRONG_IF;
281 /* Now that we've decided to send a response, save the qid */
284 IF_DEBUG(DEBUG_TRACE)
285 log(LOG_DEBUG, 0, "Sending traceroute response");
287 /* copy the packet to the sending buffer */
288 p = mld6_send_buf + sizeof(struct mld6_hdr);
290 bcopy(data, p, datalen);
295 * If there is no room to insert our reply, coopt the previous hop
296 * error indication to relay this fact.
298 if (p + sizeof(struct tr6_resp) > mld6_send_buf + RECV_BUF_SIZE) {
299 resp = (struct tr6_resp *)p - 1;
300 resp->tr_rflags = TR_NO_SPACE;
306 * fill in initial response fields
308 resp = (struct tr6_resp *)p;
309 bzero(resp, sizeof(struct tr6_resp));
310 datalen += (RLEN + sizeof(struct mld6_hdr));
312 resp->tr_qarr = htonl(((tp.tv_sec + JAN_1970) << 16) +
313 ((tp.tv_usec << 10) / 15625));
315 resp->tr_rproto = PROTO_PIM;
316 resp->tr_outifid = (vifi == NO_VIF) ? TR_NO_VIF : htonl(vifi);
317 resp->tr_rflags = errcode;
318 if ((sa_global = max_global_address()) == NULL) /* impossible */
319 log(LOG_ERR, 0, "acept_mtrace: max_global_address returns NULL");
320 resp->tr_lcladdr = sa_global->sin6_addr;
323 * obtain # of packets out on interface
326 if (vifi != NO_VIF &&
327 ioctl(udp_socket, SIOCGETMIFCNT_IN6, (char *)&mreq) >= 0)
328 resp->tr_vifout = htonl(mreq.ocount);
330 resp->tr_vifout = 0xffffffff;
333 * fill in scoping & pruning information
337 if (mrt != (mrtentry_t *)NULL)
338 for (gt = rt->rt_groups; gt; gt = gt->gt_next) {
339 if (gt->gt_mcastgrp >= group)
345 if (gt && gt->gt_mcastgrp == group) {
348 for (st = gt->gt_srctbl; st; st = st->st_next)
349 if (qry->tr_src == st->st_origin)
352 sg_req.src.s_addr = qry->tr_src;
353 sg_req.grp.s_addr = group;
354 if (st && st->st_ctime != 0 &&
355 ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) >= 0)
356 resp->tr_pktcnt = htonl(sg_req.pktcnt + st->st_savpkt);
358 resp->tr_pktcnt = htonl(st ? st->st_savpkt : 0xffffffff);
360 if (VIFM_ISSET(vifi, gt->gt_scope))
361 resp->tr_rflags = TR_SCOPED;
362 else if (gt->gt_prsent_timer)
363 resp->tr_rflags = TR_PRUNED;
364 else if (!VIFM_ISSET(vifi, gt->gt_grpmems))
365 if (VIFM_ISSET(vifi, rt->rt_children) &&
366 NBRM_ISSETMASK(uvifs[vifi].uv_nbrmap,
367 rt->rt_subordinates)) /*XXX*/
368 resp->tr_rflags = TR_OPRUNED;
370 resp->tr_rflags = TR_NO_FWD;
372 if (scoped_addr(vifi, group))
373 resp->tr_rflags = TR_SCOPED;
374 else if (rt && !VIFM_ISSET(vifi, rt->rt_children))
375 resp->tr_rflags = TR_NO_FWD;
380 * if no rte exists, set NO_RTE error
382 if (mrt == (mrtentry_t *)NULL) {
383 src->sin6_addr = *dst; /* the dst address of resp. pkt */
384 resp->tr_inifid = TR_NO_VIF;
385 resp->tr_rflags = TR_NO_RTE;
386 memset(&resp->tr_rmtaddr, 0, sizeof(struct in6_addr));
388 /* get # of packets in on interface */
389 mreq.mifi = mrt->incoming;
390 if (ioctl(udp_socket, SIOCGETMIFCNT_IN6, (char *)&mreq) >= 0)
391 resp->tr_vifin = htonl(mreq.icount);
393 resp->tr_vifin = 0xffffffff;
397 * MASK_TO_VAL(rt->rt_originmask, resp->tr_smask);
399 resp->tr_inifid = htonl(mrt->incoming);
400 if (mrt->upstream != (pim_nbr_entry_t *)NULL)
401 parent_address = mrt->upstream->address.sin6_addr;
403 parent_address = in6addr_any;
405 resp->tr_rmtaddr = parent_address;
406 if (!IF_ISSET(vifi, &mrt->oifs)) {
407 IF_DEBUG(DEBUG_TRACE)
409 "Destination %s not on forwarding tree "
411 inet6_fmt(&qry->tr_dst),
412 inet6_fmt(&qry->tr_src));
413 resp->tr_rflags = TR_WRONG_IF;
416 if (rt->rt_metric >= UNREACHABLE) {
417 resp->tr_rflags = TR_NO_RTE;
418 /* Hack to send reply directly */
426 * If we're the RP for the trace group, note it.
428 rpentry_ptr = rp_match(&grp_sa6);
429 if (rpentry_ptr && local_address(&rpentry_ptr->address) != NO_VIF)
430 resp->tr_rflags = TR_RP;
435 * if metric is 1 or no. of reports is 1, send response to requestor
436 * else send to upstream router. If the upstream router can't handle
437 * mtrace, set an error code and send to requestor anyway.
439 IF_DEBUG(DEBUG_TRACE)
440 log(LOG_DEBUG, 0, "rcount:%d, no:%d", rcount, no);
442 ovifi = NO_VIF; /* unspecified */
443 if ((rcount + 1 == no) || (mrt == NULL) || (mrt->metric == 1)) {
444 resptype = MLD6_MTRACE_RESP;
445 resp_sa6.sin6_addr = qry->tr_raddr;
446 if (IN6_IS_ADDR_LINKLOCAL(&resp_sa6.sin6_addr) ||
447 IN6_IS_ADDR_MC_LINKLOCAL(&resp_sa6.sin6_addr)) {
448 if ((ovifi = find_vif_direct(&dst_sa6)) == NO_VIF) {
450 "can't determine outgoing i/f for mtrace "
459 if (!can_mtrace(rt->rt_parent, rt->rt_gateway)) {
460 resp_sa6.sin6_addr = qry->tr_raddr;
461 resp->tr_rflags = TR_OLD_ROUTER;
462 resptype = MLD6_MTRACE_RESP;
467 (uvifs[mrt->incoming].uv_flags & MIFF_REGISTER)) {
469 "incoming i/f is for register. "
470 "Can't be forwarded anymore.");
471 resp_sa6.sin6_addr = qry->tr_raddr;
472 resptype = MLD6_MTRACE_RESP;
476 if (mrt->upstream != (pim_nbr_entry_t *)NULL)
478 mrt->upstream->address.sin6_addr;
480 parent_address = allrouters_group.sin6_addr;
481 resp_sa6.sin6_addr = parent_address;
482 ovifi = mrt->incoming;
483 resptype = MLD6_MTRACE;
487 if (IN6_IS_ADDR_MULTICAST(&resp_sa6.sin6_addr)) {
488 struct sockaddr_in6 *sa6;
491 * Send the reply on a known multicast capable vif.
492 * If we don't have one, we can't source any
495 if (IN6_IS_ADDR_MC_LINKLOCAL(&resp_sa6.sin6_addr)) {
496 sa6 = &uvifs[ovifi].uv_linklocal->pa_addr;
497 ifindex = uvifs[ovifi].uv_ifindex;
500 if (phys_vif != -1 &&
501 (sa6 = uv_global(phys_vif)) != NULL) {
502 IF_DEBUG(DEBUG_TRACE)
504 "Sending reply to %s from %s",
506 inet6_fmt(&sa6->sin6_addr));
507 ifindex = uvifs[phys_vif].uv_ifindex;
510 log(LOG_INFO, 0, "No enabled phyints -- %s",
511 "dropping traceroute reply");
515 k_set_hlim(mld6_socket, qry->tr_rhlim);
516 send_mld6(resptype, no, sa6, &resp_sa6, group,
517 ifindex, 0, datalen, 0);
518 k_set_hlim(mld6_socket, 1);
520 struct sockaddr_in6 *sa6 = NULL;
521 ifindex = -1; /* unspecified by default */
523 if (IN6_IS_ADDR_LINKLOCAL(&resp_sa6.sin6_addr)) {
524 /* ovifi must be valid in this case */
525 ifindex = uvifs[ovifi].uv_ifindex;
526 sa6 = &uvifs[ovifi].uv_linklocal->pa_addr;
529 IF_DEBUG(DEBUG_TRACE)
530 log(LOG_DEBUG, 0, "Sending %s to %s from %s",
531 resptype == MLD6_MTRACE_RESP ?
532 "reply" : "request on",
534 sa6 ? inet6_fmt(&sa6->sin6_addr) : "unspecified");
536 send_mld6(resptype, no, sa6, &resp_sa6, group, ifindex,