routing_table.c

路有算法aodv的linux下的版本

	    rt_table_update_timeout(next_hop_rt, ACTIVE_ROUTE_TIMEOUT);

    }
    /* Also update the reverse route and reverse next hop along the
       path back, since routes between originators and the destination
       are expected to be symmetric. */
    if (rev_rt && rev_rt->state == VALID) {
	
	if (llfeedback || rev_rt->hcnt != 1 || rev_rt->hello_timer.used)
	    rt_table_update_timeout(rev_rt, ACTIVE_ROUTE_TIMEOUT);

	next_hop_rt = rt_table_find(rev_rt->next_hop);

	if (next_hop_rt && next_hop_rt->state == VALID && rev_rt && 
	    next_hop_rt->dest_addr.s_addr != rev_rt->dest_addr.s_addr &&
	    (llfeedback || rev_rt->hello_timer.used))
	    rt_table_update_timeout(next_hop_rt, ACTIVE_ROUTE_TIMEOUT);

	/* Update HELLO timer of next hop neighbor if active */   
/* 	if (!llfeedback && next_hop_rt->hello_timer.used) { */
/* 	    struct timeval now; */
	    
/* 	    gettimeofday(&now, NULL); */
/* 	    hello_update_timeout(next_hop_rt, &now,  */
/* 				 ALLOWED_HELLO_LOSS * HELLO_INTERVAL); */
/* 	} */
    }
}

rt_table_t *NS_CLASS rt_table_find(struct in_addr dest_addr)
{
    hash_value hash;
    unsigned int index;
    list_t *pos;

    if (rt_tbl.num_entries == 0)
	return NULL;

    /* Calculate index */
    index = hashing(&dest_addr, &hash);

    /* Handle collisions: */
    list_foreach(pos, &rt_tbl.tbl[index]) {
	rt_table_t *rt = (rt_table_t *)pos;

	if (rt->hash != hash) 
	    continue;
	
	if (memcmp(&dest_addr, &rt->dest_addr, sizeof(struct in_addr)) == 0)
	    return rt;

    }
    return NULL;
}
rt_table_t *NS_CLASS rt_table_find_gateway()
{
    rt_table_t *gw = NULL;
    int i;

    for (i = 0; i < RT_TABLESIZE; i++) {
	list_t *pos;
	list_foreach(pos, &rt_tbl.tbl[i]) {
	    rt_table_t *rt = (rt_table_t *)pos;
	    
	    if (rt->flags & RT_GATEWAY && rt->state == VALID) {
		if (!gw || rt->hcnt < gw->hcnt)
		    gw = rt;
	    }
	}
    }
    return gw;
}
#ifdef CONFIG_GATEWAY
int NS_CLASS rt_table_update_inet_rt(rt_table_t *gw, u_int32_t life)
{
    int n = 0;
    int i;
    
    if (!gw)
	return -1;

    for (i = 0; i < RT_TABLESIZE; i++) {
	list_t *pos;
	list_foreach(pos, &rt_tbl.tbl[i]) {
	    rt_table_t *rt = (rt_table_t *)pos;
	    
	    if (rt->flags & RT_INET_DEST && rt->state == VALID) {
		rt_table_update(rt, gw->dest_addr, gw->hcnt, 0, life,
				VALID, rt->flags);
		n++;
	    }
	}
    }
    return n;
}
#endif /* CONFIG_GATEWAY_DISABLED */

