7e2ca33e02b7691a92470069e27a84be18c2d95f
[olsrd.git] / src / process_package.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright
13  *   notice, this list of conditions and the following disclaimer in
14  *   the documentation and/or other materials provided with the
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its
17  *   contributors may be used to endorse or promote products derived
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  */
40
41 #include "process_package.h"
42 #include "link_set.h"
43 #include "hysteresis.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
52 static void process_message_neighbors(struct neighbor_entry *,
53                                       const struct hello_message *);
54
55 static void linking_this_2_entries(struct neighbor_entry *,
56                                    struct neighbor_2_entry *,
57                                    olsr_reltime);
58
59 static olsr_bool lookup_mpr_status(const struct hello_message *,
60                                    const struct interface *);
61
62 static void hello_tap(struct hello_message *, struct interface *,
63                       const union olsr_ip_addr *);
64
65
66 /**
67  * Processes an list of neighbors from an incoming HELLO message.
68  * @param neighbor the neighbor who sent the message.
69  * @param message the HELLO message
70  * @return nada
71  */
72 static void
73 process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_message *message)
74 {
75   struct hello_neighbor *message_neighbors;
76
77   for (message_neighbors = message->neighbors;
78        message_neighbors != NULL;
79        message_neighbors = message_neighbors->next) {
80 #ifdef DEBUG
81     struct ipaddr_str buf;
82 #endif
83     union olsr_ip_addr *neigh_addr;
84
85     /*
86      * check all interfaces
87      * so that we don't add ourselves to the
88      * 2 hop list
89      * IMPORTANT!
90      */
91     if (if_ifwithaddr(&message_neighbors->address) != NULL) {
92         continue;
93     }
94     /* Get the main address */
95     neigh_addr = olsr_lookup_main_addr_by_alias(&message_neighbors->address);
96     if (neigh_addr != NULL) {
97       message_neighbors->address = *neigh_addr;
98     }
99
100     if (message_neighbors->status == SYM_NEIGH ||
101         message_neighbors->status == MPR_NEIGH) {
102       struct neighbor_2_list_entry *two_hop_neighbor_yet =
103         olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
104 #ifdef DEBUG
105       OLSR_PRINTF(7, "\tProcessing %s\n", olsr_ip_to_string(&buf, &message_neighbors->address));
106 #endif
107       if (two_hop_neighbor_yet != NULL) {
108         /* Updating the holding time for this neighbor */
109         olsr_set_timer(&two_hop_neighbor_yet->nbr2_list_timer,
110                        message->vtime, OLSR_NBR2_LIST_JITTER,
111                        OLSR_TIMER_ONESHOT, &olsr_expire_nbr2_list,
112                        two_hop_neighbor_yet, nbr2_list_timer_cookie->ci_id);
113
114         /*
115          * For link quality OLSR, reset the path link quality here.
116          * The path link quality will be calculated in the second pass, below.
117          * Keep the saved_path_link_quality for reference.
118          */
119         if (olsr_cnf->lq_level > 0) {
120           /*
121            * loop through the one-hop neighbors that see this
122            * 'two_hop_neighbor'
123            */
124           struct neighbor_list_entry *walker;
125           for (walker = two_hop_neighbor_yet->neighbor_2->neighbor_2_nblist.next;
126                walker != &two_hop_neighbor_yet->neighbor_2->neighbor_2_nblist;
127                walker = walker->next) {
128             /*
129              * have we found the one-hop neighbor that sent the
130              * HELLO message that we're current processing?
131              */
132
133             if (walker->neighbor == neighbor) {
134               walker->path_linkcost = LINK_COST_BROKEN;
135             }
136           }
137         }
138       } else {
139         struct neighbor_2_entry *two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
140         if (two_hop_neighbor == NULL) {
141 #ifdef DEBUG
142           OLSR_PRINTF(5,
143                       "Adding 2 hop neighbor %s\n\n",
144                       olsr_ip_to_string(&buf, &message_neighbors->address));
145 #endif
146           two_hop_neighbor = olsr_malloc(sizeof(*two_hop_neighbor), "Process HELLO");
147           two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist;
148           two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist;
149           two_hop_neighbor->neighbor_2_pointer = 0;
150           two_hop_neighbor->neighbor_2_addr = message_neighbors->address;
151           olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
152         }
153         /*
154          * linking to this two_hop_neighbor entry
155          */
156         changes_neighborhood = OLSR_TRUE;
157         changes_topology = OLSR_TRUE;
158         linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
159       }
160     }
161   }
162
163   /* Separate, second pass for link quality OLSR */
164   /* Separate, second and third pass for link quality OLSR */
165   if (olsr_cnf->lq_level > 0) {
166     olsr_linkcost first_hop_pathcost;
167     struct link_entry *lnk = get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
168
169     if (!lnk) {
170         return;
171     }
172     /* calculate first hop path quality */
173     first_hop_pathcost = lnk->linkcost;
174     /*
175      *  Second pass for link quality OLSR: calculate the best 2-hop
176      * path costs to all the 2-hop neighbors indicated in the
177      * HELLO message. Since the same 2-hop neighbor may be listed
178      * more than once in the same HELLO message (each at a possibly
179      * different quality) we want to select only the best one, not just
180      * the last one listed in the HELLO message.
181      */
182     for(message_neighbors = message->neighbors;
183         message_neighbors != NULL;
184         message_neighbors = message_neighbors->next) {
185       if (if_ifwithaddr(&message_neighbors->address) != NULL) {
186             continue;
187       }
188       if (message_neighbors->status == SYM_NEIGH ||
189           message_neighbors->status == MPR_NEIGH) {
190         struct neighbor_list_entry *walker;
191         struct neighbor_2_list_entry *two_hop_neighbor_yet =
192           olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
193
194         if (!two_hop_neighbor_yet) {
195           continue;
196         }
197
198         /*
199          *  loop through the one-hop neighbors that see this
200          * 'two_hop_neighbor_yet->neighbor_2'
201          */
202         for (walker = two_hop_neighbor_yet->neighbor_2->neighbor_2_nblist.next;
203              walker != &two_hop_neighbor_yet->neighbor_2->neighbor_2_nblist;
204              walker = walker->next) {
205           /*
206            * have we found the one-hop neighbor that sent the
207            * HELLO message that we're current processing?
208            */
209           if (walker->neighbor == neighbor) {
210             // the link cost between the 1-hop neighbour and the
211             // 2-hop neighbour
212             olsr_linkcost new_second_hop_linkcost = message_neighbors->cost;
213
214             // the total cost for the route
215             // "us --- 1-hop --- 2-hop"
216             olsr_linkcost new_path_linkcost = first_hop_pathcost + new_second_hop_linkcost;
217
218             // Only copy the link quality if it is better than what we have
219             // for this 2-hop neighbor
220             if (new_path_linkcost < walker->path_linkcost){
221               walker->second_hop_linkcost = new_second_hop_linkcost;
222               walker->path_linkcost = new_path_linkcost;
223
224               if (olsr_is_relevant_costchange(new_path_linkcost, walker->saved_path_linkcost)){
225                 walker->saved_path_linkcost = new_path_linkcost;
226
227                 if (olsr_cnf->lq_dlimit > 0) {
228                   changes_neighborhood = OLSR_TRUE;
229                   changes_topology = OLSR_TRUE;
230                 } else {
231                   OLSR_PRINTF(3, "Skipping Dijkstra (3)\n");
232                 }
233               }
234             }
235           }
236         }
237       }
238     }
239   }
240 }
241
242 /**
243  * Links a one-hop neighbor with a 2-hop neighbor.
244  *
245  * @param neighbor the 1-hop neighbor
246  * @param two_hop_neighbor the 2-hop neighbor
247  * @return nada
248  */
249 static void
250 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
251 {
252   struct neighbor_list_entry   *list_of_1_neighbors = olsr_malloc(sizeof(*list_of_1_neighbors), "Link entries 1");
253   struct neighbor_2_list_entry *list_of_2_neighbors = olsr_malloc(sizeof(*list_of_2_neighbors), "Link entries 2");
254
255   list_of_1_neighbors->neighbor = neighbor;
256   list_of_1_neighbors->path_linkcost = LINK_COST_BROKEN;
257   list_of_1_neighbors->saved_path_linkcost = LINK_COST_BROKEN;
258   list_of_1_neighbors->second_hop_linkcost = LINK_COST_BROKEN;
259
260   /* Queue */
261   two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
262   list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
263   two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
264   list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
265
266   list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
267   list_of_2_neighbors->nbr2_nbr = neighbor; /* XXX refcount */
268   list_of_2_neighbors->nbr2_list_timer =
269     olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER,
270                      OLSR_TIMER_ONESHOT, &olsr_expire_nbr2_list,
271                      list_of_2_neighbors, nbr2_list_timer_cookie->ci_id);
272
273   /* Queue */
274   neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
275   list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
276   neighbor->neighbor_2_list.next = list_of_2_neighbors;
277   list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
278
279   /*increment the pointer counter*/
280   two_hop_neighbor->neighbor_2_pointer++;
281 }
282
283 /**
284  * Check if a hello message states this node as a MPR.
285  *
286  * @param message the message to check
287  * @param n_link the buffer to put the link status in
288  *
289  * @return 1 if we are selected as MPR 0 if not
290  */
291 static olsr_bool
292 lookup_mpr_status(const struct hello_message *message,
293                   const struct interface *in_if)
294 {
295   struct hello_neighbor *neighbors;
296
297   for (neighbors = message->neighbors; neighbors; neighbors = neighbors->next) {
298     if (olsr_cnf->ip_version == AF_INET
299         ? ip4equal(&neighbors->address.v4, &in_if->ip_addr.v4)
300         : ip6equal(&neighbors->address.v6, &in_if->int6_addr.sin6_addr)) {
301       return neighbors->link == SYM_LINK && neighbors->status == MPR_NEIGH ? OLSR_TRUE : OLSR_FALSE;
302     }
303   }
304   /* Not found */
305   return OLSR_FALSE;
306 }
307
308 /**
309  * Initializing the parser functions we are using
310  * For downwards compatibility reasons we also understand the non-LQ messages.
311  */
312 void
313 olsr_init_package_process(void)
314 {
315   if (olsr_cnf->lq_level == 0) {
316     olsr_parser_add_function(&olsr_input_hello, HELLO_MESSAGE);
317     olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE);
318   }
319   else {
320     olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
321     olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE);
322   }
323   olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
324   olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
325   olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
326 }
327
328 static int
329 deserialize_hello(struct hello_message *hello, const void *ser)
330 {
331   const unsigned char *limit;
332   olsr_u8_t type;
333   olsr_u16_t size;
334
335   const unsigned char *curr = ser;
336   pkt_get_u8(&curr, &type);
337   if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
338     /* No need to do anything more */
339     return 1;
340   }
341   pkt_get_reltime(&curr, &hello->vtime);
342   pkt_get_u16(&curr, &size);
343   pkt_get_ipaddress(&curr, &hello->source_addr);
344
345   pkt_get_u8(&curr, &hello->ttl);
346   pkt_get_u8(&curr, &hello->hop_count);
347   pkt_get_u16(&curr, &hello->packet_seq_number);
348   pkt_ignore_u16(&curr);
349
350   pkt_get_reltime(&curr, &hello->htime);
351   pkt_get_u8(&curr, &hello->willingness);
352
353   hello->neighbors = NULL;
354   limit = ((const unsigned char *)ser) + size;
355   while (curr < limit) {
356     const struct lq_hello_info_header *info_head = (const struct lq_hello_info_header *)curr;
357     const unsigned char *limit2 = curr + ntohs(info_head->size);
358
359     curr = (const unsigned char *)(info_head + 1);
360     while (curr < limit2) {
361       struct hello_neighbor *neigh = olsr_malloc_hello_neighbor("HELLO deserialization");
362       pkt_get_ipaddress(&curr, &neigh->address);
363
364       if (type == LQ_HELLO_MESSAGE) {
365         olsr_deserialize_hello_lq_pair(&curr, neigh);
366       }
367       neigh->link = EXTRACT_LINK(info_head->link_code);
368       neigh->status = EXTRACT_STATUS(info_head->link_code);
369
370       neigh->next = hello->neighbors;
371       hello->neighbors = neigh;
372     }
373   }
374   return 0;
375 }
376
377
378 static void
379 hello_tap(struct hello_message *message,
380           struct interface *in_if,
381           const union olsr_ip_addr *from_addr)
382 {
383   /*
384    * Update link status
385    */
386   struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
387
388   if (olsr_cnf->lq_level > 0) {
389     struct hello_neighbor *walker;
390     /* just in case our neighbor has changed its HELLO interval */
391     olsr_update_packet_loss_hello_int(lnk, message->htime);
392
393     /* find the input interface in the list of neighbor interfaces */
394     for (walker = message->neighbors; walker != NULL; walker = walker->next) {
395       if (ipequal(&walker->address, &in_if->ip_addr)) {
396         break;
397       }
398     }
399
400     // memorize our neighbour's idea of the link quality, so that we
401     // know the link quality in both directions
402     olsr_memorize_foreign_hello_lq(lnk, walker);
403
404     /* update packet loss for link quality calculation */
405     olsr_update_packet_loss(lnk);
406   }
407
408   /*
409    * Hysteresis
410    */
411   if (olsr_cnf->use_hysteresis) {
412     /* Update HELLO timeout */
413     /* printf("MESSAGE HTIME: %f\n", message->htime);*/
414     olsr_update_hysteresis_hello(lnk, message->htime);
415   }
416
417   /* Check if we are chosen as MPR */
418   if (lookup_mpr_status(message, in_if)) {
419     /* source_addr is always the main addr of a node! */
420     olsr_update_mprs_set(&message->source_addr, message->vtime);
421   }
422
423   /* Check willingness */
424   if (lnk->neighbor->willingness != message->willingness) {
425     struct ipaddr_str buf;
426     OLSR_PRINTF(1, "Willingness for %s changed from %d to %d - UPDATING\n",
427                 olsr_ip_to_string(&buf, &lnk->neighbor->neighbor_main_addr),
428                 lnk->neighbor->willingness,
429                 message->willingness);
430     /*
431      *If willingness changed - recalculate
432      */
433     lnk->neighbor->willingness = message->willingness;
434     changes_neighborhood = OLSR_TRUE;
435     changes_topology = OLSR_TRUE;
436   }
437
438   /* Don't register neighbors of neighbors that announces WILL_NEVER */
439   if (lnk->neighbor->willingness != WILL_NEVER) {
440     process_message_neighbors(lnk->neighbor, message);
441   }
442
443   /* Process changes immedeatly in case of MPR updates */
444   olsr_process_changes();
445
446   olsr_free_hello_packet(message);
447 }
448
449 olsr_bool olsr_input_hello(union olsr_message *msg, struct interface *inif, union olsr_ip_addr *from)
450 {
451   struct hello_message hello;
452
453   if (msg == NULL) {
454     return OLSR_FALSE;
455   }
456   if (deserialize_hello(&hello, msg) != 0) {
457     return OLSR_FALSE;
458   }
459   hello_tap(&hello, inif, from);
460
461   /* Do not forward hello messages */
462   return OLSR_FALSE;
463 }
464
465 /*
466  * Local Variables:
467  * c-basic-offset: 2
468  * indent-tabs-mode: nil
469  * End:
470  */