Cleanup in use of extern variables. Rather trivial changes, but a lot of them
[olsrd.git] / src / mpr.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without 
7  * modification, are permitted provided that the following conditions 
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright 
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright 
13  *   notice, this list of conditions and the following disclaimer in 
14  *   the documentation and/or other materials provided with the 
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its 
17  *   contributors may be used to endorse or promote products derived 
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  * $Id: mpr.c,v 1.15 2006/01/07 08:16:20 kattemat Exp $
40  */
41
42 #include "defs.h"
43 #include "mpr.h"
44 #include "two_hop_neighbor_table.h"
45 #include "olsr.h"
46 #include "neighbor_table.h"
47 #include "scheduler.h"
48
49 /* Begin:
50  * Prototypes for internal functions 
51  */
52
53 static olsr_u16_t
54 add_will_always_nodes(void);
55
56 static void
57 olsr_optimize_mpr_set(void);
58
59 static void
60 olsr_clear_mprs(void);
61
62 static void
63 olsr_clear_two_hop_processed(void);
64
65 static struct neighbor_entry *
66 olsr_find_maximum_covered(int);
67
68 static olsr_u16_t
69 olsr_calculate_two_hop_neighbors(void);
70
71 static int
72 olsr_check_mpr_changes(void);
73
74 static int
75 olsr_chosen_mpr(struct neighbor_entry *, olsr_u16_t *);
76
77 static struct neighbor_2_list_entry *
78 olsr_find_2_hop_neighbors_with_1_link(int);
79
80
81 /* End:
82  * Prototypes for internal functions 
83  */
84
85
86
87 /**
88  *Find all 2 hop neighbors with 1 link
89  *connecting them to us trough neighbors
90  *with a given willingness.
91  *
92  *@param willingness the willigness of the neighbors
93  *
94  *@return a linked list of allocated neighbor_2_list_entry structures
95  */
96 static struct neighbor_2_list_entry *
97 olsr_find_2_hop_neighbors_with_1_link(int willingness)
98 {
99   
100  
101   olsr_u8_t                    index;
102   struct neighbor_2_list_entry *two_hop_list_tmp = NULL;
103   struct neighbor_2_list_entry *two_hop_list = NULL;
104   struct neighbor_entry        *dup_neighbor;
105   struct neighbor_2_entry      *two_hop_neighbor = NULL;
106
107
108   for(index=0;index<HASHSIZE;index++)
109     {
110
111       for(two_hop_neighbor = two_hop_neighbortable[index].next;
112           two_hop_neighbor != &two_hop_neighbortable[index];
113           two_hop_neighbor = two_hop_neighbor->next)
114         {
115           
116           //two_hop_neighbor->neighbor_2_state=0;
117           //two_hop_neighbor->mpr_covered_count = 0;
118           
119           dup_neighbor = olsr_lookup_neighbor_table(&two_hop_neighbor->neighbor_2_addr);
120           
121           if((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM))
122             {
123               
124               //OLSR_PRINTF(1, "(1)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&two_hop_neighbor->neighbor_2_addr))
125
126               continue;
127             }
128           
129           if(two_hop_neighbor->neighbor_2_pointer == 1)
130             {
131               if((two_hop_neighbor->neighbor_2_nblist.next->neighbor->willingness == willingness) &&
132                  (two_hop_neighbor->neighbor_2_nblist.next->neighbor->status == SYM))
133                 {
134                   two_hop_list_tmp = olsr_malloc(sizeof(struct neighbor_2_list_entry), "MPR two hop list");
135
136                   //OLSR_PRINTF(1, "ONE LINK ADDING %s\n", olsr_ip_to_string(&two_hop_neighbor->neighbor_2_addr))
137
138                   /* Only queue one way here */           
139                   two_hop_list_tmp->neighbor_2 = two_hop_neighbor;
140                   
141                   two_hop_list_tmp->next = two_hop_list;
142                   
143                   two_hop_list= two_hop_list_tmp;
144                 }
145             }
146           
147         }
148       
149     }
150   
151   return(two_hop_list_tmp);
152 }
153   
154
155
156
157
158
159 /**
160  *This function processes the chosen MPRs and updates the counters
161  *used in calculations
162  */
163 static int
164 olsr_chosen_mpr(struct neighbor_entry *one_hop_neighbor, olsr_u16_t *two_hop_covered_count)
165 {
166   struct neighbor_list_entry   *the_one_hop_list;
167   struct neighbor_2_list_entry *second_hop_entries; 
168   struct neighbor_entry        *dup_neighbor;
169   olsr_u16_t                   count;
170   
171   count = *two_hop_covered_count;
172
173   OLSR_PRINTF(1, "Setting %s as MPR\n", olsr_ip_to_string(&one_hop_neighbor->neighbor_main_addr))
174
175   //printf("PRE COUNT: %d\n\n", count);
176
177   one_hop_neighbor->is_mpr = OLSR_TRUE; //NBS_MPR;
178   
179   for(second_hop_entries = one_hop_neighbor->neighbor_2_list.next;
180       second_hop_entries != &one_hop_neighbor->neighbor_2_list;
181       second_hop_entries = second_hop_entries->next)
182     {
183       dup_neighbor = olsr_lookup_neighbor_table(&second_hop_entries->neighbor_2->neighbor_2_addr);
184
185       if((dup_neighbor != NULL) && (dup_neighbor->status == SYM))
186         {
187           //OLSR_PRINTF(7, "(2)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&second_hop_entries->neighbor_2->neighbor_2_addr))
188           continue;
189         }
190
191       //      if(!second_hop_entries->neighbor_2->neighbor_2_state)
192       //if(second_hop_entries->neighbor_2->mpr_covered_count < olsr_cnf->mpr_coverage)
193       //{
194           /*
195             Now the neighbor is covered by this mpr
196           */
197           second_hop_entries->neighbor_2->mpr_covered_count++;
198           the_one_hop_list = second_hop_entries->neighbor_2->neighbor_2_nblist.next;
199
200           //OLSR_PRINTF(1, "[%s](%x) has coverage %d\n", olsr_ip_to_string(&second_hop_entries->neighbor_2->neighbor_2_addr), second_hop_entries->neighbor_2, second_hop_entries->neighbor_2->mpr_covered_count)
201
202           if(second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
203              count++;
204                       
205           while(the_one_hop_list != &second_hop_entries->neighbor_2->neighbor_2_nblist)
206             {
207               
208               if((the_one_hop_list->neighbor->status == SYM))
209                 {
210                   if(second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
211                     {
212                       the_one_hop_list->neighbor->neighbor_2_nocov--;
213                     }
214                 }
215               the_one_hop_list = the_one_hop_list->next;
216             }
217           
218           //}
219     }
220
221   //printf("POST COUNT %d\n\n", count);
222   
223   *two_hop_covered_count = count;
224   return count;
225
226 }
227
228
229 /**
230  *Find the neighbor that covers the most 2 hop neighbors
231  *with a given willingness
232  *
233  *@param willingness the willingness of the neighbor
234  *
235  *@return a pointer to the neighbor_entry struct
236  */
237 static struct neighbor_entry *
238 olsr_find_maximum_covered(int willingness)
239 {
240   olsr_u16_t                  maximum;
241   olsr_u8_t                   index;
242   struct neighbor_entry       *a_neighbor;
243   struct neighbor_entry       *mpr_candidate=NULL;
244    
245   maximum = 0;
246   
247   for (index=0;index<HASHSIZE;index++)
248     {
249       for(a_neighbor = neighbortable[index].next;
250           a_neighbor != &neighbortable[index];
251           a_neighbor = a_neighbor->next)
252         {
253           /*      
254           printf("[%s] nocov: %d mpr: %d will: %d max: %d\n\n", 
255                  olsr_ip_to_string(&a_neighbor->neighbor_main_addr), 
256                  a_neighbor->neighbor_2_nocov,
257                  a_neighbor->is_mpr,
258                  a_neighbor->willingness,
259                  maximum);
260           */
261           if((!a_neighbor->is_mpr) &&
262              (a_neighbor->willingness == willingness) && 
263              (maximum < a_neighbor->neighbor_2_nocov))
264             {
265               //printf("ADDING\n");
266               maximum = a_neighbor->neighbor_2_nocov;
267               mpr_candidate = a_neighbor;
268             }
269         }
270     }
271   return mpr_candidate;
272 }
273
274
275 /**
276  *Remove all MPR registrations
277  */
278 static void
279 olsr_clear_mprs()
280 {
281   olsr_u32_t index;
282   struct neighbor_entry   *a_neighbor;
283   struct neighbor_2_list_entry *two_hop_list;
284   
285   for (index=0;index<HASHSIZE;index++)
286     {
287       for(a_neighbor = neighbortable[index].next;
288           a_neighbor != &neighbortable[index];
289           a_neighbor = a_neighbor->next)
290         {
291           /* Clear MPR selection */
292           if(a_neighbor->is_mpr)
293             {
294               a_neighbor->was_mpr = OLSR_TRUE;
295               a_neighbor->is_mpr = OLSR_FALSE;
296             }
297
298           /* Clear two hop neighbors coverage count */
299           for(two_hop_list = a_neighbor->neighbor_2_list.next;
300               two_hop_list != &a_neighbor->neighbor_2_list;
301               two_hop_list = two_hop_list->next)
302             {
303               two_hop_list->neighbor_2->mpr_covered_count = 0;
304             }
305         }
306     }
307
308 }
309
310
311 /**
312  *Check for changes in the MPR set
313  *
314  *@return 1 if changes occured 0 if not
315  */
316 static int
317 olsr_check_mpr_changes()
318 {
319   olsr_u32_t index;
320   struct neighbor_entry       *a_neighbor;
321   int retval;
322
323   retval = 0;
324   
325   for (index=0;index<HASHSIZE;index++)
326     {
327       for(a_neighbor = neighbortable[index].next;
328           a_neighbor != &neighbortable[index];
329           a_neighbor = a_neighbor->next)
330         {
331           if(a_neighbor->was_mpr)
332             {
333               a_neighbor->was_mpr = OLSR_FALSE;
334               if(!a_neighbor->is_mpr)
335                 retval = 1;
336             }
337         }
338     }
339
340   return retval;
341 }
342
343
344 /**
345  *Clears out proccess registration
346  *on two hop neighbors
347  */
348 static void
349 olsr_clear_two_hop_processed()
350 {
351   struct neighbor_2_entry  *neighbor_2;
352   int index;
353   
354   for(index=0;index<HASHSIZE;index++)
355     {
356       for(neighbor_2 = two_hop_neighbortable[index].next;
357           neighbor_2 != &two_hop_neighbortable[index];
358           neighbor_2 = neighbor_2->next)
359         {
360           /* Clear */
361           neighbor_2->processed = 0;
362         }
363     }
364
365 }
366
367
368 /**
369  *This function calculates the number of two hop neighbors
370  */
371 static olsr_u16_t
372 olsr_calculate_two_hop_neighbors()
373 {
374   olsr_u8_t                    index;
375   struct neighbor_entry        *a_neighbor, *dup_neighbor;
376   olsr_u16_t                   count, n_count, sum;
377   struct neighbor_2_list_entry *twohop_neighbors;
378   
379   //dup_neighbor = NULL;
380   
381   n_count = 0;
382   count = 0;
383   sum = 0;
384
385   /* Clear 2 hop neighs */
386   olsr_clear_two_hop_processed();
387
388   for(index=0;index<HASHSIZE;index++)
389     {
390       for(a_neighbor = neighbortable[index].next;
391           a_neighbor != &neighbortable[index];
392           a_neighbor = a_neighbor->next)
393         { 
394           count = 0;
395           n_count = 0;
396           
397           if(a_neighbor->status == NOT_SYM)
398             {       
399               a_neighbor->neighbor_2_nocov = count;
400               continue;
401             }
402
403           for(twohop_neighbors = a_neighbor->neighbor_2_list.next;
404               twohop_neighbors != &a_neighbor->neighbor_2_list;
405               twohop_neighbors = twohop_neighbors->next)
406             {
407               //printf("\tChecking %s....", olsr_ip_to_string(&twohop_neighbors->neighbor_2->neighbor_2_addr));
408               
409               dup_neighbor = olsr_lookup_neighbor_table(&twohop_neighbors->neighbor_2->neighbor_2_addr);
410               
411               if((dup_neighbor == NULL) || (dup_neighbor->status != SYM))
412                 {
413                   n_count++;
414                   if(!twohop_neighbors->neighbor_2->processed)
415                     {
416                       count++;
417                       twohop_neighbors->neighbor_2->processed = 1;
418                     }
419                 }
420             }
421           a_neighbor->neighbor_2_nocov = n_count;
422           
423           /* Add the two hop count */
424           sum += count;
425         }
426     }
427   
428   OLSR_PRINTF(3, "Two hop neighbors: %d\n", sum)
429   return sum;
430 }
431
432
433
434
435 /**
436  * Adds all nodes with willingness set to WILL_ALWAYS
437  */
438 static olsr_u16_t
439 add_will_always_nodes()
440 {
441
442   olsr_u8_t                    index;
443   struct neighbor_entry        *a_neighbor;
444   olsr_u16_t                   count;
445
446   count = 0;
447
448   //printf("\nAdding WILL ALWAYS nodes....\n");
449
450   for(index=0;index<HASHSIZE;index++)
451     {
452       for(a_neighbor = neighbortable[index].next;
453           a_neighbor != &neighbortable[index];
454           a_neighbor = a_neighbor->next)
455         { 
456           if((a_neighbor->status == NOT_SYM) || (a_neighbor->willingness != WILL_ALWAYS))
457             continue;
458
459           olsr_chosen_mpr(a_neighbor, &count); 
460
461           OLSR_PRINTF(3, "Adding WILL_ALWAYS: %s\n", olsr_ip_to_string(&a_neighbor->neighbor_main_addr))
462
463         }
464     }
465   
466   //OLSR_PRINTF(1, "Count: %d\n", count)
467   return count;
468 }
469
470 /**
471  *This function calculates the mpr neighbors
472  *@return nada
473  */
474 void
475 olsr_calculate_mpr()     
476 {
477   
478   olsr_u16_t                   two_hop_covered_count=0;
479   olsr_u16_t                   two_hop_count=0;  
480   struct neighbor_2_list_entry *two_hop_list=NULL;
481   struct neighbor_2_list_entry *tmp;
482   struct neighbor_entry        *mprs; 
483   int i;
484
485   OLSR_PRINTF(3, "\n**RECALCULATING MPR**\n\n")
486
487   olsr_clear_mprs();
488
489   two_hop_count = olsr_calculate_two_hop_neighbors();
490
491   two_hop_covered_count += add_will_always_nodes();
492
493   /*
494    *Calculate MPRs based on WILLINGNESS
495    */
496
497   for(i = WILL_ALWAYS - 1; i > WILL_NEVER; i--)
498     {
499       two_hop_list = olsr_find_2_hop_neighbors_with_1_link(i);
500
501       while(two_hop_list != NULL)
502         {
503           //printf("CHOSEN FROM 1 LINK\n");
504           if(!two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor->is_mpr)
505             olsr_chosen_mpr(two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor, &two_hop_covered_count); 
506           tmp = two_hop_list;
507           two_hop_list = two_hop_list->next;;
508           free(tmp);
509         }
510       
511       if(two_hop_covered_count >= two_hop_count)
512         {
513           i = WILL_NEVER;
514           break;
515         }
516
517       //printf("two hop covered count: %d\n", two_hop_covered_count);
518    
519       while((mprs = olsr_find_maximum_covered(i)) != NULL)
520         {
521           //printf("CHOSEN FROM MAXCOV\n");
522           olsr_chosen_mpr(mprs,&two_hop_covered_count);
523
524           if(two_hop_covered_count >= two_hop_count)
525             {
526               i = WILL_NEVER;
527               break;
528             }
529
530         }
531     }
532   
533   /*
534     increment the mpr sequence number
535   */
536   //neighbortable.neighbor_mpr_seq++;
537
538   /* Optimize selection */
539   olsr_optimize_mpr_set();
540
541   if(olsr_check_mpr_changes())
542     {
543       OLSR_PRINTF(3, "CHANGES IN MPR SET\n")
544       if(olsr_cnf->tc_redundancy > 0)
545         signal_link_changes(OLSR_TRUE);
546     }
547
548 }
549
550 /**
551  *Optimize MPR set by removing all entries
552  *where all 2 hop neighbors actually is
553  *covered by enough MPRs already
554  *Described in RFC3626 section 8.3.1
555  *point 5
556  *
557  *@return nada
558  */
559 static void
560 olsr_optimize_mpr_set()
561 {
562   int i, remove, index;
563   struct neighbor_2_list_entry *two_hop_list;
564   struct neighbor_entry *a_neighbor, *dup_neighbor;
565
566   //printf("\n**MPR OPTIMIZING**\n\n");
567
568   for(i = WILL_NEVER + 1; i < WILL_ALWAYS; i++)
569     {
570
571       for(index=0;index<HASHSIZE;index++)
572         {
573
574           for(a_neighbor = neighbortable[index].next;
575               a_neighbor != &neighbortable[index];
576               a_neighbor = a_neighbor->next)
577             {
578               
579               if(a_neighbor->willingness != i)
580                 continue;
581               
582               if(a_neighbor->is_mpr)
583                 {
584                   //printf("\tChecking %s\n", olsr_ip_to_string(&a_neighbor->neighbor_main_addr));
585                   remove = 1;
586
587                   for(two_hop_list = a_neighbor->neighbor_2_list.next;
588                       two_hop_list != &a_neighbor->neighbor_2_list;
589                       two_hop_list = two_hop_list->next)
590                     {
591                       
592                       dup_neighbor = olsr_lookup_neighbor_table(&two_hop_list->neighbor_2->neighbor_2_addr);
593                       
594                       if((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM))
595                         continue;
596                       
597                       //printf("\t[%s] coverage %d\n", olsr_ip_to_string(&two_hop_list->neighbor_2->neighbor_2_addr), two_hop_list->neighbor_2->mpr_covered_count);
598                       /* Do not remove if we find a entry which need this MPR */
599                       if(two_hop_list->neighbor_2->mpr_covered_count <= olsr_cnf->mpr_coverage)
600                         remove = 0;
601                       
602                     }
603                   if(remove)
604                     {
605                       OLSR_PRINTF(3, "MPR OPTIMIZE: removiong mpr %s\n\n", olsr_ip_to_string(&a_neighbor->neighbor_main_addr))
606                       a_neighbor->is_mpr = OLSR_FALSE;
607                     }
608
609
610                 }
611             }
612           
613         }
614
615
616     }
617
618 }
619
620
621
622 void
623 olsr_print_mpr_set()
624 {
625   int                   index;
626   struct neighbor_entry *a_neighbor;
627
628   OLSR_PRINTF(1, "MPR SET: ")
629
630   for(index=0;index<HASHSIZE;index++)
631     {
632       for(a_neighbor = neighbortable[index].next;
633           a_neighbor != &neighbortable[index];
634           a_neighbor = a_neighbor->next)
635         { 
636           
637           /* 
638            * Remove MPR settings
639            */
640           if(a_neighbor->is_mpr)
641             OLSR_PRINTF(1, "[%s] ", olsr_ip_to_string(&a_neighbor->neighbor_main_addr))
642         }
643     }
644
645   OLSR_PRINTF(1, "\n")
646
647 }