routing_table.c

路有算法aodv的linux下的版本

/*****************************************************************************
 *
 * Copyright (C) 2001 Uppsala University and Ericsson AB.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Authors: Erik Nordstr鰉, <[e-mail]>
 *
 *****************************************************************************/

#include <time.h>

#ifdef NS_PORT
#include "ns/aodv-uu.h"
#else
#include "routing_table.h"
#include "aodv_timeout.h"
#include "aodv_rerr.h"
#include "aodv_hello.h"
#include "aodv_socket.h"
#include "k_route.h"
#include "timer_queue.h"
#include "defs.h"
#include "debug.h"
#include "params.h"
#include "seek_list.h"
#include "nl.h"
#endif				/* NS_PORT */

static unsigned int hashing(struct in_addr *addr, hash_value *hash);

extern int llfeedback;

void NS_CLASS rt_table_init()
{
    int i;

    rt_tbl.num_entries = 0;
    rt_tbl.num_active = 0;

    /* We do a for loop here... NS does not like us to use memset() */
    for (i = 0; i < RT_TABLESIZE; i++) {
	INIT_LIST_HEAD(&rt_tbl.tbl[i]);
    }
}

void NS_CLASS rt_table_destroy()
{
    int i;
    list_t *tmp = NULL, *pos = NULL;

    for (i = 0; i < RT_TABLESIZE; i++) {
	list_foreach_safe(pos, tmp, &rt_tbl.tbl[i]) {
	    rt_table_t *rt = (rt_table_t *)pos;
	    
	    rt_table_delete(rt);
	}
    }
}

/* Calculate a hash value and table index given a key... */
unsigned int hashing(struct in_addr * addr, hash_value * hash)
{
    /*   *hash = (*addr & 0x7fffffff); */
    *hash = (hash_value)addr->s_addr;

    return (*hash & RT_TABLEMASK);
}

rt_table_t *NS_CLASS rt_table_insert(struct in_addr dest_addr, 
				     struct in_addr next,
				     u_int8_t hops, u_int32_t seqno,
				     u_int32_t life, u_int8_t state,
				     u_int16_t flags, unsigned int ifindex)
{
    hash_value hash;
    unsigned int index;
    list_t *pos;
    rt_table_t *rt;
    struct in_addr nm;
    nm.s_addr = 0;
    
    /* Calculate hash key */
    index = hashing(&dest_addr, &hash);

    /* Check if we already have an entry for dest_addr */
    list_foreach(pos, &rt_tbl.tbl[index]) {
	rt = (rt_table_t *)pos;
	if (memcmp(&rt->dest_addr, &dest_addr, sizeof(struct in_addr)) == 0) {
	    DEBUG(LOG_INFO, 0, "%s already exist in routing table!", 
		  ip_to_str(dest_addr));

	    return NULL;
	}
    }

    if ((rt = (rt_table_t *) malloc(sizeof(rt_table_t))) == NULL) {
	fprintf(stderr, "Malloc failed!\n");
	exit(-1);
    }
    
    memset(rt, 0, sizeof(rt_table_t));

    rt->dest_addr = dest_addr;
    rt->next_hop = next;
    rt->dest_seqno = seqno;
    rt->flags = flags;
    rt->hcnt = hops;
    rt->ifindex = ifindex;
    rt->hash = hash;
    rt->state = state;

    timer_init(&rt->rt_timer, &NS_CLASS route_expire_timeout, rt);

    timer_init(&rt->ack_timer, &NS_CLASS rrep_ack_timeout, rt);

    timer_init(&rt->hello_timer, &NS_CLASS hello_timeout, rt);

    rt->last_hello_time.tv_sec = 0;
    rt->last_hello_time.tv_usec = 0;
    rt->hello_cnt = 0;

    rt->nprec = 0;
    INIT_LIST_HEAD(&rt->precursors);

    /* Insert first in bucket... */
    
    rt_tbl.num_entries++;
    
    DEBUG(LOG_INFO, 0, "Inserting %s (bucket %d) next hop %s",
	  ip_to_str(dest_addr), index, ip_to_str(next));

    list_add(&rt_tbl.tbl[index], &rt->l);
    
    if (state == INVALID) {

	if (flags & RT_REPAIR) {
	    rt->rt_timer.handler = &NS_CLASS local_repair_timeout;
	    life = ACTIVE_ROUTE_TIMEOUT;
	} else {
	    rt->rt_timer.handler = &NS_CLASS route_delete_timeout;
	    life = DELETE_PERIOD;
	}

    } else {
	rt_tbl.num_active++;
#ifndef NS_PORT
	/* Add route to kernel routing table ... */
	if (k_add_rte(dest_addr, next, nm, hops, rt->ifindex) < 0)
	    alog(LOG_WARNING, errno, __FUNCTION__,
		"Could not add kernel route!");
	nl_send_add_route_msg(dest_addr, next, life, flags);
#endif
    }

#ifdef CONFIG_GATEWAY_DISABLE
    if (rt->flags & RT_GATEWAY)
	rt_table_update_inet_rt(rt, life);
#endif

//#ifdef NS_PORT
    DEBUG(LOG_INFO, 0, "New timer for %s, life=%d",
	  ip_to_str(rt->dest_addr), life);

    if (life != 0)
	timer_set_timeout(&rt->rt_timer, life);
//#endif
    /* In case there are buffered packets for this destination, we
     * send them on the new route. */
    if (rt->state == VALID && seek_list_remove(seek_list_find(dest_addr))) {
#ifdef NS_PORT
	if (rt->flags & RT_INET_DEST)
            packet_queue_set_verdict(dest_addr, PQ_ENC_SEND);
        else
            packet_queue_set_verdict(dest_addr, PQ_SEND);
#endif
    }
    return rt;
}

