/*	$NetBSD: route.c,v 1.5 1995/12/10 10:07:12 mycroft Exp $	*/

/*

 * The mrouted program is covered by the license in the accompanying file

 * named "LICENSE".  Use of the mrouted program represents acceptance of

 * the terms and conditions listed in that file.

 *

 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of

 * Leland Stanford Junior University.

 */

#include "defs.h"

/*

 * This define statement saves a lot of space later

 */

#define RT_ADDR	(struct rtentry *)&routing_table

/*

 * Exported variables.

 */

int routes_changed;			/* 1=>some routes have changed */

int delay_change_reports;		/* 1=>postpone change reports  */

/*

 * The routing table is shared with prune.c , so must not be static.

 */

struct rtentry *routing_table;		/* pointer to list of route entries */

/*

 * Private variables.

 */

static struct rtentry *rtp;		/* pointer to a route entry         */

static struct rtentry *rt_end;		/* pointer to last route entry      */

unsigned int nroutes;			/* current number of route entries  */

/*

 * Private functions.

 */

static int init_children_and_leaves(struct rtentry *r, vifi_t parent);

static int find_route(u_int32_t origin, u_int32_t mask);

static void create_route(u_int32_t origin, u_int32_t mask);

static void discard_route(struct rtentry *prev_r);

static int compare_rts(const void *rt1, const void *rt2);

static int report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst);

/*

 * Initialize the routing table and associated variables.

 */

void

init_routes()

{

}

/*

 * Initialize the children and leaf bits for route 'r', along with the

 * associated dominant, subordinate, and leaf timing data structures.

 * Return TRUE if this changes the value of either the children or

 * leaf bitmaps for 'r'.

 */

static int

init_children_and_leaves(struct rtentry *r, vifi_t parent)

{

    vifi_t vifi;

    struct uvif *v;

    vifbitmap_t old_children, old_leaves;

	    }

	    else {

	    }

	}

	else {

	}

    }

}

/*

 * A new vif has come up -- update the children and leaf bitmaps in all route

 * entries to take that into account.

 */

void

add_vif_to_routes(vifi_t vifi)

{

    struct rtentry *r;

    struct uvif *v;

	    }

	    else {

	    }

	}

    }

}

/*

 * A vif has gone down -- expire all routes that have that vif as parent,

 * and update the children bitmaps in all other route entries to take into

 * account the failed vif.

 */

void

delete_vif_from_routes(vifi_t vifi)

{

    struct rtentry *r;

	    }

	    }

	    else {

	    }

	}

    }

}

/*

 * A neighbor has failed or become unreachable.  If that neighbor was

 * considered a dominant or subordinate router in any route entries,

 * take appropriate action.

 */

void

delete_neighbor_from_routes(u_int32_t addr, vifi_t vifi)

{

    struct rtentry *r;

    struct uvif *v;

		}

		else {

		}

	    }

		}

		else {

		}

	    }

	    }

	}

    }

}

/*

 * Prepare for a sequence of ordered route updates by initializing a pointer

 * to the start of the routing table.  The pointer is used to remember our

 * position in the routing table in order to avoid searching from the

 * beginning for each update; this relies on having the route reports in

 * a single message be in the same order as the route entries in the routing

 * table.

 */

void

start_route_updates(void)

{

}

/*

 * Starting at the route entry following the one to which 'rtp' points,

 * look for a route entry matching the specified origin and mask.  If a

 * match is found, return TRUE and leave 'rtp' pointing at the found entry.

 * If no match is found, return FALSE and leave 'rtp' pointing to the route

 * entry preceding the point at which the new origin should be inserted.

 * This code is optimized for the normal case in which the first entry to

 * be examined is the matching entry.

 */

static int

find_route(u_int32_t origin, u_int32_t mask)

{

    struct rtentry *r;

	}

	}

	else break;

    }

}

/*

 * Create a new routing table entry for the specified origin and link it into

 * the routing table.  The shared variable 'rtp' is assumed to point to the

 * routing entry after which the new one should be inserted.  It is left

 * pointing to the new entry.

 *

 * Only the origin, originmask, originwidth and flags fields are initialized

 * in the new route entry; the caller is responsible for filling in the rest.

 */

static void

create_route(u_int32_t origin, u_int32_t mask)

{

    struct rtentry *r;

    }

    else                              r->rt_originwidth = 1;

    else

      rt_end = r;

}

/*

 * Discard the routing table entry following the one to which 'prev_r' points.

 */

static void

discard_route(struct rtentry *prev_r)

{

    struct rtentry *r;

    else

      rt_end = prev_r;

}

