/*               Kernel AODV  v2.1National 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 notsure how much of it is left anymore, but MadHocproved to be a great starting point.MadHoc was written by - Fredrik Lilieblad,Oskar Mattsson, Petra Nylund, Dan Ouchterlonyand Anders Roxenhag Mail: mad-hoc@flyinglinux.netThis software is Open Source under the GNU General Public Licence.*/#include "route_table.h"/****************************************************   route_table----------------------------------------------------A table which contains all the needed routinginformation 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 deletesthem****************************************************/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 thenreturns 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 whichmatches 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 whichmatches 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 theip 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 calledwhen 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 calledwhen 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