[PATCH 0/3] batman-adv: broadcast flooding improvements

[PATCH 0/3] batman-adv: broadcast flooding improvements

[Linus Lüssing]

Hi,

This patchset adds two improvements for the broadcast flooding
algorithm:

The first patch refactors/reorders the broadcast packet queueing.
Before a broadcast packet was always queued. Now the queueing decision
is performed on a per interface basis. Also the first broadcast is always
transmitted immediately, without queueing now to increase performance.

Furthermore this restructuring prepares for the next two patches:

Patches 2 and 3 introduce a broadcast-packet-to-unicast mechanism.
Similar to the multicast-to-unicast feature of the multicast back-end a
broadcast packet is split into multiple unicast transmissions. The major
difference here, for the broadcast flooding, is that it is performed on
a per-hop instead of the initial originator node basis.

This should improve throughput and reliability in densely populated
receiver scenarios, where the multicast back-end is not able to operate
(the multicast back-end is more targeted at sparsely populated receiver
scenarios so far).

Regards, Linus

[PATCH 1/3] batman-adv: bcast: queue per interface, if needed

[Linus Lüssing]

Currently we schedule a broadcast packet like:

3x: [ [(re-)queue] --> for(hard-if): maybe-transmit ]

The intention of queueing a broadcast packet multiple times is to
increase robustness for wireless interfaces. However on interfaces
which we only broadcast on once the queueing induces an unncessary
penalty. This patch restructures the queueing to be performed on a per
interface basis:

for(hard-if):
- transmit
- if wireless: [queue] --> transmit --> [requeue] --> transmit

Next to the performance benefits on non-wireless interfaces this
should also make it easier to apply alternative strategies for
transmissions on wireless interfaces in the future (for instance sending
via unicast transmissions on wireless interfaces, without queueing in
batman-adv, if appropriate).

Signed-off-by: Linus Lüssing <linus.luessing@c0d3.blue>
---
 net/batman-adv/main.h           |   1 -
 net/batman-adv/routing.c        |   9 +-
 net/batman-adv/send.c           | 391 ++++++++++++++++++++++----------
 net/batman-adv/send.h           |  12 +-
 net/batman-adv/soft-interface.c |  12 +-
 5 files changed, 288 insertions(+), 137 deletions(-)

diff --git a/net/batman-adv/main.h b/net/batman-adv/main.h
index c59afcba..ddef606c 100644
--- a/net/batman-adv/main.h
+++ b/net/batman-adv/main.h
@@ -88,7 +88,6 @@
 /* number of packets to send for broadcasts on different interface types */
 #define BATADV_NUM_BCASTS_DEFAULT 1
 #define BATADV_NUM_BCASTS_WIRELESS 3
-#define BATADV_NUM_BCASTS_MAX 3
 
 /* length of the single packet used by the TP meter */
 #define BATADV_TP_PACKET_LEN ETH_DATA_LEN
