1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (C) 2007-2017 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, see <http://www.gnu.org/licenses/>.
19 #include "bat_iv_ogm.h"
22 #include <linux/atomic.h>
23 #include <linux/bitmap.h>
24 #include <linux/bitops.h>
25 #include <linux/bug.h>
26 #include <linux/byteorder/generic.h>
27 #include <linux/cache.h>
28 #include <linux/errno.h>
29 #include <linux/etherdevice.h>
30 #include <linux/gfp.h>
31 #include <linux/if_ether.h>
32 #include <linux/init.h>
33 #include <linux/jiffies.h>
34 #include <linux/kernel.h>
35 #include <linux/kref.h>
36 #include <linux/list.h>
37 #include <linux/lockdep.h>
38 #include <linux/netdevice.h>
39 #include <linux/netlink.h>
40 #include <linux/pkt_sched.h>
41 #include <linux/printk.h>
42 #include <linux/random.h>
43 #include <linux/rculist.h>
44 #include <linux/rcupdate.h>
45 #include <linux/seq_file.h>
46 #include <linux/skbuff.h>
47 #include <linux/slab.h>
48 #include <linux/spinlock.h>
49 #include <linux/stddef.h>
50 #include <linux/string.h>
51 #include <linux/types.h>
52 #include <linux/workqueue.h>
53 #include <net/genetlink.h>
54 #include <net/netlink.h>
55 #include <uapi/linux/batadv_packet.h>
56 #include <uapi/linux/batman_adv.h>
60 #include "gateway_client.h"
61 #include "hard-interface.h"
65 #include "network-coding.h"
66 #include "originator.h"
69 #include "translation-table.h"
72 static void batadv_iv_send_outstanding_bat_ogm_packet(struct work_struct *work);
75 * enum batadv_dup_status - duplicate status
77 enum batadv_dup_status {
78 /** @BATADV_NO_DUP: the packet is no duplicate */
82 * @BATADV_ORIG_DUP: OGM is a duplicate in the originator (but not for
87 /** @BATADV_NEIGH_DUP: OGM is a duplicate for the neighbor */
91 * @BATADV_PROTECTED: originator is currently protected (after reboot)
97 * batadv_ring_buffer_set() - update the ring buffer with the given value
98 * @lq_recv: pointer to the ring buffer
99 * @lq_index: index to store the value at
100 * @value: value to store in the ring buffer
102 static void batadv_ring_buffer_set(u8 lq_recv[], u8 *lq_index, u8 value)
104 lq_recv[*lq_index] = value;
105 *lq_index = (*lq_index + 1) % BATADV_TQ_GLOBAL_WINDOW_SIZE;
109 * batadv_ring_buffer_avg() - compute the average of all non-zero values stored
110 * in the given ring buffer
111 * @lq_recv: pointer to the ring buffer
113 * Return: computed average value.
115 static u8 batadv_ring_buffer_avg(const u8 lq_recv[])
124 while (i < BATADV_TQ_GLOBAL_WINDOW_SIZE) {
137 return (u8)(sum / count);
141 * batadv_iv_ogm_orig_free() - free the private resources allocated for this
143 * @orig_node: the orig_node for which the resources have to be free'd
145 static void batadv_iv_ogm_orig_free(struct batadv_orig_node *orig_node)
147 kfree(orig_node->bat_iv.bcast_own);
148 kfree(orig_node->bat_iv.bcast_own_sum);
152 * batadv_iv_ogm_orig_add_if() - change the private structures of the orig_node
153 * to include the new hard-interface
154 * @orig_node: the orig_node that has to be changed
155 * @max_if_num: the current amount of interfaces
157 * Return: 0 on success, a negative error code otherwise.
159 static int batadv_iv_ogm_orig_add_if(struct batadv_orig_node *orig_node,
166 spin_lock_bh(&orig_node->bat_iv.ogm_cnt_lock);
168 old_size = (max_if_num - 1) * sizeof(unsigned long) * BATADV_NUM_WORDS;
169 data_ptr = kmalloc_array(max_if_num,
170 BATADV_NUM_WORDS * sizeof(unsigned long),
175 memcpy(data_ptr, orig_node->bat_iv.bcast_own, old_size);
176 kfree(orig_node->bat_iv.bcast_own);
177 orig_node->bat_iv.bcast_own = data_ptr;
179 data_ptr = kmalloc_array(max_if_num, sizeof(u8), GFP_ATOMIC);
183 memcpy(data_ptr, orig_node->bat_iv.bcast_own_sum,
184 (max_if_num - 1) * sizeof(u8));
185 kfree(orig_node->bat_iv.bcast_own_sum);
186 orig_node->bat_iv.bcast_own_sum = data_ptr;
191 spin_unlock_bh(&orig_node->bat_iv.ogm_cnt_lock);
197 * batadv_iv_ogm_drop_bcast_own_entry() - drop section of bcast_own
198 * @orig_node: the orig_node that has to be changed
199 * @max_if_num: the current amount of interfaces
200 * @del_if_num: the index of the interface being removed
203 batadv_iv_ogm_drop_bcast_own_entry(struct batadv_orig_node *orig_node,
204 int max_if_num, int del_if_num)
210 lockdep_assert_held(&orig_node->bat_iv.ogm_cnt_lock);
212 chunk_size = sizeof(unsigned long) * BATADV_NUM_WORDS;
213 data_ptr = kmalloc_array(max_if_num, chunk_size, GFP_ATOMIC);
215 /* use old buffer when new one could not be allocated */
216 data_ptr = orig_node->bat_iv.bcast_own;
218 /* copy first part */
219 memmove(data_ptr, orig_node->bat_iv.bcast_own, del_if_num * chunk_size);
221 /* copy second part */
222 if_offset = (del_if_num + 1) * chunk_size;
223 memmove((char *)data_ptr + del_if_num * chunk_size,
224 (uint8_t *)orig_node->bat_iv.bcast_own + if_offset,
225 (max_if_num - del_if_num) * chunk_size);
227 /* bcast_own was shrunk down in new buffer; free old one */
228 if (orig_node->bat_iv.bcast_own != data_ptr) {
229 kfree(orig_node->bat_iv.bcast_own);
230 orig_node->bat_iv.bcast_own = data_ptr;
235 * batadv_iv_ogm_drop_bcast_own_sum_entry() - drop section of bcast_own_sum
236 * @orig_node: the orig_node that has to be changed
237 * @max_if_num: the current amount of interfaces
238 * @del_if_num: the index of the interface being removed
241 batadv_iv_ogm_drop_bcast_own_sum_entry(struct batadv_orig_node *orig_node,
242 int max_if_num, int del_if_num)
247 lockdep_assert_held(&orig_node->bat_iv.ogm_cnt_lock);
249 data_ptr = kmalloc_array(max_if_num, sizeof(u8), GFP_ATOMIC);
251 /* use old buffer when new one could not be allocated */
252 data_ptr = orig_node->bat_iv.bcast_own_sum;
254 memmove(data_ptr, orig_node->bat_iv.bcast_own_sum,
255 del_if_num * sizeof(u8));
257 if_offset = (del_if_num + 1) * sizeof(u8);
258 memmove((char *)data_ptr + del_if_num * sizeof(u8),
259 orig_node->bat_iv.bcast_own_sum + if_offset,
260 (max_if_num - del_if_num) * sizeof(u8));
262 /* bcast_own_sum was shrunk down in new buffer; free old one */
263 if (orig_node->bat_iv.bcast_own_sum != data_ptr) {
264 kfree(orig_node->bat_iv.bcast_own_sum);
265 orig_node->bat_iv.bcast_own_sum = data_ptr;
270 * batadv_iv_ogm_orig_del_if() - change the private structures of the orig_node
271 * to exclude the removed interface
272 * @orig_node: the orig_node that has to be changed
273 * @max_if_num: the current amount of interfaces
274 * @del_if_num: the index of the interface being removed
276 * Return: 0 on success, a negative error code otherwise.
278 static int batadv_iv_ogm_orig_del_if(struct batadv_orig_node *orig_node,
279 int max_if_num, int del_if_num)
281 spin_lock_bh(&orig_node->bat_iv.ogm_cnt_lock);
283 if (max_if_num == 0) {
284 kfree(orig_node->bat_iv.bcast_own);
285 kfree(orig_node->bat_iv.bcast_own_sum);
286 orig_node->bat_iv.bcast_own = NULL;
287 orig_node->bat_iv.bcast_own_sum = NULL;
289 batadv_iv_ogm_drop_bcast_own_entry(orig_node, max_if_num,
291 batadv_iv_ogm_drop_bcast_own_sum_entry(orig_node, max_if_num,
295 spin_unlock_bh(&orig_node->bat_iv.ogm_cnt_lock);
301 * batadv_iv_ogm_orig_get() - retrieve or create (if does not exist) an
303 * @bat_priv: the bat priv with all the soft interface information
304 * @addr: mac address of the originator
306 * Return: the originator object corresponding to the passed mac address or NULL
308 * If the object does not exists it is created an initialised.
310 static struct batadv_orig_node *
311 batadv_iv_ogm_orig_get(struct batadv_priv *bat_priv, const u8 *addr)
313 struct batadv_orig_node *orig_node;
314 int size, hash_added;
316 orig_node = batadv_orig_hash_find(bat_priv, addr);
320 orig_node = batadv_orig_node_new(bat_priv, addr);
324 spin_lock_init(&orig_node->bat_iv.ogm_cnt_lock);
326 size = bat_priv->num_ifaces * sizeof(unsigned long) * BATADV_NUM_WORDS;
327 orig_node->bat_iv.bcast_own = kzalloc(size, GFP_ATOMIC);
328 if (!orig_node->bat_iv.bcast_own)
331 size = bat_priv->num_ifaces * sizeof(u8);
332 orig_node->bat_iv.bcast_own_sum = kzalloc(size, GFP_ATOMIC);
333 if (!orig_node->bat_iv.bcast_own_sum)
336 kref_get(&orig_node->refcount);
337 hash_added = batadv_hash_add(bat_priv->orig_hash, batadv_compare_orig,
338 batadv_choose_orig, orig_node,
339 &orig_node->hash_entry);
341 goto free_orig_node_hash;
346 batadv_orig_node_put(orig_node);
348 batadv_orig_node_put(orig_node);
353 static struct batadv_neigh_node *
354 batadv_iv_ogm_neigh_new(struct batadv_hard_iface *hard_iface,
355 const u8 *neigh_addr,
356 struct batadv_orig_node *orig_node,
357 struct batadv_orig_node *orig_neigh)
359 struct batadv_neigh_node *neigh_node;
361 neigh_node = batadv_neigh_node_get_or_create(orig_node,
362 hard_iface, neigh_addr);
366 neigh_node->orig_node = orig_neigh;
372 static int batadv_iv_ogm_iface_enable(struct batadv_hard_iface *hard_iface)
374 struct batadv_ogm_packet *batadv_ogm_packet;
375 unsigned char *ogm_buff;
378 /* randomize initial seqno to avoid collision */
379 get_random_bytes(&random_seqno, sizeof(random_seqno));
380 atomic_set(&hard_iface->bat_iv.ogm_seqno, random_seqno);
382 hard_iface->bat_iv.ogm_buff_len = BATADV_OGM_HLEN;
383 ogm_buff = kmalloc(hard_iface->bat_iv.ogm_buff_len, GFP_ATOMIC);
387 hard_iface->bat_iv.ogm_buff = ogm_buff;
389 batadv_ogm_packet = (struct batadv_ogm_packet *)ogm_buff;
390 batadv_ogm_packet->packet_type = BATADV_IV_OGM;
391 batadv_ogm_packet->version = BATADV_COMPAT_VERSION;
392 batadv_ogm_packet->ttl = 2;
393 batadv_ogm_packet->flags = BATADV_NO_FLAGS;
394 batadv_ogm_packet->reserved = 0;
395 batadv_ogm_packet->tq = BATADV_TQ_MAX_VALUE;
400 static void batadv_iv_ogm_iface_disable(struct batadv_hard_iface *hard_iface)
402 kfree(hard_iface->bat_iv.ogm_buff);
403 hard_iface->bat_iv.ogm_buff = NULL;
406 static void batadv_iv_ogm_iface_update_mac(struct batadv_hard_iface *hard_iface)
408 struct batadv_ogm_packet *batadv_ogm_packet;
409 unsigned char *ogm_buff = hard_iface->bat_iv.ogm_buff;
411 batadv_ogm_packet = (struct batadv_ogm_packet *)ogm_buff;
412 ether_addr_copy(batadv_ogm_packet->orig,
413 hard_iface->net_dev->dev_addr);
414 ether_addr_copy(batadv_ogm_packet->prev_sender,
415 hard_iface->net_dev->dev_addr);
419 batadv_iv_ogm_primary_iface_set(struct batadv_hard_iface *hard_iface)
421 struct batadv_ogm_packet *batadv_ogm_packet;
422 unsigned char *ogm_buff = hard_iface->bat_iv.ogm_buff;
424 batadv_ogm_packet = (struct batadv_ogm_packet *)ogm_buff;
425 batadv_ogm_packet->ttl = BATADV_TTL;
428 /* when do we schedule our own ogm to be sent */
430 batadv_iv_ogm_emit_send_time(const struct batadv_priv *bat_priv)
434 msecs = atomic_read(&bat_priv->orig_interval) - BATADV_JITTER;
435 msecs += prandom_u32() % (2 * BATADV_JITTER);
437 return jiffies + msecs_to_jiffies(msecs);
440 /* when do we schedule a ogm packet to be sent */
441 static unsigned long batadv_iv_ogm_fwd_send_time(void)
443 return jiffies + msecs_to_jiffies(prandom_u32() % (BATADV_JITTER / 2));
446 /* apply hop penalty for a normal link */
447 static u8 batadv_hop_penalty(u8 tq, const struct batadv_priv *bat_priv)
449 int hop_penalty = atomic_read(&bat_priv->hop_penalty);
452 new_tq = tq * (BATADV_TQ_MAX_VALUE - hop_penalty);
453 new_tq /= BATADV_TQ_MAX_VALUE;
459 * batadv_iv_ogm_aggr_packet() - checks if there is another OGM attached
460 * @buff_pos: current position in the skb
461 * @packet_len: total length of the skb
462 * @tvlv_len: tvlv length of the previously considered OGM
464 * Return: true if there is enough space for another OGM, false otherwise.
466 static bool batadv_iv_ogm_aggr_packet(int buff_pos, int packet_len,
469 int next_buff_pos = 0;
471 next_buff_pos += buff_pos + BATADV_OGM_HLEN;
472 next_buff_pos += ntohs(tvlv_len);
474 return (next_buff_pos <= packet_len) &&
475 (next_buff_pos <= BATADV_MAX_AGGREGATION_BYTES);
478 /* send a batman ogm to a given interface */
479 static void batadv_iv_ogm_send_to_if(struct batadv_forw_packet *forw_packet,
480 struct batadv_hard_iface *hard_iface)
482 struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
486 struct batadv_ogm_packet *batadv_ogm_packet;
490 if (hard_iface->if_status != BATADV_IF_ACTIVE)
495 packet_pos = forw_packet->skb->data;
496 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_pos;
498 /* adjust all flags and log packets */
499 while (batadv_iv_ogm_aggr_packet(buff_pos, forw_packet->packet_len,
500 batadv_ogm_packet->tvlv_len)) {
501 /* we might have aggregated direct link packets with an
502 * ordinary base packet
504 if (forw_packet->direct_link_flags & BIT(packet_num) &&
505 forw_packet->if_incoming == hard_iface)
506 batadv_ogm_packet->flags |= BATADV_DIRECTLINK;
508 batadv_ogm_packet->flags &= ~BATADV_DIRECTLINK;
510 if (packet_num > 0 || !forw_packet->own)
511 fwd_str = "Forwarding";
513 fwd_str = "Sending own";
515 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
516 "%s %spacket (originator %pM, seqno %u, TQ %d, TTL %d, IDF %s) on interface %s [%pM]\n",
517 fwd_str, (packet_num > 0 ? "aggregated " : ""),
518 batadv_ogm_packet->orig,
519 ntohl(batadv_ogm_packet->seqno),
520 batadv_ogm_packet->tq, batadv_ogm_packet->ttl,
521 ((batadv_ogm_packet->flags & BATADV_DIRECTLINK) ?
523 hard_iface->net_dev->name,
524 hard_iface->net_dev->dev_addr);
526 buff_pos += BATADV_OGM_HLEN;
527 buff_pos += ntohs(batadv_ogm_packet->tvlv_len);
529 packet_pos = forw_packet->skb->data + buff_pos;
530 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_pos;
533 /* create clone because function is called more than once */
534 skb = skb_clone(forw_packet->skb, GFP_ATOMIC);
536 batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_TX);
537 batadv_add_counter(bat_priv, BATADV_CNT_MGMT_TX_BYTES,
538 skb->len + ETH_HLEN);
539 batadv_send_broadcast_skb(skb, hard_iface);
543 /* send a batman ogm packet */
544 static void batadv_iv_ogm_emit(struct batadv_forw_packet *forw_packet)
546 struct net_device *soft_iface;
548 if (!forw_packet->if_incoming) {
549 pr_err("Error - can't forward packet: incoming iface not specified\n");
553 soft_iface = forw_packet->if_incoming->soft_iface;
555 if (WARN_ON(!forw_packet->if_outgoing))
558 if (WARN_ON(forw_packet->if_outgoing->soft_iface != soft_iface))
561 if (forw_packet->if_incoming->if_status != BATADV_IF_ACTIVE)
564 /* only for one specific outgoing interface */
565 batadv_iv_ogm_send_to_if(forw_packet, forw_packet->if_outgoing);
569 * batadv_iv_ogm_can_aggregate() - find out if an OGM can be aggregated on an
570 * existing forward packet
571 * @new_bat_ogm_packet: OGM packet to be aggregated
572 * @bat_priv: the bat priv with all the soft interface information
573 * @packet_len: (total) length of the OGM
574 * @send_time: timestamp (jiffies) when the packet is to be sent
575 * @directlink: true if this is a direct link packet
576 * @if_incoming: interface where the packet was received
577 * @if_outgoing: interface for which the retransmission should be considered
578 * @forw_packet: the forwarded packet which should be checked
580 * Return: true if new_packet can be aggregated with forw_packet
583 batadv_iv_ogm_can_aggregate(const struct batadv_ogm_packet *new_bat_ogm_packet,
584 struct batadv_priv *bat_priv,
585 int packet_len, unsigned long send_time,
587 const struct batadv_hard_iface *if_incoming,
588 const struct batadv_hard_iface *if_outgoing,
589 const struct batadv_forw_packet *forw_packet)
591 struct batadv_ogm_packet *batadv_ogm_packet;
592 int aggregated_bytes = forw_packet->packet_len + packet_len;
593 struct batadv_hard_iface *primary_if = NULL;
595 unsigned long aggregation_end_time;
597 batadv_ogm_packet = (struct batadv_ogm_packet *)forw_packet->skb->data;
598 aggregation_end_time = send_time;
599 aggregation_end_time += msecs_to_jiffies(BATADV_MAX_AGGREGATION_MS);
601 /* we can aggregate the current packet to this aggregated packet
604 * - the send time is within our MAX_AGGREGATION_MS time
605 * - the resulting packet wont be bigger than
606 * MAX_AGGREGATION_BYTES
607 * otherwise aggregation is not possible
609 if (!time_before(send_time, forw_packet->send_time) ||
610 !time_after_eq(aggregation_end_time, forw_packet->send_time))
613 if (aggregated_bytes > BATADV_MAX_AGGREGATION_BYTES)
616 /* packet is not leaving on the same interface. */
617 if (forw_packet->if_outgoing != if_outgoing)
620 /* check aggregation compatibility
621 * -> direct link packets are broadcasted on
622 * their interface only
623 * -> aggregate packet if the current packet is
624 * a "global" packet as well as the base
627 primary_if = batadv_primary_if_get_selected(bat_priv);
631 /* packets without direct link flag and high TTL
632 * are flooded through the net
635 !(batadv_ogm_packet->flags & BATADV_DIRECTLINK) &&
636 batadv_ogm_packet->ttl != 1 &&
638 /* own packets originating non-primary
639 * interfaces leave only that interface
641 (!forw_packet->own ||
642 forw_packet->if_incoming == primary_if)) {
647 /* if the incoming packet is sent via this one
648 * interface only - we still can aggregate
651 new_bat_ogm_packet->ttl == 1 &&
652 forw_packet->if_incoming == if_incoming &&
654 /* packets from direct neighbors or
655 * own secondary interface packets
656 * (= secondary interface packets in general)
658 (batadv_ogm_packet->flags & BATADV_DIRECTLINK ||
660 forw_packet->if_incoming != primary_if))) {
667 batadv_hardif_put(primary_if);
672 * batadv_iv_ogm_aggregate_new() - create a new aggregated packet and add this
674 * @packet_buff: pointer to the OGM
675 * @packet_len: (total) length of the OGM
676 * @send_time: timestamp (jiffies) when the packet is to be sent
677 * @direct_link: whether this OGM has direct link status
678 * @if_incoming: interface where the packet was received
679 * @if_outgoing: interface for which the retransmission should be considered
680 * @own_packet: true if it is a self-generated ogm
682 static void batadv_iv_ogm_aggregate_new(const unsigned char *packet_buff,
683 int packet_len, unsigned long send_time,
685 struct batadv_hard_iface *if_incoming,
686 struct batadv_hard_iface *if_outgoing,
689 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
690 struct batadv_forw_packet *forw_packet_aggr;
692 unsigned char *skb_buff;
693 unsigned int skb_size;
694 atomic_t *queue_left = own_packet ? NULL : &bat_priv->batman_queue_left;
696 if (atomic_read(&bat_priv->aggregated_ogms) &&
697 packet_len < BATADV_MAX_AGGREGATION_BYTES)
698 skb_size = BATADV_MAX_AGGREGATION_BYTES;
700 skb_size = packet_len;
702 skb_size += ETH_HLEN;
704 skb = netdev_alloc_skb_ip_align(NULL, skb_size);
708 forw_packet_aggr = batadv_forw_packet_alloc(if_incoming, if_outgoing,
709 queue_left, bat_priv, skb);
710 if (!forw_packet_aggr) {
715 forw_packet_aggr->skb->priority = TC_PRIO_CONTROL;
716 skb_reserve(forw_packet_aggr->skb, ETH_HLEN);
718 skb_buff = skb_put(forw_packet_aggr->skb, packet_len);
719 forw_packet_aggr->packet_len = packet_len;
720 memcpy(skb_buff, packet_buff, packet_len);
722 forw_packet_aggr->own = own_packet;
723 forw_packet_aggr->direct_link_flags = BATADV_NO_FLAGS;
724 forw_packet_aggr->send_time = send_time;
726 /* save packet direct link flag status */
728 forw_packet_aggr->direct_link_flags |= 1;
730 INIT_DELAYED_WORK(&forw_packet_aggr->delayed_work,
731 batadv_iv_send_outstanding_bat_ogm_packet);
733 batadv_forw_packet_ogmv1_queue(bat_priv, forw_packet_aggr, send_time);
736 /* aggregate a new packet into the existing ogm packet */
737 static void batadv_iv_ogm_aggregate(struct batadv_forw_packet *forw_packet_aggr,
738 const unsigned char *packet_buff,
739 int packet_len, bool direct_link)
741 unsigned long new_direct_link_flag;
743 skb_put_data(forw_packet_aggr->skb, packet_buff, packet_len);
744 forw_packet_aggr->packet_len += packet_len;
745 forw_packet_aggr->num_packets++;
747 /* save packet direct link flag status */
749 new_direct_link_flag = BIT(forw_packet_aggr->num_packets);
750 forw_packet_aggr->direct_link_flags |= new_direct_link_flag;
755 * batadv_iv_ogm_queue_add() - queue up an OGM for transmission
756 * @bat_priv: the bat priv with all the soft interface information
757 * @packet_buff: pointer to the OGM
758 * @packet_len: (total) length of the OGM
759 * @if_incoming: interface where the packet was received
760 * @if_outgoing: interface for which the retransmission should be considered
761 * @own_packet: true if it is a self-generated ogm
762 * @send_time: timestamp (jiffies) when the packet is to be sent
764 static void batadv_iv_ogm_queue_add(struct batadv_priv *bat_priv,
765 unsigned char *packet_buff,
767 struct batadv_hard_iface *if_incoming,
768 struct batadv_hard_iface *if_outgoing,
769 int own_packet, unsigned long send_time)
771 /* _aggr -> pointer to the packet we want to aggregate with
772 * _pos -> pointer to the position in the queue
774 struct batadv_forw_packet *forw_packet_aggr = NULL;
775 struct batadv_forw_packet *forw_packet_pos = NULL;
776 struct batadv_ogm_packet *batadv_ogm_packet;
778 unsigned long max_aggregation_jiffies;
780 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_buff;
781 direct_link = !!(batadv_ogm_packet->flags & BATADV_DIRECTLINK);
782 max_aggregation_jiffies = msecs_to_jiffies(BATADV_MAX_AGGREGATION_MS);
784 /* find position for the packet in the forward queue */
785 spin_lock_bh(&bat_priv->forw_bat_list_lock);
786 /* own packets are not to be aggregated */
787 if (atomic_read(&bat_priv->aggregated_ogms) && !own_packet) {
788 hlist_for_each_entry(forw_packet_pos,
789 &bat_priv->forw_bat_list, list) {
790 if (batadv_iv_ogm_can_aggregate(batadv_ogm_packet,
791 bat_priv, packet_len,
792 send_time, direct_link,
796 forw_packet_aggr = forw_packet_pos;
802 /* nothing to aggregate with - either aggregation disabled or no
803 * suitable aggregation packet found
805 if (!forw_packet_aggr) {
806 /* the following section can run without the lock */
807 spin_unlock_bh(&bat_priv->forw_bat_list_lock);
809 /* if we could not aggregate this packet with one of the others
810 * we hold it back for a while, so that it might be aggregated
813 if (!own_packet && atomic_read(&bat_priv->aggregated_ogms))
814 send_time += max_aggregation_jiffies;
816 batadv_iv_ogm_aggregate_new(packet_buff, packet_len,
817 send_time, direct_link,
818 if_incoming, if_outgoing,
821 batadv_iv_ogm_aggregate(forw_packet_aggr, packet_buff,
822 packet_len, direct_link);
823 spin_unlock_bh(&bat_priv->forw_bat_list_lock);
827 static void batadv_iv_ogm_forward(struct batadv_orig_node *orig_node,
828 const struct ethhdr *ethhdr,
829 struct batadv_ogm_packet *batadv_ogm_packet,
830 bool is_single_hop_neigh,
831 bool is_from_best_next_hop,
832 struct batadv_hard_iface *if_incoming,
833 struct batadv_hard_iface *if_outgoing)
835 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
838 if (batadv_ogm_packet->ttl <= 1) {
839 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, "ttl exceeded\n");
843 if (!is_from_best_next_hop) {
844 /* Mark the forwarded packet when it is not coming from our
845 * best next hop. We still need to forward the packet for our
846 * neighbor link quality detection to work in case the packet
847 * originated from a single hop neighbor. Otherwise we can
848 * simply drop the ogm.
850 if (is_single_hop_neigh)
851 batadv_ogm_packet->flags |= BATADV_NOT_BEST_NEXT_HOP;
856 tvlv_len = ntohs(batadv_ogm_packet->tvlv_len);
858 batadv_ogm_packet->ttl--;
859 ether_addr_copy(batadv_ogm_packet->prev_sender, ethhdr->h_source);
861 /* apply hop penalty */
862 batadv_ogm_packet->tq = batadv_hop_penalty(batadv_ogm_packet->tq,
865 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
866 "Forwarding packet: tq: %i, ttl: %i\n",
867 batadv_ogm_packet->tq, batadv_ogm_packet->ttl);
869 if (is_single_hop_neigh)
870 batadv_ogm_packet->flags |= BATADV_DIRECTLINK;
872 batadv_ogm_packet->flags &= ~BATADV_DIRECTLINK;
874 batadv_iv_ogm_queue_add(bat_priv, (unsigned char *)batadv_ogm_packet,
875 BATADV_OGM_HLEN + tvlv_len,
876 if_incoming, if_outgoing, 0,
877 batadv_iv_ogm_fwd_send_time());
881 * batadv_iv_ogm_slide_own_bcast_window() - bitshift own OGM broadcast windows
882 * for the given interface
883 * @hard_iface: the interface for which the windows have to be shifted
886 batadv_iv_ogm_slide_own_bcast_window(struct batadv_hard_iface *hard_iface)
888 struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
889 struct batadv_hashtable *hash = bat_priv->orig_hash;
890 struct hlist_head *head;
891 struct batadv_orig_node *orig_node;
898 for (i = 0; i < hash->size; i++) {
899 head = &hash->table[i];
902 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
903 spin_lock_bh(&orig_node->bat_iv.ogm_cnt_lock);
904 word_index = hard_iface->if_num * BATADV_NUM_WORDS;
905 word = &orig_node->bat_iv.bcast_own[word_index];
907 batadv_bit_get_packet(bat_priv, word, 1, 0);
908 if_num = hard_iface->if_num;
909 w = &orig_node->bat_iv.bcast_own_sum[if_num];
910 *w = bitmap_weight(word, BATADV_TQ_LOCAL_WINDOW_SIZE);
911 spin_unlock_bh(&orig_node->bat_iv.ogm_cnt_lock);
917 static void batadv_iv_ogm_schedule(struct batadv_hard_iface *hard_iface)
919 struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
920 unsigned char **ogm_buff = &hard_iface->bat_iv.ogm_buff;
921 struct batadv_ogm_packet *batadv_ogm_packet;
922 struct batadv_hard_iface *primary_if, *tmp_hard_iface;
923 int *ogm_buff_len = &hard_iface->bat_iv.ogm_buff_len;
926 unsigned long send_time;
928 if (hard_iface->if_status == BATADV_IF_NOT_IN_USE ||
929 hard_iface->if_status == BATADV_IF_TO_BE_REMOVED)
932 /* the interface gets activated here to avoid race conditions between
933 * the moment of activating the interface in
934 * hardif_activate_interface() where the originator mac is set and
935 * outdated packets (especially uninitialized mac addresses) in the
938 if (hard_iface->if_status == BATADV_IF_TO_BE_ACTIVATED)
939 hard_iface->if_status = BATADV_IF_ACTIVE;
941 primary_if = batadv_primary_if_get_selected(bat_priv);
943 if (hard_iface == primary_if) {
944 /* tt changes have to be committed before the tvlv data is
945 * appended as it may alter the tt tvlv container
947 batadv_tt_local_commit_changes(bat_priv);
948 tvlv_len = batadv_tvlv_container_ogm_append(bat_priv, ogm_buff,
953 batadv_ogm_packet = (struct batadv_ogm_packet *)(*ogm_buff);
954 batadv_ogm_packet->tvlv_len = htons(tvlv_len);
956 /* change sequence number to network order */
957 seqno = (u32)atomic_read(&hard_iface->bat_iv.ogm_seqno);
958 batadv_ogm_packet->seqno = htonl(seqno);
959 atomic_inc(&hard_iface->bat_iv.ogm_seqno);
961 batadv_iv_ogm_slide_own_bcast_window(hard_iface);
963 send_time = batadv_iv_ogm_emit_send_time(bat_priv);
965 if (hard_iface != primary_if) {
966 /* OGMs from secondary interfaces are only scheduled on their
967 * respective interfaces.
969 batadv_iv_ogm_queue_add(bat_priv, *ogm_buff, *ogm_buff_len,
970 hard_iface, hard_iface, 1, send_time);
974 /* OGMs from primary interfaces are scheduled on all
978 list_for_each_entry_rcu(tmp_hard_iface, &batadv_hardif_list, list) {
979 if (tmp_hard_iface->soft_iface != hard_iface->soft_iface)
982 if (!kref_get_unless_zero(&tmp_hard_iface->refcount))
985 batadv_iv_ogm_queue_add(bat_priv, *ogm_buff,
986 *ogm_buff_len, hard_iface,
987 tmp_hard_iface, 1, send_time);
989 batadv_hardif_put(tmp_hard_iface);
995 batadv_hardif_put(primary_if);
999 * batadv_iv_ogm_orig_update() - use OGM to update corresponding data in an
1001 * @bat_priv: the bat priv with all the soft interface information
1002 * @orig_node: the orig node who originally emitted the ogm packet
1003 * @orig_ifinfo: ifinfo for the outgoing interface of the orig_node
1004 * @ethhdr: Ethernet header of the OGM
1005 * @batadv_ogm_packet: the ogm packet
1006 * @if_incoming: interface where the packet was received
1007 * @if_outgoing: interface for which the retransmission should be considered
1008 * @dup_status: the duplicate status of this ogm packet.
1011 batadv_iv_ogm_orig_update(struct batadv_priv *bat_priv,
1012 struct batadv_orig_node *orig_node,
1013 struct batadv_orig_ifinfo *orig_ifinfo,
1014 const struct ethhdr *ethhdr,
1015 const struct batadv_ogm_packet *batadv_ogm_packet,
1016 struct batadv_hard_iface *if_incoming,
1017 struct batadv_hard_iface *if_outgoing,
1018 enum batadv_dup_status dup_status)
1020 struct batadv_neigh_ifinfo *neigh_ifinfo = NULL;
1021 struct batadv_neigh_ifinfo *router_ifinfo = NULL;
1022 struct batadv_neigh_node *neigh_node = NULL;
1023 struct batadv_neigh_node *tmp_neigh_node = NULL;
1024 struct batadv_neigh_node *router = NULL;
1025 struct batadv_orig_node *orig_node_tmp;
1027 u8 sum_orig, sum_neigh;
1031 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1032 "%s(): Searching and updating originator entry of received packet\n",
1036 hlist_for_each_entry_rcu(tmp_neigh_node,
1037 &orig_node->neigh_list, list) {
1038 neigh_addr = tmp_neigh_node->addr;
1039 if (batadv_compare_eth(neigh_addr, ethhdr->h_source) &&
1040 tmp_neigh_node->if_incoming == if_incoming &&
1041 kref_get_unless_zero(&tmp_neigh_node->refcount)) {
1042 if (WARN(neigh_node, "too many matching neigh_nodes"))
1043 batadv_neigh_node_put(neigh_node);
1044 neigh_node = tmp_neigh_node;
1048 if (dup_status != BATADV_NO_DUP)
1051 /* only update the entry for this outgoing interface */
1052 neigh_ifinfo = batadv_neigh_ifinfo_get(tmp_neigh_node,
1057 spin_lock_bh(&tmp_neigh_node->ifinfo_lock);
1058 batadv_ring_buffer_set(neigh_ifinfo->bat_iv.tq_recv,
1059 &neigh_ifinfo->bat_iv.tq_index, 0);
1060 tq_avg = batadv_ring_buffer_avg(neigh_ifinfo->bat_iv.tq_recv);
1061 neigh_ifinfo->bat_iv.tq_avg = tq_avg;
1062 spin_unlock_bh(&tmp_neigh_node->ifinfo_lock);
1064 batadv_neigh_ifinfo_put(neigh_ifinfo);
1065 neigh_ifinfo = NULL;
1069 struct batadv_orig_node *orig_tmp;
1071 orig_tmp = batadv_iv_ogm_orig_get(bat_priv, ethhdr->h_source);
1075 neigh_node = batadv_iv_ogm_neigh_new(if_incoming,
1077 orig_node, orig_tmp);
1079 batadv_orig_node_put(orig_tmp);
1083 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1084 "Updating existing last-hop neighbor of originator\n");
1088 neigh_ifinfo = batadv_neigh_ifinfo_new(neigh_node, if_outgoing);
1092 neigh_node->last_seen = jiffies;
1094 spin_lock_bh(&neigh_node->ifinfo_lock);
1095 batadv_ring_buffer_set(neigh_ifinfo->bat_iv.tq_recv,
1096 &neigh_ifinfo->bat_iv.tq_index,
1097 batadv_ogm_packet->tq);
1098 tq_avg = batadv_ring_buffer_avg(neigh_ifinfo->bat_iv.tq_recv);
1099 neigh_ifinfo->bat_iv.tq_avg = tq_avg;
1100 spin_unlock_bh(&neigh_node->ifinfo_lock);
1102 if (dup_status == BATADV_NO_DUP) {
1103 orig_ifinfo->last_ttl = batadv_ogm_packet->ttl;
1104 neigh_ifinfo->last_ttl = batadv_ogm_packet->ttl;
1107 /* if this neighbor already is our next hop there is nothing
1110 router = batadv_orig_router_get(orig_node, if_outgoing);
1111 if (router == neigh_node)
1115 router_ifinfo = batadv_neigh_ifinfo_get(router, if_outgoing);
1119 /* if this neighbor does not offer a better TQ we won't
1122 if (router_ifinfo->bat_iv.tq_avg > neigh_ifinfo->bat_iv.tq_avg)
1126 /* if the TQ is the same and the link not more symmetric we
1127 * won't consider it either
1129 if (router_ifinfo &&
1130 neigh_ifinfo->bat_iv.tq_avg == router_ifinfo->bat_iv.tq_avg) {
1131 orig_node_tmp = router->orig_node;
1132 spin_lock_bh(&orig_node_tmp->bat_iv.ogm_cnt_lock);
1133 if_num = router->if_incoming->if_num;
1134 sum_orig = orig_node_tmp->bat_iv.bcast_own_sum[if_num];
1135 spin_unlock_bh(&orig_node_tmp->bat_iv.ogm_cnt_lock);
1137 orig_node_tmp = neigh_node->orig_node;
1138 spin_lock_bh(&orig_node_tmp->bat_iv.ogm_cnt_lock);
1139 if_num = neigh_node->if_incoming->if_num;
1140 sum_neigh = orig_node_tmp->bat_iv.bcast_own_sum[if_num];
1141 spin_unlock_bh(&orig_node_tmp->bat_iv.ogm_cnt_lock);
1143 if (sum_orig >= sum_neigh)
1147 batadv_update_route(bat_priv, orig_node, if_outgoing, neigh_node);
1154 batadv_neigh_node_put(neigh_node);
1156 batadv_neigh_node_put(router);
1158 batadv_neigh_ifinfo_put(neigh_ifinfo);
1160 batadv_neigh_ifinfo_put(router_ifinfo);
1164 * batadv_iv_ogm_calc_tq() - calculate tq for current received ogm packet
1165 * @orig_node: the orig node who originally emitted the ogm packet
1166 * @orig_neigh_node: the orig node struct of the neighbor who sent the packet
1167 * @batadv_ogm_packet: the ogm packet
1168 * @if_incoming: interface where the packet was received
1169 * @if_outgoing: interface for which the retransmission should be considered
1171 * Return: true if the link can be considered bidirectional, false otherwise
1173 static bool batadv_iv_ogm_calc_tq(struct batadv_orig_node *orig_node,
1174 struct batadv_orig_node *orig_neigh_node,
1175 struct batadv_ogm_packet *batadv_ogm_packet,
1176 struct batadv_hard_iface *if_incoming,
1177 struct batadv_hard_iface *if_outgoing)
1179 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
1180 struct batadv_neigh_node *neigh_node = NULL, *tmp_neigh_node;
1181 struct batadv_neigh_ifinfo *neigh_ifinfo;
1183 u8 orig_eq_count, neigh_rq_count, neigh_rq_inv, tq_own;
1184 unsigned int neigh_rq_inv_cube, neigh_rq_max_cube;
1186 unsigned int tq_asym_penalty, inv_asym_penalty;
1187 unsigned int combined_tq;
1188 unsigned int tq_iface_penalty;
1191 /* find corresponding one hop neighbor */
1193 hlist_for_each_entry_rcu(tmp_neigh_node,
1194 &orig_neigh_node->neigh_list, list) {
1195 if (!batadv_compare_eth(tmp_neigh_node->addr,
1196 orig_neigh_node->orig))
1199 if (tmp_neigh_node->if_incoming != if_incoming)
1202 if (!kref_get_unless_zero(&tmp_neigh_node->refcount))
1205 neigh_node = tmp_neigh_node;
1211 neigh_node = batadv_iv_ogm_neigh_new(if_incoming,
1212 orig_neigh_node->orig,
1219 /* if orig_node is direct neighbor update neigh_node last_seen */
1220 if (orig_node == orig_neigh_node)
1221 neigh_node->last_seen = jiffies;
1223 orig_node->last_seen = jiffies;
1225 /* find packet count of corresponding one hop neighbor */
1226 spin_lock_bh(&orig_neigh_node->bat_iv.ogm_cnt_lock);
1227 if_num = if_incoming->if_num;
1228 orig_eq_count = orig_neigh_node->bat_iv.bcast_own_sum[if_num];
1229 neigh_ifinfo = batadv_neigh_ifinfo_new(neigh_node, if_outgoing);
1231 neigh_rq_count = neigh_ifinfo->bat_iv.real_packet_count;
1232 batadv_neigh_ifinfo_put(neigh_ifinfo);
1236 spin_unlock_bh(&orig_neigh_node->bat_iv.ogm_cnt_lock);
1238 /* pay attention to not get a value bigger than 100 % */
1239 if (orig_eq_count > neigh_rq_count)
1240 total_count = neigh_rq_count;
1242 total_count = orig_eq_count;
1244 /* if we have too few packets (too less data) we set tq_own to zero
1245 * if we receive too few packets it is not considered bidirectional
1247 if (total_count < BATADV_TQ_LOCAL_BIDRECT_SEND_MINIMUM ||
1248 neigh_rq_count < BATADV_TQ_LOCAL_BIDRECT_RECV_MINIMUM)
1251 /* neigh_node->real_packet_count is never zero as we
1252 * only purge old information when getting new
1255 tq_own = (BATADV_TQ_MAX_VALUE * total_count) / neigh_rq_count;
1257 /* 1 - ((1-x) ** 3), normalized to TQ_MAX_VALUE this does
1258 * affect the nearly-symmetric links only a little, but
1259 * punishes asymmetric links more. This will give a value
1260 * between 0 and TQ_MAX_VALUE
1262 neigh_rq_inv = BATADV_TQ_LOCAL_WINDOW_SIZE - neigh_rq_count;
1263 neigh_rq_inv_cube = neigh_rq_inv * neigh_rq_inv * neigh_rq_inv;
1264 neigh_rq_max_cube = BATADV_TQ_LOCAL_WINDOW_SIZE *
1265 BATADV_TQ_LOCAL_WINDOW_SIZE *
1266 BATADV_TQ_LOCAL_WINDOW_SIZE;
1267 inv_asym_penalty = BATADV_TQ_MAX_VALUE * neigh_rq_inv_cube;
1268 inv_asym_penalty /= neigh_rq_max_cube;
1269 tq_asym_penalty = BATADV_TQ_MAX_VALUE - inv_asym_penalty;
1271 /* penalize if the OGM is forwarded on the same interface. WiFi
1272 * interfaces and other half duplex devices suffer from throughput
1273 * drops as they can't send and receive at the same time.
1275 tq_iface_penalty = BATADV_TQ_MAX_VALUE;
1276 if (if_outgoing && if_incoming == if_outgoing &&
1277 batadv_is_wifi_hardif(if_outgoing))
1278 tq_iface_penalty = batadv_hop_penalty(BATADV_TQ_MAX_VALUE,
1281 combined_tq = batadv_ogm_packet->tq *
1285 combined_tq /= BATADV_TQ_MAX_VALUE *
1286 BATADV_TQ_MAX_VALUE *
1287 BATADV_TQ_MAX_VALUE;
1288 batadv_ogm_packet->tq = combined_tq;
1290 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1291 "bidirectional: orig = %pM neigh = %pM => own_bcast = %2i, real recv = %2i, local tq: %3i, asym_penalty: %3i, iface_penalty: %3i, total tq: %3i, if_incoming = %s, if_outgoing = %s\n",
1292 orig_node->orig, orig_neigh_node->orig, total_count,
1293 neigh_rq_count, tq_own, tq_asym_penalty, tq_iface_penalty,
1294 batadv_ogm_packet->tq, if_incoming->net_dev->name,
1295 if_outgoing ? if_outgoing->net_dev->name : "DEFAULT");
1297 /* if link has the minimum required transmission quality
1298 * consider it bidirectional
1300 if (batadv_ogm_packet->tq >= BATADV_TQ_TOTAL_BIDRECT_LIMIT)
1305 batadv_neigh_node_put(neigh_node);
1310 * batadv_iv_ogm_update_seqnos() - process a batman packet for all interfaces,
1311 * adjust the sequence number and find out whether it is a duplicate
1312 * @ethhdr: ethernet header of the packet
1313 * @batadv_ogm_packet: OGM packet to be considered
1314 * @if_incoming: interface on which the OGM packet was received
1315 * @if_outgoing: interface for which the retransmission should be considered
1317 * Return: duplicate status as enum batadv_dup_status
1319 static enum batadv_dup_status
1320 batadv_iv_ogm_update_seqnos(const struct ethhdr *ethhdr,
1321 const struct batadv_ogm_packet *batadv_ogm_packet,
1322 const struct batadv_hard_iface *if_incoming,
1323 struct batadv_hard_iface *if_outgoing)
1325 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
1326 struct batadv_orig_node *orig_node;
1327 struct batadv_orig_ifinfo *orig_ifinfo = NULL;
1328 struct batadv_neigh_node *neigh_node;
1329 struct batadv_neigh_ifinfo *neigh_ifinfo;
1332 bool need_update = false;
1334 enum batadv_dup_status ret = BATADV_NO_DUP;
1335 u32 seqno = ntohl(batadv_ogm_packet->seqno);
1338 unsigned long *bitmap;
1340 orig_node = batadv_iv_ogm_orig_get(bat_priv, batadv_ogm_packet->orig);
1342 return BATADV_NO_DUP;
1344 orig_ifinfo = batadv_orig_ifinfo_new(orig_node, if_outgoing);
1345 if (WARN_ON(!orig_ifinfo)) {
1346 batadv_orig_node_put(orig_node);
1350 spin_lock_bh(&orig_node->bat_iv.ogm_cnt_lock);
1351 seq_diff = seqno - orig_ifinfo->last_real_seqno;
1353 /* signalize caller that the packet is to be dropped. */
1354 if (!hlist_empty(&orig_node->neigh_list) &&
1355 batadv_window_protected(bat_priv, seq_diff,
1356 BATADV_TQ_LOCAL_WINDOW_SIZE,
1357 &orig_ifinfo->batman_seqno_reset, NULL)) {
1358 ret = BATADV_PROTECTED;
1363 hlist_for_each_entry_rcu(neigh_node, &orig_node->neigh_list, list) {
1364 neigh_ifinfo = batadv_neigh_ifinfo_new(neigh_node,
1369 neigh_addr = neigh_node->addr;
1370 is_dup = batadv_test_bit(neigh_ifinfo->bat_iv.real_bits,
1371 orig_ifinfo->last_real_seqno,
1374 if (batadv_compare_eth(neigh_addr, ethhdr->h_source) &&
1375 neigh_node->if_incoming == if_incoming) {
1378 ret = BATADV_NEIGH_DUP;
1381 if (is_dup && ret != BATADV_NEIGH_DUP)
1382 ret = BATADV_ORIG_DUP;
1385 /* if the window moved, set the update flag. */
1386 bitmap = neigh_ifinfo->bat_iv.real_bits;
1387 need_update |= batadv_bit_get_packet(bat_priv, bitmap,
1388 seq_diff, set_mark);
1390 packet_count = bitmap_weight(bitmap,
1391 BATADV_TQ_LOCAL_WINDOW_SIZE);
1392 neigh_ifinfo->bat_iv.real_packet_count = packet_count;
1393 batadv_neigh_ifinfo_put(neigh_ifinfo);
1398 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1399 "%s updating last_seqno: old %u, new %u\n",
1400 if_outgoing ? if_outgoing->net_dev->name : "DEFAULT",
1401 orig_ifinfo->last_real_seqno, seqno);
1402 orig_ifinfo->last_real_seqno = seqno;
1406 spin_unlock_bh(&orig_node->bat_iv.ogm_cnt_lock);
1407 batadv_orig_node_put(orig_node);
1408 batadv_orig_ifinfo_put(orig_ifinfo);
1413 * batadv_iv_ogm_process_per_outif() - process a batman iv OGM for an outgoing
1415 * @skb: the skb containing the OGM
1416 * @ogm_offset: offset from skb->data to start of ogm header
1417 * @orig_node: the (cached) orig node for the originator of this OGM
1418 * @if_incoming: the interface where this packet was received
1419 * @if_outgoing: the interface for which the packet should be considered
1422 batadv_iv_ogm_process_per_outif(const struct sk_buff *skb, int ogm_offset,
1423 struct batadv_orig_node *orig_node,
1424 struct batadv_hard_iface *if_incoming,
1425 struct batadv_hard_iface *if_outgoing)
1427 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
1428 struct batadv_hardif_neigh_node *hardif_neigh = NULL;
1429 struct batadv_neigh_node *router = NULL;
1430 struct batadv_neigh_node *router_router = NULL;
1431 struct batadv_orig_node *orig_neigh_node;
1432 struct batadv_orig_ifinfo *orig_ifinfo;
1433 struct batadv_neigh_node *orig_neigh_router = NULL;
1434 struct batadv_neigh_ifinfo *router_ifinfo = NULL;
1435 struct batadv_ogm_packet *ogm_packet;
1436 enum batadv_dup_status dup_status;
1437 bool is_from_best_next_hop = false;
1438 bool is_single_hop_neigh = false;
1439 bool sameseq, similar_ttl;
1440 struct sk_buff *skb_priv;
1441 struct ethhdr *ethhdr;
1445 /* create a private copy of the skb, as some functions change tq value
1448 skb_priv = skb_copy(skb, GFP_ATOMIC);
1452 ethhdr = eth_hdr(skb_priv);
1453 ogm_packet = (struct batadv_ogm_packet *)(skb_priv->data + ogm_offset);
1455 dup_status = batadv_iv_ogm_update_seqnos(ethhdr, ogm_packet,
1456 if_incoming, if_outgoing);
1457 if (batadv_compare_eth(ethhdr->h_source, ogm_packet->orig))
1458 is_single_hop_neigh = true;
1460 if (dup_status == BATADV_PROTECTED) {
1461 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1462 "Drop packet: packet within seqno protection time (sender: %pM)\n",
1467 if (ogm_packet->tq == 0) {
1468 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1469 "Drop packet: originator packet with tq equal 0\n");
1473 if (is_single_hop_neigh) {
1474 hardif_neigh = batadv_hardif_neigh_get(if_incoming,
1477 hardif_neigh->last_seen = jiffies;
1480 router = batadv_orig_router_get(orig_node, if_outgoing);
1482 router_router = batadv_orig_router_get(router->orig_node,
1484 router_ifinfo = batadv_neigh_ifinfo_get(router, if_outgoing);
1487 if ((router_ifinfo && router_ifinfo->bat_iv.tq_avg != 0) &&
1488 (batadv_compare_eth(router->addr, ethhdr->h_source)))
1489 is_from_best_next_hop = true;
1491 prev_sender = ogm_packet->prev_sender;
1492 /* avoid temporary routing loops */
1493 if (router && router_router &&
1494 (batadv_compare_eth(router->addr, prev_sender)) &&
1495 !(batadv_compare_eth(ogm_packet->orig, prev_sender)) &&
1496 (batadv_compare_eth(router->addr, router_router->addr))) {
1497 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1498 "Drop packet: ignoring all rebroadcast packets that may make me loop (sender: %pM)\n",
1503 if (if_outgoing == BATADV_IF_DEFAULT)
1504 batadv_tvlv_ogm_receive(bat_priv, ogm_packet, orig_node);
1506 /* if sender is a direct neighbor the sender mac equals
1509 if (is_single_hop_neigh)
1510 orig_neigh_node = orig_node;
1512 orig_neigh_node = batadv_iv_ogm_orig_get(bat_priv,
1515 if (!orig_neigh_node)
1518 /* Update nc_nodes of the originator */
1519 batadv_nc_update_nc_node(bat_priv, orig_node, orig_neigh_node,
1520 ogm_packet, is_single_hop_neigh);
1522 orig_neigh_router = batadv_orig_router_get(orig_neigh_node,
1525 /* drop packet if sender is not a direct neighbor and if we
1526 * don't route towards it
1528 if (!is_single_hop_neigh && !orig_neigh_router) {
1529 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1530 "Drop packet: OGM via unknown neighbor!\n");
1534 is_bidirect = batadv_iv_ogm_calc_tq(orig_node, orig_neigh_node,
1535 ogm_packet, if_incoming,
1538 /* update ranking if it is not a duplicate or has the same
1539 * seqno and similar ttl as the non-duplicate
1541 orig_ifinfo = batadv_orig_ifinfo_new(orig_node, if_outgoing);
1545 sameseq = orig_ifinfo->last_real_seqno == ntohl(ogm_packet->seqno);
1546 similar_ttl = (orig_ifinfo->last_ttl - 3) <= ogm_packet->ttl;
1548 if (is_bidirect && (dup_status == BATADV_NO_DUP ||
1549 (sameseq && similar_ttl))) {
1550 batadv_iv_ogm_orig_update(bat_priv, orig_node,
1551 orig_ifinfo, ethhdr,
1552 ogm_packet, if_incoming,
1553 if_outgoing, dup_status);
1555 batadv_orig_ifinfo_put(orig_ifinfo);
1557 /* only forward for specific interface, not for the default one. */
1558 if (if_outgoing == BATADV_IF_DEFAULT)
1561 /* is single hop (direct) neighbor */
1562 if (is_single_hop_neigh) {
1563 /* OGMs from secondary interfaces should only scheduled once
1564 * per interface where it has been received, not multiple times
1566 if (ogm_packet->ttl <= 2 &&
1567 if_incoming != if_outgoing) {
1568 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1569 "Drop packet: OGM from secondary interface and wrong outgoing interface\n");
1572 /* mark direct link on incoming interface */
1573 batadv_iv_ogm_forward(orig_node, ethhdr, ogm_packet,
1574 is_single_hop_neigh,
1575 is_from_best_next_hop, if_incoming,
1578 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1579 "Forwarding packet: rebroadcast neighbor packet with direct link flag\n");
1583 /* multihop originator */
1585 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1586 "Drop packet: not received via bidirectional link\n");
1590 if (dup_status == BATADV_NEIGH_DUP) {
1591 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1592 "Drop packet: duplicate packet received\n");
1596 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1597 "Forwarding packet: rebroadcast originator packet\n");
1598 batadv_iv_ogm_forward(orig_node, ethhdr, ogm_packet,
1599 is_single_hop_neigh, is_from_best_next_hop,
1600 if_incoming, if_outgoing);
1603 if (orig_neigh_node && !is_single_hop_neigh)
1604 batadv_orig_node_put(orig_neigh_node);
1607 batadv_neigh_ifinfo_put(router_ifinfo);
1609 batadv_neigh_node_put(router);
1611 batadv_neigh_node_put(router_router);
1612 if (orig_neigh_router)
1613 batadv_neigh_node_put(orig_neigh_router);
1615 batadv_hardif_neigh_put(hardif_neigh);
1617 consume_skb(skb_priv);
1621 * batadv_iv_ogm_process() - process an incoming batman iv OGM
1622 * @skb: the skb containing the OGM
1623 * @ogm_offset: offset to the OGM which should be processed (for aggregates)
1624 * @if_incoming: the interface where this packet was receved
1626 static void batadv_iv_ogm_process(const struct sk_buff *skb, int ogm_offset,
1627 struct batadv_hard_iface *if_incoming)
1629 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
1630 struct batadv_orig_node *orig_neigh_node, *orig_node;
1631 struct batadv_hard_iface *hard_iface;
1632 struct batadv_ogm_packet *ogm_packet;
1633 u32 if_incoming_seqno;
1634 bool has_directlink_flag;
1635 struct ethhdr *ethhdr;
1636 bool is_my_oldorig = false;
1637 bool is_my_addr = false;
1638 bool is_my_orig = false;
1640 ogm_packet = (struct batadv_ogm_packet *)(skb->data + ogm_offset);
1641 ethhdr = eth_hdr(skb);
1643 /* Silently drop when the batman packet is actually not a
1646 * This might happen if a packet is padded (e.g. Ethernet has a
1647 * minimum frame length of 64 byte) and the aggregation interprets
1648 * it as an additional length.
1650 * TODO: A more sane solution would be to have a bit in the
1651 * batadv_ogm_packet to detect whether the packet is the last
1652 * packet in an aggregation. Here we expect that the padding
1653 * is always zero (or not 0x01)
1655 if (ogm_packet->packet_type != BATADV_IV_OGM)
1658 /* could be changed by schedule_own_packet() */
1659 if_incoming_seqno = atomic_read(&if_incoming->bat_iv.ogm_seqno);
1661 if (ogm_packet->flags & BATADV_DIRECTLINK)
1662 has_directlink_flag = true;
1664 has_directlink_flag = false;
1666 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1667 "Received BATMAN packet via NB: %pM, IF: %s [%pM] (from OG: %pM, via prev OG: %pM, seqno %u, tq %d, TTL %d, V %d, IDF %d)\n",
1668 ethhdr->h_source, if_incoming->net_dev->name,
1669 if_incoming->net_dev->dev_addr, ogm_packet->orig,
1670 ogm_packet->prev_sender, ntohl(ogm_packet->seqno),
1671 ogm_packet->tq, ogm_packet->ttl,
1672 ogm_packet->version, has_directlink_flag);
1675 list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) {
1676 if (hard_iface->if_status != BATADV_IF_ACTIVE)
1679 if (hard_iface->soft_iface != if_incoming->soft_iface)
1682 if (batadv_compare_eth(ethhdr->h_source,
1683 hard_iface->net_dev->dev_addr))
1686 if (batadv_compare_eth(ogm_packet->orig,
1687 hard_iface->net_dev->dev_addr))
1690 if (batadv_compare_eth(ogm_packet->prev_sender,
1691 hard_iface->net_dev->dev_addr))
1692 is_my_oldorig = true;
1697 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1698 "Drop packet: received my own broadcast (sender: %pM)\n",
1704 unsigned long *word;
1710 orig_neigh_node = batadv_iv_ogm_orig_get(bat_priv,
1712 if (!orig_neigh_node)
1715 /* neighbor has to indicate direct link and it has to
1716 * come via the corresponding interface
1717 * save packet seqno for bidirectional check
1719 if (has_directlink_flag &&
1720 batadv_compare_eth(if_incoming->net_dev->dev_addr,
1721 ogm_packet->orig)) {
1722 if_num = if_incoming->if_num;
1723 offset = if_num * BATADV_NUM_WORDS;
1725 spin_lock_bh(&orig_neigh_node->bat_iv.ogm_cnt_lock);
1726 word = &orig_neigh_node->bat_iv.bcast_own[offset];
1727 bit_pos = if_incoming_seqno - 2;
1728 bit_pos -= ntohl(ogm_packet->seqno);
1729 batadv_set_bit(word, bit_pos);
1730 weight = &orig_neigh_node->bat_iv.bcast_own_sum[if_num];
1731 *weight = bitmap_weight(word,
1732 BATADV_TQ_LOCAL_WINDOW_SIZE);
1733 spin_unlock_bh(&orig_neigh_node->bat_iv.ogm_cnt_lock);
1736 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1737 "Drop packet: originator packet from myself (via neighbor)\n");
1738 batadv_orig_node_put(orig_neigh_node);
1742 if (is_my_oldorig) {
1743 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1744 "Drop packet: ignoring all rebroadcast echos (sender: %pM)\n",
1749 if (ogm_packet->flags & BATADV_NOT_BEST_NEXT_HOP) {
1750 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
1751 "Drop packet: ignoring all packets not forwarded from the best next hop (sender: %pM)\n",
1756 orig_node = batadv_iv_ogm_orig_get(bat_priv, ogm_packet->orig);
1760 batadv_iv_ogm_process_per_outif(skb, ogm_offset, orig_node,
1761 if_incoming, BATADV_IF_DEFAULT);
1764 list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) {
1765 if (hard_iface->if_status != BATADV_IF_ACTIVE)
1768 if (hard_iface->soft_iface != bat_priv->soft_iface)
1771 if (!kref_get_unless_zero(&hard_iface->refcount))
1774 batadv_iv_ogm_process_per_outif(skb, ogm_offset, orig_node,
1775 if_incoming, hard_iface);
1777 batadv_hardif_put(hard_iface);
1781 batadv_orig_node_put(orig_node);
1784 static void batadv_iv_send_outstanding_bat_ogm_packet(struct work_struct *work)
1786 struct delayed_work *delayed_work;
1787 struct batadv_forw_packet *forw_packet;
1788 struct batadv_priv *bat_priv;
1789 bool dropped = false;
1791 delayed_work = to_delayed_work(work);
1792 forw_packet = container_of(delayed_work, struct batadv_forw_packet,
1794 bat_priv = netdev_priv(forw_packet->if_incoming->soft_iface);
1796 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_DEACTIVATING) {
1801 batadv_iv_ogm_emit(forw_packet);
1803 /* we have to have at least one packet in the queue to determine the
1804 * queues wake up time unless we are shutting down.
1806 * only re-schedule if this is the "original" copy, e.g. the OGM of the
1807 * primary interface should only be rescheduled once per period, but
1808 * this function will be called for the forw_packet instances of the
1809 * other secondary interfaces as well.
1811 if (forw_packet->own &&
1812 forw_packet->if_incoming == forw_packet->if_outgoing)
1813 batadv_iv_ogm_schedule(forw_packet->if_incoming);
1816 /* do we get something for free()? */
1817 if (batadv_forw_packet_steal(forw_packet,
1818 &bat_priv->forw_bat_list_lock))
1819 batadv_forw_packet_free(forw_packet, dropped);
1822 static int batadv_iv_ogm_receive(struct sk_buff *skb,
1823 struct batadv_hard_iface *if_incoming)
1825 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
1826 struct batadv_ogm_packet *ogm_packet;
1830 int ret = NET_RX_DROP;
1832 res = batadv_check_management_packet(skb, if_incoming, BATADV_OGM_HLEN);
1836 /* did we receive a B.A.T.M.A.N. IV OGM packet on an interface
1837 * that does not have B.A.T.M.A.N. IV enabled ?
1839 if (bat_priv->algo_ops->iface.enable != batadv_iv_ogm_iface_enable)
1842 batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_RX);
1843 batadv_add_counter(bat_priv, BATADV_CNT_MGMT_RX_BYTES,
1844 skb->len + ETH_HLEN);
1847 ogm_packet = (struct batadv_ogm_packet *)skb->data;
1849 /* unpack the aggregated packets and process them one by one */
1850 while (batadv_iv_ogm_aggr_packet(ogm_offset, skb_headlen(skb),
1851 ogm_packet->tvlv_len)) {
1852 batadv_iv_ogm_process(skb, ogm_offset, if_incoming);
1854 ogm_offset += BATADV_OGM_HLEN;
1855 ogm_offset += ntohs(ogm_packet->tvlv_len);
1857 packet_pos = skb->data + ogm_offset;
1858 ogm_packet = (struct batadv_ogm_packet *)packet_pos;
1861 ret = NET_RX_SUCCESS;
1864 if (ret == NET_RX_SUCCESS)
1872 #ifdef CONFIG_BATMAN_ADV_DEBUGFS
1874 * batadv_iv_ogm_orig_print_neigh() - print neighbors for the originator table
1875 * @orig_node: the orig_node for which the neighbors are printed
1876 * @if_outgoing: outgoing interface for these entries
1877 * @seq: debugfs table seq_file struct
1879 * Must be called while holding an rcu lock.
1882 batadv_iv_ogm_orig_print_neigh(struct batadv_orig_node *orig_node,
1883 struct batadv_hard_iface *if_outgoing,
1884 struct seq_file *seq)
1886 struct batadv_neigh_node *neigh_node;
1887 struct batadv_neigh_ifinfo *n_ifinfo;
1889 hlist_for_each_entry_rcu(neigh_node, &orig_node->neigh_list, list) {
1890 n_ifinfo = batadv_neigh_ifinfo_get(neigh_node, if_outgoing);
1894 seq_printf(seq, " %pM (%3i)",
1896 n_ifinfo->bat_iv.tq_avg);
1898 batadv_neigh_ifinfo_put(n_ifinfo);
1903 * batadv_iv_ogm_orig_print() - print the originator table
1904 * @bat_priv: the bat priv with all the soft interface information
1905 * @seq: debugfs table seq_file struct
1906 * @if_outgoing: the outgoing interface for which this should be printed
1908 static void batadv_iv_ogm_orig_print(struct batadv_priv *bat_priv,
1909 struct seq_file *seq,
1910 struct batadv_hard_iface *if_outgoing)
1912 struct batadv_neigh_node *neigh_node;
1913 struct batadv_hashtable *hash = bat_priv->orig_hash;
1914 int last_seen_msecs, last_seen_secs;
1915 struct batadv_orig_node *orig_node;
1916 struct batadv_neigh_ifinfo *n_ifinfo;
1917 unsigned long last_seen_jiffies;
1918 struct hlist_head *head;
1919 int batman_count = 0;
1923 " Originator last-seen (#/255) Nexthop [outgoingIF]: Potential nexthops ...\n");
1925 for (i = 0; i < hash->size; i++) {
1926 head = &hash->table[i];
1929 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
1930 neigh_node = batadv_orig_router_get(orig_node,
1935 n_ifinfo = batadv_neigh_ifinfo_get(neigh_node,
1940 if (n_ifinfo->bat_iv.tq_avg == 0)
1943 last_seen_jiffies = jiffies - orig_node->last_seen;
1944 last_seen_msecs = jiffies_to_msecs(last_seen_jiffies);
1945 last_seen_secs = last_seen_msecs / 1000;
1946 last_seen_msecs = last_seen_msecs % 1000;
1948 seq_printf(seq, "%pM %4i.%03is (%3i) %pM [%10s]:",
1949 orig_node->orig, last_seen_secs,
1950 last_seen_msecs, n_ifinfo->bat_iv.tq_avg,
1952 neigh_node->if_incoming->net_dev->name);
1954 batadv_iv_ogm_orig_print_neigh(orig_node, if_outgoing,
1956 seq_putc(seq, '\n');
1960 batadv_neigh_node_put(neigh_node);
1962 batadv_neigh_ifinfo_put(n_ifinfo);
1967 if (batman_count == 0)
1968 seq_puts(seq, "No batman nodes in range ...\n");
1973 * batadv_iv_ogm_neigh_get_tq_avg() - Get the TQ average for a neighbour on a
1974 * given outgoing interface.
1975 * @neigh_node: Neighbour of interest
1976 * @if_outgoing: Outgoing interface of interest
1977 * @tq_avg: Pointer of where to store the TQ average
1979 * Return: False if no average TQ available, otherwise true.
1982 batadv_iv_ogm_neigh_get_tq_avg(struct batadv_neigh_node *neigh_node,
1983 struct batadv_hard_iface *if_outgoing,
1986 struct batadv_neigh_ifinfo *n_ifinfo;
1988 n_ifinfo = batadv_neigh_ifinfo_get(neigh_node, if_outgoing);
1992 *tq_avg = n_ifinfo->bat_iv.tq_avg;
1993 batadv_neigh_ifinfo_put(n_ifinfo);
1999 * batadv_iv_ogm_orig_dump_subentry() - Dump an originator subentry into a
2001 * @msg: Netlink message to dump into
2002 * @portid: Port making netlink request
2003 * @seq: Sequence number of netlink message
2004 * @bat_priv: The bat priv with all the soft interface information
2005 * @if_outgoing: Limit dump to entries with this outgoing interface
2006 * @orig_node: Originator to dump
2007 * @neigh_node: Single hops neighbour
2008 * @best: Is the best originator
2010 * Return: Error code, or 0 on success
2013 batadv_iv_ogm_orig_dump_subentry(struct sk_buff *msg, u32 portid, u32 seq,
2014 struct batadv_priv *bat_priv,
2015 struct batadv_hard_iface *if_outgoing,
2016 struct batadv_orig_node *orig_node,
2017 struct batadv_neigh_node *neigh_node,
2022 unsigned int last_seen_msecs;
2024 last_seen_msecs = jiffies_to_msecs(jiffies - orig_node->last_seen);
2026 if (!batadv_iv_ogm_neigh_get_tq_avg(neigh_node, if_outgoing, &tq_avg))
2029 if (if_outgoing != BATADV_IF_DEFAULT &&
2030 if_outgoing != neigh_node->if_incoming)
2033 hdr = genlmsg_put(msg, portid, seq, &batadv_netlink_family,
2034 NLM_F_MULTI, BATADV_CMD_GET_ORIGINATORS);
2038 if (nla_put(msg, BATADV_ATTR_ORIG_ADDRESS, ETH_ALEN,
2040 nla_put(msg, BATADV_ATTR_NEIGH_ADDRESS, ETH_ALEN,
2041 neigh_node->addr) ||
2042 nla_put_u32(msg, BATADV_ATTR_HARD_IFINDEX,
2043 neigh_node->if_incoming->net_dev->ifindex) ||
2044 nla_put_u8(msg, BATADV_ATTR_TQ, tq_avg) ||
2045 nla_put_u32(msg, BATADV_ATTR_LAST_SEEN_MSECS,
2047 goto nla_put_failure;
2049 if (best && nla_put_flag(msg, BATADV_ATTR_FLAG_BEST))
2050 goto nla_put_failure;
2052 genlmsg_end(msg, hdr);
2056 genlmsg_cancel(msg, hdr);
2061 * batadv_iv_ogm_orig_dump_entry() - Dump an originator entry into a message
2062 * @msg: Netlink message to dump into
2063 * @portid: Port making netlink request
2064 * @seq: Sequence number of netlink message
2065 * @bat_priv: The bat priv with all the soft interface information
2066 * @if_outgoing: Limit dump to entries with this outgoing interface
2067 * @orig_node: Originator to dump
2068 * @sub_s: Number of sub entries to skip
2070 * This function assumes the caller holds rcu_read_lock().
2072 * Return: Error code, or 0 on success
2075 batadv_iv_ogm_orig_dump_entry(struct sk_buff *msg, u32 portid, u32 seq,
2076 struct batadv_priv *bat_priv,
2077 struct batadv_hard_iface *if_outgoing,
2078 struct batadv_orig_node *orig_node, int *sub_s)
2080 struct batadv_neigh_node *neigh_node_best;
2081 struct batadv_neigh_node *neigh_node;
2086 neigh_node_best = batadv_orig_router_get(orig_node, if_outgoing);
2087 if (!neigh_node_best)
2090 if (!batadv_iv_ogm_neigh_get_tq_avg(neigh_node_best, if_outgoing,
2094 if (tq_avg_best == 0)
2097 hlist_for_each_entry_rcu(neigh_node, &orig_node->neigh_list, list) {
2101 best = (neigh_node == neigh_node_best);
2103 if (batadv_iv_ogm_orig_dump_subentry(msg, portid, seq,
2104 bat_priv, if_outgoing,
2105 orig_node, neigh_node,
2107 batadv_neigh_node_put(neigh_node_best);
2115 if (neigh_node_best)
2116 batadv_neigh_node_put(neigh_node_best);
2123 * batadv_iv_ogm_orig_dump_bucket() - Dump an originator bucket into a
2125 * @msg: Netlink message to dump into
2126 * @portid: Port making netlink request
2127 * @seq: Sequence number of netlink message
2128 * @bat_priv: The bat priv with all the soft interface information
2129 * @if_outgoing: Limit dump to entries with this outgoing interface
2130 * @head: Bucket to be dumped
2131 * @idx_s: Number of entries to be skipped
2132 * @sub: Number of sub entries to be skipped
2134 * Return: Error code, or 0 on success
2137 batadv_iv_ogm_orig_dump_bucket(struct sk_buff *msg, u32 portid, u32 seq,
2138 struct batadv_priv *bat_priv,
2139 struct batadv_hard_iface *if_outgoing,
2140 struct hlist_head *head, int *idx_s, int *sub)
2142 struct batadv_orig_node *orig_node;
2146 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
2150 if (batadv_iv_ogm_orig_dump_entry(msg, portid, seq, bat_priv,
2151 if_outgoing, orig_node,
2166 * batadv_iv_ogm_orig_dump() - Dump the originators into a message
2167 * @msg: Netlink message to dump into
2168 * @cb: Control block containing additional options
2169 * @bat_priv: The bat priv with all the soft interface information
2170 * @if_outgoing: Limit dump to entries with this outgoing interface
2173 batadv_iv_ogm_orig_dump(struct sk_buff *msg, struct netlink_callback *cb,
2174 struct batadv_priv *bat_priv,
2175 struct batadv_hard_iface *if_outgoing)
2177 struct batadv_hashtable *hash = bat_priv->orig_hash;
2178 struct hlist_head *head;
2179 int bucket = cb->args[0];
2180 int idx = cb->args[1];
2181 int sub = cb->args[2];
2182 int portid = NETLINK_CB(cb->skb).portid;
2184 while (bucket < hash->size) {
2185 head = &hash->table[bucket];
2187 if (batadv_iv_ogm_orig_dump_bucket(msg, portid,
2189 bat_priv, if_outgoing, head,
2196 cb->args[0] = bucket;
2201 #ifdef CONFIG_BATMAN_ADV_DEBUGFS
2203 * batadv_iv_hardif_neigh_print() - print a single hop neighbour node
2204 * @seq: neighbour table seq_file struct
2205 * @hardif_neigh: hardif neighbour information
2208 batadv_iv_hardif_neigh_print(struct seq_file *seq,
2209 struct batadv_hardif_neigh_node *hardif_neigh)
2211 int last_secs, last_msecs;
2213 last_secs = jiffies_to_msecs(jiffies - hardif_neigh->last_seen) / 1000;
2214 last_msecs = jiffies_to_msecs(jiffies - hardif_neigh->last_seen) % 1000;
2216 seq_printf(seq, " %10s %pM %4i.%03is\n",
2217 hardif_neigh->if_incoming->net_dev->name,
2218 hardif_neigh->addr, last_secs, last_msecs);
2222 * batadv_iv_ogm_neigh_print() - print the single hop neighbour list
2223 * @bat_priv: the bat priv with all the soft interface information
2224 * @seq: neighbour table seq_file struct
2226 static void batadv_iv_neigh_print(struct batadv_priv *bat_priv,
2227 struct seq_file *seq)
2229 struct net_device *net_dev = (struct net_device *)seq->private;
2230 struct batadv_hardif_neigh_node *hardif_neigh;
2231 struct batadv_hard_iface *hard_iface;
2232 int batman_count = 0;
2234 seq_puts(seq, " IF Neighbor last-seen\n");
2237 list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) {
2238 if (hard_iface->soft_iface != net_dev)
2241 hlist_for_each_entry_rcu(hardif_neigh,
2242 &hard_iface->neigh_list, list) {
2243 batadv_iv_hardif_neigh_print(seq, hardif_neigh);
2249 if (batman_count == 0)
2250 seq_puts(seq, "No batman nodes in range ...\n");
2255 * batadv_iv_ogm_neigh_diff() - calculate tq difference of two neighbors
2256 * @neigh1: the first neighbor object of the comparison
2257 * @if_outgoing1: outgoing interface for the first neighbor
2258 * @neigh2: the second neighbor object of the comparison
2259 * @if_outgoing2: outgoing interface for the second neighbor
2260 * @diff: pointer to integer receiving the calculated difference
2262 * The content of *@diff is only valid when this function returns true.
2263 * It is less, equal to or greater than 0 if the metric via neigh1 is lower,
2264 * the same as or higher than the metric via neigh2
2266 * Return: true when the difference could be calculated, false otherwise
2268 static bool batadv_iv_ogm_neigh_diff(struct batadv_neigh_node *neigh1,
2269 struct batadv_hard_iface *if_outgoing1,
2270 struct batadv_neigh_node *neigh2,
2271 struct batadv_hard_iface *if_outgoing2,
2274 struct batadv_neigh_ifinfo *neigh1_ifinfo, *neigh2_ifinfo;
2278 neigh1_ifinfo = batadv_neigh_ifinfo_get(neigh1, if_outgoing1);
2279 neigh2_ifinfo = batadv_neigh_ifinfo_get(neigh2, if_outgoing2);
2281 if (!neigh1_ifinfo || !neigh2_ifinfo) {
2286 tq1 = neigh1_ifinfo->bat_iv.tq_avg;
2287 tq2 = neigh2_ifinfo->bat_iv.tq_avg;
2288 *diff = (int)tq1 - (int)tq2;
2292 batadv_neigh_ifinfo_put(neigh1_ifinfo);
2294 batadv_neigh_ifinfo_put(neigh2_ifinfo);
2300 * batadv_iv_ogm_neigh_dump_neigh() - Dump a neighbour into a netlink message
2301 * @msg: Netlink message to dump into
2302 * @portid: Port making netlink request
2303 * @seq: Sequence number of netlink message
2304 * @hardif_neigh: Neighbour to be dumped
2306 * Return: Error code, or 0 on success
2309 batadv_iv_ogm_neigh_dump_neigh(struct sk_buff *msg, u32 portid, u32 seq,
2310 struct batadv_hardif_neigh_node *hardif_neigh)
2313 unsigned int last_seen_msecs;
2315 last_seen_msecs = jiffies_to_msecs(jiffies - hardif_neigh->last_seen);
2317 hdr = genlmsg_put(msg, portid, seq, &batadv_netlink_family,
2318 NLM_F_MULTI, BATADV_CMD_GET_NEIGHBORS);
2322 if (nla_put(msg, BATADV_ATTR_NEIGH_ADDRESS, ETH_ALEN,
2323 hardif_neigh->addr) ||
2324 nla_put_u32(msg, BATADV_ATTR_HARD_IFINDEX,
2325 hardif_neigh->if_incoming->net_dev->ifindex) ||
2326 nla_put_u32(msg, BATADV_ATTR_LAST_SEEN_MSECS,
2328 goto nla_put_failure;
2330 genlmsg_end(msg, hdr);
2334 genlmsg_cancel(msg, hdr);
2339 * batadv_iv_ogm_neigh_dump_hardif() - Dump the neighbours of a hard interface
2341 * @msg: Netlink message to dump into
2342 * @portid: Port making netlink request
2343 * @seq: Sequence number of netlink message
2344 * @bat_priv: The bat priv with all the soft interface information
2345 * @hard_iface: Hard interface to dump the neighbours for
2346 * @idx_s: Number of entries to skip
2348 * This function assumes the caller holds rcu_read_lock().
2350 * Return: Error code, or 0 on success
2353 batadv_iv_ogm_neigh_dump_hardif(struct sk_buff *msg, u32 portid, u32 seq,
2354 struct batadv_priv *bat_priv,
2355 struct batadv_hard_iface *hard_iface,
2358 struct batadv_hardif_neigh_node *hardif_neigh;
2361 hlist_for_each_entry_rcu(hardif_neigh,
2362 &hard_iface->neigh_list, list) {
2366 if (batadv_iv_ogm_neigh_dump_neigh(msg, portid, seq,
2378 * batadv_iv_ogm_neigh_dump() - Dump the neighbours into a message
2379 * @msg: Netlink message to dump into
2380 * @cb: Control block containing additional options
2381 * @bat_priv: The bat priv with all the soft interface information
2382 * @single_hardif: Limit dump to this hard interfaace
2385 batadv_iv_ogm_neigh_dump(struct sk_buff *msg, struct netlink_callback *cb,
2386 struct batadv_priv *bat_priv,
2387 struct batadv_hard_iface *single_hardif)
2389 struct batadv_hard_iface *hard_iface;
2391 int i_hardif_s = cb->args[0];
2392 int idx = cb->args[1];
2393 int portid = NETLINK_CB(cb->skb).portid;
2396 if (single_hardif) {
2397 if (i_hardif_s == 0) {
2398 if (batadv_iv_ogm_neigh_dump_hardif(msg, portid,
2406 list_for_each_entry_rcu(hard_iface, &batadv_hardif_list,
2408 if (hard_iface->soft_iface != bat_priv->soft_iface)
2411 if (i_hardif++ < i_hardif_s)
2414 if (batadv_iv_ogm_neigh_dump_hardif(msg, portid,
2417 hard_iface, &idx)) {
2425 cb->args[0] = i_hardif;
2430 * batadv_iv_ogm_neigh_cmp() - compare the metrics of two neighbors
2431 * @neigh1: the first neighbor object of the comparison
2432 * @if_outgoing1: outgoing interface for the first neighbor
2433 * @neigh2: the second neighbor object of the comparison
2434 * @if_outgoing2: outgoing interface for the second neighbor
2436 * Return: a value less, equal to or greater than 0 if the metric via neigh1 is
2437 * lower, the same as or higher than the metric via neigh2
2439 static int batadv_iv_ogm_neigh_cmp(struct batadv_neigh_node *neigh1,
2440 struct batadv_hard_iface *if_outgoing1,
2441 struct batadv_neigh_node *neigh2,
2442 struct batadv_hard_iface *if_outgoing2)
2447 ret = batadv_iv_ogm_neigh_diff(neigh1, if_outgoing1, neigh2,
2448 if_outgoing2, &diff);
2456 * batadv_iv_ogm_neigh_is_sob() - check if neigh1 is similarly good or better
2457 * than neigh2 from the metric prospective
2458 * @neigh1: the first neighbor object of the comparison
2459 * @if_outgoing1: outgoing interface for the first neighbor
2460 * @neigh2: the second neighbor object of the comparison
2461 * @if_outgoing2: outgoing interface for the second neighbor
2463 * Return: true if the metric via neigh1 is equally good or better than
2464 * the metric via neigh2, false otherwise.
2467 batadv_iv_ogm_neigh_is_sob(struct batadv_neigh_node *neigh1,
2468 struct batadv_hard_iface *if_outgoing1,
2469 struct batadv_neigh_node *neigh2,
2470 struct batadv_hard_iface *if_outgoing2)
2475 ret = batadv_iv_ogm_neigh_diff(neigh1, if_outgoing1, neigh2,
2476 if_outgoing2, &diff);
2480 ret = diff > -BATADV_TQ_SIMILARITY_THRESHOLD;
2484 static void batadv_iv_iface_activate(struct batadv_hard_iface *hard_iface)
2486 /* begin scheduling originator messages on that interface */
2487 batadv_iv_ogm_schedule(hard_iface);
2491 * batadv_iv_init_sel_class() - initialize GW selection class
2492 * @bat_priv: the bat priv with all the soft interface information
2494 static void batadv_iv_init_sel_class(struct batadv_priv *bat_priv)
2496 /* set default TQ difference threshold to 20 */
2497 atomic_set(&bat_priv->gw.sel_class, 20);
2500 static struct batadv_gw_node *
2501 batadv_iv_gw_get_best_gw_node(struct batadv_priv *bat_priv)
2503 struct batadv_neigh_node *router;
2504 struct batadv_neigh_ifinfo *router_ifinfo;
2505 struct batadv_gw_node *gw_node, *curr_gw = NULL;
2506 u64 max_gw_factor = 0;
2507 u64 tmp_gw_factor = 0;
2510 struct batadv_orig_node *orig_node;
2513 hlist_for_each_entry_rcu(gw_node, &bat_priv->gw.gateway_list, list) {
2514 orig_node = gw_node->orig_node;
2515 router = batadv_orig_router_get(orig_node, BATADV_IF_DEFAULT);
2519 router_ifinfo = batadv_neigh_ifinfo_get(router,
2524 if (!kref_get_unless_zero(&gw_node->refcount))
2527 tq_avg = router_ifinfo->bat_iv.tq_avg;
2529 switch (atomic_read(&bat_priv->gw.sel_class)) {
2530 case 1: /* fast connection */
2531 tmp_gw_factor = tq_avg * tq_avg;
2532 tmp_gw_factor *= gw_node->bandwidth_down;
2533 tmp_gw_factor *= 100 * 100;
2534 tmp_gw_factor >>= 18;
2536 if (tmp_gw_factor > max_gw_factor ||
2537 (tmp_gw_factor == max_gw_factor &&
2540 batadv_gw_node_put(curr_gw);
2542 kref_get(&curr_gw->refcount);
2546 default: /* 2: stable connection (use best statistic)
2547 * 3: fast-switch (use best statistic but change as
2548 * soon as a better gateway appears)
2549 * XX: late-switch (use best statistic but change as
2550 * soon as a better gateway appears which has
2551 * $routing_class more tq points)
2553 if (tq_avg > max_tq) {
2555 batadv_gw_node_put(curr_gw);
2557 kref_get(&curr_gw->refcount);
2562 if (tq_avg > max_tq)
2565 if (tmp_gw_factor > max_gw_factor)
2566 max_gw_factor = tmp_gw_factor;
2568 batadv_gw_node_put(gw_node);
2571 batadv_neigh_node_put(router);
2573 batadv_neigh_ifinfo_put(router_ifinfo);
2580 static bool batadv_iv_gw_is_eligible(struct batadv_priv *bat_priv,
2581 struct batadv_orig_node *curr_gw_orig,
2582 struct batadv_orig_node *orig_node)
2584 struct batadv_neigh_ifinfo *router_orig_ifinfo = NULL;
2585 struct batadv_neigh_ifinfo *router_gw_ifinfo = NULL;
2586 struct batadv_neigh_node *router_gw = NULL;
2587 struct batadv_neigh_node *router_orig = NULL;
2588 u8 gw_tq_avg, orig_tq_avg;
2591 /* dynamic re-election is performed only on fast or late switch */
2592 if (atomic_read(&bat_priv->gw.sel_class) <= 2)
2595 router_gw = batadv_orig_router_get(curr_gw_orig, BATADV_IF_DEFAULT);
2601 router_gw_ifinfo = batadv_neigh_ifinfo_get(router_gw,
2603 if (!router_gw_ifinfo) {
2608 router_orig = batadv_orig_router_get(orig_node, BATADV_IF_DEFAULT);
2612 router_orig_ifinfo = batadv_neigh_ifinfo_get(router_orig,
2614 if (!router_orig_ifinfo)
2617 gw_tq_avg = router_gw_ifinfo->bat_iv.tq_avg;
2618 orig_tq_avg = router_orig_ifinfo->bat_iv.tq_avg;
2620 /* the TQ value has to be better */
2621 if (orig_tq_avg < gw_tq_avg)
2624 /* if the routing class is greater than 3 the value tells us how much
2625 * greater the TQ value of the new gateway must be
2627 if ((atomic_read(&bat_priv->gw.sel_class) > 3) &&
2628 (orig_tq_avg - gw_tq_avg < atomic_read(&bat_priv->gw.sel_class)))
2631 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
2632 "Restarting gateway selection: better gateway found (tq curr: %i, tq new: %i)\n",
2633 gw_tq_avg, orig_tq_avg);
2637 if (router_gw_ifinfo)
2638 batadv_neigh_ifinfo_put(router_gw_ifinfo);
2639 if (router_orig_ifinfo)
2640 batadv_neigh_ifinfo_put(router_orig_ifinfo);
2642 batadv_neigh_node_put(router_gw);
2644 batadv_neigh_node_put(router_orig);
2649 #ifdef CONFIG_BATMAN_ADV_DEBUGFS
2650 /* fails if orig_node has no router */
2651 static int batadv_iv_gw_write_buffer_text(struct batadv_priv *bat_priv,
2652 struct seq_file *seq,
2653 const struct batadv_gw_node *gw_node)
2655 struct batadv_gw_node *curr_gw;
2656 struct batadv_neigh_node *router;
2657 struct batadv_neigh_ifinfo *router_ifinfo = NULL;
2660 router = batadv_orig_router_get(gw_node->orig_node, BATADV_IF_DEFAULT);
2664 router_ifinfo = batadv_neigh_ifinfo_get(router, BATADV_IF_DEFAULT);
2668 curr_gw = batadv_gw_get_selected_gw_node(bat_priv);
2670 seq_printf(seq, "%s %pM (%3i) %pM [%10s]: %u.%u/%u.%u MBit\n",
2671 (curr_gw == gw_node ? "=>" : " "),
2672 gw_node->orig_node->orig,
2673 router_ifinfo->bat_iv.tq_avg, router->addr,
2674 router->if_incoming->net_dev->name,
2675 gw_node->bandwidth_down / 10,
2676 gw_node->bandwidth_down % 10,
2677 gw_node->bandwidth_up / 10,
2678 gw_node->bandwidth_up % 10);
2679 ret = seq_has_overflowed(seq) ? -1 : 0;
2682 batadv_gw_node_put(curr_gw);
2685 batadv_neigh_ifinfo_put(router_ifinfo);
2687 batadv_neigh_node_put(router);
2691 static void batadv_iv_gw_print(struct batadv_priv *bat_priv,
2692 struct seq_file *seq)
2694 struct batadv_gw_node *gw_node;
2698 " Gateway (#/255) Nexthop [outgoingIF]: advertised uplink bandwidth\n");
2701 hlist_for_each_entry_rcu(gw_node, &bat_priv->gw.gateway_list, list) {
2702 /* fails if orig_node has no router */
2703 if (batadv_iv_gw_write_buffer_text(bat_priv, seq, gw_node) < 0)
2711 seq_puts(seq, "No gateways in range ...\n");
2716 * batadv_iv_gw_dump_entry() - Dump a gateway into a message
2717 * @msg: Netlink message to dump into
2718 * @portid: Port making netlink request
2719 * @seq: Sequence number of netlink message
2720 * @bat_priv: The bat priv with all the soft interface information
2721 * @gw_node: Gateway to be dumped
2723 * Return: Error code, or 0 on success
2725 static int batadv_iv_gw_dump_entry(struct sk_buff *msg, u32 portid, u32 seq,
2726 struct batadv_priv *bat_priv,
2727 struct batadv_gw_node *gw_node)
2729 struct batadv_neigh_ifinfo *router_ifinfo = NULL;
2730 struct batadv_neigh_node *router;
2731 struct batadv_gw_node *curr_gw;
2735 router = batadv_orig_router_get(gw_node->orig_node, BATADV_IF_DEFAULT);
2739 router_ifinfo = batadv_neigh_ifinfo_get(router, BATADV_IF_DEFAULT);
2743 curr_gw = batadv_gw_get_selected_gw_node(bat_priv);
2745 hdr = genlmsg_put(msg, portid, seq, &batadv_netlink_family,
2746 NLM_F_MULTI, BATADV_CMD_GET_GATEWAYS);
2754 if (curr_gw == gw_node)
2755 if (nla_put_flag(msg, BATADV_ATTR_FLAG_BEST)) {
2756 genlmsg_cancel(msg, hdr);
2760 if (nla_put(msg, BATADV_ATTR_ORIG_ADDRESS, ETH_ALEN,
2761 gw_node->orig_node->orig) ||
2762 nla_put_u8(msg, BATADV_ATTR_TQ, router_ifinfo->bat_iv.tq_avg) ||
2763 nla_put(msg, BATADV_ATTR_ROUTER, ETH_ALEN,
2765 nla_put_string(msg, BATADV_ATTR_HARD_IFNAME,
2766 router->if_incoming->net_dev->name) ||
2767 nla_put_u32(msg, BATADV_ATTR_BANDWIDTH_DOWN,
2768 gw_node->bandwidth_down) ||
2769 nla_put_u32(msg, BATADV_ATTR_BANDWIDTH_UP,
2770 gw_node->bandwidth_up)) {
2771 genlmsg_cancel(msg, hdr);
2775 genlmsg_end(msg, hdr);
2780 batadv_neigh_ifinfo_put(router_ifinfo);
2782 batadv_neigh_node_put(router);
2787 * batadv_iv_gw_dump() - Dump gateways into a message
2788 * @msg: Netlink message to dump into
2789 * @cb: Control block containing additional options
2790 * @bat_priv: The bat priv with all the soft interface information
2792 static void batadv_iv_gw_dump(struct sk_buff *msg, struct netlink_callback *cb,
2793 struct batadv_priv *bat_priv)
2795 int portid = NETLINK_CB(cb->skb).portid;
2796 struct batadv_gw_node *gw_node;
2797 int idx_skip = cb->args[0];
2801 hlist_for_each_entry_rcu(gw_node, &bat_priv->gw.gateway_list, list) {
2802 if (idx++ < idx_skip)
2805 if (batadv_iv_gw_dump_entry(msg, portid, cb->nlh->nlmsg_seq,
2806 bat_priv, gw_node)) {
2816 cb->args[0] = idx_skip;
2819 static struct batadv_algo_ops batadv_batman_iv __read_mostly = {
2820 .name = "BATMAN_IV",
2822 .activate = batadv_iv_iface_activate,
2823 .enable = batadv_iv_ogm_iface_enable,
2824 .disable = batadv_iv_ogm_iface_disable,
2825 .update_mac = batadv_iv_ogm_iface_update_mac,
2826 .primary_set = batadv_iv_ogm_primary_iface_set,
2829 .cmp = batadv_iv_ogm_neigh_cmp,
2830 .is_similar_or_better = batadv_iv_ogm_neigh_is_sob,
2831 #ifdef CONFIG_BATMAN_ADV_DEBUGFS
2832 .print = batadv_iv_neigh_print,
2834 .dump = batadv_iv_ogm_neigh_dump,
2837 #ifdef CONFIG_BATMAN_ADV_DEBUGFS
2838 .print = batadv_iv_ogm_orig_print,
2840 .dump = batadv_iv_ogm_orig_dump,
2841 .free = batadv_iv_ogm_orig_free,
2842 .add_if = batadv_iv_ogm_orig_add_if,
2843 .del_if = batadv_iv_ogm_orig_del_if,
2846 .init_sel_class = batadv_iv_init_sel_class,
2847 .get_best_gw_node = batadv_iv_gw_get_best_gw_node,
2848 .is_eligible = batadv_iv_gw_is_eligible,
2849 #ifdef CONFIG_BATMAN_ADV_DEBUGFS
2850 .print = batadv_iv_gw_print,
2852 .dump = batadv_iv_gw_dump,
2857 * batadv_iv_init() - B.A.T.M.A.N. IV initialization function
2859 * Return: 0 on success or negative error number in case of failure
2861 int __init batadv_iv_init(void)
2865 /* batman originator packet */
2866 ret = batadv_recv_handler_register(BATADV_IV_OGM,
2867 batadv_iv_ogm_receive);
2871 ret = batadv_algo_register(&batadv_batman_iv);
2873 goto handler_unregister;
2878 batadv_recv_handler_unregister(BATADV_IV_OGM);