1 // SPDX-License-Identifier: GPL-2.0-or-later
2 // Copyright (c) 2020, Nikolay Aleksandrov <nikolay@nvidia.com>
4 #include <linux/export.h>
5 #include <linux/if_ether.h>
6 #include <linux/igmp.h>
8 #include <linux/jhash.h>
9 #include <linux/kernel.h>
10 #include <linux/log2.h>
11 #include <linux/netdevice.h>
12 #include <linux/netfilter_bridge.h>
13 #include <linux/random.h>
14 #include <linux/rculist.h>
15 #include <linux/skbuff.h>
16 #include <linux/slab.h>
17 #include <linux/timer.h>
18 #include <linux/inetdevice.h>
19 #include <linux/mroute.h>
21 #include <net/switchdev.h>
22 #if IS_ENABLED(CONFIG_IPV6)
23 #include <linux/icmpv6.h>
26 #include <net/ip6_checksum.h>
27 #include <net/addrconf.h>
30 #include "br_private.h"
31 #include "br_private_mcast_eht.h"
33 static bool br_multicast_del_eht_set_entry(struct net_bridge_port_group *pg,
34 union net_bridge_eht_addr *src_addr,
35 union net_bridge_eht_addr *h_addr);
36 static void br_multicast_create_eht_set_entry(struct net_bridge_port_group *pg,
37 union net_bridge_eht_addr *src_addr,
38 union net_bridge_eht_addr *h_addr,
42 static struct net_bridge_group_eht_host *
43 br_multicast_eht_host_lookup(struct net_bridge_port_group *pg,
44 union net_bridge_eht_addr *h_addr)
46 struct rb_node *node = pg->eht_host_tree.rb_node;
49 struct net_bridge_group_eht_host *this;
52 this = rb_entry(node, struct net_bridge_group_eht_host,
54 result = memcmp(h_addr, &this->h_addr, sizeof(*h_addr));
58 node = node->rb_right;
66 static int br_multicast_eht_host_filter_mode(struct net_bridge_port_group *pg,
67 union net_bridge_eht_addr *h_addr)
69 struct net_bridge_group_eht_host *eht_host;
71 eht_host = br_multicast_eht_host_lookup(pg, h_addr);
75 return eht_host->filter_mode;
78 static struct net_bridge_group_eht_set_entry *
79 br_multicast_eht_set_entry_lookup(struct net_bridge_group_eht_set *eht_set,
80 union net_bridge_eht_addr *h_addr)
82 struct rb_node *node = eht_set->entry_tree.rb_node;
85 struct net_bridge_group_eht_set_entry *this;
88 this = rb_entry(node, struct net_bridge_group_eht_set_entry,
90 result = memcmp(h_addr, &this->h_addr, sizeof(*h_addr));
94 node = node->rb_right;
102 static struct net_bridge_group_eht_set *
103 br_multicast_eht_set_lookup(struct net_bridge_port_group *pg,
104 union net_bridge_eht_addr *src_addr)
106 struct rb_node *node = pg->eht_set_tree.rb_node;
109 struct net_bridge_group_eht_set *this;
112 this = rb_entry(node, struct net_bridge_group_eht_set,
114 result = memcmp(src_addr, &this->src_addr, sizeof(*src_addr));
116 node = node->rb_left;
118 node = node->rb_right;
126 static void __eht_destroy_host(struct net_bridge_group_eht_host *eht_host)
128 WARN_ON(!hlist_empty(&eht_host->set_entries));
130 br_multicast_eht_hosts_dec(eht_host->pg);
132 rb_erase(&eht_host->rb_node, &eht_host->pg->eht_host_tree);
133 RB_CLEAR_NODE(&eht_host->rb_node);
137 static void br_multicast_destroy_eht_set_entry(struct net_bridge_mcast_gc *gc)
139 struct net_bridge_group_eht_set_entry *set_h;
141 set_h = container_of(gc, struct net_bridge_group_eht_set_entry, mcast_gc);
142 WARN_ON(!RB_EMPTY_NODE(&set_h->rb_node));
144 del_timer_sync(&set_h->timer);
148 static void br_multicast_destroy_eht_set(struct net_bridge_mcast_gc *gc)
150 struct net_bridge_group_eht_set *eht_set;
152 eht_set = container_of(gc, struct net_bridge_group_eht_set, mcast_gc);
153 WARN_ON(!RB_EMPTY_NODE(&eht_set->rb_node));
154 WARN_ON(!RB_EMPTY_ROOT(&eht_set->entry_tree));
156 del_timer_sync(&eht_set->timer);
160 static void __eht_del_set_entry(struct net_bridge_group_eht_set_entry *set_h)
162 struct net_bridge_group_eht_host *eht_host = set_h->h_parent;
163 union net_bridge_eht_addr zero_addr;
165 rb_erase(&set_h->rb_node, &set_h->eht_set->entry_tree);
166 RB_CLEAR_NODE(&set_h->rb_node);
167 hlist_del_init(&set_h->host_list);
168 memset(&zero_addr, 0, sizeof(zero_addr));
169 if (memcmp(&set_h->h_addr, &zero_addr, sizeof(zero_addr)))
170 eht_host->num_entries--;
171 hlist_add_head(&set_h->mcast_gc.gc_node, &set_h->br->mcast_gc_list);
172 queue_work(system_long_wq, &set_h->br->mcast_gc_work);
174 if (hlist_empty(&eht_host->set_entries))
175 __eht_destroy_host(eht_host);
178 static void br_multicast_del_eht_set(struct net_bridge_group_eht_set *eht_set)
180 struct net_bridge_group_eht_set_entry *set_h;
181 struct rb_node *node;
183 while ((node = rb_first(&eht_set->entry_tree))) {
184 set_h = rb_entry(node, struct net_bridge_group_eht_set_entry,
186 __eht_del_set_entry(set_h);
189 rb_erase(&eht_set->rb_node, &eht_set->pg->eht_set_tree);
190 RB_CLEAR_NODE(&eht_set->rb_node);
191 hlist_add_head(&eht_set->mcast_gc.gc_node, &eht_set->br->mcast_gc_list);
192 queue_work(system_long_wq, &eht_set->br->mcast_gc_work);
195 void br_multicast_eht_clean_sets(struct net_bridge_port_group *pg)
197 struct net_bridge_group_eht_set *eht_set;
198 struct rb_node *node;
200 while ((node = rb_first(&pg->eht_set_tree))) {
201 eht_set = rb_entry(node, struct net_bridge_group_eht_set,
203 br_multicast_del_eht_set(eht_set);
207 static void br_multicast_eht_set_entry_expired(struct timer_list *t)
209 struct net_bridge_group_eht_set_entry *set_h = from_timer(set_h, t, timer);
210 struct net_bridge *br = set_h->br;
212 spin_lock(&br->multicast_lock);
213 if (RB_EMPTY_NODE(&set_h->rb_node) || timer_pending(&set_h->timer))
216 br_multicast_del_eht_set_entry(set_h->eht_set->pg,
217 &set_h->eht_set->src_addr,
220 spin_unlock(&br->multicast_lock);
223 static void br_multicast_eht_set_expired(struct timer_list *t)
225 struct net_bridge_group_eht_set *eht_set = from_timer(eht_set, t,
227 struct net_bridge *br = eht_set->br;
229 spin_lock(&br->multicast_lock);
230 if (RB_EMPTY_NODE(&eht_set->rb_node) || timer_pending(&eht_set->timer))
233 br_multicast_del_eht_set(eht_set);
235 spin_unlock(&br->multicast_lock);
238 static struct net_bridge_group_eht_host *
239 __eht_lookup_create_host(struct net_bridge_port_group *pg,
240 union net_bridge_eht_addr *h_addr,
241 unsigned char filter_mode)
243 struct rb_node **link = &pg->eht_host_tree.rb_node, *parent = NULL;
244 struct net_bridge_group_eht_host *eht_host;
247 struct net_bridge_group_eht_host *this;
250 this = rb_entry(*link, struct net_bridge_group_eht_host,
252 result = memcmp(h_addr, &this->h_addr, sizeof(*h_addr));
255 link = &((*link)->rb_left);
257 link = &((*link)->rb_right);
262 if (br_multicast_eht_hosts_over_limit(pg))
265 eht_host = kzalloc(sizeof(*eht_host), GFP_ATOMIC);
269 memcpy(&eht_host->h_addr, h_addr, sizeof(*h_addr));
270 INIT_HLIST_HEAD(&eht_host->set_entries);
272 eht_host->filter_mode = filter_mode;
274 rb_link_node(&eht_host->rb_node, parent, link);
275 rb_insert_color(&eht_host->rb_node, &pg->eht_host_tree);
277 br_multicast_eht_hosts_inc(pg);
282 static struct net_bridge_group_eht_set_entry *
283 __eht_lookup_create_set_entry(struct net_bridge *br,
284 struct net_bridge_group_eht_set *eht_set,
285 struct net_bridge_group_eht_host *eht_host,
288 struct rb_node **link = &eht_set->entry_tree.rb_node, *parent = NULL;
289 struct net_bridge_group_eht_set_entry *set_h;
292 struct net_bridge_group_eht_set_entry *this;
295 this = rb_entry(*link, struct net_bridge_group_eht_set_entry,
297 result = memcmp(&eht_host->h_addr, &this->h_addr,
298 sizeof(union net_bridge_eht_addr));
301 link = &((*link)->rb_left);
303 link = &((*link)->rb_right);
308 /* always allow auto-created zero entry */
309 if (!allow_zero_src && eht_host->num_entries >= PG_SRC_ENT_LIMIT)
312 set_h = kzalloc(sizeof(*set_h), GFP_ATOMIC);
316 memcpy(&set_h->h_addr, &eht_host->h_addr,
317 sizeof(union net_bridge_eht_addr));
318 set_h->mcast_gc.destroy = br_multicast_destroy_eht_set_entry;
319 set_h->eht_set = eht_set;
320 set_h->h_parent = eht_host;
322 timer_setup(&set_h->timer, br_multicast_eht_set_entry_expired, 0);
324 hlist_add_head(&set_h->host_list, &eht_host->set_entries);
325 rb_link_node(&set_h->rb_node, parent, link);
326 rb_insert_color(&set_h->rb_node, &eht_set->entry_tree);
327 /* we must not count the auto-created zero entry otherwise we won't be
328 * able to track the full list of PG_SRC_ENT_LIMIT entries
331 eht_host->num_entries++;
336 static struct net_bridge_group_eht_set *
337 __eht_lookup_create_set(struct net_bridge_port_group *pg,
338 union net_bridge_eht_addr *src_addr)
340 struct rb_node **link = &pg->eht_set_tree.rb_node, *parent = NULL;
341 struct net_bridge_group_eht_set *eht_set;
344 struct net_bridge_group_eht_set *this;
347 this = rb_entry(*link, struct net_bridge_group_eht_set,
349 result = memcmp(src_addr, &this->src_addr, sizeof(*src_addr));
352 link = &((*link)->rb_left);
354 link = &((*link)->rb_right);
359 eht_set = kzalloc(sizeof(*eht_set), GFP_ATOMIC);
363 memcpy(&eht_set->src_addr, src_addr, sizeof(*src_addr));
364 eht_set->mcast_gc.destroy = br_multicast_destroy_eht_set;
366 eht_set->br = pg->key.port->br;
367 eht_set->entry_tree = RB_ROOT;
368 timer_setup(&eht_set->timer, br_multicast_eht_set_expired, 0);
370 rb_link_node(&eht_set->rb_node, parent, link);
371 rb_insert_color(&eht_set->rb_node, &pg->eht_set_tree);
376 static void br_multicast_ip_src_to_eht_addr(const struct br_ip *src,
377 union net_bridge_eht_addr *dest)
379 switch (src->proto) {
380 case htons(ETH_P_IP):
381 dest->ip4 = src->src.ip4;
383 #if IS_ENABLED(CONFIG_IPV6)
384 case htons(ETH_P_IPV6):
385 memcpy(&dest->ip6, &src->src.ip6, sizeof(struct in6_addr));
391 static void br_eht_convert_host_filter_mode(struct net_bridge_port_group *pg,
392 union net_bridge_eht_addr *h_addr,
395 struct net_bridge_group_eht_host *eht_host;
396 union net_bridge_eht_addr zero_addr;
398 eht_host = br_multicast_eht_host_lookup(pg, h_addr);
400 eht_host->filter_mode = filter_mode;
402 memset(&zero_addr, 0, sizeof(zero_addr));
403 switch (filter_mode) {
405 br_multicast_del_eht_set_entry(pg, &zero_addr, h_addr);
408 br_multicast_create_eht_set_entry(pg, &zero_addr, h_addr,
415 static void br_multicast_create_eht_set_entry(struct net_bridge_port_group *pg,
416 union net_bridge_eht_addr *src_addr,
417 union net_bridge_eht_addr *h_addr,
421 struct net_bridge_group_eht_set_entry *set_h;
422 struct net_bridge_group_eht_host *eht_host;
423 struct net_bridge *br = pg->key.port->br;
424 struct net_bridge_group_eht_set *eht_set;
425 union net_bridge_eht_addr zero_addr;
427 memset(&zero_addr, 0, sizeof(zero_addr));
428 if (!allow_zero_src && !memcmp(src_addr, &zero_addr, sizeof(zero_addr)))
431 eht_set = __eht_lookup_create_set(pg, src_addr);
435 eht_host = __eht_lookup_create_host(pg, h_addr, filter_mode);
439 set_h = __eht_lookup_create_set_entry(br, eht_set, eht_host,
444 mod_timer(&set_h->timer, jiffies + br_multicast_gmi(br));
445 mod_timer(&eht_set->timer, jiffies + br_multicast_gmi(br));
450 if (hlist_empty(&eht_host->set_entries))
451 __eht_destroy_host(eht_host);
453 if (RB_EMPTY_ROOT(&eht_set->entry_tree))
454 br_multicast_del_eht_set(eht_set);
457 static bool br_multicast_del_eht_set_entry(struct net_bridge_port_group *pg,
458 union net_bridge_eht_addr *src_addr,
459 union net_bridge_eht_addr *h_addr)
461 struct net_bridge_group_eht_set_entry *set_h;
462 struct net_bridge_group_eht_set *eht_set;
463 bool set_deleted = false;
465 eht_set = br_multicast_eht_set_lookup(pg, src_addr);
469 set_h = br_multicast_eht_set_entry_lookup(eht_set, h_addr);
473 __eht_del_set_entry(set_h);
475 if (RB_EMPTY_ROOT(&eht_set->entry_tree)) {
476 br_multicast_del_eht_set(eht_set);
484 static void br_multicast_del_eht_host(struct net_bridge_port_group *pg,
485 union net_bridge_eht_addr *h_addr)
487 struct net_bridge_group_eht_set_entry *set_h;
488 struct net_bridge_group_eht_host *eht_host;
489 struct hlist_node *tmp;
491 eht_host = br_multicast_eht_host_lookup(pg, h_addr);
495 hlist_for_each_entry_safe(set_h, tmp, &eht_host->set_entries, host_list)
496 br_multicast_del_eht_set_entry(set_h->eht_set->pg,
497 &set_h->eht_set->src_addr,
501 /* create new set entries from reports */
502 static void __eht_create_set_entries(struct net_bridge_port_group *pg,
503 union net_bridge_eht_addr *h_addr,
509 union net_bridge_eht_addr eht_src_addr;
512 memset(&eht_src_addr, 0, sizeof(eht_src_addr));
513 for (src_idx = 0; src_idx < nsrcs; src_idx++) {
514 memcpy(&eht_src_addr, srcs + (src_idx * addr_size), addr_size);
515 br_multicast_create_eht_set_entry(pg, &eht_src_addr, h_addr,
521 /* delete existing set entries and their (S,G) entries if they were the last */
522 static bool __eht_del_set_entries(struct net_bridge_port_group *pg,
523 union net_bridge_eht_addr *h_addr,
528 union net_bridge_eht_addr eht_src_addr;
529 struct net_bridge_group_src *src_ent;
530 bool changed = false;
534 memset(&eht_src_addr, 0, sizeof(eht_src_addr));
535 memset(&src_ip, 0, sizeof(src_ip));
536 src_ip.proto = pg->key.addr.proto;
537 for (src_idx = 0; src_idx < nsrcs; src_idx++) {
538 memcpy(&eht_src_addr, srcs + (src_idx * addr_size), addr_size);
539 if (!br_multicast_del_eht_set_entry(pg, &eht_src_addr, h_addr))
541 memcpy(&src_ip, srcs + (src_idx * addr_size), addr_size);
542 src_ent = br_multicast_find_group_src(pg, &src_ip);
545 br_multicast_del_group_src(src_ent, true);
552 static bool br_multicast_eht_allow(struct net_bridge_port_group *pg,
553 union net_bridge_eht_addr *h_addr,
558 bool changed = false;
560 switch (br_multicast_eht_host_filter_mode(pg, h_addr)) {
562 __eht_create_set_entries(pg, h_addr, srcs, nsrcs, addr_size,
566 changed = __eht_del_set_entries(pg, h_addr, srcs, nsrcs,
574 static bool br_multicast_eht_block(struct net_bridge_port_group *pg,
575 union net_bridge_eht_addr *h_addr,
580 bool changed = false;
582 switch (br_multicast_eht_host_filter_mode(pg, h_addr)) {
584 changed = __eht_del_set_entries(pg, h_addr, srcs, nsrcs,
588 __eht_create_set_entries(pg, h_addr, srcs, nsrcs, addr_size,
596 /* flush_entries is true when changing mode */
597 static bool __eht_inc_exc(struct net_bridge_port_group *pg,
598 union net_bridge_eht_addr *h_addr,
602 unsigned char filter_mode,
605 bool changed = false, flush_entries = to_report;
606 union net_bridge_eht_addr eht_src_addr;
608 if (br_multicast_eht_host_filter_mode(pg, h_addr) != filter_mode)
609 flush_entries = true;
611 memset(&eht_src_addr, 0, sizeof(eht_src_addr));
612 /* if we're changing mode del host and its entries */
614 br_multicast_del_eht_host(pg, h_addr);
615 __eht_create_set_entries(pg, h_addr, srcs, nsrcs, addr_size,
617 /* we can be missing sets only if we've deleted some entries */
619 struct net_bridge *br = pg->key.port->br;
620 struct net_bridge_group_eht_set *eht_set;
621 struct net_bridge_group_src *src_ent;
622 struct hlist_node *tmp;
624 hlist_for_each_entry_safe(src_ent, tmp, &pg->src_list, node) {
625 br_multicast_ip_src_to_eht_addr(&src_ent->addr,
627 if (!br_multicast_eht_set_lookup(pg, &eht_src_addr)) {
628 br_multicast_del_group_src(src_ent, true);
632 /* this is an optimization for TO_INCLUDE where we lower
633 * the set's timeout to LMQT to catch timeout hosts:
634 * - host A (timing out): set entries X, Y
635 * - host B: set entry Z (new from current TO_INCLUDE)
636 * sends BLOCK Z after LMQT but host A's EHT
637 * entries still exist (unless lowered to LMQT
638 * so they can timeout with the S,Gs)
639 * => we wait another LMQT, when we can just delete the
642 if (!(src_ent->flags & BR_SGRP_F_SEND) ||
643 filter_mode != MCAST_INCLUDE ||
646 eht_set = br_multicast_eht_set_lookup(pg,
650 mod_timer(&eht_set->timer, jiffies + br_multicast_lmqt(br));
657 static bool br_multicast_eht_inc(struct net_bridge_port_group *pg,
658 union net_bridge_eht_addr *h_addr,
666 changed = __eht_inc_exc(pg, h_addr, srcs, nsrcs, addr_size,
667 MCAST_INCLUDE, to_report);
668 br_eht_convert_host_filter_mode(pg, h_addr, MCAST_INCLUDE);
673 static bool br_multicast_eht_exc(struct net_bridge_port_group *pg,
674 union net_bridge_eht_addr *h_addr,
682 changed = __eht_inc_exc(pg, h_addr, srcs, nsrcs, addr_size,
683 MCAST_EXCLUDE, to_report);
684 br_eht_convert_host_filter_mode(pg, h_addr, MCAST_EXCLUDE);
689 static bool __eht_ip4_handle(struct net_bridge_port_group *pg,
690 union net_bridge_eht_addr *h_addr,
695 bool changed = false, to_report = false;
698 case IGMPV3_ALLOW_NEW_SOURCES:
699 br_multicast_eht_allow(pg, h_addr, srcs, nsrcs, sizeof(__be32));
701 case IGMPV3_BLOCK_OLD_SOURCES:
702 changed = br_multicast_eht_block(pg, h_addr, srcs, nsrcs,
705 case IGMPV3_CHANGE_TO_INCLUDE:
708 case IGMPV3_MODE_IS_INCLUDE:
709 changed = br_multicast_eht_inc(pg, h_addr, srcs, nsrcs,
710 sizeof(__be32), to_report);
712 case IGMPV3_CHANGE_TO_EXCLUDE:
715 case IGMPV3_MODE_IS_EXCLUDE:
716 changed = br_multicast_eht_exc(pg, h_addr, srcs, nsrcs,
717 sizeof(__be32), to_report);
724 #if IS_ENABLED(CONFIG_IPV6)
725 static bool __eht_ip6_handle(struct net_bridge_port_group *pg,
726 union net_bridge_eht_addr *h_addr,
731 bool changed = false, to_report = false;
734 case MLD2_ALLOW_NEW_SOURCES:
735 br_multicast_eht_allow(pg, h_addr, srcs, nsrcs,
736 sizeof(struct in6_addr));
738 case MLD2_BLOCK_OLD_SOURCES:
739 changed = br_multicast_eht_block(pg, h_addr, srcs, nsrcs,
740 sizeof(struct in6_addr));
742 case MLD2_CHANGE_TO_INCLUDE:
745 case MLD2_MODE_IS_INCLUDE:
746 changed = br_multicast_eht_inc(pg, h_addr, srcs, nsrcs,
747 sizeof(struct in6_addr),
750 case MLD2_CHANGE_TO_EXCLUDE:
753 case MLD2_MODE_IS_EXCLUDE:
754 changed = br_multicast_eht_exc(pg, h_addr, srcs, nsrcs,
755 sizeof(struct in6_addr),
764 /* true means an entry was deleted */
765 bool br_multicast_eht_handle(struct net_bridge_port_group *pg,
772 bool eht_enabled = !!(pg->key.port->flags & BR_MULTICAST_FAST_LEAVE);
773 union net_bridge_eht_addr eht_host_addr;
774 bool changed = false;
779 memset(&eht_host_addr, 0, sizeof(eht_host_addr));
780 memcpy(&eht_host_addr, h_addr, addr_size);
781 if (addr_size == sizeof(__be32))
782 changed = __eht_ip4_handle(pg, &eht_host_addr, srcs, nsrcs,
784 #if IS_ENABLED(CONFIG_IPV6)
786 changed = __eht_ip6_handle(pg, &eht_host_addr, srcs, nsrcs,
794 int br_multicast_eht_set_hosts_limit(struct net_bridge_port *p,
797 struct net_bridge *br = p->br;
799 if (!eht_hosts_limit)
802 spin_lock_bh(&br->multicast_lock);
803 p->multicast_eht_hosts_limit = eht_hosts_limit;
804 spin_unlock_bh(&br->multicast_lock);