diff mbox series

[v2] batman-adv: Introduce no noflood mark

Message ID 20190507072821.8147-1-linus.luessing@c0d3.blue
State Rejected, archived
Delegated to: Simon Wunderlich
Headers show
Series [v2] batman-adv: Introduce no noflood mark | expand

Commit Message

Linus Lüssing May 7, 2019, 7:28 a.m. UTC
This mark prevents a multicast packet being flooded through the whole
mesh. The advantage of marking certain multicast packets via e.g.
ebtables instead of dropping is then the following:

This allows an administrator to let specific multicast packets pass as
long as they are forwarded to a limited number of nodes only and are
therefore creating no burdon to unrelated nodes.

Signed-off-by: Linus Lüssing <linus.luessing@c0d3.blue>

---

https://www.open-mesh.org/projects/batman-adv/wiki/Noflood-broadcast-prevention

Changelog v2:

* rebased to master
* sysfs -> netlink
---
 include/uapi/linux/batman_adv.h | 12 ++++++++++++
 net/batman-adv/netlink.c        | 22 ++++++++++++++++++++++
 net/batman-adv/soft-interface.c | 20 ++++++++++++++++++++
 net/batman-adv/types.h          | 12 ++++++++++++
 4 files changed, 66 insertions(+)

Comments

Sven Eckelmann May 7, 2019, 7:30 a.m. UTC | #1
On Tuesday, 7 May 2019 09:28:21 CEST Linus Lüssing wrote:
> This mark prevents a multicast packet being flooded through the whole
> mesh. The advantage of marking certain multicast packets via e.g.
> ebtables instead of dropping is then the following:
> 
> This allows an administrator to let specific multicast packets pass as
> long as they are forwarded to a limited number of nodes only and are
> therefore creating no burdon to unrelated nodes.
> 
> Signed-off-by: Linus Lüssing <linus.luessing@c0d3.blue>

I still don't see why this has to be implemented in batman-adv and not as an 
external filter (tc-ebpf or something like that).

Kind regards,
	Sven
Marek Lindner May 7, 2019, 8 a.m. UTC | #2
On Tuesday, 7 May 2019 15:30:46 HKT Sven Eckelmann wrote:
> On Tuesday, 7 May 2019 09:28:21 CEST Linus Lüssing wrote:
> > This mark prevents a multicast packet being flooded through the whole
> > mesh. The advantage of marking certain multicast packets via e.g.
> > ebtables instead of dropping is then the following:
> > 
> > This allows an administrator to let specific multicast packets pass as
> > long as they are forwarded to a limited number of nodes only and are
> > therefore creating no burdon to unrelated nodes.
> > 
> > Signed-off-by: Linus Lüssing <linus.luessing@c0d3.blue>
> 
> I still don't see why this has to be implemented in batman-adv and not as an
> external filter (tc-ebpf or something like that).

As I understand the use-case (Linus correct me if I am wrong): The mark is 
supposed to drop packets that couldn't be $optimized by one of the various 
batman-adv payload traffic optimizations. From outside of batman-adv it would be 
difficult to tell if a broadcast / multicast packet was optimized (think: served 
via DAT cache, sent as unicast, etc) or not.

@Linus: How about making the intention clearer by choosing a better name (for 
example: nobroadcast mark) and introducing proper documentation when and how 
to use this flag ?

Cheers,
Marek
Sven Eckelmann May 7, 2019, 8:21 a.m. UTC | #3
On Tuesday, 7 May 2019 10:00:18 CEST Marek Lindner wrote:
[...]
> > I still don't see why this has to be implemented in batman-adv and not as an
> > external filter (tc-ebpf or something like that).
> 
> As I understand the use-case (Linus correct me if I am wrong): The mark is 
> supposed to drop packets that couldn't be $optimized by one of the various 
> batman-adv payload traffic optimizations. From outside of batman-adv it would be 
> difficult to tell if a broadcast / multicast packet was optimized (think: served 
> via DAT cache, sent as unicast, etc) or not.

It should be easy to see in tc whether a packet is transmitted as unicast or 
broadcast. It is just a bit check in the destination mac. So it would end up 
as a filter somewheere in the hardif tx path which first checks following 
before rejecting a packet:

* is it a multicast/broadcast destination address?

  - maybe this part isn't even necessary - at least the mcast2unicast stuff 
    uses batadv_send_skb_unicast 

* is it a batman-adv packet?
* is is a batman-adv compat 15 broadcast packet?
* does it have the noflood mark?

This would even allow some fancy stuff like rate limiting or per hardif 
behavior. With the problem that there is no package yet which does this in 
gluon.

