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

   rreq
----------------------------------------------------
Handles the generation of RREQ and recieving
****************************************************/

extern u_int32_t g_broadcast_ip;
extern struct route_table_entry *g_my_entry;
extern u_int32_t g_my_ip;


void convert_rreq_to_host(struct rreq *tmp_rreq)
{
    tmp_rreq->rreq_id=ntohl(tmp_rreq->rreq_id);
    tmp_rreq->dst_seq=ntohl(tmp_rreq->dst_seq);
    tmp_rreq->src_seq=ntohl(tmp_rreq->src_seq);
}

void convert_rreq_to_network(struct rreq *tmp_rreq)
{
    tmp_rreq->rreq_id=htonl(tmp_rreq->rreq_id);
    tmp_rreq->dst_seq=htonl(tmp_rreq->dst_seq);
    tmp_rreq->src_seq=htonl(tmp_rreq->src_seq);
}



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

   recv_rreq
----------------------------------------------------
Handles the recieving of RREQs
****************************************************/
int recv_rreq(struct event_queue_entry *working_packet)
{
    struct rreq *working_rreq;
    struct interface_list_entry *tmp_interface;
    struct rreq       *out_rreq;  /* Forwarded RREQ */
    struct route_table_entry   *tmp_entry;       /* Routing table entry */
    struct flood_id_queue_entry *tmp_rreq_id;
    u_int64_t          current_time;  /* Current time */
    int size_out;

    /* Update the hop count */
    char src_ip[16];
    char dst_ip[16];



    working_rreq=working_packet->data;
    convert_rreq_to_host(working_rreq);

    //find what interface the packet was recived on
    tmp_interface=find_interface_by_dev(working_packet->dev);

    if (tmp_interface==NULL)
    {

        printk (KERN_WARNING "AODV: Recieved on a RREQ from an unrecognized interface.\n");

        return -ENODEV;
    }


    /* Look in the route request list to see if the node has
       already received this request. */
    tmp_rreq_id = find_flood_id_queue_entry(working_rreq->src_ip, working_rreq->rreq_id);


    /* Check if an entry in the route request list was found, and if it's
       still valid. If there is a valid entry, this request shouldn't be
       checked. */
    if (tmp_rreq_id != NULL) 
    {
        return 0;
    }

    tmp_entry=find_route_table_entry(working_rreq->src_ip);
    
    if ((tmp_entry!=NULL) && (tmp_entry->next_hop!=working_packet->src_ip))
      
      {
	strcpy(src_ip,inet_ntoa(working_rreq->src_ip));
	strcpy(dst_ip,inet_ntoa(working_rreq->dst_ip));
	//	printk("To: %s src: %s RREQ_ID: %u, expires: %d\n",src_ip,dst_ip,working_rreq->rreq_id,tmp_entry->lifetime-getcurrtime());
	return -EHOSTDOWN;
      }


    /* Have not received this RREQ within BCAST_ID_SAVE time */

    /* Add this RREQ to the list for further checks */

    current_time = getcurrtime(); /* Get the current time */


    if (insert_flood_id_queue_entry(working_rreq->src_ip, working_rreq->dst_ip,working_rreq->rreq_id, current_time + PATH_TRAVERSAL_TIME) == 1)
      {
        /* Couldn't add the entry, ignore and continue */
      }
    working_rreq->hop_count=working_rreq->hop_count+1;

    /* UPDATE REVERSE */

    update_route_entry(working_rreq->src_ip,  working_packet->src_ip, working_rreq->hop_count, working_rreq->src_seq, working_packet->dev);



    tmp_entry = find_route_table_entry(working_rreq->dst_ip);






    /* Test to see if we should send a RREP AKA we have or are the desired route*/

    if ((working_rreq->dst_ip == tmp_interface->ip) || 
	(tmp_entry != NULL && tmp_entry->route_valid && tmp_entry->route_seq_valid) )
    {
      /* The node already had a valid route to the destination */      
        if (working_rreq->u || seq_less_or_equal(working_rreq->dst_seq,tmp_entry->dst_seq ))
	  {
	    /*Check to see if only the destination should reply */
	    
            if (!working_rreq->d || (find_interface_by_ip(working_rreq->dst_ip)!=NULL))
	      {
		
                //If the RREQ is addressed to us and we have the same Seq as the RREQ we up our Seq by one
                if ((find_interface_by_ip(working_rreq->dst_ip)!=NULL) && (working_rreq->dst_seq>=tmp_entry->dst_seq))
		  {
                    tmp_entry->dst_seq=working_rreq->dst_seq+1;
		  }

                strcpy(src_ip,inet_ntoa(working_rreq->src_ip));
                strcpy(dst_ip,inet_ntoa(working_rreq->dst_ip));
                printk(KERN_INFO "AODV: Generating RREP -  src: %s dst: %s \n",src_ip,dst_ip);


                /* Call for gen_rrep to send a Route Reply */


                gen_rrep(working_rreq->src_ip,working_rreq->dst_ip,working_packet->src_ip,working_rreq->dst_seq,working_rreq->g);

                return 0;
            }
        }
    }

#ifdef AODV_GATEWAY
    if (!adhoc_subnet_test(working_rreq->dst_ip))
      {
	printk("Gatewaying for address: %s \n", inet_ntoa( working_rreq->dst_ip ));
	if (tmp_entry == NULL)
	  {
	    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 = working_rreq->dst_ip;
	    tmp_entry->next_hop = g_my_ip;
	    tmp_entry->dev= g_my_entry->dev;
	    tmp_entry->dst_seq = 1;
	    tmp_entry->route_valid = 1;
	    tmp_entry->route_seq_valid = 1;
	    tmp_entry->rreq_id = 0;
	    tmp_entry->hop_count = 20;
	    tmp_entry->lifetime = getcurrtime() + 5000;
	  }
	else
	  {
	    tmp_entry->dst_seq++;
	  }

	gen_rrep(working_rreq->src_ip,working_rreq->dst_ip,working_packet->src_ip,working_rreq->dst_seq,0);
	return 0;
      }
#endif



    /* The node didn't have a valid route to the destination */

    if ((working_packet->ttl) <=1)
    {
        return -ETIMEDOUT;
    }

    if ((out_rreq = (struct rreq*) kmalloc(sizeof (struct rreq),GFP_ATOMIC)) == NULL)
      {

        printk(KERN_WARNING "AODV: Error creating a new RREQ\n");

        /* Failed to allocate memory for forwarded RREQ */
        return -ENOMEM;
    }


    size_out=sizeof(struct rreq);

    /* Set the RREQ structure */
    out_rreq->type = 1;
    out_rreq->j = working_rreq->j;
    out_rreq->r = working_rreq->r;
    out_rreq->g = working_rreq->g;
    out_rreq->d = working_rreq->d;
    out_rreq->u = working_rreq->u;
    out_rreq->reserved = 0;
    out_rreq->hop_count = working_rreq->hop_count;
    out_rreq->dst_ip = working_rreq->dst_ip;
    out_rreq->src_ip = working_rreq->src_ip;

    //we want it to be network byte order
    out_rreq->src_seq = htonl(working_rreq->src_seq);
    out_rreq->rreq_id = htonl(working_rreq->rreq_id);

    /* Set the right sequence number */
    if (tmp_entry!=NULL)
    {
        if (seq_greater(working_rreq->dst_seq, tmp_entry->dst_seq))
            out_rreq->dst_seq=htonl(working_rreq->dst_seq);
        else
            out_rreq->dst_seq=htonl(tmp_entry->dst_seq);
    }
    else
        out_rreq->dst_seq = htonl(working_rreq->dst_seq);



    /* Call send_datagram to send and forward the RREQ */
    local_broadcast(working_packet->ttl-1, out_rreq, sizeof(struct rreq));

    kfree(out_rreq);

    return 0;
}



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

   gen_rreq
