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