2 * Copyright (c) 2008, 2009, 2010, 2011 Nicira Networks.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
26 #include "dynamic-string.h"
34 #include "poll-loop.h"
40 VLOG_DEFINE_THIS_MODULE(bond);
42 /* Bit-mask for hashing a flow down to a bucket.
43 * There are (BOND_MASK + 1) buckets. */
44 #define BOND_MASK 0xff
46 /* A hash bucket for mapping a flow to a slave.
47 * "struct bond" has an array of (BOND_MASK + 1) of these. */
49 struct bond_slave *slave; /* Assigned slave, NULL if unassigned. */
50 uint64_t tx_bytes; /* Count of bytes recently transmitted. */
51 tag_type tag; /* Tag for entry<->slave association. */
52 struct list list_node; /* In bond_slave's 'entries' list. */
55 /* A bond slave, that is, one of the links comprising a bond. */
57 struct hmap_node hmap_node; /* In struct bond's slaves hmap. */
58 struct bond *bond; /* The bond that contains this slave. */
59 void *aux; /* Client-provided handle for this slave. */
61 struct netdev *netdev; /* Network device, owned by the client. */
62 char *name; /* Name (a copy of netdev_get_name(netdev)). */
65 long long delay_expires; /* Time after which 'enabled' may change. */
66 bool up; /* Last link status read from netdev. */
67 bool enabled; /* May be chosen for flows? */
68 bool lacp_may_enable; /* LACP considers this interface bondable. */
69 tag_type tag; /* Tag associated with this slave. */
71 /* Rebalancing info. Used only by bond_rebalance(). */
72 struct list bal_node; /* In bond_rebalance()'s 'bals' list. */
73 struct list entries; /* 'struct bond_entry's assigned here. */
74 uint64_t tx_bytes; /* Sum across 'tx_bytes' of entries. */
76 /* BM_STABLE specific bonding info. */
77 uint32_t stb_id; /* ID used for 'stb_slaves' ordering. */
80 /* A bond, that is, a set of network devices grouped to improve performance or
83 struct hmap_node hmap_node; /* In 'all_bonds' hmap. */
84 char *name; /* Name provided by client. */
90 enum bond_mode balance; /* Balancing mode, one of BM_*. */
91 struct bond_slave *active_slave;
92 tag_type no_slaves_tag; /* Tag for flows when all slaves disabled. */
93 int updelay, downdelay; /* Delay before slave goes up/down, in ms. */
94 bool lacp_negotiated; /* LACP negotiations were successful. */
95 bool bond_revalidate; /* True if flows need revalidation. */
96 uint32_t basis; /* Basis for flow hash function. */
98 /* SLB specific bonding info. */
99 struct bond_entry *hash; /* An array of (BOND_MASK + 1) elements. */
100 int rebalance_interval; /* Interval between rebalances, in ms. */
101 long long int next_rebalance; /* Next rebalancing time. */
102 bool send_learning_packets;
104 /* BM_STABLE specific bonding info. */
105 tag_type stb_tag; /* Tag associated with this bond. */
108 struct netdev_monitor *monitor; /* detect == BLSM_CARRIER only. */
110 /* Legacy compatibility. */
111 long long int next_fake_iface_update; /* LLONG_MAX if disabled. */
113 /* Tag set saved for next bond_run(). This tag set is a kluge for cases
114 * where we can't otherwise provide revalidation feedback to the client.
115 * That's only unixctl commands now; I hope no other cases will arise. */
116 struct tag_set unixctl_tags;
119 static struct hmap all_bonds = HMAP_INITIALIZER(&all_bonds);
121 static void bond_entry_reset(struct bond *);
122 static struct bond_slave *bond_slave_lookup(struct bond *, const void *slave_);
123 static void bond_enable_slave(struct bond_slave *, bool enable,
125 static void bond_link_status_update(struct bond_slave *, struct tag_set *);
126 static void bond_choose_active_slave(struct bond *, struct tag_set *);
127 static bool bond_is_tcp_hash(const struct bond *);
128 static unsigned int bond_hash_src(const uint8_t mac[ETH_ADDR_LEN],
129 uint16_t vlan, uint32_t basis);
130 static unsigned int bond_hash_tcp(const struct flow *, uint16_t vlan,
132 static struct bond_entry *lookup_bond_entry(const struct bond *,
135 static tag_type bond_get_active_slave_tag(const struct bond *);
136 static struct bond_slave *choose_output_slave(const struct bond *,
139 static void bond_update_fake_slave_stats(struct bond *);
141 /* Attempts to parse 's' as the name of a bond balancing mode. If successful,
142 * stores the mode in '*balance' and returns true. Otherwise returns false
143 * without modifying '*balance'. */
145 bond_mode_from_string(enum bond_mode *balance, const char *s)
147 if (!strcmp(s, bond_mode_to_string(BM_TCP))) {
149 } else if (!strcmp(s, bond_mode_to_string(BM_SLB))) {
151 } else if (!strcmp(s, bond_mode_to_string(BM_STABLE))) {
152 *balance = BM_STABLE;
153 } else if (!strcmp(s, bond_mode_to_string(BM_AB))) {
161 /* Returns a string representing 'balance'. */
163 bond_mode_to_string(enum bond_mode balance) {
166 return "balance-tcp";
168 return "balance-slb";
172 return "active-backup";
178 /* Creates and returns a new bond whose configuration is initially taken from
181 * The caller should register each slave on the new bond by calling
182 * bond_slave_register(). */
184 bond_create(const struct bond_settings *s)
188 bond = xzalloc(sizeof *bond);
189 hmap_init(&bond->slaves);
190 bond->no_slaves_tag = tag_create_random();
191 bond->stb_tag = tag_create_random();
192 bond->next_fake_iface_update = LLONG_MAX;
193 bond->monitor = netdev_monitor_create();
195 bond_reconfigure(bond, s);
197 tag_set_init(&bond->unixctl_tags);
204 bond_destroy(struct bond *bond)
206 struct bond_slave *slave, *next_slave;
212 hmap_remove(&all_bonds, &bond->hmap_node);
214 HMAP_FOR_EACH_SAFE (slave, next_slave, hmap_node, &bond->slaves) {
215 hmap_remove(&bond->slaves, &slave->hmap_node);
216 /* Client owns 'slave->netdev'. */
220 hmap_destroy(&bond->slaves);
224 netdev_monitor_destroy(bond->monitor);
230 /* Updates 'bond''s overall configuration to 's'.
232 * The caller should register each slave on 'bond' by calling
233 * bond_slave_register(). This is optional if none of the slaves'
234 * configuration has changed. In any case it can't hurt.
236 * Returns true if the configuration has changed in such a way that requires
240 bond_reconfigure(struct bond *bond, const struct bond_settings *s)
242 bool revalidate = false;
244 if (!bond->name || strcmp(bond->name, s->name)) {
246 hmap_remove(&all_bonds, &bond->hmap_node);
249 bond->name = xstrdup(s->name);
250 hmap_insert(&all_bonds, &bond->hmap_node, hash_string(bond->name, 0));
253 bond->updelay = s->up_delay;
254 bond->downdelay = s->down_delay;
255 bond->rebalance_interval = s->rebalance_interval;
257 if (bond->balance != s->balance) {
258 bond->balance = s->balance;
262 if (bond->basis != s->basis) {
263 bond->basis = s->basis;
268 if (bond->next_fake_iface_update == LLONG_MAX) {
269 bond->next_fake_iface_update = time_msec();
272 bond->next_fake_iface_update = LLONG_MAX;
275 if (bond->bond_revalidate) {
277 bond->bond_revalidate = false;
280 if (bond->balance == BM_AB || !bond->hash || revalidate) {
281 bond_entry_reset(bond);
288 bond_slave_set_netdev__(struct bond *bond, struct bond_slave *slave,
289 struct netdev *netdev)
291 if (slave->netdev != netdev) {
293 netdev_monitor_remove(bond->monitor, slave->netdev);
295 netdev_monitor_add(bond->monitor, netdev);
296 slave->netdev = netdev;
300 /* Registers 'slave_' as a slave of 'bond'. The 'slave_' pointer is an
301 * arbitrary client-provided pointer that uniquely identifies a slave within a
302 * bond. If 'slave_' already exists within 'bond' then this function
303 * reconfigures the existing slave.
305 * 'stb_id' is used in BM_STABLE bonds to guarantee consistent slave choices
306 * across restarts and distributed vswitch instances. It should be unique per
307 * slave, and preferably consistent across restarts and reconfigurations.
309 * 'netdev' must be the network device that 'slave_' represents. It is owned
310 * by the client, so the client must not close it before either unregistering
311 * 'slave_' or destroying 'bond'.
314 bond_slave_register(struct bond *bond, void *slave_, uint32_t stb_id,
315 struct netdev *netdev)
317 struct bond_slave *slave = bond_slave_lookup(bond, slave_);
320 slave = xzalloc(sizeof *slave);
322 hmap_insert(&bond->slaves, &slave->hmap_node, hash_pointer(slave_, 0));
325 slave->delay_expires = LLONG_MAX;
326 slave->up = netdev_get_carrier(netdev);
327 slave->name = xstrdup(netdev_get_name(netdev));
328 bond->bond_revalidate = true;
330 slave->enabled = false;
331 bond_enable_slave(slave, slave->up, NULL);
334 if (slave->stb_id != stb_id) {
335 slave->stb_id = stb_id;
336 bond->bond_revalidate = true;
339 bond_slave_set_netdev__(bond, slave, netdev);
342 slave->name = xstrdup(netdev_get_name(netdev));
345 /* Updates the network device to be used with 'slave_' to 'netdev'.
347 * This is useful if the caller closes and re-opens the network device
348 * registered with bond_slave_register() but doesn't need to change anything
351 bond_slave_set_netdev(struct bond *bond, void *slave_, struct netdev *netdev)
353 struct bond_slave *slave = bond_slave_lookup(bond, slave_);
355 bond_slave_set_netdev__(bond, slave, netdev);
359 /* Unregisters 'slave_' from 'bond'. If 'bond' does not contain such a slave
360 * then this function has no effect.
362 * Unregistering a slave invalidates all flows. */
364 bond_slave_unregister(struct bond *bond, const void *slave_)
366 struct bond_slave *slave = bond_slave_lookup(bond, slave_);
373 netdev_monitor_remove(bond->monitor, slave->netdev);
374 bond_enable_slave(slave, false, NULL);
376 del_active = bond->active_slave == slave;
378 struct bond_entry *e;
379 for (e = bond->hash; e <= &bond->hash[BOND_MASK]; e++) {
380 if (e->slave == slave) {
388 hmap_remove(&bond->slaves, &slave->hmap_node);
389 /* Client owns 'slave->netdev'. */
396 bond_choose_active_slave(bond, &tags);
397 bond->send_learning_packets = true;
401 /* Should be called on each slave in 'bond' before bond_run() to indicate the
402 * results of lacp_slave_may_enable() on 'slave_'. */
404 bond_slave_set_lacp_may_enable(struct bond *bond, void *slave_,
407 bond_slave_lookup(bond, slave_)->lacp_may_enable = may_enable;
410 /* Performs periodic maintenance on 'bond'. The caller must provide 'tags' to
411 * allow tagged flows to be invalidated.
413 * The caller should check bond_should_send_learning_packets() afterward. */
415 bond_run(struct bond *bond, struct tag_set *tags, bool lacp_negotiated)
417 struct bond_slave *slave;
418 bool is_tcp_hash = bond_is_tcp_hash(bond);
420 bond->lacp_negotiated = lacp_negotiated;
422 /* Update link status. */
423 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
424 slave->up = netdev_get_carrier(slave->netdev);
428 netdev_monitor_flush(bond->monitor);
431 /* Enable slaves based on link status and LACP feedback. */
432 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
433 bond_link_status_update(slave, tags);
435 if (!bond->active_slave || !bond->active_slave->enabled) {
436 bond_choose_active_slave(bond, tags);
439 /* Update fake bond interface stats. */
440 if (time_msec() >= bond->next_fake_iface_update) {
441 bond_update_fake_slave_stats(bond);
442 bond->next_fake_iface_update = time_msec() + 1000;
445 if (is_tcp_hash != bond_is_tcp_hash(bond)) {
446 bond->bond_revalidate = true;
449 if (bond->bond_revalidate) {
450 bond->bond_revalidate = false;
452 bond_entry_reset(bond);
453 if (bond->balance != BM_STABLE) {
454 struct bond_slave *slave;
456 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
457 tag_set_add(tags, slave->tag);
460 tag_set_add(tags, bond->stb_tag);
462 tag_set_add(tags, bond->no_slaves_tag);
465 /* Invalidate any tags required by */
466 tag_set_union(tags, &bond->unixctl_tags);
467 tag_set_init(&bond->unixctl_tags);
470 /* Causes poll_block() to wake up when 'bond' needs something to be done. */
472 bond_wait(struct bond *bond)
474 struct bond_slave *slave;
476 netdev_monitor_poll_wait(bond->monitor);
478 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
479 if (slave->delay_expires != LLONG_MAX) {
480 poll_timer_wait_until(slave->delay_expires);
484 if (bond->next_fake_iface_update != LLONG_MAX) {
485 poll_timer_wait_until(bond->next_fake_iface_update);
488 /* Ensure that any saved tags get revalidated right away. */
489 if (!tag_set_is_empty(&bond->unixctl_tags)) {
490 poll_immediate_wake();
493 /* We don't wait for bond->next_rebalance because rebalancing can only run
494 * at a flow account checkpoint. ofproto does checkpointing on its own
495 * schedule and bond_rebalance() gets called afterward, so we'd just be
496 * waking up for no purpose. */
499 /* MAC learning table interaction. */
502 may_send_learning_packets(const struct bond *bond)
504 return !bond->lacp_negotiated && bond->balance != BM_AB;
507 /* Returns true if 'bond' needs the client to send out packets to assist with
508 * MAC learning on 'bond'. If this function returns true, then the client
509 * should iterate through its MAC learning table for the bridge on which 'bond'
510 * is located. For each MAC that has been learned on a port other than 'bond',
511 * it should call bond_send_learning_packet().
513 * This function will only return true if 'bond' is in SLB mode and LACP is not
514 * negotiated. Otherwise sending learning packets isn't necessary.
516 * Calling this function resets the state that it checks. */
518 bond_should_send_learning_packets(struct bond *bond)
520 bool send = bond->send_learning_packets && may_send_learning_packets(bond);
521 bond->send_learning_packets = false;
525 /* Sends a gratuitous learning packet on 'bond' from 'eth_src' on 'vlan'.
527 * See bond_should_send_learning_packets() for description of usage. */
529 bond_send_learning_packet(struct bond *bond,
530 const uint8_t eth_src[ETH_ADDR_LEN],
533 struct bond_slave *slave;
534 struct ofpbuf packet;
538 assert(may_send_learning_packets(bond));
539 if (!bond->active_slave) {
540 /* Nowhere to send the learning packet. */
544 memset(&flow, 0, sizeof flow);
545 memcpy(flow.dl_src, eth_src, ETH_ADDR_LEN);
546 slave = choose_output_slave(bond, &flow, vlan);
548 ofpbuf_init(&packet, 0);
549 compose_benign_packet(&packet, "Open vSwitch Bond Failover", 0xf177,
552 eth_set_vlan_tci(&packet, htons(vlan));
554 error = netdev_send(slave->netdev, &packet);
555 ofpbuf_uninit(&packet);
560 /* Checks whether a packet that arrived on 'slave_' within 'bond', with an
561 * Ethernet destination address of 'eth_dst', should be admitted.
563 * The return value is one of the following:
565 * - BV_ACCEPT: Admit the packet.
567 * - BV_DROP: Drop the packet.
569 * - BV_DROP_IF_MOVED: Consult the MAC learning table for the packet's
570 * Ethernet source address and VLAN. If there is none, or if the packet
571 * is on the learned port, then admit the packet. If a different port has
572 * been learned, however, drop the packet (and do not use it for MAC
576 bond_check_admissibility(struct bond *bond, const void *slave_,
577 const uint8_t eth_dst[ETH_ADDR_LEN], tag_type *tags)
579 /* Admit all packets if LACP has been negotiated, because that means that
580 * the remote switch is aware of the bond and will "do the right thing". */
581 if (bond->lacp_negotiated) {
585 /* Drop all multicast packets on inactive slaves. */
586 if (eth_addr_is_multicast(eth_dst)) {
587 *tags |= bond_get_active_slave_tag(bond);
588 if (bond->active_slave != bond_slave_lookup(bond, slave_)) {
593 /* Drop all packets for which we have learned a different input port,
594 * because we probably sent the packet on one slave and got it back on the
595 * other. Gratuitous ARP packets are an exception to this rule: the host
596 * has moved to another switch. The exception to the exception is if we
597 * locked the learning table to avoid reflections on bond slaves. */
598 return BV_DROP_IF_MOVED;
601 /* Returns the slave (registered on 'bond' by bond_slave_register()) to which
602 * a packet with the given 'flow' and 'vlan' should be forwarded. Returns
603 * NULL if the packet should be dropped because no slaves are enabled.
605 * 'vlan' is not necessarily the same as 'flow->vlan_tci'. First, 'vlan'
606 * should be a VID only (i.e. excluding the PCP bits). Second,
607 * 'flow->vlan_tci' is the VLAN TCI that appeared on the packet (so it will be
608 * nonzero only for trunk ports), whereas 'vlan' is the logical VLAN that the
609 * packet belongs to (so for an access port it will be the access port's VLAN).
611 * Adds a tag to '*tags' that associates the flow with the returned slave.
614 bond_choose_output_slave(struct bond *bond, const struct flow *flow,
615 uint16_t vlan, tag_type *tags)
617 struct bond_slave *slave = choose_output_slave(bond, flow, vlan);
619 *tags |= bond->balance == BM_STABLE ? bond->stb_tag : slave->tag;
622 *tags |= bond->no_slaves_tag;
630 bond_is_balanced(const struct bond *bond)
632 return bond->balance == BM_SLB || bond->balance == BM_TCP;
635 /* Notifies 'bond' that 'n_bytes' bytes were sent in 'flow' within 'vlan'. */
637 bond_account(struct bond *bond, const struct flow *flow, uint16_t vlan,
641 if (bond_is_balanced(bond)) {
642 lookup_bond_entry(bond, flow, vlan)->tx_bytes += n_bytes;
646 static struct bond_slave *
647 bond_slave_from_bal_node(struct list *bal)
649 return CONTAINER_OF(bal, struct bond_slave, bal_node);
653 log_bals(struct bond *bond, const struct list *bals)
655 if (VLOG_IS_DBG_ENABLED()) {
656 struct ds ds = DS_EMPTY_INITIALIZER;
657 const struct bond_slave *slave;
659 LIST_FOR_EACH (slave, bal_node, bals) {
661 ds_put_char(&ds, ',');
663 ds_put_format(&ds, " %s %"PRIu64"kB",
664 slave->name, slave->tx_bytes / 1024);
666 if (!slave->enabled) {
667 ds_put_cstr(&ds, " (disabled)");
669 if (!list_is_empty(&slave->entries)) {
670 struct bond_entry *e;
672 ds_put_cstr(&ds, " (");
673 LIST_FOR_EACH (e, list_node, &slave->entries) {
674 if (&e->list_node != list_front(&slave->entries)) {
675 ds_put_cstr(&ds, " + ");
677 ds_put_format(&ds, "h%td: %"PRIu64"kB",
678 e - bond->hash, e->tx_bytes / 1024);
680 ds_put_cstr(&ds, ")");
683 VLOG_DBG("bond %s:%s", bond->name, ds_cstr(&ds));
688 /* Shifts 'hash' from its current slave to 'to'. */
690 bond_shift_load(struct bond_entry *hash, struct bond_slave *to,
693 struct bond_slave *from = hash->slave;
694 struct bond *bond = from->bond;
695 uint64_t delta = hash->tx_bytes;
697 VLOG_INFO("bond %s: shift %"PRIu64"kB of load (with hash %td) "
698 "from %s to %s (now carrying %"PRIu64"kB and "
699 "%"PRIu64"kB load, respectively)",
700 bond->name, delta / 1024, hash - bond->hash,
701 from->name, to->name,
702 (from->tx_bytes - delta) / 1024,
703 (to->tx_bytes + delta) / 1024);
705 /* Shift load away from 'from' to 'to'. */
706 from->tx_bytes -= delta;
707 to->tx_bytes += delta;
709 /* Arrange for flows to be revalidated. */
710 tag_set_add(set, hash->tag);
712 hash->tag = tag_create_random();
715 /* Pick and returns a bond_entry to migrate to 'to' (the least-loaded slave),
716 * given that doing so must decrease the ratio of the load on the two slaves by
717 * at least 0.1. Returns NULL if there is no appropriate entry.
719 * The list of entries isn't sorted. I don't know of a reason to prefer to
720 * shift away small hashes or large hashes. */
721 static struct bond_entry *
722 choose_entry_to_migrate(const struct bond_slave *from, uint64_t to_tx_bytes)
724 struct bond_entry *e;
726 if (list_is_short(&from->entries)) {
727 /* 'from' carries no more than one MAC hash, so shifting load away from
728 * it would be pointless. */
732 LIST_FOR_EACH (e, list_node, &from->entries) {
733 double old_ratio, new_ratio;
736 if (to_tx_bytes == 0) {
737 /* Nothing on the new slave, move it. */
742 old_ratio = (double)from->tx_bytes / to_tx_bytes;
743 new_ratio = (double)(from->tx_bytes - delta) / (to_tx_bytes + delta);
744 if (old_ratio - new_ratio > 0.1) {
745 /* Would decrease the ratio, move it. */
753 /* Inserts 'slave' into 'bals' so that descending order of 'tx_bytes' is
756 insert_bal(struct list *bals, struct bond_slave *slave)
758 struct bond_slave *pos;
760 LIST_FOR_EACH (pos, bal_node, bals) {
761 if (slave->tx_bytes > pos->tx_bytes) {
765 list_insert(&pos->bal_node, &slave->bal_node);
768 /* Removes 'slave' from its current list and then inserts it into 'bals' so
769 * that descending order of 'tx_bytes' is maintained. */
771 reinsert_bal(struct list *bals, struct bond_slave *slave)
773 list_remove(&slave->bal_node);
774 insert_bal(bals, slave);
777 /* If 'bond' needs rebalancing, does so.
779 * The caller should have called bond_account() for each active flow, to ensure
780 * that flow data is consistently accounted at this point. */
782 bond_rebalance(struct bond *bond, struct tag_set *tags)
784 struct bond_slave *slave;
785 struct bond_entry *e;
788 if (!bond_is_balanced(bond) || time_msec() < bond->next_rebalance) {
791 bond->next_rebalance = time_msec() + bond->rebalance_interval;
793 /* Add each bond_entry to its slave's 'entries' list.
794 * Compute each slave's tx_bytes as the sum of its entries' tx_bytes. */
795 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
797 list_init(&slave->entries);
799 for (e = &bond->hash[0]; e <= &bond->hash[BOND_MASK]; e++) {
800 if (e->slave && e->tx_bytes) {
801 e->slave->tx_bytes += e->tx_bytes;
802 list_push_back(&e->slave->entries, &e->list_node);
806 /* Add enabled slaves to 'bals' in descending order of tx_bytes.
808 * XXX This is O(n**2) in the number of slaves but it could be O(n lg n)
809 * with a proper list sort algorithm. */
811 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
812 if (slave->enabled) {
813 insert_bal(&bals, slave);
816 log_bals(bond, &bals);
818 /* Shift load from the most-loaded slaves to the least-loaded slaves. */
819 while (!list_is_short(&bals)) {
820 struct bond_slave *from = bond_slave_from_bal_node(list_front(&bals));
821 struct bond_slave *to = bond_slave_from_bal_node(list_back(&bals));
824 overload = from->tx_bytes - to->tx_bytes;
825 if (overload < to->tx_bytes >> 5 || overload < 100000) {
826 /* The extra load on 'from' (and all less-loaded slaves), compared
827 * to that of 'to' (the least-loaded slave), is less than ~3%, or
828 * it is less than ~1Mbps. No point in rebalancing. */
832 /* 'from' is carrying significantly more load than 'to', and that load
833 * is split across at least two different hashes. */
834 e = choose_entry_to_migrate(from, to->tx_bytes);
836 bond_shift_load(e, to, tags);
838 /* Delete element from from->entries.
840 * We don't add the element to to->hashes. That would only allow
841 * 'e' to be migrated to another slave in this rebalancing run, and
842 * there is no point in doing that. */
843 list_remove(&e->list_node);
845 /* Re-sort 'bals'. */
846 reinsert_bal(&bals, from);
847 reinsert_bal(&bals, to);
849 /* Can't usefully migrate anything away from 'from'.
850 * Don't reconsider it. */
851 list_remove(&from->bal_node);
855 /* Implement exponentially weighted moving average. A weight of 1/2 causes
856 * historical data to decay to <1% in 7 rebalancing runs. 1,000,000 bytes
857 * take 20 rebalancing runs to decay to 0 and get deleted entirely. */
858 for (e = &bond->hash[0]; e <= &bond->hash[BOND_MASK]; e++) {
866 /* Bonding unixctl user interface functions. */
869 bond_find(const char *name)
873 HMAP_FOR_EACH_WITH_HASH (bond, hmap_node, hash_string(name, 0),
875 if (!strcmp(bond->name, name)) {
882 static struct bond_slave *
883 bond_lookup_slave(struct bond *bond, const char *slave_name)
885 struct bond_slave *slave;
887 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
888 if (!strcmp(slave->name, slave_name)) {
896 bond_unixctl_list(struct unixctl_conn *conn,
897 const char *args OVS_UNUSED, void *aux OVS_UNUSED)
899 struct ds ds = DS_EMPTY_INITIALIZER;
900 const struct bond *bond;
902 ds_put_cstr(&ds, "bond\ttype\tslaves\n");
904 HMAP_FOR_EACH (bond, hmap_node, &all_bonds) {
905 const struct bond_slave *slave;
908 ds_put_format(&ds, "%s\t%s\t",
909 bond->name, bond_mode_to_string(bond->balance));
912 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
914 ds_put_cstr(&ds, ", ");
916 ds_put_cstr(&ds, slave->name);
918 ds_put_char(&ds, '\n');
920 unixctl_command_reply(conn, 200, ds_cstr(&ds));
925 bond_unixctl_show(struct unixctl_conn *conn,
926 const char *args, void *aux OVS_UNUSED)
928 struct ds ds = DS_EMPTY_INITIALIZER;
929 const struct bond_slave *slave;
930 const struct bond *bond;
932 bond = bond_find(args);
934 unixctl_command_reply(conn, 501, "no such bond");
938 ds_put_format(&ds, "bond_mode: %s\n",
939 bond_mode_to_string(bond->balance));
941 if (bond->balance != BM_AB) {
942 ds_put_format(&ds, "bond-hash-algorithm: %s\n",
943 bond_is_tcp_hash(bond) ? "balance-tcp" : "balance-slb");
946 ds_put_format(&ds, "bond-hash-basis: %"PRIu32"\n", bond->basis);
948 ds_put_format(&ds, "updelay: %d ms\n", bond->updelay);
949 ds_put_format(&ds, "downdelay: %d ms\n", bond->downdelay);
951 if (bond_is_balanced(bond)) {
952 ds_put_format(&ds, "next rebalance: %lld ms\n",
953 bond->next_rebalance - time_msec());
956 ds_put_format(&ds, "lacp_negotiated: %s\n",
957 bond->lacp_negotiated ? "true" : "false");
959 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
960 struct bond_entry *be;
963 ds_put_format(&ds, "\nslave %s: %s\n",
964 slave->name, slave->enabled ? "enabled" : "disabled");
965 if (slave == bond->active_slave) {
966 ds_put_cstr(&ds, "\tactive slave\n");
968 if (slave->delay_expires != LLONG_MAX) {
969 ds_put_format(&ds, "\t%s expires in %lld ms\n",
970 slave->enabled ? "downdelay" : "updelay",
971 slave->delay_expires - time_msec());
974 ds_put_format(&ds, "\tlacp_may_enable: %s\n",
975 slave->lacp_may_enable ? "true" : "false");
977 if (!bond_is_balanced(bond)) {
982 for (be = bond->hash; be <= &bond->hash[BOND_MASK]; be++) {
983 int hash = be - bond->hash;
985 if (be->slave != slave) {
989 ds_put_format(&ds, "\thash %d: %"PRIu64" kB load\n",
990 hash, be->tx_bytes / 1024);
992 if (bond->balance != BM_SLB) {
996 /* XXX How can we list the MACs assigned to hashes? */
999 unixctl_command_reply(conn, 200, ds_cstr(&ds));
1004 bond_unixctl_migrate(struct unixctl_conn *conn, const char *args_,
1005 void *aux OVS_UNUSED)
1007 char *args = (char *) args_;
1008 char *save_ptr = NULL;
1009 char *bond_s, *hash_s, *slave_s;
1011 struct bond_slave *slave;
1012 struct bond_entry *entry;
1015 bond_s = strtok_r(args, " ", &save_ptr);
1016 hash_s = strtok_r(NULL, " ", &save_ptr);
1017 slave_s = strtok_r(NULL, " ", &save_ptr);
1019 unixctl_command_reply(conn, 501,
1020 "usage: bond/migrate BOND HASH SLAVE");
1024 bond = bond_find(bond_s);
1026 unixctl_command_reply(conn, 501, "no such bond");
1030 if (bond->balance != BM_SLB) {
1031 unixctl_command_reply(conn, 501, "not an SLB bond");
1035 if (strspn(hash_s, "0123456789") == strlen(hash_s)) {
1036 hash = atoi(hash_s) & BOND_MASK;
1038 unixctl_command_reply(conn, 501, "bad hash");
1042 slave = bond_lookup_slave(bond, slave_s);
1044 unixctl_command_reply(conn, 501, "no such slave");
1048 if (!slave->enabled) {
1049 unixctl_command_reply(conn, 501, "cannot migrate to disabled slave");
1053 entry = &bond->hash[hash];
1054 tag_set_add(&bond->unixctl_tags, entry->tag);
1055 entry->slave = slave;
1056 entry->tag = tag_create_random();
1057 unixctl_command_reply(conn, 200, "migrated");
1061 bond_unixctl_set_active_slave(struct unixctl_conn *conn, const char *args_,
1062 void *aux OVS_UNUSED)
1064 char *args = (char *) args_;
1065 char *save_ptr = NULL;
1066 char *bond_s, *slave_s;
1068 struct bond_slave *slave;
1070 bond_s = strtok_r(args, " ", &save_ptr);
1071 slave_s = strtok_r(NULL, " ", &save_ptr);
1073 unixctl_command_reply(conn, 501,
1074 "usage: bond/set-active-slave BOND SLAVE");
1078 bond = bond_find(bond_s);
1080 unixctl_command_reply(conn, 501, "no such bond");
1084 slave = bond_lookup_slave(bond, slave_s);
1086 unixctl_command_reply(conn, 501, "no such slave");
1090 if (!slave->enabled) {
1091 unixctl_command_reply(conn, 501, "cannot make disabled slave active");
1095 if (bond->active_slave != slave) {
1096 tag_set_add(&bond->unixctl_tags, bond_get_active_slave_tag(bond));
1097 bond->active_slave = slave;
1098 bond->active_slave->tag = tag_create_random();
1099 VLOG_INFO("bond %s: active interface is now %s",
1100 bond->name, slave->name);
1101 bond->send_learning_packets = true;
1102 unixctl_command_reply(conn, 200, "done");
1104 unixctl_command_reply(conn, 200, "no change");
1109 enable_slave(struct unixctl_conn *conn, const char *args_, bool enable)
1111 char *args = (char *) args_;
1112 char *save_ptr = NULL;
1113 char *bond_s, *slave_s;
1115 struct bond_slave *slave;
1117 bond_s = strtok_r(args, " ", &save_ptr);
1118 slave_s = strtok_r(NULL, " ", &save_ptr);
1120 char *usage = xasprintf("usage: bond/%s-slave BOND SLAVE",
1121 enable ? "enable" : "disable");
1122 unixctl_command_reply(conn, 501, usage);
1127 bond = bond_find(bond_s);
1129 unixctl_command_reply(conn, 501, "no such bond");
1133 slave = bond_lookup_slave(bond, slave_s);
1135 unixctl_command_reply(conn, 501, "no such slave");
1139 bond_enable_slave(slave, enable, &bond->unixctl_tags);
1140 unixctl_command_reply(conn, 501, enable ? "enabled" : "disabled");
1144 bond_unixctl_enable_slave(struct unixctl_conn *conn, const char *args,
1145 void *aux OVS_UNUSED)
1147 enable_slave(conn, args, true);
1151 bond_unixctl_disable_slave(struct unixctl_conn *conn, const char *args,
1152 void *aux OVS_UNUSED)
1154 enable_slave(conn, args, false);
1158 bond_unixctl_hash(struct unixctl_conn *conn, const char *args_,
1159 void *aux OVS_UNUSED)
1161 char *args = (char *) args_;
1162 uint8_t mac[ETH_ADDR_LEN];
1167 char *mac_s, *vlan_s, *basis_s;
1168 char *save_ptr = NULL;
1170 mac_s = strtok_r(args, " ", &save_ptr);
1171 vlan_s = strtok_r(NULL, " ", &save_ptr);
1172 basis_s = strtok_r(NULL, " ", &save_ptr);
1175 if (sscanf(vlan_s, "%u", &vlan) != 1) {
1176 unixctl_command_reply(conn, 501, "invalid vlan");
1180 vlan = OFP_VLAN_NONE;
1184 if (sscanf(basis_s, "%"PRIu32, &basis) != 1) {
1185 unixctl_command_reply(conn, 501, "invalid basis");
1192 if (sscanf(mac_s, ETH_ADDR_SCAN_FMT, ETH_ADDR_SCAN_ARGS(mac))
1193 == ETH_ADDR_SCAN_COUNT) {
1194 hash = bond_hash_src(mac, vlan, basis) & BOND_MASK;
1196 hash_cstr = xasprintf("%u", hash);
1197 unixctl_command_reply(conn, 200, hash_cstr);
1200 unixctl_command_reply(conn, 501, "invalid mac");
1207 unixctl_command_register("bond/list", bond_unixctl_list, NULL);
1208 unixctl_command_register("bond/show", bond_unixctl_show, NULL);
1209 unixctl_command_register("bond/migrate", bond_unixctl_migrate, NULL);
1210 unixctl_command_register("bond/set-active-slave",
1211 bond_unixctl_set_active_slave, NULL);
1212 unixctl_command_register("bond/enable-slave", bond_unixctl_enable_slave,
1214 unixctl_command_register("bond/disable-slave", bond_unixctl_disable_slave,
1216 unixctl_command_register("bond/hash", bond_unixctl_hash, NULL);
1220 bond_entry_reset(struct bond *bond)
1222 if (bond->balance != BM_AB) {
1223 size_t hash_len = (BOND_MASK + 1) * sizeof *bond->hash;
1226 bond->hash = xmalloc(hash_len);
1228 memset(bond->hash, 0, hash_len);
1230 bond->next_rebalance = time_msec() + bond->rebalance_interval;
1237 static struct bond_slave *
1238 bond_slave_lookup(struct bond *bond, const void *slave_)
1240 struct bond_slave *slave;
1242 HMAP_FOR_EACH_IN_BUCKET (slave, hmap_node, hash_pointer(slave_, 0),
1244 if (slave->aux == slave_) {
1253 bond_enable_slave(struct bond_slave *slave, bool enable, struct tag_set *tags)
1255 struct bond *bond = slave->bond;
1256 slave->delay_expires = LLONG_MAX;
1257 if (enable != slave->enabled) {
1258 slave->enabled = enable;
1259 if (!slave->enabled) {
1260 VLOG_WARN("interface %s: disabled", slave->name);
1262 tag_set_add(tags, slave->tag);
1265 VLOG_WARN("interface %s: enabled", slave->name);
1266 slave->tag = tag_create_random();
1269 if (bond->balance == BM_STABLE) {
1270 bond->bond_revalidate = true;
1276 bond_link_status_update(struct bond_slave *slave, struct tag_set *tags)
1278 struct bond *bond = slave->bond;
1281 up = slave->up && slave->lacp_may_enable;
1282 if ((up == slave->enabled) != (slave->delay_expires == LLONG_MAX)) {
1283 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 20);
1284 VLOG_INFO_RL(&rl, "interface %s: link state %s",
1285 slave->name, up ? "up" : "down");
1286 if (up == slave->enabled) {
1287 slave->delay_expires = LLONG_MAX;
1288 VLOG_INFO_RL(&rl, "interface %s: will not be %s",
1289 slave->name, up ? "disabled" : "enabled");
1291 int delay = (bond->lacp_negotiated ? 0
1292 : up ? bond->updelay : bond->downdelay);
1293 slave->delay_expires = time_msec() + delay;
1295 VLOG_INFO_RL(&rl, "interface %s: will be %s if it stays %s "
1298 up ? "enabled" : "disabled",
1305 if (time_msec() >= slave->delay_expires) {
1306 bond_enable_slave(slave, up, tags);
1311 bond_is_tcp_hash(const struct bond *bond)
1313 return (bond->balance == BM_TCP || bond->balance == BM_STABLE)
1314 && bond->lacp_negotiated;
1318 bond_hash_src(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan, uint32_t basis)
1320 return hash_3words(hash_bytes(mac, ETH_ADDR_LEN, 0), vlan, basis);
1324 bond_hash_tcp(const struct flow *flow, uint16_t vlan, uint32_t basis)
1326 struct flow hash_flow = *flow;
1327 hash_flow.vlan_tci = htons(vlan);
1329 /* The symmetric quality of this hash function is not required, but
1330 * flow_hash_symmetric_l4 already exists, and is sufficient for our
1331 * purposes, so we use it out of convenience. */
1332 return flow_hash_symmetric_l4(&hash_flow, basis);
1336 bond_hash(const struct bond *bond, const struct flow *flow, uint16_t vlan)
1338 assert(bond->balance != BM_AB);
1340 return (bond_is_tcp_hash(bond)
1341 ? bond_hash_tcp(flow, vlan, bond->basis)
1342 : bond_hash_src(flow->dl_src, vlan, bond->basis));
1345 static struct bond_entry *
1346 lookup_bond_entry(const struct bond *bond, const struct flow *flow,
1349 return &bond->hash[bond_hash(bond, flow, vlan) & BOND_MASK];
1352 /* This function uses Highest Random Weight hashing to choose an output slave.
1353 * This approach only reassigns a minimal number of flows when slaves are
1354 * enabled or disabled. Unfortunately, it has O(n) performance against the
1355 * number of slaves. There exist algorithms which are O(1), but have slightly
1356 * more complex implementations and require the use of memory. This may need
1357 * to be reimplemented if it becomes a performance bottleneck. */
1358 static struct bond_slave *
1359 choose_stb_slave(const struct bond *bond, const struct flow *flow,
1362 struct bond_slave *best, *slave;
1363 uint32_t best_hash, flow_hash;
1367 flow_hash = bond_hash(bond, flow, vlan);
1368 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1369 if (slave->enabled) {
1372 hash = hash_2words(flow_hash, slave->stb_id);
1373 if (!best || hash > best_hash) {
1383 static struct bond_slave *
1384 choose_output_slave(const struct bond *bond, const struct flow *flow,
1387 struct bond_entry *e;
1389 switch (bond->balance) {
1391 return bond->active_slave;
1394 return choose_stb_slave(bond, flow, vlan);
1397 e = lookup_bond_entry(bond, flow, vlan);
1398 if (!e->slave || !e->slave->enabled) {
1399 e->slave = CONTAINER_OF(hmap_random_node(&bond->slaves),
1400 struct bond_slave, hmap_node);
1401 if (!e->slave->enabled) {
1402 e->slave = bond->active_slave;
1404 e->tag = tag_create_random();
1413 static struct bond_slave *
1414 bond_choose_slave(const struct bond *bond)
1416 struct bond_slave *slave, *best;
1418 /* Find an enabled slave. */
1419 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1420 if (slave->enabled) {
1425 /* All interfaces are disabled. Find an interface that will be enabled
1426 * after its updelay expires. */
1428 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1429 if (slave->delay_expires != LLONG_MAX
1430 && slave->lacp_may_enable
1431 && (!best || slave->delay_expires < best->delay_expires)) {
1439 bond_choose_active_slave(struct bond *bond, struct tag_set *tags)
1441 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 20);
1442 struct bond_slave *old_active_slave = bond->active_slave;
1444 bond->active_slave = bond_choose_slave(bond);
1445 if (bond->active_slave) {
1446 if (bond->active_slave->enabled) {
1447 VLOG_INFO_RL(&rl, "bond %s: active interface is now %s",
1448 bond->name, bond->active_slave->name);
1450 VLOG_INFO_RL(&rl, "bond %s: active interface is now %s, skipping "
1451 "remaining %lld ms updelay (since no interface was "
1452 "enabled)", bond->name, bond->active_slave->name,
1453 bond->active_slave->delay_expires - time_msec());
1454 bond_enable_slave(bond->active_slave, true, tags);
1457 if (!old_active_slave) {
1458 tag_set_add(tags, bond->no_slaves_tag);
1461 bond->send_learning_packets = true;
1462 } else if (old_active_slave) {
1463 VLOG_WARN_RL(&rl, "bond %s: all interfaces disabled", bond->name);
1467 /* Returns the tag for 'bond''s active slave, or 'bond''s no_slaves_tag if
1468 * there is no active slave. */
1470 bond_get_active_slave_tag(const struct bond *bond)
1472 return (bond->active_slave
1473 ? bond->active_slave->tag
1474 : bond->no_slaves_tag);
1477 /* Attempts to make the sum of the bond slaves' statistics appear on the fake
1478 * bond interface. */
1480 bond_update_fake_slave_stats(struct bond *bond)
1482 struct netdev_stats bond_stats;
1483 struct bond_slave *slave;
1484 struct netdev *bond_dev;
1486 memset(&bond_stats, 0, sizeof bond_stats);
1488 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1489 struct netdev_stats slave_stats;
1491 if (!netdev_get_stats(slave->netdev, &slave_stats)) {
1492 /* XXX: We swap the stats here because they are swapped back when
1493 * reported by the internal device. The reason for this is
1494 * internal devices normally represent packets going into the
1495 * system but when used as fake bond device they represent packets
1496 * leaving the system. We really should do this in the internal
1497 * device itself because changing it here reverses the counts from
1498 * the perspective of the switch. However, the internal device
1499 * doesn't know what type of device it represents so we have to do
1500 * it here for now. */
1501 bond_stats.tx_packets += slave_stats.rx_packets;
1502 bond_stats.tx_bytes += slave_stats.rx_bytes;
1503 bond_stats.rx_packets += slave_stats.tx_packets;
1504 bond_stats.rx_bytes += slave_stats.tx_bytes;
1508 if (!netdev_open_default(bond->name, &bond_dev)) {
1509 netdev_set_stats(bond_dev, &bond_stats);
1510 netdev_close(bond_dev);