lib/mcast-snooping.c

   1 /*
   2  * Copyright (c) 2014 Red Hat, Inc.
   3  *
   4  * Based on mac-learning implementation.
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at:
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19 #include <config.h>
  20 #include "mcast-snooping.h"
  21
  22 #include <inttypes.h>
  23 #include <stdlib.h>
  24
  25 #include "bitmap.h"
  26 #include "byte-order.h"
  27 #include "coverage.h"
  28 #include "hash.h"
  29 #include "openvswitch/list.h"
  30 #include "poll-loop.h"
  31 #include "timeval.h"
  32 #include "entropy.h"
  33 #include "unaligned.h"
  34 #include "util.h"
  35 #include "vlan-bitmap.h"
  36 #include "openvswitch/vlog.h"
  37
  38 COVERAGE_DEFINE(mcast_snooping_learned);
  39 COVERAGE_DEFINE(mcast_snooping_expired);
  40
  41 static struct mcast_port_bundle *
  42 mcast_snooping_port_lookup(struct ovs_list *list, void *port);
  43 static struct mcast_mrouter_bundle *
  44 mcast_snooping_mrouter_lookup(struct mcast_snooping *ms, uint16_t vlan,
  45                               void *port)
  46     OVS_REQ_RDLOCK(ms->rwlock);
  47
  48 bool
  49 mcast_snooping_enabled(const struct mcast_snooping *ms)
  50 {
  51     return !!ms;
  52 }
  53
  54 bool
  55 mcast_snooping_flood_unreg(const struct mcast_snooping *ms)
  56 {
  57     return ms->flood_unreg;
  58 }
  59
  60 bool
  61 mcast_snooping_is_query(ovs_be16 igmp_type)
  62 {
  63     return igmp_type == htons(IGMP_HOST_MEMBERSHIP_QUERY);
  64 }
  65
  66 bool
  67 mcast_snooping_is_membership(ovs_be16 igmp_type)
  68 {
  69     switch (ntohs(igmp_type)) {
  70     case IGMP_HOST_MEMBERSHIP_REPORT:
  71     case IGMPV2_HOST_MEMBERSHIP_REPORT:
  72     case IGMPV3_HOST_MEMBERSHIP_REPORT:
  73     case IGMP_HOST_LEAVE_MESSAGE:
  74         return true;
  75     }
  76     return false;
  77 }
  78
  79 /* Returns the number of seconds since multicast group 'b' was learned in a
  80  * port on 'ms'. */
  81 int
  82 mcast_bundle_age(const struct mcast_snooping *ms,
  83                  const struct mcast_group_bundle *b)
  84 {
  85     time_t remaining = b->expires - time_now();
  86     return ms->idle_time - remaining;
  87 }
  88
  89 static uint32_t
  90 mcast_table_hash(const struct mcast_snooping *ms,
  91                  const struct in6_addr *grp_addr, uint16_t vlan)
  92 {
  93     return hash_bytes(grp_addr->s6_addr, 16,
  94                       hash_2words(ms->secret, vlan));
  95 }
  96
  97 static struct mcast_group_bundle *
  98 mcast_group_bundle_from_lru_node(struct ovs_list *list)
  99 {
 100     return CONTAINER_OF(list, struct mcast_group_bundle, bundle_node);
 101 }
 102
 103 static struct mcast_group *
 104 mcast_group_from_lru_node(struct ovs_list *list)
 105 {
 106     return CONTAINER_OF(list, struct mcast_group, group_node);
 107 }
 108
 109 /* Searches 'ms' for and returns an mcast group for destination address
 110  * 'dip' in 'vlan'. */
 111 struct mcast_group *
 112 mcast_snooping_lookup(const struct mcast_snooping *ms,
 113                       const struct in6_addr *dip, uint16_t vlan)
 114     OVS_REQ_RDLOCK(ms->rwlock)
 115 {
 116     struct mcast_group *grp;
 117     uint32_t hash;
 118
 119     hash = mcast_table_hash(ms, dip, vlan);
 120     HMAP_FOR_EACH_WITH_HASH (grp, hmap_node, hash, &ms->table) {
 121         if (grp->vlan == vlan && ipv6_addr_equals(&grp->addr, dip)) {
 122            return grp;
 123         }
 124     }
 125     return NULL;
 126 }
 127
 128 struct mcast_group *
 129 mcast_snooping_lookup4(const struct mcast_snooping *ms, ovs_be32 ip4,
 130                       uint16_t vlan)
 131     OVS_REQ_RDLOCK(ms->rwlock)
 132 {
 133     struct in6_addr addr = in6_addr_mapped_ipv4(ip4);
 134     return mcast_snooping_lookup(ms, &addr, vlan);
 135 }
 136
 137 /* If the LRU list is not empty, stores the least-recently-used entry
 138  * in '*e' and returns true.  Otherwise, if the LRU list is empty,
 139  * stores NULL in '*e' and return false. */
 140 static bool
 141 group_get_lru(const struct mcast_snooping *ms, struct mcast_group **grp)
 142     OVS_REQ_RDLOCK(ms->rwlock)
 143 {
 144     if (!ovs_list_is_empty(&ms->group_lru)) {
 145         *grp = mcast_group_from_lru_node(ms->group_lru.next);
 146         return true;
 147     } else {
 148         *grp = NULL;
 149         return false;
 150     }
 151 }
 152
 153 static unsigned int
 154 normalize_idle_time(unsigned int idle_time)
 155 {
 156     return (idle_time < 15 ? 15
 157             : idle_time > 3600 ? 3600
 158             : idle_time);
 159 }
 160
 161 /* Creates and returns a new mcast table with an initial mcast aging
 162  * timeout of MCAST_ENTRY_DEFAULT_IDLE_TIME seconds and an initial maximum of
 163  * MCAST_DEFAULT_MAX entries. */
 164 struct mcast_snooping *
 165 mcast_snooping_create(void)
 166 {
 167     struct mcast_snooping *ms;
 168
 169     ms = xmalloc(sizeof *ms);
 170     hmap_init(&ms->table);
 171     ovs_list_init(&ms->group_lru);
 172     ovs_list_init(&ms->mrouter_lru);
 173     ovs_list_init(&ms->fport_list);
 174     ovs_list_init(&ms->rport_list);
 175     ms->secret = random_uint32();
 176     ms->idle_time = MCAST_ENTRY_DEFAULT_IDLE_TIME;
 177     ms->max_entries = MCAST_DEFAULT_MAX_ENTRIES;
 178     ms->need_revalidate = false;
 179     ms->flood_unreg = true;
 180     ovs_refcount_init(&ms->ref_cnt);
 181     ovs_rwlock_init(&ms->rwlock);
 182     return ms;
 183 }
 184
 185 struct mcast_snooping *
 186 mcast_snooping_ref(const struct mcast_snooping *ms_)
 187 {
 188     struct mcast_snooping *ms = CONST_CAST(struct mcast_snooping *, ms_);
 189     if (ms) {
 190         ovs_refcount_ref(&ms->ref_cnt);
 191     }
 192     return ms;
 193 }
 194
 195 /* Unreferences (and possibly destroys) mcast snooping table 'ms'. */
 196 void
 197 mcast_snooping_unref(struct mcast_snooping *ms)
 198 {
 199     if (!mcast_snooping_enabled(ms)) {
 200         return;
 201     }
 202
 203     if (ovs_refcount_unref_relaxed(&ms->ref_cnt) == 1) {
 204         mcast_snooping_flush(ms);
 205         hmap_destroy(&ms->table);
 206         ovs_rwlock_destroy(&ms->rwlock);
 207         free(ms);
 208     }
 209 }
 210
 211 /* Changes the mcast aging timeout of 'ms' to 'idle_time' seconds. */
 212 void
 213 mcast_snooping_set_idle_time(struct mcast_snooping *ms, unsigned int idle_time)
 214     OVS_REQ_WRLOCK(ms->rwlock)
 215 {
 216     struct mcast_group *grp;
 217     struct mcast_group_bundle *b;
 218     int delta;
 219
 220     idle_time = normalize_idle_time(idle_time);
 221     if (idle_time != ms->idle_time) {
 222         delta = (int) idle_time - (int) ms->idle_time;
 223         LIST_FOR_EACH (grp, group_node, &ms->group_lru) {
 224             LIST_FOR_EACH (b, bundle_node, &grp->bundle_lru) {
 225                 b->expires += delta;
 226             }
 227         }
 228         ms->idle_time = idle_time;
 229     }
 230 }
 231
 232 /* Sets the maximum number of entries in 'ms' to 'max_entries', adjusting it
 233  * to be within a reasonable range. */
 234 void
 235 mcast_snooping_set_max_entries(struct mcast_snooping *ms,
 236                                size_t max_entries)
 237     OVS_REQ_WRLOCK(ms->rwlock)
 238 {
 239     ms->max_entries = (max_entries < 10 ? 10
 240                        : max_entries > 1000 * 1000 ? 1000 * 1000
 241                        : max_entries);
 242 }
 243
 244 /* Sets if unregistered multicast packets should be flooded to
 245  * all ports or only to ports connected to multicast routers
 246  *
 247  * Returns true if previous state differs from current state,
 248  * false otherwise. */
 249 bool
 250 mcast_snooping_set_flood_unreg(struct mcast_snooping *ms, bool enable)
 251     OVS_REQ_WRLOCK(ms->rwlock)
 252 {
 253     bool prev = ms->flood_unreg;
 254     ms->flood_unreg = enable;
 255     return prev != enable;
 256 }
 257
 258 static struct mcast_group_bundle *
 259 mcast_group_bundle_lookup(struct mcast_snooping *ms OVS_UNUSED,
 260                           struct mcast_group *grp, void *port)
 261     OVS_REQ_RDLOCK(ms->rwlock)
 262 {
 263     struct mcast_group_bundle *b;
 264
 265     LIST_FOR_EACH (b, bundle_node, &grp->bundle_lru) {
 266         if (b->port == port) {
 267             return b;
 268         }
 269     }
 270     return NULL;
 271 }
 272
 273 /* Insert a new bundle to the mcast group or update its
 274  * position and expiration if it is already there. */
 275 static struct mcast_group_bundle *
 276 mcast_group_insert_bundle(struct mcast_snooping *ms OVS_UNUSED,
 277                           struct mcast_group *grp, void *port, int idle_time)
 278     OVS_REQ_WRLOCK(ms->rwlock)
 279 {
 280     struct mcast_group_bundle *b;
 281
 282     b = mcast_group_bundle_lookup(ms, grp, port);
 283     if (b) {
 284         ovs_list_remove(&b->bundle_node);
 285     } else {
 286         b = xmalloc(sizeof *b);
 287         ovs_list_init(&b->bundle_node);
 288         b->port = port;
 289         ms->need_revalidate = true;
 290     }
 291
 292     b->expires = time_now() + idle_time;
 293     ovs_list_push_back(&grp->bundle_lru, &b->bundle_node);
 294     return b;
 295 }
 296
 297 /* Return true if multicast still has bundles associated.
 298  * Return false if there is no bundles. */
 299 static bool
 300 mcast_group_has_bundles(struct mcast_group *grp)
 301 {
 302     return !ovs_list_is_empty(&grp->bundle_lru);
 303 }
 304
 305 /* Delete 'grp' from the 'ms' hash table.
 306  * Caller is responsible to clean bundle lru first. */
 307 static void
 308 mcast_snooping_flush_group__(struct mcast_snooping *ms,
 309                              struct mcast_group *grp)
 310 {
 311     ovs_assert(ovs_list_is_empty(&grp->bundle_lru));
 312     hmap_remove(&ms->table, &grp->hmap_node);
 313     ovs_list_remove(&grp->group_node);
 314     free(grp);
 315 }
 316
 317 /* Flush out mcast group and its bundles */
 318 static void
 319 mcast_snooping_flush_group(struct mcast_snooping *ms, struct mcast_group *grp)
 320     OVS_REQ_WRLOCK(ms->rwlock)
 321 {
 322     struct mcast_group_bundle *b;
 323
 324     LIST_FOR_EACH_POP (b, bundle_node, &grp->bundle_lru) {
 325         free(b);
 326     }
 327     mcast_snooping_flush_group__(ms, grp);
 328     ms->need_revalidate = true;
 329 }
 330
 331
 332 /* Delete bundle returning true if it succeeds,
 333  * false if it didn't find the group. */
 334 static bool
 335 mcast_group_delete_bundle(struct mcast_snooping *ms OVS_UNUSED,
 336                           struct mcast_group *grp, void *port)
 337     OVS_REQ_WRLOCK(ms->rwlock)
 338 {
 339     struct mcast_group_bundle *b;
 340
 341     LIST_FOR_EACH (b, bundle_node, &grp->bundle_lru) {
 342         if (b->port == port) {
 343             ovs_list_remove(&b->bundle_node);
 344             free(b);
 345             return true;
 346         }
 347     }
 348     return false;
 349 }
 350
 351 /* If any bundle has expired, delete it.  Returns the number of deleted
 352  * bundles. */
 353 static int
 354 mcast_snooping_prune_expired(struct mcast_snooping *ms,
 355                              struct mcast_group *grp)
 356     OVS_REQ_WRLOCK(ms->rwlock)
 357 {
 358     int expired;
 359     struct mcast_group_bundle *b, *next_b;
 360     time_t timenow = time_now();
 361
 362     expired = 0;
 363     LIST_FOR_EACH_SAFE (b, next_b, bundle_node, &grp->bundle_lru) {
 364         /* This list is sorted on expiration time. */
 365         if (b->expires > timenow) {
 366             break;
 367         }
 368         ovs_list_remove(&b->bundle_node);
 369         free(b);
 370         expired++;
 371     }
 372
 373     if (!mcast_group_has_bundles(grp)) {
 374         mcast_snooping_flush_group__(ms, grp);
 375         expired++;
 376     }
 377
 378     if (expired) {
 379         ms->need_revalidate = true;
 380         COVERAGE_ADD(mcast_snooping_expired, expired);
 381     }
 382
 383     return expired;
 384 }
 385
 386 /* Add a multicast group to the mdb. If it exists, then
 387  * move to the last position in the LRU list.
 388  */
 389 bool
 390 mcast_snooping_add_group(struct mcast_snooping *ms,
 391                          const struct in6_addr *addr,
 392                          uint16_t vlan, void *port)
 393     OVS_REQ_WRLOCK(ms->rwlock)
 394 {
 395     bool learned;
 396     struct mcast_group *grp;
 397
 398     /* Avoid duplicate packets. */
 399     if (mcast_snooping_mrouter_lookup(ms, vlan, port)
 400         || mcast_snooping_port_lookup(&ms->fport_list, port)) {
 401         return false;
 402     }
 403
 404     learned = false;
 405     grp = mcast_snooping_lookup(ms, addr, vlan);
 406     if (!grp) {
 407         uint32_t hash = mcast_table_hash(ms, addr, vlan);
 408
 409         if (hmap_count(&ms->table) >= ms->max_entries) {
 410             group_get_lru(ms, &grp);
 411             mcast_snooping_flush_group(ms, grp);
 412         }
 413
 414         grp = xmalloc(sizeof *grp);
 415         hmap_insert(&ms->table, &grp->hmap_node, hash);
 416         grp->addr = *addr;
 417         grp->vlan = vlan;
 418         ovs_list_init(&grp->bundle_lru);
 419         learned = true;
 420         ms->need_revalidate = true;
 421         COVERAGE_INC(mcast_snooping_learned);
 422     } else {
 423         ovs_list_remove(&grp->group_node);
 424     }
 425     mcast_group_insert_bundle(ms, grp, port, ms->idle_time);
 426
 427     /* Mark 'grp' as recently used. */
 428     ovs_list_push_back(&ms->group_lru, &grp->group_node);
 429     return learned;
 430 }
 431
 432 bool
 433 mcast_snooping_add_group4(struct mcast_snooping *ms, ovs_be32 ip4,
 434                          uint16_t vlan, void *port)
 435     OVS_REQ_WRLOCK(ms->rwlock)
 436 {
 437     struct in6_addr addr = in6_addr_mapped_ipv4(ip4);
 438     return mcast_snooping_add_group(ms, &addr, vlan, port);
 439 }
 440
 441 int
 442 mcast_snooping_add_report(struct mcast_snooping *ms,
 443                           const struct dp_packet *p,
 444                           uint16_t vlan, void *port)
 445 {
 446     ovs_be32 ip4;
 447     size_t offset;
 448     const struct igmpv3_header *igmpv3;
 449     const struct igmpv3_record *record;
 450     int count = 0;
 451     int ngrp;
 452
 453     offset = (char *) dp_packet_l4(p) - (char *) dp_packet_data(p);
 454     igmpv3 = dp_packet_at(p, offset, IGMPV3_HEADER_LEN);
 455     if (!igmpv3) {
 456         return 0;
 457     }
 458     ngrp = ntohs(igmpv3->ngrp);
 459     offset += IGMPV3_HEADER_LEN;
 460     while (ngrp--) {
 461         bool ret;
 462         record = dp_packet_at(p, offset, sizeof(struct igmpv3_record));
 463         if (!record) {
 464             break;
 465         }
 466         /* Only consider known record types. */
 467         if (record->type < IGMPV3_MODE_IS_INCLUDE
 468             || record->type > IGMPV3_BLOCK_OLD_SOURCES) {
 469             continue;
 470         }
 471         ip4 = get_16aligned_be32(&record->maddr);
 472         /*
 473          * If record is INCLUDE MODE and there are no sources, it's equivalent
 474          * to a LEAVE.
 475          */
 476         if (ntohs(record->nsrcs) == 0
 477             && (record->type == IGMPV3_MODE_IS_INCLUDE
 478                 || record->type == IGMPV3_CHANGE_TO_INCLUDE_MODE)) {
 479             ret = mcast_snooping_leave_group4(ms, ip4, vlan, port);
 480         } else {
 481             ret = mcast_snooping_add_group4(ms, ip4, vlan, port);
 482         }
 483         if (ret) {
 484             count++;
 485         }
 486         offset += sizeof(*record)
 487                   + ntohs(record->nsrcs) * sizeof(ovs_be32) + record->aux_len;
 488     }
 489     return count;
 490 }
 491
 492 int
 493 mcast_snooping_add_mld(struct mcast_snooping *ms,
 494                           const struct dp_packet *p,
 495                           uint16_t vlan, void *port)
 496 {
 497     const struct in6_addr *addr;
 498     size_t offset;
 499     const struct mld_header *mld;
 500     const struct mld2_record *record;
 501     int count = 0;
 502     int ngrp;
 503     bool ret;
 504
 505     offset = (char *) dp_packet_l4(p) - (char *) dp_packet_data(p);
 506     mld = dp_packet_at(p, offset, MLD_HEADER_LEN);
 507     if (!mld) {
 508         return 0;
 509     }
 510     ngrp = ntohs(mld->ngrp);
 511     offset += MLD_HEADER_LEN;
 512     addr = dp_packet_at(p, offset, sizeof(struct in6_addr));
 513
 514     switch (mld->type) {
 515     case MLD_REPORT:
 516         ret = mcast_snooping_add_group(ms, addr, vlan, port);
 517         if (ret) {
 518             count++;
 519         }
 520         break;
 521     case MLD_DONE:
 522         ret = mcast_snooping_leave_group(ms, addr, vlan, port);
 523         if (ret) {
 524             count++;
 525         }
 526         break;
 527     case MLD2_REPORT:
 528         while (ngrp--) {
 529             record = dp_packet_at(p, offset, sizeof(struct mld2_record));
 530             if (!record) {
 531                 break;
 532             }
 533             /* Only consider known record types. */
 534             if (record->type >= IGMPV3_MODE_IS_INCLUDE
 535                 && record->type <= IGMPV3_BLOCK_OLD_SOURCES) {
 536                 struct in6_addr maddr;
 537                 memcpy(maddr.s6_addr, record->maddr.be16, 16);
 538                 addr = &maddr;
 539                 /*
 540                  * If record is INCLUDE MODE and there are no sources, it's
 541                  * equivalent to a LEAVE.
 542                  */
 543                 if (record->nsrcs == htons(0)
 544                     && (record->type == IGMPV3_MODE_IS_INCLUDE
 545                         || record->type == IGMPV3_CHANGE_TO_INCLUDE_MODE)) {
 546                     ret = mcast_snooping_leave_group(ms, addr, vlan, port);
 547                 } else {
 548                     ret = mcast_snooping_add_group(ms, addr, vlan, port);
 549                 }
 550                 if (ret) {
 551                     count++;
 552                 }
 553             }
 554             offset += sizeof(*record)
 555                       + ntohs(record->nsrcs) * sizeof(struct in6_addr)
 556                       + record->aux_len;
 557         }
 558     }
 559
 560     return count;
 561 }
 562
 563 bool
 564 mcast_snooping_leave_group(struct mcast_snooping *ms,
 565                            const struct in6_addr *addr,
 566                            uint16_t vlan, void *port)
 567     OVS_REQ_WRLOCK(ms->rwlock)
 568 {
 569     struct mcast_group *grp;
 570
 571     /* Ports flagged to forward Reports usually have more
 572      * than one host behind it, so don't leave the group
 573      * on the first message and just let it expire */
 574     if (mcast_snooping_port_lookup(&ms->rport_list, port)) {
 575         return false;
 576     }
 577
 578     grp = mcast_snooping_lookup(ms, addr, vlan);
 579     if (grp && mcast_group_delete_bundle(ms, grp, port)) {
 580         ms->need_revalidate = true;
 581         return true;
 582     }
 583     return false;
 584 }
 585
 586 bool
 587 mcast_snooping_leave_group4(struct mcast_snooping *ms, ovs_be32 ip4,
 588                            uint16_t vlan, void *port)
 589 {
 590     struct in6_addr addr = in6_addr_mapped_ipv4(ip4);
 591     return mcast_snooping_leave_group(ms, &addr, vlan, port);
 592 }
 593
 594 \f
 595 /* Router ports. */
 596
 597 /* Returns the number of seconds since the multicast router
 598  * was learned in a port. */
 599 int
 600 mcast_mrouter_age(const struct mcast_snooping *ms OVS_UNUSED,
 601                   const struct mcast_mrouter_bundle *mrouter)
 602 {
 603     time_t remaining = mrouter->expires - time_now();
 604     return MCAST_MROUTER_PORT_IDLE_TIME - remaining;
 605 }
 606
 607 static struct mcast_mrouter_bundle *
 608 mcast_mrouter_from_lru_node(struct ovs_list *list)
 609 {
 610     return CONTAINER_OF(list, struct mcast_mrouter_bundle, mrouter_node);
 611 }
 612
 613 /* If the LRU list is not empty, stores the least-recently-used mrouter
 614  * in '*m' and returns true.  Otherwise, if the LRU list is empty,
 615  * stores NULL in '*m' and return false. */
 616 static bool
 617 mrouter_get_lru(const struct mcast_snooping *ms,
 618                 struct mcast_mrouter_bundle **m)
 619     OVS_REQ_RDLOCK(ms->rwlock)
 620 {
 621     if (!ovs_list_is_empty(&ms->mrouter_lru)) {
 622         *m = mcast_mrouter_from_lru_node(ms->mrouter_lru.next);
 623         return true;
 624     } else {
 625         *m = NULL;
 626         return false;
 627     }
 628 }
 629
 630 static struct mcast_mrouter_bundle *
 631 mcast_snooping_mrouter_lookup(struct mcast_snooping *ms, uint16_t vlan,
 632                               void *port)
 633     OVS_REQ_RDLOCK(ms->rwlock)
 634 {
 635     struct mcast_mrouter_bundle *mrouter;
 636
 637     LIST_FOR_EACH (mrouter, mrouter_node, &ms->mrouter_lru) {
 638         if (mrouter->vlan == vlan && mrouter->port == port) {
 639             return mrouter;
 640         }
 641     }
 642     return NULL;
 643 }
 644
 645 bool
 646 mcast_snooping_add_mrouter(struct mcast_snooping *ms, uint16_t vlan,
 647                            void *port)
 648     OVS_REQ_WRLOCK(ms->rwlock)
 649 {
 650     struct mcast_mrouter_bundle *mrouter;
 651
 652     /* Avoid duplicate packets. */
 653     if (mcast_snooping_port_lookup(&ms->fport_list, port)) {
 654         return false;
 655     }
 656
 657     mrouter = mcast_snooping_mrouter_lookup(ms, vlan, port);
 658     if (mrouter) {
 659         ovs_list_remove(&mrouter->mrouter_node);
 660     } else {
 661         mrouter = xmalloc(sizeof *mrouter);
 662         mrouter->vlan = vlan;
 663         mrouter->port = port;
 664         COVERAGE_INC(mcast_snooping_learned);
 665         ms->need_revalidate = true;
 666     }
 667
 668     mrouter->expires = time_now() + MCAST_MROUTER_PORT_IDLE_TIME;
 669     ovs_list_push_back(&ms->mrouter_lru, &mrouter->mrouter_node);
 670     return ms->need_revalidate;
 671 }
 672
 673 static void
 674 mcast_snooping_flush_mrouter(struct mcast_mrouter_bundle *mrouter)
 675 {
 676     ovs_list_remove(&mrouter->mrouter_node);
 677     free(mrouter);
 678 }
 679 \f
 680 /* Ports */
 681
 682 static struct mcast_port_bundle *
 683 mcast_port_from_list_node(struct ovs_list *list)
 684 {
 685     return CONTAINER_OF(list, struct mcast_port_bundle, node);
 686 }
 687
 688 /* If the list is not empty, stores the fport in '*f' and returns true.
 689  * Otherwise, if the list is empty, stores NULL in '*f' and return false. */
 690 static bool
 691 mcast_snooping_port_get(const struct ovs_list *list,
 692                         struct mcast_port_bundle **f)
 693 {
 694     if (!ovs_list_is_empty(list)) {
 695         *f = mcast_port_from_list_node(list->next);
 696         return true;
 697     } else {
 698         *f = NULL;
 699         return false;
 700     }
 701 }
 702
 703 static struct mcast_port_bundle *
 704 mcast_snooping_port_lookup(struct ovs_list *list, void *port)
 705 {
 706     struct mcast_port_bundle *pbundle;
 707
 708     LIST_FOR_EACH (pbundle, node, list) {
 709         if (pbundle->port == port) {
 710             return pbundle;
 711         }
 712     }
 713     return NULL;
 714 }
 715
 716 static void
 717 mcast_snooping_add_port(struct ovs_list *list, void *port)
 718 {
 719     struct mcast_port_bundle *pbundle;
 720
 721     pbundle = xmalloc(sizeof *pbundle);
 722     pbundle->port = port;
 723     ovs_list_insert(list, &pbundle->node);
 724 }
 725
 726 static void
 727 mcast_snooping_flush_port(struct mcast_port_bundle *pbundle)
 728 {
 729     ovs_list_remove(&pbundle->node);
 730     free(pbundle);
 731 }
 732
 733 \f
 734 /* Flood ports. */
 735 void
 736 mcast_snooping_set_port_flood(struct mcast_snooping *ms, void *port,
 737                               bool flood)
 738     OVS_REQ_WRLOCK(ms->rwlock)
 739 {
 740     struct mcast_port_bundle *fbundle;
 741
 742     fbundle = mcast_snooping_port_lookup(&ms->fport_list, port);
 743     if (flood && !fbundle) {
 744         mcast_snooping_add_port(&ms->fport_list, port);
 745         ms->need_revalidate = true;
 746     } else if (!flood && fbundle) {
 747         mcast_snooping_flush_port(fbundle);
 748         ms->need_revalidate = true;
 749     }
 750 }
 751 \f
 752 /* Flood Reports ports. */
 753
 754 void
 755 mcast_snooping_set_port_flood_reports(struct mcast_snooping *ms, void *port,
 756                                       bool flood)
 757     OVS_REQ_WRLOCK(ms->rwlock)
 758 {
 759     struct mcast_port_bundle *pbundle;
 760
 761     pbundle = mcast_snooping_port_lookup(&ms->rport_list, port);
 762     if (flood && !pbundle) {
 763         mcast_snooping_add_port(&ms->rport_list, port);
 764         ms->need_revalidate = true;
 765     } else if (!flood && pbundle) {
 766         mcast_snooping_flush_port(pbundle);
 767         ms->need_revalidate = true;
 768     }
 769 }
 770 \f
 771 /* Run and flush. */
 772
 773 static void
 774 mcast_snooping_mdb_flush__(struct mcast_snooping *ms)
 775     OVS_REQ_WRLOCK(ms->rwlock)
 776 {
 777     struct mcast_group *grp;
 778     struct mcast_mrouter_bundle *mrouter;
 779
 780     while (group_get_lru(ms, &grp)) {
 781         mcast_snooping_flush_group(ms, grp);
 782     }
 783
 784     hmap_shrink(&ms->table);
 785
 786     while (mrouter_get_lru(ms, &mrouter)) {
 787         mcast_snooping_flush_mrouter(mrouter);
 788     }
 789 }
 790
 791 void
 792 mcast_snooping_mdb_flush(struct mcast_snooping *ms)
 793 {
 794     if (!mcast_snooping_enabled(ms)) {
 795         return;
 796     }
 797
 798     ovs_rwlock_wrlock(&ms->rwlock);
 799     mcast_snooping_mdb_flush__(ms);
 800     ovs_rwlock_unlock(&ms->rwlock);
 801 }
 802
 803 /* Flushes mdb and flood ports. */
 804 static void
 805 mcast_snooping_flush__(struct mcast_snooping *ms)
 806     OVS_REQ_WRLOCK(ms->rwlock)
 807 {
 808     struct mcast_group *grp;
 809     struct mcast_mrouter_bundle *mrouter;
 810     struct mcast_port_bundle *pbundle;
 811
 812     while (group_get_lru(ms, &grp)) {
 813         mcast_snooping_flush_group(ms, grp);
 814     }
 815
 816     hmap_shrink(&ms->table);
 817
 818     /* flush multicast routers */
 819     while (mrouter_get_lru(ms, &mrouter)) {
 820         mcast_snooping_flush_mrouter(mrouter);
 821     }
 822
 823     /* flush flood ports */
 824     while (mcast_snooping_port_get(&ms->fport_list, &pbundle)) {
 825         mcast_snooping_flush_port(pbundle);
 826     }
 827
 828     /* flush flood report ports */
 829     while (mcast_snooping_port_get(&ms->rport_list, &pbundle)) {
 830         mcast_snooping_flush_port(pbundle);
 831     }
 832 }
 833
 834 void
 835 mcast_snooping_flush(struct mcast_snooping *ms)
 836 {
 837     if (!mcast_snooping_enabled(ms)) {
 838         return;
 839     }
 840
 841     ovs_rwlock_wrlock(&ms->rwlock);
 842     mcast_snooping_flush__(ms);
 843     ovs_rwlock_unlock(&ms->rwlock);
 844 }
 845
 846 static bool
 847 mcast_snooping_run__(struct mcast_snooping *ms)
 848     OVS_REQ_WRLOCK(ms->rwlock)
 849 {
 850     bool need_revalidate;
 851     struct mcast_group *grp;
 852     struct mcast_mrouter_bundle *mrouter;
 853     int mrouter_expired;
 854
 855     while (group_get_lru(ms, &grp)) {
 856         if (hmap_count(&ms->table) > ms->max_entries) {
 857             mcast_snooping_flush_group(ms, grp);
 858         } else {
 859             if (!mcast_snooping_prune_expired(ms, grp)) {
 860                 break;
 861             }
 862         }
 863     }
 864
 865     hmap_shrink(&ms->table);
 866
 867     mrouter_expired = 0;
 868     while (mrouter_get_lru(ms, &mrouter)
 869            && time_now() >= mrouter->expires) {
 870         mcast_snooping_flush_mrouter(mrouter);
 871         mrouter_expired++;
 872     }
 873
 874     if (mrouter_expired) {
 875         ms->need_revalidate = true;
 876         COVERAGE_ADD(mcast_snooping_expired, mrouter_expired);
 877     }
 878
 879     need_revalidate = ms->need_revalidate;
 880     ms->need_revalidate = false;
 881     return need_revalidate;
 882 }
 883
 884 /* Does periodic work required by 'ms'. Returns true if something changed
 885  * that may require flow revalidation. */
 886 bool
 887 mcast_snooping_run(struct mcast_snooping *ms)
 888 {
 889     bool need_revalidate;
 890
 891     if (!mcast_snooping_enabled(ms)) {
 892         return false;
 893     }
 894
 895     ovs_rwlock_wrlock(&ms->rwlock);
 896     need_revalidate = mcast_snooping_run__(ms);
 897     ovs_rwlock_unlock(&ms->rwlock);
 898
 899     return need_revalidate;
 900 }
 901
 902 static void
 903 mcast_snooping_wait__(struct mcast_snooping *ms)
 904     OVS_REQ_RDLOCK(ms->rwlock)
 905 {
 906     if (hmap_count(&ms->table) > ms->max_entries
 907         || ms->need_revalidate) {
 908         poll_immediate_wake();
 909     } else {
 910         struct mcast_group *grp;
 911         struct mcast_group_bundle *bundle;
 912         struct mcast_mrouter_bundle *mrouter;
 913         long long int mrouter_msec;
 914         long long int msec = 0;
 915
 916         if (!ovs_list_is_empty(&ms->group_lru)) {
 917             grp = mcast_group_from_lru_node(ms->group_lru.next);
 918             bundle = mcast_group_bundle_from_lru_node(grp->bundle_lru.next);
 919             msec = bundle->expires * 1000LL;
 920         }
 921
 922         if (!ovs_list_is_empty(&ms->mrouter_lru)) {
 923             mrouter = mcast_mrouter_from_lru_node(ms->mrouter_lru.next);
 924             mrouter_msec = mrouter->expires * 1000LL;
 925             msec = msec ? MIN(msec, mrouter_msec) : mrouter_msec;
 926         }
 927
 928         if (msec) {
 929             poll_timer_wait_until(msec);
 930         }
 931     }
 932 }
 933
 934 void
 935 mcast_snooping_wait(struct mcast_snooping *ms)
 936 {
 937     if (!mcast_snooping_enabled(ms)) {
 938         return;
 939     }
 940
 941     ovs_rwlock_rdlock(&ms->rwlock);
 942     mcast_snooping_wait__(ms);
 943     ovs_rwlock_unlock(&ms->rwlock);
 944 }