rt_table_t *NS_CLASS rt_table_update(rt_table_t * rt, struct in_addr next,
				     u_int8_t hops, u_int32_t seqno,
				     u_int32_t lifetime, u_int8_t state,
				     u_int16_t flags)
{
    struct in_addr nm;
    nm.s_addr = 0;

    if (rt->state == INVALID && state == VALID) {

	/* If this previously was an expired route, but will now be
	   active again we must add it to the kernel routing
	   table... */
	rt_tbl.num_active++;
	
	if (rt->flags & RT_REPAIR)
	    flags &= ~RT_REPAIR;
	
#ifndef NS_PORT
	if (k_add_rte(rt->dest_addr, next, nm, hops, rt->ifindex) < 0)
	    alog(LOG_WARNING, errno, __FUNCTION__,
		"Could not add kernel route!");
	else
	    DEBUG(LOG_INFO, 0, "Added kernel route for expired %s",
		  ip_to_str(rt->dest_addr));
	
	nl_send_add_route_msg(rt->dest_addr, next, lifetime, flags);
#endif

    } else if (rt->next_hop.s_addr != 0 && 
	       rt->next_hop.s_addr != next.s_addr) {
	DEBUG(LOG_INFO, 0, "rt->next_hop=%s, new_next_hop=%s",
	      ip_to_str(rt->next_hop), ip_to_str(next));

#ifndef NS_PORT
	if (k_chg_rte(rt->dest_addr, next, nm, hops, rt->ifindex) < 0)
	    alog(LOG_WARNING, errno, __FUNCTION__,
		"Could not update kernel route!");

	nl_send_add_route_msg(rt->dest_addr, next, lifetime, flags);
#endif
    }

    rt->flags = flags;
    rt->dest_seqno = seqno;
    rt->next_hop = next;

    if (hops > 1 && rt->hcnt == 1) {
	rt->last_hello_time.tv_sec = 0;
	rt->last_hello_time.tv_usec = 0;
	rt->hello_cnt = 0;
	timer_remove(&rt->hello_timer);
    }

    rt->hcnt = hops;
    
#ifdef CONFIG_GATEWAY
    if (rt->flags & RT_GATEWAY)
	rt_table_update_inet_rt(rt, lifetime);
#endif

//#ifdef NS_PORT
    rt->rt_timer.handler = &NS_CLASS route_expire_timeout;

    if (!(rt->flags & RT_INET_DEST))
	rt_table_update_timeout(rt, lifetime);
//#endif
    
    /* Finally, mark as VALID */
    rt->state = state;

    /* In case there are buffered packets for this destination, we send
     * them on the new route. */
    if (rt->state == VALID && seek_list_remove(seek_list_find(rt->dest_addr))) {
#ifdef NS_PORT
	if (rt->flags & RT_INET_DEST)
            packet_queue_set_verdict(rt->dest_addr, PQ_ENC_SEND);
        else
            packet_queue_set_verdict(rt->dest_addr, PQ_SEND);
#endif
    }
    return rt;
}

NS_INLINE rt_table_t *NS_CLASS rt_table_update_timeout(rt_table_t * rt,
						       u_int32_t lifetime)
{
    struct timeval new_timeout;

    if (!rt)
	return NULL;

    if (rt->state == VALID) {
	/* Check if the current valid timeout is larger than the new
	   one - in that case keep the old one. */
	gettimeofday(&new_timeout, NULL);
	timeval_add_msec(&new_timeout, lifetime);

	if (timeval_diff(&rt->rt_timer.timeout, &new_timeout) < 0)
	    timer_set_timeout(&rt->rt_timer, lifetime);
    } else
	timer_set_timeout(&rt->rt_timer, lifetime);

    return rt;
}

/* Update route timeouts in response to an incoming or outgoing data packet. */
void NS_CLASS rt_table_update_route_timeouts(rt_table_t *fwd_rt, 
					     rt_table_t *rev_rt)
{
    rt_table_t *next_hop_rt = NULL;
    
    /* When forwarding a packet, we update the lifetime of the
       destination's routing table entry, as well as the entry for the
       next hop neighbor (if not the same). AODV draft 10, section
       6.2. */
   
    if (fwd_rt && fwd_rt->state == VALID) {
	
	if (llfeedback || fwd_rt->hcnt != 1 || fwd_rt->hello_timer.used)
	    rt_table_update_timeout(fwd_rt, ACTIVE_ROUTE_TIMEOUT);
	    
	next_hop_rt = rt_table_find(fwd_rt->next_hop);
	
	if (next_hop_rt && next_hop_rt->state == VALID && 
	    next_hop_rt->dest_addr.s_addr != fwd_rt->dest_addr.s_addr &&
	    (llfeedback || fwd_rt->hello_timer.used))