Or am I missing something essential here which is also done in the 
batadv_interface_tx path?

And why would we see see stuff which as served via DAT? This is usually not 
transmitted on the hardif ports.

Kind regards,
	Sven
Linus Lüssing May 7, 2019, 3:17 p.m. UTC | #4
On Tue, May 07, 2019 at 10:21:40AM +0200, Sven Eckelmann wrote:
> On Tuesday, 7 May 2019 10:00:18 CEST Marek Lindner wrote:
> [...]
> > > I still don't see why this has to be implemented in batman-adv and not as an
> > > external filter (tc-ebpf or something like that).
> > 
> > As I understand the use-case (Linus correct me if I am wrong): The mark is 
> > supposed to drop packets that couldn't be $optimized by one of the various 
> > batman-adv payload traffic optimizations. From outside of batman-adv it would be 
> > difficult to tell if a broadcast / multicast packet was optimized (think: served 
> > via DAT cache, sent as unicast, etc) or not.
> 
> It should be easy to see in tc whether a packet is transmitted as unicast or 
> broadcast. It is just a bit check in the destination mac. So it would end up 
> as a filter somewheere in the hardif tx path which first checks following 
> before rejecting a packet:
> 
> * is it a multicast/broadcast destination address?
> 
>   - maybe this part isn't even necessary - at least the mcast2unicast stuff 
>     uses batadv_send_skb_unicast 
> 
> * is it a batman-adv packet?
> * is is a batman-adv compat 15 broadcast packet?
> * does it have the noflood mark?
> 
> This would even allow some fancy stuff like rate limiting or per hardif 
> behavior. With the problem that there is no package yet which does this in 
> gluon.

Ah, that's an interesting idea. So basically filtering on the
hardif instead of in batman-adv via some custom compiled BPF
filters. So basically similar to writing a small program like the
gluon-radv-filterd with a BPF_* parser?

https://github.com/freifunk-gluon/gluon/blob/master/package/gluon-radv-filterd/src/gluon-radv-filterd.c#L223

> Or am I missing something essential here which is also done in the 
> batadv_interface_tx path?

Hm, I guess functionally this would be mostly equivalent. Maybe
except a bit of performance due to our custom queueing
infrastructure. Not sure how much performance it would cost on our
small MIPS devices if a client were sending a few MBit/s of UDP
multicast through our batadv_add_bcast_packet_to_list()
infrastructure.

The noflood-mark would drop the packet early on in batadv_interface_tx(),
before any queueing or copying happens.

Maybe more importantly even before the bcast_packet->seqno is
increased. It could become an issue if a node were increasing it's
seqno quickly without other nodes noticing the new seqnos.
Broadcast packets we actually let through might then be received
with a seqno outside of the seqno window on the receiving nodes.

> And why would we see see stuff which as served via DAT? This is usually not 
> transmitted on the hardif ports.

I guess Marek ment it the other way round (see his "or not" at the
end of his sentence).

Regards, Linus
Linus Lüssing May 7, 2019, 3:34 p.m. UTC | #5
On Tue, May 07, 2019 at 05:17:23PM +0200, Linus Lüssing wrote:
> > This would even allow some fancy stuff like rate limiting or per hardif 
> > behavior. With the problem that there is no package yet which does this in 
> > gluon.
> 
> Ah, that's an interesting idea. So basically filtering on the
> hardif instead of in batman-adv via some custom compiled BPF
> filters. So basically similar to writing a small program like the
> gluon-radv-filterd with a BPF_* parser?
> 
> https://github.com/freifunk-gluon/gluon/blob/master/package/gluon-radv-filterd/src/gluon-radv-filterd.c#L223

And usability is of course different. Compared to writing a BPF
program it would just be an extra line in the firewall like here:

https://github.com/freifunk-gluon/gluon/pull/1357/files#diff-adbff50d8f3994ffbbac77f580ace41e

And setting the noflood_mark in batman-adv:

https://github.com/freifunk-gluon/gluon/pull/1357/files#diff-89c09eae71234dcaa46a6137d796048b

Also, we would not only need to package it for Gluon then but also
various Linux distributions used on gateways, I guess. To further
reduce the ARP broadcasts for vanished clients on gateways, for instance
(the second use-case).


Btw., I think rate-limiting would already be possible. We could
set the mark in a rate-limited fashion incoming on bat0 with
ebtables for instance.

Which could be useful to simplify gluon-ebtables-arp-limiter [0] a
bit. Currently there's a loop over the "batctl dat_cache" table
to add an exception to rate-limiting for addresses available in
the cache.

Regards, Linus


