timer_queue.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 "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;
        }
        else
        {
            // Set the timer to the actual seconds / microseconds from now

            //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 = ( tv - currtime );
          remainder = do_div( numerator, 1000 );

            delay_time.tv_sec =  numerator;
            delay_time.tv_usec = remainder * 1000;

        }

    }

    if (!timer_pending(&aodv_timer))
    {
        aodv_timer.function=&timer_queue_signal;
        aodv_timer.expires=jiffies + tvtojiffies(&delay_time);
        add_timer(&aodv_timer);
    }
    else
    {
      mod_timer(&aodv_timer,jiffies + tvtojiffies(&delay_time));
    }

    /* lock Read */
    timer_read_unlock();

    // Set the timer (in real time)
    return;
}



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

   timer_queue_signal
----------------------------------------------------
Gets called when the system alarm goes off. The
function then pulls the first queued event and
acts on it
****************************************************/
void timer_queue_signal()
{
    struct timer_queue_entry *tmp_entry;
    u_int64_t currtime;



    // Get the first due entry in the queue /
    currtime = getcurrtime();
    tmp_entry = find_first_timer_queue_entry_due(currtime);
    // While there is still events that has timed out

    while (tmp_entry != NULL)
    {
        switch (tmp_entry->flags)
        {
        case EVENT_RREQ:
            timer_rreq(tmp_entry);
            break;

        case EVENT_HELLO:
            hello_resend(tmp_entry);
            break;

        case EVENT_CLEANUP:
            timer_cleanup();
            break;

        case EVENT_NEIGHBOR:
            timer_neighbor(tmp_entry);
            break;

        default:
            break;
        }

        // Dequeue the entry so that it will not happened again
        // delete_timer_queue_entry(tmp_entry);
        kfree(tmp_entry);

        // Get new time and check for more timedout entrys
        currtime = getcurrtime();
        tmp_entry = find_first_timer_queue_entry_due(currtime);
    }
    update_timer_queue();


}


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

   insert_timer_queue_entry
----------------------------------------------------
Insert an event into the queue. Also allocates
enough room for the data and copies that too
****************************************************/
int insert_timer_queue_entry(u_int64_t msec,void *data,int size,u_int32_t id,u_int16_t retries,u_int8_t ttl,unsigned char flags)
{
    struct timer_queue_entry *prev_entry;
    struct timer_queue_entry *tmp_entry;
    struct timer_queue_entry *new_entry;


    // get memory
    if ((new_entry = kmalloc(sizeof(struct timer_queue_entry), GFP_ATOMIC)) == NULL)
    {
        printk(KERN_WARNING "AODV: Error allocating timer!\n");

        return -ENOMEM;
    }

    // copy data
    new_entry->tv = msec;
    new_entry->id = id;
    new_entry->flags = flags;
    new_entry->retries=retries;
    new_entry->ttl=ttl;
    new_entry->size=size;
    new_entry->data=data;

    prev_entry=NULL;

    /* lock Write */
    timer_write_lock();


    tmp_entry=timer_queue;


    while (tmp_entry!=NULL && new_entry->tv > tmp_entry ->tv)
    {
        prev_entry=tmp_entry;
        tmp_entry=tmp_entry->next;
    }



      if (timer_queue==tmp_entry)
        {
          new_entry->next=timer_queue;
          timer_queue=new_entry;
        }
      else
        {
          if (tmp_entry==NULL)  // If at the end of the List
            {
              new_entry->next=NULL;
              prev_entry->next=new_entry;
            }
          else     // Inserting in to the middle of the list somewhere
            {
              new_entry->next=prev_entry->next;
              prev_entry->next=new_entry;
            }
        }

    /* unlock Write */
    timer_write_unlock();


    // Update the timer to reflect the new situation
    //    update_timer_queue();


    return 0;
}


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

   find_first_timer_queue_entry
----------------------------------------------------
Returns the first entry in the timer queue
****************************************************/
struct timer_queue_entry *find_first_timer_queue_entry()
{

    return timer_queue;
}


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

   find_first_timer_queue_entry_of_id
----------------------------------------------------
Returns the first timer queue entry with a matching
ID
****************************************************/
struct timer_queue_entry * find_first_timer_queue_entry_of_id(u_int32_t id)
{
    struct timer_queue_entry *tmp_entry;

    /* lock Read */
    timer_read_lock();


    tmp_entry=timer_queue;

