Update to new avl/list iteration macros
[olsrd.git] / src / hna_set.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 "hna_set.h"
43 #include "ipcalc.h"
44 #include "defs.h"
45 #include "parser.h"
46 #include "olsr.h"
47 #include "scheduler.h"
48 #include "net_olsr.h"
49 #include "tc_set.h"
50 #include "olsr_ip_prefix_list.h"
51 #include "olsr_logging.h"
52
53 /* Some cookies for stats keeping */
54 static struct olsr_timer_info *hna_net_timer_info = NULL;
55 static struct olsr_cookie_info *hna_net_mem_cookie = NULL;
56
57 static void olsr_expire_hna_net_entry(void *context);
58
59 /**
60  * Initialize the HNA set
61  */
62 void
63 olsr_init_hna_set(void)
64 {
65   OLSR_INFO(LOG_HNA, "Initialize HNA set...\n");
66
67   hna_net_timer_info = olsr_alloc_timerinfo("HNA Network", &olsr_expire_hna_net_entry, false);
68
69   hna_net_mem_cookie = olsr_create_memcookie("hna_net", sizeof(struct hna_net));
70 }
71
72 /**
73  * Lookup a network entry in the HNA subtree.
74  *
75  * @param tc the HNA hookup point
76  * @param prefic the prefix to look for
77  *
78  * @return the localized entry or NULL of not found
79  */
80 static struct hna_net *
81 olsr_lookup_hna_net(struct tc_entry *tc, const struct olsr_ip_prefix *prefix)
82 {
83   struct hna_net *hna;
84
85   hna = avl_find_element(&tc->hna_tree, prefix, hna, hna_tc_node);
86   return hna;
87 }
88
89 /**
90  * Adds a network entry to a HNA gateway.
91  *
92  * @param tc the gateway entry to add the network to
93  * @param net the nework prefix to add
94  * @param prefixlen the prefix length
95  *
96  * @return the newly created entry
97  */
98 static struct hna_net *
99 olsr_add_hna_net(struct tc_entry *tc, const struct olsr_ip_prefix *prefix)
100 {
101   /* Add the net */
102   struct hna_net *new_net = olsr_cookie_malloc(hna_net_mem_cookie);
103
104   /* Fill struct */
105   new_net->hna_prefix = *prefix;
106
107   /* Set backpointer */
108   new_net->hna_tc = tc;
109
110   /*
111    * Insert into the per-tc hna subtree.
112    */
113   new_net->hna_tc_node.key = &new_net->hna_prefix;
114   avl_insert(&tc->hna_tree, &new_net->hna_tc_node);
115
116   return new_net;
117 }
118
119 /**
120  * Delete a single HNA network.
121  *
122  * @param hna_net the hna_net to delete.
123  */
124 static void
125 olsr_delete_hna_net(struct hna_net *hna_net)
126 {
127   struct tc_entry *tc = hna_net->hna_tc;
128
129   /*
130    * Delete the rt_path for the hna_net.
131    */
132   olsr_delete_routing_table(&hna_net->hna_prefix.prefix, hna_net->hna_prefix.prefix_len, &tc->addr, OLSR_RT_ORIGIN_HNA);
133
134   /*
135    * Remove from the per-tc tree.
136    */
137   avl_delete(&tc->hna_tree, &hna_net->hna_tc_node);
138
139   if (hna_net->hna_net_timer) {
140     olsr_stop_timer(hna_net->hna_net_timer);
141     hna_net->hna_net_timer = NULL;
142   }
143   /*
144    * Unlock and free.
145    */
146   olsr_cookie_free(hna_net_mem_cookie, hna_net);
147 }
148
149 /**
150  * Delete all the HNA nets hanging off a tc entry.
151  *
152  * @param entry the tc entry holding the HNA networks.
153  */
154 void
155 olsr_flush_hna_nets(struct tc_entry *tc)
156 {
157   struct hna_net *hna_net, *iterator;
158
159 #if !defined REMOVE_LOG_DEBUG
160   struct ipaddr_str buf;
161 #endif
162
163   OLSR_DEBUG(LOG_TC, "flush hna nets of '%s' (%u)\n", olsr_ip_to_string(&buf, &tc->addr), tc->edge_tree.count);
164   OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net, iterator) {
165     olsr_delete_hna_net(hna_net);
166   }
167 }
168
169 /**
170  * Callback for the hna_net timer.
171  */
172 static void
173 olsr_expire_hna_net_entry(void *context)
174 {
175   struct hna_net *hna_net = context;
176 #if !defined REMOVE_LOG_DEBUG
177   struct ipaddr_str buf;
178   struct ipprefix_str prefixstr;
179 #endif
180
181   OLSR_DEBUG(5, "HNA: timeout %s via hna-gw %s\n",
182              olsr_ip_prefix_to_string(&prefixstr, &hna_net->hna_prefix), olsr_ip_to_string(&buf, &hna_net->hna_tc->addr));
183
184   hna_net->hna_net_timer = NULL;        /* be pedandic */
185
186   olsr_delete_hna_net(hna_net);
187 }
188
189 /**
190  * Update a HNA entry. If it does not exist it
191  * is created.
192  * This is the only function that should be called
193  * from outside concerning creation of HNA entries.
194  *
195  *@param gw address of the gateway
196  *@param net address of the network
197  *@param mask the netmask
198  *@param vtime the validitytime of the entry
199  *
200  *@return nada
201  */
202 static void
203 olsr_update_hna_entry(const union olsr_ip_addr *gw, const struct olsr_ip_prefix *prefix, uint32_t vtime,
204     uint16_t msg_seq)
205 {
206   struct tc_entry *tc = olsr_locate_tc_entry(gw);
207   struct hna_net *net_entry = olsr_lookup_hna_net(tc, prefix);
208
209   if (net_entry == NULL) {
210     /* Need to add the net */
211     net_entry = olsr_add_hna_net(tc, prefix);
212     changes_hna = true;
213   }
214
215   net_entry->tc_entry_seqno = msg_seq;
216
217   /*
218    * Add the rt_path for the entry.
219    */
220   olsr_insert_routing_table(&net_entry->hna_prefix.prefix, net_entry->hna_prefix.prefix_len, &tc->addr, OLSR_RT_ORIGIN_HNA);
221
222   /*
223    * Start, or refresh the timer, whatever is appropriate.
224    */
225   olsr_set_timer(&net_entry->hna_net_timer, vtime,
226                  OLSR_HNA_NET_JITTER, net_entry, hna_net_timer_info);
227 }
228
229 /**
230  * Print all HNA entries.
231  *
232  *@return nada
233  */
234 void
235 olsr_print_hna_set(void)
236 {
237   /* The whole function doesn't do anything else. */
238 #if !defined REMOVE_LOG_INFO
239   struct tc_entry *tc, *tc_iterator;
240   struct ipaddr_str buf;
241   struct ipprefix_str prefixstr;
242   struct hna_net *hna_net, *hna_iterator;
243
244   OLSR_INFO(LOG_HNA, "\n--- %s ------------------------------------------------- HNA\n\n", olsr_wallclock_string());
245
246   OLSR_FOR_ALL_TC_ENTRIES(tc, tc_iterator) {
247     OLSR_INFO_NH(LOG_HNA, "HNA-gw %s:\n", olsr_ip_to_string(&buf, &tc->addr));
248
249     OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net, hna_iterator) {
250       OLSR_INFO_NH(LOG_HNA, "\t%-27s\n", olsr_ip_prefix_to_string(&prefixstr, &hna_net->hna_prefix));
251     }
252   }
253 #endif
254 }
255
256 static void
257 olsr_prune_hna_entries(struct tc_entry *tc)
258 {
259   struct hna_net *hna_net, *iterator;
260
261   OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net, iterator) {
262     if (hna_net->tc_entry_seqno != tc->hna_seq) {
263       olsr_delete_hna_net(hna_net);
264     }
265   }
266 }
267
268 /**
269  * Process incoming HNA message.
270  * Forwards the message if that is to be done.
271  */
272 void
273 olsr_input_hna(struct olsr_message *msg,
274     struct interface *in_if __attribute__ ((unused)),
275     union olsr_ip_addr *from_addr, enum duplicate_status status)
276 {
277   struct tc_entry *tc;
278   struct olsr_ip_prefix prefix;
279   const uint8_t *curr;
280 #if !defined REMOVE_LOG_DEBUG
281   struct ipaddr_str buf;
282 #endif
283
284
285   /* We are only interested in MID message types. */
286   if (msg->type != HNA_MESSAGE) {
287     return;
288   }
289
290   /*
291    * If the sender interface (NB: not originator) of this message
292    * is not in the symmetric 1-hop neighborhood of this node, the
293    * message MUST be discarded.
294    */
295   if (check_neighbor_link(from_addr) != SYM_LINK) {
296     OLSR_DEBUG(LOG_HNA, "Received HNA from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
297     return;
298   }
299
300   tc = olsr_locate_tc_entry(&msg->originator);
301   if (status != RESET_SEQNO_OLSR_MESSAGE && tc->hna_seq != -1 && olsr_seqno_diff(msg->seqno, tc->hna_seq) <= 0) {
302     /* this HNA is too old, discard it */
303     return;
304   }
305   tc->hna_seq = msg->seqno;
306
307   OLSR_DEBUG(LOG_HNA, "Processing HNA from %s, seq 0x%04x\n", olsr_ip_to_string(&buf, &msg->originator), msg->seqno);
308
309   /*
310    * Now walk the list of HNA advertisements.
311    */
312   curr = msg->payload;
313   while (curr + 2*olsr_cnf->ipsize <= msg->end) {
314     pkt_get_ipaddress(&curr, &prefix.prefix);
315     pkt_get_prefixlen(&curr, &prefix.prefix_len);
316
317     if (!ip_prefix_list_find(&olsr_cnf->hna_entries, &prefix.prefix, prefix.prefix_len, olsr_cnf->ip_version)) {
318       /*
319        * Only update if it's not from us.
320        */
321       olsr_update_hna_entry(&msg->originator, &prefix, msg->vtime, msg->seqno);
322     }
323   }
324
325   /*
326    * Prune the HNAs that did not get refreshed by this advertisment.
327    */
328   olsr_prune_hna_entries(tc);
329 }
330
331 void
332 generate_hna(void *p __attribute__ ((unused))) {
333   struct interface *ifp, *ifp_iterator;
334   struct ip_prefix_entry *h, *h_iterator;
335   uint8_t msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE] __attribute__ ((aligned));
336   uint8_t *curr = msg_buffer;
337   uint8_t *length_field, *last;
338   bool sendHNA = false;
339
340   OLSR_INFO(LOG_PACKET_CREATION, "Building HNA\n-------------------\n");
341
342   pkt_put_u8(&curr, HNA_MESSAGE);
343   pkt_put_reltime(&curr, olsr_cnf->hna_params.validity_time);
344
345   length_field = curr;
346   pkt_put_u16(&curr, 0); /* put in real messagesize later */
347
348   pkt_put_ipaddress(&curr, &olsr_cnf->router_id);
349
350   pkt_put_u8(&curr, 255);
351   pkt_put_u8(&curr, 0);
352   pkt_put_u16(&curr, get_msg_seqno());
353
354   last = msg_buffer + sizeof(msg_buffer) - olsr_cnf->ipsize;
355   OLSR_FOR_ALL_IPPREFIX_ENTRIES(&olsr_cnf->hna_entries, h, h_iterator) {
356     union olsr_ip_addr subnet;
357
358     olsr_prefix_to_netmask(&subnet, h->net.prefix_len);
359     sendHNA = true;
360     pkt_put_ipaddress(&curr, &h->net.prefix);
361     pkt_put_ipaddress(&curr, &subnet);
362   }
363
364   if (!sendHNA) {
365     return;
366   }
367
368   pkt_put_u16(&length_field, curr - msg_buffer);
369
370   OLSR_FOR_ALL_INTERFACES(ifp, ifp_iterator) {
371     if (net_outbuffer_bytes_left(ifp) < curr - msg_buffer) {
372       net_output(ifp);
373       set_buffer_timer(ifp);
374     }
375     net_outbuffer_push(ifp, msg_buffer, curr - msg_buffer);
376   }
377 }
378
379 /*
380  * Local Variables:
381  * c-basic-offset: 2
382  * indent-tabs-mode: nil
383  * End:
384  */