[0]: https://github.com/freifunk-gluon/gluon/tree/master/package/gluon-ebtables-limit-arp
Sven Eckelmann May 7, 2019, 3:45 p.m. UTC | #6
On Tuesday, 7 May 2019 17:17:23 CEST Linus Lüssing wrote:
> Ah, that's an interesting idea. So basically filtering on the
> hardif instead of in batman-adv via some custom compiled BPF
> filters. So basically similar to writing a small program like the
> gluon-radv-filterd with a BPF_* parser?
> 
> https://github.com/freifunk-gluon/gluon/blob/master/package/gluon-radv-filterd/src/gluon-radv-filterd.c#L223

Yes, but you don't have to write the stuff with these intrinsics and cBPF.
This was done in gluon-radv-filterd only to avoid extra dependencies to 
build the program for this really minimal piece of code.
And I didn't had much benefits from using eBPF at the moment [1].

You can just write it in C and use clang to create (e)BPF bytecode as 
described in http://man7.org/linux/man-pages/man8/tc-bpf.8.html

Kind regards,
	Sven

[1] https://github.com/freifunk-gluon/gluon/pull/838#issuecomment-355547594
Linus Lüssing May 14, 2019, 8:19 a.m. UTC | #7
On Tue, May 07, 2019 at 05:17:23PM +0200, Linus Lüssing wrote:
> Maybe more importantly even before the bcast_packet->seqno is
> increased. It could become an issue if a node were increasing it's
> seqno quickly without other nodes noticing the new seqnos.
> Broadcast packets we actually let through might then be received
> with a seqno outside of the seqno window on the receiving nodes.

Hm, what do others think about this? If I'm not mistaken then we
currently have three places to consider, which would be affected
by high packet rate multicast:

1) Sender, batadv_forw_packet_alloc() in batadv_add_bcast_packet_to_list():
   -> BATADV_BCAST_QUEUE_LEN = 256

2) Receiver, batadv_test_bit() in batadv_recv_bcast_packet():
   -> BATADV_TQ_LOCAL_WINDOW_SIZE = 64 -> duplicate detection

3) Receiver, batadv_window_protected() in batadv_recv_bcast_packet():
   -> BATADV_EXPECTED_SEQNO_RANGE = 65536


I did some rough estimations with a 5Mbit/s multicast stream
(typical bitrate of a 720p video), quantified to 1250 byte
packets on a piece of paper. It seems ok-ish for the three cases
above, but also seems to get in a range I would start feeling
uncomfortable.

Dropping early via noflood instead of dropping later on the
hard-interfaces via BPF would avoid taking up queueing space and
sequence numbers.

(And I think the queueing onto the kworker also creates quite a
bit of load. At least something like that was my experience on
a Raspberry Pi One with a USB wifi dongle which used a driver
that queued everything onto the kworker, the kworker was
always very busy and never made it above 10-15MBit/s if I remember
correctly [1].)


[1]: https://wikidevi.com/wiki/TP-LINK_TL-WDN4200
diff mbox series

Patch

