timer_queue.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 "timer_queue.h"
/****************************************************

   timer_queue
----------------------------------------------------
A queue of timed events
****************************************************/

struct timer_list aodv_timer;

struct timer_queue_entry *timer_queue=NULL;
extern struct route_table_entry *g_my_entry;
extern u_int32_t g_broadcast_ip;
extern u_int32_t g_my_ip;
rwlock_t timer_lock = RW_LOCK_UNLOCKED;
unsigned long flags;

void timer_read_lock()
{
    read_lock_irqsave(&timer_lock,flags);
}

void timer_read_unlock()
{
   read_unlock_irqrestore(&timer_lock,flags);
}

void timer_write_lock()
{
  write_lock_irqsave(&timer_lock,flags);
}

void timer_write_unlock()
{
  write_unlock_irqrestore(&timer_lock,flags);
}



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

   read_timer_queue_proc
----------------------------------------------------
Prints out the current queue into a buffer when
ever the proc file its read
****************************************************/
int read_timer_queue_proc(char *buffer, char **buffer_location, off_t offset, int buffer_length,int *eof,void *data)
{
    struct timer_queue_entry *tmp;
u_int64_t remainder, numerator;
    u_int64_t tmp_time;
    int len;
    static char *my_buffer;
    char temp_buffer[80];


    /* lock Read */
    timer_read_lock();

    my_buffer=buffer;
    sprintf(my_buffer,"\nTimer Queue\n---------------------------------\n");

    tmp = timer_queue;

    while (tmp != NULL)
    {
        tmp_time=tmp->tv-getcurrtime();

	//This is a fix for an error that occurs on ARM Linux Kernels because they do 64bits differently
	//Thanks to S. Peter Li for coming up with this fix!
	numerator = (tmp_time);
	remainder = do_div( numerator, 1000 );
	sprintf(temp_buffer,"sec/msec: %lu/%lu\t id:%s\t retries: %u\t ttl: %u\t Type: %d\n", (unsigned long)numerator, (unsigned long)remainder, inet_ntoa(tmp->id), tmp->retries, tmp->ttl,tmp->flags);

	strcat(my_buffer,temp_buffer);
        tmp = tmp->next;
    }

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

    /* unlock Read */
    timer_read_unlock();

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



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

   print_timer
----------------------------------------------------
prints the contents of the timer queue to the
console screen
****************************************************/
void print_timer_queue()
{
    struct timer_queue_entry *tmp;
    u_int64_t tmp_time;
	u_int64_t remainder, numerator;


    tmp = timer_queue;

    while (tmp != NULL)
    {
        tmp_time=tmp->tv-getcurrtime();

	//This is a fix for an error that occurs on ARM Linux Kernels because they do 64bits differently
	//Thanks to S. Peter Li for coming up with this fix!

	numerator = tmp_time;
	remainder = do_div( numerator, 1000 );
	printk("sec/msec: %lu/%lu id:%lu size: %d retries: %u ttl: %u\n", (unsigned long)numerator, (unsigned long)remainder, (unsigned long)tmp->id, tmp->size, tmp->retries, tmp->ttl);

        tmp = tmp->next;
    }

}


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

   timer_rreq
----------------------------------------------------
Handles the resending of RREQ if a route
reply is not recieved in a certian amount of time
****************************************************/
int timer_rreq(struct timer_queue_entry *tmp_entry)
{
    struct route_table_entry *tmp_route;
    struct rreq *tmp_rreq;
    u_int32_t rreq_id;

    tmp_rreq=tmp_entry->data;

    /* Check how may time we have sent it already */
    if (tmp_entry->retries >= RREQ_RETRIES)
    {
        /* Sent it maximum times */

        ipq_drop_ip(tmp_rreq->dst_ip);
        kfree(tmp_entry->data);

        /* Return error */
        return 0;
    }
    else
    {
        /* Increment nr of retries */
        tmp_entry->retries++;

        /* Check new TTL */
        if (tmp_entry->ttl > TTL_THRESHOLD)
            tmp_entry->ttl = NET_DIAMETER;
        else
            tmp_entry->ttl += TTL_INCREMENT;


        tmp_route = (find_interface_by_ip(tmp_rreq->src_ip))->route_entry;
  
	(tmp_route->rreq_id)++;



	tmp_rreq->rreq_id = htonl(tmp_route->rreq_id); // byte order problem discovered and fixed by Dinesh/ Manish

        if (insert_flood_id_queue_entry(tmp_rreq->src_ip, tmp_rreq->dst_ip,tmp_route->rreq_id,getcurrtime() + tmp_entry->ttl * 2 * NODE_TRAVERSAL_TIME ) <0)
	  {
	    printk(KERN_WARNING "AODV: Could not insert into broadcast list\n");
	    kfree(tmp_entry->data);

            /* Couldn't add to broadcast list */
            return -ENOMEM;
	  }

        /* Send packet again */
        local_broadcast( tmp_entry->ttl,tmp_rreq, tmp_entry->size);




        insert_timer_queue_entry(getcurrtime() + NET_TRAVERSAL_TIME, tmp_rreq,tmp_entry->size,tmp_rreq->dst_ip,tmp_entry->retries,tmp_entry->ttl, EVENT_RREQ);



    }

    return 0;
}



void timer_neighbor(struct timer_queue_entry *timer_entry)
{
    struct neighbor_list_entry  *tmp_entry;
    struct route_table_entry *tmp_route;

    tmp_entry = find_neighbor_list_entry(timer_entry->id);

    if (tmp_entry!=NULL)
    {
        tmp_route=find_route_table_entry(tmp_entry->ip);
        if (tmp_route!=NULL)
        {

            //link_break(tmp_entry->ip);  we can't delete it directly because that would trigger an error because you are making changes to the route table on an interupt!!!

            tmp_route->lifetime=getcurrtime()-1;
            //insert_event_queue_entry(g_my_ip,g_my_ip,NULL,NULL,EVENT_CLEANUP,0,NULL,0);
            delete_neighbor_list_entry(tmp_entry->ip);
        }
    }
}

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

   hello_resend
----------------------------------------------------
Handles the resending of the Hello message and
also places the hello message back on the
queue so it will be called again
****************************************************/
int hello_resend(struct timer_queue_entry *tmp_entry)
{
    struct rrep *tmp_rrep;
    struct interface_list_entry *tmp_interface;
    u_int64_t curr_time=getcurrtime();
    u_int16_t random_number;


    tmp_rrep=tmp_entry->data;

    tmp_interface=find_interface_by_ip(tmp_rrep->dst_ip);
    if (tmp_interface==NULL)
    {

        printk(KERN_WARNING "AODV: HELLO error retrieveing interface\n");
	
	kfree(tmp_rrep);
	
        return 0;
    }

    tmp_rrep->dst_seq = htonl(tmp_interface->route_entry->dst_seq);

    local_broadcast(1,tmp_rrep, sizeof(struct rrep));
    /*    get_random_bytes(&random_number,sizeof(u_int16_t));
    random_number=random_number%20;
    */
    tmp_interface->last_hello=curr_time;
    insert_timer_queue_entry(tmp_entry->tv + HELLO_INTERVAL, tmp_rrep,tmp_entry->size,tmp_rrep->dst_ip,tmp_entry->retries,tmp_entry->ttl, EVENT_HELLO);

    return 0;
}



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

   timer_cleanup
----------------------------------------------------
Gets rid of everything in the timer queue.
Should be called before you shutdown the module
****************************************************/
void timer_cleanup()
{
    insert_event_queue_entry(EVENT_CLEANUP,NULL);
    insert_timer_queue_entry(getcurrtime() + ACTIVE_ROUTE_TIMEOUT, NULL,0,g_my_ip,0,0, EVENT_CLEANUP);

}

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

   init_timer_queue
----------------------------------------------------
Initalizes the timer queue... duh!
****************************************************/
int init_timer_queue()
{

    init_timer(&aodv_timer);
    timer_queue=NULL;
    return 0;
}

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

   update_timer_queue
----------------------------------------------------
Sets the  system alarm for the first event in the
timer queue
****************************************************/
/*
static unsigned long tvtojiffies(struct timeval *value)
{
    unsigned long sec = (unsigned) value->tv_sec;
    unsigned long usec = (unsigned) value->tv_usec;
    u_int64_t numerator, numerator1;


	//This is a fix for an error that occurs on ARM Linux Kernels because they do 64bits differently
	//Thanks to S. Peter Li for coming up with this fix!

    numerator = ULONG_MAX;
    do_div( numerator, HZ );
    if (sec > (unsigned long) numerator)
        return ULONG_MAX;

    numerator = 1000000;
    do_div( numerator, HZ );

    usec += numerator - 1;

    numerator1 = usec;
    do_div( numerator1,  numerator );
    usec = numerator1;

    return HZ*sec+usec;
}
*/

static unsigned long tvtojiffies(struct timeval *value)
{
        unsigned long sec = (unsigned) value->tv_sec;
        unsigned long usec = (unsigned) value->tv_usec;

        if (sec > (ULONG_MAX / HZ))
                return ULONG_MAX;
        usec += 1000000 / HZ - 1;
        usec /= 1000000 / HZ;
        return HZ*sec+usec;
}


void update_timer_queue()
{
    struct timeval delay_time;
    u_int64_t currtime;
    u_int64_t tv;
    u_int64_t remainder, numerator;

    delay_time.tv_sec = 0;
    delay_time.tv_usec = 0;

    /* lock Read */
    timer_read_lock();
  
    if (timer_queue == NULL)
    {
        // No event to set timer for
        delay_time.tv_sec = 0;
        delay_time.tv_usec = 0;
    }
    else
    {
        //* Get the first time value
        tv = timer_queue->tv;

        currtime = getcurrtime();

        if (tv <= currtime)
        {
            // If the event has allready happend, set the timeout to              1 microsecond :-)


            delay_time.tv_sec = 0;
            delay_time.tv_usec = 1;