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