diff --git a/include/uapi/linux/batman_adv.h b/include/uapi/linux/batman_adv.h
index 67f46367..6fabb7aa 100644
--- a/include/uapi/linux/batman_adv.h
+++ b/include/uapi/linux/batman_adv.h
@@ -480,6 +480,18 @@  enum batadv_nl_attrs {
 	 */
 	BATADV_ATTR_MULTICAST_FANOUT,
 
+	/**
+	 * @BATADV_ATTR_NOFLOOD_MARK: the noflood mark which allows to tag
+	 *  frames which should never be broadcast flooded through the mesh.
+	 */
+	BATADV_ATTR_NOFLOOD_MARK,
+
+	/**
+	 * @BATADV_ATTR_NOFLOOD_MASK: the noflood (bit)mask which allows to tag
+	 *  frames which should never be broadcast flooded through the mesh.
+	 */
+	BATADV_ATTR_NOFLOOD_MASK,
+
 	/* add attributes above here, update the policy in netlink.c */
 
 	/**
diff --git a/net/batman-adv/netlink.c b/net/batman-adv/netlink.c
index a67720fa..a08a67af 100644
--- a/net/batman-adv/netlink.c
+++ b/net/batman-adv/netlink.c
@@ -134,6 +134,8 @@  static const struct nla_policy batadv_netlink_policy[NUM_BATADV_ATTR] = {
 	[BATADV_ATTR_AP_ISOLATION_ENABLED]	= { .type = NLA_U8 },
 	[BATADV_ATTR_ISOLATION_MARK]		= { .type = NLA_U32 },
 	[BATADV_ATTR_ISOLATION_MASK]		= { .type = NLA_U32 },
+	[BATADV_ATTR_NOFLOOD_MARK]		= { .type = NLA_U32 },
+	[BATADV_ATTR_NOFLOOD_MASK]		= { .type = NLA_U32 },
 	[BATADV_ATTR_BONDING_ENABLED]		= { .type = NLA_U8 },
 	[BATADV_ATTR_BRIDGE_LOOP_AVOIDANCE_ENABLED]	= { .type = NLA_U8 },
 	[BATADV_ATTR_DISTRIBUTED_ARP_TABLE_ENABLED]	= { .type = NLA_U8 },
@@ -286,6 +288,14 @@  static int batadv_netlink_mesh_fill(struct sk_buff *msg,
 			bat_priv->isolation_mark_mask))
 		goto nla_put_failure;
 
+	if (nla_put_u32(msg, BATADV_ATTR_NOFLOOD_MARK,
+			bat_priv->noflood_mark))
+		goto nla_put_failure;
+
+	if (nla_put_u32(msg, BATADV_ATTR_NOFLOOD_MASK,
+			bat_priv->noflood_mark_mask))
+		goto nla_put_failure;
+
 	if (nla_put_u8(msg, BATADV_ATTR_BONDING_ENABLED,
 		       !!atomic_read(&bat_priv->bonding)))
 		goto nla_put_failure;
@@ -466,6 +476,18 @@  static int batadv_netlink_set_mesh(struct sk_buff *skb, struct genl_info *info)
 		bat_priv->isolation_mark_mask = nla_get_u32(attr);
 	}
 
+	if (info->attrs[BATADV_ATTR_NOFLOOD_MARK]) {
+		attr = info->attrs[BATADV_ATTR_NOFLOOD_MARK];
+
+		bat_priv->noflood_mark = nla_get_u32(attr);
+	}
+
+	if (info->attrs[BATADV_ATTR_NOFLOOD_MASK]) {
+		attr = info->attrs[BATADV_ATTR_NOFLOOD_MASK];
+
+		bat_priv->noflood_mark_mask = nla_get_u32(attr);
+	}
+
 	if (info->attrs[BATADV_ATTR_BONDING_ENABLED]) {
 		attr = info->attrs[BATADV_ATTR_BONDING_ENABLED];
 
diff --git a/net/batman-adv/soft-interface.c b/net/batman-adv/soft-interface.c
index a7677e1d..6912f651 100644
--- a/net/batman-adv/soft-interface.c
+++ b/net/batman-adv/soft-interface.c
@@ -176,6 +176,23 @@  static void batadv_interface_set_rx_mode(struct net_device *dev)
 {
 }
 
+/**
+ * batadv_send_skb_has_noflood_mark() - check if packet has a noflood mark
+ * @bat_priv: the bat priv with all the soft interface information
+ * @skb: the packet to check
+ *
+ * Return: True if the skb's mark matches a configured noflood mark and
+ * noflood mark mask. False otherwise.
+ */
+static bool
+batadv_skb_has_noflood_mark(struct batadv_priv *bat_priv, struct sk_buff *skb)
+{
+	u32 match_mark = skb->mark & bat_priv->noflood_mark_mask;
+
+	return bat_priv->noflood_mark_mask &&
+	       match_mark == bat_priv->noflood_mark;
+}
+
 static netdev_tx_t batadv_interface_tx(struct sk_buff *skb,
 				       struct net_device *soft_iface)
 {
@@ -326,6 +343,9 @@  static netdev_tx_t batadv_interface_tx(struct sk_buff *skb,
 		if (batadv_dat_snoop_outgoing_arp_request(bat_priv, skb))
 			brd_delay = msecs_to_jiffies(ARP_REQ_DELAY);
 
+		if (batadv_skb_has_noflood_mark(bat_priv, skb))
+			goto dropped;
+
 		if (batadv_skb_head_push(skb, sizeof(*bcast_packet)) < 0)
 			goto dropped;
 
diff --git a/net/batman-adv/types.h b/net/batman-adv/types.h
index 74b64473..325a41a8 100644
--- a/net/batman-adv/types.h
+++ b/net/batman-adv/types.h
@@ -1592,6 +1592,18 @@  struct batadv_priv {
 	 */
 	u32 isolation_mark_mask;
 
+	/**
+	 * @noflood_mark: the skb->mark value used to allow directed targeting
+	 *  only
+	 */
+	u32 noflood_mark;
+
+	/**
+	 * @noflood_mark_mask: bitmask identifying the bits in skb->mark to be
+	 *  used for the noflood mark
+	 */
+	u32 noflood_mark_mask;
+
 	/** @bcast_seqno: last sent broadcast packet sequence number */
 	atomic_t bcast_seqno;