hello.c

unix/linux下的路由守护程序

/*
 * Public Release 3
 * 
 * $Id: hello.c,v 1.1 1998/06/30 14:42:06 wfs Exp $
 */

/*
 * ------------------------------------------------------------------------
 * 
 * Copyright (c) 1996, 1997 The Regents of the University of Michigan
 * All Rights Reserved
 *  
 * Royalty-free licenses to redistribute GateD Release
 * 3 in whole or in part may be obtained by writing to:
 * 
 * 	Merit GateDaemon Project
 * 	4251 Plymouth Road, Suite C
 * 	Ann Arbor, MI 48105
 *  
 * THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION WARRANTIES OF 
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE REGENTS OF THE
 * UNIVERSITY OF MICHIGAN AND MERIT DO NOT WARRANT THAT THE
 * FUNCTIONS CONTAINED IN THE SOFTWARE WILL MEET LICENSEE'S REQUIREMENTS OR
 * THAT OPERATION WILL BE UNINTERRUPTED OR ERROR FREE. The Regents of the
 * University of Michigan and Merit shall not be liable for
 * any special, indirect, incidental or consequential damages with respect
 * to any claim by Licensee or any third party arising from use of the
 * software. GateDaemon was originated and developed through release 3.0
 * by Cornell University and its collaborators.
 * 
 * Please forward bug fixes, enhancements and questions to the
 * gated mailing list: [e-mail].
 * 
 * ------------------------------------------------------------------------
 * 
 * Copyright (c) 1990,1991,1992,1993,1994,1995 by Cornell University.
 *     All rights reserved.
 * 
 * THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT
 * LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 * GateD is based on Kirton's EGP, UC Berkeley's routing
 * daemon	 (routed), and DCN's HELLO routing Protocol.
 * Development of GateD has been supported in part by the
 * National Science Foundation.
 * 
 * ------------------------------------------------------------------------
 * 
 * Portions of this software may fall under the following
 * copyrights:
 * 
 * Copyright (c) 1988 Regents of the University of California.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms are
 * permitted provided that the above copyright notice and
 * this paragraph are duplicated in all such forms and that
 * any documentation, advertising materials, and other
 * materials related to such distribution and use
 * acknowledge that the software was developed by the
 * University of California, Berkeley.  The name of the
 * University may not be used to endorse or promote
 * products derived from this software without specific
 * prior written permission.  THIS SOFTWARE IS PROVIDED
 * ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */


/*
 *	Hello output routines were taken from Mike Petry ([e-mail])
 *	Also, hello input routines were written by Bill Nesheim, Cornell
 *	CS Dept,  Currently at [e-mail]
 */

#define	INCLUDE_TIME
#include "include.h"
#include "inet.h"
#include "targets.h"
#include "hello.h"

flag_t hello_flags;			/* Options */
trace *hello_trace_options;		/* Trace flags from parser */
metric_t hello_default_metric = HELLO_UNREACHABLE;	/* Default metric to use when propogating */
pref_t hello_preference = RTPREF_HELLO;	/* Preference for HELLO routes */

static task_timer *hello_timer_update;		/* To send updates */
static task_timer *hello_timer_flash;		/* To send flash updates */
static task_timer *hello_timer_age;		/* To age routes */

static task_job *hello_target_list_job;		/* To rebuild target list after interface changes */
static target hello_targets = { &hello_targets, &hello_targets };	/* Target list */

static block_t hello_win_block_index;	/* Allocation index for hello window */

int hello_n_trusted;			/* Number of trusted gateways */
int hello_n_source;			/* Number of source gateways */
gw_entry *hello_gw_list;		/* List of HELLO gateways */
adv_entry *hello_import_list;		/* List of nets to import from HELLO */
adv_entry *hello_export_list;		/* LIst of sources to exports routes to HELLO */
adv_entry *hello_int_policy;		/* List of interface policy */


static const bits hello_flag_bits[] = {
{ HELLOF_ON,		"ON" },
{ HELLOF_BROADCAST,	"Broadcast" },
{ HELLOF_SOURCE,	"Source" },
{ HELLOF_CHOOSE,	"Choose" },
{ HELLOF_FLASHDUE,	"FlashDue" },
{ HELLOF_NOFLASH,	"NoFlash" },    
{ HELLOF_RECONFIG,	"ReConfig" },
{ 0 }
} ;

