1 /* Copyright (C) 2007-2012 B.A.T.M.A.N. contributors:
3 * Marek Lindner, Simon Wunderlich, Antonio Quartulli
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of version 2 of the GNU General Public
7 * License as published by the Free Software Foundation.
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 #include "translation-table.h"
22 #include "soft-interface.h"
23 #include "hard-interface.h"
26 #include "originator.h"
28 #include "bridge_loop_avoidance.h"
30 #include <linux/crc16.h>
32 static void batadv_send_roam_adv(struct bat_priv *bat_priv, uint8_t *client,
33 struct orig_node *orig_node);
34 static void batadv_tt_purge(struct work_struct *work);
36 batadv_tt_global_del_orig_list(struct tt_global_entry *tt_global_entry);
38 /* returns 1 if they are the same mac addr */
39 static int batadv_compare_tt(const struct hlist_node *node, const void *data2)
41 const void *data1 = container_of(node, struct tt_common_entry,
44 return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0);
47 static void batadv_tt_start_timer(struct bat_priv *bat_priv)
49 INIT_DELAYED_WORK(&bat_priv->tt_work, batadv_tt_purge);
50 queue_delayed_work(batadv_event_workqueue, &bat_priv->tt_work,
51 msecs_to_jiffies(5000));
54 static struct tt_common_entry *batadv_tt_hash_find(struct hashtable_t *hash,
57 struct hlist_head *head;
58 struct hlist_node *node;
59 struct tt_common_entry *tt_common_entry, *tt_common_entry_tmp = NULL;
65 index = batadv_choose_orig(data, hash->size);
66 head = &hash->table[index];
69 hlist_for_each_entry_rcu(tt_common_entry, node, head, hash_entry) {
70 if (!batadv_compare_eth(tt_common_entry, data))
73 if (!atomic_inc_not_zero(&tt_common_entry->refcount))
76 tt_common_entry_tmp = tt_common_entry;
81 return tt_common_entry_tmp;
84 static struct tt_local_entry *
85 batadv_tt_local_hash_find(struct bat_priv *bat_priv, const void *data)
87 struct tt_common_entry *tt_common_entry;
88 struct tt_local_entry *tt_local_entry = NULL;
90 tt_common_entry = batadv_tt_hash_find(bat_priv->tt_local_hash, data);
92 tt_local_entry = container_of(tt_common_entry,
93 struct tt_local_entry, common);
94 return tt_local_entry;
97 static struct tt_global_entry *
98 batadv_tt_global_hash_find(struct bat_priv *bat_priv, const void *data)
100 struct tt_common_entry *tt_common_entry;
101 struct tt_global_entry *tt_global_entry = NULL;
103 tt_common_entry = batadv_tt_hash_find(bat_priv->tt_global_hash, data);
105 tt_global_entry = container_of(tt_common_entry,
106 struct tt_global_entry, common);
107 return tt_global_entry;
112 batadv_tt_local_entry_free_ref(struct tt_local_entry *tt_local_entry)
114 if (atomic_dec_and_test(&tt_local_entry->common.refcount))
115 kfree_rcu(tt_local_entry, common.rcu);
118 static void batadv_tt_global_entry_free_rcu(struct rcu_head *rcu)
120 struct tt_common_entry *tt_common_entry;
121 struct tt_global_entry *tt_global_entry;
123 tt_common_entry = container_of(rcu, struct tt_common_entry, rcu);
124 tt_global_entry = container_of(tt_common_entry, struct tt_global_entry,
127 kfree(tt_global_entry);
131 batadv_tt_global_entry_free_ref(struct tt_global_entry *tt_global_entry)
133 if (atomic_dec_and_test(&tt_global_entry->common.refcount)) {
134 batadv_tt_global_del_orig_list(tt_global_entry);
135 call_rcu(&tt_global_entry->common.rcu,
136 batadv_tt_global_entry_free_rcu);
140 static void batadv_tt_orig_list_entry_free_rcu(struct rcu_head *rcu)
142 struct tt_orig_list_entry *orig_entry;
144 orig_entry = container_of(rcu, struct tt_orig_list_entry, rcu);
145 batadv_orig_node_free_ref(orig_entry->orig_node);
150 batadv_tt_orig_list_entry_free_ref(struct tt_orig_list_entry *orig_entry)
152 /* to avoid race conditions, immediately decrease the tt counter */
153 atomic_dec(&orig_entry->orig_node->tt_size);
154 call_rcu(&orig_entry->rcu, batadv_tt_orig_list_entry_free_rcu);
157 static void batadv_tt_local_event(struct bat_priv *bat_priv,
158 const uint8_t *addr, uint8_t flags)
160 struct tt_change_node *tt_change_node, *entry, *safe;
161 bool event_removed = false;
162 bool del_op_requested, del_op_entry;
164 tt_change_node = kmalloc(sizeof(*tt_change_node), GFP_ATOMIC);
169 tt_change_node->change.flags = flags;
170 memcpy(tt_change_node->change.addr, addr, ETH_ALEN);
172 del_op_requested = flags & TT_CLIENT_DEL;
174 /* check for ADD+DEL or DEL+ADD events */
175 spin_lock_bh(&bat_priv->tt_changes_list_lock);
176 list_for_each_entry_safe(entry, safe, &bat_priv->tt_changes_list,
178 if (!batadv_compare_eth(entry->change.addr, addr))
181 /* DEL+ADD in the same orig interval have no effect and can be
182 * removed to avoid silly behaviour on the receiver side. The
183 * other way around (ADD+DEL) can happen in case of roaming of
184 * a client still in the NEW state. Roaming of NEW clients is
185 * now possible due to automatically recognition of "temporary"
188 del_op_entry = entry->change.flags & TT_CLIENT_DEL;
189 if (!del_op_requested && del_op_entry)
191 if (del_op_requested && !del_op_entry)
195 list_del(&entry->list);
197 event_removed = true;
201 /* track the change in the OGMinterval list */
202 list_add_tail(&tt_change_node->list, &bat_priv->tt_changes_list);
205 spin_unlock_bh(&bat_priv->tt_changes_list_lock);
208 atomic_dec(&bat_priv->tt_local_changes);
210 atomic_inc(&bat_priv->tt_local_changes);
213 int batadv_tt_len(int changes_num)
215 return changes_num * sizeof(struct tt_change);
218 static int batadv_tt_local_init(struct bat_priv *bat_priv)
220 if (bat_priv->tt_local_hash)
223 bat_priv->tt_local_hash = batadv_hash_new(1024);
225 if (!bat_priv->tt_local_hash)
231 void batadv_tt_local_add(struct net_device *soft_iface, const uint8_t *addr,
234 struct bat_priv *bat_priv = netdev_priv(soft_iface);
235 struct tt_local_entry *tt_local_entry = NULL;
236 struct tt_global_entry *tt_global_entry = NULL;
237 struct hlist_head *head;
238 struct hlist_node *node;
239 struct tt_orig_list_entry *orig_entry;
242 tt_local_entry = batadv_tt_local_hash_find(bat_priv, addr);
244 if (tt_local_entry) {
245 tt_local_entry->last_seen = jiffies;
246 /* possibly unset the TT_CLIENT_PENDING flag */
247 tt_local_entry->common.flags &= ~TT_CLIENT_PENDING;
251 tt_local_entry = kmalloc(sizeof(*tt_local_entry), GFP_ATOMIC);
255 batadv_dbg(DBG_TT, bat_priv,
256 "Creating new local tt entry: %pM (ttvn: %d)\n", addr,
257 (uint8_t)atomic_read(&bat_priv->ttvn));
259 memcpy(tt_local_entry->common.addr, addr, ETH_ALEN);
260 tt_local_entry->common.flags = BATADV_NO_FLAGS;
261 if (batadv_is_wifi_iface(ifindex))
262 tt_local_entry->common.flags |= TT_CLIENT_WIFI;
263 atomic_set(&tt_local_entry->common.refcount, 2);
264 tt_local_entry->last_seen = jiffies;
266 /* the batman interface mac address should never be purged */
267 if (batadv_compare_eth(addr, soft_iface->dev_addr))
268 tt_local_entry->common.flags |= TT_CLIENT_NOPURGE;
270 /* The local entry has to be marked as NEW to avoid to send it in
271 * a full table response going out before the next ttvn increment
272 * (consistency check)
274 tt_local_entry->common.flags |= TT_CLIENT_NEW;
276 hash_added = batadv_hash_add(bat_priv->tt_local_hash, batadv_compare_tt,
278 &tt_local_entry->common,
279 &tt_local_entry->common.hash_entry);
281 if (unlikely(hash_added != 0)) {
282 /* remove the reference for the hash */
283 batadv_tt_local_entry_free_ref(tt_local_entry);
287 batadv_tt_local_event(bat_priv, addr, tt_local_entry->common.flags);
289 /* remove address from global hash if present */
290 tt_global_entry = batadv_tt_global_hash_find(bat_priv, addr);
292 /* Check whether it is a roaming! */
293 if (tt_global_entry) {
294 /* These node are probably going to update their tt table */
295 head = &tt_global_entry->orig_list;
297 hlist_for_each_entry_rcu(orig_entry, node, head, list) {
298 orig_entry->orig_node->tt_poss_change = true;
300 batadv_send_roam_adv(bat_priv,
301 tt_global_entry->common.addr,
302 orig_entry->orig_node);
305 /* The global entry has to be marked as ROAMING and
306 * has to be kept for consistency purpose
308 tt_global_entry->common.flags |= TT_CLIENT_ROAM;
309 tt_global_entry->roam_at = jiffies;
313 batadv_tt_local_entry_free_ref(tt_local_entry);
315 batadv_tt_global_entry_free_ref(tt_global_entry);
318 static void batadv_tt_realloc_packet_buff(unsigned char **packet_buff,
319 int *packet_buff_len,
323 unsigned char *new_buff;
325 new_buff = kmalloc(new_packet_len, GFP_ATOMIC);
327 /* keep old buffer if kmalloc should fail */
329 memcpy(new_buff, *packet_buff, min_packet_len);
331 *packet_buff = new_buff;
332 *packet_buff_len = new_packet_len;
336 static void batadv_tt_prepare_packet_buff(struct bat_priv *bat_priv,
337 unsigned char **packet_buff,
338 int *packet_buff_len,
341 struct hard_iface *primary_if;
344 primary_if = batadv_primary_if_get_selected(bat_priv);
346 req_len = min_packet_len;
347 req_len += batadv_tt_len(atomic_read(&bat_priv->tt_local_changes));
349 /* if we have too many changes for one packet don't send any
350 * and wait for the tt table request which will be fragmented
352 if ((!primary_if) || (req_len > primary_if->soft_iface->mtu))
353 req_len = min_packet_len;
355 batadv_tt_realloc_packet_buff(packet_buff, packet_buff_len,
356 min_packet_len, req_len);
359 batadv_hardif_free_ref(primary_if);
362 static int batadv_tt_changes_fill_buff(struct bat_priv *bat_priv,
363 unsigned char **packet_buff,
364 int *packet_buff_len,
367 struct tt_change_node *entry, *safe;
368 int count = 0, tot_changes = 0, new_len;
369 unsigned char *tt_buff;
371 batadv_tt_prepare_packet_buff(bat_priv, packet_buff,
372 packet_buff_len, min_packet_len);
374 new_len = *packet_buff_len - min_packet_len;
375 tt_buff = *packet_buff + min_packet_len;
378 tot_changes = new_len / batadv_tt_len(1);
380 spin_lock_bh(&bat_priv->tt_changes_list_lock);
381 atomic_set(&bat_priv->tt_local_changes, 0);
383 list_for_each_entry_safe(entry, safe, &bat_priv->tt_changes_list,
385 if (count < tot_changes) {
386 memcpy(tt_buff + batadv_tt_len(count),
387 &entry->change, sizeof(struct tt_change));
390 list_del(&entry->list);
393 spin_unlock_bh(&bat_priv->tt_changes_list_lock);
395 /* Keep the buffer for possible tt_request */
396 spin_lock_bh(&bat_priv->tt_buff_lock);
397 kfree(bat_priv->tt_buff);
398 bat_priv->tt_buff_len = 0;
399 bat_priv->tt_buff = NULL;
400 /* check whether this new OGM has no changes due to size problems */
402 /* if kmalloc() fails we will reply with the full table
403 * instead of providing the diff
405 bat_priv->tt_buff = kmalloc(new_len, GFP_ATOMIC);
406 if (bat_priv->tt_buff) {
407 memcpy(bat_priv->tt_buff, tt_buff, new_len);
408 bat_priv->tt_buff_len = new_len;
411 spin_unlock_bh(&bat_priv->tt_buff_lock);
416 int batadv_tt_local_seq_print_text(struct seq_file *seq, void *offset)
418 struct net_device *net_dev = (struct net_device *)seq->private;
419 struct bat_priv *bat_priv = netdev_priv(net_dev);
420 struct hashtable_t *hash = bat_priv->tt_local_hash;
421 struct tt_common_entry *tt_common_entry;
422 struct hard_iface *primary_if;
423 struct hlist_node *node;
424 struct hlist_head *head;
428 primary_if = batadv_primary_if_get_selected(bat_priv);
430 ret = seq_printf(seq,
431 "BATMAN mesh %s disabled - please specify interfaces to enable it\n",
436 if (primary_if->if_status != IF_ACTIVE) {
437 ret = seq_printf(seq,
438 "BATMAN mesh %s disabled - primary interface not active\n",
444 "Locally retrieved addresses (from %s) announced via TT (TTVN: %u):\n",
445 net_dev->name, (uint8_t)atomic_read(&bat_priv->ttvn));
447 for (i = 0; i < hash->size; i++) {
448 head = &hash->table[i];
451 hlist_for_each_entry_rcu(tt_common_entry, node,
453 seq_printf(seq, " * %pM [%c%c%c%c%c]\n",
454 tt_common_entry->addr,
455 (tt_common_entry->flags &
456 TT_CLIENT_ROAM ? 'R' : '.'),
457 (tt_common_entry->flags &
458 TT_CLIENT_NOPURGE ? 'P' : '.'),
459 (tt_common_entry->flags &
460 TT_CLIENT_NEW ? 'N' : '.'),
461 (tt_common_entry->flags &
462 TT_CLIENT_PENDING ? 'X' : '.'),
463 (tt_common_entry->flags &
464 TT_CLIENT_WIFI ? 'W' : '.'));
470 batadv_hardif_free_ref(primary_if);
474 static void batadv_tt_local_set_pending(struct bat_priv *bat_priv,
475 struct tt_local_entry *tt_local_entry,
476 uint16_t flags, const char *message)
478 batadv_tt_local_event(bat_priv, tt_local_entry->common.addr,
479 tt_local_entry->common.flags | flags);
481 /* The local client has to be marked as "pending to be removed" but has
482 * to be kept in the table in order to send it in a full table
483 * response issued before the net ttvn increment (consistency check)
485 tt_local_entry->common.flags |= TT_CLIENT_PENDING;
487 batadv_dbg(DBG_TT, bat_priv,
488 "Local tt entry (%pM) pending to be removed: %s\n",
489 tt_local_entry->common.addr, message);
492 void batadv_tt_local_remove(struct bat_priv *bat_priv, const uint8_t *addr,
493 const char *message, bool roaming)
495 struct tt_local_entry *tt_local_entry = NULL;
498 tt_local_entry = batadv_tt_local_hash_find(bat_priv, addr);
502 flags = TT_CLIENT_DEL;
504 flags |= TT_CLIENT_ROAM;
506 batadv_tt_local_set_pending(bat_priv, tt_local_entry, flags, message);
509 batadv_tt_local_entry_free_ref(tt_local_entry);
512 static void batadv_tt_local_purge(struct bat_priv *bat_priv)
514 struct hashtable_t *hash = bat_priv->tt_local_hash;
515 struct tt_local_entry *tt_local_entry;
516 struct tt_common_entry *tt_common_entry;
517 struct hlist_node *node, *node_tmp;
518 struct hlist_head *head;
519 spinlock_t *list_lock; /* protects write access to the hash lists */
522 for (i = 0; i < hash->size; i++) {
523 head = &hash->table[i];
524 list_lock = &hash->list_locks[i];
526 spin_lock_bh(list_lock);
527 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
529 tt_local_entry = container_of(tt_common_entry,
530 struct tt_local_entry,
532 if (tt_local_entry->common.flags & TT_CLIENT_NOPURGE)
535 /* entry already marked for deletion */
536 if (tt_local_entry->common.flags & TT_CLIENT_PENDING)
539 if (!batadv_has_timed_out(tt_local_entry->last_seen,
540 BATADV_TT_LOCAL_TIMEOUT))
543 batadv_tt_local_set_pending(bat_priv, tt_local_entry,
544 TT_CLIENT_DEL, "timed out");
546 spin_unlock_bh(list_lock);
551 static void batadv_tt_local_table_free(struct bat_priv *bat_priv)
553 struct hashtable_t *hash;
554 spinlock_t *list_lock; /* protects write access to the hash lists */
555 struct tt_common_entry *tt_common_entry;
556 struct tt_local_entry *tt_local_entry;
557 struct hlist_node *node, *node_tmp;
558 struct hlist_head *head;
561 if (!bat_priv->tt_local_hash)
564 hash = bat_priv->tt_local_hash;
566 for (i = 0; i < hash->size; i++) {
567 head = &hash->table[i];
568 list_lock = &hash->list_locks[i];
570 spin_lock_bh(list_lock);
571 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
574 tt_local_entry = container_of(tt_common_entry,
575 struct tt_local_entry,
577 batadv_tt_local_entry_free_ref(tt_local_entry);
579 spin_unlock_bh(list_lock);
582 batadv_hash_destroy(hash);
584 bat_priv->tt_local_hash = NULL;
587 static int batadv_tt_global_init(struct bat_priv *bat_priv)
589 if (bat_priv->tt_global_hash)
592 bat_priv->tt_global_hash = batadv_hash_new(1024);
594 if (!bat_priv->tt_global_hash)
600 static void batadv_tt_changes_list_free(struct bat_priv *bat_priv)
602 struct tt_change_node *entry, *safe;
604 spin_lock_bh(&bat_priv->tt_changes_list_lock);
606 list_for_each_entry_safe(entry, safe, &bat_priv->tt_changes_list,
608 list_del(&entry->list);
612 atomic_set(&bat_priv->tt_local_changes, 0);
613 spin_unlock_bh(&bat_priv->tt_changes_list_lock);
616 /* find out if an orig_node is already in the list of a tt_global_entry.
617 * returns 1 if found, 0 otherwise
619 static bool batadv_tt_global_entry_has_orig(const struct tt_global_entry *entry,
620 const struct orig_node *orig_node)
622 struct tt_orig_list_entry *tmp_orig_entry;
623 const struct hlist_head *head;
624 struct hlist_node *node;
628 head = &entry->orig_list;
629 hlist_for_each_entry_rcu(tmp_orig_entry, node, head, list) {
630 if (tmp_orig_entry->orig_node == orig_node) {
640 batadv_tt_global_add_orig_entry(struct tt_global_entry *tt_global_entry,
641 struct orig_node *orig_node, int ttvn)
643 struct tt_orig_list_entry *orig_entry;
645 orig_entry = kzalloc(sizeof(*orig_entry), GFP_ATOMIC);
649 INIT_HLIST_NODE(&orig_entry->list);
650 atomic_inc(&orig_node->refcount);
651 atomic_inc(&orig_node->tt_size);
652 orig_entry->orig_node = orig_node;
653 orig_entry->ttvn = ttvn;
655 spin_lock_bh(&tt_global_entry->list_lock);
656 hlist_add_head_rcu(&orig_entry->list,
657 &tt_global_entry->orig_list);
658 spin_unlock_bh(&tt_global_entry->list_lock);
661 /* caller must hold orig_node refcount */
662 int batadv_tt_global_add(struct bat_priv *bat_priv, struct orig_node *orig_node,
663 const unsigned char *tt_addr, uint8_t flags,
666 struct tt_global_entry *tt_global_entry = NULL;
669 struct tt_common_entry *common;
671 tt_global_entry = batadv_tt_global_hash_find(bat_priv, tt_addr);
673 if (!tt_global_entry) {
674 tt_global_entry = kzalloc(sizeof(*tt_global_entry), GFP_ATOMIC);
675 if (!tt_global_entry)
678 common = &tt_global_entry->common;
679 memcpy(common->addr, tt_addr, ETH_ALEN);
681 common->flags = flags;
682 tt_global_entry->roam_at = 0;
683 atomic_set(&common->refcount, 2);
685 INIT_HLIST_HEAD(&tt_global_entry->orig_list);
686 spin_lock_init(&tt_global_entry->list_lock);
688 hash_added = batadv_hash_add(bat_priv->tt_global_hash,
690 batadv_choose_orig, common,
691 &common->hash_entry);
693 if (unlikely(hash_added != 0)) {
694 /* remove the reference for the hash */
695 batadv_tt_global_entry_free_ref(tt_global_entry);
699 batadv_tt_global_add_orig_entry(tt_global_entry, orig_node,
702 /* there is already a global entry, use this one. */
704 /* If there is the TT_CLIENT_ROAM flag set, there is only one
705 * originator left in the list and we previously received a
706 * delete + roaming change for this originator.
708 * We should first delete the old originator before adding the
711 if (tt_global_entry->common.flags & TT_CLIENT_ROAM) {
712 batadv_tt_global_del_orig_list(tt_global_entry);
713 tt_global_entry->common.flags &= ~TT_CLIENT_ROAM;
714 tt_global_entry->roam_at = 0;
717 if (!batadv_tt_global_entry_has_orig(tt_global_entry,
719 batadv_tt_global_add_orig_entry(tt_global_entry,
723 batadv_dbg(DBG_TT, bat_priv,
724 "Creating new global tt entry: %pM (via %pM)\n",
725 tt_global_entry->common.addr, orig_node->orig);
728 /* remove address from local hash if present */
729 batadv_tt_local_remove(bat_priv, tt_global_entry->common.addr,
730 "global tt received", flags & TT_CLIENT_ROAM);
734 batadv_tt_global_entry_free_ref(tt_global_entry);
738 /* print all orig nodes who announce the address for this global entry.
739 * it is assumed that the caller holds rcu_read_lock();
742 batadv_tt_global_print_entry(struct tt_global_entry *tt_global_entry,
743 struct seq_file *seq)
745 struct hlist_head *head;
746 struct hlist_node *node;
747 struct tt_orig_list_entry *orig_entry;
748 struct tt_common_entry *tt_common_entry;
752 tt_common_entry = &tt_global_entry->common;
754 head = &tt_global_entry->orig_list;
756 hlist_for_each_entry_rcu(orig_entry, node, head, list) {
757 flags = tt_common_entry->flags;
758 last_ttvn = atomic_read(&orig_entry->orig_node->last_ttvn);
759 seq_printf(seq, " * %pM (%3u) via %pM (%3u) [%c%c]\n",
760 tt_global_entry->common.addr, orig_entry->ttvn,
761 orig_entry->orig_node->orig, last_ttvn,
762 (flags & TT_CLIENT_ROAM ? 'R' : '.'),
763 (flags & TT_CLIENT_WIFI ? 'W' : '.'));
767 int batadv_tt_global_seq_print_text(struct seq_file *seq, void *offset)
769 struct net_device *net_dev = (struct net_device *)seq->private;
770 struct bat_priv *bat_priv = netdev_priv(net_dev);
771 struct hashtable_t *hash = bat_priv->tt_global_hash;
772 struct tt_common_entry *tt_common_entry;
773 struct tt_global_entry *tt_global_entry;
774 struct hard_iface *primary_if;
775 struct hlist_node *node;
776 struct hlist_head *head;
780 primary_if = batadv_primary_if_get_selected(bat_priv);
782 ret = seq_printf(seq,
783 "BATMAN mesh %s disabled - please specify interfaces to enable it\n",
788 if (primary_if->if_status != IF_ACTIVE) {
789 ret = seq_printf(seq,
790 "BATMAN mesh %s disabled - primary interface not active\n",
796 "Globally announced TT entries received via the mesh %s\n",
798 seq_printf(seq, " %-13s %s %-15s %s %s\n",
799 "Client", "(TTVN)", "Originator", "(Curr TTVN)", "Flags");
801 for (i = 0; i < hash->size; i++) {
802 head = &hash->table[i];
805 hlist_for_each_entry_rcu(tt_common_entry, node,
807 tt_global_entry = container_of(tt_common_entry,
808 struct tt_global_entry,
810 batadv_tt_global_print_entry(tt_global_entry, seq);
816 batadv_hardif_free_ref(primary_if);
820 /* deletes the orig list of a tt_global_entry */
822 batadv_tt_global_del_orig_list(struct tt_global_entry *tt_global_entry)
824 struct hlist_head *head;
825 struct hlist_node *node, *safe;
826 struct tt_orig_list_entry *orig_entry;
828 spin_lock_bh(&tt_global_entry->list_lock);
829 head = &tt_global_entry->orig_list;
830 hlist_for_each_entry_safe(orig_entry, node, safe, head, list) {
832 batadv_tt_orig_list_entry_free_ref(orig_entry);
834 spin_unlock_bh(&tt_global_entry->list_lock);
839 batadv_tt_global_del_orig_entry(struct bat_priv *bat_priv,
840 struct tt_global_entry *tt_global_entry,
841 struct orig_node *orig_node,
844 struct hlist_head *head;
845 struct hlist_node *node, *safe;
846 struct tt_orig_list_entry *orig_entry;
848 spin_lock_bh(&tt_global_entry->list_lock);
849 head = &tt_global_entry->orig_list;
850 hlist_for_each_entry_safe(orig_entry, node, safe, head, list) {
851 if (orig_entry->orig_node == orig_node) {
852 batadv_dbg(DBG_TT, bat_priv,
853 "Deleting %pM from global tt entry %pM: %s\n",
855 tt_global_entry->common.addr, message);
857 batadv_tt_orig_list_entry_free_ref(orig_entry);
860 spin_unlock_bh(&tt_global_entry->list_lock);
863 static void batadv_tt_global_del_struct(struct bat_priv *bat_priv,
864 struct tt_global_entry *tt_global_entry,
867 batadv_dbg(DBG_TT, bat_priv, "Deleting global tt entry %pM: %s\n",
868 tt_global_entry->common.addr, message);
870 batadv_hash_remove(bat_priv->tt_global_hash, batadv_compare_tt,
871 batadv_choose_orig, tt_global_entry->common.addr);
872 batadv_tt_global_entry_free_ref(tt_global_entry);
876 /* If the client is to be deleted, we check if it is the last origantor entry
877 * within tt_global entry. If yes, we set the TT_CLIENT_ROAM flag and the timer,
878 * otherwise we simply remove the originator scheduled for deletion.
881 batadv_tt_global_del_roaming(struct bat_priv *bat_priv,
882 struct tt_global_entry *tt_global_entry,
883 struct orig_node *orig_node, const char *message)
885 bool last_entry = true;
886 struct hlist_head *head;
887 struct hlist_node *node;
888 struct tt_orig_list_entry *orig_entry;
890 /* no local entry exists, case 1:
891 * Check if this is the last one or if other entries exist.
895 head = &tt_global_entry->orig_list;
896 hlist_for_each_entry_rcu(orig_entry, node, head, list) {
897 if (orig_entry->orig_node != orig_node) {
905 /* its the last one, mark for roaming. */
906 tt_global_entry->common.flags |= TT_CLIENT_ROAM;
907 tt_global_entry->roam_at = jiffies;
909 /* there is another entry, we can simply delete this
910 * one and can still use the other one.
912 batadv_tt_global_del_orig_entry(bat_priv, tt_global_entry,
918 static void batadv_tt_global_del(struct bat_priv *bat_priv,
919 struct orig_node *orig_node,
920 const unsigned char *addr,
921 const char *message, bool roaming)
923 struct tt_global_entry *tt_global_entry = NULL;
924 struct tt_local_entry *local_entry = NULL;
926 tt_global_entry = batadv_tt_global_hash_find(bat_priv, addr);
927 if (!tt_global_entry)
931 batadv_tt_global_del_orig_entry(bat_priv, tt_global_entry,
934 if (hlist_empty(&tt_global_entry->orig_list))
935 batadv_tt_global_del_struct(bat_priv, tt_global_entry,
941 /* if we are deleting a global entry due to a roam
942 * event, there are two possibilities:
943 * 1) the client roamed from node A to node B => if there
944 * is only one originator left for this client, we mark
945 * it with TT_CLIENT_ROAM, we start a timer and we
946 * wait for node B to claim it. In case of timeout
947 * the entry is purged.
949 * If there are other originators left, we directly delete
951 * 2) the client roamed to us => we can directly delete
952 * the global entry, since it is useless now.
954 local_entry = batadv_tt_local_hash_find(bat_priv,
955 tt_global_entry->common.addr);
957 /* local entry exists, case 2: client roamed to us. */
958 batadv_tt_global_del_orig_list(tt_global_entry);
959 batadv_tt_global_del_struct(bat_priv, tt_global_entry, message);
961 /* no local entry exists, case 1: check for roaming */
962 batadv_tt_global_del_roaming(bat_priv, tt_global_entry,
968 batadv_tt_global_entry_free_ref(tt_global_entry);
970 batadv_tt_local_entry_free_ref(local_entry);
973 void batadv_tt_global_del_orig(struct bat_priv *bat_priv,
974 struct orig_node *orig_node, const char *message)
976 struct tt_global_entry *global_entry;
977 struct tt_common_entry *tt_common_entry;
979 struct hashtable_t *hash = bat_priv->tt_global_hash;
980 struct hlist_node *node, *safe;
981 struct hlist_head *head;
982 spinlock_t *list_lock; /* protects write access to the hash lists */
987 for (i = 0; i < hash->size; i++) {
988 head = &hash->table[i];
989 list_lock = &hash->list_locks[i];
991 spin_lock_bh(list_lock);
992 hlist_for_each_entry_safe(tt_common_entry, node, safe,
994 global_entry = container_of(tt_common_entry,
995 struct tt_global_entry,
998 batadv_tt_global_del_orig_entry(bat_priv, global_entry,
1001 if (hlist_empty(&global_entry->orig_list)) {
1002 batadv_dbg(DBG_TT, bat_priv,
1003 "Deleting global tt entry %pM: %s\n",
1004 global_entry->common.addr, message);
1005 hlist_del_rcu(node);
1006 batadv_tt_global_entry_free_ref(global_entry);
1009 spin_unlock_bh(list_lock);
1011 orig_node->tt_initialised = false;
1014 static void batadv_tt_global_roam_purge_list(struct bat_priv *bat_priv,
1015 struct hlist_head *head)
1017 struct tt_common_entry *tt_common_entry;
1018 struct tt_global_entry *tt_global_entry;
1019 struct hlist_node *node, *node_tmp;
1021 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp, head,
1023 tt_global_entry = container_of(tt_common_entry,
1024 struct tt_global_entry, common);
1025 if (!(tt_global_entry->common.flags & TT_CLIENT_ROAM))
1027 if (!batadv_has_timed_out(tt_global_entry->roam_at,
1028 BATADV_TT_CLIENT_ROAM_TIMEOUT))
1031 batadv_dbg(DBG_TT, bat_priv,
1032 "Deleting global tt entry (%pM): Roaming timeout\n",
1033 tt_global_entry->common.addr);
1035 hlist_del_rcu(node);
1036 batadv_tt_global_entry_free_ref(tt_global_entry);
1040 static void batadv_tt_global_roam_purge(struct bat_priv *bat_priv)
1042 struct hashtable_t *hash = bat_priv->tt_global_hash;
1043 struct hlist_head *head;
1044 spinlock_t *list_lock; /* protects write access to the hash lists */
1047 for (i = 0; i < hash->size; i++) {
1048 head = &hash->table[i];
1049 list_lock = &hash->list_locks[i];
1051 spin_lock_bh(list_lock);
1052 batadv_tt_global_roam_purge_list(bat_priv, head);
1053 spin_unlock_bh(list_lock);
1058 static void batadv_tt_global_table_free(struct bat_priv *bat_priv)
1060 struct hashtable_t *hash;
1061 spinlock_t *list_lock; /* protects write access to the hash lists */
1062 struct tt_common_entry *tt_common_entry;
1063 struct tt_global_entry *tt_global_entry;
1064 struct hlist_node *node, *node_tmp;
1065 struct hlist_head *head;
1068 if (!bat_priv->tt_global_hash)
1071 hash = bat_priv->tt_global_hash;
1073 for (i = 0; i < hash->size; i++) {
1074 head = &hash->table[i];
1075 list_lock = &hash->list_locks[i];
1077 spin_lock_bh(list_lock);
1078 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
1080 hlist_del_rcu(node);
1081 tt_global_entry = container_of(tt_common_entry,
1082 struct tt_global_entry,
1084 batadv_tt_global_entry_free_ref(tt_global_entry);
1086 spin_unlock_bh(list_lock);
1089 batadv_hash_destroy(hash);
1091 bat_priv->tt_global_hash = NULL;
1094 static bool _batadv_is_ap_isolated(struct tt_local_entry *tt_local_entry,
1095 struct tt_global_entry *tt_global_entry)
1099 if (tt_local_entry->common.flags & TT_CLIENT_WIFI &&
1100 tt_global_entry->common.flags & TT_CLIENT_WIFI)
1106 struct orig_node *batadv_transtable_search(struct bat_priv *bat_priv,
1108 const uint8_t *addr)
1110 struct tt_local_entry *tt_local_entry = NULL;
1111 struct tt_global_entry *tt_global_entry = NULL;
1112 struct orig_node *orig_node = NULL;
1113 struct neigh_node *router = NULL;
1114 struct hlist_head *head;
1115 struct hlist_node *node;
1116 struct tt_orig_list_entry *orig_entry;
1119 if (src && atomic_read(&bat_priv->ap_isolation)) {
1120 tt_local_entry = batadv_tt_local_hash_find(bat_priv, src);
1121 if (!tt_local_entry)
1125 tt_global_entry = batadv_tt_global_hash_find(bat_priv, addr);
1126 if (!tt_global_entry)
1129 /* check whether the clients should not communicate due to AP
1132 if (tt_local_entry &&
1133 _batadv_is_ap_isolated(tt_local_entry, tt_global_entry))
1139 head = &tt_global_entry->orig_list;
1140 hlist_for_each_entry_rcu(orig_entry, node, head, list) {
1141 router = batadv_orig_node_get_router(orig_entry->orig_node);
1145 if (router->tq_avg > best_tq) {
1146 orig_node = orig_entry->orig_node;
1147 best_tq = router->tq_avg;
1149 batadv_neigh_node_free_ref(router);
1151 /* found anything? */
1152 if (orig_node && !atomic_inc_not_zero(&orig_node->refcount))
1156 if (tt_global_entry)
1157 batadv_tt_global_entry_free_ref(tt_global_entry);
1159 batadv_tt_local_entry_free_ref(tt_local_entry);
1164 /* Calculates the checksum of the local table of a given orig_node */
1165 static uint16_t batadv_tt_global_crc(struct bat_priv *bat_priv,
1166 struct orig_node *orig_node)
1168 uint16_t total = 0, total_one;
1169 struct hashtable_t *hash = bat_priv->tt_global_hash;
1170 struct tt_common_entry *tt_common_entry;
1171 struct tt_global_entry *tt_global_entry;
1172 struct hlist_node *node;
1173 struct hlist_head *head;
1177 for (i = 0; i < hash->size; i++) {
1178 head = &hash->table[i];
1181 hlist_for_each_entry_rcu(tt_common_entry, node,
1183 tt_global_entry = container_of(tt_common_entry,
1184 struct tt_global_entry,
1186 /* Roaming clients are in the global table for
1187 * consistency only. They don't have to be
1188 * taken into account while computing the
1191 if (tt_global_entry->common.flags & TT_CLIENT_ROAM)
1194 /* find out if this global entry is announced by this
1197 if (!batadv_tt_global_entry_has_orig(tt_global_entry,
1202 for (j = 0; j < ETH_ALEN; j++)
1203 total_one = crc16_byte(total_one,
1204 tt_global_entry->common.addr[j]);
1213 /* Calculates the checksum of the local table */
1214 static uint16_t batadv_tt_local_crc(struct bat_priv *bat_priv)
1216 uint16_t total = 0, total_one;
1217 struct hashtable_t *hash = bat_priv->tt_local_hash;
1218 struct tt_common_entry *tt_common_entry;
1219 struct hlist_node *node;
1220 struct hlist_head *head;
1224 for (i = 0; i < hash->size; i++) {
1225 head = &hash->table[i];
1228 hlist_for_each_entry_rcu(tt_common_entry, node,
1230 /* not yet committed clients have not to be taken into
1231 * account while computing the CRC
1233 if (tt_common_entry->flags & TT_CLIENT_NEW)
1236 for (j = 0; j < ETH_ALEN; j++)
1237 total_one = crc16_byte(total_one,
1238 tt_common_entry->addr[j]);
1247 static void batadv_tt_req_list_free(struct bat_priv *bat_priv)
1249 struct tt_req_node *node, *safe;
1251 spin_lock_bh(&bat_priv->tt_req_list_lock);
1253 list_for_each_entry_safe(node, safe, &bat_priv->tt_req_list, list) {
1254 list_del(&node->list);
1258 spin_unlock_bh(&bat_priv->tt_req_list_lock);
1261 static void batadv_tt_save_orig_buffer(struct bat_priv *bat_priv,
1262 struct orig_node *orig_node,
1263 const unsigned char *tt_buff,
1264 uint8_t tt_num_changes)
1266 uint16_t tt_buff_len = batadv_tt_len(tt_num_changes);
1268 /* Replace the old buffer only if I received something in the
1269 * last OGM (the OGM could carry no changes)
1271 spin_lock_bh(&orig_node->tt_buff_lock);
1272 if (tt_buff_len > 0) {
1273 kfree(orig_node->tt_buff);
1274 orig_node->tt_buff_len = 0;
1275 orig_node->tt_buff = kmalloc(tt_buff_len, GFP_ATOMIC);
1276 if (orig_node->tt_buff) {
1277 memcpy(orig_node->tt_buff, tt_buff, tt_buff_len);
1278 orig_node->tt_buff_len = tt_buff_len;
1281 spin_unlock_bh(&orig_node->tt_buff_lock);
1284 static void batadv_tt_req_purge(struct bat_priv *bat_priv)
1286 struct tt_req_node *node, *safe;
1288 spin_lock_bh(&bat_priv->tt_req_list_lock);
1289 list_for_each_entry_safe(node, safe, &bat_priv->tt_req_list, list) {
1290 if (batadv_has_timed_out(node->issued_at,
1291 BATADV_TT_REQUEST_TIMEOUT)) {
1292 list_del(&node->list);
1296 spin_unlock_bh(&bat_priv->tt_req_list_lock);
1299 /* returns the pointer to the new tt_req_node struct if no request
1300 * has already been issued for this orig_node, NULL otherwise
1302 static struct tt_req_node *batadv_new_tt_req_node(struct bat_priv *bat_priv,
1303 struct orig_node *orig_node)
1305 struct tt_req_node *tt_req_node_tmp, *tt_req_node = NULL;
1307 spin_lock_bh(&bat_priv->tt_req_list_lock);
1308 list_for_each_entry(tt_req_node_tmp, &bat_priv->tt_req_list, list) {
1309 if (batadv_compare_eth(tt_req_node_tmp, orig_node) &&
1310 !batadv_has_timed_out(tt_req_node_tmp->issued_at,
1311 BATADV_TT_REQUEST_TIMEOUT))
1315 tt_req_node = kmalloc(sizeof(*tt_req_node), GFP_ATOMIC);
1319 memcpy(tt_req_node->addr, orig_node->orig, ETH_ALEN);
1320 tt_req_node->issued_at = jiffies;
1322 list_add(&tt_req_node->list, &bat_priv->tt_req_list);
1324 spin_unlock_bh(&bat_priv->tt_req_list_lock);
1328 /* data_ptr is useless here, but has to be kept to respect the prototype */
1329 static int batadv_tt_local_valid_entry(const void *entry_ptr,
1330 const void *data_ptr)
1332 const struct tt_common_entry *tt_common_entry = entry_ptr;
1334 if (tt_common_entry->flags & TT_CLIENT_NEW)
1339 static int batadv_tt_global_valid(const void *entry_ptr,
1340 const void *data_ptr)
1342 const struct tt_common_entry *tt_common_entry = entry_ptr;
1343 const struct tt_global_entry *tt_global_entry;
1344 const struct orig_node *orig_node = data_ptr;
1346 if (tt_common_entry->flags & TT_CLIENT_ROAM)
1349 tt_global_entry = container_of(tt_common_entry, struct tt_global_entry,
1352 return batadv_tt_global_entry_has_orig(tt_global_entry, orig_node);
1355 static struct sk_buff *
1356 batadv_tt_response_fill_table(uint16_t tt_len, uint8_t ttvn,
1357 struct hashtable_t *hash,
1358 struct hard_iface *primary_if,
1359 int (*valid_cb)(const void *, const void *),
1362 struct tt_common_entry *tt_common_entry;
1363 struct tt_query_packet *tt_response;
1364 struct tt_change *tt_change;
1365 struct hlist_node *node;
1366 struct hlist_head *head;
1367 struct sk_buff *skb = NULL;
1368 uint16_t tt_tot, tt_count;
1369 ssize_t tt_query_size = sizeof(struct tt_query_packet);
1372 if (tt_query_size + tt_len > primary_if->soft_iface->mtu) {
1373 tt_len = primary_if->soft_iface->mtu - tt_query_size;
1374 tt_len -= tt_len % sizeof(struct tt_change);
1376 tt_tot = tt_len / sizeof(struct tt_change);
1378 skb = dev_alloc_skb(tt_query_size + tt_len + ETH_HLEN);
1382 skb_reserve(skb, ETH_HLEN);
1383 tt_response = (struct tt_query_packet *)skb_put(skb,
1384 tt_query_size + tt_len);
1385 tt_response->ttvn = ttvn;
1387 tt_change = (struct tt_change *)(skb->data + tt_query_size);
1391 for (i = 0; i < hash->size; i++) {
1392 head = &hash->table[i];
1394 hlist_for_each_entry_rcu(tt_common_entry, node,
1396 if (tt_count == tt_tot)
1399 if ((valid_cb) && (!valid_cb(tt_common_entry, cb_data)))
1402 memcpy(tt_change->addr, tt_common_entry->addr,
1404 tt_change->flags = BATADV_NO_FLAGS;
1412 /* store in the message the number of entries we have successfully
1415 tt_response->tt_data = htons(tt_count);
1421 static int batadv_send_tt_request(struct bat_priv *bat_priv,
1422 struct orig_node *dst_orig_node,
1423 uint8_t ttvn, uint16_t tt_crc,
1426 struct sk_buff *skb = NULL;
1427 struct tt_query_packet *tt_request;
1428 struct neigh_node *neigh_node = NULL;
1429 struct hard_iface *primary_if;
1430 struct tt_req_node *tt_req_node = NULL;
1433 primary_if = batadv_primary_if_get_selected(bat_priv);
1437 /* The new tt_req will be issued only if I'm not waiting for a
1438 * reply from the same orig_node yet
1440 tt_req_node = batadv_new_tt_req_node(bat_priv, dst_orig_node);
1444 skb = dev_alloc_skb(sizeof(struct tt_query_packet) + ETH_HLEN);
1448 skb_reserve(skb, ETH_HLEN);
1450 tt_request = (struct tt_query_packet *)skb_put(skb,
1451 sizeof(struct tt_query_packet));
1453 tt_request->header.packet_type = BAT_TT_QUERY;
1454 tt_request->header.version = BATADV_COMPAT_VERSION;
1455 memcpy(tt_request->src, primary_if->net_dev->dev_addr, ETH_ALEN);
1456 memcpy(tt_request->dst, dst_orig_node->orig, ETH_ALEN);
1457 tt_request->header.ttl = BATADV_TTL;
1458 tt_request->ttvn = ttvn;
1459 tt_request->tt_data = htons(tt_crc);
1460 tt_request->flags = TT_REQUEST;
1463 tt_request->flags |= TT_FULL_TABLE;
1465 neigh_node = batadv_orig_node_get_router(dst_orig_node);
1469 batadv_dbg(DBG_TT, bat_priv,
1470 "Sending TT_REQUEST to %pM via %pM [%c]\n",
1471 dst_orig_node->orig, neigh_node->addr,
1472 (full_table ? 'F' : '.'));
1474 batadv_inc_counter(bat_priv, BAT_CNT_TT_REQUEST_TX);
1476 batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr);
1481 batadv_neigh_node_free_ref(neigh_node);
1483 batadv_hardif_free_ref(primary_if);
1486 if (ret && tt_req_node) {
1487 spin_lock_bh(&bat_priv->tt_req_list_lock);
1488 list_del(&tt_req_node->list);
1489 spin_unlock_bh(&bat_priv->tt_req_list_lock);
1495 static bool batadv_send_other_tt_response(struct bat_priv *bat_priv,
1496 struct tt_query_packet *tt_request)
1498 struct orig_node *req_dst_orig_node = NULL, *res_dst_orig_node = NULL;
1499 struct neigh_node *neigh_node = NULL;
1500 struct hard_iface *primary_if = NULL;
1501 uint8_t orig_ttvn, req_ttvn, ttvn;
1503 unsigned char *tt_buff;
1505 uint16_t tt_len, tt_tot;
1506 struct sk_buff *skb = NULL;
1507 struct tt_query_packet *tt_response;
1509 batadv_dbg(DBG_TT, bat_priv,
1510 "Received TT_REQUEST from %pM for ttvn: %u (%pM) [%c]\n",
1511 tt_request->src, tt_request->ttvn, tt_request->dst,
1512 (tt_request->flags & TT_FULL_TABLE ? 'F' : '.'));
1514 /* Let's get the orig node of the REAL destination */
1515 req_dst_orig_node = batadv_orig_hash_find(bat_priv, tt_request->dst);
1516 if (!req_dst_orig_node)
1519 res_dst_orig_node = batadv_orig_hash_find(bat_priv, tt_request->src);
1520 if (!res_dst_orig_node)
1523 neigh_node = batadv_orig_node_get_router(res_dst_orig_node);
1527 primary_if = batadv_primary_if_get_selected(bat_priv);
1531 orig_ttvn = (uint8_t)atomic_read(&req_dst_orig_node->last_ttvn);
1532 req_ttvn = tt_request->ttvn;
1534 /* I don't have the requested data */
1535 if (orig_ttvn != req_ttvn ||
1536 tt_request->tt_data != htons(req_dst_orig_node->tt_crc))
1539 /* If the full table has been explicitly requested */
1540 if (tt_request->flags & TT_FULL_TABLE ||
1541 !req_dst_orig_node->tt_buff)
1546 /* In this version, fragmentation is not implemented, then
1547 * I'll send only one packet with as much TT entries as I can
1550 spin_lock_bh(&req_dst_orig_node->tt_buff_lock);
1551 tt_len = req_dst_orig_node->tt_buff_len;
1552 tt_tot = tt_len / sizeof(struct tt_change);
1554 skb = dev_alloc_skb(sizeof(struct tt_query_packet) +
1559 skb_reserve(skb, ETH_HLEN);
1560 tt_response = (struct tt_query_packet *)skb_put(skb,
1561 sizeof(struct tt_query_packet) + tt_len);
1562 tt_response->ttvn = req_ttvn;
1563 tt_response->tt_data = htons(tt_tot);
1565 tt_buff = skb->data + sizeof(struct tt_query_packet);
1566 /* Copy the last orig_node's OGM buffer */
1567 memcpy(tt_buff, req_dst_orig_node->tt_buff,
1568 req_dst_orig_node->tt_buff_len);
1570 spin_unlock_bh(&req_dst_orig_node->tt_buff_lock);
1572 tt_len = (uint16_t)atomic_read(&req_dst_orig_node->tt_size) *
1573 sizeof(struct tt_change);
1574 ttvn = (uint8_t)atomic_read(&req_dst_orig_node->last_ttvn);
1576 skb = batadv_tt_response_fill_table(tt_len, ttvn,
1577 bat_priv->tt_global_hash,
1579 batadv_tt_global_valid,
1584 tt_response = (struct tt_query_packet *)skb->data;
1587 tt_response->header.packet_type = BAT_TT_QUERY;
1588 tt_response->header.version = BATADV_COMPAT_VERSION;
1589 tt_response->header.ttl = BATADV_TTL;
1590 memcpy(tt_response->src, req_dst_orig_node->orig, ETH_ALEN);
1591 memcpy(tt_response->dst, tt_request->src, ETH_ALEN);
1592 tt_response->flags = TT_RESPONSE;
1595 tt_response->flags |= TT_FULL_TABLE;
1597 batadv_dbg(DBG_TT, bat_priv,
1598 "Sending TT_RESPONSE %pM via %pM for %pM (ttvn: %u)\n",
1599 res_dst_orig_node->orig, neigh_node->addr,
1600 req_dst_orig_node->orig, req_ttvn);
1602 batadv_inc_counter(bat_priv, BAT_CNT_TT_RESPONSE_TX);
1604 batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr);
1609 spin_unlock_bh(&req_dst_orig_node->tt_buff_lock);
1612 if (res_dst_orig_node)
1613 batadv_orig_node_free_ref(res_dst_orig_node);
1614 if (req_dst_orig_node)
1615 batadv_orig_node_free_ref(req_dst_orig_node);
1617 batadv_neigh_node_free_ref(neigh_node);
1619 batadv_hardif_free_ref(primary_if);
1625 static bool batadv_send_my_tt_response(struct bat_priv *bat_priv,
1626 struct tt_query_packet *tt_request)
1628 struct orig_node *orig_node = NULL;
1629 struct neigh_node *neigh_node = NULL;
1630 struct hard_iface *primary_if = NULL;
1631 uint8_t my_ttvn, req_ttvn, ttvn;
1633 unsigned char *tt_buff;
1635 uint16_t tt_len, tt_tot;
1636 struct sk_buff *skb = NULL;
1637 struct tt_query_packet *tt_response;
1639 batadv_dbg(DBG_TT, bat_priv,
1640 "Received TT_REQUEST from %pM for ttvn: %u (me) [%c]\n",
1641 tt_request->src, tt_request->ttvn,
1642 (tt_request->flags & TT_FULL_TABLE ? 'F' : '.'));
1645 my_ttvn = (uint8_t)atomic_read(&bat_priv->ttvn);
1646 req_ttvn = tt_request->ttvn;
1648 orig_node = batadv_orig_hash_find(bat_priv, tt_request->src);
1652 neigh_node = batadv_orig_node_get_router(orig_node);
1656 primary_if = batadv_primary_if_get_selected(bat_priv);
1660 /* If the full table has been explicitly requested or the gap
1661 * is too big send the whole local translation table
1663 if (tt_request->flags & TT_FULL_TABLE || my_ttvn != req_ttvn ||
1669 /* In this version, fragmentation is not implemented, then
1670 * I'll send only one packet with as much TT entries as I can
1673 spin_lock_bh(&bat_priv->tt_buff_lock);
1674 tt_len = bat_priv->tt_buff_len;
1675 tt_tot = tt_len / sizeof(struct tt_change);
1677 skb = dev_alloc_skb(sizeof(struct tt_query_packet) +
1682 skb_reserve(skb, ETH_HLEN);
1683 tt_response = (struct tt_query_packet *)skb_put(skb,
1684 sizeof(struct tt_query_packet) + tt_len);
1685 tt_response->ttvn = req_ttvn;
1686 tt_response->tt_data = htons(tt_tot);
1688 tt_buff = skb->data + sizeof(struct tt_query_packet);
1689 memcpy(tt_buff, bat_priv->tt_buff,
1690 bat_priv->tt_buff_len);
1691 spin_unlock_bh(&bat_priv->tt_buff_lock);
1693 tt_len = (uint16_t)atomic_read(&bat_priv->num_local_tt) *
1694 sizeof(struct tt_change);
1695 ttvn = (uint8_t)atomic_read(&bat_priv->ttvn);
1697 skb = batadv_tt_response_fill_table(tt_len, ttvn,
1698 bat_priv->tt_local_hash,
1700 batadv_tt_local_valid_entry,
1705 tt_response = (struct tt_query_packet *)skb->data;
1708 tt_response->header.packet_type = BAT_TT_QUERY;
1709 tt_response->header.version = BATADV_COMPAT_VERSION;
1710 tt_response->header.ttl = BATADV_TTL;
1711 memcpy(tt_response->src, primary_if->net_dev->dev_addr, ETH_ALEN);
1712 memcpy(tt_response->dst, tt_request->src, ETH_ALEN);
1713 tt_response->flags = TT_RESPONSE;
1716 tt_response->flags |= TT_FULL_TABLE;
1718 batadv_dbg(DBG_TT, bat_priv,
1719 "Sending TT_RESPONSE to %pM via %pM [%c]\n",
1720 orig_node->orig, neigh_node->addr,
1721 (tt_response->flags & TT_FULL_TABLE ? 'F' : '.'));
1723 batadv_inc_counter(bat_priv, BAT_CNT_TT_RESPONSE_TX);
1725 batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr);
1730 spin_unlock_bh(&bat_priv->tt_buff_lock);
1733 batadv_orig_node_free_ref(orig_node);
1735 batadv_neigh_node_free_ref(neigh_node);
1737 batadv_hardif_free_ref(primary_if);
1740 /* This packet was for me, so it doesn't need to be re-routed */
1744 bool batadv_send_tt_response(struct bat_priv *bat_priv,
1745 struct tt_query_packet *tt_request)
1747 if (batadv_is_my_mac(tt_request->dst)) {
1748 /* don't answer backbone gws! */
1749 if (batadv_bla_is_backbone_gw_orig(bat_priv, tt_request->src))
1752 return batadv_send_my_tt_response(bat_priv, tt_request);
1754 return batadv_send_other_tt_response(bat_priv, tt_request);
1758 static void _batadv_tt_update_changes(struct bat_priv *bat_priv,
1759 struct orig_node *orig_node,
1760 struct tt_change *tt_change,
1761 uint16_t tt_num_changes, uint8_t ttvn)
1766 for (i = 0; i < tt_num_changes; i++) {
1767 if ((tt_change + i)->flags & TT_CLIENT_DEL) {
1768 roams = (tt_change + i)->flags & TT_CLIENT_ROAM;
1769 batadv_tt_global_del(bat_priv, orig_node,
1770 (tt_change + i)->addr,
1771 "tt removed by changes",
1774 if (!batadv_tt_global_add(bat_priv, orig_node,
1775 (tt_change + i)->addr,
1776 (tt_change + i)->flags, ttvn))
1777 /* In case of problem while storing a
1778 * global_entry, we stop the updating
1779 * procedure without committing the
1780 * ttvn change. This will avoid to send
1781 * corrupted data on tt_request
1786 orig_node->tt_initialised = true;
1789 static void batadv_tt_fill_gtable(struct bat_priv *bat_priv,
1790 struct tt_query_packet *tt_response)
1792 struct orig_node *orig_node = NULL;
1794 orig_node = batadv_orig_hash_find(bat_priv, tt_response->src);
1798 /* Purge the old table first.. */
1799 batadv_tt_global_del_orig(bat_priv, orig_node, "Received full table");
1801 _batadv_tt_update_changes(bat_priv, orig_node,
1802 (struct tt_change *)(tt_response + 1),
1803 ntohs(tt_response->tt_data),
1806 spin_lock_bh(&orig_node->tt_buff_lock);
1807 kfree(orig_node->tt_buff);
1808 orig_node->tt_buff_len = 0;
1809 orig_node->tt_buff = NULL;
1810 spin_unlock_bh(&orig_node->tt_buff_lock);
1812 atomic_set(&orig_node->last_ttvn, tt_response->ttvn);
1816 batadv_orig_node_free_ref(orig_node);
1819 static void batadv_tt_update_changes(struct bat_priv *bat_priv,
1820 struct orig_node *orig_node,
1821 uint16_t tt_num_changes, uint8_t ttvn,
1822 struct tt_change *tt_change)
1824 _batadv_tt_update_changes(bat_priv, orig_node, tt_change,
1825 tt_num_changes, ttvn);
1827 batadv_tt_save_orig_buffer(bat_priv, orig_node,
1828 (unsigned char *)tt_change, tt_num_changes);
1829 atomic_set(&orig_node->last_ttvn, ttvn);
1832 bool batadv_is_my_client(struct bat_priv *bat_priv, const uint8_t *addr)
1834 struct tt_local_entry *tt_local_entry = NULL;
1837 tt_local_entry = batadv_tt_local_hash_find(bat_priv, addr);
1838 if (!tt_local_entry)
1840 /* Check if the client has been logically deleted (but is kept for
1841 * consistency purpose)
1843 if (tt_local_entry->common.flags & TT_CLIENT_PENDING)
1848 batadv_tt_local_entry_free_ref(tt_local_entry);
1852 void batadv_handle_tt_response(struct bat_priv *bat_priv,
1853 struct tt_query_packet *tt_response)
1855 struct tt_req_node *node, *safe;
1856 struct orig_node *orig_node = NULL;
1858 batadv_dbg(DBG_TT, bat_priv,
1859 "Received TT_RESPONSE from %pM for ttvn %d t_size: %d [%c]\n",
1860 tt_response->src, tt_response->ttvn,
1861 ntohs(tt_response->tt_data),
1862 (tt_response->flags & TT_FULL_TABLE ? 'F' : '.'));
1864 /* we should have never asked a backbone gw */
1865 if (batadv_bla_is_backbone_gw_orig(bat_priv, tt_response->src))
1868 orig_node = batadv_orig_hash_find(bat_priv, tt_response->src);
1872 if (tt_response->flags & TT_FULL_TABLE)
1873 batadv_tt_fill_gtable(bat_priv, tt_response);
1875 batadv_tt_update_changes(bat_priv, orig_node,
1876 ntohs(tt_response->tt_data),
1878 (struct tt_change *)(tt_response + 1));
1880 /* Delete the tt_req_node from pending tt_requests list */
1881 spin_lock_bh(&bat_priv->tt_req_list_lock);
1882 list_for_each_entry_safe(node, safe, &bat_priv->tt_req_list, list) {
1883 if (!batadv_compare_eth(node->addr, tt_response->src))
1885 list_del(&node->list);
1888 spin_unlock_bh(&bat_priv->tt_req_list_lock);
1890 /* Recalculate the CRC for this orig_node and store it */
1891 orig_node->tt_crc = batadv_tt_global_crc(bat_priv, orig_node);
1892 /* Roaming phase is over: tables are in sync again. I can
1895 orig_node->tt_poss_change = false;
1898 batadv_orig_node_free_ref(orig_node);
1901 int batadv_tt_init(struct bat_priv *bat_priv)
1905 ret = batadv_tt_local_init(bat_priv);
1909 ret = batadv_tt_global_init(bat_priv);
1913 batadv_tt_start_timer(bat_priv);
1918 static void batadv_tt_roam_list_free(struct bat_priv *bat_priv)
1920 struct tt_roam_node *node, *safe;
1922 spin_lock_bh(&bat_priv->tt_roam_list_lock);
1924 list_for_each_entry_safe(node, safe, &bat_priv->tt_roam_list, list) {
1925 list_del(&node->list);
1929 spin_unlock_bh(&bat_priv->tt_roam_list_lock);
1932 static void batadv_tt_roam_purge(struct bat_priv *bat_priv)
1934 struct tt_roam_node *node, *safe;
1936 spin_lock_bh(&bat_priv->tt_roam_list_lock);
1937 list_for_each_entry_safe(node, safe, &bat_priv->tt_roam_list, list) {
1938 if (!batadv_has_timed_out(node->first_time,
1939 BATADV_ROAMING_MAX_TIME))
1942 list_del(&node->list);
1945 spin_unlock_bh(&bat_priv->tt_roam_list_lock);
1948 /* This function checks whether the client already reached the
1949 * maximum number of possible roaming phases. In this case the ROAMING_ADV
1952 * returns true if the ROAMING_ADV can be sent, false otherwise
1954 static bool batadv_tt_check_roam_count(struct bat_priv *bat_priv,
1957 struct tt_roam_node *tt_roam_node;
1960 spin_lock_bh(&bat_priv->tt_roam_list_lock);
1961 /* The new tt_req will be issued only if I'm not waiting for a
1962 * reply from the same orig_node yet
1964 list_for_each_entry(tt_roam_node, &bat_priv->tt_roam_list, list) {
1965 if (!batadv_compare_eth(tt_roam_node->addr, client))
1968 if (batadv_has_timed_out(tt_roam_node->first_time,
1969 BATADV_ROAMING_MAX_TIME))
1972 if (!batadv_atomic_dec_not_zero(&tt_roam_node->counter))
1973 /* Sorry, you roamed too many times! */
1980 tt_roam_node = kmalloc(sizeof(*tt_roam_node), GFP_ATOMIC);
1984 tt_roam_node->first_time = jiffies;
1985 atomic_set(&tt_roam_node->counter,
1986 BATADV_ROAMING_MAX_COUNT - 1);
1987 memcpy(tt_roam_node->addr, client, ETH_ALEN);
1989 list_add(&tt_roam_node->list, &bat_priv->tt_roam_list);
1994 spin_unlock_bh(&bat_priv->tt_roam_list_lock);
1998 static void batadv_send_roam_adv(struct bat_priv *bat_priv, uint8_t *client,
1999 struct orig_node *orig_node)
2001 struct neigh_node *neigh_node = NULL;
2002 struct sk_buff *skb = NULL;
2003 struct roam_adv_packet *roam_adv_packet;
2005 struct hard_iface *primary_if;
2007 /* before going on we have to check whether the client has
2008 * already roamed to us too many times
2010 if (!batadv_tt_check_roam_count(bat_priv, client))
2013 skb = dev_alloc_skb(sizeof(struct roam_adv_packet) + ETH_HLEN);
2017 skb_reserve(skb, ETH_HLEN);
2019 roam_adv_packet = (struct roam_adv_packet *)skb_put(skb,
2020 sizeof(struct roam_adv_packet));
2022 roam_adv_packet->header.packet_type = BAT_ROAM_ADV;
2023 roam_adv_packet->header.version = BATADV_COMPAT_VERSION;
2024 roam_adv_packet->header.ttl = BATADV_TTL;
2025 primary_if = batadv_primary_if_get_selected(bat_priv);
2028 memcpy(roam_adv_packet->src, primary_if->net_dev->dev_addr, ETH_ALEN);
2029 batadv_hardif_free_ref(primary_if);
2030 memcpy(roam_adv_packet->dst, orig_node->orig, ETH_ALEN);
2031 memcpy(roam_adv_packet->client, client, ETH_ALEN);
2033 neigh_node = batadv_orig_node_get_router(orig_node);
2037 batadv_dbg(DBG_TT, bat_priv,
2038 "Sending ROAMING_ADV to %pM (client %pM) via %pM\n",
2039 orig_node->orig, client, neigh_node->addr);
2041 batadv_inc_counter(bat_priv, BAT_CNT_TT_ROAM_ADV_TX);
2043 batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr);
2048 batadv_neigh_node_free_ref(neigh_node);
2054 static void batadv_tt_purge(struct work_struct *work)
2056 struct delayed_work *delayed_work =
2057 container_of(work, struct delayed_work, work);
2058 struct bat_priv *bat_priv =
2059 container_of(delayed_work, struct bat_priv, tt_work);
2061 batadv_tt_local_purge(bat_priv);
2062 batadv_tt_global_roam_purge(bat_priv);
2063 batadv_tt_req_purge(bat_priv);
2064 batadv_tt_roam_purge(bat_priv);
2066 batadv_tt_start_timer(bat_priv);
2069 void batadv_tt_free(struct bat_priv *bat_priv)
2071 cancel_delayed_work_sync(&bat_priv->tt_work);
2073 batadv_tt_local_table_free(bat_priv);
2074 batadv_tt_global_table_free(bat_priv);
2075 batadv_tt_req_list_free(bat_priv);
2076 batadv_tt_changes_list_free(bat_priv);
2077 batadv_tt_roam_list_free(bat_priv);
2079 kfree(bat_priv->tt_buff);
2082 /* This function will enable or disable the specified flags for all the entries
2083 * in the given hash table and returns the number of modified entries
2085 static uint16_t batadv_tt_set_flags(struct hashtable_t *hash, uint16_t flags,
2089 uint16_t changed_num = 0;
2090 struct hlist_head *head;
2091 struct hlist_node *node;
2092 struct tt_common_entry *tt_common_entry;
2097 for (i = 0; i < hash->size; i++) {
2098 head = &hash->table[i];
2101 hlist_for_each_entry_rcu(tt_common_entry, node,
2104 if ((tt_common_entry->flags & flags) == flags)
2106 tt_common_entry->flags |= flags;
2108 if (!(tt_common_entry->flags & flags))
2110 tt_common_entry->flags &= ~flags;
2120 /* Purge out all the tt local entries marked with TT_CLIENT_PENDING */
2121 static void batadv_tt_local_purge_pending_clients(struct bat_priv *bat_priv)
2123 struct hashtable_t *hash = bat_priv->tt_local_hash;
2124 struct tt_common_entry *tt_common_entry;
2125 struct tt_local_entry *tt_local_entry;
2126 struct hlist_node *node, *node_tmp;
2127 struct hlist_head *head;
2128 spinlock_t *list_lock; /* protects write access to the hash lists */
2134 for (i = 0; i < hash->size; i++) {
2135 head = &hash->table[i];
2136 list_lock = &hash->list_locks[i];
2138 spin_lock_bh(list_lock);
2139 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
2141 if (!(tt_common_entry->flags & TT_CLIENT_PENDING))
2144 batadv_dbg(DBG_TT, bat_priv,
2145 "Deleting local tt entry (%pM): pending\n",
2146 tt_common_entry->addr);
2148 atomic_dec(&bat_priv->num_local_tt);
2149 hlist_del_rcu(node);
2150 tt_local_entry = container_of(tt_common_entry,
2151 struct tt_local_entry,
2153 batadv_tt_local_entry_free_ref(tt_local_entry);
2155 spin_unlock_bh(list_lock);
2160 static int batadv_tt_commit_changes(struct bat_priv *bat_priv,
2161 unsigned char **packet_buff,
2162 int *packet_buff_len, int packet_min_len)
2164 uint16_t changed_num = 0;
2166 if (atomic_read(&bat_priv->tt_local_changes) < 1)
2169 changed_num = batadv_tt_set_flags(bat_priv->tt_local_hash,
2170 TT_CLIENT_NEW, false);
2172 /* all reset entries have to be counted as local entries */
2173 atomic_add(changed_num, &bat_priv->num_local_tt);
2174 batadv_tt_local_purge_pending_clients(bat_priv);
2175 bat_priv->tt_crc = batadv_tt_local_crc(bat_priv);
2177 /* Increment the TTVN only once per OGM interval */
2178 atomic_inc(&bat_priv->ttvn);
2179 batadv_dbg(DBG_TT, bat_priv,
2180 "Local changes committed, updating to ttvn %u\n",
2181 (uint8_t)atomic_read(&bat_priv->ttvn));
2182 bat_priv->tt_poss_change = false;
2184 /* reset the sending counter */
2185 atomic_set(&bat_priv->tt_ogm_append_cnt, BATADV_TT_OGM_APPEND_MAX);
2187 return batadv_tt_changes_fill_buff(bat_priv, packet_buff,
2188 packet_buff_len, packet_min_len);
2191 /* when calling this function (hard_iface == primary_if) has to be true */
2192 int batadv_tt_append_diff(struct bat_priv *bat_priv,
2193 unsigned char **packet_buff, int *packet_buff_len,
2198 /* if at least one change happened */
2199 tt_num_changes = batadv_tt_commit_changes(bat_priv, packet_buff,
2203 /* if the changes have been sent often enough */
2204 if ((tt_num_changes < 0) &&
2205 (!batadv_atomic_dec_not_zero(&bat_priv->tt_ogm_append_cnt))) {
2206 batadv_tt_realloc_packet_buff(packet_buff, packet_buff_len,
2207 packet_min_len, packet_min_len);
2211 return tt_num_changes;
2214 bool batadv_is_ap_isolated(struct bat_priv *bat_priv, uint8_t *src,
2217 struct tt_local_entry *tt_local_entry = NULL;
2218 struct tt_global_entry *tt_global_entry = NULL;
2221 if (!atomic_read(&bat_priv->ap_isolation))
2224 tt_local_entry = batadv_tt_local_hash_find(bat_priv, dst);
2225 if (!tt_local_entry)
2228 tt_global_entry = batadv_tt_global_hash_find(bat_priv, src);
2229 if (!tt_global_entry)
2232 if (!_batadv_is_ap_isolated(tt_local_entry, tt_global_entry))
2238 if (tt_global_entry)
2239 batadv_tt_global_entry_free_ref(tt_global_entry);
2241 batadv_tt_local_entry_free_ref(tt_local_entry);
2245 void batadv_tt_update_orig(struct bat_priv *bat_priv,
2246 struct orig_node *orig_node,
2247 const unsigned char *tt_buff, uint8_t tt_num_changes,
2248 uint8_t ttvn, uint16_t tt_crc)
2250 uint8_t orig_ttvn = (uint8_t)atomic_read(&orig_node->last_ttvn);
2251 bool full_table = true;
2253 /* don't care about a backbone gateways updates. */
2254 if (batadv_bla_is_backbone_gw_orig(bat_priv, orig_node->orig))
2257 /* orig table not initialised AND first diff is in the OGM OR the ttvn
2258 * increased by one -> we can apply the attached changes
2260 if ((!orig_node->tt_initialised && ttvn == 1) ||
2261 ttvn - orig_ttvn == 1) {
2262 /* the OGM could not contain the changes due to their size or
2263 * because they have already been sent BATADV_TT_OGM_APPEND_MAX
2265 * In this case send a tt request
2267 if (!tt_num_changes) {
2272 batadv_tt_update_changes(bat_priv, orig_node, tt_num_changes,
2273 ttvn, (struct tt_change *)tt_buff);
2275 /* Even if we received the precomputed crc with the OGM, we
2276 * prefer to recompute it to spot any possible inconsistency
2277 * in the global table
2279 orig_node->tt_crc = batadv_tt_global_crc(bat_priv, orig_node);
2281 /* The ttvn alone is not enough to guarantee consistency
2282 * because a single value could represent different states
2283 * (due to the wrap around). Thus a node has to check whether
2284 * the resulting table (after applying the changes) is still
2285 * consistent or not. E.g. a node could disconnect while its
2286 * ttvn is X and reconnect on ttvn = X + TTVN_MAX: in this case
2287 * checking the CRC value is mandatory to detect the
2290 if (orig_node->tt_crc != tt_crc)
2293 /* Roaming phase is over: tables are in sync again. I can
2296 orig_node->tt_poss_change = false;
2298 /* if we missed more than one change or our tables are not
2299 * in sync anymore -> request fresh tt data
2301 if (!orig_node->tt_initialised || ttvn != orig_ttvn ||
2302 orig_node->tt_crc != tt_crc) {
2304 batadv_dbg(DBG_TT, bat_priv,
2305 "TT inconsistency for %pM. Need to retrieve the correct information (ttvn: %u last_ttvn: %u crc: %u last_crc: %u num_changes: %u)\n",
2306 orig_node->orig, ttvn, orig_ttvn, tt_crc,
2307 orig_node->tt_crc, tt_num_changes);
2308 batadv_send_tt_request(bat_priv, orig_node, ttvn,
2309 tt_crc, full_table);
2315 /* returns true whether we know that the client has moved from its old
2316 * originator to another one. This entry is kept is still kept for consistency
2319 bool batadv_tt_global_client_is_roaming(struct bat_priv *bat_priv,
2322 struct tt_global_entry *tt_global_entry;
2325 tt_global_entry = batadv_tt_global_hash_find(bat_priv, addr);
2326 if (!tt_global_entry)
2329 ret = tt_global_entry->common.flags & TT_CLIENT_ROAM;
2330 batadv_tt_global_entry_free_ref(tt_global_entry);