FIX: ignore UNSPEC_LINKS during MPR lookup
[olsrd.git] / src / process_package.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 "process_package.h"
43 #include "link_set.h"
44 #include "hna_set.h"
45 #include "two_hop_neighbor_table.h"
46 #include "neighbor_table.h"
47 #include "mpr_selector_set.h"
48 #include "mid_set.h"
49 #include "olsr.h"
50 #include "parser.h"
51 #include "olsr_logging.h"
52
53 static bool olsr_input_hello(union olsr_message *ser, struct interface *inif, union olsr_ip_addr *from);
54
55 static void process_message_neighbors(struct neighbor_entry *, const struct lq_hello_message *);
56
57 static void linking_this_2_entries(struct neighbor_entry *, struct neighbor_2_entry *, olsr_reltime);
58
59 static bool lookup_mpr_status(const struct lq_hello_message *, const struct interface *);
60
61 static void hello_tap(struct lq_hello_message *, struct interface *, const union olsr_ip_addr *);
62
63
64 /**
65  * Processes an list of neighbors from an incoming HELLO message.
66  * @param neighbor the neighbor who sent the message.
67  * @param message the HELLO message
68  * @return nada
69  */
70 static void
71 process_message_neighbors(struct neighbor_entry *neighbor, const struct lq_hello_message *message)
72 {
73   struct lq_hello_neighbor *message_neighbors;
74   olsr_linkcost first_hop_pathcost;
75   struct link_entry *lnk;
76
77   for (message_neighbors = message->neigh; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
78 #if !defined REMOVE_LOG_DEBUG
79     struct ipaddr_str buf;
80 #endif
81     union olsr_ip_addr *neigh_addr;
82
83     /*
84      * check all interfaces
85      * so that we don't add ourselves to the
86      * 2 hop list
87      * IMPORTANT!
88      */
89     if (if_ifwithaddr(&message_neighbors->addr) != NULL) {
90       continue;
91     }
92     /* Get the main address */
93     neigh_addr = olsr_lookup_main_addr_by_alias(&message_neighbors->addr);
94     if (neigh_addr != NULL) {
95       message_neighbors->addr = *neigh_addr;
96     }
97
98     if (message_neighbors->neigh_type == SYM_NEIGH || message_neighbors->neigh_type == MPR_NEIGH) {
99       struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->addr);
100       if (two_hop_neighbor_yet != NULL) {
101         struct neighbor_list_entry *walker;
102
103         /* Updating the holding time for this neighbor */
104         olsr_set_timer(&two_hop_neighbor_yet->nbr2_list_timer,
105                        message->comm.vtime, OLSR_NBR2_LIST_JITTER,
106                        OLSR_TIMER_ONESHOT, &olsr_expire_nbr2_list, two_hop_neighbor_yet, nbr2_list_timer_cookie->ci_id);
107
108         /*
109          * reset the path link quality here.
110          * The path link quality will be calculated in the second pass, below.
111          * Keep the saved_path_link_quality for reference.
112          */
113
114         /*
115          * loop through the one-hop neighbors that see this
116          * 'two_hop_neighbor'
117          */
118         for (walker = two_hop_neighbor_yet->neighbor_2->neighbor_2_nblist.next;
119              walker != &two_hop_neighbor_yet->neighbor_2->neighbor_2_nblist; walker = walker->next) {
120           /*
121            * have we found the one-hop neighbor that sent the
122            * HELLO message that we're current processing?
123            */
124           if (walker->neighbor == neighbor) {
125             walker->path_linkcost = LINK_COST_BROKEN;
126           }
127         }
128       } else {
129         struct neighbor_2_entry *two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&message_neighbors->addr);
130         if (two_hop_neighbor == NULL) {
131           OLSR_DEBUG(LOG_LINKS, "Adding 2 hop neighbor %s\n\n", olsr_ip_to_string(&buf, &message_neighbors->addr));
132           two_hop_neighbor = olsr_malloc(sizeof(*two_hop_neighbor), "Process HELLO");
133           two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist;
134           two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist;
135           two_hop_neighbor->neighbor_2_pointer = 0;
136           two_hop_neighbor->neighbor_2_addr = message_neighbors->addr;
137           olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
138         }
139         /*
140          * linking to this two_hop_neighbor entry
141          */
142         changes_neighborhood = true;
143         changes_topology = true;
144         linking_this_2_entries(neighbor, two_hop_neighbor, message->comm.vtime);
145       }
146     }
147   }
148
149   /* Second pass */
150   lnk = get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
151
152   if (!lnk) {
153     return;
154   }
155   /* calculate first hop path quality */
156   first_hop_pathcost = lnk->linkcost;
157   /*
158    *  Second pass : calculate the best 2-hop
159    * path costs to all the 2-hop neighbors indicated in the
160    * HELLO message. Since the same 2-hop neighbor may be listed
161    * more than once in the same HELLO message (each at a possibly
162    * different quality) we want to select only the best one, not just
163    * the last one listed in the HELLO message.
164    */
165   for (message_neighbors = message->neigh; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
166     if (if_ifwithaddr(&message_neighbors->addr) != NULL) {
167       continue;
168     }
169     if (message_neighbors->neigh_type == SYM_NEIGH || message_neighbors->neigh_type == MPR_NEIGH) {
170       struct neighbor_list_entry *walker;
171       struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->addr);
172
173       if (!two_hop_neighbor_yet) {
174         continue;
175       }
176
177       /*
178        *  loop through the one-hop neighbors that see this
179        * 'two_hop_neighbor_yet->neighbor_2'
180        */
181       for (walker = two_hop_neighbor_yet->neighbor_2->neighbor_2_nblist.next;
182            walker != &two_hop_neighbor_yet->neighbor_2->neighbor_2_nblist; walker = walker->next) {
183         /*
184          * have we found the one-hop neighbor that sent the
185          * HELLO message that we're current processing?
186          */
187         if (walker->neighbor == neighbor) {
188           // the link cost between the 1-hop neighbour and the
189           // 2-hop neighbour
190           olsr_linkcost new_second_hop_linkcost = message_neighbors->cost;
191
192           // the total cost for the route
193           // "us --- 1-hop --- 2-hop"
194           olsr_linkcost new_path_linkcost = first_hop_pathcost + new_second_hop_linkcost;
195
196           // Only copy the link quality if it is better than what we have
197           // for this 2-hop neighbor
198           if (new_path_linkcost < walker->path_linkcost) {
199             walker->second_hop_linkcost = new_second_hop_linkcost;
200             walker->path_linkcost = new_path_linkcost;
201
202             if (olsr_is_relevant_costchange(new_path_linkcost, walker->saved_path_linkcost)) {
203               walker->saved_path_linkcost = new_path_linkcost;
204
205               if (olsr_cnf->lq_dlimit > 0) {
206                 changes_neighborhood = true;
207                 changes_topology = true;
208               }
209             }
210           }
211         }
212       }
213     }
214   }
215 }
216
217 /**
218  * Links a one-hop neighbor with a 2-hop neighbor.
219  *
220  * @param neighbor the 1-hop neighbor
221  * @param two_hop_neighbor the 2-hop neighbor
222  * @return nada
223  */
224 static void
225 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
226 {
227   struct neighbor_list_entry *list_of_1_neighbors = olsr_malloc(sizeof(*list_of_1_neighbors), "Link entries 1");
228   struct neighbor_2_list_entry *list_of_2_neighbors = olsr_malloc(sizeof(*list_of_2_neighbors), "Link entries 2");
229
230   list_of_1_neighbors->neighbor = neighbor;
231   list_of_1_neighbors->path_linkcost = LINK_COST_BROKEN;
232   list_of_1_neighbors->saved_path_linkcost = LINK_COST_BROKEN;
233   list_of_1_neighbors->second_hop_linkcost = LINK_COST_BROKEN;
234
235   /* Queue */
236   two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
237   list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
238   two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
239   list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
240
241   list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
242   list_of_2_neighbors->nbr2_nbr = neighbor;     /* XXX refcount */
243   list_of_2_neighbors->nbr2_list_timer =
244     olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER,
245                      OLSR_TIMER_ONESHOT, &olsr_expire_nbr2_list, list_of_2_neighbors, nbr2_list_timer_cookie->ci_id);
246
247   /* Queue */
248   neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
249   list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
250   neighbor->neighbor_2_list.next = list_of_2_neighbors;
251   list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
252
253   /*increment the pointer counter */
254   two_hop_neighbor->neighbor_2_pointer++;
255 }
256
257 /**
258  * Check if a hello message states this node as a MPR.
259  *
260  * @param message the message to check
261  * @param n_link the buffer to put the link status in
262  *
263  * @return 1 if we are selected as MPR 0 if not
264  */
265 static bool
266 lookup_mpr_status(const struct lq_hello_message *message, const struct interface *in_if)
267 {
268   struct lq_hello_neighbor *neighbors;
269
270   for (neighbors = message->neigh; neighbors; neighbors = neighbors->next) {
271     if ( neighbors->link_type != UNSPEC_LINK
272         && (olsr_cnf->ip_version == AF_INET
273             ? ip4cmp(&neighbors->addr.v4, &in_if->ip_addr.v4) == 0
274             : ip6cmp(&neighbors->addr.v6, &in_if->int6_addr.sin6_addr) == 0)) {
275       return neighbors->link_type == SYM_LINK && neighbors->neigh_type == MPR_NEIGH ? true : false;
276     }
277   }
278   /* Not found */
279   return false;
280 }
281
282 /**
283  * Initializing the parser functions we are using
284  * For downwards compatibility reasons we also understand the non-LQ messages.
285  */
286 void
287 olsr_init_package_process(void)
288 {
289   olsr_parser_add_function(&olsr_input_hello, HELLO_MESSAGE);
290   olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
291   olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE);
292   olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
293   olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
294   olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
295 }
296
297 void
298 olsr_deinit_package_process(void)
299 {
300   olsr_parser_remove_function(&olsr_input_hello, HELLO_MESSAGE);
301   olsr_parser_remove_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
302   olsr_parser_remove_function(&olsr_input_tc, TC_MESSAGE);
303   olsr_parser_remove_function(&olsr_input_tc, LQ_TC_MESSAGE);
304   olsr_parser_remove_function(&olsr_input_mid, MID_MESSAGE);
305   olsr_parser_remove_function(&olsr_input_hna, HNA_MESSAGE);
306 }
307
308 static int
309 deserialize_hello(struct lq_hello_message *hello, const void *ser)
310 {
311   const unsigned char *limit;
312   uint8_t type;
313   uint16_t size;
314
315   const unsigned char *curr = ser;
316   pkt_get_u8(&curr, &type);
317   if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
318     /* No need to do anything more */
319     return 1;
320   }
321   pkt_get_reltime(&curr, &hello->comm.vtime);
322   pkt_get_u16(&curr, &size);
323   pkt_get_ipaddress(&curr, &hello->comm.orig);
324
325   pkt_get_u8(&curr, &hello->comm.ttl);
326   pkt_get_u8(&curr, &hello->comm.hops);
327   pkt_get_u16(&curr, &hello->comm.seqno);
328   pkt_ignore_u16(&curr);
329
330   pkt_get_reltime(&curr, &hello->htime);
331   pkt_get_u8(&curr, &hello->will);
332
333   hello->neigh = NULL;
334   limit = ((const unsigned char *)ser) + size;
335   while (curr < limit) {
336     const struct lq_hello_info_header *info_head = (const struct lq_hello_info_header *)curr;
337     const unsigned char *limit2 = curr + ntohs(info_head->size);
338
339     curr = (const unsigned char *)(info_head + 1);
340     while (curr < limit2) {
341       struct lq_hello_neighbor *neigh = olsr_malloc_lq_hello_neighbor();
342       pkt_get_ipaddress(&curr, &neigh->addr);
343
344       olsr_deserialize_hello_lq_pair(&curr, neigh);
345       neigh->link_type = EXTRACT_LINK(info_head->link_code);
346       neigh->neigh_type = EXTRACT_STATUS(info_head->link_code);
347
348       neigh->next = hello->neigh;
349       hello->neigh = neigh;
350     }
351   }
352   return 0;
353 }
354
355
356 static void
357 hello_tap(struct lq_hello_message *message, struct interface *in_if, const union olsr_ip_addr *from_addr)
358 {
359   /*
360    * Update link status
361    */
362   struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
363   struct lq_hello_neighbor *walker;
364   /* just in case our neighbor has changed its HELLO interval */
365   olsr_update_packet_loss_hello_int(lnk, message->htime);
366
367   /* find the input interface in the list of neighbor interfaces */
368   for (walker = message->neigh; walker != NULL; walker = walker->next) {
369     if (walker->link_type != UNSPEC_LINK && olsr_ipcmp(&walker->addr, &in_if->ip_addr) == 0) {
370       break;
371     }
372   }
373
374   /*
375    * memorize our neighbour's idea of the link quality, so that we
376    * know the link quality in both directions
377    *
378    * walker is NULL if there the current interface was not included in
379    * the message (or was included as an UNSPEC_LINK)
380    */
381   olsr_memorize_foreign_hello_lq(lnk, walker);
382
383   /* update packet loss for link quality calculation */
384   olsr_update_packet_loss(lnk);
385
386   /* Check if we are chosen as MPR */
387   if (lookup_mpr_status(message, in_if)) {
388     /* source_addr is always the main addr of a node! */
389     olsr_update_mprs_set(&message->comm.orig, message->comm.vtime);
390   }
391
392   /* Check willingness */
393   if (lnk->neighbor->willingness != message->will) {
394 #if !defined REMOVE_LOG_DEBUG
395     struct ipaddr_str buf;
396 #endif
397     OLSR_DEBUG(LOG_LINKS, "Willingness for %s changed from %d to %d - UPDATING\n",
398                olsr_ip_to_string(&buf, &lnk->neighbor->neighbor_main_addr), lnk->neighbor->willingness, message->will);
399     /*
400      *If willingness changed - recalculate
401      */
402     lnk->neighbor->willingness = message->will;
403     changes_neighborhood = true;
404     changes_topology = true;
405   }
406
407   /* Don't register neighbors of neighbors that announces WILL_NEVER */
408   if (lnk->neighbor->willingness != WILL_NEVER) {
409     process_message_neighbors(lnk->neighbor, message);
410   }
411
412   /* Process changes immedeatly in case of MPR updates */
413   olsr_process_changes();
414
415   destroy_lq_hello(message);
416 }
417
418 static bool
419 olsr_input_hello(union olsr_message *msg, struct interface *inif, union olsr_ip_addr *from)
420 {
421   struct lq_hello_message hello;
422
423   if (msg == NULL) {
424     return false;
425   }
426   if (deserialize_hello(&hello, msg) != 0) {
427     return false;
428   }
429   hello_tap(&hello, inif, from);
430
431   /* Do not forward hello messages */
432   return false;
433 }
434
435 /*
436  * Local Variables:
437  * c-basic-offset: 2
438  * indent-tabs-mode: nil
439  * End:
440  */