static const flag_t hello_trace_masks[1] = {
	TR_HELLO_DETAIL
} ;

const bits hello_trace_types[] = {
    { TR_DETAIL,		"detail packets" },
    { TR_DETAIL_SEND,	"detail send packets" },
    { TR_DETAIL_RECV,	"detail recv packets" },
    { TR_PACKET,		"packets" },
    { TR_PACKET_SEND,	"send packets" },
    { TR_PACKET_RECV,	"recv packets" },
    { TR_DETAIL_1,	"detail packets" },
    { TR_DETAIL_SEND_1,	"detail send packets" },
    { TR_DETAIL_RECV_1,	"detail recv packets" },
    { TR_PACKET_1,	"packets" },
    { TR_PACKET_SEND_1,	"send packets" },
    { TR_PACKET_RECV_1,	"recv packets" },
    { 0, NULL }
};

metric_t hop_to_hello[] =
{					/* Translate interface metric to hello metric */
    0,					/* 0 */
    100,				/* 1 */
    148,				/* 2 */
    219,				/* 3 */
    325,				/* 4 */
    481,				/* 5 */
    713,				/* 6 */
    1057,				/* 7 */
    1567,				/* 8 */
    2322,				/* 9 */
    3440,				/* 10 */
    5097,				/* 11 */
    7552,				/* 12 */
    11190,				/* 13 */
    16579,				/* 14 */
    24564,				/* 15 */
    30000				/* 16 */
};


/* Routines for support of the hello window system */

/*
 * initialize the sliding HELLO history window.
 */
static void
hello_win_init __PF2(vp, void_t,
		     tdelay, metric_t)
{
    struct hello_win *hwp = (struct hello_win *) vp;
    int msf = 0;

    while (msf < HWINSIZE) {
	hwp->h_win[msf++] = HELLO_UNREACHABLE;
    }
    hwp->h_index = 0;
    hwp->h_min = tdelay;
    hwp->h_min_ttl = 0;
    hwp->h_win[0] = tdelay;
}


/*
 * add a HELLO derived time delay to the route entries HELLO window.
 */
static void
hello_win_add __PF2(vp, void_t,
		    tdelay, metric_t)
{
    struct hello_win *hwp = (struct hello_win *) vp;
    int msf, t_index = 0;

    hwp->h_index++;
    if (hwp->h_index >= HWINSIZE) {
	hwp->h_index = 0;
    }
    hwp->h_win[hwp->h_index] = tdelay;
    if (tdelay > hwp->h_min) {
	hwp->h_min_ttl++;
    } else {
	hwp->h_min = tdelay;
	hwp->h_min_ttl = 0;
    }
    if (hwp->h_min_ttl >= HWINSIZE) {
	hwp->h_min = HELLO_UNREACHABLE;
	for (msf = 0; msf < HWINSIZE; msf++) {
	    if (hwp->h_win[msf] <= hwp->h_min) {
		hwp->h_min = hwp->h_win[msf];
		t_index = msf;
	    }
	}
	hwp->h_min_ttl = 0;
	if (t_index < hwp->h_index) {
	    hwp->h_min_ttl = hwp->h_index - t_index;
	} else if (t_index > hwp->h_index) {
	    hwp->h_min_ttl = HWINSIZE - (t_index - hwp->h_index);
	}
    }
}


/*
 *	Dump info about a HELLO route
 */
static void
hello_rt_dump __PF2(fd, FILE *,
		    rt, rt_entry *)
{
    int cnt, ind;
    struct hello_win *hwp = (struct hello_win *) rt->rt_data;

    (void) fprintf(fd, "\t\t\tMinimum HELLO time delay in last %d updates: %d\n",
		   HWINSIZE,
		   hwp->h_min);
    (void) fprintf(fd, "\t\t\tLast %d HELLO time delays:\n\t\t",
		   HELLO_REPORT);
    ind = hwp->h_index;
    for (cnt = HELLO_REPORT; cnt; cnt--) {
	(void) fprintf(fd, "%d ",
		       hwp->h_win[ind]);
	if (++ind >= HWINSIZE) {
	    ind = 0;
	}
    }
    (void) fprintf(fd, "\n");
}


/*
 *	Dump protocol specific info
 */
static void
hello_rt_free __PF2(rt, rt_entry *,
		    rtd, void_t)
{
    task_block_free(hello_win_block_index, rtd);
}


/*
 *	Trace a HELLO packet
 */
