route_table.c

linux 下的aodv实现源代码

/*
               Kernel AODV  v2.1
National Institute of Standards and Technology
               Luke Klein-Berndt
-----------------------------------------------------
  Version 2.1 new features:
     * Much more stable!
     * Added locks around important areas
     * Multihop Internet gatewaying now works
     * Multicast hack added
     * Many bug fixes!
-----------------------------------------------------

Originally based upon MadHoc code. I am not
sure how much of it is left anymore, but MadHoc
proved to be a great starting point.

MadHoc was written by - Fredrik Lilieblad,
Oskar Mattsson, Petra Nylund, Dan Ouchterlony
and Anders Roxenhag Mail: [e-mail]

This software is Open Source under the GNU General Public Licence.

*/

#include "route_table.h"
/****************************************************

   route_table
----------------------------------------------------
A table which contains all the needed routing
information to contact other nodes
****************************************************/

extern u_int32_t g_broadcast_ip;
extern struct route_table_entry *g_my_entry;
struct route_table_entry *route_table;
rwlock_t route_lock = RW_LOCK_UNLOCKED;

/* Declaration of internal procedures */
struct precursor_entry *find_precursor_entry(struct route_table_entry* tmp_entry, u_int32_t tmp_ip);

void route_read_lock()
{
  read_lock_bh(&route_lock);
}

void route_read_unlock()
{
  read_unlock_bh(&route_lock);
}

void route_write_lock()
{
  write_lock_bh(&route_lock);
}

void route_write_unlock()
{
  write_unlock_bh(&route_lock);
}



/*
 * init_rt
 *
 * Description:
 *   Initializes the main routing table by creating a
 *   head for the list.
 *
 * Arguments: void
 *
 * Return: void
 */

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

   init_route_table
----------------------------------------------------
Initalizes the route table so it can hold data
****************************************************/
int init_route_table( void)
{
    route_table=NULL;
    return 0;
}


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

   get_first_route_table_entry
----------------------------------------------------
Returns the first entry in the routing table
****************************************************/
struct route_table_entry *get_first_route_table_entry()
{
    return route_table;
}




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

   find_inactive_route_table_entries
----------------------------------------------------
Finds expired route table entries and deletes
them
****************************************************/
void find_inactive_route_table_entries()
{
    struct route_table_entry *tmp_route;
    struct route_table_entry *dead_route;
    u_int64_t curr_time;

    curr_time=getcurrtime();


    /*lock table*/
    route_write_lock();

    tmp_route=route_table;



    while(tmp_route!=NULL)
    {
        if ((tmp_route->lifetime < curr_time) && !tmp_route->self_route)
        {

            if(tmp_route->route_valid==FALSE)
            {

                printk(KERN_INFO "ROUTE_TABLE: Route: %s has expired and will be deleted from the Route Table\n",inet_ntoa(tmp_route->dst_ip));



		/* step back before deletion */
                dead_route=tmp_route;

		tmp_route=tmp_route->next;

                if (route_table==dead_route)
                    route_table=dead_route->next;

                if (dead_route->prev!=NULL)
                    dead_route->prev->next = dead_route->next;


                if (dead_route->next!=NULL)
                    dead_route->next->prev = dead_route->prev;

                delete_precursors_from_route_table_entry(dead_route);
                kfree(dead_route);
            }
            else
	      {
                if(tmp_route->self_route==0)
		  {
                    if(tmp_route->next_hop == tmp_route->dst_ip)
		      {
			route_write_unlock();
			/* break also performs route_expiry */
			link_break(tmp_route->dst_ip);
			route_write_lock();

		      }
                    else
		      {

                        printk(KERN_INFO "AODV: Route Table Entry: %s is inactive  and will be marked as expired!!\n",inet_ntoa(tmp_route->dst_ip));
			route_write_unlock();
                        route_expiry(tmp_route);
			route_write_lock();
                    }
                }
		
                tmp_route=tmp_route->next;
		

            }
        }
        else
	  {

            tmp_route=tmp_route->next;
	    

	  }

    }

    route_write_unlock();


}


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

   create_route_table_entry
