2 * Copyright (C) 2007-2012 B.A.T.M.A.N. contributors:
4 * Marek Lindner, Simon Wunderlich
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.
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.
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
23 #include "translation-table.h"
24 #include "soft-interface.h"
25 #include "hard-interface.h"
28 #include "originator.h"
30 #include "bridge_loop_avoidance.h"
32 #include <linux/crc16.h>
34 static void send_roam_adv(struct bat_priv
*bat_priv
, uint8_t *client
,
35 struct orig_node
*orig_node
);
36 static void tt_purge(struct work_struct
*work
);
37 static void tt_global_del_orig_list(struct tt_global_entry
*tt_global_entry
);
39 /* returns 1 if they are the same mac addr */
40 static int compare_tt(const struct hlist_node
*node
, const void *data2
)
42 const void *data1
= container_of(node
, struct tt_common_entry
,
45 return (memcmp(data1
, data2
, ETH_ALEN
) == 0 ? 1 : 0);
48 static void tt_start_timer(struct bat_priv
*bat_priv
)
50 INIT_DELAYED_WORK(&bat_priv
->tt_work
, tt_purge
);
51 queue_delayed_work(bat_event_workqueue
, &bat_priv
->tt_work
,
52 msecs_to_jiffies(5000));
55 static struct tt_common_entry
*tt_hash_find(struct hashtable_t
*hash
,
58 struct hlist_head
*head
;
59 struct hlist_node
*node
;
60 struct tt_common_entry
*tt_common_entry
, *tt_common_entry_tmp
= NULL
;
66 index
= choose_orig(data
, hash
->size
);
67 head
= &hash
->table
[index
];
70 hlist_for_each_entry_rcu(tt_common_entry
, node
, head
, hash_entry
) {
71 if (!compare_eth(tt_common_entry
, data
))
74 if (!atomic_inc_not_zero(&tt_common_entry
->refcount
))
77 tt_common_entry_tmp
= tt_common_entry
;
82 return tt_common_entry_tmp
;
85 static struct tt_local_entry
*tt_local_hash_find(struct bat_priv
*bat_priv
,
88 struct tt_common_entry
*tt_common_entry
;
89 struct tt_local_entry
*tt_local_entry
= NULL
;
91 tt_common_entry
= tt_hash_find(bat_priv
->tt_local_hash
, data
);
93 tt_local_entry
= container_of(tt_common_entry
,
94 struct tt_local_entry
, common
);
95 return tt_local_entry
;
98 static struct tt_global_entry
*tt_global_hash_find(struct bat_priv
*bat_priv
,
101 struct tt_common_entry
*tt_common_entry
;
102 struct tt_global_entry
*tt_global_entry
= NULL
;
104 tt_common_entry
= tt_hash_find(bat_priv
->tt_global_hash
, data
);
106 tt_global_entry
= container_of(tt_common_entry
,
107 struct tt_global_entry
, common
);
108 return tt_global_entry
;
112 static void 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 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
);
130 static void tt_global_entry_free_ref(struct tt_global_entry
*tt_global_entry
)
132 if (atomic_dec_and_test(&tt_global_entry
->common
.refcount
)) {
133 tt_global_del_orig_list(tt_global_entry
);
134 call_rcu(&tt_global_entry
->common
.rcu
,
135 tt_global_entry_free_rcu
);
139 static void tt_orig_list_entry_free_rcu(struct rcu_head
*rcu
)
141 struct tt_orig_list_entry
*orig_entry
;
143 orig_entry
= container_of(rcu
, struct tt_orig_list_entry
, rcu
);
144 atomic_dec(&orig_entry
->orig_node
->tt_size
);
145 orig_node_free_ref(orig_entry
->orig_node
);
149 static void tt_orig_list_entry_free_ref(struct tt_orig_list_entry
*orig_entry
)
151 call_rcu(&orig_entry
->rcu
, tt_orig_list_entry_free_rcu
);
154 static void tt_local_event(struct bat_priv
*bat_priv
, const uint8_t *addr
,
157 struct tt_change_node
*tt_change_node
;
159 tt_change_node
= kmalloc(sizeof(*tt_change_node
), GFP_ATOMIC
);
164 tt_change_node
->change
.flags
= flags
;
165 memcpy(tt_change_node
->change
.addr
, addr
, ETH_ALEN
);
167 spin_lock_bh(&bat_priv
->tt_changes_list_lock
);
168 /* track the change in the OGMinterval list */
169 list_add_tail(&tt_change_node
->list
, &bat_priv
->tt_changes_list
);
170 atomic_inc(&bat_priv
->tt_local_changes
);
171 spin_unlock_bh(&bat_priv
->tt_changes_list_lock
);
173 atomic_set(&bat_priv
->tt_ogm_append_cnt
, 0);
176 int tt_len(int changes_num
)
178 return changes_num
* sizeof(struct tt_change
);
181 static int tt_local_init(struct bat_priv
*bat_priv
)
183 if (bat_priv
->tt_local_hash
)
186 bat_priv
->tt_local_hash
= hash_new(1024);
188 if (!bat_priv
->tt_local_hash
)
194 void tt_local_add(struct net_device
*soft_iface
, const uint8_t *addr
,
197 struct bat_priv
*bat_priv
= netdev_priv(soft_iface
);
198 struct tt_local_entry
*tt_local_entry
= NULL
;
199 struct tt_global_entry
*tt_global_entry
= NULL
;
200 struct hlist_head
*head
;
201 struct hlist_node
*node
;
202 struct tt_orig_list_entry
*orig_entry
;
205 tt_local_entry
= tt_local_hash_find(bat_priv
, addr
);
207 if (tt_local_entry
) {
208 tt_local_entry
->last_seen
= jiffies
;
212 tt_local_entry
= kmalloc(sizeof(*tt_local_entry
), GFP_ATOMIC
);
216 bat_dbg(DBG_TT
, bat_priv
,
217 "Creating new local tt entry: %pM (ttvn: %d)\n", addr
,
218 (uint8_t)atomic_read(&bat_priv
->ttvn
));
220 memcpy(tt_local_entry
->common
.addr
, addr
, ETH_ALEN
);
221 tt_local_entry
->common
.flags
= NO_FLAGS
;
222 if (is_wifi_iface(ifindex
))
223 tt_local_entry
->common
.flags
|= TT_CLIENT_WIFI
;
224 atomic_set(&tt_local_entry
->common
.refcount
, 2);
225 tt_local_entry
->last_seen
= jiffies
;
227 /* the batman interface mac address should never be purged */
228 if (compare_eth(addr
, soft_iface
->dev_addr
))
229 tt_local_entry
->common
.flags
|= TT_CLIENT_NOPURGE
;
231 /* The local entry has to be marked as NEW to avoid to send it in
232 * a full table response going out before the next ttvn increment
233 * (consistency check) */
234 tt_local_entry
->common
.flags
|= TT_CLIENT_NEW
;
236 hash_added
= hash_add(bat_priv
->tt_local_hash
, compare_tt
, choose_orig
,
237 &tt_local_entry
->common
,
238 &tt_local_entry
->common
.hash_entry
);
240 if (unlikely(hash_added
!= 0)) {
241 /* remove the reference for the hash */
242 tt_local_entry_free_ref(tt_local_entry
);
246 tt_local_event(bat_priv
, addr
, tt_local_entry
->common
.flags
);
248 /* remove address from global hash if present */
249 tt_global_entry
= tt_global_hash_find(bat_priv
, addr
);
251 /* Check whether it is a roaming! */
252 if (tt_global_entry
) {
253 /* These node are probably going to update their tt table */
254 head
= &tt_global_entry
->orig_list
;
256 hlist_for_each_entry_rcu(orig_entry
, node
, head
, list
) {
257 orig_entry
->orig_node
->tt_poss_change
= true;
259 send_roam_adv(bat_priv
, tt_global_entry
->common
.addr
,
260 orig_entry
->orig_node
);
263 /* The global entry has to be marked as ROAMING and
264 * has to be kept for consistency purpose
266 tt_global_entry
->common
.flags
|= TT_CLIENT_ROAM
;
267 tt_global_entry
->roam_at
= jiffies
;
271 tt_local_entry_free_ref(tt_local_entry
);
273 tt_global_entry_free_ref(tt_global_entry
);
276 int tt_changes_fill_buffer(struct bat_priv
*bat_priv
,
277 unsigned char *buff
, int buff_len
)
279 int count
= 0, tot_changes
= 0;
280 struct tt_change_node
*entry
, *safe
;
283 tot_changes
= buff_len
/ tt_len(1);
285 spin_lock_bh(&bat_priv
->tt_changes_list_lock
);
286 atomic_set(&bat_priv
->tt_local_changes
, 0);
288 list_for_each_entry_safe(entry
, safe
, &bat_priv
->tt_changes_list
,
290 if (count
< tot_changes
) {
291 memcpy(buff
+ tt_len(count
),
292 &entry
->change
, sizeof(struct tt_change
));
295 list_del(&entry
->list
);
298 spin_unlock_bh(&bat_priv
->tt_changes_list_lock
);
300 /* Keep the buffer for possible tt_request */
301 spin_lock_bh(&bat_priv
->tt_buff_lock
);
302 kfree(bat_priv
->tt_buff
);
303 bat_priv
->tt_buff_len
= 0;
304 bat_priv
->tt_buff
= NULL
;
305 /* We check whether this new OGM has no changes due to size
309 * if kmalloc() fails we will reply with the full table
310 * instead of providing the diff
312 bat_priv
->tt_buff
= kmalloc(buff_len
, GFP_ATOMIC
);
313 if (bat_priv
->tt_buff
) {
314 memcpy(bat_priv
->tt_buff
, buff
, buff_len
);
315 bat_priv
->tt_buff_len
= buff_len
;
318 spin_unlock_bh(&bat_priv
->tt_buff_lock
);
323 int tt_local_seq_print_text(struct seq_file
*seq
, void *offset
)
325 struct net_device
*net_dev
= (struct net_device
*)seq
->private;
326 struct bat_priv
*bat_priv
= netdev_priv(net_dev
);
327 struct hashtable_t
*hash
= bat_priv
->tt_local_hash
;
328 struct tt_common_entry
*tt_common_entry
;
329 struct hard_iface
*primary_if
;
330 struct hlist_node
*node
;
331 struct hlist_head
*head
;
335 primary_if
= primary_if_get_selected(bat_priv
);
337 ret
= seq_printf(seq
,
338 "BATMAN mesh %s disabled - please specify interfaces to enable it\n",
343 if (primary_if
->if_status
!= IF_ACTIVE
) {
344 ret
= seq_printf(seq
,
345 "BATMAN mesh %s disabled - primary interface not active\n",
351 "Locally retrieved addresses (from %s) announced via TT (TTVN: %u):\n",
352 net_dev
->name
, (uint8_t)atomic_read(&bat_priv
->ttvn
));
354 for (i
= 0; i
< hash
->size
; i
++) {
355 head
= &hash
->table
[i
];
358 hlist_for_each_entry_rcu(tt_common_entry
, node
,
360 seq_printf(seq
, " * %pM [%c%c%c%c%c]\n",
361 tt_common_entry
->addr
,
362 (tt_common_entry
->flags
&
363 TT_CLIENT_ROAM
? 'R' : '.'),
364 (tt_common_entry
->flags
&
365 TT_CLIENT_NOPURGE
? 'P' : '.'),
366 (tt_common_entry
->flags
&
367 TT_CLIENT_NEW
? 'N' : '.'),
368 (tt_common_entry
->flags
&
369 TT_CLIENT_PENDING
? 'X' : '.'),
370 (tt_common_entry
->flags
&
371 TT_CLIENT_WIFI
? 'W' : '.'));
377 hardif_free_ref(primary_if
);
381 static void tt_local_set_pending(struct bat_priv
*bat_priv
,
382 struct tt_local_entry
*tt_local_entry
,
383 uint16_t flags
, const char *message
)
385 tt_local_event(bat_priv
, tt_local_entry
->common
.addr
,
386 tt_local_entry
->common
.flags
| flags
);
388 /* The local client has to be marked as "pending to be removed" but has
389 * to be kept in the table in order to send it in a full table
390 * response issued before the net ttvn increment (consistency check) */
391 tt_local_entry
->common
.flags
|= TT_CLIENT_PENDING
;
393 bat_dbg(DBG_TT
, bat_priv
,
394 "Local tt entry (%pM) pending to be removed: %s\n",
395 tt_local_entry
->common
.addr
, message
);
398 void tt_local_remove(struct bat_priv
*bat_priv
, const uint8_t *addr
,
399 const char *message
, bool roaming
)
401 struct tt_local_entry
*tt_local_entry
= NULL
;
403 tt_local_entry
= tt_local_hash_find(bat_priv
, addr
);
407 tt_local_set_pending(bat_priv
, tt_local_entry
, TT_CLIENT_DEL
|
408 (roaming
? TT_CLIENT_ROAM
: NO_FLAGS
), message
);
411 tt_local_entry_free_ref(tt_local_entry
);
414 static void tt_local_purge(struct bat_priv
*bat_priv
)
416 struct hashtable_t
*hash
= bat_priv
->tt_local_hash
;
417 struct tt_local_entry
*tt_local_entry
;
418 struct tt_common_entry
*tt_common_entry
;
419 struct hlist_node
*node
, *node_tmp
;
420 struct hlist_head
*head
;
421 spinlock_t
*list_lock
; /* protects write access to the hash lists */
424 for (i
= 0; i
< hash
->size
; i
++) {
425 head
= &hash
->table
[i
];
426 list_lock
= &hash
->list_locks
[i
];
428 spin_lock_bh(list_lock
);
429 hlist_for_each_entry_safe(tt_common_entry
, node
, node_tmp
,
431 tt_local_entry
= container_of(tt_common_entry
,
432 struct tt_local_entry
,
434 if (tt_local_entry
->common
.flags
& TT_CLIENT_NOPURGE
)
437 /* entry already marked for deletion */
438 if (tt_local_entry
->common
.flags
& TT_CLIENT_PENDING
)
441 if (!has_timed_out(tt_local_entry
->last_seen
,
445 tt_local_set_pending(bat_priv
, tt_local_entry
,
446 TT_CLIENT_DEL
, "timed out");
448 spin_unlock_bh(list_lock
);
453 static void tt_local_table_free(struct bat_priv
*bat_priv
)
455 struct hashtable_t
*hash
;
456 spinlock_t
*list_lock
; /* protects write access to the hash lists */
457 struct tt_common_entry
*tt_common_entry
;
458 struct tt_local_entry
*tt_local_entry
;
459 struct hlist_node
*node
, *node_tmp
;
460 struct hlist_head
*head
;
463 if (!bat_priv
->tt_local_hash
)
466 hash
= bat_priv
->tt_local_hash
;
468 for (i
= 0; i
< hash
->size
; i
++) {
469 head
= &hash
->table
[i
];
470 list_lock
= &hash
->list_locks
[i
];
472 spin_lock_bh(list_lock
);
473 hlist_for_each_entry_safe(tt_common_entry
, node
, node_tmp
,
476 tt_local_entry
= container_of(tt_common_entry
,
477 struct tt_local_entry
,
479 tt_local_entry_free_ref(tt_local_entry
);
481 spin_unlock_bh(list_lock
);
486 bat_priv
->tt_local_hash
= NULL
;
489 static int tt_global_init(struct bat_priv
*bat_priv
)
491 if (bat_priv
->tt_global_hash
)
494 bat_priv
->tt_global_hash
= hash_new(1024);
496 if (!bat_priv
->tt_global_hash
)
502 static void tt_changes_list_free(struct bat_priv
*bat_priv
)
504 struct tt_change_node
*entry
, *safe
;
506 spin_lock_bh(&bat_priv
->tt_changes_list_lock
);
508 list_for_each_entry_safe(entry
, safe
, &bat_priv
->tt_changes_list
,
510 list_del(&entry
->list
);
514 atomic_set(&bat_priv
->tt_local_changes
, 0);
515 spin_unlock_bh(&bat_priv
->tt_changes_list_lock
);
518 /* find out if an orig_node is already in the list of a tt_global_entry.
519 * returns 1 if found, 0 otherwise
521 static bool tt_global_entry_has_orig(const struct tt_global_entry
*entry
,
522 const struct orig_node
*orig_node
)
524 struct tt_orig_list_entry
*tmp_orig_entry
;
525 const struct hlist_head
*head
;
526 struct hlist_node
*node
;
530 head
= &entry
->orig_list
;
531 hlist_for_each_entry_rcu(tmp_orig_entry
, node
, head
, list
) {
532 if (tmp_orig_entry
->orig_node
== orig_node
) {
541 static void tt_global_add_orig_entry(struct tt_global_entry
*tt_global_entry
,
542 struct orig_node
*orig_node
,
545 struct tt_orig_list_entry
*orig_entry
;
547 orig_entry
= kzalloc(sizeof(*orig_entry
), GFP_ATOMIC
);
551 INIT_HLIST_NODE(&orig_entry
->list
);
552 atomic_inc(&orig_node
->refcount
);
553 atomic_inc(&orig_node
->tt_size
);
554 orig_entry
->orig_node
= orig_node
;
555 orig_entry
->ttvn
= ttvn
;
557 spin_lock_bh(&tt_global_entry
->list_lock
);
558 hlist_add_head_rcu(&orig_entry
->list
,
559 &tt_global_entry
->orig_list
);
560 spin_unlock_bh(&tt_global_entry
->list_lock
);
563 /* caller must hold orig_node refcount */
564 int tt_global_add(struct bat_priv
*bat_priv
, struct orig_node
*orig_node
,
565 const unsigned char *tt_addr
, uint8_t ttvn
, bool roaming
,
568 struct tt_global_entry
*tt_global_entry
= NULL
;
572 tt_global_entry
= tt_global_hash_find(bat_priv
, tt_addr
);
574 if (!tt_global_entry
) {
575 tt_global_entry
= kzalloc(sizeof(*tt_global_entry
),
577 if (!tt_global_entry
)
580 memcpy(tt_global_entry
->common
.addr
, tt_addr
, ETH_ALEN
);
582 tt_global_entry
->common
.flags
= NO_FLAGS
;
583 tt_global_entry
->roam_at
= 0;
584 atomic_set(&tt_global_entry
->common
.refcount
, 2);
586 INIT_HLIST_HEAD(&tt_global_entry
->orig_list
);
587 spin_lock_init(&tt_global_entry
->list_lock
);
589 hash_added
= hash_add(bat_priv
->tt_global_hash
, compare_tt
,
590 choose_orig
, &tt_global_entry
->common
,
591 &tt_global_entry
->common
.hash_entry
);
593 if (unlikely(hash_added
!= 0)) {
594 /* remove the reference for the hash */
595 tt_global_entry_free_ref(tt_global_entry
);
599 tt_global_add_orig_entry(tt_global_entry
, orig_node
, ttvn
);
601 /* there is already a global entry, use this one. */
603 /* If there is the TT_CLIENT_ROAM flag set, there is only one
604 * originator left in the list and we previously received a
605 * delete + roaming change for this originator.
607 * We should first delete the old originator before adding the
610 if (tt_global_entry
->common
.flags
& TT_CLIENT_ROAM
) {
611 tt_global_del_orig_list(tt_global_entry
);
612 tt_global_entry
->common
.flags
&= ~TT_CLIENT_ROAM
;
613 tt_global_entry
->roam_at
= 0;
616 if (!tt_global_entry_has_orig(tt_global_entry
, orig_node
))
617 tt_global_add_orig_entry(tt_global_entry
, orig_node
,
622 tt_global_entry
->common
.flags
|= TT_CLIENT_WIFI
;
624 bat_dbg(DBG_TT
, bat_priv
,
625 "Creating new global tt entry: %pM (via %pM)\n",
626 tt_global_entry
->common
.addr
, orig_node
->orig
);
629 /* remove address from local hash if present */
630 tt_local_remove(bat_priv
, tt_global_entry
->common
.addr
,
631 "global tt received", roaming
);
635 tt_global_entry_free_ref(tt_global_entry
);
639 /* print all orig nodes who announce the address for this global entry.
640 * it is assumed that the caller holds rcu_read_lock();
642 static void tt_global_print_entry(struct tt_global_entry
*tt_global_entry
,
643 struct seq_file
*seq
)
645 struct hlist_head
*head
;
646 struct hlist_node
*node
;
647 struct tt_orig_list_entry
*orig_entry
;
648 struct tt_common_entry
*tt_common_entry
;
652 tt_common_entry
= &tt_global_entry
->common
;
654 head
= &tt_global_entry
->orig_list
;
656 hlist_for_each_entry_rcu(orig_entry
, node
, head
, list
) {
657 flags
= tt_common_entry
->flags
;
658 last_ttvn
= atomic_read(&orig_entry
->orig_node
->last_ttvn
);
659 seq_printf(seq
, " * %pM (%3u) via %pM (%3u) [%c%c]\n",
660 tt_global_entry
->common
.addr
, orig_entry
->ttvn
,
661 orig_entry
->orig_node
->orig
, last_ttvn
,
662 (flags
& TT_CLIENT_ROAM
? 'R' : '.'),
663 (flags
& TT_CLIENT_WIFI
? 'W' : '.'));
667 int tt_global_seq_print_text(struct seq_file
*seq
, void *offset
)
669 struct net_device
*net_dev
= (struct net_device
*)seq
->private;
670 struct bat_priv
*bat_priv
= netdev_priv(net_dev
);
671 struct hashtable_t
*hash
= bat_priv
->tt_global_hash
;
672 struct tt_common_entry
*tt_common_entry
;
673 struct tt_global_entry
*tt_global_entry
;
674 struct hard_iface
*primary_if
;
675 struct hlist_node
*node
;
676 struct hlist_head
*head
;
680 primary_if
= primary_if_get_selected(bat_priv
);
682 ret
= seq_printf(seq
,
683 "BATMAN mesh %s disabled - please specify interfaces to enable it\n",
688 if (primary_if
->if_status
!= IF_ACTIVE
) {
689 ret
= seq_printf(seq
,
690 "BATMAN mesh %s disabled - primary interface not active\n",
696 "Globally announced TT entries received via the mesh %s\n",
698 seq_printf(seq
, " %-13s %s %-15s %s %s\n",
699 "Client", "(TTVN)", "Originator", "(Curr TTVN)", "Flags");
701 for (i
= 0; i
< hash
->size
; i
++) {
702 head
= &hash
->table
[i
];
705 hlist_for_each_entry_rcu(tt_common_entry
, node
,
707 tt_global_entry
= container_of(tt_common_entry
,
708 struct tt_global_entry
,
710 tt_global_print_entry(tt_global_entry
, seq
);
716 hardif_free_ref(primary_if
);
720 /* deletes the orig list of a tt_global_entry */
721 static void tt_global_del_orig_list(struct tt_global_entry
*tt_global_entry
)
723 struct hlist_head
*head
;
724 struct hlist_node
*node
, *safe
;
725 struct tt_orig_list_entry
*orig_entry
;
727 spin_lock_bh(&tt_global_entry
->list_lock
);
728 head
= &tt_global_entry
->orig_list
;
729 hlist_for_each_entry_safe(orig_entry
, node
, safe
, head
, list
) {
731 tt_orig_list_entry_free_ref(orig_entry
);
733 spin_unlock_bh(&tt_global_entry
->list_lock
);
737 static void tt_global_del_orig_entry(struct bat_priv
*bat_priv
,
738 struct tt_global_entry
*tt_global_entry
,
739 struct orig_node
*orig_node
,
742 struct hlist_head
*head
;
743 struct hlist_node
*node
, *safe
;
744 struct tt_orig_list_entry
*orig_entry
;
746 spin_lock_bh(&tt_global_entry
->list_lock
);
747 head
= &tt_global_entry
->orig_list
;
748 hlist_for_each_entry_safe(orig_entry
, node
, safe
, head
, list
) {
749 if (orig_entry
->orig_node
== orig_node
) {
750 bat_dbg(DBG_TT
, bat_priv
,
751 "Deleting %pM from global tt entry %pM: %s\n",
752 orig_node
->orig
, tt_global_entry
->common
.addr
,
755 tt_orig_list_entry_free_ref(orig_entry
);
758 spin_unlock_bh(&tt_global_entry
->list_lock
);
761 static void tt_global_del_struct(struct bat_priv
*bat_priv
,
762 struct tt_global_entry
*tt_global_entry
,
765 bat_dbg(DBG_TT
, bat_priv
,
766 "Deleting global tt entry %pM: %s\n",
767 tt_global_entry
->common
.addr
, message
);
769 hash_remove(bat_priv
->tt_global_hash
, compare_tt
, choose_orig
,
770 tt_global_entry
->common
.addr
);
771 tt_global_entry_free_ref(tt_global_entry
);
775 /* If the client is to be deleted, we check if it is the last origantor entry
776 * within tt_global entry. If yes, we set the TT_CLIENT_ROAM flag and the timer,
777 * otherwise we simply remove the originator scheduled for deletion.
779 static void tt_global_del_roaming(struct bat_priv
*bat_priv
,
780 struct tt_global_entry
*tt_global_entry
,
781 struct orig_node
*orig_node
,
784 bool last_entry
= true;
785 struct hlist_head
*head
;
786 struct hlist_node
*node
;
787 struct tt_orig_list_entry
*orig_entry
;
789 /* no local entry exists, case 1:
790 * Check if this is the last one or if other entries exist.
794 head
= &tt_global_entry
->orig_list
;
795 hlist_for_each_entry_rcu(orig_entry
, node
, head
, list
) {
796 if (orig_entry
->orig_node
!= orig_node
) {
804 /* its the last one, mark for roaming. */
805 tt_global_entry
->common
.flags
|= TT_CLIENT_ROAM
;
806 tt_global_entry
->roam_at
= jiffies
;
808 /* there is another entry, we can simply delete this
809 * one and can still use the other one.
811 tt_global_del_orig_entry(bat_priv
, tt_global_entry
,
817 static void tt_global_del(struct bat_priv
*bat_priv
,
818 struct orig_node
*orig_node
,
819 const unsigned char *addr
,
820 const char *message
, bool roaming
)
822 struct tt_global_entry
*tt_global_entry
= NULL
;
823 struct tt_local_entry
*tt_local_entry
= NULL
;
825 tt_global_entry
= tt_global_hash_find(bat_priv
, addr
);
826 if (!tt_global_entry
)
830 tt_global_del_orig_entry(bat_priv
, tt_global_entry
, orig_node
,
833 if (hlist_empty(&tt_global_entry
->orig_list
))
834 tt_global_del_struct(bat_priv
, tt_global_entry
,
840 /* if we are deleting a global entry due to a roam
841 * event, there are two possibilities:
842 * 1) the client roamed from node A to node B => if there
843 * is only one originator left for this client, we mark
844 * it with TT_CLIENT_ROAM, we start a timer and we
845 * wait for node B to claim it. In case of timeout
846 * the entry is purged.
848 * If there are other originators left, we directly delete
850 * 2) the client roamed to us => we can directly delete
851 * the global entry, since it is useless now. */
853 tt_local_entry
= tt_local_hash_find(bat_priv
,
854 tt_global_entry
->common
.addr
);
855 if (tt_local_entry
) {
856 /* local entry exists, case 2: client roamed to us. */
857 tt_global_del_orig_list(tt_global_entry
);
858 tt_global_del_struct(bat_priv
, tt_global_entry
, message
);
860 /* no local entry exists, case 1: check for roaming */
861 tt_global_del_roaming(bat_priv
, tt_global_entry
, orig_node
,
867 tt_global_entry_free_ref(tt_global_entry
);
869 tt_local_entry_free_ref(tt_local_entry
);
872 void tt_global_del_orig(struct bat_priv
*bat_priv
,
873 struct orig_node
*orig_node
, const char *message
)
875 struct tt_global_entry
*tt_global_entry
;
876 struct tt_common_entry
*tt_common_entry
;
878 struct hashtable_t
*hash
= bat_priv
->tt_global_hash
;
879 struct hlist_node
*node
, *safe
;
880 struct hlist_head
*head
;
881 spinlock_t
*list_lock
; /* protects write access to the hash lists */
886 for (i
= 0; i
< hash
->size
; i
++) {
887 head
= &hash
->table
[i
];
888 list_lock
= &hash
->list_locks
[i
];
890 spin_lock_bh(list_lock
);
891 hlist_for_each_entry_safe(tt_common_entry
, node
, safe
,
893 tt_global_entry
= container_of(tt_common_entry
,
894 struct tt_global_entry
,
897 tt_global_del_orig_entry(bat_priv
, tt_global_entry
,
900 if (hlist_empty(&tt_global_entry
->orig_list
)) {
901 bat_dbg(DBG_TT
, bat_priv
,
902 "Deleting global tt entry %pM: %s\n",
903 tt_global_entry
->common
.addr
,
906 tt_global_entry_free_ref(tt_global_entry
);
909 spin_unlock_bh(list_lock
);
911 atomic_set(&orig_node
->tt_size
, 0);
912 orig_node
->tt_initialised
= false;
915 static void tt_global_roam_purge(struct bat_priv
*bat_priv
)
917 struct hashtable_t
*hash
= bat_priv
->tt_global_hash
;
918 struct tt_common_entry
*tt_common_entry
;
919 struct tt_global_entry
*tt_global_entry
;
920 struct hlist_node
*node
, *node_tmp
;
921 struct hlist_head
*head
;
922 spinlock_t
*list_lock
; /* protects write access to the hash lists */
925 for (i
= 0; i
< hash
->size
; i
++) {
926 head
= &hash
->table
[i
];
927 list_lock
= &hash
->list_locks
[i
];
929 spin_lock_bh(list_lock
);
930 hlist_for_each_entry_safe(tt_common_entry
, node
, node_tmp
,
932 tt_global_entry
= container_of(tt_common_entry
,
933 struct tt_global_entry
,
935 if (!(tt_global_entry
->common
.flags
& TT_CLIENT_ROAM
))
937 if (!has_timed_out(tt_global_entry
->roam_at
,
938 TT_CLIENT_ROAM_TIMEOUT
))
941 bat_dbg(DBG_TT
, bat_priv
,
942 "Deleting global tt entry (%pM): Roaming timeout\n",
943 tt_global_entry
->common
.addr
);
946 tt_global_entry_free_ref(tt_global_entry
);
948 spin_unlock_bh(list_lock
);
953 static void tt_global_table_free(struct bat_priv
*bat_priv
)
955 struct hashtable_t
*hash
;
956 spinlock_t
*list_lock
; /* protects write access to the hash lists */
957 struct tt_common_entry
*tt_common_entry
;
958 struct tt_global_entry
*tt_global_entry
;
959 struct hlist_node
*node
, *node_tmp
;
960 struct hlist_head
*head
;
963 if (!bat_priv
->tt_global_hash
)
966 hash
= bat_priv
->tt_global_hash
;
968 for (i
= 0; i
< hash
->size
; i
++) {
969 head
= &hash
->table
[i
];
970 list_lock
= &hash
->list_locks
[i
];
972 spin_lock_bh(list_lock
);
973 hlist_for_each_entry_safe(tt_common_entry
, node
, node_tmp
,
976 tt_global_entry
= container_of(tt_common_entry
,
977 struct tt_global_entry
,
979 tt_global_entry_free_ref(tt_global_entry
);
981 spin_unlock_bh(list_lock
);
986 bat_priv
->tt_global_hash
= NULL
;
989 static bool _is_ap_isolated(struct tt_local_entry
*tt_local_entry
,
990 struct tt_global_entry
*tt_global_entry
)
994 if (tt_local_entry
->common
.flags
& TT_CLIENT_WIFI
&&
995 tt_global_entry
->common
.flags
& TT_CLIENT_WIFI
)
1001 struct orig_node
*transtable_search(struct bat_priv
*bat_priv
,
1002 const uint8_t *src
, const uint8_t *addr
)
1004 struct tt_local_entry
*tt_local_entry
= NULL
;
1005 struct tt_global_entry
*tt_global_entry
= NULL
;
1006 struct orig_node
*orig_node
= NULL
;
1007 struct neigh_node
*router
= NULL
;
1008 struct hlist_head
*head
;
1009 struct hlist_node
*node
;
1010 struct tt_orig_list_entry
*orig_entry
;
1013 if (src
&& atomic_read(&bat_priv
->ap_isolation
)) {
1014 tt_local_entry
= tt_local_hash_find(bat_priv
, src
);
1015 if (!tt_local_entry
)
1019 tt_global_entry
= tt_global_hash_find(bat_priv
, addr
);
1020 if (!tt_global_entry
)
1023 /* check whether the clients should not communicate due to AP
1025 if (tt_local_entry
&& _is_ap_isolated(tt_local_entry
, tt_global_entry
))
1031 head
= &tt_global_entry
->orig_list
;
1032 hlist_for_each_entry_rcu(orig_entry
, node
, head
, list
) {
1033 router
= orig_node_get_router(orig_entry
->orig_node
);
1037 if (router
->tq_avg
> best_tq
) {
1038 orig_node
= orig_entry
->orig_node
;
1039 best_tq
= router
->tq_avg
;
1041 neigh_node_free_ref(router
);
1043 /* found anything? */
1044 if (orig_node
&& !atomic_inc_not_zero(&orig_node
->refcount
))
1048 if (tt_global_entry
)
1049 tt_global_entry_free_ref(tt_global_entry
);
1051 tt_local_entry_free_ref(tt_local_entry
);
1056 /* Calculates the checksum of the local table of a given orig_node */
1057 static uint16_t tt_global_crc(struct bat_priv
*bat_priv
,
1058 struct orig_node
*orig_node
)
1060 uint16_t total
= 0, total_one
;
1061 struct hashtable_t
*hash
= bat_priv
->tt_global_hash
;
1062 struct tt_common_entry
*tt_common_entry
;
1063 struct tt_global_entry
*tt_global_entry
;
1064 struct hlist_node
*node
;
1065 struct hlist_head
*head
;
1069 for (i
= 0; i
< hash
->size
; i
++) {
1070 head
= &hash
->table
[i
];
1073 hlist_for_each_entry_rcu(tt_common_entry
, node
,
1075 tt_global_entry
= container_of(tt_common_entry
,
1076 struct tt_global_entry
,
1078 /* Roaming clients are in the global table for
1079 * consistency only. They don't have to be
1080 * taken into account while computing the
1083 if (tt_global_entry
->common
.flags
& TT_CLIENT_ROAM
)
1086 /* find out if this global entry is announced by this
1089 if (!tt_global_entry_has_orig(tt_global_entry
,
1094 for (j
= 0; j
< ETH_ALEN
; j
++)
1095 total_one
= crc16_byte(total_one
,
1096 tt_global_entry
->common
.addr
[j
]);
1105 /* Calculates the checksum of the local table */
1106 uint16_t tt_local_crc(struct bat_priv
*bat_priv
)
1108 uint16_t total
= 0, total_one
;
1109 struct hashtable_t
*hash
= bat_priv
->tt_local_hash
;
1110 struct tt_common_entry
*tt_common_entry
;
1111 struct hlist_node
*node
;
1112 struct hlist_head
*head
;
1116 for (i
= 0; i
< hash
->size
; i
++) {
1117 head
= &hash
->table
[i
];
1120 hlist_for_each_entry_rcu(tt_common_entry
, node
,
1122 /* not yet committed clients have not to be taken into
1123 * account while computing the CRC */
1124 if (tt_common_entry
->flags
& TT_CLIENT_NEW
)
1127 for (j
= 0; j
< ETH_ALEN
; j
++)
1128 total_one
= crc16_byte(total_one
,
1129 tt_common_entry
->addr
[j
]);
1138 static void tt_req_list_free(struct bat_priv
*bat_priv
)
1140 struct tt_req_node
*node
, *safe
;
1142 spin_lock_bh(&bat_priv
->tt_req_list_lock
);
1144 list_for_each_entry_safe(node
, safe
, &bat_priv
->tt_req_list
, list
) {
1145 list_del(&node
->list
);
1149 spin_unlock_bh(&bat_priv
->tt_req_list_lock
);
1152 static void tt_save_orig_buffer(struct bat_priv
*bat_priv
,
1153 struct orig_node
*orig_node
,
1154 const unsigned char *tt_buff
,
1155 uint8_t tt_num_changes
)
1157 uint16_t tt_buff_len
= tt_len(tt_num_changes
);
1159 /* Replace the old buffer only if I received something in the
1160 * last OGM (the OGM could carry no changes) */
1161 spin_lock_bh(&orig_node
->tt_buff_lock
);
1162 if (tt_buff_len
> 0) {
1163 kfree(orig_node
->tt_buff
);
1164 orig_node
->tt_buff_len
= 0;
1165 orig_node
->tt_buff
= kmalloc(tt_buff_len
, GFP_ATOMIC
);
1166 if (orig_node
->tt_buff
) {
1167 memcpy(orig_node
->tt_buff
, tt_buff
, tt_buff_len
);
1168 orig_node
->tt_buff_len
= tt_buff_len
;
1171 spin_unlock_bh(&orig_node
->tt_buff_lock
);
1174 static void tt_req_purge(struct bat_priv
*bat_priv
)
1176 struct tt_req_node
*node
, *safe
;
1178 spin_lock_bh(&bat_priv
->tt_req_list_lock
);
1179 list_for_each_entry_safe(node
, safe
, &bat_priv
->tt_req_list
, list
) {
1180 if (has_timed_out(node
->issued_at
, TT_REQUEST_TIMEOUT
)) {
1181 list_del(&node
->list
);
1185 spin_unlock_bh(&bat_priv
->tt_req_list_lock
);
1188 /* returns the pointer to the new tt_req_node struct if no request
1189 * has already been issued for this orig_node, NULL otherwise */
1190 static struct tt_req_node
*new_tt_req_node(struct bat_priv
*bat_priv
,
1191 struct orig_node
*orig_node
)
1193 struct tt_req_node
*tt_req_node_tmp
, *tt_req_node
= NULL
;
1195 spin_lock_bh(&bat_priv
->tt_req_list_lock
);
1196 list_for_each_entry(tt_req_node_tmp
, &bat_priv
->tt_req_list
, list
) {
1197 if (compare_eth(tt_req_node_tmp
, orig_node
) &&
1198 !has_timed_out(tt_req_node_tmp
->issued_at
,
1199 TT_REQUEST_TIMEOUT
))
1203 tt_req_node
= kmalloc(sizeof(*tt_req_node
), GFP_ATOMIC
);
1207 memcpy(tt_req_node
->addr
, orig_node
->orig
, ETH_ALEN
);
1208 tt_req_node
->issued_at
= jiffies
;
1210 list_add(&tt_req_node
->list
, &bat_priv
->tt_req_list
);
1212 spin_unlock_bh(&bat_priv
->tt_req_list_lock
);
1216 /* data_ptr is useless here, but has to be kept to respect the prototype */
1217 static int tt_local_valid_entry(const void *entry_ptr
, const void *data_ptr
)
1219 const struct tt_common_entry
*tt_common_entry
= entry_ptr
;
1221 if (tt_common_entry
->flags
& TT_CLIENT_NEW
)
1226 static int tt_global_valid_entry(const void *entry_ptr
, const void *data_ptr
)
1228 const struct tt_common_entry
*tt_common_entry
= entry_ptr
;
1229 const struct tt_global_entry
*tt_global_entry
;
1230 const struct orig_node
*orig_node
= data_ptr
;
1232 if (tt_common_entry
->flags
& TT_CLIENT_ROAM
)
1235 tt_global_entry
= container_of(tt_common_entry
, struct tt_global_entry
,
1238 return tt_global_entry_has_orig(tt_global_entry
, orig_node
);
1241 static struct sk_buff
*tt_response_fill_table(uint16_t tt_len
, uint8_t ttvn
,
1242 struct hashtable_t
*hash
,
1243 struct hard_iface
*primary_if
,
1244 int (*valid_cb
)(const void *,
1248 struct tt_common_entry
*tt_common_entry
;
1249 struct tt_query_packet
*tt_response
;
1250 struct tt_change
*tt_change
;
1251 struct hlist_node
*node
;
1252 struct hlist_head
*head
;
1253 struct sk_buff
*skb
= NULL
;
1254 uint16_t tt_tot
, tt_count
;
1255 ssize_t tt_query_size
= sizeof(struct tt_query_packet
);
1258 if (tt_query_size
+ tt_len
> primary_if
->soft_iface
->mtu
) {
1259 tt_len
= primary_if
->soft_iface
->mtu
- tt_query_size
;
1260 tt_len
-= tt_len
% sizeof(struct tt_change
);
1262 tt_tot
= tt_len
/ sizeof(struct tt_change
);
1264 skb
= dev_alloc_skb(tt_query_size
+ tt_len
+ ETH_HLEN
);
1268 skb_reserve(skb
, ETH_HLEN
);
1269 tt_response
= (struct tt_query_packet
*)skb_put(skb
,
1270 tt_query_size
+ tt_len
);
1271 tt_response
->ttvn
= ttvn
;
1273 tt_change
= (struct tt_change
*)(skb
->data
+ tt_query_size
);
1277 for (i
= 0; i
< hash
->size
; i
++) {
1278 head
= &hash
->table
[i
];
1280 hlist_for_each_entry_rcu(tt_common_entry
, node
,
1282 if (tt_count
== tt_tot
)
1285 if ((valid_cb
) && (!valid_cb(tt_common_entry
, cb_data
)))
1288 memcpy(tt_change
->addr
, tt_common_entry
->addr
,
1290 tt_change
->flags
= NO_FLAGS
;
1298 /* store in the message the number of entries we have successfully
1300 tt_response
->tt_data
= htons(tt_count
);
1306 static int send_tt_request(struct bat_priv
*bat_priv
,
1307 struct orig_node
*dst_orig_node
,
1308 uint8_t ttvn
, uint16_t tt_crc
, bool full_table
)
1310 struct sk_buff
*skb
= NULL
;
1311 struct tt_query_packet
*tt_request
;
1312 struct neigh_node
*neigh_node
= NULL
;
1313 struct hard_iface
*primary_if
;
1314 struct tt_req_node
*tt_req_node
= NULL
;
1317 primary_if
= primary_if_get_selected(bat_priv
);
1321 /* The new tt_req will be issued only if I'm not waiting for a
1322 * reply from the same orig_node yet */
1323 tt_req_node
= new_tt_req_node(bat_priv
, dst_orig_node
);
1327 skb
= dev_alloc_skb(sizeof(struct tt_query_packet
) + ETH_HLEN
);
1331 skb_reserve(skb
, ETH_HLEN
);
1333 tt_request
= (struct tt_query_packet
*)skb_put(skb
,
1334 sizeof(struct tt_query_packet
));
1336 tt_request
->header
.packet_type
= BAT_TT_QUERY
;
1337 tt_request
->header
.version
= COMPAT_VERSION
;
1338 memcpy(tt_request
->src
, primary_if
->net_dev
->dev_addr
, ETH_ALEN
);
1339 memcpy(tt_request
->dst
, dst_orig_node
->orig
, ETH_ALEN
);
1340 tt_request
->header
.ttl
= TTL
;
1341 tt_request
->ttvn
= ttvn
;
1342 tt_request
->tt_data
= tt_crc
;
1343 tt_request
->flags
= TT_REQUEST
;
1346 tt_request
->flags
|= TT_FULL_TABLE
;
1348 neigh_node
= orig_node_get_router(dst_orig_node
);
1352 bat_dbg(DBG_TT
, bat_priv
,
1353 "Sending TT_REQUEST to %pM via %pM [%c]\n",
1354 dst_orig_node
->orig
, neigh_node
->addr
,
1355 (full_table
? 'F' : '.'));
1357 send_skb_packet(skb
, neigh_node
->if_incoming
, neigh_node
->addr
);
1362 neigh_node_free_ref(neigh_node
);
1364 hardif_free_ref(primary_if
);
1367 if (ret
&& tt_req_node
) {
1368 spin_lock_bh(&bat_priv
->tt_req_list_lock
);
1369 list_del(&tt_req_node
->list
);
1370 spin_unlock_bh(&bat_priv
->tt_req_list_lock
);
1376 static bool send_other_tt_response(struct bat_priv
*bat_priv
,
1377 struct tt_query_packet
*tt_request
)
1379 struct orig_node
*req_dst_orig_node
= NULL
, *res_dst_orig_node
= NULL
;
1380 struct neigh_node
*neigh_node
= NULL
;
1381 struct hard_iface
*primary_if
= NULL
;
1382 uint8_t orig_ttvn
, req_ttvn
, ttvn
;
1384 unsigned char *tt_buff
;
1386 uint16_t tt_len
, tt_tot
;
1387 struct sk_buff
*skb
= NULL
;
1388 struct tt_query_packet
*tt_response
;
1390 bat_dbg(DBG_TT
, bat_priv
,
1391 "Received TT_REQUEST from %pM for ttvn: %u (%pM) [%c]\n",
1392 tt_request
->src
, tt_request
->ttvn
, tt_request
->dst
,
1393 (tt_request
->flags
& TT_FULL_TABLE
? 'F' : '.'));
1395 /* Let's get the orig node of the REAL destination */
1396 req_dst_orig_node
= orig_hash_find(bat_priv
, tt_request
->dst
);
1397 if (!req_dst_orig_node
)
1400 res_dst_orig_node
= orig_hash_find(bat_priv
, tt_request
->src
);
1401 if (!res_dst_orig_node
)
1404 neigh_node
= orig_node_get_router(res_dst_orig_node
);
1408 primary_if
= primary_if_get_selected(bat_priv
);
1412 orig_ttvn
= (uint8_t)atomic_read(&req_dst_orig_node
->last_ttvn
);
1413 req_ttvn
= tt_request
->ttvn
;
1415 /* I don't have the requested data */
1416 if (orig_ttvn
!= req_ttvn
||
1417 tt_request
->tt_data
!= req_dst_orig_node
->tt_crc
)
1420 /* If the full table has been explicitly requested */
1421 if (tt_request
->flags
& TT_FULL_TABLE
||
1422 !req_dst_orig_node
->tt_buff
)
1427 /* In this version, fragmentation is not implemented, then
1428 * I'll send only one packet with as much TT entries as I can */
1430 spin_lock_bh(&req_dst_orig_node
->tt_buff_lock
);
1431 tt_len
= req_dst_orig_node
->tt_buff_len
;
1432 tt_tot
= tt_len
/ sizeof(struct tt_change
);
1434 skb
= dev_alloc_skb(sizeof(struct tt_query_packet
) +
1439 skb_reserve(skb
, ETH_HLEN
);
1440 tt_response
= (struct tt_query_packet
*)skb_put(skb
,
1441 sizeof(struct tt_query_packet
) + tt_len
);
1442 tt_response
->ttvn
= req_ttvn
;
1443 tt_response
->tt_data
= htons(tt_tot
);
1445 tt_buff
= skb
->data
+ sizeof(struct tt_query_packet
);
1446 /* Copy the last orig_node's OGM buffer */
1447 memcpy(tt_buff
, req_dst_orig_node
->tt_buff
,
1448 req_dst_orig_node
->tt_buff_len
);
1450 spin_unlock_bh(&req_dst_orig_node
->tt_buff_lock
);
1452 tt_len
= (uint16_t)atomic_read(&req_dst_orig_node
->tt_size
) *
1453 sizeof(struct tt_change
);
1454 ttvn
= (uint8_t)atomic_read(&req_dst_orig_node
->last_ttvn
);
1456 skb
= tt_response_fill_table(tt_len
, ttvn
,
1457 bat_priv
->tt_global_hash
,
1458 primary_if
, tt_global_valid_entry
,
1463 tt_response
= (struct tt_query_packet
*)skb
->data
;
1466 tt_response
->header
.packet_type
= BAT_TT_QUERY
;
1467 tt_response
->header
.version
= COMPAT_VERSION
;
1468 tt_response
->header
.ttl
= TTL
;
1469 memcpy(tt_response
->src
, req_dst_orig_node
->orig
, ETH_ALEN
);
1470 memcpy(tt_response
->dst
, tt_request
->src
, ETH_ALEN
);
1471 tt_response
->flags
= TT_RESPONSE
;
1474 tt_response
->flags
|= TT_FULL_TABLE
;
1476 bat_dbg(DBG_TT
, bat_priv
,
1477 "Sending TT_RESPONSE %pM via %pM for %pM (ttvn: %u)\n",
1478 res_dst_orig_node
->orig
, neigh_node
->addr
,
1479 req_dst_orig_node
->orig
, req_ttvn
);
1481 send_skb_packet(skb
, neigh_node
->if_incoming
, neigh_node
->addr
);
1486 spin_unlock_bh(&req_dst_orig_node
->tt_buff_lock
);
1489 if (res_dst_orig_node
)
1490 orig_node_free_ref(res_dst_orig_node
);
1491 if (req_dst_orig_node
)
1492 orig_node_free_ref(req_dst_orig_node
);
1494 neigh_node_free_ref(neigh_node
);
1496 hardif_free_ref(primary_if
);
1502 static bool send_my_tt_response(struct bat_priv
*bat_priv
,
1503 struct tt_query_packet
*tt_request
)
1505 struct orig_node
*orig_node
= NULL
;
1506 struct neigh_node
*neigh_node
= NULL
;
1507 struct hard_iface
*primary_if
= NULL
;
1508 uint8_t my_ttvn
, req_ttvn
, ttvn
;
1510 unsigned char *tt_buff
;
1512 uint16_t tt_len
, tt_tot
;
1513 struct sk_buff
*skb
= NULL
;
1514 struct tt_query_packet
*tt_response
;
1516 bat_dbg(DBG_TT
, bat_priv
,
1517 "Received TT_REQUEST from %pM for ttvn: %u (me) [%c]\n",
1518 tt_request
->src
, tt_request
->ttvn
,
1519 (tt_request
->flags
& TT_FULL_TABLE
? 'F' : '.'));
1522 my_ttvn
= (uint8_t)atomic_read(&bat_priv
->ttvn
);
1523 req_ttvn
= tt_request
->ttvn
;
1525 orig_node
= orig_hash_find(bat_priv
, tt_request
->src
);
1529 neigh_node
= orig_node_get_router(orig_node
);
1533 primary_if
= primary_if_get_selected(bat_priv
);
1537 /* If the full table has been explicitly requested or the gap
1538 * is too big send the whole local translation table */
1539 if (tt_request
->flags
& TT_FULL_TABLE
|| my_ttvn
!= req_ttvn
||
1545 /* In this version, fragmentation is not implemented, then
1546 * I'll send only one packet with as much TT entries as I can */
1548 spin_lock_bh(&bat_priv
->tt_buff_lock
);
1549 tt_len
= bat_priv
->tt_buff_len
;
1550 tt_tot
= tt_len
/ sizeof(struct tt_change
);
1552 skb
= dev_alloc_skb(sizeof(struct tt_query_packet
) +
1557 skb_reserve(skb
, ETH_HLEN
);
1558 tt_response
= (struct tt_query_packet
*)skb_put(skb
,
1559 sizeof(struct tt_query_packet
) + tt_len
);
1560 tt_response
->ttvn
= req_ttvn
;
1561 tt_response
->tt_data
= htons(tt_tot
);
1563 tt_buff
= skb
->data
+ sizeof(struct tt_query_packet
);
1564 memcpy(tt_buff
, bat_priv
->tt_buff
,
1565 bat_priv
->tt_buff_len
);
1566 spin_unlock_bh(&bat_priv
->tt_buff_lock
);
1568 tt_len
= (uint16_t)atomic_read(&bat_priv
->num_local_tt
) *
1569 sizeof(struct tt_change
);
1570 ttvn
= (uint8_t)atomic_read(&bat_priv
->ttvn
);
1572 skb
= tt_response_fill_table(tt_len
, ttvn
,
1573 bat_priv
->tt_local_hash
,
1574 primary_if
, tt_local_valid_entry
,
1579 tt_response
= (struct tt_query_packet
*)skb
->data
;
1582 tt_response
->header
.packet_type
= BAT_TT_QUERY
;
1583 tt_response
->header
.version
= COMPAT_VERSION
;
1584 tt_response
->header
.ttl
= TTL
;
1585 memcpy(tt_response
->src
, primary_if
->net_dev
->dev_addr
, ETH_ALEN
);
1586 memcpy(tt_response
->dst
, tt_request
->src
, ETH_ALEN
);
1587 tt_response
->flags
= TT_RESPONSE
;
1590 tt_response
->flags
|= TT_FULL_TABLE
;
1592 bat_dbg(DBG_TT
, bat_priv
,
1593 "Sending TT_RESPONSE to %pM via %pM [%c]\n",
1594 orig_node
->orig
, neigh_node
->addr
,
1595 (tt_response
->flags
& TT_FULL_TABLE
? 'F' : '.'));
1597 send_skb_packet(skb
, neigh_node
->if_incoming
, neigh_node
->addr
);
1602 spin_unlock_bh(&bat_priv
->tt_buff_lock
);
1605 orig_node_free_ref(orig_node
);
1607 neigh_node_free_ref(neigh_node
);
1609 hardif_free_ref(primary_if
);
1612 /* This packet was for me, so it doesn't need to be re-routed */
1616 bool send_tt_response(struct bat_priv
*bat_priv
,
1617 struct tt_query_packet
*tt_request
)
1619 if (is_my_mac(tt_request
->dst
)) {
1620 /* don't answer backbone gws! */
1621 if (bla_is_backbone_gw_orig(bat_priv
, tt_request
->src
))
1624 return send_my_tt_response(bat_priv
, tt_request
);
1626 return send_other_tt_response(bat_priv
, tt_request
);
1630 static void _tt_update_changes(struct bat_priv
*bat_priv
,
1631 struct orig_node
*orig_node
,
1632 struct tt_change
*tt_change
,
1633 uint16_t tt_num_changes
, uint8_t ttvn
)
1637 for (i
= 0; i
< tt_num_changes
; i
++) {
1638 if ((tt_change
+ i
)->flags
& TT_CLIENT_DEL
)
1639 tt_global_del(bat_priv
, orig_node
,
1640 (tt_change
+ i
)->addr
,
1641 "tt removed by changes",
1642 (tt_change
+ i
)->flags
& TT_CLIENT_ROAM
);
1644 if (!tt_global_add(bat_priv
, orig_node
,
1645 (tt_change
+ i
)->addr
, ttvn
, false,
1646 (tt_change
+ i
)->flags
&
1648 /* In case of problem while storing a
1649 * global_entry, we stop the updating
1650 * procedure without committing the
1651 * ttvn change. This will avoid to send
1652 * corrupted data on tt_request
1656 orig_node
->tt_initialised
= true;
1659 static void tt_fill_gtable(struct bat_priv
*bat_priv
,
1660 struct tt_query_packet
*tt_response
)
1662 struct orig_node
*orig_node
= NULL
;
1664 orig_node
= orig_hash_find(bat_priv
, tt_response
->src
);
1668 /* Purge the old table first.. */
1669 tt_global_del_orig(bat_priv
, orig_node
, "Received full table");
1671 _tt_update_changes(bat_priv
, orig_node
,
1672 (struct tt_change
*)(tt_response
+ 1),
1673 tt_response
->tt_data
, tt_response
->ttvn
);
1675 spin_lock_bh(&orig_node
->tt_buff_lock
);
1676 kfree(orig_node
->tt_buff
);
1677 orig_node
->tt_buff_len
= 0;
1678 orig_node
->tt_buff
= NULL
;
1679 spin_unlock_bh(&orig_node
->tt_buff_lock
);
1681 atomic_set(&orig_node
->last_ttvn
, tt_response
->ttvn
);
1685 orig_node_free_ref(orig_node
);
1688 static void tt_update_changes(struct bat_priv
*bat_priv
,
1689 struct orig_node
*orig_node
,
1690 uint16_t tt_num_changes
, uint8_t ttvn
,
1691 struct tt_change
*tt_change
)
1693 _tt_update_changes(bat_priv
, orig_node
, tt_change
, tt_num_changes
,
1696 tt_save_orig_buffer(bat_priv
, orig_node
, (unsigned char *)tt_change
,
1698 atomic_set(&orig_node
->last_ttvn
, ttvn
);
1701 bool is_my_client(struct bat_priv
*bat_priv
, const uint8_t *addr
)
1703 struct tt_local_entry
*tt_local_entry
= NULL
;
1706 tt_local_entry
= tt_local_hash_find(bat_priv
, addr
);
1707 if (!tt_local_entry
)
1709 /* Check if the client has been logically deleted (but is kept for
1710 * consistency purpose) */
1711 if (tt_local_entry
->common
.flags
& TT_CLIENT_PENDING
)
1716 tt_local_entry_free_ref(tt_local_entry
);
1720 void handle_tt_response(struct bat_priv
*bat_priv
,
1721 struct tt_query_packet
*tt_response
)
1723 struct tt_req_node
*node
, *safe
;
1724 struct orig_node
*orig_node
= NULL
;
1726 bat_dbg(DBG_TT
, bat_priv
,
1727 "Received TT_RESPONSE from %pM for ttvn %d t_size: %d [%c]\n",
1728 tt_response
->src
, tt_response
->ttvn
, tt_response
->tt_data
,
1729 (tt_response
->flags
& TT_FULL_TABLE
? 'F' : '.'));
1731 /* we should have never asked a backbone gw */
1732 if (bla_is_backbone_gw_orig(bat_priv
, tt_response
->src
))
1735 orig_node
= orig_hash_find(bat_priv
, tt_response
->src
);
1739 if (tt_response
->flags
& TT_FULL_TABLE
)
1740 tt_fill_gtable(bat_priv
, tt_response
);
1742 tt_update_changes(bat_priv
, orig_node
, tt_response
->tt_data
,
1744 (struct tt_change
*)(tt_response
+ 1));
1746 /* Delete the tt_req_node from pending tt_requests list */
1747 spin_lock_bh(&bat_priv
->tt_req_list_lock
);
1748 list_for_each_entry_safe(node
, safe
, &bat_priv
->tt_req_list
, list
) {
1749 if (!compare_eth(node
->addr
, tt_response
->src
))
1751 list_del(&node
->list
);
1754 spin_unlock_bh(&bat_priv
->tt_req_list_lock
);
1756 /* Recalculate the CRC for this orig_node and store it */
1757 orig_node
->tt_crc
= tt_global_crc(bat_priv
, orig_node
);
1758 /* Roaming phase is over: tables are in sync again. I can
1760 orig_node
->tt_poss_change
= false;
1763 orig_node_free_ref(orig_node
);
1766 int tt_init(struct bat_priv
*bat_priv
)
1768 if (!tt_local_init(bat_priv
))
1771 if (!tt_global_init(bat_priv
))
1774 tt_start_timer(bat_priv
);
1779 static void tt_roam_list_free(struct bat_priv
*bat_priv
)
1781 struct tt_roam_node
*node
, *safe
;
1783 spin_lock_bh(&bat_priv
->tt_roam_list_lock
);
1785 list_for_each_entry_safe(node
, safe
, &bat_priv
->tt_roam_list
, list
) {
1786 list_del(&node
->list
);
1790 spin_unlock_bh(&bat_priv
->tt_roam_list_lock
);
1793 static void tt_roam_purge(struct bat_priv
*bat_priv
)
1795 struct tt_roam_node
*node
, *safe
;
1797 spin_lock_bh(&bat_priv
->tt_roam_list_lock
);
1798 list_for_each_entry_safe(node
, safe
, &bat_priv
->tt_roam_list
, list
) {
1799 if (!has_timed_out(node
->first_time
, ROAMING_MAX_TIME
))
1802 list_del(&node
->list
);
1805 spin_unlock_bh(&bat_priv
->tt_roam_list_lock
);
1808 /* This function checks whether the client already reached the
1809 * maximum number of possible roaming phases. In this case the ROAMING_ADV
1812 * returns true if the ROAMING_ADV can be sent, false otherwise */
1813 static bool tt_check_roam_count(struct bat_priv
*bat_priv
,
1816 struct tt_roam_node
*tt_roam_node
;
1819 spin_lock_bh(&bat_priv
->tt_roam_list_lock
);
1820 /* The new tt_req will be issued only if I'm not waiting for a
1821 * reply from the same orig_node yet */
1822 list_for_each_entry(tt_roam_node
, &bat_priv
->tt_roam_list
, list
) {
1823 if (!compare_eth(tt_roam_node
->addr
, client
))
1826 if (has_timed_out(tt_roam_node
->first_time
, ROAMING_MAX_TIME
))
1829 if (!atomic_dec_not_zero(&tt_roam_node
->counter
))
1830 /* Sorry, you roamed too many times! */
1837 tt_roam_node
= kmalloc(sizeof(*tt_roam_node
), GFP_ATOMIC
);
1841 tt_roam_node
->first_time
= jiffies
;
1842 atomic_set(&tt_roam_node
->counter
, ROAMING_MAX_COUNT
- 1);
1843 memcpy(tt_roam_node
->addr
, client
, ETH_ALEN
);
1845 list_add(&tt_roam_node
->list
, &bat_priv
->tt_roam_list
);
1850 spin_unlock_bh(&bat_priv
->tt_roam_list_lock
);
1854 static void send_roam_adv(struct bat_priv
*bat_priv
, uint8_t *client
,
1855 struct orig_node
*orig_node
)
1857 struct neigh_node
*neigh_node
= NULL
;
1858 struct sk_buff
*skb
= NULL
;
1859 struct roam_adv_packet
*roam_adv_packet
;
1861 struct hard_iface
*primary_if
;
1863 /* before going on we have to check whether the client has
1864 * already roamed to us too many times */
1865 if (!tt_check_roam_count(bat_priv
, client
))
1868 skb
= dev_alloc_skb(sizeof(struct roam_adv_packet
) + ETH_HLEN
);
1872 skb_reserve(skb
, ETH_HLEN
);
1874 roam_adv_packet
= (struct roam_adv_packet
*)skb_put(skb
,
1875 sizeof(struct roam_adv_packet
));
1877 roam_adv_packet
->header
.packet_type
= BAT_ROAM_ADV
;
1878 roam_adv_packet
->header
.version
= COMPAT_VERSION
;
1879 roam_adv_packet
->header
.ttl
= TTL
;
1880 primary_if
= primary_if_get_selected(bat_priv
);
1883 memcpy(roam_adv_packet
->src
, primary_if
->net_dev
->dev_addr
, ETH_ALEN
);
1884 hardif_free_ref(primary_if
);
1885 memcpy(roam_adv_packet
->dst
, orig_node
->orig
, ETH_ALEN
);
1886 memcpy(roam_adv_packet
->client
, client
, ETH_ALEN
);
1888 neigh_node
= orig_node_get_router(orig_node
);
1892 bat_dbg(DBG_TT
, bat_priv
,
1893 "Sending ROAMING_ADV to %pM (client %pM) via %pM\n",
1894 orig_node
->orig
, client
, neigh_node
->addr
);
1896 send_skb_packet(skb
, neigh_node
->if_incoming
, neigh_node
->addr
);
1901 neigh_node_free_ref(neigh_node
);
1907 static void tt_purge(struct work_struct
*work
)
1909 struct delayed_work
*delayed_work
=
1910 container_of(work
, struct delayed_work
, work
);
1911 struct bat_priv
*bat_priv
=
1912 container_of(delayed_work
, struct bat_priv
, tt_work
);
1914 tt_local_purge(bat_priv
);
1915 tt_global_roam_purge(bat_priv
);
1916 tt_req_purge(bat_priv
);
1917 tt_roam_purge(bat_priv
);
1919 tt_start_timer(bat_priv
);
1922 void tt_free(struct bat_priv
*bat_priv
)
1924 cancel_delayed_work_sync(&bat_priv
->tt_work
);
1926 tt_local_table_free(bat_priv
);
1927 tt_global_table_free(bat_priv
);
1928 tt_req_list_free(bat_priv
);
1929 tt_changes_list_free(bat_priv
);
1930 tt_roam_list_free(bat_priv
);
1932 kfree(bat_priv
->tt_buff
);
1935 /* This function will enable or disable the specified flags for all the entries
1936 * in the given hash table and returns the number of modified entries */
1937 static uint16_t tt_set_flags(struct hashtable_t
*hash
, uint16_t flags
,
1941 uint16_t changed_num
= 0;
1942 struct hlist_head
*head
;
1943 struct hlist_node
*node
;
1944 struct tt_common_entry
*tt_common_entry
;
1949 for (i
= 0; i
< hash
->size
; i
++) {
1950 head
= &hash
->table
[i
];
1953 hlist_for_each_entry_rcu(tt_common_entry
, node
,
1956 if ((tt_common_entry
->flags
& flags
) == flags
)
1958 tt_common_entry
->flags
|= flags
;
1960 if (!(tt_common_entry
->flags
& flags
))
1962 tt_common_entry
->flags
&= ~flags
;
1972 /* Purge out all the tt local entries marked with TT_CLIENT_PENDING */
1973 static void tt_local_purge_pending_clients(struct bat_priv
*bat_priv
)
1975 struct hashtable_t
*hash
= bat_priv
->tt_local_hash
;
1976 struct tt_common_entry
*tt_common_entry
;
1977 struct tt_local_entry
*tt_local_entry
;
1978 struct hlist_node
*node
, *node_tmp
;
1979 struct hlist_head
*head
;
1980 spinlock_t
*list_lock
; /* protects write access to the hash lists */
1986 for (i
= 0; i
< hash
->size
; i
++) {
1987 head
= &hash
->table
[i
];
1988 list_lock
= &hash
->list_locks
[i
];
1990 spin_lock_bh(list_lock
);
1991 hlist_for_each_entry_safe(tt_common_entry
, node
, node_tmp
,
1993 if (!(tt_common_entry
->flags
& TT_CLIENT_PENDING
))
1996 bat_dbg(DBG_TT
, bat_priv
,
1997 "Deleting local tt entry (%pM): pending\n",
1998 tt_common_entry
->addr
);
2000 atomic_dec(&bat_priv
->num_local_tt
);
2001 hlist_del_rcu(node
);
2002 tt_local_entry
= container_of(tt_common_entry
,
2003 struct tt_local_entry
,
2005 tt_local_entry_free_ref(tt_local_entry
);
2007 spin_unlock_bh(list_lock
);
2012 void tt_commit_changes(struct bat_priv
*bat_priv
)
2014 uint16_t changed_num
= tt_set_flags(bat_priv
->tt_local_hash
,
2015 TT_CLIENT_NEW
, false);
2016 /* all the reset entries have now to be effectively counted as local
2018 atomic_add(changed_num
, &bat_priv
->num_local_tt
);
2019 tt_local_purge_pending_clients(bat_priv
);
2021 /* Increment the TTVN only once per OGM interval */
2022 atomic_inc(&bat_priv
->ttvn
);
2023 bat_dbg(DBG_TT
, bat_priv
, "Local changes committed, updating to ttvn %u\n",
2024 (uint8_t)atomic_read(&bat_priv
->ttvn
));
2025 bat_priv
->tt_poss_change
= false;
2028 bool is_ap_isolated(struct bat_priv
*bat_priv
, uint8_t *src
, uint8_t *dst
)
2030 struct tt_local_entry
*tt_local_entry
= NULL
;
2031 struct tt_global_entry
*tt_global_entry
= NULL
;
2034 if (!atomic_read(&bat_priv
->ap_isolation
))
2037 tt_local_entry
= tt_local_hash_find(bat_priv
, dst
);
2038 if (!tt_local_entry
)
2041 tt_global_entry
= tt_global_hash_find(bat_priv
, src
);
2042 if (!tt_global_entry
)
2045 if (_is_ap_isolated(tt_local_entry
, tt_global_entry
))
2051 if (tt_global_entry
)
2052 tt_global_entry_free_ref(tt_global_entry
);
2054 tt_local_entry_free_ref(tt_local_entry
);
2058 void tt_update_orig(struct bat_priv
*bat_priv
, struct orig_node
*orig_node
,
2059 const unsigned char *tt_buff
, uint8_t tt_num_changes
,
2060 uint8_t ttvn
, uint16_t tt_crc
)
2062 uint8_t orig_ttvn
= (uint8_t)atomic_read(&orig_node
->last_ttvn
);
2063 bool full_table
= true;
2065 /* don't care about a backbone gateways updates. */
2066 if (bla_is_backbone_gw_orig(bat_priv
, orig_node
->orig
))
2069 /* orig table not initialised AND first diff is in the OGM OR the ttvn
2070 * increased by one -> we can apply the attached changes */
2071 if ((!orig_node
->tt_initialised
&& ttvn
== 1) ||
2072 ttvn
- orig_ttvn
== 1) {
2073 /* the OGM could not contain the changes due to their size or
2074 * because they have already been sent TT_OGM_APPEND_MAX times.
2075 * In this case send a tt request */
2076 if (!tt_num_changes
) {
2081 tt_update_changes(bat_priv
, orig_node
, tt_num_changes
, ttvn
,
2082 (struct tt_change
*)tt_buff
);
2084 /* Even if we received the precomputed crc with the OGM, we
2085 * prefer to recompute it to spot any possible inconsistency
2086 * in the global table */
2087 orig_node
->tt_crc
= tt_global_crc(bat_priv
, orig_node
);
2089 /* The ttvn alone is not enough to guarantee consistency
2090 * because a single value could represent different states
2091 * (due to the wrap around). Thus a node has to check whether
2092 * the resulting table (after applying the changes) is still
2093 * consistent or not. E.g. a node could disconnect while its
2094 * ttvn is X and reconnect on ttvn = X + TTVN_MAX: in this case
2095 * checking the CRC value is mandatory to detect the
2097 if (orig_node
->tt_crc
!= tt_crc
)
2100 /* Roaming phase is over: tables are in sync again. I can
2102 orig_node
->tt_poss_change
= false;
2104 /* if we missed more than one change or our tables are not
2105 * in sync anymore -> request fresh tt data */
2107 if (!orig_node
->tt_initialised
|| ttvn
!= orig_ttvn
||
2108 orig_node
->tt_crc
!= tt_crc
) {
2110 bat_dbg(DBG_TT
, bat_priv
,
2111 "TT inconsistency for %pM. Need to retrieve the correct information (ttvn: %u last_ttvn: %u crc: %u last_crc: %u num_changes: %u)\n",
2112 orig_node
->orig
, ttvn
, orig_ttvn
, tt_crc
,
2113 orig_node
->tt_crc
, tt_num_changes
);
2114 send_tt_request(bat_priv
, orig_node
, ttvn
, tt_crc
,