route_table.c

説明を見る。

/*
               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: mad-hoc@flyinglinux.net

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

    }


/*unlock table*/
route_read_unlock();    

    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;
    while ( tmp_precursor!=NULL)
    {
        printk("          -: Precursor -->   %s\n",inet_ntoa(tmp_precursor->ip));
        tmp_precursor=tmp_precursor->next;
    }
}


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

   print_route_table
----------------------------------------------------
Prints out the current routing table to the
console screen
****************************************************/
void print_route_table()
{
    struct route_table_entry *tmp_entry;
    char dst[16];
    char hop[16];

    tmp_entry=route_table;
    printk(KERN_INFO "---------------------------------------------\n");

    while (tmp_entry!=NULL)
    {
        strcpy(hop,inet_ntoa(tmp_entry->next_hop));
        strcpy(dst,inet_ntoa(tmp_entry->dst_ip));
        printk(KERN_INFO "(  Dst: %s Dst Seq: %d  Hop Count: %d Next Hop: %s  )\n",dst ,tmp_entry->dst_seq,tmp_entry->hop_count,hop);
        print_precursors(tmp_entry);
        tmp_entry=tmp_entry->next;
        // printk("printed one entry\n");
    }
    printk(KERN_INFO "---------------------------------------------\n");

}




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

   cleanup_route_table
----------------------------------------------------
Erases everything in the routing table and the
kernel routing table
****************************************************/
int  cleanup_route_table(void)
{

    struct route_table_entry *tmp_entry, *dead_entry;

    int count=0;

    tmp_entry=route_table;


    print_route_table();


    while(tmp_entry!=NULL)
    {

        if(delete_kernel_route_entry(tmp_entry->dst_ip, tmp_entry->next_hop) != 0)
          printk(KERN_WARNING "AODV: Error removing Kernel route to: %s\n",inet_ntoa((__u32) tmp_entry->dst_ip));


        delete_precursors_from_route_table_entry(tmp_entry);
        dead_entry=tmp_entry;
        tmp_entry=tmp_entry->next;
        kfree(dead_entry);

        count++;
    }

    route_table=NULL;
    return 0;
}





/*
 * add_precursor
 *
 * Description:
 *   Allocates memory for a new precursor and inserts it in
 *   the precursor list for the destination given by the argument.
 *
 * Arguments:
 *   struct artentry *tmp_artentry - Routing table entry for the destination
 *   u_intr32_t tmp_ip - IP address for the precursor to insert
 *
 * Returns:
 *   int - 0 if precursor is successfully created
 *        -1 otherwise.
 */
/****************************************************

   insert_precursor_entry
----------------------------------------------------
Allocates and adds a precursor to a route
entry
****************************************************/
int insert_precursor_entry(struct route_table_entry *tmp_entry, u_int32_t tmp_ip)
{
    struct precursor_entry *tmp_precursor;


    if(find_precursor_entry(tmp_entry, tmp_ip) == NULL)
    {
        if((tmp_precursor = kmalloc(sizeof(struct precursor_entry),GFP_ATOMIC)) == NULL)
        {

            printk(KERN_WARNING "AODV: Error adding precusrosr\n");


            return -ENOMEM;
        }
        
        tmp_precursor->next = tmp_entry->precursors;
        tmp_precursor->prev = NULL;
        tmp_precursor->ip = tmp_ip;
        if (tmp_entry->precursors!=NULL)
            tmp_entry->precursors->prev = tmp_precursor;
        tmp_entry->precursors=tmp_precursor;
        return 0;
    }

    return -EINVAL;
}


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

   delete_precursor
----------------------------------------------------
Deletes a precurs from a route entries list of
precursors
****************************************************/
void delete_precursor_entry(struct route_table_entry *tmp_entry, u_int32_t tmp_ip)
{
    struct precursor_entry *tmp_precursor;

    if((tmp_precursor = find_precursor_entry(tmp_entry, tmp_ip)) != NULL)
    {
        if (tmp_precursor->prev!=NULL)
            tmp_precursor->prev->next = tmp_precursor->next;
        if (tmp_precursor->next!=NULL)
            tmp_precursor->next->prev = tmp_precursor->prev;
        if (tmp_entry->precursors == tmp_precursor)
            tmp_entry->precursors=tmp_precursor->next;
        kfree(tmp_precursor);
    }
}


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

   delete_precursor_entry_from_route_table
