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