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