/*ARGSUSED*/
static void
hello_trace __PF8(tp, task *,
		  comment, const char *,
		  src, sockaddr_un *,
		  dst, sockaddr_un *,
		  packet, void_t,
		  length, size_t,
		  nets, int,
		  detail, int)
{
    u_int i;
    const char *cp;
    byte *hello = (byte *) packet;
    byte *end = hello + length;
    struct hm_hdr hm_hdr;
    struct hellohdr hellohdr;
    struct type0pair type0pair;
    struct type1pair type1pair;

    tracef("HELLO %s %A -> %A  %d bytes",
	   comment,
	   src,
	   dst,
	   length);
    if (nets >= 0) {
	tracef("  %d nets",
	       nets);
    }

    /* Calculate the checksum of this packet */
    if (inet_cksum(packet, length)) {
	tracef(" *checksum bad*");
    }	
    trace_only_tp(tp,
		  0,
		  (NULL));

    PickUp_hellohdr(hello, hellohdr);

    if (detail) {
	switch (hellohdr.h_date & H_DATE_BITS) {
	    case H_DATE_LEAPADD:
		cp = "add_leap_second ";
		break;
	    case H_DATE_LEAPDEL:
		cp = "del_leap_second ";
		break;
	    case H_DATE_UNSYNC:
		cp = "unsync ";
		break;
	    default:
		cp = "";
	}
	BIT_RESET(hellohdr.h_date, H_DATE_BITS);
	trace_only_tp(tp,
		      TRC_NOSTAMP,
		      ("HELLO %s %s%d/%d/%d %02d:%02d:%02d.%03d GMT  tstp %d",
		       comment,
		       cp,
		       (hellohdr.h_date >> H_DATE_MON_SHIFT) & H_DATE_MON_MASK,
		       (hellohdr.h_date >> H_DATE_DAY_SHIFT) & H_DATE_DAY_MASK,
		       ((hellohdr.h_date >> H_DATE_YEAR_SHIFT) & H_DATE_YEAR_MASK) + H_DATE_YEAR_BASE,
		       hellohdr.h_time / (60 * 60 * 1000),
		       (hellohdr.h_time / (60 * 1000)) % 60,
		       (hellohdr.h_time / (1000)) % 60,
		       hellohdr.h_time % 1000,
		       hellohdr.h_tstp));

	while (hello < end) {
	    PickUp_hm_hdr(hello, hm_hdr);
	    trace_only_tp(tp,
			  TRC_NOSTAMP,
			  ("%s\ttype %d  count %d",
			   comment,
			   hm_hdr.hm_type,
			   hm_hdr.hm_count));
	    for (i = 0; i < hm_hdr.hm_count; i++) {
		switch (hm_hdr.hm_type) {
		    case 0:
			PickUp_type0pair(hello, type0pair);
			trace_only_tp(tp,
				      TRC_NOSTAMP,
				      ("%s\t\tdelay %d  offset %d",
				       comment,
				       type0pair.d0_delay,
				       type0pair.d0_offset));
			break;
		    case 1:
			PickUp_type1pair(hello, type1pair);
			trace_only_tp(tp,
				      TRC_NOSTAMP,
				      ("%s\t\t%-15A  delay %5d  offset %d",
				       comment,
				       sockbuild_in(0, type1pair.d1_dst),
				       type1pair.d1_delay,
				       type1pair.d1_offset));
			break;
		    default:
			trace_only_tp(tp,
				      TRC_NOSTAMP,
				      ("%s\t\tInvalid type - giving up!",
				       comment));
			return;
		}
	    }
	}
	trace_only_tp(tp,
		      0,
		      (NULL));
    }
}


/*
 * hello_send():
 * 	Fill in the hello header and checksum, then send the packet.
 */