    while (tmp_entry != NULL && tmp_entry->id != id)
        tmp_entry=tmp_entry->next;

    /* unlock Read */
    timer_read_unlock();

    return tmp_entry;
}

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

   find_first_timer_queue_entry_of_id_and_flag
----------------------------------------------------
Returns the first timer queue entry with a matching
ID and flag
****************************************************/
struct timer_queue_entry * find_first_timer_queue_entry_of_id_and_flag(u_int32_t id, unsigned char flags)
{
    struct timer_queue_entry *tmp_entry;

    /* lock Read */
    timer_read_lock();

    tmp_entry=timer_queue;


    while (tmp_entry != NULL && tmp_entry->id != id && tmp_entry->flags!=flags)
        tmp_entry=tmp_entry->next;

    /* unlock Read */
    timer_read_unlock();

    return tmp_entry;
}


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

   delete_timer_queue_entry_of_id
----------------------------------------------------
Deletes the first entry with a matching id
****************************************************/
void delete_timer_queue_entry_of_id(u_int32_t id, unsigned char flags)
{
    struct timer_queue_entry *tmp_entry;
    struct timer_queue_entry *prev_entry;
    struct timer_queue_entry *dead_entry;
    int deleted=0;

    /* lock Write */
    timer_write_lock();

    tmp_entry=timer_queue;
    prev_entry=NULL;

    while (tmp_entry != NULL)
    {
        if (tmp_entry->id == id && tmp_entry->flags == flags)
        {
            if (prev_entry==NULL)
                timer_queue=tmp_entry->next;
            else
                prev_entry->next=tmp_entry->next;

            dead_entry=tmp_entry;
            tmp_entry=tmp_entry->next;
            kfree(dead_entry->data);
            kfree(dead_entry);
            deleted=1;

        }
        else
        {
            prev_entry=tmp_entry;
            tmp_entry=tmp_entry->next;
        }
    }

    //    if (!deleted)
    // printk(KERN_WARNING "Faild to delete %s  -  %d\n",inet_ntoa(id),flags);
    /* unlock Write */
    timer_write_unlock();

    update_timer_queue();
}

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

   delete_timer_queue_entry
----------------------------------------------------
Deletes the entry from the timer queue. You
have to do this so the linked list is not broken
****************************************************/
int delete_timer_queue_entry(struct timer_queue_entry *dead_entry)
{
    struct timer_queue_entry *tmp_entry;
    struct timer_queue_entry *prev_entry;
    /* Is first element */


    /* lock Write */
    timer_write_lock();

    tmp_entry=timer_queue;
    prev_entry=NULL;

    while (tmp_entry!=NULL && tmp_entry!=dead_entry)
    {
        prev_entry=tmp_entry;
        tmp_entry=tmp_entry->next;
    }
    if (tmp_entry==NULL)
      {
        printk(KERN_WARNING "AODV: Could not find Timer Queue Entry to delete!\n");
        timer_write_unlock();
        return 1;

      }
    if (prev_entry==NULL)
        timer_queue=tmp_entry->next;
    else
        prev_entry->next=tmp_entry->next;

    //kfree(tmp_entry->data);
    kfree(tmp_entry);

    //update_timer_queue();

    /* unlock Write */
    timer_write_unlock();

    return 0;
}


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

   remove_first_timer_queue_entry
----------------------------------------------------
Removes the first timer queue entry
****************************************************/

void remove_first_timer_queue_entry()
{
    struct timer_queue_entry *dead_entry;

    /* lock Write */
    timer_write_lock();

    if (timer_queue!=NULL)
    {
        dead_entry=timer_queue;
        timer_queue=timer_queue->next;
        kfree(dead_entry);
    }

    /* unlock Write */
    timer_write_unlock();
}

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

   find_first_timer_queue_entry_due
----------------------------------------------------
Returns the first entry in the queue that has a time
that is lower than the argument ie. the first element
if the argument is greater than its tv value.
****************************************************/
struct timer_queue_entry *find_first_timer_queue_entry_due(u_int64_t tv)
{
    struct timer_queue_entry *tmp_entry;


    /* lock Read */
    timer_read_lock();


    if (timer_queue != NULL)
    {
        /* If pqe's time is in teh interval */
        if ((timer_queue->tv) < tv)
          {
            tmp_entry=timer_queue;
            timer_queue=timer_queue->next;
            return tmp_entry;
          }
    }

    /* unlock read */
    timer_read_unlock();

    return NULL;
}

---