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