/* Route expiry and Deletion. */
int NS_CLASS rt_table_invalidate(rt_table_t * rt)
{
    struct timeval now;

    gettimeofday(&now, NULL);

    if (rt == NULL)
	return -1;

     /* If the route is already invalidated, do nothing... */
    if (rt->state == INVALID) {
	DEBUG(LOG_DEBUG, 0, "Route %s already invalidated!!!",
	      ip_to_str(rt->dest_addr));
	return -1;
    }
    
    if (rt->hello_timer.used) {
	DEBUG(LOG_DEBUG, 0, "last HELLO: %ld",
	      timeval_diff(&now, &rt->last_hello_time));
    }
   
    /* Remove any pending, but now obsolete timers. */
    timer_remove(&rt->rt_timer);
    timer_remove(&rt->hello_timer);
    timer_remove(&rt->ack_timer);

    /* Mark the route as invalid */
    rt->state = INVALID;
    rt_tbl.num_active--;

    rt->hello_cnt = 0;

    /* When the lifetime of a route entry expires, increase the sequence
       number for that entry. */
    seqno_incr(rt->dest_seqno);
    
    rt->last_hello_time.tv_sec = 0;
    rt->last_hello_time.tv_usec = 0;

#ifndef NS_PORT
    /* Delete kernel routing table entry. */
    if (k_del_rte(rt->dest_addr) < 0)
	alog(LOG_WARNING, errno, __FUNCTION__, "Could not delete kernel route!");
   /*  if (rt->flags & RT_REPAIR) */
/* 	nl_send_add_route_msg(d, ACTIVE_ROUTE_TIMEOUT); */
/*     else */
    nl_send_del_route_msg(rt->dest_addr);
#endif

    
#ifdef CONFIG_GATEWAY
    /* If this was a gateway, check if any Internet destinations were using
     * it. In that case update them to use a backup gateway or invalide them
     * too. */
    if (rt->flags & RT_GATEWAY) {
	int i;
	
	rt_table_t *gw = rt_table_find_gateway();
	
	for (i = 0; i < RT_TABLESIZE; i++) {
	    list_t *pos;
	    list_foreach(pos, &rt_tbl.tbl[i]) {
		rt_table_t *rt2 = (rt_table_t *)pos;
		
		if (rt2->state == VALID && (rt2->flags & RT_INET_DEST) &&
		    (rt2->next_hop.s_addr == rt->dest_addr.s_addr)) {
		    if (0) {
			DEBUG(LOG_DEBUG, 0, "Invalidated GW %s but found new GW %s for %s",  ip_to_str(rt->dest_addr), ip_to_str(gw->dest_addr),  
			      ip_to_str(rt2->dest_addr));
			rt_table_update(rt2, gw->dest_addr, gw->hcnt, 0, 
					timeval_diff(&rt->rt_timer.timeout, 
						     &now), VALID, rt2->flags);
		    } else {
			rt_table_invalidate(rt2);
			precursor_list_destroy(rt2);
		    }
		}
	    }
	}
    }
#endif

    if (rt->flags & RT_REPAIR) {
	/* Set a timeout for the repair */

	rt->rt_timer.handler = &NS_CLASS local_repair_timeout;
	timer_set_timeout(&rt->rt_timer, ACTIVE_ROUTE_TIMEOUT);

	DEBUG(LOG_DEBUG, 0, "%s kept for repairs during %u msecs",
	      ip_to_str(rt->dest_addr), ACTIVE_ROUTE_TIMEOUT);
    } else {

	/* Schedule a deletion timer */
	rt->rt_timer.handler = &NS_CLASS route_delete_timeout;
	timer_set_timeout(&rt->rt_timer, DELETE_PERIOD);

	DEBUG(LOG_DEBUG, 0, "%s removed in %u msecs",
	      ip_to_str(rt->dest_addr), DELETE_PERIOD);
    }

    return 0;
}

void NS_CLASS rt_table_delete(rt_table_t *rt)
{
    if(!rt) {
	DEBUG(LOG_ERR, 0, "No route entry to delete");
	return;
    }
    
    list_detach(&rt->l);
    
    precursor_list_destroy(rt);
    
    if (rt->state == VALID) {
	
#ifndef NS_PORT
	if (k_del_rte(rt->dest_addr) < 0)
	    alog(LOG_WARNING, errno, __FUNCTION__,
		"Could not delete kernel route!");
	
#endif
	rt_tbl.num_active--;
    }
    /* Make sure timers are removed... */
    timer_remove(&rt->rt_timer);
    timer_remove(&rt->hello_timer);
    timer_remove(&rt->ack_timer);
    
    rt_tbl.num_entries--;
    
    free(rt);
    return;
}

/****************************************************************/

/* Add an neighbor to the active neighbor list. */

void NS_CLASS precursor_add(rt_table_t * rt, struct in_addr addr)
{
    precursor_t *pr;
    list_t *pos;

    /* Sanity check */
    if (!rt)
	return;

    /* Check if the node is already in the precursors list. */
    list_foreach(pos, &rt->precursors) {
	pr = (precursor_t *)pos;
	    
	if (pr->neighbor.s_addr == addr.s_addr)
	    return;
    }
    
    if ((pr = (precursor_t *) malloc(sizeof(precursor_t))) == NULL) {
	perror("Could not allocate memory for precursor node!!\n");
	exit(-1);
    }

    DEBUG(LOG_INFO, 0, "Adding precursor %s to rte %s",
	  ip_to_str(addr), ip_to_str(rt->dest_addr));
    
    pr->neighbor.s_addr = addr.s_addr;
    
    /* Insert in precursors list */
    
    list_add(&rt->precursors, &pr->l);
    rt->nprec++;

    return;
}

/****************************************************************/

/* Remove a neighbor from the active neighbor list. */

void NS_CLASS precursor_remove(rt_table_t * rt, struct in_addr addr)
{
    list_t *pos;

    /* Sanity check */
    if (!rt)
	return;

    list_foreach(pos, &rt->precursors) {
	precursor_t *pr = (precursor_t *)pos;
	if (pr->neighbor.s_addr == addr.s_addr) {
	    DEBUG(LOG_INFO, 0, "Removing precursor %s from rte %s",
		  ip_to_str(addr), ip_to_str(rt->dest_addr));

	    list_detach(pos);
	    rt->nprec--;
	    free(pr);
	    return;
	}
    }
}

/****************************************************************/

/* Delete all entries from the active neighbor list. */

void precursor_list_destroy(rt_table_t * rt)
{
    list_t *pos, *tmp;
    
    /* Sanity check */
    if (!rt)
	return;

    list_foreach_safe(pos, tmp, &rt->precursors) {
	precursor_t *pr = (precursor_t *)pos;
	list_detach(pos);
	rt->nprec--;
	free(pr);
    }
}