899d4943d8adacc7c1490e66f00169f61b217f1a
[linux-3.10.git] / net / batman-adv / originator.c
1 /*
2  * Copyright (C) 2009-2011 B.A.T.M.A.N. contributors:
3  *
4  * Marek Lindner, Simon Wunderlich
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of version 2 of the GNU General Public
8  * License as published by the Free Software Foundation.
9  *
10  * This program is distributed in the hope that it will be useful, but
11  * WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18  * 02110-1301, USA
19  *
20  */
21
22 /* increase the reference counter for this originator */
23
24 #include "main.h"
25 #include "originator.h"
26 #include "hash.h"
27 #include "translation-table.h"
28 #include "routing.h"
29 #include "gateway_client.h"
30 #include "hard-interface.h"
31 #include "unicast.h"
32 #include "soft-interface.h"
33
34 static void purge_orig(struct work_struct *work);
35
36 static void start_purge_timer(struct bat_priv *bat_priv)
37 {
38         INIT_DELAYED_WORK(&bat_priv->orig_work, purge_orig);
39         queue_delayed_work(bat_event_workqueue, &bat_priv->orig_work, 1 * HZ);
40 }
41
42 int originator_init(struct bat_priv *bat_priv)
43 {
44         if (bat_priv->orig_hash)
45                 return 1;
46
47         spin_lock_bh(&bat_priv->orig_hash_lock);
48         bat_priv->orig_hash = hash_new(1024);
49
50         if (!bat_priv->orig_hash)
51                 goto err;
52
53         spin_unlock_bh(&bat_priv->orig_hash_lock);
54         start_purge_timer(bat_priv);
55         return 1;
56
57 err:
58         spin_unlock_bh(&bat_priv->orig_hash_lock);
59         return 0;
60 }
61
62 void neigh_node_free_ref(struct kref *refcount)
63 {
64         struct neigh_node *neigh_node;
65
66         neigh_node = container_of(refcount, struct neigh_node, refcount);
67         kfree(neigh_node);
68 }
69
70 static void neigh_node_free_rcu(struct rcu_head *rcu)
71 {
72         struct neigh_node *neigh_node;
73
74         neigh_node = container_of(rcu, struct neigh_node, rcu);
75         kref_put(&neigh_node->refcount, neigh_node_free_ref);
76 }
77
78 struct neigh_node *create_neighbor(struct orig_node *orig_node,
79                                    struct orig_node *orig_neigh_node,
80                                    uint8_t *neigh,
81                                    struct batman_if *if_incoming)
82 {
83         struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
84         struct neigh_node *neigh_node;
85
86         bat_dbg(DBG_BATMAN, bat_priv,
87                 "Creating new last-hop neighbor of originator\n");
88
89         neigh_node = kzalloc(sizeof(struct neigh_node), GFP_ATOMIC);
90         if (!neigh_node)
91                 return NULL;
92
93         INIT_HLIST_NODE(&neigh_node->list);
94
95         memcpy(neigh_node->addr, neigh, ETH_ALEN);
96         neigh_node->orig_node = orig_neigh_node;
97         neigh_node->if_incoming = if_incoming;
98         kref_init(&neigh_node->refcount);
99
100         spin_lock_bh(&orig_node->neigh_list_lock);
101         hlist_add_head_rcu(&neigh_node->list, &orig_node->neigh_list);
102         spin_unlock_bh(&orig_node->neigh_list_lock);
103         return neigh_node;
104 }
105
106 static void free_orig_node(void *data, void *arg)
107 {
108         struct hlist_node *node, *node_tmp;
109         struct neigh_node *neigh_node;
110         struct orig_node *orig_node = (struct orig_node *)data;
111         struct bat_priv *bat_priv = (struct bat_priv *)arg;
112
113         spin_lock_bh(&orig_node->neigh_list_lock);
114
115         /* for all neighbors towards this originator ... */
116         hlist_for_each_entry_safe(neigh_node, node, node_tmp,
117                                   &orig_node->neigh_list, list) {
118                 hlist_del_rcu(&neigh_node->list);
119                 call_rcu(&neigh_node->rcu, neigh_node_free_rcu);
120         }
121
122         spin_unlock_bh(&orig_node->neigh_list_lock);
123
124         frag_list_free(&orig_node->frag_list);
125         hna_global_del_orig(bat_priv, orig_node, "originator timed out");
126
127         kfree(orig_node->bcast_own);
128         kfree(orig_node->bcast_own_sum);
129         kfree(orig_node);
130 }
131
132 void originator_free(struct bat_priv *bat_priv)
133 {
134         if (!bat_priv->orig_hash)
135                 return;
136
137         cancel_delayed_work_sync(&bat_priv->orig_work);
138
139         spin_lock_bh(&bat_priv->orig_hash_lock);
140         hash_delete(bat_priv->orig_hash, free_orig_node, bat_priv);
141         bat_priv->orig_hash = NULL;
142         spin_unlock_bh(&bat_priv->orig_hash_lock);
143 }
144
145 /* this function finds or creates an originator entry for the given
146  * address if it does not exits */
147 struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr)
148 {
149         struct orig_node *orig_node;
150         int size;
151         int hash_added;
152
153         orig_node = ((struct orig_node *)hash_find(bat_priv->orig_hash,
154                                                    compare_orig, choose_orig,
155                                                    addr));
156
157         if (orig_node)
158                 return orig_node;
159
160         bat_dbg(DBG_BATMAN, bat_priv,
161                 "Creating new originator: %pM\n", addr);
162
163         orig_node = kzalloc(sizeof(struct orig_node), GFP_ATOMIC);
164         if (!orig_node)
165                 return NULL;
166
167         INIT_HLIST_HEAD(&orig_node->neigh_list);
168         spin_lock_init(&orig_node->neigh_list_lock);
169
170         memcpy(orig_node->orig, addr, ETH_ALEN);
171         orig_node->router = NULL;
172         orig_node->hna_buff = NULL;
173         orig_node->bcast_seqno_reset = jiffies - 1
174                                         - msecs_to_jiffies(RESET_PROTECTION_MS);
175         orig_node->batman_seqno_reset = jiffies - 1
176                                         - msecs_to_jiffies(RESET_PROTECTION_MS);
177
178         size = bat_priv->num_ifaces * sizeof(unsigned long) * NUM_WORDS;
179
180         orig_node->bcast_own = kzalloc(size, GFP_ATOMIC);
181         if (!orig_node->bcast_own)
182                 goto free_orig_node;
183
184         size = bat_priv->num_ifaces * sizeof(uint8_t);
185         orig_node->bcast_own_sum = kzalloc(size, GFP_ATOMIC);
186
187         INIT_LIST_HEAD(&orig_node->frag_list);
188         orig_node->last_frag_packet = 0;
189
190         if (!orig_node->bcast_own_sum)
191                 goto free_bcast_own;
192
193         hash_added = hash_add(bat_priv->orig_hash, compare_orig, choose_orig,
194                               orig_node);
195         if (hash_added < 0)
196                 goto free_bcast_own_sum;
197
198         return orig_node;
199 free_bcast_own_sum:
200         kfree(orig_node->bcast_own_sum);
201 free_bcast_own:
202         kfree(orig_node->bcast_own);
203 free_orig_node:
204         kfree(orig_node);
205         return NULL;
206 }
207
208 static bool purge_orig_neighbors(struct bat_priv *bat_priv,
209                                  struct orig_node *orig_node,
210                                  struct neigh_node **best_neigh_node)
211 {
212         struct hlist_node *node, *node_tmp;
213         struct neigh_node *neigh_node;
214         bool neigh_purged = false;
215
216         *best_neigh_node = NULL;
217
218         spin_lock_bh(&orig_node->neigh_list_lock);
219
220         /* for all neighbors towards this originator ... */
221         hlist_for_each_entry_safe(neigh_node, node, node_tmp,
222                                   &orig_node->neigh_list, list) {
223
224                 if ((time_after(jiffies,
225                         neigh_node->last_valid + PURGE_TIMEOUT * HZ)) ||
226                     (neigh_node->if_incoming->if_status == IF_INACTIVE) ||
227                     (neigh_node->if_incoming->if_status == IF_NOT_IN_USE) ||
228                     (neigh_node->if_incoming->if_status == IF_TO_BE_REMOVED)) {
229
230                         if ((neigh_node->if_incoming->if_status ==
231                                                                 IF_INACTIVE) ||
232                             (neigh_node->if_incoming->if_status ==
233                                                         IF_NOT_IN_USE) ||
234                             (neigh_node->if_incoming->if_status ==
235                                                         IF_TO_BE_REMOVED))
236                                 bat_dbg(DBG_BATMAN, bat_priv,
237                                         "neighbor purge: originator %pM, "
238                                         "neighbor: %pM, iface: %s\n",
239                                         orig_node->orig, neigh_node->addr,
240                                         neigh_node->if_incoming->net_dev->name);
241                         else
242                                 bat_dbg(DBG_BATMAN, bat_priv,
243                                         "neighbor timeout: originator %pM, "
244                                         "neighbor: %pM, last_valid: %lu\n",
245                                         orig_node->orig, neigh_node->addr,
246                                         (neigh_node->last_valid / HZ));
247
248                         neigh_purged = true;
249
250                         hlist_del_rcu(&neigh_node->list);
251                         call_rcu(&neigh_node->rcu, neigh_node_free_rcu);
252                 } else {
253                         if ((!*best_neigh_node) ||
254                             (neigh_node->tq_avg > (*best_neigh_node)->tq_avg))
255                                 *best_neigh_node = neigh_node;
256                 }
257         }
258
259         spin_unlock_bh(&orig_node->neigh_list_lock);
260         return neigh_purged;
261 }
262
263 static bool purge_orig_node(struct bat_priv *bat_priv,
264                             struct orig_node *orig_node)
265 {
266         struct neigh_node *best_neigh_node;
267
268         if (time_after(jiffies,
269                 orig_node->last_valid + 2 * PURGE_TIMEOUT * HZ)) {
270
271                 bat_dbg(DBG_BATMAN, bat_priv,
272                         "Originator timeout: originator %pM, last_valid %lu\n",
273                         orig_node->orig, (orig_node->last_valid / HZ));
274                 return true;
275         } else {
276                 if (purge_orig_neighbors(bat_priv, orig_node,
277                                                         &best_neigh_node)) {
278                         update_routes(bat_priv, orig_node,
279                                       best_neigh_node,
280                                       orig_node->hna_buff,
281                                       orig_node->hna_buff_len);
282                         /* update bonding candidates, we could have lost
283                          * some candidates. */
284                         update_bonding_candidates(orig_node);
285                 }
286         }
287
288         return false;
289 }
290
291 static void _purge_orig(struct bat_priv *bat_priv)
292 {
293         struct hashtable_t *hash = bat_priv->orig_hash;
294         struct hlist_node *walk, *safe;
295         struct hlist_head *head;
296         struct element_t *bucket;
297         struct orig_node *orig_node;
298         int i;
299
300         if (!hash)
301                 return;
302
303         spin_lock_bh(&bat_priv->orig_hash_lock);
304
305         /* for all origins... */
306         for (i = 0; i < hash->size; i++) {
307                 head = &hash->table[i];
308
309                 hlist_for_each_entry_safe(bucket, walk, safe, head, hlist) {
310                         orig_node = bucket->data;
311
312                         if (purge_orig_node(bat_priv, orig_node)) {
313                                 if (orig_node->gw_flags)
314                                         gw_node_delete(bat_priv, orig_node);
315                                 hlist_del(walk);
316                                 kfree(bucket);
317                                 free_orig_node(orig_node, bat_priv);
318                         }
319
320                         if (time_after(jiffies, orig_node->last_frag_packet +
321                                                 msecs_to_jiffies(FRAG_TIMEOUT)))
322                                 frag_list_free(&orig_node->frag_list);
323                 }
324         }
325
326         spin_unlock_bh(&bat_priv->orig_hash_lock);
327
328         gw_node_purge(bat_priv);
329         gw_election(bat_priv);
330
331         softif_neigh_purge(bat_priv);
332 }
333
334 static void purge_orig(struct work_struct *work)
335 {
336         struct delayed_work *delayed_work =
337                 container_of(work, struct delayed_work, work);
338         struct bat_priv *bat_priv =
339                 container_of(delayed_work, struct bat_priv, orig_work);
340
341         _purge_orig(bat_priv);
342         start_purge_timer(bat_priv);
343 }
344
345 void purge_orig_ref(struct bat_priv *bat_priv)
346 {
347         _purge_orig(bat_priv);
348 }
349
350 int orig_seq_print_text(struct seq_file *seq, void *offset)
351 {
352         struct net_device *net_dev = (struct net_device *)seq->private;
353         struct bat_priv *bat_priv = netdev_priv(net_dev);
354         struct hashtable_t *hash = bat_priv->orig_hash;
355         struct hlist_node *walk, *node;
356         struct hlist_head *head;
357         struct element_t *bucket;
358         struct orig_node *orig_node;
359         struct neigh_node *neigh_node;
360         int batman_count = 0;
361         int last_seen_secs;
362         int last_seen_msecs;
363         int i;
364
365         if ((!bat_priv->primary_if) ||
366             (bat_priv->primary_if->if_status != IF_ACTIVE)) {
367                 if (!bat_priv->primary_if)
368                         return seq_printf(seq, "BATMAN mesh %s disabled - "
369                                      "please specify interfaces to enable it\n",
370                                      net_dev->name);
371
372                 return seq_printf(seq, "BATMAN mesh %s "
373                                   "disabled - primary interface not active\n",
374                                   net_dev->name);
375         }
376
377         seq_printf(seq, "[B.A.T.M.A.N. adv %s%s, MainIF/MAC: %s/%pM (%s)]\n",
378                    SOURCE_VERSION, REVISION_VERSION_STR,
379                    bat_priv->primary_if->net_dev->name,
380                    bat_priv->primary_if->net_dev->dev_addr, net_dev->name);
381         seq_printf(seq, "  %-15s %s (%s/%i) %17s [%10s]: %20s ...\n",
382                    "Originator", "last-seen", "#", TQ_MAX_VALUE, "Nexthop",
383                    "outgoingIF", "Potential nexthops");
384
385         spin_lock_bh(&bat_priv->orig_hash_lock);
386
387         for (i = 0; i < hash->size; i++) {
388                 head = &hash->table[i];
389
390                 hlist_for_each_entry(bucket, walk, head, hlist) {
391                         orig_node = bucket->data;
392
393                         if (!orig_node->router)
394                                 continue;
395
396                         if (orig_node->router->tq_avg == 0)
397                                 continue;
398
399                         last_seen_secs = jiffies_to_msecs(jiffies -
400                                                 orig_node->last_valid) / 1000;
401                         last_seen_msecs = jiffies_to_msecs(jiffies -
402                                                 orig_node->last_valid) % 1000;
403
404                         neigh_node = orig_node->router;
405                         seq_printf(seq, "%pM %4i.%03is   (%3i) %pM [%10s]:",
406                                    orig_node->orig, last_seen_secs,
407                                    last_seen_msecs, neigh_node->tq_avg,
408                                    neigh_node->addr,
409                                    neigh_node->if_incoming->net_dev->name);
410
411                         rcu_read_lock();
412                         hlist_for_each_entry_rcu(neigh_node, node,
413                                                  &orig_node->neigh_list, list) {
414                                 seq_printf(seq, " %pM (%3i)", neigh_node->addr,
415                                                 neigh_node->tq_avg);
416                         }
417                         rcu_read_unlock();
418
419                         seq_printf(seq, "\n");
420                         batman_count++;
421                 }
422         }
423
424         spin_unlock_bh(&bat_priv->orig_hash_lock);
425
426         if ((batman_count == 0))
427                 seq_printf(seq, "No batman nodes in range ...\n");
428
429         return 0;
430 }
431
432 static int orig_node_add_if(struct orig_node *orig_node, int max_if_num)
433 {
434         void *data_ptr;
435
436         data_ptr = kmalloc(max_if_num * sizeof(unsigned long) * NUM_WORDS,
437                            GFP_ATOMIC);
438         if (!data_ptr) {
439                 pr_err("Can't resize orig: out of memory\n");
440                 return -1;
441         }
442
443         memcpy(data_ptr, orig_node->bcast_own,
444                (max_if_num - 1) * sizeof(unsigned long) * NUM_WORDS);
445         kfree(orig_node->bcast_own);
446         orig_node->bcast_own = data_ptr;
447
448         data_ptr = kmalloc(max_if_num * sizeof(uint8_t), GFP_ATOMIC);
449         if (!data_ptr) {
450                 pr_err("Can't resize orig: out of memory\n");
451                 return -1;
452         }
453
454         memcpy(data_ptr, orig_node->bcast_own_sum,
455                (max_if_num - 1) * sizeof(uint8_t));
456         kfree(orig_node->bcast_own_sum);
457         orig_node->bcast_own_sum = data_ptr;
458
459         return 0;
460 }
461
462 int orig_hash_add_if(struct batman_if *batman_if, int max_if_num)
463 {
464         struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface);
465         struct hashtable_t *hash = bat_priv->orig_hash;
466         struct hlist_node *walk;
467         struct hlist_head *head;
468         struct element_t *bucket;
469         struct orig_node *orig_node;
470         int i;
471
472         /* resize all orig nodes because orig_node->bcast_own(_sum) depend on
473          * if_num */
474         spin_lock_bh(&bat_priv->orig_hash_lock);
475
476         for (i = 0; i < hash->size; i++) {
477                 head = &hash->table[i];
478
479                 hlist_for_each_entry(bucket, walk, head, hlist) {
480                         orig_node = bucket->data;
481
482                         if (orig_node_add_if(orig_node, max_if_num) == -1)
483                                 goto err;
484                 }
485         }
486
487         spin_unlock_bh(&bat_priv->orig_hash_lock);
488         return 0;
489
490 err:
491         spin_unlock_bh(&bat_priv->orig_hash_lock);
492         return -ENOMEM;
493 }
494
495 static int orig_node_del_if(struct orig_node *orig_node,
496                      int max_if_num, int del_if_num)
497 {
498         void *data_ptr = NULL;
499         int chunk_size;
500
501         /* last interface was removed */
502         if (max_if_num == 0)
503                 goto free_bcast_own;
504
505         chunk_size = sizeof(unsigned long) * NUM_WORDS;
506         data_ptr = kmalloc(max_if_num * chunk_size, GFP_ATOMIC);
507         if (!data_ptr) {
508                 pr_err("Can't resize orig: out of memory\n");
509                 return -1;
510         }
511
512         /* copy first part */
513         memcpy(data_ptr, orig_node->bcast_own, del_if_num * chunk_size);
514
515         /* copy second part */
516         memcpy(data_ptr + del_if_num * chunk_size,
517                orig_node->bcast_own + ((del_if_num + 1) * chunk_size),
518                (max_if_num - del_if_num) * chunk_size);
519
520 free_bcast_own:
521         kfree(orig_node->bcast_own);
522         orig_node->bcast_own = data_ptr;
523
524         if (max_if_num == 0)
525                 goto free_own_sum;
526
527         data_ptr = kmalloc(max_if_num * sizeof(uint8_t), GFP_ATOMIC);
528         if (!data_ptr) {
529                 pr_err("Can't resize orig: out of memory\n");
530                 return -1;
531         }
532
533         memcpy(data_ptr, orig_node->bcast_own_sum,
534                del_if_num * sizeof(uint8_t));
535
536         memcpy(data_ptr + del_if_num * sizeof(uint8_t),
537                orig_node->bcast_own_sum + ((del_if_num + 1) * sizeof(uint8_t)),
538                (max_if_num - del_if_num) * sizeof(uint8_t));
539
540 free_own_sum:
541         kfree(orig_node->bcast_own_sum);
542         orig_node->bcast_own_sum = data_ptr;
543
544         return 0;
545 }
546
547 int orig_hash_del_if(struct batman_if *batman_if, int max_if_num)
548 {
549         struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface);
550         struct hashtable_t *hash = bat_priv->orig_hash;
551         struct hlist_node *walk;
552         struct hlist_head *head;
553         struct element_t *bucket;
554         struct batman_if *batman_if_tmp;
555         struct orig_node *orig_node;
556         int i, ret;
557
558         /* resize all orig nodes because orig_node->bcast_own(_sum) depend on
559          * if_num */
560         spin_lock_bh(&bat_priv->orig_hash_lock);
561
562         for (i = 0; i < hash->size; i++) {
563                 head = &hash->table[i];
564
565                 hlist_for_each_entry(bucket, walk, head, hlist) {
566                         orig_node = bucket->data;
567
568                         ret = orig_node_del_if(orig_node, max_if_num,
569                                         batman_if->if_num);
570
571                         if (ret == -1)
572                                 goto err;
573                 }
574         }
575
576         /* renumber remaining batman interfaces _inside_ of orig_hash_lock */
577         rcu_read_lock();
578         list_for_each_entry_rcu(batman_if_tmp, &if_list, list) {
579                 if (batman_if_tmp->if_status == IF_NOT_IN_USE)
580                         continue;
581
582                 if (batman_if == batman_if_tmp)
583                         continue;
584
585                 if (batman_if->soft_iface != batman_if_tmp->soft_iface)
586                         continue;
587
588                 if (batman_if_tmp->if_num > batman_if->if_num)
589                         batman_if_tmp->if_num--;
590         }
591         rcu_read_unlock();
592
593         batman_if->if_num = -1;
594         spin_unlock_bh(&bat_priv->orig_hash_lock);
595         return 0;
596
597 err:
598         spin_unlock_bh(&bat_priv->orig_hash_lock);
599         return -ENOMEM;
600 }