This is mrouted version 3.5, with the route-change notification hook from

mrouted-3.5n.  This is being splatted onto the head rather than properly
imported thanks to the ``delete trailing whitespace'' screw.  This code is
now actively working in an operational environment (the DARTNET) so I
have some confidence that the basic functionality actually works.

Obtained from: Bill Fenner, PARC, and ISI

1 files changed, 87 insertions, 67 deletions

diff --git a/usr.sbin/mrouted/prune.h b/usr.sbin/mrouted/prune.h
index fd1fd23..dadba5d 100644
--- a/usr.sbin/mrouted/prune.h
+++ b/usr.sbin/mrouted/prune.h
@@ -7,91 +7,104 @@
  * Leland Stanford Junior University.
  *
  *
- * $Id: prune.h,v 1.2 1994/09/08 02:51:24 wollman Exp $
+ * $Id: prune.h,v 3.5 1995/05/09 01:00:39 fenner Exp $
  */
 
 /*
- * Macro for copying the user-level cache table to the kernel
- * level table variable passed on by the setsock option
+ * Group table
+ *
+ * Each group entry is a member of two doubly-linked lists:
+ *
+ * a) A list hanging off of the routing table entry for this source (rt_groups)
+ *	sorted by group address under the routing entry (gt_next, gt_prev)
+ * b) An independent list pointed to by kernel_table, which is a list of
+ *	active source,group's (gt_gnext, gt_gprev).
+ *
  */
-
-#define COPY_TABLES(from, to) { \
-	register u_int _i; \
-	(to).mfcc_origin.s_addr     = (from)->kt_origin; \
-	(to).mfcc_mcastgrp.s_addr   = (from)->kt_mcastgrp; \
-	(to).mfcc_originmask.s_addr = (from)->kt_originmask; \
-	(to).mfcc_parent            = (from)->kt_parent; \
-	for (_i = 0; _i < numvifs; _i++) \
-	    (to).mfcc_ttls[_i]	  = (from)->kt_ttls[_i]; \
+struct gtable {
+    struct gtable  *gt_next;		/* pointer to the next entry	    */
+    struct gtable  *gt_prev;		/* back pointer for linked list	    */
+    struct gtable  *gt_gnext;		/* fwd pointer for group list	    */
+    struct gtable  *gt_gprev;		/* rev pointer for group list	    */
+    u_int32	    gt_mcastgrp;	/* multicast group associated       */
+    vifbitmap_t     gt_scope;		/* scoped interfaces                */
+    u_char	    gt_ttls[MAXVIFS];	/* ttl vector for forwarding        */
+    vifbitmap_t	    gt_grpmems;		/* forw. vifs for src, grp          */
+    int		    gt_prsent_timer;	/* prune timer for this group	    */
+    int  	    gt_timer;		/* timer for this group entry	    */
+    time_t 	    gt_ctime;		/* time of entry creation         */
+    u_char	    gt_grftsnt;		/* graft sent/retransmit timer	    */
+    struct stable  *gt_srctbl;		/* source table			    */
+    struct ptable  *gt_pruntbl;		/* prune table			    */
+    struct rtentry *gt_route;		/* parent route			    */
+#ifdef RSRR
+    struct rsrr_cache *gt_rsrr_cache;	/* RSRR cache                       */
+#endif /* RSRR */
 };
 
-
 /*
- * User level Kernel Cache Table structure
- *
- * A copy of the kernel table is kept at the user level. Modifications are
- * made to this table and then passed on to the kernel. A timeout value is
- * an extra field in the user level table.
+ * Source table
  *
+ * When source-based prunes exist, there will be a struct ptable here as well.
  */
-struct ktable
+struct stable 
 {
-    struct ktable  *kt_next;       	/* pointer to the next entry        */
-    u_long	    kt_origin;		/* subnet origin of multicasts      */
-    u_long	    kt_mcastgrp;    	/* multicast group associated       */
-    u_long	    kt_originmask;	/* subnet mask for origin           */
-    vifi_t	    kt_parent; 	    	/* incoming vif                     */
-    u_long	    kt_gateway;		/* upstream router                  */
-    vifbitmap_t	    kt_children;	/* outgoing children vifs           */
-    vifbitmap_t	    kt_leaves;		/* subset of outgoing children vifs */
-    vifbitmap_t     kt_scope;		/* scoped interfaces                */
-    u_char	    kt_ttls[MAXVIFS];	/* ttl vector for forwarding        */
-    vifbitmap_t	    kt_grpmems;		/* forw. vifs for src, grp          */
-    int		    kt_timer;		/* for timing out entry in cache    */
-    struct prunlst *kt_rlist;		/* router list nghboring this rter  */
-    u_short	    kt_prun_count;	/* count of total no. of prunes     */
-    int		    kt_prsent_timer;	/* prune lifetime timer             */
-    u_int	    kt_grftsnt;		/* graft sent upstream              */
+    struct stable  *st_next;       	/* pointer to the next entry        */
+    u_int32	    st_origin;		/* host origin of multicasts        */
+    u_long	    st_pktcnt;		/* packet count for src-grp entry   */
 };
 
 /*
- * structure to store incoming prunes
+ * structure to store incoming prunes.  Can hang off of either group or source.
  */