----------------------------------------------------
Generates a RREQ! wahhooo!
****************************************************/
int gen_rreq(u_int32_t src_ip, u_int32_t dst_ip)
{
    struct route_table_entry *tmp_entry;
    struct rreq *out_rreq, *timer_rreq;
    u_int8_t  out_ttl;




    /* Do not send rreq to the same host again if its already in the timer queue */

    if (find_first_timer_queue_entry_of_id_and_flag(dst_ip,EVENT_RREQ) != NULL)
        return 0;

    /* Allocate memory for the rreq message */


    if ((out_rreq = (struct rreq*) kmalloc(sizeof(struct rreq),GFP_ATOMIC)) == NULL)
    {
        printk(KERN_WARNING "AODV: Can't allocate new rreq\n");
        return -ENOMEM;
    }

    /* Allocate memory for the timer queue position for the rreq */

    if ((timer_rreq = kmalloc(sizeof(struct rreq),GFP_ATOMIC))==NULL)
    {
        printk("AODV: Can't allocate for a new timer queue position\n");
	kfree(out_rreq);

        /* Couldn't allocate memory */
        return -ENOMEM;
    }

    /* Get routing table entry for destination */
    tmp_entry = find_route_table_entry(dst_ip);


    if (tmp_entry == NULL)
    {
        /* Entry does not exist -> set to initial values*/
        out_rreq->dst_seq = 0;
        out_rreq->u = TRUE;
        out_ttl =  TTL_START;
    }
    else
    {
        /* Entry does exist -> get value from rt */
        out_rreq->dst_seq = htonl(tmp_entry->dst_seq);
        if (tmp_entry->route_seq_valid)
        {
            out_rreq->u=FALSE;
        }
        else
        {
            out_rreq->u=TRUE;
        }
        out_ttl =  tmp_entry->hop_count + TTL_INCREMENT;
    }

    /* Get routing table entry for source, when this is ourself this one should always exist*/

    tmp_entry = (find_interface_by_ip(src_ip))->route_entry;

    if (tmp_entry == NULL)
    {
        printk(KERN_WARNING "AODV: Can't get route to self\n");

	kfree(out_rreq);
	kfree(timer_rreq);

        return -EHOSTUNREACH;
    }

    /* Get our own sequence number */
    (tmp_entry->rreq_id)++;
    tmp_entry->dst_seq=tmp_entry->dst_seq+1;
    out_rreq->src_seq = htonl(tmp_entry->dst_seq);
    out_rreq->rreq_id = htonl(tmp_entry->rreq_id);

    /* Fill in the package */
    out_rreq->dst_ip = dst_ip;
    out_rreq->src_ip = src_ip;
    out_rreq->type = 1;
    out_rreq->hop_count = htonl(0);
    out_rreq->j = 0;
    out_rreq->r = 0;
    out_rreq->d = 0;
    out_rreq->reserved = 0;
    out_rreq->second_reserved = 0;
    out_rreq->g=1;

    /* Get the broadcast address and ttl right */

    //    if (insert_flood_id_queue_entry(out_rreq->src_ip, out_rreq->dst_ip,out_rreq->rreq_id, getcurrtime() + 2* out_ttl * NODE_TRAVERSAL_TIME) == 1)
    if (insert_flood_id_queue_entry(out_rreq->src_ip, out_rreq->dst_ip,out_rreq->rreq_id, getcurrtime() + 2 * NET_TRAVERSAL_TIME) < 0)
    {
      kfree(out_rreq);
      kfree(timer_rreq);

      printk(KERN_WARNING "AODV: Can't add to broadcast list\n");

      return -ENOMEM;
    }

    memcpy(timer_rreq,out_rreq,sizeof(struct rreq));
    out_ttl=10;
    //    insert_timer_queue_entry(getcurrtime() + NET_TRAVERSAL_TIME,timer_rreq, sizeof(struct rreq),out_rreq->dst_ip,0,out_ttl, EVENT_RREQ);
    insert_timer_queue_entry(getcurrtime() + NET_TRAVERSAL_TIME,timer_rreq, sizeof(struct rreq),out_rreq->dst_ip,RREQ_RETRIES,out_ttl, EVENT_RREQ);


    update_timer_queue();

    //local_broadcast(out_ttl,out_rreq,sizeof(struct rreq));
    local_broadcast(10,out_rreq,sizeof(struct rreq));

    kfree(out_rreq);

    return 0;
}