Initial import
[olsrd.git] / front-end / src / nodes.c
1 /*
2  * OLSR ad-hoc routing table management protocol GUI front-end
3  * Copyright (C) 2003 Andreas T√łnnesen (andreto@ifi.uio.no)
4  *
5  * This file is part of olsrd-unik.
6  *
7  * uolsrGUI is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * uolsrGUI is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with olsrd-unik; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20  *
21  */
22
23 #include "common.h"
24 #include "nodes.h"
25 #include <math.h>
26
27
28 void
29 init_nodes()
30 {
31
32   nodes.next = &nodes;
33   nodes.prev = &nodes;
34 }
35
36 /*
37  *Insert a new node in the list
38  *NB! The list is NOT checked for duplicates!!
39  */
40 struct node *
41 insert_node(struct node *n, olsr_u8_t vtime)
42 {
43   struct node *new_node;
44
45   printf("Inserting node %s\n", ip_to_string((union olsr_ip_addr *)&n->addr));
46
47   if((new_node = malloc(sizeof(struct node))) == 0)
48     {
49       fprintf(stderr, "OUT OF MEMORY!\n");
50       exit(1);
51     }
52
53   memcpy(new_node, n, sizeof(struct node));
54   
55   /* queue */
56   nodes.next->prev = new_node;
57   new_node->next = nodes.next;
58   nodes.next = new_node;
59   new_node->prev = &nodes;
60
61   new_node->hna.next = &new_node->hna;
62   new_node->hna.prev = &new_node->hna;
63   new_node->mid.next = &new_node->mid;
64   new_node->mid.prev = &new_node->mid;
65   new_node->mpr.next = &new_node->mpr;
66   new_node->mpr.prev = &new_node->mpr;
67
68
69   update_timer_node(&n->addr, vtime);
70
71   return new_node;
72 }
73
74
75 /**
76  *Add a new node to the set
77  */
78 int
79 add_node(union olsr_ip_addr *node, olsr_u8_t vtime)
80 {
81   struct node new;
82   struct node *tmp_nodes;
83   struct timeval tmp_timer;
84   double dbl_time;
85   olsr_u32_t time_value;
86   struct mid *tmp_mid;
87
88   dbl_time = me_to_double(vtime);
89   time_value = (olsr_u32_t) dbl_time*1000;
90
91   tmp_timer.tv_sec = time_value/1000;
92   tmp_timer.tv_usec = (time_value-(tmp_timer.tv_sec*1000)) * 1000;   
93
94   /* Check if node exists */
95   for(tmp_nodes = nodes.next;
96       tmp_nodes != &nodes;
97       tmp_nodes = tmp_nodes->next)
98     {
99       if(memcmp(&tmp_nodes->addr, node, ipsize) == 0)
100         {
101           //printf("updating timer for node %s\n", ip_to_string(node));
102           //printf("Updatimng timer for: %s\n", ip_to_string(node));
103           //printf("Secs: %d, usecs: %d\n", (int)tmp_timer.tv_sec, (int)tmp_timer.tv_usec);
104           gettimeofday(&now, (struct timezone *)NULL);
105           timeradd(&now, &tmp_timer, &tmp_nodes->timer);
106           return 0; 
107         }
108       /* Check MID */
109       for(tmp_mid = tmp_nodes->mid.next;
110           tmp_mid != &tmp_nodes->mid;
111           tmp_mid = tmp_mid->next)
112         {
113           if(memcmp(&tmp_mid->alias, node, ipsize) == 0)
114             {
115               //printf("updating timer for node %s\n", ip_to_string(node));
116               //printf("Updatimng timer for (MID): %s\n", ip_to_string(&tmp_nodes->addr));
117               //printf("Secs: %d, usecs: %d\n", (int)tmp_timer.tv_sec, (int)tmp_timer.tv_usec);
118               gettimeofday(&now, (struct timezone *)NULL);
119               timeradd(&now, &tmp_timer, &tmp_nodes->timer);
120               return 0; 
121             }
122         }
123     }
124
125   /* New node */
126   memset(&new, 0, sizeof(struct node));
127   memcpy(&new.addr, node, ipsize);
128   new.display = 1;
129   printf("1:");
130   insert_node(&new, vtime);
131   update_nodes_list(&new);
132  
133   return 1;
134 }
135
136
137 int
138 update_timer_node(union olsr_ip_addr *node, olsr_u8_t vtime)
139 {
140   struct node *tmp_nodes;
141   struct timeval tmp_timer;
142   double dbl_time;
143   olsr_u32_t time_value;
144
145   dbl_time = me_to_double(vtime);
146   time_value = (olsr_u32_t) dbl_time*1000;
147
148   tmp_timer.tv_sec = time_value/1000;
149   tmp_timer.tv_usec = (time_value-(tmp_timer.tv_sec*1000)) * 1000;   
150
151   //printf("Updatimng timer for: %s\n", ip_to_string(node));
152   //printf("Secs: %d, usecs: %d\n", (int)tmp_timer.tv_sec, (int)tmp_timer.tv_usec);
153
154   for(tmp_nodes = nodes.next;
155       tmp_nodes != &nodes;
156       tmp_nodes = tmp_nodes->next)
157     {
158       if(memcmp(&tmp_nodes->addr, node, ipsize) == 0)
159         {
160           //printf("updating timer for node %s\n", ip_to_string(node));
161           gettimeofday(&now, (struct timezone *)NULL);
162           timeradd(&now, &tmp_timer, &tmp_nodes->timer);
163           if(tmp_nodes->display)
164             update_nodes_list(tmp_nodes);
165           return 1; 
166         }
167     }
168   
169   return 0;
170 }
171
172
173 /**
174  *Updates the hold time for the mpr 'mpr' registered on
175  *the node 'node'. Adds the mpr to the node if not already
176  *registered.
177  *@param node the node that has chosen the MPR
178  *@param mpr the MPR chosen by the node
179  *@return 0 if node was added, 1 if not
180  */
181 int
182 update_timer_mpr(union olsr_ip_addr *node, union olsr_ip_addr *mpr, olsr_u8_t vtime)
183 {
184   struct node *tmp_nodes;
185   struct mpr *tmp_mpr;
186   struct timeval tmp_timer;
187   double dbl_time;
188   olsr_u32_t time_value;
189
190   dbl_time = me_to_double(vtime);
191   time_value = (olsr_u32_t) dbl_time*1000;
192
193   tmp_timer.tv_sec = time_value/1000;
194   tmp_timer.tv_usec = (time_value-(tmp_timer.tv_sec*1000)) * 1000;   
195
196   //printf("Updatimng MPR timer for: %s\n", ip_to_string(node));
197   //printf("Secs: %d, usecs: %d\n", (int)tmp_timer.tv_sec, (int)tmp_timer.tv_usec);
198
199   //printf("Updatimng timer for: %s\n", ip_to_string(node));
200   for(tmp_nodes = nodes.next;
201       tmp_nodes != &nodes;
202       tmp_nodes = tmp_nodes->next)
203     {
204       if(memcmp(&tmp_nodes->addr, node, ipsize) == 0)
205         {
206           for(tmp_mpr = tmp_nodes->mpr.next;
207               tmp_mpr != &tmp_nodes->mpr;
208               tmp_mpr = tmp_mpr->next)
209             {
210               if(memcmp(&tmp_mpr->addr, mpr, ipsize) == 0)
211                 {
212                   //printf("updating timer for MPR %s ", ip_to_string(mpr));
213                   //printf("node %s\n", ip_to_string(node));
214                   gettimeofday(&now, (struct timezone *)NULL);
215                   timeradd(&now, &tmp_timer, &tmp_mpr->timer);
216                   return 1; 
217                 }
218             }
219           /* Only add if parent is added */
220           add_mpr(node, mpr, &tmp_timer);
221           return 0;
222         }
223     }
224
225   return 0;
226 }
227
228
229
230
231 int
232 add_mid_node(union olsr_ip_addr *node, union olsr_ip_addr *alias, olsr_u8_t vtime)
233 {
234
235   struct node *tmp_nodes;
236   struct mid *tmp_mid;
237   struct node new, *inserted;
238
239   //printf("MID_add: %s\n", ip_to_string(alias));
240
241   //update_timer_node(node, vtime);
242
243   for(tmp_nodes = nodes.next;
244       tmp_nodes != &nodes;
245       tmp_nodes = tmp_nodes->next)
246     {
247       if(memcmp(&tmp_nodes->addr, node, ipsize) == 0)
248         {
249           for(tmp_mid = tmp_nodes->mid.next;
250               tmp_mid != &tmp_nodes->mid;
251               tmp_mid = tmp_mid->next)
252             {
253               if(memcmp(&tmp_mid->alias, alias, ipsize) == 0)
254                 return 0;
255             }
256
257           /* we didn't find the address */
258           printf("(1)NEW MID %s ", ip_to_string(alias));
259           printf("ADDED FOR %s\n", ip_to_string(node));
260           if((tmp_mid = malloc(sizeof(struct mid))) == 0)
261             {
262               fprintf(stderr, "OUT OF MEMORY\n");
263               exit(1);
264             }
265
266           memcpy(&tmp_mid->alias, alias, ipsize);
267
268           tmp_nodes->mid.next->prev = tmp_mid;
269           tmp_mid->next = tmp_nodes->mid.next;
270           tmp_nodes->mid.next = tmp_mid;
271           tmp_mid->prev = &tmp_nodes->mid;
272
273           remove_node_addr(alias); // Remove if already registered as a node
274           
275           update_nodes_list(tmp_nodes);
276           return 1; 
277
278         }
279     }
280
281
282
283   /*New node */
284
285   printf("ADDING NEW NODE %s FROM MID...\n", ip_to_string(node));
286   /* We don't know wery much... */
287   memset(&new, 0, sizeof(struct node));
288   memcpy(&new.addr, node, ipsize);
289   inserted = insert_node(&new, vtime);
290
291   if((tmp_mid = malloc(sizeof(struct mid))) == 0)
292     {
293       fprintf(stderr, "OUT OF MEMORY!\n");
294       exit(1);
295     }
296
297   memcpy(&tmp_mid->alias, alias, ipsize);
298
299   tmp_mid->next = &inserted->mid;
300   tmp_mid->prev = &inserted->mid;
301   inserted->mid.next = tmp_mid;
302   inserted->mid.prev = tmp_mid;
303
304   update_nodes_list(inserted);
305
306   return 2;
307 }
308
309
310 int
311 add_hna_node(union olsr_ip_addr *node, union olsr_ip_addr *net, union olsr_ip_addr *mask, olsr_u8_t vtime)
312 {
313
314   struct node *tmp_nodes;
315   struct hna *tmp_hna;
316   struct node new, *inserted;
317
318   //printf("HNA: %s\n", ip_to_string(&net));
319
320   update_timer_node(node, vtime);
321
322   for(tmp_nodes = nodes.next;
323       tmp_nodes != &nodes;
324       tmp_nodes = tmp_nodes->next)
325     {
326       if(memcmp(&tmp_nodes->addr, node, ipsize) == 0)
327         {
328           for(tmp_hna = tmp_nodes->hna.next;
329               tmp_hna != &tmp_nodes->hna;
330               tmp_hna = tmp_hna->next)
331             {
332               if((memcmp(&tmp_hna->net, net, ipsize) == 0) && (memcmp(&tmp_hna->mask, mask, ipsize) == 0))
333                 return 0;
334             }
335
336           //printf("NEW HNA ADDED FOR %s ", ip_to_string(node));
337           //printf("net: %s \n", ip_to_string(&net));
338           /* we didn't find the address */
339           if((tmp_hna = malloc(sizeof(struct hna))) == 0)
340             {
341               fprintf(stderr, "OUT OF MEMORY\n");
342               exit(1);
343             }
344
345           memcpy(&tmp_hna->net, net, ipsize);
346           memcpy(&tmp_hna->mask, mask, ipsize);
347
348           /* queue */
349           tmp_nodes->hna.next->prev = tmp_hna;
350           tmp_hna->next = tmp_nodes->hna.next;
351           tmp_nodes->hna.next = tmp_hna;
352           tmp_hna->prev = &tmp_nodes->hna;
353           
354           update_nodes_list(tmp_nodes);
355           return 1; 
356         }
357     }
358
359
360
361   printf("ADDING NEW NODE %s FROM HNA...\n", ip_to_string(node));
362   /* We don't know wery much... */
363   memset(&new, 0, sizeof(struct node));
364   memcpy(&new.addr, node, ipsize);
365   inserted = insert_node(&new, vtime);
366
367   if((tmp_hna = malloc(sizeof(struct hna))) == 0)
368     {
369       fprintf(stderr, "OUT OF MEMORY!\n");
370       exit(1);
371     }
372
373   memcpy(&tmp_hna->net, net, ipsize);
374   memcpy(&tmp_hna->mask, mask, ipsize);
375
376   tmp_hna->next = &inserted->hna;
377   tmp_hna->prev = &inserted->hna;
378   inserted->hna.next = tmp_hna;
379   inserted->hna.prev = tmp_hna;
380
381   update_nodes_list(inserted);
382
383   return 2;
384 }
385
386
387 /**
388  *Add the MPR mpr to the node nodes selected MPRs.
389  *Nodes are NOT added if they are not yet registered!
390  *
391  *@param node the node that has chosen an MPR
392  *@param mpr the MPR choosen by node
393  *@return negative if node already registered or node not found
394  */
395 int
396 add_mpr(union olsr_ip_addr *node, union olsr_ip_addr *mpr, struct timeval *tmp_timer)
397 {
398
399   struct node *tmp_nodes;
400   struct mpr *mprs;
401   struct mpr *tmp_mpr;
402
403   for(tmp_nodes = nodes.next;
404       tmp_nodes != &nodes;
405       tmp_nodes = tmp_nodes->next)
406     {
407       if(memcmp(&tmp_nodes->addr, node, ipsize) == 0)
408         {
409           for(mprs = tmp_nodes->mpr.next;
410               mprs != &tmp_nodes->mpr;
411               mprs = mprs->next)
412             {
413               if(memcmp(&mprs->addr, mpr, ipsize) == 0)
414                   return 0;
415             }
416
417           //printf("Adding MPR %s to ", ip_to_string(mpr));
418           //printf("%s\n", ip_to_string(node));
419           /* Add mpr */
420
421           if((tmp_mpr = malloc(sizeof(struct mpr))) == 0)
422             {
423               fprintf(stderr, "OUT OF MEMORY\n");
424               exit(1);
425             }
426
427           memcpy(&tmp_mpr->addr, mpr, ipsize);
428
429           gettimeofday(&now, (struct timezone *)NULL);
430           timeradd(&now, tmp_timer, &tmp_mpr->timer);
431
432           /* queue */
433           tmp_nodes->mpr.next->prev = tmp_mpr;
434           tmp_mpr->next = tmp_nodes->mpr.next;
435           tmp_nodes->mpr.next = tmp_mpr;
436           tmp_mpr->prev = &tmp_nodes->mpr;
437
438           update_nodes_list(tmp_nodes);
439           return 1; 
440
441         }
442     }
443
444   return 1;
445 }
446
447
448
449
450 int
451 remove_node(struct node *node)
452 {
453   struct hna *tmp_hna, *tmp_hna2;
454   struct mid *tmp_mid, *tmp_mid2;
455   struct mpr *tmp_mpr, *tmp_mpr2;
456
457   printf("Remove node %s\n", ip_to_string(&node->addr));
458
459
460   tmp_hna = node->hna.next;
461   while(tmp_hna != &node->hna)
462     {
463       tmp_hna2 = tmp_hna;
464       tmp_hna = tmp_hna->next;
465       free(tmp_hna2);
466     }
467   tmp_mpr = node->mpr.next;
468   while(tmp_mpr != &node->mpr)
469     {
470       tmp_mpr2 = tmp_mpr;
471       tmp_mpr = tmp_mpr->next;
472       free(tmp_mpr2);
473     }
474   tmp_mid = node->mid.next;
475   while(tmp_mid != &node->mid)
476     {
477       tmp_mid2 = tmp_mid;
478       tmp_mid = tmp_mid->next;
479       free(tmp_mid2);
480     }
481   
482   /* Gemove form GUI */
483   remove_nodes_list(&node->addr);
484   
485   /* Dequeue */
486   node->prev->next = node->next;
487   node->next->prev = node->prev;
488   
489   free(node);
490
491   return 1;  
492 }
493
494
495
496
497
498
499 /*
500  * Remove based on address
501  */
502
503 int
504 remove_node_addr(union olsr_ip_addr *node)
505 {
506   struct node *tmp_nodes;
507   struct hna *tmp_hna, *tmp_hna2;
508   struct mid *tmp_mid, *tmp_mid2;
509   struct mpr *tmp_mpr, *tmp_mpr2;
510
511   printf("Remove node %s\n", ip_to_string(node));
512
513
514   tmp_nodes = nodes.next;
515
516   while(tmp_nodes != &nodes)
517     {
518       if(memcmp(&tmp_nodes->addr, node, ipsize) == 0)
519         {
520           printf("(2)Deleting node %s\n", ip_to_string((union olsr_ip_addr *)&tmp_nodes->addr));
521
522           tmp_hna = tmp_nodes->hna.next;
523           while(tmp_hna != &tmp_nodes->hna)
524             {
525               tmp_hna2 = tmp_hna;
526               tmp_hna = tmp_hna->next;
527               free(tmp_hna2);
528             }
529           tmp_mpr = tmp_nodes->mpr.next;
530           while(tmp_mpr != &tmp_nodes->mpr)
531             {
532               tmp_mpr2 = tmp_mpr;
533               tmp_mpr = tmp_mpr->next;
534               free(tmp_mpr2);
535             }
536           tmp_mid = tmp_nodes->mid.next;
537           while(tmp_mid != &tmp_nodes->mid)
538             {
539               tmp_mid2 = tmp_mid;
540               tmp_mid = tmp_mid->next;
541               free(tmp_mid2);
542             }
543
544           /* Gemove form GUI */
545           remove_nodes_list(&tmp_nodes->addr);
546
547           /* Dequeue */
548           tmp_nodes->prev->next = tmp_nodes->next;
549           tmp_nodes->next->prev = tmp_nodes->prev;
550
551           free(tmp_nodes);
552
553           return 1;
554         }
555
556       tmp_nodes = tmp_nodes->next;
557     }
558
559   return 0;
560 }
561
562
563
564
565 struct node *
566 find_node(char *ip)
567 {
568   struct node *tmp_nodes;
569
570   for(tmp_nodes = nodes.next;
571       tmp_nodes != &nodes;
572       tmp_nodes = tmp_nodes->next)
573     {
574       if(strcmp(ip_to_string((union olsr_ip_addr *)&tmp_nodes->addr), ip) == 0)
575         return tmp_nodes;
576     }
577
578   return NULL;
579 }
580
581
582 struct node *
583 find_node_t(union olsr_ip_addr *ip)
584 {
585   struct node *tmp_nodes;
586
587   for(tmp_nodes = nodes.next;
588       tmp_nodes != &nodes;
589       tmp_nodes = tmp_nodes->next)
590     {
591       if(memcmp(&tmp_nodes->addr, ip, ipsize) == 0)
592         return tmp_nodes;
593     }
594
595
596   return 0;
597 }
598
599
600 /*
601  *Remove timed out nodes
602  */
603 gint
604 time_out_nodes(gpointer data)
605 {
606   struct node *tmp_nodes;
607   struct node *node_to_delete;
608
609   /* Wait before starting timing out */
610   if(timeouts)
611     {
612       timeouts--;
613       //printf("Waiting...\n");
614       return 1;
615     }
616
617   //printf("Timing out nodes...\n");
618   gettimeofday(&now, (struct timezone *)NULL);
619
620   tmp_nodes = nodes.next;
621
622   while(tmp_nodes != &nodes)
623     {
624       //printf("%s: %6d < %6d\n", ip_to_string(&tmp_nodes->addr), tmp_nodes->timer.tv_sec, now.tv_sec);
625       if(timercmp(&tmp_nodes->timer,&now,<))
626         {
627           printf("Node %s timed out...\n", ip_to_string((union olsr_ip_addr *)&tmp_nodes->addr));
628           node_to_delete = tmp_nodes;
629
630           tmp_nodes = tmp_nodes->next;
631
632           remove_nodes_list(&node_to_delete->addr);
633           remove_node(node_to_delete);
634         } 
635       else
636         tmp_nodes = tmp_nodes->next;
637     }
638
639   return 1;
640 }
641
642
643
644 /**
645  *Timeout MPRs for a given node. Only called when user
646  *is to see the registered MPRs of the node.
647  *@param node the node whom MPRs should be timed out
648  *@return negative if node not found
649  */
650 int
651 time_out_mprs(union olsr_ip_addr *node)
652 {
653
654   struct node *tmp_nodes;
655   struct mpr *mpr_to_delete;
656   struct mpr *tmp_mpr;
657
658   gettimeofday(&now, (struct timezone *)NULL);
659
660
661   /* W A R N I N G !
662    *
663    * THIS ALGORITHM HAS NOT BEEN TESTED PROPERLY!!!!!!
664    * -Andreas
665    */
666
667   for(tmp_nodes = nodes.next;
668       tmp_nodes != &nodes;
669       tmp_nodes = tmp_nodes->next)
670     {
671       if(memcmp(&tmp_nodes->addr, node, ipsize) == 0)
672         {
673           tmp_mpr = tmp_nodes->mpr.next;
674          
675           while(tmp_mpr != &tmp_nodes->mpr)
676             {
677               if(timercmp(&tmp_mpr->timer,&now,<))
678                 {
679                   printf("MPR %s OF NODE ", ip_to_string((union olsr_ip_addr *)&tmp_mpr->addr));
680                   printf("%s TIMIED OUT ", ip_to_string((union olsr_ip_addr *)&tmp_nodes->addr));fflush(stdout);
681
682                   mpr_to_delete = tmp_mpr;
683                   tmp_mpr = tmp_mpr->next;
684
685                   /* Dequeue */
686                   mpr_to_delete->next->prev = mpr_to_delete->prev;
687                   mpr_to_delete->prev->next = mpr_to_delete->next;
688                   /* Delete */
689                   free(mpr_to_delete);
690                 }
691               else
692                 tmp_mpr = tmp_mpr->next;
693             }
694
695           return 1;
696         }
697     }
698
699   return 0;
700 }
701
702
703
704 void
705 init_timer(olsr_u32_t time_value, struct timeval *hold_timer)
706
707   olsr_u16_t  time_value_sec=0;
708   olsr_u16_t  time_value_msec=0;
709
710   time_value_sec=time_value/1000;
711   time_value_msec=time_value-(time_value_sec*1000);
712
713   hold_timer->tv_sec=time_value_sec;
714   hold_timer->tv_usec=time_value_msec*1000; 
715   
716 }
717
718
719 /**
720  *Function that converts a mantissa/exponent 8bit value back
721  *to double as described in RFC3626:
722  *
723  * value = C*(1+a/16)*2^b [in seconds]
724  *
725  *  where a is the integer represented by the four highest bits of the
726  *  field and b the integer represented by the four lowest bits of the
727  *  field.
728  *
729  *@param me the 8 bit mantissa/exponen value
730  *
731  *@return a double value
732  */
733 double
734 me_to_double(olsr_u8_t me)
735 {
736   int a = me>>4;
737   int b = me - a*16;
738   return (double)(VTIME_SCALE_FACTOR*(1+(double)a/16)*(double)pow(2,b));
739 }