/*

 * Process a route report for a single origin, creating or updating the

 * corresponding routing table entry if necessary.  'src' is either the

 * address of a neighboring router from which the report arrived, or zero

 * to indicate a change of status of one of our own interfaces.

 */

void

update_route(u_int32_t origin, u_int32_t mask, u_int metric, u_int32_t src,

    vifi_t vifi)

{

    struct rtentry *r;

    u_int adj_metric;

    /*

     * Compute an adjusted metric, taking into account the cost of the

     * subnet or tunnel over which the report arrived, and normalizing

     * all unreachable/poisoned metrics into a single value.

     */

	    "%s reports out-of-range metric %u for origin %s",

    }

    /*

     * Look up the reported origin in the routing table.

     */

	/*

	 * Not found.

	 * Don't create a new entry if the report says it's unreachable,

	 * or if the reported origin and mask are invalid.

	 */

	}

		"%s reports an invalid origin (%s) and/or mask (%08x)",

	}

	/*

	 * OK, create the new routing entry.  'rtp' will be left pointing

	 * to the new entry.

	 */

	/*

	 * Now "steal away" any sources that belong under this route

	 * by deleting any cache entries they might have created

	 * and allowing the kernel to re-request them.

	 */

    }

    /*

     * We now have a routing entry for the reported origin.  Update it?

     */

	/*

	 * The routing entry is for a formerly-unreachable or new origin.

	 * If the report claims reachability, update the entry to use

	 * the reported route.

	 */

    }

	/*

	 * The report has come either from the interface directly-connected

	 * to the origin subnet (src and r->rt_gateway both equal zero) or

	 * from the gateway we have chosen as the best first-hop gateway back

	 * towards the origin (src and r->rt_gateway not equal zero).  Reset

	 * the route timer and, if the reported metric has changed, update

	 * our entry accordingly.

	 */

	}

	    }

	}

    }

	/*

	 * The report is for an origin we consider reachable; the report

	 * comes either from one of our own interfaces or from a gateway

	 * other than the one we have chosen as the best first-hop gateway

	 * back towards the origin.  If the source of the update is one of

	 * our own interfaces, or if the origin is not a directly-connected

	 * subnet and the reported metric for that origin is better than

	 * what our routing entry says, update the entry to use the new

	 * gateway and metric.  We also switch gateways if the reported

	 * metric is the same as the one in the route entry and the gateway

	 * associated with the route entry has not been heard from recently,

	 * or if the metric is the same but the reporting gateway has a lower

	 * IP address than the gateway associated with the route entry.

	 * Did you get all that?

	 */

	    /*

	     * XXX Why do we do this if we are just changing the metric?

	     */

	    }

	}

    }

	/*

	 * The report came from a vif other than the route's parent vif.

	 * Update the children and leaf info, if necessary.

	 */

	    /*

	     * Vif is a child vif for this route.

	     */

		/*

		 * Neighbor has lower metric to origin (or has same metric

		 * and lower IP address) -- it becomes the dominant router,

		 * and vif is no longer a child for me.

		 */

	    }

		/*

		 * Neighbor considers this vif to be on path to route's

		 * origin; if no subordinate recorded, record this neighbor

		 * as subordinate and clear the leaf flag.

		 */

		}

	    }

		/*

		 * Current subordinate no longer considers this vif to be on

		 * path to route's origin; it is no longer a subordinate

		 * router, and we set the leaf confirmation timer to give

		 * us time to hear from other subordinates.

		 */

		}

		else {

		}

	    }

	}

	    /*

	     * Current dominant no longer has a lower metric to origin

	     * (or same metric and lower IP address); we adopt the vif

	     * as our own child.

	     */

	    }

	    }

	    else {

	    }

	}

    }

}

/*

 * On every timer interrupt, advance the timer in each routing entry.

 */

void

age_routes(void)

{

    struct rtentry *r;

    struct rtentry *prev_r;

    vifi_t vifi;

	    /*

	     * Route is still good; see if any leaf timers need to be

	     * advanced.

	     */

			/*

			 * Unlike other timers, leaf timers decrement.

			 */

#ifdef NOTYET

			    /* If the vif is a physical leaf but has neighbors,

			     * it is not a tree leaf.  If I am a leaf, then no

			     * interface with neighbors is a tree leaf. */

			    if (!(((uvifs[vifi].uv_flags & VIFF_LEAF) ||

				   (vifs_with_neighbors == 1)) &&

				  (uvifs[vifi].uv_neighbors != NULL))) {

#endif

#ifdef NOTYET

			    }

#endif

			}

			else {

			}

		    }

		}

	    }

	}

	    /*

	     * Time to garbage-collect the route entry.

	     */

	    r = prev_r;

	}

	    /*

	     * Time to expire the route entry.  If the gateway is zero,

	     * i.e., it is a route to a directly-connected subnet, just

	     * set the timer back to zero; such routes expire only when

	     * the interface to the subnet goes down.

	     */

	    }

	    else {

	    }

	}

    }

}

