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