-struct prunlst
+struct ptable 
 {
-    struct prunlst *rl_next;
-    u_long	    rl_router;
-    u_long	    rl_router_subnet;
-    vifi_t	    rl_vifi;
-    int		    rl_timer;
+    struct ptable  *pt_next;		/* pointer to the next entry	    */
+    u_int32	    pt_router;		/* router that sent this prune	    */
+    vifi_t	    pt_vifi;		/* vif prune received on	    */
+    int		    pt_timer;		/* timer for prune		    */
 };
 
+/*
+ * The packet format for a traceroute request.
+ */
 struct tr_query {
-    u_long  tr_src;		/* traceroute source */
-    u_long  tr_dst;		/* traceroute destination */
-    u_long  tr_raddr;		/* traceroute response address */
+    u_int32  tr_src;		/* traceroute source */
+    u_int32  tr_dst;		/* traceroute destination */
+    u_int32  tr_raddr;		/* traceroute response address */
+#if defined(BYTE_ORDER) && (BYTE_ORDER == LITTLE_ENDIAN)
+    struct {
+	u_int	qid : 24;	/* traceroute query id */
+	u_int	ttl : 8;	/* traceroute response ttl */
+    } q;
+#else
     struct {
 	u_int   ttl : 8;	/* traceroute response ttl */
 	u_int   qid : 24;	/* traceroute query id */
     } q;
-} tr_query;
+#endif /* BYTE_ORDER */
+};
 
 #define tr_rttl q.ttl
 #define tr_qid  q.qid
 
+/*
+ * Traceroute response format.  A traceroute response has a tr_query at the
+ * beginning, followed by one tr_resp for each hop taken.
+ */
 struct tr_resp {
-    u_long  tr_qarr;		/* query arrival time */
-    u_long  tr_inaddr;		/* incoming interface address */
-    u_long  tr_outaddr;		/* outgoing interface address */
-    u_long  tr_rmtaddr;		/* parent address in source tree */
-    u_long  tr_vifin;		/* input packet count on interface */
-    u_long  tr_vifout;		/* output packet count on interface */
-    u_long  tr_pktcnt;		/* total incoming packets for src-grp */
+    u_int32 tr_qarr;		/* query arrival time */
+    u_int32 tr_inaddr;		/* incoming interface address */
+    u_int32 tr_outaddr;		/* outgoing interface address */
+    u_int32 tr_rmtaddr;		/* parent address in source tree */
+    u_int32 tr_vifin;		/* input packet count on interface */
+    u_int32 tr_vifout;		/* output packet count on interface */
+    u_int32 tr_pktcnt;		/* total incoming packets for src-grp */
     u_char  tr_rproto;		/* routing protocol deployed on router */
     u_char  tr_fttl;		/* ttl required to forward on outvif */
     u_char  tr_smask;		/* subnet mask for src addr */
     u_char  tr_rflags;		/* forwarding error codes */
-} tr_resp;
+};
 
 /* defs within mtrace */
 #define QUERY	1
@@ -100,24 +113,31 @@ struct tr_resp {
 #define RLEN	sizeof(struct tr_resp)
 
 /* fields for tr_rflags (forwarding error codes) */
-#define TR_NO_ERR	0x0
-#define TR_WRONG_IF	0x1
-#define TR_PRUNED	0x2
-#define TR_SCOPED	0x4
-#define TR_NO_RTE	0x5
+#define TR_NO_ERR	0
+#define TR_WRONG_IF	1
+#define TR_PRUNED	2
+#define TR_OPRUNED	3
+#define TR_SCOPED	4
+#define TR_NO_RTE	5
+#define TR_NO_FWD	7
+#define TR_NO_SPACE	0x81
+#define TR_OLD_ROUTER	0x82
 
 /* fields for tr_rproto (routing protocol) */
-#define PROTO_DVMRP	0x1
-#define PROTO_MOSPF	0x2
-#define PROTO_PIM	0x3
-#define PROTO_CBT	0x4
+#define PROTO_DVMRP	1
+#define PROTO_MOSPF	2
+#define PROTO_PIM	3
+#define PROTO_CBT	4
 
 #define MASK_TO_VAL(x, i) { \
+			u_int32 _x = ntohl(x); \
 			(i) = 0; \
-			while ((x) << (i)) \
+			while ((_x) << (i)) \
 				(i)++; \
-			}
+			};
 
 #define VAL_TO_MASK(x, i) { \
-			x = ~((1 << (32 - (i))) - 1); \
-			}
+			x = htonl(~((1 << (32 - (i))) - 1)); \
+			};
+
+#define NBR_VERS(n)	(((n)->al_pv << 8) + (n)->al_mv)