2 * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
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"
35 #include "poll-loop.h"
42 VLOG_DEFINE_THIS_MODULE(bond);
44 /* Bit-mask for hashing a flow down to a bucket.
45 * There are (BOND_MASK + 1) buckets. */
46 #define BOND_MASK 0xff
48 /* A hash bucket for mapping a flow to a slave.
49 * "struct bond" has an array of (BOND_MASK + 1) of these. */
51 struct bond_slave *slave; /* Assigned slave, NULL if unassigned. */
52 uint64_t tx_bytes; /* Count of bytes recently transmitted. */
53 tag_type tag; /* Tag for entry<->slave association. */
54 struct list list_node; /* In bond_slave's 'entries' list. */
57 /* A bond slave, that is, one of the links comprising a bond. */
59 struct hmap_node hmap_node; /* In struct bond's slaves hmap. */
60 struct bond *bond; /* The bond that contains this slave. */
61 void *aux; /* Client-provided handle for this slave. */
63 struct netdev *netdev; /* Network device, owned by the client. */
64 unsigned int change_seq; /* Tracks changes in 'netdev'. */
65 char *name; /* Name (a copy of netdev_get_name(netdev)). */
68 long long delay_expires; /* Time after which 'enabled' may change. */
69 bool enabled; /* May be chosen for flows? */
70 bool may_enable; /* Client considers this slave bondable. */
71 tag_type tag; /* Tag associated with this slave. */
73 /* Rebalancing info. Used only by bond_rebalance(). */
74 struct list bal_node; /* In bond_rebalance()'s 'bals' list. */
75 struct list entries; /* 'struct bond_entry's assigned here. */
76 uint64_t tx_bytes; /* Sum across 'tx_bytes' of entries. */
78 /* BM_STABLE specific bonding info. */
79 uint32_t stb_id; /* ID used for 'stb_slaves' ordering. */
82 /* A bond, that is, a set of network devices grouped to improve performance or
85 struct hmap_node hmap_node; /* In 'all_bonds' hmap. */
86 char *name; /* Name provided by client. */
92 enum bond_mode balance; /* Balancing mode, one of BM_*. */
93 struct bond_slave *active_slave;
94 tag_type no_slaves_tag; /* Tag for flows when all slaves disabled. */
95 int updelay, downdelay; /* Delay before slave goes up/down, in ms. */
96 enum lacp_status lacp_status; /* Status of LACP negotiations. */
97 bool bond_revalidate; /* True if flows need revalidation. */
98 uint32_t basis; /* Basis for flow hash function. */
100 /* SLB specific bonding info. */
101 struct bond_entry *hash; /* An array of (BOND_MASK + 1) elements. */
102 int rebalance_interval; /* Interval between rebalances, in ms. */
103 long long int next_rebalance; /* Next rebalancing time. */
104 bool send_learning_packets;
106 /* BM_STABLE specific bonding info. */
107 tag_type stb_tag; /* Tag associated with this bond. */
109 /* Legacy compatibility. */
110 long long int next_fake_iface_update; /* LLONG_MAX if disabled. */
112 /* Tag set saved for next bond_run(). This tag set is a kluge for cases
113 * where we can't otherwise provide revalidation feedback to the client.
114 * That's only unixctl commands now; I hope no other cases will arise. */
115 struct tag_set unixctl_tags;
118 static struct hmap all_bonds = HMAP_INITIALIZER(&all_bonds);
120 static void bond_entry_reset(struct bond *);
121 static struct bond_slave *bond_slave_lookup(struct bond *, const void *slave_);
122 static void bond_enable_slave(struct bond_slave *, bool enable,
124 static void bond_link_status_update(struct bond_slave *, struct tag_set *);
125 static void bond_choose_active_slave(struct bond *, struct tag_set *);
126 static unsigned int bond_hash_src(const uint8_t mac[ETH_ADDR_LEN],
127 uint16_t vlan, uint32_t basis);
128 static unsigned int bond_hash_tcp(const struct flow *, uint16_t vlan,
130 static struct bond_entry *lookup_bond_entry(const struct bond *,
133 static tag_type bond_get_active_slave_tag(const struct bond *);
134 static struct bond_slave *choose_output_slave(const struct bond *,
136 uint16_t vlan, tag_type *tags);
137 static void bond_update_fake_slave_stats(struct bond *);
139 /* Attempts to parse 's' as the name of a bond balancing mode. If successful,
140 * stores the mode in '*balance' and returns true. Otherwise returns false
141 * without modifying '*balance'. */
143 bond_mode_from_string(enum bond_mode *balance, const char *s)
145 if (!strcmp(s, bond_mode_to_string(BM_TCP))) {
147 } else if (!strcmp(s, bond_mode_to_string(BM_SLB))) {
149 } else if (!strcmp(s, bond_mode_to_string(BM_STABLE))) {
150 *balance = BM_STABLE;
151 } else if (!strcmp(s, bond_mode_to_string(BM_AB))) {
159 /* Returns a string representing 'balance'. */
161 bond_mode_to_string(enum bond_mode balance) {
164 return "balance-tcp";
166 return "balance-slb";
170 return "active-backup";
176 /* Creates and returns a new bond whose configuration is initially taken from
179 * The caller should register each slave on the new bond by calling
180 * bond_slave_register(). */
182 bond_create(const struct bond_settings *s)
186 bond = xzalloc(sizeof *bond);
187 hmap_init(&bond->slaves);
188 bond->no_slaves_tag = tag_create_random();
189 bond->stb_tag = tag_create_random();
190 bond->next_fake_iface_update = LLONG_MAX;
192 bond_reconfigure(bond, s);
194 tag_set_init(&bond->unixctl_tags);
201 bond_destroy(struct bond *bond)
203 struct bond_slave *slave, *next_slave;
209 hmap_remove(&all_bonds, &bond->hmap_node);
211 HMAP_FOR_EACH_SAFE (slave, next_slave, hmap_node, &bond->slaves) {
212 hmap_remove(&bond->slaves, &slave->hmap_node);
213 /* Client owns 'slave->netdev'. */
217 hmap_destroy(&bond->slaves);
224 /* Updates 'bond''s overall configuration to 's'.
226 * The caller should register each slave on 'bond' by calling
227 * bond_slave_register(). This is optional if none of the slaves'
228 * configuration has changed. In any case it can't hurt.
230 * Returns true if the configuration has changed in such a way that requires
234 bond_reconfigure(struct bond *bond, const struct bond_settings *s)
236 bool revalidate = false;
238 if (!bond->name || strcmp(bond->name, s->name)) {
240 hmap_remove(&all_bonds, &bond->hmap_node);
243 bond->name = xstrdup(s->name);
244 hmap_insert(&all_bonds, &bond->hmap_node, hash_string(bond->name, 0));
247 bond->updelay = s->up_delay;
248 bond->downdelay = s->down_delay;
250 if (bond->rebalance_interval != s->rebalance_interval) {
251 bond->rebalance_interval = s->rebalance_interval;
255 if (bond->balance != s->balance) {
256 bond->balance = s->balance;
260 if (bond->basis != s->basis) {
261 bond->basis = s->basis;
266 if (bond->next_fake_iface_update == LLONG_MAX) {
267 bond->next_fake_iface_update = time_msec();
270 bond->next_fake_iface_update = LLONG_MAX;
273 if (bond->bond_revalidate) {
275 bond->bond_revalidate = false;
278 if (bond->balance == BM_AB || !bond->hash || revalidate) {
279 bond_entry_reset(bond);
286 bond_slave_set_netdev__(struct bond_slave *slave, struct netdev *netdev)
288 if (slave->netdev != netdev) {
289 slave->netdev = netdev;
290 slave->change_seq = 0;
294 /* Registers 'slave_' as a slave of 'bond'. The 'slave_' pointer is an
295 * arbitrary client-provided pointer that uniquely identifies a slave within a
296 * bond. If 'slave_' already exists within 'bond' then this function
297 * reconfigures the existing slave.
299 * 'stb_id' is used in BM_STABLE bonds to guarantee consistent slave choices
300 * across restarts and distributed vswitch instances. It should be unique per
301 * slave, and preferably consistent across restarts and reconfigurations.
303 * 'netdev' must be the network device that 'slave_' represents. It is owned
304 * by the client, so the client must not close it before either unregistering
305 * 'slave_' or destroying 'bond'.
308 bond_slave_register(struct bond *bond, void *slave_, uint32_t stb_id,
309 struct netdev *netdev)
311 struct bond_slave *slave = bond_slave_lookup(bond, slave_);
314 slave = xzalloc(sizeof *slave);
316 hmap_insert(&bond->slaves, &slave->hmap_node, hash_pointer(slave_, 0));
319 slave->delay_expires = LLONG_MAX;
320 slave->name = xstrdup(netdev_get_name(netdev));
321 bond->bond_revalidate = true;
323 slave->enabled = false;
324 bond_enable_slave(slave, netdev_get_carrier(netdev), NULL);
327 if (slave->stb_id != stb_id) {
328 slave->stb_id = stb_id;
329 bond->bond_revalidate = true;
332 bond_slave_set_netdev__(slave, netdev);
335 slave->name = xstrdup(netdev_get_name(netdev));
338 /* Updates the network device to be used with 'slave_' to 'netdev'.
340 * This is useful if the caller closes and re-opens the network device
341 * registered with bond_slave_register() but doesn't need to change anything
344 bond_slave_set_netdev(struct bond *bond, void *slave_, struct netdev *netdev)
346 struct bond_slave *slave = bond_slave_lookup(bond, slave_);
348 bond_slave_set_netdev__(slave, netdev);
352 /* Unregisters 'slave_' from 'bond'. If 'bond' does not contain such a slave
353 * then this function has no effect.
355 * Unregistering a slave invalidates all flows. */
357 bond_slave_unregister(struct bond *bond, const void *slave_)
359 struct bond_slave *slave = bond_slave_lookup(bond, slave_);
366 bond_enable_slave(slave, false, NULL);
368 del_active = bond->active_slave == slave;
370 struct bond_entry *e;
371 for (e = bond->hash; e <= &bond->hash[BOND_MASK]; e++) {
372 if (e->slave == slave) {
380 hmap_remove(&bond->slaves, &slave->hmap_node);
381 /* Client owns 'slave->netdev'. */
388 bond_choose_active_slave(bond, &tags);
389 bond->send_learning_packets = true;
393 /* Should be called on each slave in 'bond' before bond_run() to indicate
394 * whether or not 'slave_' may be enabled. This function is intended to allow
395 * other protocols to have some impact on bonding decisions. For example LACP
396 * or high level link monitoring protocols may decide that a given slave should
397 * not be able to send traffic. */
399 bond_slave_set_may_enable(struct bond *bond, void *slave_, bool may_enable)
401 bond_slave_lookup(bond, slave_)->may_enable = may_enable;
404 /* Performs periodic maintenance on 'bond'. The caller must provide 'tags' to
405 * allow tagged flows to be invalidated.
407 * The caller should check bond_should_send_learning_packets() afterward. */
409 bond_run(struct bond *bond, struct tag_set *tags, enum lacp_status lacp_status)
411 struct bond_slave *slave;
413 if (bond->lacp_status != lacp_status) {
414 bond->lacp_status = lacp_status;
415 bond->bond_revalidate = true;
418 /* Enable slaves based on link status and LACP feedback. */
419 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
420 bond_link_status_update(slave, tags);
421 slave->change_seq = netdev_change_seq(slave->netdev);
423 if (!bond->active_slave || !bond->active_slave->enabled) {
424 bond_choose_active_slave(bond, tags);
427 /* Update fake bond interface stats. */
428 if (time_msec() >= bond->next_fake_iface_update) {
429 bond_update_fake_slave_stats(bond);
430 bond->next_fake_iface_update = time_msec() + 1000;
433 if (bond->bond_revalidate) {
434 bond->bond_revalidate = false;
436 bond_entry_reset(bond);
437 if (bond->balance != BM_STABLE) {
438 struct bond_slave *slave;
440 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
441 tag_set_add(tags, slave->tag);
444 tag_set_add(tags, bond->stb_tag);
446 tag_set_add(tags, bond->no_slaves_tag);
449 /* Invalidate any tags required by */
450 tag_set_union(tags, &bond->unixctl_tags);
451 tag_set_init(&bond->unixctl_tags);
454 /* Causes poll_block() to wake up when 'bond' needs something to be done. */
456 bond_wait(struct bond *bond)
458 struct bond_slave *slave;
460 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
461 if (slave->delay_expires != LLONG_MAX) {
462 poll_timer_wait_until(slave->delay_expires);
465 if (slave->change_seq != netdev_change_seq(slave->netdev)) {
466 poll_immediate_wake();
470 if (bond->next_fake_iface_update != LLONG_MAX) {
471 poll_timer_wait_until(bond->next_fake_iface_update);
474 /* Ensure that any saved tags get revalidated right away. */
475 if (!tag_set_is_empty(&bond->unixctl_tags)) {
476 poll_immediate_wake();
479 /* We don't wait for bond->next_rebalance because rebalancing can only run
480 * at a flow account checkpoint. ofproto does checkpointing on its own
481 * schedule and bond_rebalance() gets called afterward, so we'd just be
482 * waking up for no purpose. */
485 /* MAC learning table interaction. */
488 may_send_learning_packets(const struct bond *bond)
490 return bond->lacp_status == LACP_DISABLED
491 && bond->balance != BM_STABLE
492 && bond->active_slave;
495 /* Returns true if 'bond' needs the client to send out packets to assist with
496 * MAC learning on 'bond'. If this function returns true, then the client
497 * should iterate through its MAC learning table for the bridge on which 'bond'
498 * is located. For each MAC that has been learned on a port other than 'bond',
499 * it should call bond_compose_learning_packet().
501 * This function will only return true if 'bond' is in SLB or active-backup
502 * mode and LACP is not negotiated. Otherwise sending learning packets isn't
505 * Calling this function resets the state that it checks. */
507 bond_should_send_learning_packets(struct bond *bond)
509 bool send = bond->send_learning_packets && may_send_learning_packets(bond);
510 bond->send_learning_packets = false;
514 /* Sends a gratuitous learning packet on 'bond' from 'eth_src' on 'vlan'.
516 * See bond_should_send_learning_packets() for description of usage. The
517 * caller should send the composed packet on the port associated with
518 * port_aux and takes ownership of the returned ofpbuf. */
520 bond_compose_learning_packet(struct bond *bond,
521 const uint8_t eth_src[ETH_ADDR_LEN],
522 uint16_t vlan, void **port_aux)
524 struct bond_slave *slave;
525 struct ofpbuf *packet;
529 assert(may_send_learning_packets(bond));
531 memset(&flow, 0, sizeof flow);
532 memcpy(flow.dl_src, eth_src, ETH_ADDR_LEN);
533 slave = choose_output_slave(bond, &flow, vlan, &tags);
535 packet = ofpbuf_new(0);
536 compose_rarp(packet, eth_src);
538 eth_push_vlan(packet, htons(vlan));
541 *port_aux = slave->aux;
545 /* Checks whether a packet that arrived on 'slave_' within 'bond', with an
546 * Ethernet destination address of 'eth_dst', should be admitted.
548 * The return value is one of the following:
550 * - BV_ACCEPT: Admit the packet.
552 * - BV_DROP: Drop the packet.
554 * - BV_DROP_IF_MOVED: Consult the MAC learning table for the packet's
555 * Ethernet source address and VLAN. If there is none, or if the packet
556 * is on the learned port, then admit the packet. If a different port has
557 * been learned, however, drop the packet (and do not use it for MAC
561 bond_check_admissibility(struct bond *bond, const void *slave_,
562 const uint8_t eth_dst[ETH_ADDR_LEN], tag_type *tags)
564 struct bond_slave *slave = bond_slave_lookup(bond, slave_);
566 /* LACP bonds have very loose admissibility restrictions because we can
567 * assume the remote switch is aware of the bond and will "do the right
568 * thing". However, as a precaution we drop packets on disabled slaves
569 * because no correctly implemented partner switch should be sending
572 * If LACP is configured, but LACP negotiations have been unsuccessful, we
573 * drop all incoming traffic. */
574 switch (bond->lacp_status) {
575 case LACP_NEGOTIATED: return slave->enabled ? BV_ACCEPT : BV_DROP;
576 case LACP_CONFIGURED: return BV_DROP;
577 case LACP_DISABLED: break;
580 /* Drop all multicast packets on inactive slaves. */
581 if (eth_addr_is_multicast(eth_dst)) {
582 *tags |= bond_get_active_slave_tag(bond);
583 if (bond->active_slave != bond_slave_lookup(bond, slave_)) {
588 switch (bond->balance) {
590 /* Drop all packets which arrive on backup slaves. This is similar to
591 * how Linux bonding handles active-backup bonds. */
592 *tags |= bond_get_active_slave_tag(bond);
593 if (bond->active_slave != slave) {
594 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
596 VLOG_DBG_RL(&rl, "active-backup bond received packet on backup"
597 " slave (%s) destined for " ETH_ADDR_FMT,
598 slave->name, ETH_ADDR_ARGS(eth_dst));
604 /* TCP balanced bonds require successful LACP negotiated. Based on the
605 * above check, LACP is off on this bond. Therfore, we drop all
606 * incoming traffic. */
610 /* Drop all packets for which we have learned a different input port,
611 * because we probably sent the packet on one slave and got it back on
612 * the other. Gratuitous ARP packets are an exception to this rule:
613 * the host has moved to another switch. The exception to the
614 * exception is if we locked the learning table to avoid reflections on
616 return BV_DROP_IF_MOVED;
625 /* Returns the slave (registered on 'bond' by bond_slave_register()) to which
626 * a packet with the given 'flow' and 'vlan' should be forwarded. Returns
627 * NULL if the packet should be dropped because no slaves are enabled.
629 * 'vlan' is not necessarily the same as 'flow->vlan_tci'. First, 'vlan'
630 * should be a VID only (i.e. excluding the PCP bits). Second,
631 * 'flow->vlan_tci' is the VLAN TCI that appeared on the packet (so it will be
632 * nonzero only for trunk ports), whereas 'vlan' is the logical VLAN that the
633 * packet belongs to (so for an access port it will be the access port's VLAN).
635 * Adds a tag to '*tags' that associates the flow with the returned slave.
638 bond_choose_output_slave(struct bond *bond, const struct flow *flow,
639 uint16_t vlan, tag_type *tags)
641 struct bond_slave *slave = choose_output_slave(bond, flow, vlan, tags);
643 *tags |= bond->balance == BM_STABLE ? bond->stb_tag : slave->tag;
646 *tags |= bond->no_slaves_tag;
654 bond_is_balanced(const struct bond *bond)
656 return bond->rebalance_interval
657 && (bond->balance == BM_SLB || bond->balance == BM_TCP);
660 /* Notifies 'bond' that 'n_bytes' bytes were sent in 'flow' within 'vlan'. */
662 bond_account(struct bond *bond, const struct flow *flow, uint16_t vlan,
665 if (bond_is_balanced(bond)) {
666 lookup_bond_entry(bond, flow, vlan)->tx_bytes += n_bytes;
670 static struct bond_slave *
671 bond_slave_from_bal_node(struct list *bal)
673 return CONTAINER_OF(bal, struct bond_slave, bal_node);
677 log_bals(struct bond *bond, const struct list *bals)
679 if (VLOG_IS_DBG_ENABLED()) {
680 struct ds ds = DS_EMPTY_INITIALIZER;
681 const struct bond_slave *slave;
683 LIST_FOR_EACH (slave, bal_node, bals) {
685 ds_put_char(&ds, ',');
687 ds_put_format(&ds, " %s %"PRIu64"kB",
688 slave->name, slave->tx_bytes / 1024);
690 if (!slave->enabled) {
691 ds_put_cstr(&ds, " (disabled)");
693 if (!list_is_empty(&slave->entries)) {
694 struct bond_entry *e;
696 ds_put_cstr(&ds, " (");
697 LIST_FOR_EACH (e, list_node, &slave->entries) {
698 if (&e->list_node != list_front(&slave->entries)) {
699 ds_put_cstr(&ds, " + ");
701 ds_put_format(&ds, "h%td: %"PRIu64"kB",
702 e - bond->hash, e->tx_bytes / 1024);
704 ds_put_cstr(&ds, ")");
707 VLOG_DBG("bond %s:%s", bond->name, ds_cstr(&ds));
712 /* Shifts 'hash' from its current slave to 'to'. */
714 bond_shift_load(struct bond_entry *hash, struct bond_slave *to,
717 struct bond_slave *from = hash->slave;
718 struct bond *bond = from->bond;
719 uint64_t delta = hash->tx_bytes;
721 VLOG_INFO("bond %s: shift %"PRIu64"kB of load (with hash %td) "
722 "from %s to %s (now carrying %"PRIu64"kB and "
723 "%"PRIu64"kB load, respectively)",
724 bond->name, delta / 1024, hash - bond->hash,
725 from->name, to->name,
726 (from->tx_bytes - delta) / 1024,
727 (to->tx_bytes + delta) / 1024);
729 /* Shift load away from 'from' to 'to'. */
730 from->tx_bytes -= delta;
731 to->tx_bytes += delta;
733 /* Arrange for flows to be revalidated. */
734 tag_set_add(set, hash->tag);
736 hash->tag = tag_create_random();
739 /* Pick and returns a bond_entry to migrate to 'to' (the least-loaded slave),
740 * given that doing so must decrease the ratio of the load on the two slaves by
741 * at least 0.1. Returns NULL if there is no appropriate entry.
743 * The list of entries isn't sorted. I don't know of a reason to prefer to
744 * shift away small hashes or large hashes. */
745 static struct bond_entry *
746 choose_entry_to_migrate(const struct bond_slave *from, uint64_t to_tx_bytes)
748 struct bond_entry *e;
750 if (list_is_short(&from->entries)) {
751 /* 'from' carries no more than one MAC hash, so shifting load away from
752 * it would be pointless. */
756 LIST_FOR_EACH (e, list_node, &from->entries) {
757 double old_ratio, new_ratio;
760 if (to_tx_bytes == 0) {
761 /* Nothing on the new slave, move it. */
766 old_ratio = (double)from->tx_bytes / to_tx_bytes;
767 new_ratio = (double)(from->tx_bytes - delta) / (to_tx_bytes + delta);
768 if (old_ratio - new_ratio > 0.1) {
769 /* Would decrease the ratio, move it. */
777 /* Inserts 'slave' into 'bals' so that descending order of 'tx_bytes' is
780 insert_bal(struct list *bals, struct bond_slave *slave)
782 struct bond_slave *pos;
784 LIST_FOR_EACH (pos, bal_node, bals) {
785 if (slave->tx_bytes > pos->tx_bytes) {
789 list_insert(&pos->bal_node, &slave->bal_node);
792 /* Removes 'slave' from its current list and then inserts it into 'bals' so
793 * that descending order of 'tx_bytes' is maintained. */
795 reinsert_bal(struct list *bals, struct bond_slave *slave)
797 list_remove(&slave->bal_node);
798 insert_bal(bals, slave);
801 /* If 'bond' needs rebalancing, does so.
803 * The caller should have called bond_account() for each active flow, to ensure
804 * that flow data is consistently accounted at this point. */
806 bond_rebalance(struct bond *bond, struct tag_set *tags)
808 struct bond_slave *slave;
809 struct bond_entry *e;
812 if (!bond_is_balanced(bond) || time_msec() < bond->next_rebalance) {
815 bond->next_rebalance = time_msec() + bond->rebalance_interval;
817 /* Add each bond_entry to its slave's 'entries' list.
818 * Compute each slave's tx_bytes as the sum of its entries' tx_bytes. */
819 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
821 list_init(&slave->entries);
823 for (e = &bond->hash[0]; e <= &bond->hash[BOND_MASK]; e++) {
824 if (e->slave && e->tx_bytes) {
825 e->slave->tx_bytes += e->tx_bytes;
826 list_push_back(&e->slave->entries, &e->list_node);
830 /* Add enabled slaves to 'bals' in descending order of tx_bytes.
832 * XXX This is O(n**2) in the number of slaves but it could be O(n lg n)
833 * with a proper list sort algorithm. */
835 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
836 if (slave->enabled) {
837 insert_bal(&bals, slave);
840 log_bals(bond, &bals);
842 /* Shift load from the most-loaded slaves to the least-loaded slaves. */
843 while (!list_is_short(&bals)) {
844 struct bond_slave *from = bond_slave_from_bal_node(list_front(&bals));
845 struct bond_slave *to = bond_slave_from_bal_node(list_back(&bals));
848 overload = from->tx_bytes - to->tx_bytes;
849 if (overload < to->tx_bytes >> 5 || overload < 100000) {
850 /* The extra load on 'from' (and all less-loaded slaves), compared
851 * to that of 'to' (the least-loaded slave), is less than ~3%, or
852 * it is less than ~1Mbps. No point in rebalancing. */
856 /* 'from' is carrying significantly more load than 'to', and that load
857 * is split across at least two different hashes. */
858 e = choose_entry_to_migrate(from, to->tx_bytes);
860 bond_shift_load(e, to, tags);
862 /* Delete element from from->entries.
864 * We don't add the element to to->hashes. That would only allow
865 * 'e' to be migrated to another slave in this rebalancing run, and
866 * there is no point in doing that. */
867 list_remove(&e->list_node);
869 /* Re-sort 'bals'. */
870 reinsert_bal(&bals, from);
871 reinsert_bal(&bals, to);
873 /* Can't usefully migrate anything away from 'from'.
874 * Don't reconsider it. */
875 list_remove(&from->bal_node);
879 /* Implement exponentially weighted moving average. A weight of 1/2 causes
880 * historical data to decay to <1% in 7 rebalancing runs. 1,000,000 bytes
881 * take 20 rebalancing runs to decay to 0 and get deleted entirely. */
882 for (e = &bond->hash[0]; e <= &bond->hash[BOND_MASK]; e++) {
890 /* Bonding unixctl user interface functions. */
893 bond_find(const char *name)
897 HMAP_FOR_EACH_WITH_HASH (bond, hmap_node, hash_string(name, 0),
899 if (!strcmp(bond->name, name)) {
906 static struct bond_slave *
907 bond_lookup_slave(struct bond *bond, const char *slave_name)
909 struct bond_slave *slave;
911 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
912 if (!strcmp(slave->name, slave_name)) {
920 bond_unixctl_list(struct unixctl_conn *conn,
921 int argc OVS_UNUSED, const char *argv[] OVS_UNUSED,
922 void *aux OVS_UNUSED)
924 struct ds ds = DS_EMPTY_INITIALIZER;
925 const struct bond *bond;
927 ds_put_cstr(&ds, "bond\ttype\tslaves\n");
929 HMAP_FOR_EACH (bond, hmap_node, &all_bonds) {
930 const struct bond_slave *slave;
933 ds_put_format(&ds, "%s\t%s\t",
934 bond->name, bond_mode_to_string(bond->balance));
937 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
939 ds_put_cstr(&ds, ", ");
941 ds_put_cstr(&ds, slave->name);
943 ds_put_char(&ds, '\n');
945 unixctl_command_reply(conn, ds_cstr(&ds));
950 bond_print_details(struct ds *ds, const struct bond *bond)
952 struct shash slave_shash = SHASH_INITIALIZER(&slave_shash);
953 const struct shash_node **sorted_slaves = NULL;
954 const struct bond_slave *slave;
957 ds_put_format(ds, "---- %s ----\n", bond->name);
958 ds_put_format(ds, "bond_mode: %s\n",
959 bond_mode_to_string(bond->balance));
961 ds_put_format(ds, "bond-hash-basis: %"PRIu32"\n", bond->basis);
963 ds_put_format(ds, "updelay: %d ms\n", bond->updelay);
964 ds_put_format(ds, "downdelay: %d ms\n", bond->downdelay);
966 if (bond_is_balanced(bond)) {
967 ds_put_format(ds, "next rebalance: %lld ms\n",
968 bond->next_rebalance - time_msec());
971 ds_put_cstr(ds, "lacp_status: ");
972 switch (bond->lacp_status) {
973 case LACP_NEGOTIATED:
974 ds_put_cstr(ds, "negotiated\n");
976 case LACP_CONFIGURED:
977 ds_put_cstr(ds, "configured\n");
980 ds_put_cstr(ds, "off\n");
983 ds_put_cstr(ds, "<unknown>\n");
987 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
988 shash_add(&slave_shash, slave->name, slave);
990 sorted_slaves = shash_sort(&slave_shash);
992 for (i = 0; i < shash_count(&slave_shash); i++) {
993 struct bond_entry *be;
995 slave = sorted_slaves[i]->data;
998 ds_put_format(ds, "\nslave %s: %s\n",
999 slave->name, slave->enabled ? "enabled" : "disabled");
1000 if (slave == bond->active_slave) {
1001 ds_put_cstr(ds, "\tactive slave\n");
1003 if (slave->delay_expires != LLONG_MAX) {
1004 ds_put_format(ds, "\t%s expires in %lld ms\n",
1005 slave->enabled ? "downdelay" : "updelay",
1006 slave->delay_expires - time_msec());
1009 ds_put_format(ds, "\tmay_enable: %s\n",
1010 slave->may_enable ? "true" : "false");
1012 if (!bond_is_balanced(bond)) {
1017 for (be = bond->hash; be <= &bond->hash[BOND_MASK]; be++) {
1018 int hash = be - bond->hash;
1020 if (be->slave != slave) {
1024 ds_put_format(ds, "\thash %d: %"PRIu64" kB load\n",
1025 hash, be->tx_bytes / 1024);
1027 /* XXX How can we list the MACs assigned to hashes of SLB bonds? */
1030 shash_destroy(&slave_shash);
1031 free(sorted_slaves);
1032 ds_put_cstr(ds, "\n");
1036 bond_unixctl_show(struct unixctl_conn *conn,
1037 int argc, const char *argv[],
1038 void *aux OVS_UNUSED)
1040 struct ds ds = DS_EMPTY_INITIALIZER;
1043 const struct bond *bond = bond_find(argv[1]);
1046 unixctl_command_reply_error(conn, "no such bond");
1049 bond_print_details(&ds, bond);
1051 const struct bond *bond;
1053 HMAP_FOR_EACH (bond, hmap_node, &all_bonds) {
1054 bond_print_details(&ds, bond);
1058 unixctl_command_reply(conn, ds_cstr(&ds));
1063 bond_unixctl_migrate(struct unixctl_conn *conn,
1064 int argc OVS_UNUSED, const char *argv[],
1065 void *aux OVS_UNUSED)
1067 const char *bond_s = argv[1];
1068 const char *hash_s = argv[2];
1069 const char *slave_s = argv[3];
1071 struct bond_slave *slave;
1072 struct bond_entry *entry;
1075 bond = bond_find(bond_s);
1077 unixctl_command_reply_error(conn, "no such bond");
1081 if (bond->balance != BM_SLB) {
1082 unixctl_command_reply_error(conn, "not an SLB bond");
1086 if (strspn(hash_s, "0123456789") == strlen(hash_s)) {
1087 hash = atoi(hash_s) & BOND_MASK;
1089 unixctl_command_reply_error(conn, "bad hash");
1093 slave = bond_lookup_slave(bond, slave_s);
1095 unixctl_command_reply_error(conn, "no such slave");
1099 if (!slave->enabled) {
1100 unixctl_command_reply_error(conn, "cannot migrate to disabled slave");
1104 entry = &bond->hash[hash];
1105 tag_set_add(&bond->unixctl_tags, entry->tag);
1106 entry->slave = slave;
1107 entry->tag = tag_create_random();
1108 unixctl_command_reply(conn, "migrated");
1112 bond_unixctl_set_active_slave(struct unixctl_conn *conn,
1113 int argc OVS_UNUSED, const char *argv[],
1114 void *aux OVS_UNUSED)
1116 const char *bond_s = argv[1];
1117 const char *slave_s = argv[2];
1119 struct bond_slave *slave;
1121 bond = bond_find(bond_s);
1123 unixctl_command_reply_error(conn, "no such bond");
1127 slave = bond_lookup_slave(bond, slave_s);
1129 unixctl_command_reply_error(conn, "no such slave");
1133 if (!slave->enabled) {
1134 unixctl_command_reply_error(conn, "cannot make disabled slave active");
1138 if (bond->active_slave != slave) {
1139 tag_set_add(&bond->unixctl_tags, bond_get_active_slave_tag(bond));
1140 bond->active_slave = slave;
1141 bond->active_slave->tag = tag_create_random();
1142 VLOG_INFO("bond %s: active interface is now %s",
1143 bond->name, slave->name);
1144 bond->send_learning_packets = true;
1145 unixctl_command_reply(conn, "done");
1147 unixctl_command_reply(conn, "no change");
1152 enable_slave(struct unixctl_conn *conn, const char *argv[], bool enable)
1154 const char *bond_s = argv[1];
1155 const char *slave_s = argv[2];
1157 struct bond_slave *slave;
1159 bond = bond_find(bond_s);
1161 unixctl_command_reply_error(conn, "no such bond");
1165 slave = bond_lookup_slave(bond, slave_s);
1167 unixctl_command_reply_error(conn, "no such slave");
1171 bond_enable_slave(slave, enable, &bond->unixctl_tags);
1172 unixctl_command_reply(conn, enable ? "enabled" : "disabled");
1176 bond_unixctl_enable_slave(struct unixctl_conn *conn,
1177 int argc OVS_UNUSED, const char *argv[],
1178 void *aux OVS_UNUSED)
1180 enable_slave(conn, argv, true);
1184 bond_unixctl_disable_slave(struct unixctl_conn *conn,
1185 int argc OVS_UNUSED, const char *argv[],
1186 void *aux OVS_UNUSED)
1188 enable_slave(conn, argv, false);
1192 bond_unixctl_hash(struct unixctl_conn *conn, int argc, const char *argv[],
1193 void *aux OVS_UNUSED)
1195 const char *mac_s = argv[1];
1196 const char *vlan_s = argc > 2 ? argv[2] : NULL;
1197 const char *basis_s = argc > 3 ? argv[3] : NULL;
1198 uint8_t mac[ETH_ADDR_LEN];
1205 if (sscanf(vlan_s, "%u", &vlan) != 1) {
1206 unixctl_command_reply_error(conn, "invalid vlan");
1214 if (sscanf(basis_s, "%"PRIu32, &basis) != 1) {
1215 unixctl_command_reply_error(conn, "invalid basis");
1222 if (sscanf(mac_s, ETH_ADDR_SCAN_FMT, ETH_ADDR_SCAN_ARGS(mac))
1223 == ETH_ADDR_SCAN_COUNT) {
1224 hash = bond_hash_src(mac, vlan, basis) & BOND_MASK;
1226 hash_cstr = xasprintf("%u", hash);
1227 unixctl_command_reply(conn, hash_cstr);
1230 unixctl_command_reply_error(conn, "invalid mac");
1237 unixctl_command_register("bond/list", "", 0, 0, bond_unixctl_list, NULL);
1238 unixctl_command_register("bond/show", "[port]", 0, 1, bond_unixctl_show,
1240 unixctl_command_register("bond/migrate", "port hash slave", 3, 3,
1241 bond_unixctl_migrate, NULL);
1242 unixctl_command_register("bond/set-active-slave", "port slave", 2, 2,
1243 bond_unixctl_set_active_slave, NULL);
1244 unixctl_command_register("bond/enable-slave", "port slave", 2, 2,
1245 bond_unixctl_enable_slave, NULL);
1246 unixctl_command_register("bond/disable-slave", "port slave", 2, 2,
1247 bond_unixctl_disable_slave, NULL);
1248 unixctl_command_register("bond/hash", "mac [vlan] [basis]", 1, 3,
1249 bond_unixctl_hash, NULL);
1253 bond_entry_reset(struct bond *bond)
1255 if (bond->balance != BM_AB) {
1256 size_t hash_len = (BOND_MASK + 1) * sizeof *bond->hash;
1259 bond->hash = xmalloc(hash_len);
1261 memset(bond->hash, 0, hash_len);
1263 bond->next_rebalance = time_msec() + bond->rebalance_interval;
1270 static struct bond_slave *
1271 bond_slave_lookup(struct bond *bond, const void *slave_)
1273 struct bond_slave *slave;
1275 HMAP_FOR_EACH_IN_BUCKET (slave, hmap_node, hash_pointer(slave_, 0),
1277 if (slave->aux == slave_) {
1286 bond_enable_slave(struct bond_slave *slave, bool enable, struct tag_set *tags)
1288 struct bond *bond = slave->bond;
1289 slave->delay_expires = LLONG_MAX;
1290 if (enable != slave->enabled) {
1291 slave->enabled = enable;
1292 if (!slave->enabled) {
1293 VLOG_WARN("interface %s: disabled", slave->name);
1295 tag_set_add(tags, slave->tag);
1298 VLOG_WARN("interface %s: enabled", slave->name);
1299 slave->tag = tag_create_random();
1302 if (bond->balance == BM_STABLE) {
1303 bond->bond_revalidate = true;
1309 bond_link_status_update(struct bond_slave *slave, struct tag_set *tags)
1311 struct bond *bond = slave->bond;
1314 up = netdev_get_carrier(slave->netdev) && slave->may_enable;
1315 if ((up == slave->enabled) != (slave->delay_expires == LLONG_MAX)) {
1316 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 20);
1317 VLOG_INFO_RL(&rl, "interface %s: link state %s",
1318 slave->name, up ? "up" : "down");
1319 if (up == slave->enabled) {
1320 slave->delay_expires = LLONG_MAX;
1321 VLOG_INFO_RL(&rl, "interface %s: will not be %s",
1322 slave->name, up ? "disabled" : "enabled");
1324 int delay = (bond->lacp_status != LACP_DISABLED ? 0
1325 : up ? bond->updelay : bond->downdelay);
1326 slave->delay_expires = time_msec() + delay;
1328 VLOG_INFO_RL(&rl, "interface %s: will be %s if it stays %s "
1331 up ? "enabled" : "disabled",
1338 if (time_msec() >= slave->delay_expires) {
1339 bond_enable_slave(slave, up, tags);
1344 bond_hash_src(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan, uint32_t basis)
1346 return hash_3words(hash_bytes(mac, ETH_ADDR_LEN, 0), vlan, basis);
1350 bond_hash_tcp(const struct flow *flow, uint16_t vlan, uint32_t basis)
1352 struct flow hash_flow = *flow;
1353 hash_flow.vlan_tci = htons(vlan);
1355 /* The symmetric quality of this hash function is not required, but
1356 * flow_hash_symmetric_l4 already exists, and is sufficient for our
1357 * purposes, so we use it out of convenience. */
1358 return flow_hash_symmetric_l4(&hash_flow, basis);
1362 bond_hash(const struct bond *bond, const struct flow *flow, uint16_t vlan)
1364 assert(bond->balance == BM_TCP || bond->balance == BM_SLB);
1366 return (bond->balance == BM_TCP
1367 ? bond_hash_tcp(flow, vlan, bond->basis)
1368 : bond_hash_src(flow->dl_src, vlan, bond->basis));
1371 static struct bond_entry *
1372 lookup_bond_entry(const struct bond *bond, const struct flow *flow,
1375 return &bond->hash[bond_hash(bond, flow, vlan) & BOND_MASK];
1378 /* This function uses Highest Random Weight hashing to choose an output slave.
1379 * This approach only reassigns a minimal number of flows when slaves are
1380 * enabled or disabled. Unfortunately, it has O(n) performance against the
1381 * number of slaves. There exist algorithms which are O(1), but have slightly
1382 * more complex implementations and require the use of memory. This may need
1383 * to be reimplemented if it becomes a performance bottleneck. */
1384 static struct bond_slave *
1385 choose_stb_slave(const struct bond *bond, uint32_t flow_hash)
1387 struct bond_slave *best, *slave;
1392 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1393 if (slave->enabled) {
1396 hash = hash_2words(flow_hash, slave->stb_id);
1397 if (!best || hash > best_hash) {
1407 static struct bond_slave *
1408 choose_output_slave(const struct bond *bond, const struct flow *flow,
1409 uint16_t vlan, tag_type *tags)
1411 struct bond_entry *e;
1413 if (bond->lacp_status == LACP_CONFIGURED) {
1414 /* LACP has been configured on this bond but negotiations were
1415 * unsuccussful. Drop all traffic. */
1419 switch (bond->balance) {
1421 return bond->active_slave;
1424 return choose_stb_slave(bond, bond_hash_tcp(flow, vlan, bond->basis));
1427 if (bond->lacp_status != LACP_NEGOTIATED) {
1428 /* Must have LACP negotiations for TCP balanced bonds. */
1433 if (!bond_is_balanced(bond)) {
1434 return choose_stb_slave(bond, bond_hash(bond, flow, vlan));
1436 e = lookup_bond_entry(bond, flow, vlan);
1437 if (!e->slave || !e->slave->enabled) {
1438 e->slave = CONTAINER_OF(hmap_random_node(&bond->slaves),
1439 struct bond_slave, hmap_node);
1440 if (!e->slave->enabled) {
1441 e->slave = bond->active_slave;
1443 e->tag = tag_create_random();
1453 static struct bond_slave *
1454 bond_choose_slave(const struct bond *bond)
1456 struct bond_slave *slave, *best;
1458 /* Find an enabled slave. */
1459 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1460 if (slave->enabled) {
1465 /* All interfaces are disabled. Find an interface that will be enabled
1466 * after its updelay expires. */
1468 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1469 if (slave->delay_expires != LLONG_MAX
1470 && slave->may_enable
1471 && (!best || slave->delay_expires < best->delay_expires)) {
1479 bond_choose_active_slave(struct bond *bond, struct tag_set *tags)
1481 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 20);
1482 struct bond_slave *old_active_slave = bond->active_slave;
1484 bond->active_slave = bond_choose_slave(bond);
1485 if (bond->active_slave) {
1486 if (bond->active_slave->enabled) {
1487 VLOG_INFO_RL(&rl, "bond %s: active interface is now %s",
1488 bond->name, bond->active_slave->name);
1490 VLOG_INFO_RL(&rl, "bond %s: active interface is now %s, skipping "
1491 "remaining %lld ms updelay (since no interface was "
1492 "enabled)", bond->name, bond->active_slave->name,
1493 bond->active_slave->delay_expires - time_msec());
1494 bond_enable_slave(bond->active_slave, true, tags);
1497 if (!old_active_slave) {
1498 tag_set_add(tags, bond->no_slaves_tag);
1501 bond->send_learning_packets = true;
1502 } else if (old_active_slave) {
1503 VLOG_WARN_RL(&rl, "bond %s: all interfaces disabled", bond->name);
1507 /* Returns the tag for 'bond''s active slave, or 'bond''s no_slaves_tag if
1508 * there is no active slave. */
1510 bond_get_active_slave_tag(const struct bond *bond)
1512 return (bond->active_slave
1513 ? bond->active_slave->tag
1514 : bond->no_slaves_tag);
1517 /* Attempts to make the sum of the bond slaves' statistics appear on the fake
1518 * bond interface. */
1520 bond_update_fake_slave_stats(struct bond *bond)
1522 struct netdev_stats bond_stats;
1523 struct bond_slave *slave;
1524 struct netdev *bond_dev;
1526 memset(&bond_stats, 0, sizeof bond_stats);
1528 HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1529 struct netdev_stats slave_stats;
1531 if (!netdev_get_stats(slave->netdev, &slave_stats)) {
1532 /* XXX: We swap the stats here because they are swapped back when
1533 * reported by the internal device. The reason for this is
1534 * internal devices normally represent packets going into the
1535 * system but when used as fake bond device they represent packets
1536 * leaving the system. We really should do this in the internal
1537 * device itself because changing it here reverses the counts from
1538 * the perspective of the switch. However, the internal device
1539 * doesn't know what type of device it represents so we have to do
1540 * it here for now. */
1541 bond_stats.tx_packets += slave_stats.rx_packets;
1542 bond_stats.tx_bytes += slave_stats.rx_bytes;
1543 bond_stats.rx_packets += slave_stats.tx_packets;
1544 bond_stats.rx_bytes += slave_stats.tx_bytes;
1548 if (!netdev_open(bond->name, "system", &bond_dev)) {
1549 netdev_set_stats(bond_dev, &bond_stats);
1550 netdev_close(bond_dev);