diff --git a/net/batman-adv/routing.c b/net/batman-adv/routing.c
index f0f86482..30fbd073 100644
--- a/net/batman-adv/routing.c
+++ b/net/batman-adv/routing.c
@@ -1188,9 +1188,9 @@ int batadv_recv_bcast_packet(struct sk_buff *skb,
 	struct batadv_bcast_packet *bcast_packet;
 	struct ethhdr *ethhdr;
 	int hdr_size = sizeof(*bcast_packet);
-	int ret = NET_RX_DROP;
 	s32 seq_diff;
 	u32 seqno;
+	int ret;
 
 	/* drop packet if it has not necessary minimum size */
 	if (unlikely(!pskb_may_pull(skb, hdr_size)))
@@ -1216,7 +1216,7 @@ int batadv_recv_bcast_packet(struct sk_buff *skb,
 	if (batadv_is_my_mac(bat_priv, bcast_packet->orig))
 		goto free_skb;
 
-	if (bcast_packet->ttl < 2)
+	if (bcast_packet->ttl-- < 2)
 		goto free_skb;
 
 	orig_node = batadv_orig_hash_find(bat_priv, bcast_packet->orig);
@@ -1255,7 +1255,9 @@ int batadv_recv_bcast_packet(struct sk_buff *skb,
 	batadv_skb_set_priority(skb, sizeof(struct batadv_bcast_packet));
 
 	/* rebroadcast packet */
-	batadv_add_bcast_packet_to_list(bat_priv, skb, 1, false);
+	ret = batadv_forw_bcast_packet(bat_priv, skb, 0, false);
+	if (ret == NETDEV_TX_BUSY)
+		goto free_skb;
 
 	/* don't hand the broadcast up if it is from an originator
 	 * from the same backbone.
@@ -1281,6 +1283,7 @@ int batadv_recv_bcast_packet(struct sk_buff *skb,
 	spin_unlock_bh(&orig_node->bcast_seqno_lock);
 free_skb:
 	kfree_skb(skb);
+	ret = NET_RX_DROP;
 out:
 	if (orig_node)
 		batadv_orig_node_put(orig_node);
diff --git a/net/batman-adv/send.c b/net/batman-adv/send.c
index 3ce5f7ba..1341b9ac 100644
--- a/net/batman-adv/send.c
+++ b/net/batman-adv/send.c
@@ -737,57 +737,52 @@ void batadv_forw_packet_ogmv1_queue(struct batadv_priv *bat_priv,
 }
 
 /**
- * batadv_add_bcast_packet_to_list() - queue broadcast packet for multiple sends
+ * batadv_forw_bcast_packet_to_list() - queue broadcast packet for transmissions
  * @bat_priv: the bat priv with all the soft interface information
  * @skb: broadcast packet to add
  * @delay: number of jiffies to wait before sending
  * @own_packet: true if it is a self-generated broadcast packet
+ * @if_in: the interface where the packet was received on
+ * @if_out: the outgoing interface to queue on
  *
- * add a broadcast packet to the queue and setup timers. broadcast packets
+ * Adds a broadcast packet to the queue and sets up timers. Broadcast packets
  * are sent multiple times to increase probability for being received.
  *
- * The skb is not consumed, so the caller should make sure that the
- * skb is freed.
+ * This call clones the given skb, hence the caller needs to take into
+ * account that the data segment of the original skb might not be
+ * modifiable anymore.
  *
  * Return: NETDEV_TX_OK on success and NETDEV_TX_BUSY on errors.
  */
-int batadv_add_bcast_packet_to_list(struct batadv_priv *bat_priv,
-				    const struct sk_buff *skb,
-				    unsigned long delay,
-				    bool own_packet)
+static int batadv_forw_bcast_packet_to_list(struct batadv_priv *bat_priv,
+					    struct sk_buff *skb,
+					    unsigned long delay,
+					    bool own_packet,
+					    struct batadv_hard_iface *if_in,
+					    struct batadv_hard_iface *if_out)
 {
-	struct batadv_hard_iface *primary_if;
 	struct batadv_forw_packet *forw_packet;
-	struct batadv_bcast_packet *bcast_packet;
+	unsigned long send_time = jiffies;
 	struct sk_buff *newskb;
 
-	primary_if = batadv_primary_if_get_selected(bat_priv);
-	if (!primary_if)
+	newskb = skb_clone(skb, GFP_ATOMIC);
+	if (!newskb)
 		goto err;
 
-	newskb = skb_copy(skb, GFP_ATOMIC);
-	if (!newskb) {
-		batadv_hardif_put(primary_if);
-		goto err;
-	}
-
-	forw_packet = batadv_forw_packet_alloc(primary_if, NULL,
+	forw_packet = batadv_forw_packet_alloc(if_in, if_out,
 					       &bat_priv->bcast_queue_left,
 					       bat_priv, newskb);
-	batadv_hardif_put(primary_if);
 	if (!forw_packet)
 		goto err_packet_free;
 
-	/* as we have a copy now, it is safe to decrease the TTL */
-	bcast_packet = (struct batadv_bcast_packet *)newskb->data;
-	bcast_packet->ttl--;
-
 	forw_packet->own = own_packet;
 
 	INIT_DELAYED_WORK(&forw_packet->delayed_work,
 			  batadv_send_outstanding_bcast_packet);
 
-	batadv_forw_packet_bcast_queue(bat_priv, forw_packet, jiffies + delay);
+	send_time += delay ? delay : msecs_to_jiffies(5);
+
+	batadv_forw_packet_bcast_queue(bat_priv, forw_packet, send_time);
 	return NETDEV_TX_OK;
 
 err_packet_free:
@@ -796,6 +791,231 @@ int batadv_add_bcast_packet_to_list(struct batadv_priv *bat_priv,
 	return NETDEV_TX_BUSY;
 }
 
+/**
+ * batadv_forw_bcast_packet_if() - forward and queue a broadcast packet
+ * @bat_priv: the bat priv with all the soft interface information
+ * @skb: broadcast packet to add
+ * @delay: number of jiffies to wait before sending
+ * @own_packet: true if it is a self-generated broadcast packet
+ * @if_in: the interface where the packet was received on
+ * @if_out: the outgoing interface to forward to
+ *
+ * Transmits a broadcast packet on the specified interface either immediately
+ * or if a delay is given after that. Furthermore, queues additional
+ * retransmissions if this interface is a wireless one.
+ *
+ * This call clones the given skb, hence the caller needs to take into
+ * account that the data segment of the original skb might not be
+ * modifiable anymore.
+ *
+ * Return: NETDEV_TX_OK on success and NETDEV_TX_BUSY on errors.
+ */
+static int batadv_forw_bcast_packet_if(struct batadv_priv *bat_priv,
+				       struct sk_buff *skb,
+				       unsigned long delay,
+				       bool own_packet,
+				       struct batadv_hard_iface *if_in,
+				       struct batadv_hard_iface *if_out)
+{
+	unsigned int num_bcasts = if_out->num_bcasts;
+	struct sk_buff *newskb;
+	int ret = NETDEV_TX_OK;
+
+	if (!delay) {
+		newskb = skb_clone(skb, GFP_ATOMIC);
+		if (!newskb)
+			return NETDEV_TX_BUSY;
+
+		batadv_send_broadcast_skb(newskb, if_out);
+		num_bcasts--;
+	}
+
+	/* delayed broadcast or rebroadcasts? */
+	if (delay || num_bcasts >= 1) {
+		BATADV_SKB_CB(skb)->num_bcasts = num_bcasts;
+
+		ret = batadv_forw_bcast_packet_to_list(bat_priv, skb, delay,
+						       own_packet, if_in,
+						       if_out);
+	}
+
+	return ret;
+}
+
+/**
+ * batadv_send_no_broadcast() - check whether (re)broadcast is necessary
+ * @bat_priv: the bat priv with all the soft interface information
+ * @skb: broadcast packet to check
+ * @own_packet: true if it is a self-generated broadcast packet
+ * @if_out: the outgoing interface checked and considered for (re)broadcast
+ *
+ * Return: False if a packet needs to be (re)broadcasted on the given interface,
+ * true otherwise.
+ */
+static bool batadv_send_no_broadcast(struct batadv_priv *bat_priv,
+				     struct sk_buff *skb, bool own_packet,
+				     struct batadv_hard_iface *if_out)
+{
+	struct batadv_hardif_neigh_node *neigh_node = NULL;
+	struct batadv_bcast_packet *bcast_packet;
+	u8 *orig_neigh;
+	u8 *neigh_addr;
+	char *type;
+	int ret;
+
+	if (!own_packet) {
+		neigh_addr = eth_hdr(skb)->h_source;
+		neigh_node = batadv_hardif_neigh_get(if_out,
+						     neigh_addr);
+	}
+
+	bcast_packet = (struct batadv_bcast_packet *)skb->data;
+	orig_neigh = neigh_node ? neigh_node->orig : NULL;
+
+	ret = batadv_hardif_no_broadcast(if_out, bcast_packet->orig,
+					 orig_neigh);
+
+	if (neigh_node)
+		batadv_hardif_neigh_put(neigh_node);
+
+	/* ok, may broadcast */
+	if (!ret)
+		return false;
+
+	/* no broadcast */
+	switch (ret) {
+	case BATADV_HARDIF_BCAST_NORECIPIENT:
+		type = "no neighbor";
+		break;
+	case BATADV_HARDIF_BCAST_DUPFWD:
+		type = "single neighbor is source";
+		break;
+	case BATADV_HARDIF_BCAST_DUPORIG:
+		type = "single neighbor is originator";
+		break;
+	default:
+		type = "unknown";
+	}
+
+	batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
+		   "BCAST packet from orig %pM on %s suppressed: %s\n",
+		   bcast_packet->orig,
+		   if_out->net_dev->name, type);
+
+	return true;
+}
+
+/**
+ * __batadv_forw_bcast_packet() - forward and queue a broadcast packet
+ * @bat_priv: the bat priv with all the soft interface information
+ * @skb: broadcast packet to add
+ * @delay: number of jiffies to wait before sending
+ * @own_packet: true if it is a self-generated broadcast packet
+ *
+ * Transmits a broadcast packet either immediately or if a delay is given
+ * after that. Furthermore, queues additional retransmissions on wireless
+ * interfaces.
+ *
+ * This call clones the given skb, hence the caller needs to take into
+ * account that the data segment of the given skb might not be
+ * modifiable anymore.
+ *
+ * Return: NETDEV_TX_OK on success and NETDEV_TX_BUSY on errors.
+ */
+static int __batadv_forw_bcast_packet(struct batadv_priv *bat_priv,
+				      struct sk_buff *skb,
+				      unsigned long delay,
+				      bool own_packet)
+{
+	struct batadv_hard_iface *hard_iface;
+	struct batadv_hard_iface *primary_if;
+	int ret = NETDEV_TX_OK;
+
+	primary_if = batadv_primary_if_get_selected(bat_priv);
+	if (!primary_if)
+		return NETDEV_TX_BUSY;
+
+	rcu_read_lock();
+	list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) {
+		if (hard_iface->soft_iface != bat_priv->soft_iface)
+			continue;
+
+		if (!kref_get_unless_zero(&hard_iface->refcount))
+			continue;
+
+		if (batadv_send_no_broadcast(bat_priv, skb, own_packet,
+					     hard_iface)) {
+			batadv_hardif_put(hard_iface);
+			continue;
+		}
+
+		ret = batadv_forw_bcast_packet_if(bat_priv, skb, delay,
+						  own_packet, primary_if,
+						  hard_iface);
+		batadv_hardif_put(hard_iface);
+
+		if (ret == NETDEV_TX_BUSY)
+			break;
+	}
+	rcu_read_unlock();
+
+	batadv_hardif_put(primary_if);
+	return ret;
+}
+
+/**
+ * batadv_forw_bcast_packet() - forward and queue a broadcast packet
+ * @bat_priv: the bat priv with all the soft interface information
+ * @skb: broadcast packet to add
+ * @delay: number of jiffies to wait before sending
+ * @own_packet: true if it is a self-generated broadcast packet
+ *
+ * Transmits a broadcast packet either immediately or if a delay is given
+ * after that. Furthermore, queues additional retransmissions on wireless
+ * interfaces.
+ *
+ * This call might reallocate skb data.
+ *
+ * Return: NETDEV_TX_OK on success and NETDEV_TX_BUSY on errors.
+ */
+int batadv_forw_bcast_packet(struct batadv_priv *bat_priv,
+			     struct sk_buff *skb,
+			     unsigned long delay,
+			     bool own_packet)
+{
+	int ret = __batadv_forw_bcast_packet(bat_priv, skb, delay, own_packet);
+
+	if (ret == NETDEV_TX_BUSY)
+		return ret;
+
+	/* __batadv_forw_bcast_packet clones, make sure original
+	 * skb stays writeable
+	 */
+	return (skb_cow(skb, 0) < 0) ? NETDEV_TX_BUSY : NETDEV_TX_OK;
+}
+
+/**
+ * batadv_send_bcast_packet() - send and queue a broadcast packet
+ * @bat_priv: the bat priv with all the soft interface information
+ * @skb: broadcast packet to add
+ * @delay: number of jiffies to wait before sending
+ * @own_packet: true if it is a self-generated broadcast packet
+ *
+ * Transmits a broadcast packet either immediately or if a delay is given
+ * after that. Furthermore, queues additional retransmissions on wireless
+ * interfaces.
+ *
+ * Consumes the provided skb.
+ */
+void batadv_send_bcast_packet(struct batadv_priv *bat_priv,
+			      struct sk_buff *skb,
+			      unsigned long delay,
+			      bool own_packet)
+{
+	__batadv_forw_bcast_packet(bat_priv, skb, delay, own_packet);
+	consume_skb(skb);
+}
+
 /**
  * batadv_forw_packet_bcasts_left() - check if a retransmission is necessary
  * @forw_packet: the forwarding packet to check
@@ -811,28 +1031,20 @@ int batadv_add_bcast_packet_to_list(struct batadv_priv *bat_priv,
  * Return: True if (re)transmissions are left, false otherwise.
  */
 static bool
-batadv_forw_packet_bcasts_left(struct batadv_forw_packet *forw_packet,
-			       struct batadv_hard_iface *hard_iface)
+batadv_forw_packet_bcasts_left(struct batadv_forw_packet *forw_packet)
 {
-	unsigned int max;
-
-	if (hard_iface)
-		max = hard_iface->num_bcasts;
-	else
-		max = BATADV_NUM_BCASTS_MAX;
-
-	return BATADV_SKB_CB(forw_packet->skb)->num_bcasts < max;
+	return BATADV_SKB_CB(forw_packet->skb)->num_bcasts;
 }
 
 /**
- * batadv_forw_packet_bcasts_inc() - increment retransmission counter of a
+ * batadv_forw_packet_bcasts_dec() - decrement retransmission counter of a
  *  packet
- * @forw_packet: the packet to increase the counter for
+ * @forw_packet: the packet to decrease the counter for
  */
 static void
-batadv_forw_packet_bcasts_inc(struct batadv_forw_packet *forw_packet)
+batadv_forw_packet_bcasts_dec(struct batadv_forw_packet *forw_packet)
 {
-	BATADV_SKB_CB(forw_packet->skb)->num_bcasts++;
+	BATADV_SKB_CB(forw_packet->skb)->num_bcasts--;
 }
 
 /**
@@ -843,30 +1055,30 @@ batadv_forw_packet_bcasts_inc(struct batadv_forw_packet *forw_packet)
  */
 bool batadv_forw_packet_is_rebroadcast(struct batadv_forw_packet *forw_packet)
 {
-	return BATADV_SKB_CB(forw_packet->skb)->num_bcasts > 0;
+	unsigned char num_bcasts = BATADV_SKB_CB(forw_packet->skb)->num_bcasts;
+
+	return num_bcasts != forw_packet->if_outgoing->num_bcasts;
 }
 
+/**
+ * batadv_send_outstanding_bcast_packet() - transmit a queued broadcast packet
+ * @work: work queue item
+ *
+ * Transmits a queued broadcast packet and if necessary reschedules it.
+ */
 static void batadv_send_outstanding_bcast_packet(struct work_struct *work)
 {
-	struct batadv_hard_iface *hard_iface;
-	struct batadv_hardif_neigh_node *neigh_node;
+	unsigned long send_time = jiffies + msecs_to_jiffies(5);
+	struct batadv_forw_packet *forw_packet;
 	struct delayed_work *delayed_work;
-	struct batadv_forw_packet *forw_packet;
-	struct batadv_bcast_packet *bcast_packet;
+	struct batadv_priv *bat_priv;
 	struct sk_buff *skb1;
-	struct net_device *soft_iface;
-	struct batadv_priv *bat_priv;
-	unsigned long send_time = jiffies + msecs_to_jiffies(5);
 	bool dropped = false;
-	u8 *neigh_addr;
-	u8 *orig_neigh;
-	int ret = 0;
 
 	delayed_work = to_delayed_work(work);
 	forw_packet = container_of(delayed_work, struct batadv_forw_packet,
 				   delayed_work);
-	soft_iface = forw_packet->if_incoming->soft_iface;
-	bat_priv = netdev_priv(soft_iface);
+	bat_priv = netdev_priv(forw_packet->if_incoming->soft_iface);
 
 	if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_DEACTIVATING) {
 		dropped = true;
@@ -878,76 +1090,15 @@ static void batadv_send_outstanding_bcast_packet(struct work_struct *work)
 		goto out;
 	}
 
-	bcast_packet = (struct batadv_bcast_packet *)forw_packet->skb->data;
+	/* send a copy of the saved skb */
+	skb1 = skb_clone(forw_packet->skb, GFP_ATOMIC);
+	if (!skb1)
+		goto out;
 
-	/* rebroadcast packet */
-	rcu_read_lock();
-	list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) {
-		if (hard_iface->soft_iface != soft_iface)
-			continue;
+	batadv_send_broadcast_skb(skb1, forw_packet->if_outgoing);
+	batadv_forw_packet_bcasts_dec(forw_packet);
 
-		if (!batadv_forw_packet_bcasts_left(forw_packet, hard_iface))
-			continue;
-
-		if (forw_packet->own) {
-			neigh_node = NULL;
-		} else {
-			neigh_addr = eth_hdr(forw_packet->skb)->h_source;
-			neigh_node = batadv_hardif_neigh_get(hard_iface,
-							     neigh_addr);
-		}
-
-		orig_neigh = neigh_node ? neigh_node->orig : NULL;
-
-		ret = batadv_hardif_no_broadcast(hard_iface, bcast_packet->orig,
-						 orig_neigh);
-
-		if (ret) {
-			char *type;
-
-			switch (ret) {
-			case BATADV_HARDIF_BCAST_NORECIPIENT:
-				type = "no neighbor";
-				break;
-			case BATADV_HARDIF_BCAST_DUPFWD:
-				type = "single neighbor is source";
-				break;
-			case BATADV_HARDIF_BCAST_DUPORIG:
-				type = "single neighbor is originator";
-				break;
-			default:
-				type = "unknown";
-			}
-
-			batadv_dbg(BATADV_DBG_BATMAN, bat_priv, "BCAST packet from orig %pM on %s suppressed: %s\n",
-				   bcast_packet->orig,
-				   hard_iface->net_dev->name, type);
-
-			if (neigh_node)
-				batadv_hardif_neigh_put(neigh_node);
-
-			continue;
-		}
-
-		if (neigh_node)
-			batadv_hardif_neigh_put(neigh_node);
-
-		if (!kref_get_unless_zero(&hard_iface->refcount))
-			continue;
-
-		/* send a copy of the saved skb */
-		skb1 = skb_clone(forw_packet->skb, GFP_ATOMIC);
-		if (skb1)
-			batadv_send_broadcast_skb(skb1, hard_iface);
-
-		batadv_hardif_put(hard_iface);
-	}
-	rcu_read_unlock();
-
-	batadv_forw_packet_bcasts_inc(forw_packet);
-
-	/* if we still have some more bcasts to send */
-	if (batadv_forw_packet_bcasts_left(forw_packet, NULL)) {
+	if (batadv_forw_packet_bcasts_left(forw_packet)) {
 		batadv_forw_packet_bcast_queue(bat_priv, forw_packet,
 					       send_time);
 		return;
diff --git a/net/batman-adv/send.h b/net/batman-adv/send.h
index 5921ee4e..f8cfb1dd 100644
--- a/net/batman-adv/send.h
+++ b/net/batman-adv/send.h
@@ -40,10 +40,14 @@ int batadv_send_broadcast_skb(struct sk_buff *skb,
 			      struct batadv_hard_iface *hard_iface);
 int batadv_send_unicast_skb(struct sk_buff *skb,
 			    struct batadv_neigh_node *neigh_node);
-int batadv_add_bcast_packet_to_list(struct batadv_priv *bat_priv,
-				    const struct sk_buff *skb,
-				    unsigned long delay,
-				    bool own_packet);
+int batadv_forw_bcast_packet(struct batadv_priv *bat_priv,
+			     struct sk_buff *skb,
+			     unsigned long delay,
+			     bool own_packet);
+void batadv_send_bcast_packet(struct batadv_priv *bat_priv,
+			      struct sk_buff *skb,
+			      unsigned long delay,
+			      bool own_packet);
 void
 batadv_purge_outstanding_packets(struct batadv_priv *bat_priv,
 				 const struct batadv_hard_iface *hard_iface);
diff --git a/net/batman-adv/soft-interface.c b/net/batman-adv/soft-interface.c
index a7677e1d..5df29ce8 100644
--- a/net/batman-adv/soft-interface.c
+++ b/net/batman-adv/soft-interface.c
@@ -192,7 +192,7 @@ static netdev_tx_t batadv_interface_tx(struct sk_buff *skb,
 	struct vlan_ethhdr *vhdr;
 	unsigned int header_len = 0;
 	int data_len = skb->len, ret;
-	unsigned long brd_delay = 1;
+	unsigned long brd_delay = 0;
 	bool do_bcast = false, client_added;
 	unsigned short vid;
 	u32 seqno;
@@ -331,7 +331,7 @@ static netdev_tx_t batadv_interface_tx(struct sk_buff *skb,
 
 		bcast_packet = (struct batadv_bcast_packet *)skb->data;
 		bcast_packet->version = BATADV_COMPAT_VERSION;
-		bcast_packet->ttl = BATADV_TTL;
+		bcast_packet->ttl = BATADV_TTL - 1;
 
 		/* batman packet type: broadcast */
 		bcast_packet->packet_type = BATADV_BCAST;
@@ -347,13 +347,7 @@ static netdev_tx_t batadv_interface_tx(struct sk_buff *skb,
 		seqno = atomic_inc_return(&bat_priv->bcast_seqno);
 		bcast_packet->seqno = htonl(seqno);
 
-		batadv_add_bcast_packet_to_list(bat_priv, skb, brd_delay, true);
-
-		/* a copy is stored in the bcast list, therefore removing
-		 * the original skb.
-		 */
-		consume_skb(skb);
-
+		batadv_send_bcast_packet(bat_priv, skb, brd_delay, true);
 	/* unicast packet */
 	} else {
 		/* DHCP packets going to a server will use the GW feature */
-- 
2.20.1

Re: [PATCH 1/3] batman-adv: bcast: queue per interface, if needed

[Sven Eckelmann]

[-- Attachment #1: Type: text/plain, Size: 883 bytes --]

On Tuesday, 14 May 2019 09:38:57 CEST Linus Lüssing wrote:
> which we only broadcast on once the queueing induces an unncessary

unnecessary

>  /**
>   * batadv_forw_packet_bcasts_left() - check if a retransmission is necessary
>   * @forw_packet: the forwarding packet to check
> @@ -811,28 +1031,20 @@ int batadv_add_bcast_packet_to_list(struct batadv_priv *bat_priv,
>   * Return: True if (re)transmissions are left, false otherwise.
>   */
>  static bool
> -batadv_forw_packet_bcasts_left(struct batadv_forw_packet *forw_packet,
> -                              struct batadv_hard_iface *hard_iface)
> +batadv_forw_packet_bcasts_left(struct batadv_forw_packet *forw_packet)


/home/sven/tmp/qemu-batman/batman-adv/net/batman-adv/send.c:1191: warning: Excess function parameter 'hard_iface' description in 'batadv_forw_packet_bcasts_left'

Kind regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH 2/3] batman-adv: allow broadcast packet type with unicast destination

[Linus Lüssing]

So far, only batman-adv broadcast packets are allowed if they have a
broadcast ethernet destination.

For the upcoming broadcast-via-unicasts feature it is necessary that a
neighboring node is capable of receiving a batman-adv broadcast packet
with a unicast ethernet destination, too.

Therefore this patch relaxes the ethernet destination check for
batman-adv broadcast packets and adds the necessary capability tracking
for later compatibility checking.

Signed-off-by: Linus Lüssing <linus.luessing@c0d3.blue>
---
 include/uapi/linux/batadv_packet.h |  2 +
 net/batman-adv/bat_iv_ogm.c        |  6 ++-
 net/batman-adv/bat_v_elp.c         |  2 +
 net/batman-adv/hard-interface.c    |  1 +
 net/batman-adv/originator.c        | 65 ++++++++++++++++++++++++++++++
 net/batman-adv/originator.h        |  3 ++
 net/batman-adv/routing.c           |  7 +++-
 net/batman-adv/types.h             | 21 ++++++++++
 8 files changed, 104 insertions(+), 3 deletions(-)

diff --git a/include/uapi/linux/batadv_packet.h b/include/uapi/linux/batadv_packet.h
index 4ebc2135..2ec59e4a 100644
--- a/include/uapi/linux/batadv_packet.h
+++ b/include/uapi/linux/batadv_packet.h
@@ -164,6 +164,7 @@ enum batadv_bla_claimframe {
  * @BATADV_TVLV_TT: translation table tvlv
  * @BATADV_TVLV_ROAM: roaming advertisement tvlv
  * @BATADV_TVLV_MCAST: multicast capability tvlv
+ * @BATADV_TVLV_BCAST: broadcast capability tvlv
  */
 enum batadv_tvlv_type {
 	BATADV_TVLV_GW		= 0x01,
@@ -172,6 +173,7 @@ enum batadv_tvlv_type {
 	BATADV_TVLV_TT		= 0x04,
 	BATADV_TVLV_ROAM	= 0x05,
 	BATADV_TVLV_MCAST	= 0x06,
+	BATADV_TVLV_BCAST	= 0x07,
 };
 
 #pragma pack(2)
diff --git a/net/batman-adv/bat_iv_ogm.c b/net/batman-adv/bat_iv_ogm.c
index bd4138dd..bcbebf10 100644
--- a/net/batman-adv/bat_iv_ogm.c
+++ b/net/batman-adv/bat_iv_ogm.c
@@ -1310,8 +1310,12 @@ batadv_iv_ogm_process_per_outif(const struct sk_buff *skb, int ogm_offset,
 	if (is_single_hop_neigh) {
 		hardif_neigh = batadv_hardif_neigh_get(if_incoming,
 						       ethhdr->h_source);
-		if (hardif_neigh)
+		if (hardif_neigh) {
 			hardif_neigh->last_seen = jiffies;
+
+			batadv_hardif_neigh_update_capa(orig_node,
+							hardif_neigh);
+		}
 	}
 
 	router = batadv_orig_router_get(orig_node, if_outgoing);
diff --git a/net/batman-adv/bat_v_elp.c b/net/batman-adv/bat_v_elp.c
index 2614a9ca..d49b61c1 100644
--- a/net/batman-adv/bat_v_elp.c
+++ b/net/batman-adv/bat_v_elp.c
@@ -489,6 +489,8 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv,
 	hardif_neigh->bat_v.elp_latest_seqno = ntohl(elp_packet->seqno);
 	hardif_neigh->bat_v.elp_interval = ntohl(elp_packet->elp_interval);
 
+	batadv_hardif_neigh_update_capa(orig_neigh, hardif_neigh);
+
 hardif_free:
 	if (hardif_neigh)
 		batadv_hardif_neigh_put(hardif_neigh);
diff --git a/net/batman-adv/hard-interface.c b/net/batman-adv/hard-interface.c
index 79d1731b..b71d8efc 100644
--- a/net/batman-adv/hard-interface.c
+++ b/net/batman-adv/hard-interface.c
@@ -936,6 +936,7 @@ batadv_hardif_add_interface(struct net_device *net_dev)
 		hard_iface->num_bcasts = BATADV_NUM_BCASTS_WIRELESS;
 
 	batadv_v_hardif_init(hard_iface);
+	atomic_set(&hard_iface->num_bcast_no_urcv, 0);
 
 	batadv_check_known_mac_addr(hard_iface->net_dev);
 	kref_get(&hard_iface->refcount);
diff --git a/net/batman-adv/originator.c b/net/batman-adv/originator.c
index 45db798a..73eacccf 100644
--- a/net/batman-adv/originator.c
+++ b/net/batman-adv/originator.c
@@ -42,6 +42,7 @@
 #include "routing.h"
 #include "soft-interface.h"
 #include "translation-table.h"
+#include "tvlv.h"
 
 /* hash class keys */
 static struct lock_class_key batadv_orig_hash_lock_class_key;
@@ -196,6 +197,26 @@ void batadv_orig_node_vlan_put(struct batadv_orig_node_vlan *orig_vlan)
 	kref_put(&orig_vlan->refcount, batadv_orig_node_vlan_release);
 }
 
+/**
+ * batadv_orig_bcast_tvlv_ogm_handler() - process incoming broadcast tvlv
+ * @bat_priv: the bat priv with all the soft interface information
+ * @orig: the orig_node of the ogm
+ * @flags: flags indicating the tvlv state (see batadv_tvlv_handler_flags)
+ * @tvlv_value: tvlv buffer containing the multicast data
+ * @tvlv_value_len: tvlv buffer length
+ */
+static void batadv_orig_bcast_tvlv_ogm_handler(struct batadv_priv *bat_priv,
+					       struct batadv_orig_node *orig,
+					       u8 flags,
+					       void *tvlv_value,
+					       u16 tvlv_value_len)
+{
+	if (flags & BATADV_TVLV_HANDLER_OGM_CIFNOTFND)
+		clear_bit(BATADV_ORIG_CAPA_HAS_BCAST_URCV, &orig->capabilities);
+	else
+		set_bit(BATADV_ORIG_CAPA_HAS_BCAST_URCV, &orig->capabilities);
+}
+
 /**
  * batadv_originator_init() - Initialize all originator structures
  * @bat_priv: the bat priv with all the soft interface information
@@ -215,6 +236,12 @@ int batadv_originator_init(struct batadv_priv *bat_priv)
 	batadv_hash_set_lock_class(bat_priv->orig_hash,
 				   &batadv_orig_hash_lock_class_key);
 
+	batadv_tvlv_container_register(bat_priv, BATADV_TVLV_BCAST, 1, NULL, 0);
+	batadv_tvlv_handler_register(bat_priv,
+				     batadv_orig_bcast_tvlv_ogm_handler,
+				     NULL, BATADV_TVLV_BCAST, 1,
+				     BATADV_TVLV_HANDLER_OGM_CIFNOTFND);
+
 	INIT_DELAYED_WORK(&bat_priv->orig_work, batadv_purge_orig);
 	queue_delayed_work(batadv_event_workqueue,
 			   &bat_priv->orig_work,
@@ -269,6 +296,9 @@ static void batadv_hardif_neigh_release(struct kref *ref)
 	hlist_del_init_rcu(&hardif_neigh->list);
 	spin_unlock_bh(&hardif_neigh->if_incoming->neigh_list_lock);
 
+	if (!atomic_read(&hardif_neigh->bcast_has_urcv))
+		atomic_dec(&hardif_neigh->if_incoming->num_bcast_no_urcv);
+
 	batadv_hardif_put(hardif_neigh->if_incoming);
 	kfree_rcu(hardif_neigh, rcu);
 }
@@ -542,6 +572,34 @@ batadv_neigh_node_get(const struct batadv_orig_node *orig_node,
 	return res;
 }
 
+/**
+ * batadv_hardif_neigh_update_capa() - update hardif neighbor capabilities
+ * @orig_node: originator object representing the neighbour
+ * @hardif_neigh: the hardif neighbor to update
+ *
+ * Propagates neighbor node specific capabilities from an originator node onto a
+ * hardif neighbor node:
+ *
+ * This updates the broadcast-via-unicast reception capability flag of a
+ * neighbor node and updates the matching counter on the hard interfaces it
+ * belongs to.
+ */
+void
+batadv_hardif_neigh_update_capa(const struct batadv_orig_node *orig_node,
+				struct batadv_hardif_neigh_node *hardif_neigh)
+{
+	struct batadv_hard_iface *hard_iface = hardif_neigh->if_incoming;
+
+	if (test_bit(BATADV_ORIG_CAPA_HAS_BCAST_URCV,
+		     &orig_node->capabilities)) {
+		if (atomic_add_unless(&hardif_neigh->bcast_has_urcv, 1, 1))
+			atomic_dec(&hard_iface->num_bcast_no_urcv);
+	} else {
+		if (atomic_add_unless(&hardif_neigh->bcast_has_urcv, -1, 0))
+			atomic_inc(&hard_iface->num_bcast_no_urcv);
+	}
+}
+
 /**
  * batadv_hardif_neigh_create() - create a hardif neighbour node
  * @hard_iface: the interface this neighbour is connected to
@@ -576,6 +634,10 @@ batadv_hardif_neigh_create(struct batadv_hard_iface *hard_iface,
 	hardif_neigh->if_incoming = hard_iface;
 	hardif_neigh->last_seen = jiffies;
 
+	atomic_set(&hardif_neigh->bcast_has_urcv, 0);
+	atomic_inc(&hardif_neigh->if_incoming->num_bcast_no_urcv);
+	batadv_hardif_neigh_update_capa(orig_node, hardif_neigh);
+
 	kref_init(&hardif_neigh->refcount);
 
 	if (bat_priv->algo_ops->neigh.hardif_init)
@@ -975,6 +1037,9 @@ void batadv_originator_free(struct batadv_priv *bat_priv)
 
 	cancel_delayed_work_sync(&bat_priv->orig_work);
 
+	batadv_tvlv_container_unregister(bat_priv, BATADV_TVLV_BCAST, 1);
+	batadv_tvlv_handler_unregister(bat_priv, BATADV_TVLV_BCAST, 1);
+
 	bat_priv->orig_hash = NULL;
 
 	for (i = 0; i < hash->size; i++) {
diff --git a/net/batman-adv/originator.h b/net/batman-adv/originator.h
index 3829e26f..fb22161d 100644
--- a/net/batman-adv/originator.h
+++ b/net/batman-adv/originator.h
@@ -30,6 +30,9 @@ batadv_hardif_neigh_get(const struct batadv_hard_iface *hard_iface,
 			const u8 *neigh_addr);
 void
 batadv_hardif_neigh_put(struct batadv_hardif_neigh_node *hardif_neigh);
+void
+batadv_hardif_neigh_update_capa(const struct batadv_orig_node *orig_node,
+				struct batadv_hardif_neigh_node *hardif_neigh);
 struct batadv_neigh_node *
 batadv_neigh_node_get_or_create(struct batadv_orig_node *orig_node,
 				struct batadv_hard_iface *hard_iface,
diff --git a/net/batman-adv/routing.c b/net/batman-adv/routing.c
index 30fbd073..03b4e609 100644
--- a/net/batman-adv/routing.c
+++ b/net/batman-adv/routing.c
@@ -1198,8 +1198,11 @@ int batadv_recv_bcast_packet(struct sk_buff *skb,
 
 	ethhdr = eth_hdr(skb);
 
-	/* packet with broadcast indication but unicast recipient */
-	if (!is_broadcast_ether_addr(ethhdr->h_dest))
+	/* packet with broadcast indication but unicast recipient
+	 * which is not us
+	 */
+	if (!is_broadcast_ether_addr(ethhdr->h_dest) &&
+	    !batadv_is_my_mac(bat_priv, ethhdr->h_dest))
 		goto free_skb;
 
 	/* packet with broadcast/multicast sender address */
diff --git a/net/batman-adv/types.h b/net/batman-adv/types.h
index 74b64473..877a2762 100644
--- a/net/batman-adv/types.h
+++ b/net/batman-adv/types.h
@@ -193,6 +193,13 @@ struct batadv_hard_iface {
 	/** @rcu: struct used for freeing in an RCU-safe manner */
 	struct rcu_head rcu;
 
+	/**
+	 * @num_bcast_no_urcv: number of neighbor nodes on this interface which
+	 * do not support receiving batman-adv broadcast packets with a
+	 * unicast ethernet frame destination
+	 */
+	atomic_t num_bcast_no_urcv;
+
 	/** @bat_iv: per hard-interface B.A.T.M.A.N. IV data */
 	struct batadv_hard_iface_bat_iv bat_iv;
 
@@ -528,6 +535,13 @@ enum batadv_orig_capabilities {
 	 *  (= orig node announces a tvlv of type BATADV_TVLV_MCAST)
 	 */
 	BATADV_ORIG_CAPA_HAS_MCAST,
+
+	/**
+	 * BATADV_ORIG_CAPA_HAS_BCAST_URCV: orig node is able to receive
+	 * batman-adv broadcast packets with a unicast ethernet frame
+	 * destination
+	 */
+	BATADV_ORIG_CAPA_HAS_BCAST_URCV,
 };
 
 /**
@@ -600,6 +614,13 @@ struct batadv_hardif_neigh_node {
 	/** @last_seen: when last packet via this neighbor was received */
 	unsigned long last_seen;
 
+	/**
+	 * @bcast_has_urcv: a flag indicating whether this neighbor node
+	 * supports receiving batman-adv broadcast packets with a unicast
+	 * ethernet frame destination
+	 */
+	atomic_t bcast_has_urcv;
+
 #ifdef CONFIG_BATMAN_ADV_BATMAN_V
 	/** @bat_v: B.A.T.M.A.N. V private data */
 	struct batadv_hardif_neigh_node_bat_v bat_v;
-- 
2.20.1

Re: [PATCH 2/3] batman-adv: allow broadcast packet type with unicast destination

[Sven Eckelmann]

[-- Attachment #1: Type: text/plain, Size: 963 bytes --]

On Tuesday, 14 May 2019 09:38:58 CEST Linus Lüssing wrote:
> diff --git a/include/uapi/linux/batadv_packet.h b/include/uapi/linux/batadv_packet.h
> index 4ebc2135..2ec59e4a 100644
> --- a/include/uapi/linux/batadv_packet.h
> +++ b/include/uapi/linux/batadv_packet.h
> @@ -164,6 +164,7 @@ enum batadv_bla_claimframe {
>   * @BATADV_TVLV_TT: translation table tvlv
>   * @BATADV_TVLV_ROAM: roaming advertisement tvlv
>   * @BATADV_TVLV_MCAST: multicast capability tvlv
> + * @BATADV_TVLV_BCAST: broadcast capability tvlv
>   */
>  enum batadv_tvlv_type {
>         BATADV_TVLV_GW          = 0x01,
> @@ -172,6 +173,7 @@ enum batadv_tvlv_type {
>         BATADV_TVLV_TT          = 0x04,
>         BATADV_TVLV_ROAM        = 0x05,
>         BATADV_TVLV_MCAST       = 0x06,
> +       BATADV_TVLV_BCAST       = 0x07,
>  };

Please submit the batctl td support for this tvlv. It also looks like the 
mcast tvlv is also missing.

Kind regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH 2/3] batman-adv: allow broadcast packet type with unicast destination

[Sven Eckelmann]

[-- Attachment #1: Type: text/plain, Size: 1638 bytes --]

On Tuesday, 14 May 2019 09:38:58 CEST Linus Lüssing wrote:
[...]
> +/**
> + * batadv_orig_bcast_tvlv_ogm_handler() - process incoming broadcast tvlv
> + * @bat_priv: the bat priv with all the soft interface information
> + * @orig: the orig_node of the ogm
> + * @flags: flags indicating the tvlv state (see batadv_tvlv_handler_flags)
> + * @tvlv_value: tvlv buffer containing the multicast data
> + * @tvlv_value_len: tvlv buffer length
> + */
> +static void batadv_orig_bcast_tvlv_ogm_handler(struct batadv_priv *bat_priv,
> +                                              struct batadv_orig_node *orig,
> +                                              u8 flags,
> +                                              void *tvlv_value,
> +                                              u16 tvlv_value_len)
> +{
> +       if (flags & BATADV_TVLV_HANDLER_OGM_CIFNOTFND)
> +               clear_bit(BATADV_ORIG_CAPA_HAS_BCAST_URCV, &orig->capabilities);
> +       else
> +               set_bit(BATADV_ORIG_CAPA_HAS_BCAST_URCV, &orig->capabilities);
> +}
> +

Bitops require #include <linux/bitops.h>

>  /**
>   * batadv_originator_init() - Initialize all originator structures
>   * @bat_priv: the bat priv with all the soft interface information
> @@ -215,6 +236,12 @@ int batadv_originator_init(struct batadv_priv *bat_priv)
>         batadv_hash_set_lock_class(bat_priv->orig_hash,
>                                    &batadv_orig_hash_lock_class_key);
>  
> +       batadv_tvlv_container_register(bat_priv, BATADV_TVLV_BCAST, 1, NULL, 0);

BATADV_TVLV_BCAST requires #include <uapi/linux/batadv_packet.h>

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH 2/3] batman-adv: allow broadcast packet type with unicast destination

[Sven Eckelmann]

[-- Attachment #1: Type: text/plain, Size: 690 bytes --]

On Tuesday, 14 May 2019 09:38:58 CEST Linus Lüssing wrote:
> +
> +       /**
> +        * BATADV_ORIG_CAPA_HAS_BCAST_URCV: orig node is able to receive
> +        * batman-adv broadcast packets with a unicast ethernet frame
> +        * destination
> +        */
> +       BATADV_ORIG_CAPA_HAS_BCAST_URCV,
>  };

Here is a minor problem with the kerneldoc syntax:

    ./net/batman-adv/types.h:550: warning: Incorrect use of kernel-doc format:          * BATADV_ORIG_CAPA_HAS_BCAST_URCV: orig node is able to receive
    ./net/batman-adv/types.h:555: warning: Enum value 'BATADV_ORIG_CAPA_HAS_BCAST_URCV' not described in enum 'batadv_orig_capabilities'

Kind regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH 3/3] batman-adv: forward broadcast packets via unicast transmissions

[Linus Lüssing]

With the high bitrates of modern wireless devices these days multiple
unicast transmissions are usually less costly than a broadcast
transmission on a low bitrate.

Furthermore unicast transmissions come with the advantage of being
acknowledged and potentially retried automatically, hence with a better
reliability.

The compromise so far was to (re-)transmit a broadcast packet three
times in batman-adv and advise the user to set a higher multicast rate.
However the multicast still needs to be chosen somewhat conservatively
(typically something between 12MBit/s and 24MBit/s are chosen) to ensure
robustness. Which might be too low for some applications.

With this patch a broadcast packet is forwarded on a link via individual
unicast transmissions as long as the number of receivers is smaller or
equal to the configurable multicast fanout (default: 16).

Unicasts are only send to neighboring nodes which are direct
neighbors. So a neighbor node which we see on a link but which has a
better reachability via a multi-hop path will not receive a unicast
transmission.

Furthermore, the broadcast avoidance checks still apply (no echo to
previous sender, no echo to initial originator) to further reduce
unicast transmissions.

Signed-off-by: Linus Lüssing <linus.luessing@c0d3.blue>
---
 net/batman-adv/hard-interface.c |   1 +
 net/batman-adv/routing.c        |  38 ++++++++
 net/batman-adv/send.c           | 156 ++++++++++++++++++++++++++++++++
 net/batman-adv/types.h          |   8 ++
 4 files changed, 203 insertions(+)

diff --git a/net/batman-adv/hard-interface.c b/net/batman-adv/hard-interface.c
index b71d8efc..11864f77 100644
--- a/net/batman-adv/hard-interface.c
+++ b/net/batman-adv/hard-interface.c
@@ -937,6 +937,7 @@ batadv_hardif_add_interface(struct net_device *net_dev)
 
 	batadv_v_hardif_init(hard_iface);
 	atomic_set(&hard_iface->num_bcast_no_urcv, 0);
+	atomic_set(&hard_iface->num_direct_orig, 0);
 
 	batadv_check_known_mac_addr(hard_iface->net_dev);
 	kref_get(&hard_iface->refcount);
diff --git a/net/batman-adv/routing.c b/net/batman-adv/routing.c
index 03b4e609..99a138ae 100644
--- a/net/batman-adv/routing.c
+++ b/net/batman-adv/routing.c
@@ -42,6 +42,40 @@
 static int batadv_route_unicast_packet(struct sk_buff *skb,
 				       struct batadv_hard_iface *recv_if);
 
+/**
+ * batadv_route_update_direct_neigh_count() - update the direct neighbor counter
+ * @oldrouter: the previously selected router
+ * @newrouter: the newly selected router
+ * @orig: the originator (MAC) the router is updated for
+ *
+ * Updates to direct neighbor originator counter of the hard interface the old
+ * and new router belongs to.
+ */
+static void
+batadv_route_update_direct_neigh_count(struct batadv_neigh_node *oldrouter,
+				       struct batadv_neigh_node *newrouter,
+				       u8 *orig)
+{
+	bool oldrouter_is_direct = false;
+	bool newrouter_is_direct = false;
+	u8 *neigh_orig;
+
+	if (oldrouter) {
+		neigh_orig = oldrouter->hardif_neigh->orig;
+		oldrouter_is_direct = batadv_compare_eth(neigh_orig, orig);
+	}
+
+	if (newrouter) {
+		neigh_orig = newrouter->hardif_neigh->orig;
+		newrouter_is_direct = batadv_compare_eth(neigh_orig, orig);
+	}
+
+	if (oldrouter_is_direct && !newrouter_is_direct)
+		atomic_dec(&oldrouter->if_incoming->num_direct_orig);
+	else if (!oldrouter_is_direct && newrouter_is_direct)
+		atomic_inc(&newrouter->if_incoming->num_direct_orig);
+}
+
 /**
  * _batadv_update_route() - set the router for this originator
  * @bat_priv: the bat priv with all the soft interface information
@@ -77,6 +111,10 @@ static void _batadv_update_route(struct batadv_priv *bat_priv,
 	if (neigh_node)
 		kref_get(&neigh_node->refcount);
 
+	if (recv_if == BATADV_IF_DEFAULT)
+		batadv_route_update_direct_neigh_count(curr_router, neigh_node,
+						       orig_node->orig);
+
 	rcu_assign_pointer(orig_ifinfo->router, neigh_node);
 	spin_unlock_bh(&orig_node->neigh_list_lock);
 	batadv_orig_ifinfo_put(orig_ifinfo);
diff --git a/net/batman-adv/send.c b/net/batman-adv/send.c
index 1341b9ac..c83f14b2 100644
--- a/net/batman-adv/send.c
+++ b/net/batman-adv/send.c
@@ -905,6 +905,146 @@ static bool batadv_send_no_broadcast(struct batadv_priv *bat_priv,
 	return true;
 }
 
+/**
+ * batadv_forw_bcast_may_ucast() - check if a broadcast packet can be unicasted
+ * @bat_priv: the bat priv with all the soft interface information
+ * @if_out: the outgoing interface to check for
+ *
+ * Return: True if the number of 1-hop, direct neighbor originators on the given
+ * interface is smaller than or equal to the configured multicast fanout limit
+ * and all neighbor nodes support the reception of batman-adv broadcast
+ * packets with a unicast ethernet frame destination. Otherwise returns false.
+ */
+static bool batadv_forw_bcast_may_ucast(struct batadv_priv *bat_priv,
+					struct batadv_hard_iface *if_out)
+{
+	unsigned long num_direct_orig;
+	unsigned long num_bcast_no_urcv;
+
+	num_direct_orig = atomic_read(&if_out->num_direct_orig);
+	num_bcast_no_urcv = atomic_read(&if_out->num_bcast_no_urcv);
+
+	return !num_bcast_no_urcv &&
+	       (num_direct_orig <= atomic_read(&bat_priv->multicast_fanout));
+}
+
+/**
+ * batadv_forw_bcasts_via_ucasts_check() - check if a neighbor needs a unicast
+ * @bat_priv: the bat priv with all the soft interface information
+ * @skb: broadcast packet to check
+ * @if_out: the outgoing interface to check for
+ * @if_neigh: the neighbor node to check for
+ * @own_packet: true if it is a self-generated broadcast packet
+ *
+ * Return: True if a packet needs to be transmitted to the given neighbor,
+ * false otherwise.
+ */
+static bool
+batadv_forw_bcasts_via_ucasts_check(struct batadv_priv *bat_priv,
+				    struct sk_buff *skb,
+				    struct batadv_hard_iface *if_out,
+				    struct batadv_hardif_neigh_node *if_neigh,
+				    bool own_packet)
+{
+	u8 *bcast_orig = ((struct batadv_bcast_packet *)skb->data)->orig;
+	struct batadv_hardif_neigh_node *neigh_node = NULL;
+	struct batadv_neigh_node *router = NULL;
+	struct batadv_orig_node *orig_node;
+	bool ret = false;
+	u8 *router_addr;
+	u8 *neigh_addr;
+	u8 *orig_neigh;
+
+	if (!own_packet) {
+		neigh_addr = eth_hdr(skb)->h_source;
+		neigh_node = batadv_hardif_neigh_get(if_out,
+						     neigh_addr);
+	}
+
+	orig_neigh = neigh_node ? neigh_node->orig : NULL;
+
+	orig_node = batadv_orig_hash_find(bat_priv, if_neigh->orig);
+	if (orig_node) {
+		router = batadv_orig_router_get(orig_node, BATADV_IF_DEFAULT);
+		router_addr = router ? router->addr : NULL;
+	}
+
+	/* is the originator -> no rebroadcast */
+	if (batadv_compare_eth(if_neigh->orig, bcast_orig)) {
+		goto out;
+	/* is the one we received from -> no rebroadcast */
+	} else if (orig_neigh &&
+		   batadv_compare_eth(if_neigh->orig, orig_neigh)) {
+		goto out;
+	/* only 1-hop, direct neighbor originators */
+	} else if (router && !batadv_compare_eth(router_addr, if_neigh->addr)) {
+		goto out;
+	}
+
+	ret = true;
+out:
+	if (router)
+		batadv_neigh_node_put(router);
+	if (orig_node)
+		batadv_orig_node_put(orig_node);
+	if (neigh_node)
+		batadv_hardif_neigh_put(neigh_node);
+
+	return ret;
+}
+
+/**
+ * batadv_forw_bcast_packet_via_ucasts() - unicast a broadcast packet
+ * @bat_priv: the bat priv with all the soft interface information
+ * @skb: broadcast packet to send
+ * @own_packet: true if it is a self-generated broadcast packet
+ * @if_out: the outgoing interface to forward to
+ *
+ * Forwards a broadcast packet on the specified interface via unicast
+ * transmissions.
+ *
+ * This call clones the given skb, hence the caller needs to take into
+ * account that the data segment of the original skb might not be
+ * modifiable anymore.
+ *
+ * Return: NETDEV_TX_OK on success and NETDEV_TX_BUSY on errors.
+ */
+static int batadv_forw_bcast_via_ucasts(struct batadv_priv *bat_priv,
+					struct sk_buff *skb,
+					bool own_packet,
+					struct batadv_hard_iface *if_out)
+{
+	struct batadv_hardif_neigh_node *hardif_neigh;
+	struct sk_buff *newskb;
+	int ret = NETDEV_TX_OK;
+
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(hardif_neigh, &if_out->neigh_list, list) {
+		if (!kref_get_unless_zero(&hardif_neigh->refcount))
+			continue;
+
+		if (!batadv_forw_bcasts_via_ucasts_check(bat_priv, skb, if_out,
+							 hardif_neigh,
+							 own_packet)) {
+			batadv_hardif_neigh_put(hardif_neigh);
+			continue;
+		}
+
+		newskb = skb_clone(skb, GFP_ATOMIC);
+		if (!newskb) {
+			batadv_hardif_neigh_put(hardif_neigh);
+			ret = NETDEV_TX_BUSY;
+			break;
+		}
+
+		batadv_send_skb_packet(newskb, if_out, hardif_neigh->addr);
+		batadv_hardif_neigh_put(hardif_neigh);
+	}
+	rcu_read_unlock();
+
+	return ret;
+}
+
 /**
  * __batadv_forw_bcast_packet() - forward and queue a broadcast packet
  * @bat_priv: the bat priv with all the soft interface information
@@ -949,6 +1089,22 @@ static int __batadv_forw_bcast_packet(struct batadv_priv *bat_priv,
 			continue;
 		}
 
+		/* try individual unicasts first */
+		if (!delay && batadv_forw_bcast_may_ucast(bat_priv,
+							  hard_iface)) {
+			ret = batadv_forw_bcast_via_ucasts(bat_priv, skb,
+							   own_packet,
+							   hard_iface);
+
+			if (ret == NETDEV_TX_BUSY) {
+				batadv_hardif_put(hard_iface);
+				break;
+			}
+
+			batadv_hardif_put(hard_iface);
+			continue;
+		} /* else: transmit via broadcast */
+
 		ret = batadv_forw_bcast_packet_if(bat_priv, skb, delay,
 						  own_packet, primary_if,
 						  hard_iface);
diff --git a/net/batman-adv/types.h b/net/batman-adv/types.h
index 877a2762..52a51861 100644
--- a/net/batman-adv/types.h
+++ b/net/batman-adv/types.h
@@ -200,6 +200,14 @@ struct batadv_hard_iface {
 	 */
 	atomic_t num_bcast_no_urcv;
 
+	/**
+	 * @num_direct_orig: number of neighboring originators on this
+	 * interface which have a direct, 1-hop path (which is equivalent
+	 * to the number of neighbor nodes on this interface which are a
+	 * selected router)
+	 */
+	atomic_t num_direct_orig;
+
 	/** @bat_iv: per hard-interface B.A.T.M.A.N. IV data */
 	struct batadv_hard_iface_bat_iv bat_iv;
 
-- 
2.20.1

Re: [PATCH 3/3] batman-adv: forward broadcast packets via unicast transmissions

[Sven Eckelmann]

[-- Attachment #1: Type: text/plain, Size: 1473 bytes --]

On Tuesday, 14 May 2019 09:38:59 CEST Linus Lüssing wrote:
> +static bool batadv_forw_bcast_may_ucast(struct batadv_priv *bat_priv,
> +                                       struct batadv_hard_iface *if_out)
> +{
> +       unsigned long num_direct_orig;
> +       unsigned long num_bcast_no_urcv;
> +
> +       num_direct_orig = atomic_read(&if_out->num_direct_orig);
> +       num_bcast_no_urcv = atomic_read(&if_out->num_bcast_no_urcv);
> +
> +       return !num_bcast_no_urcv &&
> +              (num_direct_orig <= atomic_read(&bat_priv->multicast_fanout));
> +}

ecsv/pu|sparse linux-3.16.66 cfg: BLA=y DAT=y DEBUGFS=n DEBUG=y TRACING=y NC=n MCAST=n BATMAN_V=y SYSFS=y|/home/build_test/build_env/tmp.I4uiDZgE1M/net/batman-adv/send.c:928:57: error: no member 'multicast_fanout' in struct batadv_priv
/home/build_test/build_env/tmp.I4uiDZgE1M/net/batman-adv/send.c:928:47: warning: call with no type!
/home/build_test/build_env/tmp.I4uiDZgE1M/net/batman-adv/send.c: In function ‘batadv_forw_bcast_may_ucast’:
/home/build_test/build_env/tmp.I4uiDZgE1M/net/batman-adv/send.c:928:50: error: ‘struct batadv_priv’ has no member named ‘multicast_fanout’
         (num_direct_orig <= atomic_read(&bat_priv->multicast_fanout));
                                                  ^~
/home/build_test/build_env/tmp.I4uiDZgE1M/net/batman-adv/send.c:929:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

Kind regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]