----------------------------------------------------
Removes a precursor from all route table entries
****************************************************/
void delete_precursor_entry_from_route_table(u_int32_t tmp_ip)
{
    struct route_table_entry *tmp_entry;
    
    /*lock table*/
    route_read_lock();    
    
    tmp_entry=route_table;

    while (tmp_entry!=NULL)
    {

        delete_precursor_entry(tmp_entry, tmp_ip);
        tmp_entry=tmp_entry->next;
    }

    /*unlock table*/
    route_read_unlock();    
}



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

   find_precursor_entry
----------------------------------------------------
Will find a precursor entry in a route table
entries list of precursors
****************************************************/
struct precursor_entry* find_precursor_entry(struct route_table_entry *tmp_entry, u_int32_t tmp_ip)
{
    struct precursor_entry *tmp_precursor;

    tmp_precursor=tmp_entry->precursors;
    while (tmp_precursor!=NULL)
    {
        if(tmp_precursor->ip == tmp_ip)
            return tmp_precursor;
        tmp_precursor=tmp_precursor->next;
    }
    return NULL;
}




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

   update_reverse_route_entry
----------------------------------------------------
Will create or update a reverse route to node
****************************************************/
int update_route_entry(u_int32_t ip, u_int32_t next_hop_ip, u_int8_t hop_count, u_int32_t seq, struct net_device *dev)
{
    struct route_table_entry  *tmp_entry;
    u_int64_t        curr_time;

    /*lock table*/


    tmp_entry = find_route_table_entry(ip); /* Get entry from RT if there is one */
    if ((tmp_entry == NULL) || (!tmp_entry->route_valid) ||
            (!tmp_entry->route_seq_valid) ||
            (seq_greater( seq , tmp_entry->dst_seq)) ||
            ((seq == tmp_entry->dst_seq) &&
             (hop_count < tmp_entry->hop_count)))
    {

        /* If there didn't exist an entry in RT to the source, create it */
        if (tmp_entry == NULL)
        {


          /*unlock table*/

          tmp_entry = create_route_table_entry();
          /*lock table*/
          if (tmp_entry==NULL) // Thanks to M. Musuvathi for catching this!
            return -ENOMEM;

          tmp_entry->dst_ip = ip;

        }
        else //Since the entry existed we might want to change krt
        {
            delete_kernel_route_entry(tmp_entry->dst_ip, tmp_entry->next_hop);
        }

        if (tmp_entry->self_route)
          {
            printk("updating a SELF-ROUTE!!! %s hopcount %d\n",inet_ntoa(next_hop_ip),hop_count);
            if   (!tmp_entry->route_valid) 
              printk("because route was invalid!\n");
            
            if (!tmp_entry->route_seq_valid) 
              printk("because seq was invalid!\n");
            
            if (seq_greater( seq , tmp_entry->dst_seq))
              printk("because seq of route was lower!\n");
            if ((seq == tmp_entry->dst_seq) && (hop_count < tmp_entry->hop_count))
              printk("becase seq same but hop lower!\n");
          }
        /* Update values in the RT entry */
        tmp_entry->dst_seq = seq;
        tmp_entry->next_hop = next_hop_ip;
        tmp_entry->hop_count = hop_count;
        tmp_entry->dev= dev;
        tmp_entry->route_valid=TRUE;
        insert_kernel_route_entry(tmp_entry->dst_ip, tmp_entry->next_hop,tmp_entry->dev->name);
        ipq_send_ip(ip);
    }

    curr_time = getcurrtime(); /* Get current time */
    /* Check if the lifetime in RT is valid, if not update it */

    tmp_entry->lifetime = curr_time+ACTIVE_ROUTE_TIMEOUT;


    return 0;
}



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

   delete_precursors_from_route_table_entry