----------------------------------------------------
Allocates memory for a new route table entry,
places that entry into the linked list and then
returns a pointer for that entry
****************************************************/
struct route_table_entry *create_route_table_entry()
{
    struct route_table_entry *tmp_entry;

    /* Allocate memory for new entry */

    if((tmp_entry = (struct route_table_entry*)kmalloc(sizeof(struct route_table_entry),GFP_ATOMIC)) == NULL)
    {

        printk(KERN_WARNING "AODV: Error getting memory for inserting new rtentry\n");


        return NULL;
    }


    tmp_entry->precursors=NULL;
    tmp_entry->self_route=FALSE;
    tmp_entry->rreq_id=0;
    tmp_entry->link=255;
    tmp_entry->dev=NULL;
    tmp_entry->route_valid=FALSE;
    tmp_entry->route_seq_valid=FALSE;
    tmp_entry->prev = NULL;
  
    /*lock table*/
    route_write_lock();

    
    if (route_table!=NULL)
        route_table->prev = tmp_entry;
    tmp_entry->next = route_table;
    route_table=tmp_entry;

    /*unlock table*/
    route_write_unlock();


    return tmp_entry;
}


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

   find_route_table_entry
----------------------------------------------------
Returns a pointer to a route table entry which
matches the ip address
****************************************************/
struct route_table_entry *fast_find_route_table_entry(u_int32_t tmp_ip)
{
    struct route_table_entry *tmp_entry;

    tmp_entry=route_table;

    while(tmp_entry!=NULL)
    {
        if(tmp_entry->dst_ip == tmp_ip)
        {

          return tmp_entry;
        }
	
        tmp_entry=tmp_entry->next;
    }


    return NULL;
}

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

   find_route_table_entry
----------------------------------------------------
Returns a pointer to a route table entry which
matches the ip address
****************************************************/
struct route_table_entry *find_route_table_entry(u_int32_t tmp_ip)
{
    struct route_table_entry *tmp_entry;

    /*lock table*/
    route_read_lock();

    tmp_entry=route_table;

    while(tmp_entry!=NULL)
    {
        if(tmp_entry->dst_ip == tmp_ip)
        {
	  /*unlock table*/
	  route_read_unlock();

          return tmp_entry;
        }
	
        tmp_entry=tmp_entry->next;
    }

    /*unlock table*/
    route_read_unlock();

    return NULL;
}



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

   delete_route_table_entry
----------------------------------------------------
Deletes a route table entry which matches the
ip address
****************************************************/
int delete_route_table_entry(u_int32_t tmp_ip)
{
    struct route_table_entry *tmp_entry;

    if ((tmp_entry=find_route_table_entry(tmp_ip))==NULL)
        return -ENOENT;

    delete_kernel_route_entry(tmp_entry->dst_ip,tmp_entry->next_hop);

    /*lock table*/
    route_write_lock();    

    if (route_table==tmp_entry)
        route_table=tmp_entry->next;


    if (tmp_entry->prev!=NULL)
        tmp_entry->prev->next = tmp_entry->next;

    if (tmp_entry->next!=NULL)
        tmp_entry->next->prev = tmp_entry->prev;

    /*unlock table*/
    route_write_unlock();    

    delete_precursors_from_route_table_entry(tmp_entry);
    kfree(tmp_entry);
    return 0;
}


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

   read_monitor_proc
