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