- }
- }
- return false;
-}
-
-static bool
-port_trunks_vlan(const struct port *port, uint16_t vlan)
-{
- return (port->vlan < 0
- && (!port->trunks || bitmap_is_set(port->trunks, vlan)));
-}
-
-static bool
-port_includes_vlan(const struct port *port, uint16_t vlan)
-{
- return vlan == port->vlan || port_trunks_vlan(port, vlan);
-}
-
-static bool
-port_is_floodable(const struct port *port)
-{
- int i;
-
- for (i = 0; i < port->n_ifaces; i++) {
- if (!ofproto_port_is_floodable(port->bridge->ofproto,
- port->ifaces[i]->dp_ifidx)) {
- return false;
- }
- }
- return true;
-}
-
-static size_t
-compose_dsts(const struct bridge *br, const struct flow *flow, uint16_t vlan,
- const struct port *in_port, const struct port *out_port,
- struct dst dsts[], tag_type *tags, uint16_t *nf_output_iface)
-{
- mirror_mask_t mirrors = in_port->src_mirrors;
- struct dst *dst = dsts;
- size_t i;
-
- if (out_port == FLOOD_PORT) {
- /* XXX use ODP_FLOOD if no vlans or bonding. */
- /* XXX even better, define each VLAN as a datapath port group */
- for (i = 0; i < br->n_ports; i++) {
- struct port *port = br->ports[i];
- if (port != in_port
- && port_is_floodable(port)
- && port_includes_vlan(port, vlan)
- && !port->is_mirror_output_port
- && set_dst(dst, flow, in_port, port, tags)) {
- mirrors |= port->dst_mirrors;
- dst++;
- }
- }
- *nf_output_iface = NF_OUT_FLOOD;
- } else if (out_port && set_dst(dst, flow, in_port, out_port, tags)) {
- *nf_output_iface = dst->dp_ifidx;
- mirrors |= out_port->dst_mirrors;
- dst++;
- }
-
- while (mirrors) {
- struct mirror *m = br->mirrors[mirror_mask_ffs(mirrors) - 1];
- if (!m->n_vlans || vlan_is_mirrored(m, vlan)) {
- if (m->out_port) {
- if (set_dst(dst, flow, in_port, m->out_port, tags)
- && !dst_is_duplicate(dsts, dst - dsts, dst)) {
- dst++;
- }
- } else {
- for (i = 0; i < br->n_ports; i++) {
- struct port *port = br->ports[i];
- if (port_includes_vlan(port, m->out_vlan)
- && set_dst(dst, flow, in_port, port, tags))
- {
- int flow_vlan;
-
- if (port->vlan < 0) {
- dst->vlan = m->out_vlan;
- }
- if (dst_is_duplicate(dsts, dst - dsts, dst)) {
- continue;
- }
-
- /* Use the vlan tag on the original flow instead of
- * the one passed in the vlan parameter. This ensures
- * that we compare the vlan from before any implicit
- * tagging tags place. This is necessary because
- * dst->vlan is the final vlan, after removing implicit
- * tags. */
- flow_vlan = ntohs(flow->dl_vlan);
- if (flow_vlan == 0) {
- flow_vlan = OFP_VLAN_NONE;
- }
- if (port == in_port && dst->vlan == flow_vlan) {
- /* Don't send out input port on same VLAN. */
- continue;
- }
- dst++;
- }
- }
- }
- }
- mirrors &= mirrors - 1;
- }
-
- partition_dsts(dsts, dst - dsts, ntohs(flow->dl_vlan));
- return dst - dsts;
-}
-
-static void OVS_UNUSED
-print_dsts(const struct dst *dsts, size_t n)
-{
- for (; n--; dsts++) {
- printf(">p%"PRIu16, dsts->dp_ifidx);
- if (dsts->vlan != OFP_VLAN_NONE) {
- printf("v%"PRIu16, dsts->vlan);
- }
- }
-}
-
-static void
-compose_actions(struct bridge *br, const struct flow *flow, uint16_t vlan,
- const struct port *in_port, const struct port *out_port,
- tag_type *tags, struct odp_actions *actions,
- uint16_t *nf_output_iface)
-{
- struct dst dsts[DP_MAX_PORTS * (MAX_MIRRORS + 1)];
- size_t n_dsts;
- const struct dst *p;
- uint16_t cur_vlan;
-
- n_dsts = compose_dsts(br, flow, vlan, in_port, out_port, dsts, tags,
- nf_output_iface);
-
- cur_vlan = ntohs(flow->dl_vlan);
- for (p = dsts; p < &dsts[n_dsts]; p++) {
- union odp_action *a;
- if (p->vlan != cur_vlan) {
- if (p->vlan == OFP_VLAN_NONE) {
- odp_actions_add(actions, ODPAT_STRIP_VLAN);
- } else {
- a = odp_actions_add(actions, ODPAT_SET_DL_TCI);
- a->dl_tci.tci = htons(p->vlan & VLAN_VID_MASK);
- a->dl_tci.tci |= htons(flow->dl_vlan_pcp << VLAN_PCP_SHIFT);
- }
- cur_vlan = p->vlan;
- }
- a = odp_actions_add(actions, ODPAT_OUTPUT);
- a->output.port = p->dp_ifidx;
- }
-}
-
-/* Returns the effective vlan of a packet, taking into account both the
- * 802.1Q header and implicitly tagged ports. A value of 0 indicates that
- * the packet is untagged and -1 indicates it has an invalid header and
- * should be dropped. */
-static int flow_get_vlan(struct bridge *br, const struct flow *flow,
- struct port *in_port, bool have_packet)
-{
- /* Note that dl_vlan of 0 and of OFP_VLAN_NONE both mean that the packet
- * belongs to VLAN 0, so we should treat both cases identically. (In the
- * former case, the packet has an 802.1Q header that specifies VLAN 0,
- * presumably to allow a priority to be specified. In the latter case, the
- * packet does not have any 802.1Q header.) */
- int vlan = ntohs(flow->dl_vlan);
- if (vlan == OFP_VLAN_NONE) {
- vlan = 0;
- }
- if (in_port->vlan >= 0) {
- if (vlan) {
- /* XXX support double tagging? */
- if (have_packet) {
- static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
- VLOG_WARN_RL(&rl, "bridge %s: dropping VLAN %"PRIu16" tagged "
- "packet received on port %s configured with "
- "implicit VLAN %"PRIu16,
- br->name, ntohs(flow->dl_vlan),
- in_port->name, in_port->vlan);
- }
- return -1;
- }
- vlan = in_port->vlan;
- } else {
- if (!port_includes_vlan(in_port, vlan)) {
- if (have_packet) {
- static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
- VLOG_WARN_RL(&rl, "bridge %s: dropping VLAN %d tagged "
- "packet received on port %s not configured for "
- "trunking VLAN %d",
- br->name, vlan, in_port->name, vlan);
- }
- return -1;
- }
- }
-
- return vlan;
-}
-
-/* A VM broadcasts a gratuitous ARP to indicate that it has resumed after
- * migration. Older Citrix-patched Linux DomU used gratuitous ARP replies to
- * indicate this; newer upstream kernels use gratuitous ARP requests. */
-static bool
-is_gratuitous_arp(const struct flow *flow)
-{
- return (flow->dl_type == htons(ETH_TYPE_ARP)
- && eth_addr_is_broadcast(flow->dl_dst)
- && (flow->nw_proto == ARP_OP_REPLY
- || (flow->nw_proto == ARP_OP_REQUEST
- && flow->nw_src == flow->nw_dst)));
-}
-
-static void
-update_learning_table(struct bridge *br, const struct flow *flow, int vlan,
- struct port *in_port)
-{
- enum grat_arp_lock_type lock_type;
- tag_type rev_tag;
-
- /* We don't want to learn from gratuitous ARP packets that are reflected
- * back over bond slaves so we lock the learning table. */
- lock_type = !is_gratuitous_arp(flow) ? GRAT_ARP_LOCK_NONE :
- (in_port->n_ifaces == 1) ? GRAT_ARP_LOCK_SET :
- GRAT_ARP_LOCK_CHECK;
-
- rev_tag = mac_learning_learn(br->ml, flow->dl_src, vlan, in_port->port_idx,
- lock_type);
- if (rev_tag) {
- /* The log messages here could actually be useful in debugging,
- * so keep the rate limit relatively high. */
- static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30,
- 300);
- VLOG_DBG_RL(&rl, "bridge %s: learned that "ETH_ADDR_FMT" is "
- "on port %s in VLAN %d",
- br->name, ETH_ADDR_ARGS(flow->dl_src),
- in_port->name, vlan);
- ofproto_revalidate(br->ofproto, rev_tag);
- }
-}
-
-/* Determines whether packets in 'flow' within 'br' should be forwarded or
- * dropped. Returns true if they may be forwarded, false if they should be
- * dropped.
- *
- * If 'have_packet' is true, it indicates that the caller is processing a
- * received packet. If 'have_packet' is false, then the caller is just
- * revalidating an existing flow because configuration has changed. Either
- * way, 'have_packet' only affects logging (there is no point in logging errors
- * during revalidation).
- *
- * Sets '*in_portp' to the input port. This will be a null pointer if
- * flow->in_port does not designate a known input port (in which case
- * is_admissible() returns false).
- *
- * When returning true, sets '*vlanp' to the effective VLAN of the input
- * packet, as returned by flow_get_vlan().
- *
- * May also add tags to '*tags', although the current implementation only does
- * so in one special case.
- */
-static bool
-is_admissible(struct bridge *br, const struct flow *flow, bool have_packet,
- tag_type *tags, int *vlanp, struct port **in_portp)
-{
- struct iface *in_iface;
- struct port *in_port;
- int vlan;
-
- /* Find the interface and port structure for the received packet. */
- in_iface = iface_from_dp_ifidx(br, flow->in_port);
- if (!in_iface) {
- /* No interface? Something fishy... */
- if (have_packet) {
- /* Odd. A few possible reasons here:
- *
- * - We deleted an interface but there are still a few packets
- * queued up from it.
- *
- * - Someone externally added an interface (e.g. with "ovs-dpctl
- * add-if") that we don't know about.
- *
- * - Packet arrived on the local port but the local port is not
- * one of our bridge ports.
- */
- static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
-
- VLOG_WARN_RL(&rl, "bridge %s: received packet on unknown "
- "interface %"PRIu16, br->name, flow->in_port);
- }
-
- *in_portp = NULL;
- return false;
- }
- *in_portp = in_port = in_iface->port;
- *vlanp = vlan = flow_get_vlan(br, flow, in_port, have_packet);
- if (vlan < 0) {
- return false;
- }
-
- /* Drop frames for reserved multicast addresses. */
- if (eth_addr_is_reserved(flow->dl_dst)) {
- return false;
- }
-
- /* Drop frames on ports reserved for mirroring. */
- if (in_port->is_mirror_output_port) {
- if (have_packet) {
- static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
- VLOG_WARN_RL(&rl, "bridge %s: dropping packet received on port "
- "%s, which is reserved exclusively for mirroring",
- br->name, in_port->name);
- }
- return false;
- }
-
- /* Packets received on bonds need special attention to avoid duplicates. */
- if (in_port->n_ifaces > 1) {
- int src_idx;
- bool is_grat_arp_locked;
-
- if (eth_addr_is_multicast(flow->dl_dst)) {
- *tags |= in_port->active_iface_tag;
- if (in_port->active_iface != in_iface->port_ifidx) {
- /* Drop all multicast packets on inactive slaves. */
- return false;
- }
- }
-
- /* Drop all packets for which we have learned a different input
- * port, because we probably sent the packet on one slave and got
- * it back on the other. Gratuitous ARP packets are an exception
- * to this rule: the host has moved to another switch. The exception
- * to the exception is if we locked the learning table to avoid
- * reflections on bond slaves. If this is the case, just drop the
- * packet now. */
- src_idx = mac_learning_lookup(br->ml, flow->dl_src, vlan,
- &is_grat_arp_locked);
- if (src_idx != -1 && src_idx != in_port->port_idx &&
- (!is_gratuitous_arp(flow) || is_grat_arp_locked)) {
- return false;
- }
- }
-
- return true;
-}
-
-/* If the composed actions may be applied to any packet in the given 'flow',
- * returns true. Otherwise, the actions should only be applied to 'packet', or
- * not at all, if 'packet' was NULL. */
-static bool
-process_flow(struct bridge *br, const struct flow *flow,
- const struct ofpbuf *packet, struct odp_actions *actions,
- tag_type *tags, uint16_t *nf_output_iface)
-{
- struct port *in_port;
- struct port *out_port;
- int vlan;
- int out_port_idx;
-
- /* Check whether we should drop packets in this flow. */
- if (!is_admissible(br, flow, packet != NULL, tags, &vlan, &in_port)) {
- out_port = NULL;
- goto done;
- }
-
- /* Learn source MAC (but don't try to learn from revalidation). */
- if (packet) {
- update_learning_table(br, flow, vlan, in_port);
- }
-
- /* Determine output port. */
- out_port_idx = mac_learning_lookup_tag(br->ml, flow->dl_dst, vlan, tags,
- NULL);
- if (out_port_idx >= 0 && out_port_idx < br->n_ports) {
- out_port = br->ports[out_port_idx];
- } else if (!packet && !eth_addr_is_multicast(flow->dl_dst)) {
- /* If we are revalidating but don't have a learning entry then
- * eject the flow. Installing a flow that floods packets opens
- * up a window of time where we could learn from a packet reflected
- * on a bond and blackhole packets before the learning table is
- * updated to reflect the correct port. */
- return false;
- } else {
- out_port = FLOOD_PORT;
- }
-
- /* Don't send packets out their input ports. */
- if (in_port == out_port) {
- out_port = NULL;
- }
-
-done:
- if (in_port) {
- compose_actions(br, flow, vlan, in_port, out_port, tags, actions,
- nf_output_iface);
- }
-
- return true;
-}
-
-static bool
-bridge_normal_ofhook_cb(const struct flow *flow, const struct ofpbuf *packet,
- struct odp_actions *actions, tag_type *tags,
- uint16_t *nf_output_iface, void *br_)
-{
- struct bridge *br = br_;
-
- COVERAGE_INC(bridge_process_flow);
-
- return process_flow(br, flow, packet, actions, tags, nf_output_iface);
-}
-
-static void
-bridge_account_flow_ofhook_cb(const struct flow *flow, tag_type tags,
- const union odp_action *actions,
- size_t n_actions, unsigned long long int n_bytes,
- void *br_)
-{
- struct bridge *br = br_;
- const union odp_action *a;
- struct port *in_port;
- tag_type dummy = 0;
- int vlan;
-
- /* Feed information from the active flows back into the learning table to
- * ensure that table is always in sync with what is actually flowing
- * through the datapath.
- *
- * We test that 'tags' is nonzero to ensure that only flows that include an
- * OFPP_NORMAL action are used for learning. This works because
- * bridge_normal_ofhook_cb() always sets a nonzero tag value. */
- if (tags && is_admissible(br, flow, false, &dummy, &vlan, &in_port)) {
- update_learning_table(br, flow, vlan, in_port);
- }
-
- /* Account for bond slave utilization. */
- if (!br->has_bonded_ports) {
- return;
- }
- for (a = actions; a < &actions[n_actions]; a++) {
- if (a->type == ODPAT_OUTPUT) {
- struct port *out_port = port_from_dp_ifidx(br, a->output.port);
- if (out_port && out_port->n_ifaces >= 2) {
- struct bond_entry *e = lookup_bond_entry(out_port,
- flow->dl_src);
- e->tx_bytes += n_bytes;
- }
- }
- }
-}
-
-static void
-bridge_account_checkpoint_ofhook_cb(void *br_)
-{
- struct bridge *br = br_;
- long long int now;
- size_t i;
-
- if (!br->has_bonded_ports) {
- return;
- }
-
- now = time_msec();
- for (i = 0; i < br->n_ports; i++) {
- struct port *port = br->ports[i];
- if (port->n_ifaces > 1 && now >= port->bond_next_rebalance) {
- port->bond_next_rebalance = now + port->bond_rebalance_interval;
- bond_rebalance_port(port);
- }
- }
-}
-
-static struct ofhooks bridge_ofhooks = {
- bridge_normal_ofhook_cb,
- bridge_account_flow_ofhook_cb,
- bridge_account_checkpoint_ofhook_cb,
-};
-\f
-/* Bonding functions. */
-
-/* Statistics for a single interface on a bonded port, used for load-based
- * bond rebalancing. */
-struct slave_balance {
- struct iface *iface; /* The interface. */
- uint64_t tx_bytes; /* Sum of hashes[*]->tx_bytes. */
-
- /* All the "bond_entry"s that are assigned to this interface, in order of
- * increasing tx_bytes. */
- struct bond_entry **hashes;
- size_t n_hashes;
-};
-
-/* Sorts pointers to pointers to bond_entries in ascending order by the
- * interface to which they are assigned, and within a single interface in
- * ascending order of bytes transmitted. */
-static int
-compare_bond_entries(const void *a_, const void *b_)
-{
- const struct bond_entry *const *ap = a_;
- const struct bond_entry *const *bp = b_;
- const struct bond_entry *a = *ap;
- const struct bond_entry *b = *bp;
- if (a->iface_idx != b->iface_idx) {
- return a->iface_idx > b->iface_idx ? 1 : -1;
- } else if (a->tx_bytes != b->tx_bytes) {
- return a->tx_bytes > b->tx_bytes ? 1 : -1;
- } else {
- return 0;
- }
-}
-
-/* Sorts slave_balances so that enabled ports come first, and otherwise in
- * *descending* order by number of bytes transmitted. */
-static int
-compare_slave_balance(const void *a_, const void *b_)
-{
- const struct slave_balance *a = a_;
- const struct slave_balance *b = b_;
- if (a->iface->enabled != b->iface->enabled) {
- return a->iface->enabled ? -1 : 1;
- } else if (a->tx_bytes != b->tx_bytes) {
- return a->tx_bytes > b->tx_bytes ? -1 : 1;
- } else {
- return 0;
- }
-}
-
-static void
-swap_bals(struct slave_balance *a, struct slave_balance *b)
-{
- struct slave_balance tmp = *a;
- *a = *b;
- *b = tmp;
-}
-
-/* Restores the 'n_bals' slave_balance structures in 'bals' to sorted order
- * given that 'p' (and only 'p') might be in the wrong location.
- *
- * This function invalidates 'p', since it might now be in a different memory
- * location. */
-static void
-resort_bals(struct slave_balance *p,
- struct slave_balance bals[], size_t n_bals)
-{
- if (n_bals > 1) {
- for (; p > bals && p->tx_bytes > p[-1].tx_bytes; p--) {
- swap_bals(p, p - 1);
- }
- for (; p < &bals[n_bals - 1] && p->tx_bytes < p[1].tx_bytes; p++) {
- swap_bals(p, p + 1);
- }
- }
-}
-
-static void
-log_bals(const struct slave_balance *bals, size_t n_bals, struct port *port)
-{
- if (VLOG_IS_DBG_ENABLED()) {
- struct ds ds = DS_EMPTY_INITIALIZER;
- const struct slave_balance *b;
-
- for (b = bals; b < bals + n_bals; b++) {
- size_t i;
-
- if (b > bals) {
- ds_put_char(&ds, ',');
- }
- ds_put_format(&ds, " %s %"PRIu64"kB",
- b->iface->name, b->tx_bytes / 1024);
-
- if (!b->iface->enabled) {
- ds_put_cstr(&ds, " (disabled)");
- }
- if (b->n_hashes > 0) {
- ds_put_cstr(&ds, " (");
- for (i = 0; i < b->n_hashes; i++) {
- const struct bond_entry *e = b->hashes[i];
- if (i > 0) {
- ds_put_cstr(&ds, " + ");
- }
- ds_put_format(&ds, "h%td: %"PRIu64"kB",
- e - port->bond_hash, e->tx_bytes / 1024);
- }
- ds_put_cstr(&ds, ")");
- }
- }
- VLOG_DBG("bond %s:%s", port->name, ds_cstr(&ds));
- ds_destroy(&ds);
- }
-}
-
-/* Shifts 'hash' from 'from' to 'to' within 'port'. */
-static void
-bond_shift_load(struct slave_balance *from, struct slave_balance *to,
- int hash_idx)
-{
- struct bond_entry *hash = from->hashes[hash_idx];
- struct port *port = from->iface->port;
- uint64_t delta = hash->tx_bytes;
-
- VLOG_INFO("bond %s: shift %"PRIu64"kB of load (with hash %td) "
- "from %s to %s (now carrying %"PRIu64"kB and "
- "%"PRIu64"kB load, respectively)",
- port->name, delta / 1024, hash - port->bond_hash,
- from->iface->name, to->iface->name,
- (from->tx_bytes - delta) / 1024,
- (to->tx_bytes + delta) / 1024);
-
- /* Delete element from from->hashes.
- *
- * We don't bother to add the element to to->hashes because not only would
- * it require more work, the only purpose it would be to allow that hash to
- * be migrated to another slave in this rebalancing run, and there is no
- * point in doing that. */
- if (hash_idx == 0) {
- from->hashes++;
- } else {
- memmove(from->hashes + hash_idx, from->hashes + hash_idx + 1,
- (from->n_hashes - (hash_idx + 1)) * sizeof *from->hashes);
- }
- from->n_hashes--;
-
- /* Shift load away from 'from' to 'to'. */
- from->tx_bytes -= delta;
- to->tx_bytes += delta;
-
- /* Arrange for flows to be revalidated. */
- ofproto_revalidate(port->bridge->ofproto, hash->iface_tag);
- hash->iface_idx = to->iface->port_ifidx;
- hash->iface_tag = tag_create_random();
-}
-
-static void
-bond_rebalance_port(struct port *port)
-{
- struct slave_balance bals[DP_MAX_PORTS];
- size_t n_bals;
- struct bond_entry *hashes[BOND_MASK + 1];
- struct slave_balance *b, *from, *to;
- struct bond_entry *e;
- size_t i;
-
- /* Sets up 'bals' to describe each of the port's interfaces, sorted in
- * descending order of tx_bytes, so that bals[0] represents the most
- * heavily loaded slave and bals[n_bals - 1] represents the least heavily
- * loaded slave.
- *
- * The code is a bit tricky: to avoid dynamically allocating a 'hashes'
- * array for each slave_balance structure, we sort our local array of
- * hashes in order by slave, so that all of the hashes for a given slave
- * become contiguous in memory, and then we point each 'hashes' members of
- * a slave_balance structure to the start of a contiguous group. */
- n_bals = port->n_ifaces;
- for (b = bals; b < &bals[n_bals]; b++) {
- b->iface = port->ifaces[b - bals];
- b->tx_bytes = 0;
- b->hashes = NULL;
- b->n_hashes = 0;
- }
- for (i = 0; i <= BOND_MASK; i++) {
- hashes[i] = &port->bond_hash[i];
- }
- qsort(hashes, BOND_MASK + 1, sizeof *hashes, compare_bond_entries);
- for (i = 0; i <= BOND_MASK; i++) {
- e = hashes[i];
- if (e->iface_idx >= 0 && e->iface_idx < port->n_ifaces) {
- b = &bals[e->iface_idx];
- b->tx_bytes += e->tx_bytes;
- if (!b->hashes) {
- b->hashes = &hashes[i];
- }
- b->n_hashes++;
- }
- }
- qsort(bals, n_bals, sizeof *bals, compare_slave_balance);
- log_bals(bals, n_bals, port);
-
- /* Discard slaves that aren't enabled (which were sorted to the back of the
- * array earlier). */
- while (!bals[n_bals - 1].iface->enabled) {
- n_bals--;
- if (!n_bals) {
- return;
- }
- }
-
- /* Shift load from the most-loaded slaves to the least-loaded slaves. */
- to = &bals[n_bals - 1];
- for (from = bals; from < to; ) {
- uint64_t overload = from->tx_bytes - to->tx_bytes;
- if (overload < to->tx_bytes >> 5 || overload < 100000) {
- /* The extra load on 'from' (and all less-loaded slaves), compared
- * to that of 'to' (the least-loaded slave), is less than ~3%, or
- * it is less than ~1Mbps. No point in rebalancing. */
- break;
- } else if (from->n_hashes == 1) {
- /* 'from' only carries a single MAC hash, so we can't shift any
- * load away from it, even though we want to. */
- from++;