static void
hello_send __PF4(tlp, target *,
		 packet, byte *,
		 fillp, byte *,
		 maxsize, size_t *)
{
    byte *hello;
    struct hellohdr hellohdr;
    struct hm_hdr hm_hdr;
    utime_t hello_time;
    struct tm *gmt;
    int error = FALSE;
    size_t length = fillp - packet;

    /*
     * All packets in an update must be the same size, padding should be used
     * if necessary to insure this.  This is for timing that we don't do, but
     * lets be consistent.
     */
    if (length > *maxsize) {
	/* Remember the largest packet */
	*maxsize = length;
    } else {
	/* Pad this packet out to the size of the largest sent */
	bzero ((caddr_t) fillp, *maxsize - length);
	length = *maxsize;
    }

    TIMER_PEEK();
    hello_time.ut_sec = utime_current.ut_sec + utime_boot.ut_sec;
    hello_time.ut_usec = utime_current.ut_usec + utime_boot.ut_usec;
    if (hello_time.ut_usec >= 1000000) {
	hello_time.ut_usec -= 1000000;
	hello_time.ut_sec += 1;
    }
    gmt = (struct tm *) gmtime(&hello_time.ut_sec);

    /*
     * set the date field in the HELLO header.  Be very careful here as
     * the last two bits (14&15) should be set so the Fuzzware doesn't use
     * this packet to synchronize its Master Clock.  Using bitwise OR's
     * instead of addition just to be safe when dealing with h_date which
     * is an unsigned short.
     */
    hellohdr.h_date = ((gmt->tm_year - H_DATE_YEAR_BASE) & H_DATE_YEAR_MASK) |
	((gmt->tm_mday & H_DATE_DAY_MASK) << H_DATE_DAY_SHIFT) |
	    (((gmt->tm_mon + 1) & H_DATE_MON_MASK) << H_DATE_MON_SHIFT) |
		H_DATE_UNSYNC;
    /*
     * milliseconds since midnight UT of current day
     */
#define	MULBY60(X)	(((X) << 6) - ((X) << 2))
#define	MULBY1000(X)	(((X) << 10) - ((X) << 4) - ((X) << 3))
    hello_time.ut_sec = (time_t) (MULBY60(gmt->tm_hour) + gmt->tm_min);
    hello_time.ut_sec = MULBY60(hello_time.ut_sec) + (time_t) gmt->tm_sec;
    hellohdr.h_time = MULBY1000(hello_time.ut_sec) + hello_time.ut_usec / 1000;
#undef	MULBY1000
#undef	MULBY60

    /*
     * 16 bit field used in rt calculation,  0 for ethernets
     */
    hellohdr.h_tstp = 0;
    hellohdr.h_cksum = 0;
    hello = packet;
    PutDown_hellohdr(hello, hellohdr);

    /* Build the hm header */
    hm_hdr.hm_type = 1;
    hm_hdr.hm_count = (length - Size_hellohdr - Size_hm_hdr) / Size_type1pair;

    /* Check for packet size skew */
    assert((hm_hdr.hm_count * Size_type1pair) == (length - Size_hellohdr - Size_hm_hdr));

    PutDown_hm_hdr(hello, hm_hdr);

    /* Calculate the checksum and put it into the packet */
    hellohdr.h_cksum = inet_cksum((void_t) packet, length);
    hello = packet;
    PutDown(hello, hellohdr.h_cksum);

    if (task_send_packet(tlp->target_task,
			 (void_t) packet,
			 length,
			 0,
			 *tlp->target_dst) < 0) {
	error = TRUE;
    }

    if (TRACE_PACKET_SEND_TP(tlp->target_task,
			     0,
			     0,
			     hello_trace_masks)) {
	hello_trace(tlp->target_task,
		    error ? "*NOT* SENT" : "SENT",
		    *tlp->target_src,
		    *tlp->target_dst,
		    packet,
		    length,
		    (int) hm_hdr.hm_count,
		    TRACE_DETAIL_SEND_TP(tlp->target_task,
					 0,
					 0,
					 hello_trace_masks));
    }
    return;
}


/*
 *	Process an incomming HELLO packet
 */
static void
hello_recv __PF1(tp, task *)
{
    int n_packets = TASK_PACKET_LIMIT;
    size_t count;

    while (n_packets-- && !task_receive_packet(tp, &count)) {
	u_int i;
	struct ip *ip;
	register byte *hello;
	byte *end;
	size_t hello_len;
	struct hm_hdr hm_hdr;
	if_addr *ifap;
	rt_parms rtparms;

	task_parse_ip(ip, hello, byte *);

	hello_len = ip->ip_len;
	end = hello + hello_len;

	if (TRACE_PACKET_RECV_TP(tp,
				 0,
				 0,
				 hello_trace_masks)) {
	    hello_trace(tp,
			"RECV",
			task_recv_srcaddr,
			sockbuild_in(0, ip->ip_dst.s_addr),
			(void_t) hello,
			hello_len,
			-1,
			TRACE_DETAIL_RECV_TP(tp,
					     0,
					     0,
					     hello_trace_masks));
	}