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 (!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     list_init(&ms->group_lru);
 172     list_init(&ms->mrouter_lru);
 173     list_init(&ms->fport_list);
 174     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         list_remove(&b->bundle_node);
 285     } else {
 286         b = xmalloc(sizeof *b);
 287         list_init(&b->bundle_node);
 288         b->port = port;
 289     }
 290
 291     b->expires = time_now() + idle_time;
 292     list_push_back(&grp->bundle_lru, &b->bundle_node);
 293     return b;
 294 }
 295
 296 /* Return true if multicast still has bundles associated.
 297  * Return false if there is no bundles. */
 298 static bool
 299 mcast_group_has_bundles(struct mcast_group *grp)
 300 {
 301     return !list_is_empty(&grp->bundle_lru);
 302 }
 303
 304 /* Delete 'grp' from the 'ms' hash table.
 305  * Caller is responsible to clean bundle lru first. */
 306 static void
 307 mcast_snooping_flush_group__(struct mcast_snooping *ms,
 308                              struct mcast_group *grp)
 309 {
 310     ovs_assert(list_is_empty(&grp->bundle_lru));
 311     hmap_remove(&ms->table, &grp->hmap_node);
 312     list_remove(&grp->group_node);
 313     free(grp);
 314 }
 315
 316 /* Flush out mcast group and its bundles */
 317 static void
 318 mcast_snooping_flush_group(struct mcast_snooping *ms, struct mcast_group *grp)
 319     OVS_REQ_WRLOCK(ms->rwlock)
 320 {
 321     struct mcast_group_bundle *b;
 322
 323     LIST_FOR_EACH_POP (b, bundle_node, &grp->bundle_lru) {
 324         free(b);
 325     }
 326     mcast_snooping_flush_group__(ms, grp);
 327     ms->need_revalidate = true;
 328 }
 329
 330
 331 /* Delete bundle returning true if it succeeds,
 332  * false if it didn't find the group. */
 333 static bool
 334 mcast_group_delete_bundle(struct mcast_snooping *ms OVS_UNUSED,
 335                           struct mcast_group *grp, void *port)
 336     OVS_REQ_WRLOCK(ms->rwlock)
 337 {
 338     struct mcast_group_bundle *b;
 339
 340     LIST_FOR_EACH (b, bundle_node, &grp->bundle_lru) {
 341         if (b->port == port) {
 342             list_remove(&b->bundle_node);
 343             free(b);
 344             return true;
 345         }
 346     }
 347     return false;
 348 }
 349
 350 /* If any bundle has expired, delete it.  Returns the number of deleted
 351  * bundles. */
 352 static int
 353 mcast_snooping_prune_expired(struct mcast_snooping *ms,
 354                              struct mcast_group *grp)
 355     OVS_REQ_WRLOCK(ms->rwlock)
 356 {
 357     int expired;
 358     struct mcast_group_bundle *b, *next_b;
 359     time_t timenow = time_now();
 360
 361     expired = 0;
 362     LIST_FOR_EACH_SAFE (b, next_b, bundle_node, &grp->bundle_lru) {
 363         /* This list is sorted on expiration time. */
 364         if (b->expires > timenow) {
 365             break;
 366         }
 367         list_remove(&b->bundle_node);
 368         free(b);
 369         expired++;
 370     }
 371
 372     if (!mcast_group_has_bundles(grp)) {
 373         mcast_snooping_flush_group__(ms, grp);
 374         expired++;
 375     }
 376
 377     if (expired) {
 378         ms->need_revalidate = true;
 379         COVERAGE_ADD(mcast_snooping_expired, expired);
 380     }
 381
 382     return expired;
 383 }
 384
 385 /* Add a multicast group to the mdb. If it exists, then
 386  * move to the last position in the LRU list.
 387  */
 388 bool
 389 mcast_snooping_add_group(struct mcast_snooping *ms,
 390                          const struct in6_addr *addr,
 391                          uint16_t vlan, void *port)
 392     OVS_REQ_WRLOCK(ms->rwlock)
 393 {
 394     bool learned;
 395     struct mcast_group *grp;
 396
 397     /* Avoid duplicate packets. */
 398     if (mcast_snooping_mrouter_lookup(ms, vlan, port)
 399         || mcast_snooping_port_lookup(&ms->fport_list, port)) {
 400         return false;
 401     }
 402
 403     learned = false;
 404     grp = mcast_snooping_lookup(ms, addr, vlan);
 405     if (!grp) {
 406         uint32_t hash = mcast_table_hash(ms, addr, vlan);
 407
 408         if (hmap_count(&ms->table) >= ms->max_entries) {
 409             group_get_lru(ms, &grp);
 410             mcast_snooping_flush_group(ms, grp);
 411         }
 412
 413         grp = xmalloc(sizeof *grp);
 414         hmap_insert(&ms->table, &grp->hmap_node, hash);
 415         grp->addr = *addr;
 416         grp->vlan = vlan;
 417         list_init(&grp->bundle_lru);
 418         learned = true;
 419         ms->need_revalidate = true;
 420         COVERAGE_INC(mcast_snooping_learned);
 421     } else {
 422         list_remove(&grp->group_node);
 423     }
 424     mcast_group_insert_bundle(ms, grp, port, ms->idle_time);
 425
 426     /* Mark 'grp' as recently used. */
 427     list_push_back(&ms->group_lru, &grp->group_node);
 428     return learned;
 429 }
 430
 431 bool
 432 mcast_snooping_add_group4(struct mcast_snooping *ms, ovs_be32 ip4,
 433                          uint16_t vlan, void *port)
 434     OVS_REQ_WRLOCK(ms->rwlock)
 435 {
 436     struct in6_addr addr = in6_addr_mapped_ipv4(ip4);
 437     return mcast_snooping_add_group(ms, &addr, vlan, port);
 438 }
 439
 440 int
 441 mcast_snooping_add_report(struct mcast_snooping *ms,
 442                           const struct dp_packet *p,
 443                           uint16_t vlan, void *port)
 444 {
 445     ovs_be32 ip4;
 446     size_t offset;
 447     const struct igmpv3_header *igmpv3;
 448     const struct igmpv3_record *record;
 449     int count = 0;
 450     int ngrp;
 451
 452     offset = (char *) dp_packet_l4(p) - (char *) dp_packet_data(p);
 453     igmpv3 = dp_packet_at(p, offset, IGMPV3_HEADER_LEN);
 454     if (!igmpv3) {
 455         return 0;
 456     }
 457     ngrp = ntohs(igmpv3->ngrp);
 458     offset += IGMPV3_HEADER_LEN;
 459     while (ngrp--) {
 460         bool ret;
 461         record = dp_packet_at(p, offset, sizeof(struct igmpv3_record));
 462         if (!record) {
 463             break;
 464         }
 465         /* Only consider known record types. */
 466         if (record->type < IGMPV3_MODE_IS_INCLUDE
 467             || record->type > IGMPV3_BLOCK_OLD_SOURCES) {
 468             continue;
 469         }
 470         ip4 = get_16aligned_be32(&record->maddr);
 471         /*
 472          * If record is INCLUDE MODE and there are no sources, it's equivalent
 473          * to a LEAVE.
 474          */
 475         if (ntohs(record->nsrcs) == 0
 476             && (record->type == IGMPV3_MODE_IS_INCLUDE
 477                 || record->type == IGMPV3_CHANGE_TO_INCLUDE_MODE)) {
 478             ret = mcast_snooping_leave_group4(ms, ip4, vlan, port);
 479         } else {
 480             ret = mcast_snooping_add_group4(ms, ip4, vlan, port);
 481         }
 482         if (ret) {
 483             count++;
 484         }
 485         offset += sizeof(*record)
 486                   + ntohs(record->nsrcs) * sizeof(ovs_be32) + record->aux_len;
 487     }
 488     return count;
 489 }
 490
 491 int
 492 mcast_snooping_add_mld(struct mcast_snooping *ms,
 493                           const struct dp_packet *p,
 494                           uint16_t vlan, void *port)
 495 {
 496     const struct in6_addr *addr;
 497     size_t offset;
 498     const struct mld_header *mld;
 499     const struct mld2_record *record;
 500     int count = 0;
 501     int ngrp;
 502     bool ret;
 503
 504     offset = (char *) dp_packet_l4(p) - (char *) dp_packet_data(p);
 505     mld = dp_packet_at(p, offset, MLD_HEADER_LEN);
 506     if (!mld) {
 507         return 0;
 508     }
 509     ngrp = ntohs(mld->ngrp);
 510     offset += MLD_HEADER_LEN;
 511     addr = dp_packet_at(p, offset, sizeof(struct in6_addr));
 512
 513     switch (mld->type) {
 514     case MLD_REPORT:
 515         ret = mcast_snooping_add_group(ms, addr, vlan, port);
 516         if (ret) {
 517             count++;
 518         }
 519         break;
 520     case MLD_DONE:
 521         ret = mcast_snooping_leave_group(ms, addr, vlan, port);
 522         if (ret) {
 523             count++;
 524         }
 525         break;
 526     case MLD2_REPORT:
 527         while (ngrp--) {
 528             record = dp_packet_at(p, offset, sizeof(struct mld2_record));
 529             if (!record) {
 530                 break;
 531             }
 532             /* Only consider known record types. */
 533             if (record->type >= IGMPV3_MODE_IS_INCLUDE
 534                 && record->type <= IGMPV3_BLOCK_OLD_SOURCES) {
 535                 struct in6_addr maddr;
 536                 memcpy(maddr.s6_addr, record->maddr.be16, 16);
 537                 addr = &maddr;
 538                 /*
 539                  * If record is INCLUDE MODE and there are no sources, it's
 540                  * equivalent to a LEAVE.
 541                  */
 542                 if (record->nsrcs == htons(0)
 543                     && (record->type == IGMPV3_MODE_IS_INCLUDE
 544                         || record->type == IGMPV3_CHANGE_TO_INCLUDE_MODE)) {
 545                     ret = mcast_snooping_leave_group(ms, addr, vlan, port);
 546                 } else {
 547                     ret = mcast_snooping_add_group(ms, addr, vlan, port);
 548                 }
 549                 if (ret) {
 550                     count++;
 551                 }
 552             }
 553             offset += sizeof(*record)
 554                       + ntohs(record->nsrcs) * sizeof(struct in6_addr)
 555                       + record->aux_len;
 556         }
 557     }
 558
 559     return count;
 560 }
 561
 562 bool
 563 mcast_snooping_leave_group(struct mcast_snooping *ms,
 564                            const struct in6_addr *addr,
 565                            uint16_t vlan, void *port)
 566     OVS_REQ_WRLOCK(ms->rwlock)
 567 {
 568     struct mcast_group *grp;
 569
 570     /* Ports flagged to forward Reports usually have more
 571      * than one host behind it, so don't leave the group
 572      * on the first message and just let it expire */
 573     if (mcast_snooping_port_lookup(&ms->rport_list, port)) {
 574         return false;
 575     }
 576
 577     grp = mcast_snooping_lookup(ms, addr, vlan);
 578     if (grp && mcast_group_delete_bundle(ms, grp, port)) {
 579         ms->need_revalidate = true;
 580         return true;
 581     }
 582     return false;
 583 }
 584
 585 bool
 586 mcast_snooping_leave_group4(struct mcast_snooping *ms, ovs_be32 ip4,
 587                            uint16_t vlan, void *port)
 588 {
 589     struct in6_addr addr = in6_addr_mapped_ipv4(ip4);
 590     return mcast_snooping_leave_group(ms, &addr, vlan, port);
 591 }
 592
 593 \f
 594 /* Router ports. */
 595
 596 /* Returns the number of seconds since the multicast router
 597  * was learned in a port. */
 598 int
 599 mcast_mrouter_age(const struct mcast_snooping *ms OVS_UNUSED,
 600                   const struct mcast_mrouter_bundle *mrouter)
 601 {
 602     time_t remaining = mrouter->expires - time_now();
 603     return MCAST_MROUTER_PORT_IDLE_TIME - remaining;
 604 }
 605
 606 static struct mcast_mrouter_bundle *
 607 mcast_mrouter_from_lru_node(struct ovs_list *list)
 608 {
 609     return CONTAINER_OF(list, struct mcast_mrouter_bundle, mrouter_node);
 610 }
 611
 612 /* If the LRU list is not empty, stores the least-recently-used mrouter
 613  * in '*m' and returns true.  Otherwise, if the LRU list is empty,
 614  * stores NULL in '*m' and return false. */
 615 static bool
 616 mrouter_get_lru(const struct mcast_snooping *ms,
 617                 struct mcast_mrouter_bundle **m)
 618     OVS_REQ_RDLOCK(ms->rwlock)
 619 {
 620     if (!list_is_empty(&ms->mrouter_lru)) {
 621         *m = mcast_mrouter_from_lru_node(ms->mrouter_lru.next);
 622         return true;
 623     } else {
 624         *m = NULL;
 625         return false;
 626     }
 627 }
 628
 629 static struct mcast_mrouter_bundle *
 630 mcast_snooping_mrouter_lookup(struct mcast_snooping *ms, uint16_t vlan,
 631                               void *port)
 632     OVS_REQ_RDLOCK(ms->rwlock)
 633 {
 634     struct mcast_mrouter_bundle *mrouter;
 635
 636     LIST_FOR_EACH (mrouter, mrouter_node, &ms->mrouter_lru) {
 637         if (mrouter->vlan == vlan && mrouter->port == port) {
 638             return mrouter;
 639         }
 640     }
 641     return NULL;
 642 }
 643
 644 bool
 645 mcast_snooping_add_mrouter(struct mcast_snooping *ms, uint16_t vlan,
 646                            void *port)
 647     OVS_REQ_WRLOCK(ms->rwlock)
 648 {
 649     struct mcast_mrouter_bundle *mrouter;
 650
 651     /* Avoid duplicate packets. */
 652     if (mcast_snooping_port_lookup(&ms->fport_list, port)) {
 653         return false;
 654     }
 655
 656     mrouter = mcast_snooping_mrouter_lookup(ms, vlan, port);
 657     if (mrouter) {
 658         list_remove(&mrouter->mrouter_node);
 659     } else {
 660         mrouter = xmalloc(sizeof *mrouter);
 661         mrouter->vlan = vlan;
 662         mrouter->port = port;
 663         COVERAGE_INC(mcast_snooping_learned);
 664         ms->need_revalidate = true;
 665     }
 666
 667     mrouter->expires = time_now() + MCAST_MROUTER_PORT_IDLE_TIME;
 668     list_push_back(&ms->mrouter_lru, &mrouter->mrouter_node);
 669     return ms->need_revalidate;
 670 }
 671
 672 static void
 673 mcast_snooping_flush_mrouter(struct mcast_mrouter_bundle *mrouter)
 674 {
 675     list_remove(&mrouter->mrouter_node);
 676     free(mrouter);
 677 }
 678 \f
 679 /* Ports */
 680
 681 static struct mcast_port_bundle *
 682 mcast_port_from_list_node(struct ovs_list *list)
 683 {
 684     return CONTAINER_OF(list, struct mcast_port_bundle, node);
 685 }
 686
 687 /* If the list is not empty, stores the fport in '*f' and returns true.
 688  * Otherwise, if the list is empty, stores NULL in '*f' and return false. */
 689 static bool
 690 mcast_snooping_port_get(const struct ovs_list *list,
 691                         struct mcast_port_bundle **f)
 692 {
 693     if (!list_is_empty(list)) {
 694         *f = mcast_port_from_list_node(list->next);
 695         return true;
 696     } else {
 697         *f = NULL;
 698         return false;
 699     }
 700 }
 701
 702 static struct mcast_port_bundle *
 703 mcast_snooping_port_lookup(struct ovs_list *list, void *port)
 704 {
 705     struct mcast_port_bundle *pbundle;
 706
 707     LIST_FOR_EACH (pbundle, node, list) {
 708         if (pbundle->port == port) {
 709             return pbundle;
 710         }
 711     }
 712     return NULL;
 713 }
 714
 715 static void
 716 mcast_snooping_add_port(struct ovs_list *list, void *port)
 717 {
 718     struct mcast_port_bundle *pbundle;
 719
 720     pbundle = xmalloc(sizeof *pbundle);
 721     pbundle->port = port;
 722     list_insert(list, &pbundle->node);
 723 }
 724
 725 static void
 726 mcast_snooping_flush_port(struct mcast_port_bundle *pbundle)
 727 {
 728     list_remove(&pbundle->node);
 729     free(pbundle);
 730 }
 731
 732 \f
 733 /* Flood ports. */
 734 void
 735 mcast_snooping_set_port_flood(struct mcast_snooping *ms, void *port,
 736                               bool flood)
 737     OVS_REQ_WRLOCK(ms->rwlock)
 738 {
 739     struct mcast_port_bundle *fbundle;
 740
 741     fbundle = mcast_snooping_port_lookup(&ms->fport_list, port);
 742     if (flood && !fbundle) {
 743         mcast_snooping_add_port(&ms->fport_list, port);
 744         ms->need_revalidate = true;
 745     } else if (!flood && fbundle) {
 746         mcast_snooping_flush_port(fbundle);
 747         ms->need_revalidate = true;
 748     }
 749 }
 750 \f
 751 /* Flood Reports ports. */
 752
 753 void
 754 mcast_snooping_set_port_flood_reports(struct mcast_snooping *ms, void *port,
 755                                       bool flood)
 756     OVS_REQ_WRLOCK(ms->rwlock)
 757 {
 758     struct mcast_port_bundle *pbundle;
 759
 760     pbundle = mcast_snooping_port_lookup(&ms->rport_list, port);
 761     if (flood && !pbundle) {
 762         mcast_snooping_add_port(&ms->rport_list, port);
 763         ms->need_revalidate = true;
 764     } else if (!flood && pbundle) {
 765         mcast_snooping_flush_port(pbundle);
 766         ms->need_revalidate = true;
 767     }
 768 }
 769 \f
 770 /* Run and flush. */
 771
 772 static void
 773 mcast_snooping_mdb_flush__(struct mcast_snooping *ms)
 774     OVS_REQ_WRLOCK(ms->rwlock)
 775 {
 776     struct mcast_group *grp;
 777     struct mcast_mrouter_bundle *mrouter;
 778
 779     while (group_get_lru(ms, &grp)) {
 780         mcast_snooping_flush_group(ms, grp);
 781     }
 782
 783     hmap_shrink(&ms->table);
 784
 785     while (mrouter_get_lru(ms, &mrouter)) {
 786         mcast_snooping_flush_mrouter(mrouter);
 787     }
 788 }
 789
 790 void
 791 mcast_snooping_mdb_flush(struct mcast_snooping *ms)
 792 {
 793     if (!mcast_snooping_enabled(ms)) {
 794         return;
 795     }
 796
 797     ovs_rwlock_wrlock(&ms->rwlock);
 798     mcast_snooping_mdb_flush__(ms);
 799     ovs_rwlock_unlock(&ms->rwlock);
 800 }
 801
 802 /* Flushes mdb and flood ports. */
 803 static void
 804 mcast_snooping_flush__(struct mcast_snooping *ms)
 805     OVS_REQ_WRLOCK(ms->rwlock)
 806 {
 807     struct mcast_group *grp;
 808     struct mcast_mrouter_bundle *mrouter;
 809     struct mcast_port_bundle *pbundle;
 810
 811     while (group_get_lru(ms, &grp)) {
 812         mcast_snooping_flush_group(ms, grp);
 813     }
 814
 815     hmap_shrink(&ms->table);
 816
 817     /* flush multicast routers */
 818     while (mrouter_get_lru(ms, &mrouter)) {
 819         mcast_snooping_flush_mrouter(mrouter);
 820     }
 821
 822     /* flush flood ports */
 823     while (mcast_snooping_port_get(&ms->fport_list, &pbundle)) {
 824         mcast_snooping_flush_port(pbundle);
 825     }
 826
 827     /* flush flood report ports */
 828     while (mcast_snooping_port_get(&ms->rport_list, &pbundle)) {
 829         mcast_snooping_flush_port(pbundle);
 830     }
 831 }
 832
 833 void
 834 mcast_snooping_flush(struct mcast_snooping *ms)
 835 {
 836     if (!mcast_snooping_enabled(ms)) {
 837         return;
 838     }
 839
 840     ovs_rwlock_wrlock(&ms->rwlock);
 841     mcast_snooping_flush__(ms);
 842     ovs_rwlock_unlock(&ms->rwlock);
 843 }
 844
 845 static bool
 846 mcast_snooping_run__(struct mcast_snooping *ms)
 847     OVS_REQ_WRLOCK(ms->rwlock)
 848 {
 849     bool need_revalidate;
 850     struct mcast_group *grp;
 851     struct mcast_mrouter_bundle *mrouter;
 852     int mrouter_expired;
 853
 854     while (group_get_lru(ms, &grp)) {
 855         if (hmap_count(&ms->table) > ms->max_entries) {
 856             mcast_snooping_flush_group(ms, grp);
 857         } else {
 858             if (!mcast_snooping_prune_expired(ms, grp)) {
 859                 break;
 860             }
 861         }
 862     }
 863
 864     hmap_shrink(&ms->table);
 865
 866     mrouter_expired = 0;
 867     while (mrouter_get_lru(ms, &mrouter)
 868            && time_now() >= mrouter->expires) {
 869         mcast_snooping_flush_mrouter(mrouter);
 870         mrouter_expired++;
 871     }
 872
 873     if (mrouter_expired) {
 874         ms->need_revalidate = true;
 875         COVERAGE_ADD(mcast_snooping_expired, mrouter_expired);
 876     }
 877
 878     need_revalidate = ms->need_revalidate;
 879     ms->need_revalidate = false;
 880     return need_revalidate;
 881 }
 882
 883 /* Does periodic work required by 'ms'. Returns true if something changed
 884  * that may require flow revalidation. */
 885 bool
 886 mcast_snooping_run(struct mcast_snooping *ms)
 887 {
 888     bool need_revalidate;
 889
 890     if (!mcast_snooping_enabled(ms)) {
 891         return false;
 892     }
 893
 894     ovs_rwlock_wrlock(&ms->rwlock);
 895     need_revalidate = mcast_snooping_run__(ms);
 896     ovs_rwlock_unlock(&ms->rwlock);
 897
 898     return need_revalidate;
 899 }
 900
 901 static void
 902 mcast_snooping_wait__(struct mcast_snooping *ms)
 903     OVS_REQ_RDLOCK(ms->rwlock)
 904 {
 905     if (hmap_count(&ms->table) > ms->max_entries
 906         || ms->need_revalidate) {
 907         poll_immediate_wake();
 908     } else {
 909         struct mcast_group *grp;
 910         struct mcast_group_bundle *bundle;
 911         struct mcast_mrouter_bundle *mrouter;
 912         long long int mrouter_msec;
 913         long long int msec = 0;
 914
 915         if (!list_is_empty(&ms->group_lru)) {
 916             grp = mcast_group_from_lru_node(ms->group_lru.next);
 917             bundle = mcast_group_bundle_from_lru_node(grp->bundle_lru.next);
 918             msec = bundle->expires * 1000LL;
 919         }
 920
 921         if (!list_is_empty(&ms->mrouter_lru)) {
 922             mrouter = mcast_mrouter_from_lru_node(ms->mrouter_lru.next);
 923             mrouter_msec = mrouter->expires * 1000LL;
 924             msec = msec ? MIN(msec, mrouter_msec) : mrouter_msec;
 925         }
 926
 927         if (msec) {
 928             poll_timer_wait_until(msec);
 929         }
 930     }
 931 }
 932
 933 void
 934 mcast_snooping_wait(struct mcast_snooping *ms)
 935 {
 936     if (!mcast_snooping_enabled(ms)) {
 937         return;
 938     }
 939
 940     ovs_rwlock_rdlock(&ms->rwlock);
 941     mcast_snooping_wait__(ms);
 942     ovs_rwlock_unlock(&ms->rwlock);
 943 }