/*               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 "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;}