----------------------------------------------------
Prints out the route table to a buffer. It is called
when the related proc file is read
****************************************************/
int read_monitor_proc(char *buffer, char **buffer_location, off_t offset, int buffer_length,int *eof,void *data)
{
    static char *my_buffer;
    char temp_buffer[80];
    struct route_table_entry *tmp_entry;
    int len;

    char dst[16];
    char hop[16];

    /*lock table*/
    route_read_lock();    


    tmp_entry=route_table;

    my_buffer=buffer;


    sprintf(my_buffer,"\n");
    tmp_entry=route_table;
    while (tmp_entry!=NULL)
    {
        if (tmp_entry->hop_count==0)
        {
            strcpy(hop,inet_ntoa(tmp_entry->next_hop));
            strcpy(dst,inet_ntoa(tmp_entry->dst_ip));
            sprintf(temp_buffer,"%s %s %d \n",dst ,hop,tmp_entry->hop_count);
            strcat(my_buffer,temp_buffer);
        }
        tmp_entry=tmp_entry->next;
    }
    tmp_entry=route_table;
    while (tmp_entry!=NULL)
    {
        if (tmp_entry->hop_count==1)
        {
            strcpy(hop,inet_ntoa(tmp_entry->next_hop));
            strcpy(dst,inet_ntoa(tmp_entry->dst_ip));
            sprintf(temp_buffer,"%s %s %d \n",dst ,hop,tmp_entry->hop_count);
            strcat(my_buffer,temp_buffer);

        }
        tmp_entry=tmp_entry->next;
    }
    tmp_entry=route_table;
    while (tmp_entry!=NULL)
    {
        if (tmp_entry->hop_count>1)
        {
            strcpy(hop,inet_ntoa(tmp_entry->next_hop));
            strcpy(dst,inet_ntoa(tmp_entry->dst_ip));
            sprintf(temp_buffer,"%s %s %d \n",dst ,hop,tmp_entry->hop_count);
            strcat(my_buffer,temp_buffer);

        }
        tmp_entry=tmp_entry->next;
    }

    /*unlock table*/
    route_read_unlock();    


    len = strlen(my_buffer);
    *buffer_location = my_buffer + offset;
    len -= offset;
    if (len > buffer_length)
        len = buffer_length;
    else if (len < 0)
        len = 0;
    return len;
}
/****************************************************

   read_route_table_proc
----------------------------------------------------
Prints out the route table to a buffer. It is called
when the related proc file is read
****************************************************/
int read_route_table_proc(char *buffer, char **buffer_location, off_t offset, int buffer_length,int *eof,void *data)
{

    static char *my_buffer;
    char temp_buffer[200];
    char temp[40];
    struct route_table_entry *tmp_entry;
    struct precursor_entry  *tmp_precursor;
    u_int64_t remainder, numerator;
    u_int64_t tmp_time;
    int len,i;
    u_int64_t currtime;
    char dst[16];
    char hop[16];

    currtime=getcurrtime();

    /*lock table*/
    route_read_lock();    


    tmp_entry=route_table;

    my_buffer=buffer;


    sprintf(my_buffer,"\nRoute Table \n---------------------------------------------------------------------------------\n");
    sprintf(temp_buffer,"        IP        |       Seq    |   Hop Count  |     Next Hop\n");
    strcat(my_buffer,temp_buffer);
    sprintf(temp_buffer,"---------------------------------------------------------------------------------\n");
    strcat(my_buffer,temp_buffer);

    while (tmp_entry!=NULL)
    {
        strcpy(hop,inet_ntoa(tmp_entry->next_hop));
        strcpy(dst,inet_ntoa(tmp_entry->dst_ip));
        sprintf(temp_buffer,"  %-16s       %5u          %3d         %-16s   ",dst ,tmp_entry->dst_seq,tmp_entry->hop_count,hop);
        strcat(my_buffer,temp_buffer);
	if (tmp_entry->route_valid)
	  strcat(my_buffer, " Valid ");
	
	tmp_time=tmp_entry->lifetime-currtime;
	numerator = (tmp_time);
	remainder = do_div( numerator, 1000 );
	
        if (tmp_entry->lifetime < currtime )
	{
	  sprintf(temp," Expired!\n");
	}
	else
	  {
	    sprintf(temp," sec/msec: %lu/%lu %d\n", (unsigned long)numerator, (unsigned long)remainder,tmp_entry->self_route);
	  }
	strcat(my_buffer,temp);


        tmp_precursor=tmp_entry->precursors;

#ifndef ARM