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

   rreq_id_queue
----------------------------------------------------
This is used to keep track of messages which
are flooded to prevent rebroadcast of messages
****************************************************/

struct rreq_id_queue_entry *rreq_id_queue;
/****************************************************

   init_rreq_id_queue
----------------------------------------------------
Gets the ball rolling!
****************************************************/

int init_rreq_id_queue( void )
{
    rreq_id_queue=NULL;
    return 0;
}

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

   find_rreq_id_queue_entry
----------------------------------------------------
will search the queue for an entry with the
matching ID and src_ip
****************************************************/
struct rreq_id_queue_entry *find_rreq_id_queue_entry(u_int32_t src_ip, u_int32_t rreq_id)
{
    struct rreq_id_queue_entry  *tmp_entry;  /* Working entry in the RREQ list */

    tmp_entry = rreq_id_queue; /* Start at the header */

    //go through the whole queue
    while (tmp_entry!=NULL)
    {
        //if there is a match and it is still valid
        if (src_ip == tmp_entry->src_ip && rreq_id == tmp_entry->rreq_id)
            if (check_rreq_id_queue_entry_lifetime(tmp_entry) == 0)
                return tmp_entry;

        //continue on to the next entry
        tmp_entry=tmp_entry->next;

    }
    return NULL;
}


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

   read_rreq_id_proc
----------------------------------------------------
prints out the flood id queue when the proc
file is read
****************************************************/
int read_rreq_id_proc(char *buffer, char **buffer_location, off_t offset, int buffer_length,int *eof,void *data)
{
    int len;
    static char *my_buffer;
    char temp_buffer[80];
    struct rreq_id_queue_entry *tmp_entry;
    char tmp[16];
    u_int64_t tmp_time;
    tmp_entry=rreq_id_queue;

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

    while (tmp_entry!=NULL)
    {
        tmp_time=tmp_entry->lifetime-getcurrtime();
        strcpy(tmp,inet_ntoa(tmp_entry->dst_ip));
        sprintf(temp_buffer,"Src IP: %-16s  Dst IP: %-16s Flood ID: %-10u sec/msec: %lu/%lu \n", inet_ntoa(tmp_entry->src_ip),tmp,tmp_entry->rreq_id,(unsigned long)(tmp_time) / 1000, (unsigned long)(tmp_time) % 1000);
        strcat(my_buffer,temp_buffer);
        tmp_entry=tmp_entry->next;
    }

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

    *buffer_location=my_buffer;
    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_rreq_id_queue
----------------------------------------------------
prints out the flood id queue onto the console
screen
****************************************************/
void print_rreq_id_queue()
{
    struct rreq_id_queue_entry *tmp_entry;
    char tmp[16];
    tmp_entry=rreq_id_queue;

    printk("Flood ID list:\n");
    while (tmp_entry!=NULL)
    {
        strcpy(tmp,inet_ntoa(tmp_entry->dst_ip));
        printk("Src IP: %-16s  Dst IP: %-16s Flood ID: %-10u  \n", inet_ntoa(tmp_entry->src_ip),tmp,tmp_entry->rreq_id);
        tmp_entry=tmp_entry->next;
    }
}

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

   clean_up_rreq_id_queue
----------------------------------------------------
Deletes everything in the flood id queue
****************************************************/
void cleanup_rreq_id_queue()
{
    struct rreq_id_queue_entry *tmp_entry,*dead_entry;
    int count=0;

    tmp_entry=rreq_id_queue;

#ifdef MESSAGES
    print_rreq_id_queue();
#endif

    while (tmp_entry!=NULL)
    {
        dead_entry=tmp_entry;
        tmp_entry=tmp_entry->next;
        kfree(dead_entry);
        count++;
    }

#ifdef MESSAGES
    printk("Removed %d Flood ID entries! \n",count);
    printk("---------------------------------------------\n");
#endif
}

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

   insert_rreq_id_queue_entry
----------------------------------------------------
Inserts an entry into the flood ID queue
****************************************************/
int insert_rreq_id_queue_entry(u_int32_t ip, u_int32_t dst_ip,u_int32_t id, u_int64_t lt)
{
    struct rreq_id_queue_entry  *new_entry; /* Pointer to the working entry */

    /* The header wasn't empty, find the last entry */

    /* Allocate memory for the new entry */
    if ((new_entry = (struct rreq_id_queue_entry*)kmalloc(sizeof(struct rreq_id_queue_entry),GFP_ATOMIC)) == NULL)
    {
#ifndef NO_ERROR
        printk("INSERT_FLOOD_ID_QUEUE_ENTRY: Error creating flood ID queue entry\n");
#endif
        /* Failed to allocate memory for new Route Request */
        return 1;
    }
    /* Fill in the information in the new entry */
    new_entry->src_ip = ip;
    new_entry->dst_ip = dst_ip;
    new_entry->rreq_id = id;
    new_entry->lifetime = lt;
    new_entry->next = rreq_id_queue;

    /* Put the new entry in the list */
    rreq_id_queue=new_entry;

    return 0;
}

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

   check_rreq_id_queue_entry_lifetime
----------------------------------------------------
Checks the lifetime of a flood ID queue entry.
Returns 0 if it is valid and 1 if it is not!
****************************************************/
int check_rreq_id_queue_entry_lifetime(struct rreq_id_queue_entry *tmp_entry)
{
    u_int64_t  curr_time = getcurrtime(); /* Current time */

    /* Check if the entry is valid */
    if ((tmp_entry!=NULL )&&(curr_time > tmp_entry->lifetime))
    {

        return 1;
    }

    if (tmp_entry==NULL)
	#ifndef NO_ERROR
        printk("check_rreq_id_queue_lifetime passed a NULL\n");
	#endif
    return 0;
}

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

   delete_old_rreq_id_queue_entries
----------------------------------------------------
Goes through the flood ID queue and deletes
all of the old entries
****************************************************/
void delete_old_rreq_id_queue_entries(void )
{
    struct rreq_id_queue_entry *tmp_entry,*prev_entry,*dead_entry;
    u_int64_t  curr_time = getcurrtime(); /* Current time */


    tmp_entry=rreq_id_queue;
    prev_entry=NULL;

    //go through the entire queue
    while(tmp_entry!=NULL)
    {

        //if the entry has expired
        if (curr_time > tmp_entry->lifetime)
        {
            //if it is the first entry
            if(prev_entry==NULL)
                rreq_id_queue=NULL;
            else
                prev_entry->next=tmp_entry->next;

            //kill it!
            dead_entry=tmp_entry;
            tmp_entry=tmp_entry->next;
            kfree(dead_entry);
        }
        else
        {
            //next entry
            prev_entry=tmp_entry;
            tmp_entry=tmp_entry->next;
        }
    }
}

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

   delete_rreq_id_queue_entry
----------------------------------------------------
Deletes a flood id queue entry
****************************************************/
int delete_rreq_id_queue_entry(struct rreq_id_queue_entry *dead_entry)
{
    struct rreq_id_queue_entry *tmp_entry, *prev_entry;

    tmp_entry=rreq_id_queue;
    prev_entry=NULL;

    //since we don't know the previous entry we have to go
    //through entire list to find it!
    while (tmp_entry!=NULL)
    {
        //if we find the entry we wish to delete
        if(tmp_entry==dead_entry)
        {
            if (prev_entry==NULL)
                rreq_id_queue=NULL;
            else
                prev_entry->next=tmp_entry->next;
            kfree(tmp_entry);
            return 0;
        }
        tmp_entry=tmp_entry->next;
    }
    return 1;
}