----------------------------------------------------
Removes all of a route table entries precurosrs
****************************************************/
void delete_precursors_from_route_table_entry(struct route_table_entry *tmp_entry)
{
    struct precursor_entry *tmp_precursor;
    struct precursor_entry *dead_precursor;

    tmp_precursor=tmp_entry->precursors;

    while (tmp_precursor!=NULL)
    {

        dead_precursor=tmp_precursor;
        tmp_precursor=tmp_precursor->next;
        kfree(dead_precursor);
    }
    tmp_entry->precursors=NULL;
}


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

   create_kernel_route_entry
----------------------------------------------------
Creates a Kernel Routing table entry
****************************************************/
struct rtentry *create_kernel_route_entry(u_int32_t dst_ip, u_int32_t gw_ip,char *interf)
{
    struct rtentry *new_rtentry;
    struct sockaddr_in dst;
    struct sockaddr_in gw;
    struct sockaddr_in genmask;

    if((new_rtentry = kmalloc(sizeof(struct rtentry),GFP_ATOMIC)) == NULL)
    {
#ifndef NO_ERROR
        printk("KRTABLE: Gen- Error generating a route entry\n");
#endif

        return NULL; /* Malloc failed */
    }

    dst.sin_family = AF_INET;
    gw.sin_family = AF_INET;
    genmask.sin_family = AF_INET;

    dst.sin_addr.s_addr = dst_ip;
    gw.sin_addr.s_addr = gw_ip;
    genmask.sin_addr.s_addr=g_broadcast_ip;
    new_rtentry->rt_flags = RTF_UP | RTF_HOST | RTF_GATEWAY;

    new_rtentry->rt_metric = 0;
    //new_rtentry->rt_dev = NULL;
    new_rtentry->rt_dev = interf;
    new_rtentry->rt_dst = *(struct sockaddr *) &dst;
    new_rtentry->rt_gateway = *(struct sockaddr*) &gw;
    new_rtentry->rt_genmask = *(struct sockaddr*) &genmask;

    return new_rtentry;
}






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

   insert_kernel_route_entry
----------------------------------------------------
Creates an entry in the kernel routing table
****************************************************/
int insert_kernel_route_entry(u_int32_t dst_ip, u_int32_t gw_ip,char *interf)
{
    struct rtentry  *new_krtentry;
    mm_segment_t oldfs;
    int error;
#ifdef TRACE

    char dst[16];
    char gw[16];
#endif

    if ((new_krtentry = create_kernel_route_entry(dst_ip, gw_ip,interf)) == NULL)
    {
        #ifndef NO_ERROR
        printk("trouble creating route table entry!\n");
        #endif
        return -1;
    }


    oldfs = get_fs();
    set_fs(get_ds());
    error=ip_rt_ioctl(SIOCADDRT, (char*) new_krtentry);

#ifdef TRACE
    strcpy(dst,inet_ntoa(dst_ip));
    strcpy(gw,inet_ntoa(gw_ip));
    printk("ADD_KROUTE: Added kroute to: %s thru: %s  \n",dst,gw);

#endif

    set_fs(oldfs);

    kfree(new_krtentry);

    return 0;
}



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

   delete_kernel_route_entry
----------------------------------------------------
Removes a entry from the Kernel routing table
****************************************************/
int delete_kernel_route_entry(u_int32_t dst_ip, u_int32_t gw_ip)
{
    struct rtentry  *new_krtentry;
    mm_segment_t oldfs;
#ifdef TRACE

    char dst[16];
    char gw[16];
#endif

    if ((new_krtentry = create_kernel_route_entry(dst_ip, gw_ip,NULL)) == NULL)
        // del_kroute failed
        return 1;

    oldfs = get_fs();
    set_fs(KERNEL_DS);

    //For Kernel programming you have to use ip_rt_ioctl to insert routes
    if(ip_rt_ioctl(SIOCDELRT, (char*) new_krtentry) == -1)
    {
#ifndef NO_ERROR
        printk("DEL_KRTENTRY: Danger Will Robinson!\n");
#endif

        set_fs(oldfs);

        //SIOCDELRT failed
        return 1;
    }
#ifdef TRACE
    strcpy(dst,inet_ntoa(dst_ip));
    strcpy(gw,inet_ntoa(gw_ip));
    printk("DEL_KROUTE: Deleted kroute to: %s thru: %s  \n",dst,gw);

#endif

    set_fs(oldfs);

    kfree(new_krtentry);

    return 0;
}

---