* killed lots of #ifdef ... #endif which make the source quite unreadable
[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  */
40
41 #include "ipcalc.h"
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 #include "net_olsr.h"
49
50 /* Begin:
51  * Prototypes for internal functions 
52  */
53
54 static olsr_u16_t
55 add_will_always_nodes(void);
56
57 static void
58 olsr_optimize_mpr_set(void);
59
60 static void
61 olsr_clear_mprs(void);
62
63 static void
64 olsr_clear_two_hop_processed(void);
65
66 static struct neighbor_entry *
67 olsr_find_maximum_covered(int);
68
69 static olsr_u16_t
70 olsr_calculate_two_hop_neighbors(void);
71
72 static int
73 olsr_check_mpr_changes(void);
74
75 static int
76 olsr_chosen_mpr(struct neighbor_entry *, olsr_u16_t *);
77
78 static struct neighbor_2_list_entry *
79 olsr_find_2_hop_neighbors_with_1_link(int);
80
81
82 /* End:
83  * Prototypes for internal functions 
84  */
85
86
87
88 /**
89  *Find all 2 hop neighbors with 1 link
90  *connecting them to us trough neighbors
91  *with a given willingness.
92  *
93  *@param willingness the willigness of the neighbors
94  *
95  *@return a linked list of allocated neighbor_2_list_entry structures
96  */
97 static struct neighbor_2_list_entry *
98 olsr_find_2_hop_neighbors_with_1_link(int willingness)
99 {
100   
101  
102   olsr_u8_t                    index;
103   struct neighbor_2_list_entry *two_hop_list_tmp = NULL;
104   struct neighbor_2_list_entry *two_hop_list = NULL;
105   struct neighbor_entry        *dup_neighbor;
106   struct neighbor_2_entry      *two_hop_neighbor = NULL;
107
108
109   for(index=0;index<HASHSIZE;index++)
110     {
111
112       for(two_hop_neighbor = two_hop_neighbortable[index].next;
113           two_hop_neighbor != &two_hop_neighbortable[index];
114           two_hop_neighbor = two_hop_neighbor->next)
115         {
116           
117           //two_hop_neighbor->neighbor_2_state=0;
118           //two_hop_neighbor->mpr_covered_count = 0;
119           
120           dup_neighbor = olsr_lookup_neighbor_table(&two_hop_neighbor->neighbor_2_addr);
121           
122           if((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM))
123             {
124               
125               //OLSR_PRINTF(1, "(1)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
126
127               continue;
128             }
129           
130           if(two_hop_neighbor->neighbor_2_pointer == 1)
131             {
132               if((two_hop_neighbor->neighbor_2_nblist.next->neighbor->willingness == willingness) &&
133                  (two_hop_neighbor->neighbor_2_nblist.next->neighbor->status == SYM))
134                 {
135                   two_hop_list_tmp = olsr_malloc(sizeof(struct neighbor_2_list_entry), "MPR two hop list");
136
137                   //OLSR_PRINTF(1, "ONE LINK ADDING %s\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
138
139                   /* Only queue one way here */           
140                   two_hop_list_tmp->neighbor_2 = two_hop_neighbor;
141                   
142                   two_hop_list_tmp->next = two_hop_list;
143                   
144                   two_hop_list= two_hop_list_tmp;
145                 }
146             }
147           
148         }
149       
150     }
151   
152   return(two_hop_list_tmp);
153 }
154   
155
156
157
158
159
160 /**
161  *This function processes the chosen MPRs and updates the counters
162  *used in calculations
163  */
164 static int
165 olsr_chosen_mpr(struct neighbor_entry *one_hop_neighbor, olsr_u16_t *two_hop_covered_count)
166 {
167   struct neighbor_list_entry   *the_one_hop_list;
168   struct neighbor_2_list_entry *second_hop_entries; 
169   struct neighbor_entry        *dup_neighbor;
170   olsr_u16_t                   count;
171   struct ipaddr_str            buf;
172   count = *two_hop_covered_count;
173
174   OLSR_PRINTF(1, "Setting %s as MPR\n", olsr_ip_to_string(&buf, &one_hop_neighbor->neighbor_main_addr));
175
176   //printf("PRE COUNT: %d\n\n", count);
177
178   one_hop_neighbor->is_mpr = OLSR_TRUE; //NBS_MPR;
179   
180   for(second_hop_entries = one_hop_neighbor->neighbor_2_list.next;
181       second_hop_entries != &one_hop_neighbor->neighbor_2_list;
182       second_hop_entries = second_hop_entries->next)
183     {
184       dup_neighbor = olsr_lookup_neighbor_table(&second_hop_entries->neighbor_2->neighbor_2_addr);
185
186       if((dup_neighbor != NULL) && (dup_neighbor->status == SYM))
187         {
188           //OLSR_PRINTF(7, "(2)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&buf, &second_hop_entries->neighbor_2->neighbor_2_addr));
189           continue;
190         }
191
192       //      if(!second_hop_entries->neighbor_2->neighbor_2_state)
193       //if(second_hop_entries->neighbor_2->mpr_covered_count < olsr_cnf->mpr_coverage)
194       //{
195           /*
196             Now the neighbor is covered by this mpr
197           */
198           second_hop_entries->neighbor_2->mpr_covered_count++;
199           the_one_hop_list = second_hop_entries->neighbor_2->neighbor_2_nblist.next;
200
201           //OLSR_PRINTF(1, "[%s](%x) has coverage %d\n", olsr_ip_to_string(&buf, &second_hop_entries->neighbor_2->neighbor_2_addr), second_hop_entries->neighbor_2, second_hop_entries->neighbor_2->mpr_covered_count);
202
203           if(second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
204              count++;
205                       
206           while(the_one_hop_list != &second_hop_entries->neighbor_2->neighbor_2_nblist)
207             {
208               
209               if((the_one_hop_list->neighbor->status == SYM))
210                 {
211                   if(second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
212                     {
213                       the_one_hop_list->neighbor->neighbor_2_nocov--;
214                     }
215                 }
216               the_one_hop_list = the_one_hop_list->next;
217             }
218           
219           //}
220     }
221
222   //printf("POST COUNT %d\n\n", count);
223   
224   *two_hop_covered_count = count;
225   return count;
226
227 }
228
229
230 /**
231  *Find the neighbor that covers the most 2 hop neighbors
232  *with a given willingness
233  *
234  *@param willingness the willingness of the neighbor
235  *
236  *@return a pointer to the neighbor_entry struct
237  */
238 static struct neighbor_entry *
239 olsr_find_maximum_covered(int willingness)
240 {
241   olsr_u16_t                  maximum;
242   struct neighbor_entry       *a_neighbor;
243   struct neighbor_entry       *mpr_candidate = NULL;
244    
245   maximum = 0;
246
247   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
248
249 #if 0
250       printf("[%s] nocov: %d mpr: %d will: %d max: %d\n\n", 
251              olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr), 
252              a_neighbor->neighbor_2_nocov,
253              a_neighbor->is_mpr,
254              a_neighbor->willingness,
255              maximum);
256 #endif
257
258       if ((!a_neighbor->is_mpr) &&
259           (a_neighbor->willingness == willingness) && 
260           (maximum < a_neighbor->neighbor_2_nocov)) {
261
262           maximum = a_neighbor->neighbor_2_nocov;
263           mpr_candidate = a_neighbor;
264       }
265   } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
266
267   return mpr_candidate;
268 }
269
270
271 /**
272  *Remove all MPR registrations
273  */
274 static void
275 olsr_clear_mprs(void)
276 {
277   struct neighbor_entry *a_neighbor;
278   struct neighbor_2_list_entry *two_hop_list;
279
280   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
281
282     /* Clear MPR selection. */
283     if (a_neighbor->is_mpr) {
284       a_neighbor->was_mpr = OLSR_TRUE;
285       a_neighbor->is_mpr = OLSR_FALSE;
286     }
287
288     /* Clear two hop neighbors coverage count/ */
289     for (two_hop_list = a_neighbor->neighbor_2_list.next;
290          two_hop_list != &a_neighbor->neighbor_2_list;
291          two_hop_list = two_hop_list->next) {
292       two_hop_list->neighbor_2->mpr_covered_count = 0;
293     }
294
295   } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
296 }
297
298
299 /**
300  *Check for changes in the MPR set
301  *
302  *@return 1 if changes occured 0 if not
303  */
304 static int
305 olsr_check_mpr_changes(void)
306 {
307   struct neighbor_entry *a_neighbor;
308   int retval;
309
310   retval = 0;
311   
312   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
313
314     if (a_neighbor->was_mpr) {
315       a_neighbor->was_mpr = OLSR_FALSE;
316
317       if (!a_neighbor->is_mpr) {
318         retval = 1;
319       }
320     }
321   } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
322
323   return retval;
324 }
325
326
327 /**
328  *Clears out proccess registration
329  *on two hop neighbors
330  */
331 static void
332 olsr_clear_two_hop_processed(void)
333 {
334   int index;
335   
336   for(index=0;index<HASHSIZE;index++)
337     {
338       struct neighbor_2_entry  *neighbor_2;
339       for(neighbor_2 = two_hop_neighbortable[index].next;
340           neighbor_2 != &two_hop_neighbortable[index];
341           neighbor_2 = neighbor_2->next)
342         {
343           /* Clear */
344           neighbor_2->processed = 0;
345         }
346     }
347
348 }
349
350
351 /**
352  *This function calculates the number of two hop neighbors
353  */
354 static olsr_u16_t
355 olsr_calculate_two_hop_neighbors(void)
356 {
357   struct neighbor_entry *a_neighbor, *dup_neighbor;
358   struct neighbor_2_list_entry *twohop_neighbors;
359   olsr_u16_t count = 0;
360   olsr_u16_t n_count = 0;
361   olsr_u16_t sum = 0;
362   
363   /* Clear 2 hop neighs */
364   olsr_clear_two_hop_processed();
365
366   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
367
368     if (a_neighbor->status == NOT_SYM) {            
369       a_neighbor->neighbor_2_nocov = count;
370       continue;
371     }
372
373     for (twohop_neighbors = a_neighbor->neighbor_2_list.next;
374          twohop_neighbors != &a_neighbor->neighbor_2_list;
375          twohop_neighbors = twohop_neighbors->next) {
376
377       dup_neighbor = olsr_lookup_neighbor_table(&twohop_neighbors->neighbor_2->neighbor_2_addr);
378               
379       if ((dup_neighbor == NULL) || (dup_neighbor->status != SYM)) {
380         n_count++;
381         if (!twohop_neighbors->neighbor_2->processed) {
382           count++;
383           twohop_neighbors->neighbor_2->processed = 1;
384         }
385       }
386     }
387     a_neighbor->neighbor_2_nocov = n_count;
388           
389     /* Add the two hop count */
390     sum += count;
391
392   } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
393   
394   OLSR_PRINTF(3, "Two hop neighbors: %d\n", sum);
395   return sum;
396 }
397
398
399
400
401 /**
402  * Adds all nodes with willingness set to WILL_ALWAYS
403  */
404 static olsr_u16_t
405 add_will_always_nodes(void)
406 {
407   struct neighbor_entry *a_neighbor;
408   olsr_u16_t count = 0;
409
410 #if 0
411   printf("\nAdding WILL ALWAYS nodes....\n");
412 #endif
413
414   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
415     struct ipaddr_str buf;
416     if ((a_neighbor->status == NOT_SYM) ||
417         (a_neighbor->willingness != WILL_ALWAYS)) {
418       continue;
419     }
420     olsr_chosen_mpr(a_neighbor, &count); 
421
422     OLSR_PRINTF(3, "Adding WILL_ALWAYS: %s\n",
423                 olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
424
425   } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
426
427 #if 0  
428   OLSR_PRINTF(1, "Count: %d\n", count);
429 #endif
430   return count;
431 }
432
433 /**
434  *This function calculates the mpr neighbors
435  *@return nada
436  */
437 void
438 olsr_calculate_mpr(void)     
439 {  
440   olsr_u16_t two_hop_covered_count;
441   olsr_u16_t two_hop_count;
442   int i;
443
444   OLSR_PRINTF(3, "\n**RECALCULATING MPR**\n\n");
445
446   olsr_clear_mprs();
447   two_hop_count = olsr_calculate_two_hop_neighbors();
448   two_hop_covered_count = add_will_always_nodes();
449
450   /*
451    *Calculate MPRs based on WILLINGNESS
452    */
453
454   for(i = WILL_ALWAYS - 1; i > WILL_NEVER; i--)
455     {
456       struct neighbor_entry        *mprs; 
457       struct neighbor_2_list_entry *two_hop_list = olsr_find_2_hop_neighbors_with_1_link(i);
458
459       while(two_hop_list != NULL)
460         {
461           struct neighbor_2_list_entry *tmp;
462           //printf("CHOSEN FROM 1 LINK\n");
463           if(!two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor->is_mpr)
464             olsr_chosen_mpr(two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor, &two_hop_covered_count); 
465           tmp = two_hop_list;
466           two_hop_list = two_hop_list->next;;
467           free(tmp);
468         }
469       
470       if(two_hop_covered_count >= two_hop_count)
471         {
472           i = WILL_NEVER;
473           break;
474         }
475
476       //printf("two hop covered count: %d\n", two_hop_covered_count);
477    
478       while((mprs = olsr_find_maximum_covered(i)) != NULL)
479         {
480           //printf("CHOSEN FROM MAXCOV\n");
481           olsr_chosen_mpr(mprs,&two_hop_covered_count);
482
483           if(two_hop_covered_count >= two_hop_count)
484             {
485               i = WILL_NEVER;
486               break;
487             }
488
489         }
490     }
491   
492   /*
493     increment the mpr sequence number
494   */
495   //neighbortable.neighbor_mpr_seq++;
496
497   /* Optimize selection */
498   olsr_optimize_mpr_set();
499
500   if(olsr_check_mpr_changes())
501     {
502       OLSR_PRINTF(3, "CHANGES IN MPR SET\n");
503       if(olsr_cnf->tc_redundancy > 0)
504         signal_link_changes(OLSR_TRUE);
505     }
506
507 }
508
509 /**
510  *Optimize MPR set by removing all entries
511  *where all 2 hop neighbors actually is
512  *covered by enough MPRs already
513  *Described in RFC3626 section 8.3.1
514  *point 5
515  *
516  *@return nada
517  */
518 static void
519 olsr_optimize_mpr_set(void)
520 {
521   struct neighbor_entry *a_neighbor, *dup_neighbor;
522   struct neighbor_2_list_entry *two_hop_list;
523   int i, remove;
524
525 #if 0
526   printf("\n**MPR OPTIMIZING**\n\n");
527 #endif
528
529   for(i = WILL_NEVER + 1; i < WILL_ALWAYS; i++) {
530
531     OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
532               
533       if (a_neighbor->willingness != i) {
534         continue;
535       }
536               
537       if (a_neighbor->is_mpr) {
538         remove = 1;
539
540         for (two_hop_list = a_neighbor->neighbor_2_list.next;
541              two_hop_list != &a_neighbor->neighbor_2_list;
542              two_hop_list = two_hop_list->next) {
543                       
544           dup_neighbor = olsr_lookup_neighbor_table(&two_hop_list->neighbor_2->neighbor_2_addr);
545                       
546           if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
547             continue;
548           }
549                       
550           //printf("\t[%s] coverage %d\n", olsr_ip_to_string(&buf, &two_hop_list->neighbor_2->neighbor_2_addr), two_hop_list->neighbor_2->mpr_covered_count);
551           /* Do not remove if we find a entry which need this MPR */
552           if (two_hop_list->neighbor_2->mpr_covered_count <= olsr_cnf->mpr_coverage) {
553             remove = 0;
554           }      
555         }
556
557         if (remove) {
558           struct ipaddr_str buf;
559           OLSR_PRINTF(3, "MPR OPTIMIZE: removiong mpr %s\n\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
560           a_neighbor->is_mpr = OLSR_FALSE;
561         }
562       }
563     } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
564   }
565 }
566
567 void
568 olsr_print_mpr_set(void)
569 {
570 #ifndef NODEBUG
571   /* The whole function makes no sense without it. */
572   struct neighbor_entry *a_neighbor;
573
574   OLSR_PRINTF(1, "MPR SET: ");
575
576   OLSR_FOR_ALL_NBR_ENTRIES(a_neighbor) {
577
578     /* 
579      * Remove MPR settings
580      */
581     if (a_neighbor->is_mpr) {
582       struct ipaddr_str buf;
583       OLSR_PRINTF(1, "[%s] ", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
584     }
585   } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
586
587   OLSR_PRINTF(1, "\n");
588 #endif
589 }
590
591 /*
592  * Local Variables:
593  * c-basic-offset: 2
594  * End:
595  */