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