route_table.c

一种AODV实现方法

/*
               Kernel AODV  v2.0
National Institute of Standards and Technology
               Luke Klein-Berndt
-----------------------------------------------------
  Version 2.0 new features:
     * Updated to AODV draft version 11
     * Managed internet gatewaying
     * Monitor wireles signal strength
     * 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;


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

/*
 * 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;
    tmp_route=route_table;
#ifdef TRACE
    printk ("Finding inactive route table stuff\n");
#endif
    curr_time=getcurrtime();
    while(tmp_route!=NULL)
    {
#ifdef TRACE
        printk("working with route %s   %ul    %ul  \n",inet_ntoa(tmp_route->dst_ip),tmp_route->lifetime,getcurrtime());
#endif

        if(tmp_route->lifetime < curr_time)
        {

            if(tmp_route->route_valid==FALSE)
            {
#ifdef MESSAGES
                printk("ROUTE_TABLE: Route: %s has expired and will be deleted from the Route Table\n",inet_ntoa(tmp_route->dst_ip));
#endif
                /* step back before deletion */
                dead_route=tmp_route;

                tmp_route=tmp_route->next;
                delete_kernel_route_entry(dead_route->dst_ip,dead_route->next_hop);


                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)
                    {
                        /* break also performs route_expiry */
                        link_break(tmp_route->dst_ip);
                    }
                    else
                    {
#ifdef MESSAGES
                        printk("ROUTE_TABLE: Route Table Entry: %s is inactive  and will be marked as expired!!\n",inet_ntoa(tmp_route->dst_ip));
#endif
                        route_expiry(tmp_route);
                    }
                }
                tmp_route=tmp_route->next;
            }
        }
        else
            tmp_route=tmp_route->next;


    }
#ifdef TRACE
    printk("all done finding inactives");
#endif
}


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

   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)
    {
#ifndef NO_ERROR
        printk("Route_Table: Error Getting memory for inserting new rtentry\n");
#endif

        return NULL;
    }

    tmp_entry->precursors=NULL;
    tmp_entry->self_route=0;
    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;
    if (route_table!=NULL)
        route_table->prev = tmp_entry;
    tmp_entry->next = route_table;
    route_table=tmp_entry;

    return tmp_entry;
}


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

   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;

    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;
}


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

   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 1;

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

    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;

    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];
    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 %d\n",dst ,hop,tmp_entry->hop_count,tmp_entry->link);
            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 %d\n",dst ,hop,tmp_entry->hop_count,tmp_entry->link);
            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 %d\n",dst ,hop,tmp_entry->hop_count,tmp_entry->link);
            strcat(my_buffer,temp_buffer);

        }
        tmp_entry=tmp_entry->next;
    }

    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[20];
    struct route_table_entry *tmp_entry;
    struct precursor_entry  *tmp_precursor;

    int len,i;

    char dst[16];
    char hop[16];
    tmp_entry=route_table;

    my_buffer=buffer;


    sprintf(my_buffer,"\nRoute Table \n---------------------------------------------------------------------------------\n");
    sprintf(temp_buffer,"        IP        |       Seq    |   Hop Count  |     Next Hop    |    Link\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->link<255)
        {
            sprintf(temp_buffer,"(  %d ) ",tmp_entry->link);
            strcat(my_buffer,temp_buffer);
            strcpy(temp,"[");
            for (i=1;i<(tmp_entry->link/10);i++)
            {
                strcat(temp,"|");
            }
            for (;i<10;i++)
            {
                strcat(temp,"-");
            }
            strcat(temp,"] \n");

        }
        else
            strcpy(temp," N/A \n");
        strcat(my_buffer,temp);
        tmp_precursor=tmp_entry->precursors;

	#ifndef ARM
        while ( tmp_precursor!=NULL)
        {
            sprintf(temp_buffer,"\t\t-: Precursor -->   %s\n",inet_ntoa(tmp_precursor->ip));
            strcat(my_buffer,temp_buffer);
            tmp_precursor=tmp_precursor->next;
        }
	  #endif
        tmp_entry=tmp_entry->next;
    }

    strcat(my_buffer,"---------------------------------------------------------------------------------\n\n");

    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;
}



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

   print_precursors
----------------------------------------------------
It will print the precursors for a route table
entry
****************************************************/
void print_precursors(struct route_table_entry *tmp_entry)
{
    struct precursor_entry  *tmp_precursor;

    tmp_precursor=tmp_entry->precursors;