/*

 * Mark all routes as unreachable.  This function is called only from

 * hup() in preparation for informing all neighbors that we are going

 * off the air.  For consistency, we ought also to delete all reachable

 * route entries from the kernel, but since we are about to exit we rely

 * on the kernel to do its own cleanup -- no point in making all those

 * expensive kernel calls now.

 */

void

expire_all_routes(void)

{

    struct rtentry *r;

    }

}

/*

 * Delete all the routes in the routing table.

 */

void

free_all_routes(void)

{

    struct rtentry *r;

    r = RT_ADDR;

}

/*

 * Process an incoming neighbor probe message.

 */

void

accept_probe(u_int32_t src, u_int32_t dst, char *p, int datalen,

    u_int32_t level)

{

    vifi_t vifi;

    }

}

struct newrt {

	u_int32_t mask;

	u_int32_t origin;

	int metric;

	int pad;

};

static int

compare_rts(const void *rt1, const void *rt2)

{

    u_int32_t o1, o2;

    /* masks are equal */

}

/*

 * Process an incoming route report message.

 */

void

accept_report(u_int32_t src, u_int32_t dst, char *p, int datalen,

    u_int32_t level)

{

    vifi_t vifi;

    int width, i, nrt = 0;

    int metric;

    u_int32_t mask;

    }

	    "ignoring oversize (%d bytes) route report from %s",

    }

		"received truncated route report from %s",

	}

	((u_char *)&mask)[0] = 0xff;            width = 1;

		"%s reports bogus netmask 0x%08x (%s)",

	}

		    "received truncated route report from %s",

	    }

    }

    /*

     * If the last entry is default, change mask from 0xff000000 to 0

     */

	}

		     src, vifi);

    }

}

/*

 * Send a route report message to destination 'dst', via virtual interface

 * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.

 */

void

report(int which_routes, vifi_t vifi, u_int32_t dst)

{

    struct rtentry *r;

    char *p;

    int i;

    int datalen = 0;

    int width = 0;

    u_int32_t mask = 0;

    u_int32_t src;

    u_int32_t nflags;

#ifdef NOTYET

    /* If I'm not a leaf, but the neighbor is a leaf, only advertise default */

    if ((vifs_with_neighbors != 1) && (uvifs[vifi].uv_flags & VIFF_LEAF)) {

      *p++ = 0;       /* 0xff000000 mask */

      *p++ = 0;

      *p++ = 0;

      *p++ = 0;       /* class A net 0.0.0.0 == default */

      *p++ = 0x81;    /*XXX metric 1, is this safe? */

      datalen += 5;

      send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,

                htonl(MROUTED_LEVEL), datalen);

      return;

    }

#endif

	    continue;

	/*

	 * If there is no room for this route in the current message,

	 * send the message and start a new one.

	 */

	    datalen = 0;

	    mask = 0;

	}

	}

    }

    }

}

/*

 * Send a route report message to all neighboring routers.

 * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.

 */

void

report_to_all_neighbors(int which_routes)

{

    vifi_t vifi;

    struct uvif *v;

    struct rtentry *r;

    int routes_changed_before;

    /*

     * Remember the state of the global routes_changed flag before

     * generating the reports, and clear the flag.

     */

	}

    }

    /*

     * If there were changed routes before we sent the reports AND

     * if no new changes occurred while sending the reports, clear

     * the change flags in the individual route entries.  If changes

     * did occur while sending the reports, new reports will be

     * generated at the next timer interrupt.

     */

	}

    }

    /*

     * Set a flag to inhibit further reports of changed routes until the

     * next timer interrupt.  This is to alleviate update storms.

     */

}

/*

 * Send a route report message to destination 'dst', via virtual interface

 * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.

 */

static int

report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst)

{

    struct rtentry *r;

    char *p;

    int i;

    int nrt = 0;

    int datalen = 0;

    int width = 0;

    u_int32_t mask = 0;

    u_int32_t src;

    u_int32_t nflags;

#ifdef NOTYET

	/* Don't send poisoned routes back to parents if I am a leaf */

	if ((vifs_with_neighbors == 1) && (r->rt_parent == vifi)

		&& (r->rt_metric > 1)) {

	    ++nrt;

	    continue;

	}

#endif

	/*

	 * If there is no room for this route in the current message,

	 * send it & return how many routes we sent.

	 */